Advanced

A polynomial-time bound for matching and registration with outliers

Olsson, Carl LU ; Enqvist, Olof LU and Kahl, Fredrik LU (2008) IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops), 2008 In 2008 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOLS 1-12 p.3230-3237
Abstract
We present a framework for computing optimal transformations, aligning one point set to another, in the presence of outliers. Example applications include shape matching and registration (using, for example, similarity, affine or projective transformations) as well as multiview reconstruction problems (triangulation, camera pose etc.). While standard methods like RANSAC essentially use heuristics to cope with outliers, we seek to find the largest possible subset of consistent correspondences and the globally optimal transformation aligning the point sets. Based on theory from computational geometry, we show that this is indeed possible to accomplish in polynomial-time. We develop several algorithms which make efficient use of convex... (More)
We present a framework for computing optimal transformations, aligning one point set to another, in the presence of outliers. Example applications include shape matching and registration (using, for example, similarity, affine or projective transformations) as well as multiview reconstruction problems (triangulation, camera pose etc.). While standard methods like RANSAC essentially use heuristics to cope with outliers, we seek to find the largest possible subset of consistent correspondences and the globally optimal transformation aligning the point sets. Based on theory from computational geometry, we show that this is indeed possible to accomplish in polynomial-time. We develop several algorithms which make efficient use of convex programming. The scheme has been tested and evaluated on both synthetic and real data for several applications. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
2008 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOLS 1-12
pages
3230 - 3237
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops), 2008
external identifiers
  • wos:000259736802122
  • scopus:51949096723
ISSN
1063-6919
language
English
LU publication?
yes
id
20985f3f-b933-4522-9e8c-6b2f6609a62b (old id 1285913)
date added to LUP
2009-02-10 14:11:42
date last changed
2017-10-22 04:15:02
@inproceedings{20985f3f-b933-4522-9e8c-6b2f6609a62b,
  abstract     = {We present a framework for computing optimal transformations, aligning one point set to another, in the presence of outliers. Example applications include shape matching and registration (using, for example, similarity, affine or projective transformations) as well as multiview reconstruction problems (triangulation, camera pose etc.). While standard methods like RANSAC essentially use heuristics to cope with outliers, we seek to find the largest possible subset of consistent correspondences and the globally optimal transformation aligning the point sets. Based on theory from computational geometry, we show that this is indeed possible to accomplish in polynomial-time. We develop several algorithms which make efficient use of convex programming. The scheme has been tested and evaluated on both synthetic and real data for several applications.},
  author       = {Olsson, Carl and Enqvist, Olof and Kahl, Fredrik},
  booktitle    = {2008 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOLS 1-12},
  issn         = {1063-6919},
  language     = {eng},
  pages        = {3230--3237},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {A polynomial-time bound for matching and registration with outliers},
  year         = {2008},
}