bitmap = on code la suite des points.

vectoriel = on code une description de l'image (rectangles, ellipses, ...)

exemple :

Une droite = {tous les points de cette droite} (bitmap)

= {2 extrémités} (vectoriel)

1) format proche du hardware (sauf processeur dédié)

2) adaptable aux images complexes

3) Adapté aux traitements d'images (brosse, aérographe, gomme, contraste, ...)

1) modifications spatiales difficiles transformation par réduction => perte d'information

transformation par agrandissement => grossissement des points.

2) Encombrement important.

On ne stocke que les points caractéristiques de l'image (extrémité d'une droite, centre et un autre point pour un cercle, ...)

1) adaptable à chaque périphérique (car ajustable, coordonnées relatives, adaptable aux drivers intelligents, ...)

2) stockage moins encombrant (la taille ne dépend que de la complexité du document lui même)

3) adapté aux objets mathématiques et leur extension (voiture, avion , ...)

1) mal adapté aux images quelconques

2) difficulté de traitement d'une partie de l'image

3) travail d'interprétation à faire => temps de traitement => processeur adapté ou UC ?

3 canons RGB (Rouge, Vert, Bleu)

valeur numérique -> valeur analogique DAC (convertisseur digitaux analogiques)

Valeur du triplet RGB = une valeur de couleur

exemple :

(0,0, max) => bleu foncé

(0, 0, 0) => noir

l'oeil humain voit 16 millions § 2^24 = 2^(3x8) couleurs => TrueColor

En général on n'a pas 24 bits pour un pixel (i.e. un point élémentaire à l'écran) mais 8. On parle alors de fichier pixmap au lieu de bitmap. Le nombre de bits pour décrire la couleur d'un pixel est appelé la profondeur.

Donc 2^8 = 256 couleurs à un instant donné (choisi parmi 16,7 millions).

Ces 2^8 couleurs sont stockées dans une palette (table de couleur, colormap, look-up table, LUT, palette, É).

On repère les couleurs par un indice dans cette colormap.

donc afficher du noir = afficher le pixel d'indice 5

ATTENTION

pixel a deux sens :

- point élémentaire à l'écran

- indice dans une table de couleur

Remarque

Si on change de table de couleur

afficher pixel d'indice 5 = afficher Rouge => flash

Conclusion

Il faudra une table de couleurs dans un fichier d'image

On ajoute des couleurs à la couleur noire.

Plus on ajoute de la couleur plus on rapproche du blanc

exemple : les écrans.

On enlève des couleurs à la couleur blanche (qui "contient" toutes les couleurs).

Plus on ajoute une couleur plus cette couleur absorbe (donc enlève) sa couleur complémentaire.

le cyan absorbe le rouge, le magenta absorbe le vert, le jaune absorbe le bleu.

exemple : l'impression sur papier blanc, la photographie.

classement proche de l'humain.

3 notions : famille, saturation, brillance.

- famille des rouge, des verts, ...

- saturation claire à foncée

- l'intensité

