Flash system for fast and accurate pattern localization

[0002] 1. Field of the Invention

[0003] The present invention relates to improving images and more particularly to object localization with an advanced search hierarchy.

[0004] 2. Description of the Prior Art

[0005] The needs for accurate and efficient object localization prevail in many industrial applications, such as automated visual inspection and factory automation. The efficiency of the object localization system is directly related to the throughput of the product. In addition, the machine vision system should also be general enough to perform different kinds of tasks in a very short period of task switching time. This can significantly increase the applicability as well as the productivity of the system, which is very important for adapting to the fast changing needs of customers and markets.

[0006] The image reference approach is very popular in automatic visual inspection due to its general applicability to a variety of inspection tasks. This is further described by R. T. Chin in “Automatic Visual Inspection: 1981 to 1987”, Computer Vision, Graphics, and Image Processing, Vol. 41, No. 3, pp. 346-381, 1988. However, it requires very precise alignment of the inspection pattern in the image. To achieve very precise pattern alignment, traditional template matching is extremely time-consuming when the search space is large. Some methods have been proposed to resolve this alignment problem. These are described by T. S. Newman and A. K. Jain in “A Survey Of Automatic Visual Inspection”, Computer Vision and Image Understanding, Vol. 61, No. 2, pp. 231-262, 1995; by A. A. Rodriguez and J. R. Mandeville in “Image Registration For Automated Inspection Of Printed Circuit Patterns Using CAD Reference Data”, Machine Vision and Applications, Vol. 6, pp. 233-242, 1993; and by T. Hiroi, S. Maeda, H. Kubota, K. Watanabe and Y. Nakagawa in “Precise Visual Inspection For LSI Wafer Patterns Using Subpixel Image Alignment”, Proc. Second IEEE Workshop on Applications of Computer Vision, pp. 26-34, Florida, December 1994. Rodriguez and Mandeville proposed an image registration technique by fitting feature points in the zero-crossings extracted from the inspection image to the corresponding points extracted from the CAD model via an affine transformation. However, the correspondence between the two set of feature usually can not be reliably established. Hiroi et al. presented a sum-of-squared-differences (SSD) based method to determine the shift between the two images. Unfortunately, this method is restricted to recover small shifts.

[0007] The present invention provides a new FLASH (Fast Localization with Advanced Search Hierarchy) system for fast and accurate object localization in a large search space. This object localization system is very useful for applications in automated visual inspection and pick-and-place systems for automatic factory assembly. This system is based on the assumption that the surrounding regions of the pattern within the search range are always fixed. The FLASH system comprises a hierarchical nearest-neighbor search system and an optical-flow based energy minimization system. The hierarchical nearest-neighbor search system produces rough estimates of the transformation parameters for the optical-flow based energy minimization system which provides very accurate estimation results and associated confidence measures.

[0008] FIG. 1 illustrates a block diagram of the present invention.

[0009] FIG. 2 illustrates an example reference image with a template indicated by the dashed window W.

[0010] FIG. 3 illustrates a flow diagram of a training phase in the object localization system of the present invention.

[0011] FIG. 4 illustrates a flow diagram of an execution phase in the object localization system of the present invention.

[0012] FIG. 5 illustrates hierarchical clustering of data samples in an entire search data set for a fast nearest-neighbor search.

[0013] FIG. 6 illustrates in FIG. 6(a) a first reference image and a template window used for experiments on pattern localization under a large search space and in FIG. 6(b) and FIG. 6(c), two input images with located reference points using the FLASH system of the present invention.

[0014] FIG. 7 illustrates in FIG. 7(a) a second reference image and a template window used for experiments on pattern localization under a large search space and in FIG. 7(b) and FIG. 7(c), two input images with located reference points using the FLASH system of the present invention.

