# Multi band Fermi surface in 1T-VSe2 and its implication for charge density
wave phase

Turgut Yilmaz  National Synchrotron Light Source II, Brookhaven National Lab,
Upton, New York 11973, USA<EMAIL_ADDRESS>Boris Sinkovic  Department of
Physics, University of Connecticut, Storrs, Connecticut 06269, USA  Elio
Vescovo  National Synchrotron Light Source II, Brookhaven National Lab, Upton,
New York 11973, USA

(August 29, 2024)

###### Abstract

Here, our angle resolved photoemission spectroscopy experiment reveled that
the surface band structure of the 1T-VSe2 host electronic states that was not
predicted or probed before. Earlier claims to support charge density wave
phase can be all explained in terms of these new findings. Its Fermi surface
found to be not gaped at any point of the Brillouin zone and warping effect on
the electronic structure, attributed to the lattice distortion previously, is
due to the different dispersion of the multiple bands. Based on these new
findings and interpretations, charge density wave induced modification on the
electronic structure of 1T-VSe2 needs to be reconstructed in the future
studies.

††preprint: APS/123-QED

Layered transition metal dichalcogenides (TMDCs) host various electronic,
structural, and transport phenomena making them most promising candidates for
applications in electronic devices [1, 2]. Among the many novel states, the
charge density wave (CDW) phase in these compounds is particularly under
scrutiny as it is neighbor to superconductivity in the phase diagrams [3, 4].
In terms of electronic structure, the CDW phase is usually linked to Fermi
surface nesting with opening of a gap at specific portion of the Fermi surface
connected by the CDW wave vector [5, 6, 7]. In response, atoms move from their
original positions forming a superstructure that can be visualized through a
scanning tunneling electron microscopy (STM) experiment [8, 9, 10].

Of all TMDCs, 1T-VSe2 is a special example due to its long wavelength 3D CDW
phase in the bulk. It undergoes an incommensurate CDW with $4a\times 4a\times
3.18c$ periodic lattice distortion around $T^{*}$ = 110 K, followed by a
second transition to a commensurate CDW state around 80 K [9, 10, 11]. On the
other hand, CDW-phase on the electronic structure is anomalously supported by
angle resolved photoemission spectroscopy (ARPES) studies. Such as, CDW
induced gap has been reported around the $\overline{M}$-point of the Fermi
surface as a shift of a secondary peak while a spectral intensity suppression
at the Fermi level is absent [12, 13, 14, 15]. This appeared to be a well
established way of measuring the CDW induced gap in the bulk 1T-VSe2 samples.
Furthermore, a recent STM study also reported a gap at the Fermi surface which
is found to be more pronounced around the $\Gamma$-point [16]. However, this
observation should not be correlated with the structural transition since the
$\Gamma$-point is not along the CDW wave vector. The results are even more
elusive in the monolayer VSe2 samples. First, fully gaped Fermi surface
claimed to be reported by multiple studies [17, 18, 19]. Such observation is
unlikely to be due to the CDW phase because CDW wave vector clearly has no
influence in that case. Second, monolayer samples seem to have a larger CDW
induced gap ($\sim$100 meV) with a higher T∗. On the other hand, experimental
band structures do not exhibit any signature of back-bending to support such a
large energy gap in contrast to the computational models [17, 18, 19].

Here, we re-evaluate some of the main results reported on 1T-VSe2 by
performing a detailed ARPES experiment and rule out the earlier CDW related
claims point by point. The Fermi surface of 1T-VSe2 contains multiple bands,
not previously detected and they have different in-plane and out-plane
dispersion. Thereby, the previous observations that are attributed to the CDW
phase are due to the lack of resolving these bands. In this regard, the
previous theoretical models and experimental observations cannot be assigned
to the CDW phase and the impact of structural distortion on the electronic
structure requires further characterizations and approaches. But, new
observations provide more detailed electronic structure that can guide future
studies as well as suggesting the revision of the various other studies
regarding electronic properties of 1T-VSe2.

Figure 1:  (a) Orbital projected band structure of the bulk VSe2 in normal
state. Red horizontal line represents the Fermi level. (a-c) Fermi surfaces of
a bulk 1T-VSe2 sample were taken with LH at 10 K, LV at 10, and LV at 160 K,
respectively. (d-f) Corresponding ARPES maps along the $\overline{M}$\-
$\overline{\Gamma}$ \- $\overline{M^{\prime}}$ direction. The asymmetric band
structure observed with LV polarized lights is likely due to the 3-fold
rotational symmetry of the band structure. The orbital character of the bands
is adapted from the literature (g) EDCs taken along the black, blue, and red
arrows shown in (e).

Single crystal 1T-VSe2 were obtained from 2dsemiconductors company. ARPES
experiments were performed at 21-ID-1 (ESM) beamline of NSLS-II using a DA30
Scienta electron spectrometer with an energy resolution better than 12 meV and
the beam spot size was approximately 5 $\mu$m2. The synchrotron radiation
incidence angle was 55o. Analyzer slit was along to the $\overline{M}$ \-
$\overline{\Gamma}$ \- $\overline{M^{\prime}}$ direction during the ARPES
measurements at normal emission and along to the $\overline{M}$ \-
$\overline{M^{\prime}}$-direction during the zone corner scans. LV polarized
light is parallel to the sample surface and analyzer slit while LH polarized
light is on the incident plane. Band structure calculation is performed with
Quantum Espresso package [20, 21]. The photon energy is converted to kz
crystal momentum adopting the free electron final state approximation given as
$\hbar$kz = 2me$\sqrt{E_{kin}\cos(\theta)+V_{o}}$ where me is the free
electron mass, Ekin is the photoelectron kinetic energy, and Vo, inner
potential, set to 7.5 eV [22].

We first investigate computed electronic structure in Figure 1(a) to compare
it with the experimental one. Fermi level is dominated by V 3$d$ atomic
orbitals which forms a V-saped bulk bands at $M(L)$-points while it exhibits
relatively flatter feature near the zone center. Highly dispersive Se 4$p$
atomic orbitals mostly located around the $\Gamma$($A$)-points below the Fermi
level. Furthermore the V 3$d$ atomic orbitals do not exhibit any splitting
near the $\Gamma$($A$) or $M(L)$-points. Particularly, a single band is
crossing the Fermi level in the vicinity of the $M(L)$-point. This band
structure is in excellent agreement with the previous studies [23, 24], but it
underestimates the details as we will discuss latter in this work.

The experimental electronic structure of 1T-VSe2 bulk samples is studied by
using linear horizontal (LH) and linear vertical (LV) polarized lights in
Figure 1(b-e), respectively. In the LH geometry, apparent ellipsoidal electron
pockets centered at $\overline{M}$($\overline{M^{\prime}}$)-points are the
main features of the Fermi surface while highly dispersive Se 4$p$ atomic
orbitals dominate the zone center (Figure 1(b)). The corresponding ARPES map
along the $\overline{M}$-$\overline{\Gamma}$-$\overline{M^{\prime}}$ exhibits
V-3$d$ atomic orbitals with nearly flat dispersion in the vicinity of the
$\overline{\Gamma}$-point where it overlaps with Se 4$p$ atomic orbitals
(Figure 1d). Overall band structure obtained for this particular experimental
geometry is consistent with the computed one as well as the earlier ARPES
reports [14, 22, 17, 17, 24].

On the other hand, the same band structure taken with LV polarized light
reveals differences in details. The zone center exhibits a point like
dispersion enabling to study the band structure around the
$\overline{\Gamma}$-point more precisely. Unlike the single band observed with
LH polarized light, three bands called $\alpha$, $\beta$, and $\gamma$ are now
resolved around the zone center (Figure 1(e)). The first two bands are
crossing the Fermi level at k∥ = -0.37 $\AA$-1 and at k∥ = -0.24 $\AA$-1 while
the third band is located just below the Fermi level displaying a flatter
dispersion towards to $\overline{\Gamma}$-point. These additional states are
not predicted in the band structure calculation reported here or elsewhere
[14, 22, 17, 17, 24, 23, 24]. Implication of the new findings in terms of CDW
induced gap is that if a band is located just below the Fermi level,
temperature induced lifetime broadening can always lead to a determination of
a false gap. This is likely to be the case for a recent STM study that reports
a prominent gap in the vicinity of the $\overline{\Gamma}$-point [16].
Furthermore, these multiple bands are main characteristics of the material and
can be resolved below and above the T∗ showing that they are not due to the
structural distortion(Figure 1(c) and Supplementary Materials Figure S1(a-b)).

