maybe a bug of prepare_sort function in mediancut.c

[zlucode]

prepare_sort function in mediancut.c:

       qsort(channels, 4, sizeof(channels[0]), comparevariance);
....
        // Only the first channel really matters. When trying median cut many times
        // with different histogram weights, I don't want sort randomness to influence outcome.
        tmp = ((unsigned int)(chans[channels[0].chan]*65535.0)<<16) |
                                        (unsigned int)((chans[channels[2].chan] + 
                                        chans[channels[1].chan]/2.0 + 
                                        chans[channels[3].chan]/4.0)*65535.0);

After qsort operation to channels, the variance should be like this : channels array[0] >[1]>[2]>[3]. and from the comment it says " the first channel really matters." I think the weight here is about the variance. so the weight should be like :array[0] >[1]>[2]>[3]. and the first <<16 could amply it's importance, and the least /4.0 makes it does not important.

So I think the code here should be like below, isn't it ?

        tmp = ((unsigned int)(chans[channels[0].chan]*65535.0)<<16) |
                                        (unsigned int)((chans[channels[1].chan] +  //[2]-->1 
                                        chans[channels[2].chan]/2.0 +   //[1]-->2
                                        chans[channels[3].chan]/4.0)*65535.0);

If not ,could you tell me why the code snippet is like original version?

thanks Lu

[kornelski]

Good find! It's one of these cases I've just randomly tweaked until it improved my DSSIM benchmark, but I don't know why it works :D

It's likely that only sorting by the first channel matters, and the rest is noise. Or perhaps sorting by most variance, then little variance, separates colors in some useful way. I haven't checked.

[zlucode]

Hi kornelski,

thanks for your explanation! And forgive me to ask 2 more question , both about some magic number. (1) in box_variance(), mediacut.c:

   result.a = variancea*(4.0/16.0);    // why * (4.0/16.0)
    result.r = variancer*(7.0/16.0);    //why * (7.0/16.0)
    result.g = varianceg*(9.0/16.0);// ..
    result.b = varianceb*(5.0/16.0);// ..

if we are getting "variance", we should be like this:

    result.a = variancea*(sum_of_all_adjusted_weight);
    result.r = variancer* (sum_of_all_adjusted_weight); 
   (etc..)

anyway, I cannot figure out why using 4.0/16.0, 7.0/16.0 ... ?

(2) in nearest_init(), nearest.c:

handle->nearest_other_color_dist[i] = best.distance * best.distance / 4.0; // half of squared distance 

actually "best.distance" is a sqrt distance. and nearest_other_color_dist[i] should be "power(best.distance , 2)/4".

It will be compared to guess_diff in nearest_search(). while guess_diff is a distance that is NOT sqrt. So I think if you want to compare it to guess_diff, you should set nearest_other_color_dist[i] to a distance value NOT be sqrt. that is: "best.distance * best.distance". but why let nearest_other_color_dist[i]= ../4.0 here? why 4.0 ?

there are several places using magic number like this , I picked out two above , hope you can help me to understand more about this cool project.

B.R. Lu

[kornelski]

In box_variance() I think I've tried to make it more perceptual, but when I used coefficients that are usually used for color to gray conversion (where green dominates, red is smaller, blue is tiny), the "correct" coefficients didn't work as expected, so I tweaked it to be only a slight adjustment.

[kornelski]

The second is mathematical identity:

(x/2)^2 = x*x / 4