From 378804e7fc26018b70fc8beafbb03b16a0e536f2 Mon Sep 17 00:00:00 2001 From: =?utf8?q?St=C3=A9phane=20Domas?= Date: Fri, 14 Oct 2011 15:34:05 +0200 Subject: [PATCH 1/1] premier commit : MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit - canevas de base du document - début de la rédaction de la partie algos --- dmems12.tex | 256 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 251 insertions(+), 5 deletions(-) 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} -- 2.39.5