Thoughts on a GIF-replacement file format

769 views
Skip to first unread message

Tom Lane

unread,
Jan 5, 1995, 7:50:07 PM1/5/95
to
It seems to me that there are two separable decisions to be made:
1. what overall file format to use;
2. what compression mechanism to use within that overall format.
We could reasonably drop GZIP or Huffman or another compression method
into any file format design, so these are separate issues. The
compression method will pretty much determine the file size for any
given image data, but the file format will determine the features and
future extensibility of the design.


For the file format choice, I think there are two reasonable
alternatives:
1. Use GIF as-is, or with a few extensions such as 24-bit support.
2. Use an all-new design, whether Tom Boutell's or something else.
The third alternative, bolting a new compression method onto some other
existing spec such as Targa, doesn't appeal to me. It will not be
noticeably easier to implement, and it will not address the existing
application areas of GIF as well as GIF does.

Choice #1 assumes that Compuserve will cooperate and make the revised
"GIF95" spec available on the same terms as previous versions. Onerous
requirements such as we saw in the proposed license agreement are
unacceptable and will certainly lead to the adoption of choice #2.
But for now let's assume that CIS will play ball.

To make a reasoned choice between these alternatives, we need to look at
the feature set that we want the file format to have. Which of GIF89's
capabilities must be preserved? Which would we be willing to give up?
What new capabilities, not found in GIF89, do we really need?

I am not a fan of including features in the file format definition that
we don't desperately need. To be widely portable, especially in the
short time frame we have here, the definition must be simple and easy to
implement. I'd remind you also that few existing implementations
support all of GIF89; the "portable" part of GIF is probably GIF87 with
only one image per file.

For example, Boutell's proposal does not support multiple images in one
file, nor does it handle the animation capabilities of GIF89. As far as
I know there are no Internet applications that make use of those
features, so eliminating them is a reasonable idea for Internet
purposes. I do not know how many CIS-related applications really need
those features. If that stuff is widely used anywhere, then perhaps we
need to stick closely to the existing GIF format.

The question of just which features to include and which not needs much
more discussion before any format proposal is frozen. Here are a few
thoughts of my own:
1. Serial access read and write (ie, the format must be readable and
writable on-the-fly as a datastream): essential to keep.
2. Palette image storage: essential to keep, though it might be enough
to support only 4 and 8 bits per pixel, not 1 to 8 as GIF does.
Odd-size bit depths are more complex to program and don't compress
very well --- the space savings may be illusory.
3. Lossless true color storage: not in GIF89, but many people want to
add this. Do we need both 16 and 24 bits/pixel, or just 24?
4. Lossy true color storage: I think it would be better to keep lossy
storage out of the picture. It's tough enough getting people to
understand the differences between JPEG and GIF; having both lossy
and lossless options in one file format will case untold confusion.
5. Text comments: essential.
6. Support for non-square pixels: I'd rather like to see this crock
go away :-). If anyone still has that sort of silly hardware,
their viewers should compensate for it, not make the rest of us
live with it.
7. Interleaved display capability: I once thought this capability was
useless, but it is coming back into favor on the World Wide Web.
We probably want to keep it. Do we want an interleave order
smarter than GIF89's ? (Ie interleave in both directions?)
8. Animation, user interaction, etc: I'd say lose these.
9. Multiple images per file: I'd say lose this, too.
No doubt others will have their own opinions on these points. Let's
hear them! We need a discussion!!


On to the second basic issue, which is what compression method to
provide. I think there's not much question that we want a lossless
compression method that gives compression at least approaching what
we got from LZW. I see two reasonable choices:
1. GZIP. This is pretty close to state of the art (better than LZW)
and while it is not absolutely certain to be patent-free, a lot of
effort has gone towards making it so. I think we could safely use it.
2. Some ancient method such as plain Huffman coding, which will
certainly be patent-free by virtue of age. This is likely to give
noticeably poorer compression than LZW, however.
Anything else will pose a distinct risk of being blindsided later by
some patent, as originally happened with LZW.

My feeling is that GZIP is a better choice.

regards, tom lane
organizer, Independent JPEG Group

Oliver Fromme (TBH)

unread,
Jan 5, 1995, 10:09:39 PM1/5/95
to

Tom Lane (t...@netcom.com) wrote:
: It seems to me that there are two separable decisions to be made:

: 1. what overall file format to use;
: 2. what compression mechanism to use within that overall format.
: [...]
: For the file format choice, I think there are two reasonable

: alternatives:
: 1. Use GIF as-is, or with a few extensions such as 24-bit support.
: 2. Use an all-new design, whether Tom Boutell's or something else.
: [...]
: I'd remind you also that few existing implementations

: support all of GIF89; the "portable" part of GIF is probably GIF87 with
: only one image per file.

Basically I agree with Tom. GIF87 covers almost everything that we
need for a "lightweight" portable format. I'd like to suggest the
following extensions to GIF87:
1. transparency (quite important for the Web),
2. some provisions for error recovery, maybe similar to the
restart markers in JPEG files.

The format doesn't need to support animations (that's what AVI,
MPEG, FLI, DL etc. are for) nor multiple images.

I don't think that the format should support 24 bit images. So far,
everybody seemed to be pretty happy with GIF's 8 bit restriction,
and adding 24 bit support to its successor might cause some confusion.
Remember that there are many other formats supporting lossless 24 bit
images (Targa, PCX, BMP, just to mention a few). Also, 24 bit images
won't benefit much from the lossless compression (whichever algorithm
will be used).

As far as 16 bit images are concerned, I think they are absolutely
useless. Such images have only 5 bit (32 steps) per color component,
which makes them look bad. In fact, when converting a truecolor
image to 16 bit (e.g. Targa-16) and to 8 bit (GIF or whatever),
you'll probably notice that the 8 bit image looks better, especially
on smooth color transitions.

: [...]
: 2. Palette image storage: essential to keep, though it might be enough


: to support only 4 and 8 bits per pixel, not 1 to 8 as GIF does.
: Odd-size bit depths are more complex to program and don't compress
: very well --- the space savings may be illusory.

At least 1, 4 and 8 bit should be supported. Also, sometimes
I used 6 bit greyscaled GIFs (64 shades of grey), but that's
not too important.

: [...]
: 7. Interleaved display capability: I once thought this capability was


: useless, but it is coming back into favor on the World Wide Web.
: We probably want to keep it. Do we want an interleave order
: smarter than GIF89's ? (Ie interleave in both directions?)

I think it's good the way GIF handles it. A 2D interleaving
would complicate things very much, and it would certainly
result in poor compression. I don't think it's worth the
trouble.

: [...]
: No doubt others will have their own opinions on these points. Let's


: hear them! We need a discussion!!

Very true!

: On to the second basic issue, which is what compression method to


: provide. I think there's not much question that we want a lossless
: compression method that gives compression at least approaching what
: we got from LZW. I see two reasonable choices:
: 1. GZIP. This is pretty close to state of the art (better than LZW)
: and while it is not absolutely certain to be patent-free, a lot of
: effort has gone towards making it so. I think we could safely use it.
: 2. Some ancient method such as plain Huffman coding, which will
: certainly be patent-free by virtue of age. This is likely to give
: noticeably poorer compression than LZW, however.
: Anything else will pose a distinct risk of being blindsided later by
: some patent, as originally happened with LZW.

