Sequential Correspondence Verification
A Fast and Precise Verification of Given Image Correspondences by Cosegmentation

Jan Cech, Jiri Matas, Michal Perdoch

Features

	High precision and recall, significantly better than matching SIFT descriptors [4].
	Fast decision (about 0.5 seconds per 1000 correspondences).
	Tradeoff between speed and accuracy controlled by Wald's SPRT parameters.
	The algorithm returns a verification score (likelihood ratio) besides the decision (correct/mismatch).
	Suitable for challenging matching problems (high ratio of outliers ~ 90%).
	Always applicable before RANSAC. Process generating tentative correspondences may be much more permissive.
	Applicable in wide range of problems where correspondences are sought, e.g. Wide-Baseline-Stereo, Large Scale Image Retrieval.

Download

Code (a software package for Matlab V7, 32/64-bit Linux, 32/64-bit Windows),

Ground-truth affine correspondence set (a set of 10k affine correspondences in 24 image pairs). Please cite us by [1].

Examples

SCV	SIFT ratio
		input correspondences: 1773 selected correspondences: 84 - correct (SCV): 100% - correct (SIFT-ratio): 69% CPU time: 1.4 sec.
		input correspondences: 3065 selected correspondences: 22 - correct (SCV): 95% - correct (SIFT-ratio): 45% CPU time: 1.3 sec.

Figures show correspondences selected by SCV algorithm, and for a reference also the same number of correspondences with the lowest ratio of first to second closest SIFT descriptors [4]. The CPU time  is measured on PC C2 2.4 GHz. Click on images to see them in a full resolution. Note that these results are verified tentative correspondences, i.e. before RANSAC.

Description

In many retrieval, object recognition and wide baseline stereo methods, correspondences of interest points (distinguished regions, transformation covariant points) are established possibly sublinearly by matching a compact descriptor such as SIFT. We show that a subsequent cosegmentation process coupled with a quasi-optimal sequential decision process leads to a correspondence verification procedure that has (i) high precision (is highly discriminative) (ii) good recall and (iii) is fast.
The sequential decision on the correctness of a correspondence is based on trivial attributes of a modified dense stereo matching growing algorithm [3]. The attributes are projected on a prominent discriminative direction by SVM. Wald's sequential probability ratio test is performed for SVM projection computed on progressively larger co-segmented regions. Experimentally we show that the process significantly outperforms the standard correspondence selection process based on SIFT distance ratios on challenging matching problems.

The algorithm is described in papers [1, 2].

References

[1]	Jan Cech, Jiri Matas, Michal Perdoch. Efficient Sequential Correspondence Selection by Cosegmentation. IEEE Trans. on PAMI. In Press. DOI 10.1109/TPAMI.2009.176. [pdf] [bib]
[2]	Jan Cech, Jiri Matas, Michal Perdoch. Efficient Sequential Correspondence Selection by Cosegmentation. In Proc. CVPR, 2008. [pdf] [bib]
[3]	Jan Cech, Radim Sara. Efficient Sampling of Disparity Space for Fast and Accurate Matching. In Proc. BenCOS Workshop CVPR, 2007. [pdf] [bib] [software]
[4]	David Lowe. Distinctive Image Features from Scale-Invariant Keypoints. IJCV, 60(2):91-100, 2004.