Mots-clés : réseaux de neurones ; compression d'images ; apprentissage automatique ; fractales.

annotation

Cet article présente une méthode permettant de réduire le temps de codage pour la compression d'images fractales. Cette approche combine l'extraction de fonctionnalités avec la classification de domaines à l'aide d'un réseau neuronal auto-organisé. L'extraction de fonctionnalités réduit la taille de la tâche et permet au réseau neuronal de s'entraîner sur une image différente de celle en cours d'encodage. Un réseau neuronal auto-organisé pour la classification introduit le concept de topologie de cluster et élimine également le besoin de spécifier a priori de nombreuses classes d'images appropriées. Le réseau s'organise en fonction de la répartition des caractéristiques des images obtenues lors du processus de formation. L'article présente des résultats qui montrent que l'approche de classification peut réduire le temps de codage de deux ordres de grandeur tout en conservant une précision comparative et une efficacité de compression.

1. Introduction

Le codage d'images fractales est une approche prometteuse dans les applications de compression d'images telles que les sites Internet. Cependant, le temps requis pour la phase de codage de cette approche a constitué un obstacle à son adoption en tant que méthode pratique. Le processus de codage consiste à mapper les blocs de domaine en blocs d'images de rang. Pour chaque bloc de classement, l'algorithme recherche un bloc de domaine et la transformation correspondante qui fourniront la meilleure correspondance avec le bloc de classement. La classification par blocs de domaines peut accélérer considérablement le codage en réduisant le nombre de domaines à rechercher. L'utilisation de réseaux de neurones auto-organisés à des fins de classification de domaines a déjà été explorée. Ces réseaux apportent une amélioration par rapport aux approches de classification de base en identifiant la topologie des clusters de classes. La contribution de ce travail est de combiner la classification de domaine à l'aide d'un réseau neuronal auto-organisé avec l'extraction de caractéristiques pour permettre un codage d'image encore plus rapide. Un petit ensemble de caractéristiques d'image mesurant les qualités de tonalité et de texture sont calculés pour chaque domaine et bloc de classement. Ainsi, à chaque bloc est associé un vecteur de caractéristiques dont la taille ne dépend pas de la taille du bloc. L'extraction de fonctionnalités est bénéfique pour deux raisons. Premièrement, la réduction de la taille du problème qui en résulte réduit la quantité de calcul requise dans le processus de recherche de domaine. Deuxièmement, puisque les caractéristiques sont indépendantes de la structure des domaines spécifiques, il devient possible de former un réseau auto-organisé sur une image et d'utiliser le réseau résultant pour une classification sur d'autres images. Ainsi, le temps de formation du réseau ne fait pas partie du temps total de codage. Les mesures du temps de codage des images fractales sont généralement exprimées en termes de temps d'exécution sur un poste de travail Sun ou Silicon Graphics. L'approche présentée ici fournit des mesures comparables lorsqu'elle est exécutée sur un PC Pentium 120 MHz.

2. Codage fractal des images

Le codage fractal des images est basé sur la théorie des systèmes de fonctions itérées (ci-après abrégé en IFS, de l'anglais Iterated Function System - IFS). La théorie CIF est basée sur le théorème de cartographie de contraction (ci-après abrégé en TOC, de l'anglais Contraction Mapping Theorem - CMT) issu de l'analyse classique, qui est utilisé pour construire des images fractales de manière itérative. Une image fractale est un point fixe dans l’espace image, garanti par TOS, et cette image est appelée attracteur CIF. Le problème inverse, résolu par le codage d'images fractales, commence par considérer une image donnée et calculer le SIF, qui représente une image proche de celle donnée - son attracteur. Le code d’image fractale nécessite généralement (mais pas toujours) moins d’espace de stockage que l’image originale, ce qui en fait une technique de compression. Les résultats empiriques montrent que dans de nombreux cas, la méthode fractale est aussi efficace que le JPEG, qui est aujourd'hui considéré comme le standard de compression.

La compression d'images fractales utilise un type spécial de PIF appelé système de fonctions itérées partitionnées (PIFS). Le CICF se compose d'un espace métrique complet X, d'un ensemble de sous-domaines D i ⊂ X, i = 1,...,n, et d'un ensemble de transformations de contraction w i ~ : D i → X, i = 1,... ,n. Nous considérons les images en niveaux de gris comme des fonctions de valeurs réelles f(x, y) définies sur une région carrée I 2 = I×I . Soit w i ~ (x, y) une transformation affine I 2 → I 2 telle que

à condition que w i ~ soit inversible et (x, y) ∈ R i . La constante s i élargit ou rétrécit la plage de valeurs de la fonction f et, puisque nous parlons d'images en niveaux de gris, elle contrôle le contraste. De même, la constante o i augmente ou diminue les valeurs d'échelle de gris ou contrôle la luminosité. La transformation w i ~ est appelée la composante spatiale de la transformation w i .

L'algorithme de base est exécuté comme suit. Nous divisons l’image en blocs de rang rectangulaires (Ri) qui ne se chevauchent pas. Les blocs R i peuvent avoir la même taille, mais le plus souvent, une sorte de partitionnement avec une taille de bloc variable est utilisée, ce qui permet de remplir de manière dense des parties de l'image contenant de petits détails avec des blocs de petit rang. Les résultats présentés ici ont été obtenus en utilisant le schéma de partition quadtree décrit dans . Nous couvrons l'image avec une séquence de blocs de domaines, éventuellement superposés. Les domaines peuvent être de différentes tailles et se comptent généralement par centaines, voire par milliers. La transformation affine (2.1) est une transformation de contraction spatiale si |det A i |

(2.3)

était petit. Pour les images numérisées, l'intégrale (2.3) est remplacée par la sommation sur les pixels. Si, après avoir trouvé le meilleur w i , la valeur (2.3) est toujours supérieure à une erreur prédéterminée, alors le schéma de partitionnement en quatre arbres divise le rang en quatre rectangles plus petits et le processus de recherche de la transformation optimale est répété pour ces blocs plus petits. Ce processus se poursuit jusqu'à ce que la valeur (2.3) devienne inférieure à l'erreur tolérée ou jusqu'à ce qu'une profondeur maximale prédéterminée d'arbre quadruple soit atteinte. L'image est décodée en appliquant itérativement la transformée W à l'image f, où

W(f)(x,y) = w i (f)(x,y) pour (x,y) ∈ R i

Si les transformations (wi) ont été choisies correctement, alors l'itération W 0n (f) sera proche de l'image originale pour une valeur de n suffisante. L'étape de codage nécessite beaucoup de calculs en raison du grand nombre de domaines qui doivent être recherchés pour chaque bloc de rang, ainsi que des calculs requis chaque fois qu'un domaine est comparé à un rang. Dans ce travail, la réduction des exigences informatiques de l’étape de codage est abordée de deux manières. Tout d’abord, le concept de caractéristiques d’image définies pour chaque domaine et bloc de rang est introduit. Les domaines potentiellement adaptés peuvent alors être sélectionnés sur la base des valeurs d'un nombre de ces caractéristiques inférieur aux valeurs des pixels eux-mêmes. Deuxièmement, il est proposé d'organiser les blocs de domaines dans une topologie de cluster en utilisant un réseau neuronal auto-organisé. Cela réduit encore le temps de codage en permettant au réseau de localiser rapidement dans l'espace des fonctionnalités les blocs de domaine similaires aux blocs de classement.

3. Extraction de fonctionnalités

Une façon d’accélérer le processus de codage fractal des images consiste à isoler un petit nombre de caractéristiques qui décrivent les blocs de domaine et de classement. Ensuite, la comparaison des blocs de domaine et de rang est effectuée sur la base de ces caractéristiques, et non sur des pixels individuels, ce qui réduit la quantité de travail. Dans ce travail, six caractéristiques sont utilisées pour décrire la distribution de la texture et du contraste de l'image. L’extraction de fonctionnalités elle-même accélère considérablement le processus de codage.

