Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
UNIVERSITÀ
DEGLI STUDI DI TRIESTE
Corso di Elaborazione Elettronica di Immagini
ELABORAZIONE E CODIFICA
DI IMMAGINI BITONALI
Gabriele Guarnieri
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Sommario
Quantizzazione di immagini
1
Dithering
2
Ordered dithering
3
Noise shaping
Codifica di immagini bitonali
4
Codifica CCITT Fax
5
Codifica JBIG2
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Metodo
Proprietà
Esempio
Dithering
Una quantizzazione “semplice” introduce un errore sistematico
molto visibile (falsi contorni)
Per rendere meno visibile l’errore, è possibile introdurre una
componente casuale nella quantizzazione → Dithering
Ipotesi: un valore x ∈ R deve essere quantizzato per produrre un
valore y ∈ Z. Supponiamo per semplicità che x ∈ [0, 1]
Procedimento: calcoliamo y con la regola
{︃
y=
0
1
con probabilità 1 − x
con probabilità x
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Metodo
Proprietà
Esempio
Esempio
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Metodo
Proprietà
Esempio
Proprietà
Media e varianza:
E {y |x } = x
E {(y − x )2 |x } = x (1 − x )
Si dimostra che il metodo descritto equivale a
Sommare ad x un rumore bianco n uniformemente distribuito
nell’intervallo [−1/2, 1/2]
Arrotondare il risultato all’intero più vicino
Oppure, in alternativa
Sommare ad x un rumore bianco n uniformemente distribuito
nell’intervallo [0, 1]
Troncare il risultato all’intero inferiore
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Metodo
Proprietà
Esempio
Proprietà
Supponiamo che x sia uniformemente distribuito nell’intervallo
[0, 1] e mediamo rispetto ad x
⇒ Il rumore di quantizzazione y − x ha una densità di probabilità
triangolare nell’intervallo [−1, 1], con varianza 1/6
Il dithering aumenta la varianza del rumore di quantizzazione,
tuttavia la sua natura casuale lo rende in generale meno fastidioso
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Metodo
Proprietà
Esempio
Subtractive dithering
Il rumore di quantizzazione è comunque dipendente dal segnale x
in ingresso. Ad esempio, la sua varianza è funzione di x
Si può eliminare questa correlazione con una tecnica detta
subtractive dithering
Sommare ad x un rumore bianco n uniformemente distribuito
nell’intervallo [−1/2, 1/2]
Arrotondare il risultato all’intero più vicino
Al momento della visualizzazione, sottrarre da y un identico
rumore n
In questo modo, il rumore di quantizzazione è bianco e
uniformemente distribuito nell’intervallo [−1/2, 1/2]
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Metodo
Proprietà
Esempio
Esempio (quantizzazione a 4 livelli)
Dithering
Gabriele Guarnieri
Subtractive dithering
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Ordered dithering
Noise shaping
Schema del metodo
Esempio (Floyd-Steinberg)
Ordered dithering
Invece del rumore casuale n, si utilizza un “pattern” o “threshold
map” deterministico e periodico
Vantaggi
Semplicità computazionale
Minori artefatti temporali (se usato su filmati)
Svantaggi: maggiore visibilità dell’errore di quantizzazione
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Ordered dithering
Noise shaping
Schema del metodo
Esempio (Floyd-Steinberg)
Esempio (Bayer)
Esempio di “threshold map” proposto da Bryce Bayer
⎡
⎤
1 9 3 11
⎢
1 ⎢13 5 15 7 ⎥
1
⎥
⎢
⎥−
16 ⎣ 4 12 2 10⎦ 32
16 8 14 6
Procedimento:
Si somma all’immagine la “threshold map” replicata
Si tronca il risultato all’intero inferiore
Bryce Bayer, “An optimum method for two-level rendition of continuous-tone
pictures”, IEEE International Conference on Communications, Vol. 1, pp.
11–15 (1973).
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Ordered dithering
Noise shaping
Schema del metodo
Esempio (Floyd-Steinberg)
Esempio (Bayer)
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Ordered dithering
Noise shaping
Schema del metodo
Esempio (Floyd-Steinberg)
Noise shaping
Il dithering introduce un rumore approssimativamente “bianco”,
cioè con uguale intensità a tutte le frequenze.
Tuttavia, abbiamo visto che la sensibilità dell’occhio umano varia
con la frequenza (contrast sensitivity function)
Inserendo un meccanismo di reazione, o error diffusion, è possibile
“modellare” lo spettro del rumore, tipicamente spostandolo verso
le alte frequenze
Questo metodo è comunemente usato dalle stampanti a getto
d’inchiostro per riprodurre toni di grigio usando soltanto bianco
(carta) e nero (inchiostro)
I convertitori A/D “sigma-delta” sono basati su principi simili
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Ordered dithering
Noise shaping
Schema del metodo
Esempio (Floyd-Steinberg)
Schema del metodo
Calcolo funzione di trasferimento:
N(z) = Y (z) − U(z)
U(z) = X (z) − H(z)N(z)
[︀
]︀
⇒ Y (z) = X (z) + 1 − H(z) N(z)
Il filtro H(z) consente di “modellare” lo spettro del rumore n
introdotto dalla quantizzazione
Di solito si usa un filtro FIR causale, con risposta impulsiva nulla
nell’origine per semplicità di calcolo
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Ordered dithering
Noise shaping
Schema del metodo
Esempio (Floyd-Steinberg)
Esempio (Floyd-Steinberg)
Uno dei metodi più usati, sviluppato da Floyd e Steinberg, usa un
filtro con la seguente risposta impulsiva:
⎡
⎤
0 0 0
1 ⎢
⎥
H=
⎣0 0 7⎦
16
3 5 1
Proprietà:
Coefficienti rappresentabili in virgola fissa
Produce un’uscita “a scacchiera” se l’ingresso x si trova a
metà tra due livelli
R. W. Floyd and L. Steinberg, “An adaptive algorithm for spatial grey scale”,
Proceedings of the Society of Information Display, Vol. 17, pp. 75–77, 1976.
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Ordered dithering
Noise shaping
Schema del metodo
Esempio (Floyd-Steinberg)
Esempio (Floyd-Steinberg)
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica monodimensionale
Codifica bidimensionale
Codifica CCITT Fax
Metodo per la codifica senza perdita di immagini bitonali,
standardizzato nel 1988 dal CCITT (ora ITU-T)
Sviluppato per la trasmissione di fax, ma utilizzato anche per
l’archiviazione (tipicamente in documenti TIFF o PDF)
Due metodi di codifica:
Codifica monodimensionale: “Modified Huffman” (MH)
Codifica bidimensionale: “Modified READ” (MR)
Due versioni attualmente in uso:
Group 3 (ITU-T T.4): Codifica MH o MR, buona resistenza
agli errori di trasmissione
Group 4 (ITU-T T.6): Codifica MR, pensata per trasmissione
su linee ISDN o archiviazione
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica monodimensionale
Codifica bidimensionale
Codifica monodimensionale
Ogni riga dell’immagine viene trattata indipendentemente dalle
altre
Ogni riga è formata da run alternati di pixel bianchi o neri. Ogni
run viene rappresentato da un codice di Huffman prefissato
Lunghezza < 64 ⇒ “Terminating code”
Lunghezza ≥ 64 ⇒ “Make-up code” + “Terminating code”
Ogni riga inizia con un run bianco (eventualmente di lunghezza
nulla) e termina con un simbolo di end of line (per il recupero del
sincronismo in caso di errori)
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica monodimensionale
Codifica bidimensionale
Codifica bidimensionale
Sfrutta la similitudine tra righe adiacenti, codificando in modo
efficiente la differenza tra una riga e la precedente: codifica
“Relative Element Address Designate” (READ)
Diverse modalità
Group 3 → Almeno una riga ogni K codificata in modo
monodimensionale (K dipende dalla risoluzione)
Group 4 → Codifica bidimensionale per tutte le righe; per la
prima si usa come riferimento una riga bianca
Rapporti di compressione tipici (per scansioni di documenti di
testo): 5 – 8 per il Group 3, circa doppi per il Group 4
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica monodimensionale
Codifica bidimensionale
Definizione di changing picture element
Pixel con colore diverso rispetto al pixel precedente nella stessa riga
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica monodimensionale
Codifica bidimensionale
Pass mode
Condizione: b2 < a1
Codifica:
Scrittura di un simbolo 0001
a0 ← b2
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica monodimensionale
Codifica bidimensionale
Vertical mode
Condizione: |a1 − b1 | ≤ 3
Codifica:
Scrittura di un simbolo per rappresentare la distanza a1 − b1
a0 ← a1
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica monodimensionale
Codifica bidimensionale
Horizontal mode
Codifica:
Scrittura di un simbolo 001
Scrittura delle run length (a1 − a0 ) e (a2 − a1 ), in modo
analogo alla codifica monodimensionale
a0 ← a2
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica di regioni di testo
Codifica di regioni con immagini
Codifica JBIG2
Metodo sviluppato dal Joint Bi-level Image Experts Group
(CCITT/ITU-T e ISO). Standardizzato nel 2000 come ITU-T T.88
e nel 2001 come ISO/IEC 14492
Utilizzato tipicamente all’interno di documenti PDF o DJV/DJVU
Rapporti di compressione tipici:
Lossless: 3 – 5 volte superiore al Fax Group 4
Lossy: 3 – 10 volte superiore al lossless
Caratteristiche innovative
Segmentazione della pagina in regioni di testo, immagini (con
dithering) e dati generici
Codifica efficiente di documenti multi-pagina
Alta velocità di decompressione
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica di regioni di testo
Codifica di regioni con immagini
Codifica di regioni di testo
Una regione di testo contiene dei simboli (tipicamente caratteri
tipografici) ripetuti più volte in modo uguale o simile
Il codificatore separa i simboli nella pagina e costruisce un
dizionario di simboli, che può essere condiviso tra più pagine
Per ogni simbolo nella pagina, il codificatore
Cerca un simbolo simile nel dizionario
Se il simbolo esiste, codifica l’indice nel dizionario e la
posizione nella pagina
Altrimenti, codifica i pixel del simbolo e lo aggiunge al
dizionario
Raffina se necessario il simbolo con ulteriori dati
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica di regioni di testo
Codifica di regioni con immagini
Codifica di regioni di testo
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali
Dithering
Dithering spaziale
Codifica CCITT Fax
Codifica JBIG2
Introduzione
Codifica di regioni di testo
Codifica di regioni con immagini
Codifica di regioni con immagini
Per codificare un’immagine con dithering, il decodificatore
Ricostruisce l’immagine di partenza a scala di grigi
(descreening)
Costruisce e trasmette un halftone bitmap dictionary con
pattern di dimensione prefissata
Utilizza i valori di grigio stimati come indici nel dizionario
Per codificare un’immagine generica, si usa un context-dependent
arithmetic coding
Gabriele Guarnieri
Elaborazione e codifica di immagini bitonali