itk::NeighborhoodRange: a new class for efficient modern C++ style iteration

matt.mccormick · April 19, 2018, 4:26pm

Yes, maybe itk::Experimental.

Yes, an Insight Journal article could be first, then some of its contents could be applied in the Software Guide.

Niels_Dekker · April 19, 2018, 5:49pm

@blowekamp, @matt.mccormick Thank you both for this fundamental discussion!

For now I would just like to add some remarks:

My current project at LKEB (Leiden University Medical Center) uses ITK’s implementation of Hough Transform for circle detection. If the range class I’m proposing here cannot be used to improve the performance of itk::HoughTransform2DCirclesImageFilter, I find it harder to justify the hours I’m spending on the range class, here at my work. I hope you understand! So this raises the question: if the range class is placed in an itk::Experimental namespace, can it still be used by other non-Experimental ITK classes?

If it’s really a show-stopper that the current NeighborhoodRange (Patch Set 12) does not use the NeighborhoodAccessor, I think it can be fixed, actually. I do have it working right now, locally at my computer.

Regarding the name of the class, I did carefully choose “NeighborhoodRange”. The term “range” matches the concept of a modern C++ range (Ranges TS) The term “Neighborhood” is essential here as it only iterates over a neighborhood of pixels, not the entire image. And as far as I can see, it has the same meaning within my proposed class as it has with the “traditional” ITK neighborhood iterators. We could name it “ModernNeighborhoodRange”, but then we would have to rename it again in a few years, when it’s not that “modern” anymore. Anyway, I’m not opposed to “ModernNeighborhoodRange”, although I like “NeighborhoodRange” better.

BTW, I think NeighborhoodOffsets.h (which is part of my proposed patch) could be adapted to make use of itk::NeighborhoodAllocator, instead of std::vector, if that would bring the patch closer to the existing ITK Neighborhood family… would you like that?

matt.mccormick · April 19, 2018, 6:15pm

Yes, understood.

Most of the work for a class comes after the initial merge, e.g. making it work across all platforms, following up with bugs, etc. This is why it is important to have good testing and documentation, etc.

Cool!

It at least needs Iterator if it is an iterator and Image if it only applies to images to follow ITK naming conventions.

matt.mccormick · April 19, 2018, 6:23pm

This should not be a problem if it is not part of the non-Experimental API.

Niels_Dekker · April 19, 2018, 11:16pm

Patch Set 13 uses the NeighborhoodAccessor of the image. Please check it out!

Hereby I would like to clarify: The proposed itk::NeigborhoodRange class is not an iterator! It has two iterator types, though:

itk::NeighborhoodRange<TImage>::iterator
itk::NeighborhoodRange<TImage>::const_iterator

So the following line declares a range, not an iterator:

itk::NeighborhoodRange<ImageType> range{ *image, location, offsets };

But of course, you can get iterators from the range, as follows:

itk::NeighborhoodRange<ImageType>::iterator iterator1 = range.begin();
itk::NeighborhoodRange<ImageType>::iterator iterator2 = range.end();
itk::NeighborhoodRange<ImageType>::const_iterator iterator3 = range.cbegin();
itk::NeighborhoodRange<ImageType>::const_iterator iterator4 = range.cend();

So personally I still think the name of the class is correct. But certainly, placing the class in an Experimental namespace sounds like a good idea. I guess that would make it easier to change the name of the class after the first release, just in case we might regret the initial class name…

matt.mccormick · April 20, 2018, 12:56pm

So we are defining a new concept, here, Range, instead of Iterator, which makes sense.

The name should have Image in it, though, i.e. ImageNeighborhoodRange.

Niels_Dekker · April 20, 2018, 1:42pm

Thanks, Matt!

ImageNeighborhoodRange is OK to me, but still I like NeighborhoodRange better.

Can you please explain why you think the range class I’m proposing here should have Image in its name, while the classic ITK Neighborhood classes don’t have it? Seriously, the old itk::NeighborhoodIterator also just iterates on an image.

matt.mccormick · April 20, 2018, 2:02pm

As explained in the Software Guide, consistency is important.

The naming convention specifies

  class name = <algorithm><input><concept>

Where <input> here is ImageNeighborhood and <concept> is Range. Or, perhaps it should be NeighborhoodImageIterator we do not consider Neighborhood as <input>.

