5
�oggetti� della scena trattata aprendo nuove prospettive per la rete NUSD nelle
applicazioni video.
1.2 Immagini e video digitali: parametri descrittivi
Tradizionalmente le immagini digitali vengono rappresentate come matrici
rettangolari di pixels e i video digitali vengono interpretati come un flusso di frames
(essi stessi riconducibili a immagini). Le immagini, pertanto, non sono altro che un
insieme di picture elements (pixels appunto) spazialmente ordinati a formare una scena.
La scena, a sua volta, � interpretabile come una serie di oggetti e uno sfondo. Oggetti e
sfondo formano classi di pixels che presentano caratteristiche comuni tipiche di quella
classe e utili pertanto per rappresentarla.
Il problema vero � quello di identificare quelle caratteristiche che permettono
ad un utente o, meglio sarebbe, ad un automa di separare e riconoscere in maniera
univoca oggetti e sfondo. Alcuni parametri utili a descrivere quelle caratteristiche sono
le tre componenti colore, la differenza tra due frames successivi, informazioni sugli
spostamenti orizzontali e verticali dei singoli pixel o di blocchi, la variazione di
illuminazione e altri. Ogni parametro porta naturalmente informazioni sull�immagine
ma bisogna capire quale diventa utile allo scopo: segmentare l�immagine in background
( lo sfondo ) e foreground ( oggetti in primo piano ).
1.3 Clustering
Quando vengono individuati i parametri rappresentativi della scena bisogna
trovare la procedura migliore per raggruppare i pixels con caratteristiche comuni cio�
trovare la tecnica migliore per clusterizzare l�immagine.
6
1.3.1 Introduzione al clustering
Come gi� accennato, il clustering � un processo con il quale si tenta di
determinare le relazioni tra gli oggetti appartenenti ad un insieme di dati e organizzare
gli stessi in raggruppamenti (cluster) in modo che gli oggetti in un cluster siano tra loro
pi� simili rispetto quelli assegnati ad un altro cluster. Per clustering s�intende quindi una
tecnica con la quale si creano raggruppamenti di oggetti simili, che presentano fra loro
caratteristiche omogenee; quindi se un oggetto in un cluster possiede determinate
caratteristiche, � molto probabile che anche gli altri oggetti nel cluster presentino le
stesse propriet�.
1.3.2 Tecniche di clustering
Ci sono due grossi gruppi in cui distinguere le tecniche di clustering:
partitioning (anche detti K-Clustering) in cui ogni oggetto � assegnato ad un cluster, e
hierarchical clustering, in cui ogni cluster ottenuto in una prima fase e di taglia pi�
grande � a sua volta riclusterizzato in gruppi pi� piccoli.
1.3.2.1 K-clustering: algoritmo di tipo iterativo delle partizioni
Negli algoritmi di questo tipo i dati da clusterizzare sono organizzati in pattern
(vettori aventi come componenti delle variabili dette features). Quindi dato un insieme S
di dati e un intero k lo scopo � quello di partizionare lo spazio di partenza in k
sottoinsiemi
i
S che rappresentano, appunto, i cluster. Per attuare questa partizione nella
maniera ottimale questi algoritmi utilizzano la minimizzazione di una funzione
obiettivo, generalmente questa minimizzazione avviene attraverso una procedura di tipo
iterativo che distingue i vari algoritmi tra loro: il valore minimo globale ottenuto dalla
funzione obiettivo ci fornisce la soluzione ottimale, mentre i minimi locali
rappresentano soluzioni sub-ottimali.
7
In questi algoritmi i cluster sono rappresentati da un prototipo rispetto al quale
si definisce una misura di similarit� da cui poi ricavare la funzione obiettivo. Una tipica
funzione obiettivo o comunque un criterio di ottimizzazione usato comunemente e la
somma dei quadrati (distanza euclidea tra i dati e i prototipi)
Questo tipo di ottimizzazione presenta alcuni punti deboli:
1. Favorisce il riconoscimento di cluster di forma sferica
2. Non reietta adeguatamente il rumore lasciandosi influenzare molto da quei
punti di S che non appartengono naturalmente a nessuno dei cluster
Cambiando la funzione obiettivo o la misura di distanza riesco a riconoscere
anche altre forme dei cluster o migliorare il problema del rumore, generando nuove
famiglie di algoritmi che si adattano ai vari casi. Una di queste � la cosiddetta density
based in cui l�idea base � quella di considerare i cluster come un�area dell�insieme di
partenza �densamente popolata�. Quest�area potr� avere una forma qualunque e
presumibilmente potr� essere considerata separata da ogni altra presente nell�insieme di
partenza S.
Un�altra famiglia legata a quella density based � la graph theoretic. Gli
algoritmi appartenenti a questa famiglia si basano sulla teoria dei grafi e presentano
vantaggi importanti solo se i cluster da rappresentare trovano una forma semplificata
applicando le regole proprie della stessa.
1.3.2.2 Hierarchical clustering: algoritmi di tipo gerarchico
Questo tipo di algoritmo � usato fondamentalmente quando l�insieme di
partenza S non ha una singola ed ovvia partizione in cluster ben separati. L�obiettivo del
clustering gerarchico � quello di produrre un albero T(S) nel quale i nodi rappresentano
sottoinsiemi si S. In quest�albero S stesso � un nodo, in particolare rappresenta la radice
dell�albero stesso da cui partono i �figli�.
8
Gli algoritmi gerarchici si dividono in due sottoclassi:
1. Agglomerativi gerarchici
2. Divisivi gerarchici
I primi iniziano facendo corrispondere ad ogni dato in ingresso un cluster. In
seguito si cercano i due cluster pi� simili per poterli unire in un unico cluster. Si
procede cos� fino a quando non si giunge ad un unico cluster con tutti i dati. A questo
punto si decide qual � la partizione migliore applicando un opportuno criterio di
validazione e s�individua pertanto a quale livello di T(S) ho la migliore clusterizzazione
di S.
I secondi procedono in maniera inversa rispetto agli agglomerativi iniziando da
un unico cluster che contiene tutti i pattern e si comincia a separarli fino a trovare, al
limite, cluster con un solo dato d�ingresso. Anche qui con un criterio di validazione si
sceglie il livello di T(S) migliore.
La finalit� del lavoro presentato � clusterizzare una sequenza video,
separandola in zone omogenee, in modo da separare da uno sfondo quasi statico gi
oggetti in moto nella scena. Questa separazione ha come scopo quello di ottimizzare la
codifica della scena e permettere la trasmissione, con buona qualit�, anche a bassi
bitrate. Vediamo qual�� attualmente una tecnica di codifica molto usata: l�Mpeg4.
1.4 La codifica Mpeg-4
Lo standard di codifica attualmente pi� usato � l�Mpeg-4 in quanto � stato
creato per supportare un ampio numero di applicazioni che vanno dai computer alla
compressione video per filmati commerciali e non da ultimo � utilizzato nell�industria
delle telecomunicazioni.
9
L�Mpeg-4 supporta un basso bitrate che pu� essere, pertanto, ottimizzato per le
bande strette delle trasmissioni senza cavo, internet e altri campi dove un basso bitrate �
indispensabile.
1.4.1 Lo standard Mpeg-4
La societ� Mpeg ha iniziato lo sviluppo dello standard Mpeg-4 nel 1993
cercando di sviluppare un algoritmo e degli strumenti per ottenere un�efficiente codifica
e rappresentazione audio-video per venire incontro alle esigenze delle applicazioni di
video conferenza. All�inizio lo standard fu ristretto principalmente alle applicazioni a
basso bitrate salvo poi svilupparlo per le pi� svariate applicazioni a diversi bitrate. La
forza di questo algoritmo risiede nell�abilit� di rappresentare le scene come un insieme
di oggetti audiovisivi, per aumentare l�efficienza della codifica audio e video.
Lo standard � capace di considerare, in fase di codifica, audio, video, testi,
immagini ecc. come oggetti separati che, in fase di decodifica, verranno mutiplexati e
sincronizzati per ricostruire l�immagine di partenza. Il separare la scena in oggetti
permette, naturalmente, di poter agire in maniera casuale su ogni oggetto e codificarlo
in maniera autonoma. Si pu� poi pensare ad eventuali manipolazioni su quella parte
della scena rappresentata da un oggetto e si pu� creare quindi una certa interattivit� con
la scena stessa. Lo standard nella sua prima versione � stato presentato nel 1999.
L�algoritmo di compressione video dello standard sfrutta la ridondanza
spaziale e temporale che si verifica in alcune parti di un video o nei frames.
La ridondanza spaziale si pu� sfruttare con una tecnica di codifica intraframe
che consiste nel codificare ogni frame separatamente. Si pu� poi pensare di sfruttare il
fatto che due frame consecutivi siano tra loro molto simili e usare questo per aumentare
la compressione. Questa tecnica di compressione temporale aumenta la codifica rispetto
alla semplice spaziale ma non di molto come ci si pu� attendere perch� ci possono
essere video in cui il salto tra due frame successivi avviene molto spesso. Questa tecnica
di codifica � detta interframe.
10
Una semplice tecnica interframe � quella che valuta la differenza tra due frame
successivi e la codifica. Questa tecnica sembra ottimale per ricostruire le sequenze,
pensando di trasmettere solo la differenza sommandola con la precedente per ottenere il
frame successivo. E� evidente che questo si concilia bene solo se i frame che stiamo
trattando presentano un background (sfondo) stazionario e un foreground (immagine in
primo piano) che si muove e che verr� codificato. Nella realt�, per�, questo � un evento
che si realizza poche volte e bisogna sempre considerare un movimento dello sfondo
dovuto ad un tremolio dell�utente che riprende la scena (anche se questo � forse il meno
dannoso) ovvero a panning e zomming della camera. L�Mpeg-4 prevede una tecnica di
motion compensation per risolvere questo problema.
Figura 1.1:
Diagramma a blocchi di un Encoder per la codifica MPEG-4
11
Con l�Mpeg-4 un oggetto video pu� consistere in un intero frame o in parte di
esso e pu� essere codificato come una forma arbitraria. Lo stream dell�Mpeg-4 contiene
tre piani di video oggetti (video object pane-VOPs) che non sono altro che gruppi di
macroblocchi, in genere 16x16 pixels per lo spazio luminanza e 8x8 pixels per lo spazio
crominanza per il generico sottospazio del colore di una scena.
Vediamo cosa rappresentano questi piani
• I-VOPs che contiene le porzioni intracoded, un po� come si fa nella
compressione Jpeg
• P-VOPs che sono codificati predittivamente partendo dal precedente VOPs gi�
codificato
• B-VOPs che � codificato in maniera bidirezionale usando la differenza con i
precedente ed il successivo VOPs
I-VOPs � il piano che compare regolarmente nello stream perch� serve a
decodificare i successivi intercoded VOPs quali ad esempio gli stessi P-VOPs e B-
VOPs.
La figura 1.1 mostra il diagramma a blocchi semplificato di un encoder usato
nella codifica Mpeg-4. Per primo l�encoder determina se il VOP deve essere intercoded
o intracoded per decidere come operare. Se il VOP � di tipo I-VOPs, quindi intracoded,
si opera una DCT (discrete cosine trasformation) bidimensionale su tutti i macroblocchi
del piano, i coefficienti trovati vengono poi quantizzati. In questo modo si trasformano
le informazioni spaziali dei macroblocchi nel dominio delle frequenze. In questo
dominio si pu� attuare una migliore codifica, infatti, la maggior parte dell�energia dei
blocchi la ritroviamo in bassa frequenza e pertanto, saranno i coefficienti della DCT a
queste frequenze ad essere codificati con un numero inferiore di bits, dovendo occupare
per pi� tempo il canale trasmissivo, mentre ad alta frequenza potranno essere codificati
con un numero di bits maggiore. La scelta di preferire le componenti a bassa frequenza
� dovuta al fatto che bastano per avere una buona qualit� dell�immagine in fase di
ricostruzione.
12
Per ricostruire l�immagine si opera una quantizzazione inversa e una
trasformazione DCT inversa sull�I-VOPs codificato e si ottengono i macroblocchi
dell�I-VOP. I coefficienti calcolati vengono anche conservati in una memoria locale per
poter mettere in piedi una procedura di Motion Compensation con i blocchi successivi.
Se la codifica del VOP � di tipo intercoded, quindi nel caso di una codifica P-
VOPs, si opera su ogni macroblocco una predizione della Motion Compensation. Si
prende un VOP di riferimento per trovare il macroblocco pi� simile a quello da
codificare, si opera poi una differenza spaziale tra il macroblocco presente in ingresso
all�encoder e quello di riferimento e si conserva il risultato in un vettore di moto. Su
questo vettore si eseguono le stesse operazioni di prima: DCT, quantizzazione per ogni
macroblocco P-VOPs. Al decoder il P-VOP � ricostruito operando una Motion
Compensation sui coefficienti del vettore di moto su cui si � gi� eseguita una
quantizzazione inversa ed una DCT inversa. Il P-VOP ricostruito viene poi conservato
in una frame memory per essere utilizzato per la successiva operazione di Motion
Compensation.
La codifica dei B-VOPs � simile a quella del P-VOPs tenendo conto che questa
deve essere bidirezionale.
Lo standard prevede tecniche per migliorare la robustezza video per quelle
situazioni in cui si verificano facilmente errori. Presenta, infatti, una capacit� interna a
rivelare e localizzare gli errori, a recuperare i dati su cui si sono verificati gli errori e, a
livello visivo, ridurre a minimo l�effetto dell�errore sull�immagine.
13
CAPITOLO 2
LA SEGMENTAZIONE
2.1 Introduzione
La parola segmentazione ha un significato che dipende in gran parte dalle
applicazioni e dal contesto in cui � usata ma segmentare, fondamentalmente, vuol dire
trovare una procedura la cui finalit� � quella di definire una partizione dello spazio. Nel
caso delle immagini e delle sequenze video lo spazio pu� essere temporale (1D),
spaziale (2D) o spazio-temporale (3D) e verr� chiamato decision-space.
La fase di segmentazione � fondamentale nel processo conoscitivo di una scena
reale; grazie a questa analisi si � in grado di distinguere gli oggetti salienti rispetto allo
sfondo. Come � noto il processo di segmentazione di immagini statiche, per la ricerca
degli oggetti contenuti, si pu� indirizzare o alla ricerca di aree con caratteristiche simili,
o alla ricerca delle discontinuit� fra le varie aree. La scelta della caratteristica o
dell'insieme di caratteristiche rispetto a cui effettuare l'analisi dipende dalle propriet�
delle immagini in esame e dalla complessit� globale di elaborazione richiesta.
Per le applicazioni multimediali, la segmentazione ha diversi obiettivi. In
particolare � finalizzata al riconoscimento di oggetti nella scena per la codifica (come
visto per lo standard Mpeg-4), la stima di partizioni della scena per una migliore
codifica, seguire la regione della scena trovata nella sua evoluzione temporale ovvero
trovare i punti di separazione delle sequenze.
Le specifiche caratteristiche che verranno considerate sono:
14
• il tempo che l�algoritmo ha a disposizione per trattare la generica immagine o
a generica sequenza
• nel caso dei video, la quantit� di dati da elaborare che, come gi� accennato,
pu� essere molto elevata
• l�efficienza dell�algoritmo di segmentazione in termini di complessit�
computazionale e di memoria richiesta.
2.2 Strategie di segmentazione
Vediamo ora quali sono i vari punti chiave di un algoritmo di segmentazione e
le varie scelte che si possono fare nella sua stesura.
Fondamentalmente si pu� vedere che lo schema principale della segmentazione
� dato dalla concatenazione di tre principali passi: simplification, estrazione delle
feature, decision.
• Simplification: I dati originali presenti in una immagine o in un video
presentano tante informazioni che, per la maggior parte dei casi, sono irrilevanti e
contribuiscono solo ad appesantire la parte relativa alla codifica. E�, pertanto, utile
eseguire una semplificazione delle informazioni, ad esempio filtrando le immagini, in
modo da eliminare la parte irrilevante. Inoltre, la semplificazione deve portare anche
alla creazione di aree pi� semplici da segmentare. La semplificazione deve ridurre la
complessit� delle textured areas ovvero ridurre i dettagli che siano pi� piccoli di una
data soglia. Filtri usati in questa fase sono elencati in figura due.
• Estrazione delle feature: Lo spazio delle features � importante per la
segmentazione. Infatti, la selezione dei features influenza profondamente la
segmentazione, in quanto in base alle feature si sceglie il criterio da usare per
raggruppare le zone omogenee all�interno della scena. Spesso lo spazio dei campioni
automaticamente fornisce queste informazioni, ad esempio nel caso della
segmentazione per il colore, il valore dei pixels stessi fornisce il features utili alla
segmentazione. Nella maggior parte dei casi, per�, bisogna operare direttamente
15
sull�immagine per estrarre le informazioni volute. Alcune feature caratteristiche sono
elencate in figura 2.1.
Filtri vari Colore Classificazione
-Passa basso Texture Transizione
-Filtri morfologici Moto Omogeneità
-Passa banda Differenza tra frame
Figura 2.1:
Principali passi di un algoritmo di segmentazione
• Decision: Per ottenere infine una partizione adeguata dei dati bisogna
analizzare i features estratti. In questa fase si decide la posizione della soglia che forma
le partizioni, questa soglia separer� le aree segmentate che contengono elementi dalle
caratteristiche comuni. Ad esempio, se devo operare una segmentazione spaziale dove
sono interessato a riconoscere oggetti la decision pu� essere la forma. In genere tre sono
e tecniche usate per definire una partizione: classification, transition-based e
homogeneity-based.
Simplification
Feature
Extraction
Decision
16
Una regione creata da un algoritmo di segmentazione si definisce, pertanto,
come un�insieme di elementi (pixels o immagini, se la segmentazione � spaziale o
temporale) omogenei nello spazio dei features e connessi nel decision-space. Una
regione pu� non avere un significato proprio, nel senso che pu� non rappresentare
niente di riconoscibile, come, al contrario, un oggetto nello spazio 2-D rappresenta
un�entit� che ha un suo significato, � un oggetto definito. In particolare un oggetto lo
potremo vedere come un insieme di regioni.
Esistono tecniche di segmentazione che utilizzano pi� features per effettuare la
partizione. Questo approccio, per�, sottintende la definizione di un criterio che combini
le features tra loro o tecniche di segmentazione a passi, in cui ad ogni passo si cambia
criterio decisionale in base alle features analizzate. Spesso, sullo spazio dei dati e quindi
sulla partizione ottenuta si vuole operare con una certa interattivit�. Questo approccio
porta necessariamente una ulteriore complicazione sullo spazio dei campioni stesso e
sui criteri di decisione da prendere tanto che l�algoritmo che si crea non si potr� pi�
classificare in base allo spazio delle feature usate.
Nei paragrafi successivi analizzeremo alcune tecniche oggi usate per la
segmentazione, prestando attenzione soprattutto al passo decision che, ovviamente, �
quello fondamentale per decidere se il processo di segmentazione � avvenuto o meno
con successo e, soprattutto, se abbiamo ottenuto, partendo dalle feature considerate, il
risultato sperato.
2.3 Stato dell’arte per il processo di segmentazione
Come gi� visto nel paragrafo precedente il passo decision ricopre un ruolo
fondamentale in quanto in questa fase si decide i criterio da usare per ottenere le
partizioni desiderate. Avevamo inoltre visto che esistono fondamentalmente tre tecniche
per definire una partizione: classification, transition-based e homogeneity-based. Di
queste la prima ha poca importanza per i nostri fini, in quanto, � poco utilizzata per la
segmentazione delle immagini o dei filmati.
17
2.3.1 La tecnica transition-based
Lo scopo di questa tecnica � stimare le discontinuit� che si manifestano nel
decision space valutando quelle presenti nello spazio delle features. Per facilitare il
riconoscimento di queste discontinuit� si opera una preventiva elaborazione dei dati per
cercare di metterle in risalto. Questo si fa semplicemente operando un filtraggio sui dati,
filtraggio che presenter� in uscita valori elevati proprio in corrispondenza delle
transizioni e valori pi� bassi nelle zone pi� omogenee della scena.
Quando sono state messe in risalto le zone di transizione si pu� procedere alla
partizione vera e propria. In questa fase bisogna prestare attenzione, infatti, i valori
trovati non sono necessariamente quelli voluti anche se hanno buone probabilit� per
diventarlo. Questo problema nasce dal fatto che nella fase di �filtraggio� anche
transizioni interne alla scena, come nel caso di passaggi tra zone omogenee all�interno
della scena stessa, vengono prese in considerazione e i contorni di queste zone sono
difficilmente rilevabili.
Le informazioni ottenute dal filtraggio vengono a questo punto elaborate. Si
procede ad una binarizzazione dei dati ottenuti per ridurre ulteriormente l�incertezza
sulla scelta della posizione di transizione e se necessario si opera anche un primo
sfoltimento dei dati binarizzati per avere un�idea della zona partizionata. Le tecniche di
sfoltimento devono essere tali da non far perdere la connessione tra le zone che sono
state partizionare. Questa � una caratteristica fondamentale per le segmentazioni spaziali
e spazio-temporali in cui la transizione stimata pu� non essere connessa e rappresenta il
contorno di un oggetto reale della scena. Questo problema � risolto usando tecniche di
riempimento dei gap per connettere i contorni dei segmenti ottenuti e ottenere la
partizione finale. Il problema della connessione, tanto importante per la segmentazione
spaziale, non si sente in quella temporale, in quanto, la trasmissione dei frames e
definita da un tempo e quindi non si richiede una connessione particolare.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
