Specifications

9
level is an array of 64 elements that you can index by any interleaving of the two MSBs of each color—we suggest
RRGGBB, but just be sure to use the same interleaving of bits for all uses. Other levels are equally straightforward.
The Algorithm:
This section outlines the algorithm that you must use. The text here is simply a rewriting of Section 2.2 from
http://www.leptonica.org/papers/colorquant.pdf, which is in turn mostly a practical overview of ear-
lier work along with some useful implementation details. The paper does provide enough references for you to trace
back to much of that earlier work (most of which you can find free online or by leveraging UIUC’s online library sub-
scriptions). The paper also provides a number of more sophisticated algorithms, which you are welcome to attempt or
extend. As usual, we strongly recommend that you first get this version working and save a copy to avoid unhappiness
at handin time.
The basic idea behind the algorithm is to set aside 64 colors for the 64 nodes of the second level of an octree, and then
to use the remaining colors (in this case, 128 of them) to represent those nodes in the fourth level of an octree that
contain the most pixels from the image. In other words, you choose the 128 colors that comprise as much of the image
as possible and assign color values for them, then fill in the rest of the image with what’s left.
The first step in the algorithm requires that you count the number of pixels in each node at level four of an octree.
Define a structure for all relevant data for a level-four octree node, then create an array of that structure for your
algorithm. Go through the pixels in the image file, map them into the appropriate octree node, and count them up.
Once you’re done, you must sort the octree nodes based on the number of pixels appearing in each and select the most
frequent 128 for specific palette colors. The C library qsort routine will help here, provided that you have recorded
some sort of color identifier in your node structure for use after the sort completes. If you’re not already familiar with
the C library implementation of quicksort, you may want to read the man page (man 3 qsort) to avoid implementing
your own sorting routine.
What 18-bit color should you use for the palette? The average of the 5:6:5 RGB values for those pixels that make use
of the color. Note that you must calculate the averages for red, green, and blue separately. Calculating the average of
the 16-bit pixels directly may be amusing, but will not earn many points. Rather than going through the pixels in the
file again, of course, you should keep track of the necessary data during the first pass and calculate averages only for
those 128 nodes for which you plan to assign palette colors. Eventually, you also need a way to map these 5:6:5 RGB
color values into the 8-bit VGA colors that you assign, so be sure to keep track of the mapping implied by your octree
node selection.
Every pixel in the image must be assigned a color, of course. The next step in the algorithm is to assign the remaining
64 palette colors to the 64 level-two octree nodes. You may find that in some images, some of these nodes contain no
pixels—you need not bother to optimize this case by reassigning the palette colors to level-four nodes.
What 18-bit color should be used for the palette for the level-two octree nodes? As before, the average of the 5:6:5 RGB
values for those pixels that make use of the color. Here there’s a twist, however: any pixels that have been assigned to
one of the level-four octree nodes do not make use of the level-two palette color. So you must remove their contribution
before calculating the average color for the level-two node.
Your code should write the palette values that it selects for an image in the photo
t structure along with the final
image data. Once your code has finished selecting colors and palette values, it must go through the file data again and
map 5:6:5 RGB values into VGA colors. Don’t forget that your colors are indexed from 0 to 191 in the arrays, but
must occupy colors 64 to 255 in the VGA palette. The first 64 colors in the palette are used for objects and the status
bar. You may want to review fseek (man 3 fseek) to help you go over the file data again.
Finally, don’t forget to make use of the palette that you define (probably in prep
room) via your set palette
function.
My implementation, including all structures, variables, and code, required a little over 150 lines.
Handin Both the checkpoint and the final handin will require you to sit down with a TA in the lab to demonstrate
your code and to answer a few questions.