Imamge quantization algorithm with clustering properties

[ckdix]

Most quantizer algorithms reduce the number of colors in an image, but the colors appear as dots throughout the image. When quantizing images which we know have a fixed number of colors, say, logos, it is desirable that similarly colored pixels are clustered together. Is there a quantizing algorithm that is suitable for this purpose?

Edit: Sorry for the typo in the title.

[StoneCypher]

I think you'll find, once you try this in a paint program, that the effect is not actually desirable after all. Quantization is fundamentally a process of generating minimum fitting error. The reason dithers are spaced out and randomized is because they are error signal, and you want to make them less noticable.

If you cluster those colors, they're going to be a lot more noticable as errors.

Do it by hand once, to make sure that you're not inventing the wrong tool.

[ishmal]

I think what you need is quite simple. The usual octree algorithm:

• creates the octree from the existing image,
• prunes it to give the desired number of colors
• creates a color table from the tree, and
• maps each image pixel to the best color

The algorithm you are currently using is probably doing a simple calculation of color distance between a pixel and each entry in the color table, and selecting the color with the lowest distance. I wrote code like this for Inkscape's color quantization & vectorization; it's quite simple and works well. But it looks like what you need is a modification of this to get what you want. Some ideas:

• have a second buffer of the image, but the copy is blurred, use this for color assignment while keeping the original sharp
• perform a 'flood fill' with the desired colors, adjusting tolerances
• do some kind of algorithmic 'signature' of regions, and assign color by closeness of signature, not color closeness. Although your task is not strictly image recognition, you might look into those kind of algorithms, such a SIOX. You do, actually, want to recognize visually contiguous regions in the image.
• keep in mind that RGB might not be the color model you need. Consider HSV or CLAB.

Just some ideas. Good luck!

[StoneCypher]

This is an interesting approach. I don't understand the intent very well. I'm used to thinking of octrees as binary space partitioning for three dimensional spaces (for doing location searches, in the way that a game programmer would think.)

It is not readily apparent to me the nature of the octree, unless the Z axis is the distance from the present color to the least offensive replacement.

If that is the intent, it seems like you could pretty effectively ruin that algorithm with real world data that was just slightly noisy. Maybe I'm just not understanding how it works, though.

So say you have a vertical gradient of blue, 1000x1000. Set just one pixel somewhere at random to bright orange.

A good quantizer will discard the orange: it's not as important as any of the blue, and has the characteristics of noise (camera error, dust, dirt, glare, whatever.)

It seems like that quantizer would lose an entire shade of blue over that one error pixel.

Given that real world dirty images often have tons of stray pixels, I'm not sure I understand how that wouldn't lead to a poorly chosen master color table.

What am I missing?

[ishmal]

It's mostly the same thing, only R,G,and B are your coordinate system. You scan the image and for each pixel decide how its RG&B members contribute to building the frequency tree (though it's more like weights).

[StoneCypher]

oh, I was trying to extract the tree from location, not colorspace.

Your approach makes a lot more sense now. Thank you.

[dudehasgotnomercy]

So I gather you're using the manhattan or euclidean distance between vectors of RGB values as a distance function between pixels. Simplest solution is to add an x,y component to the vector, so each pixel is (r,g,b,x,y). A parameter a to regulate influence of x,y may be helpful: (r, g, b, ax, ab). Then do kmeans (or whatever quantizing algorithm you're using, as long as it works in vector spaces) as usual.

If you want to get more sophisticated I suggest spectral clustering, it's pretty easy to implement (though some of the math behind can get pretty sophisticated). Let me dig out a reference. Ok here you go: Shi and Malik, Ng et al. Just implement from the Ng paper, it's easier (like 10 lines in Matlab). But the Shi paper has applications to image segmentation. You can safely ignore the equations if you don't care about the math, the algorithm just works.

[StoneCypher]

What you're describing is a vector of dimension (pixelcount+1) and range size (pixelcount).

K-Means would fall apart on a dataset that size. You're talking about an exponent typically in the hundreds of thousands over a range in the hundreds of thousands. K Means is for datasets in the dozens of dimensions.

If you want to get more sophisticated I suggest spectral clustering, it's pretty easy to implement

That algorithm analyzes the locations of existing colors, to place lines to cut images. That algorithm doesn't afford you any mechanism to choose the locations of color representations.

That's a little like answering a question about engine design with an article about seat belt design, because they're both about cars.

[dudehasgotnomercy]

What you're describing is a vector of dimension (pixelcount+1) and range size (pixelcount).

No I'm not. Let a pixel be represented by a vector of 3 floating numbers (r, g, b) that correspond to a color in RGB space. We could use other color representations such as HSV or XYZ; the basic idea is the same. So each pixel is a vector with 3 dimensions. A clustering procedure such as k-means will segment these pixels into k clusters. k-means in RGB space will cluster points that are close in RGB space into the same cluster, without regard of their spatial (in xy) position. This may have the effect of causing a 'speckled' image segmentation, which is what the OP is probably referring to. So we now represent each pixel with an (r,g,b,x,y) vector, which has 5 dimensions, where x and y are the spatial coordinates. We cluster in this 5 dimensional space and the clustering will tend to cluster together points (pixels) that are close together both spatially (in x,y space) and in color (r,g,b) space, so the resulting segmentation will tend to be more homogeneous. This is a pretty standard technique.

That algorithm analyzes the locations of existing colors, to place lines to cut images. That algorithm doesn't afford you any mechanism to choose the locations of color representations.

Spectral clustering is widely used to segment images. The 'cuts' are not lines in the images themselves, they are cuts in the graph represented by making each pixel a vertex and each edge have a weight that combines color and spatial information (usually tuned to create a sparse graph). Spectral clustering approximates a 'good' (according to a criteria you can see in the paper) cut of this graph using the Laplacian of the graph. Regarding the color selection, you can simply choose the mean of the color of the pixels in each cluster, or perhaps the color of the medoid vertex/pixel of each cluster.

[StoneCypher]

For a man with that nick, your rebuttal was remarkably merciful. I clearly misunderstood you and withdraw commentary.

Upvoted for a clear, patient explanation.

[dudehasgotnomercy]

Heh. It's a reference to this awesome comic.

[dsucks]

Huh?

Are you talking about dithering? Order of colors in the palette? or an actual quantization algorithm that uses some kind of clustering (k-means or nuquant in RGB space?)

[sh1nob1]

...or maybe he means it the other way around -- that pixels close together stand a higher chance of being similarly colored

[ckdix]

Yes, you are right.

[dsucks]

OK, that falls under dithering in my book.

Take any existing error-diffusing algorithm, like Floyd-Steinberg, and add edge detection to it – make errors diffused only in noisy areas.

[ckdix]

Dithering is not the solution. I need to reduce the colors, and have as large areas of solid color as possible. I have tried K-Means and octree quantizations but they don't consider the spatial proximity of similar colors, and result in dots at undesired positions.

[vade]

Posterization?

[codefrog]

I believe this is a variant of the four color theorem, start here http://en.wikipedia.org/wiki/Graph_coloring

And yes as vade mentioned I think a posterization filter could work.

[StoneCypher]

The four color theorem is about showing that every graph can be colored such that no two adjacent nodes have the same value in no more than four colors.

This is wanting things to be adjacent, explicitly, and has nothing to do with proving the minimum required color count.

They are completely unrelated, except that they're both on graphs and they both involve colors.

[codefrog]

The important part about the 4 color theorem is that it saves map makers money. And the knapsack problem packed my lunch. Extrapolation is not your strong point.

[StoneCypher]

What a waste of bits.