priaonehaha / aforge

Automatically exported from code.google.com/p/aforge
Other
0 stars 0 forks source link

Improved algorithm for Median Cut #355

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago
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 9 years ago
Here's an illustration of the problem and the improvement.

Original comment by kgould...@sasaki.com on 14 Aug 2013 at 4:51

Attachments: