Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!mit-eddie!uw-beaver!cornell!rochester!pt.cs.cmu.edu!PROOF.ERGO.CS.CMU.EDU!cokasaki From: cokasaki@PROOF.ERGO.CS.CMU.EDU (Chris Okasaki) Newsgroups: comp.compression Subject: Re: looking for info on image compression Message-ID: <12481@pt.cs.cmu.edu> Date: 26 Mar 91 03:57:29 GMT References: <5040@ns-mx.uiowa.edu> <5043@ns-mx.uiowa.edu> Organization: Carnegie-Mellon University, CS/RI Lines: 86 In article <5043@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes: >...and strings of >pixels, reading left to right, are lousy predictors of the next pixel >compared to 2-dimensional neighborhoods. Given a 2-dimensional image and a locally adaptive compression algorithm which works on 1-dimensional streams, one can do much better than simply processing the pixels from left to right, row by row. As the previous poster suggested, a 2-dimensional neighborhood provides a much better predictor. This is especially important for compression algorithms such as the poster's splay-tree algorithm which adapt very quickly. What one wishes to do is increase the 2-dimensional "locality" of any particular contiguous subsequence of the 1-dimensional stream of data seen by the compressor. One very simple, and very fast, approach is to "snake" through the image, compressing the first row from left to right, the second row from right to left, the third row from left to right, etc. This prevents the annoying "jumps" from the end of one row to the beginning of the next. An even better method is to process the image in strips of N rows, "snaking" vertically across the first strip, then back across the second strip, etc. For instance, a 5x4 image might be processed in the following order (with N=2): 1 4 5 8 9 2 3 6 7 10 19 18 15 14 11 20 17 16 13 12 The value of N depends on size of the compression algorithm's "window", that is, how many previous pixels are significant in determining the current state. For instance, if an algorithm uses the last M pixels to predict the value of the current pixel, then N=sqrt(M) would be a good choice. Unfortunately, M is not always easy to calculate, and even if M is known, the M pixels may not be weighted the same, further complicating the choice of N. An even better, if significantly more complex, path through the image can best be described recursively. The basic pattern is ->1 4-> | ^ v | 2->3 where you enter from the top left and exit from the top right (this orientation will be rotated as the algorithm progresses). Now, divide the image into quadrants, and process each quadrant recursively in the following manner: Quadrant 1 (top left) : enter from the top left, exit from the bottom left Quadrant 2 (bot. left) : enter from the top left, exit from the top right Quadrant 3 (bot. right): enter from the top left, exit from the top right Quadrant 4 (top right) : enter from the bottom right, exit from the top right (Note that the orientation's of the recursive subcalls for Quadrants 1 and 4 are flipped.) For example, an 8x8 image would be processed in the following order: 1 4 5 6 | 59 60 61 64 2 3 8 7 | 58 57 62 63 15 14 9 10 | 55 56 51 50 16 13 12 11 | 54 53 52 49 ------------+------------ 17 18 31 32 | 33 34 47 48 20 19 30 29 | 36 35 46 45 21 24 25 28 | 37 40 41 44 22 23 26 27 | 38 39 42 43 Of course, compressing a 2-dimensional image with an algorithm DESIGNED for that job will almost certainly yield better results than a 1-dimensional stream compressor applied to the same image, but by being careful in our choice of the ORDER in which pixels are processed we may be able come close to the performance of a true 2-d compressor, while still employing our trusty, well-understood, 1-d compression utilities. Comments? Chris cokasaki@cs.cmu.edu BTW, these paths that I've been desribing might be best thought of as space-filling curves. Does anyone know of any better curves in terms of the "locality" of contiguous subsequences? -- ------------------------------------------------------------------------------- | Chris Okasaki | Life is NOT a zero-sum game! | | cokasaki@cs.cmu.edu | | -------------------------------------------------------------------------------