Fuzzy mo ion adap i e algo i hm and i s
ha dwa e implemen a ion o ideo
de-in e lacing
J. Gu i´e ez-R´ıos1, P. B ox2,3, F. Fe n´andez-He n´andez1,
I. Ba u one2,3and S. S´anchez-Solano2
1Dep . Tecnolog´ıa Fo ´onica. Uni e sidad Poli ´ecnica Mad id. Campus de
Mon egancedo. 28660 Boadilla del Mon e. Mad id (Spain) {[email p o ec ed]}
2Ins i u o de Mic oelec ´onica de Se illa. Cen o Nacional de Mic oelec ´onica
(CSIC). 41092 Am´e ico Vespucio s/n. Se illa (Spain) {b [email p o ec ed]}
3Dep . Elec ´onica y Elec omagne ismo. Uni e sidad de Se illa (Spain)
Abs ac
In e lacing echniques we e in oduced in he ea ly analog TV ansmission sys ems
as an e icien mechanism capable o hal ing he ideo bandwid h. Cu en ly, in e -
lacing is also used by some mode n digi al TV ansmission sys ems, howe e , he e
is a p oblem a he ecei e side since he majo i y o mode n display de ices equi e
a p og essi e scanning. De-in e lacing algo i hms con e an in e laced ideo signal
in o a p og essi e one by pe o ming in e pola ion. To achie e good de-in e lacing
esul s, dynamical and local image ea u es should be conside ed. The g adual adap-
a ion o he de-in e lacing echnique as a unc ion o he le el o mo ion de ec ed
in each pixel is a powe ul me hod ha can be ca ied ou by means o uzzy in-
e ence. The s a ing poin o ou s udy is an algo i hm ha uses a uzzy in e ence
sys em o e alua e mo ion locally (FMA algo i hm). Ou app oach is based on con-
olu ion echniques o p ocess a uzzy ulebase o mo ion-adap i e de-in e lacing.
Di e en s a egies based on bi-dimensional con olu ion echniques a e p oposed. In
pa icula , he algo i hm called ‘single con olu ion algo i hm’ in oduces signi ican
ad an ages: a mo e accu a e measu emen o he le el o mo ion by using a ma ix
o weigh s, and a unique uzzi ica ion p ocess a e he global es ima ion, which
educes he compu a ional cos . Di e en a chi ec u es o he ha dwa e implemen-
a ion o his algo i hm a e desc ibed in VHDL language. The physical ealiza ion
is ca ied ou on a RC100 Celoxica FPGA de elopmen boa d.
Key wo ds: De-in e lacing, Fuzzy Logic, Mo ion Adap i e, Con olu ion.
1This wo k was pa ially suppo ed by MOBY-DIC p ojec FP7-INFSO-ICT-
P ep in submi ed o Else ie 11 Janua y 2011
1 In oduc ion
In e laced ideo is a me hod o hal e ideo bandwid h by elimina ing ho i-
zon al lines in successi e ames. An in e laced ideo sequence consis s o a
se o al e na ing e en and odd ields con aining, espec i ely, he e en- and
he odd-numbe ed lines o he o iginal images. E en hough his ansmission
scheme was in oduced by he i s analogue TV b oadcas ing sys ems, i is
also used by some o mode n digi al ideo s anda ds. Howe e , mode n TV
se s, compu e displays, and LCD displays use p og essi e scanning, ha is,
hey equi e comple e ames con aining all he lines.
De-in e lacing algo i hms a e equi ed o con e in e laced ideo signals in o
a p og essi e o ma by in e pola ing he missing lines o each ield (see Fig.
1). To pe o m de-in e lacing, many algo i hms ha e been epo ed in he li -
e a u e [1]. They can oughly be classi ied in o wo ca ego ies: non-mo ion
compensa ed (non-MC) and mo ion-compensa ed (MC) algo i hms [1]. MC
echniques in ol e a huge compu a ional cos bu hey o e he mos e ec i e
esul s in mo ing a eas [2]. Among non-MC echniques, wo ca ego ies a e
dis inguished: spa ial in e pola ion o in a- ield echniques, and empo al in-
e pola ion o in e - ield echniques. Spa ial in e pola ion algo i hms calcula e
he lines by in e pola ing he adjacen lines om he same ield. Spa ial in-
e pola ion may be e ical (only pixels om uppe and lowe lines in e ical
di ec ion a e conside ed), such as line a e aging, o di ec ional (a highe num-
be o pixels om up and down lines a e e alua ed in se e al edge di ec ions)
[3]-[8].
Tempo al in e pola ion algo i hms in e pola e he missing lines by employ-
ing pixels om di e en ields. Among hem, he simples me hods a e: ield
inse ion (whe e lines om he p e ious ield o he sequence a e inse ed),
and -line a e age ( ha pe o ms he a e age alue be ween lines om he
p e ious and pos e io ields o he ideo sequence).
In e - ield echniques wo k p ope ly in he s a ic pa s o he image. Howe e ,
i he image con ains dynamical a eas, hese me hods p oduce undesi ed e -
ec s (lines ge misaligned) in mo ing objec s. On he o he hand, in a- ield
echniques wo k much be e in he p esence o mo ion, bu o e poo e-
sul s in s a ic egions. This ci cums ance is he basic idea o mo ion adap i e
de-in e lacing algo i hms, which we e o iginally p oposed in [9]. This kind o
algo i hms ies o combine an spa ial o in a- ield me hod and a empo al
o in e - ield me hod acco ding o he p esence o mo ion [10].
248858 (www.mobydic-p ojec .eu) om Eu opean Communi y, TIN2005-08943-
C02-01 and TEC2008-04920 p ojec s om he Spanish Go e nmen (wi h suppo
om he Eu opean Regional De elopmen Fund), and P08-TIC-03674 p ojec om
he Andalusian Regional Go e nmen .
2
The weakes poin o mo ion adap i e de-in e lacing algo i hms is he co ec
de ec ion o he mo ion le el. The ou pu signal o a mo ion de ec o may be
no always null in a eas whe e he e is no mo ion. Fundamen ally his is due
o he p esence o noise, bu some sys ems ha e also addi ional p oblems. Fo
ins ance, in e lacing causes alse mo ion in e ically de ailed pa s and iming
ji e o he sampling clock is pa icula ly ha m ul in ho izon ally de ailed
a eas. To a oid hese e ec s, some mo ion de ec o s usually include any kind
o spa io- empo al il e ing [11].
The uni e sal app oxima ion capabili y o uzzy sys ems has been exploi ed
o in e pola e images [12]-[14] and ideo sequences [15]-[17], [18]-[20]. Fo de-
in e lacing pu pose, se e al p oposals ha e been epo ed in he li e a u e. The
p oposal in [18] uses so -decision uzzy logic echniques o emo e noise and
de-in e lace TV ideo signals. A uzzy edge-di ec ion de ec o is in oduced in
[19] o o ien a con en ional e ico- empo al il e o de-in e lacing. O he
possible op ion is o use uzzy logic and o apply di e en heu is ic ules wi h
app oxima e le els o unce ain y, which implici ly pe o ms a non-linea il e -
ing [20]. The algo i hm in [15]-[17] uses a uzzy in e ence ule base o choose
de-in e lacing s a egy acco ding o he de ec ion o mo ion. Mo e ecen ly,
se e al p oposals based on uzzy echniques ha e been epo ed o pe o m
de-in e lacing by enhancing edges in he sequence [3]-[7]. A uzzy logic-based
app oach ha pe o ms a weigh ed spa io- empo al de-in e lacing is p esen ed
in ci e[21].
This pape is o ganized as ollows: Sec ion 2 summa izes he s a ing algo i hm
o ou s udy. Sec ion 3 desc ibes he p oposed algo i hms. The e alua ion o
hei pe o mance and i s compa ison wi h o he de-in e lacing echniques a e
es ablished in Sec ion 4. The ha dwa e implemen a ion o he mos e icien
p oposal called ‘single con olu ion algo i hm’ is de ailed in Sec ion 5. Finally,
some conclusions a e expounded in Sec ion 6.
FIELD NUMBER
n+1
n
n-1
FRAME NUMBER
n+1
n
n-1
In e pola ed
lines
T ansmi ed line
DE-INTERLACING
(a) (b)
Fig. 1. (a) In e laced ideo signal. (b) De-in e laced ideo signal.
3
2 Desc ip ion o he s a ing algo i hm
The algo i hm p oposed by Van de Ville e al. in [15]-[17] desc ibes heu is ic
knowledge by means o a uzzy ule se o look o an e icien ade-o be ween
line a e aging and ield inse ion, g adually adap ed o he le el o mo ion
de ec ed in e e y pixel. The app oach p esen ed by Van de Ville e al. will
be called Fuzzy Mo ion Adap i e (FMA) algo i hm in his con ibu ion o
simpli y i s ci a ion. FMA achie es a good quali y o he de-in e laced sequence
bu i becomes expensi e, in e ms o compu a ional cos . A de i ed uzzy
app oach om hese con ibu ions was p oposed by Sanz e al. in [22]. This
p oposal was o ien ed o so wa e implemen a ion and p esen s an adap i e
me hod ha spli s he co esponding uzzy mo ion de ec o in o 1D il e s and
linea simula ion unc ions. Addi ionally, he in ol ed sa u a ion pa ame e s
we e on-line adjus ed aking in o accoun he global ame mo ion.
Ou p oposal is inspi ed by i bu i imp o es i s pe o mance and educes i s
cos conside ably. In o de o acili a e he unde s anding o he FMA, le us
i s desc ibe i b ie ly.
The luminance unc ion o a ideo sequence is deno ed by a h ee dimen-
sional unc ion I(x, y, ) whe e xand ya e he ca esian co-o dina es o he
pixels in e e y ame, and is he ield numbe in he sequence. As images
a e digi ized in pixels, x,yand a e disc e e a iables de ined o e na u al
numbe s. Ini ially, ou case o s udy is a monoch oma ic ideo signal bu he
p ocedu e is easily ex ended o colo image, conside ing he luminance o he
join RGB signal and applying he ob ained co ec ion o each one o he RGB
componen s.
As empo al me hod, ield inse ion ope a ion is chosen, which can be ex-
p essed as ollows:
IT(x, y, ) = I(x, y, −1) (1)
while line a e aging is selec ed as spa ial me hod, which is exp essed as:
IS(x, y, ) = (I(x, y −1, ) + I(x, y + 1, ))/2 (2)
In his way, he luminance o he pixels o he missing lines will be calcula ed
and adap ed o local mo ion, as ollows:
I(x, y, ) = (1 −γ(x, y, )) ·IT(x, y, ) + γ(x, y, )·IS(x, y, ) (3)
whe e γ(x, y, ) is a alue in he in e al [0,1] which ep esen s an es ima ion
o cu en mo ion in he pixel (x, y) and is ob ained as he consequen o a
se o uzzy ules o mo ion es ima ion. Then, as highe is he mo ion (highe
alue o γ(x, y, )), highe is he weigh o spa ial in e pola ion o e empo al
in e pola ion and ice- e sa.
4
small
!"#$"%&'("#)
)))))*+,-.-'/)
0)
1)
2) 3)
!)
la ge
Fig. 2. Fuzzy pa i ion composed by linguis ic e ms ‘small’ and ‘la ge’.
The ules o FMA o ge ing γ(x, y, ) ake he ame di e ence signal as he
inpu space. The ame di e ence signal is de ined as:
H(x, y, ) = |(I(x, y, + 1) −I(x, y, −1)|/2 (4)
which deno es he a ia ion in he luminance o e e y pixel.
The se o ules p oposed in FMA o mo ion de ec ion has he ollowing
meaning:
(1) When he ame di e ence signals in he neighbo hood o he cu en
pixel is small, he consequen s a es he e is no mo ion p esen .
(2) When he e a e la ge ame di e ence signal only a le side o he cu en
pixel, he consequen s ill s a es he e is no mo ion p esen .
(3) When he e a e la ge ame di e ence signal only a igh side o he
cu en pixel, he consequen s ill s a es he e is no mo ion p esen .
(4) When he e a e la ge ame di e ence signals a bo h sides o he cu en
pixel, he consequen s a es he e is mo ion p esen .
(5) When he ame di e ence signal a he cu en pixel is la ge, he conse-
quen also assumes he e is mo ion p esen .
whe e ‘ ame di e ence’ is a linguis ic a iable whose alues, small and la ge,
a e ep esen ed by he uzzy se s depic ed in Fig. 2. Fu he mo e, he use
o piece-wise linea unc ions will ease he ha dwa e implemen a ion o he
algo i hm.
These ules a e also execu ed in he uppe and lowe lines o he p e ious ield
in o de o conside a ec angula window a ound he cu en pixel. The inal
alue o γ(x, y, ) is ob ained a e applying a de uzzi ica ion p ocess, which is
exp essed as ollows:
γ(x, y, ) = π(M(x,y, )= ue)
π(M(x,y, )= ue)+π(M(x,y, )= alse)
(5)
whe e πM(x,y, )= ue and πM(x,y, )= alse a e de ined as he combined plausibili y
5

Table 1
Fuzzy ule se o 2 neighbo s a each side o he cu en pixel
Rule An eceden s Consequen
1.(H(x+2,y, )is small)AND (H(x+1,y, )is small)AND
(H(x,y, )is small)AND (H(x−1,y, )is small)AND
(H(x−2,y, )is small)M(x,y, )= alse
2.(H(x+2,y, )is small)AND (H(x+1,y, )is small)AND
(H(x,y, )is small)AND ((H(x−1,y, )is la ge)OR
(H(x−2,y, )is la ge)) M(x,y, )= alse
3.((H(x+2,y, )is la ge)OR (H(x+1,y, )is la ge)) AND
(H(x,y, )is small)AND (H(x−1,y, )is small)AND
(H(x−2,y, )is small)M(x,y, )= alse
4.((H(x+2,y, )is la ge)OR (H(x+1,y, )is la ge)) AND
((H(x−1,y, )is la ge)OR (H(x−2,y, )is la ge)) M(x,y, )= ue
5.H(x,y, )is la ge M(x,y, )= ue
o he p esence o absence o mo ion espec i ely, as ollows:
π(M(x,y, )= ue)=max(M(x,y, )= ue, M(x,y−1, −1)= ue, M(x,y+1, −1)= ue) (6)
π(M(x,y, )= alse)=min(M(x,y, )= alse, M(x,y−1, −1)= alse, M(x,y+1, −1)= alse) (7)
M(x,y, )= ue and M(x,y, )= alse a e de ined as he consequen s ha s a e ‘ ue’
and ‘ alse’ mo ion espec i ely, and a e calcula ed by combining he ac i a ion
deg ee, αi, o he co esponding ules as ollows:
M(x,y, )= alse =max(α1(x, y, ), α2(x, y, ), α3(x, y, )) (8)
M(x,y, )= ue =max(α4(x, y, ), α5(x, y, )) (9)
The complexi y o FMA app oach depends on he numbe o he conside ed
pixels a each side o he cu en pixel in he same line. I his numbe is
deno ed wi h he pa ame e K, he o al numbe o an eceden es in he i e
ules a e 2K+ 1. FMA ules when he pa ame e Kequals wo a e shown in
Table 1.
Van de Ville e al. desc ibed he e iciency o hei p oposal by de-in e lacing
se e al sequences [15]-[17]. A e analyzing di e en alues o pa ame e s K,
a and b (a and b de ine he ansi ion zone o he membe ship unc ions in
6
Fig. 2), hey conclude, and we ha e co obo a ed, ha he bes esul s and,
he e o e, he lowe e o s 2, a e ob ained o K=2 and 0 ≤a≤1; 6 ≤b≤9.
FMA in oduces impo an ad an ages o e o he con en ional mo ion adap-
i e me hods bu i implies a high compu a ional complexi y since i equi es
o i s implemen a ion a high numbe o max-min ope a o s, a high numbe
o uzzi ica ion p ocesses (as many as he numbe o an eceden s in he ules),
and one di ision as shown he exp ession in (5). Ou p oposal is inspi ed by
FMA, bu i conside ably educes i s compu a ional cos and in oduces wo
imp o emen s o achie e a supe io pe o mance. Fi s ly, he use o con olu-
ion echniques allows he sys em o e alua e be e he p esence o mo ion in
con as o he use o max-min no ms in FMA, which o ces he sys em only
o conside he ex eme alues. And he second one is o assign weigh s o he
alues o di e ences ma ix. I seems logical o assign a highe alue o pixels
ha a e close o he cu en pixel loca ion.
3 In e ence by con olu ion
This sec ion desc ibes ou p oposal which applies con olu ion echniques o
pe o m ule in e ence. This is no a p ocedu e o his pa icula applica ion
bu i is a he a gene al me hod specially use ul in he case o a high numbe o
an eceden s. Fu he mo e, con olu ion is a na u al and e y equen ope a ion
in signal p ocessing, and a g ea e o has been dedica ed o inc ease e iciency
o i s execu ion, bo h a ha dwa e and so wa e le els. Besides, con olu ion
can be compu ed as a p oduc in he equency space, ge ing g ea e iciency
by using Fas Fou ie T ans o m (FFT) algo i hms.
In he case o wo-dimensional signals, disc e e con olu ion c(x,y) o wo unc-
ions w(x,y) and s(x,y) is de ined as:
c(x, y) = w(x, y)∗s(x, y) =
∞
X
n=−∞
∞
X
m=−∞
w(m, n)·s(x−m, y −n) (10)
I we choose o w(x,y) in (10) a ec angula unc ion o heigh 1, ha is:
2In o de o be able o compa e he e iciency o di e en algo i hms and con igu-
a ions, quan i ying image quali y is ca ied ou conside ing he Mean Squa e E o
(MSE) be ween o iginal image and p ocessed one. Since i is a s anda d measu e-
men and conside s all he image pixels.
7
H(x,y, -1) H(x,y, ) D(x,y, )
Fig. 3. Line inse ion in he di e ences ma ix
w(x, y)=1, i 


−Kl≤x≤K
−Lu≤y≤Ld



else w(x, y) = 0
(11)
he con olu ion o s(x,y) and w(x,y) in (11) would be he addi ion o all he
elemen s o s(x,y) wi hin he window. Fu he mo e, i he heigh o w(x,y) is
changed o 1/[(Kl+K +1)×(Lu+Ld+1)], he esul o he con olu ion would
be he mean alue o s(x,y) wi hin he window.
Consequen ly, all he union ope a ions in he ules may be globally imple-
men ed by means o con olu ion. In e sec ion ope a ions mus be p oduc s in
his case. To con e p oduc s in o con olu ions is easible by applica ion o De
Mo gan’s laws, since in e sec ions a e con e ed in o unions. Tha is, con o-
lu ion o a window on he complemen a y o he ma ix o di e ences H(x,y, )
will p o ide an es ima ion o no -mo ion wi hin his pa icula window.
Acco ding o his idea, he in e ence mechanism equi ed by he FMA algo-
i hm may be implemen ed by a bi-dimensional con olu ion. As i was de-
sc ibed p e iously, he algo i hm es ima es mo ion by e alua ing pixel di -
e ences in e ical and ho izon al di ec ions. Ou p oposal ealizes a bidi-
mensional con olu ion using he global di e ences ma ix (D(x, y, )) which
includes all he lines o he cu en ield (H(x, y, )) plus he lines om he
p e ious ield (H(x, y, −1)). This ma ix (D(x, y, )) is calcula ed by in e -
wea ing as shown in Fig. 3.
D(x, y, ) = H(x, y, ) + H(x, y, −1) (12)
Al hough ou p oposals could conside any window size, h ee lines a e used
since his size o e s a good ade-o be ween complexi y and pe o mance.
Fu he mo e, FMA algo i hm wo ks wi h h ee lines and he same numbe o
lines has o be used in o de o es ablish a ai compa ison.
8
3.1 The app oach based on con olu ion wi h i e ules
This app oach calcula es he mo ion-adap a i e pa ame e γ(x, y, ) in equa-
ion (5). Le us conside , o example, he second ule o FMA (see Table 1). I
is e alua ed by using he same neighbo s ha we e used by FMA algo i hm,
ha is, a window size o 3x5. Since he i s pa o he an eceden is he es i-
ma ion o mo ion small in he igh side o he window, including he cu en
pixel, we will make con olu ion (p ope ly speaking, co ela ion) o he global
di e ences complemen a y ma ix (D’(x,y, ) ha e alua es ‘no mo ion’) as
ollows:
C2a=1
9







00111
00111
00111







∗D0(x, y, ) (13)
whe e he ac o 1/9 is o make a e aging ins ead o addi ion. Since he al-
ues o he global di e ences ma ix a e es ic ed in he in e al [0,1], he
complemen a y o he ma ix o di e ences will be made as ollows:
D0(x, y, ) = TOP −D(x, y, ) (14)
whe e TOP is he maximum alue o he di e ences ma ix. Fo example, i
luminance is encoded wi h eigh bi s, he maximum alue is 255. The o he
pa o he an eceden o he second ule is he es ima ion o mo ion la ge in
he le pa o he con olu ion window (excluding he cu en pixel), exp essed
by using he ollowing equa ion:
C2b=1
6







11000
11000
11000







∗D(x, y, ) (15)
Now, he consequen o his second ule is ob ained by choosing an agg ega-
ion ope a o o making in e sec ion o C2aand C2b. Fo example, minimum,
p oduc , a e aging in he o m o geome ic mean, e c... Any case, he mem-
be ship unc ion o make uzzi ica ion mus be sui able o he chosen agg e-
ga o . This p ocedu e is ex ended o he es o he ules used by he FMA
algo i hm (see Table 2). Fo ins ance, he hi d ule will be implemen ed wi h
9
MC algo i hm called ‘MC ield inse ion’; and, inally, he p oposal o Van de
Ville e al.
As i can be seen in Table 4, he p oposed algo i hm achie es he lowes
MSE e o s in h ee o he six sequences (Pa is, News, Mo he ). The MC
algo i hm wo ks be e in wo sequences (Tokyo and Salesman), whe eas he
VT echnique wi h h ee ields sligh ly imp o es he esul s in he T e o
sequence.
Fo he Salesman sequence, he MSE alue o each de-in e laced ame is
shown in Fig. 8. This g aph also p o es he ad an age o mo ion adap i e
p oposals ha conside ably educes he e o alues by combining he spa ial
(line a e age) and he empo al ( ield inse ion) echniques.
Complexi y is analyzed using wo igu es o me i : 1) ha dwa e esou ces o
s o e luminance alues o he pixels in ol ed in he calcula ion; and 2) p im-
i i e ope a ions (POs). Table 5 shows he s o age de ices ha a e equi ed
by each de-in e lacing algo i hm. The mo ion adap i e algo i hms equi e ield
memo ies o e alua e he p esence o mo ion. Speci ically, FMA app oach uses
wo ield memo ies o e alua e he i e ules o he cu en pixel and ano he
mo e o s o e he consequen s o he pixels in he p e ious ield. To calcula e
he con olu ion, he single con olu ion p oposal equi es h ee ields mem-
o ies. The second igu e o me i is es ima ed by e alua ing he numbe o
POs o calcula e an in e pola ed alue. Addi ion, sub ac ion, shi ing, abso-
lu e di e ence and sign unc ion a e conside ed as ope a ion o complexi y 1
PO, while mul iplica ion and di ision a e conside ed wi h complexi y 2 POs.
As can be seen in Table 5, he p oposal conside ably educes he numbe o
POs in compa ison wi h he FMA app oach, and sligh ly inc eases he POs
o e ico- empo al algo i hms. In e ms o compu a ional cos , he hea ies
echnique is he MC algo i hm. The calcula ion o he numbe o POs is no
included in Table 5 since i depends on he s a egy used o calcula e he mo-
ion ec o and he size o he block p ocessing. Fo ins ance, he implemen ed
e sion o he MC ield inse ion used he 3-DRS algo i hm desc ibed in [26]
and i equi es 529 POs.
Be ween simple linea de-in e lacing algo i hms and complex mo ion-compensa ed
ones, mo ion-adap i e algo i hms ep esen a sui able midpoin . The analysis
o de-in e lacing esul s shows he e iciency o he p oposed mo ion- adap i e
algo i hm. Fu he mo e, i educes he complexi y o he FMA algo i hm up
o a pe cen age o 56% in e ms o POs.
16

