Talk:Median cut algorithm (C Plus Plus)

From LiteratePrograms

Contents 1 Question 2 Strange Results 3 not always better 4 Incorrect Comparator Object

Question

Hi! I'm a new user. May I ask something about median cut, especially about the process? —Unsigned comment by Bip (talk).

Welcome, Bip. You're very likely the same person who contacted me in e-mail. This particular implementation works in the manner I described: each box contains a set of points, and each time a box is divided, exactly half the points are placed in each new box; sometimes this means each box contains some points of exactly the same color. If not, please go ahead and ask your question. :-) Deco 22:19, 8 June 2006 (PDT)

Strange Results

I'm getting strange results using this technique. When i am drawing some anti-aliased text, say in 3 colors, i'd expect the CLUT to contain variations on those three colors from black to full intensity. For example, with this image:

When I run it through the algorithm, I get this CLUT:

with this resulting image:

To prove that I incorporated the code correctly, I also ran your test image (the flower), and got this CLUT:

with this resulting image:

Do you have any ideas?

Another issue is that it seems that there is always more than one black, even if there are more colors to pick?

Davecotter 20:11, 11 September 2006 (PDT)

Hi Dave. It would appear that my error lay in putting pixels in the initial block, rather than colors. In other words, I need to perform elimination of duplicates, which is not difficult to do in roughly linear time using a std::set, particularly if runs are dealt with intelligently. I will make edits to fix this. Deco 08:20, 25 September 2006 (PDT)

not always better

I implemented your suggestion, and while it does actually make anti-aliased text look much better, it makes your test "flower" image look worse :(
Davecotter 13:39, 27 September 2006 (PDT)

Yes, after I thought about this more I realised it wasn't the correct solution - I don't know why my updates to the talk page were not saved. It's a fundamental problem of median cut that it is biased towards assigning many colours to large regions of the image. To avoid duplicate palette entries, the easiest possible solution would probably be to simply continue splitting until I get a large enough number of unique colours. Another reason that your text doesn't look very nice is that Floyd-Steinberg dithering works very poorly on this sort of image - try it without dithering. Deco 15:27, 4 October 2006 (PDT)

Incorrect Comparator Object

I found a bug in this code. It appeared when I flipped the image vertically and I got different color palette. The color palette should be the same since the content of the image was not changed. I found that the problem is with comparator object for n_th function which is used for median finding. It does not take into account the case when the coordinates are equal. I use the RGB object so according to article (the incorrect version):

//RGB Comparator
template <class T, int index>
class CoordinatePointComparator {
public:
    bool operator()(RGB<T> left, RGB<T> right) {
        switch(index) {
            case R_SIDE:
                return (left.r < right.r);
            case G_SIDE:
                return (left.g < right.g);
            case B_SIDE:
                return (left.b < right.b);
            default:
                assert(false);
        }
    }
};   

and the correct version is:

//RGB Comparator
template <class T, int index>
class CoordinatePointComparator {
public:
    bool operator()(RGB<T> left, RGB<T> right) {
        switch(index) {
            case R_SIDE:
                if (left.r < right.r);
                    return true;
                else if (left.r > right.r)
                    return false;
                else if (left.g < right.g)
                    return true;
                else if (left.g > right.g)
                    return false;
                else if (left.b < right.b)
                    return true;
                else
                    return false;
            case G_SIDE:
                if (left.g < right.g);
                    return true;
                else if (left.g > right.g)
                    return false;
                else if (left.r < right.r)
                    return true;
                else if (left.r > right.r)
                    return false;
                else if (left.b < right.b)
                    return true;
                else
                    return false;
            case B_SIDE:
                if (left.b < right.b);
                    return true;
                else if (left.b > right.b)
                    return false;
                else if (left.g < right.g)
                    return true;
                else if (left.g > right.g)
                    return false;
                else if (left.r < right.r)
                    return true;
                else
                    return false;
            default:
                assert(false);
        }
    }
};