Abstract
The well-known robust point matching (RPM) method uses deterministic annealing for optimization, and it has two problems. First, it cannot guarantee the global optimality of the solution and tends to align the centers of two point sets. Second, deformation needs to be regularized to avoid the generation of undesirable results. To address these problems, in this paper we first show that the energy function of RPM can be reduced to a concave function with very few non-rigid terms after eliminating the transformation variables and applying linear transformation; we then propose to use concave optimization technique to minimize the resulting energy function. The proposed method scales well with problem size, achieves the globally optimal solution, and does not need regularization for simple transformations such as similarity transform. Experiments on synthetic and real data validate the advantages of our method in comparison with state-of-the-art methods.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Besl, P.J., McKay, N.D.: A method for registration of 3-d shapes. IEEE Trans. Pattern Analysis and Machine Intelligence 14, 239–256 (1992)
Zhang, Z.: Iterative point matching for registration of free-form curves and surfaces. International Journal of Computer Vision 13, 119–152 (1994)
Chui, H., Rangarajan, A.: A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding 89, 114–141 (2003)
Myronenko, A., Song, X.: Point set registration: Coherent point drift. IEEE Transactions on Pattern Analysis and Machine Intelligence 32, 2262–2275 (2010)
Tsin, Y., Kanade, T.: A Correlation-Based Approach to Robust Point Set Registration. In: Pajdla, T., Matas, J(G.) (eds.) ECCV 2004. LNCS, vol. 3023, pp. 558–569. Springer, Heidelberg (2004)
Jian, B., Vemuri, B.C.: A robust algorithm for point set registration using mixture of gaussians. In: IEEE International Conference on Computer Vision, vol. 2, pp. 1246–1251 (2005)
Sofka, M., Yang, G., Stewart, C.V.: Simultaneous covariance driven correspondence (cdc) and transformation estimation in the expectation maximization framework. In: IEEE Conf. Computer Vision and Pattern Recognition, pp. 1–8 (2007)
Horst, R., Tuy, H.: Global Optimization, Deterministic Approaches. Springer (1996)
Maciel, J., Costeira, J.: A global solution to sparse correspondence problems. IEEE Trans. Pattern Analysis and Machine Intelligence 25, 187–199 (2003)
Olsson, C., Kahl, F., Oskarsson, M.: Branch-and-bound methods for euclidean registration problems. IEEE Transactions on Pattern Analysis and Machine Intelligence 31, 783–794 (2009)
Pfeuffer, F., Stiglmayr, M., Klamroth, K.: Discrete and geometric branch and bound algorithms for medical image registration. Annals of Operations Research 196, 737–765 (2012)
Golub, G.H., Loan, C.F.V.: Matrix computations. The Johns Hopkins University Press (1996)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Dover Publications, Inc., New York (1998)
Jiang, H., Drew, M.S., Li, Z.-N.: Matching by linear programming and successive convexification. IEEE Trans. Pattern Analysis and Machine Intelligence 29, 959–975 (2007)
Caetano, T.S., Caelli, T.: A unified formulation of invariant point pattern matching. In: 18th International Conference on Pattern Recognition (ICPR 2006), vol. 3, pp. 121–124 (2006)
Lian, W., Zhang, L.: Rotation Invariant Non-rigid Shape Matching in Cluttered Scenes. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part V. LNCS, vol. 6315, pp. 506–518. Springer, Heidelberg (2010)
Thayananthan, A., Stenger, B., Torr, P.H.S., Cipolla, R.: Shape context and chamfer matching in cluttered scenes. In: IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 127–133 (2003)
Belongie, S., Malik, J., Puzicha, J.: Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Analysis and Machine Intelligence 24(4), 509–522 (2002)
Vikstén, F., Forssén, P.E., Johansson, B., Moe, A.: Comparison of local image descriptors for full 6 degree-of-freedom pose estimation. In: IEEE International Conference on Robotics and Automation, pp. 2779–2786 (2009)
Caetano, T.S., Caelli, T., Schuurmans, D., Barone, D.A.C.: Graphical models and point pattern matching. IEEE Trans. Pattern Analysis and Machine Intelligence 28(10), 1646–1663 (2006)
Zheng, Y., Doermann, D.: Robust point matching for nonrigid shapes by preserving local neighborhood structures. IEEE Trans. Pattern Analysis and Machine Intelligence 28, 643–649 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lian, W., Zhang, L. (2012). Robust Point Matching Revisited: A Concave Optimization Approach. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds) Computer Vision – ECCV 2012. ECCV 2012. Lecture Notes in Computer Science, vol 7573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33709-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-33709-3_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33708-6
Online ISBN: 978-3-642-33709-3
eBook Packages: Computer ScienceComputer Science (R0)