Since this is a departure from how Neighborhood is used within the rest of the toolkit, the differences and distinction should be clearly noted in the documentation.

According to the naming convention, itk::NeighborhoodIterator should have Image in the name, which would make it easier to identify and find with all the other iterators that operator on Image:

class  	itk::ImageConstIterator< TImage >
 
class  	itk::ImageConstIteratorWithIndex< TImage >
 
class  	itk::ImageConstIteratorWithOnlyIndex< TImage >
 
class  	itk::ImageIterator< TImage >
 
class  	itk::ImageIteratorWithIndex< TImage >
 
class  	itk::ImageLinearConstIteratorWithIndex< TImage >
 
class  	itk::ImageLinearIteratorWithIndex< TImage >
 
class  	itk::ImageRandomConstIteratorWithIndex< TImage >
 
class  	itk::ImageRandomConstIteratorWithOnlyIndex< TImage >
 
class  	itk::ImageRandomIteratorWithIndex< TImage >
 
class  	itk::ImageRandomNonRepeatingConstIteratorWithIndex< TImage >
 
class  	itk::ImageRandomNonRepeatingIteratorWithIndex< TImage >
 
class  	itk::ImageRegionConstIterator< TImage >
 
class  	itk::ImageRegionConstIteratorWithIndex< TImage >
 
class  	itk::ImageRegionConstIteratorWithOnlyIndex< TImage >
 
class  	itk::ImageRegionExclusionConstIteratorWithIndex< TImage >
 
class  	itk::ImageRegionExclusionIteratorWithIndex< TImage >
 
class  	itk::ImageRegionIterator< TImage >
 
class  	itk::ImageRegionIteratorWithIndex< TImage >
 
class  	itk::ImageRegionReverseConstIterator< TImage >
 
class  	itk::ImageRegionReverseIterator< TImage >
 
class  	itk::ImageReverseConstIterator< TImage >
 
class  	itk::ImageReverseIterator< TImage >
 
class  	itk::ImageScanlineConstIterator< TImage >
 
class  	itk::ImageScanlineIterator< TImage >
 
class  	itk::ImageSliceConstIteratorWithIndex< TImage >
 
class  	itk::ImageSliceIteratorWithIndex< TImage >

In the future, hopefully there will be other Range classes that operate on other data structures like PointSet’s, etc. By following the ITK naming convention, these can have meaningful names that are easy to understand.

blowekamp · April 20, 2018, 5:31pm

This class is similar to itk::ShapedNeightborhoodIterator in that they both take in a set of offsets to a Neighborhood to iterate over. Also in ITK a Neighborhood is just a hyper-rectangular region defined by a radius.

I urge the “ShapedNeighborhood” be part of the name. Following Matt’s ambitions for "Range"s for other types. I suggest the following name: ImageShapedNeighborhoodRange and adding a Doxygen \see link to ShapedNeighborhoodIterator.

dzenanz · April 20, 2018, 5:59pm

My opinion was to not be overly ambitions right away, and while the class is in itk::experimental namespace it could be named ShapedNeighborhoodRange. If the other *Range classes are added it could then be renamed to ImageShapedNeighborhoodRange to disambiguate it from e.g. PointSetShapedNeighborhoodRange or ImageRange.

Niels_Dekker · April 20, 2018, 10:50pm

Here is just some example code to show the similarity between itk::ShapedNeightborhoodIterator and the neighborhood range class, as mentioned by @blowekamp

This is how NeighborhoodRange could be used for a diagonal neighborhood shape:

const std::vector<itk::Offset<>> offsets = { {-1, -1}, {0, 0}, {1, 1} };
itk::ImageRegionIteratorWithIndex<ImageType> imageRegionIterator{image, imageRegion};

while (!imageRegionIterator.IsAtEnd())
{
  const itk::Index<> location = imageRegionIterator.GetIndex();
  itk::Experimental::NeighborhoodRange<ImageType> range{*image, location, offsets};

  for (PixelType neigborhoodPixel : range)
  {
    std::cout << neigborhoodPixel << ' ';
  }
  ++imageRegionIterator;
}

And this is the equivalent, using the classic itk::ShapedNeighborhoodIterator:

const std::vector<itk::Offset<>> offsets = { {-1, -1}, {0, 0}, {1, 1} };
itk::ImageRegionIteratorWithIndex<ImageType> imageRegionIterator{image, imageRegion};
const itk::Size<> radius = { { 1, 1 } };

itk::ShapedNeighborhoodIterator<ImageType>
  shapedNeighborhoodIterator{radius, image, imageRegion};

for (const auto offset : offsets)
{
  shapedNeighborhoodIterator.ActivateOffset(offset);
}

while (!imageRegionIterator.IsAtEnd())
{
  const itk::Index<> location = imageRegionIterator.GetIndex();
  shapedNeighborhoodIterator.SetLocation(location);

  for (auto it = shapedNeighborhoodIterator.Begin(); !it.IsAtEnd(); ++it)
  {
    PixelType neigborhoodPixel = it.Get();
    std::cout << neigborhoodPixel << ' ';
  }
  ++imageRegionIterator;
}

Disclaimer: I did not do a KWStyle check But I did test these examples!

HTH, Niels

Niels_Dekker · April 23, 2018, 3:14pm

Update: This morning I submitted Patch Set 19, which can be reviewed, and possibly merged…

itkNeighborhoodRange.h has significant improvements to the reference types, NeighborhoodRange::iterator::reference (the return type of iterator::operator*()), and NeighborhoodRange::const_iterator::reference. Under the hood, these types are proxy types: Patch Set 19 implements them by an internal (private) template class, PixelProxy<VIsConst>. (VIsConst is true for const access to the pixel, and false for non-const access). Both const and non-const PixelProxy now have a private helper object of type PixelProxyHelper<VIsConst>, which communicates with the NeighborhoodAccessor of the image (calling NeighborhoodAccessor.Get(internalPixel) and NeighborhoodAccessor.Set(internalPixel, pixelValue)).

Tests were added to itkNeighborhoodRangeGTest.cxx to check that the reference types behave like real (built-in) C++ reference types (PixelType & and const PixelType &), and to check that a neighborhood iteration on an itk::VectorImage is also supported well.

Please have a look!

Niels_Dekker · April 24, 2018, 9:53am

@matt.mccormick I do appreciate that you care about proper class names. Now the following existing neighborhood related ITK classes deal specifically with images, and still don’t have Image in their identifier. Do you think they should?

NeighborhoodIterator
ConstNeighborhoodIterator
ConstNeighborhoodIteratorWithOnlyIndex

ShapedNeighborhoodIterator
ConstShapedNeighborhoodIterator

NeighborhoodAccessorFunctor
NeighborhoodInnerProduct

LevelSetNeighborhoodExtractor
LevelSetVelocityNeighborhoodExtractor

matt.mccormick · April 24, 2018, 1:45pm

Yes, I think they should have Image in their name. Since there is abundant client code that use these classes, it is difficult and disruptive to change the name now. Hence, all the fuss about the name

Niels_Dekker · April 24, 2018, 5:39pm

[Regarding NeighborhoodIterator, ConstNeighborhoodIterator, ConstNeighborhoodIteratorWithOnlyIndex, ShapedNeighborhoodIterator, ConstShapedNeighborhoodIterator, etc.]

OK, but still I don’t like the name ImageShapedNeighborhoodRange very much I would read it as “image shaped neighborhood range”. Which sounds to me like “heart shaped box”. The Nirvana song, you know? https://www.youtube.com/watch?v=n6P0SitRwy8 But while the box of Nirvana may be heart shaped, the neighborhood certainly isn’t image shaped. You get my point?

What do you think of ShapedImageNeighborhoodRange? It should be read as “shaped image-neighborhood range”: the range class for a shaped image-neighborhood.

matt.mccormick · April 24, 2018, 7:01pm

Good point – it could be perceived as image-shaped.

Agreed, that is even better!

Thanks for making the adjustments. It Smells Like Team Spirit.

Niels_Dekker · April 25, 2018, 2:18pm

I’m preparing another patch set which I’ll try to submit later today. It should include renaming the range class, as we discussed here. Hopefully this will be the final patch set before the merge to the master branch of ITK!

But there’s something I need to tell you… While developing the range class, I was informed by two C++ experts, Anthony Williams and Jonathan Wakely, that the iterators I’m proposing here do not entirely satisfy the iterator requirements as specified by the current C++ Standard! So what does that mean…?

