# A Geometrical-Information-Assisted Approach for Local Feature Matching

Authors: Buhai Shi; Qingming Zhang; Haibo Xu
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This paper presents a geometrical-information-assisted approach for matching local features. With the aid of Bayes’ theorem, it is found that the posterior confidence of matched features can be improved by introducing global geometrical information given by distances between feature points. Based on this result, we work out an approach to obtain the geometrical information and apply it to assist matching features. The pivotal techniques in this paper include(1) exploiting elliptic parameters of feature descriptors to estimate transformations that map feature points in images to points in an assumed plane; (2) projecting feature points to the assumed plane and finding a reliable referential point in it; (3) computing differences of the distances between the projected points and the referential point. Our new approach employs these differences to assist matching features, reaching better performance than the nearest neighbor-based approach in precision versus the number of matched features.


---

## Body

## 1. Introduction

For matching local features, the threshold-based method and the nearest neighbor-based approach (NNA) are two fundamental strategies. Compared with the threshold-based approach, the NNA matches features more precisely [1]. From the previous works (cf. [2–5]) to the recent ones (cf. [6, 7]), the nearest neighbor techniques are exploited broadly. Since positions of matched features can be seen as samples generated from two images related by a certain homography, RANSAC [8] is usually applied to exclude the impact of outliers on the estimation [9–16], therefore improving matching effect of local features. RANSAC has a defect when inliers are fairly less in putative matches, which causes unpredictable elapsed time, even failing to estimate consensus sets. For matching features more efficiently, some methods introduce prior information into the algorithm of estimating consensus sets, e.g., Guided-MLESAC [17], PROSAC [18], and SESAC [19], using distributions constructed by prior information instead of the uniform distribution to generate hypothetical homographies. Besides, some preliminary processes are also employed to produce subsets containing more uncontaminated samples in advance before running plain RANSAC. For example, Cov-RANSAC [20] employs SPRT and a covariance test; DT-RANSAC [21] refines data by topological information in the Delaunay triangulation; SVH-RANSAC [22] adopts a local feature scale constraint to group observations; SC-RANSAC [23] utilizes spatial relations between extracted corresponding points; and WD-RANSAC [24] and QML-RANSAC [25] adopt the Wigner distribution and the quasi maximum likelihood algorithm, respectively. Nevertheless, in the case of matching features between nonrigidly transformed images, it is difficult to estimate a nonparametric consensus by a homography-estimation-based approach. Some nonparametric consensus methods are also developed to match local features. SparseVFC [26, 27] introduces sparse representations to estimating vector field consensus and shows powerful performance in matching features. LLT [28] exploits local geometrical constraints to estimate the consensus set which comprises inliers in matches between two rigidly or nonrigidly transformed images. Besides those consensus-estimation-based methods, approaches without estimating consensus are also studied. The method presented in [29] divides the vector of a local descriptor into subvectors and employs binary trees to compare subvectors to achieve NNA. For matching features in the binocular stereo scene, the approach in [30] uses some adjacent pixels near a feature point to form a block and then to find the best match by the block. LPM [31] applies local neighborhood structures to determine true matches, and based on it, GLPM [32] introduces a set with more confidence of including true matches, which are obtained by the distance ratios of local descriptors, and then reaches better performance than LPM. Another local-geometrical-information-based technique is proposed by [33] for describing features and matching features, which exploits topological relationship amid local features. Moreover, in the case of matching some deep features, convolutional neural networks are employed [34].Motivated by approaches above built on local geometrical information, we discuss a new method assisted by geometrical information to improve the performance for matching features. An extracting procedure for scale-invariant features provides information about scale or even affine parameters of features (cf. [10, 35]), which can estimate the geometrical relationship between two images. We here discover an appropriate geometrical relation and study how to estimate it and exploit this relation to further improve matching effect. This paper is organized as follows. In Section 2, we discuss factors that influence matching effect and point out a new way to enhance matching effect. In Section 3, we discuss how Euclidean distance can assist matching features and work out an algorithm of matching features assisted by geometrical information. We would like to abbreviate the algorithm Geometrical-Information-Assisted Matching as GIAM in this paper. In Section 4, we test GIAM and compare the results with other methods. Finally we conclude our work in Section 5.


## 2. Factors That Influence Matching Effect

In what follows,Pair(P,Q) denotes the event that a point P matches another point Q, and ~Pair(P,Q) is the negation of it. F(·) denotes a feature descriptor and d(·,·) is a similar metric of the descriptors of two points. Besides, the symbol c(ε) represents that the function c(ε)→c (c is a constant satisfying 0≤c≤1) as ε→0, where ε is a vector in Rn for some positive integer n.


### 2.1. Discussion for Posterior Confidence of Matched Features

