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

: 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

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.

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'.

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

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.

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.  :-)

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

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.

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

John Bradley  -  XV Dude

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.

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).

: 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

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.

Ditto.

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. :-) )

Yup.

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).

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

Greg Roelofs
Info-ZIP UnZip Dude

: brad...@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.

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

        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

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

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

mark

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?

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

Sam
--
Samuel Paik / Digital Equipment Corporation / 3D Device Support
p...@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.

: >> 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.

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

In article <TGL.95Jan6175...@netcom11.netcom.com>,

In article <3ejota$...@ikarus.rz.tu-clausthal.de>,

        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.
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

        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

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

Oliver Fromme (TBH) <i...@sun.rz.tu-clausthal.de> writes:

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.

Why wimp out?

--
Daniel Quinlan
quin...@best.com

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

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

Oliver Fromme (TBH) (i...@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.

Oliver Fromme (TBH) (i...@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.

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.

: i...@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.

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

:         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.

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

i...@sun.rz.tu-clausthal.de (Oliver Fromme (TBH)) writes:

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.

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.

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

                        regards, tom lane
                        organizer, Independent JPEG Group

i...@sun.rz.tu-clausthal.de (Oliver Fromme (TBH)) writes:

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...

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.

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

                        regards, tom lane
                        organizer, Independent JPEG Group

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.

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.

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.

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

 -=> 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.ni...@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