
\documentclass[twocolumn, final]{svjour3}

\usepackage[square, numbers, sort]{natbib}

\usepackage{transparent}
%\usepackage[pdftex]{graphicx,color}
%   \graphicspath{{imgfs/}}
%   \DeclareGraphicsExtensions{.pdf,.jpeg,.png}

  %\usepackage[dvips]{graphicx}
  \usepackage{graphicx}
  %\graphicspath{{imgfs/}}
  \DeclareGraphicsExtensions{.jpg}

% *** MATH PACKAGES ***
%
\usepackage[cmex10]{amsmath}

% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage[ruled,lined,linesnumbered]{algorithm2e}

% *** ALIGNMENT PACKAGES ***
%
\usepackage{array}
\usepackage{mdwmath}
\usepackage{mdwtab}

% *** SUBFIGURE PACKAGES ***
\usepackage[caption=false,font=footnotesize]{subfig}

% *** FLOAT PACKAGES ***
%
\usepackage{fixltx2e}

\journalname{Signal Processing Systems}

\newcommand{\kl}{\includegraphics[scale=0.4]{kernLeft.jpg}~}
\newcommand{\kr}{\includegraphics[scale=0.4]{kernRight.jpg}}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{Fine-tuned high-speed implementation \\of a GPU-based median filter.}

% author names and affiliations
% use a multiple column layout for up to two different
% affiliations

\author{
Gilles Perrot \and
St\'{e}phane Domas \and
Rapha\"{e}l Couturier}

\institute{
FEMTO-ST institute\\
Rue Engel Gros, 90000 Belfort, France.\\\email{forename.name@univ-fcomte.fr}  
}

\date{Received: date / Revised: date}

% make the title area
\maketitle

\keywords{median, filter, GPU}

\begin{abstract}
  Median filtering is a well-known method used in a wide range of application frameworks as well as a standalone filter, especially for \textit{salt-and-pepper} denoising. It is able to highly reduce the power of noise while minimizing edge blurring.
Currently, existing algorithms and implementations are quite efficient but may be improved as far as processing speed is concerned, which has led us to further investigate the specificities of modern GPUs.
In this paper, we propose the GPU implementation of fixed-size kernel median filters, able to output up to 1.85 billion pixels per second on C2070 Tesla cards. 
Based on a Branchless Vectorized Median class algorithm and implemented through memory fine tuning and the use of GPU registers, our median drastically outperforms existing implementations, resulting, as far as we know, in the fastest median filter to date.  
\end{abstract} 

\section{Introduction}
First introduced by Tukey in \cite{tukey77}, median filtering has been widely studied since then, and many researchers have proposed efficient implementations of it, adapted to various hypothesis, architectures and processors. 
Originally, its main drawbacks were its compute complexity, its non linearity and its data-dependent runtime. Several researchers have addressed these issues and designed, for example, efficient histogram-based median filters featuring predictable runtimes \cite{Huang:1981:TDS:539567, Weiss:2006:FMB:1179352.1141918}.  
More recently, authors have managed to take advantage of the newly opened perspectives offered by modern GPUs, to develop CUDA-based filters such as the Branchless Vectorized Median filter (BVM) \cite{5402362, chen09} which allows very interesting runtimes and  the histogram-based, PCMF median filter \cite{6288187} which was the fastest median filter implementation to our knowledge.

The use of a GPU as a general-purpose computing processor raises the issue of data transfers, especially when kernel runtime is fast and/or when large data sets are processed. In certain cases, data transfers between GPU and CPU are slower than the actual computation on GPU, even though global GPU processes can prove faster than similar ones run on CPU. 
In the following section, we propose the overall code structure to be used with our median kernels. 
For more concision and readability, our coding will be restricted to 8 or 16 bit gray-level input images whose height ($H$) and width ($W$) are both multiples of 512 pixels. 
Let us also point out that the following implementation, targeted on Nvidia Tesla GPU (Fermi architecture, compute capability 2.x), may easily be adapted to other models e.g. those of compute capability 1.3.

\section{General structure}
Algorithm \ref{algo:memcopy} describes how data is handled in our code. 
Input image data is stored in the GPU's texture memory so as to benefit from the 2-D caching mechanism. After kernel execution, copying output image back to CPU memory is done by use of pinned memory, which drastically accelerates data transfer.
 
\begin{algorithm}
%\SetNlSty{textbf}{}{:}
\footnotesize
 allocate and populate CPU memory \textbf{h\_in}\;
 allocate CPU pinned-memory \textbf{h\_out}\;
 allocate GPU global memory \textbf{d\_out}\;
 declare GPU texture reference \textbf{tex\_img\_in}\;
 allocate GPU array \textbf{array\_img\_in}\;
 bind \textbf{array\_img\_in} to texture \textbf{tex\_img\_in}\;
 copy data from \textbf{h\_in} to \textbf{array\_img\_in}\label{algo:memcopy:H2D}\; 
 kernel\kl gridDim,blockDim\kr\tcc*[f]{to d\_out}\label{algo:memcopy:kernel}\;
 copy data from \textbf{d\_out} to \textbf{h\_out} \label{algo:memcopy:D2H}\;
\caption{Global memory management on CPU and GPU sides.}
\label{algo:memcopy}
\end{algorithm}

% references section
\bibliographystyle{spbasic}

\bibliography{biblio3}



% that's all folks
\end{document}

%doi = {10.5201/ipol.2011.bcm_nlm},