Feature di forma

Annalisa Franco

annalisa.franco@unibo.it

http://bias.csr.unibo.it/VR/

Le feature di forma (shape features)

• Gli oggetti possono essere

riconosciuti sulla base del

loro “contorno”;

• La forma (shape) è una

caratteristica

fondamentale per la

rappresentazione degli

oggetti.

2

Proprietà delle feature di forma (1)

• L’efficacia delle feature di forma è legata alla presenza di alcune

proprietà fondamentali:

▫ 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.

3

Proprietà delle feature di forma (2)

▫ Robustezza al rumore

I descrittori non devono risentire (eccessivamente) della presenza di (una

quantità ragionevole) di rumore.

▫ Invarianza rispetto a possibili occlusioni

▫ Indipendenza statistica e ripetibilità

Descrittore compatto e riproducibile per una stessa tipologia di pattern.

4

Estrazione del contorno

• 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 (es.

segmentazione basata su colore, operatori morfologici, estrazione

degli edge, ecc.).

5

Immagine originale Segmentazione Operatori morfologici Estrazione degli edge

Polygon evolution (1)

• 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. Ciò permette di ridurre gli

effetti del rumore che può nascere dall’operazione di

discretizzazione del contorno.

• Uno degli approcci possibili per l’approssimazione poligonale di

una forma è chiamata polygon evolution, un approccio iterativo

che prevede, a ogni passo, la sostituzione di due segmenti

consecutivi 𝑠1, 𝑠2 con un singolo segmento che congiunge i punti

estremi di 𝑠1 e 𝑠2.

6

Polygon evolution (2)

• L’ordine con cui si analizzano i segmenti è determinato sulla

base della rilevanza, calcolata come:

𝐾 𝑠1, 𝑠2 =𝛽 𝑠1, 𝑠2 𝑙 𝑠1 𝑙(𝑠2)

𝑙 𝑠1 + 𝑙 𝑠2

dove 𝛽 𝑠1, 𝑠2 è l’angolo relativo al vertice comune tra 𝑠1 e 𝑠2 e

𝑙 𝛼 è la lunghezza del segmento 𝛼 normalizzata rispetto alla

lunghezza totale della curva poligonale.

7

Shape: indicatori di base

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.

• Centro di gravità: corrisponde semplicemente al centroide dei

punti della figura:

𝐺 = 𝑔𝑥 , 𝑔𝑦

𝑔𝑥 =1

𝑁σ𝑖=1𝑁 𝑥𝑖 𝑔𝑦 =

1

𝑁σ𝑖=1𝑁 𝑦𝑖

dove N è il numero di punti che costituiscono la forma..

8

Shape: indicatori di base• Bounding box: il più piccolo rettangolo in

grado di contenere tutti i punti della forma. A

partire dalla bounding box si possono

calcolare due indicatori:

Eccentricity:𝐿

𝑊

Elongation: 1 −𝐿

𝑊

• Convexity: rapporto tra il perimetro del

convex hull 𝑂𝑐𝑜𝑛𝑣𝑒𝑥ℎ𝑢𝑙𝑙 e quello della forma O:

𝐶𝑐𝑜𝑛𝑣𝑒𝑥𝑖𝑡𝑦 =𝑂𝑐𝑜𝑛𝑣𝑒𝑥ℎ𝑢𝑙𝑙

𝑂• Numero di Eulero: descrive la relazione tra il

numero di parti continue (S) e il numero di

buchi (N) nella forma:

𝐸𝑢𝑙 = 𝑆 − 𝑁

9

Eul = 1 Eul = -1 Eul = 0

Shape: indicatori di base

• Circularity ratio: questo indicatori quantifica la

similarità della forma in oggetto con un cerchio.

Esistono diverse definizioni: Rapporto tra l’area della forma e quella di un

cerchio di pari perimetro:

𝐶1 =4𝜋𝐴𝑠𝑂2

dove 𝑂2 è il perimetro della forma e 𝐴𝑠 l’area.

Rapporto tra area e perimetro:

𝐶2 = 𝐴𝑠/𝑂𝑠 Circle variance:

𝐶3 =𝜎𝑅𝜇𝑅

dove 𝜇𝑅 e 𝜎𝑅 sono la media e la deviazione

standard della distanza radiale dal centroide

