Pixmaps, Revisited: Encoding Data More Efficiently

As you should recall from our exploration of pixel maps, it is straightforward to write an image to a file by writing each pixel in the image, one by one. Unfortunately, this technique is far from the most efficient way to represent a color. For example, we must represent each pixel with approximately twelve characters: three for the red component, three for the green component, three for the blue component, a space between red and green, a space between green and blue, and a carriage return.

If we care about efficiency, we want a smaller representation. Is such a representation possible? Certainly. We know that the computer internally represents integers more efficiently. Unfortunately, standard Scheme does not provide us with direct access to that representation. In particular, there are no procedures that write and read integers in the standard computer format.

However, that does not mean that we are doomed to using only the multi-character representation of integers. In particular, we can cheat a bit by converting integers to characters and then writing those characters. Then, to read an integer, we read the character and convert back. This technique will only work for relatively small positive integers, but those are the kinds of integers we use for the components.

Okay, let's write some helper procedure that do the conversion from integer to character and back again. Before writing them, we need to note one more thing: Many implementations of write-char will not write the character that corresponds to 0. What's the workaround? We add one to the value when writing, and subtract 1 from the value when reading. Putting that all together, we get the following.

(define int-write
  (lambda (int port)
    (write-char (integer->char (+ int 1)) port)))

(define int-read
  (lambda (port)
    (let ((ch (read-char port)))
      (if (eof-object? ch)
          ch
          (- (char->integer ch) 1)))))

(define int-peek
  (lambda (port)
    (let ((ch (peek-char port)))
      (if (eof-object? ch)
          ch
          (- (char->integer ch) 1)))))

We are now ready to rewrite rgb-write and rgb-read. Since the internal representation of colors includes negative integers and very large integers (neither of which are acceptable inputs to int-write), we must design our implementation to use the components. By relying on the components, we also ensure that our procedure will continue to work even if the internal representation of colors changes.

(define rgb-write
  (lambda (color port)
    (int-write (rgb-red color) port)
    (int-write (rgb-green color) port)
    (int-write (rgb-blue color) port)))

(define rgb-read
  (lambda (port)
    (let* ((red (int-read port))
           (green (int-read port))
           (blue (int-read port)))
       (if (eof-object? blue) 
           blue
           (rgb-new red green blue)))))

These work as well as the preceding versions, but produce files that a human being can't read. Most programmers will say it's worth the loss of readability in exchange for the savings in space. How much of a savings is this? Well, we now use three characters for every color. It turns out that each character takes about a byte. Hence, when we write the color white (255/255/255) in human-readable form, we end up writing 12 bytes (three for each number, plus two spaces and the newline). Even when we write the color black (0/0/0) in human-readable format, we end up writing six bytes (one for each number, plus two spaces, plus the newline). Hence, using bytes saves us between 50% and 75% of the file size.

While we've made some improvements, the files we create by representing images as pixmaps are still pretty big. For example, a 200x200 image has 40,000 pixels. If we're using 3 bytes per pixel, that's 120K to store the image. If you try saving a 200x200 image with the GIMP, you'll normally find that it's significantly smaller. Why? Because computer scientists have been looking at lots of clever ways to save space in images.

A common technique for saving space is to use fewer bytes per pixel. Can we really do that? We can certainly do so if the image contains a limited number of colors. For example, if we know that each pixel is black or white, we can use less than a byte per pixel. We won't go to that level of detail in this class, because that requires us to explore some more complex issues of data representation. However, we will see some very reliable techniques for using only a byte per pixel in our next reading and lab, using a technique called “color palettes”.

What other techniques are possible? If an image has a number of blocks of pixels of the same color, we can save space by representing blocks of colors as blocks, rather than a pixel at a time. Doing so will make it much harder to write the procedures that write and read files, but it will save a lot of space. The simplest form of this representation is called run-length encoding and it involves writing a count before each color. For example, we might say that the first line of an image has 23 black pixels, followed by 16 white pixels, followed by 25 black pixels, with only 12 bytes (one byte for the 23, three bytes for black, one byte for the 16, three bytes for white, one byte for the 25, three bytes for the black), which is much better than the 192 bytes we would need if we wrote each pixel.

Another promising strategy echoes one you've seen. If you create an image with an algorithm, you can represent the image with the algorithm, rather than in terms of the pixel. Since most of the algorithms we write using region.compute-pixels! or the GIMP drawing tools uses less than a page of code, we can represent images with less than 1000 or so bytes, even for really large images. But what if you don't know the function used to create the image? Trying to construct functions that can represent an image are one of the more interesting directions of graphics research.