Motivation
Color Space Dimension Reduction
explores methods of dimension reduction, focusing on spacefilling
curves. For the purpose of presenting colors for selection, the
spacefilling curve attributed to Hilbert seems to perform better than
the curve due to Peano. Can that difference be quantified?
The goal of dimension reduction is to find a mapping from a
higherdimensional space to a lowerdimensional space where points
which are close in the higherdimensional space map to points which
are close in the other space.
Apparatus
 20090610 Development version of SCM 5e5
 20090610 Development version of SLIB 3b1
 Scheme program closeness.scm
 the "convert" program, part of ImageMagick6.3.2
Procedure

scm l closeness.scm
 Graphs are written in the working directory:
 "Zcurver.png"
 Graph of Euclideandistance /
scalardistance versus the scalardistance between two points
for the Zcurve in 2, 3, 4, and 6 dimensions.
 "Zcurvel.png"
 Graph of the logarithm of
Euclideandistance versus the logarithm of the scalardistance
between two points for the Zcurve in 2, 3, 4, and 6 dimensions.
 "Peanor.png"
 Graph of Euclideandistance /
scalardistance versus the scalardistance between two points for
the Peano spacefilling curve in 2, 3, 4, and 6 dimensions.
 "Peanol.png"
 Graph of the logarithm of
Euclideandistance versus the logarithm of the scalardistance
between two points for the Peano spacefilling curve in 2, 3, 4, and
6 dimensions.
 "Hilbertr.png"
 Graph of Euclideandistance /
scalardistance versus the scalardistance between two points for
the Hilbert spacefilling curve in 2, 3, 4, and 6 dimensions.
 "Hilbertl.png"
 Graph of the logarithm of
Euclideandistance versus the logarithm of the scalardistance
between two points for the Hilbert spacefilling curve in 2, 3, 4,
and 6 dimensions.
Method
 The closeness.scm program fills an
array with the multidimensional coordinates corresponding to 4096
(or 729 for Peano curves) successive integers.
 For a given dimension it then computes, for each scalardistance
from 1 to 15, the average ratio of Euclideandistance to the
scalardistance for all pairs of points having that scalar
separation.
 The resulting graphs are written to graphic files:
 "Zcurver.png"
 "Peanor.png"
 "Hilbertr.png"
 For a given dimension it then computes, for each scalardistance
from 1 to 100, the logarithm of the average Euclideandistance for
all pairs of points having that scalar separation.
 The resulting graphs are written to graphic files:
 "Zcurvel.png"
 "Peanol.png"
 "Hilbertl.png"
Measurements
Analysis
The Zcurve has
the widest spread and is particularly poor in 2dimensions (the top
plot). Worse still is that most unit length scalar edges map to
coordinates which are more than one unit separated. Thus the average
displacement for unit edges averages above 1.6 for 2dimensions and
above 1.35 for the other ranks.
The ratios for all three functions quickly approach their low,
asymptotic values as the rank is increased. For the Peano and Hilbert
curves the traces for ranks 6 and 9 are coincident.
The spacefilling curve attributed to
Peano maps scalar unit lengths to unit Euclidean lengths, giving
optimal behavior for the shortest length. In fact all horizontal
segments are exactly unit length. The vertical segments run 2 and 5
units; raising the averages in that range.
The spacefilling curve attributed to
Hilbert edges out the Peano curve to have the best performance of
those measured.
ColorSpace Dimension
Reduction also finds the Hilbert curve (slightly) better
than Peano's.
And [Bongki 2001]
rates it best as well.
Logarithmic Measurements
Plotting the (logarithm of) average Euclideandistance versus the
(logarithm of) scalardistance out to longer distances seems to
indicate that the roughness of the high rank curves does not become
smooth asymptotically.
Copyright © 2005, 2009 Aubrey Jaffer
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.

  Computer Natural Science

 agj @ alum.mit.edu
 Go Figure!