𝑔𝑥, 𝑔𝑦 dei punti di contorno.

10

Chain code (1)

• 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 ሼ𝑖|𝑖 =

11

Chain code (2)

Il chain code è invariante per traslazione (codifica relativa) ma è

molto sensibile al rumore e non invariante per rotazione. Per

ovviare a queste problematiche sono state proposte alcune varianti:

• Differential chain code: la codifica si ottiene calcolando la

differenza tra direzione consecutive (ottenuta sottraendo a

ciascun elemento del chain code quello precedente modulo n dove

n è la connettività).

• Re-sampling chain code: per limitare l’influenza del rumore

l’approccio prevede un campionamento del contorno più

grossolano prima del calcolo del chain code.

12

Shape matrix (1)

È una matrice di dimensioneM × N che descrive una forma.

• 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 𝑁 × 𝑁sottoquadrati (indicati con 𝑆𝑖𝑗 , 𝑖, 𝑗 = 1, . . , 𝑁 ). Ciascun elemento

della shape matrix 𝑆𝑀 = 𝐵𝑖𝑗 è:

𝐵𝑖𝑗 = ൝1, 𝜇 𝑆𝑖𝑗 ∩ 𝑆 ≥ 𝜇 𝑆𝑖𝑗 /2

0, 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖

dove 𝜇 𝐹 è l’area della regione F.

13

Shape matrix (2)

• 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.

14

Beam Angle Statistics (1)

• Il descrittore beam angle statistics 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 𝐵 = 𝑃1, 𝑃2, … , 𝑃𝑁 il contorno rappresentato come sequenza

connessa di punti 𝑃𝑖 = 𝑥𝑖 , 𝑦𝑖 , 𝑖 = 1, . . , 𝑁. Per ciascun punto 𝑃𝑖 il

beam angle tra il beam vector successivo 𝑉𝑖+𝑘 = 𝑃𝑖𝑃𝑖+𝑘 e quello

precedente 𝑉𝑖−𝑘 = 𝑃𝑖𝑃𝑖−𝑘 nel neighborhood system di ordine k

viene calcolato come:

𝐶𝑘 𝑖 = 𝜃𝑉𝑖+𝑘 − 𝜃𝑉𝑖−𝑘dove

𝜃𝑉𝑖+𝑘 = 𝑎𝑟𝑐𝑡𝑎𝑛𝑦𝑖+𝑘 − 𝑦𝑖𝑥𝑖+𝑘 − 𝑥

𝜃𝑉𝑖−𝑘= 𝑎𝑟𝑐𝑡𝑎𝑛𝑦𝑖−𝑘 − 𝑦𝑖𝑥𝑖−𝑘 − 𝑥

15

Beam Angle Statistics (2)

16

Una rappresentazione compatta si può

ottenere considerando i beam angle di

ciascun punto 𝐶𝑘 𝑖 come una variabile

casuale con distribuzione di probabilità

𝑃 𝐶𝑘 𝑖 e calcolandone i momenti di

diverso ordine (media, varianza, ecc…)

BAS: esempio

17

One-dimensional functions (1)

• Il calcolo di alcuni descrittori di forma richiede una

rappresentazionemonodimensionale 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 (es. Fourier, Wavelet).

• Complex coordinates: la funzione associa semplicemente a

ciascun punto del contorno 𝑃𝑛 𝑥 𝑛 , 𝑦(𝑛) , 𝑛 ∈ 1, 𝑁 il numero

complesso generato dalle sue coordinate:

𝑧 𝑛 = 𝑥 𝑛 − 𝑔𝑥 + 𝑖 𝑦 𝑛 − 𝑔𝑦

dove 𝑔𝑥, 𝑔𝑦 è il centroide.

18

One-dimensional functions (1)

• Centroid distance function: la funzione associa a ciascun punto

del contorno la sua distanza dal centroide:

𝑟 𝑛 = 𝑥 𝑛 − 𝑔𝑥2 + 𝑦 𝑛 − 𝑔𝑦

2 1/2

Grazie alla sottrazione del centroide, le due precedenti

rappresentazioni sono invarianti per traslazione.

• Area function: la funzione analizza l’area del triangolo formato

da due punti consecutivi del contorno e il centroide.

19

Descrittori di Fourier (1)

In generale i descrittori di Fourier si ottengono applicando la

