| A skeleton is a powerful shape descriptor that captures both boundary and region information of an object. The skeleton, also known as medial axis or symmetric axis, describes a shape with idealized thin lines and preserves the topology of the original shape. Since the first notion of Blum's grassfire analogy to the skeleton, various techniques have been developed to exploit the idea. Among them is the extraction of the ridge/valley-like structures from topographic surfaces.; Computing ridge/valley-like structures of topographic surfaces has been of great interest for more than a century in various fields of science such as hydrology. In recent decades, such structures have been adopted in image processing and rigorously studied to obtain useful skeleton-like descriptors of shapes. Although numerous ridge/valley detection algorithms have been reported in literature, they suffer from several common problems such as a priori knowledge about the object boundary, the computation of high order derivatives, and the difficulty in 3D implementation. Moreover, the processing unit of most algorithms are individual objects and, as a consequence, each object contained within an image must be processed separately.; In this thesis, we propose a scan line algorithm that rapidly constructs the coarse graph representation of skeletons in discrete image space without involving explicit boundary information or high order derivatives. We also demonstrate that smooth skeletons in continuous space can be obtained by deforming the coarse graph. The proposed algorithm operates on the entire image as a whole, not on the individual object contained in it. As a result, it automatically detects the presence on multiple objects and computes their skeletons simultaneously, representing each object with a separate subgraph. Finally, we propose a simple 3D extension of the algorithm that extracts 1D-skeletons of 3D objects similar to the GC axes. The proposed algorithms apply best to the extraction of the center lines of elongate objects such as finding vessel paths. |
