Computational complexity analysis of the graph extraction algorithm for volumetric segmentation method

摘要

The problem of partitioning images into homogenous regions or semantic entities is a basic problem for identifying relevant objects. Visual segmentation is related to some semantic concepts because certain parts of a scene are pre-attentively distinctive and have a greater significance than other parts. Unfortunately there are huge of papers for planar images and segmentation methods and most graph-based for planar images and very few papers for volumetric segmentation methods. The major concept used in graph-based volumetric segmentation method is the concept of homogeneity of regions and thus the edge weights are based on color distance. A huge number of approaches to segmentation are based on finding compact regions in some feature space. A recent technique using feature space regions first transforms the data by smoothing it in a way that preserves boundaries between regions. In this paper we extend our previous papers for planar images by adding a new step in the volumetric segmentation algorithm that allows us to determine regions closer to it. The key to the whole algorithm of volumetric segmentation is the honeycomb. Then the volumetric segmentation module creates virtual cells of prisms with tree-hexagonal structure defined on the set of the image voxels of the input spatial image and a spatial triangular grid graph having tree-hexagons as cells of vertices. The computational complexity analysis shows that our volumetric segmentation methods are linear.