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

Abstract

Boundarybased 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 starling 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 aIgorithm operates in a coarsetofine 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 or the solution of the course search A criterion that governs selecting the hopping step parameter is given which reduces rbe number of starting point computations by an order For shape representation triangle area signalure (TAS) is computed from triangles formed by the boundary points ExperimentaI resuIts on the MPEG7 CE1 database or 1400 shapes show that the proposed aleorithrn returns the solution of the exhaustive search with a high degree of accuracy and a considerable reduction in the number of computations