Page 193 -

Chapter 4 ■ Grey-Level Segmentation 167

There are a great number of ways to update the probabilities, to weight the
Q values, and to perform the initial classification. A good algorithm is soundly
based in mathematics and good sense, but there is a lot of leeway in how it
might be implemented.

4.4 Moving Averages

The relaxation method has one serious drawback that has not been men-
tioned — it is very slow. If speed is a criterion of interest, then a method
that uses moving averages is quite appealing [Wellner, 1993]. This algorithm
yields one threshold per pixel very quickly, and gives surprisingly good seg-
mentations. It is designed for images containing text; for example, scanned
documents. In these cases the illumination can be expected to be good, as can
the general image quality.
A moving average is just the mean grey level of the last n pixels seen. The
image can be treated as a one-dimensional stream of pixels, which is common
in C anyway, and the average can either be computed exactly or estimated via:
M i
M i+1 = M i − + g i + 1 (EQ 4.51)
n
where M i+1 is the estimate of the moving average for pixel i + 1havinggrey
level g i+1 ,and M i is the previous moving average (i.e., for pixel i).
Any pixel less than a fixed percentage of its moving average is set to black,
otherwise to white. To avoid a bias for one side of the image over the other,
1
a novel scanning method called boustrophedon scanning was employed. This
means traversing pixels in opposite directions in every other line. That is, the
pixel following the last one in row i is the last one in row i + 1, followed by
the second last in row i + 1, and so on back to the start of row i + 1; this is
followed by the start pixel in row i + 2, and so to the final one. This avoids
the discontinuity at the end of the line that occurs with the usual C method of
scanning a two-dimensional array.
The process begins with an estimate of the moving average; a value of
127 ∗ n was selected, and this will only affect the first few pixels in the image.
The value of n used is the number of columns divided by 8. Now Equation
4.51 is used to compute the moving average estimate for the next pixel (the
first), which is used immediately as a threshold:


M i 100 − pct
 0 if g i < ×
V = n 100 (EQ 4.52)
255 otherwise

1 Greek, meaning ‘‘as the ox plows.’’