Transcript Binary Image Analysis

Mata kuliah : T0283 - Computer Vision
Tahun
: 2010
Lecture 06
Binary Image Analysis
Learning Objectives
After carefully listening this lecture, students will be able
to do the following :
show how connected component labeling is performed
and its uses in shape classifier
demonstrate object area and perimeter calculation based
on binary images
January 20, 2010
T0283 - Computer Vision
3
From Processing to Analysis
Localized perspective in binary image processing
Low-level vision
PHIL
High-level vision
Holistic perspective in binary image analysis
January 20, 2010
T0283 - Computer Vision
4
Connectivity
X’
Y’
Y
X
X and Y are connected
X’ and Y’ are NOT connected
a and b are connected if there exists a path from a to b
Notation: if a and b are connected, we write a ~ b
January 20, 2010
T0283 - Computer Vision
5
Connected Components in Digital Images
A set S of pixels is a CC if there is at least one path that
joins every pair {p,q} of pixels in S, and contains
exclusively of pixels in S.
Two types of connectivity: 4 - (edge) connectivity and 8(vertex) connectivity
January 20, 2010
T0283 - Computer Vision
6
Connected Component
Two pixels are c-adjacent (c=4 or 8) if they share at least
an edge (c=4), or a vertex (c=8).
Two pixels are c-connected (c=4 or 8) if it is possible to find
a path between these two pixels through pairs of c-adjacent
(c=4,8) pixels.
A c-connected component is a maximal connected set
where each pixel is c-connected to other pixels in the set.
January 20, 2010
T0283 - Computer Vision
7
Example
q
q
p
p
p ~ q no matter 4-neighbors
or 8-neighbors
January 20, 2010
p ~ q only when 8-neighbors
is considered
T0283 - Computer Vision
8
Component Labeling
original
binary
image
If 4-neighbors,
three connected
components
January 20, 2010
T0283 - Computer Vision
If 8-neighbors,
two connected
components
9
Connected Component Labeling
1
2
4
January 20, 2010
T0283 - Computer Vision
3
5
10
MATLAB Function BWLABEL
>help bwlabel
BWLABEL Label connected components in binary image.
L = BWLABEL(BW,N) returns a matrix L, of the same size as BW, containing
labels for the connected components in BW. N can have a value of either
4 or 8, where 4 specifies 4-connected objects and 8 specifies
8-connected objects; if the argument is omitted, it defaults to 8.
The elements of L are integer values greater than or equal to 0. The
pixels labeled 0 are the background. The pixels labeled 1 make up one
object, the pixels labeled 2 make up a second object, and so on.
[L,NUM] = BWLABEL(BW,N) returns in NUM the number of connected objects found in BW.
See also bwareaopen, bweuler, bwlabeln, bwselect, label2rgb.
January 20, 2010
T0283 - Computer Vision
11
Euler Number
EN=0
EN=-1
EN=-3
Euler Number EN=number of connected components – number of holes
January 20, 2010
T0283 - Computer Vision
12
CC Algorithm
Process the image row by row
Assign a label to the first pixel of each CC
Otherwise assign its label by propagating from left or top
1
2
1
2
1
1
January 20, 2010
1
1
2
1
?
T0283 - Computer Vision
Clash!
(equivalence)
13
One approach
Propagate the smaller label in case of clash
Record the equivalence in a table
After the entire image is processed, find the set of
equivalence classes
Second pass replaces each label with its equivalent
class
Two passes!
January 20, 2010
T0283 - Computer Vision
14
Boundary of Binary Objects
X
X=X-(X _ B)
January 20, 2010
or
X
X=(X + B) – B
T0283 - Computer Vision
15
Chain Codes Boundary Representation
4-directional chain code:
0033333323221211101101
January 20, 2010
T0283 - Computer Vision
8-directional chain code:
076666553321212
16
Two Problems with the Chain Code
Chain code representation is conceptually
appealing, yet has the following two problems
Dependent on the starting point
Dependent on the orientation
To use boundary representation in object
recognition, we need to achieve invariance to
starting point and orientation
Normalized codes
Differential codes
January 20, 2010
T0283 - Computer Vision
17
Normalization Strategy
33001122
33001122
30011223
00112233
01122330 Sort
11223300 rows
12233001
22330011
23300112
January 20, 2010
00112233
01122330
11223300
12233001
22330011
23300112
33001122
30011223
T0283 - Computer Vision
First row gives the
normalized chain code
00112233
18
Differential Strategy
90o
33001212
normalize
00121233
33010122
normalize
01012233
Differential coding:
dk=ck-ck-1 (mod 4) for 4-directional chain codes
dk=ck-ck-1 (mod 8) for 8-directional chain codes
January 20, 2010
T0283 - Computer Vision
19
Shape Numbers= Normalized Differential
Chain Codes
Differential code:
dk=ck-ck-1 (mod 4)
33001212
differentiate
10101131
normalize
01011311
33010122
differentiate
10113110
normalize
01011311
Note that the shape numbers of two objects related by 90o rotation
are indeed identical
January 20, 2010
T0283 - Computer Vision
20
Examples : Chain Encoding
2 unit
pixel
y
1 unit
pixel
Encoding
start point
x
January 20, 2010
T0283 - Computer Vision
21
Perimeter Calculation
3
4
5
2
P
6
1
Direction 0
7
Start
11000060666464444332
Perimeter P = SE + V2 SO units
= 16 + 4 V2 = 21.66 units
January 20, 2010
T0283 - Computer Vision
22
Area Calculation
Y
Y
Direction 0
Additive comp. = 1 x y
Direction 5
Subtractive comp = (1 x y) – 0.5
Y
Y
Direction 1
Subtrac. comp. = (1 x y) + 0.5
January 20, 2010
Direction 2 dan 6
Zero component (neutral)
T0283 - Computer Vision
23
Area Calculation (cont’d)
3
Subtractive
y-coordinate
7
6
5
4
4
2
4
P
5
6
1
0
Additive
7
Start
6
5
3
2
11000060666464444332
3
Area = 5.5 + 6.5 + 7 + 7 + 7 + 7 + 0 + 6 + 0 + 0 + 0 – 3 + 0 – 2 – 2
– 2 – 2 – 2.5 – 3.5 + 0
= 29 square units
January 20, 2010
T0283 - Computer Vision
24
MATLAB Implementation
January 20, 2010
T0283 - Computer Vision
25
Run Length Encoding (RLE)
Segmen citra biner
0
0
0
0
0
0
0
0
0
0
#
#
#
0
#
0
0
0
#
#
#
#
0
0
0
0
#
#
#
0
#
0
0
0
0
0
0
#
#
0
0
0
0
0
0
0
0
0
10(0), 3(1), 1(0), 1(1), 3(0), 4(1), 4(0), 3(1), 1(0), 1(1), 6(0), 2(1), 9(0)
January 20, 2010
T0283 - Computer Vision
26
Chord Encoding
Segmen citra biner
baris
January 20, 2010
0
0
0
0
0
0
0
0
0
0
#
#
#
0
#
0
0
0
#
#
#
#
0
0
0
0
#
#
#
0
#
0
0
0
0
0
0
#
#
0
0
0
0
0
0
0
0
0
1 (2,4) (6,6); 2 (2,5); 3 (2,4) (6,6); 4 (5,6).
kolom
T0283 - Computer Vision
27
Matlab Implementation on Shapes Classifier
Step
Step
Step
Step
Step
Step
Step
1:
2:
3:
4:
5:
6:
7:
Read image
Convert image from rgb to gray
Threshold the image
Invert the Binary Image
Find the boundaries Concentrate
Determine Shapes properties
Classify Shapes according to
January 20, 2010
T0283 - Computer Vision
28
Step 1: Read image
RGB = imread('test.bmp');
figure, imshow(RGB), title('INPUT IMAGE');
January 20, 2010
T0283 - Computer Vision
29
Step 2: Convert image from rgb to gray
GRAY = rgb2gray(RGB);
figure,imshow(GRAY),title('GRAY IMAGE');
January 20, 2010
T0283 - Computer Vision
30
Step 3: Threshold the image.
threshold = graythresh(GRAY);
BW = im2bw(GRAY, threshold);
figure, imshow(BW), title('BINARY IMAGE');
January 20, 2010
T0283 - Computer Vision
31
Step 4: Invert the Binary Image
BW = ~ BW;
figure,imshow(BW),title('INVERTED BINARY IMAGE');
January 20, 2010
T0283 - Computer Vision
32
Step 5: Find the boundaries
Concentrate only on the exterior boundaries.
Option 'noholes' will accelerate the processing by preventing
bwboundaries from searching for inner contours.
[B,L] = bwboundaries(BW, 'noholes');
%[L, N] = bwlabel(BW,8);
Step 6: Determine objects properties
STATS = regionprops(L, 'all');
% we need 'BoundingBox' and 'Extent'
January 20, 2010
T0283 - Computer Vision
33
Step 7: Classify Shapes according to properties
%
%
%
%
Square = 3 = (1 + 2) = (X=Y + Extent = 1)
Rectangular = 2 = (0 + 2) = (only Extent = 1)
Circle = 1 = (1 + 0) = (X=Y , Extent < 1)
UNKNOWN = 0
for i = 1 : length(STATS)
W(i) = uint8(abs(STATS(i).BoundingBox(3) - STATS(i).BoundingBox(4)) < 0.1);
W(i) = W(i) + 2 * uint8((STATS(i).Extent - 1) == 0 );
centroid = STATS(i).Centroid;
switch W(i)
case 1
plot(centroid(1),centroid(2),'wO');
case 2
plot(centroid(1),centroid(2),'wX');
case 3
plot(centroid(1),centroid(2),'wS');
end
end
January 20, 2010
T0283 - Computer Vision
34
Step 7: Classify Shapes according to properties (cont’d)
figure, imshow(RGB), title('HASIL IDENTIFIKASI SQUARE, CIRCLE &
RECTANGLE'); hold on
January 20, 2010
T0283 - Computer Vision
35