Probabilistic Feature Matching for Fast Scalable Visual Prompting

Thomas Frick, Cezary Skura, Filip Janicki, Roy Assaf, Niccolò Avogaro, Daniel Caraballo, Yagmur Gizem Cinar, Brown Ebouky, Ioana Giurgiu, Takayuki Katsuki, Piotr Kluska, Cristiano Malossi, Haoxiang Qiu, Tomoya Sakai, Florian Scheidegger, Andrej Simeski, Daniel Yang, Andrea Bartezzaghi, Mattia RigottiIJCAI 2024

Abstract

Interactive image segmentation often struggles with the computational overhead of pixel-wise matching at high resolutions. We present Softmatcher, a training-free framework that enables real-time segmentation using simple user scribbles. By substituting rigid matching algorithms with a scalable probabilistic approach based on entropic regularization, Softmatcher achieves a 6x speedup over previous state-of-the-art methods on standard benchmarks like FSS-1000, while maintaining competitive accuracy. This enables truly interactive "segment anything" workflows.

Introduction

Image segmentation is a fundamental task in computer vision, recently revolutionized by foundation models like the Segment Anything Model (SAM). However, SAM typically requires precise point or box prompts for each target image. Few-shot segmentation methods attempt to automate this by matching a labeled "reference" image to "target" images. A major bottleneck in these systems is the reliance on the Hungarian algorithm for pixel matching, which has a cubic computational complexity ($O(N^3)$). As image resolution increases, this complexity leads to significant latency, hindering real-time human-in-the-loop interaction.

Methodology

Softmatcher addresses the scalability bottleneck by treating pixel matching as an Optimal Transport problem solved through probabilistic assignments rather than rigid one-to-one mapping.

Overview of the Softmatcher framework, illustrating the pipeline from reference scribble to final mask generation.

The workflow consists of three primary stages:

  1. Prompting & Reference Segmentation: A user provides a coarse scribble on a reference image, which SAM converts into a high-quality reference mask.
  2. Soft Feature Matching: Deep features are extracted from both images using a frozen DINOv2 model. Softmatcher applies entropic regularization to the matching problem, reducing complexity to $O(N^2)$. An optimized version, "Softmatcher RFF," utilizes Random Fourier Features for even greater efficiency.
  3. Mask Generation: The matching process yields a probability map. Points are sampled and clustered from this map, then fed into SAM to generate the final segmentation mask.

Experimental Setup

The framework was evaluated on the FSS-1000 dataset, which contains 1,000 object classes. This benchmark is particularly challenging as it includes many "unseen" objects, testing the system's open-world generalization capabilities without requiring task-specific fine-tuning.

Results and Discussion

Softmatcher demonstrates a significant improvement in computational efficiency without a substantial loss in segmentation quality.

Comparison of inference time across different image sizes for the Hungarian algorithm versus Softmatcher variants.

Performance Metrics

  • Computational Efficiency: At a resolution of 448 pixels, Softmatcher is approximately 6x faster than the Hungarian-based Matcher. The scaling advantage becomes even more pronounced at higher resolutions.
  • Segmentation Accuracy: On FSS-1000, Softmatcher achieved a one-shot Intersection over Union (IoU) of 85.5%, closely trailing the 87.0% of the much slower Matcher baseline.

Key Insights

The success of Softmatcher highlights that "compositional" approaches—combining existing foundation models like DINOv2 and SAM with efficient mathematical "glue"—can solve complex tasks without massive retraining. Furthermore, the shift from rigid matching to probabilistic estimation suggests that in interactive systems, low latency is often more valuable than marginal gains in theoretical matching perfection.

Conclusion and Future Work

Softmatcher provides a scalable, training-free solution for interactive visual prompting. While highly effective, the system remains dependent on the feature discriminability of the underlying foundation models. Future research directions include integrating multimodal prompts via CLIP and refining the "Reject & Merge" logic for complex, multi-object scenes.

Summary updated

BibTeX
@inproceedings{frick2024probabilistic,
  author = {Thomas Frick and Cezary Skura and Filip Janicki and Roy Assaf and Niccolò Avogaro and Daniel Caraballo and Yagmur Gizem Cinar and Brown Ebouky and Ioana Giurgiu and Takayuki Katsuki and Piotr Kluska and Cristiano Malossi and Haoxiang Qiu and Tomoya Sakai and Florian Scheidegger and Andrej Simeski and Daniel Yang and Andrea Bartezzaghi and Mattia Rigotti},
  title = {{Probabilistic Feature Matching for Fast Scalable Visual Prompting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure