A Fuzzy Mo ion Adap i e Algo i hm o
In e laced- o-P og essi e Con e sion
P. B ox I. Ba u one S. Sánchez-Solano
Ins i u o de Mic oelec ónica de Se illa - CNM – CSIC
A da. Reina Me cedes S/N. Edi icio CICA
41012 Se illa (SPAIN)
e-mail: [email p o ec ed]
Abs ac
In e laced- o-p og essi e algo i hms a e
cu en ly equi ed by ideo o ma
con e sion sys ems in o de o display a
p og essi e scanning used in mode n
isualiza ion equipmen s. De-
in e lacing algo i hms use in e pola ion
echniques o calcula e missing pixels
in ansmi ed ields. A mo ion adap i e
algo i hm which employs uzzy logic o
adap he in e pola ion s a egy o he
p esence o mo ion in he images is
p oposed in his pape . The
pe o mance o his new app oach is
e alua ed by ex ensi e simula ion o
di e en ideo sequences.
Keywo ds: Mo ion adap i e, de-in e lacing,
uzzy in e ence sys ems.
1 In oduc ion
Mo ion de ec ion is c ucial o many undamen al
asks in image p ocessing (such as de-in e lacing
[1] o pic u e a e-up con e sion [2]) which
eso o he in e pola ion o image sequence
da a o inc ease he e ical esolu ion o he
image (de-in e lacing) o he numbe o pic u es
which compose he ideo sequence ( a e-up
con e sion). Mo ion adap i e in e pola ion
echniques p o ide e icien solu ions o his
kind o p oblems because hey allow o apply
di e en in e pola ion algo i hms in he s a ic
and dynamic pa s o he images. Ob iously,
hei pe o mance elies s ongly upon he
quali y o mo ion de ec ion schemes.
Mo ion de ec o s basically e alua e he
di e ence be ween pixels in consecu i e
pic u es o make a decision. Howe e , due o
noise and e ical de ails, his alue may no be
a good measu emen . To inc ease he obus ness
o mo ion de ec o s, se e al p oposals ha e been
desc ibed in he li e a u e. Some examples a e
he use o a low-pass il e o educe luc ua ions
o he alues nea edges, o he linea
combina ion o se e al de ec o ou pu s [2].
Fuzzy logic has also been applied o de ec
mo ion in o ma con e sion sys ems which ake
ad an age o i s in e pola ion capabili y o
ob ain new da a in a eas whe e he decision is
no i ial. Techniques desc ibed in [3] and [4]
p opose uzzy mo ion adap i e algo i hms o
de-in e lacing.
In e laced o ma was in oduced o hal e he
equi ed bandwid h in cu en TV sys ems
(NTSC, PAL). I consis s in ansmi ing ields
wi h he hal o he lines ins ead o he whole
ames. A he ecei e side, a de-in e lacing (o
in e laced- o-p og essi e con e sion) algo i hm
econs uc s he missing lines applying
in e pola ion echniques. Figu e 1 illus a es his
p ocess. The ad en o HDTV sys ems, high
Figu e 1: De-in e lacing ask
quali y moni o s, displays and p ojec o s has
inc eased he need o de-in e lacing algo i hms
in he las ew yea s.
Linea de-in e lacing echniques, which always
pe o m he same kind o in e pola ion be ween
pixels, ha e been widely applied. Among hem,
empo al algo i hms (such as ield inse ion)
exploi he co ela ion in he ime domain
achie ing good esul s in s a ic a eas bu
in oducing e y annoying e ec s in mo ing
a eas o he image. Spa ial in e pola ion
algo i hms (such as line doubling o line
a e age) p esen as main ad an age hei low
implemen a ion cos , since memo y is no
equi ed o s o e p e ious ields. Howe e , hey
in oduce blu ing and s ai s-case e ec in
e ical de ails and edges. Theo e ically, a linea
combina ion o bo h echniques should p o ide
he bes esul s. To p o ide i , mo ion adap i e
in e pola ion echniques we e in oduced.
A no el mo ion adap i e in e pola ion algo i hm
is p oposed in his pape . I uses a uzzy
in e ence sys em o decide he mos con enien
in e pola ion acco ding o he p esence o
mo ion. The pape is o ganized as ollows.
Sec ion 2 includes he desc ip ion o he
algo i hm and i s applica ion o de-in e lace
ideo sequences. The pe o mance o he new
algo i hm, compa ed wi h o he s o simila
complexi y in e ms o memo y equi emen s, is
e alua ed in Sec ion 3. Finally some conclusions
a e gi en in Sec ion 4.
2 Fuzzy Mo ion Adap i e Algo i hm
The idea o mo ion adap i e algo i hms o de-
in e lacing was o iginally desc ibed in [5]. I
basically consis s in using wo di e en
in e pola o s, one o s a ic a eas and ano he
one o mo ing a eas. The main no el y o ou
p oposal is o use h ee ins ead o wo kinds o
in e pola o s depending on he le el o mo ion in
he pic u e. This is ca ied ou by using a uzzy
logic-based in e ence sys em o apply he
ollowing heu is ic knowledge in o de o
e alua e he missing pixels in a ield:
1) I mo ion is small hen he bes op ion is
o use in o ma ion om p e ious ields
pe o ming a empo al il e ing (IT) as
in e pola ion me hod.
2) I mo ion is la ge hen he bes op ion is o
use in o ma ion om he cu en ield
pe o ming a spa ial il e ing (IS) as
in e pola ion me hod.
3) In o he cases, he mo ion is medium and
a linea combina ion o he spa ial and
empo al il e ing will be he bes op ion.
These ules, summa ized in Table 1, allow
imp o ing he esul s o con en ional mo ion
de ec o s p o iding smoo h ansac ions be ween
he h ee in e pola o s. To achie e i , he uzzy
se s illus a ed in Figu e 2 a e used o ep esen
he concep s “SMALL”, “MEDIUM”, and
“LARGE”, ins ead o h eshold alues.
Table 1: Fuzzy ule se o he p oposed
algo i hm
i mo ion (x,y, ) hen I(x,y, )
SMALL c1 = IT(x,y, )
LARGE c2 = IS(x,y, )
MEDIUM c3 = γ IT(x,y, ) + λ IS(x,y, )
The inpu o he sys em is he bi-dimensional
con olu ion o he di e ence o luminances, Hij,
gi en by he ollowing exp ession:
Figu e 2: Membe ship unc ions o he
uzzy mo ion adap i e sys em
()
2
)1,,()1,,(
),,(
121
242
121
16
1
1
)1,1,1(),,1()1,1,1(
)1,1,(),,()1,1,(
)1,1,1(),,1()1,1,1(
1),,(
3
1
3
1
+−−
=










=










−+++−−+
−+−−
−+−−−−−
=








=∑∑
==
yxI yxI
yxHC
yxH yxH yxH
yxH yxH yxH
yxH yxH yxH
H
CH yxmo ion
i
ij
j
ij
() ()()
() ()()()
3,,),,(,,
,,),,(,,),,(
32
31
yx yx yxI
yx yx yxI yxI
S
T
αλα
α
γ
α
⋅+⋅
+⋅+⋅=
whe e x and y a e he spa ial coo dina es o he
p ocessed pixel in a ame, and de e mines he
o de o he ield in he sequence.
Bi-dimensional con olu ion is e y sui able o
measu e mo ion since i conside s he spa ial and
empo al neighbo hood o he cu en pixel.
Besides, i p o ides high lexibili y because
con olu ion weigh s, Cij, allow gi ing mo e
p io i y o nea es pixels in he neighbo hood.
Exp ession (1) shows one o he bi-dimensional
con olu ion windows which ha e been used.
Conside ing his exp ession, pixels (in da k
g ey) shown in Figu e 3 a e aking pa in he bi-
dimensional con olu ion. A s udy using
con olu ion windows wi h di e en sizes is
p esen ed in Sec ion 3.
The luminance componen o he in e pola ed
pixel is calcula ed applying he Fuzzy Mean
de uzzica ion me hod as ollows:
whe e αi a e he ac i a ion deg ees o each ule.
Subs i u ing he consequen s, ci (see Table 1),
and applying ha α1+α2+α3 is always equal o 1,
he abo e exp ession can be gi en as:
Figu e 4 shows he block diag am o he uzzy
mo ion adap i e algo i hm. Acco ding o (3), he
algo i hm applies a empo al il e ing i he bi-
dimensional con olu ion o he di e ence o
luminances is eally small (α1 is equal o 1 and
he es o αi a e 0). I pe o ms a spa ial
il e ing i he mo ion le el is eally la ge (α2
akes he alue 1 and he o he s αi a e 0).
O he wise wo ules a e ac i a ed and a non-
linea combina ion be ween wo o he h ee
consequen s is applied.
F om he desc ip ion o he uzzy sys em,
di e en h eshold alues H1, H2 and H3 a e
used in he desc ip ions o membe ship
unc ions o “SMALL”, “MEDIUM” and
“LARGE” (see Figu e 2). Rega ding he
consequen s o he uzzy ule se , he
pe o mance o he uzzy mo ion adap i e
algo i hm also depends on he pa ame e s γ and
λ, which de e mine he hi d in e pola o
unc ion as a linea combina ion o he in a-
ield (IS) and in e - ield (IT) me hod. Despi e
he e is no es ic ion o de e mina e hese i e
alues, some o hem achie e be e esul s han
he o he ones. In o de o es ima e hese alues,
a se o inpu /ou pu aining pa e ns om
p og essi e ideo sequences is used o minimize
an e o unc ion be ween he o iginal alues
(ob ained om he p og essi e ideo sequences)
Figu e 3: Pixels in da k g ey a e aking pa in bi-dimensional con olu ion
Figu e 4: Block diag am o he uzzy mo ion
adap i e algo i hm
()()
() ()
2
,,
,,,,
),,( 3
1
3
1
∑
∑
=
=
⋅
=
i
i
i
ii
yx
yxc yx
yxI
α
α
and he in e pola ed ones. This is ca ied ou
pe o ming a supe ised lea ning algo i hm.
In o de o ealize i , he de elopmen
en i onmen X uzzy 3.0 is used [6]. I is a whole
en i onmen o designing uzzy se s ha is
composed o a se o CAD ools co e ing he
di e en s ages o desc ip ion, e i ica ion,
simpli ica ion and syn hesis o in e ence
sys ems based on uzzy logic. X uzzy 3.0 is ee
so wa e and i can be downloaded om he web
page: h p://www.imse.cnm.es/X uzzy.
X uzzy 3.0 in eg a es a CAD ool, x sl, o une
uzzy sys ems desc ibed in XFL ( he
speci ica ion language in X uzzy) [7].
Conside ing ha ule consequen s could be
desc ibed as linea unc ions o he e inpu
a iables (IT, IS and mo ion), he uzzy sys em
has been pe o med wi hin X uzzy as a i s -
o de Takagi-Sugeno sys em. To achie e i , he
ule se in Table 1 has been ansla ed in o he
equi alen one shown in Table 2, whe e he
membe ship unc ion called “DUMMY” e u ns
a alue o one independen ly o he inpu alue.
This is necessa y o include he inpu a iables
IT and IS in he an eceden s o he ule se .
Figu e 5 illus a es he g aphical use in e ace
o he CAD ool x edi wi hin X uzzy 3.0 which
eases he desc ip ions o he ule se .
x sl allows he use di e en lea ning algo i hms
as well as uning only speci ic pa ame e s o he
sys em and a selec ing c i e ion o s op he
p ocess. In pa icula , he well-known
Ma qua d -Le enbe g algo i hm is chosen and
he pa ame e s H1, H2, H3, λ and γ a e enabled
o pa icipa e in he uning p ocess. Figu e 6
shows he e olu ion o h ee e o unc ions
along he lea ning p ocess a e ele en
i mo ion (x,y, ) and IS(x,y, ) and IT(x,y, ) hen I(x,y, )
SMALL and DUMMY and DUMMY c1 = IT(x,y, )
LARGE and DUMMY and DUMMY c2 = IS(x,y, )
MEDIUM and DUMMY and DUMMY c3 = γ IT(x,y, ) + λ IS(x,y, )
Table 2: Desc ip ion o he uzzy sys em ule se wi h X uzzy3.0
Figu e 5: Desc ip ion o he uzzy ule se using x edi wi hin X uzzy 3.0
()
5
11111
12321
13631
12321
11111
42
1
3
















=C
()
4
111
232
363
232
111
32
1
2
















=C
i e a ions.
Compa ing wi h o he uzzy mo ion adap i e
algo i hms, ou p oposal educes conside ably
he compu a ional complexi y o he me hod in
[3] (i will be p o ed in he Sec ion 3). The bi-
dimensional con olu ion o he di e ence
ma ix was i s ly in oduced in [4] o compu e
he se o uzzy in e ence o ules. In ou case,
his ope a o is used as inpu o he uzzy sys em
o dis inguish he di e en le els o mo ion in
he image.
3 Simula ion esul s
The simula ion esul s p esen ed in his sec ion
allow compa ing ou p oposal wi h o he de-
in e lacing algo i hms. In o de o employ an
objec i e pe o mance measu emen , o iginal
p og essi e ideo sequences whose e en/odd
lines we e p e iously elimina ed ha e been de-
in e laced and an e o unc ion has been
employed o e alua e he beha io o di e en
de-in e lacing algo i hms. The p oposed
algo i hm has been compa ed wi h line
doubling, line a e age, ield inse ion, VT
il e ing using wo [8] and h ee ields [9] and
he wo uzzy mo ion adap i e algo i hms
p oposed in [3] and [4]. The h ee mo ion
adap i e algo i hms use he same in e pola o s:
line a e age as spa ial il e ing and ield
inse ion as empo al il e ing (as i was
explained in Sec ion 2, ou app oach uses a
linea combina ion o bo h echniques as hi d
in e pola o ).
Di e en sizes o he con olu ion windows ha e
been conside ed o ou me hod: 3x3, 5x3 and
5x5. The weigh s o he new ma ices 5x3 and
5x5 a e shown in exp essions (4) and (5),
espec i ely. They ha e been selec ed
empi ically, gi en mo e p io i y o closes pixels
in he neighbo hood. Ob iously, when he
window size is bigge , mo e pixels a e
Figu e 6: E olu ion o he uning p ocess

conside ed o e alua e mo ion wi h he
co esponding inc ease in he compu a ional
cos .
Table 2 shows he a e age PSNR alues
ob ained when de-in e lacing he ields o
se e al s anda d ideo sequences. Th ee ows,
co esponding o he h ee bi-dimensional
windows used o ou p oposal, a e included in
he able. The PSNR esul s show ha he new
algo i hm pe o ms be e han all he o he
algo i hms∗. The inclusion o a hi d consequen
inc eases he obus ness o he mo ion de ec o
ob aining highe PSNR alues han he o he
wo uzzy mo ion adap i e algo i hms. This
cha ac e is ic can be also co obo a ed wi h he
de-in e laced images showed in Figu e 7 and
Figu e 8 (especially in ma ked a eas wi h whi e
ci cles). Rega ding he h ee op ions o ou
p oposal, he me hod which wo ks wi h a bigge
bi-dimensional con olu ion window achie es
he bes esul s.
Ne e heless, no only quali y pe o mance bu
also compu a ional ime and cos should be
∗ In spi e o he e a e o he pe cep ual measu es, he
majo i y o esea ch communi y in image p ocessing use
he PSNR o es ima e he quali y o he econs uc ed
image.
e alua ed. This is he eason why all hese
algo i hms ha e been p og ammed in Ma lab
and execu ed on he same PC (a 2.0 GHz
Pen ium 4 p ocesso unning he MS-Window
XP ope a ing sys em). The o al CPU ime and
he compu a ional ime a io acco ding o he
as es algo i hm a e shown in Table 3.
Mo eo e , he complexi y is also e alua ed in
e ms o memo y equi emen s as i is shown in
Table 4. Compa ing wi h he VT (3 ields)
algo i hm (widely used in TV indus y), ou
p oposal equi es an ex a- ield memo y since
ou ields a e used o e alua e he amoun o
mo ion. Howe e , i inc eases conside ably he
de ec ion o mo ion.
4 Conclusions
A no el mo ion adap i e algo i hm o de-
in e lacing has been p esen ed in his pape . I
employs a uzzy sys em which model heu is ic
knowledge o classi y di e en a eas in he ield
acco ding o he p esence o mo ion. Di e en
in e pola ions a e applied depending on his
classi ica ion. Field inse ion is pe o med in
s a ic a eas, line a e age in mo ing a eas, and a
combina ion o bo h in he es o he image. As
a esul , he p oposed me hod p o ides be e
solu ions elimina ing he blu ing and he
Video Sequence Missa Pa is T e o Salesman News Mo he Ca phone
Fo ma CIF (288x352) QCIF (144x176)
Line Doubling 36.44 23.61 31.05 29.75 25.18 31.81 28.25
Line A e age 40.47 26.67 35.04 33.53 29.25 35.94 32.61
Field Inse ion 38.36 29.86 34.36 36.17 33.13 36.14 30.34
VT 2 ields 40.25 30.73 36.61 36.54 35.46 39.61 34.08
VT 3 ields 40.52 31.37 37.16 36.95 35.67 40.89 34.54
Fuzzy Mo ion
Adap i e [3] 40.01 33.12 35.38 37.62 34.73 39.49 32.27
Fuzzy Mo ion
Adap i e [4] 40.18 35.28 36.69 38.29 37.51 41.87 34.78
P oposed 1
(3x3) 40.51 35.78 37.49 38.44 38.68 41.93 34.83
P oposed 2
(5x3) 40.58 35.93 37.61 38.49 38.91 42.02 34.92
P oposed 3
(5x5) 40.63 35.99 37.68 38.55 38.97 42.05 34.97
Table 2: A e age PSNR ( alues in dBs) when de-in e lacing se e al ideo sequences
annoying s ai s-s ep e ec o he de-in e laced
images. Besides, i is achie ed a he expense o
a low inc emen in he complexi y.
Acknowledgemen s
The au ho s wish o exp ess hei g a i ude o
D . J. Gu ié ez-Ríos o his encou agemen s
and ad ices. This wo k has been pa ially
unded by he p ojec s TEC2005-04359/MIC
om he Spanish Minis y o Educa ion and
Science and TIC2006-635 om he Andalusian
Regional Go e nmen . The i s au ho is also
suppo ed by he Spanish Minis y o Educa ion
unde he p og am F.P.U. o Phd. S uden s.
Re e ences
[1] G. De Haan and E.B. Belle s. De-
in e lacing: An o e iew. P oc. o he IEEE,
ol.86, pp.1839-1857, Sep .1988
[2] G. De Haan. Video p ocessing. Uni e si y
P ess, Eindho en, 2004.
[3] D. Van de Ville, B. Rogge, W. Philips and I.
Lemahieu. De-in e lacing using uzzy-based
mo ion de ec ion. P oc. 3 d In . Con . on
Knowledge-Based In elligen In o ma ion
Enginee ing Sys ems, pp.263-267, Adelaide,
Aus alia, Aug. 1999
[4] J. Gu ié ez-Ríos, F. Fe nández-He nández,
J. C. C espo and G. T e iño. Mo ion
adap i e uzzy ideo de-in e lacing me hod
based on con olu ion echniques. P oc. o
In o ma ion P ocessing and Managemen o
Unce ain y in Knowledge-Based Sys ems,
Pe ugia, I aly, July 2004
[5] A. M. Bock. Mo ion adap i e s anda ds
con e sion be ween o ma s o simila ield
a es. Signal P ocessing: Image
Communica ion, pp.275-280, ol.6 no.3,
June 1994
[6] F.J. Mo eno-Velo, I. Ba u one, S. Sánchez-
Solano, A. Ba iga. Rapid design o
complex uzzy sys ems wi h XFUZZY,
P oc. IEEE In . Con . on Fuzzy Sys ems,
pp.342-347S . Louis, USA, May 2003
[7] F.J. Mo eno-Velo, I. Ba u one, R. Senhadji
and S. Sánchez-Solano. Tuning complex
uzzy sys ems by supe ised lea ning
algo i hms, P oc. IEEE In . Con . on Fuzzy
Sys ems, pp.226-231, S . Louis, USA, May
2003
[8] Genesis Mic ochip, Inc., P elimina y da a
shee o Genesis gmVLD8, 8 bi digi al
ideoline double , e sion 1.0, June 1996
[9] M. Wes on. In e pola ing lines o ideo
signals. US-pa en 4, 789-893, Dec. 1998
Line
Doub.
Line
A e .
Field
Inse .
VT
2 ields
VT
3 ields
Mo ion
adap.[3]
Mo ion
adap.[4]
P oposed Algo i hm
3x3 5x3 5x5
CPU
ime (s) 2.03 2.05 3.28 10.62 14.65 143.03 29.21 30.95 31.71 32.14
Ra io 1 1.01 1.61 5.23 7.21 70.42 14.37 15.25 15.62 15.82
Table 3: Compu a ion ime equi ed by de-in e lacing algo i hms
Line
Doub.
Line
A e .
Field
Inse .
VT
2 ields
VT
3 ields
Mo ion
adap.[3]
Mo ion
adap.[4]
P oposed Algo i hm
3x3 5x3 5x5
Field
Memo ies 0 0 1 1 2 3 3 3 3 3
Line
Delays 0 1 0 1 2 0 0 0 0 2
Pixel
Delays 0 0 0 0 0 4 4 2 4 4
Table 4: S o age de ices
Figu e 7: (a) P og essi e ame o “Ca phone” sequence. (b) The co esponding in e laced ield.
De-in e laced image applying: (c) line doubling, (d) line a e age, (e) ield inse ion,
and
(
)
VT il e in
g
2 ields
Figu e 8: De-in e laced image applying: (a) VT il e ing 3 ields, (b) uzzy mo ion adap i e
in [3] and (c) in [4], p oposal wi h 5x5 (d), 5x3 (e) and ( ) 3x3 window