[Insight-users] FloodFilledImageFunctionConditionalIterator: Losing efficiency (GCC 3.3)

[Frederic Perez]

Hello Insight-users,

I'm (still) using the GCC 3.3.3 compiler in a Cygwin environment, and I have
identified another performance problem (ITK 2.0.0 slower than ITK 1.8.1).
Concretely, the operator++ of itk::FloodFilledImageFunctionConditionalIterator
or itk::FloodFilledImageFunctionConditionalConstIterator objects seem to slow
down significantly the computation time in some of my applications. A 
version reduced to the minimum of the algorithm exhibiting the problem 
is given below. Linking it to "Release" versions of the toolkit for the 1.8.1
and 2.0.0 official releases we obtain:

  % OwnItk181Apps-binary-release/TestFloodFill/testfloodfill.exe 100
  'Corner' flood-fill starts... finished. [ T.: 0.89 s ]
  % OwnItk200Apps-binary-release/TestFloodFill/testfloodfill.exe 100
  'Corner' flood-fill starts... finished. [ T.: 8.313 s ]

That is, the 2.0.0 version takes 8.3 seconds while the 1.8.1 version 
lasts less than a second.

Browsing the corresponding code I reached the 
Code/Common/itkFloodFilledImageFunctionConditionalConstIterator.txx 
which seems to include the core of the problem. The inspector
IsPixelIncluded was changed between revisions 1.2 and 1.3 to account
for GCC 3.4 issues:

  Revision 1.2: return m_Function->EvaluateAtIndex(index);
  Revision 1.3: return this->GetFunction()->EvaluateAtIndex(index);

GetFunction is a inspector defined as a virtual function returning a 
SmartPointer. It returns m_Function, which happens to be a protected 
member. I didn't know how to accelerate this but by changing the line
again to a Revision 1.2-like form (i.e. avoiding the GetFunction call):

  return this->m_Function->EvaluateAtIndex(index);
  
After this change and relinking the test program, timings went down 
from 8.3 seconds to 0.9 seconds. Maybe there is a better way to fix
the problem, though.


As a final note, I'd like to use the latest ITK's official release, but 
I fear that other performance bugs can bite me in the future while using 
the toolkit. I wonder whether updating my GCC compiler to 3.4 I can 
"get rid" of these performance problems.


Thanks for your consideration,

Frederic Perez

----------

Self-contained test which creates a simple image and iterates through 
it by means of a FloodFilledImageFunctionConditionalIterator iterator.
The program expects as a parameter the 'size' of the image.

#include "itkImage.h"
#include "itkImageRegionIterator.h"
#include "itkBinaryThresholdImageFunction.h"
#include "itkFloodFilledImageFunctionConditionalIterator.h"
#include "itkTimeProbe.h"

int
main( int argc, char ** argv )
{
  //  Creating an image
  
  typedef short PixelType;
  typedef itk::Image< PixelType,  3 > ImageType;
  ImageType::Pointer image = ImageType::New();
  ImageType::IndexType start;
  start[0] = start[1] = start[2] = 0;;
  ImageType::SizeType size;
  size[0] = size[1] = size[2] = atoi( argv[1] );
  ImageType::RegionType region(start, size);
  image->SetRegions( region );
  image->Allocate();
  itk::ImageRegionIterator< ImageType > it1( image, region);
  for (it1.GoToBegin(); !it1.IsAtEnd(); ++it1)
    it1.Set( -500 );

  //  'Corner' flood-fill

  std::cout << "'Corner' flood-fill starts..." << std::flush;
  itk::TimeProbe clock;
  clock.Start();
  
  typedef itk::BinaryThresholdImageFunction<ImageType> FunctionType;
  FunctionType::Pointer function = FunctionType::New();
  function->SetInputImage ( image );
  function->ThresholdBetween( -1000, -200 ); // ( <lower>, <upper> )

  ImageType::IndexType seed;
  seed[0] = seed[1] = seed[2] = 0;
  
  typedef itk::FloodFilledImageFunctionConditionalIterator< // or ConstIterator
    ImageType,
    FunctionType > IteratorType;
  IteratorType it( image, function, seed );
  it.GoToBegin();
  while (!it.IsAtEnd())
    ++it; // <--- Performance problem here (ITK 2.0.0, GCC 3.3.3)
  
  clock.Stop();
  std::cout << " finished. [ T.: " << clock.GetMeanTime() << " s ]" <<
std::endl;
  return 0;
}