Connected

 Components  
  Basic  defini2ons  
  Connec2vity,  Adjacency,  Connected  Components  
  Background/Foreground,  Boundaries,  Morphological  opera2ons  
  Run-­‐length  encoding  
  Component  Labeling  
  Recursive  algorithm  
  Two-­‐scan  algorithm  
  Chain  Codes  
  Integral  Images  
  Histograms  
  Gray  and  Color  Histograms  
  Edge  Histograms  
  Proper2es  
Connected  components  -­‐  1   Many slides from Larry David
 4(8)  Connec2vity  
  Defini2on:    Given  a  pixel  (i,j)  its  4-­‐
neighbors  are  the  points  (i’,j’)  such  
that  |i-­‐i’|  +  |j-­‐j’|  =  1  
  the  4-­‐neighbors  are  (i±i,  j)  and  (i,j±1)  
  Defini2on:  Given  a  pixel  (i,j)  its  8-­‐
neighbors  are  the  points  (i’,j’)  such  
that  max(|i-­‐i’|,|j-­‐j’|)  =  1  
  the  8-­‐  neighbors  are  (i,  j±1),  (i±1,  j)  and  
(i±1,  j±1)  

Connected  components  -­‐  2  

 Adjacency  
  Defini2on:    Given  two  disjoint  sets  of  pixels,  A  and  B,  A  is  
4-­‐(8)  adjacent  to  B  is  there  is  a  pixel  in  A  that  is  a  4-­‐(8)  
neighbor  of  a  pixel  in  B  

Connected  components  -­‐  3  

 Connected  components  
  Defini2on:  A  4-­‐(8)path  from  pixel  (i0,j0)  to  (in,jn)  is  a  
sequence  of  pixels  (i0,j0)  (i1,j1)  (i2,j2)  ,  ...  (in,jn)  such  that  (ik,  
jk)  is  a  4-­‐(8)  neighbor  of  (ik+1,  jk+1),  for  k  =  0,  ...,  n-­‐1  

(i0,j0) (i0,j0)

(in, jn) (in, jn)

Every 4-path is an 8-path!

Connected  components  -­‐  4  

 Connected  components  
  Defini2on:  Given  a  binary  image,  B,  the  set  of  all  1’s  is  called  
the  foreground  and  is  denoted  by  S  
  Defini2on:  Given  a  pixel  p  in  S,  p  is  4-­‐(8)  connected  to  q  in  S  if  
there  is  a  path  from  p  to  q  consis2ng  only  of  points  from  S.  
  The  rela2on  “is-­‐connected-­‐to”  is  an  equivalence  rela2on  
  Reflexive  -­‐  p  is  connected  to  itself  by  a  path  of  length  0  
  Symmetric  -­‐  if  p  is  connected  to  q,  then  q  is  connected  to  p  by  the  
reverse  path  
  Transi2ve  -­‐  if  p  is  connected  to  q  and  q  is  connected  to  r,  then  p  is  
connected  to  r  by  concatena2on  of  the  paths  from  p  to  q  and  q  to  r  

Connected  components  -­‐  5  

 Connected  components  
  Since  the  “is-­‐connected-­‐to”  rela2on  is  an  equivalence  rela2on,  it  
par22ons  the  set  S  into  a  set  of  equivalence  classes  or  components  
  these  are  called  connected  components  
  Defini2on:    S is  the  complement  of  S  -­‐  it  is  the  set  of  all  pixels  in  B  
whose  value  is  0  
  S    can  also  be  par22oned  into  a  set  of  connected  components  
  Regard  the  image  as  being  surrounded  by  a  frame  of  0’s  
  The  component(s)  of S that  are  adjacent  to  this  frame  is  called  
the  background  of  B.  
  All  other  components  of  S  are  called  holes  

Connected  components  -­‐  6  

 Examples  -­‐  Black  =  1,  Green  =  0  

How many 4-(8) components of S?

What is the background?
Which are the 4-(8) holes?

Connected  components  -­‐  7  

 Background  and  foreground  
connec2vity  
  Use  opposite  connec2vity  for  the  foreground  and  the  background  
  4-­‐foreground,  8-­‐background:  4  single  pixel  objects  and  no  holes  
  4-­‐background,  8-­‐foreground:  one  4  pixel  object  containing  a  1  
