Pattern model positioning method in image processing, image processing apparatus, image processing program, and computer readable recording medium

[0001] The present application claims foreign priority based on Japanese Patent Applications No. 2008-206478, filed Aug. 9, 2008, and No. 2008-267979, filed Oct. 16, 2008, the contents of which is incorporated herein by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates to a pattern model positioning method in image processing, an image processing apparatus, an image processing program, and a computer readable recording medium, for performing fine positioning with higher accuracy upon searching out of an image to be searched and positioning a pattern model corresponding to a pre-registered image.

[0004] 2. Description of the Related Art

[0005] An image processing apparatus for processing an image picked up by an image pickup element typically includes: an image pickup apparatus for picking up an image processing object (hereinafter also referred to as “work”); an image data storing device for storing data on the image picked up by the image pickup apparatus; and an image data processing device for processing the image data stored by the image data storing device. For example, in the image processing apparatus where the image pickup apparatus is made up of a CCD camera, luminance data (so-called multi-valued data) such as 256 levels of gray or 1024 levels of gray is obtained based on each of charge amounts of a large number of charge coupled elements constituting an image pickup surface, whereby a position, a rotational angle and the like of the work as an object to be searched can be found. Conventionally, as techniques for performing processing on image data to search an object to be searched in image processing, there are known a difference search performed using a total value of absolute values of pixel difference values between images, a normalized correlation search performed using normalized correlation values between images, and the like. In these searches, an object to be searched that is wished to be searched is previously registered as a template image, and based on the image, a search is executed for the object to be searched out of an image to be searched. In these search processing, a region-based search by use of image data has conventionally been mainstream. However, such a conventional region-based search based on image thickness or the like has the problem of being susceptible to a change in illumination upon image pickup, and the like.

[0006] Meanwhile, there has also been provided a method for performing edge extraction processing on a registered image and an image to be searched, to perform a search based on edge information. In this method, a concentration value of pixels constituting image data is not used, but edge data based on an amount of change in concentration value is used, and hence it is possible to obtain the advantage of being not susceptible to fluctuations in illumination upon image pickup. Especially, in recent years, an edge-based pattern search with an edge regarded as a characteristic amount is drawing attention for its high robustness, and is in practical use in industrial applications and the like.

[0007] As a technique for improving a processing speed of a pattern search, a “coarse to fine” approach is known. Namely, first, a search is coarsely performed using a low-resolution image (coarse image), and after a rough position is specified, detailed positioning is performed using a high-resolution image (fine image), thereby to enhance accuracy of a position and posture. In the case of performing the edge-based search by means of coarse-to-fine type template matching, a pyramid search is used where a search is performed using coarse data obtained by compressing (also referred to as “thinning out” or the like) original data, to specify a rough position, and thereafter, a search is performed using detailed data. FIG. 87 shows a concept of the pyramid search. As shown in this drawing, a rough search (referred to as “coarse search” or the like) is performed using a low-resolution image having a high reduction ratio, to find a rough position. Thereafter, a search is performed in the vicinity thereof with an increased resolution and an intermediate reduction ratio, and finally, a fine search is performed on an image of an original size or an image having a reduction ratio close to the original size. As thus described, in the typical pyramid search, a plurality of images having changed resolutions are prepared, and a schematic position is first detected by use of an image having the lowest resolution. In subsequent processing, a search range is narrowed down to the vicinity of the previous detected position as the resolution is gradually increased. Thereby, the accuracy of the detected position enhances with each succeeding processing level, finally leading to detection of a highly accurate position with the resolution being that of the original image or closer thereto. As a technique concerning fine positioning for finding a position and posture with high accuracy by means of such coarse-to-fine type template matching, an image processing apparatus of Japanese Patent No. 3759983 is known.

[0008] This image processing apparatus includes: an image pickup apparatus for picking up an image processing object; an image data storing device for storing data on the image picked up by the image pickup apparatus; a search template data storing apparatus for storing data on a search template having a plurality of point pairs which are each made up of two points sandwiching an edge of the image processing object and also located at a fixed distance from each other that is larger than an array pitch of the image pickup devices of the image pickup apparatus, and are previously set correspondingly to a plurality of positions on the edge; and a determination device for determining the image processing object as an object to be searched that matches with the search template of the search template data storing device when the point pairs are taken as being in a matching state where one point of the pair is located inside the edge of the image processing object and the other is located within the background and the point pairs in an amount not smaller than a set amount out of the plurality of point pairs are in the matching state in a case where the search template is superimposed on a screen with image data of the image data storing device present therein and a difference state of an optical characteristic value of each point constituting the plurality of point pairs is larger than a set state. According to this apparatus, it is possible to see the presence or absence of the object to be searched and whether or not the image processing object is the object to be searched by use of the image data and the search template. Those can be determined by calculating and comparing optical characteristic values of two points constituting each of all point pairs, so that an image processing apparatus capable of readily and speedily performing processing can be obtained.

[0009] In this fine positioning, as described above, one-dimensional edge processing is performed on a seek-line to find an edge position, and a difference between an ideal point and the corresponding point is found. Using the difference and geometric information peculiar to a model (information such as a model being in rectangular shape, etc.) a displacement and a rotational angle are found. FIG. 88 shows the relation between a pattern detected upon registration and a seek-line SLN, and on the other hand, FIG. 89 shows a state immediately before fine positioning after a coarse search during motion. FIG. 90 shows an enlarged view of the lower left portion of FIG. 89. As a kernel of the edge, (−1, −1, −1 −1, 1, 1, 1, 1) shown in Table 1 below is employed. In edge detection, an edge is found by applying this kernel to a pixel value obtained by interpolation on the seek-line SLN.

[0010]

	TABLE 1
	−	−	−	−	+	+	+	+

[0011] However, high accuracy cannot be expected in this technique because whether or not the corresponding point is present on the seek-line is determined based only upon the relation between a size of a differential value and its threshold and an edge direction and an angle component are not considered. Further, there has been a drawback with this technique in that processing cannot be performed in a case where a plurality of points as candidates of the corresponding point are present on the seek-line, e.g., a double line cannot be processed. Moreover, in this method, although positioning of a simple shape such as a rectangle and a circle can be realized, positioning of a general and multipurpose shape such as a more complicated shape and a character pattern cannot be performed. Furthermore, there has been a problem in that accurate edge detection cannot be performed on a thin-linear object to be searched due to the long kernel of the edge detection. Namely, a difference is computed along the line by the one-dimensional kernel in the longitudinal direction, to consider an edge. Especially, the kernel needs to be made longer in order to enhance noise resistance. There has consequently been a drawback in that, when a work itself is long and narrow, edge data becomes relatively weak, to be regarded as a noise component, and hence accurate edge detection cannot be expected.

[0012] Meanwhile, a fine positioning method by a least squares method using image points and segments is disclosed in I. J. Cox, J. B. Kruskal, and D. A. Wallach, “Predicting and Estimation the performance of a subpixel registration algorithm,” IEEE Trans. Pattern Anal. Machine Intell., vol. 12, no. 6, pp. 721-734, (August 1990). In this method, a pattern model is configured of segments. Further, error detection processing is performed on an image to be searched not yet inputted, to create an edge image including imaginary points. The pattern model is superimposed on a position in the edge image which was decided by a coarse search, and a least squares method is performed using as an error value a distance between a point and a straight line, which are every image point in the image to be searched and a segment inside the pattern model that is close to the image point, to decide a fine position. In an example of FIG. 91 shown is the relation between a pattern model configured of two segments and image points (input image points) in an image to be searched.

[0013] However, there has been a problem with this technique in that, since the corresponding relation between the segment and the point depends only upon the distance therebetween, a point may be computed as the corresponding point even in an inherently non-corresponding relation with the segment in view of the edge direction or the like. Further, there has also been a problem in that, from necessity of acquiring imaginary points in the image to be searched, the edge detection needs to be performed on every point in a high resolution image as an object to be searched, and hence round-robin processing is performed, leading to an increase in processing time with increase in resolution of the image data.

[0014] The present invention was made in order to solve the conventional problems as thus described. A principal object of the present invention is to provide a pattern model positioning method in image processing, an image processing apparatus, an image processing program, and a computer readable recording medium, which can perform fine positioning with higher accuracy at higher speed.

[0015] In order to achieve the above object, a first pattern model positioning method in image processing of, upon searching out of an image to be searched and positioning an object to be searched that is similar to a pre-registered image by use of a pattern model corresponding to the registered image, positioning with accuracy higher than at an initially given position, the method is capable of including the steps of extracting a contour from the registered image; constructing a pattern model of the registered image, in which a plurality of reference points are set on the extracted contour, and also a corresponding point search line having a predetermined length and passing through each reference point as well as being substantially orthogonal to the contour is also allocated to each reference point; acquiring an image to be searched, and also arranging the pattern model so as to be superimposed on the image to be searched in accordance with an initial position included in the image to be searched and corresponding to the registered image; finding a corresponding edge point on the image to be searched corresponding to a reference point of each corresponding point search line of the pattern model out of each pixel in the image to be searched that is positioned as superimposed on the corresponding point search line upon superimposing the pattern model on the initial position on the image to be searched; and taking a distance between each corresponding edge point and a contour including the reference point corresponding to the corresponding edge point as an evaluation value, and performing fine positioning with accuracy higher than accuracy in the given initial position such that an absolute value of an accumulated value of the evaluation values becomes minimal. Thereby, it is possible to use data on the corresponding point search line as the pattern model for fine positioning. Particularly, by using not only the edge strength of the image along but also the edge angle thereof, it is possible to add a direction component, so as to perform highly accurate positioning resistant to a noise component. Further, by changing the length of the corresponding point search line, it is possible to obtain an advantage of being capable of readily changing a corresponding-edge-point search range, so as to adjust the positioning accuracy.

[0016] According to a second pattern model positioning method in image processing, the step of extracting the contour from the registered image can include the steps of extracting a plurality of edge points from the registered image; coupling adjacent edge points among the extracted plurality of edge points, to create a continuous chain; and creating a segment by respectively approximating one or more chains by means of a line and/or a circular arc, and regarding aggregation of the segments as a contour. Thereby, it is possible to construct a pattern model made up of segments approximated by a line and/or a circular arc, so as to realize positioning with higher accuracy.

[0017] According to a third pattern model positioning method in image processing, the step of performing the fine positioning can be made to compute an error value or a weight value in a least squares method by use of the distance between each segment constituting the contour and a corresponding edge point thereof, to find the accumulated value of the evaluation values. Thereby, by solving simultaneous equations obtained by calculation of a least squares method with regard to the corresponding edge point of each reference point, it is possible to find a position and a posture of the pattern model.

[0018] According to a fourth pattern model positioning method in image processing, the least squares method in the fine positioning step is to apply an error function, obtained by calculating a distance between the corresponding edge point and a circular arc, to a circular arc segment and an error function, obtained by calculating a distance between the corresponding edge point and a straight line, to a line segment. Thereby, it is possible to realize fine positioning by the effective least squares method without hindering a rotational movement of the circular arc segment.

[0019] According to a fifth pattern model positioning method in image processing, the step of creating the segment with respect to the chains repeats an operation of first attempting appreciation of the chains by the line and then switching to appreciation by the circular arc when an error of the approximation by the line exceeds a pre-set approximation threshold, to create a sequence of segments.

[0020] According to a sixth pattern model positioning method in image processing, the segment can be configured of at least any of a cone curve, a spline curve and a Bezier curve, or in combination of these.

[0021] According to a seventh pattern model positioning method in image processing, a pre-set margin can be set at the edge of the segment upon setting the reference point on the contour, and the reference point is set in a region excluding the margin portion. Thereby, since a setting can be made so as not to provide the corresponding point search line at the end portion and corner portion, it is possible to eliminate a portion that becomes unstable due to a large change in edge angle, so as to obtain a result of stable pattern matching.

[0022] According to an eighth pattern model positioning method in image processing, the initial position corresponding to the registered image included in the image to be searched in the step of arranging the pattern model so as to be superimposed on the image to be searched can be acquired by reducing the image to be searched and performing a pattern search on the image to be searched after the reduction. Thereby, it is possible to perform a simple coarse search at high speed on the reduced image to be searched.

[0023] According to a ninth pattern model positioning method in image processing, the corresponding point search line can be formed by being set to have a predetermined length in a direction substantially orthogonal to the segment with the reference point that is set on the segment taken as the center. Thereby, it is possible to set the corresponding point search line to be a line substantially orthogonal to the segment with the reference point set at the center.

[0024] According to a tenth pattern model positioning method in image processing, the predetermined length of the corresponding point search line can be decided in accordance with a ratio between a reduction ratio of the image to be searched as an object of a coarse search that is a search performed with predetermined accuracy on the whole area of the image to be searched and a reduction ratio of the image to be searched to be subjected to the fine positioning. Thereby, by at least searching a range corresponding to the ratio of reduction ratios of the image to be searched, it is possible to hold the positioning accuracy. For example, it is possible to make the corresponding point search line at least have a length based on the number of pixels corresponding to the reduction ratio for reducing the image to be searched.

[0025] According to an eleventh pattern model positioning method in image processing, the pattern model is capable of including array data on the corresponding point search line, and includes as the array data at least any of a coordinate of the reference point, an angle of the corresponding point search line and a length of the corresponding point search line.

[0026] According to a twelfth pattern model positioning method in image processing, in the case of a plurality of corresponding-edge-point candidates being present on the corresponding point search line, the step of finding the corresponding edge point on the image to be searched can regard, as the corresponding edge point, a point having: an edge strength that is larger than an edge strength threshold and shows the maximum, and an edge angle that is sufficiently close to an ideal edge angle and is also the closet to the reference point.

[0027] According to a thirteenth pattern model positioning method in image processing, the step of extracting the segment from the chains repeats an operation of attempting appreciation by the line and then switching to appreciation by the circular arc when an error of the approximation by the line exceeds a pre-set approximation threshold, to extract a sequence of segments. Thereby, it is possible to perform highly accurate fitting by approximation in combination of the line and the circular arc.

[0028] According to a fourteenth pattern model positioning method in image processing, the method is constructed to make at least any one of a movement in an X-direction, a movement in a Y-direction, a rotation, and enlargement/reduction settable as a degree of freedom of the least squares method. Thereby, it is possible to deal with the rotation, enlargement, reduction and the like of the registered image as well as the parallel movements in the xy directions.

[0029] According to a fifteenth pattern model positioning method in image processing, the method is constructed to further make an aspect settable as the degree of freedom of the least squares method. Thereby, it is possible to deal with transfiguration of the registered image and the like as well as the parallel movements in the xy directions.

[0030] According to a sixteenth pattern model positioning method in image processing, the fine positioning step can be repeatedly performed while shortening the corresponding point search line. Thereby, the fine positioning is repeatedly performed, and it is thus possible to realize positioning with higher accuracy.

[0031] According to a seventeenth pattern model positioning method in image processing, in the step of performing fine positioning, the least squares method is repeatedly applied to the corresponding point search line, and also the length of the corresponding point search line is gradually shortened in accordance with the number of repeated times of the least squares method. Thereby, the least squares method is repeatedly applied, and it is thus possible to readily realize positioning with higher accuracy.

[0032] According to an eighteenth pattern model positioning method in image processing, in the step of performing fine positioning, the length of the corresponding point search line can be decided based on a reduction ratio in the coarse search which is a search performed with predetermined accuracy on the whole area of the image to be searched and a reduction ratio upon the fine positioning.

[0033] According to a nineteenth pattern model positioning method in image processing, in the step of performing fine positioning, the least squares method is repeatedly applied to the corresponding point search line, and an edge angle threshold is gradually decreased in accordance with the number of repeated times of the least squares method. Thereby, the least squares method is repeatedly applied, and it is thus possible to readily realize positioning with higher accuracy.

[0034] According to a twentieth pattern model positioning method in image processing, in the step of performing fine positioning, upon repeatedly applying the least squares method on the corresponding point search line, the least squares method is discontinued at the time point when the error value exceeds a pre-set error value threshold, and that result is regarded as a final result. Thereby, the least squares method is repeatedly applied, and it is thus possible to readily realize position with higher accuracy.

[0035] According to a twenty first pattern model positioning method in image processing, in the step of performing the fine positioning, the method can be constructed to apply the least squares method to the corresponding point search line, discontinue the least squares method at the time point when the error value exceeds the pre-set error value threshold, apply as a final result an approximation performed by use of the error value of the least squares method completed in the pre-step, and also output the error value of the final result. Thereby, it is possible to use the error value, calculated by the least squares method, as an indicator indicating whether the fitting condition is good or bad.

[0036] According to a twenty second pattern model positioning method in image processing, in the step of constructing the pattern model, the method can be constructed to make the presence or absence of a polarity of an edge direction settable. Thereby, it is possible to change the processing method for the edge angle in accordance with the presence or absence of the polarity of the edge direction. Further, it is possible to apply the same setting to every segment.

[0037] According to a twenty third pattern model positioning method in image processing, in the step of constructing the pattern model, the angle and the corresponding point search line of each reference point can change in accordance with an affine transformation value.

[0038] According to a twenty fourth pattern model positioning method in image processing, upon extracting the edge point from the registered image, Sobel processing can be performed, to compute the edge angle and the edge strength of each edge point.

[0039] According to a twenty fifth pattern model positioning method in image processing, in creation of the corresponding point search line upon searching the corresponding point, computing can be performed using Bresenham's algorithm for creating straight-line data.

[0040] According to a twenty sixth pattern model positioning method in image processing, in the step of constructing the pattern model, a predetermined interval at which the reference points are set on the segments can be a fixed width. Thereby, it is possible to readily set the corresponding point search line.

[0041] According to a twenty seventh pattern model positioning method in image processing, in the step of constructing the pattern model, filtering for selecting the segment on which the reference point is set can be performed. Thereby, it is possible to set only the reference point with respect to the selected segment for setting the corresponding point search line, so as to enhance the accuracy of the pattern search.

[0042] According to a twenty eighth pattern model positioning method in image processing, criteria for selecting the segment upon the filtering can be set based on a result of computing an average edge strength of the edge points included in each segment and comparing the obtained average edge strength with a pre-set average edge strength threshold for filtering. Thereby, it is possible to select a segment having a large average edge strength, so as to expect a pattern search based on an edge with high accuracy and thus enhance the search accuracy.

[0043] According to a twenty ninth pattern model positioning method in image processing, criteria for selecting the segment upon the filtering can be set based on a result of comparing the length of each segment with a pre-set edge strength threshold for filtering. Thereby, it is possible to select only long segments for setting the reference points, so as to enhance the accuracy of the pattern search.

[0044] According to a thirtieth pattern model positioning method in image processing, in the step of constructing the pattern model, the pattern model can be created based on a fixed geometric shape. Thereby, it is possible to create a pattern model, with fixed geometric graphics such as circular, oval, triangle and rectangular shapes regarded as references, singly or in combination of these graphics, so as to simplify creation of the pattern search and each of subsequently processing.

[0045] According to a thirty first pattern model positioning method in image processing, the edge image created from the registered image can be subjected to thinning processing as non-maximal point suppressing processing in advance of edge coupling processing.

[0046] According to a thirty second pattern model positioning method in image processing, at least any of the edge angle obtained from the image to be searched, the edge strength threshold, a position, data expressing the edge angle in units of vectors, and an edge vector is used as data for finding the corresponding edge point.

[0047] According to a thirty third pattern model positioning method in image processing, a threshold of every edge angle difference in the repeated least squares method upon selecting the corresponding edge point is decided based on an angle resolution obtained in the last coarse search.

[0048] According to a thirty fourth pattern model positioning method in image processing, the length of the corresponding point search line can be changed with respect to each reference point. Thereby, the length of the corresponding point search line is not made fixed but set biased with respect to the reference point, and it is thus possible to expect enhancement of the accuracy.

[0049] According to a thirty fifth pattern model positioning method in image processing, Bresenham's algorithm for creating straight-line data can be used in scanning of the corresponding point search line. Thereby, using Bresenham's algorithm as an algorithm for drawing a straight-line continuously free of overlapping, it is possible to readily and accurately set the corresponding point search line.

[0050] According to a thirty sixth pattern model positioning method in image processing, the coordinate of the reference point can be represented by a sub-pixel coordinate.

[0051] According to a thirty seventh pattern model positioning method in image processing, the step of fining the coordinate of the corresponding edge point can include the steps of: finding the corresponding edge point on the corresponding point search line; selecting a pair point corresponding to the corresponding edge point such that the corresponding edge point and the pair point are substantially orthogonal to and sandwich the corresponding point search line; and finding respective sub-pixel coordinates of the corresponding edge point and the pair point, to find an average coordinate of the sub-pixel coordinates and take the obtained average coordinate as a real corresponding edge point coordinate. Thereby, computing of the corresponding edge point in corrugated shape is suppressed, and it is thus possible to obtain a stable computing result.

[0052] According to a thirty eighth pattern model positioning method in image processing, the step of fining the coordinate of the corresponding edge point can include the steps of: searching a tentative corresponding edge point on the corresponding point search line; and finding a plurality of neighborhood edge points present around the tentative corresponding edge point, to find sub-pixel coordinates of the tentative corresponding edge point and the plurality of neighborhood edge points.

[0053] According to a thirty ninth pattern model positioning method in image processing, in the step of performing the fine positioning, the least squares method is applied to the corresponding point search line, and a score is calculated as the evaluation value by a ratio between the number of corresponding points and the number of reference points in the final least squares method processing.

[0054] According to a fortieth pattern model positioning method in image processing, the score is found by the following expression:

[0055] $\begin{array}{cc}S=\frac{\sum _{i=1}^{n}1}{\sum _{i=1}^{m}1}=\frac{n}{m}& \left[\mathrm{Expression}3\right]\end{array}$

• [0056] S: score
• [0057] n: the number of corresponding points
• [0058] m: the number of reference points

[0059] According to a forty first pattern model positioning method in image processing, in the step of performing the fine positioning, the least squares method is applied to the corresponding point search line, and a score is calculated as the evaluation value by a ratio of a total of weights each obtained from a difference between the edge angle of the corresponding edge point in the final least squares method processing and the edge angle of the reference point corresponding thereto, and the number of reference points.

[0060] According to a forty second pattern model positioning method in image processing, the score is found by the following expression:

[0061] $\begin{array}{cc}S=\frac{\sum _{i=1}^n\omega \left({\theta }_i-{\theta }_i^p\right)}{\sum _{i=1}^{m}1}& \left[\mathrm{Expression}4\right]\end{array}$

• [0062] S: score
• [0063] n: the number of corresponding points
• [0064] m: the number of reference points
• [0065] ω(x): function that is 1 when x=0, and monotonously decreases with increase in x
• [0066] θi: edge angle of corresponding point
• [0067] θip: angle of reference point corresponding to corresponding point

[0068] A forty third image processing apparatus for positioning with accuracy higher than at an initially given position upon searching out of an image to be searched and positioning an object that is similar to a pre-registered image by use of a pattern model corresponding to the registered image, the apparatus is capable of including: an image input device for acquiring a registered image and an image to be searched; a contour extracting device for extracting a contour from the registered image acquired by the image input device; a chain creating device for extracting a plurality of edge points from the contour extracted by the contour extracting device, and coupling adjacent edge points among the extracted plurality of edge points, to create a continuous chain; a segment creating device for creating a segment by respectively approximating one or more chains by means of a line and/or a circular arc; a pattern model constructing device for setting a plurality of reference points on the segment created by the segment creating device, and also constructing a pattern model of the registered image to which corresponding point search lines with a fixed length are allocated that pass through the respective reference points and are substantially orthogonal to the contours; and a fine positioning device for acquiring an initial position corresponding to the registered image included in the image to be searched acquired by the image input device, arranging the pattern model so as to be superimposed on the image to be searched, to find each of individual corresponding edge points on the image to be searched that corresponds to each segment constituting the pattern model, regarding a relation between each segment and the corresponding edge point as an evaluation value, and performing with accuracy higher than at an initially given position such that an accumulated value of the evaluation values becomes minimal or maximal. Thereby, it is possible to use data on the corresponding point search line as the pattern model for fine positioning. Particularly, by using not only the edge strength of the image along but also the edge angle thereof, it is possible to add a direction component, so as to perform highly accurate positioning resistant to a noise component. Further, by changing the length of the corresponding point search line, it is possible to obtain an advantage of being capable of readily changing a corresponding-edge-point search range.

