Robust Simultaneous 3D Registration via Rank Minimization
Diego Thomas
National Institute of Informatics
Tokyo, Japan / JFLI, CNRS

Yasuyuki Matsushita
Microsoft Research Asia
Beijing, China

Akihiro Sugimoto
National Institute of Informatics
Tokyo, Japandiego thomas@nii.ac.jp

yasumat@microsoft.com

sugimoto@nii.ac.jp

Abstract
We present a robust and accurate 3D registration method
for a dense sequence of depth images taken from unknown
viewpoints. Our method simultaneously estimates multiple
extrinsic parameters of the depth images to obtain a registered full 3D model of the scanned scene. By arranging
the depth measurements in a matrix form, we formulate theproblem as a simultaneous estimation of multiple extrinsics
and a low-rank matrix, which corresponds to the aligned
depth images as well as a sparse error matrix. Unlike previous approaches that use sequential or heuristic global registration approaches, our solution method uses an advanced
convex optimization technique for obtaining a robust solution via rank minimization. To achieve accurate computation, we develop a depth projection method that has minimum sensitivity to sampling by reading projected depth values in the input depth images. We demonstrate the effectiveness of the proposed method through extensive experiments
and compare it with previous standard techniques.

Figure 1: Illustration of the problem setting. A static scene
is densely observed from a continuously varying viewpoint.
From each viewpoint, a depth image is obtained. Our goal
is to simultaneously register the observed depth images.
A wide class of 3D registration techniques focus on pairwise registration due to the heavy computational complexity of simultaneous registration, especially when the number of input depth images becomes large. With these techniques, however, the error of the independent pair-wise registration accumulates, which leads to significant global misalignment. Even though bundle adjustment or other heuristic global methods have been used for refining the registration result, fewer studies have been done on simultaneously
registering multiple depth images.
In this work, we consider the situation depicted in Fig. 1.
A static scene is densely scanned from an unknown continuous camera path, which gives a dense sequence of depth
images (e.g., a Kinect sensor recording VGA depth images
at 30 fps). The camera intrinsics are assumed to be known
and unchanged during the acquisition, while its extrinsics
are unknown. The objective is then to align all the input
depth images with each other simultaneously. Equivalently,
we search for all the camera extrinsics that best align all
depth images with a common cloud of points. The samesetting is presented in KinectFusion [13], where video-rate
3D modeling results are shown. While their work focuseson efficient sequential registration for achieving real-time

1. Introduction
Automatic 3D registration from a set of depth images has
a long history yet is still a challenging problem in computer
vision. Early approaches to 3D registration have been developed for range data that are acquired from sparse viewpoints because the task of depth scanning has been expensive. Recently, a significant effort has been made to develop inexpensive consumer depth cameras that allow theacquisition of depth images at a video rate, e.g., Microsoft
Kinect [1]. The video-rate depth cameras are becoming acommodity tool for depth measurement with reasonable accuracy. Such a depth camera brings a new problem settingfor 3D registration; registering a dense set of depth images
taken from continuously varying viewpoints. Since mostof the existing registration techniques are not designed for
dense sets of depth images, it is desirable to have a newtechnique for robustly, efficiently, and simultaneously registering multiple depth images taken from dense viewpoints.
1

scanning, we are interested in robust, and accurate simultaneous registration that is designed as an offline process.
To achieve the goal of simultaneous registration of adense set of depth images, we develop a method based on arank minimization strategy. We cast the problem of aligning a set of overlapping depth images as a problem of recovering a low-rank component from a high dimensional
observation matrix. By stacking the depth images transformed to our reference coordinates using the extrinsics as
a column vector in the high dimensional matrix, we formulate the problem as a simultaneous estimation of all the
extrinsics and a low-rank matrix, which corresponds to thealigned depth images, as well as a sparse error matrix. The
approach is motivated by previous work of Peng et al. [19],called RASL, which performs robust 2D image alignment
from multiple images.
Estimating all the extrinsics that relate all depth images
together cannot be simply achieved by applying RASL in astraightforward manner. Two major difficulties arise whensimultaneously registering multiple depth images. Firstly,
in contrast to 2D image alignment, we search for 2D to 3D
transformations that align all depth images to a global point
cloud. Accordingly, we have to formulate the relationshipbetween the observation matrix we use and the 3D transformations that we want to estimate. Secondly, when registering depth images, a depth value itself changes with thecamera pose while the 2D image case preserves the pixel intensity values. In other words, when the same scene point isobserved, the depth value is dependent on the camera pose,
while the intensity is not if a Lambertian scene is assumed.
In this work, we explicitly formulate the problem of simultaneously registering multiple depth images and propose asolution method for it.

