View Planning for Automated Site ModelingPaul S. Blaer and Peter K. AllenDepartment of Computer Science, Columbia University{pblaer,allen}@cs.columbia.eduAbstract— We present a systematic method for constructing3-D models of large outdoor sites. The method is designed fora mobile robot platform and incorporates automated acquisitionof scanned data as well as automated view planning and modelconstruction. In our modeling process, we first use a preliminaryview or set of preplanned views to yield an initial, approximate,3-D model of the target structure. Then, we update this model byusing a voxel-based procedure to plan and acquire the next bestview. This updating is repeated sequentially until an accurateand complete 3-D model is finally obtained. The method wassuccessfully tested on a portion of the Columbia Universitycampus.I. INTRODUCTIONAccurate three-dimensional models of large outdoor struc-tures, such as buildings and their surroundings, have manyuses. These models can provide an educational walk arounda structure that is thousands of miles away. They can allowengineers to analyze the stability of a structure and then testpossible corrections without endangering the original. Theycan allow us to preserve historical sites that are in danger ofdestruction, and they can allow us to preserve archaeologicalsites at various stages of an excavation. In all of these cases,it is important to have an accurate computer based 3-D modelof the large scale outdoor structure.Methods for acquiring such models have progressively in-creased in accuracy and have evolved from manual methods tomore automated methods. At the simpler end of the spectrum,one can send a team of surveyors to take measurements byhand and then have a designer put together a model fromthose measurements. More sophisticated tools do exist. Thereare a number of laser range scanners on the market that willquickly generate a dense point cloud of measurements. With asufficient number of scans around the object being measured,one can generate models of centimeter or better accuracy.Although the models obtained by laser scanning are nowvery accurate and the acquisition process is fast and automated,there is still a major human component involved. The scanningsensor must be physically moved from location to location,and each scanning operation itself can take up to one hourdepending on the type of sensor and the density of the scan.In addition, a plan must be laid out to determine where to takeeach individual scan. This requires choosing efficient viewsthat will cover the entire surface area of the structure withoutocclusions from other objects and without self occlusions fromthe target structure itself. This is the essence of the so–calledview planning problem.We propose to automate this view planning task by mount-ing the scanning equipment on a mobile robot platform,AVENUE [1] (see Fig. 1), that is capable of localizing andnavigating itself through an urban environment. View planningsoftware for model construction is then added to the robot’snavigation system. This paper presents our work on the viewplanning component of this system.Our method of model building has two basic steps. In aninitial static modeling phase, the system acquires a preliminaryview or set of views of the target region. In the second phase,a voxel-based method is used to choose the next best viewfrom information in the initial model. This phase now becomesdynamic as each new scan updates our model and providesnew information for the next best view. The entire methodcan produce an accurate and complete 3-D model of largecomplicated structures.II. RELATED WORKCurrently there are a number of other research projectsattempting to construct three-dimensional models of urbanscenes and outdoor structures. These projects include the 3-Dcity model construction project at Berkeley [2], the outdoormap building project at the University of Tsukuba [3], theMIT City Scanning Project [4], and the volumetric roboticmapping project by Thrun et al [5] which initially focusedon the mapping of mines but has recently been extended tooutdoor scenes. For the most part, however, these methodsleave the actual planning component to a human operator.The view planning problem can be described as the taskof finding a set of sensor configurations which efficientlyand accurately fulfill a modeling or inspection task (see [6]and [7]). The literature can be divided into three separatecategories. The first two deal with model-based and non-model-based methods. The third describes methods applicableto view planning for a mobile robot.The model-based methods are the inspection methods inwhich the system is given some initial model of the scene.Early research focused on planning for 2-D camera-basedsystems. Included in this are works by Cowan and Kovesi [8]and by Tarabanis et al [9]. Later, these methods were extendedto the 3-D domain in works by Tarbox and Gottschlich [10]and by Scott et al [11]. We can also include the art galleryproblems in this category. In two dimensions, these problemscan be approached with traditional geometric solutions suchas in Xie el al [12] and with randomized methods such as inGonz´alez-Ba˜nos et al [13]. The art gallery approach has alsobeen applied to 3-D problems by Danner and Kavraki [14].The non-model-based methods seek to generate modelswith no prior information. These include volumetric methodsFig. 1. On the left is the ATRV-2 based AVENUE Mobile Robot. In the center is a photograph of our test case, Uris Hall, taken from the roof of a neighboringbuilding (picture courtesy of Alejandro Troccoli). On the right is a 2-D map of the building footprints on the northern portion of the Columbia campus. Alsoshown on the right are the 9 scan locations (shown as black dots) determined by the initial two-dimensional view planner of method B. The views from theselocations cover 95% of the 2-D outline of Uris Hall.such as Connolly [15], Banta et al [16], Massios and Fisher[17], and Soucy et al [18]. There are also surface-basedmethods which include Maver and Bajcsy [19], Pito [20], Reedand Allen [21], and Sequeira et al ([22], [23]). A statisticalapproach is taken by Whaite and Ferrie [24].View planning for 2-D map construction with a mobile robotis addressed by Gonz´alez-Ba˜nos et al [25] and Grabowski etal [26]. View planning for 3-D scenes with a mobile robot isaddressed by N¨uchter et al [27].III. PLATFORM AND ENVIRONMENTThe platform for this project