Usually it is not difficult to construct a descriptorF(·) and a similar metric d(·,·) satisfying(1)PrdFP,FQ≤ϵ∣PairP,Q=1ϵ,where P and Q are two points of attempt matching. Suppose Pr(Pair(P,Q))=p. For a certain descriptor and a similar metric, we have (2)PrPairP,Q,dFP,FQ≤ϵ=1ϵp. Hence the posterior probability of the matched P and Q is(3)PrPairP,Q∣dFP,FQ≤ϵ=1ϵp1ϵp+R, where R=Pr(d(F(P),F(Q))≤ϵ∣~Pair(P,Q))(1-p).As can be seen from (3), except the trivial case of p=1, to reach a higher posterior confidence of the match (P,Q), it is plausible to lower the conditional probability Pr(d(F(P),F(Q))≤ϵ∣~Pair(P,Q)). Nevertheless, comparing with designing an appropriate F(·) and d(·,·) satisfying Pr(d(F(P),F(Q))≤ϵ∣Pair(P,Q))=1(ϵ), constructing F(·) and d(·,·) such that Pr(d(F(P),F(Q))≤ϵ∣~Pair(P,Q))=0(ϵ), is a more arduous task. Thus it would be alleviating if another metric m(·,·) can be introduced satisfying(4)PrmP,Q≤ϵ∣~PairP,Q=eϵfor a given ~Pair(P,Q) and for some 0<e≤1, where the event {m(P,Q)≤ϵ2∣~Pair(P,Q)} is conditionally independent with {d(F(P),F(Q))≤ϵ1∣~Pair(P,Q)}. Let us denote Pr(d(F(P),F(Q))≤ϵ)≜c1(ϵ) and Pr(d(F(P),F(Q))≤ϵ1,m(P,Q)≤ϵ2)≜c2(ϵ1,ϵ2), so that the posterior confidence of matched features can be written as(5)PrPairP,Q∣dFP,FQ≤ϵ1,mP,Q≤ϵ2=c2ϵ1,ϵ2pc2ϵ1,ϵ2p+c1ϵ1-1ϵ1p·eϵ2.In contrast to (3), (5) shows that e(ϵ2) approximating 0(ϵ2) improves posterior confidence. As will be shown next, some geometrical information can be exploited to construct a metric satisfying (4).


### 2.2. Geometrical Information for Matching Features

Suppose that two imagesIP and IQ are transformed, respectively, from an image Icom by two affine homographies(6)HP=TPtP01,HQ=TQtQ01,where tP and tQ contribute to translations on the homogeneous coordinates; TP and TQ are invertible linear transformations on the Cartesian coordinates, which yield rotation, scale change, and tilt of planar images. Let symbols Po and Qo be matched points and symbols P and Q be points (respectively, in IP and IQ) to be matched. Here we by “a point in an image”, say P in IP, mean that P∈dom(IP), its domain of definition. Since the procedure for feature extracting hardly provides information about tP and tQ, we then perform a technique to erase them by calculation of Euclidean distance (which is denoted by dE(·,·)) in the same image Icom as follows: (7)dETP-1P-tP,TP-1Po-tP=dETP-1P,TP-1Po,and (8)dETQ-1Q-tQ,TQ-1Qo-tQ=dETQ-1Q,TQ-1Qo.Therefore we figure out the following expression describing geometrical information (where i=1,…,n)(9)GIP,Q=dEdETP-1P,TP-1Po,dETQ-1Q,TQ-1Qo.Noting that the pointTP-1(Po-tP) equals TQ-1(Qo-tQ) in the image Icom, we will show that the geometrical information (9) can be employed as a metric satisfying (4) and (5). We call such a TP-1(Po-tP) thereferential point and (Po,Qo) thereferential pair.Proposition 1.
Suppose that the imageIcom is defined on R2. Then any point P in IP and any point Q in IQ satisfy (10)PrGIP,Q≤ϵ∣~PairP,Q=0ϵ.Proof.
Denote byp(x,y) the p.d.f. of projected feature points (x,y) in Icom (from dom(IP) or dom(IQ)) on R2 and set r=dE(TP-1P,TP-1Po). Since P and Q do not match, the point TP-1(P-tP) differs from TQ-1(Q-tQ) in R2. We then have (11)PrGIP,Q≤ϵ∣~PairP,Q=∬Dϵ\TP-1P-tPpx,ydxdy,where Dϵ={(x,y)∣(r-ϵ)2≤x2+y2≤(r+ϵ)2}. It follows that Pr(GI(P,Q)≤ϵ∣~Pair(P,Q))→0 as ϵ→0.The result of Proposition1 indicates an optimal case in applying (5). However, we need to formulate the discrete form for pragmatic use, which is built on a probability dominated by the counting measure.Proposition 2.
Suppose thatIcom=f(xk,yl) is an image in its discrete form, where k=1,2,…,M, l=1,2,…,N for some M,N∈Z+. Then any point P in IP and any point Q in IQ satisfy (12)PrGIP,Q≤ϵ∣~PairP,Q=cϵ,where 0≤c<1.Proof.
Denote bypkl the probability of a feature point (from dom(IP) or dom(IQ)) being projected to the point (xk,yl) and set r=dE(TP-1P,TP-1Po). Since P and Q do not match, the point TP-1(P-tP) differs from TQ-1(Q-tQ) in the image Icom. Hence we have (13)PrGIP,Q≤ϵ∣~PairP,Q=∑xk,yl∈Dϵ\TP-1P-tPpkl<1,where Dϵ={(x,y)∈dom(Icom)∣(r-ϵ)2≤x2+y2≤(r+ϵ)2}. We finish the proof by noting that for sufficiently small ϵ’s, the Dϵ’s are constant.Since the number of pixels centred at the referential point with a certain radius is far less than the number of pixels in the whole image, presumably in most cases thec should be far less than 1. Therefore Proposition 2 offers a suboptimal result for (5) in matching features. The proofs and discussions of Propositions 1 and 2 are shown in Figure 1.Figure 1
An illustration ofIcom for Propositions 1 and 2, where the left side indicates that the probability of two points P and Q being projected into the same circle centred at the referential point is zero under the Lebesgue measure on R2, whereas the right side shows that the counterpart may not be zero under the counting measure since there are points except TP-1(P-tP) (e.g., the 11 pink boxes above) that Q could be projected to.


