Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-06-22
2003-09-16
Mariam, Daniel G. (Department: 2621)
Image analysis
Pattern recognition
Template matching
C382S181000, C382S203000, C382S209000, C382S220000
Reexamination Certificate
active
06621929
ABSTRACT:
BACKGROUND
1. Technical Field
The present invention relates generally to image matching and, in particular, to a method for matching images using spatially-varying illumination change models.
2. Background Description
Image matching or image alignment is a fundamental tool in many areas of computer vision, such as, for example, target tracking, motion analysis, object recognition, and automated visual inspection. For target tracking, image matching is used to accurately locate target objects in temporal image sequences. Various image matching techniques provide point or region correspondence in an image sequence for image motion analysis. An essential step for object recognition is pose determination, which can be accomplished by image alignment techniques. In automated visual inspection, image alignment between the inspection image and the reference image is usually the first and the most crucial step.
A large number of image matching techniques have been described in literature to improve the accuracy, generality, robustness, and speed of image matching. They can be classified into two categories, i.e., the feature-based matching approach and the intensity-based matching approach.
The feature-based matching approach requires reliable feature extraction as well as robust feature correspondence to overcome missing feature and outlier problems due to partial occlusion. The main advantage of the feature-based matching approach is robustness against illumination changes.
The intensity-based matching approach is primarily based on the SSD (Sum of Squared Differences) formulation, which does not require feature extraction or direct correspondence between two sets of features. However, this approach is more sensitive to illumination changes than the feature-based approach. In addition, the conventional SSD-based formulation is not robust against occlusion. The SSD formulation is further described by P. Anandan, in “A Computational Framework and an Algorithm for the Measurement of Visual Motion”, International Journal of Computer Vision, Vol. 2, No. 3, 1989, pp. 283-310.
An object matching algorithm based on robust estimation and eigenspace projection to recover affine transformations for an object under different views is described by M. J. Black and A. D. Jepson, in “EigenTracking: Robust Matching and Tracking of Articulated Objects Using a View-based Representation”, International Journal of Computer Vision, Vol. 26, No. 1, pp. 63-84, 1998. The eigenspace is computed from a collection of images for the same object under different views. Robust estimation is used to allow for partial occlusion.
A region matching and tracking algorithm based on robust framework is described by P. N. Belhumeur and G. D. Hager, in “Efficient Region Tracking With Parametric Models of Geometry and Illumination”, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 20, No. 10, pp. 1025-1039, 1998. According to the article, the illumination changes are modeled into the SSD formulation using a low-dimensional linear sub-space determined from several images of the same object under different illumination conditions. The main disadvantage of this algorithm is the need for several images of the same object under different illumination conditions to compute the linear sub-space before the tracking process.
Accordingly, it would be desirable and highly advantageous to have a method for matching images that is robust against illumination changes and that does not require several images of the same object under different illumination conditions.
SUMMARY OF THE INVENTION
The present invention is directed to a method for matching images using spatially-varying illumination change models. The present invention is very useful for computer vision applications such as, for example, target tracking, motion analysis, object recognition, and automated visual inspection.
According to a first aspect of the present invention, a method for matching images includes the step of providing a template image and an input image. The images include pixels, each pixel having an intensity associated therewith. An energy function formed by weighting a sum of squared differences of data constraints corresponding to locations of both the template image and the input image is minimized to determine estimated geometric and spatially-varying illumination parameters for the input image with respect to the template image. The estimated geometric and spatially-varying illumination parameters are outputted for further processing.
According to a second aspect of the present invention, the method further includes the step of partitioning the template image into blocks of pixels. A reliability measure is determined for each pixel in each block. Pixel locations are identified for each block having the largest reliability measure.
According to a third aspect of the present invention, the minimizing step further includes the step of calculating a Hessian matrix and a gradient vector of the energy function based on an initial guess of geometric and illumination parameters. The initial guess is updated based on the calculating of the Hessian matrix and the gradient vector of the energy function. The Hessian matrix and the gradient vector of the energy function are iteratively recalculated until an updated guess is within an acceptable increment from a previous updated guess.
According to a fourth aspect of the present invention, the method further includes the step of smoothing the template image to reduce noise effects.
According to a fifth aspect of the present invention, the minimizing step further includes the step of incorporating a spatially-varying illumination change factor into the data constraints to account for pixel intensity changes due to illumination effects.
According to a sixth aspect of the present invention, the minimizing step includes the step of alleviating errors due to nonlinear characteristics in an optical sensor using a consistency measure of image gradients and a nonlinear function of pixel intensities.
According to a seventh aspect of the present invention, the minimizing step includes the step of modeling spatially-varying illumination multiplication and bias factors using low-order polynomials.
According to an eighth aspect of the present invention, the minimizing step further includes the step of dynamically assigning weights to the data constraints based on residues of the data constraints, a consistency measure of image gradients, and a non-linear function of the pixel intensities.
According to a ninth aspect of the present invention, the method further includes the step of generating an initial guess corresponding to initial geometric and illumination parameters of the input image.
REFERENCES:
patent: 5471252 (1995-11-01), Iu
patent: 5495537 (1996-02-01), Bedrosian et al.
patent: 5581629 (1996-12-01), Hanna et al.
patent: 5745668 (1998-04-01), Poggio et al.
patent: 5911035 (1999-06-01), Tsao
Hager, et al “Efficient Region Tracking with Parametric Models of Geometry and Illumination”, pp. 1025-1039, IEEE, 1998.*
Guillaume, et al “A Gauss-Newton-Like Optimization Algorithm for “Weighted” Nonlinear Least-Squares Poblems”, pp. 222-2228, IEEE, 1996.*
Snyder “On the mathematical foundations of smoothness constraints for the determination of optical flow and for surface reconstruction”, pp. 1105-1114, IEEE, 1991.*
Barron, et al. “Performance of optical flow techniques”, pp. 43-77, International Journal Computer Vision, 1994.*
Zhang “Modelling geometric structure and illumination varation of a scene from real images”, pp. 1041-1046, IEEE, 1998.*
Wu, et al. “A correlation-Relaxation-Labeling framework for computing optical flow-Tmplate matching from a new perspective”, pp. 843-853, IEEE, 1995.
Fang Ming
Lai Shang-Hong
Mariam Daniel G.
Siemens Corporate Research Inc.
LandOfFree
Method for matching images using spatially-varying... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for matching images using spatially-varying..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for matching images using spatially-varying... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3072078