3D BUILDING MODELS SEGMENTATION BASED ON K-MEANS++ CLUSTER ANALYSIS

Chengqi Zhang, Bo Mao2016 · DOI

Abstract 3D mesh model segmentation is a critical task in digital geometry processing, enabling applications like reconstruction, compression, and texture mapping. This paper proposes an improved method for segmenting Collada 3D building models into meaningful parts using the K-means++ clustering algorithm. While traditional K-means is sensitive to randomized initial seed points, K-means++ utilizes a smarter initialization strategy to enhance both speed and accuracy. Experimental results on a large-scale dataset demonstrate that this approach achieves consistent and semantically meaningful segmentations.

Introduction

In the context of "Cyber City" applications, 3D mesh models are often represented as unstructured collections of triangular patches. For a computer, these models lack semantic context—there is no inherent distinction between a roof, a wall, or a foundation. To make these models actionable for urban planning or automated processing, they must be segmented into meaningful geometric parts.

Clustering algorithms, particularly K-means, are frequently employed for this task. However, standard K-means is notoriously sensitive to its initial state. Because it begins by selecting random centroids, different executions on the same model can yield vastly different results, often failing to capture the true architectural structure of the building. This research addresses this instability by integrating the K-means++ initialization strategy.

Methodology

The proposed segmentation pipeline involves three primary stages designed to transform raw mesh data into organized components.

1. Model Normalization

To ensure the algorithm is robust against variations in scale and orientation, models are first normalized. The center of gravity is moved to the coordinate origin, and the model is scaled to fit within a unit space. This process, similar to Principal Component Analysis (PCA), ensures that the geometric features are comparable across different models.

2. Feature Extraction and Clustering Logic

Instead of using raw vertex data, the algorithm extracts the center of gravity of each triangular patch as the primary feature for clustering. This keeps the computational overhead low while preserving the spatial relationships necessary for surface grouping.

The iterative pipeline for 3D mesh segmentation using cluster analysis.

3. K-means++ Initialization

The core innovation lies in the initialization of cluster centers. K-means++ selects the first centroid randomly but chooses subsequent centroids with a probability proportional to their squared distance from existing centers. This ensures that the initial "seeds" are well-spread across the model's geometry, preventing the algorithm from converging on poor local optima. For building models, the authors typically set the cluster count ($K$) to 5, reflecting the standard architectural composition of one roof and four walls.

Results and Discussion

The method was evaluated using a dataset of 2,000 Collada (.dae) building models. The use of K-means++ significantly improved the stability and quality of the segmentation compared to traditional methods.

Qualitative Performance

Visual analysis confirms that K-means++ produces cleaner boundaries and more logical groupings. Traditional K-means often results in "jagged edges" or fragmented clusters where parts of a wall are incorrectly grouped with the roof. In contrast, the improved method consistently identifies distinct architectural features.

Segmentation results showing a building model decomposed into five semantically distinct parts (b1-b5).

Efficiency and Stability

By starting with a better distribution of centroids, the algorithm requires fewer iterations to converge. This leads to improvements in both processing speed and the accuracy of the final parts. The $K=5$ heuristic proved effective for the majority of residential and commercial structures in the dataset, successfully isolating roofs from vertical wall surfaces.

Conclusion

The integration of K-means++ provides a robust solution for the semantic segmentation of 3D building models. By stabilizing the initialization process, the researchers achieved more reliable results that are suitable for downstream urban modeling tasks.

Future work will focus on dynamic determination of the cluster count ($K$) to accommodate more complex architectural styles. Additionally, the authors propose "co-segmentation"—processing groups of similar models simultaneously—to further enhance the consistency and efficiency of the segmentation process.

Summary updated

Abstract

3D mesh model segmentation is drawing increasing attentions from digital geometry processing field in recent years. The original 3D mesh model need to be divided into separate meaningful parts or surface patches based on certain standards to support reconstruction, compressing, texture mapping, model retrieval and etc. Therefore, segmentation is a key problem for 3D mesh model segmentation. In this paper, we propose a method to segment Collada (a type of mesh model) 3D building models into meaningful parts using cluster analysis. Common clustering methods segment 3D mesh models by K-means, whose performance heavily depends on randomized initial seed points (i.e., centroid) and different randomized centroid can get quite different results. Therefore, we improved the existing method and used K-means++ clustering algorithm to solve this problem. Our experiments show that K-means++ improves both the speed and the accuracy of K-means, and achieve good and meaningful results.
BibTeX
@inproceedings{zhang2016d,
  author = {Chengqi Zhang and Bo Mao},
  title = {{3D BUILDING MODELS SEGMENTATION BASED ON K-MEANS++ CLUSTER ANALYSIS}},
  booktitle = {˜The},
  year = {2016},
  doi = {10.5194/isprs-archives-xlii-2-w2-57-2016},
}
Figure