Mechanism for determining parallax between digital images

Claim 2

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).

Claim 3

A method according to claim 1, wherein step (d) comprises the steps of: (d1) defining a boundary window about each of the prescribed pixels of said first array, such that a respective boundary window contains a respective prescribed pixel and a plurality of neighboring pixels and such that adjacent boundary windows border one another; and (d2) determining the parallax between pixels contained in respective boundary windows and corresponding pixels of said second array, in accordance with the parallax determined in step (c).

Claim 4

A method according to claim 2, wherein step (d2) comprises the steps of: (d2-1) using a respective pixel of said second array identified in step (b) as a reference pixel, correlating the image contents of a second image pattern window, which contains a pixel adjacent to a prescribed pixel and a plurality of neighboring pixels of said first array, with the image contents of a respective second correlation window, said second correlation window containing a pixel displaced with respect to said reference pixel of said second array, in the same manner that said adjacent pixel is displaced with respect to said prescribed pixel of said first array, and a plurality of neighboring pixels of said second array, for different placements of said second correlation window within a second search window of said second array; (d2-2) on the basis of correlation carried out in step (d2-1), identifying which pixel of said second array represents a location on said contoured surface that corresponds to said adjacent pixel within said boundary window of said first array; (d2-3) determining the parallax between said adjacent pixel of said first array and the pixel of said second search window identified in step (d2-1); and (d2-4) using a respective pixel of said second array identified in step (d2-2) as a reference pixel, repeating steps (d2-1)-(d2-3) for the remaining pixels of each respective boundary window.

Claim 5

A method according to claim 2, wherein step (a) comprises measuring the contrast within said first image pattern window, and wherein steps (b)-(d) are carried out with respect to said first image pattern window in response to the value of the measured contrast being greater than a prescribed contrast value.

Claim 6

A method according to claim 4, wherein step (c) includes the steps of measuring the parallax between respective identified pixels of said first search windows and associated prescribed pixels of said first array, determining the average value of said measured parallax for a plurality of first search windows, and discarding those identified pixels whose parallax differs from said average value of said measured parallax by a prescribed difference.

Claim 7

A method according to claim 5, wherein said prescribed difference corresponds to the standard deviation.

Claim 8

A method according to claim 3, further including the step of: (e) for each of the prescribed pixels of said first array for which corresponding pixels of said second array were not identified in step (b), each of such prescribed pixels having an associated boundary window as defined in step (d1), determining the parallax between pixels contained in said associated boundary window and corresponding pixels of said second array, in accordance with the parallax determined in step (d2-4) 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.

Claim 9

A method according to claim 7, wherein step (e) comprises the steps of: (e1) for a respective pixel belonging to an associated boundary window, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective pixel and a neighboring pixel the parallax between which and a corresponding pixel of said second array has been determined; (e2) for each respective pixel of said second array located in step (e1), defining a third search window containing that pixel and a plurality of neighboring pixels; (e3) for a respective pixel belonging to said associated boundary window, defining a third image pattern window containing said respective pixel and a plurality of neighboring pixels, such that the size of said third image pattern window is less than the size of said third search window; (e4) defining, within said third search window, a third correlation window sized in correspondence with said third image pattern correlation window; (e5) for respectively different locations of said third correlation window within said third search window, correlating the contents of said third correlation window with the contents of said third image pattern window; (e6) specifying which pixels among the image pixels of said third search window are associated with locations on said contoured surface represented by pixels of said associated boundary window, in accordance with the correlation carried out in step (e5); and (e7) 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 separations between respective pixels of said associated boundary window and image pixels of said third search window specified in step (e6).

Claim 10

A method according to claim 8, wherein step (e1) comprises, for a respective pixel belonging to an associated boundary window, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective pixel and a pixel of a neighboring boundary window.

Claim 11