[0015] The needs for accurate and efficient object localization prevail in many industrial applications, such as automated visual inspection and factory automation. Traditional template matching techniques are unsatisfactory due to the enormous amounts of computation involved to achieve very accurate localization, especially when the search space is very large. The present invention provides a new FLASH (Fast Localization with Advanced Search Hierarchy) system for fast and accurate object localization in a large search space. This system is based on the assumption that the surrounding regions of the pattern within the search range are always fixed. The FLASH system comprises a hierarchical nearest-neighbor search system and an optical-flow based energy minimization system. The hierarchical nearest-neighbor search system produces rough estimates of the transformation parameters for the optical-flow based energy minimization system, which provides very accurate estimation results and associated confidence measures. The hierarchical nearest-neighbor search system first computes selected wavelet features from the image inside the template window as the input feature vector. In the training phase, the same feature extraction process is applied to the transformed reference image for a discrete set of transformation parameters sampled from the search space, and then these feature vectors are clustered using hierarchical competitive networks. In the online execution phase, a rough estimate of the transformation parameters can be obtained using the hierarchical nearest-neighbor search system for the feature vector computed from the input image. The optical-flow based energy minimization system is subsequently applied to provide a very accurate estimate with a good initial guess supplied by the hierarchical nearest-neighbor search system. This is further described in U.S. patent application Ser. No. 08/993,850 entitled “A Method For Localization Refinement Of Pattern Images” filed on Dec. 18, 1997, assigned to the same assignee as the present invention and hereby incorporated by reference. Experimental results are given to demonstrate the efficiency of the system.

[0016] A flow diagram of the FLASH system of the present invention is shown in FIG. 1. The FLASH system comprises a hierarchical nearest-neighbor search system 12 and an optical-flow based energy minimization system 14. Hierarchical nearest-neighbor search system 12 produces rough estimates of the transformation parameters for the optical-flow based energy minimization system, which provides very accurate estimation results and associated confidence measures. Hierarchical nearest-neighbor search system 12 first computes selected wavelet features from the image inside the template window as the input feature vector. Then, a rough estimate of the transformation parameters that correspond to the best match of the feature vector computed from the input image and those of the transformed reference image are obtained via hierarchical nearest-neighbor search system 12. Optical-flow based energy minimization system 14 is subsequently applied to provide an accurate estimate with a good initial guess supplied by hierarchical nearest-neighbor search system 12. The details of hierarchical nearest-neighbor search system 12 and optical-flow based energy minimization system 14 are described below.

[0017] The following will describe hierarchical nearest-neighbor search system 12. The 2D object localization problem in machine vision for the image reference approach can be posed as follows. Assume the reference image is denoted by I(x,y) and the template object is given inside a window W={(x,y)|x₀≦x≦x₁,y₀≦y≦y₁} of the reference image. FIG. 2 shows an example reference image with the template window W inside for the pick-and-place assembly application. The 2D object localization must find the best match of the template in the input image F(x,y) with a global transformation T_θ, where T₇₄ can be the 2D rigid transformation containing a translation and rotation or the affine transformation with the transformation parameters given in the vector θ.

[0018] To improve the efficiency of the search system, a best match base on the comparisons between feature vectors computed from the images are found, instead of comparing directly between images. The feature vector matching strategy involves computing representative feature vectors for each image inside the template window and then finding the best match as follows $\begin{array}{cc}\hat{k}=\arg \underset{k}{\min }\sum _{i=1}^p{\left(v_i^{\left(k\right)}-u_i\right)}^2,& \left(1\right)\end{array}$

[0019] where u and v^(k)are p-dimensional feature vectors for the input image F(x,y) and transformed reference images I_k(x,y) inside the template window W . The feature vector used in this example contains wavelet features computed from the image. The feature vectors v^(k)can be computed and stored in the training phase. In the execution phase, only the computation of the feature vector u and the search of the best match between u and all v^(k)is required. The use of the representative feature vector is principally a dimensionality reduction procedure to reduce the storage as well as computation required for the present invention.

[0020] Hierarchical nearest-neighbor search system 12 is used to further reduce the search computational complexity. This system is based on a hierarchical competitive layer neural network. It drastically saves the computational cost in the search of a best match with some additional storage requirement for storing the weights in the neural networks. In addition, it requires some training time for the neural networks in the training phase.

