Locality Preserving Matching

1 Introduction

This study focuses on the problem of establishing reliable point correspondences between two images of the same scene. Many of the computer vision tasks such as 3D reconstruction, content-based image retrieval, visual homing, object detection and recognition start by assuming that the point correspondences have been successfully recovered [Ma et al., 2013; Bai et al., 2017]. In this paper, we treat the target task as a matching problem between two sets of discrete points, where each point is an image feature extracted by a feature detector and has a local image descriptor, e.g. the scale invariant feature transform (SIFT) [Lowe, 2004].

The matching problem possesses a combinatorial nature, making the matching space of all the possible matches huge. Even without considering the outliers, a simple problem of matching N points to another N points would lead to a total of N! permutations [Wang et al., 2014]. To address this issue, a popular strategy is to construct a group of putative correspondences by imposing a similarity constraint to reduce the set of possible matches. It requires that points can only match points with similar descriptors. Thus the matching task boils down to determine the correctness of each match in the putative set. This paper intends to conquer the mismatch removal from some given putative point correspondences.

During the past few decades, a variety of robust estimators have been developed to address the mismatch removal problem. Nevertheless, it is still a challenging task to customize a practical algorithm when dealing with many realworld problems. Firstly, the use of only local descriptor information will inevitably lead to a number of false matches in the putative set, and this problem is typically even worse if the image pairs suffer from low-quality, occlusion, repeated structures, etc. Secondly, the transformation models between two images are various, making it difficult to design a general algorithm. However, such a general algorithm is frequently required in many computer vision tasks such as deformable object recognition where the transformation models are often unknown in advance. Thirdly, the high computational load, especially of complex non-rigid transformation models, limits its applicability in real-time tasks.

To address the above three challenges, in this paper we propose a simple yet surprisingly effective feature matching approach, which is able to accurately remove the outliers from a putative correspondence set in only a few milliseconds. We observe that for an image pair of the same scene or object, the absolute distance between two feature points may change significantly under viewpoint change or non-rigid deformation, but the spatial neighborhood relationship among feature points representing the topological structures of an image scene are generally well preserved due to physical constraints. Based on this fact, we introduce a mathematical model that constrains the unknown inlier correspondences to have similar local neighborhood structures. This formulation is general, and it can handle both rigid and non-rigid deformations related between two images. We further derive a simple closed-form solution, which has linearithmic time complexity and linear space complexity with respect to the scale of the given putative set. Experiments on various image data demonstrate that the proposed method can produce more accurate matching results with much less computation time (e.g., more than two orders of magnitude faster) compared with other state-of-the-art methods.

Our contribution in this paper is two-fold. On the one hand, we propose a simple yet effective approach for robust feature matching. Unlike most existing methods which require a special parametric or non-parametric model to characterize the global image transformation, our method merely aims to preserve local neighborhood structures of feature points and hence, it is more general. On the other hand, we derive a closed-form solution with linearithmic complexity which can solve a typical matching problem with over 1, 000 putative correspondences in only a fewmilliseconds, therefore, it is beneficial for many real-time applications and can quickly provide a good initialization for more complicated problemspecific matching algorithms. We validate this solution on real-word tasks such as image retrieval and visual homing, and obtain better results than other state-of-the-arts in terms of both accuracy and efficiency.

2 RelatedWork

Numerous mismatch removal methods have been proposed over the last decades, which can be roughly divided into four categories, say statistical regression methods, resampling methods, non-parametric interpolation methods, and graph matching methods.

Statistics literature shows that the methods that minimize the L1 norm are more robust and can resist a larger proportion of outliers compared with quadratic L2 norms [Huber, 1981]. Liu et al. [Liu et al., 2015] proposed a regression method based on adaptive boosting learning for 3D rigid matching. Maier et al. [Maier et al., 2016] introduced a guided matching scheme based on statistical optical flow. The most popular resampling method is RANSAC, which has several variants such as MLESAC [Torr and Zisserman, 2000] and PROSAC [Chum and Matas, 2005]. These methods adopt a hypothesize-and-verify approach and attempt to obtain the smallest possible outlier-free subset to estimate a provided parametric model by resampling. The statistical regression and resampling methods rely on a predefined parametric model, which become less efficient when the underlying image transformation is non-rigid; they also tend to severely degrade if the outlier ratio becomes large [Li and Hu, 2010]. Several non-parametric interpolation methods [Ma et al., 2014; Li and Hu, 2010; Wang et al., 2017] have recently been introduced to address these issues. These methods commonly interpolate a non-parametric function by applying the prior condition, in which the motion field associated with the feature correspondence is slow-and-smooth. However, they typically have cubic complexities and the computational costs are huge for large putative set, which limits their uses in real-time applications such as object tracking, visual odometry, SLAM, etc. Graph matching is another technique to solve the matching problem; several representative studies include spectral matching [Leordeanu and Hebert, 2005], dual decomposition [Torresani et al., 2008], mode-seeking [Wang et al., 2014], and graph shift (GS) [Liu and Yan, 2010]. In addition, Lee et al. [Lee et al., 2015] proposed to use local neighborhoods for feature description to alleviate false matches. Graph matching provides considerable flexibility to the object model and delivers robust matching and recognition. Nevertheless, it suffers from similar drawbacks of its non-polynomial-hard nature.

