Title of Invention

APPARATUS FOR AUTONOMOUS DETERMINATION OF TIE POINTS IN IMAGERY

Abstract

Apparatus for selecting tie point locations within a series of geographically overlapping images, the apparatus comprising: an image generator having an output representing a series of overlapping images; a memory coupled to the image generator to accept the output representing a series of overlapping images; a computer coupled to the memory to receive the series of overlapping images, the computer having: a means for ordering the series of overlapping images to maximize successful phase correlations between adjacent ones of the series of overlapping images; a means for phase correlating at full resolution the adjacent ones of the series of overlapping images according to the ordering of the series of overlapping images to determine translational offsets between overlapping areas in the adjacent ones of the series of overlapping images; a means for selecting initial candidate tie point locations within the overlapping areas in the adjacent ones of the series of overlapping images according to signal levels and scene content within the overlapping areas determining those initial candidate tie point locations falling within a signal level threshold for phase correlation between each of the adjacent ones of the series of overlapping areas at full resolution; a means for phase correlating at a reduced resolution those initial candidate tie point locations with the translated offsets that satisfy the signal level threshold through all adjacent ones of the series of overlapping images to determine surviving tie point locations; and a means for refining the surviving tie point locations to sub-pixel accuracy to identify a final tie point location.

Full Text

