Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!rutgers!labrea!decwrl!adobe!ondine!greid
From: greid@ondine (Glenn Reid)
Newsgroups: comp.graphics
Subject: Data Compression
Message-ID: <3387@adobe.COM>
Date: Mon, 16-Nov-87 19:37:31 EST
Article-I.D.: adobe.3387
Posted: Mon Nov 16 19:37:31 1987
Date-Received: Thu, 19-Nov-87 03:45:20 EST
References: <619@applix.UUCP> <305@etn-rad.UUCP>
Sender: nobody@adobe.COM
Reply-To: greid@adobe.UUCP (Glenn Reid)
Organization: Adobe Systems Incorporated, Mountain View
Lines: 38
Keywords: compression fonts

As I understand it, 3-to-1 compression rates are close to optimal unless you
can take advantage of the "context" (i.e. knowing that there may be many
sequential frames that are essentially the same).

The way compression schemes work, in general, is to take N bits of data and
represent the pattern in M bits (hopefully N > M).  For example, a run-length
encoding can represent a run of white bits by just encoding the number of
white ones in a row, instead of representing each of them individually.

An interesting variation on this is to represent bitmaps as hexadecimal.  This
is, in fact, a 2-to-1 loss (not really a compression scheme), but it has
the property that there is an external "table lookup" mechanism implied by
the compression scheme.  In particular, the ASCII character code system is
used to represent the hex digits, which are then interpreted as base 16
numbers instead of characters.  The "table lookup" is implicitly the
ASCII character set.

I started thinking about using, say, the Macintosh Screen Fonts as a kind of
table for bitmaps.  A bit pattern could be represented by a single byte if
it happened to match a screen font character in a system font (modulo the
problem that someone could edit the fonts).  Depending on the font, this
could be quite a substantial compression scheme.  But it suffers from being
"context-dependent" in the same sense that the previous examples were, since
it would rely on a Macintosh-specific resource.

But what if there were an ISO standard "table" of bitmaps, encoded much like
the ASCII character set.  Compressed bit images could be represented as
indices into the standard table, rather than being self-sufficient.  I believe
that the only way to dramatically improve compression is to rely on an
external context or external data of some kind, rather than trying to use
an algorithm to compress the data.

Is this feasible?  My information theory is a little weak; perhaps someone
could either run with this or shoot it full of holes so I can go back to
thinking about something else.

Glenn Reid
Adobe Systems