Les six caractéristiques suivantes sont utilisées ici : 1) écart type, σ ; 2) asymétrie (asymétrie), qui est la somme des cubes des différences entre les valeurs des pixels et la valeur moyenne du bloc, normalisée par le cube σ ; 3) le contraste interpixel (contraste voisin), qui mesure la différence entre les valeurs des pixels voisins ; 4) bêta, qui montre à quel point les valeurs des pixels diffèrent de la valeur au centre du bloc ; 5) gradient horizontal, qui caractérise le changement horizontal des valeurs des pixels du bloc ; 6) dégradé vertical, qui caractérise le changement des valeurs des pixels du bloc de haut en bas. La valeur moyenne des pixels n'est pas utilisée comme caractéristique puisque le contraste et la luminosité changent au cours du processus de correspondance entre les blocs de domaine et de classement. Lors de la comparaison des distances dans l'espace des caractéristiques, le vecteur de caractéristiques est normalisé pour garantir que les valeurs de caractéristiques élevées ne dominent pas la comparaison.

4. Réseaux de neurones auto-organisés

La prochaine amélioration qui peut être apportée consiste à classer les domaines et les classements en fonction de ces caractéristiques et à comparer les classements uniquement aux domaines de classes similaires. Le schéma de classification de domaine utilisé ici est basé sur un réseau neuronal Kohonen auto-organisé. Ce type de réseau est constitué d'un réseau de positions de nœuds. Chaque nœud du réseau est associé à un vecteur de poids, qui a la même dimension que la dimension des vecteurs caractéristiques. La dimension des vecteurs de caractéristiques utilisés ici est de 6. Et le réseau de nœuds utilisé ici se compose de 10 lignes et 10 colonnes. Chaque nœud représente une classe de blocs de domaine d'image, nous visons donc à maintenir le nombre total de nœuds assez petit. D'autres manières d'organiser les nœuds, telles que des matrices de dimension supérieure, peuvent être envisagées.

Le processus d’apprentissage se déroule de manière indépendante, sans aucun contrôle humain. Le réseau de vecteurs de poids est initialisé avec des valeurs aléatoires. Ensuite, le réseau reçoit un vecteur de caractéristiques d'entrée et nous trouvons le vecteur de poids le plus proche du vecteur d'entrée. Autrement dit, nous trouvons que je suis tel que

||v – w je'j' || ≤ ||v – w ij || pour tout ce que je, j

où v est le vecteur de caractéristiques d'entrée et w est le vecteur de poids au nœud ij. Les poids adjacents sur le réseau au poids sélectionné w i'j' sont adaptés pour ressembler davantage au vecteur d'entrée. Cette adaptation s'exprime par la formule

w ij nouveau = w ij ancien + ε·exp(α·||v–w ij ancien || 2)·(v– w ij ancien)

où ij sont les indices des nœuds qui sont au voisinage du nœud i’j’. La taille de ce voisinage diminue à chaque nouvelle itération du processus d’apprentissage. Le paramètre ε est le pas d'itération, et α est inversement proportionnel à ce pas. L'implémentation logicielle des résultats présentés est donnée ci-dessous.

Une fois le réseau entraîné, les blocs de domaine pour une image donnée sont classés en attribuant à chacun d'eux le vecteur de poids qui s'en rapproche le plus dans l'espace des fonctionnalités. Lorsque le vecteur de caractéristiques d'un bloc de classement entre dans le réseau, il est également associé au vecteur de poids du réseau. Le bloc de classement est ensuite comparé aux domaines associés à ce vecteur de poids, ainsi qu'aux domaines associés aux vecteurs de poids adjacents sur le réseau. L'avantage de la classification basée sur un réseau de neurones auto-organisé réside dans l'idée d'organiser les classes d'images en classes adjacentes, ce qui est assuré par le réseau de réseau. Un autre avantage est que ce regroupement de types d’images se produit sans qu’il soit nécessaire de prédéfinir des classes d’images.

5. Résultats

Le tableau 1 présente les résultats d'une comparaison de la compression d'images fractales utilisant trois méthodes différentes, appliquées aux images présentées dans les figures 1 et 2. La méthode « de base » est la méthode standard de partitionnement en quad-arbre discutée dans , sans classification de domaine. La valeur « niveau quadtree » indique la profondeur maximale autorisée du quadtree. Ici, un grand nombre conduit à des blocs de rang plus petits, ce qui conduit à une meilleure qualité de l'image décodée, mais en même temps à une moins bonne compression. Le « seuil d'erreur » est un paramètre qui contrôle la condition de division des blocs de rang en blocs plus petits du niveau immédiatement supérieur de l'arbre quadruple. Les valeurs d'erreur sont calculées en comparant le bitmap d'origine avec l'image décodée à l'aide de 6 itérations (plus d'itérations produiraient des erreurs légèrement plus petites). « Erreur moyenne » est l'erreur moyenne par pixel, tandis que « PSNR » est le rapport signal/bruit maximal, calculé comme dans . La méthode « FO » (fonctionnalités uniquement) compare les blocs de domaine et de classement sur la base des six caractéristiques décrites dans la section 3. La méthode finale (« SO ») classe les domaines à l'aide d'un réseau neuronal auto-organisé d'extraction de caractéristiques, comme indiqué ci-dessus. Dans chaque cas, un total de 320 blocs de domaines ont été utilisés. Un plus grand nombre de domaines entraînerait des temps d'encodage plus longs et, dans une certaine mesure, de meilleurs taux de compression.

Les taux de compression sont estimés par le rapport d'une moyenne de 4 octets pour chaque bloc de rang aux 66 614 octets du bitmap d'origine. La méthode SO est environ deux fois plus rapide que la méthode FO et cent fois plus rapide que la méthode de base (le « temps par bloc » exprime une mesure du temps d'exécution indépendante de la précision de l'image finale ; les temps donnés ici sont pour un Pentium PC 120 MHz). Le réseau auto-organisé a été formé séparément sur une image différente des deux images présentées ici, de sorte que le temps de formation n'est pas inclus dans le temps total de cette méthode. Le degré de compression et la qualité de l'image décodée, aussi bien avec les méthodes accélérées qu'avec la méthode de base, sont comparables.

Tableau 1 - Résultats de la compression d'images fractales à l'aide de la classification de domaines auto-organisés (« méthode SO »), de la comparaison des domaines basée uniquement sur les caractéristiques (« FO ») et de la méthode de base (« Base »)

	Image	Seuil d'erreur	Niveau quad-arbre	Nombre de blocs	Temps, (s)	Temps par bloc, (s)	Erreur moyenne, %		Coeff. compression
(UN)	(b)

Figure 2 - (a) : Image raster originale « Feuilles » (256×256, 256 niveaux de gris) ; (b) : Image décodée (6 itérations, niveau quad-tree 7, erreur moyenne de pixel 3,05 %, compression 1,6 : 1). Des niveaux de détail plus élevés dans cette image entraînent des performances plus lentes

6. Conclusions

La combinaison de l'extraction de fonctionnalités avec la classification de domaines par un réseau neuronal auto-organisé permet une accélération significative du codage. La classification d'une image basée sur un petit nombre de caractéristiques réduit non seulement la quantité de calcul impliquée, mais permet également au réseau d'être formé sur une image autre que celle en cours de codage, éliminant ainsi le temps de formation du temps de codage global. Un réseau auto-organisé établit son propre ensemble de classes de domaine représentatives et définit également une topologie de cluster de classes de domaine.

Littérature

