Detect clusters in an RGB space

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.

• @A_A thanks for the tidy up didn't know you could do that.
– TJA
Apr 10 '18 at 1:48
• No worries. I was wondering if it would be possible to clarify how you see this working conceptually because the phrase "... I would like to take advantage of the essentially 3D nature of RGB colour vs 2D grayscale images to improve the accuracy..." draws a comparison between two dissimilar things, the image and the colour space. I suppose that your objective is to "filter" only what appears to be grayscale from an image (?).
– A_A
Apr 10 '18 at 7:39
• So the main objective is the "binarization" of the images into just black and white values before using various elements of the OpenCV or similar libraries.
– TJA
Apr 11 '18 at 9:18
• The idea behind using a 3D space where the axes are R, G, B is that that the grey's will be relatively close to a line from black(0, 0, 0) to white(256, 256, 256) well actually more like (80, 80, 80) whereas the blue biro and brown water stains would be off to the side. The reason I refer to clusters is that I expect to see groups of similar colours forming clusters within that space. And by working from the notional centre of these clusters I can include/exclude surrounding colour points from each of those sets.
– TJA
Apr 11 '18 at 9:29

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.