Image Processing Reference
In-Depth Information
Fig. 7.4
Two examples of
extracted BLOBs. Each
BLOB has a unique color
(
4
,
0
)
is investigated
(
4
,
1
)
. This is outside the image and therefore not an object
pixel. All the neighbors of
(
4
,
0
)
have now been investigated and the algorithm
therefore traces back and looks at the second neighbor of
(
3
,
0
)
, namely
(
3
,
1
)
.This
is an object pixel and is therefore labeled 1, burned and becomes the new focus of
attention. In this way the algorithm also finds
(
3
,
2
)
to be part of object 1 and finally
ends by investigating the fourth neighbor of
(
2
,
0
)
.
All pixels which are part of the top object have now been labeled with the same
label 1 meaning that this BLOB has been segmented. The algorithm then moves on
following the scan path in Fig. 4.28 until it meets the next object pixel
(
1
,
3
)
, which
is then labeled 2, and starts a new grass-fire. The result will be the image shown in
Fig.
7.2
, where each BLOB has a unique label. In Fig.
7.4
the BLOBs from Fig.
7.1
have been extracted and color coded according to their BLOB label.
The algorithm can be implemented very efficiently by a function calling itself.
Such an algorithm is said to be recursive and care should be taking to ensure the
program is terminated properly as recursive algorithms have no built-in termination
strategy. Another danger is that a computer has a limited amount of memory allo-
cated to function calls. And since the grass-fire algorithm can have many thousands
function calls queued up, the computer can run out of allocated memory.
−
7.1.2 The Sequential Grass-Fire Algorithm
The grass-fire algorithm can also be implemented in a sequential manner. This is
less efficient from a programming point of view, but it does not suffer from the
problems mentioned above for the recursive grass-fire algorithm.
The sequential grass-fire algorithm also scans the image from top left to bottom
right. When an object pixel is found it does two things. Firstly, in the output image
it gives this pixel an object label, 1, and secondly it “burns” the pixel in the input
image by setting it to zero (black). The next step is to check the neighbors (four or
eight pixels depending on the connectivity) and see if any of them is an object pixel.
So far this is exactly the same as the recursive grass-fire algorithm, but now comes
the difference. If any of the neighbors is an object pixel they are labeled 1 in the
output image and set to zero (burned) in the input image. Also, they are placed in
a list. Next step is to take the first pixel in the list and check its neighbors. If any
are object pixels they are labeled in the output, set to zero in the input and placed
