Teknomo–Fernandez algoritm

TF-algoritmen producerar bakgrundsbilden från en video av en gata med många fotgängare som korsar.

Teknomo –Fernandez-algoritmen (TF-algoritmen) är en effektiv algoritm för att generera bakgrundsbilden för en given videosekvens.

Genom att anta att bakgrundsbilden visas i större delen av videon kan algoritmen generera en bra bakgrundsbild av en video i $O(R)$ -tid med endast ett litet antal binära operationer och Boolean Bit-operationer, som kräver en liten mängd minne och har inbyggda operatorer som finns i många programmeringsspråk som C , C++ och Java .

Historia

TF-algoritmen genererar den färgade bakgrundsbilden och använder den för bakgrundssubtraktion.

Människor som spårar från videor involverar vanligtvis någon form av bakgrundssubtraktion för att segmentera förgrunden från bakgrunden. När förgrundsbilder har extraherats kan önskade algoritmer (som de för rörelsespårning , objektspårning och ansiktsigenkänning ) exekveras med dessa bilder.

Bakgrundssubtraktion kräver dock att bakgrundsbilden redan är tillgänglig och tyvärr är det inte alltid så. Traditionellt söks bakgrundsbilden manuellt eller automatiskt från videobilderna när det inte finns några objekt. På senare tid har automatisk bakgrundsgenerering genom objektdetektering , mediall filtrering, medoidfiltrering, approximerad medianfiltrering, linjärt prediktivt filter, icke-parametrisk modell , Kalman-filter och adaptiv utjämning föreslagits; de flesta av dessa metoder har dock hög beräkningskomplexitet och är resurskrävande.

Teknomo–Fernandez-algoritmen är också en automatisk bakgrundsgenereringsalgoritm. Dess fördel är emellertid dess beräkningshastighet på endast $O(R)$ -tid, beroende på upplösningen $R$ för en bild och dess noggrannhet som uppnås inom ett hanterbart antal bildrutor. Endast minst tre bildrutor från en video behövs för att producera bakgrundsbilden, förutsatt att för varje pixelposition förekommer bakgrunden i majoriteten av videorna. Dessutom kan den utföras för både gråskala och färgade videor.

Antaganden

Kameran är stillastående.
Omgivningens ljus förändras bara långsamt i förhållande till rörelserna hos personerna i scenen.
Antalet personer upptar inte scenen för det mesta av tiden på samma plats.

Generellt sett kommer dock algoritmen säkert att fungera närhelst följande viktiga antagande gäller:

För varje pixelposition innehåller majoriteten av pixelvärdena i hela videon pixelvärdet för den faktiska bakgrundsbilden (vid den positionen).

Så länge varje del av bakgrunden visas i större delen av videon, behöver inte hela bakgrundsbilden visas i någon av dess ramar. Algoritmen förväntas fungera korrekt.

Generering av bakgrundsbild

Ekvationer

För tre bildrutor av bildsekvens $x_{1}$ , $x_{2}$ och $x_{3}$ är bakgrundsbilden $B$ erhålls med $B=x_{3}(x_{1}\oplus x_{2})+x_{1}x_{2}$
Den booleska funktionen $S$ i tabellen inträffar när antalet 1 poster är större än hälften av antalet bilder så att $S={\begin{cases}1,&{\text{if }}\sum _{i=1}^{n}x_{i}\geq \left\ lceil {\frac {n}{2}}+1\right\rceil ,{\text{ och }}n\geq 3\\0,&{\text{annars}}\end{cases}}$
För tre bilder kan bakgrundsbilden $B$ tas som värde

{\bar {x}}_{1}x_{2}x_{ 3}+x_{1}{\bar {x}}_{2}x_{3}+x_{1}x_{2}{\bar {x}}_{3}+x_{1}x_{2 }x_{3}

Algoritm för bakgrundsgenerering

På den första nivån väljs tre ramar slumpmässigt från bildsekvensen för att skapa en bakgrundsbild genom att kombinera dem med den första ekvationen. Detta ger en bättre bakgrundsbild på den andra nivån. Proceduren upprepas tills önskad nivå $L$ .

Teoretisk noggrannhet

På nivå ${\displaystyle \ell } representeras$ sannolikheten $p_{\ell }$ att den modala biten som förutspås är den faktiska modalbiten representeras av ekvationen $p_{\ell }=(p_{\ell -1})^{3}+3(p_{\ell -1})^{ 2}(1-p_{\ell -1})$ . Tabellen nedan visar de beräknade sannolikhetsvärdena över flera nivåer med hjälp av några specifika initiala sannolikheter. Det kan observeras att även om den modala biten vid den betraktade positionen är vid låga 60 % av ramarna, är sannolikheten för noggrann modal bitbestämning redan mer än 99 % vid 6 nivåer.

Den här tabellen ger de beräknade sannolikhetsvärdena över flera nivåer med hjälp av några specifika initiala sannolikheter. Det kan observeras att även om den modala biten vid den betraktade positionen är vid låga 60 % av ramarna, är sannolikheten för noggrann modal bitbestämning redan mer än 99 % på sex nivåer.

Rymdkomplexitet

Utrymmeskravet för Teknomo–Fernandez-algoritmen ges av funktionen ${\displaystyle O(RF+R3^{L})} ,$ beroende på upplösningen $R$ för bild, antalet $F$ bildrutor i videon och det önskade antalet $L$ nivåer. Det faktum att $L$ troligen inte kommer att överstiga 6 reducerar dock rymdkomplexiteten till ${\displaystyle O(RF)$ .

Tidskomplexitet

Hela algoritmen körs i $O(R)$ -tid, endast beroende på bildens upplösning. Beräkning av den modala biten för varje bit kan göras i $O(1)$ -tid medan beräkningen av den resulterande bilden från de tre givna bilderna kan göras i $O( R)$ -tid. Antalet bilder som ska bearbetas i $L$ -nivåer är $O(3^{L})$ . Men eftersom $L\leq 6$ så är detta faktiskt $O(1)$ , alltså körs algoritmen i $O(R)$ .

Varianter

En variant av Teknomo–Fernandez-algoritmen som innehåller Monte-Carlo-metoden med namnet CRF har utvecklats. Två olika konfigurationer av CRF implementerades: CRF9,2 och CRF81,1. Experiment på några färgade videosekvenser visade att CRF-konfigurationerna överträffar TF-algoritmen när det gäller noggrannhet. Emellertid förblir TF-algoritmen mer effektiv när det gäller behandlingstid.

Ansökningar

Vidare läsning

Chu, Varian Sherwin B. (2013). Bakgrundsbildrekonstruktion med slumpmässig ramsampling och logiska bitoperationer ( avhandling). Ateneo de Manila University.
Abu, Patricia Angela R. (2015). Förbättring av Teknomo-Fernandez Bakgrundsbildsmodelleringsalgoritm för förgrundssegmentering ( avhandling). Ateneo de Manila University.

externa länkar

Bakgrundsbildsgenerering med booleska operationer – beskriver TF-algoritmen, dess antaganden, processer, noggrannhet, tid och rumskomplexitet och exempelresultat.
En Monte-Carlo-baserad algoritm för bakgrundsgenerering – en variant av Teknomo–Fernandez-algoritmen som innehåller Monte-Carlo-metoden utvecklades i denna studie.