\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}

\maketitle

\thispagestyle{empty}

\begin{abstract}

  

{\it keywords}: FPGA, cantilever, interferometry.
\end{abstract}

\section{Introduction}

%% 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}
