Cryptography Reference
In-Depth Information
the United States. The Senate gets twomembers from each state and
Heckbert compares this to his algorithm. It spreads out the repre-
sentation so no part of the color space is over- or under-represented.
The House of Representatives, on the other hand, gets one represen-
tative for each unit of population. This works well if you're fromheav-
ily populated areas like Manhattan. These have representatives for
each part of town. Western states like Nevada, however, have only
one representative and thus have little power in the House. Heckbert
compares this approach to the “popularity” algorithms.
The subdivision algorithm used by S-Tools can use two different
ways to cut the boxes. In one way, the largest dimension is chosen
by measuring the greatest difference in RGB values. In the other way,
the largest dimension is found by comparing the luminosity of the
different choices. Here is the basic algorithm in detail:
1. Place all of the colors from the image in one box.
2. Repeat this until there are
n
boxes that will represent the final
n
colors.
(a) For each box, find the minimum and maximum value in
each dimension. That is, find the smallest and largest
value of red for any color in the box, the smallest and
largest value of green, and the smallest and largest value
of blue.
(b) For each dimension of each box, measure the length. This
might be the difference in absolute length or it might be
the difference in luminosity.
(c) Find the longest dimension and split this particular box.
Heckbert suggests this can be done by either finding the
median color in the box along this dimension, or you can
choose the geometric middle.
3. Choose a representative color for all of the original colors in
each box. S-Tools offers three choices: center of the box, av-
erageofthecolors,oraverageofthepixels.
colors is chosen, S-Tools can use “dither-
ing” to replace the old colors with new ones.
The algorithm attempts to find the best number of new colors,
When the new set of
n
n
, through a limbo process. It slowly lowers the number of colors
until it ends up with less than 256 colors after the data is mixed into
the least significant bits. Often, it must repeat this process several
times until the right number is found. S-Tools cannot predict the
number of final colors ahead of time because it constantly tries to
