Data Acquiring Support System Using
Recommendation Degree Map for 3D Outdoor ModelingToshihiro ASAI, Masayuki KANBARA, Naokazu YOKOYA
Graduate School of Information Science, Nara Institute of Science and Technology,
8916-5 Takayama, Ikoma, Nara 630-0192, Japan
ABSTRACT
We propose a support system of range data acquisition by a laser rangeﬁnder for wide area outdoor modelingin order to reduce un-observed portions of generated model. The system presents the operator a recommendation degree map which illustrates recommendation position of acquisition of range data in the objective area.
The operator decides a next acquisition position in consideration of movement distance of sensor system andrecommendation degrees of the map. The recommendation degree is computed by measurement density as theindex. The recommendation degree at a position is given by the diﬀerence between measurement density acquired by rangeﬁnder and measurement density estimated by the system in reachable area of the laser beams.
The reachable area of the laser beams is estimated by using a 3D model generated from the acquired range data.
The system computes the measurement density by the reachable area of the laser beams. The recommendation
degrees in the objective area are computed by the model generated from range data whenever a range data is
acquired. Moreover, the system judges whether overlapping portions of the range data can be acquired for theregistration by ICP algorithm from a work area which the sensor system can enter.
Keywords: support system of data acquisition, 3D modeling of outdoor environment, laser rangeﬁnder, recommendation degree

1. INTRODUCTION
Recently, automatic 3D modeling methods of wide outdoor environments are widely investigated by developmentof a laser rangeﬁnder which can measure object with high accuracy. The generated model is expected to apply
in various applications such as simulation, navigation and virtual tour1–3 . Since the measurable portions ofrangeﬁnder are generally limited to the area which laser beam has reached, it is diﬃcult to measure whole
objects in the outdoor environments in one measurement by the rangeﬁnder. To obtain the whole shape ofobjective area, we have to acquire range data from many diﬀerent positions and to precisely register them.
Un-observed portions caused by occlusions etc. as shown in Fig. 1 become deﬁcits of the model.
View planning methods which estimates optimal position and orientation of the rangeﬁnder to eﬃciently
reduce the un-observed portions have been proposed4–6 . The methods generally estimate an optimal positionand orientation of a rangeﬁnder with the most amount of reduction of un-observed portions. The conventional
methods which compute the optimal position and orientation by using 3D model generated from acquired range
data have been proposed5, 7 . 3D model is separated into observed and un-observed portions by acquired model.
The optimal position and orientation are estimated by computing the amount of reductions from the model. An
accurate registration of range data which are reﬂected to the 3D model is required in order to precisely computethe amount of reduction of the un-observed portion. Allen et al. compute optimal position and orientation ofa rangeﬁnder by shapes of un-observed portions which are estimated from the neighboring observed shapes ofthem5 . This method assumes that the shapes of object area are almost measured in order to estimate the shapesof un-observed portions and as such, is diﬃcult to apply to environments in which range data is not acquired yet.
The methods mainly target indoor7 , it is easy to precisely obtain the position and orientation of a rangeﬁnder
by using markers and sensors etc. These view planning systems realize an interactive support of data acquisition
by registering the acquired range data on the spot.
E-mail: {toshih-a, kanbara, yokoya}@is.naist.jp

Figure 1. Deficits of the model by occlustions.

