# itk::NeighborhoodRange: a new class for efficient modern C++ style iteration
**URL:** https://discourse.itk.org/t/itk-neighborhoodrange-a-new-class-for-efficient-modern-c-style-iteration/833
**Category:** Engineering
**Created:** [April 10, 2018, 7:37pm UTC](https://discourse.itk.org/t/itk-neighborhoodrange-a-new-class-for-efficient-modern-c-style-iteration/833 "2018-04-10T19:37:56Z")
**Posts on this page:** 20
**Page:** 2
> [@blowekamp](#):
>
> Perhaps it should be in a sub-namespace of itk to help indicate that then.
Yes, maybe `itk::Experimental`.
> [@blowekamp](#):
>
> As being experimental, I am not sure the ITK Software Guide is the place for things that have not stabilized and may need to be changed in the future.
Yes, an Insight Journal article could be first, then some of its contents could be applied in the Software Guide.
---
@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)](http://www.lkeb.nl) 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](http://review.source.kitware.com/#/c/23326/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](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4685.pdf)) 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](http://review.source.kitware.com/#/c/23326/12/Modules/Core/Common/include/itkNeighborhoodOffsets.h) (which is part of my proposed patch) could be adapted to make use of [itk::NeighborhoodAllocator](https://itk.org/Doxygen/html/classitk_1_1NeighborhoodAllocator.html), instead of std::vector, if that would bring the patch closer to the existing ITK Neighborhood family… would you like that?
---
> [@Niels\_Dekker](#):
>
> I find it harder to justify the hours I’m spending on the range class, here at my work. I hope you understand!
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.
> [@Niels\_Dekker](#):
>
> 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.
Cool!
> [@Niels\_Dekker](#):
>
> Anyway, I’m not opposed to “ModernNeighborhoodRange”, although I like “NeighborhoodRange” better.
It at least needs _Iterator_ if it is an iterator and _Image_ if it only applies to images to follow [ITK naming conventions](https://itk.org/ITKSoftwareGuide/html/Book1/ITKSoftwareGuide-Book1ch13.html#x57-275000C.6).
---
> [@Niels\_Dekker](#):
>
> 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?
This should not be a problem if it is not part of the non-Experimental API.
---
> [@matt.mccormick](#):
>
> Cool!
😃 [Patch Set 13](http://review.source.kitware.com/#/c/23326/13) uses the NeighborhoodAccessor of the image. Please check it out!
> [@matt.mccormick](#):
>
> It at least needs Iterator if it is an iterator and Image if it only applies to images to follow ITK naming conventions
Hereby I would like to clarify: The proposed itk::NeigborhoodRange class is _ **not** _ an iterator! It has two iterator types, though:
```
itk::NeighborhoodRange::iterator
itk::NeighborhoodRange::const_iterator
```
So the following line declares a _range_, not an iterator:
```
itk::NeighborhoodRange range{ *image, location, offsets };
```
But of course, you can get iterators _from_ the range, as follows:
```
itk::NeighborhoodRange::iterator iterator1 = range.begin();
itk::NeighborhoodRange::iterator iterator2 = range.end();
itk::NeighborhoodRange::const_iterator iterator3 = range.cbegin();
itk::NeighborhoodRange::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… 🙂
---
> [@Niels\_Dekker](#):
>
> But of course, you can get iterators from the range, as follows:
>
> itk::NeighborhoodRange\::iterator iterator1 = range.begin();
> itk::NeighborhoodRange\::iterator iterator2 = range.end();
> itk::NeighborhoodRange\::const\_iterator iterator3 = range.cbegin();
> itk::NeighborhoodRange\::const\_iterator iterator4 = range.cend();
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_.
---
> [@matt.mccormick](#):
>
> So we are defining a new concept, here, Range, instead of Iterator, which makes sense.
Thanks, Matt! 🙂
> [@matt.mccormick](#):
>
> The name should have Image in it, though, i.e. ImageNeighborhoodRange.
_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.
---
As [explained in the Software Guide](https://itk.org/ITKSoftwareGuide/html/Book1/ITKSoftwareGuide-Book1ch13.html#x57-262000C.3), consistency is important.
The [naming convention](https://itk.org/ITKSoftwareGuide/html/Book1/ITKSoftwareGuide-Book1ch13.html#x57-275000C.6) specifies
```auto
class name =
```
Where `` here is `ImageNeighborhood` and `` is `Range`. Or, perhaps it should be _NeighborhoodImageIterator_ we do not consider _Neighborhood_ as ``.
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.
> [@Niels\_Dekker](#):
>
> 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?
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_](https://itk.org/Doxygen/html/group__ImageIterators.html):
```auto
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.
---
This class is similar to [itk::ShapedNeightborhoodIterator](https://itk.org/Doxygen/html/classitk_1_1ShapedNeighborhoodIterator.html) in that they both take in a set of offsets to a Neighborhood to iterate over. Also in ITK a [Neighborhood](https://itk.org/Doxygen/html/classitk_1_1Neighborhood.html) 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](https://www.stack.nl/~dimitri/doxygen/manual/commands.html#cmdsee) link to ShapedNeighborhoodIterator.
---
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`.
---
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> offsets = { {-1, -1}, {0, 0}, {1, 1} };
itk::ImageRegionIteratorWithIndex imageRegionIterator{image, imageRegion};
while (!imageRegionIterator.IsAtEnd())
{
const itk::Index<> location = imageRegionIterator.GetIndex();
itk::Experimental::NeighborhoodRange 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> offsets = { {-1, -1}, {0, 0}, {1, 1} };
itk::ImageRegionIteratorWithIndex imageRegionIterator{image, imageRegion};
const itk::Size<> radius = { { 1, 1 } };
itk::ShapedNeighborhoodIterator
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
---
Update: This morning I submitted [Patch Set 19](http://review.source.kitware.com/#/c/23326/19), which can be reviewed, and possibly merged…
[itkNeighborhoodRange.h](http://review.source.kitware.com/#/c/23326/19/Modules/Core/Common/include/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` 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`, which communicates with the NeighborhoodAccessor of the image (calling `NeighborhoodAccessor.Get(internalPixel)` and `NeighborhoodAccessor.Set(internalPixel, pixelValue)`).
Tests were added to [itkNeighborhoodRangeGTest.cxx](http://review.source.kitware.com/#/c/23326/19/Modules/Core/Common/test/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!
---
@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
```
---
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 😉
---
[Regarding _NeighborhoodIterator, ConstNeighborhoodIterator, ConstNeighborhoodIteratorWithOnlyIndex, ShapedNeighborhoodIterator, ConstShapedNeighborhoodIterator_, etc.]
> [@matt.mccormick](#):
>
> Yes, I think they should have Image in their name.
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](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.
---
> [@Niels\_Dekker](#):
>
> 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](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?
Good point – it could be perceived as _image-shaped_. 🎸 ☀
> [@Niels\_Dekker](#):
>
> What do you think of ShapedImageNeighborhoodRange? It should be read as “shaped image-neighborhood range”: the range class for a shaped image-neighborhood.
Agreed, that is even better!
Thanks for making the adjustments. It Smells Like Team Spirit. 🤘
---
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](https://github.com/anthonywilliams) and [Jonathan Wakely](https://github.com/jwakely), 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](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/n4741.pdf)):
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(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](https://cplusplus.github.io/LWG/issue2790) by Jonathan Wakely) And `std::vector::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](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0022r2.html) by [Eric Niebler](https://github.com/ericniebler).
Summary: `itk::NeighborhoodRange::iterator` ([patch set 19](http://review.source.kitware.com/#/c/23326/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_. 😃
---
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!
---
By the way, I found the review process for [this patch](http://review.source.kitware.com/#/c/23326/) quite exhausting. You see, it was only accepted after submitting [the 21st patch set](http://review.source.kitware.com/#/c/23326/21). While I felt that [patch set 7](http://review.source.kitware.com/#/c/23326/7) was already worth a commit. [Patch set 7](http://review.source.kitware.com/#/c/23326/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](http://review.source.kitware.com/#/c/23326/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](https://github.com/Kitware/ITK/commit/b88462a4b927db9ccc3e88816e0a821c3be17d4f). 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?
[Previous page](https://discourse.itk.org/t/itk-neighborhoodrange-a-new-class-for-efficient-modern-c-style-iteration/833.md?page=1)
[Next page](https://discourse.itk.org/t/itk-neighborhoodrange-a-new-class-for-efficient-modern-c-style-iteration/833.md?page=3)