Triangulation Algorithm in the Application of the 3 d Model Elevation Reconstruc

开篇：润墨网以专业的文秘视角，为您筛选了一篇Triangulation Algorithm in the Application of the 3 d Model Elevation Reconstruc范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

Abstract：With the "Digital Earth" concept put forward, people are starting to focus on geospatial information technology. Traditional manual process of building modeling process gradually eliminate by history due to cumbersome and inefficient work. With massive data storage and processing technologies emerge and gradually improved, people began to explore measured by laser radar technology building point cloud data, the use of point cloud data processing software for further building boundary extraction. Model boundary extraction process, using the prototype with the model fit is good, clear and easy programming algorithm triangulation algorithm.

Keywords: triangulation, point cloud data, boundary extraction, data processing

中图分类号：C37文献标识码：A文章编号：2095-2104(2013)

Ⅰ.Introduction

With the "Digital Earth" and "Digital City" concept put forward geospatial importance of information technology gradually people pay attention to it. Expansion of storage space and data processing speeds increased, it is so massive data processing well with its "Digital City" and the "Digital Earth" building better together. After the 1970s, the advent of laser radar technology, geographic mapping technology and other buildings from the traditional manual data measured and stored, and gradually move towards high-precision, high-speed, high efficiency and standardization of spatial data processing is also gradually moving towards intelligent. Therefore, the non-contact measurement and high-efficiency measurement will inevitably become an important means of spatial data

acquisition, and massive spatial data fast, reliable, automated processing is bound to become the core research question.

Ⅱ.LiDAR data types and Microstation v8i under Terrasolid Plug-in Overview

LiDAR data Types Introduction

Point cloud data is obtained by 3D scanner information types. Scan data record in dot pattern, each containing three-dimensional coordinates of a point, and some may contain color information (R, G, B) or the intensity of the object reflector [1]. Point cloud data in addition to geometry, there intensity (Intensity) information, intensity information for receiving the laser scanner unit to capture the echo intensity, the intensity information with the target surface material, surface roughness, the angle of incidence direction, and the emission energy of the instrument, the laser wavelength.

Recently airborne laser scanning measurement system and data processing technology is more mature. Airborne three-dimensional reconstruction is more on terrain and building reconstruction, the idea is that you need to classify the data on different terrain and buildings reconstructing, the terrain is built directly into the plane Delaunay triangulation, planar structures obtained information directly down to the ground. Prior research focused on the top surface of the building information extraction algorithm optimization.

And airborne LiDAR, compared with vehicle-mounted LIDAR point cloud density, flexible acquisition, can also get side close-range image characteristics, but because of the point cloud in a huge number of discrete points, direct extraction of geometric features of the building more difficult, more it is important vehicle platform can only get information on the building facade facing the street, these problems limit the car in the city of laser radar information, access to areas of application, but for targeted applications, such as street applications, automotive laser radar would be a very good choice [2].

B．Terrasolid Introduction

MicroStation and AutoCAD is an internationally famous 2D and 3D CAD design software, the first version in 1986 by the Bentley brothers developed. MicroStation is the one in the building, civil engineering, transportation, processing factories, manufacturing, government, utilities and telecommunications network solutions for areas such as the basic platform. According to the needs of users of MicroStation offers five different levels may be suitable for application developers programming language. Meanwhile, MicroStation has a very strong compatibility and scalability can be achieved through a series of third-party software, many special effects [3].

TerraSolid Series software is the first commercial LiDAR data processing software is developed on Microstation, which runs on top of Micorstation system, which includes: TerraMatch, TerraScan, Terramodeler, TerraPhoto, such as the four common modules. In microstation loaded Terrasolid module shown in Figure 1:

Figure 1.Terrasolid works in microsation v8i

Ⅲ. 3-D model boundary extraction algorithm

Three-dimensional model is three-dimensional boundary extraction groups of buildings and other applications based measurement location. Software such as AutoCAD and SketchUp can already achieve manually restore the three-dimensional structure boundaries. However, with the rapid development of information technology, manual modeling speed has been far behind the people in the three-dimensional modeling of geographic information quality requirements.

A．LiDAR Data Acquisition board

Data sources used in this paper by Wuhan University Remote Sensing and national laboratories provided here to be sincere gratitude.

StreetMapper360 integrated Riegl the VQ-250 laser scanner can be configured according to one or two, mounted to the roof left and / or right orientation. In addition, the roof rack is also equipped with both left and right depending on the AVT Pike F421C-speed color digital imaging systems. Precision positioning and orientation is TERRA-control integrated GPS / IMU system and is equipped with DIA - Direct Inertial Aiding, can effectively solve the problem of GPS signal loss of lock.

B．Data Preprocessing

Outliers removed. In actual aerial flight, due to various factors (specular reflection, the system circuit, etc. obstruction) effects, LiDAR raw data is often abnormal values. Therefore, we need a rough filter processing the raw data, excluding the greater altitude and below ground outliers.

C．Data Correction

LiDAR system includes a laser emitting and receiving means for real-time location information obtained POS system as well as for reflecting the laser beam oscillating mirror three parts, laser emitting device according to set intervals constantly emitting a laser beam, the laser beam hit the reflector mirror, through the swing mirror, reflecting the laser beam onto the ground. The laser beam hits the object, reflection will occur, when the recording airborne return signal receiving apparatus, which records a corresponding data point. When the laser beam is reflected, not all at once reflex. While the laser beams through multiple reflections, the receiving device records the plurality of corresponding data points.

