 |
 |
 |
Skeleton Pruning
Problems common to modern methods of skeleton pruning include changes in topology and retention of insignificant data. Our method is able to both preserve original topology and to eliminate all redundant or unnecessary branches. We use a method known as Discrete Curve Evolution (DCE) to partition the shape's contour at points of greatest visual significance. While other partitioning methods can be used, we obtain very good results using DCE.
A complete tree of a leaf, two trees created with contour partitions induced by five random points, and a tree created with contour partitions induced by Discrete Curve Evolution.
Click the image for a larger view.
Since DCE points represent points of greatest visual significance along the contour, branches connected to these points represent branches of greatest shape significance. Pruning is accomplished by removing branches that do not terminate at convex DCE points. Branches ending at concave DCE points are discarded because they represent only small amounts of shape data, producing only small branches. The removal of these small branches does not alter the shape information of the tree, but removing them does help to reduce processing time. At some point in DCE evolution, all concave points would be removed anyway, as a DCE-evolved contour always converges to a convex contour.
Because our method does not involve branch shortening, branches retain their original lengths, and therefore preserve topological stability. This effect is apparent in that skeleton branches obtained through contour partitioning always terminate at a point on the contour, whereas branches obtained from other pruning methods do not. An additional advantage to out method is that we are able to retain branches that denote internal contours, or holes, and not disconnect them during the pruning stage. This further preserves the topological stability of a skeleton.
An animation demonstrating our proposed method of skeleton pruning.
Click the image for a larger view.
DCE also naturally compensates for another problem common to deriving trees from images: noise. The DCE algorithm naturally filters out noisy points along the contour. The removal of these points from consideration has the effect of removing spurious branches caused by noise from our tree.
Due to the fact that DCE produces a hierarchal line of evolved contours, different trees of varying detail can be obtained at different levels (though the same image at the same level will always yield the same DCE evolution and the same tree). The specific level to which a contour would need evolved depends on the particular application. For more details see Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution.
Presented below are some examples of our proposed pruning algorithm. The experimental group was composed of images from the MPEG-7 Core Experiment CE-Shape-1 dataset. Note that our algorithm produces similar skeletons for similar shapes, such as the camel, and produces skeletons that are stable with respect to noise distortion, such as the crosses.
| <- Prev | Next -> |