From: Stéphane Domas <sdomas@prodigy.iut-bm.univ-fcomte.fr>
Date: Fri, 14 Oct 2011 13:34:05 +0000 (+0200)
Subject: premier commit :
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/dmems12.git/commitdiff_plain/378804e7fc26018b70fc8beafbb03b16a0e536f2?ds=inline

premier commit :

- canevas de base du document
- début de la rédaction de la partie algos
---

diff --git a/dmems12.tex b/dmems12.tex
index 4a6bd69..806e509 100644
--- a/dmems12.tex
+++ b/dmems12.tex
@@ -1,12 +1,258 @@
-\documentclass{article}
+\documentclass[12pt]{article}
+%\usepackage{latex8}
+%\usepackage{times}
+\usepackage[latin1]{inputenc}
+%\usepackage{pstricks,pst-node,pst-text,pst-3d}
+%\usepackage{babel}
+\usepackage{amsmath}
+\usepackage{url}
+\usepackage{graphicx}
+\usepackage{thumbpdf}
+\usepackage{color}
+\usepackage{moreverb}
+\usepackage{commath}
+\usepackage{subfigure}
+%\input{psfig.sty}
+\usepackage{fullpage}
+\usepackage{fancybox}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
+\newcommand{\noun}[1]{\textsc{#1}}
+
+\newcommand{\tab}{\ \ \ }
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%% my bib path.
+
+
+\title{Using FPGAs for high speed and real time cantilever deflection estimation}
+
+\author{ Raphaël COUTURIER\\
+Laboratoire d'Informatique 
+de l'Universit\'e de  Franche-Comt\'e, \\
+BP 527, \\
+90016~Belfort CEDEX, France\\
+ \and Stéphane Domas\\
+Laboratoire d'Informatique 
+de l'Universit\'e de  Franche-Comt\'e, \\
+BP 527, \\
+90016~Belfort CEDEX, France\\
+ \and Gwenhaël Goavec\\
+??
+?? \\
+??, \\
+??\\}
+
+
 \begin{document}
-\abstract {
-In this paper we describe....
-}
 
+\maketitle
+
+\thispagestyle{empty}
+
+\begin{abstract}
+
+  
+
+{\it keywords}: FPGA, cantilever, interferometry.
+\end{abstract}
 
 \section{Introduction}
 
-\section{Conclusion}
+%% blabla +
+%% quelques ref commentées sur les calculs basés sur l'interférométrie
+
+\section{Measurement architecture}
+\label{sec:measure-archi}
+
+%% description de l'architecture générale de l'acquisition d'images
+%% avec au milieu une unité de traitement dont on ne précise pas ce
+%% qu'elle est.
+
+%% image tirée des expériences.
+
+\section{Design goals}
+\label{sec:goals}
+
+%% objectifs en terme de rapidité et de précision, avec en vue l'ajout
+%% du contrôle => l'unité de traitement qui s'impose est un FPGA =>
+%% algo adapté au FPGA.
+
+%% peut etre que cette section peut être déplacée en intro ... à voir.
+
+\section{Proposed solution}
+\label{sec:solus}
+
+\subsection{Cantilever deflection estimation}
+
+%% => faire de l'interpolation de signal sinusoidal
+%% descriptif rapide des deux méthodes : splines et moindres carrés
+As shown on image \ref{img:img-xp}, each cantilever is covered by
+interferometric fringes. The fringes will distort when cantilevers are
+deflected. Estimating the deflection is done by computing this
+distortion. For that, (ref A. Meister + M Favre) proposed a method
+based on computing the phase of the fringes, at the base of each
+cantilever, near the tip, and on the base of the array. They assume
+that a linear relation binds these phases, which can be use to
+"unwrap" the phase at the tip and to determine the deflection.\\
+
+More precisely, segment of pixels are extracted from images taken by a
+high-speed camera. These segments are large enough to cover several
+interferometric fringes and are placed at the base and near the tip of
+the cantilevers. They are called base profile and tip profile in the
+following. Furthermore, a reference profile is taken on the base of
+the cantilever array.
+
+The pixels intensity $I$ (in gray level) of each profile is modelized by :
+
+\begin{equation}
+\label{equ:profile}
+I(x) = ax+b+A.cos(2\pi f.x + \theta)
+\end{equation}
+
+where $x$ is the position of a pixel in its associated segment.
+
+The global method consists in two main sequences. The first one aims
+to determin the frequency $f$ of each profile with an algorithm based
+on spline interpolation (see below). It also computes the coefficient
+used for unwrapping the phase. The second one is the acquisition loop,
+while which images are taken at regular time steps. For each image,
+the phase $\theta$ of all profiles is computed to obtain, after
+unwrapping, the deflection of cantilevers.
+
+This phase computation is obviously the bottle-neck of the whole
+process. For example, if we consider the camera actually in use, an
+exposition time of 2.5ms for $1024\times 1204$ pixels seems the
+minimum that can be reached. For a $10\times 10$ cantilever array, if
+we neglect the time to extract pixels, it implies that computing the
+deflection of a single cantilever should take less than 25$µ$s, which is
+quite small.
+
+\subsection{Considered algorithms}
+
+Two solutions have been studied to achieve phase computation. The
+original one, proposed by A. Meister and M. Favre, is based on
+interpolation by splines. It allows to compute frequency and
+phase. The second one, detailed in this article, is based on a
+classical least square method but suppose that frequency is already
+known.
+
+\subsubsection{Spline algorithm}
+
+Let consider a profile $P$, that is a segment of $M$ pixels with an
+intensity in gray levels. Let call $I(x)$ the intensity of profile in $x
+\in [0,M[$. 
+
+At first, only $M$ values of $I$ are known, for $x = 0, 1,
+\ldots,M-1$. A normalisation allows to scale known intensities into
+$[-1,1]$. We compute splines that fit at best these normalised
+intensities. Splines are used to interpolate $N = k\times M$ points
+(typically $k=3$ is sufficient), within $[0,M[$. Let call $x^s$ the
+coordinates of these $N$ points and $I^s$ their intensities.
+
+In order to have the frequency, the mean line $a.x+b$ (see equation \ref{equ:profile}) of $I^s$ is
+computed. Finding intersections of $I^s$ and this line allow to obtain
+the period thus the frequency.
+
+The phase is computed via the equation :
+\begin{equation}
+\theta = atan \left[ \frac{\sum_{i=0}^{N-1} sin(2\pi f x^s_i) \times I^s(x^s_i)}{\sum_{i=0}^{N-1} cos(2\pi f x^s_i) \times I^s(x^s_i)} \right]
+\end{equation}
+
+Two things can be noticed. Firstly, the frequency could also be
+obtained using the derivates of spline equations, which only implies
+to solve quadratic equations. Secondly, frequency of each profile is
+computed a single time, before the acquisition loop. Thus, $sin(2\pi f
+x^s_i)$ and $cos(2\pi f x^s_i)$ could also be computed before the loop, which leads to a
+much faster computation of $\theta$.
+
+\subsubsection{Least square algorithm}
+
+Assuming that we compute the phase during the acquisition loop,
+equation \ref{equ:profile} has only 4 parameters :$a, b, A$, and
+$\theta$, $f$ and $x$ being already known. Since $I$ is non-linear, a
+least square method based an Gauss-newton algorithm must be used to
+determine these four parameters. Since it is an iterative process
+ending with a convergence criterion, it is obvious that it is not
+particularly adapted to our design goals.
+
+Fortunatly, it is quite simple to reduce the number of parameters to
+only $\theta$. Let $x^p$ be the coordinates of pixels in a segment of
+size $M$. Thus, $x^p = 0, 1, \ldots, M-1$. Let $I(x^p)$ be their
+intensity. Firstly, we "remove" the slope by computing :
+
+\[I^{corr}(x^p) = I(x^p) - a.x^p - b\]
+
+Since linear equation coefficients are searched, a classical least
+square method can be used to determine $a$ and $b$ :
+
+\[a = \frac{covar(x^p,I(x^p))}{var(x^p)} \]
+
+Assuming an overlined symbol means an average, then :
+
+\[b = \overline{I(x^p)} - a.\overline{{x^p}}\]
+
+Let $A$ be the amplitude of $I^{corr}$, i.e. 
+
+\[A = \frac{max(I^{corr}) - min(I^{corr})}{2}\]
+
+Then, the least square method to find $\theta$ is reduced to search the minimum of :
+
+\[\sum_{i=0}^{M-1} \left[ cos(2\pi f.i + \theta) - \frac{I^{corr}(i)}{A} \right]^2\]
+
+It is equivalent to derivate this expression and to solve the following equation :
+
+\begin{eqnarray*}
+2\left[ cos\theta \sum_{i=0}^{M-1} I^{corr}(i).sin(2\pi f.i) + sin\theta \sum_{i=0}^{M-1} I^{corr}(i).cos(2\pi f.i)\right] \\
+- A\left[ cos2\theta \sum_{i=0}^{M-1} sin(4\pi f.i) + sin2\theta \sum_{i=0}^{M-1} cos(4\pi f.i)\right]   = 0
+\end{eqnarray*}
+
+Several points can be noticed :
+\begin{itemize}
+\item As in the spline method, some parts of this equation can be
+  computed before the acquisition loop. It is the case of sums that do
+  not depend on $\theta$ :
+
+\[ \sum_{i=0}^{M-1} sin(4\pi f.i), \sum_{i=0}^{M-1} cos(4\pi f.i) \] 
+
+\item Lookup tables for $sin(2\pi f.i)$ and $cos(2\pi f.i)$ can also be
+computed.
+
+\item The simplest method to find the good $\theta$ is to discretize
+  $[-\pi,\pi]$ in $N$ steps, and to search which step leads to the
+  result closest to zero. By the way, three other lookup tables can
+  also be computed before the loop :
+
+\[ sin \theta, cos \theta, \left[ cos 2\theta \sum_{i=0}^{M-1} sin(4\pi f.i) + sin 2\theta \sum_{i=0}^{M-1} cos(4\pi f.i)\right] \]
+
+\item This search can be very fast using a dichotomous process in $log_2(N)$ 
+
+\end{itemize}
+
+\subsubsection{Comparison}
+
+\subsection{FPGA constraints}
+
+%% contraintes imposées par le FPGA : algo pipeline/parallele, pas d'op math complexe, ...
+
+\subsection{Least square algorithm}
+
+%% description précise
+%% avantage sur FPGA
+
+\subsection{VDHL design paradigms}
+
+\subsection{VDHL implementation}
+
+\section{Experimental results}
+\label{sec:results}
+
+
+
+
+\section{Conclusion and perspectives}
+
+
+\bibliographystyle{plain}
+\bibliography{biblio}
 
 \end{document}