Compressione lossless di
immagini composite
Corso di Compressione Dati Sistemi Multimediali
Compressi
Compression Team
Prof. Bruno Carpentieri
A.A. 2007/2008
Overview
†
†
†
†
Introduzione
Analisi del problema
Approcci attuali
Soluzioni proposte
„ Compression Team
„ Compressi
Immagini composite
Immagini contenente
testo
Es: Pagina di un libro,
libro quotidiano,
quotidiano
giornale, depliant, libretto
istruzioni
Immagini composite (2)
† Gli algoritmi di compressione
immagine
g
attuali sono nati p
per la
memorizzazione di foto in digitale e
quindi sono ottimizzati p
q
per la
rappresentazione di immagini
naturali.
† Comprimere il testo con la stessa
tecnica non è una soluzione ottimale
Immagini composite (3)
† In determinate circostanze il testo
contenuto all'interno di un'immagine
g
ha
solo significato informativo e non necessità
degli stessi dettagli grafici dell'immagine.
† L'obiettivo è dunque
q
q
quello di migliorare
g
il
rapporto di compressione di un'immagine
composita mantenendo comunque un buon
compromesso con la perdita di
informazione/qualità della parte del testo
Comportamento Jpeg col testo
† La compressione di immagini/testo con JPEG classico
offre risultati “inquietanti ”.
Comportamento JPEG col
testo(2)
† L'immagine precedente contenente
solo testo è di circa 66 KB salvata in
Bitmap monocromatico e varia tra i
68 KB e i 140 KB se salvata in
formato JPG.
SLIm
(Segmented Layered Image)
† La mancanza di un formato per
bitmap composite ha portato allo
sviluppo del sistema SLIm.
† Separa testo e linee dalle immagini di
sfondo, per comprimerli più
efficientemente.
Le caratteristiche
† Estremamente semplice e veloce.
† Performance di compressione
prossime allo stato dell’arte.
† Possibile utilizzo in diverse
applicazioni.
† Opera segmentando l’immagine in tre
distinte componenti: background,
foreground e mask layer.
Architettura di SLIm
† crea la maschera binaria che indica
per ciascun
i
pixel
i l se appartiene
ti
all
foreground o al background.
Architettura di SLIm
† separa l’immagine in input,
utilizzando
tili
d lla maschera,
h
su d
due li
livelli:
lli
foreground e background.
Architettura di SLIm
† Binary coder: codifica la maschera.
† Image
g coder: è un codificatore standard di
immagini (JPEG, JPEG-2000) che codifica
background e foreground.
Architettura di SLIm
† combina l’immagine di foreground e
di background in base alla maschera,
restituendo in output l’immagine
compressa.
Come funziona SLIm ?
F
B
I 2 approcci di compressione
† Un primo approccio è usare un codec di immagini che
utilizza la maschera per codificare separatamente sia
ll’immagine
immagine di background che quella di foreground
foreground.
Background
Foreground
I 2 approcci di compressione
†
Un altro approccio possibile è utilizzare un codec off-theshelf per codificare l’intero bitmap del background e del
foreground perciò si assegnano dei valori che producono
foreground,
una buona compressione a quei pixels “don’t care” che
figurano all’interno della maschera.
Background
Foreground
Masked pixel
Il Problema
†
Il problema principale consiste nell’interpolare i pixels validi
all’interno delle locazioni che figurano nella maschera in
modo da non introdurre sharp edges.
edges
†
Esistono tre diversi algoritmi per risolvere il problema che
producono
d
quasii le
l stesse performance
f
di compressione,
i
pur richiedendo diverse velocità di esecuzione:
„
„
„
Algoritmo di Voronoi
Algoritmo POCS
Algoritmo di Filtering (da noi usato)
Filtering
†
Esegue un filtro, calcolante una
l’immagine da sinistra a destra
sostituendo ogni pixel
(con
combinazione lineare (ad esempio
sinistra e di quello superiore.
media, che scandisce
e dall’alto in basso,
maschera) con una
la media) del pixel a
Filtering (2)
†
Un altro simile filtro opera allo stesso modo, ma segue la
direzione opposta (parte dall’angolo in basso a destra
dell immagine).
dell’immagine)
†
Infine, viene calcolata una combinazione lineare dei risultati
ottenuti da entrambi i filtri, pesata al valore della distanza
del pixel più vicino (senza maschera) incontrato dai filtri.
Mask Separation
†
L’obiettivo è assegnare ogni pixel al background o al
foreground in modo da massimizzare la compressione
combinata di maschera,
maschera foreground e background.
background
†
Supponiamo:
IMG N pixel
i l
2N possibili
ibili maschere
h
ma è oneroso ricercarle tutte.
†
La soluzione, è usare un approccio greedy “divide and
conquer ” su regioni più piccole:
„
calcoliamo la maschera usando solo una versione a
livelli di grigio dell’immagine che minimizza la varianza
all’interno di queste regioni, fino a quella ottimale.
Mask Separation (2)
POSSIBILI MERGE
newF
F1, B1
F2, B2
F=F2; B=B1,B2,F1
newB
F1
F2, B1, B2
F1, B1, F2
B2
F1 F2,
F1,
F2 B2
B1
F2
F1, B1, B2
F1, F2
B1, B2
F1, B1
F2, B2
F1, B2
F2, B1
IMMAGINE
ORIGINALE
MASK(43K)
FOREGROUND(34k)
BACKGROUND(29K)
DjVu
† Sviluppato dal 1996 negli AT&T Labs
† Consente la distribuzione su Internet
di immagini ad alta risoluzione, di
doc menti scannerizzati,
documenti
scanne i ati documenti
doc menti
digitali e fotografie.
Modellazione con DjVu
† Si basa su un modello che propone la
segmentazione
g
dell'immagine
g
in
background layer (foto e texture) e
foreground layer (testo) ciascuno dei quali
viene compresso con algoritmi specifici (es.
algoritmo di tipo wavelet come per JPEG
2000).
2000)
† Con questa tecnica si possono ottenere file
molto
lt "leggeri",
"l
i" veloci
l id
da visualizzare
i
li
anche
h
su computer di vecchia generazione.
Prestazioni DjVu
† Fattori di compressione
„ documenti a colori
colori, dalle 5 alle 10 volte
migliori rispetto ad altri formati
concorrenti quali JPEG e GIF;
„ documenti in bianco e nero, fattori dalle
3 alle 8 volte migliori
g
rispetto
p
al
formato TIFF G4;
„ documenti digitalizzati a 400 ppi in fullcolor,
l
con rapportii di compressione
i
tra
1:300 e 1:1000.
DjVu VS JPEG
Bitmap
(699 KB)
DjVu 300dpp
(37 KB)
JPEG 300dpp
(54 KB)
Immagine originale
JPEG
(200 kbytes)
SLIm
(100 kbytes)
DjVu
(65 kbytes)
Approcci Compression Team
† L’approccio che sarà adottato è
quello basato sulla tecnologia SLIm
† Compressione dei due livelli
(background e foreground) settando
i pixel “don’t care” a:
„
„
„
„
1 (bianco)
0 (nero)
M di d
Media
deii pixel
i l adiacenti
di
ti
Filtering
Esempi approcci
Codificati
A
B X
Non codificati
Mascherato non codificato
Esempi approcci
Codificati
A
B 1
Non codificati
Mascherato non codificato
Settaggio pixel
mascherato ad 1 (bianco)
Esempi approcci
Codificati
A
B 0
Non codificati
Mascherato non codificato
Settaggio pixel
mascherato ad 0
(nero)
Esempi approcci
Codificati
A
B
Non codificati
Mascherato non codificato
A+ B
2
Settaggio pixel mascherato alla
media dei valori dei pixel
adiacenti
Esempi approcci
U
A V X
Filtro 1
Analizzati dal filtro
U +V
X=
2
Non analizzati
Pixel da mascherare
Analizzato senza maschera
più vicino
Y W
Z B
Y=
Z +W
2
Filtro 2
Esempi approcci
Codificati
Non codificati
Mascherato non codificato
X
d ( X , A) ⋅ X + d (Y , B ) ⋅ Y
X=
d ( X , A) + d (Y , B )
Settaggio
S
tt
i pixel
i l mascherato
h t alla
ll
combinazione lineare dei
risultati ottenuti dai filtri, pesata
al valore della distanza del pixel
più vicino senza maschera
incontrato dai filtri
Soluzione Proposte da “Compressi”
† Utilizzo di una “maschera colore” per estrarre
dall'immagine
dall
immagine tutte i pixel di un colore
selezionato dall'utente, che corrisponde al
colore del testo.
† Utilizzo di una maschera che selezioni ed estragga i
pixel solo oltre una certa oscurità indicata dall'utente
(
(threshold)
)
† Utilizzo di Canny per l'edge detection e cercare di
dividere ll'interno
interno (testo) e ll'esterno
esterno (sfondo e
immagine) dei contorni e comprimerli
separatamente.
Maschera colore
La maschera colore è uno strumento che permette di
effettuare l’estrazione di un determinato colore,
selezionato dall’utente, da una immagine.
Esempio estrazione del colore rosso:
Maschera colore (cont.)
†
†
Utilizzando la maschera colore si può estrarre un testo.
L’esempio seguente mostra come la selezione del colore
rosso comporta l’esclusione
l esclusione dello stesso nell’area
nell area relativa al
testo.
Soluzione Proposte
† Utilizzo di una “maschera colore” per estrarre
dall'immagine
dall
immagine tutte i pixel di un colore selezionato
dall'utente, che corrisponde al colore del testo.
† Utilizzo di una maschera che selezioni ed
estragga i pixel solo oltre una certa oscurità
indicata dall'utente (threshold)
(
)
† Utilizzo di Canny per l'edge detection e cercare di
dividere ll'interno
interno (testo) e ll'esterno
esterno (sfondo e
immagine) dei contorni e comprimerli separatamente.
Utilizzo della Threshold
†
La scelta della corretta soglia permette di separare il background
dagli oggetti.
†
Se il testo possiede una tonalità di colore diversa dal resto
dell’immagine potrà essere facilmente selezionata attraverso il
taglio dell’istogramma decidendo il corretto intervallo
corrispondente alla tonalità di colore da eliminare.
Soluzione Proposte
† Utilizzo di una “maschera colore” per estrarre
dall'immagine tutte i pixel di un colore selezionato
dall'utente,
dall
utente, che corrisponde al colore del testo.
† Utilizzo di una maschera che selezioni ed estragga i
pixel
i l solo
l oltre
lt una certa
t oscurità
ità indicata
i di t d
dall'utente
ll' t t
(threshold)
† Utilizzo di Canny per l'edge detection e cercare
di dividere l'interno (testo) e l'esterno (sfondo e
immagine) dei contorni e comprimerli
separatamente.
Edge Detection
†
L' Algoritmo di Canny è un operatore ideato da John F. Canny
nel 1986, ed adottato nel campo dell'elaborazione delle immagini
per il riconoscimento dei contorni.
†
I bordi nelle immagini spesso corrispondono a contorni di oggetti
dove l’intensità varia rapidamente.
†
L’individuazione dei bordi e’ largamente utilizzata quando si vuole
dividere l’immagine in aree corrispondenti a oggetti differenti.
Inoltre rappresentare un’immagine attraverso i suoi bordi permette
che la quantità di dati da memorizzare sia ridotta
significativamente.
f
†
Il metodo di Canny segue i seguenti passi:
1.
1
2.
3.
4.
Filtro gaussiano
Norma del gradiente
Thresholding
Thinning
Edge Detection (cont.)
Passi dell’algoritmo
Immagine
input
Selezione
della regione
Immagine
senza testo
Creazione
maschera
Compressione
con LOCO
Estrazione
testo
maschera
Combina
bits
Compressione
maschera
Immagine con testo compressa
Passi dell’algoritmo proposto
†
Immagine da
comprimere
†
Per il forte balzo
di intensità
intorno alla
scritta OK
l’algoritmo di
compressione
lossless JPEG
non è efficiente
ffi i t
Passi dell
dell’algoritmo
algoritmo proposto
(cont.)
† Passo 1)
„ L’utente
L utente seleziona la minima area
contenente del testo.
Passi dell
dell’algoritmo
algoritmo proposto
(cont.)
† Passo 2)
„ Sull’area
Sull area selezionata viene applicato
l’algoritmo di Canny Edge Detection.
Canny edge detection
Passi dell
dell’algoritmo
algoritmo proposto
(cont.)
† Passo 3)
„ Creazione della maschera
† Maschera colore
† Sfruttando il Canny Edge Detector
† Threshold sull’istogramma
La maschera verrà compressa
e salvata separata dall’immagine
Codice della maschera
Passi dell
dell’algoritmo
algoritmo proposto
(cont.)
† Passo 4)
„ Si sostituisce il colore dei pixel
corrispondenti alla maschera
nell’immagine
ll’i
i
originale
i i l con il valore
l
d
deii
pixel intorno al testo
„ Così
C ì ffacendo
d sii attenueranno
tt
le
l forti
f ti e
repentine variazioni di intensità presenti
nell’immagine
nell
immagine in modo da garantire un
migliore funzionamento dell’algoritmo
Lossless Jpeg.
Jpeg
Passi dell
dell’algoritmo
algoritmo proposto
(cont.)
† Passo 5)
„ Compressione senza perdita
dell’immagine e della maschera ottenute.
Al momento della visualizzazione
dell’immagine compressa, maschera e i
pixel del contorno saranno riutilizzati per
riposizionare il testo all’interno
dell’immagine
dell
immagine di partenza.