TL;DR
This paper introduces Conditional Image Retrieval (CIR), a novel approach that combines visual similarity search with user-defined filters (conditions) to find semantically related images across diverse subsets of a dataset. They demonstrate its utility with MosAIc, an interactive web app for exploring art, and show CIR can act as non-parametric style transfer and reveal "blind spots" in generative models.
What Problem Does This Paper Address?
Traditional image retrieval systems excel at finding visually similar images within a large, undifferentiated corpus. However, they struggle to efficiently retrieve images that are semantically related but belong to specific, pre-defined subsets (e.g., art from a particular culture or era). Existing methods often resort to brute-force filtering after an initial search, which is inefficient for specific conditions, or require building separate search indices for each subset, which is computationally expensive. This paper addresses the challenge of performing conditional image retrieval on-the-fly, enabling users to discover nuanced connections across diverse collections.
Methods
The core innovation is Conditional Image Retrieval (CIR), which augments standard image retrieval with user-specified "conditions." These conditions act as filters, narrowing down the search space to relevant subsets of the data. The authors propose a generic method to adapt existing image retrieval data structures, particularly tree-based K-Nearest Neighbor (KNN) structures like Random Projection Trees (RP Trees).
Key methodological contributions include:
- Adaptive Tree Pruning: They leverage the theoretical properties of RP Trees to show that sub-trees can naturally capture the geometry of data subsets. This allows for efficient pruning of the tree during a conditional query, significantly reducing the search space.
- Inverted Index for Pruning: An inverted index is used to quickly identify the relevant nodes in the tree that contain points satisfying the condition, enabling dynamic pruning.
- Theoretical Bounds: The paper provides theoretical bounds on the efficiency of their approach, demonstrating its scalability.
- MosAIc Web App: An interactive application is presented to showcase CIR's capabilities in exploring art collections.
Datasets
The paper introduces two new datasets for evaluating CIR methods:
- ConditionalFont: Contains 15,687 grayscale images of 63 ASCII characters across 249 fonts, allowing for content-style separation.
- ConditionalArt: Comprises 1,000,000 color images created by stylizing 5,000 content images from MS COCO with 200 styles from WikiArt.
They also evaluate on the FEI face database (2800 high-resolution faces across 200 participants and various conditions).
Key Insights and Ideas
- CIR as Non-Parametric Style Transfer: The paper demonstrates that CIR can effectively find images with similar content but different styles, acting as a form of "non-parametric" style transfer by retrieving existing images rather than generating new ones.
- Discovering "Blind Spots" in GANs: By analyzing the distribution of generated data within conditional KNN trees, CIR can identify areas where GANs under-sample or over-sample the true data distribution, revealing weaknesses in their generative capabilities. This is achieved using a novel metric called Relative Conditioner Density (RCD).
- Tree-Based Structures are Naturally Conditional: The work highlights how tree-based data structures, particularly RP Trees, are inherently suited for conditional queries due to their hierarchical partitioning, allowing for efficient pruning of irrelevant branches.
- Uncovering Unexpected Connections: The MosAIc application showcases how CIR can reveal surprising visual and semantic connections between artworks spanning vast cultural and temporal divides.
Key Results
- Performance Improvement: The proposed adaptive pruning method (Conditional) significantly outperforms "query-then-filter" strategies and approaches the performance of a "dedicated" tree (pre-computed for every subset) without the high re-creation cost. Speedups of up to 3x relative to brute force are observed for large subsets.
- Accuracy: CIR systems, using various deep learning features, achieve high accuracy in retrieving content-matched images across different styles on the introduced datasets. For example, on the FEI dataset, accuracy at @10 reaches 0.94.
- GAN Analysis: The RCD metric successfully highlights statistically significant structural differences between GAN-generated distributions and real data, even when metrics like FID show similarity. This allowed them to identify specific image types (e.g., microphones, brimmed hats) that a Progressive GAN struggled to generate.
Limitations and Future Work
- Conditioner Size: While the approach is efficient for larger subsets, performance can degrade for very small conditions, though it still outperforms naive "query-then-filter."
- Underlying KNN Tree Dependency: The performance of conditional KNN methods is dependent on the quality and efficiency of the underlying unconditional KNN tree.
- Future Work: The authors suggest exploring more sophisticated diversity-reducing geometries and re-weighting query outputs to mitigate issues with low diversity in conditional neighbors. They also propose further investigation into using CIR to analyze and improve GANs.
Summary updated