Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
2000-09-20
2004-08-31
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S154000, C382S240000, C382S284000, C382S294000
Reexamination Certificate
active
06785427
ABSTRACT:
CROSS REFERENCE TO MICROFICHE APPENDIX
Appendix A which is a microfiche appendix of 1 sheet of microfiche and having a total of 19 frames, contains the pseudo code and source code for implementing the image matching method according to one embodiment of the present invention. A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent documents or patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention generally relates to digital image matching; and in particular, the present invention relates to an image matching method using resolution pyramids with geometric constraints.
2. Background of the Invention
Digital photography is becoming more popular today as digital cameras and scanners are becoming widely available. Digital images can be created either by capturing a scene using a digital camera or digitizing a traditional film-based photograph using a scanner. Digital photography has many advantages over the traditional film-based photography. One particular advantage is that digital images can be easily manipulated or edited for better presentation. Furthermore, the digital images can be readily distributed over electronic media such as the internet or electronic mail.
When a photographer captures a scene using a camera, the desired field of view may be larger than the normal field of view of the camera. The photographer could use a panoramic camera or fisheye lens to capture a wide area in a panoramic image. However, such equipment can be expensive and is unavailable to a casual photographer. Digital photography allows a panoramic image to be produced without the need of purchasing a separate panoramic camera or fisheye lenses. For example, a photographer with a digital camera may capture a series of digital pictures of a scene by rotating the camera and taking pictures with the camera pointed in a sequence of different directions. The captured images may then be stitched together to produce a panoramic picture of the scene. Of course, film-based photographs can be digitized, and the panoramic picture can be composed by stitching together the digitized images.
Presently, digital image programs are available for stitching multiple digital images together to form a panoramic picture. Exemplary programs include Ulead Cool 360™, Live Picture PhotoVista™, and MGI PhotoSuite III™. Conventional image matching programs generally use feature correspondence algorithms, which operate by matching features of two source images, to determine how to combine the two images. However, these algorithms can be very slow because the search area to find the matching points is large and the computational burden of the image matching process is great. It may take several minutes to produce a 360° panoramic picture, and often the result is not satisfactory. Therefore, it is desirable to provide more accurate image matching and to perform the imaging matching at a much faster speed.
SUMMARY OF THE INVENTION
According to an embodiment the present invention, an image matching method for matching a first image and an overlapping second image includes (a) generating a first set of working layers of the first image, the, first set of working layers including multiple working layer having successively increasing resolutions from a first working layer having the coarsest resolution to a last working layer having the finest resolution; (b) generating a second set of working layers of the second image, the second set of working layers including multiple working layer having successively increasing resolutions from a first working layer having the coarsest resolution to a last working layer having the finest resolution; (c) determining using correlation an overlap region between the first working layer of the first image and the first working layer of the second image, the overlap region being defined by translational displacement parameters only; (d) selecting the first working layer of the first image; (e) selecting multiple feature points in the first working layer of the first image; (f) determining from within multiple attention areas and using the translational displacement parameters multiple positions in the first working layer of the second image corresponding to the multiple feature points in the first image; (g) determining motion parameters based on the multiple feature points and the multiple positions, the motion parameters describing the positional relationship between the first working layer of the first image and the first working layer of the second image; (h) selecting a next working layer in the first set of working layers of the first image, the next working layer being a working layer with the next higher resolution than the first working layer; (i) selecting a second next working layer having in the same resolution as the next working layer of the first image; (j) selecting multiple feature points in the next working layer of the first image; (k) determining from within multiple attention areas and using the motion parameters multiple positions in the second next working layer of the second image corresponding to the multiple feature points in the first image; (l) determining motion parameters based on the multiple feature points and the multiple positions, the motion parameters describing the positional relationship between the next working layer of the first image and the second next working layer of the second image; and (m) selecting another next working layer in the first set of working layers of the first imaging, the next working layer being a working layer with the next higher resolution than the working layer just processed. Finally, the method repeats steps (i) to (m) using the next working layer of the first image and the second next working layer of the second image until the last working layer of the first image and the last working layer of the second image have been processed.
According to another embodiment of the present invention, the resolution pyramid of each of the images may include two or more working layers, each working layers having reduced image size and decreased resolution from the previous working layer.
The image matching method can be used to stitch together two or more images to create a panoramic picture. The use of resolution pyramids with a novel feature matching algorithm achieves computational efficiency and image matching accuracy not attainable by conventional programs. The present invention will be better understood upon consideration of the detailed description below and the accompanying drawings.
REFERENCES:
patent: 4973111 (1990-11-01), Haacke et al.
patent: 5627915 (1997-05-01), Rosser et al.
patent: 5742710 (1998-04-01), Hsu et al.
patent: 5790206 (1998-08-01), Ju
patent: 6078701 (2000-06-01), Hsu et al.
patent: 6157747 (2000-12-01), Szeliski et al.
patent: 6192156 (2001-02-01), Moorby
patent: 6349114 (2002-02-01), Mory
patent: 6359617 (2002-03-01), Xiong
patent: 6646655 (2003-11-01), Brandt et al.
Correlation (ESSI-CNES-INRIA report Bernard Holtz 1991) (2 pgs).
Les Kitchen et al., “Gray-Level corner detection” Pattern Recognition Letters 1 (1982) 95-102.
ArcSoft, Inc.
Boudreau Leo
Cook Carmen C.
Patent Law Group LLP
Rosario-Vasquez Dennis
LandOfFree
Image matching using resolution pyramids with geometric... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image matching using resolution pyramids with geometric..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image matching using resolution pyramids with geometric... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269275