Sur la base des transformations DFT, Walsh-Hadamard et Haar, un certain nombre d'autres transformations peuvent être construites. transformations orthogonales. Ils peuvent être déterminés soit à l'aide du produit de Kronecker, soit comme une somme de produits de Kronecker. Par exemple, une transformée hybride de Hadamard-Haar est proposée, dont la matrice est de l'ordre de dimension définie comme

L'article donne une définition récursive de la transformée dite de Hadamard modifiée.

et sa connexion avec la transformée de Haar est indiquée.

Nous considérons la matrice de la transformée de Walsh dite généralisée d'ordre de dimension (transformation par fonctions de Vilenkin-Chrestenson), définie comme la puissance de Kronecker de la matrice

L'ouvrage décrit ce qu'on appelle la -transformation, qui est construite sur la base de la transformation de Walsh-Hadamard en remplaçant chaque somme dans l'expression (3.114) par sa valeur absolue. Cette transformation est irréversible.

Il convient également de mentionner la transformée inclinée, la transformée inclinée de Haar et la transformée de base discrète proposées pour le codage d'images.

On peut montrer que la plupart des transformations unitaires actuellement utilisées en traitement d'images peuvent être représentées comme des sommes de produits de Kronecker de matrices élémentaires, de matrices de permutation et de quelques autres. Cette représentation des matrices Haar, Hadamard, Walsh, Walsh-Paley, matrice Hadamard modifiée, matrice Hadamard-Haar, matrice DFT, matrice Walsh généralisée est présentée dans le tableau. 3.5 en utilisant la notation suivante :

Une matrice de permutation de dimensions, lorsqu'elle est multipliée par un vecteur, ses éléments sont réorganisés conformément au code binaire inversé de leur nombre ; - une matrice de permutation de dimensions qui effectue la permutation des éléments vectoriels conformément au code Gray inverse de leurs nombres ; - Produit de Kronecker des matrices ; Puissance de Kronecker de la matrice.

(voir scan)

Suite du tableau. 3.5 (voir scan)

Cette représentation fournit une base pratique pour comparer les transformations. Ainsi, lorsqu'on compare les représentations d'une matrice, il est facile de « remarquer qu'elles diffèrent dans l'ordre inverse des matrices à chaque terme ; la matrice MHAD diffère de la matrice Hadamard HAD en ce qu'elle n'est pas construite sur

Et ainsi de suite, etc. Pour toutes ces matrices, il existe des algorithmes rapides permettant de les multiplier par un vecteur lors de la transformation. Ce fait est le plus directement lié à la possibilité de représenter des matrices sous forme de sommes de matrices de Kronecker (voir chapitre 4).

Sur la base des transformations unidimensionnelles décrites, les transformations séparables bidimensionnelles correspondantes peuvent être construites comme des transformations doubles unidimensionnelles :

où M est l'une des matrices de transformation décrites ci-dessus ; a - signal discret bidimensionnel ; a est sa transformation.

Notez que toutes les transformations d'image unitaires actuellement utilisées dans le traitement d'images numériques sont séparables, c'est-à-dire qu'elles sont effectuées séparément le long des colonnes et des lignes d'un signal bidimensionnel. Cela réduit le nombre d’opérations nécessaires pour les réaliser. Des transformations séparables peuvent également être construites en choisissant différentes matrices pour les transformations le long des lignes et des colonnes :

Voilà comment ça se passe transformations mixtes, utilisé dans les dispositifs spécialisés de codage d'images numériques (voir, par exemple).

Les applications des transformations unitaires en traitement d'image peuvent être divisées en trois groupes :

Codage d'images ;

Extraction de fonctionnalités pour la préparation et la reconnaissance d’images ;

Filtrage généralisé.

L'encodage d'images est actuellement la principale application des transformations (sauf DFT). De plus, certaines transformations (par exemple, transformation oblique et transformation de base linéaire discrète, etc.) ont été introduites spécifiquement pour être utilisées dans le codage.

Les coefficients de représentation du signal obtenus à la suite de sa transformation peuvent être considérés comme ses signes et utilisés dans la préparation d'images (voir Partie II, Chapitre 7) et pour la reconnaissance. Un exemple de transformation inventée spécifiquement pour mettre en évidence des caractéristiques lors de la reconnaissance est la -transformation. Les applications des transformations pour le codage et la reconnaissance sont liées. En règle générale, les transformations qui donnent de meilleurs résultats pour l’encodage sont également meilleures pour l’extraction de fonctionnalités.

L'utilisation de transformations unitaires pour le filtrage des signaux repose sur une généralisation de la notion de filtrage dans le domaine fréquentiel transformation discrète Fourier. Lors du filtrage des signaux à l'aide de DFT, la transformation de signal suivante est effectuée :

Matrices de transition de la transformation T vers la DFT et vice versa.

Cette approche a été proposée pour généraliser le filtrage linéaire (Wiener) optimal (voir aussi).

En fonction du type de transformation T et des propriétés du filtre requis, la complexité de réalisation de l'opération de filtration (3.139), estimée par exemple par le nombre d'opérations, peut varier. En particulier, il peut s'avérer plus rentable d'utiliser la transformée de Walsh-Hadamard plus rapide au lieu de la TFD, malgré la plus grande complexité de la multiplication par une matrice de filtre hors diagonale dans ce cas (voir aussi § 6.5).

L'un des moyens les plus courants de traiter des signaux unidimensionnels et multidimensionnels, y compris des images, sont les transformations orthogonales. Le rôle des transformations orthogonales est particulièrement important dans la résolution du problème de la réduction du taux de transmission des symboles binaires dans la télévision numérique et, par conséquent, dans la réduction de la bande de fréquences requise des canaux de communication. L’essence des transformations orthogonales est de représenter le signal original comme une somme de fonctions de base orthogonales.

Rappelons que les fonctions x(t) et y(t) sont dites orthogonales sur le segment (t 1, t 2) si leur produit scalaire est égal à zéro

Cette définition peut être étendue aux signaux discrets représentés par des séquences de nombres. Les signaux discrets x(n) et y(n), ayant chacun N échantillons, sont dits orthogonaux si la condition est satisfaite

L'un des plus exemples célèbres L'application de la transformation orthogonale est l'expansion du signal périodique x en une série de Fourier

Où: ; T - période de répétition du signal x(t).

Les coefficients réels de la série de Fourier sont déterminés par les relations

Sous forme complexe, le développement en série de Fourier a la forme :

Amplitudes harmoniques complexes ;

j est l'unité imaginaire.

Non seulement un signal périodique de période T peut être développé en une série de Fourier, mais également un signal qui ne diffère de 0 que sur l'intervalle de temps (-T/2, T/2). Dans ce cas, une continuation périodique du signal sur tout l'axe du temps avec une période T est utilisée.

Considérons un signal discret x(n), différent de 0 pour n = 0,1, ..., N-1. Pour un tel signal, il est également possible d'introduire une expansion de base des fonctions sinusoïdales. Étant donné que le spectre de fréquences du signal échantillonné doit être limité par le haut conformément à la condition du théorème de Kotelnikov, un nombre fini de composantes de fréquence restant dans la décomposition du signal discret sont des fonctions harmoniques complexes discrètes. Ce développement, appelé transformation de Fourier discrète (TFD), a la forme

N=0, 1…N-1,(2.6)

où les coefficients DFT X(k) sont déterminés par la relation

K=0, 1…N-1,(2.7)

Rappelons que trouver les coefficients X(k) à partir de (2.7) est généralement appelé TFD direct, et l'obtention d'un signal à partir de ces coefficients conformément à (2.6) est une TFD inverse.

Dans ces relations, des sommes apparaissaient à la place d'intégrales, puisque le signal originel n'est pas continu, mais discret. Fréquence utilisée dans la décomposition signaux analogiques et ayant la dimension rad/s, dans la DFT correspond à une quantité sans dimension, où k=0, 1…N-1. Le rapport montre quelle fraction de la fréquence d'échantillonnage correspond à la fréquence d'une harmonique discrète donnée.

Les coefficients DFT Х(k) et les facteurs exponentiels dans (2.6), (2.7) sont des nombres complexes. Chaque nombre complexe est stocké dans la mémoire numérique sous la forme d'une paire de nombres réels représentant ses parties réelle et imaginaire. L'addition de deux nombres complexes nécessite d'effectuer deux opérations d'addition de nombres réels : les parties réelle et imaginaire sont ajoutées séparément. La multiplication de deux nombres complexes nécessite quatre opérations de multiplication et deux opérations d'addition pour les nombres réels. Ainsi, effectuer une DFT sous une forme complexe entraîne une augmentation significative du volume de mémoire requis et du temps de calcul.

Pour traiter uniquement avec nombres réels, utilisent généralement la décomposition par transformée en cosinus discrète (DCT), décrite par la relation :

où les coefficients de politique monétaire sont déterminés par les formules

Comme dans le cas de la DFT, trouver les coefficients C(k) selon (2.9) est appelé DCT directe, et représenter le signal sous la forme (2.8) est appelé DCT inverse.

De même, nous pouvons écrire les relations pour DFT et DCT directes et inverses dans cas bidimensionnel. Un signal discret bidimensionnel, par exemple une trame distincte d'un signal de télévision numérique, est représenté par une matrice de valeurs x(t,n), où t = 0 ... M-1 - numéro d'échantillon dans le ligne, n = 0 .., N-1 - numéro de ligne dans le cadre.

La DFT bidimensionnelle directe a la forme :

k=0…M-1, l=0…N-1,

où X (k, l) sont des coefficients DFT complexes qui reflètent le spectre de fréquence spatiale de l'image.

La DFT bidimensionnelle inverse représente la décomposition d'une image en fonctions de base :

Les coefficients de la politique monétaire directe bidimensionnelle sont déterminés par les formules :

La DCT bidimensionnelle inverse a la forme :

Les quantités et sont des fréquences spatiales discrètes, respectivement le long des coordonnées horizontales et verticales, qui sont exprimées sous forme de quantités sans dimension ayant la même signification que la fréquence discrète dans le cas unidimensionnel. Chaque fréquence spatiale discrète est proportionnelle au rapport de la période spatiale d'échantillonnage à une coordonnée donnée à la période spatiale de cette composante fréquentielle. Les périodes spatiales sont mesurées en unités de distance.

Sur la fig. 2.3 montre les fonctions de base de la DCT bidimensionnelle pour M = 8, N = 8 sous forme d'images en demi-teintes. Les zones claires correspondent aux valeurs positives et les zones sombres correspondent aux valeurs négatives.

Riz. 2.3.

Exemples présentés :

• une) k = 1, je= 0 ; b) k = 0, l = 1 ; c) k = 1, l = 1 ;
• d) k = 0, l = 2 ; e) k = 1, l = 2 ; e) k = 2, l = 2 ;
• g) k = 4, l = 2 ; h) k = 7, l = 1 ; je) k = 7, l = 7.

Une propriété remarquable de la décomposition d'un signal vidéo selon la base DCT est que chaque fonction de base contient simultanément des informations sur l'ensemble de l'image. Le nombre de fonctions de base utilisées pour décomposer le signal vidéo détermine la précision de la représentation de l'image.

Conformément à , en général, il est possible d'estimer le coût des ressources de calcul lors de l'exécution d'une DFT directe et inverse comme proportionnel à N 2 . De même, on peut montrer que le calcul des TFD bidimensionnelles directes et inverses nécessite un nombre d'opérations proportionnel à N 2 M 2.

