Natur | Gratis software , algoritme |
---|---|
Navngivet med henvisning til | Paul Viola ( in ) , Michael Jones ( in ) |
Den Viola og Jones metode er en metode til påvisning objekt i et digitalt billede , foreslået af forskere Paul Viola og Michael Jones i 2001. Det er et af de allerførste metoder er i stand til effektivt og i realtid at opdage objekter i et billede. Oprindeligt opfundet til at opdage ansigter , kan det også bruges til at opdage andre typer objekter såsom biler eller fly . Metoden til Viola og Jones har været en af de mest kendte og mest anvendte metoder, især til ansigtsgenkendelse og påvisning af mennesker .
Som en overvåget læringsproces kræver metoden til Viola og Jones fra nogle få hundrede til flere tusinde eksempler på det objekt, der skal detekteres, for at træne en klassificering . Når det er lært, bruges denne klassifikator til at registrere den mulige tilstedeværelse af objektet i et billede ved at gennemse det udtømmende i alle mulige positioner og i alle mulige størrelser.
Anses for at være en af de vigtigste objektdetekteringsmetoder, er metoden til Viola og Jones især kendt for at have introduceret flere begreber, der senere blev taget op af mange forskere inden for computersyn , for eksempel begrebet integralt billede eller klassificeringsmetoden konstrueret som en kaskade af boostede klassifikatorer .
Denne metode drager fordel af en implementering under BSD-licens i OpenCV , et bibliotek, der er meget brugt i computersyn .
Paul Viola og Michael Jones, derpå ansat ved Cambridge Research Laboratory i det amerikanske firma Compaq , offentliggør metoden, der bærer deres navn for første gang den13. juli 2001i det videnskabelige tidsskrift International Journal of Computer Vision (IJCV). De to forfattere offentliggjorde derefter to andre artikler om metoden: en mindre detaljeret version, præsenteret på konferencen om computersyn og mønstergenkendelse (CVPR) idecember 2001 og en revideret version i 2004, stadig i IJCV.
De funktioner ekstraheret ved denne fremgangsmåde er inspireret af værker af Papageorgiou, Oren og Poggio, der stammer fra 1998, der brug funktioner konstrueret af Haar wavelets . Metoden er også inspireret af tidligere arbejde af Paul Viola og Kinh Tieu inden for et andet felt, nemlig billedsøgning efter indhold , ved at tage ideen om funktionsvalg af AdaBoost op . Blandt de mange ansigtsgenkendelse metoder offentliggjort på det tidspunkt, Viola og Jones mener især, at af Rowley- Kanade : på grund af sine gode resultater og hastighed, de tager det som et benchmark for sammenligninger. For ækvivalent ydeevne bemærker Viola og Jones, at detektering ved deres metode er 15 gange hurtigere end Rowley-Kanade-detektoren.
Metoden, der anses for at være en af de mest effektive inden for ansigtsgenkendelse, bliver hurtigt en standard inden for dette felt. Arbejdet fra Viola og Jones er blandt de mest anvendte og citerede af forskere, og der foreslås mange forbedringer. Deres arbejde udvides også til andre typer objekter end ansigter, og metoden bliver således en standard inden for objektdetektering . Metoden anerkendes også som den, der havde mest indflydelse inden for ansigtsgenkendelse i 2000'erne .
Viola and Jones-metoden er en udseende-baseret tilgang, der involverer at gå gennem hele billedet ved at beregne en række funktioner i overlappende rektangulære områder. Det har det særlige ved at bruge meget enkle, men meget talrige egenskaber. En første innovation i metoden er introduktionen af integrerede billeder , som muliggør hurtig beregning af disse egenskaber. En anden vigtig innovation er udvælgelsen af disse egenskaber ved at booste , ved at fortolke karakteristika som klassifikatorer. Endelig foreslår metoden en arkitektur til at kombinere de boostede klassifikatorer i en kaskadeproces, hvilket bringer en nettogevinst i detektionstid.
Metoden, som en overvåget indlæringsmetode , er opdelt i to faser: et trin i indlæring af klassifikatoren baseret på et stort antal positive eksempler (dvs. objekter af interesse, for eksempel ansigter) og negative eksempler og en detektionsfase ved at anvende denne klassifikator til ukendte billeder.
I stedet for at arbejde direkte på pixelværdierne og for at være både mere effektive og hurtigere foreslår Viola og Jones at bruge egenskaber , det vil sige en syntetisk og informativ repræsentation beregnet ud fra pixelværdier. Viola og Jones definerer meget enkle karakteristika, de pseudo-Haar karakteristika , der beregnes af forskellen mellem pixelsummen af to eller flere tilstødende rektangulære områder. Figuren modsat giver eksempler på de egenskaber, der er foreslået af Viola og Jones til 2, 3 eller 4 rektangler, hvor summen af mørke pixels trækkes fra summen af hvide pixels. Deres navn kommer fra deres lighed med Haar-bølgerne , der tidligere blev foreslået som egenskaber af Papageorgiou, og som Viola og Jones blev inspireret af.
For hurtigt og effektivt at beregne disse egenskaber på et billede foreslår forfatterne også en ny metode, som de kalder " integreret billede ". Det er en repræsentation i form af et billede af samme størrelse som det originale billede, som på hvert af dets punkter indeholder summen af pixels placeret over det og til venstre. Mere formelt defineres det integrerede billede ved punktet ud fra billedet ved at:
Takket være denne repræsentation kan en karakteristik, der er dannet af to rektangulære zoner, kun beregnes i 6 adgang til det integrerede billede og derfor i en konstant tid uanset karakteristikkens størrelse.
BeregningKarakteristikkerne beregnes på alle positioner og på alle skalaer i et lille detektionsvindue, typisk 24 × 24 pixels eller 20 × 15 pixels. Et meget stort antal karakteristika pr. Vindue genereres således, Viola og Jones giver eksemplet med et vindue med størrelse 24 × 24, som genererer cirka 160.000 karakteristika.
I detektionsfasen scannes hele billedet ved at flytte detektionsvinduet med en bestemt tonehøjde i vandret og lodret retning (denne tonehøjde er lig med 1 pixel i den oprindelige algoritme). Skalaændringerne foretages ved successivt at ændre størrelsen på detektionsvinduet. Viola og Jones bruger en multiplikationsfaktor på 1,25, indtil vinduet dækker hele billedet.
Endelig og for at være mere robuste over for variationer i belysning normaliseres vinduerne af variansen .
Konsekvensen af disse tekniske valg, især brugen af fulde billeder , er en bemærkelsesværdig gevinst i effektivitet, idet egenskaberne evalueres meget hurtigt uanset størrelsen på vinduet.
Det andet nøgleelement i Viola and Jones-metoden er brugen af en boosting- metode for at vælge de bedste egenskaber. Boosting er et princip, der består i at opbygge en “stærk” klassifikator ud fra en vægtet kombination af “svage” klassifikatorer, dvs. give i gennemsnit en bedre respons end et tilfældigt valg. Viola og Jones tilpasser dette princip ved at sammenligne en egenskab med en svag klassifikator ved at konstruere en svag klassifikator, der kun bruger en egenskab. Indlæringen af den svage klassifikator består derefter i at finde tærskelværdien for karakteristikken, der gør det muligt bedre at adskille de positive eksempler fra de negative eksempler. Klassifikatoren reduceres derefter til et par (karakteristisk, tærskel).
Den anvendte boostingsalgoritme er i praksis en modificeret version af AdaBoost , som bruges både til udvælgelsen og til træning af en "stærk" klassifikator. De anvendte svage klassifikatorer er ofte beslutningstræer . En bemærkelsesværdig sag, der ofte ses, er dybdetræet 1, som reducerer klassificeringsoperationen til en simpel tærskelværdi.
Algoritmen er af den iterative type med et bestemt antal iterationer. Ved hver iteration vælger algoritmen en karakteristik, der føjes til listen over karakteristika valgt ved de tidligere iterationer, og det hele vil bidrage til konstruktionen af den endelige stærke klassifikator. Dette valg udføres ved at træne en svag klassifikator for alle egenskaber og vælge den med den mindste fejl på træningssættet. Algoritmen opretholder også en sandsynlighedsfordeling over træningssættet, revurderet ved hver iteration baseret på klassificeringsresultaterne. Især gives der mere vægt på eksempler, der er vanskelige at klassificere, dvs. dem med stor fejl. Den sidste "stærke" klassifikator bygget af AdaBoost består af den vægtede sum af de valgte klassifikatorer.
Mere formelt betragter vi et sæt billeder og deres tilknyttede etiketter , som f.eks. Hvis billedet er et negativt eksempel, og hvis det er et eksempel på det objekt, der skal detekteres. Den boostende algoritme består af et antal iterationer, og for hver iteration og hver karakteristik bygger vi en svag klassifikator . Ideelt set er målet at få en klassificeringen som netop forudsiger etiketterne for hver prøve, dvs. . I praksis er klassifikatoren ikke perfekt, og fejlen genereret af denne klassifikator er givet af:
,det er de vægte, der er knyttet til hvert eksempel og opdateret ved hver iteration som en funktion af den fejl, der blev opnået i den tidligere iteration. Derefter vælger den iteration, klassifikatoren har den laveste fejl .
Den endelige stærke klassifikator er bygget ved at tærske den vægtede sum af de valgte svage klassifikatorer:
De er koefficienter beregnet ud fra fejlen .
Metoden til Viola og Jones er baseret på en udtømmende søgningstilgang på hele billedet, som tester objektets tilstedeværelse i et vindue i alle positioner og i flere skalaer. Denne tilgang er imidlertid ekstremt dyr med hensyn til beregning. En af nøgleidéerne til metoden til at reducere disse omkostninger ligger i organiseringen af detektionsalgoritmen i en kaskade af klassifikatorer. Anvendes sekventielt, tager disse klassifikatorer beslutning om at acceptere - vinduet indeholder objektet, og eksemplet sendes derefter til den næste klassifikator - eller afviser - vinduet indeholder ikke objektet, og i dette tilfælde er eksemplet bestemt udelukket -. Ideen er, at da langt størstedelen af de testede vinduer er negative (dvs. ikke indeholder objektet), er det fordelagtigt at kunne afvise dem med så få beregninger som muligt. Her er de enkleste klassifikatorer og derfor de hurtigste placeret i starten af kaskaden og afviser meget hurtigt langt størstedelen af negative eksempler. Denne kaskadestruktur kan også fortolkes som et degenereret beslutningstræ , da hver knude kun har en gren.
I praksis består kaskaden af en række trin, hver består af en stærk klassifikator, som AdaBoost lærer . Uddannelsen af klassificeringen af gulvet udføres med eksemplerne, der passerede gulvet ; denne klassifikator skal derfor stå over for et vanskeligere problem: jo højere op etager, jo mere komplekse klassifikatorer.
Valget af antal etager indstilles af brugeren; i deres oprindelige metode bruger Viola og Jones gulve. Brugeren skal også specificere den mindste detektionshastighed og den maksimale falske alarmhastighed , der skal opnås for scenen . Kaskadedetekteringshastigheden gives derefter af:
og den falske alarmrate ved:
I praksis satserne og er de samme for alle etager. Indirekte bestemmer disse hastigheder også antallet af karakteristika, der bruges af stærke klassifikatorer på hver etage: Adaboost-gentagelser fortsætter, indtil den falske alarmhastighed er nået. Svage funktioner / klassifikatorer tilføjes, indtil målraterne er nået, inden de går videre til næste niveau.
For at opnå korrekt detektion og falske alarmhastigheder i slutningen af kaskaden er det nødvendigt, at de stærke klassifikatorer i hvert trin har en god detektionshastighed; på den anden side kan de have en høj falsk alarmrate. Hvis vi tager eksemplet med en 32-trins kaskade for at opnå en endelig ydeevne, og hver stærk klassifikator skal opnå , men har råd (dvs. og ). Hvert tilføjet trin reducerer derfor antallet af falske alarmer, men også detekteringshastigheden.
Flere forskere påpeger, at denne idé om hurtigt at filtrere de enkleste negative eksempler ikke er ny. Det findes i andre metoder i form af heuristik , såsom påvisning af kødfarve eller et præklassificeringstrin.
Læringen udføres på et meget stort sæt positive billeder (det vil sige indeholde objektet) og negativt (ikke indeholdende objektet). Flere tusinde eksempler er normalt nødvendige. Denne læring inkluderer:
Påvisningen påføres et testbillede, hvor det ønskes at detektere tilstedeværelsen og placeringen af et objekt. Her er trinene:
Viola og Jones testede deres algoritme ved hjælp af MIT + CMU ansigter , som bestod af 130 billeder indeholdende 507 frontale ansigter. De præsenterer deres resultat i form af en ROC- kurve ( Receiver Operating Characteristic ), som giver den korrekte detektionshastighed i henhold til det samlede antal falske alarmer på alle billeder af corpus. For eksempel får de en detekteringsfrekvens på 88,8% for 50 falske alarmer.
Viola og Jones sammenligner også udførelsen af deres metode med eksisterende ansigtsdetektorer, især Rowley-Kanades. De finder ud af, at resultaterne generelt er tæt på de andre detektorer, skønt de er lidt lavere end Rowley-Kanade-resultaterne for et lavt antal falske alarmer og lidt højere for et stort antal falske alarmer.
Detektionshastigheden afhænger på sin side direkte af antallet af evaluerede egenskaber og derfor af billedets indhold. På en Pentium III- pc, der kører ved 700 MHz , rapporterer forfatterne en gennemsnitlig behandlingstid på 0,067 sekunder for en billedstørrelse 384 × 288 pixels, svarende til en gennemsnitshastighed på 15 billeder i sekundet, tæt på kravene til videobehandling i tide ægte (dvs. 25 billeder i sekundet). Endelig, baseret på MIT + CMU-ansigter, er deres detektor 15 gange hurtigere end Rowley-Kanade og 600 gange hurtigere end Schneiderman-Kanade, til sammenlignelig detektion og falske alarmhastigheder.
Der er efterfølgende foreslået mange forbedringer, der har til formål at forbedre parametriseringen af metoden eller at afhjælpe et bestemt antal begrænsninger.
En af de første forbedringer blev foretaget af Lienhart og Maydt i 2002. De foreslog at udvide pseudo-Haar-funktionssættet, der blev brugt fra 4 til 14 funktioner. På samme måde introducerer de "skæve" egenskaber (roteret 45 °) samt en metode til at beregne dem baseret på en udvidelse af de integrerede billeder .
Andre typer funktioner er også blevet brugt til at erstatte Haar-funktioner: histogrammer af orienterede gradienter , lokale bitmønstre eller regionskovarians. Forskerne foreslog også at bruge variationer af boostingsalgoritmen , herunder RealBoost , der producerer et reelt vurderet tillidsindeks ud over klassificeringen. Flere værker har således vist RealBoosts overlegenhed over AdaBoost inden for rammerne af Viola og Jones-algoritmen.
Viola og Jones udvidede i 2003 deres system til at omfatte detektering af fodgængere i videoer, herunder bevægelsesinformation ud over information om udseende.
En af metodens begrænsninger er dens manglende robusthed over for rotation og dens vanskeligheder med at lære flere synspunkter af det samme objekt. Især er det vanskeligt at få en klassifikator, der er i stand til at detektere både front- og sideflader. Viola og Jones har foreslået en forbedring, der korrigerer denne defekt, som består i at lære en kaskade dedikeret til hver orientering eller visning og ved at bruge et beslutningstræ under påvisning til at vælge den korrekte kaskade, der skal anvendes. Flere andre forbedringer blev efterfølgende foreslået for at give en løsning på dette problem.
En anden vigtig begrænsning af metoden til Viola og Jones vedrører læringstiden for kaskaden, generelt mellem flere dage og flere ugers beregning, hvilket alvorligt begrænser testmulighederne og valg af parametre.
Et af de største problemer med metoden foreslået af Viola og Jones er, at der ikke er nogen optimal metode til at vælge de forskellige parametre, der styrer algoritmen: antallet af etager, deres rækkefølge eller detektering og falske alarmhastigheder. For hver etage skal vælges ved forsøg og fejl . Der foreslås flere metoder til automatisk at bestemme nogle af disse tærskler.
En kritik af metoden vedrører også tabet af information, der gennemgår, når man går fra et trin til et andet af kaskaden, tab som følge af skæreeffekten af de beslutninger om accept eller afvisning, der er truffet på hvert trin. Nogle forskere foreslår løsningen med at opbevare oplysningerne i den vægtede sum af de svage klassifikatorer, for eksempel " boosting chain " af Xiao. En mere radikal ændring af strukturen foreslås af Bourdev og hans forestilling om fleksibel kaskade, som i det væsentlige består i at eliminere begrebet trin, ved at danne en enkelt stærk klassifikator, derfor en enkelt sum, og ved at gøre det muligt at træffe en beslutning ved hver evaluering. lav klassifikator og overvinde begrænsningen af detekteringshastigheder og falske alarmer.
Metoden til Viola og Jones er i det væsentlige blevet anvendt til ansigtsdetektering og personopdagelse , hovedsageligt på grund af de mange praktiske anvendelser, der tilbydes af disse to områder, herunder CCTV , indeksering af billeder og video eller mand-maskine-grænseflader multimodale. Et eksempel på en generel offentlig anvendelse af metoden gives af digitale kameraer , hvor den bruges til at udføre automatisk fokusering på ansigter. Kombineret med JPEG 2000- standarden kan metoden også bruges til at komprimere ansigter med en lavere kompressionshastighed end resten af billedet for at bevare ansigtsdetaljer. De bilproducenter er også interesseret i den metode til at designe sikkerhedssystemer, der automatisk registrerer andre trafikanter, især fodgængere. Forskning har også vist, at effektiviteten af metoden ikke er begrænset til det synlige domæne , men også strækker sig til det infrarøde domæne .
Metoden til Viola og Jones er også blevet brugt til at detektere andre typer objekter, for eksempel hænder , til gestural kontrol af et menneske-maskine-interface , biler i satellitbilleder til oprettelse af systemer med geografisk information uden visuel tilstedeværelse af biler eller til evaluering og overvågning af vejtrafikken.
Metoden er også blevet evalueret til påvisning af fly i billeder med lav opløsning fra et indbygget kamera i et luftfartøj for at undgå kollision. Militære applikationer findes også til påvisning af mål (tanke, fly) i luft- eller satellitbilleder.
Der er mange implementeringer af Viola og Jones detektoren, den mest anvendte er den i C ++, der findes i computersynsbiblioteket OpenCV , frigivet under BSD-licensen . Implementeringer er udviklet til bestemte miljøer eller platforme, især til udførelse i webbrowsere ved hjælp af Flash- multimediesoftware ActionScript- script- sprog . Hardwareimplementeringer er også blevet udviklet på ASIC , FPGA og GPU . Brugen af sidstnævntes parallelle arkitektur muliggør en klar besparelse af detektionstid sammenlignet med den traditionelle OpenCV-implementering.
Endelig er de mest almindelige implementeringer dem, der findes i digitale kameraer til autofokus ved ansigtsgenkendelse. De kræver specielle optimeringer for at klare den lave computerkraft for denne type hardware.
(en) Richard Szeliski, Computer Vision: Algorithms and Applications , Springer ,2010