## 2.1. Discussion for Posterior Confidence of Matched Features

Usually it is not difficult to construct a descriptorF(·) and a similar metric d(·,·) satisfying(1)PrdFP,FQ≤ϵ∣PairP,Q=1ϵ,where P and Q are two points of attempt matching. Suppose Pr(Pair(P,Q))=p. For a certain descriptor and a similar metric, we have (2)PrPairP,Q,dFP,FQ≤ϵ=1ϵp. Hence the posterior probability of the matched P and Q is(3)PrPairP,Q∣dFP,FQ≤ϵ=1ϵp1ϵp+R, where R=Pr(d(F(P),F(Q))≤ϵ∣~Pair(P,Q))(1-p).As can be seen from (3), except the trivial case of p=1, to reach a higher posterior confidence of the match (P,Q), it is plausible to lower the conditional probability Pr(d(F(P),F(Q))≤ϵ∣~Pair(P,Q)). Nevertheless, comparing with designing an appropriate F(·) and d(·,·) satisfying Pr(d(F(P),F(Q))≤ϵ∣Pair(P,Q))=1(ϵ), constructing F(·) and d(·,·) such that Pr(d(F(P),F(Q))≤ϵ∣~Pair(P,Q))=0(ϵ), is a more arduous task. Thus it would be alleviating if another metric m(·,·) can be introduced satisfying(4)PrmP,Q≤ϵ∣~PairP,Q=eϵfor a given ~Pair(P,Q) and for some 0<e≤1, where the event {m(P,Q)≤ϵ2∣~Pair(P,Q)} is conditionally independent with {d(F(P),F(Q))≤ϵ1∣~Pair(P,Q)}. Let us denote Pr(d(F(P),F(Q))≤ϵ)≜c1(ϵ) and Pr(d(F(P),F(Q))≤ϵ1,m(P,Q)≤ϵ2)≜c2(ϵ1,ϵ2), so that the posterior confidence of matched features can be written as(5)PrPairP,Q∣dFP,FQ≤ϵ1,mP,Q≤ϵ2=c2ϵ1,ϵ2pc2ϵ1,ϵ2p+c1ϵ1-1ϵ1p·eϵ2.In contrast to (3), (5) shows that e(ϵ2) approximating 0(ϵ2) improves posterior confidence. As will be shown next, some geometrical information can be exploited to construct a metric satisfying (4).


## 2.2. Geometrical Information for Matching Features