1. E. DeJesus, « Walking, Talking Web », Byte, janvier 1997, p. 81-84.
2. Y. Fisher, éd., Fractal Image Compression, (New York : Springer-Verlag, 1995).
3. A. Jacquin, « Codage d'images basé sur une théorie fractale de transformations d'images contractives itérées », IEEE Trans. Processus d'image. 1, 1992, 18-30.
4. A. Bogdan et H. Meadows, « Réseau neuronal Kohonen pour le codage d'images basé sur la théorie de la transformation itérative », Proc. SPIE 1766, 1992, 425-436.
5. R. Hamzaoui, « Codebook clustering by self-organizing maps for fractal image compression », NATO ASI Conf. Sur l'encodage et l'analyse d'images fractales, juillet 1995.
6. M. Barnsley, Fractals Everywhere, 2e éd. (Boston : Presse académique, 1993).
7. T. Kohonen, Auto-organisation et mémoire associative, (Springer-Verlag, 1989).
8. S. Welstead, Réseaux neuronaux et applications de logique floue en C/C++, (New York : John Wiley and Sons, 1994).

Avec la quantification vectorielle, un groupe de N échantillons d'un signal numérique est codé simultanément ( N- vecteur dimensionnel). Dans le cas d'un signal unidimensionnel, les vecteurs peuvent être des groupes de N comptes consécutifs. Dans le cas d'une image, les vecteurs peuvent être des blocs de plusieurs éléments d'image adjacents horizontalement et verticalement. En figue. La figure 5.54 montre un schéma fonctionnel d'un système de transmission d'informations qui utilise la quantification vectorielle.

La signification de la quantification vectorielle est la suivante. L'ensemble de tout ce qui se produit dans un signal N-les vecteurs dimensionnels sont divisés en L sous-ensembles de sorte que les vecteurs inclus dans chaque sous-ensemble diffèrent peu les uns des autres. Dans chaque sous-ensemble, un vecteur de référence est sélectionné pour représenter tous les vecteurs de ce sous-ensemble. Tous les vecteurs de référence sont écrits dans un livre de codes et chacun d'eux se voit attribuer un mot de code spécifique.

Entrée numérique x(n) arrive à l’entrée du codeur. La procédure de codage est que pour chaque vecteur à N dimensions du livre de codes, il existe un vecteur de référence le plus proche, dont le code est envoyé à la sortie du codeur. Ainsi, pour chaque groupe de N- échantillons de signaux d'entrée x(n) un mot de code est transmis Royaume-Uni).

Dans le décodeur conformément au mot de passe reçu Royaume-Uni)(la barre indique que le signal est arrivé sur le canal de communication) le vecteur de référence est lu dans le livre de codes et converti en un groupe de Néchantillons de signal de sortie o(n). Le livre de codes peut varier en fonction des propriétés du signal codé.

La quantification vectorielle est une méthode de compression avec perte, et comme de vrais groupes de Néchantillons de signal d'entrée X(n) dans le signal de sortie o(n) sont remplacés par ceux de référence N- des vecteurs dimensionnels. L'un des avantages de la quantification vectorielle est la simplicité du décodeur, qui effectue uniquement l'opération de lecture du vecteur de référence dans le livre de codes.

Parallèlement, la recherche dans le codeur du vecteur de référence le plus proche de celui en cours de codage nécessite un grand nombre de calculs. Le vecteur de référence le plus proche est lu dans le livre de codes lorsque la valeur minimale de l'erreur quadratique de quantification est atteinte. E :

E= S (aj-bj) 2 ,

Où un J- les éléments du vecteur d'entrée ; bj– éléments du vecteur de référence.

Le codage d'images fractales est proche de la quantification vectorielle, dans lequel des blocs découpés dans l'image originale elle-même sont utilisés comme éléments du livre de codes.

Les méthodes de compression fractale peuvent être considérées comme une modification de la quantification vectorielle, dans laquelle des blocs découpés de diverses manières dans l'image originale elle-même sont utilisés comme éléments du livre de codes. Il est possible de transformer les blocs de l'image codée, permettant à ces blocs d'être similaires aux blocs de référence (rotations, réflexions miroir). La quantification vectorielle et le codage fractal peuvent être utilisés en télévision, offrant une compression significative de l'information.

Cependant, la grande quantité de calcul impliquée dans le codage empêche l'utilisation de ces méthodes dans les systèmes de télévision numérique.

Questions de contrôle

1. Dans quel ordre les blocs d'images couleur sont-ils codés selon la norme JPEG ?

2. Pourquoi la quantification des coefficients DCT crée-t-elle des distorsions moins visibles que la quantification de l'image elle-même ?

3. Comment la norme JPEG contrôle-t-elle le degré de compression ?

4. Quelle est l’essence du codage avec des mots de code de longueur variable ?

5. Que signifie le terme « codage hybride » par rapport aux normes MPEG-1, MPEG-2 ?

6. Pourquoi les images sont-elles réorganisées dans GOP avant d'encoder MPEG-1, MPEG-2 ?

7. Quelle est la différence entre les modes de codage de trame et de champ en MPEG-1, MPEG-2 ?

8. Pourquoi pour B-les images ont atteint le plus haut degré de compression ?

9. À quoi sert la mémoire tampon de l'encodeur MPEG-2 ?

10. Qu'est-ce que l'évolutivité ?

11. Que sont les niveaux et profils MPEG-2 ?

12. Comment les données des différents programmes TV sont-elles extraites du flux de transport MPEG-2 ?

1. Les fractales et l'histoire de la méthode de compression fractale

En décembre 1992, juste avant Noël, Microsoft sort son nouveau CD, Microsoft Encarta. Depuis, cette encyclopédie multimédia, contenant des informations sur les animaux, les fleurs, les arbres et les lieux pittoresques, n'a pas quitté la liste des encyclopédies les plus populaires sur CD. Dans une récente enquête de Microsoft, Encarta a de nouveau pris la première place, battant son concurrent le plus proche, la Compton Multimedia Encyclopedia. La raison de cette popularité réside dans la facilité d'utilisation, la haute qualité des articles et, surtout, le grand nombre de matériaux. Le disque contient 7 heures de son, 100 vidéos d'animation, environ 800 cartes évolutives, ainsi que 7 000 photographies de haute qualité. Et tout cela - sur un seul disque ! Rappelons qu'un CD classique de 650 Mo sans compression peut contenir soit 56 minutes d'audio de haute qualité, soit 1 heure de résolution vidéo avec une résolution de 320x200 au format MPEG-1, soit 700 images couleur mesurant 640x480. Pour accueillir plus d'informations, des algorithmes d'archivage assez efficaces sont nécessaires. Nous ne nous attarderons pas sur les méthodes d'archivage vidéo et audio. Nous parlerons d'un nouvel algorithme prometteur : la compression fractale des informations graphiques.

Concepts "fractale" Et "géométrie fractale" (fracturé- constitué de fragments, lat.) ont été proposés par un mathématicien B.Mandelbrot en 1975 pour désigner des structures irrégulières mais auto-similaires. La naissance de la géométrie fractale est généralement associée à la publication du livre de B. Mandelbrot « Fractal Geometry of Nature » en 1977. L'une des idées principales du livre était que la géométrie traditionnelle (c'est-à-dire l'utilisation de lignes et de surfaces) est extrêmement difficile à représenter des objets naturels. La géométrie fractale les définit très simplement.

La définition de Mandelbrot d'une fractale est la suivante : "Une fractale est une structure composée de parties qui sont en quelque sorte similaires au tout"

L’une des principales propriétés des fractales est l’autosimilarité. Dans le cas le plus simple, une petite partie d’une fractale contient des informations sur l’ensemble de la fractale. Les fractales, ces belles images de systèmes dynamiques, étaient auparavant utilisées en infographie principalement pour construire des images du ciel, des feuilles, des montagnes et de l'herbe. Une image belle et, plus important encore, qui imite de manière fiable un objet naturel pourrait être spécifiée par quelques coefficients seulement.

