Distance Field Transform with an Adaptive Iteration Method

摘要：

We propose a novel distance field transform method based on an iterative method adaptively performed on an evolving active band. Our method utilizes a narrow band to store active grid points being computed. Unlike the conventional fast marching method, we do not maintain a priority queue, and instead, perform iterative computing inside the band. This new algorithm alleviates the programming complexity and the data-structure (e.g. a heap) maintenance overhead, and leads to a parallel amenable computational process. During the active band propagating from a starting boundary layer, each grid point stays in the band for a lifespan time, which is determined by analyzing the particular geometric property of the grid structure. In this way, we find the Face-Centered Cubic (FCC) grid is a good 3D structure for distance transform.We further develop a multiple-segment method for the band propagation, achieving the computational complexity of O(m·N) with a segment-related constant m.

关键词： Distance Transform GPU Iteration Wavefront Propagation Narrow Band FCC Multiple-segment

作者: Fan Chen Ye Zhao

作者单位: Department of Computer Science, Kent State University Kent, Ohio, USA

会议类型: 国际会议

会议名称: IEEE International Conference on Shape Modeling and Applications (SMI)(2009年形状建模国际会议)

会议地点: 北京

会议语种:英文

页码: 111-118

在线出版日期: 2009-06-26（万方平台首次上网日期，不代表论文的发表时间）