Patent ID: 12243248

DETAILED DESCRIPTION

Provided herein are systems and methods for registration (i.e., matching) and carrying out fine image adjustments of aerial or satellite images. Also provided are systems and methods for registration where resampling is minimized or avoided altogether which may reduce degradation of or preserve spectral purity.

As mentioned, DEMs of high accuracy and fine resolution can be very difficult and/or expensive to generate, particularly in remote areas and/or mountainous regions. Satellite imagery often covers entire countries not just areas around cities or towns, and country wide elevation models can be difficult to obtain. Further, if such elevation models are available, and often they are not, they can be expensive to buy (in many countries they are not free) or foreign countries may consider them sensitive for security reasons. Thus, many satellite images are corrected with open source or public domain data which may have a low resolution, such as from 30 m to 5 m (depending on the country).

Obtaining GCPs is also required for ortho correction. Typically, GCP data needs to be much finer in resolution than elevation data. For example, for a 1 m resolution satellite, ground control of 25 cm to 10 cm might be required. Getting such ground control data may be considered expensive outside populated areas since it is often the case that a surveyor must visit the location. With regard to camera distortion, large, expensive satellites which may not be affordable for many, tend to provide accurate distortion information however the multitude of lower cost micro satellites tend to have inaccurate, or no, distortion information.

In addition, it is possible that data from different satellite sensors can be mixed together, or data from the same sensor may be acquired at different times. The input elevation and GCPs improve over time and this can mean that older ortho images may not match precisely with the newer ones because the inputs have changed. The older ortho images could be regenerated from scratch with the new DEM, GCPs, but this may not be practical and still does not guarantee perfect alignment.

The following provides an introduction to the nomenclature used hereinafter to describe the methods of the present disclosure.

An input image (I) can be mapped to an output (resampled) image (O) via the transformation:
I→O[xi,yi]  (Equation 1),

where i ranges over the number of columns in the output image and j ranges over the number rows in the output image.

The output image O at pixel location (i,j) may be resampled from the input image I centred at position [xi, yj]. For example, the output pixel position (2, 3) may have the value x2=10.3; and y3=15.1, which means the output image pixel position (column=2 and row=3) would be resampled from the input image pixel position (column=10.3 and row=15.1). This process is described in greater detail below.

An example of a resampling method is shown inFIG.1, where there is depicted an input raster image2having input positions: A: (0.4, 1.2); B: (1.8, 2.9); C: (3.5, 5.5); D: (2.9, 1.9); and E: (4.5, 3.5). The input positions may be sampled from the input raster image10into an empty raster matrix to create a resampled output raster image12. An output matrix O[xi, yj] (14) of the saved sample positions is also depicted. The resampling method used is independent of this representation. Resampling methods may include, but are not limited to, nearest neighbour, cubic convolution, sinc functions or the modulation transfer function for a particular sensor (if known).

In an ortho image, the mapping (eq. 1) is derived from the sensor geometry (which can include: block bundle adjustments based on GCPs and TPs, camera lens models, camera movement, cartographic projection) and a digital elevation model (DEM). Typically, in the ortho correction process, the mapping (eq. 1) is embedded in the ortho production process and is not explicitly saved, only the resulting output raster image is produced. However, if the mapping is saved explicitly, it can be used to directly generate the ortho product at a later time without the need for knowledge of the sensor geometry or having the DEM available. Since the ortho mapping is being saved, it can be denoted for later use as:
I→O′[xi,yj]  (Equation 2).

FIG.2illustrates a method of generating an ortho image. First, at step20, a raw image, DEM and geometric may be retrieved. This may be done by, for example, launching a job on a computing device (not shown), such as a server in a system (not shown) for processing image data. The computing device may run one or more job scripts to call processing modules which may access image data and related data. Generally, such job scripts may include instructions which are executable by the computing device to carry out the image processing methods described herein. Next, at step22, a resample grid may be computed. Optionally, the resample grid may be saved (step28) as described above. Using the resample grid, an ortho image may be generated24, and subsequently saved (26) to, for example, an image database or database server (not shown) to which the computing device has access.

Access to databases and data files is inherent in the operation of most networks and thus the computing device(s) may be located anywhere on a network that communicatively couples the modules and devices described herein. Processing of data may be accomplished by processing modules written in a computer language such as, for example, C or C++. Such modules may be written such that they can transparently accept a variety of data input sources including, but not limited to, local files, network files, databases, passed memory data structures or data from standardized web services. For example, a job script performing ortho correction may have a processing module that can obtain elevation data from a local file and may, as a fall back, be configured to utilize a web service providing Earth elevation data. The scope of the present disclosure is not limited by the nature of the processing modules (many processing modules are known), and the methods described herein may be carried out using various system architectures.

Continuing with respect to ortho correction, in theory, two ortho products of the same resolution and cartographic project should perfectly align. That is, features such as roads, fields, should perfectly lay on top of each other. However, this is often not true in practice. Each ortho image may have its own unmodeled errors. In some areas of each image, alignment may be perfect, and in other areas off by many pixels. Simple corrections, such as a constant shift of an entire image, may not correct the alignment since the errors may vary in complex ways.

The above discussed complex error variation may be addressed by a technique known as dense matching. Given a reference image R and an image M to match to it, a matching algorithm may be used to match points in R to their corresponding points in M. Such matching algorithm may be run by, e.g., a processing module running a job script as described above. While matching every point in R is desirable, it may be too time consuming and/or may require higher computing power than is available. To accelerate matching, match points may be found in a grid of every n′th column and n′th row which may speed up the process by order n2. As described in greater detail below, missing match points between the grid match locations may be interpolated. In practice values of n=8 or n=16 have been found to provide a good balance between speed and ability to model complex error patterns. This may be particularly beneficial when limited computing power is available.

Similar to Equation 1, this transformation can be expressed as:
IM→OR[xi,yj]  (Equation 3),

where IMrefers to the image to be matched to the reference image R, and OR[xi, yj] refers to the location of the match on the image M.

With reference toFIG.3, images M and R, though of the same geographic area, will have differences in addition to their similarities. For example, two images may be taken weeks or years apart and features such as new roads may appear, farmers fields may change in crop or shape, trees may die, or water bodies may change level. The matching algorithm may have some level of match failures and blunders (i.e., incorrect matches). Such matching may be carried out at step32, where image R may be matched to image M on a 1/nth row and a 1/nth column grid. Next, at step34, the set of match points generated at step32may be filtered to remove such blunders. Detecting which points are blunders may be done using an adaptive filtering technique which may analyze the magnitude of the [xi, yj] shifts in a local N×N neighbourhood and remove those outside a statistical threshold (for example, 2 sigma). This approach may automatically adapt to the level of misalignment which can vary through the images.

The resulting filtered grid OR[xi, yj] will thus have locations with missing match points. The missing match points may be interpolated from surrounding valid match points (step36). Such match points may be deemed valid by, for example, being at or below the statistical threshold for misalignment. Other adaptive techniques may be used to identify blunders.

It is desirable that the point matching algorithm is robust to obtain accuracy to the subpixel level. It may be preferable to use Fast Fourier Transform (FFT) phase matching which has been demonstrated in the literature to have accuracies of better than 1/10thpixel in appropriate circumstances. Other matching algorithms may also be used. Optionally, the filtered and interpolated grid OR[xi, yj] may be smoothed via a Gaussian filter to remove small scale jitter (step38).

At step40, it may be determined whether the filtered grid is 1:1 dimensionally with respect to the reference image R. If the filtered grid is not 1:1, it can be interpolated to be 1:1 at step42, for example using bi-linear interpolation. Following steps40and42, using the filtered and interpolated grid OR[xi, yj], the match image M may be resampled to match the reference image (44). The grid can then optionally be saved for later use (step46), and the super registered image M generated at step44may be saved (e.g., to a database). Numerous experiments have shown that alignment achieved using this method may be within about ⅕thto about 1/10thof pixel across the entire image area.

Dense matching tends to be expensive computationally, and thus it can be desirable to avoid 1:1 matching. The above described 1:N matching is N*N (N squared) times more efficient than 1:1 matching. It may be that using 1:N level matching in combination with interpolation of missing points as described above is less computationally expensive as compared to conventional methods for dealing with or avoiding match failure and blunders.

Building on the method described above with respect toFIG.3, any number, N, of match images (M1, M2, M3, . . . MN) may be matched and resampled to a single reference image R. This may create a super matched stack of images in which all N match images are super matched to the reference image and to each other. A super matched stack, which may be highly aligned or nearly perfectly aligned, e.g., within about ⅕th to about 1/10th of pixel), may enable temporal series change detection and analysis algorithms (such as Continuous Change Detection) to be run on the stack with higher accuracy.