A few weeks ago I found a collection of compression sources on
the net. It contained a program called AR002 (or something
similar) which uses a compression method called LZHUF (maybe
a combination of LZ77 and Huffman, both of which are patent-free
as far as I know). The same method is used in the popular
LHA archiver, by the way. The source is about 500 lines of
C (both the encoder and decoder), and the implementation seems
to be quite easy and straightforward. The compression should be
better than LZW (on average), and it's quite fast and doesn't
require too much memory (quite an important point).
How about this one?

I haven't had a look at the gzip sources yet, but I suspect that
it is considerably more complicated and more extensive than
LZHUF. If I'm wrong, well, then let's go for gzip!

Regards,
Oliver Fromme, author of QPEG

PS: My software will continue to support the GIF format
(at least reading it), and of course the new format, too,
as soon as the specs are fixed and widely accepted.

--
Oliver Fromme, Leibnizstr. 18-61, 38678 Clausthal, Germany
Internet/Usenet email address: fro...@rz.tu-clausthal.de
Info service: send email with subject "SEND HELP" to the above address
WWW server: http://www.rz.tu-clausthal.de/~inof/Welcome.html

John Bradley

unread,
Jan 5, 1995, 11:34:34 PM1/5/95
to
In article <TGL.95Ja...@netcom16.netcom.com> t...@netcom.com (Tom Lane) writes:
> 2. Palette image storage: essential to keep, though it might be enough
> to support only 4 and 8 bits per pixel, not 1 to 8 as GIF does.
> Odd-size bit depths are more complex to program and don't compress
> very well --- the space savings may be illusory.

I've always figured that having the format support arbitrary bit depths mainly
made it easier for the decoder to deal with: ie, it knows ahead of time that
there'll be no more than 16 colors, or 256 colors, or whatever. I believe
that, other than the smaller colortable in the header of the file, it makes
no difference on the compression. (An '8-bit' image with two colors should
compress nearly as well as a '1-bit' image with two colors.)

Anyway, I agree that 1-bit per pixel is useful (the only other compressed
1-bit format I can think of is TIFF, and that's entirely too complex to
be the standard 'lightweight' image format). I'd say 'leave it variable',
just like in GIF. Once you have to write the 'get some number of bits other
than 8' function, it's easy-ish enough to get an arbitrary number of bits.

> 3. Lossless true color storage: not in GIF89, but many people want to
> add this. Do we need both 16 and 24 bits/pixel, or just 24?

I'd like to see this added, but I won't cry if it doesn't make it. I think
this would be a fine opportunity to fix the one glaring shortcoming in GIF
(as far as I'm concerned), the lack of 24-bit lossless support. While there
are plenty of other 24-bit lossless formats (Targa, TIFF, etc.) for the
most part they're either non-trivial to implement, too all-encompassing,
not widespread, and/or not sufficiently compressed. I'd think the a
plane-wise LZ-ish compression scheme would do reasonably well.

Incidentally, I'm entirely against support for 16-bit images (of
either variety: truecolor or greyscale). 16-bit truecolor images are
easy enough to compute from their 24-bit counterparts, and in any event,
I think 16-bit 'truecolor' hardware will, for the most part, go away.
I think it's just a temporary anomoly, as no one would *want* 16-bit
truecolor versus 24-bit truecolor. (Whereas 8-bit pseudocolor is
still a very useful format, for reasons mentioned elsewhere.)

16-bit greyscale images are entirely too specialized (x-ray images, etc.)
to warrant inclusion in a 'lightweight graphics standard'.

> 4. Lossy true color storage: I think it would be better to keep lossy
> storage out of the picture. It's tough enough getting people to
> understand the differences between JPEG and GIF; having both lossy
> and lossless options in one file format will case untold confusion.

Agreed. You want lossy, use JPEG. You want lossless, use TheNewThing.

> 5. Text comments: essential.

Agreed. As far as I'm concerned, it's the only really useful feature in
GIF89. Well, that and transparency. I'd particularly *like* to see the
'text captioning' feature go away, as I've always thought it was a useless,
poorly-defined feature, and one that I've almost never seen an example of.

> 6. Support for non-square pixels: I'd rather like to see this crock
> go away :-). If anyone still has that sort of silly hardware,
> their viewers should compensate for it, not make the rest of us
> live with it.

Agreed. There's no need for this bogosity in this day and age. If you
still have non-1:1 images, get a good image scaler to fix them. (I
recommend XV, personally. :-)

> 7. Interleaved display capability: I once thought this capability was
> useless, but it is coming back into favor on the World Wide Web.
> We probably want to keep it. Do we want an interleave order
> smarter than GIF89's ? (Ie interleave in both directions?)

Agreed that it's necessary. I'd say keep it the same as GIF's.

> 8. Animation, user interaction, etc: I'd say lose these.
> 9. Multiple images per file: I'd say lose this, too.

Lose 'em both.

Basically, here's what I'd like to see:
1 image per file
support for 1-8 bit colormapped images,
with reasonable lossless compression,
and a 'transparent' color
support for 24-bit truecolor images,
with reasonable lossless compression,
*no* transparent color in 24-bit mode

And I think that would nicely handle nearly everything that JPEG doesn't.

>My feeling is that GZIP is a better choice.

Agreed, though I'd have to re-read the terms of the Gnu Public License
to be sure!

John Bradley - XV Dude

John Woods

unread,
Jan 6, 1995, 10:43:47 AM1/6/95
to
t...@netcom.com (Tom Lane) writes:
>For the file format choice, I think there are two reasonable
>alternatives:
> 1. Use GIF as-is, or with a few extensions such as 24-bit support.
> 2. Use an all-new design, whether Tom Boutell's or something else.
>To make a reasoned choice between these alternatives, we need to look at
>the feature set that we want the file format to have. Which of GIF89's
>capabilities must be preserved? Which would we be willing to give up?
>What new capabilities, not found in GIF89, do we really need?

I would like to argue for using exactly GIF89, nothing more and nothing less,
with a license-free compression scheme.

A problem with designing an entirely new format is that major modifications
will be needed to the dozens or hundreds of currently-maintained graphic
manipulation programs, which will slow the acceptance of an entirely new
format. Reusing the GIF framework means that existing applications need only
test for a new string and contain new compression/decompression codes. If
freely-usable compression and decompression code is available, application
writers will have little trouble adapting. While there are a wide array of
problems that GIF does not address, these problems are, in general, already
addressed by other formats; the immediate problem, the sudden absence of the
GIF format, is quite handily solved by, well, GIF.

