Viola–Jones objektdetekteringsramverk

Viola –Jones-objektdetekteringsramverket är ett ramverk för maskininlärning av objektdetektering som föreslogs 2001 av Paul Viola och Michael Jones . Det motiverades främst av problemet med ansiktsdetektering , även om det kan anpassas till detektering av andra objektklasser.

Algoritmen är effektiv för sin tid och kan upptäcka ansikten i bilder på 384 gånger 288 pixlar med 15 bilder per sekund på en konventionell 700 MHz Intel Pentium III . Den är också robust och uppnår hög precision och återkallelse .

Även om den har lägre noggrannhet än mer moderna metoder som faltningsneurala nätverk , betyder dess effektivitet och kompakta storlek (endast runt 50k parametrar, jämfört med miljontals parametrar för typiska CNN som DeepFace ) att den fortfarande används i fall med begränsad beräkningskraft. Till exempel, i originaltidningen, rapporterade de att denna ansiktsdetektor kunde köras på Compaq iPAQ med 2 fps (denna enhet har en StrongARM med låg effekt utan flyttals-hårdvara).

Problembeskrivning

Ansiktsdetektering är ett binärt klassificeringsproblem kombinerat med ett lokaliseringsproblem: givet en bild, bestäm om den innehåller ansikten och konstruera gränsrutor för ansikten.

För att göra uppgiften mer hanterbar upptäcker Viola–Jones-algoritmen endast full sikt (ingen ocklusion), frontal (ingen huvudvändning), upprätt (ingen rotation), väl upplysta, fullstora (upptar större delen av ramen) ansikten i bilder med fast upplösning.

Restriktionerna är inte så stränga som de verkar, eftersom man kan normalisera bilden för att föra den närmare kraven för Viola-Jones.

vilken bild som helst kan skalas till en fast upplösning
för en allmän bild med ett ansikte av okänd storlek och orientering kan man utföra klumpdetektering för att upptäcka potentiella ansikten, sedan skala och rotera dem till upprätt läge i full storlek.
bildens ljusstyrka kan korrigeras genom vitbalansering .
begränsningsrutorna kan hittas genom att skjuta ett fönster över hela bilden och markera varje fönster som innehåller ett ansikte.
- Detta skulle i allmänhet detektera samma ansikte flera gånger, för vilka dupliceringsborttagningsmetoder, såsom icke-maximal undertryckning, kan användas.

Kravet på "frontal" är icke förhandlingsbart, eftersom det inte finns någon enkel transformation på bilden som kan vända ett ansikte från en sidovy till en frontvy. Däremot kan man träna flera Viola-Jones-klassificerare, en för varje vinkel: en för frontvy, en för 3/4-vy, en för profilvy, några fler för vinklarna däremellan. Sedan kan man under körning exekvera alla dessa klassificerare parallellt för att upptäcka ansikten i olika synvinklar.

Kravet på "full-view" är inte heller förhandlingsbart, och kan inte enkelt hanteras genom att träna fler Viola-Jones-klassificerare, eftersom det finns för många möjliga sätt att blockera ett ansikte.

Komponenter i ramverket

En fullständig presentation av algoritmen finns i.

Betrakta en bild $I(x,y)$ med fast upplösning $(M,N)$ . Vår uppgift är att fatta ett binärt beslut: om det är ett foto av ett standardiserat ansikte (frontalt, väl upplyst, etc) eller inte.

Viola–Jones är i huvudsak en förstärkt funktionsinlärningsalgoritm , tränad genom att köra en modifierad AdaBoost -algoritm på Haar-funktionsklassificerare för att hitta en sekvens av klassificerare $f_{1},f_{2},...,f_{k}$ . Haar-funktionsklassificerare är grova, men tillåter mycket snabb beräkning, och den modifierade AdaBoost konstruerar en stark klassificerare av många svaga.

Vid körning testas en given bild ${\displaystyle I} på$ $f_{1}(I),f_{2}(I),...f_{k}(I)$ sekventiellt. Om vid någon punkt, $f_{i}(I)=0$ , returnerar algoritmen omedelbart "inget ansikte upptäckt". Om alla klassificerare returnerar 1, returnerar algoritmen "ansikte upptäckt". Av denna anledning kallas Viola-Jones-klassificeraren även "Haar cascade classifier".