[0069] A forty fourth image processing apparatus can further include: an image reducing device for reducing the image to be searched, acquired by the image input device, with a predetermined reduction ratio; an edge angle image creating device for computing an edge angle image including edge angle information with respect to each pixel constituting the image on the reduction-ratio image to be searched reduced by the image reducing device; an edge angle bit image creating device for transforming each pixel of the edge angle image, created by the edge angle image creating device, into an edge angle bit image expressed by an edge angle bit indicating an angle with a pre-defined fixed width; an edge angle bit image reducing device for performing, in order to create an edge angle bit reduced image reduced from the edge angle bit image, an OR operation on an edge angle bit of every pixel included in an OR operation region decided in accordance with a reduction ratio for reducing the edge angle bit image, to create an edge angle bit reduced image made up of reduced edge angle bit data representing each OR operation region; and a coarse search device for performing a pattern search on a first edge angle bit reduced image created by the edge angle bit image reducing device by using as a template a pattern model for first coarse search created with a first reduction ratio with regard to a first-reduction-ratio image to be searched reduced by the image reducing device with the first reduction ratio, to find with first accuracy a first position and posture corresponding to the pattern model for first coarse search from the whole area of the first edge angle bit reduced image, and also performing a pattern search on a second edge angle bit reduced image created by the edge angle bit image reducing device by using as a template a pattern model for second coarse search created with a second reduction ratio that is not larger than the first reduction ratio and not smaller than unmagnification with regard to a second-reduction-ratio image to be searched reduced by the image reducing device into the second reduction ratio, to find with second accuracy that is higher than the first accuracy a second position and posture corresponding to the pattern model for second coarse search from a predetermined region of the second edge angle bit reduced image where the first position and posture are set as references, wherein the fine positioning device arranges a pattern model so as to be superimposed on a third-reduction-ratio image to be searched, obtained by reducing as appropriate the image to be searched into a third reduction ratio that is not smaller than unmagnification and not larger than the second reduction ratio by use of the second position and posture of the third-reduction-ratio image to be searched, to find a corresponding edge point on the third-reduction-ratio image to be searched corresponding to a contour constituting the pattern model, regards a relation between each contour and its corresponding edge point as an evaluation value, and perform fine positioning with third accuracy that is higher than the second accuracy such that an accumulated value of the evaluation values becomes minimal or maximal. Thereby, it is possible to hold the edge angle information even in the case of the image data being further reduced, so as to perform highly accurate search with data size reduced without lowering the search accuracy.

[0070] A forty fifth image processing apparatus can further include a segment filtering function for selecting a segment on which a reference point is set upon constructing the pattern model. Thereby, it is possible to set the reference point with respect only to the selected segment, so as to enhance the accuracy of the pattern search.

[0071] A forty sixth image processing program to position with accuracy higher than at an initially given position upon searching out of an image to be searched and positioning an object that is similar to a pre-registered image by use of a pattern model corresponding to the registered image, the program is capable of causing a computer to realize: an image input function for acquiring a registered image and an image to be searched; a contour extracting function for extracting a contour from the registered image acquired by the image input function; a chain creating function for extracting a plurality of edge points from the contour extracted by the contour extracting function, and coupling adjacent edge points among the extracted plurality of edge points, to create a continuous chain; a segment creating function for creating a segment by respectively approximating one or more chains by means of a line and/or a circular arc; a pattern model constructing function for setting a plurality of reference points on the segment created by the segment creating function, and also constructing a pattern model of the registered image to which corresponding point search lines with a fixed length are allocated that pass through the respective reference points and are substantially orthogonal to the contours; and a fine positioning function for acquiring an initial position corresponding to the registered image included in the image to be searched acquired by the image input function, arranging the pattern model so as to be superimposed on the image to be searched, to find each of individual corresponding edge points on the image to be searched that corresponds to each segment constituting the pattern model, regarding a relation between each segment and the corresponding edge point as an evaluation value, and performing with accuracy higher than at an initially given position such that an accumulated value of the evaluation values becomes minimal or maximal. Thereby, it is possible to use data on the corresponding point search line as the pattern model for fine positioning. Particularly, by using not only the edge strength of the image along but also the edge angle thereof, it is possible to add a direction component, so as to perform highly accurate positioning resistant to a noise component. Further, by changing the length of the corresponding point search line, it is possible to obtain an advantage of being capable of readily changing a corresponding-edge-point search range.

[0072] According to a forty seventh image processing program, the program is capable of causing a computer to further realize: an image reducing function for reducing the image to be searched, acquired by the image input function, with a predetermined reduction ratio; an edge angle image creating function for computing an edge angle image including edge angle information with respect to each pixel constituting the image on the reduction-ratio image to be searched reduced by the image reducing function; an edge angle bit image creating function for transforming each pixel of the edge angle image, created by the edge angle image creating function, into an edge angle bit image expressed by an edge angle bit indicating an angle with a pre-defined fixed width; an edge angle bit image reducing function for performing, in order to create an edge angle bit reduced image reduced from the edge angle bit image, an OR operation on an edge angle bit of every pixel included in an OR operation region decided in accordance with a reduction ratio for reducing the edge angle bit image, to create an edge angle bit reduced image made up of reduced edge angle bit data representing each OR operation region; and a coarse search function for performing a pattern search on a first edge angle bit reduced image created by the edge angle bit image reducing function by using as a template a pattern model for first coarse search created with a first reduction ratio with regard to a first-reduction-ratio image to be searched reduced by the image reducing function with the first reduction ratio, to find with first accuracy a first position and posture corresponding to the pattern model for first coarse search from the whole area of the first edge angle bit reduced image, and also performing a pattern search on a second edge angle bit reduced image created by the edge angle bit image reducing function by using as a template a pattern model for second coarse search created with a second reduction ratio that is not larger than the first reduction ratio and not smaller than unmagnification with regard to a second-reduction-ratio image to be searched reduced by the image reducing function into the second reduction ratio, to find with second accuracy that is higher than the first accuracy a second position and posture corresponding to the pattern model for second coarse search from a predetermined region of the second edge angle bit reduced image where the first position and posture are set as references, wherein the fine positioning function arranges a pattern model so as to be superimposed on a third-reduction-ratio image to be searched, obtained by reducing as appropriate the image to be searched into a third reduction ratio that is not smaller than unmagnification and not larger than the second reduction ratio by use of the second position and posture of the third-reduction-ratio image to be searched, to find a corresponding edge point on the third-reduction-ratio image to be searched corresponding to a contour constituting the pattern model, regards a relation between each contour and its corresponding edge point as an evaluation value, and perform fine positioning with third accuracy that is higher than the second accuracy such that an accumulated value of the evaluation values becomes minimal or maximal. Thereby, it is possible to hold the edge angle information even in the case of the image data being further reduced, so as to perform highly accurate search with data size reduced without lowering the search accuracy.

[0073] Further, a forty eighth computer readable recording medium stores the above program. The recording medium includes magnetic disks, optical disks, magneto-optical disks, semiconductor memories, and some other medium capable of storing a program, such as a CD-ROM, a CD-R, a CD-RW, a flexible disk, a magnetic tape, an MO, a DVD-ROM, a DVD-RAM, a DVD-R, a DVD+R, a DVD-RW, a DVD+RW, Blue-ray, an HD, and a DVD (AOD). Moreover, the program includes one in the form distributed by downloading through a network line such as the Internet, other than one delivered as stored in the above recording medium. Furthermore, the recording medium includes equipment capable of recording a program, for example, general purpose equipment or dedicated equipment which is mounted in a state where the above program is executable in the form of software or firmware. Further, each processing and function included in the program may be executed by program software executable by a computer, or processing in each section may be realized by hardware such as a predetermined gate array (FPGA, ASIC) or in a mixed form of program software and a partial hardware module that realizes part of elements of hardware.

[0165] In the following, an embodiment of the present invention is described based on drawings. However, the embodiments shown below exemplifies a pattern model positioning method in image processing, an image processing apparatus, an image processing program, and a computer readable recording medium for making a technical concept of the present invention concrete, and the present invention does not specify its pattern model positioning method in image processing, image processing apparatus, image processing program, and computer readable recording medium to the following. Further, the present specification by no means specifies a member shown in the claims to a member in the embodiment. Especially a size, a material, a shape, a relative arrangement and the like of a constitutional component described in the embodiment are not intended on restricting the range of the present invention to those but simply are explanatory examples so long as a specific description is not particularly given. It is to be noted that there are cases where a size, a positional relation or the like of a member shown by each drawing may be emphasized for the sake of clarifying description. Moreover, in the following description, the same name or symbol indicates the same member or a homogeneous member, and a detailed description is not repeatedly provided as appropriate. Furthermore, as for each element constituting the present invention, a plurality of elements may be made up of the same member and may thus take the aspect of sharing one member, or on the contrary, a function of one member can be realized by being shared by a plurality of members.

[0166] The connection of an image processing apparatus for use in an example of the present invention with a computer, a printer, an external storage apparatus, and other peripheral equipment, which are connected to the image processing apparatus and used for operation, control, display, and other processing, are made electrically, magnetically or optically for communication by serial connection such as IEEE1394, RS-232x, RS-422 or USB, parallel connection, or connection through a network such as 10BASE-T, 100BASE-TX or 1000BASE-T. The connection is not restricted to physical connection using a cable, but may be wireless connection through the use of electric waves such as wireless LAN like IEEE802.1x or Bluetooth (registered trademark), infrared rays, optical communications, or the like, or some other connection. Further, for the recording medium for data exchange, setting storage, and the like, a memory card, a magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory or the like can be used. It should be noted that in the present specification, the image processing apparatus is used not only in the meaning of an apparatus body for performing edge extraction, pattern matching and the like, but also in the meaning including a contour extraction system formed in combination of this apparatus body with peripheral equipment such as a computer and an external storage apparatus.

[0167] Further, in the present specification, the pattern model positioning method in image processing, the image processing apparatus, the image processing program, and the computer readable recording medium are not restricted to a system itself that performs edge extraction, measurement region setting, and edge point coupling, and an apparatus and a method that operate and perform in a hardware manner processing of input/output, display, computing, communication, and other processing which are related to pickup and acquirement of a variety of images. An apparatus and a method for realizing processing in a software manner are also included in the range of the present invention. For example, an apparatus and a system, where software, a program, a plug-in, an object, a library, an applet, a compiler, a module, a macro that operates on a specific program, or the like is integrated into a general purpose circuit or computer, to allow performance of edge extraction and edge point coupling themselves or processing related thereto, also correspond to any of the pattern model positioning method in image processing, the image processing apparatus, the image processing program, and the computer readable recording medium according to the present invention. Further, in the present specification, the computer includes, other than a general purpose or dedicated electronic calculator, a workstation, a terminal, a mobile type electronic apparatus, PDC, CDMA, W-CDMA, FOMA (registered trademark), GSM, IMT2000, a mobile phone such as a forth-generation mobile phone, a PHS, a PDA, a pager, a smart phone, and other electronic apparatuses. Moreover, in the present specification, the program is not restricted to one singly used, but can also be used in the mode of functioning as part of a specific computer program, software, service or the like, in the mode of functioning as called when necessary, in the mode of being provided as a service in an environment of an operating system (OS) or the like, in the mode of operating as being resident in the environment, in the mode of operating in a background, or in a position as another supporting program.

(Brief Flow of Image Processing)

[0168] FIG. 1 shows a block diagram of an image processing apparatus 100. As shown in FIGS. 2A to 2H, this image processing apparatus 100 previously registers an image wished to be searched and creates a pattern model from this registered image, and upon actual operation, the apparatus finds a position corresponding to the pattern model out of an image to be searched that is inputted. A scheme of an operation upon creating the pattern model is shown in a flowchart of FIG. 3. In the present embodiment, as shown in FIG. 2A, a user sets a region where a pattern model is created with respect to a registered image RI wished to be searched, namely a pattern window PW, is set by a user (Step S301 in FIG. 3). An image including a region where this pattern window PW is set is reduced as appropriate, as shown in FIG. 2B (Step S302 in the same drawing). Further, as shown in FIG. 2C, from a reduced pattern window RPM, a pattern model PM as a search pattern corresponding to the registered image RI is created (Step S303 in the same drawing). As thus described, in advance of the actual search operation, the image processing apparatus previously creates the pattern model PM corresponding to the registered image RI wished to be searched out of the image to be searched.

[0169] Further, as shown in FIG. 2D, the pattern model PM is reduced into a reduction ratio for first edge angle bit image and a reduction ratio for second edge angle bit image (described later), and used during motion (Step S304 in the same drawing). Such creation of the reduced pattern model RPM can be previously performed upon registration or can also be performed upon each operation.

[0170] Meanwhile, a scheme of an operation during motion is shown in a flowchart of FIG. 4. during motion, after an image OI to be searched is inputted in Step S401 (FIG. 2E), this image OI to be searched is reduced into a reduced image ROI to be searched as appropriate in Step S402 (FIG. 2F). Next, in Step S403, an edge angle bit image EB is created from the reduced image ROI to be searched (FIG. 2G: detailed later). Further, in Step S404, an edge angle bit reduced image REB reduced from the edge angle bit image EB is created (FIG. 2H). In Step S405, a pattern search is executed on the edge angle bit reduced image REB obtained as thus described by use of the pattern model obtained upon registration.

(Image Processing Apparatus 100)

[0171] Next, a configuration of the image processing apparatus 100 is described. The image processing apparatus 100 shown in the block diagram of FIG. 1 includes an image input device 1 for inputting an image, a display device 3 for displaying an image and a variety of data, an operation device 2 for the user to perform a variety of operations, and an output device 5 constituting an output interface for outputting a result of image processing in an image processing apparatus body 100A to the outside. The image input device 1 is made up of an image pickup device such as a CCD. An input image inputted from the image input device 1 is captured into the image processing apparatus body 100A through an A/D conversion device. Further, the display device 3 displays an original image of the input image or an edge image obtained by performing image processing on the original image by, for example, edge image processing.

(Image Processing Apparatus Body 100A)

[0172] The image processing apparatus body 100A includes a storage device 4 for storing a variety of data, and a computing device 6 for performing a variety of computing concerning image processing. Other than a registered image inputted from the image input device 1 through the A/D conversion device, the storage device 4 includes a pattern model created with this registered image regarded as a template image, an image to be searched, a work region for use in hold and storage of temporary data created upon creating the pattern model from the registered image or upon searching, and the like.

(Computing Device 6)

[0173] The computing device 6 includes a contour extracting device 62 for performing edge detection on an image to extract a contour, a chain creating device 63 for creating a chain from contour information, a segment creating device 68 for creating a segment from the chains, and other variety of devices. Examples of other devices include an edge angle bit image creating device 69, an edge angle bit image reducing device 78, an image reducing device 77 for reducing an image into a predetermined magnification, a pattern model constituting device 70 constituting a pattern model, a coarse searching device 71 performing coarse search, and a fine positioning device 76 for performing highly accurate positioning inside an image to be searched by means of a pattern model of a registered image based on edge information (detailed later). This computing device 6 registers a pattern model and performs a search in an image to be searched by use of the registered pattern model as described above. In order to perform such operations, the chain creating device 63, the segment creating device 68 and the pattern model constituting device 70 are used upon registration of the pattern model. Further, the coarse searching device 71 and the fine positioning device 76 are used upon actual operation. Moreover, the image reducing device 77, the contour extracting device 62, the chain creating device 63, and the like are used for both the operation upon registration and the operation during motion, and the edge angle bit image creating device 69 and the edge angle bit image reducing device 78 are used during motion. It is to be noted that in the present embodiment, although the chain creating device 63 is used only upon registration, it can also perform chaining on the image to be searched during motion.

(Contour Extracting Device 62)

[0174] The contour extracting device 62 includes an edge angle/edge strength image creating device 60 for creating an edge angle image and an edge strength image as edge images, and a thinning device 61. Specifically, with respect to a multi-valued image inputted by the image input device 1 (an original image of an original size or a reduced image reduced by a later-mentioned image reducing device 77), the edge angle/edge strength image creating device 60 creates edge strength images respectively in the X and Y directions (an edge strength image component in the X-direction and an edge strength image component in the Y-direction) by use of a filter known for extracting an edge point, for example, by use of a Sobel filter each in the X and Y directions, and the device also creates a two-dimensional edge angle image from these edge angle images in the X and Y directions. Further, with respect to this edge image created by the edge angle/edge strength image creating device 60, the thinning device 61 thins the edge point, for example by edge-strength non-maximal point suppressing processing.

[0175] It is to be noted that the edge strength in the present specification is a numeral value expressing a degree as to whether or not one pixel is part of an edge (darkness to brightness). The edge strength is typically calculated from pixel values of a target pixel and nine pixels located therearound. Further, the edge angle shows a direction of an edge in one pixel, and typically calculated from edge strengths in the X and Y directions which are found by use of the foregoing Sobel filter or the like each in the X and Y directions.

(Chain Creating Device 63)

[0176] Meanwhile, the chain creating device 63 and the segment creating device 68 are used upon creating a pattern with part of a registered image regarded as a template image. The chain creating device 63 in the present example includes an edge chaining device 64 and a chain filtering device 66. Specifically, the edge chaining device 64 creates a chain by coupling a plurality of adjacent edge points among a plurality of edge points included in an edge image created by the contour extracting device 62. Further, the chain filtering device 66 performs filtering on a plurality of chain groups created by the edge chaining device 64 by means of a variety of characteristic amounts of chains.

(Segment Creating Device 68)

[0177] Further, the segment creating device 68 includes an edge chain segmenting device 65 and a segment selecting device 67. The edge chain segmenting device 65 approximates each chain having been created by the edge chaining device 64 and filtered by the chain filtering device 66, to create a segment. The segment in this case is a line and/or a circular arc appropriated by a least squares method. Further, the segment selecting device 67 performs the filtering on the segment.

[0178] Moreover, the segment selecting device 67 can also include a pattern characteristic selecting function. Namely, changing a selection criterion for a segment constituting a pattern model in accordance with characteristics of a pattern obtained from an object to be searched can realize more stable positioning. This is to be detailed later.

(Pattern Model Constituting Device 70)

[0179] The pattern model constituting device 70 is a device for creating a pattern model to be stored into the foregoing storage device. Specifically, each segment created by performing processing on a registered image by the foregoing contour extracting device 62, chain creating device 63 and segment creating device 68 perform processing on the registered image is processed by the pattern model constituting device 70. The pattern model is to be detailed later.

(Image Reducing Device 77)

[0180] Meanwhile, the image reducing device 77 is a device for reducing a registered image and an image to be searched. Its reduction ratio is automatically set by an automatic reduction ratio decision mode. Specifically, as described above, in the present embodiment, a region wished by the user to be a pattern model is set on the registered image. The reduction ratio in this case is automatically set in accordance with the region set by the user. Namely, the reduction ratio is automatically decided in accordance with a size of the pattern window PW for specifying a pattern model. For example, in the case of the pattern window PW being in rectangular shape, the reduction ratio is decided in accordance with a length of its shorter side.

[0181] It is to be noted that in the present specification, “increase a reduction ratio”, “a reduction ratio is large”, or “a reduction ratio is high” means increasing a reduction degree or increasing a compression ratio, and for example indicates reduction of a reduced image having a reduction ratio of one-eighth into a reduced image having a reduction ratio of one-sixteenth. On the contrary, “decrease a reduction ratio”, “a reduction ratio is small”, or “a reduction ratio is low” means suppressing a reduction degree and for example bringing a reduced image to the unmagnified image side, and for example indicates changing of a reduced image having a reduction ratio of one-sixteenth to a reduced image having a reduction ratio of one-eighth. Further, a “reduction ratio not smaller than unmagnification” does not mean enlarging the unmagnified image, but means an image having a reduction ratio larger than the unmagnified image, namely a reduction ratio of 1, or the unmagnified image of a reduction ratio of 1.

[0182] Moreover, other than such an automatic reduction ratio decision mode, a manual reduction ratio decision mode in which the user selects a desired reduction ratio and decides it as a reduction ratio may also be employed. In an example of a user interface shown in FIG. 5, the user is to select a reduction ratio as a reduction ratio for large-area search out of a plurality of reduction ratio, alternatives of one-second, one-fourth and one-eighth here. The reduction ratio may be specified with an arbitrary numeral value. Further, an image showing how the original image transforms by reduction of the image with a reduction ratio selected in this case may be displayed in conjunction. In such a manner, a reduction ratio for local search (medium reduction ratio) and a fine positioning reduction ratio can also be set other than the reduction ratio for large-area search (reduction ratio for large area).

[0183] Further, a reduction ratio for local search can also be automatically added. Specifically, when a ratio between the reduction ratio for large-area search and the reduction ratio for local search is larger than a predetermined value, a local search (additional local search) set with an additional reduction ratio (reduction ratio for local search) between these reduction ratio for large-area search and reduction ratio for local search is automatically added (cf. FIG. 10). Further, the additional local search can be repeated a plurality of times. In such a manner, the ratio between the reduction ratio for large-area search and the reduction ratio for local search can be held within the predetermined value, to seek reduction in search speed.

[0184] The image reducing device 77 is utilized for a registered image that creates a pattern model and an image to be searched that is reduced with the same reduction ratio as a reduction ratio set in the registered image. Namely, the image to be searched is also reduced with the reduction ratio set in the registered image.

(Edge Angle Bit Image Creating Device 69)

[0185] The edge angle bit image creating device 69 creates an edge angle bit image by use of an edge angle image created by the foregoing edge angle/edge strength image creating device 60 of the computing device 6 with respect to an image to be searched and a reduced image obtained by reducing the image to be searched by the foregoing image reducing device 77. Namely, the edge angle bit image creating device 69 is used to create an edge angle bit image of an image to be searched during motion. In other words, it is not used upon registration of a pattern model.

[0186] More specifically, as shown in FIGS. 6A to 6C, values of 0 to 360 degrees as edge angles are sectionalized in units of 45 degrees into eight bit data (FIG. 6B). It is determined whether or not edge angles obtained corresponding to the respective pixels of the edge angle image are in bit positions allocated to the respective eight sectionalized regions (FIG. 6A), and a flag of 1 is set in the determined bit position, to transform the edge angle image into an edge angle bit image (FIG. 6C). In the present embodiment, an edge angle bit image is created by the edge angle bit image creating device 69 by use of an edge angle image created by the edge angle/edge strength image creating device 60 of the computing device 6 (detailed later based on FIG. 30 and the like). However, this method is not restrictive, and for example, an edge angle bit image may be created by the edge angle bit image creating device 69 by use of an edge angle image thinned by the thinning device 61 of the computing device 6.

(Edge Angle Bit Image Reducing Device 78)

[0187] The edge angle bit image reducing device 78 is a means for reducing an edge angle bit image created by the foregoing edge angle bit image creating device 69. Thereby, an edge angle bit reduced image is obtained.

[0188] A reduction ratio of an edge angle bit reduced image in the present embodiment is decided in accordance with the size of the pattern window PW by use of which the user sets a region wished to be a pattern model on a registered image. Therefore, in the case of automatically deciding a reduction ratio in the edge angle bit image reducing device 78, the size of the pattern window PW set on the registered image is reflected. However, this method is not restrictive and, needless to say, the reduction ratio in the edge angle bit image reducing device 78 can be directly set by checking a reduction ratio of the pattern model.

[0189] This state is described by comparison with a conventional method. In the case of reducing an edge angle bit image by the conventional method, for example, in the case of the reduction ratio being one-eighth of the original image size of the image to be searched, a region of 8×8 pixels, namely an edge angle of one pixel representing 64 pixels or an edge angle of one pixel obtained by reducing an average value of 64 pixels has been regarded as a center value of the region. As opposed to this, in reduction in edge angle bit image by the edge angle bit image reducing device 78 according to the present embodiment, for example in the case of the reduction ratio being one-eighth of the original of the image to be searched, a state is held where a flag of 1 is set in a bit position of each pixel of 64 pixels in the 8×8 region, namely in a bit position corresponding to every angle possessed by 64 pixels as shown in FIG. 7 in the form of storing the bit positions as they are by an OR operation. It is thereby possible to store information on the edge angle bit image so as to be prevented from being damaged even after image reduction, and thus obtain accuracy in a search by use of a pattern model.

[0190] An OR operation region where the OR operation is performed is decided in accordance with a reduction ratio for reducing the edge angle bit image. For example, in the case of creating an edge angle bit reduced image by reducing the edge angle bit image into one-eighth, a region of 8×8 is the OR operation region. Namely, the edge angle bit image is sectionalized into 8×8 OR operation regions, and in each OR operation region, a result of performing the OR operation on edge angle bits of all pixels included in the OR operation region is reduced edge angle bit data representing each OR operation region. Aggregation of reduced edge angle bit data in each OR operation region obtained in the above manner is an edge angle bit reduced image.