A method according to claim 7, further including the step of: (f) for each of remaining pixels of said first array, for which parallax with pixels of said second array has not been determined through step (e), determining the parallax between such pixels and corresponding pixels of said second array in accordance with the parallax by the steps of (f1) for a respective remaining pixel, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective remaining pixel and an adjacent pixel the parallax between which and a corresponding pixel of said second array has been determined; (f2) for each respective corresponding pixel of said second array located in step (f1), defining a fourth search window containing said respective corresponding pixel and a plurality of neighboring pixels; (f3) for a respective remaining pixel, defining a fourth image pattern window containing said respective remaining pixel and a plurality of neighboring pixels, such that the size of said fourth image pattern window is less than the size of said fourth search window; (f4) defining, within said fourth search window, a fourth correlation window sized in correspondence with said fourth image pattern window; (f5) for respectively different locations of said fourth correlation window within said fourth search window, correlating the contents of said fourth correlation window with the contents of said fourth image pattern window; (f6) specifying which pixels among the image pixels of said fourth search window are associated with locations on said contoured surface represented by remaining pixels of said first array, in accordance with the correlation carried out in step (f5); and (f7) determining the parallax between locations on said contoured surface as seen in said first image and corresponding locations on said contoured surface as seen in said second digitized image in accordance with separations between respective pixels of said first array and image pixels of said fourth search window specified in step (f6).

Claim 12

A method according to claim 10, further comprising repeating steps (f1)-(f7) using correlation and search windows of progressively larger sizes.

Claim 13

A method according to claim 10, further comprising repeating steps (f1)-(f7) using a different traverse of said first and second pixel arrays.

Claim 14

A method according to claim 1, further including the step of (e) determining parallax for sub-pixels of said image by interpolating the parallax values derived in step (d).

Claim 15

A method according to claim 13, wherein step (e) comprises determining a correlation value for an integral pixel step at a maximum value of parallax and at two points on either side of the maximum, and processing the correlation values to interpolate the position between integral pixel steps at which the local maxima occurs.

Claim 16

A method according to claim 1, further including the step of (e) determining elevations of locations on said contoured surface in accordance with the parallax determined in step (d).

Claim 17

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).

Claim 18

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).

Claim 19

A method according to claim 16, wherein step (g) comprises the steps of: (g1) defining a boundary window about each of the pixels of said first sub-array, such that a respective boundary window contains a respective pixel of said first sub-array and a plurality of neighboring pixels and such that adjacent boundary windows border one another; and (g2) for each pixel of said first sub-array, for which a respective pixel of said second sub-array has been specified in step (f), determining the parallax between pixels contained in its associated boundary window and corresponding pixels of said second array in accordance with separations between respective pixels of said first sub-array and those pixels of said second array specified in step (f).

Claim 20

A method according to claim 17, wherein step (g2) comprises the steps of: (g2-1) for each pixel belonging to a respective boundary window defined in step (g1), locating a respective pixel of said second array in accordance with the separation between the pixel of said first sub-array belonging to said respective boundary window and a pixel of said second array specified in step (f); (g2-2) for each respective pixel of said second array located in step (g2-1), defining a second search window containing that pixel and a plurality of neighboring pixels; (g2-3) for each pixel of said respective boundary window for which a respective pixel of said second array has been located in step (g2-1), defining a second image pattern window containing said each pixel and a plurality of neighboring pixels, such that the size of said second image pattern window is less than the size of said second search window; (g2-4) defining, within said second search window, a second comparison window sized in correspondence with said second image pattern window; (g2-5) for respectively different locations of said second comparison window within said second search window, comparing the contents of said second comparison window with the contents of said second image pattern window; (g2-6) specifying which pixels among the image pixels of said second search window are associated with locations on said contoured surface represented by pixels of said boundary window, in accordance with the comparison carried out in step (g2-5); and (g2-7) determining the parallax between locations on said contoured surface as seen in said first image and corresponding locations on said contoured surface as seen in said second image in accordance with separations between respective pixels of said boundary window and image pixels of said second search window specified in step (g2-6).

Claim 21

A method according to claim 16, wherein step (c) comprises defining a plurality of first 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 images, the size of a first search window being larger than a first image pattern window, step (d) comprises defining said first comparison window as a first correlation window sized in correspondence with said first image pattern window, step (e) comprises, for respectively different locations of said first correlation window within a respective first search window, correlating the contents of said first correlation window with the contents of said first image pattern window, and wherein step (f) comprises specifying which pixel among the pixels of said first search window represents that location on said contoured surface corresponding to a respective pixel of said first sub-array of pixels of said first image, in accordance with the location of the said first correlation window within said first search window for which the value of the correlation produced by step (e) is largest.

Claim 22