That argues for GIF, and nothing more. As to "nothing less", while the fancier
features of GIF89 are spottily implemented, they're at least already specified,
and repeating their specification doesn't make existing applications any _less_
complete (so the problem doesn't get worse); dropping those features means
that we'll be wasting bandwidth again as soon as someone figures out how to
use one of those features ("We need a lightweight image format with a 600-page
specification.").


I see the real problem as not the lack of a given format (there are billions
of other image formats, for heaven's sake, it's not like we're all going to
have to print all our images to a color printer for archival until we figure
out how to represent them again!), it's the sudden lack of a simple format
that solves well the same problems that GIF solves well. A truly lightweight
image format, like Boutell's proposal before everyone started clamoring for
36-bit animated movies in arbitrary color spaces with sound and smell, would
solve the same types of problems (and solve them well), but would face inertia
in being adopted by application writers. The featurefest proposals that have
been developing here would not really solve the GIF problem (come on, let's
keep the display time down below the time required to download the image at
14.4K!), tread over ground already handled adequately by dozens of other
formats*, and will take an infinite amount of time to settle on.


Now, the chief difficulty is getting Compu$erve to agree to it. There are two
important reasons why they might not: (1) their claims that it's Uniblab
holding a gun to their heads notwithstanding, they really want to torpedo WWW
until they've cornered the market, in which case no GIF-like format will get
their approval; (2) their lawyers will be so sick and tired of arguing with
intellectual-property lawyers about patents that they will want to have an
absolutely ironclad guarantee that the chosen compression format will never,
EVER get them into legal trouble again, in which case no GIF-like format will
get their approval without such a guarantee. For gzip, GNU's legal opinion
that gzip is free of trouble might or might not be adequate; CompuServe's
lawyers will certainly need to duplicate the work themselves, and they will
be a good deal less optimistic in the face of any uncertainty.


In the absense of CompuServe's blessing of a free GIF95 format, then I would
argue for the simplest possible format that solves GIF's problem domain, and
leave harder problems to other formats. Since the motivation for some is
Web pages, there's no particular reason why the icon that points to one's
holiday photos has to be in the same format as those holiday photos.


>On to the second basic issue, which is what compression method to
>provide. I think there's not much question that we want a lossless
>compression method that gives compression at least approaching what
>we got from LZW. I see two reasonable choices:
> 1. GZIP. This is pretty close to state of the art (better than LZW)
> and while it is not absolutely certain to be patent-free, a lot of
> effort has gone towards making it so. I think we could safely use it.

Gzip looks like a good bet, but I'd like to see a little more work done in
determining its patent status; not only don't we want to go through this
fire drill again, we want commercial developers to feel sure that *they*
won't go through this fire drill again, otherwise they might as well give
Uniblab their pound of flesh now and be done with it (which would torpedo
any free compressed formats).

The folks who trumpeted their FREE SOFTWARE FINAL SOLUTION TO THE GIF PROBLEM
suggested LZSS compression; does anyone know for sure which patents do or don't
cover it?

Maybe some owner of a compression patent could be convinced to license it free
of charge to anyone who gives them free advertising (i.e. have your application
display "THANK YOU COREDUMP INDUSTRIES FOR YOUR COMPRESSION ALGORITHM" and you
can use it free, or something like that).

Oliver Fromme (TBH)

unread,
Jan 6, 1995, 10:51:06 AM1/6/95
to
John Bradley (bra...@devo.dccs.upenn.edu) wrote:

: t...@netcom.com (Tom Lane) writes:
: > 2. Palette image storage: essential to keep, though it might be enough
: > to support only 4 and 8 bits per pixel, not 1 to 8 as GIF does.
: > Odd-size bit depths are more complex to program and don't compress
: > very well --- the space savings may be illusory.

: I've always figured that having the format support arbitrary bit depths mainly
: made it easier for the decoder to deal with: ie, it knows ahead of time that
: there'll be no more than 16 colors, or 256 colors, or whatever. I believe
: that, other than the smaller colortable in the header of the file, it makes
: no difference on the compression. (An '8-bit' image with two colors should
: compress nearly as well as a '1-bit' image with two colors.)

Agreed. 1, 4 and 8 bit should be supported at the very least. I don't
think that odd bit depths would cause that much trouble. Maybe even
an odd number of colors, for example 175 palette entries (just to save
space in the palette, but the indices would be 8 bit in this case, of
course).

By the way, the format should also support greyscaled images without
needing to store a palette. For example, 8 bit greyscaled images
(0=black, 255=white). Obviously, a palette for such images is
superfluous and would just waste space.
I think it is also advisable to transform greyscaled images to
delta representation before compression.

: > 3. Lossless true color storage: not in GIF89, but many people want to


: > add this. Do we need both 16 and 24 bits/pixel, or just 24?

: I'd like to see this added, but I won't cry if it doesn't make it.

: [...]
: I'd think the a


: plane-wise LZ-ish compression scheme would do reasonably well.

You're probably right. The problem is, that lossless compression
methods yield poor compression on typical 24 bit images (i.e.
photographic material), while JPEG yields best compression (but
lossy) on just that type of images.

How about using lossless JPEG for the 24 bit variant of the new
format? Or something similar to lossless JPEG? As far as I
know, lossless JPEG is quite simple and easy to implement (as
compared to lossy JPEG).

Another suggestion for 24 bit images:
First, the image should be separated into its RGB components
(perhaps not the whole image, but line by line, because that
needs considerably less memory on both the encoding and decoding
side).
Second, the components are transformed into delta representation
(i.e. for each sample the difference to its predecessor ist stored,
rather than the sample itself). For typical 24 bit images, the
delta representation compresses certainly better than the original
data.
Third, the resulting data is compressed using either gzip,
LZHUF or something similar to lossless JPEG (the original
lossless JPEG method is not applicable to delta representation).

I think the above process should compress pretty well.

: Incidentally, I'm entirely against support for 16-bit images (of
: either variety: truecolor or greyscale).

: [...]

I fully agree.

: Basically, here's what I'd like to see:


: 1 image per file
: support for 1-8 bit colormapped images,
: with reasonable lossless compression,
: and a 'transparent' color
: support for 24-bit truecolor images,
: with reasonable lossless compression,
: *no* transparent color in 24-bit mode

That seems very reasonable to me. I'd like to add the possibility
of greyscaled images (1-8 bit) without color map.

: And I think that would nicely handle nearly everything that JPEG doesn't.

I think so, too.

A few thoughts about the basic format:
- It should contain a "magic word" at the very beginning,
preferably the name of the format (see below), so it can
be easily identified. Some version number or feature byte
should also be added.
- The file should be divided into chunks, similar to IFF
or GIF, each chunk starting with a byte (or word) which
identifies its type, followed by its size (for easily
skipping the chunk).
- There should be some rules defining the order of chunks,
so it can be read in a serial way. For example, the
palette (if existant) should precede the actual pixel
data. The chunk defining the image size should be the
very first in the file, immediately followed by a copyright
notice chunk (if existant).
- The format should be extendable, i.e. it should be possible
to add more application specific chunks, which may be
ignored by other applications.

By the way, has anybody an idea how to call the new format?
Maybe this is a little premature, but people like to have
names for things... Once we agreed on a name, everything
else should be as easy as patenting xor to change a bit's
value... :-)

How about "PING" ("Ping Is Not Gif") ? The 3 byte extension
for DOS people could be either .pin or .png.
Or how about "TNT" ("The New Thing", as Brad suggested) ?
On the other hand, I think the name should be pronounceable,
just like "GIF".

Regards,
Oliver Fromme, author of QPEG

--


