Dimension Free Rigid Point Set Registration in Linear Time

This paper proposes a rigid point set matching
algorithm in arbitrary dimensions based on the idea of symmetric
covariant function. A group of functions of the points in the set are
formulated using rigid invariants. Each of these functions computes a
pair of correspondence from the given point set. Then the computed
correspondences are used to recover the unknown rigid transform
parameters. Each computed point can be geometrically interpreted as
the weighted mean center of the point set. The algorithm is compact,
fast, and dimension free without any optimization process. It either
computes the desired transform for noiseless data in linear time, or
fails quickly in exceptional cases. Experimental results for synthetic
data and 2D/3D real data are provided, which demonstrate potential
applications of the algorithm to a wide range of problems.

Authors:

• Jianqin Qu

Keywords:

• Covariant point
• point matching
• dimension free
• rigid registration.

References:

[1] G. Scott and C. Lonquiet-Higgins, “An algorithm for associating the
features of two images,” Proc. of Royal Society of London, vol. 255, pp.
21–26, 1991.
[2] P. Besl and N. McKay, “A method for registration of 3d shapes,” IEEE
Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp.
239–266, 1992.
[3] V. Golyanik, B. Taetz, and D. Stricker, “Joint pre-alignment and robust
rigid point set registration,” in 2016 IEEE International Conference on
Image Processing (ICIP), Sept 2016, pp. 4503–4507.
[4] J. Ma, J. Zhao, and A. L. Yuille, “Non-rigid point set registration by
preserving global and local structures,” IEEE Transactions on Image
Processing, vol. 25, no. 1, pp. 53–64, Jan 2016.
[5] S. N. Shahed, Y.-T. Chi, J. Ho, and M.-H. Yang, “Higher dimensional
affine registration and vision applications,” IEEE Transactions on
Pattern Recognition and Machine Intelligence, vol. 33, no. 7, pp.
1324–133, 2011.
[6] M. Carcassoni and E. Hancock, “Spectral correspondence for point
pattern matching,” Pattern Recognition, vol. 36, pp. 193–204, 2003.
[7] L. Shapiro and J. Brady, “Feature-based correspondence-an eigenvector
approach,” Image Vision Comput., vol. 10, pp. 283–288, 1992.
[8] J. Ho, M.-H. Yang, A. Ranganrajan, and B. Vemuri, “A new affine
registration algorithm for 2d point sets,” Workshop on Applications of
Computer Vision (WACV), vol. 12, no. 1, pp. 234–778, Apr. 2007.
[9] J. Ho and M.-H. Yang, “On affine registration of planar point sets using
complex numbers,” Computer Vision and Image Understanding, vol.
115, no. 1, pp. 234–778, Jan. 2011.
[10] J. Qu, L. Gong, and L. Yang, “A 3d point matching algorithm for affine
registration,” International Journal of Computer Assisted Radiology
and Surgery, vol. 6, no. 2, pp. 229–236, Mar 2011. (Online). Available:
https://doi.org/10.1007/s11548-010-0503-y.
[11] Z. Wang and H. Xiao, “Dimension-free affine shape matching through
subspace invariance,” in Computer Vision and Pattern Recognition, 2009.
CVPR 2009. IEEE Conference on, june 2009, pp. 2482 –2487.
[12] B. Horn, “Closed-form solution of absolute orientation using unit
quaternions,” Journal of the Optical Society of America A: Optics, Image
Science, and Vision, vol. 4, no. 4, pp. 629–642, 1987.
[13] L. Greengard and J. Strain, “The fast gauss transform,” SIAM Journal
on Scientific and Statistical Computing, vol. 12, no. 1, pp. 79–94,
1991. (Online). Available: https://doi.org/10.1137/0912004.
[14] C. Yang, R. Duraiswami, and N. A. Gumerov, “Improved
fast gauss transform and efficient kernel density estimation,”
Proceedings Ninth IEEE International Conference on Computer Vision,
vol. C, no. 9987944, pp. 664–671 vol.1, 2003. (Online). Available:
http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1238383.
[15] “Image archive of computational vision at caltech,”
http://www.vision.caltech.edu.
[16] Stanford Computer Graphics Laboratory, “The stanford 3d scanning
repository,” http://graphics.stanford.edu/data/3Dscanrep/.