Home

Aerial image matching

Introduction

The project is dedicated to automated matching of high-resolution aerial images. This problem arises in such areas as cartography, geodesy, Earth monitoring and others. Image matching is the first stage within the aerial image processing cycle and must be carried out robustly in order to produce qualitative orthophotomaps and precise digital surface and terrain models (DSM, DTM).

The proposed algorithm employs the feature-based image matching approach. It takes a block of images as an input (Figure 1) and returns a number of feature points, each being present in two or more images. Thus, the output of the algorithm can be used for computing image transformations and for image stitching.


Figure 1. Input data example: 2 routes with 3 images in each

The block of images is actually a set of aerial photo sequences called routes. For each image the route it belongs to is known. The order of images within a route is also supposed to be defined as this information is usually easily available. Figure 1 represents an example of input data consisting of 2 routes with 3 images in each. Relative locations of routes are unknown and must be computed automatically. There can be an arbitrary number of images in a block. The resolution of each image is up to 200 megapixels.

This project has been conducted in cooperation with Racurs company. It originates from the GML Aero Matching project.

The proposed algorithm

The algorithm consists of the following main steps:

  • Image pyramid generation. Because original images are too large, their small copies are used first. Original images form the lowest pyramid level, while the small ones represent the highest level.
  • Block assembly at the highest pyramid level. At this step the small copies of images are linked into a single block. Such tasks as automatic overlap area computation, selection of images for matching and feature-based matching are solved at this stage.
  • Matching at the lowest pyramid level. The overlapping images are rematched at the lowest level of the pyramid (information about overlap is retrieved at the previous step). For optimization reasons pairs of matching points are gathered within special zones. Among the problems solved at this step are: zones’ selection, zones’ propagation from one image to another and zonal matching. Note that though GPS / IMU data, when available, makes the previous step easier, it is anyway necessary to rematch at the lowest level to achieve high accuracy.
  • Points’ propagation. After the matching points for image pairs are retrieved, they are propagated to other images in which they appear. Points that are present in multiple images are crucial for further block stitching.

In matching process Harris corner detector and SIFT descriptor are used. Matching errors are eliminated by the use of a RANSAC-like model estimation algorithm with homography and fundamental matrix being employed as models. For robustness reasons such methods as NNDR (Nearest Neighbour Distance Ratio) filter, edge filter, topological filter, iterative matches’ generation and some others are applied.

The main achievements

A number of unique algorithms have been developed, including the following:

  • Automatic block assembly at the highest pyramid level. Images within routes and routes themselves are linked without any user interaction.
  • Selection of images for matching at the highest level based on dynamic queue with priorities. As routes may be located in arbitrary way with respect to each other, it is important to detect the areas of their contiguity, i.e. overlapping images, as soon as possible to fasten the whole assembly process.
  • Automatic image overlap area detection
  • Zones selection algorithm for matching at the lowest pyramid level. Not all the areas of Earth surface are equally suitable for matching. For example, urban areas are preferable to forests and water as they produce more feature points. Thus it is important to retrieve matches within “good” zones first and not to employ other zones until necessary.
  • Automatic conflicts’ resolution. Conflicts correspond to cases of violation of some basic principles such as unambiguousness of matches and their transitivity (for points being present in more than 2 images). Conflicts may appear, for example, after the points’ propagation procedure.

Note that the proposed aerial image matching procedure is fully automatic.

Automatic image overlap area detection

The automatic image overlap area detection algorithm is an important part of the described aerial image matching procedure. It allows to cope successfully with the cases of extremely low overlap (Figure 2).


Figure 2. The result of automatic image overlap area detection algorithm

The main idea is to use the Hough voting scheme for detecting images’ relative shift and rotation. A detailed description of the algorithm and results can be found in the following paper that has been accepted for publication at the Photogrammetric Computer Vision and Image Analysis ‘2010 conference proceedings:

The project team