Matching with PROSAC — Progressive Sample Consensus

Abstract

A new robust matching method is proposed. The progressive sample consensus (PROSAC) algorithm exploits the linear ordering defined on the set of correspondences by a similarity function used in establishing tentative correspondences. Unlike RANSAC, which treats all correspondences equally and draws random samples uniformly from the full set, PROSAC samples are drawn from progressively larger sets of top-ranked correspondences. Under the mild assumption that the similarity measure predicts correctness of a match better than random guessing, we show that PROSAC achieves large computational savings. Experiments demonstrate it is often significantly faster (up to more than hundred times) than RANSAC. For the derived size of the sampled set of correspondences as a function of the number of samples already drawn, PROSAC converges towards RANSAC in the worst case. The power of the method is demonstrated on wide-baseline matching problems.

Keywords

RANSACMatching (statistics)CorrectnessSimilarity (geometry)Set (abstract data type)MathematicsSample (material)Function (biology)Artificial intelligenceAlgorithmPattern recognition (psychology)Computer scienceStatisticsImage (mathematics)

Affiliated Institutions

Czech Technical University in Prague CZ

Related Publications

Defining the consensus sequences of<i>E.coli</i>promoter elements by random selectio

Arnold Oliphant , Kevin Struhl

The consensus sequence of E.coli promoter elements was determined by the method of random selection. A large collection of hybrid molecules was produced in which random-sequence...

1988 Nucleic Acids Research 61 citations

Multi-Image Matching Using Multi-Scale Oriented Patches

Mathew Brown , Richard Szeliski , Simon Winder

This paper describes a novel multi-view matching framework based on a new type of invariant feature. Our features are located at Harris corners in discrete scale-space and orien...

2005 399 citations

Sparsity and incoherence in compressive sampling

Emmanuel J. Candès , Justin Romberg

We consider the problem of reconstructing a sparse signal x^0\\in{\\bb R}^n from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an...

2007 Inverse Problems 2068 citations

Item-based top-<i>N</i>recommendation algorithms

Mukund Deshpande , George Karypis

The explosive growth of the world-wide-web and the emergence of e-commerce has led to the development of recommender systems ---a personalized information filtering technology u...

2004 ACM Transactions on Information Systems 2164 citations

Stable signal recovery from incomplete and inaccurate measurements

Emmanuel J. Candès , Justin Romberg , Terence Tao

Abstract Suppose we wish to recover a vector x 0 ∈ ℝ 𝓂 (e.g., a digital signal or image) from incomplete and contaminated observations y = A x 0 + e ; A is an 𝓃 × 𝓂 matrix wi...

2006 Communications on Pure and Applied Ma... 7037 citations

Publication Info

Year: 2005
Type: article
Volume: 1
Pages: 220-226
Citations: 1059
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Matching with PROSAC — Progressive Sample Consensus

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

1059

OpenAlex

Cite This

APA Style

                            
                                    Ondřej Chum, 
                                
                                    Jiřı́ Matas
                                
                            (2005). 
                            Matching with PROSAC — Progressive Sample Consensus. 
                            
                            , 1
                            
                            , 220-226.
                            https://doi.org/10.1109/cvpr.2005.221

Identifiers

DOI: 10.1109/cvpr.2005.221