[Insight-developers] Re: [Insight-users] compare speed of dilate and erode in itk, vtk
and matlab
Stephen R. Aylward
aylward@unc.edu
Thu, 01 May 2003 16:00:18 -0400
Depending on the type of data being dilated/eroded...you might want to
look at
BasicFilters/itkErodeObjectMorphologyImageFilter
It runs quite a bit (I think over an order of magntitude) faster than
itkBinaryErodeImageFilter
The former assumes that the background has a constant intensity value.
The latter is really for images with varying background intensities.
I think I posted the speed differences about a year ago...
Stephen
Miller, James V (Research) wrote:
> 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
>>
>
> _______________________________________________
> Insight-users mailing list
> Insight-users@public.kitware.com
> http://public.kitware.com/mailman/listinfo/insight-users
--
===============================================
Dr. Stephen R. Aylward
Assistant Professor of Radiology
Adjunct Assistant Professor of Computer Science
http://caddlab.rad.unc.edu
aylward@unc.edu
(919) 966-9695