Iterative Refinement of Range Images with
Anisotropic Error Distribution
Ryusuke Sagawa† Takeshi Oishi† Atsushi Nakazawa†
Ryo Kurazume‡ Katsushi Ikeuchi†† The University of Tokyo

Abstract
We propose a method which refines the range measurement of range finders by computing correspondences ofvertices of multiple range images acquired from various
viewpoints. Our method assumes that a range image acquired by a laser range finder has anisotropic error distribution which is parallel to the ray direction. Thus,
we find corresponding points of range images along withthe ray direction. We iteratively converge range images
to minimize the distance of corresponding points. We
demonstrate the effectiveness of our method by presenting the experimental results of artificial and real range
data. Also we show that our method refines a 3D shape
more accurately as opposed to that achieved by using theGaussian filter.

1 Introduction
Large scale 3D modeling technology has become popular and is often used for modeling industrial plants, buildings, cultural heritage objects, and so on. Using this technology, enables many project scientists to digitize large
scale cultural heritage objects or natural scenes.
The 3D object modeling is accomplished by performing
the following three steps:(1) Acquiring the range images (Scanning).
(2) Aligning of many range images acquired from different viewpoints (Aligning).
(3) Re-generating the unified meshes (Merging).
Usually, during the scanning process To ensure that all of
the 3D shape data is acquired, several range images aretaken of each portion of the object surface.
For the alignment of the small objects, the geometrical
relationship between range images can be easily identified because the objects’ motions are controlled by using rotation tables or manipulators. However, that relationship cannot be acquired for large objects; in suchcases, range image matching techniques are used for thealignment. Many studies have been devoted to achieving
this purpose. Besl proposed a feature point-based matching method [1], while Chen’s method is based on the‡ Kyushu University

evaluation between the point and the polygons. Neugebauer proposed the idea of ’simultaneous registration’that aligns range images simultaneously to avoid the error accumulation of the pairwise alignment methods [6].
A similar idea was proposed by Nishino et al. [7].
A merging procedure produces unified meshes fromaligned range images. This is accomplished by concatenating the polygons’ borders [10], using deformable surfaces [4] or implicit functions [2, 11]. Wheeler’s method
uses ’signed distance’ to represent the distance from 3D
mesh surfaces and their consensus. As the result, the errors and outliers are eliminated.
The errors of the final 3D model come from these factors.
(1) A measurement error on the range images.
(2) A matching error on the alignment process.
(3) The quantization and equalization errors on the merging process.
The type (2) and (3) errors depend on the object shapeand the algorithm, and so are solved by selecting a suitable algorithm according to the objects. For the type (1)error, Taubin used the spatial smoothing filter [9], but finefeatures can be lost during this procedure. Basically, thiskind of error cannot be avoided from one range image byusing any software algorithms.
Taking many range images of the same surface is the oneof the solutions for this problem. Generally, any range
measurement system has its characteristic minimum measurement accuracy and error distributions. Wheeler’s
method is based on this consideration, but is weak for
spatially high resolution range images. The signed distance is calculated along the normal direction of the surface. If the normal directions are not responsible becauseof a measurement error, then the final merging result isalso not responsible.
We propose a method to avoid this weakness and improve the accuracy of the final 3D model. This reduces
the measurement errors on the distance value in the overlapping areas of the aligned range images. By applying
this method before the merging process, a much finer 3Dmodel may be acquired. Unlike the existing spatial filtering method, our method is able to not only smooth theFigure 1: Measurement error

surface of the final 3D mesh model but also to extract
fine features. In the following sections, 2 describes our
proposed estimation and correction method. 3 shows theresult of refinement of artificial and real range data. Finally, we summarize our method in 4.

2 Proposed Method
Our method corrects errors by iterative computation similar to registration techniques like ICP[1]. Let us call thebase range image the ’model’ and others the ’scenes.’ We
first search the corresponding points on all scenes of eachvertex of the model. Then, we move every vertex of themodel respectively to reduce the distance of each correspondence. Our method continues this process until the
distances become sufficiently small.
The following pseudo code shows the proposed algorithm:
Algorithm Procedure of Correct Errors
while (error > threshold){for (i = 0; i < nImage; ++i){/* range image i is model */for (j = 0; j < nImage; ++j){/* Search corresponding points *//* for all vertices of the model*/if (i != j) CorrespondenceSearch(i, j);}/* Compute the next position of vertices */MoveVertex(i);}/* Update the motion of all vertices */UpdateVertex(all);}

