ALGORITMO ADAPTATIVO CON EL GRADO DE
MOVIMIENTO PARA EL DESENTRELAZADO DE V´
IDEO
P. B ox1,I.Ba u one
1,S.S´anchez-Solano1,J.Gu i´e ez-R´ıos2and F. Fe n´andez-He n´andez2
1Ins i u o de Mic oelec ´onica de Se illa (IMSE-CNM-CSIC)
A da. Reina Me cedes S/N. Edificio CICA. 41012 Se illa
e-mail:[email p o ec ed]
2Dp o. Tecnolog´ıa Fo ´onica. Facul ad de In o m´a ica de la Uni e sidad Poli ´ecnica de Mad id
Campus de Mon egancedo S/N. 28660 Boadilla del Mon e (Mad id)
e-mail:jg @fi.upm.es
Resumen
En es a comunicaci´on se p esen a un algo-
i mo adap a i o con el mo imien o pa a el
desen elazado de ´ıdeo. Se basa en un sis-
ema de in e encia di uso, que ealiza una
in e polaci´on en e dos ´ecnicas lineales en
unci´on del g ado de mo imien o. Se ha eali-
zado un es udio de di e en es sis emas di usos
con dis in o n´ume o de unciones de pe e-
nencia, analiz´andose el g ado de complejidad
de los mismos en e a su eficacia desen ela-
zando a ias secuencias de ´ıdeo.
Palab as Cla e: Desen elazado de ´ıdeo,
Mo imien o adap a i o, Sis emas de in e en-
cia di usos, T´ecnicas de ap endizaje supe i-
sado.
1 INTRODUCCI ´
ON
Los p incipales o ma os de ansmisi´on de se˜nales de
ele isi´on (NTCS, PAL, SECAM) u ilizan una se˜nal de
´ıdeo en elazada, donde s´olo se ansmi en al e na i-
amen e las l´ıneas pa es e impa es de cada o og ama.
De es e modo, el ancho de banda de la ansmisi´on
se educe a la mi ad de una o ma muy e ec i a ya
que, debido a las ca ac e ´ıs icas del sis ema de isi´on
humano, el pa padeo p o ocado po la eliminaci´on de
l´ıneas es p ´ac icamen e inap eciable [3]. No obs an e,
el auge de disposi i os que equie en un ba ido p o-
g esi o de la se˜nal de ´ıdeo ( ele iso es de al a de-
finici´on, DVDs, p oyec o es, e c.) ha omen ado el
desa ollo de algo i mos de desen elazado que eali-
zan alg´un ipo de in e polaci´on espacio- empo al pa a
calcula las l´ıneas no ansmi idas.
En e los algo i mos de desen elazado pueden dis in-
gui se globalmen e aquellos que u ilizan un ec o e-
p esen a i o del mo imien o de la imagen pa a in e -
pola las l´ıneas ausen es y los que no lo hacen [4].
Los p ime os ealizan una in e polaci´on m´as p ecisa
a cos a de un ele ado cos e compu acional eque ido
pa a calcula dicho ec o . Los di e en es algo i mos
pueden clasifica se a endiendo a si in e polan siemp e
los mismos p´ıxeles ( ´ecnicas lineales) [6] [11], o si la
in e polaci´on se adap a a las ca ac e ´ıs icas de la ima-
gen ( ´ecnicas no-lineales) [1] [5]. En e los algo i mos
adap a i os se dis inguen a su ez dos g upos: aquellos
que a an de adap a la in e polaci´onalap esencia
de bo des en la imagen [5]; y aquellos o os que e al´uan
la can idad de mo imien o en la imagen adap ando la
in e polaci´on a ´es a [1].
Cuando se emplean ´ecnicas de mo imien o adap a-
i o es undamen al ealiza una buena es imaci´on del
g ado de mo imien o. B´asicamen e los de ec o es de
mo imien o e al´uan la di e encia de alo es de lumi-
nancia en e p´ıxeles de campos consecu i os. No obs-
an e, es a medida no siemp e es fiable debido a la
p esencia de bo des o de alles con g andes cons an es
de alo es de luminancia en la di ecci´on e ical de la
imagen, y a que la se˜nal puede con ene uido. Pa a
aumen a la obus ez de los de ec o es de mo imien o
algunos au o es p oponen conec a a ios en cascada,
de modo que solo si odos ellos de ec an mo imien o la
se˜nalseac i e[3]. Tambi´en se han p opues o dis in-
os algo i mos basados en l´ogica di usa pa a ealiza un
desen elazado adap a i o con el g ado de mo imien o
ob eniendo mejo as significa i as. Es o se debe a la
capacidad de las ´ecnicas di usas pa a ealiza in e -
polaciones en zonas donde la in o maci´on es imp ecisa
y, po an o, la decisi´on no es i ial [10]. La ´ecnica
p opues a en [10] ob iene buenos esul ados pe o em-
plea una base de eglas compleja que equie e un cos e
compu acional conside able.
En es a comunicaci´on se p opone un nue o algo i mo
adap a i o pa a el desen elazado de ´ıdeo que em-
plea un sis ema de in e enciadi usopa ade e mina ,
en unci´on del mo imien o, la in e polaci´
on en e los
p´ıxeles de las l´ıneas asnmi idas. El algo i mo es des-
c i o en de alle en la secci´on 2. Su alidez es anali-
zada en la secci´on 3 desen elazando a ias secuencias
de im´agenes. Finalmen e, las conclusiones del abajo
son esumidas en la secci´on 4.
2 DESCRIPCI ´
ON DEL
ALGORITMO
El algo i mo de desen elazado adap a i o en unci´on
del mo imien o que p esen amos se basa en la siguien e
heu ´ıs ica:sielp´ıxel a calcula co esponde a un ´a ea
donde no exis e mo imien o, el esul ado mejo se ob-
iene ealizando una in e polaci´on en e p´ıxeles del
campo an e io (in e polaci´on empo al). Si po el
con a io el p´ıxel co esponde a un ´a ea donde el g ado
de mo imien o es ele ado, lo m´as adecuado es eali-
za una in e polaci´on en e dis in os p´ıxeles del campo
ac ual (in e polaci´on espacial). En e las ´ecnicas li-
neales empo ales y espaciales se han elegido las m´as
b´asicas: la ´ecnica de inse ci´on del p´ıxel del campo
an e io como empo al (IT) y la media a im´e ica de
los p´ıxeles de las l´ıneas supe io e in e io como espa-
cial (IS). El g ado de mo imien o es e aluado p oce-
sando la se˜nal que se ob iene al ealiza la con oluci´on
bi-dimensional de la di e encia de luminancia en a-
lo absolu o de dos campos que con ienen l´ıneas de la
misma pa idad. Ma em´a icamen e puede exp esa se
como:
mo (x, y, )=Σ
3
i=1(Σ3
j=1Hij Cij )(1)
donde Hij, Cij, ienen dadas po las siguien es ma i-
ces:
⎛
⎝
121
C=1
16 242
121
⎞
⎠(2)
⎛
⎝
Hx−1y−1 −1Hx−1y Hx−1y+1 −1
Hxy =Hxy−1 −1Hxy Hxy+1 −1
Hx+1y−1 −1Hx+1y Hx+1y+1 −1
⎞
⎠(3)
siendo Hxy la di e encia en alo absolu o de la lumi-
nancia de los p´ıxeles que pe enecen a dos campos que
con ienen l´ıneas de la misma pa idad:
Hxy =H(x, y, )=|I(x, y, −1) −I(x, y, +1)|
2(4)
La no aci´on (x,y, ) significa que el p´ıxel iene una ubi-
caci´on espacial de e minada po las coo denadas (x,y)
y co esponde a un campo de e minado ( ) de la se-
cuencia de ideo. A endiendo al ama˜no de las ma i-
ces H y C, se obse a que se emplea una en ana de
con oluci´on bi-dimensional de ama˜no 3x3. La idea
de u iliza ´ecnicas de con oluci´on pa a e alua el mo-
imien o ue in oducida en [7]. La p incipal en aja
de ´es as es que pe mi en ene en cuen a la con i-
buci´on de los ecinos espacio- empo ales al es ima el
mo imien o en el p´ıxel ac ual. De es e modo, puede
minimiza se la influencia de los e en uales e o es en
la de ecci´on de mo imien o debido a la p esencia de
uido, bo des o de alles con con as es de luminancia
ele ados. Adem´as es posible asigna un peso ponde-
ando cada uno de los p´ıxeles ecinos median e los coe-
ficien es de la ma iz C, al y como indica la exp essi´on
(2). Se ha ealizado un es udio pa a e alua dis in as
posibilidades de la en ana de con oluci´on analizando
dis in as dimensiones y alo es de los coeficien es que
la componen [2]. Como conclusi´on se ha seleccionado
la indicada en la exp esi´on (2).
Las ´ecnicas de mo imien o adap a i o ue on o igi-
nalmen e in oducidas en [1]. El g ado de mo imien o
se e aluaba compa ando el alo de la se˜nal co espon-
dien e a la di e encia de luminancia en e campos con-
secu i os con un alo umb al cons an e. El obje i o
del abajo desc i o en es a comunicaci´on ha sido em-
plea una ´ecnica de mo imien o adap a i o que em-
plea un sis ema di uso pa a ealiza la ansici´on en e
las dos ´ecnicas de in e polaci´on (IS,IT)demane a
m´as sua e. De es e modo, en las zonas donde el g ado
de mo imien o es medio y po an o, la decisi´on no es
i ial, se ealiza una in e polaci´on no-lineal en e IS
eIT.
2.1 DESCRIPCI´
ON DEL SISTEMA DE
INFERENCIA DIFUSO
El conocimien o heu ´ıs ico empleado po las ´ecnicas
de mo imien o adap a i o es modelado median e un
sis ema de in e encia di uso. En p ime luga , se ha
empleado un sis ema con solo dos eglas, donde los
concep os SMALL y LARGE se ep esen an median e
los conjun os di usos de la Figu a 1(a). No obs an e,
podemos ap o echa la capacidad de in e polaci´on de
la l´ogica di usa conside ando la posibilidad de amplia
el n´ume o de conjun os di usos. De es e modo, se ´ıa
posible con empla un nue o conjun o di uso ( ep e-
sen ado con la e ique a MEDIUM en la Figu a 1(b)).
La base de eglas se amplia conside ando una nue a e-
gla que, en el caso de ac i a se, implemen a una com-
binaci´on lineal de las ´ecnicas ISyIT.
Es e azonamien o puede ex ende se aumen ando el
n´ume o de conjun os di usos conside ados a los cua-
o (SMALL, SMALL-MEDIUM, MEDIUM-LARGE,
LARGE) o cinco (SMALL, SMALL-MEDIUM, ME-
Figu a 1: Funciones de pe enecia u ilizadas po los dis in os sis emas de in e encia
DIUM, MEDIUM-LARGE, LARGE) ep esen ados en
las Figu a 1(c) y 1(d) espec i amen e. El n´ume o de
eglas de la base de eglas aumen a del mismo modo.
El p oblema de es a ´ecnica es que ”a p io i” no exis e
ninguna indicaci´on pa a fija las cons an es de los con-
secuen es de las bases de eglas con m´as de dos eglas
, ni ampoco pa a de e mina las cons as es (A, B, C,
D, E) que definen los conjun os di usos asociados a las
dis in as e ique as lingu´ıs icas. Pa a fija es os alo-
es podemos en ena los sis emas di usos empleando
´ecnicas de ap endizaje supe isado. El apa ado si-
guien e desc ibe en de alle dicho p oceso.
2.2 PROCESO DE APRENDIZAJE
SUPERVISADO
Los sis emas han sido implemen ados en el en o no
de desa ollo de sis emas di usos X uzzy [8]. Es e en-
o no acili a el dise˜no de sis emas de in e encia basa-
dos en l´ogica di usa al inclui dis in as he amien as
de CAD que cub en las e apas de desc ipci´on, iden ifi-
caci´on, simplificaci´on, e ificaci´on, ajus e au om´a ico
ys´ın esis.
La e apa de ajus e cons i uye habi ualmen e una de
las a easm´as complejas del dise˜no de sis emas di u-
sos. La he amien a que se enca ga de implemen a
es a e apa en X uzzy se denomina x l [9]. Es a he-
amien a pe mi e aplica algo i mos de ap endizaje
Figu a 2: Valo es de MSE ob enidos po los dis in os sis emas de in e encia di usos al desen elaza las secuencias
de ideo
supe isado donde el compo amien o deseado del sis-
ema es desc i o median e un conjun o de pa ones de
en enamien o. Los sis emas han sido en enados u i-
lizando como pa ones de en enamien o un conjun o
de o og amas de ´ıdeo p og esi o. De es e modo,
el algo i mo de ap endizaje supe isado seleccionado
(Ma qua d -Le enbe g en nues o caso) in en a mini-
miza una unci´on de e o que e al´ua la di e encia
en e el compo amien o ac ual y el deseado (de e -
minado po los pa ones de en ada/salida). La he-
amien a x l pe mi e aplica el p oceso de ajus e a
los dis in os pa ´ame os de los sis emas de in e encia
di usos implemen ados. La u ilidad de es a e apa del
p oceso de dise˜no se ha e ificado desen elazando a-
ias secuencias de ´ıdeo, y se explica en de alle en la
secci´on 3.
3 RESULTADOS DE SIMULACI ´
ON
El algo i mo p opues o ha sido p obado simulando dis-
in as secuencias de ´ıdeo es ´anda es ampliamen e u i-
lizadas po la comunidad cien ´ıfica y accesibles a a ´es
de la p´agina web: h p://decsai.ug .es. Las secuencias
u ilizadas se encuen an o iginalmen e en un o ma o
de ´ıdeo p og esi o po lo han sido desen elazadas a -
ificialmen e, es deci , eliminado l´ıneasdecadadeuno
de los o og amas que las componen. Los da os del
fiche o de en enamien o se ob iene seleccionando un
conjun o de im´agenes p og esi as de cada una de las
secuencias.
La Figu a 2 mues a el e o cuad ´a ico medio (MSE)
ob enido al desen elaza seis secuencias de ´ıdeo. Es e
alo co esponde al alo medio de las im´agenes des-
en elazadas (ap oximadamen e se han simulado unas
Tabla 1: Valo medio de PSNR (en dBs) ob enido al desen elaza dis in as secuencia con di e en es algo i mos.
Secuencia Missa Salesman Ca phone Pa is T e o News
Fo ma o CIF CIF QCIF CIF CIF QCIF
RL 36.44 29.75 28.25 23.61 31.05 25.18
IS40.47 33.53 32.61 26.67 35.04 29.25
IT38.36 36.17 30.34 29.86 34.36 33.13
VT-2 ields 40.25 36.54 34.08 30.73 36.61 35.46
VT-3 ields 40.52 36.95 34.54 31.37 37.16 35.67
T´ecnica [10] 40.01 37.62 32.27 33.12 35.38 34.73
P opues a 2 eglas 40.18 38.29 34.78 35.28 36.69 37.51
P opues a 3 eglas 40.51 38.44 34.83 35.78 37.49 38.68
P opues a 4 eglas 39.65 38.23 34.94 35.55 36.77 38.65
P opues a 5 eglas 39.67 38.21 34.94 35.93 37.16 39.15
50 im´agenes de cada secuencia). Las g ´aficas de la
Figu a 2 mues an los esul ados ob enidos al imple-
men a un algo i mo donde los concep os, SMALL,
SMALL-MEDIUM, MEDIUM, MEDIUM-LARGE y
LARGE es ´an definidos median e alo es umb ales,
es deci , de e minados po un alo num´e ico cons-
an e. Tambi´en se mues an los esul ados ob enidos
median e la implemen aci´on de los sis emas di usos
con dis in o n´ume o de eglas (con y sin ap endizaje).
Compa ando las es se ies de esul ados puede dedu-
ci se que los algo i mos que implemen an los sis emas
di usos ob iene los e o es m´as peque˜nos, educi´endose
a´un m´as es os alo es si las unciones de pe enencia
y los consecuen es se modifican median e el p oceso
de ap endizaje. Finalmen e, analizando el n´ume o de
eglas empleadas y el alo de MSE ob enido se de-
duce que si se u ilizan es eglas se ob ienen mejo es
esul ados que con dos. No obs an e, las mejo as in-
oducidas con cua o y cinco unciones de pe enecia
no son significa i as con espec o a la p opues a que
u iliza es. Es m´as, en de e minados casos incluso
dan luga a e o es lige amen e supe io es.
El algo i mo p opues o ambi´en ha sido compa ado
con o as ´ecnicas de desen elazado. La Tabla 1 mues-
a el alo medio en PSNR ob enido al desen elaza
dis in as secuencias de ´ıdeo aplicando una se ie de al-
go i mos. Conc e amen e se han analizado las ´ecnicas
lineales m´as simples: duplicaci´on o epe ici´on del p´ıxel
de la l´ınea an e io (RL) y el alo medio de las l´ıneas
supe io e in e io (IS)como ´ecnicas espaciales y la in-
se ci´on del p´ıxel del campo an e io (IT)como empo-
al. Tambi´en se han conside ado en el es udio ´ecnicas
lineales espacio- empo ales ac ualmen e u ilizadas en
chips come ciales [5], [10]. Finalmen e, hemos con-
side ado una ´ecnica de mo imien o adap a i o que
ambi´en emplea un sis ema di uso pa a ealiza la in-
e polaci´on [9]. Analizando los esul ados mos ados
en la Tabla 1 se obse a que los esul ados m´as al os de
PSNR y po an o, los e o es m´as bajos co esponden
al algo i mo p opues o (se indican los alo es ob eni-
dos con las dis in as unciones de pe enencia as ea-
liza se el p oceso de ap endizaje). Es o ambi´en puede
se co obo ado analizando las im´agenes desen elaza-
das de la Figu a 3.
Finalmen e, se ha ealizado un an´alisis del cos e
compu acional in oluc ado en la implemen aci´on de
cada uno de los algo i mos. Pa a ello odos los al-
go i mos han sido ejecu ados en la misma pla a o ma
(un PC con p ocesado Pen ium IV y sis ema ope a-
i o MSWindow XP) de e min´andose el iempo em-
pleado po cada uno de ellos en p ocesa una misma
secuencia. Los esul ados se mues an en la Tabla 2.
Puede comp obo se c´omo las ´ecnicas lineales son la
m´as ´apidas aunque los esul ados ob enidos po ellas
se en ampliamen e mejo ados po nues a p opues a.
4CONCLUSIONES
En es e comunicaci´on se ha p esen ado un sis ema di-
uso que en unci´on del g ado de mo imien o imple-
men a dis in as combinaciones en e dos ´ecnicas li-
neales. Es ´a basado en las ´ecnicas cl´asicas de mo i-
mien o adap a i o pe o u iliza deficiones di usas en lu-
ga de c isp pa a de e mina el g ado de mo imien o.
Se han implemen ado dis in os sis emas dis usos con
dis in o g ado de complejidad analizando la eficacia de
cada uno de ellos pa a ealiza la in e polaci´on. Los
pa ´ame os que definen el sis ema de in e encia di uso
han sido de e minados median e un p oceso de ajus e
au om´a ico implemen ando un p oceso de ap endizaje
supe isado. En unci´on de los esul ados ob enidos
se deduce que un sis ema que e al´ua el g ado de mo-
imien o con es unciones de pe enencia es eficien e
an o po los esul ados que consigue como po su cos e
compu acional.
Tabla 2: Tiempo de ejecuci´on pa a desen elaza una de las secuencias.
Algo i mo RL ISITVT VT T´ecnica P opues a
2 ields 3 ields [10] 2-3-4-5 eglas
Tiempo(s) 2.03 2.05 3.28 10.62 14.65 143.03 29.23-30.95-31.76-32.65
Figu a 3: Im´agenes desen elazadas ob enidas apli-
cando: (a) RL, (b) IS,(c)IT, (d) VT2fields, (e)
VT3fields, ( ) ´ecnica [10], (g) p opues a de 2 y (h)
3 eglas
Ag adecimien os
Es e abajo ha sido pa cialmen e financiado po los
p oyec os TEC2005-04359/MIC del Minis e io espa˜nol
de Educaci´on y Ciencia, y TIC2006-635 de la Jun a de
Andaluc´ıa. El p ime au o o ma pa e del p og ama
de o maci´on pa a es udian es de doc o ado F.P.U.,
del Minis e io espa˜nol de Educaci´on y Ciencia.
Re e encias
[1] A. M. Bock. Mo ion adap i e s anda ds con e -
sion be ween o ma s o simila field a es. Signal
P ocessing: Image Communica ion, Vol. 6, no. 3,
P´ag.275-280, 1994.
[2] P. B ox, I. Ba u one, S. S´anchez-Solano. A Fuzzy
Mo ion Adap i e Algo i hm o In e laced- o-
P og essi e Con e sion. I will be published in
P oc. o he In o ma ion P ocessing and Manage-
men o Unce ain y in Knowledge-Based Sys ems
(IPMU’2006), 2006.
[3] G. De Haan. Video P ocessing. Uni e si y P ess,
Eindho en, 2004.
[4] G. De Haan and E. B. Belle s. De-in e lacing: An
o e iew. P oc. o he IEEE, Vol. 86, P´ag.1839-
1857, 1998.
[5] T. Doyle and M. Looymans. P og essi e scan con-
e sion using edge in o ma ion. Signal P ocessing
o HDTV. Ed. Else ie Science Publishe s, Vol.
II, P´ag.711-721, 1990.
[6] Genesis Mic ochip, Inc., P elimina y da a shee o
Genesis gmVLD8, 8 bi digi al ideo line double ,
e si´on 1, 1996.
[7] J. Gu i´e ez-R´ıos, F. Fe n´andez-He n´andez, J. C.
C espo and G. T i i˜no. Mo ion adap i e uzzy i-
deo 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-Bsed
Sys ems, 2004.
[8] F. J. Mo eno-Velo, I. Ba u one, S.S´anchez-Solano
and A. Ba iga. Rapid design o complex uzzy
sys ems wi h XFUZZY. P oc. IEEE In . Con .
on Fuzzy Sys ems,P´ags.342-347, 2003.
[9] F. J. Mo eno-Velo, I. Ba u one, R. Senhadji y S.
S´anchez-Solano. Tuning complex uzzy sys ems
by supe ised lea ning algo i hms. P oc. IEEE
In . Con . on Fuzzy Sys ems,P´ags. 226-231, 2003.
[10] D. Van de Ville, B. Rogge, W. Philips and I. Le-
mahieu. De-in e lacing using uzzy-based mo ion
de ec ion. P oc.3 dIn .Con .onKnowledge-
Based In elligen In o ma ion Enginee ing Sys-
ems,P´ag.263-267, 1999.
[11] M. Wes on. In e pola ing lines o ideo signals.
US-pa en 4, P´ag.789-893, 1998.