[0191] Further, the OR operation means a sum operation, especially a sum operation of bits. Moreover, upon performing the OR operation of pixels, other than simply adding up bits, a lower limit value may be set on the number of pixels having edge angle bits. For example, in a case where the number of pixels each having an edge angle bit to be added does not satisfy a predetermined number-of-pixels threshold, this edge angle bit is ignored. Namely, since edge angle bits to be added of bit pixels in number extremely smaller than others, such as one to several pixels, may be noise or an error, such pixels having low credibility can be ignored. It is thereby possible to create a highly reliable edge angle bit reduced image based on only angle bits thought to be highly reliable.

(Other OR Operation: Saturated Addition)

[0192] Further, as the OR operation, an operation other than the above-mentioned sum operation can also be used. A saturated addition is described as an example. For example, in the case of performing reduction processing or enlargement processing by the OR operation, the OR operation is performed on pixel data on an edge angle bit image of n×n. Extension of this operation is to “perform saturated addition on a bit corresponding to each angle and decide a next center value from a result of the saturated addition”. The saturated addition means addition processing in which an upper limit is previously set on an addition result and in the case of the a result of regular addition exceeding the upper limit, clipping is performed at the upper limit value. For example, when the upper limit is 100, the upper limit is restricted to 100 in the following manner:
10+89=99
11+89=100
12+89=100
10+100=100

[0193] Next, a specific example of reduction processing by use of the saturated addition is described based on FIGS. 52A and 52B. FIG. 52A is a schematic view showing an edge angle image in which each pixel has an edge angle, and FIG. 52B is a schematic view showing an edge angle sections for expressing the respective pixels constituting this edge angle image with 8-bit edge angle bit data. It is to be noted that edge angle sections obtained by sectionalizing an angle for expressing edge angle directions by edge angle bits is described later by means of FIG. 31. In the example of FIG. 52B, the edge angle is sectionalized by displacement by 22.5 degrees from the horizontal or vertical direction. The edge angle sections are respectively labeled with E, SE, S, SW, W, NW, N and NE by a width of 45 degrees clockwise from exactly right, and respectively provided with labels of edge angle bits of 0, 1, 2, 3, 4, 5, 6 and 7. An edge angle bit image obtained by representing nine pixels “a” to “i” constituting the edge angle image of FIG. 52A with edge angle bits in accordance with the edge angle sections of FIG. 52B have edge angle bit data as follows:

[0194] 76543210

• [0195] a: 00001000
• [0196] b: 10000000
• [0197] c: 10000000
• [0198] d: 00001000
• [0199] e: 10000000
• [0200] f: 10000000
• [0201] g: 00001000
• [0202] h: 00000100
• [0203] i: 10000101

[0204] Then, in an edge angle bit image in a new reduced image, bits of “a” to “i” corresponding to the respective angles are all subjected to the saturated addition. The upper limit in the saturated addition is set to three. For example, reduced edge angle bit data “e′” of the position of “e” can be calculated by:
e′=a+b+c+d+e+f+g+h+i
A result of the calculation is as follows:

[0205] 7766554433221100

• [0206] e′: 1100000011100001; binary display
• [0207] e′: 3 0 0 0 3 2 0 1; decimal display

[0208] In the above computing result, characteristics of the saturated addition processing appear. Namely, values not smaller than three are all clipped to three. Such an addition is referred to as the saturated addition where, when a summing result is not smaller than a clipping threshold as thus described, clipping is performed at that value. This reduced edge angle bit data “e′” can be used as it is in search processing. For example, reduced edge angle bit data e″ where only values not smaller than two are made one and the other values are made zero can be expressed as follows so as to be used for the search:

[0209] 76543210

• [0210] e″: 10001100; binary display
  (Pattern Model X for Coarse Search Device)

[0211] The pattern model constituting device 70 creates two kinds of pattern models, which are a pattern model X for coarse search to be used in later-mentioned coarse searching device 71, and a pattern model Y for fine positioning to be used in the fine positioning (FIGS. 8A to 8C). The pattern model X for coarse search is formed such that a reference point is decided on each segment based on a pre-set condition, and an angle is set which is in a direction of a normal to the segment at each reference point and at which an orientation of an edge is set.

(Pattern Model Y for Fine Positioning)

[0212] Meanwhile, as for the pattern model Y for fine positioning, each reference point is created where, in addition to information of the foregoing pattern model X for coarse search, a parameter classified by a segment expressing each corresponding segment (e.g. parameter capable of defining a segment made up of a line or a circular arc) and a line (hereinafter referred to as “corresponding point search line), which is a kind of normal to the segment that is extended in the edge direction and further has a predetermined length, are set. The corresponding point search line is extended forward and backward in the direction of the normal with the reference point set at the center. It is to be noted that one or more reference points are preferably set on each segment. In other words, it is not necessary to include a segment with no reference point set thereon in the pattern model.

(Rough Search Device 71)

[0213] A search during motion is performed by the coarse searching device 71 and the fine positioning device 76 by use of a dedicated pattern model created upon registration. The coarse searching device 71 is a device for performing a coarse search during motion. The coarse search can be performed a plurality of times with different reduction ratios, as well as only once. In the case of performing the coarse search a plurality of times, it is preferably performed based on more detailed data approximated to the original size in such a manner that a reduction ratio of a second coarse search is suppressed lower than a reduction ratio of a first coarse search, namely a resolution is increased, or some other manner. Further, the second coarse search is preferably performed while narrowing a scanning area based on a result of the first coarse search. A scheme of searches during motion is shown in a flowchart of FIG. 9 and a schematic view of FIG. 10. In the present embodiment, as shown in Step S901 of FIG. 9, a first coarse search (large-area search), which is performed by use of a second pattern model obtained by reduction with a reduction ratio for large area, is performed on the whole area of an image to be searched. Thereafter, a second coarse search (local search) is performed on a region of a “detection candidate” obtained by the first coarse search and a region on the periphery thereof in an image to be searched having a medium reduction ratio that is lower than in the first coarse search. Further, in Step S903, fine positioning is performed by the fine positioning device 76 by use of the pattern model Y.

[0214] It should be noted that the order of creating a pattern model upon registration and the order of executing a search during motion are not necessarily matched with each other. For example, upon registration, pattern models are created sequentially from a pattern model having a lower reduction ratio (close to the original size), (first pattern model→second pattern model, etc.). This can extremely reduce conditions in which minute information is lost as the image is reduced. As opposed to this, during motion, a search is performed on pattern models in a reverse order, starting from a pattern model having a higher reduction ratio (lower resolution, higher compression ratio, etc.), (first coarse search→second coarse search). Thereby, a search can be performed efficiently by coarse-to-fine approach. This results in that the first coarse search is performed by use of the second pattern model during motion, and subsequently, the second coarse search is performed by use of the first pattern model.

(First Coarse Search)

[0215] Next, a scheme of the coarse search performed by the coarse searching device 71 is described. First, in the first coarse search, a rough search is performed on the whole area of the image to be searched by use of the registered pattern model, to extract a rough position, namely a detection candidate. On the edge angle bit reduced image of the image to be searched created by the edge angle bit image reducing device 78, scanning is performed by use of a pattern model created from the registered image having the same reduction ratio. Specifically, for example, in order to scan the whole region of an edge angle bit image obtained by reducing the original size into one-eighth, a pattern model set in a posture having a specific rotational angle is scanned from the upper left of the edge angle bit reduced image toward a lower-right direction. Thereby, a region of the detection candidate similar to the pattern model is specified in the whole region of the edge angle bit reduced image. The same scan is performed in the same manner by use of all of a plurality of different rotational postures which are individually set on the pattern model. Namely, the scan with a changed rotational angle is repeated a plurality of times. Consequently, the entire region of the detection candidates similar to the pattern model is extracted as a matching candidate with respect to the pattern model. FIGS. 11A to 11D each show a state where edge angle bits change as a result of rotation of the pattern model. In this example, a change in edge angle bit from (b) to (d) in a case (c) of rotating a pattern model (a) for large-area search clockwise by 60 degrees. Further, an evaluation value (score value), representing a similarity, of each detection candidate is computed, and candidates having a score value higher than a certain threshold are extracted. Moreover, each detection candidate has information on its position and posture, namely an XY coordinate of the pattern model, an angle θ and a score. It is noted that the score is to be detailed later.

(Second Coarse Search)

[0216] Next, the coarse searching device 71 performs the second coarse search based on a result of the first coarse search. In the second coarse search, a reduction ratio smaller than the reduction ratio of the image to be searched which was used in the foregoing first coarse search, i.e. a reduction ratio with a larger amount of information, is used. The detection candidates are narrowed down for example by use of an edge angle bit reduced image having a reduction ratio of one-fourth, and by use of a pattern model having a reduction ratio of one-eighth only in the entire peripheral region of the detection candidate similar to the pattern model which was extracted in the edge angle bit reduced image having the same reduction ratio used in the first coarse search. Since this second coarse search is a search performed using part of the edge angle bit reduced image, it can efficiently execute narrowing down of the detection candidates. As thus described, an efficient search can be made possible by performing the coarse search in a plurality of stages. Namely, after the whole area is scanned to specify a rough position in the first coarse search, the second coarse search is performed in the specified region (detection candidate, or “one likely to be the object”) or in the vicinity thereof in the image having a lower reduction ratio. Further, the local search can be performed a plurality of times in accordance with reduction ratios.

(Fine Positioning Device 76)

[0217] As thus described, after a “detection candidate more likely to be the object” is found by performing the coarse search on the detection candidates and the vicinity thereof by the coarse searching device 71, fine positioning is performed by the fine positioning device 76. In the fine positioning, a search is performed in a non-reduced image of the original size or an image having a reduction ratio that is lower than the reduction ratio used in the coarse search and close to the original size. It is to be noted that, in this case, the image of the original size is also treated as an image having a reduction ratio of one. Further, the image to be searched is an edge angle bit image in the coarse search, whereas it is the original image or an image reduced therefrom in the fine positioning.

[0218] The fine positioning device 76 arranges a corresponding point search line of the pattern model Y for fine positioning so as to be superimposed on the image to be searched in the region of the detection candidate which was obtained on the image to be searched and is similar to the pattern model. Specifically, this is a search device for performing a search by use of a pattern model having the same magnification as that of the image to be searched in the region of the detection candidate, which was narrowed down by the searches by means of the edge angle bit reduced image and the pattern model having two different reduction ratios by use of the foregoing coarse searching device 71, and is similar to the pattern model.

[0219] Each of the pattern models used by the coarse searching device 71 and the fine positioning device 76 above is not an image itself as data for use in image processing (hereinafter referred to as “image data”), but data formed by one-dimensionally listing at least an X coordinate position, a Y coordinate position and an edge angle value corresponding to each edge point obtained from the image data. The “pattern model” is one made up of such data, and using the pattern model being not image data but listed data can seek speeding up of processing. Meanwhile, the image data is so-called image data, and for example, when it has data size of 640×480 bits, a value of each coordinate position of each pixel in the whole area needs to be held. As opposed to this, in the case of using the pattern model, it can be configured only of a position and an angle corresponding to an edge portion of an edge image. Hence a data amount is relatively small, to allow reduction in required amount of processing. Therefore, the use of the pattern model in place of image data enables processing at higher speed.

[0220] It is to be noted that in the present specification, the “registered image” is the original of an image wished to be searched. Meanwhile, the pattern model is the forgoing listed data suitable for a search for the same image as the registered image out of the image to be searched. In the present embodiment, the pattern model has information on the XY coordinate and the angle θ of each point constituting the pattern model. As described later, data constituting the pattern model in the fine positioning has information on a later-mentioned corresponding point search line on top of the information on the XY coordinate and the angle θ of each point.

[0221] Each member shown in FIG. 1 can also be executed by integrating a plurality of members, or dividing one function into individual members. For example, the image reducing device 77 for reducing an image can be integrated into the contour extracting device 62. Further, while each function of the computing device 6 can be processed by one CPU, LSI or the like, for example, the functions may be dispersed into a dedicated FPGA for performing pre-processing, a dedicated DSP for performing image processing, and the like. In this image processing apparatus 100, image processing is performed in an image processing portion made up of a DSP or the like, and displays of an image and a search result are processed by a CPU. As thus described, dispersing and processing each function can seek speeding up of processing. A member that executes each function can be arbitrarily made up.

[0222] The image input device 1 acquires an input image which was picked up and created by external equipment and is subject to image processing. Input image data can be acquired from external equipment by communication or I/O, and other than that, the data can also be inputted in the form of data file through a recording media. Further, the image processing apparatus itself may be made to have a function of picking up an input image. In this case, the image input device 1 functions as an image pickup device and an image creation device. When a camera using a solid-state image pickup element such as a CCD or a CMOS as the image pickup device is used and a work such as an electronic component to be subject to image processing is picked up, there is a difference in light amount of reflected light between light irradiated on the work and light irradiated on the background, and hence a difference occurs in electronic charge amount of the solid-state image pickup element between a portion corresponding to the work and a portion corresponding to the background. Namely, since a difference in luminance of the image occurs between the work and the background, this luminance difference can be detected as a contour or an edge of the work. It is to be noted that contour data on the registered image can also be inputted as CAD data on the work or the like. In such a manner, data inputted from the image input device 1 is A/D converted as appropriate, and transmitted to an image processing apparatus body portion.

[0223] The storage device 4 stores a parameter file storing a variety of data necessary for a variety of transformation and calculation for template matching and the like, and data on a pattern model of a registered image, an edge image for an image to be searched, and the like. As thus described, other than storing set contents, the storage device 4 can also be used as a region for storing data of an input image. As such a storage device 4 used can be a semiconductor element such as a DRAM or a flash memory, or a solid-state storage device such as hard disk.

[0224] The operation device 2 is an input device for operating the image processing apparatus 100. For example, in a case where the user operates a mouse 81 and a keyboard 82 to manually specify a processing region, the input device functions as a processing region specifying device 5. On the other hand, computing can also be performed by the computing device 6 based on image processing on the image processing apparatus 100 side, to automatically specify the processing region.

[0225] The input device is cable-connected or wireless-connected, or fixed, with the image processing apparatus 100. Examples of a typical input device include a variety of pointing devices such as a mouse, a keyboard, a slide pad, a track point, a tablet, a joy stick, a console, a jog dial, a digitizer, a light pen, a ten key, a touchpad, and a pointing stick. Further, in the mode of connecting a computer where a contour extracting program is installed with the image processing apparatus 100, or in the mode of regarding the computer where the contour extracting program is installed as an image processing apparatus or a contour extracting device, the above devices can also be used in operations of the image processing apparatus itself and its peripheral equipment other than an operation of the contour extracting program. Moreover, the user can directly touch the surface of the screen for making an input and an operation through use of a touch screen or a touch panel for a display itself that displays an interface screen, or the user can use a vocal input device or other existing input devices, or can also use these simultaneously. In the example of FIG. 1, the input device is made up of the pointing devices such as the mouse and the keyboard.

[0226] As the display device 3, a display such as an external liquid crystal monitor or a CRT monitor can be used. Further, a display device and an operation device can be simultaneously used by use of a display device of a type equipped with an input function such as a touch panel. The display device 3 can also be built in the image processing apparatus itself other than taking the form of being externally connected therewith.

[0227] The above configuration is exemplary, and for example, the image processing apparatus itself may include a display device, an operation device, and the like, and each member can also be simultaneously used in one member or may be integrated into the computing device 6. In the following, an example is described where a contour extracting program is installed into a general-purpose computer to execute edge coupling processing and contour extracting processing.

(Detailed Procedure for Image Processing)

[0228] This image processing apparatus performs pre-processing (enlargement, reduction, smoothing, Sobel filtering, and the like) on a registered image (also referred to as standard image, referenced image, and the like) and an image to be searched which were acquired by the image input device 1, and thereafter, extracts an edge as characteristic extraction. The apparatus then performs an edge-based pattern search during motion by use of a pattern model obtained from the registered image. In the present embodiment, as described above, a pattern model is previously registered (FIG. 3), and upon actual operation, processing is performed on the image to be searched (FIG. 4). As thus described, dispersing processing upon registration and processing during motion can speed up the processing.

[0229] The operation upon registration is described more specifically. By processing the registered image by the foregoing contour extracting device 62, a contour portion of the registered image is extracted as an edge, and an edge image for registered image is created which is expressed by aggregation of points with a width of about one pixel. The edge image for registered image is temporarily stored into an edge image memory for registered image of the storage device 4. Further, a pattern model is created from the edge image for registered image by the segment creating device 68 and the pattern model constituting device 70. The pattern model to be used in the search is held in a pattern model memory of the storage device 4, and is called as appropriate.

(Creation of Pattern Model Upon Registration)

[0230] FIG. 12 shows a flowchart of a procedure for creating the pattern model upon registration. For creation of the pattern model, as described above, a master image of an image wished to be extracted out of the image to be searched is specified as the registered image, and temporarily stored into the storage device 4. Therefore, a pattern window is set on the registered image (Step S1201). A reduction ratio is set with respect to this registered image (Step S1202), and thereafter, the image is sought to be reduced by the image reducing device 77 (Step S1203). Further, a contour is extracted from the reduced image. Specifically, edge extraction processing and chaining processing are performed (Step S1204). Further, chains are coupled to create a segment (Step S1205). In such a manner as above, edge data is sought to be segmented by the contour extracting device 62, the chain creating device 63 and the segment creating device 68 with respect to the reduced image. The pattern model is then created by the pattern model constituting device 70 (Step S1206).

[0231] As described above, in the present embodiment, two kinds of models are created as pattern model which are the pattern model X for coarse search and the pattern model Y for fine positioning. Further, a data structure of the pattern model for coarse search is made up of a coordinate position in the X and Y directions and an edge angle of each edge point with respect to an arbitrarily set original point. A data structure of the pattern model for fine positioning is made up of a coordinate position in the X and Y directions, an edge angle, and a later-mentioned corresponding point search line of each edge point with respect to the arbitrarily set original point.

(Edge Angle)

[0232] The edge angle is one showing a concentration gradient direction of the edge at the edge point. For showing the edge angle, 0 to 360 degrees are expressed by 256 levels.

(Edge Angle)

[0233] It is to be noted that, as for an edge strength of each edge point, in the present embodiment, the data is configured only of edge points having larger strength values than a pre-set strength value in the present embodiment, and hence the strength values are not held as data. However, the present invention is not restricted to this method, and for example in the case performing evaluation, weighting, or the like by later-mentioned score calculation based on similarity of edge strength values in search algorithm, data on edge strength may be held as a value of the data structure of the pattern model.

(Decision of Reduction Ratio of Image)

[0234] Further, upon using a reduced image upon registration, selection of its reduction ratio is highly important since the reduction ratio also exerts an effect during motion. There is set an appropriate reduction ratio with which noise can be eliminated and search time can be reduced while characteristic points in the image necessary for the search are held. For example, in the case of placing a high value on the search accuracy at the cost of the search time in the balance between the search accuracy and the search time to some degree, a reduction ratio is set to a specific reduction ratio that is made relatively low. Alternatively, an optimal reduction ratio decided by the user by trial and error can be utilized. In the present embodiment, an automatic mode for automatically deciding a reduction ratio and a manual mode for the user specifying a reduction ratio are made switchable. In the automatic mode, the reduction ratio is decided based on a length of a shorter side demarcating a rectangular region of the pattern window PW. Further, in the manual mode, when the user selects the optimal value while checking with his or her eyes how the pattern model actually transforms in accordance with the reduction ratio, it is possible to facilitate a setting operation as a sensuous operation. In an example of a user interface of FIGS. 13A to 13C, it is shown by means of an image that the reduction ratio can be selected using a dropdown list when the manual mode is selected, and how an image transforms in accordance with the selected reduction ratio. The higher the reduction ratio is made, the more significantly the image change its shape as its corner portion becomes less sharp. With reference to such a change in image, the user can select an appropriate reduction ratio in accordance with his or her application or purpose.

[0235] Otherwise, as another example, a technique for automatically deciding the balance between the search accuracy and the search time may be adopted. For example, as items on which the user puts a high value, the search accuracy, the search time, and both of them are presented as alternatives, and after a selection is made by the user, an appropriate setting is automatically performed in accordance with the selection.

(Pattern Model X for Coarse Search)

[0236] The coarse search is a search for efficiently narrowing down, for a short period of time, a region where the same image as the registered image is highly likely to be present as a detection candidate out of the image to be searched, in advance of the later-mentioned fine positioning. Therefore, the coarse search achieves the foregoing purpose through use of an image reduced from an original image to be searched or an original registered image. More specifically, as is the pyramid search shown in FIG. 87, the coarse search is performed by use of a reduced image obtained by reducing an image of the original size. In this coarse search, an image having a high reduction ratio and a low resolution is used. Then, the fine positioning is performed on a coarse position (detection candidate) obtained in the coarse search. In this fine positioning, an image having a lower reduction ratio and a higher resolution than those in the coarse search are used.

[0237] A procedure for creating the pattern model X for coarse search is described. In Step S1201, a master image of an image wished to be detected out of the image to be searched is temporarily stored as the registered image into the registered image memory of the storage device 4. More specifically, the user sets on the screen a position and a size of a portion required as a registered image with respect to an image captured from the image pickup device and displayed in the display device by use of the pattern window PW in rectangular shape as shown in FIGS. 2A to 2H.

[0238] Next, a reduction ratio upon reducing the image by the image reducing device 77 is decided in this registered image (Step S1202). In the present embodiment, a reduction ratio for large area of the pattern model described later is decided in accordance with the size of this pattern window PW, namely the number of pixels included in the rectangle.

[0239] That is, in the case of the number of pixels as the registered image being relatively large, the reduction ratio is set rather high since a loss of characteristic points inside the image is small even with the reduction ratio set high. On the other hand, in the case of the number of pixels as the registered image being relatively small, the reduction ratio is set rather low since the characteristic points inside the image is more likely to be lost. It is preferable to set, as the optimal reduction ratio, a reduction ratio to such a degree that reduction leads to removal of noise inside the image, but does not lead to loss of the characteristic points in the image.

[0240] As another technique for deciding a reduction ratio, for example, the registered image is shifted in the X and Y directions by a predetermined amount with respect to the same registered image. When the autocorrelation modestly changes, the image can be determined as having a characteristic that a correlation value is not apt to change so long as a certain degree of matching is realized, and hence the reduction ratio is set high. On the other hand, when the autocorrelation drastically changes, the image can be determined as having a characteristic that the correlation value is apt to change, and hence the reduction ratio is held low. In such a manner, the reduction ratio can also be decided based on the autocorrelation.

[0241] Based on the reduction ratio decided in such a manner as above, the registered image of the original size is reduced by the image reducing device 77 (Step S1203). Specifically, in the image reducing device 77, reduction in image is executed not with a final reduction ratio decided based on the size of the pattern window PW, but with the medium reduction ratio positioned between the original size of the image and the reduction ratio for large area. The edge is further sought to be segmented by the contour extracting device 62, the chain creating device 63 and the segment creating device 68 with respect to the image having the medium reduction ratio by the image reducing device 77 (Step S1204, Step S1205). It is to be noted that the medium reduction ratio corresponds to the reduction ratio in the second coarse search.

[0242] Reduction in image of the original size is followed by edge-data formation and segmentation of the image because performing the processing in this order can reduce noise while storing characteristic points held in the original image as compared with the reversal order in which the edge-data formation and segmentation of the image of the original size is followed by reduction in the obtained image. Further, this method is also in line with the purpose of the coarse search to extract the region of the detection candidate similar to the pattern model. Therefore, the medium reduction ratio can be set in a manual setting where the user manually decides the ratio while looking at the segment so that noise can be reduced to some degree while characteristic points in the image of the original size are held. Alternatively, the medium reduction ratio can be set in an automatic setting where the ratio is automatically set in accordance with the size of the pattern window PW.

(Creation of First Pattern Model)

[0243] Next, in Step S1206, the pattern model constituting device 70 creates the first pattern model with the foregoing medium reduction ratio by use of the data segmented by the segment creating device 68. This first pattern model is used for the local search among the coarse search (Step S902 of FIG. 9). FIGS. 8A to 8C each show an example of each pattern. In the first pattern model, as shown in FIG. 8A, a reference point is decided on each segment present inside edge image data based on a pre-determined condition, and an edge model point is defined at which an edge angle is set in the direction of the normal to the segment and in the orientation of the edge with respect to each reference point.

(Creation of Second Pattern Model)

