Acontext-basedadaptivelosslessnearly-losslesscodingscheme资源-CSDN文库

lossless

compression

需积分: 6 6 浏览量 2015-09-08 16:53:30 上传评论收藏 256KB PDF 举报

资源推荐

资源详情

资源评论

A Context-based, Adaptive, Lossless/Nearly-Lossless Co ding

Scheme for Continuous-tone Images

Xiaolin Wu



Department of Computer Science

The University of Western Ontario

London, Ontario, Canada N6A 5B7

wu@csd.uwo.ca

519-661-3561

Nasir Memon

Department of Computer Science

Northern Illinois University

DeKalb, Illinois, U.S.A. 60115

memon@cs.niu.edu

815-653-6944

Khalid Sayood

Department of Electrical Engineering

University of Nebraska-Lincoln

Lincoln, Nebraska, U.S.A. 68588

ksayoo d@eecomm.unl.edu

402-472-6688

July 5, 1995

1 Summary

We propose a context-based, adaptive, predictive coding system for lossless/nearly-lossless

compression of continuous-tone images. The system provides b etter compression than other

lossless image co ders in the literature. This is accomplished with low time and space

complexities. The high co ding eciency of the proposed image compression system is due

to the use of a novel, nonlinear, context-based predictor; the low time and space complexities

are made possible by an ecient technique for forming and quantizing prediction contexts.

The proposed co ding system gives an average

lossless bit rate of 2.99 bits/pixel

on the 18 8-bit test images selected by ISO for prop osal evaluation, versus an average

bit

rate of 3.98 bits/pixel for lossless JPEG

on the same set of test images (we cannot

compare the two methods on images of higher than 8 bit intensity resolutions, b ecause

there is no available implementation of lossless JPEG to handle these images). Even more

encouragingly, our system obtains

1 % lower bit rate

than the recent UCM (Universal

Context Modeling) metho d [6]. The latter is a highly sophisticated and complex context-

based image co ding technique which was considered to be indicative of lower bound on

lossless bit rates achievable by other more practical metho ds. Furthermore, in its nearly

lossless version, the proposed image co der yields signicantly higher compression than the



The contact person.

current JPEG standard for the same ob jective quality measure such as PSNR and MSE

when the p eak errors are bounded by



3, and



We need to stress the fact that the context mo deling and prediction modules of the

proposed system are algorithmically very simple, involving mostly integer arithmetic and

simple logic. The prediction and modeling comp onents of the enco der and deco der require

only

1.52 CPU seconds

on 512



512 continuous-tone images, and

2.28 CPU seconds

720



576 continuous-tone images, when b eing executed on a SUN SPARC10 workstation.

Both the encoding and deco ding algorithms are suitable for parallel and pip eline hardware

implementation while supp orting sequential build-up. By adding the time sp ent on entropy

coding, one gets the total execution time of the encoding or decoding pro cess. The prop osed

image co ding system is symmetric, meaning that the enco der and decoder have the same

time and space complexities.

The prop osed system encodes and decodes images in raster scan order with a single

pass through the image. The coding pro cess uses prediction contexts that involve only the

previous two scan lines of coded pixels. Consequently, the enco ding and decoding algorithms

require a simple double buer that holds two rows of pixels that immediately proceed the

current pixel. Besides the space for double buering, the system uses only a total of

3.3K

bytes

of working memory, regardless of image sizes.

A schematic description of the co ding system is given in Fig. 1. The blo ck diagram

depicts only the enco ding pro cess. The deco ding is just a reverse process.

The co ding system operates in two mo des: binary and continuous-tone modes. The

binary mo de is for the situation in which the current lo cality of the input image has no

more than two intensity values, hence it is designed for a more general class of images than

the class of black-and-white images. The system automatically selects one of the two mo des

depending on the context of the current pixel. In the binary mode, a context-based adaptive

arithmetic coder is used to co de three symbols, including an escape symbol.

