EXERCICES SUPPLEMENTAIRES SUR LA DCT ET LES TRANSFORMATIONS ORTHOGONALES

Exercice 1

Pour N = 4. Calculez la DFT (TFD) du signal suivant f = [1, −1,1,1]. Esquissez | ck | en fonction de k.

Utilisez vos résultats de la partie (1) pour vérifier le théorème de Parseval dans ce cas particulier. Rappelons que le théorème déclare que l'énergie dans l'espace temps est égale à l'énergie dans l'espace fréquence

=

Exercice 2

En utilisant l'identité d'Euler (équation 1), développez le cosinus du DCT défini ci-dessus (équation 2) en une somme de sinusoïdes complexes et montrez que le DCT peut être réécrit comme la somme de deux DFT modulées en phase:

(2) (1)

où

Exercice 3

Considérons la séquence z (n1, n2) dont 3 × 3 DFT satisfait ;

Déterminez z(n1,n2).

Exercice 4

Considérer une séquence X générant la séquence suivante : 10 11 12 11 12 13 12 11

1 Calculer la matrice de la transformation DCT 8x8

2 Effectuer la transformation de cette séquence.

Exercice 5

montrez que, comme la DFT, la DCT peut être calculée efficacement par une décomposition ligne-colonne, en présentant l'algorithme de cette décomposition.

Considérons la séquence suivante :

Calculer le 2 × 2 DCT X (k1, k2) directement à partir de la définition

pour la séquence en b) calculer X (k1, k2) par la décomposition ligne-colonne. Laquelle des deux approches est la plus efficace?

Exercice 6

Considérer une séquence X générant les points suivants : (2, 3), (1,2) et (3, 1)

1 Calculer la matrice de covariance Cxx.

2 Calculer les valeurs propres de Cxx.

3 Déduire les vecteurs propres de Cxx et la matrice de la transformation KLT.

4 Effectuer la transformation KLT pour ces vecteurs.

Exercice 7

Soit 𝑓 (𝑥, 𝑦) une image numérique de taille 256 × 256. Afin de compresser cette image, nous prenons sa transformée en cosinus discrète 𝐶 (𝑢, 𝑣), 𝑢, 𝑣 = 0, ..., 255 et ne gardons que les coefficients de transformation en cosinus discret pour 𝑢, 𝑣 = 0, ..., 𝑛 avec 0≤𝑛 <255. Le pourcentage d'énergie totale de l'image d'origine qui est conservé dans ce cas est donné par la formule 𝑎𝑛 + 𝑏 + 85 avec 𝑎, 𝑏 constantes. De plus, l'énergie qui est préservée si 𝑛 = 0 est de 85%. Trouver les constantes 𝑎, 𝑏

Exercice 8

Extraire les fonctions de base de la transformée en cosinus discrète 1D, pour le cas m = 8 et pour k = 0,1,. . . , 7, c'est-à-dire, esquisser une fonction de base pour chacune des huit valeurs. Rappel: La transformée en cosinus discrète est donnée par:

Exercice 9

Soit le bloc d’image 88 pixels suivant :

Donnez une estimation approximative de la matrice 8 × 8 correspondante des valeurs transformées que vous vous attendez à trouver. (On recherche une estimation approchée sans calculs.)

Exercice 10

La transformation de Fourier rapide (FFT) est l'algorithme le plus connu pour calculer la transformation de Fourier discrète (DFT). L'une de ses nombreuses applications est la compression du signal. Supposons que le vecteur f = [f0, ..., fN − 1] représente un signal à compresser.

Lors de la compression, nous n'appliquons généralement pas FFT directement. Au lieu de cela, nous étendons d'abord le signal d'une certaine manière. Discutez très brièvement des deux extensions les plus courantes qui donnent lieu à la transformée en cosinus discret (DCT) et à la transformée en sinus discret (DST).

Décrivez brièvement comment vous utiliseriez DCT ou DST pour compresser.

Lequel des deux, DCT ou DST, pensez-vous être plus efficace pour comprimer les signaux? Vous devez mentionner le taux de décroissance attendu des coefficients de Fourier et le phénomène de Gibbs.

La FFT réduit le coût de calcul naïf de l'application de la DFT des N2opérations à NlogN. Décrivez brièvement comment cela est réalisé.

Exercice 11

On souhaite transmettre une image à niveau de gris (8 bits par pixel) sur une ligne de 9600 bits par seconde.

a) Si l’on envoie cette image selon un ordre raster scan, après 15 secondes combien de lignes sont reçues? À quel pourcentage ce nombre de ligne correspond par rapport au nombre de lignes total de l’image.

b) On transmet maintenant l’image de façon progressive. La première approximation consiste à transmettre 1 pixel pour un bloc de 88. Combien dure la transmission de la première approximation.

c) Après avoir reçu la première approximation, combien faut-il encore attendre pour recevoir une deuxième approximation consistant à 1 pixel par bloc 44.

Exercice 12