pixel  hole  

Connected  components  -­‐  8  

 Boundaries  
  The  boundary  of  S  is  the  set  of  all  pixels  of  S  that  have  4-­‐
neighbors  in  S.    The  boundary  set  is  denoted  as  S’.    
  The  interior  is  the  set  of  pixels  of  S  that  are  not  in  its  
boundary:  S-­‐S’  
  Defini2on:  Region  T  surrounds  region  R  (or  R  is  inside  T)  if  
any  4-­‐path  from  any  point  of  R  to  the  background  
intersects  T  
  Theorem:    If  R  and  T  are  two  adjacent  components,  then  
either  R  surrounds  T  or  T  surrounds  R.  

Connected  components  -­‐  9  

 Examples  
A A A

A
B
A A B
A

B B
A

Even levels are components of 0’s

The background is at level 0
Odd levels are components of 1’s

Connected  components  -­‐  10  

 Morphological  Opera2ons  
  Parallel  opera2ons  –  cannot  be  done  in  place  
  Erosion  
  In  binary  images:  replace  the  boundary  by  the  background  
pixels  
  In  gray  level  images:  replace  the  pixel  value  by  the  min  
value  of  its  neighbors    
  Dila2on  
  In  binary  images  grows  a  region  by  replacing  background  
4(8)  neighbors  of  all  foreground  pixels  by  foreground  
  In  gray  level  images:  replace  each  pixel  value  by  the  max  
value  of  its  neighbors  

Connected  components  -­‐  11  

 Run-­‐length  Encoding  
Used  mainly  to  represent  binary  images  such  as  faxes.  
Various  approaches  exist,  this  approach  represents  only  foreground.    

Foreground  is  a  list  of  lists.  

Each  non-­‐zero  row  is  represented  by  
a  list.  
(r  b1e1  b2e2…)  where  r  is  the  row  and  
biei  are  the  beginning  and  ending  
column  indices  for  a  foreground  run  
 
((11144)(214)(52355))  

Connected  components  -­‐  12  

 Component  labeling  

  Given:    Binary  image  B  

  Produce:  An  image  in  which  all  of  the  pixels  in  each  
connected  component  are  given  a  unique  label.  
  Solu2on  1:    Recursive,  depth  first  labeling  
  Scan  the  binary  image  from  top  to  bojom,  lek  to  right  un2l  
encountering  a  1  (0).  
  Change  that  pixel  to  the  next  unused  component  label  
  Recursively  visit  all  (8,4)  neighbors  of  this  pixel  that  are  1’s  
(0’s)  and  mark  them  with  the  new  label  

Connected  components  -­‐  13  

Example  

Connected  components  -­‐  14  

 Recursive  Algorithm  
1.  Create  stack  S,  ini2ally  empty  
2.  Scan  the  binary  image  from  top  to  bojom,  lek  to  right  un2l  
encountering  a  1  (0).  
3.  Change  that  pixel’s  label  to  the  next  unused  component  label  
4.  Push  the  pixel  on  S  (push  the  coordinates)  
5.  While  S  is  not  empty  
Pop  a  pixel  p  from  S  
For  each  unlabeled  neighbor  of  p  if  it’s  value  is  1(0)    
 label  it  with  the  current  label  
 push  it  on  S  
 

Connected  components  -­‐  15  

 Topology  Challenge  
  How  to  determine  which  components  of  0’s  are  holes  in  
which  components  of  1’s    

  Scan  labeled  image:  

  When  a  new  label  is  encountered  make  it  the  child  of  the  
label  on  the  lek  

Connected  components  -­‐  16  

 Solu2on  2  -­‐  row  scanning  up  and  down  
  Start  at  the  top  row  of  the  image  
  par22on  that  row  into  runs  of  0’s  and  1’s  
  each  run  of  0’s  is  part  of  the  background,  and  is  given  the  special  
background  label  
  each  run  of  1’s  is  given  a  unique  component  label  
  For  all  subsequent  rows  
  par22on  into  runs  
  if  a  run  of  1’s  (0’s)  has  no  run  of  1’s(0’s)  directly  above  it,  then  it  is  
poten2ally  a  new  component  and  is  given  a  new  label  
  if  a  run  of  1’s  (0’s)  overlaps  one  or  more  runs  on  the  previous  row  
