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