Codifica a descrittori multipli per comunicazioni multimediali

Sistema di codifica a descrittori multipli per comunicazioni multimediali

Giancarlo Ippolito

Tesi di Laurea Magistrale in Ingegneria Elettronica

Relatore Prof. Marco Carli

Co-relatore Ing. Federica Battisti

Università degli studi Roma TRE

Maggio 2011

Ringraziamenti

Dedico questa tesi ai miei genitori ai quali dico GRAZIE per primo. Forse per loro non basta un solo grazie perchè dovrei dire grazie per la pazienza che hanno avuto nei miei confronti, grazie per l'aiuto morale che mi hanno dato quando spesse volte non credevo più in me, grazie per l'aiuto economico che mi hanno dato per poter svolgere la mia carriera universitaria. L'avevo detto, un solo grazie non basta per i miei genitori che hanno creduto in me più di quanto forse non lo abbia fatto io, fornendomi la fiducia che alle volte svaniva in me perchè magari un esame andava male. In un percorso universitario penso sia importante avere qualcuno con cui condividere gioie e soprattutto dolori, io ho avuto la fortuna di avere due magnifici genitori che hanno condiviso tutto, forse alle volte immedesimandosi pure troppo nei miei panni ma è proprio per questo che riuscivano a capirmi e ad aiutarmi nel migliore dei modi.

Un GRAZIE anche al Prof. Carli e alla Prof.ssa Battisti che mi hanno seguito nello svolgimento della tesi in questi mesi aiutandomi a capire gli errori che commettevo e ad indirizzarmi nella retta via al fine di portare in commissione una tesi coi fiocchi.

Ehi! non posso poi non dire GRAZIE ai miei amici e colleghi universitari con i quali ho passato questi anni assieme studiando e divertendomi anche: speriamo di non dimenticare nessuno :-) : Giuseppe, Paola, Sara, Alessio I, Alessio B, Alessio R, Marcotto, Mitico, Federico, Roberto, Gaetano, Livia, Alessia, Divinia....tutta la compagnia della biblio del Murialdo.

A tutti voi, GRAZIE.

i

Indice

• Ringraziamenti i
• Indice ii
• Premessa 1
• Introduzione 5
• Abstract 8
• 1 Introduzione ai descrittori multipli 11
• 1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
• 1.2 Cenni storici sui descrittori multipli . . . . . . . . . . . . . . . 11
• 1.3 Introduzione alla MDC . . . . . . . . . . . . . . . . . . . . . . 13
• 1.4 Codifica progressiva vs MDC . . . . . . . . . . . . . . . . . . . 14
• 1.4.1 Incremento della qualità legata ai descrittori . . . . . . 15
• 1.5 Modello a due descrittori . . . . . . . . . . . . . . . . . . . . . 17
• 1.6 Applicazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
• 1.6.1 Applicazione in Internet . . . . . . . . . . . . . . . . . 18
• 1.6.2 Per cosa usare un MD . . . . . . . . . . . . . . . . . . 19
• 1.7 Descrittori multipli per marchiatura . . . . . . . . . . . . . . . 19
• 1.8 Obiettivo della tesi . . . . . . . . . . . . . . . . . . . . . . . . 21
• 2 Sistema di marchiatura a descrittori multipli 23
• 2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
• 2.2 Schema di marchiatura proposto . . . . . . . . . . . . . . . . . 24
• 2.3 Analisi del descrittore marchiato . . . . . . . . . . . . . . . . . 26
• 2.4 Schema di detection . . . . . . . . . . . . . . . . . . . . . . . . 27

ii iii INDICE