itk::NeighborhoodRange::iterator supports everything you would expect from a bidirectonal iterator: ++it, --it, it++, it--, *it, auto it2{it1}, it2 = it1, it1 == it2, it1 != it2. However, it does not satisfy the following requirements (quoted from the current Working Draft of the C++ Standard):

From section [iterator.requirements.general]:

An iterator i for which the expression (*i).m is well-defined supports the expression i->m with the same semantics as (*i).m.

From section [forward.iterators]:

if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T

itk::NeighborhoodRange::iterator does not have an operator->(), so it does not support it->m. Moreover, itk::NeighborhoodRange::iterator::reference (the return type of iterator::operator*()) is not a real C++ reference type (PixelType &), instead, it’s a proxy class (PixelProxy).

Strictly speaking, that implies that itk::NeighborhoodRange::iterator is not guaranteed to work well as argument to a C++ Standard Library function that requires a standard compliant iterator.

Fortunately itkNeighborhoodRangeGTest.cxx tests such use cases, and they all pass successfully:

std::vector<PixelType>(range.cbegin(), range.cend());
std::reverse_copy(range.begin(), range.end(), stdVector.begin());
std::inner_product(range.begin(), range.end(), range.begin(), 0.0);
std::for_each(range.begin(), range.end(), [](const PixelType&){});

Moreover: some iterators in the C++ Standard Library don’t satisfy these particular requirement either! std::istreambuf_iterator does not have an operator->() (as reported by Jonathan Wakely) And std::vector<bool>::iterator also has a proxy as iterator::reference type.

Even more hopeful: There is a very detailed proposal to get full support for proxy iterators into the C++ Standard Library: Proxy Iterators for the Ranges Extensions by Eric Niebler.

Summary: itk::NeighborhoodRange::iterator (patch set 19) may not yet officially satisfy all iterator requirements from the current C++ Standard, but in practice, it just appears to work well, as argument to an std function. And of course, the other advantages are still there as well: a significant performance improvement, support for multi-threading and support for range-based for loops.

Niels_Dekker · April 26, 2018, 12:03pm

Very happy to see that itk::ShapedImageNeighborhoodRange - the class formerly known as “NeighborhoodRange” - has been merged onto the master! Thanks, Matt!!!

Thanks to you all: @matt.mccormick, @blowekamp, @dzenanz, @phcerdan, @jhlegarreta, @hjmjohnson, @LucH, and Kitware Robot, of course!

matt.mccormick · April 26, 2018, 2:05pm

Thank you, @Niels_Dekker and everyone who helped with the reviews! This is a huge contribution to ITK.

Niels_Dekker · April 28, 2018, 5:34pm

By the way, I found the review process for this patch quite exhausting. You see, it was only accepted after submitting the 21st patch set. While I felt that patch set 7 was already worth a commit. Patch set 7 already worked well enough for its initial use case, in my opinion: improving the performance of GaussianDerivativeImageFunction and HoughTransform2DCirclesImageFilter. OK, it only supported rectangular neighborhoods, but as a first commit, that seemed reasonable to me. Of course, adding custom shape support was a great enhancement, but it could have been added with a separate commit.

With patch set 12, custom shape support was fully implemented, and again, I was hoping that that would justify a commit. However, it was only after another major enhancement, using the NeighborhoodAccessor of the image, that the patch was accepted.

So basically I felt some pressure to keep adding more features to a single commit, which were holding back the merge. While I was afraid that these extra features would only make it harder to get everything reviewed carefully, as the implementation got more complicated, and that it would become too big to get it into ITK 5.0 in time.

I still feel it would have been better to have had three commits, instead of one, for this patch: commit 1 supporting rectangular neighborhoods, commit 2 adding custom shape support, and commit 3 using NeighborhoodAccessor. The intermediate commits might still have been useful to analyze the design decisions afterwards, from the git log. Hope you understand my point!

Anyway, thanks again for having ShapedImageNeighborhoodRange at the master branch! I’m proud that I was able to make this contribution

Kind regards, Niels

P.S. I’m now preparing to add a way to allow a custom border extrapolation (boundary conditions). How much time is still left before the next alpha?