However, in order to estimate the position and orientation of a rangeﬁnder precisely, it is diﬃcult to use themarkers and sensors etc. in the outdoor environment. ICP algorithm8 is generally used for registration of range
data. This algorithm requires the overlapping portions among range data. Surmann at el. register range data
by using ICP algorithm and automatically generate a 3D model with an autonomous mobile robot9 . Since themethod does not consider whether overlapped portion of the acquired data can be measured enough to register
the range data, it may be failed to register them.
We propose a support system for an operator of sensor system to eﬃciently acquire the range data in outdoor
environments. The system presents the operator a recommendation degree map which illustrates recommendation
position of data acquisition in the objective area. The operator decides a next acquisition position by seeing themap. The system computes the amount of reduction of the un-observed portions at each position by a voxel
model in the objective area by updating the voxel model with registered range data on the spot. Note that thesystem does not take into consideration an orientation of the rangeﬁnder in the computation of recommendation
degrees by using the omnidirectional rangeﬁnder. Since the general rangeﬁnder for outdoor modeling radiates
laser beams radially, the measurement density of object depends on the distance from the rangeﬁnder. The
recommendation degree is computed by measurement density as the index. The recommendation degree ata position is given by the diﬀerence between measurement density acquired by rangeﬁnder and measurement
density estimated by the system in reachable area of the laser beams. The reachable area of the laser beams is
estimated by using a 3D model generated from acquired range data. In order to register range data by plane based
ICP algorithm which we proposed10 , the system judges whether the overlapping portions can be acquired fromthe work area which the sensor system can enter. The system computes the overlapping rates of plane portions
by using the 3D mode. System uses a GPS and an INS sensor to obtain an initial value of a transformation
matrix of acquired range data in the registration. The GPS is also used to show the operator a current position.
The system generates the 2D map showing recommendation degrees at the positions where overlapping planeportions of range data can be acquired for registration process. The operator decides next acquisition positionin consideration of movement distance of the sensor system and recommendation degrees of the map.
This paper is structured as follow. Section 2 describes a design and a detail of the proposed system. In
section 3, experimental results are shown. Finally, Section 4 gives summary and future work.

2. SUPPORT SYSTEM OF RANGE DATA ACQUISITIONIN OUTDOOR ENVIRONMENT
2.1. Design of the support system
The purpose of the proposed system is to support the data acquisition of the outdoor environments eﬃciently
on the spot. To realize this purpose, the following requirements should be satisﬁed.
(a) Online processing of computing recommendation degree
The proposed method presents the operator a recommendation degree map which illustrates recommendation
position of data acquisition on the spot. The map is generated whenever a range data is acquired. The systemstartAcquisition of range dataprocessing by the system
Decision by the system

Plane detection
Movement to the next position

Registration of range dataprocessing by the operator
Decision by the operator

Success judgmentof registration
succeedfailedUpdate of voxel dataNormal vector of plane portion
Reflection probability of laser beam
Maximum measurement density

Estimation of ground height
Computation of recommendation degree
Generation of the map illustrating
the recommendation degree

continue

End judgmentof acquisition
end

end

Figure 2. Flow diagram of proposed method.

gives priority to speed over the accuracy in the computation of recommendation degree, in order to shorten waitingtime of the computation so that the operator may not feel a burden. The system generates a voxel model fromacquired range data by using voxel carving approach11 with low computation cost. Recommendation degree ata position is computed from measurement density of each voxel which is observed at the position in the work
area of the sensor system.
(b) Presentation of recommendation degree to operator with 2D map
In the outdoor environment, the work area and move path of a rangeﬁnder are restricted. System presents
the operator the 2D map which shows recommendation degrees in the work area. The operator decides thenext acquisition position in consideration of movement distance of the sensor system and measurement degreesof the map. The proposed method assumes that an altitude corresponds to a pair of latitude and longitude.
The altitudes of the ground in the work area are estimated from registered range data. The system computes
recommendation degrees in the work area of the sensor system where altitudes are known. Moreover, the systemjudges whether the plane portions can be acquired for registration at the work area by using the voxel model.