[0021] There are two phases in the object localization system of the present invention that take place in hierarchical nearest-neighbor search system 12, namely a training phase and an execution phase. The flow diagram for the training phase is shown in FIG. 3. The training phase contains a generation of image templates from reference image 30 under different transformation parameter vectors θ₁,K,θ_N32. Reference image 30 and transformation parameter vectors 32 are inputted to image transformation 34 which also receives an input of window W. The output of image transformation 34 flows to image template normalization 36, which includes the re-sampling the image inside the template window into a fixed size and normalization of the re-sampled image intensity value by subtracting its mean and scaling the mean-subtracted image values to unit variance. The re-sampling of the image in a template window to a fix size is for ease of computation in wavelet transformation, which is required in feature generator 38. The computation of representative feature vectors for all of the normalized image templates is performed by feature vector generator 38. This involves computing the wavelet transformation of the normalized image and using some important wavelet coefficients for the representative feature vector. The representative feature vectors are provided to trainer of hierarchical competitive layer neural networks 40.

[0022] The flow diagram of the execution phase is shown in FIG. 4. The execution phase comprises the feature generation within feature vector generator 44 from input image 42 and the hierarchical nearest-neighbor search within searcher 46 for the transformation parameter vector of the best match. Note that the feature generator 44 consists of re-sampling the input image inside the template window, normalizing the re-sampled image values to zero mean and unit variance, taking wavelet transform of the normalized image and using some important wavelet coefficients to be the feature vector. The output of the execution phase is object pose of the best match.

[0023] The hierarchical clustering of the entire feature vectors v₁,K,v_Nis accomplished by using the hierarchical competitive networks. This is further described by S.-H. Lai and M. Fang in “Adaptive Medical Image Visualization Based On Hierarchical Neural Networks And Intelligent Decision Fusion”, Proceedings of IEEE Workshop on Neural Networks for Signal Processing, pp. 438-447, Cambridge, England, 1998. In FIG. 5, the entire feature vector samples are first clustered into M⁽¹⁾clusters 52, namely cluster C₁⁽¹⁾, K, C_M⁽¹⁾. In the second level, each cluster C_j⁽¹⁾can be further partitioned into M_j⁽²⁾sub-clusters, i.e. cluster C_j,1⁽²⁾, K, C_j,M⁽²⁾. Note that the superscripts (1) and (2) stand for the indexes of levels in the hierarchical clustering structure. The hierarchical clustering structure can be repeated for many levels. In the last level 60, each sub-cluster contains some corresponding feature vector samples that fall into it.

[0024] The training of the competitive networks is an unsupervised learning process. The Kohonen's learning rule was employed in this unsupervised training process. This is further described by T. Kohonen in Self-Organization and Associative Memory,2nd Edition, Springer-Verlag, Berlin, 1987. The training of all the competitive networks is performed in a top-to-down approach, i.e. the training of the competitive networks starts from the first level to the last level. The training results for the current level are propagated into the training of the next level.

[0025] The following will describe the optical-flow based energy minimization system, 14 of FIG. 1. This system is an accurate, efficient and robust system for determining precise pattern localization. This system is based on a least squares fitting of the modified optical flow constraints. No feature correspondence is required in this system. However, some points with reliable data constraints are selected for efficient computation in the training phase of the optical-flow based energy minimization system. In addition, this system is robust against noises and uniform illumination changes, since the modified optical flow constraint accounts for the illumination changes. For the present invention, the determination of the 2D rigid with scaling transformation between the input image and pattern image is focused on. Other global transformation models, such as affine transformations, can also be employed in the same framework of the present invention. A rough initial guess for this localization system is supplied by the hierarchical nearest-neighbor search system which is discussed above. The aim of this energy minimization system is to obtain a precise localization of a pattern given a rough initial guess.

[0026] 2D rigid transformations with size changes are considered and the transformed location (u,v) at the location x,y) can be written as $\begin{array}{cc}\left(\begin{array}{c}u\\ v\end{array}\right)=\sigma \left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)\left(\begin{array}{c}x-x_c\\ y-y_c\end{array}\right)+\left(\begin{array}{c}{x}_c+\Delta x\\ y_c+\Delta y\end{array}\right)& \left(2\right)\end{array}$

