Thinning and skeletonizing grayscale cubical complex images of any dimensionality
- In this thesis, we present a practical, flexible, and theoretically rigorous method of extracting a sparse skeletal representation of higher-intensity shapes in a grayscale image of any dimensionality. Our approach assumes that the input d-dimensional image belongs to the newly-defined subclass of cubical complex images (CCIs), whose superlevel sets are equivalent to a nested family of cubical complexes. Though the fraction of images that fall into this category is small, we show that every image can be easily transformed into a CCI whose linear dimensions are double those of the original, so our skeletonization scheme remains applicable to all images. The majority of this thesis is devoted to a new grayscale image thinning algorithm, applicable only to CCIs, which reduces the higher-intensity points in an image to a much smaller representative subset. We introduce the algorithm in three stages. In the first stage, we assume that the image is binary, and we use this simple case to clearly explain the underlying thinning mechanism, the unique geometric structure that generalizes to images of any dimensionality, and the many new guarantees we can make on the thinned foreground shape including thinness, centeredness, and topological equivalence to the original foreground set. In the second stage, we generalize the binary image technique into one for grayscale images. We show how the incompatible shapes represented by different gray levels of the image can be reconciled, including an elegant framework for mitigating the effects of low-contrast noise while preserving high-contrast image features. In the final stage, we consider the possibility that thinning might only be performed along a subset of the image axes. We explore the resulting thinning behavior, and we offer an optimized version of the thinning algorithm that capitalizes on the great opportunities for parallel processing that appear under these conditions. After fully developing the thinning algorithm, we study how to best select a sparse subset of points in the thinned image to serve as a representative of the underlying shape. We explore three possible approaches that balance skeletal sparsity with the preservation of image topology. Finally, we address a shortcoming of our grayscale thinning algorithm: it runs in time proportional to the number of distinct values in an input image. To improve the computation time of the thinning routine, we explore an image quantization scheme that attempts to reduce the number of distinct image values while limiting changes in image contrast which affect the behavior of our thinning algorithm.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|Antúnez, Emilio Rodríguez
|Stanford University, Department of Electrical Engineering
|Guibas, Leonidas J
|Guibas, Leonidas J
|Statement of responsibility
|Emilio Rodríguez Antúnez.
|Submitted to the Department of Electrical Engineering.
|Thesis (Ph.D.)--Stanford University, 2010.
- © 2010 by Emilio Rodriguez Antunez
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...