程序代写代做代考 algorithm The University of

The University of
CS 3335
Visual Computing
Ontario
Boundary & Shape Regularization
(segmentation, reconstruction, video texture,…)
Acknowledgements: some slides from the University of Manchester and Visual Dynamics Group (University of Oxford)
5-1

The University of
CS 3335 Visual Computing
Boundary & Shape Regularization Ontario  Basic boundary/shape regularization objectives
 Intelligent scissors (a.k.a. live-wire)
• contrast weighted graphs • Dijkstra algorithm
Extra Reading: Szeliski, Sec. 5.1.3
 Basic graph cuts
• contrast weighted graphs
• max-flow algorithm
• applications (2D and 3D segmentation, shape reconstruction, texture synthesis, etc)
Extra Reading: Szeliski, Sec. 5.5 Sonka et al., Sec. 7.6
5-2

Intelligent Scissors (a.k.a. live-wire)
Ontario
The University of
[Eric Mortensen, William Barrett, 1995]

Intelligent Scissors
 Approach answers a basic question
• Q: how to find a path from seed to mouse that follows
object boundary as closely as possible?
• A: define a path that stays as close as possible to edges
Ontario
The University of

Intelligent Scissors
 Basic Idea
• find lowest cost path from seed to mouse
Ontario
The University of
on a graph (e.g. N8 pixel grid) weighted by intensity contrast simple example:
Q: How to find such a low cost path?
seed
NOTE: it is common to define weights directly on edges of the graph/grid and use
mouse
some local measure of “contrast” using magnitude of
intensity gradient
cp  25 1 | I p |
“shortest path algorithm” (Dijkstra)

Shortest Path Search (Dijkstra)
Ontario
The University of
 Computes minimum cost path from the seed to all other pixels
(once all paths are pre-computed, each path can be instantly shown as mouse moves around)
Q: How to find such a low cost path?
assume w(p,q)
– edge cost between pixels p and q on 8-neighborhood (N8) graph
Example:
w(p,q)  (cp cq)||q p||
NOTE: diagonal edges are scaled by 2 .
(see next slide)
NOTE: it is common to define weights directly on edges of the graph/grid and use
“shortest path algorithm” (Dijkstra)

Segmentation should be
Invariant to Image Rotation
image gradient scores
The University of
Ontario
After object rotation
2222222
L
2
2 2
2 2
Path’s cost along the top boundary Path’s cost along the top-left boundary 2*714 2*510
After diagonal links are adjusted by 2 2* 2*514

The University of
(see Cormen et.al. “Introduction to Algorithms”, p.595) Dijkstra’s shortest path algorithm
Ontario
3 sets of nodes
• Free
• Active
• Expanded
495 103 323
link cost wpq
1. init node costs (distances) to , set p = seed point, cost(p) = 0
2. expand p as follows:
for each of p’s neighbors q that are not “expanded”
• set cost(q) = min( cost(p) + wpq, cost(q) )
ALGORITHM

Dijkstra’s shortest path algorithm
495
495
1 1 0 3 3 323
323
1. init node costs (distances) to , set p = seed point, cost(p) = 0
2. expand p as follows:
for each of p’s neighbors q that are not “expanded”
• set cost(q) = min( cost(p) + wpq, cost(q) )
– ifq’scostchanged,makeqpointbacktop
• put q on the ACTIVE list (if not already there)
Ontario
The University of
3 sets of nodes
• Free
• Active
• Expanded
ALGORITHM

Dijkstra’s shortest path algorithm
495
325495
2 1 1 0 3 3
343323 323
1. init node costs (distances) to , set p = seed point, cost(p) = 0
2. expand p as follows:
for each of p’s neighbors q that are not “expanded”
• set cost(q) = min( cost(p) + wpq, cost(q) )
– ifq’scostchanged,makeqpointbacktop
• put q on the ACTIVE list (if not already there)
3. set r = node with minimum cost on the ACTIVE list
4. repeat Step 2 for p = r
Ontario
The University of
3 sets of nodes
• Free
• Active
• Expanded
ALGORITHM

The University of
Dijkstra’s shortest path algorithm
4365
325495
3 2 1 1 0 3 3 343323
4323
1. init node costs (distances) to , set p = seed point, cost(p) = 0
2. expand p as follows:
for each of p’s neighbors q that are not “expanded”
• set cost(q) = min( cost(p) + wpq, cost(q) )
– ifq’scostchanged,makeqpointbacktop
• put q on the ACTIVE list (if not already there)
3. set r = node with minimum cost on the ACTIVE list
4. repeat Step 2 for p = r
Ontario
3 sets of nodes
• Free
• Active
• Expanded
ALGORITHM

