Gli oggetti possono essere riconosciuti sulla base del loro contorno: la forma (shape) è una caratteristica fondamentale per la rappresentazione degli oggetti. L'efficacia delle feature di forma è legata alla presenza di alcune proprietà fondamentali:
| Proprietà | Significato |
|---|---|
| Identificabilità | Oggetti visivamente simili devono essere rappresentati da descrittori simili. |
| Invarianza a trasformazioni affini | Rotazioni, traslazioni e cambiamenti di scala non devono alterare il descrittore. |
| Robustezza al rumore | I descrittori non devono risentire (eccessivamente) della presenza di una quantità ragionevole di rumore. |
| Invarianza rispetto a possibili occlusioni | Un oggetto parzialmente coperto deve restare riconoscibile. |
| Indipendenza statistica e ripetibilità | Descrittore compatto e riproducibile per una stessa tipologia di pattern. |
Sono i criteri con cui giudicare ogni descrittore delle sezioni seguenti: il chain code, per esempio, fallisce clamorosamente su robustezza al rumore e invarianza alla rotazione, mentre i descrittori di Fourier normalizzati soddisfano quasi tutte le proprietà.
Molti descrittori di forma si basano su un'analisi del contorno degli oggetti e richiedono pertanto che questo sia estratto dall'immagine di partenza tramite operazioni di vario tipo: segmentazione basata su colore, operatori morfologici, estrazione degli edge. La pipeline tipica è immagine originale → segmentazione → operatori morfologici → estrazione degli edge, cioè esattamente il capitolo 3 usato come pre-processing.
L'approssimazione poligonale di una forma è utile per ignorare le variazioni minime che una forma può avere e considerare invece la struttura complessiva dell'oggetto: riduce gli effetti del rumore che può nascere dall'operazione di discretizzazione del contorno.
Uno degli approcci possibili è la polygon evolution, un approccio iterativo che prevede, a ogni passo, la sostituzione di due segmenti consecutivi s₁, s₂ con un singolo segmento che congiunge i punti estremi di s₁ e s₂.
L'ordine con cui si analizzano i segmenti è determinato sulla base della rilevanza, calcolata come:
β(s₁, s₂) · l(s₁) · l(s₂)
K(s₁, s₂) = ─────────────────────────────
l(s₁) + l(s₂)dove β(s₁, s₂) è l'angolo relativo al vertice comune tra s₁ e s₂ e l(α) è la lunghezza del segmento α normalizzata rispetto alla lunghezza totale della curva poligonale. La formula è leggibile: la rilevanza cresce con l'angolo (un vertice netto conta più di uno appena accennato) e con la lunghezza dei due segmenti coinvolti. Si eliminano per primi i vertici a rilevanza minima, cioè quelli quasi allineati tra segmenti corti — il rumore.
Analizzando il contorno dell'oggetto è possibile estrarre una serie di indicatori di base, principalmente di tipo geometrico, che hanno un potere discriminante limitato ma possono comunque contribuire al calcolo della similarità tra immagini se combinati con altri descrittori.
| Indicatore | Definizione |
|---|---|
| Centro di gravità | Il centroide dei punti della figura: G = (g_x, g_y) con g_x = (1/N)·Σᵢ xᵢ e g_y = (1/N)·Σᵢ yᵢ, dove N è il numero di punti che costituiscono la forma. |
| Bounding box | Il più piccolo rettangolo in grado di contenere tutti i punti della forma. Da essa si calcolano eccentricity = L/W ed elongation = 1 − L/W. |
| Convexity | Rapporto tra il perimetro del convex hull e quello della forma: C_convexity = O_convexhull / O. Misura quanto la forma è frastagliata o rientrante. |
| Numero di Eulero | Descrive la relazione tra il numero di parti continue (S) e il numero di buchi (N) nella forma: Eul = S − N. Esempi: una figura piena senza buchi ha Eul = 1; una figura con due buchi ha Eul = −1; una figura con un buco ha Eul = 0. |
Il chain code è un approccio comune per la rappresentazione di forme come sequenze connesse di segmenti caratterizzati da una specifica lunghezza e orientazione.
Il primo chain code proposto descrive gli spostamenti lungo una sequenza di pixel di contorno usando la cosiddetta 8-connectivity o la 4-connectivity. La direzione di ciascuno spostamento è codificata sulla base di uno schema di numerazione {i | i = 0, 1, ..., 7} oppure {i | i = 0, 1, 2, 3}, che indica una rotazione in senso antiorario pari a 45° × i oppure 90° × i rispetto all'asse x positivo.
Il chain code è invariante per traslazione (la codifica è relativa) ma è molto sensibile al rumore e non invariante per rotazione. Per ovviare a queste problematiche sono state proposte alcune varianti:
Premi i pulsanti direzionali per tracciare un contorno: il codice si costruisce a ogni passo. Il differential chain code è calcolato come differenza tra direzioni consecutive modulo 8. Usa "Ruota di 45°" per verificare che il codice cambia ma il codice differenziale no.
La shape matrix è una matrice di dimensione M × N che descrive una forma. Due modelli:
Square model shape matrix: data una forma S si costruisce un quadrato centrato nel centro di gravità G di S; la dimensione di ciascun lato è 2L, dove L è la massima distanza euclidea di G da un punto del bordo. Il quadrato viene diviso in N × N sottoquadrati (indicati con S_ij, i, j = 1, ..., N). Ciascun elemento della shape matrix SM = [B_ij] è:
⎧ 1 se μ(S_ij ∩ S) ≥ μ(S_ij)/2
B_ij = ⎨
⎩ 0 altrimentidove μ(F) è l'area della regione F. In parole: la cella vale 1 se la forma ne occupa almeno metà.
Polar model shape matrix: l'area circostante il centro di gravità viene in questo caso partizionata in settori definiti in termini di coordinate polari rispetto al centro. Il calcolo degli elementi della matrice è analogo al caso precedente.
Il descrittore beam angle statistics (BAS) si basa sui raggi (beam) originati da un punto del contorno, definiti come le linee che congiungono il punto agli altri punti del contorno.
Sia B = {P₁, P₂, ..., P_N} il contorno rappresentato come sequenza connessa di punti P_i = (x_i, y_i), i = 1, ..., N. Per ciascun punto P_i il beam angle tra il beam vector successivo V_{i+k} = P_i P_{i+k} e quello precedente V_{i−k} = P_i P_{i−k}, nel neighborhood system di ordine k, viene calcolato come:
C_k(i) = θ(V_{i+k}) − θ(V_{i−k})
dove θ(V_{i+k}) = arctan( (y_{i+k} − y_i) / (x_{i+k} − x_i) )
θ(V_{i−k}) = arctan( (y_{i−k} − y_i) / (x_{i−k} − x_i) )Una rappresentazione compatta si può ottenere considerando i beam angle di ciascun punto C_k(i) come una variabile casuale con distribuzione di probabilità P(C_k(i)) e calcolandone i momenti di diverso ordine (media, varianza, ecc.). È lo stesso trucco dei color moments del capitolo 4: una distribuzione si riassume con pochi momenti.
Il calcolo di alcuni descrittori di forma richiede una rappresentazione monodimensionale del contorno. Le funzioni monodimensionali si derivano dalle coordinate dei punti di contorno e vengono chiamate shape signatures. La shape signature offre una descrizione completa della forma e viene spesso usata come rappresentazione di partenza per l'estrazione di altri descrittori (Fourier, Wavelet).
La funzione associa semplicemente a ciascun punto del contorno P_n(x(n), y(n)), con n ∈ [1, N], il numero complesso generato dalle sue coordinate:
z(n) = ( x(n) − g_x ) + i · ( y(n) − g_y )dove (g_x, g_y) è il centroide. Grazie alla sottrazione del centroide la rappresentazione è invariante per traslazione.
La funzione associa a ciascun punto del contorno la sua distanza dal centroide:
r(n) = [ (x(n) − g_x)² + (y(n) − g_y)² ]^(1/2)Anche questa è invariante per traslazione grazie alla sottrazione del centroide. Prove sperimentali hanno mostrato che è la migliore funzione per il calcolo della shape signature in vista dei descrittori di Fourier.
La funzione analizza l'area del triangolo formato da due punti consecutivi del contorno e il centroide. Al variare del punto lungo il contorno si ottiene di nuovo una funzione monodimensionale.
In generale i descrittori di Fourier si ottengono applicando la trasformata di Fourier a una shape signature. Poiché — come detto — la migliore funzione risulta essere la centroid distance function r(t), la sua trasformata di Fourier discreta è:
1 N−1
a_n = ─── Σ r(t) · exp( −j2πnt / N ), n = 0, 1, ..., N−1
N t=0Poiché la centroid distance function è invariante solo per traslazione e rotazione, i coefficienti di Fourier devono essere normalizzati per renderli invarianti a cambiamenti di scala e rispetto al punto di partenza. La normalizzazione si effettua dividendo ogni coefficiente a_n per il primo coefficiente a₁.
La logica dei descrittori di Fourier è la stessa del filtraggio passa basso del capitolo 2, applicata al contorno anziché all'immagine: i coefficienti di ordine basso descrivono la struttura complessiva della forma, quelli di ordine alto i dettagli fini e il rumore. Troncando la serie si ottiene un descrittore corto e robusto — l'equivalente analitico della polygon evolution della sezione 2.
A sinistra la forma (nera) con la sua ricostruzione da k coefficienti di Fourier (blu); a destra la centroid distance function r(t). Riduci k e osserva sparire prima i dettagli, poi la struttura: con pochissimi coefficienti resta un cerchio.
I sistemi CBIR (Content Based Image Retrieval) ricercano immagini sulla base del loro contenuto — l'esempio quotidiano è Google Image Search. Le applicazioni pratiche sono numerose: digital photo album e piattaforme come Flickr, immagini mediche, musei digitali, ricerca di marchi.
Le componenti principali del sistema sono tre:
Le modalità di formulazione della query sono diverse: query by keywords, query by sketch (l'utente disegna ciò che cerca), query by example (l'utente fornisce un'immagine simile). È possibile adottare meccanismi di relevance feedback per il miglioramento interattivo del risultato.
La ricerca nei sistemi CBIR è necessariamente approssimata, basata sul concetto di similarità. Qui si annida il problema centrale, il semantic gap: la similarità è certamente un concetto soggettivo e di alto livello, mentre le feature estratte sono di basso livello. Due immagini con istogrammi quasi identici possono raffigurare cose completamente diverse; due foto dello stesso soggetto con illuminazione diversa possono avere descrittori lontanissimi.
Per mitigare il problema, i sistemi CBIR combinano feature diverse per sfruttare al meglio tutte le informazioni disponibili. È necessario definire un meccanismo in grado di combinare informazioni diverse, attribuendo un peso a ciascuna tipologia di feature. Due strade:
L'esempio classico di fusione di score è il Borda Count:
Nell'esempio visto a lezione, con 4 immagini, il descrittore di colore assegna i punteggi 4, 3, 2, 1 alle immagini in ordine di rilevanza; il descrittore di forma fa lo stesso con il proprio ordine; la fusione somma i punteggi ottenendo 7, 6, 3, 2 e ne deriva il ranking finale. Il vantaggio del metodo: non richiede che i punteggi delle diverse feature siano confrontabili tra loro (bastano gli ordini), il che elimina il problema della normalizzazione tra metriche eterogenee.
Assegna la posizione di ciascuna immagine nei due ranking (1 = più simile alla query) e osserva il ranking fuso. Prova il caso in cui le due feature sono in disaccordo totale: la fusione produce un pareggio, ed è esattamente l'informazione utile.
Il ciclo del relevance feedback è: query → ricerca → risultato → feedback dell'utente → aggiornamento della metrica di similarità → ricerca. L'utente generalmente indica un set di immagini rilevanti R (esempi positivi) e un set di immagini non rilevanti N (esempi negativi). La ricerca può essere modificata utilizzando due diversi meccanismi:
| Meccanismo | Che cosa fa |
|---|---|
| Query point movement | Sposta la query q (un punto nello spazio delle feature) avvicinandola agli esempi positivi e allontanandola da quelli negativi. |
| Re-weighting | Modifica il peso delle diverse feature, aumentando quello delle feature che massimizzano la similarità con gli esempi positivi. |
I due meccanismi sono complementari e si usano tipicamente insieme.
| Algoritmo | Meccanismi | Formulazione |
|---|---|---|
| Rocchio | Query point movement, distanza euclidea | q' = α·q + β·(1/|P|)·Σ_{p∈P} p − γ·(1/|N|)·Σ_{n∈N} n |
| MARS | Query point movement, re-weighting, considera solo immagini rilevanti, distanza euclidea pesata | d(q,r) = (q − r)ᵀ · W · (q − r) con vettore di pesi W_i = 1/σ_i |
| Mind Reader | Query point movement, re-weighting, distanza di Mahalanobis | Generalizza MARS usando la matrice di covarianza completa anziché i soli pesi diagonali |
Il peso W_i = 1/σ_i di MARS ha una lettura immediata: una feature che negli esempi rilevanti varia poco (σ piccolo) è evidentemente caratteristica di ciò che l'utente cerca, e riceve peso alto; una feature che varia molto è irrilevante e viene attenuata.
Una famiglia diversa di metodi rappresenta la query (le immagini rilevanti) come sottospazio KL dello spazio delle feature, aggiornato iterativamente in base ai feedback ricevuti dall'utente. La regione non rilevante, data l'eterogeneità delle immagini che la compongono, è invece rappresentata da uno spazio MKL (multiplo). L'asimmetria è concettualmente importante: ciò che l'utente cerca è coerente e sta in un sottospazio; ciò che non cerca è tutto il resto del mondo e non lo si può descrivere con un modello unico.
Identificabilità (oggetti simili → descrittori simili); invarianza a trasformazioni affini (rotazioni, traslazioni, scala); robustezza al rumore; invarianza rispetto a possibili occlusioni; indipendenza statistica e ripetibilità (descrittore compatto e riproducibile per la stessa tipologia di pattern).
È un approccio iterativo di approssimazione poligonale che a ogni passo sostituisce due segmenti consecutivi s₁, s₂ con un unico segmento che unisce i loro estremi, per ignorare le variazioni minime e ridurre gli effetti del rumore di discretizzazione. L'ordine è dato dalla rilevanza K(s₁,s₂) = β(s₁,s₂)·l(s₁)·l(s₂) / (l(s₁)+l(s₂)), con β angolo al vertice comune e l lunghezze normalizzate rispetto alla lunghezza totale della curva.
Dalla bounding box (il più piccolo rettangolo contenente la forma): eccentricity = L/W ed elongation = 1 − L/W. Convexity: rapporto tra il perimetro del convex hull e quello della forma, O_convexhull / O. Numero di Eulero: Eul = S − N, con S numero di parti continue e N numero di buchi (1 per una figura piena, 0 con un buco, −1 con due buchi).
Rappresenta la forma come sequenza connessa di segmenti, codificando la direzione di ciascuno spostamento con 8-connectivity (45°×i) o 4-connectivity (90°×i) in senso antiorario rispetto all'asse x positivo. È invariante per traslazione (codifica relativa), ma è molto sensibile al rumore e non invariante per rotazione.
Differential chain code: si calcola la differenza tra direzioni consecutive, sottraendo a ciascun elemento quello precedente modulo n (n = connettività); una rotazione rigida aggiunge una costante a tutti gli elementi e la differenza la elimina. Re-sampling chain code: si campiona il contorno in modo più grossolano prima del calcolo, per limitare l'influenza del rumore.
Si costruisce un quadrato centrato nel centro di gravità G della forma, di lato 2L con L = massima distanza euclidea di G da un punto del bordo. Il quadrato è diviso in N × N sottoquadrati S_ij, e ogni elemento vale B_ij = 1 se μ(S_ij ∩ S) ≥ μ(S_ij)/2 (la forma occupa almeno metà cella), 0 altrimenti, dove μ è l'area. Nella variante polare si partiziona in settori in coordinate polari rispetto al centro.
Per ogni punto P_i del contorno misura l'angolo tra il beam vector successivo V_{i+k} e quello precedente V_{i−k} nel neighborhood di ordine k: C_k(i) = θ(V_{i+k}) − θ(V_{i−k}), con θ(V) = arctan(Δy/Δx). La rappresentazione compatta si ottiene trattando i C_k(i) come una variabile casuale e calcolandone i momenti (media, varianza, ...).
È una funzione monodimensionale derivata dalle coordinate dei punti di contorno, che offre una descrizione completa della forma e serve da base per altri descrittori (Fourier, Wavelet). Le tre: complex coordinates z(n) = (x(n)−g_x) + i(y(n)−g_y); centroid distance function r(n) = [(x(n)−g_x)² + (y(n)−g_y)²]^(1/2); area function (area del triangolo formato da due punti consecutivi e il centroide). Le prime due sono invarianti per traslazione grazie alla sottrazione del centroide.
Si applica la DFT alla shape signature — sperimentalmente la migliore è la centroid distance function: a_n = (1/N)·Σ_{t=0}^{N−1} r(t)·exp(−j2πnt/N). Poiché r(t) è invariante solo per traslazione e rotazione, i coefficienti vanno normalizzati dividendo ogni a_n per il primo coefficiente a₁, ottenendo invarianza a scala e al punto di partenza.
È lo scarto per cui la similarità è un concetto soggettivo e di alto livello, mentre le feature estratte sono di basso livello. La ricerca CBIR è quindi necessariamente approssimata, basata su similarità. Per mitigarlo si combinano feature diverse pesandole, con tecniche di fusione di score o di apprendimento automatico.
Ogni tipologia di feature produce un ranking delle immagini in base alla similarità con la query; i ranking vengono convertiti in punteggi (nell'esempio a 4 immagini: 4, 3, 2, 1), i punteggi delle diverse feature vengono sommati (ottenendo per esempio 7, 6, 3, 2) e la somma genera il ranking finale. Il vantaggio è che non richiede che gli score delle diverse feature siano confrontabili: usa solo gli ordini.
Query point movement: sposta il punto query nello spazio delle feature avvicinandolo agli esempi positivi R e allontanandolo dai negativi N. Re-weighting: modifica il peso delle diverse feature, aumentando quello delle feature che massimizzano la similarità con gli esempi positivi. Rocchio usa solo il primo; MARS e Mind Reader entrambi.
Rocchio: solo query point movement, distanza euclidea, q' = αq + β(1/|P|)Σp − γ(1/|N|)Σn. MARS: query point movement e re-weighting, considera solo le immagini rilevanti, distanza euclidea pesata d(q,r) = (q−r)ᵀW(q−r) con W_i = 1/σ_i. Mind Reader: query point movement e re-weighting con distanza di Mahalanobis, quindi con matrice di covarianza completa.
Perché le immagini rilevanti sono coerenti e possono essere rappresentate da un sottospazio KL dello spazio delle feature, aggiornato iterativamente con i feedback; la regione non rilevante è invece eterogenea — è "tutto il resto" — e viene perciò rappresentata da uno spazio MKL, cioè multiplo.