JP2646564B2 - Image processing method - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image processing method, and in particular, to an arc having a known radius, or a boundary or change point data having a partially missing part, using the circle or the arc. And an image processing method for determining the position of the center of the image.

[Conventional technology]

Conventionally, the method of obtaining the position of the center of a circle or an arc of this type includes a method of obtaining the center of gravity of a binary image and a method of using a vanishing point due to repetition of reduction processing from the binary image. However, these methods cannot be applied to a part of a circle having a chip such as a silicon wafer. In addition, some mirror-shaped wafers from which a good binary image is difficult to obtain can be binarized only in a part of the arc. In such a case, the above-described conventional method cannot be applied.

[Problems to be solved by the invention]

As described above, since the conventional image processing method for determining the position of the center of a circle or an arc uses the entire information of the circle to be positioned, the center position of only a part of the arc is calculated. There is a disadvantage that cannot be performed.

In the method using the Hough transform for an arc, all the boundary points of the image are counted up for all points at a distance γ from each of the boundary points, and then the peak search is performed to find the center of the arc. Since it is required to be obtained, a large amount of calculation is required and a large memory capacity is required. Therefore, there is a drawback that it cannot be applied to a simple arc center position determining device.

[Means for solving the problem]

According to the image processing method of the present invention, a plurality of sets of two extraction points are randomly or regularly extracted from boundary data or change point data of a curve including an arc of an image, and the two sets of extraction points are extracted. From the ratio between the distance between the two points and the radius of the arc to be determined, it is determined whether or not the calculated center distance of the circle can be calculated (= valid) or not (= invalid), and is determined to be valid. Then, a process of obtaining the center position of the circle is performed from them, the coordinate value of the obtained center position is quantized, and the coordinate value of the quantized center position of the circle is counted up. Iterating multiple times, the number of times determined by the ratio of the arc occupying the whole boundary point or change point, to perform peak search for the coordinate value with the largest count value among the quantized coordinate values Is determined as the position of the center of the arc. Configured to include a.

〔Example〕

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is an image diagram schematically showing one embodiment of the present invention.