[0244] Further, the pattern model constituting device 70 creates a second pattern model with the foregoing reduction ratio for large area by use of the data segmented by the segment creating device 68 (FIG. 8B). In this second pattern model for coarse search, as in the same manner as the first pattern model, a reference point is decided on each segment present inside edge image data based on a pre-determined condition, and an edge angle is set in the direction of the normal to the segment and in the orientation of the edge with respect to each reference point. These pattern models may not be created individually in accordance with reduction ratios, but it is possible that only one pattern model is created and then used by being enlarged or reduction ratio in accordance with a reduction ratio of an image to be searched during motion.

[0245] A difference between the first pattern model and the second pattern model is that in a case where the reference points set on each segment are present in a plurality of numbers, as shown in FIGS. 8A and 8B, a distance between the reference points is long in the second pattern model as compared with in the first pattern model. This is attributed to a difference in reduction ratio between the two pattern models. A degree of the difference in distance between the reference points is controlled by a difference between the medium reduction ratio and the reduction ratio for large area.

[0246] As shown in FIG. 9, the specific coarse search is made up of a “large-area search” (Step S901) carried out on the whole range of the image to be searched by use of the second pattern model having the reduction ratio for large area, and a “local search” (Step S902) carried out only on the candidate region of the detection candidate, extracted by this “large-area search”, by use of the first pattern model having the medium reduction ratio.

[0247] In the description of the present embodiment, in the coarse search, one “large-area search” by use of one pattern model having the reduction ratio for large area and one “local search” by use of one pattern model having the medium reduction ratio are performed. Specifically, in the case of the following medium reduction ratio with respect to the original size of the image, the reduction ratio for large area is set as follows:

• [0248] (1) in the case of not higher than 1/√2 times, the reduction ratio for large area is set to one-second of the medium reduction ratio;
• [0249] (2) in the case of 1/√2 to ¼ times, the reduction ratio for large area is set to one-third of the medium reduction ratio; and
• [0250] (3) in the case of not lower than one-fourth, the reduction ratio for large area is set to one-fourth of the medium reduction ratio.
  As thus described, the reduction ratio for large area is decided in accordance with the medium reduction ratio, thereby striking the balance between search efficiency and storage of characteristic points from the original image.

[0251] The local search can be performed a plurality of times. In the case of the medium reduction ratio being significantly high with respect to the original size, for example in the case of the medium reduction ratio being set to one-fourth of the original size of the image as (3) above, the medium reduction ratio becomes one-sixteenth of the original size of the image. In this case, since the ratio between the reduction ratio for large area and the medium reduction ratio is as large as four times, it might take too long for the “local search” to be performed on the candidate region of the detection candidate extracted by use of the second pattern model having the reduction ratio for large area and the periphery thereof.

[0252] Therefore, in the present embodiment, when the ratio between the medium reduction ratio and the reduction ratio for large area is larger than twice, an additional medium reduction ratio is set so as to add one or more searches such that the ratio between adjacent reduction ratios becomes not larger than twice. Namely, by performing two or more local searches, reduction in time required for one local search is sought. Such automatic addition of the medium reduction ratio (reduction ratio for local search) can be set for example by making a checkbox for an option to “automatically add reduction ratio for local search” in the user interface screen shown in FIG. 5.

[0253] As described above, a pattern model has a data structure made up of a coordinate position in the X and Y directions and an edge angle of each edge point with respect to an arbitrarily set original point. Therefore, when the additional medium reduction ratio is set, a pattern model corresponding to the additional medium reduction ratio is created from a segment as in the cases of the foregoing first pattern model and the second pattern model. The pattern model having the additional medium reduction ratio differs from the first pattern model as well as the second pattern model in that, when reference points set on each segment are present in a plurality of numbers, the distance between the reference points is long as compared with in the first pattern model, and is short as compared with in the second pattern model. Since the pattern model itself is made up of data on coordinate positions and the like, even when the pattern model is reduced, a defect of information due to the reduction can be made extremely small as compared with the defect of information due to reduction in image data.

(Large-Area Search)

[0254] The operation in the search during motion is also described for the sake of convenience of description. As shown in Step S901 of FIG. 9, by execution of the “large-area search” by use of the pattern model having the reduction ratio for large area, the candidate region of the detection candidate is extracted. Then, the “local search” is executed on the extracted candidate region of the detection candidate by use of the second pattern model having the second highest ratio only to the reduction ratio for large area. Thereby, based on a result of the search, the candidate region of the detection candidate with higher accuracy is narrowed down. Subsequently, the “local search” is executed on the narrowed-down candidate region of the detection candidate by use of a pattern model having a set medium reduction ratio in decreasing order of reduction ratio, to repeat the step of narrowing down the candidate region of the detection candidate.

(Fine-Positioning Reduction Ratio)

(Manual Reduction Ratio Decision Mode)

[0255] Further, as described above, in the case of the manual reduction ratio decision mode in which the user can select the reduction ratio by use of the user interface of FIG. 5, the user can select one medium reduction ratio, one reduction ratio for large area, and a fine-positioning reduction ratio that is used upon using the fine positioning device 76. However, such a setting may be made also in this case that, when the ratio between the selected medium reduction ratio and the reduction ratio for large area is larger than twice, between these reduction ratio, a further medium reduction ratio based on the foregoing condition is automatically created. Further, as for the fine positioning reduction ratio upon using the fine positioning device 76, when the user is to select a candidate of the reduction ratio, a value to be selected is restricted to be the lowest value among reduction ratios set for the coarse search or a value of a reduction ratio further lower than this (including the original size of the image). Thereby, a condition can be avoided in which the fine positioning is erroneously performed using coarser data with higher reduction ratio than the pre-stage coarse search.

(Pattern Model for Fine Positioning)

[0256] As shown in Step S903 of FIG. 9, the fine positioning search is to perform fine positioning by use of a pattern model having a final medium reduction ratio lastly used in the “local search” or a reduction ratio lower than this (including the original size of the image) on the candidate region of one or a plurality of detection candidates. The reduction ratio of the pattern model for use in the fine positioning is preferably an unmagnified image, namely the original image of the original size.

(Sharpness of Edge)

[0257] As described above, in the fine positioning, the image to be searched of the original size is not necessarily used, but an image reduced with a reduction ratio (fine-positioning reduction ratio) in the range not exceeding the final medium reduction ratio lastly used in the pre-stage local search can also be used. Thereby, especially even when the image to be searched is blurred, a preferred search result can be expected.

[0258] For example, it can be regarded that the sharper the waveform of luminance data of the edge image of the original size, the higher the sharpness, and on the contrary, the gentler the waveform, the more blurred the image. Therefore, when the sharpness of the edge portion is lower than a pre-set value, namely when the edge is dispersed in its width direction by a width not smaller than a predetermined width and the image is thus blurred, the reduction ratio is set to an appropriate fine-positioning reduction ratio and the image is reduced into this reduction ratio, so that sharpness of this image can be reduced to increase the sharpness of the edge, and hence stable positioning accuracy can be obtained.

[0259] For example, in the case of a binary image where pixels change sharply as shown in FIG. 53, a contour, namely an edge, of this image is a so-called step edge where its pixel concentration, namely pixel value, changes stepwise as shown in FIG. 54. Therefore, as shown in FIG. 55, a border of a change in strength of the edge tends to appear sharply, and accurate positioning can be expected. On the other hand, when the binary image is unclear, the border portion changes gently as shown in FIG. 56, resulting in that the change in strength of the edge becomes a poorly waved curve as shown in FIG. 57. There has thus been a problem in that even a slight fluctuation in peripheral environment such as a change in illumination or light amount exerts an effect on the edge detection accuracy, thereby preventing stable edge detection and lowering reliability of image processing such as image recognition. Accordingly, in the present embodiment, the image is reduced into the appropriate reduction ratio, to improve the edge sharpness.

(Decision of Sub-Pixel Coordinate of Edge)

[0260] Specifically, in the fine positioning by use of edge information, highly accurate positioning is performed based on the pattern model created on the basis of positional information on the edge extracted from the registered image and positioning information on the edge extracted from the image to be searched. Therefore, the positional information on the edge is extremely important.

[0261] Conventionally, as a technique for deciding a sub-pixel position of the edge, techniques of Japanese Unexamined Patent Publication No. H07-128017, U.S. Pat. No. 6,408,109B1, and the like are known. In these methods, a sub-pixel coordinate is found by means of quadric interpolation, using a total of three data: an edge strength of a target pixel and edge strengths of two pixels positioned therearound. FIG. 58 shows a scheme of a method for calculating a sub-pixel coordinate according to Japanese Unexamined Patent Publication No. H07-128017. In this drawing, EMc (Edge Magnitude center) is an edge strength value of a target edge point as an edge point left after non-maximal point suppressing processing (nonmaxsupress) for thinning the edge. Further, EMf (Edge Magnitude forward) is an estimated edge strength value indicated by an arrow in an orientation of an edge angle of the target edge point. Moreover, EMb (Edge Magnitude backward) is an estimated edge strength value indicated by a circle in the orientation of the edge angle of the target edge point. Furthermore, a subscript of 1 in EMf1, EMb1 is given to a characteristic amount of an edge point in the cross direction, and a subscript of 2 in EMf2, EMb2 is given to a characteristic amount of an edge point in the diagonal direction. In the following example considered is an angle EAc, formed by the edge angle with the horizontal direction, <45 degrees. Other angles can be found by considering symmetry. The following expressions are established.
EMf=EMf1*(1−tan EAc)+EMf2*tan EAc
EMb=EMb1*(1−tan EAc)+EMb2*tan EAc

[0262] Using three edge strength data of EMc, EMf and EMb in the above expressions, an offset amount of the sub-pixel position can be calculated by the following expression:
x=(EMf−EMb)/(2(2EMc−EMf−EMb))
y=x*tan θ

[0263] As thus described, the sub-pixel position can be computed. Next, FIGS. 55 and 57 show a state of an edge strength in focus and a state of an edge strength in an unclear image. As apparent from FIG. 55, a peak of the edge strength that in focus to some degree is sharp and the edge position can be clearly decided. On the other hand, in the case of the unclear and blurred image as shown in FIG. 57, the vicinity of the maximum comes into quite a flat state, and an error of edge strengths has a large effect on the sub-pixel coordinate. In order to evaluate that effect, the case of EMf having an error of one gradation in EMf=EMb is considered. The relation between the error of the edge angle and the sub-pixel position is shown in the following expression:

