Compositional Sketch Search

Alexander Black, Tu Bui, Long Mai, Hailin Jin, John P. Collomosse

Abstract

We present an algorithm for searching image collections using free-hand sketches that describe the appearance and relative positions of multiple objects. Sketch based image retrieval (SBIR) methods predominantly match queries containing a single, dominant object invariant to its position within an image. Our work exploits drawings as a concise and intuitive representation for specifying entire scene compositions. We train a convolutional neural network (CNN) to encode masked visual features from sketched objects, pooling these into a spatial descriptor encoding the spatial relationships and appearances of objects in the composition. Training the CNN backbone as a Siamese network under triplet loss yields a metric search embedding for measuring compositional similarity which may be efficiently leveraged for visual search by applying product quantization.

Introduction

Sketch-Based Image Retrieval (SBIR) offers an intuitive interface for visual search, allowing users to draw their intent. However, traditional SBIR systems are largely limited to single-object queries, assuming a dominant object centered in the frame. This limitation prevents users from searching for complex scene compositions, such as a dog sitting next to a car. While some recent approaches utilize scene graphs, they often rely on computationally expensive object detection at query time, hindering scalability.

This paper introduces a "compositional" sketch search method that enables users to specify both the appearance and spatial arrangement of multiple objects. By encoding these factors into a compressed search embedding, the proposed system achieves high-fidelity retrieval across millions of images without requiring explicit object detection during the search phase.

Methodology

The core of the proposed approach is the Spatial-Aware Sketch-Based Image Retrieval (SSBIR) architecture. The system processes queries through a dual-branch pipeline designed to align sketches and images in a shared metric space.

The SSBIR architecture consists of an Index Branch for images and a Query Branch for sketches, utilizing a shared embedding space optimized via contrastive losses.

Query Processing

Instead of analyzing the entire sketch canvas as a single image, the system isolates individual sketched objects. Visual features for each object are extracted using a pre-trained single-object encoder. These features are then mapped into a "query tensor"—a spatial grid that preserves the relative positions of the objects as drawn. A dedicated Spatial Encoder (CNN) then transforms this tensor into a joint search embedding.

Image Indexing and Training

To index the database, images are passed through a CNN backbone (GoogLeNet), where feature maps are flattened into the same embedding space as the sketches. The network is trained using a triplet loss function, which encourages matching sketch-image pairs to cluster together while pushing non-matching pairs apart. To ensure scalability to millions of images, the high-dimensional embeddings are compressed using two-step Product Quantization (PQ), enabling fast, memory-efficient search.

Experimental Setup

The model was trained and evaluated using several large-scale datasets:

  • OI-TrainVal: 1.3M images from OpenImages v6 used for training with bounding box annotations.
  • TU-Berlin: Used for pre-training the single-object feature extractor.
  • OI-Test-LQ / SQ: 125K test images with 11K synthesized compositional queries.
  • Stock4.5M: A real-world dataset of 4.5 million images from Adobe Stock, used to evaluate performance on unannotated data with 100 hand-drawn queries.

Results and Analysis

The SSBIR method demonstrates significant improvements over semantic-only baselines. On the OI-Test-LQ dataset, the system achieved a Mean Average Precision (mAP) of 0.260, substantially outperforming the SemIR baseline (0.188 mAP).

Qualitative examples demonstrate the system's ability to match both the visual appearance and spatial layout of multi-object sketches.

Key Insights

  • Visual Appearance vs. Semantics: Unlike methods that rely solely on text labels, SSBIR captures visual nuances. A sketch of a specific car type retrieves matching vehicles rather than generic instances of the class.
  • Implicit Detection: By embedding spatial information directly into the feature maps, the system avoids the bottleneck of explicit object detection at query time, allowing for interactive search speeds on the Stock4.5M dataset.
  • Architecture Selection: GoogLeNet was found to be superior to more modern backbones like ResNet50, likely due to better alignment with the pre-trained sketch encoder.

Conclusion

This work presents a scalable solution for compositional sketch search, bridging the gap between simple single-object retrieval and complex scene understanding. By leveraging a spatial-aware embedding and product quantization, the system enables users to search massive image databases using intuitive, multi-object drawings. Future research may focus on reducing the reliance on bounding box annotations during training through weakly supervised techniques.

Summary updated

Abstract

We present an algorithm for searching image collections using free-hand sketches that describe the appearance and relative positions of multiple objects. Sketch based image retrieval (SBIR) methods predominantly match queries containing a single, dominant object invariant to its position within an image. Our work exploits drawings as a concise and intuitive representation for specifying entire scene compositions. We train a convolutional neural network (CNN) to encode masked visual features from sketched objects, pooling these into a spatial descriptor encoding the spatial relationships and appearances of objects in the composition. Training the CNN backbone as a Siamese network under triplet loss yields a metric search embedding for measuring compositional similarity which may be efficiently leveraged for visual search by applying product quantization.
BibTeX
@inproceedings{black2021compositional,
  author = {Alexander Black and Tu Bui and Long Mai and Hailin Jin and John P. Collomosse},
  title = {{Compositional Sketch Search}},
  booktitle = {ICIP},
  year = {2021},
  url = {https://openreview.net/forum?id=V4CkQRVpTVxS},
}
Figure