give  it  the  minimum  label  of  those  runs  
  Let  a    be  that  minimal  label  and  let  {ci}  be  the  labels  of  all  other  
adjacent  runs  in  previous  row.    Relabel  all  runs  on  previous  row  
having  labels  in  {ci}  with  a  

Connected  components  -­‐  17  

 Local  relabeling  
  What  is  the  point  of  the  last  step?  
  We  want  the  following  invariant  condi2on  to  hold  aker  
each  row  of  the  image  is  processed  on  the  downward  scan:  
The  label  assigned  to  the  runs  in  the  last  row  processed  in  
any  connected  component  is  the  minimum  label  of  any  run  
belonging  to  that  component  in  the  previous  rows.  
  Note  that  this  only  applies  to  the  connec2vity  of  pixels  in  
that  part  of  B  already  processed.    There  may  be  subsequent  
merging  of  components  in  later  rows  

Connected  components  -­‐  18  

 Example  
a a B b B B B B a a B b/a B B B B
a a a a B c c c

a a B a B B B B a a B a B B B B a a B a B B B B
a a a a B c/a c/a c/a a a a a B a a a a a a a B a a a
B a a a a a C a B a a a a a C a B a a a a a C a
a a a a D a a a a a a a D/B a a a
a a a a B B B B

If  we  did  not  change  the  c’s  to  a’s,  then  the  rightmost  a  will  be  labeled  as  a  c  and  our  
invariant  condi2on  will  fail.  
Connected  components  -­‐  19  
 Upward  scan  
  A  bojom  to  top  scan  will  assign  a  unique  label  to  each  
component  
  we  can  also  compute  simple  proper2es  of  the  components  
during  this  scan  
  Start  at  the  bojom  row  
  create  a  table  entry  for  each  unique  component  label,  plus  
one  entry  for  the  background  if  there  are  no  background  
runs  on  the  last  row  
  Mark  each  component  of  1’s  as  being  “inside”  the  
background  

Connected  components  -­‐  20  

 Upward  scan  
  For  all  subsequent  rows  
  if  a  run  of  1’s  (0’s)  (say  with  label  c)  is  adjacent  to  no  run  of  1’s  
(0’s)  on  the  subsequent  row,  and  its  label  is  not  in  the  table,  and  no  
other  run  with  label  c  on  the  current  row  is  adjacent  to  any  run  of  
1’s  on  the  subsequent  row,  then:  
  create  a  table  entry  for  this  label  

  mark  it  as  inside  the  run  of  0’s  (1’s)  that  it  is  adjacent  to  on  the  
subsequent  row  
  property  values  such  as  area,  perimeter,  etc.  can  be  updated  as  
each  run  is  processed.  
  if  a  run  of  1’s  (0’s)  (say,  with  label  c)  is  adjacent  to  one  or  more  run  
of  1’s  on  the  subsequent  row,  then  it  is  marked  with  the  common  
label  of  those  runs,  and  the  table  proper2es  are  updated.      
  All  other  runs  of  “c’s”  on  the  current  row  are  also  given  the  
common  label.  

Connected  components  -­‐  21  

 Example  
-------aaa
ccc---aaa
c-c---aaa
c-c---aaa
---c--aaa
aaaaaaaa

•  changed  to  a  during  first  pass  

•  but  c’s  in  first  column  will  not  
be  changed  to  a’s  on  the  upward  pass  
unless  all  runs  are  once  equivalence  is    
detected  
 

Connected  components  -­‐  22  

Example   process row 3
a a B b B B B B a a B b B B B B
B
a a a a B c c c a a a a B c c c
B a a a a a C a B a a a a a C a
a a a a D a a a a a a a B a a a a d
a a a a B B B B a a a a B B B B
a a a a B d d d a a a a B d d d
B a a a B d d d B a a a B d d d C
B a a a B d d d B a a a B d d d
process row
a a B b B B B B 4 a a B a B B B B
a a a a B c c c a a a a B a a a process row
B a a a a a C a B a a a a a C a 2, then 1
a a a a B a a a a a a a B a a a
a a a a B B B B a a a a B B B B
a a a a B d d d a a a a B d d d
B a a a B d d d B a a a B d d d
B a a a B d d d B a a a B d d d

