# Multi-view Geometry: Correspondences Refinement Based on Algebraic
Properties

Trung-Kien Le and Ping Li
Cognitive Computing Lab
Baidu Research
10900 NE 8th St. Bellevue, WA 98004, USA

{hieukien1207<EMAIL_ADDRESS>

###### Abstract

Correspondences estimation or feature matching is a key step in the image-
based 3D reconstruction problem. In this paper, we propose two algebraic
properties for correspondences. The first is a rank deficient matrix construct
from the correspondences of at least nine key-points on two images (two-view
correspondences) and the second is also another rank deficient matrix built
from the other correspondences of six key-points on at least five images
(multi-view correspondences). To our knowledge, there are no theoretical
results for multi-view correspondences prior to this paper. To obtain accurate
correspondences, multi-view correspondences seem to be more useful than two-
view correspondences. From these two algebraic properties, we propose an
refinement algorithm for correspondences. This algorithm is a combination of
correspondences refinement, outliers recognition and missing key-points
recovery. Real experiments from the project of reconstructing Buddha statue
show that the proposed refinement algorithm can reduce the average error from
77 pixels to 55 pixels on the correspondences estimation. This drop is
substantial and it validates our results.

##  1 Introduction

Image-based 3D reconstruction is a classical and longstanding ill-pose problem
in the computer graphics and computer vision. It easily finds lots of 3D
reconstruction applications on robotics and autonomous devices via the
_simultaneous localization and mapping_ (SLAM) topic (Wang et al., 2007;
Cadena et al., 2016; Bresson et al., 2017), on medical imaging via the _human
organ modeling_ problem (McInerney and Terzopoulos, 1996; Heimann and Meinzer,
2009; Oliveira and Tavares, 2014), on physical geography (Smith et al., 2016),
and many others. In addition to wide applications in science, the image-based
3D reconstruction has also received great attention from scientists because of
the fun it brings. Imagine how happy computer vision researchers with a
passion for art would be when they recreate stunning statues like Venus de
Milo and Discobolus and store them as 3D point clouds. Or how happy computer
graphics researchers with a passion for architecture would be when they can
build some beautiful buildings like the Taj Mahal, the Colosseum, the
Forbidden City and the Blue Mosque as 3D point clouds models and everyday
enjoy them with a huge screen. With the rapid development of the computer
graphics and vision, we believe that the happiness of these researchers will
soon become a reality.

The image-based 3D reconstruction of an object can be seen as a complete
process starting from multiple 2D images and ending with modeled 3D point
clouds of this object. In general, this complete process is a combination of
the five stages that (i) the key-points or the features detection (Lowe, 1999,
2004; Ke and Sukthankar, 2004; Mikolajczyk and Schmid, 2005; Bay et al.,
2006), (ii) the point correspondences estimation, the feature matching or the
point set registration (Munkres, 1957; Myronenko and Song, 2010; Torresani et
al., 2012; Yan et al., 2016; Swoboda et al., 2019), (iii) the camera
calibration or the projection matrix estimation (Weng et al., 1992; Wei and
Ma, 1994; Zhang, 2000; Remondino and Fraser, 2006; Chuang et al., 2021), (iv)
the triangulation (Hartley and Sturm, 1997; Stewénius et al., 2005; Yang et
al., 2019; Sharp and Ovsjanikov, 2020), and (v) the bundle adjustment (Triggs
et al., 1999; Agarwal et al., 2010; Zach, 2014). These five stages are
mutually dependent. Depending on the reconstructed object, the features
detecting by the first stage can be points (Hsieh et al., 1996), edges (Ziou
and Tabbone, 1998; Dollár and Zitnick, 2013), corners (Zheng et al., 1999;
Rosten and Drummond, 2006), circles (Alhichri and Kamel, 2003), or special
curves. Methods for matching features are depended on the numbers and the
characteristics of the features. For instance, when the numbers of features
are in the tens or hundreds, the methods in the ‘graph matching’ group
(Munkres, 1957; Zhou and la Torre, 2013; Swoboda et al., 2019) are prefer.
However, when these numbers are in the thousands or more, the methods in the
‘point set registration’ group (Jian and Vemuri, 2011; Myronenko and Song,
2010; Zhou et al., 2019) seem better. If the features are too many, the
evaluating ‘point-match-point’ should be naturally replaced with ‘pointsss-
match-pointsss’ where ‘pointsss’ means a lot of points. In view of this, some
probabilistic models such as Gaussian mixture models and Bayesian mixture
models are used to characterize these evaluated pointsss. Of the five stages
of image-based 3D reconstruction process, the correspondences estimation or
the feature matching is the most difficult and has been received the most
attention from researchers. For example, the well-known formulation of the
graph matching problem is the _quadratic assignment problem_ (QAP) known as
NP-hard (Lawler, 1963). In addition, the feature matching across multiple
images is still a challenging task although several potential methods exist
for this on two images.

Figure 1: Multi-view geometry: ‘ _Red squares_ ’ are the world points, ‘ _red
triangles_ ’ are the centers of projection (COPs). They are unknown and from
that _camera calibration_ means estimating the positions of the red triangles
and _3D reconstruction_ means estimating the red squares’ positions. ‘ _Light
yellow planes_ ’ are the image and ‘ _blue circles_ ’ are the image points.
They are known. The three blue circles marked by ‘ _black circles_ ’ are
three-view correspondence of the world point ${\bf X}_{m}$.

Using the correspondences from the first and second stages, the fundamental
matrices of each pair images are computed by the _eight-point algorithm_
(Harltey and Zisserman, 2006), the _five-point algorithms_ (Nistér, 2004;
Barath, 2018) or others. Fixing the projection matrix of the reference image,
other projection matrices of other images are determined by these fundamental
matrices. From the projection matrices, positions of camera centers are
obtained. This is a reason the third stage named by the ‘camera calibration’.
The final 3D point clouds are calculated from the projection matrices and
refined by the triangulation and bundle adjustment stages.

Set in a vast forest with a constant fear of getting lost, this paper attempts
to study 3D reconstruction from the basic and theoretical point. First, we
mention that if the correspondences from the second stage are very good, some
of the existing methods in the camera calibration, the triangulation and the
bundle adjustment can give us precise 3D point clouds. The interesting thing
is that we don’t need too many, just in dozens of good correspondences.
Second, we have a question about getting dozens of good correspondences from
images. Of course, good features or good key-points bring us good
correspondences. A ‘good key-point’ means it is very different from other
points. In other words, a key-point should have enough characteristics to be
recognized. In view of this, we prefer to study the image-based 3D
reconstruction on multiple images rather than just two images. From that the
characteristics of the key-points are built based on multiple images, not only
two images. More precisely, based on the _multi-view geometry_ theory for the
image-based 3D reconstruction (Harltey and Zisserman, 2006), we study the
algebraic properties of the correspondences. Two rank properties, one for the
correspondences of at least nine key-points on two images and another for the
correspondences of six key-points on at least five images, are derived. These
two rank properties give us two constraints among correspondences. They are
help us not only on refining correspondences, but also on recognizing outliers
and recovering missing key-points.

The applications of our proposed results, i.e., refining correspondences,
recognizing outliers and recovering missing key-points are validated by some
realistic experiments from our small project on 3D reconstructing the Buddha
statue. In these experiments, we manually determine the ground-truths for the
correspondences. Therefore, all our outcome evaluations based on the
differences between the ground-truths and the estimations, the refinements are
reliable. From twenty one experiments, the average error between the ground-
truths and the estimated correspondences are 77 pixels. After applying our
proposed refinement algorithm, this average error is 55 pixels. This drop is
really dramatic and it validates our results.

Roadmap. In Section 2, we introduce the multi-view geometry problem, the
$N$-view and $M$-point camera calibration, the importance of accurate
correspondences. Then Section 3 derives the two rank properties for
correspondences, presented by Theorem 1 and Theorem 2, which are the main
results of the paper. In Section 4, we apply these two rank properties and
present the main correspondences refinement algorithm (Algorithm 4). Section 5
provides and evaluates results, and finally Section 6 concludes this article.

##  2 Multi-view Geometry

The _multi-view geometry_ is illustrated by Figure 1. There are $M$ unknown
world points ${\bf X}_{1},{\bf X}_{2},\ldots,{\bf X}_{M}$ in the three-
dimensional space $\mathbb{R}^{3}$. The three real numbers $x_{m},y_{m},z_{m}$
are used to indicate the three coordinates of the world point ${\bf X}_{m}$.
These $M$ world points are captured by $N$ images. The $n$th image capturing
the world points means that there is a $3\times 4$ projection matrix ${\bf
P}_{n}$, formulated by

${\bf
P}_{n}\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}p_{1n}&p_{2n}&p_{3n}&p_{4n}\\\
p_{5n}&p_{6n}&p_{7n}&p_{8n}\\\
p_{9n}&p_{10n}&p_{11n}&p_{12n}\end{bmatrix}_{3\times 4\,,}$ (1)

to map all the world points to a plane which is called the $n$th _image-
plane_. Using the homogeneous coordinate system, the mapping from the world
point ${\bf X}_{m}=[x_{m},y_{m},z_{m}]^{T}$ to the image point ${\bf
x}^{\text{\tiny(n)}}_{m}\stackrel{{\scriptstyle\text{def}}}{{=}}[u_{mn},v_{mn}]^{T}$
by the projection matrix ${\bf P}_{n}$ is presented mathematically as follows

${\bf P}_{n}\begin{bmatrix}{\bf X}_{m}\\\
1\end{bmatrix}=\begin{bmatrix}\omega{\bf x}^{\text{\tiny(n)}}_{m}\\\
\omega\end{bmatrix}\,,$ (2)

or

$\begin{bmatrix}p_{1n}&p_{2n}&p_{3n}&p_{4n}\\\ p_{5n}&p_{6n}&p_{7n}&p_{8n}\\\
p_{9n}&p_{10n}&p_{11n}&p_{12n}\end{bmatrix}\begin{bmatrix}x_{m}\\\ y_{m}\\\
z_{m}\\\ 1\end{bmatrix}=\begin{bmatrix}\omega u_{mn}\\\ \omega v_{mn}\\\
\omega\end{bmatrix}\,,$ (3)

where $\omega$ is an unknown scale parameter. Removing the parameter $\omega$,
Eq. (3) yields the following constraints

$\begin{split}p_{1n}x_{m}&+p_{2n}y_{m}+p_{3m}z_{m}+p_{4n}=u_{mn}(p_{9n}x_{m}+p_{10n}y_{m}+p_{11n}z_{m}+p_{12n}),\\\\[2.84526pt]
p_{5n}x_{m}&+p_{6n}y_{m}+p_{7m}z_{m}+p_{8n}=v_{mn}(p_{9n}x_{m}+p_{10n}y_{m}+p_{11n}z_{m}+p_{12n})\,.\end{split}$
(4)

These constraints are the basic relationships between the world points and key
points via the projection matrix.

###  2.1 Correspondences

Applications of multi-view geometry can be easily found in computer vision and
computer graphics. Most problems in computer vision and computer graphics use
images as the first information to exploit. From these images, there are lots
of potential methods such as SURF (Bay et al., 2006), SIFT (Lowe, 1999), PCA-
SIFT (Ke and Sukthankar, 2004), GLOH (Mikolajczyk and Schmid, 2005) to extract
_features_ or _key-points_. If ${\bf x}^{\text{\tiny(n)}}_{m}$ is an image
point of the world point ${\bf X}_{m}$ on the $n$th image for
$n=1,2,\ldots,N$, the sequence of $N$ image points $\\{{\bf
x}^{\text{\tiny(1)}}_{m},{\bf x}^{\text{\tiny(2)}}_{m},\ldots,{\bf
x}^{\text{\tiny(N)}}_{m}\\}$ is called a _correspondence_ and denoted by

$\big{\\{}{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}\,.$ (5)

Sometimes, we use an $N$_-correspondence_ with meaning that this
correspondence is from $N$ images. An example of the correspondence or three-
correspondence is found in Figure 1 from the three blue circles (image points)
and one red square (a world point) marked by the black circles. It is easy to
see an important property of the correspondence via the centers of cameras
(the red triangles) is that all the lines through the point in the
correspondence and their centers of cameras will intersect at one point. This
point is the world point corresponding to this correspondence. In three-
dimensional space, the probability of two lines intersecting at a point is
close to one. But a chance for three, four or more lines intersecting at a
point is very close to zero. Hence, this characteristic illuminates a role to
have highly accurate estimations of correspondences.

###  2.2 $N$-view and $M$-point Camera Calibration

From $N$ images ${\bf P}_{1},{\bf P}_{2},\ldots,{\bf P}_{N}$, using SURF, SIFT
or GLOH, we assume that the $N$-correspondences of $M$ world points ${\bf
X}_{1},{\bf X}_{2},\ldots,{\bf X}_{M}$ are determined. They are

$\big{\\{}{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}\subset\mathbb{R}^{2}\,,$ (6)

where ${\bf x}^{\text{\tiny(n)}}_{m}=[u_{mn},v_{mn}]^{T}$. When the
correspondences are acquired, a lot of researchers in the computer vision
naturally have had a big attention on the estimation of the world points or
the projection matrices based on their correspondences. This problem is called
the _$N$ -view and $M$-point camera calibration_ and it is a prerequisite in
many applications of computer vision.

Formally, the $N$-view and $M$-point camera calibration is stated as follows.
Given $M$ correspondences $\\{{\bf x}^{\text{\tiny(1)}}_{m}\leftrightarrow{\bf
x}^{\text{\tiny(2)}}_{m}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny(N)}}_{m}\\}^{M}_{m=1}$, finding $M$ world points $\\{{\bf
X}_{m}\\}^{M}_{m=1}$ and $N$ projection matrices $\\{{\bf P}_{n}\\}^{N}_{n=1}$
such that Eq. (2) or Eq. (4) satisfy for all $m,n$. Then we call the group
$\\{{\bf X}_{m},{\bf P}_{n}\\}$ is a _solution_ of the $N$-view and $M$-point
with respect to $\\{{\bf x}^{\text{\tiny(1)}}_{m}\leftrightarrow{\bf
x}^{\text{\tiny(2)}}_{m}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny(N)}}_{m}\\}$.

On finding the solutions for the $N$-view, $M$-point camera calibration, we
shall notice about its ambiguity which is explained as follows. Consider the
_projective transformation_ ${\bf H}$ on the three-dimensional space, where
${\bf H}$ is a non-singular $4\times 4$ matrix with 15 degrees of freedom
(Harltey and Zisserman, 2006). We let the new world points $\widehat{\bf
X}_{m}$ and the new projection matrices $\widehat{\bf P}_{n}$ be

$\begin{bmatrix}\widehat{\bf X}_{m}\\\ 1\end{bmatrix}={\bf
H}\begin{bmatrix}{\bf X}_{m}\\\ 1\end{bmatrix}\quad\text{and}\quad\widehat{\bf
P}_{n}={\bf P}_{n}{\bf H}^{-1},$ (7)

for all $m,n$. This means that

$\widehat{\bf P}_{n}\begin{bmatrix}\widehat{\bf X}_{m}\\\ 1\end{bmatrix}={\bf
P}_{n}\begin{bmatrix}{\bf X}_{m}\\\ 1\end{bmatrix}\,$ (8)

Thus, if $\\{{\bf X}_{m},{\bf P}_{n}\\}$ is a solution w.r.t. $\\{{\bf
x}^{\text{\tiny(1)}}_{m}\leftrightarrow{\bf
x}^{\text{\tiny(2)}}_{m}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny(N)}}_{m}\\}$, $\\{\widehat{\bf X}_{m},\widehat{\bf P}_{n}\\}$
is also another solution w.r.t. $\\{{\bf
x}^{\text{\tiny(1)}}_{m}\leftrightarrow{\bf
x}^{\text{\tiny(2)}}_{m}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny(N)}}_{m}\\}$. In other words, the $N$-view, $M$-point camera
calibration is invariant under a projective transformation.

###  2.3 Accuracy of Correspondences

