Computing Geodesics and Minimal Surfaces Via Graph Cuts: Yuri Boykov, Siemens Research, Princeton, NJ

Corp.
Research
Princeton, NJ
Computing geodesics and minimal

surfaces via graph cuts
Yuri Boykov, Siemens Research, Princeton, NJ
joint work with

Vladimir Kolmogorov, Cornell University, Ithaca, NY
Two standard Corp. Research
object extraction methods Princeton, NJ
Geodesic active contours Interactive Graph cuts

[Caselles et.al. ‘97, Yezzi et.al ‘97] [Boykov&Jolly ‘01]
• Continuous formulation • Discrete formulation

• Computes geodesics in image- • Computes min-cuts on
based N-D Riemannian spaces N-D grid-graphs
• Minimal geometric artifacts • Possible metrication errors
• Solved via local variational
• Global minima
technique (level sets)
Geo-cuts
Corp. Research
Geodesics and minimal surfaces Princeton, NJ
 The shortest curve between two points is a geodesic

distance
map B distance
map B
A A
Euclidian metric Riemannian metric

(constant) (space varying, tensor D(p))
 Geodesic contours use image-based Riemannian metric

 Generalizes to 3D (minimal surfaces)
Graph cuts Corp. Research
Princeton, NJ
(simple example à la Boykov&Jolly, ICCV’01)
hard
t
n-links a cut
constraint
hard
constraint
s
Minimum cost cut can be computed in polynomial time

(max-flow/min-cut algorithms)
Corp. Research
Metrication errors on graphs Princeton, NJ
Minimum cost cut Minimum length geodesic contour

(standard 4-neighborhoods) (image-based Riemannian metric)
discrete metric ??? Continuous metric space

(no geometric artifacts!)
Cut Metrics : Corp. Research
cuts impose metric properties on graphs Princeton, NJ
C || C ||   |e|
eC
 Cost of a cut can be interpreted as a geometric “length” (in 2D) or

“area” (in 3D) of the corresponding contour/surface.
Cut metric is determined by the graph topology and by edge weights.

 Can a cut metric approximate a given Riemannian metric?
Corp. Research
Our key technical result Princeton, NJ
We show how to build a grid-graph such that its

cut metric approximates any given Riemannian metric
 The main technical problem is solved via Cauchy-Crofton

formula from integral geometry.
Integral Geometry and Corp. Research
Cauchy-Crofton formula Princeton, NJ
a subset of lines L
 intersecting contour C
C 2
a set of all
LC
lines L 
0 
Euclidean length of C : || C ||  1

2  n L  d  d
the number of times
line L intersects C
Cut Metric on grids Corp. Research
can approximate Euclidean Metric Princeton, NJ
Graph nodes are imbedded

in R2 in a grid-like fashion
C
Edges of any regular
neighborhood system
generate families of lines
{ , , , }
|| C ||  1
2 n k   k  k  || C ||gc
Euclidean k graph cut cost  k  k
length for edge weights: wk 
the number of edges of 2
family k intersecting C
Corp. Research
Cut metric in Euclidean case Princeton, NJ
  k  k
 (Positive!) weights wk  depend only on
2 edge direction k.
 “Distance maps” (graph nodes “equidistant” from a given node) :
“standard” 8-neighborhoods 256-neighborhoods

4-neighborhoods
(Manhattan metric)
Corp. Research
Reducing Metrication Artifacts Princeton, NJ
Image restoration [BVZ 1999]
original restoration restoration

noisy image with “standard” with 8-neighborhoods
4-neighborhoods using edge weights
 k  k
wk 
2
Corp. Research
Cut Metric in Riemannian case Princeton, NJ
 The same technique can used to compute edge weights that

approximate arbitrary Riemannian metric defined by tensor D(p)
• Idea: generalize Cauchy-Crofton formula

 (Positive!) weights w ( p )  f ( k , D ( p )) depend on
k
edge direction k and on location/pixel p.

 Local “distance maps” assuming anisotropic D(p) = const
4-neighborhoods 8-neighborhoods 256-neighborhoods

Corp. Research
Convergence theorem Princeton, NJ

