chiang@m2c.ORG (Rit Chiang) (05/04/88)
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 you know of any mechanism or algorithm, please e-mail to me. I'll summarize all the responses. Thanks for any help. --------------------------------------------------------------------- Rit Chiang Massachusetts Microelectronics Center 75 North Drive., Westboro, MA 01581 (617)870-0312 UUCP : {harvard, ulowell}!m2c!chiang Internet: chiang@m2c.org CSNET: chiang%m2c.org@relay.cs.net
awpaeth@watcgl.waterloo.edu (Alan W. Paeth) (05/05/88)
In article <2191@m2cM2C.ORG> chiang@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