[0264] $\begin{array}{cc}{x}^{\prime }=\frac{f_d\left(1\right)-f_d\left(-1\right)}{2(2f_d\left(0\right)-f_d\left(1\right)-f_d\left(-1\right)}& \left[\mathrm{Expression}5\right]\\ y=\frac{x-a}{2\left(2c-x-a\right)}& \left[\mathrm{Expression}6\right]\end{array}$

[0265] In the above function, a state around “x=a+1” is checked by means of the following expressions:

[0266] $\begin{array}{cc}\delta y=\frac{a-a}{2\left(2c-a-a\right)}-\frac{a+1-a}{2\left(2c-a-1-a\right)}& \left[\mathrm{Expression}7\right]\\ \delta y=\frac{0}{2\left(2c-2a\right)}-\frac{1}{2\left(2c-2a-1\right)}& \left[\mathrm{Expression}8\right]\end{array}$

[0267] In the above expression, when “X=c−a”,

[0268] $\begin{array}{cc}\delta y=-\frac{1}{2\left(2X-1\right)}& \left[\mathrm{Expression}9\right]\end{array}$
When this is expressed by a graph, one as in FIG. 59 is obtained. As shown in this drawing, it is found that, as the edge strength is getting flat in X→0, namely, c→a, an effect exerted by the error of the edge strength on the error of the edge position becomes larger. The same tendency can be seen in EMf≠EMb. Therefore, in the present embodiment, the sharpness of the edge point is calculated, and using this value, an edge data reduction ratio for performing calculation of the sub-pixel position of the edge is calculated. Further, using image data reduced into the image data reduction ratio, the edge extraction is performed. As thus described, reducing the image data can transform a gentle waveform as in FIG. 57 into a sharp waveform as in FIG. 55, to stabilize an edge position so that the positioning accuracy can be improved.

[0269] A procedure for deciding the image data reduction ratio based on the sharpness of the edge point is described based on a flowchart of FIG. 60. First, in Step S6001, an edge image is created from the unmagnified image. Next, the edge of the edge image is sought to be thinned in Step S6002 while the sharpness of each edge point in the edge image is computed in Step S6003. The edge thinning processing is performed for the non-maximal point suppressing processing in advance of the edge coupling processing. Further, in Step S6004, an average value of the sharpness of the thinned target edge points is computed. Then, in Step S6005, the image data reduction ratio is decided based on this average of the sharpness. The image data reduction ratio is decided such that the positional accuracy of the edge points is held not lower than predetermined accuracy.

(Edge Model Function)

[0270] Next, an edge model function is considered. Many of the extracted edges are thought to be stepwise edges, and are assumed to be expressible by an edge model function shown below. “σs” of this edge model function is the sharpness of the edge point. An ideal form of the edge in this case is expressed as follows:

[0271] $\begin{array}{cc}\mathrm{edge}\left(x\right)=\Phi \left(\frac{x-d}{{\sigma }_s}\right)& \left[\mathrm{Expression}10\right]\\ \Phi \left(x\right)=\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^{x}e-\frac{z^2}{2}dz& \left[\mathrm{Expression}11\right]\end{array}$

[0272] FIG. 61 shows a graph of the above function. The ideal shape (profile) of the edge shown in this drawing is plotted by the following expression (in the case of I=2, l=0, and σs=0.6 along the X axis):

[0273] $\begin{array}{cc}S\left(x;\theta \right)=I\Phi \left(\frac{x-l}{{\sigma }_s}\right)& \left[\mathrm{Expression}12\right]\end{array}$
(Procedure for Pattern Search Applied with Image Data Reduction Ratio)

[0274] Next, a specific procedure for a pattern search in image processing by use of the image data reduction ratio is described based on flowcharts of FIGS. 62 and 63. In these drawings, FIG. 62 shows an operation upon registration, and FIG. 63 shows an operation during motion.

(Operation Upon Registration Applied with Image Data Reduction Ratio)

[0275] First, the operation upon registration is described based on FIG. 62. In Step S6201, the pattern model for coarse search is created. Next, in Step S6202, the edge extraction is performed by use of the unmagnified image, to find a standard deviation σs with respect to each of the extracted edge points. In finding the standard deviation σs, the shape of the edge actually extracted from the image data is assumed to be approximate to the model of FIG. 61. For calculation of the sub-pixel position of each edge at an edge point having a edge strength not smaller than a predetermined edge strength threshold, the next expression as an approximate expression of a quadric derivative of a logarithmic edge strength is employed by use of edge strengths EMb, EMc, EMf of three adjacent points B, C, F shown in FIG. 64:
t=(ln(EMf)+ln(EMb)−2 ln(EMc))*(cos(EAc)²)  [Expression 13]

[0276] Using “t” in the above expression, the standard deviation σs can be calculated from the following expression:
σ_s=1.8263*t^(−0.35661)−1.07197  [Expression 14]
What is important is that the standard deviation σs is expressible by a single-valued function, and the above expression does not have a particular meaning.

[0277] Meanwhile, in Step S6203, the edges extracted from the image data are chained and segmented by the chain creating device 63 and the segment creating device 68, to create a tentative pattern model. Further, in Step S6204, an average value σa is computed which uses only σs of each edge used upon creating this temporary pattern model. Next, in Step S6205, using this advantage value σa, an image data reduction ratio “r” is found by the following expression. This is the fine-positioning reduction ratio.

[0278] $\begin{array}{cc}r=\frac{{\sigma }_a}{0.6}& \left[\mathrm{Expression}15\right]\end{array}$

[0279] In this example, a difference value of a logarithm of the edge strength is obtained, and from this difference value, the reduction ratio is calculated. However, this example is not restrictive, and a variety of approximate values concerning a differential value of the logarithm of the edge strength can also be used to compute the image data reduction ratio. Further, the appropriate value referred hereto includes an approximate value of the differential value of the edge strength.

[0280] As thus described, when the image data reduction ratio “r” is obtained, the registered image is newly reduced in accordance with the fine-positioning reduction ratio in Step S6206. Further, the pattern model for fine positioning is created from the reduced registered image in Step S6207.

(Operation During Motion Applied with Image Data Reduction Ratio)

[0281] Next, an operation performed during motion in response to the registration operation by use of the image data reduction ratio is described based on FIG. 63. First, in Step S6301, using the above obtained fine-positioning reduction ratio, the image to be searched is reduced into the reduced image to be searched for fine positioning. Meanwhile, as Step S6302, the reduced image for coarse search is created from the image to be searched, and in Step S6303, the position and posture of the detection candidate are calculated by use of the pattern model for coarse search and the reduced image for coarse search. Finally, in Step S6304, the fine positioning is executed by use of the pattern model for fine positioning, the reduced image to be searched for fine positioning, and the position and posture of the detection candidate.

(Pre-Processing/Post-Processing of Image Reduction)

[0282] Even after the reduction in image data, image data is reduced so as to hold information on edge position as much as possible. Specifically, after application of a low-pass filter corresponding to the image data reduction ratio, a sub-sampling is performed. The edge extraction is performed on the image data after the sub sampling so that the accurate information on the edge position can be obtained.

[0283] In such a manner as above, it is possible to suppress deterioration in accuracy that occurs due to unclearness of the original image, such as blurring. Further, reducing the image data to decrease the data amount can give a side benefit of allowing subsequent processing to be performed at high speed with a light load.

[0284] In the present embodiment, the fine-positioning reduction ratio is automatically set to the reduction ratio the upper limit of which is the final medium reduction ratio (first reduction ratio) used lastly in the “local search”. Further, the pattern model for use in the fine positioning is created from the registered image reduced so as to have the same reduction ratio as the fine-positioning reduction ratio. As thus described, the fine-positioning reduction ratio is decided based on the sharpness of the edge of the edge image of the original size in the range from the original size of the image to the final medium reduction ratio used lastly in the local search.

[0285] As thus described, the fine-positioning reduction ratio is adjusted to hold the sharpness at the level not lower than a fixed level, and the reduction ratio can thus be used in the state of the sharpness being high, so that the stability of the positioning accuracy can be ensured.

(Operation Upon Registration of Pattern Model)

[0286] Again returning to the description of the registration operation of the pattern model, a procedure for registering the pattern model for fine positioning is described based on a flowchart of FIG. 14. The pattern model for fine positioning is created by use of the same image as the registered image described in the above description of the pattern model for coarse search. First, in Step S1401, in advance of the processing by the image reducing device 77, the edge image of the original size with respect to the registered image is created by the contour extracting device 62, and the sharpness of the edge is evaluated. Based on this, the optimal reduction ratio is decided in Step S1402. As thus described, in Step S1403, the image is sought to be reduced by the image reducing device 77 based on the optimal fine-positioning reduction ratio decided with respect to the registered image. Further, with respect to the image reduced with the reduction ratio (including a reduction ratio of one) decided by the image reducing device 77, the edge is segmented by the contour extracting device 62, the chain creating device 63 and the segment creating device 68 (Step S1404, Step S1405). Specifically, on the reduced image, the edge extracting processing of extracting the edge and the chaining processing of creating the chain from the edge points are performed, and segmentation for coupling the chains are further performed. Next, the pattern model constituting device 70 creates the pattern model for fine positioning with the decided fine-positioning reduction ratio by use of data segmented by the segment creating device 68 (Step S1406).

[0287] Further, as does the foregoing pattern model for coarse search, the pattern model for fine positioning decides the reference point on each segment present inside the edge image data based on a pre-set condition (Step S1407). Moreover, the angle is set with respect to each reference point (Step S1408). The angle is set in the direction of the normal to the segment as well as the orientation of the edge. Furthermore set are the kind of segment (kind of segment such as a line or a circular arc) where the reference point is provided, a parameter representing the segment (parameter capable of defining the segment made up of a line or a circular arc), an angle in the direction of the normal to the segment and in the orientation close to the edge angle, and line segment information having a length pre-set in the direction of the normal to the segment, namely a corresponding point search line (Step S1409).

(Line Length of Corresponding Point Search Line)

[0288] As for a line length of the corresponding point search line given with respect to each reference point, the same length to each reference point is set. The length is decided by means of a ratio between the final medium reduction ratio used lastly in the local search and the fine-positioning reduction ratio for use in the fine positioning. In other words, it is set that the line length is large when the ratio between the final medium reduction ratio and the fine-positioning reduction ratio is large, and the line length is small when the ratio is small.

[0289] For example, when the final medium reduction ratio used lastly in the local search is one-fourth of the original size of the image and the fine-positioning reduction ratio is unmagnification, the ratio between the final medium reduction ratio and the fine-positioning reduction ratio is four times, and hence one pixel in the local search corresponds to four pixels in the fine positioning. Therefore, the length of the line in the pattern model for fine positioning is set to a length covering each of four pixels in the positive and negative directions of the edge from the reference point. However, since the length of this line has an effect on the positioning accuracy and the search time, covering a total number of corresponding pixels by the ratio of the reduction ratios is not necessarily required. For example, the line length of the corresponding point search line is set short in accordance with the processing time required. Otherwise, on the contrary, the line length may be set not to be smaller than the corresponding number of pixels. For example, a margin can be set to the line length in accordance with the ratio of the reduction ratios, to seek the stability of the processing.

(Change in Line Length of Corresponding Point Search Line)

[0290] Further, the length of the corresponding point search line can be set not uniform forward and backward with respect to the reference point, and can be changed such that one line length is set longer or shorter. This processing is performed by the pattern model constituting device 70 or the like. An example of changing the length of the corresponding point search line is described based on FIGS. 27 and 28. In these drawings, FIG. 27 shows the case of the lengths from the reference points being the same, and FIG. 28 shows the lengths from the reference point being different. It is to be noted that in these drawings, the corresponding point search lines generated in an inner rectangular region in these drawings have been filtered. As shown in FIG. 27, when the lengths of the corresponding point search lines extended from the reference point are made constant in the forward/backward and right/left directions, the lines overlap the inner rectangular shape, which might cause erroneous determination. Therefore, when the corresponding point search lines are not extended in the inward direction, but are set only in the outward direction as in FIG. 28, more accurate search result with less erroneous determination can be expected.

(Setting Intervals of Corresponding Point Search Line)

[0291] The corresponding point search line is set on the segment excluding its end portion. This is because such an end portion is greatly influenced upon displacement. Therefore, stable processing can be expected by setting the corresponding point search line while excluding the portion greatly influenced upon displacement.

[0292] Intervals for and the number of corresponding point search lines for the setting thereof are decided in accordance with the required processing speed and accuracy of the pattern search. It is possible to keep the accuracy of the pattern search by setting such that at least one corresponding point search line is arranged on each line or circular arc constituting the segment. Most simply, one reference point is arranged at the center of the segment, and from that point, reference points are set at equal intervals on the segment. Further, the setting of the reference point is thinned out in a portion with a blurred edge angle inside the segment, and the reference points are thickly set in a reliably detected portion, and thereby, the accuracy can be enhanced.

[0293] Moreover, it is preferable to allocate at least one corresponding point search line to the center of the segment. This ensures setting of at least one corresponding point search line, even being short, with respect to the segment constituting part of the pattern model.

(Pre-Processing on Image to be Searched During Motion)

[0294] In the above, the operation upon registration of the pattern model, namely the creation of the pattern models for coarse search and the fine positioning was described (FIGS. 3, 12). During motion, a search is performed by use of these patterns (FIG. 4). In the search, a predetermined pre-processing is performed on an image to be searched inputted from the image pickup device. A procedure for performing the pre-processing on the image to be searched in the search during motion is described based on a flowchart of FIG. 15.

[0295] First, in Step S1501, based on the inputted image to be searched, the image reducing device 77 creates a reduced image by use of the medium reduction ratio for first pattern model for coarse search (first reduction ratio) which was used in the registered image upon registration.

[0296] Meanwhile, in Step S1502, the edge angle/edge strength image creating device 60 of the contour extracting device 62 creates an edge angle image and an edge strength image. Further, the thinning device 61 creates a thinned edge angle image based on these edge angle image and edge strength image.

[0297] Next, in Step S1503, the edge angle bit image creating device 69 is created by the contour extracting device 62, and based on the thinned edge strength image, an edge angle bit image corresponding to the medium reduction ratio of the first pattern model for coarse search is created. Needless to say, the edge angle bit image thus created is applied to the “local search” by use of the first pattern model for coarse search in the search operation.

[0298] Further, in Step S1504, the edge angle bit image reducing device 78 creates an edge angle bit reduced image corresponding to the reduction ratio for large area for the second pattern model for “large-area search” based on the edge angle bit image created by the edge angle bit image creating device 69.

[0299] It is to be noted that, as described in the description of the setting of the medium reduction ratio of coarse search, in the case of creating the additional pattern model based on the additional medium reduction ratio between the firstly set medium reduction ratio and the reduction ratio for large area, also in this pre-processing, as arbitrary Step S1505, an edge angle bit reduced image corresponding to the medium reduction ratio of the additional pattern model is created by the edge angle bit image reducing device 78 based on the edge angle bit image created by the edge angle bit image creating device 69.

[0300] Additionally, in the foregoing pre-processing during motion, the processing is performed on the image to be searched in the reverse order to the order of the large-area search and the local search as the coarse search, as well as the fine positioning, which are performed during motion (see FIGS. 8A to 8C), but the order of creating the pattern model is not particularly restricted, and it goes without saying that the pattern model for coarse search may be created after creation of the pattern model for fine positioning. Meanwhile, during motion, the coarse search is performed by use of an image having a high reduction ratio, and the reduction ratio is gradually lowered to perform the fine search on an image of a size close to the original size.

[0301] As thus described, after completion of the pre-processing during motion, the large-area search and the local search as the coarse search are performed using the created edge angle bit reduced image, edge angle bit image, and the like, and after the coordinate of the detection candidate is found, the fine positioning is performed (FIG. 9).

(Details of Each Operation Upon Registration)

[0302] In the above, the schemes of the operations upon registration and during motion were described. Next, the image processing operation upon registration is detailed. Upon registration, the edge angle/edge strength image creating device 60 applies the Sobel filter to the registered image, and finds the edge strength and the edge angle at each point constituting the registered image, to compute edge information including the edge strength, the edge angle and the edge position. The thinning processing is performed based on the edge information, to find the edge point. As a specific example of the thinning processing, the edge-strength non-maximal point suppressing processing can be used. The edge is thinned to have a line shape with a width of one pixel.

[0303] It is to be noted that the edge point can also be found by means of the accuracy of the sub-pixel position. For example, the sub-pixel position can be computed through use of quadric interpolation (e.g. see Japanese Unexamined Patent Publication No. H07-128017).

[0304] Further, the obtained edge points are coupled to create a continuous chain. The edge chaining device 64 performs edge coupling processing of coupling adjacent edge points with edge angles thereof almost in the same direction, to create a continuous line element (chain). The chain thus obtained also has an xy sub-pixel coordinate. Each chain is aggregation of the edge points, and each of the individual chains is provided with a chain index as an identifier for distinction among each chain.

[0305] Further, the chains are subjected to approximation by the edge chain segmenting device 65, to create a segment. The segment is found by fitting where the chains are approximated by a line and a circular arc through use of the least squares method. In the fitting, the approximation is first performed by the line, and when an error of the approximation by the line exceeds a predetermined threshold, the fitting is switched to one by the circular arc. When the error does not decrease even by the approximation by the circular arc, a result of the fitting by the line is used. In such a manner, the operation of sequentially performing the fitting in the combination of the line and the circular arc is repeated, and at the time point when the error of the fitting result exceeds the threshold, if the data obtained up to then is sufficiently long, it is regarded as the segment as a continuous line. Since the edge point is found in the sub-pixel position, the segment can also be obtained in a highly accurate position in the sub-pixel order.

[0306] The segment is created by approximating the chains by the line and the circular arc. The line segment can be expressed by an expression representing a straight line (e.g. ax+by+c=0), coordinates of end points, and the like. Meanwhile, the circular-arc segment can be expressed by a coordinate of the center, a radius, a start angle, an end angle, and the like. For example, a center coordinate (xo, yo) of a circular arc and a radius ro in “(x−xo)2+(y−yo)2=ro2” express the circular arc segment. At each of the segments created in such a manner, the reference points are set with predetermined intervals.

[0307] It should be noted that, although the example of the approximation by means of the line or the circular arc as the segment was described, this is not restrictive, and a cone curve, a spline curve, a Bezier curve, and the like can also be used as appropriate. Thereby, with a fixed geometric shape such as a circular shape, an oval shape, a triangle shape or a rectangular shape regarded as a reference, a pattern model can be created using these shapes singly or in combination, thereby to facilitate creation of the pattern search and each of subsequent processing.

(Reduction of Pattern Model)

[0308] Further, the pattern model is reduced during motion in the search. This reduction ratio is a reduction ratio for reducing the image to be searched for coarse search during motion that is described later. Since this reduction processing is to be performed, intervals are set among the reference points as the model edge points of the pattern model so as to prevent the reference points from designating the same coordinate as a result of the reduction processing. Consequently, the pattern model of FIG. 16 changes to one as in FIG. 17.

(Difference Between Pattern Model for Coarse Search and Pattern Model for Fine Positioning)

[0309] The pattern model for coarse search and the pattern model for fine positioning are separately created from the registered image of the original size (or its reduce image). In other words, the segment of the pattern model for coarse search is not created from the segment of the pattern model for fine positioning, and the segments of both models do not necessarily match. Further, since the size of the pattern model differs between the pattern model for coarse search and the pattern model for fine positioning, a distance among each reference point also differs therebetween. The difference in distance, obtained by transforming the distance among each reference point by unmagnification, depends upon the reduction ratio.

[0310] Further, in the pattern model for coarse search, the coordinate of the reference point and the orientation of the edge at the reference point (angle information) are given. In other words, the angle is set to be close to the orientation of the edge in the direction of the normal to a segment not having information on length of a corresponding point search line. In the coarse search by use of this pattern model for coarse search, the pattern model is placed on the image to be searched, and it is checked whether the edge is present at the positions of the reference points and whether the orientation of the edge matches the orientation of the pattern model.

[0311] On the other hand, in addition to the coordinate of the reference point and the orientation of the edge at the reference point in the pattern model for coarse search, the pattern model for fine positioning has a corresponding point search line passing through the reference point and having a predetermined length extending in a direction substantially orthogonal to the segment (i.e. one defining the length of the normal to the segment), and the kind of segment (e.g. attribute such as the line or the circular arc). This difference corresponds to contents of processing of each search. Namely, in the fine positioning, an edge that corresponds within the range of the corresponding point search line is searched. In such a manner, the pattern model for fine positioning functions as a corresponding edge point selecting device for selecting a corresponding edge point corresponding to the reference point.

[0312] It is to be noted that in the extraction of the contour, the segment is not necessarily required to be created. The corresponding point search line can be set not from the segment but directly from the chain. For example, in the case of setting three reference points with respect to a certain contour, three edge points that constitute the chain corresponding to the contour are set with equal intervals, to set the corresponding point search lines in the respective normal directions. With this method, high-speed processing can be expected since no segment is created, whereas the accuracy slightly deteriorates since the chain is not approximated by the straight line or the circular arc. Especially, the chain is formed by simply coupling the edge points and hence it may have poor linearity, whereas the segment is appropriated by the straight line or the circular arc so that a more accurate computing result is obtained and the position accuracy is also stabilized.

(Details of Coarse Search During Motion)

[0313] Next described is an operation during motion for actually searching the matching portion out of the image to be searched by use of the pattern model registered in such a manner as above. First, details of a procedure for obtaining a coarse position and posture in the coarse search are described based on a flowchart of FIG. 18. In the present embodiment, the coarse search divided into the large-area search and the local search, and performed, to find the detection candidate.

(Step S1801—Reduction in Image to be Searched)

[0314] First, in Step S1801, the image to be searched as the object to be searched is reduced in line with the reduction ratio of the registered image. For example, an image to be searched shown in FIG. 19A is reduced into the same magnification as that of the registered image, to obtain a reduced image to be searched shown in FIG. 19B. First, the image is reduced into the medium reduction ratio as the ratio for coarse search. In other words, the reduction ratio is not first reduced into the reduction ratio for large area which is a large reduction ratio, but first reduced into the medium reduction ratio which is a small reduction ratio.

(Step S1802—Acquirement of Edge Angle Image and Edge Strength Image)

[0315] Next, in Step S1802, the edge strength image and the edge angle image are separately obtained from the reduced image to be searched by an edge calculation device. As the edge calculating method, Sobel filtering or the like can be used.

[0316] The Sobel method is described. In the Sobel method, a matrix of 3×3 is used as an operator (kernel). This method extracts as a pixel value of the central point a value obtained by multiplying pixel values (e.g. luminance) by a coefficient with respect to peripheral points with the target point set at the center and adding up the multiplied values. This method is a horizontal and vertical filter, and has a characteristic of being resistant to noise since including a smoothing operation. The kernel for use in the Sobel filter is shown below.

[0317] $\begin{array}{cc}\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\begin{array}{ccc}-1& -2& -1\\ 0& 0& 0\\ 1& 2& 1\end{array}& \left[\mathrm{Expression}16\right]\end{array}$

[0318] As a result of this, the edge strength image and the edge angle image of the image to be searched are independently obtained.

(Step S1803—Creation of Edge Angle Bit Image of Image to be Searched)

[0319] Further, in Step S1803, the edge angle bit image is created by the edge angle bit image creating device 69 from the edge angle image and the edge strength image. The edge angle bit image is image data expressing as angle bit the edge angle of each point constituting the edge angle image. As a result of this, the edge angle bit image is obtained. Transformation from the edge angle image into the edge angle bit image is described later.

(Step S1804—Reduction in Edge Angle Bit Image)

[0320] Further, in Step S1804, the obtained edge angle bit image is reduced by the edge angle bit image reducing device 78. The reduction ratio is set to the reduction ratio for large area in the case of creating the second pattern model for large-area search, and to the medium reduction ratio in the case of creating the first pattern model for local search. As a result of this, the reduced image of the edge angle bit image is obtained.

(Step S1805—Execution of Large-Area Search)

[0321] Next, the large-area search is executed on the edge angle bit reduced image, reduced in Step S1804, by use of a pre-reduced pattern model. Specifically, the search is performed in the whole range, while the angle of the pattern model is changed, so as to scan the image from the upper left to the lower right. Thereby, the region of the detection candidate is extracted. The position and posture of the detection candidate are expressed, for example, by the XY coordinate and the angle θ or the like, respectively. The detection candidate is found by score calculation. The reduced pattern model is moved by the coarse searching device 71 in the degree of freedom of the search position and posture, and a score is calculated in each position and posture.

(Score Calculation)

[0322] The score calculation in the large-area search is performed by comparing the edge angle images at the respective edge points included in the pattern model and the edge angle bit image, obtained by reducing the image to be searched into the reduction ratio for large area, to calculate a coincidence. Upon performing the search, the data on the position and angle of the reference point are changed in line with the position and the posture the score in which the score is to be calculated. Subsequently, the angle is transformed as in the edge angle bit image, and AND processing is performed on a pixel value of the edge angle bit image data after the reduction. A value obtained by dividing a total value of the number of remaining bits by a maximal value of an expected total value is regarded as the coincidence, which is computed by the coarse searching device 71. Further, a plurality of bits can be allocated in the angle direction, to add a concept of weighting.

(Step S1806—Execution of Local Search)

[0323] Moreover, the local search is performed on the region of the detection candidate found in the large-area search. In the local search, the pattern model for local search with its reduction ratio made lower than that of the pattern model for large-area search is used. Furthermore, also as the edge angle bit image as the image to be searched, the reduced image, reduced by the reduction ratio for local search that is lower than the reduction ratio for large area, is used.

[0324] Further, upon performing the local search, not only the region of the detection candidate found in the large-area search is used as it is, but the local search may also be performed in the vicinity thereof, for example, on peripheral pixels such as 3×3 pixels and 5×5 pixels. Thereby a stable search result can be expected.

(Expansion Processing)

[0325] Namely, in order to stabilize the result of the score calculation, enlargement processing can also be performed upon performing the coarse search. There normally appears a tendency that, when the reduction ratio of the image to be searched decreases to increase the accuracy, even slight positional displacement causes a large decrease in score. A rotational angle may be minutely change for avoiding a rapid change in score, but in this case, the disadvantage of increasing a processing amount occurs. Therefore, in consideration of the balance between reduction in processing amount and improvement in accuracy, the edge angle bit image as the image to be searched is enlarged only by a predetermined amount. For example, the image is enlarged in the XY direction thereof by a predetermined number of pixels, for example, 2×2 pixels obtained by doubling one pixel. It is thereby possible to suppress rapid fluctuations of the score value due to slight displacement of the angle, so as to obtain a stable score.

[0326] In such a manner, the coarse position in the reduced image to be searched of the reduced pattern model is decided based on the calculated score. Further, as appropriate, the above step can be repeated, so as to enhance the accuracy of the coarse position. Namely, not only the coarse search is simply divided into twice, the large-area search and the local search, but the local search can be divided into a plurality of times, and a larger reduced image to be searched can be used by gradually lowering the reduction ratio of the image to be searched, so as to perform highly accurate positioning.

[0327] It is to be noted that, due to its wide range and large processing amount, the large-area search is normally performed only once. However, it can be performed a plurality of times in accordance with required accuracy or tact time. Further, as for the search technique, a known search technique can be used, such as edge search, normalized correlation search, generalized Hough transform or geometric hashing.

(Details of Fine Positioning During Motion)

[0328] After the coarse search is performed in such a manner as above and data on the position and posture of the detection candidate where the pattern model is present are found, the fine positioning is performed by the fine positioning device 76. Next, a specific procedure for the fine positioning is detailed based on a flowchart of FIG. 20.

[0329] First, in Step S2001, the pattern model for the fine positioning is superimposed on the image to be searched based on the position and posture of the detection candidate found in the coarse search. It is preferable to use the image to be searched of the original size and the pattern model for fine positioning while the position and posture finally found in the coarse search are regarded as a starting position and a starting posture. However, the fine positioning can also be performed with a reduction ratio higher than the original size (reduction ratio of one) and lower than the reduction ratio used lastly in the coarse search.

[0330] Further, in Step S2002, the point as the corresponding edge point is found along the corresponding point search line of the pattern model for fine positioning. As described above, the corresponding point search line has a predetermined length and extends in the direction of the normal to the segment, and a starting point as one of both ends of the line segment is regarded as a search starting point and an end point is regarded as a search end point. First, edge calculation is performed along the corresponding point search line, to acquire an edge vector. As a technique for the edge calculation, as described above, the Sobel filter can be used as appropriate. The edge vector obtained by this edge calculation, the edge angle, edge strength, edge position and the like of each point on the corresponding point search line are found. It is to be noted that the edge vector is one expressing the edge strength and orientation by the vector, and can be expressed like (Ex, Ey). For example, as shown in FIG. 46, when the edge strength is EM and the edge angle is θE, these are expressed by: the edge angle θE=A tan(Ey/Ex); and the edge strength EM=sqrt(Ex2+Ey2).

(Corresponding Edge Point Search Processing)

[0331] Further, based on the information on the edge vector, edge angle, edge position, and the like, the corresponding edge point corresponding to the segment that includes the reference point of the corresponding point search line is found. As an example of the method for deciding a corresponding edge point, the corresponding edge point can be decided at high speed by use of the foregoing edge vector. As another method, the calculation can be performed by use of the edge strength and the edge angle as described below, but in this case, A tan needs to be calculated described below, the computing becomes complicated. In the following described is a procedure for obtaining a corresponding edge point by use of an edge strength and an edge angle.

[0332] First, a maximal point, which has an edge strength larger than a predetermined edge strength threshold and at which an absolute value of a difference between the edge angle and the angle of the reference point is smaller than a predetermined edge angle threshold, is taken as a candidate of the corresponding edge point. Further, the closest point to the reference point among the corresponding-edge-point candidates is finally regarded as the corresponding edge point.

[0333] Further, the sub-pixel position of the edge of the corresponding edge point is found (Step S2003). Using that position and geometric data of the segment, the error value is obtained, and the calculation of the least squares method is performed (Step S2004), to obtain a fine position (Step S2005). Examples of the error value in the case of the line segment include a distance between the corresponding edge point and the straight line, and examples of the error value in the case of the circular arc segment include an absolute value of the difference between the radius and a distance between the corresponding edge point and the central position.

[0334] As thus described, the error value or the weight value for use in the calculation of the least squares method is calculated by the fine positioning device 76, and from the calculated value, simultaneous equations obtained by the least squares method are acquired. The least squares method is adopted such that the segment takes an ideal shape and the error of a plurality of corresponding points corresponding to the segment are minimized. Further, the simultaneous equations are solved, to find a highly accurate position and posture. In such a manner, a corrected amount Δx of a position X, a corrected amount Δy of a position Y, a corrected amount Δθ of the angle θ, a corrected amount Δs (s: scale) of a scale “s” are obtained.

[0335] In the fine positioning, the reference point is superimposed on the image to be searched by use of the data on the position and posture obtained in the coarse search. Then, the edge calculation such as sobel filtering is performed along the corresponding point search line, to acquire the edge vector. It is to be noted that the edge vector is represented by a result in application of the sobel filter, and can be expressed by (Sx, Sy), or the like. Further, the edge strength EM can be expressed by “EM=√(Sx2+Sy2)”, and the edge angle θE can be expressed as “θE=A tan(Sy/Sx)”, or the like. Moreover, from the edge vector, the edge angle, the edge strength and the position of the pixel at the corresponding edge point are obtained. From these edge vector, edge angle, edge strength and position, the corresponding edge point corresponding to the segment including the reference point of the corresponding edge point is found by the fine positioning device 76.

[0336] This state is described based on FIG. 21A. First, the pattern model PM shown by a thick solid line is superimposed and arranged by the fine positioning device 76 in the position of the detection candidate of the image to be searched (edge angle bit reduced image EABR shown by a broken line) obtained in the coarse search. Then, along a corresponding point search line TL that passes through a reference point KT set on the pattern model and is almost vertical to the segment of the pattern model, a corresponding edge point TT corresponding to the reference point KT is found. In FIG. 21A, the corresponding point search line TL is shown by a thin solid line. It is to be noted that the corresponding point search line TL is an imaginarily set line, and is not actually drawn. The corresponding edge point TT becomes an intersection point of the corresponding point search line TL and the reduced image EABR. With the corresponding edge point TT, the sub-pixel coordinate position can be obtained. Using this position and geometric data of the segment, fine positioning is performed by the fine positioning device 76.

[0337] Specifically, with the relation between the geometric data (line in this case) of the segment and the corresponding edge point regarded as an evaluation value, the score calculation is performed so as to minimize or maximize an accumulated value of the evaluation values. As the evaluation value, a distance can be typically used, and with this distance regarded as the error value, the calculation of the least squares method is performed so as to minimize the error value, whereby the fine position can be obtained. As the distance used can be a Euclidean distance between the segment and the corresponding edge point. Namely, in the case of the segment being the line, the distance between the corresponding edge point and the straight line is used, and in the case of the segment being the circular arc, the absolute value of the difference between the radius and the distance between the corresponding edge point and the central position. Solving the simultaneous equations obtained by a solution using the means of the least squares method can find a highly accurate position and posture. Further, the evaluation value is not restricted to the distance, and may be an angle formed by the reference point and the corresponding edge point of the reference point.

[0338] Further, FIG. 21B shows a state of corresponding edge point search processing in which the fine positioning device 76 finds the corresponding edge point. In this drawing, as in FIG. 21A, a broken line shows the reduced image EABR of the image to be searched, a thick solid line shows the pattern model PM, and a thin solid line shows the corresponding point search line TL set on the reference point KT. Found in this case is a coordinate position x, y in application of the Sobel filter in a region SR of 3×3 pixels of the reduced image EABR. The central coordinate in this calculation is found by use of Bresenham's algorithm for creating straight-line data. In the example of FIG. 21B, a pixel B is extracted as the corresponding edge point with respect to a model edge point A.

[0339] The method shown in FIG. 21B differs from Japanese Patent No. 3759983 described above in that a point, appropriately selected on the segment where the corresponding edge point was automatically extracted, is regarded as the reference point. Especially in Japanese Patent No. 3759983, an arrangement method for a seek-line is not defined. Further, upon decision of the corresponding edge point, data on the edge angle, the edge position and the like are used besides the edge strength, thereby to improve the reliability of the corresponding edge point. Additionally, the kernel used in the processing of obtaining an edge angle and an edge strength is made more compact, to lower a load of computing processing. Further, the position of the corresponding edge point can be obtained with sub-pixel accuracy. Moreover, the use of the least squares method can give the advantage of being capable of corresponding to models in a variety of shapes.

[0340] In such a manner as above, it is possible to perform highly accurate high-speed positioning in the pattern search. Especially in this method, by changing the line length of the corresponding point search line, the range for searching the corresponding edge point can be easily changed by means of the corresponding point search line, so that the advantage of being capable of adjusting the stability required. Namely, by gradually reducing the length of the corresponding point search line upon repeated application of the least squares method, positioning with higher accuracy at higher speed can be easily realized.

[0341] Additionally, since the pattern model is expressed by the segment, a corrugated phenomenon of an edge position as shown in FIG. 22 can be eliminated. Namely, in the case of performing the fine positioning between points, large positional displacement may occur between pairing with a point in a higher wave and pairing with a point in a lower wave, but such an influence can be reduced.

[0342] Further, in place of this or in addition to this, the edge angle threshold may be changed in each repetition of the least squares method. Namely, gradually reducing the edge angle threshold in accordance with the repeated number of the least squares method also allows realization of more stable positioning.

[0343] It is to be noted that upon superimposing the pattern model on the image to be searched based on the initial position obtained in the coarse search or the fine-positioning start position obtained in another coarse search, unprocessed data, so-called original image data, is used as the image to be searched, and a pattern model corresponding to the original image data is used as the pattern model.

[0344] This method can eliminate the need for transforming all pixels in the original image data of the image to be searched into edge image data, so as to seek speeding up of the processing. Especially, in inline processing where the tact time is required, such high-speed low-load processing is preferred. It goes without saying that, when overall pre-extraction of the edge data is more efficient, all points in the image to be searched can be transformed into edge image data to perform the pattern search.

[0345] Further, superimposing and arranging the whole of the pattern model on the image to be searched is not necessary, but superimposing and arranging at least the corresponding point search line suffices. In particular, since the corresponding point search line is the straight line, it can be readily obtained by computing. Therefore, in the present specification, the term “superimpose” does not necessarily means to actually superimpose an image, but is used to mean processing of deciding the corresponding edge point in accordance with the corresponding point search line. Further, the phrase “superimpose and arrange” in this case is intended to describe that the corresponding position of each image is made easy to grasp by superimposition thereof as described above, which is merely imaginary in calculation and, needless to say, the operation of actually superimposing data is not necessary.

[0346] According to this method, a highly accurate edge-base search can be realized as compared with the conventional method. In the foregoing technique of Japanese Patent No. 3759983, the direction and angle component of the edge are not considered but only a pre-defined edge direction is viewed, and hence the stability in a complicated shape cannot be expected. As opposed to this, in the technique according to the present embodiment, importance is attached to the edge direction, thereby allowing enhancement of the reliability of the corresponding edge point. Further, in the present embodiment, since a difference is calculated by use of a small filter of the kernel, such as the Sobel filter, even when the work is long and narrow, the edge can be detected. As thus described, it is possible to realize a stable edge-based search adaptable to an object to be searched in complicated shape as compared with the technique of Japanese Patent No. 3759983.

[0347] Further, upon obtaining the position of the detection candidate in the image to be searched of the pattern model, namely the initial position in the local search, there is the advantage of performing a high-speed low-load pattern search by reducing the image to be searched and performing the search. However, since part of information might be lost due to the reduction to cause deterioration in accuracy, it is desirable to perform the reduction so as to hold an information amount (detailed later). Moreover, besides the form of obtaining the initial position of the pattern model in the coarse search, the position can be manually specified by the user.

[0348] The point mentioned in the above example means the point constituting the image to be searched or the registered image, namely one pixel, but it goes without saying that a plurality of pixels (e.g. four pixels) can be lumped together as one point. Therefore, in the present specification, the point means one pixel or a predetermined number of pixels.

[0349] Further, the phrase “based on the reference point” is used not only in the meaning of the edge detection being performed on the reference point, but also in the meaning including the edge detection being performed in the neighborhood of the reference point. For example, the edge detection is performed within a designated range, such as a range from one to ten pixels around the reference point.

[0350] Further, the segment refers to a continuous line with finite length configured of the line and/or the circular arc or the combination thereof. Moreover, the cone curve, the spline curve, the Bezier curve, and the like can be combined in addition to the line and the circular arc. Furthermore, data of the corresponding point search line includes the coordinate of the reference point, and the angle and length of the corresponding point search line.

(Least Squares Method)

[0351] In the least squares method, a straight line error function is adapted to the line segment. The straight line error function is a least squares method with the distance between a point and a straight line regarded as an error function. Further, a circular arc error function is adapted to the circular arc segment. The circular arc error function is a least squares method with a distance between a point and a circular arc regarded as an error function. This is to be detailed later.

[0352] Examples of the problem of the least squares method include that, when even one quite different value is present, the accuracy extremely deteriorates due to the influence of this point. Therefore, in the present technique, a weighted least squares method, made to have a weight value so as to lower weighting on such a point, is used to suppress the influence.

[0353] Further, as a degree of freedom to be used in the least squares method, a movement in the X direction, a movement in the Y direction, rotation, enlargement/reduction, skew, aspect, and the like can be employed. Selecting these can also correspond to rotation, enlargement/reduction, distortion and the like of the registered image besides the parallel movements in the XY directions.

(Generalization of Error Function of Least Squares Method)

[0354] The error function of the least squares method is generalized and developed. First, it is considered that an error function E (po, p1, . . . , pn) is decided by an affine parameter po, p1, . . . pn (e.g. p0=x, p1=y, etc.). It is assumed that the error function E (po, p1, . . . , pn) is minimized by an optimal affine parameter poo, p1o, . . . pno) (o: optimized). At this time, the error function E (po, p1, . . . , pn) is expressed by the following expression:

[0355] $\begin{array}{cc}E\left(p_0,p_1,\dots ,p_n\right)=\sum _i{\omega }_i{e_i\left(p_0,p_1,\dots ,p_n\right)}^2& \left[\mathrm{Expression}17\right]\end{array}$

[0356] The meanings of the parameters in the following expression are as follows.

• [0357] i: index of a corresponding edge point
• [0358] ωi: weight decided in accordance with positional relation between corresponding edge point and model. For example, when the point-line distance between the corresponding edge point and the line is long, this parameter is defined to come close to zero.
• [0359] e (p0, p1, . . . , pn): individual error functions decided by geometric distance between corresponding edge point and model. This parameter is decided by the point-line distance between the corresponding edge point and the line segment, or the like.

[0360] p0 to pn: affine parameters of parallel x-movement amount, parallel y-movement amount, rotational angle, scale value, or the like.

[0361] In order to find the affine parameters poo, p1o, . . . pno that minimize the error function E (po, p1, . . . , pn), displacement amounts are found as follows from affine parameters p0t, p1t, . . . pnt that are expected to be sufficiently close to the affine parameters to be found and were obtained in the coarse search or the last fine positioning:
Δp₀, Δp₁, . . . , Δp_n
(p_i0≈p_it+Δp_i)
(t:trial)  [Expression 18]

[0362] Δp0, Δp1, . . . , Δpn are obtained by solving the following simultaneous equations:

[0363] $\begin{array}{cc}[\begin{array}{c}\sum _i{\omega }_i\frac{\partial e_i}{\partial p_0}\frac{\partial e_i}{\partial p_0}\sum _i{\omega }_i\frac{\partial e_i}{\partial p_0}\frac{\partial e_i}{\partial p_1}\dots \sum _i{\omega }_i\frac{\partial e_i}{\partial p_0}\frac{\partial e_i}{\partial p_n}\\ \sum _i{\omega }_i\frac{\partial e_i}{\partial p_1}\frac{\partial e_i}{\partial p_0}\sum _i{\omega }_i\frac{\partial e_i}{\partial p_1}\frac{\partial e_i}{\partial p_1}\dots \sum _i{\omega }_i\frac{\partial e_i}{\partial p_1}\frac{\partial e_i}{\partial p_n}\\ \dots \\ \sum _i{\omega }_i\frac{\partial e_i}{\partial p_n}\frac{\partial e_i}{\partial p_0}\sum _i{\omega }_i\frac{\partial e_i}{\partial p_n}\frac{\partial e_i}{\partial p_1}\dots \sum _i{\omega }_i\frac{\partial e_i}{\partial p_n}\frac{\partial e_i}{\partial p_n}\end{array}]\hspace{1em}[\begin{array}{c}\Delta p_0\\ \\ \Delta p_1\\ \\ \\ \Delta p_n\end{array}]=\left[\begin{array}{c}-\sum _i{\omega }_i{e}_i\frac{\partial e_i}{\partial p_0}\\ -\sum _i{\omega }_i{e}_i\frac{\partial e_i}{\partial p_1}\\ \dots \\ -\sum _i{\omega }_i{e}_i\frac{\partial e_i}{\partial p_n}\end{array}\right]& \left[\mathrm{Expression}19\right]\end{array}$

[0364] As thus described, the use of the edge angle of the image as well as the edge strength thereof can add a direction component, thereby allowing stable positioning resistant to a noise component. Especially by use of differential processing on the image data, it is possible to perform a stable search less subject to fluctuations of luminance.

(Corresponding Point Search Line Filtering Processing)

[0365] Especially performing the search processing of the corresponding point search line on the registered image to select the corresponding point search line is highly likely to be difficult, such a position is preferably eliminated from the pattern search. For example, considering the case of a registered image as in FIG. 23 being present, when corresponding point search lines automatically set on this pattern are automatically set, those are set as in FIG. 24. As shown in this drawing, the corresponding point search line is set not only on the peripheral contour, but in a portion having a contrast difference which is located in the vicinity of the center of the inside. When the matching of the edge is performed by means of such corresponding point search lines set in the vicinity of the center, portions having similar edge angles are generated in large number. Consequently, when the pattern search is performed by use of these corresponding point search lines, it becomes more likely that the corresponding edge points become blurred in the corresponding edge point detection.

[0366] In the present embodiment, such a blurred corresponding point search line is eliminated, to allow performance of a stable, highly accurate search. Specifically, the corresponding point search line set in such an unfavorable region is filtered by a corresponding-point-search-line filtering device, and when one having a similar edge strength and edge angle is present, this line is eliminated. FIG. 25 shows an example of a result of filtering the corresponding point search lines from FIG. 24.

[0367] An example of a procedure for performing corresponding-point-search-line filtering processing on a candidate of the corresponding point search line in the above manner is described based on a flowchart of FIG. 26. First, in Step S2601, corresponding-point-search-line creating processing is performed on the registered image, to create candidates for the corresponding point search line. Next, in Step S2602, the candidates for the corresponding point search line are arranged with respect to the registered image. When arranged in a position where the corresponding point search line was created, the candidates for the corresponding point search line can be detected in the neighborhood of the medium of the candidates for the corresponding point search line.

[0368] Further, in Step S2603, the search of candidates for the corresponding point search line is performed along the candidates for the corresponding point search line, to respectively count the number of candidates for the corresponding point search line. Further, in Step S2604, the filtering processing is performed, and in the case of the number of candidates for the corresponding point search line being two or larger, the corresponding point search line there is determined to be highly likely to be blurred, and is thus eliminated from the candidates for the corresponding point search line. In Step S2605, the remaining corresponding point search lines are regarded as final corresponding point search lines. By this processing, an uncertain corresponding point search line is eliminated so that a more stable pattern search result can be expected.

[0369] It is to be noted that in the case of repeating the fine positioning step, since the line length of the corresponding point search line is made smaller in accordance with the repeated number of times, the corresponding point search line selected in the once performed filtering processing of the corresponding point search lines is previously recorded, and this information can be used in the repetition step. Alternatively, also in the case of shortening the corresponding point search line, similarly, the filtering processing of the corresponding point search lines is performed, and the corresponding point search line selected as a result of the processing can be recorded.

(Corresponding Point Search Line)

[0370] Further, by changing the line length of the corresponding point search line, it is possible to expect improvement in stability of the fine positioning and speeding up thereof. The line length of the corresponding point search line is decided based on a difference in reduction ratio between the coarse search and the fine positioning. For example, when the fine positioning is performed on the unmagnified image and the final coarse search is performed with a reduction ratio of one-fourth, the length is set to the degree of eight pixels (2*4=8).

(Chain Filtering Device 66)

[0371] In the above example, at least one reference point is set with respect to every segment. In the present embodiment, upon creating the segment, chains that constitute the segment are selected, to previously construct highly reliable segment and set the reference point in each segment. Selection or elimination of such specific chains is performed by the chain filtering device 66 shown in the block diagram of FIG. 1. Examples of a reference for selection of the chain by the chain filtering device 66 include an average edge strength and a chain length.

[0372] This chain filtering device 66 performs selection of chains upon registration and during motion. Upon registration, chains worth constituting the segment are extracted. Specifically, the filtering is performed so as to eliminate a chain having a small length not satisfying a predetermined chain length threshold and a chain having a low average edge strength not satisfying a predetermined edge strength threshold because even when the segment is created from these chains, the reliability of segment data is expected to be low.

[0373] Meanwhile, during motion, since a short chain is highly likely to be noise, whether or not to use the chain is selected in accordance with the state of the image to be searched. For example, the user sets a length threshold, to eliminate a short chain. In the following, these are sequentially detailed.

[0374] First, in the case of performing the filtering based on the average edge strength, the chain filtering device 66 performs the filtering by computing an average edge strength of the edge point included with respect to each chain, and comparing the computed value with a pre-set average edge strength threshold. Namely, a chain having a low average edge strength is eliminated, and only a chain having an average edge strength not smaller than the fixed strength is segmented. The reference point is set with respect to the obtained segment to create the pattern model so that the pattern search based on the edge with high accuracy can be expected and the search accuracy can be enhanced. The average edge strength threshold can be set by the user to such a degree as to include enough an edge strength to identify the contour of the pattern model.

[0375] Further, in the case of performing the filtering based on the chain length, the chain filtering device 66 performs the filtering by comparing each chain length with a pre-set chain length threshold. Namely, only a chain having a chain length not smaller than the fixed length is selected, and a chain shorter than that is eliminated, so that the pattern search based on the stable edge can be performed, to contribute to improvement in accuracy.

[0376] Meanwhile, the segment selecting device 67 for performing filtering on a segment configured of chains can also be used. Examples of a reference for selection of the segment by the segment selecting device 67 include, similarly to the above-mentioned chain filtering device 66, an average edge strength, a segment length, whether or not an edge angle image having a similar edge angle is present in the neighborhood, and elimination of uneven distribution of identical edge angles. Further, a short segment may not be simply eliminated uniformly, but the method for filtering a segment may be changed in accordance with the combination of the line and the circular arc constituting the segment. For example, in a case where a sufficiently long segment is extracted from aggregation of segments and the combination of these is estimated to find that one or more arc sectional segments are present, when one or more lines are also present, the shorter segments are considered unnecessary and these are thus eliminated or deleted. Further, in the case of every segment being the line, when three or more long segments are present, sufficient accuracy can be held even if the other shorter segments are eliminated. As thus described, the filtering by the segment selecting device 67 can be changed in accordance with the combination constituting the segment and an appropriate segment can be selected, so that the search can be executed more efficiently.

[0377] It should be noted that the segment length in this case means the length of the straight line or the curve from one end to the other of the line or the circular arc of each segment constituting the pattern model. Further, respective segment length thresholds for the line length and the circular arc length can be individually provided. The segment length threshold is set in accordance with the registered image, required accuracy, or the like, or can be set based on the average segment length of the registered image or the image to be searched.

[0378] Further, when the filtering is performed based on whether or not a segment having a similar edge angle is present in the neighborhood, the segment selecting device 67 determines whether or not another segment having a similar edge angle in the neighborhood in terms of the edge angle of the edge point included in each segment, and eliminates such a segment when it is present. Namely, considering the possibility that a pattern search result might not be stable due to the presence of the segment having a similar edge angle, such a segment is eliminated and the reference point is then set, thereby allowing enhancement of the stability of the pattern search result.

(Tentative Corresponding Edge Point)

[0379] Next, a procedure for finding the coordinate of the corresponding edge point corresponding to the reference point in the fine positioning is described based on FIG. 29. A corresponding edge point is first found on the corresponding point search line TL, and a corresponding edge point as the other of a pair is found. An average coordinate is found from these two points, and the obtained coordinate is regarded as a real corresponding edge point coordinate.

[0380] Specifically, in FIG. 29, the reference point KT is set in part of a circular arc segment (position indicated by a circle in the drawing), and the corresponding point search line TL passing through this point is extended from the upper left to the lower right. First, an edge strength of each point of the image to be searched is checked along the corresponding point search line TL. In the example of FIG. 29, the edge strength is found based on the reference point KT. The edge strength is checked at each of four points “a”, “b”, “c”, and “d” as apexes of a grid shape including the reference point KT. A sub-pixel position of the point having the largest edge strength is found as a tentative corresponding edge point. Consequently, when “e” is computed as the tentative corresponding edge point as the sub-pixel position of the point “a”, subsequently, a pair point corresponding to this tentative corresponding edge point “e” is selected. The pair point is selected such that the tentative corresponding edge point “e” and the pair point sandwich the reference point KT. It is assumed in this case that “f” is selected as the pair point. Further, an average coordinate is obtained from the tentative corresponding edge point “e” and the pair point “f”. The obtained average coordinate is then treated as the real corresponding edge point coordinate.

[0381] In such a manner, computing of the corresponding edge point in corrugated shape can be suppressed, to obtain a stable computing result. Namely, in the case of performing the fine positioning between points, large positional displacement may occur between pairing with a point in a higher wave and pairing with a point in a lower wave, but such an influence can be reduced by the above technique.

(Method for Obtaining Coordinate of Corresponding Edge Point by Use of Neighborhood Edge Point)

[0382] Further, the method for finding a coordinate of a corresponding edge point in units of sub-pixels is not restricted to the above, but another method can also be used. For example, finding of the coordinate can also be realized in the following manner. The corresponding edge point on the corresponding point search line is searched in units of pixels, and the obtained point is regarded as the tentative corresponding edge point. A plurality of neighborhood edge points around this tentative corresponding edge point are found in units of pixels. The sub-pixel coordinates of the tentative corresponding edge point and the plurality of neighborhood edge points are found, and an average coordinate of these is then found. With this method, the position of the real corresponding edge point can be found by use of the tentative corresponding edge point and the plurality of adjacent neighborhood edge points, and hence the coordinate position of the corresponding edge point can be obtained with good accuracy in units of pixels. Further, not using the corresponding point search line but using a plurality of neighborhood edge points appropriately selected around the tentative corresponding edge point, the coordinate position of the corresponding edge point can be accurately decided in a simpler manner

[0383] As the neighborhood edge point, an edge point located on the same contour or segment around the tentative corresponding edge point can be selected. Further, using an edge angle of the tentative corresponding edge point, a neighborhood edge point having a similar edge angle can be obtained. Preferably, with an edge angle direction of the tentative corresponding edge point set at the center, edge points adjacent to the right and left are respectively selected as the neighborhood edge points. Further, a distance from the tentative corresponding edge point to the neighborhood edge point is desirably close, for example within two pixels, preferably on the order of one pixel. This is because too far a distance causes deterioration in accuracy. In the following, a procedure for obtaining the coordinate of the corresponding edge point by use of the neighborhood edge points is described based on a schematic view of a FIG. 65 and a flowchart of FIG. 66.

[0384] First, in Step S6601, the tentative corresponding edge point is searched on the corresponding point search line in units of pixels. In FIG. 65, a shaded white circle is the reference point KT, and a position corresponding to the segment constituting the contour is found on the corresponding point search line TL passing through the reference point KT. The search is performed in units of pixels, namely with each intersection of grids in FIG. 65 regarded as a reference, and (x, y)=(2, 3) is selected in the pixel coordinate in this case.

[0385] Next, in Step S6602, the neighborhood edge point is selected in units of pixels around the tentative corresponding edge point in units of pixels. Since the edge angle of the tentative corresponding edge point has a vector in a direction superimposed on the corresponding point search line, edge points sandwiching the corresponding point search line and located to the right and left thereof, as well as having edge strengths not smaller than a predetermined value, are respectively selected as the neighborhood edge points. Specifically, a first neighborhood edge point located on the right side and a second neighborhood edge point located on the left side are selected. In the example of FIG. 65, a pixel coordinate of the first neighborhood edge point is (2, 2), and a pixel coordinate of the second neighborhood edge point is (1, 3). At this time, since the edge angles of the respective neighborhood edge points are edge points in the neighborhood of the tentative corresponding edge point, the neighborhood edge points are highly likely to have similar edge angles, and hence the edge angles need not to be checked. Needless to add, it is possible to select those edge points as the neighborhood edge points after checking high similarity of the edge angles thereof. It is to be noted that, when there is no edge point having an edge strength not smaller than the predetermined value in the neighborhood position, no neighborhood edge point is selected. In this case, a later-mentioned real corresponding edge point is calculated only through use of the obtained edge points (the tentative corresponding edge point and another neighborhood edge point). Further, although a total of two neighborhood edge points on the right and left are selected in this example, the number of neighborhood edge points selected can also be one or not smaller than three. However, the number is preferably two, considering the balance between the accuracy and load of the computing processing.

[0386] Moreover, in Step S6603, the coordinate of the real corresponding edge point is computed based on the tentative corresponding edge point and the neighborhood edge points. The coordinate position of the real corresponding edge point is decided as an average coordinate of sub-pixel positions of the tentative corresponding edge point and the neighborhood edge points. In the example of FIG. 65, the corresponding edge point is decided from an average of three points: TP1 indicated by a black circle as the sub-pixel position of the tentative corresponding edge point; TP2 indicated by a shaded circle as the sub-pixel position of the first neighborhood edge point; and TP3 indicated by a cross-hatched circle as the sub-pixel position of the second neighborhood edge point. The sub-pixel position of each edge point is previously computed from pixel values therearound. A known method can be applied to a method for computing a sub-pixel position. For example, the sub-pixel position can be calculated from pixel values of surrounding 3×3 pixels with each edge point set at the center thereof, or calculated by use of information on an adjacent edge point present in the edge angle direction, or by some other means. It should be noted that the timing for computing the sub-pixel position of each edge point is not particularly restricted, and the timing may be immediately after decision of the edge point in units of pixels or immediately before calculation of the average coordinate.

[0387] In such a manner as above, the corresponding edge point can be calculated from the average of the sub-pixel coordinates of the three edge points. With this method, the three edge points can be readily extracted from the tentative corresponding edge point, it is possible to decide a highly accurate corresponding edge point through use of many edge points. For example, in the case of the number of reference points being ten, the number of corresponding edge points is normally ten, but with the above method, the respective ten tentative corresponding edge points can be added with points to the right and left thereof, and hence the corresponding edge point can be calculated from the 30 edge points, thereby to improve the accuracy due to an averaging effect. Particularly, as compared with the foregoing method for finding the average coordinate from two points that are the pair point and the tentative corresponding edge point, this method is advantageous in terms of the accuracy since the average coordinate is found from three points that are the tentative corresponding edge point and the two neighborhood edge point added thereto. It is to be noted that three points are obtained and averaged in the above, the three points can be individually used in the fine-positioning calculation.

(Transformation of Edge Angle Image into Edge Angle Bit Image)

[0388] Next, transformation from the edge angle image into the edge angle bit image is described based on FIGS. 30 to 33. Upon taking the coarse-to-fine approach, it is not easy to set the reduced image in the first coarse search. This is because information on a characteristic amount necessary for the search may be lost by image reduction. Especially in the edge-based search, edge angle information is important for improvement in accuracy of the search. Therefore, in the present embodiment, the edge angle bit image creating device 69 and the edge angle bit image reducing device 78 are provided which are capable of holding the edge angle information even when the reduction ratio is made high upon reduction of the image by the thinning device 61, to reduce a data amount while keeping a sufficient characteristic amount, so as to seek speeding up of the processing.

[0389] In the following described is a procedure for acquiring edge angle information upon reducing the image by the thinning device 61 and holding this information. First, the edge strength of each edge point of the edge angle image is checked, and a bit corresponding to the orientation of the edge angle is set to one in the case of the edge strength being larger than a set edge strength threshold, and in the case other than that, the bit is set to zero. For example, a case is considered where the edge angle bit image is created by the edge angle bit image creating device 69 from the edge angle image of 2×2 pixels made up of the four pixels (edge points) “a” to “d” shown in FIG. 30. Each of the pixels “a” to “d” has an edge strength larger than the threshold, and also has an edge strength indicated by an arrow. This edge angle is expressed by eight kinds of edge angle bits that are 0 to 7 in accordance with edge angle sections representing the correspondence of the edge angle to the bit

(Edge Angle Bit Image)

[0390] Upon transforming this edge angle image into the edge angle bit image, the edge angle information is transformed into the edge angle bits. The edge angle bit is a code that sections the edge angle direction with respect to each predetermined angle. To the edge angle section shown in FIG. 31, the same one as that in FIG. 6B described above can be applied. In the example of FIG. 31, a concentration gradient direction as the edge angle direction is sectioned into eight sections by 45 degrees, and the edge angle bit is allocated to each of the sections. This example is not restrictive. The sections may further be rotated counterclockwise by 22.5 degrees from the posture of FIG. 31, to be eight sections displaced by 22.5 degrees from the horizontal or vertical direction, and the respective edge angle sections may be labeled clockwise with E, SE, S, SW, W, NW, N, NE just from the right, each with a width of 45 degrees, and edge angle bit labels 0, 1, 2, 3, 4, 5, 6, 7 may then be added with respect to the respective edge angle sections (foregoing FIG. 52B). Naturally, such sectioning is exemplary, and for example, the edge angle can be sectioned into sixteen sections, four sections, or can further be three sections or five sections.

[0391] From the above, when the edge angle image data shown in FIG. 30 is transformed into a 2×2 edge angle bit image based on the edge angle sections of FIG. 31, the transformed image is as in FIG. 32. As thus described, the bits are set to edge angle sections corresponding to the respective edge angles with respect to the four edge points sectioned by the labels “a”, “b”, “c”, “d”.

[0392] As the method for acquiring an edge angle bit image, other than the technique for performing processing on only a portion not smaller than a certain edge strength threshold as described above, there is also a method for performing thinning processing by use of an edge strength image and an edge angle image, to acquire an edge angle bit image as described above by use of the edge angle image subjected to the thinning processing in order to acquire an edge angle bit image having a certain degree of width. In the case of the technique for performing the thinning processing, the processing time relatively takes long as compared with the foregoing technique, but there is the advantage of facilitating noise elimination since the contour portion of the object to be searched can be restricted.

(Reduction in Edge Angle Bit Image)

[0393] As thus described, after expression by means of the edge angle bit image, the data is reduced such that the edge angle information is sufficiently kept. Specifically, the data is synthesized such that “OR” or a bit sum of each edge angle bit of each pixel is taken with respect to each edge angle bit label. For example, in a case where the 2×2 data to be reduced is in the state of FIG. 32, when it is reduced into ½ long×½ side (=¼) to express the four pixels “a” to “d” by one pixel “a′”, the reduced data is as in FIG. 33. As shown in this drawing, the edge bit of each pixel is synthesized in the edge angle bit reduced image where the edge angle bits of the pixels “a” to “d” are pulled together, and the edge angle bits are set up in columns corresponding to the edge angle bit labels 0 to 7. This processing of storing the edge angle information in the edge angle bit reduced image is performed by the edge angle bit image reducing device 78. Thereby, while the data amount is reduced, the edge angle information is held even after the reduction, and it is thus possible to keep enough characteristics for the search even when the reduction ratio is increased by repetition of the reduction.

[0394] The above compression processing can improve the conventionally problematic state where search processing speed becomes insufficient when the reduction ratio is suppressed so as to keep enough a characteristic amount for the search. Even when the reduction ratio for performing the edge detection is fixed to one-half, for example, a sufficiently high-speed search can be performed by processing of reducing the edge angle bit image with this reduction ratio. The reduction ratio for performing the edge detection can be automatically decided based on at least either the size of the registered image or the characteristic data of the pattern model. Further, the reduction ratio may be arranged so as to be independently set by the user.

[0395] An example of the procedure for reducing the edge angle bit image to create the edge angle bit reduced image is described based on FIGS. 34 to 37. Upon creating the edge angle bit reduced image, attention should be paid on a segmentation problem. Namely, it is possible that simply performing reduction processing by means of sub-sampling processing may cause occurrence of large variations in later-mentioned score calculation due to subtle displacement of a start coordinate of the processing or a position in the input image of the object to be searched. As reduction methods that avoid this segmentation problem, the following two methods can be considered.

[0396] The first method is a method for performing expansion after the reduction processing. This method is described taking an example of processing of reduction into 1/n (n=2) by use of FIGS. 34 and 35. First, the OR operation is performed on n×n edge angle bit data included in each rectangular region of FIG. 34. A result of the operation is replaced as edge angle bit data representing the edge angle bit data of each of the foregoing n×n regions. Performing this processing can reduce the image into 1/n of the original image.

