Appunti completi del corso di Computer Vision

4.4 LBP, BRIEF, ORB, SURF

L’algortimo SIFT appena presentato è ad oggi l’approccio più robusto e sicuro per cal-

colare i keypoints e i relativi descrittori di un’immagine. Tuttavia questo algoritmo è

abbastanza lento è richiede lo svolgimento di calcoli importanti. Nel corso del tempo so-

no stati quindi introdotti altri algoritmi che mirano allo stesso obiettivo: LBP, BRIEF,

ORB, SURF. Analizziamoli.

54 4.4. LBP, BRIEF, ORB, SURF

4.4.1 LBP

Il Local Binary Patterns (LBP) è un algoritmo descrittore dei keypoints, il che si-

gnifica che, prima di applicarlo, è necessario individuare i punti di interesse, ad esempio

utilizzando un corner detector (Harris). Questo approccio non è invariante rispetto allo

scaling e alle rotazioni ma lo è rispetto alle traslazioni. Confronta il pixel centrale in una

finestra 3x3 con gli 8 campioni adiacenti e costruisce una sequenza binaria basata sul

segno delle differenze. Il suo pseudocodice è

1. Per ogni pixel, si confronta la sua intensità con quella degli 8 pixel adiacenti.

2. Costruzione del codice binario: se il pixel centrale ha un valore di intensità

maggiore rispetto al suo vicino allora scrivi uno ”0”, altrimenti un ”1”. Si ottiene

cosı̀ una stringa binaria di 8 bit e la si converte in un numero intero moltiplicandola

