# From a few Accurate 2D Correspondences to
3D Point Clouds

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

{hieukien1207<EMAIL_ADDRESS>

###### Abstract

Key points, correspondences, projection matrices, point clouds and dense
clouds are the skeletons in image-based 3D reconstruction, of which point
clouds have the important role in generating a realistic and natural model for
a 3D reconstructed object. To achieve a good 3D reconstruction, the point
clouds must be almost everywhere in the surface of the object. In this
article, with a main purpose to build the point clouds covering the entire
surface of the object, we propose a new feature named a _geodesic feature_ or
_geo-feature_. Based on the new geo-feature, if there are several (given)
initial world points on the object’s surface along with all accurately
estimated projection matrices, some new world points on the geodesics
connecting any two of these given world points will be reconstructed. Then the
regions on the surface bordering by these initial world points will be covered
by the point clouds. Thus, if the initial world points are around the surface,
the point clouds will cover the entire surface. A prerequisite for applying
the geo-feature to build the point clouds is having several initial world
points on the object’s surface and the accurate estimated projection matrices.
Fortunately, from the multi-view geometry theory, the initial world points and
the projection matrices can be accurately derived by their correspondences.
Following this task, this article proposes a new method to estimate the world
points and projection matrices from their correspondences. This method derives
the closed-form and iterative solutions for the world points and projection
matrices and proves that when the number of world points is less than seven
and the number of images is at least five, the proposed solutions are global
optimal. Finally, in this article, we propose an algorithm named _World points
from their Correspondences_ (WPfC) to estimate the world points and projection
matrices from their correspondences, and another algorithm named _Creating
Point Clouds_ (CrPC) to create the point clouds from the world points and
projection matrices given by the first algorithm. To be simple, from a few
accurate correspondences as an initialization, we obtain the estimations of
all projection matrices and the point clouds covering the entire surface of
the object to be 3D reconstructed. We apply the algorithms WPfC and CrPC on
the 3D Buddha statue reconstruction project. The obtained point clouds have
more than ten millions points and they are almost everywhere on the statue’s
surface. More than $95\%$ relative errors computed by correspondences are less
than 30 pixels. From our experience on image-based 3D reconstruction, this
achievement appears dramatic and validates our study.

##  1 Introduction

Image-based 3D reconstruction have been widely applied to our life and
science. The central purpose of 3D reconstruction is to create a spatial
virtual model that brings more information from images than what we can see
with the naked eyes. With this dynamic, image-based 3D reconstruction is an
age-old method, originally used in architecture long before computer-aided
imaging techniques were introduced. As early as the Renaissance, scholars
studied the appearance of the architecture of the past, analyzing it by means
of images, and using it to construct their own contemporary buildings (Carpo,
2001, page 6). Nowadays, with strong support from computer graphics and
computer vision that a virtual model is built accurately and very quickly, and
more importantly it can be visualized, we can see applications of image-based
3D reconstruction on robotics, autonomous driving (Wang et al., 2007; Cadena
et al., 2016; Bresson et al., 2017), medical imaging analysis (McInerney and
Terzopoulos, 1996; Heimann and Meinzer, 2009; Oliveira and Tavares, 2014),
physical geography (Smith et al., 2016), archaeology (Hermon, 2008; Bruno et
al., 2010), and many others. Recently, the advent of _Metaverse_ 111Metaverse
is a network of 3D virtual worlds focused on social connection.
(https://en.wikipedia.org/wiki/Metaverse) and _Second Life_ 222Second Life is
an online multimedia platform that allows people to create an avatar for
themselves and have a second life in an online 3D virtual world.
(https://en.wikipedia.org/wiki/Second_Life) reflects the power of digital 3D
reconstruction (Kemp and Livingstone, 2006; Dionisio et al., 2013). One of the
challenges for the Metaverse and Second Life is to create digital environments
that appear realistic and natural-looking spaces. Some high-accurate and high-
solution 3D virtual models of buildings, physical locations, and objects are
rendered and passed to computers to process and generate virtual worlds. Thus,
beside _artificial intelligence_ (AI), 3D reconstruction is a key technology
to power Metaverse and Second Life.

Figure 1: The image-based 3D Buddha statue reconstruction: Images and Point
clouds.

There is a forest of knowledge and techniques in image-based 3D
reconstruction, despite its deceptively simple definition. Starting with
multiple 2D images capturing an object, image-based 3D reconstruction attempts
to build a dense to estimate the surface of this object. This process can be
summarized by the three following steps that (i) detect and collect as many
_correspondences_ as possible, (ii) estimate projection matrices of all images
and build _point clouds_ from these correspondences, and (iii) apply some
smooth surface (rendering) techniques on the point clouds to generate a
_dense_ and complete the process of 3D reconstruction. Figure 1 is an example
of image-based 3D Buddha statue reconstruction. There are a lot of the Buddha
statue images (far-view and near-view) used to create the point clouds (the
_blue dots_ in four black background pictures).

To detect correspondences, we first describe or define and then estimate key
points on each image. The _key point estimation_ is also known by another name
of the _feature detection_. Depending on the object to be 3D reconstructed,
key points or features can be defined as special 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. Of course with different definitions of key points as special
points, edges, corners or circles, we have different techniques to extract
these key points. In general, SIFT (Lowe, 1999) and SURF (Bay et al., 2006)
are two popular and effective methods for extracting key points. When key
points on each image are collected, correspondences are detected based on the
matching key points or the feature matching problem (Munkres, 1957; Torresani
et al., 2012; Yan et al., 2016; Swoboda et al., 2019). _Matching key points_
is a difficult problem and has received a lot of attention from researchers.
The well-known formulation of the matching key points problem is the
_quadratic assignment problem_ (QAP) that is NP-hard (Lawler, 1963). In
addition, the matching key points across multiple images is still a
challenging task even though there are several potential methods for this on
two images. More recently, Le and Li (2022) have proposed some algebraic
properties for multi-view correspondences. These properties say that there are
some constraints among key points if they are correspondences. These
constraints will help us on estimating, refining and recovering
correspondences from the given key points.

From correspondences, a _fundamental matrix_ of each pair images is determined
based on the most popular formula in 3D reconstruction that ${\bf
x}^{\prime}{\bf F}{\bf x}=0$ where ${\bf x}$ and ${\bf x}^{\prime}$ are two
matching key points on two images and ${\bf F}$ is the fundamental matrix of
these two images (Luong and Faugeras, 1996). When the number of two-view
correspondences $\\{{\bf x}\leftrightarrow{\bf x}^{\prime}\\}$ is at least
eight, the _eight-point algorithm_ (Hartley and Kahl, 2007) derives the
fundamental matrix ${\bf F}$ by linear equations, and when this number is
five, the _five-point algorithms_ (Nistér, 2004; Barath, 2018) find solutions
for ${\bf F}$ by high-degree polynomial equations. Since the fundamental
matrix presents a relationship between two projection matrices corresponding
to two images, all projection matrices of all images are determined by fixing
one projection matrix of the reference image. As the projection matrices are
given, the point clouds are built based on _triangulation_ methods (Hartigan
and Wong, 1979; Stewénius et al., 2005; Yang et al., 2019; Sharp and
Ovsjanikov, 2020) together with a process on creating lots of new
correspondences. Finally, the point clouds are rendered to become a dense by
the _bundle adjustment_ techniques, _harmonic maps_ and _conformal maps_
(Triggs et al., 1999; Agarwal et al., 2010; Zach, 2014; Wu and Yau, 2020; Choi
et al., 2022).

Continuing our previous work in Le and Li (2022) on solving the first step of
the image-based 3D reconstruction that detects a few accurate correspondences
from multiple images, this paper will focus on the second step of estimating
projection matrices from a few correspondences and creating point clouds. With
the first task that estimate projection matrices, we motivate to obtain very
accurate projection matrices. Since image distortion is difficult to avoid,
there is always an error in the correspondence estimate. Indeed, to be
successful in 3D reconstruction with good point clouds, we need to have very
precise projection matrices for all images. As we discussed in the previous
paragraph, most of existing methods for the projection matrix estimation333The
projection matrix estimation is also known as another named the _camera
calibration_. (Weng et al., 1992; Wei and Ma, 1994; Zhang, 2000; Remondino and
Fraser, 2006; Chuang et al., 2021) estimate projection matrices through
fundamental matrix estimation. There are ambiguities on the image-based 3D
reconstruction as we shall present in Section 2.1, and these methods solve the
ambiguity problem by fixing one projection matrix of the reference image. When
this projection matrix is given, other projection matrices are easily derived
based on the fundamental matrices. In our study, we shall estimate projection
matrices directly from correspondences, not through the fundamental matrix
estimation. The main difference between our method and other existent methods
is in handling the ambiguities of the image-based 3D reconstruction. From our
experience on the _localization_ problem (Le and Ono, 2016; Le and Ho, 2020a,
b), we solve the ambiguity problem by fixing the first five world points
corresponding to the correspondences.

More precisely, if correspondences $\\{{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}^{M}_{m=1}$ of $M$ ($M\geq 5$) world points
$\\{{\bf X}_{1},{\bf X}_{2},\ldots,{\bf X}_{M}\\}$ and $N$ projection matrices
$\\{{\bf P}_{1},{\bf P}_{2},\ldots,{\bf P}_{N}\\}$ are used, from the
ambiguities we can fix ${\bf X}_{1}=[0\,,\,0\,,\,0]^{T}$, ${\bf
X}_{2}=[0\,,\,0\,,\,1]^{T}$, ${\bf X}_{3}=[0\,,\,1\,,\,0]^{T}$, ${\bf
X}_{4}=[1\,,\,0\,,\,0]^{T}$ and ${\bf X}_{5}=[1\,,\,1\,,\,1]^{T}$ in the
process of finding solutions for $N$ projection matrix $\\{{\bf P}_{1},{\bf
P}_{2},\ldots,{\bf P}_{N}\\}$. The handle of fixing the first five world
points allows us to obtain the closed-form solutions for both $N$ projection
matrices $\\{{\bf P}_{1},{\bf P}_{2},\ldots,{\bf P}_{N}\\}$ and $M$ world
points $\\{{\bf X}_{1},{\bf X}_{2},\ldots,{\bf X}_{M}\\}$ when $N\geq 5$ and
$M\geq 6$ (Theorem 1). In addition, when $M=6$ we prove that our closed-form
solutions are the best from the point of view of minimizing the mean squared
errors on the correspondences (Proposition 3). Beside the closed-form
solutions for projection matrices, we propose the iterative solutions
(Propositions 4 and 5) that are guaranteed that our final solutions are not
only better than the closed-form solutions but also local optimal.

Regarding the second task of creating point clouds, we motivate to build the
point clouds such that they can cover everywhere on the object’s surface. This
is a tough challenge. Although the property of being everywhere on the object
surface of point clouds is important, to our knowledge no 3D reconstruction
studies have addressed this property. Obviously, in order to have point clouds
covering everywhere on the object’s surface, we need a feature that can
recognize all the points on the surface by images. A new concept of _geo-
feature_ proposed by this paper (Definition 2) can do what we want. A new
world point has a _geo-feature_ if there are two old world points on the
object’s surface such that the new world point lays on the _geodesic_ in this
surface connecting these two old world points. The ‘old’ and ‘new’ world
points mean their coordinates are and are not known, and a geodesic of two
points on a surface is the shortest curves on this surface connecting these
two points (Busemann, 2012). The definitions of geo-feature and geodesic
confirm that if a point has a geo-feature it will be on the object’s surface.
Therefore, if a new geo-feature point is recognized and determined, it becomes
an old world point. Then along with other old world points it helps us to find
other new world points. To recognize and determine a geo-feature point, we
first estimate the geodesic of two old world points by straight lines
connecting image points of these two old world points on each image. From
these 2D straight lines, we find correspondences corresponding to geo-feature
points, then derive these geo-feature points based on the projection matrices
that estimated by the first task. This process will help us to create the
point clouds with millions points only from a few given points on the surface.
Not only with a huge number of points in them, these point clouds also cover
the entire surface of the object.

As a consequence of our results in studying the first step, we propose an
algorithm to estimate both the world points and projection matrices from their
correspondences. This algorithm names _World points from their
Correspondences_ (WPfC) and is given by Algorithm 2. From the results for the
second step, we also propose another algorithm to create the point clouds
based on the world points and projection matrices from the first algorithm.
The second algorithm is called _Creating Point Clouds_ (CrPC) and presented by
Algorithm 3. Unlike the first algorithm in which its correctness and
efficiency are guaranteed by some theoretical results like the global solution
given by Proposition 3 and the iterative solutions given by Proposition 5, the
validity of the second algorithm is to be thoroughly investigated through
practical experiments.

We apply our study in this paper to the _image-based 3D Buddha statue
reconstruction_ project. A purpose of this project is modeling the Buddha
statue by point clouds based on a lot of images capturing this statue. Note
that point clouds, not like dense clouds, are 3D colorless points and they do
not have any continuous regions. As such, seeing the Buddha statue through
point clouds is difficult. In other words, if we can see the 3D shape of the
statue through the point clouds, then these point clouds would be very good.
On another hand, getting ground-truths for the Buddha statue is a hard and
expensive job if we don’t want to say that it is impossible task. Thus, in
this paper, we mainly evaluate the quality of the point clouds based on their
similarity of these point clouds with the statue through our eyes.

In this project, the correspondences are found based on 112 special points
marked on the statue’s surface as we see clearly in Figures 2, 3, 4 and 7. We
use SIFT (Lowe, 1999) and SURF (Bay et al., 2006) to detect these special
points on images, and then use the work in Le and Li (2022) to estimate the
correspondences. There are twelve experiments in the project. Each experiment
has around 80$\sim$150 images that capture around 20$\sim$30 special points. A
role of each experiment is reconstructing an area corresponding to this
experiment. For instance, the _front body experiment_ reconstructs the 3D
shape of the front body, and the _face experiment_ reconstructs the 3D shape
of the face of the statue. Note that there are a lot of correspondences in
each experiment. Indeed, from twelve experiments, we have thousands outputs of
Algorithm WPfC and millions outputs of Algorithm CrPC. These huge numbers of
implementing WPfC and CrPC are sufficient for us to get correct evaluations of
these two algorithms and also the study in this paper. Since we do not have
ground-truths for world points, projection matrices and point clouds, each
implementation of WPfC or CrPC is evaluated based on a _relative error_
defined as a difference between the correspondences in the input and other
correspondences computed by the output of WPfC or CrPC. Although there are no
theoretical results to warrant a correctness for a relative error, we still
believe that small relative error reflects a good estimation from these two
algorithms. Hence, in addition to seeing with the naked eye the similarity
between the statue and the point clouds, we use the histograms of relative
errors to evaluate our study. From these histograms, we know that 95 percent
relative errors on key points (the image points of the 112 special points
marked in the statue) are less than 49 pixels, and 95 percent relative errors
on image points (image points of ten millions points in the point clouds) are
less than 25 pixels. Working with the images of size $3024\times
4032~{}\text{pixel}^{2}$, these small relative errors on our 3D reconstruction
appear to be really dramatic.

${\bf X}_{m}=\big{[}x_{m}\,,\,y_{m}\,,\,z_{m}\big{]}^{T}$ |  World point $m$, a $3\times 1$ real vector
---|---
${\bf P}_{n}=\begin{bmatrix}{\bf p}_{1,n}\\\ {\bf p}_{2,n}\\\ {\bf p}_{3,n}\end{bmatrix}=\begin{bmatrix}p_{1n}&p_{2n}&p_{3n}&p_{4n}\\\ p_{5n}&p_{6n}&p_{7n}&p_{8n}\\\ p_{9n}&p_{10n}&p_{11n}&1\end{bmatrix}$ |  Projection matrix $n$, a $3\times 4$ real matrix
${\bf x}^{\text{\tiny(n)}}_{m}=\big{[}u_{mn}\,,\,v_{mn}\big{]}^{T}$ |  Key point of the world point $m$ on the image $n$, a $2\times 1$ real vector
$\big{\\{}{\bf x}^{\text{\tiny(1)}}_{m}\leftrightarrow{\bf x}^{\text{\tiny(2)}}_{m}\leftrightarrow\cdots\leftrightarrow{\bf x}^{\text{\tiny(N)}}_{m}\big{\\}}$ |  A correspondence of world point ${\bf X}_{m}$
$\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}$ |  Correspondences of $M$ world points ${\bf X}_{1},\ldots,{\bf X}_{M}$
$\\{{\bf X}_{m},{\bf P}_{n}\\}$ |  Group of $M$ world points $\\{{\bf X}_{1},{\bf X}_{2},\ldots,{\bf X}_{M}\\}$
and $N$ projection matrices $\\{{\bf P}_{1},{\bf P}_{2},\ldots,{\bf P}_{n}\\}$
_World points from Correspondences:_ |
$\mathcal{K}_{n}\big{(}\\{{\bf X}_{m}\\}\big{)}$ |  $12\times 2M$ matrix given by (2) used to estimate projection matrix ${\bf P}_{n}$
from $M$ world points $\\{{\bf X}_{m}\\}^{M}_{m=1}$ and $M$ key points
$\\{{\bf x}^{\text{\tiny(n)}}_{m}\\}^{M}_{m=1}$
$\mathcal{H}_{m}\big{(}\\{{\bf P}_{n}\\}\big{)}$ |  $2N\times 4$ matrix given by (3) used to estimate world point ${\bf X}_{m}$
from $N$ projection matrices $\\{{\bf P}_{n}\\}^{N}_{n=1}$ and $N$ key points
$\\{{\bf x}^{\text{\tiny(n)}}_{m}\\}^{N}_{n=1}$
${\bf T}$ |  Projective transformation on $\mathbb{R}^{3}$, a non-singular $4\times 4$ matrix
$\xi^{\text{\tiny(n)}}_{m_{1}m_{2},m_{3}}$ |  Defined by (8) that is computed by three key points ${\bf x}^{\text{\tiny(n)}}_{m_{1}},{\bf x}^{\text{\tiny(n)}}_{m_{2}},{\bf x}^{\text{\tiny(n)}}_{m_{3}}$
${\bf\Lambda}_{m},f_{m},f_{xm},f_{ym},f_{zm}$ |  Used to estimate world point ${\bf X}_{m},~{}m\geq 6$
$\alpha_{n},\beta_{n},\gamma_{n}$ |  Used to estimate projection matrix ${\bf P}_{n}$
$\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}$ | Estimated correspondences
$\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$ |  Closed-form solution, the output of Algorithm 1, CF-WPfC
$\\{{\bf X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$ |  Better solution than $\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$ because of Proposition 4
$\\{{\bf X}^{**}_{m},{\bf P}^{**}_{n}\\}$ |  Better solution than $\\{{\bf X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$ because of Proposition 5
$\\{{\bf X}^{\star}_{m},{\bf P}^{\star}_{n}\\}$ |  The best solution in our work, the output of Algorithm 2, WPfC
_Creating Point clouds:_ |
 _key point_ |  An image point of the world point in $\\{{\bf X}^{\star}_{1},{\bf X}^{\star}_{2},\ldots,{\bf X}^{\star}_{M}\\}$
 _image point_ | An image point of a point in point clouds
$\mathcal{PC}$ | Point clouds
$\textbf{Img}_{n}$ |  Image $n$, a $H\times W$ real matrix
$\textbf{Img}_{n}(h,\omega)\,,\,\textbf{Img}_{n}\big{(}{\bf x}^{\text{\tiny(n)}}_{k}\big{)}$ |  Value of $\textbf{Img}_{n}$ at $(h,\omega)$ or image point ${\bf x}^{\text{\tiny(n)}}_{k}$
$\mathcal{G}({\bf X}_{k},{\bf X}_{k^{\prime}})$ |  Geodesic between two points ${\bf X}_{k},{\bf X}_{k^{\prime}}$
These two points can be world points or points in point clouds
$\textbf{Img}_{n}\big{(}{\bf X}_{k},{\bf X}_{k^{\prime}}|L\big{)}$ |  Defined by (42), $L\times 1$ vector collecting all values on $\textbf{Img}_{n}$ in the
straight line connecting image points ${\bf x}^{\text{\tiny(n)}}_{k}$ and
${\bf x}^{\text{\tiny(n)}}_{k^{\prime}}$ of ${\bf X}_{k}$ and ${\bf
X}_{k^{\prime}}$
$\mathcal{E}_{d}({\bf X}),\mathcal{E}_{i}({\bf X})$ |  Two metrics to evaluate a new created point ${\bf X}$
$\theta,\ell$ |  Two parameters in _geo-feature_ detection
$\mathcal{C}\big{(}{\bf X}_{k},{\bf X}_{k^{\prime}},\theta,\ell\big{)}$ |  Collecting all candidates for geo-features w.r.t. $\\{{\bf X}_{k},{\bf X}_{k^{\prime}},\theta,\ell\\}$
_Evaluation:_ |
$\mathcal{PC}_{\delta}$ |  Refinements of $\mathcal{PC}$ corresponding to distance $\delta$
$\mathcal{PC}_{\epsilon}$ |  Refinements of $\mathcal{PC}$ corresponding to pixel $\epsilon$
$\text{Error}_{\text{Rel}}\big{(}\\{{\bf X}^{\star}_{m},{\bf P}^{\star}_{n}\\}\big{)}$ |  Defined by (55), used to evaluate Algorithm 2, WPfC
$\text{Error}_{\text{Rel}}\big{(}{\bf X}\big{)}$ |  Defined by (56), used to evaluate Algorithm 3, CrPC
Table 1: _Notations and Explanations_

Roadmap. Most important notations of the paper and their explanations are
given by the Table 1 in the next page. The first task of estimating projection
matrices is studied in Section 2 and the second task of creating point clouds
is presented by Section 3. In Section 2, we first discuss the ambiguities of
image-based 3D reconstruction and handle them by Proposition 1. The closed-
form solutions for the world points and projection matrices from their
correspondences are derived by Theorem 1 and Algorithm 1 in Subsection 2.2.
Subsection 2.3 starts by introducing the optimization (20) to solve the _World
points from their Correspondences_ problem when the correspondences have
noise. The global optimal solutions for this optimization are derived for the
case $M\leq 6$ by Propositions 2 and 3. As $M\geq 7$, Proposition 4 brings the
better solution than the closed-forms given by Theorem 1 and Proposition 5
gives the better solution than the one from Proposition 4. In addition, the
results from Propositions 4 and 5 allow us to propose an iterative process to
find the local optimal solutions from the initial closed-from solutions given
by Theorem 1. This iterative process is Algorithm 2, named by WPfC. In Section
3, we introduce the concept of _geodesic feature_ or _geo-feature_ in the
Subsection 3.2 then propose an algorithm to detect geo-features and creating
the point clouds in Subsection 3.3. The most important result in Section 3 is
Algorithm 3, named by CrPC. This algorithm creates new world points for the
point clouds based on two old world points and the projection matrices of all
images. Since the results in Sections 2 and 3 are only materials and
Algorithms WPfC and CrPC are tools only, to complete the process of building
point clouds from a few accurate correspondences we need a protocol. Through
the _front body experiment_ in the 3D Buddha statue reconstruction project,
Section 4 introduces the proposed image-based 3D reconstruction protocol.
Finally, Section 5 gives an evaluation of our work based on the 3D Buddha
statue reconstruction project and Section 6 concludes this article.

##  2 World points from Correspondences

Let

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

be _correspondences_ of $M$ unknown _world points_ ${\bf X}_{1}$, ${\bf
X}_{2}$, $\ldots$, ${\bf X}_{M}$ capturing by $N$ unknown _cameras_ ${\bf
P}_{1},{\bf P}_{2},\ldots,{\bf P}_{N}$. The world point ${\bf X}_{m}$ is in
three-dimensional space $\mathbb{R}^{3}$ and indicated by three coordinates
$x_{m},y_{m}$ and $z_{m}$ and the camera or the projection matrix ${\bf
P}_{n}$ is the $3\times 4$ matrix denoted 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}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}\begin{bmatrix}{\bf p}_{1,n}\\\
{\bf p}_{2,n}\\\ {\bf p}_{3,n}\end{bmatrix}$

From the _multiple view geometry_ theory (Harltey and Zisserman, 2006), the
relationship between the correspondences, world points and projection matrices
are given by nonlinear equations

$\qquad\qquad{\bf P}_{n}\begin{bmatrix}{\bf X}_{m}\\\
1\end{bmatrix}\sim\begin{bmatrix}{\bf x}^{\text{\tiny(n)}}_{m}\\\
1\end{bmatrix}\qquad\quad\text{for all}\quad m,n\,,$ (1)

where ${\bf a}\sim{\bf b}$ means that two vectors ${\bf a}$ and ${\bf b}$ are
parallel. In this section we study the problem that estimating both the
unknown world points ${\bf X}_{1},{\bf X}_{2},\ldots,{\bf X}_{M}$ and the
unknown projection matrices ${\bf P}_{1},{\bf P}_{2},\ldots,{\bf P}_{N}$ from
the known key-points $\\{{\bf x}^{\text{\tiny(n)}}_{m}\\}$ based on the
nonlinear equations (1). This problem is named _the world points from their
correspondences_ (WPfC). If the world points $\\{{\bf X}_{m}\\}$ and the
projection matrices $\\{{\bf P}_{n}\\}$ satisfy (1) corresponding to the
correspondences $\\{{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}^{M}_{m=1}$, we call the group $\\{{\bf X}_{m},{\bf
P}_{n}\\}$ be a _solution_ with respect to (w.r.t.) these correspondences.
Vice versa, if there exist a group $\\{{\bf X}_{m},{\bf P}_{n}\\}$ satisfying
(1), $\\{{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}^{M}_{m=1}$ are called the _correspondences_.

Before go to further on finding solutions for the world points and the
projection matrices based on the correspondences, we mention that when the
world points are given, the solution for the projection matrix ${\bf P}_{n}$
is derived by the following linear equations

$\begin{bmatrix}\begin{matrix}~{}{\bf X}_{1}~{}&{\bf 0}\\\ 1&0\\\\[1.42262pt]
{\bf 0}&~{}{\bf X}_{1}~{}\\\ 0&1\end{matrix}&\begin{matrix}~{}{\bf
X}_{2}~{}&{\bf 0}\\\ 1&0\\\\[2.84526pt] {\bf 0}&~{}{\bf X}_{2}~{}\\\
0&1\end{matrix}&\begin{matrix}\cdots\\\ \cdots\\\\[1.42262pt] \cdots\\\
\cdots\end{matrix}&\begin{matrix}~{}{\bf X}_{M}~{}&{\bf 0}\\\
1&0\\\\[1.42262pt] {\bf 0}&~{}{\bf X}_{M}~{}\\\
0&1\end{matrix}\\\\[19.91692pt] -{\bf x}_{1}^{\text{\tiny(n)}T}{\bf
X}_{1}&-{\bf x}_{2}^{\text{\tiny(n)}T}{\bf X}_{2}&\cdots&-{\bf
x}_{M}^{\text{\tiny(n)}T}{\bf X}_{M}\\\\[5.69054pt] -{\bf
x}_{1}^{\text{\tiny(n)}T}&-{\bf x}_{2}^{\text{\tiny(n)}T}&\cdots&-{\bf
x}_{M}^{\text{\tiny(n)}T}\end{bmatrix}^{T}_{12\times 2M}\begin{bmatrix}~{}{\bf
p}_{1,n}^{T}~{}\\\\[8.53581pt] {\bf p}_{2,n}^{T}\\\\[8.53581pt] {\bf
p}_{3,n}^{T}\end{bmatrix}={\bf 0}_{2M\times 1\,,}$ (2)

for all $n$. Since the correspondences ${\bf x}_{m}^{\text{\tiny(n)}}$ are
always known, we denote the $12\times 2M$ matrix in the left side of (2) by
$\mathcal{K}_{n}(\\{{\bf X}_{m}\\})$ as the function of the world points. If
$M\geq 6$, the column vector containing all elements of ${\bf P}_{n}$ will be
the eigenvector corresponding to the smallest eigenvalue of the positive
semidefinite matrix $\big{[}\mathcal{K}_{n}(\\{{\bf
X}_{m}\\})\mathcal{K}_{n}(\\{{\bf X}_{m}\\})^{T}\big{]}$. Note that we can fix
$p_{12n}=1$.

Vice versa, when the projection matrices $\\{{\bf P}_{n}\\}$ are given, the
solution for the world point ${\bf X}_{m}$ is given by

$\begin{bmatrix}\begin{bmatrix}{\bf p}_{1,1}\\\ {\bf
p}_{2,1}\end{bmatrix}-{\bf x}_{m}^{\text{\tiny(1)}}{\bf
p}_{3,1}~{}~{}~{}\\\\[14.22636pt] \begin{bmatrix}{\bf p}_{1,2}\\\ {\bf
p}_{2,2}\end{bmatrix}-{\bf x}_{m}^{\text{\tiny(2)}}{\bf p}_{3,2}~{}~{}~{}\\\
\vdots~{}~{}~{}~{}\\\ \begin{bmatrix}{\bf p}_{1,N}\\\ {\bf
p}_{2,N}\end{bmatrix}-{\bf x}_{m}^{\text{\tiny(N)}}{\bf
p}_{3,N}\end{bmatrix}_{2N\times 4}\begin{bmatrix}{\bf X}_{m}\\\\[2.84526pt]
1\end{bmatrix}~{}=~{}{\bf 0}_{2N\times 1\,.}$ (3)

We denote the $2N\times 4$ matrix in the left side of (3) by
$\mathcal{H}_{m}(\\{{\bf P}_{n}\\})$ as the function of the projection
matrices. When $N\geq 2$, the world point ${\bf X}_{m}$ will be the three
first coordinates of the eigenvector corresponding to the smallest eigenvalue
of the positive semidefinite matrix $\big{[}\mathcal{H}_{m}(\\{{\bf
P}_{n}\\})^{T}\mathcal{H}_{m}(\\{{\bf P}_{n}\\})\big{]}$.

The solutions for the projection matrices from the world points given by (2)
and the solutions for the world points from the projection matrices in (3)
confirm that the _degrees of freedom_ (DoFs) of WPfC should be smaller than
$\min\\{3M,11N\\}$. In the next subsection, by studying an ambiguity of WPfC,
we show that the DoFs of this problem should be not larger than $3M-15$. In
addition, when there are only six world points ($M=6$), this DoFs is at most
three and the WPfC problem is solvable.

###  2.1 Ambiguity

From (1) we easily see that if $\\{{\bf X}_{m},{\bf P}_{n}\\}$ is a solution
of the correspondences $\\{{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ and $p_{12n}\neq 0$, the new group given by

$\qquad\qquad\widehat{\bf X}_{m}={\bf X}_{m}\qquad\text{and}\qquad\widehat{\bf
P}_{n}=\frac{1}{p_{12n}}{\bf P}_{n}\,,\qquad\quad\text{for all}\quad m,n\,,$

then

$\qquad\qquad\widehat{\bf P}_{n}\begin{bmatrix}\widehat{\bf X}_{m}\\\
1\end{bmatrix}=\frac{1}{p_{12n}}{\bf P}_{n}\begin{bmatrix}{\bf X}_{m}\\\
1\end{bmatrix}\sim\begin{bmatrix}{\bf x}_{m}^{\text{\tiny(n)}}\\\
1\end{bmatrix}\,,\qquad\quad\text{for all}\quad m,n\,.$

It means that $\\{\widehat{\bf X}_{m},\widehat{\bf P}_{n}\\}$ is another
solution w.r.t. $\\{{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}$. Thus, to fix this ambiguity, we can assume that
the (3,4)th element of the projection matrices ${\bf P}_{n}$ is unit for all
$n$. In addition, by using any rotation or reflection ${\bf R}$ in three-
dimensional space to transfer the world points and the projection matrices as
follows

$\widetilde{\bf X}_{m}={\bf R}{\bf X}_{m}\qquad\text{and}\qquad\widetilde{\bf
P}_{n}=\begin{bmatrix}\begin{bmatrix}p_{1n}&p_{2n}&p_{3n}\\\
p_{5n}&p_{6n}&p_{7n}\\\ p_{9n}&p_{10n}&p_{11n}\end{bmatrix}{\bf
R}^{-1}&\begin{matrix}p_{4n}\\\ p_{8n}\\\ p_{12n}\end{matrix}\end{bmatrix}$

then the group $\\{\widetilde{\bf X}_{m},\widetilde{\bf P}_{n}\\}$ is also a
solution because of

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

In another word, the world points from their correspondences is invariant
under any rotations and reflections.

In general, Harltey and Zisserman (2006) shows that WPfC is invariant under
any _projective transformation_ , a linear transformation that transfers
points into points, lines into lines, planes into planes, and any two incident
elements into two incident elements. Precisely, let ${\bf T}$ be the
_projective transformation_ on the three-dimensional space, a non-singular
$4\times 4$ matrix with 15 degrees of freedom (Harltey and Zisserman, 2006),
we create a new group $\\{\breve{\bf X}_{m},\breve{\bf P}_{n}\\}$ as follows

$\qquad\qquad\begin{bmatrix}\breve{\bf X}_{m}\\\ 1\end{bmatrix}={\bf
T}\begin{bmatrix}{\bf X}_{m}\\\ 1\end{bmatrix}\qquad\text{and}\qquad\breve{\bf
P}_{n}={\bf P}_{n}{\bf T}^{-1}\qquad\quad\text{for all}\quad m,n\,.$

The new group will be a solution w.r.t. the correspondences because of the
identity of ${\bf T}^{-1}{\bf T}$.

A projective transformation on the three-dimensional space is uniquely defined
by five projected points, unless four of them are in the same plane. Based on
this property and the invariant property of the world points from their
correspondences under any projective transformation, the following result is
derived to describe clearly the ambiguities of WPfC via the world points and
the projection matrices.

######  Proposition 1.

Given the correspondences $\big{\\{}{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\big{\\}}^{M}_{m=1}$ with $M\geq 5$, there always
exists a solution $\\{{\bf X}_{m},{\bf P}_{n}\\}$ w.r.t. these correspondences
and

$\begin{bmatrix}{\bf X}_{1}&{\bf X}_{2}&{\bf X}_{3}&{\bf X}_{4}&{\bf
X}_{5}\end{bmatrix}=\begin{bmatrix}0&0&0&1&1\\\ 0&0&1&0&1\\\
0&1&0&0&1\end{bmatrix}\quad\text{and}\quad p_{12n}=1\,.$ (4)

###### Proof.

Since $\\{{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}^{M}_{m=1}$ are the correspondences, there exists a
solution $\\{{\bf X}_{m}^{\circ},{\bf P}_{n}^{\circ}\\}$ such that

$\qquad\qquad{\bf P}_{n}^{\circ}\begin{bmatrix}{\bf X}_{m}^{\circ}\\\
1\end{bmatrix}\sim\begin{bmatrix}{\bf x}_{m}^{\text{\tiny(n)}}\\\
1\end{bmatrix}\qquad\quad\text{for all}\quad m,n\,.$

From $\\{{\bf X}_{m}^{\circ}\\}$, we find a projective transformation
$\widehat{\bf
T}\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}\hat{t}_{11}&\hat{t}_{12}&\hat{t}_{13}&\hat{t}_{14}\\\
\hat{t}_{21}&\hat{t}_{22}&\hat{t}_{23}&\hat{t}_{24}\\\
\hat{t}_{31}&\hat{t}_{32}&\hat{t}_{33}&\hat{t}_{34}\\\
\hat{t}_{41}&\hat{t}_{42}&\hat{t}_{43}&1\end{bmatrix}$ such that

$\widehat{\bf T}\begin{bmatrix}{\bf X}^{\circ}_{1}&{\bf X}^{\circ}_{2}&{\bf
X}^{\circ}_{3}&{\bf X}^{\circ}_{4}&{\bf X}^{\circ}_{5}\\\\[5.69054pt]
1&1&1&1&1\end{bmatrix}=\begin{bmatrix}0&0&0&\alpha_{3}&\alpha_{4}\\\
0&0&\alpha_{2}&0&\alpha_{4}\\\ 0&\alpha_{1}&0&0&\alpha_{4}\\\
1&\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{5}\end{bmatrix}$ (5)

where $\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}$ and $\alpha_{5}$ are
unknown and nonzero real numbers. Using linear transformations to remove
unknown parameters $\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4},\alpha_{5}$,
the matrix form (5) is presented by linear equations of fifteen variables
$\hat{t}_{ij}$ in $\widehat{\bf T}$ as follows

$\begin{bmatrix}{\bf X}_{1}^{\circ T}&1&{\bf 0}^{T}&0&{\bf 0}^{T}&0&{\bf
0}^{T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf X}_{1}^{\circ T}&1&{\bf 0}^{T}&0&{\bf
0}^{T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf 0}^{T}&0&{\bf X}_{1}^{\circ T}&1&{\bf
0}^{T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf 0}^{T}&0&{\bf 0}^{T}&0&{\bf
X}_{1}^{\circ T}\\\\[2.84526pt] {\bf X}_{2}^{\circ T}&1&{\bf 0}^{T}&0&{\bf
0}^{T}&0&{\bf 0}^{T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf X}_{2}^{\circ T}&1&{\bf
0}^{T}&0&{\bf 0}^{T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf 0}^{T}&0&{\bf
X}_{2}^{\circ T}&1&-{\bf X}_{2}^{\circ T}\\\\[2.84526pt] {\bf X}_{3}^{\circ
T}&1&{\bf 0}^{T}&0&{\bf 0}^{T}&0&{\bf 0}^{T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf
X}_{3}^{\circ T}&1&{\bf 0}^{T}&0&-{\bf X}_{3}^{\circ T}\\\\[2.84526pt] {\bf
0}^{T}&0&{\bf 0}^{T}&0&{\bf X}_{3}^{\circ T}&1&{\bf 0}^{T}\\\\[2.84526pt] {\bf
X}_{4}^{\circ T}&1&{\bf 0}^{T}&0&{\bf 0}^{T}&0&-{\bf X}_{4}^{\circ
T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf X}_{4}^{\circ T}&1&{\bf 0}^{T}&0&{\bf
0}^{T}\\\\[2.84526pt] {\bf 0}^{T}&0&{\bf 0}^{T}&0&{\bf X}_{4}^{\circ T}&1&{\bf
0}^{T}\\\\[2.84526pt] {\bf X}_{5}^{\circ T}&1&-{\bf X}_{5}^{\circ T}&-1&{\bf
0}^{T}&0&{\bf 0}^{T}\\\\[2.84526pt] {\bf X}_{5}^{\circ T}&1&{\bf
0}^{T}&0&-{\bf X}_{5}^{\circ T}&-1&{\bf 0}^{T}\end{bmatrix}_{15\times
15}\begin{bmatrix}~{}\hat{t}_{11}~{}\\\\[2.84526pt]
\hat{t}_{12}\\\\[2.84526pt] \hat{t}_{13}\\\\[2.84526pt]
\hat{t}_{14}\\\\[2.84526pt] \hat{t}_{21}\\\\[2.84526pt]
\hat{t}_{22}\\\\[2.84526pt] \hat{t}_{23}\\\\[2.84526pt]
\hat{t}_{24}\\\\[2.84526pt] \hat{t}_{31}\\\\[2.84526pt]
\hat{t}_{32}\\\\[2.84526pt] \hat{t}_{33}\\\\[2.84526pt]
\hat{t}_{34}\\\\[2.84526pt] \hat{t}_{41}\\\\[2.84526pt]
\hat{t}_{42}\\\\[2.84526pt]
\hat{t}_{43}\end{bmatrix}=\begin{bmatrix}~{}0~{}\\\\[2.84526pt]
0\\\\[2.84526pt] 0\\\\[2.84526pt] 0\\\\[2.84526pt] 0\\\\[2.84526pt]
0\\\\[2.84526pt] 1\\\\[2.84526pt] 0\\\\[2.84526pt] 1\\\\[2.84526pt]
0\\\\[2.84526pt] 1\\\\[2.84526pt] 0\\\\[2.84526pt] 0\\\\[2.84526pt]
0\\\\[2.84526pt] 0\end{bmatrix}$ (6)

where ${\bf 0}$ denotes the zero vector in three-dimensional space. When the
square matrix in the left side of (6) is invertible, which is almost the case
in our study, the solution for the projective transformation $\widehat{\bf T}$
is easily derived to satisfy (5).

Let

$\qquad\qquad\begin{bmatrix}\widehat{\bf X}_{m}\\\ 1\end{bmatrix}=\widehat{\bf
T}\begin{bmatrix}{\bf X}_{m}^{\circ}\\\
1\end{bmatrix}\quad\text{and}\quad\widehat{\bf P}_{n}={\bf
P}_{n}^{\circ}\widehat{\bf T}^{-1}\qquad\quad\text{for all}\quad m,n\,.$

Because $\widehat{\bf T}$ is determined by five points from $\\{{\bf
X}_{1}^{\circ},{\bf X}_{2}^{\circ},\ldots,{\bf X}_{5}^{\circ}\\}$ to
$\\{\widehat{\bf X}_{1},\widehat{\bf X}_{2},\ldots,\widehat{\bf X}_{5}\\}$, it
is a projective transformation. Thus, $\\{\widehat{\bf X}_{m},\widehat{\bf
P}_{n}\\}$ is the solution w.r.t. $\\{{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}^{M}_{m=1}$. In addition, (5) yields

$\begin{bmatrix}\widehat{\bf X}_{1}&\widehat{\bf X}_{2}&\widehat{\bf
X}_{3}&\widehat{\bf X}_{4}&\widehat{\bf
X}_{5}\end{bmatrix}=\begin{bmatrix}0&0&0&1&\alpha\\\ 0&0&1&0&\alpha\\\
0&1&0&0&\alpha\end{bmatrix}\,,$ (7)

where $\alpha=\alpha_{4}/\alpha_{5}$ is non-zero. We continue transforming the
solution $\\{\widehat{\bf X}_{m},\widehat{\bf P}_{n}\\}$ to obtain the
solution $\\{{\bf X}_{m},{\bf P}_{n}\\}$ by the following projective
transformation

${\bf T}=\begin{bmatrix}(3\alpha-1)/(2\alpha)&0&0&0\\\
0&(3\alpha-1)/(2\alpha)&0&0\\\ 0&0&(3\alpha-1)/(2\alpha)&0\\\
(\alpha-1)/(2\alpha)&(\alpha-1)/(2\alpha)&(\alpha-1)/(2\alpha)&1\end{bmatrix}\,.$

The five points $\\{{\bf X}_{1},{\bf X}_{2},\ldots,{\bf X}_{5}\\}$ are
determined by $\\{\widehat{\bf X}_{1},\widehat{\bf X}_{2},\ldots,\widehat{\bf
X}_{5}\\}$ as follows

$\begin{split}{\bf T}\begin{bmatrix}\widehat{\bf X}_{1}&\widehat{\bf
X}_{2}&\widehat{\bf X}_{3}&\widehat{\bf X}_{4}&\widehat{\bf X}_{5}\\\
1&1&1&1&1\end{bmatrix}&=\begin{bmatrix}(3\alpha-1)/(2\alpha)&0&0&0\\\\[2.84526pt]
0&(3\alpha-1)/(2\alpha)&0&0\\\\[2.84526pt]
0&0&(3\alpha-1)/(2\alpha)&0\\\\[2.84526pt]
(\alpha-1)/(2\alpha)&(\alpha-1)/(2\alpha)&(\alpha-1)/(2\alpha)&1\end{bmatrix}\begin{bmatrix}0&0&0&1&\alpha\\\\[2.84526pt]
0&0&1&0&\alpha\\\\[2.84526pt] 0&1&0&0&\alpha\\\\[2.84526pt]
1&1&1&1&1\end{bmatrix}\\\\[8.53581pt]
&=\begin{bmatrix}0&0&0&(3\alpha-1)/(2\alpha)&(3\alpha+1)/2\\\\[2.84526pt]
0&0&(3\alpha-1)/(2\alpha)&0&(3\alpha+1)/2\\\\[2.84526pt]
0&(3\alpha-1)/(2\alpha)&0&0&(3\alpha+1)/2\\\\[2.84526pt]
1&(3\alpha-1)/(2\alpha)&(3\alpha-1)/(2\alpha)&(3\alpha-1)/(2\alpha)&(3\alpha+1)/2\end{bmatrix}\\\\[8.53581pt]
&\sim\begin{bmatrix}0&0&0&1&1\\\ 0&0&1&0&1\\\ 0&1&0&0&1\\\
1&1&1&1&1\end{bmatrix}\,.\end{split}$

It means

$\begin{bmatrix}{\bf X}_{1}&{\bf X}_{2}&{\bf X}_{3}&{\bf X}_{4}&{\bf
X}_{5}\end{bmatrix}=\begin{bmatrix}0&0&0&1&1\\\ 0&0&1&0&1\\\
0&1&0&0&1\end{bmatrix}\,.$

The remain condition $p_{12n}=1$ we always obtain from the ambiguity of the
projection matrices. Hence, Proposition 1 is proven. ∎

From Proposition 1, we can find solutions $\\{{\bf X}_{m},{\bf P}_{n}\\}$
w.r.t. the correspondences $\\{{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\\}^{M}_{m=1}$ within a setting given by (4). Indeed,
the DoFs of the problem is now upper bound by $\min\\{3M-15,11N\\}$.
Specially, when there are only six world points ($M=6$), the DoFs is at most
three that is possible to solve. Using the Theorem II given by Le and Li
(2022), the next subsection shows that the solution for the world points ${\bf
X}_{m}~{}(m\geq 6)$ is easily derived based on the setting (4). From that
_closed-form_ solutions for all world points and projection matrices are
derived.

###  2.2 Solutions from Correspondences

We begin this subsection by reminding the Theorem II in our previous article
(Le and Li, 2022). First, for any three key-points ${\bf
x}_{m_{1}}^{\text{\tiny(n)}}$, ${\bf x}_{m_{2}}^{\text{\tiny(n)}}$ and ${\bf
x}_{m_{3}}^{\text{\tiny(n)}}$ in the same image $n$, we define the value
$\xi_{m_{1}m_{2},m_{3}}^{\text{\tiny(n)}}$ as a determinant of a $2\times 2$
matrix generating by two column vectors ${\bf
x}_{m_{3}}^{\text{\tiny(n)}}-{\bf x}_{m_{1}}^{\text{\tiny(n)}}$ and ${\bf
x}_{m_{3}}^{\text{\tiny(n)}}-{\bf x}_{m_{2}}^{\text{\tiny(n)}}$, i.e.,

$\xi_{m_{1}m_{2},m_{3}}^{\text{\tiny(n)}}\stackrel{{\scriptstyle\text{def}}}{{=}}\text{det}\left(\begin{bmatrix}{\bf
x}_{m_{3}}^{\text{\tiny(n)}}-{\bf x}_{m_{1}}^{\text{\tiny(n)}}&{\bf
x}_{m_{3}}^{\text{\tiny(n)}}-{\bf
x}_{m_{2}}^{\text{\tiny(n)}}\end{bmatrix}\right)\,.$ (8)

Now, given sub-correspondences $\\{{\bf
x}_{i}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{i}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{i}^{\text{\tiny(N)}}\\}_{i=1,2,3,4,5,m}$ from only six world points ${\bf
X}_{1}$, ${\bf X}_{2}$, ${\bf X}_{3}$, ${\bf X}_{4}$, ${\bf X}_{5}$ and ${\bf
X}_{m}$ ($6\leq m\leq M$) on $N$ images ($N\geq 5$), we consider a $N\times 5$
matrix that

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

Let ${\bf e}_{m}=[e_{1m},e_{2m},e_{3m},e_{4m},e_{5m}]^{T}$ be the eigenvector
corresponding to the smallest eigenvalue of the $5\times 5$ positive
semidefinite matrix ${\bf\Lambda}_{m}^{T}{\bf\Lambda}_{m}$, and let
$x_{m},y_{m},z_{m}$ be three coordinates of the world points ${\bf X}_{m}$.
Thanks to the setting in (4), Theorem II in Le and Li (2022) proves that

$\begin{bmatrix}z_{m}(1-x_{m}-y_{m}-z_{m})+2y_{m}z_{m}\\\\[2.84526pt]
y_{m}(1-x_{m}-y_{m}-z_{m})+2y_{m}z_{m}\\\\[2.84526pt]
x_{m}(1-x_{m}-y_{m}-z_{m})+2y_{m}z_{m}\\\\[2.84526pt]
-2x_{m}y_{m}+2y_{m}z_{m}\\\\[2.84526pt]
-2x_{m}z_{m}+2y_{m}z_{m}\end{bmatrix}\sim\begin{bmatrix}e_{1m}\\\\[2.84526pt]
e_{2m}\\\\[2.84526pt] e_{3m}\\\\[2.84526pt] e_{4m}\\\\[2.84526pt]
e_{5m}\end{bmatrix}$ (10)

Hence, let

$\begin{split}f_{m}&=(2e_{2m}e_{5m}+2e_{1m}e_{4m}-3e_{1m}e_{2m}-e_{4m}e_{5m})(e_{1m}+e_{4m}-e_{2m}-e_{5m})\\\
&\hskip
170.71652pt+(e_{2m}-e_{1m})(e_{5m}-e_{1m})(e_{2m}-e_{4m})\\\\[1.42262pt]
f_{xm}&=(e_{1m}-e_{5m})(e_{5m}-e_{4m})(e_{2m}-e_{4m})\\\\[1.42262pt]
f_{ym}&=(e_{2m}e_{5m}-e_{1m}e_{4m})(e_{2m}-e_{4m})\\\\[1.42262pt]
f_{zm}&=(e_{2m}e_{5m}-e_{1m}e_{4m})(e_{1m}-e_{5m})\end{split}$ (11)

(10) easily implies

$x_{m}=\frac{f_{xm}}{f_{m}}\quad,\quad y_{m}=\frac{f_{ym}}{f_{m}}\quad,\quad
z_{m}=\frac{f_{zm}}{f_{m}}\,.$ (12)

(12) gives us the exact solution for the world point ${\bf X}_{m}$ ($6\leq
m\leq M)$ only based on ${\bf\Lambda}_{m}$ constructed by the correspondences
from six world points ${\bf X}_{1},\ldots,{\bf X}_{5}$ and ${\bf X}_{m}$.

When the solutions for all world points are acquired, the solution for the
projection matrix ${\bf P}_{n}$ can be derived by (2) via the matrix
$\mathcal{K}_{n}(\\{{\bf X}_{m}\\})$. Using some linear transformations on the
matrix $\mathcal{K}_{n}(\\{{\bf X}_{m}\\})$, (2) becomes

$\begin{bmatrix}p_{1n}&p_{2n}&p_{3n}&p_{4n}\\\\[2.84526pt]
p_{5n}&p_{6n}&p_{7n}&p_{8n}\end{bmatrix}=\begin{bmatrix}{\bf
x}_{4}^{\text{\tiny(n)}}&{\bf x}_{3}^{\text{\tiny(n)}}&{\bf
x}_{2}^{\text{\tiny(n)}}&{\bf
x}_{1}^{\text{\tiny(n)}}\end{bmatrix}\begin{bmatrix}p_{9n}+1&0&0&0\\\
0&p_{10n}+1&0&0\\\ 0&0&p_{11n}+1&0\\\ -1&-1&-1&1\end{bmatrix}$ (13)

and

$\begin{bmatrix}{\bf x}_{4}^{\text{\tiny(n)}}-{\bf
x}_{5}^{\text{\tiny(n)}}&{\bf x}_{3}^{\text{\tiny(n)}}-{\bf
x}_{5}^{\text{\tiny(n)}}&{\bf x}_{2}^{\text{\tiny(n)}}-{\bf
x}_{5}^{\text{\tiny(n)}}&{\bf x}_{1}^{\text{\tiny(n)}}-{\bf
x}_{5}^{\text{\tiny(n)}}\\\\[2.84526pt] \frac{f_{x6}}{f_{6}}({\bf
x}_{4}^{\text{\tiny(n)}}-{\bf
x}_{6}^{\text{\tiny(n)}})&\frac{f_{y6}}{f_{6}}({\bf
x}_{3}^{\text{\tiny(n)}}-{\bf
x}_{6}^{\text{\tiny(n)}})&\frac{f_{z6}}{f_{6}}({\bf
x}_{2}^{\text{\tiny(n)}}-{\bf x}_{6}^{\text{\tiny(n)}})&{\bf
x}_{1}^{\text{\tiny(n)}}-{\bf x}_{6}^{\text{\tiny(n)}}\\\\[2.84526pt]
\vdots&\vdots&\vdots&\vdots\\\\[2.84526pt] \frac{f_{xM}}{f_{M}}({\bf
x}_{4}^{\text{\tiny(n)}}-{\bf
x}_{M}^{\text{\tiny(n)}})&\frac{f_{yM}}{f_{M}}({\bf
x}_{3}^{\text{\tiny(n)}}-{\bf
x}_{M}^{\text{\tiny(n)}})&\frac{f_{zM}}{f_{M}}({\bf
x}_{2}^{\text{\tiny(n)}}-{\bf x}_{M}^{\text{\tiny(n)}})&{\bf
x}_{1}^{\text{\tiny(n)}}-{\bf
x}_{M}^{\text{\tiny(n)}}\end{bmatrix}\begin{bmatrix}p_{9n}+1\\\\[2.84526pt]
p_{10n}+1\\\\[2.84526pt] p_{11n}+1\\\\[2.84526pt] -2\end{bmatrix}={\bf 0}\,.$
(14)

The equations from the first row of the matrix in (14) imply

$p_{9n}+1=\frac{\xi_{23,5}^{\text{\tiny(n)}}(p_{11n}+1)-2\xi_{13,5}^{\text{\tiny(n)}}}{\xi_{34,5}^{\text{\tiny(n)}}}\qquad\text{and}\qquad
p_{10n}+1=\frac{2\xi_{14,5}^{\text{\tiny(n)}}-\xi_{24,5}^{\text{\tiny(n)}}(p_{11n}+1)}{\xi_{34,5}^{\text{\tiny(n)}}}\,.$
(15)

Replacing the solutions for $p_{9n}$ and $p_{10n}$ in (15) to the remain
equations in (14), the final variable $p_{11n}$ in the matrix ${\bf P}_{n}$ is
a solution of the following linear equations

$\begin{bmatrix}f_{y6}\xi_{34,6}^{\text{\tiny(n)}}\xi_{24,5}^{\text{\tiny(n)}}-f_{z6}\xi_{24,6}^{\text{\tiny(n)}}\xi_{34,5}^{\text{\tiny(n)}}&(f_{x6}+f_{y6}+f_{z6}-f_{6})\xi_{14,6}^{\text{\tiny(n)}}\xi_{34,5}^{\text{\tiny(n)}}-2f_{y6}\xi_{34,6}^{\text{\tiny(n)}}\xi_{14,5}^{\text{\tiny(n)}}\\\\[5.69054pt]
f_{y7}\xi_{34,7}^{\text{\tiny(n)}}\xi_{24,5}^{\text{\tiny(n)}}-f_{z7}\xi_{24,7}^{\text{\tiny(n)}}\xi_{34,5}^{\text{\tiny(n)}}&(f_{x7}+f_{y7}+f_{z7}-f_{7})\xi_{14,7}^{\text{\tiny(n)}}\xi_{34,5}^{\text{\tiny(n)}}-2f_{y7}\xi_{34,7}^{\text{\tiny(n)}}\xi_{14,5}^{\text{\tiny(n)}}\\\
\vdots&\vdots\\\\[2.84526pt]
f_{yM}\xi_{34,M}^{\text{\tiny(n)}}\xi_{24,5}^{\text{\tiny(n)}}-f_{zM}\xi_{24,M}^{\text{\tiny(n)}}\xi_{34,5}^{\text{\tiny(n)}}&(f_{xM}+f_{yM}+f_{zM}-f_{M})\xi_{14,M}^{\text{\tiny(n)}}\xi_{34,5}^{\text{\tiny(n)}}-2f_{yM}\xi_{34,M}^{\text{\tiny(n)}}\xi_{14,5}^{\text{\tiny(n)}}\end{bmatrix}\begin{bmatrix}p_{11n}+1\\\\[2.84526pt]
1\end{bmatrix}={\bf 0}\,.$ (16)

Concretely, the solution for the projection matrix ${\bf P}_{n}$ is given by

${\bf P}_{n}=\begin{bmatrix}{\bf x}_{4}^{\text{\tiny(n)}}&{\bf
x}_{3}^{\text{\tiny(n)}}&{\bf x}_{2}^{\text{\tiny(n)}}&{\bf
x}_{1}^{\text{\tiny(n)}}\\\\[5.69054pt]
1&1&1&1\end{bmatrix}\begin{bmatrix}\gamma_{n}&0&0&0\\\ 0&\beta_{n}&0&0\\\
0&0&\alpha_{n}&0\\\ -1&-1&-1&1\end{bmatrix}$ (17)

where $\alpha_{n}=p_{11n}+1$ is the solution of (16) and $\beta_{n}=p_{10n}+1$
and $\gamma_{n}=p_{9n}+1$ are given by (15).

Finally, the theorem below will formally present the solutions for the world
points and the projection matrices of the WPfC problem.

######  Theorem 1.

Given correspondences $\big{\\{}{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{m}^{\text{\tiny(N)}}\big{\\}}^{M}_{m=1}$ with $M\geq 6$ and $N\geq 5$, the
following group $\\{{\bf X}_{m},{\bf P}_{n}\\}$ with

$\displaystyle\begin{bmatrix}{\bf X}_{1}&{\bf X}_{2}&{\bf X}_{3}&{\bf
X}_{4}&{\bf X}_{5}\end{bmatrix}~{}=~{}\begin{bmatrix}0&0&0&1&1\\\ 0&0&1&0&1\\\
0&1&0&0&1\end{bmatrix}$ (18a) $\displaystyle~{}{\bf
X}_{m}=\frac{1}{f_{m}}\begin{bmatrix}f_{xm}\\\ f_{ym}\\\
f_{zm}\end{bmatrix}\hskip 159.33542pt\text{for all}\quad 6\leq m\leq M\,,$
(18b) $\displaystyle~{}{\bf P}_{n}=\begin{bmatrix}{\bf
x}_{4}^{\text{\tiny(n)}}&{\bf x}_{3}^{\text{\tiny(n)}}&{\bf
x}_{2}^{\text{\tiny(n)}}&{\bf x}_{1}^{\text{\tiny(n)}}\\\\[5.69054pt]
1&1&1&1\end{bmatrix}\begin{bmatrix}\gamma_{n}&0&0&0\\\ 0&\beta_{n}&0&0\\\
0&0&\alpha_{n}&0\\\ -1&-1&-1&1\end{bmatrix}\qquad\text{for all}\quad 1\leq
n\leq N\,,$ (18c)

is a solution w.r.t. these correspondences, where $f_{m},f_{xm},f_{ym},f_{zm}$
are given by (11), $\alpha_{n}$ is given by (16) and $\beta_{n},\gamma_{n}$
are given by (15).

###  2.3 Solutions from Estimated Correspondences

In the last subsection, we solve the WPfC w.r.t. correspondences in which (i)
the solution for the world point ${\bf X}_{m}~{}(m\geq 6)$ can be derived
independently with others, and (ii) there always exists a solution for
$\alpha_{n}=p_{11n}+1$ from (16). This subsection studies the WPfC w.r.t.
_estimated correspondences_. The estimated correspondences are not the
correspondences that there exist a group of world points and projection
matrices satisfying (1), but is expected to exist another group that (1)
closely occurs. Informally, $\\{\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)}}\\}^{M}_{m=1}$ are called the _estimated
correspondences_ if there exists the $M$ world points $\\{{\bf X}_{m}\\}$ and
$N$ projection matrices $\\{{\bf P}_{n}\\}$ such that

$\begin{bmatrix}{\bf p}_{1,n}\\\ {\bf p}_{2,n}\end{bmatrix}\begin{bmatrix}{\bf
X}_{m}\\\ 1\end{bmatrix}~{}\simeq~{}\hat{\bf x}_{m}^{\text{\tiny(n)}}{\bf
p}_{3,n}\begin{bmatrix}{\bf X}_{m}\\\ 1\end{bmatrix}\qquad\text{for all}\quad
m,n\,,$ (19)

where ${\bf p}_{i,n}$ denotes the $i$th row of ${\bf P}_{n}$.

From the vague definition of the estimated correspondences, we state the WPfC
w.r.t. estimated correspondences as the following optimization problem. Given
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)}}\\}^{M}_{m=1}$, find the $M$ world points $\\{{\bf
X}_{m}\\}$ and $N$ projection matrices $\\{{\bf P}_{n}\\}$ such that

$\sum^{M}_{m=1}\sum^{N}_{n=1}\left\\{\Bigg{(}\frac{{\bf p}_{1,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{u}_{mn}\Bigg{)}^{2}+\Bigg{(}\frac{{\bf
p}_{2,n}\big{[}{\bf X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{v}_{mn}\Bigg{)}^{2}\right\\}\quad\longrightarrow\quad\text{minimum}$
(20)

where $\hat{u}_{mn},\hat{v}_{mn}$ are two coordinates of $\hat{\bf
x}_{m}^{\text{\tiny(n)}}$. A value in the left side of (20) is called the
_objective value_ of $\\{{\bf X}_{m},{\bf P}_{n}\\}$ and it is always non-
negative. We denote this value by $d(\\{{\bf X}_{m},{\bf P}_{n}\\})$. Thanks
to the theory we study on the WPfC w.r.t. correspondences in the previous
subsection, by finding the group $\\{{\bf X}^{\star}_{m},{\bf
P}^{\star}_{n}\\}$ such that their objective values are zero, a proposition
below solves totally the optimization (20) for $M\leq 5$.

######  Proposition 2.

When $M\leq 5$, there always exists a group $\\{{\bf X}^{\star}_{m},{\bf
P}^{\star}_{n}\\}$ such that its objective value is zero. It means $\\{{\bf
X}^{\star}_{m},{\bf P}^{\star}_{n}\\}$ is a global optimal solution for (20).

###### Proof.

We start the proof of Proposition 2 with a mention that the ambiguity given by
Proposition 1 is still correct for the WPfC w.r.t. estimated correspondences.
Indeed, the global optimal solution $\\{{\bf X}^{\star}_{m},{\bf
P}^{\star}_{n}\\}$ for (20) will be found based on the setting (4) for the
world points and

${\bf P}^{\star}_{n}=\begin{bmatrix}\hat{\bf x}_{4}^{\text{\tiny(n)}}&\hat{\bf
x}_{3}^{\text{\tiny(n)}}&\hat{\bf x}_{2}^{\text{\tiny(n)}}&\hat{\bf
x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
1&1&1&1\end{bmatrix}\begin{bmatrix}\gamma_{n}&0&0&0\\\ 0&\beta_{n}&0&0\\\
0&0&\alpha_{n}&0\\\ -1&-1&-1&1\end{bmatrix}$ (21)

for the projection matrices. It easily sees that when $M=1$ with the estimated
correspondences $\\{\hat{\bf x}_{1}^{\text{\tiny(n)}}\\}^{N}_{n=1}$, we always
have

${\bf P}^{\star}_{n}\begin{bmatrix}{\bf X}^{\star}_{1}\\\
1\end{bmatrix}=\begin{bmatrix}\hat{\bf x}_{4}^{\text{\tiny(n)}}&\hat{\bf
x}_{3}^{\text{\tiny(n)}}&\hat{\bf x}_{2}^{\text{\tiny(n)}}&\hat{\bf
x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
1&1&1&1\end{bmatrix}\begin{bmatrix}\gamma_{n}&0&0&0\\\ 0&\beta_{n}&0&0\\\
0&0&\alpha_{n}&0\\\ -1&-1&-1&1\end{bmatrix}\begin{bmatrix}0\\\ 0\\\ 0\\\
1\end{bmatrix}=\begin{bmatrix}\hat{\bf x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
1\end{bmatrix}$

for any values of the remain parameters $\hat{\bf
x}_{2}^{\text{\tiny(n)}},\hat{\bf x}_{3}^{\text{\tiny(n)}},\hat{\bf
x}_{4}^{\text{\tiny(n)}}$ and $\alpha_{n},\beta_{n},\gamma_{n}$. The equation
above says that the objective value of $\\{{\bf X}^{\star}_{1},{\bf
P}^{\star}_{n}\\}$ is zero and $\\{{\bf X}^{\star}_{1},{\bf P}^{\star}_{n}\\}$
is a global optimal solution for (20) w.r.t. the estimated correspondences
$\\{\hat{\bf x}_{1}^{\text{\tiny(n)}}\\}^{N}_{n=1}$. We do similar
explanations for the case $M=2,3,$ and 4 by fixing the values of $\\{\hat{\bf
x}_{1}^{\text{\tiny(n)}},\hat{\bf x}_{2}^{\text{\tiny(n)}}\\}$ (for $M=2$),
$\\{\hat{\bf x}_{1}^{\text{\tiny(n)}},\hat{\bf
x}_{2}^{\text{\tiny(n)}},\hat{\bf x}_{3}^{\text{\tiny(n)}}\\}$ (for $M=3$),
and $\\{\hat{\bf x}_{1}^{\text{\tiny(n)}},\hat{\bf
x}_{2}^{\text{\tiny(n)}},\hat{\bf x}_{3}^{\text{\tiny(n)}},\hat{\bf
x}_{4}^{\text{\tiny(n)}}\\}$ (for $M=4$) in (21) from the estimated
correspondences. For example, in the case $M=4$ with the estimated
correspondences $\\{\hat{\bf x}_{1}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{2}^{\text{\tiny(n)}}\,,\,\hat{\bf x}_{3}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{4}^{\text{\tiny(n)}}\\}^{N}_{n=1}$, we can choose any values for
$\alpha_{n},\beta_{n},\gamma_{n}$ and always guarantee that the zero value for
the objective value of $\\{{\bf X}^{\star}_{1},{\bf X}^{\star}_{2},{\bf
X}^{\star}_{3},{\bf X}^{\star}_{4},{\bf P}^{\star}_{n}\\}$ because

$\begin{split}{\bf P}^{\star}_{n}\begin{bmatrix}{\bf X}^{\star}_{1}&{\bf
X}^{\star}_{2}&{\bf X}^{\star}_{3}&{\bf X}^{\star}_{4}\\\\[2.84526pt]
1&1&1&1\end{bmatrix}&=\begin{bmatrix}\hat{\bf
x}_{4}^{\text{\tiny(n)}}&\hat{\bf x}_{3}^{\text{\tiny(n)}}&\hat{\bf
x}_{2}^{\text{\tiny(n)}}&\hat{\bf x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
1&1&1&1\end{bmatrix}\begin{bmatrix}\gamma_{n}&0&0&0\\\ 0&\beta_{n}&0&0\\\
0&0&\alpha_{n}&0\\\ -1&-1&-1&1\end{bmatrix}\begin{bmatrix}0&0&0&1\\\
0&0&1&0\\\ 0&1&0&0\\\ 1&1&1&1\end{bmatrix}\\\\[5.69054pt]
&=\begin{bmatrix}\gamma_{n}\hat{\bf x}_{4}^{\text{\tiny(n)}}-\hat{\bf
x}_{1}^{\text{\tiny(n)}}&\beta_{n}\hat{\bf x}_{3}^{\text{\tiny(n)}}-\hat{\bf
x}_{1}^{\text{\tiny(n)}}&\alpha_{n}\hat{\bf x}_{2}^{\text{\tiny(n)}}-\hat{\bf
x}_{1}^{\text{\tiny(n)}}&\hat{\bf x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
\gamma_{n}-1&\beta_{n}-1&\alpha_{n}-1&1\end{bmatrix}\begin{bmatrix}0&0&0&1\\\
0&0&1&0\\\ 0&1&0&0\\\ 1&1&1&1\end{bmatrix}\\\\[5.69054pt]
&=\begin{bmatrix}\hat{\bf x}_{1}^{\text{\tiny(n)}}&\alpha_{n}\hat{\bf
x}_{2}^{\text{\tiny(n)}}&\beta_{n}\hat{\bf
x}_{3}^{\text{\tiny(n)}}&\gamma_{n}\hat{\bf
x}_{4}^{\text{\tiny(n)}}\\\\[2.84526pt]
1&\alpha_{n}&\beta_{n}&\gamma_{n}\end{bmatrix}\\\\[5.69054pt]
&\sim\begin{bmatrix}\hat{\bf x}_{1}^{\text{\tiny(n)}}&\hat{\bf
x}_{2}^{\text{\tiny(n)}}&\hat{\bf x}_{3}^{\text{\tiny(n)}}&\hat{\bf
x}_{4}^{\text{\tiny(n)}}\\\\[2.84526pt] 1&1&1&1\end{bmatrix}.\end{split}$

For the case $M=5$ with the estimated correspondences $\\{\hat{\bf
x}_{1}^{\text{\tiny(n)}}\,,\,\hat{\bf x}_{2}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{3}^{\text{\tiny(n)}}\,,\,\hat{\bf x}_{4}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{5}^{\text{\tiny(n)}}\\}^{N}_{n=1}$, we need to choose $\beta_{n}$ and
$\gamma_{n}$ such that

$\beta_{n}=\frac{1}{\hat{\xi}_{34,5}^{\text{\tiny(n)}}}\big{(}2\hat{\xi}_{14,5}^{\text{\tiny(n)}}-\hat{\xi}_{24,5}^{\text{\tiny(n)}}\alpha_{n}\big{)}\qquad\text{and}\qquad\gamma_{n}=\frac{1}{\hat{\xi}_{34,5}^{\text{\tiny(n)}}}\big{(}\hat{\xi}_{23,5}^{\text{\tiny(n)}}\alpha_{n}-2\hat{\xi}_{13,5}^{\text{\tiny(n)}}\big{)}$
(22)

where $\hat{\xi}_{m_{1}m_{2},m_{3}}$ is given by (8) when ${\bf
x}_{m}^{\text{\tiny(n)}}$ is replaced by its estimation $\hat{\bf
x}_{m}^{\text{\tiny(n)}}$. From that we confirm

$\begin{split}&(\gamma_{n}-1)(\hat{\bf x}_{4}^{\text{\tiny(n)}}-\hat{\bf
x}_{5}^{\text{\tiny(n)}})+(\beta_{n}-1)(\hat{\bf
x}_{3}^{\text{\tiny(n)}}-\hat{\bf
x}_{5}^{\text{\tiny(n)}})+(\alpha_{n}-1)(\hat{\bf
x}_{2}^{\text{\tiny(n)}}-\hat{\bf x}_{5}^{\text{\tiny(n)}})\\\
&\quad\qquad+(\hat{\bf x}_{4}^{\text{\tiny(n)}}-\hat{\bf
x}_{5}^{\text{\tiny(n)}})+(\hat{\bf x}_{3}^{\text{\tiny(n)}}-\hat{\bf
x}_{5}^{\text{\tiny(n)}})+(\hat{\bf x}_{2}^{\text{\tiny(n)}}-\hat{\bf
x}_{5}^{\text{\tiny(n)}})-2(\hat{\bf x}_{1}^{\text{\tiny(n)}}-\hat{\bf
x}_{5}^{\text{\tiny(n)}})~{}=~{}0\,,\end{split}$

as the explanation in (14) and (15). Then

$\begin{split}{\bf P}^{\star}_{n}\begin{bmatrix}{\bf
X}^{\star}_{5}\\\\[2.84526pt] 1\end{bmatrix}&=\begin{bmatrix}\hat{\bf
x}_{4}^{\text{\tiny(n)}}&\hat{\bf x}_{3}^{\text{\tiny(n)}}&\hat{\bf
x}_{2}^{\text{\tiny(n)}}&\hat{\bf x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
1&1&1&1\end{bmatrix}\begin{bmatrix}\gamma_{n}&0&0&0\\\ 0&\beta_{n}&0&0\\\
0&0&\alpha_{n}&0\\\ -1&-1&-1&1\end{bmatrix}\begin{bmatrix}1\\\ 1\\\ 1\\\
1\end{bmatrix}\\\\[5.69054pt] &=\begin{bmatrix}\gamma_{n}\hat{\bf
x}_{4}^{\text{\tiny(n)}}+\beta_{n}\hat{\bf
x}_{3}^{\text{\tiny(n)}}+\alpha_{n}\hat{\bf x}_{2}^{\text{\tiny(n)}}-2\hat{\bf
x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
\alpha_{n}+\beta_{n}+\gamma_{n}-2\end{bmatrix}~{}\sim\begin{bmatrix}\hat{\bf
x}_{5}^{\text{\tiny(n)}}\\\\[2.84526pt] 1\end{bmatrix}\end{split}$

and the objective value of $\\{{\bf X}^{\star}_{1},\ldots,{\bf
X}^{\star}_{5},{\bf P}^{\star}_{n}\\}$ is zero for arbitrary values of
$\alpha_{n},~{}n=1,2,\ldots,N$. ∎

By exploiting the ambiguities of WPfC, Proposition 2 proposes some simple and
potential solutions for WPfC with at most five world points. Interestingly,
all these solutions are global optimal. In optimization theory, finding global
optimal solutions is the most important problem we hope to solve.
Unfortunately, finding global solutions for the non-convex and non-concave
objective functions like (20) is difficult (Horst and Tuy, 1996). Our strategy
to solve the optimization (20) is summarized as follows. First, basing on the
global optimal solutions in Proposition 2, we find closed-form solutions
$\\{{\bf X}_{m}^{\circ},{\bf P}_{n}^{\circ}\\}$ for (20) with expecting that
these closed-form solutions are closed to the global optimal ones. Second, we
propose an iterative algorithm to generate some other better solutions
$\\{{\bf X}^{*}_{m},{\bf P}^{*}_{n}\\}$ from its initialization $\\{{\bf
X}_{m}^{\circ},{\bf P}_{n}^{\circ}\\}$, the closed-form solution found by the
first step.

####  2.3.1 Closed-form solutions

This subsection starts with the closed-form solutions for WPfC when the number
of world points are six ($M=6$). These closed-forms are global optimal
solutions of another optimization that is from (20) and adding five
constraints related to the first five world points. This optimization is
stated as follows.

$\begin{split}&\arg\min_{\big{\\{}{\bf X}_{m},{\bf
P}_{n}\big{\\}}}\sum^{N}_{n=1}\left\\{\Bigg{(}\frac{{\bf p}_{1,n}\big{[}{\bf
X}_{6}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{6}^{T}\,,\,1\big{]}^{T}}-\hat{u}_{6n}\Bigg{)}^{2}+\Bigg{(}\frac{{\bf
p}_{2,n}\big{[}{\bf X}_{6}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{6}^{T}\,,\,1\big{]}^{T}}-\hat{v}_{6n}\Bigg{)}^{2}\right\\}\\\\[5.69054pt]
&\text{subject to }\quad{\bf P}_{n}\begin{bmatrix}{\bf X}_{m}\\\
1\end{bmatrix}\sim\begin{bmatrix}\hat{\bf x}_{m}^{\text{\tiny(n)}}\\\
1\end{bmatrix}\quad\text{for all}\quad m=1,2,3,4,5,\quad
n=1,2,\ldots,N.\end{split}$ (23)

Note that under the constraints ${\bf P}_{n}\begin{bmatrix}{\bf X}_{m}\\\
1\end{bmatrix}\sim\begin{bmatrix}\hat{\bf x}_{m}^{\text{\tiny(n)}}\\\
1\end{bmatrix}$ for all $1\leq m\leq 5$,

$\sum^{5}_{m=1}\sum^{N}_{n=1}\left\\{\Bigg{(}\frac{{\bf p}_{1,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{u}_{mn}\Bigg{)}^{2}+\Bigg{(}\frac{{\bf
p}_{2,n}\big{[}{\bf X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{v}_{mn}\Bigg{)}^{2}\right\\}=0\,.$

Thus the objective value of (23) is the exact objective value of (20). The
proof of Proposition 2 says that the group $\\{{\bf X}^{\star}_{1},{\bf
X}^{\star}_{2},{\bf X}^{\star}_{3},{\bf X}^{\star}_{4},{\bf
X}^{\star}_{5},{\bf X}^{\star}_{6},{\bf P}^{\star}_{n}\\}$ given by

$\displaystyle\begin{bmatrix}{\bf X}^{\star}_{1}&{\bf X}^{\star}_{2}&{\bf
X}^{\star}_{3}&{\bf X}^{\star}_{4}&{\bf X}^{\star}_{5}&{\bf
X}^{\star}_{6}\end{bmatrix}=\begin{bmatrix}0&0&0&1&1&f^{\star}_{x}/f^{\star}\\\
0&0&1&0&1&f^{\star}_{y}/f^{\star}\\\
0&1&0&0&1&f^{\star}_{z}/f^{\star}\end{bmatrix}$ (24a) $\displaystyle{\bf
P}^{\star}_{n}=\begin{bmatrix}\hat{\bf x}_{4}^{\text{\tiny(n)}}&\hat{\bf
x}_{3}^{\text{\tiny(n)}}&\hat{\bf x}_{2}^{\text{\tiny(n)}}&\hat{\bf
x}_{1}^{\text{\tiny(n)}}\\\\[2.84526pt]
1&1&1&1\end{bmatrix}\begin{bmatrix}\gamma^{\star}_{n}&0&0&0\\\
0&\beta^{\star}_{n}&0&0\\\ 0&0&\alpha^{\star}_{n}&0\\\
-1&-1&-1&1\end{bmatrix}\quad(n=1,2,\ldots,N),$ (24b)
$\displaystyle\text{with}\quad\beta^{\star}_{n}=\frac{1}{\hat{\xi}_{34,5}^{\text{\tiny(n)}}}\big{(}2\hat{\xi}_{14,5}^{\text{\tiny(n)}}-\hat{\xi}_{24,5}^{\text{\tiny(n)}}\alpha^{\star}_{n}\big{)},~{}~{}\gamma^{\star}_{n}=\frac{1}{\hat{\xi}_{34,5}^{\text{\tiny(n)}}}\big{(}\hat{\xi}_{23,5}^{\text{\tiny(n)}}\alpha^{\star}_{n}-2\hat{\xi}_{13,5}^{\text{\tiny(n)}}\big{)}$

will satisfy the constraints of (23) for any values of
$f^{\star},f^{\star}_{x},f^{\star}_{y},f^{\star}_{z},$ and
$\\{\alpha^{\star}_{n}\\}^{N}_{n=1}$. Based on this fact, the following
proposition gives global optimal solutions for (23).

######  Proposition 3.

As $f^{\star},f^{\star}_{x},f^{\star}_{y},f^{\star}_{z}$ are given by (9)-(11)
in which ${\bf\Lambda}_{6}$ computing based on the estimated correspondences,
and

$\alpha^{\star}_{n}~{}=~{}\frac{(a_{2n}^{2}+b_{2n}^{2})c_{1n}^{2}-(a_{1n}^{2}+b_{1n}^{2})c_{2n}^{2}\pm\sqrt{\Delta_{n}}}{2(a_{1n}^{2}+b_{1n}^{2})c_{1n}c_{2n}-2(a_{1n}a_{2n}+b_{1n}b_{2n})c_{1n}^{2}}$
(25)

where

$\begin{split}a_{1n}&=\hat{\xi}_{23,5}^{\text{\tiny(n)}}f^{\star}_{x}(\hat{u}_{4n}-\hat{u}_{6n})-\hat{\xi}_{24,5}^{\text{\tiny(n)}}f^{\star}_{y}(\hat{u}_{3n}-\hat{u}_{6n})+f^{\star}_{z}(\hat{u}_{2n}-\hat{u}_{6n})\\\\[2.84526pt]
a_{2n}&=-2\hat{\xi}_{13,5}^{\text{\tiny(n)}}f^{\star}_{x}(\hat{u}_{4n}-\hat{u}_{6n})+2\hat{\xi}_{14,5}^{\text{\tiny(n)}}f^{\star}_{y}(\hat{u}_{3n}-\hat{u}_{6n})+(f^{\star}-f^{\star}_{x}-f^{\star}_{y}-f^{\star}_{z})(\hat{u}_{1n}-\hat{u}_{6n})\\\\[2.84526pt]
b_{1n}&=\hat{\xi}_{23,5}^{\text{\tiny(n)}}f^{\star}_{x}(\hat{v}_{4n}-\hat{v}_{6n})-\hat{\xi}_{24,5}^{\text{\tiny(n)}}f^{\star}_{y}(\hat{v}_{3n}-\hat{v}_{6n})+f^{\star}_{z}(\hat{v}_{2n}-\hat{v}_{6n})\\\\[2.84526pt]
b_{2n}&=-2\hat{\xi}_{13,5}^{\text{\tiny(n)}}f^{\star}_{x}(\hat{v}_{4n}-\hat{v}_{6n})+2\hat{\xi}_{14,5}^{\text{\tiny(n)}}f^{\star}_{y}(\hat{v}_{3n}-\hat{v}_{6n})+(f^{\star}-f^{\star}_{x}-f^{\star}_{y}-f^{\star}_{z})(\hat{v}_{1n}-\hat{v}_{6n})\\\\[2.84526pt]
c_{1n}&=\hat{\xi}_{23,5}^{\text{\tiny(n)}}f^{\star}_{x}-\hat{\xi}_{24,5}^{\text{\tiny(n)}}f^{\star}_{y}+f^{\star}_{z}\\\\[2.84526pt]
c_{2n}&=-2\hat{\xi}_{13,5}^{\text{\tiny(n)}}f^{\star}_{x}+2\hat{\xi}_{14,5}^{\text{\tiny(n)}}f^{\star}_{y}+(f^{\star}-f^{\star}_{x}-f^{\star}_{y}-f^{\star}_{z})\\\\[2.84526pt]
\Delta_{n}&=\big{[}(a_{1n}^{2}+b_{1n}^{2})c_{2n}^{2}-(a_{2n}^{2}+b_{2n}^{2})c_{1n}^{2}\big{]}^{2}\\\
&\quad-4\big{[}(a_{1n}^{2}+b_{1n}^{2})c_{1n}c_{2n}-(a_{1n}a_{2n}+b_{1n}b_{2n})c_{1n}^{2}\big{]}\big{[}(a_{1n}a_{2n}+b_{1n}b_{2n})c_{2n}^{2}-(a_{2n}^{2}+b_{2n}^{2})c_{1n}c_{2n}\big{]}\,,\end{split}$
(26)

the group $\\{{\bf X}^{\star}_{1},{\bf X}^{\star}_{2},{\bf X}^{\star}_{3},{\bf
X}^{\star}_{4},{\bf X}^{\star}_{5},{\bf X}^{\star}_{6},{\bf P}^{\star}_{n}\\}$
will be a global optimal solution for the optimization (23).

###### Proof.

From the setting of ${\bf X}^{\star}_{1},{\bf X}^{\star}_{2},{\bf
X}^{\star}_{3},{\bf X}^{\star}_{4},{\bf X}^{\star}_{5},$ and $\\{{\bf
P}^{\star}_{n}\\}^{N}_{n=1}$, (23) becomes

$\begin{split}&\arg\min_{\big{\\{}f,f_{x},f_{y},f_{z},\alpha_{n}\big{\\}}\,}\sum^{N}_{n=1}\Bigg{\\{}\frac{\big{[}\gamma_{n}f_{x}(\hat{u}_{4n}-\hat{u}_{6n})+\beta_{n}f_{y}(\hat{u}_{3n}-\hat{u}_{6n})+\alpha_{n}f_{z}(\hat{u}_{2n}-\hat{u}_{6n})+(f-f_{x}-f_{y}-f_{z})(\hat{u}_{1n}-\hat{u}_{6n})\big{]}^{2}}{\big{[}\gamma_{n}f_{x}+\beta_{n}f_{y}+\alpha_{n}f_{z}+(f-f_{x}-f_{y}-f_{z})\big{]}^{2}}\\\\[5.69054pt]
&\hskip
65.44133pt+\frac{\big{[}\gamma_{n}f_{x}(\hat{v}_{4n}-\hat{v}_{6n})+\beta_{n}f_{y}(\hat{v}_{3n}-\hat{v}_{6n})+\alpha_{n}f_{z}(\hat{v}_{2n}-\hat{v}_{6n})+(f-f_{x}-f_{y}-f_{z})(\hat{v}_{1n}-\hat{v}_{6n})\big{]}^{2}}{\big{[}\gamma_{n}f_{x}+\beta_{n}f_{y}+\alpha_{n}f_{z}+(f-f_{x}-f_{y}-f_{z})\big{]}^{2}}\Bigg{\\}}\end{split}$
(27)

where $a_{1n},b_{1n},c_{1n}$ and $a_{2n},b_{2n},c_{2n}$ are given by (26).
When $f^{\star},f^{\star}_{x},f^{\star}_{y},f^{\star}_{z}$ are fixed, the
optimization (27) is globally optimized by the values
$\\{\alpha^{\star}_{n}\\}^{N}_{n=1}$ given by (25). Hence, to finish the proof
of Proposition 3 we need to prove that (27) is globally optimized at
$f^{\star},f^{\star}_{x},f^{\star}_{y},f^{\star}_{z}$ given by (9)-(11) while
${\bf P}^{\star}_{n},\alpha^{\star}_{n},\beta^{\star}_{n},\gamma^{\star}_{n}$
are functions of $f^{\star},f^{\star}_{x},f^{\star}_{y}$ and $f^{\star}_{z}$.
Thanks to Theorem II in Le and Li (2022), we know that the sixth world point
${\bf
X}^{\star}_{6}=\frac{1}{f^{\star}}[f^{\star}_{x}\,,\,f^{\star}_{y}\,,\,f^{\star}_{z}]^{T}$
should be found from the following optimization

$\\{f^{\star}\,,\,f^{\star}_{x}\,,\,f^{\star}_{y}\,,\,f^{\star}_{z}\\}=\quad\arg\min_{\big{\\{}f,f_{x},f_{y},f_{z}\big{\\}}}\left\|~{}{\bf\Lambda}_{6}\begin{bmatrix}f_{z}(f-f_{x}-f_{y}-f_{z})+2f_{y}f_{z}\\\\[2.84526pt]
f_{y}(f-f_{x}-f_{y}-f_{z})+2f_{y}f_{z}\\\\[2.84526pt]
f_{x}(f-f_{x}-f_{y}-f_{z})+2f_{y}f_{z}\\\\[2.84526pt]
-2f_{x}f_{y}+2f_{y}f_{z}\\\\[2.84526pt]
-2f_{x}f_{z}+2f_{y}f_{z}\end{bmatrix}~{}\right\|^{2}_{2}$ (28)

where ${\bf\Lambda}_{6}$ given by (9) is the $N\times 5$ matrix computing from
the estimated correspondences. Let $[e_{1},e_{2},e_{3},e_{4},e_{5}]^{T}$ be
the eigenvector corresponding to the smallest eigenvalue of
${\bf\Lambda}^{T}_{6}{\bf\Lambda}_{6}$. The optimization (28) will be globally
optimized if

$\begin{bmatrix}f_{z}(f-f_{x}-f_{y}-f_{z})+2f_{y}f_{z}\\\\[2.84526pt]
f_{y}(f-f_{x}-f_{y}-f_{z})+2f_{y}f_{z}\\\\[2.84526pt]
f_{x}(f-f_{x}-f_{y}-f_{z})+2f_{y}f_{z}\\\\[2.84526pt]
-2f_{x}f_{y}+2f_{y}f_{z}\\\\[2.84526pt]
-2f_{x}f_{z}+2f_{y}f_{z}\end{bmatrix}\sim\begin{bmatrix}e_{1}\\\\[2.84526pt]
e_{2}\\\\[2.84526pt] e_{3}\\\\[2.84526pt] e_{4}\\\\[2.84526pt]
e_{5}\end{bmatrix}\,.$ (29)

The parameters $\\{f^{\star},f^{\star}_{x},f^{\star}_{y},f^{\star}_{z}\\}$
given by (11) satisfy (29). Thus, they are the global optimal solutions for
(28) and also for (27). Proposition 3 is proven. ∎

Note that Proposition 3 derives the global optimal solutions for (23) but
these solutions are not global optimal solutions for (20). In addition,
because of the strict constraints in (23), its global optimal solutions are
far to ones of (20). In the case $M>6$, the optimization (23) naturally
becomes

$\begin{split}&\arg\min_{\big{\\{}{\bf X}_{m},{\bf
P}_{n}\big{\\}}}\sum^{M}_{m=6}\,\sum^{N}_{n=1}\left\\{\Bigg{(}\frac{{\bf
p}_{1,n}\big{[}{\bf X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{u}_{mn}\Bigg{)}^{2}+\Bigg{(}\frac{{\bf
p}_{2,n}\big{[}{\bf X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{v}_{mn}\Bigg{)}^{2}\right\\}\\\\[5.69054pt]
&\text{subject to }\quad{\bf P}_{n}\begin{bmatrix}{\bf X}_{m}\\\
1\end{bmatrix}\sim\begin{bmatrix}\hat{\bf x}_{m}^{\text{\tiny(n)}}\\\
1\end{bmatrix}\quad\text{for all}\quad 1\leq m\leq 5,\quad 1\leq n\leq
N.\end{split}$ (30)

The optimization (30) is more complex than the optimization (23). Finding
global optimal solutions for (30) is too difficult. Moreover, similar as the
case of $M=6$, we believe that the global optimal solutions for (30) are far
to the global optimal solutions for (20). Because of this reason, this study
does not focus on obtaining the global optimal solutions for (30). We shall
use the global optimal solutions in the case $M=6$ as the candidates for the
optimal solutions in the case $M>6$. More precisely, to generate optimal
solutions for (30), we first propose the optimal world points ${\bf
X}^{\circ}_{m}=\frac{1}{f^{\star}_{m}}[f^{\star}_{xm}\,,\,f^{\star}_{ym}\,,\,f^{\star}_{zm}]^{T}$,
($6\leq m\leq M$) as the global optimal solutions for (28) when
${\bf\Lambda}_{6}$ is replaced by ${\bf\Lambda}_{m}$. Then for each
$m\in\\{6,7,\ldots,M\\}$ that brings a group of
$\\{f^{\star},f^{\star}_{x},f^{\star}_{y},f^{\star}_{z}\\}$ and
$\\{a_{1n},b_{1n},c_{1n},a_{2n},b_{2n},c_{2n},\Delta_{n}\\}^{N}_{n=1}$, one
candidate for $\\{\alpha^{\star}_{n}\\}^{N}_{n=1}$ is generated by (25), and a
corresponded candidate for $\\{{\bf P}^{\circ}_{n}\\}^{N}_{n=1}$ is obtained
by (24b). From a lot of these candidates, the best one is chosen based on the
objective value in (30). Formally, our process on estimating the closed-form
solutions for WPfC is presented by Algorithm 1. In this paper, we denote

$\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}=\texttt{CF-
WPfC}\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}\\}^{M}_{m=1}\big{)}$

to say that $\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$ is the output of
the CF-WPfC algorithm with the input $\\{\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}\\}^{M}_{m=1}$.

Algorithm 1 Closed-form solutions for WPfC (CF-WPfC)

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.

Conditions: $M\geq 6$ and $N\geq 5$.

Implementation:

$\text{Eval}\longleftarrow 10^{8}$: a huge number

For all $1\leq m_{1}<m_{2}<m_{3}<m_{4}<m_{5}\leq M$:

1. $[{\bf X}_{m_{1}}\,,\,{\bf X}_{m_{2}}\,,\,{\bf X}_{m_{3}}\,,\,{\bf X}_{m_{4}}\,,\,{\bf X}_{m_{5}}]\quad\longleftarrow\quad\begin{bmatrix}0&0&0&1&1\\\ 0&0&1&0&1\\\ 0&1&0&0&1\end{bmatrix}$ as the setting (4).

2. For all $1\leq m\leq M$ such that $m\notin\\{m_{1},m_{2},m_{3},m_{4},m_{5}\\}$:

a.
$\hat{\xi}_{i_{1}i_{2},j}^{\text{\tiny(n)}}~{}\overset{\eqref{eq:Xi}}{\longleftarrow}~{}\big{\\{}\hat{\bf
x}_{i_{1}}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{i_{2}}^{\text{\tiny(n)}}\,,\,\hat{\bf x}_{j}^{\text{\tiny(n)}}\big{\\}}$
for all $1\leq n\leq N$,

b. ${\bf\Lambda}_{m}\hskip
8.53581pt~{}\overset{\eqref{eq:Lambda}}{\longleftarrow}~{}\big{\\{}\hat{\bf
x}_{i}^{\text{\tiny(1)}}\leftrightarrow\hat{\bf
x}_{i}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\hat{\bf
x}_{i}^{\text{\tiny(N)}}\big{\\}}_{i\in\\{m_{1},m_{2},m_{3},m_{4},m_{5},m\\}}$

c. $[e_{1m},e_{2m},e_{3m},e_{4m},e_{5m}]^{T}$: the eigenvector corresponding
to the smallest eigenvalue of ${\bf\Lambda}^{T}_{m}{\bf\Lambda}_{m}$,

d.
$\\{f_{m},f_{xm},f_{ym},f_{zm}\\}~{}\overset{\eqref{eq:f_Eigen}}{\longleftarrow}~{}\\{e_{1m},e_{2m},e_{3m},e_{4m},e_{5m}\\}$

e. ${\bf
X}_{m}~{}\longleftarrow~{}\frac{1}{f_{m}}[f_{xm}\,,\,f_{ym}\,,\,f_{zm}]^{T}$.

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

a.
$\\{a_{1n},a_{2n},b_{1n},b_{2n},c_{1n},c_{2n},\Delta_{n}\\}~{}\overset{\eqref{eq:CF_alpha_1}}{\longleftarrow}~{}\\{f_{m},f_{xm},f_{ym},f_{zm}\\}$,
$\\{\hat{\xi}_{i_{1}i_{2},j}^{\text{\tiny(n)}}\\}$, $\big{\\{}\hat{\bf
x}_{i}^{\text{\tiny(n)}}\big{\\}}_{i\in\\{m_{1},m_{2},m_{3},m_{4},m_{5},m\\}}$

b. if $\Delta_{n}>0$:

$\alpha_{n}~{}\overset{\eqref{eq:CF_alpha}}{\longleftarrow}~{}\frac{(a_{2n}^{2}+b_{2n}^{2})c_{1n}^{2}-(a_{1n}^{2}+b_{1n}^{2})c_{2n}^{2}\pm\sqrt{\Delta_{n}}}{2(a_{1n}^{2}+b_{1n}^{2})c_{1n}c_{2n}-2(a_{1n}a_{2n}+b_{1n}b_{2n})c_{1n}^{2}}$

else:
$\alpha_{n}~{}\longleftarrow~{}\big{\\{}-a_{2n}/a_{1n}~{},~{}-b_{2n}/b_{1n}~{},~{}-(a_{1n}a_{2n}+b_{1n}b_{2n})/(a_{1n}^{2}+b_{1n}^{2})\big{\\}}$

c. ${\bf
P}_{n}~{}\overset{\eqref{eq:CF_PM_6}}{\longleftarrow}~{}\big{\\{}\hat{\bf
x}_{m_{1}}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{m_{2}}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{m_{3}}^{\text{\tiny(n)}}\,,\,\hat{\bf
x}_{m_{4}}^{\text{\tiny(n)}}\,,\,\alpha_{n}\,,\,\beta_{n}\,,\,\gamma_{n}\big{\\}}$

4\.

$\text{Obj}\longleftarrow\sum_{m\notin\\{m_{1},m_{2},m_{3},m_{4},m_{5}\\}}\,\sum^{N}_{n=1}\left\\{\Bigg{(}\frac{{\bf
p}_{1,n}\big{[}{\bf X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{u}_{mn}\Bigg{)}^{2}+\Bigg{(}\frac{{\bf
p}_{2,n}\big{[}{\bf X}_{m}^{T}\,,\,1\big{]}^{T}}{{\bf p}_{3,n}\big{[}{\bf
X}_{m}^{T}\,,\,1\big{]}^{T}}-\hat{v}_{mn}\Bigg{)}^{2}\right\\}$

5. If $\text{Obj}<\text{Eval}$:

$\text{Eval}\longleftarrow\text{Obj}\qquad\text{and}\qquad\big{\\{}{\bf
X}^{\circ}_{m},{\bf P}^{\circ}_{n}\big{\\}}~{}\longleftarrow~{}\big{\\{}{\bf
X}_{m},{\bf P}_{n}\big{\\}}\,.$

Output: $\big{\\{}{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\big{\\}}$ .

####  2.3.2 Iterative solutions

The output $\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$ of the CF-WPfC
algorithm is an optimal solution for (30), from that there always exist five
world points ${\bf X}^{\circ}_{m_{1}},{\bf X}^{\circ}_{m_{2}},{\bf
X}^{\circ}_{m_{3}},{\bf X}^{\circ}_{m_{4}},{\bf X}^{\circ}_{m_{5}}$ such that

$\qquad\qquad{\bf P}^{\circ}_{n}\begin{bmatrix}{\bf
X}^{\circ}_{m_{i}}\\\\[2.84526pt] 1\end{bmatrix}\sim\begin{bmatrix}\hat{\bf
x}_{m_{i}}^{\text{\tiny(n)}}\\\\[2.84526pt] 1\end{bmatrix}\qquad\text{for
all}\quad n\quad\text{and}\quad i=1,2,3,4,5\,.$

Under these constraints, the solution $\\{{\bf X}^{\circ}_{m},{\bf
P}^{\circ}_{n}\\}$ can be far to the global optimal solution for (20). In this
subsection, we propose a method to release these constraints and then create
better solutions for (20). The proposed method starts with the following
result. Given the estimated correspondences $\big{\\{}\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)}}\big{\\}}^{M}_{m=1}$ with $M\geq 6$ and $N\geq 5$, let

$\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}=\texttt{CF-
WPfC}\big{(}\\{\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)}}\\}^{M}_{m=1}\big{)}$

and $\big{\\{}\breve{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\breve{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\breve{\bf
x}_{m}^{\text{\tiny(N)}}\big{\\}}^{M}_{m=1}$ be its correspondences, i.e.,

$\qquad\qquad\breve{\bf x}_{m}^{\text{\tiny(n)}}=\left[~{}\frac{{\bf
p}^{\circ}_{1,n}\big{[}{\bf X}^{\circ T}_{m}\,,\,1\big{]}^{T}}{{\bf
p}^{\circ}_{3,n}\big{[}{\bf X}^{\circ
T}_{m}\,,\,1\big{]}^{T}}~{},~{}\frac{{\bf p}^{\circ}_{2,n}\big{[}{\bf
X}^{\circ T}_{m}\,,\,1\big{]}^{T}}{{\bf p}^{\circ}_{3,n}\big{[}{\bf X}^{\circ
T}_{m}\,,\,1\big{]}^{T}}~{}\right]^{T}\qquad\text{for all}\quad m,n\,.$ (31)

On the $n$th image, there are two $M$-groups of points $\\{\hat{\bf
x}_{m}^{\text{\tiny(n)}}\\}^{M}_{m=1}$ and $\\{\breve{\bf
x}_{m}^{\text{\tiny(n)}}\\}^{M}_{m=1}$. A difference between these two groups
is a part corresponding to the index $n$ of the object value of (20) for the
solution $\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$. Thus, we expect that
these $N$ differences are small to ensure that $\\{{\bf X}^{\circ}_{m},{\bf
P}^{\circ}_{n}\\}$ is good. The theory of _absolute orientation_ (Horn, 1987)
allows us to have an optimal _reflection_ or _rotation_ ${\bf
R}^{*}_{n}\in\mathbb{R}^{2\times 2}$ and an optimal _translation_ ${\bf
t}^{*}_{n}\in\mathbb{R}^{2}$ to transfer $\\{\breve{\bf
x}_{m}^{\text{\tiny(n)}}\\}^{M}_{m=1}$ closest to $\\{\hat{\bf
x}_{m}^{\text{\tiny(n)}}\\}^{M}_{m=1}$. Exactly, the result in Horn (1987)
solves the following optimization

$\begin{split}\\{{\bf R}^{*}_{n}\,,\,{\bf
t}^{*}_{n}\\}=&\arg\min\sum^{M}_{m=1}\Big{\|}\big{(}{\bf R}_{n}\breve{\bf
x}_{m}^{\text{\tiny(n)}}+{\bf t}_{n}\big{)}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\Big{\|}_{2}\\\\[2.84526pt] &\text{subject
to}\quad{\bf R}_{n}~{}\text{: a rotation or a reflection},~{}~{}{\bf
t}_{n}~{}\text{: a translation.}\end{split}$ (32)

With the optimal reflection or rotation ${\bf R}^{*}_{n}$ and the optimal
translation ${\bf t}^{*}_{n}$ for the $n$th image, we consider new projection
matrices that

${\bf P}^{*}_{n}=\begin{bmatrix}{\bf R}^{*}_{n}&{\bf t}^{*}_{n}\\\\[2.84526pt]
{\bf 0}_{1\times 2}&1\end{bmatrix}{\bf P}^{\circ}_{n}\qquad\text{for all}\quad
n\,,$ (33)

and get a better solution for (20) by the following proposition.

######  Proposition 4.

According to the optimization (20), $\\{{\bf X}^{\circ}_{m},{\bf
P}^{*}_{n}\\}$ is better than $\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$,
i.e.,

$\sum^{M}_{m=1}\sum^{N}_{n=1}\big{\|}\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}~{}\leq~{}\sum^{M}_{m=1}\sum^{N}_{n=1}\big{\|}\breve{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\,,$
(34)

where $\big{\\{}\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)}}\big{\\}}$ be the correspondences of $\\{{\bf
X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$, i.e.,

$\qquad\qquad\bar{\bf x}_{m}^{\text{\tiny(n)}}=\left[~{}\frac{{\bf
p}^{*}_{1,n}\big{[}{\bf X}^{\circ T}_{m}\,,\,1\big{]}^{T}}{{\bf
p}^{*}_{3,n}\big{[}{\bf X}^{\circ T}_{m}\,,\,1\big{]}^{T}}~{},~{}\frac{{\bf
p}^{*}_{2,n}\big{[}{\bf X}^{\circ T}_{m}\,,\,1\big{]}^{T}}{{\bf
p}^{*}_{3,n}\big{[}{\bf X}^{\circ
T}_{m}\,,\,1\big{]}^{T}}~{}\right]^{T}\qquad\text{for all}\quad m,n\,.$

###### Proof.

The formula of ${\bf P}^{*}_{n}$ given by (33) implies

${\bf P}^{*}_{n}\begin{bmatrix}{\bf X}^{\circ}_{m}\\\\[2.84526pt]
1\end{bmatrix}=\begin{bmatrix}{\bf R}^{*}_{n}&{\bf t}^{*}_{n}\\\\[2.84526pt]
{\bf 0}_{1\times 2}&1\end{bmatrix}{\bf P}^{\circ}_{n}\begin{bmatrix}{\bf
X}^{\circ}_{m}\\\\[2.84526pt] 1\end{bmatrix}\sim\begin{bmatrix}{\bf
R}^{*}_{n}&{\bf t}^{*}_{n}\\\\[2.84526pt] {\bf 0}_{1\times
2}&1\end{bmatrix}\begin{bmatrix}\breve{\bf
x}_{m}^{\text{\tiny(n)}}\\\\[2.84526pt] 1\end{bmatrix}=\begin{bmatrix}{\bf
R}^{*}_{n}\breve{\bf x}_{m}^{\text{\tiny(n)}}+{\bf t}^{*}_{n}\\\\[2.84526pt]
1\end{bmatrix}\,.$

Since $\\{\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)}}\\}$ be the correspondences of $\\{{\bf
X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$, the above equations confirm $\bar{\bf
x}_{m}^{\text{\tiny(n)}}={\bf R}^{*}_{n}\breve{\bf
x}_{n}^{\text{\tiny(n)}}+{\bf t}^{*}_{n}$ for all $m$ and $n$. Thus, for all
$n$

$\sum^{M}_{m=1}\big{\|}\bar{\bf x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\leq\sum^{M}_{m=1}\Big{\|}\big{(}{\bf
I}_{2}\breve{\bf x}_{m}^{\text{\tiny(n)}}+{\bf 0}_{2\times 1}\big{)}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\Big{\|}^{2}_{2}=\sum^{M}_{m=1}\big{\|}\breve{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\,,$
(35)

where ${\bf I}_{2}$ is a $2\times 2$ identity matrix. (35) sufficiently
finishes the proof of Proposition 4. ∎

From the closed-form solution $\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$
given by CF-WPfC algorithm, Proposition 4 proposes the better solution
$\\{{\bf X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$ by using the absolute orientation
theory to change the projection matrices. In the absolute orientation theory,
we are interested in the following fact.

######  Fact 1.

Given a group of $M$ points $\\{{\bf x}_{m}\\}^{M}_{m=1}$ in $\mathbb{R}^{2}$
and its estimation $\\{{\bf x}^{\prime}_{m}\\}^{M}_{m=1}$. Assuming that
$\\{{\bf x}^{\prime\prime}_{m}\\}^{M}_{m=1}$ is a linear transformation from
$\\{{\bf x}_{m}\\}^{M}_{m=1}$ and $\\{{\bf x}^{\prime}_{m}\\}^{M}_{m=1}$, and

$\sum^{M}_{m=1}\big{\|}{\bf x}^{\prime}_{m}-{\bf
x}_{m}\big{\|}^{2}_{2}~{}\leq~{}\sum^{M}_{m=1}\big{\|}{\bf
x}^{\prime\prime}_{m}-{\bf x}_{m}\big{\|}^{2}_{2}$

then

$\sum^{M}_{m=1}\big{\|}\big{(}{\bf R}^{\prime}{\bf x}^{\prime}_{m}+{\bf
t}^{\prime}\big{)}-{\bf
x}_{m}\big{\|}^{2}_{2}~{}\leq~{}\sum^{M}_{m=1}\big{\|}\big{(}{\bf
R}^{\prime\prime}{\bf x}^{\prime\prime}_{m}+{\bf t}^{\prime\prime}\big{)}-{\bf
x}_{m}\big{\|}^{2}_{2}$

where $\\{{\bf R}^{\prime},{\bf t}^{\prime}\\}$ and $\\{{\bf
R}^{\prime\prime},{\bf t}^{\prime\prime}\\}$ are the optimal solutions for
(32) corresponding to $\\{{\bf x}^{\prime}_{m}\\}$ and $\\{{\bf
x}^{\prime\prime}_{m}\\}$, respectively.

Fact 1 is not always correct, however the probability for the correctness of
Fact 1 is close to one. For example, Fact 1 is almost correct with the
correspondences and their estimations in our study. Hence, in our work, we use
this fact to create better solutions. Formally, we find the better solution
$\\{{\bf X}^{**}_{m},{\bf P}^{**}_{n}\\}$ than $\\{{\bf X}^{\circ}_{m},{\bf
P}^{*}_{n}\\}$ by the following process. From the 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)}}\\}$ of $\\{{\bf X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$,
we create a new estimated correspondences $\\{\ddot{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ from the old 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)}}\\}$ by a simple linear transformation that

$\qquad\qquad\qquad\ddot{\bf
x}_{m}^{\text{\tiny(n)}}=\frac{1}{2}\big{(}\bar{\bf
x}_{m}^{\text{\tiny(n)}}+\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{)}\qquad\text{for all}\quad m,n\,.$

Let

$\\{\ddot{\bf X}_{m},\ddot{\bf P}_{n}\\}~{}=~{}\texttt{CF-
WPfC}\big{(}\\{\ddot{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(N)}}\\}\big{)}$ (36)

and $\\{\dot{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\dot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\dot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ be the correspondences of $\\{\ddot{\bf
X}_{m},\ddot{\bf P}_{n}\\}$. Finally, let $\\{\tilde{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ be the optimal correspondences from $\\{\dot{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\dot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\dot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ by using (32). We use the final correspondences
$\\{\tilde{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ to obtain the better solution $\\{{\bf
X}^{**}_{m},{\bf P}^{**}_{n}\\}$ as we want by

$\\{{\bf X}^{**}_{m},{\bf P}^{**}_{n}\\}~{}=~{}\texttt{CF-
WPfC}\big{(}\\{\tilde{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(N)}}\\}\big{)}\,.$ (37)

The better of $\\{{\bf X}^{**}_{m},{\bf P}^{**}_{n}\\}$ than $\\{{\bf
X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$ is proven by the following proposition.

######  Proposition 5.

The solution $\\{\dot{\bf X}_{m},\dot{\bf P}_{n}\\}$ is better than $\\{{\bf
X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$, and then the solution $\\{{\bf
X}^{**}_{m},{\bf P}^{**}_{n}\\}$ is better than $\\{{\bf X}^{\circ}_{n},{\bf
P}^{*}_{n}\\}$ based on the correctness of Fact 1.

###### Proof.

A relationship between two correspondences $\\{\dot{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\dot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\dot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ and $\\{\ddot{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ via the solution $\\{\ddot{\bf X}_{m},\ddot{\bf
P}_{n}\\}$ confirms that $\dot{\bf x}_{m}^{\text{\tiny(n)}}=\ddot{\bf
x}_{m}^{\text{\tiny(n)}}$ for all $n$ and $m=1,2,\ldots,5$. Thus, the
objective value of $\\{\ddot{\bf X}_{m},\ddot{\bf P}_{n}\\}$ is computed based
on its correspondences as follows.

$\begin{split}d\big{(}\\{\ddot{\bf X}_{m},\ddot{\bf
P}_{n}\\}\big{)}&=\sum^{M}_{m=1}\sum^{N}_{n=1}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\\\
&=\sum^{5}_{m=1}\sum^{N}_{n=1}\big{\|}\ddot{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}+\sum^{M}_{m=6}\sum^{N}_{n=1}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\\\
&\leq\sum^{5}_{m=1}\sum^{N}_{n=1}\Big{\|}\frac{1}{2}(\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}})\Big{\|}^{2}_{2}+\sum^{M}_{m=6}\sum^{N}_{n=1}2\Big{(}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\ddot{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}+\big{\|}\ddot{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\Big{)}\\\
&=\frac{1}{4}\sum^{5}_{m=1}\sum^{N}_{n=1}\big{\|}\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}+\frac{1}{2}\sum^{M}_{m=6}\sum^{N}_{n=1}\big{\|}\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}+2\sum^{M}_{m=6}\sum^{N}_{n=1}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\ddot{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\\\
&=\frac{1}{2}d\big{(}\\{{\bf X}^{\circ}_{m},{\bf
P}^{*}_{n}\\}\big{)}-\frac{1}{4}\sum^{5}_{m=1}\sum^{N}_{n=1}\big{\|}\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}+2\sum^{M}_{m=6}\sum^{N}_{n=1}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\ddot{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\\\
&\leq\frac{1}{2}d\big{(}\\{{\bf X}^{\circ}_{m},{\bf
P}^{*}_{n}\\}\big{)}+2\sum^{M}_{m=6}\sum^{N}_{n=1}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\ddot{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\end{split}$ (38)

On the other hand, since the projection matrices ${\bf P}^{\circ}_{n}$ and
${\bf P}^{*}_{n}$ have the same third rows, the correspondences of the
solution $\\{{\bf X}^{\circ}_{m},\frac{1}{2}({\bf P}^{\circ}_{n}+{\bf
P}^{*}_{n})\\}$ will be

$\bigg{\\{}\frac{1}{2}\big{(}\breve{\bf x}_{m}^{\text{\tiny(1)}}+\bar{\bf
x}_{m}^{\text{\tiny(1)}}\big{)}~{}\leftrightarrow~{}\frac{1}{2}\big{(}\breve{\bf
x}_{m}^{\text{\tiny(2)}}+\bar{\bf
x}_{m}^{\text{\tiny(2)}}\big{)}~{}\leftrightarrow~{}\cdots~{}\leftrightarrow~{}\frac{1}{2}\big{(}\breve{\bf
x}_{m}^{\text{\tiny(N)}}+\bar{\bf
x}_{m}^{\text{\tiny(N)}}\big{)}\bigg{\\}}^{M}_{m=1\,.}$

In addition, $\\{{\bf X}^{\circ}_{m},\frac{1}{2}({\bf P}^{\circ}_{n}+{\bf
P}^{*}_{n})\\}$ satisfies the constraints of (30) w.r.t. $\\{\ddot{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ because

$\qquad\quad\frac{1}{2}\big{(}{\bf P}^{\circ}_{n}+{\bf
P}^{*}_{n}\big{)}\begin{bmatrix}{\bf X}^{\circ}_{m}\\\\[2.84526pt]
1\end{bmatrix}\sim\frac{1}{2}\big{(}\breve{\bf
x}_{m}^{\text{\tiny(n)}}+\bar{\bf
x}_{m}^{\text{\tiny(n)}}\big{)}=\frac{1}{2}\big{(}\hat{\bf
x}_{m}^{\text{\tiny(n)}}+\bar{\bf x}_{m}^{\text{\tiny(n)}}\big{)}=\ddot{\bf
x}_{m}^{\text{\tiny(n)}}\qquad\text{for all}\quad n\quad\text{and}\quad
m=1,2\ldots,5\,.$

Indeed, although $\\{\ddot{\bf X}_{m},\ddot{\bf P}_{n}\\}$ is not the global
optimal solution for (30) w.r.t. $\\{\ddot{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$, we still expect that it is better than $\\{{\bf
X}^{\circ}_{m},\frac{1}{2}({\bf P}^{\circ}_{n}+{\bf P}^{*}_{n})\\}$ for this
optimization. It means that

$\begin{split}\sum^{M}_{m=6}\sum^{N}_{n=1}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\ddot{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}&~{}\leq~{}\sum^{M}_{m=6}\sum^{N}_{n=1}\Big{\|}\frac{1}{2}\big{(}\bar{\bf
x}_{m}^{\text{\tiny(n)}}+\breve{\bf x}_{m}^{\text{\tiny(n)}}\big{)}-\ddot{\bf
x}_{m}^{\text{\tiny(n)}}\Big{\|}^{2}_{2}\\\
&~{}=~{}\sum^{M}_{m=6}\sum^{N}_{n=1}\Big{\|}\frac{1}{2}\big{(}\bar{\bf
x}_{m}^{\text{\tiny(n)}}+\breve{\bf
x}_{m}^{\text{\tiny(n)}}\big{)}-\frac{1}{2}\big{(}\bar{\bf
x}_{m}^{\text{\tiny(n)}}+\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{)}\Big{\|}^{2}_{2}\\\
&~{}=~{}\frac{1}{4}d\big{(}\\{{\bf X}^{\circ}_{m},{\bf
P}^{\circ}_{n}\\}\big{)}\,.\end{split}$ (39)

Algorithm 2 Iterative solutions for WPfC (WPfC)

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.

Conditions: $M\geq 6$ and $N\geq 5$.

Implementation:

1. $\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}~{}\overset{\text{CF-WPfC alg.}}{\longleftarrow}~{}\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{\\}}$ .

2. $\text{Eval}~{}~{}\overset{\eqref{eq:Opt_WPfC}}{\longleftarrow}~{}~{}d\big{(}\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}\big{)}$: an objective value,

$\\{{\bf X}^{\star}_{m},{\bf
P}^{\star}_{n}\\}~{}~{}\longleftarrow~{}~{}\\{{\bf X}^{\circ}_{m},{\bf
P}^{\circ}_{n}\\}$ .

3. Repeat several times the following steps:

a. $\\{\breve{\bf x}_{m}^{\text{\tiny(1)}}\leftrightarrow\breve{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\breve{\bf
x}_{m}^{\text{\tiny(N)}}\\}~{}~{}\overset{\eqref{eq:Corresponences_Est}}{\longleftarrow}~{}~{}\\{{\bf
X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$ ,

b. for each $n$, $\\{\bar{\bf
x}_{m}^{\text{\tiny(n)}}\\}^{M}_{m=1}~{}~{}\overset{\text{Absolute
orientation}}{\longleftarrow}~{}~{}\\{\breve{\bf
x}_{m}^{\text{\tiny(n)}}\\}^{M}_{m=1}$ ,

c. create a new correspondences $\\{\ddot{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\ddot{\bf
x}_{m}^{\text{\tiny(N)}}\\}$ : $\ddot{\bf
x}_{m}^{\text{\tiny(n)}}=\frac{1}{2}\big{(}\bar{\bf
x}_{m}^{\text{\tiny(n)}}+\hat{\bf x}_{m}^{\text{\tiny(n)}}\big{)}$ ,

d. $\\{{\bf X}^{*}_{m},{\bf P}^{*}_{n}\\}~{}\overset{\text{CF-WPfC
alg.}}{\longleftarrow}~{}\big{\\{}\ddot{\bf
x}^{\text{\tiny(1)}}_{m}\,\leftrightarrow\,\ddot{\bf
x}^{\text{\tiny(2)}}_{m}\,\leftrightarrow\,\cdots\,\leftrightarrow\,\ddot{\bf
x}^{\text{\tiny(N)}}_{m}\big{\\}}$ ,

e. if $d\big{(}\\{{\bf X}^{*}_{m},{\bf P}^{*}_{n}\\}\big{)}<\text{Eval}$:
$\\{{\bf X}^{\star}_{m},{\bf
P}^{\star}_{n}\\}~{}~{}\longleftarrow~{}~{}\\{{\bf X}^{*}_{m},{\bf
P}^{*}_{n}\\}$

$\text{Eval}~{}~{}\overset{\eqref{eq:Opt_WPfC}}{\longleftarrow}~{}~{}d\big{(}\\{{\bf
X}^{*}_{m},{\bf P}^{*}_{n}\\}\big{)}$ ,

f. $\\{{\bf X}^{\circ}_{m},{\bf
P}^{\circ}_{n}\\}~{}~{}\longleftarrow~{}~{}\\{{\bf X}^{*}_{m},{\bf
P}^{*}_{n}\\}$ .

Output: $\big{\\{}{\bf X}^{\star}_{m},{\bf P}^{\star}_{n}\big{\\}}$ .

Because of $d\big{(}\\{{\bf X}^{\circ}_{m},{\bf P}^{*}_{n}\\}\big{)}\leq
d\big{(}\\{{\bf X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}\big{)}$, (38) and (39)
yield

$d\big{(}\\{\ddot{\bf X}_{m},\ddot{\bf
P}_{n}\\}\big{)}~{}\leq~{}\frac{1}{2}d\big{(}\\{{\bf X}^{\circ}_{m},{\bf
P}^{*}_{n}\\}\big{)}+\frac{1}{2}d\big{(}\\{{\bf X}^{\circ}_{m},{\bf
P}^{\circ}_{n}\\}\big{)}~{}\leq~{}d\big{(}\\{{\bf X}^{\circ}_{m},{\bf
P}^{\circ}_{n}\\}\big{)}\,.$

Therefore $\\{\ddot{\bf X}_{m},\ddot{\bf P}_{n}\\}$ is better than $\\{{\bf
X}^{\circ}_{m},{\bf P}^{\circ}_{n}\\}$, i.e.,

$\sum^{M}_{m=1}\sum^{N}_{n=1}\big{\|}\dot{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}~{}\leq~{}\sum^{M}_{m=1}\sum^{N}_{n=1}\big{\|}\breve{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\,.$
(40)

Fact 1 and (40) imply

$\sum^{M}_{m=1}\sum^{N}_{n=1}\big{\|}\tilde{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf
x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}~{}\leq~{}\sum^{M}_{m=1}\sum^{N}_{n=1}\big{\|}\bar{\bf
x}_{m}^{\text{\tiny(n)}}-\hat{\bf x}_{m}^{\text{\tiny(n)}}\big{\|}^{2}_{2}\,.$
(41)

Finally, since

$\\{{\bf X}^{**}_{m},{\bf P}^{**}_{n}\\}=\texttt{CF-WPfC}(\\{\tilde{\bf
x}_{m}^{\text{\tiny(1)}}\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow\tilde{\bf
x}_{m}^{\text{\tiny(N)}}\\})$ $\\{{\bf X}^{\circ}_{m},{\bf
P}^{*}_{n}\\}=\texttt{CF-WPfC}(\\{\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)}}\\})\,$

(41) confirms that $\\{{\bf X}^{**}_{m},{\bf P}^{**}_{n}\\}$ is better than
$\\{{\bf X}^{\circ}_{m},{\bf P}^{*}_{n}\\}$. Proposition 5 is proven. ∎

The results given by Propositions 4 and 5 allow us to build an iterative
process to find good solutions from the closed-form solution given by
Algorithm 1. This iterative process is called the _Iterative solutions for
WPfC_ and presented by Algorithm 2. In this work, the output

$\\{{\bf X}^{\star}_{m},{\bf
P}^{\star}_{n}\\}~{}=~{}\texttt{WPfC}\big{(}\\{\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)}}\\}^{M}_{m=1}\big{)}$

of Algorithm 2 is considered the final solution for the world points from
correspondences (WPfC). Since the correctness of Fact 1 is not always
guaranteed, convergence of our proposed iterative process can be not occurred.
We overcome this drawback by simply choosing the optimal solution if its
objective value is the smallest at each time in step 3, and fix the number of
times in step 3 by 20.

##  3 Creating Point clouds

Figure 2: World points and camera positions from a 3D-reconstruction of the
_front body_ of Buddha statue. This experiment has 116 images and 27 key-
points. The results are estimated by Algorithm 2 in which the _red circles_
are the estimated world points, the _green circles_ are the estimated camera
positions. The _small blue circles_ are the other estimated world points from
other experiments. They are added in the figure to simulate the 3D-shape of
the Buddha statue. The Buddha statue is horizontal. Some examples of the
correspondences can be found from the key-points on the twenty five images in
the figure.

We begin this section by summarizing our results that we had in the previous
section. The results are simply explained by Figure 2 that presents results
from our project on 3D reconstructing _front body of the Buddha statue_. Given
116 images, we determine 27 key-points and then correspondences. In our work,
we use SURF (Bay et al., 2006) and SIFT (Lowe, 1999) to detect the key-points
on each images, and then create the correspondences. The estimated
correspondences are refined by Le and Li (2022) before using as the input of
both Algorithms 1 and 2. The output of the Algorithm 2 are the 27 world points
indicated by the _red circles_ and the 116 camera positions indicated by the
_green circles_. Of course, from these 27 world points, we cannot recognize
the Buddha statue. We need more points to get the 3D-shape of the statue, then
construct its surface to complete its 3D-reconstruction.

This section studies how to create new points from the images, the world
points and the camera positions derived by the previous section. These new
points are called _point clouds_. Before going further on the study of
creating point clouds, we discuss some important tasks. First, points clouds
should be almost everywhere on the object’s surface. Second, points in point
clouds will be evaluated with a metric. From there we know what is good and
what is bad. Finally, a creating point clouds process should be simple, so we
can recover bad points or missing surfaces by adding new images.

Discussing on the first task, we shall see a disadvantage of existence methods
on 3D-reconstruction. In general, the existence methods build point clouds
based on features they detect on images (Munkres, 1957; Lowe, 1999;
Mikolajczyk and Schmid, 2005; Bay et al., 2006; Myronenko and Song, 2010).
Therefore, surfaces with weak or translucent features cannot be reconstructed.
Of course, to overcome this disadvantage, we can change properties of features
for successful point detection on these surfaces. In the viewpoint of this
approach, features detection will depend on applications.

In this section, we propose a new approach to feature detection. A proposed
feature of a point does not depend on neighbors of this point as the existence
methods do. This feature is defined based on geometrical properties of this
point to some given points. We name this feature by a _geodesic feature_ or
shortly by a _geo-feature_. Given two world points on the object’s surface, a
geodesic between these two points is defined as the shortest curve on the
object’s surface connecting two points (Busemann, 2012). Then an unknown world
point has a ‘ _geo-feature_ ’ if there exist two know world points that this
unknown world point lays on their geodesic. We shall introduce and study
carefully the geo-feature in Subsection 3.2 after we list some needed
notations for its introduction.

###  3.1 Notations

Given $K$ world points $\\{{\bf X}_{1},{\bf X}_{2},\ldots,{\bf X}_{K}\\}$, $N$
projection matrices $\\{{\bf P}^{\star}_{1},{\bf P}^{\star}_{2},\ldots,{\bf
P}^{\star}_{N}\\}$ and their correspondences $\\{{\bf
x}_{k}^{\text{\tiny(1)}}\leftrightarrow{\bf
x}_{k}^{\text{\tiny(2)}}\leftrightarrow\cdots\leftrightarrow{\bf
x}_{k}^{\text{\tiny(N)}}\\}^{K}_{k=1}$ as we can acquire from Section 2. We
use the symbol $\star$ for the projection matrices because all the projection
matrices used in this section are from Algorithm 2 in Section 2, and use $K$
to replace $M$, the number of world points, because the number of world points
will be increased in the process of creating point clouds $(K\gg M)$. Let us
denote ${\bf Img}_{n}$ be a _gray-scale image_ from the $n$th camera. It is an
$H\times W$ matrix and its elements are real values from zero to one. ${\bf
Img}_{n}(h,w)$ or ${\bf Img}_{n}({\bf x}_{k}^{\text{\tiny(n)}})$ is the value
of ${\bf Img}_{n}$ at the $(h,w)$-th pixel or the image point ${\bf
x}_{k}^{\text{\tiny(n)}}$. Note that the image point ${\bf
x}_{k}^{\text{\tiny(n)}}$ would be in the rectangle $[0,H]\times[0,W]$.
Otherwise, we think that this image point does not exist. In addition, for
convenience we accept the image point ${\bf x}_{k}^{\text{\tiny(n)}}$ as a
real vector, not must be integer vector. When two coordinates of ${\bf
x}_{k}^{\text{\tiny(n)}}$ are not integers, they are replaced by their closest
integers to determine the value of ${\bf Img}_{n}({\bf
x}_{k}^{\text{\tiny(n)}})$.

From any two world points ${\bf X}_{k}$, ${\bf X}_{k^{\prime}}$ on the 3D
object’s surface, we denote $\mathcal{G}({\bf X}_{k},{\bf X}_{k^{\prime}})$ be
a _geodesic_ between ${\bf X}_{k}$ and ${\bf X}_{k^{\prime}}$, the shortest
curve on the 3D object’s surface connecting ${\bf X}_{k}$ and ${\bf
X}_{k^{\prime}}$. A motivation of this section is a study on how to
reconstruct this geodesic. Given an image ${\bf Img}_{n}$ capturing both ${\bf
X}_{k}$ and ${\bf X}_{k^{\prime}}$, we define

${\bf Img}_{n}({\bf X}_{k},{\bf X}_{k^{\prime}}|L)~{}=~{}\begin{bmatrix}{\bf
Img}_{n}({\bf x}_{k}^{\text{\tiny(n)}})\\\\[2.84526pt] {\bf
Img}_{n}\Big{(}\frac{1}{L-1}\left[(L-2){\bf x}_{k}^{\text{\tiny(n)}}+{\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}\right]\Big{)}\\\\[7.11317pt] {\bf
Img}_{n}\Big{(}\frac{1}{L-1}\left[(L-3){\bf x}_{k}^{\text{\tiny(n)}}+2{\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}\right]\Big{)}\\\ \vdots\\\\[1.42262pt] {\bf
Img}_{n}\Big{(}\frac{1}{L-1}\left[{\bf x}_{k}^{\text{\tiny(n)}}+(L-2){\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}\right]\Big{)}\\\\[7.11317pt] {\bf
Img}_{n}({\bf x}_{k^{\prime}}^{\text{\tiny(n)}})\end{bmatrix}_{L\times 1}$
(42)

then normalize this vector, i.e., $\|{\bf Img}_{n}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)\|_{2}=1$. This is the column vector of length $L$ that
contains all image points on a straight line between the image points ${\bf
x}_{k}^{\text{\tiny(n)}}$ of ${\bf X}_{k}$ and ${\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}$ of ${\bf X}_{k^{\prime}}$ on the image
${\bf Img}_{n}$. When $L=\|{\bf x}_{k}^{\text{\tiny(n)}}-{\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}\|_{\infty}$, a $\mathcal{L}_{\infty}$-norm
or maximum norm of the vector ${\bf x}_{k}^{\text{\tiny(n)}}-{\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}$, each value at a pixel in the straight line
between ${\bf x}_{k}^{\text{\tiny(n)}}$ and ${\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}$ will correspond to one element in the
vector ${\bf Img}_{n}({\bf X}_{k},{\bf X}_{k^{\prime}}|L)$, and when $L$ is
double, each value at one pixel will correspond to two elements in the vector.
We call this vector the _image curve_ between ${\bf X}_{k}$ and ${\bf
X}_{k^{\prime}}$ on ${\bf Img}_{n}$ and expect that this image curve is close
to the image of the geodesic $\mathcal{G}({\bf X}_{k},{\bf X}_{k^{\prime}})$.
Hence, from a lot of these image curves, we can obtain some information of the
geodesic and reconstruct some points on it.

Next we introduce a concept of _similar_ for a group of images with respect to
(w.r.t.) two world points.

######  Definition 1.

Given a threshold $\theta\in(0,1)$ and two world points ${\bf X}_{k},{\bf
X}_{k^{\prime}}$, a group of $J$ images $\\{{\bf Img}_{n_{1}}$, ${\bf
Img}_{n_{2}}$,$\ldots,{\bf Img}_{n_{J}}\\}$ is called similar w.r.t. ${\bf
X}_{k},{\bf X}_{k^{\prime}}$ and $\theta$ if

$\big{\|}{\bf\Psi}^{T}{\bf\Psi}~{}-~{}{\bf 1}_{J\times
J}\big{\|}_{\infty}~{}\leq~{}\theta\,,$ (43)

where

${\bf\Psi}~{}=~{}\begin{bmatrix}{\bf Img}_{n_{1}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)^{T}\\\\[2.84526pt] {\bf Img}_{n_{2}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)^{T}\\\ \vdots\\\ {\bf Img}_{n_{J}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)^{T}\end{bmatrix}^{T}_{L\times J}$ (44)

and

$L~{}=~{}\max\Big{\\{}\big{\|}{\bf x}_{k}^{\text{\tiny$(n_{1})$}}-{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{1})$}}\big{\|}_{\infty}~{},~{}\big{\|}{\bf
x}_{k}^{\text{\tiny$(n_{2})$}}-{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{2})$}}\big{\|}_{\infty}~{},\,\ldots\,,~{}\big{\|}{\bf
x}_{k}^{\text{\tiny$(n_{J})$}}-{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{J})$}}\big{\|}_{\infty}\Big{\\}}\,.$ (45)

Since all columns ${\bf Img}_{n_{j}}({\bf X}_{k},{\bf X}_{k^{\prime}}|L)$ of
${\bf\Psi}$ are normalized, the $(i,j)$-th element of ${\bf\Psi}^{T}{\bf\Psi}$
is a Pearson correlation of two vectors ${\bf Img}_{n_{i}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)$ and ${\bf Img}_{n_{j}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)$. Thus, if the group $\\{{\bf Img}_{n_{1}},{\bf
Img}_{n_{2}},\ldots,{\bf Img}_{n_{J}}\\}$ is similar w.r.t. $\\{{\bf
X}_{k},{\bf X}_{k^{\prime}},\theta\\}$, then any two image curves of ${\bf
X}_{k}$ and ${\bf X}_{k^{\prime}}$ on two images $n_{i}$ and $n_{j}$ has a
Pearson correlation at least $1-\theta$. Hence, when $\theta\simeq 0$, these
curves are linearly dependent. This rare situation results two cases that (i)
all these $J$ images capture two world points ${\bf X}_{k}$ and ${\bf
X}_{k^{\prime}}$ in the same direction, or (ii) the geodesic $\mathcal{G}({\bf
X}_{k},{\bf X}_{k^{\prime}})$ is a straight line. We easily check the first
case by comparing the camera positions and ${\bf X}_{k},{\bf X}_{k^{\prime}}$.
If it is not the first but the second case, it is useful for 3D reconstruction
because all points in the straight line $\mathcal{G}({\bf X}_{k},{\bf
X}_{k^{\prime}})$ can be reconstructed by these $J$ images. In practice,
because of (i) non-straight line of the geodesic $\mathcal{G}({\bf X}_{k},{\bf
X}_{k^{\prime}})$, (ii) distortions in images and others, it is difficult to
catch this situation with $\theta\simeq 0$. However, what is happen when the
group $\\{{\bf Img}_{n_{1}},{\bf Img}_{n_{2}},\ldots,{\bf Img}_{n_{J}}\\}$ is
similar w.r.t. $\\{{\bf X}_{k},{\bf X}_{k^{\prime}},\theta\\}$ with
$\theta\simeq 0.3$? We expect that although this situation will not help us to
reconstruct all points, it will help us to reconstruct some special points in
$\mathcal{G}({\bf X}_{k},{\bf X}_{k^{\prime}})$.

Finally, we finish this subsection by introducing a metric for points in point
clouds. Assuming that $\\{{\bf x}^{\text{\tiny$(n_{1})$}}\leftrightarrow{\bf
x}^{\text{\tiny$(n_{2})$}}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny$(n_{J})$}}\\}$ is a correspondence found on the $J$-group
$\\{{\bf Img}_{n_{1}},{\bf Img}_{n_{2}},\ldots,{\bf Img}_{n_{J}}\\}$ based on
the geo-feature as we study in Subsection 3.2. From the given projection
matrices $\\{{\bf P}^{\star}_{n_{1}},{\bf P}^{\star}_{n_{2}},\ldots,{\bf
P}^{\star}_{n_{J}}\\}$, we compute the $2J\times 4$ matrix
$\mathcal{H}(\\{{\bf P}^{\star}_{n_{j}}\\})$ and determine a world point ${\bf
X}$ as (3). The correct correspondence $\\{\bar{\bf
x}^{\text{\tiny$(n_{1})$}}\leftrightarrow\bar{\bf
x}^{\text{\tiny$(n_{2})$}}\leftrightarrow\cdots\leftrightarrow\bar{\bf
x}^{\text{\tiny$(n_{J})$}}\\}$ for the new world point is given by

$\qquad\qquad\bar{\bf x}^{\text{\tiny$(n_{j})$}}~{}=~{}\left[\frac{{\bf
p}^{\star}_{1,n_{j}}\big{[}{\bf X}^{T}\,,\,1\big{]}^{T}}{{\bf
p}^{\star}_{3,n_{j}}\big{[}{\bf X}^{T}\,,\,1\big{]}^{T}}~{},~{}\frac{{\bf
p}^{\star}_{2,n_{j}}\big{[}{\bf X}^{T}\,,\,1\big{]}^{T}}{{\bf
p}^{\star}_{3,n_{j}}\big{[}{\bf
X}^{T}\,,\,1\big{]}^{T}}\right]^{T}\qquad\text{for}\quad j=1,2\ldots,J\,.$
(46)

Thus, we use the _mean differences_ between these two correspondences to
evaluate the new point ${\bf X}$. Concretely, we denote this metric by
$\mathcal{E}_{\text{d}}$, and the metric of ${\bf X}$ is defined by

$\mathcal{E}_{\text{d}}({\bf X})~{}=~{}\frac{1}{J}\sum^{J}_{j=1}\big{\|}{\bf
x}^{\text{\tiny$(n_{j})$}}-\bar{\bf x}^{\text{\tiny$(n_{j})$}}\big{\|}_{2\,.}$
(47)

Beside the metric $\mathcal{E}_{\text{d}}$, we evaluate the estimation of the
world point ${\bf X}$ based on the number of images using for this estimation.
We denote this metric by $\mathcal{E}_{\text{i}}$ and
$\mathcal{E}_{\text{i}}({\bf X})$ will be $J$. Therefore, the new point ${\bf
X}$ is good if $\mathcal{E}_{\text{d}}({\bf X})$ is low and
$\mathcal{E}_{\text{i}}({\bf X})$ is high.

###  3.2 Geodesic feature

Assuming that the group of $J$ images $\\{{\bf Img}_{n_{1}},{\bf
Img}_{n_{2}},\ldots,{\bf Img}_{n_{J}}\\}$ is similar w.r.t. two world points
${\bf X}_{k},{\bf X}_{k^{\prime}}$ and a threshold $\theta$. Given a length
$\ell<L$ where $L$ is given by (45), we are interested with the following
optimization

$\arg\min_{1\leq l_{1},l_{2},\ldots,l_{J}\leq
L-\ell}\Big{\|}{\bf\Psi}^{T}_{l_{1}l_{2}\ldots
l_{J}}{\bf\Psi}_{l_{1}l_{2}\ldots l_{J}}~{}-~{}{\bf 1}_{J\times
J}\Big{\|}_{\infty}$ (48)

where ${\bf\Psi}_{l_{1}l_{2}\ldots l_{J}}$ is a $\ell\times J$ matrix that its
$j$-th column is a sub-column beginning at $l_{j}$ and ending at
$l_{j}+\ell-1$ of the $j$-th column of ${\bf\Psi}$, i.e.,

$\big{[}{\bf\Psi}_{l_{1}l_{2}\ldots
l_{J}}\big{]}_{j}~{}=~{}\big{[}{\bf\Psi}(l_{j},j)\,,\,{\bf\Psi}(l_{j}+1,j)\,,\,{\bf\Psi}(l_{j}+2,j)\,,\,\ldots\,,\,{\bf\Psi}(l_{j}+\ell-1,j)\big{]}^{T}$
(49)

with $\big{[}{\bf\Psi}_{l_{1}l_{2}\ldots l_{J}}\big{]}_{j}$ means the $j$-th
column of ${\bf\Psi}_{l_{1}l_{2}\ldots l_{J}}$ and ${\bf\Psi}(i,j)$ mean the
$(i,j)$-th element of ${\bf\Psi}$. If
$\\{l^{*}_{1},l^{*}_{2},\ldots,l^{*}_{J}\\}$ is the optimal solution for (48),
it is obvious that

$\qquad\text{Corr}\Big{(}\big{[}{\bf\Psi}_{l^{*}_{1}l^{*}_{2}\ldots
l^{*}_{J}}\big{]}_{i}\,,\,\big{[}{\bf\Psi}_{l^{*}_{1}l^{*}_{2}\ldots
l^{*}_{J}}\big{]}_{j}\Big{)}~{}\gg~{}\text{Corr}\big{(}{\bf\Psi}_{i}\,,\,{\bf\Psi}_{j}\big{)}>1-\theta\,\qquad\text{for
all}\quad i,j\,,$

where ${\bf\Psi}_{j}={\bf Img}_{n_{j}}({\bf X}_{k},{\bf X}_{k^{\prime}}|L)$ be
the $j$-th column of ${\bf\Psi}$. We expect that when $\theta\simeq 0.3$ and
$\ell\simeq L/10$, the correlation between two vectors
$[{\bf\Psi}_{l^{*}_{1}l^{*}_{2}\ldots l^{*}_{J}}]_{i}$ and
$[{\bf\Psi}_{l^{*}_{1}l^{*}_{2}\ldots l^{*}_{J}}]_{j}$ is at least 0.9 for all
$i,j$. Then as our previous discussion, all the sub image curves
$\big{\\{}[{\bf\Psi}_{l^{*}_{1}l^{*}_{2}\ldots
l^{*}_{J}}]_{j}\big{\\}}^{J}_{j=1}$ are close to images of a sub-geodesic of
$\mathcal{G}({\bf X}_{k},{\bf X}_{k^{\prime}})$. In addition, this sub-
geodesic is nearly straight line. Indeed, in theory we can reconstruct all
points in this sub-geodesic. In our work, we only reconstruct the mid-point of
this sub-geodesic based on a correspondence from the mid-points of
$\big{\\{}[{\bf\Psi}_{l^{*}_{1}l^{*}_{2}\ldots
l^{*}_{J}}]_{j}\big{\\}}^{J}_{j=1}$. Concretely, the following definition of
the geo-feature explains how we find a new world point to create the point
clouds.

######  Definition 2.

Given a similar group $\\{{\bf Img}_{n_{1}},{\bf Img}_{n_{2}},\ldots,{\bf
Img}_{n_{J}}\\}$ w.r.t. $\\{{\bf X}_{k},{\bf X}_{k^{\prime}},\theta\\}$, let
$\\{l^{*}_{1},l^{*}_{2},\ldots,l^{*}_{J}\\}$ be the optimal solution for (48)
corresponding to $\ell$. A correspondence $\\{{\bf
x}^{\text{\tiny$(n_{1})$}}\leftrightarrow{\bf
x}^{\text{\tiny$(n_{2})$}}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny$(n_{J})$}}\\}$ where

${\bf
x}^{\text{\tiny$(n_{j})$}}~{}=~{}\frac{L-1-(l^{*}_{j}\,+\,\ell/2)}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+\frac{l^{*}_{j}+\ell/2}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}$ (50)

is called a geodesic feature (geo-feature) w.r.t. ${\bf X}_{k},{\bf
X}_{k^{\prime}},\theta$ and $\ell$.

When the geo-feature $\\{{\bf x}^{\text{\tiny$(n_{1})$}}\leftrightarrow{\bf
x}^{\text{\tiny$(n_{2})$}}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny$(n_{J})$}}\\}$ is found, we use (3), together with the
projection matrix $\\{{\bf P}^{\star}_{n_{j}}\\}$, to create a new world point
${\bf X}$. If the metrics $\mathcal{E}_{d}$ and $\mathcal{E}_{i}$ of the new
point is small and large, respectively, we add this point in the point clouds
and reconstruct other points in the geodesic $\mathcal{G}({\bf X}_{k},{\bf
X}_{k^{\prime}})$ by applying the same process with replacing the couple
$\\{{\bf X}_{k},{\bf X}_{k^{\prime}}\\}$ by $\\{{\bf X}_{k},{\bf X}\\}$ or
$\\{{\bf X},{\bf X}_{k^{\prime}}\\}$.

###  3.3 Algorithm

An initialization of our process on creating the point clouds is a group of
$M$ world points $\\{{\bf X}^{\star}_{1},{\bf X}^{\star}_{2},\ldots,{\bf
X}^{\star}_{M}\\}$ and $N$ projection matrices $\\{{\bf P}^{\star}_{1},{\bf
P}^{\star}_{2},\ldots,{\bf P}^{\star}_{N}\\}$, the output of Algorithm 2. We
choose all a couple of two world points ${\bf X}^{\star}_{k}$ and ${\bf
X}^{\star}_{k^{\prime}}$, and use $N$ images ${\bf Img}_{1},{\bf
Img}_{2},\ldots,{\bf Img}_{N}$, together with two groups of image points
$\\{{\bf x}^{\text{\tiny(n)}}_{k}\\}^{N}_{n=1}$ of ${\bf X}^{\star}_{k}$ and
$\\{{\bf x}^{\text{\tiny(n)}}_{k^{\prime}}\\}$ of ${\bf
X}^{\star}_{k^{\prime}}$ computing based on the projection matrices $\\{{\bf
P}^{\star}_{n}\\}^{N}_{n=1}$, to find as much as possible geo-features w.r.t.
this couple.

Beside a criterion of geo-feature used as a sign of good point for the point
clouds, we can use a small value of $\mathcal{E}_{d}$ and a large value of
$\mathcal{E}_{i}$ of a point to guarantee that this is a good point. For
example, in our project of the Buddha’s statue 3D reconstruction, if a point
has its $\mathcal{E}_{d}$ value at most 25 and its $\mathcal{E}_{i}$ value at
least 20, i.e., this point is estimated by at least 20 images and a mean
difference between image points of this point before and after estimation is
smaller than 25 pixels, would be a good point. Thus, we can create lots of
candidates then use their metrics $\mathcal{E}_{d}$ and $\mathcal{E}_{i}$ to
recognize good candidate to add in the point clouds. Based on this viewpoint,
we shall simplify a process of finding geo-features based on the _similar
groups_ given by Definition 1 and the optimal solutions for (48) by a simple
process of finding _candidates_ that

######  Definition 3.

Given a group of $J$ images $\\{{\bf Img}_{n_{1}}\,,\,{\bf
Img}_{n_{2}},\ldots,{\bf Img}_{n_{J}}\\}$, a correspondence $\\{{\bf
x}^{\text{\tiny$(n_{1})$}}\leftrightarrow{\bf
x}^{\text{\tiny$(n_{2})$}}\leftrightarrow\cdots\leftrightarrow{\bf
x}^{\text{\tiny$(n_{J})$}}\\}$ is called a candidate of a geo-feature w.r.t.
$\\{{\bf X}_{k},{\bf X}_{k^{\prime}},\theta,\ell\\}$ if

  1. 1.

for all $1\leq i\neq j\leq J$, a group of two images $\\{{\bf
Img}_{n_{i}}\,,\,{\bf Img}_{n_{j}}\\}$ is similar w.r.t. $\\{{\bf X}_{k},{\bf
X}_{k^{\prime}},\theta\\}$ ,

  2. 2.

${\bf x}^{\text{\tiny$(n_{j})$}}$ is in the straight line between ${\bf
x}_{k}^{\text{\tiny$(n_{j})$}}$ and ${\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}$, i.e., there exists an integer number
$l_{j}$ between $\ell/2$ to $L-1-\ell/2$ that

${\bf x}^{\text{\tiny$(n_{j})$}}~{}=~{}\frac{L-1-l_{j}}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+\frac{l_{j}}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\,,$

  3. 3.

and for all $1\leq i\neq j\leq J$,

$\text{Corr}\Big{(}\psi\big{(}{\bf
x}^{\text{\tiny$(n_{i})$}}\big{)}\,,\,\psi\big{(}{\bf
x}^{\text{\tiny$(n_{j})$}}\big{)}\Big{)}~{}\geq~{}1-\theta\,,$

where

$\psi\big{(}{\bf x}^{\text{\tiny$(n_{j})$}}\big{)}~{}=~{}\psi\big{(}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}},{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}},l_{j}\big{)}~{}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}\begin{bmatrix}\frac{L-1-(l_{j}-\ell/2)}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+\frac{l_{j}-\ell/2}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\\\\[7.11317pt]
\frac{L-1-(l_{j}-\ell/2+1)}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+\frac{l_{j}-\ell/2+1}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\\\\[2.84526pt] \vdots\\\\[2.84526pt]
\frac{L-1-(l_{j}+\ell/2-1)}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+\frac{l_{j}+\ell/2-1}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\\\\[7.11317pt]
\frac{L-1-(l_{j}+\ell/2)}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+\frac{l_{j}+\ell/2}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\end{bmatrix}_{\ell\times 1}$ (51)

be the $\ell\times 1$ vector in the straight line between ${\bf
x}_{k}^{\text{\tiny$(n_{j})$}}$ and ${\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}$ with ${\bf
x}^{\text{\tiny$(n_{j})$}}$ be a middle.

Although motivating to find candidates for geo-features of $J$ images ($J\gg
2$), Definition 3 allows us to find these candidates by doing independently
with any two images from $J$ images. More precisely, given a couple of two
images ${\bf Img}_{n_{i}}$ and ${\bf Img}_{n_{j}}$, first we check

$\text{Corr}\big{(}{\bf Img}_{n_{i}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)\,,\,{\bf Img}_{n_{j}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)\big{)}~{}\geq~{}1-\theta$

where $L=\max\big{\\{}\|{\bf x}_{k}^{\text{\tiny$(n_{i})$}}-{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{i})$}}\|_{\infty}\,,\,\|{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}-{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\|_{\infty}\big{\\}}$ to confirm that
the group $\\{{\bf Img}_{n_{i}}\,,\,{\bf Img}_{n_{j}}\\}$ is similar w.r.t.
$\\{{\bf X}_{k},{\bf X}_{k^{\prime}},\theta\\}$. Second, we find all
$l_{i},l_{j}\in\\{0,1,\ldots,L-1\\}$ such that the third condition of
Definition 3 occurs. Then we store the image points

$\begin{split}{\bf x}^{\text{\tiny$(n_{i})$}}~{}&=~{}\frac{L-1-l_{i}}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{i})$}}+\frac{l_{i}}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{i})$}}\qquad\text{to}\qquad\mathcal{I}_{n_{i}}\,,\\\\[5.69054pt]
{\bf x}^{\text{\tiny$(n_{j})$}}~{}&=~{}\frac{L-1-l_{j}}{L-1}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+\frac{l_{j}}{L-1}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\qquad\text{to}\qquad\mathcal{I}_{n_{j}}\,,\end{split}$

where $\mathcal{I}_{n_{i}},\,\mathcal{I}_{n_{j}}$ be sets of all candidates
for the geo-feature w.r.t. $\\{{\bf X}_{k},{\bf
X}_{k^{\prime}},\theta,\ell\\}$ on the images $n_{i}$ and $n_{j}$,
respectively, and remember that ${\bf x}^{\text{\tiny$(n_{i})$}}$ in
$\mathcal{I}_{n_{i}}$ matches to ${\bf x}^{\text{\tiny$(n_{j})$}}$ in
$\mathcal{I}_{n_{j}}$. Here we have a notice that if (i) ${\bf
x}_{1}^{\text{\tiny$(n_{j})$}}\in{\bf Img}_{n_{j}}$ matches to ${\bf
x}^{\text{\tiny$(n_{i})$}}\in{\bf Img}_{n_{i}}$, (ii) another ${\bf
x}_{2}^{\text{\tiny$(n_{j})$}}\in{\bf Img}_{n_{j}}$ matches to ${\bf
x}^{\text{\tiny$(n_{i^{\prime}})$}}\in{\bf Img}_{n_{i^{\prime}}}$, and (iii)
${\bf x}_{1}^{\text{\tiny$(n_{j})$}}\neq{\bf x}_{2}^{\text{\tiny$(n_{j})$}}$
but they are very close then we must conclude ${\bf
x}_{1}^{\text{\tiny$(n_{j})$}}$ matches to ${\bf
x}^{\text{\tiny$(n_{i^{\prime}})$}}$ and ${\bf x}_{2}^{\text{\tiny$(n_{j})$}}$
matches to ${\bf x}^{\text{\tiny$(n_{i})$}}$. In addition, we should replace
two points ${\bf x}_{1}^{\text{\tiny$(n_{j})$}}$ and ${\bf
x}_{2}^{\text{\tiny$(n_{j})$}}$ by a new point $\bar{\bf
x}^{\text{\tiny$(n_{j})$}}$ and remember that the new point $\bar{\bf
x}^{\text{\tiny$(n_{j})$}}$ matches to both ${\bf x}^{\text{\tiny$(n_{i})$}}$
on the image $n_{i}$ and ${\bf x}^{\text{\tiny$(n_{i^{\prime}})$}}$ on the
image $n_{i^{\prime}}$. To solve this problem, we shall cluster the set
$\mathcal{I}_{n_{j}}$ to group image points that are close together into a
group. Note that all image points in $\mathcal{I}_{n_{j}}$ are in a straight
line between ${\bf x}_{k}^{\text{\tiny$(n_{j})$}}$ and ${\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}$. Thus, we shall use the _Jenks
natural breaks optimization_ (Jenks, 1967) to cluster all image points in
$\mathcal{I}_{n_{j}}$. We have a mention that in one-dimensional clustering,
the Jenks natural breaks optimization seems to be _$k$ -means clustering_
(Hartigan and Wong, 1979).

Algorithm 3 Creating Point Clouds from two given world points (CrPC)

Input: $\big{\\{}{\bf P}^{\star}_{1},{\bf P}^{\star}_{2},\ldots,{\bf
P}^{\star}_{N}\big{\\}}$ : Projection matrices,

${\bf X}_{k}$ and ${\bf X}_{k^{\prime}}$ : Two given world points,

$\theta$ and $\ell$ : Thresholds for candidates detection.

Implementation:

1. $\mathcal{PC}~{}\longleftarrow~{}\emptyset$ : a point clouds set collecting all reconstructed points,

$\\{{\bf x}_{k}^{\text{\tiny(n)}}\\}^{N}_{n=1}\overset{\text{Image
points}~{}\eqref{eq:Image_point}}{\longleftarrow}\big{\\{}{\bf
X}_{k}\,;\,\\{{\bf P}^{\star}_{n}\\}\big{\\}}$ and $\\{{\bf
x}_{k^{\prime}}^{\text{\tiny(n)}}\\}^{N}_{n=1}\overset{\text{Image
points}~{}\eqref{eq:Image_point}}{\longleftarrow}\big{\\{}{\bf
X}_{k^{\prime}}\,;\,\\{{\bf P}^{\star}_{n}\\}\big{\\}}$ ,

$\mathcal{I}_{1}\longleftarrow\emptyset$ ,
$\mathcal{I}_{2}\longleftarrow\emptyset$ , $\ldots$ ,
$\mathcal{I}_{N}\longleftarrow\emptyset$ .

2. For all $1\leq n_{i}\neq n_{j}\leq N$:

2.1. $L\longleftarrow\max\big{\\{}\|{\bf x}_{k}^{\text{\tiny$(n_{i})$}}-{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{i})$}}\|_{\infty}\,,\,\|{\bf
x}_{k}^{\text{\tiny$(n_{j})$}}-{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\|_{\infty}\big{\\}}$ .

2.2. ${\bf Img}_{n_{i}}({\bf X}_{k},{\bf X}_{k^{\prime}}|L)$ and ${\bf
Img}_{n_{j}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)~{}\longleftarrow~{}~{}\eqref{eq:Image_Line}$ .

2.3. If $\text{Corr}\big{(}{\bf Img}_{n_{i}}({\bf X}_{k},{\bf
X}_{k^{\prime}},|L)\,,\,{\bf Img}_{n_{j}}({\bf X}_{k},{\bf
X}_{k^{\prime}}|L)\big{)}~{}>~{}1-\theta$ :

for all $\ell/2\leq l_{i},l_{j}\leq L-1-\ell/2$:

a. $\psi\big{(}{\bf x}_{k}^{\text{\tiny$(n_{i})$}},{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{i})$}},l_{i}\big{)}$ and $\psi\big{(}{\bf
x}_{k}^{\text{\tiny$(n_{j})$}},{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}},l_{j}\big{)}~{}\longleftarrow~{}\eqref{eq:Image_Line_ell}$

b. if $\text{Corr}\big{(}\psi({\bf x}_{k}^{\text{\tiny$(n_{i})$}},{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{i})$}},l_{i})\,,\,\psi({\bf
x}_{k}^{\text{\tiny$(n_{j})$}},{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}},l_{j})\big{)}~{}>~{}1-\theta$ :

i. ${\bf
x}^{\text{\tiny$(n_{i})$}}~{}\longleftarrow~{}\frac{1}{L-1}\big{[}(L-1-l_{i}){\bf
x}_{k}^{\text{\tiny$(n_{i})$}}+l_{i}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{i})$}}\big{]}$ and add ${\bf
x}^{\text{\tiny$(n_{i})$}}$ to $\mathcal{I}_{n_{i}}$