In addition to the mismatch removal, some efforts on generating better putative correspondences have also been carried. Guo and Cao [Guo and Cao, 2012] proposed a triangle constraint, which can produce better putative correspondences in terms of quantity and accuracy compared with the distance ratio in [Lowe, 2004]. Hu et al. [Hu et al., 2015] proposed the local selection of a suitable descriptor for each feature point instead of employing a global descriptor during putative correspondence construction. A cascade scheme has been suggested to prevent the loss of true matches, which can significantly enhance the correspondence number [Wang et al., 2014; Cho and Lee, 2012].

3 Method

This section describes our method for establishing accurate correspondences between two feature sets extracted respectively from two images of the same or similar scenes. To this end, we first construct a set of putative matches by considering all possible matches between two feature sets and filtering out matches whose feature descriptor vectors are sufficiently different. We then use a geometric constraint to remove the false matches contained in the putative set, which further filters out those matches with different spatial neighborhood structures among feature points. Fortunately, there are several well-designed feature descriptors (e.g., SIFT [Lowe, 2004]) which can efficiently establish putative correspondence between feature sets. Therefore, in the following, we will focus on the mismatch removal problem and introduce a simple yet efficient strategy by preserving local neighborhood structure.

3.1 ProblemFormulation

Suppose we have obtained a set of N putative feature correspondences S = {(xi, yi)}Ni=1 extracted from two given images, where xi and yi are 2D column vectors denoting the spatial positions of feature points (our approach is not limited by the dimension of the input data, which can be directly applied to 3D matching problems). Our goal is to remove the outliers contained in S to establish accurate correspondences.

If the spatial relationship between the image pair is a simple rigid transformation, then the distance between any feature correspondence will be preserved. In other words, denot-

ing I the unknown inlier set, its optimal solution is

with the cost function C defined as:

where d is a certain distance metric such as Euclidean distance, and | · | denotes the cardinality of a set. In this cost function, the first term penalizes any match which does not preserve the distance of a point pair, the second term discourage the outliers, and the parameter λ > 0 controls the tradeoff between these two terms. Ideally, the optimal solution should achieve zero penalty, i.e., the first term of C should be zero.

However, if the image pair undergoes a relatively complex non-rigid transformation, the above distance relationship, in general, will not hold, especially for matches that are far from each other. Fortunately, the local neighborhood structure among feature points may not change freely due to the physical constraints in the small region around a point, which means that the distribution of neighboring point pairs after transformation should be preserved [Zheng and Doermann, 2006]. Therefore, by preserving only local neighborhood structures, the cost function in Eq. (2) becomes:

where Nx denotes the neighborhood of point x. There is no obvious neighborhood definition for a point set. In our evaluation, we adopt a simple strategy that searches the K (K = 4 in default) nearest neighbors for each point in the corresponding feature set under the Euclidean distance.

We associate the putative set S with an N ×1 binary vector p, where pi ∈ {0, 1} denotes the match correctness of the i-th correspondence (xi, yi). Specifically, pi = 1 indicates inlier and pi = 0 points to outlier. Note that the absolute distance of a point pair is not preserved well under non-rigid deformation such as scale changes. To address this issue, we quantize the distance to two levels as:

and the same as d(yi, yj). In this case, the cost function in Eq. (3) is converted to:

With the distance definition in Eq. (4), the objective function in Eq. (5) is translation, rotation, and scale invariant. The problem of removing outliers and establishing accurate feature correspondences could be solved by searching an optimal solution p that minimizes the cost function (5).

3.2 Solution

To optimize the objective function (5), we reorganize its form by merging the terms related to pi and obtain:

where

is a cost that measures if the i-th correspondence (xi, yi) meets the geometric constraint of preserving local neighborhood structure. Clearly, a correct match will bring zero cost or a small cost while a false match will increase the cost largely.