Par exemple, le calcul de la DFT pour un bloc d'image carré contenant 8x8 éléments (pixels) nécessitera environ 16 10 3 opérations de multiplication et d'addition. Et le calcul de la DFT d'une image de télévision en noir et blanc de la norme de décomposition habituelle, contenant 720 x 576 pixels, nécessitera environ 8·10 11 opérations. Si les calculs sont effectués sur un ordinateur qui effectue 10 6 opérations sur des nombres réels par seconde, le temps de calcul de la DFT sera de 8 10 5 s, soit plus de 200 heures. Évidemment, pour calculer la DFT des images de télévision en temps réel, c'est à dire. pendant la période de numérisation des images, il est nécessaire de rechercher des moyens de réduire le nombre d'opérations requises.

La manière la plus radicale de réduire la quantité de calcul consiste à utiliser des algorithmes DFT rapides découverts dans les années 60, appelés algorithmes de transformée de Fourier rapide (FFT). Les algorithmes rapides de calcul de la DFT sont décrits en détail dans de nombreuses sources documentaires et ne sont pas abordés ici.

Une FFT bidimensionnelle peut être décomposée en une séquence de FFT unidimensionnelles. Le nombre d'opérations nécessaires s'avère proportionnel. Pour l'exemple ci-dessus d'une trame de télévision composée de 720x576 pixels, cette valeur s'avère être d'environ 8 10 6, soit 10 5 fois inférieure au nombre d'opérations nécessaires pour calcul direct TFD.

Il existe également des algorithmes rapides pour calculer la politique monétaire. Comme on le verra ci-dessous, dans la télévision numérique, le rôle principal est joué par la DCT de blocs de 8x8 pixels, qui utilise un algorithme pour calculer rapidement une DCT unidimensionnelle d'un segment de signal numérique contenant huit éléments. Dans ce cas, la DCT est d'abord calculée pour chaque colonne du bloc d'éléments d'image, puis la DCT est calculée pour chaque ligne de la matrice de nombres 8x8 résultante.

Dans les équipements modernes, y compris la télévision numérique, la DFT et la DCT sont généralement effectuées en temps réel à l'aide de processeurs de signaux numériques (DSP) ou de matériel spécial, par exemple des dispositifs informatiques parallèles.

DCT est à la base des méthodes de codage actuellement les plus utilisées JPEG, MPEG-1, MPEG-2, dont une description sera donnée dans la section 2.2.

Algorithmes de compression d'images numériques utilisant des transformations orthogonales

En tant que manuscrit

Umnyashkin Sergueï Vladimirovitch

CDU 004.932 : 004.421 : 519.722

Méthodes mathématiques et algorithmes numériques

compression d'image à l'aide

transformations orthogonales

Spécialité 05.13.11 - « Mathématiques et logiciels ordinateurs, complexes et réseaux informatiques »

Moscou – 2001 2

Les travaux ont été réalisés à l'Institut d'État de technologie électronique de Moscou (Université technique)

Consultant scientifique: Docteur en Sciences Physiques et Mathématiques, Professeur Pospelov A.S.

Adversaires officiels:

Docteur en sciences physiques et mathématiques, professeur Ososkov G.A.

Docteur en sciences physiques et mathématiques, professeur Selishchev S.V.

Docteur en Sciences Techniques, Professeur Koekin A.I.

Organisation leader: Radio de l'Institut unitaire de recherche sur les entreprises de l'État fédéral (Moscou)

La soutenance aura lieu le 19 février 2002 à 14h30 lors d'une réunion du conseil de thèse D.212.134.02 à l'Institut d'État de technologie électronique de Moscou à l'adresse : 103498, Moscou, Zelenograd, MIET (TU).

La thèse se trouve dans la bibliothèque MIET (TU).

Secrétaire scientifique de la thèse /Vorobiev N.V./ professeur du conseil

Caractéristiques générales du travail

Pertinence sujets. Le stockage et la transmission d'images avec représentation numérique directe sous la forme d'une matrice de pixels (points image) nécessitent le traitement d'énormes quantités de données.

Cependant, la représentation directe des images est inefficace : du fait de la corrélation importante des éléments matriciels, un codage indépendant des pixels génère des codes redondants. Par conséquent, parmi d'autres problèmes de traitement d'images numériques, le problème de la compression d'images, qui consiste à trouver des moyens de mettre en œuvre un codage efficace des données visuelles, est particulièrement pertinent.

But du travail. La complexité des algorithmes utilisés pour la compression d'images ne cesse de croître - cela concerne non seulement le volume de calculs, mais également les fondements idéologiques de la construction d'algorithmes, dont la plupart sont basés sur l'utilisation de transformations orthogonales discrètes pour le prétraitement des données. Dans le même temps, le problème de la compression d'images est posé par la pratique, qui nécessite une attention constante aux capacités des équipements réels pour le résoudre. But Le travail impliquait l'étude des problèmes théoriques d'un codage d'image efficace à l'aide de transformations orthogonales, ainsi que le développement d'algorithmes de compression appropriés adaptés à une utilisation pratique sur la base d'outils informatiques universels à usage général.

Direction de la recherche. Les recherches menées dans le cadre de la thèse ont porté sur les questions suivantes :

1. Recherche et développement de méthodes d'analyse théorique et de synthèse de transformations discrètes pour les schémas de compression de données corrélées ;

2. Développement de nouveaux algorithmes rapides de calcul de la transformée discrète de Chrestenson-Levy (DCLT) et d'un algorithme de compression d'images en demi-teintes basé sur le codage statistique des spectres DPCL ;

3. Etude des spécificités et formalisation du schéma général de compression par traitement bloc par bloc fragments d'image utilisant une transformation orthogonale suivie d'une quantification et d'un codage statistique des coefficients de transformation ;

4. Développement d'algorithmes de compression d'images en ondelettes et étude des possibilités de codage fractal dans le spectre des ondelettes ;

5. Développement d'un algorithme de compression de séquences vidéo (images dynamiques), pouvant être utilisé sous forme d'implémentation logicielle basée sur des outils informatiques universels à usage général (ordinateurs personnels multimédias).

Méthodes de recherche. Les méthodes d'analyse mathématique et fonctionnelle ont été utilisées comme principal outil de recherche théorique, algèbre linéaire, théorie des probabilités et statistiques mathématiques, théorie de l'information. Une partie importante de la recherche a également consisté en des expériences informatiques sur le traitement d'images réelles fixes et dynamiques, visant à obtenir les données statistiques nécessaires et à déterminer les caractéristiques des algorithmes de compression finaux. Les expériences réalisées ont confirmé l'exactitude solutions théoriques et l'efficacité des algorithmes de compression proposés.

Nouveauté scientifique. À la suite des travaux de thèse, de nouvelles méthodes d'analyse de l'efficacité des transformations orthogonales conçues pour compresser des données corrélées ont été obtenues ; spécifiquement pour la compression des données, la transformée pseudocosinus discrète (DPCT) a été introduite en considération (construite pour la première fois). De nouveaux algorithmes rapides de calcul de DPCL ont été développés, sur la base desquels un schéma de compression d'images statiques ayant des caractéristiques similaires à la méthode JPEG a été obtenu pour la première fois.

Pour le traitement des images fixes et dynamiques, de nouveaux algorithmes et des approches théoriques générales ont été proposés qui formalisent des procédures d'analyse et de synthèse de schémas de compression d'images numériques basés sur des transformations orthogonales discrètes.

Les principaux résultats suivants sont soumis pour la soutenance de la thèse :

L'invention concerne un procédé d'évaluation de l'efficacité de décorrélation de transformations orthogonales et des algorithmes de clustering pour DPKP corrélés basés sur celui-ci et un algorithme rapide pour son calcul ;

Nouvel algorithme DPCL rapide et sa modification – un algorithme avec calcul incomplet ; algorithme de calculs combinés DPKL pour traiter des tableaux réels dans la base (1,exp(-2i/3)) ;

Une méthode de compression d'image basée sur une méthode spéciale de codage arithmétique des spectres DPCL des blocs d'images ;

Déterministe et estimations probabilistes coefficients de transformée en cosinus discrète (DCT) ;

Algorithme de codage contextuel des spectres d'images DCT ;

Schéma général de compression d'images basé sur la quantification vectorielle adaptative dans le domaine des transformations orthogonales ;

Algorithmes de compression par ondelettes pour images statiques ;

Algorithme de recherche de blocs d'images déplacés ;

Technique expérimentale pour construire des spectres de partitionnement en zones de codage indépendantes ;

Algorithme de compression vidéo.

Valeur pratique. En général, le contenu du travail est appliqué, de sorte que les résultats théoriques obtenus servent également à atteindre des objectifs liés au développement d'algorithmes et de schémas spécifiques pour la compression d'images numériques. L'application des algorithmes de compression d'images obtenus est possible pour une large classe de systèmes de stockage et de transmission d'informations visuelles, principalement dans les applications informatiques multimédias et en réseau. Les algorithmes développés, comme le confirment les expériences, présentent des caractéristiques élevées en termes de vitesse, de qualité de traitement et de compression des données, qui correspondent au niveau mondial moderne.

