A shape class for ShapedImageNeighborhoodRange and ShapedNeighborhoodIterator

Engineering
1

Hereby I would like to share my ideas behind the proposed patch ENH: Added class to create offsets for a hyperrectangular neighborhood shape

Both the new ShapedImageNeighborhoodRange (from namespace itk::Experimental) and the original itk::ShapedNeighborhoodIterator allow specifying the shape of a neighborhood by means of offsets (objects of type itk::Offset<N>). Unfortunately, it can be somewhat cumbersome for users to specify the values of such offsets, depending on the preferred shape. I think it would be nice if ITK could have some classes for commonly used neighborhood shapes. Each class would allow generating the offsets for that particular shape. If possible, they might all have a similar interface, like this:

template <unsigned int VImageDimension>
class ExampleImageNeighborhoodShape
{
public:
  static constexpr unsigned int ImageDimension = VImageDimension;
  constexpr explicit ExampleImageNeighborhoodShape(...) noexcept;
  constexpr std::size_t GetNumberOfOffsets() const noexcept;
  void FillOffsets(itk::Offset<ImageDimension>*) const noexcept;
};

Not surprisingly, that’s also basically the interface of the HyperrectangularImageNeighborhoodShape<ImageDimension> class, which is part of the proposed patch. This class specifically supports generating the offsets for box-shaped neighborhoods. It can be constructed as follows, for example:

constexpr itk::Size<ImageDimension> radius = {{ 1, 2 }};  // For example.
constexpr HyperrectangularImageNeighborhoodShape<ImageDimension> shape{radius};

The offsets can then be generated as follows:

std::array<OffsetType, shape.GetNumberOfOffsets()> offsets;
shape.FillOffsets(offsets.data());

Or by using the proposed convenience function GenerateImageNeighborhoodOffsets (also added to namespace itk::Experimental):

std::vector<OffsetType> offsets = GenerateImageNeighborhoodOffsets(shape);

The offsets can then be used to specify the shape for the original itk::ShapedNeighborhoodIterator:

ShapedNeighborhoodIterator<ImageType> neighborhoodIterator{radius, image, region};

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

As well as to specify the shape for the new itk::Experimental::ShapedImageNeighborhoodRange:

ShapedImageNeighborhoodRange<ImageType> neighborhoodRange{*image, location, offsets};

Please have a look: http://review.source.kitware.com/#/c/23389

P.S. The patch does not yet present any other shapes, but @phcerdan already suggested another one, that we are still discussing at itk::NeighborhoodRange: a new class for efficient modern C++ style iteration

2

Thanks @dzenanz for merging the patch, ENH: Added class to create offsets for a hyperrectangular neighborhood shape!

I think this could pave the way for the topological connectivity shape class, that Pablo and I have been discussing at itk::NeighborhoodRange: a new class for efficient modern C++ style iteration

This class should support generating the offsets for N-connected neighborhoods: 4- and 8-connected neighborhoods in 2-D, 6-, 18-, and 26-connected neighborhoods in 3-D, etc.

@phcerdan Would it be OK to you if I would simply name the shape class ConnectedImageNeighborhoodShape, with the initial patch set? I find something like “TopologicalConnectivityImageNeighborhoodShape” a bit too verbose. And I think it’s basically just a connected neighborhood: a neighborhood of pixels that are connected to one specific center pixel. What do you think?

3

It sounds ok to me! Thanks Niels.

1 Like
4

@phcerdan Thanks for your initial review of itk::Experimental::ConnectedImageNeighborhoodShape, while it was still in WIP state (work in progress). I think it’s fully functional now, and correctly implemented. However, I wonder if an extra parameter would be needed, to optionally include the center pixel. What do you think? Would you use it? Or would you always choose to exclude the center pixel anyway?

5

I think you mostly want center pixel. The option to exclude it seems fine to me.

6

If the user wants the center pixel, the existing HyperrectangularImageNeighborhoodShape can be used. I wouldn’t add extra complexity to the class.

The purpose of this class, at least in my mind, is to visit neighbors assuming the center pixel is occupied, for example in Label or Binary images.

But of course, if you think it is worth, I can be convinced!

7

Thanks for your feedback, @dzenanz and @phcerdan

Yes I do believe that it could be useful to (optionally) include the center pixel. The shape would then still be different from the existing HyperrectangularImageNeighborhoodShape, at least when maximumDistance < ImageDimension. For example, a 4-connected neighborhood is not rectangular. (Or at least, it is not supported by HyperrectangularImageNeighborhoodShape.)

For erosion or dilation, I think you would want to include the center pixel.

Pablo, I can certainly imagine that that’s an interesting use case. Still I’m curious, do you have a specific filter of morphological operation in mind?

8

Good question! I have an incomplete picture in my mind to categorize pixels/voxels based on the occupancy configuration of its nearest neighbors. I see ConnectedImageNeighborhoodShape as a way to select the adjacency relationship of the pixel, -4 or 8- in 2D, -6 or 18 or 26- in 3D.

For each adjacency relationship, we can query each spel (i.e. pixel or voxel) for properties like: IsConnected, IsSimple (i.e does the removal of the spel changes the topology of the original object?), isEndPoint, isBranchPoint, IsIsthmus, etc. These properties depend on the adjacency relationship, and the neighborhood occupancy.

And I think you are right @dzenanz , the center pixel is useful if we are talking about adjacency because any pixel is adjacent to itself. Convinced! :smiley:

1 Like
9

Update: Yesterday I added a boolean includeCenterPixel parameter to the explicit ConnectedImageNeighborhoodShape constructor. To be used as follows (for example):

