Feature di colore e di tessitura

1. Feature invarianti: il dilemma progettuale

Con il termine feature invarianti si denotano caratteristiche estratte dai pattern che siano costanti (il più possibile) rispetto alle possibili variazioni intra-classe. Due semplici feature invarianti rispetto a trasformazioni affini sono l'area e il perimetro di un oggetto.

Uno dei maggiori dilemmi nelle applicazioni di PR è se l'invarianza dei pattern debba essere gestita a livello di feature (attraverso la scelta e l'estrazione di feature invarianti) oppure a livello di classificazione (attraverso la scelta e il progetto di metodi in grado di sopportare feature non invarianti).

Feature invarianti        →   Classificazione triviale
Feature non invarianti    →   Classificazione più complessa

Nessuno dei due metodi è preferibile in assoluto, e molto spesso gli approcci scelti sono ibridi: gestiscono l'invarianza a livello di feature solo per alcuni tipi di variabilità. Due considerazioni guidano la scelta:

• se l'invarianza è gestita a livello di feature, la classificazione è molto più veloce. Questo può far propendere per tale soluzione nel caso, per esempio, di riconoscimento rispetto a un elevato numero di classi (identificazione di un individuo su un database di un milione di persone);
• d'altro canto, gestire l'invarianza a livello di feature è spesso più difficile, e i metodi che utilizzano classificatori robusti con feature non invarianti forniscono maggiore accuratezza e affidabilità.

Le applicazioni tipiche delle feature invarianti mostrate a lezione sono tre: ricerche di similarità, classificazione e localizzazione.

2. Hand-crafted features e representation learning

Le tecniche basate su deep learning cercano di apprendere rappresentazioni gerarchiche significative automaticamente, attraverso un processo di apprendimento costituito da più livelli: low-level features → mid-level features → high-level features → classificatore → output. Ogni livello opera una sorta di trasformazione non lineare di feature, i cui parametri possono essere appresi automaticamente. Il riferimento classico per la visualizzazione di queste feature è il lavoro di Zeiler e Fergus (2013) su una rete convoluzionale addestrata su ImageNet.

La gerarchia ha un'interpretazione semantica sorprendentemente uniforme tra domini diversi:

riconoscimento di immagini:  pixel → edge → texton → motif → part → object
riconoscimento di testi:     character → word → word group → clause → sentence → story

Quale approccio scegliere?

Non esiste una tecnica universalmente migliore dell'altra; applicazioni diverse richiedono tecniche diverse.

I capitoli 4-8 percorrono la prima colonna, i capitoli 9-12 la seconda.

3. Color histograms

Un color histogram è una rappresentazione della distribuzione dei colori in un'immagine. Nel caso di immagini digitali l'istogramma si ottiene:

1. quantizzando ciascun canale dello spazio colore in un numero prefissato di bin;
2. contando quanti sono i pixel dell'immagine che presentano un determinato colore.

Se indichiamo con b_i il numero di bin in cui è stato discretizzato il canale i dello spazio colore (RGB o altro), il numero totale di bin dell'istogramma 3D è il prodotto:

N = Π b_i        (istogramma 3D, congiunto)
    i

La scelta del numero di bin deve essere valutata attentamente, perché influenza notevolmente le prestazioni sia in termini di efficacia (ciascun bin dovrebbe contenere colori effettivamente simili) sia in termini di efficienza (aumentando il numero di bin aumenta la complessità computazionale).

Istogramma 3D o tre istogrammi 1D?

Con 16 bin per canale, per esempio, la differenza è tra 16³ = 4096 bin e 16·3 = 48 bin: due ordini di grandezza.

4. Metriche di similarità tra istogrammi

Ai fini del confronto tra immagini sulla base degli istogrammi colore è necessario definire una metrica che ne esprima la similarità (o dissimilarità). Le due più usate viste a lezione:

Correlazione (similarità)

              Σ_I ( H₁(I) − H̄₁ ) · ( H₂(I) − H̄₂ )
d(H₁, H₂) = ───────────────────────────────────────────
            sqrt( Σ_I (H₁(I) − H̄₁)² · Σ_I (H₂(I) − H̄₂)² )

dove   H̄_k = (1/N) · Σ_J H_k(J)

È il coefficiente di correlazione tra i due vettori-istogramma: vale 1 per istogrammi identici e decresce al divergere delle distribuzioni.

Intersezione (similarità)

d(H₁, H₂) = Σ_I  min( H₁(I), H₂(I) )

Somma, bin per bin, il minimo tra i due conteggi: misura letteralmente "quanti pixel i due istogrammi hanno in comune". Con istogrammi normalizzati vale 1 per istogrammi identici e 0 per istogrammi con supporti disgiunti.

5. Color moments