FORM 2 THE PATENTS ACT, 1970 (39 of 1970) COMPLETE SPECIFICATION [See section 10] APPARATUS FOR AUTONOMOUS DETERMINATION OF TIE POINTS IN IMAGERY; RAYTHEON COMPANY A COMPANY ORGANIZED AND EXISTING UNDER THE LAWS OF UNITED STATES OF AMERICA, WHOSE ADDRESS IS 141 SPRING STREET, LEXINGTON, MASSACHUSETTS, 02421, U.S.A.; THE FOLLOWING SPECIFICATION PARTICULARLY DESCRIBES AND ASCERTAINS THE NATURE OF THE INVENTION AND THE MANNER IN WHICH IT IS TO BE PERFOMED. The present invention relates to an apparatus for selecting tie points within a sequence of geographically overlapping digital images. Image registration techniques play an important role in terrain assessment and mapping. From a sequence of geographically overlapping digital images, image registration techniques identify and automatically register points of correspondence ("tie points") among the plurality of images. These images are digital images with different orientations and/or scales. These images may also have been obtained at differing times of year and from different geographical perspectives. Once tie points are identified, coordinates of each corresponding point in each images are calculated so as to be invariant with respect to the scale, orientation and position of the image of which the points are a part. From this information, the areas in common of the overlapping images can be analyzed. It may be desirable to assemble a single large image based on a collection of all of the overlapping points. Thus a need has arisen to provide an apparatus for automatically identifying the same geographical points in different digital images having common coverage in a more versatile and useful fashion. 2 BRIEF DESCRIPTION OF THE DRAWINGS ;- For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following Detailed Description taken in conjunction with the accompanying Drawings in which: FIGURE 1 is a flow diagram illustrating the achievement of autonomous tie point registration; FIGURE 2 is a flow diagram illustrating the ordering of geographically overlapping images; FIGURE 3 illustrates the data array resulting from calculating the inverse Fourier transform of an adjacent data array pair; FIGURE 4 is a flow diagram illustrating the phase correlation of image data arrays at a first resolution; FIGURE 5 is a flow diagram illustrating the phase correlation of image data arrays at a second resolution; FIGURE 6 is a flow diagram illustrating the assessment of potential tie point locations; FIGURE 7 is a flow diagram illustrating the normalized cross correlation of the present invention; FIGURE 8 is a flow diagram illustrating the ranking of candidate tie point locations, 3 FIGURE 9 is a flow diagram illustrating the consensus check function of the present invention; and FIGURE 10 is a flow diagram illustrating the fitting of a quadratic surface to a 3X3 pixel window extracted from a normalized cross correlation solution array. FIGURE 11 is a block diagram of apparatus for autonomous determination of tie points in imagery as described with reference to figures 1-10. DETAILED DESCRIPTION :- Referring now to the drawings, and more particularly to Figure 1, there is shown a flow diagram on achieving autonomous tie point registration. The process is broken down into the selection process 10 and mensuration process 12. The selection process 10 identifies coarse tie point locations from reduced resolution imagery (generally 1/64X). The mensuration process 12 refines the locations of the rough tie points estimations provided by the selection process 10 to sub pixel array. The selection process 10 includes optimize stereo pairing 14. The optimize stereo pairing 14 places a plurality of digital images provided by an image gathering apparatus (not shown) in a circular order such that all pairings, including the pairing of the first and last images, possess a high degree of likelihood for successful phase correlation. This 4 approach minimizes the differences between the seasons of adjacent images and in the angles defining the taking geometry of adjacent images. The smaller the degree of difference between these tow parameters, the greater the possibility of a successful phase correlation between the adjacent images. Referring now to Figure 2, which illustrates the ordering of the geographically overlapping images according to the present invention, each image is assigned at step 16 a numerical tag from 1 to N, where N = the total number of images. The ordered images are stored in a two column array M, wherein the total number of rows equals the number of same flight image pairs plus the remaining number of single unpaired images. The first location of array M contains the image closest to midyear. Midyear is defined to be midnight July 1 in the northern hemisphere (including the equator) and as midnight, January 1 in the southern hemisphere. The numerical tags of the same flight image pair occurring closest to the midyear date is stored at step 18 in the first row of array M with the tag of the fore perspective image in Column 1, and the tag of the aft perspective image in Column 2. For each of the remaining same flight, stereo image pairs, the stereo geometry angles of the image pair most similar to those of the previously stored stereo image pair are 5 calculated, and the tags for the image pair are stored at step 20 in the next row of array M. The stereo image pair containing the most closely associated stereo geometry angles are determined by defining the vector of the last stereo geometry angles placed in the array M as (ai, a2, , a6) and the ith unplaced same flight stereo image pair as (bii, bi2 bi6). The following equation : Li- Wj *|aj-bu| 7=1 is used to determine the index of the same flight stereo image pair minimizing equation (1). Inquiry step 22 continues it the next image pair until all same flight stereo image pairs have been stored within array M. After inquiry step 22 determines all same flight image pairs have been stored in array M, the single image nearest in time to the image most recently stored in array M is determined at step 24, and the numerical tag of this image is stored in Column 2 of the next row of array M. This procedure continues via inquiry step 26 until the numerical tags of all single images have been stored within array M. Referring back to Figure 1, once all images have been ordered by the optimized stereo pairing 14, the phase correlator 21 determines the translational offsets between consecutively ordered images. In order to determine the translational offset between each of the adjacent images, 6 phase correlations are performed between the data arrays describing the images. Adjacent arrays of image data are phase correlated by taking the inverse Fourier Transform of the arrays to compute the phase of the cross power spectrum of the arrays. This procedure generates a third array as shown in Figure 3, that peaks at the desired offset location. The degree of correlation between the two data arrays is measured by correlator Figure of Merti (FOM), defined as the difference between the maximum correlation value in the signal region and the maximum correlation value in the noise region. The peak value of the phase correlation surface is denoted by 0max and its location is given by ( Δl, Δs). The noise peak (N max) is located outside a 5X5 pixel signal region centered at (Δl, Δs). Referring now to Figure 4, there is shown a flow diagram illustrating the phase correlation of adjacent image data arrays to determine the translational offset between the images. A pair of images are super imposed and shifted against each other without rotation until image features in the overlapping region coincide. Phase correlation is performed twice for each consecutive pairing in the ordering. Each of these phase correlations is performed at a different resolution size. The first resolution size is chosen depending upon the amount of data available in the vicinity 7 of the proposed tie point locations, and the second resolution size is normally 1/8X. A 64 square pixel window region (W) in the first image and a 128 square pixel search region (S) in the second image are selected at step 30. Within the search region(s), twenty-five (25) overlapping 64 square pixel subregions, identified as candidate match areas, are selected at step 32. The candidate match areas lag each other by 16 pixels in each dimension. Phase correlation is performed at step 34 between the first image window and each of the candidate match areas. For each correlation, a feature vector is stored. The feature vector consist of (Ǿmax, N max, FOM, Δl, Δs). Also recorded are the index of the candidate match area having the maximum FOM, as well as the index if the candidate match area having the maximum value of Ǿmax. Once each candidate match area within the search region (S), has been phase correlated with the window (W), an additional phase correlation, the Valid Match Verification (VMV), is performed at step 36. The VMV adds the offsets (Δl, Δs) obtained from correlating (W) with each of the candidate match areas to the location of each candidate match area and phase correlates (W) with the translated candidate match areas. The feature vector (0max, N max, FOM, Al, As) for these additional correlations is also stored. 8 If the maximum FOM from the VMV exceed at inquiry step 38 the threshold FOM value, phase correlation is considered successful. Thus, at step 40, the center of window (W) is mapped to the center of the 64 square pixel array of the first image and the center of the best matching candidate match area is mapped to the center of a 96 square pixel array in the second image at a point (S*) defined by the following equation : (1) S* = S + (Δ1, Δs)i- (Δl, Δs)v wherein : (Δl, Δs) i = initial candidate match offset (Δl, Δs) v = VMV offset. Phase correlation is performed at step 41 at the second resolution according to the procedure illustrated in Figure 5. If the maximum Figure of Merit value does not exceed the threshold Figure of Merit value at inquiry step 38, the translational offsets of all twenty - five (25) candidate match areas are added at step 42 to their respective locations, and the translated candidate match areas are phase correlated at step 44. If any of the candidate match areas predict the same match location (+ 2 pixels in each dimension separately) as the previous phase correlation predicted at inquiry step 46, this candidate is deemed to successfully match the window in the first image. The 64 square pixel first image window is centered at the initial window location 9 at step 40, and the 96 square pixel search region is centered at the point (S *) corresponding to: (3) S* = S + (Δl, Δs) i Phase correlation proceeds at step 41 according to the process outlined in Figure 5. If none of the candidate match areas predict the same location at step 46, correlation is deemed to have failed and new tie point locations must be proposed by the redensification function at step 47. Referring now to Figure 5, there is illustrated the processing of candidate tie points at the second resolution. A 64 square pixel window region (W) in the first image and a 96 square pixel search region (S) in the second image are selected and centered at step 48 at respective proposed tie point locations from the process described in Figure 4. Within the search regions, nine (9) overlapping candidate match areas (subregions) are selected at step 49. These candidate match areas lag each other by 16 pixels in each dimension. The window is phase correlated at step 50 with each of the candidate match areas. For each correlation, a feature vector is stored as described previously with respect to FIGURE 4. Also recorded are the index of the candidate with the largest FOM, the index of the candidate with the largest Ǿmax and the value of 0max for the central candidate match area (S5). 10 Inquiry step 51 determines if Ǿmax of the central candidate match area exceeds a maximum threshold value. If so, a valid match verification is performed at step 52 on S5 and the tie points for the current image pair are selected at step 54 at the center of W for the left image, and at Ss- Δl, Δs) 5 + (Δl, Δs) v for the right image. If 0max of the central candidate match area does not exceed the predetermined maximum threshold value for 0max, a valid match verification procedure, as described previously with respect to FIGURE 4, is executed at step 56. If the maximum Figure of Merit from VMV exceeds the threshold FOM value at inquiry step 58, phase correlation is considered successful. Thus, at step 60, the center of window (W) is mapped to the center of the 64X64 pixel array of the first image and the center of the best matching candidate area is mapped to the center of a 96X96 pixel array in the second image. If the maximum Figure of Merit value from the VMV process at step 56 does not exceed the threshold Figure of Merit value at inquiry step 58, the translation offsets of all twenty - five ( 25) candidate match areas are added at step 64 to their respective locations, and the translated candidate match areas are phase correlated at step 66. If any of the candidate match areas predict the same match location ( ± 2 pixels in each dimension separately) as the 11 previous phase correlation predicted at inquiry step 68, this candidate is deemed to successfully match the window in the first image and the 64 square pixel first image window is centered at the initial window location at step 60, while the 96 square pixel search region is centered at the point (S*) corresponding to : (3) S* = S + (Δl, Δs) i If none of the candidate match areas predict the same location at step 68, correlation is deemed to have failed and new tie point locations must be proposed by redensification 71. Once an image pairing has been successfully phase correlated, a proposed tie point location exists in the right hand image of the pairing. Coordinates for this tie point location are given in a plane. To move to the next pairing, this tie point location is mapped to rectified (x, t) space using the appropriate coefficients for image rectification, and the point is then mapped to (r, s) space of the next pairing using a different set of coefficients at step 62. This yields a new tie point location in the left hand image of the next pairing that forms the center of the new Window W. Referring back to Figure 1, the candidate area assessment 53 provides an assessment of signal level and scene content correlation for candidate areas within the first image. The signal level and scene content correlation are calculated at 12 sixteen (16) test point locations within each candidate area. By analyzing the signal level and scene content correlation, test point locations to be used in finding tie point locations within the remaining images are generated. Referring now to FIGURE 6, there is more fully illustrated the assessment of candidate areas. The number of candidate areas within the first image are determined at step 72 and 16 test point locations are selected within each candidate area of the first image. A signal level test is performed at step 74 on the test points within each candidate area. The signal level test determines the standard deviation of signal strength within a 7X15 pixel array centered about each test point location. It is to be understood that the size of the pixel array surrounding the test point locations in the signal level tests may be of a variety of dimensions selected by a user. The calculated standard deviation is compared to a predetermined threshold level. If eleven (11) of the standard deviations computed for the 16 test point locations are less than the threshold level as determine by inquiry step 76, the candidate area is considered non-suitable due to a weak signal-to-noise ratio and processing proceeds to the next candidate area at step 78. 13 If inquiry step 76 determines a candidate area contains sufficient signal to noise ratio, the scene content correlation is calculated at step 60 for the candidate area. For each test point location within a candidate area, a 7X15 pixel window centered about a given test point is phase correlated with four (4) different 7X15 windows, whose window centers are displaced some by distance (i) with respect to the test point center. Locations of the four (4) window midpoints are at . The correlation procedure provides four (4) autocorrelation estimates pi, p2, P3 and p4. Estimates of correlation content for a lag i are made for the sample (s) and line (l ) directions according to the following equations :- (4) 2 2 If inquiry step 82 determines the correlation contents for the line and sample directions does not lie within a predetermined threshold range, the candidate area is considered unsuitable and processing proceeds to the next candidate area via step 78. Otherwise, the candidate areas 14 identified at step 84 as suitable candidates for the normalized cross correlation function. Referring again to Figure 1, the candidate tie points determined from the candidate area assessment 53 are forwarded to normalized cross correlation (NCC) 90. Candidate tie point locations in the left hand image of the first stereo pair are assigned as designated by the CAA function. The NCC 90 attempts to find conjugate pairs in the right hand image. The maximum correlator values contained in the NCC solution array is chosen as a conjugate tie point location. A FOM test is applied to the selected conjugate tie point locations as an additional check on validity. Points that fail the FOM test are dropped from further processing. Points that pass the FOM test are mapped to the left hand image of the next stereo pair which has been specified by the optimized image pairing 14. The entire NCC process is repeated on each stereo pair. Candidate tie points that pass all of the FOM tests (one (1) per stereo pair) are mapped back to the original image, and a closure test network 110 locates blunders and false matches. Referring now to FIGURE 7, there is illustrated in more detail the method for accomplishing the normalized cross correlation of the normalized cross correlation function. Candidate tie point locations in the first image received from 15 the CAA network 53 are correlated at step 92 with the second image, and the maximum correlation values are selected as conjugate points within the second image at step 94. One the maximum correlation value is determined, the Figure of Merit (FOM) for the image correlation is determined according to the following equation: where P max and η max are defined in FIGURE 3 and PGF is computed by the following: 16 Where P max and N max are defined in Figure3 and PGF is computed by the following: and N is the total number of Pi , values generated in the correlation process. The FOM value is compared to a threshold FOM value and any candidate locations not exceeding a threshold FOM value are dropped as candidate locations at step 96. A stereo image pair comprised of the second image of the previous image pair and the following image are dewarped as a stereo pair at step 98. The candidate points surviving the FOM test from the previous normalized cross correlation process are again correlated for the next image pair at step 100. Points passing the FOM test for this correlation are determined at step 102, and the points are forwarded for dewarping and correlation if inquiry step 104 verifies the existence of additional image pairs. Once all image pairs have been correlated, the last and first images are dewarped as a stereo pair at step 106, and the images are correlated at step 108. Candidate matches passing the FOM threshold requirements throughout the process are forwarded for further analysis. The preceding discussion of the normalized cross correlation procedure assumes there will be successful correlations in each image. If, for any reason, this does not occur, normalized cross correlation processing will terminate for those images, and control passes to the redensification 71. If all alternate tolerance regions are exhausted, and no 17 candidate tie points are found, the procedure reverts to interactive selection of the tie point candidates. Referring again to FIGURE 1, the closure test 110 performs a deterministic test arising from the concept that a single point, when correlated and mapped through all images of interest with zero (0) errors, will have the same computed coordinate value that was assigned to it at the beginning of NCC processing. Therefore, the difference between its initial assigned coordinate and its final mapped value at the end of closure test processing will be zero (0). There is some residual error after closure test processing for valid candidate tie points. A tolerance threshold of ± 2 pixels has been established. Points having closure errors greater than this magnitude are considered blunders and are not retained for further processing. Once normalized cross correlation 90 has generated the plurality of candidate tie point locations, the closure test 110 maps the location of the candidate tie points in the last image form (r, s) coordinates to (x, t) coordinates and then back to (r, s) coordinates in the left hand image of the first stereo pair. The mapped candidate tie points are compared to the original position of the tie points and any pixels differing by more than two (pixels) are discarded. The two variations are incorporated to account for correlating and 18 mapping errors caused by the normalization cross correlation procedure. The candidate tie point ranking 112 receives the information vector of candidate tie points having passed the closure test 110. The candidate tie point ranking 112 selects three (3) candidate tie points having the highest probability of successfully passing normalized cross correlation and closure test procedures during the mensuration process 12 based upon data contained within the information vectors of the candidate points. 19 Referring now to Figure 8, there is illustrated the ranking of candidate tie point locations according to the candidate tie point ranking 112. All candidate tie points are read at step 114 from the correlation file generated by the normalized cross correlation and closure tests 90, 110. For each candidate tie point, the averages of RATIO and PGF are computed at step 116. The averages for RATIO and PGF form a mean information vector (Vm) for each candidate tie point location, as illustrated by the following equation: The RATIO and PGF averages are sorted at step 118 in descending order. The candidate tie point ranking 112 selects at step 120 the first three (3) candidate tie points according to the sorted RATIO average list. While the present description describes sorting the candidate tie points according to the RATIO average of the candidate tie points, the candidate tie points may also be sorted according to the PGF parameter as selected by a user. Finally, the top three (3) candidates tie points from the sorted lists are output at step 122 for further processing. Referring back to FIGURE 1, once all candidate tie points are ranked by the candidate tie point ranking 112, the points are passed to the consensus check 130. The consensus check 130 selects the top two (2) or three (3) tie point locations from the ranked candidates and calculates the distance between the points in three dimesional object space for each stereo pairing. The triangle formed in three dimensional object space by three (3) candidate tie point locations should be congruent in all pairings. Candidate tie points passing these criteria minimizes the possibility of false match locations with any of the three (3) points. To calculate the distances between the candidate tie points forming the triangles, the consensus 20 check 130 processes the ranked candidate tie points and direction cosines in all stereo pairings of interest. In the event that only one tie point candidate location exists, the consensus check 130 is bypassed, and the point is passed to the mensuration process 12. Referring now to Figure 9, there is more fully illustrated the strategy by which the consensus check 130 performs the analysis of the ranked candidate tie points. At inquiry step 132, a determination is made of the existence of more than one (1) tie point candidate location. If only one (1) candidate tie point exists, processing passes to step 146 to pass the candidate tie point to the mensuration process 12. If more than one (1) tie point candidate exists, the top candidate locations, normally two (2) or three (3), are read at step 134, and the distances between these points in all stereo pairings are calculated at step 136. Utilizing the distances computed at step 136, the standard deviation of distances between particular tie point candidates in the stereo pairs are determined at step 138. These standard deviations are compared at step 140 to a predetermined tolerance range, and if all deviations exists within the specified tolerance range, the top two (2) or three (3) candidates are passes to mensuration at step 146. If one or more of the standard deviations are not within the specified tolerance range, the candidate point to be rejected 21 is determined at step 142, and the next ranked candidate tie point is selected at step 144. The determination of candidate tie points for rejection at step 142 will be more fully discussed. Once a new tie point location is selected at step 144, control returns to step 136 and the distances and standard deviations between the new candidate tie point locations are again determined. If any of the standard deviations do not fall within one of the predetermined tolerance ranges one of the following three 3) procedure will be followed at step 142. CASE 1 :- One standard deviation is greater than a tolerance level; and a) the other two standard deviations are not equal; or PROCEDURE : The common tie point of the two distances with the largest standard deviation is rejected. b) the other two standard deviations are equal. PROCEDURE:- The lower ranked tie point of the tie points comprising the distances in question is rejected. CASE 2:- Two standard deviations are greater than a tolerance level. PROCEDURE;- The common tie point of the two distances is rejected. 22 CASE:- All three standard deviations are greater than tolerance ; and a) all three standard deviations are unequal; or PROCEDURE;- The common tie point of the two largest standard deviations is rejected. b) two standard deviations are equal and the third standard deviation is greater ; or PROCEDURE:- The lower ranked tie point of the segment comprising the largest standard deviation is rejected. c) two standard deviations are equal and the third standard deviation is less ; or PROCEDURE:- The common tie point of the two largest standard deviations is rejected. d) all three standard deviations are equal. PROCEDURE: - The common tie point of the two lowest ranked tie points is rejected. Referring back to Figure 1, the redensification 71 provides the logic required to redensify an alternate location for a tolerance region when a candidate tie point location cannot 23 be found in the primary tolerance region. The first time redensification 71 is utilized for determining an initial or primary tolerance region, alternate locations of tolerance region on either side of the primary region are computed. These alternate locations of tolerance regions are utilized when there is a failure to find candidate tie point locations at any point within the selection procedure 10. After completion of the selection procedure 10, the surviving candidate tie points (normally 3) are forwarded to the mensuration process 12. The mensuration process 12 provides many of the same functional processes as the selection process 10 but performs the procedures at full resolution. Normalized cross correlation 150 utilizes the normalized crossed correlation procedure discussed previously with respect to FIGURE 7. However, there are a few notable differences between the two procedures. The FOM test of step 96 applied to the correlated peak values during the selection process 10 is not performed for the normalized cross correlation 150 of the mensuration process 12. All correlator peak locations are accepted as valid and the closure test 152 is used to determine which locations are kept as candidate points. Also, image data used to fill 7X15 Windows are sampled four (4) or more pixels apart in both the left and right images. Finally, the normalized cross 24 correlation procedure is carried out at full resolution as opposed to one quarter resolution. After the normalized cross correlation 150 analyses, the surviving candidate tie points are forwarded at full resolution to a closure test 152. The closure test 152 analyzes and forwards tie point candidate locations passing the closure test in the same manner as that discussed with respect to the closure test 100 of the selection process 10. Once normalized cross correlation 150 and closure test 152 have processed the candidate tie points, any surviving tie point candidates are processed by tie point accuracy 154 to estimate the accuracy of the tie point candidates. Tie point accuracy 154 refines the candidate tie point locations to decimal line and sample (sub-pixel) accuracy and determines the error associates with tie point candidate location estimate. Initial integer tie point locations are refined by fitting a quadratic surface to a 3X3 window extracted from the normalized cross correlation solution array and determining the surface fit maximum needed to refine the tie point integer location to sub-pixel accuracy. Referring now to Figure 10, there is illustrated the fitting of the quadratic surface to a 3X3 pixel window extracted from the normalized cross correlation solution array. The 3X3 pixel window centered about the maximum value of the cross correlation array is extracted at step 160 from the array. 25 The coefficients of a quadratic surface satisfying the least squares constraint on the nine (9) points included in the extracted 3X3 array are determined at step 162 for the following quadratic equation : The surface coefficients for the quadratic surface are determined according to the following equations: Where : 26 and the Pij value indicates the maximum value produced by he correlation process. The remaining Plk values {l * i, K*j) denote a 3X3 window of correlation values having P« as the midpoint and maximum value. Finally, the coordinates (x,y) of the peak of the quadratic surface are found at step 154 according to the equation: where H= 4a3 a.4 – a5 Under any other conditions for a3 and H, the location of the peak value for the quadratic surface fit defaults to the center of the window such that (x,y) = (0,0) A second estimate of the integer tie point location is calculated at step 166 and the two (2) estimates are combined at step 168 to provide a final sub-pixel tie point location estimate. Generation of the second estimate is based upon the assumption that autocorrelation values of the 7X15 pixel window and the direction of a line (L) containing the integer tie point and first sub-pixel estimate diminish according to an exponential function given by; (10) ǾXX=e~cr 27 The fall off rate a is computed by locating the integer lag (N1 for N1 * 5) along line (L) whose autocorrelation value p is the smallest of the positive autocorrelation values. Upon this bases, a is computed to be - In (p)/ N l. This autocorrelation model is designed to fit exactly the autocorrelation values along line p computed at lags 0 and N l. The second sub-pixel estimate is then given simply by the lag value along (L) for which the model assumes the value of 0max (the peak value of the normalized cross correlation function) given as : A=_^L *ln(0max) T ln(/>) Previous locations of tie points to sub-pixel accuracy using simulated stereo imagery has indicated accuracies to generally be less than 0.2 pixel (line and sample) for either the surface fit estimation on the expeditial correlation model described in equation 10. It appears that general scene content may be adequately modeled by a process generally providing results somewhere between the two models discussed. For this reason, the final tie point estimation PTP is determined by combining results from the two estimates at step 64. 28 Referring to Figure 11, there is illustrated a block diagram of apparatus for autonomous determination of tie points in imagery including an image generator 180 outputting a plurality of digital images to a memory 182. The digital images are stored in the memory 182 for processing by a computer 184 coupled to the memory. Also coupled to the computer 184 is a keyboard 186 for manual instruction to the computer by a user of the apparatus. In addition, a display/ printer 188 is also coupled to the computer to display and/or print the results of autonomous determination of tie points in imagery. The computer 184 is programmed to order a series of overlapping images stored in the memory 182 to maximize successful correlation between adjacent image pairs. In addition, the computer 184 is programmed to phase correlate the adjacent image pairs according to the ordering of the series of overlapping images to determine an offset between overlapping areas in the adjacent image pairs. Also programmed into the computer 184 is selecting initial candidate tie point locations within the overlapping areas of the adjacent image pairs valid for each at a reduced resolution. Further, the computer 184 is programmed to determine the candidate tie point location likely valid for phase correlation between each of the adjacent image pairs in the plurality of overlapping areas at full resolution. The 29 candidate tie point locations are phase correlated by programming the computer 184 at full resolution. The candidate tie point locations are phase correlated with adjacent images in the plurality of images to determine surviving tie point locations and the surviving tie point locations are refined to sub-pixel accuracy. In addition, the computer 184 is programmed to perform autonomous determination of tie points in imagery as disclosed and described with reference to Figures 1-10. Although a preferred of the present invention has been illustrated in the accompanying drawings and described in the foregoing detailed description, it will be understood that the invention is not limited to the embodiment disclosed, but is capable of numerous rearrangements, modifications and substitutions of parts and elements without departing from the spirit of the invention. 30 Claims 1. Apparatus for selecting tie point locations within a series of overlapping images, the apparatus comprising : an image generator having an output representing a series of overlapping images; a memory coupled to the image generator to accept the output representing a series of overlapping images; a computer coupled to the memory to receive the series of overlapping images, the computer programmed to : (a) ordering the series of overlapping images to maximize successful phase correlations between adjacent image pairs; (b) phase correlating the adjacent image pairs according to the ordering of the series of overlapping images to determine an offset between overlapping areas in the adjacent image pairs; (c) selecting initial candidate tie point locations within the overlapping areas of the adjacent image pairs valid for each at a reduced resolution; (d) determining the candidate tie point location likely valid for phase correlation between each 31 of the adjacent image pairs in the plurality of overlapping areas at full resolution; (e) phase correlating at full resolution the candidate tie point locations determined in (d) through all adjacent images in the plurality of images to determine surviving tie point locations; and (f) refining the surviving tie point locations to sub-pixel accuracy. 2. The apparatus of Claim 1, the computer further programmed to : (a) placing a first image pair from the plurality of overlapping images into a first location in an array, the first time image pair being generated closest to a predetermined point in time; (b) placing a next image pair closest in geometry to a previously placed image pair in a next storage location in the array; and (c) repeating (b) until all image pairs are placed in the array. 3. The apparatus of Claim 2, the computer further programmed to : (a) selecting an unpaired single image closest in time to an image previously stored in the array; 32 (b) placing the selected unpaired single image in the array; and (c) repeating (a) and (b) until all unpaired single images from the plurality of overlapping images have been placed in the array. 4. The apparatus of Claim 1, wherein the computer programmed to phase, correlating the adjacent image pairs comprises : a phase correlating a search region in a first image to a plurality of candidate regions in a second image at a first reduced resolution to determine a first translational offset; translating a center of the first and second images to a location indicated by the first translational offset; phase correlating the translated images to determine the centers of the overlapping regions at a second reduced resolution. 5. The apparatus of Claim 1, further comprising the computer programmed to assess suitability of overlapping areas in adjacent images for normalized cross correlation, comprising : selecting a plurality of candidate areas within the overlapping areas of adjacent images; 33 determining whether the signal to noise ratio for a plurality of candidate tie points within a first candidate area pass predetermined threshold requirements; rejecting the candidate tie points failing the predetermined threshold requirements; determining the candidate tie points located within a predetermined scene correlation range for the candidate tie points passing the predetermined threshold requirements; and classifying candidate tie points within the predetermined scene correlation threshold as suitable candidate tie points. 6. The apparatus of Claim 1, wherein the computer programmed to select initial candidate tie point locations comprises : (a) phase correlating a first adjacent image pair from the plurality of overlapping images to select initial candidate tie points; (b) rejecting initial candidate tie points not satisfying a threshold figure of merit value; (c) dewarping unrejected initial candidate tie points to a next adjacent image pair; 34 (d) phase correlating the next adjacent image pair to determine initial candidate tie points surviving for the next adjacent image pair; (e) rejecting surviving candidate tie points not satisfying a threshold figure of merit value; and (f) repeating (c) through (e) to determine candidate tie points surviving phase correlation and threshold figure of merit value requirements for each adjacent image pair in the plurality of overlapping images. 7. The apparatus of Claim 6, wherein the computer programmed to select initial candidate tie point locations further comprises : dewarping the candidate tie points surviving phase correlation and threshold figure of merit value requirements from the final image of the plurality of overlapping images to the first image of the plurality of overlapping images; comparing the surviving dewarped candidate tie points to corresponding initial candidate tie points; and rejecting the surviving dewarped candidate tie points not falling within a predetermined number of pixels of the corresponding initial candidate tie points. 35 8. The apparatus of Claim 1, wherein the computer programmed to determine the candidate tie point locations comprises : computing a RATIO average for each candidate tie point; sorting the candidate tie points according to the RATIO average into a list; and selecting the top candidate tie points from the sorted list. 9. The apparatus of Claim 1, wherein the computer programmed to determine the candidate tie point locations comprises : computing a PGF average for each candidate tie point; sorting the candidate tie points according to the PGF overages into a list; and selecting the top candidate tie points from the sorted list. 10. The apparatus of Claim 1, wherein the computer programmed to select initial candidate tie point locations comprises testing the top ranked candidate tie points. 11. The apparatus of Claim 10, wherein the computer programmed to test the top marked candidate tie points comprises : (a) determining distances between the top candidate tie points in each of the adjacent images within the plurality of overlapping images: 36 (b) determining standard deviations of the distances between the top candidate tie points from the distances determined in (a); (c) comparing the standard deviations for each of the distances between the top candidate tie points to predetermined threshold standard deviations; (d) passing the candidate tie points if all standard deviations do not exceed the predetermined threshold standard deviations; and (e) rejecting candidate tie points if any of the standard deviations exceed the predetermined threshold standard deviations. 12. The apparatus of Claim 1, wherein the computer programmed to phase correlate at full resolution the candidate tie points comprises : (a), phase correlating a first adjacent image pair from the plurality of overlapping images to select initial candidate tie points: (b). rejecting initial candidate tie points not satisfying a threshold figure of merit value; (c). dewarping unrejected initial candidate tie points to a next adjacent image pair; 37 (d). phase correlating the next adjacent image pair to determine initial candidate tie points surviving for the next adjacent image pair; (e). rejecting surviving candidate tie points not satisfying a threshold figure of merit value, and (f). repeating (c) through (e) to determine candidate tie points surviving phase correlation and threshold figure of merit value requirements for each adjacent image pair in the plurality of overlapping images. 13. The apparatus of Claim 12, wherein the computer programmed to phase correlate at full resolution the candidate tie points comprises : dewarping the candidate tie points surviving phase correlation and threshold figure to merit value requirements from the final image of the plurality of overlapping images to the first image of the plurality of overlapping images; comparing the surviving dewarped candidate tie points to corresponding initial candidate tie points; rejecting surviving dewarped candidate tie points not falling within a predetermined number of pixels of the corresponding initial candidate tie points. 14. The apparatus of Claim 1, wherein the computer programmed to refine the surviving tie point locations comprises : 38 fitting a quadratic surface to an array generated by the phase correlation of adjacent image arrays; determining a first peak location of the quadratic surface; determining a second peak location according to a predetermined function; and combining the first and second peak locations to determine a final tie point location. 15. Apparatus for image correlation to determine candidate time point locations, the apparatus comprising : an image generator having an output representing a series of overlapping images; a memory coupled to the image generator to accept the output representing a series of overlapping images; a computer coupled to the memory to receive the series of overlapping images, the computer programmed to : (a). phase correlating a first adjacent image pair from the plurality of overlapping images to select initial candidate tie points; (b). rejecting the initial candidate tie points not satisfying a threshold figure of merit value; (c). dewarping unrejected initial candidate tie points to a next adjacent image pair; 39 (d). phase correlating the next adjacent image pair to determine initial candidate tie points surviving for the next adjacent image pair; (e). rejecting surviving candidate tie points not satisfying a threshold figure of merit value; and (f). repeating (c) through (e) until candidate tie points surviving phase correlation and threshold figure of merit value requirements for each adjacent image pair in the plurality of overlapping images. 16. The apparatus of Claim 15, the computer further programmed to : dewarping the candidate tie points surviving phase correlation and threshold figure of merit value requirements from the final image of the plurality of overlapping image to the first image of the plurality of overlapping images; comparing the surviving dewarped candidate tie points to corresponding initial candidate tie points; rejecting surviving dewarped candidate tie points not falling within a predetermined number of pixels of the corresponding initial candidate tie points. 17. Apparatus for selecting tie point locations within a series of overlapping images, the apparatus comprising : an image generator having an output representing a series of overlapping images; 40 a memory coupled to the image generator to accept the output representing a series of overlapping images; a computer coupled to the memory to receive the series of overlapping images, the computer programmed to : selecting a plurality of candidate tie point locations from the overlapping images at a reduced resolution, by : ordering the overlapping images to maximize successful phase correlations between adjacent images; phase correlating adjacent image paris in an order provided by the ordering to determine an offset between overlapping areas; assessing suitability of overlapping areas for normalized cross correlation; selecting initial candidate tie point locations using normalized cross correlation between adjacent images: selecting top candidate tie point locations from the initial candidate tie point locations; refining the top candidate tie point locations to sub pixel accuracy at full resolution, by : phase correlating the candidate tie point locations between all adjacent images at full resolution to determine the surviving candidate tie points; and 41 refining the surviving candidate tie points to a sub pixel location. 18. Apparatus for identifying geographical tie points from a plurality of stereo images having common geographical coverage, the apparatus comprising : an image generator having an output representing a series of overlapping images; a memory coupled to the image generator to accept the output representing a series of overlapping images; a computer coupled to the memory to receive the series of overlapping images, the computer programmed to : estimating locations of corresponding geographical tie points from the plurality of stereo images; determining coordinates of the estimated geographical tie points; and selecting from the determined coordinates the estimated geographical tie points within the plurality of stereo images representing geographical tie points. 19. The apparatus of Claim 18, the computer further programmed to forming a geographical image from the selected geographical tie points. 20. The apparatus of Claim 18, wherein the computer programmed to estimate locations of the corresponding geographical tie points comprises : 42 ordering the plurality of stereo images to minimize differences between seasons of related images and the parameters defining the geometry of the related images; storing the ordered related images in a two column array; superimposing and shifting the ordered related images until the corresponding geographical tie points substantially coincide in an overlapping region to calculate translational offsets between the ordered related images; determined suitability of the overlapping region for normalized cross correlation; and determining locations of the corresponding geographical tie points by normalized cross correlation at a reduced resolution. 21. The apparatus of Claim 20, wherein the computer programmed to superimpose and shift the ordered related images comprises : phase correlating at a first resolution to generate a maximum figure of merit and a threshold figure of merit; comparing the maximum figure of merit to the threshold figure of merit; phase correlating at a second resolution when the maximum figure of merit exceeds the threshold figure of merit; and 43 proposing new locations of the corresponding geographical tie points by redensification when the threshold figure of merit exceeds the maximum figure of merit, and repeating comparing the maximum figure of merit to the threshold figure of merit. 22. The apparatus of Claim 21, wherein the computer further programmed to maximize the probability of selecting corresponding geographical tie points comprises calculating distances between the corresponding geographical tie points in three dimensional object space. 23. The apparatus of Claim 20, wherein the computer programmed to estimate locations of the corresponding geographical tie points comprises : testing for a closure to discard the corresponding geographical tie point locations that exceed a predetermined tolerance value; and maximizing the probability of selecting corresponding geographical tie points when determining coordinates of the estimated geographical tie points by ranking the corresponding geographical tie point locations remaining from the closure. 24. The apparatus of Claim 18, wherein the computer programmed to determine coordinates of the estimated geographical tie points comprises : 44 discarding the estimated geographical tie point locations that exceed a predetermined tolerance value; and estimating an accuracy of the estimated geographical tie point locations remaining after discarding to determine errors thereby enabling further refining the estimated geographical tie point locations. 25. Apparatus for identifying geographical tie points from a plurality of digital images having common geographical coverage, the apparatus comprising an image generator having an output representing a plurality of digital images; a memory coupled to the image generator to accept the output representing a plurality of digital images; a computer coupled to the memory to receive the plurality of digital images, the computer programmed to: estimating locations of corresponding geographical tie points from the plurality of digital images by : ordering the plurality of digital images to minimize differences between seasons of ordered adjacent digital images and the angles defining the geometry of the ordered adjacent digital images; storing the ordered adjacent digital images in a two column array; 45 superimposing and shifting the ordered adjacent digital images until the corresponding geographical tie points substantially coincide in an overlapping region to calculate translational offsets between the ordered adjacent digital images; determining suitability of the overlapping region for normalized cross correlation; determining locations of the corresponding geographical tie points by normalized cross correlation at reduced resolution; and testing for a closure to discard the corresponding geographical tie point locations exceeding a predetermined tolerance value; determined coordinates of the estimated geographical tie points; selecting from the determined coordinates the estimated geographical tie points within the plurality of digital images representing geographical tie points; and forming a geographical image from the selected geographical tie points. 26. The apparatus of Claim 25, wherein the computer programmed to estimate locations of the corresponding geographical tie points comprises; 46 testing for a closure to discard the corresponding geographical tie point locations that exceed a predetermined tolerance value; and maximizing the probability of selecting corresponding geographical tie points when determining coordinates of the estimated geographical tie points by ranking the corresponding geographical tie point locations remaining from the closure. 27. The apparatus of Claim 26, wherein the computer programmed to maximize the probability of selecting corresponding geographical tie points comprises calculating distances between the corresponding geographical tie points in three dimensional object space. 28. The apparatus of Claim 25, wherein the computer programmed to determine coordinates of the estimated geographical tie points comprises : discarding the estimated geographical tie point locations that exceed a predetermined tolerance value; and estimating an accuracy of the estimated geographical tie point locations remaining after discarding to determine errors thereby enabling further refining the estimated geographical tie point locations. 47 29. Apparatus for identifying geographical tie points from a plurality of digital images having common geographical coverage, the apparatus comprising : an image generator having an output representing a plurality of digital images; a memory coupled to the image generator to accept the output representing a plurality of digital images; a computer coupled to the memory to receive the plurality of digital images, the computer programmed to : estimating locations of corresponding geographical tie points from the plurality of digital images; determining coordinates of the estimated geographical tie points by : discarding the estimated geographical tie point locations that exceed a predetermined tolerance value; and determining an accuracy of the estimated geographical tie point locations remaining after discarding to determine errors thereby enabling further refining the estimated geographical tie point locations; selecting from the refined estimated geographical tie point locations geographical tie points within the plurality of digital images; and forming a geographic image based on the selected geographical tie points. 48 30. The apparatus of Claim 29, wherein the computer programmed to estimate locations of the corresponding geographical tie points comprises : ordering the plurality of digital images to minimize differences between seasons of related images and the parameters defining the geometry of the related images; storing the ordered related images in a two column array; superimposing and shifting the ordered related images until the corresponding geographical tie points substantially coincide in an overlapping region to calculate translational offsets between the ordered related images; determining suitability of the overlapping region for normalized cross correlation; and determining the locations of the corresponding geographical tie points by normalized cross correlation at reduced resolution. 31. Apparatus for identifying geographical tie points from a plurality of digital images having common geographical coverage, the apparatus comprising : an image generator having an output representing a plurality of digital images; a memory coupled to the image generator to accept the output representing the plurality of digital images; 49 a computer coupled to the memory to receive the plurality of digital images, the computer programmed to : estimating locations of corresponding geographical tie points from the plurality of digital images at reduced resolution by : ordering the plurality of digital images to minimize differences between seasons of ordered adjacent digital images and the angles defining the geometry of the ordered adjacent digital images; storing the ordered adjacent digital images in a two column array; superimposing and shifting the ordered adjacent digital images until the corresponding geographical tie points substantially coincide in an overlapping region to calculate translational offsets between the ordered adjacent digital images; determining suitability of the overlapping region for normalized cross correlation; determining locations of the corresponding geographical tie points by normalized cross correlation at reduced resolution; testing for a closure to discard the corresponding geographical tie point locations exceeding a predetermined tolerance value; and 50 determining coordinates of the estimated geographical tie points at full resolution by ; discarding the estimated geographical tie point locations that exceed a predetermined tolerance value; and determining an accuracy of the estimated geographical tie point locations remaining from the step of discarding to determine errors thereby enabling further refining the estimated geographical tie point locations; and selecting from the refined estimated geographical tie point locations geographical tie points within the plurality of digital images; and forming a geographic image based on the selected geographical tie points. 32. Apparatus for selecting tie points within a sequence of overlapping digital images, the apparatus comprising : an image generator having an output representing a sequence of overlapping digital images; a memory coupled to the image generator to accept the output representing a sequence of overlapping digital images; a computer coupled to the memory to receive the sequence of overlapping digital images, the computer programmed to : 51 identifying tie point locations from the sequence of overlapping digital images by phase correlation at a reduced resolution; and refining the identified tie point locations to sub-pixel accuracy by normalized cross correlation at full resolution to select tie points within the sequence of overlapping digital images. 33. The apparatus of Claim 32, wherein the computer programmed to identify tie point locations comprises : ordering the sequences of overlapping digital images to maximize the number of successful phase correlations between adjacent image pairs; calculating translational offsets between the adjacent image pairs; assessing suitability of overlapping areas of normalized cross correlation; and determining the tie point locations by normalized cross correlation at a reduced resolution. 34. The apparatus of Claim 33, wherein the computer programmed to identify tie point locations further comprises : testing for a closure to discard the tie point locations that exceed a predetermined tolerance value; and 52 ranking the tie point locations remaining from the closure to maximize the probability of selecting tie points during refining the identified tie point locatins. 35. The apparatus for Claim 34, wherein the computer programmed to rank tie point locations further comprises calculating distances between the tie point locations to consensus check in three dimensional object space. 36. The apparatus of Claim 32, wherein the computer programmed to refine the identified tie point locations comprises : testing for a closure to discard the tie point locations that exceed a predetermined tolerance value; and estimating an accuracy of the tie point locations remaining from the closure to determine errors thereby enabling further refining the tie point locations to sub-pixel accuracy. 37. Apparatus for selecting tie points within a sequence of overlapping digital images, the apparatus comprising : an image generator having an output representing a sequence of overlapping digital images; a memory coupled to the image generator to accept the output representing a sequence of overlapping digital images; 53 a computer coupled to the memory to receive the sequence of overlapping digital images, the computer programmed to: identifying tie point locations from the sequence of overlapping digital images by phase correlation at a reduced resolution, by : ordering the sequence of overlapping digital images to maximize the number of successful phase correlations between adjacent image pairs; calculating translational offsets between the adjacent image pairs; determining suitability of overlapping areas for normalized cross correlation; determining the tie point locations by normalized cross correlation; testing for a closure to discard the tie point locations that exceed a predetermined tolerance value; and refining the identified tie point locations to sub-pixel accuracy by normalized cross correlation at full resolution, by: conducting the closure test to discard the tie point locations that exceed a predetermined tolerance value; and estimating an accuracy of the tie point locations remaining from the closure to determine error associated 54 with estimating to further refine the tie point locations to sub-pixel accuracy. Dated this 8th day of August, 2002.

