Measuring in photographs requires detecting the same point in multiple photographs. Doing so for each pixel creates a very dense set of measurements: a point cloud. This technique is called Dense Matching.
A camera is a passive measurement system in which reflected sunlight or artificial light is recorded by photographs. Unlike laser scanning, which is an active measurement system, photos require an additional processing step to create point clouds from the photos. This is done by finding corresponding points in overlapping photographs, then calculating the X,Y,Z coordinates of the corresponding object points.
In digital images, finding corresponding points can be done automatically with image matching techniques, also called Structure from Motion (SfM). The three main methods are (1) Area-based (ABM), (2) Feature-based (FBM) and (3) Semi-Global Matching (SGM). ABM and FBM are local methods.
Local Methods
Local methods first detect small image windows with sufficient contrast or texture - target patches - in the single image. Detecting and using such image windows with distinctive points is important to obtain a reliable match. The corresponding point in the overlapping image is known approximately from the position and orientation of the camera during image capture and global information about local elevation differences.
One way to find corresponding points in ABM is to slide the target patch pixel by pixel over a search window in the other image - search patch - and calculate a similarity measure for each pixel (Figure 1). Cross-correlation is often used which takes on values between -1 and +1. The pixel with the highest similarity value is the corresponding point. In a follow-up calculation, the location of this point can be determined with subpixel accuracy. A disadvantage of cross-correlation and other statistical measures is that there should be little difference in shooting angles; the overlapping pictures should be more or less parallel to each other.
Figure 1 - Sliding a window from one image (target patch) over a search window in the other image (search patch); a similarity value (R) is calculated for each pixel. Only for the pixels where R is greater than a threshold value is indicated in green.
A special ABM method is matching based on the least squares method - Least-Squares Matching (LSM) - which can handle large differences in shooting angles between the two pictures and is very accurate. The disadvantage is that the mutual location of the corresponding points must be known to within a few pixels. This makes this method especially suitable for capturing the location of the corresponding points in very accurate x,y image coordinates after a coarser match has been found using another method.
In FBM, the gray values are not used directly for calculating similarity. First, the gray values in both windows are converted to features that require the first or second derivatives of the gray values. The derivatives are calculated with digital differentiation operators (Figure 2). Then the values of the features of a point in the target patch are compared with those of the features of points in the search window. The point whose features best match is the searched point. Often LSM is then applied to increase the accuracy of the X,Y,Z coordinates.
Figure 2 - FBM: digital operators (left) are used to differentiate gray values of the image once (center) or twice (right); features are calculated from the derivatives.
To detect mismatches in ABM and FBM, a check is made to see if the points lie sufficiently well on a predefined surface described by a mathematical model. The points that do not lie (approximately) on that surface are removed as mismatches. This check for global consistency is performed as a final step and is not part of the matching itself.
Local methods are fast and very accurate and are therefore mainly used for the accurate co-registration of overlapping pictures. They are less suitable for producing dense point clouds for the following reasons:
- In areas with little texture or low contrast, no or unreliable matches can be found; the point density here is low resulting in a heterogeneous distribution of points which is unfavorable for many applications
- Mismatches occur in areas with repetitive patterns (Figure 3)
- In occlusion and high buildings (sudden height jumps) it is impossible or difficult to find matches
Figure 3 - Repetitive patterns, such as aligned parking spaces, lead to ambiguity resulting in mismatches.
Semi-global Matching (SGM).
The idea of global matching is that matching and global consistency, unlike local methods, are integrated and thus implemented simultaneously. It had long been known that global matching produces dense point clouds, but implementation seemed impractical due to high computation times and memory consumption. With the increasing demand for dense point clouds, finding a solution became increasingly sticky. Around 2010, the combination of increases in computing power and the development of a clever way to reduce global matching from a 2D problem to a quasi 1D problem led to the rapid emergence of dense image matching techniques based on semi-global matching (SGM). Here not all pixels in the image overlap are used but only pixels lying on 8 or 16 symmetric paths in the overlap (Figure 4). This provides a good approximation of global matching while making the method fast.
Figure 4 - Semi-global matching using 8 symmetric paths. The directions of the paths correspond to rows, columns and the two diagonals of the digital photo.
How do you bring local matches and global consistency together in one mathematical formula so that they can be performed simultaneously? This can be done by adding the local similarity values across paths and subtracting from the sum penalty points when neighboring pixels do match but their height differences are large compared to the predefined surface model.
SGM is a general method and can be implemented in many ways. It is currently part of about a dozen commercial photogrammetric software packages, often as a separate module of a larger package. The high level of detail that can be achieved in a photogrammetric point cloud created with SGM is shown in Figure 5.
Figure 5 - A point cloud of a built-up area fabricated with semi-global matching from overlapping photos taken from a drone. Note the good reconstruction of the white building with hardly any contrast and texture.
Image matching, like laser scanning, is a non-selective measurement technique. Unwanted objects must be removed, and this can be done automatically with digital filters. But these filtering techniques never work perfectly and a labor-intensive visual check is always required.
The geometric quality of point clouds from Dense Matching is highly dependent on the quality of the input data used. It is important that all lens distortion parameters are properly applied and that the correct attitude positions of the images are used. Because many software prioritize processing software and beautiful results, the geometric quality of these types of point clouds is highly variable. This is especially true for surfaces with little texture and for point clouds calculated over very large areas. Good quality control is therefore important.
