1. Algoritmi
In questo capitolo verranno presentati gli algoritmi di un sistema di videosorveglianza che sono stati studiati in precedenti lavori svolti presso un laboratorio di Visione Artificiale.
Data una sequenza di immagini, lo scopo di questi algoritmi è quello di riconoscere per ognuna di esse i punti appartenenti a oggetti di interesse della scena ripresa. L'informazione prodotta a questo livello è di tipo binario: l’output generato dai vari algoritmi è costituito da immagini i cui pixel hanno solo due valori (bianco o nero) per indicare se il punto è relativo allo sfondo o a oggetti rilevati.
Gli algoritmi trattati prescindono dalla conoscenza del tipo di applicazione, né tantomeno conoscono le caratteristiche della scena ripresa. Nell’elaborazione vengono ignorate la natura e il numero degli oggetti presenti; qualsiasi fenomeno che produca effetti non eliminabili con filtri per rumore genera inevitabilmente dei “blob” ovvero gruppi di pixel estranei allo sfondo.
Problemi derivati da questa caratteristica tipicamente sono dovuti ad oggetti che cambiano posizione (ad es. una macchina parcheggiata che riprende a muoversi) o di cui si perde ogni interesse (per es., in una applicazione di sorveglianza del traffico, una macchina parcheggiata da lungo tempo).
Per comprendere meglio il funzionamento dei vari algoritmi che si vogliono confrontare è necessario individuare e descrivere le categorie principali in cui sono stati suddivisi.
Questa prima classificazione è fatta in base alle caratteristiche teoriche. In particolare è preso in considerazione il metodo usato per individuare gli oggetti.
Una prima suddivisione è la seguente:
· Algoritmi basati su differenze fra frame.
· Algoritmi basati sul confronto con un “background”.
Per ognuna saranno elencati i problemi specifici che quella classe di algoritmi affronta con successo e quelli che invece non si riesce a risolvere, mettendo così alla luce i limiti del suo campo d’azione.
2. Algoritmi derivativi
La prima classi di algoritmi che esamineremo è quella degli algoritmi basati su differenze tra frame. Caratteristica principale di questa classe è quella di individuare gli oggetti in movimento in una sequenza video prendendo in considerazione solo le differenze presenti tra immagini successive.
Quindi l’output degli algoritmi presenti in questa categoria evidenzia degli oggetti soltanto in corrispondenza dei pixel che presentano nelle varie immagini delle differenze di intensità apprezzabili. Le possibili implementazioni si differenziano l’una dall’altra in base al numero di immagini consecutive considerate nelle elaborazioni.
In particolare sono state analizzate due soluzioni, Single Difference e Double Difference, che utilizzano per l’individuazione di oggetti rispettivamente le ultime due e le ultime tre immagini della sequenza video.
L’output di questi algoritmi è caratterizzato dal fatto di essere dipendente dalla velocità di movimento degli oggetti ripresi nella scena. Maggiore è la velocità di spostamento, maggiori saranno le differenze tra immagini consecutive e quindi più evidente sarà l’output finale. Viceversa movimenti lenti introdurranno piccole variazioni, riducendo la qualità dell’elaborazione finale. Come conseguenza, oggetti che compaiono nella scena e poi si fermano cessano di essere individuati da questa classe di algoritmi. Quindi eventuali operazioni di inseguimento (tracking) devono essere gestite da algoritmi di alto livello che devono sempre tenere traccia della posizione dell’oggetto anche nel caso questo si fermi.
Una seconda carenza di questa classe è il cosiddetto problema di “foreground aperture”: la corretta individuazione della sagoma di un oggetto può essere compromessa se questo presenta delle zone a tinta uniforme che non producono cambiamenti in immagini successive.
Un pregio notevole di questi algoritmi è rappresentato dalla loro sostanziale insensibilità a variazioni luminose dell’ambiente. Questo è vero fin tanto che le variazioni delle intensità dei pixel restano al di sotto della soglia di riconoscimento. Inoltre anche cambiamenti istantanei delle condizioni di illuminazione (ad es. una lampada che viene accesa all’interno di una stanza) mandano in crisi l’elaborazione solo per pochi frame, fintanto che la situazione non si stabilizza. (ad es. si pensi al transitorio nell’accensione di una luce al neon).
Tutti e due gli algoritmi presentano pregi legati al ridotto carico computazionale garantito dalla semplicità delle operazioni da eseguire.
3. Algoritmi con Background
Nella seconda categoria di algoritmi, l’individuazione degli oggetti si basa sul confronto tra l’immagine corrente di una sequenza e un background di riferimento che contiene informazioni sulla scena in assenza di oggetti di interesse. Rispetto agli algoritmi visti in precedenza, questo tipo di approccio risulta più intuitivo e naturale; l’occhio umano infatti cerca nella sequenza di immagini oggetti estranei avendo come riferimento la scena vuota. Storicamente questo è il tipo di approccio più usato dai sistemi di videosorveglianza.
Punto di forza di questa classe rispetto alla precedente è che la qualità dell’output non dipende più dalla velocità di movimento dell’oggetto e, in particolare, l’individuazione è garantita anche nel caso in cui questo diventi stazionario.
Questa caratteristica permette una facilitazione per quanto riguarda un eventuale modulo di inseguimento (tracking) in un sistema di videosorveglianza. Rispetto agli algoritmi basati su differenze fra frame, questa classe non presenta più il problema del foreground aperture: oggetti di colore uniforme vengono individuati correttamente. Più in generale si ha sempre la possibilità di individuare la sagoma di un oggetto di interesse priva di lacune, eccetto nel caso che questo non abbia caratteristiche tali da essere confuso con il background. In letteratura questo fenomeno è noto con il nome di mimetizzazione (o camouflage).
La presenza di un background di riferimento rende dipendenti dalle variazioni globali della scena gli algoritmi basati sulle differenze. Ad esempio si perde robustezza nei confronti delle variazioni di illuminazione. Infatti il background “fotografa” la scena in un certo momento: se avvengono cambiamenti che modificano le condizioni iniziali, allora i dati di riferimento relativi alla scena “fotografata” non sono più validi. Quindi nasce la necessità di mantenere corretti i dati contenuti nel background di riferimento nel corso dell’evoluzione della scena ripresa mediante opportune tecniche di aggiornamento.
Dalle considerazioni appena fatte deriva un aumento della complessità degli algoritmi in quanto, oltre alla detection, si ha la necessità di mantenere un background aggiornato rispetto alle variazioni della scena. Per rendere più facile l’analisi, si è cercato di procedere nella descrizione degli algoritmi operando delle semplificazioni; in particolare si è cercato di dividere, dove possibile, l’algoritmo in moduli più semplici da analizzare e comprendere.
Da un’analisi degli algoritmi presenti in letteratura e di quelli presentati in questo lavoro, ci si accorge che questa classe si presta molto bene ad una semplificazione di questo tipo. Infatti tutti gli algoritmi sono costituiti da due moduli distinti, che lavorano l’uno a partire dai risultati dell’altro.
Questi moduli sono :
· Modulo di detection.
· Modulo di aggiornamento del background
Il primo si occupa di estrarre oggetti di interesse dall’immagine corrente mediante un confronto con il background di riferimento. Il secondo si occupa dell’aggiornamento dei dati contenuti nel background a partire dall’output generato dal precedente. L’algoritmo risulta così costituito da due blocchi in retroazione che lavorano separatamente, l’uno a partire dal risultato dell’altro.
Tanto più il riferimento sarà fedele allo stato attuale della scena senza oggetti, tanto più l’output sarà di migliore qualità. Allo stesso modo quanto migliore è la detection, tanto più l’aggiornamento potrà essere effettuato in maniera efficace.
Analizzando i diversi tipi di soluzioni per i moduli di detection sono state individuate due categorie principali di approcci:
· Algoritmi di detection statistici.
· Algoritmi di detection con immagine di riferimento.
4. Algoritmi di detection statistici
La prima sottoclasse è costituita da algoritmi che sono in grado di generare una statistica per ogni pixel in modo da conoscere la dinamica della scena.
Infatti i pixel appartenenti allo sfondo non sono costanti, ma sono soggetti a fluttuazioni continue.
Questi algoritmi in una prima fase, detta training, analizzano la scena in assenza di oggetti estranei al fine di stimare qualsiasi fenomeno di “rumore motorio”, cioè di tutti quei fenomeni di moto apprezzabili che non hanno alcun interesse ai fini della videosorveglianza.
In questo modo verrà costruito un modello del background costituito da un insieme di parametri statistici non rappresentabili visivamente. In fase di rilevamento verranno considerati “punti di moto” soltanto i pixel i cui valori non ricadono nella statistica del background.
5.Algoritmi di detection con immagine di riferimento.
La seconda sottoclasse di algoritmi usa un riferimento costituito da un’immagine che rappresenta la scena ripresa senza oggetti. L’individuazione è fatta valutando la somiglianza tra l’immagine corrente e quella nel background di riferimento.
Le tecniche di confronto che possono essere applicate sono diverse: si possono confrontare i valori dei singoli pixel, può essere valutata la somiglianza tra blocchi corrispondenti nelle due immagini, oppure la classificazione di un pixel può essere fatta esaminando il suo intorno.
Ogni tecnica presenta dei vantaggi particolari e degli effetti indesiderati
Comunque, in generale, questi algoritmi risultano più vulnerabili a fenomeni di instabilità dello sfondo (waveing trees) rispetto a quelli statistici, in quanto il confronto viene effettuato allo stesso modo su tutta l’immagine impostando un unico parametro, o al più un insieme di parametri, rendendo quindi impossibile l’adattamento a zone particolarmente rumorose della scena ripresa. In ognuno di essi si tratterà di trovare il migliore compromesso tra sensibilità e soppressione del rumore motorio.
Vi sono poi tecniche che possono offrire dei vantaggi per quanto riguarda le variazioni di illuminazione. La risoluzione di questo problema, trattandosi di una variazione globale della scena, sarebbe di competenza del modulo di manutenzione del background, tuttavia una buona detection, particolarmente tollerante a sbalzi di luminosità, può facilitare il corretto aggiornamento dello sfondo.
Tra gli algoritmi con immagine di riferimento che sono stati esaminati vi è l’Absolute Difference.
6. Absolute Difference
In base ai test e alle valutazioni svolte in questi studi, l’algoritmo che ha prestazioni migliori per questa applicazione risulta essere l’Absolute Difference.
Questo giudizio è stato confermato nella fase di sviluppo del sistema di tracking quando è diventato chiaro quali, tra i pregi e i difetti dei vari algoritmi, risultano essere più importanti nell’interpretazione della scena.
Daremo quindi ora una breve descrizione di questo algoritmo, in quanto esiste e andrebbe sfruttata la possibilità di effettuare una retroazione del sistema di interpretazione sul modulo di detection.
Questo algoritmo di detection rappresenta l’implementazione più semplice che si possa fare di un confronto con un’immagine di riferimento.
L’elaborazione infatti sfrutta l’idea più immediata che consiste in un confronto tra le intensità dei pixel corrispondenti nell’immagine corrente e in quella del background. Se tale differenza è in valore assoluto sufficientemente elevata allora il punto viene riconosciuto come appartenente al foreground.
La soglia di discriminazione dei pixel va necessariamente impostata dall’utente a seconda del tipo di applicazione e della scena ripresa, o dal sistema di interpretazione a seconda del rumore che si presenta in un dato momento. Una soglia bassa garantisce un’alta sensibilità ed è adatta ad immagini poco rumorose. Mentre in riprese esterne caratterizzate da disturbi elevati, per esempio dovuti al rumore motorio già esaminato in precedenza (alberi o cavi elettrici che si muovono con il vento) la soglia va impostata ad un valore maggiore.
Comunque in tutti i casi si tratta di trovare il giusto compromesso tra il numero di pixel falsi negativi (sensibilità algoritmo) e di falsi positivi (quantità di rumore).
A questo punto un miglioramento della qualità dell’output si otterrebbe “filtrando” i pixel isolati dovuti al rumore per poi “amalgamare” i punti relativi ad oggetti. Questo effetto si ottiene operando prima un blurring dell’output, che ha l’effetto di sfumare l’immagine e di fatto si traduce nel sostituire ogni pixel con il valore medio dei valori dei pixel nelle vicinanze, infine si attua una sogliatura per binarizzare nuovamente l’output. Questa operazione introduce altri due parametri, il primo specifica le dimensioni dell’intorno sul quale calcolare la media, il secondo è una soglia di discriminazione come quella già vista in precedenza. Più grande è il primo parametro più viene accentuato il filtraggio e l’accorpamento dei punti.
Per quello che riguarda l’algoritmo di mantenimento del background la scelta è caduta sull’aggiornamento a 2 pesi nel quale si sfrutta l’informazione che si ha sul valore semantico (oggetto o sfondo) di ciascun pixel della scena; a questo livello, in corrispondenza di oggetti di interesse, l’aggiornamento del background viene tenuto “lento” per evitare di includere informazioni errate nel riferimento, viceversa negli altri punti viene effettuato “velocemente” per garantire un aggiornamento fedele in presenza di variazioni nella scena.
L’aggiornamento di un background costituito da un’immagine viene effettuato con una media pesata tra il valore precedente di un pixel del background (PixelBackgroundn) e quello del corrispondente nell’immagine corrente > Immaginen:PixelBackground (x y) PixelBackground (x y) PesoAgg(x y) Immagine (x y) PesoAgg(x y)
Il peso di aggiornamento varia a seconda che il punto in questione appartenga o no ad un oggetto di interesse. Purtroppo l’aggiornamento a due pesi presenta qualche inconveniente.
Per come è concepito, questo algoritmo aggiorna in maniera molto lenta le informazioni nelle aree di background momentaneamente coperte da un oggetto e, d’altra parte, non sarebbe possibile fare altrimenti proprio perché il background è nascosto dall’oggetto. In questo modo, se è in atto una variazione del background (per es. dovuta ad un cambio di illuminazione) mentre un oggetto è presente nella scena, le zone mascherate da quest’ultimo manterranno inevitabilmente i valori precedenti la loro copertura.
Nel caso l’oggetto riprendesse a muoversi rivelerebbe di nuovo lo sfondo che, a causa del mancato aggiornamento, potrebbe presentare differenze tali da mancare l’individuazione di oggetti inesistenti (falsi positivi).
Questo errore poi continua a venire visualizzato fintanto che l’aggiornamento lento che caratterizza i punti oggetto non riesce a ripristinare la correttezza del background.
