3D MODELING OF OUTDOOR SCENES BY INTEGRATING STOP-AND-GO ANDCONTINUOUS SCANNING OF RANGEFINDER
Toshihiro ASAI† , Masayuki KANBARA† , Naokazu YOKOYA††

Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara, Japan.
{toshih-a,kanbara,yokoya}@is.naist.jp
Commission V, WG V/4

KEY WORDS: Three-dimensional Modeling, Laser scanning, Urban Scene, GPS/INS.
ABSTRACT:This paper describes a 3D modeling method for wide outdoor environments by integrating stop-and-go and continuous scanning of laser
rangefinder. First, range images of an outdoor scene are measured by stop-and-go scanning by using omnidirectional laser rangefinder,
and the 3D surface model is generated. Next, to recover the parts that are not measured in the stop-and-go scanning mode due to
occlusion, we measure the outdoor scene in the continuous scanning mode where the laser rangefinder line-scans the scene under
movement is employed. In the continuous scanning mode, the position and orientation of the rangefinder is acquired by a hybrid sensor
which consists of GPS (Global Positioning System) and INS (Inertial Navigation System). Finally, multiple range data acquired in two
scanning modes are integrated by registering overlapped parts of range data.

1 INTRODUCTION
3D models of outdoor environments can be used in a number ofapplications such as landscape simulation, human navigation andvirtual walk-through. However, such 3D models are often mademanually with high costs, so recently automatic 3D modelingmethods have been widely investigated; for example, 3D shapeestimation from an image sequence (1)-(5) and 3D measurement
by a laser rangefinder (6)-(9). The merit of the former is that themethod can reconstruct a 3D model with only a camera. However, since it is difficult for vision-based methods to reconstruct a
3D model with high accuracy, the approaches are not suitable for
3D modeling of wide area outdoor environments. On the other
hand, the latter can widely measure the shape of object with highaccuracy. Thus it is useful for wide area outdoor environments.
Two scanning methods of rangefinder have been proposed:• Stop-and-go scanning (7)-(9),• Continuous scanning (10)-(11).
The stop-and-go scanning method measures environments at anumber of fixed positions. In order to generate 3D models of environments, range data acquired at multiple points should be registered. In most conventional methods for registration of multiple
range data, the ICP algorithm (12) is often used. In the method,
the distance between corresponding points in paired range data isdefined as a registration error, and a transformation matrix is calculated so that the error is minimized. Therefore, to apply the ICP
algorithm, it is necessary for a pair of range data to include overlapped regions. Since outdoor environments are complex, manyocclusions occur and also there are some objects which cannot bemeasured by the rangefinder stably. In order to solve this problem, Gunadi et al. (13) have registered local range data acquiredon the ground into a global range data acquired from the sky.
In the stop-and-go scanning, it takes a long time for data acquisition of wide outdoor environments without lacking portions
caused by occlusion. This method measures the real environments by a moving sensor system mounted a car or an airplaneetc. This method can measure wide area scenes efficiently.However,to generate a 3D model from acquired range data, the positions

and orientations of rangefinder are needed. The accuracy of generated model depends on the accuracy of estimated positions andorientations of rangefinder during measurement. One of the continuous scanning methods used a GPS (Global Positioning System) and an INS (Inertial Navigation System) sensor to acquire
position and orientation of rangefinder (10), this method can acquire the position and orientation stably. However, a GPS is influenced by the reflection of radio wave by the buildings, and an
INS sensor can not acquire data with sufficient accuracy for 3Dmodeling by an accumulative error, when the sensor is used for along time.
As another method, Früh et al. (11) have acquired range data
by using a line scanner which scans the scene horizontally, andthe position and orientation are estimated by matching horizontal scan data. They have carried out 3D modeling of an urbansite with a texture by using the method. This method estimatesthe current position and orientation of rangefinder from the difference between previous and current scanning results. For thatreason, an error is accumulated. Moreover, when the current scanline can not match previous one because of the influence of objects which are not measured stably or the shake of sensor system,
the position and orientation can not be estimated.
This paper proposes a 3D modeling method which is based on integrating the data acquired by stop-and-go and continuous scanning for reduction of non-measured portions. First, outdoor environments are measured at multiple points by stop-and-go scanning using an omnidirectional laser rangefinder, and a 3D surface
model is generated. Then, the portions, defined as non-measured
portions, which are not measured by stop-and-go scanning aremeasured by continuous scanning. In order to register multiple
range data of wide area acquired by stop-and-go scanning stably,
only planar surfaces that are extracted from the range data areused for registration process, because typical outdoor environments contain many plane regions such as walls and roads. Multiple range data are simultaneously registered by the improved ICP
algorithm using detected plane portions. In registration process,the position and orientation, which are acquired by RTK-GPS
and INS sensor, are used as initial values of sensor position andorientation of range data for registration by the ICP algorithm.

