Advanced Methods for Image

Segmentation

Ilya Pollak
Purdue University

November 10, 2008

 Outline
• Image segmentation examples
• Different classes of image segmentation methods
• Methods based on scale-spaces:
– Linear Gaussian scale-space
– Perona-Malik equation
– Stabilized inverse diffusion equation (SIDE)
• Vector-valued SIDEs
• Applications to Digital Microscopy Data
Segmentation of a Freckle Defect in
Single Crystal Nickel Images

freckle021 freckle055

freckle059 freckle108
Segmentation of Dermatoscopic
Images of Skin Lesions
 Segmentation of a SAR Image

Original Method 1 Method 2

 Document Image Segmentation

Document and its segmentation Classification of regions

 Activation Detection in Functional
MRI

Left hemifield stimulus Right hemifield stimulus

 References
• L. Huffman, J. Simmons and I. Pollak. Segmentation of digital microscopy data for
the analysis of defect structures in materials using nonlinear diffusions. Presented
at the Conference on Computational Imaging, IS&T/SPIE 20th Annual Symposium
on Electronic Imaging Science and Technology, January 27-31, 2008, San Jose,
CA. In Computational Imaging VI, Proceedings of SPIE, C.A. Bouman, E.L.
Miller, and I. Pollak, Eds.
• X. Dong and I. Pollak. Multiscale Segmentation with Vector-Valued Nonlinear
Diffusions on Arbitrary Graphs. IEEE Trans. Im. Proc., 15(7):1993-2005, July
2006.
• M.G. Fleming, C. Steger, J. Zhang, J. Gao, A.B. Cognetta, I. Pollak and C.R. Dyer.
Techniques for a structural analysis of dermatoscopic imagery. Computerized
Medical Imaging and Graphics, 22(5):375-389, 1998.
• I. Pollak, A.S. Willsky and H. Krim. Image segmentation and edge enhancement
with stabilized inverse diffusion equations. IEEE Trans. Im. Proc., 9(2):256-266,
Feb 2000.
• W. Wang, I. Pollak, T.-S. Wong, C.A. Bouman, M.P. Harper and J.M. Siskind.
Hierarchical stochastic image grammars for classification and segmentation. IEEE
Trans. Im. Proc., 15(10):3033-3052, October 2006.
• J. Wei, T. Talavage and I. Pollak. Modeling and activation detection in fMRI data
analysis. In Proc. IEEE Statistical Signal Processing Workshop, pp. 141-145,
August 26-29, 2007, Madison, WI.
 Some Classes of Segmentation
Methods
• Bayesian classification (C. Bouman, Tue AM):
– Construct a prior model for each pixel class, estimate pixel classes from the
observed data
• Active contours (S. Acton, J. Kovačević, Tue AM):
– Throw several curves onto the image and let them evolve towards objects of
interest by minimizing an energy
• Graph-based methods (S. Wang, Tue AM):
– E.g., compute an optimal graph cut
• Variational methods (C. Bajaj, Tue PM):
– Set up and solve a global variational problem (e.g. Mumford-Shah)
• Region merging:
– Recursively merge regions to reduce an energy
• Multiscale methods:
– Repeatedly coarsen with “low-pass” filters, segment coarsened versions
To simplify, consider 1D segmentation first

Take the first row of pixels and plot

their intensities as a function of position:
Noise Removal with a Linear
Gaussian Scale-Space

* =

* =

* =
 Linear Gaussian Scale-Space and
Heat Equation
2t
* = u (t , x),
where

ut (t , x)  u xx (t , x) Heat equation

u (0, x) 
 1D Example
ut  u xx
 2D Example
ut  uxx  uyy

Fine scale Coarse scale

 Perona-Malik Equation

ut  F(ux )
x
• Edge sharpening for ux  K
• Ill-posed, ut  F (ux )uxx
• Semi-discrete and discrete versions are well-posed:

u n (t )  F (un 1 (t )  un (t ))  F (un (t )  un 1 (t ))
 i1
un  uni  t  (F(uni 1  uni )  F (uni  un1 i
))
 Semi-Discrete Perona-Malik
Equation
We focus on the semi-discrete equation, which is a system of ODE’s:

u n (t )  F (un 1 (t )  un (t ))  F (un (t )  un 1 (t )) for n=1,…,N

u(0)  u  u ,u ,,u
0 0
1
0
2 N 
0 T

 2D Example
Large K

Small K
 Stabilized Inverse Diffusion Equations
(SIDE’s) F(u  u ) n 1 n

• Pollak, Willsky, Krim, Trans. Image Proc., Feb. 2000.

• The limit of Perona-Malik as K approaches zero. un 1  un

• Semi-discrete version is well-posed. uk 1  uk un 1  un
– Sliding modes on the surfaces u : un 1  un  
– I.e., if un 1( )  un ( ) then un 1 (t)  un (t) for t  
• Scale-space consists of piecewise-
  
constant signals.

– Will converge to a constant within finite time.
Another 1D Example
 SIDEs (continued)
• The solution automatically produces fine-to-coarse sequence of segmentations.
• This process is a multiscale region merging algorithm which starts with
singleton regions.
• Sliding mode dynamics for the i-th region of length Li and intensity i :
1
 i (t )   F ( i 1 (t )  i (t ))  F ( i (t )  i 1 (t ))
Li
• In 2D,  
1
 i (t ) 
Ai
 F (
jnbrs ( i )
j (t )  i (t ))bij

– where Ai is the number of pixels in region i, and

bij is the length of the boundary between regionsi and j.


 2D Example

1000 regions 100 regions 2 regions

