Color-Space Dimension Reduction

	http://people.csail.mit.edu/jaffer/Color/CSDR
	Color-Space Dimension Reduction

Color-Name Dictionaries are 3-dimensional datasets with names. Large dictionaries, which range into the thousands of colors, are created for identifying paints or inks. Common color names (like "blue") are not used alone; but they can be components of names; some process companies assign numbers to colors. Large collections of idiosyncratic identifiers convey little meaning without their charts or samples.

The large color dictionaries available on-line do not come with charts or sample cards. This article describes a method developed for creating usable color catalogs. The 10-page charts in this article are of the Resene paint colors. Clicking on a catalog page image will fetch the 10-page PDF chart. Ignore the top left white patch on each page; it is a legend.

Organizing Colors

Trying to arrange hundreds or thousands of patches onto fixed size sheets is a daunting task. An alphabetic organization produces a visual jumble:

Alphabetical Color Chart; page 5

Trying to manually arrange hundreds or thousands of patches by color onto fixed size sheets seems a recipe for madness. Successfully mapping colors from a 3-dimensional color space to 2-dimensional sheets of paper while keeping similar colors close essentially reduces the dimension of that color space.

The straightforward method of 3-into-2 reduction is to slice the space in parallel layers, each holding the same number of colors.

After the colors are partitioned into pages, the colors are sorted by a second criterion and laid out in a serpentine pattern on the sheet; going down the first column, then up the second column, then down the third column, etc.

These sheets are sliced by the luminance (L of L*C*h), then sorted by hue (h of L*C*h):

Partition by luminance; sort by hue; page 4

Partition by luminance; sort by hue; page 5

Partition by luminance; sort by hue; page 6

If one is looking for pink, one must search both sides of several sheets to match a particular shade.

Is partitioning by hue any better?

Partition by hue; sort by luminance; page 4

Partition by hue; sort by luminance; page 5

Partition by hue; sort by luminance; page 6

The color patches don't transition smoothly across the page, and the rightmost rows are hard to distinguish from each other.

Statistical dimension reduction

Statistical dimension reduction is synonymous with data clustering. But colors in high quality dictionaries are dispersed fairly evenly through color space. Statistical methods would separate the points on the basis of quantization errors and color-space non-uniformity (all CIE color spaces are nonuniform). Charts produced this way would emphasize features irrelevant or even distracting to the catalog's intended use.

Data-independent dimension reduction

The clustering in color dictionary datasets being artifacts, can we reduce dimension by a process which is not dependent on clustering of actual color coordinates? The answer is yes; and it is very effective!

Hilbert Space-Filling Curves

	Hilbert Space-Filling Curves

A space-filling function is a parameterized function which maps a unit line segment to a curve in the unit square, cube, etc, which gets arbitrarily close to a given point in the unit cube as the parameter increases.

We want our space-filling function to preserve locality (if points are close on the line, then they are close in the cube) as much as possible. In studies such as [Bongki 2001] the Hilbert curve employed here performs well.

The inverse of the space-filling function is also well defined, taking coordinates in the unit cube and returning a number between 0 and 1. Let us order the color points by their positions on the unit line segment (as computed by the inverse space-filling function). Notice that we have reduced dimension not by 1, but by 2. The serpentine pattern described above arranges the color patches back into 2 dimensions on each sheet.

Partition and sort by Hilbert space-filling curve; page 4

Partition and sort by Hilbert space-filling curve; page 5

Partition and sort by Hilbert space-filling curve; page 6

Notice the smoothness of color transitions on the serpentine path. Near matches to a color are usually found on only one or two pages of the catalog.

This Hilbert ordering is used for the generation of all the Color-Name Dictionary catalogs.

Peano Space-Filling Curves
The results from using the Peano space-filling curve are similar but not quite as smooth as Hilbert's.

	Peano Space-Filling Curves

Partition and sort by Peano space-filling curve; page 4

Partition and sort by Peano space-filling curve; page 5

Partition and sort by Peano space-filling curve; page 6

Bibliography

[Bongki 2001]: Bongki Moon, H.V. Jagadish, Christos Faloutsos, and Joel Salz,
Analysis of the Clustering Properties of Hilbert Space-filling Curve,
IEEE Trans. on Knowledge and Data Engineering (IEEE-TKDE),
vol. 13, no. 1, pp. 124-141, Jan./Feb. 2001.

I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory. My actions and comments do not reflect in any way on MIT.
		Color
	agj @ alum.mit.edu	Go Figure!