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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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
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
Boyd, S., Parikh, N., Chu, E., et al., 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
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
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
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
Duchenne, O., Bach, F., Kweon, I.S., et al., 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
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
Gardiner, F.P., Lakic, N., 2000. Quasiconformal Teichmüller Theory. American Mathematical Society, Providence, USA. http://dx.doi.org/10.1090/surv/076
Gu, X.D., Yau, S.T., 2008. Computational Conformal Geometry. International Press, Somerville, MA,USA.
Heider, P., Pierre-Pierre, A., Li, R., et al., 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
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.
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
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
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
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
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
Lehto, O., Virtanen, K.I., Lucas, K.W., 1973. Quasiconformal Mappings in the Plane. Springer New York.
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
Lipman, Y., Yagev, S., Poranne, R., et al., 2014. Feature matching with bounded distortion. ACM Trans. Graph., 33(3):26. http://dx.doi.org/10.1145/2602142
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
Lui, L.M., Wong, T.W., Zeng, W., et al., 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
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
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
Nealen, A., Müller, M., Keiser, R., et al., 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
Sasaki, Y., 2007. The Truth of the F-measure. School of Computer Science, University of Manchester.
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
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
van Kaick, O., Zhang, H., Hamarneh, G., et al., 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
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
Wang, S., Wang, Y., Jin, M., et al., 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
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
Wright, S.J., 2015. Coordinate descent algorithms. Math. Program., 151(1):3–34. http://dx.doi.org/10.1007/s10107-015-0892-3
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
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
Zeng, W., Hua, J., Gu, X., 2009. Symmetric conformal mapping for surface matching and registration. Int. J. CAD/CAM, 9(1):103–109.
Zhao, Z., Feng, X., Teng, S., et al., 2012. Multiscale point correspondence using feature distribution and frequency domain alignment. Math. Probl. Eng., 2012:382369. http://dx.doi.org/10.1155/2012/382369
Author information
Authors and Affiliations
Corresponding author
Additional information
Project supported by the National Natural Science Foundation of China (Nos. 61672482 and 11626253) and the One Hundred Talent Project of the Chinese Academy of Sciences
ORCID: Chun-xue WANG, http://orcid.org/0000-0002-2118-3016
Rights and permissions
About this article
Cite this article
Wang, Cx., Liu, Lg. Feature matching using quasi-conformal maps. Frontiers Inf Technol Electronic Eng 18, 644–657 (2017). https://doi.org/10.1631/FITEE.1500411
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.1500411