Connected  components  -­‐  23  

 Chain  Codes  
Used  for  efficient  boundary  representa2on.  First  (reference)  pixel    
is  recorded.    
All  other  pixels  by  given  by  their  rela2ve  displacement  index.  

An  example  chain  code.  The  reference  pixel  star2ng  the  chain  is  marked    
by  an  arrow:    
0007766555555670000006444444442221111112234445652211  

Connected  components  -­‐  24   figure from Sonka, Hlavac, Boyle

 Integral  Images  
Values  ii(i,j)  at  loca2on  (i,j)  represent  the  sums  of  all  the  original  pixel  
values  lek  of  and  above  (i,j)    

Compu(ng  Integral  Images:  

1.  Let  s(i,j)  denote  a  cumula2ve  row  sum,  let  s(i,-­‐1)=0.  
2.  Let  ii(i,j)  be  an  integral  image,  let  ii(-­‐1,j)=0.  
3.  Using  a  single  row-­‐by-­‐row  scan  of  the  image,  calculate  s(i,j)  and  ii(i,j)  
using  the  following  itera2ve  formulas  

   s(i,j) = s(i,j-1)+f(i,j)

ii(i,j) = ii(i-1,j)+s(i,j)
Connected  components  -­‐  25  
 Integral  Images:    
Compu2ng  Sums  in  an  Area  

The  sum  of  values  in  area  D  can  be  obtained  using  ii  

Connected  components  -­‐  26   figure from Sonka, Hlavac, Boyle

 Integral  Images:    
Compu2ng  Rectangle  Features  

•   Rectangle-­‐based  features  are  computed  from  an  integral  image.    

•   These  features  are  computed  by  subtrac2ng  the  sum  in  the  shaded  
rectange(s)  from  the  sum  in  the  non-­‐shaded  rectangle(s).  
•   Pictures  show:  (a-­‐b)  two-­‐rectangle,  (c)  three-­‐rectangle,  (d)  four  rectangle.  
•   These  features  can  easily  be  computed  at  different  scales/sizes.    

Connected  components  -­‐  27   figure from Sonka, Hlavac, Boyle

 Gray  Image  Histograms  
Histogram  h:    
 gray-­‐level  frequency  distribu2on  of    
 the  gray  level  image  f  
 
hf(g):    #  of  pixels  in  f  whose  gray  level  is  g  
 
Cumula@ve  histogram  Hf(g):    
 #  of  pixels  in  F  whose  gray  level  is  ≤g  
 
In  Matlab:  imhist  
   

Connected  components  -­‐  28  

 Color  Histograms  

  Reduced  color  representa2on    =    

     C  =  (R/16)  *  256  +    (G/16)*16    +  (B/16)  
     (This  results  in  a  24  -­‐>  12  bit  color  depth  
reduc2on)  
  This  results  in  a  4096  bin  histogram  
-  lowest  4  bits  are  less  useful  
-  requires  less  storage  
-  faster  implementa2on  -­‐  easier  to  compare    
histograms  

Connected  components  -­‐  29  

 Edge  Histograms  
  Use  edge  detector  to  compute  edges  (Gx,Gy)  
  The  edge  strength  is  given  by  the  vector  magnitude  
and  the  orienta2on  is  the  angle  of  the  vector  
  Histogram  bin  index  is  determined  using  edge  
orienta2on  (N  bins  total),  and  the  bin  count  is  
incremented  using  the  edge  magnitude  

Connected  components  -­‐  30  

 Histogram  Matching  
  Histogram  Intersec2on  
P
i min{hc (i), hb (i)}
Ih (hc , hb ) = P
i max{hc (i), hb (i)}

  Chi  Squared  Formula  

X (hc (i) hb (i))2
2
(hc , hb ) = 2
i
h c (i) + h b (i)

Connected  components  -­‐  31  

 Region  Proper2es  
  Our  goal  is  to  recognize  each  connected  component  as  
one  of  a  set  of  known  objects  
  lejers  of  the  alphabet  
  simple  objects  
  object  parts  
  We  need  to  associate  measurements,  or  proper2es,  with  
each  connected  component  that  we  can  compare  against  
expected  proper2es  of  different  object  types.  

Connected  components  -­‐  32  

 Proper2es  
  Area:  A=|S|  
  Perimeter:  P=boundary  length  
  Euler’s  number:  ν  =  S-­‐N  
S  –  number  of  con2guous  parts  of  an  object  
N  –  number  of  holes  in  an  object  
  Compactness:    P2/A  
  Projec2ons  
  Eccentricity  
  Elongatedness  
  Rectangularity  
  Convex  Hull  
  Moments  

Connected  components  -­‐  33  

 How  do  we  compute  the  perimeter  of  a  
connected  component?  

1.  Count  the  number  of  pixels  in  the  

component  adjacent  to  0’s  
  perimeter  of  black  square  would  be  1  
  but  perimeter  of  gray  square,  which  
has  4x  the  area,  would  be  4  
  but  perimeter  should  go  up  as  sqrt  of  
area  
2.  Count  the  number  of  0’s  adjacent  to  
the  component  
  works  for  the  black  and  gray  
squares,  but  fails  for  the  red  
dumbbell    

Connected  components  -­‐  34  

 How  do  we  compute  the  perimeter  of  a  
connected  component?  
3)  Count  the  number  of  sides  of  pixels  in  the  
component  adjacent  to  0’s  
  these  are  the  cracks  between  the  pixels  
  clockwise  traversal  of  these  cracks  is  