Correspondences will be the input of the $N$-view and $M$-point camera
calibration. Naturally, we have an interesting question about an effect of the
correspondences estimation on the solutions of the $N$-view and $M$-point
camera calibration. To answer this question we study the $N$-view and
$M$-point problem from a small real experiment on reconstructing the Buddha
statue. As shown in Figure 2, there are thirteen world points on the Buddha’s
face and they are marked by some special symbols. Distances between two of
them are manually measured carefully, and from that their relative positions
are determined by using the _multidimensional scale_ (MDS) (Torgerson, 1952;
Schönemann, 1970). Hence, ground truths for the thirteen world points are
acquired. The Buddha’s face, together with the thirteen world points, are
captured by four images. Since the world points are marked by the special
symbols, their correspondences are easily determined with high accuracy. They
are indicated by the _red plus symbols_ as shown in Figure 2. From the ground
truths for the world points and the image points, when the number of the world
points capturing by the $n$th image, $M_{0}$, is at least six, the projection
matrix of this image is derived by the following linear equation

${\bf K}^{T}\begin{bmatrix}p_{1n}\\\ p_{2n}\\\ \vdots\\\
p_{12n}\end{bmatrix}_{12\times 1}=~{}~{}{\bf 0}_{2M_{0}\times 1\,,}$ (9)

where ${\bf K}$ is a $12\times 2M_{0}$ matrix constructed by the coordinates
of the world points ($x_{m},y_{m},z_{m}$) and the image points
($u_{mn},v_{mn}$) as follows

$\displaystyle{\bf
K}\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}x_{1}&0&\ldots&x_{M_{0}}&0\\\
y_{1}&0&\ldots&y_{M_{0}}&0\\\ z_{1}&0&\ldots&z_{M_{0}}&0\\\ 1&0&\ldots&1&0\\\
0&x_{1}&\ldots&0&x_{M_{0}}\\\ 0&y_{1}&\ldots&0&y_{M_{0}}\\\
0&z_{1}&\ldots&0&z_{M_{0}}\\\ 0&1&\ldots&0&1\\\
-u_{1n}x_{1}&-v_{1n}x_{1}&\ldots&-u_{M_{0}n}x_{M_{0}}&-v_{M_{0}n}x_{M_{0}}\\\
-u_{1n}y_{1}&-v_{1n}y_{1}&\ldots&-u_{M_{0}n}y_{M_{0}}&-v_{M_{0}n}y_{M_{0}}\\\
-u_{1n}z_{1}&-v_{1n}z_{1}&\ldots&-u_{M_{0}n}z_{M_{0}}&-v_{M_{0}n}z_{M_{0}}\\\
-u_{1n}&-v_{1n}&\ldots&-u_{M_{0}n}&-v_{M_{0}n}\end{bmatrix}_{12\times
2M_{0}\,.}$ (10)

Figure 2: An example of the four-view and thirteen-point camera calibration.
The _red plus symbols_ are the ground truths, the _blue cross symbols_ and
_green squares_ are estimations of the image points with small and big noises
respectively. Figure 3: Estimations of the centers of cameras and the world
points corresponding to the ground truths and estimated image points with
small and big noises in Figure 2.

The centers of cameras are derived from their projection matrices (Harltey and
Zisserman, 2006). Summarily, we emphasize that with this experiment the ground
truths for the world points, correspondences and centers of cameras are
determined with high accuracy. The ground truths for the thirteen world points
and four centers of camera are simulated by the _red circles_ and _red
triangles_ in Figure 3.

Next we study the effect of the correspondences estimation on the $N$-view and
$M$-point problem by corrupting the ground truths of the correspondences and
seeing how the world points and centers of cameras change. Two different level
noises (small and big) are used to corrupt the image points. The first
corruption with small noises changes the ground truths indicated by the _red
plus symbols_ to the estimated image points indicated by the _blue cross
symbols_. The second one with big noises gives other estimated image points
indicated by _green squares_. Figure 2 simulates clearly the differences among
the ground truths (red plus), estimated image points with small noises (blue
cross) and estimated image points with big noises (green squares) on each
image.

The above sub-figure of Figure 3 presents the ground truth and estimated
centers of cameras for the two above corruptions. The red, blue and green
triangles are the ground truths, estimations with small noises and estimations
with big noises, respectively. To obtain the blue triangles for the estimated
centers of cameras with small noises, we use the linear equation Eq. (9) in
which the matrix ${\bf K}$ is constructed by the ground truths of the world
points and the estimated image points indicated by the blue cross in each
images. Similarly, we replace the blue estimated image points to the green
ones on constructing ${\bf K}$ to get the estimations of the green triangles
corresponding to the big noises corruption. The below sub-figure presents the
ground truths and estimated world points. The red, yellow and green dots are
the ground truths, estimated world points with small noises and estimated one
with big noises, respectively. The yellow dots are determined based on the
blue cross image points and the ground truths of the centers of cameras that
are indicated by the red triangles. Formally, a formula for the world point
${\bf X}_{m}=[x_{m},y_{m},z_{m}]^{T}$ from the $N$ images $\\{{\bf P}_{n}\\}$
and $N$ image points $\\{{\bf x}^{\text{\tiny(n)}}_{m}=[u_{mn},v_{mn}]^{T}\\}$
given by

${\bf H}^{T}\begin{bmatrix}x_{m}\\\ y_{m}\\\ z_{m}\\\ 1\end{bmatrix}_{4\times
1}=~{}~{}{\bf 0}_{2N\times 1\,,}$ (11)

where ${\bf H}$ is the following $4\times 2N$ matrix

$\displaystyle{\bf
H}\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}p_{1,1}-u_{m1}p_{9,1}&p_{5,1}-v_{m1}p_{9,1}&\ldots&p_{5N}-v_{mN}p_{9N}\\\\[2.84526pt]
p_{2,1}-u_{m1}p_{10,1}&p_{6,1}-v_{m1}p_{10,1}&\ldots&p_{6N}-v_{mN}p_{10N}\\\\[2.84526pt]
p_{3,1}-u_{m1}p_{11,1}&p_{7,1}-v_{m1}p_{11,1}&\ldots&p_{7N}-v_{mN}p_{11N}\\\\[2.84526pt]
p_{4,1}-u_{m1}p_{12,1}&p_{8,1}-v_{m1}p_{12,1}&\ldots&p_{8N}-v_{mN}p_{12N}\end{bmatrix}_{4\times
2N\,.}$ (12)

The green dots are determined similarly as the yellow ones when we replace the
blue cross estimated image points by the green square estimations.

All four images in Figure 2 have the size $3024\times 3024$ pixels. The
average differences between the red pluses (ground truths) and the blue
crosses (the estimations with small noises) is around 40 pixels, and the
similar average between the red pluses and the green squares is around 80
pixels. Intuitively, these differences are small but the errors on estimating
the second center of camera and the two world points located on two ears of
the Budhha’s face are too large. Note that the solutions presented in Figure 3
are found within some extra information, i.e., the centers of cameras are
found based on knowing the world points, and vice versa the world points are
determined based on knowing the centers of cameras. So, we cannot expect
better solutions for the $N$-view and $M$-motion camera calibration if the
noises on the estimations of correspondences are similar as Figure 2. Indeed,
to solve some potential applications of the $N$-view and $M$-point problem
such as the near filed 3D reconstruction, we should have better results than
ones shown in Figure 2 and Figure 3.

Some recent realistic applications in computer vision (Harltey and Zisserman,
2006; Zheng et al., 2017; Zollhöfer et al., 2018) show that we can get good
solutions for the $N$-view and $M$-point problem when we (i) exploit more
information from the cameras, (ii) improve SURF, SIFT, etc. to get better
features or interested points, or/and (iii) increase the number of images. In
this paper, we shall propose a different method. Given the correspondences, we
shall refine them before applying some existent algorithms to derive the
estimations of the world points and the centers of cameras. Our refinement
only bases on the geometrical characteristics of the world points, the
correspondences and the centers of cameras in the multi-view geometry. This is
an advantage and from that we can combine our method with other methods to get
better results. This idea that improving the observations based on their
algebraic or geometrical properties can be found in (Velasco et al., 2016; Le
et al., 2018) on studying the signal-based localization.

##  3 Rank Properties for Correspondences

This section presents the main contribution of the paper. Depending on the
number of views $N$ and the number of key-points $M$, an upper bound rank for
a matrix constructed by the correspondences is derived. The upper bound ranks
of these matrices give us some linear constraints among the elements of these
matrices. Thus, if these elements are simple functions of the correspondences,
these linear constraints will help us on recognizing the outliers and refine
the correspondences.

The first contribution of the paper is in Theorem 1 from that a _rank
deficient $M\times 9$ matrix_ is constructed from $M$ correspondences of two
images with $M\geq 9$. Because of the rank deficient property, there is a
linear constraint among this matrix’s elements. Interestingly, since all the
four times $M$ coordinates of the $M$ correspondences are in these elements,
we shall use the rank deficient property given by Theorem 1 to refine these
$4M$ coordinates. Theorem 2, proposing another _rank deficient $N\times 5$
matrix_ constructed from six correspondences of $N$ images with $N\geq 5$, is
the second contribution of the paper. Unlike Theorem 1, the elements of the
$N\times 5$ matrix in Theorem 2 are quartic functions of $12N$ coordinates
from six correspondences in $N$ images. Thus, it is difficult to get a good
algorithm to refine these correspondences based on the rank deficient property
given by Theorem 2. However, as shown in the next section, this rank deficient
property is efficient to _outliers refinement_ and _self-estimation_ in
correspondences estimations.

The result proposed by Theorem 1 is correct for all two-view and $M$-point
with $M\geq 9$, while the one in Theorem 2 is correct for all $N$-view and
six-point with $N\geq 5$. Hence when the number of correspondences is large
but the number of images is small, we shall use Theorem 1 in recognizing the
outliers and refining the correspondences. Vice versa, when the number of
correspondences is small and the number of images is larger, Theorem 2 can be
used. Note that the results in Theorem 1 and Theorem 2 cannot work for the
cases of the number of correspondences be smaller than nine and the number of
images be smaller than five.

Before introducing the two main theorems we mention that we shall use some
simple notations for the cases of two and three-view. More precisely, in the
two-view case we shall use $\\{{\bf x}_{m}\leftrightarrow{\bf
x}^{\prime}_{m}\\}$ and $\\{{\bf P},{\bf Q}\\}$ to denote the correspondence
and the projection matrices, and in the three-view case we use $\\{{\bf
x}_{m}\leftrightarrow{\bf x}^{\prime}_{m}\leftrightarrow{\bf
x}^{\prime\prime}_{m}\\}$ and $\\{{\bf P},{\bf Q},{\bf R}\\}$.

###  3.1 Rank Property for the Two-View

The first result of this paper for the two-view and $M$-point camera
calibration is given by the following theorem.

######  Theorem 1.

Let

$\bigg{\\{}{\bf
x}_{m}\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}u_{m}\\\
v_{m}\end{bmatrix}~{}\leftrightarrow~{}{\bf
x}^{\prime}_{m}\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}u^{\prime}_{m}\\\
v^{\prime}_{m}\end{bmatrix}\bigg{\\}}^{M}_{m=1}$ (13)

be $M$ correspondences on two images. Then the following $M\times 9$ matrix
${\bf\Gamma}$ given by

$\begin{bmatrix}1&u_{1}&v_{1}&u^{\prime}_{1}&v^{\prime}_{1}&u_{1}u^{\prime}_{1}&u_{1}v^{\prime}_{1}&v_{1}u^{\prime}_{1}&v_{1}v^{\prime}_{1}\\\\[2.84526pt]
1&u_{2}&v_{2}&u^{\prime}_{2}&v^{\prime}_{2}&u_{2}u^{\prime}_{2}&u_{2}v^{\prime}_{2}&v_{2}u^{\prime}_{2}&v_{2}v^{\prime}_{2}\\\\[2.84526pt]
1&u_{3}&v_{3}&u^{\prime}_{3}&v^{\prime}_{3}&u_{3}u^{\prime}_{3}&u_{3}v^{\prime}_{3}&v_{3}u^{\prime}_{3}&v_{3}v^{\prime}_{3}\\\\[2.84526pt]
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\\[2.84526pt]
1&u_{M}&v_{M}&u^{\prime}_{M}&v^{\prime}_{M}&u_{M}u^{\prime}_{M}&u_{M}v^{\prime}_{M}&v_{M}u^{\prime}_{M}&v_{M}v^{\prime}_{M}\end{bmatrix}_{M\times
9}$ (14)

will have the rank at most 8.

###### Proof.

Let $\\{{\bf X}_{m}=[x_{m},y_{m},z_{m}]^{T}\\}^{M}_{m=1}$ and

${\bf P}=\begin{bmatrix}p_{1}&p_{2}&p_{3}&p_{4}\\\ p_{5}&p_{6}&p_{7}&p_{8}\\\
p_{9}&p_{10}&p_{11}&p_{12}\end{bmatrix}_{3\times 4}~{},\qquad~{}{\bf
Q}=\begin{bmatrix}q_{1}&q_{2}&q_{3}&q_{4}\\\ q_{5}&q_{6}&q_{7}&q_{8}\\\
q_{9}&q_{10}&q_{11}&q_{12}\end{bmatrix}_{3\times 4}$ (15)

be the $M$ world points and two projection matrices corresponding to the two-
correspondence $\\{{\bf x}_{m}\leftrightarrow{\bf x}^{\prime}_{m}\\}$. The
equation Eq. (11) which is from Eq. (4), implies

${\bf K}\begin{bmatrix}x_{m}\\\ y_{m}\\\ z_{m}\\\ 1\end{bmatrix}={\bf
0}_{4\times 1}$ (16)

where

${\bf
K}=\begin{bmatrix}p_{1}-u_{m}p_{9}&p_{2}-u_{m}p_{10}&p_{3}-u_{m}p_{11}&p_{4}-u_{m}p_{12}\\\\[2.84526pt]
p_{5}-v_{m}p_{9}&p_{6}-v_{m}p_{10}&p_{7}-v_{m}p_{11}&p_{8}-v_{m}p_{12}\\\\[2.84526pt]
q_{1}-u^{\prime}_{m}q_{9}&q_{2}-u^{\prime}_{m}q_{10}&q_{3}-u^{\prime}_{m}q_{11}&q_{4}-u^{\prime}_{m}p_{12}\\\\[2.84526pt]
q_{5}-v^{\prime}_{m}q_{9}&q_{6}-v^{\prime}_{m}q_{10}&q_{7}-v^{\prime}_{m}q_{11}&q_{8}-v^{\prime}_{m}p_{12}\end{bmatrix}_{4\times
4\,.}$ (17)

It is clear from Eq. (17) that the determinant of ${\bf K}$ should be zero,
i.e., $\text{det}({\bf K})=0$. Considering
$u_{m},v_{m},u^{\prime}_{m},v^{\prime}_{m}$ as unknown variables and
$\\{p_{i},q_{j}\\}$ as coefficients, we present the determinant of ${\bf K}$
as a polynomial equation that

$\begin{split}\text{det}({\bf
K})&=a_{0}+a_{1}u_{m}+a_{2}v_{m}+a_{3}u^{\prime}_{m}+a_{4}v^{\prime}_{m}\\\
&~{}~{}~{}+a_{5}u_{m}v_{m}+a_{6}u_{m}u^{\prime}_{m}+a_{7}u_{m}v^{\prime}_{m}+a_{8}v_{m}u^{\prime}_{m}+a_{9}v_{m}v^{\prime}_{m}+a_{10}u^{\prime}_{m}v^{\prime}_{m}\\\
&~{}~{}~{}+a_{11}u_{m}v_{m}u^{\prime}_{m}+a_{12}u_{m}v_{m}v^{\prime}_{m}+a_{13}u_{m}u^{\prime}_{m}v^{\prime}_{m}+a_{14}v_{m}u^{\prime}_{m}v^{\prime}_{m}\\\
&~{}~{}~{}+a_{15}u_{m}v_{m}u^{\prime}_{m}v^{\prime}_{m}\,.\end{split}$ (18)

This polynomial has sixteen monomials and they are

$\begin{split}&1,~{}u_{m},~{}v_{m},~{}u^{\prime}_{m},~{}v^{\prime}_{m},~{}u_{m}v_{m},~{}u_{m}u^{\prime}_{m},~{}u_{m}v^{\prime}_{m},~{}v_{m}u^{\prime}_{m},~{}v_{m}v^{\prime}_{m},~{}u^{\prime}_{m}v^{\prime}_{m},\\\
&u_{m}v_{m}u^{\prime}_{m},~{}u_{m}v_{m}v^{\prime}_{m},~{}u_{m}u^{\prime}_{m}v^{\prime}_{m},~{}v_{m}u^{\prime}_{m}v^{\prime}_{m},~{}u_{m}v_{m}u^{\prime}_{m}v^{\prime}_{m}\,,\end{split}$
(19)