RTK-GPS(Nikon-Trimble, LogPakII)

Laser rangefinder(Riegl, LMS-Z360)

INS sensor(Tokimec, TISS-5-40)
Figure 1: Sensor system mounted on a vehicle.

Table 1: Specification of LMS-Z360
measurable angle
measurable range
measurement accuracy
minimum step angle
maximum resolution
measurement rate per line

horizontal:
360◦
vertical:-50◦ ∼40◦
1m∼200m±12mm
0.01◦
horizontal: 0.0025◦
vertical:
0.002◦
20Hz

The 3D surface model is generated by polygonizing the registered range data. The non-measured portions exist sparsely in theenvironments measured by stop-and-go scanning mode at multiple points. Therefore, the proposed method attempts to reduce
the non-measured portions and time for measurement of environments by continuous scanning mode using a line scanner. Moreover, the positions and orientations of rangefinder during measurement are optimized by registering the range data acquired in
the continuous scanning mode into the 3D surface model acquiredin the stop-and-go scanning mode.
This paper is structured as follow. Section 2 briefly describes thesensor system used in this study. Section 3 explains the registration of omnidirectional range data acquired at multiple positions.
Section 4 describes the method for integrating the data which are
acquired by stop-and-go and continuous scanning. In Section 5,
experimental results are described. Finally, Section 6 gives summary and future work.

Table 2: Specifications of hybrid sensor (measurement rate :50Hz)(a) Accuracy of position.
latitude±3.0cmlongitude ±3.0cm
altitude±4.0cm(b) Accuracy of orientation.
yaw
±2◦
roll
±0.5◦
pitch ±0.5◦measured by the INS sensor includes an accumulative error. The
INS sensor is interlocked with RTK-GPS in order to correct theaccumulative error by measuring the direction of movement calculated by GPS data during movement. This hybrid sensor canacquire the position and orientation with high accuracy by compensating the low measurement rate of RTK-GPS and accumulative error of INS sensor. The specification of hybrid sensor isshown in Table 2.
The transformation matrix between rangefinder and INS sensor
can be estimated by measuring more than three markers whose
positions in the INS sensor coordinate system are known. The
markers are placed at positions which can be measured by therangefinder as shown in Fig. 2(a). The transformation is estimated by measuring the positions of markers with respect to therangefinder as shown in Fig. 2(b).
marker

2 SENSOR SYSTEM
This section describes the sensor system. Fig. 1 illustrates thesensor system mounted on a vehicle. In the proposed method,
the position and orientation of sensor system are fixed during acquisition of data. The system equips the omnidirectional laser
rangefinder (Riegl, LMS-Z360), RTK-GPS (Nikon-Trimble, LogPakII), and INS sensor (Tokimec, TISS-5-40). The system is usedin both stop-and-go and continuous scanning modes.
Omnidirectional Rangefinder
The specification of the rangefinder is shown in Table 1. Angle
and resolution of measured range data can be determined by user.
This rangefinder can measure environments omnidirectionally byilluminating a laser beam radially. The rangefinder takes at least
45 seconds for omnidirectional measurement. The rangefinder isused as an omnidirectional rangefinder in the stop-and-go scanning mode and is used as a line scanner in the continuous scanning mode.
RTK-GPS and INS sensor
RTK-GPS and INS sensor are used to measure the position andorientation of sensor system, respectively. In general, a yaw value(a) Layout of markers(b) Laser intensity of markers

