TL;DR
Most sketch-based image retrieval systems only allow users to search using a single, centrally drawn object. This paper introduces a "compositional" sketch search method that lets users draw multiple objects in specific spatial arrangements to find matching scenes. By encoding both object appearance and layout into a compressed search embedding, the system scales to search millions of images without needing explicit object detection at query time.
What Problem Does This Paper Address?
Sketch-Based Image Retrieval (SBIR) is a highly intuitive way to search visual databases—you draw what you want to find. However, existing SBIR algorithms almost exclusively focus on single-object queries. They assume the user is drawing one dominant object (like a single shoe or chair) that takes up the whole canvas.
If a user wants to find a specific scene composition—for example, a dog sitting next to a car, with a tree above them—traditional SBIR fails. It either ignores the spatial layout entirely or only matches the largest object. While some recent methods have tried to tackle scene graphs, they usually require running slow, explicit object detectors on the entire image database. This paper tackles the challenge of building a spatial-aware SBIR system that understands multi-object compositions and scales efficiently to databases with millions of images.
Methods
The authors propose a Spatial-Aware Sketch-Based Image Retrieval (SSBIR) architecture. Here is how it works:
- The Query Tensor: Instead of processing the whole sketch canvas at once, the system isolates each sketched object. It extracts visual features for each object using a pre-trained single-object encoder. It then places these feature vectors into a spatial grid (a "query tensor") based on where the objects were drawn on the canvas. This preserves the spatial layout.
- Spatial Encoder: A Convolutional Neural Network (CNN) maps this spatial grid into a joint search embedding space.
- Image Indexing Branch: To make database images searchable, they are passed through a standard CNN backbone (like GoogLeNet). The output feature maps are flattened into the exact same embedding space as the sketches.
- Contrastive Training: The network is trained using a triplet loss function. It learns to pull matching sketch-image pairs closer together in the embedding space while pushing irrelevant images away.
- Product Quantization (PQ): To make searching millions of images fast and memory-efficient, the high-dimensional embeddings are compressed into short binary codes using 2-step Product Quantization.
Crucially, because the spatial layout is baked directly into the embedding space, the system does not need to run an object detector on the database images during a search.
Datasets
- OI-TrainVal: A subset of OpenImages v6 containing 1.3M training images and 26K validation images across 141 classes. Used to train the model using bounding box annotations.
- TU-Berlin: A standard dataset of single-object sketches, used to pre-train the single-object feature extractor.
- OI-Test-LQ / OI-Test-SQ: 125K test images from OpenImages. The authors synthesized 11K compositional sketch queries (and a smaller 900-query subset) by placing TU-Berlin sketches into the bounding box locations of OpenImages test data.
- Stock4.5M: A massive, real-world dataset of 4.5 million images from Adobe Stock. The authors created 100 hand-drawn, multi-object compositional queries to test real-world scalability and domain generalization.
Key Insights and Ideas
- Appearance + Layout Beats Semantics: Previous layout-based search methods (like the baseline SemIR) convert sketches into text labels (e.g., "car" next to "house") and search based on semantics. This proposed method encodes the actual visual appearance of the sketch. A sketch of a sports car retrieves different results than a sketch of a van, even if both are in the same location on the canvas.
- Implicit Detection is Key to Scaling: By forcing the image CNN backbone to learn spatial arrangements directly in its feature maps, the authors bypass the need for an explicit object detection step at query time. This is what allows the system to search 4.5 million images interactively.
- Older Backbones Can Still Win: Surprisingly, the older GoogLeNet architecture significantly outperformed newer models like ResNet50 and EfficientNet-B0 for the image indexing branch. The authors suspect this is because GoogLeNet aligns better with the pre-trained single-object sketch encoder used earlier in the pipeline.
Key Results
- Quantitative Superiority: On the OI-Test-LQ dataset, the proposed SSBIR achieved a Mean Average Precision (mAP) of 0.260 and an NDCG of 0.534. This crushed the closest spatial-semantic baseline (SemIR), which scored 0.188 mAP and 0.412 NDCG.
- Real-World User Study: On the massive Stock4.5M dataset, human evaluators on Amazon Mechanical Turk strongly preferred the proposed method. For top-20 retrieved results, SSBIR achieved a Precision@20 of 0.432 (compared to 0.345 for baselines), proving it works well on wild, unannotated data.
- Qualitative Success: Visual examples in the paper show the model successfully retrieving complex scenes (e.g., a person standing next to a dog, or a specific type of car next to a house) that match both the visual style of the sketch and the exact spatial positioning.
Limitations and Future Work
While the authors do not include a dedicated limitations section, a few constraints are apparent from the methodology. First, the system relies heavily on bounding box annotations (from OpenImages) during the training phase to learn spatial layouts, which limits the training data to heavily annotated datasets. Second, the pipeline requires a single-object sketch embedding to be trained offline beforehand, making the training process somewhat disjointed.
Future work could likely explore weakly supervised learning to remove the reliance on bounding boxes during training, or adapt the compositional embedding approach to video retrieval.
Summary updated