I color moments sono descrittori del colore molto utilizzati per la loro semplicità ed efficacia. Si basano sull'assunzione che la distribuzione dei colori in un'immagine possa essere interpretata come una distribuzione di probabilità, caratterizzata da un certo numero di momenti che possono essere sfruttati per descrivere l'immagine stessa.

Data un'immagine I di N pixel, definiamo p_ij il canale i del pixel j. I tre momenti più utilizzati sono:

              N
Media:   E_i = Σ (1/N) · p_ij                     colore medio nell'immagine
             j=1

                        N
Dev. std: σ_i = sqrt( (1/N) · Σ (p_ij − E_i)² )   radice della varianza
                       j=1

                          N
Skewness: s_i = cbrt( (1/N) · Σ (p_ij − E_i)³ )   asimmetria della distribuzione
                         j=1

Il descrittore dell'immagine è costituito dai momenti calcolati per i diversi canali (RGB o altro spazio): con 3 canali e 3 momenti si ottiene un vettore di soli 9 valori — molto più compatto di un istogramma. Per il confronto tra descrittori solitamente si usa la distanza euclidea, eventualmente pesata.

Momenti globali e locali

I color moments, se calcolati sull'intera immagine, non mantengono informazioni di tipo spaziale — esattamente come gli istogrammi. Per arricchire il descrittore con informazioni locali è possibile dividere l'immagine in regioni e calcolare per ciascuna i relativi color moments. Due varianti:

• partizionamento in regioni disgiunte: una griglia, semplice ed economica, ma sensibile a piccoli spostamenti dell'oggetto (un pixel oltre il confine cambia regione);
• fuzzy regions: suddivisione in regioni parzialmente sovrapposte, più robusta proprio perché un pixel vicino al confine contribuisce a entrambe le regioni.

La stessa strategia può essere usata con altri descrittori globali: è un pattern di progetto ricorrente, non una tecnica specifica dei momenti.

A che cosa servono: i sistemi CBIR

L'applicazione tipica sono i Content Based Image Retrieval Systems (CBIR): sistemi che consentono di reperire immagini sulla base del loro contenuto, senza utilizzare informazioni (keyword, metadati) associate all'immagine stessa. Sfruttano spesso il paradigma query by example e possono implementare meccanismi di relevance feedback per il miglioramento progressivo del risultato sulla base dell'interazione con l'utente.

L'architettura è semplice: il database di immagini passa per l'image feature extraction e popola il feature space; la query image viene proiettata nello stesso spazio; una distance measure produce le retrieved images. Il capitolo 5 riprende i CBIR in dettaglio.

6. Tessiture: che cosa sono e come si misurano

In diverse applicazioni di PR (per esempio nel telerilevamento) i pattern presentano superfici non omogenee caratterizzate da trame più o meno regolari, dette texture, che possono essere sfruttate per la loro classificazione o riconoscimento.

Le texture sono generalmente caratterizzate da primitive che si ripetono secondo alcune regole che ne descrivono la trama. Dal punto di vista percettivo si distinguono tre aspetti:

• conformazione del granulo;
• direzionalità;
• periodicità (scala).

Per la discriminazione di texture sono stati introdotti diversi metodi: matrici di co-occorrenza, gray-level difference, autocorrelazione, morfologia, frattali, banchi di filtri. Le sezioni seguenti approfondiscono i tre trattati a lezione: co-occorrenza, filtri di Gabor e Local Binary Pattern.

7. Matrici di co-occorrenza dei livelli di grigio

Le matrici di co-occorrenza sono istogrammi bidimensionali che descrivono le co-occorrenze di coppie di livelli di grigio secondo specificate direzioni.

Una matrice M_dx,dy è generata da una distanza e una direzione, specificate sotto forma di un vettore spostamento [dx, dy]. L'elemento M_dx,dy[i, j] rappresenta la probabilità che il pixel [x,y] abbia intensità i e il pixel [x+dx, y+dy] abbia intensità j.

Vengono generalmente calcolate le 4 matrici fondamentali: M₋₁,₀, M₋₁,₋₁, M₀,₋₁, M₊₁,₋₁, corrispondenti alle quattro direzioni a 0°, 45°, 90° e 135°.

Esempio svolto a mano

Immagine 6×6 a 2 livelli di grigio, vettore spostamento d = (−1, −1):

0  1  0  0  1  0
1  1  0  1  1  0
0  1  0  0  1  0            d = (−1, −1)
1  1  0  1  1  0
0  1  0  0  1  0
1  1  0  1  1  0

Con questo spostamento le coppie valide sono quelle con x ≥ 1 e y ≥ 1, cioè 5 × 5 = 25 coppie. Contandole una per una si ottiene:

                    j=0   j=1
              i=0 ⎡  2    10 ⎤
    M₋₁,₋₁ =      ⎢          ⎥ × 1/25
              i=1 ⎣  9     4 ⎦