For a given putative set, the neighborhood relationship between the feature points is fixed, and hence all the cost values {ci}Ni=1 can be calculated in advance. That is to say, the only unknown variable in Eq. (6) is pi, and its solution is obvious: any correspondence with a cost smaller than λ will lead to a negative term and decrease the objective function, while any correspondence with a cost larger than λ will result in an positive term and increase the objective function. Therefore, the optimal solution of p that minimizes Eq. (6) is determined by the following simple criterion:

And hence, the optimal inlier set I ∗ is determined by:

From Eq. (8), we see that parameter λ also plays a role of threshold that judges the match correctness of a putative correspondence. Note that the setting of pi can be arbitrary when ci = λ. Besides, the value of ci is always an integer, and hence we do not need to tune λ among non-integer values.

3.3 Neighborhood Construction

The neighborhood Nx of each point x in Eq. (3) is constructed based on the whole feature set which also involves outliers. This strategy in general works well due to the following reasons. On the one hand, for an outlier (xi, yi), its local neighborhood structures cannot be preserved between two images, leading to a large cost ci, and hence it will be easily identified as an outlier. On the other hand, for an inlier (xj, yj), even if its neighborhood Nxj or Nyj contains some outliers, the major components are typically inliers which conform to the geometric constraint, and hence its cost cj will not be large.

To verify how good it works, we collect in total 30 image pairs involving natural images, remote sensing images, medical images, as well as infrared images. The precision and recall are used to evaluate the matching performance, where the precision is defined as the ratio of the identified correct match number and the preserved match number, and the recall is defined as the ratio of the identified correct match number and the correct match number contained in the putative set. The initial inlier percentages of the SIFT matching on the test data are summarized in Fig. 1a, where in average only 68.53% putative correspondences are inliers. Figures 1b and 1c demonstrate the precision and recall curves with respect to different λ. We see that with a proper value of λ (e.g., 6), our method can preserve about 95.26% of the true correspondences, and the precision can also reach up to 90.79%.

Nevertheless, it will be more desirable if the neighborhood Nx can be constructed based on only the inlier set I. In this case, the calculation of the cost cj for an inlier will be more accurate and is not influenced by the outlier, therefore, the margin between inlier and outlier will be distinctly enlarged. This is helpful for accurate classification of the putative correspondences, especially when the putative set S contains a large number of outliers. However, the true inlier set I cannot be known in advance and it is to be solved in our problem. To solve this dilemma, here we seek an approximation I0 of it. As shown in Fig. 1, our method is able to generate a correspondence set which can remove most of the outliers and simultaneously keep most of the inliers just by using S for neighborhood construction. Clearly, this set is a good approximation of the true inlier set, i.e., I0 = argminI C(I; S, λ) with the neighborhood constructed based on the whole set S.

Subsequently, we use I0 to construct neighborhood for each correspondence in S, and solve the optimal I ∗ as:

By using I0 instead of S for neighborhood construction, the average precision-recall pair on the 30 test pairs can be largely increased from (90.79%, 95.26%) to (96.17%, 97.21%). The distributions of the cost ci by using the whole feature set and using I0 to construct neighborhood are reported in Figs. 1d and 1e, respectively. We see that the margin between inlier and outlier has been distinctly enlarged.

In fact, we could use a progressive strategy to construct the neighborhood, i.e., iteratively using the correspondence set generated in the previous iteration for neighborhood construction until convergence, and the average precision-recall pair is then further increased to (96.33%, 98.06%). Note that such progressive strategy can only slightly improve the matching performance, which means that I0 is good enough to approximate the true inlier set for neighborhood construction. Therefore, we just use Eq. (10) to determine the optimal inlier set for simplicity.

Parameter settings. There are two parameters in our method: K and λ. The former determines the number of nearest neighbors for neighborhood construction, while the latter controls the threshold for judging the correctness of a putative correspondence. Clearly, large value of K or small value of λ will increase the precision and simultaneously decrease the recall, and vice versa. In our evaluate, we set the default values as K = 4, and λ = 6.

Since our matching strategy is to preserve local neighborhood structures, we name our method locality preserving matching (LPM). We summarize our LPM in Alg. 1.

3.4 Computational Complexity

To search the K nearest neighbors for each feature point in S, the time complexity is close to O((K + N) logN) by

Algorithm 1: The LPM Algorithm

Input: putative set S = {(xi, yi)}Ni=1 , parameters K, λ Output: inlier set I ∗

