\documentclass[a4paper,11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[frenchb]{babel}
\usepackage{textcomp}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{slashbox}
\usepackage{mathrsfs}
\usepackage{hyperref}
\usepackage{tgheros}
\usepackage{fancyvrb}
%\renewcommand*\familydefault{\sfdefault} %% Only if the base font of the document is to be sans serif
\usepackage[T1]{fontenc}
\makeatletter
\def\thickhrulefill{\leavevmode \leaders \hrule height 1pt\hfill \kern \z@}
\renewcommand{\maketitle}{
\begin{titlepage}%
    \let\footnotesize\small
    \let\footnoterule\relax
    \parindent \z@
    \reset@font
    \vskip 10\p@
    \hbox{\mbox{%
        \hspace{4pt}%
        \fbox{\includegraphics[width=3em]{eisti.png}}%
        \hspace{4pt}
        }%
      \vrule depth 0.9\textheight%
      \mbox{\hspace{2em}}
      \vtop{% %%%%%%%%%%%%%%%%%%
        \vskip 40\p@
        \begin{flushleft}
          \Large \@author \par
        \end{flushleft}
        \vskip 80\p@
        \begin{flushleft}
          \huge \bfseries \@title \par
        \end{flushleft}
        \vskip 260\p@
        \begin{flushleft}
          \large \@date \par
        \end{flushleft}
        \vfil
        }}
\setcounter{page}{0}
  \end{titlepage}%
  \setcounter{page}{0}%
}
\makeatother
\author{Alves Vincent\\Jarret Guillaume\\Analyse Numérique - Groupe B10}
\title{Reconstruction d'Images par FFT et SVD}
\date{8/06/14}
\begin{document}
\maketitle

\newpage
\tableofcontents
\setcounter{page}{1}
\newpage
\section{Introduction}
L'objectif de ce TP d'Analyse Numérique est d'utiliser deux méthodes pour la reconstruction approchée des images. 
La transformée rapide de Fourier (FFT) et la décomposition en valeurs singulières (SVD). 

Nous avons implémenté ces deux méthodes sous Scilab et les avons testées sur l'image fournie $im34.txt$.
Nous allons d'abord vous présenter ces méthodes, puis notre implémentation et les résultats que nous en avons tiré.

\begin{center}
\includegraphics[scale=1]{orig.png}\\
\textit{Image originale.}
\end{center}
\newpage
\section{Présentation mathématique du problème}

\subsection{Méthode FFT}
Cette méthode consiste à compresser en enlevant certaines valeurs de la transformée de Fourier de l'image.

Soit notre image transformée en une matrice bidimensionelle $M$. Pour appliquer FFT, les étapes à suivre sont les suivantes.
\begin{itemize}
\item{} Convertir $M$ en une matrice monodimensionelle $T$.
\item{} Appliquer la transformée de Fourier à ce tableau.
\item{} Retirer la première valeur, usuellement trop élevée, et la seconde moitié du tableau obtenu, car elle peut être réobtenue par symétrie.
\item{} Appliquer notre compression en retirant un pourcentage des valeurs restantes, par exemple 70\%: On retirera les valeurs après 3/10 de la longueur de la matrice.
\item{} Appliquer une symétrie à la matrice restante pour obtenir une matrice monodimensionelle de taille égale à $T$.
\item{} Appliquer la transformée de Fourier inverse.
\item{} Reconvertir la matrice en une matrice bidimensionelle.
\end{itemize}

\subsection{Méthode SVD}
Cette méthode consiste à décomposer notre image en trois matrices $U,S,V$ de mêmes dimensions, avec les valeurs singulières de M sur sa diagonale, classées par ordre décroissant. $U$ et $V$ sont deux matrices représentant les vecteurs singuliers de M.

\begin{itemize}
\item{} Récupérer la diagonale de $S$ dans un tableau monodimensionnel.
\item{} La taille de ce tableau représente le nombre de valeurs singulières pour l'image étudiée
\item{} Conserver un pourcentage de valeurs singulières
\item{} Calculer $U*S*V'$ pour obtenir l'image reconstruite, $V'$ étant les valeurs singulières préservées.
\end{itemize}


\newpage
\section{Réalisation informatique}
Nous avons utilisé le programme Scilab pour réaliser les codes suivants.
\subsection{Fonction FFT}
\begin{verbatim}
//Passage en Matrice 1D. -1 = length(original)
go = matrix(img,1,-1);

//Application de Fourier
A=fft(go);

figure(4, "Figure_name", "FFT : Spectre Original");
clf(4);
plot(abs(A));


//On prend de 2 à 1/2 de la matrice(160000)
for (i=length(A)/2:length(A))
        A(i)=0;
end
A(1)=0;

figure(2, "Figure_name", "FFT : Spectre Tronqué");
clf(2);
plot(abs(A));

//---------Reconstitution de l'image via FFT inverse----------------


//On prend un pourcentage de fréquences (ici, 30%) pour la compression.
for (i=length(A)*(30/100):length(A))
        A(i)=0;
end

//A=A(2:length(A)*(30/100));

//Reconstruire un spectre complet par symétrie:
A_recons = zeros(1, 500*640); //Longeur complete
A_recons(1:length(A)) = A; //On remplit le début avec ce qui reste de A

A_recons((500*640-length(A)+2):(500*640)) = conj(A($:-1:2));
A_recons(1:length(A)/2) = A(1:length(A)/2); 
//symétrie.

figure(5, "Figure_name", "FFT : Spectre complet reconstruit");
clf(5);
plot(abs(A_recons));

B=ifft(A); //On applique la transformée inverse

B=abs(B);

temp = matrix(B,500,640); //500x640 Taille image originale
Result = uint8(255*temp);
figure(3, "Figure_name", "Image compressée");
clf(3);
ShowImage(Result,'Image compressée');

\end{verbatim}

\newpage

\subsection{Fonction SVD}
\begin{verbatim}

//Obtention de l'image originale
img = read('im34.txt',-1,640);
ap = uint8(255*img);
figure(1, "Figure_name", "Image originale");
clf(1);
ShowImage(ap,'Image originale');

//---------Application de la SVD-----------

[U, S, V] = svd(img);
S = diag(S); 
// On récupère les min(m, n) valeurs singulières (extraction valeurs diagonales de S)

        // Début : partie graphique
        figure(2, "Figure_name", "Valeurs Singulières");
        clf(2);
        x = 1:length(S);
        plot(x,S);
       
// Réduction à 30\% des valeurs
nb_val = length(S) * (5/100);
U = U(:, 1:nb_val);
S = S(1:nb_val);
V = V(:, 1:nb_val);
       
svdmat = [S,U',V'];
    
//----------SVD Inverse---------------
    
        // Extraction des matrices U, S, V
        S = diag(svdmat(:, 1));
        U = svdmat(:, 2:501)'; //Commencer à 2 <=> Ajouter 1 à la largeur
        V = svdmat(:, 502:size(svdmat,2));
        tab = U * S * V;
           
        Resultat = uint8(255*tab);
        figure(3, "Figure_name", "Image reconstruite à partir de SVD");
        clf(3);
        ShowImage(Resultat,'Image reconstruite à partir de SVD');

\end{verbatim}

\section{Résultats obtenus}

Avec un taux de compression de 70\%(30\% des valeurs conservées):

\begin{center}
\includegraphics[scale=0.5]{ananufft.jpg}\\
\textit{Transformation FFT appliquée.}
\end{center}

\begin{center}
\includegraphics[scale=0.5]{ananusvd2.jpg}\\
\textit{Transformation SVD appliquée.}
\end{center}

\newpage
Avec un taux de compression de 95\%(5\% des valeurs conservées):

\begin{center}
\includegraphics[scale=0.5]{ananufft2.jpg}\\
\textit{Transformation FFT appliquée.}
\end{center}

\begin{center}
\includegraphics[scale=0.5]{ananuSVD.jpg}\\
\textit{Transformation SVD appliquée.}
\end{center}

Notre implémentation de FFT est fausse, au vu de l'image obtenue. Cependant, SVD semble bien fonctionner.
\newpage

\section{Conclusion générale}
Malgré les erreurs de notre implémentation, nous pouvons voir que SVD est une méthode de compression correcte jusqu'à un certain pourcentage. Cependant, les valeurs singulières supprimées apportent une erreur numérique visible par l'apparition de points blancs ou noirs sur toutes les valeurs saturées de l'images(blancs/noirs quasi-parfaits).

Passé un certain pourcentage(20\% de valeurs gardées), on observe un phénomène de pixélisation de l'image. On ne peut donc pas pousser l'algorithme trop loin si l'on désire conserver la qualité générale de l'image.

\section{Reférences}
\noindent
Support de cours Scilab, Cycle ingénieur, EISTI Première année.\\

\section{Annexe - Guide d'utilisation du programme}
\begin{itemize}
\item{}Dans Scilab, sélectionner \textbf{Fichier $\rightarrow$ Changer le répertoire courant}
\item{}Sélectionner le répertoire dans lequel ont été extraits les fichiers Fourier.sce et ValSingu.sce, ainsi que le fichier im34.txt (que nous ne pouvons fournir à cause des restrictions de Sifoci...)
\item{}Entrer dans Scilab \textbf{exec('Fourier.sce');} ou \textbf{exec('ValSingu.sce');}, selon la méthode désirée.
\item{}Scilab récupèrera l'image, éxecutera l'algorithme et affichera le résultat.
\end{itemize}

\end{document} 