Projet Quadtree - Compression d'Images

Un programme de compression d'images utilisant une structure de données Quadtree en C avec la bibliothèque graphique MLV.

📋 Description

Ce projet implémente un algorithme de compression d'images par approximation adaptative. L'algorithme subdivise récursivement les régions de l'image selon leur erreur de couleur moyenne, créant ainsi une représentation compressée efficace.

Principe de Fonctionnement

1. Calcul de la couleur moyenne : Pour chaque région, calcule la couleur moyenne (RGBA)
2. Calcul de l'erreur : Mesure la distance entre chaque pixel et la couleur moyenne
3. Subdivision adaptative : Les régions avec la plus grande erreur sont subdivisées en 4 quadrants
4. Optimisation par tas : Utilise un max-heap pour toujours traiter les zones les plus imprécises en priorité

Complexité Algorithmique

• Calcul de moyenne : O(n²) par métapixel
• Calcul d'erreur : O(n²) par métapixel (optimisé sans sqrt)
• Construction complète : O(n² × p × log k) où p = profondeur max, k = nombre de nœuds

🚀 Fonctionnalités

Niveau 1 : Construction du Quadtree

• ✅ Subdivision progressive avec visualisation en temps réel
• ✅ Optimisation par max-heap pour priorité sur les erreurs maximales

Niveau 2 : Sauvegarde

• ✅ Format QTN (QuadTree Noir et blanc) : Compression en niveaux de gris
• ✅ Format QTC (QuadTree Couleur) : Compression RGBA complète
• ✅ Formats binaires compacts et rapides à charger

Niveau 3 : Minimisation avec Perte

• ✅ Fusion des nœuds similaires (distance colorimétrique < seuil)
• ✅ Réduction supplémentaire de la taille mémoire
• ✅ Sauvegarde des versions minimisées
• ✅ Chargement d'images compressées

🏗️ Architecture

Structure MVC (Model-View-Controller)

projectV2/
├── include/
│   ├── config.h          # Constantes de configuration centralisées
│   ├── utils.h           # Fonctions utilitaires génériques
│   ├── quadtree.h        # Structure et logique du quadtree (Model)
│   ├── heap.h            # Structure de tas max pour optimisation
│   ├── view.h            # Interface graphique et affichage (View)
│   └── controller.h      # Logique de contrôle (Controller)
├── src/
│   ├── main.c            # Point d'entrée du programme
│   ├── quadtree.c        # Implémentation du quadtree
│   ├── heap.c            # Implémentation du max-heap
│   ├── view.c            # Rendu graphique MLV
│   ├── controller.c      # Gestion des événements utilisateur
│   └── utils.c           # Fonctions utilitaires (mémoire, couleurs)
├── img/
│   ├── input/            # Images sources
│   └── output/           # Fichiers compressés (.qtc, .qtn)
├── doc/                  # Documentation (Doxygen dans Raph_test)
└── Makefile

📦 Installation

Prérequis

• Compilateur GCC et outils de compilation

  sudo apt-get install build-essential

• Bibliothèque MLV (MultiMedia Library for Various purposes)

Installation de MLV sur Debian/Ubuntu

1. Installer les dépendances SDL:

   sudo apt-get install libsdl-gfx1.2-dev libsdl1.2-dev libsdl-mixer1.2-dev
   sudo apt-get install libsdl-ttf2.0-dev libglib2.0-dev libxml2-dev
   sudo apt-get install libsdl-image1.2-dev

2. Télécharger et installer MLV:

   Téléchargez les paquets depuis le site officiel MLV:

   • libmlv0_2.0.2-1_amd64.deb
   • libmlv0-dev_2.0.2-1_amd64.deb

   Puis installez:

   sudo dpkg -i libmlv0_2.0.2-1_amd64.deb libmlv0-dev_2.0.2-1_amd64.deb

   Note: Pour systèmes 32 bits, utilisez les paquets _i386.deb

Installation sur Fedora

sudo yum update
sudo rpm --import RPM-GPG-KEY-Boussicault
sudo yum install mlv-2.0.2-0.fc22.x86_64.rpm
sudo yum install mlv-devel-2.0.2-0.fc22.x86_64.rpm
sudo yum install mlv-static-2.0.2-0.fc22.x86_64.rpm

Installation depuis le code source

1. Installer les dépendances:

   # Outils de compilation
   sudo apt-get install gcc libtool make autoconf doxygen
   
   # Bibliothèques SDL
   sudo apt-get install libsdl1.2-dev libsdl-gfx1.2-dev libsdl-mixer1.2-dev
   sudo apt-get install libsdl-ttf2.0-dev libglib2.0-dev libxml2-dev

2. Télécharger et compiler MLV:

   # Télécharger mlv-2.0.2.tar.gz depuis le site officiel
   tar -xzf mlv-2.0.2.tar.gz
   cd mlv-2.0.2
   ./configure --prefix=/usr
   make
   sudo make install