2D Examples
 Segmentation of Vector-Valued
Images: Motivation
How to segment an image composed of several textures
whose average intensities may not be very different?

One possible answer: convert it into several “feature” images

which associate different intensities with different textures
 Scalar-Valued Image Vector-Valued
Image
Filter 1

Filter 2

Filter N

Original image Filter bank Vector-valued

feature image
Example: Gabor Energy Features

• Useful for analyzing textures at different

scales, frequencies, orientations
• Filter an image with Gabor filter pairs at
many scales, frequencies, orientations
• For each Gabor filter pair, take the energy
image
Gabor Energy Features
 SIDE as a Gradient Descent
S  R1,,RI   a partition of the image domain into I regions
US  all piecewise - constant images with this partition


= + +
 SIDE as a Gradient Descent
S  R1,,RI   a partition of the image domain into I regions
US  all piecewise - constant images with this partition


Observation : 2D SIDE is
u  E
where the gradient is taken in the current U S
and where E (u)   E(
i , j nbrs
j  i )b ij

F(v) E(v)

v v
€ €
 From Scalar-Valued to Vector-Valued
SIDEs

• Define an inner product between feature (or color) vectors.

• Define an inner product between two vector-valued images
in U S
• Perform recursive region merging, with gradient descent
r r
on E (u) = ∑ ( j i ) bij between merges.
E μ − μ
i, j nbrs

€
 Vector-Valued SIDE
 
 1  j  i  
i  
a( Ri ) R j NBRS ( Ri )
b( Ri , R j )   E ' (||  j  i ||)
||  j  i ||


– i is the vector intensity of region Ri at scale t
– a(Ri) is an application-specific positive weight function,
e.g., the area of region Ri
– b(Ri,Rj) is an application-specific positive weight
function which relates neighboring regions Ri and Rj,
e.g., the length of the boundary between Ri and Rj
– E(x) is the energy function, e.g., E  x   x
• This choice of E(x) pushes intensities μ of neighboring regions
to equality, therefore encouraging a coarse segmentation
Multiscale Segmentation Algorithm

1. Given a segmentation S of image u, evolve

the descent equation until the intensities of
some pair of neighbor regions are equal.
2. Merge the two regions by removing them
both from S and adding their union to S.
3. If the desired number of regions is reached,
stop. Else, go to Step 1.
Texture Segmentation Example
Texture Segmentation Example
Another Example
Segmentation of a Natural Image
Segmentation of a Freckle Defect in Single
Crystal Nickel Images

freckle021 freckle055

freckle059 freckle108
Multi-Tilt Segmentations
Combining segmentations from
multiple images

+ + +

=
 Segmentation Fusion

1. Locate landmarks visible in every image

2. Register images using landmarks
3. Combine SIDE segmentations of each
image to create a composite segmentation
 Carbides as Landmarks
• Carbides appear as dark spots in the material
visible at most of the tilt angles. These are used as
landmarks.

Some visible
carbides
 Landmark Detection

• Carbides detected by thresholding the intensity of pixels in

regions where less than 1% of pixels are above threshold

Carbide pixel
extraction
 Image Registration

Unaligned segmentation Aligned through 2D Aligned by affine-

boundaries (4001 in red, correlation transforming 7001 to match
7001 in green) 4001
 Segmentation Fusion
• Directly overlaying segmentations from multiple tilts produces
many new “regions” due to slight differences in SIDE outputs
on different images.

Zoom in on shared
Overlaid boundaries of 4001 region borders
and transformed 7001
 Removing Small Extraneous Regions

• Assign a unique region label to every region in the original

individual segmentations.
• Each region in the combined segmentation then has two
original region labels from the original segmentations.
• The overlap of Region A from
image 1 with Region B from
image 2 may produce multiple
new contiguous regions.

New region labels

indicated by color
 Removing Small Extraneous Regions
• New regions are defined as “extraneous” if they make up less
than ε% of both of the original regions the pixels belonged to.
• Extraneous regions are then combined with the neighboring
region that shares one of the same original region labels and
contains the most pixels from that original region.

Zoom of original overlay Zoom of overlay labeling

Direct overlay contains 1960 regions Removing extraneous regions
labeling after extraneous region
results in 426 regions total
removal
 Segmentation Fusion for Four Tilts
Merged 4001-5001-
4001 regions Merged 4001-5001
6001 regions
regions
Merged 4001-5001-
6001-7001 regions

Transformed Transformed Transformed

5001 regions 6001 regions 7001 regions
 Segmentations and Images

4001 portion 5001 portion

Combined region
boundaries

6001 portion 7001 portion

 Summary
• SIDE is a flexible, robust segmentation
method
• Once parameters are selected, no human
interaction
• Can work in conjunction with any feature
extraction method and any image
registration/fusion method
• Has been successfully applied to natural
images, medical images, and microscopy
images of materials
 Acknowledgments
• Jeff Simmons of AFRL
• Data: Michael Uchic and Jonathan Spowart of
AFRL
• Past Funding: AFRL, Wright-Patterson AFB
(Dr. Dallis Hardwick, program manager) under
subcontract USAF-5212-STI-SC-0026 from
GeneralDynamics Information Technology, Inc.
(May-Nov 2007)
• Future Funding: ??????
 Future Work
• Improvements to multi-tilt fusion
• Joint 3D/4D segmentation
• Applications to other images of materials
• Investigation of feature extraction methods
• Parameter learning
• Prior modeling: designing penalty functions a and
b and energy function E
• Theoretical analysis:
– Total-variation minimization for u0 = x + w
– Inverse problems: u0 = Ax + w
– Non-Gaussian noise