# Research on the Fundamental Principles and Characteristics of Correspondence Function

Authors: Xiangru Li; Guanghui Wang; Q. M. Jonathan Wu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The correspondence function (CF) is a concept
recently introduced to reject the mismatches from given putative
correspondences. The fundamental idea of the CF is
that the relationship of some corresponding points between two
images to be registered can be described by a pair of vector-valued
functions, estimated by a nonparametric regression
method with more flexibility than the normal parametric model,
for example, homography matrix, similarity transformation, and
projective transformations. Mismatches are rejected by
checking their consistency with the CF. This paper proposes a
visual scheme to investigate the fundamental principles of the
CF and studies its characteristics by experimentally comparing
it with the widely used parametric model epipolar geometry
(EG). It is shown that the CF describes the mapping from the
points in one image to their corresponding points in another
image, which enables a direct estimation of the positions of the
corresponding points. In contrast, the EG acts by reducing the
search space for corresponding points from a two-dimensional
space to a line, which is a problem in one-dimensional space. As
a result, the undetected mismatches of the CF are usually near
the correct corresponding points, but many of the undetected
mismatches of the EG are far from the correct point.


---

## Body

## 1. Introduction

Finding point correspondences between two images is a fundamental problem in computer vision [1, 2]. In two given images, the corresponding points (CPs) are the projections of the same point in a scene. Many computer vision algorithms and applications rely on the successful identification of point correspondences between two images, for example, tracking, stereo vision, motion analysis, object recognition, remote sensing, image mosaicing, and automatic quality control, among others [3–7].Point correspondences are usually established by the following procedures: extracting salient points, calculating their descriptors based on a small and local area around them, establishing putative correspondences by comparing the descriptors, and refining the putative correspondences. Compared with the representations based on a large spatial area, local feature descriptors are usually more robust to brightness variation, deformation, and occlusion but have less distinctiveness. This typically results in a high percentage of mismatches/outliers among the computed putative correspondences, which are very likely to ruin traditional estimation methods [8–10]. Therefore, an essential problem in computer vision is rejecting mismatches from given putative correspondences in a refining stage [11–13].Correspondence function (CF) is a model recently introduced based on point set mapping theory to reject mismatches from putative correspondences [2]. The fundamental idea of CF is that, for two given images I and I′ of a scene, the relationships between their CPs can be described by a pair of vector-valued functions, which are estimated by a nonparametric regression method. Mismatches are then detected by checking whether they are consistent with the CFs. The key of the model is that the relationships between CPs are represented with more flexibility than the usual parametric model, for example, homography matrix [14], similarity transformation [15], and projective transformations [15]. The flexibility is to account for nonrigidity of objects or to reduce the undue influence from outliers.In this work, we propose a visual scheme to investigate the fundamental principles of CF (Figures1 and 2) and to study its characteristics by experimentally comparing it with the widely used parametric model epipolar geometry (EG) (some rudimentary comparisons were made between CF and EG in a conference paper ([16])). It is shown that the CF describes the mapping from a point in one image to its CP(s) in another image, which enables us to directly estimate the positions of the CPs. However, the EG acts by reducing the search space for CPs from a two-dimensional space to a line, which is a problem in one-dimensional space. In applications, the result of the difference between EG and CF is that the undetected mismatches by CF are usually near the correct CPs, but many of the undetected mismatches of EG are far from the correct correspondence.Figure 1
A sketch map of the relationships between CPs. (a) Two axes are a sketch map of two imagesI and I′ of a scene to be matched; that curve is a sketch map of the correspondence manifold formed by CPs between I and I′ [17]; (b) a sketch map of the relationship between CPs presented to emphasize the mapping from one image point to its CP(s).
(a)
(b)Figure 2
Convert the relationship between CPs into two function mappings. The red dotted lines represent the deleted corresponding connections and the original corresponding relationship in Figure1(b) can be recovered from (a) and (b) by collecting all of the remaining connections and deleting the directions. (a) CRI→I′: these relationships between CPs can be depicted by a function from I to I′; (b) CRI′→I: these relationships between CPs can be depicted by a function from I′ to I.
(a)
(b)


## 2. Related Research

The mismatch-rejecting problem has been investigated in many studies [14, 18, 19], and the EG constraint is a widely used model in resolving the problem.Suppose thatI and I′ are two images of a scene, F is the fundamental matrix, and S⊂I×I′ is a set of putative point correspondences between them. The EG constraint says(1)pTFp′=0,where (p,p′)∈I×I′ is a pair of CPs and a superscript T denotes the transpose of a matrix or vector. The principle of the mismatch-rejecting methods based on EG is that the corresponding point p′ of p∈I is on a line l′=FTp in I′ and vice versa (Figure 3(a)), where l and l′ are called two epipolar lines defined by points p′ and p, respectively [3]. Therefore, if F is known, then we can reject some mismatches from S by checking whether they are consistent with the EG constraint (1) [1, 3, 4].Figure 3
Epipolar geometry (EG) constraint. (a)O1 and O2 are two camera centres, P is a scene point, I and I′ are two images of a scene, e and e′ are two epipolar points in the images, and l and l′ are two epipolar lines determined by two points p′ and p, respectively. (b) A sketch map of image I′ in (a).
(a)
(b)However, as shown in Figure3(b), if p1′∈I′ is another point on the epipolar line l′, the mismatch (p,p1′) cannot be detected by this constraint. Therefore, the EG constraint is a necessary but insufficient condition, by which the mismatches consistent with (1) cannot be detected. Unfortunately, the undue influence of these kinds of mismatches may be large enough to severely distort the final results in applications, for example, in image mosaicing and 3-dimensional reconstruction.CF is a concept recently introduced to reject mismatches from putative correspondences between images [2]. Its potential superiority has been shown experimentally on efficiency and accuracy. From the point set mapping perspective, CF depicts the relationships between corresponding points by mapping a point in one image to its corresponding point in another [2].For two images of a general scene, the relationship between some corresponding points (CPs) can be classified into three types: one-one, one-many, and many-one [2, 4]. The fundamental idea of the CF is to decompose the relationships between the CPs into two subsets. The two subsets consist of one-one and many-one, or one-one and one-many kinds of corresponding relationships. The two subsets of corresponding relationships can be described by two vector-valued functions, f:I→I′ and f′:I′→I.SupposeS={(pi,pi′),i=1,…,n}⊂I×I′ are a set of putative correspondences. CF, for example, f, can be represented by(2)fp=∑i=1nwikp,pi′,where k(·,·) is kernel function and wi=(wi1,wi2) are parameters to be estimated. Based on this representation and Gaussian kernel, Li and Hu [2] studied the estimation of CF based on Support Vector Machine.Actually, the vector-valued function interpolation/regression with similar idea has been extensively investigated for modelling the transformations between two images in scenarios of image registration and computer graphics. For example, Goshtasby [20] used a vector-valued function from a reference image to a target image for remote sensing image registration based on surface spline; Bookstein [21] studied the registration of medical images based on the thin-plate spline (TPS). Schölkopf et al. [22] proposed a machine learning method to establish dense point correspondences by estimating the deformation fields that transform two given objects into each other.In these scenarios, the focus is to transform an image into a coordinate system of another image, therefore two images to be processed are usually called a reference image and a target image, respectively, and only one vector-valued function is needed to describe the relationship from the reference image to the target image. A good review can be found in [15, 23] for the works on image registration based on this idea.Letp∈I and p′∈I′ be two image points, g(p)=f(p)-p, and y=p′-p. The CF, for example, f(p)=p′:I→I′, can be expressed by(3)y=gp,where y=p′-p. The mapping y=g(p):I→I′-I is a special expression of CF and referred to as a vector field [24, 25]. Zhao et al. [24] and Ma et al. [25] investigated the vector field learning problem using a Bayesian framework and studied its application in outlier rejection. Ma et al. [26, 27] proposed an estimation method, L2E, for the vector field and investigated its application in point set registration between images of nonrigid object; Ma et al. [28] investigated the point correspondence problem by interpolating the vector field and formulated it a maximum a posteriori (MAP) estimation of a Bayesian model with some hidden variables.In literature, related researches are usually focused on learning and application of the correspondence function or transformation function based on a flexible function. We investigate the principles and characteristics of it in this work.