Table 5
Analysis o s o age esou ces and p imi i e ope a ions (POs) equi ed by each de-
in e lacing algo i hm
Resou ces Complexi y
De-in e lacing Line Field Regis e POs
Algo i hm bu e memo y
Line doubling - - - -
Line a e aging 1 - - 2
ELA 3+3 1 - 2 11
ELA 5+5 1 - 4 20
Enhanced ELA [24] 1 - 2 16
Field inse ion - 1 - -
VT 2 ields 2 1 - 16
VT 3 ields 2 2 - 12
Median echnique [25] 1 1 - 11
Van de Ville e al. (FMA) 2+1 2 4 103
S.con olu ion 1 3 4 45
5 Ha dwa e implemen a ion
Ha dwa e implemen a ion o he single de-in e lacing algo i hm has been de-
eloped wi h he ool XSG (Xilinx Sys em Gene a o ) [27]. This ool con-
sis s o a Simulink lib a y, called Xilinx blockse , and so wa e o ansla e a
Simulink model in o a ha dwa e ealiza ion o he model desc ibed in VHDL
language. XSG maps he sys em pa ame e s (de ined like mask a iables
in Xilinx blockse blocks) in o en i ies, a chi ec u es, po s, signals, and a -
ibu es in he ha dwa e ealiza ion.
Th ee di e en sys em a chi ec u es ha e been conside ed o implemen he
single con olu ion de-in e lacing algo i hm. They di e a he le el o pa al-
lelism employed o implemen he con olu ion. The i s one is a comple ely
pa allel a chi ec u e in which hi y alues o luminance, s o ed in memo y,
a e necessa y o calcula e he luminance o each pixel in he new inse ed line
(Fig. 9(a)). As a esul , a alue is ob ained o he pixel in a clock pe iod.
The second design (see Fig. 9(b)) employs a mixed a chi ec u e which ca ies
ou he ope a ions in sequen ial o m o he i e alues o each ow o he di -
e ences ma ix, whe eas ope a ions om di e en columns o he di e ence
17
H(x-2,y, )
H(x-1,y, )
H(x,y, )
H(x+1,y, )
H(x+2,y, )
H(x-2,y+1, +1) H(x-2,y+1, +1)+
+2H(x-2,y+1, +1)+
+3H(x-2,y+1, +1)+
+2H(x-2,y+1, +1)+
+H(x-2,y+1, +1)
H(x-1,y+1, +1)
H(x,y+1, +1)
H(x+1,y+1, +1)
H(x+2,y+1, +1)
FUZZIFICATION
CONVOLUTION
H(:,:,:)
2nd LINE
CONVOLUTION
H(:,y, )
1s LINE
CONVOLUTION
H(:,y-1, )
3 d LINE
CONVOLUTION
H(:,y+1, )
(a)
(b)
(c)
H(x-2,y-1, +1)
H(x-1,y-1, +1)
H(x,y-1, +1)
H(x+1,y-1, +1)
H(x+2,y-1, +1)
H(x-2,y-1, +1)+
+2H(x-2,y-1, +1)+
+3H(x-2,y-1, +1)+
+2H(x-2,y-1, +1)+
+H(x-2,y-1, +1)
H(x-2,y, +1)+
+3H(x-2,y, +1)+
+5H(x-2,y, +1)+
+3H(x-2,y, +1)+
+H(x-2,y, +1)
(1-γ)·IT+γ·IS
FUZZIFICATION
(1-γ)·IT+γ·IS
(1-γ)·IT+γ·IS
FUZZIFICATION
Fig. 9. (a) Pa allel, (b) mixed and (c) sequen ial implemen a ion a chi ec u es de-
eloped wi h XSG.
ma ix a e ealized in pa allel. A esul is ob ained a e i e clock pe iods in
his case. The hi d design uses a o ally sequen ial a chi ec u e (Fig. 9(c)).
In his case a new alue o luminance is calcula ed a e i een clock pe iods.
Fuzzi ica ion p ocess is pe o med a e con olu ion in hese h ee a chi ec-
u es. This s a egy p o ides wo ad an ages: i s ly, uzzi ica ion always im-
plies a los o in o ma ion, and he idea is o p ocess con olu ion wi hou
in o ma ion loss. Secondly, his s a egy simpli ies he a chi ec u es since a
unique uzzi ica ion block is used independen ly o he selec ed a chi ec u e
(see Fig. 9).
To gi e a physical medium o he di e en ha dwa e implemen a ion a chi ec-
u es o he algo i hm, a RC100 Celoxica boa d has been employed. This boa d
is specially sui able o implemen algo i hms o ideo p ocessing applica ions.
I includes a medium size FPGA om Xilinx called Spa an II. Since he al-
go i hm does no in ol e a huge compu a ional cos , his FPGA should be
adequa e o achie e eal- ime applica ions. Fu he mo e, he RC100 includes
a XCR3128XL CPLD and wo 36-bi x 256k loca ion independen synch onous
RAM banks, in which h ee co ela i e ields a e s o ed, which a e necessa y
o he calculus o he algo i hm.
The sys em includes a CVBS ideo inpu and a ideo decoding chip (SAA7111
om Philips), enabling he FPGA o cap u e and decode NTSC and PAL ideo
sou ces. All con ol signals a e di ec ly mapped wi h he pins o he FPGA.
Finally, he boa d has he abili y o gene a e 24-bi colo VGA ou pu o be
displayed on a moni o . The boa d ea u es a 24-bi Video DAC o con e
18
he digi al ou pu om he FPGA o he app op ia e analog signals on he
VGA connec o .
Celoxica p o ides a de elopmen en i onmen which uses he Handel-C lan-
guage o ha dwa e desc ip ion. Thus, i inco po a es a lib a y o Handel-C
mac os and unc ions designed o make i possible o s a p oducing Handel-
C designs igh away on he RC100 Celoxica boa d [28]. This lib a y includes
mac os o accessing each bank o SRAM and ideo d i e s o he D/A con-
e e which p o ides he VGA ou pu and o he ideo decode SAA7111.
The high le el o ou design is a desc ip ion in Handel-C o he beha io o
he sys em. The gene a ed code desc ibes he cap u e o ideo signal h ough
he CVBS ideo inpu and he w i ing p ocess o da a s o ed in memo ies.
The eading p ocess om SRAM p o ides he inpu o a black box de ined in
Handel-C which in eg a es he design o he de-in e lacing algo i hm desc ibed
by XSG. Da a o he new lines a e o de ed in a p ocess o be able o display
he da a on a moni o h ough he VGA ou pu . Fig. 10(a) shows a block
diag am wi h he p ocesses implemen ed on he FPGA.
Bo h HDLs desc ip ions a e syn hesized indi idually. The VHDL desc ip ion
ob ained om XSG is syn hesized wi h FPGA Exp ess Compile II om
Synopsys. On he o he hand, he Handel-C desc ip ion is syn hesized wi h
DK1, he so wa e ool p o ided by Celoxica. Bo h designs a e inco po a ed a
a pos -syn hesis le el when he implemen a ion o he global sys em is ca ied
ou . Fig. 10(b) shows a block diag am o he ools used in he design.
CAMERA
CVBS INPUT
VIDEO CHIP
READ
INTERLACED
DATA
WRITE
DATA
READ
DATA
INTERFACE
WITH XSG
DESIGN
DISPLAY
DATA ON
SCREEN
MONITOR
VGA OUTPUT
DAC
SRAM0 SRAM1 RC100
CELOXICA
SPARTAN2 XC2S200
(a)
SYSGEN
FPGA
COMPILER
II
FPGA
XILINX
TOOLS
DK1
CELOXICA
MODELSIM
.ed
. hd
.ed
.bi
.c
Tes bench. hd
VHDL
Desc ip ion
Syn hesis Syn hesis
Implemen a ion
(b)
Fig. 10. (a) Block diag am o p ocesses implemen ed in he FPGA. (b) Tools used
in he de elopmen o he design.
19
DE-INTERLACING RESULTS: Salesman sequence
8
9
10
11
12
13
14
15
16
17
3 8 13 18 23 28 33 38 43 48
F ame numbe
MSEE
Ha dwa e (16-bi s)
P oposed (64-bi s)
Ha dwa e (8-bi s)
MSE
8-bi s
16-bi s
64-bi s
Fig. 11. MSE alues ob ained by se e al implemen a ions o he single con olu ion
algo i hm.
5.1 Implemen a ion esul s
The di e en al e na i es o implemen ing he single con olu ion de-in e lacing
algo i hm can be e alua ed om esul s ob ained in he Simulink en i onmen
o by modeling he VHDL desc ip ion gene a ed by XSG wi h he ModelSim
ool om Men o G aphics. MSE esul s achie ed by he XSG designs o he
Salesman sequence is shown in Fig. 10.
As can be seen om he esul s in Fig. 10, MSE alue is highe o he ha dwa e
implemen a ions since he algo i hm desc ibed in Ma lab wo ks wi h double-
p ecision numbe s (64-bi s) whe eas XSG models has been implemen ed wi h
Table 6
Implemen a ion esul s o he designs gene a ed wi h XSG
FPGA SPARTAN2 xc2s200
XSG Design No. slices No. slices P ocessing ime
XSG design Global design (ns) / (MHz)
Pa allel 8 bi s 588(25%) 1906(81%) 36/27.7
Pa allel 16 bi s 894(38%) 2216(94.2%) 39/25.6
Mixed 8 bi s 196(8.3%) 1514(64.4%) 115/8.7
Mixed 16 bi s 381(16.9%) 1698(72.2%) 125/6.9
Sequen ial 8 bi s 98(4.16%) 1424(60.5%) 345/2.8
Sequen ial 16 bi s 233(9.9%) 1550(65.9%) 390/2.6
20
in ege numbe s o 8 and 16 bi s. Ob iously, he implemen a ion wi h 16-bi s
achie e lowe e o s han he implemen a ion wi h 8-bi s.
Implemen a ion esul s in e ms o de ice u iliza ion a e shown in Table 6. An-
alyzing hese esul s, he numbe o slices o he sequen ial design is ob iously
lowe han he o he s and he pa allel design equi es he highes numbe o
de ices. Table 6 also includes he esul s ob ained in e ms o he occupa ional
le el o he FPGA when he global design w i en in Handel-C is implemen ed.
The Philips SAA7111 ideo decoding chip on he RC100 boa d is con olled
using he I2Cbus in-sys em communica ion p o ocol. I p o ides a da a a e
o 13.5 MHz and hus, his o ces he sys em o compu e a new in e pola ed
pixel alue a 27 MHz. Acco ding o he iming esul s in Table 6, he sui able
a chi ec u e o a eal- ime implemen a ion in his ha dwa e pla o m would
be he 8-bi pa allel one.
6 Conclusions
A uzzy de-in e lace o ideo sequences p oposed by Van de Ville e al. has
been he inspi a ion o p opose o he algo i hms o ideo de-in e lacing based
on con olu ion echniques.
Mo ion es ima ion is c ucial o adjus he in e pola ion echnique. The le el
o mo ion is e alua ed wi h a uzzy sys em and i s pe o mance depends on
he quali y o he inpu a iables. A global ma ix ha conside s in e and
in a- ield pixel di e ences is used o ob ain obus inpu a iables.
The de eloped echniques consis on making con olu ion o he inpu a iables
wi h a selec ed unc ion ha ge s a weigh ed a e aging among hem, ca ying
ou a kind o uzzy union. Fuzzy in e sec ion may be compu ed in a simila
way and wi h simila le el o complexi y, by he applica ion o con olu ion
echniques.
The de eloped de-in e lace s a e essen ially wo: one o hem makes use o
he same se o ules o he s a ing algo i hm and applies con olu ion in he
in e ence. The o he akes ad an age om he ac ha he unc ion o make
con olu ion is able o con igu e a weigh ing scheme among he inpu a iables
and simpli ies he se o ules in only one con olu ion (single con olu ion algo-
i hm). This single con olu ion app oach has been implemen ed on a FPGA
de elopmen boa d using he Xilinx’s Sys em Gene a o ool in combina ion
wi h he Handel-C de elopmen en i onmen p o ided by Celoxica. Th ee di -
e en sys em a chi ec u es, which di e a he le el o pa allelism employed
o implemen he con olu ion, ha e been conside ed. Timing esul s p o e
21