Il existe une grande variété de fractales. Les types de fractales potentiellement les plus utiles sont les fractales basées sur un système de fonctions itératives. (Système de fonctions itérées - IFS). Méthode IFS en relation avec la construction d'images fractales, inventées par un grand expert en la matière Michael Barnsley et ses collègues de l'Institut national de technologie. Géorgie (Institut de technologie de la Géorgie), est basé sur l'autosimilarité des éléments de l'image et consiste à modéliser l'image avec plusieurs fragments plus petits d'elle-même. Des équations spéciales vous permettent de déplacer, de faire pivoter et de modifier l'échelle des zones d'image ; ainsi, ces zones servent de blocs de construction pour le reste du tableau.

L'un des plus étonnants (et célèbres) IFS-image est une fougère noire, dans laquelle chaque feuille est en fait une version miniature de la fougère elle-même (voir figure). Malgré le fait que l'image ait été créée par un ordinateur utilisant la méthode de transformation affine, la fougère ressemble exactement à une vraie. Il a été suggéré que la nature, lorsqu'elle code la structure génétique des plantes et des arbres, utilise quelque chose qui s'apparente à une méthode IFS-fractales.

IFS-les fractales ont une application très réelle et utile : elles peuvent être utilisées pour compresser de grandes images raster à une fraction de leur taille normale. Cette affirmation découle du théorème Banach sur les transformations contractives (également connues sous le nom de Théorème du collage) et est le résultat des travaux d'un chercheur de l'Institut national de technologie. Géorgie Michael Barnsley dans la zone IFS. Fort de cette conclusion, il quitte l'institut, fait breveter sa découverte et fonde l'entreprise Systèmes itérés incorporés. Il a raconté au monde entier son exploit dans un magazine Octet pour janvier 1988. Cependant, il n'y avait aucune information sur la résolution du problème inverse : comment trouver des transformations affines à partir d'une image donnée. À ce moment-là, ce problème n’avait même pas la moindre idée de solution. Dans l'article Barnsley Plusieurs images fractales réalistes ont été présentées, mais elles ont toutes été créées à la main.

Idéalement, j'aimerais pouvoir trouver un système de transformations affines pour n'importe quelle image (IFSM), reproduisant l'image avec une précision donnée. Cependant, la solution était un peu hors de question. C'est l'étudiant qui l'a trouvé en premier Barnsley, Arnaud Jacquin. La méthode proposée s'appelle «Système de fonctions itérées partitionnées - PIFS». Selon ce schéma, les parties individuelles d’une image ne sont pas similaires à l’image entière, mais seulement à certaines parties de celle-ci.

2. Fondements mathématiques de la compression fractale

Les méthodes de compression fractale vous permettent de compresser les informations 10 000 fois. Tous les programmes de compression fractale connus sont basés sur l'algorithme de Jackwin, un employé de Barnsley qui, en 1992, tout en soutenant sa thèse, a décrit un algorithme pratique de compression fractale. L'avantage incontestable du travail était que l'intervention humaine dans le processus de compression était complètement éliminée.

Considérons le mécanisme de compression des données fractales. L'archivage fractal repose sur le fait qu'en utilisant les coefficients d'un système de fonctions itérées, l'image est présentée sous une forme plus compacte. Avant d'examiner le processus d'archivage, regardons comment IFS construit une image. À proprement parler, IFS est un ensemble de transformations affines 3D qui transforment une image en une autre. Les points dans l'espace tridimensionnel (coordonnée x, coordonnée y, luminosité) subissent une transformation. Ce processus a été clairement démontré par Barnsley lui-même dans son livre Fractal Image Compression. Il a introduit le concept de photocopieuse, composé d'un écran sur lequel l'image originale est représentée et d'un système de lentilles qui projettent l'image sur un autre écran. Chaque objectif projette une partie de l'image originale. En disposant les lentilles et en modifiant leurs caractéristiques, vous pouvez contrôler l'image résultante. L'obligation est imposée aux objectifs de réduire la taille de la partie projetée de l'image. De plus, ils peuvent modifier la luminosité d'un fragment et projeter non pas des cercles, mais des zones avec une bordure arbitraire. Une étape de la Machine consiste à en construire une nouvelle par projection à partir de l’image originale. Il est indiqué qu'à un certain stade, l'image cessera de changer. Cela dépendra uniquement de l’emplacement et des caractéristiques des objectifs et ne dépendra pas de l’image originale. Cette image est appelée point fixe ou attracteur d'un IFS donné. Le théorème du collage garantit qu'il existe exactement un point fixe pour chaque IFS. Le mappage des lentilles étant compressif, chaque lentille définit explicitement des régions auto-similaires dans notre image. Grâce à l’autosimilarité, nous obtenons une structure d’image complexe quel que soit le grossissement. Les deux images les plus connues obtenues par IFS sont le triangle de Sierpinski et la fougère de Barnsley. La première est donnée par trois, et la seconde par des transformations affines (ou, dans notre terminologie, des lentilles). Chaque transformation est spécifiée littéralement en quelques octets, tandis que l'image construite avec leur aide peut occuper plusieurs mégaoctets. Il devient clair comment fonctionne l'archiveur et pourquoi cela prend autant de temps. En fait, la compression fractale est une recherche de zones auto-similaires dans une image et la détermination de paramètres de transformation affine pour celles-ci. Dans le pire des cas, si aucun algorithme d’optimisation n’est utilisé, il sera nécessaire d’énumérer et de comparer tous les fragments d’image possibles de différentes tailles. Même pour de petites images, en tenant compte de la discrétion, nous obtenons un nombre astronomique d'options à trier. Même une réduction drastique des classes de transformations, par exemple en ne mettant à l'échelle qu'un certain nombre de fois, ne permettra pas d'atteindre un temps acceptable. De plus, la qualité de l'image est perdue. La grande majorité des recherches dans le domaine de la compression fractale visent désormais à réduire le temps d'archivage nécessaire pour obtenir une image de haute qualité.

Considérons donc la justification mathématique de la possibilité d'une compression fractale.

Il existe une cartographie où se trouve l’ensemble de toutes les images possibles. W est l'union des mappages w je :

De telles cartographies sont appelées compressif, et la déclaration suivante est vraie pour eux :

Si à une image F 0 nous allons commencer à réappliquer le mappage W de sorte que

C'est l'image finale F appelé attracteur, ou point fixe de cartographie W. On sait aussi que si les transformations w je sont compressifs, alors leur union W est également compressif.

3. Schéma typique de compression fractale

Compte tenu de ce qui précède, le schéma de compression ressemble à ceci : image R. Casser en morceaux r je, appelé zones de classement. Suivant pour chaque domaine r je trouver la zone d je et transformation w je de telle sorte que les conditions suivantes soient remplies :

1.d je plus grande en taille r je .

2.w je (r je ) a la même forme, la même taille et la même position que r je .

3. Coefficient toi transformation w je doit être inférieur à un.

4. La valeur doit être aussi petite que possible.

