A shape class for ShapedImageNeighborhoodRange and ShapedNeighborhoodIterator

Engineering
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.

21

@phcerdan Would it be OK to you if the identifiers HyperrectangularImageNeighborhoodShape and GenerateHyperrectangularImageNeighborhoodOffsets would be renamed to RectangularImageNeighborhoodShape and GenerateRectangularImageNeighborhoodOffsets, respectively?

I remember you suggested the term hyperrectangular:

Wikipedia explained to me that the term hyperrectangle is a “generalization of a rectangle for higher dimensions”.

Personally I feel that the “hyper” adjective is not really necessary, as the template argument VImageDimension already indicates that the rectangle may be generalized for higher dimensionalities.

Note that itk::Image<TPixel, VImageDimension> also supports dimensionalities higher than 2 (even though the ITK image class has not been named something like itk::Hyperimage<THyperpixel, VImageDimension>).

Note also that this shape class supports 1-D as well. Would that be a hypo rectangular shape?

So please tell me, what do you think by now?

1 Like
22

Hi @Niels_Dekker, it would be definitively ok for me. NRectangle, or HyperRectangle might be more explicit, but as you mentioned, if the image dimension is a required template parameter, that can be inferred. I would just recommend to avoid the temptation of providing a default template parameter (= 2) for ImageDimension because the name (which I am sure is not in your plans).

2 Likes
23

Thanks, @phcerdan! I realize it’s very much a subjective issue. And it’s not a big issue to me. But anyway, please check my proposed patch: STYLE: Replaced “Hyperrect…” by “Rect…” in class + function names

P.S. I swear, I did not add a default template parameter :smiley:

1 Like