Feature matching using quasi-conformal maps

Chun-xue WANG; Li-gang LIU

doi:10.1631/FITEE.1500411

Your Location：

Home >

Browse articles >

Feature matching using quasi-conformal maps

Regular Papers | Updated：2022-05-19

- Feature matching using quasi-conformal maps
- 基于拟共形映射的特征点匹配
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 5, Pages: 644-657(2017)
- Affiliations：
  
  School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China
- Author bio：
  
  E-mail:lgliu@ustc.edu.cn
- Funds：
- DOI：10.1631/FITEE.1500411
  CLC： TP391
- Received：26 November 2015，
  
  Accepted：24 March 2016，
  
  Published：2017-05
- Accepted：
Scan QR Code
Chun-xue WANG, Li-gang LIU. Feature matching using quasi-conformal maps[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(5): 644-657.
DOI：

Chun-xue WANG, Li-gang LIU. Feature matching using quasi-conformal maps[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(5): 644-657. DOI： 10.1631/FITEE.1500411.

摘要

本文提出一种在两幅图像之间寻找保持几何关系一致的特征点对应的自动方法。虽然传统的SIFT（Scale-invariant feature transform）方法能得到一些对应点，但是其中有些对应点是无效的，我们的目标就是去除其中的无效对应点，使得剩下的对应点能够保持在拟共形映射下的几何关系。我们将问题描述为集成Beltrami系数项的拟共形映射的带约束优化问题，是通过交替求解线性系统和线性约束的凸二次规划来求解的。我们的方法非常简单而且对噪声点不敏感，优于一些已有的方法。

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

references

S Belongie , , , J Malik , , , J Puzicha . . Shape matching and object recognition using shape contexts . . IEEE Trans. Patt. Anal. Mach. Intell. , , 2002 . . 24 ( ( 4 ): ): 509 - - 522 . . DOI: 10.1109/34.993558 http://doi.org/10.1109/34.993558 . .

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

S Boyd , , , N Parikh , , , E Chu , , , 等 . . Distributed optimization and statistical learning via the alternating direction method of multipliers . . Found. Trends Mach. Learn. , , 2011 . . 3 ( ( 1 ): ): 1 - - 122 . . DOI: 10.1561/2200000016 http://doi.org/10.1561/2200000016 . .

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

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

P Daripa . . A fast algorithm to solve nonhomogeneous Cauchy-Reimann equations in the complex plane . . SIAM J. Sci. Stat. Comput. , , 1992 . . 13 ( ( 6 ): ): 1418 - - 1432 . . DOI: 10.1137/0913080 http://doi.org/10.1137/0913080 . .

O Duchenne , , , F Bach , , , IS Kweon , , , 等 . . A tensorbased algorithm for high-order graph matching . . IEEE Trans. Patt. Anal. Mach. Intell. , , 2011 . . 33 ( ( 12 ): ): 2383 - - 2395 . . DOI: 10.1109/TPAMI.2011.110 http://doi.org/10.1109/TPAMI.2011.110 . .

MA Fischler , , , RC Bolles . . Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography . . Commun. ACM , , 1981 . . 24 ( ( 6 ): ): 381 - - 395 . . DOI: 10.1145/358669.358692 http://doi.org/10.1145/358669.358692 . .

FP Gardiner , , , N Lakic . . Quasiconformal Teichmüller Theory , , 2000 . . : USA : American Mathematical Society, Providence, , , DOI: 10.1090/surv/076 http://doi.org/10.1090/surv/076 . .

XD Gu , , , ST Yau . . Computational Conformal Geometry , , 2008 . . : Somerville, MA, USA : International Press , , . .

P Heider , , , A Pierre-Pierre , , , R Li , , , 等 . . Local shape descriptors, a survey and evaluation . . 2011 . . Eurographics Workshop on 3D Object Retrieval . . 1 - - 8 . . DOI: 10.2312/3DOR/3DOR11/049-056 http://doi.org/10.2312/3DOR/3DOR11/049-056 . .

GE Hinton , , , CKI Williams , , , MD Revow . . Adaptive elastic models for hand-printed character recognition . . 1991 . . 4th Int. Conf. on Neural Information Processing Systems . . 512 - - 519 . . . .

KT Ho , , , LM Lui . . QCMC: quasi-conformal parameterizations for multiply-connected domains . . Adv. Comput. Math. , , 2016 . . 42 ( ( 2 ): ): 279 - - 312 . . DOI: 10.1007/s10444-015-9424-1 http://doi.org/10.1007/s10444-015-9424-1 . .

B Jian , , , BC Vemuri , , , JL Marroquin . . Robust nonrigid multimodal image registration using local frequency maps . . 2005 . . Biennial Int. Conf. on Information Processing in Medical Imaging . . 504 - - 515 . . DOI: 10.1007/11505730_42 http://doi.org/10.1007/11505730_42 . .

KC Lam , , , LM Lui . . Landmark and intensity-based registration with large deformations via quasi-conformal maps . . SIAM J. Imag. Sci. , , 2014 . . 7 ( ( 4 ): ): 2364 - - 2392 . . DOI: 10.1137/130943406 http://doi.org/10.1137/130943406 . .

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

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

O Lehto , , , KI Virtanen , , , KW Lucas . . Quasiconformal Mappings in the Plane . . Springer New York , , 1973 . . .

Y Li , , , X Xie , , , Z Yang . . Alternating direction method of multipliers for solving dictionary learning . . Commun. Math. Stat. , , 2015 . . 3 37 - - 55 . . DOI: 10.1007/s40304-015-0050-5 http://doi.org/10.1007/s40304-015-0050-5 . .

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

LM Lui , , , TC Ng . . A splitting method for diffeomorphism optimization problem using Beltrami coefficients . . J. Sci. Comput. , , 2015 . . 63 ( ( 2 ): ): 573 - - 611 . . DOI: 10.1007/s10915-014-9903-4 http://doi.org/10.1007/s10915-014-9903-4 . .

LM Lui , , , TW Wong , , , W Zeng , , , 等 . . Optimization of surface registrations using Beltrami holomorphic flow . . J. Sci. Comput. , , 2012 . . 50 ( ( 3 ): ): 557 - - 585 . . DOI: 10.1007/s10915-011-9506-2 http://doi.org/10.1007/s10915-011-9506-2 . .

CW Mastin , , , JF Thompson . . Quasiconformal mappings and grid generation . . SIAM J. Sci. Stat. Comput. , , 1984 . . 5 ( ( 2 ): ): 305 - - 310 . . DOI: 10.1137/0905022 http://doi.org/10.1137/0905022 . .

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

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

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

V Taimouri , , , J Hua . . Deformation similarity measurement in quasi-conformal shape space . . Graph. Models , , 2014 . . 76 ( ( 2 ): ): 57 - - 69 . . DOI: 10.1016/j.gmod.2013.12.001 http://doi.org/10.1016/j.gmod.2013.12.001 . .

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

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

A Vedaldi , , , B Fulkerson . . Vlfeat: an open and portable library of computer vision algorithms . . 2010 . . Proc. 18th ACM Int. Conf. on Multimedia . . 1469 - - 1472 . . DOI: 10.1145/1873951.1874249 http://doi.org/10.1145/1873951.1874249 . .

S Wang , , , Y Wang , , , M Jin , , , 等 . . Conformal geometry and its applications on 3D shape matching, recognition, and stitching . . IEEE Trans. Patt. Anal. Mach. Intell. , , 2007 . . 29 ( ( 7 ): ): 1209 - - 1220 . . DOI: 10.1109/TPAMI.2007.1050 http://doi.org/10.1109/TPAMI.2007.1050 . .

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

SJ Wright . . Coordinate descent algorithms . . Math. Program. , , 2015 . . 151 ( ( 1 ): ): 3 - - 34 . . DOI: 10.1007/s10107-015-0892-3 http://doi.org/10.1007/s10107-015-0892-3 . .

A Yezzi , , , A Mennucci . . Conformal metrics and true “gradient flows” for curves . . 2005 . . ICCV . . 913 - - 919 . . DOI: 10.1109/ICCV.2005.60 http://doi.org/10.1109/ICCV.2005.60 . .

W Zeng , , , XD Gu . . Registration for 3D surfaces with large deformations using quasi-conformal curvature flow . . 2011 . . CVPR . . 2457 - - 2464 . . DOI: 10.1109/CVPR.2011.5995410 http://doi.org/10.1109/CVPR.2011.5995410 . .

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

Z Zhao , , , X Feng , , , S Teng , , , 等 . . Multiscale point correspondence using feature distribution and frequency domain alignment . . Math. Probl. Eng , , 2012 . . 382369 DOI: 10.1155/2012/382369 http://doi.org/10.1155/2012/382369 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