Suppose that two imagesIP and IQ are transformed, respectively, from an image Icom by two affine homographies(6)HP=TPtP01,HQ=TQtQ01,where tP and tQ contribute to translations on the homogeneous coordinates; TP and TQ are invertible linear transformations on the Cartesian coordinates, which yield rotation, scale change, and tilt of planar images. Let symbols Po and Qo be matched points and symbols P and Q be points (respectively, in IP and IQ) to be matched. Here we by “a point in an image”, say P in IP, mean that P∈dom(IP), its domain of definition. Since the procedure for feature extracting hardly provides information about tP and tQ, we then perform a technique to erase them by calculation of Euclidean distance (which is denoted by dE(·,·)) in the same image Icom as follows: (7)dETP-1P-tP,TP-1Po-tP=dETP-1P,TP-1Po,and (8)dETQ-1Q-tQ,TQ-1Qo-tQ=dETQ-1Q,TQ-1Qo.Therefore we figure out the following expression describing geometrical information (where i=1,…,n)(9)GIP,Q=dEdETP-1P,TP-1Po,dETQ-1Q,TQ-1Qo.Noting that the pointTP-1(Po-tP) equals TQ-1(Qo-tQ) in the image Icom, we will show that the geometrical information (9) can be employed as a metric satisfying (4) and (5). We call such a TP-1(Po-tP) thereferential point and (Po,Qo) thereferential pair.Proposition 1.
Suppose that the imageIcom is defined on R2. Then any point P in IP and any point Q in IQ satisfy (10)PrGIP,Q≤ϵ∣~PairP,Q=0ϵ.Proof.
Denote byp(x,y) the p.d.f. of projected feature points (x,y) in Icom (from dom(IP) or dom(IQ)) on R2 and set r=dE(TP-1P,TP-1Po). Since P and Q do not match, the point TP-1(P-tP) differs from TQ-1(Q-tQ) in R2. We then have (11)PrGIP,Q≤ϵ∣~PairP,Q=∬Dϵ\TP-1P-tPpx,ydxdy,where Dϵ={(x,y)∣(r-ϵ)2≤x2+y2≤(r+ϵ)2}. It follows that Pr(GI(P,Q)≤ϵ∣~Pair(P,Q))→0 as ϵ→0.The result of Proposition1 indicates an optimal case in applying (5). However, we need to formulate the discrete form for pragmatic use, which is built on a probability dominated by the counting measure.Proposition 2.
Suppose thatIcom=f(xk,yl) is an image in its discrete form, where k=1,2,…,M, l=1,2,…,N for some M,N∈Z+. Then any point P in IP and any point Q in IQ satisfy (12)PrGIP,Q≤ϵ∣~PairP,Q=cϵ,where 0≤c<1.Proof.
Denote bypkl the probability of a feature point (from dom(IP) or dom(IQ)) being projected to the point (xk,yl) and set r=dE(TP-1P,TP-1Po). Since P and Q do not match, the point TP-1(P-tP) differs from TQ-1(Q-tQ) in the image Icom. Hence we have (13)PrGIP,Q≤ϵ∣~PairP,Q=∑xk,yl∈Dϵ\TP-1P-tPpkl<1,where Dϵ={(x,y)∈dom(Icom)∣(r-ϵ)2≤x2+y2≤(r+ϵ)2}. We finish the proof by noting that for sufficiently small ϵ’s, the Dϵ’s are constant.Since the number of pixels centred at the referential point with a certain radius is far less than the number of pixels in the whole image, presumably in most cases thec should be far less than 1. Therefore Proposition 2 offers a suboptimal result for (5) in matching features. The proofs and discussions of Propositions 1 and 2 are shown in Figure 1.Figure 1
An illustration ofIcom for Propositions 1 and 2, where the left side indicates that the probability of two points P and Q being projected into the same circle centred at the referential point is zero under the Lebesgue measure on R2, whereas the right side shows that the counterpart may not be zero under the counting measure since there are points except TP-1(P-tP) (e.g., the 11 pink boxes above) that Q could be projected to.


## 3. Matching Features Assisted by Geometrical Information

### 3.1. Discussion for Algorithm