Figure 2: Alignment of rangefinder and INS sensor coordinate
systems.
3 GENERATION OF 3D SURFACE MODEL BY
STOP-AND-GO SCANNING
A surface model of environment is generated by registering multiple omnidirectional range data (14). All the range data are registered to the GPS coordinate system. Since the position and orientation acquired by the sensors include some errors, they are used
as initial values in registration and should be optimized. The ICP
algorithm (12) is often used for registration of multiple range images. In the conventional ICP algorithm, the distance between
corresponding points in paired range data is defined as a registration error, and the transformation matrix is calculated so thatthe error is minimized. The present rangefinder measures the distance by rotating the laser scan, thus the spatial density of datapoints depends on the distance; that is, close objects are measured densely and far objects are measured sparsely. In registering range data obtained at different positions, this causes the
problem that multiple points may correspond to a single point.
The solution tends to fall into a local minimum, because the correspondences between points are discrete and do not include thesurface information about an object (16). The proposed method
first detects plane regions from all the range data, and then determines point-to-plane correspondences. Finally, the transformation matrix of range data is calculated by overlapping the corresponding planes.
3.1 Simultaneous Registration of Multiple Omnidirectional
Range Data
Multiple range data are registered by overlapping the corresponding planes among range data. For this purpose as a pre-processing,planar regions in range data are detected and the normal vectors
at the measured points in planar regions are calculated, and thenthe plane in one data is matched with planar points in other data.
Multiple range data are simultaneously registered for optimization of transformation matrices. The position and orientation acquired by RTK-GPS and INS sensor are used as an initial value
in the optimization. The flowchart of the registration is shown in
Fig. 3 and the detail of each process is described in the following.
start
Plane detection from range data (3.1.1)

Nkl1
Pni
Qnij

no

Is solution converged?
yes

Qx1

3.1.1 Plane Detection from Range Data Planar regions aredetected from range data by local plane fitting. We employ therenormalization method (15) for planar region detection and thequadtree segmentation recursively. The whole range image istaken as an initial region. The distances between estimated planeand points in the region are calculated and when at least one distance is bigger than a threshold, the region is split. On the other
hand, when all the distances are smaller than the threshold, theregion is defined as a plane portion. The points which are notdefined as a plane portion are not used for registration process.
3.1.2 Search of Corresponding Plane The plane corresponding to the plane of a certain range data is looked for from anotherrange data. The plane correspondence is described below. Let
RDn be range data n (n = 1, · · · , N ), Pni be a planar regionin RDn (i = 1, · · · , I) and Qnij be a point in the plane Pni(j = 1, · · · , J). The normal vector of Pni is denoted by Nni .
A plane corresponding to the point Qnij is searched from range
data other than the range data n. A plane Pkl corresponding to
the point Qnij is selected so that |Qnij Qx |, which means the
distance between Qnij and Qx , is minimized. Note that Pkl and
Qnij satisfy two conditions shown in Fig. 4: the inner productof Nkl and Nni is below a threshold (Fig. 4(a)) and a point Qx
where the vector Nkl passing through point Qnij intersects theplane Pkl exists (Fig. 4(b)). Pkl1 is chosen as the plane whichcorresponds to Qnij in both Fig. 4(a) and (b).

Pkl1

Nkl1 Qx2
Qnij

Pkl2

Nkl2

(b) Selection by existence of an intersection.

Figure 4: Selection of corresponding plane.
3.1.3 Estimation of position and orientation of range data
The sensor position of range data is estimated from the distances
between points in a plane and the corresponding planes and thesensor orientation of range data is estimated from the inner products of normal vectors of corresponding points and planes. Let
Tn and Rn be sensor position and orientation of range data n(n = 1, · · · , N ), respectively.
step 1. The orientations Rn are estimated by maximizing thecorrelation CN defined as the sum of inner products of normal vectors of a point Qu and the plane PQu which is corresponding Qu (u = 1, · · · , U ), where U represents thenumber of pairs of corresponding point and plane.
U
X(RQu NQu ) · (RPQu NPQu ) → max,

