# Adaptive Binarisation

The previous post covered the basics of binarisation, and introduced the Otsu algorithm, a good method for finding a global threshold number for a page. But there are inevitable limitations with using a global threshold for binarisation. Better would be to use a threshold that is adapted over different regions of the page, so that as the conditions of the page change so can the threshold. This technique is called adaptive binarisation.

For each pixel of an image, adaptive binarisation considers the pixels around it to determine a good threshold. This means that even in an area which is heavily shaded, for example near the spine of a book, the text will be correctly differentiated from the background, as even though they may both be darker than the text in the rest of the page, it is the darkness relative to its surroundings that matters.

A popular algorithm for this adaptive binarisation technique was described in a 2000 paper by J. Sauvola Adaptive document image binarization. The key part of the paper which is still used today is his modification of an earlier algorithm for adaptive binarisation by Niblack (1986), to add standard deviation to the calculation of a local threshold for an area. This improves the algorithm significantly, enabling it to take better account of variations in particularly dark or light areas of an image, such as in the gutter or a particularly stained area.

There are two parameters that need to be set for the Sauvola algorithm,
a general *threshold value* called *k*, and the *window size*. The
*threshold value* works much the same way as in other binarisation
algorithms, essentially setting how aggressive the algorithm should be
in removing dark areas, at the expense of potentially removing some
parts of text. It can be between 0 and 1, with a higher number
resulting in more aggressive binarisation. The *window size* is
the number of pixels around each pixel which are taken into account by
the algorithm to determine whether to set the pixel to black or white.
A larger window size results in less local adjustment for different
areas of a page, but too low and a good deal of noise can be incorrectly
detected as text.

A major disadvantage of adaptive binarisation methods is that they tend to be much slower than global threshold binarisation, as a new threshold must be calculated for every pixel. In the case of the Sauvola algorithm, this requires calculating the mean and standard deviation of every pixel in the window around each pixel, for each pixel, which adds up to a lot of calculations.

Fortunately, however, we can use some clever mathematics to
dramatically reduce the amount of comuptation that is necessary for
adaptive binarisation. The key is using *Integral Images*, also
known as *Summed Area Tables*. These work by calculating the sum of
each pixel above and to the left of each pixel, which can then be
used to calculate the mean and standard deviation of any area in an
image by a very simple calculation of adding two numbers together
and subtracting another two numbers from the Integral Image - a
process that is many times faster than calculating the mean and
standard deviation from scratch for each pixel. The *Integral Image*
essentially does all of the calculation once for the whole image.
This technique is well described in the paper
Efficient implementation of local adaptive thresholding techniques using integral images
by Shafait, Keysers and Breuel.

## Our Tools

There are surprisingly few free software tools to do binarisation
with the Sauvola algorithm, and none that I could find that can
use *Integral Images* to speed the processing up. When you’re just
binarising a few images, maybe that isn’t so important, but when
you’re operating on a scale of many thousands of images, potentially
processing each one multiple times with different threshold values,
cutting the processing time from 60 seconds to 0.1 seconds makes a
very big difference.

So, we wrote a Go package which does Sauvola binarisation, which
contains both standalone command line tools and can be used as a
package in your own Go projects. The same package contains some
other image preprocessing functionality, so the package is called
rescribe.xyz/preproc (docs).
The command line binarisation tool in the package is *binarize*, and
the relevant Go functions are Sauvola() and IntegralSauvola().

The Integral Image support is provided by another package we wrote, rescribe.xyz/integral (docs), which will also be useful for other image processing tools which require calculating the mean or standard deviation for different areas of an image. It includes tests and examples, so should be easy to pick up and use for your own projects.