Improved algorithm for Median Cut
Opened this issue · 1 comments
GoogleCodeExporter commented
Describe the feature you are interested and which may bring benefit to the
project ...
I recently found the need to make a small improvement to the MedianCutQuantizer
that seems to dramatically improve the color groupings when dealing with small
groups (i.e. when original colors / palette colors = a small number).
The original algorithm simply splits cubes one after the other. This may work
well for trimming large color sets into much smaller ones, but in our case, we
are sometimes trimming 80 colors down to 70. The danger is that you can get
remaining groups that contain very different colors. So if you have e.g. grey
and red remaining in that cube, both will show as a pinkish color and other
groups may contain very similar colors. Ideally you would want red and grey to
have their own cubes and group the similar colors in another cube.
Provide any references/links to publications/algorithms/etc. which could
help in development ...
The improvement is to be a bit more judicious about the choice of the next cube
to split. We just sort the cubes each time based on the sum of their R, G & B
sizes in order to pick the next cube that contains the largest color
discrepancy across all its colors.
See the attached files with the following changes:
MedianCutCube: Added CubeSize property which is simply the sum of RedSize ,
GreenSize and BlueSize.
MedianCutQuantizer: Added SortCubesBySize method and modified SplitCubes.
For very large color sets, this modification could slow the algorithm down (as
it re-sorts the list of cubes with each iteration). It may make more sense to
provide this as an option rather than replacing the current algorithm entirely
as we have done.
Original issue reported on code.google.com by kgould...@sasaki.com on 14 Aug 2013 at 4:08
Attachments:
GoogleCodeExporter commented
Here's an illustration of the problem and the improvement.
Original comment by kgould...@sasaki.com on 14 Aug 2013 at 4:51
Attachments: