Updated date:

The History of IBM Technology in Image Compression

Author:

Jack is a volunteer at the CCNY Archives. Before retiring, he worked at IBM for over 28 years. As of 2/2020, Jack has over 100,000 views.

the-history-of-ibm-technology-in-image-compression

Introduction

As a former member of a small group of technologists working at IBM Research back in the 1980-2000, I have a unique perspective on the work done in image compression and digital image processing. These important inventions are still used today in every image captured by digital cameras and transmitted across the world via the web and every youtube video you watch. Here is the story of some of the people and their achievements.

This story needs to be told and I am just honored to have a small part in this story.

- Oct. 2020

Background

In the olden days, sending an image across a 2400 baud line is really slow and painful. Where there is a need, there is room for inventions. The idea is simple. If we can come up with a scheme to compressed the data size and send it and on the receiving side decompress it and voila, you have a good solution.

That is the start of image compression technology. The idea is simple but to implement the actual algorithm not so much. As it turn out, there are many competing algorithms and all claim to be better than the next. It takes some work to sort them out and a standards committee to over see this process.

The Process...

The process of coming up with a standard is long and tedious. For example, the CCITT Group 3 FAX standard took many years to approve and adopt.

The algorithm is Huffman encoding that uses run-length encoding to get the maximum compression. This standard is a lossless algorithm which is the best quality possible. The idea takes advantage of text documents which comprises of black text against a white background. By using a set of standard documents that are representative of most office scanned documents, developers and technologist could come up with statistics of the run-lengths distribution. Once they have a good set of statistics, the next step is to assign the optimal codes to represent these runs.

It is an iterative process to run the algorithm or simulate them against the same set of documents and see the compression factor. The best codes will produce the smallest number of compression bytes and thereby speed the transmission.

Tools...

it You might think it is easy to develop algorithms for compression, or anything for that matter. It requires a bit of genius, a lot of hard work and having the right tools to implement it. In IBM Research, part of the reason we were successful is because of home grown tools. One example I will highlight here is the creation of a programming language that was used extensively by our small team of scientists, engineers and programmers. You never heard of this language and probably never will. It is called PDS - Program Development System.

It was invented by Gerry Goertzel and developed and supported by Karen Anderson for the host VM system and later ported to the IBM PC by Jim Morgan. Karen also did a lot of work on cross-assemblers for other machines. This gave us another advantage in that we could program to experimental machines for which C compilers did not yet exist.

Why was this important?

In traditional programming language like Fortran, C and PL1 and Cobol, you have to write the program, compile it and then execute it to get results. This is a tedious process and slows down the development process where you are trying small changes to get an incremental improvement in performance.

The genius of PDS is that it is interactive. That is to say, this development workspace allow one to write code as functions which can be executed immediately. The second important aspect of PDS, it allows the programmer to use assembly language to code. This is machine specific. By understanding how the underlying hardware works, we are able to move data and manipulate bits at the register level. Most all other programming languages at the time do not allow such access.

Why is this an advantage?

Speed of execution is foremost. When it comes to image processing algorithms, it is the basic kernel that is absolutely critical to getting a fast computation. This kernel or subroutine is called upon millions of times in repetition to process the whole image. If you can reduce the instruction set by even a few steps, you can speed up the whole operation significantly.

It was the tool that gave our small group at IBM Research the advantage no one else have even at the rest of IBM.

Side Note: PDS uses polish notation for calculations. One advantage of this scheme is that you need not use parenthesis.

Image Compression...

Our small group was called Image Technologies and it was only about a dozen people. I was fortunate enough to be part of an Ad Tech group working on imaging that was based at Research even though we were part of the Communications Division of IBM. A reorganization back in the mid 1980s, combined our two groups since we were working on similar projects that have both research content and product applications.

There was two members of our group that worked on image compression. Joan Mitchell and Bill Pennebaker. Both were highly trained PhDs and experts in their fields. They hold combined hundreds of patents. Their job was to work on improving algorithms in image compression first in binary images, then grayscale and color and finally videos.

These algorithms must be tested and revised and improved on a schedule set by the International Standards committee. They would meet periodically to evaluate the progress from various groups and a final decision was made to select the best algorithm possible that will give the best quality and performance overall.

Cesar Gonzales was another member of our group and later became the group manager. He was instrumental in the development of MPEG and worked closely with Bill and Joan.

Bill and Joan wrote the classic text books on JPEG and MPEG standards which is still taught and used today by graduate schools. Check the Amazon links below.

Impact on IBM Products...

Some have the misconception that we at IBM Research are just playing in our sand box. That is not true. Our inventions and algorithms are embedded in many of the products in the IBM product line both hardware and software.

