Automatic Tie-point Extraction

One of the most complex and time-consuming tasks in the photogrammetric workflow is the extraction of corresponding points in two or more overlapping images. This is the first stage of aerial triangulation and block adjustment aimed at computing the positions of the projection centre and the orientation of each image. Automating the extraction of these so-called ‘tie points’ can be challenging, especially when non-standard approaches such as cameras mounted on UAVs or oblique imagery are used. The authors present a novel matching method able to handle the most challenging imagery.

The aim of matching is to identify corresponding points in imagery overlaps in a photogrammetric block. Since the early eighties, countless methods have been developed, all with their own advantages and disadvantages. However, images resulting from some of the new camera systems and platforms, and images recorded under harsh weather conditions, require more robust approaches. Therefore, a new matching method was developed – named MatchMe – and implemented as a module in Icaros’ IPS (Icaros Photogrammetric Suite). The method consists of a three-step sequence: (1) Extracting – in each image – distinctive points which sufficiently contrast with their vicinity, (2) Assigning feature descriptors to each and every distinctive point, and (3) Determining corresponding points in the image overlaps based on similarity of the feature descriptors.

Distinctive Points
Today’s approaches rely on the extraction of distinctive points in each image, after which a matching process is conducted on the features assigned to these points. These practices are gradually replacing the classical approaches which are typically based on correlation, least squares matching or other algorithms carried out on the grey values in selected image patches. Our approach for extracting distinctive points in each image has been inspired by the well-known Förstner operator, developed in 1986, and is further based on pyramids of multiple scale images, all derived from the original scale. Using a multi-scale approach, salient points which are dominant with respect to their environment and with respect to the scale-level are determined. To further refine the position and scale of an extracted point, a quadratic fitting model is applied. The implementation of the method exploits the GPU (Graphic Processing Unit) hardware, which leads to faster processing compared to other methods. Table 1 shows time scores for runs of four types of images on an Intel i7 QuadCore machine with 12GB memory and an NVIDIA Tesla C1060 graphics board. Additionally, the method shows a better distribution of the points over the image resulting in a more stable geometry of the photogrammetric block.

Feature Descriptors
For each point, a feature descriptor is generated which represents the derivatives of the grey values of the pixels around the point and consists of non-negative values normalised to unit length (0-1). To make the descriptor invariant to rotation transformations, the dominant orientation angle is extracted first and used as a datum. Instead of using the grey values themselves, invariance to illumination is gained by taking into account the directional derivatives of a point relative to its neighbouring pixels. The values are also clipped to make the method robust to other photometric variations. Using these descriptors, the method is robust in cases such as large baselines, oblique imagery and other non-conventional perspective differences between the images.

Corresponding Points
A search for corresponding points can start by evaluating the two sets of descriptors of each candidate image pair, i.e. for each descriptor of a point in the first image, one searches for the most similar descriptor of the points in the second image. The points which show the highest similarity are selected as corresponding points. The above approach only concerns image pairs. For aerial triangulation, however, tie points connecting more than two images are essential. These kinds of tie points, also called multi-ray points, are very important for the photogrammetric block stability and thus significant in preventing discontinuities and inconsistencies in DTMs, mosaics and 3D models and other final products. To generate a single set of multi-ray points out of multiple sets of pair-wise point matches, a process of global unification is applied. This process is based on a connection graph in which each of the edges represents an image-pair tie point. Each component of connectivity in this graph is forming a global point with multiple rays. This method typically yields thousands of multi-ray points whereas aerial triangulation requires just several dozens for each image. Therefore, only points with the highest descriptive values and those showing the highest level of confidence are selected.

Interface and Analysis
While the method works in a fully automated manner, the MatchMe module offers a complete user interface. The interface allows the process parameters to be configured, thus enabling different solutions for different terrain types and project demands. Tools for editing the points using a simple and yet comprehensive visual interface have been implemented too. The user interface consists of three synchronised views (table, image and map) which provide a range of analysis and editing tools to quickly access, manipulate and resample all the data elements including points, rays and images. In the map view (Figure 1, above, left), image centres are overlaid on an orthophoto and the width of the lines between image centres represents the strength of the connections between image overlaps.

Examples
The first example concerns the processing of imagery from a payload with five small-format 16MP cameras – four oblique (focal length 65mm) and one nadir (focal length 85mm). The project contained 3,200 images covering the entire Tel-Aviv metropolitan area captured by SightVision Israel Ltd. The oblique cameras were positioned in four perpendicular viewing directions. The Ground Sample Distance (GSD) for the nadir images was 15cm. After 4.5 hours of computation, MatchMe produced 36,673 points with sub-pixel accuracy (RMSE: 0.8 pixels) (Figure 2). After a few days, the orthomosaic and all image orientations could be delivered and a third party generated a 3D city model using the aerial triangulation output (Figure 3).

The second example concerns imagery taken under clouds and precipitation conditions in Congo for a leading energy company, which needed to map the area around a planned pipeline. The area was captured in 4,950 images (GSD 30cm) using a 21MP Cannon MK III camera (focal length 50mm). Our method delivered an output of 54,450 points with sub-pixel accuracy (RMSE: 0.4 pixels) after seven hours of computation. Figure 4 shows two images with poor viewing conditions and the points extracted; even in areas covered by clouds, the same points have been detected in the two overlapping images.

Concluding Remarks
Matching can also be carried out with existing orthophotos to introduce new images in the orthophotos’ reference system (Figure 5). The method has proven to give robust and high-quality results with sub-pixel accuracy for an unlimited number of images in the same block, even when base lines are long and the perspective differences between the images are large. The method also performs well under adverse weather conditions. Compared to other commercial software, computation is fast while fewer steering parameters have to be set.

This article is modified from a paper presented previously at ASPRS 2011 Annual Conference, Milwaukee, Wisconsin, USA, 1st-5th May 2011.

Further Reading
- Förstner, W., 1986, A feature-based correspondence algorithm for image matching. Intl. Arch. Photogrammetry & Remote Sensing, 26 (3), pp. 150–166.
- Harris, C., Stephens, M. J. 1988, A combined corner and edge detector. In Alvey Vision Conference, pp. 147–152.
- Nister, D., 2004, An efficient solution to the five-point relative pose problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (6), pp. 756–777.
- Philip, J., 1996. A non-iterative algorithm for determining all essential matrices corresponding to five point pairs. Photogrammetric Record, 15(88), pp. 589–599.
- Snavely, N., Seitz, S. M., Szeliski, R., 2006, Photo tourism: Exploring photo collections in 3D, ACM Transactions on Graphics (SIGGRAPH), 25 (3), pp. 835–846.