corresponding with sixteen coefficients $a_{0},a_{1},\ldots,a_{15}$.
Interestingly, we always have

$a_{5}=a_{10}=a_{11}=a_{12}=a_{13}=a_{14}=a_{15}=0\,.$ (20)

For example, the coefficient $a_{5}$ is given by

$\begin{split}&p_{9}p_{10}q_{3}q_{8}+p_{9}p_{11}q_{4}q_{6}+p_{9}p_{12}q_{2}q_{7}+p_{10}p_{12}q_{3}q_{5}+p_{10}p_{11}q_{1}q_{8}+p_{10}p_{9}q_{4}q_{7}\\\
+\,&p_{11}p_{9}q_{2}q_{8}+p_{11}p_{10}q_{4}q_{5}+p_{11}p_{12}q_{1}q_{6}+p_{12}p_{11}q_{2}q_{5}+p_{12}p_{10}q_{1}q_{7}+p_{12}p_{9}q_{3}q_{6}\\\
-\,&p_{9}p_{12}q_{3}q_{6}-p_{9}p_{11}q_{2}q_{8}-p_{9}p_{10}q_{4}q_{7}-p_{10}p_{9}q_{3}q_{8}-p_{10}p_{11}q_{4}q_{5}-p_{10}p_{12}q_{1}q_{7}\\\
-\,&p_{11}p_{12}q_{2}q_{5}-p_{11}p_{10}q_{1}q_{8}-p_{11}p_{9}q_{4}q_{6}-p_{12}p_{9}q_{2}q_{7}-p_{12}p_{10}q_{3}q_{5}-p_{12}p_{11}q_{1}q_{6}\\\
=~{}&0\,.\\\\[-8.53581pt] \end{split}$ (21)

Thus, the polynomial in Eq. (18) with 16 monomials will be reduced to 9
monomials, and it is

$\begin{bmatrix}1\\\ u_{m}\\\ v_{m}\\\ u^{\prime}_{m}\\\ v^{\prime}_{m}\\\
u_{m}u^{\prime}_{m}\\\ u_{m}v^{\prime}_{m}\\\ v_{m}u^{\prime}_{m}\\\
v_{m}v^{\prime}_{m}\end{bmatrix}^{T}\begin{bmatrix}a_{0}\\\ a_{1}\\\ a_{2}\\\
a_{3}\\\ a_{4}\\\ a_{6}\\\ a_{7}\\\ a_{8}\\\ a_{9}\end{bmatrix}~{}=~{}0\,.$
(22)

Eq. (22) is correct for all $m=1,2,\ldots,M$. Therefore,

$\begin{bmatrix}1&1&1&\ldots&1\\\ u_{1}&u_{2}&u_{3}&\ldots&u_{M}\\\
v_{1}&v_{2}&v_{3}&\ldots&v_{M}\\\
u^{\prime}_{1}&u^{\prime}_{2}&u^{\prime}_{3}&\ldots&u^{\prime}_{M}\\\
v^{\prime}_{1}&v^{\prime}_{2}&v^{\prime}_{3}&\ldots&v^{\prime}_{M}\\\
u_{1}u^{\prime}_{1}&u_{2}u^{\prime}_{2}&u_{3}u^{\prime}_{3}&\ldots&u_{M}u^{\prime}_{M}\\\
u_{1}v^{\prime}_{1}&u_{2}v^{\prime}_{2}&u_{3}v^{\prime}_{3}&\ldots&u_{M}v^{\prime}_{M}\\\
v_{1}u^{\prime}_{1}&v_{2}u^{\prime}_{2}&v_{3}u^{\prime}_{3}&\ldots&v_{M}u^{\prime}_{M}\\\
v_{1}v^{\prime}_{1}&v_{2}v^{\prime}_{2}&v_{3}v^{\prime}_{3}&\ldots&v_{M}v^{\prime}_{M}\end{bmatrix}^{T}\begin{bmatrix}a_{0}\\\
a_{1}\\\ a_{2}\\\ a_{3}\\\ a_{4}\\\ a_{6}\\\ a_{7}\\\ a_{8}\\\
a_{9}\end{bmatrix}~{}=~{}0\,.$ (23)

Since the vector $[a_{0},a_{1},\ldots,a_{9}]^{T}$ is non-zero, the proof of
Theorem 1 is finished by Eq. (23). ∎

Theorem 1 confirms that nine columns of the matrix ${\bf\Gamma}$ in Eq. (14)
are linearly dependent. When the number of key-points is at least nine ($M\geq
9$), the columns linear independence yields the rank deficient property for
${\bf\Gamma}$. The key point of the proof of Theorem 1 is the linear
relationship Eq. (22) from that all the coordinates of the $m$th point
correspondences are in the first vector and all the elements of the two
projection matrices are in the second vector. Thus this linear relationship is
still correct when we replace the first vector by another from other
correspondences. In another word, Theorem 1 is correct not only for nine two-
correspondences but also ten, eleven or more two-correspondences.

When $M\geq 9$, considering the $9\times 9$ sub-matrix
${\bf\Gamma}_{1,2,\ldots,9}$ constructed by the first nine rows of
${\bf\Gamma}$ in Eq. (14), Theorem 1 guarantees

$\text{det}\big{(}{\bf\Gamma}_{1,2,\ldots,9}\big{)}=0\,.$ (24)

Let us denote ${\bf\Gamma}_{1,2,\ldots,9}^{i}$ the $8\times 8$ matrix from
${\bf\Gamma}_{1,2,\ldots,9}$ when we remove the first row and the $i$-th
column $(i=1,2,\ldots,9)$. Using the first row to compute the determinant of
the $9\times 9$ matrix ${\bf\Gamma}_{1,2,\ldots,9}$ via its $8\times 8$
matrices, Eq. (24) implies

$\alpha_{1|2,\ldots,9}u_{1}+\beta_{1|2,\ldots,9}v_{1}+\gamma_{1|2,\ldots,9}=0\,,$
(25)

where

$\begin{split}\alpha_{1|2,\ldots,9}&~{}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}-\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{2}\big{|}-u^{\prime}_{1}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{6}\big{|}+v^{\prime}_{1}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{7}\big{|}\\\\[5.69054pt]
\beta_{1|2,\ldots,9}&~{}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{3}\big{|}-u^{\prime}_{1}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{8}\big{|}+v^{\prime}_{1}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{9}\big{|}\\\\[5.69054pt]
\gamma_{1|2,\ldots,9}&~{}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{1}\big{|}-u^{\prime}_{1}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{4}\big{|}+v^{\prime}_{1}\big{|}{\bf\Gamma}_{1,2,\ldots,9}^{5}\big{|}\,.\end{split}$
(26)

The linear equation Eq. (25) brings us an idea that if the image point ${\bf
x}_{1}=[u_{1},v_{1}]^{T}$ is an outlier and other image points are good
estimations then the outlier $[u_{1},v_{1}]^{T}$ can be refined or recomputed
based on Eq. (25). Only one linear equation as Eq. (25) is not sufficient to
determine two variables $u_{1}$ and $v_{1}$. Fortunately, when $M\geq 10$, we
have at least these nine linear equations and they are sufficient to give us
the good solutions for the outlier $[u_{1},v_{1}]^{T}$. Formally, this idea is
solved by the following proposition.

######  Proposition 1.

Assuming that $M\geq 10$, the functions of $u_{1}$ and $v_{1}$ from the remain
coordinates are given by

$\begin{bmatrix}u_{1}\\\
v_{1}\end{bmatrix}=-\begin{bmatrix}\alpha_{1|2,\ldots,9}&\beta_{1|2,\ldots,9}\\\
\vdots&\vdots\\\ \alpha_{1|i_{1},\ldots,i_{8}}&\beta_{1|i_{1},\ldots,i_{8}}\\\
\vdots&\vdots\\\
\alpha_{1|M-7,\ldots,M}&\beta_{1|M-7,\ldots,M}\end{bmatrix}^{\dagger}\begin{bmatrix}\gamma_{1|2,\ldots,9}\\\
\vdots\\\ \gamma_{1|i_{1},\ldots,i_{8}}\\\ \vdots\\\
\gamma_{1|M-7,\ldots,M}\end{bmatrix}$ (27)

for all $2\leq i_{1}<i_{2}<\cdots<i_{8}\leq M$, where $\dagger$ denotes Moore-
Penrose inverse operator.

###### Proof.

Eq. (25) is correct for all nine indices $1$ and $2\leq
i_{1}<i_{2}<\cdots<i_{8}\leq M$. So,

$\begin{bmatrix}\alpha_{1|i_{1},i_{2},\ldots,i_{8}}&\beta_{1|i_{1},i_{2},\ldots,i_{8}}\end{bmatrix}\begin{bmatrix}u_{1}\\\
v_{1}\end{bmatrix}=-\gamma_{1|i_{1},i_{2},\ldots,i_{8}}\,.$ (28)

Hence, let eight indices $(i_{1},\ldots,i_{8})$ run from the first group
$(2,\ldots,9)$ to the last group $(M-7,\ldots,M)$ we get

$\begin{bmatrix}\alpha_{1|2,\ldots,9}&\beta_{1|2,\ldots,9}\\\ \vdots&\vdots\\\
\alpha_{1|i_{1},i_{2},\ldots,i_{8}}&\beta_{1|i_{1},i_{2},\ldots,i_{8}}\\\
\vdots&\vdots\\\
\alpha_{1|M-7,\ldots,M}&\beta_{1|M-7,\ldots,M}\end{bmatrix}\begin{bmatrix}u_{1}\\\
v_{1}\end{bmatrix}=-\begin{bmatrix}\gamma_{1|2,\ldots,9}\\\ \vdots\\\
\gamma_{1|i_{1},i_{2},\ldots,i_{8}}\\\ \vdots\\\
\gamma_{1|M-7,\ldots,M}\end{bmatrix}\,.$ (29)

Note that the matrix in the left side of Eq. (29) has the size ${M-1\choose
8}\times 2$ and its is always full rank. Thus, Eq. (27) is as a consequence of
Eq. (29) and Proposition 1 is correct. ∎

###  3.2 Rank Property for the Multi-View

To get another rank property for the multi-view case we follow the idea from
the linear constraint Eq. (22) to derive another linear constraint that the
first vector is from the coordinates of the correspondences and the second
vector is from the coordinates of the world points. Thus, because the second
vector is independent to the images, if this linear constraint is found it
will be correct for all images. Then an upper bound rank for the multi-view
can be obtained.

Theorem 2, basing on the above discussion, proposes an upper bound rank for an
$N\times 5$ matrix constructed from the six point correspondences in $N$
images.

######  Theorem 2.

Let

$\Big{\\{}{\bf x}_{m}^{\texttt{\tiny(1)}}\,\leftrightarrow\,{\bf
x}_{m}^{\texttt{\tiny(2)}}\,\leftrightarrow\,{\bf
x}_{m}^{\texttt{\tiny(3)}}\,\leftrightarrow\,\cdots\,\leftrightarrow\,{\bf
x}_{m}^{\texttt{\tiny(N)}}\Big{\\}}^{6}_{m=1}$ (30)

be six correspondences on $N$ images, where ${\bf
x}^{\texttt{\tiny(n)}}_{m}\stackrel{{\scriptstyle\text{def}}}{{=}}[u_{mn},v_{mn}]^{T}$.
The following $N\times 5$ matrix

${\bf\Lambda}~{}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}\begin{bmatrix}\xi^{\text{\tiny(1)}}_{34,5}\xi^{\text{\tiny(1)}}_{12,6}&\xi^{\text{\tiny(1)}}_{42,5}\xi^{\text{\tiny(1)}}_{13,6}&\xi^{\text{\tiny(1)}}_{23,5}\xi^{\text{\tiny(1)}}_{14,6}&\xi^{\text{\tiny(1)}}_{12,5}\xi^{\text{\tiny(1)}}_{34,6}&\xi^{\text{\tiny(1)}}_{13,5}\xi^{\text{\tiny(1)}}_{42,6}\\\\[8.53581pt]
\xi^{\text{\tiny(2)}}_{34,5}\xi^{\text{\tiny(2)}}_{12,6}&\xi^{\text{\tiny(2)}}_{42,5}\xi^{\text{\tiny(2)}}_{13,6}&\xi^{\text{\tiny(2)}}_{23,5}\xi^{\text{\tiny(2)}}_{14,6}&\xi^{\text{\tiny(2)}}_{12,5}\xi^{\text{\tiny(2)}}_{34,6}&\xi^{\text{\tiny(2)}}_{13,5}\xi^{\text{\tiny(2)}}_{42,6}\\\\[8.53581pt]
\xi^{\text{\tiny(3)}}_{34,5}\xi^{\text{\tiny(3)}}_{12,6}&\xi^{\text{\tiny(3)}}_{42,5}\xi^{\text{\tiny(3)}}_{13,6}&\xi^{\text{\tiny(3)}}_{23,5}\xi^{\text{\tiny(3)}}_{14,6}&\xi^{\text{\tiny(3)}}_{12,5}\xi^{\text{\tiny(3)}}_{34,6}&\xi^{\text{\tiny(3)}}_{13,5}\xi^{\text{\tiny(3)}}_{42,6}\\\\[2.84526pt]
\vdots&\vdots&\vdots&\vdots&\vdots\\\\[4.2679pt]
\xi^{\text{\tiny(N)}}_{34,5}\xi^{\text{\tiny(N)}}_{12,6}&\xi^{\text{\tiny(N)}}_{42,5}\xi^{\text{\tiny(N)}}_{13,6}&\xi^{\text{\tiny(N)}}_{23,5}\xi^{\text{\tiny(N)}}_{14,6}&\xi^{\text{\tiny(N)}}_{12,5}\xi^{\text{\tiny(N)}}_{34,6}&\xi^{\text{\tiny(N)}}_{13,5}\xi^{\text{\tiny(N)}}_{42,6}\end{bmatrix}_{N\times
5}$ (31)

where

$\xi^{\texttt{\tiny(n)}}_{i_{1}i_{2},j}\,\stackrel{{\scriptstyle\text{def}}}{{=}}\,\begin{vmatrix}u_{i_{1}n}-u_{jn}&u_{i_{2}n}-u_{jn}\\\\[2.84526pt]
v_{i_{1}n}-v_{jn}&v_{i_{2}n}-v_{jn}\end{vmatrix}$ (32)

will have the rank at most 4.

###### Proof.

Let ${\bf X}_{1}=[x_{1},y_{1},z_{1}]^{T},{\bf
X}_{2}=[x_{2},y_{2},z_{2}]^{T},\ldots,{\bf X}_{6}=[x_{6},y_{6},z_{6}]^{T}$ be
the six world points and

${\bf P}_{n}=\begin{bmatrix}p_{1n}&p_{2n}&p_{3n}&p_{4n}\\\
p_{5n}&p_{6n}&p_{7n}&p_{8n}\\\
p_{9n}&p_{10n}&p_{11n}&p_{12n}\end{bmatrix}_{3\times 4}$ (33)

($n=1,2,\ldots,N$) be five projection matrices corresponding to the point
correspondences given by Eq. (30). From Eq. (9) and Eq. (10) we know that
within at least six world points the projection matrix ${\bf P}_{n}$ can be
derived by a linear equation. Unfortunately, these six world points are
unknown. But we can use this linear equation to present each element of ${\bf
P}_{n}$ as a function of these six world points. We begin with the linear
equation presenting the relationship between the six world points and the
projection matrix via the corresponding image point.