ii. ${\bf
x}^{\text{\tiny$(n_{j})$}}~{}\longleftarrow~{}\frac{1}{L-1}\big{[}(L-1-l_{j}){\bf
x}_{k}^{\text{\tiny$(n_{j})$}}+l_{j}{\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}\big{]}$ and add ${\bf
x}^{\text{\tiny$(n_{j})$}}$ to $\mathcal{I}_{n_{j}}$

iii. Remember that “${\bf x}^{\text{\tiny$(n_{i})$}}$ matches to ${\bf
x}^{\text{\tiny$(n_{j})$}}$”.

3. For each $n\in\\{1,2,\ldots,N\\}$, $\big{\\{}\bar{\bf x}_{1}^{\text{\tiny(n)}},\bar{\bf x}_{2}^{\text{\tiny(n)}},\ldots,\bar{\bf x}_{\kappa_{n}}^{\text{\tiny(n)}}\big{\\}}$ $\overset{\text{~{}Jenks natural breaks optimization~{}}}{\longleftarrow}$ $\mathcal{I}_{n}$ .

4. $\mathcal{C}({\bf X}_{k},{\bf X}_{k^{\prime}},\theta,\ell)~{}\longleftarrow~{}$ (53) and (54).

5. For each candidate $\big{\\{}\bar{\bf x}_{h_{1}}^{\text{\tiny$(n_{1})$}}\leftrightarrow\bar{\bf x}_{h_{2}}^{\text{\tiny$(n_{2})$}}\leftrightarrow\cdots\leftrightarrow\bar{\bf x}_{h_{J}}^{\text{\tiny$(n_{J})$}}\big{\\}}$ in $\mathcal{C}({\bf X}_{k},{\bf X}_{k^{\prime}},\theta,\ell)$

