Image analysis – Image transformation or preprocessing – Convolution
Reexamination Certificate
1999-10-06
2003-11-04
Couso, Yon J. (Department: 2725)
Image analysis
Image transformation or preprocessing
Convolution
C708S420000
Reexamination Certificate
active
06643412
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to convolution for examination using an image device and, more particularly, to a method and apparatus for high speed convolution designed to process high speed convolution irrespective of a mask size through a novel image file structure a linearity of the convolution and overcome problems with the related art convolution processing that cannot be actually realized due to an excessive processing time though examination reliability is enhanced with an increase in the mask size for the convolution.
2. Discussion of Related Art
In an image processing, convolution refers to a procedure of operation to obtain corresponding pixel values by multiplying the values of pixels surrounding image data in an area such as a kernel area by kernel values and summing the resulting values, in a case where the kernel center is matched to each pixel of the image data through an operation of a kernel composed of numerals and the image data.
When the individual pixel value of image data is I(x,y), the mask size (2m+1)×(2n+1) and the mask value M(x,y), the resulting value of operation for each pixel can be expressed by:
∑
(
x
,
y
)
=
∑
i
=
-
m
i
=
m
∑
j
=
-
n
j
=
n
I
(
x
+
i
,
y
+
j
)
×
M
(
i
+
m
+
l
,
j
+
n
+
l
)
Here, the index of the image data out of a range is zero and that of the mask value M(l.j) is positive.
FIG. 1
shows a one-dimenisional example of the calculation procedure.
A filter is generally used in the examination process through image processing and there are some cases where quality of output images is changed according to the mask size. When the mask size is increased, the image data is insensitive to the noise component and the user has many values to control so that more accurate values can be obtained. However, there is a need of multiplication and summation for the individual pixels as many as the mask size in the operation procedure. Therefore, the operation procedure takes more time with an increase in the mask size. This results in limitation of the mask size in actual applications.
As well known, the convolution procedure is to obtain the resulting value of the individual pixel by multiplying the values corresponding to the pixels and summing the multiplication results. However, this procedure involves a problem in that the number of calculations rapidly increases with an increase in the size of the filter. To solve the problem, there have been suggested many inventions in which the two-dimensional mask is divided into one-dimensional ones, or the calculations are performed in real tine by use of a high speed hardware.
For the related art method using the hardware, U.S. Pat. No 5,119,444 discloses Laplacian and Gaussian simulations using the hardware. Here, a simplest Laplacian filter and three binomial filters are sequentially used to constitute the hardware for 7×7 Gaussi an simulation.
FIG. 2
shows that use is made of a delay to store a target pixel value and its surrounding pixel values during image acquisition according to prior art. Here, the reference numeral
42
represents an SEM for image acquisition, the reference numeral
43
an analog/digital converter for converting an analog video signal to its corresponding digital image data, the reference numeral
44
a pattern compensator for outputting pattern compensation data. The reference numerals
51
and
52
indicate switches, the reference numeral
50
a delay, and the reference numerals
45
and
49
output lines for storing, in a latch, image data obtained by combining signals via the switches
51
and
52
and signals via a plurality of delays.
FIG. 3
is a diagram illustrating a procedure of obtaining Laplacian in a manner of hardware, in which the Laplacian is obtained by summing image values of pixels surrounding a target pixel out of five image values acquired in
FIG. 2
via summation circuits
60
,
61
and
64
, multiplying at a shifter the image value of the target pixel except for the four images values summed at the summation circuits
60
and
61
, and subtracting at a subtractor
68
one of the two values obtained from the shifter
60
from the other value.
FIG. 4
is a diagram illustrating a procedure of obtaining Gaussian in a manner of hardware, in which the one-dimensional Gaussian is obtained by delaying the digital video sign cals obtained in
FIG. 3
via delays
78
and
79
and then using summation circuits
70
and
74
and shifters
72
and
77
.
FIG. 5
is a diagram illustrating a procedure of obtaining 7n×7n Gaussian using the circuit shown in
FIG. 4
in a manner of hardware.
However these related art convolution apparatuses has a disadvantage in that their speed depends on the structure of a hardware and is not easy to change and that a variety of filters are difficult to realize.
Further, in a case where it is needed to increase the filter mask size in order to enhance the quality of results in a real-time calculation, the speed of the hardware is deteriorated or the cost is greatly increased.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a method and apparatus for high speed convolution, designed to process high speed convolution irrespective of a mask size through a novel image file structure and linearity of the convolution and overcome problems with the related art convolution processing method and apparatus that cannot be actually realized due to an excessive processing time though examination reliability is enhanced with an increase in the mask size for the convolution.
To achieve the first object of the present invention, there is provided a method for high speed convolution including the steps of: determining a convolution mask by dividing a theoretical mask into a predetermined number of areas as many as a multiple of sampling intervals of target data; generating accumulative image data of a target image to be convolved and storing them in a memory; calculating image summation data in an area corresponding to the area of each step of the mask from the accumulative image data; and calculating the convolution of pixels from the corresponding area image data and mask step values corresponding to the area.
The present invention also provides an apparatus for high speed convolution including an accumulative image data generator for converting an input image of a camera to digital image data, adding the converted image data to image summation data from an origin on the present horizontal line to a previous pixel, and adding the result value to a pixel value in a rectangular area formed by an origin and pixels on the line previous to a present pixel, to generate an accumulative image data; a corresponding area data calculator for extracting a predetermined number of partial area data from the accumulative image data generated from the accumulative image data generator, selectively adding and subtracting the extracted partial area data to obtain image summation data of the corresponding area, and outputting a mask step value corresponding to the area; and a pixel convolution value output for multiplying the corresponding area image data obtained from the corresponding area data calculator by the corresponding mask step value and summing the multiplication results to output a pixel convolution value.
REFERENCES:
patent: 5151953 (1992-09-01), Landeta
patent: 5948053 (1999-09-01), Kamiya
patent: 6215908 (2001-04-01), Pazmino et al.
Hong Cheol-Kee
Kim Cheol-Woo
Couso Yon J.
Jacobson & Holman PLLC
LG Electronics Inc.
LandOfFree
Method and apparatus for high speed convolution does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for high speed convolution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for high speed convolution will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3183960