Verifica: 2 + 10 + 9 + 4 = 25. La lettura è istruttiva: gli elementi fuori diagonale (10 e 9) dominano, cioè lungo la diagonale a 45° i livelli tendono a cambiare. È esattamente ciò che ci si aspetta da una texture a righe verticali osservata in diagonale.

Le misure riassuntive

Dalle 4 matrici — o dalla loro media, la cosiddetta matrice non orientata — possono essere estratte numerose caratteristiche riassuntive. Sono queste, non le matrici, a entrare nel vettore di feature:

8. Banchi di filtri e filtri di Gabor

L'approccio a banchi di filtri consiste nell'eseguire la convoluzione dell'immagine con una serie di filtri (il banco) e nell'estrarre dalle immagini ottenute alcuni indicatori di sintesi (media, varianza, momenti, ...).

Un insieme di filtri molto utilizzati sono i filtri di Gabor (Daugman, 1988), per i quali sono state trovate forti analogie con alcuni meccanismi del sistema visivo umano. Ogni filtro è costituito da una funzione sinusoidale attenuata progressivamente da una gaussiana. Il filtro, costituito da una parte reale e una immaginaria, è regolato da 3 parametri:

• la frequenza della sinusoide, f;
• l'orientazione della sinusoide, θ, rispetto al piano x,y;
• l'ampiezza della gaussiana, σ.

Il filtro di Gabor simmetrico bidimensionale ha la forma:

g(x, y : θ, f) = exp( −(1/2) · [ x_θ²/σ_x² + y_θ²/σ_y² ] ) · cos( 2π f x_θ )

dove θ è l'orientazione del filtro, f la frequenza della sinusoide, σ_x e σ_y le deviazioni standard della gaussiana sugli assi x e y, e [x_θ, y_θ] le coordinate di [x, y] dopo una rotazione in senso orario degli assi cartesiani di un angolo pari a (90° − θ):

⎡ x_θ ⎤   ⎡  cos(90° − θ)   sin(90° − θ) ⎤ ⎡ x ⎤
⎢     ⎥ = ⎢                               ⎥ ⎢   ⎥
⎣ y_θ ⎦   ⎣ −sin(90° − θ)   cos(90° − θ) ⎦ ⎣ y ⎦

Il banco

Per la generazione del banco di filtri, una volta definiti i range di interesse, si esegue una discretizzazione (in uno dei tanti modi possibili) dei 3 parametri fondamentali. L'esempio mostrato a lezione copre il dominio delle frequenze con 6 orientazioni e 4 scale, per un totale di 24 filtri.

Dove applicare la convoluzione

Una questione pratica decisiva: su quali punti si calcola la risposta? Le tre strategie viste a lezione:

In tutti i casi, il feature vector finale si ottiene concatenando la risposta (modulo o parte reale) ai diversi filtri nei punti di applicazione della convoluzione.

9. Local Binary Pattern e BSIF

Il Local Binary Pattern (LBP) è un operatore introdotto da Ojala per l'analisi della tessitura delle immagini. L'operatore assegna ai pixel di un'immagine, in un intorno di dimensione 3×3, un valore binario (0 o 1): il valore è assegnato confrontando il valore del pixel con quello del pixel centrale dell'intorno. Se il pixel ha un valore superiore o uguale a quello del pixel centrale gli è assegnato il valore 1, 0 in caso contrario. Concatenando gli 8 bit si ottiene una stringa come 11101001.

L'estensione a intorni circolari

L'operatore LBP di base è stato esteso per gestire intorni di dimensione variabile. In questo caso si usa il concetto di intorno circolare di un pixel e i punti campione sono individuati tramite interpolazione. L'operatore è definito da due parametri:

• il numero di punti campione P;
• il raggio R dell'intorno circolare.

Le configurazioni tipiche mostrate a lezione: P=8, R=1.0; P=12, R=2.5; P=16, R=4.0.

Pattern uniformi

I pattern binari più interessanti sono quelli uniformi, in quanto rappresentano le strutture locali più rilevanti (edge, spot, ecc.). Un pattern è detto uniforme quando, considerato in modo circolare, contiene al massimo due transizioni 0-1 o 1-0. Per esempio i pattern 10000011, 11110000, 00000000 sono uniformi.

Considerare solo i pattern uniformi permette di risparmiare memoria: i pattern totali sono 2^P, mentre gli uniformi sono solo P·(P−1) + 2. Con P = 8: 256 pattern totali contro 58 uniformi.

Il feature vector LBP

Il vettore di feature associato a un'immagine è un istogramma (eventualmente normalizzato) calcolato come segue:

1. l'immagine è partizionata in k² sottofinestre;
2. per ogni sottofinestra è costruito un istogramma in cui ciascun bin è associato a uno specifico pattern; i bin sono in totale P·(P−1) + 3: P·(P−1) bin per i pattern con 2 transizioni, 2 bin per i pattern con 0 transizioni (tutti zeri e tutti uni), 1 bin per tutti i pattern non uniformi messi insieme;
3. il vettore di feature si ottiene concatenando gli istogrammi calcolati per tutte le sottofinestre.

È di nuovo la strategia "globale + griglia" già vista per i color moments: l'istogramma per sottofinestra reintroduce l'informazione spaziale che il singolo istogramma perderebbe.

BSIF: quando i filtri si imparano

Il metodo Binarized Statistical Image Features (BSIF) è stato proposto per l'analisi di tessiture ed è utilizzato per varie applicazioni nell'ambito del riconoscimento del volto (per esempio la presentation attack detection). Analogamente a LBP, rappresenta un'immagine come un istogramma di occorrenze di pattern binari, dove ciascun pattern binario codifica il contenuto visivo di una patch dell'immagine.

La differenza sostanziale è che i singoli pattern binari sono calcolati binarizzando la risposta a un insieme di filtri lineari, e i filtri utilizzati non sono pre-definiti ma appresi attraverso un opportuno addestramento (tipicamente a partire da immagini naturali). I filtri sono stimati in fase di training con l'obiettivo di massimizzare l'indipendenza statistica delle stringhe binarie risultanti dalla loro applicazione, tramite ICA.

Per ciascuna patch X (l × l) e per ciascun filtro W_i:

s_i = Σ_{u,v} W_i(u,v) · X(u,v)             risposta al filtro i

       ⎧ 1   se s_i > 0
b_i =  ⎨                                    binarizzazione
       ⎩ 0   altrimenti

b = concatenazione dei b_i                  stringa binaria della patch

L'intera immagine è rappresentata dall'istogramma delle occorrenze delle possibili stringhe binarie b.

10. Haar-like features e immagine integrale

La texture che caratterizza un'immagine può essere codificata applicando all'immagine stessa delle maschere binarie che evidenziano particolari variazioni di intensità luminosa: sono le Haar-like features. Ogni valore del vettore di feature è ottenuto posizionando una maschera in una sottoregione dell'immagine; le feature sono applicate modificandone dimensione, forma e posizione.

Il numero che ne risulta è impressionante: usando una sottofinestra di dimensione 24×24, con tutte le possibili combinazioni di posizione (orizzontale e verticale) e scala, si ottengono in totale 49396 feature.

Queste feature sono utilizzate per due ragioni: sono efficaci per molte applicazioni (in particolare la localizzazione del volto) e possono essere calcolate in modo efficiente usando l'immagine integrale.

L'immagine integrale

L'immagine integrale in posizione (r,c) è la somma del valore dei pixel sopra e a sinistra di (r,c):

II(r, c) = Σ  I(r', c')        con  r' ≤ r,  c' ≤ c

Può essere calcolata con una sola scansione dell'immagine originale usando le seguenti formule ricorsive:

S(r, c)  = S(r, c−1) + I(r, c)          somma cumulativa per righe
II(r, c) = II(r−1, c) + S(r, c)

con  S(r, −1) = 0  e  II(−1, c) = 0

Usando l'immagine integrale è possibile calcolare la somma del valore dei pixel in qualsiasi rettangolo con quattro soli accessi. Con riferimento allo schema classico a quattro punti, la somma all'interno del rettangolo D è data da:

somma(D) = II(4) + II(1) − II(2) − II(3)

Le feature caratterizzate da 2, 3 o 4 rettangoli possono essere calcolate usando rispettivamente 6, 8 e 9 valori di riferimento. Il costo di ogni feature è dunque costante, indipendente dalle dimensioni del rettangolo: è ciò che rende praticabile la valutazione di decine di migliaia di feature in tempo reale.

Un'applicazione: il localizzatore di Viola e Jones

Il localizzatore di Viola e Jones combina tre ingredienti:

1. Estrazione e valutazione di Haar-like feature (efficiente grazie all'immagine integrale).
2. Classificazione mediante boosting: costruzione di un classificatore robusto come combinazione di molteplici classificatori semplici.
3. Multiscale detection.

Lo schema di funzionamento è x → features → classify → F(x) → y, con y = +1 (face) o y = −1 (non face). La localizzazione è effettuata facendo scorrere una finestra di ricerca (le cui dimensioni possono variare) sull'immagine, estraendo le feature presenti nella finestra e classificando la finestra come volto o non volto. Il capitolo 7 riprende Viola-Jones nel contesto più generale del template matching e della localizzazione.

Verifica le tue conoscenze