called  a  crack  code  
  perimeter  of  black  is  4,  gray  is  8  and  
red  is  8  
  What  effect  does  rota2on  have  on  the  
value  of  a  perimeter  of  the  digi2za2on  of  a  
simple  shape?  
  rota2on  can  lead  to  large  changes  in  
the  perimeter  and  the  area!  

Connected  components  -­‐  35  

 Perimeter  computa2on  (cont.)  
  We  can  give  different  weights  to  boundary  pixels    
  1  –  ver2cal  and  horizontal  pairs  
  21/2    –  diagonal  pairs  
  The  boundary  can  be  approximated  by  a  polygon  line  (or  
splines)  and  its  length  could  be  used  

  It  majers  most  for  small  (low  resolu2on  objects)  

Connected  components  -­‐  36  

 Compactness  
•  smallest  for  a  circle:  4π2r2/πr2  =  4π  
•  higher  for  elongated  objects  
 

a) A compact object. b) no-compact object

Connected  components  -­‐  37   figure from Sonka, Hlavac, Boyle

 Projec2ons  

X
ph (i) = f (i, j)
j
X
pv (j) = f (i, j)
i

Connected  components  -­‐  38   figure from Sonka, Hlavac, Boyle

 Eccentricity  

figure from Sonka, Hlavac, Boyle

u  Ratio of the length of the maximum chord A to the maximum chord B
perpendicular to A (ratio of major and minor axes of an object)
u  An approximate measure could be based on a ratio of main region axes of
inertia

Connected  components  -­‐  39  

 Elongatedness  

figure from Sonka, Hlavac, Boyle

u  Ratio of the length of the sides of the region bounding rectangle
u  To make it work for regions like (b) sometimes redefined as the ratio of
area and maximum region thickness
²  The thickness can be computed by counting the number of erosion
steps d needed to completely remove the object
A
E=
(2d)2
Connected  components  -­‐  40  
 Rectangularity  
 

figure from Sonka, Hlavac, Boyle

u  Ratio of area of bounding rectangle ab and area of the object

Connected  components  -­‐  41  

 Convex  Hull  
Features
•  Area of the CH
•  Ratio of the area of the CH
and the region

figure from Sonka, Hlavac, Boyle

u  Computed by creating a monotone polygon (min and max pixel coordinate
in each row)
u  Followed by iteratively filling concave regions (computed using triples of
pixels along the boundary)
u  Number of steps linear in number of boundary pixels

Connected  components  -­‐  42  

 Concavity  Tree  

figure from Sonka, Hlavac, Boyle

u  Constructed iteratively starting from the convex hull

Connected  components  -­‐  43  

 Bounding  Box  and  Extremal  Points  

Topmost left Topmost right

Leftmost top Rightmost top

Leftmost bottom Rightmost bottom

Bottommost left Bottommost right

Can be used to approximate various properties