2.2. Detail of the support system
A ﬂow diagram of proposed method is shown in Fig. 2. First, the operator decides the measurement position inconsideration of movement distance of sensor system and recommendation degrees of the map which illustrates
the recommendation degree. The recommendation degrees in the work area are computed by the reachable areaof laser beam. The voxel model is used to estimate reachable area of laser beam. When the operator acquires newrange data, system immediately updated the voxel model by using the registered new range data. The operator
decides the next acquisition position or end of measurement by the map with which the recommendation degrees
have been reﬂected.
2.2.1. Registration of range data
We have proposed a plane based ICP algorithm for range data acquired in outdoor environments10 . The
registration method applies to the system because the method10 can stably register range data in outdoor
environments. The registration in the proposed method is not a simultaneous registration of multiple range data
but a sequential registration of newly acquired range data only. The position and orientation acquired by usinga GPS and an INS sensor are used as initial value of transformation matrix for registration of the acquired range
data. The plane portion and its normal vector are estimated by plane detection.
Plane portions of range data are detected by local plane ﬁtting. We employ the renormalization method12
for estimation of plane parameters and the quadtree segmentation recursively. The range data is stored by thedata structure of the two-dimensional array, the whole array is taken as an initial region. The distances between
estimated plane and 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, the region is deﬁned
as a plane portion. The points which are not deﬁned as a plane portion are not used in registration process.
2.2.2. 3D voxel model for computation of recommendation degree
The voxel model is used to compute recommendation degrees at a position in the work area of sensor system. The
reachable area of the laser beams from a position is estimated by using a voxel model generated from acquired
range data. The recommendation degree at a position is the sum of diﬀerence between a measurement density
acquired by rangeﬁnder and a measurement density estimated from the position at each voxel in reachable areaof the laser beams. A number of laser beams which can measure the plane portions is also estimated by thereachable area. The system judges whether range data acquired at the position can be registered by the number.
The components of a voxel are described in the following.
(a)Reflectance probability of laser beam
The voxel model requires a huge amount of memory in a wide area environment like the outdoors, it is necessary
to make the resolution of a voxel space low. However, when the resolution of the voxel space is low, it is diﬃcult
to precisely estimate the reachable area of the laser beams from a position in the work area of the sensor system.
In the proposed method, each voxel has a reﬂectance probability of laser beam as a rate of object occupancy inthe interior of the voxel. System computes the probability which a laser beam reaches to a voxel from a position
by using the reﬂectance probability of the voxels. The recommendation degree at a certain position is deﬁned assum of products of the diﬀerence of measurements density and the probability which laser reaches at each voxel.
The reﬂectance probability of a voxel P is deﬁned as P = t/(t + f ), where t is a number of reﬂections, f is anumber of passages of laser beam in the voxel. The voxels which a laser beam passes or reﬂects are searched byusing the Bresenham line drawing algorithm13 . When a laser beam did not reﬂect, it is assumed that the beam
passed to measurable range of a rangeﬁnder.
(b)Maximum measurement density
Since a laser rangeﬁnder for outdoor environments generally radiates laser beams radially, the measurement
density of object located in the distance from the rangeﬁnder is low. In order to improve the generated model,
the proposed method computes the recommendation degrees by the measurement density as the index. The
maximum measurement density of a voxel is estimated from acquired range data. The measurement density isgiven by R/r, where let R and r be the resolution of range data and distance between acquisition position andvoxel.
(c)Normal vectors of plane potions
The registration requires the overlapping plane portions among range data. The normal information of the planeportion is used to judge whether the plane portions can be acquired at a position in the work area of the sensor
system. The information is stored in the voxel where detected plane portion by the method described in 2.2.1
exists. When multiple planes exist in the voxel, the voxel has all normal information of them. The acquirable
plane portions at a position in the work area are estimated by an inner product of vector of laser beam from theposition and its normal vector stored in the voxel.
2.2.3. Computation of recommendation degree
The recommendation degree is deﬁned as an extent of object shapes which can be measured more minutely thanacquired range data by the rangeﬁnder. The recommendation degree is given by sum of the product of thediﬀerence of measurement density and probability which the laser beam reaches in all the voxels. The diﬀerenceof measurement density means diﬀerence between maximum measurement density acquired by rangeﬁnder andmeasurement density estimated by the voxel model. When range data is acquired at the position P, let Vln (n =1, · · · , Nl ) be the voxels in order of passing laser beam l l(l = 1, · · · , L). Recommendation degree R(p) is deﬁned
as follows:
R(p) =

Nl
L 
n−1




Dl1 Pl1 +Dln Pln(1 − Plm ) ,
l=1

n=2

m=1

(1)

where Dln is given as follows:


Dln =

