\newcommand{\tab}{\ \ \ }
-
\begin{document}
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 :
+The pixels intensity $I$ (in gray level) of each profile is modelized by:
\begin{equation}
\label{equ:profile}
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).\\
+(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
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
+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.\\
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
+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
The board we use is designed by the Armadeus compagny, 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
+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)
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=4$ is sufficient), within $[0,M[$. Let call $x^s$ the
-coordinates of these $N$ points and $I^s$ their intensities.
+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 (SPL in the
+following) are used to interpolate $N = k\times M$ points (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 :
+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.
\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
+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
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}}\]
\[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) \]
\item The simplest method to find the good $\theta$ is to discretize
$[-\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, \]
\end{itemize}
-Finally, the whole summarizes in an algorithm (called LSQ in the following) in two parts, one before and one during the acquisition loop :
+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}[h]
\caption{LSQ algorithm - before acquisition loop.}
\label{alg:lsq-before}
\subsubsection{Comparison}
-We compared the two algorithms on the base of three criterions :
+We compared the two algorithms on the base of three criteria:
\begin{itemize}
\item precision of results on a cosinus profile, distorted with noise,
\item number of operations,
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
+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 =
+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{figure}[ht]
\begin{center}
- \includegraphics[width=9cm]{intens-noise20}
+ \includegraphics[width=\columnwidth]{intens-noise20}
\end{center}
\caption{Sample of worst profile for N=10}
\label{fig:noise20}
\begin{figure}[ht]
\begin{center}
- \includegraphics[width=9cm]{intens-noise60}
+ \includegraphics[width=\columnwidth]{intens-noise60}
\end{center}
\caption{Sample of worst profile for N=30}
\label{fig:noise60}
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
+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 hard constraint : it has no
+The Spartan 6 used in our architecture has 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,
latency because of operations that could not complete during a single
or few clock cycles. Divisions are in this case and, moreover, they
need an varying number of clock cycles to complete. Even
-multiplications can be a problem : DSP48 take inputs of 18 bits
+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 implentation 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.
+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
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
+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
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
+%%Before obtaining the least bitstream, the crucial question is: how to
%%translate the C code the LSQ into VHDL ?
