Mechanism for determining parallax between digital images
First Claim
1. For use with a digitized image processing system wherein first and second digitized images respectively representative of first and second views of a contoured surface as seen from first and second respectively different look angles are generated, said first and second digitized images containing respective first and second arrays of image pixels, a method of determining parallax between locations on said contoured surface as seen in said first digitized image and corresponding locations on said contoured surface as seen in said second digitized image, comprising the steps of:
- (a) correlating image contents of a plurality of first image pattern windows distributed throughout said first array, each first image pattern window containing a respective sub-array of pixels of said first array, with image contents of respective first correlation windows positioned at locations including initial and subsequent correlation windows positioned at respective initial and subsequent locations, each first correlation window containing a respective sub-array of pixels of said second array, by different placements of said first correlation windows within a plurality of first search windows distributed throughout said second array to determine the locations, where said different placements of the first correlation windows include initial different placements of the initial correlation window within the initial search window to determine the initial location of the initial correlation window, and subsequent different placements of the subsequent correlation window within the subsequent search window to determine the subsequent location of the subsequent correlation window responsive to one of an initial parallax responsive to the initial location and a subsequent parallax;
(b) identifying, on the basis of correlations carried out in step (a), an initial pixel of said second array representing an initial location on said contoured surface corresponding to an initial prescribed pixel of said first array responsive to said initial different placements, and identifying, on the basis of correlations carried out in step (a), pixels of said second array representing locations on said contoured surface that correspond to prescribed pixels of said first array responsive to said subsequent different placements;
(c) determining the initial parallax between the initial pixel and the initial prescribed pixel, and determining the parallax between respective ones of the prescribed pixels of said first array and the pixels of said second array; and
(d) determining the parallax between locations on said contoured surface as seen in said first digitized image and corresponding locations on said contoured surface as seen in said second digitized image, in accordance with the initial parallax and the parallax determined in step (c).
1 Assignment
0 Petitions
Accused Products
Abstract
A mechanism for determining parallax between first and second digital images employs an iterative image pattern search and correlation process, which is able to rapidly determine the parallax for each pixel that is common to the images captured by a stereo image pair. By the initial use of a dispersed sub-array of reference point pixels distributed throughout a first image array, a similarly dispersed sub-array of tie points, to be used as starting points for subsequent, more densely populated search and correlation steps, can be rapidly obtained for the second image array. The derived parallax values may then be subjected to an interpolation function to sub-pixel accuracies. Once the parallax between the first and second image arrays has been derived, elevations can be computed using a conventional parallax-dependent mechanism.
-
Citations
57 Claims
-
1. For use with a digitized image processing system wherein first and second digitized images respectively representative of first and second views of a contoured surface as seen from first and second respectively different look angles are generated, said first and second digitized images containing respective first and second arrays of image pixels, a method of determining parallax between locations on said contoured surface as seen in said first digitized image and corresponding locations on said contoured surface as seen in said second digitized image, comprising the steps of:
-
(a) correlating image contents of a plurality of first image pattern windows distributed throughout said first array, each first image pattern window containing a respective sub-array of pixels of said first array, with image contents of respective first correlation windows positioned at locations including initial and subsequent correlation windows positioned at respective initial and subsequent locations, each first correlation window containing a respective sub-array of pixels of said second array, by different placements of said first correlation windows within a plurality of first search windows distributed throughout said second array to determine the locations, where said different placements of the first correlation windows include initial different placements of the initial correlation window within the initial search window to determine the initial location of the initial correlation window, and subsequent different placements of the subsequent correlation window within the subsequent search window to determine the subsequent location of the subsequent correlation window responsive to one of an initial parallax responsive to the initial location and a subsequent parallax; (b) identifying, on the basis of correlations carried out in step (a), an initial pixel of said second array representing an initial location on said contoured surface corresponding to an initial prescribed pixel of said first array responsive to said initial different placements, and identifying, on the basis of correlations carried out in step (a), pixels of said second array representing locations on said contoured surface that correspond to prescribed pixels of said first array responsive to said subsequent different placements; (c) determining the initial parallax between the initial pixel and the initial prescribed pixel, and determining the parallax between respective ones of the prescribed pixels of said first array and the pixels of said second array; and (d) determining the parallax between locations on said contoured surface as seen in said first digitized image and corresponding locations on said contoured surface as seen in said second digitized image, in accordance with the initial parallax and the parallax determined in step (c). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. For use with a digitized image processing system wherein first and second digitized images respectively representative of first and second views of a contoured surface as seen from first and second respectively different look angles are generated, said first and second digitized images containing respective first and second arrays of image pixels, a method of determining parallax between locations on said contoured surface as seen in said first image and locations on said contoured surface as seen in said second image, comprising the steps of:
-
(a) defining a first sub-array of pixels of said first image of said contoured surface, said first sub-array of pixels encompassing that portion of said contoured surface seen in both of said first and second images; (b) defining a first image pattern window and a subsequent image pattern window about each of the pixels of said first sub-array, such that a respective first image pattern window contains a respective pixel of said first sub-array and a plurality of neighboring pixels; (c) defining a plurality of first search windows including respective first and subsequent search windows among said second array of image pixels, each of said first search windows encompassing a respectively different second sub-array of pixels of said second image that contains a pixel located geometrically proximate to the location of a respective pixel of said first sub-array of pixels of said first image, the size of a first search window being larger than the first image pattern window; (d) defining, within the respective first search window, a first comparison window sized in correspondence with said first image pattern window, and within the subsequent search window, a subsequent comparison window; (e) comparing, for respectively different initial locations of the first comparison window within the respective first search window, the contents of said first image pattern window with the contents of said first comparison window to determine an initial location of the first comparison window within the respective first search window, and comparing, for respectively different subsequent locations of the subsequent comparison window within the subsequent search window, the contents of the subsequent image pattern window with the contents of said subsequent comparison window to determine a subsequent location of the subsequent comparison window responsive to one of an initial parallax responsive to the initial location and an adjacent parallax; (f) specifying an initial pixel of said second array representing an initial surface location on said contoured surface corresponding to an initial respective first pixel of said first sub-array of pixels of said first image, and specifying which pixels among the image pixels of said second array represent locations on said contoured surface corresponding to the respective pixels of said first sub-array of pixels of said first image, in accordance with the comparison carried out in step (e); and (g) determining the parallax between locations on said contoured surface as captured by said first image with corresponding locations on said contoured surface as captured by said second image in accordance with separations between respective pixels of said first sub-array and the initial pixel and the pixels of the image pixels of said second array specified in step (f). - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. For use with a digitized image processing system wherein first and second digitized images respectively representative of first and second views of a contoured surface as seen from first and second respectively different look angles are generated, said first and second digitized images containing respective first and second arrays of images pixels, a method of determining parallax between locations on said contoured surface as seen in said first digitized image and corresponding locations on said contoured surface as in said second digitized image, comprising the steps of:
-
(a) defining, within said first array of image pixels, a sub-array of reference pixels, said sub-array of reference pixels being distributed over that portion of said contoured surface contained in both of said first and second digitized images; (b) defining, about each respective reference pixel of said sub-array, a respective first image pattern window and a subsequent image pattern window, such that the respective first image pattern window contains a respective reference pixel and a plurality of neighboring pixels; (c) defining a plurality of first search window including respective first and subsequent search windows distributed among said second array of pixels, each of said first search window encompassing a respectively different plurality of pixels that contains a tentative tie point pixel located geometrically proximate to the location of a respective reference pixel of said sub-array, a size of a first search window being larger than a first image pattern window; (d) defining, within the respective first search window, a first correlation window sized in correspondence with said first image pattern window and within the subsequent search window, a subsequent correlation window; (e) correlating, for respectively different initial locations of the first correlation window within the respective first search window, the contents of said first correlation window with the contents of said first image pattern window to determine an initial location of the first correlation window within the respective first search window, and correlating, for respectively different subsequent locations of the subsequent correlation window within the subsequent search window, the contents of the subsequent image pattern window with the contents of said subsequent correlation window to determine a subsequent location of the subsequent correlation window responsive to one of an initial parallax responsive to the initial location and an adjacent parallax; (f) identifying an initial pixel of said second array representing an initial surface location on said contoured surface corresponding to an initial respective first pixel of said sub-array, and identifying which pixels, among the image pixels of said second array, represent locations on said contoured surface that correspond to the respective reference pixels of the sub-array, in accordance with correlations carried out in step (e); (g) determining the parallax between respective identified tie point pixels and associated tentative tie point pixels including the initial pixel and the pixels of said second array identified in step (f); and (h) determining the parallax between locations on said contoured surface as seen in said first digitized image and corresponding locations on said contoured surface as seen in said second digitized image, in accordance with the parallax, determined in step (g). - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49)
-
-
50. A method of determining parallax between different digitized first and second images of a surface, comprising the steps of:
-
(a) correlating an initial pattern window including a first tie-point pixel of the first image with an initial correlation window in the second image by different placements of said initial correlation window in an initial search window including a second tie-point pixel of the second image to determine an initial placement, and determining a tie-point parallax between the first tie-point and the initial placement of the initial correlation window in the initial search window; (b) correlating a subsequent pattern window including subsequent pixels of the first image with a subsequent correlation window in the second image by different placements of the subsequent correlation window in a subsequent search window of the second image to determine a subsequent placement responsive to one of the tie-point parallax and a subsequent parallax, and determining the subsequent parallax between one of the subsequent pixels of the first image and the subsequent placement of the subsequent correlation window in the subsequent search window; and (c) determining the parallax between pixels of the first and second images of the surface using one of the tie-point and the subsequent parallax. - View Dependent Claims (51, 52, 53)
-
-
54. An apparatus for determining parallax between different digitized first and second images of a surface, comprising:
-
(a) first means for correlating an initial pattern window including a first tie-point pixel of the first image with an initial correlation window in the second image by different placements of the initial correlation window in an initial search window including a second tie-point pixel of the second image to determine an initial placement, and determining a tie-point parallax between the first tie-point and the initial placement of said initial correlation window in the initial search window; (b) second means for correlating a subsequent pattern window including subsequent pixels of the first image with a subsequent correlation window in the second image by different placements of the subsequent correlation window in a subsequent search window of the second image to determine a subsequent placement responsive to one of the tie-point parallax and a subsequent parallax, and determining the subsequent parallax between one of the subsequent pixels of the first image and the subsequent placement of the subsequent correlation window in the subsequent search window; and (c) third means for determining the parallax between pixels of the first and second images of the surface using one of the tie-point and the subsequent parallax. - View Dependent Claims (55, 56, 57)
-
Specification