Compression Images Par Ondelettes
Compression Images Par Ondelettes
Compression Images Par Ondelettes
02/02/2011
de codage bases sur la T.O. Algorithme EZW Caractristiques Algorithme JPEG 2000 Caractristiques Algorithme: EBCOT Codage des ROI (region of interest) Exemples Parties II et III
page 2 Dpartement TSI SI222 - Codage d'images par ondelettes
Pourquoi
utiliser la T.O. ? Limites de la TCD : reprsentation des contours faible dbits ; effets de bloc T.O. : bon modle du signal
- bonne rsolution spatiale haute frquence - bonne rsolution frquentielle basse frquence
page 3
Dpartement TSI
Stratgies de codage
Mthodes ne prenant pas en compte les spcificits de lAMR Allocation de bits entre les sous-bandes Quantification dans chaque sous-bande (quantificateur optimal de Lloyd-Max adapt) Codage entropique (ex. : Huffmann), ventuellement contextuel Avantage : corrlations intra-bande bien exploites (une QV peut encore amliorer lefficacit !) Inconvnient : on nexploite pas les corrlations rsiduelles inter-bandes !
page 4 Dpartement TSI SI222 - Codage d'images par ondelettes
Stratgies de codage
Mthodes exploitant les dpendances hirarchiques entre les coefficients : EZW (Embedded Zerotrees of Wavelet coefficients), SPIHT (Set Partitioning in Hierarchical Trees)
Mthodes
bases sur une reprsentation par arbres des dpendances entre les sous-bandes Avantages : corrlations inter-bande bien exploites, faible complexit Inconvnient : plus difficile obtenir la scalabilit en rsolution
page 5 Dpartement TSI SI222 - Codage d'images par ondelettes
Algorithme EZW
Caractristiques principales
Scalabilit
en qualit, cest--dire reprsentation progressive Codage lossy-to-lossless Faible complexit Performance de compression bien meilleure que JPEG Trs vident aux faibles dbits
page 6
Dpartement TSI
Bande LL : approximation
TO
encore 2 niveaux
Dtails diagonaux
Bande HH Dtails diagonaux Dtails horizontaux
page 9
Dpartement TSI
Algorithme EZW
Le
seule ordre de bayalage des sous bandes nest pas suffisant pour garantir que les coefficients plus grands soient envoys en premiers Il faut localiser les coefficients significatifs Problme : Rduction de linformation de localisation Ide : Exploiter la corrlation inter-bande pour prvoir les coefficients non-significatifs Si la prdiction est correcte, on conomise la description de beaucoup de coefficients
page 10
Dpartement TSI
page 11
Dpartement TSI
cn,m
descendants de cn,m
page 12
Dpartement TSI
page 13
Dpartement TSI
Ide de EZW
Quand
un coefficients est petit (c.--d. sous seuil), il est probable que tout ses descendants soient petits aussi Alors on utilise un seul symbole de codage pour reprsenter un coefficient c tel que : c est non significatif tous ses descendant sont non significatif En ce cas c est une racine darbre de zros (zero-tree root) Avec un seul symbole (ZT) on code (1+4+42+4N-n) coefficients Information de localisation implicite dans linformation de significativit
page 14 Dpartement TSI SI222 - Codage d'images par ondelettes
=0 n = floor(log2 ( |c|max)) Tk = 2n while (dbit < dbit disponible) Pas dominant Pas de raffinement Tk+1 Tk/2 k++ end
page 15
Dpartement TSI
Pas dominant
Balayage
des coefficients Si |c| > Tn Coefficient significatif Si c>0 on encode SP (significant positive) Si c<0 on encode SN (significant negative) sinon, on compare tous les descendants de c avec le seuil si tous les descendants sont non-significatifs, c est cod comme zero-tree root (ZT) et ses descendants ne seront plut considrs ce pas sinon le coefficient est cod comme isolated zero (IZ)
page 16 Dpartement TSI SI222 - Codage d'images par ondelettes
Pas de raffinement
On
code un ultrieur bit pour tous les coefficients significatifs Cest quivalent dire que on rduit de moiti la cellule de quantification des coefficients significatifs
page 17
Dpartement TSI
Itration et terminaison
Le
pas dominant k permet de coder le k-me plan de bit de la matrice des coefficients dondelette Au fait, dire que un coefficient est significatif est quivalent dire que 2n < |c| < 2n+1 On rduit le seuil de moiti : on passe au prochaine plan de bit
Lalgorithme
termine quand on a puis le nombre de bit disponible ou quand on a cod tous les plans de bit (transforme en entire, codage sans perte)
Dpartement TSI SI222 - Codage d'images par ondelettes
page 18
-2T0
-T0
T0
2T0
page 19
Dpartement TSI
-2T0
-T0
T0
2T0
page 20
Dpartement TSI
- SN -3/4 T0
- IZ, ZT 0
-2T0
-T0
-T0/2
T0/2
T0
2T0
page 21
Dpartement TSI
-2T0
-T0
-T0/2
T0/2
T0
2T0
page 22
Dpartement TSI
Algorithme EZW
Codage
par plan de bits : Au pas k on code le bit plane log2Tk Description progressive : Chaque nouveau plan de bit permet de raffiner la quantification des coefficients Codage entropique (Huffman ou arithmtique) des symboles de significativit Codage lossless-to-lossy On utilise une transforme en entiers (tous coefficients entiers) Quand on code tous les plans de bit, on peut reconstruire parfaitement tous les coefficients
page 23 Dpartement TSI SI222 - Codage d'images par ondelettes
Le standard JPEG2000
JPEG : Joint Photographic Experts Group But : compression numrique des images fixes Organismes de standardisation : ISO et ITU-T
Partie I : Core coding system Partie II : Extensions (TCQ, images multi-composants,) Partie III : Motion JPEG2000 Partie IV : Conformance Partie V : Reference Software Partie VI : Compound images
Partie VII : Abandonne Partie VIII : JPSEC Partie IX : JPIP Partie X : JP3D Partie XI : JPWL Partie XII : ISO Base Media File Format / MPEG-4
page 24
Dpartement TSI
page 25
Dpartement TSI
composs : JPEG peu performant sur des documents binaires (texte) Accs alatoire : JPEG peu flexible Architecture ouverte : le systme peut tre optimis pour diffrents types dimages et dapplications Transmission progressive en qualit et en rsolution
En conclusion, JPEG2000, standard international (IS) depuis 2001, a pour objectif de complter et pas de remplacer le standard JPEG
page 26 Dpartement TSI SI222 - Codage d'images par ondelettes
Marchs et Applications
1. Internet 2. Mobiles 3. Imprimantes 4. Scanners 5. e-commerce 6. Camras numriques 7. Fac-simile 8. Librairies numriques 9. Imagerie mdicale 10. Imagerie satellitaire
page 27 Dpartement TSI SI222 - Codage d'images par ondelettes
fonctionnalits : Codage des rgions dintrt Robustesse aux erreurs Scalabilit en qualit et en rsolution Tiling Capacit datteindre un dbit donn Du codage sans perte au codage avec perte dans un seul systme Meilleure compression bas dbit Complexit plus leve
page 28 Dpartement TSI SI222 - Codage d'images par ondelettes
Description de lalgorithme
Transformation
en ondelettes Partition en blocs EBCOT: Quantification Codage entropique Allocation de dbit (optimisation RD)
Ondelettes utilises : mode sans perte : biorthogonales 5/3 (lifting entiers vers des entiers) mode avec perte : Daubechies biorthogonales 9/7
page 29 Dpartement TSI SI222 - Codage d'images par ondelettes
page 30
Dpartement TSI
page 31
Dpartement TSI
page 32
Dpartement TSI
obtenir un certain dbit total, les trains binaires doivent tre coups
couper les trains binaires? Ri = RT/N simple mais sous optimale Solution optimale ?
Comment
Problme
D Di
page 33 Dpartement TSI
R R
i
de Lagrange : minimisation de
J Di R.i RT
Le
dDi dRi
page 34
Dpartement TSI
dbit-distorsion finale dtermine le point de coupure de chaque flux binaire de bloc Bloc avec grandes valeurs Dbit plus important Les points de coupure optimaux sont des points o les courbes RD des blocs ont la mme pente On peut dterminer plusieurs points de coupure, correspondants plusieurs dbit totaux Le bitstream global est ainsi form dun ensemble de couches (layers)
page 35
Dpartement TSI
Layer 1, 1
page 36 Dpartement TSI SI222 - Codage d'images par ondelettes
Layer 2, 2
page 37 Dpartement TSI SI222 - Codage d'images par ondelettes
1 : gnration des flux binaires progressifs par bloc, avec information RD Codeur arithmtique bas sur les contextes Tier 2 : cration des couches de qualit et codage de linformation RD Optimisation RD
Attention
page 38
Dpartement TSI
Exploite
les variations locales, dun bloc lautre, des caractristiques statistiques de limage Facilite les applications ncessitant un accs alatoire dans limage Rduit lutilisation mmoire dans limplantation matrielle du codeur ou dcodeur Permet une implantation parallle Effet de bloc ?
page 39
Dpartement TSI
Certaines rgions de limage doivent avoir une meilleure qualit Statique : la rgion est dcide et encode ds le dbut, ct encodeur Dynamique : la rgion est dcide et peut tre dcode en ligne partir dun seul bitstream Masque de la rgion Masque binaire, dfinit les pixel de la ROI et du background La masque est dfinie sur limage dans le domaine spatial, mais selon le filtre utilis, on value sa forme dans le domaine transform
page 40
Dpartement TSI
page 41
Dpartement TSI
Les coefficients dondelettes correspondant la ROI sont multiplis par une constante s La distorsion associ alla ROI est artificiellement plus grande Un surplus de ressources est donn la ROI Le background nest pas modifi On peut avoir plusieurs ROI, chacune avec son s Les valeurs de s sont stockes dans le bitstream La masque de la ROI est ncessaire au codage et au dcodage
page 42
Dpartement TSI
Mthode MAXSHIFT : tous les coefficients de la ROI sont translats au-dessus des coefficients du background La ROI est code avant tout autre rgion Au dcodeur un simple seuil est utilis pour reconnatre la ROI Aucune information sur la ROI doit tre insre dans le train binaire
page 43
Dpartement TSI
de mise lchelle (general scaling) Avantages : La qualit relative entre ROI et background peut tre choisie arbitrairement On peut utiliser plusieurs ROI avec diffrentes qualits Inconvnients : Seulement formes rectangulaire ou circulaire Ncessaire envoyer la forme de la ROI Complexit supplmentaire au dcodeur (dcodage de forme) Supporte seulement dans la partie II
page 44 Dpartement TSI SI222 - Codage d'images par ondelettes
Mthode MAXSHIFT Avantages Pas besoin denvoyer linformation de forme Pas besoin de concevoir un encodeur/dcodeur de formes Forme de la ROI quelconque Inconvnients Une seule ROI On peut pas modifier la qualit relative de ROI et BG
Augmentation du dbit avec MAXSHIFT par rapport nonROI pour un codage sans perte : rgion rectangulaire : inf. 2% rgion circulaire 25% de limage : inf. 10%
Dpartement TSI SI222 - Codage d'images par ondelettes
page 45
Pondration psycho-visuelle
Exploite la connaissance de la sensibilit du systme visuel, variable en fonction des frquences spatiales mesure par la CSF (Contrast Sensitivity Function) CSF dtermine par la frquence spatiale des coefficients dondelettes : une valeur par sous-bande La pondration CSF est dtermine par lencodeur, mais dpend des conditions de visualisation au dcodeur Deux situations : FVW (Fixed Visual Weighting) : CSF choisies en fonction des conditions de visualisation finales PVC (Progressive Visual Coding) : les pondrations visuelles sont changes au cours du processus dencodage
page 46
Dpartement TSI
du codage entropique Code blocks Rinitialisation du codeur chaque pas Symboles de synchronisation Niveau des paquets Petits paquets Symboles de synchronisation
page 47
Dpartement TSI
Scalabilit en qualit
page 48
Dpartement TSI
Scalabilit en qualit
page 49
Dpartement TSI
Scalabilit en qualit
page 50
Dpartement TSI
Scalabilit en qualit
page 51
Dpartement TSI
Scalabilit en rsolution
page 52
Dpartement TSI
Scalabilit en rsolution
page 53
Dpartement TSI
Scalabilit en rsolution
page 54
Dpartement TSI
Scalabilit en rsolution
page 55
Dpartement TSI
coded quantization Amliore les performances de compression Visual masking Traitement non-lineaire qui exploite les effet de masquage visuel Dcomposition ondelettes arbitraire Filtres ondelettes arbitraires Multiple component transform Pour image plusieurs composantes ROI avec la mthode General Scaling
page 56 Dpartement TSI SI222 - Codage d'images par ondelettes
Motion JPEG2000
Chaque image de la vido est code indpendamment des autres avec JPEG2000 partie I Faible complexit par rapport codeurs vido bass sur la estimation/compensation du mouvement Performance de compression infrieure aux codeurs avec ME/MC Robustesse aux erreurs (pas de dpendance entre images)
page 57
Dpartement TSI