From: PAOLIVER@INDYVAX.BITNET
Subject: Photo CD efficiency & patents
Reply-To: PAOLIVER@INDYVAX.bitnet
Organization: FUNET-NGW
Distribution: alt
Date: Tue, 10 Nov 1992 09:31:13 GMT

   Huffman coding has been around for years. I've recently
discovered that it is, as far as I can determine, the
basis for lossless JPEG (a public domain spec, as I
understand it, by the way.)
   Fractal compression, while fantastically computationally
intense for *encoding*, is very efficiently decoded. It can
be made pretty lossless. Perhaps not enough so, however. But
where applicable, it can give excellent results while
getting far better than 3x compression. You've patronizingly
dismissed this as, to paraphrase, gaudy new technology, when
old will do fine.  Well, this pointless new technology lets
someone put 10,000+ pictures on one CD-ROM with pretty good
quality ....

   660 megabytes of storage space is a fairly arbitrary
number. But 100 pictures ... ? A nice even human number
that has little to do with technology, more to do with
a deliberate design decision. Hence my comment.

   To quote from Mark Nelson in 'The Data Compression Book':
"Huffman coding, named for its inventor D.A. Huffman, achieves
the mininum amount of redundancy possible in a fixed set of
variable-length codes. This doesn't mean that Huffman coding
is an optimal coding method. It means that it provides the
best approximation for coding symbols when using fixed-width
codes.
   "... Though Huffman coding is inefficient due to using an
integral number of bits per code, it is relatively easy to
implement and very efficient for both coding and decoding.
Huffman first published his paper on coding in 1952, and it
instantly became the most-cited paper in Information Theory.
It probably still is. Huffman's original work spawned numerous
minor variations, and it dominated the coding world till the
early 1980s. [He goes on to describe Arithmetic coding as a
successor. He also describes adaptive coding, within an
appropriate statistical model, as far better than fixed length
codes.]"
        Yes, I realize that you quoted a 'mere' 15% improvement
using Arithmetic coding. Neither Huffman nor Arithmetic
coding were developed, as far as I know, with raster picture
data in mind, either.

   I simply don't believe that a concerted effort of the
results of thousands of man hours of thinking time can yield
nothing better for lossless encoding of picture data than
Huffman coding (40 years old). Perhaps this is merely my
astonishment at work here. Perhaps Kodak really did
find the best available to Mankind when they settled
on it. I remain skeptical simply because Huffman has been
around for a long time and was not developed with 2d
raster data in mind with its almost inherent redundancies
(few pictures taken are going to consist of a series of exposed
grains that randomly vary from grain to adjacent grain,
I think you'd agree; most clearly have gradual variations
within broad regions of the picture, along with sharp
transitions. A Laplacian edge finding digital filter
illustrates this fact. Hence, there's clear structure and
large scale general order to almost all real world photos. This
implies that a better model utilizing these redundancies can
be developed specifically for photos.)

   I'll believe what you're saying after I see Kodak
post a reward of, say, $20,000 (a modest sum for Kodak,
a lot for most academics personally) to the first person to
come up with a lossless compression algorithm that performs
an average of 2X or more better than Kodak's scheme on a
sampling of real world photographs (as opposed to randomly
garbled bits of junk from a random number generator.) The cost
savings in disks required would clearly be immense, far
greater than $20,000.
   If the problem is as intractable as you claim, Kodak could
make this offer with no trepidition, couldn't it? At worst,
it could get better technology for a small cost. If, that is,
it really wanted it.

    I'm beginning to see that Kodak wanted to be as "standard"
as possible -- re: lossless JPEG (Huffman coding), CD-ROM
standards, etc. This isn't bad, except that there appears to
be something of a contradiction between wanting to sacrifice
the best possible efficiency in the name of standardization,
while simultaneously wanting to stop third parties from freely
using Photo-CD.

   In a legal philosophy sense, I don't believe that someone
should be able to get a patent by simply application of an old
known algorithm in an obvious way. Otherwise, I could claim
patent protection on the application of Huffman coding to, say,
stock market tables and sue anyone who uses a public domain
Huffman encoder to encode their stock market data. Substitute
"stock market tables" with "raster scan data", no difference.

   This doesn't mean that Kodak should be able to patent other,
really new, aspects, if they are really new arrangements. I
keep bringing up fractal compression because, yes, it is
*really new* and very non-obvious, even to other fractal people.
So they deserve their patent. But patenting the obvious, or even
the non-obvious but publicly known for a long time, is contrary
to the charter of the patent office, regardless of the
way it's currently operated.
Newsgroups: alt.cd-rom