Here are just some small examples of image processing routines used:

  • compression and decompression subroutines for mainframe and PCs
  • image scaling
  • Image sharpening
  • Image rotations
  • Watermarking, visible and invisible
  • JPEG, MPEG, TIFF and other file formats
  • Facsimile systems
  • Digital Libraries
  • Color image printing

Summary

A group of our past members had a reunion a few years ago in 2017. Check out the link below and see the various members of some of our team. Unfortunately some could not make it in person and some have past away.

I will be adding pieces to this article as I develop more content on some of the other contributions of our group in the area of Color Image Processing, Printing, and watermarking...and Digital library and image capture technologies. Please check back periodically for additions.

Postscript

I reached out to our manager Fred Mintzer who has copies of both books signed. I was able to borrow them since I could not find my copy of the book in my basement.

Here are a few photos from the books.

JPEG

the-history-of-ibm-technology-in-image-compression

JPEG Dedication Page

the-history-of-ibm-technology-in-image-compression

JPEG Acknowledgements Page

the-history-of-ibm-technology-in-image-compression

JPEG and IBM Products

the-history-of-ibm-technology-in-image-compression

MPEG

the-history-of-ibm-technology-in-image-compression

MPEG Dedication Page

the-history-of-ibm-technology-in-image-compression

MPEG Acknowledgements Page

the-history-of-ibm-technology-in-image-compression

Additional Details from Cesar Gonzales

No question Bill and Joan were key players in JBIG (most modern fax standards) and the JPEG standards, including JPEG 2000. I would say that in all cases their most important contribution was in getting arithmetic coding accepted as a valid (and better) coding technique as compared to Huffman coding, which was a well established and "old" statistical coding technique. Thanks to Bill and Joan, I was introduced to arithmetic coding and worked for and with them in putting the IBM proposal for the JPEG standard. While only the arithmetic coding part of the proposal survived, all the merit goes to Bill and Joan and our colleagues at Almaden that invented arithmetic coding (Pasco and Rissanen) for IBM's impact on these standards. As for MPEG, Joan and Bill were editors and wrote parts of an important book summarizing the MPEG-1 and MPEG standard; however, I have to honestly say that they did not participate or influence the standard in any way that I am aware of other than to help propagate the standard through their book. My group (Eric Viscito, Lascoe Allman, Tom McCarthy, and others) used the knowledge we inherited from Joan and Bill to also introduce and propose arithmetic coding to MPEG. While we did not succeed in getting AC in MPEG-1 and MPEG-2, the organization ultimately adopted it for MPEG-4/H.264 and beyond, standards which are the most widely adopted compression standards in video today.

The Importance of History

One great example of technology that changed the world is the UPC. The barcode which appears on every product sold and every product shipped by Amazon...

The inventor of the barcode was Norman Joseph Woodland. He was an IBMer.

You probably never heard of him. He was oddly enough a member of the Manhattan Project, the group of engineers and scientists that developed the first atomic bomb.

The barcode is simple enough but the genius of it is making it a standard that is adopted worldwide. It is like the Morse code. Just dots and dashes and yet, for a time period, it was the fastest transmission of information.

The barcode is just bars of lines of thin and wide between white spaces. The code is robust enough to catalog a vast amount of products.

The first UPC-marked item ever to be scanned at a retail checkout was a 10-pack (50 sticks) of Wrigley's Juicy Fruit chewing gum, purchased at the Marsh supermarket in Troy, Ohio, at 8:01 a.m. on June 26, 1974.[6] The NCR cash register rang up 67 cents.[7] The shopping cart also contained other barcoded items but the gum was the first one picked up at the checkout. The gum packet went on display at the Smithsonian Institution's American history museum in Washington, D.C.

A barcode has 13 numbers. That is 10 to the power of 13 unique codes. A simple invention, combined with a standard, is now the system that help move millions of items from point A to point B. Amazon could not ship all those items in 2 days delivery without the automation that comes from the use of barcodes.

Some Related Info

Book on Image Compression Standards

This content is accurate and true to the best of the author’s knowledge and is not meant to substitute for formal and individualized advice from a qualified professional.

© 2020 Jack Lee

Comments

Jack Lee (author) from Yorktown NY on October 07, 2020:

Raymond, thanks for checking in. There are many technologies we take for granted today that originated from IBM, including the barcodes, magnetic disks, Fortran programming, APL, and many many more...

Raymond Philippe from The Netherlands on October 07, 2020:

I honestly never realized IBM played such an important role in image compression. For one thing, it has surely saved me a lot of disc space ;-)