INTERPOLATION AND EXTRAPOLATION OF IMAGE PARTITIONS USING
CODING
SCHEMES
FOURIER DESCRIPTORS: APPLICATION TO SEGMENTATION-BASED
Fe an Ma que's, Be na Llo ens
and
An oni
Gasull
Dep . de Teo ia del Senyal i Comunicacions
Uni e si a Poli kcnica
de
Ca alunya
Campus No d
UPC
-
Edi ici
D5
c/ G an Capi & s/n.
08034
Ba celona, Spain
E-mail: [email p o ec ed]
ABSTRACT
This pape p esen s an
in e pola ion/ex apola ion
ech-
nique o sequence pa i ions. I consis s o ou s eps: e-
gion pa ame iza ion, egion in e pola ion, egion o de ing
and pa i ion c ea ion. The e olu ion o each egion is di-
ided in o wo ypes: egula mo ion and andom de o ma-
ions. Bo h ypes o e olu ion a e pa ame ized by means
o he Fou ie desc ip o s
o
he egions and hey a e sepa-
a ely in e pola ed in he Fou ie domain. The inal in e -
pola ed pa i ion is buil om he o de ed combina ion o
he in e pola ed egions, using mo phological ools.
1.
INTRODUCTION
In he amewo k o image sequence coding, he e is a con-
inuos need o new echniques o each highe comp ession
a ios. A usual app oach o educe he in o ma ion
o
be
sen is o code only a subse o he o al amoun o ames
in he image sequence. In he ecei e side, ames which
ha e no been sen a e in e pola ed om he ansmi ed
in o ma ion. This is he echnique used in he MPEG-2
s anda d, whe e he so-called B- ames a e in e pola ed.
Towa ds he goal
o
achie ing e y low bi - a es, sec-
ond gene a ion coding echniques
[3]
ha e been p oposed.
In his amewo k, he s udy o segmen a ion-based cod-
ing echniques is, nowadays, a e y ac i e ield o esea ch
[6]
[l].
In his case, an accu a e in e pola ion can be pe -
o med elying on he coded pa i ions and g ay le els o
each egion. The e o e, wo di e en ypes o in o ma ion
should
be
in e pola ed:
g ay
le els
and
pa i ions.
In he
coding p ocess, g ay le els a e usually pa ame ized (poly-
nomial coe icien s,
DCT
componen s,
...)
so
ha hey can
be easily in e pola ed.
On
he o he hand, ypical pa i-
ion coding echniques
[2]
do no pa ame ize con ou s and,
he e o e, hei in e pola ion is no s aigh o wa d.
To
in e pola e pa i ions, he in o ma ion o he in e-
io o he egions yielded by he segmen a ion could be
This wo k has
been
pa ially suppo ed by
he
RACE P ojec
2072
(MAVT)
o
he Eu opean Union and he TIC
92-1319-CO3-
01-PB
o
he Spanish Go e nmen
used. Howe e , segmen a ions can be ob ained using di e -
en c i e ia and, he e o e, egions can be ela ed
o
di e en
concep s: homogeneous g ay le el, homogeneous mo ion,
special ype o ex u es, e c. To implemen
an
in e po-
la ion echnique independen o he segmen a ion c i e ia,
he echnique should use only pa i ion in o ma ion; ha
is, he shape and he posi ion o egions in he pa i ion.
The i s s ep o in e pola e a se
o
pa i ions be ween
wo ini ial ones is o pe o m a egion ma ching be ween he
egions o ming hese ini ial pa i ions. A egion appea ing
in bo h ini ial pa i ions should ha e assigned he same la-
bel in bo h pa i ions. When his s a emen is ul illed, se-
quence pa i ions a e said o ha e empo al label cohe ence.
Region ma ching is a di icul p oblem and i s solu ions a e
usually e y ime consuming. Segmen a ion-based coding
echniques sol e his p oblem by keeping ack o he egion
labels h ough he ime domain while pe o ming he seg-
men a ion. Thus, he in e pola ion p ocedu e can assume
ini ial pa i ions wi h empo al label cohe ence.
Howe e , a sequence coding scheme may, e y likely,
use an In a- ame mode
as
e eshmen , in e lea ed wi h
he In e - ame ones. In he case o an In a- ame mode,
he in o ma ion o be sen is no ela ed
o
he p e iously
ansmi ed in o ma ion. The empo al label cohe ence is,
he e o e, b oken and in e pola ion is no possible wi hou
ca ying ou
a
egion ma ching. A second possibili y is,
a he han o in e pola e be ween bo h pa i ions, o gen-
e a e he in e media e pa i ions by ex apola ing he in-
o ma ion
o
he las In e - ame and he In a- ame coded
pa i ions. Ex apola ion is no only use ul o deal wi h
pa i ion wi h empo al uncohe ence bu also o educe he
ime delay in he ecei e side. Tha is, ins ead o in e po-
la ing all pa i ions be ween wo coded ones, some o hem
can be ex apola ed om he o me ecei ed pa i ion.
In his pape ,
a
echnique o in e pola ion and ex ap-
ola ion
o
empo al label cohe en pa i ions is p oposed. I
uses Fou ie Desc ip o s o model he egula mo ion as well
as he andom de o ma ions o egions h ough he ime do-
main. This echnique is desc ibed in he sequel as ollows.
A e his in oduc ion, Sec ion 2 is de o ed o he gen-
e al
in e pola ion/ex apola ion
echnique. I is composed
584
0-8186-7310-9/95 $4.00
0
1995
IEEE
o ou s eps: egion pa ame iza ion, egion in e pola ion,
egion o de ing and c ea ion o a pa i ion. Sec ion
3
de-
ails he speci ic implemen a ion o each o hese ou s eps.
To
e alua e he in e pola ion echnique, some esul s a e
p esen ed in Sec ion
4
and some conclusions a e d i en.
2.
GENERAL SCHEME
Pa i ion in e pola ion and ex apola ion can be s a ed as:
gi en wo ini ial pa i ions
P,
and
P3,
each one composed
o a se o egions
{R,k}
{RJk},
espec i ely, new pa i ions
ha e o be ound ep esen ing he e olu ion om
PI
o
P3
(in e pola ion) as well as beyond
P3
(ex apola ion).
Two di e en app oaches can be p oposed o he p ob-
lem o image pa i ion in e pola ion. A i s app oach is o
in e pola e di ec ly he ini ial pa i ions, join ly analyzing
all he egions in he image [4]. This app oach is only easi-
ble when egions sligh ly a y hei posi ion om he i s o
he las pa i ion. A second app oach is o in e pola e each
egion sepa a ely and, a e wa ds,
o
combine he in e po-
la ed egions in o de o build he in e pola ed pa i ions.
This app oach can handle pa i ions wi hou cons ains in
he egion posi ions. Gi en his capabili y, his app oach
has been chosen in his wo k.
The gene al
in e pola ion/ex apola ion
scheme elies
on he shape and posi ion in o ma ion
o
each egion. Re-
gion e olu ion h ough he ime domain is di ided in o wo
ypes: egula mo ion and andom de o ma ions. Reg-
ula mo ion
is
desc ibed by a gi en mo ion model (e.g.:
ansla ion, zoom and/o o a ion). The egion e olu ion
ha canno be desc ibed by egula mo ion is
said
o be
andom de o ma ions. Bo h ypes
o
in o ma ion should
be pa ame ized o each egion in o de o easily ob ain
i s in e pola ion. The e exis echniques ha , a he han
pa ame izing egions, pe o m he in e pola ion by com-
pu ing a geodesical dis ance be ween egions in he ini ial
pa i ions [4] [7]. Such an app oach does no allow o ex-
apola e, gi en he ac ha he geodesical dis ance is only
de ined be ween he wo ini ial pa i ions
P,
and
P3.
Once egions in bo h pa i ions ha e been pa ame e -
ized, hei pa ame e s a e in e pola ed. This pa ame e in-
e pola ion yields a sepa a ed ep esen a ion o he e olu-
ion o each egion. Tha is, o each egion, i 5 posi ion
and shape a e ob ained a each in e pola ed pa i ion. The
egion in e pola ion has o handle he p oblem
o
egions
which a e only in one o he wo ini ial pa i ions (appea -
ing
o
disappea ing egions).
In
addi ion, in e pola ed e-
gions canno be di ec ly combined o ob ained he inal in-
e pola ed pa i ion. When combining hem, wo p oblems
a ise. Fi s , in e pola ed egions can o e lap andl, second,
some pa s
o
he space may no be co e ed by any egion.
To sol e he i s p oblem, egions a e o de ed This
o -
de ing gi es p io i y o one egion wi h espec o i s neigh-
bo s
so
ha , in case o o e lap, he a ea o o e lapping is
assigned o his egion. Finally, a e combining he in e po-
la ed egions
ollowing
he abo e o de ing, unco e ed
a eas
should be assigned o some o he neighbo egions. This
is done in o de
o
ensu e ha
a
inal pa i ion is achie ed.
The comple e scheme is illus a ed in Figu e
1.
Ini ial Pa i ions
1
Pa ame iza ion
54
O de ing
ic
Pa i ion
C ea ion
In e pola edEx apola ed
Pa i ions
Figu e
1:
Gene al scheme
3.
IN’TERPOLATION/EXTRAPOLATION
OF
IMAGE
PARTITIONS
In his sec ion, speci ic implemen a ions o he abo e ou
s eps a e desc ibed. They use a Fou ie desc ip o ep e-
sen a ion and ma hema ical mo phology ools.
3.1.
Region
pa ame iza ion
A
gi en egion om bo h ini ial pa i ions ( ha is,
R,,
and
RJp)
is sepa a ely pa ame ized. Thei con ou s a e de-
sc ibed as wo complex unc ions
zEp[n]
and z3,[n], namely
posi ion unc ions, whe e bo h con ou s ha e been no mal-
ized o con ain he same numbe o samples
N.
The e is
a
di ec ela ionship be ween a posi ion unc ion
z[n]
and i s
Fou ie ans o m Z[k]. This ans o m yields he Fou ie
desc ip o de ini ion:
N-1
1
N
Z[k]
=
-
c
z[n]
e--j+n
n=O
F om
he Fou ie desc ip o s, a new se o pa ame e s
can be de ined. This
se
is mo e use ul o desc ibing he
e olu ion o he con ou s and, he e o e, o in e pola ion
pu poses. The e olu ion be ween wo egions
RI,
and
R3,
can be ep esen ed
as
he di e ences be ween hei con-
ou ep esen a ions zlP[n] and
z3,[n].
This e olu ion can
be di ided in o wo ypes: egula mo ion and andom de-
o ma ions. The human isual sys em is much mo e sen-
si i e o e o s in he in e pola ion o he egula mo ion
han o he andom de o ma ions. The e o e, he in o ma-
ion ela ed o egula mo ion is ex ac ed i s om he
Fou ie desc ip o s and ea ed sepa a ely. A e wa ds, he
Fou ie desc ip o s a e no malized wi h espec o he eg-
ula
mo ion pa ame e s
so
ha
pa ame e s
desc ibing
he
andom de o ma ions a e ob ained. In his
wo k,
egula
mo ion co esponds
o
equi o m ans o ma ions [8]
:
ans-
la ion
(Pc,~
E
C),
zooming
(So,@
E
R+)
and o a ion
585
(E,,a
E
[0,2~]).
The pa ame e s ela ed wi h hese con-
cep s a e:
G a i y
cen e
C:
I is ela ed o he ansla ion. I is
ob ained di ec ly om he i s Fou ie desc ip o . The con-
ou ep esen a ion is no malized
Dc
by subs ac ing his
sample o he Fou ie desc ip o s:
(
=
Z[O], D<Z[k]
=
Z[k]
-
(6[k]
(2)
Size
p:
I is ela ed o he zooming. I is ob ained
as he magni ude o he Fou ie desc ip o s. The con ou
ep esen a ion is no malized
Sp
by di iding he Fou ie de-
sc ip o s by hei euclidean no m:
(3)
Angle
o
o a ion
a
and
ini ial poin
:
They a e
ela ed o he o a ion. Se e al me hods o es ima ing bo h
pa ame e s sepa a ely ha e been analyzed. Ne e heless,
he mos obus echnique has shown o be a join es ima-
ion o bo h pa ame e s. This echnique adds a line phase
o he phase o he Fou ie desc ip o s
so
ha he wo
coe -
icien s o g ea es magni ude,
Z[kl]
and
Z[k,],
become eal
a e no maliza ion
I,
R,.
Tha is,
2n
N
~(Z*[kl)
=
~(Z[kl)
+
- k
+
a
=
2x ,
T
E
Z
(5)
Ac ually, he es ima ion o hese wo pa ame e s is done
in such a way ha i al eady accoun s wi h he con ou
e olu ion. Tha is, pa ame e s ela ed o he o a ion o
egion
R,
a e compu ed using in o ma ion om he con-
ou s in bo h images,
Z,,[k]
and
Zjp[k].
This is imple-
men ed by using o no maliza ion he wo coe icien s
z
and
j
leading o he wo g ea es magni ude o he p oduc
MP[k]
=I[
Z,,[k]Z,,[k]
11
(MP[ki]
>
MP[k2]
is assumed).
In o de no o wi hd aw possible co ec solu ions,
all
cases
whe e
O.lMP[k2]
<
MP[k]
a e analyzed. Using
(5),
each
pai o possible coe icien s esul s in a se o pai s o no -
maliza ion pa ame e s
(a,
).
To chose he inal pai
(a,
),
a measu e o dissimila i y is u ilized:
This measu e may yield solu ions ep esen ing e y la ge
o a ions. Such o a ions a e no usual in he add essed ap-
plica ion. Thus, a pai
(a,
)
leading o
a
solu ion close o
he minimum one bu in ol ing
a
smalle o a ion is chosen:
d[Z;,
z:]"
<
2d[Z;, Z2*]m n1mZlm
(7)
A e his inal no maliza ion, con ou s a e ep esen ed
by wo se s o pa ame e s. The i s se is ela ed o he
egula mo ion
o
he egion
((,/3,
a, )
whe eas he second
se
(Z*[k])
is
ela ed
o
he andom de o ma ions.
Gi en ha he no maliza ion o
a
egion
R,
is done us-
ing he con ou ep esen a ion
o
his egion in bo h ini ial
pa i ions
(Z,,[k]
and
Z,,[k]),
con lic i e egions (appea -
ing
o
disappea ing egions) ha e o be handle sepa a ely.
Fo such egions, a weigh ed a e age
o
he pa ame e s o
hei neighbo egions is compu ed. The weigh s depend
on he amoun o con ou poin s ha a e sha ed be ween
he gi en egion and i s neighbo . The pa ame e s o he
neighbo egion being close o he a e aged pa ame e s a e
assigned o he con lic i e egion.
3.2.
Region
in e pola ion/ex apola ion
The abo e se o pa ame e s is in e pola ed in o de o ob-
ained he con ou ep esen a ion o he in e pola ed e-
gions. Se e al echniques ha e been analyzed o in e pola -
ing bo h he egula mo ion and he andom de o ma ions.
Fo he case o egula mo ion pa ame e s, linea in e pola-
ion leads o a esul which is mo e pleasan o he human
isual sys em. I yields smoo h ansi ions be ween egions.
Di e en solu ions o he in e pola ion
o
andom de-
o ma ion pa ame e s ha e been also analyzed. Ac ually,
ou di e en echniques o in e pola ing he no malized
Fou ie desc ip o s
Z*[k]
ha e been es ed: Ca esian in-
e pola ion, pola in e pola ion, high equency subs i u-
ion and high equency elimina ion
[5].
Bes esul s, in
e ms o leading o a de o ma ion con o ming o na u al
objec s mo ion, ha e been ob ained using he Ca esian in-
e pola ion. No e ha he abo e echnique o in e pola ion
o egula mo ion and andom de o ma ion pa ame e s can
also be applied o ex apola ion pu poses.
Figu e
2
shows an example o he in e pola ion o a e-
gion ob ained om he segmen a ion o he image sequence
Table-Tennis.
This example is used o illus a e he impo -
ance o using he p ocedu e o es ima e
(Y
and
T,
abo e
p esen ed. In he i s
case,
he wo in e pola ed egions
a e ob ained wi h he pai
cy,^)
leading
o
he minimum
o he measu e o dissimila i y
(6),
whe eas in he second
case, he solu ion cons ained in o a ion
(7)
is p esen ed.
No e ha he second solu ion yields a mo e na u al mo ion.
Figu e
2:
Example
o
in e pola ion cons ained in o a ion
3.3.
Region
o de ing
Once all he egions ha e been sepa a ely in e pola ed, hey
a e o de ed
so
ha possible o e lappings a e sol ed. The
o de ing gi es p io i y o hose egions ha ing a smalle
amoun o andom de o ma ions wi h espec o hei neigh-
bo s. This p ocedu e assumes ha
i
he e olu ion o a
egion
R,
can be ep esen ed only elying on he egula
mo ion in
a
mo e accu a e way han i s neighbo s, his e-
gion should p ese e, as much
as
possible, he ac ual shape
gi en by i s in e pola ion.
The o de ing is ob ained by compu ing
a
dis ance on he
no malized con ou s
z:,[n]
and
zj,[n].
Di e en dis ances
ha e been analyzed and he bes esul s, in e ms
o
isual
quali y, ha e been ob ain wi h he no m
L,.
highe o de le el (lowe p io i y) han he non-con lic i e
Con lic i e egions (appea ing
o
disappea ing ones) ha e
586
egion o highes o de le el. I he non-con lic i e egion
wi h lowes p io i y has an o de le el
O,,,,
a con lic i e
egion
R,
will ecei e he o de le el O[q]
=
Om,,
+
Ob].
Ob] ep esen s he o de ing o he non-con lic i e egion
R,
om which he con lic i e egion
R,
had ob ained i s
egula mo ion pa ame e s.
3.4.
Pa i ion
c ea ion
In e pola ed pa i ions a e c ea ed by combina ion o he
di e en in e pola ed egions espec ing he p e ious o de -
ing. The use o an o de ing sol es he p oblem o o e lap-
ping egions. Howe e , he e may be a eas o he space
which a e no co e ed by any in e pola ed egion; ha
is,
holes in he in e pola ed pa i ion. Such a eas should be
co e ed by neighbo egions o ob ain a inal pa i ion.
Di e en echniques ha e been s udied o ill such holes.
A
simple solu ion is o dila e he in e pola ed egions
so
ha
hei labels co e he holes.
Fo
each in e pola ed egion, i s
geodesical dila ion o size
1
is pe o med. This geodesical
dila ion uses as e e ence space he union o he egion o
be dila ed and he a ea co e ed by i s neighbo holes. I
is applied i s o he egions wi h lowe le el o p io i y
in he p e ious o de ing. Tha is, he mo e eliable is he
egion ep esen a ion, he smalle i s a ia ion should be.
This p ocedu e is i e a ed un il all he holes a e co e ed.
The p e ious echnique a ises wo main p oblems. Fi s ,
in he case o
a
hole be ween wo egions, oughly hal o
he hole is co e ed by each egion, in spi e o hei p io i y
le el. Second, dila ed egions may co e a eas e y dis an
om he posi ion o he in e pola ed egions.
The i s p oblem is sol ed by adap ing he size o he
geodesical dila ion o be applied o each egion wi h espec
o i s le el o p io i y. The e o e, in he same i e a ion s ep,
a egion wi h lowe p io i y will be dila ed by
a
s uc u ing
elemen o size g ea e han a egion wi h highe p io i y.
To sol e he second p oblem, he dila ion is ca ied ou
in wo s eps. Fi s ,
a
mask is c ea ed. Regions om bo h
ini ial pa i ions a e in e pola ed keeping ixed hei an-
dom de o ma ion pa ame e s and only in e pola ing he
egula mo ion ones. The union o hese new in e pola ed
egions o ms a mask and only he holes inside his mask
will be co e ed in he i s s ep. The e o e, he e e ence
space o he geodesical dila ion o
a
gi en egion
R,
in he
i s s ep is o med by he in e sec ion o he p e ious holes
and he a ea co e ed by he new in e pola ions o egion
R,.
In he second s ep, he emaining holes a e co e ed.
4.
RESULTS AND CONCLUSIONS
Figu e 3 shows an example o in e pola ion o 4 ames om
he sequence Ca phone be ween ames 60 and 65. No e
he co ec e olu ion o all he egions, in spi e o p esen -
ing di e en mo ions. Figu e 4 shows he ex apola ion o
2 ames om he same sequence be ween ames 65 and
70.
F ames 66 and 67 ha e been ex apola ed om ame
65 using he pa ame e s ob ained in he p e ious expe i-
ence. No e ha he e olu ion o
all
egions
is
also
co ec ,
al hough being in he case o ex apola ion.
The example o Figu e 3 illus a es he ac ha he
in e pola ion echnique ha has been p esen ed pe o ms
co ec ly. Mo eo e , i can be easily ex ended o he case
o ex apola ion, as shown in he example o Figu e
4.
This
echnique has been es ed on a la ge se o sequences and
using di e en segmen a ion echniques. In all
cases,
esul s
ha e he same quali y le el as hose abo e p esen ed.
5.
REFERENCES
F. Ba olini and
V.
Capellini. A segmen a ion-based
mo ion-compensa ed scheme o low- a e ideo coding.
In P oceedings
o
he Fi s
IEEE
In e na ional Con e -
ence on Image P ocessing, olume 11, pages 457-461,
Texas, U.S.A., No embe 1994.
C.
Gu
and
M.
Kun . Con ou simpli ica ion and mo-
ion compensa ion o e y low bi - a e ideo coding.
In Fi s
IEEE
In e na ional Con e ence on Image P o-
cessing, pages 423-427, Texas, U.S.A., No embe 1994.
M.
Kun , A. Ikonomopoulos, and
M.
Koche . Second
gene a ion image coding echniques. P oceedings o he
IEEE,
73(4):549-575, Ap il 1985.
F. Meye . Algo i hmes d’in e pola ion base6 su des
dis ances gCodCsiques. Technical epo
,
Cen e de Mo -
phologie Ma hCma ique, Fon ainebleau, Dec. 1994.
R.
Que al
0.
Be an and
H.
Mai e. Shape in e po-
la ion using ou ie desc ip o s wi h applica ion
o
ani-
ma ion g aphics. Signal P ocessing, 4:53-58, 1982.
P. Salembie and M. Pa dLs. Hie a chical mo phological
segmen a ion o image sequence coding.
IEEE
T ans-
ac ions on Image P ocessing, 3(5):639-651, Sep . 1994.
P.
Soille. Gene alized geodesic dis ances applied o
in e pola ion and shape desc ip ion. In
J.
Se a and
P.
Soille, edi o s, Ma hema ical mo phology and i s ap-
plica ions o image p ocessing, pages 193-200. Khiwe
Academic Publishe s, 1994.
P. Van O e loo.
A
con ou -o ien ed app oach
o
shape
analysis. P en ice Hall In e na ional (UK), 1991.
Figu e 3: Example o in e pola ion
Figu e
4:
Example
o
ex apola ion
587