Haar har klassificerare

Betrakta en perceptron $f_{w,b}$ definierad av två variabler $w(x,y),b$ . Den tar in en bild $I(x,y)$ med fast upplösning och returnerar

$f_{w,b}(I)={\begin{ fall}1,\quad {\text{if }}\summa _{x,y}w(x,y)I(x,y)+b>0\\0,\quad {\text{else}} \end{cases}}$

Exempel på rektangelfunktioner som visas i förhållande till det omslutande detektionsfönstret

En Haar-funktionsklassificerare är en perceptron $f_{w,b}$ med en mycket speciell sorts $w$ som gör den extremt billig att beräkna. Nämligen, om vi skriver ut matrisen $w(x,y)$ , finner vi att den bara tar tre möjliga värden $\{+1, -1,0\}$ , och om vi färgar matrisen med vitt på $+1$ , svart på $-1$ och transparent på $0$ , är matrisen i ett av de 5 möjliga mönstren som visas till höger.

Varje mönster måste också vara symmetriskt till x-reflektion och y-reflektion (om man ignorerar färgändringen), så till exempel, för den horisontella vit-svarta funktionen, måste de två rektanglarna ha samma bredd. För den vertikala vit-svart-vit-funktionen måste de vita rektanglarna vara av samma höjd, men det finns ingen begränsning på den svarta rektangelns höjd.

Haarfunktion som liknar näsryggen appliceras på ansiktet

Haarfunktion som liknar ögonområdet som är mörkare än de övre kinderna appliceras på ett ansikte

motivering för Haar funktioner

Haar-funktionerna som används i Viola-Jones-algoritmen är en delmängd av de mer allmänna Haar-basfunktionerna , som har använts tidigare inom området bildbaserad objektdetektering.

Även om de är grova jämfört med alternativ som styrbara filter , är Haar-funktionerna tillräckligt komplexa för att matcha egenskaperna hos typiska mänskliga ansikten. Till exempel:

Ögonområdet är mörkare än de övre kinderna.
Näsbryggan är ljusare än ögonen.

Sammansättning av egenskaper som bildar matchande ansiktsdrag:

Placering och storlek: ögon, mun, näsrygg
Värde: orienterade gradienter av pixelintensiteter

Dessutom möjliggör designen av Haar-funktioner effektiv beräkning av $f_{w,b}(I)$ med enbart konstant antal additioner och subtraktioner, oavsett storleken på de rektangulära särdragen, med hjälp av tabellen för summerade arealer .

Att lära sig och använda en Viola-Jones-klassificerare

Välj en upplösning $(M,N)$ för bilderna som ska klassificeras. I originalpapperet rekommenderade de $(M,N)=(24,24)$ .

inlärning

Samla ett träningsset, där vissa innehåller ansikten och andra som inte innehåller ansikten. Utför en viss modifierad AdaBoost-träning på uppsättningen av alla Haar-funktionsklassificerare av dimension ( $\displaystyle (M,N)}$ , tills önskad nivå av precision och återkallelse uppnås. Den modifierade AdaBoost-algoritmen skulle mata ut en sekvens av Haar-funktionsklassificerare $f_{1},f_{2},...,f_{k}$ .

Detaljerna för den modifierade AdaBoost-algoritmen beskrivs nedan.

använder sig av

För att använda en Viola-Jones-klassificerare med $f_{1},f_{2},...,f_{k}$ på en bild $I$ , beräkna $f_{1}(I),f_{2}(I),...f_{k}(I)$ sekventiellt. Om vid någon punkt, $f_{i}(I)=0$ , returnerar algoritmen omedelbart "inget ansikte upptäckt". Om alla klassificerare returnerar 1, returnerar algoritmen "ansikte upptäckt".

Inlärningsalgoritm