Soit 𝑓 (𝑥, 𝑦) une image numérique de taille 𝑀 × 𝑁pixels qui est nulle en dehors de 0≤𝑥≤𝑀 − 1, 0≤𝑦≤𝑁 − 1, où 𝑀 et 𝑁 sont des entiers et des puissances de 2. Transformée Hadamard discrète standard de 𝑓 (𝑥, 𝑦), nous relions 𝑓 (𝑥, 𝑦) à une nouvelle 𝑁 × 𝑁 séquence de points 𝐻 (𝑢, 𝑣).
(i) Indiquer le principal inconvénient de la transformation Hadamard discrète.
(ii) Dans le cas de 𝑀 = 𝑁 = 2 et

Calculer les coefficients de transformée de Hadamard de 𝑓 (𝑥, 𝑦)

Exercice 13

Soit 𝑓 (𝑥, 𝑦) l'image numérique 4 × 4 constante suivante qui est nulle en dehors de 0≤𝑥≤3, 0≤𝑦≤3, avec 𝑟 une valeur constante.

Donner la transformée de Hadamard standard de 𝑓 (𝑥, 𝑦) sans effectuer aucune manipulation mathématique.
(ii) Commentaire sur la propriété de compactage énergétique de la transformation Hadamard standard

Exercice 14

Trouvez les DCT-2D des matrices de données X suivantes.

Exercice 15

Nous savons que nous pouvons compresser une image en filtrant les termes à haute fréquence, en ne retenant que ceux à basse fréquence, qui sont les plus importants pour l'œil humain. Que se passera t il si nous faisons le contraire pour une image en niveaux de gris, en filtrant les termes basse fréquence et en conservant les termes haute fréquence ?

Exercice 16 : Propriété de séparabilité

Déterminez si les séquences suivantes sont séparables ou non séparables. Dans chaque cas, justifiez soigneusement votre réponse (soit en prouvant que la séquence n'est pas séparable, soit en déterminant sa décomposition en le produit de deux séquences)

Exercice 16 :

Le diagramme de flux IDCT pour Ν = 8 basé sur les travaux de Wang et Suehiro et Hatori est illustré à la figure suivante. Notez les facteurs matriciels qui correspondent à cet organigramme. Indiquez le nombre de multiplications et le nombre d'ajouts requis pour cet algorithme.

Avec :

Comme le DCT est une transformation orthogonale, les facteurs matriciels pour le DCT peuvent être développés à partir de ce diagramme de flux (ci-dessus). À l'aide de ces facteurs matriciels, tracez le diagramme du DCT Ν = 8. Montrez que (y compris le facteur de normalisation 2 / N): (facteurs matriciels pour DCT) (facteurs matriciels pour IDCT) = matrice d'identité,

Exercice 17 :

Le diagramme de flux de la matrice T utilisée dans une approximation DCT à faible coût de calcul est représenté ci-dessous. Les données d’entrées sont les xn et les sorties sont Xk. Les flèches en plein sont des multiplications par 1 et en pointillées sont des multiplications par -1. Sous forme matricielle ceci correspond à : X=T.x

Selon ce diagramme de flux, combien d’opérations sont-elles nécessaires pour effectuer la transformation X=T.x

Trouvez la matrice T

Dans le cas d’une transformation 2 D 88, combien d’opérations seront-elles nécessaires ?

Exercice 18 :

Même chose que l’exercice précédent avec ce diagramme de flux d’une autre transformation approximée à faible coût.

Exercice 19 :

Toujours avec le même principe des approximations de transformation où X=C88.x. La matrice C88 est donnée ci-dessous.

Donnez le diagramme de flux optimisé

Selon ce diagramme de flux, combien d’opérations sont-elles nécessaires pour effectuer cette transformation

Dans le cas d’une transformation 2 D 88, combien d’opérations seront-elles nécessaires ?

Comparer cette transformation aux deux précédentes de point de vue nombre d’opérations

Dans un schéma de compression basée sur les transformations, l’étape qui suit la transformation est la quantification. Sous sa forme la plus simple elle consiste à supprimer les composantes hautes fréquences, souvent non significatives (faibles amplitudes), pour ne garder que les composantes basses fréquences généralement plus significatives. Pour un bloc d’images 88 et en utilisant une transformation 2D (comme le propose la question 3), nous obtiendrons un bloc transformation 88=64 coefficients. Mais on va supposer que nous n’allons retenir que 44 coefficients uniquement (les plus significatifs). Donc 16 coefficients uniquement sur les 64 coefficients calculés précédemment ont été retenus. Ceci nous pousse donc, pour économiser le temps de calcul davantage de la transformation, à ne pas calculer les coefficients (au nombre de 64 – 16 =48 coefficients) qui seront éliminés par l’étape de quantification. Proposez donc une modification de la matrice C pour ne calculer que les 16 coefficients qui nous allons garder dans l’étape suivante à savoir la quantification. Quel est alors le gain de calcul en nombre d’opérations ?