Planar shape matching based on binary tree shape representation

In this paper we suggest a new way of representing planar two-dimensional shapes and a shape matching method which utilizes the new representation. Through merging of the neighboring boundary runs, a shape can be partitioned into a set of triangles. These triangles are inherently connected according to a binary tree structure. Here we use the binary tree with the triangles as its nodes to represent the shape. This representation is found to be insensitive to shape translation, rotation, scaling and skewing changes due to viewer's location changes (or the object's pose changes). Furthermore, the representation is of multiresolution.

In shape matching we compare the two trees representing two given shapes node by node according to the breadth-first tree traversing sequence. The comparison is done from top of the tree and moving downward, which means that we first compare the lower resolution approximations of the two shapes. If the two approximations are different, the comparison stops. Otherwise, it goes on and compares the finer details of the two shapes. Only when the two shapes are very similar, will the two corresponding trees be compared entirely. Thus, the matching algorithm utilizes the multiresolution characteristic of the tree representation and appears to be very efficient.