Feature matching based on corner and edge constraints

The principle underpinning stereo vision—comparing like but disparate images—is essential for calculating distances in applications that include 3D recognition, aircraft navigation, and motion analysis. A critical component of such calculations is matching image features, in particular corners and edges, which simplifies search space by extracting essential information from complex data. But feature matching is difficult to do quickly and accurately. One problem is that of detecting edges and their connectivity. A second problem is a lack of geometric constraints, which makes image edges hard to define in the first place.

Much work has been carried out in this area over the last several years.^1–4 Han and Park,¹ for example, proposed a contour-matching algorithm based on contour endpoint constraints and distance measures, and epipolar constraints, which reduce the search space from the whole image to a single line. The disadvantage of this algorithm is that it is sensitive to noise disturbance. Yuan² used a robust cooperative strategy to match contours with epipolar geometry, but the computational demands of this approach are high. Park and Han³ proposed a technique that can estimate contour motion; however, it is unreliable if the contour arc length varies or the contour has occluding parts.

Corners are important 2D local image features.⁴ With the aid of other known methods,⁵ corners can be matched with 100% accuracy. The epipolar constraint, already mentioned,^1–6 and the so-called continuity constraint are two such techniques that can be applied. Yet the problem of speed remains. Here, we propose a new, fast edge-matching algorithm based on corner and edge constraints that limits the search region to only a few pixels and thus improves matching time.

The algorithm consists, first, in finding a set of corners⁷ and edges.⁸ Second, matched corners are established using the method reported by Zhang and colleagues for recovering unknown epipolar geometry.⁵ The next challenge is how to use matched corners to guide edge matching. In general, a corner is unlikely to lie precisely in an edge. Thus, we describe two kinds of edges: edges near corners, and edges far from corners.

For edge matching near matched corners, the closest distance between the corner and the edge is short (e.g., less than four pixels). In such a small region, distortion is inconsequential. Once matched corners—we refer to them as 1 and 2—have been determined, a propagation strategy to seek possible matched edge points is performed in eight directions. If an edge point is met in some expanded direction simultaneously, we can attain two matched edges. For example, as shown in Figure 1, when points p_l and p_r meet at a 45° angle, we get two matched edges, L₁ and R₁.

 

Figure 1. Configuration map of edge matching near matched corners.

In the case of edge matching far from matched corners (e.g., more than four pixels), the images may be somewhat distorted. The propagation strategy is the same as for edge matching near matched corners, but the propagation region is larger (for our purposes, 100 pixels). In extending from corner 1, when an edge point p_l is met in the left image—see Figure 2(a)—we find the correlative point p with the same direction and distance from corner 2 in the right image: see Figure 2(b). Owing to distortion, point p may not lie in an edge. Thus, we restrict a search region (such as 5×5 pixels) centered on p. Within this region, we apply epipolar and correlation constraints to find whether a point corresponding to p_l exists. After confirming the matched point p_r of p_l, we obtain the matched edge R₁ of L.

 

Figure 2. Configuration map of edge matching far from matched corners.

Once we have established all the matched edges, we must determine the point correspondence. To speed up the process, we introduce a new constraint based on edges. Consider a pair of matched edges L and R. We save a pair of matched points in L and R such that L[i]↔R[j]. The main strategy of the edge constraint is simply to use the matched pair to guide other point matching in the two edges, incorporating the continuity constraint. This step enables us to complete the matched points.

In summary, the objective of this research was to develop a quick, accurate, and robust edge-matching approach based on two new corner and edge constraints. Figure 3 shows the matched results. The image measures 768×576 pixels. Using our algorithm, it took roughly 0.9s to detect and match corners, and only about 0.28s to match all the edge points. Finally, we produced a sparse 3D structure, and used a technique of interpolation to generate 3D terrain maps.

Figure 3. The matching result and the 3D reconstruction map of simulated terrain.