trasformata di Fourier a una shape signature. Alcune prove

sperimentali hanno mostrato che la migliore funzione per il calcolo

della shape signature è la centroid distance function 𝑟 𝑡 . La

trasformata di Fourier discreta di 𝑟 𝑡 è:

𝑎𝑛 =1

𝑁

𝑡=0

𝑁−1

𝑟 𝑡 exp −𝑗2𝜋𝑛𝑡

𝑁, 𝑛 = 0,1, . . , 𝑁 − 1

Poiché 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.

20

Descrittori di Fourier (2)

Secondo la teoria alla base della trasformata di Fourier, la forma

generale dei coefficienti di una centroid distance function 𝑟 𝑡trasformata con cambiamento di scala e di punto iniziale 𝑟 𝑡 𝑜 è:

𝑎𝑛 = exp 𝑗𝑛𝜏 𝑠 𝑎𝑛(𝑜)

dove 𝑎𝑛 e 𝑎𝑛(𝑜)

sono i coefficienti di Fourier della forma trasformata e

di quella originale rispettivamente, 𝜏 è l’angolo relativo al

cambiamento di punto iniziale e s è il fattore di scala.

Consideriamo la seguente espressione:

𝑏𝑛 =𝑎𝑛𝑎1

=exp 𝑗𝑛𝜏 𝑠 𝑎𝑛

(𝑜)

exp 𝑗𝜏 𝑠 𝑎1(𝑜)

=𝑎𝑛(𝑜)

𝑎1(𝑜)

exp 𝑗 𝑛 − 1 𝜏 = 𝑏𝑛(𝑜)

exp 𝑗 𝑛 − 1 𝜏

Ignorando le informazioni di fase e considerando solo il modulo dei

coefficienti, allora 𝑏𝑛 e 𝑏𝑛(𝑜)

sono uguali; quindi 𝑏𝑛 è invariante

anche a cambiamenti di scala e di punto iniziale. Il descrittore è

quindi dato da: 𝑏𝑛 , 0 < 𝑛 < 𝑁

21

Momenti invarianti (1)

• I momenti invarianti, chiamati anche Geometric moment

invariants, sono i più semplici momenti con basi ψ𝑝𝑞 = 𝑥𝑝𝑦𝑞;

sebbene queste basi siano complete, esse non sono ortogonali.

• Dati due interi non negativi p e q il momento mp,q di ordine (p+q)-

esimo del pattern f(x,y) è:

Centroide (baricentro): [x0 , y0] = [m1,0 / m0,0 , m0,1 /m0,0].

Se l’immagine è traslata di un vettore t anche il centroide è traslato

della stessa quantità; pertanto l’immagine centralizzata fT(x,y)=f(x-

x0,y-y0) è invariante per traslazione.

22

dxdy,xfyxm qpq,p y

Momenti invarianti (2)

Combinando in modo più complesso diversi momenti si posso

ottenere feature invarianti per scala e rotazione. Queste feature

presentano tuttavia alcuni svantaggi:

• Ridondanza di informazioni: poiché le basi utilizzate non sono

ortogonali, questi momenti presentano un elevato grado di

ridondanza;

• Sensibilità al rumore: i momenti di ordine elevato sono molto

sensibili alla presenza di rumore nell’immagine;

• Grandi variazioni nel range di valori: poiché le basi prevedono il

calcolo della potenza di p e q, i momenti calcolati presentano

un’elevata variabilità del range di valori per ordini differenti; ciò

può causare instabilità in particolare quando la dimensione

dell’immagine è elevata.

23

Momenti di Zernike

Tra i diversi momenti proposti, i momenti di Zernike sono probabilmente i

più popolari e utilizzati grazie alla loro dimostrata superiorità. I polinomi di

Zernike (tutti ortogonali tra loro) sono definiti come:

Per ogni coppia di valori m, d: con d 0, d-m pari e non negativo, il

momento di Zernike di ordine d, con ripetizione m è dato da:

dove, il kernel k(d, m; x, y) espresso in coordinate polari è:

Il modulo di un momento di Zernike è invariante per rotazione.

L’invarianza anche per scala e traslazione può essere ottenuta

normalizzando f (attraverso i momenti regolari) prima del calcolo dei

momenti di Zernike.

24

ld

/md

l

ldm r

!/md!/md!l