Compilation

Méthode 1: Avec Make (recommandé)

cd projectV2
make

L'exécutable sera généré dans bin/quadtree.

Méthode 2: Avec GCC directement

Si vous préférez compiler manuellement avec gcc:

gcc -Wall `pkg-config --cflags MLV` \
    `pkg-config --libs-only-other --libs-only-L MLV` \
    src/*.c \
    `pkg-config --libs-only-l MLV` \
    -o bin/quadtree

Le Makefile fourni utilise automatiquement pkg-config pour détecter MLV.

🎮 Utilisation

Lancement

./bin/quadtree img/input/votre_image.jpg

Interface

L'interface graphique propose 7 boutons :

1. NIVEAU 1: Construct Quadtree - Construit et affiche le quadtree progressivement
2. NIVEAU 2: Save as QTN (BW) - Sauvegarde en noir et blanc
3. NIVEAU 2: Save as QTC (Color) - Sauvegarde en couleur
4. NIVEAU 3: Minimize Quadtree - Minimise l'arbre avec perte acceptable
5. NIVEAU 3: Save Minimized QTN (BW) - Sauvegarde la version minimisée N&B
6. NIVEAU 3: Save Minimized QTC (Color) - Sauvegarde la version minimisée couleur
7. NIVEAU 3: Load Image - Charge une image .qtc/.qtn ou une nouvelle image

Exemples

# Compresser une image
./bin/quadtree img/input/beach.jpg
# Cliquer "Construct Quadtree" puis "Save as QTC"

# Charger une image compressée
./bin/quadtree img/input/beach.jpg
# Cliquer "Load Image" et entrer: img/output/quadtree.qtc

✨ Améliorations Récentes (Décembre 2025)

Le projet a bénéficié d'une refonte majeure pour améliorer qualité, performance et maintenabilité :

Nouveaux Modules

• config.h : Configuration centralisée (taille image, capacités heap, seuils)
• utils.h/c :
  • Allocation mémoire sécurisée (safe_malloc, safe_realloc)
  • Fonctions d'extraction de couleur réutilisables
  • Validation de fichiers avant chargement

Optimisations de Performance

• ⚡ +15% de vitesse : Suppression de sqrt() dans calculate_error
  • Utilise la distance au carré (comparaison équivalente, calcul plus rapide)
• 🛡️ Robustesse : Toutes les allocations mémoire vérifiées

Qualité du Code

• 🧹 Code propre : -30 lignes de duplication supprimées
• 📏 Maintenabilité : 0 magic numbers (remplacés par constantes nommées)
• 🔒 Sécurité : Validation des fichiers avant chargement

Voir IMPROVEMENTS.md pour les détails complets.

🌿 Branches

• main : Branche principale (stable)
• PH_test : Développement avec architecture MVC (contributions PH et Raphael)
• Raph_test : PH_test + Documentation Doxygen par Raphael
• test-coderabbit : Tests d'intégration CodeRabbit

📚 Documentation

Documentation du Code

La branche Raph_test contient une documentation Doxygen complète :

git checkout Raph_test
cd projectV2/doc/html
firefox index.html  # Ouvrir la documentation

Fichiers de Documentation

• implementation_plan.md : Plan des améliorations
• walkthrough.md : Guide détaillé des modifications

🧪 Tests

Test de Compilation

cd projectV2
make clean && make

Test Fonctionnel

./bin/quadtree img/input/panda.jpeg
# Interface graphique doit s'ouvrir avec l'image et les boutons

Test de Performance

time ./bin/quadtree img/input/NorthernLights.jpg
# Mesurer le temps d'exécution

🔧 Configuration

Les paramètres principaux sont configurables dans projectV2/include/config.h :

#define DEFAULT_IMAGE_SIZE 512          // Taille de redimensionnement
#define DEFAULT_HEAP_CAPACITY 1024      // Capacité initiale du heap
#define MERGE_THRESHOLD 25.0            // Seuil de fusion (minimisation)
#define WINDOW_WIDTH 860                // Largeur de la fenêtre

📄 Licence

Projet universitaire - Utilisation libre pour l'apprentissage.

👥 Auteurs

• Raphael (Raphael2120) : Architecture MVC, développement principal, optimisations
• PH : Développement, contributions au code
• Améliorations récentes : Refactoring qualité, performance, documentation (Décembre 2025)

🐛 Problèmes Connus

• La bibliothèque MLV est nécessaire pour la compilation
• Les images sont automatiquement redimensionnées à 512×512
• Le format de sauvegarde est propriétaire (.qtc/.qtn)

🚧 Évolutions Futures

• Support d'images de tailles variables
• Interface de sélection de fichiers graphique
• Unification complète des fonctions save/load (paramètre format)
• Support multi-threading pour subdivision parallèle
• Export vers formats standard (PNG, JPG)
• Interface web avec WebAssembly

---

Pour plus d'informations, consultez le code source commenté ou la documentation Doxygen.