Distance Transform-Based Skeleton Extraction and Its Applications in Sensor Networks
Distance Transform-Based Skeleton Extraction and Its Applications in Sensor Networks
复制标题
DOI：
10.1109/tpds.2012.300
复制
发表时间：
2013-09
影响因子：
5.3
通讯作者：
Wenping Liu;Hongbo Jiang;X. Bai;Guang Tan;Chonggang Wang;Wenyu Liu-;Kechao Cai
中科院分区：
文献类型：
--
作者：
Wenping Liu;Hongbo Jiang;X. Bai;Guang Tan;Chonggang Wang;Wenyu Liu-;Kechao Cai
我们研究了大规模传感器网络的骨架提取问题，纯粹依赖于连接信息。现有的努力在这条线高度依赖于边界检测算法，这是用来提取准确的边界节点。一个挑战是，在实践中，这可能限制边界检测算法的适用性。例如，在边界检测算法不能很好地工作的低节点密度网络中，提取的边界节点通常是不完整的。本文从距离变换的角度对骨架提取提出了一种新的观点，将距离变换的网络与不完整的边界联系起来。因此，我们提出了一个分布式和可扩展的骨架提取算法，称为DIST，基于距离变换，同时产生低通信开销。该算法不要求边界的完整性和精确性，使得该算法在实际应用中更加实用。首先，我们计算网络的距离变换。具体地，估计每个节点到传感器网络的边界的距离（跳数）。由距离值组成的节点图被认为是距离变换（距离图）。然后使用距离图来识别骨架节点。接下来，通过在所识别的骨架节点内的受控泛洪来生成骨架弧，从而连接这些骨架弧，以提取粗骨架。最后，我们通过构建最短路径树来细化粗骨架，然后进行修剪阶段。得到的骨架是强大的边界噪声或形状变化。此外，我们提出了两个具体的应用程序，受益于提取的骨架：识别完整的边界和形状分割。首先，使用DIST提取骨架，我们建议识别更多边界节点以形成有意义的边界曲线。其次，利用衍生的骨架分割成近似凸块的网络已被证明是有效的。
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.