Mise en œuvre des résultats des travaux. Les résultats théoriques des travaux et les algorithmes de compression des images vidéo ont été introduits au Complexe national de recherche et de production "Centre technologique" MIET (http://www.tcen.ru) et utilisés dans les activités scientifiques et de production de l'entreprise scientifique et de production. "Technologie" (Moscou).

Approbation du travail. Principaux résultats Les travaux ont été rapportés et discutés lors des conférences et réunions scientifiques suivantes :

1. VIIe école d'hiver de Saratov sur la théorie des fonctions et des approximations (SSU, janvier 1994).

2. Int. conférence sur la théorie des fonctions et des approximations, dédiée au 90e anniversaire d'Acad. S.M. Nikolsky (Moscou, MI RAS, mai 1995).

3. Conférences scientifiques et techniques panrusse « Électronique et informatique » (Moscou, MIET, 1995-2000).

4. Int. conférence sur la théorie de l'approximation des fonctions, dédiée à la mémoire du prof. P.P. Korovkina (Kaluga, KSPU, 26-29 juin 1996).

5. Conférences internationales « Méthodes d'optimisation des calculs » (Kiev, 1997, 2001).

6. Conférence internationale « Problèmes de l'enseignement mathématique », dédiée. 75e anniversaire du membre correspondant. Prof. L.D. Kudryavtseva (1998).

7. Conférence internationale « Théorie de l'approximation et analyse harmonique » (Tula, 26-29 mai 1998).

8. Conférence internationale « Les technologies de l'information dans les projets innovants » (Ijevsk, 20-22 avril 1999).

9. VIIe Conférence internationale « Mathématiques. Économie. Écologie. Education » – Colloque international « Les séries de Fourier et leurs applications »

(Novorossiisk, 1999).

10. VIIe Conférence internationale « Mathématiques. Ordinateur. Éducation"

11. Conférence internationale consacrée au 80e anniversaire de la naissance de S.B. Stechkin (Ekaterinbourg, 28 février - 3 mars 2000).

Publications. Le contenu principal de la thèse se reflète dans 30 ouvrages.

Structure et portée de la thèse. Le mémoire contient des pages (dont 26 pages d'annexes) et se compose d'une introduction, de six chapitres, d'une conclusion et de 6 annexes. La liste bibliographique comprend 178 titres. Les annexes fournissent résultats numériques un certain nombre d'expériences sur le traitement d'images, ainsi que informations générales et des copies des documents sur l'utilisation des résultats du travail de thèse.

Dans l'introduction(28 pages) la pertinence, la nouveauté scientifique et la valeur pratique de la recherche sont justifiées. Le contenu des chapitres est brièvement résumé.

Dans le premier chapitre(35 pages) fournit les informations préliminaires nécessaires à une présentation ultérieure, fournit un bref aperçu et une classification des principales approches pour mettre en œuvre un codage d'image efficace.

L'utilisation d'algorithmes de compression avec perte pour les images en demi-teintes est très répandue : en autorisant une erreur dans l'image reconstruite, vous pouvez obtenir bien plus haut niveau compression des données. Le plus souvent, la qualité du traitement de l'image est évaluée par X = (xi, j) – la matrice de l'image originale, X = (xi, j) – la matrice de l'image obtenue après traitement (compression et récupération des données). Pour la valeur logarithmique de l'écart type, la mesure généralement acceptée PSNR (rapport signal sur bruit de crête) est utilisée. Il convient d'envisager les méthodes de compression d'image sous la forme d'un schéma général composé de trois étapes principales : réduction des inter-éléments. corrélation de données, quantification d'éléments de données, codage statistique . La quantification est le principal outil utilisé dans la compression de données avec perte. Essentiellement, la quantification est l'extraction d'une partie fondamentale de l'information à partir des données d'entrée, lorsqu'il y en a moins. partie importante tombe.

La quantification scalaire et vectorielle est utilisée.

Conversion d'une image en région spectrale généralisée à l'aide de transformation linéaire F peut réduire considérablement la corrélation inter-éléments dans la matrice de transformation Y = F (X) par rapport à la corrélation des éléments dans la matrice d'image discrète. Le codage indépendant par composant de la matrice Y, plutôt que de la matrice X, devient alors plus important. efficace. On peut également donner une interprétation énergétique du but de l'utilisation des transformations, qui dans cette compréhension est de concentrer la partie maximale de l'énergie du signal discret original (matrice X) dans le nombre minimum de coefficients spectraux (éléments de la matrice Y). Il existe un certain lien entre la distribution d'énergie dans le spectre généralisé et les propriétés décorrélantes des transformations. L’étude de l’efficacité des propriétés de décorrélation est donc une tâche importante lors du choix d’une transformation à utiliser dans un schéma de compression.

Les images photographiques réelles sont des signaux bidimensionnels qui présentent des inhomogénéités (caractéristiques) dans les zones des contours des objets. Par conséquent, la base des fonctions utilisées pour la décomposition doit avoir une bonne localisation dans l'image originale. Cependant, dans les zones de fond, l'image peut être considérée comme une réalisation d'un signal stationnaire, ce qui rend préférable d'utiliser une base d'expansion localisée en fréquence (il est bien connu que les coefficients de Fourier de l'expansion trigonométrique d'un signal stationnaire sont non corrélé).

Il est impossible d’obtenir simultanément une haute résolution dans les domaines fréquentiel et temporel en raison du principe d’incertitude de Heisenberg. La solution consiste à utiliser des bases d'ondelettes (rafales) fonctionnelles, qui ont une résolution temps-fréquence variable. Les approches basées sur les splash sont actuellement dominantes dans le traitement des images fixes, remplaçant progressivement l'outil de décorrélation traditionnel, la transformée en cosinus discrète.

Le premier chapitre note que pour optimiser les algorithmes de compression de données avec perte, une approche basée sur la minimisation de la fonction Lagrange RD est souvent utilisée. Soit X un ensemble de données d'entrée qui, à la suite de la procédure de compression-récupération, est associé à un ensemble de données de sortie de même nature, Y=F(X,u), où u=(u1,... ,un) est un ensemble de paramètres de contrôle de l'algorithme de compression F. On considère les éléments X, Y d'un espace de métrique D(X,Y), l'ensemble de tous valeurs possibles vecteur de contrôle u que nous désignons par U. Le problème d'optimisation du codage est de trouver de tels paramètres u* = u1,..., un de l'algorithme F pour un ensemble donné de données d'entrée X et le coût binaire maximum autorisé Rb tel que les données une erreur de codage D(X, Y)=D(X,F(X,u)) prendrait valeur minimale. Autrement dit, où R(X,u) est le nombre de bits requis pour coder un ensemble de données X avec les paramètres u.

Trouver une solution tâches(1) se résume dans la plupart des cas à de lourdes procédures numériques de nature itérative. Si la contrainte R(X,u)Rb n'est pas spécifiée, alors pour déterminer les paramètres de codage optimaux u* correspondant à la solution du problème (1) pour une valeur (précédemment inconnue) de Rb, une version simplifiée de minimisation du RD de Lagrange la fonction est utilisée :

où est un paramètre non négatif spécifié en externe. Le paramètre de la fonction J(u) définit l'équilibre entre la qualité et le niveau de compression des données. La valeur =0 correspond à la plus petite erreur de codage ; en augmentant la valeur, on obtient, en optimisant les paramètres de l'algorithme F selon (2), une longueur de code plus petite, mais une erreur plus grande. Ainsi, vous pouvez personnaliser l'algorithme de codage F aux caractéristiques requises. Pour trouver une solution au problème (1), la minimisation (2) est répétée de manière itérative, avec différentes significations– cette procédure est appelée optimisation RD1.

Le premier chapitre note également brièvement les fonctionnalités associées au traitement (compression-récupération) des images dynamiques. La principale transformation utilisée pour la compression vidéo reste la DCT, car elle est plus simple en termes de quantité de calculs que les transformations en ondelettes.

Comme pour la compression statique, les algorithmes de codage vidéo sont souvent plus complexes que les algorithmes de décodage.

Implémentation d'un logiciel de compression vidéo en temps réel, Berger T. Rate Distortion Theory. – Endlewood Cliffs, New Jersey : Prentice Hall, 1971.

Ainsi, il impose des restrictions importantes sur la complexité admissible des calculs.

Chapitre deux(52 pages) est consacré à l'étude de l'efficacité et de la synthèse des transformations orthogonales destinées à être utilisées en compression de données. La nouvelle méthode proposée pour analyser l’efficacité repose sur le raisonnement suivant. Soit connue la matrice de covariance KX du vecteur de données d'origine X = (x0, x1,..., x N 1)T, le spectre vectoriel Y est obtenu à la suite d'une transformation orthogonale avec la matrice W : Y= WX.

L’entropie inconditionnelle moyenne du coefficient du spectre vectoriel peut s’écrire :

où fk(mk,k,x) est la fonction de densité de probabilité pour la caractéristique spectrale yk (k-ième composante du vecteur Y), mk – espérance mathématique, k – écart type, f k0 (x) = f k (0,1, x). Plus l’entropie moyenne (3) est faible, plus le codage indépendant ultérieur des composantes spectrales sera efficace. En imposant la contrainte que pour la classe que pour la transformation de Karhunen-Loeve optimale (lorsque la matrice W=Wopt est composée de vecteurs propres KX et la matrice KY=WKXWT a une forme diagonale N 1 N forme nale) de l'efficacité décorrélante, on considérera la valeur de l'entropie excédentaire moyenne H (W, K X) = H cp (W, K X) H cp (Wopt , K X), qui s'exprime à travers les éléments des matrices K X = (cov(xi, x j))i, j = 0 et W = (wi, j)i, j =0 comme suit :

Plus la valeur de H(W,KX) est grande, plus l'efficacité de la transformation décorrélée avec la matrice W est faible. Les calculs numériques de la valeur (4) pour diverses transformations et types de matrices de covariance ont montré des résultats tout à fait cohérents avec les données connues. obtenu par d'autres méthodes, par exemple selon Pearl (Pearl J. On coding and filtering stationary signals by discrete Fourier transforms // IEEE Trans. Inf. Theory. - 1973. - Vol. ITP. 229-232.).

Le modèle d'un signal discret (vecteur X), qui possède des statistiques de signaux discrets, est d'un grand intérêt pour l'analyse. Processus de Markov premier ordre, lorsque la matrice de covariance a la forme suivante :

Ce modèle est souvent utilisé pour décrire la corrélation inter-lignes et inter-colonnes dans des images discrètes. À =1, ​​lorsque toutes les composantes du vecteur d'origine X sont identiques (pour deux échantillons quelconques du vecteur, le coefficient de corrélation égal à un), le calcul du critère (4) introduit pour la matrice (5) est impossible, car dans ce cas nous avons det K X = 0. En même temps, dans les zones de fond de l'image 1. Au chapitre 2 le théorème suivant a été prouvé.

Théorème 2.1. Pour n'importe qui matrice orthogonale W (NN) tel que j = 0,1,... N 1 : w0, j = (la fonction de base d'indice nul est la composante constante normalisée) et la matrice de covariance (5) Diverses études, dont celles réalisées au chapitre 2 , montrent que parmi les transformations discrètes dotées d'algorithmes de calcul rapides (pour la dimension N, implémentées dans les opérations arithmétiques ~ NlogN), les caractéristiques de décorrélation du processus de Markov (5) les plus proches de la transformation optimale de Karhunen-Loeve sont obtenues en utilisant la DCT.

Cependant, malgré la disponibilité d'algorithmes de calcul rapides bien développés, la DCT nécessite fondamentalement des opérations de multiplication pour sa mise en œuvre et est sensiblement inférieure en termes de volume de calculs, par exemple aux transformations de Haar, Walsh et Chrestenson-Levy. Une question distincte, à laquelle une attention considérable est accordée dans le chapitre 2, est la construction d'une nouvelle transformation qui présente à la fois des caractéristiques de décorrélation élevées pour le modèle (5) et des algorithmes de calcul beaucoup plus rapides que pour la DCT. La transformée pseudocosinus discrète résultante est définie pour des vecteurs de dimension N, ce qui permet le développement N=N1…Nn, avec k Nk(2,3,4). La représentation N=N1…Nn doit s'écrire avec un nombre minimum de facteurs Nk, en les disposant sans diminuer, c'est-à-dire : k, m>k : NkNm. Par exemple, pour N=8 nous avons N1=2, N2=4 (mais pas N1=4, N2=2 et non N1=N2=N2=2). Ensuite la matrice DPKP WN (dans ce cas, l'indice indique la dimension de la transformation) est construite comme un produit direct2 WN = WN 1 ... WN n matrices DPKP élémentaires WN k (W2,W3,W4), k=1 ,...,n, où les matrices élémentaires orthogonales Sous le produit tensoriel (direct) des matrices D=(dl,m) (l=0,…,-1; m=0,…,-1) et et sont obtenu grâce à certaines modifications des matrices DCT de la dimension correspondante. Matrices élémentaires peut être représenté comme le produit d'une certaine matrice diagonale D par une matrice C, et la structure C permet de réaliser la multiplication par un vecteur arbitraire U uniquement en utilisant les opérations d'addition et de soustraction de nombres (la multiplication par 2 équivaut à une addition, 2x=x+x). Exactement:

Des propriétés du produit tensoriel découle la représentation WN = D N C N, C N = C N 1 ... C N n. Les matrices C2, C3, C4, D2, D3, D4 sont données ci-dessus. Ainsi, la mise en œuvre du DPKP Y = WN X = D N C N X consiste en la mise en œuvre de la multiplication de la matrice CN par le vecteur, Y = C N X, et de la normalisation ultérieure du vecteur résultant Y, Y = D N Y. Pour calculer le DPKP, il est pratique d'utiliser des algorithmes rapides basés sur la représentation factorisée pour les matrices3 :

matrice unitaire de dimension N j N j. Puisque les matrices TN j) sont constituées d'une certaine manière de blocs matriciels clairsemés C N j, multiplier la matrice TN j) par un vecteur se réduit également aux seules opérations d'addition et de soustraction de nombres. Algorithmes rapides Les DPCP inversés sont construits de la même manière, car dû à opT) () A noter que la normalisation (multiplication par la matrice DN) requise lors du calcul du DPKP et du DPKP inverse pour le schéma de compression avec quantification scalaire des coefficients de transformation n'entraîne aucune complication des calculs.

La normalisation peut être combinée lors de la compression des données avec l'étape du scalaire appelée vecteur Y du pas de quantification individuel qj = q/djj (où d jj est un élément de la matrice de normalisation diagonale D N). Lors de la déquantification de y j = m~ j, le multiplicateur pour l'élément y j doit être choisi sous la forme mj=qdjj.

Comme le montrent les calculs de l'entropie excédentaire moyenne (4) et de la corrélation résiduelle selon Pearl, pour les données avec statistiques de processus de Markov de premier ordre (5), DPKP est plus efficace en décorrélation par rapport à d'autres transformations rapides, dont la mise en œuvre réduit également uniquement aux opérations d'addition et de soustraction de nombres.

Chapitre trois(48 pages) est consacré à l’étude de l’utilisation de la transformée discrète de Chrestenson-Levy (DCLT) pour la compression d’images et constitue un développement des recherches menées dans le cadre du travail de thèse de l’auteur.

Pour étayer la validité de cette idée, voir pp. 84-85 de la monographie « Abstract systèmes algébriques et traitement du signal numérique » / Varichenko L.V., Labunets V.G., Rakov M.A. - Kiev : Naukova Dumka, 1986. – 248 p.

L'idée derrière l'algorithme de compression proposé au chapitre 5 est basée sur les travaux de Lewis-Knowles6 (LK) et Xiong-Ramchandran-Orchard7 (XRO). Lorsqu'il est codé Lewis A.S., Knowles G. Compression d'image utilisant la transformation en ondelettes 2D // IEEE Trans.

Processus d'image. – 1992. – Vol. 1. - N° 2. – P.244-250.

Lors du développement de la topologie S dans XRO, une carte binaire (ni) a été utilisée pour tous les nœuds de l'arbre à l'exception des feuilles : si ni=0, alors l'arbre à ce nœud est élagué, et si ni=1, alors au moins les descendants immédiats sont conservé. Ceci est illustré sur la Fig. 2A. Le codage des caractéristiques statistiques (ni) n'est pas utilisé dans l'algorithme XRO. Dans le même temps, les attributs (ni) des nœuds voisins (par position dans la sous-bande) sont des quantités corrélées. Pour prendre en compte cette corrélation, dans l'algorithme développé, il est proposé de regrouper les caractéristiques des nœuds voisins (ni )iC j en élément unique données, de sorte que la carte d'élagage (topologie des arbres) soit décrite par un nouvel alphabet de données avec des symboles Ni=(ni1,ni2,ni3,ni4)=ni1+2ni2+4ni3+8ni4, qui sont également codés statistiquement. La nouvelle fonctionnalité étendue Nj s’avère être associée au nœud j d’un niveau supérieur, voir Fig. 2B.

Élagage des branches Figure 2. Méthode d'élagage des branches lors de la visualisation des nœuds couche par couche : A – algorithme XRO, B – codage topologique proposé. Ci=(i1,i2,i3,i4) L'idée, qui remonte aux travaux de LK et est utilisée sous la même forme dans XRO, est la suivante : plus la valeur absolue du coefficient d'ondelette wi (ou énergie, wi2) du nœud parent i, moins il est probable qu'une branche nulle (c'est-à-dire coupée) apparaisse à ce nœud. Une prédiction plus précise de l’occurrence de la branche nulle peut être réalisée en utilisant Xiong Z., Ramchandran K. et Orchard M.T. Quantification espace-fréquence pour le codage d'images par ondelettes // IEEE Trans. Processus d'image. – V.6 – mai 1997, p. 677-693.

de la valeur prédite Pi est une somme qui comprend, en plus de wi2, également les carrés des valeurs au nœud i. Pour la valeur prédite du nœud i, il est proposé d'utiliser le montant suivant valeurs absolues coefficients d'ondelettes :

où les ensembles d'indices de sommation sont déterminés parmi les voisins du nœud i dans la sous-bande conformément à la Fig. 3. Les coefficients de pondération inclus dans la somme ont été obtenus à la suite du traitement statistique d'un certain nombre d'images de test afin d'identifier la valeur maximale de l'échantillon pour le coefficient de corrélation entre la valeur prédite (10) et l'énergie des coefficients d'ondelettes quantifiés. des descendants immédiats Ci : Pi, w2 max.

L'algorithme de compression d'ondelettes proposé utilise plusieurs modèles statistiques. La fonction du codeur arithmétique, qui estime, à l'aide de modèles statistiques internes, le nombre de bits nécessaires pour coder le symbole c dans le kème flux, sera notée H(k,c). La désignation Hspec fait référence aux flux dans lesquels sont codés des coefficients d'ondelettes quantifiés, Hmap - aux flux dans lesquels sont codés les signes du début de la branche zéro. Les arbres de spectre sont traités séquentiellement ; Après avoir optimisé la topologie de l'arbre suivant, il faut le coder, et ainsi adapter les modèles statistiques du codeur arithmétique.

Etape 0. /* initialisation */ i Ln1 : /* tous les nœuds de l'avant-dernier niveau sont visualisés */ /* ajustement des coefficients quantifiés */ /* calcul des fonctions RD de sauvegarde et de rognage des feuilles */ Etape 2. i Ll : /* visualisation du niveau actuel avec tentative de coupe des branches */ Si i0 alors /* n'ont pas atteint le début de l'arbre */ /* détermination de la topologie optimale des branches */ /* ajustement des coefficients quantifiés */ /* préparation de visualiser le niveau suivant */ sinon /* i=0, atteint l'arbre de début */ /* déterminer la topologie optimale de l'arbre */ Étape 3. /* générer et afficher le résultat */ Fin Les nœuds de l'arbre sont visualisés depuis le feuilles jusqu'à la racine. Lors de la première étape (préparatoire), les nœuds i qui n'ont que des descendants immédiats (Ci=Ui) sont parcourus, des tableaux sont formés à partir des valeurs des fonctions RD correspondant aux options de coupe (J U i) et de préservation (J U i) part. Auparavant, à l'étape 1.1, pour chaque nœud feuille, la possibilité d'une minimisation de Lagrange supplémentaire, qui caractérise la quantification scalaire des coefficients d'ondelettes, est analysée. Cette procédure est basée sur les propriétés connues de la distribution de probabilité des coefficients d'ondelettes, selon lesquelles les coûts binaires R pour coder le coefficient sont a priori d'autant plus petits que sa valeur absolue est faible (pour cette raison, pour le cas w = 0, le aucune procédure de minimisation supplémentaire n’est appliquée). Lors de la deuxième étape, qui est effectuée pour tous les nœuds i des niveaux suivants, iLl (l=n-2,...,0), la méthode d'élagage des branches optimale RD est sélectionnée (étapes 2.1-2.2) à partir de nœuds jCi. Les étapes 2.3 et 2. ont la même signification que les étapes 1.1, 1.2. A noter que l'introduction d'une optimisation supplémentaire de la quantification scalaire (étapes 1.1 et 2.3) permet, au même niveau de compression, d'augmenter encore le PSNR de 0,02-0,03 dB.

Pour tous les nœuds, sauf celui de la racine, le choix du modèle de codage des caractéristiques Ni (à l'étape 2.1) se fait à l'aide de la règle définie par la fonction IndMap(i). Pour coder la caractéristique N0 associée à la racine de l'arbre, un flux de données distinct est utilisé, auquel est classiquement attribué le numéro 0 (voir étape 2.6).

Comme il ressort de la description ci-dessus de l'algorithme d'optimisation, rôle vital dans son travail, les fonctions IndMap(Pi) et IndSpec(i) jouent un rôle, qui fixent les règles de sélection des flux pour le codage des données. La première fonction sélectionne le modèle de codage de caractéristiques Ni=(ni1,ni2,ni3,ni4) en fonction de la valeur moyenne des valeurs prédites Pi (10), i=i1,i2,i3,i4, et a la forme suivante :

Des seuils (t1,t2,t3)=(0,3;1,1;4,0) pour la sélection des modèles ont été trouvés suite à la minimisation de la longueur du code binaire de sortie R(t1,t2,t3) lors du traitement des images de test bien connues Lena, Barbara, Goldhill. Les expériences ont également montré qu’introduire un plus grand nombre de modèles pour les fonctionnalités n’a aucun sens.

La deuxième fonction clé de l'algorithme de compression d'ondelettes, IndSpec(i), est une règle de sélection de modèle pour coder les coefficients d'ondelettes qui n'entrent pas dans les branches zéro. Pour coder les coefficients spectraux, il est plus efficace d'utiliser une valeur prédictive obtenue non seulement du nœud parent, mais également des coefficients d'ondelettes des nœuds qui sont dans la même sous-bande, à côté de celle en cours de traitement8. Dans l'algorithme considéré, la séquence de codage et de décodage des nœuds du spectre d'ondelettes est déterminée par le diagramme de la figure 4 (les nombres indiquent l'ordre de traitement des sous-bandes). Pour une utilisation dans la fonction IndSpec(j), la valeur prédite du nœud actuel j (marqué en noir) est formée s j = 0,36 Pi + 1,06 w j y + w jx + 0,4 w jd, où jy est un nœud voisin vertical, jx est l'idée d'utiliser le contexte des coefficients d'ondelettes voisines a été proposée dans l'ouvrage Chrysafis S., Ortega A. Efficient Context-Based Entropy Coding for Lossy Wavelet Image Compression // Proc. Conférence sur la compression des données. – Snowbird (Utah), 1997. – P. 241-250.

nœud voisin horizontal, jd – nœud voisin diagonal (qui ont déjà été traités, voir Fig. 4), Pi est déterminé pour le nœud parent i (jCi) par (10). Dans ce cas, les résultats du traitement des images de test.

Le modèle nul fait référence au codage des coefficients spectraux sous des fonctions de mise à l'échelle et est à nouveau isolé. Le premier modèle inclut les coefficients d'ondelettes de fréquence les plus basses (niveau L1), ainsi que les coefficients pour lesquels la prévision sj est la plus grande.

Caractéristiques données par le tableau. 1. La valeur PSNR (en dB), selon l'algorithme de compression proposé, obtenue lors de la compression d'images de test pour des images de test standard selon l'algorithme proposé, est donnée dans le tableau. 1. Dans les expériences, Lena Barbara Goldhill a utilisé des transformations en ondelettes en cinq étapes tirées des travaux de Wei D., Pai H.-T. et Bovik A. C., Antisymétrique Biorthogonal Coiflets for Image Coding // Proc. Conférence internationale de l'IEEE sur Traitement d'images. – Chicago, 1998. – V. 2. – P. 282-286. Comparaison caractéristiques obtenues avec les résultats de l'application d'autres algorithmes bien connus montre que l'algorithme proposé a de très hautes performances.

Les études finales du chapitre 5 concernent la construction d'un schéma de codage hybride pour le spectre d'ondelettes, lorsqu'en plus de la méthode de découpage des branches des coefficients d'ondelettes décrite ci-dessus, la possibilité d'une « auto-quantification » vectorielle des branches est également autorisée , qui peut être interprété comme un codage fractal dans le domaine des transformées en ondelettes9. L'algorithme hybride résultant nécessite beaucoup plus de calculs, mais la composante fractale du codage s'est avérée être presque complètement supprimée par le schéma de compression d'ondelettes de base basé sur l'élagage des branches. Il convient cependant de noter que la combinaison des deux approches dans un algorithme hybride a été réalisée de manière simple et que les possibilités de développement ultérieur laissent ici un vaste champ de recherche.

Le sixième chapitre (45 pages) est consacré à l'étude des algorithmes de compression dynamique d'images afin de construire un schéma de compression vidéo adapté à la mise en œuvre de logiciels, permettant un traitement en temps réel sur des ordinateurs personnels.

Une image d'une séquence vidéo est une matrice de pixels constituée de M1 lignes et M2 colonnes : B=(bk,l), k=0.1,…,M1-1, l=0.1,…,M2-1, et par un séquence vidéo, nous entendons un ensemble d’images ordonnées B0,B1,…,Bi,…. Appelons le bloc (y,x) du cadre B (y, x – coordonnées entières) une sous-matrice By,x=(bk,l), où k=y,y+1,…,y+N1-1, l=x ,x+1,…,y+N2-1. Dans l'algorithme développé, chaque image de la séquence vidéo est divisée lors du traitement en blocs matriciels adjacents (Bm,n) de taille 88, m,n=0,8,16... Si un bloc Biy,x de la séquence vidéo s'avère dans un certain sens « similaire » au bloc original Bim, n, nous supposons que le bloc Bim,n est un fragment déplacé Biy,x Voir, par exemple, Davis G.M., A wavelet-based Analysis of fractal image compression // IEEETrans. Processus d'image. – 1998. – V.7 – N° 2. – P.141-154.

l'image précédente, et pour encoder un bloc (m,n) de l'image, il suffit de définir les coordonnées du bloc dans l'image précédente, y et x, ou de modifier les coordonnées y-m et x-n. Un cas particulier de bloc déplacé est un bloc stationnaire lorsque m=y, n=x. Si un bloc Bim,n ne peut pas être trouvé similaire dans une trame précédente, le bloc doit être codé comme nouveau. Pour sélectionner la méthode de codage du prochain bloc traité Bim, n, on est à nouveau guidé par le critère du minimum de la fonction de Lagrange J(b)=D(b)+R(b). Supposons que l'argument b= corresponde à l'encodage du bloc déplacé (fixé), et b=1 – le nouveau. Ceux. si J(1)>J(0), alors le bloc est codé comme déplacé, et comme nouveau dans le cas contraire.

Lors de l'utilisation de l'optimisation RD, le problème de la recherche de blocs déplacés est formulé comme suit. Pour un (m,n)-bloc Bim, n donné de la i-ème trame, trouver dans la trame reconstruite précédente un tel (y,x)-bloc B iy,x pour que la fonction de Lagrange RD prenne la valeur minimale. Ici, il est pris en compte que les coordonnées du bloc trouvé seront codées comme relatives, c'est-à-dire vecteur de déplacement r = (y-m, x-n). Pour que la recherche soit effectuée en temps réel, seuls les points (v,u) suffisamment proches du point (m,n) doivent être considérés comme une région. L'augmentation de l'efficacité de la recherche en élargissant la zone est obtenue en utilisant divers algorithmes de recherche dirigée visant à minimiser l'erreur de représentation du bloc déplacé Bim, n Biy,1, qui correspond au cas particulier (11) à =0. Afin de prendre en compte la contribution des coûts bits à la fonction RD J*, nous réaliserons la minimisation (11) étape par étape, en supposant à chaque étape approximativement que les vecteurs déplacement considérés entraînent les mêmes coûts de codage statistique. De plus, pour accroître l’universalité des algorithmes de recherche itérative, nous rechercherons plus précisément les petits mouvements. En effet, si un certain bloc de l'image s'est déplacé d'une distance significative par rapport à l'image précédente, alors le fragment correspondant de l'image est perçu par l'œil humain comme flou, et il n'est pas nécessaire de déterminer avec précision le vecteur de mouvement. Les petits mouvements de blocs sont non seulement prédominants, mais doivent également être suivis avec précision en raison de la nature spécifique de la perception visuelle. L’algorithme de recherche RD proposé a la forme suivante.

Étape 0. Calcul de la valeur de la fonction RD du bloc fixe, r=(0,0) :

Étape 1. Recherche exacte proche de la force brute pour les petits mouvements.

1.1. Parmi les neuf blocs (y,x) de la trame précédente, 1.2. Parmi les neuf blocs (y,x) de la trame précédente, 1.3. Calcul valeurs de la fonction RD Étape 2. Recherche approximative des grands déplacements.

2.1. Parmi les huit blocs (y,x) de la trame précédente, 2.2. Parmi les neuf blocs (y,x) de la trame précédente, (y 4, x 4)((0,0), (2,2), (2,2), (2,2), (2,2), (3,0), (0,3), (3,0), ( 0.3)) 2.3. Calcul de la valeur de la fonction RD Étape 3. Sélection de la meilleure option pour déplacer le bloc.

Fin Pour calculer la valeur de la fonction J0, il faut prendre en compte les coûts en bits pour coder le signe du bloc déplacé : J 0 = J * log2 (mov), où mov est la fréquence d'apparition des blocs déplacés dans données déjà traitées.

Le volume principal de calculs dans l'algorithme donné est associé au calcul des écarts B im, n Biy, x. Pendant les calculs, un point d'essai passe de l'étape 0 à l'étape 1.1, un – de l'étape 1.1 à 1.2, un – de l'étape 2.1 à 2.2. En conséquence, le calcul de l’écart doit être effectué 33 fois.

Pour augmenter l'efficacité de l'algorithme de recherche donné pour le vecteur (y, x) du bloc traité, une prévision doit être effectuée en utilisant les vecteurs () et () de deux blocs voisins déjà traités (voisin vertical et voisin horizontal, respectivement) . La prévision elle-même est constituée des coordonnées relatives y 0, x 0, qui déterminent le transfert du centre de la zone de recherche : du point (m, n) au point (m, n) = m + y 0, n + x 0. Les expériences montrent que le nombre de nouveaux blocs d'images est réduit de 5 à 25 % si l'on accepte la règle suivante pour faire une prévision :

Suivant l'idéologie du standard MPEG, nous traitons également de nouveaux blocs par quantification suivie d'un codage statistique de coefficients DCT bidimensionnels. Soit S=F(Bm,n) le résultat de la DCT du bloc Bm,n. Notons SQ = (~k,l = round(sk,l / qk,l))k,l =0, SQ = (sk,l = qk,l ~k,l )k,l =0, où Q = (qk,l )k,l =0 – une des matrices de quantification JPEG. Pour coder statistiquement la matrice S, l'algorithme de codage contextuel discuté au chapitre 4 est utilisé, qui comprend une étape supplémentaire d'optimisation RD. Soit encore ZQ = (z0,..., z63) le vecteur obtenu suite à la lecture en zigzag des données de la matrice SQ selon la règle définie par la norme JPEG (SQ ZQ), G (ZQ) = (g k )C=1 (0,..., 63) est l'ensemble des indices des éléments non nuls du vecteur ZQ, c'est-à-dire z g k 0 si gkG ; gkG : z g k = 0. L'optimisation RD du codage statistique est possible en allongeant la série nulle en réduisant le nombre d'éléments dans l'ensemble G (en mettant en plus à zéro les composantes du vecteur ZQ). Afin d'éviter une complication notable de l'algorithme de codage, nous analyserons uniquement la possibilité d'augmenter la série zéro finale, ce qui contribue le plus à minimiser la fonction J(ZQ)=D(ZQ)+R(ZQ ). Soit ZQ le vecteur obtenu à partir du vecteur ZQ suite à la mise à zéro des dernières composantes (zk )k = g m +1, c'est-à-dire

G (ZQ) = (g k )m=1 G (ZQ), m=1,…,C. Alors l'optimisation RD la plus simple consiste à rechercher un indice g m * G (ZQ) tel que la procédure de codage d'un nouveau bloc d'image considérée ci-dessus suppose l'utilisation d'une matrice de quantification Q donnée. Un algorithme de codage universel doit fonctionner avec un certain ensemble de matrices de quantification (Qj) avec la possibilité de sélectionner celles requises pour des conditions spécifiques.

Si l'ensemble est suffisamment grand, alors la sélection de la matrice de quantification Q basée sur le principe de minimisation de la fonction JQ (12) se transforme en une procédure lourde qui ne peut être mise en œuvre en temps réel par des moyens standards. De plus, avec une large gamme de valeurs possibles pour l'indice j, son codage séparément pour chaque nouveau bloc entraîne des coûts de bits supplémentaires inacceptablement élevés. Par conséquent, seules quelques matrices de l’ensemble recommandé par JPEG ont été sélectionnées comme ensemble initial, qui correspondent aux niveaux de qualité le meilleur, le pire et certains intermédiaires. Dans les expériences, le nombre de matrices |(Qj)|=4 a été choisi. Pour accélérer l'exécution des opérations de division, nécessaires à la quantification, les éléments des matrices (Qj) ont été arrondis à la valeur la plus proche 2k, k=0,1,... Cette approche permet de remplacer les opérations de nombre entier division et multiplication avec décalages de bits de la représentation binaire des nombres, qui sont généralement effectuées beaucoup plus rapidement par un équipement réel.

Compte tenu du coût en bits nécessaire au codage de l'indice de la matrice de quantification, la fonction de Lagrange correspondant au codage d'un nouveau bloc d'image est définie comme suit :

J = min (J Q log 2 Q) log 2 new, où JQ est conforme à (12), Q est la fréquence d'apparition de la matrice Q, new est la fréquence d'apparition de nouveaux blocs lors des traitements précédents.

Lors de l'étude des caractéristiques de l'algorithme de compression vidéo final, pour estimer l'ampleur de l'erreur de codage dans la séquence reconstruite B0, B1,..., B K 1, le rapport entre la valeur maximale du signal et du bruit a été utilisé, qui a été déterminé comme suit :

où M1 et M2 définissent la taille du cadre en pixels. Les séquences de tests bien connues News, Container ship, Hall Monitor, Akiyo, Claire ont été choisies pour les expériences. Tous ont une taille d’image de 144 176 pixels. Avant les expériences, les séquences originales étaient allégées : seule une image sur trois, B3k (k=0,...,24), était utilisée pour former ces séquences vidéo de 25 images, qui étaient ensuite traitées. Cet amincissement temporel a été conçu pour simuler un taux de capture vidéo de 10 images par seconde, au lieu de l'original (pour toutes les séquences ci-dessus) de 30 images par seconde. Seule la composante Y de luminosité a été traitée et seule la composante de luminosité a été utilisée pour analyser l'erreur. La compression logicielle des séquences vidéo a été réalisée en temps réel.

Les résultats des expériences numériques obtenues par l'étudiant diplômé F.V. Strelkov sont reflétés dans le tableau 2. La valeur PSNR (13) obtenue sur les mêmes séquences vidéo de test affinées de 25 images à l'aide de l'encodeur MPEG accessible au public - http://www.mpeg .org /MSSG. La longueur du fichier de données compressé obtenu dans chaque expérience est exactement égale au produit de la taille du flux binaire de données (indiqué dans le tableau) par un facteur de 2,5. Dans tous les tests, le schéma de compression proposé donne bons résultats, dépassant les caractéristiques de l'encodeur MPEG-2 spécifié, malgré le fait que le codec mpeg2encode utilisait une recherche exhaustive dans une zone de 2323 pixels pour trouver des blocs d'images déplacés.

Tableau 2. Caractéristiques de compression de l'algorithme proposé L'algorithme de compression vidéo décrit a été implémenté dans un logiciel dans le cadre des travaux menés au Complexe national de recherche et de production « Centre technologique » de Moscou institut d'étatéquipements électroniques et à la centrale nucléaire "Technologie"

La mise en œuvre des bibliothèques de compression vidéo développées a été réalisée dans un certain nombre de systèmes logiciels, parmi lesquels le système de contrôle et d'enregistrement vidéo Visual Security présente le plus grand intérêt pratique (voir.

http://www.tcen.ru/vs).

Les résultats des recherches menées dans le cadre du travail de thèse sont résumés dans dernière section– « Principaux résultats et conclusion » (3 pages).

Le travail de thèse présenté examine divers aspects de l'utilisation de transformations orthogonales discrètes pour la compression d'images numériques, à la fois à partir d'une analyse théorique purement formelle et à partir des exigences et des limites que la pratique impose à des schémas et algorithmes informatiques spécifiques. En général, le contenu du travail est orienté vers l'application, donc la plupart résultats théoriquesétayées par des expériences informatiques dont les résultats, à leur tour, servaient non seulement d’illustration ou de test de la théorie, mais donnaient souvent une impulsion et fournissaient le matériel source pour des recherches ultérieures. Sur la base des résultats des recherches menées dans le cadre de la thèse, les conclusions suivantes peuvent être tirées.

1. Les transformations orthogonales sont le principal outil utilisé pour la décorrélation des données lors de la compression d'images. Au cas où modèle mathématique le signal discret est donné par une matrice de covariance, pour analyser l'efficacité du traitement de décorrélation, il est conseillé d'utiliser le critère d'entropie excédentaire moyenne proposé dans l'ouvrage.

2. Surtout pour la compression des données corrélées, la transformée pseudocosinus discrète (DPCT) a été obtenue et introduite pour la première fois. Dans un schéma de compression qui suppose la présence d'un étage de quantification scalaire des coefficients de transformation, parmi les transformations rapides considérées, dont la mise en œuvre se réduit uniquement aux opérations d'addition-soustraction (Walsh, Haar, pseudocosine), DPKP donne les meilleurs résultats de décorrélation pour un signal discret décrit par le modèle de Markov.

3. En utilisant les algorithmes DPCL rapides obtenus, qui prennent en compte les spécificités du traitement des tableaux réels, le schéma de compression d'image proposé basé sur le codage arithmétique des coefficients DPCL atteint des caractéristiques proches de la version JPEG basée sur DCT en termes de qualité de traitement et complexité informatique.

4. Lors de l'utilisation du codage statistique des coefficients DCT à l'aide de la méthode JPEG, la présence de « sauts » dans le signal discret est la moins souhaitable dans la région centrale des fragments de traitement.

5. La méthode de codage arithmétique multi-modèle (multi-flux) est très efficace lorsqu'elle est utilisée dans divers schémas et algorithmes de compression de données, et l'un des points clés dans le développement de schémas de compression est la définition de règles de sélection du codage actuel. modèle basé sur le contexte des données déjà traitées. Ainsi, l'utilisation de l'algorithme de codage arithmétique contextuel multi-modèle des coefficients DCT proposé au chapitre 4 dans le schéma JPEG augmente l'efficacité de la compression des données de 10 %.

6. Lors de la compression d'images à l'aide d'un codage multimodèle de structures arborescentes de spectres d'ondelettes, la règle de sélection du modèle doit être basée sur un contexte combiné qui prend en compte à la fois l'environnement du coefficient d'ondelette lui-même dans la sous-bande et l'environnement du « parent ». "coefficient. Le nouvel algorithme efficace de compression d'images numériques avec perte obtenu sur cette base, qui a été développé sur la base des résultats de l'étude des propriétés statistiques des spectres de transformées en ondelettes discrètes, présente des caractéristiques de compression élevées avec une complexité de mise en œuvre acceptable pour une large gamme d'applications.

7. Pour éliminer la redondance inter-images (temporelle) des données vidéo, le plus préférable pour une utilisation pratique parmi les algorithmes étudiés pour la compensation par blocs des mouvements devrait être l'algorithme hybride proposé de recherche dirigée, dans lequel les petits mouvements sont recherchés avec précision et soin, et les grands mouvements - plus grossièrement.

8. Lors de l'utilisation de l'algorithme de compression vidéo proposé, qui a été développé sur la base d'une approche d'optimisation RD prenant en compte les exigences et les spécificités de la mise en œuvre du logiciel, la compression et la restauration vidéo en temps réel sont obtenues sur la base d'ordinateurs personnels modernes, avec haute qualité traitement.

D'une manière générale, les travaux de thèse ont obtenu de nouveaux résultats scientifiques dont les dispositions théoriques ont permis de développer et de formaliser de manière significative des procédures d'analyse et de synthèse de schémas de compression d'images numériques basées sur l'utilisation de transformations orthogonales discrètes. Les approches et recommandations développées ont conduit à la construction de schémas et d'algorithmes de compression spécifiques, dont beaucoup ont été implémentés dans des logiciels et ont confirmé expérimentalement l'efficacité de leur application.

Liste des principaux ouvrages sur le sujet de la thèse 1. Efimov A.V., Umnyashkin S.V. Algorithmes rapides pour calculer la transformée discrète de Chrestenson-Levy et estimer ses caractéristiques spectrales // Teor. fonctions et env. : Tr. 7e Saratov. hiver école (1994). Partie 2. - Saratov : Maison d'édition SSU, 1995. - P. 9-20.

2. Efimov A.V., Pospelov A.S., Umnyashkin S.V. Application de la transformée de Chrestenson-Levy aux problèmes de traitement de l'information numérique // International.

conf. "Espaces fonctionnels, théorie de l'approximation, analyse non linéaire", dédié. 90e anniversaire de l'académicien S.M. Nikolsky (27 avril - 3 mai 1995) : Résumé.

rapport - M. : Maison d'édition MIPT, 1995. - P.124-125.

3. Umnyashkin S.V. Application de la transformée discrète de Chrestenson-Levy (DCLT) pour le codage d'images : comparaison avec la transformée de Fourier discrète (DFT) // Vseros. scientifique-technique conf. « Électronique et informatique » du 15 au 17 novembre. 1995 : Résumé. rapport - M. : MGIET (TU), 1995. - P. 265-266.

4. Umnyashkin S.V. Estimation de la dispersion des éléments du spectre d'une transformée en cosinus discrète d'un processus Markov stationnaire du premier ordre Int. conf. selon la théorie env. func., dédié à la mémoire du prof. P.P. Korovkina (Kaluga, 26-29 juin 1996) : Résumé. rapport -T.2.-Tver : TSU, 1996. - P. 217-218.

5. Umnyashkin S.V. Évaluation de l'efficacité de l'utilisation de transformations unitaires pour coder des signaux discrets // Informatique et communications : Sat.

Ouvrages scientifiques éd. V.A. Barhotkina. M. : MIET. - 1997. P.73-78.

6. Umnyashkin S.V. Évaluation de l'efficacité de l'utilisation de transformations discrètes pour la compression des données // « Électronique et informatique – 97 ». Deuxième Conférence scientifique et technique panrusse avec participation internationale(Zelenograd, 25-26 novembre 1997) : Résumé. doc. Partie 2. - P.79.

7. Efimov A.V., Pospelov A.S., Umnyashkin S.V. Fondements théoriques et quelques caractéristiques de l'application des transformations multiplicatives discrètes dans les problèmes de compression d'images numériques // Actes de la conférence internationale « Calcul d'optimisation de la nutrition » (6-8 juin 1997, Kiev) Kiev : Institut de cybernétique du nom de V.M. Glushkov, 1997. - pages 108-112.

8. Efimov A.V., Pospelov A.S., Umnyashkin S.V. Quelques propriétés des systèmes orthonormés multiplicatifs utilisés en traitement du signal numérique // Actes institut mathématique eux. V.A. Steklov RAS.

- T.219. - 1997. - De 137-182.

9. Efimov A.V., Umnyashkin S.V. Sur certaines propriétés du système Haar généralisé et évaluation de l'efficacité de l'utilisation de transformations orthogonales pour la compression des données // Espaces fonctionnels. Opérateurs différentiels. Problèmes d'enseignement mathématique : Actes de l'international. conf., dédié 75e anniversaire du membre correspondant. Prof. L.D. Kudryavtseva. - Tome 1. - M. : Ros. Université de l'Amitié des Peuples, 1998. - pp. 70-73.

10. Oumnyachkine S.V. Sur la modification de la transformée en cosinus discrète // Théorie de l'approximation et analyse harmonique : Proc. rapport international conf.

11. Umnyashkin S.V. Sur modification de la transformée en cosinus discrète // Izv. Tul. État un-ta. Ser. Mathématiques. Mécanique. Informatique. Toula : TulGU, 1998. T. 4. Numéro. 1. pages 143-147.

12. Umnyashkin S.V., Kochetkov M.E. Analyse de l'efficacité de l'utilisation de transformations orthogonales discrètes pour le codage numérique de données corrélées // Actualités des universités. Électronique. - N°6. - 1998. - P. 79-84.

13. Umnyashkin S.V. Sur le clustering des données corrélées. // Les technologies de l'information dans les projets innovants. Aéroport international. conf. (Ijevsk, 20-22 avril 1999) : Documents des rapports. - Ijevsk, IzhSTU, 1999. - P. 59-65.

14. Oumnyachkine S.V. Algorithme de clustering de données corrélées // VII Int. conf. Mathématiques. Économie. Écologie. Éducation. Aéroport international. sym. Séries de Fourier et leurs applications : Proc. doc. – Rostov : Rost. État économie acad., 1999. – P. 211-212.

15. Efimov A.V., Pospelov A.S., Umnyashkin S.V. Quelques problématiques d'utilisation de systèmes multiplicatifs et de transformations dans des problèmes de traitement d'images numériques // VII Intern. conf. Mathématiques. Économie.

Écologie. Éducation. Aéroport international. sym. Séries de Fourier et leurs applications : Proc.

doc. – Rostov : Rost. État économie acad., 1999. – pp. 154-155.

16. Oumnyachkine S.V. Transformation pseudocosine pour la compression de signaux discrets // Technologies de l'information et problèmes de microélectronique.

Assis. scientifique tr. – M. : MIET. – 1999. – P.158-170.

17. Umnyashkin S.V. Algorithme de compression d'images fixes basé sur la transformée en ondelettes discrète // VIIe Conférence internationale « Mathématiques. Ordinateur. Education" (Dubna, JINR, 24-29 janvier 2000) :

Abstrait. doc. – Moscou : Progrès-Tradition, 2000. – P.327.

18. Efimov A.V., Umnyashkin S.V. Sur la structure de certaines transformées en ondelettes directes et inverses // Théorie de l'approximation de fonctions et d'opérateurs : Proc.

rapport Aéroport international. conf., dédié 80 ans. à partir du jour de la naissance S.B. Stechkina (Ekaterinbourg, 28 février – 3 mars 2000). -Ekaterinb. : UrSU, 2000. – P.74-75.

19. Umnyashkin S.V., Strelkov F.V., Joukov V.G. Algorithmes en trois étapes pour la recherche de blocs d'images déplacés // Technologies de l'information et systèmes de contrôle. Assis. scientifique tr. édité par V.A. Barhotkina. – M : MIET, 2000.

– p. 47-55.

20. Oumnyachkine S.V. Compression d'images numériques par transformée discrète de Chrestenson-Levy // Revue scientifique et technique interindustrielle « Complexe de défense - progrès scientifique et technique de la Russie », n° 2, 2000. P.28-39.

21. Umnyashkin S.V., Kosmach M.V. Optimisation de l'encodage des images numériques par la méthode JPEG // Izv. université Électronique. -Non 4-5. -2000. -P.139-141.

22. Umnyashkin S.V. Compensation du mouvement des objets lors de la compression de données vidéo // « Electronique et informatique - XXIe siècle » Troisième conférence scientifique et technique internationale : Proc. doc. – M. : MIET, 2000. – P. 365-366.

23. Oumnyachkine S.V. Algorithme de recherche de blocs déplacés pour le codage d'images vidéo numériques // Interbranch. n.-t. revue « Complexe de défense - progrès scientifique et technologique de la Russie », n° 3, 2001. – pp. 38-41.

24. Umnyashkin S.V. Utilisation du codage arithmétique contextuel pour augmenter la compression des données à l'aide du schéma JPEG // Actualités des universités. Électronique. - N°3. - 2001. – P. 96-99.

25. Umnyashkin S.V. Compression par ondelettes d'images numériques avec prédiction de modèles statistiques // Izv. universités Électronique. - N°5. - 2001. P.86-94.

26. Umnyashkin S.V. Algorithme de codage fractal d'images dans le domaine des transformations en ondelettes // Mathématiques informatiques. Optimisation des calculs : Recueil d'ouvrages scientifiques. – Tome 1. – Kiv : Institut de Cybernétique im.

V.M. Glushkova, 2001. – P. 385-391.

27. Umnyashkin S.V. Compression d'images basée sur une modélisation prédictive mixte d'arbres d'ondelettes // Rapports de l'Université Vxj (Suède) – Mathématiques, sciences naturelles et technologie. – Nr.11 (septembre), 2001. – 18 pages.

28. Umnyashkin S.V., Strelkov F.V. Un schéma optimisé pour le RD pour la compression vidéo en temps réel // Rapports de l'Université Vxj (Suède) – Mathématiques, sciences naturelles et technologie. – Nr.12 (septembre), 2001. – 15 pages.

29. Développement d'algorithmes et de logiciels pour la mise en œuvre de l'analyse numérique et de la compression d'images vidéo en temps réel basés sur un système matériel et logiciel à usage général : Rapport de recherche (final) / NPP « Technologie » ; mains – Umnyashkin S.V. – « Gardien » ; Numéro d'état

rég. 01990011697 ; Inv. N° 01077. – Moscou, 1999. – 74 p.

30. Recherche et développement d'algorithmes logiciels de compression de données avec perte pour le traitement vidéo numérique : Rapport de recherche (final) / NPP « Technologie » ; mains – Umnyashkin S.V. - "Montre"; Numéro d'état rég.

01200004624 ; Inv. N° 100704. – Moscou, 2000. – 48 p.

Signé pour publication : 25 décembre 2001 Arrêté n° 332. Tirage 100 exemplaires. Académicien-ed.l. 2.4. Formater 6084 1/
équations Résumé de la thèse de doctorat en sciences physiques et mathématiques Moscou 2007 Le travail a été réalisé à l'Institut de recherche en mathématiques appliquées et en automatisation..."

« KORNILOV Dmitry Alexandrovich RECHERCHE SUR LES PROPRIÉTÉS DES FULLERENES ET DES NANOTUBES PAR LA MÉTHODE DE DYNAMIQUE MOLÉCULAIRE Spécialité 01.04.07 – Physique de la matière condensée Résumé de la thèse pour le diplôme scientifique de candidat en sciences physiques et mathématiques Saint-Pétersbourg 2003. Le travail a été effectué dans un établissement public d'enseignement supérieur enseignement professionnel Université polytechnique d'État de Saint-Pétersbourg Directeur scientifique : Docteur... »

«CHIRIKOV ANTON MIKHAILOVICH NOUVEAUX THÉORÈMES D'UNICACITÉ POUR LA SÉRIE DE PUISSANCE 01.01.01 - analyse réelle, complexe et fonctionnelle Résumé de la thèse pour le diplôme scientifique du candidat en sciences physiques et mathématiques ST. PETERSBOURG 2011 Le travail a été achevé au Département d'analyse mathématique. Faculté de MathématiquesÉtat russe Université pédagogique eux. Herzen Directeur scientifique, docteur en sciences physiques et mathématiques, professeur Nikolay Shirokov... »

« Sidorov Evgeniy Nikolaevich CARACTÉRISTIQUES DES PROPRIÉTÉS OPTIQUES DU GaAs LOURD DOPÉ : Te DANS DES CONDITIONS DE DISTRIBUTION D'IMPURETÉS CORRÉLÉES Spécialité 01.04.10 - physique des semi-conducteurs RÉSUMÉ de la thèse pour le diplôme de candidat en sciences physiques et mathématiques Tomsk - 2010 Travaux réalisés dans la succursale de Moscou de l'Institut de physique des semi-conducteurs du nom. A.V. Rzhanova SB RAS Directeur scientifique : Candidat en sciences physiques et mathématiques Davletkildeev Nadim Anvarovich Officiel..."

« LYASHEDKO ANDREY DMITRIEVICH Distorsions thermooptiques dans les lasers au néodyme à base d'éléments actifs en plaques avec pompage par diode longitudinale Spécialité : 01.04.21 - physique des lasers RÉSUMÉ de la thèse pour le diplôme scientifique de candidat en sciences physiques et mathématiques Moscou - 2012 Les travaux ont été réalisés à l'Institution budgétaire fédérale des sciences Institut de physique générale du nom SUIS. Prokhorov RAS Directeur scientifique : Docteur en Sciences Physiques et Mathématiques Tsvetkov..."

« UDC : 535.326, 534.18 Pyatakova Zoya Aleksandrovna INTERACTION ACOUSTOOPTIQUE DANS LES CRISTAUX PHOTONIQUES BIDIMENSIONNELS Spécialité 01.04.03 – radiophysique Résumé de la thèse pour le diplôme de candidat en sciences physiques et mathématiques Moscou - 2011 Le travail a été achevé à la Faculté de physique de Moscou université d'état eux. M.V. Lomonossov Directeur scientifique : candidat... »

« Alla Aleksandrovna KRUTIKOVA ANALYSE SPECTRALE DE MATÉRIAUX COMPOSITES À BASE DE SILICIUM NANOCRISTALLIN Spécialité : 02.00.02 – Chimie analytique RÉSUMÉ de la thèse pour le diplôme scientifique de candidat en sciences chimiques Moscou–2007 Le travail a été achevé au département chimie analytique Académie d'État de technologie chimique fine de Moscou. M.V. Lomonossov Directeur scientifique : Docteur en sciences chimiques, professeur Anatoly Alexandrovich Ishchenko Officiel..."

« MATVENKO Sergueï Ivanovitch STRUCTURES PÉRIODIQUES DANS LES SYSTÈMES CORRÉLÉS DE FAIBLE DIMENSION Spécialité 01.04.02 - physique théorique RÉSUMÉ de la thèse pour le diplôme de docteur en sciences physiques et mathématiques Tchernogolovka - 2012 Le travail a été effectué à l'Institution budgétaire de l'État fédéral de l'Institut des sciences de physique théorique nommé d'après... "

«UDC 004.896 AKSENOV Konstantin Aleksandrovich THÉORIE ET ​​PRATIQUE DE SOUTIEN À LA PRISE DE DÉCISION DANS LE DOMAINE DES PROCESSUS DE CONVERSION DE RESSOURCES Spécialité 05.13.01 – Analyse du système, gestion et traitement de l'information Résumé de la thèse pour le diplôme de docteur en sciences techniques Ekaterinbourg - 2011 Travaux effectués à le café Département des systèmes de contrôle automatisés de l'établissement d'enseignement autonome de l'État fédéral d'enseignement professionnel supérieur de l'Oural université fédérale nommé d'après le premier président de la Russie B.N. Eltsine. Scientifique..."

"Voskov Alexey Leonidovich CALCUL DES ÉQUILIBRES DE PHASES PAR LA MÉTHODE DES COQUILLES CONVEXES Spécialité 02.00.04 - chimie physique RÉSUMÉ de la thèse pour le diplôme de candidat en sciences chimiques Moscou - 2010 Les travaux ont été effectués dans le laboratoire de thermodynamique chimique du Département de chimie physique de la Faculté de chimie de l'Université d'État de Moscou du nom de M.V. ova . Directeur scientifique : Docteur en sciences chimiques, professeur Gennady Fedorovich Voronin Officiel..."

« Kravchenko Igor Vitalievich CARACTÉRISTIQUES DE LA STRUCTURATION DE SYSTÈMES EN COUCHES ET DISPERSÉS DE POLYMÈRES INCOMPATIBLES SOUS ÉCOULEMENT DE CISAILLEMENT. MODÉLISATION NUMÉRIQUE 02.00.06 – Composés de haut poids moléculaire Résumé de la thèse pour le diplôme de candidat en sciences physiques et mathématiques Moscou 2010 www.sp-department.ru Le travail a été réalisé à l'Institut des problèmes de l'Institution de l'Académie des sciences de Russie physique chimique Directeur scientifique de l'RAS : Docteur en sciences physiques et mathématiques Patlazhan..."

« Gribov Andrey Gennadievich ANALYSE DES ÉCHANGES D'INFORMATIONS DANS LES SYSTÈMES DE GESTION Spécialité 13.05.01 – Analyse de systèmes, gestion et traitement de l'information (industrie) RÉSUMÉ de la thèse pour le diplôme scientifique de candidat en sciences physiques et mathématiques Moscou - 2011 Le travail a été réalisé au Institution du Centre informatique de l'Académie russe des sciences. Les AA Dorodnitsyn RAS au Département des problèmes d'optimisation appliqués. Encadreur scientifique : Docteur en Sciences Physiques et Mathématiques..."

«Jardimalieva Gulzhian Iskakovna (CO)POLYMÉRISATION ET TRANSFORMATIONS THERMIQUES DE MONOMÈRES CONTENANT DES MÉTAUX COMME MOYEN DE CRÉER DES MÉTALLOPOLYMÈRES ET DES NANOCOMPOSITES 02.00.06 – composés de haut poids moléculaire RÉSUMÉ de la thèse pour le diplôme scientifique de docteur en sciences chimiques Tchernogolovka - 2009 www.sp-department.ru Le travail a été réalisé à l'Institut des problèmes de physique chimique de l'Académie des sciences de Russie Docteur en sciences chimiques, professeur consultant scientifique : Anatoly Dmitrievich, docteur en sciences chimiques, a aidé..."

« GAVRILOV Aleksey Andreevich RECHERCHE DE SYSTÈMES POLYMÈRES ALÉATOIRES LINÉAIRES ET EN RÉSEAU PAR MÉTHODES DE MODÉLISATION INFORMATIQUE Spécialités 02.00.06 composés de haut poids moléculaire, 01.04.07 – physique de la matière condensée Résumé de la thèse pour le diplôme scientifique de candidat en sciences physiques et mathématiques Moscou – 201 3 Les travaux ont été réalisés au Département de physique des polymères et des cristaux, Faculté de physique, Université d'État de Moscou, du nom de M.V. Lomonossov...."

« NGUYEN XUAN NGIA RELAXATION DIELECTRIQUE DES STRUCTURES SUPRAMOLECULAIRES DANS LES FLUIDES BIOLOGIQUES AUX BASSES FREQUENCES INFRANORMALES Spécialité - 01.04.04. Électronique physique RÉSUMÉ de la thèse pour le diplôme de candidat en sciences physiques et mathématiques Saint-Pétersbourg - 2011 Le travail a été effectué à l'établissement d'enseignement public d'enseignement professionnel supérieur de l'Université polytechnique d'État de Saint-Pétersbourg Superviseur scientifique :..."

«Naimushina Ekaterina Alexandrovna. UDC 538.945 APPLICATION DE LA MÉTHODE DE SPECTROSCOPIE ÉLECTRONIQUE À RAYONS X POUR L'ÉTUDE DE LA STRUCTURE CHIMIQUE DES OXYDES DE CUIVRE COMPLEXES À L'ÉTAT SUPRACONDUCTEUR Spécialité 01.04.01. – instruments et méthodes physique expérimentale RÉSUMÉ de la thèse pour le diplôme de candidat en sciences physiques et mathématiques Ijevsk - 2004 Le travail a été réalisé dans le laboratoire de spectroscopie électronique de l'Institut de physique des surfaces de l'État d'Oudmourtie..."

« Dashkov Evgeniy Vladimirovich Sur les calculs propositionnels représentant le concept de prouvabilité 01.01.06 – logique mathématique, algèbre et théorie des nombres RÉSUMÉ de la thèse pour le diplôme scientifique du candidat en sciences physiques et mathématiques Moscou - 2012 Le travail a été achevé au département logique mathématique et théorie des algorithmes de la Faculté de mécanique et de mathématiques de l'Université d'État de Moscou du nom de M.V...."

« Rusakov Dmitry Mikhailovich DIAGRAMMES DE PROGRAMME AVEC CONSTANTES Spécialité 01.01.09 – mathématiques discrètes et cybernétique mathématique RÉSUMÉ de la thèse pour le diplôme universitaire de candidat en sciences physiques et mathématiques Moscou - 2008 Le travail a été réalisé au Département de cybernétique mathématique de la Faculté de mathématiques computationnelles et de cybernétique de l'Université d'État de Moscou du nom de M.V. Lomonossov. Scientifique..."

« REMEEVA ALFIA NILOVNA MÉTHODES D'ENSEIGNEMENT DE LA PHYSIQUE DANS LES CLASSES DE PROFIL SOCIO-ÉCONOMIQUE 13.00.02 – théorie et méthodes d'enseignement et d'éducation (physique) RÉSUMÉ de la thèse pour le diplôme scientifique du candidat sciences pédagogiques Chelyabinsk - 2008 Les travaux ont été réalisés au Département de théorie et méthodes d'enseignement de la physique de l'État établissement d'enseignement enseignement professionnel supérieur État de Sterlitamak académie pédagogique Responsable scientifique : docteur... »

Les transformations utilisées pour compresser les images doivent être rapides et, si possible, faciles à mettre en œuvre sur un ordinateur. Cela suppose essentiellement que de telles transformations doivent être linéaire. Autrement dit, les valeurs converties AVEC( sont des combinaisons linéaires (sommes avec certains facteurs ou poids) des quantités originales (pixels) DJ, et le multiplicateur ou poids correspondant est un certain nombre Wij(facteur de conversion). Moyens, AVEC( -]G\- djWij, où r, j= 1,2,..., p. Par exemple, quand n= 4 cette transformation peut s'écrire forme matricielle qui dans le cas général prendra la forme suivante : C = W D. Chaque vecteur colonne de la matrice W est appelé « vecteur de base ».

Une tâche importante consiste à déterminer les coefficients de conversion wij. La principale exigence est qu'après la transformation, la valeur Avec\ serait grande, et toutes les autres quantités C2, сз,... deviendraient petites. Rapport de base С( = Ylj djWij suppose que AVEC( sera important si le poids Wij améliorera les valeurs correspondantes déjà. Cela se produira, par exemple, si les composantes des vecteurs wij Et DJ ont des significations similaires et des signes identiques. Vice versa, AVEC( sera petit si les poids sont petits et que la moitié d'entre eux ont le signe opposé au signe du nombre correspondant déjà. Par conséquent, si c* grand est obtenu, alors les vecteurs W(j sont similaires au dj vectoriel original, et petits AVEC( signifie que les composants wij très différent de déjà. Par conséquent, les vecteurs de base wij peut être interprété comme un outil permettant d’extraire certaines caractéristiques du vecteur d’origine.

En pratique les poids Wij ne devrait pas dépendre des données sources. Dans le cas contraire, ils devront être ajoutés au fichier compressé pour être utilisés par le décodeur. Cette considération, ainsi que le fait que les données sources sont des pixels, c'est-à-dire des quantités non négatives, déterminent la manière dont les vecteurs de base sont choisis. Le premier vecteur, celui qui génère Avec\, doit être constitué de nombres proches, éventuellement correspondants. Cela améliorera les valeurs de pixels non négatives. Et tous les autres vecteurs de base doivent être constitués pour moitié de nombres positifs et pour l’autre moitié de nombres négatifs. Après avoir multiplié par valeurs positives et leur addition, le résultat sera un petit nombre. (Cela est particulièrement vrai lorsque les données source sont proches et nous savons que les pixels voisins ont tendance à avoir des valeurs proches.) Rappelez-vous que les vecteurs de base fournissent un outil pour extraire des caractéristiques des données source. Par conséquent, un bon choix serait des vecteurs de base très différents les uns des autres et donc capables d’extraire des caractéristiques différentes. Cela conduit à l’idée que les vecteurs de base devraient être mutuellement orthogonaux. Si la matrice de transformation W est constituée de vecteurs orthogonaux, alors la transformation s'appelle orthogonal. Une autre observation qui permet le choix correct des vecteurs de base est que ces vecteurs doivent avoir des fréquences de changements de signe de plus en plus élevées afin d'extraire, pour ainsi dire, les caractéristiques haute fréquence des données compressées lors du calcul des quantités transformées.

Le premier vecteur de base (rangée supérieure W) est composé uniquement de un, donc sa fréquence est nulle. Tous les autres vecteurs ont deux +1 et deux -1, ils produiront donc de petites valeurs converties et leurs fréquences (mesurées par le nombre de changements de signe dans une ligne) augmenteront. Cette matrice est similaire à la matrice de transformation d'Hadamard-Walsh (voir équation (3.11)). Par exemple, transformons le vecteur initial (4,6,5,2)

Le résultat est assez encourageant puisque le nombre Avec\ est devenu grand (par rapport aux données originales) et les deux autres nombres sont devenus petits. Calculons les énergies des données originales et transformées. L'énergie initiale est 4 2 + b 2 + 5 2 + 2 2 = 81, et après la transformation, l'énergie est devenue 17 2 + 3 2 + (-5) 2 + I 2 - 324, soit quatre fois plus grande. L'énergie peut être économisée en multipliant la matrice de transformation W par un facteur 1/2. Le nouveau produit W-(4,6,5,2) t sera égal à (17/2,3/2, -5/2,1/2). Ainsi, l'énergie est conservée et concentrée dans la première composante, et elle s'élève désormais à 8,5 2 /81 = 89 % de l'énergie totale des données originales, dont la première composante ne représentait que 20 %.

Un autre avantage de la matrice W est qu'elle effectue également la transformation inverse. Les données originales (4,6,5,2) sont restaurées à l'aide du produit W-(17/2,3/2, -5/2,1/2) t.

Nous sommes désormais en mesure d’apprécier les mérites de cette transformation. Nous quantifions le vecteur transformé (8.5,1.5,-2.5,0.5) en l'arrondissant à un nombre entier et obtenons (9,1,-3,0). Nous effectuons la transformation inverse et obtenons le vecteur (3.5,6.5,5.5,2.5). Dans une expérience similaire, nous supprimons simplement les deux plus petits nombres et obtenons (8, 5,0, -2,5,0), puis effectuons la transformation inverse de ce vecteur grossièrement quantifié. Il en résulte des données reconstruites (3,5.5,5.5,3), qui sont également assez proches de l'original. Donc, notre conclusion : même cette transformation simple et intuitive est un bon outil pour « éliminer » la redondance des données d'origine. Des transformations plus sophistiquées produisent des résultats qui permettent de récupérer des données avec un degré élevé de similarité, même avec une quantification très grossière.

« Image en impression » - Spécificités de l'image en impression. La propriété principale d'une image imprimée. Livre. Particularité les plus belles imprimeries. Pluralité Massivité Accessibilité publique. Connecter des images avec du texte. L'art du livre. Fonte.

« Graphiques vectoriels et raster » - Les primitives vectorielles sont spécifiées à l'aide de descriptions. Principes de construction d'images vectorielles et raster. Les images vectorielles occupent une quantité relativement faible de mémoire. Types d'infographie. Les images vectorielles sont décrites par des dizaines, voire des milliers de commandes. Inconvénients des graphiques raster.

« Infographie » - Les principaux problèmes liés à l'utilisation de graphiques raster. Les types d'infographie diffèrent par les principes de formation des images. Infographie. Graphiques fractals. Types d'infographie. De gros volumes de données. Pixels. Caractéristiques comparatives des graphiques raster et vectoriels. Chaque point de l'écran ne peut avoir que deux états : « noir » ou « blanc ».

«Création d'images graphiques» - Limites du canevas. Tâche 4. Créez un dessin composé de formes automatiques. Créez un dessin à l'aide de la barre d'outils Dessiner. La position de l'image graphique dans le texte. Insérez une image de la collection dans le texte. Toile. Caractéristiques comparatives des graphiques raster et vectoriels. Fonctionnalités de création d'une image vectorielle dans Word 2003.

"Image d'une tête d'homme" - D'autres visages froids et morts sont fermés par des barreaux, comme un cachot. D’autres sont comme des tours dans lesquelles personne ne vit ni ne regarde par la fenêtre pendant longtemps. Quels types de portraits existe-t-il ? Proportions du visage d'une personne. Image des traits du visage. Visage humain et émotions. N. Zabolotski. Quels types de visages existe-t-il ? Dessin d'une tête humaine. Vraiment, le monde est à la fois grand et merveilleux !

« Images raster » - Conclusions de l'expérience. Rouge. Quelles couleurs primaires un ordinateur utilise-t-il ? Codage raster des informations graphiques. Image rastée. Pixels différentes couleurs. Bleu (turquoise). Gris. Rose. Palette ordinateurs modernes. Toutes les couleurs peuvent être numérotées et chaque numéro peut être converti en code binaire.