%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {

% The Beamer class comes with a number of default slide themes
% which change the colors and layouts of slides. Below this is a list
% of all the themes, uncomment each in turn to see what they look like.

%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

% As well as themes, the Beamer class has a number of color themes
% for any slide theme. Uncomment each of these in turn to see how it
% changes the colors of your current slide theme.

%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
%\usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
%\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
%\usecolortheme{wolverine}

%\setbeamertemplate{footline} % To remove the footer line in all slides uncomment this line
%\setbeamertemplate{footline}[page number] % To replace the footer line in all slides with a simple slide count uncomment this line

%\setbeamertemplate{navigation symbols}{} % To remove the navigation symbols from the bottom of all slides uncomment this line
}

\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{listings}
\usepackage{adjustbox}

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title{Real-time Image Segmentation} % The short title appears at the bottom of every slide, the full title is only on the title page

\author{Miklos Homolya, Ravikishore Kommajosyula, Gaurav Kukreja} % Your name
\institute[TUM] % Your institution as it will appear on the bottom of every slide, may be shorthand to save space
{
Technical University of Munich \\ % Your institution for the title page
\medskip
}
\date{\today} % Date, can be changed to a custom date

\begin{document}
 \lstset{language=C++,
 	basicstyle=\ttfamily\scriptsize,
 	keywordstyle=\color{blue}\ttfamily,
 	stringstyle=\color{red}\ttfamily,
 	commentstyle=\color{green}\ttfamily,
 	breaklines=true
 }

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------

%------------------------------------------------
\section{Introduction} % Sections can be created in order to organize your presentation into discrete blocks, all sections and subsections are automatically printed in the table of contents as an overview of the talk
%------------------------------------------------

\begin{frame}
\frametitle{Problem Definition}

\end{frame}

%------------------------------------------------
%------------------------------------------------

\section{Algorithm}

\subsection{Binary Image Segmentation}

\begin{frame}
  \frametitle{Binary Image Segmentation}

  Energy functional
  \begin{equation*}
    E_1(u) := \int_{{\rm I\!R}^N} \left| \nabla u \right|
    + \lambda \int_{{\rm I\!R}^N} \left| u(x) - f(x) \right| \, dx
  \end{equation*}

  Functional derivative
  \begin{equation*}
    \frac{\delta E_1}{\delta u} = - \, \mathrm{div} \left( {\frac{\nabla u}{| \nabla u |}} \right)
    + \lambda \frac{u - f}{|u - f|}
  \end{equation*}

  Gradient descent solver \\~\\

  \begin{thebibliography}{99}
  \bibitem[Chan, 2005]{} Tony F. Chan, Selim Esedoglu and Mila Nikolova (2005)
    \newblock Finding the Global Minimum for Binary Image Restoration
  \end{thebibliography}
\end{frame}

\begin{frame}
  \frametitle{Sample Result}
  \begin{columns}[t]
    \begin{column}{.4\textwidth}
      \adjincludegraphics[width=\linewidth]{binary_in}
      Noisy binary image.
    \end{column}
    \begin{column}{.4\textwidth}
      \adjincludegraphics[width=\linewidth]{binary_out}
      Restored binary image.
    \end{column}
  \end{columns}
\end{frame}

\subsection{Grayscale Image Segmentation}

\begin{frame}
  \frametitle{Grayscale Image Segmentation}

  Euler-Lagrange equation
  \begin{equation*}
    \mathrm{div} \left( {\frac{\nabla u}{| \nabla u |}} \right)
    - \lambda \, s(x) - \alpha \, \nu'(u) = 0
  \end{equation*}
  where $ s(x) = (c_1 - f(x))^2 - (c_2 - f(x))^2 $, and $ \alpha \, \nu'(u) $ forces $ u $ into $ [0; 1] $.
  \\~\\
  Gradient descent solver
  \\~\\
  \begin{thebibliography}{99}
  \bibitem[Chan, 2004]{} Tony F. Chan, Selim Esedoglu and Mila Nikolova (2004)
    \newblock Algorithms for Finding Global Minimizers of Image Segmentation and Denoising Models
  \end{thebibliography}
\end{frame}

\begin{frame}
  \frametitle{Sample Result}
  \begin{columns}[t]
    \begin{column}{.4\textwidth}
      \adjincludegraphics[width=\linewidth]{camera_in}
      Grayscale input image.
    \end{column}
    \begin{column}{.4\textwidth}
      \adjincludegraphics[width=\linewidth]{camera_out}
      Segmentation (without thresholding).
    \end{column}
  \end{columns}
\end{frame}

\subsection{Primal-Dual Method}

