#70: Accurate spatial neighborhood relationships for arbitrarily-shaped objects using Hamilton-Jacobi GVD

S. K. Nath, K. Palaniappan, and F. Bunyak

Lecture Notes in Computer Science (SCIA), Volume 4522, pgs. 421--431, 2007

cell segmentation, segmentation, active contours, data mining

PlainText, Bibtex, PDF, DOI, Google Scholar


Many image segmentation approaches rely upon or are enhanced by using spatial relationship information between image regions and their object correspondences. Spatial relationships are usually captured in terms of relative neighborhood graphs such as the Delaunay graph. Neighborhood graphs capture information about which objects are close to each other in the plane or in space but may not capture complete spatial relationships such as containment or holes. Additionally, the typical approach used to compute the Delaunay graph (or its dual, the Voronoi polytopes) is based on using only the point-based (i.e., centroid) representation of each object. This can lead to incorrect spatial neighborhood graphs for sized objects with complex topology, eventually resulting in poor seg- mentation. This paper proposes a new algorithm for efficiently, and accurately ex- tracting accurate neighborhood graphs in linear time by computing the Hamilton- Jacobi generalized Voronoi diagram (GVD) using the exact Euclidean-distance transform with Laplacian-of-Gaussian, and morphological operators. The algo- rithm is validated using synthetic, and real biological imagery of epithelial cells.