Each time a pixel is resampled the spectral purity is degraded and the image becomes “fuzzier”. This, in turn, degrades the accuracy of any analysis performed on the image (such as continuous change detection or pixel based classification). Keeping the number of resamples to a minimum to preserve spectral purity is often desirable.

In the above-discussed method, match image M may be resampled two times, once to create the ortho image, and a second time when the ortho image is resampled to match the reference image R.

If the grid to create the ortho image for image M is available (Equation 2), and the grid mapping M to the Reference image R is available (Equation 3), these equations can be chained sequentially as:
IM→O′M[xi,yj]→OR[ui,vj]  (Equation 4),

where [ui, vj] is the same grid meaning as [xi, yj] but uses different letters for ease of explanation.

Turning toFIG.4, the two displacement grids in Equation 4 may be obtained (steps50and52) and added on an element by element basis to output a single displacement grid which combines both the ortho correction and the super registration to the reference image R (step54). This displacement grid may then be used to perform the two operations in a single resample which may result in greater spectral purity and a less blurry image as compared to if the operations were carried out over two resamples (steps56and58). This given in equation 5 shown below. The resampled super registered image with greater purity may then be saved at step60. Further, by having the ortho grid (step50inFIG.4) and the match grid (step52) available for a single resample (step56), computational efficiency may in some cases be increased as compared to when such operations are not completed in a single step.
IM→OR[xi+ui,yj+vi]  (Equation 5)

By repeating the above method, each of any number N of match images (M1, M2, M3, . . . MN) may be matched and resampled in a single resample to a particular reference image R. This may create a super matched stack of images in which all N match images are super matched to the reference image and to each other and may have greater spectral purity and less blurriness as compared to a stack generated by the method described with respect toFIG.3, which involves two resampling steps.

In some circumstances, the original (unsampled) spectral values are desired, even if this may result in a decrease in positional accuracy. This may be achieved by using Nearest Neighbour resampling which copies the nearest pixel to the resample location as described in Equation 5. As shown inFIG.5, this method differs from that shown inFIG.4at steps62and62. Nearest Neighbour resampling (step62) may introduce a positional error of up to about plus or minus one half pixel. The resulting increased positional error may still be subpixel and in applications where preserving spectral purity is important, this may be an acceptable trade off. At step64, the spectrally pure super registered image may be saved.

By repeating the method discussed above and shown inFIG.5, each of any number N of match images (M1, M2, M3, . . . MN) may be matched may use nearest neighbour resampling to a single reference image R. Such method may create a super matched stack of images in which all N match images are super matched to the reference image, may be super matched to each other within +/− one half pixel and may have little to no spectral degradation since spectral values are copied rather than combined with neighbouring pixels.

The methods described herein may be embodied in sets of executable machine code stored in a variety of formats such as object code or source code. The executable machine code or portions of the code may be integrated with the code of other programs, implemented as subroutines, plug-ins, add-ons, software agents, by external program calls, in firmware or by other techniques as known in the art.

Any module or component exemplified herein that executes instructions may include or otherwise have access to computer readable media such as storage media, computer storage media, or data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Computer storage media may include volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. Examples of computer storage media include RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by an application, module, or both.

For simplicity and clarity of illustration, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements. In addition, numerous specific details are set forth in order to provide a thorough understanding of the examples described herein. However, it will be understood by those of ordinary skill in the art that the examples described herein may be practiced without these specific details. In other instances, well-known methods, procedures and components have not been described in detail so as not to obscure the examples described herein. Also, the description is not to be considered as limiting the scope of the examples described herein.

It will be appreciated that the examples and corresponding diagrams used herein are for illustrative purposes only. Different configurations and terminology can be used without departing from the principles expressed herein. For instance, components and modules can be added, deleted, modified, or arranged with differing connections without departing from these principles.

The steps or operations in the flow charts and diagrams described herein are just for example. There may be many variations to these steps or operations without departing from the principles discussed above. For instance, the steps may be performed in a differing order, or steps may be added, deleted, or modified.

Although the above principles have been described with reference to certain specific examples, various modifications thereof will be apparent to those skilled in the art as outlined in the appended claims.