ABSTRACT

In order to simplify the three-dimensional building group model, this paper proposes a clustering generalization method based on visual cognitive theory. The method uses road elements to roughly divide scenes, and then uses spatial cognitive elements such as direction, area, height and their topological constraints to classify them precisely, so as to make them conform to the urban morphological characteristics. Delaunay triangulation network and boundary tracking synthesis algorithm are used to merge and summarize the models, and the models are stored hierarchically. The proposed algorithm should be verified experimentally with a typical urban complex model. The experimental results show that the efficiency of the method used in this paper is at least 20% higher than that of previous one, and with the growth of test data, the higher efficiency is improved. The classification results conform to human cognitive habits, and the generalization levels of different models can be relatively unified by adaptive control of each threshold in the clustering generalization process.

Keywords:

Visual Cognition, 3D Building Model Group, Geometry Threshold, Hierarchical Generalization, Cluster Generalization

1. Introduction

Three-dimensional city model is the key infrastructure of digital city and smart city. The expression of multi-scale three-dimensional city model is the frontier and difficult problem of geographic information science. For a long time, the multi-scale representation of three-dimensional urban models has focused on geometric simplification, and most of the research focuses on simplification of single model. However, in fact, it is equally important to simplify and synthesize the building community in a global sense, which can not only show the structure and layout of the whole city, but also significantly improve the efficiency of three-dimensional model display or roaming. However, the traditional simplification method of single model applied to buildings will bring about the problem that geometry is simply deleted or difficult to distinguish. Especially in urban-scale buildings, the use of traditional simplification algorithm may lead to the deletion of the entire residential area, or when comparing residential buildings with commercial buildings, there will be obvious differences in building scale. Therefore, a new approach is needed to simplify the overall scene. At present, the research on global three-dimensional simplification methods by scholars at home and abroad is mainly manifested in the following two aspects: 1) The simplified method based on geometric features, mainly focusing on distance control. For example, Chang et al. use the principle of similarity in nature of distance, regard distance as a simplified element, use single-link to cluster [1] ; Yang et al. add orientation elements to cluster them on the basis of Chang [2] . However, neither of them takes into account the height parameters of the 3-D scene. 2) The simplified method based on morphology, mainly based on the characteristics of urban morphology and Gestalt principle, guarantees the readability of building communities and conforms to human spatial cognitive habits. For instance, Zhang et al. simulated and quantitatively analyzed it based on human cognitive habits, and proposed a cognitive clustering algorithm [3] . Based on the distance between buildings, using morphological operation method, Kada [4] proposed a hybrid clustering algorithm; Liu Wenkai et al. [5] studied the clustering algorithm of urban mobile objects from the perspective of mining urban traffic congestion. Regnauld [6] imitates the method of two-dimensional map synthesis, constructs adjacent graph and minimum spanning tree, and uses Gestalt criterion to segment adjacent graph to ensure the structural characteristics of urban building groups. In the process of research, the above methods classify urban building groups based on geometric features such as distance or visual features, but neither of them make use of the unique topological relationship of geographical entities to carry out a comprehensive analysis conforming to the visual recognition and geometric features in morphology, so their classification and simplification effect are not satisfactory. In this paper, the model is clustered and generalized and stored hierarchically by utilizing the unique topological relationship of geographical entities, integrating the analysis and judgment of spatial cognition, and combining with the geometric characteristics of cities. Experiments show that the proposed method is more efficient than traditional methods in classification and simplification.

2. The Problem Statement and Theoretical Model

A city, a microcosm of the real world, reflects the structure, layout, and human activities of certain parts of the real world, and can perform certain functions. Therefore, urban models, especially urban architectural models, are essential parts of helping people understand spatial and temporal relationships. The 3D city scene itself is of scale and complexity, and the 3D fine model of large range and multi-details makes the real-time visualization of virtual city become a challenging problem. Therefore, it is necessary to cluster the 3D city model under the premise of ensuring the accuracy of certain space geometry, and to conform to the human visual perception rule. This can not only significantly improve the efficiency of scene rendering and rendering, but also obtain comprehensive information about human activities and urban layout, which can effectively analyze time and space.

Urban morphology can be used to capture certain patterns of urban formation and evolution. The city is a gathering place of human beings, and its evolution is closely related to human activities. Therefore, based on the law of visual perception in morphology, we make a global sense of clustering, generalization and analysis of 3D building models. Through cluster generalization, we can not only get the overall layout of the city, but also find the aggregation point of the city and the law of the density distribution of the urban building group, which can provide data support for the real geo-spatial analysis. In geographical space, the distance near a similar level of geographical entity distance can bring the nature of similarity for 3D model [7] , 2D distance based classification method needs to be extended, the need to consider the 3D model specific height information. Attention is paid to the direction difference and height difference of the model, as well as the characteristics of global urban morphology and human spatial cognition law. This research is mainly based on the visual cognitive law of morphology. In the clustering process, road network segmentation is used to maintain the whole structural characteristics of the urban building model. The accuracy of clustering is controlled by spatial cognitive related factors such as topological relationship, orientation relationship, height and area, and global clustering is carried out. In the process of merging and generalizing, triangular network and boundary tracking algorithm are used to synthesize the clustering, and try to ensure the balance of rendering interaction, and finally store it hierarchically.

