From kragen@dnaco.net Mon Sep 14 13:25:00 1998 Date: Mon, 14 Sep 1998 13:24:59 -0400 (EDT) From: Kragen To: bsittler@nmt.edu Subject: new (?) lossless image compression scheme Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Keywords: X-UID: 1974 Status: O X-Status: There's a picture of my 1600x1200 desktop at . The raw .bmp is five and a half megs; gzip shrinks it by a factor of fifty down to 111K. I think another factor of five or ten could be achieved. Lempel-Ziv compression makes text smaller by replacing the second and subsequent occurrences of a repeated sequence with a reference to the original sequence. Such a scheme applied in two dimensions could significantly reduce the size of simple stylized images like this desktop. Much of the screen real-estate is tiled with a simple desktop pattern, for example, which is about 75x75. Much of the rest of the screen is taken up by identical icons of folders, and most of what remains is either whitespace or text. Such a scheme would be much more efficient (for desktops) if it had provision for overlapping images. Many of the shortcut images on the left side are copies of icons elsewhere on the display, but with a little arrow superimposed on them. The tiling of the background is much simpler to represent as a uniform tiling across the whole desktop, with things obscuring part of it, than if you had to represent its exact contours, which is what LZ compression actually does. I'm not sure how one would do the actual compression, though. The easiest way, in this case, would be to have access to the protocol stream that created the image, but it seems like something that ought to be doable in software in reasonably quick times. You have to somehow notice which areas of the image are similar, guess which things are simpler to represent as being partly obscured, and express the rest concisely. I'm not sure how to do this algorithmically. Kragen -- Kragen Sitaker The sages do not believe that making no mistakes is a blessing. They believe, rather, that the great virtue of man lies in his ability to correct his mistakes and continually make a new man of himself. -- Wang Yang-Ming