TNI Flashcards
Lois de Parkinson
1) Les volumes de données augmentent toujours
jusqu’à remplir l’espace de stockage disponible.
2) Le trafic réseau augmente jusqu’à occuper la largeur de bande passante disponible
Loi de Moore
L’espace de stockage et la capacité de traitement des données stockées doublent tous les 18 mois.
Conséquence des lois de Parkinson et de Moore
D’ici à la fin du 21e siècle, chaque personne sur Terre disposera d’un téraoctet de données stockées.
Modèle de communication de Shannon et Weaver
1) La source énonce un message
2) L’émetteur transforme le message en signal
3) Le canal achemine le signal (un bruit peut apparaître)
4) Le récepteur reçoit le signal et reconstitue un message
5) Le destinataire reçoit le message
Les deux types de compression et leur principale particularité
=> Compression sans perte : données préservées
=> Compression avec perte : données dégradées
Exemples avec une contrainte de temps réel
=> Téléphone, vidéo (la compression et la décompression doivent être rapides)
Exemples avec une contrainte de temps différé
=> Stockage sur disque (la compression peut être lente mais pas la décompression)
=> Imagerie satellitaire ou embarquée (la décompression peut être lente mais pas la compression)
Performances d’un système de compression avec perte
- taux de compression (débit initial / débit après compression)
- qualité du signal comprimé (critère subjectif : visuel / critère objectif : SNR)
- Complexité du système
Définition d’une source :
- discrète
- sans mémoire
- avec mémoire
Rappels :
1) une source <=> système pouvant prendre plusieurs états
2) pour transmettre un message, la source utilise un langage
- discrète : alphabet discret (cas du numérique)
- sans mémoire : états indépendants
- avec mémoire : états dépendants entre eux
Probabilité d’apparition du niveau de gris x
pₓ(x) = nb_pixels_égaux_à_x / nb_total_de_pixels
Fonction de densité pour une loi uniforme
fₓ(x) = 1 / (b-a)
avec x ∊ [a, b]
Fonction de densité pour une loi gaussienne
fₓ(x) = exp(-(x-μ)² / 2σ²) / sqrt(2πσ²)
Fonction de densité pour une loi laplacienne
fₓ(x) = exp(- √2 * |x-μ| / σ) / (√2 * σ)
Entropie de Shannon
Quantité d’information moyenne minimale contenue dans une source. Elle s’exprime en bits/échantillon ou en bits/pixel
Entropie d’ordre 0
Pour une source S indépendante prenant ses valeurs dans un ensemble de K symboles, de probabilité d’apparition pk (k∈{1,…,K})
H(S) = -∑pk*ln(pk) bits/pixel
(on somme sur k de 1 à K)
Entropie conjointe
Les échantillons sont des groupes de pixels (permet de prendre en compte la corrélation entre pixels)
Entropie conditionnelle
Les échantillons sont des pixels ou des groupes de pixels (permet de prendre en compte le passé)
Quantité d’information après codage
< entropie pour le codage avec perte
≥ entropie pour le codage sans perte
Distorsion moyenne
D = (1 / MN) * ∑∑(i(m,n)-î(m,n))²
Première somme : m∈[| 0, M-1 |]
Deuxième somme : n∈[| 0, N-1 |]
i : pixel original
î : pixel compressé
SNR
SNR = 10log( ( ∑∑i²(m,n) ) / (MN*D) )
s’exprime en dB
PSNR
PSNR = 10*log( (2ⁿ-1)² / D )
(s’exprime en dB)
où n est le nombre de bits
Exemple de limite pour l’évaluation de la qualité avec le PSNR
Un bruitage dans une région de l’image (rendant méconnaissable cette zone) peut produire le même PSNR qu’un bruitage sur toute l’image
Exemple de limite pour l’évaluation de la qualité
Les outils classiques d’évaluation de la qualité laissent penser qu’une image est fortement bruitée si elle a seulement subi une rotation. Pourtant, son contenu est inchangé.
Chaîne de compression
Signal => Mise en forme (transformée) => Quantification + indexation (perte d’informations) => Codage entropique => Adaptation au canal => Décodage au canal => Décodage entropique => Désindexation => Transformée inverse => Signal restitué
Méthode par transformée : DCT
Discret Cosine Transform (Transformée en cosinus discrète) : découpage de l’image en blocs (+ ou - stationnaires)
=> inadaptée aux signaux non-stationnaires
=> algorithme rapide
=> effets de blocs après quantification
Analyse multirésolution : Ondelette
ψₐᵦ(x) = (1 / √|a|) * ψ( (x-β) / a )
Avec a le facteur d’échelle et β (ou b) le facteur de translation
=> adaptée aux signaux non-stationnaires
=> permet une décomposition spatio-fréquentielle
=> permet une décomposition multi-résolution
=> pas d’effets de bloc
=> permet la transmission progressive
Définition d’un signal stationnaire
On dit qu’un signal aléatoire est stationnaire si ses propriétés statistiques sont invariantes par translation dans le temps.
Analyse multirésolution : approche interbandes
On code les dépendances entre les sous-images.
=> simple et efficace mais sensible aux erreurs de transmission
Analyse multirésolution : approche intrabandes
Chaque sous-image est codée de manière indépendante.
=> nécessité de définir un débit pour chaque sous-bande
=> problème : obtenir la distorsion la plus faible
But de la quantification
But : représenter un signal numérisé sur L1 niveaux par L2 niveaux (L2 < L1)
Code préfixe
Un code préfixe (ou code instantané) est un code ayant la particularité de ne posséder aucun mot du code ayant pour préfixe un autre mot du code.
Code de Huffman
Code préfixe mis au point par Huffman en 1952.
- Avantages : faible complexité, code instantané, plus petit parmi tous les codes instantanés
- Inconvénients : performances faibles, nécessité de connaître toute la source
QSU (quantifieur scalaire uniforme)
C’est le type de quantifieur le plus simple, où les intervalles sont de longueur constante. Il est optimal pour une source uniforme
Partitionnement de l’espace en régions de Voronoï
Chaque cellule (surface) représente la « zone d’influence » d’un centroïde (points noirs).
Principe du JPEG
1) Découpage en blocs de 8x8 pixels (entiers entre 0 et 255)
Puis sur chaque bloc :
2) Centrage : 8x8 pixels (entiers entre -128 et +127)
3) DCT : 8x8 coefficients DCT (réels entre -1023.0 et +1024.0)
4) Quantification : 8x8 coefficients quantifiés
5) Zigzag scan : 64 coefficients ordonnés (BF => HF)
6) Huffman : séquence de bits
Avantages et inconvénients du JPEG
Avantage : gros succès => 80% des images sur le web
Inconvénients :
- efficacité de codage limitée
- effets visuels de bloc lors d’une compression forte
- applications d’imagerie demandent de nouvelles fonctionnalités non supportées par JPEG
Exigences pour JPEG 2000
- excellent rapport distorsion / débit
- gestion de 2 à 16 millions de couleurs sur la même architecture
- compression avec ou sans perte
- transmission progressive par résolution et par raffinement
- faible complexité algorithmique
- accès aléatoire dans le fichier compressé pour extraction de régions d’intérêt
- robustesse aux erreurs de transmission
- protection des informations pour l’exploitation correcte de l’image.
Structure de base retenue pour JPEG 2000
1) Transformée en ondelettes
2) Codeur par plan de bits
3) Codeur entropique
En réalité, seuls la syntaxe et le décodeur sont normalisés. Le codeur est seulement informatif.
Caractéristiques de JPEG 2000
- Gestion des images multi-composantes (ex : couleur)
- Gestion des dynamiques de 1 à 32 bits
- Découpage de l’image en « tuiles » et transformation de chaque « tuile »
- Choix de transformées en ondelettes (lifting ou convolution). Filtres pré-implémentés ou utilisateurs
- Multirésolution : Nombre de niveaux de décomposition variable et choix de l’arbre de décomposition
- Codage par blocs uniformes de 64x64 coefficients transformés
Principe de JPEG 2000
Image => Prétraitements => DWT => Quantification => Codeur entropique (codage arithmétique puis organisation du flux) => Données comprimées (binaires)
Acronyme JPEG
Joint Photographic Experts Group
Plan de bits pour une tuile
Chaque plan correspond à un bit de l’écriture binaire des nombres composant la tuile (morceau de l’image). Ces différents plans sont ensuite parcourus successivement, du plan correspondant au bit le plus significatif jusqu’au plan correspondant au bit le moins significatif.
Résolution progressive
Composante puis niveau puis couche
Qualité progressive
Composante puis couche puis niveau
Définition de la cryptographie
Technique visant à transformer un message pour qu’il devienne illisible
Définition de la stéganographie
Technique visant à dissimuler un message dans un autre
Définition du tatouage numérique
Technique visant à insérer une signature invisible et indélébile dans une image
Tatouage visible
Masquage d’un document à l’aide d’une ou plusieurs marques visibles qui ne sont effaçables correctement que si l’on possède une clé secrète.
Tatouage fragile
Permet de prouver qu’un document n’a pas été falsifié (i.e. n’a pas subi de transformation pouvant modifier son interprétation)
Tatouage semi-fragile
Permet de détecter localement des manipulations malveillantes tout en étant robuste à certains traitements (comme par exemple la compression)
Tatouage aveugle
La marque est extraite à l’aide du document tatoué (éventuellement attaqué) seulement
Tatouage semi-aveugle
La marque est extraite à l’aide du document tatoué et de la connaissance de la signature (marque)
Défis théoriques du tatouage
- Capacité d’insertion (jusqu’à plusieurs kbits)
- Invisibilité
- Robustesse (face à des traitements bienveillants ou non)
- Sécurité (liée aux attaques exploitant une faille de l’algorithme lui-même)
Tatouage dans le domaine spatial : algorithme du Patchwork
- 2 patches A et B de même taille (n pixels) choisis aléatoirement dans l’image (=> clé)
- modification de l’image en augmentant d’une unité le niveau de gris des pixels de A et en diminuant d’un niveau de gris les pixels de B
- S’ = ∑a’ᵢ - b’ᵢ = 2n ne peut être trouvé que par un utilisateur ayant la clé car pour n grand, S = ∑aᵢ - bᵢ ≃ 0
=> faible robustesse, permet juste de savoir si la personne a la clé
Tatouage dans le domaine spatial : méthode du bit de poids faible (LSB pour Least Significant Bit)
On remplace le(s) bit(s) de poids faible du pixel d’origine par le(s) bit(s) de poids fort du tatouage
Avantages du tatouage dans le domaine transformé
- Meilleure prise en compte des propriétés psychovisuelles
- Robustesse accrue
Tatouage dans le domaine transformé : algorithme de Koch et Zhao
Tatouage dans les moyennes fréquences
Principe : choix de zones de blocs fréquentiels (blocs DCT 8x8 choisis aléatoirement) avec la même amplitude de valeur puis modification.
=> faible robustesse aux attaques géométriques et faible capacité
Pourquoi l’algorithme de Koch et Zhao utilise des fréquences moyennes ?
- Fréquences basses (zones homogènes) : robuste mais visible
- Fréquences hautes (forts contours) : invisible mais fragile
Tatouage et compression conjoints : utilisation d’un seul dictionnaire
- Avantages : méthode aveugle, robustesse à la compression, au filtrage et au bruit
- Inconvénients : sensibilité aux attaques géométriques, capacité limitée
Tatouage et compression conjoints : utilisation de deux dictionnaires (QVAM)
QVAM = quantification vectorielle algébrique modulée
- Avantages : méthode aveugle, robustesse à la compression, au filtrage et au bruit, forte capacité
- Inconvénients : sensibilité aux attaques géométriques
Caractéristiques du tatouage vidéo
- bande passante de dissimulation plus grande que pour les images fixes
- contrainte de temps réel cruciale (algorithme peu complexe)
- attaques beaucoup plus difficiles que pour les images fixes
- les méthodes de tatouage s’appliquent souvent à des flux compressés
DWT
Discret Wavelet Transform (transformée par ondelettes discrète)