5.1. Use $J$ projection matrices $\\{{\bf P}^{\star}_{n_{1}},{\bf
P}^{\star}_{n_{2}},\ldots,{\bf P}^{\star}_{n_{J}}\\}$ and (3) to create a new
world point ${\bf X}$ ,

5.2. $\mathcal{E}_{d}({\bf X})~{}\longleftarrow~{}~{}\eqref{eq:Image_point}$
and (47) , $\mathcal{E}_{i}({\bf X})=J$ ,

5.3. If $\mathcal{E}_{d}({\bf X})$ and $\mathcal{E}_{i}({\bf X})$ satisfy the
conditions of the point clouds, add ${\bf X}$ to $\mathcal{PC}$.

Output: $\mathcal{PC}$ \- Point clouds.

Assuming that the Jenks natural breaks optimization clusters
$\mathcal{I}_{n_{j}}$ into $\kappa_{j}$ classes $\\{{\bf I}_{1},{\bf
I}_{2},\ldots,{\bf I}_{\kappa_{j}}\\}$, we shall replace all the image points
${\bf x}^{\text{\tiny$(n_{j})$}}$ in ${\bf I}_{h}$ by their mean $\bar{\bf
x}_{h}^{\text{\tiny$(n_{j})$}}$ given by

$\bar{\bf x}_{h}^{\text{\tiny$(n_{j})$}}=\frac{1}{|{\bf I}_{h}|}\sum_{{\bf
x}^{\text{\tiny$(n_{j})$}}\in{\bf I}_{h}}{\bf x}^{\text{\tiny$(n_{j})$}}$ (52)

