Picture Skeletons Based on Eccentricities of Points of Minimum Spanning Trees
Robert E. Osteen, Patrick Lin · SIAM Journal on Computing · 1974
Special properties of the eccentricities of points of trees are developed. An algorithm based on those properties is presented for the generation of all diametral paths of a given nontrivial tree. The algorithm is adapted for a certain picture processing application. Given a discrete spatially quantized picture, a grey-distance is defined for neighboring picture cells to produce a graph with weighted lines. A minimum spanning tree of a connected component of the graph is submitted to the modified algorithm, which produces a skeleton of the picture object. The skeleton is further reduced to a smaller tree with weighted lines, viz., the unique tree homeomorphic to the skeleton having no point of degree two. This reduced skeleton with weighted lines constitutes a very compact representation of the picture object, facilitating object classification.