ANIMAPS III: COLOR STRAWS, COLOR VOXELS, AND COLOR RAMPS
Sandra L. Arlinghaus
The University of Michigan
and
William C. Arlinghaus
Lawrence Technological University

BACKGROUND

    Background is important not only in color visualization but also in fostering a deep understanding of a variety of abstract concepts. One place to begin any background study of color is with the four-color problem (now, "theorem;" Appel and Haken, 1976). For centuries, mathematicians have concerned themselves with how many colors are necessary and sufficient to color complicated maps of many regions. (Two regions are said to be adjacent, and therefore require different colors, if and only if they share a common edge; a common vertex, alone, is not enough to force a new color.) The answer depends on the topological structure of the surface onto which the map is projected. When the map is on the surface of a torus (doughnut) seven colors are always enough. Surprisingly, perhaps, the result was known on the torus well in advance of the result for the plane (then again, the plane is unbounded and the torus is not). The same number of colors that work for the plane will also work for the sphere (viewing the plane as the sphere with one point removed). However, it was not until the last half of the twentieth century, aided by the capability of contemporary computing equipment to examine large numbers of cases, that the age-old "four color problem" became the "four color theorem." Appel and Haken (1976) showed that four colors are always enough to color any map in the plane (hence the University of Illinois postage meter stamp of "four colors suffice" announcing this giant result).

    The world of creating paper maps and publishing them has traditionally been one that is black and white: color processing is expensive and often has been prohibitive. Nonetheless, cartographers, photographers, and others have developed a number of strategies for considering color, independent of how many colors suffice to color a map in the plane. Indeed, Arthur Robinson noted (Robinson, 1960, p. 228),

"Color is without a doubt the most complex single medium with which the cartographer works. The complications arise from a number of circumstances, the major one being that even yet we do not know precisely what color is. The complexity is due to the fact that, so far as the use of color is concerned, it exists only in the eye of the observer." Like the mathematician, the cartographer, too, has significant unsolved problems associated with the concept of color.

    Thus, color choice and use is typically tailored to "standard" reactions, by a typical observer, to color. The effect of color on an observer is often captured using the following terms as primitive terms: hue, saturation, and luminosity.

In the more contemporary environment of the desktop computer, users of various software packages in common use are exposed to the hue-saturation-luminosity set of primitive terms on a regular basis. In addition, they see the RGB (Red-Green-Blue) description also using three primitive terms and the printer's (photocopier's) environment of separations into layers based on CMYK (Cyan-Magenta-Yellow-Black). A color wheel (Figure 1) can help the user to design strategies for color change: to decrease magenta, for example, subtract magenta, or add cyan and yellow (opposite from magenta).

COLOR STRAWS AND COLOR VOXELS

    One obvious way to look at color, given two sets of primitives each with three elements, is as an ordered triple in Euclidean three-space. Indeed, that is how color maps are set up in contemporary software such as Netscape, Microsoft Office, and so forth. Hue is measured across a horizontal x-axis (Figure 2) and saturation is measured along a vertical y-axis (Figure 3). The result is a square or rectangle with vertical strips of color corresponding in order to the pattern on the color wheel. A third axis of luminosity (a gray scale) is often seen as a strip to the right of this square (Figure 4). It serves to match the selected color against light/dark values.

Figure 2. Animated color map: shows change in resulting hue as one moves across the x-axis.
Figure 3. Animated color map: shows change in resulting saturation as one moves along the y-axis.
Figure 4. Animated color map: shows change in resulting luminosity as one moves along the z-axis.
These animated color maps fix two dimensions and allow a third one to vary.  That variation shows up in the small rectangle to the lower left of the color map and also in "straw" to the right of the plane region.   In all three cases, hue is the variable mapped on the horizontal axis, saturation is the variable mapped on the vertical axis, and luminosity is the variable mapped in the straw to the right.  Thus, in Figure 2, luminosity is fixed at 120 as indicated by the small arrow to the right of the straw.  Saturation is fixed at 180 along the left side of the rectangle.  Only hue is allowed to vary, as shown in the progression of the crosshair movement.  The small rectangle to the lower left of the color map changes in color to show the hue of the current position of the crosshair.   Thus, to see a hue-straw, one would need to take all 256 colors available in the flashing rectangle and stack them up in order of progression.  Similarly, one can allow saturation to vary and keep hue and luminosity fixed (Figure 3).  When luminosity is once again fixed at 120, and hue at 180, a structurally identical situation occurs (to that above).  To see a saturation-straw, one would need to take all 256 colors available in the flashing rectangle and stack them up in order of progression.  The final case, in Figure 4, keeps hue and saturation fixed and allows luminosity to vary.  Thus, one imagines a point in the base hue/luminosity plane fixed at (180, 120) and variable height shown in the luminosity straw reflecting changes in the single color-point as one alters luminosity.  In this latter case, the obvious straw that appears is in fact the actual luminosity straw sought.  In two cases, there is no evident straw of color and in the third there is; visualization is not impossible but it is made difficult.
     An alternate way to visualize all of this is to think of a cube (in 3-space) of 256 units on a side.  Label the x-axis as hue, the y-axis as saturation, and the z-axis as luminosity.  Then, draw a plane parallel to the base plane (bottom of the cube) at height 120.    Fix lines at 180 within that plane:  one with hue=180 and one with saturation=180.  These two lines trace the paths of the crosshairs, respectively, in Figures 2 and 3.  What the cube approach also shows clearly is that there are really a set of voxels (volume pixels) making up the cube:  there are 256 straws available for each of the three variables.  Since 256=2^8, there are therefore 2^8 * 2^8 * 2^8 = 2^24 = 16,777,216 voxels within the color cube (note the reliance on discrete mathematics and discrete structuring of a normally continuous object).
     The notion of looking only at voxel subsets within a single plane parallel to a face of the cube is limiting within this large, but finite, set of possibilities.  In choosing sequences of color there may well be reason to follow a diagonal, to tip a plane, or to find various other ways of selecting subsets of color, as a smoothed color ramp, from this vast array.  It is to these possibilities that we now turn.