2. Related work
While successful attempts to simultaneously register
multiple 2D images have been made, a large amount of 3D
registration methods focus on pair-wise alignment. In general, pair-wise registration methods can be divided into two
categories: (1) ones that use a sparse set of point correspondences, which we call sparse feature-based methods, and (2)ones that use a dense set of point correspondences, which
we call dense correspondence methods.
Sparse feature-based methods, like SIFT [16] and its
variants [4, 6, 25], are known to be fast and efficient, butwith limited accuracy. In these techniques, sets of keypoints are first detected, and a discriminative descriptor
is attached to each key-point. Then, the detected keypoints are matched across the range images to estimate
the best transformation using various approaches, such as
RANSAC [8], entropy maximization [15], or expectation
maximization [12].
The Iterative Closest Point (ICP) method [5] is a con-ventional method that uses a dense set of point correspondences, where each point in one scan is matched with its
closest point in the other scan to obtain dense correspondences. Various extensions have been developed [13, 24,
28, 30, 31] for improving the computational cost and accuracy. Different metrics such as point-to-point [5], or pointto-plane metrics [22] can be used to select the closest points,
and various outlier rejection strategies, such as reciprocity
or rigidity, are used to improve registration results. While
the ICP-based methods are in general accurate, they alsopresent some limitations. One of the major problems is thatpoint matches are computed independently. As a result, theobtained cost function includes an accumulation of local errors, which often makes the function trapped into a local
minima when the scene presents multiple symmetries.
For registering multiple depth images, there are pairwise and simultaneous approaches. In general, pair-wiseregistration of multiple depth scans can be further divided
into two categories: (1) methods that use a frame-to-frame
approach [9, 28]; (2) methods that use a frame-to-globalmodel approach [13, 17, 27]. In the first category, Weise etal. [28] combine geometric and texture registration methods to align pairs of successive frames. Cui et al. [9]propose to combine registration and super-resolution methods. From an initial estimate of the alignment obtainedusing SLAM [10], super-resolution depth images are obtained [20, 21], which are then aligned using a non-rigid
registration method with a mixture of Gaussians [14]. The
final position of each camera can then be obtained by combining multiple pair-wise transformations. In the latter category, Izadi et al. [13] use a framework where live depthscans are registered to a global model of the 3D scene.
After aligning all input depth scans, various heuristic approaches are used to correct propagated errors. For example, Torsello et al. [26] develop an algorithm that uses projection of pair-wise alignments onto a reference frame anddiffusion along a graph of adjacent nodes. Sharp et al. [23]propose to distribute the accumulated errors using an optimization strategy over the graph of neighboring views.
When a loop in the input depth scans sequence is available, additional loop closure adjustment methods [29, 13]
are used to correct the propagated errors, sometimes at thecost of global deformations in the final 3D model.
Extensions of the ICP algorithm [11, 18] have been proposed for simultaneous registration of multiple range images. However, handling multiple range images simultaneously dramatically increase the computational time. As
pointed out in [11] it takes O(nb2im N log(N )) operations
to find all point correspondences across nbim range images
with N points each. Such methods are thus unpracticalwhen aligning a dense sequence of range images.
Our method is motivated by recent advances in the robust principal component analysis (RPCA) [7]. Based on

RPCA, Peng et al. [19] proposed a method called RASL,
which performs robust simultaneous 2D alignment of multiple images. Motivated by these previous works, we develop a robust simultaneous 3D alignment method that does
not require computing matches through all input images,
but takes advantage of advanced convex optimization techniques. While the extension of the previous method to the
3D registration is not straightforward, we develop a solution method that effectively takes into account the 3D to 2D
projections and handles issues that arise in 3D registration.

3. Proposed method

