Segmentering i planer

Segmenteringen i fly er den automatiske identifikation ved computermetoder af planernes grænser i en video . Dette består i automatisk at finde de redigeringspunkter , der oprindeligt blev defineret af instruktøren , ved at måle diskontinuiteterne mellem de på hinanden følgende rammer i videoen. Disse redigeringspunkter er naturligvis kendt af producenten af videoen, men er generelt ikke afsløret eller tilgængelige. For at undgå en lang og kedelig identifikation af planer ved at se for en menneskelig operatør er der udviklet automatiske metoder af computerforskere.

Det er det ældste og mest undersøgte problem inden for videoindeksering , der anses for at være en vigtig byggesten for at muliggøre analyse og søgning af videoer. I begyndelsen af 2000'erne var der kun nogle få direkte anvendelser af segmentering i skud for offentligheden eller i digital videosoftware . Det er dog et stort skridt i analysen af video, der tillader definition og brug af teknikker til at finde information i videoer.

Definition

Segmentering i skud består i at bestemme de forskellige skud i en video. Dette giver kun mening, hvis videoen faktisk indeholder skud, det vil sige, den blev redigeret af en instruktør . Visse typer videoer ( videoovervågning , personlige videoer osv.) Egner sig derfor ikke til denne type teknik. Videoerne, der generelt betragtes, er film eller tv- shows .

Segmentering i skud kaldes undertiden (forkert) af nogle forskere "segmentering i scener". Den segmentering i scener er dog en anden opgave, som består i at identificere de scener , hvor dette begreb defineres som en gruppering af skud deler en vis semantisk sammenhæng.

Vi kan også henvise til segmenteringen i skud som et "omvendt Hollywood-problem" for at understrege, at det er den omvendte funktion af redigeringen : det er dekonstruktionen af videoen for at identificere byggestenene til basen, der er filmet af instruktøren: planerne.

Forskellige typer overgange mellem skud

Der er mange, mange måder at skifte mellem to skud på. Den enkleste er den pludselige overgang: vi går fra et skud til et andet uden et overgangsbillede. For at gøre denne passage mere fleksibel, har direktørerne forestillet en bred vifte af gradvise overgange, svinder til sort, crossfades , klude , og mange andre, gjorde stadig lettere ved brugen af computere., Og selv forbruger videoredigeringsprogrammer .

Til segmentering i fly skelner forskere generelt kun to typer: bratte overgange (også kaldet nedskæringer fra engelsk "udskæring") og progressive overgange, som inkluderer alle andre typer overgange.

Historisk

Det første arbejde med segmentering i skud går tilbage til begyndelsen af 1990'erne. Det er den ældste og mest udforskede videoindekseringsopgave. Der er to hovedårsager til dette:

Det er en relativt enkel opgave at udføre, fortolke og evaluere.
Identifikation af klipene giver et resultat, der anses for at være det første skridt i at kunne løse problemer med videoindeksering på højere niveau. Udførelsen af plan-segmenteringsalgoritmer er derfor afgørende for domænet generelt.

Et stort antal algoritmer blev offentliggjort i 1990'erne og 2000'erne. En stor vanskelighed er sammenligningen af resultaterne af de forskellige foreslåede algoritmer, testet på forskellige korpusser med hensyn til størrelse og indhold. Oprettelsen af TRECVID i 2003 var et vigtigt skridt, da det introducerede standardpræstationsmålinger og vigtigst af alt fælles indhold, som muliggør en upartisk sammenligning af ydeevne. Korpusstørrelsen er ret stor (400 timer i 2007), men indholdet forbliver ret homogent (for det meste tv-nyheder og dokumentarfilm ).

Et lignende initiativ blev lanceret i Frankrig i 2005 under navnet ARGOS med indhold leveret af INA og CERIMES .

Et andet problem knyttet til udførelsen af algoritmer fremgår af den første forskning. Mens detektionsresultaterne for pludselige overgange er ret gode hurtigt, er dette ikke tilfældet for gradvise overgange. I slutningen af 1990'erne og begyndelsen af 2000'erne så vi fremkomsten af adskillige artikler, der fokuserede på vanskelighederne med at opdage progressive overgange.

I 2002 offentliggjorde Alan Hanjalic fra Delft University of Technology en artikel med den provokerende titel: “Shot Boundary Detection: Unraveled and Resolved? »(Oversættelse: Segmentering i planer: et problem løst? ), Hvor han bekræfter, at hovedproblemet med de foreslåede metoder er deres store følsomhed over for tærskelværdier, hvilket betyder, at manuelle justeringer skal foretages i henhold til de typer videoer, der skal behandlet. Han fortaler derfor brugen af robuste statistiske teknikker baseret på beslutningsteori .