• 3 Decisione della soglia 30
• 3.1 Problema della decisione . . . . . . . . . . . . . . . . . . . . . 30
• 3.2 Errori di prima e seconda specie . . . . . . . . . . . . . . . . . 32
• 3.3 Calcolo della soglia con il criterio di Neyman-Pearson . . . . . 33
• 3.4 Verifica ipotesi binaria: presenza assenza del marchio . . . . . 35
• 4 Detection a un descrittore 40
• 4.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
• 4.2 La soglia di decisione . . . . . . . . . . . . . . . . . . . . . . . 41
• ρ 4.3 Il picco di correlazione . . . . . . . . . . . . . . . . . . . . 46
• k 4.4 Detection del marchio . . . . . . . . . . . . . . . . . . . . . . 48
• 4.5 Analisi della qualità . . . . . . . . . . . . . . . . . . . . . . . . 52
• 4.5.1 Analisi del PSNR . . . . . . . . . . . . . . . . . . . . . 54
• 4.5.2 Analisi del WPSNR . . . . . . . . . . . . . . . . . . . . 58
• 4.5.3 Analisi del PSNR-HVS-M . . . . . . . . . . . . . . . . 62
• 4.6 Analisi della probabilità di errore . . . . . . . . . . . . . . . . 65
• 4.6.1 Probabilità di mancato allarme . . . . . . . . . . . . . 66
• 4.6.2 Probabilità di falso positivo . . . . . . . . . . . . . . . 67
• 4.6.3 Probabilità di errore . . . . . . . . . . . . . . . . . . . 69
• 5 Detection a due descrittori 71
• 5.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
• 5.2 Descrittore somma . . . . . . . . . . . . . . . . . . . . . . . . 72
• 5.3 La soglia di decisione . . . . . . . . . . . . . . . . . . . . . . . 73
• ρ 5.4 Il picco di correlazione . . . . . . . . . . . . . . . . . . . . . 75
• k 5.5 Detection del marchio . . . . . . . . . . . . . . . . . . . . . 77
• 5.5.1 Risultati sperimentali . . . . . . . . . . . . . . . . . . . 83
• 5.6 Miglioramento della detection . . . . . . . . . . . . . . . . . . 90
• 5.6.1 Descrittore a doppia somma . . . . . . . . . . . . . . . 90
• 5.6.2 Detection del marchio . . . . . . . . . . . . . . . . . . 91
• 5.6.3 Risultati sperimentali . . . . . . . . . . . . . . . . . . . 94
• 5.7 Analisi della qualità . . . . . . . . . . . . . . . . . . . . . . . . 101
• 5.8 Analisi della probabilità d'errore . . . . . . . . . . . . . . . . . 105
• 5.8.1 Probabilità di mancato allarme . . . . . . . . . . . . . 106
• 5.8.2 Probabilità di falso positivo . . . . . . . . . . . . . . . 107
• 5.8.3 Probabilità di errore . . . . . . . . . . . . . . . . . . . 108

iv INDICE

• 6 Detection in presenza di attacco 110
• 6.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
• 6.2 Attacchi Standard . . . . . . . . . . . . . . . . . . . . . . . . . 111
• 6.3 Attacchi proposti . . . . . . . . . . . . . . . . . . . . . . . . . 112
• 6.4 Metodo di Attacco . . . . . . . . . . . . . . . . . . . . . . . . 114
• 6.5 Attacco JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
• 6.6 Attacco Blurring . . . . . . . . . . . . . . . . . . . . . . . . . 115
• 6.7 Attacco Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
• Conclusioni 120
• A Cenni sulla marchiatura digitale 123
• A.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
• A.2 La marchiatura . . . . . . . . . . . . . . . . . . . . . . . . . . 124
• A.2.1 Autenticazione dei dati . . . . . . . . . . . . . . . . . . 127
• A.2.2 Copia non autorizzata . . . . . . . . . . . . . . . . . . 128
• A.2.3 Dimostrazione di proprietà . . . . . . . . . . . . . . . . 128
• A.2.4 Identificazione di appropriazione indebita . . . . . . . . 128
• A.3 Proprietà di un marchio . . . . . . . . . . . . . . . . . . . . . 128
• A.4 Schema di principio di marchiatura e detection . . . . . . . . . 130
• A.5 Principali tecniche di marchiatura . . . . . . . . . . . . . . . . 131
• A.5.1 Metodo LSB . . . . . . . . . . . . . . . . . . . . . . . . 132
• A.5.2 Metodo Spread Spectrum . . . . . . . . . . . . . . . . 132
• A.5.3 Metodo DCT . . . . . . . . . . . . . . . . . . . . . . . 132
• A.5.4 Metodo DFT . . . . . . . . . . . . . . . . . . . . . . . 133
• A.5.5 Metodo Patchwork . . . . . . . . . . . . . . . . . . . . 133
• Indice analitico 134
• Elenco delle figure 135
• Bibliografia 139

Premessa

In questa premessa si vuole dare al lettore una panoramica di come è stata svolta la tesi, fornendo informazioni sul software usato e su come sono stati elaborati i grafici presenti nei capitoli successivi. Lo studio della detection del marchio in immagini digitali è stato eseguito usando il linguaggio di programmazione Matlab con il quale sono stati sviluppati i codici simulatori del sistema di marchiatura e detection proposti nel Capitolo 2 sotto forma di schemi e i codici per disegnare i diversi grafici. I test svolti durante lo svolgimento della tesi sono stati condotti su una serie di dieci immagini su scala di grigi di dimensioni 512X512 pixels scelte dal sito internet [1], solitamente utilizzate nell'ambito del digital watermaking e dell'elaborazione dell'immagine e riportate in Figura 4.17.