per le potenze di 2: ( 8

≥

1 se i(x) i(x )

i X i−1

τ (x, x ) = f (x) = 2 τ (x, x ) (4.8)

i i

0 se i(x) < i(x )

i i=1

Ora f (x) rappresenta il pattern locale.

3. Dopo aver calcolato i valori LBP per tutti i pixel, si costruisce un istogramma delle

frequenze per rappresentare la distribuzione delle texture.

Per le applicazioni di riconoscimento l’immagine viene suddivisa in blocchi quadrati, viene

calcolato il descrittore LBP di ciascun blocco e infine vengono concatenati gli istogrammi.

Si usano poi questi istogrammi come feature per un classificatore (e.g. SVM).

Figura 4.6: Algoritmo LBP: 1. Considera una finestra 3x3 di campioni; 2. Sottrai ad

ogni campione nella finestra il valore di intensità del pixel centrale; 3. Associa ai valori

negativi ”0” e ai valori positivi o nulli ”1” nella finestra; 4. Moltiplica per potenze di due

questi campioni in modo da ottenere un numero intero.

CAPITOLO 4. FEATURES EXTRACTION AND DESCRIPTION 55

4.4.2 BRIEF

Il Binary Robust Independent Elementary Features (BRIEF) è un descrittore

delle features, invariante alle traslazioni ma non alle rotazioni e allo scaling. Il processo

di calcolo del descrittore segue questi passi:

1. Applicazione di un filtro gaussiano.

2. Confronto di coppie di pixel (x, y) all’interno di una finestra p centrata nel key-

point e selezionate in modo casuale (preferibilmente una distribuzione Gaussiana

Isotropica) (

1 se p(x) < p(y)

τ (p; x, y) = 0 altrimenti ⊤

dove p(x) è l’intensità del pixel nella versione filtrata di p in posizione x = (u, v) .

Questo confronto genera una sequenza binaria che rappresenta la distribuzione

locale delle intensità.

3. Costruzione del descrittore binario, concatenando i risultati dei confronti in un unico

vettore di bit. Il numero n definisce la lunghezza della stringa binaria, ovvero la

q

lunghezza del descrittore. Tipicamente si sceglie n = 128, 256 o 512 bit. Altrimenti

q

si converte la stringa binaria in un numero intero permettendo cosı̀ un confronto

più rapido X i−1

2 τ (p; x, y)

f (p) = 1≤i≤n

q

4. Per confrontare due descrittori BRIEF, si calcola la distanza di Hamming, che conta

il numero di bit differenti (operazione XOR tra due stringhe binarie).

Il descrittore BRIEF lavora su delle features che sono state già estratte da un altro algo-

ritmo (e.g. Harris o FAST) e risulta 5 volte più veloce di SIFT e SURF. Poichè i confronti

tra i descrittori vengono implementati tramite l’operazione di XOR sulle stringhe bina-

rie, questa tecnica è super veloce e, al contempo, occupa molto meno spazio in memoria

rispeto ai descrittori basati su istogrammi (come SIFT).

4.4.3 ORB

L’algoritmo ORB (Oriented FAST and Rotated BRIEF) è un metodo efficiente per l’e-

strazione e la descrizione delle features di un’immagine, progettato per essere veloce e ro-

busto alle trasformazioni geometriche. ORB combina l’estrattore FAST con il descrittore

BRIEF nel seguente modo:

1. FAST:

• Rilevamento dei keypoints: ORB usa l’algoritmo FAST per rilevare i

keypoints.

• Invarianza allo scaling: Poiché FAST non è invariante rispetto alla scala,

ORB applica FAST su una piramide di immagini costruita a diverse scale.

Questo permette di rendere i keypoints invarianti alle operazioni di scala.

56 4.4. LBP, BRIEF, ORB, SURF

• Selezione dei migliori keypoints tramite Harris: Dopo aver applicato

FAST, ORB utilizza il criterio di Harris per selezionare solo i keypoints più

rilevanti (ovvero quelli che rispondono meglio come angoli).

2. Orientazione e Invarianza alla Rotazione:

• Calcolo del centroide d’intensità: Per ciascun keypoint, ORB calcola

il centroide di intensità della patch locale (regione attorno al keypoint). Il

centroide è la media ponderata delle posizioni dei pixel in base alla loro

intensità.

• Assegnazione dell’orientazione: L’orientazione del keypoint è determinata

dalla direzione del centroide rispetto al pixel centrale. Questa orientazione è

importante per rendere il descrittore invariante rispetto alla rotazione.

3. BRIEF:

• Dopo aver ottenuto i keypoints e assegnato loro un’orientazione, ORB utilizza

BRIEF per creare un descrittore binario per ciascuno di essi. Tuttavia, sappia-

mo che BRIEF non è invariante alla rotazione. Per risolvere questo problema,

la patch attorno al keypoint viene ruotata in base all’orientazione stimata. In

questo modo il descrittore è invariante alla rotazione.

I passi eseguiti da questo algoritmo vengono riportati in modo schematico in figura 4.7.

Figura 4.7: Algoritmo ORB per l’estrazione e la descrizione dei keypoints.

4.4.4 SURF

Prima di introdurre l’algoritmo SURF, è necessario definire il concetto di Immagine

Integrale. L’immagine integrale I (x, y) di un’immagine I(x, y) rappresenta la somma

Σ

CAPITOLO 4. FEATURES EXTRACTION AND DESCRIPTION 57

dei pixel all’interno della regione rettangolare compresa tra il punto (0,0) e il punto (x, y)

j≤y

i≤x X

X I(i, j) (4.9)

I (x, y) =

Σ j=0

i=0

Questa rappresentazione permette di calcolare rapidamente la somma dei pixel in qualsiasi

area rettangolare utilizzando solo quattro operazioni. Ad esempio, considerando la figura

4.8, l’area della regione S può essere determinata con:

− −

S = I (A) I (B) I (C) + I (D) (4.10)

Σ Σ Σ Σ

Figura 4.8: Integrale di un’immagine.

Lo Speeded Up Robust Features (SURF) è un algoritmo per l’estrazione e la descri-

zione delle feature in un’immagine, progettato per essere più veloce di SIFT, mantenendo

l’invarianza rispetto allo scaling, rotazioni, traslazioni e cambiamenti di illuminazione.

Gli step eseguiti da questo algoritmo sono:

1. Estrazione delle features: calcolo della matrice Hessiana

L L

xx xy

H = L L

yx yy

dove L è la convoluzione tra la derivata seconda di una gaussiana e l’immagine I,

xx

similmente L , L e L . Questo calcolo viene approssimato utlizzando dei box-

xy yx yy

filters come riportato in figura 4.9. Invece di utilizzare una piramide gaussiana

come SIFT, SURF approssima la LoG con dei box-filters (operatori Haar) e, grazie

all’integrale dell’immagine, questa operazione può essere svolta molto rapidamente

scalando i filtri stessi piuttosto che l’immagine. Ricerca il massimo del determinante

di H per individuare i keypoints.

2. Calcolo dei descrittori: considera una regione quadrata centrata nel keypoint

×

suddivisa in 16 sottoregioni (ciascuna 4 4). Ottieni l’orientazione e compensa per

essa. Somma le risposte delle Haar wavelet, d , d per ciascuna sottoregione. Per

x y

avere informazioni sulla polarità del cambiamento d’intensità, somma anche i valori

assoluti delle risposte delle wavelet. Applica una sfocatura gaussiana e normalizza il

vettore per avere norma unitaria. Il descrittore risultante ha dimensioni 16×4 = 64.

58 4.4. LBP, BRIEF, ORB, SURF

Figura 4.9: Utilizzo dei box filter per approssimare il calcolo delle derivate seconde nella

matrice Hessiana, i.e. approssimazione della Laplacian of Gaussian (LoG).

Il descrittore delle features estratte è cosı̀ invariante all’illuminazione, rotazione e scaling.

Le principali differenze tra SIFT e SURF sono che:

• SIFT costruisce uno scale space applicando ripetutamente un filtro gaussiano e

sottocampionando l’immagine. Questo processo è necessario per identificare i key-

points su diverse scale.

• SURF evita la costruzione esplicita di una piramide di scale perché utilizza filtri

di diverse dimensioni direttamente sull’immagine originale. Grazie all’uso delle

immagini integrali, questi filtri possono essere applicati rapidamente, permettendo

di analizzare diverse scale senza dover generare versioni ridotte dell’immagine.

Dunque, non è necessario costruire la rappresentazione dello scale space in ottave uti-

lizzata da SIFT quando si lavora con SURF. Inoltre, SURF è circa 3 volte più veloce

rispetto a SIFT ma è meno robusto ai cambiamenti di illuminazione e punti di vista.

Capitolo 5

Image Segmentation

La segmentazione delle immagini è il processo che consiste nel suddividere un’immagine in

regioni significative che corrispondono a oggetti o aree differenti. Queste regioni sono

solitamente omogenee rispetto a certe caratteristiche, come ad esempio l’intensità, il co-

lore, o la texture. L’obiettivo della segmentazione è quello di semplificare e/o modificare

l’immagine in modo che sia più facile analizzarla, per esempio, per compiti di riconosci-

mento di oggetti, tracking o analisi semantica. Ci sono due diversi criteri per segmentare

un’immagine: similarità tra i pixel di una stessa regione oppure discontinuità/differenze

tra i pixel di regioni diverse.

In termini formali, il problema della segmentazione può essere formulato nel seguente

modo: suddividere un’immagine R in n regioni R , . . . , R tali che

1 n

ni=1

S R = R (ciascun pixel dev’essere assegnato ad una regione)

1. i

∩ ∅ ∀i ̸

2. R R = = j (ciascun pixel può essere associato ad una sola regione)

i j ∀i

3. R è un insieme connesso (non sempre necessario)

i ∀i

4. Q(R ) = true (predicato)

i ∪ ∀i, ̸

5. Q(R R ) = f alse j i adiacente a j e i = j

i j

5.1 Global Thresholding

Uno dei metodi più semplic