165 lines
8.3 KiB
TeX
165 lines
8.3 KiB
TeX
\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}
|