New shape representation and similarity measure for efficient shape indexing

Abstract

Efficient search and retrieval of similar shapes in large databases stipulates two hardly compatible demands to the shape representations. On one hand, shape similarity conveys similarity of spatial relations of the shape parts. Thus, the representation should embed a kind of graph description of the shape, and allow estimation of the (inexact) correspondence between these descriptions. On the other hand, the representation should enable fast retrieval in large databases. Current shape indexing solutions do not comply well to these stipulations simultaneously. The G-graphs1 have been introduced as shape descriptors conveying structural and quantitative shape information. In the current work we define a representation of the G-graphs by strings consisting of the symbols from a four-letter alphabet such that two G-graphs are isomorphic as G-graphs if and only if their string representations are identical. This allows us to represent shapes by vectors consisting of strings and to introduce a shape representation satisfying both above demands. Experimental results are presented. © 2002 SPIE · 0277-786X/02/$15.00.