Subspace matching: Unique solution to point matching with geometric constraints

Marques, Manuel; Stošić, Marko; Costeira, João

Authors:	Marques, Manuel Stošić, Marko Costeira, João
Title:	Subspace matching: Unique solution to point matching with geometric constraints
Journal:	Proceedings of the IEEE International Conference on Computer Vision
First page:	1288
Last page:	1294
Conference:	12th International Conference on Computer Vision, ICCV 2009; Kyoto; Japan; 29 September 2009 through 2 October 2009
Issue Date:	1-Dec-2009
ISBN:	978-1-424-44420-5
DOI:	10.1109/ICCV.2009.5459318
Abstract:	Finding correspondences between feature points is one of the most relevant problems in the whole set of visual tasks. In this paper we address the problem of matching a feature vector (or a matrix) to a given subspace. Given any vector base of such a subspace, we observe a linear combination of its elements with all entries swapped by an unknown permutation. We prove that such a computationally ha... Finding correspondences between feature points is one of the most relevant problems in the whole set of visual tasks. In this paper we address the problem of matching a feature vector (or a matrix) to a given subspace. Given any vector base of such a subspace, we observe a linear combination of its elements with all entries swapped by an unknown permutation. We prove that such a computationally hard integer problem is uniquely solved in a convex set resulting from relaxing the original problem. Also, if noise is present, based on this result, we provide a robust estimate recurring to a linear programming-based algorithm. We use structure-from-motion and object recognition as motivating examples.
Publisher:	IEEE