Documents:

716-mum-2002-cancelled pages(27-02-2008).pdf

716-mum-2002-claims(granted)-(27-02-2008).doc

716-mum-2002-claims(granted)-(27-02-2008).pdf

716-mum-2002-claims.doc

716-mum-2002-claims.pdf

716-mum-2002-correspondence((10-03-2008).pdf

716-mum-2002-correspondence(ipo)-(11-04-2008).pdf

716-mum-2002-correspondence-received-ver-061106.pdf

716-mum-2002-correspondence-received-ver-070806.pdf

716-mum-2002-correspondence-received-ver-270103.pdf

716-mum-2002-correspondence-received.pdf

716-mum-2002-description (complete).pdf

716-mum-2002-drawing(08-08-2002).pdf

716-mum-2002-drawings.pdf

716-mum-2002-form 1(08-08-2002).pdf

716-mum-2002-form 1(27-01-2003).pdf

716-mum-2002-form 18(08-08-2006).pdf

716-mum-2002-form 2(granted)-(27-02-2008).doc

716-mum-2002-form 2(granted)-(27-02-2008).pdf

716-mum-2002-form 3(06-11-2006).pdf

716-mum-2002-form 3(08-08-2002).pdf

716-mum-2002-form 5(08-08-2002).pdf

716-mum-2002-form 5(13-02-2008).pdf

716-mum-2002-form 5(27-01-2003).pdf

716-mum-2002-form-1.pdf

716-mum-2002-form-18.pdf

716-mum-2002-form-2.doc

716-mum-2002-form-2.pdf

716-mum-2002-form-26.pdf

716-mum-2002-form-3-ver-031106.pdf

716-mum-2002-form-3.pdf

716-mum-2002-form-5-ver-141002.pdf

716-mum-2002-form-5.pdf

716-mum-2002-form-pct-isa-210(08-08-2002).pdf

716-mum-2002-petition under rule137(07-11-2006).pdf

716-mum-2002-petition under rule138(27-02-2008).pdf

716-mum-2002-power of attorney(06-11-2000).pdf

abstract-1.jpg

abstract1.jpg