Oliver Fromme, Leibnizstr. 18-61, 38678 Clausthal, Germany
Internet/Usenet email address: fro...@rz.tu-clausthal.de

WWW server: http://www.rz.tu-clausthal.de/~inof/Welcome.html

Cave Newt

unread,
Jan 6, 1995, 11:57:09 AM1/6/95
to
t...@netcom.com (Tom Lane) writes:

>> 2. Palette image storage: essential to keep, though it might be enough
>> to support only 4 and 8 bits per pixel, not 1 to 8 as GIF does.
>> Odd-size bit depths are more complex to program and don't compress
>> very well --- the space savings may be illusory.

bra...@devo.dccs.upenn.edu (John Bradley) writes:

>Once you have to write the 'get some number of bits other
>than 8' function, it's easy-ish enough to get an arbitrary number of bits.

The question is how well it compresses. I'm reasonably sure deflation
is an 8-bit method, so are you going to "get N bits and put them into
a multiple of 8" or try to pack them? If the latter, that way lies
madness.

>Incidentally, I'm entirely against support for 16-bit images

Ditto.

>I think 16-bit 'truecolor' hardware will, for the most part, go away.
>I think it's just a temporary anomoly, as no one would *want* 16-bit
>truecolor versus 24-bit truecolor. (Whereas 8-bit pseudocolor is
>still a very useful format, for reasons mentioned elsewhere.)

Maybe, maybe not. Keep in mind that the issue isn't simply one of
memory sizes but of bandwidth, shielding, and so forth. Boosting the
bits by 50% (16 -> 24) without boosting the dot clock means your refresh
rates suck. And 200MHz signals require serious engineering to avoid an
RF nightmare. (I chuckle over the thought of the FCC refusing even
class A certification to ATI or Diamond. :-) )

>Agreed. You want lossy, use JPEG. You want lossless, use TheNewThing.

>> 8. Animation, user interaction, etc: I'd say lose these.
>> 9. Multiple images per file: I'd say lose this, too.

Yup.

>> 7. Interleaved display capability: I once thought this capability was
>> useless, but it is coming back into favor on the World Wide Web.
>> We probably want to keep it. Do we want an interleave order
>> smarter than GIF89's ? (Ie interleave in both directions?)

>Agreed that it's necessary. I'd say keep it the same as GIF's.

As someone else pointed out, 2D interleaving kills your compression.
Keep it the same as GIF89, possibly with a bigger interleave factor (I'm
not sure what the GIF spec says about this).

>>My feeling is that GZIP is a better choice.

>Agreed, though I'd have to re-read the terms of the Gnu Public License
>to be sure!

That's irrelevant. The engine for GZIP existed before GZIP did and outside
the GPL.

Greg Roelofs
Info-ZIP UnZip Dude

Oliver Fromme (TBH)

unread,
Jan 6, 1995, 1:23:00 PM1/6/95
to
Cave Newt (ro...@ellis.uchicago.edu) wrote:

: bra...@devo.dccs.upenn.edu (John Bradley) writes:
:
: >Once you have to write the 'get some number of bits other
: >than 8' function, it's easy-ish enough to get an arbitrary number of bits.

: The question is how well it compresses. I'm reasonably sure deflation
: is an 8-bit method, so are you going to "get N bits and put them into
: a multiple of 8" or try to pack them? If the latter, that way lies
: madness.

No. No matter which compression method is used, only used bits
will be stored. For example, take a 7 bit GIF and convert it
to 8 bit (leaving the upper half of the palette unused). The
8 bit version will be larger than the 7 bit version.
So why not allow 7 bits (and 3, 5), too?

: >I think 16-bit 'truecolor' hardware will, for the most part, go away.


: >I think it's just a temporary anomoly, as no one would *want* 16-bit
: >truecolor versus 24-bit truecolor. (Whereas 8-bit pseudocolor is
: >still a very useful format, for reasons mentioned elsewhere.)
:
: Maybe, maybe not. Keep in mind that the issue isn't simply one of
: memory sizes but of bandwidth, shielding, and so forth. Boosting the
: bits by 50% (16 -> 24) without boosting the dot clock means your refresh
: rates suck. And 200MHz signals require serious engineering to avoid an
: RF nightmare.

24 bit images can be displayed on 16 bit hardware (and vice versa).
We should not allow 16 bit for the new format just because current
hardware can cope better with 16 bit than with 24 bit. It's best
to always use 24 bit, which can be displayed on 16 bit devices, and
which provides 24 bit quality on 24 bit devices.

I'm still not sure if 24 bit should be supported at all.
8 bit support would be sufficient to replace the GIF format.

: As someone else pointed out, 2D interleaving kills your compression.


: Keep it the same as GIF89, possibly with a bigger interleave factor (I'm
: not sure what the GIF spec says about this).

We should keep it the way it is used in GIF. There is no
reason to change it, and it would complicate writing new
ecoders and decoders.

NOEL_GIFFIN

unread,
Jan 6, 1995, 2:45:00 PM1/6/95
to
In article <3eih8q$n...@netnews.upenn.edu>, bra...@devo.dccs.upenn.edu (John Bradley) writes...

>In article <TGL.95Ja...@netcom16.netcom.com> t...@netcom.com (Tom Lane) writes:
>
>Incidentally, I'm entirely against support for 16-bit images (of
>either variety: truecolor or greyscale). 16-bit truecolor images are
>easy enough to compute from their 24-bit counterparts, and in any event,
>I think 16-bit 'truecolor' hardware will, for the most part, go away.
>I think it's just a temporary anomoly, as no one would *want* 16-bit
>truecolor versus 24-bit truecolor. (Whereas 8-bit pseudocolor is
>still a very useful format, for reasons mentioned elsewhere.)
>
>John Bradley - XV Dude

I agree that the 16-bit format as it currently stands, is fairly useless
and it will probably go away. This I feel could become something fairly
useful if hardware manufacturers added 16 bit colour lookup tables to
their graphics cards. One of the reasons that 8-bit gifs are still so
popular is that they are very easy to manipulate and edit. They contain
a 24-bit pallette information to a 256 colour maximum. Pallette rotation
and editing is so much cleaner than pixel editing. In 24-bit files if
you want to change a certain colour you have to search the whole file for
all occurences and rewrite the pixel information. In 8-bit using a CLUT
you just edit a single instance. The problem with 16 bit modes as they
currently stand is that they are limited to 16-bit pallette information,
which has a very limited spectrum and you have to dither to reduce banding
problems. If graphics cards had a 16 bit addressable CLUT instead of an
8 bit one, (requires additional 3x32kbyte of memory), then a 16 bit graphic
image format which contained 24-bit pallette information would become
very useful indeed. The main problem with the sixteen bit formats as I see
it was the limited available pallette. Remove that and add some hardware
and you have a nice new graphic standard. The limitation of only 65536
different colours on screen isn't nearly so severe if you can choose all those
65536 colours from a full 24 bit spectrum. Think of all the great
animations that could be done with the new pallette range.

This may not be the ideal time to discuss this as the immediate concern
is what to do about GIF, but it's an idea i've been kicking around, so while
everyone is discussing graphic format, I thought I'd put it out there.

Noel Giffin

