Transcript Recursive connected components algorithm

Chapter 3 cont’d.
Shape Characteristics
Properties of image regions
Area
A
1

 
R
r ,c  R
where R is a region (object/connected component), and
|R| is the cardinality (number of elements) of the set, R
Centroid/Center of Mass
(balance point)
1

1
 r , c     r ,  c 
A
A


 r , c  R 
r
,
c

R

where R is a region (object/connected component)
Variance and standard deviation
from “Numerical Recipes in C.”
Median

“middle value” after we sort the values


Less susceptible to “outliers”


Technical note: When we have an even
number of values, the median is defined as
the average of the middle two values.
alpha-trimmed mean
Order statistic (other than middle is
possible)
What’s the first (sorted value) called?
 What’s the last called?

Median, mean, …

Ex. {1, 7, -5, 12, 2}
Sorted:
 Median:
 Mean (average):
 Standard deviation:

 Built

<-5, 1, 2, 7, 12>
2
3.4
6.4
into Excel as stdev()
Alpha-trimmed mean:
3.3 (average of {1,2,7})
So how can we calculate a region’s
characteristics?

Ex. Region area
A
1

 
R
r ,c  R
where R is a region (object/connected component)
So how can we calculate a region’s
characteristics?
First, implement the region labeling
algorithm.
 Note that the output of region labeling is
assigns a positive integer to each labeled
region.


Use the labeled image as input to the area
calculating algorithm (for example).
Recall the
recursive
connected
components
algorithm
I don’t care for
this format!
Recursive
connected
components
algorithm
//This will negate the labels.
I don’t care for
this format!
Recursive connected
components algorithm
I don’t care for
this format!
Recursive connected
components algorithm
How can we modify
this to determine the
area of a given labeled
region?
I don’t care for
this format!
Recursive
connected
components
algorithm
, label )
// this will negate the labels already assigned
mArea = 0; //to determine area (class var)
(we wish to find the region
labeled with label)
I don’t care for
this format!
Recursive connected
components algorithm
Find the specific region in
which we are interested.
Change –label to +label so we
don’t visit here again later.
I don’t care for
this format!
== -label then
++mArea; //determine area
-label
Perimeter
P4 
 r , c  
R | N 8 r , c   R   
P8 
 r , c  
R |N
4 r , c  
R  
where R is a region (object/connected component)
Perimeter example
…
P4 
 r , c  
R |N
r , c  
8
R  
…
P8 
 r , c  
R |N
4
r , c  
R  
Perimeter
P4  r , c   R | N 8 r , c   R   
P8  r , c   R | N 4 r , c   R   
P4  p  R  q  N 8  p  | q  R (alt defn)
where R is a region (object/connected component)
How can we determine these perimeter sets?
Perimeter
1.
Use boundary tracking algorithm (ex. Gordon
and Udupa).
2.
Use morphological operations (internal
boundaries using either 4- or 8-connected
neighborhoods).

3.
then track the boundary
Modify the recursive connected components
algorithm.

then track the boundary
Length of perimeter
P  k | rk 1 , ck 1   N 4 rk , ck 
 2 k | rk 1 , ck 1   N 8 rk , ck   N 4 rk , ck 
K=length of pixel sequence.
(k+1) is computed modulo k (i.e., (k+1) % k).
|P| is the cardinality of (number of elements in) the set P.
Circularity

C1 is min for digital octagons or diamonds
(depending upon connectivity) but not for
digital circles.
2
P
C1 
A

Therefore, another measure was proposed.
Circularity (Haralick)
R
C2 
R
Note: (rk,ck)  P (perimeter).
So (r-k,c-k) is centroid of perimeter.
where the mean radial distance is:
1
R 
K
K 1
 r , c   r , c 
k 0
k
k
k
k
and its standard deviation is:
1
R  
K

K 1
  r , c   r , c 
k 0
k
k
k
k
2
 R 




1
2
Circularity

For more measures see R.S. Montero, E.
Bribiesca, “State of the art of compactness
and circularity measures,” I. Math. Forum
4, no. 2009:1305-1335.

http://www.m-hikari.com/imfpassword2009/25-28-2009/bribiescaIMF2528-2009.pdf for a comparison of methods.
Bounding “box” (rectangle)
Second moments

