Two standard object extraction methods Interactive Graph cuts

Two standard object extraction methods

• Interactive Graph cuts

• [Boykov&Jolly ‘01]

• Discrete formulation
• Computes min-cuts on N-D grid-graphs

Graph cuts (simple example à la Boykov&Jolly, ICCV’01)

Metrication errors on graphs

Cut Metrics : cuts impose metric properties on graphs

Our key technical result

Integral Geometry and Cauchy-Crofton formula

Cut Metric on grids can approximate Euclidean Metric

Cut metric in Euclidean case

Reducing Metrication Artifacts

Cut Metric in Riemannian case

• The same technique can used to compute edge weights that approximate arbitrary Riemannian metric defined by tensor D(p)

• Idea: generalize Cauchy-Crofton formula

Convergence theorem

“Geo-Cuts” algorithm

Minimal surfaces in image induced Riemannian metric spaces (3D)

Our results reveal a relation between…

• Level Sets Graph Cuts

• [Osher&Sethian’88,…] [Greig et. al.’89, Ishikawa et. al.’98, BVZ’98,…]

Conclusions

• “Geo-cuts” combines geodesic contours and graph cuts.

• The method can be used as a “global” alternative to variational level-sets.

• Reduction of metrication errors in existing graph cut methods

• stereo [Roy&Cox’98, Ishikawa&Geiger’98, Boykov&Veksler&Zabih’98, ….]
• image restoration/segmentation [Greig’86, Wu&Leahy’97,Shi&Malik’98,…]
• texture synthesis [Kwatra/et.al’03]

• Theoretical connection between discrete geometry of graph cuts and concepts of integral & differential geometry

Geo-cuts (more examples)