!drR 2

2

0 1212

11

dxdyy,x;m,dky,xfd

A

yx

dm π

1

122

imdm erR,r;m,dk θ

• Il riconoscimento del volto da identikit è spesso un elemento

fondamentale per l’identificazione di criminali.

• Un disegno (identikit) dev’essere confrontato con un insieme

(molto ampio) di volti per consentire l’individuazione dei soggetti

più simili..

• Identikit e fotografie non sono direttamente confrontabili.

Un’applicazione: riconoscimento

identikit

Input sketch Edge image Shape feature

vectors

LBP

Shape

Matrix

Combined and normalized

feature vector

Photo candidates

Output photo

Edge

extractionShape feature

computation

Photo-

candidate

selection

SURF-based

recognition

Feature di forma (1)

Shape matrix

Local BinaryPattern

Beam Angle Statistics

Local OrientationHistogram

Fourier Descriptors

Feature di forma (2)

Problemi aperti

28

• Riconoscimento da facial composite

29

I Sistemi CBIR• Si tratta di sistemi che ricercano immagini sulla base del loro

contenuto (es. Google Image Search).

• Numerose sono le applicazioni pratiche:

▫ Digital Photo Album, Flickr, ecc…

▫ Immagini mediche

▫ Musei digitali

▫ Ricerca di marchi

• Le componenti principali del sistema sono:

▫ Estrattore di feature (rappresentazione delle immagini);

▫ Query engine (calcolo della “similarità” tra immagini);

▫ Interfaccia utente.

30

Formulazione della query

Le modalità di formulazione della query sono diverse:

Possibile adottare meccanismi di relevance feedback per il

miglioramento interattivo del risultato.

31

Query by sketchQuery by keywords Query by example

Query engine

• Abbiamo già analizzato diverse tecniche di estrazione di feature

che consentono di codificare informazioni relative al contenuto

dell’immagine in termini di colore, tessitura e forma.

• La ricerca nei sistemi CBIR è necessariamente approssimata,

basata sul concetto di similarità.

▫ Problema: semantic gap! La similarità è certamente un concetto

soggettivo e di alto livello, mentre le feature estratte sono di basso

livello.

• I sistemi CBIR solitamente 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.

▫ tecniche di fusione di score;

▫ apprendimento automatico.

32

Fusione di score: esempio Borda Count

33C

olo

reF

orm

a

• Ogni tipologia di feature produce una classifica o

ranking delle immagini, a seconda della similarità

che esse presentano con la query.

• I ranking sono poi convertiti in punteggi che sono poi

tra loro sommati e usati per produrre il ranking

finale.

Query

Fusione di score: esempio Borda Count

34

4 3 2 1

4 3 2 1

Colo

reF

orm

aF

usi

on

e 7 6 3 2

RisultatoRisultato

Il relevance feedbackQuery

Feedback dell’utente

Aggiornamento della metrica di

similarità

RicercaRicerca

Query Point Movement e

Re-Weighting

• 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:

36

Query Point Movement

Query Point Movement

+ Re-weighting

Query point movement. Sposta la

query q (punto nello spazio delle

feature) avvicianandola agli esempi

positivi allontanandola da quelli

negativi.

Re-Weighting. Modifica il peso delle

diverse feature aumentando quello

delle feature che massimizzano la

similarità con gli esempi positivi.

• Rocchio:▫ Query Point Movement

▫ Distanza euclidea

• MARS:▫ Query Point Movement

▫ Re-Weighting

▫ Considera solo immagini rilevanti

▫ Distanza euclidea pesata

• Mind Reader:▫ Query Point Movement

▫ Re-Weighting

▫ Mahalanobis distance

Alcuni algoritmi (1)

𝑞′ = 𝛼𝑞 + 𝛽1

𝑃

𝑝∈𝑃

𝑝 − 𝛾1

𝑁

𝑛∈𝑃

𝑛

𝑑 𝑞, 𝑟 = 𝑞 − 𝑟 𝑇 ∙ 𝑊 ∙ 𝑞 − 𝑟

𝑊𝑖 =1

𝜎𝑖Vettore

di pesi

Alcuni algoritmi (2)

Approccio basato su sottospazi KL:

• La query (immagini rilevanti) viene

rappresentata 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, è invece

rappresentata da uno spazio MKL.

38