[0027] where (Δx,Δy) is the translation vector, θ is the rotation angle, σ is the size scaling factor, and (x_c,y_c) is the center of rotation. Due to the fact that there are an infinite number of possible combinations of the translation vector, rotation angle and rotation center for any 2D rigid transformation, the rotation center is chosen to be the same as the center of the template without loss of generality.

[0028] The energy function to be minimized in this system is a sum of squared modified optical flow constraints given as follows $\begin{array}{c}E\left(\Delta x,\Delta y,\theta ,\sigma ,a,b\right)=\sum _i{w}_i(I_{x,i}\left(\Delta x+x_c-x_i\right)+I_{y,i}\left(\Delta y+y_c-y_i\right)+\\ {\sigma \left(f_i\cos \theta +g_i\sin \theta \right)-f_i+I\left(x_i,y_i\right)-\mathrm{aF}\left(x_i,y_i\right)-b)}^2\end{array}$

[0029] where w_iis the weight associated with the i-th constraint selected at the location (x_i,y_i), I_x,iand I_y,iare the partial derivatives of the reference image I(x,y) along the x and y directions respectively at the location (x_i,y_i), f_i=I_x,i(x_i−x_c)+I_y,i(y_i−y_c), g_i=−I_x,i(y_i−y_c)+I_y,i(x_i−x_c, and a is the multiplication factor and b is the offset factor to model the uniform illumination change. This energy minimization problem is a nonlinear least square minimization problem. When a good initial guess is available, the Newton method can be employed to solve this minimization problem very efficiently. The iterative energy minimization system is used that includes a Newton update in each iteration of the iterative energy minimization framework to obtain the least squared solution very efficiently.

[0030] The following will describe experimental results utilizing the present invention. Throughout the experiments, two reference images with the template windows as shown in FIGS. 6aand 7aare used. The sizes of both images are 400×400. The feature vector used in the experiments is the concatenation of normalized wavelet features computed the image. After the dimensionality reduction, the size of the feature vector is 256.

[0031] The search range in the experiments is set to be within ±50 pixels for both the shifts in Δx and Δy, within ±45 degrees for the rotation angle θ, and within ±20% for the scaling factor σ. After the discretization in the search space, there are a total number of 25137 samples in the discrete search space, i.e. N=25137. In one implementation of the hierarchical nearest-neighbor search system of the present invention, two levels in the hierarchical competitive networks are used for clustering.

[0032] The FLASH system of the present invention provides very accurate localization results. Two examples of pattern localization using the FLASH system are shown in FIGS. 6 and 7. FIG. 6 illustrates in FIG. 6(a) a first reference image with a selected reference point indicated by a cross sign used for experiments on pattern localization and in FIG. 6(b) and FIG. 6(c), two input images with located reference points estimated from the FLASH system. FIG. 7 illustrates in FIG. 7(a) a second reference image with a selected reference point indicated by a cross sign used for experiments on pattern localization and in FIG. 7(b) and FIG. 7(c), two input images with located reference points estimated from the FLASH system of the present invention. In this example, the errors in translation estimates are within 0.08 pixels for Δx and Δy, and the errors in rotation estimates are within 0.05 degrees. The execution time for the FLASH system takes less than 0.05 seconds on a Pentium Pro 200 PC running NT 4.0.

[0033] In summary, the present invention provides a FLASH system for fast and accurate object localization in a large search space. The FLASH system comprises a hierarchical nearest-neighbor search system for rough localization and an optical-flow based energy minimization system for precise localization. In the first step of the FLASH system, the hierarchical nearest-neighbor search system is used to obtain a rough localization estimate in an efficient fashion and drastically improves the computational speed of the nearest-neighbor search when the search space is large. The optical-flow based energy minimization system is subsequently applied to provide a very accurate estimate with a good initial guess supplied by the hierarchical nearest-neighbor search system. The efficiency and accuracy of the FLASH system was demonstrated through experiments.

[0034] It is not intended that this invention be limited to the hardware or software arrangement, or operational procedures shown disclosed. This invention includes all of the alterations and variations thereto as encompassed within the scope of the claims as follows.