A correspondence selection method based on same object and same position constraints

Abstract

Establishing robust correspondences between two images is important for computer version tasks. However, in the real scene incorrect correspondences are inevitable no matter what kind of correspondence matching algorithms are adopted due to some complex factors, such as illumination, occlusion, and so on. To reduce the number of incorrect correspondences, an algorithm with the same object and same position constraints (SOSPC), is proposed to remove wrong correspondences from the given putative correspondences in this paper. The algorithm is based on the fact that in the given image pairs correct correspondences locate at the same position on the same objects. To select the correspondences on the same objects, an object matching method based on the correspondences selected by GMS is proposed. To select the correspondences on the correct positions, an iterative fundamental matrix estimation method based on clustering is presented. The experimental results have validated the effectiveness of the same object and the same position constraints, and the method achieves the state-of-art performance on five datasets.

Introduction

Finding feature correspondences is a fundamental task in the field of computer vision, which has a wide range of applications such as structure-from-motion, ¹ multi-view stereo, ² image retrieval, ³ simultaneous localization and mapping, ⁴ face verification, ⁵ and et al. To acquire accurate correspondences, a popular two-step strategy is used. In the first step, the initial correspondence set is computed by correspondence matching algorithms (e.g. SIFT, ⁶ ORB, ⁷ A-KAZE, ⁸ etc). In the second step, more robust correspondences are determined out from the initial correspondence set by correspondence selection algorithms. By the second step, the ratio of correct correspondences can be raised, which offers more opportunities for the success of the subsequent operations in most cases.

Most correspondence matching algorithms establish correspondence relationship between two images by extracting keypoints and local image descriptors.^6,7,9,10 Each keypoint has a descriptor to describe its texture, illumination and other features, and keypoints with most similar descriptors are matched. However, many correspondence matching algorithms usually have such problems: (1) due to complexity of real scenes, they are difficult to be adaptable to different photograph conditions in images simultaneously, such as changing viewpoints, repeated structures, different illumination, occlusion, similar textures and so on; (2) many matching algorithms only consider local descriptor, and some global structure information is ignored, which results in many correspondences having similar local structure but belonging to different objects.

