%
% 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}

\usepackage{picins}
\usepackage{graphicx}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  hyperref should be the last package to be loaded.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage[
bookmarks,
bookmarksopen,
backref,
colorlinks,
linkcolor={blue},
citecolor={blue},
urlcolor={blue},
]{hyperref}

%  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{Shaped Neighborhood based Flood Filled Conditional Iterators}

% 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{Tim Hauke Heibel and Martin Groher}
\authoraddress{Computer Aided Medical Procedures, Technische Universit\"at M\"unchen}

\begin{document}

\maketitle

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

% The abstract should be a paragraph or two long, and describe the
% scope of the document.
\begin{abstract}
\noindent
ITK's \cite{ITKSoftwareGuideSecondEdition} flood filling iterator represents a way to visit pixels/voxels within an image 
having a specific connectivity. The iterator is initialized at known seed points and
starting from these, neighbors that are within the desired connectivity are marked as to
be visited and processed by the iterator in the future.

The \htmladdnormallink{FloodFilledFunctionConditionalConstIterator}
{http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Common/itkFloodFilledFunctionConditionalConstIterator.h?root=Insight&view=log}
builds the foundation for the implementation of the 
\htmladdnormallink{NeighborhoodConnectedImageFilter}
{http://www.itk.org/cgi-bin/viewcvs.cgi/Code/BasicFilters/itkNeighborhoodConnectedImageFilter.h?root=Insight&view=log}
and is currently fixed to investigating 4-neighborhoods in 2D and 6-neighborhoods in 3D. 
Since many existing applications use region growing algorithms that perform on full 
neighborhoods (i.e. 8-connected in 2D and 26-connected in 3D) it is desirable to be able 
to choose at least between these two standard connectivities.

In this document we describe the extension of the existing iterator to be using 
\htmladdnormallink{ShapedNeighborhoodIterators}
{http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Common/itkShapedNeighborhoodIterator.h&root=Insight&view=log} 
which has already been proposed in the 
implementation of the \htmladdnormallink{FloodFilledFunctionConditionalConstIterator}
{http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Common/itkFloodFilledFunctionConditionalConstIterator.txx?root=Insight&view=log}.

\end{abstract}

\tableofcontents

Since the changes described in this publication are very basic the remainder
will be kept quite short. First we will give a quick overview about the implementation 
details and then we will provide some results and comparisons of the new iterator 
with the already existing one. The comparisons will focus on 
\begin{itemize}
\item topology in 2D and 3D 
\item speed comparisons.
\end{itemize}
The topology of the new filter, i.e. the order in which pixels/voxels are processed
is here of particular interest since backward compatibility requires the new
iterator to process pixels in the exact same order as the existing iterator.
This must be the case due to the fact that there may exist implementations which do 
in some way rely on the order in which pixels/voxels are processed.

\section{Implementation Details}

The existing implementation computes offsets to access a specific pixel in the 
neighborhood of the currently processed pixel in a low level way. The advantage 
of this approach is that it is performance wise quite fast though the code is
not easy to grasp at the first glance. Furthermore the existing implementation
is bound to a fixed 4-neighborhood in 2D and a 6-neighborhood in 3D while some
applications might take advantage of fully connected neighborhoods.

It has already been mentioned in the current implementation that the loop used
during the neighborhood iteration could be replaced with a \code{ShapedNeighborhoodIterator}
and we simply followed this advice.

Since the processing loop is making extensive use of the actual index of each
neighbor, we used the function 
\code{ShapedNeighborhoodIterator::ConstIterator::GetNeighborhoodOffset()} and the knowledge 
about the position of the center pixel to compute the neighbor's index. Due to
the fact that we are not using the iterators of the neighborhood to access 
the underlying pixel values, the \code{ShapedNeighborhoodIterator} does not need 
to be shifted over the image itself and thus we are not required to call
\code{ConstNeighborhoodIterator::SetLocation()} which would increase the processing 
time of the iterator loop dramatically. As a matter of fact we are just using the
iterator functionality of the \code{ShapedNeighborhoodIterator::ConstIterator} but
not the one of the \code{ShapedNeighborhoodIterator} itself.

The proposed \code{ShapedFloodFilledFunctionConditionalConstIterator} 
has the same functionality and the same basic interface as the existing
\code{FloodFilledFunctionConditionalConstIterator}. The usage of the
\code{ShapedNeighborhoodIterator} now furthermore allows the user to configure the 
\code{ShapedFloodFilledFunctionConditionalConstIterator} such that the flood
filling is performed based on a fully connected neighborhood in ND. The class 
interface has therefore been extended by four functions
\begin{itemize}
	\item \code{void SetFullyConnected(const bool fullyConnected)}
	\item \code{bool GetFullyConnected() const}
	\item \code{void FullyConnectedOn()}
	\item \code{void FullyConnectedOff()}
\end{itemize}
When the member variable \code{m\_FullyConnected} is set to \code{true} the underlying
\code{ShapedNeighborhoodIterator} is configured to have a fully connected neighborhood
(8-connected in 2D and 26-connected in 3D). This configuration is achieved by utilizing
the template method \code{TIterator* setConnectivity( TIterator* it, bool fullyConnected )}
provided via the header file \htmladdnormallink{itkConnectedComponentAlgorithm.h}
{http://www.itk.org/cgi-bin/viewcvs.cgi/Code/BasicFilters/itkConnectedComponentAlgorithm.h?root=Insight&view=log}.
Whenever the same member variable is set to \code{false} the iterator will be put back in
its default behavior that is equivalent to the class \code{FloodFilledFunctionConditionalConstIterator}.

\section{Results and Testing}

The first test we performed aimed at the verification if the new implementation processes contour
pixels in the same order as the existing version. This test has been done by creating a
synthetic image similar to the one in figure \ref{fig:Input2D} and by executing both iterators on 
the same image. While incrementing both iterators during each step of the image traversal we check
if the iterators are containing the same index. 

\piccaption{2D synthetic input \label{fig:Input2D}}
\parpic(130px,130px)[f]{
  \includegraphics[width=128px]{./images/input2D.png}  
}

As soon as this is not the case the test will
exit while indicating a failure. The test has been implemented currently for 2D case (\code{IteratorTest2D})
as well as for the 3D case (\code{IteratorTest3D}) and succeeded in both cases.

For the evaluation of the full connectivity we created an image with an object that could only
be extracted as a whole in cases where the iterator investigates a fully connected neighborhood. 
Again an output image has been created where all pixels visited by the iterator were simply 
marked with $255$. The final test is performed by iterating a second time over all pixels of the
input and output image while verifying that both images are identical. The test will exit while
yielding a failure if that is not the case and has been implemented in \code{IteratorTest2D8Connected}.

Finally for the evaluation of the performance compared to the original implementation we created
a relatively large image (1280x1280 pixels) and let both iterators process the image one after the other.
The processing time has been measured for each iterator separately via the \code{itk::TimeProbe}
class. The process itself has been repeated a hundred times to achieve a more representative measure
since the problem with high precision timers is that they do not profile the real performance but rather
the performance including processor stalls, which results in measurements that are subject to high
fluctuations. Nonetheless the measurements indicate that the new implementation is approximately
20.22\% slower than the existing implementation.

For us it is currently not completely clear where this discrepancy is originating from since the 
\code{ShapedNeighborhoodIterator} has already all offsets precomputed, and accessing these
offsets is just a matter of requesting data from a list. The \code{ShapedNeighborhoodIterator}
itself is, as mentioned beforehand, not recreated during the 
\code{ShapedFloodFilledFunctionConditionalConstIterator}'s increment and can thus not be
the bottleneck leading to the lack of performance.

\begin{figure}[htbp]
     \begin{minipage}{0.45\textwidth}
      \centering
       \includegraphics[width=0.95\textwidth]{./images/1280x1280times.png}
       \caption{Measured times (Blue 'Low-level Offsets', Red 'ShapedNeighborhoodIterator') for iterating over the test image given in seconds.}
     \end{minipage}\hfill
     \begin{minipage}{0.45\textwidth}
      \centering
       \includegraphics[width=0.95\textwidth]{./images/1280x1280_910791.png}
       \caption{Performance decrease given in percent. The box plot shows a median value of 20.22\% as well as quite a few outliers due to the fluctuations of the performance counter.}
     \end{minipage}
\end{figure}

\section{Conclusion and Discussion}

We have provided a small change for the \code{FloodFilledFunctionConditionalConstIterator} that 
allows the user to choose between sparse and full connectivity of the neighborhood. These changes
are currently encapsulated in two new classed namely
\begin{itemize}
  \item \code{ShapedFloodFilledFunctionConditionalConstIterator}
  \item \code{ShapedFloodFilledImageFunctionConditionalConstIterator}.
\end{itemize}
If it is possible to adapt the new implementation such that it performs equivalently fast as the
old implementation we suggest to merge our proposed changes into the existing
\code{FloodFilledFunctionConditionalConstIterator} since it would allow algorithms such as
the \code{NeighborhoodConnectedImageFilter} to perform a region growing
on sparsely connected objects.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Insert the bibliography using BibTeX
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{plain}
\bibliography{InsightJournal}


\end{document}