Den hastighet med vilken funktioner kan utvärderas kompenserar dock inte tillräckligt för deras antal. Till exempel, i ett standardunderfönster med 24x24 pixlar, finns det totalt $M = 162336$ möjliga funktioner, och det skulle vara oöverkomligt dyrt att utvärdera dem alla när du testar en bild. Således använder ramverket för objektdetektering en variant av inlärningsalgoritmen AdaBoost för att både välja de bästa funktionerna och träna klassificerare som använder dem. Denna algoritm konstruerar en "stark" klassificerare som en linjär kombination av viktade enkla "svaga" klassificerare.

h(\mathbf {x} )=\operatörsnamn {sgn} \left(\sum _{j=1}^ {M}\alpha _{j}h_{j}(\mathbf {x} )\right)

Varje svag klassificerare är en tröskelfunktion baserad på funktionen $f_{j}$ .

h_{j}(\mathbf {x} )={\begin{cases}-s_{j}&{\text{ om }}f_{j}<\theta _{j}\\s_{j}&{\text{annars}}\end{fall}}

Tröskelvärdet $\theta _{j}$ och polariteten $s_{j}\in \pm 1$ bestäms i träningen, liksom koefficienterna $\alpha _{j}$ .

Här rapporteras en förenklad version av inlärningsalgoritmen:

Indata: Uppsättning av $N$ positiva och negativa träningsbilder med deras etiketter ${(\mathbf {x} ^{i},y^{i})}$ . Om bild $i$ är ett ansikte $y^{i}=1$ , om inte $y^{i}=-1$ .

Initialisering: tilldela en vikt $w_{1}^{i}={\frac {1}{N}}$ till varje bild $i$ .
För varje funktion $f_{j}$ $f_{j}$ med $j=1,...,M$ $j=1,...,M$
1. Renormalisera vikterna så att de summeras till ett.
2. Tillämpa funktionen på varje bild i träningsuppsättningen, hitta sedan den optimala tröskeln och polariteten $\theta _{j},s_{j}$ som minimerar det viktade klassificeringsfelet. Det vill säga $\theta _{j},s_{j}=\arg \min _{\theta ,s }\;\summa _{i=1}^{N}w_{j}^{i}\varepsilon _{j}^{i}$ där $\varepsilon _{j}^{i}={\begin{cases}0&{\text{if }}y^{i}=h_{j}(\mathbf { x} ^{i},\theta _{j},s_{j})\\1&{\text{annars}}\end{fall}}$
3. Tilldela en vikt $\alpha _{j}$ till $h_{j}$ som är omvänt proportionell mot felfrekvensen. På detta sätt anses bästa klassificerare mer.
4. Vikterna för nästa iteration, dvs $w_{j+1}^{i}$ , reduceras för bilderna $i$ som klassificerades korrekt.
Ställ in den slutliga klassificeraren till $h(\mathbf {x} )=\operatörsnamn {sgn} \left(\sum _{ j=1}^{M}\alpha _{j}h_{j}(\mathbf {x} )\right)$

Kaskadarkitektur

I genomsnitt är endast 0,01 % av alla underfönster positiva (ansikten)
Lika beräkningstid spenderas på alla underfönster
Måste spendera mest tid bara på potentiellt positiva underfönster.
En enkel klassificerare med två funktioner kan uppnå nästan 100 % detekteringshastighet med 50 % FP-hastighet .
Den klassificeraren kan fungera som ett första lager i en serie för att filtrera bort de flesta negativa fönster
Det andra lagret med 10 funktioner kan hantera "hårdare" negativa fönster som överlevde det första lagret, och så vidare...
En kaskad av gradvis mer komplexa klassificerare uppnår ännu bättre detektionshastigheter. Utvärderingen av de starka klassificerare som genereras av inlärningsprocessen kan göras snabbt, men det är inte tillräckligt snabbt för att köras i realtid. Av denna anledning är de starka klassificerarna arrangerade i en kaskad i komplexitetsordning, där varje successiv klassificerare tränas endast på de utvalda sampel som passerar genom de föregående klassificerarna. Om i något skede i kaskaden en klassificerare avvisar underfönstret under inspektion, utförs ingen ytterligare bearbetning och fortsätt att söka i nästa underfönster. Kaskaden har därför formen av ett degenererat träd. När det gäller ansikten använder den första klassificeraren i kaskaden – kallad uppmärksamhetsoperatorn – endast två funktioner för att uppnå en falsk negativ frekvens på cirka 0 % och en falsk positiv frekvens på 40 %. Effekten av denna enda klassificerare är att minska med ungefär hälften av antalet gånger som hela kaskaden utvärderas.

