Image Retrieval by Elastic Matching of User Sketches

Alberto Del Bimbo, Pietro PalaICIAP 1995 · DOI

Introduction

Traditional image retrieval systems primarily rely on text-based keywords. However, linguistic descriptions often fail to capture the "intrinsic visuality" of pictorial data. For instance, in an art catalog, the keyword "bottle" is insufficient to distinguish between various subtle shapes. This paper proposes a retrieval method based on hand-drawn sketches, treating them as "elastic" templates that can deform to match object boundaries in images.

Methodology

Elastic Shape Matching

The core of the system is a deformation process where a user's sketch, modeled as a first-order spline, is warped onto the edges of objects within the database. A hand-drawn sketch of a bottle used as a query template. Source, p. 6 This is framed as an energy minimization problem. The system minimizes a compound functional that considers:

  • Strain Energy: The degree of elongation required for the template.
  • Bend Energy: The amount of curvature change in the template.
  • Edge Alignment: The overlap between the deformed template and the image's gradient field.
A hand-drawn sketch of a bottle used as a query template.

To validate matches and reject "illegal" deformations, a Back-propagation Neural Network is employed. It analyzes parameters such as overlap degree, energy values, and the preservation of curvature zeroes (topological constraints).

Spatial Relationship Analysis

For queries involving multiple objects, the system utilizes Minimum Enclosing Rectangles (MER) to define spatial arrangements. The system categorizes relationships into five types (disjoint, meet, contain, inside, partly overlap) and tracks cardinal orientations. To maintain efficiency, these relationships are encoded into signature files using hash functions, acting as a "sieve" to filter out irrelevant images before the computationally intensive elastic matching is performed.

Experimental Evaluation

The system was tested on a database of 20th-century paintings by Giorgio Morandi, known for his still-life compositions of similar objects. This dataset provides a rigorous test for differentiating subtle shape variations.

Results and Discussion

The system demonstrates high sensitivity to shape and spatial precision. By calculating the "energy" required for transformation, the system can rank results by similarity. Ranked retrieval results showing images with varying degrees of similarity to the user's sketch. Source, p. 6 Key findings include:

  • Shape Sensitivity: The system successfully ranks objects with similar silhouettes at the top, while more "strained" or differently proportioned shapes receive lower scores.
  • Multi-Object Precision: Spatial filtering effectively narrows the search space for complex queries involving multiple items and their relative positions.
  • Invariance: The method is inherently invariant to translation and includes mechanisms for scale and rotation invariance.
Ranked retrieval results showing images with varying degrees of similarity to the user's sketch.

Conclusion

This research provides a robust framework for visual querying. By combining elastic matching with spatial relationship analysis, the system bridges the gap between approximated human sketches and precise digital image data. Future work will focus on optimizing the computational complexity of the gradient descent matching process to scale for larger datasets.

Summary updated

BibTeX
@inproceedings{bimbo1995image,
  author = {Alberto Del Bimbo and Pietro Pala},
  title = {{Image Retrieval by Elastic Matching of User Sketches}},
  booktitle = {ICIAP},
  year = {1995},
  doi = {10.1007/3-540-60298-4\_256},
}
Figure