%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{graphics}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
%% Special footnote code from the package 'stblftnt.sty'
%% Author: Robin Fairbairns -- Last revised Dec 13 1996
\let\SF@@footnote\footnote
\def\footnote{\ifx\protect\@typeset@protect
    \expandafter\SF@@footnote
  \else
    \expandafter\SF@gobble@opt
  \fi
}
\expandafter\def\csname SF@gobble@opt \endcsname{\@ifnextchar[%]
  \SF@gobble@twobracket
  \@gobble
}
\edef\SF@gobble@opt{\noexpand\protect
  \expandafter\noexpand\csname SF@gobble@opt \endcsname}
\def\SF@gobble@twobracket[#1]#2{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage[latin1]{inputenc}
%\textheight26cm
%\textwidth15.5cm
%\hoffset-2cm
%\voffset-3cm

%chargement des drivers Subfigures
% \usepackage{french}
% \usepackage{subfigure}
%chargement des drivers EPIC et EEPIC
\usepackage{amsfonts}
\usepackage{fullpage}
\sloppy

% Chargement des drivers Postscript
\input{psfig}

%%%%%%%%%%%%%%%
\makeatother

\begin{document}


\title{\textbf{\huge TTI :TP}{\huge }\\
 {\huge }\textbf{\huge Transformée de Fourier discrète} }


\author{\textbf{2 séances}}

\maketitle

\section{Données}


\subsection{Données image}

On utilisera des images de niveaux de gris compris entre 0 et 255 au format
pgm. \\
 Les procédures d'entrée-sortie devront etre effectuees \underbar{}a l'aide
de Vamp.


\subsection{Données FFT}

On dispose dans le répertoire de données d'un fichier module-fft.c contenant:

\begin{itemize}
\item deux procédures permettant de calculer la FFT 1D par entrelacement temporel
de signaux 1D complexes.

\begin{itemize}
\item -- La première de ces procédures appelée bit \underbar{}reverse, effectue la
permutation des données en entrée de l'algorithme afin que les données de sorties
soient correctement ordonnées.
\item -- La deuxième procédure calcule la transformée de Fourier d'un signal complexe
x+iy . La partie réelle de la FFT est rendue dans x et la partie imaginaire
dans y.
\end{itemize}
\item différentes procédures utiles lors des phases de test. Vous pourrez vous référer
au fichier module-fft.h pour un descriptif des différentes procédures disponibles.
\end{itemize}
\noindent \textbf{\large NB:} les coefficients de Fourier obtenus ne tiennent
pas compte du facteur \( \frac{1}{N} \). On obtient donc les coefficients X(u)
suivant:\\
\begin{equation}
X(u)=\sum _{k=0}^{N-1}x(k)e^{-j2\Pi \frac{uk}{N}}
\end{equation}



\section{Programmation}

L'ensemble des entêtes des procédures à écrire (sauf la procédure decal \underbar{}origine)
se trouve dans le fichier fft-a-prog.h. Vous devrez remplir le corps de ces
procédures dans le fichier fft-a-prog.c. A partir des deux procédures de calcul
de la FFT1D, nous allons implémenter un algorithme de FFT 2D:
\begin{equation}
F(u,v)=\frac{1}{N}\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}f(x,y)e^{-j2\Pi (\frac{ux+vy}{N})}
\end{equation}
 Voila les différentes procédures à réaliser:

\begin{enumerate}
\item une procédure calculant le module de la transformée (complexe).
\item une procédure de calcul de la FFT 1D inverse.
\item une procédure calculant la FFT 2D à partir de sa propriété de séparabilité:
on calcule dans un premier temps la transformation sur les lignes puis on applique
la transformation sur les colonnes de l'image complexe obtenue.
\item une procédure decal \underbar{}origine décalant l'origine de l'image du module
vous est fournie (l'image est calculée pour une fréquence comprise entre~ \( -\frac{N}{2} \)~et~\( \frac{N}{2} \),
ce qui revient à mettre l'origine au centre). Vous proposerez une autre procédure
utilisant une solution où l'image est modifiée avant FFT (l'entête ne vous est
pas fourni).
\item une procédure calculant la FFT 2D inverse.
\item une procédure qui crée une mire sinusoïdale 1D de taille N et d'équation
\[
I(j)=sin(\omega j)\]
 Vous donnerez \( \omega  \) en fonction de N et de n, où n est le nombre de
périodes. Vous la sauvegarderez dans un fichier nommé test1d.
\item une procédure qui crée un fichier ``mire-sinusoidale.pgm'' (cf fig \ref{mire})
contenant une mire sinusoïdale constante suivant l'axe des y. Pour cela, vous
pourrez partir de la procédure 1D déjà programmée.
\begin{figure}
\centerline{ \fbox{\resizebox*{4cm}
{!}{\includegraphics{mire.ps}} } }


\caption{mire sinusoidale, n=3}

\label{mire}
\end{figure}

\end{enumerate}
\noindent \textbf{\large Rappels:}{\large \par}

\begin{itemize}
\item séparabilité de TFD 2D:~\( F(u,v)=\frac{1}{N}\sum _{x=0}^{N-1}e^{-j2\Pi \frac{ux}{N}}\sum _{y=0}^{N-1}f(x,y)e^{-j2\Pi \frac{vy}{N}} \)\\
 \hspace*{2cm}avec~ \( \sum _{y=0}^{N-1}f(x,y)e^{-j2\Pi \frac{vy}{N}}=NF(x,v) \)
\item calcul de la TF inverse: \( TFD^{-1}(X)=(TFD(X^{*}))^{*} \)
\end{itemize}

\section{Applications}


\subsection{FFT 1D}

La procédure TEST1D vous permettra de réaliser les tests sur les signaux que
vous entrerez dans un fichier appelé test1d. Les résultats des différentes procédures
seront sauvés dans le fichier resul1d.

\begin{enumerate}
\item Soit l'exemple suivant: 1 1 1 1. Calculer à la main le résultat de la TF 1D
sur ce vecteur. Vérifier alors que vous obtenez la même chose avec votre procédure
de calcul de la FFT 1D.
\item Effectuer les mêmes opérations mais avec la mire sinusoïdale 1D.
\item Interpréter les résultats obtenus.
\end{enumerate}

\subsection{FFT 2D}

vous procéderez en deux étapes:

\begin{itemize}
\item test sur des petits fichiers: \\
 la procédure TEST2D vous permettra de réaliser les tests sur les signaux 2D
que vous entrerez dans un fichier appelé test2d. Les résultats des différentes
procédures seront sauvés dans le fichier resul2d.
\item test sur des images: \\
 On dispose de l'image croix.ppm et disque.ppm (64{*}64) dans le fichier de
données unix/tptti/tp2 ainsi que de l'image de la mire que vous aurez générée.
Vous effectuerez les différentes étapes suivantes:

\begin{enumerate}
\item lancer la procédure FFT \underbar{}IM sur ces trois images.
\item visualiser l'image du module de celles-ci (image``fft-im.pgm''): commenter
et expliquer vos résultats.
\item vérifier que l'on retrouve les images originales dans ``fft-im-inv.pgm''.
\item sur l'image de la croix: donner une méthode pour éliminer la barre verticale
(la tester si possible).
\end{enumerate}
\end{itemize}

\section{A rendre}

\begin{enumerate}
\item le listing du programme.
\item un commentaire de celui-ci.
\item une réponse aux questions posées dans le paragraphe applications.
\end{enumerate}
\end{document}