Non-degenerate Rigid Alignment in a Patch Framework

03/21/2023
by   Dhruv Kohli, et al.
0

Given a set of overlapping local views (patches) of a dataset, we consider the problem of finding a rigid alignment of the views that minimizes a 2-norm based alignment error. In general, the views are noisy and a perfect alignment may not exist. In this work, we characterize the non-degeneracy of an alignment in the noisy setting based on the kernel and positivity of a certain matrix. This leads to a polynomial time algorithm for testing the non-degeneracy of a given alignment. Consequently, we focus on Riemannian gradient descent for minimization of the error and obtain a sufficient condition on an alignment for the algorithm to converge (locally) linearly to it. In the case of noiseless views, a perfect alignment exists, resulting in a realization of the points that respects the geometry of the views. Under a mild condition on the views, we show that the non-degeneracy of a perfect alignment is equivalent to the local rigidity of the resulting realization. By specializing the characterization of a non-degenerate alignment to the noiseless setting, we obtain necessary and sufficient conditions on the overlapping structure of the views for a locally rigid realization. Similar results are also obtained in the context of global rigidity.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset