Università degli studi di Ferrara
DIPARTIMENTO DI INGEGNERIA
Corso di Laurea in Ingegneria Elettronica
Codifica e decodifica di oggetti visivi
nello standard MPEG-4
Laureando:
Fabio Cavalli
Relatore:
Dott. Ing. Massimo Piccardi
Correlatore:
Prof. Ing. Rita Cucchiara
DATI VISIVI
- Contenuti visivi bidimensionali naturali: immagini in movimento a colori
a variazione continua di tono
- Rappresentazione in forma normale:
successione di bitmaps
nello spazio di colore YCBCR
t
- Sottocampionamento crominanza:
 perdita di qualità impercettibilie
 rappresentazione più compatta
esempio notevole: chroma format 4:2:0
Campione Y
Campione CB,CR
TRASMISSIONE DI CONTENUTI VISIVI
Es.: filmato SIF 4:2:0 progressivo a 30 Hz in true color (‘risoluzione’ media)
ogni frame richiede 1,5 ∙ 352 ∙ 240 ∙ 8 ≈ 1 Mbit → data rate: 30 Mbps
LIMITI
TRASMISSIONE
STORAGE
banda canali di trasmissione
capacità dispositivi storage
es.: ISDN 128 kbps
es.: 1 h di filmato richiede 13,5 GB
di memoria di massa
compressione necessaria in part. per riproduzione in tempo reale dalla rete
→ altrimenti conveniente: uso efficiente delle risorse (rete, memorie)
tempi di latenza ridotti SE non è troppo onerosa
COMPRESSIONE
Compressione o compattamento dei dati: codifica dell’informazione volta
al conseguimento di una rappresentazione in forma compatta
Efficienza di codifica per immagini naturali:
 correlazione spaziale → codifica intra
 correlazione temporale → codifica inter
 ridondanza percettiva (spc. e tmp.) → codifica con perdita (lossy)
TECNICHE LOSSY PER IMMAGINI FISSE
Maggior efficienza di compressione a parità di costo computazionale
 quantizzazione vettoriale
 compressione frattale
Troppo onerose → codifica per trasformate
CODIFICA PER TRASFORMATE
Trasform.
2D
Quantiz.
scalare
Codifica
entropica
01011101...
8x8
3x
Cod. sorgente (lossy)
Cod. lossless
Implementazione low cost della quantizzazione vettoriale
1. Trasformazione decorrelante:
coefficienti indipendenti – energia concentrata alle basse frequenze spaziali
trasf. subottime ma veloci: attualmente DCT (tutti IS)
verso Wavelet (JPEG2000, VTC di MPEG-4): opt. contorni (localizzazione)
2. Quantizzazione pesata o percettiva
3. Codifica entropica: Huffman o aritmetica (5-10% più efficiente ma onerosa)
MPEG
MPEG: comitato ISO/IEC per codifica immagini in mov. ed audio associato
MPEG-4: fase 4 del gruppo, attualmente 2 versioni (altre 3 in fieri)
Storage su
supporti digitali
Televisione
digitale (SDTV e
HDTV)
Codifica a oggetti
MPEG-7: rappresentazione e gestione contenuti multimediali
MPEG-21: infrastruttura multimediale
MPEG-4
Mira all’integrazione di 3 campi applicativi della tecnologia dell’informazione
TV
computer
MPEG-4
telecom.
Obiettivi:
 efficienza di compressione per ampia gamma di bitrates e tipi di dato
 interattività basata sui contenuti → approccio ad oggetti
Sequenza
tradizionale
(frame based)
Oggetto di forma
arbitraria
(arbitrary shaped)
 accesso universale → rappresentazione robusta e scalabilità
PARTE 1: SISTEMA
audio
Non solo codifica ma anche composizione di scene
 contenuti disomogenei:
es. video: naturali, sintetici (2D e 3D) o ibridi
 grafo in stile VRML
 codec scena formato BIFS
immagine
arbitrary-shaped
naturale
3D
sintetico
Immagine
naturale
tradizionale
Consente l’integrazione dei codec specifici
 codifica → multiplazione dei flussi informativi in uno stream MP4 conforme
 decodifica → demultiplazione e composizione della scena
Supporto necessario
PARTE 2: VIDEO
Standard generale: moltissimi tools ad hoc per le diverse funzionalità
Implementazione completa spesso ingiustificata e costosa → profili e livelli
 Profilo: definisce un’implementazione parziale dello standard
(sottoinsieme della sintassi) attraverso i tipi di oggetti trattabili
 Livello: identifica un insieme di vincoli sui parametri dell’algoritmo,
fissando il limite massimo di complessità consentita
Profilo@livello → punto di interoperabilità codec fissato
Profili visivi naturali:
simple
scalable
simple
ricoprimento parziale
→ MPEG-4 video famiglia di algoritmi
core
n bit
main
CODIFICA FRAME-BASED
Si adatta la codifica a blocchi per trasformate alle immagini in movimento:
importante correlazione temporale → codifica differenziale dell’immagine
rispetto a una sua predizione
Formazione predizione:
 in avanti, indietro (ordine di riproduzione) o bi-interpolata
 con compensazione del movimento: si stima il movimento dei macroblocchi
