ImageRange - a range of iterators to the pixels of an image

Engineering
2

This is a monumental, awesome contribution, @Niels_Dekker! :tada: :mountain:

1 Like
3

In the mean time, I had a look at the performance, using ImageRange to copy the pixel data of an itk::Image, and compared it with the good old itk::ImageAlgorithm::Copy (using VS2017 Release):

std::copy(imageRange.cbegin(), imageRange.cend(), std::begin(outputImageRange));

Versus:

itk::ImageAlgorithm::Copy(&inputImage, &outputImage, bufferedRegion, bufferedRegion);

Guess what, the old ImageAlgorithm::Copy ran more than 4 times faster than the equivalent std::copy on the ImageRange iterators! :flushed:

Fortunately, with the pull request that I just submitted, both lines of code will run approximately equally fast, according to my observation :sweat_smile:

1 Like
4

For the record, this is implemented by pull request 295 - PERF: N4BiasFieldCorrectionImageFilter implementation using ImageRange. I observed about 10% performance improvement on an Update() of this filter.

1 Like
5

The ImageAlgorithm::Copy is a good implementation. It was implemented in ITKv4, and it made several filters go nearly 100x faster than the prior implementation. It implements copying arbitrary regions in the images, and takes care to compute the maximum continuous regions between the image, and then calls std::transform or std::copy in a the appropriate chunks. This method was implemented based on the needs and features required for working with itk::Images and their multiple regions (BufferedRegions, RequestedRegion, LargestPossibleRegions). It is used in filters like the PasteImageFilter, SliceBySliceImageFilter, PadImageFilter etc… These filters are in the Grid group, so they move chunks around. Removing most of the features and then making a comparison biases the evaluation.

Are there any problems with the ImageAlgorithm::Copy that motivate an update?

6

Honestly I’m impressed about itk::ImageAlgorithm::Copy. I think it’s a very clever :+1: piece of code! Having seen how well it performs, I’m certainly not suggesting to generally replace existing ImageAlgorithm::Copy calls by std::copy calls on ImageRange iterators.

In general, I would only suggest to convert existing ITK filters to start using ImageRange, when that would yield a significant performance gain. Or when it would yield an obvious style improvement. But only if it would perform at least as good as the original code, of course!

1 Like
7

I like the new interface of the ImageRange iterator as it behaves as expected like a std C++ iterator. This is a very good :+1: thing and hope to see more of it. However, it became apparent yesterday, during the N4 review, the implications of only iterating over the BufferedRegion and how that interacts with the ITK pipeline.

The fact that the pipeline provides no guarantee that the BufferedRegion(s) is equal to the RequestedRegion(s) for a filter’s inputs is quite significant and needs to be fully considered. The implications are that the iterator is not suitable for operating on the input images, in general, because of the lack of guarantee we don’t know what the BufferedRegion is after a parent filter is executed. There are some cases where these implicit assumptions might be appropirate… but that requires further thought.

It would be prudent to add a required argument to the ImageRange, the Region which it iterates on. This would make the current implicit assumption explicit. The exemplar use case would be to just pass the image’s BufferedRegion. Logic should be added so that if the Region parameter does not match the BufferedRegion than an exception would be thrown. This would simplify the N4 filter, up for review, by removing the checks ( they would be now part for the ImageRange constructor), and make the region operated on explicit. For old school ITK developers this is the expected usage, and it makes sense to know the region we are iterating over.

8

Thanks for your ideas on ImageRange, @blowekamp. However, I’m not yet convinced that there should be such region checking and exception throwing within the ImageRange(Image&) constructor. It’s an essential property of ImageRange that it iterates over the entire image buffer. (If necessary, we could rename the class to something like “ImageBufferPixelRange” or “BufferedImageRange”.) Note that ImageRange may also be used outside of the context of an ITK pipeline. For example, when initializing an itk::Image, before its first use.

I’m considering to also add an image region specific class to iterate over pixels. However, such an “ImageRegionRange” would not be as fast as ImageRange.

It seems alright to me that a filter itself explicitly checks the regions or sizes of its input images. It does not seem necessary to me to have these precondition checks “hidden” within the ImageRange objects used by the filter. Right?

Please reconsider my pull request, PERF: N4BiasFieldCorrectionImageFilter implementation using ImageRange. I really think it’s OK now.

9

The use / assumptions / contract of itk::Image's RequestedRegion and BufferedRegion are that

  1. Once is comes time to process the RequestedRegion, it may be smaller than the BufferedRegion. This is common when an input image cannot stream or the filter producing an input image needed to extend the input’s BufferedRegion.
  2. The BufferedRegion fully contains the RequestedRegion.

As a consequence, the ImageRange class or an alternative class should support operating on a RequestedRegion that is smaller than the BufferedRegion. Also, it is not necessary to check that the RequestedRegion is inside the BufferedRegion when iterating over it. The filters make sure that this is true, and if an image is constructed outside of a filter, the author is required to ensure this is true, just like they are required to call Allocate() if necessary. Excessive checks that hurt performance or make the API more confusing should be avoided.

1 Like
10

Thanks for your feedback, @matt.mccormick

I can imagine having two image range types:

  • BufferedImageRange<TImage>: the fastest way to iterate over the entire buffer of an itk::Image (as currently implemented by Experimental::ImageRange<TImage>)
  • RequestedImageRange<TImage>: iterating within the RequestedRegion of the specified image.

They could be constructed the same way, just passing an image as parameter:

  BufferedImageRange<TImage> bufferedImageRange{*image}; 
  RequestedImageRange<TImage> requestedImageRange{*image};