Selvom mange punkter stadig skal løses (evaluering af store heterogene korpusser, dårlig ydeevne til at detektere progressive overgange, afhængighed af manuelle justeringer osv.), Formaliserer Hanjalic gennem titlen på sin artikel det faktum, at segmentering i planer betragtes af det videnskabelige samfund skulle være et "løst" problem.

Metoder

Hovedideen bag segmenteringsmetoderne i fly er, at billederne i nærheden af en overgang er meget forskellige. Vi forsøger derefter at identificere diskontinuiteterne i videostrømmen.

Det generelle princip er at udtrække en observation fra hvert billede og derefter definere en afstand (eller et mål for lighed) mellem observationer. Anvendelse af denne afstand mellem to på hinanden følgende billeder over hele videostrømmen producerer et endimensionelt signal, hvor vi derefter ser efter toppe (hhv. Trug, hvis lighedsmåling) svarer til øjeblikket med stærk ulighed.

Observationer og afstande

Den enkleste observation er ganske enkelt sæt af pixels i billedet. For 2 billeder og dimension N × M er den åbenlyse afstand derefter gennemsnittet af de absolutte forskelle pixel til pixels (afstand L1): $I_1$ $I_ {2}$

{\ displaystyle d (I_ {1}, I_ {2}) = {\ frac {1} {NM}} \ sum _ {i = 1} ^ {N} \ sum _ {j = 1} ^ {M} | I_ {1} (x_ {i}, y_ {j}) - I_ {2} (x_ {i}, y_ {j}) |}

Mere raffinerede tilgange måler muligvis kun betydelige ændringer og filtrerer pixels ud, der genererer for små forskelle, som kun tilføjer støj.

Desværre er teknikkerne i pixeldomænet meget følsomme over for bevægelse af objekter eller kameraer. Bloker matchende teknikker er blevet foreslået at reducere bevægelse følsomhed, men pixel domæne metoder er stort set blevet fortrængt af histogram baserede metoder .

Histogrammet, af luminans eller farve, er en udbredt observation. Det er let at beregne og er relativt robust over for støj og objektbevægelse, fordi et histogram ignorerer rumlige ændringer i billedet. Mange beregningsmetoder teknikker (på hele billedet, på blokke ...) og afstande (L1, cosinus ligheden ,, ² test ...) er blevet foreslået. En sammenligning af udførelsen af forskellige observationer på forskellige videoindhold viste, at brugen af histogrammer gav stabile og gode kvalitetsresultater.

Metoderne ved hjælp af histogrammet lider imidlertid af store mangler: de er ikke robuste over for pludselige ændringer i belysning (fotografer blinker, sol osv.) Eller til hurtige bevægelser.

For at løse disse problemer bruges en anden observation ofte: billedets konturer. Disse detekteres på hvert billede ved hjælp af en kantdetekteringsmetode , og konturerne sammenlignes muligvis efter registrering . Denne teknik er robust over for bevægelse såvel som for ændringer i belysning. På den anden side er kompleksiteten høj.

Andre observationer er blevet foreslået: karakterisering af kamerabevægelse eller detektion i det komprimerede domæne fra DCT- koefficienter eller endda en kombination af observationer, for eksempel intensitet og bevægelse.

Påvisning af diskontinuiteter

Anvendelse af en måling på observationer af på hinanden følgende billeder producerer et endimensionelt signal, hvor det derefter er nødvendigt at identificere diskontinuiteterne, som indikerer en ændring af planet.

Den enkleste metode er en tærskel for signalet med en fast værdi. Denne metode lider under mange ulemper: manuel tilpasning af tærsklen i henhold til corpus , følsomhed over for støj, til bevægelse ... En mere robust metode består i lokal tilpasning af tærsklen ved at beregne den for eksempel som værende middelværdien af signal i et vindue omkring den betragtede top.

En mere tilfredsstillende metode er at bestemme værdien af tærsklen ud fra et skøn over fordelingen af diskontinuiteterne. Den fordeling antages at være Gaussisk parametre og tærsklen er defineret som , hvor r bruges til at indstille antallet af falske alarmer. ${\ displaystyle {\ mathcal {N}} (\ mu, \, \ sigma ^ {2})}$ ${\ displaystyle S = \ mu + r \ sigma}$

En mere teoretisk baseret tilgang er at bruge beslutningsteori . Konventionelt defineres to hypoteser for hvert billede: overgang eller ikke-overgang, og beslutningen træffes ved at sammenligne sandsynlighedsforholdet med det a priori sandsynlighedsforhold. Brug af en Bayesisk estimeringsmetode løser nogle problemer forbundet med denne meget enkle tilgang.