The depth images {dk }k∈[1:n] and the intrinsics matrix K
are given as input. We aim at estimating the extrinsics matrices Tk , or equivalently, estimating the aligned points Xk .
For a reference viewpoint1 ref with the extrinsics matrix Tref = I, we can compute re-projected depth imagesd(ref,k) by projecting scene points Xk that are visible fromthe k-th view to the reference coordinates byd(ref,k) (H −1 (Kρ(P(ref,k) (u, v)))> ) = z(P(ref,k) (u, v)),

where
−1
P(ref,k) (u, v) = H −1 (Tref
H(Xk (u, v))) = Xk (u, v).

Our method takes a dense sequence of depth images
recorded with unknown camera motion. We assume thatthe depth images of our input share a common overlapping
region of the scene. We start with an initial guess of thecamera extrinsics, and all depth measurements are projectedto the reference camera coordinates. With this setting, ourmethod finds extrinsics that align depth images in a simultaneous manner using a rank minimization strategy.

When all points of Xk are well estimated, all the depth images d(ref,k) become well aligned up to occlusions, missing data, and data noise. By substituting Xk (u, v) withH −1 (Tk H(Pk (u, v))) we can then write:

3.1. Notation

Therefore, d(ref,k) becomes a function of Tk . Now
we use a compact representation τk for denoting thesix extrinsic parameters of Tk , which are {Rx , Ry , Rz ,Tx , Ty , Tz }. We denote τ = τ1 , . . . , τn , and vec thevectorizing operator that only serializes pixels of the reprojected depth image that have a valid depth measurement in all the re-projected depth images. To compute
this, we use a binary mask, which is computed as an intersection of valid entries of all the re-projected depth images. Therefore, the vectorizing operator depends on thecurrent estimates of the extrinsics. We then denote D(τ ) =[vec(d(ref,1) , τ ), . . . , vec(d(ref,n) , τ )] the matrix of all reprojected depth images in the vectorized form. Derivinga closed-form expression of the operator vec is difficult;therefore, we use a procedural approach to compute this.
As done in [19], the problem that we want to solve can thenbe re-written, with a trade-off parameter α, asWe represent the 6-DOF camera extrinsics estimated forthe k-th depth image dk as a rigid transformation matrix:
Rk t kTk = >∈ SE3
0
1
where the Euclidean group SE3 := {R, t|R ∈ SO3 , t ∈R3 }. This maps the k-th local coordinates to the global coordinates. We will also use a single constant camera intrinsic matrix K ∈ R3×3 that transforms points on the sensor
plane to image pixels.
Let us denote by ρ a function that performs projection
onto the sensor plane of w = (x, y, z)> ∈ R3 to obtain its
projection on the image plane wp = (u, v, 1)> ∈ R3 by
wp = ρ(w). The function ρ−1 performs the inverse projection: w = ρ−1 (wp , z). We will also use the function H todenote a homogeneous operator H(u) := (u> |1)> , and thereverse dehomogenization operator H −1 ((u> |1)> ) := u.
By a little bit of notation abuse, we will denote the zcomponent of a vector w as z(w).

3.2. Problem formulation
Let us consider n depth images that have a common
overlapping region in the scene. We are interested in finding camera extrinsics that correspond to the depth measurements. A pixel q = (u, v)> has its corresponding 3D points
Pk (u, v) = ρ−1 (K −1 H(q), dk (u, v)) (k = 1, . . . , n) in
the local coordinates, where dk denotes the k-th depth image. Each point Pk (u, v) is related to the corresponding
visible scene point Xk (u, v) ∈ R3 in the global coordinate
system, by
Pk (u, v) = H −1 (Tk−1 H(Xk (u, v))).

d(ref,k) (H −1 (Kρ(P(ref,k) (u, v)))> ) =z(H −1 (Tk H(Pk (u, v)))).

(1)min (rank(A) + αkEk0 ) s.t. A + E = D(τ ),A,E,τ

