7

I need to solve the following problem:

INPUT: Image IM, Palette PA

OUTPUT: IM only with the colours of PA

The input image is in RGB but I can convert it to HSV. The colour target palette I specify contains at the moment: black, white, light gray, gray, dark gray, blue, pink, red, purple, green, yellow, brown, orange.

I searched a lot for that, but I can only find reducing an image to the most common colours or reducing it to a fixed palette like 16 colours EGA graphics.

I found the best answer of this: How do I convert any image to a 4-color paletted image using the Python Imaging Library?

It has an input palette and reduces the image to that. Is there an equal way to do in in OpenCV with C++ ?

Community
  • 1
  • 1
Kenyakorn Ketsombut
  • 2,072
  • 2
  • 26
  • 43
  • 1
    difficult to tell what you're trying to do. are you trying to write a color quantizer? or do you just want to force an rgb image to a fixed palette? if the later, then all you have to do is set each pixel to the closest color (via L2) from the palette. if the former, then you can use a clustering algorithm (e.g. k means). – thang Jan 31 '13 at 03:41
  • 1
    What @thang commented works just fine, but watch out for the color space you are doing this. See http://stackoverflow.com/a/14237976/1832154 as an example of differences between distinct color spaces for replacing colors by the closest one. – mmgp Jan 31 '13 at 03:45
  • thanks for your quick replies. indeed I "want to force an rgb image to a fixed palette". And yes one of my major problems is to find a good distance measurement between two colours. http://stackoverflow.com/questions/14236721/how-to-replace-pixel-color-with-other-color-in-image/14237976#14237976 is interesting. However I thought the would be a ready-to-use implementation, like the python library I quoted above. – Kenyakorn Ketsombut Jan 31 '13 at 05:18
  • **What have you tried?** Mapping an image to a *given* fixed palette is not hard, unless you want to go into dithering. See e.g. https://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dithering for details. – Has QUIT--Anony-Mousse Jan 31 '13 at 10:13
  • "Mapping an image to a given fixed palette" is exactly what I want to do. To tell me, that it is not hard, is not very constructive. – Kenyakorn Ketsombut Jan 31 '13 at 12:34
  • @Anony-Mousse that doesn't make any sense. Dithering is a very easy thing to do, clustering is not (kmeans is NP-hard for instance). – mmgp Jan 31 '13 at 17:33
  • @KenyakornKetsombut re-add the tag `cluster-analysis` please, it makes complete sense for the question. – mmgp Jan 31 '13 at 17:34
  • @mmgp: but the question is about mapping an image to a *given* palette, *not* finding an optimized palette. No clustering involved. – Has QUIT--Anony-Mousse Jan 31 '13 at 17:35
  • @Anony-Mousse the palette is given, but now how do you map each input color to a color in the palette ? There are at least two approaches, mentioned in the two first comments. – mmgp Jan 31 '13 at 17:38
  • @mmgp of course he needs to measure color distance, but he does not need to redo color quantization with k-means if he already has a given palette... – Has QUIT--Anony-Mousse Jan 31 '13 at 23:25
  • @Anony-Mousse I think we are just seeing this in different ways. I understand that you are considering the clustering step to construct a certain palette, but since he has one already then there is no need for such step. On the other hand, there are ways to use clustering to map the colors in the present image to the already fixed palette. For example, we could group the image into `p` clusters, and then the mean color of each cluster could be used to determine which color in the palette the entire cluster is mapped to. – mmgp Jan 31 '13 at 23:33
  • @mmgp why should this improve the result for a fixed palette, if you first map the image to *another* palette of p colors, then substitute the colors to the closest match? I figure you like the k-means color quantization, but it does not really make sense to use it this way. The quality will be worse, and so will the runtime. – Has QUIT--Anony-Mousse Feb 01 '13 at 07:27
  • @Anony-Mousse First of all, I never suggested k-means so I have no idea why you are suggesting I like that particular method for this task. I also never claimed this method improves or not the final result, but I don't have the results to say whether it does or not. On the other hand, you seem to be sure since you are claiming it never does. Can you actually prove that the quality will be worse ? – mmgp Feb 01 '13 at 11:45
  • @mmgp: Mind it, but k-means is the only clustering that is popular for reducing a color image to k colors... Now for the quality: if e.g. the color palette is not optimized for this particular image, then the results will be next to meaningless. Say you have an image that is mostly different kinds of blue. The target palette is as desribed in the question. So pretty much every cluster will become the same blue, and you have a 100% blue image in the end. Applying Floyd-Steinberg will however produce a properly dithered image to minimize the error (for the given palette). – Has QUIT--Anony-Mousse Feb 01 '13 at 12:38
  • @Anony-Mousse while you have provided an example where in fact the result is bad when using clustering methods, if the palette happens to have a single color that is closer to every color in the image than any other color in the palette, you will get the same bad result. It remains to be proved that clustering is always bad here. – mmgp Feb 01 '13 at 12:46
  • @mmgp Well, for obvious reasons the error when using dithering *directly* will always be better than *merging the cluster to a single color* before dithering, too! Sorry, I still say your suggestion of using clustering is useless. Show me any example where it *improves* the result, please! – Has QUIT--Anony-Mousse Feb 01 '13 at 12:51
  • @Anony-Mousse you are adding another tool to the mix, let us compare apples to apples. At some point I might add an answer with actual results, you can also add your results in the mean time. – mmgp Feb 01 '13 at 12:55

2 Answers2

2

Suppose that rgb color space is 3D cube

rgb color space

And Palette PA is several points in this cube. So our problem is reduced to finding the nearest Palette PA point for any given rgb point in 3D space.

I think the better solution is k-d tree

enter image description here

At the end of wiki page you can find several links for c++ implementations

Pylyp
  • 404
  • 1
  • 7
  • 15
1

Since your palette is fixed, you'll want to use a dithering approach such as Floyd Steinberg dithering along with an appropriate color similarity measure, for example in Lab color space.

Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194