Title

Bwt-Based Efficient Shape Matching

Keywords

Burrows-wheeler transform; Compression; Content-based retrieval; Shape matching; Shape retrieval

Abstract

Effective shape-based image retrieval requires an appropriate representation of object shape contours. Such a representation should be invariant under certain transformations, such as those due to rotation, scaling, partial occlusion, noise in the image, or changes in the viewing geometry. Given a shape boundary, we decompose it into primitive shape segments that capture the saliency of object parts, and perform retrieval based on the primitives. Motivated by the sorted contexts of the Burrows-Wheeler Transform, we present an algorithm for efficient shape matching, suitable for large-scale shape databases, when the shape boundaries are represented as a sequence of shape primitives. Given a query shape, the algorithm can locate all the potential areas in the database where a match could occur in time that is logarithmic with respect to the database size. The potential matches are then verified in time that is linear with respect to the number of potential matches. Performance of the proposed algorithm is evaluated using both synthetic and real shape databases. Copyright 2007 ACM.

Publication Date

1-1-2007

Publication Title

Proceedings of the ACM Symposium on Applied Computing

Number of Pages

1079-1085

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/1244002.1244237

Socpus ID

35248882872 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/35248882872

This document is currently not available here.

Share

COinS