The University of
Dijkstra’s shortest path algorithm
4365
325495
3 2 1 1 0 3 3 343323
4 3 2 3
1. init node costs (distances) to , set p = seed point, cost(p) = 0
2. expand p as follows:
for each of p’s neighbors q that are not “expanded”
• set cost(q) = min( cost(p) + wpq, cost(q) )
– ifq’scostchanged,makeqpointbacktop
• put q on the ACTIVE list (if not already there)
3. set r = node with minimum cost on the ACTIVE list
4. repeat Step 2 for p = r
Ontario
3 sets of nodes
• Free
• Active
• Expanded
ALGORITHM

The University of
Path Search (basic idea)
Ontario
B
A
– processed nodes (distance to A is known)
– active nodes (front)
– active node with the smallest distance value
Dijkstra algorithm

Dijkstra’s shortest path algorithm  Properties
Ontario
The University of
• It computes the minimum cost path from the seed to every node in the graph. This set of minimum paths is represented as a tree
• Running time, with N pixels:
– O(N2) time if you use an active list
– O(N log N) if you use an active priority queue (heap) with replacement – takes < second for a typical (640x480) image • Once this tree is computed once, we can extract the optimal path from any point to the seed in O(N) time. – it runs in real time as the mouse moves • What happens when the user specifies a new seed? The University of Livewire extensions  Directed graphs  Restricted search space • Restricted domain (e.g. near a priori model) • Restricted backward search  Different edge weight functions • Image-Edgestrength • Image-EdgeCurvature • Proximity to known approximate model/boundary  Multi-resolution processing Ontario The University of Results Ontario http://www.cs.washington.edu/education/courses/455/03wi/projects/project1/artifacts/in d Graph cuts  Shortest paths for segmentation in 2D The University of Ontario Graph Cuts approach Example: find the shortest closed contour in a given domain of a graph Shortest paths approach p Compute the shortest path p ->p for a point p. Repeat for all points on the
gray line. Then choose the optimal contour.
Compute the minimum cut that separates red region from blue region

The University of
Graph cuts for optimal boundary detection simple example [Boykov&Jolly, ICCV’01] Ontario
NOTE: any number of pixels can be “seeds” in this application
(all such pixels should be connected to the corresponding terminals with “prohibitively expensive” t-links)
hard constraint
n-links
a cut
t
Minimum cost cut can be computed in polynomial time
(max-flow/min-cut algorithms)
 ||I I ||2 wpqexpp p 
s
hard constraint

 22  Ipq Ip Iq

Optimal boundary in 2D
Ontario
The University of
“max-flow = min-cut”

Optimal boundary in 3D
Ontario
The University of
3D bone segmentation (real time screen capture)

Optimal boundary in 3D
Ontario
The University of

The University of
Cuts on directed graphs
Ontario
t
Cut on a directed graph
 Cost of a cut includes only edges from the source to the sink components  Cut’s cost (on a directed graph) changes if terminals are swapped
Swapping terminals s and t is similar to switching surface orientation
s

Cuts on directed graphs
Ontario
The University of

The University of
Graph Cuts Basics (see Cormen’s book)
Simple 2D example Ontario
Goal: divide the graph into two parts separating red and blue nodes
s-t graph cut “source” “sink”
ST
A graph with two terminals S and T
• Cut cost is a sum of severed edge weights
• Minimum cost s-t cut can be found in polynomial time

s/t min cut algorithms are widely studied (combinatorial optimization)
Ontario
The University of
 Augmenting paths [Ford & Fulkerson, 1962]  Push-relabel [Goldberg-Tarjan, 1986]

The University of
“Augmenting Paths”
Ontario
 Find a path from S to T along non-saturated edges
 Increase flow along this path until some edge saturates
“source” “sink” ST
A graph with two terminals

The University of
“Augmenting Paths”
Ontario
 Find a path from S to T along non-saturated edges
 Increase flow along this path until some edge saturates
 Find next path…  Increase flow…
“source” “sink” ST
A graph with two terminals

“Augmenting Paths”
Ontario
 Find a path from S to T along non-saturated edges
 Increase flow along this path until some edge saturates
The University of
“source” “sink” ST
Iterate until … all paths from S to T have at
least one saturated edge
A graph with two terminals
MAX FLOWMIN CUT

Graph cuts vs Region Growing
Ontario
The University of
like “region growing”

The University of
Graph cuts vs Region Growing
Ontario
like “region growing”

The University of
Graph cuts vs Region Growing
Ontario
like “region growing”

The University of
Graph cuts vs Region Growing
Ontario
like “region growing”