Mark Adler

unread,
Jan 6, 1995, 3:58:39 PM1/6/95
to

>> 2. Some ancient method such as plain Huffman coding, which will
>> certainly be patent-free by virtue of age. This is likely to give
>> noticeably poorer compression than LZW, however.

Well, almost certainly patent-free. Considering the patents that have
been given, I was just thinking the other day of patenting Huffman
coding and renaming it Adler coding. ;-)

mark

Mark Adler

unread,
Jan 6, 1995, 4:01:15 PM1/6/95
to

>> On the other hand, I think the name should be pronounceable,
>> just like "GIF".

How about PIF (.pif): public image format.

mark

Samuel S. Paik

unread,
Jan 6, 1995, 3:06:12 PM1/6/95
to
John Bradley <bra...@devo.dccs.upenn.edu> wrote:
>Incidentally, I'm entirely against support for 16-bit images (of
>either variety: truecolor or greyscale).

>I think 16-bit 'truecolor' hardware will, for the most part, go away.


>I think it's just a temporary anomoly, as no one would *want* 16-bit

As an aside, 12-bit truecolor seems to becoming popular among low-end
3D machines, this allows for inexpensive double-buffer true-color hardware.

How about a digital signature field?

> support for 24-bit truecolor images,
> with reasonable lossless compression,
> *no* transparent color in 24-bit mode

How about alpha values? Or is this too exotic for today.

Sam
--
Samuel Paik / Digital Equipment Corporation / 3D Device Support
pa...@avalon.eng.pko.dec.com / 508-493-4048 / I speak only for myself

The yin and yang of programming languages (due to Andrew Koenig)

Pure object-oriented programming:
everything is an object, even your program
Pure functional programming:
everything is a program, even your data.

Oliver Fromme (TBH)

unread,
Jan 6, 1995, 6:44:42 PM1/6/95
to

Mark Adler (mad...@cco.caltech.edu) wrote:
: >> On the other hand, I think the name should be pronounceable,

: >> just like "GIF".
:
: How about PIF (.pif): public image format.

This could cause some confusion, since the extension .pif is
already used for something different on DOS/Windows machines.


A few hours ago I made some suggestions about delta transformation.
Please forget whatever I said, because it just doesn't work.
I tried delta conversion on several images -- it does not make
them compress better, no matter what kind of image (greyscaled,
truecolor, color mapped).

By the way, I just read the statement that Unisys also claims
LZW decompression to be covered by their patent. This sounds
very serious to me. We really need to create a GIF replacement
as soon as possible.

Leonardo H. Loureiro

unread,
Jan 6, 1995, 10:41:26 PM1/6/95
to
In article <TGL.95Ja...@netcom11.netcom.com>,
Tom Lane <t...@netcom.com> wrote:

>j...@proteon.com (John Woods) writes:
>> I would like to argue for using exactly GIF89, nothing more and nothing less,
>> with a license-free compression scheme.
>> ...

>> the immediate problem, the sudden absence of the
>> GIF format, is quite handily solved by, well, GIF.
>
>This is a very defensible position, and I more than half agree with it.
>
>I think the reason for this whole discussion is to take stock of the
>features that we need and don't need, then see whether the "value added"
>that can be given by a (reasonably simple) new design would justify the
>extra work needed to implement a whole new format spec. If not, back
>to GIF.

>
>> The featurefest proposals that have been developing here would not
>> really solve the GIF problem ...

>> and will take an infinite amount of time to settle on.
>
>As always, producing a good design will require taste and restraint
>on the part of the designer. Putting everything everyone asks for
>into the stew is not good design. (See TIFF.) Tom Boutell is going
>to try to produce a coherent design from all these suggestions, and
>perhaps one or two others will try their hands if they don't like
>his proposal. We'll have to look at those designs and weigh them
>against the GIF+gzip alternative. Ease of implementation will
>definitely need to be one of the considerations.

>
>> Now, the chief difficulty is getting Compu$erve to agree to it.
>
>I've been talking to the moderators of CIS's graphics forums, and
>from what I hear, it may not be as difficult as all that. I don't
>think that CIS is exactly happy with the current situation either.
>More, they would like the net to continue using GIF, and I believe
>they realize that GIF/LZW is a dead horse.
>
>Keep in mind that CIS thought they were putting a PD compressor into
>GIF to begin with... changing to one that really is PD will just
>adhere to their original goals.

>
>> they will want to have an absolutely ironclad guarantee that the
>> chosen compression format will never, EVER get them into legal trouble
>> again. ... For gzip, GNU's legal opinion that gzip is

>> free of trouble might or might not be adequate; CompuServe's lawyers
>> will certainly need to duplicate the work themselves, and they will be
>> a good deal less optimistic in the face of any uncertainty.
>
>I rather imagine that *everyone* would like them to make exactly such a
>thorough, independent examination! If there is anything dubious about
>gzip's patent status, better to find out now than later.
>
>Now, if they take an unreasonable amount of time about it, that might
>be a problem. Anyone know how long a patent search usually takes?

ahti heinla

unread,
Jan 7, 1995, 5:45:01 AM1/7/95
to
In article <3ejota$r...@ikarus.rz.tu-clausthal.de>,

>How about "PING" ("Ping Is Not Gif") ? The 3 byte extension
>for DOS people could be either .pin or .png.
>Or how about "TNT" ("The New Thing", as Brad suggested) ?
>On the other hand, I think the name should be pronounceable,
>just like "GIF".

LIF (Lightweight Image Format)
--
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Launchpad is an experimental internet BBS. The views of its users do not
necessarily represent those of UNC-Chapel Hill, OIT, or the SysOps.
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

ahti heinla

unread,
Jan 7, 1995, 5:57:41 AM1/7/95
to

re: compression method to use in the new format.

so far, most people comment on using a general purpose compression
algorithm like lz77/lzss/lzhuf/gzip. what about image transforms like 2d
haar transform? haar transform works with integers, is as fast as lzw
(about 1mb/sec for compression). also, if the coefficients are stored in
correct order, it is really perfectly possible to read the file in a
serial manner, aobtaining a coarse image first and adding more detail to
the display as the higher frequency components come down the wire. it's
probably as easy or easier to implement as lzw. i'm not sure of the patent
issues, perhaps someone can shed the light.

ahti

Daniel Quinlan

unread,
Jan 7, 1995, 5:57:58 AM1/7/95
to
Oliver Fromme (TBH) <in...@sun.rz.tu-clausthal.de> writes:

> A few weeks ago I found a collection of compression sources on the
> net. It contained a program called AR002 (or something similar)
> which uses a compression method called LZHUF (maybe a combination of
> LZ77 and Huffman, both of which are patent-free as far as I know).
> The same method is used in the popular LHA archiver, by the way.
> The source is about 500 lines of C (both the encoder and decoder),
> and the implementation seems to be quite easy and straightforward.
> The compression should be better than LZW (on average), and it's
> quite fast and doesn't require too much memory (quite an important
> point). How about this one?

The compression in LHA is somewhat slow, especially compared to the
LZ77 variant that pkzip/gzip uses and it doesn't achieve as good a
level of compression.

