Generating connected skeletons for exact and approximate reconstruction

Abstract

An algorithm for generating skeletons of objects in a binary image is described. The algorithm produces a well-centered skeleton with the same simple connectivity as the object, and it allows the object to be either exactly or approximately (to within a known, user-selectable error) reconstructed. Its connectivity and reconstructability properties can be rigorously proved. For approximate reconstruction, the skeleton can also be (almost always) thin and is insensitive to border noise without image prefiltering or skeleton post-pruning, while maintaining the precise error bounds for reconstruction. Because of these properties, its robustness to rotation, pleasing visual appearance, and flexibility, it is well suited for such applications as data compression, image analysis, character recognition, and circuit board inspection.