Pattern image detection method
Provided are a method and apparatus for detecting a pattern image, and more particularly, a pattern image detection method and a pattern image detection apparatus for effectively detecting a pattern of a template image from a target image. The pattern image detection method and the pattern image detection apparatus can provide an effect of quickly and accurately detecting the pattern of the template image from the target image while reducing the amount of computation for detecting the pattern of the template image.
1. A pattern image detection method in which a template image is compared with a target image and a pattern included in the template image is searched for from the target image, as to determine a location in the target image where a chip placement or other operations at the determined location is to be performed, the pattern image detection method comprising:
(a) receiving the template image and the target image by a receiving module;
(b) receiving a reference similarity that is a criterion for determining whether there is a similarity, a reference skip distance that defines a distance to a next comparison reference pixel in the target image, and detailed search criteria that defines a range in which a detailed search is performed in the target image, by the receiving module;
(c) dividing the template image into a plurality of regions having the same size by a template region module;
(d) summing a square of a brightness value of each of pixels in each region of the template image and setting the sum as a brightness value for each region, by the template region module;
(e) selecting a comparison reference pixel of the target image by a target region module;
(f) selecting a comparison target area having the same size as the template image on the basis of the comparison reference pixel of the target image and dividing the comparison target area into a plurality of regions having the same size as the regions of the template image, by the target region module;
(g) summing a square of a brightness value of each of pixels in each region of the comparison target area of the target image and setting the sum as a brightness value for each region, by the target region module;
(h) performing a normalized cross-correlation calculation according to Equation 1 in units of regions on the brightness value for each region of the template image and the comparison target area of the target image to calculate a similarity between the template image and the comparison target area, by a similarity calculation module;
R
(
u
,
v
)
=
∑
Y
=
0
B
Y
-
1
∑
X
=
0
B
X
-
1
(
T
(
X
,
Y
)
-
E
(
T
)
)
(
D
u
,
v
(
X
,
Y
)
-
E
(
D
u
,
v
)
)
∑
Y
=
0
B
Y
-
1
∑
X
=
0
B
X
-
1
(
T
(
X
,
Y
)
-
E
(
T
)
)
2
∑
Y
=
0
B
Y
-
1
∑
X
=
0
B
X
-
1
(
D
u
,
v
(
X
,
Y
)
-
E
(
D
u
,
v
)
)
2
[
Equation
1
]
where, u: a position of the target image in a horizontal axis, v: a position of the target image in a vertical axis, X: a position of a region of the template image in the horizontal axis, Y: a position of a region of the template image in the vertical axis, W: a horizontal length of the template image, H: a vertical length of the template image, B X : the number of regions of the template image in the horizontal axis, B Y : the number of regions of the template image in the vertical axis, T: the entire region of the template image, D u,v : the entire comparison region of the target image, I T (x,y): a brightness value of an x, y position of the template image, I D (x,y): a brightness value of an x, y position of the target image,
T
(
X
,
Y
)
=
∑
y
=
Y
H
B
Y
(
Y
+
1
)
H
B
Y
∑
x
=
X
W
B
X
(
X
+
1
)
W
B
X
I
T
(
x
,
y
)
2
D
u
,
v
(
X
,
Y
)
=
∑
y
=
Y
H
B
Y
(
Y
+
1
)
H
B
Y
∑
x
=
X
W
B
X
(
X
+
1
)
W
B
X
I
D
(
x
+
u
,
y
+
v
)
2
E
(
T
)
=
1
WH
∑
y
=
0
H
∑
x
=
0
W
I
T
(
x
,
y
)
2
E
(
D
u
,
v
)
=
1
WH
∑
y
=
0
H
∑
x
=
0
W
I
D
(
x
+
u
,
y
+
v
)
2
(i) comparing the similarity calculated in operation (h) by the similarity calculation module with the reference similarity, setting the comparison reference pixel as a point of interest when the similarity is greater than the reference similarity, and updating a position of a next pixel adjacent to the comparison reference pixel as the comparison reference pixel, by a similarity determination module;
(j) comparing the similarity calculated in operation (h) by the similarity calculation module with the reference similarity, and updating a position of a pixel spaced apart from the comparison reference pixel by the reference skip distance as the comparison reference pixel when the similarity is less than the reference similarity, by the similarity determination module;
(k) repeating operations (f) to (j) for the comparison reference pixel updated in operation (i) or (j); and
(l) performing a similarity calculation of Equation 1 in units of regions or pixels having a size smaller than that of the region obtained in operations (c) and (f) within a distance range that is set by the detailed search criteria around the point of interest set in operation (i); and
(m) identifying a pixel having the largest similarity around the point of interest from the target image, by a position determination module, wherein a position of the identified pixel in the target image is where the pattern to be searched for is located.
2. The pattern image detection method of claim 1 , wherein
in operation (a), the receiving module squares the brightness value of each pixel of the template image and the target image, and then converts each of the template image and the target image into an integral image,
in operation (d), the sum of the square of a brightness value for each region is calculated by using the integral image of the template image generated in operation (a), and
in operation (g), the sum of the square of the brightness value for each region is calculated by using the integral image of the target image generated in operation (a).
3. The pattern image detection method of claim 1 , wherein
in operation (a), the receiving module reduces the number of bits by using a brightness value of 8-bit units, which is converted using a weight ratio between the square of the brightness value of each pixel of the template image and the target image and a 16-bit resolution, and then converts each of the template image and the target image into the form of an integral image,
in operation (d), the sum of the square of a brightness value for each region is calculated by using the integral image of the template image generated in operation (a), and
in operation (g), the sum of the square of the brightness value for each region is calculated by using the integral image of the target image generated in operation (a).
4. The pattern image detection method of claim 1 , wherein
in operation (b), the receiving module receives the reference skip distance that is set to have a value that varies according to a numerical range of a similarity to be calculated in operation (h) by the similarity calculation module, and
in operation (j), the comparison reference pixel is updated according to a value corresponding to the reference skip distance for each similarity range that is stored in the receiving module in operation (b).
5. The pattern image detection method of claim 2 , wherein
in operation (b), the receiving module receives the reference skip distance that is set to have a value that varies according to a numerical range of a similarity to be calculated in operation (h) by the similarity calculation module, and
in operation (j), the comparison reference pixel is updated according to a value corresponding to the reference skip distance for each similarity range that is stored in the receiving module in operation (b).
6. The pattern image detection method of claim 3 , wherein
in operation (b), the receiving module receives the reference skip distance that is set to have a value that varies according to a numerical range of a similarity to be calculated in operation (h) by the similarity calculation module, and
in operation (j), the comparison reference pixel is updated according to a value corresponding to the reference skip distance for each similarity range that is stored in the receiving module in operation (b).
7. The pattern image detection method of claim 4 , wherein in operation (b), as a value of the similarity is smaller, the reference skip distance received by the receiving module is set to be greater to correspond to the range of the value.
8. The pattern image detection method of claim 5 , wherein in operation (b), as a value of the similarity is smaller, the reference skip distance received by the receiving module is set to be greater to correspond to the range of the value.
9. The pattern image detection method of claim 6 , wherein in operation (b), as a value of the similarity is smaller, the reference skip distance received by the receiving module is set to be greater to correspond to the range of the value.