En meget anden metode er udviklet af Truong et al. , der foreslår ikke at træffe en lokal beslutning, men en global beslutning, der forsøger at finde den optimale segmentering af hele den betragtede video. Forfatterne vedtager en tilgang baseret på det maksimale efterfølgende for at finde den segmentering, der maksimerer sandsynligheden , sandsynligheden for, at segmenteringen er optimal, idet man kender observationerne . For at undgå en systematisk udforskning af alle mulige segmenteringer anvendes en dynamisk programmeringsteknik . ${\ displaystyle P (S | O)}$ $S$ $O$

Forbedringer

Metoderne beskrevet ovenfor er ikke altid effektive til at detektere gradvise overgange. Heng et al. påpege, at de fleste metoder er baseret på måling af forskellen i observationer mellem tilstødende billeder, og at disse forskelle kan være små for gradvise overgange.

For at løse dette problem er der blevet foreslået teknikker baseret på detektion og / eller sporing af objekter. Den generelle idé er, at sporing af et objekt indikerer kontinuitet, og tab af sporing kan indikere overgang. Andre foreslår specifikt at modellere opførelsen af hver type progressiv overgang ( fade til sort, crossfade , lukker osv.) Ved heuristiske metoder og dobbelt tærskelsteknikker eller et neuralt netværk .

Crossfades er særlig vanskelige at opdage, og noget arbejde fokuserer kun på denne opgave. Andre fokuserer på skodder , især fordi det er en teknik, der er meget brugt på tv.

Et andet stort problem er, at pludselige ændringer i belysning, blink, pletter, solens udseende / forsvinden ... Specifikke metoder er udviklet til at reducere falske alarmer forbundet med disse hændelser ved hjælp af detektering af konturer eller efterbehandling.

Forestillinger

Resultaterne af segmenteringen i planer evalueres ved målinger, der er resultatet af søgningen efter information : præcision og tilbagekaldelse .

Ved pludselige overgange er beregningen af disse to målinger enkel: en overgang opdages godt, savnes eller falsk. For progressive overgange, der er spredt over flere billeder, indføres der undertiden en supplerende måling for at måle antallet af billeder, der faktisk registreres korrekt. Afhængigt af forfatterne evalueres resultaterne undertiden ved at skelne mellem de pludselige overgange og de gradvise overgange eller nogle gange ved at blande resultaterne.

Sammenligningen af resultaterne mellem de forskellige algoritmer er meget delikat, især fordi forestillingerne kan variere betydeligt alt efter korpus. Der blev foretaget nogle sammenligningsforsøg, men var ikke helt tilfredsstillende. I 2001 oprettede TREC- evalueringskampagnen , oprindeligt afsat til tekst , et "videospor" beregnet til evaluering af algoritmer til video. I 2003 blev opgaven uafhængig under navnet TRECVID og indførte tilvejebringelsen af et fælles korpus og en uafhængig evaluering.

Resultaterne af disse evalueringskampagner bekræfter, at algoritmerne har nået modenhed med hensyn til pludselige overgange med mange tilbagekaldelses- og præcisionsscorer over 90%. Påvisning af progressive overgange er på den anden side altid en vanskelig opgave med generelt score på 70% i præcision og tilbagekaldelse, hvor de bedste algoritmer undertiden smertefuldt når 80%.

Metodernes kompleksitet evalueres også og er meget forskellig i henhold til algoritmerne, der spænder fra 20 gange hurtigere end realtid til mere end 20 gange langsommere.

Ansøgninger

Segmentering i skud anses generelt for at være for lav til at blive brugt som i en video- navigations- og informationssøgningsapplikation . Et hurtig frem-skud for skud kan dog med fordel erstatte en traditionel hurtig fremad baseret på et simpelt spring af et fast antal billeder.

Den primære anvendelse af segmentering i skud er at give et arbejdsgrundlag for videoindekseringsalgoritmer på højere niveau. For eksempel til bestemmelse af scener , produktion af videooversigter eller endda analyse af sportsvideoer.

Nogle videoredigeringssoftware , for eksempel Windows Movie Maker og VirtualDub , bruger segmentering i klip til at generere præ-trim for brugeren, hvilket giver mulighed for let ikke-lineær redigering. For cinephiles, der er interesseret i filmanalyse, kan disse teknikker muligvis være af interesse for automatisk at bestemme antallet af skud i en film og deres placering.

Plansegmentering bruges også i billedgendannelsesteknikker til korrektion af defekter, der er forbundet med plane ændringer, såsom kalibreringsekko og billedforvrængning.

Noter og referencer