(1)

u=0

where NQu and NPQu are the normal vectors of Qu andPQu respectively.
step 2. The positions Tn are estimated by minimizing the error
ET which is defined as the sum of distances between corresponding point and plane as follows.

end

Figure 3: Procedure of registring range data

Qx2

Nni

CN =

Estimation of transformation matrix fromcorresponding points and planes (3.1.3)

Pkl2
Nkl2

(a) Selection by threshold of an inner product.

Transformation of range data to global coordinate system
Search of plane which corresponds
to each point of the plane portion (3.1.2)

Qx1

Pkl1

ET =

U
X


distance(Qu , PQu) → min,(2)uwhere Qu and PQu
are Qu and PQu after transformation by(RQu , TQu ) and (RPQu , TPQu ), and the orientations estimated in step 1 are fixed.
The corresponding plane is searched again after the step 2 andthe process is iterated until the solution is converged. Downhill
simplex method in multidimensions (17), which does not needthe derivatives, is used for the optimization.

3.2 Polygonization of Range Data
A polygonal representation is generated from each range data byconnecting four corners of each region defined as a plane portionin the plane detection process in order to reduce the number ofpolygons. In a non-plane portion, a polygon is generated by connecting adjoining pixels which are neighbors of pixels and oneof diagonal neighbors of pixels. A range data partially overlaps
other range data. The quantity of data is reduced by removing
redundant polygons at overlapping regions. Polygons are generated from range data in order of input. The generated polygons which correspond to the vertices of the generating polygon
with the method described in Section 3.1.2. are searched. Whendistances between vertices and intersection Qx are less than athreshold, the polygon is deleted as a redundant one as shown in
Fig. 5. Note that only the polygon defined as a plane portion isdeleted to maintain the quality of model and to reduce the amountof data.

sensor position
generated 3D model

non-measured portion
Generated polygon

Overlapping polygon

Vertex of the generating polygon

cross section

Correspondence of point and plane

Figure 5: Deletion of overlapping areas.

point Pilaser
corresponding point Xpi

Figure 7: Search of the corresponding point. (The case whichtake up a certain scan line.)

Figure 6: Non-measured portions of generared 3D model
4 INTEGRATION OF STOP-AND-GO ANDCONTINUOUS SCANNING
This section describes the method for integrating the range data
which are acquired by stop-and-go and continuous scanning. 3D
surface model which is generated from the data acquired by stopand-go scanning has non-measured portions as shown in Fig. 6(white portions). The non-measured portions exist sparsely in theenvironments measure by stop-and-go scanning mode at multiple points using an omnidirectional rangefinder. Therefore, theproposed method attempts to reduce the non-measured portions
and time for measurement of environments by continuous scanning mode using a line scanner. The positions and orientationsof rangefinder during movement are measured by the hybrid sensor which consists of a RTK-GPS and an INS sensor. The positions and orientations of rangefinder during measurement are
optimized by registering the range data acquired in continuous
scanning mode into the generated model from stop-and-go scanning.
In continuous scanning, the positions and orientations of rangefinder are continuously measured by the hybrid sensor. Since theaccuracy of GPS is dependent on the state of an electric wave,
it is difficult to maintain the high accuracy. Therefore, positions
and orientations acquired by the hybrid sensor are used as initialvalues for registration and are optimized by registering continuous scanning data with the model generated in Section 3. In thecase of registration process for the data acquired in the stop-andgo scanning mode, in order to exclude complex objects such as
trees, plane portions are detected from range data and only theplane parts are used for registration. For the same reason in continuous scanning, straight lines are detected from each scan lineof range data, and only the straight line parts are used for registration. Procedure of registration is shown in the following.
1. Straight lines are detected from each scan line of range databy straight line fitting by downhill simplex method in multidimensions (17).