In the continuous-tone mode, the gradient of the image at the current pixel

is esti-

mated. A gradient-adjusted prediction

is made. The gradient-adjusted predictor

has a higher precision than existing DPCM predictors, particularly in the areas of strong

edges. The predictor

is further improved by an error feedback technique, resulting in an

adaptive, context-based, non-linear predictor



. The idea is to model the prediction errors

under dierent contexts. Given a context, the conditional sample mean 

of the prediction

errors under this context is fed back to

to generate a second and improved prediction



+ 

(see Fig. 1).

The selection b etween the continuous-tone and binary mo des is based on pixel contexts.

The mode selection is automatic, and completely transparent to the user. No side infor-

mation ab out mode switching is required. The co ded image only needs a

header of ve

bytes

: two for width, two for height, and one for depth or the numb er of bits in intensity

resolution.

2 Gradient-adjusted Predictor

In this section, we introduce a nonlinear predictor that adapts itself to the image gradi-

ents near the predicted pixel. This predictor improves the precision of traditional DPCM

predictors, particularly in areas of sharp edges.

Denote an input image of width

and height

[

i; j

], 0



i < W

, 0



j < H

. In

order not to obscure the concept of the prop osed compression algorithm, we only consider

in the following development the sequential co ding of interior pixels

[

i; j

], 2



i < W



j < H

2. Many possible treatments of b oundary pixels are p ossible, and they do not

make a signicant dierence in the nal compression ratio due to the small p opulation of

boundary pixels. In this prop osal, b oundary pixels are co ded by a simple DPCM scheme

as they are encountered in the raster scan.

To facilitate the prediction of

[

i; j

] and entropy co ding of the prediction error via

context mo deling, we compute the following quantities:

[

; j

]

[

; j

]