dln − dln
0(dln > dln )(dln ≤ dln )(2)where let dln and dln be the maximum measurement density of acquired range data and a measurement densityof a voxel Vln from the position p. Reﬂectance probability is set to 1 and maximum measurement density is set
to 0 as initial value of voxel.
2.2.4. Acquisition of plane portions for registration
The system judges whether plane portions of range data can be acquired at a position in the work area of thesensor system for the registration process. The system estimates the number of the laser beams which canmeasure plane portions from the position by using the voxel model. The measurable plane portions from theposition are searched by the normal information stored in each voxel and laser vector from the position to theeach voxel. The system decides the plane portion in a voxel can be acquired from the position when an innerproduct of a laser vector from the position to the voxel and a normal vector of the voxel is less than a threshold.
Plane based registration requires three kind of plane which has diﬀerent normal vector. When a number of laser
beams which can measure plane portions from the position are more than a threshold, system judges that therange data acquired at the position can be registered.
2.2.5. Accelerating computation of recommendation degree by using GPU
The computation of recommendation degree is accelerated by using a GPU which has programmable shader.
The recommendation degree is given by sum of the product of the diﬀerence of density and probability which
the laser beam reaches in all the voxels. Rendering of all the voxels is carried out by same resolution and view
angle with a range data, where let intensity and alpha value be deference of measurement density and reﬂectanceprobability, respectively. The recommendation degree is given by sum of intensities in all the pixels. The normal
vectors of a voxel are quantized per 45 degrees in the horizontal 8 directions and vertical 4 directions. The
quantized normal information is inputted to a GPU as 32-bit ﬂag information. Processing on the GPU, normal
information of a voxel is computed from the ﬂag information. When the inner product of a vector from viewpoint
to a voxel and a normal vector is more than a threshold, the system judges that the plane portion which exists inthe voxel is measurable from supposed acquisition position, and reﬂects in a rendering result using the anothercolor. Although the accuracy of a rendering deteriorates a little, the numbers of the polygon can be reduced
to 1/6 by rendering a voxel as a billboard in which length of edge is same as a voxel, and rendering speed is
improved.

3. EXPERIMENT OF DATA ACQUISITION
We have carried out experiments of data acquisition supported by the proposed system. In this experiment,
the latitudes and longitudes in work area of the sensor system are known. The altitude corresponding to apair of latitude and longitude is estimated from acquired range data. Measurable range of the omnidirectional
rangeﬁnder is 150m, horizontal and vertical angles are set to 360 and 90 degrees and resolution of range data is
set to 1024×512. The voxel size is set to 2m and latitude and longitude are divided in the same size as a voxel,
and let the lowest altitude of range data in the grid be altitude of the grid. The recommendation degrees are also
computed at the same interval as voxel size. In the experiments, the system updates the recommendation degrees
in the area within 50m radius from the position where range data is acquired by voxel data within 50m verticallyand within 200m horizontally from the position. First, the rate of overlapping plane portions for registration
is decided by the simulation experiment. We show the experimental result which has applied the rate in theoutdoor environment.

B

approx.
35m

approx.
35m
approx.
40m
A

Figure 3. Map of the virtual environment.

Figure 4. Bird’s-eye view of the virtual environment.
RTK-GPS(Nikon-Trimble, LogPakII)

Laser rangefinder(Riegl, LMS-Z360)

INS sensor(Tokimec, TISS-5-40)

Figure 5. Car mounted sensor system.

3.1. Simulation in virtual environments
The map and the bird’s-eye view of a virtual environment used for the simulation are shown in Fig. 3 and 4. The
area is approximately 200m square, and the maximum height of building is approximately 40m. The tree models
are placed around buildings in the virtual model like a real environment, become a hindrance of plane detection.
The position and orientation as inputs a GPS and an INS sensor in this experiment are given the following
errors. The position includes the error of which average is 5m and standard deviation is 3m. The orientation
includes the error of which average is 10 degrees and standard deviation is 5 degrees. The experiment supposed
the case which the proposed system is not used and the range data was acquired from point A at intervals of
approximately 30-40m. The data was acquired in order as shown by arrows in Fig. 3. Since suﬃcient planeportions for registration were not acquired, the registration failed in the data acquired at point B. The successconditions of registration are that three kind of plane can be measured at a position in 0.05% or more of all laser
beams.

3.2. Experiment in outdoor environments
We have developed a prototype support system of data acquisition which mainly consists of a desktop PC (CPUPentium4 3.2GHz, Memory 2GB, GPU Gerforce6800, VRAM 256MB), the omnidirectional laser rangeﬁnder(Riegl, LMS-Z360), RTK-GPS (Nikon-Trimble, LogPakII), and INS sensor (Tokimec, TISS-5-40). Fig. 5 illustrates the sensor system mounted on a vehicle. A yaw value measured by the INS sensor generally includes anaccumulative error. The INS sensor is linked with the RTK-GPS in order to correct the accumulative error bymeasuring the direction of movement calculated by GPS data under movement. The processing time required tocompute the degree of recommendation was approximately 0.05ms per position. Total processing time was about
1 minute per one acquisition of range data in this experiment, although the processing time depends on area
where recommendation degrees are computed. A partial shape of objective area generated from acquired range
data is shown in right column of Fig. 6 and each recommendation map from the acquired range data is shownin left column of Fig. 6. The operator conﬁrmed that the generated map shows the position with high degreeof recommendation, as shown in Fig. 6, and decided next acquisition position judging from the map. Since thesystem judged that the acquirable area of overlapping portions of acquired range data was narrow in near the
positions of the 19th - the 22nd and the 41st - the 45th, the acquisition intervals were short. Around there,
Acquisition of the plane portions of acquired range data is actually diﬃcult because of the trees in along theroad. The operator decided for the end of data acquisition after acquiring the 49th range data in this experiment.

