AbstractsComputer Science


by Chen Fan

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.