Useful for classifying alphabetic characters
in standard orientation.
2nd order spatial moments
Describe shape.
1. Row variation (about a
horizontal axis at the mean):
2. Variation from the centroid:
3. Column variation (about a
vertical at the mean):
All invariant under translation and
scale (but not rotation)!
1
2
r  r 
rr 

A r ,c R
1
r  r c  c 
rc 

A r ,c R
1
2
c  c 
cc 

A r ,c R
Second moment about an arbitrary
axis
Second moment
about an
arbitrary axis
 r ,c , 
1
2
d

A  r ,c R
1
2
V  cos  , sin  

A  r ,c R
1
2
r  r  cos   c  c sin  

A  r ,c R

where    
2
Axis with least second moment
2  rc
tan 2 
 rr   cc

 2  rc 
1

  arctan 
2
  rr   cc 


Useful for determining the orientation of objects
(which can subsequently used to align objects).

Highly symmetric objects (such as circles and
squares) will cause a divide by zero to occur.
Example of calculating axis of least second
moment for a particular object (illustrating its
relationship to object orientation).
col
row
344
275
345
col mean
353.8
row mean
284.0
u_cc
u_rr
u_rc
95.4
81.0
87.9
275
76.9
81.0
78.9
346
275
60.3
81.0
69.9
347
275
45.8
81.0
60.9
348
275
33.3
81.0
51.9
349
275
22.7
81.0
42.9
350
275
14.2
81.0
33.9
351
275
7.7
81.0
24.9
344
276
95.4
64.0
78.1
345
276
76.9
64.0
70.1
346
276
60.3
64.0
62.1
347
276
45.8
64.0
54.1
348
276
33.3
64.0
46.1
349
276
22.7
64.0
38.1
350
276
14.2
64.0
30.1
u_cc mean
u_rr mean
24.1
u_rc mean
28.7
19.6
2u_rc/(u_rr-u_cc)
radians
8.5
0.7
degrees
41.7
375
365
+x
355
345
335
+y
325
315
Excel plot of object
points.
305
295
285
275
275
295
315
335
355
375
col
row
344
275
345
col mean
row mean
353.8
284.0
u_cc
u_rr
u_rc
95.4
81.0
87.9
275
76.9
81.0
78.9
346
275
60.3
81.0
69.9
347
275
45.8
81.0
60.9
348
275
33.3
81.0
51.9
349
275
22.7
81.0
42.9
350
275
14.2
81.0
33.9
351
275
7.7
81.0
24.9
344
276
95.4
64.0
78.1
345
276
76.9
64.0
70.1
346
276
60.3
64.0
62.1
347
276
45.8
64.0
54.1
348
276
33.3
64.0
46.1
349
276
22.7
64.0
38.1
350
276
14.2
64.0
30.1
u_cc mean
u_rr mean
24.1
u_rc mean
28.7
19.6
2u_rc/(u_rr-u_cc)
radians
8.5
0.7
degrees
41.7
375
365
355
345
335
325
315
305
Centroid of object.
295
285
275
275
295
315
335
355
375
col
row
344
275
345
col mean
353.8
row mean
284.0
u_cc
u_rr
u_rc
95.4
81.0
87.9
275
76.9
81.0
78.9
346
275
60.3
81.0
69.9
347
275
45.8
81.0
60.9
348
275
33.3
81.0
51.9
349
275
22.7
81.0
42.9
350
275
14.2
81.0
33.9
351
275
7.7
81.0
24.9
344
276
95.4
64.0
78.1
345
276
76.9
64.0
70.1
346
276
60.3
64.0
62.1
347
276
45.8
64.0
54.1
348
276
33.3
64.0
46.1
349
276
22.7
64.0
38.1
350
276
14.2
64.0
30.1
u_cc mean
u_rr mean
24.1
u_rc mean
28.7
19.6
2u_rc/(u_rr-u_cc)
radians
8.5
0.7
degrees
41.7
375
365
355
345
335
325
315
Angle of axis with least second
moment.
305
295
285
275
275
295
315
335
355
375
Even more region features

Matlab’s Image Processing Toolbox
(http://www.mathworks.com/help/toolbox/i
mages/ref/regionprops.html) provides the
following:

Area, EulerNumber, Orientation,
BoundingBox, Extent, Perimeter, Centroid,
Extrema, PixelIdxList, ConvexArea,
FilledArea, PixelList, ConvexHull, FilledImage,
Solidity, ConvexImage, Image, SubarrayIdx,
Eccentricity, MajorAxisLength, EquivDiameter,
MinorAxisLength