[Insight-users] compare speed of dilate and erode in itk, vtk
and matlab
Miller, James V (Research)
millerjv@crd.ge.com
Thu, 1 May 2003 15:33:43 -0400
I started running the dilate and erode code through Rational Quantify.
I check in some optimizations to the erosion code. I would have expected
the compiler to do these optimizations but oh well. But this will not
account
for all the speed differences.
The dilate code is about twice the speed of the erode code. Most of the
time
in both algorithms is in evaluating ConstNeighborhoodIterator::GetPixel(i)
Half the time of the GetPixel() code is getting stuff on and off the stack.
Of the remaining half, 1/3 of the time is spent evaluating whether
m_NeedToUseBoundaryCondition is true or not. The other 2/3 spent indexing
into the 1D array and returning a value ( return (*(this->operator[](n))) )
We might be able to decrease the time spent putting items on and off the
stack
by reducing the number of local variables. I think it will be hard to make
the "if (!m_NeedToUseBoundaryCondition)" statement run any faster or the
"return (*(this->operator[](n)))" statement run any faster.
The other option is to try to inline the entire method (essentially removing
the function call).
This is my quick and dirty analysis. Gotta run to a meeting.
Jim
> -----Original Message-----
> From: Miller, James V (Research) [mailto:millerjv@crd.ge.com]
> Sent: Thursday, May 01, 2003 1:51 PM
> To: 'Luis Ibanez'; Insight-users@public.kitware.com;
> novalet@yahoo.com.cn
> Subject: RE: [Insight-users] compare speed of dilate and erode in itk,
> vtk and matlab
>
>
> I just dug through the Matlab code as far they will let
> outsiders dig. Matlab implements the opening and closing
> as a sequence of erodes and dilates just like ITK does.
>
>
>
> > -----Original Message-----
> > From: Luis Ibanez [mailto:luis.ibanez@kitware.com]
> > Sent: Thursday, May 01, 2003 11:35 AM
> > To: Insight-users@public.kitware.com; novalet@yahoo.com.cn
> > Subject: [Insight-users] compare speed of dilate and erode
> in itk, vtk
> > and matlab
> >
> >
> > Hi Chen,
> >
> > Thanks for letting us know about the results of
> > your tests. They are quite interesting indeed.
> >
> > 1) About the compiler error in VC6:
> > Did you installed the Service Pack 5 for VC++ ?
> > This is required for building ITK.
> > We are not getting this error in our nightly
> > builds with VC++ 6.0, so it is definetely
> > something with your compiler.
> >
> > 2) If I may summarize the result of the test,
> > when they are comparable the timings are:
> >
> > - Matlab 19 s
> > - VTK 20 s
> > - ITK 56 s
> >
> > Is this right ?
> >
> > This clearly shows that we may have to
> > improve the performance of these filters.
> > Probably creating specialized 3D version
> > could help. Another option is to provide
> > optimal implementations for Openning and
> > Closing, right now this is done by a sequence
> > of erode+dilate, in practice some performance
> > can be improved by doing the opening in a
> > single pass.
> >
> > We will take a look at the options.
> >
> >
> > 3) Just for the record: whenever you need
> > timing of ITK methods, you can take advantage
> > of the TimeProbe and TimeCollector classes:
> >
> > http://www.itk.org/Insight/Doxygen/html/classitk_1_1TimeProbe.html
> > http://www.itk.org/Insight/Doxygen/html/classitk_1_1TimeProbes
> > CollectorBase.html
> >
> > Their use is quite simple and allows to do
> > timing of specific sections of code.
> >
> >
> >
> > Regards,
> >
> >
> > Luis
> >
> >
> > ------------------------------
> > Chen Fu wrote:
> >
> > > Hi Lius,
> > > Yes, i build ITK and my demo in both "Release" option
> > > and "Debug" option in vc6, but not directly select in
> > > CMake.
> > > To my understand, they are the same. BTW, vc6 report a
> > > internal error(should call MS support according to the
> > > error info) when compile release option on
> > > itkDanielssonDistanceMapImageFilter.txx Line 286, i
> > > have to seperate it into two lines to get pass, but in
> > > debug option it is not a problem.
> > > OutputImageType::PixelType p = static_cast<typename
> > > OutputImageType::PixelType>(sqrt( distance ));
> > > dt.Set( p );
> > > I don't know the reason, any idea?
> > >
> > > You are right. The "release" is much quicker than
> > > "debug" option. But compare to matlab, it is still
> > > slower.
> > >
> > > My code list below, it takes itk release option 56
> > > seconds to finish, debug option takes 608 seconds,
> > > while vtk(written in tcl script) cost 20 seconds,
> > > matlab code cost only 1.6 seconds.
> > >
> > > I carefully exam the code and at last find out the
> > > speed of matlab is benefit from computing on really
> > > blackwhite image format which means 8 pixels in one
> > > byte. If i replace "BW = im2bw(Ic, graythresh(Ic));"
> > > with "BW = Ic", matlab will compute in a gray image
> > > mode, that will take 19 seconds to finished.
> > >
> > >>From these tests, i think the morphology operators in
> > > itk deserve more efforts to enhance their performance.
> > > Maybe the pure iterator system is expensive for visit
> > > every pixel. But i am not familiar enough with source
> > > code yet, so can not give any really constructive
> > > suggestion, sorry. These tests are just my exercises
> > > to use itk and vtk.
> > >
> > > matlab code:
> > > ========================================
> > > t0 = clock;
> > > I = imread('d:\nova\pearbig.tif');
> > > Ic = imcomplement(I);
> > > BW = im2bw(Ic, graythresh(Ic));
> > > se = strel('disk', 6);
> > > BWc = imclose(BW, se);
> > > BWco = imopen(BWc, se);
> > > mask = BW & BWco;
> > > etime(clock, t0)
> > > =======================================
> > >
> > > my itk code:
> > > =======================================
> > > // itkTester2.cpp : Defines the entry point for the
> > > console application.
> > > //
> > >
> > > #include "stdafx.h"
> > >
> > > #include "itkImage.h"
> > > #include "itkImageFileReader.h"
> > > #include "itkImageFileWriter.h"
> > > #include "itkBinaryThresholdImageFilter.h"
> > > #include <itkBinaryDilateImageFilter.h>
> > > #include <itkBinaryErodeImageFilter.h>
> > > #include <itkBinaryBallStructuringElement.h>
> > > #include <time.h>
> > >
> > > void itkBinaryThresholdImageFilterTest()
> > > {
> > >
> > > // Use a random image source as input
> > > typedef unsigned char PixelType;
> > > typedef itk::Image< PixelType, 2 > ImageType;
> > > typedef itk::ImageFileReader< ImageType >
> > > ReaderType;
> > > ReaderType::Pointer source = ReaderType::New();
> > > source->SetFileName("d:\\pearbig.png");
> > >
> > > // Declare the type for the binary threshold
> > > binaryThreshold
> > > typedef itk::BinaryThresholdImageFilter< ImageType,
> > > ImageType > FilterType;
> > >
> > >
> > > // Create a binaryThreshold
> > >
> > > FilterType::Pointer binaryThreshold =
> > > FilterType::New();
> > >
> > > // Setup ivars
> > > PixelType lower = 180;
> > > PixelType upper = 255;
> > > binaryThreshold->SetUpperThreshold( upper );
> > > binaryThreshold->SetLowerThreshold( lower );
> > >
> > > PixelType inside = 0;
> > > PixelType outside = 255;
> > > binaryThreshold->SetInsideValue( inside );
> > > binaryThreshold->SetOutsideValue( outside );
> > >
> > > // Connect the input images
> > > binaryThreshold->SetInput( source->GetOutput() );
> > >
> > > // Declare the type for the structuring element
> > > typedef itk::BinaryBallStructuringElement<unsigned
> > > char, 2>
> > > KernelType;
> > > // Create the structuring element
> > > KernelType ball;
> > > KernelType::SizeType ballSize;
> > > ballSize[0] = 5;
> > > ballSize[1] = 5;
> > > ball.SetRadius(ballSize);
> > > ball.CreateStructuringElement();
> > >
> > > // Declare the type for the morphology Filter
> > > typedef itk::BinaryDilateImageFilter<ImageType,
> > > ImageType, KernelType>
> > > BinaryDilateType;
> > > typedef itk::BinaryErodeImageFilter<ImageType,
> > > ImageType, KernelType>
> > > BinaryErodeType;
> > >
> > > //Close = Erode then Dilate
> > > BinaryErodeType::Pointer binaryErode =
> > > BinaryErodeType::New();
> > > binaryErode->SetInput(binaryThreshold->GetOutput() );
> > > binaryErode->SetKernel( ball );
> > > binaryErode->SetErodeValue( 255 );
> > >
> > > BinaryDilateType::Pointer binaryDilate =
> > > BinaryDilateType::New();
> > > binaryDilate->SetInput(binaryErode->GetOutput() );
> > > binaryDilate->SetKernel( ball );
> > > binaryDilate->SetDilateValue( 255 );
> > >
> > > //Open = Dilate then Erode
> > > BinaryDilateType::Pointer binaryDilate2 =
> > > BinaryDilateType::New();
> > > binaryDilate2->SetInput(binaryDilate->GetOutput() );
> > > binaryDilate2->SetKernel( ball );
> > > binaryDilate2->SetDilateValue( 255 );
> > >
> > > BinaryErodeType::Pointer binaryErode2 =
> > > BinaryErodeType::New();
> > > binaryErode2->SetInput(binaryDilate2->GetOutput() );
> > > binaryErode2->SetKernel( ball );
> > > binaryErode2->SetErodeValue( 255 );
> > >
> > > typedef itk::ImageFileWriter< ImageType >
> > > WriterType;
> > > WriterType::Pointer writer = WriterType::New();
> > > writer->SetFileName("d:\\pearlite2.png");
> > > writer->SetInput (binaryErode2->GetOutput() );
> > > writer->Update();
> > > }
> > >
> > >
> > > void main(int argc, char* argv[])
> > > {
> > > clock_t a = clock();
> > > itkBinaryThresholdImageFilterTest();
> > > clock_t b = clock();
> > > printf("time %lf\n", 1.0*(b-a)/CLOCKS_PER_SEC);
> > > }
> > >
> > > ======================================
> > >
> > > vtk tcl script
> > >
> > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > > package require vtk
> > >
> > > vtkPNGReader reader1
> > > reader1 SetFileName d:/pearbig.png
> > >
> > > vtkImageCast cast
> > > cast SetOutputScalarTypeToFloat
> > > cast SetInput [reader1 GetOutput]
> > >
> > > vtkImageThreshold thresh
> > > thresh SetInput [cast GetOutput]
> > > thresh ThresholdByUpper 180
> > > thresh SetInValue 0.0000
> > > thresh SetOutValue 255.0000
> > > thresh ReleaseDataFlagOff
> > >
> > > vtkImageOpenClose3D my_close
> > > my_close SetInput [thresh GetOutput]
> > > my_close SetOpenValue 0.0000
> > > my_close SetCloseValue 255.0000
> > > my_close SetKernelSize 11 11 1
> > > my_close ReleaseDataFlagOff
> > >
> > > vtkImageOpenClose3D my_open
> > > my_open SetInput [my_close GetOutput]
> > > my_open SetOpenValue 255.0000
> > > my_open SetCloseValue 0.0000
> > > my_open SetKernelSize 11 11 1
> > > my_open ReleaseDataFlagOff
> > >
> > > vtkImageToImageStencil imageToStencil
> > > imageToStencil SetInput [my_open GetOutput]
> > > imageToStencil ThresholdBetween 0 127
> > > # silly stuff to increase coverage
> > > #imageToStencil SetUpperThreshold [imageToStencil
> > > GetUpperThreshold]
> > > #imageToStencil SetLowerThreshold [imageToStencil
> > > GetLowerThreshold]
> > >
> > > vtkImageStencil stencil
> > > stencil SetInput [reader1 GetOutput]
> > > stencil SetBackgroundValue 120
> > > stencil ReverseStencilOn
> > > stencil SetStencil [imageToStencil GetOutput]
> > >
> > > vtkPNGWriter writer
> > > writer SetInput [ stencil GetOutput ]
> > > writer SetFileName d:/pearbig2.png
> > > writer Write
> > >
> > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > >
> > > --- Luis Ibanez <luis.ibanez@kitware.com> ???:>
> > >
> >
> > >>Hi Chen,
> > >>
> > >>The ITK implementation of morphology operations
> > >>also decompose the processing of the boundary
> > >>regions. This is done by the SmartNeighborhood
> > >>iterator.
> > >>
> > >>So, the difference in preformance is not due to
> > >>boundary processing.
> > >>
> > >>
> > >>
> > >>About your speed comparison:
> > >>
> > >>1) In what platform are you compiling ITK ?
> > >>
> > >>2) Did you enable the "Release" option in
> > >> CMake when configuring ITK ?
> > >>
> > >> Enabling "Release" will add the flags for
> > >> code optimization, given that most of ITK
> > >> is templated code, there is a dramatic speed
> > >> difference between code compiled for debug
> > >> and code compiled for release.
> > >>
> > >>
> > >>
> > >>Regards,
> > >>
> > >>
> > >> Luis
> > >>
> > >>
> > >>-----------------------
> > >>
> > >>Chen Fu wrote:
> > >>
> >
> > >>>Hi!
> > >>>I recently compare the morphology operation in
> >
> > >>
> > >>vtk,
> > >>
> >
> > >>>itk and matlab. To my surprise, vtk and itk is
> >
> > >>
> > >>much
> > >>
> >
> > >>>slower than matlab.
> > >>>I believe the problem is the boundary processing.
> >
> > >>
> > >>In
> > >>
> >
> > >>>vtk and itk code, every pixel must take 8 compares
> >
> > >>
> > >>to
> > >>
> >
> > >>>confirm whether it is inside the image boundary.
> >
> > >>
> > >>But
> > >>
> >
> > >>>in matlab, the boundary is preprocessed by
> >
> > >>
> > >>extending
> > >>
> >
> > >>>the size of image, so get rid of such compares. I
> >
> > >>
> > >>will
> > >>
> >
> > >>>try to do some modify of itk code to enhance its
> > >>>performance, but i am not very clearly how to do
> > >>>extend the image in itk's pipeline architecture.
> > >>>Maybe somebody can give me some hints?
> > >>>
> > >>>
> > >>>=====
> > >>>Remote Scensing Satellite Ground Station
> > >>>Chinese Academy of Science
> > >>>
> >
> > >>
> > >>
> >
> > >
> > >
> > > =====
> > > Remote Scensing Satellite Ground Station
> > > Chinese Academy of Science
> > >
> > > _________________________________________________________
> >
> > _______________________________________________
> > Insight-users mailing list
> > Insight-users@public.kitware.com
> > http://public.kitware.com/mailman/listinfo/insight-users
> >
> _______________________________________________
> Insight-users mailing list
> Insight-users@public.kitware.com
> http://public.kitware.com/mailman/listinfo/insight-users
>