Digital reconstruction of existing objects and complex 3D environments is often necessary for developing realistic virtual reality scenes. Three-dimensional range scanners capture shape information about complex objects and real-world environments as immense data clouds comprising discrete 3D surface points and their corresponding RGB (red, green, blue) color values. To improve the usability of the raw point clouds, the data must be broken into meaningful clusters.^{1} Once properly segmented, it is possible to recreate individual objects and successfully model the scanned space. Accurate segmentation of building interiors^{2, 3} and architectural shapes^{1,4} poses unique challenges due to the presence of multiple objects, partially occluded geometry, and vast geometric diversity. Unfortunately, segmentation algorithms that rely on pure surface geometry,^{3} prior-shape knowledge,^{5, 6} and simplified shape approximations^{5,7} have difficulty handling such complex point clouds. As a result, they often generate only primitive shape information through piecewise approximation of planar surfaces. We propose a hierarchical clustering algorithm^{8} that exploits color and geometry to improve clustering reliability.

**Figure 1.**Colored point cloud generation using stationary range scanner and its mapped colored digital pictures. RGB: Red, green, blue. XYZ: Geometry of spatial data points.

**Figure 2.**Segmentation results of (a) first and (b) second hierarchical stage using hue and geometric similarity.

This shape-based hierarchy manages geometric diversity by extracting large, planar (e.g., walls, floor, and ceiling) and small, freeform regions (interior complex objects) in two successive stages. Each hierarchical stage uses its own geometric complexity-driven algorithmic parameters to handle planar and complex regions alike. The segmentation accuracy is further improved by investigating the color (RGB) along with the geometry of spatial data points (XYZ). This additional similarity ensures coherent clustering even in geometrically uncertain areas. It also helps in identifying unique data clusters representing multiple objects with similar overlapping geometries. We demonstrated the approach on a colored point cloud acquired from an office room with multiple objects (table, chairs, monitor, printer, statue head, and so on) and colored sheets on the walls using a stationary FARO^{®} range scanner (LS880) and mapped colored images (see Figure 1).

To be able to use color as a reliable differentiating parameter, we converted the colored point cloud from highly correlated RGB sensor values into a more robust hue, saturation, and value color perception space. This helps in defining the color with hue alone. The clustering process starts with the selection of a suitable seed point from coherent areas, defined in terms of geometry and color, which prevents subsequent cluster readjustments. Further, an adaptive average-density approach^{8} ensures accurate seed selection from sparse as well as dense data regions. The selected seed point expands its cluster by investigating its neighboring points using local geometry and hue similarity criteria.^{8}

The first stage exploits the fact that planar regions constitute a large portion of building interiors, and thus extracts these regions (wall, windows, doors, windows, floors, and ceilings) using constraints that combine hue and a measure of local planarity called planar alignment factor.^{8} This stage segments 72–84% of the sampled points into planar clusters: see Figure 2(a). The significantly reduced data points representing complex, freeform interior objects are further clustered in the second stage using higher-order geometric parameters (surface normal) and hue similarity constraints: see Figure 2(b).

The hierarchical approach allows the selection of adaptive geometric parameters in each stage, whereas the additional hue constraint identifies unique clusters (colored sheets, light fixtures, and air vent) from planar regions that could not be recognized geometrically. The hue constraint also helps in extracting saturated clusters from coherent regions spanning small discontinuities (floor) and sparse density regions (e.g., statue and monitor) using relaxed geometric constraints. The algorithmic parameters can be changed to control the segmentation level and extract individual surfaces, geometric features, or specific objects.

In summary, we have described research that advances scene reconstruction by providing a robust data segmentation strategy for large colorized point clouds of building interiors. The dual similarity criterion improves the segmentation reliability, and shape-based hierarchy handles the geometric diversity. Our next steps will be to investigate other color models to further improve the reliability of the method.

*The work is supported, in part, by the Natural Sciences and Engineering Research Council of Canada and the National Research Council of Canada in London, Ontario, Canada.*

George K. Knopf, Kuldeep Sareen

University of Western Ontario

London, Canada

George Knopf is a professor in the Department of Mechanical and Materials Engineering. His research activities involve 3D shape reconstruction, laser microfabrication, development of optically driven microactuators, and bioelectronic imaging arrays.

Kuldeep Sareen is a PhD candidate in the Department of Mechanical and Materials Engineering. His current research interests focus on 3D range scanning and include geometric modeling, reverse engineering, virtual reality reconstruction, and building information modeling from large point clouds.

Roberto Canas

Institute for Research in Construction

National Research Council of Canada

London, Canada

Roberto Canas pursues research and development for the construction sector based on his expertise in mathematics and physics, high-performance computation, and graphics. His current work focuses on using building information modeling to perform analysis, modeling, and simulation of current and future building performance, as well as fire propagation and egress.

References:

1. X. Ning, X. Zhang, Y. Wang, M. Jaeger, Segmentation of architecture shape information from 3D point cloud,

*Proc. 8th Int'l Conf. Virt. Real. Continuum Appl. Indus.*, pp. 127-132, 2009. doi:

10.1145/1670252.1670280
2. P. Dorninger, C. Nothegger, 3D segmentation of unstructured point clouds for building modelling, *Proc. Int'l Arch. Photogramm. Remote Sens. Spat. Info. Sci., ISPRS Symp. Photogramm. Image Anal*., pp. 191-196, 2007.

3. T. Rabbani, F. A. V. Heuvel, G. Vosselman, Segmentation of point clouds using smoothness constraints,* Proc. ISPRS Symp. Image Eng. Vis. Metrol.*, pp. 248-253, 2006.

4. Q. Zhan, Y. Liang, Y. Xiao, Color-based segmentation of point clouds, *Proc. ISPRS Laser Scan. Workshop*, pp. 248-252, 2009.

5. A. Budroni, J. Böhm, Toward automatic reconstruction of interiors from laser data, *Proc. Int'l Arch. Photogramm. Remote Sens. Spat. Info. Sci., Symp. 3D Virt. Reconst. Vis. Complex Arch*., 2009. Technical Session 7.

6. A. Alharthy, J. Berthel, Detailed building reconstruction from airborne laser data using a moving surface method,* Proc. Int'l Arch. Photogramm. Remote Sens., 20th ISPRS Cong.,* pp. 213-218, 2004.

7. G. Bahmutov, V. Popescu, M. Mudure, Efficient large scale acquisition of building interiors,

*Comput. Graph. Forum 25, *no. 3, pp. 655-662, 2006. doi:

10.1111/j.1467-8659.2006.00985.x
8. K. K. Sareen, G. K. Knopf, R. Canas, Hierarchical data clustering approach for segmenting colored three-dimensional point clouds of building interiors,

* Opt. Eng. 50,* no. 7, pp. 077003, 2011. doi:

10.1117/1.3599868