06. Estrazione Feature (Parte 2)

Estrazione di Feature (Parte 2)

[Slide](C:\UNI\Magistrale\visione\06_Estrazione di feature (parte 2).pdf)

Indice

• Feature di Forma (Shape Features)
  • Proprietà delle Feature di Forma
  • Estrazione del Contorno
  • Polygon Evolution
  • Indicatori di Base
  • Chain Code
  • Shape Matrix
  • Beam Angle Statistics (BAS)
  • Funzioni Monodimensionali (Shape Signatures)
  • Descrittori di Fourier
• Sistemi CBIR
  • Architettura e Query
  • Semantic Gap e Fusione di Score
  • Relevance Feedback

---

Feature di Forma (Shape Features)

Definizione

Le shape features sono descrittori che codificano la forma di un oggetto a partire dal suo contorno. La forma è una delle caratteristiche più discriminative per il riconoscimento di oggetti.

Proprietà delle Feature di Forma

Un buon descrittore di forma deve avere queste proprietà:

• Identificabilità: oggetti visivamente simili devono avere descrittori simili — la stessa classe di oggetti (es. cammelli in pose diverse) deve produrre vettori vicini nello spazio delle feature
• Invarianza a trasformazioni affini: rotazioni, traslazioni e scale non devono alterare il descrittore
• Robustezza al rumore: piccole irregolarità del contorno non devono cambiare significativamente il descrittore
• Invarianza alle occlusioni: il descrittore deve funzionare anche quando l’oggetto è parzialmente coperto
• Indipendenza statistica e ripetibilità: il descrittore deve essere compatto e riproducibile per la stessa classe di pattern

Estrazione del Contorno

La maggior parte dei descrittori di forma richiede che il contorno sia estratto in anticipo. La pipeline tipica è:

Immagine originale → Segmentazione → Morfologia → Estrazione edge → Contorno

Ogni step affina la rappresentazione dell’oggetto fino a ottenere il bordo pulito.

Polygon Evolution

Per ridurre l’effetto del rumore sul contorno, si approssima la forma con un poligono via polygon evolution: un processo iterativo che a ogni passo sostituisce due segmenti consecutivi $s_1,s_2$ con un unico segmento che ne congiunge gli estremi.

L’ordine in cui i segmenti vengono eliminati è basato sulla loro rilevanza:

$K(s_1,s_2)=\frac{\beta (s_1,s_2)\cdot l(s_1)\cdot l(s_2)}{l(s_1)+l(s_2)}$

dove $\beta (s_1,s_2)$ è l’angolo al vertice comune e $l(\alpha )$ è la lunghezza normalizzata del segmento. I segmenti con rilevanza bassa (angolo piccolo, segmenti corti) vengono eliminati per primi.

In pratica: si eliminano i dettagli “poco importanti” fino a ottenere un poligono semplificato che cattura la struttura globale della forma.

Indicatori di Base

Dal contorno si possono estrarre indicatori geometrici semplici con basso potere discriminante individuale, ma utili se combinati:

Centro di gravità (centroide): $G=(g_x,g_y)g_x=\frac{1}{N}{\sum }_{i=1}^N{x}_i{g}_y=\frac{1}{N}{\sum }_{i=1}^N{y}_i$

Bounding box (rettangolo minimo che contiene la forma):

• Eccentricity: $L/W$ (rapporto lunghezza/larghezza)
• Elongation: $1-L/W$ (quanto è allungata la forma)

Convexity (convessità): rapporto tra il perimetro del convex hull e quello della forma originale: $C_{convexity}=\frac{O_{convexhull}}{O}$

Valori vicini a 1 indicano forme convesse; valori bassi indicano forme irregolari/frastagliate.

Numero di Eulero: descrive la topologia della forma come differenza tra parti connesse ($S$) e buchi ($N$): $Eul=S-N$

Esempi: il numero “3” ha $Eul=1$, la “B” ha $Eul=-1$, il “9” ha $Eul=0$.