Graph cuts
Ontario
The University of
iteration 2

The University of
Graph cuts 2
Ontario

The University of
Graph cuts 2
Ontario
Any paths would work, but shorter paths give faster algorithms (in theory and practice)

Graph cuts 3
Ontario
The University of

Graph cuts 3
Ontario
The University of
Finds optimal boundary (least number of holes)
due to Energy minimization

Graph cut is an old standard problem with tons of applications outside vision
The University of
Ontario
From Harris & Ross [1955]
38

Graph cut is an old standard problem with tons of applications outside vision
The University of
Ontario
From Harris & Ross [1955]
39

Applications of
max-flow (min cut) algorithms
 Matrix rounding
 Perfect matching
 Vertex cover
 Routing (airline scheduling)  Baseball elimination
 Economics (circulation–demand problem)  Computer vision
The University of
Ontario

Multi-view volumetric photo-reconstruction
The University of
Ontario
Calibrated images of Lambertian scene
CVPR’05 slides from Vogiatzis, Torr, Cippola
3D model of scene

first pass at multiview reconstruction:
The University of
use silhouettes
=> Visual Hull
Ontario
 Cameras are calibrated
• Each point P in 3D space projects to a
known pixel Xi (P) in i-th camera.
 Assume that each camera knows object’s 2D silhouette
• How can one be obtained?
 Project each camera’s silhouette
into space to obtain a 3D cone.
 Intersection of the cones generated by each image gives the visual hull of the object
• visual hull is the smallest 3D shape consistent with all silhouettes.

The University of
Visual hull of a human face
Ontario
visual hull (from silhouettes)
CVPR’05 slides from Vogiatzis, Torr, Cippola

Can refine visual hull using
photoconsistency
I2(P)
I3(P) I1(P)
(P)  | I (P)  I |2 P i
i
The University of
Ontario
surface of a photo hull
only over cameras i that
“see” voxel P
photo-inconsistency for voxel P
Find surface of
low photo-inconsistency
CVPR’05 slides from Vogiatzis, Torr, Cippola

Estimating visibility
“see” voxel P
(P)  | I (P)  I |2 i
The University of
Ontario
i
P
1. Get nearest point on outer surface
2. Use outer surface for occlusions
2. Discard occluded views
CVPR’05 slides from Vogiatzis, Torr, Cippola
only over cameras i that

Graph cuts applied to multi-view reconstruction
The cost of the cut integrates photoconsistency over the whole space
The University of
Ontario
Source
Sink
CVPR’05 slides from Vogiatzis, Torr, Cippola

Graph cuts applied to multi-view reconstruction
The University of
Ontario
surface of good photoconsistency
visual hull (silhouettes)
CVPR’05 slides from Vogiatzis, Torr, Cippola

texture/features in 3D reconstruction
camera . . camera AB
The University of
Ontario
photoconsistent voxels
unknown true surface
photoconsistent voxels
photoconsistent voxels
photoconsistent voxels
surface reconstruction based on optimizing photoconsistency
3D volume where surface is being reconstructed
(search space)

texture/features in 3D reconstruction
camera . . camera AB
The University of
Ontario
photoconsistent voxels
unknown true surface
photoconsistent voxels
photoconsistent voxels
photoconsistent voxels
surface reconstruction based on optimizing photoconsistency
MORE REALISTIC RESULT BASED ON
DATA NOISE, BLUR, ERRORS IN CAMERA CALIBRATION, AND “SHRINKING BIAS” (more later)
3D volume where surface is being reconstructed
(search space)

The University of
Graph cuts for video textures
Graph-cuts video textures (Kwatra, Schodl, Essa, Bobick 2003)
Ontario
Short video clip
a cut
12
Long video clip
3D generalization of “image-quilting” (Efros & Freeman, 2001)

The University of
Graph cuts for video textures
Graph-cuts video textures (Kwatra, Schodl, Essa, Bobick 2003)
Ontario
original short clip
synthetic infinite texture

Segmentation boundary regularization Summary:
Ontario
The University of
 Methods • live-wire
covered
• graphcuts
• deformable models (snakes)
• geodesicactivecontours
• manymore…
later (in the context of tracking)
 Optimization is not trivial
• graph techniques (Dijkstra, max-flow) covered
• dynamic programming
• gradientdescent
• variationalmethods
later (for snakes, pictorial structures, etc)
5-52

preview:
This topic:
consistent segmentation boundaries
(basic boundary objectives)
Next topic:
consistent appearance of segments
(feature clustering objectives)
Then:
combining appearance & boundary objectives
unsupervised applications => more advanced objectives
Ontario
The University of
5-53