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. http://dx.doi.org/10.1109/34.993558

[2] Bers,L., 1977. Quasiconformal mappings, with applications to differential equations, function theory and topology. Bull. Am. Math. Soc., 83(6):1083–1100. http://dx.doi.org/10.1090/S0002-9904-1977-14390-5

[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. http://dx.doi.org/10.1561/2200000016

[4] Chui,H., Rangarajan, A., 2003. A new point matching algorithm for non-rigid registration. Comput. Vis. Image Understand., 89(2-3):114–141. http://dx.doi.org/10.1016/S1077-3142(03)00009-2

[5] Daripa,P., 1991. On a numerical method for quasi-conformal grid generation. J. Comput. Phys., 96(1):229–236. http://dx.doi.org/10.1016/0021-9991(91)90274-O

[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. http://dx.doi.org/10.1137/0913080

[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. http://dx.doi.org/10.1109/TPAMI.2011.110

[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. http://dx.doi.org/10.1145/358669.358692

[9] Gardiner,F.P., Lakic, N., 2000. Quasiconformal Teichmüller Theory. American Mathematical Society, Providence, USA. http://dx.doi.org/10.1090/surv/076

[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. http://dx.doi.org/10.2312/3DOR/3DOR11/049-056

[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. http://dx.doi.org/10.1007/s10444-015-9424-1

[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. http://dx.doi.org/10.1007/11505730_42

[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. http://dx.doi.org/10.1137/130943406

[16] Lazebnik,S., Schmid, C., Ponce,J. , 2004. Semi-local affine parts for object recognition. British Machine Vision Conf., p.779–788. http://dx.doi.org/10.5244/C.18.98

[17] Lazebnik,S., Schmid, C., Ponce,J. , 2005. A maximum entropy framework for part-based texture and object recognition. ICCV, p.832–838. http://dx.doi.org/10.1109/ICCV.2005.10

[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.http://dx.doi.org/10.1007/s40304-015-0050-5

[20] Lipman,Y., Yagev, S., Poranne,R. , , 2014. Feature matching with bounded distortion. ACM Trans. Graph., 33(3):26. http://dx.doi.org/10.1145/2602142

[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. http://dx.doi.org/10.1007/s10915-014-9903-4

[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. http://dx.doi.org/10.1007/s10915-011-9506-2

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

[24] Montagnat,J., Delingette, H., Ayache,N. , 2001. A review of deformable surfaces: topology, geometry and deformation. Image Vis. Comput., 19(14):1023–1040. http://dx.doi.org/10.1016/S0262-8856(01)00064-6

[25] Nealen,A., Müller, M., Keiser,R. , , 2006. Physically based deformable models in computer graphics. Comput. Graph. For., 25(4):809–836. http://dx.doi.org/10.1111/j.1467-8659.2006.01000.x

[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. http://dx.doi.org/10.1016/j.gmod.2013.12.001

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

[29] van Kaick,O., Zhang, H., Hamarneh,G. , , 2011. A survey on shape correspondence. Comput. Graph. For., 30(6):1681–1707. http://dx.doi.org/10.1111/j.1467-8659.2011.01884.x

[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. http://dx.doi.org/10.1145/1873951.1874249

[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. http://dx.doi.org/10.1109/TPAMI.2007.1050

[32] Weber,O., Myles, A., Zorin,D. , 2012. Computing extremal quasiconformal maps. Comput. Graph. For., 31(5):1679–1689.http://dx.doi.org/10.1111/j.1467-8659.2012.03173.x

[33] Wright,S.J., 2015. Coordinate descent algorithms. Math. Program., 151(1):3–34. http://dx.doi.org/10.1007/s10107-015-0892-3

[34] Yezzi,A., Mennucci, A., 2005. Conformal metrics and true “gradient flows” for curves. ICCV, p.913–919. http://dx.doi.org/10.1109/ICCV.2005.60

[35] Zeng,W., Gu,X.D., 2011. Registration for 3D surfaces with large deformations using quasi-conformal curvature flow. CVPR, p.2457–2464. http://dx.doi.org/10.1109/CVPR.2011.5995410

[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. http://dx.doi.org/10.1155/2012/382369

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag Berlin Heidelberg