Une valeur supplémentaire est parfois ajoutée pour décrire le degré de trannsaprence (vitre d'une voiture, ...)

système RGB.

système YUV : signaux Y (luminance), U et V (chrominances i.e. informations pour la couleur). C'est une transformation linéaire du système RGB. Y est une echelle de gris : c'est le seul coefficient utilisé pour les téléviseurs noirs et blanc. Les téléviseurs couleurs utilisent les 3 coefficients.

système CMY (Cyan, Magenta, Yellow). En fait, les 3 couleurs réunies ne donnent pas un "beau" noir (mais un "vilain" beige). On ajoute alors une composante noir pour obtenir une échelle à 4 valeurs CMYK.

système HSV (Hue, Saturation, Value) ou HSB (Hue, Saturation, Brightness).

Hue est la couleur (i.e. la famille)

Saturation (ou chroma) est la "quantité de blanc" dans la couleur : être 100% saturé = couleur "pure", être peu saturé = couleur pâle. par exemple rouge saturé à 50% est un rose.

Value est "l'intensité émise" : grande intensité = très brillant, peu d'intensité = proche du noir.

Divers algorithmes

appelé encore RLE (Run Length Encoding)

Utilisé dans TIFF, BMP, PCX

sans perte

Idée de base : regrouper les points consécutifs ayant même valeur.

Exemple :

aaaaaaaaaaaaaaa

est codé

15a

mal adapté aux fichiers ayant peu de répétitions successives (texte, image digitalisé, É)

Jakob Ziv et Abraham Lempel (1977, 78)

implanté par Terry Welch (1984) dans les contrôleurs de disque.

utilisé dans :

- les formats d'images GIF, TIFF 5.0 (1988)

- la norme V42bis des modems

- Postscript niveau 2

- les commandes de compression compress, zoo, ...

utilise un "dictionnaire"

les entrées 0-255 sont les lettres de l'alphabet.

les entrées 256-4095 sont des chaînes (i.e. plusieurs caractères consécutifs)

Chaque entrée est donc sur 12 bits.

En compression on lit les données de sorte à former des chaînes. Si une chaîne construite n'existe pas dans le dictionnaire on crée une entrée dans ce dictionnaire et on l'ajoute.

Donc chaque nouvelle chaîne ajoutée au dictionnaire est formée d'une chaîne déjà existante suivi du "caractère courant".

L'algorithme est :

Exemple d'exécution :

chaîne à coder : /QED/QE/QEE/QEB

Le code de la chaîne /QED/QE/QEE/QEB est la première colonne soit :

/ ; Q ; E ; D ; 256 ; E ; 260 ; 261 ; 257 ; B

Pour décoder on a l'algorithme similaire à l'encodage !! :

Exemple d'exécution :

chaîne à décoder :

/ ; Q ; E ; D ; 256 ; E ; 260 ; 261 ; 257 ; B

La sortie décodée est la seconde colonne :

/QED/QE/QEE/QEB

- les algorithmes de compression et de décompression construisent évidemment le même dictionnaire.

- compression/décompression sans perte

- rapide pour compresser comme pour décompresser

- on utilise un dictionnaire qui N'est PAS transporté (mais construit au fur et à mesure dans la compression comme dans la décompression)

Pour tout programme de compression sans perte, pour tout entier N, il existe un fichier de taille > N qui n'est pas compressé strictement.

remarque préliminaire :

Dans un programme de compression sans perte deux fichiers distincts donnent 2 fichiers compressés distincts.

démonstration :

Par l'absurde

Soit un programme de compression qui diminue strictement les fichiers de taille plus grand que N. Supposons que tous les fichiers de taille supérieure à N compressés par ce programme le sont sans perte. Montrons qu'on arrive à une contradiction.

On considère tous les fichiers de taille exactement N bits.

Il y en a 2^N.

Tous les fichiers ont au plus N-1 bits (compression stricte)

Or il y a :

- 2^(N-1) fichiers de N-1 bits

- 2^(N-2) fichiers de N-2 bits

- ...

- 1 fichier de taille 0 bit

donc on obtient 2^N-1 fichiers compressés (2^(N-1) + 2^(N-2) + ... + 1)

En résumé

Au départ 2^N fichiers à compresser

A l'arrivée 2^N - 1 fichiers compressés.

donc 2 fichiers distincts ont donné le même fichier compressé contradiction

Remarque

démonstration purement mathématique pas de théorie de l'information.

Conclusion

Le théorème dit donc qu'un programme de compression strict sans perte n'existe pas.

Un programme de compression strict est un programme de compression avec perte.

= Joint Photographic Experts Group (le comité dépendant de l'ISO qui initialement a écrit ce standard)

écrit par Tom Lane, Philip Gladstone and al

si problème difficile les joindre à

jpeg-info@uu.net ou encore

Tom_Lane@g.gp.cs.cmu.edu

utilisé par :

- JFIF (JPEG File Interchange Format)

- TIFF 6.0 (Juin 1992)

- TGA, É

algorithme avec perte donc

- usage limité à des données dont les changements sont imperceptibles pour un humain (son, image mais pas programme ou fichier de données quelconques)

- éviter les phases successives de compression/décompression

- meilleure performance (taux de compression 20:1, rapidité de compression/décompression)

L'oeil humain est plus sensible aux changements de brillance que de couleurs voisines => JPEG plus performant pour des couleurs que pour le noir et blanc.

peut manipuler la TrueColor (16 millions de couleur) !! (alors que GIF seulement 256 couleurs) donc très performant sur des écrans 24-bit => le format du futur ?

La qualité de compression et la qualité du résultat est paramétrable par l'utilisateur (le facteur Q)

C'est difficile !!

voir le code disponible à ftp.uu.net fichier

/graphics/jpeg/jpegsrc.v5.tar.gz

utilise le codage d'un pixel en

luminance Y = 0,6G+0,3R+0,1B

2 signaux de chrominance

U = Y-B et V = Y-R

- Division de l'image (système YUV) en blocs de 8x8 pixels

- On applique la DCT (Discrete Cosine Transform) à chaque bloc (FDCT = Forward DCT)

- Quantification des coefficients => perte d'informations paramétrable avec "facteur de qualité"

- "codage entropique" (sans perte)

Pour décoder on fait les opérations inverses

FDCT et IDCT utilisent les équations :

pour encoder les blocs de 8x8 bits

et

pour décoder

avec

pour u, v=0

et

pour sinon

C'est la principale source de perte d'information de l'algorithme.

On divise chaque coefficient F(u,v) par son coefficient de quantifieur associé et on arrondi à l'entier le plus proche :

la déquantification est :

Les tables de quantification sont par exemple des tables "normalisées" CCIR-601

elle utilise un algorithme d'Huffman

Compresser est une chose. Le format des fichiers images en est une autre.

On peut avoir un certain format de fichiers et lui associer un ou plusieurs algorithmes de compression.

Par exemple suivant les versions, le format TIFF utilise les algorithmes de compression :

- pas de compression (jusqu'à la version 4.0 N&B)

- RLE

- LZW

- CCITT group 3 et 4

- JPEG

Les fichiers peuvent être organisés sous la forme :

Si les valeurs des pixels sont codées à l'aide d'une palette on obtient :

En cas de plusieurs images présentes dans un fichier on a:

Si chaque image nécessite sa propre palette on obtient :

Pour décrire les champs on utilisera les conventions :

CHAR 8-bit signé

BYTE 8-bit non signé

WORD 16-bit non signé (entier)

DWORD 32-bit non signé (entier)

LONG 32-bit signé (entier)

FLOAT 32-bit flottant (simple précision)

DOUBLE 64-bit flottant (double précision)

= Graphics Interchange Format

créé par CompuServe Inc.

supporte jusqu'à 256 couleurs

compression LZW et c'est le seul : pas de fichier GIF non compacté, ni compacté par autre algorithme que LZW

taille maximale de l'image : 64Kbx64Kb pixels

peut contenir plusieurs images par fichier (mais souvent n'en contient qu'une)

Attention certains viewer GIF ne peuvent pas afficher plusieurs images d'un fichier GIF.

utilise le modèle RGB et les palettes

Deux révisions : GIF87a (Mai 87) et GIF89a

l'en tête et le descripteur logique d'écran sont de type GIFHEAD :

typedef struct _GifHeader {
   /* En tête */
   BYTE Signature[3]; /* = "GIF" */
   BYTE Version[3]; /*"87a" ou "89a" */
   /* Descripteur logique d'écran */
   WORD ScreenWidth; /*largeur écran (en pixels) */
   WORD ScreenHeigth; /*hauteur écran (en pixels) */
   BYTE Packed; /*info sur écran et palette globale */
  BYTE BackgroundColor; /* couleur de fond*/
  BYTE AspectRatio;
} GIFHEAD;

ScreenWidth et ScreenHeigth est la résolution minimale de l'écran pour afficher l'image correctement. Sans cela des calculs de recadrage devront être effectués.

Packed contient des informations sur la palette globale :

bit 0-2 : taille des entrées de la palette globale (i.e. nombre de bits - 1 d'une entrée)
bit 3 : = 0 (pour 89a)
bit 4-6 = 0 (pour 89a)
bit 7 : bit de présence de la table de couleur globale (= 1 => il y en une)

BackgroundColor est la couleur de fond i.e. l'aire de dessin non couverte par l'image.
AspectRatio est largeur_Pixel/hauteur_pixel.

La palette globale est optionnelle. C'est en général la seule palette du fichier. Elle est valide pour les images n'ayant pas leur propre palette.

Les entrées de cette palette sont des triplets de type :

typedef struct _GifColorTable {
BYTE Red;
BYTE Green;
BYTE Blue;
} GIFCOLORTABLE;

Le nombre d'entrées de cette palette est une puissance de 2 (au plus 256 entrées). C'est d'ailleurs :

1L << (Bit0-2dePacked + 1)

Un bloc image i est de la forme :

Le descripteur local d'image a pour type :

typedef struct _GifImageDescriptor {
   BYTE Separator; /* = 2Ch */
   WORD Left;
   WORD Top;
   WORD Width;
   WORD Height;
   BYTE Packed;
   /* Descripteur logique d'écran */
} GIFIMGDESC;

Separator indique le début du descripteur.

Left et Top indique les coordonnées du coin haut-gauche de l'image par rapport à l'écran logique.

Width et Height est la taille de l'image en pixels.

Packed contient des informations sur l'image :

bit 0 : bit de présence de la palette locale (=1 elle est présente et on l'utilise pour l'image. =0 on utilise la palette globale)
bit 1 : = 1 image entrelacée, = 0 non entrelacée.
bit 2 = 0 (pour 89a)
bit 3-4 : pour futur
bit 5-7 : nombre de bits pour chaque entrée de la palette locale

La palette locale a la même structure que la palette globale. Elle la remplace si elle est présente.

Les données images sont LZW compactées.

Elles sont stockées en suite de blocs. Le premier octet indique la taille du bloc. Le bloc est terminé par un octet NULL (redondance)

remarque : on peut décoder les blocs indépendamment les uns les autres (voire en parallèle)

Chaque pixel est un indice dans la palette associée à l'image.

Une image GIF est une suite de lignes de l'image. Chaque élément de l'image est un point.

GIF peut choisir (c'est souvent le cas) de stocker les données de manière non entrelacées (i.e. consécutivement) ou entrelacées :

- d'abord les lignes 0, 8, 16, ... (O mod 8)

- puis les lignes 4, 12, 20, ... (4 mod 8)

- puis les lignes 2, 6, 10, 14, ... (2 mod 4)

- enfin les lignes 1, 3, 5, 7, ... (1 mod 2)

=> effet de store vénitien à l'affichage mieux que consécutifs.

Des outils permettent de construire un gif animé en incorporant une suite d'image Gif.

Les logiciels de création de gif animés sur diverses plateformes sont à :

http://members.aol.com/royalef/toolbox.htm

Il existe des logiciels (payants) qui permettent de créer des animations par glisser-déposer et de sauvegarder le résultat dans un gif animé (ou une applet Java). Par exemple Object Dancer.

On peut citer les travaux de Yves Piguet (EPFL) à :

http://iawww.epfl.ch/Staff/Yves.Piguet/clip2gif-home/GifBuilder.html

l'outil est GifBuilder.

"GifBuilder 0.5 F est un utilitaire scriptable pour créer des GIF animés sur le

Macintosh. Il peut être utilisé manuellement pour réunir des images PICT, GIF, TIFF et/ou Photoshop ou pour convertir des films

QuickTime, FilmStrip ou PICS.

Les GIF animés peuvent être affichés par Netscape 2.0 ou plus, Microsoft Internet Explorer 2.1 ou plus. GifBuilder est freeware."

On construit les fichiers GIF (capture d'écran) et GIFConverter (shareware) par exemple.

Les images sont ajoutées par glisser-déposer.

standard ISO pour encoder de l'audio, de la vidéo, du texte, des images dans un flot de données synchronizées.

Cette norme ISO CD 11172 est payante, peut être commandée à l'ANSI et contient 4 parties :

11172.1 Synchronization and multiplexing of audio-visual information

11172.2 Video Compression

11172.3 Audio Compression

11172.4 Conformance testing

Le groupe de travail ISO est Motion Picture Experts Group (MPEG). Le premier but est de stocker des données son et vidéo sur des CD audio et DAT. Par la suite sur des CD-ROM (mac et Windows)

MPEG n'est pas une suite d'images JPEG (!= gif animé). Une animation fait comme suite d'images MPEG dans un fichier est du MJPEG (avec en plus de la compression audio)

MPEG utilise à la fois de la compression spatiale d'images comme JPEG mais aussi de la compression temporelle (cf ci dessous)

MPEG utilise l'échelle YCbCr (variante de YUV)

En MPEG, compresser et plus difficile que décompresser i.e. construire des données MPEG est plus difficile que les lire.

Un flot MPEG = suite de trames

2 sortes de compression : compression "intertrame" ou temporelle et "intratrame" ou spatiale.

La compression intertrame consiste à avoir des "trames de synchronisation" et des déduire les autres trames à partir de celles là.

La compression spatiale est de compresser une trame en utilisant une compression DCT (cf. JPEG)

Il y a 3 sortes de trames en MPEG :

- trame I (trame indépendante)

- trame P (trame prédite)

- trame B (trame bidirectionelle)

Une trame I code une information vidéo indépendamment d'autres trames. Un flot MPEG commence par une trame I.

Une trame P est construite à partir de la trame P ou I la plus proche qui la précède. En fait seuls les changements ("deltas") entre cette trame et sa précédente de reférence sont codés.

Une trame B est construite à partir de 2 trames P ou I les plus proche et qui l'encadrent.

Un flot MPEG est de la forme :

IBBPBBPBBPBBIBBPBBPBBI

En pratique environ 12 trames B ou P entre 2 trames I, une trame I toutes les 0,4 secondes.

Chaque trame est ensuite compressée par l'algorithme de DCT comme le format JPEG.

L'ordre de décompression n'est pas l'ordre des trames dans le flot. Un flot de trames :

IBBPBBPBBI (0123456789) est décompressé dans l'ordre :

IPBBPBBIBB (0312645978)

puis affiché

IBBPBBPBBI (0123456789)

Le standard MPEG n'indique la quantité de trame P et B à utiliser. Un flot MPEG constitué uniquement de trames I et un MJPEG. Il est facile à obtenir car ce sont les trames B et P qui rendent la construction d'un flot MPEG difficile. Par contre il est très peu compressé.

développé par Apple pour l'audio et la vidéo.

non seulemement un format mais un ensemble d'outils associés (la Movie Toolbox) permettant d'éditer, de construire des films en couper, copier, coller, ...

est utilisé sur mac ou Windows

permet de stocker des pistes multiples audio (un même film dans plusieurs langues) et des pistes multiples de vidéo (panneau interactifs du film dans plusieurs langues). Peut contenir un "preview" vidéo du film (de 5 sec), un poster.

utilise des formats de compression propriété Apple (hormis JPEG).

environ 50% de la vidéo sur le Web est en format QuickTime (New Media Magazine Septembre 1997).

D'autres produits multimédia comme Adobe After Effects, Avid Cinema, Adobe Premiere s'appuient sur QuickTime.

Encyclopedia of graphics file formats James D.Murray, W. VanRyper ed 0'Reilly

FAQ JPEG à ftp://rtfm.mit.edu:/pub/usenet/news.answers/jpeg-faq

ou e-mail à mail-server@rtfm.mit.edu avec la ligne

send usenet/news.answers/jpeg-faq

FAQ compression à ftp://rtfm.mit.edu:/pub/usenet/news.answers/compression-faq

FAQ formats de fichiers graphiques à ftp://rtfm.mit.edu:/pub/usenet/news.answers/graphics/fileformats-faq/

A. Didier Le Gall, "MPEG: A Video Compression Standard for Multimedia

Applications," Communications of the ACM, April 1991, Vol.34, No.4, pp. 47-58

Inside Macintosh, Imaging and QuickTime volumes, Addison Wesley

http://www.quicktime.apple.com/

http://www.quicktimefaq.org

rapport d'exposé : Le format gif animé, Cédric JOUBERT, John REGNIER. valeur C Conception d'Applications Multimédia (CAM) CNAM 1997.