DISTANCE FIELD TRANSFORM WITH AN ADAPTIVE ITERATION METHOD
Institution: | Kent State University |
---|---|
Department: | College of Arts and Sciences / Department of Computer Science |
Degree: | MS |
Year: | 2009 |
Keywords: | Computer Science; distance field; distance transform; narrow band; multi-segment |
Record ID: | 1862515 |
Full text PDF: | http://rave.ohiolink.edu/etdc/view?acc_num=kent1255727002 |
In my thesis, a novel distance field transform Method is proposed basing 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.