4. CONCLUSION
We have proposed a support system of data acquisition for outdoor modeling on the spot by presenting an operator of sensor system the recommendation degree map which illustrates recommendation positions of acquisitionin objective area. The recommendation degree is computed by measurement density as the index. The recommendation degree at a position is given by the diﬀerence between measurement density acquired by rangeﬁnder
and measurement density estimated by the system in reachable area of the laser beams. The reachable area ofthe laser beams is estimated by using a voxel model generated from the acquired range data. Each voxel has areﬂectance probability of laser beam as a rate of object occupancy in the interior of the voxel. System computes
the probability which a laser beam reaches to a voxel from a position by using the reﬂectance probability of thevoxels. Moreover, to register range data by plane based ICP algorithm, the system judges whether the overlapping portions can be acquired from the work area which the sensor system can enter. The recommendation
degrees are computed on the spot whenever new range data is acquired. The computation of recommendation
degree is accelerated by using a GPU. The experiment in the virtual environment has shown availability by the
support system which presents the operator the eﬃcient position in consideration of not only a registration but
a measurement density with recommendation degree map. We have conﬁrmed that the operator could recognize
the eﬃcient position by the map illustrating the recommendation degrees in the objective area.

REFERENCES
1. 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.
2. 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.
3. C. Früh and A. Zakhor: “An Automated Method for Large-Scale, Ground-Based City Model Acquisition,”International Jour. of Computer Vision, Vol. 60, pp. 5–24, 2004.
4. J, Maver and R. Bajcsy: “Occlusions as a Guide for Planning the Next View,” IEEE Trans. on PatternAnalysis and Machine Intelligence, Vol. 15 No. 5, pp. 417–433, 1993.
5. P. K. Allen, M. K. Reed and I. Stamos: “View Planning for Site Modeling,” Proc. DARPA Image Understanding Workshop, pp. 1181–1192, 1998.
6. R. Pito: “A Solusion to the Next Best View Problem for Autmated Surface Acquisiton,” IEEE Trans. on
Pattern Analysis and Machine Intelligence, Vol. 21, No. 10, pp. 1016–1030, 1999.
7. W. R. Scott, G. Roth and J. F. Rivest: “View Planning for Automated 3D Object Reconstruction andInspection,” ACM Computing Surveys, Vol. 35, No. 1, pp. 64–96, 2003.
8. P. J. Besl and N. D. McKay: “A Method for Registration of 3-D Shapes,” IEEE Trans. on Pattern Analysis
and Machine Intelligence, Vol. 14 No. 2, pp. 239–256, 1992.
9. H. Surmann, A. Nüchter and J. Hertzberg: “An Autonomous Mobile Robot with a 3D Laser Range Finder
for 3D Exploration and Digitalization of Indoor Environments,” Jour. Robotics and Autonomous Systems,
Vol. 45, pp. 181–198, 2003.
10. 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 and Modeling (3DIM), pp. 447-454,
2005.
11. Y. Sakaguchi, H. Kato, K. Sato, and S. Inokuchi: “Acquisition of Entire Surface Data Based on Fusion ofRange Data,” IEICE Trans. on Information and Systems, Vol. E74–D, No. 10, pp. 3417–3422, 1991.
12. Y. Kanazawa and K. Kanatani: “Reliability of Fitting a Plane to Range Data,” IEICE Trans. on Informationand Systems, Vol. E78-D, No. 12, pp. 1630–1635, 1995.
13. J. E. Bresenham: “Algorithm for Computer Control of a Digital Plotter,” IBM Systems Jour., Vol. 4, No. 1,
pp. 25–30, 1965.

Recommendation degree
low

high

Acquisition positionof range data

The area where rangefinder
cannot enter

1st acquisition.

18th acquisition.

49th acquisition.
Figure 6. Recommendation degree map.

Viewpoint in the imageof model