Because of the above reasons, in the first step it is inevitable that correspondence matching results will suffer from a lot of incorrect matches as shown in Figure 1(a) and (b), no matter what kind of correspondence matching algorithm is applied. Thus in the second step it is necessary to remove the incorrect matches by the correspondence selection algorithm. Correspondence selection algorithms may select robust correspondences based on different principles. For example, some methods (e.g. RANSAC ¹¹ and USAC ¹² select robust correspondences by estimating a transformation model from one image to another image, and some other methods (e.g. GMS ¹³ and VFC ¹⁴ select correspondences based on the consistency of local geometric structures. However, these methods still have their own drawbacks: in the real world some transformation relationships between image pairs are complicated, for the methods that estimate the transformation model, it is hard to pick all correct correspondences out only by one kind of transformation model, for example, in Figure 1(c) correct correspondences on some objects are not selected using RANSAC method. For the methods based on local geometric structures, they often select the correspondences that match right regions, but sometimes they may not match the position of correspondences accurately in pixel level. Therefore, correspondence selection algorithm still deserves further study.

Figure 1.

(a) The initial correspondences obtained by A-KZKE algorithm, ⁸ (b) the initial correspondences obtained by ORB algorithm, ⁷ and (c) the ORB correspondences selected by RANSAC algorithm. ¹¹

In this paper we focus on the second step and propose a method named SOSPC to select robust correspondences from the initial correspondence set. Based on the fact that correct correspondences should be on the same object and at the same position of the same object, we introduce the two constraints into the selection mechanism of correct correspondences in our method. For the same object constraint, the same objects in different images can be matched well by our designed method based on GMS, ¹³ then correspondences that match objects wrongly will be removed. For the same position constraint, the fundamental matrix that corresponds to each object is calculated by an iterative method, and according to the obtained fundamental matrix these correspondences on wrong positions are removed.

In summary, the contributions of this paper are as follows:

• The constraint that correct correspondences are on the same objects is introduced into our algorithm. To select the correspondences on the same objects, an object matching method using the correspondences selected by GMS ¹³ is proposed.

• The constraint that correct correspondences locate at the same position on the same objects are integrated into the correspondence selection algorithm. An iterative fundamental matrix estimation method based on clustering is presented to improve the precision of the extracted fundamental matrix.

• Our method has achieved the state-of-art performance comparing with other correspondence selection algorithms on several challenging datasets.

Related works

Correspondence matching algorithms

The most popular strategy to establish the relationships among keypoints in different images are divided into three stages: extracting keypoints from images, computing descriptors of keypoints, and matching the keypoints in image pairs based on the descriptors. The most famous correspondence matching approaches are SIFT ⁶ and SURF. ⁹ But, because both of them use Gaussian scale space, some details and noises are smoothed, which affects the localization accuracy and distinctiveness. To solve this problem, KAZE method ¹⁵ is proposed, which uses nonlinear diffusion filtering to increase the distinctiveness. For decreasing the computational cost and taking the benefits of nonlinear diffusion filtering, some people design A-KAZE ⁸ method based on the Fast Explicit Diffusion framework. In some scenes, the computational resources are limited, ORB ⁷ and BRISK ¹⁶ are proposed, which both combine modifications of FAST corner detector ¹⁷ and binary descriptors based on BRIEF. ¹⁸

Correspondence selection algorithms

In the last decades, many correspondence selection algorithms have been presented. Generally speaking, the correspondence selection methods can be divided into parametric methods and non-parametric methods.

Parametric methods select robust correspondences mainly by estimating global transformation model. ACC, ¹⁹ as a kind of parametric method, uses Hessian affine detector, which is invariant to affine transformations, to estimate the local homography matrix as constraints. The most well-known correspondence selection algorithm is RANSAC, ¹¹ which randomly samples some correspondences and estimates a plane homography matrix or a fundamental matrix based on the maximum number of inliers. According to RANSAC, some variants are developed such as MLEESAC, ²⁰ PROSAC, ²¹ LO-RANSAC, ²² and USAC, ¹² which also select robust correspondences by estimating a global homography or essential matrix. But such methods have some drawbacks: (1) the accuracy of estimated global transformation will be affected especially when many incorrect correspondences occur; (2) they often rely on a predefined parametric model, which is not suitable for the non-rigid image transformation.

For non-parametric methods, their principles may be different. A popular design strategy is based on the consistency of local geometric structures or appearance (feature similarity). Considering that the correct feature correspondences on the same object have coherent transformations, CoSeg-HV ²³ integrates image co-segmentation into feature matching and applies the Hough voting and its inverted variant are applied to establish correspondences. LPM ²⁴ removes the false matches in the initial correspondence set according to spatial neighborhood structures. The authors formulate the spatial structure constraint into a mathematical model, and derive a closed-form solution with linearithmic time. Based on the solution the true matches can be selected. VFC ¹⁴ assumes that noise around correct matches and wrong matches has different distribution. Then it estimates the probability of the correct matches by the maximum likelihood estimation. In Lee et al., ²⁵ propose a robust correspondence selection method based on local neighborhood. In this method the feature of each correspondence consists of a local graph combined by features of neighboring correspondences, and by comparing the similarity of the local graph the algorithm can select robust correspondences. GMS ¹³ incorporates smoothness constraints into matching, and it proves that the number of correspondences around true matches and false matches has different distributions, which establishes a link between correspondence numbers and match quality. Thus the correct matches can be determined by the correspondence numbers around a correspondence. Because such methods distinguish true or false correspondences mainly by the local structure and impose no position constraint in the pixel level, sometimes the accuracy of such methods may be lower.

Method

Problem definition

Given two images $I_A$ and $I_B$ , $C_{\mathrm{initial}}=\{c_1,c_2,\dots ,c_i,\dots ,c_M\}$ is the set of initial correspondences obtained by the correspondence matching algorithm, where $c_i=\{p_{\mathrm{ai}},p_{\mathrm{bi}}\}$ , $p_{\mathrm{ai}}$ and $p_{\mathrm{bi}}$ are keypoint locations in $I_A$ and $I_B$ , respectively. $C_{\mathrm{selected}}$ is a subset of $C_{\mathrm{initial}}$ , which is composed by elements selected from $C_{\mathrm{initial}}$ by the correspondence selection algorithm. Our goal is to select robust correspondences from $C_{\mathrm{initial}}$ and put them into $C_{\mathrm{selected}}$ as far as possible. In our algorithm, the selection of robust correspondences is based on the same object constraint and the same position constraint.

The same object constraint

The same object constraint means that the correct correspondences should locate on the same objects in image pairs, so different objects should be distinguished and matched in image pairs firstly, then correspondences that correspond to different objects should be removed.

To distinguish different objects in an image, the image is divided into several colorful regions by segmentation algorithm, ²⁶ as shown in Figure 2. The region set that consists of these regions in $I_A$ is denoted as $R{e}_A=\{R{e}_{a1},\dots ,R{e}_{\mathrm{ai}},\dots ,R{e}_{\mathrm{aU}}\}$ , and the region set in $I_B$ is denoted as $R{e}_B=\{R{e}_{b1},\dots ,R{e}_{\mathrm{bi}},\dots ,R{e}_{\mathrm{bV}}\}$ , where $U$ and $V$ denote the number of divided regions in $I_A$ and $I_B$ , respectively. Each region with a kind of color is regarded as an object, although they may be not a real object in the real scene.

Figure 2.

(a) The divided regions in $I_A$ and (b) the divided regions in $I_B$ . The arrow from $R{e}_{a1}$ to $R{e}_{b1}$ represents that the corresponding region of $R{e}_{a1}$ in $I_B$ is $R{e}_{b1}$ .

The same object constraint can be defined that: when $R{e}_{\mathrm{ai}}$ and $R{e}_{\mathrm{bj}}$ correspond to the same object in image pairs, if correspondence $c_k$ satisfies the same object constraint and $p_{\mathrm{ak}}$ locates on $R{e}_{\mathrm{ai}}$ , then $p_{\mathrm{bk}}$ should locate on $R{e}_{\mathrm{bj}}$ .

Based on the definition, the relationship of the same object in the two images should be established firstly. An intuitive method is to use existing initial correspondences to match the objects in image pairs. But, in fact, matching objects correctly may be difficult by the initial correspondences, because many initial correspondences are not reliable enough. Using initial correspondences to match regions will cause many incorrect object matching, which will result in the reduction of the obtained correct correspondences.

In this section, we propose an object matching method that utilizes the correspondences selected by GMS method. ¹³ GMS uses supported correspondences of a correspondence to determine whether the correspondence is robust. Let $\xi (p)$ denote the neighbor of point $p$ , the neighbor correspondence set of $c_i$ is $\{c_j|p_{\mathrm{aj}}\in \xi (p_{\mathrm{ai}})\}$ , the supported correspondence set of $c_i$ can be denoted by $\{c_j|p_{\mathrm{aj}}\in \xi (p_{\mathrm{ai}}),p_{\mathrm{bj}}\in \xi (p_{\mathrm{bi}})\}$ . According to the smooth motion assumption, it is derived that the supported correspondence number of $c_i$ follows binomial distribution as shown in Figure 3. When $c_i$ is correct, the number of elements in supported correspondence set follows the binomial distribution denoted by the blue curve, and when $c_i$ is wrong, the number of elements in supported correspondence set follows the binomial distribution denoted by the red curve. In Figure 3, the threshold is used to distinguish robust correspondences, which is related to the number of elements in neighbor correspondence set of $c_i$ .

Figure 3.

The distributions of correspondence number. ¹³

Although by GMS algorithm some robust correspondences can be obtained, due to its limitation, many selected correspondences usually correspond to the same regions between images rather than the accurate position in pixel level. Fortunately this characteristics is suitable for object matching.

Another problem that needs to be solved is that due to the limitation of image segmentation algorithm, a region with a certain color may not be a real object, which causes many correct correspondences to be lost. For example, in Figure 2, due to the result of image segmentation, the real object that consists of $R{e}_{a1}$ , $R{e}_{a2}$ , and $R{e}_{a3}$ is the same as the object that consists of $R{e}_{b1}$ and $R{e}_{b2}$ . In this case, if only $c_i$ that $p_{\mathrm{ai}}$ locates in $R{e}_{a1}$ and $p_{\mathrm{bi}}$ locates in $R{e}_{b1}$ are selected, $c_j$ that $p_{\mathrm{aj}}$ locates in $R{e}_{a1}$ and $p_{\mathrm{bj}}$ locates in $R{e}_{b2}$ will be removed. In order to obtain as far as many correct correspondences, such one-to-one region mapping model cannot be adopted.

For a region $R{e}_{\mathrm{ai}}$ , $c_k$ that $p_{\mathrm{ak}}$ locates in $R{e}_{\mathrm{ai}}$ is selected as a voter to determine its corresponding region in $I_B$ . If $p_{\mathrm{bk}}$ locates in $R{e}_{\mathrm{bj}}$ , $c_k$ votes $R{e}_{\mathrm{bj}}$ as the corresponding region of $R{e}_{\mathrm{ai}}$ , and the number of votes that $R{e}_{\mathrm{bj}}$ receives to determine the corresponding region of $R{e}_{\mathrm{ai}}$ is denoted as $|{\mathrm{Re}}_{\mathrm{bj}}^{\mathrm{ai}}|$ . For a region $R{e}_{\mathrm{bi}}$ , $c_k$ that $p_{\mathrm{bk}}$ locates in $R{e}_{\mathrm{bi}}$ is selected as a voter to determine its corresponding region in $I_A$ . If $p_{\mathrm{ak}}$ locates in $R{e}_{\mathrm{aj}}$ , $c_k$ votes $R{e}_{\mathrm{aj}}$ as the corresponding region of $R{e}_{\mathrm{bi}}$ , and the number of votes that $R{e}_{\mathrm{aj}}$ receives to determine the corresponding region of $R{e}_{\mathrm{bi}}$ is denoted as $|{\mathrm{Re}}_{\mathrm{aj}}^{\mathrm{bi}}|$ . The corresponding region of $R{e}_{\mathrm{ai}}$ in $I_B$ is represented by ${\mathrm{Re}}_{\mathrm{bj}}^{\mathrm{ai}*}$ , and the corresponding region of $R{e}_{\mathrm{bi}}$ in $I_A$ is represented by ${\mathrm{Re}}_{\mathrm{aj}}^{\mathrm{bi}*}$ . The two corresponding regions are determined by equations (1) and (2), respectively. By this method, the corresponding region of each region in other image is determined.

$${\mathrm{Re}}_{\mathrm{bj}}^{\mathrm{ai}*}=\arg max\{|{\mathrm{Re}}_{b1}^{\mathrm{ai}}|,\dots ,|{\mathrm{Re}}_{\mathrm{bk}}^{\mathrm{ai}}|,\dots ,|{\mathrm{Re}}_{\mathrm{bV}}^{\mathrm{ai}}|\}$$

(1)

$${\mathrm{Re}}_{\mathrm{aj}}^{\mathrm{bi}*}=\arg max\{|{\mathrm{Re}}_{a1}^{\mathrm{bi}}|,\dots ,|{\mathrm{Re}}_{\mathrm{ak}}^{\mathrm{bi}}|,\dots ,|{\mathrm{Re}}_{\mathrm{aU}}^{\mathrm{bi}}|\}$$

(2)

For correspondence $c_k$ whose $p_{\mathrm{ak}}$ is in $R{e}_{\mathrm{ai}}$ , whether the correspondence satisfies the same object constraint is determined by equation (3). For correspondence $c_k$ whose $p_{\mathrm{bk}}$ is in $R{e}_{\mathrm{bi}}$ , whether the correspondence satisfies the same object constraint is determined by equation (4). Thus a correspondence can be selected as a true match not only by equation (3) but also by equation (4), which alleviates the problem that many correct correspondences are ignored due to the performance of segmentation algorithm.

$$f_1(c_k)=\{\begin{array}{c}\mathrm{true}{p}_{\mathrm{ak}}\in R{e}_{\mathrm{ai}},p_{\mathrm{bk}}\in {\mathrm{Re}}_{\mathrm{bj}}^{\mathrm{ai}*}\hfill \\ \multicolumn{1}{c}{\mathrm{false}{p}_{\mathrm{ak}}\in R{e}_{\mathrm{ai}},p_{\mathrm{bk}}\notin {\mathrm{Re}}_{\mathrm{bj}}^{\mathrm{ai}*}}\end{array}$$

(3)

$$f_2(c_k)=\{\begin{array}{cc}\mathrm{true}\hfill & p_{\mathrm{bk}}\in R{e}_{\mathrm{bi}},p_{\mathrm{ak}}\in {\mathrm{Re}}_{\mathrm{aj}}^{\mathrm{bi}*}\hfill \\ \multicolumn{1}{c}{\mathrm{false}}& p_{\mathrm{bk}}\in R{e}_{\mathrm{bi}},p_{\mathrm{ak}}\notin {\mathrm{Re}}_{\mathrm{aj}}^{\mathrm{bi}*}\hfill \end{array}$$

(4)

The true correspondence $c_k$ where its $p_{\mathrm{ak}}$ is in $R{e}_{\mathrm{ai}}$ is put in set $S_{\mathrm{ai}}^0$ . The true correspondence $c_k$ where its $p_{\mathrm{bk}}$ is in $R{e}_{\mathrm{bj}}$ is put in set $S_{\mathrm{bj}}^0$ . All the correspondences that satisfy equations (3) or (4) form the set $S^0=\{S_{a1}^0,\dots ,S_{\mathrm{ai}}^0,\dots ,S_{\mathrm{aU}}^0,S_{b1}^0,\dots ,S_{\mathrm{bj}}^0,\dots ,S_{\mathrm{bV}}^0\}$ .

The same position on the same object constraint

To describe the position constraint in pixel level, the fundamental matrix tool is used in our algorithm. From Faugeras, ²⁷ for a correspondence $c_i$ , it can be obtained that

$$p_{\mathrm{ai}}^{T}F{p}_{\mathrm{bi}}=p_{\mathrm{ai}}^T{K_1}^{-T}{R}_{c_2}^{c_1}S{K_2}^{-1}{p}_{\mathrm{bi}}=0$$

(5)

where $p_{\mathrm{ai}}=(u_1,v_1,1)$ and $p_{\mathrm{bi}}=(u_2,v_2,1)$ are the homogeneous image coordinates in $I_A$ and $I_B$ , respectively. $F$ is the fundamental matrix, $C_1$ is the camera that captures $I_A$ , and $C_2$ is the camera that captures $I_B$ . $K_1$ and $K_2$ are the internal parameters of $C_1$ and $C_2$ respectively, $R_{c_2}^{c_1}$ denotes the rotation matrix from $C_2$ coordinate to $C_1$ coordinate, and $S$ is a matrix that only has relationship with translation vector $t_{c_2}^{c_1}$ , which is the coordinate of optical center of $C_2$ in $C_1$ coordinate system. From equation (5), it can be known that if the internal parameters of $C_1$ and $C_2$ are the same, $F$ is only related to $R_{c_2}^{c_1}$ and $t_{c_2}^{c_1}$ .

Many accurate algorithms, for example, RANSAC and its variants, use a fundamental matrix to describe the position constraint in pixel level. However, if the relative positions of different objects are changed in image pairs, such methods only select the correspondences of one object. Because when the relative position of different objects are changed, according to Theorem 1 it can be known that the these objects correspond to different fundamental matrix. Under the guidance of Theorem 1 and the goal to describe the position constraint in pixel level, the designed algorithm needs to obtain the fundamental matrix of each object.

• Theorem 1. Each object corresponds to a fundamental matrix. If the relative positions of these objects are unchanged in $I_A$ and $I_B$ , these objects correspond to the same fundamental matrix; otherwise, they correspond to different fundamental matrix.

Proof: As shown in Figure 4, $O_a$ and $O_b$ are two objects. $O_{a1}$ denotes $O_a$ captured by $C_1$ , and $O_{a2}$ denotes $O_a$ captured by $C_2$ . The coordinate system of $O_a$ when $C_1$ captures $I_A$ is denoted by $a_1$ , and the coordinate system of $O_a$ when $C_2$ captures $I_B$ is denoted by $a_2$ . $R_{b_1}^{a_1}$ denotes the rotation matrix from the coordinate system of $O_{b_1}$ to the coordinate system of $O_{a_1}$ , and $R_{b_2}^{a_2}$ denotes the rotation matrix from the coordinate system of $O_{b2}$ to the coordinate system of $O_{a2}$ .

Figure 4.

The diagram of relative position of objects in image pairs: (a) the diagram when the relative position of objects are unchanged in image pairs, (b) the diagram when the relative position of objects are changed in image pairs, (c) assuming that the coordinate system of $O_{a1}$ is static, Figure 4(b) can be converted into this situation, and (d) assuming that the coordinate system of $O_{b1}$ is static, Figure 4(b) can be converted into this situation.

Referring to the coordinate system of $O_a$ , the rotation matrix $R_{c_2}^{c_1}$ from $C_2$ coordinate system to $C_1$ coordinate system is represented by ${}^a{R}_{c_2}^{c_1}$ , which is obtained by equation (6). The translation vector $t_{c_2}^{c_1}$ is represented by ${}^a{t}_{c_2}^{c_1}$ , which is calculated by equation (7).

$${}^a{R}_{c_2}^{c_1}=R_{a_1}^{c_1}{R}_{c_2}^{a_2}$$

(6)

$${}^a{t}_{c_2}^{c_1}{=}^{c_1}{p}_{c_2}=R_{a_1}^{c_1}{p}_{c_2}^{a_2}$$

(7)

where $p_{c_2}^{a_2}$ is the coordinate of the optical center of $C_2$ in the coordinate system of $a_2$ .

Referring to the coordinate of $O_b$ , the rotation matrix from $C_2$ coordinate system to $C_1$ coordinate system is denoted by ${}^b{R}_{c_2}^{c_1}$ , which is obtained by (8). The translation vector ${}^b{t}_{c_2}^{c_1}$ is calculated by equation (9).

$$\begin{array}{c}{}^b{R}_{c_2}^{c_1}=R_{b_1}^{c_1}{R}_{c_2}^{b_2}=R_{b_1}^{c_1}{R}_{a_2}^{b_2}{R}_{b_2}^{a_2}{R}_{c_2}^{b_2}\hfill \end{array}$$

(8)

$${}^b{t}_{c_2}^{c_1}=R{}_{b_1}^{b_2}{p}_{c_2}=R_{a_1}^{c_1}{R}_{b_1}^{a_1}{R}_{a_2}^{b_2}{p}_{c_2}^{a_2}$$

(9)

• When the relative position between $O_a$ and $O_b$ is unchanged in images $I_A$ and $I_B$ :

The condition is equivalent to that $R_{b_1}^{a_1}=R_{b_2}^{a_2}$ , $R_{a_1}^{b_1}=R_{a_2}^{b_2}$ . Equations (8) and (9) can be rewritten as follows:

$${}^b{R}_{c_2}^{c_1}=R_{b_1}^{c_1}{R}_{a_2}^{b_2}{R}_{b_2}^{a_2}{R}_{c_2}^{b_2}=R_{b_1}^{c_1}{R}_{a_1}^{b_1}{R}_{b_2}^{a_2}{R}_{c_2}^{b_2}=R_{a_1}^{c_1}{R}_{c_2}^{a_2}{=}^a{R}_{c_2}^{c_1}$$

(10)

$${}^b{t}_{c_2}^{c_1}=R_{a_1}^{c_1}{R}_{b_1}^{a_1}{R}_{a_2}^{b_2}{p}_{c_2}^{a_2}=R_{a_1}^{c_1}{R}_{b_2}^{a_2}{R}_{a_2}^{b_2}{p}_{c_2}^{a_2}=R_{a_1}^{c_1}{p}_{c_2}^{a_2}{=}^a{t}_{c_2}^{c_1}$$

(11)

From equations (10) and (11), it can be seen that ${}^a{R}_{c_2}^{c_1}$ and ${}^b{R}_{c_2}^{c_1}$ are the same, and ${}^a{t}_{c_2}^{c_1}$ and ${}^b{t}_{c_2}^{c_1}$ are also the same, thus $O_a$ and $O_b$ correspond to the same fundamental matrix in image pairs.

• (b) When the relative position between $O_a$ and $O_b$ is changed in images $I_A$ and $I_B$ :

The condition is equivalent to that $R_{b_1}^{a_1}\ne R_{b_2}^{a_2}$ , $R_{a_1}^{b_1}\ne R_{a_2}^{b_2}$ . Equations (8) and (9) can be rewritten as follows:

$${}^b{R}_{c_2}^{c_1}=R_{b_1}^{c_1}{R}_{a_2}^{b_2}{R}_{b_2}^{a_2}{R}_{c_2}^{b_2}\ne R_{b_1}^{c_1}{R}_{a_1}^{b_1}{R}_{b_2}^{a_2}{R}_{c_2}^{b_2}=R_{a_1}^{c_1}{R}_{c_2}^{a_2}{=}^a{R}_{c_2}^{c_1}$$

(12)

$${}^b{t}_{c_2}^{c_1}=R_{a_1}^{c_1}{R}_{b_1}^{a_1}{R}_{a_2}^{b_2}{p}_{c_2}^{a_2}\ne R_{a_1}^{c_1}{R}_{b_2}^{a_2}{R}_{a_2}^{b_2}{p}_{c_2}^{a_2}=R_{a_1}^{c_1}{p}_{c_2}^{a_2}{=}^a{t}_{c_2}^{c_1}$$

(13)

From equations (12) and (13), it can be seen that ${}^a{R}_{c_2}^{c_1}$ and ${}^b{R}_{c_2}^{c_1}$ are different, and ${}^a{t}_{c_2}^{c_1}$ and ${}^b{t}_{c_2}^{c_1}$ are also different, thus $O_a$ and $O_b$ correspond to the different fundamental matrix in image pairs.

Epipolar distance

As shown in Figure 5, according to the properties of fundamental matrix, it can be known that the epipolar lines in $I_A$ and $I_B$ are $l_1$ and $l_2$ , respectively.

$$l_1:F{p}_{\mathrm{bi}}=(m_1,n_1,h_1{)}^T$$

(14)

$$l_2:F{p}_{\mathrm{ai}}=(m_2,n_2,h_2{)}^T$$

(15)

where $m$ , $n$ , and $h$ are the parameters to denote the straight line $\mathrm{mu}+\mathrm{nv}+h=0$ in images. The distance $d_1$ from $p_{\mathrm{ai}}$ to $l_1$ and the distance $d_2$ from $p_{\mathrm{bi}}$ to $l_2$ are:

$$d_1=\frac{m_1{u}_1+n_1{v}_1+h_1}{\sqrt{m_1^2+n_1^2}}$$

(16)

$$d_2=\frac{m_2{u}_2+n_2{v}_2+h_2}{\sqrt{m_2^2+n_2^2}}$$

(17)

Figure 5.

The illustration of epipolar distance. $O_1$ is the optical center of the camera that takes image $I_A$ , and $O_2$ is the optical center of the camera that takes image $I_B$ . $d_1$ and $d_2$ are both epipolar distances.

In equations (16) and (17), $d_1$ and $d_2$ are both epipolar distances, and the minimum epipolar distance of $c_i$ using $F$ is defined as equation (18).

$$d(c_i,F)=max(d_1,d_2)$$

(18)

An iterative fundamental matrix estimation method based on clustering (IFMEM)

To find the fundamental matrix of each object, the correspondence in $S^0$ is applied. The correspondence set $S_{\mathrm{ai}}^0$ in $S^0$ consists of correspondences on $R{e}_{\mathrm{ai}}$ . According to $S_{\mathrm{ai}}^0$ , a seed fundamental matrix $F_{\mathrm{ai}}^0$ that corresponds to $R{e}_{\mathrm{ai}}$ is calculated by RANSAC. ¹¹ Besides, other seed fundamental matrix that corresponds to $R{e}_{\mathrm{aj}}$ and $R{e}_{\mathrm{bk}}$ can also be calculated, and they form a seed fundamental matrix set $F^0=\{F_{a1}^0,\dots ,F_{\mathrm{ai}}^0,\dots ,F_{\mathrm{aU}}^0,F_{b1}^0,\dots ,F_{\mathrm{bj}}^0,\dots ,F_{\mathrm{bV}}^0\}$ .

However, these seed fundamental matrix cannot be directly used to select correspondences at the same position on the same object, because under the limitation of accuracy of image segmentation and object matching, some correct correspondences may be removed while some wrong correspondences still remain. This disadvantage makes not all seed fundamental matrix so reliable, which causes some incorrect correspondences be selected and many correct correspondences be ignored.

To improve the precision and increase the number of selected correct correspondences, IFMEM is proposed. If the epipolar distance of the correspondence $c_i$ calculated by fundamental matrix $F_{\mathrm{aj}}^0$ is less than ${\tau }_0$ , which means that $c_i$ is on the object that can be described roughly by $F_{\mathrm{aj}}^0$ , $c_i$ is put into set $S_{\mathrm{aj}}^1$ . The sets like $S_{\mathrm{aj}}^1$ form a new set $S^1=\{S_{a1}^1,\dots ,S_{\mathrm{ai}}^1,\dots ,S_{\mathrm{aU}}^1,S_{b1}^1,\dots ,S_{\mathrm{bj}}^1,\dots ,S_{\mathrm{bV}}^1\}$ . Based on $S^1$ , the new fundamental matrix set $F^1=\{F_{a1}^1,\dots ,F_{\mathrm{ai}}^1,\dots ,F_{\mathrm{aU}}^1,F_{b1}^1,\dots ,F_{\mathrm{bj}}^1,\dots ,F_{\mathrm{bV}}^1\}$ can be obtained.

After $l$ times iterations, the final fundamental matrix $F^l$ can be obtained. During the process of iteration, ${\tau }_l$ becomes smaller by equation (19), $\alpha$ is a factor between 0 and 1.

$$\begin{array}{c}{\tau }_l=\alpha {\tau }_{l-1}\hfill \end{array}$$

(19)

While $\tau$ becomes smaller more precise points are preserved and the estimated fundamental matrix can be more accurate. Finally $F^l$ is used to select the correspondences in $C_{\mathrm{initial}}$ , and correspondences that satisfy the epipolar distance <3.0 are put into $C_{\mathrm{selected}}$ .

The workflow of the whole algorithm is shown as Figure 6, and it can be also written as Algorithm 1. The number of initial feature matches is denoted as $N$ , the number of objects segmented in an image is $M$ , the maximum iteration times of the method to calculate the fundamental matrix is $L$ , the time complexity of the image segmentation algorithm is $O_{\mathrm{seg}}$ , the time complexity of the method to calculate a fundamental matrix is $O_{\mathrm{ransac}}$ . The time complexity of the object matching algorithm based on GMS is $O(M^{2}N)$ , the time complexity of the method to calculate fundamental matrix of each matrix is $O(\mathrm{LM}{O}_{\mathrm{ransac}})$ , so the time complexity of the whole algorithm is $O_{\mathrm{seg}}+O(M^{2}N+\mathrm{LM}{O}_{\mathrm{ransac}})$ . $O_{\mathrm{seg}}$ is related to the adopted image segmentation algorithm, and the time complexity of different image segmentation algorithms varies greatly. The time complexity of $O_{\mathrm{ransac}}$ is related to $N$ , and as the accuracy increases, the number of iterations will increase. In the actual calculation process, an upper limit on the number of iterations can be set, so the final time complexity of the whole algorithm can be denoted as $O_{\mathrm{seg}}+O(M^{2}N)$ .

Figure 6.

The workflow of SOSPC with the same object and same position constraints.

Algorithm 1 SOSPC Algorithm 1

Input: The initial correspondences $C_{\mathrm{initial}}$ . Output: The correspondences $C_{\mathrm{selected}}$ selected by our algorithm. 1: By segment algorithm, 26 images $I_A$ and $I_B$ are divided into regions $R{e}_A$ and $R{e}_B$ , respectively. 2: By GMS method the reliable correspondences are selected and they are used to establish the mapping from $R{e}_A$ to $R{e}_B$ and the mapping from $R{e}_B$ to $R{e}_A$ [equations (1) and (2)]. The correspondences that satisfy the same object constraint are selected, and they form the set $S^0$ [equations (3) and (4)]. 3: Based on $S^0$ the seed fundamental matrix set $F^0$ is calculated by RANSAC. 4: Initialize ${\tau }_0$ . 5: for $l=0$ ; $l<=L$ ; $l++$ do 6:      for $c_i$ in $C_{\mathrm{initial}}$ do 7:          for $F_{\mathrm{aj}}^l$ (or $F_{\mathrm{bj}}^l$ ) in $F^l$ do 8:              if $\mathrm{d}(c_i,F_{\mathrm{aj}}^l(\mathrm{or}{F}_{\mathrm{bj}}^l))<{\tau }_l$ then 9:                   $c_i$ is added into $S_{\mathrm{aj}}^{l+1}$ (or $S_{\mathrm{bj}}^{l+1}$ ) 10:            end if 11:        end for 12:     end for 13:     Based on $S^{l+1}$ , the fundamental matrix set $F^{l+1}$ is calculated by RANSAC. 14:      ${\tau }_{l+1}=\alpha {\tau }_l$ 15: end for 16: for $c_i$ in $C_{\mathrm{initial}}$ do 17:    for $F_{\mathrm{aj}}^l$ (or $F_{\mathrm{bj}}^l$ ) in $F^l$ do 18:        if $\mathrm{d}(c_i,F_{\mathrm{aj}}^l(\mathrm{or}{F}_{\mathrm{bj}}^l))<3.0$ then 19:               $c_i$ is added into $C_{\mathrm{selected}}$ . 20:            end if 21:       end for 22: end for

Experiments

In this section, the performance evaluation and analysis of the proposed method are reported. The open source library OPENCV is employed to detect the initial correspondences by ORB algorithm.

Datasets

Five datasets are employed in our experiments: Person,Gerrard, Graham, South, and MultiObjects. The first four datasets all contain 400 pairs of images, which are obtained from, ¹ and their ground-truth camera parameters are provided. Based on the camera parameters, the fundamental matrix between image pairs are calculated, then the corresponding epipolar distance for each correspondence is calculated. The correspondence with epipolar distances <3.0 is regarded as the ground-truth. In the four datasets there are many challenges to select robust correspondences. Graham, Gerrard, and South are facing several problems, such as changed viewpoint, repeated structure, different illumination. In Person, there are a lot of rotation scenes between image pairs. In the four datasets, there are many similar textures in images, which produce a lot of incorrect correspondences. MultiObjects is a self-made dataset, which contains 45 pairs of images. There are some objects in each image pairs, some objects may be covered by other objects, and the relative positions among these objects are usually changed in image pairs. The fundamental matrix that corresponds each object is provided. The correspondence with epipolar distances <3.0 is regarded as the ground-truth.

Performacne evaluation

In the following, we refer to paper^13,24 to evaluate our algorithms on five datasets by the precision, recall, and F-measure. They are defined as follows:

$$\mathrm{Precision}=\frac{\mathrm{TP}}{\mathrm{TP}+\mathrm{FP}}$$

(20)

$$\mathrm{Recall}=\frac{\mathrm{TP}}{\mathrm{TP}+\mathrm{FN}}$$

(21)

$$F_{\mathrm{measure}}=\frac{2*\mathrm{Precision}*\mathrm{Recall}}{\mathrm{Precision}+\mathrm{Recall}}$$

(22)

where $\mathrm{TP}$ and $\mathrm{FP}$ is the number of correct and incorrect correspondences selected by a specific algorithm, respectively. $\mathrm{FN}$ is the number of correct correspondences in the initial correspondences that are not selected by the algorithm.

Verification experiments

In this subsection, the first experiment is used to prove Theorem 1. From Theorem 1, it can be known that each object corresponds to a fundamental matrix. Figure 7(a) is the initial correspondences obtained by ORB. The correct correspondences on $O_1$ and $O_2$ are selected manually to calculate the fundamental matrix $F_{o1}$ and $F_{o2}$ , respectively. Figure 7(b) and (c) are the results of correspondence selection based on $F_{o1}$ and $F_{o2}$ , respectively. From Figure 5, it can be seen that $F_{o1}$ and $F_{o2}$ can select the correspondences on $O_1$ and $O_2$ , respectively. The experiment result is in accordance with the expectation of Theorem 1.

Figure 7.

The experiments to prove that each object corresponds to a fundamental matrix: (a) the initial correspondences, (b) the correspondences selected by $F_{o1}$ , and (c) the correspondences selected by $F_{o2}$ .

To justify the two proposed constrains’ effects, we have also conducted two comparison experiments. Our contrast tests are both tested on the subset of the five datasets. The first comparison experiment is used to prove the effect of the same object constraint, and the results are shown in Table 1. From this table, it can be seen that the precision of GMS is higher than the initial correspondences, which means that the GMS methods can select more robust correspondences from the initial correspondences. Then the initial correspondences are used to match the same objects, and based on the object matching result the precision and F-measure of the selected correspondences are improved comparing with the initial correspondences, which illustrates that the same object constraint has a positive effect on the correspondence selection. The robust correspondences selected by GMS are also used to match the same objects in image pairs, and by this way it acquires the best precision and F-measure. This experiment shows that using robust correspondences for object matching can improve the performance of the same object constraint.

Table 1.

The experiment about the same object constraint.

Method	Precision	Recall	F-Measure
The initial correspondences	0.131	1.000	0.231
GMS	0.277	0.868	0.419
OMBIC	0.281	0.641	0.390
OMBGMSC	0.309	0.721	0.432

$\mathrm{OMBIC}$ denotes the object matching by the initial correspondences, and $\mathrm{OMBGMSC}$ denotes the object matching by the correspondences selected by GMS.

The second comparison experiment is used to prove the effect of the same position on the same objects constraint, the related result is shown in Table 2. At first the correspondences that selected by the same object constraint using GMS is obtained, then the same position constraint is applied. The same position constraint is tested by two methods: one method is to utilize the seed fundamental matrix $F^0$ to select the correct correspondences, the other method is to utilize $F^l$ to select the correct correspondences. From this table, it can be seen that by using the same position constraint the precision and F-measure have been raised a lot, which proves that the same position constraint can further improve the performance of our algorithm on the basis of the same object constraint. From Table 2, it can also be seen that the same position constraint by $F^l$ have a better performance than the same position constraint only by $F^0$ . Because the correspondences in $S^0$ are not reliable and enough, the calculated fundamental matrix set $F^0$ is not accurate enough, which results in many correct correspondences being ignored. But by iteration, the proposed IFMEM method can use more and more robust correspondences to calculate the fundamental matrix of each object, and the final fundamental matrix $F^l$ can be more accurate and comprehensive. According to $F^l$ more correct correspondences can be selected.

Table 2.

The experiment about the same position constraint.

Method	Precision	Recall	F-Measure
OMBGMSC	0.309	0.721	0.432
The same position constraint by $F^0$	0.747	0.427	0.543
The same position constraint by $F^l$	0.773	0.658	0.711

Contrast experiments of different methods

Our method is also compared with some competitive correspondence selection methods such as RANSAC, GMS, VFC on the five datasets. Table 3 shows the performance of these feature correspondences selection methods. Because different thresholds of an algorithm have different influences on precision and recall, the statistical results of precision and recall in Table 3 are obtained according to the thresholds corresponding to the highest F-measure for each algorithm. Due to similar texture in these datasets, there are a lot of incorrect initial correspondences, for example, the correspondence result shown in Figure 8(a). From Table 3, it can be seen that our algorithm achieves the best precision and F-measure in the first four datasets, which proves that our algorithm has better performance in these datasets. In the MultiObject, our method achieves best F-measure. Although RANSAC algorithm achieves the best precision, its selected correspondences often locate only on one object and the correspondences on other objects are often discarded as shown in Figure 9(a). Besides, our method and GMS are both tested on TUM-RGB dataset, ²⁸ and the results are shown in Table 4. Because many images in this dataset are continuous, both methods achieve high accuracy compared with previous datasets. From Table 4, it can be seen that GMS achieves a higher precision, however, our method achieves higher recall and F-measure. That is because in our method every object matching result has a fundamental matrix to fit the correspondences on each object, more correspondences that are relative robust can be selected compared with GMS, therefore our method can obtain a better comprehensive result.

Table 3.

Evaluation results of the five correspondence selection algorithm on the five datasets.

Method	Graham			Gerrard			Person			South			MultiObjects
Precision	Recall	F-measure	Precision	Recall	F-measure	Precision	Recall	F-measure	Precision	Recall	F-measure	Precision	Recall	F-measure
RANSAC	0.6677	0.6650	0.6663	0.6107	0.6289	0.6196	0.7584	0.7172	0.7372	0.5754	0.5827	0.5790	0.636	0.708	0.670
GMS	0.6916	0.6657	0.6784	0.6463	0.6468	0.6465	0.7464	0.7155	0.7306	0.7133	0.5278	0.6067	0.509	0.784	0.617
VFC	0.5003	0.7207	0.5906	0.4119	0.7057	0.5201	0.6940	0.7729	0.7313	0.3742	0.6410	0.4726	0.546	0.668	0.600
Ours	0.7555	0.7069	0.7303	0.7353	0.6504	0.6903	0.7909	0.7792	0.7850	0.7413	0.5886	0.6562	0.546	0.899	0.679

Figure 8.

(a) The initial matches obtained by ORB, (b) the matches selected by RANSAC, (c) the matches selected by GMS, (d) the matches selected by VFC, and (e) the matches selected by our method SOSPC.

Figure 9.

(a)The matches selected by RANSAC, (b) the matches selected by GMS, (c) the matches selected by VFC, and (d) the matches selected by our method SOSPC.

Table 4.

Evaluation results of GMS and ours on TUM-RGB dataset.

Method	Precision	Recall	F-measure
GMS	0.926	0.895	0.910
Ours	0.897	0.991	0.942

Furthermore, we analyze the performance of different correspondence selection algorithms, and explain the result based on a pair of images taken out from dataset Person and shown in Figure 6. Figure 8(a) shows the initial correspondences obtained by ORB, and Figure 8(b)–(e) are the correspondence selection results of RANSAC, GMS, VFC, and Ours, respectively. Table 5 records indicators of these correspondence selection algorithms on this image pair. In the image pair, it is seen that there are many similar textures, the motion of the camera is changed much, and there are many wrong initial correspondences in Figure 8(a). For RANSAC algorithm, it often has excellent performance when wrong correspondences are less, but in these datasets, images contain many similar textures (e.g. leaves), which has caused many wrong correspondences, so the estimated model by RANSAC is affected a lot. GMS often selects the correspondences that match the same regions, but it cannot judge whether correspondences are true or false in the pixel level, so the precision is lower than RANSAC. Our method can match many same objects in image pairs and remove the wrong correspondences that match incorrect objects. Then our algorithm will calculate the fundamental matrix of each object, and by IFMEM more and more robust correspondences are used to calculate the fundamental matrix to improve its precision. By these fundamental matrix, many correct correspondences will be selected.

Table 5.

Evaluation results on an image pair.

Method	Precision	Recall	F-measure
RANSAC	0.417	0.833	0.556
GMS	0.375	0.333	0.353
VFC	0.00	0.00	0.00
Ours	0.545	1.00	0.706

The Precision-Recall (PR) curves are also drawn in Figure 10(a)–(e). These algorithms adopts different thresholds on Graham, Gerrard, Person, South, and MultiObjects. In the first four figures, it can be seen that the curves of our approach are on the upper right of other PR curves, which further proves that our method has the best performance. In the last figure, our method can achieve a high recall rate while maintaining a high accuracy, which also performs better performance.

Figure 10.

The performance of the evaluated algorithms on five datasets: (a) Graham, (b) Gerrard, (c) Person, (d) South, and (e) MultiObjects.

Conclusion

In this paper, we have proposed the correspondence selection method SOSPC to select the correct correspondences from the initial correspondences. In our approach, the same object constraint and the same position on the same object constraint are integrated into our correspondence selection algorithm. To match the same objects in the image pairs, we propose an object matching method by the correspondences selected by GMS. To improve the precision of the fundamental matrix, we propose the IFMEM method to calculate the fundamental matrix iteratively. Finally we have conducted several experiments to verify the effectiveness of the proposed constraints, and prove that our approach can achieve the best performance comparing with other correspondence selection algorithms in the given datasets.