Skeleton Extraction from Incomplete Boundaries in Sensor Networks Based on Distance Transform

This paper proposes a novel approach, named DIST, to skeleton extraction from incomplete boundaries using the idea of { 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 { critical skeleton nodes} are identified. Next, a set of { 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.