HopDSW: An approximate dynamic space warping algorithm for fast shape matching and retrieval

Boundary-based shape matching has many applications in areas, such as pattern recognition and computer vision. Recently, Dynamic space warping (DSW) has emerged as a very effective tool for matching shapes. However, a central computational difficulty associated with DSW arises when a boundary’s starting point (or rotation angle) is unknown. In this paper, the HopDSW algorithm is proposed to speed up the starting point computation. Rather than performing an exhaustive search for the correct starting point as in classical approaches, the proposed algorithm operates in a coarse-to-fine manner. The coarse search is global and uses a hopping step to exclude points from the search. Then, the search is refined in the neighborhood of the solution of the coarse search. A criterion that governs selecting the hopping step parameter is given, which reduces the number of starting point computations by an order. For shape representation, triangle area signature (TAS) is computed from triangles formed by the boundary points. Experimental results on the MPEG-7 CE-1 database of 1400 shapes show that the proposed algorithm returns the solution of the exhaustive search with a high degree of accuracy and a considerable reduction in the number of computations.