Al fine di verificare l'efficacia del sistema di marchiatura e di detection sono state svolte dapprima una serie di prove di marchiatura e detection su una singola immagine al fine di verificare il corretto funzionamento dell'algoritmo poi, verificato quanto detto si è svolto uno studio di livello statistico. Il marchio inserito in tutte le immagini è un marchio a distribuzione gaussiana generato random attraverso la funzione rand di Matlab usando un certo seme seed. Lo stesso procedimento è stato eseguito per gli algoritmi relativi all'analisi della qualità e della probabilità d'errore, verificandone così l'effettivo funzionamento.

Passo successivo alla verifica della bontà degli algoritmi è stato quello di avviare uno studio a livello probabilistico infatti, poichè la tesi si basa sull'osservazione della presenza del marchio all'interno di una immagine attraverso uno studio probabilistico, sono necessarie diverse osservazioni dei campioni, dove per campione s'intende il descrittore marchiato. È chiaro che maggiore è il numero di osservazioni effettuate e migliore è lo studio statistico della detection del marchio tuttavia, in questo lavoro di tesi il numero di osservazioni effettuate si limita al valore 100. La causa della limitazione di questo valore è solo di tipo computazionale in quanto i pc usati alla realizzazione della tesi impiegavano un tempo lungo all'elaborazione di un numero elevato di osservazioni, tuttavia è sufficiente allo scopo proposto dalla tesi. Ciò vuol dire che ognuna della dieci immagini è stata marchiata 100 volte con un marchio generato da una diversa chiave e, per ognuna di quest volte è stata verificata la detection. I grafici risultanti dall'analisi predetta riportano il valore medio della media delle 100 osservazioni eseguite su ogni immagine. Lo studio suddetto vale anche per i grafici della probabilità di errore ma non per quelli relativi alle metriche di qualità, i quali hanno richiesto elevate risorse computazionali e per cui si è scelto di graficare solamente la curva media derivante dalla media di 50 osservazioni su dieci immagini su di un intervallo ristretto di SN R e potenza del marchio α. I grafici ottenuti, rispetto agli altri, presentano dunque andamenti rettilinei a tratti proprio per la scelta di osservare l'andamento su un numero di punti inferiori della variabile indipendente. Tale scelta, forzata dal punto di vista computazionale, comporta un certo calo di accuratezza nei valori assunti dalla curva, tuttavia in questa tesi l'elemento principale su cui si è interessati non è tanto il valore preciso assunto qualità ma quanto la detection del marchio, motivo per cui dai grafici della qualità ci serve capire come essa si comporta genericamente all'aumentare delle variabili indipendenti e quale cambiamento subisce quando i descrittori marchiati sono due. Sempre per quanto riguarda l'analisi della qualità delle immagini è da aggiungere che le osservazioni sono state effettuate su valori dopo la conversione mat2gray di Matlab.

Nella fase di attacco sono stati scelti alcuni tra gli attacchi standard noti in letteratura e sono stati applicati alle immagini seguendo lo stesso ragionamento visto per la detection. L'attacco è stato applicato 100 volte per ognuna delle dieci immagini marchiate ogni volta con marchio differente. Il risultato graficato è il rappresentante della media dei valori ottenuti dalle medie dei 100 risultati.

Per ciò che concerne la variabile indipendente SN R, tutti i grafici in funzione di essa riportano valori assunti nell'intervallo di SN R compreso tra [−100 100] dB; è da tenere in considerazione che ad oggi con i canali trasmissivi conosciuti ed usati è impossibile ottenere dei livelli di rapporto segnale rumore bassi oltre un certo valore, tuttavia la scelta di questo intervallo è stata presa in considerazione per evidenziare che anche per alcuni bassi valori del SN R si riesce a rilevare il marchio senza alcun problema. L'analisi della detection dunque non tiene conto del degradamento della qualità dell'immagine, ma offre una osservazione anche per valori limiti nei quali sicuramente non ci si arriverà mai nella realtà, ma che sono comunque utili ai fini dello studio del miglioramento della detection.

È opportuno precisare inoltre che tutti i valori ottenuti sperimentalmente non sono stati normalizzati a 1 per cui quando si parla ad esempio del grafico del picco di correlazione ci si riferisce ad una curva rappresentante dei valori che se normalizzata rispetto al suo massimo ritorna la curva della correlazione. Tale curva da ora in poi prenderà il nome di picco di correlazione ρ e verrà indica con la lettere greca k.

