Local picture-repetition mode detector for video de-interlacing

P. B ox e al.: Local Pic u e- epe i ion Mode De ec o o Video De-in e lacing Con ibu ed Pape Manusc ip ecei ed Sep embe 21, 2007 0098 3063/07/$20.00 © 2007 IEEE 1647 Local Pic u e- epe i ion Mode De ec o o Video De-in e lacing Piedad B ox, Leon Woes enbe g, and Ge a d de Haan, Senio Membe , IEEE Abs ac — The de-in e lacing o ideo ma e ial con e e d om ilm can be pe ec , p o ided i is possible o ecognize he ield-pai s ha o igina e om he same ilm image. Va ious so-called ilm-de ec o s ha e been p oposed o his pu pose, mainly in he pa en -li e a u e. Typically, hese de ec o s ail in cases whe e ideo o e lays a e me ged wi h ilm ma e ial, o when non- s anda d epe i ion pa e ns a e used. Bo h p oblems occu equen ly in ele ision b oadcas . Fo hese hyb id and/o i egula cases, we p opose a de ec o ha can de ec di e en pic u e- epe i ion pa e ns locally in he image. This de ec o combines uzzy logic ules and spa io- empo al p edic ion o a i e a a highly obus decision signal, sui able o pixel- accu a e de-in e lacing o hyb id and i egula ideo ma e ial. In addi ion o an e alua ion o he pe o mance, he pape also p o ides a complexi y analysis. Index T e ms — Pic u e- epe i ion Mode De ec ion, Video De- in e lacin g , Pull Down, Video Si g nal P ocessin g , Fuzzy In e ence Sys ems. I. INTRODUCTION Knowledge o he pic u e epe i ion pa e n is highly ele an o se e al ideo signal p ocessing asks, like ideo comp ession, pic u e- a e con e sion and de-in e lacing. As his in o ma ion is usually no included in he ansmission, he de ec ion o pic u e epe i ion om he ideo da a is necessa y. We shall ocus on he de-in e lacing applica ion [1], which is pa icula ly ele an , since i he ield- p ai s ha a e o igina ed om he same image a e ecognize d hen he de-in e lacing o ideo ma e ial can be pe ec . As a la ge pe cen age, o en he majo i y, o b oadcas ideo ma e ial has been con e ed om ilm, me hods o ealize ilm- mode de ec ion a e cu en ly in demand. In his con e sion pic u e epe i ion is equi ed, since ideo signals o igina ing om a ideo came a p o ide a pic u e a e o 50 Hz, o 60 Hz, whe eas i he ma e ial was egis e ed wi h a cine-came a he pic u e a e is only 24 images pe second. In o de o adap ilm o bo h s anda d ansmissions, a p ocess called ’pull-down’ is pe o med. Basically, i consis s o epea edly scanning a ilm image un il i is ime o show he nex . Fo 25 Hz ilm shown in a 50 Hz P . B ox is wi h he Ins i u o de Mic oelec ´ onica de Se illa (CNM-CSIC) and he Uni e si y o Se ille, Spain (e-mail:[email p o ec ed]). L.M.P . W oes enbe g is wi h he Axon Digi al Desing, Udenhou , he Ne he lands (e- mail:leon.w oes enbe g@axon. ). G. de Haan is wi h he Philips Resea ch Eindho en, Eindho en, he Ne he lands. He is also p o esso a he In o ma ion and Communica ion G oup, T echnology Uni e si y o Eindho en, he Ne he lands (e- mail:[email p o ec ed]om). b oadcas , e e y image is shown wice and he con e sion is e e ed o as 2:2 pull-down. Fo 24 Hz ilm shown on a 60 Hz ele ision, ilm images a e shown al e na ingly 2 and 3 imes, which is he so-called 3:2 pull-down p ocess. Independen o he ype o came a and epe i ion pa e n, in e laced ideo signals ansmi only he odd lines o od d images and he e en lines o e en images. Di e en de ec o s ha e been p oposed o iden i y he ield- p ai s o igina ing om he same ilm image o enable pe ec de-in e lacing, o p ope pic u e- a e con e sion. Among he m ze o- ec o ma ching de ec o s ha e widely been employe d by he majo i y o cu en ilm de ec o s [2]. They y o ma ch he ze o mo ion ec o s on a p e ious ield. To pe o m i , hey no mally use wo kinds o signals: a i s o de ec he ame simila i y and a second one o measu e he ield simila i y. Based on he analysis o bo h simila i y me ics, con ol signals a e gene a ed. They indica e he mode o he ideo signal, i.e. ideo o ilm, an d he ype and phase o he ilm mode, o de e mine he image’s posi ion in he 3:2 o 2:2 pull-down pa e n. O he app oaches y o iden i y jagged edges in ames. This undesi able phenomenon appea s when wo ields wi h mo ing objec s, sampled a di e en momen s a ime, a e me ged in o a single image. Se e al p oposals o his kind o de ec o s ha e been p esen ed in he li e a u e [3], [4]. Ano he de ec o based on edge-de ec ion was p oposed in [5]. I analyzes he posi ion o edges in he image since i he e is a pic u e epe i ion o he ields, edges should be a he same spa ial posi ion. Finally, a mo ion ec o based app oach has been p oposed in [6]. The sum o he leng h o he mo ion ec o s is e alua ed o decide i wo ields a e iden ical o no . Recen ad ances in he a ea o ilm-de ec ion can be di ided in o wo ca ego ies. The i s ones epo on he inc eased obus ness o he algo i hms, whe eas he second ones ocus on he de ec ion o he local ideo mode in hyb id ideo sequences. An imp o ed obus ness is especially ele an , as an in- co ec mode decision p oduces highly annoying a e ac s in he de-in e laced ideo signal. The app oach desc ibe d in [7] educes he numbe o w ong decisions due o e ical de ails using a new di e ence me ic, whe eas he p oposed me hod in [8] uses a laye ed s uc u e o achie e a obus ness imp o emen . Local de ec ion has been mo i a ed by he inc ease o TV ma e ial ha combines images om di e en o igins in a IEEE T ansac ions on Consume Elec onics, Vol. 53, No. 4, NOVEMBER 2007 1648 single ield. None o he echniques p e iously ci ed can locally de ec di e en modes in a single ield, as hei ou pu is a single lag o he en i e ield. They usually compa e he sum o absolu e alues o ame and ield di e ences o e he en i e ield wi h a h eshold alue [2], [7]. This s a egy is a om op imal, since he bes h eshold alue s ongly depends on he amoun o mo ion and he le el o noise in he pic u e. Mo eo e , i lea es no op ions o dis inguish he di e en modes in a single ield ha occu in hyb id ma e ial. To sol e his p oblem, a me hod o de ec ing he ilm mode o indi idually mo ing objec s wi hin ields is desc ibed in [9]. The iden i ica ion o hese objec s is pe o med using segmen a ion. Ou p oposal combines uzzy logic and spa io- empo al p edic ion o inc ease he obus ness o he inal decision, an d also o ake a decision locally on a pixel-by- p ixel basis. Due o he capaci y o he uzzy logic- b ased models o pe o m a non-linea mapping be ween he inpu and ou pu space, hey a e well-known as good in e pola o s [10]. One example is he me hod de eloped in [11], which uses an adap i e de-in e lacing p ocess by weigh ing be ween ’ ield inse ion’ and ’a spa ial in e pola ion algo i hm’. The weigh ing ac o s a e ob ained analyzing, as inpu s o he uzzy sys em, he in a and in e - ield signal di e ences o he cu en pixel along a se o p e-de e mined di ec ions. In his pape , we p opose a se o uzzy IF-THEN ules o ake a decision ins ead o ealizing a weigh ed in e pola ion. I n his no el app oach, each ule models heu is ic knowledge o iden i y one o he possible pic u e- epe i ion modes on a pixel-by-pixel basis. To make his pixel-accu a e de ec o obus , a se o p oposals a e p esen ed. Among hem, he main no el y is he inclusion o a spa io- empo al p edic ion scheme inspi ed on ecu si e mo ion es ima ion [12]. He e, p edic io n implies ha he inal decision no only co esponds o he cu en pixel, bu also he decisions in a spa io- empo al neighbo hood o he cu en pixel a e conside ed. Since he decision is made on a pixel-by- p ixel basis, ou me hod can deal success ully wi h hyb id ideo ma e ial. Mo eo e , ou p oposal is no limi ed o he ecogni ion o he s anda d epe i ions pa e ns, like he popula 2:2 o 3:2 pull-down pa e ns o ilm. This ex ends i s applicabili y o any i egula , pic u e- epe i ion sequence. This pape is o ganized as ollows. The p oposed algo i h m is desc ibed in Sec ion II. We p esen se e al p oposals om a b asic one o a mo e sophis ica ed one in he di e en subsec ions o Sec ion II. The pe o mance o he app oach is p o en by ex ensi e simula ions o ideo sequences applying he mode de ec ion o pe o m di e en de-in e lacing echniques. These esul s a e p esen ed in Sec ion III. This sec ion also includes a complexi y analysis o he algo i hm. Finally, we d aw ou conclusions in Sec ion IV. II. LOCAL PICTURE-REPETITION MODE DETECTOR The p oposed mode de ec o is a decision-making sys em based on a se o ules. Each single ule models heu is ic knowledge o iden i y locally di e en modes. As men ioned in he in oduc ion, ou p oposal, o de- in e lacing, o e s mo e han jus he unc ionali y o a ilm-de ec o , as i s ules deal wi h all possible pic u e- epe i ion pa e ns. To help app ecia e he backg ound o he ules, we shall i s b ie ly desc ibe he con e sion be ween ilm and ideo, which is s ill he mos common cause o pic u e- epe i ion in b oadcas ideo. The 3:2 pull-down p ocess is common o ans e 24 Hz ilm o 60 Hz ideo. To achie e his, e e y odd ilm image is scanned wice, while e e y e en ilm image is scanned h ee imes as shown in Fig. 1(a). The ea e , he signal is in e laced. The 2:2 pull-down p ocess is common o ans e 24 Hz ilm o 50 Hz ideo. Ini ially, he pic u e- a e o he ilm is inc eased o 25 images pe second by unning he ilm 4% as e . Then, each ilm image is scanned wice and in e laced, gene a ing wo ideo ields as shown in Fig. 1(b). To a i e a pic u e- epe i ion de ec ion, we calcula e h ee di e ence signals, he ame di e ence signal (δ ame) be ween he nex and p e ious ield a he same spa ial posi ion (x, y), and he wo ield di e ences o he cu en pixel: wi h he p e ious ield (δ ield1) and wi h he nex ield (δ ield2). In o de o inc ease obus ness agains noise he median alue o each di e ence a h ee e ical posi ions is used (see Fig. 2). They a e de ined by he ollowing exp essions: δ ame ( x , y , n ) = med ( δ ame ( − 2 ) , δ am e ( 0 ) , δ am e ( 2 ) ) ( 1 ) Film 24 Hz A B Video 60 Hz A odd A e en A odd B e en Film 25 Hz A B Video 50 Hz A odd A e en B odd Line y-2 δ ame ( - 2 ) T ansmi ed pixel In e pola ed pixel B odd C e en B e en Codd y C D C odd C e en C D Ce en Dodd y +1 D odd D e en De en y +2 ( a ) ( b ) n-1 n n+1 Fiel d Fig. 1. S anda d con e sion be ween ideo and ilm o ma s: (a) 3:2 Pull- down. ( b ) 2:2 Pull-down. Fig. 2. Pic u e- epe i ion mode de ec o ape u e. The shown pixels a e used o calcula e he local di e ences. y -1 ame ( 0) ame ( 2 ) ield1 ( - 1) ield 2 ( - 1) ield1 ( 1) ield1 ( 0) δ δ δ δ δ δ δ δ ield 2 ( 1) ield 2 (0 ) P. B ox e al.: Local Pic u e- epe i ion Mode De ec o o Video De-in e lacing 1649 Video 60 Hz A odd A e en A odd B e en B odd C e en C odd C e en D odd D e en δ ield S S L S L S S L S δ ame S L L L L S L L δ ield1 S S L S L S S L δ ield2 S L S L S S L S δ ame S L L L L S L L Video 50 Hz A odd A e en B odd B e en C odd C e en D odd D e en S L S L S L S L L L L L L δ ield1 S L S L S L S L δ ield2 L S L S L S L S δ ame L L L L L L L L (a) 3:2 Pull-down ( b ) 2:2 Pull-down Fig. 3. Tempo al di e ence pa e ns o s anda d con e sions. δ ame (x, y, n) =med (δ ame(−2) , δ ame(0) , δ ame(2) ) (1) δ ield1 (x, y, n) =med (δ ield1(−1) , δ ield1(0) , δ ield1(1) ) (2) δ ield2 (x, y, n) =med (δ ield2(−1) , δ ield2(0) , δ ield2(1) ) (3) whe e n deno es he ield numbe in he sequence o de : δ ame(i) (x, y, n) = |F (x, y + i, n + 1) − F (x, y + i, n − 1)| δ ield1(i) (x, y, n) = |Fd (x, y + i, n) − F (x, y + i, n − 1)| δ ield2(i) (x, y, n) = |Fd (x, y + i, n) − F (x, y + i, n + 1)| To calcula e he di e ences, a simple ini ial de-in e lacing algo i hm is used o gene a e p og essi e ames (Fd). Typically, a e ical- empo al median o a e ical- empo al linea il e is p oposed [1]. I he ini ial de-in e lacing p ocess would be pe ec , he di e ence be ween ields om he same sou ce image, as i occu s wi h ilm, should be equal o ze o. Wi h a simple and ealis ic ini ial de-in e lacing algo i h m alias and e ical de ails in he ield may in oduce alse de ec ions o mo ion. In o de o educe his p oblem, he ield di e ences shown in exp essions (2) and (3) a e no malized by e ical in a- ields di e ences. The di e en ypes o empo al di e ences pa e ns a e shown in Fig. 3(a) and 3(b) o he pull-down 3:2 and 2:2 p ocess, whe e ’L’ means a la ge di e ence and ’S’ a small di e ence. Conside ing hese empo al di e ence p a e ns, he ollowing knowledge can be applied o de ec he di e en modes: 1) I he ame di e ence is la ge and bo h iel d di e ences a e la ge oo, hen he pixel co esponds o a mo ing objec in a ideo sequence, whe e all ields a e di e en . 2) I he ame di e ence is small and bo h ield di e ences a e also small, hen he pixel co esponds o an a ea wi hou mo ion du ing hese wo ield-pe iods. The e- o e, i mus be, ei he a s a iona y a ea, o a mo ing a ea i he 3 ields o igina e om a 3 imes epea ed image, e.g. as i occu s wi h 3:2 pull-down. 3) I he ame di e ence is la ge, bu one o he ield di e ences is small while he o he is la ge, he n he cu en pixel belongs o a sequence wi h pic u e- epe i ion, whe e a leas one ield is epea ed, as i occu s e.g. in 2:2 pull-down mode. 4) O he wise, none o he modes is iden i ied. This he may occu when he ini ial de-in e lacing p ocess, hen necessa y o calcula e he ield di e ences, su e s, om alias, because he signals a e co up ed by noise, o because he image has a la a ea. This heu is ic knowledge can be modelled using a sys e m wi h uzzy IF-THEN ules, since he concep s la ge and small a e unde s ood as uzzy de ini ions ins ead o h eshold alues. Using uzzy logic, he concep s o ’SMALL’ an d ’LARGE’ a e ep esen ed by uzzy se s, he membe ship alues o which change con inuously be ween 0 and 1, as shown Fig. 4(a) and Fig. 4(b). Each uzzy IF-THEN ule in ou sys em has an eceden 1 linguis ic alues and a single consequen mode as shown in Table I. The minimum/maximum2 ope a o s a e selec ed as connec i es ’and’/’o ’ o he an eceden s, espec i ely. 1 0 Membe ship deg ee o δ o LARGE µ(δ) Membe ship deg ee o δ o SMALL 0 D0 D1 δ D2 D3 δ 1 An eceden is he common e m o a condi ion in he uzzy logic domain [13] (a) (b) Fig. 4. Membe ship unc ions o he uzzy se s (a) LARGE, (b) SMALL. 2 Minimum and maximum ope a o s a e usually de ined as ’and’ and ’o ’ ope a o s in he uzzy logic domain espec i ely [13] µ(δ) δ ield δ ame 1 IEEE T ansac ions on Consume Elec onics, Vol. 53, No. 4, NOVEMBER 2007 1650 TABLE I FU Z Z Y RU L E SE T i an eceden hen consequen 1) δ ame (x,y,n) is LARGE and δ ield1 (x,y,n) is LARGE and δ ield2 (x,y,n) is LARGE MODE is ideo 2) δ ame (x,y,n) is SMALL and δ ield1 (x,y,n) is SMALL and δ ield2 (x,y,n) is SMALL MODE is s a iona y 3) (δ ame (x,y,n) is LARGE and δ ield1 (x,y,n) is SMALL and δ ield2 (x,y,n) is LARGE) o MODE is epe i ion (δ ame (x,y,n) is LARGE and δ ield1 (x,y,n) is LARGE and δ ield2 (x,y,n) is SMALL) 4 ) o he wise MODE is unde e mined The use o he ope a o ’and’ o ces he sys em o analyze he ield di e ences signals only i he co esponding ame di e ence signal is la ge. This s a egy inc eases he obus ness o he de ec ion, since he ame di e ence signal is mo e eliable han he o he di e ences ha a e based on impe ec ini ial de-in e lacing esul s (Fd). The main ad an age o he uzzy-logic based app oach is ha i p o ides a smoo h ansi ion be ween one decision and ano he . The ac i a ion deg ee o a ule (αi) indica es he compa ibili y g ade o he (i h) IF-THEN ule, which is calcula ed by compu ing he membe ship alues o he an eceden s: α 1 (x, y, n)= min(µLARGE( δ ame ),µLARGE ( δ ield1 ),µLARGE ( δ ield2)) (4) α 2 (x, y, n)= min(µSMALL( δ ame ),µSMALL ( δ ield1 ),µSMALL ( δ ield2)) (5) α 3 (x, y, n)= max((α3a , α3b )) (6) α 4 (x, y, n)= 1- α 1 - α 2 - α 3 (7) whe e: α 3a (x, y, n)= min(µLARGE( δ ame ),µLARGE ( δ ield1 ),µSMALL ( δ ield2)) (8) α 3b (x, y, n)= min(µLARGE( δ ame ),µSMALL ( δ ield1 ),µLARGE ( δ ield2)) (9) Fo each pixel, he alues α{1,2,3,4} a e he ou pu signals o he uzzy sys em. Each signal co esponds o he ac i a ion deg ee o an indi idual ule and anges om 0 o 1. Since ou p oposed de ec o aims a a pixel-by- p ixel mode decision, al e na i e obus ness measu es a e necessa y. These a e desc ibed in he ollowing subsec ions. A. Inc ease o he obus ness o he uzzy sys em decision The p oposed easoning me hod is based on a single winne ule. The winne is he uzzy IF-THEN ule ha has he maximum ac i a ion deg ee, ha is, he maximum compa ibili y g ade wi h one o he pa e ns des e y low. Missing line T ansmi ed line 3x3 Spa ial- desc ibed by he an eceden s. Howe e i mul iple ac i a io n deg ees o con a y ules a e ac i a ed, choosing he maximally ac i a ed mode easily esul s in w ong decisions. To imp o e his, a decision is adop ed when i s co esponding ule is he mos ac i a ed and also he ac i a ion deg ee o he con a y ule is e y low. B. Spa io- empo al P edic ion In ou p oposal, he inal decision o he cu en pixel is no only based on he decision o he sys em o he cu en pixel, bu applies ’spa io- empo al’ p edic ions, aking in o accoun also he decisions o he pixels in a 3x3 neighbo hood. The idea is o make a decision only when one mode is ac ually clea , and p opaga e he decision un il a new clea decision is aken. To educe e o p opaga ion a meande ed scanning is p oposed (see Fig. 5). The de ec o p ocesses he e en ields in a s eaming ashion, ha is, o m he op-le pixel o he bo om- igh pixel, whe eas he odd ields a e p ocessed om he bo om- igh pixel o he op- le pixel . Fou pixels in he 3x3 window a e spa ial neighbo s and belong o he cu en ield, and ou a e empo al neighbo s o he p e ious ield as shown Fig. 5. C. Tempo al o wa d p edic ion p ocess The empo al p edic ions a e mo e complex han he spa ial p edic ion. To illus a e he p oblem, le us conside he empo al di e ence pa e n o pull-down 3:2 p ocess shown in Fig. 3(a). Analysis o his pa e n shows ha no only he hi d ule is ac i a ed bu also he second one. To be exac , he second ule is ac i a ed e e y i e ields o he ideo sequence. This means ha he MODE o a pixel wi h he same spa ial coo dina es in he p e ious ield no always has o ag ee wi h he cu en one. Fo any pic u e epe i ion pa e n, decisions om he p e ious ield can be ans o med in o new p edic ions as shown in Fig. 6. The alues o di e ence signals a e ep esen ed using he no a io n ’LSL’, which means a LARGE di e ence o δ ield1 and a SMALL di e ence o δ ield2 and a LARGE alue o δ ame . Fo each alue o he di e ence signals in he p e ious ield, he di e en al e na i es o a pixel in he cu en ield a e shown in Fig. 6. F om he knowledge o he p e ious mode, only he alue o δ ield1 can be assigned. Fo ins ance, a pixel om he p e ious ield whe e ideo mode is de ec ed implies a la ge alue o di e ence signals, ha is ’LLL’. In his case, he alue o δ ield1 will be su ely ’L’ in he nex ield and hen, δ ame will be also ’LARGE’. Howe e , he e is no in o ma ion o p edic he alue o δ ield2. Analyzing each possibili y he P e i ous i e ld ( o dd) C u en i e ld ( e en ) empo a l ape u e Spa ial neigh b ou s Cu en p ixel Tempo al neighbou s Fig. 5. The decisions a 9 posi ions in a 3x3-ape u e a e in ol ed in he decision-making p ocess. P. B ox e al.: Local Pic u e- epe i ion Mode De ec o o Video De-in e lacing 1651 P e ious di e ence alues LLL SSS LSL SLL ??? Upda ed di e ence alues L?L S?? S?? L?L ??? Mode o a pixel in he p e ious ield MODE is ideo MODE is s a iona y MODE is epe i ion MODE is unde e mined Tempo al p edic ion o he Mode MODE can be ideo o epe i ion MODE can be s a iona y o epe i ion MODE can be ideo, epe i ion and s a iona y MODE is unde e mined Fig. 8. I pic u e- epe i ion is assumed inco ec ly, ea he ing (le ) will show. Fig. 6. Tempo al p edic ions o he MODE in he p e ious ield. empo al p edic ions o he modes a e shown in Fig. 6. The mul iple modes o he empo al p edic ions ha e an equal bias. D. Rein o cemen o he inal decision The lowcha o he p ocess is shown in Fig. 7. The inpu signal is he MODE o he pixels in he 3x3 neighbo hood. Only i he occu ence o modes exceeds a se o alues C{1,2,3,4} and he e a e no unde e mined decisions, a con ol signal called PATTERN is ac i a ed. I no , i.e. he majo i y o decisions a e unde e mined, he con ol signal will be gene a ed o code he PATTERN signal o ’unde e mined’ decisions. Finally, in pixels whe e none o he ules is su icien ly ac i a ed, he decision o he p e ious pixel in he scanning di ec ions is assigned. Some e oneous mode decisions a e mo e c i ical han o he s. Fo ou de-in e lacing applica ion, epe i ion mode leads o pe ec esul s h ough me ging he lines o ields ha b elong o he same ilm image. Howe e , when his mode is e oneously de ec ed, e.g. in ideo came a ma e ial, annoying ea he ing a e ac s appea in he de-in e lace d p ic u e, as shown in Fig. 8. The consequences o he ideo mode decision is less c i ical, since in his case a obus de-in e lacing echnique is employed ha pe o ms sub- op imal on ilm ma e ial, bu gi es no e y objec ionable a e ac s. Gi en his asymme ical beha iou , p io i y is gi en o he ideo-mode, i.e. he mode o which we assume he e is no pic u e epe i ion. The e o e, his mode is co obo a ed i s ly and i equi es a lowe numbe o modes in he ape u e o ake a decision: C1 <C2≈C3≈C4 (see Fig. 7). Th ough analysis o he wo pa s o he hi d ule, a secon d con ol signal is gene a ed named ‘PHASE’ o iden i y which wo o he h ee ields a e iden ical in he case ha a pic u e epe i ion, e.g. a epe i ion mode, is de ec ed. Fig. 9 shows he placemen o he uzzy mode de ec o in he ideo p ocessing chain o ou de- in e lacing applica ion. Bo h signals gene a ed by he uzzy sys em a e used as con ol signals o de e mine he de-in e lacing s a egy. In case ha a epe i ion mode is de ec ed, he de-in e lacing p ocess becomes pe ec by wea ing wo ields oge he . This is also alid in he case ha he pixel is classi ied as belonging o a s a iona y a ea. Howe e , i he i s o he ou h ule a e he mos ac i a ed, a con en ional ideo de-in e lacing app oach [1] has o be used. E. Imp o ing he pe o mance o he uzzy sys em by membe ship unc ion lea ning F om heu is ic knowledge, he e is no es ic ion o ix he pa ame e s o membe ship unc ions. Howe e , some alues will p o ide be e esul s han o he ones. Ou idea is o selec he mos sui able alues using a se o inpu /ou pu aining p a e ns o image sequences whe e he mode decision is known by he designe . Fi e ields o wo di e en sequences we e used. O iginally bo h sequences a e ideo ma e ial bu he 3:2 and 2:2 pull-down cadences we e gene a ed and used as aining pa e ns. These sequences a e called Kielp an d Bicycle in Sec ion III. Simula ion esul s in Sec ion III p o e ha he me hod is obus o a wide numbe o es sequences. coun e ideo > C 1 1 PATTERN [00] ideo MODE 3X3 nei g hbo hood coun e s a iona y coun e epe i ion > C 2 > C 3 1 1 A ND 0 AND 0 1 1 PATTERN [01] s a iona y PATTERN [10] epe i ion coun e unde e mined ==0 > C 3 1 1 NOT A ND 0 PATTERN [11] unde e mined INPUT SIGNAL DE-INTERLACING STRATEGY DE-INTERLACING TECHNIQUE FUZZY MODE PHASE PREVIOUS DECISION DETECTO R PATTERN Fig. 7. Flowcha o he decision block o inc ease he obus ness o he con ol ’MODE’ signal. Fig. 9. Placemen o he uzzy ilm-mode de ec o in he ideo chain. A ND 0 OUTPUT SIGNAL IEEE T ansac ions on Consume Elec onics, Vol. 53, No. 4, NOVEMBER 2007 1652 TABLE II MEMBERSHIP FUNCTION PARAMETERS AFTER THE LERANING PROCESS Inpu Mode M ode Mode M ode Ini ial a iable Pa ame e s ideo ‘ s a iona y’ ‘ epe i ion’ ‘ unde e mined’ pa ame e s LSL SLL D0 1 0 0.5 0 0 0 δ ame D1 8 8 1.5 8 8 8 D2 0 0 0 0 0 0 D3 8 8 8 8 8 8 D0 0 0 0 0 0 0 δ ield2 D1 2 2 2 2 2 2 D2 0 0 0 0 0 0 D3 2 2 2 2 2 2 D0 0 0 0 0 0 0 δ ield1 D1 0.25 2 0.5 2 2 2 D2 0 1 0 1 0 0 D3 2 8.5 2 9 2 2 ha he me hod is obus o a wide numbe o es sequences. Fo he uning p ocess, we used he de elopmen en i onmen X uzzy3.0 [14]. This is an 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 o n uzzy logic. X uzzy3.0 in eg a es a CAD ool, named x s l [15], o une uzzy sys ems desc ibed in he en i onmen . We u he applied a se o aining ideo sequences. Onl y he alues D0, D1, D2 and D3 ha de ine he membe ship unc ions ha e been adjus ed in he lea ning s age. The Le enbe g-Ma qua d algo i hm has been selec ed as supe ised lea ning algo i hm and he esul s o he p ocess a e shown in Table II. This able shows he uned pa ame e s o each one o he modes, and also he ini ial pa ame e s o he membe ship unc ions ha we e ixe d manually. Fo he i s ield o he ideo sequence, he ini ial pa ame e s a e used. Fo he es o he ields, he uned pa ame e s o each mode is aken. F. Mode il e ing o imp o e obus ness Since an e oneous ideo de ec ion in he epe i ion a ea is less se ious han an e oneous epe i ion mode decision, a simple spa ial il e ing is pe o med o sp ead he ideo mode decision. Fig. 10 shows he shape o he spa ial ape u e. As i can be seen, i con ains mo e pixels in he e ical di ec ion han in he ho izon al. The eason is ha he image is p ocessed p ocessed in a s eaming di ec ion, so mis akes a e ansmi ed along ho izon al di ec ion. To a oid his, a highe num b e o pixels in e ical di ec ion a e conside ed. The inal s uc u al o e iew o he p oposed de ec o is shown in Fig. 11. III. PERFORMANCE OF THE PROPOSED ALGORITHM The pe o mance o he p oposed algo i hm has been e alua ed in he de-in e lacing applica ion. We in es iga ed he image quali y and calcula ed he compu a ional cos o he de ec o . Subsec ion A desc ibes he cos calcula ions. A b ie desc ip ion o he ideo es sequences can be ound in Subsec ion B and inally, he o e all pe o mance is gi en in Subsec ion C. A. Algo i hm Cos The algo i hmic cos is measu ed using he numbe o loa ing poin ope a ions (FLOPS) as a(n in e se) igu e o me i . The algo i hm equi es 543.7 Megas loa ing poin ope a ions o analyze one ield o a ideo sequence wi h a esolu ion o 720x576. We ha e conside ed his measu emen ins ead o compu a ional ime as i is s ongly depends on he pla o m on which he algo i hm is implemen ed and he e icienc o he p og amming Fig. 10. 3x9-ape u e o he spa ial il e ing. Fig. 11. S uc u al o e iew o he ilm de ec o . FIELD MEMOR Y FIELD MEMOR Y δ ield2 FUZZ Y LOGIC SYSTEM 3x3 ape u e MODE FILTERING δ ield1 Modi ica ion membe ship pa ame e s Upda ed MODE MEMOR Y δ ame MODE P. B ox e al.: Local Pic u e- epe i ion Mode De ec o o Video De-in e lacing 1653 ( a ) TMF se q uence ( b ) Fi e- ose se q uence ( c ) Rena a h y b id se q uence Fig. 12. Snapsho s o eal sequences used o p o e he pe o mance o he p oposed algo i hm. measu emen ins ead o compu a ional ime as i s ongly depends on he pla o m on which he algo i hm is implemen ed and he e iciency o he p og amming. B. Desc ip ion o he Sequences Subsec ion C con ains esul s om he analysis o se e al sequences. Some o hem a e eal sequences om TV channels o mo ies, and o he s a e es ideo ma e ial. Fo y ields o each sequence ha e been p ocessed. Th ee o hese sequences ha e been especially analyzed: - TMF. This is an o iginal sequence cap u ed om a Du ch b oadcas channel called TMF. The sequence is an in e lace d ideo clip (2:2 pull-down mode) wi h an o e lay con aining a icke - ape ideo ex as can be seen in Fig. 12(a). I also con ains s a iona y a eas (a ound he clock an d he TMF-logo). - Fi e- ose. This is an in e laced 2:2 ilm sequence. The de ec ion o epe i ion mode is di icul due o he ine de ails in he man’s bea d as shown in Fig. 12(b). Mo eo e his sequence con ains a e y low le el o mo ion. - Rena a. This sequence has been used o show he imp o emen s in oduced by he indi idual obus ness measu es explained in Sec ion II. I is o iginally a ideo scene. Howe e , i has been a i icially ans o med in o an in e laced 2:2 epe i ion mode. The sequence has hen b een con e ing in o a hyb id sequence, by adding a ho izon ally ho izon ally mo ing ideo ex in he middle o he ields, as shown in Fig. 12(c). C. Simula ion Resul s To p o e he pe o mance o he p oposed de ec o , he h ee- ields VT il e ing app oach [16] is used i he ’ ideo’ o ’unde e mined’ mode is de ec ed. On he o he hand, i one o he ’ epe i ion’ mode is de ec ed, he de-in e lacing p ocess is implemen ed by wea ing. Compa ing he de-in e laced wi h he o iginal p og essi e pic u e o Rena a, a Mean Squa ed E o can be calcula ed. Fig. 13 shows he ela i e MSE-sco e as a pe cen age o he MSE-sco e ob ained wi h he VT il e ing [16]. As can be seen, ou inal p oposal educes he o al MSE e o wi h almos 60 %. I includes he imp o emen s ha a e desc ibed in subsec ions {A, B, C, D, E, F} o Sec ion II. The esul s achie ed by he p oposal wi h a modi ica ion o membe ship unc ion pa ame e s a e sligh ly b e e (column P4 in Fig. 13) han he ob ained wi h ixed pa ame e s (column P3 in Fig. 13). The de ec o has also been used o de-in e lace he eal sequences shown in Tables III and IV. I dec eases he o al MSE sco e by a high ac o in pe cen age (almos 100%) in he majo i y o ilm sequences (see Table III). This no only p oduces a pe ec ly de-in e laced image, bu also conside ably educes he complexi y as wea ing is he me hod wi h he lowes compu a ional cos . Due o he p esence o low mo ion and/o a high numbe o he de ails, epe i ion mode is no well de ec ed in some o he ilm sequences and he MSE only alls o 40%. This is no c ucial o de-in e lacing applica ions because con en ional de-in e lacing is applied when ac ual epe i ion is misin e p e ed as ideo. Finally, he o al MSE is sligh ly educed when he de ec o is used o ideo sequences (see Table IV). This is due o he imp o ed de-in e lacing o he ew s a ic a eas. Al hough he modi ica ion o membe ship unc ion pa ame e s does no in oduce many ad an ages o he Rena a hyb i d Tables III and IV. RE NA T A HY B RID SEQUENCE 200 180 160 140 120 MSE % 1 00 80 60 40 20 0 VT P1 P2 P3 P4 P5 P oposal P1 : Simple Fuzzy Sys em(SFS) P2 : SFS+ {A} P3 : SFS+ {A, B, C, D} P4 : SFS+ {A, B, C, D, E} P5 : SFS+ {A, B, C, D, E, F} Fig. 13. MSE pe cen age o each one o he p oposals. IEEE T ansac ions on Consume Elec onics, Vol. 53, No. 4, NOVEMBER 2007 1654 TABLE III SIMULATION RESULTS OF FILM SEQUENCES Sequence Sh ek Gladia o S ai s F a go F a go Ma ze1 Ma ze2 F i e Chop F a go V anessa Chop Fligh o ice e p ai ose hun land T o al MSE De ec o o 327.607 62.72 93.96 208.54 327.31 745.74 682.17 204.61 52.01 364.13 217.53 220.69 231.65 De ec o on 1.52 0.098 0 124.77 0.143 419.78 0 0 0.077 0.74 0.21 2.83 0 Reduc ion(%) 99.53 99.84 100 40.16 99.95 43.708 100 100 99.85 99.79 99.901 98.71 100 TABLE IV SIMULATION R ESULTS OF VIDEO Sequence Anima ix-a Anima ix-b Dieano he day Bicycle Kielp Gi lga e Wman Rena a Xmen2 News eade T o al MSE De ec o o 139.71 712.46 446.38 1517.03 5321.83 156.109 71.56 450.425 266.52 1027.992 De ec o on 52.06 711.91 371.29 1503.52 5319.12 154.71 71.45 449.79 250.81 1027.93 Reduc ion(%) 62.74 0.03 16.83 0.9 0.05 0.8 0.19 0.01 5.89 0.01 sequence, i is necessa y o achie e good esul s o some sequences in Tables III and IV. The esponse o he de ec o was also analyzed o he TMF and Fi e- ose sequences. The ou pu modes when p ocessing he snapsho in Fig. 12(a) can be isually co obo a ed in Fig. 14(a). In his igu e, whi e colo means epe i ion mode, ligh g g ey means s a iona y a eas, da k g ey co esponds o ideo mode and black colo shows zones whe e he decision is no clea . As can be seen, he c i ical a eas o he ield a e co ec ly de ec ed. The MSE alue o he TMF sequence could no be included in Table III since he o iginal p og essi e ma e ial is no a ailable. The pe o mance o he o iginal Fi e- ose ( ilm ma e ial) sequence is pe ec as shown in Table III. I his sequence is ans o med in o ideo by elimina ing he epea ed ields, ideo mode is also co ec ly de ec ed despi e he low le el o mo ion as shown Fig. 14(b). Finally, a es is p oposed o p o e he ad an ages o using uzzy de ini ions o he concep s SMALL and LARGE ins ead o c isp de ini ions. The esul s show a mo e c i ical dis inc ion among he di e en mode a eas o he ield i c isp de ini ions a e used. This p oduces se ious mis akes as i can be seen in Fig. 15(a) o Rena a hyb id sequence and in Fig. 15(b) o TMF sequence. Un o una ely, he e is no compe i i e de ec o ha p e o ms a local pic u e epe i ion mode de ec ion in cu en scien i ic li e a u e. This is why compa isons wi h o he p oposals o simila cha ac e is ics a e no included in his sec ion. IV. CONCLUSIONS The de-in e lacing o ideo ma e ial con e ed om il m can be pe ec , p o ided i is de ec ed co ec ly. Typically, howe e , a ailable de ec o s ail in cases whe e ideo o e lays a e me ged wi h ilm ma e ial, o when non- s anda d epe i ion pa e ns a e used. Bo h p oblems occu equen ly in ele ision b oadcas . Fo hese hyb id and/o i egula cases, we ha e p oposed a de ec o ha is capable o de ec locally in he image di e en pic u e- epe i ion pa e ns. By dis inguishing only he ollowing cases: - S a iona y, i.e. all 3 ields show objec a same posi ion - N o iden ical ields, i.e. all 3 ields show objec a di e en posi ion Pai ed iden ical ields case A, i s wo ields show objec a same posi ion, hi d ield a di e en posi ion ii hid i ld di ii Fig. 14. Mode decisions aken by he sys em o (a) TMF and (b) Rena a sequences. Whi e indica es epe i ion, ligh g ey s a iona y, da k g ey ideo and black a e unclea a eas. (a) Rena a sequence (b) TMF sequence Fig. 15. Simula ion esul s using c isp de ini ions o LARGE and SMALL. P. B ox e al.: Local Pic u e- epe i ion Mode De ec o o Video De-in e lacing 1655 Pai ed iden ical ields case B, las wo ields show objec a same posi ion, i s ield a di e en posi ion - Unclea , i.e. he local da a is ambiguous we designed a p ic u e epe i ion de ec o , sui able o all possible pa e ns wi hou limi a ion o he common pa e ns, like 2:2 and 3:2 pull-down. Fo ins ance, a long a bi a y cadence such as 3:2:2:3 can be de ec ed since he ules an eceden s only compu e absolu e di e ences among h ee consecu i e ields. The de ec o combines uzzy logic ules, o deal wi h unce ain cases, and uses spa io- empo al p edic ion o ge a obus decision signal e en in unclea a eas. Ou e alua ion shows a e y a ou able pe o mance and an a ac i e low compu a ional complexi y. REFERENCES [1] G. de Haan and E. B. Belle s, De-in e lacing - an o e iew. P oc. o he IEEE, ol. 86, Issue 9, pp. 1839-1857, Sep. 1998. [2] T. C. Lyon and J. J. Campbell, Mo ion sequence pa e n de ec o 1, 1991. Uni ed S a es Pa en O ice US 4,982,290. [3] C. Co ea and R. Schwee , Film mode de ec ion p ocedu e and de ice. Assignee: Deu sche Thomson-B and GMBH, Villingen-Schwennigen (DE), July 1, 1998. Eu opean Pa en O ice 0567072B1. [4] H. Y. W. Lucas, P og essi e/in e lace and edundan ield de ec ion o encode . Applican : STMICRO-Elec onics Asia Paci ic PTE LTD, Singapo e, June, 2000. Wo ld In ellec ual P ope y O ganiza ion, In e na ional Publica ion Numbe : WO 00/33579. [5] P. Swan, Sys em and me hod o econs uc ing nonin e laced cap u ed con en o display on a p og essi e sc een. Assignee: ATE Technologies, Inc. Tho nhill, anada, Ap . 25, 2000. Uni ed S a es Pa en O ice US 6,055,018. [6] G. de Haan, H. Huijgen, P .Biezen, and O. Ojo, Me hod and appa a us o disc imina ing be ween mo ie ilm and non-mo ie ilm and gene a ing a pic u e signal p ocessing mode con ol signal. Assignee: U.S. Philips Co po a ion, New Yo k, USA, No . 15, 1994. Uni ed S a es Pa en O ice US 5,365,280. [7] A. Dommisse, Film de ec ion o ad anced scan a e con e e s, M. Sc.Thesis, TUE, Eindho en, Aug. 2002. [8] C.-C. Ku and R.-K. Liang, Robus Laye ed Film-Mode Sou ce 3:2 Pulldown De ec ion/Co ec ion. IEEE T ans. on Consume Elec onics, ol.50, no.4, pp. 1190-1193, No . 2004. [9] G. de Haan and R. B. Wi eb ood, Recognizing ilm and ideo objec occu ing in pa allel in single ele ision signals ields. Assignee: Konin- klijke Philips Elec onics N. V., Eindho en, NL, Aug. 30, 2005. Uni ed S a es Pa en O ice US 6,937,655. [10] J. L. Cas o, Fuzzy logic con olle s a e uni e sal app oxima o s. IEEE T ans. on ys ems, Man and Cybe ne ics, ol.25, no.4, pp. 629-635, Ap . 1995. [11] L. He and H. Zhang, Mo ion objec ideo on ilm de ec ion and adap i e de-in e lace me hod based on uzzy logic. Assignee: nDSP Co po a ion, Campbell, CA, Sep. 28, 2004. Uni ed S a es Pa en O ice US 6,799,168. [12] G. de Haan, and P. W. A. C. Biezen, Sub-pixel mo ion es ima ion wi h 3- D ecu si e sea ch block-ma ching.Signal P ocessing: Image Commu- nica ion 6, pp.229-239, June 1994. [13] E. Cox, The Fuzzy Sys ems Handbook: A P ac i ione ’s Guide o Build- ing, Using, and Main aining Fuzzy Sys ems. AP P o essional Edi o ial (2nd edi ion). [14] F.J. Mo eno-Velo, I. Ba u one, S. Sánchez-Solano, and A. Ba iga, Rapid design o complex uzzy sys ems wi h X uzzy.P oc. IEEE In . Con . on Fuzzy Sys ems, pp.342-347, S . Louis, USA, May 2003. [15] 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. [16] M. Wes on, In e pola ing lines o ideo signals. Assignee: B i ish B oadcas ing Co po a ion, London, GB2, Dec. 6, 1988. Uni e d S a es Pa en O ice US 4,789,893. Piedad B ox was bo n in 1979 in Có doba, Spain. She ecei ed he deg ee in Elec onic Physics o m he Uni e si y o Có doba in 2002, and he Ad anced S udies Deg ee in Mic oelec onics om he Uni e si y o Se ille in 2004. Since 2002, she has been wi h he Mic oelec onics Ins i u e o Se ille (IMSE), which belongs o he Spanish Resea ch Council (CSIC) and he Uni e si y o Se ille. She ecei e d a ellowship o In oduc ion o Resea ch o Unde g adua e S uden s du ing 2002. Cu en ly, she is a Pos g adua e Re- sea ch Fellow and has a Pos g adua e Fellowship unde F.P.U. p og am om he Spanish go e nmen . He esea ch a eas a e uzzy image p ocessing algo i hms and hei ha dwa e implemen a ion (s a ing om high-le el desc ip ions o p o o yping in FPGAs). She belongs o he ’Digi al and Mixed Signal In eg a ed Ci cui Design G oup’ o IMSE. Leon Woes enbe g ecei ed he M.Sc. deg ee in Elec ical Enginee ing om he Uni e si y o Tech- nology Eindho en in 2006. His inal p ojec in ol ed con en -adap i e ideo de-in e lacing unde supe ision o Ge a d de Haan. Since 2000 he has been employed, and pe o med his M.Sc. inal p ojec a Axon Digi al Design, a manu ac u e o audio and ideo p ocessing sys ems o ele ision b oadcas and p oduc ion. As an embedded so wa e enginee he de eloped and e- used open-sou ce so wa e in a comme cial en i onmen . Since 1992 he is in ol ed in open-sou ce so wa e p ojec s as de elope and p ojec manage . Cu en ly, since 2004, as a senio sys ems designe he designs signal p ocessing and con ol sys ems and so wa e and acqui es and p epa es newly a ailable echnology o use in u u e designs. His p o essional in e es s in ol e ope a ing sys ems, ha dwa e/so wa e codesign, ideo and g aphics, he open-sou ce de elopmen model and he use o open-sou ce so wa e in comme cial en i onmen s. Ge a d de Haan (Senio Membe , IEEE) ecei ed B.Sc., M.Sc., and Ph.D. deg ees om Del Uni- e si y o Technology in 1977, 1979 an d 1992 espec i ely. He joined Philips Resea ch in 1979. He has led esea ch p ojec s in he a ea o ideo p ocessing, and pa icipa ed in Eu opean p ojec s. He has coached s uden s om a ious uni e si ies, and eaches since 1988 o he Philips Cen e o Technical T aining. Cu en ly, he is a Resea ch Fellow in he Video P ocessing & Visual Pe cep ion g oup o Philips Resea ch Eindho en, and a pa - ime ull P o esso a he Eind- ho en Uni e si y o Technology eaching ”Video P ocessing o Mul imedia Sys ems”. He has a pa icula in e es in algo i hms o mo ion es ima ion, ideo a e con e sion, and image enhancemen . His wo k in hese a eas has esul ed in se e al books, mo e han 120 pape s, abou 100 pa en s, and a ious comme cially a ailable ICs. He was he i s place winne in he 1995 and 2002 ICCE Ou s anding Pape Awa ds p og am, he second place winne in 1997, 1998 and 2003, and he 1998 ecipien o he Gilles Hols Awa d. In 2002, he ecei ed he Ches e Sall Awa d om he IEEE Consume Elec onics Socie y. The Philips ‘Na u al Mo ion Tele ision’ concep , based on his PhD-s udy ecei ed he Eu opean Video Inno a ion Awa d o he Yea 95 om he Eu opean Imaging and Sound Associa ion. In 2001, he successo o his concep ”Digi al Na u al Mo ion Tele ision” ecei ed a ”Business Inno a ion Awa d” om he Wall S ee Jou nal Eu ope. Ge ad de Haan is a Senio Membe o he IEEE.