(da) Alan Hanjalic, “Detektering af skudgrænse: udrullet og løst? », Fac. af Inf. Technol. & Syst., Delft University of Technology, IEEE Transactions on Circuits and Systems for Video Technology, Feb 2002.
(da) Chung-Lin Huang, Bing-Yao Liao, "En robust metode til detektering af sceneskift til videosegmentering", IEEE-transaktioner på kredsløb og systemer til videoteknologi, december 2001.
(en) Yingying Zhu, Dongru Zhou, "Detektion af sceneskift baseret på analyse af lyd- og videoindhold", Coll. fra datalogi, Wuhan University, Kina, femte internationale konference om computernational intelligens og multimedieapplikationer, 2003.
(i) Shah Mubarak, "Gæst Indledning: Changing Shape of Computer Vision i det enogtyvende århundrede," International Journal of Computer Vision, Springer Netherlands, 2002.
ARGOS-kampagne til evaluering af værktøjer til overvågning af videoindhold
(in) Rainer Lienhart, "Dissolve Reliable Detection", International Journal of Image and Graphics, 2001.
(da) Min Wu, Wayne Wolf, Bede Liu, "En algoritme til detektion af tørre", 1998
(in) CW Ngo, TC Pong RT Chin, "Detection of Gradual Transitions through Temporal Analysis Slice" CVPR 1999.
Det er ikke altid en afstand i den matematiske forstand.
(i) Kiyotaka Otsuji, Yoshinobu Tonomura, og Yuji Ohba, "Video browsing hjælp lysstyrke data", Visuel Kommunikation og billedbehandling '91: Image Processing, 1991.
Akio Nagasaka Yuzuru Tanaka, "Automatisk videoindeksering og fuldvideo-søgning efter objektudseende", anden arbejdskonference om visuelle databasesystemer, 1991.
(da) John S. Boreczky og Lawrence A. Rowe, "Sammenligning af detektionsmetoder til videooptagelsesgrænser", Lagring og hentning til billed- og videodatabaser (SPIE), 1996.
(en) Heng WJ; Ngan KN, “Implementeringen af objektbaseret skudgrænsedetektion ved hjælp af kantsporing og sporing”, IEEE International Symposium on Circuits and Systems, 1999.
(en) Heng WJ; Ngan KN, "Bestemmelse af lommelygte med høj nøjagtighed til detektion af skudgrænser", Signalbehandling: Billedkommunikation, bind 18, nummer 3, marts 2003.
(i) Juan M. Sanchez, Xavier Binefa Jordi Vitria, "Shot Partitionering Based Anerkendelse af TV-reklamer" Multimedia værktøjer og applikationer, 2002.
(i) P. Bouthemy Mr. Gelgon F. Ganansia. “En samlet tilgang til detektion af skiftændring og karakterisering af kamerabevægelser”, Intern publikation nr. 1148, IRISA , november 1997.
Boon-Lock Yeo, Bede Liu, "hurtig sceneanalyse på komprimeret video", CirSysVideo (5), nr. 6, december 1995.
(da) T. Kaneko, O. Hori, "Cut Detection Technique from MPEG Compressed Video Using Likelihood Ratio Test", ICPR, 1998.
(da) Ba Tu Truong, Chitra Dorai, Svetha Venkatesh "Nye forbedringer til at skære, falme og opløse detektionsprocesser i videosegmentering", Forløb fra den ottende internationale ACM-konference om multimedie, 2000.
(i) A. Hanjalic M. Ceccarelli, RL Lagendijk, J. Biemond, "Automatisering af systemer, der muliggør søgning på lagrede video data" lagring og genfinding for Billede og video Databaser, 1997
(i) Nuno Vasconcelos, Andrew Lippman, "En Bayesiansk modellering ramme for Video Shot Segmentering Karakterisering og indhold" Workshop om indholdsbaseret Adgang for Billede og Video Biblioteker 1997.
(i) Ba Tu Truong, Venkatesh, S., "at finde den optimale Temporal Partitionering af video-sekvenser", IEEE International Conference on Multimedia og Expo 2005.
Rainer Lienhart, “Sammenligning af algoritmer til automatisk registrering af skudgrænser”, Lagring og hentning af billed- og videodatabaser (SPIE), 1998.
(en) TRECVid 2006, " Shot Boundary Task Overview ",
(i) Xuan Wei Chen Jin-Hau Kuo Wei-Ta Chu Ja-Ling Wu, "er Action film baseret segmentering og sammendrag tempo analyse", ACM International Workshop on MMS-hentning SIGMM information 2004.
Ewa Kijak, “ Multimodal strukturering af sportsvideoer efter stokastiske modeller ”, Speciale fra University of Rennes 1, IRISA , december 2003.