A unified framework for line-like skeleton extraction in 2D/3D sensor networks

In sensor networks, skeleton extraction has emerged as an appealing approach to support many applications such as load-balanced routing and location-free segmentation. While significant advances have been made for 2D cases, so far skeleton extraction for 3D sensor networks has not been thoroughly studied. In this paper, we conduct the first work on the skeleton extraction in 3D sensor networks, and propose a unified framework for line-like skeleton extraction in both 2D and 3D sensor networks. Our algorithm has the following three steps: first, each node identifies itself as a skeleton node if the geodesic shortest paths between its nearest boundary nodes (referred to as feature nodes) decompose the boundary of the network into more than one connected component; second, each skeleton node is assigned a monotonically increasing importance measure according to the maximum Lebesgue measure of the connected components of the boundary such that the identified skeleton nodes are self-connected; and finally, the skeleton is pruned based on the proposed metric branch similarity. The proposed algorithm is connectivity-based, distributed and of low complexity. Extensive simulations show that it is robust to shape variations and boundary noise.