A Multi-step Strategy for Shape Similarity Search In Kamon Image Database

Abstract

Similarity search in image databases relies on comparing the query with a set of images based on features like shape, colour, texture, and spatial locations. As the size of database grows, query processing strategies were proposed to increase performance by reducing the number of distance calculations. Most strategies are two-step, with the initial 'prune' step based on a high-dimensional spatial index followed by a 'refine' step performing expensive computation. They work well with metric similarity models where lower bounding distance functions exist for pruning. In this work, similarity search in a Japanese Kamon Image Database is attempted. The choice of shapes as features is deliberate because kamons are in black and white, and their meanings are conveyed by shapes. Further, a three-step 'prune-filter-refine' strategy targeting models with non-metric distance functions is described. Compared to the two-step approach, this strategy achieves a further reduction in number of distance calculations needed but with close to no change in the precision figure.