2.1 Error model of Range Measurement
Laser range finders measure distance by shooting a laser
and receiving its reflection from the target object. The
3D position of the point of reflection is computed by the

Figure 2: Search correspondence

distance and the ray vector. The error of the 3D position
mainly depends on the error of the distance. The error of
the vertical direction to the ray vector, which is caused by
the mechanism of the range finder, is much smaller thanthe error of the distance. Thus, we assume the error of therange measurement by a laser range finder is anisotropic
and exists only along the ray vector (Figure 1).
2.2 Correspondence Search
Since we assume that error exists only along the ray vector and that range images are completely aligned, ourmethod searches corresponding points along the ray vector. Now, x is the vector from the center of the sensor to
the vertex of the model and y is the vector from the center
to the corresponding point of the scene. Then,y = ax(1)where a is the coefficient. Thus, these points are on thesame line (Figure 2).
To eliminate wrong correspondences, if the distance ofcorresponding points is larger than a threshold, we remove the scene point from the correspondence. We use
the maximum error of the range finder as the threshold.
This correspondence search is computed for every combination of range images.
2.3 Error Correction
Errors are corrected by moving each vertex to the new position, which is estimated from the corresponding points.
Since the direction of error of each range image is different, some correspondences are not accurate. In thecase that the number of overlapped range images is small,
it is difficult to estimate the accurate point. Thus, wemove each vertex to the weighted average point of thecorrespondence in order to gradually converge the error.
The kth vertex of ith range image xik is moved to thex1y1
Ray directions

x2
y2
x3

Figure 4: Smoothing effect by iteration

Figure 3: Error by resolution and geometry

After one more iteration, x2 moves toweighted average point ik = (1 − w) · xik + w ·xRange images


1
yjk
nik − 1

(2)

x2

i=j

where nik is the number of the corresponding points andw is the weight. In this paper, we use w = 0.5. This process is applied to all vertices of each range image. We
reiterate it until the error of correspondence converges
sufficiently.
2.4 Discussion
The error of corresponding points  depends on the errorof measurement M easure and the error by sparse sampling of a range image Geometry .
 = M easure + Geometry(3)M easure is corrected by iterative computation. However,Geometry is caused by the curvature of the surface andthe sampling interval of a range image.

==(1 − w)x2 + w((1 − α )y1 + α y2 )w 2 (1 − α )(1 − β)x1 + w 2 α γx3 +((1 − w)2 + w 2 (1 − α )β + w 2 α (1 − γ))x2 +w(1 − w)(2 − α − α )y1 +w(1 − w)(α + α )y2(6)

where α is a coefficient. Since the equation of x2 includes the neighbor vertices x1 , x3 , the smoothing effectoccurs during an iteration similar to the smoothing filter.
However, the weight of x1 and x3 in (6) is small compared with that of the smoothing filter, for example,x2 = αx1 + βx2 + (1 − α − β)x3 ,(7)

which does not include y1 , y2 . Thus, the propagation of
the smoothing effect of our method is slower than that of
the smoothing filter. In our present implementation, we
determine the number of iterations by estimating manually whether the iteration is sufficient.

In Figure 3, the range measurement is noise-free and thevertices of range images are on the real surface (namely
M easure = 0); however, the error exists between x andy . Thus,  = 0 only if the surface is planar.
= 0 planar area(4)
> 0 otherwise

With regard to the computation cost, most of the computation cost is due to searching for correspondences.
Our algorithm searches for correspondences of vertices
by rendering all range images from the viewpoint of thereference range image. Thus, the order of computation isO(M N 2 ) for an iteration of refinement of all range images, where N is the number of range images and M is
the number of vertices of a range image.

Figure 4 shows a 2D example of range images. For simplicity, we assume the new positions of x2 , y1 , y2 after an
iteration is computed as

3

3.1 Error Distribution of Laser Range Finderx2 = (1 − w)x2 + w((1 − α)y1 + αy2 )y1 = (1 − w)y1 + w((1 − β)x1 + βx2 )y2 = (1 − w)y2 + w((1 − γ)x2 + γx3 )Experiment(5)