COLOR RAMPS:  ALTERNATE METRICS
      The problem of finding color ramps linking one color to another can be captured simply as follows.  To find a ramp joining two colors, A and B, first represent each of A and B as an ordered triple in color voxel space.  Then, the problem becomes one of find a path from A to B.  Because one is limited to integer-only arithmetic, divisibility of distances often will not be precise; thus, one is thrown from the continuous realm of the Euclidean metric into considering the non-Euclidean realm of the Manhattan metric (of square pixel/cubic voxel space).  Algorithms for finding shortest paths between two arbitrary points using integer-only arithmetic will therefore apply to colors mapped in color space as well as to physical locations mapped on city grids.  To see how these ideas might play out with colors, we consider an example that will lead to an animated color ramp.

Find a path through color voxel space from (80, 100, 120), shown below as a medium green

to (200, 160, 60), shown below as a fairly deep purple.

One set of points through which to pass, spaced evenly (not always possible), is given in the table below.  The left-hand column shows values of hue, the middle column values of saturation, and the right-hand column values of luminosity.
 

80 100 120
90 105 115
100 110 110
110 115 105
120 120 100
130 125 95
140 130 90
150 135 85
180 140 80
170 145 75
180 150 70
190 155 65
200 160 60

Figure 5 shows an animation using the path outlined in the table above.  The crosshairs show the movement along the path while the flashing color in the rectangle below the color map shows the associated color ramp.  Clearly, the choice of path is not unique:  geodesics are not unique in Manhattan space.  From this analysis, we see that the following theorem will hold.



Theorem.
The determination of color ramps joining two colors is abstractly equivalent to finding paths in Manhattan space between two arbitrary points (where geodesics are not unique).

    One might wonder what would happen when other color characterization schemes are considered.  We suspect that a similar analysis will follow.  For, in a related, but not identical, manner the RGB scheme may also be represented as describing color using 3-space. In that scheme, the gray scale comes out as a 45 degree diagonal. Computer scientists offer a color code containing six alpha-numeric characters, appearing in pairs of hexadecimal code that also serve as a 3-space. Generally, though, the various schemes offer only visual slices through this three-dimensional color space along axes or in other "expected" ways. Different vantage points offer different perspectives, however. Pantone color formula guide books offer one physical set of straws by which to probe 3D color space. The theorem above offers a comprehensive mathematical set.


REFERENCES

Appel, K., and Haken, W. A proof of the 4-color theorem. Discrete Mathematics, 16, 1976, no. 2 (and related references).

Arthur H. Robinson, Elements of Cartography, 2nd Edition, 1960. New York: Wiley.

RELATED LITERATURE
Sandra L. Arlinghaus, William C. Arlinghaus, John D. Nystuen.  The Hedetniemi Matrix Sum:  An Algorithm for Shortest Path and Shortest Distance, Geographical Analysis, Vol. 22, #4, Oct. 1990, pp. 351-360.

Sandra L. Arlinghaus, William C. Arlinghaus, John D. Nystuen.  The Hedetniemi Matrix Sum:  A Real-world Application, Solstice, Vol. I, No. 2, 1990.  http://www.imagenet.org

Sandra L. Arlinghaus, William C. Arlinghaus, John D. Nystuen.  Discrete Mathematics and Counting Derangements in Blind Wine Tastings, Solstice, Vol. VI, #1, 1993.  http://www.imagenet.org

Sandra L. Arlinghaus, William C. Arlinghaus, Frank Harary, John D. Nystuen.  Los Angeles 1994--A Spatial Scientific Study, Solstice, Vol. V, #1, 1994. http://www.imagenet.org