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

N-dimensional Scan in a Universal QIC-122 CODEC

IP.com Disclosure Number: IPCOM000108928D
Original Publication Date: 1992-Jul-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 2 page(s) / 93K

Publishing Venue

IBM

Related People

Medan, Y: AUTHOR

Abstract

Described is a method to enable better compression results for information streams which are arranged in N-dimensional structures, such as still and motion pictures, than QIC-122 or LZ-1 type algorithms.

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

N-dimensional Scan in a Universal QIC-122 CODEC

       Described is a method to enable better compression
results for information streams which are arranged in N-dimensional
structures, such as still and motion pictures, than QIC-122 or LZ-1
type algorithms.

      Employed is a programmable N-dimensional (N-D) scan process for
enhancing the compression of multi-dimensional information sources.
The approach is based on identifying three key parameters which
govern a scan process that can preserve the adjacency of the matched
data in information tiles.  The set can be compactly defined for the
Universal QIC-122 Codec using one of the available Control Codes.  A
default setting of a linear (1-D) horizontal scan provides
compatability with the current QIC-122 standard (see (*)).  The
novelty of the method is in specifying a generic scan process using a
compact set of parameters that enables performance matches of
N-dimensional tiles rather than simple 1-D strings.  Data elements
which are adjacent in the original information domain are compared
against new adjacent data clusters in order to find a match.

      In a typical LZ-1 type compression scheme, such as QIC-122, it
is assumed that a byte-oriented input stream is to be encoded using a
mixture of direct coding - stating the actual value of the byte ('raw
byte') and indirect coding - using an offset and a runlength values
to point to a previous instance of a given string (compressed byte)
that is contained in an adjacent history buffer.  The size of this
buffer is limited by practical considerations so that a reference can
be made to near-term data.  N-dimensional information sources are
digitally stored as a single long vector which results from scanning
the source along its leading dimension repeatedly until all data is
covered.  For example, a 2-D source like an image is typically
scanned row-wise until all rows are stored.  When it is desired to
compress such a source using an LZ-1 type algorithm, data elements on
adjacent rows are separated by Nr data elements, where NR is the
number of elements per row.  Since the algorithm attempts to find a
sequential match of the incoming string to one that already exists,
it i...