Les trois premières conditions signifient que la cartographie w je sera compressif. Et en raison de la quatrième condition, l'image codée R. et son image W(R) seront semblables les uns aux autres. Idéalement R=W(R). Cela signifie que notre image R. et sera un point fixe W. C'est ici qu'on utilise la similarité des différentes parties de l'image (d'où le nom - "compression fractale"). Il s'est avéré que presque toutes les images réelles contiennent des parties similaires les unes aux autres, jusqu'à une transformation affine.

Ainsi, pour compresser une image W besoin de:

1. Divisez l'image en zones de classement r je(zones non superposées couvrant la totalité de l’image).

2. Pour chaque zone de classement r je trouver une zone d je(appelé domaine), et afficher w je, avec les propriétés ci-dessus.

3. Rappelez-vous les coefficients des transformations affines W, positions des zones de domaine d je, ainsi que la division de l'image en domaines.

Ainsi, pour décompresser l'image, vous aurez besoin de :

1. Créez une (n'importe quelle) image initiale R. 0 .

2. Appliquez-lui le mappage plusieurs fois W(Syndicat w je).

3. Depuis l'affichage W compressive, puis par conséquent, après un nombre suffisant d'itérations, l'image viendra à l'attracteur et cessera de changer. L'attracteur est notre image originale. La décompression est terminée.

C'est ce qui permet de l'augmenter plusieurs fois lors du déploiement. Les exemples dans lesquels, lors de l'agrandissement d'images d'objets naturels, apparaissent de nouveaux détails véritablement inhérents à ces objets (par exemple, lorsque, lorsqu'on agrandit une photographie d'un rocher, elle acquiert de nouvelles irrégularités plus petites).

4. Estimation du taux de compression et des coûts de calcul

La taille des données pour une détermination complète de la zone de classement est calculée à l'aide de la formule :

Où Nb Et Mo- le nombre de bits nécessaires au stockage de chacune des coordonnées est calculé à l'aide des formules suivantes :

Où V Et H- les dimensions verticales et horizontales de l'image, Taille- taille du bloc de domaine, Étape- étape de recherche de domaine.

Pour stocker la transformation T 3 bits requis.

Pour le stockage U Et V 9 et 7 bits sont nécessaires respectivement.

Par exemple, prenons une image d'une taille de 256x256 pixels, et nous explorerons la zone du domaine avec un pas de 4 pixels.

Nd = Md = (256 - 8 + 1) / 4 = 62

Nb = Mb = CEIL (log 2 62) = 6

Z = 12 + 3 + 6 + 6 = 27

Ratio de compression S s'élève à

S = (8 * 8 * 8) / 27 = 19

Le taux de compression n'est pas aussi élevé qu'on le souhaiterait, mais les paramètres de compression sont loin d'être optimaux et le taux peut augmenter considérablement.

Estimons maintenant la complexité de calcul de cet algorithme. Au stade de la compression, nous devons énumérer toutes les zones de domaine - 1 024 pièces, pour chacune - toutes les zones de rang - 58 081 pièces (à l'étape 1), et pour chacune d'elles, tour à tour, les 8 transformations. Le total est de 1"024 x 58"081 x 8 = 475"799"552 actions. Cependant, ces actions ne sont pas anodines et incluent plusieurs opérations matricielles, qui, à leur tour, incluent des opérations de multiplication et de division de nombres à virgule flottante.

Malheureusement, même sur un PC moderne (et c'est exactement le genre de machines pour lesquelles nous voulions implémenter l'algorithme), il faudra un temps inacceptable pour compresser une image de seulement 256 x 256 pixels. Il est évident que l’algorithme considéré nécessite une optimisation.

L'idée de la compression d'images fractales est née relativement récemment - dans les années 70 du siècle dernier. On pense que ce domaine a commencé à se développer plus activement après la publication du livre de Benoit Mandelbrot «Fractal Geometry of Nature». Il n'existe pas de définition exacte des objets fractals, mais il est généralement admis que les fractales sont des objets qui ont la propriété d'autosimilarité, c'est-à-dire ceux dont une partie de l'objet ressemble à l'objet entier. Un exemple classique de fractale est une feuille de fougère - ce qu'on appelle la fougère Barnsley.

L'idée de compression fractale repose précisément sur la propriété d'autosimilarité. Mais il y a deux problèmes : premièrement, rien ne garantit la présence d’une propriété d’autosimilarité dans une image arbitraire ; deuxièmement, même si l'objet est fractal, comment sélectionner la ou les zones à partir desquelles l'image sera construite. Une base théorique est donc nécessaire pour résoudre ces problèmes. Une telle base existe et est donnée ci-dessous.

2. BASE THÉORIQUE.

2.1IMAGES NOIRES ET BLANCHES.

2.1.1.Espaces métriques.

Une métrique d dans un espace X est fonction de deux arguments d(x,y) tels que :

Alors (X,d) est un espace métrique. On dit qu’une suite de points converge vers un point x si

Un espace métrique où chaque suite de Cauchy converge vers un point de cet espace est appelé espace métrique complet.

Le point x est appelé point limite de l'ensemble X s'il existe une séquence de points de X convergeant vers le point x.

Un ensemble dans un espace métrique s'appelle fermé, s'il contient tous ses points limites. L'ensemble B de (X, d) est appelé limité, s'il existe un point x 0 de X et une valeur finie R > 0 telle que pour tout x de B la condition d(x,x 0) est satisfaite

2.1.2 Ensembles compacts et espace Hausdorff.

Un ensemble C dans un espace métrique (X, d) est appelé compact, si chaque séquence infinie de C a une sous-séquence convergente en C.

Définissons un espace Hausdorff.

Soit (X, d) un espace métrique complet. Définissons H(X) comme un espace constitué de sous-ensembles compacts de l'ensemble X. Autrement dit, chaque point de H(X) est un sous-ensemble compact de X.

Considérons un point arbitraire x de X et un B arbitraire de H(X). Posons par définition

d(x, B) = min(d(x, y) : y Î B).

En raison de la compacité de l’ensemble B, le minimum existe et est borné. Considérons maintenant arbitrairement A,B Î H(X) et définissons la distance entre eux comme d(A, B) = max(d(x, B): x Î A) La compacité de A assure l'existence et la finitude de le maximum, mais d(A, B) ne spécifie pas de métrique, car, dans le cas général, d(A, B) № d(B,A).

Définissons une nouvelle mesure de distance h(A, B) :

h(A, B) = max(d(A, B), d(B, A)).

Nous avons maintenant obtenu une métrique dans l’espace H(X). La métrique h est appelée Métrique de Hausdorff, et l'espace métrique (H(X), h) est espace de Hausdorff métrique.

2.1.3 Mappages compressifs.

Une transformation f : X® X dans un espace métrique (X, d) est appelée une carte de contraction s'il existe une constante s, 0 £ s £ s*d(x 1 , x 2) pour tout x 1 , x 2 Î X. La constante s est appelée facteur de compression d'affichage f. Le point x 0 est appelé point fixe (attracteur) de l'application de contraction f si f(x 0) = x 0.

Théorème sur les cartographies de contraction.

Soit f : X® X une application de contraction sur l'espace métrique complet (X, d). Alors f a un et un seul point fixe x 0 Î X, et pour tout x 0 Î X f n (x)® x 0 .

2.1.4. Systèmes de fonctions itérables.

Soit (w 1 , … , w N ) un ensemble fini d'applications de compression dans (X, d) avec des coefficients de compression s 1 , … , s N . Nous définissons une application W sur des ensembles compacts de points de X comme suit :

W(B) = w 1 (B) Et ... Et w N (B) pour chaque B Î H(X).

Ainsi, nous avons obtenu une carte de contraction W : H(X) ® H(X) avec coefficient de compression

s = max(s 1 , …, s N )

Système de fonctions itérables (IFS) se compose d'un espace métrique complet (X, d) et d'un ensemble fini d'applications de contraction w n:X ® X avec des coefficients de compression s n . Le taux de compression IFS est défini comme s = max(s 1 , ..., s N ).

IFS sera noté (X, w n : n = 1,2,…, N).

Théorème du collage. Soit L un point de l'espace H(X). Étant donné certains e > 0. Choisissons IFS (X, w n : n = 1,2,…,N) avec un facteur de compression s, 0 Ј e. Alors h(L,A) Ј h(L, W(L) )/ (1-s) Ј e / (1-s) , Où A est l'attracteur de cet IFS.

2.1.5. Transformations affines.

Transformations affines – transformations de la forme

Les transformations affines effectuent la compression/étirement, la translation et la rotation d'un objet.

2.1.5. Codage d'images.

Pour obtenir les coefficients de la transformation affine recherchée (dans les cas les plus simples), il suffit de résoudre 2 systèmes de 3 équations à 3 inconnues. A titre d’exemple, considérons la construction du Triangle de Sierpinski. Cette image est décrite par 3 transformations :

Le premier traduit les points (1,2,3) en points (1,4,6) ;

2-e : (1,2,3) – dans (4,2,5) ;

3-e : (1,2,3) – en (6,5,3),

(voir photo en bas à gauche).

Ci-dessous à droite se trouve une image du triangle de Sierpinski obtenue à l'aide de l'algorithme probabiliste et des transformations trouvées de la manière ci-dessus.

2.1.7 Décodage des images.

2.1.7.1 Algorithme déterministe.

L'algorithme déterministe de construction d'une image d'attracteur IFS applique directement le théorème de cartographie de contraction à toute image initiale B de H(X). L'algorithme construit une séquence d'images A n en appliquant de manière répétée la cartographie IFS W = (w 1, ... , w N). Si nous définissons A 0 =B, alors le processus peut s'écrire sous la forme A n = W(A n-1). Par le théorème de cartographie de contraction, A n converge vers l'attracteur d'un IFS donné. Vous trouverez ci-dessous un exemple de l'algorithme déterministe - les premières itérations et l'image finale proche de l'attracteur.

2.1.7.2 Algorithme probabiliste.

Bien que l’algorithme déterministe soit une application directe du théorème de cartographie de contraction, permettant d’observer son fonctionnement en pratique, il est trop lent et n’est généralement pas utilisé en pratique pour construire des images d’attracteurs.

Il est préférable d'utiliser un algorithme probabiliste : Un algorithme probabiliste associe à chaque transformation w i issue de l'IFS une probabilité p i . Ces probabilités déterminent la densité avec laquelle chaque partie de l'image de l'attracteur est recouverte de points. Les probabilités de transformation peuvent être calculées comme le rapport du module du déterminant de la matrice de transformation principale à la somme des modules des déterminants des matrices principales de toutes transformations de l’IFS.

Algorithme de construction d'images :

1) Pour n = 1 à number_of_points_in_image, faites

2) (x, y) = aléatoire (B)

3) pour I=1 à number_of_iterations, faites

