dmems12.tex

   1 \documentclass[12pt]{article}
   2 %\usepackage{latex8}
   3 %\usepackage{times}
   4 \usepackage[latin1]{inputenc}
   5 %\usepackage{pstricks,pst-node,pst-text,pst-3d}
   6 %\usepackage{babel}
   7 \usepackage{amsmath}
   8 \usepackage{url}
   9 \usepackage{graphicx}
  10 \usepackage{thumbpdf}
  11 \usepackage{color}
  12 \usepackage{moreverb}
  13 \usepackage{commath}
  14 \usepackage{subfigure}
  15 %\input{psfig.sty}
  16 \usepackage{fullpage}
  17 \usepackage{fancybox}
  18
  19 %%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
  20 \newcommand{\noun}[1]{\textsc{#1}}
  21
  22 \newcommand{\tab}{\ \ \ }
  23
  24 %%%%%%%%%%%%%%%%%%%%%%%%%%%% my bib path.
  25
  26
  27 \title{Using FPGAs for high speed and real time cantilever deflection estimation}
  28
  29 \author{ Raphaël COUTURIER\\
  30 Laboratoire d'Informatique
  31 de l'Universit\'e de  Franche-Comt\'e, \\
  32 BP 527, \\
  33 90016~Belfort CEDEX, France\\
  34  \and Stéphane Domas\\
  35 Laboratoire d'Informatique
  36 de l'Universit\'e de  Franche-Comt\'e, \\
  37 BP 527, \\
  38 90016~Belfort CEDEX, France\\
  39  \and Gwenhaël Goavec\\
  40 ??
  41 ?? \\
  42 ??, \\
  43 ??\\}
  44
  45
  46 \begin{document}
  47
  48 \maketitle
  49
  50 \thispagestyle{empty}
  51
  52 \begin{abstract}
  53
  54
  55
  56 {\it keywords}: FPGA, cantilever, interferometry.
  57 \end{abstract}
  58
  59 \section{Introduction}
  60
  61 %% blabla +
  62 %% quelques ref commentées sur les calculs basés sur l'interférométrie
  63
  64 \section{Measurement architecture}
  65 \label{sec:measure-archi}
  66
  67 %% description de l'architecture générale de l'acquisition d'images
  68 %% avec au milieu une unité de traitement dont on ne précise pas ce
  69 %% qu'elle est.
  70
  71 %% image tirée des expériences.
  72
  73 \section{Design goals}
  74 \label{sec:goals}
  75
  76 %% objectifs en terme de rapidité et de précision, avec en vue l'ajout
  77 %% du contrôle => l'unité de traitement qui s'impose est un FPGA =>
  78 %% algo adapté au FPGA.
  79
  80 %% peut etre que cette section peut être déplacée en intro ... à voir.
  81
  82 \section{Proposed solution}
  83 \label{sec:solus}
  84
  85 \subsection{Cantilever deflection estimation}
  86
  87 %% => faire de l'interpolation de signal sinusoidal
  88 %% descriptif rapide des deux méthodes : splines et moindres carrés
  89 As shown on image \ref{img:img-xp}, each cantilever is covered by
  90 interferometric fringes. The fringes will distort when cantilevers are
  91 deflected. Estimating the deflection is done by computing this
  92 distortion. For that, (ref A. Meister + M Favre) proposed a method
  93 based on computing the phase of the fringes, at the base of each
  94 cantilever, near the tip, and on the base of the array. They assume
  95 that a linear relation binds these phases, which can be use to
  96 "unwrap" the phase at the tip and to determine the deflection.\\
  97
  98 More precisely, segment of pixels are extracted from images taken by a
  99 high-speed camera. These segments are large enough to cover several
 100 interferometric fringes and are placed at the base and near the tip of
 101 the cantilevers. They are called base profile and tip profile in the
 102 following. Furthermore, a reference profile is taken on the base of
 103 the cantilever array.
 104
 105 The pixels intensity $I$ (in gray level) of each profile is modelized by :
 106
 107 \begin{equation}
 108 \label{equ:profile}
 109 I(x) = ax+b+A.cos(2\pi f.x + \theta)
 110 \end{equation}
 111
 112 where $x$ is the position of a pixel in its associated segment.
 113
 114 The global method consists in two main sequences. The first one aims
 115 to determin the frequency $f$ of each profile with an algorithm based
 116 on spline interpolation (see below). It also computes the coefficient
 117 used for unwrapping the phase. The second one is the acquisition loop,
 118 while which images are taken at regular time steps. For each image,
 119 the phase $\theta$ of all profiles is computed to obtain, after
 120 unwrapping, the deflection of cantilevers.
 121
 122 This phase computation is obviously the bottle-neck of the whole
 123 process. For example, if we consider the camera actually in use, an
 124 exposition time of 2.5ms for $1024\times 1204$ pixels seems the
 125 minimum that can be reached. For a $10\times 10$ cantilever array, if
 126 we neglect the time to extract pixels, it implies that computing the
 127 deflection of a single cantilever should take less than 25$µ$s, which is
 128 quite small.
 129
 130 \subsection{Considered algorithms}
 131
 132 Two solutions have been studied to achieve phase computation. The
 133 original one, proposed by A. Meister and M. Favre, is based on
 134 interpolation by splines. It allows to compute frequency and
 135 phase. The second one, detailed in this article, is based on a
 136 classical least square method but suppose that frequency is already
 137 known.
 138
 139 \subsubsection{Spline algorithm}
 140
 141 Let consider a profile $P$, that is a segment of $M$ pixels with an
 142 intensity in gray levels. Let call $I(x)$ the intensity of profile in $x
 143 \in [0,M[$.
 144
 145 At first, only $M$ values of $I$ are known, for $x = 0, 1,
 146 \ldots,M-1$. A normalisation allows to scale known intensities into
 147 $[-1,1]$. We compute splines that fit at best these normalised
 148 intensities. Splines are used to interpolate $N = k\times M$ points
 149 (typically $k=3$ is sufficient), within $[0,M[$. Let call $x^s$ the
 150 coordinates of these $N$ points and $I^s$ their intensities.
 151
 152 In order to have the frequency, the mean line $a.x+b$ (see equation \ref{equ:profile}) of $I^s$ is
 153 computed. Finding intersections of $I^s$ and this line allow to obtain
 154 the period thus the frequency.
 155
 156 The phase is computed via the equation :
 157 \begin{equation}
 158 \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]
 159 \end{equation}
 160
 161 Two things can be noticed. Firstly, the frequency could also be
 162 obtained using the derivates of spline equations, which only implies
 163 to solve quadratic equations. Secondly, frequency of each profile is
 164 computed a single time, before the acquisition loop. Thus, $sin(2\pi f
 165 x^s_i)$ and $cos(2\pi f x^s_i)$ could also be computed before the loop, which leads to a
 166 much faster computation of $\theta$.
 167
 168 \subsubsection{Least square algorithm}
 169
 170 Assuming that we compute the phase during the acquisition loop,
 171 equation \ref{equ:profile} has only 4 parameters :$a, b, A$, and
 172 $\theta$, $f$ and $x$ being already known. Since $I$ is non-linear, a
 173 least square method based an Gauss-newton algorithm must be used to
 174 determine these four parameters. Since it is an iterative process
 175 ending with a convergence criterion, it is obvious that it is not
 176 particularly adapted to our design goals.
 177
 178 Fortunatly, it is quite simple to reduce the number of parameters to
 179 only $\theta$. Let $x^p$ be the coordinates of pixels in a segment of
 180 size $M$. Thus, $x^p = 0, 1, \ldots, M-1$. Let $I(x^p)$ be their
 181 intensity. Firstly, we "remove" the slope by computing :
 182
 183 \[I^{corr}(x^p) = I(x^p) - a.x^p - b\]
 184
 185 Since linear equation coefficients are searched, a classical least
 186 square method can be used to determine $a$ and $b$ :
 187
 188 \[a = \frac{covar(x^p,I(x^p))}{var(x^p)} \]
 189
 190 Assuming an overlined symbol means an average, then :
 191
 192 \[b = \overline{I(x^p)} - a.\overline{{x^p}}\]
 193
 194 Let $A$ be the amplitude of $I^{corr}$, i.e.
 195
 196 \[A = \frac{max(I^{corr}) - min(I^{corr})}{2}\]
 197
 198 Then, the least square method to find $\theta$ is reduced to search the minimum of :
 199
 200 \[\sum_{i=0}^{M-1} \left[ cos(2\pi f.i + \theta) - \frac{I^{corr}(i)}{A} \right]^2\]
 201
 202 It is equivalent to derivate this expression and to solve the following equation :
 203
 204 \begin{eqnarray*}
 205 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] \\
 206 - 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
 207 \end{eqnarray*}
 208
 209 Several points can be noticed :
 210 \begin{itemize}
 211 \item As in the spline method, some parts of this equation can be
 212   computed before the acquisition loop. It is the case of sums that do
 213   not depend on $\theta$ :
 214
 215 \[ \sum_{i=0}^{M-1} sin(4\pi f.i), \sum_{i=0}^{M-1} cos(4\pi f.i) \]
 216
 217 \item Lookup tables for $sin(2\pi f.i)$ and $cos(2\pi f.i)$ can also be
 218 computed.
 219
 220 \item The simplest method to find the good $\theta$ is to discretize
 221   $[-\pi,\pi]$ in $N$ steps, and to search which step leads to the
 222   result closest to zero. By the way, three other lookup tables can
 223   also be computed before the loop :
 224
 225 \[ 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] \]
 226
 227 \item This search can be very fast using a dichotomous process in $log_2(N)$
 228
 229 \end{itemize}
 230
 231 \subsubsection{Comparison}
 232
 233 \subsection{FPGA constraints}
 234
 235 %% contraintes imposées par le FPGA : algo pipeline/parallele, pas d'op math complexe, ...
 236
 237 \subsection{Least square algorithm}
 238
 239 %% description précise
 240 %% avantage sur FPGA
 241
 242 \subsection{VDHL design paradigms}
 243
 244 \subsection{VDHL implementation}
 245
 246 \section{Experimental results}
 247 \label{sec:results}
 248
 249
 250
 251
 252 \section{Conclusion and perspectives}
 253
 254
 255 \bibliographystyle{plain}
 256 \bibliography{biblio}
 257
 258 \end{document}