ha an 8-bi pa allel implemen a ion o he algo i hm is capable o p o ide
eal- ime ope a ion o his ha dwa e pla o m.
The quali y o he esul s a e be e han hese ob ained by he s a ing algo-
i hm. Howe e , he mos signi ican imp o emen has been he educ ion o
he compu a ional complexi y.
Re e ences
[1] G. de Haan - De-in e lacing. Chap e book o Digi al Video Pos P ocessing, pp.
185-201, Uni e si y P ess Eindho en, Sep. 2006.
[2] Y-L. Chang, S-F. Lin, C-Y. Chen, L-G. Chen - Video de-in e lacing by adap i e
4- ield global/local mo ion compensa ed app oach. IEEE T ans. on Ci cui s and
Sys ems o Video Technology, o. 15, no.12, pp 1569-1582, 2005.
[3] G. Jeon, M. Anise i, V. Bellandi, J. Jeong - Fuzzy ule-based edge- es o a ion
algo i hm in HDTV in e laced sequences. IEEE T ans. on Consume Elec onics,
ol. 53, no.2, pp 725-731, May 2007.
[4] G. Jeon, R. Lee, D. Kim, J. Lee, J. Jeong - Weigh ed uzzy il e on in e laced-
o-p og essi e con e sion. P oc. IEEE In e na ional Con e ence on Mul imedia
and Expo, pp 173-176, Ap . 2008.
[5] G. Jeon, Y. Fang, K. Lee, M. Y. Jung, R. Lee, J. Jeong - Video dein e lacing
algo i hm based on uzzy easoning wi h angle ex ac ion app oach. S udies in
Compu a ional In elligence, ol. 226, pp. 369-379, 2009.
[6] G. Jeon, M. Anise i, V. Bellandi, E. Damiani, J. Jeong - Designing o a
ype.2 uzzy logic il e o imp o ing edge-p ese ing es o a ion o in e laced-
o-p og essi e con e sion. In o ma ion Sciences, ol. 179, no. 13, pp. 2194-2207,
Jun. 2009.
[7] G. Jeon, M. Anise i, J. Lee, V. Bellandi, J. Jeong - Concep o linguis ic a iable-
based uzzy ensemble app oach: Applica ion o in e laced HDTV sequences.
IEEE T ans. on Fuzzy Sys ems, ol. 17, no. 6, pp. 1245-1258, Dec. 2009.
[8] S.-J. Pa k, G. Jeon, J. Jeong - Dein e lacing algo i hm using edge di ec ion
om analysis o he DCT coe icein dis ibu ion. IEEE T ans. on Consume
Elec onics, ol. 55, no. 3, pp.1674-1684, 2009.
[9] A. M. Bock - Mo ion adap i e s anda ds con e sion be ween o ma s o similia
ield a es. Signal P ocessing: Image Communica ion, ol. 6, no. 3, pp. 275-280,
Jan. 1994.
[10] C. S ille , S. Kammel, J. Ho n and T. Dang - The compu a ion o mo ion.
Digi al Image Sequence P ocessing, Comp ession and Analysis. Todd R. Reed
Ed. CRC P ess, 2005.
22
[11] D. Wang, A. Vincen , P. Blanch ield - Hyb id de-in e lacing algo i hm based
on mo ion ec o eliabili y. IEEE T ans. on Ci cui s and Sys ems o Video
Technology, ol.15, no. 8, pp. 1019-1025, 2005.
[12] H. C. Ting, H. M. Hang - Spa ially adap i e in e pola ion o digi al images
using uzzy in e ence. P oc. SPIE, ol. 2727, pp 1206-17, Ma . 1996.
[13] N. Sheza , H. Ab omo -Segal, I. Su skone , R. Ba -Sella - Adap i e low
complexi y algo i hm o image zooming a ac ional scaling a io. P oc. 21s
IEEE Con en ion o he Elec ical and Elec onics Enginee s, pp 253-256, Tel
A i (Is ael), Ap . 2005.
[14] T. Aso, N. Sue ake, T. Yamakawa - A code- educ ion echnique o an image
enla gemen by using a sum-based uzzy in e pola ion. P oc. 9 h In . Con . on
Neu al In o ma ion P ocessing (ICONIP), ol. 3, pp 711-721, To ino (I aly), Aug.
1989.
[15] D. Van de Ville, B. Rogge, W. Philips, I. Lamahieu - De-in e lacing using
uzzy-based mo ion de ec ion. P oc. In . Con . on Knowledge-Based In elligen
In o ma ion Enginee ing Sys ems, 1999.
[16] D. Van de Ville, B. Rogge, W. Philips, I. Lamahieu - E alua ion o se e al
ope a o s o uzzy-based mo ion adap i e de-in e lacing. P oc. o he PRORISC
IEEE Benelux Wo kshop on Ci cui s, Sys ems and Signal P ocessing, pp 535-544,
No . 1999.
[17] D. Van de Ville, R. Van de Wall, W. Philips and I. Lamahieu - Mo ion
adap i e de-in e lacing using uzzy logic. P oc. o In e na ional Con e ence on
In o ma ion P ocessing and Managemen o Unce ain y in Knowledge-Based
Sys ems(IPMU), pp 1989-1996, Jul. 2002.
[18] M. Mancuso, V. D’Al o, R. Poluzzi - Fuzzy edge-o ien ed mo ion-adap i e noise
educ ion and scanning a e con e sion. P oc. IEEE Asia-Paci ic Con e ence on
Ci cui s and Sys ems (APCCAS), pp 652-656, Dec. 1994.
[19] F. Michaud, C. T. Le Dinh, G. Lachi e - Fuzzy de ec ion o edge-di ec ion o
ideo line doubling. IEEE T ans. on Ci cui s and Sys ems o Video Technology,
o. 7, no. 3, pp 539-542, Jun. 1997.
[20] H. Jiang, D. Huu, E. Tinyo k and M. Vasquez - Mo ion Adap i e De-in e lacing.
Uni ed S a es Pa en (US 6,459,455), Oc . 2002.
[21] G. Jeon, J. You, J. Jeong - Weigh ed uzzy easoning scheme o in e laced
o p og essi e con e sion. IEEE T ans. on Ci cui s and Sys ems o Video
Technology, ol. 19, no. 6, pp 842-855, Jun. 2009.
[22] A. Sanz, F. Fe n´andez, J. Gu i´e ez-R´ıos, G. T i i˜no, A. S´anchez, J.C.
C espo, A. Mazadiego - Video dein e lacing using adap i e uzzy il e s. Applied
Compu a ional In elligence - P oc. o he 6 h In e na ional FLINS Con e ence,
pp 397-402, 2004.
23
[23] T. Doyle, M. Looymans - P og essi e scan con e sion using edge in o ma ion.
Signal P ocessing o HDTV, II. L. Chia iglione ED., Else ie Science Publishe s,
pp.711-721, 1990.
[24] H. Y. Lee, J. W. Pa k, T. M. Bae, S. U. Choi, Y. H. Ha - Adap i e scan a e
up-con e sion sys em based on human isual cha ac e is ics. IEEE T ans. on
Consume Elec onics, ol.46, no.4, pp 999-1006, No . 2000.
[25] P. Haa is o, Y. Neu o - Mo ion adap i e scan a e up-con e sion.
Mul idimensional Sys ems Signal P ocessing, no. 3, pp 113-130, 1992.
[26] G. de Haan - Mo ion es ima ion, chap e book o Video P ocessing, pp 221-269,
Uni e si y P ess Eindho en, 2004.
[27] Xilinx - Xilinx Sys em Gene a o 2.1 o Simulink Use Guide.
(h p://www.ma hwo ks.com/applica ions/dsp comm/xilinx e guide.pd ),
2004.
[28] Celoxica - RC100 Func ion Lib a y Manual. 2002
24