4)   p = aléatoire (0,1)

5)   (x,y) = W k (x,y) //où la probabilité p correspond à la transformation W k

Vous trouverez ci-dessous un exemple du fonctionnement de l'algorithme probabiliste.

Vous pouvez remarquer que pour l'algorithme probabiliste, il existe des points spéciaux - les images noires. Si le travail de l'algorithme probabiliste commence par eux, alors l'attracteur ne sera jamais obtenu. Cela conduit à la déclaration suivante : S'il y a au moins un point noir dans l'image initiale, alors il existe une probabilité non nulle que le résultat de l'algorithme probabiliste soit une image purement noire, et cette probabilité est d'autant plus grande que le nombre de points noirs dans l'image initiale est grand. image.

En effet, que l'image ait des dimensions n x m. Alors le nombre total de points qu’il contient est N = n x m. Soit le nombre de points noirs égal à b, soit le nombre de points utilisés pour construire l'image soit égal à M. La probabilité qu'un point sélectionné au hasard soit noir est égale à b/N.

La probabilité que tous les points sélectionnés soient noirs est égale à

Ainsi, pour que l'algorithme fonctionne correctement avec une probabilité supérieure à 1-e, où e O (0, 1), l'inégalité suivante est requise : log b/N e & livre M

Regardons un exemple. Soit e = 0,01. Ensuite pour le bon fonctionnement de l'algorithme probabiliste avec une image initiale de taille 300x300 avec un seul point blanc, il faut

M > journal 89999/90000 0,01 > 414463

Il est intéressant de noter que, bien que l'algorithme probabiliste soit largement utilisé dans divers travaux scientifiques, aucun des auteurs n'a jamais prêté attention à ce fait.

2.1 IMAGES en niveaux de gris.

2.2.1 Espace métrique.

Les images en niveaux de gris peuvent être considérées comme de véritables fonctions f(x,y), défini sur le carré unité I2=I x I..

Sur ces fonctions, vous pouvez saisir une métrique comme suit :

Soit F l'espace des fonctions réelles carrées intégrables sur I2 avec la métrique introduite. Alors (F,d) est un espace métrique complet et le théorème de cartographie de contraction y est valable.

Puisque nous travaillerons avec des images numériques, qui sont essentiellement des matrices de valeurs fixes de la fonction f(x,y), prises en points fixes (xi, yj), dans ce cas nous pouvons utiliser la métrique quadratique moyenne ( RMS) :

2.2.2 PIFS et transformations affines d'images en niveaux de gris.

Cette section utilise des IFS d'un type spécial - Systèmes de fonctions itérables par morceaux (PIFS). PIFS se compose d'un espace métrique complet X, d'un ensemble de sous-domaines D i de X et d'un ensemble d'applications de contraction w i : D i ® X, i = 1, 2, … , n.

2.2.2.1 Transformations affines.

Soit w 0 i une transformation affine prenant en lui le carré unité I2. W 0 i (x,y) = A i (x,y)T + b i , où A i est une matrice de taille 2x2, b i est un vecteur de taille 2x1. Soit D i un sous-domaine de I2, et soit R i la plage de valeurs de la transformation w 0 i : w 0 i (D i) = R i . Définissons l'application w i:F ® F agissant sur l'image f(x,y):

(si w 0i est inversible et (x,y) vient de R i).

La constante si contrôle le contraste, o i contrôle la luminosité. w i est une transformation affine de base d'images en niveaux de gris.

2.2.2.2 Mappages compressifs.

Pour que le mappage wi soit compressif, nous exigeons que la condition soit remplie

d 2 (wi (f), w i (g)) Ј s*d 2 (f, g).

Théorème de cartographie des contractions.

Soit (R i ) former un revêtement de l'ensemble I2, et en même temps ne se coupe pas deux à deux. Soit v i un PIFS de la forme v i:D i ® R i pour un certain ensemble de zones de domaine D i. Pour chaque v i, nous déterminons la compression correspondante w i sur l'espace image F de la manière indiquée ci-dessus. Soit W(f(x,y)) = w i (f(x,y)) pour (x,y) de R i. Alors W est une contraction sur F, a un point fixe unique f W et W n (f) ® f W comme n ® Ґ pour toute image f.

Théorème du collage.

Soit une image en niveaux de gris f. Soit W une application de contraction telle que d 2 (f,W(f)) Ј e . Alors d 2 (f, f W) Ј e /(1-s), où s est le coefficient de compression de l'application W, f w est l'attracteur PIFS.

2.2.3 Codage fractal.

Dans le codage d'images fractales, nous essayons de trouver un ensemble de mappages contractifs qui mappent les blocs de domaine à un ensemble de blocs de rang.

L'algorithme de codage de base est le suivant :

1) Nous divisons l'image originale en blocs de classement qui ne se chevauchent pas.

2) Nous recouvrons l'image d'une séquence de blocs de domaines, éventuellement se croisant (les domaines peuvent être de différentes tailles et leur nombre se compte généralement par milliers).

3) Pour chaque bloc de classement, on retrouve le domaine et la transformation correspondante qui couvre le mieux le bloc de classement

4) Si nous n’obtenons pas une correspondance suffisamment précise, nous divisons les blocs de classement en blocs plus petits. Nous poursuivons ce processus jusqu'à ce que nous obtenions une correspondance acceptable ou que la taille des blocs de classement atteigne une limite prédéterminée.

2.2.4 Décodage des images.