A method according to claim 19, wherein step (b) comprises measuring the contrast within said first image pattern window, and wherein steps (c)-(f) are carried out with respect to a respective pixel of said first sub-array in response to the value of the measured contrast being greater than a prescribed contrast value.

Claim 23

A method according to claim 19, wherein step (f) includes the steps of measuring the parallax between said specified pixels and associated pixels of said first sub-array, determining the average value of said measured parallax for a plurality of first search windows, and discarding those specified pixels whose parallax differs from said average value of said measured parallax by a prescribed difference.

Claim 24

A method according to claim 21, wherein said prescribed difference corresponds to the standard deviation.

Claim 25

A method according to claim 19, wherein step (g) comprises the steps of: (g1) defining a boundary window about each of the pixels of said first sub-array, such that a respective boundary window contains a respective pixel of said first sub-array and a plurality of neighboring pixel and such that adjacent boundary windows border one another; and (g2) for each pixel of said first sub-array, for which a respective pixel of said second sub-array has been specified in step (f), determining the parallax between pixels contained in its associated boundary window and corresponding pixels of said second array in accordance with separations between respective pixels of said first sub-array and those pixels of said second array specified in step (f).

Claim 26

A method according to claim 23, wherein step (g2) comprises the steps of: (g2-1) for each pixel belonging to a respective boundary window defined in step (g1), locating a respective pixel of said second array in accordance with the parallax between the pixel of said first sub-array belonging to said respective boundary window and a pixel of said second array specified in step (f); (g2-2) for each respective pixel of said second array located in step (g2-1), defining a second search window containing that pixel and a plurality of neighboring pixels; (g2-3) for each pixel of said respective boundary window for which a respective pixel of said second array has been located in step (g2-1), defining a second image pattern window containing said each pixel and a plurality of neighboring pixels, such that the size of said second image pattern window is less than the size of said second search window; (g2-4) defining, within said second search window, a second correlation window sized in correspondence with said second image pattern window; (g2-5) for respectively different locations of said second correlation window within said second search window, correlating the contents of said second correlation window with the contents of said second image pattern window; (g2-6) specifying which pixels among the image pixels of said second search window are associated with locations on said contoured surface represented by pixels of said boundary window, in accordance with the correlation carried out in step (g2-5); and (g2-7) determining the parallax between locations on said contoured surface as seen in said first image and corresponding locations on said contoured surface as seen in said second image in accordance with separations between respective pixels of said boundary window and image pixels of said second search window specified in step (g2-6).

Claim 27

A method according to claim 24, wherein step (g2-3) comprises measuring the contrast within said second image pattern window, and wherein steps (g2-4)-(g2-7) are carried out with respect to pixels of a respective first boundary window in response to the value of the measured contrast within said second image pattern window being greater than a predetermined contrast value.

Claim 28

A method according to claim 18, further including the step of: (h) for each of the pixels of said first sub-array for which corresponding pixels of said second array were not specified in step (f) each of such pixels of said first sub-array having an associated boundary window as defined in step (g1), determining the parallax between pixels contained in said associated boundary window and corresponding pixels of said second array in accordance with the parallax determined in step (g2-7) between locations on said contoured surface as seen in said first image and corresponding locations on said contoured surface as seen in said second image.

Claim 29

A method according to claim 26, wherein step (h) comprises the steps of: (h1) for a respective pixel belonging to an associated boundary window, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective pixel and a neighboring pixel the parallax between which and a corresponding pixel of said second array has been determined; (h2) for each respective pixel of said second array located in step (h1), defining a third search window containing that pixel and a plurality of neighboring pixels; (h3) for a respective pixel belonging to said associated boundary window, defining a third image pattern window containing said respective pixel and a plurality of neighboring pixels, such that the size of said image pattern window is less than the size of said third search window; (h4) defining, within said third search window, a third correlation window sized in correspondence with said third image pattern window; (h5) for respectively different locations of said third correlation window within said third search window, correlating the contents of said third correlation window with the contents of said third image pattern window; (h6) specifying which pixels among the image pixels of said third search window are associated with locations on said contoured surface represented by pixels of said associated boundary window, in accordance with the correlation carried out in step (h5); and (h7) determining the parallax between locations on said contoured surface as seen in said first image and corresponding locations on said contoured surface as seen in said second image in accordance with separations between respective pixels of said associated boundary window and image pixels of said third search window specified in step (h6).

Claim 30

