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

Parameter Reduction and Context Selection for Compression of Gray-Scale Images

IP.com Disclosure Number: IPCOM000043425D
Original Publication Date: 1984-Aug-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR [+3]

Abstract

This invention relates to a method for compressing digitized signals (event values) comprising the steps of: (a) partitioning the event values to be encoded into equivalence classes; (b) determining conditioning contexts where a partition of the event value may comprise a context component; and (c) encoding the event value by (1) the equivalence class conditioned by the context and (2) encoding the event value within the equivalence class unconditionally. Relatedly, a context component may include a partition based on a prior encoded event value. Also, the encoded event may include an error value obtained from a linear prediction model. Error is the difference between actual and predicted values.

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

Page 1 of 2

Parameter Reduction and Context Selection for Compression of Gray-Scale Images

This invention relates to a method for compressing digitized signals (event values) comprising the steps of: (a) partitioning the event values to be encoded into equivalence classes; (b) determining conditioning contexts where a partition of the event value may comprise a context component; and (c) encoding the event value by (1) the equivalence class conditioned by the context and (2) encoding the event value within the equivalence class unconditionally. Relatedly, a context component may include a partition based on a prior encoded event value. Also, the encoded event may include an error value obtained from a linear prediction model. Error is the difference between actual and predicted values. Further, the linear model presupposes a template (context) for computing a predicted value from the history in the neighborhood of the instantaneous point. Since the error is available historically, it has a distribution. The term "bucket" is the range of error values to be encoded. Also, the term "partition" is the mapping of error values into the appropriate bucket. In the compression of multi-level (color or gray) image data, effective compression is obtained economically by judicial selection of the mode. This involves reducing the number of coding parameters to describe a distribution when several contexts are involved, and choosing contexts for which variations in distribution are expected.

Fig. 1 illustrates a portion of the two-dimensional raster scan of the illumination levels z(x,y) of an image. (Levels z(x,y) can be viewed as a third dimension.) Relative to "picture element" (pixel) z(0,0) at the origin, the figure shows a number of its neighboring elements with their coordinates.

(Image Omitted)

We can pass a unique plane with the equation f(x,y) = ax + by + c

(2.1) where x and y are the coordinates in the x and y directions, and where a, b, and c are constant coefficients, and where f(x,y) is the value of the height above point (x,y). Let the plane P1 be passed through the three pixel points (-1,0), (-1,1), and (0,1) of respective heights z(-1,0), z(-1,1), and z(0,1). Plane P1 can be used as function f to estimate or "predict" the pixel value z(0,0) as follows: f(0,0) = c = z(-1,0) + z(0,1) - z(-1,1) for 0 < c < 255,

(2.2) f(0,0) = 0 for c O 0 and f(0,0) = 255 for c > 255. Here, each pixel is assumed to lie in the range [0,255]. The two-dimensional array {z(x,y)} is converted to a linear one Lz(t)1, t = 1,2,..., obtained by scanning the picture row-by-row (raster-scan order) starting in the uppermost row and progressing from left to right. If the "current" pixel z(0,0) is z(t), then the prediction ...