---
title: TP Codage, quantification, compression et filtrage
---

INFO001 TP Codage, quantification, compression, filtrage linéaire et morphologique
===

> [name=Jacques-Olivier Lachaud, Stephane Breuils][time=2025][color=#907bf7]

###### tags: `info001` `tp`
Pour nous échauffer, je vous propose de commencer ce TP avec une application de filtrage morphologique.

## 0. Filtrage morphologique pour la détection
On s'interesse à compter de manière automatique le nombre de composantes connexes **totalement visible** dans une image médicale. Récupérer l'image `globBlancRed.jpg` sur moodle. Cette image possède des 'tâches' qu'il faut retirer.
1. Reprendre le programme `ex1.cpp`
2. Convertir l'image en niveau de gris et la binariser (`110, 255, THRESH_OTSU`).
3. Supprimer les petites 'tâches'.
4. Appliquer le programme commenter et afficher le nombre de composantes connexes et visualiser l'image segmenter (après watershed).
5. Commenter.

:::warning
**Rendu** : Vous rendrez vos programmes c++ (.hpp, .cpp) et un rapport décrivant les structures utilisées et les réponses aux questions.
:::

Dans la suite de ce TP, je vous fais construire une application qui compresse, code et filtre des images. Les différentes étapes de cette partie sont
- Compression naive,
- Codage,
- Quantification,
- Compression/Décompression avec la transformée de Fourier,
- Filtrage et séparation.

Pour la compression d'images, on aura besoin de la définition du taux de compression $\tau$ défini par
$$
\tau = \frac{\text{nombre total de bits de l'image compressée}}{\text{nombre total de bits de l'image d'origine}}
$$

## 1. Compression naive

### 1.1 Avec parcourt ligne par ligne
Dans cette section, on s'interesse à un algorithme naïf de compression. Cet algorithme consiste simplement à stocker l'image sous la forme d'un vecteur dont chaque élément contient un couple `(nbRepetitions,valeurpixel)`. Ce couple stocke le nombre de pixels de valeur identique avec la valeur associée du pixel. A titre d'exemple, l'image compressée obtenue à partir de l'image $3\times3$ suivante
$$
\left(
\begin{array}{ccc}
1&1&1\\
5&5&5\\
5&4&4
\end{array}
\right)
$$
sera le vecteur

{(3,1),(4,5),(2,4)}

1. Donner le taux de compression de l'algorithme naïf sur cette image $3\times 3$.
2. Ecrire une fonction effectuant la compression de l'image `imgSimpleRayures.png` sur moodle. Le prototype de votre fonction est

std::vector<std::pair<int,int>> compressionNaive(Mat imgACompresser) 

4. Ecrire une fonction permettant de décompresser une image compressée avec l'algorithme de compression naïf.
5. Ecrire une fonction qui calcule le taux de compression $\tau$ de votre fonction pour l'image `imgSimpleRayures.png`. Donner les résultats de tau de compression pour différentes images.
6. Est-ce que les étapes compression-décompression induisent une perte de pixels de l'image d'origine?

### 1.2 Avec parcourt colonne par colonne et en zigzag
7. Effectuer la compression avec un parcourt colonne par colonne montré sur la figure ci-dessous (`mat.col(2)`)

8. Effectuer la compression avec un parcourt en zigzag comme sur la figure ci-dessous (parcourt des diagonales)

## 2. Compression par histogramme
On s'interesse dans cette section à une compression qui se base sur les occurences des valeurs de niveau de gris des pixels. Brièvement, cette compression assigne des nombres binaires de longueur variable aux niveaux de gris des pixels. Les niveaux de gris les plus fréquents reçoivent des nombres binaires plus courts que ceux qui apparaissent peu.

Une possibilité pour effectuer cette compression est de passer par la construction de l'arbre binaire de Huffman. Cet arbre est construit de manière à ce que les niveaux de gris les plus probables soient situés plus près de la racine, ce qui leur attribue des codes plus courts.
Pour mieux comprendre la construction de cet arbre, considérons les symboles $M_1,M_2,M_3,M_4,M_5$ représentant des niveaux de gris.
- Les symboles sont classés par ordre d'occurrence décroissante. On assigne alors aux deux symboles d'occurrence la plus faible les bits 0 et 1.
- Ces deux symboles sont combinés en un nouveau symbole, fictif, dont l'occurrence est la somme des occurrences des symboles élémentaires. La liste des symboles est alors mise à jour. Cette liste est toujours classée, et comporte un élément de moins.
- La procédure est réitérée, jusqu’à ce que la liste finale ne contienne plus que deux symboles, auxquels on assigne les bits 0 et 1.
Le codage pour chaque symbole initial est alors établi en repartant « à l’envers » et en concatenant la
suite de 0 et de 1.

Exemple:
On suppose les probabilités des symboles suivants

M1 : p1 = 4
M2 : p2 = 2
M3 : p3 = 2
M4 : p4 = 1
M5 : p5 = 1

L'arbre de Huffman obtenu est représenté dans la figure ci-dessous

Le codage de chaque symbole à partir de cet arbre est

M1 : 10
M2 : 00
M3 : 01
M4 : 110
M5 : 111

1. Vérifier, avec l'exemple, qu'un code ne peut être préfixe d'un autre code. Justifier.
2. Ecrire le programme permettant de former l'arbre de Huffman avec Opencv.
Nous allons commencer par nous occuper de la structure de données pour représenter l'arbre binaire. Je propose d'utiliser trois `std::vector<int>` :
- le premier `std::vector<int> occurences` stocke les occurences des noeuds. Dans l'exemple précédent, les symboles $M1,M2,\cdots,M5$ auront les valeurs $4,2,2,1,1\cdots$.
- le deuxième `std::vector<int> fils_gauche` stocke l'indice du fils gauche du noeud courant. Pour les feuilles, comme $M1,M2,\cdots,M5$, les indices des fils seront $-1$.
- le troisième `std::vector<int>` stocke l'indice du fils droit du noeud courant.
Le contenu des vecteurs avec l'exemple précédent serait

// M1,M2,M3,M4,M5,M45,M23,M145,M12345
{ 4, 2 ,2 ,1, 1, 2, 4, 6, 10}
{-1,-1,-1,-1,-1, 3, 1, 0, 6}
{-1,-1,-1,-1,-1, 4, 2, 5, 7}

Dans le paragraphe suivant, nous nous interessons à un algorithme permettant de construire ces vecteurs.
- Lors de l'ajout d'un nœud, on recherche systématiquement les nœuds ayant la plus faible occurrence. Pour ce faire, la structure de donnnées adaptée est la file de priorité. En c++, on utilise une `std::priority_queue` pour stocker les indices des nœuds :

    auto cmp = [&occurences](int a, int b) { return occurences[a] > occurences[b]; };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> prioqueue(cmp);
    
    // Initialisation de la file de priorite avec les indices initiaux
    for (size_t i = 0; i < occurences.size(); ++i) {
        prioqueue.push(i);
    }

- Boucle principale : Tant que la file de priorité contient plus d'un élément :
-> Extraction : Extraire les deux indices de plus basse occurence de la file de priorité. Appelons-les index1 et index2.
-> Création du nouveau nœud parent : Ajoutez la somme des occurences des nœuds `index1` et `index2` au vecteur ``occurences``.
-> Ajouter `index1` à `fils_gauche` (pour le nouveau nœud).
-> Ajouter `index2` à `fils_droit` (pour le nouveau nœud).
-> Ajout d'un nouveau nœud à la file de priorité : Ajouter l'indice du nouveau nœud (qui est le dernier indice ajouté aux vecteurs, fonction `push`) à la file de priorité.

Enfin, pour générer les codes (bits), on parcourt l'arbre depuis la racine vers les feuilles (parcourt des vecteurs). Pour ce faire, on utilise une fonction récursive de parcourt dont le pseudo-code est le suivant

Fonction genererCodes(indiceNoeud, codeCourant, fils_gauche, fils_droit, codes)
    // Cas de récursion final : on est sur une feuille
    SI fils_gauche[indiceNoeud] = -1 ET filsGauche[indiceNoeud] = -1 ALORS
        codes[indiceNoeud] <- codeCourant // Stocker le code pour ce nœud
        RETOURNER

    FIN SI

    // Appel récursif pour le fils gauche (si il existe)
    SI fils_gauche[indiceNoeud] != -1 ALORS
        genererCodes(fils_gauche[indiceNoeud], codeCourant + "0", fils_gauche, fils_droit, codes)
    FIN SI

    // Appel récursif pour le fils droit (si il existe)
    SI fils_droit[indiceNoeud] != -1 ALORS
        genererCodes(fils_droit[indiceNoeud], codeCourant + "1", fils_gauche, fils_droit, codes)
    FIN SI

Fin Fonction

// Fonction principale pour lancer la génération des codes
Fonction genererTousLesCodes(racine, enfantsGauche, enfantsDroit)
    codes <- nouveau dictionnaire vide // Pour stocker les codes (indice -> code binaire)
    genererCodes(racine, "", enfantsGauche, enfantsDroit, codes) // Appel initial avec la racine et un code vide
    retourner codes
Fin Fonction

Ecrire en c++ ce pseudo-code.

4. Effectuer la compression et la décompression, à l'aide des question précédentes, sur la matrice $3\times 3$ de la section précédente.
5. Ecrire une fonction qui calcule $\tau$ étant donnée une image.
6. Cette compression induit-elle une perte de l'information.

## 3. Compression par transformée en cos discrète
On considère dans cette section une compression d'image par une selection de certains éléments de la Transformée en Cosinus Discrète (DCT). Tout comme la transformée de Fourier Discrète, la DCT permet d'avoir une représentation fréquentielle de l'image.

1. Effectuer la DCT d'une image avec la fonction `cv::dct`.
:::warning
pour pouvoir appliquer la DCT à une image. On supposera que l'image d'origine est en niveau de gris et le type de chaque pixel est `CV_32F`.
:::
2. Calculer également la DCT inverse de la matrice obtenue dans la question précédente.
3. Utiliser le code ci-dessous pour visualiser la dct de l'image.

cv::Mat dct_display;
cv::log(cv::abs(dct_result) + 1, dct_display); 
cv::normalize(dct_display, dct_display, 0, 255, cv::NORM_MINMAX, CV_8U);

4. Ecrire une fonction `Mat extraitBlocImage(Mat img, int origine_x,int origine_y,int bloc_largeur,int bloc_longueur)` qui extrait la matrice bloc à partir du pixel `(origine_x,origine_y)` et de largeur `bloc_largeur` et longueur `bloc_longueur`. Utiliser un objet de type `Rect` avec l'opérateur `operator()`.
5. Extraire les composantes basses fréquences de la DCT dans une image `img_compresse_bf`
6. Appliquer la DCT inverse sur `img_compresse_bf` avec la fonction. Que constatez-vous.
7. En déduire une méthode permettant de compresser puis décompresser une image. Ecrire une fonction qui compresse et décompresse l'image.
9. Cette technique est-elle sans perte?
10. Dans cette question, on cherche à appliquer la DCT sur chaque bloc $8 \times 8$ de l'image (pour une grande image). Découper l'image en bloc de $8 \times 8$.
11. Appliquer la DCT sur chaque bloc.
12. Pour chaque bloc DCT, parcourir le bloc en zigzag et ne sélectionner que les premiers éléments de chaque bloc.
13. Effectuer les étapes de décompression pour chaque sous-ensemble de bloc.
14. Calculer le scalaire $\tau$ de votre méthode.

## 4. Filtrage et séparabilité

On considère la séparabilité des filtres 2D et notamment leurs performances.
1. Utiliser `cv::imread()` pour charger une image de taille assez grande (`ville` par exemple). Convertir l'image en niveaux de gris avec `cv::cvtColor()`.
2. Utiliser `cv::getGaussianKernel()` pour générer deux vecteurs gaussiens 1D (horizontal et vertical) et les multiplier pour obtenir le masque de convolution 2D.
3. Effectuer la convolution 2D de l'image avec le noyau gaussien 2D généré dans la question précédent. Utiliser `cv::filter2D()`. Mesurer le temps d'exécution avec `cv::getTickCount()`, par exemple

double t = (double)getTickCount();
instructions à chronometrer
t = ((double)getTickCount() - t) / getTickFrequency();
cout << "Temps d un bloc d'instructions tres interessant : " << t << " secondes" << endl;

4. Appliquer le filtrage séparable en effectuant deux convolutions 1D avec `cv::sepFilter2D()`. Mesurer le temps d'exécution et comparer avec la question précédente.
5. Commenter.
6. Afficher l'image originale, l'image filtrée avec la convolution 2D et l'image filtrée avec la convolution séparable.