Deterministic Prediction of Pels Produced by the Line-Preserving Binary Image Reduction Algorithm to Maximize Data Compression
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Arps, RB: AUTHOR [+3]
Disclosed is a method for deterministic prediction of pels in adaptive data compression systems that use reduction algorithms having directional bias. The invention improves image-quality output by such systems.
Deterministic Prediction of Pels Produced by the
Binary Image Reduction Algorithm to Maximize Data Compression
a method for deterministic prediction of pels in
adaptive data compression systems that use reduction algorithms
having directional bias. The invention improves image-quality output
by such systems.
compression system implementing progressive bi-level
coding comprises a compression stage and a reconstruction stage. In
the former, original image data is compressed in a series of
reduction/ compression steps, each of said steps reducing a
higher-resolution image by a factor of two to produce a
lower-resolution image and corresponding encoded data. The encoded
data preserves contextual information about the preceding
higher-resolution image which will later be used to reproduce the
reconstruction stage, compressed data is reconstructed
in a series of decompression/enlargement steps, each of said steps
producing a higher-resolution image from a lower-resolution image and
the contextual compressed data using a deterministic prediction
Anderson and Mintzer have disclosed 
published  a resolution reduction algorithm for binary images
that preserves the presence of black lines and/or lone black pels
after reduction. This reduction algorithm has been combined with
adaptive data compression to define progressive binary image
compression coding systems with improved image quality for the
required reduced resolution images .
line-preserving algorithm is used to reduce the
resolution of an image by a factor of two in both vertical and
horizontal dimensions, it successively deletes alternate rows and
columns while preserving lone black pels flanked by white pels.
These "lonely" black pels contain information which would otherwise
be lost in the deletion process.
Preserving algorithm is from a class of reduction
algorithms that have "directional bias." For instance, in this
algorithm lonely black pels are moved UP into a flanking white pel
during horizontal row deletion, and LEFT into a flanking white pel
during vertical column deletion (UP-LEFT directional bias). The
invention disclosed is adapted for use with the Line-Preserving
Binary Image Reduction Algorithm of Mintzer having a DOWN-RIGHT
directional bias, but may be adapted to other reduction algorithms
having a directional bias.
A lower resolution image is enlarged at each
enlargement/ decompression step by a factor of 2:1 in both dimensions
prior to decompression. Such enlargement merely provides a temporary
higher resolution image until deterministic prediction is performed.
Any suitable enlargement algorithm may be implemented.
illustrates how a lower-resolution image (reference) and
a higher-resolution image (to be encoded) may be aligned. Each set