## 3. Principles of Correspondence Function

SupposeI and I′ are two images to be registered. The CPs between I and I′ form a surface in the joint-image space I×I′ [17], which is illustrated schematically in Figure 1(a). In this figure, images I and I′ are illustrated as a horizontal axis and a vertical axis, respectively. And the surface is referred to as correspondence manifold (CM) in [17].In Figure1(a), (pA,pA′) is a pair of CPs between images I and I′, and A is a point in the joint-image space I×I′ formed by CPs (pA,pA′), and the other points on the curves from A to E and from F to G have similar meanings. Additionally, curves AB, CD, and FG correspond to the image points projected from the scene surface which can be distinguished by both cameras of I and I′; curves BC and DE and points {E,F} correspond to the scene portions which can only be distinguished by one camera as illustrated in Figure 4(a). The gap between E and F corresponds to the scene portion between C1 and C2 in Figure 4(b) that can be observed by one camera but not by the other one. This sketch map shows that the relationship between corresponding points can be classified into three types: one-one, one-many, and many-one. This characteristic is independent of the camera model of the images to be registered and the complexity of scene surface.Figure 4
Exception of uniqueness in correspondence problem. (a) Many points{Ai′}⊂I′ share a correspondence point A1∈I. (b) Two points A1′ and A2′ in image I′ correspond to one common point A∈I, and there are no CPs in image I for the points in (A1′,A2′)⊂I′.
(a)
(b)To highlight the mapping between CPs, we move the origin to an infinite point and connect the CPs by a dotted line; then the sketch map in Figure1(a) becomes Figure 1(b). It is well known that a function is a mapping that can depict two types of relationships—many-one and one-one—in mathematics. Therefore, the relationship between CPs is too complex to be described by a function.The fundamental idea of CF is to decompose the corresponding relationships (we name the mapping relations between CPs as “corresponding relationships”) into two directional relationships that can be depicted by two functions. For convenience, these directional relationships are referred to as “component relations” (CRs) and labeled asCRI→I′ and CRI′→I, respectively. The CR consists of one-one mapping and many-one mapping. For example, Figures 2(a) and 2(b) are a pair of CRs of Figure 1.The component relation, for example,CRI→I′, can be constructed as follows: for every point p∈I, if there is a unique corresponding point p′∈I′, the corresponding relationship (p,p′) should be one member of CRI→I′. Otherwise, if p has more than one corresponding point {p1′,…,pk′}k>0∈I′, we have two choices: either ignore all of the corresponding relationships {(p,pi),1≤i≤k} or select any one of the CPs pi0′, insert (p,pi0′) into CRI′→I, and ignore the other corresponding relationships {(p,pi),1≤i≤k,i≠i0}. Component relation CRI′→I can be constructed similarly by checking every potential point p′∈I′. For example, in Figures 1 and 2, point pA∈I has a unique corresponding point pA′ in I′; therefore the corresponding relationship (pA,pA′) is in component relation CRI→I′. In particular, the corresponding point of pD∈I is also unique in I′. Therefore, (pD,pDE′) is one member of the component relation CRI→I′ even though the CPs of pDE′ are not unique in image I.Therefore,CRI→I′ is a one-to-one or many-to-one mapping from I to I′ and can be depicted by a vector-valued function f:I→I′. Similarly, CRI′→I is also a one-to-one or many-to-one mapping from I′ to I and can be depicted by a vector-valued function f′:I′→I.On the other hand, for any given corresponding point pair(p,p′)∈I×I′, if it is of the one-one type, the corresponding relationship expressed by it can be depicted not only by a function from I to I′ but also by a function from I′ to I. Therefore the corresponding relationships of the one-one type can be found in both CRI→I′ and CRI′→I, such as the corresponding point pair (pA,pA′) in Figures 1(b), 2(a), and 2(b). Otherwise, if one given corresponding point pair (p,p′)∈I×I′ is of the many-one type, p has a unique corresponding image (If (p,p′) are a pair of CPs, p is called the corresponding image of p′ and vice versa.) in I′ based on the definition of CPs of the many-one type. Therefore, the corresponding relationships of the many-one type can also be depicted by a function mapping and are members of CRI→I′, like the corresponding point pairs {(pD,pDE′),…,(pEF,pDE′)} in Figures 1(b) and 2(a). Similarly, the corresponding relationships of one-many can be depicted by a function mapping from I′ to I and are members of CRI′→I, such as the CPs {(pBC,pB′),…,(pBC,pC′)} in Figures 1(b) and 2(b).In conclusion, for a pair of imagesI and I′ to be registered of a scene, the relationships between CPs can be decomposed into a pair of component relations CRI→I′ and CRI′→I, which consist of a number of one-to-one and many-to-one mappings. The CRI→I′ and CRI′→I can be described by a pair of vector-valued functions as f:I→I′ and f′:I′→I. The (f,f′) are named as correspondence functions (CFs) in [2].In image registration,I and I′ are referred to as a reference image and a target image, respectively; the objective is to transform the target image into the coordinate system of the reference image. Therefore, only one vector-valued function, for example, f:I→I′, is needed to describe the corresponding relationship and named transformation function in [23].Therefore, CF is a pair of functions(f,f′) demonstrating that, for any one pair of CPs p∈I and p′∈I′, (p,p′) are consistent with at least one of two functions f or f′, which can be estimated from a given set of putative correspondences based on robust regression method [2]. Also, for any given point p∈I, its corresponding point can be uniquely estimated by the CF and vice versa (Figure 2).In practice, putative correspondences are usually corrupted by noise and outliers, and the number of putative correspondences is limited. Therefore, only an estimation of CF with a certain accuracy can be estimated, and the actual results may be not strictly consistent with the “necessary and sufficient condition.”Therefore, the characteristic is that CF model can reduce the searching space of CPs into an elliptical area and the mismatches of CF are usually near the correct CPs (Section5).


## 4. Learning of CF and Its Application in Mismatch Rejection