Connected  components  -­‐  44  
 Moments  
  An  “ideal”  set  of  features  should  be  independent  of  
  the  posi2on  of  the  connected  component  
  the  orienta2on  of  the  connected  component  
  the  size  of  the  connected  component  
  ignoring  the  fact  that  as  we  “zoom  in”  on  a  shape  we  tend  to  
see  more  detail  
  These  problems  are  solved  by  features  called  moments  

Connected  components  -­‐  45  

 Central  moments  
  Let  S  be  a    connected  component  in  a  binary  image  
  generally,  S  can  be  any  subset  of  pixels,  but  for  our  
applica2on  the  subsets  of  interest  are  the  connected  
components  
  The  (j,k)’th  moment  of  S  is  defined  to  be  
X
Mjk (S) = xj y k
(x,y)2S

Connected  components  -­‐  46  

 Central  moments  
  M00  =  the  area  of  the  connected  component  
X X
0 0
M00 = x y = 1 = |S|
(x,y)2S (x,y)2S
  The  center  of  gravity  of  S  can  be  expressed  as  
P
M10 (S) x
x̄ = =
M00 (S) |S|
P
M01 (S) y
ȳ = =
M00 (S) |S|
Connected  components  -­‐  47  
 Central  moments  
  Using  the  center  of  gravity,  we  can  define  the  central  
(j,k)’th  moment  of  S  as  
X
j k
µjk = (x x̄) (y ȳ)
(x,y)2S
  If  the  component  S  is  translated,  this  means  that  we  have  
added  some  numbers  (a,b)  to  the  coordinates  of  each  
pixel  in  S  
  for  example,  if  a  =  0  and  b  =  -­‐1,  then  we  have  shiked  the  
component  up  one  pixel  

Connected  components  -­‐  48  

 Central  moments  
  Central  moments  are  not  affected  by  transla2ons  of  S.    Let  
S’={(x’,  y’):x’=x+a,  y’=y+b,  (x,y)  in  S}  
  The  center  of  gravity    of  S’  is  the  c.o.g.  of  S  shiked  by  (a,b)  
P 0
P P P
0 x (x + a) x a
x̄(S ) = 0
= = + = x̄ + a
|S | |S| |S| |S|
  The  central  moments  of  S’  are  the  same  as  those  of  S  
X
µjk (S ) = 0
(x0 x̄(S 0 ))j (y 0 ¯(y)(S 0 ))k
X
= (x + a [x̄(S) + a])j (y + b [ȳ(S) + b])k
X
= (x x̄)j (y ȳ)k = µjk (S)

Connected  components  -­‐  49  

 Object  Orienta2on  

  Object  orienta2on  can  be  computed  from  central  

moments  
✓ ◆
1 2µ11
✓ = arctan
2 µ20 µ02

Connected  components  -­‐  50  

 Central  moments  
  The  standard  devia2ons  of  the  x  and  y  coordinates  of  S  
can  also  be  obtained  from  central  moments:  
r r
µ20 µ02
x = , y =
|S| |S|
  We  can  then  create  a  set  of  normalized  coordinates  of  S  
that  we  can  use  to  generate  moments  unchanged  by  
transla2on  and  scale  changes  
x x̄ y ȳ
x̃ = , ỹ =
x y

Connected  components  -­‐  51  

 Normalized  central  moments  
  The  means  of  these  new  variables  are  0,  and  their  
standard  devia2ons  are  1.    If  we  define  the  normalized  
moments;  mjk  as  follows  
P j k
x̃ ỹ
mjk =
M00
  then  these  moments  are  not  changed  by  any  scaling  or  
transla2on  of  S  
  Let  S*  =  {(x*,y*):  x*  =  ax  +  b,  y*  =  ay  +  c,  (x,y)  in  S}  
  if  b  and  c  are  0,  then  we  have  scaled  S  by  a  
  if  a  is  0,  then  we  have  translated  S  by  (b,c)  

Connected  components  -­‐  52  

 Normalized  central  moments  
!j !k
1 X x⇤ x(S ⇤ ) y ⇤
y(S ⇤)
mjk (S ⇤ ) = ⇤ ⇤
|S| x (S ) y (S )

1 X aj (x x̄(S))j ak (y ȳ(S))k
=
|S| aj xj (S) ak yk (S)
= mjk (S)
  Details  of  the  proof  are  simple.  

Connected  components  -­‐  53