A Technique for 3D Modelling of Buildings
Taejung Kim and Soon Dal Choi
Satellite Technology Research Center
Korea Advanced Institute of Science and Technology
373-1, KuSung-Dong, YuSung-Gu, Taejun
Korea
Phone: +82-42-869-8629, Fax: +82-42-861-0064
E-mail: tjkim@satrec.kaist.ac.kr
Abstract
A fully automated technique has been developed for 3D mapping of buildings from high resolution aerial and space imagery ..This paper will briefly describe the basic principles of the technique and present the results .." from various images-
The technique consists of three parts: building height extraction, building detection, and 3D modelling.. For building height extraction, a pyramidal matching algorithm has been developed.. This algorithm emphasises .the control between levels in order to reduce the blunder propagation.. For building detection, anew graph- r,. based algorithm has been developed.. This algorithm extracts lines from single image and store them and their ~ relationships in a graph. Building hypotheses can be generated by finding closed loops in the graph." 3D modelling of buildings can be achieved by combining the results from building height extraction and ..building detection. Buildings are modelled as planar or apex surfaces and heights from pyramidal matching are assigned to these surfaces.. Building detection output is used as interpolation boundaries.. The results from various images show that the developed technique can model buildings successfully.
I. Introduction
The extraction of man-made objects from remotely-sensed imagery is one of the fundamental tasks in remote ~ sensing as well as in image understanding. In particular, man-made objects such as roads or buildings are important features in urban areas and techniques to extract them have numerous applications in urban icc", mapping, urban planning and Geo-Information engineering.There have been several app~oaches prposed for automated building extration.. The most pular ones are perceptual groupIng [I] and lIne analysIs [2,3].. The use of shadow InformatIon and perspectIve geometry has .' also been used by manyauthors [4,5].. However, the nature of buildings in real world necessitate the need to ; include 3D analysis in building extraction: building detection performed in 2D cannot fully "understand"buildings in the scene.. For such purpose, stereo matching has been used with the combination of other approaches mentioned before. However, building extraction (in 3D) remains still difficult as it requires not only good low-Ievel vision techniques such as edge or line extraction but also good middle-level or high-Ievel vision techniques such as cognition and interpretation..
This paper describes a new approach developed for automated 3D building extraction.. The new approach uses a stereo matching technique to retrieve 3D information on buildings and a buitding detection technique to "recognize" buildings in 2D.. These two techniques are combined for 3D buitding e>.iraction.. The next section will describe briefly the principles of this approach.. In section 3. some results or building extraction will be presented.. Conclusions and future work will be discussed in section 4..
2. A new technique
The new technique can be divided by three parts: height extraction using a pyramidal matching algorithm,
building detection using a line-relation graph and 3D modelling of buildings using the results from height
extraction and building detection. This section will describe each of them briefly. Interested readers should
refer [3,6,7,8] for more detailed explanation.
2.1 Height extraction
For height extraction, a pyramidal matching technique was proposed and proved effective. Due to the nature ofbuildings, there are many abrupt discontinuities in any scene containing buildings. This violates theassumption of contiguous disparity field, which almost all stereo matching algorithms adopt. Previousexperiments with a adaptive least squares correlation matching algorithm showed that buildings in a scenemake blunders and isolated regions for stereo matching [6].pyramidal matching can partly solve these problems: it can reduce the magnitude of height discontinuities and hence) the number of isolated regions by averaging down the image resolution; it can also enhance stereo matching by utili sing the matching results of lower resolution as the initial guess for higher resolution matching; it can also enable a fully automated system by using automatically generated initial guess at the lowest resolution matching.
One of the difficulties for any pyramidal matching approaches is the problem of "blunder propagation" : errors at the lowest resolution are amplified through image pyramid. In order to minimize this problem, a tile-based control strategy was developed. Tiles with a given size are defined across the image plane and only the best matched point within a tile is selected as the initial guess for the next resolution matching. This pyramidal matching algorithm was tested with many aerial and space come images and it produced successful results [9,10]. The results of experiments were reported elsewhere.
2.2 Building detection
For building detection, a graph-based algorithm was developed [3]. This algorithm generates building hypotheses by line analysis and then verifies them using shadow information and/or perspective geometry. This algorithm needs only a single image and building detection is performed in two dimension.
Firstly, lines are extracted in an image using several steps: edge elements are detected by a Canny-Petrou- Kittler filter; a connected edge labelling algorithm is applied; two end-points of a linear elements are searched for With end-point templates. A line is defined with two end-points. Small lines broken from a long line and parallel lines with a narrow gap are merged. .
Secondly, the relations between lines are searched for. The line relations are classified as positive, negative, or parallel connection. The value of connection is also defined accordingly. Lines and line relations (type and value of connections) are stored in s graph. The nodes of the graph consist of lines and the arcs the relationship between lines.
Thirdly, the system generates building hypotheses by finding closed loops in the line-relation graph. To traverse a graph, a depth-first search algorithm is used. In order to make sensible building hypotheses, the search is limited by some connection rules and the maximum number of nodes it visits. However, experiments with this method revealed some limitations, the main one being unable to generate any building hypothesis where lines from one or more sides of a building are missing. To overcome this limitation, the concept of "super" building hypothesis, the building hypothesis generated from a "U"-shaped chain, is introduced.
Finally, building hypotheses are verified. Similar building hypotheses are merged and some small building hypotheses are removed. Similarity is defined when building hypotheses have all identical components but one in their search chains. Shadow analysis is performed and lines in a scene are classified into ground-level and
building-level lines. False building hypotheses, which contains any ground-level line, are removed. For an oblique viewing geometry, vertical lines can be visible in a scene and perspective geometry can be used to verify building hypotheses. After detecting vertical lines, lines are also classified into building-level, middle- evel, and ground-level lines. Building hypotheses which consist of alone building-level lines are verified.
After the verification procedure, a building hypothesis represents a whole or part of a building.
2.3. 3D modelling of buildings
One of the weakest application areas of any mono scopic approach is the extraction of height or depth information. The building detection system described above suffers from the same drawback. Although some .indication of building height may be possible by shadow analysis and perspective geometry , the system cannot provide accurate information on building height. Stereo matching results usually give accurate height information. However, height is assigned only on grid-points and it is difficult to obtain the height of objects such as building roofs without further processing. Also ...there is a problem of height for urban areas. In such areas, the surface does not vary in a geo-statistical manner. Large areas of the surface are very flat or linearly varying and there are many cliffs due to building ..boundaries. Hence "kriging", one of the common techniques for height interpolation, cannot be applied. Height- interpolation requires external guidance or, alternatively, a proper statistical model of the surface should be modelled.
The fusion of stereoscopic and monoscopic cues can potentially solve these problems [8] .Rich height information from the stereoscopic process can be used to assign height onto buildings. Building hypotheses t, detected by the monoscopic process can provide the external guidance of height interpolation so that interpolation only takes place within the boundary of a building hypothesis.
From the pyramidal matching technique described in section 2.1, a matching list can be generated. From the building detection system described in section 2.2, building hypotheses are generated. Each building hypothesis provides interpolation boundaries and matched points in a matching list provide height " information. Using the matched points which fall in a building hypothesis, coefficients of a surface model of a building hypothesis are calculated. Interpolation is then performed using the surface model equation.11Three surface models were considered for building roofs: a planar, an apex, and a quadratic surface model. The.coefficients of each model can be calculated using the matched points within a building hypothesis through
"least squares estimation. The estimation errors of three models are then compared and the model with the least : error is chosen as a proper surface model. However, previous experiments have shown that a quadratic surface .model has an unacceptable error when the number of modelling points is too small and these points are not ..well-distributed in a building hypothesis. Although there may be dome structures in a scene, these are rare and , could be dealt with by specialised processes. The quadratic surface model was, therefore, discarded. The surface is assumed to be either planar or apex. Also, if the estimation error of a surface model is larger than .some threshold value, the surface model is not accepted and a building hypothesis remains un-modelled. Afterchoosing a proper surface model, interpolation can be done simply by calculating the corresponding height using the surface model equation.