Based on the discussions in Section3, for a pair of images I1 and I2 of a scene, the relationship of some corresponding points between I1 and I2 can be decomposed into a pair of component relations (CRs): CRI→I′ and CRI′→I. A CR consists of one-one mapping and many-one mapping.Therefore,CRI→I′ and CRI′→I can be described by two vector-valued functions, f:I→I′ and f′:I′→I:(4)fp=p′,f′p′=p,where p∈I, p′∈I′, and (f,f′) are referred to as a pair of correspondence functions (CFs).SupposeS={(p,p′),p∈I,p′∈I′} is a set of putative correspondences between I1 and I2. If we treat y=p′ as an output of a system and x=p as an input, the CF f can be estimated from S={(x,y)=(p,p′),p∈I,p′∈I′} using a vector-valued regression method, for example, vector field consensus (VFC) method [24, 28] and IECF (Iteratively Estimate Correspondence Function) algorithm [2]. The fundamental ideas of VFC and IECF are as follows: approximately represent the unknown CF f as a weighted sum of kernel functions (2) and estimate the weights iteratively by gradually reducing the undue effects from outliers. The objective of this work is to investigate the fundamental principles and characteristics of CF. Therefore, we do not compare the various implementation of CF and do experiments by IECF. The CF f′ can be estimated similarly.Theoretically, the correctness of a pair of putative correspondences(p,p′) can be determined by checking whether it is consistent with one of the estimated correspondence functions f^ or f^′. However, due to the influence of image noise, the observed corresponding points usually are not strictly consistent with the estimated CFs f^ and f^′ and a tolerance parameter αI is needed to determine whether they are consistent. It is shown that the consistency of (p,p′) with f^ can be determined by(5)cfp,p′=f^p-p′Σ-1f^p-p′T,where the superscript T represents a transpose of a vector and Σ is the covariance matrix of random variable f^(p)-p′ and can be estimated using IECF algorithm [2]. The consistency of (p,p′) with f^′ is measured similarly and denoted by cf′(p,p′). Then, some mismatches can be rejected by the constraints cf(p,p′)>αI and cf′(p,p′)>αI.Similarly, a tolerance parameterαR is also needed to reject mismatches by the EG constraint (1):(6)pTFp′>αR.


## 5. Experimental Research

In this section, we experimentally investigate the characteristics of the CF by comparing it with the widely used parametric model epipolar geometry (EG) ((1), Figure 3) in the context of rejecting mismatches.


### 5.1. Experimental Configuration

The mismatch-rejecting methods based on CF and EG are implemented by algorithms ICF (identifying point correspondences by correspondence function) [2] and RANSAC (Random Sample Consensus) [11, 29, 30], respectively, in this study. Since the coordinates of the observed putative CPs are usually corrupted by noise, they are not strictly consistent with the CF and EG equations. Therefore, two tolerance parameters are needed for the computation; we name the two parameters αR in EG + RANSAC and αI in CF + ICF.In evaluating the performance of local descriptors and points matching models, there are several schemes, for example, recall, precision [31], and ROC curve [14]. However, the objective of this work’s experiments is to show the characteristic of fail-detected mismatches of CF. Therefore, to make a fair comparison, we adjusted the values of αR and αI such that a same number of putative correspondences are identified as possible correct matches in every experiment and the RANSAC are implemented without a limit on iteration number.SupposeI and I′ are two images of a scene to be matched and suppose S is a set of putative correspondences between them. A mismatch-rejecting method will partition S into two subsets, Sc and Sm, as possible correct correspondences and possible mismatches. For readability, we denote the two subsets by ScEG and SmEG in the method based on EG constraint and ScCF and SmCF in the method based on CF. Thus, set S can be divided into four subsets, ScEG∩ScCF, S¯cEG∩ScCF, ScEG∩S¯cCF, and S¯cEG∩S¯cCF, where S¯cEG=S-ScEG=SmEG and S¯cCF=S-ScCF=SmCF. The meanings of the above four subsets are as follows:(1)
ScEG∩ScCF=S¯mEG∩S¯mCF: the putative correspondences that are regarded as possible correct matches by the methods based on EG and CF.(2)
S¯cEG∩ScCF=SmEG∩S¯mCF: the putative correspondences that are regarded as possible mismatches by EG method and possible correct matches by CF.(3)
ScEG∩S¯cCF=S¯mEG∩SmCF: the putative correspondences that are regarded as possible correct matches by the EG method and possible mismatches by CF.(4)
S¯cEG∩S¯cCF=SmEG∩SmCF: the putative correspondences that are regarded as possible mismatches by the methods based on EG and CF.On subsets ScEG∩ScCF and S¯cEG∩S¯cCF, the two methods based on CF and EG constraint are consistent. Therefore, it is sufficient to focus on ScEG∩S¯cCF and S¯cEG∩ScCF to compare the CF model and the EG constraint.For convenience in comparing the results of EG and CF, we manually removed some of the correct and near-correct putative correspondences fromScEG∩S¯cCF and S¯cEG∩ScCF in some experiments, and the two sets composed of the remaining putative correspondences are denoted by T(ScEG∩S¯cCF) and T(S¯cEG∩ScCF), respectively:(i)
T(ScEG∩S¯cCF): the typical putative correspondences that are classified as possible correct matches by EG and as possible mismatches by CF.(ii)
T(S¯cEG∩ScCF): the typical putative correspondences that are classified as possible mismatches by EG and as possible correct correspondences by CF.


### 5.2. Experiments

#### 5.2.1. Main Results

One of the used image pairs is presented in Figure5. There are 1278 and 1207 SIFT feature points extracted from two images, respectively (the feature points are detected by the multiscale DoG (Difference of Gaussian) scheme and described by the orientation histogram technique [32]), and 448 putative correspondences computed from the feature points by the NNDR (Nearest Neighbor and Distance Ratio) method [32]. Due to the ambiguity of local information, some of the putative correspondences are incorrect and need to be rejected. In this experiment, the two methods based on EG and CF are inconsistent on 52 putative correspondences (Figures 5(a) and 5(b)). For example, for every putative correspondence (p,p′) in Figure 5(a), the CF method identified it as a possible correct match, but the EG method identified it as a possible mismatch. Therefore, based on the definition of S¯cEG∩ScCF and ScEG∩S¯cCF, we can regard ScEG∩S¯cCF as a set of potential mismatches that the EG constraint fails to detect and S¯cEG∩ScCF as a set of potential mismatches that the CF model fails to reject. More results are presented in Figures 6, 7, and 8.Figure 5
An image pair of a toy bear. (a) 26 EG potential mismatches (PMs) that are accepted by CF as matches; (b) 26 CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=10.597 and αR=0.00019.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)Figure 6
An image pair of a corridor. (a) 25 EG PMs that are accepted by CF as matches; (b) 25 CF PMs that are accepted by EG as matches; (c) 31 EG PMs that are accepted by CF as matches; (d) 31 CF PMs that are accepted by EG as matches. In (a)-(b),αI=5.991 and αR=0.00048 and in (c)-(d), αI=110 and αR=0.05.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 7
An image pair of Baxia. (a) Some EG PMs that are accepted by CF as matches; (b) some CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=10.597 and αR=0.05.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)Figure 8
An image pair of temple Fayu. (a) 204 EG PMs that are accepted by CF as matches; (b) 204 CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=3.1 and αR=0.0001515 (for visibility, only 100 randomly chosen PMs are presented in (a) and (b)).
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)


