Dimension Free Rigid Point Set Registration in Linear Time

Authors: Jianqin Qu

Abstract:

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.

Keywords: Covariant point, point matching, dimension free, rigid registration.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.2363322

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/.