<p>Suppose we want to convert an RGB image into a paletted image. As an example, we may have a 1024x1024 image, and we want to map it onto 512 unique colors. All the colors are RGB. This is a problem of how to do this efficiently.</p>
<p>The naive solution would be to go over each color, find the distance from each RGB in the palette array, and then assigning a value to the closest one.</p>
<p>Problem is this is probably quite slow, for <span class="math-container">$n$</span> pixels in some 2D raster with <span class="math-container">$k$</span> palette indices, it's <span class="math-container">$\mathcal{O}(nk)$</span>.</p>
<p>My next thought was to take a 3D volume where each axis is R, G, and B from 0 - 255, find the average of the points along one axis, partition, and recurse, sort of like how BSP trees are built. For example, I'd find the average and slice along the red axis to partition approximately half of the palette indices into two pieces. Then in the children, I'd do the same averaging for green, and slice along the green axis, and then blue, then red, etc... eventually ending up with a tree where I can walk down it from a color by doing a dot product against the dividing plane or something, and figure out whether to traverse the front or back partitions until I reach a leaf (which would be some palette index).</p>
<p>This is a common algorithm, I don't know the name of it but I used it in my graphics classes for generating a slicing point for AABB's for models. I figure I'd get approximately <span class="math-container">$\mathcal{O}(n \lg k)$</span> (under some assumptions) which would hopefully be somewhat faster. I don't know for sure since I haven't profiled but I'd hope it is.</p>
<p>This is my idea, but is there another, better way of doing this? Ideally I figure the partitioning idea above would give me the most performance without doing something crazy, but I am unsure if there's a better way of doing it, or if this is <em>the</em> ideal way to do it. That could be a valid answer to this question, as in, &quot;yes you're right, that's the way you should do it.&quot; Likewise, I'm asking because I don't know if there's a better way of doing it, or if I'm doing a needlessly complex step when something I don't need to, or maybe there's a <span class="math-container">$\mathcal{O}(1)$</span> algorithm out there that wouldn't be too much more work. &quot;Known unknowns&quot; are why I'm asking.</p>
<p>Speed does somewhat matter here, so I'm willing to do implement something a bit more ugly if it's something noticeable, especially since there are some users of my application who don't have great computers, and anything I can do on the step that stands out for them (of which this is one of them) would be of help.</p>