> I haven't had a look at the gzip sources yet, but I suspect that it
> is considerably more complicated and more extensive than LZHUF. If
> I'm wrong, well, then let's go for gzip!

Why wimp out?

--
Daniel Quinlan
qui...@best.com

ahti heinla

unread,
Jan 7, 1995, 6:11:22 AM1/7/95
to

i just wrote that haar transform works aat about 1mb/sec for
compression. i forgot to add 'on a i486dx2/66'. sorry.

Howard Wilson

unread,
Jan 7, 1995, 6:49:27 AM1/7/95
to
Oliver Fromme (TBH) (in...@sun.rz.tu-clausthal.de) wrote:

: Basically I agree with Tom. GIF87 covers almost everything that we


: need for a "lightweight" portable format. I'd like to suggest the
: following extensions to GIF87:
: 1. transparency (quite important for the Web),
: 2. some provisions for error recovery, maybe similar to the
: restart markers in JPEG files.

: The format doesn't need to support animations (that's what AVI,
: MPEG, FLI, DL etc. are for) nor multiple images.

: I don't think that the format should support 24 bit images. So far,

Ok, that's mostly the relevant stuff to my statement. B-).

I agree with Oliver here. While I have seen some great proposals regarding
a new all-purpose graphics format that look really cool, I think we MAY be
losing sight of what is needed here. What is needed, as far as I can tell,
is a simple replacement of GIF, possibly with a few minor modifications as
mentioned above. To use Oliver's words...we want a lightweight format here,
not the end-all be-all. As mentioned, animation and 24 bit are covered
by other formats.

Myself, I couldn't find anything wrong with the "GEF" proposal.
Since the heart of the problem is LZW...using something else for
compression would solve the problem. That's assuming CI$ isn't lying
when they say they support GIF.

Howard


--
st...@ionet.net fnord | "And my soul from out that shadow that
I speak for no one but myself, | lies floating on the floor, shall be
and no one else speaks for me. | lifted --- nevermore! - The Raven
Commence strategic maneuvers at audible command signal. 5, 4, 3, 2, 1, begin.
GIF 1987-1994, Rest in Peace. Read comp.graphics for details.

Howard Wilson

unread,
Jan 7, 1995, 6:57:33 AM1/7/95
to
Oliver Fromme (TBH) (in...@sun.rz.tu-clausthal.de) wrote:

: How about "PING" ("Ping Is Not Gif") ? The 3 byte extension


: for DOS people could be either .pin or .png.
: Or how about "TNT" ("The New Thing", as Brad suggested) ?
: On the other hand, I think the name should be pronounceable,
: just like "GIF".

Ummm..."GIF" isn't all that pronounceable, from what I can tell.
Myself, I say it is a hard gee sound, but even I lapse into the
"JIF" from time to time. If the new name DOES turn out to be "GEF", I
shuuder tho think of the thousands of "JEFF" images people will think
they have.

Quick question, just to bring me up to speed...EXACTLY what are we
discussing? (Yes, I should have asked this before my last message).
When I think of "GIF", I think more along the lines of drawings and such,
as JPEG beats it to Hell on actual pictures.

Oliver Fromme (TBH)

unread,
Jan 7, 1995, 7:58:11 AM1/7/95
to
Tom Lane (t...@netcom.com) wrote:
: in...@sun.rz.tu-clausthal.de (Oliver Fromme (TBH)) writes:
: > No. No matter which compression method is used, only used bits

: > will be stored. For example, take a 7 bit GIF and convert it
: > to 8 bit (leaving the upper half of the palette unused). The
: > 8 bit version will be larger than the 7 bit version.
: > So why not allow 7 bits (and 3, 5), too?
:
: [...]
: I believe that what you are proposing for a new format is that 7-bit
: pixel indices would be packed tightly into 8-bit bytes, after which
: gzip would operate on the byte stream. The misalignment would mean that
: short repetition patterns in the pixel stream would not look like short
: repeated byte sequences to gzip. This would surely hurt compression.
: I haven't done the experiments, but I'd bet that representing the pixel
: indexes as bytes, with a "wasted" bit per pixel, would produce a smaller
: file after compression. Question is, how strong is this effect; would
: it justify padding, say, 5-bit data to 8-bit? Maybe even more? Maybe
: the pre-gzip representation should be one byte per pixel for any
: palette-index image, regardless of the palette size. *That* would
: certainly simplify life...

Well, my GIF example was a bit misleading.
Of course you are right, packing an odd number of bits tightly
would certainly hurt compression. As you suggested, it's probably
best to use one byte per pixel, no matter how many bits are actually
used.
But then again, why not allow odd palette sizes? It needn't even
be a power of 2, the palette could contain, say 142 entries.

Oliver Fromme (TBH)

unread,
Jan 7, 1995, 8:02:43 AM1/7/95
to
ahti heinla (Ahti....@launchpad.unc.edu) wrote:
: so far, most people comment on using a general purpose compression

: algorithm like lz77/lzss/lzhuf/gzip. what about image transforms like 2d
: haar transform? haar transform works with integers, is as fast as lzw
: (about 1mb/sec for compression). also, if the coefficients are stored in
: correct order, it is really perfectly possible to read the file in a
: serial manner, aobtaining a coarse image first and adding more detail to
: the display as the higher frequency components come down the wire. it's
: probably as easy or easier to implement as lzw. i'm not sure of the patent
: issues, perhaps someone can shed the light.

As far as I know, Haar transform is NOT lossless, and it can NOT
be effectively used on color mapped images. So this is not the
way to go for a GIF replacement.

Tom Lane

unread,
Jan 6, 1995, 8:24:41 PM1/6/95
to
in...@sun.rz.tu-clausthal.de (Oliver Fromme (TBH)) writes:
> Cave Newt (ro...@ellis.uchicago.edu) wrote:
> : bra...@devo.dccs.upenn.edu (John Bradley) writes:
> : >Once you have to write the 'get some number of bits other
> : >than 8' function, it's easy-ish enough to get an arbitrary number of bits.

> : The question is how well it compresses.

> No. No matter which compression method is used, only used bits


> will be stored. For example, take a 7 bit GIF and convert it
> to 8 bit (leaving the upper half of the palette unused). The
> 8 bit version will be larger than the 7 bit version.
> So why not allow 7 bits (and 3, 5), too?

Not necessarily. The GIF result is not applicable. As used in GIF, the
pixel indices are fed to LZW as separate symbols, not packed into bytes.
In the experiment you describe, the LZW compressor will see the exact
same input symbol series and produce the exact same output symbol series
in both cases. The only effect of increasing the nominal input symbol
size from 7 to 8 bits is that the starting *output* symbol size goes up
one bit. This costs you a small, fixed overhead.

I believe that what you are proposing for a new format is that 7-bit
pixel indices would be packed tightly into 8-bit bytes, after which
gzip would operate on the byte stream. The misalignment would mean that
short repetition patterns in the pixel stream would not look like short
repeated byte sequences to gzip. This would surely hurt compression.
I haven't done the experiments, but I'd bet that representing the pixel
indexes as bytes, with a "wasted" bit per pixel, would produce a smaller
file after compression. Question is, how strong is this effect; would
it justify padding, say, 5-bit data to 8-bit? Maybe even more? Maybe
the pre-gzip representation should be one byte per pixel for any
palette-index image, regardless of the palette size. *That* would
certainly simplify life...

