4 ms·

This does not actually brute force the entire search space - the search space for all possible palettes is 2¹⁹² palettes, 16 times 12 bit, modulo 16! permutatio

This does not actually brute force the entire search space - the search space for all possible palettes is 2¹⁹² palettes, 16 times 12 bit, modulo 16! permutations and some other things like repeated colors. The algorithm described performs a greedy search picking the best fit for each palette entry in turns but it is at the very least not obvious that this will yield the optimal solution - maybe picking a suboptimal color for the first palette entry will allow a better fit later than picking the optimal color for the first palette entry. The same applies for choosing the color of the next pixel - it could be possible that making one pixel worse might allow subsequent pixel to be approximated better. Which then also leads to the choice of the error function - what is better, many medium deviation or many small deviation plus some big deviations? Without careful analysis it is really hard to tell, at least for me, how a greedy approach compares to the optimal solution, but I would guess that one gets pretty close but I do not think that one is guaranteed to find the optimal solution. I would also guess that one could create pathological cases where the greedy approach produces surprisingly bad results.

kzrdude 4y ago
Scale down the problem and analyze it that way if one still wants to play with brute force. Smaller image and smaller palette. See what can be learned.
vanderZwan 4y ago
> The same applies for choosing the color of the next pixel - it could be possible that making one pixel worse might allow subsequent pixel to be approximated better. I was thinking the same thing: what if we looked at the next two pixels and tried to find the values that minimized total error. If done right that should essentially give horizontal 2x1 dithering for free.
- danbruc 4y ago
  The entire thing is essentially already a threshold dithering process, pick the closest available color and throw away the error. So one could certainly extend this to a more sophisticated dithering process and maybe even get rid of the first dithering process from 24 bit to 12 bit and do it all in one go. This also made me realize that there is no good reason why the author is iterating through all red, green and blue values, one could just compute the closest ones.
  - vanderZwan 4y ago
    Huh, that's a really good point: wouldn't using a simple error diffusion dither give decent results here? We basically have 16 palette colors, plus three individual channel-delta ones, so all we have to do is check which of our nineteen options has the lowest error, instead of the normal threshold approach.
    - danbruc 4y ago
      The thing is, you do not have the palette in advance, that is kind of the main point of the article. As the author says, one could build a palette in advance, but it is not clear that one of the common algorithms for that would yield a really good one as they look at the entire image but in this case we mostly need colors for strong edges that are not handled well by the HAM encoding. So maybe a good solution would be to first only use HAM and record all the errors, the build a palette that reduces those errors as much as possible, and then encode it again with HAM and the palette. The thing is of course that the errors propagate with HAM as you can always only adjust one channel and so any change to a pixel will or at least might also affect errors of subsequent pixels. On top of that you might have error propagation from a dithering algorithm. But I think here I have reached the limit of my reasoning capability without having to pull out pen and paper and really digging into it. Final note, I would probably try to find a iterative algorithm that tries to reduces the error in several iterations as I think jumping directly to the best solution is probably pretty hard.

kzrdude 4y ago

Scale down the problem and analyze it that way if one still wants to play with brute force. Smaller image and smaller palette. See what can be learned.

vanderZwan 4y ago

> The same applies for choosing the color of the next pixel - it could be possible that making one pixel worse might allow subsequent pixel to be approximated better. I was thinking the same thing: what if we looked at the next two pixels and tried to find the values that minimized total error. If done right that should essentially give horizontal 2x1 dithering for free.

danbruc 4y ago
The entire thing is essentially already a threshold dithering process, pick the closest available color and throw away the error. So one could certainly extend this to a more sophisticated dithering process and maybe even get rid of the first dithering process from 24 bit to 12 bit and do it all in one go. This also made me realize that there is no good reason why the author is iterating through all red, green and blue values, one could just compute the closest ones.
- vanderZwan 4y ago
  Huh, that's a really good point: wouldn't using a simple error diffusion dither give decent results here? We basically have 16 palette colors, plus three individual channel-delta ones, so all we have to do is check which of our nineteen options has the lowest error, instead of the normal threshold approach.
  - danbruc 4y ago
    The thing is, you do not have the palette in advance, that is kind of the main point of the article. As the author says, one could build a palette in advance, but it is not clear that one of the common algorithms for that would yield a really good one as they look at the entire image but in this case we mostly need colors for strong edges that are not handled well by the HAM encoding. So maybe a good solution would be to first only use HAM and record all the errors, the build a palette that reduces those errors as much as possible, and then encode it again with HAM and the palette. The thing is of course that the errors propagate with HAM as you can always only adjust one channel and so any change to a pixel will or at least might also affect errors of subsequent pixels. On top of that you might have error propagation from a dithering algorithm. But I think here I have reached the limit of my reasoning capability without having to pull out pen and paper and really digging into it. Final note, I would probably try to find a iterative algorithm that tries to reduces the error in several iterations as I think jumping directly to the best solution is probably pretty hard.