Browse Prior Art Database

Deterministic Prediction of Pels Produced by the Line-Preserving Binary Image Reduction Algorithm to Maximize Data Compression

IP.com Disclosure Number: IPCOM000111042D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 153K

Publishing Venue

IBM

Related People

Arps, RB: AUTHOR [+3]

Abstract

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.

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

Deterministic Prediction of Pels Produced by the Line-Preserving
Binary Image Reduction Algorithm to Maximize Data Compression

      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.

      A data 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
same.

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

      Reduction - Anderson and Mintzer have disclosed [1]  and
published [2]  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 [3].

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

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

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

      Fig.1 illustrates how a lower-resolution image (reference) and
a higher-resolution image (to be encoded) may be aligned.  Each set
of high-re...