Clearly, the BufferedImageRange would use the BufferedRegion, and the RequestedImageRange would use the RequestedRegion of the image. Do you agree? Or do you think it would still be useful to add a region parameter? Is it useful to support specifying an arbitrary region, that is not one of these two?

11

Well stated.

There is a check in the base ImageConstIterator class that ensures the region to iterate on is contained in the BufferedRegion. This is a simple check that is usually done once during construction, and not per-pixel, so it has negligible impact on performance. This checks has been very useful which saves time and effort in writing, running and debugging pipelines or filters. The ImageRange or ImageBufferedRegionRange needs a similar check for the expected region being equal to the buffered.

Unexpected issues happened when there are multiple input and/or image grid and region manipulation explicitly stating the region being iterated on and checking that will occur will benefit both developers of filters and pipelines as well as when the ImageRange is use directly. It will help the class be easy to use and have wider adoption, while improving the reliability of the toolkit.

Currently, you specify the region an iterator works on with the conventional ImageRegionIterators. This works quite well both in the pipeline and outside. Only being able to iterate on requested or buffered regions will not generally work inside the pipelines, and would miss the flexibility needed to be widely used.

I understand that the current ImageRange was implemented to be very efficient and it has achieved that goal inpart by only being able to iterated on the BufferedRegion. This class needs to be:

  • renamed to something like ImageBufferedRegionRange
  • an argument added to the constructor to ensure the expected region is actually the buffered region being iterated on so that it is safe and clear what is being iterated over.

There is also a need for a general ImageRegionRange iterator to operate on an arbitrary region.

1 Like
12

Thank you guys, for discussing this issue so extensively.

In my opinion, this specific range should just provide an elegant and generic interface to the pixel buffer as a whole:

  • Offering access though the external PixelType of the image, rather than the InternalPixelType
  • Supporting the modern C++ range interface

I think there should be another image range type that specifically iterates within a specified region (working title “ImageRegionRange”). I think I can submit a WIP version quite soon.

And yes, I would like rename this ImageRange, to ImageBufferRange. Would you like that too?

13

A internal check that is performed once in the constructor of the range is reasonable.

Yes! And this class is extremely awesome, BTW!

:+1: Sounds great!

14

Here is sample usage I see:

const InputImageType * inputImage = this->GetInput();
const MaskImageType *const maskImage = GetMaskImage();

RegionType inputRegion = inputImage->GetBufferedRegion();

const auto imageRange = MakeImageRange(inputImage, inputRegion);
const auto maskImageRange = MakeImageRange(maskImage, inputRegion);

When using multiple ImageRange is make since to specify what region we are intending to iterate on, and check that they are consistent with the BufferedRegion.

15

Thanks for your encouraging reply, @matt.mccormick

Thanks, @blowekamp I understand your intention. Although personally I still think this region checking could be done more explicitly within the filter itself, before creating the ranges. Anyway, it’s clear how you would like to have it.

But then, I would like to support other use cases as well, with just a single image. For example, like this:

  for(auto&& pixel: MakeImageBufferRange(this->GetImage()) )
  {
      pixel = 42;
  }

For such use cases, I would not want to require an extra ImageRegion parameter. Users would then just do:

  for(auto&& pixel:
    MakeImageBufferRange(this->GetImage(), this->GetImage()->GetBufferedRegion()) )
    ...

Internally, ImageBufferRange would then just check if image->GetBufferedRegion() == image->GetBufferedRegion(), for one and the same image. That would not make any sense to me.

As a compromise, could it be acceptable to you to have an optional rather than an obligatory ImageRegion parameter?

1 Like
16

I would propose the following more compact style:

auto itkImage = this->GetImage();
for( auto && pixel: MakeImageBufferRange(itkImage, itkImage->GetBufferedRegion()))
...

That looks like the right amount of verbosity to me. ITK has traditionally been over verbose or long in the required typedefs, variable names etc. The burden of writing is only once, but it is read likely hundreds of time so a little verbosity to make what the region being operated on clear ( to those who may not have seen this new iterative before) is well worth the effort.

17

I’m sorry Bradley, but I’m not convinced. Internally, MakeImageBufferRange(itkImage, itkImage->GetBufferedRegion()) would just check if itkImage->GetBufferedRegion() is equal to itself (!), which looks completely unnecessary to me.

Moreover, it would be a pity to me if MakeImageBufferRange would no longer support passing a nullptr as Image-pointer argument of MakeImageBufferRange. Currently MakeImageBufferRange returns an empty range, in that case. For example at itkN4BiasFieldCorrectionImageFilter.hxx#L278:

const auto maskImageBufferRange = MakeImageBufferRange(this->GetMaskImage());

In this case, this->GetMaskImage() may return nullptr, and if that’s the case, you cannot easily pass maskImage->GetBufferedRegion() as second argument.

Would you like it if I rename the current MakeImageBufferRange(TImage*) to something like “MakeImageBufferRangeForBufferedRegion(TImage*)”? Would that make things clearer to you (or anyone else)?

Of course you may still add another (an extra) Make function that does perform BufferedRegion checking… what do you think?

18

+1

19

Update: I have finally finalized my ImageRegionRange pull request, and it has just been merged onto the master branch, by @hjmjohnson :

Thanks for your comments @dzenanz, @blowekamp !

I hope it can be included with ITK 5.1.0!

2 Likes
20

@Niels_Dekker Thank you for your contributions! Your careful considerations and extraordinary efforts are very much appreciated.

Please keep up the great work.

Hans

2 Likes
21

For the record, ImageRegionRange has been included with ITK 5.1 Beta 1:

1 Like