2. The point corresponding each point Pi (i = 1, · · · , I) is
searched from generated 3D surface model as shown in Fig.
7. The point corresponding to Pi is defined as XP i whichis intersection of the laser beam on Pi and the generated
model.
3. The transformation matrices MP i are estimated by minimizing the error which defined as the sum of distances between corresponding points as follows.
I ˛
˛
X
˛
˛
E=
˛(MP i Pi )XP i ˛ → min.
i=1

4. If the solution does not converge, return to 2.
5 EXPERIMENTS
We have carried out experiments of registration of range 3D modeling by integrating the data acquired in the stop-and-go and continuous scanning modes. In stop-and-go scanning, the omnidirectional range images are acquired at 68 points in our campus(about 250m × 300m). Since the proposed registration method
requires overlapping portions among range data in stop-and-goscanning, we have acquired the omnidirectional range data approximately at 30m interval. The resolution of each omnidirectional range image is 1024×512. A cluster system consisting of
24 PCs (CPU: Pentium4 1.7GHz, Memory: 1024MB) is used forfinding corresponding planes, and a single PC (CPU: Pentium4
1.8GHz, Memory: 2048MB) is used for registration of multiple
omnidirectional range data. The time required for registration isabout 7 days. The generated 3D surface model from the data bystop-and-go scanning is shown in Fig. 8. From Fig. 8 we confirm
that the generated model has no large distortion.
In a preliminary experiment of continuous scanning, the data acquisition area and the path of sensor system for measurement of
the non-measured portions are determined manually. The data areintegrated by registering the range data acquired by continuous
scanning into the generated 3D surface model. The 3D surface
model is generated from the 3 range data acquired by stop-andgo scanning. In continuous scanning, the rangefinder by which
the direction was fixed is used as a line scanner for acquisition ofdata, and range data of 1000 lines are acquired in the 70m path.
The range image acquired by continuous scanning is shown in
Fig. 9. The sensor system has been already aligned among sensor coordinate systems and timing of data acquisition. The 3D

[5] M. Okutomi and T. Kanade: “A Multiple-baseline Stereo,”
IEEE Trans. on Pattern Analysi and Machine Intelligence,Vol. 15, No. 4, pp. 353–363, 1993.
[6] S. F. El-Hakim, C. Brenner, and G. Roth: “A Multi-sensor
Approach to Creating Accurate Virtual Environments,” Jour.
of Photogrammetry & Remote Sensing, Vol. 53, pp. 379–391,
1998.
Figure 9: Range data acquired by continuous scanning.
surface model used for the experiments is shown Fig. 10(a), andthe range data acquired by continuous scanning is shown 10(b).
It is assumed that the range data of one scan line is acquired at
the same position and orientation, and the sensor motion are optimized on the condition that the position and orientation between
sequential scan lines vary smoothly. The results of registration
are shown in Fig. 11. Although the model registered by only the
positions and orientations which are acquired by hybrid sensor
includes distortion in some parts in Fig. 10(b), from Fig. 11 we
confirm that the registered data is revised correctly.
6 CONCLUSION
This paper has proposed a 3D modeling method which integrates
the data acquired in stop-and-go and continuous scanning modes
using a rangefinder for the reduction of non-measured portions.
In stop-and-go scanning, a 3D model is generated from omnidirectional range images acquired at multiple positions. We haveconfirmed that the model has no large distortion. However, we
can observe many small data lacking portions mainly caused by
occlusions in the generated model. The data lacking portions aremeasured by continuous scanning. In a preliminary experimentof continuous scanning, the data acquisition area and the path of
sensor system for measurement of the non-measured portions are
determined manually. The data are integrated by registering thedata acquired by continuous scanning using a line scanner to themodel generated from the data by stop-and-go scanning. We haveconfirmed that the non-measured positions are reduced by registering the data acquired by stop-and-go and continuous scanning.
We are planning to control the direction of rangefinder for measurement of non-measured portions by storing the generated modelin a measurement system and automatically detecting the nonmeasured portions.
REFERENCES[1] T. Sato, M. Kanbara, N. Yokoya, and H. Takemura: “Dense
3-D Reconstruction of an Outdoor Scene by Hundreds-baseline
Stereo Using a Hand-held Video Camera,” International Jour. of
Computer Vision, Vol. 47, No. 1-3, pp. 119–129, 2002.
[2] S. Ozawa, M. Notomi, and H. Zen: “A Wide Scope Modeling to Reconstruct Urban Scene”, Proc. ISPRS Commission V
Int. Symposium on Real-Time Imaging and Dynamic Analysis,
pp. 370–376, 1998.
[3] C. Tomasi and T. Kanade: “Shape and Motion from Image
Streams under Orthography A Factorization Method,” International Jour. of Computer Vision, Vol. 9, No. 2, pp. 137–154,
1992.
[4] M. Pollefeys, R. Koch, M. Vergauwen, A. A. Deknuydt, and
L. J. V. Gool: “Three-demintional Scene Reconstruction from
Images,” Proc. SPIE, Vol. 3958, pp. 215–226, 2000.