[

i; j

[

; j

[

+ 1

; j

[

i; j

[

; j

]

[

; j

[

i; j

[

i; j

[

+ 1

; j

[

+ 1

; j

[

; j

]

[

; j

[

; j

[

; j

[

i; j

[

; j

135

[

+ 1

; j

[

+ 2

; j

[

i; j

[

+ 1

; j

[

i; j

[

; j

]

(1)

Clearly,

, and

135

are estimates, within a scaling factor, of the gradients

of the intensity function, near pixel

[

i; j

] in horizontal, vertical, 45-degree diagonal, and

135-degree diagonal directions. The values of

, and

135

are used to detect the

magnitude and orientation of edges in the input image, and make necessary adjustments

in the prediction. We aim to alleviate the problem that the precision of existing DPCM-

type predictors can be adversely aected by edges. In (1) three absolute dierences are

used for

in each direction. This gave the best compression results in our exp eriments.

Two or one absolute dierences can b e used here for lower complexity with a small loss

in performance. An ecient incremental and/or parallel scheme for evaluating

and

135

is straightforward.

Based on

, and

135

, we prop ose a simple technique, as described by the

following conditional statements, to make a gradient-adjusted prediction

[

i; j

] of

[

i; j

(

32)

sharp edge

[

i; j

] = (

[

; j

] +

[

i; j

1])

(

) + (

[

+ 1

; j

[

; j

1])

else if

(

12)

horizontal edge

[

i; j

] = (2

[

; j

] +

[

i; j

1])

3 + (

[

+ 1

; j

[

; j

1])

else if

(

12)

vertical edge

[

i; j

] = (

[

; j

] + 2

[

i; j

1])

3 + (

[

+ 1

; j

[

; j

1])

else

smooth area

[

i; j

] = (

[

; j

] +

[

i; j

1])

2 + (

[

+ 1

; j

[

; j

1])

(

135

32)

sharp 135-deg diagonal edge

[

i; j

] =

[

i; j

] + (

[

+ 1

; j

[

; j

1])

else if

(

135

16)

135-deg diagonal edge

[

i; j

] =

[

i; j

] + (

[

+ 1

; j

[

; j

1])

else if

(

135

32)

sharp 45-deg diagonal edge

[

i; j

] =

[

i; j

] + (

[

; j

[

+ 1

; j

1])

else if

(

135

16)

45-deg diagonal edge

[

i; j

] =

[

i; j

] + (

[

; j

[

+ 1

; j

1])

16;

Again the procedure given ab ove is parallelizable. This technique diers from the ex-

isting linear predictors in that it weights the neighboring pixels of

[

i; j

] according to the

estimated gradients of the image. In eect,

[

i; j

] is a simple, adaptive, nonlinear predictor.

The predictor coecients and thresholds given ab ove were empirically chosen. A ma jor

criterion in choosing these co ecients is the ease of computations. For instance, most

coecients are of p ower of 2 to avoid multiplications/divisions.

It is p ossible, albeit quite exp ensive, to optimize the coecients and thresholds for an

image or a class of images, so that a norm of the expected prediction error

is minimized. We do not prop ose such an optimization process to b e part of the ISO

standard. However, it is important to p oint out that the co ecients and thresholds in

computing

[

i; j

] can b e set by the user, if the user knows the optimal or nearly optimal

coecients and thresholds for the target images.

3 Error Energy Quantization for Minimum Entropy

Although the nonlinear predictor

[

i; j

] outperforms linear predictors, it does not completely

remove the statistical redundancy in the image. The variance of prediction errors

still strongly correlates to the smo othness of the image around the predicted pixel

[

i; j

]. To

model this correlation at a small computational cost, we dene an error energy estimator

to be

 =

;

(2)

where

and

are dened in (1) which are reused here to quantify the variability of pixel

values, and

is the magnitude of the prediction error at the preceding pixel

[

; j

is chosen because large errors tend to o ccur consecutively. The co ecients

, and

剩余32页未读，继续阅读

评论收藏

内容反馈

sbx19850629

粉丝: 8
资源: 12

A context-based adaptive lossless nearly-lossless coding scheme

最新资源

A context-based adaptive lossless nearly-lossless coding scheme

adaptive Haar-like MCTF based wavelet video coding scheme

Context-Based Adaptive Binary Arithmetic Coding in the H.264 AVC Video Compression Standard

Context-Based, Adaptive, Lossless Image Coding

context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video

Context-based_adaptive_binary_arithmetic_coding.ra_264_H.264_H.2

基于排序的自适应布谷鸟搜索算法_matlab_algorithm_search_Ranking-based adaptive c

A-MULTI-EXPOSURE-IMAGE-FUSION-BASED-ON-THE-ADAPTIVE-WEIGHTS

A unified scheme for adaptive stroke-based rendering.pdf

Context_aware Sequential Recommender

Neural Network-Based Adaptive Command Filtered Position Tracking Control for Induction Motors

ESO-Based Adaptive Robust Force Control of Linear Electric Load

Model-based adaptive non-null interferometry for freeform surface metrology

A Trust-Based Adaptive Probability Marking and Storage Traceback Scheme for WSNs

QRD-RLS Adaptive Filtering Jos´e Antonio Apolin´ario Jr.

Space-Time Adaptive Processing Using Pattern Classification

Identifier-based adaptive neural dynamic surface control for uncertain DC-DC buck converter system with input constraint

白皮书h.264 英文版

behavior-based adaptive cotroller

Neural-network-based output-feedback adaptive dynamic surface control for a class of stochastic nonlinear time-delay systems with unknown control directions

自适应滤波器--Adaptive Filter 2

A Self-Adaptive Deep Learning-Based System for Anomaly Detection

An adaptive unscented Kalman filter-based adaptive tracking control for wheeled mobile robots with control constrains in the presence of wheel slipping

Space-Time Adaptive Processing for Radar

Adaptive Network-Based Fuzzy Inference System

grammar-based whitebox fuzzing

Space-Time Adaptive Processing for Airborne Radar_J.Ward

DSP-Based speed adaptive flux observer

最新资源