\documentclass{article}

\renewcommand{\familydefault}{\sfdefault} % police en "sans-serif"

\usepackage[T1]{fontenc} % encodage
\usepackage[french]{babel} % langue
\usepackage[hidelinks]{hyperref} % liens cliquable dans la table des matières
\usepackage{geometry} % change les dimensions de la page
\usepackage{graphicx} % images
\usepackage{subcaption} % images côtes à côtes

\geometry{ % définition taille pages
    a4paper,
    left=20mm,
    top=20mm
}

\usepackage{minted} % intégration code
\usemintedstyle{emacs}

\title{Compression d’images avec quadtrees}
\author{\href{mailto:anri.kennel@etud.univ-paris8.fr}{Anri Kennel}\thanks{Numéro d'étudiant : 20010664}\, (L2-X)\\Algorithmique et structures de données 2 $\cdot$ Université Paris 8}
\date{Année universitaire 2021-2022}

\begin{document}
    \maketitle
    \tableofcontents
    \clearpage

    \section[Présentation]{Brève présentation}
    J'ai réalisé le projet seul. Mon projet est de compresser une image avec une structure \textit{quadtree}.

    \begin{figure}[!ht]
        \centering
        \begin{subfigure}{.49\textwidth}
            \href{https://pxhere.com/en/photo/1409995}{\includegraphics[height=0.2\textheight]{images/not-compressed.png}}
            \caption{Non compressé (3.6Mo)}
        \end{subfigure}
        \begin{subfigure}{.49\textwidth}
            \centering
            \includegraphics[height=0.2\textheight]{images/compressed-7.png}
            \caption{Compressé / 7 (56ko)}
        \end{subfigure}
    \end{figure}

    \subsection{Objectifs}
    \begin{itemize}
        \item Compiler facilement le programme
        \item Réussir à compresser l'image
        \item Code clair et commenté
        \item Ne pas utiliser OpenCV
    \end{itemize}

    \section[Explications]{Explications de la réalisation}
    \subsection*{Makefile}
    La compilation est simple avec le \texttt{Makefile}. Il est possible de faire \texttt{make} pour compiler avec la SDL et \texttt{O3}. Il est aussi possible de faire \texttt{make dev} et ainsi compiler avec la SDL et les flags de développement :
    \begin{itemize}
        \item \texttt{Wall} et \texttt{Wextra} pour les warnings
        \item \texttt{Wshadow} pour le nom des variables
        \item \texttt{pedantic} pour la compilation
        \item \texttt{g} pour Valgrind
        \item \texttt{Wold-style-cast} et \texttt{Wsign-conversion} pour bien utiliser les casts
    \end{itemize}

    \subsection*{Libraries}
    J'ai utilisé les librairies
    \begin{itemize}
        \item \texttt{fstream} pour vérifier empêcher d'écraser une image existante
        \item \texttt{SDL\_image} pour utiliser \texttt{SDL\_Surface} de la \texttt{SDL}
        \item \texttt{array} pour stocker et donner aux méthodes les 4 morceaux qui compose l'image quand divisé
    \end{itemize}

    \subsection*{Classe}
    Ma classe \texttt{QuadTree} est déclarée dans \texttt{includes/quadtree.hpp} et définie
    dans \texttt{src/quadtree.cpp}, elle contient :
    \begin{itemize}
        \item Une variable qui stocke la qualité de l'image (\texttt{niveau})
        \item Une variable qui stocke la couleur majoritaire dans l'image (\texttt{couleur})
        \item Une variable \texttt{std::pair} qui stocke les dimensions de l'image (\texttt{dimensions})
        \item 4 variables représentant les enfants du noeud (\texttt{nord\_ouest}, \texttt{nord\_est}, \texttt{sud\_ouest}, \texttt{sud\_est})
        \item Une variable qui définie si le noeud est final ou non (\texttt{final})
        \item Une variable qui stocke le format utilisé par l'image (\texttt{format})
        \newpage
        \item Une méthode qui permet de calculer la couleur majoraitaire dans l'image (\texttt{calculeCouleur})
        \item Une méthode qui permet savoir lors de l'exportation si elle est finie (\texttt{verificationEgalitee})
        \item Une méthode qui permet de séparer en 4 l'image (\texttt{coupeEnQuatre})
        \item Une méthode qui permet de rassembler 4 morceaux d'image en une seule (\texttt{colleQuatreImages})
        \item Une méthode qui permet d'exporter la surface avec un certain niveau de compression (\texttt{image})
    \end{itemize}
    \vspace{10pt}

    Cette classe permet de diviser récursivement l'image en 4 parts
    et d'en extraire la couleur qui y est majoritaire dans chaque morceaux d'image.

    \subsubsection*{Constructeur}
    Dans le constructeur de ma classe, j'initialise \texttt{format} à \texttt{SDL\_PIXELFORMAT\_RGB888}
    au lieu du format de mon image (\texttt{image->format}) car il y a un \textit{bug} dans
    la méthode \texttt{colleQuatreImages} qui préserve mal les couleurs. \texttt{SDL\_PIXELFORMAT\_RGB888} rend donc l'image en noir et blanc.

    \subsubsection*{Surfaces}
    Je \href{https://wiki.libsdl.org/SDL_LockSurface}{verrouille et déverrouille ma surface} à chaque utilisation même si c'est probablement inutile mais ça m'évite de vérifier si \texttt{SDL\_MUSTLOCK} est égale à 0 à chaque fois.
    \begin{center}\begin{minipage}{0.5\textwidth}
        \begin{minted}[linenos]{cpp}
if(SDL_LockSurface(surface) == 0) {
    /* ... */

    SDL_UnlockSurface(surface);
}
        \end{minted}
    \end{minipage}\end{center}

    \subsubsection*{Format des surfaces}
    Toutes les surfaces que je crées ont le même format, ça m'évite d'utiliser les masks \href{https://wiki.libsdl.org/SDL_CreateRGBSurface#code_examples}{en fonction de} l'endian.

    \subsubsection*{\texttt{calculeCouleur}}
    Pour calculer la couleur dans \texttt{calculeCouleur} je fait une moyenne \texttt{RGBA} de tout les pixels de la surface.

    \subsubsection*{\texttt{verificationEgalitee}}
    Dans \texttt{verificationEgalitee} je regarde si tout les pixels \texttt{RGB} de la surface sont identiques (j'ignore le canal alpha).

    \subsubsection*{\texttt{coupeEnQuatre}}
    Quand je coupe en quatre mon image dans \texttt{coupeEnQuatre}, je commence par définir les coordonnées de mes 4 morceaux (ici \texttt{s} est la surface mère) :
    \begin{center}\begin{minipage}{0.7\textwidth}
        \begin{minted}[linenos]{cpp}
std::array<std::array<int, 4>, 4> coordonnes_quadrants;
coordonnes_quadrants[0] = {0       , 0       , s->w / 2, s->h / 2};
coordonnes_quadrants[1] = {0       , s->h / 2, s->w / 2, s->h    };
coordonnes_quadrants[2] = {s->w / 2, 0       , s->w    , s->h / 2};
coordonnes_quadrants[3] = {s->w / 2, s->h / 2, s->w    , s->h    };
        \end{minted}
    \end{minipage}\end{center}
    Puis je créer tour à tour mes 4 surfaces qui je rajoute dans une \texttt{std::array}. Dans ses surfaces je vais
    recopier pixel-par-pixel de la grande surface vers la plus petite (ici \texttt{x}/\texttt{y} varient respectivement en fonction de la largeur/longueur du morceau d'image):
    \begin{center}\begin{minipage}{1\textwidth}
        \begin{minted}[linenos]{cpp}
int x1 = x * nouvelle_image->format->BytesPerPixel,
    y1 = y * nouvelle_image->pitch,
    x2 = (coordonnes_quadrants[i][0] + x) * s->format->BytesPerPixel,
    y2 = (coordonnes_quadrants[i][1] + y) * s->pitch;
*reinterpret_cast<Uint32 *>(static_cast<Uint8 *>(nouvelle_image->pixels) + y1 + x1) =
*reinterpret_cast<Uint32 *>(static_cast<Uint8 *>(s->pixels) + y2 + x2);
        \end{minted}
    \end{minipage}\end{center}

    \subsubsection*{\texttt{colleQuatreImages}}
    Quand je rassemble mon image dans \texttt{colleQuatreImages}, je commence par récupérer les dimensions de
    mon image originale en regardant des morceaux en diagonale (sur l'image je compare soit 1 et 4, soit 2 et 3).
    \begin{figure}[!ht]
        \centering
        \includegraphics[height=0.2\textheight]{images/image_coupe_en_4.png}
    \end{figure}
    \\Si les dimensions des 2 morceaux sont différents alors je prend la plus grande dimensions \texttt{- 1}.

    Une fois les dimensions récupérer, je copie pixel-par-pixel les morceaux sur ma grande surface, comme dans la méthode \texttt{coupeEnQuatre}. Je libère les morceaux de la mémoire une fois rassemblé.

    \section{Ajouts}
    \begin{itemize}
        \item Possibilité de préciser le niveau de compresser (0 très compressé et 10 pas compressé)
        \item Utilisation de la SDL pour gérer l'image
    \end{itemize}

    \subsection{Piste d'amélioration}
    Je n'ai malheureusement pas réussi à garder la couleur lorsque je compresse l'image, j'aimerais réussir à rendre ça fonctionnelle.

\end{document}