Cluster generalization consists of three main operations, which are model clustering, model merging, model generalization and hierarchical storage. The flow chart of model clustering and generalization is shown as Figure 1.

2.1. Model Clustering

In city model, classification is related to human activity or function similarity. This paper is mainly based on the clustering method of visual cognition in morphology. In morphology, the Gestalt criterion requires that four aspects of proximity, similarity, continuity and directionality need to be taken into account

when clustering the model [8] . According to the readability of urban morphology, Lynch [9] divides the city into five main categories: Road, boundary, node, region and landmark [10] . The road is the city readability cognition is extremely important factors, road network can show the arranged in a crisscross pattern layout of the entire city; landmark, is the feature points need to pay attention to the landmark building is of special significance in the whole city pattern, so the need for specific treatment when clustering, as the original to preserve the city characteristics. According to these five elements and the Gestalt criterion, the clustering of visual perception based groups is carried out for 3D building models.

2.1.1. Establishing a Restricted Triangulation Network

Firstly, the Delaunay triangulation is constructed by using the Gestalt criterion and the similar features of adjacent geographical entities in the geographical space to determine the proximity between buildings. Delaunay triangulation is a triangle composed of the closest three points, which has the characteristics of uniqueness and stability. By using this property of Delaunay triangulation, the Delaunay triangulation is used to start the clustering generalization between buildings, and then the graph is integrated.

With convenient operation and cluster behind, the centroid of the surface triangulation construction based on the traditional method, but the automatic establishment of triangulation based on building the profile of automatic extraction of boundary point or vertex algorithm. The algorithm and program for automatic extraction of edge generation TIN are designed, and the generated TIN is shown in Figure 2.

The method of triangulation is based on boundary points or contour vertex, so we need to do some sifting operations, and the correct connection triangles are retained by filtering. As shown in Figure 3. Since the model clustering process takes place between different models, it is not necessary to study the structure and composition of the model, so the triangular mesh built in the model should be removed. Here, through the superposition operation with the bottom contour map, the triangulation network inside the contour map is deleted, and the triangulation network [10] [11] [12] [13] , which can reflect the relation between buildings, is preserved. After deleting the traversal, the resulting triangulation is analyzed. There are two cases: 1) Some triangulation networks are built on the same building surface, such as T1 and T2 triangulation in Figure 3, they are wrong triangulation. 2) The triangulation network is built on the outline of different buildings, such as all the correct triangulation in Figure 3. Here, you need to delete all the wrong triangulation in the first case and retain all the correct triangulation that reflects the merging relationship between buildings in the second case. For the first case, it can be found and deleted that the wrong triangulation of the first case can be ruled out by a concave and convex analysis, and reconstructed the new triangulation such as the real line triangulation, and the reasonable triangulation in the second cases are preserved, and the CDT (Constrained Delaunay Triangulation)1 is generated comprehensively, as shown in Figure 4.

After the establishment of CDT1, according to Lynch proposed five morphological elements of the principle, CDT1 continue to be divided, first of all, CDT1 and road network overlay division. Road is an important factor to control the layout of the whole city. The classification of road elements not only conforms to the characteristics of urban morphology, but also improves the efficiency of classification. Rough grouping of building model by road network gets the initial classification results G1, as shown in Figure 5.

2.1.2. Cluster Analysis Based on Visual Perception

Visual perception refers to the perception process of human beings to obtain information through the visual judgment in the daily life. A range of mental processes that include the perception, storage, memory, and decoding of geographic information. The difference of the perceptual modes is the main basis for judging the division of spatial scales. According to different scales and different spatial perception patterns, space can be divided into graphics, streetscape, environment and geographical space.

The distribution of human activities or functional areas will lead to urban development and evolution. In urban planning, after the key functional areas are identified, visual perception is adopted to construct the city. Therefore, in building cluster analysis, we need to take into account the human visual cognitive habits, people’s visual perception habits generally have the following three situations:

1) Homotropism or ipsilaterality. Visually it is customary to default buildings on the same side of the road to the same category [14] ; the buildings of the same or similar direction are the default. Therefore, it is necessary to consider the use of topological relations to determine the same side of the road, and to analyze the difference between the buildings.

