Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-11-15
2003-07-08
Dastouri, Mehrdad (Department: 2623)
Image analysis
Pattern recognition
Template matching
C382S194000, C382S225000, C382S295000, C382S296000, C382S298000
Reexamination Certificate
active
06591011
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for processing plural pictures to generate a synthesized picture.
2. Description of the Related Art
In keeping up with improvement in computer performance, a wide variety of processing algorithms have been developed in many technical fields to yield tremendous results. Among these image processing techniques, pattern matching is stirring up notice.
The problem of pattern matching, in case the coordinates of points of point sets are more or less inaccurate, as in feature points afforded by e.g., pleissey corner detection or Kanade Lucas Tomari (so called KLT) corner detection algorithm in two point sets S={S
1
, . . . , S
n
) and Q={Q
1
, . . . , Q
m
} in a Euclid d-dimensional space E
d
, having different densities. What is to be done in such case is to discriminate inliers, as matched points, from outliers, as non-matched points.
Given a transformation T, accuracy of the matching can be calculated using the Haussdorf distance in percent representation. That is, with the so-called n-k outlier effect removed, by employing this Haussdorf distance, matching accuracy is given as shown in the following equation (1):
h
k
({
S, Q
})=min
kS&egr;S
min
Q&egr;Q
d
(
S, Q
) (1).
In the above equation (1), mink means returning the least kth element, and d(·,·) is a distance function. As stated in “A. Efrat and M. J. Katz, Computing Fair and Bottleneck Matchings in Geometric Graphs, in Proc. 7th Annu. Internat. Sympos. Algorithms Comp., pages 115-125, 1996”, the defect of this Haussdorf index is that a sole point is eventually matched a plural number of times. In such case, meaningful results cannot be achieved in visual geometric like images having different zoom values.
One of the latest technologies in the pattern matching is disclosed in “H. Alt and L. Guibas, Resemblance of Geometric Objects, in “Jorg-Rudiger Sack and Jorge Urruitia, editors, Handbook of Computational Geometry, Elsevier Science Publishers B. V. North-Holland, Amsterdam, 1998”. Irani and Raghavan have proposed in “Sandy Irani and Prabhakar Raghavan, Combinatorial and Experimental Results for Randomized Point Matching Algorithms, in Proc. 12th annual ACM Symposium on Computational Geometry, pages 68-77, 1996”, a randomized Monte Carlo method as a technique for finding the transformation under the supposition that the sets S and Q are matched at least densely, that is that at least portions of points are matched. This randomized Monte Carlo method is based on involute feature points defining the transformation and represents global processing.
The local processing, employed extremely widely in pattern matching, assumes the space of parameters defining a space of a transformation matrix T and applies to these generating parameters the branch and bound method as shown in “Michiel Hagedoorn and Remco C. Veltkamp, Reliable and Efficient Pattern Matching Using and Affine Invariant Metric, Technical Report UU-CS-1997-33, Utrecht University, Department of Computing Science, October, 1997” or in “D. Mount, N. Netanyahu and J. Le Moigne, Improved Algorithms for Robust Point Pattern Matching and Applications to Image Registration, in 14th Annual ACM Symposium on Computational Geometry, 1998”. For example, if translation and/or rotation of a plane is allowed, a 3×3 matrix generated by three parameters (x, y, &thgr;), representing the amount and direction of translation, expressed as T=R
2
×[0, 2&pgr;] using the homogeneous coordinates, is defined.
As another technique for finding the pattern matching, there is a majority decision method, which represents an example of generalization of the Hough transformation, as disclosed in “T. Akutsu, H. Tamaki and T. Tokuyama, Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Set, Discrete and Computational Geometry, pages 207-331, 1998”. Recently, Indyk et al., has proposed in “P. Indyk, R. Motwani and S. Venkatasubramanian, Geometric Matching under Noise: Combinatorial Bounds and Algorithms, In SODA: Symposium of Datastructures and Algorithms 1999 and in “M. Gavrirov, P. Indyk, R. Motowni and S.Venkatasubramanian, Geometric Pattern Matching: A Performance Study, In. Proc. of the 15th Symp. of Comp. Geo., 1999” an algorithm for executing pattern matching by taking the diameter of a point set into account if there exists a noise. Also, Cardoze and Schulman related in “Cardoze and Schulman, Pattern Matching for Spatial Point Sets, In FOCS: IEEE Symposium on Foundations of Computer Science (FOCS), 1998” the pattern matching with the number theory and proposed a fast algorithm of executing Fourier transform in accordance with the diameter of a point set.
In the field of the above-described picture processing, it is desired to further raise the efficiency of the technique for a user to generate a synthesized picture. Among the techniques for the user to generate synthesized pictures, there are such a system of synthesizing a picture taking into account a digital still camera having lens distortion or an offset optical system in a camera such as a sequence of pictures making up a motion picture.
However, difficulties are encountered in applying a geometrical model for picture synthesis, such that the processing volume becomes enormous while the processing becomes extremely time-consuming. Consequently, a demand is raised for establishing a technique for efficiently synthesizing a picture using a geometrical model.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a picture processing method and apparatus whereby plural pictures can be synthesized efficiently by applying a geometrical model.
In one aspect, the present invention provides an image processing method including a feature extracting step of extracting feature points of two or more images, a matching step of comparing feature points of one of the two or more images to those of other images for effecting matching and a computing step of performing computations for changing the relative position between the one image and the other image based on the results of the matching step.
In this image processing method, feature points of each of two or more images are extracted, the feature points of one of the two or more images are compared to those of the other image or images to effect matching. Based on the results of this matching, computations are carried out to change the relative positions of the one image and the other image or images to synthesize the two or more images.
In another aspect, the present invention provides an image processing apparatus including feature extracting means for extracting feature points of two or more images, matching means for comparing feature points of one of the two or more images to those of other images for effecting matching and computing means for performing computations for changing the relative position between the one image and the other image based on the results of matching by the matching means.
In this image processing apparatus, feature points of each of the two or more images are extracted by the feature extracting means and the feature points of one of the images are compared to those of the other image or images by the matching means by way of matching. Based on the results of this matching, computations are executed by the computing means such as to change the relative position between the one image and the other image or images to synthesize the two or more images.
REFERENCES:
patent: 6006226 (1999-12-01), Cullen et al.
patent: 6111983 (2000-08-01), Fenster et al.
patent: 6348980 (2002-02-01), Cullen et al.
S. Irani & P. Raghavan, “Combinatorial and Experimental Results for Randomized Point Matching Algorithms,” Proceedings of 12th Annual ACM Symposium on Computational Geometry,May 1996, pp. 68-77.
A. Efrat & M. Katz, “Computing Fair and Bottleneck Matchings in Geometric Graphs,” Proceedings—7th Annual In
Dastouri Mehrdad
Sony Corporation
LandOfFree
Picture processing method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Picture processing method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Picture processing method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3104555