#### 5.2.2. Comparing the CF and EG Constraint by Analyzing the Undetected Mismatches

For ease of explanation, we introduce the following two definitions: type-I mismatches and type-II mismatches. Suppose(p¯,p¯′) is a mismatch. If there exists a correct corresponding point pair (p,p′) satisfying that the points p¯ and p¯′ are in the neighborhood of p and p′, respectively, then (p¯,p¯′) is defined as a mismatch of type-I. Otherwise, we call (p¯,p¯′) a type-II mismatch. For example, the mismatches in Figure 7(d) and (p,p3′) in Figure 3(b) belong to type-II and (p,p2′) in Figure 3(b) belong to type-I. By the EG constraint, we can only determine whether a putative correspondence is in a band around the epipolar line (Figures 3(b), 9(b), and 9(d)) but not whether it is close to the correct one. Therefore, the undetected mismatches usually belong to type-II in the methods based on the EG constraint (Figures 3, 5(b), 5(d), 6(b), 6(d), 7(b), 7(d), 8(b), and 8(d)). The CF constraint determines the mapping relationships between two CPs and directly estimates the position of the corresponding point. Therefore, by the mismatch-rejecting methods based on CF, we can restrict the error bound of the putative correspondences by a tolerance parameter αI; the undetected mismatches by CF usually belong to type-I. To show the difference between the CF model and EG constraints, a typical result is presented in Figure 6, in which we relax the tolerance parameters αI and αR to ensure the two sets S¯cEG∩ScCF and ScEG∩S¯cCF change at equal speed.Figure 9
Some PMs and their corresponding epipolar lines. The EG model cannot detect the mismatches that are near the epipolar line but far from the correct CPs. The undetected mismatches by CF are usually near both the correct CPs and the epipolar line. (a) and (c) present the EG PMs that are accepted by CF as matches in the experiments of Figures7(c) and 8(c), respectively; (b) and (d) present the CF PMs that are accepted by EG as matches in the experiments of Figures 7(d) and 8(d), respectively. In these experiments, (pi,pi′) is a pair of putative CPs, and li is the epipolar line corresponding to pi′ and li′ is the epipolar line corresponding to pi.
(a)
(b)
(c)
(d)However, the mismatches of type-I and type-II are usually dramatically different from each other in usefulness and undue influence. From the mismatches of type-I, we can search for the correct CPs by including more information. On the contrary, other than ruining the traditional estimation methods and distorting the final application results (e.g., image mosaicing and three-dimensional reconstruction), the mismatches of the type-II provide less useful information.


### 5.3. Further Evaluation on Some Popular Benchmark Data