${\left[\begin{tabular}[]{cccccccccccc}$x_{1}$&$y_{1}$&$z_{1}$&1&0&0&0&0&$-u_{1n}x_{1}$&$-u_{1n}y_{1}$&$-u_{1n}z_{1}$&$-u_{1n}$\\\\[2.84526pt]
0&0&0&0&$x_{1}$&$y_{1}$&$z_{1}$&1&$-v_{1n}x_{1}$&$-v_{1n}y_{1}$&$-v_{1n}z_{1}$&$-v_{1n}$\\\\[2.84526pt]
$x_{2}$&$y_{2}$&$z_{2}$&1&0&0&0&0&$-u_{2n}x_{2}$&$-u_{2n}y_{2}$&$-u_{2n}z_{2}$&$-u_{2n}$\\\\[2.84526pt]
0&0&0&0&$x_{2}$&$y_{2}$&$z_{2}$&1&$-v_{2n}x_{2}$&$-v_{2n}y_{2}$&$-v_{2n}z_{2}$&$-v_{2n}$\\\\[2.84526pt]
$x_{3}$&$y_{3}$&$z_{3}$&1&0&0&0&0&$-u_{3n}x_{3}$&$-u_{3n}y_{3}$&$-u_{3n}z_{3}$&$-u_{3n}$\\\\[2.84526pt]
0&0&0&0&$x_{3}$&$y_{3}$&$z_{3}$&1&$-v_{3n}x_{3}$&$-v_{3n}y_{3}$&$-v_{3n}z_{3}$&$-v_{3n}$\\\\[2.84526pt]
$x_{4}$&$y_{4}$&$z_{4}$&1&0&0&0&0&$-u_{4n}x_{4}$&$-u_{4n}y_{4}$&$-u_{4n}z_{4}$&$-u_{4n}$\\\\[2.84526pt]
0&0&0&0&$x_{4}$&$y_{4}$&$z_{4}$&1&$-v_{4n}x_{4}$&$-v_{4n}y_{4}$&$-v_{4n}z_{4}$&$-v_{4n}$\\\\[2.84526pt]
$x_{5}$&$y_{5}$&$z_{5}$&1&0&0&0&0&$-u_{5n}x_{5}$&$-u_{5n}y_{5}$&$-u_{5n}z_{5}$&$-u_{5n}$\\\\[2.84526pt]
0&0&0&0&$x_{5}$&$y_{5}$&$z_{5}$&1&$-v_{5n}x_{5}$&$-v_{5n}y_{5}$&$-v_{5n}z_{5}$&$-v_{5n}$\\\\[2.84526pt]
$x_{6}$&$y_{6}$&$z_{6}$&1&0&0&0&0&$-u_{6n}x_{6}$&$-u_{6n}y_{6}$&$-u_{6n}z_{6}$&$-u_{6n}$\\\\[2.84526pt]
0&0&0&0&$x_{6}$&$y_{6}$&$z_{6}$&1&$-v_{6n}x_{6}$&$-v_{6n}y_{6}$&$-v_{6n}z_{6}$&$-v_{6n}$\\\\[2.84526pt]
\end{tabular}\right]_{12\times 12}\begin{bmatrix}p_{1n}\\\\[2.84526pt]
p_{2n}\\\\[2.84526pt] p_{3n}\\\\[2.84526pt] p_{4n}\\\\[2.84526pt]
p_{5n}\\\\[2.84526pt] p_{6n}\\\\[2.84526pt] p_{7n}\\\\[2.84526pt]
p_{8n}\\\\[2.84526pt] p_{9n}\\\\[2.84526pt] p_{10n}\\\\[2.84526pt]
p_{11n}\\\\[2.84526pt] p_{12n}\end{bmatrix}\,=~{}{\bf 0}_{12\times 1\,.}}$
(34)

Thanks to the invariant property of the $N$-view, $M$-point camera calibration
under any projective transformation, without loss of generality we can assume
that

$\begin{bmatrix}{\bf X}_{1}&{\bf X}_{2}&{\bf X}_{3}&{\bf
X}_{4}\end{bmatrix}=\begin{bmatrix}x_{1}&x_{2}&x_{3}&x_{4}\\\
y_{1}&y_{2}&y_{3}&y_{4}\\\
z_{1}&z_{2}&z_{3}&z_{4}\end{bmatrix}=\begin{bmatrix}0&0&0&1\\\ 0&0&1&0\\\
0&1&0&0\end{bmatrix}.$ (35)

Hence, Eq. (34) becomes

${\left[\begin{tabular}[]{cccccccccccc}0&0&0&1&0&0&0&0&0&0&0&$-u_{1n}$\\\\[2.84526pt]
0&0&0&0&0&0&0&1&0&0&0&$-v_{1n}$\\\\[2.84526pt]
0&0&1&1&0&0&0&0&0&0&$-u_{2n}$&$-u_{2n}$\\\\[2.84526pt]
0&0&0&0&0&0&1&1&0&0&$-v_{2n}$&$-v_{2n}$\\\\[2.84526pt]
0&1&0&1&0&0&0&0&0&$-u_{3n}$&0&$-u_{3n}$\\\\[2.84526pt]
0&0&0&0&0&1&0&1&0&$-v_{3n}$&0&$-v_{3n}$\\\\[2.84526pt]
1&0&0&1&0&0&0&0&$-u_{4n}$&0&0&$-u_{4n}$\\\\[2.84526pt]
0&0&0&0&1&0&0&1&$-v_{4n}$&0&0&$-v_{4n}$\\\\[2.84526pt]
$x_{5}$&$y_{5}$&$z_{5}$&1&0&0&0&0&$-u_{5n}x_{5}$&$-u_{5n}y_{5}$&$-u_{5n}z_{5}$&$-u_{5n}$\\\\[2.84526pt]
0&0&0&0&$x_{5}$&$y_{5}$&$z_{5}$&1&$-v_{5n}x_{5}$&$-v_{5n}y_{5}$&$-v_{5n}z_{5}$&$-v_{5n}$\\\\[2.84526pt]
$x_{6}$&$y_{6}$&$z_{6}$&1&0&0&0&0&$-u_{6n}x_{6}$&$-u_{6n}y_{6}$&$-u_{6n}z_{6}$&$-u_{6n}$\\\\[2.84526pt]
0&0&0&0&$x_{6}$&$y_{6}$&$z_{6}$&1&$-v_{6n}x_{6}$&$-v_{6n}y_{6}$&$-v_{6n}z_{6}$&$-v_{6n}$\end{tabular}\right]_{12\times
12}\begin{bmatrix}p_{1n}\\\\[2.84526pt] p_{2n}\\\\[2.84526pt]
p_{3n}\\\\[2.84526pt] p_{4n}\\\\[2.84526pt] p_{5n}\\\\[2.84526pt]
p_{6n}\\\\[2.84526pt] p_{7n}\\\\[2.84526pt] p_{8n}\\\\[2.84526pt]
p_{9n}\\\\[2.84526pt] p_{10n}\\\\[2.84526pt] p_{11n}\\\\[2.84526pt]
p_{12n}\end{bmatrix}\,=~{}{\bf 0}_{12\times 1\,.}}$ (36)

Eq. (36) is a simple linear equation for us to present
$p_{in},~{}(i=1,2,\ldots,12)$ as functions of the two remain unknown world
points ${\bf X}_{5}=[x_{5},y_{5},z_{5}]^{T}$ and ${\bf
X}_{6}=[x_{6},y_{6},z_{6}]^{T}$. We simplify Eq. (36) by implementing some
linear operators on the rows of the matrix given in Eq. (36) as follows.
First, we subtract the first row for the third, fifth, 7th, 9th and 11th rows,
and subtract the second row for the forth, sixth, 8th, 10th and 12th rows.
After the first step we have a new matrix. With this new matrix, we subtract
$x_{5}$ times the 7th row, $y_{5}$ times the fifth row and $z_{5}$ times the
third row from the 9th and 11th rows and $x_{5}$ times the 8th row, $y_{5}$
times the 6th row and $z_{5}$ times the forth row from the 10th and 12th rows.
Finally we have another but equivalent linear equations given by

${\left[\begin{tabular}[]{cccccccccccc}0&0&0&1&0&0&0&0&0&0&0&$-u_{1n}$\\\
0&0&0&0&0&0&0&1&0&0&0&$-v_{1n}$\\\
0&0&1&0&0&0&0&0&0&0&$-u_{2n}$&$u_{1n}-u_{2n}$\\\
0&0&0&0&0&0&1&0&0&0&$-v_{2n}$&$v_{1n}-v_{2n}$\\\
0&1&0&0&0&0&0&0&0&$-u_{3n}$&0&$u_{1n}-u_{3n}$\\\
0&0&0&0&0&1&0&0&0&$-v_{3n}$&0&$v_{1n}-v_{3n}$\\\
1&0&0&0&0&0&0&0&$-u_{4n}$&0&0&$u_{1n}-u_{4n}$\\\
0&0&0&0&1&0&0&0&$-v_{4n}$&0&0&$v_{1n}-v_{4n}$\\\\[5.69054pt]
0&0&0&0&0&0&0&0&$x_{5}(u_{4n}-u_{5n})$&$y_{5}(u_{3n}-u_{5n})$&$z_{5}(u_{2n}-u_{5n})$&$\begin{matrix}(u_{1n}-u_{5n})-x_{5}(u_{1n}-u_{4n})\\\
-y_{5}(u_{1n}-u_{3n})\\\ -z_{5}(u_{1n}-u_{2n})\end{matrix}$\\\\[17.07164pt]
0&0&0&0&0&0&0&0&$x_{5}(v_{4n}-v_{5n})$&$y_{5}(v_{3n}-v_{5n})$&$z_{5}(v_{2n}-v_{5n})$&$\begin{matrix}(v_{1n}-v_{5n})-x_{5}(v_{1n}-v_{4n})\\\
-y_{5}(v_{1n}-v_{3n})\\\ -z_{5}(v_{1n}-v_{2n})\end{matrix}$\\\\[17.07164pt]
0&0&0&0&0&0&0&0&$x_{6}(u_{4n}-u_{6n})$&$y_{6}(u_{3n}-u_{6n})$&$z_{6}(u_{2n}-u_{6n})$&$\begin{matrix}(u_{1n}-u_{6n})-x_{6}(u_{1n}-u_{4n})\\\
-y_{6}(u_{1n}-u_{3n})\\\ -z_{6}(u_{1n}-u_{2n})\end{matrix}$\\\\[17.07164pt]
0&0&0&0&0&0&0&0&$x_{6}(v_{4n}-v_{6n})$&$y_{6}(v_{3n}-v_{6n})$&$z_{6}(v_{2n}-v_{6n})$&$\begin{matrix}(v_{1n}-v_{6n})-x_{6}(v_{1n}-v_{4n})\\\
-y_{6}(v_{1n}-v_{3n})\\\
-z_{6}(v_{1n}-v_{2n})\end{matrix}$\end{tabular}\right]\begin{bmatrix}p_{1n}\\\\[2.84526pt]
p_{2n}\\\\[2.84526pt] p_{3n}\\\\[2.84526pt] p_{4n}\\\\[2.84526pt]
p_{5n}\\\\[2.84526pt] p_{6n}\\\\[2.84526pt] p_{7n}\\\\[2.84526pt]
p_{8n}\\\\[2.84526pt] p_{9n}\\\\[2.84526pt] p_{10n}\\\\[2.84526pt]
p_{11n}\\\\[2.84526pt] p_{12n}\end{bmatrix}={\bf 0}_{12\times 1\,.}}$ (37)

From Eq. (37), we easily get some simple linear equations of $\\{p_{in}\\}$
and $\\{u_{mn}\\}$ such as $p_{4n}=u_{1n}p_{12n},~{}p_{8n}=v_{1n}p_{12n}$ or
$p_{3n}=u_{2n}p_{11n}-(u_{1n}-u_{2n})p_{12n}$. However the interesting point
we exploit from Eq. (37) to get the upper rank given by this theorem is in the
following equation

$\widehat{\bf K}\begin{bmatrix}p_{9n}\\\ p_{10n}\\\ p_{11n}\\\
p_{12n}\end{bmatrix}={\bf 0}_{1\times 4\,,}$ (38)

where

$\widehat{\bf
K}~{}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}\begin{bmatrix}x_{5}(u_{4n}-u_{5n})&y_{5}(u_{3n}-u_{5n})&z_{5}(u_{2n}-u_{5n})&\begin{matrix}(u_{1n}-u_{5n})-x_{5}(u_{1n}-u_{4n})\\\
-y_{5}(u_{1n}-u_{3n})\\\ -z_{5}(u_{1n}-u_{2n})\end{matrix}\\\\[19.91692pt]
x_{5}(v_{4n}-v_{5n})&y_{5}(v_{3n}-v_{5n})&z_{5}(v_{2n}-v_{5n})&\begin{matrix}(v_{1n}-v_{5n})-x_{5}(v_{1n}-v_{4n})\\\
-y_{5}(v_{1n}-v_{3n})\\\ -z_{5}(v_{1n}-v_{2n})\end{matrix}\\\\[19.91692pt]
x_{6}(u_{4n}-u_{6n})&y_{6}(u_{3n}-u_{6n})&z_{6}(u_{2n}-u_{6n})&\begin{matrix}(u_{1n}-u_{6n})-x_{6}(u_{1n}-u_{4n})\\\
-y_{6}(u_{1n}\\-u_{3n})\\\ -z_{6}(u_{1n}-u_{2n})\end{matrix}\\\\[19.91692pt]
x_{6}(v_{4n}-v_{6n})&y_{6}(v_{3n}-v_{6n})&z_{6}(v_{2n}-v_{6n})&\begin{matrix}(v_{1n}-v_{6n})-x_{6}(v_{1n}-v_{4n})\\\
-y_{6}(v_{1n}-v_{3n})\\\
-z_{6}(v_{1n}-v_{2n})\end{matrix}\end{bmatrix}_{4\times 4\,.}$ (39)

It means that the matrix $\widehat{\bf K}$ is not full-rank and its
determinant is zero, i.e.,

$\text{det}(\widehat{\bf K})=0\,.$ (40)

Noting that the variables in Eq. (40) is $x_{5},y_{5},z_{5}$, the coordinates
of ${\bf X}_{5}$ and $x_{6},y_{6},z_{6}$, the coordinates of ${\bf X}_{6}$. We
do not have any variable in ${\bf P}_{n}$ in Eq. (40). To compute the
determinant of $\widehat{\bf K}$, we notice that

$\begin{split}&\begin{vmatrix}x_{5}(u_{4n}-u_{5n})&y_{5}(u_{3n}-u_{5n})\\\\[5.69054pt]
x_{5}(v_{4n}-v_{5n})&y_{5}(v_{3n}-v_{5n})\end{vmatrix}\begin{vmatrix}z_{6}(u_{2n}-u_{6n})&\begin{matrix}(u_{1n}-u_{6n})-x_{6}(u_{1n}-u_{4n})\\\
-y_{6}(u_{1n}-u_{3n})\\\ -z_{6}(u_{1n}-u_{2n})\end{matrix}\\\\[25.60747pt]
z_{6}(v_{2n}-v_{6n})&\begin{matrix}(v_{1n}-v_{6n})-x_{6}(v_{1n}-v_{4n})\\\
-y_{6}(v_{1n}-v_{3n})\\\
-z_{6}(v_{1n}-v_{2n})\end{matrix}\end{vmatrix}\\\\[5.69054pt]
&=x_{5}y_{5}z_{6}\xi^{\text{\tiny(n)}}_{34,5}\big{[}\xi^{\text{\tiny(n)}}_{12,6}-x_{6}\xi^{\text{\tiny(n)}}_{12,46}-y_{6}\xi^{\text{\tiny(n)}}_{12,36}-z_{6}\xi^{\text{\tiny(n)}}_{12,26}\big{]}\end{split}$
(41)

where $\xi^{\text{\tiny(n)}}_{34,5}$ and $\xi^{\text{\tiny(n)}}_{12,6}$ are
defined by Eq. (32), and others are given by

$\xi^{\text{\tiny(n)}}_{i_{1}i_{2},j_{1}j_{2}}\,\stackrel{{\scriptstyle\text{def}}}{{=}}\,\begin{vmatrix}u_{i_{1}n}-u_{j_{1}n}&u_{i_{2}n}-u_{j_{2}n}\\\\[2.84526pt]
v_{i_{1}n}-v_{j_{1}n}&v_{i_{2}n}-v_{j_{2}n}\end{vmatrix}.$ (42)

Now the determinant of $\widehat{\bf K}$ is computed via its $2\times 2$
blocks as follows

