mlm@nl.cs.cmu.edu (Michael L. Mauldin) (04/10/90)
Has anyone in UseNetLand implemented the Laplacian Pyramid image compression algorithm? I believe it was developed at RCA -- I just saw a segment about it last night on "For All Practical Purposes" with Sol Garfunkel. The researchers were claiming 8 to 1 compression for greyscale images. Anyone have any pointers to relevant literature for this algorithm? -- Synopsis: To encode an image, you repeat the following process: 1. Generate a 1/4 size image which is the 'smooth' of the full image by taking a Laplacian of the original. 2. Blow up the 1/4 size image to full size (how was not clear), and then take the difference of the original and the enlarged, smooth image. For regions of low detail, the difference image is mostly zeroes and small integers. 3. Recursively endcode the 1/4 size Laplacian by repeating steps 1 & 2 on the smaller image, until you get down to a single pixel (or some trivially small image). The size requirements are 1 + 1/4 + 1/16 + 1/64 + ... = 4/3 But this image is mostly zeroes and small numbers, and can be compressed easily by other methods. You transmit an image by starting with the lowest resolution images, so the image builds up in resolution. They showed this happening in color for a real estate photo library on the show. -- Michael L. Mauldin (Fuzzy) Center for Machine Translation ARPA: Michael.Mauldin@NL.CS.CMU.EDU Carnegie Mellon University Phone: (412) 268-5293 Pittsburgh, PA 15213-3890
turk@media-lab.media.mit.edu (Matthew Turk) (04/11/90)
See P. Burt and E. Adelson, "The laplacian pyramid as a compact image code", IEEE Trans. Comm., April '83, pp. 532-540. This describes the laplacian pyramid and a simple coding algorithm that uses it. Check out most any image coding proceedings in the mid-to-late 80's for other applications of the laplacian pyramid. Matthew Turk MIT Media Lab turk@media-lab.media.mit.edu 20 Ames St., E15-391 uunet!mit-amt!turk Cambridge, MA 02139 (617)253-0381
jimm@amiga.UUCP (Jim Mackraz) (04/11/90)
In article <8795@pt.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael L. Mauldin) writes:
)Has anyone in UseNetLand implemented the Laplacian Pyramid image
)compression algorithm? I believe it was developed at RCA --
I've toyed with it; sometime's it's called the Burt pyramid. I don't
have the specific reference (sorry), but a paper appears in a
book on "Multi-resolution image processing" or something, edited
by Rosenthal, I think. yeesh.
)The researchers were claiming 8 to 1 compression for greyscale images.
It's not a compression routine, per se, rather a frequency band separation
which has lower sample rates for lower frequency bands. The highest
frequency band has the same number of elements as the original picture,
but now they can be signed (!) so it's a priori larger.
This band typically has values concentrated around 0, though, so a
huffman scheme gets a big payoff. You mentioned this.
Another potentially useful factor is that in compressing motion video,
you can often degrade the high frequencies (detail) for moving objects,
so the pyramid gives you a good handle on that. You might, for example,
transmit the highest band only every few frames or something cheezy
like that. For bringing a still image off of disk, it "looks
recognizable most quickly" to bring up the lows first, and details later,
which you mention.
)Synopsis:
)To encode an image, you repeat the following process:
) 1. Generate a 1/4 size image which is the 'smooth' of
) the full image by taking a Laplacian of the original.
A "subsampled" version of the original after the low frequencies
are filtered out. Is it really the Laplacian? I'm rusty. It's
convolving with a Gaussian, or plainly taking a weighted average
of the neighbors for "every other" point.
) 2. Blow up the 1/4 size image to full size (how was not
) clear), and then take the difference of the original
) and the enlarged, smooth image.
Stick the values from step one on a lattice filled with zeros and
average again. I think the result is not different from something
you could have done in place, without the shrink-then-zoom steps,
but you want the small version anyway, and the operations are supposed
to be easy to implement in hardware this way (see the reference).
I might be remembering poorly on the mechanics of this step.
) For regions of low detail, the difference image is
) mostly zeroes and small integers.
*signed* integers.
) 3. Recursively endcode the 1/4 size Laplacian by repeating
) steps 1 & 2 on the smaller image, until you get down to
) a single pixel (or some trivially small image).
Nah, just do it two or three times ... ;^)
)You transmit an image by starting with the lowest resolution images, so
)the image builds up in resolution. They showed this happening in color
)for a real estate photo library on the show.
I don't know for sure if this technique is part of the RCA/GE/Sarnoff/Intel
DVI technology, but I think it came from the same people.
There are other things you can do with a cheap and multi-rate sampled
frequency band breakdown, such as object recognition, and so on. See
the article.
This stuff gives great demo (I can't distribute the demos I wrote, sorry).
jimm
--
-------------------------------------------------- - opinions by me
"This voice console is a *must*. I press Execute.
`Hello, I know that you've been feeling tired.
I bring you love and deeper understanding.' " -lyrics by Kate Bushkassover@jupiter.crd.ge.com (David Kassover) (04/11/90)
In article <5532@amiga.UUCP> jimm@superman.UUCP (Jim Mackraz) writes: >In article <8795@pt.cs.cmu.edu> mlm@nl.cs.cmu.edu (Michael L. Mauldin) writes: >)Has anyone in UseNetLand implemented the Laplacian Pyramid image >)compression algorithm? I believe it was developed at RCA -- > >I've toyed with it; sometime's it's called the Burt pyramid. I don't >have the specific reference (sorry), but a paper appears in a >book on "Multi-resolution image processing" or something, edited >by Rosenthal, I think. yeesh. Are these the same kind, or similar to, the pyramids that Rosenfeld was investigating at the U of Maryland about 9 years ago? I must admit that I'm not clear on the name nor the university after all this time... Dr. R------ gave a talk at the Graphics Center (colloquial name) at RPI in 1980 or 1981. If memory serves me properly, Dr. R------ was using simple pixel averaging to generate "pyramids" of quadtree and/or octree data. I specifically recall him saying that as far as image analysis and interpretation (That blotch over there: That's a Tank. No don't shoot it, it's ours) quadtrees and pyramids where not much use, but the pyramid in particular was rather usefull for STORAGE and DISPLAY purposes.