The characteristics of the CF are also investigated on two series of popular benchmark data sets widely used to compare and evaluate related algorithms [33, 34].To evaluate the two schemes quantitatively, this work conducted experiments on a series of image sets with ground-truth correspondences [31, 35]. The images were captured under special consideration to enable the encoding of the ground-truth correspondences with homographies between the reference image and other images. The ground-truth homographies are computed based on the following steps: first, a set of putative correspondences are manually selected and an initial estimation of the homography is computed based on the selected putative correspondences; second, the images are approximately aligned with the rough estimation of homography; third, reliable interest points are detected and matched automatically and an accurate homography is computed from them.The experimental results are presented in Figures11, 12, 13, and 14. In every experiment, the upper image and the lower image are called the reference image and the target image, respectively. In addition to the computed putative correspondences, we also present the ground-truth CPs and ground-truth correspondence relationships in these experiments. The ground-truth CPs in the target images are computed for all of the marked interest points in reference images based on the ground-truth homographies and denoted by red circles. The detected interest points are denoted by black plus signs. The ground-truth correspondence relationships are displayed as blue dashed lines and the computed putative correspondence relationships are shown by a solid line with red or green for visibility.Suppose thatS={(p1,p1′),…,(pn,pn′)} are a set of putative correspondences and S¯={(p1,p¯1′),…,(pn,p¯n′)} are the ground-truth correspondences of S. We quantitatively evaluate the quality of S by the root-mean-square deviation (RMSD) RMSD(S)=∑i=1npi′-p¯i′T∗(pi′-p¯i′)/n.The second series of evaluation data are the Middlebury Stereo Datasets [36, 37] (http://vision.middlebury.edu/stereo/data/).  These data sets were created using an automated version of structured-lighting technique [38]. Each dataset consists of seven rectified views. This work used the first and the fifth views for evaluation. The experimental results are presented in Figures 15, 16, 17, 18, and 19.


### 5.4. CF and EG in Practice

#### 5.4.1. Necessity and Sufficiency

As analyzed, the EG constraint is a necessary but insufficient condition in the correspondence problem, and the CF model describes the mapping between CPs directly. However, in applications, some correct CPs may be inconsistent with the estimated EG model and/or the estimated CF model; there may be some mismatches that are “consistent” with the estimated CF model; there also may be some of the putative correspondences which are “consistent” with the estimated CF but “inconsistent” with the estimated EG, for example, the experimental results in Figures5(a), 5(b), 7(a), 7(b), 8(a), and 8(b). The reasons for the above results are as follows:(i)
The coordinates of the obtained putative CPs are usually corrupted by noise.(ii)
There are usually some errors in the estimation of the CF and EG.(iii)
As pointed out in the first paragraph of Section5, a preset tolerance parameter is needed to define the “consistent” and “inconsistent” in the applications of CF and EG. However, the noise in the obtained putative CPs is random.


#### 5.4.2. Characteristics and Limitations of the CF Model and EG Model

In the two models, there are no restrictions on the depth range of the imaged scene. However, the EG is a global describing model, and the CF is a local describing model. In the EG model, any pair of putative CPs can influence the overall model estimation, whereas in the CF model, a pair of putative CPs only influence the model estimation within a local area in their vicinity. The shortcoming of the global model EG is that the overall model estimation can be degraded or ruined by PCs with considerable noise or mismatches in any area of the images. The shortcoming of the local model CF is that a pair of good CPs cannot improve the estimation of CF outside of a local area around itself. Thus, the uneven distribution of putative correspondences with different quality results in the fact that the estimated CF may be of high quality in some areas but of low quality in others; for example, in the experiment of Figure10, the qualities of the CF estimations over the second-nearest-to-the-cameras crossbeam and the third-nearest-to-the-cameras crossbeam are better than estimation over the first-nearest-to-the-cameras crossbeam. The “local area” is determined by the CF estimation method and its chosen parameters; for example, in the CF estimation method SP (SVM) [2], the local area is determined by the chosen kernel and the scale parameter. The above limitations of EG and CF can be alleviated by investigating robust estimation methods, for example, the RANSAC, M-estimators [8], LMedS (Least Median of Squares) [9], and MLESAC [10, 12] for EG. In future work, we will investigate further the estimation method for CF to improve its robustness.Figure 10
The possible correct correspondences identified by CF in the experiment of Figure8 are presented based on depth. (a) 34 putative correspondences (PCs) over the first crossbeam; (b) 324 PCs over the second crossbeam; (c) 214 PCs over the third crossbeam; (d) 20 PCs around the fourth crossbeam; (e) 2 PCs on the wall (for clarity, only 50 randomly chosen PCs are presented in (b) and (c)).
(a)
(b)
(c)
(d)
(e)Figure 11
Quantitative evaluation on two popular benchmark sets: bikes and leuven. The ground-truth CPs are presented by red circles, the detected interest points by black plus signs. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a solid green solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=2.1435×10-5 in (b), and αR=5.8×10-5 in (d).
(a)
RMSD = 13.86
(b)
RMSD = 227.07
(c)
RMSD = 3.84
(d)
RMSD = 236.26Figure 12
Quantitative evaluation on two popular benchmark sets: wall and bark. ((a) and (c)) The EG PMs that are accepted by CF as matches; ((b) and (d)) the CF PMs that are accepted by EG as matches.αI=10.597, αR=2.029×10-4 in (b), and αR=1.05×10-4 in (d).
(a)
RMSD = 16.31
(b)
RMSD = 400.98
(c)
RMSD = 3.58
(d)
RMSD = 322.88Figure 13
Quantitative evaluation on two popular benchmark sets: graf and boat. The ground-truth CPs are presented by red circles and the detected interest points by black plus signs. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a solid green solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=5×10-4 in (b), and αR=7.7×10-5 in (d).
(a)
RMSD = 10.17
(b)
RMSD = 426.39
(c)
RMSD = 3.29
(d)
RMSD = 176.46Figure 14
Quantitative evaluation on two popular benchmark sets: trees and ubc. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a yellow solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=5.9×10-5 in (b), and αR=1.85×10-4 in (d).
(a)
RMSD = 4.41
(b)
RMSD = 331.09
(c)
RMSD = 1.57
(d)
RMSD = 117.28Figure 15
Evaluation on Middlebury Stereo Datasets: art and books. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.013 in (a) and (b), αR=0.00018 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 16
Evaluation on Middlebury Stereo Datasets: computer and dolls. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.00018 in (a) and (b), αR=0.00048 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 17
Evaluation on Middlebury Stereo Datasets: drumsticks and dwarves. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.00078 in (a) and (b), αR=0.0035 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 18
Evaluation on Middlebury Stereo Datasets: laundry and moebius. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.0.0000275 in (a) and (b), αR=0.00035 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 19
Evaluation on Middlebury Stereo Dataset: reindeer. (a) Two potential EG mismatches that are accepted by CF as matches; (b) two potential CF mismatches that are accepted by EG as matches.αR=0.005 and αI=30.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF


## 5.1. Experimental Configuration

The mismatch-rejecting methods based on CF and EG are implemented by algorithms ICF (identifying point correspondences by correspondence function) [2] and RANSAC (Random Sample Consensus) [11, 29, 30], respectively, in this study. Since the coordinates of the observed putative CPs are usually corrupted by noise, they are not strictly consistent with the CF and EG equations. Therefore, two tolerance parameters are needed for the computation; we name the two parameters αR in EG + RANSAC and αI in CF + ICF.In evaluating the performance of local descriptors and points matching models, there are several schemes, for example, recall, precision [31], and ROC curve [14]. However, the objective of this work’s experiments is to show the characteristic of fail-detected mismatches of CF. Therefore, to make a fair comparison, we adjusted the values of αR and αI such that a same number of putative correspondences are identified as possible correct matches in every experiment and the RANSAC are implemented without a limit on iteration number.SupposeI and I′ are two images of a scene to be matched and suppose S is a set of putative correspondences between them. A mismatch-rejecting method will partition S into two subsets, Sc and Sm, as possible correct correspondences and possible mismatches. For readability, we denote the two subsets by ScEG and SmEG in the method based on EG constraint and ScCF and SmCF in the method based on CF. Thus, set S can be divided into four subsets, ScEG∩ScCF, S¯cEG∩ScCF, ScEG∩S¯cCF, and S¯cEG∩S¯cCF, where S¯cEG=S-ScEG=SmEG and S¯cCF=S-ScCF=SmCF. The meanings of the above four subsets are as follows:(1)
ScEG∩ScCF=S¯mEG∩S¯mCF: the putative correspondences that are regarded as possible correct matches by the methods based on EG and CF.(2)
S¯cEG∩ScCF=SmEG∩S¯mCF: the putative correspondences that are regarded as possible mismatches by EG method and possible correct matches by CF.(3)
ScEG∩S¯cCF=S¯mEG∩SmCF: the putative correspondences that are regarded as possible correct matches by the EG method and possible mismatches by CF.(4)
S¯cEG∩S¯cCF=SmEG∩SmCF: the putative correspondences that are regarded as possible mismatches by the methods based on EG and CF.On subsets ScEG∩ScCF and S¯cEG∩S¯cCF, the two methods based on CF and EG constraint are consistent. Therefore, it is sufficient to focus on ScEG∩S¯cCF and S¯cEG∩ScCF to compare the CF model and the EG constraint.For convenience in comparing the results of EG and CF, we manually removed some of the correct and near-correct putative correspondences fromScEG∩S¯cCF and S¯cEG∩ScCF in some experiments, and the two sets composed of the remaining putative correspondences are denoted by T(ScEG∩S¯cCF) and T(S¯cEG∩ScCF), respectively:(i)
T(ScEG∩S¯cCF): the typical putative correspondences that are classified as possible correct matches by EG and as possible mismatches by CF.(ii)
T(S¯cEG∩ScCF): the typical putative correspondences that are classified as possible mismatches by EG and as possible correct correspondences by CF.


## 5.2. Experiments

### 5.2.1. Main Results

One of the used image pairs is presented in Figure5. There are 1278 and 1207 SIFT feature points extracted from two images, respectively (the feature points are detected by the multiscale DoG (Difference of Gaussian) scheme and described by the orientation histogram technique [32]), and 448 putative correspondences computed from the feature points by the NNDR (Nearest Neighbor and Distance Ratio) method [32]. Due to the ambiguity of local information, some of the putative correspondences are incorrect and need to be rejected. In this experiment, the two methods based on EG and CF are inconsistent on 52 putative correspondences (Figures 5(a) and 5(b)). For example, for every putative correspondence (p,p′) in Figure 5(a), the CF method identified it as a possible correct match, but the EG method identified it as a possible mismatch. Therefore, based on the definition of S¯cEG∩ScCF and ScEG∩S¯cCF, we can regard ScEG∩S¯cCF as a set of potential mismatches that the EG constraint fails to detect and S¯cEG∩ScCF as a set of potential mismatches that the CF model fails to reject. More results are presented in Figures 6, 7, and 8.Figure 5
An image pair of a toy bear. (a) 26 EG potential mismatches (PMs) that are accepted by CF as matches; (b) 26 CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=10.597 and αR=0.00019.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)Figure 6
An image pair of a corridor. (a) 25 EG PMs that are accepted by CF as matches; (b) 25 CF PMs that are accepted by EG as matches; (c) 31 EG PMs that are accepted by CF as matches; (d) 31 CF PMs that are accepted by EG as matches. In (a)-(b),αI=5.991 and αR=0.00048 and in (c)-(d), αI=110 and αR=0.05.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 7
An image pair of Baxia. (a) Some EG PMs that are accepted by CF as matches; (b) some CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=10.597 and αR=0.05.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)Figure 8
An image pair of temple Fayu. (a) 204 EG PMs that are accepted by CF as matches; (b) 204 CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=3.1 and αR=0.0001515 (for visibility, only 100 randomly chosen PMs are presented in (a) and (b)).
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)


