Attribute Pivots for Guiding Relevance Feedback in Image Search

Adriana Kovashka, Kristen GraumanICCV 2013 · OpenReview

Abstract

In interactive image search, a user iteratively refines his results by giving feedback on exemplar images. Active selection methods aim to elicit useful feedback, but traditional approaches suffer from expensive selection criteria and cannot predict informativeness reliably due to the imprecision of relevance feedback. To address these drawbacks, we propose to actively select "pivot" exemplars for which feedback in the form of a visual comparison will most reduce the system's uncertainty. For example, the system might ask, "Is your target image more or less crowded than this image?" Our approach relies on a series of binary search trees in relative attribute space, together with a selection function that predicts the information gain were the user to compare his envisioned target to the next node deeper in a given attribute's tree. It makes interactive search more efficient than existing strategies—both in terms of the system's selection time as well as the user's feedback effort.

Introduction

Bridging the "semantic gap" remains a primary challenge in image retrieval. When a user has a specific mental image in mind, such as a particular style of shoe or a specific landscape, traditional keyword searches often fall short. Interactive search systems attempt to solve this by using "relevance feedback," where users provide input on images presented by the system to refine subsequent results.

However, traditional binary feedback (marking images as "relevant" or "irrelevant") is often imprecise; it fails to capture why a user prefers an image. Furthermore, the computational cost of identifying the most informative images to show next can be prohibitive for real-time applications. To overcome these hurdles, we introduce Attribute Pivots, a framework that utilizes relative attribute comparisons to guide the search process efficiently.

The interactive search loop: users compare their target mental image to system-selected "pivot" images using relative attributes.

Methodology: Guided Search via Attribute Pivots

The core of our approach is to treat image search as an active learning problem where the system seeks to maximize information gain in each interaction round.

Relative Attribute Trees

For each searchable attribute (e.g., "pointiness," "shininess," "openness"), the system constructs a binary search tree (BST). The root of each tree is a "pivot" image representing the median value for that specific attribute. This structure allows the system to partition the search space effectively based on user comparisons.

Binary search trees (BSTs) are constructed for each attribute, where nodes represent pivot images that partition the search space.

Active Selection and Probabilistic Feedback

Rather than selecting attributes at random, the system employs an entropy-reduction strategy. It evaluates the current pivot nodes across all attribute trees and selects the one predicted to most reduce uncertainty about the user's target.

Crucially, our system uses a probabilistic model for relevance. Recognizing that automated attribute predictors are noisy and user perceptions are subjective, the system does not "hard prune" the database. Instead, it updates the probability of relevance for all images based on the feedback, allowing the search to recover from potentially incorrect or ambiguous responses. This approach ensures robustness while maintaining the efficiency of a tree-based search ($O(MN)$ selection time).

Experimental Results

We evaluated the Attribute Pivots framework on three diverse datasets: Shoes (~15k images), Outdoor Scenes, and PubFig Celebrity Faces. Testing involved both large-scale simulations and live user studies via Amazon Mechanical Turk.

Efficiency and Accuracy

The results demonstrate significant improvements over traditional top-ranked feedback methods. In the Shoes dataset, users reached their target image in an average of 12 rounds, nearly half the 21 rounds required by baseline methods. Furthermore, the system's selection time was reduced from over 10 minutes (for exhaustive entropy search) to just 0.05 seconds, enabling seamless real-time interaction.

Robustness to Noise

The probabilistic "soft pruning" proved essential. In trials using "hard pruning," the system failed to find the target 93% of the time due to attribute prediction errors. Our method maintained high performance even with real-world subjectivity, consistently ranking target images higher and faster than competing strategies.

Conclusion

Attribute Pivots offer a scalable and intuitive solution for interactive image search. By leveraging the power of relative comparisons and efficient tree-based selection, the system reduces both the user's cognitive effort and the computational overhead. This approach effectively bridges the semantic gap, turning image retrieval into a fast, guided conversation between the user and the machine.

Summary updated

Abstract

In interactive image search, a user iteratively refines his results by giving feedback on exemplar images. Active selection methods aim to elicit useful feedback, but traditional approaches suffer from expensive selection criteria and cannot predict in formativeness reliably due to the imprecision of relevance feedback. To address these drawbacks, we propose to actively select "pivot" exemplars for which feedback in the form of a visual comparison will most reduce the system's uncertainty. For example, the system might ask, "Is your target image more or less crowded than this image?" Our approach relies on a series of binary search trees in relative attribute space, together with a selection function that predicts the information gain were the user to compare his envisioned target to the next node deeper in a given attribute's tree. It makes interactive search more efficient than existing strategies-both in terms of the system's selection time as well as the user's feedback effort.
BibTeX
@inproceedings{kovashka2013attribute,
  author = {Adriana Kovashka and Kristen Grauman},
  title = {{Attribute Pivots for Guiding Relevance Feedback in Image Search}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=Hy-drWGubH},
}
Figure