8.2 Image segmentation using deformable models
Examples
Synthetic ellipse Prostate ultrasound image
Boundary is much easier to analyze than a digital image
Prostate ultrasound image courtesy of Ladak, Hanif M., et al. “Prostate boundary segmentation from 2D ultrasound images.” Medical physics 27.8 (2000): 1777-1788.
42
Segmentation methods
• Manual method
– An observer draws the outline of the object using a computer mouse.
– Disadvantage:
• An observer must be skilled in drawing contours in a computer
• For clinical images, an observer needs have expert knowledge about the underlying clinical problem
• Tedious and time-consumingresults in fatigue affects accuracy.
• Difficult to reproduce the outline at a later time (i.e., low degree of reproducibility).
43
Segmentation methods
• Fully automatic
– Different clinical images have different contrast.
– Solutions for specific applications have been proposed but no general solution that works in all cases.
• Manual rough outline, followed by automatic refinement.
– Outline is automatically refined after initial user input.
– Final detected outline is less dependent on initial outline.
– Quicker than manual method.
– Algorithm can be applied to a wider range of image compared to fully automatic methods.
44
Deformable models
• Contours (2D images) or surfaces (3D images) deformed automatically to fit features in an image
• Usually involves some degree of user interaction
– e.g. initialization and sometimes editing
• There are many deformable models. We will focus on the discrete dynamic contour (DDC) model.
45
How does DDC work?
46
How does DDC work?
47
How does DDC work?
48
How does DDC work?
49
2.
Digital image: I(x,y) – x is column direction – y is row direction
DDC components
1. Geometry
–
OrderedsetofverticesVi(i=0, 1, 2, …, n-1) connected by straight line segments
x
–
: Position vector of vertex Vi: described
y
–
Unit edge vector
relative to the origin of the image
I(x,y)
50
DDC components
3. Deformation mechanics
– Once the DDC is initialized, it is deformed automatically.
– Deformation is an iterative process.
– Ateachiterationstept(t=0,1,2,…;t analogous to time), a force is computed for each vertex Vi.
– These forces propel vertices to features in the image while keeping the DDC smooth.
51
DDC components
4. Forces
– Based on Newton’s second law
– Forces on each vertex results in an acceleration
– Acceleration causes each vertex to change velocity and position .
– At the new vertex position, , the contour experiences new forces (we will see why later).
– New acceleration, velocities and positions need to be calculated again.
– Iteration process continues until all vertices come to rest (i.e., ).
52
Algorithm
• Positions,velocitiesandaccelerationsofeach vertex Vi can be updated from time t to time t+Δt using the following algorithm:
– User initializes DDC (i.e., defines )
– The velocity of each vertex is initialized to zero (i.e.,
– Set t = 0 )
– Repeat deformation
• Update position:
• Compute force at each vertex (discussed later)
• Compute acceleration caused by force:
• Update velocity:
• Resample DDC to prevent vertices from getting too far or too close together (discussed later)
• Update time tt+Δt
• Repeat until or maximum number of repetitions reached.
53
Forces
• The force acting on each vertex is a weighted vector sum of 3 other forces:
– – –
external force
• attracts DDC to features such as edges in image
– –
wex: user-selected weight for the external force win: user-selected weight for the internal force
internal force
• keeps the DDC smooth in the presence of image noise
damping force
• keeps the deformation process stable
54
External force
• Essential for driving the vertices towards the edges.
• Edges are characterized by high gradient magnitude.
• External forces are usually defined in terms of an energy term.
• Energy should be defined at each pixel location such that it is locally minimum or maximum at edges, but small at regions with uniform grey levels.
55
External force
•
Anexampleofagradient-basedenergyfunctionis where I is the input image, Gσ is the
• •
NotethatEismaximumatedges.
Gaussian kernel with standard deviation σ, * operation represents the convolution operation.
should follow the direction of maximum ascent of E. Thus, .
Original image
with σ = 5 pixels
56
External force
• We could also choose the energy function as
the inverse of the image gradient:
• Since E is minimum at edges, should follow the direction of maximum descent:
Original image
where C is a constant to prevent division by 0.
57
External force
• Step edge with inverse of image gradient as E
y
Vertex 2
Gσ*I
I
x Vertex 1
E x
x
x
58
External force
• Forces produced by an edge are non-zero over a finite spatial extent orthogonal to the edge. This is called capture range.
• If a vertex on the DDC is within the capture range (Vertex 2), the force will propel vertex towards edge.
• If it is outside the capture range (Vertex 1), the external force will not have an effect.
59
External force
• Gaussian smoothing has two important consequences.
– It reduces noise in the image.
– It affects the “capture range” of an edge. The capture range around an edge becomes larger as σ is increased, but large σ also results in poor edge localization (i.e., edge is thick, not precise).
Original image
σ = 5 pixels σ = 10 pixels
60
Clustering problem
• Theexternalforceacts on a vertex has a component that is tangential to the DDC and one that is radial (i.e., orthogonal to DDC)
• Thetangential component can cause clustering of vertices:
– Over-represent boundaries at a location.
– Waste computational power.
61
•
Thisproblemcanbe eliminated if only the radial component of external force is used to deform the contour. Thus, the external force that is actually applied to the vertex is
•
is the local radial vector at vertex i.
is obtained by rotating by 900 counterclockwise
Solution to clustering problem
62
Internal force
• Image noise in the computation of external forces results in a jagged DDC after deformation
• Anatomical features are typically smooth!
• We can keep the DDC smooth in the presence of noise by applying internal forces
• Local curvature is formally defined as rate of change of tangent of the curve. In discrete contour, it can be estimated by:
63
Internal force
• Sowecoulddefine
to minimize the local
curvature, or could we?
• Problem: this causes a closed curve collapse to a point.
• Solution: Part of the contour with constant curvature will not be changed.
• Implementation would need the “length” of the local curvature at each vertex be defined.
64
Internal force
• It can be proven that ci points to the direction of or in the opposite direction.
• The length of ci along the r-axis is the dot product
, which can be positive or negative.
• We denote this length as len(ci).
65
Internal force
• For regular polygon, len(ci) are constant.
• We can filter out the constant part by:
• Andassign:
len(ci) of different contours
66
Damping force
• With presence of the external and internal forces only, theory indicates that the motion of particles in a dynamic system is oscillatory.
• We add damping force to avoid oscillation, where wd is a small negative number
67
Practical issues
• Initialization: can be a problem in that it introduces some variability into the final outlines.
– Generally, the variability is less than with the manual method
– Attempts made to automatically find a rough outline as an initialization using simple techniques such as thresholding or region growing
– Automation removes user interaction, and therefore variability due to the operator
68
Practical issues
• Parameter selection: many parameters to be selected
– e.g. σ, wex, win, wd, and ldes
– Optimal values can be obtained using a training examples. Once obtained they can be used for all similar images
– mi and Δt are usually set to 1 for all vertices
– Research groups have developed optimization methods to systematically select best parameters
69
Summary
• Definitions
– Deformable model
• Whydeformablemodelispreferredfor segmentation?
• DDCcomponents
– Vertices connected by straight line segments (each vertex with position, velocity acceleration associated with it)
– Deformation mechanics
– Forces: internal, external and damping forces
• DescribehowDDCsolvesthefollowingissues:
– Vertices would be clustered together while deforming by the external forces.
– Regular closed shape would be collapsed to a point.
70