A Variational Approach to Registration with Local Exponential Coordinates
Ashish Paman
Department of Mechanical Engineering, Indian Institute of Science Bangalore, Bengaluru, India
Search for more papers by this authorRamsharan Rangarajan
Department of Mechanical Engineering, Indian Institute of Science Bangalore, Bengaluru, India
Search for more papers by this authorAshish Paman
Department of Mechanical Engineering, Indian Institute of Science Bangalore, Bengaluru, India
Search for more papers by this authorRamsharan Rangarajan
Department of Mechanical Engineering, Indian Institute of Science Bangalore, Bengaluru, India
Search for more papers by this authorAbstract
We identify a novel parameterization for the group of finite rotations (SO3), consisting of an atlas of exponential maps defined over local tangent planes, for the purpose of computing isometric transformations in registration problems that arise in machine vision applications. Together with a simple representation for translations, the resulting system of coordinates for rigid body motions is proper, free from singularities, is unrestricted in the magnitude of motions that can be represented and poses no difficulties in computer implementations despite their multi-chart nature. Crucially, such a parameterization helps to admit varied types of data sets, to adopt data-dependent error functionals for registration, seamlessly bridges correspondence and pose calculations, and inspires systematic variational procedures for computing optimal solutions. As a representative problem, we consider that of registering point clouds onto implicit surfaces without introducing any discretization of the latter. We derive coordinate-free stationarity conditions, compute consistent linearizations, provide algorithms to compute optimal solutions and examine their performance with detailed examples. The algorithm generalizes naturally to registering curves and surfaces onto implicit manifolds, is directly adaptable to handle the familiar problem of pairwise registration of point clouds and allows for incorporating scale factors during registration.
Supporting Information
Filename | Description |
---|---|
cgf13587-sup-0001-SuppMat.pdf86.4 KB |
Code snippet 1: Exponential map of a skew matrix Code snippet 2: Level set function Ψ and its derivatives Code snippet 3: Assemble matrix-vector system Code snippet 4: Pose update Code snippet 5: Implementation of Algorithm 1 |
Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article.
References
- [Agr06]
Agrawal M.: A lie algebraic approach for consistent pose registration for general Euclidean motion. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006 (NJ, USA, 2006), IEEE, pp. 1891–1897.
10.1109/IROS.2006.282313 Google Scholar
- [AHB87] Arun K. S., Huang T. S., Blostein S. D.: Least-squares fitting of two 3-D point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5 (1987), 698–700.
- [Ale02] Alexa M.: Linear combination of transformations. In ACM Transactions on Graphics (TOG) (2002), ACM, New York, vol. 21, pp. 380–387.
10.1145/566570.566592 Google Scholar
- [AMCO08] Aiger D., Mitra N. J., Cohen-Or D.: 4-points congruent sets for robust surface registration. ACM Transactions on Graphics 27, 3 (2008), #85, 1–10.
- [AMS10]
Absil P.-A., Mahony R., Sepulchre R.: Optimization on manifolds: Methods and applications. In Recent Advances in Optimization and its Applications in Engineering. M. Diehl, F. Glineur, E. Jarlebring and W. Michiels (Eds.). Springer, Berlin (2010), pp. 125–144.
10.1007/978-3-642-12598-0_12 Google Scholar
- [AO06] Arroyo M., Ortiz M.: Local maximum-entropy approximation schemes: A seamless bridge between finite elements and meshfree methods. International Journal for Numerical Methods in Engineering 65, 13 (2006), 2167–2202.
- [BC11] Bogdan R., Cousins S.: 3D is here: Point Cloud Library (PCL). In IEEE International Conference on Robotics and Automation (ICRA) (Shanghai, China, 2011).
- [BM*92] Besl P. J., McKay N. D.: A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 14, 2 (1992), 239–256.
- [BMP02] Belongie S., Malik J., Puzicha J.: Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence 24, 4 (2002), 509–522.
- [Bra00] Bradski G.: The OpenCV Library. Dr. Dobb's Journal of Software Tools 25, (2000).
- [BSB*15] Bellekens B., Spruyt V., Berkvens R., Penne R., Weyn M.: A benchmark survey of rigid 3-D point cloud registration algorithm. International Journal of Advanced Intelligent Systems 8 (2015), 118–127.
- [CBC*01] Carr J. C., Beatson R. K., Cherrie J. B., Mitchell T. J., Fright W. R., McCallum B. C., Evans T. R.: Reconstruction and representation of 3-D objects with radial basis functions. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (New York, 2001), ACM, pp. 67–76.
10.1145/383259.383266 Google Scholar
- [CCC*08] Cignoni P., Callieri M., Corsini M., Dellepiane M., Ganovelli F., Ranzuglia G.: MeshLab: An open-source mesh processing tool. In Eurographics Italian Chapter Conference. S. Vittorio, C R. , E U. (Eds.), The Eurographics Association (2008), pp. 129–136.
- [CL96] Curless B., Levoy M.: A volumetric method for building complex models from range images. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (New York, USA, 1996), ACM, pp. 303–312.
10.1145/237170.237269 Google Scholar
- [clo18] Cloudcompare (ver. 2.8.1). http://www.cloudcompare.org/ (2018). Last accessed on August 25, 2018.
- [CM92] Chen Y., Medioni G.: Object modelling by registration of multiple range images. Image and Vision Computing 10, 3 (1992), 145–155.
- [Con] Consortium D.: Virtual math museum. http://virtualmathmuseum.org/index.html. Last accessed on June 13, 2018.
- [CR03] Chui H., Rangarajan A.: A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding 89, 2–3 (2003), 114–141.
- [CRZL04] Chui H., Rangarajan A., Zhang J., Leonard C.: Unsupervised learning of an atlas from unlabeled point-sets. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 2 (2004), 160–172.
- [CSK05] Chetverikov D., Stepanov D., Krsek P.: Robust Euclidean alignment of 3D point sets: The trimmed iterative closest point algorithm. Image and Vision Computing 23, 3 (2005), 299–309.
- [CT11] Calakli F., Taubin G.: SSD: Smooth signed distance surface reconstruction. In Computer Graphics Forum (2011), Wiley Online Library, vol. 30, pp. 1993–2002.
10.1111/j.1467-8659.2011.02058.x Google Scholar
- [DZX*10] Du S., Zheng N., Xiong L., Ying S., Xue J.: Scaling iterative closest point algorithm for registration of m–d point sets. Journal of Visual Communication and Image Representation 21, 5–6 (2010), 442–452.
- [DZYL10] Du S., Zheng N., Ying S., Liu J.: Affine iterative closest point algorithm for point set registration. Pattern Recognition Letters 31, 9 (2010), 791–799.
- [Ead17] Eade E.: Lie groups for 2D and 3D transformations. http://ethaneade.com/lie.pdf, revised May (2017). Last accessed on August 25, 2018.
- [EAS98] Edelman A., Arias T. A., Smith S. T.: The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications 20, 2 (1998), 303–353.
- [ELF97] Eggert D. W., Lorusso A., Fisher R. B.: Estimating 3-D rigid body transformations: A comparison of four major algorithms. Machine Vision and Applications 9, 5–6 (1997), 272–290.
- [FH86] Faugeras O. D., Hebert M.: The representation, recognition, and locating of 3-D objects. International Journal of Robotics Research 5, 3 (1986), 27–52.
- [Fit03] Fitzgibbon A. W.: Robust registration of 2-D and 3-D point sets. Image and Vision Computing 21, 13 (2003), 1145–1153.
- [Gal11] Gallier J.: Geometric Methods and Applications: For Computer Science and Engineering. Vol. 38. Springer Science & Business Media, New York, 2011.
10.1007/978-1-4419-9961-0 Google Scholar
- [GJMSMCMJ14] Garrido-Jurado S., Muñoz-Salinas R., Madrid-Cuevas F. J., Marín-Jiménez M. J.: Automatic generation and detection of highly reliable fiducial markers under occlusion. Pattern Recognition 47, 6 (2014), 2280–2292.
- [Gou09] Gough B.: GNU scientific library reference manual. Network Theory Ltd. http://www.gnu.org/software/gsl/ (2009). Last accessed on August 25, 2018.
- [GP02] Granger S., Pennec X.: Multi-scale EM-ICP: A fast and robust approach for surface registration. In European Conference on Computer Vision (2002), Springer, Berlin, Heidelberg, pp. 418–432.
10.1007/3-540-47979-1_28 Google Scholar
- [Gra98] Grassia F. S.: Practical parameterization of rotations using the exponential map. Journal of Graphics Tools 3, 3 (1998), 29–48.
10.1080/10867651.1998.10487493 Google Scholar
- [GX03] Gallier J., Xu D.: Computing exponentials of skew-symmetric matrices and logarithms of orthogonal matrices. International Journal of Robotics and Automation 18, 1 (2003), 10–20.
- [HFY*11] Horaud R., Forbes F., Yguel M., Dewaele G., Zhang J.: Rigid and articulated point registration with expectation conditional maximization. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 3 (2011), 587–602.
- [Hor87] Horn B. K.: Closed-form solution of absolute orientation using unit quaternions. JOSA A 4, 4 (1987), 629–642.
- [Inc] Inc. W. R.: Mathematica, Version 11.3. Champaign, IL, 2018.
- [JV05] Jian B., Vemuri B.: A robust algorithm for point set registration using mixture of Gaussians. In 10th IEEE International Conference on Computer Vision, 2005. (2005), IEEE, IEEE Computer Society, NJ, vol. 2, pp. 1246–1251.
- [Kab76] Kabsch W.: A solution for the best rotation to relate two sets of vectors. Acta Crystallographica Section A: Crystal Physics, Diffraction, Theoretical and General Crystallography 32, 5 (1976), 922–923.
- [Kan94] Kanatani K.: Analysis of 3-D rotation fitting. IEEE Transactions on Pattern Analysis and Machine Intelligence 16, 5 (1994), 543–549.
- [KI15] Krivoshapko S., Ivanov V.: Encyclopedia of Analytical Surfaces. Springer International Publishing, Switzerland, 2015.
10.1007/978-3-319-11773-7 Google Scholar
- [KLMV05] Krishnan S., Lee P. Y., Moore J. B., Venkatasubramanian S.: Global registration of multiple 3D point sets via optimization-on-a-manifold. In Symposium on Geometry Processing (2005), pp. 187–196.
- [KSS*17] Kolagunda A., Sorensen S., Saponaro P., Treible W., Kambhamettu C.: Robust shape registration using fuzzy correspondences. arXiv preprint arXiv:1702.05664 (2017).
- [Liu07] Liu Y.: A mean field annealing approach to accurate free form shape matching. Pattern Recognition 40, 9 (2007), 2418–2436.
- [LT09] Lanman D., Taubin G.: Build your own 3-D scanner: 3-D photography for beginners. In ACM SIGGRAPH 2009 Courses (2009), ACM, New York, p. 8.
10.1145/1667239.1667247 Google Scholar
- [MAM14] Mellado N., Aiger D., Mitra N.: Super 4PCS fast global pointcloud registration via smart indexing. Computer Graphics Forum 33, 5 (2014), 205–215.
- [Mar99] Marthinsen A.: Interpolation in lie groups. SIAM Journal on Numerical Analysis 37, 1 (1999), 269–285.
- [Mas02] Masuda T.: Registration and integration of multiple range images by matching signed distance fields for object shape modeling. Computer Vision and Image Understanding 87, 1–3 (2002), 51–65.
- [mat18] Matlab computer vision system toolbox (ver. r2018a). https://in.mathworks.com/help/vision/ (2018). Last accessed on August 25, 2018.
- [Mel] Mellado N.: 4PCS and super4PCS (super4pcs-v1.1.3-osx-clang-703.zip). https://github.com/nmellado/Super4PCS/releases. Accessed on August 25, 2018.
- [MGPG04] Mitra N., Gelfand N., Pottmann H., Guibas L.: Registration of point cloud data from a geometric optimization perspective. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (2004), ACM, New York, pp. 22–31.
10.1145/1057432.1057435 Google Scholar
- [MH94] Marsden J. E., Hughes T. J.: Mathematical Foundations of Elasticity. Dover Publications, New York, 2012.
- [MKS01] Ma Y., Košecká J., Sastry S.: Optimization criteria and geometric algorithms for motion and structure estimation. International Journal of Computer Vision 44, 3 (2001), 219–249.
- [MLSS94] Murray R. M., Li Z., Sastry S. S., Sastry S. S.: A Mathematical Introduction to Robotic Manipulation. CRC Press, Boca Raton, FL 1994.
- [MPD06] Makadia A., Patterson A., Daniilidis K.: Fully automatic registration of 3D point clouds. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2006 (2006), IEEE, IEEE Computer Society, NJ, vol. 1, pp. 1297–1304.
10.1109/CVPR.2006.122 Google Scholar
- [MQZ*15] Ma J., Qiu W., Zhao J., Ma Y., Yuille A., Tu Z.: Robust L2E estimation of transformation for non-rigid registration. IEEE Transactions on Signal Processing 63, 5 (2015), 1115–1129.
- [MS10] Myronenko A., Song X.: Point set registration: Coherent point drift. IEEE Transactions on Pattern Analysis and Machine Intelligence 32, 12 (2010), 2262–2275.
- [Myr] Myronenko A.: Coherent point drift (cpd2.zip). https://sites.google.com/site/myronenko/research/cpd. Accessed on August 25, 2018.
- [MZJZ17] Ma J., Zhao J., Jiang J., Zhou H.: Non-rigid point set registration with robust transformation estimation under manifold regularization. In AAAI (2017), pp. 4218–4224.
- [MZY16] Ma J., Zhao J., Yuille A.: Non-rigid point set registration by preserving global and local structures. IEEE Transactions on Image Processing 25, 1 (2016), 53–64.
- [PLH04] Pottmann H., Leopoldseder S., Hofer M.: Registration without ICP. Computer Vision and Image Understanding 95, 1 (2004), 54–71.
- [RCB97] Rangarajan A., Chui H., Bookstein F.: The softassign procrustes matching algorithm. In Biennial International Conference on Information Processing in Medical Imaging (Berlin, Heidelberg, 1997), Springer, pp. 29–42.
10.1007/3-540-63046-5_3 Google Scholar
- [Ren] Renderer X.: Implicit surfaces. http://xrt.wikidot.com/gallery:implicit. Accessed on June 13, 2018.
- [RL01] Rusinkiewicz S., Levoy M.: Efficient variants of the ICP algorithm. In Proceedings of the 3rd International Conference on 3-D Digital Imaging and Modeling (IEEE Computer Society, NJ, 2001), IEEE, pp. 145–152.
10.1109/IM.2001.924423 Google Scholar
- [SA91] Sabata B., Aggarwal J.: Estimation of motion from a pair of range images: A review. CVGIP: Image Understanding 54, 3 (1991), 309–324.
- [SAD*16] Shi Z., Alliez P., Desbrun M., Bao H., Huang J.: Symmetry and orbit detection via lie-algebra voting. In Computer Graphics Forum (2016), Wiley Online Library, Goslar Germany, Germany, vol. 35, pp. 217–227.
10.1111/cgf.12978 Google Scholar
- [SF89] Simo J., Fox D.: On a stress resultant geometrically exact shell model. Part I: Formulation and optimal parametrization. Computer Methods in Applied Mechanics and Engineering 72, 3 (1989), 267–304.
- [SHT09] Segal A., Haehnel D., Thrun S.: Generalized-ICP. In Robotics: Science and Systems (2009), vol. 2, p. 435.
10.15607/RSS.2009.V.021 Google Scholar
- [SMFF07] Salvi J., Matabosch C., Fofi D., Forest J.: A review of recent range image registration methods with accuracy evaluation. Image and Vision Computing 25, 5 (2007), 578–596.
- [Stu64] Stuelpnagel J.: On the parametrization of the three-dimensional rotation group. SIAM Review 6, 4 (1964), 422–430.
- [SVQ88] Simo J., Vu-Quoc L.: On the dynamics in space of rods undergoing large motions— A geometrically exact approach. Computer Methods in Applied Mechanics and Engineering 66, 2 (1988), 125–161.
- [SW91] Simo J., Wong K.: Unconditionally stable algorithms for rigid body dynamics that exactly preserve energy and momentum. International Journal for Numerical Methods in Engineering 31, 1 (1991), 19–52.
- [SYS07] Sofka M., Yang G., Stewart C.: Simultaneous covariance driven correspondence (CDC) and transformation estimation in the expectation maximization framework. In IEEE Conference on Computer Vision and Pattern Recognition, 2007 (IEEE Computer Society, NJ, 2007), IEEE, pp. 1–8.
10.1109/CVPR.2007.383166 Google Scholar
- [TCL*13] Tam G., Cheng Z., Lai Y., Langbein F., Liu Y., Marshall D., Martin R., Sun X., Rosin P.: Registration of 3-D point clouds and meshes: A survey from rigid to nonrigid. IEEE Transactions on Visualization and Computer Graphics 19, 7 (2013), 1199–1217.
- [Tea] Team G.-P.: Implicit algebraic surfaces. http://www-sop.inria.fr/galaad/surface/. Accessed on June 13, 2018.
- [TFR99] Trucco E., Fusiello A., Roberto V.: Robust motion and correspondence of noisy 3-D point sets with missing data. Pattern Recognition Letters 20, 9 (1999), 889–898.
- [TK04] Tsin Y., Kanade T.: A correlation-based approach to robust point set registration. In European Conference on Computer Vision (2004), Springer, Berlin, Heidelberg, pp. 558–569.
10.1007/978-3-540-24672-5_44 Google Scholar
- [TL] Turk G., Levoy M.: The Stanford 3-D Scanning Repository. Stanford Computer Graphics Laboratory. http://graphics.stanford.edu/data/3Dscanrep. Accessed on June 30, 2017.
- [Ume91] Umeyama S.: Least-squares estimation of transformation parameters between two point patterns. IEEE Transactions on Pattern Analysis & Machine Intelligence 4 (1991), 376–380.
- [WB01] Williams J., Bennamoun M.: Simultaneous registration of multiple corresponding point sets. Computer Vision and Image Understanding 81, 1 (2001), 117–142.
- [YLJ13] Yang J., Li H., Jia Y.: Go-ICP: Solving 3D registration efficiently and globally optimally. In IEEE International Conference on Computer Vision (ICCV), 2013 (IEEE Computer Society, NJ, 2013), IEEE, pp. 1457–1464.
10.1109/ICCV.2013.184 Google Scholar
- [ZD06] Zheng Y., Doermann D.: Robust point matching for nonrigid shapes by preserving local neighborhood structures. IEEE Transactions on Pattern Analysis & Machine Intelligence 28, 4 (2006), 643–649.
- [ŽK98] Žefran M., Kumar V.: Interpolation schemes for rigid body motions. Computer-Aided Design 30, 3 (1998), 179–189.