L'image est décodée en appliquant itérativement la transformée W à une image de départ arbitraire g, où W(g(x,y)) = w i (g(x,y)), pour (x,y) de R i . Si les transformations ont été choisies correctement, alors l'itération W n (g) sera proche de la valeur originale de f pour une valeur acceptable de n. Il est important que, selon le théorème du mappage de contraction, le processus converge quel que soit le choix de l’image initiale. A titre d'exemple, on peut envisager de construire l'image « vue de l'USU » à partir de l'image « vue de l'UPI ». De gauche à droite – image initiale, 1ère itération, 2ème itération, attracteur.

3. MISE EN ŒUVRE.

Toutes les constructions ci-dessus sont assez abstraites et le mécanisme de leur fonctionnement n'est pas toujours évident. Pour illustrer le processus de travail, des programmes ont été écrits (travaillant avec des images en noir et blanc, puisque ce cas est plus simple) qui permettent de démontrer clairement certains des processus décrits ci-dessus. Vous trouverez ci-dessous les descriptions des programmes.

3.1 Programme Fract0.

1. Les fractales et l'histoire de la méthode de compression fractale

Concepts "fractale" Et "géométrie fractale" (fracturé- constitué de fragments, lat.) ont été proposés par le mathématicien B. Mandelbrot en 1975 pour désigner des structures irrégulières mais auto-similaires. La naissance de la géométrie fractale est associée à la publication en 1977 du livre de B. Mandelbrot « Fractal Geometry of Nature », qui combine les résultats scientifiques des scientifiques ayant travaillé dans la période 1875-1925 en un seul système. dans ce domaine (Poincaré, Julia, Cantor, etc.).

L’une des principales propriétés des fractales est l’autosimilarité. Dans le cas le plus simple, une petite partie d’une fractale contient des informations sur l’ensemble de la fractale.

Du point de vue de l'infographie, la géométrie fractale est indispensable pour générer des objets complexes non euclidiens, dont les images sont très similaires aux objets naturels, et lorsqu'il est nécessaire de définir des lignes et des surfaces de formes très complexes à l'aide de plusieurs coefficients.

Il existe une grande variété de fractales. Le type de fractale potentiellement le plus utile est la fractale du système de fonctions itérées (IFS). La méthode IFS appliquée à la construction d'images fractales, inventée par leur grand expert Michael Barnsley et ses collègues du State Institute of Technology. Georgia (Georgia Institute of Technology), repose sur l'autosimilarité des éléments de l'image et consiste à modéliser l'image avec plusieurs fragments plus petits d'elle-même. Des équations spéciales vous permettent de déplacer, de faire pivoter et de modifier l'échelle des zones d'image ; ainsi, ces zones servent de blocs de construction pour le reste du tableau.

L’une des images IFS les plus frappantes (et les plus célèbres) est celle de la fougère noire, dans laquelle chaque feuille est en fait une version miniature de la fougère elle-même (voir photo). Malgré le fait que l'image ait été créée par un ordinateur utilisant la méthode de transformation affine, la fougère ressemble exactement à une vraie. Il a été suggéré que la nature, lors du codage de la structure génétique des plantes et des arbres, utilise quelque chose de proche de la méthode fractale IFS.

Les fractales IFS ont une application très réelle et utile : elles peuvent être utilisées pour compresser de grandes images raster à une fraction de leur taille normale. Cette affirmation découle du théorème de contraction de Banach (également connu sous le nom de théorème du collage) et est le résultat des travaux d'un chercheur de l'Institut américain de technologie. La Géorgie de Michael Barnsley dans le domaine IFS. Fort de cette conclusion, il quitte l'institut, fait breveter sa découverte et fonde la société Iterated Systems Incorporated. Il a raconté au monde entier son exploit dans le magazine Byte en janvier 1988. Cependant, il n'y avait aucune information sur la résolution du problème inverse : comment trouver des transformations affines à partir d'une image donnée. À ce moment-là, ce problème n’avait même pas la moindre idée de solution. L'article de Barnsley montrait plusieurs images fractales réalistes, mais elles avaient toutes été créées à la main.

Idéalement, j'aimerais pouvoir trouver pour n'importe quelle image un système de transformation affine (IFSM) qui reproduit l'image avec une précision donnée. Cependant, la solution était un peu hors de question. C'est Arnaud Jacquin, étudiant à Barnsley, qui l'a découvert le premier. La méthode proposée est appelée système de fonctions itérées partitionnées (PIFS). Selon ce schéma, les parties individuelles d’une image ne sont pas similaires à l’image entière, mais seulement à certaines parties de celle-ci.

2. Fondements mathématiques de la compression fractale

Considérons donc la justification mathématique de la possibilité d'une compression fractale.

Il existe une cartographie où se trouve l’ensemble de toutes les images possibles. W est l'union des mappages Wi:

Où R.– l'image, et je– certaines zones (éventuellement superposées) de l’image D. Chaque transformation Wi traduit je V r je. Ainsi:

Il serait logique de représenter l'image en fonction de deux variables f(x,y). Sur l'ensemble de toutes ces fonctions, nous introduisons une métrique (la distance entre les images), par exemple de cette manière :

D'après le théorème de Banach, il existe une certaine classe d'applications pour lesquelles il existe une constante c< 1 de telle sorte que pour toutes les images F Et g l’inégalité persiste

De telles cartographies sont appelées compressif, et la déclaration suivante est vraie pour eux :

Si à une image F 0 nous allons commencer à réappliquer le mappage W ainsi, quelque chose est dans la limite, à je tendant vers l'infini, nous obtiendrons la même image quelle que soit l'image que nous avons prise comme F 0:

C'est l'image finale F appelé attracteur, ou point fixe de cartographie W. On sait aussi que si les transformations Wi sont compressifs, alors leur union W est également compressif.

3. Schéma typique de compression fractale

Compte tenu de ce qui précède, le schéma de compression ressemble à ceci : image R. Casser en morceaux r je, appelé zones de classement. Suivant pour chaque domaine r je trouver la zone je et transformation Wi de telle sorte que les conditions suivantes soient remplies :

1. je plus grande en taille r je.
2. w je (r je) a la même forme, la même taille et la même position que r je.
3. Coefficient toi transformation Wi doit être inférieur à un.
4. La valeur doit être aussi petite que possible.