Another consideration is that packing odd-size pixels requires that you
specify the packing order: do pixels that cross byte boundaries appear
with MSBs or LSBs in earlier bytes? This is an additional item of
complexity for the spec, another possible bug for implementors, etc.
etc. TIFF forces implementors to cope with this sort of complexity, but
I think it is better to avoid the problem if possible. If it doesn't
buy a meaningful amount of compression, it certainly isn't worth it.


> I'm still not sure if 24 bit should be supported at all.
> 8 bit support would be sufficient to replace the GIF format.

So it would. But there is no decently compressed lossless 24-bit format
now available (LZW TIFF has gone a-glimmering...). If a gzip-based
format can solve that problem too, I'm inclined to add the feature.


> : As someone else pointed out, 2D interleaving kills your compression.
> : Keep it the same as GIF89, possibly with a bigger interleave factor (I'm
> : not sure what the GIF spec says about this).

> We should keep it the way it is used in GIF. There is no
> reason to change it, and it would complicate writing new
> ecoders and decoders.

Unless someone has hard evidence that some other interleaving rule
is really significantly better than GIF's, I'd say the same.

Tom Lane

unread,
Jan 6, 1995, 7:55:01 PM1/6/95
to
in...@sun.rz.tu-clausthal.de (Oliver Fromme (TBH)) writes:
> How about using lossless JPEG for the 24 bit variant of the new
> format? Or something similar to lossless JPEG? As far as I
> know, lossless JPEG is quite simple and easy to implement (as
> compared to lossy JPEG).

It's relatively easy to implement, all right ... it's just not very
good. At least the freely usable Huffman variant isn't. According to
my limited testing, you can get roughly similar compression ratios just
by applying gzip to the 24-bit RGB data. If gzip will be the
compression engine for palette-index data, we might as well re-use it
for true-color data, rather than require an independent mechanism.

Applying pixel differencing before gzipping might be a win for true-color
data. Or then again it might not; Oliver reports in a later message that
it didn't seem to help. That surprises me a little. It'd probably be
worth doing some more extensive testing...

> Another suggestion for 24 bit images:
> First, the image should be separated into its RGB components
> (perhaps not the whole image, but line by line, because that
> needs considerably less memory on both the encoding and decoding
> side).

The components definitely must not be separated by whole planes, because
that would preclude incremental on-the-fly display. Separating them by
scanlines might be tolerable. But are you sure it's worth the trouble?
If a simple interleaved-pixel RGB representation will compress about as
well, then I'd vote for that. And the differencing result makes me
think that gzip is more robust than you give it credit for.

> A few thoughts about the basic format:

Most of these ideas are already in Thomas Boutell's "lightweight bitmap
format" proposal --- have you seen that? It looks promising to me.

Tom Lane

unread,
Jan 6, 1995, 8:54:55 PM1/6/95
to
j...@proteon.com (John Woods) writes:
> I would like to argue for using exactly GIF89, nothing more and nothing less,
> with a license-free compression scheme.
> ...

> the immediate problem, the sudden absence of the
> GIF format, is quite handily solved by, well, GIF.

This is a very defensible position, and I more than half agree with it.

I think the reason for this whole discussion is to take stock of the
features that we need and don't need, then see whether the "value added"
that can be given by a (reasonably simple) new design would justify the
extra work needed to implement a whole new format spec. If not, back
to GIF.

> The featurefest proposals that have been developing here would not
> really solve the GIF problem ...


> and will take an infinite amount of time to settle on.

As always, producing a good design will require taste and restraint


on the part of the designer. Putting everything everyone asks for
into the stew is not good design. (See TIFF.) Tom Boutell is going
to try to produce a coherent design from all these suggestions, and
perhaps one or two others will try their hands if they don't like
his proposal. We'll have to look at those designs and weigh them
against the GIF+gzip alternative. Ease of implementation will
definitely need to be one of the considerations.

> Now, the chief difficulty is getting Compu$erve to agree to it.

I've been talking to the moderators of CIS's graphics forums, and


from what I hear, it may not be as difficult as all that. I don't
think that CIS is exactly happy with the current situation either.
More, they would like the net to continue using GIF, and I believe
they realize that GIF/LZW is a dead horse.

Keep in mind that CIS thought they were putting a PD compressor into
GIF to begin with... changing to one that really is PD will just
adhere to their original goals.

> they will want to have an absolutely ironclad guarantee that the


> chosen compression format will never, EVER get them into legal trouble

> again. ... For gzip, GNU's legal opinion that gzip is


> free of trouble might or might not be adequate; CompuServe's lawyers
> will certainly need to duplicate the work themselves, and they will be
> a good deal less optimistic in the face of any uncertainty.

I rather imagine that *everyone* would like them to make exactly such a


thorough, independent examination! If there is anything dubious about
gzip's patent status, better to find out now than later.

Now, if they take an unreasonable amount of time about it, that might
be a problem. Anyone know how long a patent search usually takes?

regards, tom lane
organizer, Independent JPEG Group

Hannu Niemi

unread,
Jan 7, 1995, 8:21:00 AM1/7/95
to
-=> Quoting Mad...@cco.caltech.edu to All <=-

>> On the other hand, I think the name should be pronounceable,
>> just like "GIF".

Ma> How about PIF (.pif): public image format.

Microsoft already got that for their Program Interface File (or something like
thta, too lazy to check). Just don't want to get a user complainening his or
her command.pif doesn't show up ;-)

___________________________________________________________________________
Hannu Niemi (hannu...@pcb.compart.fi)
Guilty of writing Windows soft... oops software for Microsoft(R) Windows(TM)

...It always pays to set your goal high - if you try to earn billion dollars
you earn million if you only achieve one per mille of your goal
___ Blue Wave/QWK v2.12

laUNChpad account

unread,
Jan 8, 1995, 2:01:01 AM1/8/95
to
In article <3em3dj$7...@ikarus.rz.tu-clausthal.de>,

Oliver Fromme (TBH) <in...@majestix.rz.tu-clausthal.de> wrote:
>ahti heinla (Ahti....@launchpad.unc.edu) wrote:
>: so far, most people comment on using a general purpose compression
>: algorithm like lz77/lzss/lzhuf/gzip. what about image transforms like 2d
>: haar transform?
>
>As far as I know, Haar transform is NOT lossless, and it can NOT
>be effectively used on color mapped images. So this is not the
>way to go for a GIF replacement.

