Abstract
In computer vision, the estimation of the fundamental matrix is a basic problem that has been extensively studied. 
INTRODUCTION
Fundamental matrix (F-matrix) is an important tool often used in many computer vision tasks. It reflects the corresponding relationship between two pictures shot at the same scene but taken from different viewpoints. It is widely used in tasks such as camera tracking, image rectification, and 3D reconstruction (e.g., [1] , [2] ). The fundamental matrix constrains the coordinates between two 2D images from two different viewpoints. It contains information about the cameras' focal lengths, the positions of optical centers, and the rotation and translation between the two cameras [1] .
INTRODUCTION
In order to calculate the F-matrix, using the fact that it contains 7 free variables, Hartley used 7 pairs of corresponding points, calculated 3 possible F-matrices, and called it 7-Point algorithm [2] . Tsai and Huang proposed a linear algorithm [3] , called the 8-Point algorithm for computing the F-matrix. It uses 8 pairs of matching points and estimates the F-matrix by solving a set of linear equations and making the F-matrix subject to a rank-2 constraint. There are also some other nonlinear methods. For example, Mohr and others assumed that the errors of different corresponding points are mutually independent and have the same standard deviation. They calculated the spatial position of the 3D points and the F-matrix by minimizing the error between the observed values and the fitted values of projected 2D coordinates from the 3D points [4] .
INTRODUCTION
A problem with current methods is that there are usually noise (error of 1 or 2 pixels) and point pairs that are wrongly matched. But all the algorithms mentioned above need to be calculated by the least square method, which requires that the noise mean is 0, and that all matched data points are correct when estimating the F-matrix. Thus the above mentioned algorithms are susceptible to noise and incorrectly matched point pairs.
INTRODUCTION
Some robust algorithms have been proposed to solve these problems. Zhang put forward an algorithm called M-Estimators that can distinguish inliers from outliers. This algorithm could adapt to noise but not the wrongly-matched points [5] . Rousseeuw and Leroy proposed a Least Median of Squares (LMeDS) algorithm. It randomly selects 7 pairs of corresponding points to calculate the fundamental matrix and the error function, then uses an adaptive threshold related to error function to find the outliers. The result is shown to be quite encouraging [6] .
PROPOSED ALGORITHM
In this section we propose a new F-matrix computation method. We briefly review some preliminary topics in the first three subsections for completeness, then uses another three subsections to present the proposed algorithm.
Epipolar Geometry and Fundamental Matrix
Epipolar geometry describes the relationship between two images taken by two cameras C and ' C pointing at the same scene. It is independent of the structure of the scene and is only related to the intrinsic and extrinsic parameters of the cameras.
Epipolar Geometry and Fundamental Matrix
As illustrated in Fig. 1, I and ' I are the image planes of camera C and ' C respectively. Their coordinate systems are set up as is commonly done. Specifically, origin point is located at the topleft of the image while the x-axis points to the right and the y-axis points to the bottom. The points 
Review of the 8-Point Algorithm
Suppose the F-matrix takes the form of .
Review of the 8-Point Algorithm
Also suppose that at least eight pairs of points ( , , , , , , , , ) .
Review of the 8-Point Algorithm
Without regard to the rank 2 constraint tentatively. When the F-matrix is multiplied by a scalar, it still satisfies (1). Now the F-matrix has 8 independent variables. We can utilize the constraint [3] 2 2 2 00 01 22
Review of the 8-Point Algorithm
After solving the Eq. 2, the F-matrix still does not yield to the rank 2 constraint, so we can use the SVD decomposition [3] 
Review of the 8-Point Algorithm
Since F is of rank 2, we have 2 0 σ = . Then the final estimate ' F of the 8-point algorithm is given as
Review of RANSAC
Given any statistical model, Random Sample Consensus (RANSAC) distinguishes the outliers from a data set by using a threshold of error and then finds the best parameters which describes the data set well.
Review of RANSAC
Before running RANSAC to estimate the F-matrix, we need a given th threshold (which is the distance between a point and its epipolar line) and the confidence p of the model. Then the number of iterations k and the number of inliers d must satisfy
Review of RANSAC
. The process is shown in Fig. 2 . , the coordinates of the points describe the positions of the points in the image planes I and I ′ . The difference between the two points describes the transformation between the two viewpoints. Generally, in an image, the feature rich areas tends to have more concentrated feature points to form the matching pairs for Fmatrix estimation. In order to study the distribution and transformation of the matching points, we construct a 4D space in which the vectors are of the form ( , , , )
Review of RANSAC
The 4D space contains the information about both the 2D feature point distribution and the transformation between the matching points. It can help find useful characteristics of the matching points to estimate the F-matrix. Fig . 3 shows an example of the distribution of the feature points in a general natural image. After using SIFT to find the feature points in a real image pair, we get 411 N = pairs of matching points. We can see from the Fig. 3 that most of the feature points locate in some small areas shown in the boxes. This observation provides us with the hint that by doing a cluster analysis on this 4D vectors, we may be able to identify those feature point pairs that are more reliable than those isolated ones. In the next subsection we describe a practically efficient clustering method.
Cluster Analysis
Clustering analysis that classifies the data is a common method used to analyze multidimensional data. Data points that are dense in a multidimensional area and far from other dense area tend to belong to the same cluster. The clustering result describes the distribution of the data in multidimensional space. When clustering, we commonly treat the point that is closest to the center of an area as the center of the cluster. The center point of a cluster decides the basic property of the cluster. These ideas are recently used by Rodriguez and Laio in their paper ''Clustering by fast search and find of density peaks''. The key steps are described as follows. 
Cluster Analysis
1, 0 ( ) 0, 0
Cluster Analysis
where ij d is the Euclidean distance of data point i and j , c d is a parameter which makes the mean value of i ρ equal to 2%N . N is the total number of data points. Larger i ρ means the point i is more likely to be the center of a cluster. . i δ is the minimum distance between the points which have bigger ρ than i ρ and the point i , a large value of i δ means the point i is far away from other dense area. Using ρ as the horizontal axis and δ as the vertical axis, a decision figure of all the data points can be drawn. Then those points with large product values of * ρ δ will be the cluster centers.
The Complete Proposed F-matrix Estimation Algorithm
Given any image pair, we can use the SIFT algorithm to first find the N pairs of corresponding feature points Step 2) Compute of the local density i ρ using (9) and (10) (9) and (11). (Step 4) Obtain the decision figure and find the cluster centers, which are treated as inliers. ( Step 5) Use RANSAC on the inliers of step 4, the F-matrix of the randomly chosen points is computed by the 8-Point method.
The Complete Proposed F-matrix Estimation Algorithm
As will be shown later, because the clustering step can generally produce more reliable inliers than the traditional methods, the final estimate of the F-matrix will be more accurate. In addition, because of the same reason, less iterations are needed, which means faster running time. We pick the point whose * δ ρ is higher than that is decided as a clustering center in [7] . It represents the basic transformation of the local area. α affects the total number of outliers which are picked out that larger α will result in more outliers. Meanwhile, α also influences the reliability of the inliers. With a large amount of points and g vectors located among an inlier i q , it usually indicates that i g is quite close to the local mean value and represents the actual transformation between two images at the point i .
The Complete Proposed F-matrix Estimation Algorithm
As is described above, feature points often lie in areas that have obvious characteristics. In a static scene, we consider that these dense points are often eliminated from false matching and are more reliable than the points that are isolated when being used in estimating the F-matrix because of the presence of noise. Besides, the coordinates of the matching points which are corresponding to the same object in 3D space and are located in the same area in the image plane, often change slowly along with the position in image plane. If there is noise whose mean value is 0, we can refer to the other points in the same area to decrease the influence of noise.
The Complete Proposed F-matrix Estimation Algorithm
In the decision figure, a false corresponding pair i q has big i δ and small i ρ in common.
The Complete Proposed F-matrix Estimation Algorithm
The center of a cluster of q has big δ and ρ . The points in a cluster excluding its center have small i δ but big i ρ .
The Complete Proposed F-matrix Estimation Algorithm
As is described in [8] , inliers that all come from a small area make no sense because they can hardly represent the transformation between the image pairs in the whole range of the image. However, our optimization method easily overcomes this by choosing the inlier point with a large δ .
EXPERIMENTS
Ten pairs of images (5 pairs of real images and 5 pairs of synthetic images) captured from ten scenes are used. Then the F-matrix is estimated utilizing the proposed method. We compare the proposed method with the classical methods which are completed by directly calling the functions in OpenCV. We only show the results of the estimation of F-matrix of one pair of real images and one pair of synthetic images here. While the results of the proposed method in the ten pairs of images are all encouraging. As is seen in Fig. 4 , most of the outliers in RANSAC (displayed by bigger circles) are under the curve, it proves the reliability of the search of density peaks.
Real Images
Using different values of th , we compare the proposed method with RANSAC whose result is shown in Table 1 . When th decreases, the time RANSAC consumes increases rapidly because Ransac picks up data points randomly and iterates until a fine F-matrix is found. However, the proposed method has a prior analysis on the characteristics of the data points using a simple algorithm. Beyond that, the mean error in pixel of the proposed method is smaller.
Real Images
Comparison results with other methods are show in Table 2 . 
Synthetic Images
To compare the methods from another point of view deeply, we use OpenGL to generate 2 images I and I ′ which have a known F-matrix 0 F . So 0 F is the ground truth F-matrix. Then we utilize the evaluation method in section 4.1 of [8] proposed by Zhang to evaluate the F-matrix estimated by the methods described above. The evaluation method is computed following the steps (see Fig. 6 ):
Synthetic Images
(1) Compute the fundamental matrix 1 F the proposed method. (7) Repeat step 2 to step 6 for N times. Then the results that the proposed method compares with other methods are shown in Fig. 7 , Fig.  8 and Table 3 . The numbers in Table 3 
CONCLUSION
The paper proposes the utilization of clustering to optimize the corresponding pairs of points for accurate estimation of the fundamental matrix. This approach chooses the point pairs which are likely to represent the true relationship between image pairs and suffer less from noise. As the threshold decreases, the method we use is better than the conventional RANSAC both in processing speed and accuracy. Besides, our optimization based on search of density peaks has a lower level of the error between the estimated F-matrix and the ground truth.

{'paper_id': '17039582', 'title': 'Clustering Assisted Fundamental Matrix Estimation', 's2_url': 'https://api.semanticscholar.org/CorpusID:17039582', 'source': 'S2ORC'}