Curves vs. skeletons in object recognition

The type of representation used in describing shape can have a significant impact on the effectiveness and efficiency of a recognition strategy. Shape has been represented by a point set, outline curve and shock-graph (medial axis). The curve-based representation can be viewed as point-based representation with additional organization, namely, order along a contour; shock-based representation, in turn, can be viewed as curve-based representation with additional organization, namely, pairing of contours. This additional complexity in organization leads to greater computational effort in deriving and matching these representations. However, it leads to an increase in robustness in the presence of variations. In this paper, we examine the tradeoff between robustness and computational complexity for curve- and shock-based representations. Our results indicate that the additional computational effort required in shock-graph matching is worthwhile in the presence of large amount variations, in particular those involving the presence of articulation or rearrangement of parts. However, when the space of variations is smaller, curve matching is a better strategy due to its lower complexity and roughly equivalent recognition rate.