haar transform itself _is_ lossless (that's why it is called
'transform', i.e. there is a way to convert it back), but most
itsapplications in compression are lossy indeed. they do the transform,
pick a few dominant coefficients, discard everything else, and encode only
these dominant frequencies.
now, i wasn't talking about doing it this way. essentially we could do
something like this (btw, somebody already proposed something along these
lines):
the image n*n is described at lg n levels. the highest level is
only one pixel (essentially the sum of all pixels in the image). the next
level consists of 2*2 pixels for each quarter of the image. the last level
consists of n*n pixels like the original image. now, the image is sent
down the wire starting from the highest level. at each next level, each
pixel expands to 2*2 pixels. but from the preceding levels, we already
know the sum of these four pixels; thus we can encode these four pixels
using only three values. for 8*8 image we thus need to send 1+3+12+48=64
values just like when no encoding is used. but this new representation
could be compressed better than the original image. for pictures
containing even small areas of same color, a lot of values are simply 0. now
comes the trickier part for which i haven't got a great solution: how to
compress this transformed image? the reason that makes it tricky is
that different methods do well for different types of images. there are
several choices:
(1) some variant of adaptive huffman. this is probably the best in
terms of compression ratio. probably can't be implemented easier than lzw.
(2) some simple enough variant of lz*. for each packet of three
values we could simply store a number 1..16 as a distance to its last
occurence. this _should_ be simple enough to bypass patent problems.

as for performance for paletted images: of course, it's worse than
for truecolor. but, perhaps something can be done to improve that. we
could reorder the palette so that colors closer in rgb space are also
closer in palette. furthermore: ok lets assume this is only good for
truecolor images. but plain lz* is only good for paletted images!

my points:
(1) this is almost ideal solution to the interlacing/icon view problems.
(2) is better than plain lz* (our current favourite) for truecolor
images (our current top addition to the gif format).
(3) some further reasearch and ideas are neccessary.
(4) it is/was only a suggestion.

ahti heinla

unread,
Jan 8, 1995, 3:22:00 AM1/8/95
to
oliver fromme wrote:
>: so far, most people comment on using a general purpose compression
>: algorithm like lz77/lzss/lzhuf/gzip. what about image transforms like 2d
>: haar transform?
>
> As far as I know, Haar transform is NOT lossless, and it can NOT
> be effectively used on color mapped images. So this is not the
> way to go for a GIF replacement.

the haar transform itself _is_ lossless, or else it wouldn't be
called 'transform'. most of its applications in compression are lossy,
though. this isn't what i had in mind. what i had in mind was something
along these lines:
we represent the n*n image at lg n levels. the highest level
consists of only one pixel, which is essentially the sum of all pixels
of the image. the next level consists of 2*2 pixels, which are essentially
the sums of pixels in four quarters of the image. next come 4*4 pixels and
so on. each pixel in a given level is is expanded to 4 pixels in the next
level. the image is sent down the wire starting from the highest level.
thus at each 1-->4 pixel expansion we already know the sum of these 4 pixels.
so we need to send only 3 values. so, for a 8*8 image we need to send
1+3+12+48=64 values, which is exactly the same as the total number of pixels
in the image.
so for 24bit rgb image, our next goal is to somehow encode
these values with less than 24 bits (average). essentially what we need
to do is invent a yet another compression method on top of this. but at
least for certain types of images these values are easier to compress than
the original images, so that we need only a simple method. for images
containing at least small (2*2) areas of the same color, a lot of values are
simply 0.
(1) some variant of adaptive huffman. 'some variant' is neccessary
because the range of values is not limited by, say, 256. the values at
higher levels can get quite large.
(2) some simple variant of lz*. for each triad of 3 values we could
send only a number 1..x as the distance to its last occurence. this ought
to be simple enough to avoid patent infringements. it's pretty far from
lz78, and also different from lz77.

as for performance for paletted images: of course, it's worse than
for truecolor. but, perhaps something can be done to improve that. we

could reorder the palette so that colors close in rgb space are also
close in palette. furthermore, ok lets assume it works only for rgb.
but plain lz* works only for paletted images!

my points:
(1) this is almost ideal solution to the interlacing/icon view
problems.

(2) it could work better than lz77 (our current favorite) for
rgb images (our current top addition to the gif format). the new format
could use this transform as a preprocessor only in cases where it improves
the compression ratio.


(3) some further reasearch and ideas are neccessary.

(4) it is/was only a suggestion. worth at least as much as the
derivative method suggested earlier.

Paul Haeberli

unread,
Jan 8, 1995, 3:25:32 PM1/8/95
to

bou...@netcom.com (Thomas Boutell) wrote:
> ... I don't see much reason to include 3, 5, 6 and
> 7-bit depths, since they add computational grief and
> don't represent a significant gain (you can round up
> to the next power of two).

t...@netcom.com (Tom Lane) wrote:
> Palette image storage: essential to keep, though it might be enough
> to support only 4 and 8 bits per pixel, not 1 to 8 as GIF does.
> Odd-size bit depths are more complex to program and don't compress
> very well --- the space savings may be illusory.

I think it's great that people are thinking about a new image file
format to replace GIF, but let's try to make sure we don't replace
it with something that's conceptually broken. I don't think the isssue
of decoder or encoder complexity is something that should prevent
the consideration of supporting images with 3 or 5 bits per pixel.
Some people are suggesting only supporting 4 or 8 bits per pixel!
Let's make sure the space savings really are illusory before we
discard the idea.

The important thing is to make the image file format compact for all
kinds of color indexed images. with 1, 2, 3, 4, 5, 6, 7 or 8 bits.
Also, only RGB colormap values should be stored that are used by
the image. In GIF, if you make an image that uses 129 colors, it
is saved as an 8-bit image. Unfortunately, 256 color map entries
are stored in the file. That's (127*3)=381 bytes wasted.

It might be nice to use the FAX encoding for 1 bit images with
2 colors, if this compresses better than other techniques.

in...@sun.rz.tu-clausthal.de (Oliver Fromme (TBH)) wrote:
> I think it's good the way GIF handles it. A 2D interleaving
> would complicate things very much, and it would certainly
> result in poor compression. I don't think it's worth the
> trouble.

Again, let's not let the implementation difficulty prevent
us from doing the right thing. 2D progresive transmission may
be a very nice thing to support in addition to 1D interleaving.
If there is a choice, whoever compresses the image can decide.

On another point, It could be very nice to include a field
in the images that specifies the GAMMA of the image. This
must be carefully defined, but could be very usefull to make
sure that images don't appear dark on some machines and
washed out on others.


--

paul haeberli
pa...@sgi.com

Bill Davidson

unread,
Jan 9, 1995, 3:58:28 AM1/9/95
to
In article <6JAN1995...@reg.triumf.ca>, NOEL_GIFFIN <no...@reg.triumf.ca> wrote:
>I agree that the 16-bit format as it currently stands, is fairly useless
>and it will probably go away. This I feel could become something fairly
>useful if hardware manufacturers added 16 bit colour lookup tables to
>their graphics cards.

Actually, I believe that Amiga's can display 4096 colors (12-bit pixel
entries would be required).

I'm not sure if it makes sense to implement something that's not really
supported by hardware. Is there any other hardware out there that uses
more than 256 colors but isn't true-color 24-bits? Amigas can't last
too much longer.

In fact, a 64K CLUT would provide more than enough colors for most
images to display with almost no color quantization loss but the point
seems to be becoming moot as 24-bit cards with decent resolution are
becoming more affordable all the time.

I guess what I'm saying is that it's a nice thought but it's probably
not very important. On the other hand, I don't think it really adds
that much weight to the spec or the implementation code so why not?

--Bill Davidson

Reply all
Reply to author
Forward
0 new messages