I cascading består varje steg av en stark klassificerare. Så alla funktioner är grupperade i flera stadier där varje steg har ett visst antal funktioner.

Varje stegs uppgift är att avgöra om ett givet underfönster definitivt inte är ett ansikte eller kan vara ett ansikte. Ett givet underfönster kasseras omedelbart som inte ett ansikte om det misslyckas i något av stegen.

Ett enkelt ramverk för kaskadutbildning ges nedan:

f = den maximala acceptabla falska positiva frekvensen per lager.
d = den lägsta acceptabla detekteringshastigheten per lager.
Ftarget = mål totalt falsk positiv frekvens.
P = uppsättning positiva exempel.
N = uppsättning negativa exempel.

 F(0) = 1,0; D(0) = 1,0;  i = 0   medan  F(i) > Fmålökning  i  n(i) = 0; F(i)= F(i-1)   medan  F(i) > f × F(i-1)  ökar  n(i) använd P och N för att träna en klassificerare med n(i) funktioner med  AdaBoost  Utvärdera aktuell kaskadklassificerare på valideringsuppsättning för att bestämma F(i) och D(i)  minska  tröskeln för den i:te klassificeraren (dvs. hur många svaga klassificerare behöver acceptera för att en stark klassificerare ska acceptera)  tills  den nuvarande kaskadklassificeraren har en detekteringshastighet på minst d × D (i-1) (detta påverkar också F(i)) N = ∅  om  F(i) > Ftarget utvärdera   sedan  den nuvarande kaskadformade detektorn på uppsättningen av icke-ansiktsbilder och lägg eventuella falska upptäckter i uppsättningen N.

Kaskadarkitekturen har intressanta implikationer för de individuella klassificerarnas prestanda. Eftersom aktiveringen av varje klassificerare helt beror på beteendet hos dess föregångare, är den falska positiva frekvensen för en hel kaskad:

F=\prod _{i=1}^{K}f_{i}.

På samma sätt är detektionshastigheten:

D=\prod _{i=1}^{K}d_{i}.

Således, för att matcha de falska positiva frekvenserna som vanligtvis uppnås av andra detektorer, kan varje klassificerare komma undan med förvånansvärt dålig prestanda. Till exempel, för att en 32-stegs kaskad ska uppnå en falsk positiv frekvens på 10 ⁻⁶ , behöver varje klassificerare bara uppnå en falsk positiv frekvens på cirka 65 %. Samtidigt måste dock varje klassificerare vara exceptionellt kapabel om den ska uppnå adekvata detektionshastigheter. Till exempel, för att uppnå en detektionsgrad på cirka 90 %, behöver varje klassificerare i den tidigare nämnda kaskaden uppnå en detektionsgrad på cirka 99,7 %.

Använder Viola–Jones för objektspårning

I videor av rörliga objekt behöver man inte tillämpa objektdetektering på varje bildruta. Istället kan man använda spårningsalgoritmer som KLT-algoritmen för att upptäcka framträdande egenskaper inom detektionsgränsrutorna och spåra deras rörelse mellan bildrutor. Detta förbättrar inte bara spårningshastigheten genom att ta bort behovet av att återupptäcka objekt i varje bildruta, utan det förbättrar också robustheten, eftersom de framträdande egenskaperna är mer motståndskraftiga än Viola-Jones-detektionsramverket mot rotation och fotometriska förändringar.

