From srt@duke.cs.duke.edu Thu Jul 16 20:56:34 1992
X-VM-Summary-Format: "%n %*%a %-17.17F %-3.3m %2d %4l/%-5c %I\"%s\"\n"
X-VM-Labels: nil
X-VM-VHeader: ("Resent-" "From:" "Sender:" "To:" "Apparently-To:" "Cc:" "Subject:" "Date:") nil
X-VM-Bookmark: 1
Status: RO
X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil]
["1898" "" "15" "July" "1992" "14:45:18" "GMT" "Stephen R. Tate" "srt@duke.cs.duke.edu" nil "44" "Parallel compression" "^From:" nil nil "7" nil nil nil nil]
nil)
Newsgroups: comp.compression.research
Organization: Duke University Computer Science Dept.; Durham, N.C.
From: srt@duke.cs.duke.edu (Stephen R. Tate)
Subject: Parallel compression
Date: 15 Jul 92 14:45:18 GMT
When I posted a previous message about parallel compression, I
completely forgot to mention the most relevant paper to the current
discussion:
S. De Agostino and J. Storer. "Parallel Algorithms for Optimal
Compression using Dictionaries with the Prefix Property", Proceedings
of the Data Compression Conference, 1992, pp. 52-61.
A summary:
They give parallel algorithms for compression using a fixed dictionary
with the "prefix property" --- in other words, if a string w is in
the dictionary, then all prefixes of w are also in the dictionary (note
that LZW satisfies this). Their best algorithm runs in time O(log^2 n)
time with O(n) processors (on the CREW PRAM model). This isn't
optimal in work, but it is very good (only off by a log^2(n) factor).
However, that is for a fixed dictionary, not one that is dynamically
changing like LZW... as for dynamic dictionaries, they cite a result
that "Dynamic dictionary compression is shown to be P-complete".
Without more details, I'm not sure what that means --- I assume it
means that constructing the LZ parse tree is P-complete. If that's
the correct interpretation, it means that polylog time parallel
algorithms are highly unlikely for LZW compression (for something
compatible with UNIX compress, for instance)... that is, it's
impossible to have a polylog time parallel "compress" algorithm unless
P=NC (highly unlikely).
Of course, polylog algorithms don't always correspond to "practical
parallel algorithms", but it's the best that I know of that can be
clearly analyzed.
This paper is about as clear as mud in spots (they don't give any
intuition about why or how their algorithms work), but that was probably
to fit in the page limit for conference papers --- perhaps a fuller
version is available....
--
Steve Tate srt@duke.cs.duke.edu
Dept. of Computer Science
Duke University
Durham, NC 27706
From jvander@doc.bmd.trw.com Wed Nov 25 15:06:32 1992
Status: RO
X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil]
["8581" "" "21" "November" "1992" "15:00:18" "MST" "jvander@doc.bmd.trw.com" "jvander@doc.bmd.trw.com" nil "207" "SUMMARY: parallel image compression replies" "^From:" nil nil "11" nil nil nil nil]
nil)
Newsgroups: comp.compression,comp.compression.research
From: jvander@doc.bmd.trw.com
Subject: SUMMARY: parallel image compression replies
Date: 21 Nov 92 15:00:18 MST
Hi,
I have collected responses from my posting previously and here present the
findings. Before doing so I wish to express thanks to all who replied. I have
received extremely valuable information. I continue to have correspondence
with some who have responded and will hopefully continue to receive valuable
information. If any are interested in further information I receive let me
know.
Jeff VanderDoes
jvander@oz.bmd.trw.com
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
Here are references I have found interesting on image processing (general and
specific parallel references). They are specific to my research and may or may
not help others out.
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
*** Vector Quantization
[] Y. Linde, A. Buzo, and R.M. Gray, "An alogorithm for vector quantizer
design," IEEE Trans. on Communications COM, vol. 28, pp. 84-95, 1980.
[] R.M. Gray, "Vector quantization," IEEE Acoustics, Speech and Signal
Processing Magazine, pp. 4-29, April 1984.
[] A. Gersho and R.M. Gray, "Vector Quantization and Signal Compression,"
Kluwer Academic Publishers, Boston, 1991.
[] N.M. Nasrabadi and R.A. King, "Image Coding Using Vector Quantization:
A Review," IEEE Trans. Commun. COM-36, pp. 957-971, 1988.
[] R. Chang, W. Chen, and, J. Wang, "A Fast Finite State Algorithm for
Vector Quantizer Design," IEEE Trans. on Signal Processing, Vol. 40, No. 1,
January 1992, pp. 221-225.
[] M. Manohar, and J.C. Tilton, "Progressive Vector Quantization of
Multispectral Image Data Using a Massively Parallel SIMD Machine," Proc. Data
Compression Conference, pp. 181-190, Snowbird, Utah, March 24-27, 1992.
Miscellaneous Image Compression Techniques
[] J.H. Reif and A. Yoshida, "Optical Techniques for Image Compression,"
Proc. Data Compression Conference, pp. 32-41, Snowbird, Utah, March 24-27,
1992.
[] T.R. Reed, V.R. Algazi, G.E. Ford, and I. Hussain, "Perceptually Based
Coding Of Monochrome And Color Still Images," Proc. Data Compression
Conference, pp. 142-151, Snowbird, Utah, March 24-27, 1992.
[] B.R. Epstein, R. Hingorani, J.M. Shapiro, and Martin Czigler,
"Multispectral KLT-Wavelet Data Compression for Landsat Thematic Mapper
Images," Proc. Data Compression Conference, pp. 200-208, Snowbird, Utah,
March 24-27, 1992.
[] L. McMillan, and L. Westover, "A Forward-Mapping Realization of the
Inverse Discrete Cosine Transform," Proc. Data Compression Conference,
pp. 219-228, Snowbird, Utah, March 24-27, 1992.
[] O.T.C. Chen, Z. Zhang, and B.J. Sheu, "An Adaptive High-Speed Lossy
Data Compression," Proc. Data Compression Conference, pp. 349-358, Snowbird,
Utah, March 24-27, 1992.
[] K. Sayood, and K. Anderson, "A differential Lossless Image Compression
Scheme," IEEE Trans. on Signal Processing, Vol. 40, No. 1, January 1992,
pp. 236-241.
JPEG & MPEG Model
[] G. Langdon, A. Gulati, and E. Seiler, "On the JPEG Model for Lossless
Image Compression," Proc. Data Compression Conference, pp. 172-180, Snowbird,
Utah, March 24-27, 1992.
[] D. LeGall, "MPEG: Avideo Compression Standard for Multimedia
Applications," Comm. of ACM, vol. 34, No. 4, pp. 47-58, April 1991.
[] G.K. Wallace, "The JPEG Still Picture Compression Standard,"
Comm. of ACM, vol. 34, No. 4, pp. 31-44, April 1991.
*** General References
[] M. Nelson, "The Data Compression Book," M & T Publishing, San Mateo,
CA, 1991.
[] M. Ben-Ari, "Principles of Concurrent and Distributed Computing,"
Prentice Hall, Cambridge, 1990
[] I.H. Witten, R.M. Neal, and J.G. Cleary, "Arithmetic Coding for Data
Compression," Comm. of ACM, vol. 30, No. 6, pp. 520-539, June 1987.
[] A. Kruger, "Block Truncation Compression: an efficient algorithm for
image compression," Dr. Dobb's Journal, Vol. 17, No. 4, pp. 48-55, April 1992.
[] C. Fitch, "Life without Huffman. (Unary Prefix Code offers easier to
implement data compression than Huffman Code)," EXE, vol. 6, no. 9, pp. 39-42,
March 1992.
[] L. Grunin, "Image Compression for PC graphics: something lossed,
something gained. (new imaging technology)," PC Magazine, vol. 11, no. 8, pp.
337-346, April 28, 1992.
[] M.A. Cody, "The fast wavelet transform: beyond Fourier transforms,"
Dr. Dobb's Journal, vol. 17, no. 4, pp. 16-25, April 1992.
*** Parallel Data Compression
[] M.E. Gonzalez Smith, and J.A. Storer, "Parallel Algorithms for Data
Compression," Journal of the Association for Computing Machinery, Vol. 32, No.
2, April 1985, pp. 344-373.
[] P.G. Howard, and J.S. Vitter, "Parallel Lossless Image Compression
Using Huffman and Arithemetic Coding," Proc. Data Compression Conference,
pp. 299-308, Snowbird, Utah, March 24-27, 1992.
[] M. Tinker, "DVI Parallel Image Compression," Comm. of ACM, vol. 32,
No. 7, pp. 844-851, July 1989.
[] L. Hayat, A. Naqvi, and M.B. Sandler, "Parallel implementation of a
fast thinning algorithm using image compression," IEE Proceedings-I, Vol. 138,
No. 6, pp. 615-620, December 1991.
[] R.L. Bailey, and R. Mukkamala, "Pipeling Data Compression Algorithms,"
The Computer Journal, Vol. 33, No. 4, pp. 308-313, 1990.
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
Here are responses I received which directly have pointers to references on
parallel image compression.
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
From: memon@cse.unl.edu (Nasir Memon)
[...]
at the data compression conference last may there were tow papers
presnted which takled aboot parallel image compression. one was by paul howard
of brown university. his was a very nice paper. i have a copy but i guess he
must have already contacted you. i have his email address too, if you want.
also, another paper was by manhar and tilton talking about image com[pression
on mpp acrhiutectures. i have their paper and email addresses too.
but if u have a copy of the dcc 92 proceedings then u can get hold of them i
guess.
--------------------------------------------------------------------------------
From: pgh@cs.brown.edu
Here's one that I wrote about lossless compression:
%A P. G. Howard
%A J. S. Vitter
%T Parallel Lossless Image Compression Using Huffman and Arithmetic Coding
%E J. A. Storer
%E M. Cohn
%B Proc. Data Compression Conference
%C Snowbird, Utah
%D |MAR| 24-26, 1992
%P 299-308
[He mailed me a copy of the article as well as other applicable articles]
--------------------------------------------------------------------------------
From: ijj@philabs.Philips.Com (IJsbrand Jan Aalbersberg)
%A Van der Meer, Jan
%A Sijstermans, Frans
%T CD-I Full Motion Video Encoding on a Parallel Computer
%J CACM, April 1991, 81 - 91
%K DVI, CD-I, frame compression
--------------------------------------------------------------------------------
From: rao@ctd.comsat.com
You may want to look at IEEE Trans. on Circuits and Systems for Video Technology
Special Issue on VLSI Circuits and Systems for Video - June 1992
_ ashok rao (comsat labs)
--------------------------------------------------------------------------------
From: indjic@ic.ac.uk
I remember I saw an MSc thesis on this subject from Danish Institute
NORDITA, published in 1991 ... but I can't help you more - try to
get in touch with someone over there ..
--------------------------------------------------------------------------------
From: axk8773@usl.edu (Kalhan Ajay)
Hi;
For my master's project i had implemented a Discrete Cosine Transform
based image compression algo. Though this is a sequential algo,
i have parallel implementations on 4 and 16 T800 systems.
Tried data parallelism and also pipelining.
If this interests u, let me know, and i'll send u refs.
/ajay
email: kalhan@usl.edu
[excellent resource]
--------------------------------------------------------------------------------
From: a7657@mindlink.bc.ca (Stephen H. Kawamoto)
ask jloup@chorus.fr for the comp.compression FAQ's or just ask on the topic.
there may be a related FAQ on parallel image compression
--------------------------------------------------------------------------------