Les trois premières conditions signifient que la cartographie Wi sera compressif. Et en raison de la quatrième condition, l'image codée R. et son image W(R) seront semblables les uns aux autres. Idéalement R=W(R). Cela signifie que notre image R. et sera un point fixe W. C'est ici qu'on utilise la similarité des différentes parties de l'image (d'où le nom - "compression fractale"). Il s'est avéré que presque toutes les images réelles contiennent des parties similaires les unes aux autres, jusqu'à une transformation affine.

Ainsi, pour compresser une image W besoin de:

1. Divisez l'image en zones de classement r je(zones non superposées couvrant la totalité de l’image).
2. Pour chaque zone de classement r je trouver une zone je(appelé domaine), et afficher Wi, avec les propriétés ci-dessus.
3. Rappelez-vous les coefficients des transformations affines W, positions des zones de domaine je, ainsi que la division de l'image en domaines.

Ainsi, pour décompresser l'image, vous aurez besoin de :

1. Créer une (n'importe quelle) image initiale R0.
2. Appliquez-lui le mappage plusieurs fois W(Syndicat Wi).
3. Depuis l'affichage W compressive, puis par conséquent, après un nombre suffisant d'itérations, l'image viendra à l'attracteur et cessera de changer. L'attracteur est notre image originale. La décompression est terminée.

Qu'une image soit donnée MxN points (où M Et N multiples de 8), 256 nuances de gris. Nous considérerons que les zones de rang et de domaine sont carrées. Nous diviserons l'image originale en zones de classement de 8 x 8 pixels. Nous rechercherons des domaines de domaine d'une taille de 16 x 16 points en recherchant toutes les positions possibles. Il n'existe que 8 transformations affines qui transforment un carré en carré (rotations de 0°, 90°, 180°, 270°, réflexions miroir par rapport à l'horizontale centrale, verticale centrale, à partir des diagonales principale et secondaire). Il ne reste plus qu'à trouver les coefficients de conversion des couleurs. Mais les significations toi Et v(contraste et luminosité) peuvent être facilement trouvés analytiquement.

S'il existe deux séquences de valeurs de couleur de pixel une 1 , une 2 , …, une N(zone de domaine) et b 1, b 2, …, bN(région de classement), nous pouvons alors minimiser l'écart type de la couleur des pixels, qui est une variante de la métrique de différence d'image :

Pour ce faire, il suffit d'égaliser les dérivées partielles R. Par toi et par và zéro et résolvez l’équation de toi Et v. Vous obtiendrez les expressions suivantes :

dans ce cas, si

Alors, quelles données doivent être stockées en conséquence. La grille de répartition en zones de classement est constante pour toutes les images ; elle n'a pas besoin d'être stockée. Reste la position des zones de classement (coin supérieur gauche), le numéro de transformation et les coefficients de luminosité et de contraste.

4. Estimation du taux de compression et des coûts de calcul

La taille des données pour une détermination complète de la zone de classement est calculée à l'aide de la formule :

Où X– le nombre de bits nécessaires pour stocker les coordonnées du coin inférieur gauche du domaine, T– le nombre de bits nécessaires pour stocker le type de transformation affine, U Et V– pour stocker les coefficients de contraste et de luminosité.

Où Nb Et Mo– le nombre de bits nécessaires pour stocker chacune des coordonnées est calculé à l'aide des formules suivantes :

Ici PLAFOND– fonction d'arrondi à l'entier maximum, MARYLAND Et sd– le nombre de domaines qui s'adaptent horizontalement et verticalement, qui sont calculés à l'aide des formules :

Où V Et H– les dimensions verticales et horizontales de l'image, Taille– taille du bloc de domaine, Étape– étape de recherche de domaine.

Pour stocker la transformation T 3 bits requis.

Pour le stockage U Et V 9 et 7 bits sont nécessaires respectivement.

Par exemple, prenons une image d'une taille de 256 x 256 pixels, et nous explorerons la zone du domaine avec un pas de 4 pixels.

Nd = Md = (256 - 8 + 1) / 4 = 62

Nb = Mb = CEIL (log 2 62) = 6

Z = 12 + 3 + 6 + 6 = 27

Ratio de compression S s'élève à

S = (8 * 8 * 8) / 27 = 19

Le taux de compression n'est pas aussi élevé qu'on le souhaiterait, mais les paramètres de compression sont loin d'être optimaux et le taux peut augmenter considérablement.

Estimons maintenant la complexité de calcul de cet algorithme. Au stade de la compression, nous devons parcourir toutes les zones de domaine - 1 024 pièces, pour chacune - toutes celles de rang - 58 081 pièces (à l'étape 1), et pour chacune d'elles, tour à tour, les 8 transformations. Le total est de 1 024 x 58 081 x 8 = 475 799 552 actions. Cependant, ces actions ne sont pas anodines et incluent plusieurs opérations matricielles, qui, à leur tour, incluent des opérations de multiplication et de division de nombres à virgule flottante.

Malheureusement, même sur un PC moderne (et c'est exactement le genre de machines pour lesquelles nous voulions implémenter l'algorithme), il faudra un temps inacceptable pour compresser une image de seulement 256 x 256 pixels. Il est évident que l’algorithme considéré nécessite une optimisation.

5. Optimisation de l'algorithme de compression

L'algorithme doit être optimisé dans plusieurs domaines : vitesse, qualité de l'image résultante, degré de compression.

Les mesures suivantes peuvent être prises pour réduire les coûts de calcul :

1. Explorez la zone du domaine pas complètement, mais en quelques étapes. Cela augmentera également le taux de compression, mais affectera la qualité de l'image.
2. Ne cherchez pas le meilleur domaine, mais celui qui satisfait certains E. Bien que cela puisse augmenter considérablement la vitesse de compression, cette technique peut également réduire considérablement la qualité de l’image résultante. Dans ce cas, la qualité dépend en grande partie de l’adéquation de la métrique de différence entre les images.
3. Lorsque vous recherchez une zone de domaine, ne transformez pas la zone de domaine, mais la zone de classement. Pour ce faire, il est pratique de stocker 8 variantes de zones de classement avec diverses transformations. Dans ce cas, la transformation inverse doit être écrite dans le fichier résultant. Pour toutes les transformations sauf deux, l’inverse est la transformation elle-même. Pour faire pivoter de 90° et 270°, vous devez enregistrer la rotation de 270° et 90° respectivement. Cela réduira considérablement les coûts de calcul, mais augmentera également considérablement les coûts de RAM.
4. Pour rechercher une région de domaine, vous pouvez utiliser l'un des algorithmes d'optimisation globale non linéaire conditionnelle, tels qu'un algorithme de recuit simulé ou un algorithme génétique, plutôt que la force brute. Dans ce cas, il n'y aura que trois paramètres variables (coordonnées de la zone de domaine et numéro de transformation affine), et la fonction cible est l'écart type de la zone de domaine par rapport au rang un.

Pour améliorer la qualité : si un domaine qui satisfait aux spécifications spécifiées E, la zone de classement peut être divisée en 4 sous-zones et une recherche de domaine peut être effectuée pour chacune d'elles. Cela peut être fait de manière récursive, jusqu'à ce qu'une certaine taille minimale ou un seul pixel soit atteint. Mais cela augmentera les coûts de calcul et réduira le taux de compression.

Pour augmenter le taux de compression, des blocs monochromes peuvent être identifiés. Bloc de couleur unique nous appellerons une région de classement dans laquelle l'écart type par rapport à sa propre valeur moyenne ne dépasse pas un certain E". Dans ce cas, seule la luminosité moyenne du point sera écrite dans le fichier de sortie, grâce à quoi une compression de 1 à 64 sera obtenue (pour les zones de rang de taille 8).

6. Mise en œuvre

Cet article décrit uniquement la version la plus simple de l'algorithme de compression fractale. Michael Barnsln Et Alan Sloan trouvé une méthode pour résoudre ce problème qui fonctionne pour n'importe quelle image raster, même si elle ne contient pas d'éléments évidents d'autosimilarité. Les détails complets de cette méthode n'ont pas été rendus publics, mais le fait que le package Encarta de Microsoft utilise la bibliothèque de compression Barnsley est une preuve suffisante de son efficacité et de son applicabilité générale aux images de tous types.

Ce que nous savons de la méthode Barnsley-Sloan, c'est qu'en utilisant des techniques standard de traitement d'image (d'ailleurs, vous pouvez également trouver des descriptions de beaucoup d'entre elles sur ce site), telles que la détection des contours et l'analyse des variations de texture, l'image est divisée en segments de forme irrégulière. Une série de transformations est ensuite effectuée pour définir l'image comme une union de ces segments, et les transformations sont écrites sous forme d'ensembles IFS. Grâce à un processus itératif similaire à celui utilisé pour imager la fougère, l’image est reconstruite avec une précision étonnante. Le nombre de transformations affines n'est pas fixé à 8 ; Certaines images codées peuvent utiliser 100 transformations affines ou plus.

À mon tour, je peux imaginer une variante de mise en œuvre de l'algorithme décrit ci-dessus, qui ne se distingue ni par sa rapidité ni par sa haute qualité, mais qui peut néanmoins servir d'outil de recherche simple. L'archive .rar, disponible en téléchargement, contient également les textes sources.

Une option de mise en œuvre plus avancée peut être trouvée sur le site Web