[7] H. Zhao and R. Shibasaki: “Reconstruction of Textured
Urban 3D Model by Fusing Ground-Based Laser Range and
CCD Images,” IEICE Trans. Inf. & Syst., Vol. E-83-D, No. 7,
pp. 1429–1440, 2000.
[8] P. K. Allen, A. Troccoli, B. Smith, S. Murray, I. Stamos, andM. Leordeanu: “New Methods for Digital Modeling of Historic
Sites,” IEEE Computer Graphics and Applications, Vol. 23,
pp. 32–41, 2003.
[9] Y. Sun, J. K. Paik, A. Koschan, and M. A. Abidi: “3DReconstruction of Indoor and Outdoor Scenes Using a Mobile
Range Scanner,” Proc. International Conf. on Pattern Recognition, Vol. 3, pp. 653–656, 2002.
[10] H. Zhao and R. Shibasaki: “Reconstructing a Textured
CAD Model of an Urban Environment Using Vehicle-Borne
Laser Range Scanners and Line Cameras,” Machine Vision andApplications, Vol. 14, No. 1, pp. 35-41, 2003.
[11] C. Früh and A. Zakhor: “An Automated Method for LargeScale, Ground-Based City Model Acquisition,” International
Jour. of Computer Vision, Vol. 60, pp. 5–24, 2004.
[15] P. J. Besl and N. D. McKay: “A Method for Registrationof 3-D Shapes,” IEEE Trans. on Pattern Analysis and MachineIntelligence, Vol. 14 No. 2, pp. 239–256, 1992.
[12] C. R. Gunadi, H. Shimizu, K. Kodama, and K. Aizawa:“Construction of Large-scale Virtual Eenvironment by Fusing
Range Data, Texture Images and Airbone Altimetry Data,”
Proc. Int. Symposium on 3D Data Processing, Visualization andTransmission, pp. 772-775, 2002.
[13] T. Asai, M. Kanbara, and N. Yokoya: “3D Modeling of
Outdoor Environments by Integrating Omnidirectional Range
and Color Images,” Proc. Int. Conf. on 3-D Digital Imaging andModling, pp. 447–454, 2005.
[14] Y. Kanazawa and K. Kanatani: “Reliability of Fitting a
Plane to Range Data,” IEICE Trans. on Information and Systems, Vol. E78-D, No. 12, pp. 1630–1635, 1995.
[16] K. Pulli: “Multiview Registration for Large Data Sets,”
Proc. International Conf. on 3D Digital Imaging and Modelling,pp. 160–168, 1999.
[18] W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T.
Vetterling: Numerical Recipes in C, Cambridg University Press
1988.

Figure 8: Gennerated 3D model with texture from the data which are acquired by stop-and-go scanning.

(a) Generated 3D model from the data acquiring by(b) Data acquiring by continuous scanning.
stop-and-go scanning.
Figure 10: Acquired model data.

Figure 11: Integration results of stop-and-go (gray) and continuous (white) scanning.