$\begin{split}\text{det}(\widehat{\bf
K})&=x_{5}y_{5}z_{6}\xi^{\text{\tiny(n)}}_{34,5}\big{[}\xi^{\text{\tiny(n)}}_{12,6}-x_{6}\xi^{\text{\tiny(n)}}_{12,46}-y_{6}\xi^{\text{\tiny(n)}}_{12,36}-z_{6}\xi^{\text{\tiny(n)}}_{12,26}\big{]}\\\\[1.42262pt]
&~{}~{}~{}-x_{5}y_{6}z_{5}\xi^{\text{\tiny(n)}}_{24,5}\big{[}\xi^{\text{\tiny(n)}}_{13,6}-x_{6}\xi^{\text{\tiny(n)}}_{13,46}-y_{6}\xi^{\text{\tiny(n)}}_{13,36}-z_{6}\xi^{\text{\tiny(n)}}_{13,26}\big{]}\\\\[1.42262pt]
&~{}~{}~{}+x_{6}y_{5}z_{5}\xi^{\text{\tiny(n)}}_{23,5}\big{[}\xi^{\text{\tiny(n)}}_{14,6}-x_{6}\xi^{\text{\tiny(n)}}_{14,46}-y_{6}\xi^{\text{\tiny(n)}}_{14,36}-z_{6}\xi^{\text{\tiny(n)}}_{14,26}\big{]}\\\\[1.42262pt]
&~{}~{}~{}+x_{5}y_{6}z_{6}\xi^{\text{\tiny(n)}}_{23,6}\big{[}\xi^{\text{\tiny(n)}}_{14,5}-x_{5}\xi^{\text{\tiny(n)}}_{14,45}-y_{5}\xi^{\text{\tiny(n)}}_{14,35}-z_{5}\xi^{\text{\tiny(n)}}_{14,25}\big{]}\\\\[1.42262pt]
&~{}~{}~{}-x_{6}y_{5}z_{6}\xi^{\text{\tiny(n)}}_{24,6}\big{[}\xi^{\text{\tiny(n)}}_{13,5}-x_{5}\xi^{\text{\tiny(n)}}_{13,45}-y_{5}\xi^{\text{\tiny(n)}}_{13,35}-z_{5}\xi^{\text{\tiny(n)}}_{13,25}\big{]}\\\\[1.42262pt]
&~{}~{}~{}+x_{6}y_{6}z_{5}\xi^{\text{\tiny(n)}}_{34,6}\big{[}\xi^{\text{\tiny(n)}}_{12,5}-x_{5}\xi^{\text{\tiny(n)}}_{12,45}-y_{5}\xi^{\text{\tiny(n)}}_{12,35}-z_{5}\xi^{\text{\tiny(n)}}_{12,25}\big{]}\end{split}$
(43)

We present $\text{det}(\widehat{\bf K})$ as a polynomials in which its
monomials are

$\begin{split}&x_{5}y_{5}z_{6},\,x_{5}y_{6}z_{5},\,x_{6}y_{5}z_{5},\,x_{6}y_{6}z_{5},\,x_{6}y_{5}z_{6},\,x_{5}y_{6}z_{6},\\\
&x_{5}^{2}y_{6}z_{6},\,x_{6}y_{5}^{2}z_{6},\,x_{6}y_{6}z_{5}^{2},\,x_{6}^{2}y_{5}z_{5},\,x_{5}y_{6}^{2}z_{5},\,x_{5}y_{5}z_{6}^{2}\\\
&x_{5}y_{5}x_{6}z_{6},\,x_{5}y_{5}y_{6}z_{6},\,x_{5}z_{5}x_{6}y_{6},\,x_{5}z_{5}y_{6}z_{6},\,y_{5}z_{5}x_{6}y_{6},\,y_{5}z_{5}x_{6}z_{6}\,.\end{split}$
(44)

This polynomial is

$\text{det}(\widehat{\bf
K})=b_{0}x_{5}y_{5}z_{6}+b_{1}x_{5}y_{6}z_{5}+\cdots+b_{17}y_{5}z_{5}x_{6}z_{6}\,,$
(45)

where

$\begin{split}b_{0}&=-b_{11}=\xi^{\text{\tiny(n)}}_{34,5}\xi^{\text{\tiny(n)}}_{12,6},~{}\hskip
10.66977ptb_{1}\hskip
0.7113pt=-b_{10}=\xi^{\text{\tiny(n)}}_{42,5}\xi^{\text{\tiny(n)}}_{13,6},~{}\hskip
10.66977ptb_{2}=-b_{9}\hskip
4.2679pt=\xi^{\text{\tiny(n)}}_{23,5}\xi^{\text{\tiny(n)}}_{14,6}\,,\\\\[2.84526pt]
b_{3}&=-b_{8}\hskip
3.55658pt=\xi^{\text{\tiny(n)}}_{34,6}\xi^{\text{\tiny(n)}}_{12,5},~{}\hskip
10.66977ptb_{4}=-b_{7}\hskip
4.97922pt=\xi^{\text{\tiny(n)}}_{42,6}\xi^{\text{\tiny(n)}}_{13,5},~{}~{}~{}~{}\,b_{5}=-b_{6}\hskip
2.84526pt=\xi^{\text{\tiny(n)}}_{23,6}\xi^{\text{\tiny(n)}}_{14,5}\,,\\\\[2.84526pt]
b_{12}&=\xi^{\text{\tiny(n)}}_{24,6}\xi^{\text{\tiny(n)}}_{13,45}-\xi^{\text{\tiny(n)}}_{34,5}\xi^{\text{\tiny(n)}}_{12,46},~{}b_{13}=\xi^{\text{\tiny(n)}}_{32,6}\xi^{\text{\tiny(n)}}_{14,35}-\xi^{\text{\tiny(n)}}_{34,5}\xi^{\text{\tiny(n)}}_{12,36},~{}b_{14}=\xi^{\text{\tiny(n)}}_{24,5}\xi^{\text{\tiny(n)}}_{13,46}-\xi^{\text{\tiny(n)}}_{34,6}\xi^{\text{\tiny(n)}}_{12,45}\,,\\\\[2.84526pt]
b_{15}&=\xi^{\text{\tiny(n)}}_{24,5}\xi^{\text{\tiny(n)}}_{13,26}-\xi^{\text{\tiny(n)}}_{23,6}\xi^{\text{\tiny(n)}}_{14,25},~{}b_{16}=\xi^{\text{\tiny(n)}}_{32,5}\xi^{\text{\tiny(n)}}_{14,36}-\xi^{\text{\tiny(n)}}_{34,6}\xi^{\text{\tiny(n)}}_{12,35},~{}b_{17}=\xi^{\text{\tiny(n)}}_{24,6}\xi^{\text{\tiny(n)}}_{13,25}-\xi^{\text{\tiny(n)}}_{23,5}\xi^{\text{\tiny(n)}}_{14,26}\,.\end{split}$
(46)

We use the following explanation

$\begin{split}\xi^{\text{\tiny(n)}}_{i_{1}j_{1},i_{2}j_{2}}-\xi^{\text{\tiny(n)}}_{i_{1}j_{1},i_{3}j_{2}}&=(u_{i_{1}n}-u_{i_{2}n})(v_{j_{1}n}-v_{j_{2}n})-(v_{i_{1}n}-v_{i_{2}n})(u_{j_{1}n}-u_{j_{2}n})\\\
&~{}~{}-(u_{i_{1}n}-u_{i_{3}n})(v_{j_{1}n}-v_{j_{2}n})+(v_{i_{1}n}-v_{i_{3}n})(u_{j_{1}n}-u_{j_{2}n})\\\
&=(u_{i_{3}n}-u_{i_{2}n})(v_{j_{1}n}-v_{j_{2}n})-(v_{i_{3}n}-v_{i_{2}n})(u_{j_{1}n}-u_{j_{2}n})\\\
&=\xi^{\text{\tiny(n)}}_{i_{3}j_{1},i_{2}j_{2}}\,,\end{split}$ (47)

to obtain

$\begin{split}b_{4}+b_{12}&=\xi^{\text{\tiny(n)}}_{24,6}\big{(}\xi^{\text{\tiny(n)}}_{13,45}-\xi^{\text{\tiny(n)}}_{13,5}\big{)}-\xi^{\text{\tiny(n)}}_{34,5}\xi^{\text{\tiny(n)}}_{12,46}=\xi^{\text{\tiny(n)}}_{24,6}\xi^{\text{\tiny(n)}}_{34,5}-\xi^{\text{\tiny(n)}}_{34,5}\xi^{\text{\tiny(n)}}_{12,46}=-\xi^{\text{\tiny(n)}}_{34,5}\xi^{\text{\tiny(n)}}_{12,6}\\\
&=-b_{0}\,,\end{split}$ (48)

and similar others

$\begin{split}&b_{13}+b_{5}+b_{0}=0,~{}~{}b_{14}+b_{3}+b_{1}=0,~{}~{}b_{15}+b_{5}+b_{1}=0,\\\
&b_{16}+b_{3}+b_{2}=0,~{}~{}b_{17}+b_{4}+b_{2}=0,~{}~{}b_{16}+b_{15}+b_{12}=0,~{}~{}b_{17}+b_{14}+b_{13}=0\,.\\\\[-8.53581pt]
\end{split}$ (49)

Combining Eq. (45), Eq. (46), Eq. (48) and Eq. (49), the determinant of
$\widehat{\bf K}$ can be presented as a polynomial with five monomials as
follows.

$\begin{split}&\text{det}(\widehat{\bf
K})={\begin{bmatrix}b_{0}\\\\[2.84526pt] b_{1}\\\\[2.84526pt]
b_{2}\\\\[2.84526pt] b_{3}\\\\[2.84526pt]
b_{4}\end{bmatrix}^{T}\begin{bmatrix}x_{5}z_{6}\big{[}y_{5}(1-x_{6}-y_{6}-z_{6})-y_{6}(1-x_{5}-y_{5}-z_{5})\big{]}\\\\[2.84526pt]
x_{5}y_{6}\big{[}z_{5}(1-x_{6}-y_{6}-z_{6})-z_{6}(1-x_{5}-y_{5}-z_{5})\big{]}\\\\[2.84526pt]
x_{6}y_{5}z_{5}(1-x_{6}-y_{6}-z_{6})-x_{5}y_{6}z_{6}(1-x_{5}-y_{5}-z_{5})\\\\[2.84526pt]
(x_{6}z_{5}-x_{5}z_{6})y_{6}(1-x_{5}-y_{5}-z_{5})\\\\[2.84526pt]
(x_{6}y_{5}-x_{5}y_{6})z_{6}(1-x_{5}-y_{5}-z_{5})\end{bmatrix}}\end{split}$
(50)

Since $\text{det}(\widehat{\bf K})=0$, the two column-vectors in Eq. (50) are
orthogonal. Note that $[b_{0}\,,\,b_{1}\,,\,b_{2}\,,\,b_{3}\,,\,b_{4}]$ is the
$n$th row of the matrix ${\bf\Lambda}$ in Theorem 2. Hence all the rows of
this matrix are orthogonal to the non-zero vector constructed by the
coordinates of ${\bf X}_{5}$ and ${\bf X}_{6}$ given by Eq. (50). In another
word, the $N\times 5$ matrix ${\bf\Lambda}$ has the rank at most 4. ∎

Similarly developing the rank property to the self-estimation as we do with
Theorem 1 and Proposition 1 in the last sub-section, we derive Proposition 2
as an application of the rank property proposed by Theorem 2 on the self-
estimation.

######  Proposition 2.

Assuming that $N\geq 6$, the functions of $u_{61}$ and $v_{61}$ from the
remain coordinates are given by

$\begin{bmatrix}u_{61}\\\
v_{61}\end{bmatrix}=-\begin{bmatrix}\hat{\alpha}_{1|2,3,4,5}&\hat{\beta}_{1|2,3,4,5}\\\
\vdots&\vdots\\\
\hat{\alpha}_{1|j_{1}j_{2}j_{3}j_{4}}&\hat{\beta}_{1|j_{1}j_{2}j_{3}j_{4}}\\\
\vdots&\vdots\\\
\hat{\alpha}_{1|N-3,\ldots,N}&\hat{\beta}_{1|N-3,\ldots,N}\end{bmatrix}^{\dagger}\begin{bmatrix}\hat{\gamma}_{1|2,3,4,5}\\\
\vdots\\\ \hat{\gamma}_{1|j_{1}j_{2}j_{3}j_{4}}\\\ \vdots\\\
\hat{\gamma}_{1|N-3,\ldots,N}\end{bmatrix}$ (51)

for all $2\leq j_{1}<j_{2}<j_{3}<j_{4}\leq N$, where

$\begin{split}\hat{\alpha}_{1|j_{1}j_{2}j_{3}j_{4}}&=\begin{vmatrix}\begin{matrix}\xi^{\text{\tiny(1)}}_{34,5}(v_{11}-v_{21})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{42,5}(v_{11}-v_{31})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{23,5}(v_{11}-v_{41})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{12,5}(v_{31}-v_{41})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{13,5}(v_{41}-v_{21})\end{matrix}~{}&~{}{\bf
A}_{j_{1}j_{2}j_{3}j_{4}}\end{vmatrix}_{5\times 5}\quad,\\\\[8.53581pt]
\hat{\beta}_{1|j_{1}j_{2}j_{3}j_{4}}&=\begin{vmatrix}\begin{matrix}\xi^{\text{\tiny(1)}}_{34,5}(u_{21}-u_{11})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{42,5}(u_{31}-u_{11})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{23,5}(u_{41}-u_{11})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{12,5}(u_{41}-u_{31})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{13,5}(u_{21}-u_{41})\end{matrix}~{}&~{}{\bf
A}_{j_{1}j_{2}j_{3}j_{4}}\end{vmatrix}_{5\times 5}\quad,\\\\[8.53581pt]
\hat{\gamma}_{1|j_{1}j_{2}j_{3}j_{4}}&=\begin{vmatrix}\begin{matrix}\xi^{\text{\tiny(1)}}_{34,5}(u_{11}v_{21}-u_{21}v_{11})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{42,5}(u_{11}v_{31}-u_{31}v_{11})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{23,5}(u_{11}v_{41}-u_{41}v_{11})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{12,5}(u_{31}v_{41}-u_{41}v_{31})\\\\[2.84526pt]
\xi^{\text{\tiny(1)}}_{13,5}(u_{41}v_{21}-u_{21}v_{41})\end{matrix}~{}&~{}{\bf
A}_{j_{1}j_{2}j_{3}j_{4}}\end{vmatrix}_{5\times 5}\quad,\end{split}$ (52)

and

${\bf
A}_{j_{1}j_{2}j_{3}j_{4}}={\begin{bmatrix}\xi^{\text{\tiny($j_{1}$)}}_{34,5}\xi^{\text{\tiny($j_{1}$)}}_{12,6}&\xi^{\text{\tiny($j_{2}$)}}_{34,5}\xi^{\text{\tiny($j_{2}$)}}_{12,6}&\xi^{\text{\tiny($j_{3}$)}}_{34,5}\xi^{\text{\tiny($j_{3}$)}}_{12,6}&\xi^{\text{\tiny($j_{4}$)}}_{34,5}\xi^{\text{\tiny($j_{4}$)}}_{12,6}\\\\[8.53581pt]
\xi^{\text{\tiny($j_{1}$)}}_{42,5}\xi^{\text{\tiny($j_{1}$)}}_{13,6}&\xi^{\text{\tiny($j_{2}$)}}_{42,5}\xi^{\text{\tiny($j_{2}$)}}_{13,6}&\xi^{\text{\tiny($j_{3}$)}}_{42,5}\xi^{\text{\tiny($j_{3}$)}}_{13,6}&\xi^{\text{\tiny($j_{4}$)}}_{42,5}\xi^{\text{\tiny($j_{4}$)}}_{13,6}\\\\[8.53581pt]
\xi^{\text{\tiny($j_{1}$)}}_{23,5}\xi^{\text{\tiny($j_{1}$)}}_{14,6}&\xi^{\text{\tiny($j_{2}$)}}_{23,5}\xi^{\text{\tiny($j_{2}$)}}_{14,6}&\xi^{\text{\tiny($j_{3}$)}}_{23,5}\xi^{\text{\tiny($j_{3}$)}}_{14,6}&\xi^{\text{\tiny($j_{4}$)}}_{23,5}\xi^{\text{\tiny($j_{4}$)}}_{14,6}\\\\[8.53581pt]
\xi^{\text{\tiny($j_{1}$)}}_{12,5}\xi^{\text{\tiny($j_{1}$)}}_{34,6}&\xi^{\text{\tiny($j_{2}$)}}_{12,5}\xi^{\text{\tiny($j_{2}$)}}_{34,6}&\xi^{\text{\tiny($j_{3}$)}}_{12,5}\xi^{\text{\tiny($j_{3}$)}}_{34,6}&\xi^{\text{\tiny($j_{4}$)}}_{12,5}\xi^{\text{\tiny($j_{4}$)}}_{34,6}\\\\[7.11317pt]
\xi^{\text{\tiny($j_{1}$)}}_{13,5}\xi^{\text{\tiny($j_{1}$)}}_{42,6}&\xi^{\text{\tiny($j_{2}$)}}_{13,5}\xi^{\text{\tiny($j_{2}$)}}_{42,6}&\xi^{\text{\tiny($j_{3}$)}}_{13,5}\xi^{\text{\tiny($j_{3}$)}}_{42,6}&\xi^{\text{\tiny($j_{4}$)}}_{13,5}\xi^{\text{\tiny($j_{4}$)}}_{42,6}\end{bmatrix}_{5\times
4\,.}}$ (53)

