Posts Tagged ‘LZW’

Briefly about GIF

Hi folks,

Today we will try to give you a quick overview on the GIF file format.

GIF format was introduced by CompuServe in 1987 and soon became widely adopted because it supported colours (unlike its CompuServe predecessor, RLE) and it was small-sized (thanks to the LZW lossless compression algorithm, we’ve told you a story about that in a previous article), allowing reasonably fast file transfers even for the slow, dial-up modems era.
CompuServe was a company way ahead of its time.
It was founded in Columbus, Ohio, in 1969 (the “prehistory” of the internet) by an insurance company (“Golden United Life Insurance”), initially to provide computing power for in-house optimization of the data-management needs of the mother company but shortly CompuServe became a serious business on its own, some naming it “the Google of the 70’s and 80’s”.
First they rented computing power time to other companies (when computers were idle), then a long series of pioneering achievements followed, here is an incomplete enumeration: one of the first companies to offer online services, world’s first online service offering internet connectivity, issued and hosted thousands of moderated forums, created a file transfer protocol, developed its own (proprietary) email services, hosted the first WYSIWYG email and forum posts content, pioneered the online shopping, created customized portals, pioneered online financial services, created an online chat system, introduced online games and published the first online newspaper and the first online comics.
And invented GIF, of course.

GIF (“Graphics Interchange Format”) is a bitmap graphics file format, its first version being referred to as GIF 87a, to indicate the year of release, 1987.
Two years and many enhancements later, GIF 89a version was introduced and it accounts for the vast majority of GIFs currently existing on the internet.
It provides image designers with 256 colors, allows multiple images storage for animation purposes (not in the sense of multipage, as in TIFF), provides controls for animation (animation speed and single/infinite loop option), allows on-or-off transparency (no intermediary gradients of transparency, as in PNG), provides lossless compression and introduced interlacing as an option.

Interlacing, when it concerns image files, means the image is gradually rendered by a browser but rendering starts immediately after download starts so, at first, the image looks unclear, like being out of focus, then, as its download continues, it becomes sharper and sharper, finally showing in full quality when image download is complete.
Previously described Progressive JPEG and the soon to be described PNG formats provide optional interlacing feature, too, but while in GIF and Progressive JPEG case interlacing changes the rendering order of the horizontal lines, the PNG format allows changing the order both horizontally and vertically.

As for compression, GIF uses the LZW lossless compression algoritm eversince it was created.
LZW was a perfect fit for its 8-bits-per-pixel color encoding (ie, maximum 256 colors displayed at one time in a frame) as well as for the animation feature, because GIF animation works by successively displaying bitmap images slightly different from one another (frames), their most part remaining unchanged so, being repetitive, most data are subject to very efficient compression by LZW.
GIF format isn’t commonly used for photos because compressing only 256 colors, even in a lossless manner, provides much poorer results than lossy compressing some 16 millions colors, like JPEG does.

Although the LZW algorithm was/is a major contributor to GIF’s popularity and widespread, it also gave it almost 10 years of torment (since about 1994 until about 2004) caused by the Unisys patent protection controversy.
But nowadays GIF format enjoys times of peace and recognition which will probably continue to last as long as people will keep their apetite for logos, icons, animated emoticons, low-res short clips, educational animated clips and so forth.
In 2012, this venerable format received public tribute from the Oxford Dictionaries USA subsidiary of Oxford University Press, the word “GIF” being granted the “Word of the Year” title, both as a noun and as a verb.
So now the question is: to GIF or not to GIF ?

We will try to answer this shakespearian question in a future article about which bitmap format fits best for which purpose, as PaperScan supports them all.

See you next week!

Bogdan

Big Browser on May 31

Apple 1 from 1976 signed by Wozniak sells for $650,000 Read article Game of Thrones Pirates Break BitTorrent Swarm Record Read article Google’s new “Moto X” superphone will spy on you 24/7, and you’ll like it Read article The Rise of the Mobile-Only User Read article Wary of Bitcoin? A guide to some other cryptocurrencies Read article

