Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Reduced Run-Length Encoding for Bi-Level Image Compression

IP.com Disclosure Number: IPCOM000114889D
Original Publication Date: 1995-Feb-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 115K

Publishing Venue

IBM

Related People

Pan, ST: AUTHOR

Abstract

Disclosed is a method for achieving further data reduction in run-length encoding for bi-level image compression. Run-length encoding has been an integral part of several standard image formats, for example the TGA or the TIFF formats. It is also the foundation of the most widely used bi-level image compression standards: the CCITT Group 3 and Group 4 standards, originally designed as facsimile (FAX) encoding methods for transmitting documents over telephone networks. The run-length encoding for a bi-level image is briefly described as follows.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Reduced Run-Length Encoding for Bi-Level Image Compression

      Disclosed is a method for achieving further data reduction in
run-length encoding for bi-level image compression.  Run-length
encoding has been an integral part of several standard image formats,
for example the TGA or the TIFF formats.  It is also the foundation
of the most widely used bi-level image compression standards: the
CCITT Group 3 and Group 4 standards, originally designed as facsimile
(FAX) encoding methods for transmitting documents over telephone
networks.  The run-length encoding for a bi-level image is briefly
described as follows.

      A bi-level image is represented by m scan lines with each line
containing n pixels (Figure for m=18 and n=18).  Note that CCITT's
standards requires at least 1728 pixels per each line.  Each pixel
has a binary value of 1 representing a black color and 0 representing
a white color.  Although a binary bit map of m x n bits is required
for displaying or printing the image, it may not be very efficient
when the image is stored or transmitted in its original bit-mapped
format.  The "run-length encoding" is a common technique used to
alleviate this problem by representing the bit-mapped image in a
different format.  Instead of using the straightforward bit mapping,
the run-length encoding uses the run lengths of 0 and 1 on each scan
line.  For example, in the Figure, the binary bits representing the
5th scan line is {0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0}.
With the run-length encoding, this binary bit string is represented
by the run lengths of 0 and 1 on the same line, namely, {3, 5, 2, 3,
5}.  By convention, each scan line begins with a white run.  If the
first pixel is black, then a white run length of zero is used.  For
example, the 15th scan line of the Figure is represented by run
lengths {0, 7, 11} instead of {7, 11}.  Notice that with this
convention, the encode for the black/white level of each pixel (i.e.,
0 for white and 1 for black) is not necessary since each scan line
will start with a white run and black/ white runs are always
alternating within the same line.  The advantage of using the
run-length encoding is that it can transform the entire binary bit
map into sequences of "source symbols" representing the run lengths
of 0 and 1, and the source symbols can be further encoded using any
efficient prefix code (a special kind of variable-length code).  The
CCITT's standards have chosen the Hoffman code for the source symbol
encoding.  The basic idea of the Hoffman code is to assign the
smallest number of binary bits to represent the most frequently
occurred symbol.

      Disclosed in this invention is a simple idea that leads to a
further reduction of the source symbols (i.e., the run lengths)
required to encode a bi-level image u the run-length encoding.  In
fact, by a careful inspection of the above method, one can easily
discover that the requirement f...