### 5.2.2. Comparing the CF and EG Constraint by Analyzing the Undetected Mismatches

For ease of explanation, we introduce the following two definitions: type-I mismatches and type-II mismatches. Suppose(p¯,p¯′) is a mismatch. If there exists a correct corresponding point pair (p,p′) satisfying that the points p¯ and p¯′ are in the neighborhood of p and p′, respectively, then (p¯,p¯′) is defined as a mismatch of type-I. Otherwise, we call (p¯,p¯′) a type-II mismatch. For example, the mismatches in Figure 7(d) and (p,p3′) in Figure 3(b) belong to type-II and (p,p2′) in Figure 3(b) belong to type-I. By the EG constraint, we can only determine whether a putative correspondence is in a band around the epipolar line (Figures 3(b), 9(b), and 9(d)) but not whether it is close to the correct one. Therefore, the undetected mismatches usually belong to type-II in the methods based on the EG constraint (Figures 3, 5(b), 5(d), 6(b), 6(d), 7(b), 7(d), 8(b), and 8(d)). The CF constraint determines the mapping relationships between two CPs and directly estimates the position of the corresponding point. Therefore, by the mismatch-rejecting methods based on CF, we can restrict the error bound of the putative correspondences by a tolerance parameter αI; the undetected mismatches by CF usually belong to type-I. To show the difference between the CF model and EG constraints, a typical result is presented in Figure 6, in which we relax the tolerance parameters αI and αR to ensure the two sets S¯cEG∩ScCF and ScEG∩S¯cCF change at equal speed.Figure 9
Some PMs and their corresponding epipolar lines. The EG model cannot detect the mismatches that are near the epipolar line but far from the correct CPs. The undetected mismatches by CF are usually near both the correct CPs and the epipolar line. (a) and (c) present the EG PMs that are accepted by CF as matches in the experiments of Figures7(c) and 8(c), respectively; (b) and (d) present the CF PMs that are accepted by EG as matches in the experiments of Figures 7(d) and 8(d), respectively. In these experiments, (pi,pi′) is a pair of putative CPs, and li is the epipolar line corresponding to pi′ and li′ is the epipolar line corresponding to pi.
(a)
(b)
(c)
(d)However, the mismatches of type-I and type-II are usually dramatically different from each other in usefulness and undue influence. From the mismatches of type-I, we can search for the correct CPs by including more information. On the contrary, other than ruining the traditional estimation methods and distorting the final application results (e.g., image mosaicing and three-dimensional reconstruction), the mismatches of the type-II provide less useful information.


## 5.2.1. Main Results

One of the used image pairs is presented in Figure5. There are 1278 and 1207 SIFT feature points extracted from two images, respectively (the feature points are detected by the multiscale DoG (Difference of Gaussian) scheme and described by the orientation histogram technique [32]), and 448 putative correspondences computed from the feature points by the NNDR (Nearest Neighbor and Distance Ratio) method [32]. Due to the ambiguity of local information, some of the putative correspondences are incorrect and need to be rejected. In this experiment, the two methods based on EG and CF are inconsistent on 52 putative correspondences (Figures 5(a) and 5(b)). For example, for every putative correspondence (p,p′) in Figure 5(a), the CF method identified it as a possible correct match, but the EG method identified it as a possible mismatch. Therefore, based on the definition of S¯cEG∩ScCF and ScEG∩S¯cCF, we can regard ScEG∩S¯cCF as a set of potential mismatches that the EG constraint fails to detect and S¯cEG∩ScCF as a set of potential mismatches that the CF model fails to reject. More results are presented in Figures 6, 7, and 8.Figure 5
An image pair of a toy bear. (a) 26 EG potential mismatches (PMs) that are accepted by CF as matches; (b) 26 CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=10.597 and αR=0.00019.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)Figure 6
An image pair of a corridor. (a) 25 EG PMs that are accepted by CF as matches; (b) 25 CF PMs that are accepted by EG as matches; (c) 31 EG PMs that are accepted by CF as matches; (d) 31 CF PMs that are accepted by EG as matches. In (a)-(b),αI=5.991 and αR=0.00048 and in (c)-(d), αI=110 and αR=0.05.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 7
An image pair of Baxia. (a) Some EG PMs that are accepted by CF as matches; (b) some CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=10.597 and αR=0.05.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)Figure 8
An image pair of temple Fayu. (a) 204 EG PMs that are accepted by CF as matches; (b) 204 CF PMs that are accepted by EG as matches; (c) some typical EG PMs that are accepted by CF; (d) some typical CF PMs that are accepted by EG.αI=3.1 and αR=0.0001515 (for visibility, only 100 randomly chosen PMs are presented in (a) and (b)).
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
T
(
S
¯
c
EG
∩
S
c
CF
)
(d)
T
(
S
c
EG
∩
S
¯
c
CF
)


## 5.2.2. Comparing the CF and EG Constraint by Analyzing the Undetected Mismatches

For ease of explanation, we introduce the following two definitions: type-I mismatches and type-II mismatches. Suppose(p¯,p¯′) is a mismatch. If there exists a correct corresponding point pair (p,p′) satisfying that the points p¯ and p¯′ are in the neighborhood of p and p′, respectively, then (p¯,p¯′) is defined as a mismatch of type-I. Otherwise, we call (p¯,p¯′) a type-II mismatch. For example, the mismatches in Figure 7(d) and (p,p3′) in Figure 3(b) belong to type-II and (p,p2′) in Figure 3(b) belong to type-I. By the EG constraint, we can only determine whether a putative correspondence is in a band around the epipolar line (Figures 3(b), 9(b), and 9(d)) but not whether it is close to the correct one. Therefore, the undetected mismatches usually belong to type-II in the methods based on the EG constraint (Figures 3, 5(b), 5(d), 6(b), 6(d), 7(b), 7(d), 8(b), and 8(d)). The CF constraint determines the mapping relationships between two CPs and directly estimates the position of the corresponding point. Therefore, by the mismatch-rejecting methods based on CF, we can restrict the error bound of the putative correspondences by a tolerance parameter αI; the undetected mismatches by CF usually belong to type-I. To show the difference between the CF model and EG constraints, a typical result is presented in Figure 6, in which we relax the tolerance parameters αI and αR to ensure the two sets S¯cEG∩ScCF and ScEG∩S¯cCF change at equal speed.Figure 9
Some PMs and their corresponding epipolar lines. The EG model cannot detect the mismatches that are near the epipolar line but far from the correct CPs. The undetected mismatches by CF are usually near both the correct CPs and the epipolar line. (a) and (c) present the EG PMs that are accepted by CF as matches in the experiments of Figures7(c) and 8(c), respectively; (b) and (d) present the CF PMs that are accepted by EG as matches in the experiments of Figures 7(d) and 8(d), respectively. In these experiments, (pi,pi′) is a pair of putative CPs, and li is the epipolar line corresponding to pi′ and li′ is the epipolar line corresponding to pi.
(a)
(b)
(c)
(d)However, the mismatches of type-I and type-II are usually dramatically different from each other in usefulness and undue influence. From the mismatches of type-I, we can search for the correct CPs by including more information. On the contrary, other than ruining the traditional estimation methods and distorting the final application results (e.g., image mosaicing and three-dimensional reconstruction), the mismatches of the type-II provide less useful information.