A method according to claim 27, wherein step (h1) comprises, for a respective pixel belonging to an associated boundary window, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective pixel and a pixel of a neighboring boundary window.

Claim 31

A method according to claim 27, further including the step of: (i) for each of remaining pixels of said first array, for which parallax with pixels of said second array has not been determined through step (h), determining the parallax between such pixels and corresponding pixels of said second array in accordance with the parallax by (i1) for a respective remaining pixel, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective remaining pixel and an adjacent pixel the parallax between which and a corresponding pixel of said second array has been determined; (i2) for each respective corresponding pixel of said second array located in step (i1), defining a fourth search window containing said respective corresponding pixel and a plurality of neighboring pixels; (i3) for a respective remaining pixel, defining a fourth image pattern window containing said respective remaining pixel and a plurality of neighboring pixels, such that the size of said fourth image pattern window is less than the size of said fourth search window; (i4) defining, within said fourth search window, a fourth correlation window sized in correspondence with said fourth image pattern window; (i5) for respectively different locations of said fourth correlation window within said fourth search window, correlating the contents of said fourth correlation window with the contents of said fourth image pattern window; (i6) specifying which pixels among the image pixels of said fourth search window are associated with locations on said contoured surface represented by remaining pixels of said first array, in accordance with the correlation carried out in step (i5); and (i7) determining the parallax between locations on said contoured surface as seen in said first image and corresponding locations on said contoured surface as seen in said second image in accordance with separations between respective pixels of said first array and image pixels of said fourth search window specified in step (i6).

Claim 32

A method according to claim 29, further comprising repeating steps (i1)-(i7) using correlation and search windows of progressively larger sizes.

Claim 33

A method according to claim 29, further comprising repeating steps (i1)-(i7) using a different traverse of said first and second pixel arrays.

Claim 34

A method according to claim 16, further including the step of (e) determining parallax for sub-pixels of said image by interpolating the parallax values derived in step (d).

Claim 37

A method according to claim 16, further including the step of (e) determining elevations of locations on said contoured surface in accordance with the parallax determined in step (d).

Claim 38

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).

Claim 39

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).

Claim 40

A method according to claim 35, wherein step (h) comprises the steps of: (h1) defining a boundary window about each of said reference pixels, such that a respective boundary window contains a respective reference pixel and a plurality of neighboring pixels and such that adjacent boundary windows border one another; and (h2) determining the parallax between pixels contained in respective boundary windows and corresponding pixels of said second array, in accordance with the parallax determined in step (g) between respective tentative tie point pixels and identified tie point pixels identified in step (f).

Claim 41

A method according to claim 36, wherein step (h2) comprises the steps of: (h2-1) for each pixel belonging to a respective boundary window defined in step (h1), locating a respective pixel of said second array in accordance with the parallax determined in step (g); (h2-2) for each respective pixel of said second array located in step (h2-1), defining a second search window containing said each respective pixel and a plurality of neighboring pixels; (h2-3) for each pixel of a respective boundary window for which a respective pixel of said second array has been located in step (h2-1), defining a second image pattern window containing said each pixel and a plurality of neighboring pixels, such that the size of said second image pattern window is less than the size of said second search window; (h2-4) defining, within said second search window, a second correlation window sized in correspondence with said second image pattern window; (h2-5) for respectively different locations of said second correlation window within said second search window, correlating the contents of said second correlation window with the contents of said second image pattern window; (h2-6) identifying which pixels among the image pixels of said second search window are associated with locations on said contoured surface represented by pixels of said boundary window, in accordance with the correlations carried out in step (h2-5); and (h2-7) 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 separations between respective pixels of said boundary window and image pixels of said second search window identified in step (h2-6).

Claim 42

A method according to claim 37, wherein step (b) comprises measuring the contrast within said first image pattern window, and wherein steps (c)-(g) are carried out with respect to a respective reference pixel in response to the value of the measured contrast being greater than a prescribed contrast value.

Claim 43

A method according to claim 38, wherein step (f) includes the steps of measuring the parallax between said identified pixels and associated tentative tie point pixels, determining the average value of said measured parallax for a plurality of first search windows, and discarding those identified tie point pixels whose parallax differs from said average value of said measured parallax by a prescribed difference.

Claim 44

A method according to claim 39, wherein said prescribed difference corresponds to the standard deviation.

Claim 45

