search

ksubileau / color-thief-php

Grabs the dominant color or a representative color palette from an image. Uses PHP and GD, Imagick or Gmagick.
MIT License
632 stars 64 forks source link

Simplify color storage to always use 8 bits per color. #42

Closed mreiden closed 5 years ago

mreiden commented 5 years ago

It doesn't save memory to use fewer bits since they're stored as integers anyway. Zero the least significant bits (keep 5 most significant bits) for everything other than pixelArray. I found it confusing to get the original color back where you needed to know to shift things by the least significant bits dropped.

This way you decide how many significant bits to keep when calling getColorIndex and don't need to remember when you want the colors back via getColorsFromIndex.

ksubileau commented 5 years ago

This is certainly coming from the original JS implementation, but indeed you're right, this doesn't save memory. Your changes seem OK, but strangely the CI doesn't seem to like it. I tried to restart it but no changes. Could you have a look at this please ?

mreiden commented 5 years ago

So after getting into this, it seems like storing the histogram buckets as 5 bits is the cleaner approach since there are many places that need to convert to bucket indexes. The cleaner approach is to use the 15 bit combined bucket index when creating the histogram.

I do think there is a bug in how the 15 bit indexes are created for these histogram buckets, but I honestly still haven't figured out how it's actually working. The bits in the index created for RGB 255,255,255 seem like it should be 15 1s, but even the test confuses me as it tests against 269535 which is 01000 00111 00110 11111 in binary. Maybe since these are histogram bucket indexes it just works if it's done the same way everywhere even if it seems incorrect to me.

I'm about to add another request where 255,255,255 ends up as 32767 which is 11111 11111 11111 in binary which looks correct to me. I've added some tests too.

mreiden commented 5 years ago

The two failing tests fail because a single RGB value is off by 1 in several buckets.

ksubileau commented 5 years ago

Thank you for your work! FYI, this library was created several years ago simply by converting the code of the original Javascript library, and honestly, I don't remember the details of the core algorithm today. So I need to take some time to get back into this in depth to be able to give a you a relevant feedback. I'll try to do it shortly.

About the tests failing because of a difference of 1, I have already encountered this situation previously and I thought to add a tolerance on the tests, but I think that as the algorithm is deterministic, normally this should not happen... In fact I never really take time to try to understand why this happen.

I seen you also submit a new PR #43 with some common changes, does it supersedes this one ?