2) Area similarity. Visually inclined to incorporate buildings of similar size into one class. So you need to consider the area difference between buildings. If the area difference exceeds a certain value, it will need to be re grouped.

3) Height. Height is a characteristic of a three-dimensional building model. If the building height difference between the control in a certain range, the vision will tend to return for a class. Therefore, it is necessary to consider the difference of height between buildings in the initial classification. In addition, height based analysis can quickly determine some landmark buildings, which have important guiding significance for the overall urban structure and development changes.

Based on this, this paper deals with the clustering of buildings. The road network controls the whole layout of the whole city. Therefore, firstly, the urban road network and the CDT2 are superimposed and analyzed, and the Delaunay triangulation network intersected with the road network is deleted. The effect is shown in Figure 4. And then use visual perception in the same side or lateral judgment to further classify. Through the topological relation of the surface layer, the location relation of the building and its adjacent road network (same side or different side) is judged and assigned, the same side is 1, the other side is 0, and the same side is classified. Initial classification results G2 are obtained. Based above, then we use the three elements of the direction, height and area in visual cognition to analyze and classify them further.

1) Height: as an important feature of three-dimensional building model, it has great theoretical significance for its analysis and judgment. Height based analysis generally focuses on two cases: Firstly, the extraction of landmark buildings. The emergence of landmark buildings can affect the overall layout of the city. In urban planning, landmark buildings are generally used as agglomeration points to form clear density classification and functional zoning. Second, the difference between the height of the building can be classified two times. The method of analysis is as follows: by setting a parameter ${\delta }_h$ , it is screened and classified by comparing the ${\delta }_h$ with the designated threshold.

${\delta }_h=\frac{h_i}{h_{avg}}\times \left(1-\frac{a{}_i}{{\displaystyle \sum _{i=1}^n{a}_i}}\right)$ (1)

where $h_{avg}$ is the average height of this cluster, $h_i$ is the height of the building i and $a_i$ is the weight coefficient, representing the footprint area of the building i. Among them, it is the weight value of the building in the community of the building, that is, the area of the bottom outline of the building, the average height of the building group, and the height of the building. If it is greater than the threshold, the building is extracted as a separate group, otherwise, the building is classified into one class.

2) Area: area is also more important information of 3D building model. The similarity of area size can also be used as a judgment factor of clustering. The area is generally used in combination with the distance, as a compound judgment condition, to avoid a large number of repeated calculations, and to improve efficiency. The method is as follows: by setting a parameter to judge.

${\delta }_a=\partial \times \frac{a_i}{a_{avg}}$ (2)

where $\partial$ is the weight, the distance between adjacent buildings, $a_i$ represents the building area of building i, $a_{avg}$ represents the average building area of all buildings.

3) Directions: visually, people tend to classify buildings in the same direction. In this paper, the method of linear detection is used to determine the direction. The building centroid as the link point, centroid connected with the line between multiple buildings, analysis to determine the angle between line links, the following three conditions: a) If the angle is 0 degrees and 180 degrees, it can be classified to judge the same. b) If the angle is an acute angle or right angle, the link line is broken and extracted from the existing grouping as a new class. c) If the angle is greater than 90 degrees, the direction is similar or classified.

2.2. Hierarchical Merging and Storing

2.2.1. Model Merging and Generalization

During the hull merging and simplification process, the algorithm introduces some geometric errors into the final mesh. We call these geometric errors negative spaces because our algorithm adds geometry to previously empty spaces. We define the negative space of a cluster mesh as the difference in area between its footprint and the sum of the buildings’ footprints. In this paper, the method of merging and boundary tracing analysis by Delaunay is used to judge, and the analysis results are further screened through angle. By setting the angle threshold, this is set to 135 degrees based on the experience value [15] [16] [17] , and if the angle does not exceed the threshold, the initial merged contour is retained (Figure 6).

$h=\frac{{\displaystyle \sum _{i=1}^n{h}_i\times {\partial }_i}}{{\displaystyle \sum _{i=1}^n{\partial }_i}}$ (3)

where h is the height of this cluster, $h_i$ is the height of the building i and ${\partial }_i$ is the weight of coefficient, representing the footprint area of the building i.

2.2.2. Hierarchical Storage of Data

We use a tree structure to store the simplified models. Because there is no new vertex introduced, the coordinates of the original vertex are stored alone. For every node in the tree, we only store the identifiers of its corresponding vertex rather than its vertex coordinates (see Figure 7). It can avoid vertex coordinates being stored redundantly, thus saving much storage space. Every node also stores the attached useful information, such as the sum of the building area and its height.

In Figure 7, from top to bottom diagram is divided into three layers, and the detail levels are increased in turn. Each layer consists of a number of vertex, each vertex contains coordinates and height information. You can access the corresponding storage structure of the model according to the different levels of detail requirements of the architectural model.

