Distance Transform-Based Skeleton Extraction and Its Applications in Sensor Networks
Authors:
- 22 October 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 24 (9) , 1763-1772
Abstract
We study the problem of skeleton extraction for large-scale sensor networks with reliance purely on connectivity information. Existing efforts in this line highly depend on the boundary detection algorithms, which are used to extract accurate boundary nodes. One challenge is that in practical this could limit the applicability of the boundary detection algorithms. For instance, in low node density networks where boundary detection algorithms do not work well, the extracted boundary nodes are often incomplete. This paper brings a new view to skeleton extraction from a distance transform perspective, bridging the distance transform of the network and the incomplete boundaries. As such, we propose a distributed and scalable algorithm for skeleton extraction, called DIST, based on DIStance Transform, while incurring low communication overhead. The proposed algorithm does not require that the boundaries are complete or accurate, which makes the proposed algorithm more practical in applications. First, we compute the distance transform of the network. Specifically, the distance (hop count) of each node to the boundaries of a sensor network is estimated. The node map consisting of the distance values is considered as the distance transform (the distance map). The distance map is then used to identify skeleton nodes. Next, skeleton arcs are generated by controlled flooding within the identified skeleton nodes, thereby connecting these skeleton arcs, to extract a coarse skeleton. Finally, we refine the coarse skeleton by building shortest path trees followed by a prune phase. The obtained skeleton is robust to boundary noise or shape variations. Besides, we present two specific applications that benefit from the extracted skeleton: identifying complete boundaries and shape segmentation. First, with the extracted skeleton using DIST, we propose to identify more boundary nodes to form a meaningful boundary curve. Second, the utilization of the derived skeleton to segment the network into approximately convex pieces has been shown to be effective.Keywords
This publication has 22 references indexed in Scilit:
- Approximate convex decomposition based localization in wireless sensor networks2012
- Convex Partition of Sensor Networks and Its Use in Virtual Coordinate Geographic Routing2009
- Shape Segmentation and Applications in Sensor Networks2007
- MAP: Medial axis based geometric routing in sensor networksWireless Networks, 2006
- Euclidean skeletons and conditional bisectors1992
- Generating skeletons and centerlines from the distance transformCVGIP: Graphical Models and Image Processing, 1992
- Continuous skeleton computation by Voronoi diagramCVGIP: Image Understanding, 1992
- Efficient computation of various types of skeletons1991
- Distance transformations in digital imagesComputer Vision, Graphics, and Image Processing, 1986
- Biological shape and visual science (part I)Journal of Theoretical Biology, 1973