jk87377@cc.tut.fi (Juhana Kouhia) (05/20/91)
Forwarded from comp.compression
Original From: ross@spam.ua.oz.au (Ross Williams)
Original Summary: A personal account of the 1991 data compression conference
Original Keywords: data compression conference 1991 personal account
programme snowbird utah skiing patents
Date: 20 May 91 06:36:09 GMT
[Compressed version by Juhana Kouhia]
Data Compression Conference 1991 (DCC'91): The Unauthorized Report
==================================================================
Author : Ross Williams (ross@spam.ua.oz.au)
Date : 20-May-1991.
ABSTRACT
--------
This document gives a personal account of the world's first conference
entirely devoted to Data Compression: DCC91. The conference was held
at Snowbird, Utah, USA, 7-11 April 1991.
CONFERENCE PROGRAM
------------------
[Selected items -Juhana]
1. Image Coding by Adaptive Tree-Structured Segmentation
X.Wu and C.Yao (U. Western Ontario)
2. Prediction Trees and Lossless Image Compression
N.D.Memon, S.S.Magliveras, and K.Sayood (U. Nebraska at Lincoln)
3. Image Compression Methods with Distortion Controlled Capabilities
T.Markas and J.Reif (Duke U.)
4. Concentric-Shell Partition Vector Quantization with Application to
Image Coding
H.Nguyen and J.W.Mark (U. Waterloo)
5. An Iteratively Interpolative Vector Quantization Algorithm for
Image Data Compression
K.Xue and J.M.Crissey (Wright State U.)
6. A New Transform Domain Vector Quantization Technique for Image Data
Compression in an Asynchronous Transfer Mode Network
P.P.Polit and N.M.Nasrabadi (Worcerster Polytechnic Institute)
7. A 64 Kb/s Video Codec using a 2-D Wavelet Transform
A.S.Lewis and G.Knowles (Imperial College)
8. A Practical Approach to Fractal Based Image Compression
A.P.Pentland and B.Horowitz (MIT)
9. New Methods for Lossless Image Compression Using Arithmetic Coding
P.Howard and J.S.Vitter (Brown U.)
10. Complexity Aspects of Map Compression
H.Brodlaender, T.F.Gonzales, and T.Kloks (UC Santa Barbara)
11. Compression of Natural Images Using Thread-like Visual Primitives
J.Robinson (U. Waterloo)
12. A Neural Network Based VLSI Vector Quantizer for Real-Time Image
Compression
W.Fang, B.Sheu, and O.T.C.Chen (U. Southern California)
13. Two-Level Context Based Compression of Binary Images
A.Moffat (U. Melbourne)
14. Flexible Compression for Bitmap Sets
A.Bookstein (U. Chicago) and S.T.Klein (Bar Ilan U.)
15. Compression of Stereoscopic Image Data
E.Salari an W.A.Whyte, Jr.
16. Concurrent Techniques for Developing Motion Video Compression Algorithms
J.A.Elliott, P.M.Grant, and G.G.Sexton
17. Effects of Coefficient Coding on JPEG Basline Image Compression
M.Chang and G.G.Langdon
18. Generalized Scanning and Multioresolution Compression
I.Gertner and Y.Y.Zeevi
19. Implementing JPEG Algorithm on INMOS Transputer Equipped Machines
A.Omodeo, M.Pugassi, and N.Scarabottolo
20. Improved Hierarchical Interpolation (HINT) Method for the Reversible
Compression of Grayscale Images
K.Chen and T.Ramabadran
21. Lossless Coding Techniques for Color Graphical Images
G.S.Yovanof and J.R.Sullivan
22. Motion-Compensated Video Image Compression Using Luminance and
Chrominance Components for Motion Estimation
C.W.Wong
23. On the Selection of Color Basis for Image Compression
W.K.Chau, S.K.Wong, X.D.Yang, S.J.Wan
24. Performance Analysis of a Vector Quantization Algorithm for Image Data
A.Desoky and Y.You
25. Pictorial Data Compression Using Array Grammars
E.T.Lee
26. Signal Processing and Compression for Image Capturing Systems Using a
Single-Chip Sensor
Y.T.Tsai
27. 3-D Image Compression for X-ray CT Images Using Displacement Estimation
H.Less, Y.Kim, A.H.Rowberg, and E.A.Riskin
28. Transform Coding of Monochrome and Color Images Using Trellis Coded
Quantization
K.L.Tong and M.W.Marcellin
29. Using Fractal Geometry for Image Compression
K.Culik and S.Dube
30. A Very High Speed Noiseless Data Compression Chip for Space
Imaging Applications
R.Anderson, J.Bowers, W.C.Fang, D.Johnson, J.Lee, and R.Nixon
PROCEEDINGS
-----------
As I understand it, the conference proceedings have been published by
the IEEE and you can obtain a copy ("DCC91 proceedings") from:
IEEE Computer Society
PO Box 3014
10662 Los Vaqueros Circle
Los Alamitos CA 90720-1264
USA
Ph: +1 (714) 821-8380
The proceedings are in the form of a small, strongly bound book and is
essential reading for compressor heads. It may also be possible to
obtain a list of the papers presented and then individual reprints.
[I include this patent section in case it has something to do with
graphics -Juhana]
PATENTS
-------
One of the dominant underground themes of the conference (at least for
me) was PATENTS. As Richard Stallman has pointed out, the situation
with software patents is getting on the stupid side. Amazing though it
is, there are now software patents covering:
* Scrolling with multiple subwindows.
* Exclusive OR highlighted text.
* Natural order spreadsheet recalculation.
* Use of backing store to store overlapping parts of windows.
These are just the beginning. Soon, it seems, it will be impossible to
write a large computer program without accidentally violating several
dozen patents.
The field of data compression is now hot with patents. Starting with
the problems with LZW (Unisys wants about $20000 from any manufacturer
using it) and Unix compress, we have seen the LZ78 hierarchy almost
closed to the public. It is extremely unclear what is covered and what
is not.
A key issue here is that there seems to be no TECHNICAL procedure for
establishing exactly what a software patent covers. It seems that any
company that has a patent coming remotely close to an algorithm in use
can successfully launch (if not win) a lawsuit against the user. This
environment rules out the use of any algorithm close to a patented
algorithm by any company or individual who could not survive a test
law case. One result, as we have seen, is the locking up of the LZ78
hierarchy.
I went to the conference expecting to find the answers to the question
of what is covered by patents and what is not. Instead I found
hundreds of people even more confused than I was. In the twilight
hours of the conference dinner I remember sitting at a table with some
fairly heavy compressor heads none of whom seemed to have the faintest
idea of what was covered by patents - "Only a lawyer can decide" they
said.
From my communications before and during the conference my impressions
of the patent situation are as follows:
* The LZ78 class is under challenge. Don't touch it until it is resolved.
There was a rumour going around that a certain compressor head heavy
had agreed to testify that prior art of LZW existed before Welch.
But don't hold your breath.
* The LZ77 class is basically open. However, there are patents popping
up everywhere so get in early or you might find your algorithm gone.
* Markov techniques (such as PPM, PPMC, DMC, DHPC, SAKDC, DAFC -- see
my book for details) are all open. No problem. Go for it.
* Arithmetic coding is open except for some binary arithmetic codes and
some versions that avoid multiplication.
You can find out more about software patents and their problems from:
The League for Programming Freedom
1 Kendall Square #143
PO Box 9171
Cambridge MA 02139
Net: league@prep.ai.mit.edu
Phone: +1 (617) 243-4091
Document: "Against Software Patents".
Document: "Against User Interface Copyright".
To "raise the consciousness" of participants, James Woods and I handed
out league for programming freedom propaganda and buttons (reading
"Get Your Lawyers off My Computer"). We received various responses
ranging from that of someone who seemed to have just come from the
live audience of the Arsenio Hall show ("Hey yeah, give me that badge
- yeah, wooo woo wooo, ooh ooh ooh") to the gruff refusal of a guy
from a certain big company who had probably come to the conference to
flog patent licenses. Gruff refusals were also obtained from people
whom we had already bothered three times before - its hard to
recognise the people you've already approached out of so many people!!
Most people at the conference seemed to agree that there was a serious
problem with the patent situation but did not quite align with the
League for Programming Freedom whose current short term goal is the
elimination of all software patents. Nevertheless, it was gratifying
to see much of the room wearing the badges by the end of the poster
session.
[Other interesting items in order of appearance -Juhana]
Break: 10:10-10:35
Lunch 12:40-4:00
Break: 9:40-10:05
Lunch 12:35-4:00
Break: 10:05-10:30
Lunch: 12:35-4:00
10:45am Break
1000-1015 Break
1215-1300 Lunch
====
I observed an interesting effect during the (I think) poster session
where the hotel served a variety of main-course snack foods and a
chocolate cake cut up into slices. The chocolate cake moved slowly at
first and then was observed to vanish at an exponentially increasing
rate. This could be because:
1) Most people finished their "main course" and hit the chocolate cake
at about the same time.
2) Perceived worth increases with scarcity.
However, what I think was happening was that everyone had their eye on
the chocolate cake, but didn't want to eat any until they had finished
their "main course". However, when the cake started disappearing, the
prospect of missing out caused lots of people to abandon this ideal in
favour of securing some of the scarce resource. So it was (2) with a
sort of added criticality thrown in. Maybe we could use some
catastrophe theory here. Anyway, it doesn't matter because they
brought in another chocolate cake.
As a general rule, the food got better and better as the conference
went on.
====
Please read more from comp.compression,
Juhana Kouhia