%
% Complete documentation on the extended LaTeX markup used for Insight
% documentation is available in ``Documenting Insight'', which is part
% of the standard documentation for Insight.  It may be found online
% at:
%
%     http://www.itk.org/

\documentclass{InsightArticle}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  hyperref should be the last package to be loaded.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[dvips,
bookmarks,
bookmarksopen,
backref,
colorlinks,linkcolor={blue},citecolor={blue},urlcolor={blue},
]{hyperref}
% to be able to use options in graphics
\usepackage{graphicx}
% for pseudo code
\usepackage{listings}
% subfigures
\usepackage{subfigure}
\usepackage{amssymb}


%  This is a template for Papers to the Insight Journal. 
%  It is comparable to a technical report format.

% The title should be descriptive enough for people to be able to find
% the relevant document. 
\title{Efficient countour detection in binary and label images}

% Increment the release number whenever significant changes are made.
% The author and/or editor can define 'significant' however they like.
% \release{0.00}

% At minimum, give your name and an email address.  You can include a
% snail-mail address if you like.
\author{Ga\"etan Lehmann{$^1$}}
\authoraddress{{$^1$}INRA, UMR 1198; ENVA; CNRS, FRE 2857, Biologie du
D\'eveloppement et
Reproduction, Jouy en Josas, F-78350, France.}

\begin{document}
\maketitle

\ifhtml
\chapter*{Front Matter\label{front}}
\fi


\begin{abstract}
\noindent
Currently in ITK, the contour of the objects in a binary image can be found with \doxygen{BinaryErodeImageFilter}, with a kernel of radius $1$ and \doxygen{SimpleContourExtractorImageFilter}. BinaryErodeImageFilter is a generic filter, made to support any shape and size of structuring element, and thus is not optimized for the particular case needed to detect the contours. Moreover, that filter is not multithreaded, so it can't get the performance improvements allowed by the multiprocessor systems. As a result, the contour detection can be quite time consuming currently -- for example, in \doxygen{SignedMaurerDistanceMapImageFilter}, the contour detection takes about 33\% of the execution time. SimpleContourExtractorImageFilter gives better performance, but uses a rough approach which let a good place for performance enhancements.

This contribution comes with a new filter which highly improve the performance of the contour detection in the binary image, and a second filter which allow the detection of the contours in label images with similar performance.

\end{abstract}

% \tableofcontents

\section{Algorithm and implementation}

The \doxygen{BinaryContourImageFilter} and the \doxygen{LabelContourImageFilter} are based on \doxygen{ConnectedComponentImageFilter}\footnote{More precisely, on a multithreaded version of \doxygen{ConnectedComponentImageFilter}, available at \\ \url{http://voxel.jouy.inra.fr/darcs/contrib-itk/watershed/}} from \cite{Beare:2006p42}. The images is first transformed in a set of lines in the foreground and in the background. The foreground lines which are touching the background are found in the second step, as well as the determination of the exact part of the line on the contour of the object. That way, the image is visited only in raster order, and the comparisons made on blocks of pixels.

Both filters can be run in place.

\section{Binary and label images} \doxygen{BinaryContourImageFilter} performs a contour detection on a single label, and preserves the other (background) values. \doxygen{LabelContourImageFilter} a detection on all the labels in the image, excepted the background label. Because \doxygen{BinaryContourImageFilter} works only on two kinds of pixels, it can be much optimized than \doxygen{LabelContourImageFilter}. The performance difference are not that important though, because most of the execution time is spent in reading the input image, and writing the output one.

\begin{figure}[htbp]
\centering
\includegraphics{2th_cthead1}
\caption{The input image.\label{cthead1}}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics{2th_cthead1-1-200-0}
\caption{Binary contour detection (foreground value is $200$). The background is unchanged.\label{cthead1-bin}}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics{2th_cthead1-1-0}
\caption{Label contour detection. All the label in the image are changed.\label{cthead1-label}}
\end{figure}

\section{Performance}

The performance tests have been run on a Intel\circledR~Pentium\circledR~4 CPU at 3.20GHz with 2GB of RAM running linux 2.6.12, with the command \verb$./perf_threads image/big.nrrd$. The size of the image used for the test is $1024 \times 1024 \times 89$.

The execution time is 1.29 seconds for the binary case, 1.42 seconds for the label case, 67.6 seconds for the morphological erosion, and 10.1 seconds for the simple countour extractor. Compared to the binary erosion used in the Maurer distance map filter, the speed up is 52.4. Compared to the simple countour extractor, the speedup is 7.8.

\section{Examples}
\subsection{Binary case}

\small \begin{verbatim}
#include "itkImageFileReader.h"
#include "itkImageFileWriter.h"
#include "itkSimpleFilterWatcher.h"

#include "itkBinaryContourImageFilter.h"


int main(int argc, char * argv[])
{

  if( argc != 6 )
    {
    std::cerr << "usage: " << argv[0] << " intput output fullyConnected fg bg" << std::endl;
    std::cerr << " input: the input image" << std::endl;
    std::cerr << " output: the output image" << std::endl;
    std::cerr << " fullyConnected: 0 or 1" << std::endl;
    exit(1);
    }

//   itk::MultiThreader::SetGlobalMaximumNumberOfThreads(1);
  const int dim = 3;
  
  typedef unsigned char PType;
  typedef itk::Image< PType, dim > IType;

  typedef itk::ImageFileReader< IType > ReaderType;
  ReaderType::Pointer reader = ReaderType::New();
  reader->SetFileName( argv[1] );

  typedef itk::BinaryContourImageFilter< IType, IType > FilterType;
  FilterType::Pointer filter = FilterType::New();
  filter->SetInput( reader->GetOutput() );
  filter->SetFullyConnected( atoi(argv[3]) );
  filter->SetForegroundValue( atoi(argv[4]) );
  filter->SetBackgroundValue( atoi(argv[5]) );

  itk::SimpleFilterWatcher watcher(filter, "filter");

  typedef itk::ImageFileWriter< IType > WriterType;
  WriterType::Pointer writer = WriterType::New();
  writer->SetInput( filter->GetOutput() );
  writer->SetFileName( argv[2] );
  writer->Update();

  return 0;
}
\end{verbatim} \normalsize

\subsection{Label case}
\small \begin{verbatim}
#include "itkImageFileReader.h"
#include "itkImageFileWriter.h"
#include "itkSimpleFilterWatcher.h"

#include "itkLabelContourImageFilter.h"


int main(int argc, char * argv[])
{

  if( argc != 5 )
    {
    std::cerr << "usage: " << argv[0] << " intput output fullyConnected bg" << std::endl;
    std::cerr << " input: the input image" << std::endl;
    std::cerr << " output: the output image" << std::endl;
    std::cerr << " fullyConnected: 0 or 1" << std::endl;
    exit(1);
    }

//   itk::MultiThreader::SetGlobalMaximumNumberOfThreads(1);
  const int dim = 3;
  
  typedef unsigned char PType;
  typedef itk::Image< PType, dim > IType;

  typedef itk::ImageFileReader< IType > ReaderType;
  ReaderType::Pointer reader = ReaderType::New();
  reader->SetFileName( argv[1] );

  typedef itk::LabelContourImageFilter< IType, IType > FilterType;
  FilterType::Pointer filter = FilterType::New();
  filter->SetInput( reader->GetOutput() );
  filter->SetFullyConnected( atoi(argv[3]) );
  filter->SetBackgroundValue( atoi(argv[4]) );

  itk::SimpleFilterWatcher watcher(filter, "filter");

  typedef itk::ImageFileWriter< IType > WriterType;
  WriterType::Pointer writer = WriterType::New();
  writer->SetInput( filter->GetOutput() );
  writer->SetFileName( argv[2] );
  writer->Update();

  return 0;
}
\end{verbatim} \normalsize

\section{Acknowledgments}
I thank Dr Pierre Adenot and MIMA2 confocal facilities
(\url{http://mima2.jouy.inra.fr}) for providing the 3D test image.

\section{Conclusion}

That contribution can highly enhance the performance of the algorithms where the contour of the objects must be detected. Use in \doxygen{SignedMaurerDistanceMapImageFilter}\footnote{A multithreaded version of \doxygen{SignedMaurerDistanceMapImageFilter} which use that contribution is available at \url{http://voxel.jouy.inra.fr/darcs/contrib-itk/watershed/}} instead of \doxygen{BinaryErodeImageFilter}, it can speedup the execution time by about 30\%.

% \url{http://www.itk.org}
% \code{Insight/Documentation/Style.pdf}
% \section{Principles of Solar Spot Detection}
% \cite{ITKSoftwareGuide}.
% \doxygen{ImageToImageFilter}

% \small \begin{verbatim}
% \end{verbatim} \normalsize


% The {itemize} environment uses a bullet for each \item.  If you want the 
% \item's numbered, use the {enumerate} environment instead.
% \begin{itemize}
%   \item  Insight Toolkit 2.4.
%   \item  CMake 2.2
% \end{itemize}

% \ref{cthead1}



\appendix



\bibliographystyle{plain}
\bibliography{InsightJournal}
% \nocite{ITKSoftwareGuide}

\end{document}