Binary Shape Analysis

Binary shape analysis
Our current focus: geometrical properties of objects in the

image
Last week:
{ Mathematical morphology
z Operators
z Applications
{ image cleaning (dilation, erosion, opening, closing)
{ Binary ‘region growing’ (conditional dilation)
{ Binary template matching (hit-and-miss operator)
{ Shape representations: convex hull, skeleton
This week:
z Shape description and representation
{ Contour-based (Sonka 8.2)
{ Region-based (Sonka 8.3)
Note: the following slides are from the lecture notes of Dr. Morse
(Computer Vision 1) http://morse.cs.byu.edu/650/home/index.php 1
Boundary Description and Representation
Shape Description
I Once you have segmented an image into objects, how do

you describe them?
I Applications:
I Object identification
I Content-based image retrieval
I Object searching/finding/tracking
I Image registration (especially multimodality)
I Often used as inputs to
I matching algorithms
I machine learning algorithms
Shape Description

you describe them?
I Applications:
Shape Description

you describe them?
I Applications:
Shape Description (cont’d)
I Desirable properties:
I Compact representation
I Invariant to as many transformations as possible
(translation, rotation, scale, etc.)
I Useful for matching—
relatively insensitive to small variations
I Approaches:
I Describe the boundary (contour) of the object
I Describe the region occupied by the object (next lecture)
2
Shape Description (cont’d)
I Desirable properties:
(translation, rotation, scale, etc.)
I Useful for matching—
relatively insensitive to small variations
I Approaches:
I Describe the boundary (contour) of the object
I Describe the region occupied by the object (next lecture)
Global Properties
Simple Geometric Descriptors

I Boundary length (perimeter)
I Bending energy
I Basic Idea: How much work do you have to do to bend a
straight line into the shape?
I Calculation: Z 1
κ(s)2 ds
0
where κ(s) is the curvature at point s
I Histograms of geometric properties

I Orientations
I Curvature
I ...
Example of using bending energy for
contour description
3
Chain Codes
Chain Codes and Variations

I Chain code: encode direction around the border between pixels
I Differential chain code: change in direction around the border
(differences between chain code numbers modulo 4 or 8)
I Shape number: differential CCs normalized for starting point–
rotate differential chain code to be as small a number as possible
3 2 1
4 0
5 6 7
Chain 0066002200666446464644222222
Differential 6060202060600602626260600000
Shape No. 0000060602020606006026262606
Data Structures for Image Analysis
Simple Structures
Contour Encoding: Chains

I Encode the border of the region only.
I Only need to encode relative direction around the border.
Chain Codes

3 2 1
4 0
5 6 7
Chain 0066002200666446464644222222
Differential 6060202060600602626260600000
Shape No. 0000060602020606006026262606
Chain Codes

3 2 1
4 0
5 6 7
Chain 0066002200666446464644222222
Differential 6060202060600602626260600000
Shape No. 0000060602020606006026262606
Chain Codes
Chain Codes: Smoothing and Resampling
I Problem:
Pixel grid and noise cause change in chain code
(and its length)
I Approach:
Smooth the shape and/or resample to some fixed number
of points (code length)
Tangential Representations
Tangential Representations: ψ-s curves

I Encodes the tangent angle as a function of arclength
I Similar to differential chain codes, but not limited to grid (average
orientation over small sections of the boundary)
I Sample a fixed number of points around the boundary
!(s)
"
T(s)
!(s)
s
0
s
#"
Radial Representations
Radial Representations: r -s Curves
I Encodes the distance from the center as a function of

arclength
Curvature Representations
Curvature Representations
I Encodes the curvature κ(s) as a function of arclength
I Differentiates the tangent vector (not quite the same as
differentiating the ψ-s curve, but close)
!(s)
!(s)
s
0
s
Other Representations
Signatures
I In general, a signature is a 1-dimensional function
describing a shape (chain code, differential chain code,
ψ-s curve, r -s curve, etc.)
I Here’s another: orthogonal distance d(s) to opposing side
as a function of arclength s
Statistical Representations
Chord Distribution
I Measure length of all chord from one point on the

boundary to another.
I Histogram of lengths: invariant to rotation
I Histogram of angles: invariant to scale
Representation by Significant Points
Points of Extreme Curvature
I Another approach to describing a shape is to decompose it

into parts based on extrema of boundary curvature
I Decompose into parts
→ compare parts
→ build relationship graphs
I Some evidence that this corresponds to human perception
Representation by Significant Points
Convex Hulls
I Build the convex hull of the shape, look at where the shape
touches its convex hull—gives you an idea of the
“extremal” points or sections of the curve.
Fourier-Based Representations
Fourier Descriptors
I Can think of the boundary pixels (xk , yk ) as a curve in the
complex plane:
s(k) = x(k) + iy(k )
Fourier Descriptors (cont’d)

I A Fourier descriptor is the Fourier Transform of the
complex-valued boundary curve:
a(ν) = F (s(k ))
I Relatively insensitive to transformations:
I Most of the time, just

I use the magnitude (invariant to start point)
I ignore the zero-frequency term (invariant to translation)
I normalize sum (invariant to overall size)
Why Fourier Descriptors?
I Separates
I low-frequency components of shape (general properties)
I high-frequency ones (detail, small perturbations)
I Can filter shape!
I Low-pass filtering the Fourier descriptor smooths the shape
I Separates
I low-frequency components of shape (general properties)
I high-frequency ones (detail, small perturbations)
I Can filter shape!
I Low-pass filtering the Fourier descriptor smooths the shape

Computer-aided diagnosis: Comparing two
contours
Circumscribed (benign) Spiculated lesions in

lesions in digital (digital mammography)
mammography
The feature of interest: regularity of contour

-The circumscribed shape will have its Fourier coefficients at lower
frequencies than the spiculated shape
Alexandra Branzan Albu ELEC 310-Spring 2008-Lecture 9 11

Alexandra Branzan Albu ELEC 310-Spring 2008-Lecture 9 10
Affine and Projective Invariants
Summary
I There are lots of ways to try to describe/quantify the shape

of an object from points on the boundary
I Remember the objectives:
(translation, rotation, scale, projection, etc.)
I Relatively insensitive to small variations
Affine and Projective Invariants
Summary
I There are lots of ways to try to describe/quantify the shape

of an object from points on the boundary
I Remember the objectives:
(translation, rotation, scale, projection, etc.)
I Relatively insensitive to small variations
Example of using contour descriptors
Reading:
z ELEC 536
{ Jeong and Radke, “Reslicing axially sampled 3D
shapes using elliptic Fourier descriptors”,
Medical Image Analysis 2007
Main idea:
{ Contour-based interpolation
{ Interpolation between parallel slices from a
3D shape is necessary for reslicing and
putting into correspondence organ shapes
acquired from volumetric medical imagery
1
Rationale
2
Interpolation using Elliptic Fourier
descriptors
{ The main goal of the elliptical Fourier

analysis is to approximate a closed contour
as the sum of elliptical harmonics.
3
Contour Interpolation via EFD
descriptors
{ Input: 2 or more contour images
{ Convert each contour to EFDs
{ Assign a z-value to each contour (frame #, or distance

between MRI slices)
{ Choose z-value(s) at which to interpolate
{ Use bicubic interpolation for EFDs at those values of z
{ Convert interpolated EFDs back into x,y contour

images
4
Experimental validation
5
Disadvantages
EFD algorithm does not account for

cases where multiple contours are
present in the same image

Binary Shape Analysis

Uploaded by

Copyright:

Available Formats

Binary Shape Analysis

Uploaded by

Document Information

Original Description:

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

Binary Shape Analysis

Uploaded by

Copyright:

Available Formats

Binary shape analysis

Our current focus: geometrical properties of objects in the

I Once you have segmented an image into objects, how do

I Once you have segmented an image into objects, how do

I Once you have segmented an image into objects, how do

Shape Description (cont’d)

Shape Description (cont’d)

Simple Geometric Descriptors

where κ(s) is the curvature at point s

I Histograms of geometric properties

Chain Codes and Variations

Contour Encoding: Chains

Chain Codes and Variations

Chain Codes and Variations

Chain Codes: Smoothing and Resampling

Tangential Representations: ψ-s curves

Radial Representations: r -s Curves

I Encodes the distance from the center as a function of

I Measure length of all chord from one point on the

Points of Extreme Curvature

I Another approach to describing a shape is to decompose it

Fourier Descriptors (cont’d)

I Relatively insensitive to transformations:

I Most of the time, just

Why Fourier Descriptors?

Why Fourier Descriptors?

Why Fourier Descriptors?

Circumscribed (benign) Spiculated lesions in

The feature of interest: regularity of contour

Alexandra Branzan Albu ELEC 310-Spring 2008-Lecture 9 11

I There are lots of ways to try to describe/quantify the shape

I There are lots of ways to try to describe/quantify the shape

{ The main goal of the elliptical Fourier

{ Convert each contour to EFDs

{ Assign a z-value to each contour (frame #, or distance

{ Choose z-value(s) at which to interpolate

{ Use bicubic interpolation for EFDs at those values of z

{ Convert interpolated EFDs back into x,y contour

EFD algorithm does not account for

You might also like