## 5.3. Further Evaluation on Some Popular Benchmark Data

The characteristics of the CF are also investigated on two series of popular benchmark data sets widely used to compare and evaluate related algorithms [33, 34].To evaluate the two schemes quantitatively, this work conducted experiments on a series of image sets with ground-truth correspondences [31, 35]. The images were captured under special consideration to enable the encoding of the ground-truth correspondences with homographies between the reference image and other images. The ground-truth homographies are computed based on the following steps: first, a set of putative correspondences are manually selected and an initial estimation of the homography is computed based on the selected putative correspondences; second, the images are approximately aligned with the rough estimation of homography; third, reliable interest points are detected and matched automatically and an accurate homography is computed from them.The experimental results are presented in Figures11, 12, 13, and 14. In every experiment, the upper image and the lower image are called the reference image and the target image, respectively. In addition to the computed putative correspondences, we also present the ground-truth CPs and ground-truth correspondence relationships in these experiments. The ground-truth CPs in the target images are computed for all of the marked interest points in reference images based on the ground-truth homographies and denoted by red circles. The detected interest points are denoted by black plus signs. The ground-truth correspondence relationships are displayed as blue dashed lines and the computed putative correspondence relationships are shown by a solid line with red or green for visibility.Suppose thatS={(p1,p1′),…,(pn,pn′)} are a set of putative correspondences and S¯={(p1,p¯1′),…,(pn,p¯n′)} are the ground-truth correspondences of S. We quantitatively evaluate the quality of S by the root-mean-square deviation (RMSD) RMSD(S)=∑i=1npi′-p¯i′T∗(pi′-p¯i′)/n.The second series of evaluation data are the Middlebury Stereo Datasets [36, 37] (http://vision.middlebury.edu/stereo/data/).  These data sets were created using an automated version of structured-lighting technique [38]. Each dataset consists of seven rectified views. This work used the first and the fifth views for evaluation. The experimental results are presented in Figures 15, 16, 17, 18, and 19.


## 5.4. CF and EG in Practice

### 5.4.1. Necessity and Sufficiency

As analyzed, the EG constraint is a necessary but insufficient condition in the correspondence problem, and the CF model describes the mapping between CPs directly. However, in applications, some correct CPs may be inconsistent with the estimated EG model and/or the estimated CF model; there may be some mismatches that are “consistent” with the estimated CF model; there also may be some of the putative correspondences which are “consistent” with the estimated CF but “inconsistent” with the estimated EG, for example, the experimental results in Figures5(a), 5(b), 7(a), 7(b), 8(a), and 8(b). The reasons for the above results are as follows:(i)
The coordinates of the obtained putative CPs are usually corrupted by noise.(ii)
There are usually some errors in the estimation of the CF and EG.(iii)
As pointed out in the first paragraph of Section5, a preset tolerance parameter is needed to define the “consistent” and “inconsistent” in the applications of CF and EG. However, the noise in the obtained putative CPs is random.


### 5.4.2. Characteristics and Limitations of the CF Model and EG Model

In the two models, there are no restrictions on the depth range of the imaged scene. However, the EG is a global describing model, and the CF is a local describing model. In the EG model, any pair of putative CPs can influence the overall model estimation, whereas in the CF model, a pair of putative CPs only influence the model estimation within a local area in their vicinity. The shortcoming of the global model EG is that the overall model estimation can be degraded or ruined by PCs with considerable noise or mismatches in any area of the images. The shortcoming of the local model CF is that a pair of good CPs cannot improve the estimation of CF outside of a local area around itself. Thus, the uneven distribution of putative correspondences with different quality results in the fact that the estimated CF may be of high quality in some areas but of low quality in others; for example, in the experiment of Figure10, the qualities of the CF estimations over the second-nearest-to-the-cameras crossbeam and the third-nearest-to-the-cameras crossbeam are better than estimation over the first-nearest-to-the-cameras crossbeam. The “local area” is determined by the CF estimation method and its chosen parameters; for example, in the CF estimation method SP (SVM) [2], the local area is determined by the chosen kernel and the scale parameter. The above limitations of EG and CF can be alleviated by investigating robust estimation methods, for example, the RANSAC, M-estimators [8], LMedS (Least Median of Squares) [9], and MLESAC [10, 12] for EG. In future work, we will investigate further the estimation method for CF to improve its robustness.Figure 10
The possible correct correspondences identified by CF in the experiment of Figure8 are presented based on depth. (a) 34 putative correspondences (PCs) over the first crossbeam; (b) 324 PCs over the second crossbeam; (c) 214 PCs over the third crossbeam; (d) 20 PCs around the fourth crossbeam; (e) 2 PCs on the wall (for clarity, only 50 randomly chosen PCs are presented in (b) and (c)).
(a)
(b)
(c)
(d)
(e)Figure 11
Quantitative evaluation on two popular benchmark sets: bikes and leuven. The ground-truth CPs are presented by red circles, the detected interest points by black plus signs. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a solid green solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=2.1435×10-5 in (b), and αR=5.8×10-5 in (d).
(a)
RMSD = 13.86
(b)
RMSD = 227.07
(c)
RMSD = 3.84
(d)
RMSD = 236.26Figure 12
Quantitative evaluation on two popular benchmark sets: wall and bark. ((a) and (c)) The EG PMs that are accepted by CF as matches; ((b) and (d)) the CF PMs that are accepted by EG as matches.αI=10.597, αR=2.029×10-4 in (b), and αR=1.05×10-4 in (d).
(a)
RMSD = 16.31
(b)
RMSD = 400.98
(c)
RMSD = 3.58
(d)
RMSD = 322.88Figure 13
Quantitative evaluation on two popular benchmark sets: graf and boat. The ground-truth CPs are presented by red circles and the detected interest points by black plus signs. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a solid green solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=5×10-4 in (b), and αR=7.7×10-5 in (d).
(a)
RMSD = 10.17
(b)
RMSD = 426.39
(c)
RMSD = 3.29
(d)
RMSD = 176.46Figure 14
Quantitative evaluation on two popular benchmark sets: trees and ubc. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a yellow solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=5.9×10-5 in (b), and αR=1.85×10-4 in (d).
(a)
RMSD = 4.41
(b)
RMSD = 331.09
(c)
RMSD = 1.57
(d)
RMSD = 117.28Figure 15
Evaluation on Middlebury Stereo Datasets: art and books. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.013 in (a) and (b), αR=0.00018 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 16
Evaluation on Middlebury Stereo Datasets: computer and dolls. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.00018 in (a) and (b), αR=0.00048 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 17
Evaluation on Middlebury Stereo Datasets: drumsticks and dwarves. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.00078 in (a) and (b), αR=0.0035 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 18
Evaluation on Middlebury Stereo Datasets: laundry and moebius. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.0.0000275 in (a) and (b), αR=0.00035 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 19
Evaluation on Middlebury Stereo Dataset: reindeer. (a) Two potential EG mismatches that are accepted by CF as matches; (b) two potential CF mismatches that are accepted by EG as matches.αR=0.005 and αI=30.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF


## 5.4.1. Necessity and Sufficiency

As analyzed, the EG constraint is a necessary but insufficient condition in the correspondence problem, and the CF model describes the mapping between CPs directly. However, in applications, some correct CPs may be inconsistent with the estimated EG model and/or the estimated CF model; there may be some mismatches that are “consistent” with the estimated CF model; there also may be some of the putative correspondences which are “consistent” with the estimated CF but “inconsistent” with the estimated EG, for example, the experimental results in Figures5(a), 5(b), 7(a), 7(b), 8(a), and 8(b). The reasons for the above results are as follows:(i)
The coordinates of the obtained putative CPs are usually corrupted by noise.(ii)
There are usually some errors in the estimation of the CF and EG.(iii)
As pointed out in the first paragraph of Section5, a preset tolerance parameter is needed to define the “consistent” and “inconsistent” in the applications of CF and EG. However, the noise in the obtained putative CPs is random.


## 5.4.2. Characteristics and Limitations of the CF Model and EG Model

In the two models, there are no restrictions on the depth range of the imaged scene. However, the EG is a global describing model, and the CF is a local describing model. In the EG model, any pair of putative CPs can influence the overall model estimation, whereas in the CF model, a pair of putative CPs only influence the model estimation within a local area in their vicinity. The shortcoming of the global model EG is that the overall model estimation can be degraded or ruined by PCs with considerable noise or mismatches in any area of the images. The shortcoming of the local model CF is that a pair of good CPs cannot improve the estimation of CF outside of a local area around itself. Thus, the uneven distribution of putative correspondences with different quality results in the fact that the estimated CF may be of high quality in some areas but of low quality in others; for example, in the experiment of Figure10, the qualities of the CF estimations over the second-nearest-to-the-cameras crossbeam and the third-nearest-to-the-cameras crossbeam are better than estimation over the first-nearest-to-the-cameras crossbeam. The “local area” is determined by the CF estimation method and its chosen parameters; for example, in the CF estimation method SP (SVM) [2], the local area is determined by the chosen kernel and the scale parameter. The above limitations of EG and CF can be alleviated by investigating robust estimation methods, for example, the RANSAC, M-estimators [8], LMedS (Least Median of Squares) [9], and MLESAC [10, 12] for EG. In future work, we will investigate further the estimation method for CF to improve its robustness.Figure 10
The possible correct correspondences identified by CF in the experiment of Figure8 are presented based on depth. (a) 34 putative correspondences (PCs) over the first crossbeam; (b) 324 PCs over the second crossbeam; (c) 214 PCs over the third crossbeam; (d) 20 PCs around the fourth crossbeam; (e) 2 PCs on the wall (for clarity, only 50 randomly chosen PCs are presented in (b) and (c)).
(a)
(b)
(c)
(d)
(e)Figure 11
Quantitative evaluation on two popular benchmark sets: bikes and leuven. The ground-truth CPs are presented by red circles, the detected interest points by black plus signs. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a solid green solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=2.1435×10-5 in (b), and αR=5.8×10-5 in (d).
(a)
RMSD = 13.86
(b)
RMSD = 227.07
(c)
RMSD = 3.84
(d)
RMSD = 236.26Figure 12
Quantitative evaluation on two popular benchmark sets: wall and bark. ((a) and (c)) The EG PMs that are accepted by CF as matches; ((b) and (d)) the CF PMs that are accepted by EG as matches.αI=10.597, αR=2.029×10-4 in (b), and αR=1.05×10-4 in (d).
(a)
RMSD = 16.31
(b)
RMSD = 400.98
(c)
RMSD = 3.58
(d)
RMSD = 322.88Figure 13
Quantitative evaluation on two popular benchmark sets: graf and boat. The ground-truth CPs are presented by red circles and the detected interest points by black plus signs. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a solid green solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=5×10-4 in (b), and αR=7.7×10-5 in (d).
(a)
RMSD = 10.17
(b)
RMSD = 426.39
(c)
RMSD = 3.29
(d)
RMSD = 176.46Figure 14
Quantitative evaluation on two popular benchmark sets: trees and ubc. The ground-truth correspondences are displayed as blue dashed lines and the computed putative correspondences are shown by a yellow solid line. (a) and (c) present some EG PMs that are accepted by CF as matches; (b) and (d) present some CF PMs that are accepted by EG as matches.αI=10.597, αR=5.9×10-5 in (b), and αR=1.85×10-4 in (d).
(a)
RMSD = 4.41
(b)
RMSD = 331.09
(c)
RMSD = 1.57
(d)
RMSD = 117.28Figure 15
Evaluation on Middlebury Stereo Datasets: art and books. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.013 in (a) and (b), αR=0.00018 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 16
Evaluation on Middlebury Stereo Datasets: computer and dolls. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.00018 in (a) and (b), αR=0.00048 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 17
Evaluation on Middlebury Stereo Datasets: drumsticks and dwarves. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.00078 in (a) and (b), αR=0.0035 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 18
Evaluation on Middlebury Stereo Datasets: laundry and moebius. ((a) and (c)) Some potential EG mismatches that are accepted by CF as matches; ((b) and (d)) some potential CF mismatches that are accepted by EG as matches.αR=0.0.0000275 in (a) and (b), αR=0.00035 in (c) and (d), and αI=10.597.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF
(c)
S
¯
c
EG
∩
S
c
CF
(d)
S
c
EG
∩
S
¯
c
CFFigure 19
Evaluation on Middlebury Stereo Dataset: reindeer. (a) Two potential EG mismatches that are accepted by CF as matches; (b) two potential CF mismatches that are accepted by EG as matches.αR=0.005 and αI=30.
(a)
S
¯
c
EG
∩
S
c
CF
(b)
S
c
EG
∩
S
¯
c
CF


## 6. Conclusion

The CF is a recently introduced nonparametric model for rejecting mismatches/outliers in image point matching. In this study, we investigated the principles of the CF and studied its characteristics by comparing it with the widely used parametric model epipolar geometry (EG) constraint.It is shown that the CF describes the mapping relationships between two CPs and should be able to estimate the position of the corresponding point. Therefore, in addition to mismatch rejection, a potential application of the CF is to guide the point matching process by incorporating it into the correspondence propagation [39].In practice, putative correspondences are usually corrupted by noise and outliers, and the number of putative correspondences is limited. Therefore, only an estimation of the CF with a certain accuracy can be estimated, and the actual results will violate the “necessary and sufficient condition.” The characteristic is that the CF model can reduce the searching space of CPs into an elliptical area and the mismatches of the CF are usually near the correct CPs.



---

*Source: 721842-2015-09-07.xml*