Featurematching using quasi-conformalmaps

Abstract

We present a fully automatic method for finding geometrically consistent correspondences while discarding outliers from the candidate point matches in two images. Given a set of candidate matches provided by scale-invariant feature transform (SIFT) descriptors, which may contain many outliers, our goal is to select a subset of these matches retaining much more geometric information constructed by a mapping searched in the space of all diffeomorphisms. This problem can be formulated as a constrained optimization involving both the Beltrami coefficient (BC) term and quasi-conformal map, and solved by an efficient iterative algorithm based on the variable splitting method. In each iteration, we solve two subproblems, namely a linear system and linearly constrained convex quadratic programming. Our algorithm is simple and robust to outliers. We show that our algorithm enables producing more correct correspondences experimentally compared with state-of-the-art approaches.

Keywords

Feature correspondence / Quasi-conformal map / Splitting method

References

[1] Belongie,S., Malik,J., Puzicha,J. , 2002. Shape matching and object recognition using shape contexts. IEEE Trans. Patt. Anal. Mach. Intell., 24(4):509–522.

[2] Bers,L., 1977. Quasiconformal mappings, with applications to differential equations, function theory and topology. Bull. Am. Math. Soc., 83(6):1083–1100.

[3] Boyd,S., Parikh, N., Chu,E. , , 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 3(1):1–122.

[4] Chui,H., Rangarajan, A., 2003. A new point matching algorithm for non-rigid registration. Comput. Vis. Image Understand., 89(2-3):114–141.

[5] Daripa,P., 1991. On a numerical method for quasi-conformal grid generation. J. Comput. Phys., 96(1):229–236.

[6] Daripa,P., 1992. A fast algorithm to solve nonhomogeneous Cauchy-Reimann equations in the complex plane. SIAM J. Sci. Stat. Comput., 13(6):1418–1432.

[7] Duchenne,O., Bach,F., Kweon,I.S. , , 2011. A tensorbased algorithm for high-order graph matching. IEEE Trans. Patt. Anal. Mach. Intell., 33(12):2383–2395.

[8] Fischler,M.A., Bolles, R.C., 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM, 24(6):381–395.

[9] Gardiner,F.P., Lakic, N., 2000. Quasiconformal Teichmüller Theory. American Mathematical Society, Providence, USA.

[10] Gu,X.D., Yau,S.T., 2008. Computational Conformal Geometry. International Press, Somerville, MA, USA.

[11] Heider,P., Pierre-Pierre, A., Li,R. , , 2011. Local shape descriptors, a survey and evaluation. Eurographics Workshop on 3D Object Retrieval, p.1–8.

[12] Hinton,G.E., Williams, C.K.I., Revow,M.D. , 1991. Adaptive elastic models for hand-printed character recognition. 4th Int. Conf. on Neural Information Processing Systems, p.512–519.

[13] Ho,K.T., Lui,L.M., 2016. QCMC: quasi-conformal parameterizations for multiply-connected domains. Adv. Comput. Math., 42(2):279–312.

[14] Jian,B., Vemuri, B.C., Marroquin,J.L. , 2005. Robust nonrigid multimodal image registration using local frequency maps. Biennial Int. Conf. on Information Processing in Medical Imaging, p.504–515.

[15] Lam,K.C., Lui,L.M., 2014. Landmark and intensity-based registration with large deformations via quasi-conformal maps. SIAM J. Imag. Sci., 7(4):2364–2392.

[16] Lazebnik,S., Schmid, C., Ponce,J. , 2004. Semi-local affine parts for object recognition. British Machine Vision Conf., p.779–788.

[17] Lazebnik,S., Schmid, C., Ponce,J. , 2005. A maximum entropy framework for part-based texture and object recognition. ICCV, p.832–838.

[18] Lehto,O., Virtanen, K.I., Lucas,K.W. , 1973. Quasiconformal Mappings in the Plane. Springer New York.

[19] Li,Y., Xie,X., Yang,Z., 2015. Alternating direction method of multipliers for solving dictionary learning. Commun. Math. Stat., 3:37–55.

[20] Lipman,Y., Yagev, S., Poranne,R. , , 2014. Feature matching with bounded distortion. ACM Trans. Graph., 33(3):26.

[21] Lui,L.M., Ng,T.C., 2015. A splitting method for diffeomorphism optimization problem using Beltrami coefficients. J. Sci. Comput., 63(2):573–611.

[22] Lui,L.M., Wong,T.W., Zeng,W., , 2012. Optimization of surface registrations using Beltrami holomorphic flow. J. Sci. Comput., 50(3):557–585.

[23] Mastin,C.W., Thompson, J.F., 1984. Quasiconformal mappings and grid generation. SIAM J. Sci. Stat. Comput., 5(2):305–310.

[24] Montagnat,J., Delingette, H., Ayache,N. , 2001. A review of deformable surfaces: topology, geometry and deformation. Image Vis. Comput., 19(14):1023–1040.

[25] Nealen,A., Müller, M., Keiser,R. , , 2006. Physically based deformable models in computer graphics. Comput. Graph. For., 25(4):809–836.

[26] Sasaki,Y., 2007. The Truth of the F-measure. School of Computer Science, University of Manchester.

[27] Taimouri,V., Hua,J., 2014. Deformation similarity measurement in quasi-conformal shape space. Graph. Models, 76(2):57–69.

[28] Tuytelaars,T., Mikolajczyk, K., 2008. Local invariant feature detectors: a survey. Found. Trends Comput. Graph. Vis., 3(3):177–280.

[29] van Kaick,O., Zhang, H., Hamarneh,G. , , 2011. A survey on shape correspondence. Comput. Graph. For., 30(6):1681–1707.

[30] Vedaldi,A., Fulkerson, B., 2010. Vlfeat: an open and portable library of computer vision algorithms. Proc. 18th ACM Int. Conf. on Multimedia, p.1469–1472.

[31] Wang,S., Wang,Y., Jin,M., , 2007. Conformal geometry and its applications on 3D shape matching, recognition, and stitching. IEEE Trans. Patt. Anal. Mach. Intell., 29(7):1209–1220.

[32] Weber,O., Myles, A., Zorin,D. , 2012. Computing extremal quasiconformal maps. Comput. Graph. For., 31(5):1679–1689.

[33] Wright,S.J., 2015. Coordinate descent algorithms. Math. Program., 151(1):3–34.

[34] Yezzi,A., Mennucci, A., 2005. Conformal metrics and true “gradient flows” for curves. ICCV, p.913–919.

[35] Zeng,W., Gu,X.D., 2011. Registration for 3D surfaces with large deformations using quasi-conformal curvature flow. CVPR, p.2457–2464.

[36] Zeng,W., Hua,J., Gu,X., 2009. Symmetric conformal mapping for surface matching and registration. Int. J. CAD/CAM, 9(1):103–109.

[37] Zhao,Z., Feng,X., Teng,S., , 2012. Multiscale point correspondence using feature distribution and frequency domain alignment. Math. Probl. Eng., 2012:382369.

RIGHTS & PERMISSIONS

Zhejiang University and Springer-Verlag Berlin Heidelberg