^ ^a ^b Viola, P.; Jones, M. (2001). "Snabb objektdetektering med hjälp av en förstärkt kaskad av enkla funktioner" . Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 . IEEE Comput. Soc. 1 . doi : 10.1109/cvpr.2001.990517 . ISBN 0-7695-1272-0 . S2CID 2715202 .
^ Viola, Paul; Jones, Michael J. (maj 2004). "Robust ansiktsdetektion i realtid" . International Journal of Computer Vision . 57 (2): 137–154. doi : 10.1023/b:visi.0000013087.49260.fb . ISSN 0920-5691 . S2CID 2796017 .
^ Wang, Yi-Qing (2014-06-26). "En analys av Viola-Jones ansiktsdetektionsalgoritm" . Bildbehandling online . 4 : 128-148. doi : 10.5201/ipol.2014.104 . ISSN 2105-1232 .
^ C. Papageorgiou, M. Oren och T. Poggio. Ett allmänt ramverk för objektdetektering. Internationell konferens om datorseende , 1998
^ "Viola-Jones ansiktsdetektering hävdar 180 000 funktioner" . stackoverflow.com . Hämtad 2017-06-27 .
^ R. Szeliski, Computer Vision, algoritmer och applikationer , Springer
^ Viola, Jones: Robust objektdetektering i realtid, IJCV 2001 Se sidan 11.
^ Torbert, Shane (2016). Tillämpad datavetenskap (2:a uppl.). Springer. s. 122–131.
^ Ansiktsavkänning och spårning med KLT-algoritmen

externa länkar

Bilder som presenterar ramverket
Information om Haar Basisfunktioner
"Utbyggnad av Viola–Jones ramverk med SURF-funktionen" . Arkiverad från originalet 2020-10-18.
"IMMI - Rapidminer Image Mining Extension" . Arkiverad från originalet 2022-07-03. - Verktyg med öppen källkod för bildutvinning
"Robust ansiktsdetektion i realtid" (PDF) . Arkiverad från originalet (PDF) 2019-02-02.
En förbättrad algoritm på Viola-Jones objektdetektor
Citeringar av Viola–Jones-algoritmen i Google Scholar
på YouTube - Adaboost Förklaring från ppt av Qing Chen, Discovery Labs, University of Ottawa och en videoföreläsning av Ramsri Goutham.

Genomföranden

Jensen, Ole Helvig. "Implementera Viola–Jones ansiktsdetektionsalgoritm" (PDF) . Arkiverad från originalet (PDF) 2018-10-21.
MATLAB: [1] , [2]
OpenCV: implementerad som cvHaarDetectObjects() .
- Haar Cascade Detection i OpenCV
- Cascade Classifier Training i OpenCV

[:0-1] Viola, P.; Jones, M. (2001). "Snabb objektdetektering med hjälp av en förstärkt kaskad av enkla funktioner" . Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 . IEEE Comput. Soc. 1 . doi : 10.1109/cvpr.2001.990517 . ISBN 0-7695-1272-0 . S2CID 2715202 .

[Viola_137–154-2] Viola, Paul; Jones, Michael J. (maj 2004). "Robust ansiktsdetektion i realtid" . International Journal of Computer Vision . 57 (2): 137–154. doi : 10.1023/b:visi.0000013087.49260.fb . ISSN 0920-5691 . S2CID 2796017 .

[3] Wang, Yi-Qing (2014-06-26). "En analys av Viola-Jones ansiktsdetektionsalgoritm" . Bildbehandling online . 4 : 128-148. doi : 10.5201/ipol.2014.104 . ISSN 2105-1232 .

[4] C. Papageorgiou, M. Oren och T. Poggio. Ett allmänt ramverk för objektdetektering. Internationell konferens om datorseende , 1998

[5] "Viola-Jones ansiktsdetektering hävdar 180 000 funktioner" . stackoverflow.com . Hämtad 2017-06-27 .

[6] R. Szeliski, Computer Vision, algoritmer och applikationer , Springer

[7] Viola, Jones: Robust objektdetektering i realtid, IJCV 2001 Se sidan 11.

[8] Torbert, Shane (2016). Tillämpad datavetenskap (2:a uppl.). Springer. s. 122–131.

[9] Ansiktsavkänning och spårning med KLT-algoritmen