Advanced

Global optimality for point set registration using semidefinite programming

Iglesias, José Pedro ; Olsson, Carl LU and Kahl, Fredrik LU (2020) 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020 p.8284-8292
Abstract

In this paper we present a study of global optimality conditions for Point Set Registration (PSR) with missing data. PSR is the problem of aligning multiple point clouds with an unknown target point cloud. Since non-linear rotation constraints are present the problem is inherently non-convex and typically relaxed by computing the Lagrange dual, which is a Semidefinite Program (SDP). In this work we show that given a local minimizer the dual variables of the SDP can be computed in closed form. This opens up the possibility of verifying the optimally, using the SDP formulation without explicitly solving it. In addition it allows us to study under what conditions the relaxation is tight, through spectral analysis. We show that if the... (More)

In this paper we present a study of global optimality conditions for Point Set Registration (PSR) with missing data. PSR is the problem of aligning multiple point clouds with an unknown target point cloud. Since non-linear rotation constraints are present the problem is inherently non-convex and typically relaxed by computing the Lagrange dual, which is a Semidefinite Program (SDP). In this work we show that given a local minimizer the dual variables of the SDP can be computed in closed form. This opens up the possibility of verifying the optimally, using the SDP formulation without explicitly solving it. In addition it allows us to study under what conditions the relaxation is tight, through spectral analysis. We show that if the errors in the (unknown) optimal solution are bounded the SDP formulation will be able to recover it.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
pages
9 pages
conference name
2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020
conference location
Virtual, Online, United States
conference dates
2020-06-14 - 2020-06-19
external identifiers
  • scopus:85089134708
DOI
10.1109/CVPR42600.2020.00831
language
English
LU publication?
yes
id
5b60b4a0-2fe9-4bc3-9b01-a87acea4bbf8
date added to LUP
2021-01-13 15:31:57
date last changed
2021-01-13 15:31:57
@inproceedings{5b60b4a0-2fe9-4bc3-9b01-a87acea4bbf8,
  abstract     = {<p>In this paper we present a study of global optimality conditions for Point Set Registration (PSR) with missing data. PSR is the problem of aligning multiple point clouds with an unknown target point cloud. Since non-linear rotation constraints are present the problem is inherently non-convex and typically relaxed by computing the Lagrange dual, which is a Semidefinite Program (SDP). In this work we show that given a local minimizer the dual variables of the SDP can be computed in closed form. This opens up the possibility of verifying the optimally, using the SDP formulation without explicitly solving it. In addition it allows us to study under what conditions the relaxation is tight, through spectral analysis. We show that if the errors in the (unknown) optimal solution are bounded the SDP formulation will be able to recover it.</p>},
  author       = {Iglesias, José Pedro and Olsson, Carl and Kahl, Fredrik},
  booktitle    = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition},
  language     = {eng},
  pages        = {8284--8292},
  title        = {Global optimality for point set registration using semidefinite programming},
  url          = {http://dx.doi.org/10.1109/CVPR42600.2020.00831},
  doi          = {10.1109/CVPR42600.2020.00831},
  year         = {2020},
}