1Recognition of Shapes by Editing Shock GraphsPresented by Changhai XuMar 6, 2007(Sebastian, Klein & Kimia)• Objective– To operationalize the notion of shape similarity, and use it as a basis for categroty-level recognition• Motivation– Shape is an important cue for recognition, but it is difficult to extract, characterize and representIntroduction• Shape is represented by point sets– May not capture the global measure– May be alleviated by using a global shape context, but is still sensitive to partial occlusion and part articulation• Shape is represented by curve– Sensitive to articulations and deformationsRelated Work• Shape is represented by medial axis– Some obvious shape deformations cannot be captured– May not preserve the ordering of edges1. Use shock graphs to represent shapes2. Partition shape space by defining an equivalence class of shapes3. Discretize deformation space by defining an equivalence class of deformation paths4. Employ an edit-distance algorithm to find the optimal deformation pathOverviewShock Graphs•Medial Axis- locus of centers of maximal circles that are bitangent to shape boundaryReal ExampleShape boundaryMedial AxisShock Graphs (2)•Shock Graph- A dynamic interpretation of the medial axis- With associated direction of flow2• Shape space– Shape is a point– Shape deformation sequence is a pathPartition the shape space• Shape cell– A collection of shapes that have the same shock graph topology• Transition shapes– form the boundary between shape cellsPartition the shape space (2)Shape cell 2Shape cell 1• The number of deformation paths between two shapes is infinite• Finding the optimal deformation path is intractableDiscretize the deformation space• Two deformation paths are equivalent if they pass through the same sequence of shock graph transitionsDiscretize the deformation space (2)Avoid Complexity-Increasing Paths• Complexity-increasing shape deformation paths are not optimal• Represent a deformation path by a pair of simplifying deformation paths from A, B to a simpler shape C Edit Operations for Shock Graphs• Four edit operations are needed for shock graphs– Deform: changes the attributes of a shock branch– Merge: combines two branches at a degree-two node – Splice: deletes a shock branch and merges the remaining two– Contract: deletes a shock branch between degree-three nodes3Assign Costs to Edit Operations• Derive the cost of the deform edit:- Sum over local shape differences between matching shock segments• Derive the cost of other edits:- The limit of the deform cost as the shape moves to the boundary of the shape cellDeform Cost between Shock Edges• Deform cost between shock edges consists of – Length differences of shock segments– Curvature differences of shock segments– Length differences of the boundary segments– Curvature differences of boundary segments– Difference in width of shape– Difference in relative orientation of boundary segmentsEdit Distance between Shapes• Edit-distance is defined as the sum of the cost of edits in optimal edit sequenceExperiment ResultsEdit-distance algorithm gives intuitive results* Same colors indicate matching edges; gray-colored edges are prunedMatching Results• Shock graphs represents object parts and part hierarchyEdit-distance is robust in presence of part-based changesArticulations4• Deform edit handles smooth changes• Splice and contract edits handle abrupt changesSmooth changeAbrupt changeView-point changesEdit-distance is robust to partial occlusionPartial Occlustions• Shock graphs are sensitive to boundary noiseIn optimal edit sequence “noisy”branches are prunedBoundary noises•Strengths- Planar ordered shock graph representation- Discretization of shape space and deformation space, which makes the problem of finding an optimal deformation path practical- Incorporation of edit-distance algorithm that finds the optimal path in polynomial time- Robustness to various visual transformationsConclusions•Weaknesses- Good segmentation is required- Edit operations are sensitive to noises- Edit operations are sensitive to scale- Exhaustively searching of optimal deformation path still needs expensive computation- It doesn’t capture any features within the boundary- The shape representation is not a statistical model and is not yet suitable for learning of object classesConclusions (2)Thank
View Full Document
Unlocking...