3. Experiment and Result Analysis

3.1. Experiment Environment

Hardware Environment: Operation System of Windows 7, process unit Inter(R) of Core(TM) i5 CPU 2.53 GHz, memory 2.00 G; Development Environment: Microsoft Visual Studio 2010 and ArcEngine; Visualization Tool: OpenGL development package.

3.2. Clustering Experiment and Result Analysis

To demonstrate the performance and efficiency of our methodology, experiments have been done for purposes of evaluation. In this paper having a certain area of Lanzhou City as experimental area, data resource including vector data of bottom of test area, road data etc., clustering test is as following:

Firstly, based on the face data of building bottom, obtaining the points of boundary or vertex automatically, and constructing the Delaunay Triangulation net automatically, shows as following Figure 8.

Secondly, segment and control the road net of triangulation net that preliminary established. Chose the validate triangulation net and connect them. According to the threshold of direction, area and height to analysis and judgement, and got the results.

Thirdly, choose the way of combine the Delaunay triangulation net with boundary trace to merge models. The test area is shown in Figure 9, results of Cluster generalization shows as Figure 10. And the tests of Algorithmic efficiency for huge range has made to this Algorithm.

From Figure 10, we can see that: After the experimental process, the experimentation areas are clustered out 28 groups, by examining the texture, area, height, direction and other characteristics of each building in each group, we find that: Above all the characteristics in the same group are more consistent. The model arrangement is more in line with human visual perception, and the classification of the clustering results is also consistent.

By compared with Chang’s Algorithm, having the raw data in Figure 11(a) as sample, datum in the right has more details than that of left. Research finds that: Chang’s algorithm first combines two models that need to be merged to form a convex quadrilateral, see Figure 11(b), and then gradually iterative and subdivides, final results show in Figure 11(d). However, in Chang’s algorithm, At the same time, the same building model, which is clustered and generalized at the same time, appears at different levels of generalization. However, for this algorithm proposed in this paper, the threshold of each step is controlled, so that the generalization level of different models can be relatively unified. The clustering results of this algorithm are shown in Figure 11(c).

Further study on the computation efficiency of two algorithms, using the data in Figure 9 for test, and test the time cost of two algorithms during the course of model simplifying. Test results are shown in Table 1 and Table 2. From Table 1 and Table 2, we can see that: 1) with the increase of the amount of data, the time-cost of simplifying increases by two curves; 2) the algorithm is more efficient than Chang algorithm in simplification efficiency.

As we can see, the experimental area was clustered out into 28 groups, considering building texture, area, height, direction and other features. The classification results are also consistent with spatial cognition. As the amount of data in the model increases, time goes up in a two-fold.

4. Conclusions

Based on visual cognitive theory, this paper summarizes the global clustering of urban models. Global clustering uses the segmentation method of road network, and makes full use of the characteristics of urban morphology, so as to ensure the invariance of structure. By introducing topological relations, height threshold, area threshold, orientation threshold and other factors related to people’s spatial cognitive visual characteristics, the clustering accuracy is improved. The results show that:

1) The overall grouping effect can be consistent with the human visual cognitive law, the area of the building model, height and direction.

The features of the model are consistent, and the arrangement of the model conforms to visual cognition and Gestalt criterion.

2) The use of landmark model can fully retain the original features of the city, more in line with people’s cognitive habits.

3) The application of visual cognition and threshold constraints can be more flexible and accurate to obtain the required fine degree of the model, and the combined use of Delaunay triangulation and boundary tracking, effectively reduces the original model and the existing model of area difference, reduces unnecessary data processing burden when rendering.

4) Controlled by visual cognitive orientation, area, height threshold, for different models, the generalization hierarchy can achieve a relatively uniform, conducive to the back of the model of hierarchical storage and rendering, and the Chang algorithm is significantly different.

5) This paper takes into account the geometric characteristics and topological characteristics of visual perception, so as to achieve the classification results consistent with visual perception effect. Texture, as an effective and fast way of judgment and analysis in visual cognition, can improve classification efficiency and visualization results through accurate measurement and analysis of texture information, which is the direction of further research in the future.

Acknowledgements

This paper is funded jointly by the projects: Nature Science Funding of China (No.: 41571374), the Key Research Project of Hunan Education Ministry (No.: 16A070), Nature Science Joint Funding of Hunan Province and Xiangtan Local (No.: 2017JJ4037).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Li, C.K., Chen, J.H., Fang, J., Li, H.T. and Bu, P. (2019) Hierarchical Merging & Generalization Method of Three-Dimension City Model Group Based on the Theory of Spatial Visual Cognition. Journal of Geographic Information System, 11, 124-137. https://doi.org/10.4236/jgis.2019.112010

References