CIT2011/expose_cit2011.tex~

   1 % /solutions/conference-talks/conference-ornate-20min.fr.tex, 22/02/2006 De Sousa
   2 \documentclass{beamer}
   3 %\documentclass[red]{beamer}
   4 \usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
   5 \usepackage{amsfonts,amsmath,amssymb,stmaryrd}
   6 \usepackage[latin1]{inputenc}
   7 \usepackage[T1]{fontenc}
   8 %\usepackage[frenchb]{babel}
   9 \usepackage{aeguill}
  10 \usepackage{graphicx}
  11 \usepackage{amsmath,amssymb}
  12 \usepackage{multirow}
  13 \usepackage{multicol}
  14 \usepackage{colortbl}
  15 \usepackage{graphicx}
  16 %\usepackage{figlatex}
  17 \usepackage{multirow}
  18 \usepackage{times}
  19 \usepackage{marvosym}
  20 \usepackage{pifont}
  21 %\usepackage[vlined,longend,algoruled,titlenumbered,french]{algorithm2e}
  22 \usepackage[vlined,french,algoruled]{algorithm2e}
  23 \usepackage[gen]{eurosym}
  24
  25 %      _         _             _                     _
  26 %  ___| |_ _   _| | ___    ___| |_    ___ ___  _   _| | ___ _   _ _ __ ___
  27 % / __| __| | | | |/ _ \  / _ \ __|  / __/ _ \| | | | |/ _ \ | | | '__/ __|
  28 % \__ \ |_| |_| | |  __/ |  __/ |_  | (_| (_) | |_| | |  __/ |_| | |  \__ \
  29 % |___/\__|\__, |_|\___|  \___|\__|  \___\___/ \__,_|_|\___|\__,_|_|  |___/
  30 %          |___/
  31 %
  32
  33 \setbeamercovered{transparent}
  34 \usetheme{Warsaw}
  35 % enlever [red] dans le \documentclass si utilisation de la suite :
  36 \usecolortheme[RGB={202,31,39}]{structure} % rouge
  37
  38 %\setbeamertemplate{background}{\includegraphics[height=96mm,width=128mm]{fond.png}}
  39
  40 % definition de la couleur du fond des blocks
  41 \definecolor{ArrierePlanBodyW}{rgb}{0.5,0.5,0.5} % si ecriture blanche
  42 \definecolor{ArrierePlanBodyB}{rgb}{0.85,0.85,0.85} % si ecriture noire
  43 % definition de la couleur des slides
  44 \definecolor{ArrierePlan}{rgb}{0.9,0.9,0.9}
  45
  46 % selection de la couleur du fond des slides
  47 \setbeamercolor{background canvas}{bg=ArrierePlan}
  48 % selection de la couleur du fond des block avec ecriture noire
  49 %\setbeamercolor{block body}{use=structure,fg=black,bg=ArrierePlanBodyB}
  50 % selection de la couleur du fond des block avec ecriture blanche
  51 \setbeamercolor{block body}{use=structure,fg=white,bg=ArrierePlanBodyW}
  52
  53
  54 \DeclareGraphicsExtensions{pdf,eps,jpg,png}
  55 \graphicspath{{.}{./fig/}{img/}}
  56
  57 \defbeamertemplate*{footline}{section in head/foot}
  58 {
  59   \leavevmode%
  60   \hbox{\begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm plus1fill,rightskip=.3cm]{author in head/foot}%
  61     \usebeamerfont{author in head/foot}\insertshortauthor
  62   \end{beamercolorbox}%
  63   \begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}%
  64     \usebeamerfont{title in head/foot}\insertshorttitle \hfill \insertframenumber{} / \inserttotalframenumber\hspace*{2ex}%
  65   \end{beamercolorbox}}%
  66   \vskip0pt%
  67 }
  68
  69
  70 \setbeamercovered{dynamic}
  71 %\logo{\includegraphics[height=1cm]{./img/logo_petit-tr.png}}
  72 % \defbeamertemplate*{headline}{split theme}
  73 % {%
  74 %   \begin{beamercolorbox}{section in head/foot}
  75 %     \insertsectionnavigationhorizontal{2cm}{\includegraphics[height=2cm]{./img/logo_petit-tr.png}}{}
  76 %   \end{beamercolorbox}%
  77 %  }
  78
  79 \defbeamertemplate*{headline}{page title}{
  80   \leavevmode%
  81   \begin{beamercolorbox}[wd=.08\paperwidth,ht=1.45cm]{section in head/foot}%
  82     \vbox to 1.45cm{\vfill\hspace*{-0.1mm}\includegraphics[height=1.45cm]{./img/logo_fresnel.pdf}\vfill}%
  83   \end{beamercolorbox}%
  84   \begin{beamercolorbox}[wd=.655\paperwidth,ht=1.45cm]{section in head/foot}%
  85     \vbox to 1.45cm{\vfill\hspace*{-0.1mm}\includegraphics[height=1.45cm]{./img/UPC.jpg}\vfill}%
  86   \end{beamercolorbox}%
  87   \begin{beamercolorbox}[wd=.1\paperwidth,ht=1.45cm]{section in head/foot}%
  88     \vbox to 1.45cm{\vfill\hspace*{1mm}\includegraphics[height=1.25cm]{./img/lifc.pdf}\vfill}%
  89   \end{beamercolorbox}%
  90    \begin{beamercolorbox}[wd=.17\paperwidth,ht=1.45cm]{section in head/foot}%
  91       \vbox to 1.45cm{\vfill\hspace*{-0.1mm}\includegraphics[height=1.45cm]{./img/ufc2.pdf}\vfill}%
  92   \end{beamercolorbox}%
  93 }
  94
  95 \defbeamertemplate*{headline}{section in head/foot}
  96 {
  97   \leavevmode%
  98   \begin{beamercolorbox}[wd=.1\paperwidth,ht=1.45cm]{section in head/foot}%
  99     \vbox to 1.45cm{\vfill\hspace*{-0.1mm}\includegraphics[height=1.25cm]{./img/lifc.pdf}\vfill}%
 100   \end{beamercolorbox}%
 101   \begin{beamercolorbox}[wd=.39\paperwidth,ht=1.45cm]{section in head/foot}%
 102     \vbox to 1.45cm{\vfil\insertsectionnavigation{.4\paperwidth}\vfil}%
 103   \end{beamercolorbox}%
 104   \begin{beamercolorbox}[wd=.43\paperwidth,ht=1.45cm]{subsection in head/foot}%
 105    \vbox to 1.45cm{\vfil\insertsubsectionnavigation{.4\paperwidth}\vfil}%
 106   \end{beamercolorbox}%
 107   %\begin{beamercolorbox}[wd=.17\paperwidth,ht=1.45cm]{section in head/foot}%
 108   %    \vbox to 1.45cm{\vfill\hspace*{-0.1mm}\includegraphics[height=1.45cm]{./img/ufc2.pdf}\vfill}%
 109   %\end{beamercolorbox}%
 110   %\begin{beamercolorbox}[wd=.235\paperwidth,ht=1.45cm]{section in head/foot}%
 111   %    \vbox to 1.45cm{\vfill\hspace*{-0.1mm}\includegraphics[height=1.45cm]{./img/UPC.jpg}\vfill}%
 112   %\end{beamercolorbox}%
 113   \begin{beamercolorbox}[wd=.1\paperwidth,ht=1.45cm]{section in head/foot}%
 114     \vbox to 1.45cm{\vfill\includegraphics[height=1.45cm]{./img/logo_fresnel.pdf}\vfill}%
 115   \end{beamercolorbox}%
 116
 117 }
 118
 119
 120
 121
 122 % CUSTOM JMN
 123 %%%%%%%%%%%%%
 124 % EXERCICES %
 125 %%%%%%%%%%%%%
 126 \newcounter{exo}
 127 \setcounter{exo}{0}
 128 \newcounter{labelExo}
 129
 130 \newcommand{\Exos}[1]{\stepcounter{exo}{\vspace{0.5cm}
 131      {\textbf{Exercice \arabic{exo}~:\ #1}}}}
 132
 133 \newcommand{\Solution}{\vspace{0.5cm}
 134      {\textbf{\emph{Solution de l'exercice \arabic{exo}}}}}
 135
 136 %%%%%%%%%%%%%%%
 137 % DEFINITIONS %
 138 %%%%%%%%%%%%%%%
 139 \newcounter{def}
 140 \setcounter{def}{0}
 141 \newcounter{labelDef}
 142
 143 \renewcommand{\Definition}[1]{\stepcounter{def}{%\vspace{0.5cm}
 144    {\textbf{Définition \arabic{def}~:\ #1 }}}}
 145
 146
 147 \def\N{{ I\!\!N}}
 148 \def\R{{ I\!\!R}}
 149 \def\Z{{ Z\!\!\! Z}}
 150
 151 \def\Q{I\kern-0.60em Q}
 152 \def\C{I\kern-0.60em C}
 153 \def\F{I\kern-0.20em F}
 154 \def\K{I\kern-0.20em K}
 155
 156 % fleche d'affectation pour les algo
 157 \def\plv{$ \leftarrow$\hspace{1ex}}
 158
 159 \titlegraphic{%
 160   \centerline{%
 161     %% \parbox{.165\textwidth}{%
 162     %%  \includegraphics[width=0.165\textwidth]{logo-2lignes-moyen-tr.png}}
 163     %%\hfill
 164     %%\parbox{.22\textwidth}{%
 165     %%  \includegraphics[width=0.11\textwidth]{logo_tutelle4.jpg}}
 166     %\hfill
 167     %\parbox{.22\textwidth}{
 168     %  \includegraphics[width=0.11\textwidth]{logo_petit-tr.png}}
 169     \hfill
 170     \parbox{.5\textwidth}{%
 171       \includegraphics[width=0.5\textwidth]{CITLogo2.jpg}}
 172     \hfill
 173   }
 174 }
 175
 176
 177 \title[Snake GPU] % (facultatif, à utiliser uniquement si le titre de l'article est trop long)
 178 {\scshape GPU-accelerated snake}
 179
 180 \subtitle {GPU implementation of a region-based segmentation algorithm (snake) for large images}
 181
 182 \author[G. Perrot] % (facultatif, à utiliser seulement avec plusieurs auteurs)
 183 {Gilles Perrot$¹$, Stéphane Domas$¹$, Raphaël Couturier$¹$, Nicolas Bertaux$²$.}
 184 % - Composez les noms dans l'ordre dans lequel ils apparaîtrons dans l'article
 185 % - Utilisez la commande \inst{?} uniquement si les auteurs ont des affiliations
 186 %   différentes.
 187
 188 \institute[] % (facultatif mais généralement nécessaire)
 189 {
 190  $¹$University of Franche-Comté - Distributed Numerical Algorithmics group (AND),\\
 191  $²$Fresnel Institute - Physics and Image Computing group (PhyTI)
 192 }
 193 % - Utilisez la commande \inst uniquement s'il y a plusieurs affectations
 194 % - Faîtes quelque chose de simple, personne ne s'intéresse à votre adresse.
 195
 196 \date[] % (facultatif)
 197 {\small 31 august - 1 september}
 198
 199 %\subject{}
 200 % Inséré uniquement dans la page d'information du fichier PDF. Peut être
 201 % supprimé.
 202
 203
 204
 205 % Si vous avez un fichier nommé "université-logo-nomfichier.xxx", où xxx
 206 % est un format graphique accepté par latex ou pdflatex (comme par exemple .png),
 207 % alors vous pouvez insérer votre logo ainsi :
 208
 209 %\pgfdeclareimage[height=1cm]{logo-lifc}{img/logo-lifc.jpg}
 210 %\logo{\pgfuseimage{logo-lifc}}
 211
 212
 213
 214 % À supprimer si vous ne voulez pas que la table des matières apparaisse
 215 % au début de chaque sous-section :
 216 %
 217 % \AtBeginSubsection[] {
 218 %   \begin{frame}<beamer>{Lignes directrices}
 219 %     \tableofcontents[currentsection,currentsubsection]
 220 %   \end{frame}
 221 % }
 222
 223
 224 % Si vous souhaitez recouvrir vos transparents un à un,
 225 % utilisez la commande suivante (pour plus d'info, voir la page 74 du manuel
 226 % d'utilisation de Beamer (version 3.06) par Till Tantau) :
 227
 228 %\beamerdefaultoverlayspecification{<+->}
 229 \colorlet{textvert}{green}
 230
 231 \begin{document}
 232
 233 \setbeamertemplate{headline}[page title]
 234 \setbeamertemplate{footline}[default]
 235
 236 \begin{frame}[default]
 237   \titlepage
 238 \end{frame}
 239
 240
 241 \begin{frame}{Table of contents}
 242   \tableofcontents
 243   % Vous pouvez, si vous le souhaitez ajouter l'option [pausesections]
 244 \end{frame}
 245
 246 \setbeamertemplate{headline}[section in head/foot]
 247 \setbeamertemplate{footline}[section in head/foot]
 248
 249 \section{Context}
 250 \begin{frame}{Image segmentation}
 251 \begin{block}{Definition, goal}
 252 \begin{itemize}
 253   \item Dividing an image in two homogeneous regions.
 254     \item Reducing the amount of data needed to code information.
 255       \item Helping the human perception in certain cases.
 256 \end{itemize}
 257 \end{block}
 258 \end{frame}
 259
 260 \begin{frame}{Images of our interest}
 261 \begin{block}{Origins}
 262 \begin{itemize}
 263   \item Synthetic Aperture RADAR (S.A.R.),
 264     \item Ultrasonic (medical imaging),
 265       \item Photographic (IR, nightshots).
 266 \end{itemize}
 267 \end{block}
 268 \begin{block}{Characterictics}
 269 \begin{itemize}
 270   \item 16 bit-coded gray levels,
 271   \item From 10~Mpixels to more than 100~Mpixels,
 272   \item Very noisy.
 273 \end{itemize}
 274 \end{block}
 275 \end{frame}
 276
 277 \section{Snake algorithm}
 278 \begin{frame}{Active contour hypothesis}
 279 \begin{itemize}
 280   \item A background region $B$ and a target region $T$, containing  $n_T$ and $n_B$ pixels, compose a $L x H$ pixel image.
 281   \item Probability density functions (PDF) $p^B$ and $p^T$ are of the same family (Gaussian in this example).
 282   % inutile ds les hypotheses, on ne dit pas qu'on ls connait
 283   %\item Vectors of parameters $\Theta^B$ and $\Theta^T$ of the PDFs $p^B$ and $p^T$ are unknown.
 284   \item The contour $\varGamma$ which surrounds $T$ is chosen polygonal.
 285   \item [\ding{253}] Implementation of a region-based algorithm.
 286 \end{itemize}
 287 \end{frame}
 288
 289 \begin{frame}{Algorithm  basics : criterion}
 290 \begin{columns}
 291 \begin{column}[l]{5cm}
 292   \resizebox{5cm}{5cm}{\input{img/fig_target.pdf_t}}
 293 \end{column}
 294 \begin{column}[l]{7.5cm}
 295   \begin{itemize}
 296   \item The goal is to find the most likely contour $\varGamma$ (number and positions of nodes).
 297   \item The criterion used is a \emph{Generalized Likelihood} one .\\In the Gaussian case, it is given by
 298     $$GL = \dfrac{1}{2}\left[ n_B.log\left({\widehat{\sigma_B}}^2\right) + n_T.log\left({\widehat{\sigma_T}}^2\right)\right]$$
 299     where $\widehat{\sigma_\Omega}$ is the estimation of the deviation $\sigma$ for the region $\Omega$.
 300   \end{itemize}
 301 \end{column}
 302 \end{columns}
 303 \end{frame}
 304
 305
 306 \begin{frame}{Algorithm basics : parameters estimation}
 307   \begin{itemize}
 308   \item In the Gaussian case,  $p_{\Omega}$ has two parameters, average and deviation, which are estimated by maximum likelihood.\\
 309     If $z$ is the gray level of the pixel of coordinates $(i,j)$:
 310     $$
 311     \left(
 312       \begin{array}{l}
 313         \widehat{\mu_{\Omega}} = \frac{1}{n_{\Omega}} \displaystyle\sum_{(i,j)\in \Omega} z(i,j) \\
 314         \widehat{\sigma^2_{\Omega}} = \frac{1}{n_{\Omega}} \displaystyle\sum_{(i,j)\in \Omega} \left(z(i,j) - \widehat{\mu_{\Omega}}\right)^2 \\
 315       \end{array}
 316     \right.
 317     $$
 318   \item These estimations have to be computed for each test state of the contour $\varGamma$: time-consuming.
 319   \end{itemize}
 320 \end{frame}
 321
 322 \begin{frame}{Algorithm basics : parameters estimation}
 323   \begin{itemize}
 324 %peut-être illustrer ici
 325   \item Based on the Green-Ostogradsky theorem, Chesnaud has shown how to replace those 2-dimensions sums inside the contour
 326     by 1-dimension sums along the contour.
 327     \item This optimization implies:
 328       \begin{itemize}
 329       \item the precomputation of a few matrices (called cumulated images) containing the potential \emph{contributions} of each pixel of the image,
 330         \item the use of constant lookup tables of weighting coefficients to determine the \emph{contributions} of each segment of pixels.
 331       \end{itemize}
 332   \end{itemize}
 333 \end{frame}
 334
 335 \begin{frame}{CPU sequential implementation : outlines}
 336   \begin{enumerate}
 337   \item Precomputation of the cumulated images.
 338     \item Choice of the initial contour $\varGamma_0$: rectangle near the borders.
 339       \item Changes made to the contour in order to find the most likely one:
 340         \begin{enumerate}[i]
 341         \item Move every node as long as it gives a better criterion.
 342           \item Add nodes in the middle of each big enough segment.
 343         \end{enumerate}
 344   \end{enumerate}
 345 \end{frame}
 346
 347  \begin{frame}{Snake algorithm in action}
 348    \begin{columns}
 349      \begin{column}[T]{7cm}
 350        \begin{overprint}
 351          \onslide<1>  \includegraphics[width=7cm]{./img/sequences/cochon_it0.png}
 352          \onslide<2>  \includegraphics[width=7cm]{./img/sequences/cochon_it1.png}
 353          \onslide<3>  \includegraphics[width=7cm]{./img/sequences/cochon_it21.png}
 354          \onslide<4>  \includegraphics[width=7cm]{./img/sequences/cochon_it22.png}
 355          \onslide<5>  \includegraphics[width=7cm]{./img/sequences/cochon_it4.png}
 356        \end{overprint}
 357      \end{column}
 358      \begin{column}[T]{5cm}
 359        \only<1> {
 360          \begin{itemize}
 361          \item 15~Mpixels image\\(SSE implementation limit).
 362          \item Initial contour: 4 nodes.
 363          \end{itemize}
 364        }
 365        \only<2> {
 366          \begin{itemize}
 367          \item End of first iteration: no more move can be of interest.
 368          \end{itemize}
 369        }
 370        \only<3> {
 371          \begin{itemize}
 372          \item Nodes added in the middle of segments.
 373          \end{itemize}
 374        }
 375        \only<4> {
 376          \begin{itemize}
 377          \item End of second iteration.
 378          \end{itemize}
 379        }
 380        \only<5> {
 381          \begin{itemize}
 382          \item End of fifth iteration\\(36 nodes).
 383          \end{itemize}
 384        }
 385      \end{column}
 386    \end{columns}
 387  \end{frame}
 388
 389
 390 \section{GPU Implementation}
 391 \begin{frame}{GPU implementation: prior knowledge}
 392   \begin{itemize}
 393   \item The parallelism of a modern GPU lays on a SIMT paradigm (Single Instruction Multiple Threads): the same instruction
 394     is processed by a great number of threads at a time (up to $2^{16}$).
 395     \item Threads are compounded in independants blocks with no possible synchronization between blocks.
 396       \item Threads in a block share a small amount of shared memory (16-48~KBytes).
 397         \item There are restrictive conditions to be fullfilled in order to make efficent accesses to global and shared memory.
 398           \item Data transfers between CPU and GPU are slow.
 399   \end{itemize}
 400 \end{frame}
 401
 402 \begin{frame}{GPU implementation: precomputations}
 403   \begin{itemize}
 404   \item One of the cumulated images is not to be computed anymore: values are evaluated on the fly.
 405   \item An inclusive parallel prefixsum is performed on each row of the image for each matrix to be processed ($z$,$z^2$).
 406   \item[\ding{253}] Speedup is around x7 for images larger than 100~MPixels. Comparison is done with the SSE/CPU implementation of the PhyTI group.
 407     \item[\ding{253}] Higher speedups (x15) are obtained with specific versions for constant image sizes.
 408   \end{itemize}
 409 \end{frame}
 410
 411
 412 \begin{frame}{GPU implementation: nodes move}
 413 To select the possible next position of a node:
 414 \begin{itemize}
 415 \item Parameters of the new contour have to be estimated.
 416 \item Then the value of the criterion can be obtained and compared with the previous one.
 417 \item The parallelization needs reside essentially in the parameters estimation.\\Two possible parallelism levels:
 418   \begin{itemize}
 419   \item One contour per thread.
 420   \item One pixel per thread.
 421   \item[\ding{253}] The \emph{one pixel per thread} rule is far more efficient, due to memory access constraints.
 422   \end{itemize}
 423 \end{itemize}
 424 \end{frame}
 425
 426
 427 \begin{frame}{GPU implementation: parallelization}
 428   \begin{columns}
 429     \begin{column}[T]{6cm}
 430       \resizebox{6cm}{6cm}{\input{./img/topologie.pdf_t}}
 431     \end{column}
 432     \begin{column}[T]{6.5cm}
 433       \begin{itemize}
 434       \item Every 16 segments for every even/odd nodes are processed in parallel.
 435       \item Fits GPU specific parallelism: each pixel is processed by a thread.
 436       \end{itemize}
 437     \end{column}
 438   \end{columns}
 439 \end{frame}
 440
 441 \begin{frame}{GPU implementation: data structure}
 442 The main idea is to organize, in a single array, every pixels of every segments to be processed.\\
 443 Thus, for a given state of the contour ($N$ nodes), we:
 444   \begin{enumerate}
 445   \item Find the longest segment to be processed. It gives:
 446     \begin{itemize}
 447     \item the block size $bs$ of the computing grid,
 448     \item the number of blocks needed for each segment ($N_{TB}$).
 449     \end{itemize}
 450   \item Compute in parallel,  the coordinates of every pixels of the $16.N$ segments to be considered,
 451   \item Make some parallel reductions to finally obtain parameters estimation.
 452   \end{enumerate}
 453 \end{frame}
 454
 455 \begin{frame}{GPU implementation: data structure}
 456 \begin{center}
 457   \begin{overprint}
 458     \onslide<1> \resizebox{8cm}{1.43cm}{\input{img/contribs_segments_seg.pdf_t}}
 459     \onslide<2> \resizebox{8cm}{3.78cm}{\input{img/contribs_segments_16seg.pdf_t}}
 460     \onslide<3> \resizebox{8cm}{6cm}{\input{img/contribs_segments_even.pdf_t}}
 461     \onslide<4> \resizebox{8cm}{6cm}{\input{img/contribs_segments.pdf_t}}
 462   \end{overprint}
 463 \end{center}
 464 \end{frame}
 465
 466 \begin{frame}{GPU implementation: first results}
 467   \begin{itemize}
 468   \item Global speedup around x7-x8 for image sizes from 15 to 150~Mpixels.
 469   \item First iterations have higher speedups:
 470     \begin{itemize}
 471     \item several large segments,
 472     \item few inactive threads in the grid.
 473     \end{itemize}
 474   \item Last iterations are sometimes slower than on CPU:
 475     \begin{itemize}
 476     \item a lot of small segments,
 477     \item more inactive threads in the grid.
 478     \end{itemize}
 479   \end{itemize}
 480 \end{frame}
 481
 482 \begin{frame}{GPU implementation: smart init (reasons)}
 483   \begin{itemize}
 484   \item The target shape is often far from initial contour,
 485   \item It causes the very first iteration to be much more time-consuming than the other ones.
 486   \item Horizontal segments contributions are null.
 487   \item Vertical segments contributions computations can be fast, through a specific process.
 488   \item[\ding{253}] It's fast to find a rectangle near the target.
 489   \end{itemize}
 490 \end{frame}
 491
 492 \begin{frame}{GPU implementation: smart init (process)}
 493 \begin{columns}
 494 \begin{column}[l]{7cm}
 495   \resizebox{7cm}{6.75cm}{\input{img/smart_init1.pdf_t}}
 496 \end{column}
 497 \begin{column}[l]{5.5cm}
 498   \begin{itemize}
 499   \item Realize a periodic sampling of a few hundreds of J-coordinates.
 500   \item Evaluate in parallel every possible rectangle of diagonal $(0 , j_L)-(H , j_H)$.
 501   \item Select the one with the best GL criterion.
 502   \item $j_L$ and $j_H$ are now considered as constants.
 503   \end{itemize}
 504 \end{column}
 505 \end{columns}
 506 \end{frame}
 507
 508 \begin{frame}{GPU implementation: smart init (process)}
 509 \begin{columns}
 510 \begin{column}[l]{7cm}
 511   \resizebox{7cm}{6.75cm}{\input{img/smart_init2.pdf_t}}
 512 \end{column}
 513 \begin{column}[l]{5.5cm}
 514   \begin{itemize}
 515   \item Given $j_L$ and $j_H$.
 516   \item Realize a periodic sampling of a few hundreds of I-coordinates.
 517   \item Evaluate in parallel every possible rectangle of diagonal $(i_L , j_L)-(i_H , j_H)$.
 518   \item Select the one with the best GL criterion.
 519   \end{itemize}
 520 \end{column}
 521 \end{columns}
 522 \end{frame}
 523
 524 \begin{frame}{GPU implementation: enhancement}
 525   \begin{itemize}
 526   \item Global speedup around x10 for image sizes from 15 to 150~Mpixels and a small enough target (as in the example)
 527   \item Less than 0.6 second for the 150~Mpixels image of this example.
 528   \end{itemize}
 529 \end{frame}
 530
 531 \section{Conclusion}
 532 \begin{frame}{Conclusion, future works}
 533   \begin{itemize}
 534   \item Interesting speedups
 535   \item Original algorithm is not GPU-friendly
 536   \item Future works:
 537     \begin{itemize}
 538     \item Finding a more suited structure to describe the contour.
 539     \item Switching to a statistical model independant from a PDF: the potts model.
 540     \item Benefit from recent features of CUDA v4 (overlapping, multiple kernels)
 541     \item Extend to a multiple targets algorithm, based on this single target elementary piece of code.
 542     \end{itemize}
 543   \end{itemize}
 544 \end{frame}
 545
 546
 547 %\begin{frame}[allowframebreaks]{References}
 548 %\bibliographystyle{plain}
 549 %\bibliography{biblio}
 550 %\nocite{*}
 551 %\end{frame}
 552
 553
 554 \end{document}