###### Proof.

For any five indices $1$ and $2\leq j_{1}<j_{2}<j_{3}<j_{4}\leq N$, we use
five rows of ${\bf\Lambda}$ in Eq. (31) corresponding with these five indices
to get the $5\times 5$ sub-matrix ${\bf\Lambda}_{1j_{1}j_{2}j_{3}j_{4}}$. The
rank property of ${\bf\Lambda}$ yields

$\text{det}\big{(}{\bf\Lambda}_{1j_{1}j_{2}j_{3}j_{4}}\big{)}=0\,,$ (54)

or

$\begin{bmatrix}\xi^{\text{\tiny(1)}}_{34,5}\xi^{\text{\tiny(1)}}_{12,6}\\\\[8.53581pt]
-\xi^{\text{\tiny(1)}}_{42,5}\xi^{\text{\tiny(1)}}_{13,6}\\\\[8.53581pt]
\xi^{\text{\tiny(1)}}_{23,5}\xi^{\text{\tiny(1)}}_{14,6}\\\\[8.53581pt]
-\xi^{\text{\tiny(1)}}_{12,5}\xi^{\text{\tiny(1)}}_{34,6}\\\\[8.53581pt]
\xi^{\text{\tiny(1)}}_{13,5}\xi^{\text{\tiny(1)}}_{42,6}\end{bmatrix}^{T}\begin{bmatrix}\big{|}{\bf\Lambda}_{1j_{1}j_{2}j_{3}j_{4}}^{1}\big{|}\\\\[8.53581pt]
\big{|}{\bf\Lambda}_{1j_{1}j_{2}j_{3}j_{4}}^{2}\big{|}\\\\[8.53581pt]
\big{|}{\bf\Lambda}_{1j_{1}j_{2}j_{3}j_{4}}^{3}\big{|}\\\\[8.53581pt]
\big{|}{\bf\Lambda}_{1j_{1}j_{2}j_{3}j_{4}}^{4}\big{|}\\\\[8.53581pt]
\big{|}{\bf\Lambda}_{1j_{1}j_{2}j_{3}j_{4}}^{5}\big{|}\end{bmatrix}~{}=0\,.$
(55)

Since

$\xi^{\text{\tiny(1)}}_{i_{1}i_{2},6}=(u_{i_{1}1}v_{i_{2}1}-u_{i_{2}1}v_{i_{1}1})+(v_{i_{1}1}-v_{i_{2}1})u_{61}+(u_{i_{2}1}-u_{i_{1}1})v_{61}$
(56)

Eq. (55) means

$\hat{\alpha}_{1|j_{1}j_{2}j_{3}j_{4}}u_{61}+\hat{\beta}_{1|j_{1}j_{2}j_{3}j_{4}}v_{61}+\hat{\gamma}_{1|j_{1}j_{2}j_{3}j_{4}}=0\,,$
(57)

where
$\hat{\alpha}_{1|j_{1}j_{2}j_{3}j_{4}},\hat{\beta}_{1|j_{1}j_{2}j_{3}j_{4}}$
and $\hat{\gamma}_{1|j_{1}j_{2}j_{3}j_{4}}$ are given by Eq. (52) and Eq.
(53). Let four indices $(j_{1},j_{2},j_{3},j_{4})$ run from the first
$(2,3,4,5)$ to the last $(N-3,N-2,N-1,N)$, we get a similar formula of Eq.
(29) that

$\begin{bmatrix}\hat{\alpha}_{1|2,3,4,5}&\hat{\beta}_{1|2,3,4,5}\\\
\vdots&\vdots\\\
\hat{\alpha}_{1|j_{1}j_{2}j_{3}j_{4}}&\hat{\beta}_{1|j_{1}j_{2}j_{3}j_{4}}\\\
\vdots&\vdots\\\
\hat{\alpha}_{1|N-3,\ldots,N}&\hat{\beta}_{1|N-3,\ldots,N}\end{bmatrix}\begin{bmatrix}u_{61}\\\
v_{61}\end{bmatrix}=-\begin{bmatrix}\hat{\gamma}_{1|2,3,4,5}\\\ \vdots\\\
\hat{\gamma}_{1|j_{1}j_{2}j_{3}j_{4}}\\\ \vdots\\\
\hat{\gamma}_{1|N-3,\ldots,N}\end{bmatrix}\,.$ (58)

When $N\geq 6$, the matrix in the left side of Eq. (58) with the size
${N-1\choose 4}\times 2$ is always full rank. So Eq. (58) and Eq. (51) are
equivalent. Hence, Proposition 2 is correct. ∎

##  4 Correspondences Refinement

In this section, we study how to apply Theorem 1, Theorem 2, Proposition 1 and
Proposition 2 on refining correspondences. More precisely, we study three
applications that (i) the correspondences refinement based on Theorem 1, (ii)
the outliers recognition based on Theorem 1, and (iii) the self
correspondences estimation based on Proposition 1 and Proposition 2. Combining
these three applications, we finally propose an algorithm, named _Main
Algorithm_ , to derive better correspondences from their observations.

###  4.1 Correspondences Refinement

The $M\times 9$ matrix ${\bf\Gamma}$ given by Eq. (14) in Theorem 1 and the
$N\times 5$ matrix ${\bf\Lambda}$ given by Eq. (31) in Theorem 2 for the
perfect correspondences (the ground-truths) without noise are rank deficient.
With a set of corrupted noisy correspondence observations, the two matrices
will be full rank. The utilization of Theorem 1 and Theorem 2 for the
application of _correspondences refinement_ is to force the rank deficient of
${\bf\Gamma}$ and ${\bf\Lambda}$. It can be achieved through _singular value
decomposition_ (SVD) and the correspondences retrieved from the approximations
will give the refined correspondences.

In the case for Theorem 1, for any correspondences from two images and at
least nine key-points we first form the matrix ${\bf\Gamma}$ and apply the
SVD. By keeping the largest eight singular values and setting the last to
zero, an improved ${\bf\Gamma}$ can be obtained. The second, third, forth and
fifth columns of this improvement will give the enhanced correspondences for
the associated two images. Notice that the rank deficient property of
${\bf\Gamma}$ is still correct when these correspondences are transformed by
any translation, rotation or reflection. Thus, we fix these ambiguities by
finding an optimal translation, rotation and reflection to transform the
enhanced correspondences close to the observed correspondences. We repeat the
same processing for all two images and at least nine key-points, collect all
enhanced correspondences, take their medians corresponding with each image
point, and iterate a few times. This algorithm is called the _Correspondences
refinement_ and presented carefully by Algorithm 1.

For Theorem 2, we easily obtain the improved ${\bf\Lambda}$ by applying SVD,
keeping the largest four singular values and setting the last to zero as we do
with ${\bf\Gamma}$. However, it seems very difficult to extract the enhanced
correspondences from the improvement of ${\bf\Lambda}$. In this work, we have
not done with this problem, and it will be our the future work.

Algorithm 1 Correspondences Refinement

