Any efficient ways of storing binary or image files ?

[Alan W. Paeth]

In article <2191 at m2cM2C.ORG> chiang at m2c.ORG (Rit Chiang) writes:
>
>Does anyone know of a mechanism in storing binary or image files in
>a way similar to SCCS delta on text file (e.g. storing incremental
>changes only) ?  The goal is to store these non-ASC files
>in a disk space efficient way.

If the image data is 8-bit grey or 24-bit color (intensity channels are sitting
in bytes), then UNIX "compress" would work, except that those feature details
which are spatially adjacent in the 2D image (and show strong coherence), are
widely separated (by a scanline's worth of data) when represented as a 1D data
stream.

APPROACH

A useful fix is to preprocess the image so that every pixel has been subtracted
into the pixel immediately above it. The modified image can now be compressed
into a more compact file for shipping. A set of 2D raster op tools can do the
coding easily -- take two copies of the input, displace the first by one pixel
in y, and subtract. The subsequent compression gives (in my experience) roughly
a 50% savings over straight "compress" and the file is may be reconstructed
exactly.

On reception, the file is uncompressed and then the inverse transform applied:
each input pixel is subtracted into the pixel located immediately above in
the *output* of the previous row. This can *not* be done using said stock tools,
because the decoder is forming the next pixel as a function of both the input
and output streams. It is better to write the whole thing as one tool (which
I've done), and as the function is nearly symmetrical, the code has one simple
"decode mode" switch. The program must also begin in all cases by copying the
first line of input to the output verbatim, as no difference can be formed.
Also, note that whereas decode(code(x)) = x, code(decode(x) != x.

CODE

For input and output data arrays I(r,c) and O(r,c) with 0<=r<rows, 0<=c<cols:

for c = 0 to cols-1 do O(0,c) <- I(0,c)	# copy first row
for r=1 to rows-1 do			# for each subsequent row
   for c = 0 to cols-1 do		# for each pixel along the row
       O(r,c) = I(r,c-1) - I(r,c)	# IF CODING
       O(r,c) = O(r,c-1) - I(r,c)	# IF DECODING
   od
od

Note: choose the appropriate line based on desired coding direction. Also,
when coded in C, care in (un)signed byte conventions must be used. As a simple
test, run the program with BOTH lines present, and the output should match
the input exactly. If it does not, you will probably require an "& 0xff" (mask
off all but lowest eight bits) clause in performing the assignment to the
output array to mimic the effects of a disk write. The subtlety is best
appreciated by playing with the code; it involves a bytes of value 255 and -1
(not) being equivalent, etc. This arises because the difference equation
may form pixel differences with value less than zero. Use of a bitwise logical
"xor" can be used instead of an arithmentic "minus" in forming the difference
thus getting around all this, but the compression ratios are not as large.

DISCUSSION

This filter works by forming a vertical gradient -- constant features such as
vertical lines encode as zero. More generally, images showing a top to bottom
gradient encode as constant values; this increases the likelihood of similar
or identical bytes occurring in the datastream which "compress" then happily
gobbles up. This is slightly more general than predictive-corrective coding
which tries to reduce pixels to black and then encode them in fewer bits.
As long as pixels of relatively similar, not necessarily zero value are formed,
compress works as well. The use of "xor" makes the filter useful for images
with large areas of constant "color", typical of simple synthetic imagery, but
for digitized images, the gradient operation using the "minus" is preferrable.

The technique works for images of arbitrary precision, but the results with
"compress" are not great. To consider an example, with one bit images, the
output runs formed start on arbitrary bit, not byte, boundaries, so "compress"
can not do a very good job in encoding them, even though the entropy of the
image as been reduced.
    
    /Alan Paeth
    Computer Graphics Laboratory
    University of Waterloo