Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-12-29
2003-12-02
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Template matching
C382S278000
Reexamination Certificate
active
06658149
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a scheme for identifying a gray-scale image. In particular, the present invention relates to a technique of simultaneously improving noise tolerance and distortion tolerance in gray-scale-image identification and recognition that are essential for image pattern recognition, motion analysis, and stereo vision.
2. Description of the Background Art
Distortion tolerance and noise tolerance are serious problems to be solved for gray-scale-image identification techniques.
The techniques to improve distortion tolerance fall into three approaches. They are (1) combinational search, (2) energy minimization, and (3) affine parameter determination.
The first approach, i.e., the combinational search binarizes an input gray-scale image into an input black-point set and then matches the input black-point set and target black-point set. This first approach finds an optimal solution among black-point combinations whose number is of the factorial of the number of points contained in the input black-point set, so that this approach diverges the number of processes to obtain an optimal solution.
A technique of restricting the number of candidate solutions by setting constraints has been studied to prune the branches of a decision search tree to limit the number of processes for an optimal solution. This is disclosed in, for example, H. S. Baird, “Model-Based Image Matching Using Location,” Cambridge, Mass.: MIT Press, 1985. Under the constraints, solution algorithm has been proposed for a problem of determining whether or not two point-sets match with each other through congruent transformation (rotation and translation) and a problem of determining whether or not two point-sets match with each other through similar transformation (rotation, scale change, and translation). The number of processes involved in these algorithms is of the order of power of the number of points contained in a point-set. This algorithm is described in, for example, S. Umeyama, “Parametrized point pattern matching and its application to recognition of object families,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 15, No. 2, pp. 135-144, 1993.
It is difficult, however, to find general constraints for the above algorithms, and the above algorithms still involve a large number of processes and provide no solution for affine transformation (e.g., rotation, scale change, shearing, and translation) that includes shearing in addition to similar transformation.
On the other hand, the constraints cause local contradiction, and to resolve the local contradiction, discrete relaxation has been proposed. The discrete relaxation method employs interpoint matching coefficients to successively update matching states and converge into a consistent solution, as disclosed in, for example, A. Rosenfeld, R. A. Hummel, and S. W. Zucker, “Scene labeling by relaxation operations,” IEEE Trans., Vol. SMC-6, No. 6, pp. 420-433, 1976. The discrete relaxation, however, provides no guidance for rules for updating matching states or a way of setting matching coefficients, involves many processes due to iterations, and guarantees no convergence.
Moreover, these techniques are based on the binarization of a gray-scale image. If the image involves noise, degradation, or background texture, the binarization of the image will fail. Therefore, it is impossible for these techniques to achieve distortion tolerance from the beginning.
The second approach, i.e., the energy minimization is based on dynamic analogy. This approach formulates an image identification problem as an optimization problem based on the energy minimization principle. One effective technique based on this approach introduces image identification constraints into energy functions based on the regularization theory, as disclosed in, for example, T. Poggio, V. Torre, and C. Koch, “Computational vision and regularization theory,” Nature, Vol. 317, No. 6035, pp. 314-319, 1985.
Solutions for the energy minimization problem based on a calculus of variations, stochastic relaxation, etc., are disclosed in, for example, B. K. P. Horn and B. G. Schunck, “Determining optical flow,” Artificial Intelligence, Vol. 17, pp. 185-203, 1981; M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: active contour models,” Int. Journal of Computer Vision, Vol. 1, No. 4, pp. 321-331, 1988; and S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 6, No. 6, pp. 721-741, 1984.
These are advantageous in analytically or algebraically handling matching problems. They, however, find local optimal solutions from continuous translations based on iterated infinitesimal translations. Accordingly, it is difficult for them to deal with finite or discontinuous translations, or guarantee a convergence to a global optimal solution. In addition, they involve a large number of processes.
The third approach, i.e., the affine parameter determination binarizes an input gray-scale image into an input black-point set and matches it and a target black-point set. This approach directly finds affine parameters that maximize the matching of the input and target images from the iterated solutions of simultaneous linear equations. To evaluate the matching of two images, one technique checks to see if an average of the distances between the proximal black points of the two images has been minimized, as disclosed in T. Wakahara and K. Odaka, “Adaptive normalization of handwritten characters using global/local affine transformation,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 20, No. 12, pp. 1332-1341, 1998. Another technique to evaluate the matching of two images checks to see if a likelihood between the two images has been maximized on an assumption that the positions of black points vary according to a normal distribution, as disclosed in Japanese Patent Application No. Hei10-255042 (1998) “Point Pattern Normalization Method and Apparatus.” This affine parameter determination is a promising image identification approach in which image can be identified with respect to arbitrary affine parameter. This approach, however, is based on binarization like the above combinational search approach. Accordingly, if an image involves superimposed noise, degradation, or background texture, the binarization itself will fail. Then, it is impossible for this approach to obtain distortion tolerance as such.
On the other hand, to improve noise tolerance, there is a technique of employing normalized cross-correlation as a matching measure for gray-scale images, as disclosed in, for example, A. Rosenfeld and A. C. Kak, Digital Picture Processing, Second edition, San Diego, Calif.: Academic Press, 1982, Chap. 9. It has theoretically been verified that the normalized cross-correlation has a tolerance for a blurring operation on images, as described in, for example, T. Iijima, “Pattern Recognition,” Tokyo: Corona, 1973, Chap.6. The normalized cross-correlation is effective to identify an image that involves superimposed noise, degradation, or background texture, as described in, for example, M. Uenohara and T. Kanade, “Use of Fourier and Karhunen-Loeve decomposition for fast pattern matching with a large set of templates,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 19, No. 8, pp. 891-898, 1997; and M. Sawaki and N. Hagita, “Recognition of degraded machine-printed characters using a complementary similarity measure and error-correction learning,” IEICE Trans. Information and Systems, Vol. E79-D, No. 5, pp. 491-497, 1996. An image identification operation based on the normalized cross-correlation may handle a congruent transformation (e.g., rotation or translation) of an image by thoroughly scanning using templates. This technique, however, has an intrinsic problem of deteriorating correlation values when an affine transformation involving scale change and shearing is applied to an image. In addition, it is practically imp
Sugimura Toshiaki
Wakahara Toru
Chang Jon
Nippon Telegraph & Telephone Corporation
LandOfFree
Scheme for identifying gray-scale image does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheme for identifying gray-scale image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for identifying gray-scale image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3096535