]> AND Private Git Repository - dmems12.git/blobdiff - dmems12.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ispell
[dmems12.git] / dmems12.tex
index 806e5098f69359b8b9436f61f3f5cf542ffccab1..1dd3b4a2de6c5480ecc61bfad98723515cbf48d5 100644 (file)
@@ -1,7 +1,9 @@
-\documentclass[12pt]{article}
+
+\documentclass[10pt, peerreview, compsocconf]{IEEEtran}
 %\usepackage{latex8}
 %\usepackage{times}
-\usepackage[latin1]{inputenc}
+\usepackage[utf8]{inputenc}
+%\usepackage[cyr]{aeguill}
 %\usepackage{pstricks,pst-node,pst-text,pst-3d}
 %\usepackage{babel}
 \usepackage{amsmath}
 \usepackage{fullpage}
 \usepackage{fancybox}
 
+\usepackage[ruled,lined,linesnumbered]{algorithm2e}
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
 \newcommand{\noun}[1]{\textsc{#1}}
 
 \newcommand{\tab}{\ \ \ }
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%% my bib path.
+
+\begin{document}
 
 
-\title{Using FPGAs for high speed and real time cantilever deflection estimation}
+%% \author{\IEEEauthorblockN{Authors Name/s per 1st Affiliation (Author)}
+%% \IEEEauthorblockA{line 1 (of Affiliation): dept. name of organization\\
+%% line 2: name of organization, acronyms acceptable\\
+%% line 3: City, Country\\
+%% line 4: Email: name@xyz.com}
+%% \and
+%% \IEEEauthorblockN{Authors Name/s per 2nd Affiliation (Author)}
+%% \IEEEauthorblockA{line 1 (of Affiliation): dept. name of organization\\
+%% line 2: name of organization, acronyms acceptable\\
+%% line 3: City, Country\\
+%% line 4: Email: name@xyz.com}
+%% }
 
-\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}
+\title{A new approach based on least square methods to estimate in real time cantilevers deflection with a FPGA}
+\author{\IEEEauthorblockN{Raphaël Couturier\IEEEauthorrefmark{1}, Stéphane Domas\IEEEauthorrefmark{1}, Gwenhaël Goavec-Merou\IEEEauthorrefmark{2} and Michel Lenczner\IEEEauthorrefmark{2}}
+\IEEEauthorblockA{\IEEEauthorrefmark{1}FEMTO-ST, DISC, University of Franche-Comte, Belfort, France\\
+\{raphael.couturier,stephane.domas\}@univ-fcomte.fr}
+\IEEEauthorblockA{\IEEEauthorrefmark{2}FEMTO-ST, Time-Frequency, University of Franche-Comte, Besançon, France\\
+\{michel.lenczner@utbm.fr,gwenhael.goavec@trabucayre.com}
+}
+
 
-\maketitle
+
+
+
+
+%\maketitle
 
 \thispagestyle{empty}
 
 \begin{abstract}
 
-  
+  Atomic force microscope (AFM) provides high resolution images of
+  surfaces. We focus our attention on an interferometry method to
+  estimate the cantilevers deflection.  The initial method was based
+  on splines to determine the phase of interference fringes, and thus
+  the deflection. Computations were performed on a PC with LabView.
+  In this paper, we propose a new approach based on the least square
+  methods and its implementation that we developed on a FPGA, using
+  the pipelining technique. Simulations and real tests showed us that
+  this implementation is very efficient and should allow us to control
+  a cantilevers array in real time.
+
 
-{\it keywords}: FPGA, cantilever, interferometry.
 \end{abstract}
 
+\begin{IEEEkeywords}
+FPGA, cantilever, interferometry.
+\end{IEEEkeywords}
+
+
+\IEEEpeerreviewmaketitle
+
 \section{Introduction}
 
-%% blabla +
+Cantilevers  are  used  inside  atomic  force  microscope (AFM) which  provides  high
+resolution images of  surfaces.  Several techniques have been  used to measure the
+displacement  of cantilevers  in literature.   For example,  it is  possible to
+determine  accurately  the  deflection  with different  mechanisms. 
+In~\cite{CantiPiezzo01},   authors  used   piezoresistor  integrated   into  the
+cantilever.   Nevertheless this  approach  suffers from  the  complexity of  the
+microfabrication  process needed  to  implement the  sensor  in the  cantilever.
+In~\cite{CantiCapacitive03},  authors  have  presented an  cantilever  mechanism
+based on  capacitive sensing. This kind  of technique also  involves to instrument
+the cantilever which result in a complex fabrication process.
+
+In this  paper our attention is focused  on a method based  on interferometry to
+measure cantilevers' displacements.  In  this method cantilevers are illuminated
+by  an optic  source. The  interferometry produces  fringes on  each cantilever
+which enables to  compute the cantilever displacement.  In  order to analyze the
+fringes a  high speed camera  is used. Images  need to be processed  quickly and
+then  a estimation  method is  required to  determine the  displacement  of each
+cantilever.  In~\cite{AFMCSEM11},  authors have  used an algorithm  based on
+spline to estimate the cantilevers' positions.
+
+The overall process gives accurate results but all the computations
+are performed on a standard computer using LabView.  Consequently, the
+main drawback of this implementation is that the computer is a
+bottleneck. In this paper we propose to use a method based on least
+square and to implement all the computation on a FPGA.
+
+The remainder  of the paper  is organized as  follows. Section~\ref{sec:measure}
+describes  more precisely  the measurement  process. Our  solution based  on the
+least  square   method  and   the  implementation  on   FPGA  is   presented  in
+Section~\ref{sec:solus}.       Experimentations      are       described      in
+Section~\ref{sec:results}.  Finally  a  conclusion  and  some  perspectives  are
+presented.
+
+
+
 %% quelques ref commentées sur les calculs basés sur l'interférométrie
 
-\section{Measurement architecture}
-\label{sec:measure-archi}
+\section{Measurement principles}
+\label{sec:measure}
 
+\subsection{Architecture}
+\label{sec: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.
+In order to develop simple,  cost effective and user-friendly cantilever arrays,
+authors   of    ~\cite{AFMCSEM11}   have   developed   a    system   based   of
+interferometry. In opposition to other optical based systems, using a laser beam
+deflection scheme and  sensitive to the angular displacement  of the cantilever,
+interferometry  is sensitive  to  the  optical path  difference  induced by  the
+vertical displacement of the cantilever.
+
+The system build by these authors is based on a Linnick
+interferometer~\cite{Sinclair:05}.  It is illustrated in
+Figure~\ref{fig:AFM}.  A laser diode is first split (by the splitter)
+into a reference beam and a sample beam that reaches the cantilever
+array.  In order to be able to move the cantilever array, it is
+mounted on a translation and rotational hexapod stage with five
+degrees of freedom. The optical system is also fixed to the stage.
+Thus, the cantilever array is centered in the optical system which can
+be adjusted accurately.  The beam illuminates the array by a
+microscope objective and the light reflects on the cantilevers.
+Likewise the reference beam reflects on a movable mirror.  A CMOS
+camera chip records the reference and sample beams which are
+recombined in the beam splitter and the interferogram.  At the
+beginning of each experiment, the movable mirror is fitted manually in
+order to align the interferometric fringes approximately parallel to
+the cantilevers.  When cantilevers move due to the surface, the
+bending of cantilevers produce movements in the fringes that can be
+detected with the CMOS camera.  Finally the fringes need to be
+analyzed. In~\cite{AFMCSEM11}, authors used a LabView program to
+compute the cantilevers' deflections from the fringes.
+
+\begin{figure}    
+\begin{center}
+\includegraphics[width=\columnwidth]{AFM}
+\end{center}
+\caption{schema of the AFM}
+\label{fig:AFM}   
+\end{figure}
 
-%% peut etre que cette section peut être déplacée en intro ... à voir.
 
-\section{Proposed solution}
-\label{sec:solus}
+%% image tirée des expériences.
 
 \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 :
+\label{sec:deflest}
+
+\begin{figure}    
+\begin{center}
+\includegraphics[width=\columnwidth]{lever-xp}
+\end{center}
+\caption{Portion of an image picked by the camera}
+\label{fig:img-xp}   
+\end{figure}
+
+As shown on image \ref{fig:img-xp}, each cantilever is covered by
+several interferometric fringes. The fringes will distort when
+cantilevers are deflected. Estimating the deflection is done by
+computing this distortion. For that, authors of \cite{AFMCSEM11}
+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
+the camera. These segments are large enough to cover several
+interferometric fringes. As said above, they 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}
@@ -112,20 +208,162 @@ I(x) = ax+b+A.cos(2\pi f.x + \theta)
 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.
+to determine the frequency $f$ of each profile with an algorithm based
+on spline interpolation (see section \ref{algo-spline}). 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. Originally, this computation was also done with an
+algorithm based on spline. This article proposes a new version based
+on a least square method.
+
+\subsection{Design goals}
+\label{sec:goals}
+
+The main goal is to implement a computing unit to estimate the
+deflection of about $10\times10$ cantilevers, faster than the stream of
+images coming from the camera. The accuracy of results must be close
+to the maximum precision ever obtained experimentally on the
+architecture, i.e. 0.3nm. Finally, the latency between an image
+entering in the unit and the deflections must be as small as possible
+(NB: future works plan to add some control on the cantilevers).\\
+
+If we put aside some hardware issues like the speed of the link
+between the camera and the computation unit, the time to deserialize
+pixels and to store them in memory, ... the 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
+100 cantilevers, if we neglect the time to extract pixels, it implies
+that computing the deflection of a single
+cantilever should take less than 25$\mu$s, thus 12.5$\mu$s by phase.\\
+
+In fact, this timing is a very hard constraint. Let consider a very
+small program that initializes twenty million of doubles in memory
+and then does 1000000 cumulated sums on 20 contiguous values
+(experimental profiles have about this size). On an intel Core 2 Duo
+E6650 at 2.33GHz, this program reaches an average of 155Mflops. 
+
+%%Itimplies that the phase computation algorithm should not take more than
+%%$155\times 12.5 = 1937$ floating operations. For integers, it gives $3000$ operations. 
+
+Obviously, some cache effects and optimizations on
+huge amount of computations can drastically increase these
+performances: peak efficiency is about 2.5Gflops for the considered
+CPU. But this is not the case for phase computation that used only few
+tenth of values.\\
+
+In order to evaluate the original algorithm, we translated it in C
+language. As said further, for 20 pixels, it does about 1550
+operations, thus an estimated execution time of $1550/155
+=$10$\mu$s. For a more realistic evaluation, we constructed a file of
+1Mo containing 200 profiles of 20 pixels, equally scattered. This file
+is equivalent to an image stored in a device file representing the
+camera. We obtained an average of 10.5$\mu$s by profile (including I/O
+accesses). It is under are requirements but close to the limit. In
+case of an occasional load of the system, it could be largely
+overtaken. A solution would be to use a real-time operating system but
+another one to search for a more efficient algorithm.
+
+But the main drawback is the latency of such a solution: since each
+profile must be treated one after another, the deflection of 100
+cantilevers takes about $200\times 10.5 = 2.1$ms, which is inadequate
+for an efficient control. An obvious solution is to parallelize the
+computations, for example on a GPU. Nevertheless, the cost to transfer
+profile in GPU memory and to take back results would be prohibitive
+compared to computation time. It is certainly more efficient to
+pipeline the computation. For example, supposing that 200 profiles of
+20 pixels can be pushed sequentially in the pipelined unit cadenced at
+a 100MHz (i.e. a pixel enters in the unit each 10ns), all profiles
+would be treated in $200\times 20\times 10.10^{-9} =$ 40$\mu$s plus
+the latency of the pipeline. This is about 500 times faster than
+actual results.\\
+
+For these reasons, an FPGA as the computation unit is the best choice
+to achieve the required performance. Nevertheless, passing from
+a C code to a pipelined version in VHDL is not obvious at all. As
+explained in the next section, it can even be impossible because of
+some hardware constraints specific to FPGAs.
+
+
+\section{Proposed solution}
+\label{sec:solus}
+
+Project Oscar aims  to provide a hardware and  software architecture to estimate
+and  control the  deflection of  cantilevers. The  hardware part  consists  in a
+high-speed camera,  linked on an embedded  board hosting FPGAs. By  the way, the
+camera output stream can be pushed  directly into the FPGA. The software part is
+mostly the VHDL  code that deserializes the camera  stream, extracts profile and
+computes  the deflection. Before  focusing on  our work  to implement  the phase
+computation, we give some general information about FPGAs and the board we use.
+
+\subsection{FPGAs}
+
+A field-programmable gate  array (FPGA) is an integrated  circuit designed to be
+configured by the customer. FGPAs are composed of programmable logic components,
+called  configurable logic blocks  (CLB). These  blocks mainly  contains look-up
+tables  (LUT), flip/flops (F/F)  and latches,  organized in  one or  more slices
+connected together. Each CLB can be configured to perform simple (AND, XOR, ...)
+or complex  combinational functions.  They are interconnected  by reconfigurable
+links.  Modern FPGAs  contain memory  elements and  multipliers which  enable to
+simplify the  design and  to increase the  performance. Nevertheless,  all other
+complex  operations, like  division, trigonometric  functions, $\ldots$  are not
+available  and  must  be  done  by   configuring  a  set  of  CLBs.  Since  this
+configuration  is not  obvious at  all, it  can be  done via  a  framework, like
+ISE~\cite{ISE}. Such  a software  can synthetize a  design written in  a hardware
+description language  (HDL), map it onto  CLBs, place/route them  for a specific
+FPGA, and finally  produce a bitstream that is used to  configure the FPGA. Thus,
+from  the developer  point of  view,  the main  difficulty is  to translate  an
+algorithm in HDL code, taking  account FPGA resources and constraints like clock
+signals and I/O values that drive the FPGA.
+
+Indeed, HDL programming is very different from classic languages like
+C. A program can be seen as a state-machine, manipulating signals that
+evolve from state to state. By the way, HDL instructions can execute
+concurrently. Basic logic operations are used to aggregate signals to
+produce new states and assign it to another signal. States are mainly
+expressed as arrays of bits. Fortunately, libraries propose some
+higher levels representations like signed integers, and arithmetic
+operations.
+
+Furthermore, even if FPGAs are cadenced more slowly than classic
+processors, they can perform pipeline as well as parallel
+operations. A pipeline consists in cutting a process in sequence of
+small tasks, taking the same execution time. It accepts a new data at
+each clock top, thus, after a known latency, it also provides a result
+at each clock top. However, using a pipeline consumes more logics
+since the components of a task are not reusable by another
+one. Nevertheless it is probably the most efficient technique on
+FPGA. Because of its architecture, it is also very easy to process
+several data concurrently. When it is possible, the best performance
+is reached using parallelism to handle simultaneously several
+pipelines in order to handle multiple data streams.
+
+\subsection{The board}
+
+The board we use is designed by the Armadeus company, under the name
+SP Vision. It consists in a development board hosting a i.MX27 ARM
+processor (from Freescale). The board includes all classical
+connectors: USB, Ethernet, ... A Flash memory contains a Linux kernel
+that can be launched after booting the board via u-Boot.
+
+The processor is directly connected to a Spartan3A FPGA (from Xilinx)
+via its special interface called WEIM. The Spartan3A is itself
+connected to a Spartan6 FPGA. Thus, it is possible to develop programs
+that communicate between i.MX and Spartan6, using Spartan3 as a
+tunnel. By default, the WEIM interface provides a clock signal at
+100MHz that is connected to dedicated FPGA pins.
+
+The Spartan6 is an LX100 version. It has 15822 slices, each slice
+containing 4 LUTs and 8 flip/flops. It is equivalent to 101261 logic
+cells. There are 268 internal block RAM of 18Kbits, and 180 dedicated
+multiply-adders (named DSP48), which is largely enough for our
+project.
+
+Some I/O pins of Spartan6 are connected to two $2\times 17$ headers
+that can be used as user wants. For the project, they will be
+connected to the interface card of the camera.
 
 \subsection{Considered algorithms}
 
@@ -136,58 +374,61 @@ 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}
-
+\subsubsection{Spline algorithm (SPL)}
+\label{sec:algo-spline}
 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
+\ldots,M-1$. A normalization allows to scale known intensities into
+$[-1,1]$. We compute splines that fit at best these normalized
 intensities. Splines are used to interpolate $N = k\times M$ points
-(typically $k=3$ is sufficient), within $[0,M[$. Let call $x^s$ the
+(typically $k=4$ 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 :
+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$.
+Two things can be noticed:
+\begin{itemize}
+\item the frequency could also be obtained using the derivates of
+  spline equations, which only implies to solve quadratic equations.
+\item 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$.
+\end{itemize}
 
-\subsubsection{Least square algorithm}
+\subsubsection{Least square algorithm (LSQ)}
 
 Assuming that we compute the phase during the acquisition loop,
-equation \ref{equ:profile} has only 4 parameters :$a, b, A$, and
+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
+least square method based on a Gauss-newton algorithm can 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
+Fortunately, 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 :
+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$ :
+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 :
+Assuming an overlined symbol means an average, then:
 
 \[b = \overline{I(x^p)} - a.\overline{{x^p}}\]
 
@@ -195,22 +436,22 @@ 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 :
+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 :
+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 :
+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$ :
+  not depend on $\theta$:
 
 \[ \sum_{i=0}^{M-1} sin(4\pi f.i), \sum_{i=0}^{M-1} cos(4\pi f.i) \] 
 
@@ -218,39 +459,337 @@ Several points can be noticed :
 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
+  $[-\pi,\pi]$ in $nb_s$ 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 :
+  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] \]
+\[ sin \theta, cos \theta, \]
 
-\item This search can be very fast using a dichotomous process in $log_2(N)$ 
+\[ \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] \]
 
-\end{itemize}
+\item This search can be very fast using a dichotomous process in $log_2(nb_s)$ 
 
-\subsubsection{Comparison}
+\end{itemize}
 
-\subsection{FPGA constraints}
+Finally, the whole summarizes in an algorithm (called LSQ in the following) in two parts, one before and one during the acquisition loop:
+\begin{algorithm}[htbp]
+\caption{LSQ algorithm - before acquisition loop.}
+\label{alg:lsq-before}
+
+   $M \leftarrow $ number of pixels of the profile\\
+   I[] $\leftarrow $ intensities of pixels\\
+   $f \leftarrow $ frequency of the profile\\
+   $s4i \leftarrow \sum_{i=0}^{M-1} sin(4\pi f.i)$\\
+   $c4i \leftarrow \sum_{i=0}^{M-1} cos(4\pi f.i)$\\
+   $nb_s \leftarrow $ number of discretization steps of $[-\pi,\pi]$\\
+
+   \For{$i=0$ to $nb_s $}{
+     $\theta  \leftarrow -\pi + 2\pi\times \frac{i}{nb_s}$\\
+     lut$_s$[$i$] $\leftarrow sin \theta$\\
+     lut$_c$[$i$] $\leftarrow cos \theta$\\
+     lut$_A$[$i$] $\leftarrow cos 2 \theta \times s4i + sin 2 \theta \times c4i$\\
+     lut$_{sfi}$[$i$] $\leftarrow sin (2\pi f.i)$\\
+     lut$_{cfi}$[$i$] $\leftarrow cos (2\pi f.i)$\\
+   }
+\end{algorithm}
+
+\begin{algorithm}[htbp]
+\caption{LSQ algorithm - during acquisition loop.}
+\label{alg:lsq-during}
+
+   $\bar{x} \leftarrow \frac{M-1}{2}$\\
+   $\bar{y} \leftarrow 0$, $x_{var} \leftarrow 0$, $xy_{covar} \leftarrow 0$\\
+   \For{$i=0$ to $M-1$}{
+     $\bar{y} \leftarrow \bar{y} + $ I[$i$]\\
+     $x_{var} \leftarrow x_{var} + (i-\bar{x})^2$\\
+   }
+   $\bar{y} \leftarrow \frac{\bar{y}}{M}$\\
+   \For{$i=0$ to $M-1$}{
+     $xy_{covar} \leftarrow xy_{covar} + (i-\bar{x}) \times (I[i]-\bar{y})$\\
+   }
+   $slope \leftarrow \frac{xy_{covar}}{x_{var}}$\\
+   $start \leftarrow y_{moy} - slope\times \bar{x}$\\
+   \For{$i=0$ to $M-1$}{
+     $I[i] \leftarrow I[i] - start - slope\times i$\\
+   }
+   
+   $I_{max} \leftarrow max_i(I[i])$, $I_{min} \leftarrow min_i(I[i])$\\
+   $amp \leftarrow \frac{I_{max}-I_{min}}{2}$\\
+
+   $Is \leftarrow 0$, $Ic \leftarrow 0$\\
+   \For{$i=0$ to $M-1$}{
+     $Is \leftarrow Is + I[i]\times $ lut$_{sfi}$[$i$]\\
+     $Ic \leftarrow Ic + I[i]\times $ lut$_{cfi}$[$i$]\\
+   }
+
+   $\delta \leftarrow \frac{nb_s}{2}$, $b_l \leftarrow 0$, $b_r \leftarrow \delta$\\
+   $v_l \leftarrow -2.I_s - amp.$lut$_A$[$b_l$]\\
+
+   \While{$\delta >= 1$}{
+
+     $v_r \leftarrow 2.[ Is.$lut$_c$[$b_r$]$ + Ic.$lut$_s$[$b_r$]$ ] - amp.$lut$_A$[$b_r$]\\
+
+     \If{$!(v_l < 0$ and $v_r >= 0)$}{
+       $v_l \leftarrow v_r$ \\
+       $b_l \leftarrow b_r$ \\
+     }
+     $\delta \leftarrow \frac{\delta}{2}$\\
+     $b_r \leftarrow b_l + \delta$\\
+   }
+   \uIf{$!(v_l < 0$ and $v_r >= 0)$}{
+     $v_l \leftarrow v_r$ \\
+     $b_l \leftarrow b_r$ \\
+     $b_r \leftarrow b_l + 1$\\
+     $v_r \leftarrow 2.[ Is.$lut$_c$[$b_r$]$ + Ic.$lut$_s$[$b_r$]$ ] - amp.$lut$_A$[$b_r$]\\
+   }
+   \Else {
+     $b_r \leftarrow b_l + 1$\\
+   }
+
+   \uIf{$ abs(v_l) < v_r$}{
+     $b_{\theta} \leftarrow b_l$ \\
+   }
+   \Else {
+     $b_{\theta} \leftarrow b_r$ \\
+   }
+   $\theta \leftarrow \pi\times \left[\frac{2.b_{ref}}{nb_s}-1\right]$\\
+
+\end{algorithm}
 
-%% contraintes imposées par le FPGA : algo pipeline/parallele, pas d'op math complexe, ...
+\subsubsection{Comparison}
 
-\subsection{Least square algorithm}
+We compared the two algorithms on the base of three criteria:
+\begin{itemize}
+\item precision of results on a cosines profile, distorted with noise,
+\item number of operations,
+\item complexity to implement an FPGA version.
+\end{itemize}
 
-%% description précise
-%% avantage sur FPGA
+For the first item, we produced a matlab version of each algorithm,
+running with double precision values. The profile was generated for
+about 34000 different values of period ($\in [3.1, 6.1]$, step = 0.1),
+phase ($\in [-3.1 , 3.1]$, step = 0.062) and slope ($\in [-2 , 2]$,
+step = 0.4). For LSQ, $nb_s = 1024$, which leads to a maximal error of
+$\frac{\pi}{1024}$ on phase computation. Current A. Meister and
+M. Favre experiments show a ratio of 50 between variation of phase and
+the deflection of a lever. Thus, the maximal error due to
+discretization correspond to an error of 0.15nm on the lever
+deflection, which is smaller than the best precision they achieved,
+i.e. 0.3nm.
+
+For each test, we add some noise to the profile: each group of two
+pixels has its intensity added to a random number picked in $[-N,N]$
+(NB: it should be noticed that picking a new value for each pixel does
+not distort enough the profile). The absolute error on the result is
+evaluated by comparing the difference between the reference and
+computed phase, out of $2\pi$, expressed in percents. That is: $err =
+100\times \frac{|\theta_{ref} - \theta_{comp}|}{2\pi}$.
+
+Table \ref{tab:algo_prec} gives the maximum and average error for the two algorithms and increasing values of $N$.
+
+\begin{table}[ht]
+  \begin{center}
+    \begin{tabular}{|c|c|c|c|c|}
+      \hline
+  & \multicolumn{2}{c|}{SPL} & \multicolumn{2}{c|}{LSQ} \\ \cline{2-5}
+  noise & max. err. & aver. err. & max. err. & aver. err. \\ \hline
+  0 & 2.46 & 0.58 & 0.49 & 0.1 \\ \hline
+  2.5 & 2.75 & 0.62 & 1.16 & 0.22 \\ \hline
+  5 & 3.77 & 0.72 & 2.47 & 0.41 \\ \hline
+  7.5 & 4.72 & 0.86 & 3.33 & 0.62 \\ \hline
+  10 & 5.62 & 1.03 & 4.29 & 0.81 \\ \hline
+  15 & 7.96 & 1.38 & 6.35 & 1.21 \\ \hline
+  30 & 17.06 & 2.6 & 13.94 & 2.45 \\ \hline
+
+\end{tabular}
+\caption{Error (in \%) for cosines profiles, with noise.}
+\label{tab:algo_prec}
+\end{center}
+\end{table}
+
+These results show that the two algorithms are very close, with a
+slight advantage for LSQ. Furthermore, both behave very well against
+noise. Assuming the experimental ratio of 50 (see above), an error of
+1 percent on phase correspond to an error of 0.5nm on the lever
+deflection, which is very close to the best precision.
+
+Obviously, it is very hard to predict which level of noise will be
+present in real experiments and how it will distort the
+profiles. Nevertheless, we can see on figure \ref{fig:noise20} the
+profile with $N=10$ that leads to the biggest error. It is a bit
+distorted, with pikes and straight/rounded portions, and relatively
+close to most of that come from experiments. Figure \ref{fig:noise60}
+shows a sample of worst profile for $N=30$. It is completely distorted,
+largely beyond the worst experimental ones. 
+
+\begin{figure}[ht]
+\begin{center}
+  \includegraphics[width=\columnwidth]{intens-noise20}
+\end{center}
+\caption{Sample of worst profile for N=10}
+\label{fig:noise20}
+\end{figure}
+
+\begin{figure}[ht]
+\begin{center}
+  \includegraphics[width=\columnwidth]{intens-noise60}
+\end{center}
+\caption{Sample of worst profile for N=30}
+\label{fig:noise60}
+\end{figure}
+
+The second criterion is relatively easy to estimate for LSQ and harder
+for SPL because of $atan$ operation. In both cases, it is proportional
+to numbers of pixels $M$. For LSQ, it also depends on $nb_s$ and for
+SPL on $N = k\times M$, i.e. the number of interpolated points. 
+
+We assume that $M=20$, $nb_s=1024$, $k=4$, all possible parts are
+already in lookup tables and a limited set of operations (+, -, *, /,
+$<$, $>$) is taken account. Translating the two algorithms in C code, we
+obtain about 430 operations for LSQ and 1550 (plus few tenth for
+$atan$) for SPL. This result is largely in favor of LSQ. Nevertheless,
+considering the total number of operations is not really pertinent for
+an FPGA implementation: it mainly depends on the type of operations
+and their
+ordering. The final decision is thus driven by the third criterion.\\
+
+The Spartan 6 used in our architecture has a hard constraint: it has no built-in
+floating  point  units.   Obviously,  it  is  possible  to   use  some  existing
+"black-boxes"  for double  precision  operations.  But they  have  a quite  long
+latency. It is much simpler to  exclusively use integers, with a quantization of
+all double  precision values. Obviously,  this quantization should  not decrease
+too much the  precision of results. Furthermore, it should not  lead to a design
+with  a huge  latency because  of operations  that could  not complete  during a
+single or few clock cycles. Divisions  are in this case and, moreover, they need
+a varying  number of  clock cycles  to complete. Even  multiplications can  be a
+problem:  DSP48 take  inputs of  18  bits maximum.  For larger  multiplications,
+several DSP must be combined, increasing the latency.
+
+Nevertheless, the hardest constraint does not come from the FPGA characteristics
+but from the algorithms. Their VHDL  implementation will be efficient only if they
+can be fully (or near) pipelined. By the way, the choice is quickly done: only a
+small  part of  SPL  can be.   Indeed,  the computation  of spline  coefficients
+implies to solve  a tridiagonal system $A.m =  b$. Values in $A$ and  $b$ can be
+computed from  incoming pixels intensity  but after, the back-solve  starts with
+the  latest  values,  which  breaks  the  pipeline.  Moreover,  SPL  relies  on
+interpolating far more points than profile size. Thus, the end of SPL works on a
+larger amount of data than the beginning, which also breaks the pipeline.
+
+LSQ has  not this problem: all parts  except the dichotomial search  work on the
+same  amount  of  data, i.e.  the  profile  size.  Furthermore, LSQ  needs  less
+operations than SPL, implying a  smaller output latency. Consequently, it is the
+best candidate for phase  computation. Nevertheless, obtaining a fully pipelined
+version supposes that  operations of different parts complete  in a single clock
+cycle. It is  the case for simulations but it completely  fails when mapping and
+routing the design  on the Spartan6. By the way,  extra-latency is generated and
+there must be idle times between two profiles entering into the pipeline.
+
+%%Before obtaining the least bitstream, the crucial question is: how to
+%%translate the C code the LSQ into VHDL ?
+
+
+%\subsection{VHDL design paradigms}
+
+\section{Experimental tests}
+
+In this section we explain what  we have done yet. Until now, we could not perform
+real experiments  since we just have  received the FGPA  board. Nevertheless, we
+will include real experiments in the final version of this paper.
+
+\subsection{VHDL implementation}
+
+From the LSQ algorithm, we have written a C program that uses only
+integer values. We use a very simple quantization by multiplying
+double precision values by a power of two, keeping the integer
+part. For example, all values stored in lut$_s$, lut$_c$, $\ldots$ are
+scaled by 1024. Since LSQ also computes average, variance, ... to
+remove the slope, the result of implied Euclidean divisions may be
+relatively wrong. To avoid that, we also scale the pixel intensities
+by a power of two. Furthermore, assuming $nb_s$ is fixed, these
+divisions have a known denominator. Thus, they can be replaced by
+their multiplication/shift counterpart. Finally, all other
+multiplications or divisions by a power of two have been replaced by
+left or right bit shifts. By the way, the code only contains
+additions, subtractions and multiplications of signed integers, which
+is perfectly adapted to FGPAs.
+
+As said above, hardware constraints have a great influence on the VHDL
+implementation. Consequently, we searched the maximum value of each
+variable as a function of the different scale factors and the size of
+profiles, which gives their maximum size in bits. That size determines
+the maximum scale factors that allow to use the least possible RAMs
+and DSPs. Actually, we implemented our algorithm with this maximum
+size but current works study the impact of quantization on the results
+precision and design complexity. We have compared the result of the
+LSQ version using integers and doubles and observed that the precision
+of both were similar.
+
+Then we built two versions of VHDL codes: one directly by hand coding
+and the other with Matlab using the Simulink HDL coder
+feature~\cite{HDLCoder}. Although the approach is completely different
+we obtained VHDL codes that are quite comparable. Each approach has
+advantages and drawbacks.  Roughly speaking, hand coding provides
+beautiful and much better structured code while Simulink allows to
+produce a code faster.  In terms of throughput and latency,
+simulations shows that the two approaches are close with a slight
+advantage for hand coding.  We hope that real experiments will confirm
+that.
+
+\subsection{Simulation}
+
+Before experimental tests on the board, we simulated our two VHDL
+codes with GHDL and GTKWave (two free tools with linux). For that, we
+build a testbench based on profiles taken from experimentations and
+compare the results to values given by the SPL algorithm. Both
+versions lead to correct results.
+
+Our first code were highly optimized : the pipeline could compute a
+new phase each 33 cycles and its latency was equal to 95 cycles. Since
+the Spartan6 is clocked at 100MHz, it implies that estimating the
+deflection of 100 cantilevers would take about $(95 + 200\times 33).10
+= 66.95\mu$s, i.e. nearly 15000 estimations by second.
+
+\subsection{Bitstream creation}
+
+In order to test our code on the SP Vision board, the design was
+extended with a component that keeps profiles in RAM, flushes them in
+the phase computation component and stores its output in another
+RAM. We also added a wishbone : a component that can "drive" signals
+to communicate between i.MX and others components. It is mainly used
+to start to flush profiles and to retrieve the computed phases in RAM.
+
+Unfortunately, the first designs could not be placed and route with ISE
+on the Spartan6 with a 100MHz clock. The main problems came from
+routing values from RAMs to DSPs and obtaining a result under 10ns. By
+the way, we needed to decompose some parts of the pipeline, which adds
+some cycles. For example, some delays have been introduced between
+RAMs output and DSPs. Finally, we obtained a bitstream that has a
+latency of 112 cycles and computes a new phase every 40 cycles. For
+100 cantilevers, it takes $(112 + 200\times 40).10 = 81.12\mu$s to
+compute their deflection.
+
+This bitstream has been successfully tested on the board TODAY ! YEAAHHHHH
 
-\subsection{VDHL design paradigms}
 
-\subsection{VDHL implementation}
 
-\section{Experimental results}
 \label{sec:results}
 
 
 
 
 \section{Conclusion and perspectives}
-
+In this paper we have presented a new method to estimate the
+cantilevers deflection in an AFM.  This method is based on least
+square methods.  We have used quantization to produce an algorithm
+based exclusively on integer values, which is adapted to a FPGA
+implementation. We obtained a precision on results similar to the
+initial version based on splines.  Our solution has been implemented
+with a pipeline technique.  Consequently, it enables to handle a new
+profile image very quickly. Currently we have performed simulations
+and real tests on a Spartan6 FPGA.
+
+In future work,  we plan to study  the quantization. Then we want  to couple our
+algorithm with a high speed camera and we plan to control the whole AFM system.
 
 \bibliographystyle{plain}
 \bibliography{biblio}