where w, α, β, γ are coefficients. Coefficients α, β, γ are
determined by correspondence of x1 , x2 , x3 , y1 and y2 .

Among types of laser range finders, a time-of-flight range
finder is useful to measure a distant object with high accuracy. We use a laser range finder of the time-of-flight
type, Cyrax 2500 [3] made by Cyra Technologies, Inc. To
estimate the error distribution of the Cyrax 2500, we set
the range finder in front of a concrete wall and measured

Frequency [times]
Frequency [times]

Table 1: Distance measurement error of Cyrax 2500

16
12
8
4
0
2000

2010

2020
2030
Distance [mm](a) Near range

2040

21510

21520
21530
Distance [mm](b) Middle range

21540

Average distance [mm]2017.2 (near)21518.0 (middle)
67591.1 (far)Var. [mm2 ]
11.0
9.1
7.7

16
12
8
4
0
21500

(a)
Frequency [times]

STD. [mm]
3.3
3.0
2.8

(b)

20

Figure 6: Artificially created model

10
0
67570

67580

67590
67600
Distance [mm](c) Far range

67610

Figure 5: Distribution of errors of Cyrax2500

the distance to the wall many times. We tested three configurations of different distances, far range (67m), middle
range (20m) and near range (2m) 1 . Figure 5 shows theresult of measurement and the average, variance and standard deviation are depicted in Table 1. The error distribution becomes wide in the near range; however, it can be
regarded as a normal distribution with about 3mm standard deviation. The maximum error is about 7–8mm,
which is a little larger than the 6mm (at 50m range) of
the catalog specification.
We did not test the error distribution of the vertical direction to the ray vector. According to the catalog, it is
0.25mm at 50m range (0.0003 degree), which is drastically smaller than that of the ray direction. Thus, the error
distribution of the range image by Cyrax 2500 depends on
the ray direction.
3.2 Error Correction of Artificial DataFirst, we create artificial range images with random noiseand experiment with the error correction. Figure 6(a)shows the model without noise. Its width and height are
40cm, its depth is 20cm and it consists of 100 × 100
points. The range image with noise, of which the maxi1 The recommended range of Cyrax 2500 is 1.5–50m.

mum is 6mm, is Figure 6(b). We create 10 range images,
to which are added noises of different direction. The result of error correction is shown in Figure 7(a). Figure7(b) is one of range images filtered by Gaussian filter.
We can see that our method corrects error sufficiently andpreserves edges more accurately than does the Gaussian
filter. Figure 8 compares these two results.
We use a PC with a PentiumIII 866MHz processor anda NVIDIA GeForce3 graphics card. Since our method
searches correspondences by rendering range images, it
can be accelerated by the use of graphics hardware. The
computation time for 20 iterations is 413 seconds.
3.3 Error Correction of Real Data
Next, we experiment on the error correction of range images acquired by a laser range finder Cyrax 2400, whose
accuracy is the same as that of the Cyrax 2500.
The observed object is the Nara Asuka Great Buddha,
which is considered to be the oldest Buddha statue inJapan. Its height is about 2.7m. Cyrax 2400 is a range
finder for long range, and is not suitable for measuring
objects of the Asuka Buddha’s size. However, because of
the bad environment around the Buddha, we cannot use amore accurate range finder for near range. Thus, we measure the Buddha a little apart from it by using the Cyrax
2400.
We have acquired 9 range images of the front of the Buddha. We align these range images simultaneously by using a robust registration method [7] (see Figure 10). Since
the object is relatively small and the range is near, the ob-

(a)

(b)

Figure 7: Refined model
Figure 9: Great Buddha at Asuka temple

Figure 8: Compare our method and Gaussian filter

vious noise can be seen in the range images.
Figure 11 shows the result of the error correction by our
method. The noise has been removed from the modeland its surface is smooth. In spite of that, the edges arewell preserved because our method is not a smoothing
operation such as the Gaussian filter. In Figure 12, theerror converges to 0 as the number of iterations increases.
The computation time for 20 itrations is 1510 seconds.
Figure 13 shows the results of merging range images using both the original range images and the refined range
images. We use the merging technique by Sagawa [8].
Since the method takes consensus of range images using the distance and normal direction [11], it can remove
the error caused by measurement and registration. However, in this experiment, it is difficult to correct the error
because the range images are too noisy and its normal
direction cannot be relied on. We can see that the error remains in the merging result which uses the original
range images in Figure 13. On the other hand, the accurate model is reconstructed in the merging result with the