We first discuss how to obtainTP-1 and TQ-1. Suppose that there is a linear transformation T mapping an unit circle {x12+x22=1}, to an ellipse {ay12+2by1y2+cy22=1}, and denote A=abbc, x=(x1,x2)T, and y=(y1,y2)T. Then we have (14)y=TxxTx=1⇒T-1yTT-1y=1⇒yTT-1TT-1y=1⇒A=T-1TT-1,which means that by Cholesky decomposition of the positive-definite matrix A, we can obtain the linear transformation T-1. In descriptors of Mikolajczyk’s format [10, 35], the affine region of a feature point is enclosed by an ellipse with parameters a,b,c (for the details of these parameters please refer to the website http://www.robots.ox.ac.uk/~vgg/research/affine/descriptors.html#binaries), by which we can calculate TP-1 and TQ-1.Next we need to find the referential pair(Po,Qo) and to estimate the invertible linear transformations TP and TQ. Suppose that {(Pi,Qi)}i=1L is a sequence, which consists of the pairs ordered in similar metrics of descriptors. We assign the most similar pair as the referential pair, i.e., (Po,Qo)=(P1,Q1). Since the unit circle in Icom can be transformed by TP and TQ onto the boundaries (ellipses) of affine regions of feature points P1 and Q1, respectively, TP-1 and TQ-1 should be the respective Cholesky decomposition of matrices aP1bP1bP1cP1 and aQ1bQ1bQ1cQ1, where aP1,bP1,cP1 are parameters of the boundary ellipse of the affine region of P1 and the same applies to aQ1,bQ1,cQ1.The geometrical information for each pair of feature points can be calculated henceforth. For two sets of feature points{Pi}i=1M and {Qj}j=1N, we compute their geometrical information as(15)GIPi,Qj=dEdETP-1Pi,TP-1Po,dETQ-1Qj,TQ-1Qo.Finally, new matches are chosen by ordered scores which are calculated by a sum of similar metrics of features and geometrical information of feature points. We calculate the score of each putative pair as(16)scorePi,Qj=dFPi,FQj+GIPi,Qj.


### 3.2. Data Objects and the Algorithm of GIAM

According to the preceding discussion, we assign five matrices, including a descriptor difference matrix, a distance matrix for candidates in the imageIP, a distance matrix for candidates in the image IQ, a distance correlation matrix, and a score matrix to be basic data objects.Similar metrics between each pair of candidates constitute the descriptor difference matrixD=(dij), where dij=d(F(Pi),F(Qj)).The distance matrices areMP=(rij) and MQ=(eij), where the entries rij represent the distance induced by TP between the corresponding points (in Icom) of the i-th and the j-th feature points in IP, and the same applies to eij for feature points in IQ.The distance correlation matrixCk=(cijk) presents the geometrical information of feature points, which is given by (17)Ck=Rk⊖Ekfor k=1,…,N, where(18)Rk=ri11…rikk⋮⋮⋮,Ek=e1j1………ekjk…,and rikk and ekjk are entries selected from distance matrices MP=(rij) and MQ=(eij) in the following manner: if the entries of the k-th pair are made up of the ik-th candidate in the image IP and the jk-th candidate in the image IQ, then the k-th column in matrix Rk is the ik-th column in matrix MP, and the k-th row in matrix Ek is the jk-th row in matrix MQ, whereas the operator ⊖ in (17) is defined by cijk=∑s=1k‍(ris-esj)2. Here we name k theorder of the distance correlation matrix.The score matrixSk=D+Ck contains all results computed by (16).We summarize our algorithm in Algorithm1.Algorithm 1:Algorithm of GIAM (Geometrical-Information-Assisted Matching).
Input: Two sets of descriptors in Mikolajczyk’s format, Ω P = P i = x i , y i , a i , b i , c i , c o d e s i i = 1 M and ΩQ=Qj=xj,yj,aj,bj,cj,codesji=jN. (a) Calculate the descriptor difference matrixD. (b) Pick out the most similar pair of feature points by using the descriptor difference matrixD and assign it as the referential pair (Po,Qo). (c) Estimate theTP-1 and TQ-1 in Eq. (15). (d) Calculate the distance correlation matrixC1 by Eq. (15) and (17). Since there is only one referential pair, the order of the distance correlation matrix is1; (e) Calculate the score matrixS1=D+C1. (f) Compute an ordered matched listPik,Qjkk=1L by using the score matrix S1, where L=min{M,N} is the number of matched feature pairs. Output: An ordered matched list {(Pik,Qjk)}k=1L.


## 3.1. Discussion for Algorithm

We first discuss how to obtainTP-1 and TQ-1. Suppose that there is a linear transformation T mapping an unit circle {x12+x22=1}, to an ellipse {ay12+2by1y2+cy22=1}, and denote A=abbc, x=(x1,x2)T, and y=(y1,y2)T. Then we have (14)y=TxxTx=1⇒T-1yTT-1y=1⇒yTT-1TT-1y=1⇒A=T-1TT-1,which means that by Cholesky decomposition of the positive-definite matrix A, we can obtain the linear transformation T-1. In descriptors of Mikolajczyk’s format [10, 35], the affine region of a feature point is enclosed by an ellipse with parameters a,b,c (for the details of these parameters please refer to the website http://www.robots.ox.ac.uk/~vgg/research/affine/descriptors.html#binaries), by which we can calculate TP-1 and TQ-1.Next we need to find the referential pair(Po,Qo) and to estimate the invertible linear transformations TP and TQ. Suppose that {(Pi,Qi)}i=1L is a sequence, which consists of the pairs ordered in similar metrics of descriptors. We assign the most similar pair as the referential pair, i.e., (Po,Qo)=(P1,Q1). Since the unit circle in Icom can be transformed by TP and TQ onto the boundaries (ellipses) of affine regions of feature points P1 and Q1, respectively, TP-1 and TQ-1 should be the respective Cholesky decomposition of matrices aP1bP1bP1cP1 and aQ1bQ1bQ1cQ1, where aP1,bP1,cP1 are parameters of the boundary ellipse of the affine region of P1 and the same applies to aQ1,bQ1,cQ1.The geometrical information for each pair of feature points can be calculated henceforth. For two sets of feature points{Pi}i=1M and {Qj}j=1N, we compute their geometrical information as(15)GIPi,Qj=dEdETP-1Pi,TP-1Po,dETQ-1Qj,TQ-1Qo.Finally, new matches are chosen by ordered scores which are calculated by a sum of similar metrics of features and geometrical information of feature points. We calculate the score of each putative pair as(16)scorePi,Qj=dFPi,FQj+GIPi,Qj.


## 3.2. Data Objects and the Algorithm of GIAM

According to the preceding discussion, we assign five matrices, including a descriptor difference matrix, a distance matrix for candidates in the imageIP, a distance matrix for candidates in the image IQ, a distance correlation matrix, and a score matrix to be basic data objects.Similar metrics between each pair of candidates constitute the descriptor difference matrixD=(dij), where dij=d(F(Pi),F(Qj)).The distance matrices areMP=(rij) and MQ=(eij), where the entries rij represent the distance induced by TP between the corresponding points (in Icom) of the i-th and the j-th feature points in IP, and the same applies to eij for feature points in IQ.The distance correlation matrixCk=(cijk) presents the geometrical information of feature points, which is given by (17)Ck=Rk⊖Ekfor k=1,…,N, where(18)Rk=ri11…rikk⋮⋮⋮,Ek=e1j1………ekjk…,and rikk and ekjk are entries selected from distance matrices MP=(rij) and MQ=(eij) in the following manner: if the entries of the k-th pair are made up of the ik-th candidate in the image IP and the jk-th candidate in the image IQ, then the k-th column in matrix Rk is the ik-th column in matrix MP, and the k-th row in matrix Ek is the jk-th row in matrix MQ, whereas the operator ⊖ in (17) is defined by cijk=∑s=1k‍(ris-esj)2. Here we name k theorder of the distance correlation matrix.The score matrixSk=D+Ck contains all results computed by (16).We summarize our algorithm in Algorithm1.Algorithm 1:Algorithm of GIAM (Geometrical-Information-Assisted Matching).
Input: Two sets of descriptors in Mikolajczyk’s format, Ω P = P i = x i , y i , a i , b i , c i , c o d e s i i = 1 M and ΩQ=Qj=xj,yj,aj,bj,cj,codesji=jN. (a) Calculate the descriptor difference matrixD. (b) Pick out the most similar pair of feature points by using the descriptor difference matrixD and assign it as the referential pair (Po,Qo). (c) Estimate theTP-1 and TQ-1 in Eq. (15). (d) Calculate the distance correlation matrixC1 by Eq. (15) and (17). Since there is only one referential pair, the order of the distance correlation matrix is1; (e) Calculate the score matrixS1=D+C1. (f) Compute an ordered matched listPik,Qjkk=1L by using the score matrix S1, where L=min{M,N} is the number of matched feature pairs. Output: An ordered matched list {(Pik,Qjk)}k=1L.


## 4. Simulations

### 4.1. Datasets and Methods for Simulations

To test our new algorithm for local feature matching, we employ four methods, NNA, NNA with the plain RANSAC (NNA-RANSAC), NNA with LPM (NNA-LPM), and NNA with GIAM (NNA-GIAM). The codes of RANSAC adopted in our simulations are developed by Marco Zuliani (all these codes are obtained from the websitehttps://github.com/RANSAC/RANSAC-Toolbox) and the codes of LPM are developed by Dr. Jiayi Ma (all these codes are obtained from the website https://github.com/jiayi-ma/VFC). We set parameters for LPM as shown in Table 1 and parameters for RANSAC as shown in Table 2.Table 1
Parameters in LPM.
λ 1 = 0.8; λ2=0.5; The number of nearest neighbour 1=6; The number of nearest neighbour 2=6; τ 1 = 0.2; τ2=0.2;Table 2
Main parameters in RANSAC.
Chi-squared probability threshold for inliers 1 - e - 4 False alarm rate e - 6 Algorithm flavour R A N S A C Maximum number of iterations 100000 Minimum number of iterations 1 Theσ of assumed Gaussian noise 1We utilize an executable file implemented by Dr. Mikolajczyk (the original codes are obtained from the websitehttp://www.robots.ox.ac.uk/~vgg/research/affine/) to produce experimental data. First, we use the executable file to process all test images and generate the sets of descriptors for each test image. Second, we match features between those sets by NNA, NNA-RANSAC, and NNA-LPM as well as NNA-GIAM, respectively. We here define that a point in the first image correctly matches a corresponding point in the second image, if the distance between the point in the second image and thestandard point (to which the point in the first image is mapped via a given homography which is a ground truth) is less than 2 pixels. Precision of matches with regard to a number of matched features equals the number of correct matches divided by the number of matches. We apply a curve of precision vs. number of matches to estimate the performance of the four algorithms.For tests under fairly complex scenes, such as changes from slight to dramatic degree of rotation, scale, viewpoint, blur, light, and JPEG compression, the Mikolajczyk’s test data [36] are exploited, which consist of a group of image sets with homographies as the ground truth (the image sequences are from the website http://www.robots.ox.ac.uk/~vgg/research/affine/detectors.html) There are 8 test sets in the group, and each set contains 6 images. We match features in the first image to the rest of images in each test sequences by NNA, NNA-RANSAC, and NNA-LPM as well as NNA-GIAM, respectively. In these tests we employ the Harris-Affine detector [10, 35] to extract features and describe them by the SIFT [3, 4].


### 4.2. Results of Experiments

We obtain 40 test curves divided into 8 sets, which are shown in Figures2–9 in the appendix. In these figures, the “1vs.k” in the captions is interpreted as “the first image versus the k-th image”, indicating that the test result is obtained by matching features between the first image and the k-th image in the same test image sequence.Figure 2
Rotation and scale change for the textured scene by the Bark sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 3
Rotation and scale change for the structured scene by the Boat sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 4
Blur for the structured scene by the Bikes sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 5
Blur for the textured scene by the Trees sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 6
JEPG compression by the UBC sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 7
Illumination change by the Leuven sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 8
Viewpoint change for the textured scene by the Wall sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 9
Viewpoint change for the structured scene by the Graffiti sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)In the case of rotation and scale change for the textured scene (cf. Figure2), GIAM overcomes NNA and exceeds LPM and RANSAC when the change is dramatic. After the middle degree change ((c), (d), (e) in Figure 2), GIAM outperforms LPM on most intervals of “number of matched features”. GIAM shows slight advantage to NNA on the rotation and scale change for the structured scene (cf. Figure 3). In the cases of blurred images on both structured scene and textured scene (cf. Figures 4 and 5), GIAM improves precision of NNA. GIAM reaches higher scores than LPM when the number of matches is relatively small ((a), (b), (c) in Figure 4) in the structured scene test, and admits analogous precision to RANSAC. For the severest JEPG compression, GIAM has better performance than NNA and LPM (cf. Figure 6). GIAM, NNA, and RANSAC show almost identical performance in the case of slight to mild JPEG compression over more than half of the matches. LPM finds relatively fewer correct matches in this test sequence. In the case of illumination change (cf. Figure 7), GIAM reaches higher precision than NNA as the light turns dim and in general slightly outperforms LPM over the first 1/3 of all matches in each degree of illumination. In the case of viewpoint change for the textured scene (cf. Figure 8), GIAM overcomes LPM and exceeds NNA in all tests, and has comparable performance with RANSAC over the first 1/2 of all matches. Under the situation of viewpoint change for the structured scene (cf. Figure 9), GIAM exceeds NNA in all tests and shows better performance than others when the number of matches and the change of viewpoints are relatively small ((a), (b) in Figure 9).Consequently, it can be seen from these results that GIAM improves precision of NNA on the situations including scale change, blur change, JEPG compression change, illumination change, and slight change in viewpoint, and reaches better performance than LPM in some change of rotation, scale, illumination, signal compression, and viewpoint.


## 4.1. Datasets and Methods for Simulations

To test our new algorithm for local feature matching, we employ four methods, NNA, NNA with the plain RANSAC (NNA-RANSAC), NNA with LPM (NNA-LPM), and NNA with GIAM (NNA-GIAM). The codes of RANSAC adopted in our simulations are developed by Marco Zuliani (all these codes are obtained from the websitehttps://github.com/RANSAC/RANSAC-Toolbox) and the codes of LPM are developed by Dr. Jiayi Ma (all these codes are obtained from the website https://github.com/jiayi-ma/VFC). We set parameters for LPM as shown in Table 1 and parameters for RANSAC as shown in Table 2.Table 1
Parameters in LPM.
λ 1 = 0.8; λ2=0.5; The number of nearest neighbour 1=6; The number of nearest neighbour 2=6; τ 1 = 0.2; τ2=0.2;Table 2
Main parameters in RANSAC.
Chi-squared probability threshold for inliers 1 - e - 4 False alarm rate e - 6 Algorithm flavour R A N S A C Maximum number of iterations 100000 Minimum number of iterations 1 Theσ of assumed Gaussian noise 1We utilize an executable file implemented by Dr. Mikolajczyk (the original codes are obtained from the websitehttp://www.robots.ox.ac.uk/~vgg/research/affine/) to produce experimental data. First, we use the executable file to process all test images and generate the sets of descriptors for each test image. Second, we match features between those sets by NNA, NNA-RANSAC, and NNA-LPM as well as NNA-GIAM, respectively. We here define that a point in the first image correctly matches a corresponding point in the second image, if the distance between the point in the second image and thestandard point (to which the point in the first image is mapped via a given homography which is a ground truth) is less than 2 pixels. Precision of matches with regard to a number of matched features equals the number of correct matches divided by the number of matches. We apply a curve of precision vs. number of matches to estimate the performance of the four algorithms.For tests under fairly complex scenes, such as changes from slight to dramatic degree of rotation, scale, viewpoint, blur, light, and JPEG compression, the Mikolajczyk’s test data [36] are exploited, which consist of a group of image sets with homographies as the ground truth (the image sequences are from the website http://www.robots.ox.ac.uk/~vgg/research/affine/detectors.html) There are 8 test sets in the group, and each set contains 6 images. We match features in the first image to the rest of images in each test sequences by NNA, NNA-RANSAC, and NNA-LPM as well as NNA-GIAM, respectively. In these tests we employ the Harris-Affine detector [10, 35] to extract features and describe them by the SIFT [3, 4].


## 4.2. Results of Experiments

We obtain 40 test curves divided into 8 sets, which are shown in Figures2–9 in the appendix. In these figures, the “1vs.k” in the captions is interpreted as “the first image versus the k-th image”, indicating that the test result is obtained by matching features between the first image and the k-th image in the same test image sequence.Figure 2
Rotation and scale change for the textured scene by the Bark sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 3
Rotation and scale change for the structured scene by the Boat sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 4
Blur for the structured scene by the Bikes sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 5
Blur for the textured scene by the Trees sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 6
JEPG compression by the UBC sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 7
Illumination change by the Leuven sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 8
Viewpoint change for the textured scene by the Wall sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)Figure 9
Viewpoint change for the structured scene by the Graffiti sequence, where (a), (b), (c), (d), (e) show test scores for 1vs.2, 1vs.3, 1vs.4, 1vs.5, respectively.
(a) (b) (c) (d) (e)In the case of rotation and scale change for the textured scene (cf. Figure2), GIAM overcomes NNA and exceeds LPM and RANSAC when the change is dramatic. After the middle degree change ((c), (d), (e) in Figure 2), GIAM outperforms LPM on most intervals of “number of matched features”. GIAM shows slight advantage to NNA on the rotation and scale change for the structured scene (cf. Figure 3). In the cases of blurred images on both structured scene and textured scene (cf. Figures 4 and 5), GIAM improves precision of NNA. GIAM reaches higher scores than LPM when the number of matches is relatively small ((a), (b), (c) in Figure 4) in the structured scene test, and admits analogous precision to RANSAC. For the severest JEPG compression, GIAM has better performance than NNA and LPM (cf. Figure 6). GIAM, NNA, and RANSAC show almost identical performance in the case of slight to mild JPEG compression over more than half of the matches. LPM finds relatively fewer correct matches in this test sequence. In the case of illumination change (cf. Figure 7), GIAM reaches higher precision than NNA as the light turns dim and in general slightly outperforms LPM over the first 1/3 of all matches in each degree of illumination. In the case of viewpoint change for the textured scene (cf. Figure 8), GIAM overcomes LPM and exceeds NNA in all tests, and has comparable performance with RANSAC over the first 1/2 of all matches. Under the situation of viewpoint change for the structured scene (cf. Figure 9), GIAM exceeds NNA in all tests and shows better performance than others when the number of matches and the change of viewpoints are relatively small ((a), (b) in Figure 9).Consequently, it can be seen from these results that GIAM improves precision of NNA on the situations including scale change, blur change, JEPG compression change, illumination change, and slight change in viewpoint, and reaches better performance than LPM in some change of rotation, scale, illumination, signal compression, and viewpoint.


## 5. Conclusion

We have studied how geometrical information improves the posterior confidence of matched features and therefore enhances the matching effect. There are two essential merits in our work. The first one is that we utilize Bayes’ theorem to analyze factors influencing matching effect and figure out that prior information, which is a conditional distribution satisfying (4), can assist improving the posterior confidence of matches. The second one is exploiting the geometrical information in the descriptors, which can be used to estimate the distance between projected feature points. Consequently, the technique proposed in this paper shows its capability to improve the performance of matching features.



---

*Source: 1409672-2019-02-24.xml*