Chain Code

Definizione

Il chain code rappresenta il contorno come una sequenza di direzioni di spostamento tra pixel adiacenti, usando 8-connectivity (8 direzioni, codificate 0-7) o 4-connectivity (4 direzioni, codificate 0-3).

Il chain code è invariante per traslazione (codifica relativa gli spostamenti) ma presenta due problemi:

• Sensibile al rumore del contorno
• Non invariante per rotazione

Varianti per ovviare ai problemi:

• Differential chain code: codifica le differenze tra direzioni consecutive (modulo $n$ dove $n$ è la connettività) — rende il codice invariante per rotazione
• Re-sampling chain code: si ricampiona il contorno a una risoluzione più grossolana prima di codificarlo — riduce la sensibilità al rumore

Shape Matrix

Una shape matrix è una matrice binaria $M\times N$ che descrive se ciascuna cella di una griglia sovrapposta alla forma contiene o meno una porzione significativa dell’oggetto.

Square model shape matrix (SM): si costruisce un quadrato centrato nel centro di gravità $G$, di lato $2L$ (dove $L$ è la massima distanza euclidea da $G$ al bordo). Il quadrato è diviso in $N\times N$ sottoquadrati $S_{ij}$:

$B_{ij}=\{\begin{array}{ll}1& \text{se }\mu (S_{ij}\cap S)\ge \mu (S_{ij})/2\\ 0& \text{altrimenti}\end{array}$

Polar model shape matrix (PSM): la griglia è definita in coordinate polari rispetto al centroide — settori circolari invece di quadrati. Più adatta a forme rotazionalmente variabili (es. vasi, coppe).

Beam Angle Statistics (BAS)

Definizione

Il BAS descrive la forma locale di ciascun punto del contorno misurando l’angolo tra i “raggi” (beam) che collegano quel punto ai suoi vicini a distanza $k$.

Per ogni punto $P_i$ del contorno, il beam angle di ordine $k$ è:

$C_k(i)={\theta }_{V_{i+k}}-{\theta }_{V_{i-k}}$

dove ${\theta }_{V_{i+k}}=\arctan \frac{y_{i+k}-y_i}{x_{i+k}-x_i}$ è l’angolo del raggio verso il punto successivo a distanza $k$.

Descrittore compatto: trattando $C_k(i)$ come una variabile casuale, se ne calcolano i momenti statistici (media, varianza, ecc.) per costruire un vettore di feature compatto. Il BAS è robusto al rumore perché confronta punti distanti tra loro.

Funzioni Monodimensionali (Shape Signatures)

Le shape signatures sono funzioni 1D derivate dalle coordinate del contorno che forniscono una descrizione completa della forma — spesso usate come input per ulteriori elaborazioni (Fourier, Wavelet).

Le principali sono:

Complex coordinates: ogni punto $P_n=(x(n),y(n))$ del contorno diventa un numero complesso relativo al centroide: $z(n)=[x(n)-g_x]+i[y(n)-g_y]$

Centroid distance function: per ogni punto del contorno, si calcola la distanza dal centroide: $r(n)={\left[(x(n)-g_x{)}^2+(y(n)-g_y{)}^2\right]}^{1/2}$

Entrambe sono invarianti per traslazione grazie alla sottrazione del centroide.

Area function: area del triangolo formato da due punti consecutivi del contorno e il centroide — misura la variazione locale dell’area lungo il profilo.

Descrittori di Fourier

Applicando la trasformata di Fourier discreta alla centroid distance function $r(t)$ si ottengono i descrittori di Fourier:

$a_n=\frac{1}{N}{\sum }_{t=0}^{N-1}r(t)\exp \left(-\frac{j2\pi nt}{N}\right),n=0,1,\dots ,N-1$

La centroid distance function è invariante per traslazione e rotazione, ma i coefficienti $a_n$ devono essere normalizzati per essere invarianti anche a scala e al punto di partenza della parametrizzazione. La normalizzazione si effettua dividendo ogni coefficiente $a_n$ per $a_1$.

Vantaggio: con pochi coefficienti di bassa frequenza si ottiene una buona approssimazione della forma, con capacità di controllo del livello di dettaglio.

---

Sistemi CBIR

Definizione

I sistemi CBIR (Content Based Image Retrieval) ricercano immagini sulla base del loro contenuto visivo (colore, forma, texture), senza usare keyword o metadati. Esempio classico: Google Image Search.

Applicazioni: album fotografici, immagini mediche, musei digitali, ricerca di marchi.

Architettura e Query

Le tre componenti principali di un sistema CBIR:

1. Estrattore di feature: rappresenta tutte le immagini del database come vettori
2. Query engine: calcola la similarità tra la query e le immagini del database
3. Interfaccia utente: consente all’utente di formulare la query e fornire feedback

Modalità di query:

• Query by keywords: ricerca tramite parole chiave (non puro CBIR)
• Query by sketch: l’utente disegna la forma cercata
• Query by example: l’utente fornisce un’immagine di esempio

Semantic Gap e Fusione di Score

Semantic Gap

Il problema fondamentale del CBIR: la similarità percepita dall’utente è di alto livello (semantica), mentre le feature estratte sono di basso livello (pixel, colori, forme). Questo divario è detto semantic gap e limita le prestazioni dei sistemi CBIR.

Per migliorare i risultati, i sistemi CBIR combinano feature diverse (colore + forma + texture). Il meccanismo più semplice è il Borda Count:

1. Ogni tipo di feature produce un ranking delle immagini per similarità con la query
2. Le posizioni in classifica vengono convertite in punteggi
3. I punteggi delle diverse feature vengono sommati per produrre il ranking finale

Esempio: un’immagine in posizione 4 per colore e posizione 4 per forma ottiene un punteggio totale di 8 — che supera immagini in posizione 1 per una sola feature.

Relevance Feedback

Relevance Feedback

Il relevance feedback è un meccanismo di apprendimento interattivo che permette al sistema di affinare i risultati in base ai giudizi dell’utente.

Loop:

1. Il sistema esegue una ricerca e mostra i risultati
2. L’utente indica quali immagini sono rilevanti ($R$) e quali non rilevanti ($N$)
3. Il sistema aggiorna la metrica di similarità in base al feedback
4. Si ripete la ricerca con la metrica aggiornata

Due meccanismi di aggiornamento:

Query Point Movement: sposta il vettore query $\mathbf{q}$ nello spazio delle feature avvicinandolo agli esempi positivi e allontanandolo da quelli negativi.

Re-Weighting: modifica il peso di ciascuna feature aumentando quello delle feature che massimizzano la similarità con gli esempi rilevanti.

Algoritmi principali:

Algoritmo	Meccanismo	Distanza	Note
Rocchio	Query Point Movement	Euclidea	$q^{\prime }=\alpha q+\beta \frac{1}{\Vert P\Vert }{\sum }_{p\in P}p-\gamma \frac{1}{\Vert N\Vert }{\sum }_{n\in N}n$
MARS	QPM + Re-Weighting	Euclidea pesata ($W_i=1/{\sigma }_i$)	Usa solo esempi positivi
Mind Reader	QPM + Re-Weighting	Mahalanobis	Più sofisticato

Approccio a sottospazi: le immagini rilevanti vengono rappresentate come un sottospazio KL dello spazio delle feature, aggiornato iterativamente. Le immagini non rilevanti (eterogenee) sono rappresentate da uno spazio MKL (Multiple Kernel Learning).

---

Prossimi Argomenti

Continueremo con:

• Keypoint - rilevamento di punti chiave e descrittori locali (SIFT, SURF, ORB)
• Trasformazioni 2D e Image Stitching - omografie e composizione di immagini