CC BY-SA 4.0
2021-08-02T05:31:44.903Z
Arent you getting s bit into premature optimization here. Your optimizing k and k is at most 256(?). Most likely way less while n is easily several million. So while log(k) is nice its far better to go and parallelize this. Then realize that you have a massive parallelizing tool and do it with the graphics card if speed is really of concern.
joojaa
CC BY-SA 4.0
2021-08-02T21:10:12.350Z
@joojaa How is it a premature optimization when profiling says its the bottleneck that people notice?
Water
CC BY-SA 4.0
2021-08-02T21:13:18.317Z
Yes but if you can do a 16 times slower code that works on a gpu then you can still be faster than the benefits of reducing K to 1
joojaa
CC BY-SA 4.0
2021-08-02T21:21:56.977Z
@joojaa Doing it on the GPU is a great idea IMO, but I haven't done it because the users have very archaic GPUs (as in low end hardware from the early 2000's, can barely run OpenGL 2.0). I don't even know if they have the framebuffer extension so I could write the results into a texture. Normally I'd fire this off on a compute shader and be done with it (which is what I think you mean), but dealing with ancient hardware is much more of a pain than I thought. Further I can't debug it either, whereas code run on the CPU is something I can. If there's an OpenGL 2.0 way of doing this let me know.
Water
CC BY-SA 4.0
2021-08-05T15:59:14.453Z
The answer here goes well beyond openCV (in case you haven't seen it) https://stackoverflow.com/questions/49710006/fast-color-quantization-in-opencv
pmw1234
CC BY-SA 4.0
2021-08-05T16:00:50.913Z
Also, be sure to check out this paper:http://www.cs.joensuu.fi/sipu/pub/Threshold-JEI.pdf
pmw1234
<algorithm><image-processing>
Efficient method of mapping any RGB tuple onto a list of RGB indices, is using some kind of partition plane viable?
Water
# Efficient method of mapping any RGB tuple onto a list of RGB indices, is using some kind of partition plane viable?

(Asked by: username_0 on 2021-08-02)

Suppose we want to convert an RGB image into a paletted image. As an example, we may have a 1024x1024 image, and we want to map it onto 512 unique colors. All the colors are RGB. This is a problem of how to do this efficiently.

The naive solution would be to go over each color, find the distance from each RGB in the palette array, and then assigning a value to the closest one.

Problem is this is probably quite slow, for $n$ pixels in some 2D raster with $k$ palette indices, it's $\mathcal{O}(nk)$.

My next thought was to take a 3D volume where each axis is R, G, and B from 0 - 255, find the average of the points along one axis, partition, and recurse, sort of like how BSP trees are built. For example, I'd find the average and slice along the red axis to partition approximately half of the palette indices into two pieces. Then in the children, I'd do the same averaging for green, and slice along the green axis, and then blue, then red, etc... eventually ending up with a tree where I can walk down it from a color by doing a dot product against the dividing plane or something, and figure out whether to traverse the front or back partitions until I reach a leaf (which would be some palette index).

This is a common algorithm, I don't know the name of it but I used it in my graphics classes for generating a slicing point for AABB's for models. I figure I'd get approximately $\mathcal{O}(n \lg k)$ (under some assumptions) which would hopefully be somewhat faster. I don't know for sure since I haven't profiled but I'd hope it is.

This is my idea, but is there another, better way of doing this? Ideally I figure the partitioning idea above would give me the most performance without doing something crazy, but I am unsure if there's a better way of doing it, or if this is *the* ideal way to do it. That could be a valid answer to this question, as in, "yes you're right, that's the way you should do it." Likewise, I'm asking because I don't know if there's a better way of doing it, or if I'm doing a needlessly complex step when something I don't need to, or maybe there's a $\mathcal{O}(1)$ algorithm out there that wouldn't be too much more work. "Known unknowns" are why I'm asking.

Speed does somewhat matter here, so I'm willing to do implement something a bit more ugly if it's something noticeable, especially since there are some users of my application who don't have great computers, and anything I can do on the step that stands out for them (of which this is one of them) would be of help.

**Tags:** algorithm, image-processing

> **Comments:**
> **username_1**: Arent you getting s bit into premature optimization here. Your optimizing k and k is at most 256(?). Most likely way less while n is easily several million. So while log(k) is nice its far better to go and parallelize this. Then realize that you have a massive parallelizing tool and do it with the graphics card if speed is really of concern.  
> **username_0**: @username_1 How is it a premature optimization when profiling says its the bottleneck that people notice?  
> **username_1**: Yes but if you can do a 16 times slower code that works on a gpu then you can still be faster than the benefits of reducing K to 1  
> **username_0**: @username_1 Doing it on the GPU is a great idea IMO, but I haven't done it because the users have very archaic GPUs (as in low end hardware from the early 2000's, can barely run OpenGL 2.0). I don't even know if they have the framebuffer extension so I could write the results into a texture. Normally I'd fire this off on a compute shader and be done with it (which is what I think you mean), but dealing with ancient hardware is much more of a pain than I thought. Further I can't debug it either, whereas code run on the CPU is something I can. If there's an OpenGL 2.0 way of doing this let me know.  
> **username_2**: The answer here goes well beyond openCV (in case you haven't seen it) https://stackoverflow.com/questions/49710006/fast-color-quantization-in-opencv  
> **username_2**: Also, be sure to check out this paper:http://www.cs.joensuu.fi/sipu/pub/Threshold-JEI.pdf  

---

## 0 answers

