%======================================================================%
% Filename: Article.tex
% Project: Insight Journal Article - MaskedSpatialObjectToImageFilter
% Author: Daniel Mueller: d.mueller [at] qut.edu.au
%----------------------------------------------------------------------%
% Description:
% This artcile describes the MaskedSpatialObjectToImageFilter which
% allows for dramatic speed-ups for 'sparse' SpatialObject scenes.
%======================================================================%
\documentclass{InsightArticle}

\usepackage{amsfonts}					%Maths fonts
\usepackage{amssymb}					%Maths symbols
\usepackage{listing}					%Used for list of listings
\usepackage{listings}					%List program code source
\usepackage{subfigure}				  	%For subfigures
\usepackage{pstricks,pst-grad,multido} 	%For drawing barcharts
\usepackage[dvips]{graphicx}            %Graphics
\graphicspath{{images/}}                %List folders to figures here
\usepackage[dvips,						%Allow urls 
						bookmarks, 
						bookmarksopen,
						bookmarksnumbered, 
						backref,
						colorlinks,
						linkcolor={blue},
						citecolor={blue},
						urlcolor={blue}]{hyperref}

%======================================================================%
%                   F r o n t   M a t t e r                            % 
%======================================================================%
% The title should be descriptive enough for people to be able to find
% the relevant document. 
\title{Using a Mask to Decrease Computation Time for SpatialObject to Image Conversions}

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

% Name and affiliation
\author{Dan Mueller$^{\scriptscriptstyle\textsf{1}}$}
\authoraddress{ $^{\textsf{1}}$Queensland University of Technology, Brisbane, Australia }

%	Set custom header style
\pagestyle{fancy}								
\fancyhead{} 			% clear all header fields
\fancyhead[L]{\textsf{ Using a Mask to Decrease Computation Time for SpatialObject to Image Conversions }}
\fancyhead[R]{\textsf{\thepage}}
\fancyfoot{} 			% clear all footer fields

%Set default font
%\renewcommand{\familydefault}{\rmdefault}	%Roman
\renewcommand{\familydefault}{\sfdefault}	%Sans serif
%\renewcommand{\familydefault}{\ttdefault}	%Typewriter

%Define some colors
\definecolor{colorgridback}{rgb}{0.975,0.975,0.975}
\definecolor{colorgridlines}{gray}{0.125}
\definecolor{colorbarsub}{rgb}{0.85,0.2,0.2}
\definecolor{listcomment}{rgb}{0.0,0.5,0.0}
\definecolor{listkeyword}{rgb}{0.0,0.0,0.5}
\definecolor{listbackground}{gray}{0.965}

% Declare variables for barchart
\newdimen\mainbarwidth
\mainbarwidth = 0.4cm