Theorem: For edge weights w ( p ) set by tensor D(p)
k
| e | 0
|| C || gc  
  || C ||
  0 ,  0
Corp. Research
“Geo-Cuts” algorithm Princeton, NJ
image-derived regular grid edge weights

Riemannian metric
D(p) wk ( p )
Boundary conditions
(hard/soft constraints) Graph-cuts
[Boykov&Jolly, ICCV’01]
Global optimization
min-cut = geodesic
|| Cˆ || gc  || Cˆ ||
Minimal surfaces in image induced Corp. Research
Riemannian metric spaces (3D) Princeton, NJ
3D bone segmentation (real time screen capture)

Our results reveal a relation Corp. Research
between… Princeton, NJ
Level Sets Graph Cuts

[Osher&Sethian’88,…] [Greig et. al.’89, Ishikawa et. al.’98, BVZ’98,…]
variational optimization method for combinatorial optimization for

fairly general continuous energies a restricted class of energies [e.g. KZ’02]
finds a local minimum finds a global minimum
near given initial solution for a given set of boundary conditions
numerical stability has to be carefully
addressed [Osher&Sethian’88]: numerical stability is not an issue
continuous formulation -> “finite discrete formulation ->min-cut algorithms
differences”
anisotropic metrics are harder anisotropic Riemannian metrics
to deal with (e.g. slower) are as easy as isotropic ones
Gradient descent method VS. Global minimization tool

(restricted class of energies)
Corp. Research
Conclusions Princeton, NJ
 “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 Corp. Research
(more examples) Princeton, NJ
3D segmentation (time-lapsed)

Computing Geodesics and Minimal Surfaces Via Graph Cuts: Yuri Boykov, Siemens Research, Princeton, NJ

Uploaded by

Copyright:

Available Formats

Computing Geodesics and Minimal Surfaces Via Graph Cuts: Yuri Boykov, Siemens Research, Princeton, NJ

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Computing Geodesics and Minimal Surfaces Via Graph Cuts: Yuri Boykov, Siemens Research, Princeton, NJ

Uploaded by

Copyright:

Available Formats

Corp.

Computing geodesics and minimal

Yuri Boykov, Siemens Research, Princeton, NJ

joint work with

object extraction methods Princeton, NJ

Geodesic active contours Interactive Graph cuts

• Continuous formulation • Discrete formulation

Geodesics and minimal surfaces Princeton, NJ

 The shortest curve between two points is a geodesic

Euclidian metric Riemannian metric

 Geodesic contours use image-based Riemannian metric

Minimum cost cut can be computed in polynomial time

Metrication errors on graphs Princeton, NJ

Minimum cost cut Minimum length geodesic contour

discrete metric ??? Continuous metric space

cuts impose metric properties on graphs Princeton, NJ

 Cost of a cut can be interpreted as a geometric “length” (in 2D) or

Cut metric is determined by the graph topology and by edge weights.

Our key technical result Princeton, NJ

We show how to build a grid-graph such that its

 The main technical problem is solved via Cauchy-Crofton

Cauchy-Crofton formula Princeton, NJ

Euclidean length of C : || C ||  1

can approximate Euclidean Metric Princeton, NJ

Graph nodes are imbedded

Cut metric in Euclidean case Princeton, NJ

 “Distance maps” (graph nodes “equidistant” from a given node) :

“standard” 8-neighborhoods 256-neighborhoods

Reducing Metrication Artifacts Princeton, NJ

Image restoration [BVZ 1999]

original restoration restoration

Cut Metric in Riemannian case Princeton, NJ

 The same technique can used to compute edge weights that

edge direction k and on location/pixel p.

4-neighborhoods 8-neighborhoods 256-neighborhoods

Convergence theorem Princeton, NJ

“Geo-Cuts” algorithm Princeton, NJ

image-derived regular grid edge weights

Riemannian metric spaces (3D) Princeton, NJ

3D bone segmentation (real time screen capture)

Level Sets Graph Cuts

variational optimization method for combinatorial optimization for

Gradient descent method VS. Global minimization tool

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

 Reduction of metrication errors in existing graph cut methods

 Theoretical connection between discrete geometry of graph cuts and

(more examples) Princeton, NJ

You might also like