Tuesday, September 18, 2012


One of the odd bits in graphics are some of the functions being consistently lossy. One might well think that blur and sharpen are polar opposites of each other, that one could somehow apply a blur and then unblur it. But, that's not really true. The way the functions work is by applying a specific convolution to every pixel. For example a box blur is: .1, .1, .1 .1, .1, .1 .1, .1, .1 It has 9 parts and each of those parts is divided up and dispersed to the adjacent pixels. So it averages the color there with all the colors of the colors next to it to arrive at the new color for the pixel. The sharpen function: -0.1, -0.1f, -0.1, -0.1, 1.8, -0.1, -0.1, -0.1, -0.1 Which is to say the center pixel is made 80% brighter and all the adjacent pixels lose ten percent of that pixel's color. The functions do not need to add up to 1, but if they don't the image either gets brighter or darker overall. This is sort of the inverse of the former except that because of spreading it can well lose detail as the color migrates around.

 Using this original image.

Let's see a couple things.   Sharpened.

Sharpened and Blurred

As a fun quirk, I tried to solve the image for blurring. Finding an image which would best look like the original image after being blurred. Which is, I believe, going to be an np problem. As one path precludes other paths, and your likely going to run through the problem with some approximation. In fact, it might be possible to apply such an algorithm to a color quantized image sans blurring with implied blur and render images which are data sparse and solvable to something approximating the original image. Like a blur-implied gif image. The anti-blurred image approximation (finding the optimal might well be np-impossible, or rather knowing that it's the optimal when you have it).

Anti-Blurred Image Blurred

 When we apply a box blur to the image we get the above.

There may be some merit to the idea, but it might need some better encoding methods. As is this takes the same amount of data to display the blur-implied image than the original image. But, it may well have some methods therein to allow for pretty effective color mixing from a reduced subset of colors.

Thursday, September 13, 2012

Thomas Babington Macaulay (Quotes)

To every man upon this earth
Death cometh soon or late.
And how can man die better
Than facing fearful odds,
For the ashes of his fathers,
And the temples of his gods?
Horatius, st. 27.

Thursday, September 6, 2012

Color Distribution Methodology

Getting independent colors which are maximally dissimilar from all previous colors is a fairly common problem. The standard suggested algorithm is to subdivide the most significant differences in colors and then pattern them. I thought this was the case too. So much so that I solved the problem because I thought it would be very useful (and it might). Generally this required two minor breakthroughs understanding how to encode maximally significant differences in colors through binary (flip the ends), which I went through a lot of struggle to get to including my anti-gray codes and derivation algorithm and proof (intersperced gray codes with an additional zero anywhere in it and flipped will maximize hamming distance). And secondly understanding the patterning such that I could derive any value without iteration of the previous values.

Well, looking at the results, it quickly seems that they aren't that great.

Largely there are issues with greens being pretty close even when their RGB values are far, and the patterns constantly making what turn out to be slight variations of your standard pure colors RGB and CYM. You start clashing rather quickly.

The better solution is computationally much more difficult. And generally sort of cheating. You do the hard work. You run through every color you can represent in RGB (16,77,216 of them) and run a heavy duty color distance routine, likely CIE-Lab 2000, then you go in there and manually choose the colors. And then use this as a master list and just read from the list. The standard solution starts picking some greens that look pretty much like the previous greens after like 20. And you should be able to get like 50 colors or so which are visually distinct from one another. Perhaps with pruning of the list by hand.

Using 20k guesses (rather than brute forcing 16-million) I produced this after an hour or so.

There's likely not much left to gain brute forcing the algorithm, but I did (for a smaller value 64) and came out with this.

Which manages to out perform the heck out of the dividing algorithm and could just be read by a standard list. There might be some enhancements to be achieved by converting away from finding maximally good results initially which may cost the overall result to become pareto optimal. Or employ something like k-mean clustering in LabDE2000 colorspace (not really defined as a colorspace but pretty much is exactly that) to better maximize the list. Or goodness forbid collect data by humans voting (it's how the color spaces came about, that and math to approximate that data). Although, this would need to be done in somewhat controlled systems because human eyes are excessively sensitive to conditions. Some colors look similar on a black background when they wouldn't on a white background. Which could maybe be randomized to average out or find colors that do this less than others. It wouldn't be too hard to define a list or two which specifically address this question, because programmatically the question of which colors seem very distinct from a set of previously distinct colors has nothing really to do with computers but humans and how they perceive color, and the ability to approximate this has everything to do with humans and not that much to do with programming.

Observations which have been noted before.

There are some good color dictionaries out there. But, I'm not convinced there are much more optimal solutions. And it turns out the algorithms needed are much better at making color dictionaries than they would be generating colors on the fly. And since we're dealing with 64 colors max, we're much better doing that.

Tuesday, September 4, 2012

Color Space Comparisons.

So which color space is best.

Using a list of 9413  0 <= R,G,B <= 255, Step 15 colors (17³). And the orange from the Blogger icon. I sorted a bunch of 4x4 boxes for a large variety of color spaces. The diagrams are read left to right top to bottom. The first color is the index color. And the point is to have the colors very similar to that color closer to it. And try to avoid having any colors close to that color further away or very dissimilar colors further. This is a bit hard to figure out but you can generally eyeball it. The top should be the matching colors. You shouldn't have very similar colors to that strewn about the diagram.

The boxes are 70x70 which is 1400,  - 1 for the index color. This means 14 of the most different colors will not be shown.

Addative color. Don't think Euclidean is the simplest distance. I literally took the value distances of the R, G, B, added them up and called that a distance.

Euclidean Distance RGB
Sqrt(R² + G³ +  B²)


            long rmean = ( (long)r1 + (long)r2 ) / 2;
            long r = (long)r1 - (long)r2;
            long g = (long)g1 - (long)g2;
            long b = (long)b1 - (long)b2;
            return Math.sqrt((((512+rmean)*r*r)>>8) + 4*g*g + (((767-rmean)*b*b)>>8));

Given at:

Which is actually a pretty great article.

Luv, Standard Euclidean
The Redmean page says it gives pretty close to Luv colorspace with much less programming power needed. So here's Luv. Luminescence u, v.

Lab, Delta E (standard Euclidean distance)
sqrt(L² + a² + b²)

Lab, Delta 94
Same Lab color space, but rather than a standard Euclidean Color distance the good folks at CIE in 1994 decided to go ahead and tweak it a bit.

Lab, Delta E 2000, CIEDE2000

Using the reworked tweaked distance formula from 2000. I actually like quite a lot. It's my personal favorite and seems to give very consistent results. And consistently good results.

Lab Delta CMC
Intended for threads, paints, dyes, etc. It's the standard for that industry. Apparently you're much better off with a color to dye something than no color. Which is maybe why everything with no color is basically at the bottom, maximally far away from colors with saturation.

Hunter Lab, it uses the XYZ color space (which LAB also uses) and uses a different way to get the L,a,b values. Which are luminescence and some complementary colors.

HSL. You can't just plop this into a Euclidean distance formula you need to make a shape and get the distance within that shape. Anything with a hue, must have this done. Because H=360° and H=0° are not polar opposites, they are the same color. They should be in the same place not 360² away from each other.

In this case, I have some old code and it's wrapped up in a two stuck together half cone. Which is to say that it's a cone where the L value ends half way at the cone, and has maximal colors at L = 0.5.


Using value rather than lightness Placed into a cone.

        double X = S*V*Math.cos(H);
        double Y = S*V*Math.sin(H);
        double Z = V;

Directly invokes the HSB routine from Java's Color.RGBtoHSV() routine.

HCL: M. Sarifuddin and Rokia Missaoui
I just wrote a very long article dissing this color space. Mostly because it's ill defined and claims to be better than it is through methodological flaws. And I dunno what else.

Weighted Euclidean: 22,43,35
About this time last year, I wrote a blog post where I ran all the numbers for Delta E, Lab. And averaged the distances based on the specific colors and came up with these weights. Also noting the Compuphase paper got similar results. There are standard given weights but these are actually for Gamma. They are the weights as to how much that color contributes to how bright the color looks. 30,59,11 are correct weights here, blue contributes very little to how bright a color seems. In fact, anti-blue (yellow) is wildly bright like bizarrely so. You can't even read yellow text on a white background.

Weighted Euclidean: 30,59,11
We're dealing with Orange (specifically Blogger Icon Orange). So the huge over emphasis on red is going to make it cluster like this but, let's check out a couple other colors with similar weights.

Weighted Euclidean: 22,43,35

Weighted Euclidean: 30,59,11

Weighted Euclidean: 22,43,35

Weighted Euclidean: 30,59,11
The weighting here is very anti-blue. As a result bluish colors  get tossed all over the place.

The blue here is Google Icon blue (66,133,244).

 Lab Delta 2000, Green
For Reference.
Lab Delta 2000, Google Blue
For Reference

Hopefully we should have a better idea about color spaces and which ones may or may not be good or bad. And a pretty firm grasp on the weighted Euclidean weights for color distance being wrong. Those are fine weight when we're looking for gamma, but how bright we see colors is different than how discriminating we are between colors. You are much better with 2,4,3 than that 30,59,11 crap. Or a much better color distance formula.

HCL: a new Color Space for a pack of lies.

HCL: a new Color Space for a more Effective
Content-based Image Retrieval
M. Sarifuddin and Rokia Missaoui







 Lab Delta 2000.

 Lab Delta 1994

Lab Delta Euclidean

Hunter Lab


RGB Delta Euclidean


And Finally....

Drumroll please


Oh, did I mention the hue formula is wrong?

            H = 2 * H / 3;
            H = 4 * H / 3;
            H = 180 + 4 * H / 3;
            H = 2 * H / 3 - 180;



if (gb > 0) H += 180;

rather than,

if (rg > 0) H += 180;

Though in the equations this is done to preserve the sign.







Sunday, September 2, 2012

Color Distribution Code.

So final draft:
    public Color getColor(int i) {
        return new Color(getRGB(i));

    public int getRGB(int index) {
        int[] p = getPattern(index);
        return getElement(p[0]) << 16 | getElement(p[1]) << 8 | getElement(p[2]);

    public int getElement(int index) {
        int value = index - 1;
        int v = 0;
            v = v | (value & 1);
            v <<= 1;
            value >>= 1;
        v >>= 1;
        return v & 0xFF;

    public int[] getPattern(int index) {
        int n = (int)Math.cbrt(index);
        index -= (n*n*n);
        int[] p = new int[3];
        if (index == 0) {
            return p;
        int v = index % 3;
        index = index / 3;
        if (index < n) {
            p[v] = index % n;
            return p;
        index -= n;
        p[v      ] = index / n;
        p[++v % 3] = index % n;
        return p;

The first 729 (9^3) colors displayed in a 27x27 cube.

Color Distribution sans recursion.

I did a bit of math and got rid of the recursive section.

    public int[] getPattern(int index) {
        int n = (int)Math.cbrt(index);
        index -= (n*n*n);
        int[] p = new int[3];
        if (index == 0) {
            return p;
        int v = index % 3;
        index = index / 3;
        if (index < n) {
            p[v] = index % n;
            return p;
        index -= n;
        p[v      ] = index / n;
        return p;
Turns out you can calculate N without iterating the whole thing, but by rather taking the cube root or the index. Which makes sense if you consider all the previous patterns with characters from 0-(N-1)  would take N*N*N space to use up and we by definition used that up.