[0397] Since leaving this reduced image in this state may cause occurrence of the segmentation problem, expansion is performed on this image. As in FIG. 35, the OR operation is performed on edge angle bit data in each of m×m (m=2 in this example) rectangular regions in the image after the reduction, and its result is replaced as edge angle bit data representing each of the m×m regions. In this processing, image reduction does not occur. “m=2” in this example, but it can be considered that “m” is increased in accordance with expected variations in shape and size of the object to be searched.

[0398] Another method is a method for taking rather a wide range for the OR operation to be performed in the above reduction processing and not performing subsequent expansion. Using FIG. 36, this method is described taking the case of processing of reducing the image into 1/n (n=2). The OR operation is performed on edge angle bit data of (n+m)×(n+m)(n=1, m=1) included in each rectangular region of FIG. 36. A result of the operation is replaced as edge angle bit data representing each of the n×n edge angle bit data in the vicinity of the center of the foregoing region. Performing this processing can reduce the image into 1/n of the original image. FIG. 37 shows the case of n=2 and m=1 in the second method.

[0399] As shown in FIG. 36, in the case of repeating normal reduction by 2×2 without expansion, the segmentation problem may occur. Namely, with a change in coordinate in the upper left of the search region by one pixel, a setting of pixels upon reduction changes, and hence the score calculation deteriorates regardless of the registered image being an identical image to the image to be searched. As opposed to this, performing the expansion brings about the advantage of not generating such a problem.

(Edge Angle Bit Transformation Processing in Angle Border)

[0400] Further, upon transformation of the edge angle bit, two bits are set up that correspond to two angle regions constituting an angle border when the edge angle is in the vicinity of the angle border, and hence the effect of improving the stability can be expected. For example, in the foregoing edge angle bit image of FIG. 31 obtained by transforming the edge angle image made up of the four pixels “a” to “d” shown in FIG. 30, when the edge angle is in the vicinity of the border between E and SE, the edge angle bit in the section of E may be set up, or the edge angle bit in SE may be set up, depending upon noise. It is expected that such swing causes a nonessential effect to be exerted on calculation of the coincidence. Therefore, when the edge angle is on the border, both edge angle sections that sectionalize the border are set to one. Thereby, the swing due to noise can be eliminated, and a stable calculation result of the coincidence can be expected. Specifically, when the edge angle is located within a predetermined width (e.g. 5.625 degrees) with the border of the edge angle sections set at the center, both of the edge angle bits facing the border are set to one.

[0401] It is to be noted that this edge angle bit transformation processing on an angle border is performed only in the case of the edge angle bit transformation processing on the object to be searched, and is not performed in the case of transformation of the edge angle bit of the pattern model. This is because also performing the same processing in the case of transformation of the edge angle of the pattern brings about an unnatural change in weight with respect to each edge point.

(Edge Angle Bit Adjacent Processing)

[0402] Further, although only one edge angle bit is set up in transformation from the edge angle image into the edge angle bit image in the above example, such edge angle bit adjacent processing can also be performed where a relevant edge angle section is set at the center and an edge angle bit is also set up in each of adjacent edge angle sections. For example, one edge angle bit each is given to the relevant edge angle section and edge angle sections adjacent to the right and left thereof. Further, such weighting is also possible that two edge angle bits are given to the relevant edge angle section and one edge angle bit is given to each of the edge angle sections adjacent to the right and left. Moreover, such weighting added with a fuzzy effect is also possible that three bits are given when the edge angle of the pattern model and the edge angle of the image to be searched sufficiently match, one bit is given when the angles are slightly displaced, and zero bit is given when the displacement is large.

[0403] Also in such edge angle bit adjacent processing, as described above, when the edge angle is present in the vicinity of the border, the effect exerted by swing due to noise can be considered. Hence in the case of the edge angle bit of the image to be searched being on the border of the edge angle sections, two bits are set up in each of the adjacent edge angle sections with the border set at the center, thereby to avoid the effect of the swing.

[0404] It is to be noted that, although the eight bits are used as the angle resolution of the edge angle in the above example, this is not restrictive, and transformation by a further higher angle resolution, such as 16 bits or 32 bits, can also be performed.

(Parallelization)

[0405] Further, by parallelizing a value obtained by transforming the edge angle of the pattern model into the edge angle bit, speeding up of the search processing can be sought. FIGS. 38 and 39 show an example of parallelizing edge data of a pad. FIG. 38 is a conceptual view of a pattern model before parallelization, and FIG. 39 is a conceptual view of the pattern model after parallelization. As shown in these drawings, edge angle bit data on one reference point on the pattern model are laterally arranged in a plurality of number for parallelization, thereby enabling speeding up of the processing. A general CPU constituting a computing section is capable of performing parallel processing of four to eight bytes, and thus capable of performing quad-speed to octuple-speed processing. In such a manner, it is possible to speed up the coarse search by the parallelization processing.

(Coarse Search by Use of Edge Angle Bit Reduced Image)

[0406] In the following, a procedure for performing the coarse search by use of such reduction data is described. As for this edge angle bit reduced image, for example, when the size of the unmagnified image is 640×480 and the edge extraction is performed with a size of 320×240, one-half of the above, the size of the edge angle bit image subjected to compression processing into one eighth is 40×30. The search on this edge angle bit reduced image is performed as follows. First, upon registering the pattern model before the search processing, data as in FIGS. 40A and 40B is created. As shown in this drawing, the pattern model is held as an array of edge data having positional and angle information. FIG. 40A shows an example of the pattern model, and FIG. 40B shows an example of the pattern model of the edge data. In FIG. 40B, symbols x, y denote the coordinate position of the edge, and symbol θ denotes the angle of the edge. This pattern model is held as the array of the edge data having information on the coordinate position and the angle as shown in FIG. 40B.

[0407] Using the above data and the edge angle bit image of the image to be searched the position and the posture of the pattern is repeatedly changed, the coincidence is sequentially calculated with respect to each position and posture of the pattern. This calculation is performed as follows. First, an affine transformation value expressing a position and a posture, coincidences of which are wished to be checked, is decided. This affine transformation value is created also in light of the reduction scale of the pattern model and the reduction scale of the image to be searched Using this affine transformation value, an edge position xi, yi and an edge angle θi are transformed. The edge position after the transformation is Xi, Yi and the edge angle after the transformation is φi (i is a subscript expressing an index of the edge). This coincidence is calculated by transforming the edge angle φi into bit data in the same method as in the case of the image to be searched. A calculating expression for a coincidence S is expressed as follows:

[0408] $\begin{array}{cc}S=\frac{\sum _i\left(EABI\left(X_i,Y_i\right)\&\mathrm{AngleToBit}\left({\varphi }_i\right)!=0\right)}{\sum _{i}1}& \left[\mathrm{Expression}20\right]\end{array}$

• [0409] EABI(x, y): the edge angle bit image of the image to be searched
• [0410] X_i, Y_i: the position of the reference point after the affine transformation
• [0411] AngleToBit (θ): function to transform an edge angle data into a hit data
• [0412] φ_i: edge angle on the expected reference point after the affine transformation
• [0413] &: AND processing
• [0414] !: if the left side is equal to the right side then 0, else 1

[0415] $\sum _i\text{:}$
sum of each reference point

[0416] As thus described, the fine positioning device 76 compares edge strengths and edge angles of the respective edge points included in the image to be searched and the pattern model. The coincidence S being high indicates a high probability of the presence of the pattern model in those position and posture. In such a manner, the state is improved where the processing speed is not sufficient when the search is performed as it is with the reduction ratio decided so as to keep enough a characteristic amount for performing the search. Further, since a sufficiently high-speed search can be performed even with the reduction ratio for performing the edge extraction fixed to one-half, it is possible to obtain the advantage of not having to decide the reduction ratio for performing the edge extraction, which is typically complex.

(Reduction Step for Image to be Searched)

[0417] With such reduction processing, enough characteristics for the search can be kept even with a high reduction ratio. Upon performing the edge extraction processing such as the Sobel filter on the image to be searched, when the unmagnified image of the original size remains unchanged, much noise is generated, which might be inappropriate for extracting characteristics for the coarse search. Therefore, in the present embodiment, the reduced image is created in advance and the edge extracting processing is then performed. Thereby, the averaging effect can be obtained by reduction of the image data, which also contributes to reduction in noise. The reduction ratio as a first reduction ratio (first reduction ratio) is set to one-half of the original size. With this size, a noise reducing effect can be obtained by the averaging while characteristics necessary for the search are sufficiently kept.

(Polarity of Edge Direction)

[0418] Further, with this method, the presence or absence of a polarity of the edge direction can be set. Thereby, the method for processing the edge angle in accordance with the polarity can be changed. Conventionally, such a concept of the polarity has not been considered, but only a concept of the edge direction (angle) has been considered, and hence there has been a problem in that, for example, the edge direction (angle) is treated as 0 to 180 degrees, resulting in that vectors with different orientations cannot be distinguished to cause occurrence of a wrong search. As opposed to this, in the foregoing method, 0 to 360 degrees are covered by considering the concept of the polarity so that a further accurate search is realized.

[0419] In the case of ignoring the polarity, the edge angle bit transformation on the object-to-be-searched side can be readily realized by processing of also setting up a reverse bit simultaneously. Otherwise, a bit can be uniformly allocated not to the orientation but to the edge direction. For example in the coarse search, eight edge angle bits as the edge resolution are uniformly allocated to the edge direction, so that a result of a search can be obtained where importance is attached not to the polarity of the edge but to the resolution of the direction of the edge.

(Fine Positioning Regarding Rotational Angle)

[0420] Next, a procedure for performing fine positioning on a circular arc segment by means of the least squares method with a distance between a point and a circular arc regarded as an error angle is described based on FIGS. 41 to 45. Considered is the case of performing the fine positioning on the image to be searched by means of a pattern as the pattern model PM, expressing a partially notched circle by a circular arc segment and a line segment, as indicated by a thick line in FIG. 41. The pattern model PM of FIG. 41 is configured of one circular arc segment and one line segment, and such a work shape has generally been applied to a wafer provided with an orientation-flat surface, and the like. FIG. 42 shows a state where the coarse search has been performed on the image to be searched by means of this pattern model PM, to perform a certain level of positioning with the pattern model PM arranged in a position of a detection candidate. Considered is a state where the pattern model PM is almost superimposed on the edge point of the image to be searched and only the line segment of the notched section does not match. It is to be noted that in these drawings, the thick line indicates the pattern model PM, and a thin line indicates the edge point (input edge point IE) of the image to be searched. Further, a target point of the input edge point IE is indicated by a dashed arrow, and a tangent line SL at this input edge point is indicated by a broken line. It is to be noted that, although an actual tangent line SL is shorter and is present in the state of being superimposed on the pattern model PM of the thin line, the signal line is displayed longer in these drawings for the sake convenience of description.

[0421] When the fine positioning is performed from this state, it can be expected that the pattern model is relatively rotated so as to allow the line segment portions to match, namely in FIG. 42, the error does not necessarily become larger by the rotation even with the least squares method applied to the input edge point of the position indicated by the arrow in FIG. 42. The least squares method, in which not the distance between the point and the straight line but the distance between the point and the circular arc is regarded as the error function, is applied to the circular arc segment. Specifically, the least squares method is applied such that an absolute value of a difference between a radius of the circular pattern model and a radius of the edge point of the image with the center of the circular pattern model to be searched as the circular arc is regarded as the error value. Namely, the error function of the circular arc segment used in the least squares method is a difference between an ideal radius having the center of the circular arc segment and a distance between the center of the circular arc and the corresponding edge point. This error function of the circular arc segment can be expressed by the following expression:
e=abs(R_ideal−√{square root over ((x−x_c)²+(y−y_c)²)}{square root over ((x−x_c)²+(y−y_c)²)})  [Expression 21]

• [0422] R_ideal: an ideal radius
• [0423] (x_c, y_c): a center coordinate of a circular arc
• [0424] (x, y): corresponding edge point
  e=abs((x−x_c)²+(y−y_c)²−R_ideal²)  [Expression 22]
• [0425] R_ideal: an ideal radius
• [0426] (x_c, y_c): a center coordinate of a circular arc
• [0427] (x, y): corresponding edge point

[0428] Consequently, as shown in FIG. 43, the distance between the input edge point of the arrow and the circular arc model does not change much. Namely, this means that counterclockwise rotation of the pattern model PM as shown in FIG. 43 can be generated as a solution to a sufficient degree. It is thereby possible to expect achievement of high accuracy in the angle on the circular work in the fine positioning performed in a small number of times. It is to be noted that in the examples of FIGS. 42 and 43, the circular region indicated by the dotted line is in practice superimposed on the thin line of the pattern model, but is slightly displaced and displayed in these drawings for the sake of convenience of description.

[0429] Meanwhile, in the conventional least squares method, a distance between the input edge point and the tangent line has been regarded as the error function, and the pattern model has been moved so as to shorten this distance. It can thus be thought that the pattern model is not rotated in a proper rotational direction and this thus has the opposite effect of increasing positional displacement. For example, there have been cases where rotating the pattern model PM counterclockwise as shown in FIG. 48 from the state of FIG. 47 cannot be expected. Namely, when the pattern model PM is rotated as shown in FIG. 48 from the state of FIG. 47 where the relation between the input edge point and tangent line is formed in a position indicated by an arrow, the rotation is performed in a direction in which the input edge point detaches from the tangent line, resulting in that such a rotation cannot be generated as a solution. As opposed to this, in the present embodiment, since the foregoing least squares method with the distance between the point and the circular arc regarded as the error function is applied, it is possible to expect achievement of high accuracy in the angle on the circular work in the fine positioning performed in a small number of times.

(Corresponding Edge Point Creating Processing)

[0430] FIG. 44 shows an example of further performing creating processing of a corresponding point search line on the pattern model of FIG. 41. As thus shown, one reference point is allocated to the center of each of the circular arc segment and the line segment, and reference points are set from each of those points at fixed intervals except for the vicinities of the end edges of the segments. Further, corresponding point search lines are set from the inside to the outside in the direction of the normal to the segments on the respective reference points. FIG. 45 shows a state where the coarse search has been performed on the image to be searched by use of this pattern model, and the pattern model PM has been superimposed on the position and posture of the decided detection candidate.

[0431] In this state, the edge extraction is performed along each corresponding point search line, to search the corresponding edge point with respect to each segment. Since the corresponding edge point is a point at which each corresponding point search line and the edge point (thin line) of the image to be searched intersect, for example in FIG. 45, points indicated by × are the corresponding edge points. In the example FIG. 45, since the circular arc sections of the pattern model arranged in the position of the detection candidate obtained as a result of the coarse search and the input edge point almost match, the corresponding edge point of the circular arc segment and the circular arc segment almost match. Therefore, even when the circular work is relatively rotated, the error function of the circular arc does not increase, and hence this degree of freedom does not inhibit the rotation. It is therefore possible to expect the rotational movement to be a solution.

[0432] On the other hand, many of corresponding edge points of the line segment are not on the line segment. In the least squares method to be performed on the line segment, since the distance between the point and the straight line is regarded as the error function, it is estimated that counterclockwise rotation totally reduces a value of the error function. It is found therefrom that it can be expected to a sufficient degree to obtain counterclockwise rotation as a solution obtained by the least squares method.

(Weighing Processing in Case of a Plurality of Corresponding-Edge-Point Candidates being Present)

[0433] Furthermore, when a plurality of corresponding-edge-point candidates corresponding to the reference point are present, weighting can be performed on each corresponding edge point, so as to improve the accuracy in the fine positioning in a case where the corresponding edge points are ambiguously decided. This condition is described based on FIGS. 49A to 49D. An example of performing the fine positioning is considered using, as the pattern model, the pattern model PM that is a rectangle with two longitudinal lines drawn therein as indicated by thick lines in FIG. 49A. In this case, it is assumed that segments SG1 and SG2 as indicated by thin lines in FIG. 49B are obtained in the coarse search. In FIG. 49B, only the two segments SG1, SG2 located to the right and left of the work are considered. Corresponding point search lines TTL1, TTL2 of these segments are set in the directions of the normals (edge directions) to the respective segments SG1, SG2 passing through the reference points KT1, KT2 as described above. When the corresponding point search lines TTL1, TTL2 are set at the respective reference points KT1, KT2 as indicated by broken lines with respect to the respective segments SG1, SG2, corresponding-edge-point candidates located at the respective corresponding point search lines TTL1, TTL2 can be obtained. While only one corresponding-edge-point candidate TTA is obtained with respect to the right-side segment SG1, two corresponding-edge-point candidates TTB, TTC are obtained with respect to the left-side segment SG2. Since a corresponding edge point that is the closest to the reference point is selected out of the corresponding-edge-point candidates and decided as the corresponding edge point, TTA and TTB each become the corresponding edge point. In the example of FIG. 49B, since a plurality of corresponding-edge-point candidates are present with respect to the left-side segment SG2, it can be regarded that ambiguity is included. In this case, the issue is in which direction the segment, namely the pattern model, is to be moved. Especially in the case of FIG. 49B, when the whole segment, namely the pattern model, moves to the right as a result of selection of TTB as the corresponding edge point, it moves in the reverse direction to desired fine positioning, which is not preferred.

[0434] Therefore, upon performing the calculation of the least squares method, each corresponding edge point is weighted. In the example of FIG. 49B, since only one corresponding edge point TTA is present on the corresponding point search line TTL1 of the reference point KT1 with respect to the right-side segment SG1, a weight of “1.0” is given. On the other hand, concerning the left-side segment SG2, the corresponding-edge-point candidates TTB, TTC are located to the right and left of the reference point KT2 sandwiched therebetween on the corresponding point search line TTL2 of the reference point KT2. Therefore, weighting of the corresponding edge point TTB with regard to the reference point KT2 is set in accordance with a distance from the reference point KT2 to each corresponding-edge-point candidate. As an example of an expression for deciding weighting, as shown in FIG. 49D, when a distance between a first corresponding-edge-point candidate and the reference point is d1, and a distance between a second corresponding-edge-point candidate and the reference point is d2 (d1≦d2),
Weighting W=1−α(d1/d2)

• [0435] where 0<α<1.
  In the above expression, W=1 in the case of the number of corresponding-edge-point candidates being one, and W is smaller in the case of the number being more than one. As thus described, by increasing weighting in the case of the number of corresponding-edge-point candidates being one, namely in the case of no blurring, a movement in a more probable direction can be expected. Further, in the case of the number of corresponding-edge-point candidates being more than one, while the closest corresponding-edge-point candidate is regarded as the corresponding edge point, the positional relation between the corresponding edge point and the corresponding-edge-point candidate is the above expression: W=1−α(shorter distance)/(longer distance), when an ideal point is sandwiched, and “W=1” when the ideal point is not sandwiched. After such a weighting operation and weighting, the segment movement direction is decided by the fine positioning device 76 included in the computing device 6 of FIG. 1 as a weighting computing device.
  (Score Calculation)

[0436] Further, upon performing the fine positioning calculation by use of the least squares method, a score indicating a similarity can also be calculated. Namely, the least squares method is applied to the corresponding point search line, and the score is calculated by a ratio between the number of corresponding points and the number of reference points in the final least squares method processing. In a simplified manner, a value obtained by subtracting the number of corresponding points by the number of reference points is considered as the similarity, and the can be found by the following expression:

[0437] $\begin{array}{cc}S=\frac{\sum _{i=1}^{n}1}{\sum _{i=1}^{m}1}=\frac{n}{m}& \left[\mathrm{Expression}23\right]\end{array}$

• [0438] S: score
• [0439] n: the number of corresponding points
• [0440] m: the number of reference points

[0441] Further, a similarity of an ideal edge angle of the reference point and the edge angle of the corresponding edge point can also be reflected to the score. In this case, a ratio of a total of weights each obtained from a difference between the edge angle of the corresponding edge point in the final least squares method processing and the edge angle of the reference point corresponding thereto, and the number of reference points is calculated as the score. Specifically, it can be computed by the following expression:

[0442] $\begin{array}{cc}S=\frac{\sum _{i=1}^n\omega \left({\theta }_i-{\theta }_i^p\right)}{\sum _{i=1}^{m}1}& \left[\mathrm{Expression}24\right]\end{array}$

• [0443] S: score
• [0444] n: the number of corresponding points
• [0445] m: the number of reference points
• [0446] ω(x): function that is 1 when x=0, and monotonously decreases with increase in x
• [0447] θi: edge angle of corresponding point
• [0448] θip: angle of reference point corresponding to corresponding point (ideal angle of reference point)

[0449] The ideal edge angle of the reference point is the direction of the normal to the line when the segment is the line, and superimposed on the corresponding point search line. In this method, a setting is made such that the smaller the difference between the edge angle of each corresponding edge point and the ideal edge angle of the reference point corresponding to the corresponding edge point, the more the weight approaches 1, and on the contrary, the larger the angle difference, the more the weight approaches to 0. For example, the weight is set so as to be 0 in the case of the angle difference being 0 to 18 degrees, to be 0.1, . . . , in the case of the angle difference being 18 to 36 degrees, and to be 1 in the case of the angle difference being 162 to 180 degrees. In such a manner, a weight is computed with respect to each reference point and finally obtained weights are averaged, to compute the score.

[0450] In the example of FIG. 49B, a weight of 1 is given to the right-side corresponding edge point A, and a weight of “0.9” is given to the left-side corresponding edge point B. This results in that an action to move the pattern model to the left side is exerted on the right-side segment SG1 and an action to move the pattern model to the right side is exerted on the right-side segment SG2. Therefore, putting these together, the weight intended for movement to the left side is 1.0 and the weight intended for movement to the right side is 0.9, and consequently, the pattern model is moved to the left side, to come into a state as in FIG. 49C. Similarly, weighting is performed again from the state of FIG. 49C, and movement processing is repeated based on a result of the weighting, to determine final fine positioning. As thus described, the direction in which the pattern model is to be moved upon positioning is estimated by weighting in accordance with the distance between the corresponding-edge-point candidate and the reference point, and the positioning is then performed. It is thereby possible to move the pattern model in a relatively probably direction, so as to expect improvement in reliability and stability of the positioning.

(Method for Selecting Segment in Consideration of Positioning Direction)

[0451] Such a case as above can occur especially when many line segments are concentrated in a specific direction. In the example of FIG. 49B, the segments are present only in the longitudinal direction (Y-axis direction), and accurate positioning can thus be expected in the X-axis direction. On the other hand, since no line segment extending in the lateral direction (X-axis direction) is present, the Y-axis direction cannot be defined, to make the positioning in this direction ambiguous. Therefore, upon selecting segments constituting the pattern model, segments in the orthogonal relation, such as in the X-axis direction and the Y-axis direction, are intentionally selected for preventing the positioning directions from being concentrated in a specific direction, so that a stable positioning result can be expected. In the following, a method for selecting a segment in consideration of a positioning direction is described based on a flowchart of FIG. 50.

[0452] First, in Step S4901, in a state where a plurality of segment candidates have been obtained, the segment candidates are sorted in order of length. It is to be noted that in the case of the circular arc segment, the length of the circular arc is regarded as the segment length.

[0453] Next, in Step S4092, the longest segment candidate is selected as the segment, and also set as a reference point segment. The direction of the normal to this reference segment is regarded as a reference angle. It should be noted that, when the circular arc segment is selected, the reference angle comes into an ineffective state. When the reference angle is ineffective, a conjugated segment is selected not by means of the angle but only the length of each segment candidate.

[0454] Further, in Step S4903, the segment candidates as the conjugated segment with respect to the reference segment are extracted. It is searched from the reference angle whether or not the segment candidate included within a predetermined angle range, a first angle range in this case, is present. FIG. 51A shows an example of the first angle range. The segment candidate is extracted which is included within the range of ±45 degrees with the direction of the normal to the reference segment (90 degrees) set at the center, namely the range of 45 to 135 degrees, the range of 90 degrees in total.

[0455] In the example of the segment candidates shown in FIG. 51B, segment candidates with “◯” marked thereon are extracted, and segment candidates with “×” marked thereon are eliminated. When the line segment is selected as the conjugated segment, the reference angle becomes the direction of the normal to that segment, and comes into an effective state. When the segment is not the line but the circular arc segment, it is unconditionally extracted. This is because, in the case of the circular arc segment, a change in angle is expected to be large and can thus be useful information. Further, in the case of the circular arc, the state of the reference angle remains unchanged.

[0456] When the segment candidates are extracted, the process goes to Step S4901-1, the longest segment candidate among the extracted segment candidates is selected as the segment, and is also set as the conjugated segment with respect to the reference segment. Further, in Step S4905, it is determined whether or not the number of already selected segments has reached a predetermined number. When it reaches the predetermined number, the processing is completed. When it has not reached the predetermined number, the process goes to Step S4906, and a new reference segment is set again as the conjugated segment. Thereafter, the process returns to Step S4903, to repeat the processing. It should be noted that, in the case of the circular arc segment being selected as the conjugated segment and the circular arc segment being regarded as the reference segment, the selection of the conjugated segment is made in accordance not with the angle but with the length alone as described above when the reference angle is in the ineffective state, and the extraction of the conjugated segment is made by performing the same processing as the foregoing show when the reference angle is in the effective state.

[0457] Meanwhile, when no segment candidate included within the first angle range is present in Step S4903, the process goes to Step S4904, and it is searched in the same manner as above whether or not a segment candidate is present which is included within a second angle range expanded from the first angle range. In the example of FIG. 51A, the range of 40 to 140 degrees, expanded by ±5 degrees from the first angle range, is set as an example of the second angle range. When the segment candidate is found, the process jumped to Step S4904-1, and in the same manner as above, the longest segment is selected and set as the conjugated segment.

[0458] When no segment candidate is found even within the second angle range, in Step S4904-3, it is further searched in the same manner as above whether or not a segment candidate is present which is included within a third angle range further expanded from the second angle range. In the example of FIG. 51A, the range of 35 to 145 degrees, further expanded by ±5 degrees from the second angle range, is set as an example of the third angle range. When the segment candidate is found, the process jumped to Step S4904-1 in the same manner as above, and the longest segment is selected and set as the conjugated segment. When no segment candidate is found, the process goes to Step S4902, and the longest segment among the segment candidates is re-selected as the reference segment. It should be noted that the numeral value of the angle range, the number of times of re-settings of the angle range, and the like can be changed as appropriate. For example, when no segment is found in Step S4094-3, a search in a further expanded angle range may be performed. On the contrary, Step S4904-3 may not be performed, and when no segment is found in Step S4904-2, the process may be immediately returned to Step S4902 to reset the reference segment.

[0459] As thus described, since the operation of selecting the conjugated segment close to the orthogonal direction to the reference segment is repeated and as a result, the segment with a dispersed angle is selected, the stability of the positioning can be improved. The segment is selected in such a manner by the segment selecting device 67 of the segment creating device 68.

(Pattern Characteristic Selecting Function)

[0460] Further, a pattern characteristic selecting function can also be provided which is capable of changing selection criteria for the segment constituting the pattern model in accordance with characteristics of the pattern obtained from the object to be searched. Specifically, it is especially effective in a registered image as shown in FIG. 67. In the registered image in FIG. 67, different characters and numerals are displayed in grid frames. When the pattern window PW is set on such an image, as shown in FIG. 67, many segments SGW are set in frame portions whereas few segment SGM are set in the characters inside the frames in the created pattern model. In such a pattern model, the positioning is performed only in the frame portions, resulting in that the characters inside the frames are ignored or importance is not attached thereto, to make the characters difficult to recognize, and thereby, the positioning may be failed due to positional displacement in units of frames or the like.

[0461] This is caused by the selection criteria for the segment. Namely, a long segment has been preferentially selected from the conventional viewpoint that eliminating the noise component and attaching importance to a more clearly detected edge point leads to improvement in positioning accuracy. This is because a short contour is considered to have a large number of noise components, and based on assumption that a longer line segment adversely extracts more accurate edge information, a setting has been made to automatically select the segment from long line segments. In other words, there have not hitherto been present an image processing method and the like for making a short line segment preferentially selectable. Therefore, in the example of FIG. 67, since the edge detection tends to be relatively easy and clear in the frame portion surrounded by the straight lines, the segment created in the frame portion becomes more apt to be selected, leading to failure of the positioning as described above. Especially in the coarse search, since it is a simple search and thus not all contour information on the extracted edge, chain segment and the like are used but only part of the contour is selected, when the preferentially selected contour does not contribute to accurate positioning, the problem of such an erroneous selection occurs.

[0462] As opposed to this, in the present embodiment, a function capable of selecting the contour in ascending order of length from the shorter contour is set, so as to obtain an appropriate search result in accordance with the registered image. Further, elimination of the noise component is realized by setting a threshold and eliminating a line segment with a length not larger than the predetermined length. Consequently, while the noise component is effectively eliminated, a highly reliable search result can be obtained.

(Sorting in Order of Contour Length)

[0463] Next, two methods for selecting a short contour are described. First, a method for sorting contours in order of length and selecting a predetermined number of contours from a short one is described based on a user interface screen of FIG. 68. FIG. 68 is an image view showing a user interface of an image processing program setting screen 200 of the pattern characteristic selecting function for appropriately selecting a contour constituting a pattern model of a registered image. In this screen, the user can make respective settings for the coarse search and the fine positioning, regarding respectively as setting items an edge strength lower limit 82, a contour length lower limit 83, a number of selected contours 84, and an order of contour registration 85. Among them, the items regarding the pattern characteristic selecting function are the contour length lower limit 83, the number of selected contours 84 and the order of contour registration 85.

[0464] A range for detection as the edge is defined by the edge strength upper limit 81 and the edge strength lower limit 82, and such a filtering condition as to eliminate an edge strength higher than the upper limit value or lower than the lower limit value is designated.

(Contour Length Lower Limit Setting Device)

[0465] The contour length lower limit 83 functions as a contour length lower limit setting device for setting a lower limit for detection as the contour. Namely, the contour shorter than a lower limit value defined by the contour length lower limit 83 is filtered by a length filter. This can eliminate noise appeared as the short contour. Further, with this value made adjustable by the user, the strength of the filtering can be appropriately adjusted in accordance with a used environment and application of the filtering. Further, the contour length lower limit may be a fixed value depending upon the environment.

(Number-of-Selections Deciding Device)

[0466] The number of selected contours 84 functions as a number-of-selections deciding device for defining the number of contours selected. Defining the upper limit of the number of contours used as the pattern model can simplify the pattern model to reduce a processing amount, thereby to seek reduction in search time. Further, with the number of selections increased, the processing amount increases, but on the other hand, a highly accurate search result can be expected. It is to be noted that setting the number of contours selected to a fixed value (e.g. 50) can seek simplification of the setting operation as described above.

(Order-of-Selections Deciding Device)

[0467] The order of contour registration 85 functions as an order-of-selections deciding device capable of switching the order of selecting contours between ascending order and descending order of contour length. Thereby, in accordance with an image as an object for image processing, an appropriate selecting method of ascending order or descending order of length is set so that image processing with more flexibility and higher accuracy can be performed.

[0468] By setting the above setting items, such an extremely short contour as to be close to noise is filtered out of a plurality of contours, and the contours are made selectable sequentially from the shorter one, to effectively eliminate the noise component and also appropriately select a segment that exerts an influence on the positioning accuracy so that an efficient pattern model can be constructed.

[0469] For example considered is an example of selecting a segment constituting a pattern model by setting the pattern window PW on a registered image where different characters and numerals are displayed in grid frames as shown in FIG. 69. In the case of setting as shown in FIG. 70, since the order of contour registration 85 is set to “descending order of length”, namely, it is set so as to sequentially select the contours from the longer one to the shorter one. Thereby, as in FIG. 69, many of the segments SGW in the frame portions are undesirably selected and few of the segments SGM in the portions of characters and numerals, important for identification, are selected, and the accuracy in positioning cannot be expected if this state remains unchanged.

[0470] As opposed to this, as shown in FIG. 71, the setting in the order of contour registration 85 is changed to “ascending order of length”, namely, the setting is changed so as to select the contours sequentially from the shorter one to the longer one, whereby many of the segments SGM of the characters and numerals inside the frames come to be selected as in FIG. 72, so that a pattern model including contour information suitable for the registered image can be constructed.

[0471] It is to be noted that, although each setting item is individually settable respectively in the coarse search and fine positioning in the example of FIG. 68, it can be made settable in either one, or such a constitution may be formed that a specific item is defined by the image processing program or the image processing apparatus side, and adjustment by the user is inhibited. Reducing the number of setting items to allow a user not particularly familiar with the operation to use the device in a simplified manner can improve operability.

[0472] Further, as for the contour, contour information such as the chain or the like other than the segment is also usable. For example, in the case of using chains obtained by the chain creating device 63 as they are as the contour information without approximating the chains to the line segment or the circular arc segment, a technique for selecting the chains from the short chain as described above, a technique for making the order of selection switchable between ascending order and descending order, or a technique for eliminating a chain shorter or longer than a predetermined threshold can be applied to selection criteria for the chain, and this can also allow a similar action effect to be obtained. Next, a specific procedure for sorting the contours in order of contour length is described based on flowcharts of FIGS. 73 and 74.

[0473] First, the case of performing the sorting by use of a segment length is described based on FIG. 73. First a contour is extracted. First, in Step S7301, the registered image is Sobel-filtered, to find an edge angle image and an edge strength image. Next in Step S7302, an edge point is thinned by use of the edge angle image and the edge strength image, to find a contour point. Specifically, after creation of the edge angle image and the edge strength image by the edge angle/edge strength image creating device 60 of the contour extracting device 62, the edge point is thinned by the thinning device 61 by means of edge-strength non-maximal point suppressing processing. Further, in Step S7303, a chain is created by the chain creating device 63. Specifically, the edge chaining device 64 couples adjacent edge points, to create the chain. Moreover, the filtering is performed as appropriate by the chain filtering device 66 with a variety of characteristic amounts.

[0474] Next in Step S7304, a segment is created. The edge chain segmenting device 65 of the segment creating device 68 creates a segment obtained by approximating each chain by the line and/or the circular arc. Further, in Step S7305, the short segment is filtered. As a contour length lower limit setting device, the segment selecting device 67 eliminates a segment with a length not larger than a lower limit value, to eliminate the noise component.

[0475] Finally, in Step S7306, the segments are sorted by segment length, to select the segments constituting a pattern model sequentially from the segment having a shorter length. The segment selecting device 67 functions as a contour sorting device for sorting the contours in descending order of length, sorts the segments in order of length, and further selects the segments in number defined by the number-of-selections deciding device in a selection order defined by the order-of-selections deciding device, in ascending order of segment length, namely sequentially from the shorter one. Thereby, a pattern model suitable for the registered image as in FIG. 72 described above is constructed.

[0476] On the other hand, an example of using the chains as they are not through the segment as the contour is described based on a flowchart of FIG. 74. A procedure from extraction of the contour point to creation of the chain is the same as FIG. 73 above. Namely, in Step S7401, the registered image is Sobel-filtered, to find an edge angle image and an edge strength image. Next in Step S7402, an edge point is thinned by use of the edge angle image and the edge strength image, to find a contour point. Further, in Step S7403, a chain is created.

[0477] Then, in Step S7404, the short chain is filtered. In accordance with a lower limit value set by the contour length lower limit setting device, the chain filtering device 66 of the chain creating device 63 eliminates the chain shorter than the contour length lower limit 83. Subsequently, in Step S7405, the chains are sorted in order of chain length, to select the chains constituting a pattern model sequentially from the chain having a shorter length. Also in this case, the chain filtering device 66 functions as the contour sorting device, sorts the chains in order of length, and further selects the chains in number defined by the number-of-selections deciding device in a selection order defined by the order-of-selections deciding device, in ascending order of chain length. Thereby, a pattern model suitable for the registered image as in FIG. 72 is constructed.

[0478] With this method, the processing of once making approximation with a segment is not required, and hence the processing can be accordingly simplified. On the other hand, since the chain is a body of coupled random line segments not approximated to a fixed geometric graphic such as the line or the circular arc, each of subsequent processing becomes complicated. Which method is selected is decided in accordance with whether or not the registered image is a simple graphic, the detection accuracy of the edge point, or the like.

(Filtering Long Contour)

[0479] It should be noted that, although the sorting is performed in order of contour length in the above example, the pattern model can be constructed by eliminating the long contour without performing sorting. In the following, this method is described based on a user interface screen of FIG. 75. FIG. 75 is also an image view showing a user interface of an image processing program setting screen 300 for setting the pattern characteristic selecting function for the registered image in the image processing program. In this screen, a contour length upper limit 86 is given in addition to the edge strength upper limit 81, the edge strength lower limit 82, and the contour length lower limit 83. The edge strength upper limit 81, the edge strength lower limit 82 and the contour length lower limit 83 are similar to those in FIG. 68 described above, and detailed descriptions thereof are not repeatedly provided.

(Contour Length Upper Limit Setting Device)

[0480] The contour length upper limit 86 functions as a contour length upper limit setting device for setting an upper limit value of a contour. Namely, the contour length upper limit 86 filters the longer contour than the upper limit value defined by the contour length upper limit 86. It is thereby possible to construct a pattern model by intentionally eliminating the long contour while leaving only the short contour, so as to consequently obtain a similar effect to the case of preferentially selecting the short contour.

[0481] It is to be noted that in the example of FIG. 75, the number-of-selections deciding device is not provided, and contours in number of a pre-set defined value are automatically selected. However, the number-of-selections deciding device can also be provided so as to allow the user to manually set the number of contours.

[0482] As thus described, without sorting the contours in order of length, a pattern model can be constructed where a short contour is preferentially selected, and a pattern search also effective to the registered image as in FIG. 67 can be realized. For example, in such setting conditions as shown in FIG. 76, the pattern model includes many of the segments SGW that are selected in the frame portions as shown in FIG. 77. However, by changing the contour length upper limit 86 from 100 to 20 as shown in FIG. 78, there can be constructed a pattern model, as shown in FIG. 79, including many of the segments SGM of the characters or numerals inside the frames.

[0483] A procedure for filtering a long contour is described based on flowcharts of FIGS. 80 and 81. First, FIG. 80 describes the case of using the segment as the contour. Also with this method, as in the foregoing case of sorting the contours by contour length, contour points are extracted to create a chain. Namely, in Step S8001, the registered image is Sobel-filtered, to find an edge angle image and an edge strength image. Next in Step S8002, an edge point is thinned by use of the edge angle image and the edge strength image, to find a contour point. Further, in Step S8003, a chain is created, and subsequently in Step S8004, a segment is created.

[0484] Finally, in Step S8005, the long segment and the short segment are deleted. Besides that the segment selecting device 67 eliminates the segment having a length not larger than the lower limit value as the contour length lower limit setting device, the segment selecting device 67 further functions as the contour length upper limit setting device, to delete the segment having a length larger than the contour length upper limit 86. Consequently, since the short segment can be selected after elimination of the noise component, there can be constructed a pattern model including a segment effective for positioning in such a case as FIG. 79. Although the number of segments to be selected is a fixed value, as described above, the number-of-selections deciding device can be separately provided so as to allow the user to manually make a setting.

[0485] Further, an example of constructing a pattern model by chains in place of segments is described based on FIG. 81. Also in this case, a procedure from extraction of the contour point to creation of the chain is similar to that of FIG. 74 described above. Namely, in Step S8101, the registered image is Sobel-filtered, to find an edge angle image and an edge strength image. In Step S8102, an edge point is thinned by use of the edge angle image and the edge strength image, to find a contour point. In Step S8103, a chain is created.

[0486] Then, in Step S8104, the long chain and the short chain are deleted. The chain filtering device 66 eliminates the chain having a length not larger than a contour length lower limit value as the contour length lower limit setting device, and also functions as the contour length upper limit setting device, to delete the longer chain than the contour length upper limit 86. Consequently, since the short chain can be selected after elimination of the noise component, there can be constructed a pattern model including a chain effective for positioning of the registered image in such a case as FIG. 79. Although the number of chains to be selected is a fixed value, as described above, the number-of-selections deciding device can be separately provided so as to allow the user to manually make a setting.

(Combination of Segment Selecting Functions in Consideration of Segment Direction)

[0487] The pattern characteristic selecting function can be used simultaneously with the foregoing segment selecting function in consideration of the positioning direction or angle. Namely, as a technique for deciding which segment is selected for constructing a pattern model after sorting of segments in order of length or after filtering of a long segment, it is possible to adopt a method for selecting a conjugated segment close to an orthogonal direction to a reference segment, as a method shown by a flowchart of FIG. 50 and the like. It is to be noted that this method can be used for selection of the segment, but cannot be use for selection of the chain. This is because the chain is not appropriated by the line and/or the circular arc, and thus does not have an angle or a direction as does the segment.

[0488] An example of considering the direction of the normal to the segment upon selecting the segment after sorting or filtering is described below based on flowcharts of FIGS. 82 and 83. First, FIG. 82 shows an example of sorting the segments by segment length. Also in this case, a procedure from extraction of the contour point to create the chain and the segment to filtering of the short one among the obtained segments to sort the segments is similar to the foregoing procedure of FIG. 73. Namely, first in Step S8201, the registered image is Sobel-filtered, to find an edge angle image and an edge strength image. Next in Step S8202, an edge point is thinned by use of the edge angle image and the edge strength image, to find a contour point. Further in Step S8203, a chain is created, and then in Step S8204, a segment is created. Subsequently in Step S8205, the short segment is filtered, and then in Step S8206, segments after the filtering are sorted by segment length and arrayed in ascending order of length.

[0489] In this state, in Step S8207, the segments are selected sequentially from the shorter one while considering the direction of the normal to each segment. A specific procedure after Step S8206 of FIG. 82 is shown in a flowchart of FIG. 84. This flowchart is almost similar to the flowchart of FIG. 50, but is different therefrom in: setting the order of sorting not to descending order of segment length but to ascending order from the shorter one in Step S8401; selecting the shortest segment as a segment candidate and regarding this as a reference segment in Step S8402; and selecting the shortest segment as a segment candidate and regarding this as a conjugated segment in Step S8404-1. Other than the above are similar to those in FIG. 50, and detailed descriptions thereof are thus not repeatedly provided.

[0490] This method is particularly effectively performed on the registered image where the short segment is effective, and substantially orthogonal segments are alternately selected, to construct a pattern model where segments in such a relation that normal angles are orthogonal are intentionally selected, whereby it is possible to expect a result of stable positioning in the longitudinal and lateral directions.

[0491] Similarly, an example of considering the direction of the normal to the segment in the method for filtering a segment having a large length is described based on a flowchart of FIG. 83. Also in this case, a procedure from extraction of the contour point to create the chain and the segment to filtering of the short one and the long one is similar to the foregoing procedure of FIG. 80 and the like. Namely, first in Step S8301, the registered image is Sobel-filtered, to find an edge angle image and an edge strength image. Next in Step S8302, an edge point is thinned by use of the edge angle image and the edge strength image, to find a contour point. Further in Step S8303, a chain is created, and then in Step S8304, a segment is created. Subsequently in Step S8305, the short segment and the long segment are filtered. Since an operation of sorting the segments by segment length in Step S8306 is required at any rate in this case, the foregoing method of FIG. 82 can be regarded as more efficient from this point of view. The other effects are similar to those in FIG. 82, and as a result of selecting a conjugated segment close to the orthogonal direction, the segment with a dispersed angle is selected to be the pattern model, thereby allowing improvement in stability of the positioning.

(Improvement in Stability of Least Squares Method)

[0492] Next described is a technique for improving the stability of the least squares method performed in the fine positioning step. The least squares method is briefly categorized into a linear method and a non-linear method. In the linear least squares method out of these methods, theoretically, a solution can be uniformly obtained. On the other hand, in the non-linear least squares method, approximation is typically made until a quadratic expression, and hence the approximated value is not necessarily accurate. In some cases, in the fine positioning step, the position to be detected may be moved or rotated in a direction to lower the accuracy than the position obtained in the coarse search. For example, in the case of performing the fine positioning on a graphic with high symmetry such as a circular shape shown in FIG. 85 (a center coordinate of an outer circle is subtly different from a center coordinate of an inner circle), since an error value hardly changes even when each circle is rotated around its center as a rotational axis, the circles can rotate in a reverse direction to a direction in which the circles should essentially rotate, or consequently, a large change in angle as well as a large displacement of a parallel moving amount may occur.

[0493] In a typical solving method of the non-linear least squares method approximated by a quadratic expression, such a procedure is taken that an approximate error function is created by approximating an error function E (pi) until a quadratic power number of a trial parameter in the neighborhood of a group “pi” of trail parameters as variables of the least squares method, and using the approximate error function, such a group “pi” of the trial parameters as to minimize the error function is found.

[0494] As a solving method for obtaining a solution with a small error value in the non-linear least squares method as thus described, the following reverse-Hessian method has been proposed.

[0495] This is a method in which, after calculation of the approximate error function and calculation a group of the least trial parameters from the error function, a group of trial parameters on a next stage with higher accuracy is found all together. However, in the case of finding a solution having a small error value by use of this reverse-Hessian method, such a defect as below might occur. This is described based on FIGS. 86A and 86B. In each of FIGS. 86A and 86B, a solid line indicates the error function, and a broken line indicates an approximate error function obtained by approximating this error function. In each of FIGS. 86A and 86B, symbol P1 provided on a curve showing the error function denotes a position (x, y, θ) obtained in the coarse search described above. What is obtained as a quadratic function based on a value of the error function in the neighborhood of this P1 is the quadratic curve showing the approximate error indicated by the broken line.

[0496] Further, in the case shown in FIG. 86A, the drawing describes a case where the reverse-Hessian method appropriately acts, showing a case where, since a position having the least error value of the quadratic curve of the broken line indicating the approximate error function, namely P2, is close to a position P having the least error value of the error function indicated by the solid line, a more accurate position P2 having a small error value is found.

[0497] On the other hand, in the case of FIG. 86B, the drawing describes a case where the reverse-Hessian method inappropriately acts, showing a case where, since a position having the least error value of the quadratic curve of the broken line indicating the approximate error function, namely P2, is away from the position P having the least error value of the error function indicated by the solid line, an in accurate position P2 having a small error value is found.

[0498] Out of the above cases, in the case shown in FIG. 86B, when a solution is intended to be found as it is in the reverse-Hessian method, large displacement of the trial parameter may be taken as the solution as described above, which as a result causes the problem of deterioration in accuracy of fine positioning. The present inventor found a technique for providing a limitation concerning movement or rotation of a pattern model as a technique for suppressing occurrence of the case of the reverse-Hessian method acting in an inappropriate manner, shown in FIG. 86B. Namely, as a solving method for the least squares method based on the reverse-Hessian method, a new term is added to the error function. Specifically, besides the foregoing term concerning a distance (first error function), such a term (second error function Ed) as to increase the error value due to displacement from the trial parameter is added. Thereby, an excessively large change is suppressed by the second error function Ed so that appropriate approximation as shown in FIG. 86A can be expected. As thus described, a condition of convergence in a proper direction in the fine positioning step can be added, to avoid rotation and dispersion in an unintended direction, so as to improve the reliability of the positioning. When the trial parameter in the least squares method is Pi, the second error function is a function of “Pi-P0i”. An example of simultaneous equations of the error function E(P) obtained as a result of this is shown in the next expression:

[0499] $\begin{array}{cc}E\left(P_0,P_1,\dots ,P_n\right)=E_o\left(P_0,P_1,\dots ,P_n\right)+E_d\left(P_0,P_1,\dots ,P_n\right)E_d\left(P_0,P_1,\dots ,P_n\right)=\sum _i{\left(\frac{\left(P_i-P_{0i}\right)}{{\sigma }_i}\right)}^2& \left[\mathrm{Expression}25\right]\end{array}$

[0500] In the above expression, a total error function E(P) is expressed by a sum of a first error function Eo showing a distance between each segment and its corresponding edge point and a second error function Ed obtained by regarding as a second error value an amount of change in trial parameter in the first error function upon making that change and computing an accumulated value of the second error values. As thus described, in computing of the least squares method, since addition of the second error function Ed besides the term that becomes the least value upon matching with an ideal position leads to searching for a solution in such a direction as to make both terms smaller, and suppression of an excessively large change in trial parameter, it is possible to avoid such a condition as rotation or dispersion in a wrong direction upon the fine positioning, so as to obtain the advantage of stabilizing a processing result.

[0501] The pattern model positioning method in image processing, the image processing apparatus, an image processing program, and the computer readable recording medium according to the present invention are preferably applicable to positional detection of a coordinate position, a rotational angle and the like of a work, positional measurement of an external diameter, an internal diameter, a width, and the like, recognition, identification, determination, testing, and the like in image processing to be used in the factory automation (FA) field. For example, the present invention can be used for positioning of an electrode of an integrated circuit (IC) for bonding thereof, and the like.