Because of the laser scanner and IMU mis alignment exists between, it takes on the roll angle, tilt, pitch angle and other three placement angle error calibration, used to adjust the laser point data directional difference in the system and improve the accuracy of point cloud data.

D．Data Filtering and Classification

LiDAR point cloud data filtering and classification is the reflection of the laser signal generated by the ground echo signal ground information, buildings, vegetation, roads, bridges and other surface features information extraction process, is the LiDAR point cloud data types separate signals. The corrected point cloud data filtering and classification is to achieve the key technology of building information extraction. According to the laser spot multiple echoes, elevation and downs, elevation texture, laser intensity, aerial photographs and other reference information, design a set of ground, buildings, water, bridges, noise and other automatic classification algorithms laser point cloud processing integrated solutions. According to urban, suburban, mountainous terrain, such as different characteristics of ground classification algorithm parameters corresponding adjustment, automatic classification algorithm can be used on the ground, the roofs of buildings, such as laser spot for fast, automatic classification. Meanwhile, DOM images, laser spot profile information such as a reference, can be laser point cloud editing later hand, to achieve the correct classification of the laser point cloud.

E．Triangulation Algorithm to Extract Building Boundaries

Point set triangulation, for numerical analysis such as finite element analysis, and graphics, it is extremely important to a pretreatment technology. Especially Delaunay triangulation, because of its uniqueness, on a variety of point set geometry and Delaunay triangulation are related. In practice, the use of a maximum of triangulation is Delaunay triangulation, which is a special kind of triangulation. Subject to the following two important criteria:

Empty round features: Delaunay triangulation is unique (any four points cannot be in the same circle), Delaunay triangulation net in any one of circumscribed circle the triangle within the other points will not exist.

Maximize the minimum angle characteristics: scattered point set in the possible formation of triangulation, Delaunay triangulation of the triangle formed by the minimum angle of max. In this sense, Delaunay triangulation is "closest to the rules of the" triangulation. Specifically refers to the two adjacent convex quadrilateral diagonal triangles, in exchange, the six angles of the minimum angle is no longer increases [4]. Figure 2:

Figure 2.Maximize the minimum angle characteristics

Delaunay triangulation has excellent features include:

1)Closest to: the recent three form a triangle, and each segment (triangle edge) neither intersect.

2)Uniqueness: no matter where you start building from the area, will eventually get consistent results.

3)Optimality: any two adjacent triangles formed by the diagonal of the convex quadrilateral interchangeable if so, then the two angles of a triangle six small angle does not become bigger.

4)The most rules: If the triangulation of the minimum angle of each triangle in ascending order, the Delaunay triangulation arranged to get the maximum value.

5)Regional: Add, delete, move only affects one vertex adjacent triangles.

6)The convex polygon Case: triangulation outermost boundary forming a convex polygon shell.

7)Delaunay triangulation is unique among other characteristics make him a triangulation of the most talked about standards.

Triangulation basic ideas and operational processes: principles based on iterative point by point insertion method, the basic idea for the first contains all the data points in a polygon to create the initial triangulation, and then insert the remaining points one by one, using the LOP algorithm [5] or Watson triangle algorithm ensures that relevant data it becomes Delaunay triangulation this paper, this algorithm, the basic steps are as follows:

1)Establish the initial triangulation. obtain a given point set bounding box B (Xmin, Ymin, Xmax, Ymax), the bounding box along the diagonal split into two initial triangles, and then iterate the following steps until all data points to be processed.

2)Positioning triangle from the point set out that in the triangulation has been established to find the triangle containing that point.

3)Determine the impact of the domain from the beginning that contains the points of the triangle, triangle record based on the use of topology information seized empty circumscribed circle of measured.

4)reconstruction of influence domain triangulation. Remove affected area of the triangle. Delaunay criterion based on the influence domain re networking. Simply influence domain of the border with the current insertion point sequentially connected. The obtained result is the triangulation DT.

The process is shown in figure 3:

Figure 3.Triangle subdivision algorithm steps

Ⅳ.The application results

Street data source display as shown in figure 4:

Figure 4.Data source of street

In Microsation v8i platform Terrasolid plug, the source of the data is processed using triangulation algorithm so that the rules can be gradually building a model extraction process. Schematic diagram is shown in Figure 3.

Figure 5 Triangle subdivision algorithm

Ⅴ.Summary and outlook

With the rapid development of information technology and equipment, the point cloud data format with its advantage of data can store more and more realistic, gradually into people's horizons. People in accordance with the demand slowly grope for how to get point cloud data, processing data, the algorithm research and implementation. Triangle subdivision algorithm with its easy to understand, joint surface and the advantages of easy programming model by many people. Terrasolid as Microstation platform plug-in is used by many in the point cloud data processing. Bentely, and although Terrasolid software is charge, but the customer service attitude is very good, try to abundant. Of course, study of point cloud data, including data processing and algorithm research still have room for improvement, choose a better algorithm, using better platform, we still have a lot of work to do.

REFERENCE

[1] Tang Zesheng. 3d data field visualization [M]. Tsinghua university press, 1999.15 ~ 18.

[2] Xu Qing. 3d terrain visualization technology. Beijing: surveying and mapping publishing house. 2000.

[3] Pu S, Vosselman, G. Knowledge Based Reconstruction of Building Models from Terrestrial Laser Scanning Data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2009, 64(6).

[4] Mc Cullagh MJ and Ross C G T .Delaunay triangulation of arandom data set for is alithmic mapping[J].The Cartographic Journal,1980,17:93}991.

[5] Lawson.Software for C surface interpolation, in mathematical software. New York: academic press, 1977.