where $|{\bf I}_{h}|$ is the number of image points in ${\bf I}_{h}$. Then on
the image ${\bf Img}_{n_{j}}$, at the straight line connecting two image
points ${\bf x}_{k}^{\text{\tiny$(n_{j})$}}$ and ${\bf
x}_{k^{\prime}}^{\text{\tiny$(n_{j})$}}$, we only use $\kappa_{j}$ new image
points $\bar{\bf x}^{\text{\tiny$(n_{j})$}}_{1},\bar{\bf
x}^{\text{\tiny$(n_{j})$}}_{2},\ldots,\bar{\bf
x}_{\kappa_{j}}^{\text{\tiny$(n_{j})$}}$ to find candidates for geo-features
as defined by Definition 3. The candidates will be found based on the matches
of elements in $J$ groups $\big{\\{}\bar{\bf
x}^{\text{\tiny$(n_{j})$}}_{1},\bar{\bf
x}^{\text{\tiny$(n_{j})$}}_{2},\ldots,\bar{\bf
x}_{\kappa_{j}}^{\text{\tiny$(n_{j})$}}\big{\\}}^{J}_{j=1}$ corresponding to
$J$ groups of images $\\{{\bf Img}_{n_{1}},{\bf Img}_{n_{2}},\ldots,{\bf
Img}_{n_{J}}\\}$ that

$\begin{cases}{\bf x}^{\text{\tiny$(n_{i})$}}\quad\text{is replaced
by}\quad\bar{\bf x}_{h_{i}}^{\text{\tiny$(n_{i})$}}\\\\[5.69054pt] {\bf
x}^{\text{\tiny$(n_{j})$}}\quad\text{is replaced by}\quad\bar{\bf
x}_{h_{j}}^{\text{\tiny$(n_{j})$}}\\\\[5.69054pt] {\bf
x}^{\text{\tiny$(n_{i})$}}\quad\text{matches to}\hskip 12.80373pt\quad{\bf
x}^{\text{\tiny$(n_{j})$}}\end{cases}\qquad\Rightarrow\qquad\bar{\bf
x}_{h_{i}}^{\text{\tiny$(n_{i})$}}\quad\text{matches to}\quad\bar{\bf
x}_{h_{j}}^{\text{\tiny$(n_{j})$}}\,.$ (53)

Concretely, we consider the following set of correspondences

$\mathcal{C}\big{(}{\bf X}_{k},{\bf
X}_{k^{\prime}},\theta,\ell\big{)}~{}\stackrel{{\scriptstyle\text{def}}}{{=}}~{}\Bigg{\\{}\big{\\{}\bar{\bf
x}_{h_{1}}^{\text{\tiny$(n_{1})$}}\leftrightarrow\bar{\bf
x}_{h_{2}}^{\text{\tiny$(n_{2})$}}\leftrightarrow\cdots\leftrightarrow\bar{\bf
x}_{h_{J}}^{\text{\tiny$(n_{J})$}}\big{\\}}~{}\Bigg{|}~{}\begin{matrix}\bar{\bf
x}_{h_{j}}^{\text{\tiny$(n_{j})$}}\in\big{\\{}\bar{\bf
x}^{\text{\tiny$(n_{j})$}}_{1},\bar{\bf
x}^{\text{\tiny$(n_{j})$}}_{2},\ldots,\bar{\bf
x}_{\kappa_{j}}^{\text{\tiny$(n_{j})$}}\big{\\}}~{}~{}\text{for
all}~{}~{}j\,~{}~{}\\\\[2.84526pt] \bar{\bf
x}_{h_{i}}^{\text{\tiny$(n_{i})$}}\quad\text{matches to}\quad\bar{\bf
x}_{h_{j}}^{\text{\tiny$(n_{j})$}}\hskip 20.62823pt\quad\text{for
all}~{}~{}i,j\,\end{matrix}\Bigg{\\}}$ (54)

as candidates for the geo-features w.r.t. $\\{{\bf X}_{k},{\bf
X}_{k^{\prime}},\theta,\ell\\}$. From these candidates, new points are created
based on the known projection matrices ${\bf P}^{\star}_{n_{1}},{\bf
P}^{\star}_{n_{2}},\ldots,{\bf P}^{\star}_{n_{J}}$ and the formula (3).
Depending on applications, the optimal metric values $\mathcal{E}_{d}$ and
$\mathcal{E}_{i}$ are used to decide whether or not to create these new points
to the point clouds.

Finally, Algorithm 3, named the _creating point clouds_ (CrPC), presents step-