6
Il lavoro di Tesi è organizzato secondo i seguenti capitoli:
• Metodi Statistici ed Entropici Applicati all'Elaborazione delle Immagini.
Vengono illustrate le potenzialità e gli innumerevoli campi di applicazione
legate all'Entropia dell'Informazione applicata all'Elaborazione delle
Immagini nei suoi vari aspetti e forme. La giusta evidenza viene data ai
risultati più significativi presenti in letteratura grazie ad un breve survey che
ne illustra l'evoluzione storica/scientifica. Particolare enfasi e merito
vengono riconosciuti al Principio della Max Entropia di E.T. Jaynes e
all'originario concetto di Entropia dovuto a C. Shannon che, inizialmente
utilizzati in ambiti totalmente differenti quali quello della Termodinamica e
della Teoria dell'Informazione, assumono oggi notevole rilevanza grazie alle
numerose applicazioni in Computer Graphics (si notino ad esempio i lavori
di D. Mumford della Stanford University);
• Analisi Automatica di Pattern/Texture Visuali. Anche in questo caso dopo
una breve panoramica storico-scientifica volta a focalizzare gli obiettivi
specifici e le problematiche di base del settore, vengono brevemente illustrati
i principali risultati presenti in letteratura; in particolare si approfondiscono i
risultati del gruppo di ricerca facente capo a J. De Bonet, Learning & Vision
Group - Cambridge che ha condotto degli studi sull'Analisi/Sintesi di texture
utilizzando un approccio multirisoluzione non parametrico utilizzato di
recente anche nella discriminazione di immagini satellitari di tipo SAR.
7
Il materiale presente in questo primi capitoli rappresenta la base teorica e
scientifica, il punto di partenza dal quale si sono poi condotti gli studi e le ricerche
ulteriori che hanno portato ai risultati descritti nei capitoli successivi della Tesi.
• Analisi e Sintesi di Tessiture. In questo importante ambito teorico/applicativo
sono in fase avanzata di studio e di implementazione alcune tecniche di
sintesi che, utilizzando delle procedure di clusterizzazione ed un approccio
multirisoluzione permettono di ottenere pattern generati dalla stessa legge
stocastica di base. Inoltre la metodologia seguita ha permesso di realizzare
significativi improvement, dal punto di vista computazionale rispetto ai
metodi precedenti. Si prefigura inoltre la possibilità di applicare tali tecniche
al problema della classificazione di tessiture e nello specifico ambito
dell'analisi e sintesi di linguaggi naturali, dove in particolare è possibile
attraverso opportuni algoritmi di apprendimento riuscire a selezionare il
migliore insieme di feature necessario per riuscire a riprodurre le complesse
leggi statistiche che fanno capo al fenomeno stesso;
• Entropia e Mappe di Salienza. In questo capitolo vengono illustrati i risultati
ottenuti insieme a G. Gallo, dove analizzando l'Entropia di Shannon delle
distribuzioni di probabilità indotte dagli istogrammi di una serie ben
specifica di feature relative ad un determinato training set di esempi positivi,
si è costruita una mappa di salienza in grado di valutare la probabilità che un
dato pixel in una data scena appartenesse o meno alla classe di oggetti in
8
questione. Le potenzialità effettive del metodo proposto vengono validate da
un'esaustiva serie di esperimenti. Sono inoltre allo studio diverse estensioni
a problematiche più complesse;
• Watermarking. Questo capitolo è interamente dedicato alla discussione di un
nuovo algoritmo di watermarking su immagini digitali. Tale algoritmo,
tuttora in fase di studio e di ulteriore estensione, permette l'inserimento di un
marchio digitale, attraverso un'opportuna tecnica che manipola i pixel di un
immagine agendo nello spazio dei colori della Color Opponency. In
particolare vengono individuate delle regioni, vere e proprie sfere, associate
ai singoli pixel di un'immagine, dove è possibile eseguire degli opportuni
spostamenti impercettibili. Il metodo proposto oltre ad essere robusto
rispetto alle più comuni operazioni di image processing viene analizzato
anche attraverso una rigorosa analisi statistico-teorica che ne evidenzia la
resistenza rispetto ad alcuni attacchi intenzionali volti alla rimozione del
marchio stesso. Anche in questo caso l'analisi e la descrizione dell'algoritmo
è accompagnata da una serie di risultati sperimentali che ne fanno apprezzare
la bontà dello stesso.
Appendice:
• Viene descritto un algoritmo per la ricerca della Mediana Approssimata la cui
analisi probabilistica è stata realizzata insieme con il Prof. Micha Hofri (WPI
University); l'algoritmo in questione, competitivo dal punto di vista della
complessità computazionale, si presta bene per la realizzazione di un analogo
filtro di smoothing.
9
Note Bibliografiche
Il materiale presente nel Capitolo 3 è largamente tratto da un articolo
pubblicato sui Proceedings di Workshop on Texture Analysis in Machine Vision,
TEXTURE'99, Oulu, Finland, pp.149-156, 1999. Analogamente per il contenuto
specifico del Capitolo 4, interamente tratto da un lavoro apparso sui Proceedings
di European Congress on Intelligent Techniques and Soft Computing, EUFIT'98,
Aachen, Germany, Vol.2, pp.1375-1380, 1998. Entrambi i lavori sono stati
realizzati insieme con Giovanni Gallo.
Il Capitolo 5 fa invece parte di un filone di ricerca condotto insieme con Dario
Catalano e Giovanni Gallo dell'Università di Catania e con Rosario Gennaro
dell'IBM T.J. Watson Research Center di New York, tuttora in fase di ulteriore
sviluppo; alcuni dei risultati presentati sono stati presentati sui Proceedings di 3-
rd Workshop on Information Hiding, Dresden 1999, altri invece appariranno sui
Proceedings di IST/SPIE Electronic Imaging 2000.
L'Appendice A è in parte tratta da un lavoro realizzato con Dario Catalano,
Gianluca Cincotti e Domenico Cantone dell'Università di Catania insieme con
10
Micha Hofri della WPI University. I risultati di tale ricerca sono stati presentati
all'annuale Meeting di Average-Case on the Analysis of Algorithms, tenutosi a
Barcellona, Spagna, nel Giugno 1999. Una versione estesa di tale articolo apparirà
sui Proceedings di CIAC 2000, Roma.
Si ringraziano i coautori per aver acconsentito alla parziale riproduzione di tali
lavori in questa Tesi.
11
Non è perchè le cose sono
difficili che non osiamo,
ma è perchè non osiamo
che sono difficili.
Seneca
12
Capitolo 1
Entropia e Distribuzioni di Gibbs
nell'Elaborazione delle Immagini
In questo capitolo verranno sinteticamente illustrati i concetti di base nonché
l'evoluzione storica delle linee di ricerca facenti riferimento alla cosiddetta
Information Entropy e alle sue applicazioni nella risoluzione di problemi di
inferenza statistica nell'elaborazione delle immagini. Saranno anche introdotti i
dettagli matematici riguardanti i cosiddetti Markov Random Field (MRF) e il
relativo campionamento di Gibbs (Gibbs sampling). In particolare, attraverso un
excursus storico dei principali risultati presenti in letteratura, partendo dallo
storico lavoro di C. Shannon del 1948 e proseguendo poi con Jaynes (1957) e con
Geman & Geman (1984), verrà illustrato l'iter metodologico-scientifico che si è
13
affermato nel corso degli anni e che sta alla base di diversi risultati teorico-
applicativi ottenuti nell'ambito dell'analisi/sintesi di tessiture, nella costruzione di
mappe di salienza e nell'image restoration.
1. Introduzione
Dopo ormai quasi cinquant'anni dalla sua prima apparizione in letteratura, il
concetto di entropia è oggi universalmente accettato: diversi risultati vengono
continuamente tirati fuori e proposti negli ambiti applicativi più svariati ma
facenti comunque capo all'antica idea di misura dell'informazione. Come già
accennato il concetto di entropia fu introdotto nel 1948 da Claude Shannon, in
uno storico articolo che è alla base di tutta la moderna Teoria dell'Informazione.
Non meno importante fu il contributo di E.T. Jaynes, che nel 1957, introducendo
il Principio della Massima Entropia influenzò in maniera decisa, in un certo senso
rivoluzionandolo del tutto, l'approccio fino ad allora seguito nella risoluzione di
problematiche di inferenza statistica. L'entropia dell'informazione, come noto,
misura l'incertezza di una distribuzione di probabilità; l'evidenza sperimentale ne
ha messo in luce nel corso degli anni l'utilità pratica nella risoluzione dei
cosiddetti problemi ill-conditioned, dove cioè la mancanza di informazioni e/o di
dati specifici riguardo al problema in oggetto, richiede l'assunzione di ipotesi
quanto più generali possibili in riferimento ai parametri del sistema oggetto di
studio. Ecco spiegato il motivo per cui anche nell'Elaborazione delle Immagini,
l'entropia è risultata essere utile, come vedremo, in svariate applicazioni il cui
obiettivo specifico è la costruzione di modelli di probabilità basati su assunzioni
di tipo statistico riguardanti in particolare la riproduzione stocastica di opportune
14
caratteristiche (o features) di immagini digitali (siano esse legate a scene reali o
artificiali).
Nel 1984 S.Geman e D.Geman pubblicarono un articolo per certi versi storico,
dove attraverso la rielaborazione di differenti concetti teorici già noti nel campo
della Fisica Statistica, introdussero nuove tecniche e metodologie di lavoro
strettamente legate con le distribuzioni di Gibbs e con i Markov Random Field
(MRF). In particolare grazie a tali tecniche è oggi possibile stimare, attraverso un
opportuno algoritmo di campionamento, detto Gibbs Sampling, la legge di
distribuzione sottesa all'immagine oggetto di studio anche se il relativo modello
probabilistico è troppo complesso da manipolare analiticamente. Seguendo la
naturale evoluzione delle tecniche e dei metodi applicativi che si sono succeduti
nel corso degli anni e descrivendone le idee di base dei differenti filoni di ricerca
ci si propone quindi di analizzare il percorso culturale-scientifico che partendo da
C. Shannon ha trovato in Jaynes prima e più tardi in Geman e Geman, i padri
fondatori dei cosiddetti metodi entropici nell'Elaborazione delle Immagini. In
particolare si cercherà di evidenziare come tali risultati ottenuti in ambiti spesso
totalmente differenti e con obiettivi specifici anch'essi completamente
indipendenti siano invece inevitabilmente interconnessi tra loro e come tali
rappresentano la base scientifica delle moderne metodologie di ricerca oggi più in
voga.
2. L'Entropia di Shannon come Misura della Casualità
Il concetto di entropia dell'Informazione fu introdotto per la prima volta nel
1948 (Shannon - 1948) ma in ogni caso non si trattava di un'idea completamente
15
nuova: un analogo concetto era già conosciuto in termodinamica e in meccanica
statistica. In particolare Clausius e Boltzmann diedero la prima espressione
funzionale per l'entropia come misura del grado di disordine esistente in un
sistema termodinamico (Zemansky - 1981).
A Shannon va però il merito di aver introdotto in maniera formale e precisa il
concetto di entropia a seguito dei suoi studi legati al problema della
comunicazione di segnali su un canale in presenza di rumore. In particolare i suoi
studi si svilupparono rapidamente dando vita a due distinte linee di ricerca:
- La Teoria dell'Informazione (Information Theory): una teoria probabilistica
volta a studiare appunto le caratteristiche statistiche dei sistemi di
comunicazione;
- La Teoria della Codifica (Coding Theory): un insieme di metodi algebrici
utili a generare codifiche efficienti per diversi problemi di comunicazione. Un
noto algoritmo è per esempio quello di Huffmann dove l'entropia fornisce
una stima della lunghezza media dell'ottimale codifica iniettiva (Goldie e
Pinch - 1991; Welsh - 1988).
Ma le applicazioni dell'universale concetto di entropia sono innumerevoli e
hanno a che fare con gli ambiti applicativi più svariati. Per esempio è possibile
applicare l'entropia allo studio di criptosistemi: l'entropia condizionale è utilizzata
per misurare quanta informazione è racchiusa in un qualsiasi criptotesto in
relazione alla chiave segreta che lo ha generato (Brassard e Bratley - 1988). Altri
campi di applicazione sono l'economia, la biologia, la sociologia, lo studio dei
sistemi dinamici, la teoria degli algoritmi, oltre che la teoria dell'informazione e
16
della codifica e l'inferenza statistica. Per maggiori dettagli si veda l'esaustivo sito
Web (Hillmann - 1998).
2.1 Concetti di base
Ancora oggi l'originale articolo di Shannon è per certi versi la migliore
introduzione al moderno concetto di entropia. Rimandiamo quindi a (Shannon -
1948) per la descrizione analitica delle problematiche teorico-matematiche,
limitandoci ad elencare in maniera sintetica alcuni concetti di base.
Supponiamo di avere una variabile casuale X definita su un insieme di eventi
mutuamente esclusivi X={x1, x2, …, xn} in accordo con la distribuzione di
probabilità p(X) e tale che Si p(xi) = 1.
Se consideriamo questa variabile casuale come una sorgente di informazione,
diventa lecito cercare di misurarne in maniera consistente il grado di incertezza
associato ad ogni singolo evento. In questi casi infatti è disponibile solo la
cosiddetta distribuzione di probabilità a priori, che se da un lato consente di tirare
fuori comunque degli indici statistici di notevole rilevanza statistica (Valor medio,
Scarto Quadratico Medio, ecc.) dall'altro invece non permette di stimare in
termini probabilistici la casualità associata al fenomeno in oggetto nella sua
globalità. Per stimare in maniera numerica il grado di incertezza con un data
funzione H(X), quest'ultima deve soddisfare le seguenti proprietà di base:
1. La funzione H(X) deve esistere: deve essere cioè possibile associare un
legame di tipo numerico tra l'incertezza di una distribuzione di probabilità
ed i numeri reali;
17
2. H(X) ha una dipendenza funzionale continua su p(X): ciò significa che a
piccole variazioni della p(X) corrispondono inevitabilmente altrettante
piccole variazioni nella misura di incertezza associata;
3. Se p(xi) = 1/n , i=1, 2, …, n allora H(X) non può che essere una funzione
monotona crescente in n. In altre parole al crescere del numero di eventi, se
questi sono equiprobabili, l'incertezza associata è maggiore;
4. H(X) gode della proprietà additiva: se esiste più di un modo per calcolarne il
suo valore questo deve comunque essere lo stesso in ogni caso. Se per
esempio un evento può essere visto come l'unione di due o più distribuzioni
di probabilità il valore della funzione H per così dire globale deve essere
uguale alla media pesata dei valori assunti dalla H nei singoli casi.
E' possibile dimostrare la validità del seguente teorema dovuto a Shannon:
Teorema 2.1 L'unica funzione H che soddisfa le proprietà 1-4 di cui sopra, è
della forma:
dove k è una costante positiva (solitamente posta ad 1).
La funzione H è detta entropia, entropia di Shannon o meglio entropia
dell'informazione. Ciò per distinguerla dall'analoga espressione funzionale legata
all'entropia di un sistema termodinamico; l'entropia dell'informazione è una
proprietà associata ad una qualunque distribuzione di probabilità mentre la
) 1 ( )(log)()(
1
∑
=
−=
n
i
ii xpxpkXH
18
cosiddetta entropia sperimentale usata in termodinamica è invece una proprietà
legata a vere e proprie quantità fisiche (volume, pressione, temperatura, ecc.). Di
seguito con il termine entropia ci riferiremo all'entropia dell'informazione.
Quando nell'espressione (1) p(xi)=0 per qualche i, il relativo termine all'interno
della sommatoria è ovviamente non definito. Dato però che limx�0 x log x = 0 si
può assumere in maniera naturale che il relativo termine sia nullo o
equivalentemente considerare solo i termini diversi da zero. E' possibile
generalizzare la funzione entropia definendola sulle cosiddette sorgenti di
informazione continue. In questo caso la distribuzione della variabile casuale X è
espressa in termini di densità di probabilità (probability density function o p.d.f.)
supposta continua per semplicità di notazione.
L'espressione funzionale per la funzione entropia diventa in questo caso:
(2) )(log)()( ∫
+∞
∞−
−= dxxpxpkXH
La funzione entropia gode di alcune interessanti proprietà:
1. H(X) � 0 ed inoltre H(X)=0 se e solo se p(xi)=1 per qualche i ed
ovviamente p(xj)=0 " i� j. Si tratta cioè di un'effettiva e concreta misura
dell'incertezza nascosta nei dati a disposizione;
2. H(X) assume il suo valore massimo pari a log n quando p(xi) = 1/n," i = 1,
2, …, n. Ciò sta ad indicare che la massima incertezza si presenta quando
tutti gli eventi sono equiprobabili;
19
3. Se X e Y sono due variabili casuali allora H(X,Y) � H(X) + H(Y) dove
H(X,Y) denota l'entropia associata alla distribuzione di probabilità
congiunta di X e Y. L'eguaglianza sussiste se e solo se X e Y sono tra di loro
indipendenti;
4. Se X e Y sono due variabili casuali è possibile considerare la distribuzione
di probabilità condizionale data da (X|Y); in questo caso si definisce
entropia condizionale H(X|Y) la funzione:
L'entropia condizionale è quindi la media pesata con i valori p(y)
dell'entropie H(X|y) su tutti i possibili y.
5. H(X,Y)= H(X|Y) + H(Y). Si noti che se X e Y sono tra loro indipendenti
allora H(X|Y)=H(X).
∑∑−=
x y
yxpyxpypYXH (3) )|(log)|()()|(
Fig. 1: a) Ideogramma cinese per l'entropia b) L'entropia di due eventi con
probabilità p e (1-p) descritta al variare di p.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