e lo si applica al frame di riferimento per la predizione.
16x16
svantaggi: devo allegare i vettori di moto stimati (overhead)
stima e compensazione del moto onerose
con codifica differenziale dei MV (altamente correlati) l’efficienza
di compressione aumenta
DivX;-) implementa lo standard di codifica frame-based MPEG-4 con audio MP3
CODIFICA OBJECT-BASED
Codifica di oggetti di forma arbitraria per
supportare interattività content-based:
contenuto informativo ‘duplice’
forma
trama
Il codec per la forma guida il codec per la trama: richiede la codifica dei soli
blocchi dentro o sul contorno della sagoma
Schema di codifica classico ottimizzato:
 DCT adattiva alla forma (SA-DCT):
solo pixel attivi nei border blocks
(costo computazionale ridotto)
 Padding: sfondo originale poco efficiente
nella MC → farcitura oggetto segmentato
per ottimizzarne le capacità predittive
CODIFICA SAGOMA
Sequenza di fotogrammi detti α-planes: rappresentazione forma o livelli di
traslucentezza
→ codifica sagome binarie:
Formazione di una finestra minima (VOP) contenente l’oggetto e allineata ai
macroblocchi ← per pilotare correttamente il codec della trama
Codifica del VOP (anche lossy):
 approccio a macroblocchi, detti BAB
 moto-compensazione OR codifica aritmetica basata sul contesto (CAE)
CAE: codificatore aritmetico pilotato dalla probabilità delle realizzazioni
condizionata ad un contesto di pixel ‘vicini’ ← correlazione!
MC per formazione contesto inter mode (vicinato temporale)
CODEC VIDEO MICROSOFT
Implementazione software in C++ rivolta a Windows
 solo parte video di MPEG-4 vers. 1 → corredo software
 oggetti naturali e trame scalabili (wavelet)
 codice non ottimizzato
BENCHMARK
- Obiettivi: stima tempi di calcolo richiesti e verifica requisiti per esecuzione
in tempo reale (broadcasting in rete e videoconferenza)
- Configurazione piattaforma: PC Pentium II 450 Mhz 128 MB Windows 98
- due sole sequenze di test di ‘risoluzione’ media: 1s CIF 4:2:0 @10 fps
“Stefan”
classe frame-based
≈ 86 kB (5,6%)
“bream”
classe arbitrary-shaped
≈ 18 kB (1,2%)
FUNCTION TIMING: DECODER
“Stefan”: 730 ms
“bream”: 1960 ms
IDCT
34%
I/O
30%
altro
8%
vs
I/O
85%
elaborazione
15%
ME-MC
23%
IQ
5%
I/O in “bream” molto oneroso: diversa modalità d’accesso al disco accesso
sequenziale di “Stefan” → accesso diretto (“seekoff”) di “bream”
Misura I/O poco significativa:
 dipende fortemente disco rigido usato (ottimizzazioni controller)
 applicazioni pratiche (players): la riproduzione non richiede scrittura su disco
→ confronto al netto di I/0
CONFRONTO
Tempi di esecuzione [ms]
250
247,806
200
162
150
100
Stefan
82,553
bream
93,152
54,147
35,326
34,648
50
9,304
47,751
19,39
0
IDCT
ME-MC
IQ
VLD
shape
altro
Al netto di I/O: 500 ms (“Stefan”) contro 290 ms (“bream”) per 1s di video
Entrambe stanno in real-time, “bream” condizionatamente all’I/O
ENCODER
1000000
Tempi di esecuzione [ms]
161079
10000
3410
89369
5161
1663
477 552
1068
Stefan
bream
100
1
(I)DCT
ME-MC
(I)Q
altro (I/O)
 Tempi totali: 167 s contro 97 s per 1 s di video
 ME estremamente onerosa: tempi 2 ordini di grandezza superiori
agli altri tools
CONCLUSIONI
Fattore di scala (≈1,7) ricorrente tra gli stessi tempi relativi alle 2 sequenze:
tempi di esecuzione modulati dal numero di blocchi utili (tecniche block-based)
Per risoluzioni medie decoder supporta il real-time → distribuzione
video in rete
Margine per risoluzioni maggiori minimo MA accortezze speed-up immediato:
 codice ottimizzato MMX dei GPP moderni
 algoritmi di complessità ridotta per ME (ad libitum)
riduzione dei tempi di un ordine di grandezza
→ plausibile real-time anche per ‘risoluzioni’ maggiori su PC più recenti
Encoder: vincoli sforati clamorosamente → impossibili applicazioni real time
(end-to-end, es. videoconferenza)
Forse solo per risoluzioni molto basse su piattaforme all’avanguardia