1-
)
,,
,_
n
.
·e
y
:,
:
i-
{
~
,£
'·
,_
1-
n
,_
SIGNAL
PROCESSING
V:
Theo ies
and
Applica ions
L
To es,
E.
Masg au,
and M.A
Lagunas
(eds.)
©
Else ie
Science
Publishe s
B.
V.,
1990
749
THREE DIMENSIONAL ADAPTIVE LAPLACIAN PYRAMID IMAGE CODING
S.Sallen * L.To es** L.Gils*
* Depa men o Applied Ma hema ics and Telema ics,
**
Depa men o Signal Theo y and Communica ions
ETSETB-UPC, Apa ado 30002, Ba celona 08034, Spain.
~n
his.
pape
we p opose a h ee dimensional Laplacian Py amid coding scheme. The
mpu
1mag:
sequence
is
subsampled
bo h
spa ially
and
empo ally
in o
di e en
channels
usmg
p ope h ee dimensional sampling
s uc u es.
This
esul s
in
he
image
s~quen~e
being
:p esen ed
by
a
se ies
o
bandpass
sequences
h ough
h ee
d1mens10nal Gauss1an
and
Laplacian py amid
da a
s uc u es.
In
o de
o build
he
spa ia- empo al py amid
s uc u e
se e al il e s
a e
discussed.
1 INTRODUCTION
The Laplacian Py amid
is
a new and
e icien me hod o image encoding
(1
).
The
me hod
is
o inc easing in e es
as
bandpass
py amids and mul i esolu ion images a e
being used in o he image p ocessing
applica ions. The py amid image s uc u e
can
be
na u ally adap ed o p og essi e
image ansmission o e low-speed channels
and
hie a chical
image
e ie ing
in
compu e ized image s o age.
The me hod ob ains good comp ession
a es and excellen isual quali y o s a ic
images.
l
was hen logical o ex end he
py amid image s uc u e using a bi a y non-
ec angula
sampling
la ices
and
cha ac e ize
he sampling
la ices
by
ma ices, hus p o iding a compac and
powe ul no a ion (2).
On
he o he hand inc easing in e es is
ocused
on image sequence coding
..
Applica ions
such as
ideocon e ence
~ideo elephone
and
low bi a e image coding
m gene al, a e a key issue
in
cu en ideo
communica ion sys ems. The pape
we
p esen p oposes a new h ee dimensional
coding scheme as
an
ex ension o he
p e iously epo ed wo k
on
s a ic images.
The inpu image sequence is subsampled bo h
spa ially
and
empo ally
in o
di e en
channels using p ope h ee dimensional
sampling s uc u es. This esul s in he
image sequence being ep esen ed by a
se ies o bandpass sequences h ough h ee
dimensional Gaussian and Laplacian py amid
da a s uc u es.
In
o de
o
build he empo al py amid
s uc u e se e al spa ial- empo al il e s
a e discussed along wi h di e en sampling
s a egies.
l
is shown, as
in
he s a ic
image case, ha he pe o mance o he
py amid encoding sys em
can
be
imp o ed
by
p ope selec ion o he sampling s uc u es
hus esul ing
in
an
adap i e and e icien
encoding me hod. Mo ion compensa ion
algo i hms a e also in oduced
in
he scheme
o u he dec ease he bi a e
as
is he
case o hyb id me hods.
2 GAUSSIAN
AND
LAPLACIAN DATA
STRUCTURES
The empo al and spa ial py amid da a
s uc u e ep esen s he o iginal image
sequence in o a se o code elemen s which
a e localized in spa ial and empo al
equencies
as
well
as
in
space and ime.
Each elemen
in
he new da a s uc u e is
ob ained by applying
an
app op ia e h ee
dimensional weigh ing unc ion de ined
on
an
a bi a y sampling s uc u e.
The image sequence, and pa icula ly he
ideo-con e ence
sequences,
a e
cha ac e ized by he high co ela ions o he
neighbo ing pixels in he spa ial and
empo al dimensions. The h ee dimensional
py amid coding educes he co ela ion by
sub ac ing he o iginal sequence
s:(l,m,n)
om he low-pass e sion sequence
o
i sel
S"(l
m
n)
1 ' ' , whe e l,m,n a e he empo ally
and
spa ially coo dina es espec i ely.
The code elemen s a e ob ained om
hose sequences as a sui able di e ence
which ep esen s he p edic ion e o
o I
D0(l_,m,n) = S0
(l,m,n)-
sp,m,n)
(1)
750
being Do(l,m,n) mo e deco ela ed han he
o iginal sequence.
Then a he , han encode
s:(l,m,n)
i
encodes he se
o
band-pass sequences
ob aining da a comp ession. The comp ession
is achi ed because he low-pass sequences
a e
buil
h ough a decima ion p ocess
associa ed wi h
Mi
ma ix. Consequen ly
he.
low-pass sequences a e encoded a a educed
sample a e, and he high-pass sequences
can be desc ibed wi h ewe bi s.
I e a ing his p ocess o e he low-pass
sequence a se o low-pass { s:(l,m,
n)}
and
band-pass {Di(l,m,n)} image sequences is
ob ained whose suppo egions a e de ined
on
sampling la ices cha ac e ized by a 3X3
Mi
ma ix.
Bo h da a se s can be modeled as a
py amid da a s uc u es whe e each le el is
a sequence o dec easing dimension and
esolu ion, he o iginal sequence being he
bo om o he py amid.
The
low-pass
sequence
se
is
cons uc ed
applying
ecu si ely
he
decima ion algo i hm
S~
(l,m ,n) =
dec{
S0(l, i
,n)}
=
+l
1
o T
TT
LLL W(o,p,q) · Si(Mi [l,m,n] +
[o,p,q]
)
0 p q
(2)
whe e
o,
p,
q belong o he suppo egion o
he h ee dimensional weigh ing unc ion
W,
i is he py amid le el, wi h
i=O
he bo om
o he py amid s uc u e and
os;
i <
L-
1.
The band-pass sequence se is buil by
applying
ecu si ely
he
in e pola ion
algo i hm
o I
Di(l,m,n)=Si(l,m,n)-
Si+
1
(l,m,n)=
s:(l,m,n)-in e
{S:Jl,m,n)}
=
s:o.m.n>-lc e (M)I·
I
TT
L,L,L,W(o,p,q)·S:iM-(1-o
m-p
n-q))
0 p q (3)
This algo i hm is only e alua ed o
in ege alues o
s:+p,m,n)
..
When he decima ion and in e pola ion
p ocess uses like-Gaussian il e s, he da a
se s a e named Gaussian and Laplacian da a
s uc u es.
3 THREE DIMENSIONAL LAPLACIAN
PYRAMID CODING
The
h ee
dimensional
Laplacian
Py amid
Image
coding wi h
associa ed
sampling la ices de ined
by
a h ee by h ee
ma ices
se
{M}
is
based
on he
ansmission o he quan ized se o band-
pass sequences {Di(l,m,n)}, L he numbe o
o al le els
o
he py amid s uc u e and
DL-I(l,m,n)
=S~jl,m,n)
is
he op sequence o
he py amid.
The new coding scheme is implemen ed
in
ou s ages.
a- A se o L low-pass e sions o he
o iginal
sequence
de ined
on
sampling
{MJ
la ices
is
ob ained
by
applying
ecu si ely
he
decima ion
algo i hm. Fo he cons uc ion o each le el
i+ 1
an
ap op ia e sampling la ice is chosen
in
o de
o p o ide he bes in o ma ion
compac ion. Thus esul ing in each le el
ha ing i s p ope sampling s uc u e.
In
he
equency-domain
he
shape
o
he
ecip ocal
uni
cell
associa ed
o he
sampling
la ice
M i is compa ed o he
equency con en o he low-pass sequence
s;(l,m,n)_ The algo i hm can be modeled as a
low-pass
il e ing
and
down-sampling
p ocess.
b- The se o band-pass sequences a e
cons uc ed
by applying
ecu si ely
he
in e pola ion algo i hm o e he low-pass
sequence. This algo i hm can
be
modeled as
an up-sampling p ocess,
low~pass
il e ing
and a sui able di e ence. The weigh ing
unc ion and sampling la ice used a e he
same ha ha e been used
in
he cons uc ion
o
he
equi alen
le el
in
he low-pass
sequence.
c· The se o band-pass sequences a e
quan ized
by
laplacian
quan ize s.
The
pa ame e s o he quan ize s a e selec ed
aco ding o he s a is ics, he o al chosen
comp ession and he quali y o he desi ed
econs uc ed sequence. The se o quan ized
seq1
a i;
seq
ec1
L.~
o I
whe
is 1
a b
con
allo
si m
p o
eh
a
M,
w
•.
<
5,.Q
M
w~
D
s:<~
he
COl
ap
we
a
3.n
ed
ee
he
Id-
O
nd
o
ed
he
)n
by
:>n
ei
en
on
ei
he
1e
he
he
ce
a
1g
e
he
ss
as
ng
ng
he
on
ss
e
he
ed
en
ed
ed
sequences
{D';(l,m,n)}
a e ansmi ed using
a iable leng h codewo ds.
d-
A he ecei e , he o iginal
sequence
is
econs uc ed
applying
ecu si e ly
s·i
(l,m,n)=D:o.m,n)+
~e (M;)I·
I
TT
LLL
W(o,p,q)
-s·i+ (M-
(1-
o
m-
p
n-
q) )
0 p q
(4)
Whe e
s·L-p,m,n)
= o·L-l(l,m,n) and s'o(l,m,n)
is he econs uc ed sequence. The use o
a bi a y
sampling
la ices
in
he
cons uc ion o low
and
band
pass sequences
allows o spli he spec um
in
egions o
simila
s a is ics
adap ing he coding
p ocess o he spa ial and empo al
cha ac e is ics o he sequence.
[bJ
s'.O.mn)
I
iM,.
iM.
W .,(o,p,q) W
..
(o,p,q)
[Q
_D.,(l,m,n)
'~-'1
~
iM.
I W,(o,p,q)
s:(l.m.n)
iM.
W,(qp,q)
J....+D;.;;.{I,:;:;m,;;;:;n~)~[Q
IL...---...,
-I-
s'
.O.mn)
~
s',.(l.m,n)
TRANSMITTER RECEIVER
Figu e 1
show's
he block diag am
o
he Th ee Dimensional Laplacian Py amid
Coding.
The p edic ion e o can
be
imp o ed
applying
mo ion compensa ion o he
weigh ing unc ion. A egula decomposi ion
751
quad ee me hod
(3)
is applied o segmen
he
in e ame
di e en ial
signal in o
homogeneous egions o di e en block
sizes. Each egion is cha ac e ized by a
mo ion ec o and used
o
co ec he local
weigh ed a e age
o
each
pixel.
4 SIMULATIONS
AND
RESULTS
The esul s p esen ed he e we e
de i ed om wo ideo sequences known
as
"Miss Ame ica" and "Wai e " which a e
256x256 pixels pe ame wi h eigh pixels
pe bi and wen y i e ames pe second.
In
his coding me hod, he ype o he
il e has been chosen acco ding
o
he
app op ia e ma ix M i associa ed o each
le el. Fo ins ance, igu e 2 shows he i s
le el o he Th ee Dimensional Laplacian
Py amid o " Miss Ame ica " sequence.
In
his case we use
3D
spa ia- empo al il e
wi h 125 aps and 1 D empo al il e 5 aps
associa ed o
[
200)
M;=
020
002
and
[
200)
M;=
010
001
ideo-con e ence
sequences
Miss Ame ica" and "Wai e "
a b
Figu e
2 The i s le el o he
Laplacian Py amid Do(l,m,n)
o
"Miss
Ame ica" and "Wai e " using
a)
125 ap
spa ia- empo al il e , and
b)
5 ap empo al
il e .
752
MISS
AMERICA
WALTER
50000
40000
';
';
I
311000
.,.,
5Z.2.'1
=
1
20000
•
•
10000
-10
10
20
-20
-10
10
20
MISS
AMERICA
WALTER
'0000
.
50000
l
40000
(i:
~.u
';
(/":.21.'1
';
30000
i
20000
I
uooo
0
-20
-10
20
-20
20
Figu e 3 shows he his og ams o he
i s le el using he spa ia- empo al and
empo al il e s desc ibed abo e o he
wai e and Miss Ame ica sequences.
Figu e 4 show> esul s o consecu i e
coded ames
6,
7,
8 and 9 o he "Miss
Figu e
4 Recons uc ed ames
6,7,8,9 o "Miss Ame ica" and
1,
2,
3 o
"Wai e " wi h a signal
o
noise a io o
24
and
27
dB espec i ely.
Ame ica" whi h a comp ession a io o 40,
and ames
1,
2,
and
3
o
" Wai e " sequence
wi h a comp ession a io o 20. Compu e
esul s a e p esen ed a
64
x 4 kbi s/sec
wi h excellen isual quali y and a signal
o
noise a io o
24
and
27db espec ly. This
a e can be lowe ed by applying mo ion
compensa ion o he h ee dimensional
weigh ing unc ion.
The simula ion esul s indica ed ha
he p oposed me hod is capable o ope a ing
e y e icien ly o a wide class o ideo
applica ions such
as
192 Kbi s/second high
de ini ion ideo con e encing and in he
ange o B-ISON hie a chies. l is shown ha
he scheme does no p esen any block
e ec , o e s low compu a ional complexi y,
and
can
be
implemen ed
in
pa allel.
5 CONCLUSION
We
p esen ed he h ee dimensional
Laplacian Py amid Coding used
o
ob ain a
high comp ession a e o wide a ie y o
ideo applica ions. This me hod is he esul
o ex ending he Py amid Coding o he h ee
dimensions,
using
a bi a y
sampling
la ices. Also he sui abili y
o
apply mo ion
compensa ion
on
he weigh ing unc ions
was emphasized, achie ing a signi ican
imp o emen in he comp ession a io and
isual quali y.
6 REFERENCES
[1] "The Laplacian Py amid
as
a Compac
Image
Code",
P.J.
Bu ,
E.H.
Adelson,
IEEE
T ansac ions
on
Communica ions, Vol.
COM-31, n°4, Ap il 1983, pp.532-540.
[2] "An Adap i e Py amid Image Coding
Sys em",
S.Sallen ,
L.
To es,
P oceedings ICASSP 1988, New Yo k,
Ap il 11-14, 1988.
[3] "Simula ion O A Telecon e ence Codec
Fo ISDN", S.Sallen , A.A e o, J.Ha o,
EUSIPC0-90, Ba celona, Sep embe ,
1990.
[4] "The Sampling
And
Recons uc ion O
Time-Va ying Image y Wi h
Applica ions
in
Video Sys ems",
E.
Dubois, P oceedings
IEEE
1988, Vol.
73,
502-522, Ap il 1985.
S/(
L.
@,
1
e
i