In FIG. 1 (a), a point on the arc or curve in the image represented in the screen (x ₁ y ₁₎ ~ by extracting any two points and a set from the (x ₁₀ y _10), the A circle having a radius γ passing through a pair of two points is drawn and its intersection is determined. FIG. 1 (b) is an image diagram showing the circle thus obtained and the intersection thereof, where the intersections are concentrated near the center 2 of the arc 1 to be obtained (reference numeral 8).
The statistical risk factor (= probability of finding an erroneous point as a peak) and the number N of points to be extracted and the number M of materials (M = N−1 or , And the determination criteria Q for peak search (search for the degree of concentration) are determined, and the position of the center of the circle is determined from the partial arc at high speed within the range of allowable accuracy.

If necessary, the position of the center of the arc can be calculated with high accuracy by giving a perturbation from the obtained center position of the arc and evaluating the coincidence between the circumference of the radius γ and the arc. That is, with respect to the coordinate value of the center obtained by performing the peak search, a minute area centered on the point is set, and a circle having a radius γ centered on each of a plurality of points provided in the minute area is drawn. Count the number of boundary points present on the circumference of the circle, determine the point with the largest number of boundary points among the plurality of points in the micro area as the center of the arc, and accurately determine the center of the arc. The position can be calculated.

Also, when counting up, the count number relating to the center coordinate value and the coordinate values of two randomly selected points are simultaneously stored, and after performing a peak search, the minimum value is obtained for all points corresponding to the peak. The arc may be re-estimated by the square method, and the accuracy up to the sub-pixel may be obtained.

FIG. 2 is an image diagram showing an example of an image after extracting a boundary of a processing object in the embodiment of FIG.

In FIG. 2, an arc 1 is an arc whose center 2 is to be determined, and curves 3a to 3d are portions of the arc or other curves for which it is not necessary to determine the center. The object to be processed is the silicon wafer 4. The curve 3d is a part of an arc of another silicon wafer 5. It is assumed that the arc 1 occupies 40% of the entire length of the entire length of the arc 1 having the changing point or the boundary point and the curves 3a to 3d.

Here, two boundary points are randomly (may be regular) and extracted as one set. That is, a sufficiently long list of randomly selected points (x ₁ y ₁ ), (x ₂ y ₂ )... (X _K y _K ) is created. Are checked one by one to see if they are points on the border of the screen. When a point on the list is found to be a point on the boundary line on the screen, the points are arranged, and two points adjacent to each other in the arrangement order are set as one set.

When the extraction point is a change point, assuming that the number of maximum change points on one scanning line is N _max , (n ₁ y ₁ ), (n ₂ y ₂ )... (N _K y _K ),
A change point list of (additional n _K ∈ ｛1,..., N _max ｝) is created, and if a change point of n _j of the scan line y _j actually exists (excluding virtual change points at both ends of the scan line) Assuming that a change point is found, two points are set as a set in the order in which the change points are found. That is, a scan line number and a change point number of the run length data are searched in advance in the search range, a table of a set of two points generated at random is created, a minimum distance 1 between the two points is obtained, and the minimum distance 1 is obtained. If l is greater than or equal to l <a · γ, it is deleted from the table, and two points are randomly extracted according to this table.

That is, as shown in FIG. 3, the points on the true boundary line among the points (x ₁ y ₁ ) to (x ₈ y ₈ ) extracted at random are (x ₃ y ₃ ) and (x ₃ y ₃ ). x ₅ y ₅ ), (x ₇ y ₇ ) and (x ₈ y ₈ ), and these are [(x ₃ y ₃ ), (x ₅ y ₅ )], [(x ₅ y ₅ ),
(X ₇ y ₇ )], [(x ₇ y ₇ ), (x ₈ y ₈ )], two adjacent points are set as one set.

In some cases, all combinations of all two points obtained at random may be used. in this case,
[(X ₃ y ₃ ), (x ₅ y ₅ )], [(x ₃ y ₃ ), (x ₇ y ₇ )],
[(X ₃ y ₃ ), (x ₈ y ₈ )], [(x ₅ y ₅ ), (x ₇ y ₇ )],
[(X ₅ y ₅ ), (x ₈ y ₈ )], [(x ₇ y ₇ ), (x ₈ y ₈ )]
Use a combination of pairs.

When the change point of the run-length data is used as data, as shown in FIG. 4, a set (n ₁ y ₁ ), (n ₂ y ₂ ), (n ₂ y ₂ ) of a scan line number and a change point number is used. ₃ y ₃ ), (n
₄ y ₄ ) and (n ₅ y ₅ ) are randomly extracted.

Next, the process of obtaining the center point of the arc from the set of two points extracted at random in this manner is performed according to the procedure shown in FIG.

FIG. 5 (a) shows a case where the distance between two points is appropriate and valid and the center can be obtained, and FIG. 5 (b) shows a case where the two points are too far apart and invalid. FIGS. 5 (c) and 5 (d) are diagrams showing a case where a circle can be obtained, but is excluded because the accuracy of the center position is poor due to the distance between two points.

First, in the case shown in FIG. 5A, the distance l ₁ between the two points (x _i y _i ) and (x _{i + 1} y _{i + 1} ) is α with respect to the radius γ of the circle for which the center position is obtained. × γ> l ₁ > β × γ (α = 1.88, β = 0.68). In this case, a circle having a radius γ is drawn from each point, and the intersection of the two circles is obtained as (x _ci y _ci ) and (x _{ci + 1} y _{ci + 1} ). α and β are coefficients that give the upper and lower limits of the distance between the two points, and are values empirically obtained for the work of the example. That is, in FIGS. 5 (c) and 5 (d), the intersection angles of the arcs are close to parallel, and it is impossible to calculate a stable intersection. In the embodiment, the angle of the notch straight line portion of the wafer is 40 degrees. Degree
The values of α and β are set so that the intersection angle of the arc can be secured at 40 degrees or more.

FIG. 5 (b) shows an example in which the intersection cannot be obtained. In this case, l ₂ > 2γ. Fig. 5 (c)
Is an example that is invalid because the distance between two points is too large because 2γl ₃ α · γ. Fig. 5 (d)
Is an example of a case where the distance between two points is too short and becomes invalid because l ₄ ≦ β × γ.

