HopDSW: An approximate dynamic space warping

Boundary-based shape matching has many applications in areas, such as pattern recognitionand computer vision. Recently, Dynamic space warping (DSW) has emerged as a very effectivetool for matching shapes. However, a central computational difficulty associated with DSWarises 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 anexhaustive search for the correct starting point as in classical approaches, the proposed algorithmoperates in a coarse-to-fine manner. The coarse search is global and uses a hopping step to excludepoints 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 thenumber 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 theMPEG-7 CE-1 database of 1400 shapes show that the proposed algorithm returns the solution ofthe exhaustive search with a high degree of accuracy and a considerable reduction in the number of computation