\def\barmain(#1){
	\newdimen\tempy
	\tempy=\y
	\advance\tempy by \mainbarwidth
	\psframe[fillstyle=gradient,
	         gradbegin=white,
		     gradend=blue,
		     gradmidpoint=0,
		     gradangle=90](0,\y)(#1,\tempy)	
}

\def\barmainlegend{
	\newdimen\tempy
	\newdimen\tempx
	\tempy=\y
	\tempx=\x
	\advance\tempy by \mainbarwidth
	\advance\tempx by \mainbarwidth
	\psframe[fillstyle=gradient,
	         gradbegin=white,
		     gradend=blue,
		     gradmidpoint=0,
		     gradangle=90](\x,\y)(\tempx,\tempy)	
}

\def\barsub(#1){
	\newdimen\ysubone
	\newdimen\ysubtwo
	\ysubone=\y
	\ysubtwo=\y
	\advance\ysubone by \mainbarwidth
	\advance\ysubone by -0.175\mainbarwidth
	\advance\ysubtwo by 0.175\mainbarwidth
	\psframe[fillstyle=solid,fillcolor=colorbarsub](\x,\ysubone)(#1,\ysubtwo)	
	
}

\def\barsublegend{
	\newdimen\tempy
	\newdimen\tempx
	\tempy=\y
	\tempx=\x
	\advance\tempy by \mainbarwidth
	\advance\tempx by \mainbarwidth
	\psframe[fillstyle=solid,fillcolor=colorbarsub](\x,\y)(\tempx,\tempy)	
}

\def\nextbar{\advance\y by -0.5cm}

\def\addbartext#1{%
	\newdimen\ytext
	\ytext=\y
	\advance\ytext by 0.1cm
	\rput[rB](-0.2,\ytext){#1}%
	\advance\y by -0.5cm%
}


% Document
\begin{document}

% Setup source code listings 
\lstset{frame = tb,
        framerule = 0.5pt,
        float,
        fontadjust,
        backgroundcolor={\color{listbackground}},
        basicstyle = {\ttfamily\footnotesize},
        keywordstyle = {\ttfamily\color{listkeyword}\textbf},
        identifierstyle = {\ttfamily},
        commentstyle = {\ttfamily\color{listcomment}\textit},
        stringstyle = {\ttfamily},
        showstringspaces = false,
        showtabs = false,
        numbers = left,
        %captionpos = b,
        tabsize = 2
}


%Code definitions
\def\code#1{\small\texttt{#1}}

% Show the title
\maketitle

% Make the title page header/footer empty
\thispagestyle{empty}

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


%======================================================================%
%                       A b s t r a c t                                % 
%======================================================================%
\begin{abstract}
\noindent
This article presents an approach for decreasing the computational time for
converting a \emph{sparse} \code{SpatialObject} to an \code{Image}.
The method is applicable for \code{SpatialObjects} which
occupy less volume than the total output \code{Image} (which occurs
often, especially when using \code{TubeSpatialObjects} to represent vessels).
A new filter \code{MaskedSpatialObjectToImageFilter} is introduced which
dramatically decreases the execution time by creating a mask of relevant 
pixels. 
The mask is computed by calling the conventional \code{SpatialObjectToImageFilter}
at a lower resolution, which is significantly faster for large images.
The mask is then up-sampled to control which areas are further processed.
\\
\\
\keyword{ITK, SpatialObject, Image, convert, fast, time, speed}

\end{abstract}

%======================================================================%
%                     M a i n   M a t t e r                            % 
%======================================================================%
%\tableofcontents

%----------------------------------------------------------------------%
% Section
%----------------------------------------------------------------------%
\section{Introduction}
The ITK \code{SpatialObject} library provides an effective and powerful
mechanism for representing objects as simple geometric models. 
For many applications it is useful to convert an \code{SpatialObject} 
model to an \code{Image}.
Currently the \code{SpatialObjectToImageFilter} can be used in
such occasions, however the computational time for conversion 
of large images ($> 256 \times 256 \times 256$ pixels) can be very long.

This article introduces a new filter \code{MaskedSpatialObjectToImageFilter}
which uses a mask to decrease the time spent converting \emph{sparse}
\code{SpatialObjects}. By `sparse' I mean \code{SpatialObjects} which
occupy less space than the output \code{Image}.
This situation is common, especially for applications using tubes to
represent vessels.

In this article I briefly discuss the implementation and usage of the new 
filter, and demonstrate the speed increases with a number of `toy' and real 
datasets.

%----------------------------------------------------------------------%
% Section
%----------------------------------------------------------------------%
\section{Implementation}

\subsection{Design}
Currently \code{MaskedSpatialObjectToImageFilter} extends
\code{SpatialObjectToImageFilter} and overrides \code{GenerateData()},
however it may be possible to re-factor 
\code{SpatialObjectToImageFilter::GenerateData()} to allow the sharing of
much of this code.
Some parameters and helper methods have been added to the new filter.

In terms of additional methods, the \code{GenerateMask()} method is the
most interesting. If the user does not provide a mask (as the second input)
this method is responsible for automatic mask generation.
It does this by converting the input \code{SpatialObject} to a low-resolution 
mask. The computation of this low-resolution mask is significantly less than
at full-size. A binary dilation is applied to ensure the low-resolution 
mask covers the required area, and finally the mask is resampled to full-size.

The \code{MaskedSpatialObjectToImageFilter} has two additional parameters:
\begin{description}
	\item[\code{MaskResampleFactor}:] this parameter controls the size of the 
	low-resolution mask.
	The default value is \code{4.0}. Using this default value, for the example 
	of a $512\times512\times512$ output image, the mask will be generated at 
	the smaller size of	$128\times128\times128$ (which takes orders of magnitude 
	less time than the full-size).
	\item[\code{MaskDilationSize}:] this parameter controls the size of the 
	morphological structuring element used to expand the mask image.
	This dilation ensures that the production of the mask at the lower resolution
	does not miss included regions.
	The default value is \code{2}, however this parameter ultimately depends
	of the \code{MaskResampleFactor}.
\end{description}

\subsection{Usage}

Source code for this section can be found in 
\code{Testing/itkMaskedSpatialObjectToImageFilterTests.cxx}.
Using the new filter is almost identical to \code{SpatialObjectToImageFilter}. 
Firstly we must declare the filter type:
\begin{center}
\lstset{language=[ANSI]C++, floatplacement=!htb}	
\lstinputlisting[linerange={68-70}]
	{../Testing/itkMaskedSpatialObjectToImageFilterTests.cxx}
\end{center}

We now read a \code{GroupType SpatialObject}:
\begin{center}
\lstset{language=[ANSI]C++, floatplacement=!htb}	
\lstinputlisting[linerange={75-77}]
	{../Testing/itkMaskedSpatialObjectToImageFilterTests.cxx}
\end{center}

create the filter, plug-in the input \code{SpatialObject}, and setup the various parameters:
\begin{center}
\lstset{language=[ANSI]C++, floatplacement=!htb}	
\lstinputlisting[linerange={80-98}]
	{../Testing/itkMaskedSpatialObjectToImageFilterTests.cxx}
\end{center}

%----------------------------------------------------------------------%
% Section
%----------------------------------------------------------------------%
\section{Results}
To demonstrate the achieved speed increases I have put together two `toy' 
examples and two real examples. The real examples are \code{TubeSpatialObject}
representations of the coronary arteries extracted from multi-slice spiral
computed tomography angiography (MS-CTA) images.
These example files are included with the source
code for this article in the \code{Images} folder.
Maximum intensity projections (MIP) of the example images are shown in 
\figurename~\ref{fig:ImagesMIP}, and the dimensions and spacings 
are listed in
%\tablename~\ref{table:ImagesInfo} and 
\code{Images/Readme.txt}. 

%\begin{table}[!hbt] %placement=h,t,b,p{WIDTH},!
%\begin{center}
%\begin{tabular}{c|c|c} %l,r,c,p{width},|
%\hline
%Data & Dimensions & Spacing\\
%\hline
%Toy1 & [128, 128, 128] & [1.0, 1.0, 1.0] \\
%Toy2 & [256, 256, 256] & [1.0, 1.0, 1.0] \\
%Real1 & [512, 512, 404] & [0.414063, 0.414063, 0.400024] \\
%Real2 & [512, 512, 556] & [0.421875, 0.421875, 0.399994] \\
%\hline
%\end{tabular}
%\caption{Size and spacing information for the provide example images.}
%\label{table:ImagesInfo}
%\end{center}
%\end{table}

\begin{figure}[!htb]
\centering
\subfigure[Toy1]{%
	\includegraphics[height=35mm]{Toy1_MIP.png}}
\hspace{3mm}
\subfigure[Toy2]{%
	\includegraphics[height=35mm]{Toy2_MIP.png}}
\hspace{3mm}
\subfigure[Real1]{%
	\includegraphics[height=35mm]{Real1_MIP.png}}
\hspace{3mm}
\subfigure[Real2]{%
	\includegraphics[height=35mm]{Real2_MIP.png}}
\caption{%
\label{fig:ImagesMIP}%
Maximum intensity projection (MIP) representations of the example images.}
\end{figure}

Each of the four input \code{SpatialObjects} were converted to an
\code{Image} using both the original and masked methods.
These conversions were repeated five times and the mean taken as the 
result.
Unfortunately due to the large times associated with the conversion,
the two real datasets were converted to approximate half-size 
output images (ie. $256 \times 256 \times 256$).
The file \code{Testing/CMakeLists.txt} contains the script used
to generate the results.
The computer specifications on which these tests were run are as follows:
Intel Pentium 4, 2.8GHz dual processors, 1GB RAM, on Windows XP, 
with ITK-2.8.1, compiled using Microsoft Visual Studio .NET 7.1.
\figurename~\ref{fig:Results} depicts the resulting
mean computational times using both approaches.
It can be clearly seen that the new mask-based method is significantly 
faster for large, sparse \code{SpatialObjects} (ie. Toy2, Real1 and Real2).
Even for smaller, less sparse objects (ie. Toy1) the new method is
comparable.


%LastTest.log excerpts -----------------------------
%---------------------------------------------------
%"MaskedSpatialObject_Toy1_1" time elapsed: 00:00:07
%"SpatialObject_Toy1_1" time elapsed: 00:00:08
%"MaskedSpatialObject_Toy2_1" time elapsed: 00:00:14
%"SpatialObject_Toy2_1" time elapsed: 00:02:30
%"MaskedSpatialObject_Real1_1" time elapsed: 00:01:00
%"SpatialObject_Real1_1" time elapsed: 00:16:39
%"MaskedSpatialObject_Real2_1" time elapsed: 00:00:49
%"SpatialObject_Real2_1" time elapsed: 00:18:29
%"MaskedSpatialObject_Toy1_2" time elapsed: 00:00:07
%"SpatialObject_Toy1_2" time elapsed: 00:00:10
%"MaskedSpatialObject_Toy2_2" time elapsed: 00:00:14
%"SpatialObject_Toy2_2" time elapsed: 00:02:31
%"MaskedSpatialObject_Real1_2" time elapsed: 00:00:59
%"SpatialObject_Real1_2" time elapsed: 00:16:57
%"MaskedSpatialObject_Real2_2" time elapsed: 00:00:52
%"SpatialObject_Real2_2" time elapsed: 00:18:31
%"MaskedSpatialObject_Toy1_3" time elapsed: 00:00:07
%"SpatialObject_Toy1_3" time elapsed: 00:00:09
%"MaskedSpatialObject_Toy2_3" time elapsed: 00:00:14
%"SpatialObject_Toy2_3" time elapsed: 00:02:31
%"MaskedSpatialObject_Real1_3" time elapsed: 00:01:00
%"SpatialObject_Real1_3" time elapsed: 00:16:57
%"MaskedSpatialObject_Real2_3" time elapsed: 00:00:47
%"SpatialObject_Real2_3" time elapsed: 00:18:19
%"MaskedSpatialObject_Toy1_4" time elapsed: 00:00:06
%"SpatialObject_Toy1_4" time elapsed: 00:00:08
%"MaskedSpatialObject_Toy2_4" time elapsed: 00:00:14
%"SpatialObject_Toy2_4" time elapsed: 00:02:30
%"MaskedSpatialObject_Real1_4" time elapsed: 00:00:59
%"SpatialObject_Real1_4" time elapsed: 00:16:56
%"MaskedSpatialObject_Real2_4" time elapsed: 00:00:47
%"SpatialObject_Real2_4" time elapsed: 00:18:17
%"MaskedSpatialObject_Toy1_5" time elapsed: 00:00:06
%"SpatialObject_Toy1_5" time elapsed: 00:00:08
%"MaskedSpatialObject_Toy2_5" time elapsed: 00:00:13
%"SpatialObject_Toy2_5" time elapsed: 00:02:30
%"MaskedSpatialObject_Real1_5" time elapsed: 00:01:00
%"SpatialObject_Real1_5" time elapsed: 00:16:45
%"MaskedSpatialObject_Real2_5" time elapsed: 00:00:47
%"SpatialObject_Real2_5" time elapsed: 00:18:15

%Summary -------------------------------------------
%---------------------------------------------------
%Toy1: MaskedSpatialObjectToImageFilter = 00:00:07, 00:00:07, 00:00:07, 00:00:06, 00:00:06
%Toy1: SpatialObjectToImageFilter = 00:00:08, 00:00:10, 00:00:09, 00:00:08, 00:00:08
%
%Toy2: MaskedSpatialObjectToImageFilter = 00:00:14, 00:00:14, 00:00:14, 00:00:14, 00:00:13
%Toy2: SpatialObjectToImageFilter = 00:02:30, 00:02:31, 00:02:31, 00:02:30, 00:02:30
%
%Real1: MaskedSpatialObjectToImageFilter = 00:01:00, 00:00:59, 00:01:00, 00:00:59, 00:01:00
%Real1: SpatialObjectToImageFilter = 00:16:39, 00:16:57, 00:16:57, 00:16:56, 00:16:45
%
%Real2: MaskedSpatialObjectToImageFilter = 00:00:49, 00:00:52, 00:00:47, 00:00:47, 00:00:47
%Real2: SpatialObjectToImageFilter = 00:18:29, 00:18:31, 00:18:19, 00:18:17, 00:18:15

%Results (means) -----------------------------------
%---------------------------------------------------
%Toy1: MaskedSpatialObjectToImageFilter = 6.6 seconds = 0.11 minutes
%Toy1: SpatialObjectToImageFilter = 8.6 seconds = 0.14 minutes
%
%Toy2: MaskedSpatialObjectToImageFilter = 13.8 seconds = 0.23 minutes
%Toy2: SpatialObjectToImageFilter = 2.41 minutes
%
%Real1: MaskedSpatialObjectToImageFilter = 0.993 minutes
%Real1: SpatialObjectToImageFilter = 16:50.8 = 16.846 minutes
%
%Real2: MaskedSpatialObjectToImageFilter = 0.806 minutes
%Real2: SpatialObjectToImageFilter = 18:22.2 = 18.37 minutes


\begin{figure}[!htb]
%---- START PS PICTURE ----%
\begin{pspicture}(-4,-1)(1.5,2.5) %(upper-left-corner)(lower-right-corner)

\newdimen\x
\newdimen\y
\x=0.0cm
\y=0.0cm

%Add numbers
\psframe[fillcolor=colorgridback,fillstyle=solid](0,0)(8,1.5)
\rput(\x,-0.2){0} \advance\x by 2cm
\rput(\x,-0.2){1} \advance\x by 2cm
\rput(\x,-0.2){2} \advance\x by 2cm
\rput(\x,-0.2){3} \advance\x by 2cm
\rput(\x,-0.2){4} \advance\x by 2cm

%Add vertical lines
\multido{\n=2+2}{3}{%
	\psline[linestyle=dashed,linewidth=0.1pt,linecolor=colorgridlines](\n,0.01)(\n,1.49)%
}

%Add legend
\x=7.6cm
\y=2.2cm
\barmainlegend
\rput[rB](7.5,2.25){Original}
\x=7.6cm
\y=1.7cm
\barsublegend
\rput[rB](7.5,1.75){Mask-based}

%Add text
\y=0.85cm
\addbartext{Toy1}
\addbartext{Toy2}

%Add bars
\psset{unit=2.0cm}
\x=0.0cm
\y=0.85cm
\barmain(0.14) \barsub(0.11) \nextbar
\barmain(2.41) \barsub(0.23) \nextbar	

\end{pspicture}
%---- END PS PICTURE ----%

%---- START PS PICTURE ----%
\begin{pspicture}(-4,-1)(1.5,1.5) %(upper-left-corner)(lower-right-corner)

\newdimen\x
\newdimen\y
\x=0.0cm
\y=0.0cm

%Add numbers
\psframe[fillcolor=colorgridback,fillstyle=solid](0,0)(8,1.5)
\rput(\x,-0.2){0}   \advance\x by 2cm
\rput(\x,-0.2){5} \advance\x by 2cm
\rput(\x,-0.2){10} \advance\x by 2cm
\rput(\x,-0.2){15} \advance\x by 2cm
\rput(\x,-0.2){20} \advance\x by 2cm

%Add vertical lines
\multido{\n=2+2}{3}{%
	\psline[linestyle=dashed,linewidth=0.1pt,linecolor=colorgridlines](\n,0.01)(\n,1.49)%
}

%Add x-label
\rput(4,-1){Computational time (minutes)}

%Add text
\x=0.00cm
\y=0.85cm
\addbartext{Real1}
\addbartext{Real2}

%Add bars
\psset{unit=0.4cm}
\x=0.00cm
\y=0.85cm
\barmain(16.846) \barsub(0.993) \nextbar
\barmain(18.37) \barsub(0.806) \nextbar

\end{pspicture} 
%---- END PS PICTURE ----%

\setcounter{figure}{1}
\caption{\label{fig:Results}Experimental results of computational time for some `toy' and real datasets.}

\end{figure}

%----------------------------------------------------------------------%
% Conclusions
%----------------------------------------------------------------------%
\newpage
\section{Conclusions}
This paper presented an approach for decreasing the computation time
for converting an \code{SpatialObject} to an \code{Image}.
The speed increases are realised by only computing the \code{SpatialObject}
value at points within a mask. The mask is generated at a lower resolution
in significantly less time than full-size.
This approach assumes that the overhead for the low-resolution mask generation 
is less than converting the \code{SpatialObject} to the full size output image 
(which is the case for many applications including vascular models).
The speed-ups were demonstrated using a number of toy and real examples.
While only \code{TubeSpatialObject} examples were used, this approach
is applicable to \emph{any} desired \code{SpatialObject} representation.

\end{document}