Skeleton Extraction from Incomplete Boundaries in Sensor Networks Based on Distance Transform
Wenping Liu, Hongbo Jiang, Xiang Bai, Guang Yu Tan, Chonggang Wang, Wenyu Liu, Kechao Cai · 2012
This paper proposes a novel approach, named DIST, to skeleton extraction from incomplete boundaries using the idea of {\em distance transform}, a concept in the computer graphics area. The main contribution is a distributed and low-cost algorithm that produces accurate network skeletons without requiring that the boundaries be complete or tight. The algorithm first establishes the network's distance transform -- the hop distance of each node to the network's boundaries. Based on this, some {\em critical skeleton nodes} are identified. Next, a set of {\em skeleton arcs} are generated by controlled flooding, connecting these skeleton arcs then gives us a coarse skeleton. The algorithm finally refines the coarse skeleton by building shortest path trees, followed by a prune phase. The obtained skeletons are robust to boundary noise and shape variations.