iccv iccv2013 iccv2013-224 iccv2013-224-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Junchi Yan, Yu Tian, Hongyuan Zha, Xiaokang Yang, Ya Zhang, Stephen M. Chu
Abstract: The problem of graph matching in general is NP-hard and approaches have been proposed for its suboptimal solution, most focusing on finding the one-to-one node mapping between two graphs. A more general and challenging problem arises when one aims to find consistent mappings across a number of graphs more than two. Conventional graph pair matching methods often result in mapping inconsistency since the mapping between two graphs can either be determined by pair mapping or by an additional anchor graph. To address this issue, a novel formulation is derived which is maximized via alternating optimization. Our method enjoys several advantages: 1) the mappings are jointly optimized rather than sequentially performed by applying pair matching, allowing the global affinity information across graphs can be propagated and explored; 2) the number of concerned variables to optimize is in linear with the number of graphs, being superior to local pair matching resulting in O(n2) variables; 3) the mapping consistency constraints are analytically satisfied during optimization; and 4) off-the-shelf graph pair matching solvers can be reused under the proposed framework in an ‘out-of-thebox’ fashion. Competitive results on both the synthesized data and the real data are reported, by varying the level of deformation, outliers and edge densities. ∗Corresponding author. The work is supported by NSF IIS1116886, NSF IIS-1049694, NSFC 61129001/F010403 and the 111 Project (B07022). Yu Tian Shanghai Jiao Tong University Shanghai, China, 200240 yut ian @ s j tu . edu .cn Xiaokang Yang Shanghai Jiao Tong University Shanghai, China, 200240 xkyang@ s j tu .edu . cn Stephen M. Chu IBM T.J. Waston Research Center Yorktown Heights, NY USA, 10598 s chu @u s . ibm . com
[1] B. Bonev, F. Escolano, M. Lozano, P. Suau, M. Cazorla, and W. Aguilar. Constellations and the unsupervised learning of graphs. In GbRPR, 2007.
[2] T. Caetano, J. McAuley, L. Cheng, Q. Le, and A. J. Smola. Learning graph matching. IEEE Transaction on PAMI, 31(6): 1048–1058, 2009.
[3] M. Cho, J. Lee, and K. M. Lee. Reweighted random walks for graph matching. In ECCV, 2010.
[4] D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. IJPRAI, 2004.
[5] O. Duchenne, F. Bach, I. Kweon, and J. Ponce. A tensor-based algorithm for high-order graph matching. In CVPR, 2009.
[6] A. Egozi, Y. Keller, and H. Guterman. A probabilistic approach to spectral graph matching. IEEE Transactions on PAMI, pages 18–27, 2013.
[7] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transaction on PAMI, 1996.
[8] J. Lee, M. Cho, and K. M. Lee. Hyper-graph matching via reweighted randomwalks. In CVPR, 2011.
[9] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV, 2005.
[10] M. Leordeanu and M. Herbert. An integer projected fixed point method for graph matching and map inference. In NIPS, 2009.
[11] M. Leordeanu, R. Sukthankar, and M. Hebert. Unsupervised learning for graph matching. Int. J. Comput. Vis. ,pages 28–45, 2012.
[12] M. Leordeanu, A. Zanfir, and C. Sminchisescu. Semi-supervised learning and optimization for hypergraph matching. In ICCV, 2011.
[13] W. Lian and L. Zhang. Robust point matching revisited: A concave optimization approach. In ECCV, 2012.
[14] J. Maciel and J. Costeira. A global solution to sparse correspondence problems. IEEE Transaction on PAMI, 2003.
[15] S. Ribalta and F. A. Serratosa. A structural and semantic probabilistic model for match- ing and representing a set of graphs. In GbRPR, 2009.
[16] A. Sanfeliu, F. Serratosa, and R. Alqu e´zar. Second-order random graphs for modeling sets of attributed graphs and their application to object learning and recognition. IJPRAI, 2004.
[17] F. Serratosa, R. Alqu e´zar, and A. Sanfeliu. Function-described graphs for modeling objects represented by attributed graphs. Pattern Recognition, 2003.
[18] A. Sol e´-Ribalta and F. Serratosa. On the computation of the common labelling of a set of attributed graphs. In CIARP, 2009. 11665555 cyAua Br0 81.2460CP.Mua5brilteIP0F 1.P 0d1.e5form0at2in.503 ecrABoS0 8.64210 .CPMa5uribetlI0Pi.F1P0.de5form02.aitn 503. BcAyaru 0 18.642CPMa4burielIPtF P6nO8ulteir1024BAerocS0 2.1864MCPuabrietlIPF 6Pn8Ouilter1024 cyAua Cr0 81.2460CP.Mua5brilteIP0F 1.P 0d1.e5form0at2in.503 ecrACoS0 8.64210 .CPMa5uribetlI0Pi.F1P0.de5form02.aitn 503. CcAyaru 0 18.642CPMa4burielIPtF P6nO8ulteir1024CAerocS0 2.1864MCPuabrietlIPF 6Pn8Ouilter1024 cyAuaBCr0 81.2460CP.Mua5brilteIP0F 1.P 0d1.e5form0at2in.503 ecrBCoS0 8.64210 .CPMa5uribetlI0Pi.F1P0.de5form02.aitn 503. CcByaruA0 18.642CPMa4burielIPtF P6nO8ulteir1024CBerocS0 2.1864MCPuabrietlIPF 6Pn8Ouilter1024 cyAua Dr0 81.2460CP.Mua5brilteIP0F 1.P 0d1.e5form0at2in.503 ecrADoS0 8.64210 .CPMa5uribetlI0Pi.F1P0.de5form02.aitn 503. DcAyaru 0 18.642CPMa4burielIPtF P6nO8ulteir1024DAerocS0 2.1864MCPuabrietlIPF 6Pn8Ouilter1024 cyAuaBDr0 81.2460CP.Mua5brilteIP0F 1.P 0d1.e5form0at2in.503 ecrBDoS0 8.64210 .CPMa5uribetlI0Pi.F1P0.de5form02.aitn 503. DcByaruA0 18.642CPMa4burielIPtF P6nO8ulteir1024DBerocS0 2.1864MCPuabrietlIPF 6Pn8Ouilter1024 cyAuaCcDr0 81.2460CP.M0ua5brilteIP0FI 1.PF 0d1.e5form0a.t2ion0.530.5ecrCDoS0 8.64210 .CPMa5uribetlI0Pi.F1 P 01.de5form02.aoitn02.5305DcCyarucA0 18.642 CPMa4burielIPt F P 6nO8ulteir1024DCerocS0 2.18642MCP4uabrietlIP FI P6 n8Ouilter1024 DBCcAyrau0 2.61480MCP0.5aulbrieIPt0F .1P 0.de1f5orm02.aiton0253. CSDrceoBA0 .624180 .CPM5uaribetlIPi01.F P 01.de5form02.aoitn0253. cBDCAyarucA0 18.642 CPMua4britlIPe FI P 6nO8ulteir1024DBCAerocS0 8.6421 PMC4uabrietlIP F P6 n8Ouilter1024 rcAcayucB A00 468.1. PariIPFP B erocSA00 18.6.4.PariIPFP MulitIPFP MulitIPFP 02. CubeIPFP 04 .05.06.07.08.09.1 ratoiFill 02. CubeIPFP 04 .05.06.07.08.09.1 ratoiFill cuCraAyc0 6.24801.4CP0Mua.i5elrbtIPiF 0FP 6.P078.091CAroceS0 18.642.04 5.06 7.08PMCauritlbIPe0 FP9.FP1 ratoiFill ratoiFill cuCraAycB0 6.24801.4CP0Mua.i5elrbtIPiF 0PF6.P078.091CBroceS0 18.6420 .506.708.PMCauritlbIPe0 FP9.FP1 ratoiFill ratoiFill rcAcayucD A00 468.1. PariIPFP D erocSA00 18.6.4.PariIPFP MulitIPFP CubeIPFP 02. 04 .05.06.07.08.09.1 ratoiFill MulitIPFP CubeIPFP 02. 04 .05.06.07.08.09.1 ratoiFill cuDraAycB0 6.24801.4CP0Mua.i5elrbtIPiF 0PF6.P078.091DBroceS0 18.6420 .506.708.PMCauritlbIPe0 FP9.FP1 ratoiFill ratoiFill cuDraAycC0 6.24801.CP0Mua.i5elrbtIPiF 0PF6.0789.1DCroceS0 18.6420.5607.8PMCauritlbIPe0FP9. 1 cCDAycBaur0 .86124PCMariubetlIiPF FP CBAerocSD0 .64218CPMuabrietlIP F P ratoiFill ratoiFill 04 .05.06.07.08.09.1 04 .05.06.07.08.09.1 ratoiFill ratoiFill Figure 4: Performance evaluation for matching four synthetic graphs by varying deformation, outlier #, and edge density: average and deviation of accuracy and score out of 30 random trials. Row 1: accuracy and score of pab; Row 2: accuracy and score of pac; Row 3: accuracy and score of pbc; Row 4: accuracy and score of pad; Row 5: accuracy and score of pbd; Row 6: accuracy and score of pcd; Row 7: accuracy and score of mean of pab,pac,pbc,pbc,pbd,pcd.
[19] A. and F. Serratosa. Models and algorithms for computing the
[23] B. van Wyk and M. van Wyk. A pocs-based graph matching algorithm. IEEE labelling of a set of attributed graphs. CVIU, 2011.Transaction on Pattern Analysis and Machine Intelligence, 2004. Sol e´-Ribalta common
[24] bMay.Le s.iWa ni li nifamersen, Rce.. C Pa.t Wteirlnso Rne,c aongdni Eti.o Hna nLectotcerks.,p M auglteispl 1e2 g7r5a–p1h2 m81,at 1c9h9in7g. with
[20] P. S. T. Cour and J. Shi. Balanced graph matching. In NIPS, 2006.
[25] tAo. s Wtrouncgtur a nld p aMt. er Yno rue.c Eogn troitpoyn. an IEdE dEist Tarnacnes oafct riaon dso omn g PraApMhsI, w 1i9t8h5 .ap lication
[21] oY.fT g iraapnh, J m.Ya tacnh,in Hg.: Z Ghraandgu,a Yte. dZ ahsansiggn,m X.en Yta rnegv,is aintded H.. I Znh EaC. OCVn, th 20e1 c2o.nvergence
[22]
[26] R. Zass and A. Shashua. Probabilistic graph and hypergraph matching. In CVPR, 2008. Torresani, V. Kolmogorov, and C. Rother. Feature correspondence via graph matching: Models and global optimization. In ECCV, 2008. L. 11665566