Computational Complexity Analysis of the Graph Extraction Algorithm for 3D Segmentation

摘要

The problem of partitioning images intohomogenous regions or semantic entities is a basic problem foridentifying relevant objects. Visual segmentation is related tosome semantic concepts because certain parts of a scene arepre-attentively distinctive and have a greater significance thanother parts. Unfortunately there are huge of papers for 2Dimages and segmentation methods and most graph-based for2D images and few papers for spatial segmentation methods. We attempt to search a certain structures in the associatededge weighted spatial graph constructed on the image voxels, such as minimum spanning tree. The major concept used ingraph-based 3D clustering algorithms is the concept ofhomogeneity of regions. For color 3D segmentation algorithmsthe homogeneity of regions is color-based, and thus the edgeweights are based on color distance. Early graph-basedmethods use fixed thresholds and local measures in finding a3D segmentation. Complex grouping phenomena can emergefrom simple computation on these local cues. A number ofapproaches to segmentation are based on finding compactclusters in some feature space. A recent technique usingfeature space clustering first transforms the data by smoothingit in a way that preserves boundaries between regions. Our previous works are related to other works in the sense ofpair-wise comparison of region similarity. In this paper weextend our previous work by adding a new step in the spatialsegmentation algorithm that allows us to determine regionscloser to it. We use different measures for internal contrast of aconnected component and for external contrast between twoconnected components than the measures. The key to the wholealgorithm of spatial segmentation is the honeycomb. The preprocessingmodule is used mainly to blur the initial RGBspatial image in order to reduce the image noise by applying a3D Gaussian kernel. Then the segmentation module createsvirtual cells of prisms with tree-hexagonal structure defined onthe set of the imag- voxels of the input spatial image and aspatial triangular grid graph having tree-hexagons as cells ofvertices.