Automatic Generation of Color Palettes

A problem I've had several times is how to automatically generate colors for use in graphs. The user will be able to select some set of items that should be included and I need to select colors for each item. The requirements are:

• The color for an item should be easy to distinguish from other items. Of course, it would also be nice if the colors looked decent, but from a functional perspective, the requirement is to be able to distinguish the items in the graph.
  
• I need to be able to generate an arbitrary number of colors and avoid a fixed color palette with a predefined number. For practical purposes the number will be limited by the ability to distinguish different colors, but it would be nice for the mechanism to scale gracefully as the number of items increases.
  
• The color of the background, for my purposes white, cannot be used.

When I examined a few tools, I found that most worked by having a fixed set of colors. My first attempt was to perform a naive increment of RGB pixel values. A trivial increment works well for shades of gray. This produces a palette like:

Hex	2	4	8	16
000000
0E0E0E
1C1C1C
2A2A2A
383838
464646
545454
626262
707070
7E7E7E
8C8C8C
9A9A9A
A8A8A8
B6B6B6
C4C4C4
D2D2D2

The problem is that grayscale can be difficult to distinguish with more than a few colors. That is why tools like gnuplot use line patterns and shapes. However, most of my use cases are for graphs shown on a color monitor so there is no need to limit to grayscale. What happens if we try a naive increment with color? My first attempt was to treat the color as a three byte integer and simply divide the desired number of colors to get the increment value. Looking at the palette below you can see the results are poor:

Hex	2	4	8	16
000000
0FFFF0
1FFFE0
2FFFD0
3FFFC0
4FFFB0
5FFFA0
6FFF90
7FFF80
8FFF70
9FFF60
AFFF50
BFFF40
CFFF30
DFFF20
EFFF10

After looking around for a bit I found that the HSV representation is fairly well suited for this problem. HSV stands for hue, saturation, and value. The color space is represented as a cylinder:

For more background the paper Color Spaces for Computer Graphics gives a good overview and discusses how the various color spaces were designed with respect to human perception of color. To generate a palette the saturation and value settings can be fixed. The 360^o for the hue can be divided by the desired number of colors and then we just increment the angle for each color. This technique gives a nice palette, but for more than around 8 colors it will be difficult for a person to distinguish some shades.

Hex	2	4	8	16
FF0000
FF5F00
FFBF00
DFFF00
7FFF00
1FFF00
00FF3F
00FF9F
00FFFF
009FFF
003FFF
1F00FF
7F00FF
DF00FF
FF00BF
FF005F

The Scala code I used for generating the palettes is shown below.

object Colors {

    import java.awt.Color

    def grayscale(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 256 - 32

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "grayscale can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color(value, value, value)
        })
    }

    def naiveIncrement(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 0xFFFFFF - 0xFF

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "naive increment can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color((value >> 16) & 0xFF, (value >> 8) & 0xFF, value & 0xFF)
        })
    }

    def hsv(num: Int): Seq[Color] = {
        // Range is 360 degrees for the hue
        val range = 360.0

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta < 1.0) {
            throw new IllegalArgumentException(
                "hsv can support at most " + range + " colors")
        }
        // Generate the sequence of colors
        (0 until num).map(n => {
            val hue = n * delta
            val h = hue / 60.0
            val x = ((1 - Math.abs(h % 2 - 1)) * 255).toInt
            val c = h match {
                case h if 0.0 <= h && h < 1.0 => (255, x, 0)
                case h if 1.0 <= h && h < 2.0 => (x, 255, 0)
                case h if 2.0 <= h && h < 3.0 => (0, 255, x)
                case h if 3.0 <= h && h < 4.0 => (0, x, 255)
                case h if 4.0 <= h && h < 5.0 => (x, 0, 255)
                case h if 5.0 <= h && h < 6.0 => (255, 0, x)
                case _ => (0, 0, 0)
            }
            new Color(c._1, c._2, c._3)
        })
    }

    def main(args: Array[String]): Unit = {
        if (args.length < 2) {
            println("Usage: scala Colors <palette> <num>")
            exit(1)
        }

        // Supported palettes
        val palettes = Map(
            "grayscale" -> grayscale _,
            "naive"     -> naiveIncrement _,
            "hsv"       -> hsv _
        )

        // Generate colors and print
        palettes(args(0))(args(1).toInt).foreach(c => {
            println(c.getRGB.toHexString.toUpperCase.substring(2))
        })
    }
}

Montana Thunderstorm

Cool photo of a supercell in Montana:

How Cats Lap

It's a bit humbling how little we know about common activities. A recent article in Science talks about how cats drink. This is a topic I have never given much thought, but it seems like something that would have been studied and understood a long time ago. It turns out it has been an open question for some time. A 1940's short film called Quicker'n a Wink captured a cat drinking using one of the earliest high speed cameras. Luckily the video is now on YouTube:



Before reading the paper or seeing the video included above, I tried to think about how lapping would work. I guessed that a cat would curve the tongue and make a cup to carry the water into the mouth. It turns out this is how dogs drink as shown in the video below:



Cats use a different technique. Like dogs they curve the tongue back, but cats barely touch the surface of the water with their tongue and then quickly withdraw the tongue letting the inertia create a stream of water into the mouth. For more information see:

• Supplementary videos for the paper
• Ed Yong's take
• Jerry Coyne's take

Jefferson Memorial: panel three contextomy

A friend on facebook recently posted the following quote attributed to Thomas Jefferson:

God who gave us life gave us liberty. Can the liberties of a nation be secure when we have removed a conviction that these liberties are the gift of God? Indeed I tremble for my country when I reflect that God is just, that his justice cannot sleep forever.

Given Jefferson's record on religion, I was curious what the context was for this quote. I quickly found that this was a truncated version of the quote from panel three of the Jefferson memorial. The full quote is:

God who gave us life gave us liberty. Can the liberties of a nation be secure when we have removed a conviction that these liberties are the gift of God? Indeed I tremble for my country when I reflect that God is just, that his justice cannot sleep forever. Commerce between master and slave is despotism. Nothing is more certainly written in the book of fate than that these people are to be free. Establish a law for educating the common people. This it is the business of the state and on a general plan.

However, what I found really surprising was how this quote was created. It was created by taking snippets from 5 different documents authored by Jefferson including: A Summary View of the Rights of British America, Notes on the State of Virginia Query XVIII, Jefferson's Autobiography, a letter to George Wythe, and a letter to George Washington (toward the bottom of image 21, though the snippet is often shown as a quote I couldn't find a text version of the full letter so I linked to the scanned version from the Library of Congress). The other panels do not seem to be quite as bad, but are also quote mined from various sources.

Why? Quote mining to come up with some new statement doesn't serve as a memorial to Jefferson or his ideas. I could comb through his writings and combine a collection of snippets to express just about any view. It's possible he would have agreed with the sentiment, but the actual statement only reflects the views of whomever cobbled it together. Truly disappointing.

Apocalypse in 2012! Wait, shouldn't it be 4772?

After quickly losing interest in the movie 2012, I found myself reading about some of the claims for the 2012 phenomenon instead of paying attention to the film. For me the most interesting part was learning more about the Mayan long count calendar. The long count works in a similar way to Unix time in that it is a count from a fixed starting point known as the epoch. Unix time counts the number of seconds since January 1, 1970. The Mayan system counts the number of days since August 11, 3114 BCE.

I had always been under the impression that the 2012 fears were because it represented the end of the Mayan calendar. It turns out this isn't true. Some do seem to think it is the end of the calendar, but others just describe it as the end of a period. It is true that on December 21, 2012 the most significant digit, called the b'ak'tun, will increase by one and the least significant digits will be zero just like hitting 100,000 miles on the odometer of a car. Regardless of whether they think it is the end of the calendar or just of a given cycle, many do go on to claim the date represents the time when some catastrophic event will occur such as galactic alignment, solar flares causing geomagnetic reversal, Nibiru crashing into Earth, etc. Insane nonsense aside, the interesting thing to me was there is an overflow problem with the way the Mayan calendar, at least as I saw it described on Wikipedia, represents dates. Considering the recent problems with overflow such as Y2K and the coming year 2038 problem the obvious question is when will it overflow?

Overflow occurs because of limits in how the values are represented. For Y2K the problem was that many systems used two digits to represent the year. So the year 1900 would be recorded as "00" and 1970 would be recorded as "70". The problem is then how do you represent the year 2000? For Unix systems the time is typically stored as a signed 32-bit integer value. With one bit used for the sign, this means that there are 31-bits for the value to represent the number of seconds since the epoch. Do the math and you find: 231 / (60 s/min * 60 min/hr * 24 hr/day * 365.25 day/yr) = 68.05 years. With an epoch of January 1, 1970 the overflow will occur in 2038.

So how are Mayan dates represented? The Mayan date is represented with five digits. Each digit is base 20, except for the middle digit that is base 18. The Mayan's had symbols for representing quantities from 0 to 19, similar to how we use 0 to 9 with the decimal system. Do the math and you find that the Mayan encoding can represent 2,880,000 distinct values. As mentioned earlier it was used to count the number of days since the epoch of August 11, 3114 BCE. Using 365.25 days per year the encoding will overflow after around 7885 years, on October 13, 4772 CE. For the purposes of media fear mongering I suppose the more imminent date is useful, but you would think for a movie they could exploit interesting aspects of the actual calendar system for the plot. Of course, with my particular proposal you would have to find some reason why the date rolling over and going back to zero in a calendaring system that nobody uses would cause harm.

The Poetry of Science: Richard Dawkins and Neil deGrasse Tyson

Happy Birthday C++

Twenty-five years ago today the first reference guide for C++ was published. Wired has an interview with Bjarne Stroustrup to celebrate the occasion. C++ was the programming language I was taught in high school and was the first language I learned for programming a desktop computer. On an irrelevant tangent, the first programming language that I learned was UserRPL for the HP 48G calculator. I competed in UIL calculator competitions using the HP 32SII and became addicted to RPN making most other calculators unusable. That and my focus on engineering in college made the HP 48G a natural choice when I needed a graphing calculator. As it turns out, one of my first C++ programs was a simple calculator that accepted a postfix expression as input (much easier than processing infix expressions).