By using this new finding, one can reproduce a data appear to host a
temperature dependent gap at the Fermi level. The EDCs crossing the $\alpha$
and $\beta$ bands at the Fermi level and momentum point across the $\gamma$
band are given in Figure 1(f) for two temperatures; 10 K (below T∗ and 160 K
(above T∗). Third one has a natural gap since the band is located below the
Fermi level and the second one clearly shows no evidence of a CDW gap.
However, first one appears to experiencing a shift towards higher binding
energy at a lower temperature (marked with blue and red vertical lines in
Figure 1(f)). Such shift commonly attributed to the a gap opening in this
material [12, 13, 15]. But, spectral intensity at the Fermi level does not
show prominent temperature dependence. This apparent shift is due to the
$\beta$ band being located just below the $\alpha$ band. And, temperature
induced lifetime broadening leads them to overlap more in energy. This appears
in the band structure as if a band is shifting in energy with temperature.
Thereby, lack of the resolving these bands in the earlier studies leads to
misinterpreting the experimental data. Indeed, this should have been realized
since the vicinity of the $\Gamma$-point is not along the CDW-wave vector and
hence is not expected to be gaped.

Furthermore, the modulation of the color contrast on the electronic structure
figures is relied on as a signature of a gap opening at the Fermi level [13,
14]. Here, we repeat a similar experiment. Figure 2(a) presents the Fermi
surface that covers the ellipsoidal electron pocket centered at the
$\overline{M}$-point. Color-contrast is gradually decreasing towards
$\overline{M}$-point as consistent with the earlier studies. In this regard,
one can claim a possible gap opening at the Brillouin zone boundaries. To
check if this is the case, a logical experimental approach will be comparing
the Fermi edges taken from the different portions of the Fermi surface
recorded below T∗. In this way, possible experimental errors induced by
variable temperature can be also avoided. Thus, ARPES maps taken along the
dashed black line in Figure 2(a) and the $\overline{K}$ \- $\overline{M}$ \-
$\overline{K^{\prime}}$ direction are given in Figure 2(b-c), respectively.
Compared to the former one, the latter exhibits lower spectral intensity in
the entire band structure rather than only at the Fermi level. Therefore, the
apparent spectral intensity does not necessarily represent a gap opening.

Figure 2:  (a) The Fermi surface is recorded with 93 eV LH polarized lights.
(b-c) ARPES maps taken along the dashed black line in (a) and $\overline{K}$\-
$\overline{M}$ \- $\overline{K^{\prime}}$, respectively. (d) MDCs were taken
at the Fermi level from (b-c). (e) EDCs taken along the dashed black and
orange lines in (b-c). Vertical black and orange lines in (e) mark the high
intensity points. (f-g) ARPES maps along the $\overline{M}$ \-
$\overline{M^{\prime}}$ direction taken with 101 eV LH and LV polarized
lights, respectively. All data are collected at 10 K.

The MDCs taken at the Fermi level of Figure 2(b-c) are compared in Figure 2(d)
to find out the origin of this spectral intensity modulation. The one along
the $\overline{K}$ \- $\overline{M}$ \- $\overline{K^{\prime}}$ direction
exhibits a broader line shape compared to the other one. Therefore, the lower
intensity around $\overline{M}$ of the Fermi surface is not due to the gap
opening but it is caused by a broader electronic structure in momentum space.
Furthermore, the EDCs taken along the dashed black line in Figure 2(b) and the
dashed orange line in Figure 2(c) are given in Figure 2(e). They exhibit the
same Fermi level indicating the absence of a insulating gap. On the other
hand, the high intensity points show a difference in the EDCs (vertical orange
and black lines in Figure 2(e)). This apparent shift has been considered as
well-established experimental signature of the CDW induced gap in VSe2 [12,
13, 14, 15]. Indeed, these observations indicate existence of multiple bands
located in close proximity to each other rather than a gap opening. Therefore,
the Fermi surface is expected to be dominated at least two bands in contrast
to the previous experiments and computations.

Above argument is experimentally confirmed by analysing the various ARPES maps
parallel to $\overline{K}$ \- $\overline{M}$ \- $\overline{K}^{\prime}$.
Around $\overline{M}$-point a V-shape band is crossing the Fermi level at k| =
$\pm$ 0.32 $\AA$ (Figure 3(b)). However, band splitting towards zone center
can be seen in Figure 3(c-e) as marked with blue arrows. These additional
bands eventually connect with the neighbor electron pockets (Figure 3(f-g)).

Figure 3:  (a) The Fermi surface. (b-g) ARPES cuts along the 1-5 marked lines
shown in (a), respectively. Spectrum in (b) is along the $\overline{K}$\-
$\overline{M}$ \- $\overline{K^{\prime}}$ direction and (d-g) is taken
parallel to it. Blue arrows show the double bands. All spectra collected with
75 eV LH polarized light at 10 K. Figure 4:  (a-b) The Fermi surfaces and
corresponding ARPES maps along $\overline{K}$\- $\overline{M}$ \-
$\overline{K^{\prime}}$ direction. (c) MDCs taken at the Fermi level from each
spectrum. Orange and black lines in (c) are the Lorentzian peak fittings and
dashed lines in (c) are sum of fittings.

Multiple bands can be also probed in the band structure along the
$\overline{K}$ \- $\overline{M}$ \- $\overline{K}^{\prime}$ with more
elaborate approach. Fermi surfaces taken at various photon energies are given
in Figure 4(a). In the data, 80 eV and 97 eV photons correspond to kz = $A$
and kz = $\Gamma$ high symmetry points in 2D momentum plane. Ellipsoidal
pocket centered at $\overline{M}$-point shows a strong photon energy
dependence and it resembles more like a dog-bone at kz = $\Gamma$. In addition
to this strong spectral feature, second band with a weaker intensity can be
also visually observed in some parts of the Fermi surface. These multiple
bands can be seen in ARPES maps along $\overline{K}$ \- $\overline{M}$ \-
$\overline{K}^{\prime}$ as marked with dashed yellow and black lines (Figure
4(b)).

To further support this observation, the MDCs taken at the Fermi level are
compared in Figure 4(c). Bands located at $\pm$ k| with respect to
$\overline{M}$-point exhibit double peak features as indicated with yellow and
black fitting lines. Thereby, the V-shape conduction band is indeed formed by
two bands as inner and outer ones. Based on Figure 3(b-c), these two bands
have distinct kz dispersion as the outer band is 2D like while the inner one
has 3D character and their spectral intensities show an opposite kz
dependence. This has an important implication for the CDW phase of the VSe2.
One of the fundamental experimental evidence for the CDW phase was reported to
be a warping effect on the Fermi surface along the kz direction [13, 22, 14].
However, this warping effect is clearly due to the different nature of these
mulitple bands crossing the Fermi level and not correlated with any type of
structural distortion. Indeed, the appearent warping of the band structure is
temperature independent (Supplementary Materials SFigure 2). Therefore,
earlier observations are due to the lack of resolving multiple bands leading
to misinterpret the experimental data.

In summary, unlike the earlier studies, we show that the Fermi surface of VSe2
is dominated by multiple bands. By using this, each of the previous
observation can be explained and shown to be not related to any structural
distortion. These new findings need to be considered in order to understand
the correct nature of the CDW phase and find the structural distortion induced
modification on the electronic structure. Furthermore, these realization also
suggest that the large CDW induced gap of 100 meV in the monolayer VSe2 is
questionable [17, 18, 19, 17, 18, 19]. This is discussed in the Supplementary
Materials SFigure 3 and no gap is deducted around the $\overline{M}$-point
that can be associated with CDW phase. Furthermore, the apparent width of the
Fermi edge around the $\overline{M}$-point does not change with the
temperature in the monolayer case. This indicates that it is dominated by the
temperature independent defects such as vacancies which leads
misinterpretation of the data. All these new findings needs to be considered
in the future studies and they are probably the main reason for why the
mechanism behind the 3D charge density wave phase in VSe2 has never been
understood.

This research used resources ESM (21ID-I) beamline of the National Synchrotron
Light Source II, a U.S. Department of Energy (DOE) Office of Science User
Facility operated for the DOE Office of Science by Brookhaven National
Laboratory under Contract No. DE-SC0012704. We have no conflict of interest,
financial or other to declare.

## References

  * Mak and Shan [2016] K. F. Mak and J. Shan, Nature Photonics 10, 216 (2016).
  * Manzeli  _et al._ [2017] S. Manzeli, D. Ovchinnikov, D. Pasquier, O. V. Yazyev, and A. Kis, Nature Reviews Materials 2, 1 (2017).
  * Cho  _et al._ [2018] K. Cho, M. Kończykowski, S. Teknowijoyo, M. A. Tanatar, J. Guss, P. Gartin, J. Wilde, A. Kreyssig, R. McQueeney, A. I. Goldman, _et al._ , Nature communications 9, 1 (2018).
  * Yu  _et al._ [2021] F. Yu, D. Ma, W. Zhuo, S. Liu, X. Wen, B. Lei, J. Ying, and X. Chen, Nature communications 12, 1 (2021).
  * Grüner [1988] G. Grüner, Reviews of modern physics 60, 1129 (1988).
  * Monceau [2012] P. Monceau, Advances in Physics 61, 325 (2012).
  * Wilson  _et al._ [1974] J. Wilson, F. Di Salvo, and S. Mahajan, Physical review letters 32, 882 (1974).
  * Wang  _et al._ [1991] C. Wang, C. Slough, and R. Coleman, Journal of Vacuum Science & Technology B: Microelectronics and Nanometer Structures Processing, Measurement, and Phenomena 9, 1048 (1991).
  * Giambattista  _et al._ [1990] B. Giambattista, C. Slough, W. McNairy, and R. Coleman, Physical Review B 41, 10082 (1990).
  * Eaglesham  _et al._ [1986] D. Eaglesham, R. Withers, and D. Bird, Journal of Physics C: Solid State Physics 19, 359 (1986).
  * Tsutsumi [1982] K. Tsutsumi, Physical Review B 26, 5756 (1982).
  * Terashima  _et al._ [2003] K. Terashima, T. Sato, H. Komatsu, T. Takahashi, N. Maeda, and K. Hayashi, Physical Review B 68, 155108 (2003).
  * Sato  _et al._ [2004] T. Sato, K. Terashima, S. Souma, H. Matsui, T. Takahashi, H. Yang, S. Wang, H. Ding, N. Maeda, and K. Hayashi, journal of the physical society of japan 73, 3331 (2004).
  * Wang  _et al._ [2021] Z. Wang, Q. Yin, S. Yan, L. Wu, X. Wu, M. Li, W. Song, Q. Liu, H. Ma, W. Ji, _et al._ , Physical Review B 104, 155134 (2021).
  * Falke  _et al._ [2021] Y. Falke, N. Ehlen, G. Marini, A. Fedorov, V. Voroshnin, B. Senkovskiy, K. Nikonov, M. Hoesch, T. Kim, L. Petaccia, _et al._ , Physical Review B 104, 235137 (2021).
  * Jolie  _et al._ [2019] W. Jolie, T. Knispel, N. Ehlen, K. Nikonov, C. Busse, A. Grueneis, and T. Michely, Physical Review B 99, 115417 (2019).
  * Chen  _et al._ [2018] P. Chen, W. W. Pai, Y.-H. Chan, V. Madhavan, M.-Y. Chou, S.-K. Mo, A.-V. Fedorov, and T.-C. Chiang, Physical review letters 121, 196402 (2018).
  * Feng  _et al._ [2018] J. Feng, D. Biswas, A. Rajan, M. D. Watson, F. Mazzola, O. J. Clark, K. Underwood, I. Markovic, M. McLaren, A. Hunter, _et al._ , Nano letters 18, 4493 (2018).
  * Zong  _et al._ [2022] J. Zong, Y. Xie, Q. Meng, Q. Tian, W. Chen, X. Xie, S. Jin, Y. Zhang, L. Wang, W. Ren, _et al._ , Chinese Physics B (2022).
  * Giannozzi  _et al._ [2009] P. Giannozzi, S. Baroni, N. Bonini, M. Calandra, R. Car, C. Cavazzoni, D. Ceresoli, G. L. Chiarotti, M. Cococcioni, I. Dabo, _et al._ , Journal of physics: Condensed matter 21, 395502 (2009).
  * Giannozzi  _et al._ [2017] P. Giannozzi, O. Andreussi, T. Brumme, O. Bunau, M. B. Nardelli, M. Calandra, R. Car, C. Cavazzoni, D. Ceresoli, M. Cococcioni, _et al._ , Journal of physics: Condensed matter 29, 465901 (2017).
  * Strocov  _et al._ [2012] V. N. Strocov, M. Shi, M. Kobayashi, C. Monney, X. Wang, J. Krempasky, T. Schmitt, L. Patthey, H. Berger, and P. Blaha, Physical Review Letters 109, 086401 (2012).
  * He  _et al._ [2021] J. He, Q. Xie, and G. Xu, New Journal of Physics 23, 023027 (2021).
  * Coelho  _et al._ [2019] P. M. Coelho, K. Nguyen Cong, M. Bonilla, S. Kolekar, M.-H. Phan, J. Avila, M. C. Asensio, I. I. Oleynik, and M. Batzill, The Journal of Physical Chemistry C 123, 14089 (2019).


L^{\tilde{q}^{\prime}_{2}}_{t}L^{\tilde{r}^{\prime}_{2}}_{x}L^{\tilde{p}^{\prime}_{2}}_{v}.\end{split}$

Thus we have a solution for the full Boltzmann equation if $g=h$.

To prove that $g=h$, we let $w=g-h\geq 0$. By (6.38) the difference $w$
satisfies the equation

$\partial_{t}w+v\cdot\nabla_{x}w=Q^{+}(g,w)+Q^{+}(w,h)+Q^{-}(g,w)-Q^{-}(w,g)$

with zero initial data. By Lemma 6.9 below we know that this equation has a
unique solution $w\equiv 0$. Thus $g=h$ and we conclude the global existence
of the non-negative mild solution for the full Boltzmann equation. The
uniqueness of this solution can be proved by a standard continuity argument
and the fact that the solutions are non-negative. We include it in subsection
6.3. Also the continuity in time, scattering of the solution and Lipschitz
continuous of the solution map is included in the subsection 6.4. Thus we
conclude the Proposition 6.8.

∎

We need a lemma before we start the proof of the uniqueness.

######  Lemma 6.9.

Let $g,\;h$ be non-negative functions satisfy (6.45). Suppose that $w\geq 0$
is a mild solution of

(6.46)
$\left\\{\begin{array}[]{l}\partial_{t}w+v\cdot\nabla_{x}w=Q^{+}(g,w)+Q^{+}(w,h)+Q^{-}(g,w)-Q^{-}(w,g)\\\
w(0)=0.\end{array}\right.$

Then $w\equiv 0$.

###### Proof.

Consider the given time interval $[0,T]$ and define

$t_{0}=\inf{\Big{\\{}}t\in[0,T]{\Big{|}}\|w(t)\|_{L^{q_{2}}([0,t],L^{r_{2}}_{x}L^{p_{2}}_{v})}>0{\Big{\\}}}.$

Then $w\equiv 0$ for $0\leq t\leq t_{0}$. Let $t_{0}\leq s\leq T$.

From (6.46), we have

$w(s)=\int_{0}^{s}U(t-\tau){\big{[}}Q^{+}(g,w)+Q^{+}(w,h)+Q^{-}(g,w)-Q^{-}(w,g){\big{]}}(\tau)d\tau.$

Noting that $w\geq 0$, $0\leq h\leq g$ and the operators $U(t),Q^{+},Q^{-}$
are non-negative, we have

(6.47) $0\leq
w(s)\leq\int_{0}^{s}U(t-\tau){\big{[}}Q^{+}(g,w)+Q^{+}(w,h)+Q^{-}(g,w){\big{]}}(\tau)d\tau.$

Using (6.44), applyying Strichartz estimates as Proposition 6.6 and also the
estimates of Proposition 6.7, then we have

(6.48) $\begin{split}&\|\langle
v\rangle^{\ell_{2}}w\|_{L^{q_{2}}([t_{0},s],L^{r_{2}}_{x}L^{p_{2}}_{v})}\\\
&\leq C(\|\langle
v\rangle^{\ell}g\|_{L^{\mathbbm{q}}([t_{0},s],L^{\mathbbm{r}}_{x}L^{\mathbbm{p}}_{v})}+\\\
&\hskip 85.35826pt\|\langle
v\rangle^{\ell_{2}}h\|_{L^{\mathbbm{q}}([t_{0},s],L^{\mathbbm{r}}_{x}L^{\mathbbm{p}}_{v})})\|\langle
v\rangle^{\ell_{2}}w\|_{L^{q_{2}}(([t_{0},s],L^{r_{2}}_{x}L^{p_{2}}_{v})}\\\
&:=C(g,h,s)\|\langle
v\rangle^{\ell_{2}}w\|_{L^{q_{2}}([t_{0},s],L^{r_{2}}_{x}L^{p_{2}}_{v})}.\end{split}$

Letting $s\rightarrow t_{0}+$, clearly we have $C(g,h,s)<1$ which means that

$\|w\|_{L^{q_{2}}([t_{0},s],L^{r_{2}}_{x}L^{p_{2}}_{v})}=0$

for some $s>t_{0}$. By continuity, we have $w|_{[0,T]}\equiv 0$ for any $T>0$.
∎

###  6.3. Uniqueness of the solution

Assume that $g\geq 0$ and $h\geq 0$ both are mild solutions which satisfy
(1.14). Let $w=g-h$. Comparing to Lemma 6.9, the function $w$ satisfies
(6.46), but we do not have the property $w\geq 0$. For our convenience, we
rewrite (6.46) as

$\left\\{\begin{array}[]{l}\partial_{t}w+v\cdot\nabla_{x}w+wL(g)=Q^{+}(g,w)+Q^{+}(w,h)+Q^{-}(g,w)\\\
w(0)=0,\end{array}\right.$

and want to show $w\equiv 0$. Since $g,\;h$ and thus $w$ satisfy (6.45), the
term $L(g)$ is pointwisely a.e. well-defined. Thus the function $w$ satisfies

$\begin{split}&w(t)=\int_{0}^{t}e^{-\int_{s}^{t}U(t-\tau)L(g)(\tau)d\tau}\\\
&\hskip 85.35826pt\cdot
U(t-s){\big{[}}Q^{+}(g,w)+Q^{+}(w,h)+Q^{-}(g,w){\big{]}}(s)ds.\end{split}$

Using the fact that $L(g)\geq 0$ since $g\geq 0$, we have

(6.49)
$|w(t)|\leq\int_{0}^{t}U(t-s){\big{[}}Q^{+}(g,|w|)+Q^{+}(|w|,h)+Q^{-}(g,|w|){\big{]}}(s)ds.$

The equation (6.49) is in place of (6.47) for the proof of $w\equiv 0$, thus
we conclude the uniqueness of the solution.

###  6.4. Continuity in $L^{3}_{x,v}$ and Scattering of the solution

Now we show that $\langle v\rangle^{\ell}f\in C([0,T],L^{3}_{x,v})$ for any
$T\in[0,\infty]$. From the formula

(6.50)
$\int_{0}^{t}U(t-s)Q^{-}(f,f)(s)ds+f(t)=U(t)f_{0}+\int_{0}^{t}U(t-s)Q^{+}(f,f)(s)ds$

and the observation that each term in (6.50) is non-negative, we have

(6.51) $0\leq f(t)\leq U(t)f_{0}+\int_{0}^{t}U(t-s)Q^{+}(f,f)(s)ds.$

It has been observed by Ovcharov [37] that $U(t)f_{0}\in
C(\mathbb{R};L^{N}_{x,v})$ when $f_{0}\in L^{N}_{x,v}$. As we point out before
that multiplication of weight $\langle v\rangle^{\ell}$ commutes with $U(t)$,
thus we have $\langle v\rangle^{\ell}U(t)f_{0}\in C(\mathbb{R};L^{3}_{x,v})$.
Thus it suffices to show that $W(t)$ (see (6.8)) is also continuous. Let
$0\leq t\in(0,\infty]$. Applying inhomogeneous Strichartz with triplet
$(\tilde{\mathbbm{q}}^{\prime},\tilde{\mathbbm{r}}^{\prime},\tilde{\mathbbm{p}}^{\prime})$
used in (6.17), we see that

$\|\langle
v\rangle^{\ell}W(t)Q^{+}(f,f)\|_{L^{\infty}([0,t];L^{3}_{x,v})}=\int_{0}^{t}\|U(t-s)\langle
v\rangle^{\ell}Q^{+}(f,f)\|_{L^{3}_{x,v}}ds$

is bounded. Since $U(t)$ is continuous, we conclude that $W(t)$ is continuous
from above expression. Also the solution map $\langle v\rangle^{\ell}f_{0}\in
B_{\eta}\subset L^{3}_{x,v}\rightarrow\langle v\rangle^{\ell}f\in
L^{\mathbbm{q}}_{t}L^{\mathbbm{r}}_{x}L^{\mathbbm{p}}_{v}$ is Lipschitz
continuous.

Next we want to show that the solution $f$ scatters, i.e., there exists a
function $f_{\infty}$ with $\langle v\rangle^{\ell}f_{\infty}\in L^{3}_{x,v}$
such that

$\|\langle v\rangle^{\ell}f(t)-U(t)(\langle
v\rangle^{\ell}f_{\infty})\|_{L^{3}_{x,v}}\rightarrow 0\;\;{\rm
as}\;t\rightarrow\infty.$

The above statement is equivalent to prove that

(6.52) $\|U(-t)(\langle v\rangle^{\ell}f)(t)-\langle
v\rangle^{\ell}f_{\infty}\|_{L^{3}_{x,v}}\rightarrow 0\;\;{\rm
as}\;t\rightarrow\infty,$

since $U(t)$ preserves the $L^{3}_{x,v}$ norm.

By the Duhamel formula, we have

(6.53) $U(-t)f(t)=f_{0}+\int_{0}^{t}U(-s)Q(f,f)(s)ds.$

Hence the scattering of $f(t)$ is confirmed if we have the convergence of the
integral

$\langle v\rangle^{\ell}\int_{0}^{\infty}U(-t)Q(f,f)(t)dt$

in $L^{3}_{x,v}$. In this case $f_{\infty}$ is given by

(6.54) $f_{\infty}=f_{0}+\int_{0}^{\infty}U(-t)Q(f,f)(t)dt.$

We rewrite (6.53) as

$U(-t)f(t)+\int_{0}^{t}U(-s)Q^{-}(f,f)(s)ds=f_{0}+\int_{0}^{t}U(-s)Q^{+}(f,f)(s)ds.$

Since each term of above equation is non-negative, thus we have

$\begin{split}\int_{0}^{t}U(-s)Q^{-}(f,f)(s)ds&\leq
f_{0}+\int_{0}^{t}U(-s)Q^{+}(f,f)(s)ds\\\ &\leq
f_{0}+\int_{0}^{\infty}U(-s)Q^{+}(f,f)(s)ds.\end{split}$

By monotone convergence theorem, it holds that

(6.55) $\int_{0}^{\infty}U(-s)Q^{-}(f,f)(s)ds\leq
f_{0}+\int_{0}^{\infty}U(-s)Q^{+}(f,f)(s)ds.$

Then we are reduced to prove the right hand side of (6.55) is bounded in
$L^{3}_{x,v}$.

Let $U^{*}(t)$ be the adjoint operator of $U(t)$, it is clearly that
$U^{*}(t)=U(-t)$. Let
$(\tilde{\mathbbm{q}},\tilde{\mathbbm{r}},\tilde{\mathbbm{p}})$ be the KT-
admissible triplet chosen in (6.17) and recall that
$1/\tilde{\mathbbm{p}}^{\prime}+1/\tilde{\mathbbm{r}}^{\prime}=2/3$. By
duality, the homogeneous Strichartz estimate

$\|\langle
v\rangle^{\ell}U(t)g\|_{L^{\tilde{\mathbbm{q}}}_{t}L^{\tilde{\mathbbm{r}}}_{x}L^{\tilde{\mathbbm{p}}}_{v}}\leq
C\|\langle v\rangle^{\ell}g\|_{L^{{3}/{2}}_{x,v}}$

implies

$\begin{split}&\bigg{\|}\int_{0}^{\infty}\langle
v\rangle^{\ell}U^{*}(t)Q^{+}(f,f)dt\bigg{\|}_{L^{3}_{x,v}}\\\ &\leq C\|\langle
v\rangle^{\ell}Q^{+}(f,f)\|_{L^{\tilde{\mathbbm{q}}^{\prime}}_{t}L^{\tilde{\mathbbm{r}}^{\prime}}_{x}L^{\tilde{\mathbbm{p}}^{\prime}}_{v}}\leq
C\|\langle
v\rangle^{\ell}f\|^{2}_{L^{\mathbbm{q}}_{t}L^{\mathbbm{r}}_{x}L^{\mathbbm{p}}_{v}}\end{split}$

as before. Thus we conclude that $\langle v\rangle^{\ell}f$ scatters.

##  7\. Some tools

One of the most powerful tools in estimating the oscillatory integral

$I_{\Lambda}(u,f)=\int_{{\mathbb{R}}^{n}}e^{i\Lambda f(y)}u(y)dy,$

for large $\Lambda$ is the following lemma of stationary phase asymptotics.
There are several versions used widely, here we only record one of these which
is from Theorem 7.7.5 of Hörmander [23]. We use the notation
$D_{j}=-i\partial_{j}$.

######  Theorem 7.1 (Stationary phase asymptotics).

Let $K\subset{\mathbb{R}}^{n}$ be a compact set, $X$ an open neighborhood of
$K$ and $k$ a positive number. If $u\in C^{2k}_{c}({\mathbb{R}}^{n}),f\in
C^{3k+1}(X)$ and ${\rm Im}\;f\geq 0$ in $X,{\rm
Im}\;f(y_{0})=0,f^{\prime}(y_{0})=0,{\rm det}\;f^{\prime\prime}(y_{0})\neq
0,f^{\prime}\neq 0$ in $K\backslash\\{{y_{0}}\\}$ then

(7.1) $\displaystyle|I$ $\displaystyle-e^{i\Lambda f(y_{0})}({\rm det}(\Lambda
f^{\prime\prime}(y_{0})/2\pi i))^{-1/2}\sum_{j<k}\Lambda^{-j}L_{j}u|$
$\displaystyle\leq C\Lambda^{-k}\sum_{|\alpha|\leq
2k}\sup|D^{\alpha}u|\;,\;\Lambda>0$

Here $C$ is bounded when $f$ stays in a bounded set in $C^{3k+1}(X)$ and
$|y-y_{0}|/|f^{\prime}(y)|$ has a uniform bound. With

$g_{y_{0}}(y)=f(y)-f(y_{0})-\langle
f^{\prime\prime}(y_{0})(y-y_{0}),y-y_{0}\rangle/2$

which vanish of third order at $x_{0}$ we have

(7.2) $L_{j}u=\sum_{\nu-\mu=j}\;\;\sum_{2\nu\geq 3\mu}i^{-j}2^{-\nu}\langle
f^{\prime\prime}(y_{0})^{-1}D,D\rangle^{\nu}(g_{y_{0}}^{\mu}u)(y_{0})/\mu!\nu!$

which is a differential operator of order $2j$ acting on $u$ at $y_{0}$. The
coefficients are rational homogeneous functions of degree $-j$ in
$f^{\prime\prime}(y_{0}),\cdots,f^{2j+2}(y_{0})$ with denominator $({\rm
det}\;f^{\prime\prime}(y_{0}))^{3j}$. In every term the total number of
derivatives of $u$ and $f^{\prime\prime}$ is at most $2j$.

We need the following Schur’s Lemma which can be found in [40].

######  Lemma 7.2.

Let $\mu$ and $\nu$ be two positive measures on the space $X$. Let $K(x,y)$ be
a nonnegative measurable functions on $X\times X$. Let $T$ be the integral
operator with kernel $K$, as

$T(f)(x)=\int_{Y}K(x,y)f(y)d\nu(y)$

Suppose $1<p\leq q<\infty$ and $\frac{1}{p}+\frac{1}{p^{\prime}}=1$. Let
$\delta_{1}$ and $\delta_{2}$ be two real numbers such that
$\delta_{1}+\delta_{2}=1$. If there exist positive functions $h_{1}$ and
$h_{2}$ with positive constants $C_{1}$ and $C_{1}$ such that

$\int_{X}K(x,y)^{\delta_{1}p^{\prime}}h_{1}(y)^{p^{\prime}}d\mu(y)\leq
C_{1}h_{2}(x)^{p^{\prime}}$

for almost all $x\in X$, and

$\int_{X}K(x,y)^{\delta_{2}q}h_{2}(x)^{q}d\mu(y)\leq C_{2}h_{1}(y)^{q}$

Then $T$ maps $L^{p}(Y)$ to $L^{q}(X)$ with norm at most
$C_{1}^{1/p^{\prime}}C_{2}^{1/q}$.

Acknowledgments. Ling-Bing He is supported by NSF of China under the grant
12141102. Jin-Cheng Jiang and Meng-Hao Liang were supported in part by
National Sci-Tech Grant MOST 109-2115-M-007-002-MY3 and NSTC
112-2115-M-007-005-MY3. Hung-Wen Kuo was supported in part by NSTC
112-2115-M-006-009.

## References

  * [1] R. Alonso and E. Carneiro,Estimates for the Boltzmann collision operator via radial symmetry and Fourier transform, Advance in Math. 223 (2010), pp. 511-528.
  * [2] R. Alonso, E. Carneiro and I.M. Gamba,Convolution inequalities for the Boltzmann collision operator, Comm. Math. Physics, 298 (2010), pp. 293-322.
  * [3] R. Aloson and I.M. Gamba, Gain of integrability for the Boltzmann collisional operator, Kinetic and Related Models, 4 (2011), pp. 41-51.
  * [4] D. Arsénio, On the Global Existence of Mild Solutions to the Boltzmann Equation for Small Data in $L^{D}$, Comm. Math. Physics, 302 (2011), pp. 453-476.
  * [5] H. Bahouri, J. Chemin and R. Danchin, Fourier Analysis and Nonlinear Partial Differential Equations, Grundlehren der mathematischen Wissenschaften. Vol. 343. Berlin, Heidelberg: Springer, 2011.
  * [6] C. Bardos, I. Gamba, F. Golse, C.D. Levermore, Global Solutions of the Boltzmann Equation Over $\mathbb{R}^{D}$ Near Global Maxwellians with Small Mass, Comm. Math. Physics, 346 (2016), pp. 435-467.
  * [7] J. Bennett, N. Bez, S. Gutiérrez and S. Lee, On the Strichartz estimates for the kinetic transport equation, Comm. PDE, 39 (2014), pp. 1821-1826.
  * [8] N. Bellomo, A. Palczewski and G. Toscani, Mathematical Topics in Nonlinear Kinetic Theory, World Scientific, Singapore, 1988.
  * [9] T. Chen, R. Denlinger and N. Pavlović, Small data global well-posedness for a Boltzmann equation via bilinear spacetime estimates, Arch. Rational Mech. Anal. 240 (2021), pp. 327-381.
  * [10] R. Coifman, A real variable characterization of $H^{p}$, Studia Math., 51 (1974),pp. 269–274.
  * [11] H. Cordes, The Technique of Pseudodifferential Operators, Cambridge Univ. Press, Cambridge, 1995
  * [12] S. Coriasco, Fourier integral operators in SG classes I: composition theorems and action on SG Sobolev spaces, Rend. Sem. Mat. Univ. Pol. Torino, 57 (1999), pp. 249-302.
  * [13] F. Castella and B. Perthame, Strichartz estimates for kinetic transport equations, C.R. Acad. Sci. Paris Sér. I Math. 322, no. 6 (1996), pp. 535-540.
  * [14] S. Coriasco and M. Ruzhansky Global $L^{p}$ continuity of Fourier integral operators, Trans. Amer. Math. Soc., 366 (2014) no.5, pp. 2575-2569.
  * [15] R. Duduchava, R. Kirsch and S. Rjasanow, On estimates of the Boltzmann collision operator with cutoff, J. Math. Fluid Mech., 8 (2006), pp. 242-266.
  * [16] R. Glassey, The Cauchy problem in kinetic theory, SIAM, Philadelphia, 1996.
  * [17] L. Grafakos, Modern Fourier analysis, GTM 250, Springer, New York, 2014
  * [18] T. Gustsfsson, $L^{p}$ estimates for the nonlinear spatially homogeneous Boltzmann equation, Arch. Rational Mech. Anal., 92 (1986), pp. 23-57.
  * [19] T. Gustsfsson, Global $L^{p}$ properties for the spatially homogenous Boltzmann equation, Arch. Rational Mech. Anal., 103 (1988), pp. 1-38.
  * [20] L.-B. He, _Sharp bounds for Boltzmann and Landau collision operators_ , Ann. Sci. Ec. Norm. Super. 51 (2018) no.4, 1285-1373.
  * [21] L.-B. He and J-C. Jiang, Well-posedness and scattering for the Boltzmann equations:Soft potential with cut-off, Journal of Statistical Physics, 168 (2017) v.2, pp. 470-481.
  * [22] L.-B. He and J-C. Jiang, On the Cauchy problem for the cutoff Boltzmann equation with small initial data, Journal of Statistical Physics, 190 (2023), Article no. 52.
  * [23] L. Hörmander, The analysis of linear partial differential operators I, Springer, Berlin, 1983.
  * [24] R. Illner and M. Shinbrot, The Boltzmann equation, global existence for a rare gas in an infinite vacuum, Comm. Math. Phys., 95 (1984), pp. 217-226.
  * [25] J.-C. Jiang, Smoothing property of gain part of Boltzmann collision operator, SIAM J. Math. Anal. 44 (2012) no.3, pp. 1522-1543.
  * [26] J.-C. Jiang, Sharp regularizing estimates for the gain term of the Boltzmann collision operator, SIAM J. Math. Anal. 52 (2020) no.4, pp. 4068-4100.
  * [27] J.-C. Jiang and T.-P. Liu, Boltzmann collision operator for the infinite range potential:a limit problem, Ann. Inst. H. Poincare Anal. Non lineaire., 36 (2019) no.6, pp.1639-1677.
  * [28] S. Kaniel and M. Shinbrot, The Boltzmann equation, I. Uniqueness and local existence, Comm. Math. Phys., 55 (1978), pp. 65-84.
  * [29] R. Latter, A characterization of $H^{p}(\mathbb{R}^{n})$ in terms of atoms. Studia Math., 62 (1978), no. 1, pp.93–101.
  * [30] M.-H. Liang $L^{p}$ estimates for the gain term of the $N$-dimensional Boltzmann collision operator, in preparation.
  * [31] P.-L. Lions, Compactness in Boltzmann’s equation via Fourier integral operators and applications. I, II, J. Math. Kyoto Univ., 34 (1994), pp. 391-427, pp. 429-461.
  * [32] X. Lu, A direct method for the regularity of the gain term in the Boltzmann equation, J. Math. Anal. Appl., 228 (1998) , pp. 409-435.
  * [33] C. Mouhot and C. Villani, Regularity Theory for the Spatially Homogeneous Boltzmann Equation with Cut-Off, Arch. Rational Mech. Anal., 173 (2004), pp. 169-212.
  * [34] A. Seeger, C. Sogge, and E. Stein, Regularity properties of Fourier integral operators, Ann. of Math. (2) 134 (1991), no. 2, pp. 231–251
  * [35] E. Stein, Harmonic Analysis: Real Variable Methods, Orthogonality, and Oscillatory Integrals, Princeton Univ. Press, 1993.
  * [36] H. Triebel, Theory of Function Spaces II, Birkhäuser Verlag, Basel 1992.
  * [37] E. Ovcharov, Global regularity of nonlinear dispersive equations and Strichartz estimates, (2009) Ph.D. Thesis.
  * [38] E. Ovcharov, Strichartz estimates for the kinetic transport equation, SIAM J. Math. Anal. 43 (2011) no.3, pp. 1282-1310.
  * [39] B. Wennberg, Regularity in the Boltzmann equation and the radon transfrom, Comm. Partial Differential Equations, 19 (1994), pp. 2057-2074.
  * [40] R. Zhao, Generalization of Schur’s test and its application to a class of integral operators on the unit ball of $\mathbb{C}^{n}$, Integr. Equ. Oper. Theory 82 (2015), pp. 519-532.


# K-means clustering for efficient and robust registration of multi-view point
sets

Zutao Jiang  Jihua Zhu<EMAIL_ADDRESS>Georgios D. Evangelidis  Changqing
Zhang  Shanmin Pang  Yaochen Li  School of Software Engineering, Xi’an
Jiaotong Universiy, P. R. China  DAQRI, Vienna, Austria  School of Computer
Science and Technology, Tianjin Universiy, P. R. China

###### Abstract

Generally, there are three main factors that determine the practical usability
of registration, i.e., accuracy, robustness, and efficiency. In real-time
applications, efficiency and robustness are more important. To promote these
two abilities, we cast the multi-view registration into a clustering task. All
the centroids are uniformly sampled from the initially aligned point sets
involved in the multi-view registration, which makes it rather efficient and
effective for the clustering. Then, each point is assigned to a single cluster
and each cluster centroid is updated accordingly. Subsequently, the shape
comprised by all cluster centroids is used to sequentially estimate the rigid
transformation for each point set. For accuracy and stability, clustering and
transformation estimation are alternately and iteratively applied to all point
sets. We tested our proposed approach on several benchmark datasets and
compared it with state-of-the-art approaches. Experimental results validate
its efficiency and robustness for the registration of multi-view point sets.

###### keywords:

Multi-view registration, point sets, K-means clustering, Iterative closest
point

††journal: Pattern Recognition

##  1 Introduction

As a fundamental issue in many areas, the problem of point set registration
has attracted immense attention in computer vision [1, 2, 3], computer
graphics [4, 5], and robotics [6, 7]. The aim of point set registration is to
estimate the optimal transformation between different point sets. According to
the involved number of point sets, this problem can be roughly divided into
the pair-wise registration and the multi-view registration, with the former
being extensively addressed.

Commonly, the problem of pair-wise registration is solved by the iterative
closest point (ICP) algorithm [8] or its variants [9, 10, 11]. To achieve
registration, most of these approaches alternately build hard correspondences
and estimate the transformation. Such approaches are efficient but may be not
accurate enough. Furthermore, some registration approaches [12, 13, 14, 15]
replace the hard assignment with the soft assignment so as to obtain more
accurate results. Since the soft assignment should be built from each point to
all points in the opposite point set, these approaches are time-consuming.
Besides, most of ICP variants are locally convergent. To obtain the desired
global minimum, particle filter [16, 17] and genetic algorithm [18, 19] can be
combined to estimate the optimal transformation. 3D features can be also
extracted from the point sets and they can be matched to provide initial
transformation for the pair-wise registration[20, 21, 22].

The development of scanning equipment makes the 3D reconstruction of an object
possible. Due to the occlusion, however, the object cannot be entirely scanned
from a single viewpoint. Therefore, scanners should acquire point sets from
different viewpoints so as to cover the entire object surface. These point
sets can then be transformed into one common reference frame for the 3D model
reconstruction[23].

Unlike pair-wise registration, multi-view registration is more difficult and
has comparatively attracted less attention. Usually, the multi-view
registration can be divided into two stages: the coarse registration and fine
registration. For the coarse registration, some approaches apply the pair-wise
registration method on all or some of point set pairs, then search the minimum
set of pair-wise registration results to estimate the initial rigid
transformations for the multi-view registration [24, 25, 26]. Since there are
a lot of point set pairs involved in the multi-view registration, the coarse
registration approaches are always time-consuming. To accelerate this stage,
3D features can be extracted and matched to provide good initial parameters
for the pair-wise registration [27, 28, 29].

The fine registration has attracted considerably more attention. The common
strategy is to sequentially align and merge two point sets until all point
sets are merged into one model [30]. Although this approach may be efficient,
it generally suffers from the error accumulation. To address this issue,
Bergevin _et al_. [31] suggested to establish the correspondence between one
point set and any other point set so as to estimate the rigid transformation
of this point set. As the establishment of correspondence is time-consuming,
the efficiency of this approach is very low. Therefore, Pulli [32] proposed to
align point sets with each other and utilize the pairwise alignments as
constraints to evenly diffuse the pairwise registration errors in the multi-
view registration step. Inspired by these approaches, the pair-wise
registration algorithm can be sequentially utilized to align one point set to
the coarse model constructed by all point sets [33]. The outcome can be used
to update the coarse model, which can be further used to align each point set.
Due to too many points in the reconstructed model, however, the complexity of
these approaches is relatively high. The multi-view registration can be also
viewed as graph optimization problem [34, 35, 36], where each node denotes one
point set and each edge indicates the pair-wise registration of two connected
nodes. Without the correspondence update, these approaches can diffuse the
registration error over the graph of adjacent point sets. Despite their
efficiency, these approaches only transfer registration errors among graph
nodes and are unable to reduce the total registration errors.

Recently, Govindu and Pooja [37, 38] proposed the motion averaging algorithm
for the multi-view registration. It can recover all rigid transformations
simultaneously for multi-view registration from a set of relative motions,
which can be estimated by the pair-wise registration. Given reliable and
accurate relative motions [39], the motion averaging algorithm can achieve
accurate multi-view registration. In practical applications, the relative
motions obtained from the pair-wise registration should be confirmed [40, 41]
so as to provide reliable and accurate relative motions to the motion
averaging algorithm. Alternatively, the multi-view registration can also be
cast into the problem of low-rank and sparse (LRS) matrix decomposition [42].
For some scan pairs with large overlap, the relative motions can be estimated
and concatenated into a large matrix, which has missed data corresponding to
the scan pairs with low overlapping percentages. By the LRS decomposition, the
matrix can be completed and the multi-view registration results can be
recovered. Compared to other approaches, it is more likely to be affected by
the sparsity of the uncompleted matrix.

More recently, Evangelidis and Horaud [43] held the assumption that all the
points involved in multi-view registration are drawn from a single Gaussian
mixture, thus formulating registration as a soft clustering problem. An
expectation maximization (EM) algorithm is utilized to estimate both the
mixture parameters and the rigid transformations that optimally align the
point sets. Although this approach is accurate, lots of parameters need to be
estimated and the computational cost is quite high.

In this paper, we propose a new multi-view registration algorithm formulated
as a joint clustering and alignment problem. We build on well known clustering
paradigm, i.e., the K-means algorithm. We first design the new objective
function and then present the proposed multi-view registration algorithm.
Given initially posed point sets, this algorithm starts with estimating the
initial centroids. Then it performs the clustering operation, which consists
in the assignment of each point to a single cluster and the update of all
cluster centroids. As the multi-view point sets are not well aligned, the
shape comprised by all the updated centroids can be used as a reference point
set to sequentially estimate the rigid transformation for each point set by
the pair-wise registration. To obtain the desired results, clustering and
transformation estimation are alternately and iteratively applied to all point
sets. For the 3D model reconstruction, the K-means clustering was initially
introduced by Zhou _et al_. in [44], where the K-means clustering algorithm
was utilized to detect and merge the corresponding points of the overlapping
areas. It doesn’t involve the update of rigid transformations and only can be
viewed as a a post-processing step after multi-view registration step in 3D
reconstruction.

The remaining of the paper is organized as follows. Section 2 gives a brief
introduction of K-means clustering algorithm. Following that, Section 3
proposes the novel approach for registration of multi-view point sets. In
Section 4, the proposed approach is tested on some benchmark data-sets.
Section 5 concludes this paper.

##  2 K-means clustering

As an unsupervised learning method, K-means algorithm is effective and
interpretable for the clustering. Given the number of clusters $K$ and the
data set $X=\\{{\vec{x}_{j}}\\}_{j=1}^{M}$, the algorithm starts with initial
estimation of the $K$ centroids $\\{\vec{\mu}_{k}^{0}\\}_{k=1}^{K}$, which can
be either randomly selected or generated from the data sets. The clustering
result is obtained from the iteration of the following two steps.

Step 1: data assignment

${c^{q}}(j)=\mathop{\arg\min}\limits_{k\in\\{1,2,..,K\\}}\left\|{{{\vec{x}}_{j}}-\vec{\mu}_{k}^{q-1}}\right\|_{2}^{2}$
(1)

Step 2: centroid update

$\vec{\mu}_{k}^{q}=\frac{{\sum\nolimits_{j=1}^{M}{\\{{c^{q}}(j)=k\\}{{\vec{x}}_{j}}}}}{{\sum\nolimits_{j=1}^{M}{\\{{c^{q}}(j)=k\\}}}}$
(2)

Usually, good clustering results can be obtained by iteratively performing the
above steps until some convergence criterion is achieved.

##  3 K-means based multi-view registration

Given an accurate 3D scene model, the multi-view registration problem can be
divided into multiple subproblems, where each point set is pair-wise
registered to the accurate model, respectively. However, when scanning an
unknown scene, there is no accurate model beforehand. What is available is
just the coarse model reconstructed from the initially posed point sets, which
contains most likely unregistered points as well as too many redundant points
due to the overlapping areas among different point sets.

Figure 1: The proposed approach assumes that all points involved in multi-view
registration are sampled from $K$ clusters. Given the multi-view point sets,
the proposed approach starts with initial estimation for the $K$ cluster
centroids. Then, clustering and transformation estimation are alternately and
iteratively applied to all point sets until the stop criteria are met. The
output contain both the multi-view registration and clustering results.

To deal with these two issues, we here suppose that all the points, once
registered, are drawn from $K$ clusters, whose centroids can make up an
accurate model. Therefore, if all the points can be well clustered, the
accurate model can be constructed from the cluster centroids and the multi-
view registration can be achieved by the pair-wise registration between the
centroids and each point-set. Therefore, the multi-view registration can be
viewed as the extended clustering problem, which incorporates a pair-wise
registration solver. The flowchart of the proposed approach is displayed in
Fig. 1. Given the initial transformations that roughly align the point-sets,
e.g. by any pair-wise registration scheme, the main steps of our approach are
summarized as follows:

  1. 1.

Initialize centroids from initially aligned point sets, e.g. random selection
of $K$ points.

  2. 2.

Assign each point to the nearest cluster and then update the centroids.

  3. 3.

Align each point-set against the centroids

  4. 4.

Iterate 2) and 3) until convergence

###  3.1 Problem formulation

We are given $N$ point sets to register. Let
${{\mathbf{P}}_{i}}=\\{{\vec{p}_{ij}}\\}_{j=1}^{{M_{i}}}({\vec{p}_{ij}}\in{\mathbb{R}^{3\times
1}})$ denote the ${M_{i}}$ 3D points that belong to the $i$th point set and
let $M=\sum\nolimits_{i=1}^{N}{{M_{i}}}$ denote the total number of points. As
mentioned, we assume that all the $M$ points, once registered, are drawn from
$K$ clusters. Given initial rigid transformations
$\\{{\mathbf{R}}_{i}^{0},\vec{t}_{i}^{0}\\}_{i=1}^{N}$ that roughly align the
point-sets (e.g. by pairwise registration), the goal of multi-view
registration is to simultaneously group the $M$ points into $K$ clusters and
estimate accurate rigid transformations
$\\{{{\mathbf{R}}_{i}},{\vec{t}_{i}}\\}_{i=1}^{N}$ between each original point
set and the centroids. This is an essential difference from [43] which
registers Gaussian means with virtual points sets produced by the original
ones.

Given all the point sets $\\{{\mathbf{P}}_{i}\\}_{i=1}^{N}$ and assuming that
their points are samples drawn from $K$ clusters, represented via their
centroids $\\{\vec{\mu}_{k}\\}_{k=1}^{K}$, the multi-view registration can be
formulated as the following least-square (LS) problem:

$\begin{gathered}\mathop{\arg\min}\limits_{{{\mathbf{R}}_{i}},{{\vec{t}}_{i}},c(ij)\in\\{1,2,..,K\\}}\sum\limits_{i=2}^{N}{\sum\limits_{j=1}^{{M_{i}}}{({w_{ij}}\cdot\left\|{{{\mathbf{R}}_{i}}{{\vec{p}}_{ij}}+{{\vec{t}}_{i}}-{{\vec{\mu}}_{c(ij)}}}\right\|_{2}^{2})}}\hfill\\\
{\text{s}}{\text{.t}}{\text{.
}}{{\mathbf{R}}_{i}}^{T}{{\mathbf{R}}_{i}}={{\mathbf{I}}_{3}},\det({{\mathbf{R}}_{i}})=1\hfill\\\
\end{gathered}$ (3)

where ${\vec{\mu}_{c(ij)}}$ is the nearest cluster centroid of the transformed
point $({{\mathbf{R}}_{i}}{\vec{p}_{ij}}+{\vec{t}_{i}})$ and ${w_{ij}}$ is a
binary variable that quantifies the hard assignment. If the $c(ij)$th cluster
only contains the point that belongs to the $i$th point set, we set
${w_{ij}}=0$, otherwise ${w_{ij}}=1$. Note that solving problem (3) implies
solving both the clustering problem and the registration problem, that is, the
cluster centroids $\\{\vec{\mu}_{k}\\}_{k=1}^{K}$ are also unknown.

###  3.2 Proposed multi-view registration algorithm

K-means algorithm is very effective for the clustering. However, to solve
problem (3), it should be extended so as to cluster points and estimate the
rigid transformations simultaneously.

Regardless of registration, initial centroids
$\\{\vec{\mu}_{k}^{0}\\}_{k=1}^{K}$ are required for K-means. The initial
centroids can be either randomly selected or generated from the data set.
Given initial rigid transformations
$\\{{\mathbf{R}}_{i}^{0},\vec{t}_{i}^{0}\\}_{i=1}^{N}$, the coarse model can
be reconstructed by all point sets involved in the multi-view registration as
follows:

${\mathbf{P}}\buildrel\Delta\over{=}\\{{\mathbf{R}}_{i}^{0}{\vec{p}_{ij}}+\vec{t}_{i}^{0}\\}_{i=1,j=1}^{N,{M_{i}}}.$
(4)

Then, the initial centroids of all clusters
$\\{\vec{\mu}_{k}^{0}\\}_{k=1}^{K}$ can be uniformly sampled from this coarse
model. The shape comprised by all centroids is similar to the coarse model.
The only difference is the resolution of points.

Being provided with initial rigid transformations
$\\{{\mathbf{R}}_{i}^{0},\vec{t}_{i}^{0}\\}_{i=1}^{N}$, the K-means clustering
algorithm can be used to achieve the registration of multi-view point sets by
iterations. In each iteration, the following three steps are included:

Step 1: Assign each point to a single cluster:

${c^{q}}(ij)=\mathop{\arg\min}\limits_{k\in\\{1,2,..,K\\}}\left\|{{\mathbf{R}}_{i}^{q}{{\vec{p}}_{ij}}+\vec{t}_{i}^{q}-\vec{\mu}_{k}^{q}}\right\|_{2}^{2}.$
(5)

Step 2: Update the centroids for all clusters:

$\vec{\mu}_{k}^{q}=\frac{{\sum\nolimits_{ij=1}^{M}{\\{{c^{q}}(ij)=k\\}({\mathbf{R}}_{i}^{q}{{\vec{p}}_{ij}}+\vec{t}_{i}^{q})}}}{{\sum\nolimits_{ij=1}^{M}{\\{{c^{q}}(ij)=k\\}}}}.$
(6)

Step 3: Sequentially estimate each rigid transformation:

$\mathop{({\mathbf{R}}_{i}^{q},\vec{t}_{i}^{q})}=\arg\min\limits_{{{\mathbf{R}}_{i}},{{\vec{t}}_{i}}}\sum\limits_{j=1}^{{M_{i}}}{w_{ij}^{q}\left\|{{{\mathbf{R}}_{i}}{{\vec{p}}_{ij}}+{{\vec{t}}_{i}}-\vec{\mu}_{{c^{q}}(ij)}^{q}}\right\|_{2}^{2}}.$
(7)

As with the K-means algorithm, the above steps should be repeated until the
iteration number $q$ exceeds the maximum value $Q$ or all the estimated rigid
transformations have not drastically changed in successive iterations.
Finally, it can simultaneously achieve the clustering and obtain the desired
results for the registration of multi-view point sets.

In fact, Eq. (5) is the nearest neighbor (NN) search problem, which can be
efficiently solved by the search method based on k-d tree. After data
assignment, each cluster centroid can be directly calculated from all the
assigned points. Besides, Eq. (7) can be solved by the singular value
decomposition (SVD) method [45]. The main difficulty lies in the confirmation
of each binary variable $w_{ij}^{q}$. In the multi-view registration, the
$i$th point set covers some regions that other point sets cannot cover. If
these regions are used to update the rigid transformation for itself in Eq.
(7), the accuracy will go down. Therefore, these regions are invalid and
should be eliminated. As these regions are only covered by one point set, the
cluster lying in these regions would contain less points than other regions,
which may be covered by more than two point sets. Hence, we can confirm the
value of $w_{ij}^{q}$ according to the cardinality of the ${c^{q}}(ij)$th
cluster. Here, if the cardinality of the ${c^{q}}(ij)$th cluster is less than
four fifths of the mean value of all clusters, we set $w_{ij}^{q}=0$ so as to
eliminate the regions covered only by $i$th point set. Otherwise, we set
$w_{ij}^{q}=1$.

Based on the above description, our multi-view registration algorithm is
summarized in Algorithm 1. As seen, to efficiently register multiple point
sets, all points in the coarse reconstructed model should be clustered so as
to get the reasonable model comprised by the cluster centroids.

Algorithm 1 : Multi-view registration algorithm

Input: ${\Theta^{0}}=\\{{\mathbf{R}}_{i}^{0},\vec{t}_{i}^{0}\\}_{i=1}^{N}$,
$K$ ,$\\{{{\mathbf{P}}_{i}}\\}_{i=1}^{N}$

Get the initial model by Eq. (4);

Sample the centroids $\\{\vec{\mu}_{k}^{0}\\}_{k=1}^{K}$ from the initial
model;

$q=0$;

Repeat

$q=q+1$;

Do data assignment according to Eq. (5);

Update all cluster centroids according to Eq. (6);

for i= 2:N

Calculate $({\mathbf{R}}_{i}^{q},\vec{t}_{i}^{q})$ according to Eq. (7);

end

Until ( $\Theta$’s change is negligible) or ($q>Q$ )

Output: $\Theta=\\{{{\mathbf{R}}_{i}},{\vec{t}_{i}}\\}_{i=1}^{N}$

The only parameter that affects the performance of the algorithm is the number
of the clusters $K$, as discussed in Section 4.

###  3.3 Complexity

This section discusses the complexity of the proposed approach for
registration of multi-view point sets. Since our approach is proposed for
registering multiple point sets, the total number $M$ of points is the central
quantity. For the multi-view registration, the maximum value of clustering
iteration can be set as $Q$. At each iteration, four steps are executed to
estimate each transformation:

(1) Build the $k$-d tree. Before the estimation of all transformations, the
$k$-d tree should be built once from all $K$ cluster centroids for the point
assignment. This step results in a complexity of $O(K\log K)$.

(1) Assign each point to a single cluster. In this step, each point should be
assigned to the nearest cluster centroid. To accelerate the assignment, the
proposed approach utilizes the nearest neighbor search method based on the
$k$-d tree, which leads to a complexity of $O(M\log K)$.

(2) Update the centroids for all clusters. By sequentially traversing each
point, all the cluster centroids can be updated. Therefore, This step
introduces a complexity of $O(M)$.

(3) Sequentially estimate each rigid transformation. As shown in Eq. (7),
$M_{i}$ point pairs are used to estimate one rigid transformation, so the
estimation of $N$ rigid transformations can introduce a complexity of $O(M)$.

Since $N$ transformations are required to be estimated, the complexity of our
approach is shown in Table 1.

Table 1: Complexity of the different operations in each iteration of the proposed registration approach Operation | Complexity
---|---
Building k-d tree | $O(K\log K)$
Data assignment | $O(M\log K)$
Centroid update | $O(M)$
Transformation estimation | $O(M)$
Table 2: 3D scans used for evaluation | Bunny | Armadillo | Buddha | Dragon | Angel | Hand
---|---|---|---|---|---|---
Number of views ($N$) | 10 | 12 | 15 | 15 | 36 | 36
Total number of point ($M$) | 1362272 | 307625 | 1099005 | 469193 | 2347854 | 1065575

##  4 Experiments

To evaluate the performance of the proposed approach, a set of experiments
were conducted on six data-sets from the Stanford 3D Scanning Repository [46].
Table 2 displays some information of these data-sets, including the number of
views and total point number of each data-set. These data-sets contain the
multi-view point sets and the ground truth of transformations for their
registration. To reduce the runtime of multi-view registration, all the raw
point sets have been down-sampled by a factor $S=8$. For the comparison, the
error of rotation matrix and translation is here defined as
${E_{\mathbf{R}}}=\tfrac{1}{N}\sum\nolimits_{i=1}^{N}{{{\left\|{{{\mathbf{R}}_{i,m}}-{{\mathbf{R}}_{i,g}}}\right\|}_{F}}}$
and
${E_{\vec{t}}}=\tfrac{1}{N}\sum\nolimits_{i=1}^{N}{{{\left\|{{{\vec{t}}_{i,m}}-{{\vec{t}}_{i,g}}}\right\|}_{2}}}$,
where $({{\mathbf{R}}_{i,g}},{\vec{t}_{i,g}})$ denotes the ground truth of the
$i$th rigid transformation and $({{\mathbf{R}}_{i,m}},{\vec{t}_{i,m}})$
indicates the one estimated by the multi-view registration approach.

During experiments, the maximum step for clustering was set as $Q=500$. All
the baselines adopted the nearest-neighbor search method based on $k$-d tree
to establish point correspondences and were implemented in MATLAB. To produce
unregistered point sets, we randomly perturb the ground trough
transformations. Experiments were performed on a four-core 3.6 GHz computer
with 8 GB of memory.

###  4.1 Choice of $K$

The number of cluster centers $K$ seems to affect the performance of multi-
view registration. The actual number of the clusters is unknown and may vary
with the data set to be registered.

We conducted a group of experiments on Stanford Armadillo with different down-
sampling factor $S$. To provide the initial registration parameters, a fixed
perturbation was added to the ground-truth transformations of multi-view
registration. Then, the proposed approach was tested with the number of
cluster centers $K$ varying from $500$ to $3500$. To eliminate the randomness,
$20$ Monte Carlo (MC) trials were conducted with respect to each value of $K$.
Fig. 2 shows comparison results of the proposed approach under different
values of $K$.

Figure 2:  Mean error and run time of the proposed approach tested on
Armadillo with different values of $K$. (a) Rotation error. (b) Translation
error. (c) Runtime.

As shown in Fig. 2, the minimum rotation error is obtained for the range
$[1000,1500]$ of $K$ for all down-sampling factors. The translation error
decreases with the increase of the number of cluster centers $K$, while it may
increase again after $K=3500$. The run time obviously increases with $K$.
While a large value of $K$ might be better for accuracy reasons, a small value
of $K$ leads to a more efficient registration. By the consideration of these
two factors, we set $K=1500$ in the experiments below for the proposed
registration algorithm.

Figure 3: Comparison of different strategies for dealing with the invalid
cluster centroids

###  4.2 Validation

As mentioned before, the reconstructed model is comprised by the cluster
centroids, which are initially sampled from all the aligned point sets. Since
each point set covers some regions that other point sets cannot cover, the
proposed approach suggests that these regions should be eliminated to estimate
the rigid transformation of this point set itself. To verify the effectiveness
of this strategy, we compare the proposed approach with and without
elimination of the invalid cluster centroids, which are abbreviated as
KmeansReg and KmeansRegWOE (Kmeans Registration Without Elimination),
respectively. They were tested on Stanford Bunny and Armadillo under different
perturbation levels, where five uniform distributed noises were added to
ground-truth transformations, respectively. To eliminate the randomness, $10$
MC trials were conducted with respect to five perturbation levels. Fig. 3
illustrates the mean of rotation error, translation error and the mean run
time of the two different strategies.

Table 3: Comparison of accuracy and runtime for different approaches Dataset |  | Initial |  CFTrICP [33] |  MATrICP [38] |  LRS [42] |  JRMPC [43] | Ours
---|---|---|---|---|---|---|---
Bunny | ${E_{\mathbf{R}}}$ | 0.0360 | 0.0032 | 0.0086 | 0.0082 | 0.0163 | 0.0111
${E_{\vec{t}}(\times{10^{-3}})}$ | 2.5211 | 0.4181 | 0.4176 | 0.6115 | 1.9902 | 1.1439
| T(min) | – | 1.0828 | 0.3380 | 0.9327 | 7.7482 | 0.2207
Armadillo | ${E_{\mathbf{R}}}$ | 0.0375 | 0.0077 | 0.1088 | 0.0650 | 0.0207 | 0.0049
${E_{\vec{t}}(\times{10^{-3}})}$ | 4.5276 | 0.7717 | 7.8606 | 7.4092 | 0.8416 | 2.1517
T(min) | – | 0.7941 | 3.8178 | $>10$ | 6.9728 | 0.1426
Buddha | ${E_{\mathbf{R}}}$ | 0.0334 | 0.0333 | 0.0107 | 0.0310 | 0.0213 | 0.1320
${E_{\vec{t}}(\times{10^{-3}})}$ | 2.7316 | 2.1410 | 1.0994 | 1.4452 | 0.7771 | 1.8696
T(min) | – | $>10$ | 2.0492 | 4.8167 | $>10$ | 0.7671
Dragon | ${E_{\mathbf{R}}}$ | 0.0439 | 0.0429 | 0.2770 | 0.2539 | 0.0164 | 0.0106
${E_{\vec{t}}(\times{10^{-3}})}$ | 5.6432 | 3.8421 | 39.6289 | 36.3570 | 1.2654 | 2.5963
T(min) | – | 7.6386 | 3.2058 | $>10$ | $>10$ | 0.3042
Angel | ${E_{\mathbf{R}}}$ | 0.0382 | 0.0305 | 0.0022 | 0.0072 | 0.0105 | 0.0045
${E_{\vec{t}}(\times{10^{-3}})}$ | 184.7460 | 410.3960 | 51.8375 | 72.2118 | 66.2194 | 94.2439
T(min) | – | $>10$ | 7.7475 | $>10$ | $>10$ | 2.2303
Hand | ${E_{\mathbf{R}}}$ | 0.0423 | 0.0518 | 0.0712 | 0.0569 | 0.0175 | 0.0097
${E_{\vec{t}}(\times{10^{-3}})}$ | 227.1540 | 153.5512 | 261.3473 | 206.0000 | 96.6633 | 85.8901
T(min) | – | $>10$ | $>10$ | $>10$ | $>10$ | 1.3036

As shown in the Fig. 3, the proposed approach without elimination of the
invalid cluster centroids can always obtain the less accurate registration
results under varied noise levels for different data-sets. This is because the
pair-wise registration of two identical point sets can only obtain the
identity matrix. Since the $i$th rigid transformation should be estimated by
aligning the $i$th point set to the model comprised by all the cluster
centroids, these cluster centroids located in the regions only covered by the
$i$th point set should be eliminated. Otherwise, the registration accuracy
drops. Therefore, the proposed approach with elimination of the invalid
cluster centroids can obtain more accurate registration results. Besides, the
execution time of these two strategies are approximately equal. As a result,
it is reasonable to discard the invalid cluster centroids so as to accurately
estimate the transformations.

Figure 4: Cross-section of multi-view registration results

###  4.3 Comparison

We here compare the proposed algorithm against four state-of-the-art
approaches: the coarse-to-fine TrICP approach [33], the motion averaging TrICP
approach [38], the approach based on the low-rank and sparse decomposition
[42] as well as the joint registration approach [43], which are abbreviated as
CFTrICP, MATrICP, LRS, and JRMPC, respectively. Results are reported in run
time, the error of rotation matrix and translation.

####  4.3.1 Accuracy and efficiency

As the locally convergent registration approaches,all these five approaches
require the initial registration parameters. As mentioned, initial
registration parameters were generated by perturbing the ground truth of rigid
transformations with some noise. Subsequently, all the competed approaches
start from the same initial parameters for the registration of multi-view
point sets. For comparison, Table 3 shows the registration error and runtime
of all competed approaches for different data sets, where the bold number
denotes the best performance.To evaluate the registration accuracy in a more
intuitive way, Fig. 4 displays the multi-view registration results in the form
of cross-section.

As shown in Table 3, the proposed approach is the most efficient one among
these competed approaches. Although JRMPC is also a clustering based
registration approach, it is more time-consuming than the proposed approach
owing to the soft assignment strategy and to the larger number of parameters
that need estimating. Note that, the proposed approach only requires to
establish correspondences between each point set and the model comprised by
the cluster centroids. More specifically, it only requires to assign a single
cluster centroid to one point in each point set. While, the CFTrICP should
establish correspondences between each point set and the model constructed by
other aligned point sets. Besides, both MA-TrICP and LRS should establish
correspondences between point set pairs, which contains certain percentage of
overlaps. Since the number of the cluster centroids are much less than the
number of point involved in multi-view registration, the establishment of
correspondences, which is the most time-consuming operation in the multi-view
registration, is much faster in the proposed approach.

As shown in Table 3 and Fig. 4, the proposed approach is not very sensitive to
noises and it can always obtain acceptable accuracy compared to other
baselines. Since the proposed approach utilizes the model comprised by all
cluster centroids for the estimation of each transformation, the resolution of
this model is much lower than the model constructed by raw point sets.
Therefore, the proposed approach may not always obtain the most accurate
registration results. But other competed approaches may fail to achieve the
multi-view registration without good registration parameters. Therefore, the
proposed approach is comparable to other state-of-the-art approaches in terms
of accuracy.

####  4.3.2 Robustness

Table 4: Robustness comparison under varied noise levels Terms |  |  CFTrICP [33] |  MATrICP [38] |  LRS [42] |  JRMPC [43] | Ours
---|---|---|---|---|---|---
[-0.01,0.01] | ${E_{\mathbf{R}}}$ | 0.0106 | 0.0745 | 0.0507 | 0.0093 | 0.0061
${E_{\vec{t}}(\times{10^{-3}})}$ | 0.8539 | 4.9418 | 6.7188 | 2.1287 | 2.0236
T(min) | 1.0482 | 1.5948 | 4.6892 | 6.9014 | 0.1612
[-0.02,0.02] | ${E_{\mathbf{R}}}$ | 0.0428 | 0.1157 | 0.0566 | 0.0156 | 0.0092
${E_{\vec{t}}(\times{10^{-3}})}$ | 2.3353 | 7.5286 | 7.0797 | 2.5197 | 2.3219
T(min) | 1.3056 | 1.6660 | 7.9593 | 6.9335 | 0.1717
[-0.03,0.03] | ${E_{\mathbf{R}}}$ | 0.0676 | 0.1450 | 0.0627 | 0.0259 | 0.0159
${E_{\vec{t}}(\times{10^{-3}})}$ | 2.8578 | 8.6094 | 7.1143 | 3.1651 | 2.6353
T(min) | 1.7885 | 1.7847 | 8.6718 | 6.9945 | 0.2475
[-0.04,0.04] | ${E_{\mathbf{R}}}$ | 0.0845 | 0.1523 | 0.0636 | 0.0664 | 0.0438
${E_{\vec{t}}(\times{10^{-3}})}$ | 4.5926 | 8.6997 | 7.3976 | 6.0247 | 3.2839
T(min) | 1.7990 | 1.8480 | 10.1937 | 7.0830 | 0.3005

Figure 5: Mean error and standard Deviation with respect to different noise
levels

To further verify its robustness, the proposed approach was tested on Stanford
Armadillo under different transformation noise levels, where values sampled
from five uniform distributions were added to ground-truth transformations,
respectively. To eliminate the randomness, $10$ MC trials were conducted with
respect to five noise distributions for all competed approaches. Table 4 shows
the average of rotation error, the average of translation error, and the
average run time for these approaches. To compare the robustness in a more
intuitive way, Fig. 5 displays the mean error and the corresponding standard
deviation for these approaches.

As shown in Table 4 and Fig. 5, the proposed approach can obtain the most
robust registration results under varied initial registration. With the
increase of noise level, the registration errors of the proposed approach
increase gradually and its standard deviation is always small. Although the
CFTrICP and JRMPC perform well under low noise levels, their registration
error raises at higher noise levels. Besides, the standard deviation of the
CFTrICP increases sharply with the noise levels. Meanwhile, both MATrICP and
LRS approaches have difficulties to obtain accurate registration for the
Stanford Armadillo under all noise levels. Therefore, the proposed approach
seems to be the most robust one among all the competed approaches. Besides,
its run time is far less than other three competed approaches.

##  5 Conclusion

This paper proposes a novel approach for registration of multi-view point
sets. To the best of our knowledge, it is the first time applying the K-means
clustering to the multi-view registration problem. The proposed approach has
been tested on the Stanford 3D Scanning Repository and the experimental
results demonstrate that it can achieve the multi-view registration of
initially posed point sets with good efficiency and robustness. Similar to
most of the related approaches, the proposed approach requires initial
parameters for the multi-view registration.

Our future work will investigate how to estimate the initial rigid
transformations so as to automatically achieve the multi-view registration of
unordered point sets without any prior information.

## Acknowledgment

This work is supported by the National Natural Science Foundation of China
under Grant nos. 61573273, 61573280 and 61503300. We would like to thank
Federica Arrigoni for providing the MATLAB implementation of [42].

## Reference

## References

  * [1] T. Shiratori, J. Berclaz, M. Harville, C. Shah, T. Li, Y. Matsushita, S. Shiller, Efficient large-scale point cloud registration using loop closures, in: 3D Vision (3DV), 2015 International Conference on, IEEE, 2015, pp. 232–240.
  * [2] J. Yang, H. Li, D. Campbell, Y. Jia, Go-icp: a globally optimal solution to 3d icp point-set registration, IEEE transactions on pattern analysis and machine intelligence 38 (11) (2016) 2241–2254.
  * [3] W. Liu, Z. Lan, Y. Zhang, Z. Zhang, H. Zhao, F. Ye, X. Li, Global data registration technology based on dynamic coded points, IEEE Transactions on Instrumentation and Measurement 67 (2) (2018) 394–405.
  * [4] A. Dai, M. Nießner, M. Zollhöfer, S. Izadi, C. Theobalt, Bundlefusion: Real-time globally consistent 3d reconstruction using on-the-fly surface reintegration, ACM Transactions on Graphics (TOG) 36 (3) (2017) 24.
  * [5] D. Aiger, N. J. Mitra, D. Cohen-Or, 4-points congruent sets for robust pairwise surface registration, Acm Transactions on Graphics 27 (3) (2008) 1–10.
  * [6] F. Yu, J. Xiao, T. Funkhouser, Semantic alignment of lidar data at city scale, in: Computer Vision and Pattern Recognition (CVPR), 2015 IEEE Conference on, IEEE, 2015, pp. 1722–1731.
  * [7] L. Ma, J. Zhu, L. Zhu, S. Du, J. Cui, Merging grid maps of different resolutions by scaling registration, Robotica 34 (11) (2016) 2516–2531.
  * [8] P. J. Besl, N. D. McKay, Method for registration of 3-d shapes, in: Sensor Fusion IV: Control Paradigms and Data Structures, Vol. 1611, International Society for Optics and Photonics, 1992, pp. 586–607.
  * [9] D. Chetverikov, D. Stepanov, P. Krsek, Robust euclidean alignment of 3d point sets: the trimmed iterative closest point algorithm, Image and Vision Computing 23 (3) (2005) 299–309.
  * [10] J. M. Phillips, R. Liu, C. Tomasi, Outlier robust icp for minimizing fractional rmsd, in: 3-D Digital Imaging and Modeling, 2007. 3DIM’07. Sixth International Conference on, IEEE, 2007, pp. 427–434.
  * [11] C. Langis, M. Greenspan, G. Godin, The parallel iterative closest point algorithm, in: 3-D Digital Imaging and Modeling, 2001. Proceedings. Third International Conference on, IEEE, 2001, pp. 195–202.
  * [12] S. Granger, X. Pennec, Multi-scale em-icp: A fast and robust approach for surface registration, in: European Conference on Computer Vision, Springer, 2002, pp. 418–432.
  * [13] B. Jian, B. C. Vemuri, Robust point set registration using gaussian mixture models, IEEE Transactions on Pattern Analysis and Machine Intelligence 33 (8) (2011) 1633–1645.
  * [14] A. Myronenko, X. Song, Point set registration: Coherent point drift, IEEE transactions on pattern analysis and machine intelligence 32 (12) (2010) 2262–2275.
  * [15] Y. Tsin, T. Kanade, A correlation-based approach to robust point set registration, in: European conference on computer vision, Springer, 2004, pp. 558–569.
  * [16] R. Sandhu, S. Dambreville, A. Tannenbaum, Point set registration via particle filtering and stochastic dynamics, IEEE transactions on pattern analysis and machine intelligence 32 (8) (2010) 1459–1473.
  * [17] I. Kolesov, J. Lee, G. Sharp, P. Vela, A. Tannenbaum, A stochastic approach to diffeomorphic point set registration with landmark constraints, IEEE transactions on pattern analysis and machine intelligence 38 (2) (2016) 238–251.
  * [18] E. Lomonosov, D. Chetverikov, A. Ekárt, Pre-registration of arbitrarily oriented 3d surfaces using a genetic algorithm, Pattern Recognition Letters 27 (11) (2006) 1201–1208.
  * [19] J. Zhu, D. Meng, Z. Li, S. Du, Z. Yuan, Robust registration of partially overlapping point sets via genetic algorithm with growth operator, IET Image Processing 8 (10) (2014) 582–590.
  * [20] R. B. Rusu, N. Blodow, M. Beetz, Fast point feature histograms (fpfh) for 3d registration, in: Robotics and Automation, 2009. ICRA’09. IEEE International Conference on, IEEE, 2009, pp. 3212–3217.
  * [21] H. Lei, G. Jiang, L. Quan, Fast descriptors and correspondence propagation for robust global point cloud registration, IEEE Transactions on Image Processing 26 (8) (2017) 3614–3623.
  * [22] Z. Lou, T. Gevers, Image alignment by piecewise planar region matching, IEEE Transactions on Multimedia 16 (7) (2014) 2052–2061.
  * [23] M. J. Ren, L. J. Sun, M. Y. Liu, C. F. Cheung, Y. H. Yin, A reconstruction–registration integrated data fusion method for measurement of multiscaled complex surfaces, IEEE Transactions on Instrumentation and Measurement 66 (3) (2017) 414–423.
  * [24] D. F. Huber, M. Hebert, Fully automatic registration of multiple 3d data sets, Image and Vision Computing 21 (7) (2003) 637–650.
  * [25] A. S. Mian, M. Bennamoun, R. Owens, Three-dimensional model-based object recognition and segmentation in cluttered scenes, IEEE transactions on pattern analysis and machine intelligence 28 (10) (2006) 1584–1601.
  * [26] J. Zhu, L. Zhu, Z. Li, C. Li, J. Cui, Automatic multi-view registration of unordered range scans without feature extraction, Neurocomputing 171 (2016) 1444–1453.
  * [27] S. Fantoni, U. Castellani, A. Fusiello, Accurate and automatic alignment of range surfaces, in: 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT), 2012 Second International Conference on, IEEE, 2012, pp. 73–80.
  * [28] Y. Guo, F. Sohel, M. Bennamoun, J. Wan, M. Lu, An accurate and robust range image registration algorithm for 3d object modeling, ieee transactions on multimedia 16 (5) (2014) 1377–1390.
  * [29] Y. Guo, M. Bennamoun, F. Sohel, M. Lu, J. Wan, An integrated framework for 3-d modeling, object detection, and pose estimation from point-clouds, IEEE Transactions on Instrumentation and Measurement 64 (3) (2015) 683–693.
  * [30] Y. Chen, G. Medioni, Object modelling by registration of multiple range images, Image and vision computing 10 (3) (1992) 145–155.
  * [31] R. Bergevin, M. Soucy, H. Gagnon, D. Laurendeau, Towards a general multi-view registration technique, IEEE Transactions on Pattern Analysis and Machine Intelligence 18 (5) (1996) 540–547.
  * [32] K. Pulli, Multiview registration for large data sets, in: 3-D Digital Imaging and Modeling, 1999. Proceedings. Second International Conference on, IEEE, 1999, pp. 160–168.
  * [33] J. Zhu, Z. Li, S. Du, L. Ma, T. Zhang, Surface reconstruction via efficient and accurate registration of multiview range scans, Optical Engineering 53 (10) (2014) 102104.
  * [34] G. C. Sharp, S. W. Lee, D. K. Wehe, Multiview registration of 3d scenes by minimizing error between coordinate frames, IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (8) (2004) 1037–1050.
  * [35] S.-W. Shih, Y.-T. Chuang, T.-Y. Yu, An efficient and accurate method for the relaxation of multiview registration error, IEEE Transactions on Image Processing 17 (6) (2008) 968–981.
  * [36] A. Torsello, E. Rodola, A. Albarelli, Multiview registration via graph diffusion of dual quaternions, in: Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, IEEE, 2011, pp. 2441–2448.
  * [37] V. M. Govindu, Lie-algebraic averaging for globally consistent motion estimation, in: Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, Vol. 1, IEEE, 2004, pp. I–I.
  * [38] V. M. Govindu, A. Pooja, On averaging multiview relations for 3d scan registration, IEEE Transactions on Image Processing 23 (3) (2014) 1289–1302.
  * [39] Z. Li, J. Zhu, K. Lan, C. Li, C. Fang, Improved techniques for multi-view registration with motion averaging, in: 3D Vision (3DV), 2014 2nd International Conference on, Vol. 1, IEEE, 2014, pp. 713–719.
  * [40] V. M. Govindu, Robustness in motion averaging, in: Asian Conference on Computer Vision, Springer, 2006, pp. 457–466.
  * [41] D. S. Pankaj, R. R. Nidamanuri, Robust algorithm for multiview registration, IET Computer Vision 11 (1) (2016) 96–103.
  * [42] F. Arrigoni, B. Rossi, A. Fusiello, Global registration of 3d point sets via lrs decomposition, in: European Conference on Computer Vision, Springer, 2016, pp. 489–504.
  * [43] G. D. Evangelidis, R. Horaud, Joint alignment of multiple point sets with batch and incremental expectation-maximization, IEEE transactions on pattern analysis and machine intelligence.
  * [44] H. Zhou, Y. Liu, Accurate integration of multi-view range images using k-means clustering, Pattern Recognition 41 (1) (2008) 152–175.
  * [45] J. Zhu, D. Wang, X. Bai, H. Lu, C. Jin, Z. Li, Registration of point clouds based on the ratio of bidirectional distances, in: 3D Vision (3DV), 2016 Fourth International Conference on, IEEE, 2016, pp. 102–107.
  * [46] M. Levoy, J. Gerth, B. Curless, K. Pull, The stanford 3d scanning repository, URL http://www-graphics. stanford. edu/data/3dscanrep.