Input: $\big{\\{}\hat{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}$ : Correspondences.

Implementation:

_Repeat several times the following steps:_

1. $\mathcal{X}_{mn}\longleftarrow\emptyset$ : A set to store all candidates for refining $\hat{\bf x}_{m}^{\text{\tiny(n)}}$.

2. $\bar{\bf x}_{m}^{\text{\tiny(n)}}~{}~{}\longleftarrow~{}\hat{\bf x}_{m}^{\text{\tiny(n)}}$ for all $n,m$.

3. For all $1\leq n_{1}<n_{2}\leq N$

3.1. ${\bf\Gamma}~{}\overset{\eqref{eq13}\text{ in
Theorem~{}\ref{Thm:RanktwoView}}}{\longleftarrow}~{}\Bigg{\\{}\begin{bmatrix}u_{m}\\\\[2.84526pt]
v_{m}\end{bmatrix}\stackrel{{\scriptstyle\text{def}}}{{=}}\bar{\bf
x}_{m}^{\text{\tiny($n_{1}$)}}~{}\text{ and
}~{}\begin{bmatrix}u^{\prime}_{m}\\\\[2.84526pt]
v^{\prime}_{m}\end{bmatrix}\stackrel{{\scriptstyle\text{def}}}{{=}}\bar{\bf
x}_{m}^{\text{\tiny($n_{2}$)}}\Bigg{\\}}^{M}_{m=1}$

3.2. Apply SVD and use the largest 8 singular values only to construct
$\widehat{\bf\Gamma}$ as a refinement of ${\bf\Gamma}$.

3.3. Find the optimal candidates $\big{\\{}\breve{\bf
x}_{1}^{\text{\tiny($n_{1}$)}},\breve{\bf
x}_{1}^{\text{\tiny($n_{2}$)}},\ldots,\breve{\bf
x}_{M}^{\text{\tiny($n_{1}$)}},\breve{\bf
x}_{M}^{\text{\tiny($n_{2}$)}}\big{\\}}$ :

a. $\breve{\bf
x}_{m}^{\text{\tiny($n_{1}$)}}\leftarrow\begin{bmatrix}\widehat{\bf\Gamma}_{m,2}\\\\[1.42262pt]
\widehat{\bf\Gamma}_{m,3}\end{bmatrix}$ and $\breve{\bf
x}_{m}^{\text{\tiny($n_{2}$)}}\leftarrow\begin{bmatrix}\widehat{\bf\Gamma}_{m,4}\\\\[1.42262pt]
\widehat{\bf\Gamma}_{m,5}\end{bmatrix}$ for $m=1,\ldots,M,$ where
$\widehat{\bf\Gamma}_{i,j}$ is the $(i,j)$th element of $\widehat{\bf\Gamma}$.

b. To avoid the ambiguities of translations, rotations and reflections we use
the optimal translation, rotation and reflection to change
$\big{\\{}\breve{\bf x}_{1}^{\text{\tiny($n_{1}$)}},\breve{\bf
x}_{1}^{\text{\tiny($n_{2}$)}},\ldots,\breve{\bf
x}_{M}^{\text{\tiny($n_{1}$)}},\breve{\bf
x}_{M}^{\text{\tiny($n_{2}$)}}\big{\\}}$ such that

$\sum^{2}_{j=1}\sum^{M}_{m=1}\big{\|}\breve{\bf
x}_{m}^{\text{\tiny($n_{j}$)}}-\hat{\bf
x}_{m}^{\text{\tiny($n_{j}$)}}\big{\|}^{2}_{2}\quad\longrightarrow\quad\text{minimum\,
.}$

c. Store $\breve{\bf x}_{m}^{\text{\tiny($n_{1}$)}}$ to $\mathcal{X}_{mn_{1}}$
and $\breve{\bf x}_{m}^{\text{\tiny($n_{2}$)}}$ to $\mathcal{X}_{mn_{2}}$ .

4. For all $n,m$, obtain the refinement $\bar{\bf x}_{m}^{\text{\tiny(n)}}$ of $\hat{\bf x}_{m}^{\text{\tiny(n)}}$, by taking the _median_ of all elements in $\mathcal{X}_{mn}$.

Output: $\big{\\{}\bar{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\bar{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\bar{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}$ : The refinements.

###  4.2 Outliers Recognition

The Algorithm 1, _Correspondences Refinement_ , gives us the refined
correspondences from the observed correspondences. When the noises are absent,
i.e., the observations are the ground-truths, a difference between all the
refinements and all the observations will be zero. We expect this difference
as a parameter to evaluate how large the noises are in the observations. The
small difference confirms the very good observed correspondences and vice
versa, the large difference yields the bad ones. In addition, if the
difference from all correspondences is small but a difference from one image
point and its refinement is large, we will recognize this image point an
outlier. Here we emphasize that the concept _outlier_ is applied for an image
point, not for a correspondence. Thus, an outlier is an $2\times 1$ vector in
which the first coordinate (an integer number between one and $N$) points to
the image and the second one (an integer number between one and $M$) indicates
the point.

Following the above explanation, we propose Algorithm 2, named _Outliers
recognition_ , to detect outliers from the observations. Given a threshold
$\theta$, we detect an outlier of an image point by evaluating an Euclidean
distance between this image point and its refined image point we get from the
_Correspondences refinement_ algorithm. If this distance is larger than the
threshold $\theta$, this image point is an outlier. Note that coordinates of
image points are integer numbers that are bounded by zero and two sizes of
images. In this work, we expect to obtain correspondences in which their
errors are smaller than 50 pixels, thus we often choose $\theta$ as an integer
number between 20 and 70.

Algorithm 2 Outliers Recognition

Input: $\big{\\{}\hat{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}$ : Correspondences

$\theta$ : A threshold to recognize outliers.

Implementation:

1. $\mathcal{O}\longleftarrow\emptyset$ : A set to store indices of outliers.

2. Until no new outliers are found in below steps:

2.1 $\big{\\{}\bar{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\cdots\leftrightarrow\bar{\bf
x}_{m}^{\text{\tiny(N)}}\big{\\}}\overset{\text{Correspondences
Refinement}}{\longleftarrow}\big{\\{}\hat{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\cdots\leftrightarrow\hat{\bf
x}_{m}^{\text{\tiny(N)}}\big{\\}}$.

2.2 For all $1\leq n\leq N$ and $1\leq m\leq M$, if $\|\hat{\bf
x}_{m}^{\text{\tiny(n)}}-\bar{\bf x}_{m}^{\text{\tiny(n)}}\|_{2}\geq\theta$

a. A new outlier $\hat{\bf x}_{m}^{\text{\tiny(n)}}$ is found: Adding the
index $[n,m]^{T}$ to $\mathcal{O}$.

b. Remove $\hat{\bf x}_{m}^{\text{\tiny(n)}}$ from $\big{\\{}\hat{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\cdots\leftrightarrow\hat{\bf
x}_{m}^{\text{\tiny(N)}}\big{\\}}$.

c. Repeat steps 2.1 and 2.2.

Output: $\mathcal{O}$ : The indices of outliers.

###  4.3 Self Correspondences Estimation

Given the two-correspondences of at least ten key-points $\\{\hat{\bf
x}_{m_{i}}^{\text{\tiny(n)}}\leftrightarrow\hat{\bf
x}_{m_{i}}^{\text{\tiny(n')}}\\}^{K}_{i=1}$ $(K\geq 10)$, Proposition 1
proposes the closed-form solution for one image point, for example $\hat{\bf
x}_{m_{j}}^{\text{\tiny(n)}}$, from others. This result tells us to think
about the situation that if the image point $\hat{\bf
x}_{m_{j}}^{\text{\tiny(n)}}$ cannot observed or it is an outlier, while
others from the at least ten two-correspondences are good estimations, we can
recover the value for $\hat{\bf x}_{m_{j}}^{\text{\tiny(n)}}$ based on the
closed-form given by Proposition 1. Similarly, given the ‘at least
six’-correspondences of six key-points, Proposition 2 gives a closed-form
solution for any image point from the others. Thus, if these ‘at least
six’-correspondences contains only one outlier, this unobservable image point
or outlier can be recovered.

We notice that given an outlier, there are a lot of ‘possible’ two-
correspondences of at least ten key-points and ‘at least six’-correspondences
of six key-points containing this outlier. We use the word ‘possible’ to
emphasize that these two- and ‘at least six’-correspondences has only one
outlier. For each ‘possible’ correspondences, we get one candidate for this
outlier. Thus, there are lots of candidates for each outlier. From these
candidates, we can take their average or their median to recover the value of
the outlier. In this work, we use the median as Algorithm 3 _Self estimation_.

Algorithm 3 Self Estimation

Input: $\big{\\{}\hat{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}$ : Correspondences

$\mathcal{O}$ : The indices of outliers.

Implementation:

For each outlier labeled by the index $[n,m]^{T}$ in $\mathcal{O}$, we re-
estimate a value for $\hat{\bf x}_{m}^{\text{\tiny(n)}}$ by following:

1. $\mathcal{C}_{mn}\longleftarrow\emptyset$ : A set to store all candidates of the outlier $\hat{\bf x}_{m}^{\text{\tiny(n)}}$.

2. _Use Theorem 1:_ For all $1\leq n^{\prime}\leq N$ such that $n^{\prime}\neq n$ and for all $1\leq m_{1}<m_{2}<m_{3}<m_{4}<m_{5}<m_{6}<m_{7}<m_{8}\leq M$ such that $m\notin\\{m_{1},m_{2},m_{3},m_{4},m_{5},m_{6},m_{7},m_{8}\\}$,

2.1.
$\big{\\{}\alpha_{m|m_{1}\ldots,m_{8}},\beta_{m|m_{1},\ldots,m_{8}},\gamma_{m|m_{1},\ldots,m_{8}}\big{\\}}\longleftarrow\eqref{eq22}$
when

$M$-indices $\\{1,2,\ldots,9\\}\longleftarrow\\{m,m_{1},\ldots,m_{8}\\}$ and
$\hat{\bf x}_{m_{i}}^{\text{\tiny(n)}}=[u_{m_{i}},v_{m_{i}}]^{T}$ , $\hat{\bf
x}_{m_{i}}^{\text{\tiny(n')}}=[u^{\prime}_{m_{i}},v^{\prime}_{m_{i}}]^{T}$.

2.2. $\breve{\bf
x}_{m}^{\text{\tiny(n)}}~{}\overset{\eqref{eq23}}{\longleftarrow}~{}\big{\\{}\alpha_{m|m_{1}\ldots,m_{8}}\,,\,\beta_{m|m_{1},\ldots,m_{8}}\,,\,\gamma_{m|m_{1},\ldots,m_{8}}\big{\\}}$

2.3. add the candidate $\breve{\bf x}_{m}^{\text{\tiny(n)}}$ to
$\mathcal{C}_{mn}$.

3. _Use Theorem 2:_ For all $1\leq m_{1}<m_{2}<m_{3}<m_{4}<m_{5}\leq M$ and for all $1\leq n_{1}<n_{2}<n_{3}<n_{4}\leq N$ such that $m\notin\\{m_{1},m_{2},m_{3},m_{4},m_{5}\\}$ and $n\notin\\{n_{1},n_{2},n_{3},n_{4}\\}$

3.1.
$\big{\\{}\hat{\alpha}_{n|n_{1}n_{2}n_{3}n_{4}},\hat{\beta}_{n|n_{1}n_{2}n_{3}n_{4}},\hat{\gamma}_{n|n_{1}n_{2}n_{3}n_{4}}\big{\\}}\longleftarrow\eqref{eq42}$
when

$N$-indices $\\{1,2,3,4,5\\}\leftarrow\\{n,n_{1},n_{2},n_{3},n_{4}\\}$,
$M$-indices $\\{1,2,3,4,5,6\\}\leftarrow\\{m,m_{1},m_{2},m_{3},m_{4},m_{5}\\}$

3.2. $\breve{\bf
x}_{m}^{\text{\tiny(n)}}~{}\overset{\eqref{eq44}}{\longleftarrow}~{}\big{\\{}\hat{\alpha}_{n|n_{1}n_{2}n_{3}n_{4}}\,,\,\hat{\beta}_{n|n_{1}n_{2}n_{3}n_{4}}\,,\,\hat{\gamma}_{n|n_{1}n_{2}n_{3}n_{4}}\big{\\}}$

3.3. add the candidate $\breve{\bf x}_{m}^{\text{\tiny(n)}}$ to
$\mathcal{C}_{mn}$.

4. Re-estimate $\hat{\bf x}_{m}^{\text{\tiny(n)}}$ by taking the _median_ of all elements in $\mathcal{C}_{mn}$.

Output: $\big{\\{}\hat{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}$ : Correspondences

in which the outliers in $\mathcal{O}$ are re-estimated.

###  4.4 Main algorithm for refinement

Three applications for the refinement of correspondences are proposed
separately in the last three sections. This section studies how to combine
these three applications to get an optimal algorithm on refining
correspondences. Firstly, we mention that the _Outliers recognition_ depends
on the _Correspondences refinement_ as showing in its step 2.1. In addition,
if there are no outliers finding by the _Outlier recognition_ , the
refinements from the _Correspondences refinement_ within and without the two
algorithms _Outliers recognition_ and _Self estimations_ are the same. It is
obvious that the refinement from the _Correspondences refinement_ will be
better if we remove all outliers from its input. Therefore, an iterative
process - in which the _Correspondences refinement_ will help the _Outliers
recognition_ on detecting correctly outliers, and vice versa the _Outliers
recognition_ helps the _Correspondences refinement_ to obtain better
refinements when some outliers are removed or recovered - is needed. Secondly,
to guarantee the very good input for the _Correspondences refinement_ , the
threshold $\theta$ used on detecting outliers should be small. As a
consequence of the small threshold $\theta$, some good observed image points
can be recognized as outliers. However if all the remain image points (not the
outliers detected by the _Outliers recognition_) are good, the _Self
estimation_ will give back good values for these good observed image points.
Moreover, this algorithm can give good values for the real outliers.

From the above two discussions, we propose a combination of the three
algorithms _Correspondences refinement_ , _Outliers recognition_ and _Self
estimation_ as a final algorithm for refining the observed correspondences. It
is the _Main algorithm_ and given by Algorithm 4. There are $\kappa$
iterations and each iteration is an arrangement that the _Correspondences
refinement_ and then the _Outliers recognition_ are implemented via the step
1, then the _Self estimation_ is implemented via the step 2 and the
_Correspondences refinement_ is again finished via the step 3. In each
iteration we use the different threshold $\theta_{i}$ to detect the outliers
$\mathcal{O}_{i}$. These threshold are a descending series, i.e.,
$\theta_{1}>\theta_{2}>\cdots>\theta_{\kappa}$.

Logically, the iterative is stopped when the threshold is too small but there
are no outlier finding by the step 2. To simplify, we fix the number of
iterative $\kappa$ to three and choose the thresholds of 60, 40 and 20 for
each iterative in the hope that the final refinement will have an error of
about 50 pixels.

Algorithm 4 Main Algorithm

Input: $\big{\\{}\hat{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\hat{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}$ : Correspondences

$\theta_{1},\theta_{2},\ldots,\theta_{\kappa}$: A sequence of thresholds to
recognize outliers

Implementation:

_Repeat $\kappa$ times the following steps:_

(Assuming that we are at $i$th time)

1. $\mathcal{O}_{i}~{}\overset{\text{Outliers Recognition}}{\longleftarrow}~{}\Big{\\{}\big{\\{}\hat{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\hat{\bf x}^{\text{\tiny(N)}}_{m}\big{\\}}~{},~{}~{}\theta_{i}\Big{\\}}$.

2. $\big{\\{}\breve{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\breve{\bf x}^{\text{\tiny(N)}}_{m}\big{\\}}\overset{\text{Self Estimation}}{\longleftarrow}\Big{\\{}\big{\\{}\hat{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\hat{\bf x}^{\text{\tiny(N)}}_{m}\big{\\}}~{},~{}\mathcal{O}_{i}\Big{\\}}$.

3. $\big{\\{}\bar{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\bar{\bf x}^{\text{\tiny(N)}}_{m}\big{\\}}\overset{\text{Correspondences Refinement}}{\longleftarrow}\big{\\{}\breve{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\breve{\bf x}^{\text{\tiny(N)}}_{m}\big{\\}}$.

4. $\hat{\bf x}_{m}^{\text{\tiny(n)}}\longleftarrow\bar{\bf x}_{m}^{\text{\tiny(n)}}$ for all $m,n$, (Update for the next time)

Output: $\big{\\{}\bar{\bf x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\bar{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\bar{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}^{M}_{m=1}$ : Refinements.

##  5 Experiments and Evaluations

###  5.1 Experiment Settings

Experiments for studying this work are from our small project on
3D-reconstructing the Buddha statue. The Buddha statue is marked by 200 small
black dots. We divide the statue by 21 areas such as the face, the left hand,
the right hand, the back, the left leg, the right leg, etc. Two hundreds
marked black dots are chosen such that each area has at least ten and at most
fifteen marked dots. To reconstruct one area we take around 20 to 30 images.
Thus, for each area we have an experiment to study the $N$-view and $M$-point
problem where $N$ is the number of images ($20\leq N\leq 30$) and $M$ is the
number of marked dots appearing in this area ($10\leq M\leq 15$).

Figure 4: An experiment of the 20-view and 10-point problem for the right
front body reconstruction. This is one from the twenty one experiments
corresponding to twenty one areas of the Buddha statue. The _red dots_ are the
ground-truths for the ten-correspondences.

To study the correspondences refinement, we manually determine the marked dots
in each image. Since the marked black dots are very clear in images, these
manual coordinates are very accurate and we use them as the ground-truths for
the correspondences. Note that in the experiment of $N$-view and $M$-point,
some images do not capture all $M$ marked dots. If the marked dot is missed on
the image, its coordinates will be -1. Concretely, let us denote

Figure 5: A process on estimating the correspondences based on the ground-
truths and SIFT and SURF algorithms. (A): original images, (B): one of the
_difference of Gaussian maps_ , (C): images with the key-points found by SIFT
and SURF, and (D): image-points (_blue squares_) are found from the key-points
(_green circles_) closest to the ground truths (_red squares_).

$\big{\\{}\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(1)}}\leftrightarrow\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(2)}}\leftrightarrow\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(3)}}\leftrightarrow\cdots\leftrightarrow\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(N)}}\big{\\}}^{M}_{m=1}$ (59)

be the ground-truths for the correspondences of the $N$-view and $M$-point.
The ground-truth $\overset{\circ}{\bf x}~{}_{m}^{\text{\tiny(n)}}$ is
$[-1,-1]^{T}$ if the $m$th marked dot is not captured by the $n$th image.
Figure 4 demonstrates an experiment of the 20-view and 10-point reconstruction
for the area ‘ _right front body_ ’. The ground-truths of ten-correspondences
in each image are manually highlighted by red dots. The first image at the
position (1,1) has only seven motions, the fifteenth image at the position
(4,3) has nine motions, and no image captures all ten.

The estimations of the correspondences are found based on the SIFT (Lowe,
1999) and SURF (Bay et al., 2006) algorithms. The code for SIFT is based on
(Lowe, 2004) and the code for SURF is based on (Evans, 2009). A process of
estimating the correspondences is explained by the pictures in Figure 5. Let
us explain how to estimate the correspondences on the first image in the
experiment given by Figure 4. The picture (A1) is the original image capturing
the right front hand of the Buddha’s statue. The seven image points from the
ten-correspondences of this experiments are marked by seven black dots. (B1)
is one of the ‘difference of Gaussian’ (DOG) map of the image. The key-points
are determined based on these DOG maps. All the key-points found by the SIFT
and SURF algorithms are red dots in the picture (C1). From lots of key-points,
since the ground-truths of the seven image points are known, as highlighted by
the ‘red dots’ in picture (D1), we easily choose the closest one and use it as
the estimation for each image point. The estimations of the seven image points
are highlighted by the ‘blue dots’, and the remain key-points are indicated by
the ‘small green dots’. The Euclidean distances between the estimations and
the ground truths are 48.54, 43.43, 32.20, 33.36, 53.60, 129.02 and 28.45
(pixels). A same process on estimating nine image points from the
correspondences in the nineteenth image is presented by (A2), (B2), (C2) and
(D2). The differences between the estimations and the ground truths are 36.02,
38.35, 76.00, 150.83, 45.81, 31.00, 48.62, 43.65 and 102.86. The average
errors of the estimations on the first image and the nineteenth image are
52.66 pixels and 63.68 pixels, respectively.

Note that without the ground truths, estimating the correspondences is a
difficult problem. Since this work is focused on studying the correspondences
refinement, not the correspondences estimation, we simplify this step by
manually determining the ground-truths for the correspondences. Thanks for
this hard work, we have total 21 experiments with 402 images and 4398 image
points. For each experiment, the ground truths are really accurate, the
estimations are reliable for some real applications on the 3D reconstruction.
Given the estimation

$\big{\\{}\hat{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\hat{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\hat{\bf
x}_{m}^{\text{\tiny(3)}}\leftrightarrow\cdots\leftrightarrow\hat{\bf
x}_{m}^{\text{\tiny(N)}}\big{\\}}^{M}_{m=1}$ (60)

we shall apply the _Main algorithm_ (Algorithm 4) to evaluate how efficient
this work is on the correspondences refinement. The number times is three
($\kappa=3$) and the sequence of thresholds
$\\{\theta_{1},\theta_{2},\theta_{3}\\}$ is $\\{60,40,20\\}$. Thus, there are
three refinements $\\{\bar{\bf x}_{m}^{\text{\tiny(n)}}\\}$ for the
estimations $\\{\hat{\bf x}_{m}^{\text{\tiny(n)}}\\}$ corresponding to (i) the
first iteration with the threshold $\theta_{1}=60$, (ii) the first and second
iterations with the thresholds $(\theta_{1},\theta_{2})=(60,40)$, and (iii)
the output of the _Main algorithm_ in which we use all three iterations. We
call these three refinements by the ‘refinements with one iteration’, the
‘refinements with two iterations’ and the ‘refinements with three iterations’,
respectively. The Euclidean distances $\|\hat{\bf
x}_{m}^{\text{\tiny(n)}}-\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(n)}}\|_{2}$ and $\|\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(n)}}\|_{2}$ are called the _point-errors_ of the
estimated and refined image points $\hat{\bf x}_{m}^{\text{\tiny(n)}}$ and
$\bar{\bf x}_{m}^{\text{\tiny(n)}}$. The mean point-errors

$\frac{1}{M}\sum^{M}_{m=1}\big{\|}\hat{\bf
x}_{m}^{\text{\tiny(n)}}-\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(n)}}\big{\|}_{2}\quad\text{and}\quad\frac{1}{M}\sum^{M}_{m=1}\big{\|}\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(n)}}\big{\|}_{2}$ (61)

are called the _image-errors_ of all the estimated and refined image points on
the $n$th image. We call these errors shortly by the _$n$ th image-errors_.
Finally, the mean image-errors

$\frac{1}{NM}\sum_{n,m}\big{\|}\hat{\bf
x}_{m}^{\text{\tiny(n)}}-\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(n)}}\big{\|}_{2}\quad\text{and}\quad\frac{1}{NM}\sum_{n,m}\big{\|}\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\overset{\circ}{\bf
x}~{}_{m}^{\text{\tiny(n)}}\big{\|}_{2}$ (62)

are called the _correspondence-errors_ of the estimated correspondences
$\\{\hat{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\hat{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\hat{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ and the refined correspondences $\\{\bar{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\bar{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\bar{\bf
x}_{m}^{\text{\tiny(N)}}\\}$. These errors together will give us a good
evaluation of the correspondences refinements. Lastly, in the _Main algorithm_
we use, the number of iterations in the _Correspondences refinement_ is 10.

###  5.2 Evaluations

Figure 6 gives an evaluation of the $21$-view and $12$-point experiment for
the area ‘front and bottom body’. The upper sub-figure presents the image-
errors of the estimations and the three refinements for twenty one images.
This result shows that for all twenty one images, the refinements with two
iterations are always better than one with one iteration, and the final
refinements corresponding with three iterations are the best. Except for the
seventeenth image, all the refinements are better than the estimations. Figure
7 shows the ground-truths, the estimations and the three refinements of the
ten from twelve image points on the twenty first image and the thirteenth
image. Based on the third refinements, the twenty first image is the best and
the thirteenth image is the worst. The image-errors on the best are 55.69 (the
estimations), 44.24 (the first refinements), 35.07 (the second refinements)
and 33.93 (the third refinements). The image-errors on the worst are 116.79
(the estimations), 106.24 (the first refinements), 81.59 (the second
refinements) and 72.67 (the third refinements). Since the differences between
the estimations and the ground-truths on the twenty first image are small, all
three its refinements are good. The point-errors of the fifth and ninth image
points on the thirteenth image are very large, so the refinements for this
image are not good. Interestingly, the differences between the estimations and
the ground-truths on the seventh image are large, but its three refinements
are very good. This is an good example for us to see the role of the _Self
estimation_ algorithm on refining the correspondences.

Figure 6: An evaluation of the 21-view and 12-motion experiment. _Upper:_ The
image-errors of twenty one images. _Lower:_ The histogram of all point-errors.
Figure 7: The ground-truths and the estimated and refined image points on the
twenty first image (upper) and the thirteenth image (lower). The ground-truths
are the _red squares_ , the estimations are the _blue squares_ , the
refinements with one iteration are the ’black plus symbols’, the refinements
with two iterations are the ‘pink plus symbols’, and the refinements with
three iterations are the ‘green cross symbols’. The ground-truth and its
estimations, refinements are grouped by the ‘black ellipses’ and indicated by
the corresponded number.

The lower sub-figure in Figure 6 presents the histogram of all point-errors on
the discussed 21-view and 12-motion experiments. If an outlier is defined by
its point-error greater than 120 and a good image point is defined by its
point-error less than 50, this histogram tells us that there are around 20
outliers and 100 good image points in the estimations, and around 4 outliers
and 140 good image points in the refinements with three iterations. The
smaller number of outliers in the refinements comparing with the estimations
validates the role of the _Outlier recognition_ , and the larger number of
good image points in the refinements comparing with the estimations again
validates the efficient of the _Self estimation_. Finally, the correspondence-
errors of this experiment are 80.95 (the estimations), 63.76 (the refinements
with one iteration), 48.63 (the refinements with two iterations) and 43.34
(the refinements with three iterations).

Figure 8: Evaluations of twenty one experiments from the 3D reconstruction of
Buddha statue. These evaluations are based on the correspondence-error for the
correspondences, the image-error for the images and the point-error for the
key-points.

Figure 8 presents the correspondence-errors, image-errors and point-errors for
all 21 experiments. The first sub-figure presents all the correspondence-
errors given by Eq. (62) for all 21 experiments. The result shows that the
correspondences refinement proposed by this paper works very well for the
eighth experiment but does not work well for the last experiment. It is
important to note that the refinements with two iterations are always better
than the refinements with one iteration, and the refinements with three
iterations are always the best. The second sub-figure simulates the histogram
of 402 image-errors given by Eq. (61) for 402 image and the last sub-figure
simulates the histogram of 4398 point-errors. The average of the point-errors
corresponding to the estimations is 76.93, and ones corresponding to the
refinements with one, two and three iterations are 67.29, 62.29 and 55.15,
respectively. Note that the averages of the point-errors and the image-errors
are the same. When we replace the average by the median, these values from the
histogram of the point-errors are 50.15 (the estimations) and (49.32, 47.59,
43.20) (the refinements with one, two and three iterations). These numbers say
that 50% estimated image points have errors of less than 50 pixels, and 50%
final refinements have errors of less than 43 pixels. The percentage of final
refinements with an error of less than 50 pixels is 57%. Let us detect the
outliers by its point-error greater than 200, then there are 274 outliers from
the estimations, 210 outliers from the refinements with one iteration, 121
outliers from the refinements with two iterations, and 51 outliers from the
refinements with three iterations. The medians from the histogram of the image
points are 63.95 (the estimations) and (56.05, 51.99, 48.16) (the refinements
with one, two and three iterations). If we define the good image by its image-
error less than 50, then the refinements with three iterations has more than
50% good images and the estimations has only 23% good image.

Overall, evaluating based on the ground-truths, an improvement of the _Main
algorithm_ , comparing with the estimations and the other two refinements
corresponding with one and two iterations, is consistent.

##  6 Conclusion

This paper concentrates on improving the correspondences accuracy, the most
important problem in the 3D reconstruction based on multiple images. Assuming
that correspondences are estimated from some existing methods, this paper
proposes an independent algorithm which is based on two rank deficient
matrices to refine them. The first $M\times 9$ rank deficient matrix is
constructed using correspondences from two images and $M$ key-points. When the
number of key-points is at least nine ($M\geq 9$), the rank deficient property
of this matrix confirms its minimum singular value should be zero. Hence, if
this value is positive, we know that there is noise. Of course if this value
is too large, we really believe that there are bad correspondences and have
some outliers in them. The second $N\times 5$ rank deficient matrix is
constructed using correspondences from $N$ images and six key-points. Similar
to the first one, when there are at least five images ($N\geq 5$), this rank
deficient property helps us to recognize noise and outliers in the
correspondences. These two rank deficient matrices are found and proven by
Theorem 1 and Theorem 2.

The proposed correspondences refinement algorithm, Algorithm 4, is validated
by a number of practical experiments. To study carefully the correspondences
refinement and other future researches such as the world points estimation
(the triangulation), the building point clouds and surface (the bundle
adjustment), etc., we generate a lot of ‘ _reliable_ ’ experiments on the
3D-reconstruction of the Buddha statue project. From this project, we have 402
images capturing 200 special world points marked on the Buddha statue. Some of
these 200 world points captured by the image are defined as the key-points on
this image. Since they are very clear by looking, we manually determine the
ground-truths for all key-points on all images. On another hand, the Euclidean
distances between these 200 world points are measured to determine their
relative positions. Thus, we emphasize that there are good experiments in
which the ground truths for the correspondences, the world points and the
projection matrices are highly accurate, for us to study the correspondences
estimation, the correspondences refinement, the world points estimations, the
building point clouds and surface, and more.

The results working on the above reliable experiments demonstrate that most of
the correspondences will be improved by the proposed algorithm on the point of
recognizing outliers, recovering missing key-points and reduce point-errors.
The refined correspondences we obtain are sufficiently good for us to continue
our researches on the world points estimation and the building point clouds.

One limitation of this paper is that it has not exploited enough Theorem 2 to
refine correspondences. We believe that if Theorem 2 is used better then _Main
algorithm_ will be better. Our future work will focus on how to exploit
Theorem 2 to improve our current results.

## References

  * Agarwal et al. [2010] Sameer Agarwal, Noah Snavely, Steven M. Seitz, and Richard Szeliski.  Bundle adjustment in the large.  In _Proceedings of the 11th European Conference on Computer Vision (ECCV), Part II_ , pages 29–42, Crete, Greece, 2010.
  * Alhichri and Kamel [2003] Haikel Salem Alhichri and Mohamed Kamel.  Virtual circles: a new set of features for fast image registration.  _Pattern Recognit. Lett._ , 24(9-10):1181–1190, 2003.
  * Barath [2018] Daniel Barath.  Five-point fundamental matrix estimation for uncalibrated cameras.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 235–243, Salt Lake City, UT, 2018.
  * Bay et al. [2006] Herbert Bay, Tinne Tuytelaars, and Luc Van Gool.  SURF: speeded up robust features.  In _Proceedings of the 9th European Conference on Computer Vision (ECCV), Part I_ , pages 404–417, Graz, Austria, 2006.
  * Bresson et al. [2017] Guillaume Bresson, Zayed Alsayed, Li Yu, and Sebastien Glaser.  Simultaneous localization and mapping: A survey of current trends in autonomous driving.  _IEEE Trans. Intell. Veh._ , 2(3):194–220, 2017\.
  * Cadena et al. [2016] Cesar Cadena, Luca Carlone, Henry Carrillo, Yasir Latif, Davide Scaramuzza, José Neira, Ian Reid, and John J. Leonard.  Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age.  _IEEE Trans. Robotics_ , 32(6):1309–1332, 2016\.
  * Chuang et al. [2021] Jen-Hui Chuang, Chih-Hui Ho, Ardian Umam, HsinYi Chen, Jenq-Neng Hwang, and Tai-An Chen.  Geometry-based camera calibration using closed-form solution of principal line.  _IEEE Trans. Image Process._ , 30:2599–2610, 2021.
  * Dollár and Zitnick [2013] Piotr Dollár and C. Lawrence Zitnick.  Structured forests for fast edge detection.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , pages 1841–1848, Sydney, Australia, 2013.
  * Evans [2009] Christopher Evans.  Notes on the OpenSURF library.  Technical report, University of Bristol, 2009.
  * Harltey and Zisserman [2006] Richard I. Harltey and Andrew Zisserman.  _Multiple view geometry in computer vision (2. ed.)_.  Cambridge University Press, 2006.
  * Hartley and Sturm [1997] Richard I. Hartley and Peter F. Sturm.  Triangulation.  _Comput. Vis. Image Underst._ , 68(2):146–157, 1997.
  * Heimann and Meinzer [2009] Tobias Heimann and Hans-Peter Meinzer.  Statistical shape models for 3D medical image segmentation: A review.  _Medical Image Anal._ , 13(4):543–563, 2009.
  * Hsieh et al. [1996] Jun-Wei Hsieh, Hong-Yuan Mark Liao, Kuo-Chin Fan, and Ming-Tak Ko.  A fast algorithm for image registration without predetermining correspondences.  In _Proceedings of the 13th International Conference on Pattern Recognition (ICPR)_ , pages 765–769, Vienna, Austria, 1996.
  * Jian and Vemuri [2011] Bing Jian and Baba C. Vemuri.  Robust point set registration using gaussian mixture models.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 33(8):1633–1645, 2011.
  * Ke and Sukthankar [2004] Yan Ke and Rahul Sukthankar.  PCA-SIFT: A more distinctive representation for local image descriptors.  In _Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 506–513, Washington, DC, 2004.
  * Lawler [1963] Eugene L Lawler.  The quadratic assignment problem.  _Management science_ , 9(4):586–599, 1963.
  * Le et al. [2018] Trung-Kien Le, King Choi Ho, and Trung-Hieu Le.  Rank properties for matrices constructed from time differences of arrival.  _IEEE Trans. Signal Process._ , 66(13):3491–3503, 2018.
  * Lowe [1999] David G. Lowe.  Object recognition from local scale-invariant features.  In _Proceedings of the International Conference on Computer Vision (ICCV)_ , pages 1150–1157, Kerkyra, Corfu, Greece, 1999.
  * Lowe [2004] David G. Lowe.  Distinctive Image Features from Scale-Invariant Keypoints.  _Int. J. Comput. Vis._ , 60(2):91–110, 2004.
  * McInerney and Terzopoulos [1996] Tim McInerney and Demetri Terzopoulos.  Deformable models in medical image analysis: A survey.  _Medical Image Anal._ , 1(2):91–108, 1996.
  * Mikolajczyk and Schmid [2005] Krystian Mikolajczyk and Cordelia Schmid.  A performance evaluation of local descriptors.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 27(10):1615–1630, 2005.
  * Munkres [1957] James Munkres.  Algorithms for the assignment and transportation problems.  _Journal of the society for industrial and applied mathematics_ , 5(1):32–38, 1957.
  * Myronenko and Song [2010] Andriy Myronenko and Xubo Song.  Point set registration: Coherent point drift.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 32(12):2262–2275, 2010.
  * Nistér [2004] David Nistér.  An efficient solution to the five-point relative pose problem.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 26(6):756–777, 2004.
  * Oliveira and Tavares [2014] Francisco P.M. Oliveira and João Manuel R.S. Tavares.  Medical image registration: A review.  _Comput Methods Biomech Biomed Engin ._ , 17(2):73–93, 2014.
  * Remondino and Fraser [2006] Fabio Remondino and Clive Fraser.  Digital camera calibration methods: Considerations and comparisons.  _Int. Arch. Photogramm. Remote Sens._ , 36(5):266–272, 2006.
  * Rosten and Drummond [2006] Edward Rosten and Tom Drummond.  Machine learning for high-speed corner detection.  In _Proceedings of the 9th European Conference on Computer Vision (ECCV), Part I_ , pages 430–443, Graz, Austria, 2006.
  * Schönemann [1970] Peter H. Schönemann.  On metric multidimensional unfolding.  _Psychometrika_ , 35(3):349–366, 1970.
  * Sharp and Ovsjanikov [2020] Nicholas Sharp and Maks Ovsjanikov.  PointTriNet: Learned Triangulation of 3D point sets.  In _Proceedings of the 16th European Conference on Computer Vision (ECCV), Part XXIII_ , pages 762–778, Glasgow, UK, 2020.
  * Smith et al. [2016] Mark William Smith, Jonathan L. Carrivick, and Duncan J. Quincey.  Structure from Motion Photogrammetry in Physical Geography.  _Progress in Physical Geography_ , 40(2):247–275, 2016.
  * Stewénius et al. [2005] Henrik Stewénius, Frederik Schaffalitzky, and David Nistér.  How hard is 3-view triangulation really?  In _Proceedings of the 10th IEEE International Conference on Computer Vision (ICCV)_ , pages 686–693, Beijing, China, 2005.
  * Swoboda et al. [2019] Paul Swoboda, Dagmar Kainmüller, Ashkan Mokarian, Christian Theobalt, and Florian Bernard.  A convex relaxation for multi-graph matching.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 11156–11165, Long Beach, CA, 2019.
  * Torgerson [1952] Warren S. Torgerson.  Multidimensional scaling: I. theory and method.  _Psychometrika_ , 17(4):401–419, 1952.
  * Torresani et al. [2012] Lorenzo Torresani, Vladimir Kolmogorov, and Carsten Rother.  A dual decomposition approach to feature correspondence.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 35(2):259–271, 2012.
  * Triggs et al. [1999] Bill Triggs, Philip F. McLauchlan, Richard I. Hartley, and Andrew W. Fitzgibbon.  Bundle adjustment - A modern synthesis.  In _Proceedings of the International Workshop on Vision Algorithms (ICCV)_ , pages 298–372, Corfu, Greece, 1999.
  * Velasco et al. [2016] José F. Velasco, Daniel Pizarro, Javier Macías Guarasa, and Afsaneh Asaei.  TDOA matrices: Algebraic properties and their application to robust denoising with missing data.  _IEEE Trans. Signal Process._ , 64(20):5242–5254, 2016.
  * Wang et al. [2007] Chieh-Chih Wang, Charles E. Thorpe, Sebastian Thrun, Martial Hebert, and Hugh F. Durrant-Whyte.  Simultaneous Localization, Mapping and Moving Object Tracking.  _Int. J. Robotics Res._ , 26(9):889–916, 2007\.
  * Wei and Ma [1994] Guo-Qing Wei and Song De Ma.  Implicit and explicit camera calibration: theory and experiments.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 16(5):469–480, 1994.
  * Weng et al. [1992] Juyang Weng, Paul R. Cohen, and Marc Herniou.  Camera calibration with distortion models and accuracy evaluation.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 14(10):965–980, 1992.
  * Yan et al. [2016] Junchi Yan, Minsu Cho, Hongyuan Zha, Xiaokang Yang, and Stephen M. Chu.  Multi-graph matching via affinity optimization with graduated consistency regularization.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 38(6):1228–1242, 2016.
  * Yang et al. [2019] Kui Yang, Wei Fang, Yan Zhao, and Nianmao Deng.  Iteratively reweighted midpoint method for fast multiple view triangulation.  _IEEE Robot. Autom. Lett._ , 4(2):708–715, 2019\.
  * Zach [2014] Christopher Zach.  Robust bundle adjustment revisited.  In _Proceedings of the 13th European Conference on Computer Vision (ECCV), Part V_ , pages 772–787, Zurich, Switzerland, 2014.
  * Zhang [2000] Zhengyou Zhang.  A flexible new technique for camera calibration.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 22(11):1330–1334, 2000.
  * Zheng et al. [2017] Liang Zheng, Yi Yang, and Qi Tian.  SIFT meets CNN: A decade survey of instance retrieval.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 40(5):1224–1244, 2017.
  * Zheng et al. [1999] Zhiqiang Zheng, Han Wang, and Eam Khwang Teoh.  Analysis of gray level corner detection.  _Pattern Recognit. Lett._ , 20(2):149–162, 1999\.
  * Zhou and la Torre [2013] Feng Zhou and Fernando De la Torre.  Deformable graph matching.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2922–2929, Portland, OR, 2013.
  * Zhou et al. [2019] Jie Zhou, Xinke Ma, Li Liang, Liu Yuhe, Shijin Xu, Sim Heng Ong, and Yang Yang.  Robust variational bayesian point set registration.  In _Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 9904–9913, Seoul, Korea, 2019.
  * Ziou and Tabbone [1998] Djemel Ziou and Salvatore Tabbone.  Edge detection techniques - an overview.  _Pattern Recognition and Image Analysis_ , 8:537–559, 1998\.
  * Zollhöfer et al. [2018] Michael Zollhöfer, Patrick Stotko, Andreas Görlitz, Christian Theobalt, Matthias Nießner, Reinhard Klein, and Andreas Kolb.  State of the art on 3d reconstruction with rgb-d cameras.  In _Comput Graph Forum_ , volume 37, pages 625–652. Wiley Online Library, 2018.