A method according to claim 37, further including the step of: (i) for each of said reference pixels for which corresponding pixels of said second array were not identified in step (f), each of such reference pixels having an associated boundary window as defined in step (h1), determining the parallax between pixels contained in said associated boundary window and corresponding pixels of said second array in accordance with the parallax determined in step (h2-7) 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.

Claim 46

A method according to claim 41, wherein step (i) comprises the steps of: (i1) for a respective pixel belonging to an associated boundary window, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective pixel and a neighboring pixel the parallax between which and a corresponding pixel of said second array has been determined; (i2) for each respective pixel of said second array located in step (i1), defining a third search window containing that pixel and a plurality of neighboring pixels; (i3) for a respective pixel belonging to said associated boundary window, defining a third image pattern window containing said respective pixel and a plurality of neighboring pixels, such that the size of said third image pattern window is less than the size of said third search window; (i4) defining, within said third search window, a third correlation window sized in correspondence with said third image pattern window; (i5) for respectively different locations of said third correlation window within said third search window, correlating the contents of said third correlation window with the contents of said third image pattern window; (i6) specifying which pixels among the image pixels of said third search window are associated with locations on said contoured surface represented by pixels of said associated boundary window, in accordance with the correlation carried out in step (i5); and (i7) 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 separations between respective pixels of said associated boundary window and image pixels of said third search window specified in step (i6).

Claim 47

A method according to claim 42, wherein step (i1) comprises, for a respective pixel belonging to an associated boundary window, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective pixel and a pixel of a neighboring boundary window.

Claim 48

A method according to claim 42, further including the step of: (j) for each of remaining pixels of said first array, for which parallax with pixels of said second array has not been determined through step (i), determining the parallax between such pixels and corresponding pixels of said second array in accordance with the parallax by (j1) for a respective remaining pixel, locating a corresponding pixel of said second array in accordance with the geometric relationship between said respective remaining pixel and an adjacent pixel the parallax between which and a corresponding pixel of said second array has been determined; (j2) for each respective corresponding pixel of said second array located in step (j1), defining a fourth search window containing said respective corresponding pixel and a plurality of neighboring pixels; (j3) for a respective remaining pixel, defining a fourth image pattern window containing said respective remaining pixel and a plurality of neighboring pixels, such that the size of said fourth image pattern window is less than the size of said fourth search window; (j4) defining, within said fourth search window, a fourth correlation window sized in correspondence with said fourth image pattern window; (j5) for respectively different locations of said fourth correlation window within said fourth search window, correlating the contents of said fourth correlation window with the contents of said fourth image pattern window; (j6) specifying which pixels among the image pixels of said fourth search window are associated with locations on said contoured surface represented by remaining pixels of said first array, in accordance with the correlation carried out in step (j5); and (j7) determining the parallax between locations on said contoured surface as seen in said first image and corresponding locations on said contoured surface as seen in said second digitized image in accordance with separations between respective pixels of said first array and image pixels of said fourth search window specified in step (j6).

Claim 49

A method according to claim 44, further comprising repeating steps (j1)-(j7) using correlation and search windows of progressively larger sizes.

Claim 50

A method according to claim 44, further comprising repeating steps (j1)-(j7) using a different traverse of said first and second pixel arrays.

Claim 51

A method according to claim 35, further including the step of (e) determining parallax for sub-pixels of said image by interpolating the parallax values derived in step (d).

Claim 54

A method according to claim 35, further including the step of (e) determining elevations of locations on said contoured surface in accordance with the parallax determined in step (d).

Claim 57

A method according to claim 50, further comprising, before said step (a), the step of dividing the first image into boundary windows, and wherein said correlating steps (a) and (b) are performed for each of the boundary windows of the first image.

Claim 58

A method according to claim 50, wherein the subsequent search window is a size smaller than the initial search window.

Claim 59

A method according to claim 50, wherein the subsequent correlation window is a size smaller than the initial correlation window.

Claim 62

An apparatus according to claim 54, further comprising fourth means for dividing the first image into boundary windows, and wherein said first and second means perform the correlations for each of the boundary windows of the first image.

Claim 63

An apparatus according to claim 54, wherein the subsequent search window is a size smaller than the initial search window.

Claim 64

An apparatus according to claim 54, wherein the subsequent correlation window is a size smaller than the initial correlation window.