3. Shape Descriptor

We introduce a very simple and intuitive shape descriptor. It can be computed for any set of points X on the plane. (In this paper we apply it to compare sets of contour fragments.) Given a point A ∈ X, a shape descriptor of point A denoted S_X(A) is a histogram of all triangles spanned by A and all pairs of points B,C ∈ X, where points A,B,C must be different. To be more specific, with reference to Fig. 6, S_X(A) is a 3D histogram of the angles BAC, and two distances AB and AC. In order to distinguish the two distances, we require that the triangle BCA is oriented clockwise. In order to make our descriptor scale invariant, the distances are normalized by the average pairwise distance of points in X. The shape descriptor S(X) of the set X is a joint 3D histogram of all points, i.e., S(X) = ∑ {SX(x)| x ∈ X}. Then, the similarity ψ(X, Y ) between two sets X, Y is obtained by the standard histogram intersection.

Our shape descriptor has been inspired by Carlsson [3] (see also [30]), but it is different. Carlson considers only qualitative orientation of each triangle: oriented clock or counterclockwise. Our descriptor provides a full quantitative description of each triangle. This leads to a significant increase in descriptive power. The comparison of our triangle histogram shape similarity measure to other measures is left out due to limited space. We only demonstrate in section 4 that it is more flexible than shape context [1], which has been used to evaluate similarity between contour segments in object detection [34]. Shape context considers pairwise relationship between points, while we consider relations between triples of points.

Figure 6. A triangle constructed by points A, B and C.