现代优化方法现代优化方法 (3).pdf

9.4 Quadratic Penalty Method forHypergraph MatchingQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching1/15IntroductionRelaxation ProblemQuadratic Penalty MethodNumerical ResultsQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching2/15Graph MatchingQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching3/15Applications of Graph Matching:computer visionQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching4/15Graph MatchingFigure:Illustration of graph matchingAim of graph matching:Establish correspondence between two feature sets.Qingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching5/15Hypergraph MatchingQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching6/15Mathematical FormulationGiven hypergraphs G1=V1,E1,G2=V2,E2V1and V2:sets of points,|V1|=n1,|V2|=n2.For example,V1=1,2,3,4,V2=a,b,c,d,eE1,E2:sets of hyperedges.For example,(1,2,3)E1,(a,b,c)E2Aim:find assignment matrix X IRn1n2:Xl1l2=1,if l1 V1is assigned to l2 V2;0,otherwise.Qingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching7/15Hypergraph MatchingMatching of Hyperedges(l1,j1,k1)E1and(l2,j2,k2)E2:if Xl1l2Xj1j2Xk1k2=1,i.e.,l1 l2,j1 j2and k1 k2Matching Score B:Bl1l2j1j2k1k2:matching score between(l1,j1,k1)and(l2,j2,k2).Bl1l2j1j2k1k2 0,if(l1,j1,k1)E1and(l2,j2,k2)E2;otherwise,0.B Rn1n2n1n2n1n2:a sixth order tensor.Qingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching8/15Formulation of Hypergraph MatchingProblems StatementGiven G1=V1,E1,and G2=V2,E2,B,find thecorrespondence between feature sets V1and V2suchthat the sum of matching scores achieves themaximum.FormulationmaxX1(l1,j1,k1)E1,(l2,j2,k2)E2Bl1l2j1j2k1k2Xl1l2Xj1j2Xk1k2,(1.1)where1=X 0,1n1n2:n2l2=1Xl1l2=1,l1=1,.,n1,n1 n2,(1.2)Qingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching9/15A special case(n1=n2,permutation constraints)2=X 0,1n1n1:n1l2=1Xl1l2=1,l1=1,.,n1;n1l1=1Xl1l2=1,l2=1,.,n1.(1.3)Qingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching10/15Formulation of Hypergraph MatchingX=X11X1n2.Xn11 Xn1n2:=xT1.xTn1.x=x1.xn1.Xl1l2 xl,Xj1j2 xj,wherel=(l11)n2+l2,j=(j11)n2+j2,k=(k11)n2+k2.Bl1l2j1j2k1k2Xl1l2Xj1j2Xk1k2 Aljkxlxjxk.Qingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching11/15(1.1)is equivalent tominxRnf(x):=l,j,kAljkxlxjxk=16Ax3s.t.eT xi=1,i=1,.,n1,x 0,1,(1.4)where n=n1n2,A IRnnn.0-1 programmingNP hard in generalQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching12/15Existing methods:TM1:power iteration algorithmHypergraph Matching method via Reweighted Random Walks(RRWHM)2:dealt with the problem by randomly walkingamong two feasible vectors.HGM3:reformulated the constraints as the intersection of three convexsets,and successively projected the variables onto the sets untilconvergence.Block Coordinate Ascent Graph Matching(BCAGM)4:applied a block coordinate ascent framework,where they kept thebinary constraints,and proposed to reformulate the multi-linearobjective function into a linear one and solve it using linearassignment algorithms.Qingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching13/15Relax 0,1 to 0,1Reduce to a series of small size of assignment problemsQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching14/15SummaryHypergraph MatchingMathematical FormulationExisting MethodsQingna Li(BIT)9.4 Quadratic Penalty Method for Hypergraph Matching15/15