Detect clusters in an RGB space

Question

With OCR one of the first stages in a processing pipeline is to accurately identify what is print and what is paper, generally achieved by some form of binarization.

In the good old days most scans were captured as grayscale images. For clean images with a high level of contrast, i.e. already largely black and white, Otsu's method worked quite well.

However once things like yellowing of paper, brown water stains, notes in blue biro, and other artefacts that appear as dark grey or black in a greyscale image, along with faded print are added into the mix we find ourselves in trouble.

These days almost all scanners and smart phones capture colour images and I would like to take advantage of the essentially 3D nature of RGB colour vs 2D grayscale images to improve the accuracy of the process.

To that end can you please help me with links to methods/algorithms that help to identify the centres of clusters of colour in a 3D RGB space.

Answer 1

At first this would appear to be some form of clustering problem and indeed, the direct answer to this question would be something like K-means clustering to split the colour space in compartments, or rather, sample clouds corresponding to different annotations on a page of text.

However, there is a simpler approach to that. Indeed, strictly speaking, grayscale is a line...or, more or less a cylinder or even an ellipsoid with its longest axis on the "grayscale" line. The line that is formed by setting R=G=B on the RGB colour cube.

Therefore, the problem of "filtering out" anything that is not grayscale ends up being the problem of estimating how far a given colour sample $u(r,g,b)$ is from the grayscale line.

You can get that information by evaluating the distance of a point to a line. Now, for a scanned document that contains both grayscale and some other colour "artifacts" (whatever these may be), the histogram of this distance is going to be bimodal. Because, the pixels that belong to the printed text are going to be close to the line (therefore, small distances) and the pixels that belong to anything that is coloured are going to be far from the line (therefore, large distances). Therefore, it might even be possible to now apply Otsu's method on the histogram of distances and find the threshold. I say "it might even be possible" because the two "classes" might end up being so much separated that Otsu's method is even an overkill.

But, that is not all. Because real world documents, photographed or scanned are almost never strictly speaking grayscale. They are likely to have a tint. The tint is simply a bias towards some colour. This would manifest itself as a different orientation of the grayscale line in the RGB colour cube. Therefore, an additional step might turn out to be that you first have to do some form of normalisation to the image to either ensure that "gray is gray" or that you can discover the sort of "tint" in the image that would imply the orientation of the "grayscale line"

Alternatively, the same task might be easier to handle in a different colour space.

Hope this helps.