\begin{frame}
  \frametitle{Primal-Dual Method}
  \emph{Motivation:} Gradient descent solver has slow convergence.
  \\~\\
  Primal variable $ u \in \mathcal{C} $
  \begin{equation*}
    u : \Omega \to [0; 1]
  \end{equation*}
  Dual variable $ \xi \in \mathcal{K} $ \quad ($ \xi \sim \mathrm{grad} \, u $)
  \begin{equation*}
    \xi : \Omega \to \left\{ (x, y) : x^2 + y^2 \le 1 \right\}
  \end{equation*}

  Algorithm:
  \begin{align*}
    \xi^{n+1} &= \Pi_{\mathcal{K}}(\xi^n - \sigma \nabla \bar{u}^n)
    \\
    u^{n+1} &= \Pi_{\mathcal{C}}(u^n - \tau (\mathrm{div} \xi^{n+1} + s))
    \\
    \bar{u}^{n+1} &= u^{n+1} + (u^{n+1} - u^n) = 2 u^{n+1} - u^n
  \end{align*}
  $ \Pi_{\mathcal{C}} $ and $ \Pi_{\mathcal{K}} $ clamp the range to fit $ \mathcal{C} $ and $ \mathcal{K} $ respectively.
\end{frame}

\begin{frame}
  \frametitle{Result}
  \begin{itemize}
  \item A single iteration is costlier than for the gradient descent solver, but we could reduce iteration count from 2000 to 160.
  \item Huge impact on performance.
  \end{itemize}
\end{frame}

\section{CUDA Implementation}

\begin{frame}
  \frametitle{CUDA Implementation}
  \begin{itemize}
  \item Update kernels calls from CPU to have synchronization

  \item Update $ \xi $ and update $ u $ implemented as two kernels

  \item Image arrays for $ u^{n-1} $ and $ u^n $ swapped after each iteration

  \item Branching to avoid invalid memory accesses
  
  \end{itemize}

\end{frame}

\section{Optimizations}


\subsection{Texture Memory}

\begin{frame}
  \frametitle{CUDA Implementation}
  \begin{itemize}
  \item Swapping images after each iteration makes things difficult

  \item Cannot be used in gradient calculation. Can be used in divergence calculation

  \item Texture memory used on intermediate results $ \xi_x $ and $ \xi_y $
  
  \item Improves the FPS by 12\%
  
  \end{itemize}

\end{frame}

\subsection{OpenGL Interoperability}

\begin{frame}
\frametitle{OpenGL Interoperability}
What is Interoperability?
\begin{itemize}
	\item Mapping OpenGL Resources to CUDA, to enable CUDA to read/write
	\item Can be used to show output from CUDA kernel, straight from GPU saving time and bandwidth
\end{itemize}
\end{frame}

%------------------------------------------------

\begin{frame}[fragile]
	\frametitle{How to use OpenGL Interop?}
	\begin{itemize}
		\item Set current threads OpenGL context to use for OpenGL interop with CUDA \textbf{device}.
		\begin{lstlisting}
		cudaGLSetGLDevice(device);
		\end{lstlisting}
		\item Create OpenGL Pixel Buffer, and register to use as CUDA buffer.
		\begin{lstlisting}
		gl.glGenBuffers(1, &pixels);
		gl.glBindBuffer(GL_PIXEL_UNPACK_BUFFER, pixels);
		size_t size = w * h * 4 * sizeof(unsigned char);
		gl.glBufferData(GL_PIXEL_UNPACK_BUFFER, size, 0, GL_DYNAMIC_DRAW);
		cudaGraphicsGLRegisterBuffer(&pixels_CUDA, pixels, cudaGraphicsMapFlagsWriteDiscard);
		\end{lstlisting}
	\end{itemize}
\end{frame}

\begin{frame}[fragile]
	\frametitle{How to use OpenGL Interop?}
	Inside the Display Loop,
	\begin{itemize}
		\item Before starting kernel, map pixel buffer to a CUDA pointer.
		\begin{lstlisting}
		cudaGraphicsMapResources(1, &pixels_CUDA, 0); 
		cudaGraphicsResourceGetMappedPointer(&d_pixels, &size,  pixels_CUDA);
		\end{lstlisting}
		\item Pass CUDA pointer as parameter for kernel. The kernel writes to the buffer in \textbf{RGBA8} format.
		\item After kernel execution, unmap pixel buffer.
		\begin{lstlisting}
		cudaGraphicsUnmapResources(1, &pixels_CUDA, 0);
		\end{lstlisting}
		\item Draw buffer
		\begin{lstlisting}
		glDrawPixels(w, h, GL_RGBA, GL_UNSIGNED_BYTE, 0);
		\end{lstlisting}
	\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Demo}
  \huge{\centerline{Thank you for your attention.}}
\end{frame}

\end{document} 
