Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Computer VisionNovember 2003 L1.1© 2003 by Davi GeigerShape Representation and SimilarityOcclusion ArticulationShape similarities should be preserved under occlusions and articulation.Two equal stretching along contours can affect shape similarity differently. Shapes can be represented by contours, or by a set of interior points, or other ways. What is the shape representation that can be best used for shape similarity?StretchingStretchingComputer VisionNovember 2003 L1.2© 2003 by Davi GeigerShape Axis (SA) SA-Tree Shape Symmetry Axis RepresentationComputer VisionNovember 2003 L1.3© 2003 by Davi Geiger A variational shape representation model based on self-similarity of shapes.For each shape contour, first compute its shape axis then derive a unique shape-axis-tree (SA-tree) or shape-axis-forest (SA-forest) representation.Shape Axis (SA) SA-TreeShape ContourShape Representation via Self-SimilarityBased on work of Liu, Kohn and GeigerComputer VisionNovember 2003 L1.4© 2003 by Davi GeigerUse Use twotwo different parameterizations to compute the different parameterizations to compute the represention of a shape.represention of a shape.Construct a cost functional to measure the Construct a cost functional to measure the goodnessgoodness of a of a match between the two parameterizations.match between the two parameterizations. The cost functional is decided by the self-similarity criteria The cost functional is decided by the self-similarity criteria of of symmetrysymmetry..The InsightcounterclockwiseclockwiseComputer VisionNovember 2003 L1.5© 2003 by Davi GeigerTwo different parameterizations:Two different parameterizations: counterclockwisecounterclockwise clockwiseclockwise When the curve is closed we haveWhen the curve is closed we haveMatching the curves is described as the match of functionsMatching the curves is described as the match of functionsParameterized Shapes}10:)({1 ssx}10:)(~{2 ttx)1()(~: txtxnote (1)x~(0)x~ and )1()0( xx))((x~ ))(x(or[0,1];)()(tsts Computer VisionNovember 2003 L1.6© 2003 by Davi GeigerA Global Optimization ApproachWe seek “good” matches over the possible correspondencesWe seek “good” matches over the possible correspondences [0,1]where))((x~ ))(x(or)()( tsts)1()(~: txtxnote Computer VisionNovember 2003 L1.7© 2003 by Davi GeigerCo-CircularityMirror SymmetrySimilarity criteria: Symmetry  )('))((~)()(~))((~)())(()()())((where)())((~))(())((~)(()())((~))(())((~)((of valuessmall give shoulderror y thisIntuitivelror.measure/ersymmetry a define nowcan but we symmetry,perfect havelonger nomay we~ tangent extra theGiven y.circularit-osymmetry/cmirror defines~point another and, tangent its ,point Onettddtdttxddtxdssddsdssdxdsdxbdtxddsdxtxsxadtxddsdxtxsxxx--)(~t)(~tx)(~t)(~t)(~tx)(~t)(sx)(s)(~tx)(sx)(s)(~txComputer VisionNovember 2003 L1.8© 2003 by Davi Geiger nt vectorsunit tange oriented are))((~and))((where),()( escorresponc possible allover )(),(,))((~)),((x~)),(()),(x( ))(t,)E(s(Minimize10tstσsdtsttssFA Global Optimization ApproachComputer VisionNovember 2003 L1.9© 2003 by Davi GeigerConstraints on the form of F        ).( and)( maps of choice on thenot and)()(match on theonly dependscost that theassuring~)~(),~(,~,x~,,x~,~,~,x~,,x~~,,~,x~,,x)(),(,~,x~,,x)(~ :ationparametriz of changeany under invarianceobtain To)(),(,~,x~,,x)(),(,~,x~,,x Condition Scaling 2.roles equivalentplay ~and i.e.,)(),(,,x,~,x~)(),(,~,x~,,xmatch theofSymmetry 1.10~101010tstsdtsFdddddtddddsFdddddtddsFdtsFtsFtsFstFtsFComputer VisionNovember 2003 L1.10© 2003 by Davi GeigerConstraints on the form of F (cont.)       . )(amount known andt independen shape aby cost thechange and matching thepreserve will factorcommon by the ~ sand scaling Thus, ).(function somefor )(),(,,~,x~,,x)()(),(,~,x~,,x Invariance Scaling 4.cost affect thenot willations transformrigid that so )(),(,,~,x~,,x)(),(,~,x~,,xInvarianceRotation 3.ggtsFgtsFPartialtsFtsRRRRFComputer VisionNovember 2003 L1.11© 2003 by Davi Geiger          --10221010)()(')()('))((~)())(())((~))(()(')()('))((~)())(())((~)(()(),(,~,x~,,xas defined is encecorrespondany for cost symmetry The).)( giveslly automatica(which )( mappings possible allover cost theminize we)2constraint()(zation parameteriarbitrary any for where)(),(,~,x~,,xmin)~,(as measuresymmetry thewrite WedtsttsstxsxtsttsstxsxdtsFsttsdtsFStSimilarity criteria: SymmetryComputer VisionNovember 2003 L1.12© 2003 by Davi GeigerSimilarity criteria: Symmetry II(a)(b)dFstE JumpCost )()similarity-self())(),((10         solution theof cost) (jump nsbifurcatiofor cost a add we(d), and (c) see parts,object for nsbifurcatio allow andty irregulari shape toduesnbifurcatio ofcreation theavoid To small. be should parameter The)(')()(')())((~))(()(')()('))((~)())(())((~))(()(')()('))((~)())(())((~)(()(),(,~,x~,,xsolutions (b)over (a) bias topoints, closedbetween encescorrespond bias to term thirda add