• 1 Construct neighborhood {Nxi , Nyi }Ni=1 based on S;
• 2 Calculate cost {ci}Ni=1 using Eq. (7);
• 3 Determine I0 using Eqs. (8) and (9);
• 4 Construct neighborhood {Nxi , Nyi }Ni=1 based on I0;
• 5 Calculate cost {ci}Ni=1 using Eq. (7);
• 6 Determine I ∗ using Eqs. (8), (9) and (10).

using K-D tree [Bentley, 1975]. Thus the time complexity of Lines 1 and 4 in Alg. 1 is about O((K + N) logN). According to Eq. (7), calculating the cost {ci}Ni=1 in Lines 2 and 5 only involves some addition operation, and its time complexity is O(KN). Moreover, determining p and I using Eqs. (8) and (9) in Lines 3 and 6 cost O(N) complexity. Therefore, the total time complexity of our LPM is about O(KN + (K + N) logN). The space complexity of our LPM is O(KN) due to the memory requirements for storing the neighborhoods Nx and Ny. Generally, K ≪ N, thus the time and space complexities of our method can be simply written as O(N logN) and O(N), respectively. That is to say, our LPM has linearithmic time complexity and linear space complexity with respect to the scale of the given putative set. This is significant for large-scale problems or real-time applications.

4 Experimental Results

In order to evaluate the performance of our LPM, we first conduct experiments on feature matching for various real image pairs, and then apply it to two real-world tasks such as visual homing and image retrieval. The open source VLFEAT toolbox [Vedaldi and Fulkerson, 2010] is employed to determine the putative correspondence of SIFT [Lowe, 2004] and to search the K nearest neighbors using K-D tree. The experiments are performed on a desktop with 3.0 GHz Intel Core CPU, 8 GB memory, and C++ code. Besides, all the codes were realized without special optimization such as parallel computing or streaming SIMD extensions (SSE).

4.1 Results on Feature Matching

In this section, we focus on establishing feature correspondences for real images. To this end, we first test the performance of our method on five representative image pairs undergoing different types of image transformations, as shown in Fig. 2. The "Land" pair is an aerial photograph pair involving only linear (e.g., rigid or affine) transformation, which is typically arisen in image stitching. The "Fox" and "Book" pairs undergoes piecewise linear transformation, which is typically arisen in image/vedio retrieval. The "T-shirt" pair involves a deformable object with non-rigid motion, which is typically arisen in medical image registration. The "Church" pair is a wide baseline image pair, which is typically arisen in structure-from-motion. For each group of results, the left image pair schematically shows the matching result, and the right motion field provides the decision correctness of each correspondence in the putative set. The ground-truth is established by manual checking, and we made the benchmark before performing experiments to ensure objectivity. From the results, we see that our LPM can always produce satisfying results and very few putative matches are misjudged.

We also provide quantitative comparison on these five image pairs with four state-of-the-art matching methods such as RANSAC [Fischler and Bolles, 1981], ICF [Li and Hu, 2010], GS [Liu and Yan, 2010], and MR-RPM [Ma et al., 2017]. The performance is characterized by precision and recall, as shown in Table 1. From the results, we see that for rigid matching such as in the Land pair, all methods perform quite well. RANSAC cannot work well when the image transformation does not satisfy a parametric model, such as in the Fox, Book and T-shirt pairs. ICF and MR-RPM use a slow-and-smooth prior, which will probably fail if the motion field involves large depth discontinuity or motion inconsistency, such as in the Fox, Book and Church pairs. GS usually has high precision and low recall due to it cannot automatically estimate the factor for affinity matrix and it is not affineinvariant. In comparison, our LPM does not suffer from all these problems, which demonstrates its generality and its ability to handle various matching problems.

To test the computational efficiency of our LPM, we next conduct experiments on a publicly available feature matching dataset [Mikolajczyk et al., 2005], which contains 40 image pairs either of planar scenes or captured by camera in a fixed position during acquisition. Therefore, these images always obey homography. The ground truth homographies are supplied by the dataset. The average number of putative SIFT correspondences is about 1347.2 on the dataset. The precision, recall and runtime statistics of the five algorithms are reported in Fig. 3. From the results, we see that our LPM does not have obvious advantage in terms of matching accuracy compared with other methods, especially the MR-RPM. This is because the image transformations here are all linear homography, which is relatively simple and easy to handle. However, our LPM is surprisingly effective, which is more than two orders of magnitude faster than state-of-thearts. More specifically, our average runtime is merely 9.14 ms, making it ideal for real-time applications.

4.2 Results on Visual Homing