By the above procedure, the effective center candidate point (x _ci ,
y _ci ) ... Next, for the effective center candidate point obtained in this way, if the range in which the center exists is limited, the check is performed and the candidate points are narrowed down. For example, as shown in FIG. 6, when there is a condition that the whole circle must always enter the screen,
Only the inner region 6 (shown by hatching in FIG. 6) which is inside by a distance γ from the edge of the image is the range where the center can exist.

As mentioned above, it is within the range where the center can exist,
The quantizing function (X _i , Y _i ) = f (x _ci , y _ci ) (possibly a multivalent function) is applied to the effective center candidate point (x _ci y _ci ) to count (X _i , Y _i ) (X _i ,
Y _i ) Count up to +1. If the quantization function is multi-valued, it is possible to omit this when performing a peak search later and performing a smoothing process.

The quantization function is determined by the size of the count and the size of the smoothing of the two-dimensional array. For example, as shown in FIG. 7, when x _ci = 6.32 y _ci = 3.5, (X _i , Y _i ) =
(6,3) (7,3) (6,4) (7,4)

If the ratio ρ of the desired arc length to the length of the entire boundary line is 40%, the probability of selecting two points on the approximately correct arc is 16% (= ρ ² ). In addition to this,
At the time when (x _ci , y _ci ) (x _{ci +1} , y _{ci +1} ) can be obtained from α × γ>l> β × γ and the condition that the existence of the center is allowed and two, two establishing indicating a point the position of the center of the arc to be obtained in is 20~40% (ρ ² ~3ρ ²⁾ about. Therefore, in consideration of the stochastic risk factors to determine the appropriate number of sets N (N · ρ ² of about 10 as the minimum necessary),
A peak search of θN × ρ ² × γ (γ is a coefficient and also depends on the multivalence of f, etc.) or more is performed, and an independent peak 8 is obtained in the search, and this is set as the center position.

〔The invention's effect〕

As described above, the image processing method of the present invention is not a comprehensive method like a jutan bombing like a method using the Hough transform of arc extraction, but is a relatively simple image (industrial such as silicon wafer). However, there is an effect that the position of the center of the circle can be easily obtained from the partial arc under a certain risk factor using a stochastic method. If the random number data to be used for each image is created in advance and stored as a table, the same table can be used because each image is independent, so the calculation time for that is greatly reduced. It is possible.

[Brief description of the drawings]

FIG. 1 is an image diagram schematically showing an embodiment of the present invention, FIG. 2 is an image diagram showing an example of an image after boundary extraction in the embodiment of FIG. 1, and FIG. 3 is FIG. FIG. 4 is an image showing the result of random extraction of boundary points for the image of FIG. 4. FIG. 4 is an image showing the result of random extraction of run-leg stator change points from the image of FIG. 5 and FIG. 5 are image diagrams showing a procedure for obtaining the position of the center of the arc from two points extracted at random. FIG. 5 (a) shows a case where the center can be obtained. ) Is a diagram showing a case where the center cannot be obtained, FIG. 6 is an image diagram showing an example of a case where the range where the center of the circle can exist is limited, and FIG. 7 is a coordinate of the obtained center position. It is a schematic diagram which shows the state which counts up a histogram by performing quantization. 1... (Determined) arc 2... (Determined arc) center,
3 Curves (other than the arc to be determined), 4 Silicon wafers, 5 (other parts) (parts of) silicon wafers.

Claims (1)

(57) [Claims] 1. A plurality of sets of two extracted points are randomly or regularly extracted from boundary data or change point data of a curve including an arc of an image, and two points of the set of two extracted points are extracted. It is effective because the center distance of a stable circle can be calculated from the ratio of the distance between the arc and the radius of the arc to be obtained, or is invalid because the center distance of a stable circle cannot be obtained. And if it is determined to be valid, perform a process to determine the position of the center of the circle from them,
The obtained coordinate value of the center position is quantized, the coordinate value of the quantized circle center position is counted up, and the above-mentioned processing is determined from the ratio of the arc to the entire boundary point or change point to be obtained. It is characterized by including performing a peak search for the coordinate value having the largest count value among the quantized coordinate values and determining it as the position of the center of the arc. Image processing method.