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.
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.
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