Visual homing is the ability of an mobile robot to navigate to a goal position using visual information. The robustness of visual homing methods is dominated by the feature matching results, where recent visual homing methods typically use some heuristic methods to remove mismatches. To validate the effectiveness of our LPM on this problem, we test several state-of-the-art visual homing methods, where their feature matching scenarios are replaced with our LPM. These comparison methods include homing in scale-space (HiSS), bearing-only visual servoing (BOVS), scale-only visual servoing (SOVS), scale and bearing visual servoing (SBVS), and simplified scale-based visual servoing (SSVS), where the first comes from [Churchill and Vardy, 2013] and the rest four come from [Liu et al., 2013].

We conduct experiments on the A1originalH and CHall1H which are two scenes from a widely used panoramic image database for visual homing 1 . The two scenes contain 170 and 200 images, respectively, which are omnidirectional and unwrapped images of size 561 × 81 in an indoor environment, plus ground truth for positions where the images are collected. As in [Churchill and Vardy, 2013; Liu et al., 2013], we use total average angular error (TAAE), minimal error (Min), maximal error (Max) and standard variation of error (StdVar) to evaluate the homing performance. For all the metrics, smaller values indicate better results.

1 http://www.ti.uni-bielefeld.de/html/research/avardy/index.html

Runtime/ms

Figure 4: Left: The matching result of a typical image pair from the A1originalH scene. Blue and black lines indicate the preserved and removed putative matches. Right: Runtime statistics of LPM for visual homing over 14, 365 trials.

We schematically show our matching result for a typical image pair on the left of Fig. 4. Clearly, all the inliers and outliers in the putative set are correctly distinguished. To test the efficiency of our LPM for visual homing, we repeat the experiment 14, 365 times on different image pairs from the A1originalH scene and report the runtime statistics on the right of Fig. 4, where the median runtime is merely about 0.335 ms. The homing vector errors of all methods on the two scenes are shown in Tables 2 and 3. We can see that our LPM is able to consistently improve the state-of-the-art visual homing methods, due to that our LPM produces more accurate matching results.

4.3 Results on Image Retrieval

We also test our LPM for near-duplicate image retrieval and compare it with RANSAC, ICF, GS, and MR-RPM on the California-ND dataset [Jinda-Apiraksa et al., 2013]. We select all of the classes that have 10 or more images, and for each class we randomly select 10 images for evaluation which results in 7, 140 image pairs in total. The sizes of the test images are all 1024×768. We run the matching algorithms and utilize the number of preserved matches as the similarity between image pairs, and then return a ranked list for a provided image according to its similarities with every other image in the dataset. The performance is also characterized by precision and recall. We denote the required image number to be retrieved for a provided image as RN. The precision is valid for RN ≤ 10 and the recall is valid for RN ≥ 10, because each class contains 10 images.

The statistic retrieval results of the four methods in the dataset are presented on the left two figures of Fig. 5. Our LPM evidently outperforms all other methods and obtains the best precision and recall, followed by RANSAC and MR-RPM. Specifically, the average retrieved correct image numbers of RANSAC, ICF, GS, MR-RPM and our LPM for RN = 10 are approximately 7.45, 5.18, 7.13, 7.13 and 8.69, respectively. The runtime statistics of our LPM on all the

7, 140 image pairs is provided on the right of Fig. 5, where the median runtime is about 0.579 ms.

We also measure the retrieval performance of the so-called bulls-eye score [Bai et al., 2010], which is defined as the ratio of the total number of correct images among the 20 most similar images to the highest possible number (i.e., 10). The best possible rate is 100%. The bulls-eye scores of RANSAC, ICF, GS, MR-RPM and our LPM are approximately 81.25%, 59.50%, 80.00%, 80.25% and 92.42%, respectively. Our method again evidently showcases the best performance.

5 Discussion and Conclusion

In this paper, we proposed a novel mismatch removal method for robust feature matching. It works based on a general characteristic that the neighborhood structures of feature correspondences between two images of the same scene should be similar. We formulate this idea into a mathematic model and derive a closed-form solution with linearithmic time complexity. The qualitative and quantitative results on feature matching as well as other real-world tasks demonstrate that our method can handle a variety of matching problems. More importantly, it can identify outliers from over 1, 000 putative matches in only a few milliseconds, which is more than two orders of magnitude faster than state-of-the-art methods.

Since our method is very fast, it can be used to provide a quick initialization for more complicated problem-specific matching algorithms. For instance, it can provide a quick initialization for RANSAC to estimate the epipolar geometry between wide baseline image pairs.

Acknowledgments

We are very grateful to Alan L. Yuille for motivating us to consider the approach discussed here. This paper was supported by the National Natural Science Foundation of China under Grant nos. 61503288, 61501413 and 41501505.