Algoritmo di Viola – Jones

L’algoritmo di Viola – Jones è in grado di elaborare immagini in modo molto veloce, ottenendo al tempo stesso un’alta percentuale di successi. I principali contributi di questo algoritmo sono tre:

• Introduzione di un nuovo modo di rappresentare l’immagine, chiamato “Immagine Integrale”, che consente di calcolare in modo estremamente rapido le feature utilizzate dal detector.

• Introduzione di un algoritmo di apprendimento basato su AdaBoost (19), che seleziona un piccolo numero di feature “critiche” ottenendo un classificatore molto efficiente. • Introduzione di un metodo per comporre in cascata questi classificatori, consentendo di

scartare quasi subito regioni dell’immagine appartenenti allo sfondo e di spendere invece più tempo di elaborazione nelle regioni più promettenti.

4.1.1 Estrazione delle feature

L’algoritmo di detection di Viola – Jones classifica le immagini basandosi sul valore di alcune semplici feature. I principali vantaggi derivanti dall’utilizzo delle feature piuttosto che dei singoli pixel sono il fatto che le prime consentono di codificare conoscenze specifiche del dominio di ricerca che sarebbero altrimenti difficili da apprendere attraverso un training set finito; inoltre un sistema basato sulle feature è molto più veloce di un sistema che opera sui singoli pixel.

L’algoritmo utilizza tre tipi di feature:

• two – rectangle feature: è la differenza tra la somma dei pixel all’interno di due regioni

rettangolari.

• three – rectangle feature: calcola la somma dei pixel nei due rettangoli esterni,

60

• four – rectangle feature: calcola la differenza tra coppie diagonali di rettangoli.

Le feature appena descritte sono rappresentate in Figura 4.1:

Figura 4.1 - Feature utilizzate dall'algoritmo Viola - Jones: A e B sono esempi di two-rectangle feature, C è un esempio di three-rectangle feature, D è un esempio di four-rectangle feature. (Immagine tratta dall’articolo

ufficiale dell’algoritmo (18))

Le feature rettangolari possono essere calcolate in modo estremamente rapido utilizzando una rappresentazione alternativa dell’immagine chiamata “immagine integrale”. Nello specifico, l’immagine integrale in posizione (x,y) contiene la somma dei pixel sopra e a sinistra del punto (x,y) nell’immagine originale, ovvero:

556, 7  8 56, 7′

ᇲ
,

dove ii(x,y) è l’immagine integrale e i(x,y) è l’immagine originale. La Figura 4.2 esemplifica meglio la corrispondenza tra immagine integrale e immagine originale:

Figura 4.2 - Il valore dell'immagine integrale nel punto (x,y) è la somma di tutti i pixel sopra e sinistra del punto stesso. (Immagine tratta dall’articolo ufficiale dell’algoritmo (18)).

Come esemplificato in Figura 4.3, è importante notare che, utilizzando l’immagine integrale, ogni somma rettangolare può essere calcolata in quattro passi. Poiché le feature utilizzate coinvolgono rettangoli adiacenti, è possibile calcolare una two – rectangle feature in sei passi, una three – rectangle feature in otto passi e una four – rectangle feature in nove passi.

61

Figura 4.3 - La somma dei pixel all'interno del rettangolo D può essere calcolata in quattro passi. Infatti, il valore dell'immagine integrale nel punto 1 è la somma dei pixel del rettangolo A, il valore in posizione 2 è

A+B, in posizione 3 è A+C e in posizione 4 è A+B+C+D. Pertanto D = 4 + 1 – (2 + 3). (Immagine tratta dall’articolo ufficiale dell’algoritmo (18)).

4.1.2 Funzioni di classificazione

Poiché vi sono 45.396 feature associate ad ogni sotto-finestra dell’immagine, sebbene il calcolo della singola feature sia molto rapido, calcolarne l’interno insieme non è computazionalmente fattibile. Lo scopo dell’algoritmo è quindi quello di trovare il minor numero di feature che, combinate insieme, formino un classificatore efficiente.