Figure 10: Original range image

refined range images. In the area where range images are
not overlapped such as the side of the head, the error is
not removed.
We compare our method with the model filtered by theGaussian filter. Figure 14 shows a part of the model filtered by the Gaussian filter after merging and the model
merged from refined range images. The model with theGaussian filter is smoothed out; however, our method removes noise and preserves the edge of the surface.
Finally, we consider whether our method can be applied
to other range finders, for example, a stereo range finding
system. We construct a multi-baseline stereo system [5],which consists of 9 cameras. Figure 15 shows one of thecamera images and a stereo range image. Since the multibaseline stereo generates a range image for each camera
by taking matching images with the other 8 cameras, we
generate 9 stereo range images. These range images are
pre-aligned by stereo calibration. Thus, our refining process can be applied straightforwardly to the 9 range images. In the raw stereo range image (Figure 16(a)), we
can see the step-shaped error caused by quantization of

Figure 11: Refined range image

Original

RefinedFigure 13: Results of merging

Figure 12: Convergence of error

Gaussian Filter

Our Method

Figure 14: Compare with Gaussian filter
images. Figure 16(b) is the refined model after 10 timesof the iteration. The step-shaped error is removed afterrefinement. Also, Figure 16(a) contains a lot of debris
due to mismatching. Since the refining process is an estimation of the confidence of range data, we can regard thevertices of the range image which cannot be refined as
unreliable vertices. Figure 16(c) is the range image after
the unreliable vertices are removed.

4 SummaryIn this paper, we have proposed an efficient range image
refinement method under the consideration of unique error distributions of multiple range images. We described
how we applied this method for the modeling of the artificial test object and the actual cultural heritage object
from the images acquired by the time-of-flight range sensor. Finally, we applied our method to the range images
which are generated by the multi-baseline stereo system.
The experimental result shows the validity of this method
compared with that of the existing filter-based methods.

References[1] P. J. Besl and N. D. McKay. A method for registrationof 3-d shapes. IEEE Trans. Pattern Anal. Machine Intell.,14(2):239–256, 1992.
[2] Brian Curless and Marc Levoy. A volumetric method forbuilding complex models from range images. In Proc. SIGGRAPH’96, pages 303–312. ACM, 1996.
[3] http://www.cyra.com.
[4] Martial Hebert, Katsushi Ikeuchi, and Herve Delingette. A
spherical representation for recognition of free-form surfaces. IEEE Transactions on Pattern Analysis and MachineIntelligence, 17(7):681–690, 1995.
[5] M.Okutomi and T.Kanade. A multiple-baseline stereo.
IEEE Trans. Pattern Analysis and Machine Intelligence,15(4):353–363, 1993.
[6] P. J. Neugebauer. Geometrical cloning of 3d objects via
simultaneous registration of multiple range image. In Proc.

Original camera image(a)Raw model by stereo

Stereo range image
Figure 15: Range measurement by stereoof the 1997 Int. Conf. on Shape Modeling and Application(SMA’97), pages 130–139, 1997.

(b)Refined model[7] K. Nishino and K. Ikeuchi. Robust simultaneous registration of multiple range images. In Proc. of Fifth Asian
Conference on Computer Vision ACCV ’02, pages 454–461,
2002.
[8] R. Sagawa, K. Nishino, and K. Ikeuchi. Robust and adaptive integration of multiple range images with photometricattributes. In Proc. IEEE Computer Society Conference on
Computer Vision and Pattern Recognition 2001, volume 2,
pages 172–179, December 2001.
[9] Gabriel Taubin. A signal processing approach to fair surface design. Computer Graphics, 29(Annual Conference
Series):351–358, 1995.
[10] G. Turk and M. Levoy. Zippered polygon meshes fromrange images. In SIGGRAPH 94, pages 311–318, Jul 1994.
[11] M.D. Wheeler, Y. Sato, and K. Ikeuchi. Consensus surfaces
for modeling 3d objects from multiple range images. In
Proc. International Conference on Computer Vision, January 1998.

(c)Remove unreliable vertices
Figure 16: Refinement of range image by stereo