Image analysis – Applications – 3-d or stereo imaging analysis
Reexamination Certificate
2000-05-04
2003-08-12
Ahmed, Samir (Department: 2623)
Image analysis
Applications
3-d or stereo imaging analysis
C345S422000
Reexamination Certificate
active
06606406
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to computer vision and more particularly to a method and a system for progressive stereo matching of digital images that represent a scene.
2. Related Art
Stereo matching of digital images is widely used in many computer vision applications (such as, for example, fast object modeling and prototyping for computer-aided drafting (CAD), object segmentation and detection for human-computer interaction (HCI), video compression, and visual surveillance) to provide three-dimensional (3-D) depth information. Stereo matching obtains images of a scene from two or more cameras positioned at different locations and orientations in the scene. These digital images are obtained from each camera at approximately the same time and points in each of the image are matched corresponding to a 3-D point in space. In general, points from different images are matched by searching a portion of the images and using constraints (such as an epipolar constraint) to correlate a point in one image to a point in another image.
Several types of matching techniques exist and generally may be classified into two broad categories: feature matching and template matching. Feature matching extracts salient features from the images (such as corners and edge segments) and matches these features across two or more views. One disadvantage of feature matching, however, is that only a small subset of image pixels is used to match features. This means that if image pixels used in the matching process are unreliable then only a coarse and inaccurate 3-D representation of the actual scene is produced. Template matching uses an assumption that portions of images have some similarity and attempts to correlate these similarities across views. Although this assumption may be valid for relatively textured portions of an image and for image pairs having only small differences, the assumption may lead to unreliable matching at occlusion boundaries and within featureless regions of an image. In addition, template matching yields many false matches due in part to the unreliability of matched image pixels.
These and other existing stereo matching techniques have the disadvantage of having difficulty specifying an appropriate search range and being unable to adapt the search range depending on the observed scene structure. Existing dense matching techniques use the same search range (such as a small search window) for the entire image and thus may yield many false matches. In addition, some matching techniques consider only one match at a time and propagate the match in a small area, which also has the disadvantage of yield many false matches.
Accordingly, what is needed is a method and system for stereo matching that is capable of reducing false matches by adapting a search range depending on the scene structure. Further, this method and system would start with reliable pixel matches and progressively add reliable and unambiguous matches. What is also needed is a method and system for stereo matching that uses an adaptable search range that is dynamically determined by unambiguous pixel matches. Whatever the merits of the above-mentioned systems and methods, they do not achieve the benefits of the present invention.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art as described above and other limitations that will become apparent upon reading and understanding the present specification, the present invention includes a method and system for performing progressive stereo matching of digital images. In particular, the present invention uses a progressive iterative technique that uses a disparity gradient limit principle and a least commitment strategy to determine generally unambiguous pixel matches. The progressive iterative method of the present invention begins with a few reliable pixel matches and during successive iterations finds progressively more unambiguous pixel matches based on a novel correlation technique and a correlation score associated with a pixel match. Unambiguous pixel matches found in a previous iteration are used to define search ranges for subsequent pixels to reliably and efficiently determine matches in a current iteration. The present invention eliminates the problems of dense matching techniques whereby the same search range is used for the entire image. In the present invention, potentially false matches are reduced by dynamically changing the search range based on unambiguous matches found in previous iterations.
The present invention provides reliable and accurate pixel matching that begins with a reliable set of pixel matches and quickly adds a greater number of reliable pixel matches based on a pixel correlation. In addition, because at each step of the process the pixel matches are unambiguous, the present invention is highly efficient and fast because backtracking due to unreliable pixel matches is eliminated. Unlike many prior stereo matching techniques, the present invention works well with images containing featureless regions and is capable of changing an orientation of a search range based on the current set of reliable pixel matches.
In general, the method of the present invention includes determining a set of reliable (or unambiguous) pixel matches and progressively adding a greater number of unambiguous pixel matches to the set. The initial set of reliable pixel matches may be obtained either automatically (using a suitable matching technique that yields reliable pixel matches) or manually (such as through user input). Pixel matches are sought by defining a search range for each image and examining pixels within the search ranges for potential matches. The search range is capable of being rotated, and is part of a novel correlation technique of the present invention that provides a more robust estimate of pixel match reliability. After an iteration the set of reliable pixel matches acts as a constraint and helps define a new search range. This dynamic search range reduces potential matching ambiguities and increases the robustness of the process. Potential pixel matches found in the search ranges are tested for ambiguity and any unambiguous matches are selected and added to the set of reliable pixels matches. The ambiguity testing includes determining a correlation score for the pixel match and classifying the match based on the correlation score. The present invention also includes a system for progressive image matching that incorporates the method of the present invention.
REFERENCES:
patent: 6028672 (2000-02-01), Geng
patent: 6137902 (2000-10-01), Kinoshita et al.
patent: 6519358 (2003-02-01), Yokoyama et al.
M. Lhuillier and L, Quan, “Image interpolation by joint view triangulation”, inProc. Conf. on Computer Vision and Pattern Recognition, vol. 2, pp. 139-145, Colorado, Jun. 1999.
Q. Chen and G. Medioni, “A volumetric stereo matching method: application to image-based modeling”, inProc. Conf. on Computer Vision and Pattern Recognition, vol. 1, pp. 29-34, Jun. 1999.
Shan Ying
Zhang Zhengyou
Ahmed Samir
Fischer Craig S.
Lyon & Harr L.L.P.
Microsoft Corporation
LandOfFree
System and method for progressive stereo matching of digital... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for progressive stereo matching of digital..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for progressive stereo matching of digital... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3103181