Adaptive Sequential Prediction of Multidimensional Signals With Applications to Lossless Image Coding

[attachment=17773]

I. INTRODUCTION
P REDICTING the future of a sequence from its past is a
common and important problem in many disciplines such
as information theory, signal processing, machine learning,
economics/finance, statistics, etc. A series of seminal papers
of Rissanen established the intimate connection between prediction
and universal source coding [1]–[3]. In parallel to his
theoretical results on stochastic complexity and universal source
coding, Rissanen also proposed a constructive algorithm called
Context [2] for universal sequential prediction and coding.
This algorithm was originally developed and analyzed for
sequences, or 1-D signals. Specifically, a sequence of symbols



Manuscript received September 29, 2009; revised March 14, 2010 and June
01, 2010; accepted June 02, 2010. Date of publication July 29, 2010; date of
current version December 17, 2010. This work was supported in part by NSERC
and by NSFC (60932006, 61025005, 61001145) and the 111 Project (B07022).
The associate editor coordinating the review of this manuscript and approving
it for publication was Dr. Antonio Ortega.
X. Wu is with the Department of Electrical and Computer Engineering, Mc-
Master University, Hamilton, ON, L8G 4K1, Canada (e-mail: xwu[at]ece.mcmaster.
ca).
G. Zhai is with the Department of Electrical and Computer Engineering, Mc-
Master University, Hamilton, ON, L8G 4K1, Canada, and also with the Institute
of Image Communication and Information Processing Shanghai Jiao Tong University,
Shanghai, 200240 China (e-mail: zhaiguangtao[at]gmail.com).
X.Yang and W. Zhang are with the Institute of Image Communication and Information
Processing Shanghai Jiao Tong University, Shanghai 200240, China
(e-mail: xkyang/zhangwenjun[at]sjtu.edu.cn).



IV. EXPERIMENTAL RESULTS
To illustrate the adaptation power of the proposed
MDL-based predictor, we plot the 2-D predictor support
and the training set in relation to the current pixel
being predicted in Fig. 2. The pixel to be predicted is marked
in red, the predictor support and training set in green, where
the green intensity indicates the correlation value in (4) and the
degree of template matching in (8). For the periodic texture
pattern in Fig. 2(a), the proposed MDL design technique selects
a predictor support that consists of spatially disjoint past samples.
The selected samples exhibit the local signal structure.