L’algoritmo utilizza una variante di AdaBoost sia per selezionare le feature che per allenare il classificatore. Nella sua forma originale, AdaBoost unisce tra loro una serie di funzioni di classificazione “deboli” ottenendo un classificatore finale sufficientemente robusto.

In pratica, ciascun singolo classificatore viene ristretto all’insieme delle funzioni di classificazioni che dipendono ciascuna da una singola feature. L’algoritmo “debole” di classificazione è quindi progettato per scegliere la singola feature rettangolare che meglio separa gli esempi positivi dagli esempi negativi. Per ogni feature, il classificatore debole determina la soglia ottimale della funzione di classificazione, per la quale il minor numero di esempi viene classificato in modo errato. Un classificatore debole (hj(x)) consiste quindi in una

feature (fj), una soglia (θj) e un valore di parità (pj) che determina il segno della disuguaglianza:

96  :1 ;< =>6 ? =

0 0@5A<15

dove x è una sotto-finestra dell’immagine.

Nella pratica nessuna feature può eseguire l’attività di classificazione con un basso tasso di errore. Le feature selezionate per prime dall’algoritmo hanno tassi di errore compresi tra 0,1 e 0,3 mentre quelle selezionate al termine di quest’ultimo hanno tassi d’errore compresi tra 0,4 e 0,5.

Viene infine riportato l’algoritmo di apprendimento utilizzato da Viola – Jones:

• Siano date delle immagini di esempio (x1, y1), … , (xn, yn), dove yi = 0, 1 indica,

62 • Si inizializzano i pesi ଵ,௜ = ^ଵ

ଶ௠, ^ଵ

ଶ௟ per ௜= 0, 1 rispettivamente, dove m e l sono

rispettivamente numeri positivi e negativi. • Per t=1, … , T:

1. Si normalizzano i pesi

௧,௜← ௧,௜

∑^௡௝ୀଵ௧,௝

in modo tale che wt sia una distribuzione di probabilità.

2. Per ogni feature j si allena un classificatore che sia limitato ad utilizzare un’unica feature. L’errore viene valutato rispetto a wt, ovvero 1௝= ∑ ௜ ௜2ℎ௝௜ − ௜2.

3. Si sceglie il classificatore, ht, con il minor numero errore εt. 4. Si aggiornano i pesi:

௧ାଵ,௜=௧,௜3௧ ଵି௘೔

dove ei=0 se l’esempio xi è classificato correttamente, ei=1 in caso contrario;

inoltre 3௧= ^ఢ೟

ଵିఢ೟. • Il classificatore robusto finale è

ℎ = 41 5 6 7௧ℎ_௧ ≥¹₂6 7௧ ் ௧ୀଵ ் ௧ୀଵ 0 #89:5/9 dove 7௧ = log ^ଵ ఉ೟. 4.1.3 Cascata di classificatori

Si vuole infine descrivere brevemente l’algoritmo tramite il quale è possibile creare una cascata di classificatori in grado di ottenere ottime performance di rilevamento degli oggetti e nello stesso tempo di diminuire drasticamente il tempo di computazione necessario. L’idea chiave è quella di creare una cascata di classificatori in cui all’inizio siano presenti classificatori semplici che scartino il maggior numero di sotto-finestre, per utilizzare poi classificatori più robusti al fine di limitare al minimo il numero dei falsi positivi. In questo modo si genera un albero decisionale, che viene chiamato “cascata”. Un risultato positivo dal primo classificatore richiede l’esecuzione del secondo classificatore, un risultato positivo dal secondo l’esecuzione del terzo e così via. Un risultato negativo in un qualsiasi punto della cascata provoca l’eliminazione immediata della sotto-finestra.

63

Figura 4.4 - Schema di una cascata per il rilevamento degli oggetti. I classificatori iniziali eliminano gran parte degli esempi negativi richiedendo poco tempo computazionale. (Immagine tratta dall’articolo ufficiale

dell’algoritmo (18)).

La struttura della cascata riflette il fatto che, all’interno della singola immagine, la maggior parte delle sotto-finestre è negativa. Pertanto, lo scopo della cascata è quello di eliminare la maggior parte delle sotto-finestre negative nel più breve tempo possibile.