LZW and 3 graphics file formats

Hi folks,

This week we are going to tell you a short story about LZW compression and how it influenced 3 widespread graphics file formats: TIFF, GIF and PNG.

The story begins in 1977 and 1978 when israeli computer scientists Abraham Lempel and Jacob Ziv published descriptions of lossless data compression algorithms named LZ-77 and LZ-78, respectively.
Terry Welch, an MIT trained computer scientist, further developed the LZ algorithms and, in 1984, he published the Lempel-Ziv-Welch (LZW) algorithm.

LZW compression became the first widely used universal data compression method on computers.
Being so influential, the “LZ-” based various algorithms became, of course, subject to patent protection in many countries.
For LZW, two patents were issued in the USA (but in other countries as well), the one filed by Welch himself being assigned to Sperry Corporation (Welch’s employer) in 1983.
Sperry Corporation became Unisys in 1986.

So.
Just to have a glimpse on the algorithm, consider this string: “The cat chases the mouse in the room”
The word “the” occurs 3 times.
Replace it by “!” and the string becomes: “! cat chases ! mouse in ! room”.
Add this association (“the” to “!”) to an index and you’ve reduced the length of the string from 36 to 30 characters.
Of course, things are way more complicated than this but the main idea is that the algorithm works very well when there are many repetitive data.
And image files usually contain lots of repetitive data.

In 1986, Aldus Corporation released the first official TIFF specification and in 1988 revision 5.0 was released, which included the ability to use LZW compression.
In 1987, CompuServe created the GIF file format, the GIF specification requiring the use of the LZW algorithm to compress the data stored in each GIF file.

The holder of Welch’s LZW patent, Unisys (which maintains a portfolio of about 1500 patents), was motivated to monetize this patent as much as possible and it had to be fast, too, as the patent availability was 20 years.
Overall, the total number of licensees was about 100, among which Adobe was licensed in 1990 for the use of LZW patent for PostScript and Aldus was licensed in 1991 for the use of the Unisys LZW patent in TIFF.
Licensed LZW in TIFF generated a wave of discontent so Aldus quickly introduced JPEG compression in TIFF (as of revision 6.0 in June 1992) but it had serious design errors and limitations, making things even worse (this was later corrected and replaced with a totally new TIFF/JPEG specification).

But it was not before 1993 that Unisys finally became aware that the GIF file format, very popular already, was using their patent-protected LZW algorithm.
And CompuServe had no clue they were infringing on LZW patent.
In 1994 Unisys and CompuServe came to an understanding which, for various reasons, generated a huge protest reaction, the matter being reported by many newspapers including the Time Magazine.
Many upset developers and users removed their GIF files or converted them to JPEG (yes, JPEG again, it’s royalty-free!).
But JPEG uses lossy compression, so one of the protesting groups, formed by leaders of the online graphics community, began working on a lossless and patent-free version of GIF.
Their efforts produced the PNG specification.

As an epilogue, by 2004 all Welch (ie, Unisys) LZW patents expired in all countries where they were issued (IBM patent on LZW expired by 2006).
TIFF specifications are now controled by Adobe and LZW can be freely used with it.
Adobe uses for PDF a LZ-77 based compression algorithm named “DEFLATE”.
GIF format is still popular.
PNG became one of the most important graphics file formats in the world.

In the upcoming articles we will provide some explanations on bitmaps as well as some short overviews on the most common bitmap file formats, including TIFF, GIF and PNG.

Bye for now!

Bogdan

Big Browser on April 19

Netflix says it’s dumping Microsoft Silverlight and embracing HTML5, someday Read article Hijacking airplanes with an Android phone Read article A non-mathematical explanation of one way functions Read article Silicon Valley Goes Hollywood: Top Coders Can Now Get Agents Read article Plan your digital afterlife with Google's Inactive Account Manager Read article

Casual Friday on April 19

A duck family crosses the street