bool includeCenterPixel = true;
std::size_t maximumDistance = 2;
constexpr unsigned int dimension = 3;
ConnectedImageNeighborhoodShape<dimension> shape{maximumDistance,includeCenterPixel};
std::vector<Offset<dimension>> offsets = GenerateImageNeighborhoodOffsets(shape);

Please review: ENH: Added ConnectedImageNeighborhoodShape, for N-connected neighborhoods Kitware Build Robot gave it a +1 already. :smiley:

1 Like
10

Very glad to see that ConnectedImageNeighborhoodShape now has +1 from Dzenan (@dzenanz), Pablo (@phcerdan), and the Build Robot. :smiley: Now I just noticed that a subset of the functionality of ConnectedImageNeighborhoodShape is already there, from the existing function itk::setConnectivity(it, fullyConnected):

Just for your information, here is how itk::setConnectivity(it, fullyConnected) could have been implemented by using ConnectedImageNeighborhoodShape:

template< typename TIterator >
TIterator *
setConnectivity(TIterator *it, bool fullyConnected = false)
{
  using ShapeType =
    Experimental::ConnectedImageNeighborhoodShape<TIterator::Dimension>;
  const bool includeCenterPixel = false;
  const std::size_t maximumCityblockDistance = fullyConnected ? SIZE_MAX : 1;
  const ShapeType shape{ maximumCityblockDistance, includeCenterPixel };

  it->ClearActiveList();

  for (const auto& offset : Experimental::GenerateImageNeighborhoodOffsets(shape))
  {
    it->ActivateOffset(offset);
  }
  return it;
}

Fortunately, ConnectedImageNeighborhoodShape still has a few more features that are not yet available with itk::setConnectivity(it, fullyConnected):

I hope it will still get into ITK 5.0! Please check http://review.source.kitware.com/#/c/23452 !

1 Like
11

Good search… It’s pretty good that we have this functionality compatible with range iterators, and as you said, this also allows 18 connected neighbors in 3D, and clear and tweakable set of offsets in any dimension.

1 Like
12

@phcerdan My latest patch ENH: Documented + tested order offsets ConnectedImageNeighborhoodShape was very much inspired by your earlier remarks on the order of the offsets, already on April 14, at itk::NeighborhoodRange: a new class for efficient modern C++ style iteration Now I think I found a proper term to describe the way the offsets are sorted: colexicographic order

The unit test included with the patch compares the offsets based on colexicographic order, by passing reverse-iterators of itk::Offset<Dimension> to std::lexicographical_compare. See itkConnectedImageNeighborhoodShapeGTest.cxx

Please check: http://review.source.kitware.com/#/c/23500

1 Like
13

Nice! That’s the proper name then. You should propose a std::colexicographical_compare for c++20 :slight_smile:. Cool trick with the reverse iterators.

1 Like
14

Cool: @dzenanz just merged the patch, which documents and tests that the offsets from ConnectedImageNeighborhoodShape are in colexicographic order:
Merge topic 'docConnectedImageNeighborhoodShape' · InsightSoftwareConsortium/ITK@22d2200 · GitHub
:smiley:

Hmm, I’ll think about it. Writing a proposal for the C++ Standard is usually a lot of work! But you could propose a ColexicographicCompare functor class for ITK, of course! Which could be helpful if we would want to test the order of other generated offsets (from other shapes) as well. There’s an itk::LexicographicCompare functor class already, added by @hjmjohnson

What do you think?

15

Sounds a good idea Niels, but running short of time lately here! I am thinking maybe it is a good exercise as a first contribution for somebody interested in learning the how-tos of patch submission in ITK.

Something like this will work for TAggregateTypes with reverse iterators, right Niels? A few lines more, a test file, and we will have a new functor class in ITK that will be useful in the short future :star_struck:

template< class TAggregateType1, class TAggregateType2 = TAggregateType1 >
 class ITK_TEMPLATE_EXPORT ColexicographicCompare
 {
public:
 bool operator()(const TAggregateType1 &lhs, const TAggregateType2 &rhs) const
  {
   return std::lexicographical_compare( lhs.rbegin(), lhs.rend(), rhs.rbegin(), rhs.rend() );
 }
};
16

Your suggested ColexicographicCompare implementation, based on the existing LexicographicCompare looks very much like what I had in mind, Pablo! You didn’t read my mind, did you? :wink:

However, before copying from itk::Functor::LexicographicCompare, maybe it could still be slightly improved… I just submitted a proposed patch: ENH: Made Functor::LexicographicCompare more generic and easier to use

And then, would you suggest adding the colexicographic version to the very same header file, itkLexicographicCompare.h? (I guess it will be about 20 extra lines of code.) Or do you think it’s preferable to have a separate header file for the colex functor?

17

I read your code! :rofl:

I am not sure, we should ask @matt.mccormick and @dzenanz, but I think maybe better to have it on its own file? Or merge both in a new header named: itkComparisonFunctors

1 Like
18

My preference is to use existing itkLexicographicCompare.h for colex functor.

2 Likes
19

+1

If the colex functor would be added to itkLexicographicCompare.h, it might be clearer that it belongs there, together with LexicographicCompare, when the colex class name would be spelled with uppercase L: CoLexicographicCompare. (The ordering is also sometimes referred to as “CoLex”, with uppercase L.) What do you think?

1 Like
20

Just submitted, please review: ENH: Added Functor::CoLexicographicCompare

I think such a functor is very useful, to ensure that the sequence of offsets (instances of itk::Offset<dimension>) of a neighborhood shape are ordered in the preferred way. Usually when doing neighborhood based pixel operations, a CoLex ordered sequence of shape offsets offers the best performance.