Restricted Palette Scanning

[StevePoling]

Everyone,

It occurred to me that the processing of colored text is a constrained one. Most books are b/w. Some coffee table books have lots of photos. But red-letter Bibles have a restricted palette of two ink colors with which the book was printed. And even coffee-table books are often printed with 4-color (CMYK) process. Except for the odd coffee-table book of art and stuff, every imaged point starts out in one of a discrete number states (e.g. black or red on white), and then things like optics, lighting, and quantizing error causes the sensor to output a pixel of a different color.

This may seem like hunting a fly with an elephant gun, but this problem seems to fit a Hidden Markov Model (that the speech recognition guys use). Printing N-1 inks onto an Nth-colored page defines an N-state machine. The HMM would map each pixel to the most likely color (drawn from that palette) on the paper at that point. I have in mind an the algorithm that would accept as input an image, a palette and background color, then output the maximum-likelihood image generated by the model. Has anyone thought of using something like this in image processing? (Not OCR, binarization)

Obviously, I don't know what I'm talking about. Maybe one of you boffins may find this interesting.

[rob]

What you're referring to is clustering. If you know that your book has red, white, and black, then you want to compute three RGB points -- one for red, one for black, and one for white -- such that all the points that are more like red than black or white are categorized as "red", all the points that are more black than red or white are categorized as "black", and, you guessed it, all the points that are more white than red or black are categorized as "white".

Two issues, though.

The first issue is that the points selected by clustering algorithms are usually just enough to categorize the data. This means that after the data is categorized, the center points chosen by the algorithm are averages of all the points that fall within that category, which may not be what you want. But, if you're willing to let the clustering algorithm do its job, and then define the representative category points yourself, then there shouldn't be a problem.

The second issue is that although you print in black and white, when you scan the print back in, if you do not scan in grayscale, then you get awful looking scans because you are scanning the image at less than the Nyquist frequency (i.e. twice the printed resolution). So for a typical 300 dpi printed sheet, you need to scan at 600 dpi or higher, preferably 1200 dpi.

Since you generally can't do that, you can scan in grayscale, and then there are various techniques to upsample the image so it has a higher resolution, but is bilevel. Scan Tailor does this for you.

I assume the solution doesn't change when you go to trilevel images, though.

[Tulon]

The code that does what you are talking about is already available in the "cpaldjvu" utility, which is part of the DjVuLibre project. The only problem is that integrating it into Scan Tailor is going to take more effort than coming up with, and implementing the algorithm itself.
So, if any of you are prepared to go all the way through implementation and integration - definitely go ahead. I do consider myself retired from the project, so you can't count on me, except for advice and guidance.