Transcript Region Processing

Recap
CSC508
1
Low Level Vision
• Input
– Image sensor data
• Processing
– Neighborhood operators
– Mathematical operators
– Local contextual operators
• Output
– Pixel based features
CSC508
2
Mid Level Vision
• Input
– Pixel based features
• Processing
– Statistical operators
– Mathematical operators
– Global contextual operators
• Output
– Objects
CSC508
3
Mid-Level Vision
CSC508
4
Intensity Region Segmentation
CSC508
5
Homogeneous Intensity Regions
• Areas of constant intensity within the image
• May represent
– Objects
– Regions of interest
• Computed by [one method among many]
– Binarization
– Connected component analysis
CSC508
6
Binarization (revisited)
Original Gray Level Image
Binary Image
CSC508
7
Binarization (revisited)
CSC508
8
Region Formation
1
2
3
Original Gray Level Image
4
Marked Region Image
CSC508
9
Boundary Information
Original Gray Level Image
Region Boundary Image
CSC508
10
Finding Regions via
Connected Component Analysis
• In the input image the intensity of each region
may be arbitrary
• In the binarized image the intensity of each
region is 255 (maximum, or at least different
from the background)
• The goal of connected component analysis is
to “label” the pixels of each connected region
with a value unique to that region
CSC508
11
Connected Component Analysis
• A simple recursive “flood-fill” algorithm will
do the trick but…
– It is slow
– A large object will overflow the stack (memory
intensive)
• Smarter algorithms can be found in the
computer graphics, graph theory, and image
processing literature
CSC508
12
Connected Component Analysis
• One algorithm works as follows:
– Pass 1:
• Assign labels to each object pixel
• Keep track of neighboring labels that belong to the same object
– Pass 2:
• Rectify associations
• Pass 2 is somewhat complex and comes from a
language parsing algorithm – I won’t describe the
details here
CSC508
13
Connected Component Analysis
1
2
3
Original Gray Level Image
4
Marked Region Image
CSC508
14
Connected Component Analysis
• Note that this image is “ideal”
– You might expect images as such in a
manufacturing environment
• In less than ideal cases objects may get broken
up or merged by thin lines, etc.
– Correction can be made through the use of
Morphological operators
• Erosion
• Dilation
– More on Morphological operators next week
CSC508
15
Boundary Extraction
• Once you have identified regions it is [conceptually]
simple to extract their boundaries
– Find the upper-left most pixel of the region
– “Walk around” the region always keeping it to your right
– Keep track of the directions you step along the way (north,
south, east, or west)
– Stop when you return back to the beginning
• This creates a chain-code of the region boundary
• From the chain-code you can compute the perimeter
length and other descriptors
CSC508
16
Boundary Chain-Code
NEEE
*
S E
N
S
N E E/W
EN
S
N S E WS
N
S
N
WS
WWWW S
• “*” marks the starting point
(upper-left most pixel of the
region)
• Resultant chain-code is
NEEESESSSWSSWSWW
WWNNNNEESENWN
• Resultant perimeter is 30
CSC508
17
Region Description
CSC508
18
Object Description
• Now that we have identified objects we need a
way to describe them that will facilitate
recognition
CSC508
19
Moments
• A set of descriptors for representing the shape
of an object
• Typically applied to an identified region but
may be used with gray-level
CSC508
20
Discrete Case
• Moment of an region (general definition)
mpq  i
i
p
j
q
f i, j 
f i, j 
j
0 if not in region
 1 if in region
• Central moments

pq
 
i
j
m
x
m
10
00
i  x  j  y 
q
p
m
,y
m
01
00
f i, j 
(Object centroid)
CSC508
21
Central Moments
• First few central moments:
 m
  0
  m   xy
  m m x
  m m y
00
00
10
01
11
11
20
20
10
02
02
01
00
CSC508
22
Moment Features
• Centroids (average x and y locations)
x
m
m
10
00
,y
m
m
01
00
• Principle axis orientation
 2.0  


11
  0.5 * arctan 

 

20
02 

CSC508
23
Convex Hull
• Another useful shape descriptor
• The smallest convex border encasing the
object
– Think of stretching a rubber band around the
outside of the object and letting it wrap around it
– This will be the convex hull
• Input to the algorithm is a set of points
– These are the boundary points found previously
CSC508
24
Region Descriptors
• Region: 1
–
–
–
–
–
Area: 27753.0
xBar: 171.26
yBar: 131.89
theta: -32.87
perimeter: 1098
• Convex Hull
– Perimeter: 812
CSC508
25
Region Descriptors
• Region: 2
–
–
–
–
–
Area: 10390.0
xBar: 230.82
yBar: 252.99
theta: 87.51
perimeter: 580
• Convex Hull
– perimeter: 515
CSC508
26
Region Descriptors
• Region: 3
–
–
–
–
–
Area: 8049.0
xBar: 362.24
yBar: 223.76
theta: -6.62
perimeter: 411
• Convex Hull
– perimeter: 322
CSC508
27
Region Descriptors
• Region: 4
–
–
–
–
–
Area: 11203.0
xBar: 357.98
yBar: 378.14
theta: -27.80
perimeter: 648
• Convex Hull
– perimeter: 520
CSC508
28
Region Descriptors
• Region: 5
–
–
–
–
–
Area: 14880.0
xBar: 92.5
yBar: 366.5
theta: 0.0
perimeter: 492
• Convex Hull
– perimeter: 484
CSC508
29
Other Features
• Average Intensity
• Circularity or Compactness
p
2
p: perimeter, a: area
a
CSC508
30
Things To Do
• Reading for Next (few) Week(s)
– Chapter 14 – Segmentation by Clustering
• We’ll consider various clustering methods
– Chapter 15 – Segmentation by Models
• We’ll analyze the Hough Transform
CSC508
31
Things To Do
•
Homework
–
Convex Hull
•
•
•
–
Boundary Extraction
•
•
•
–
Code the μ00, μ10, μ01, μ11, μ20, μ02 moments
Test the code
You may write in any programming language you choose
Deliverables:
–
–
•
Write the code to trace the boundary (chain code) of a specified region
Print out the chain code symbols (start pixel row, column followed by a sequence of N E W S directions)
Test the code
Moments
•
•
•
•
Find an algorithm for computing the convex hull of a set of points
Describe the algorithm in words
Test the code
Zipped images in email
Email the source code to [email protected] with the subject line
CSC508 PROGRAM 3
Due beginning of class in two weeks
–
–
(late assignments will be penalized 10%)
I will post test images
CSC508
32