jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) (05/21/91)
I have questions to ask later, but first I'll present results:
I just finished a few experiments with using space-filling curves
(actually, Hilbert's version of the Peano curve, windowed to the image
size) to compress digitized images (most with around 140 grey levels).
What I did is extract the pixels from the image along a space-filling
curve instead of along a traditional raster, and then pipe the resulting
pixel sequence into my splay-tree based prefix code (with a single-state
source model).
In summary, over 28 images, using the space-filling-curve gave
compression rations of 2.10 (raw/compressed); on the same images,
using a conventional raster gave ratios of 1.73, so this represents
a significant improvement. In no cases did using the space-filling-
curve make things worse. In one case, it led to no significant
improvement (a picture of a dollar bill at high enough resolution that
the line-work in the engraving was visible).
By way of comparison, LZC compression (using the UNIX compress command)
along a conventional raster through the images gives a ratio of 1.69.
(This is roughly how GIF images are compressed) The only cases where LZC
was better than splay compression along a space-filling-curve involved
images that were digitized with with 4 or fewer bits-per-pixel.
My raster-to-space-filling-curve filter is available, at the cost of
an E-mail request. It's written in C. A better scheme can probably
be devised by doing something smarter than simply windowing a Hilbert
curve to the image size. As I've announced before, my splay-tree based
compression utility is also available, for the same price.
Questions:
1) Who was it who suggested using space-filling curves. Someone from
Carnegie-Mellon first raised the issue in this newsgroup, but
but I vaguely remember someone else mentioning that they'd seen
something published, and yet another person mentioned that they'd
tried using them but didn't publish the results because they weren't
significant.
2) Where can I get my hands on the "standard" images that so many people
in image processing seem to process (over and over and over ...).
I used assorted GIF images I found on USENET (extracting the grey-
scale pixels with pbmplus), but it would be nice to be able to use
the standard examples.
Doug Jones
jones@cs.uiowa.eduvictor@watson.ibm.com (Victor Miller) (05/22/91)
Doug, the first suggestion that I know of to use space-filling curves came from Lempel and Ziv in the Maratea conference "Combinatorial Algorithms on Words" in June 1984. The paper "Compression of Two-dimensional data" was subsequently published in the IEEE Transaction is Information Theory, January 1986, vol. IT-32 number 1. According to the journal, the manuscript was received in Dec. 1983. -- Victor S. Miller Vnet and Bitnet: VICTOR at WATSON Internet: victor@watson.ibm.com IBM, TJ Watson Research Center
eddins@uicbert.eecs.uic.edu (Steve Eddins) (05/22/91)
victor@watson.ibm.com (Victor Miller) writes: >Doug, the first suggestion that I know of to use space-filling curves >came from Lempel and Ziv in the Maratea conference "Combinatorial >Algorithms on Words" in June 1984. The paper "Compression of >Two-dimensional data" was subsequently published in the IEEE >Transaction is Information Theory, January 1986, vol. IT-32 number 1. >According to the journal, the manuscript was received in Dec. 1983. >-- > Victor S. Miller > Vnet and Bitnet: VICTOR at WATSON > Internet: victor@watson.ibm.com > IBM, TJ Watson Research Center Another reference of interest is J.C. Simon and J. Quinqueton, "On the Use of a Peano Scanning Im Image Processing [sic]", in {\em Issues in Digital Image Processing}, ed. R. M. Haralick and J. C. Simon, Sijthoff & Noordhoff, 1980. The authors give an algorithm for generating the Peano scan on a two-dimensional grid. They do not specifically mention compression, although they do remark that "It [the Peano scan] respects neighborhood better than a TV scanning." They give a two-dimensional data clustering application. -- Steve Eddins eddins@brazil.eecs.uic.edu (312) 996-5771 FAX: (312) 413-0024 University of Illinois at Chicago, EECS Dept., M/C 154, 1120 SEO Bldg, Box 4348, Chicago, IL 60680