where matrix A represents the aligned depth images andmatrix E represents sparse errors or occlusions.
Since both rank minimization and `0 -norm minimization
are NP-hard, in practice, we use2 k · k∗ instead of rank(·),
and k · k1 for k · k0 as done by the Principle Component Pursuit method [7] because of the non-convexity of the original problem. In addition, to deal with the non-linearity of
the constraint A + E = D(τ ), we use a local linearization
D(τ + ∆τ ) = D(τ ) + J∆τ with the Jacobian matrix J of
D w.r.t. the transformations τ , as done in [19]. This leads to
1 The choice of the reference viewpoint is arbitrary. In our case, wechoose the middle one ref = n.
2
Pn−1
2 kAk =
th singular value of A.
∗
i=0 σi (A), where σi (A) is the ithe following convex optimization problem with unknowns
A, E, and τ :minA,E,∆τ

1
kAk∗ + √ kEk1
m


s.t. A+E = D(τ )+J∆τ, (2)where the weight α is set to √1m , and m is a number of linesin D(τ ).
As shown in [19], the relaxation we used is the mostappropriate, and the algorithm ensures convergence at a
non-empty solution with a reasonable initialization.To efficiently solve Eq. (2), we use the adapted Augmented Lagrange Multiplier (ALM), as recommended by [19].
The main difficulty in depth image alignment arises
when actually solving Eq. (2). Unlike the 2D image alignment case, the behavior of the function D(τ ) becomes complex in 3D registration, and so is the problem of solving
Eq. (2). This is (i) because the projection operator exhibited in Eq. (1) exists, (ii) because the depth of a point varies
depending on the transformation τ , and (iii) because the adjacency relationship between pixels in a depth image varies
depending on the transformation τ , due to occlusions. As
a consequence, the Jacobian J cannot be computed analytically but needs to be obtained procedurally. Therefore, forour problem, accurate and rapid computation of J becomes
fairly important. For this, we develop an efficient projection method to synthesize depth images from current estimates of τ , which allows accurate and fast computation of
the Jacobian J using the finite difference method. We will
describe this in the next section.

3.3. Projection of Depth Images
We develop an efficient projection method that has minimal sensitivity to the surface sampling. Our method takes
depth images and extrinsics matrices as input and performs
projection to a virtual camera image plane with respect tothe reference depth image dref . The key idea is to computedepth values of pixels in the virtual camera image plane byinterpolating depth values in the input depth images.
Let us assume a virtual camera cam. First, we generate
the cloud of points Pref from the reference depth image
dref using the intrinsics K. Pref is then projected onto thevirtual camera image plane to obtain the depth image dcam
ref
−1
−1
(Kcam ρ(H −1 (Tcam(dcam
Tref H(Pref (u, v))))) =ref (H−1z(H −1 (Tcam
Tref H(Pref (u, v))))). The cloud of points
camPref is generated from dcam
ref using the intrinsics of cam.
For each depth image dk , the projected image dcam
(ref,k)is computed as follows. For each pixel (u, v)> of dcam
refthat has a valid depth, the pixel location (u0 , v 0 ) of thepoint Pcam
ref (u, v) for the depth image dk is computed using
the intrinsics and current extrinsics K and Tk ((u0 , v 0 ) =>H −1 (Kρ(H −1 (Tk−1 Tcam H(Pcam
ref (u, v))))) ). The cor0 0
responding depth dk (u , v ) is estimated using bi-linear
interpolation of the depth values in dk . We finallycompute the corresponding 3D point coordinates p0 =H −1 (Tk H(ρ−1 (H −1 (K −1 (u0 , v 0 , 1)> ), dk (u0 , v 0 )))) andtransform it back to the local 3D coordinate system of cam−1
p = H −1 (Tcam
H(p0 )) to obtain the depth of dcam
(ref,k) for>cam
the pixel (u, v) (d(ref,k) (u, v) = z(p)). The overall procedure is illustrated in Fig. 2. Note that if a pixel (u, v)> of>dcam
ref does not have a valid depth, then the pixel (u, v) of
camd(ref,k) does not have a valid depth neither.
We use varying poses of virtual cameras for registering a
set of depth images to avoid local minima that produce incoherent alignments in different viewpoints3 . Typically, thevirtual cameras are positioned at the front, left, and right of
the reference camera. Note that the virtual camera’s fieldof view needs to contain an overlapping area with all input
depth images. The registration is then performed by iteratively aligning the depth images with respect to these virtual
cameras.
The main advantage of computing the re-projected depth
images in this way is that the accuracy of the projection
is not limited by the sampling resolution of the depth images. On the other hand, one drawback of this approach isthat points in the reference image that are not visible fromother views will have wrong depth values after the projection. Nevertheless, this side effect is collectively handled by
the error term E in Eq. (2).

4. Experiments
To demonstrate the effectiveness of our proposed
method, we evaluate our algorithm using both synthetic andreal data. For comparison, we implemented the frame-toglobal-model framework as proposed in [13]. For the extrinsics estimation step, we chose to use the GICP method
as proposed in [22] in place of the linearized GICP as proposed in [13], because the GICP method is more accurate
than its linearized version. We also compared our methodwith GICP used in the frame-to-frame framework, as proposed in [28]. We note that we used the GICP implementation provided by [2].
When the camera is taking drastically different positions
during the scanning procedure, we use a sliding window
with a fixed size through the input sequence of depth images. Namely, we define4 Nw as the size of the window (i.e.
the maximum number of images that we register at once simultaneously) and initialize the process by simultaneously
registering the first Nw depth images. Then, the sequenceis processed as follows: for each incoming depth image, thewindow is moved by one frame (namely, for the ith frame
the window is composed of {dk }k∈[i−Nw +1,i] ) and the current block of images are simultaneously registered. Finally,
3 Such incoherences may be for example small shifts in the z direction,
which may be local minima when seen from the front, but clearly misaligned when seen from the left, or right side.
4 We chose N = 20 in the experiments.
w

Global coordinate system

Virtual camera (cam)Global coordinate systemcam

Global coordinate system

camInterpolation of
depth values

Global coordinate systemcam(x,y,z)

Same
pixel

(a) Input.

(b) Front projection of dref .

(c) Projection of dcam
ref to dk andinterpolation of depth values.

(d) Affectation of back projected
depth to dcam.
(ref,k)Figure 2: Illustration of our depth image projection operator.
for each input depth image, its final estimated extrinsic parameters are output as our result. Note that when a loop exists, standard refinement methods take several passes of theloop. In our method, such refinement is naturally performed
on-the-fly by sliding the window, even when no loop exists.
The initial extrinsics were chosen as the identity matrix
for the first window, and then we used previous estimatesas the incoming frame’s extrinsics. This initialization isreasonable as the viewpoint difference between successiveframes is small when a video-rate camera is used.
In order to speed up the process, we created a pyramidof down-sampled images for each frame and applied our
method with images from the highest tier. In the case where
the registration fails because there are not enough points inthe down sampled images, we used images from the nextlevel of the pyramid. As expected, a gain in speed comeswith loss in accuracy. Fig. 4 (a) shows the relationship between accuracy and time computation for different levels of
the pyramid. We can also see that our method was stable
when we used a pyramid of level 2 (i.e. 41 times initial resolution). Depth image resolution became problematic when1
it reached 16
times the input resolution. In this experiment,
we used the synthetic data A L shown in Fig. 3, which iscomposed of 360 depth images. Note that we implemented
our method on a 3.47 GHz PCU with 96.0 GB memory, in
MATLAB and without any parallel computations.

4.1. Synthetic data
We used three synthetic data, A L, D RAGON, and TABLE,
and created depth images by rendering from surrounding
viewpoints. In all these experiments, we know the groundtruth camera parameters. We added various levels of noise
to the depth images to produce the final input. We first explain the evaluation metrics and then discuss the result.
Registration error metric We evaluate the registration
error using the distance between the estimated position ofpoints and the ground truth in the 3D world coordinates.
The mean absolute error MAE(dk ) for the depth image dk
is defined as

Q

MAE(dk ) =
1 XkT̂k Pk (q) − Tk∗ Pk (q)k2 ,Q q=1

where T̂k is the estimated extrinsics5 , Tk∗ is the ground truth
extrinsics, Pk is the cloud of points generated from thedepth image dk and Q is the number of points in Pk .
We use two error measures using MAE(dk ). One is themax error em of MAE, and the other is the average ea of
MAE defined respectively as
em = maxk (MAE(dk )) ,ea = meank (MAE(dk )) .
Evaluation For each synthetic scene, we evaluate our
proposed method with uniform noise added in the depth images. Each depth image is perturbed with random noise in
the interval [−α, α], where α ranges between 0.0 and 10.0[mm] with 1.0 [mm] interval. The typical noise level inthe depth images acquired using a Kinect camera is about
3.0 [mm]. The depth images are generated from the point
clouds. With depth images of VGA resolution, the resolution of the range images (i.e. the average distance between
two neighboring points) was about 10.0 [mm]. For eachdata, we rendered 360 depth images as input. Namely, we
rotated the camera around the object by 1.0 degree intervalfrom 0 to 360 degrees. For AL and DRAGON we randomly perturbed the camera path to simulate a hand-heldcamera capturing.
Figure 3 shows qualitative registration results using thethree synthetic scenes with our method (without using apyramid), with GICP in the frame-to-global-model framework (called FuGICP) and with the frame-to-frame GICP
(called GICP) in the case of α = 0.0. These are all rendered
as point clouds. Table 1 summarizes the quantitative results. While GICP in the frame-to-frame framework failed
without accurate initialization, our method always obtained
5 Note that all extrinsics are transformed so that the extrinsics corresponding to the first depth image become the identity matrix.

Ground truth

Our method

FuGICPGICP

FuGICPGICP

FuGICPGICP(a) Dataset A L

Ground truth

Our method(b) Dataset D RAGON

Ground truth

Our method(c) Dataset TABLE

Figure 3: Registration results obtained with the three synthetic data, with zoom around the estimated position of the last
camera. For data AL and DRAGON, the blue vertical line passing through the green circle is a marker for better visualizationof the error. For the data TABLE, the marker is the first camera position.
the most accurate registration results, even when comparedwith FuGICP. In particular, Table 1 shows that the registration error obtained with our method is always below 10.0[mm]. This means that the maximum deviation for all points
in all depth images compared to their ground truth positions
is below the resolution of the range data. The quantitative
results thus validate the accuracy of our proposed registration method. From Table 1, we can also see that the maximum errors em are close to the mean errors en . This meansthat there are no huge errors throughout the sequences ofdepth images, and thus the accuracy of our method is lessaffected by changes in viewpoint.

FuGICP for the three synthetic scenes and for various noiselevels added to the depth values. For time reasons, we chose
to apply our method with a pyramid of level 2 (which explains why the errors for α = 0 are slightly degraded compared with Table 1). For each noise level, all methods wererun 10 times under the same conditions except for the noise
distributions, whose registration errors em and ea are shownin the plots. From Figure 4, we can see that our method
achieves robustness against data noise while FuGICP is degraded as noise increases. In particular, adding noise in thedata TABLE had dramatic effects for FuGICP.

Note that our method is less affected to changes in shapeof the object compared with FuGICP. This is because weuse a global evaluation metric accounting for multiple depth
images in contrast to the pair-wise local evaluation metricused in GICP.

4.2. Real data

Figure 4 shows the results obtained with our method andWe also perform experiments using real data recorded byMicrosoft Kinect. This sensor can record 30 depth images
per second with a resolution up to 640 × 480. We used
the RGBDemo software [3] to capture the depth and color
images. Because we had to save the live data, the frameTable 1: Registration errors em , ea , and ed for three synthetic scenes [mm] in the case of σ 2 = 0.

200

20

150

15

100

10
5

50

0

0
2

ea [mm]em[mm]*me [mn]

Data Al

30
25
20
15
10
5
0

FuGICP

Our method03Level of the pyramid

2

4

6

8

10

Noise in depth values (in mm)

0

2

4

6

8

10

Data Dragon

50
40
30
20
10
0

FuGICP
Our method0

Noise in depth values (in mm)

FuGICP
Our method
2

4

6

8

10

Noise in depth values (in mm)(d) Dataset A L

2

4

6

8

10

Noise in depth values (in mm)(in mm)FuGICP
Our method(in mm)(in mm)Data Dragon

25
20
15
10
5
0

GICP
97.4
49.9

Data Al

60
50
40
30
20
10
0
0

(a) Time versus acuracy.

TABLE
FuGICP
19.8
8.2

Ours
6.9
4.4

Data Table
80

FuGICP

60

40

Our method

20(in mm)250

25

D RAGON
FuGICP GICP
7.1
14.4
4.4
9.9

Ours
3.7
2.5

(in mm)

300

30

GICP
39.4
19.6

(in mm)35!me [mn]errors [mm]Max error em
Average error ea

1

AL
FuGICP
9.0
5.1

Ours
7.1
4.0

Data Table
150

FuGICP
Our method

100
50
0

0
0

2

4

6

8

0

10

Noise in depth values (in mm)(g) Dataset D RAGON

2

4

6

8

10

Noise in depth values (in mm)(j) Dataset TABLE

Figure 4: Plots of average registration errors. Max error em , average error ea w.r.t. different noise levels using our method
and FuGICP are plotted.
rate dropped down to 10 images per second with some lagsin the sequence. For comparison, we used FuGICP, whichobtained better results than GICP with the synthetic data.
Figure 5 shows the results using two different real scenes
with our method and FuGICP. The first scene consists of
300 images and the second scene consists of 200 images.
While the FuGICP method breaks down in the first and second examples, our method can accurately register the depth
images. The main reason for this is that even though GICP
uses dense point correspondences between pairs of depth
data, each correspondence is obtained independently. As aconsequence, parts of the scene that are weakly supportedby the global structure of the scene (feature-less parts, e.g.,walls or tables) tend to affect the registration result. In contrast, our method uses a global measure to ascertain the accuracy of the alignment (i.e., the rank of the stacked matrix).
Accordingly, local patches that lack discriminative geometric features have little impact on the registration result. In
addition, missing points are dealt with during the projection
process while occlusions and sparse depth measurement errors are modeled in the optimization problem, which leads
to a robust registration method.
Note that in these experiments, the global camera motion
amplitude was small and that it was the most advantageoussituation for FuGICP. By doing so, the volumetric model(a) Our method(b) FuGICP(c) Our method(d) FuGICP

Figure 5: The results obtained with real data.

used in FuGICP could be restricted to a small part of the 3D
world, which allowed fine discretization of the 3D scene.
We chose the most challenging conditions to evaluate thegain in accuracy of our method compared with FuGICP.

5. Conclusion
We introduced a robust simultaneous 3D registration
method for dense sets of depth images, based on a rank minimization strategy. By arranging the depth measurements ina matrix form, we formulated the problem as a simultaneous estimation of all the extrinsics and a low-rank matrix,
which corresponds to the aligned depth images, as well asa sparse error matrix that models corruptions, such as occlusions. To solve the matrix decomposition problem, weused an advanced convex optimization technique that robustly finds a solution that is unaffected by sparse errors.
We developed an efficient projection method that has minimal sensitivity to the surface sampling to achieve efficient
optimization. Our extensive experiments using synthetic
and real data demonstrated the robustness and accuracy ofour proposed method for simultaneous registration of multiple depth images.
Since the rank of all aligned depth images is 1 in theory, enforcing this condition and minimizing the L1 normof the residuals may also be effective. Investigation in thisdirection is left for future work.

References[1] Microsof kinect: http://www.xbox.com/en-US/
kinect. 1[2] ICP PCL code: http://pointclouds.org/. 4[3] RGBDemo:
http://nicolas.burrus.name/index.php. 6[4] H. Bay, T. Tuytelaars, and L. V. Gool. Surf: Speeded up
robust features. Proc. of ECCV’06, pages 404–417, 2006. 2[5] P. J. Besl and N. D. McKay. A method for registration of 3-D
shapes. IEEE Trans. on PAMI, 14(2):239–256, 1992. 2[6] N. Brusco, M. Andretto, A. Giorgi, and G. M. Cortelazzo.
3d registration by textured spin-images. Proc. of 3DIM’05,
pages 262–269, 2005. 2[7] R. Candes, X. Li, Y. Ma, and J. Wright. Robust principal
component analysis? Proc. of CoRR’09, 2009. 2, 3
[8] S. Choi, T. Kim, and Z. Yu. Performance evaluation of ransac
family. Proc. of BMVC’09, 2009. 2[9] Y. Cui, S. Schuon, D. Chan, S. Thrun, and C. Theobalt.
3d shape scanning with a time-of-flight camera. Proc. of
CVPR’10, 2010. 2[10] A. Davison, I. Reid, N. Molton, and O. Stasse. Monoslam:
Real-time single camera slam. IEEE Trans. on PAMI, pages
1052–1067, 2007. 2[11] D. W. Eggerta, A. W. Fitzgibbon, and R. B. Fisher. Simultaneous registration of multiple range views for use in reverse
engineering of cad model. 1996. 2[12] J. Herman, D. Smeets, D. Vandermeulen, and P. Suetens.
Robust point set registration using em-icp with informationtheoretically optimal outlier handling. Proc. of CVPR’11,
pages 2465–2472, 2011. 2[13] S. Izadi, D. Kim, O. Hilliges, D. Molyneaux, R. Newcombe,
P. Kohli, J. Shotton, S. Hodges, D. Freeman, A. Davison,and A. Fitzgibbon. Kinectfusion: Real-time 3d reconstruction and interaction using a moving depth camera. Proc. of
ACM Symposium on User Interface Software and Technology, 2011. 1, 2, 4
[14] B. Jian and B. C. Vemuri. A robust algorithm for point set
registration using mixture of gaussian. Proc. of ICCV’05,
2:1246–1251, 2005. 2[15] Y. Liu. Automatic range image registration in the markov
chain. IEEE Trans. on PAMI, 32(1):12–29, 2010. 2[16] D. G. Lowe. Object recognition from local scale-invariant
features. Proc. of ICCV’99, 2:1150–1157, 1999. 2[17] P. J. Neugebauer. Geometrical cloning of 3d objects via simultaneous registration of multiple range images. Proc. of
SMA’97, 1997. 2[18] K. Nishino and K. Ikeuchi. Robust simultaneous registrationof multiple range images. Proc. of ACCV’02, pages 454–461,
2002. 2[19] Y. Peng, A. Ganesh, J. Wright, W. Xu, and Y. Ma. Rasl:
Robust alignment by sparse and low-rank decomposition for
linearly correlated images. IEEE Trans. on PAMI, 2011. 2,3, 4[20] S. Schuon, C. Theobalt, J. Davis, and S. Thrun. High-quality
scanning using time-of-flight depth superresolution. Proc. of
CVPRW’08, pages 1–7, 2008. 2[21] S. Schuon, C. Theobalt, J. Davis, and S. Thrun. Lidarboost:
Depth superresolution for tof 3d shape scanning. Proc. of
CVPR’09, 2009. 2[22] A. Segal, D. Haehnel, and S. Thrun. Generalized-icp.
Robotics: Science and Systems, 2009. 2, 4
[23] G. C. Sharp, S. W. Lee, and D. K. Wehe. Multiview registration of 3d scenes by minimizing error between coordinate
frames. IEEE Trans. on PAMI, 26(8):1037–1050, 2004. 2[24] D. Thomas and A. Sugimoto. Robustly registering range images using local distribution of albedo. Computer Vision andImage Understanding, 28(4):649–667, 2011. 2[25] E. Tola, V. Lepetit, and P. Fua. Daisy: an efficient dense
descriptor applied to wide baseline stereo. IEEE Trans. on
PAMI, 2009. 2[26] A. Torsello, E. Rodola, and A. Albarelli. Multiview registration via graph diffusion of dual quaternions. Proc. of
CVPR’11, pages 2441–2448, 2011. 2[27] Y. Watanabe, T. Komuro, and M. Ishikawa. High-resolution
shape reconstruction from multiple range images based on
simultaneous estimation of surface and motion. Proc. of
ICCV’09), pages 1787–1794, 2009. 2[28] T. Weise, B. Leibe, and L. V. Gool. Accurate and robust
registration for in-hand modeling. Proc. of CVPR’08, pages
1–8, 2008. 2, 4[29] T. Weise, T. Wismer, B. Leibe, and L. V. Gool. In-handscanning with online loop closure. Proc. of 3DIM’09, pages
1630–1637, 2009. 2[30] Z. Xie, S. Xu, and X. Li. A high-accuracy method for fineregistration of overlapping point of clouds. Image and Vision
Computing, 28(4):563–570, 2010. 2[31] H. Zhang, O. Hall-Holt, and A. Kaufman. Range image registration via probability fields. Proc. of CGI’04, pages 546–
552, 2004. 2