On Sun, 14 Nov 2004 09:12:50 +0100, Sam Jost wrote:
> The image format for your pennies are called fractal compressors.
Other compression types that could be considered analogous to the
pennies example would be Run-Length encoding and Quad-Tree encoding.
In Run-Length Encoding (RLE), the pennies are analogous to individual
pixels. One-dimensional RLE looks for sequences of pixels in a
horizontal line that are the same color, and encodes them as a
(color,count) pair. More complex RLE compressors will record either
the colors of the pixels, or a (color,count) pair if the count is large
enough that the pair is smaller than the data for the original "run" of
pixels.
In two-dimensional RLE, the algorithm encodes the first scan line the
same way that one-dimensional RLE does. After the first scan line, it
takes the differences in the colors of pixels between the current scan
line and the previous scan line. It then encodes the runs in the
difference. If two scan lines are the same, the difference between
them is a single pair that covers the entire scan line, drastically
reducing the stored size of the information.
Faxes use encodings similar to this. Since a pixel in a fax image must
be either black or white, fax compression doesn't need to store the
colors directly; each line will start with a pixel of a certain color,
and the colors will alternate from there. In fact, a compressed fax
image is pretty much just a bunch of run lengths in scan line order.
The algorithm assumes that the first run of pixels is white, for
example. If it's really black, the algorithm inserts a white run of
zero pixels into the output, so that every line starts with a pixel of
the same color.
Quad-Tree encoding does something similar, but different. In this
encoding, the pennies are analogous to rectangles within the image.
Quad-Tree encoding looks at the image data as a rectangle instead of a
series of scan lines. It takes the entire image and splits it into
four sections, down the middle vertically and across the middle
horizontally.
+---+---+
| | |
| 1 | 2 |
| | |
+---+---+
| | |
| 3 | 4 |
| | |
+---+---+
Conceptually, the beginning of the "tree" is a single color that
represents the entire image. That color is the "average" color of each
of the four sections. Each section is treated the same way, split into
quarters and assigned the "average" color of its four sections, which
are then split into four sections, ... until each section represents a
pixel. The splitting can get tricky when the image dimensions aren't
powers of two, or are different in one direction than the other, but
it's not unmanageable. If the color of a section is close enough to
the colors of the other three sections, or the average, or whatever,
the values for some of the sections don't need to be saved.
There are a ton of optimizations on both of these encodings that can
have dramatic effects on which images compress well with each one. Fax
images, for example, compress the run-length values on top of the
run-length encoding. Quad-tree representations, on the other hand, can
give really good progressive effects if the image is drawn as the image
data is received.
TTYL, DougF KG4LMZ