1 2 INDICE

1 20 valori da dB a dB −60 60

2 20 valori da a . −1 1

3 L'operazione converte i valori dell'immagini in intensità i cui nuovi valori sono compresi nell'intervallo [0, 1]

4 L'intervallo contiene 100 valori di SN R.

3 INDICE

4 INDICE (a) (b)

(c) (d)

(e) (f)

(g) (h)

(i) (j)

Figura 1: Immagini Test

Introduzione

La codifica a descrittori multipli (MDC) è una tecnica che permette di scindere un segnale, nel nostro caso un'immagine, in più parti comunemente dette descrittori. Queste, vengono create in modo opportuno affinché risultino indipendenti tra di loro al fine di poter ricostruire l'immagine al ricevitore con una certa qualità Qi sfruttando anche solo uno di essi. Solitamente, i sistemi MDC risultano equilibrati in quanto ogni descrittore contribuisce a portare la stessa quantità di qualità. La teoria dei descrittori multipli dimostra che la qualità con la quale è possibile ricostruire l'immagine è direttamente proporzionale al numero di descrittori ricevuti a destinazione, infatti maggiore è il loro numero è migliore è la ricostruzione dell'immagine a lato destinatario. Teoricamente, nel caso di canale non rumoroso, privo di errori e ideale, la qualità ricostruita in presenza di tutti i descrittori risulta essere proprio la qualità di partenza dell'immagine. Purtroppo, l'ipotesi di canale ideale non è mai vera, motivo per il quale la qualità non è mai pari a quella di partenza.

Negli anni, la tecnica di codifica a descrittori multipli è stata usata, e tutt'ora è oggetto di ricerca, anche come mezzo per rendere più efficace e robusta la marchiatura e la detection di un segnale al fine di contrastare i sempre più probabili e frequenti attacchi illeciti da parte di persone malintenzionate (questioni di copyright, hacker, etc). L'idea sulla quale la tecnica di marchiatura a descrittori multipli (MDW) si basa è quella di porre il marchio su uno o più descrittori e quindi verificare a lato destinatario se è presente o meno in essi senza l'ausilio dell'immagine originale (oblivious watermark) che in altri sistemi invece è necessaria. Per avere un'idea su un sistema MDW si può fare riferimento a [2]. Sul lato ricevitore la presenza del marchio nel descrittore viene rilevata sfruttando delle statistiche probabilistiche comparate poi con una certa soglia calcolata opportunamente.

Si supponga di aver diviso la sorgente in N descrittori e che solo nel primo di essi sia stato posto il marchio. Al lato ricevitore il marchio può essere rilevato attraverso uno studio probabilistico il quale porta ad avere una certa probabilità di detection P con annesse probabilità di falso e di mancato allarme secondo quanto la teoria della decisione insegna. Se lo stesso marchio è inserito su N descrittori, ognuno di essi avrà dunque una singola probabilità di detection P. Si può notare allora la similitudine che occorre tra un sistema MDC ed un MDW, nel quale la probabilità di detection può essere pensata come la qualità che il singolo descrittore i-esimo porta per la detection del marchio. Detta similitudine porta allora alla domanda seguente:

Poiché la teoria dei MDC dice che la qualità migliora e aumenta col numero di descrittori ricevuti sul lato destinatario, si può affermare che all'aumentare dei descrittori marchiati ricevuti, la probabilità di rilevare il marchio aumenta?

A questa domanda cercherà di rispondere il lavoro di tesi svolto in questi mesi. La tesi si articolerà nel modo seguente:

• Nel primo capitolo s'introdurrà il concetto di descrittore multiplo mettendolo a confronto con le tecniche oggi largamente usate, facendo risaltare il fatto che la qualità aumenta con il numero di descrittori e che quindi può esserci analogia con la probabilità di detection di un marchio al variare dei descrittori ricevuti.
• Nel secondo capitolo si darà una panoramica del sistema di marchiatura e detection a descrittori multipli proposto per lo scopo della tesi.
• Nel terzo capitolo si studierà in approfondito la soglia di decisione da applicare come regola di decisione della presenza o assenza del marchio.
• Nel quarto capitolo si studierà la detection del marchio nel caso di ricezione di un solo descrittore mettendo così in evidenza i grafici opportuni della soglia e del picco di correlazione del descrittore marchiato, i grafici della qualità e quelli relativi alla probabilità d'errore.
• Nel capitolo 5 si osserverà il caso in cui si ricevano due descrittori marchiati evidenziando la possibilità di miglioramento della detection, la qualità