ITK  5.2.0
Insight Toolkit
itkConnectedImageNeighborhoodShape.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright NumFOCUS
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0.txt
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  *=========================================================================*/
18 
19 #ifndef itkConnectedImageNeighborhoodShape_h
20 #define itkConnectedImageNeighborhoodShape_h
21 
22 #include "itkMath.h"
23 #include "itkOffset.h"
24 
25 #include <array>
26 #include <cassert>
27 #include <cstdint> // For uintmax_t
28 #include <limits>
29 
30 // C++11 does not guarantee that assert can be used in constexpr
31 // functions. This is a work-around for GCC 4.8, 4.9. Originating
32 // from Andrzej's C++ blog:
33 // https://akrzemi1.wordpress.com/2017/05/18/asserts-in-constexpr-functions/
34 #if defined NDEBUG
35 # define ITK_X_ASSERT(CHECK) void(0)
36 #else
37 # define ITK_X_ASSERT(CHECK) ((CHECK) ? void(0) : [] { assert(!#CHECK); }())
38 #endif
39 
40 namespace itk
41 {
42 
96 template <unsigned int VImageDimension>
98 {
99 public:
100  static constexpr unsigned int ImageDimension = VImageDimension;
102 
114  constexpr explicit ConnectedImageNeighborhoodShape(const std::size_t maximumCityblockDistance,
115  const bool includeCenterPixel) ITK_NOEXCEPT
116  : m_MaximumCityblockDistance{ maximumCityblockDistance }
117  , m_IncludeCenterPixel{ includeCenterPixel }
118  , m_NumberOfOffsets{ CalculateNumberOfOffsets(maximumCityblockDistance, includeCenterPixel) }
119  {}
121 
122 
124  constexpr std::size_t
125  GetNumberOfOffsets() const ITK_NOEXCEPT
126  {
127  return m_NumberOfOffsets;
128  }
129 
130 
132  void
133  FillOffsets(Offset<ImageDimension> * const offsets) const ITK_NOEXCEPT
134  {
135  if (m_NumberOfOffsets > 0)
136  {
137  assert(offsets != nullptr);
138  Offset<ImageDimension> offset;
139  std::fill_n(offset.begin(), ImageDimension, -1);
141 
142  std::size_t i = 0;
143 
144  while (i < m_NumberOfOffsets)
145  {
146  const std::size_t numberOfNonZeroOffsetValues =
147  ImageDimension - static_cast<std::size_t>(std::count(offset.begin(), offset.end(), 0));
148 
149  if ((m_IncludeCenterPixel || (numberOfNonZeroOffsetValues > 0)) &&
150  (numberOfNonZeroOffsetValues <= m_MaximumCityblockDistance))
151  {
152  offsets[i] = offset;
153  ++i;
154  }
155 
156  // Go to the next offset:
157  for (unsigned int direction = 0; direction < ImageDimension; ++direction)
158  {
159  auto & offsetValue = offset[direction];
160 
161  ++offsetValue;
162 
163  if (offsetValue <= 1)
164  {
165  break;
166  }
167  offsetValue = -1;
168  }
169  };
170  }
171  }
172 
173 private:
174  // The maximum city-block distance (Manhattan distance) between the center
175  // pixel and each connected neighbor pixel.
177 
178  // Specifies whether or not the center pixel (offset zero) should be included
179  // with the offsets for this shape.
181 
182  // The number of offsets needed to represent this shape.
183  std::size_t m_NumberOfOffsets;
184 
185 
186  // Calculates a + b. Numeric overflow triggers a compilation error in
187  // "constexpr context" and a debug assert failure at run-time.
188  static constexpr std::uintmax_t
189  CalculateSum(const std::uintmax_t a, const std::uintmax_t b) ITK_NOEXCEPT
190  {
191  return ((a + b) >= a) && ((a + b) >= b) ? (a + b) : (ITK_X_ASSERT(!"CalculateSum overflow!"), 0);
192  }
193 
194 
195  // Calculates 2 ^ n. Numeric overflow triggers a compilation error in
196  // "constexpr context" and a debug assert failure at run-time.
197  static constexpr std::uintmax_t
198  CalculatePowerOfTwo(const std::size_t n) ITK_NOEXCEPT
199  {
200  return (n < std::numeric_limits<std::uintmax_t>::digits) ? (std::uintmax_t{ 1 } << n)
201  : (ITK_X_ASSERT(!"CalculatePowerOfTwo overflow!"), 0);
202  }
203 
204 
205  // Calculates the binomial coefficient, 'n' over 'k'.
206  // Inspired by the 'binom' function from Walter, June 23, 2017:
207  // https://stackoverflow.com/questions/44718971/calculate-binomial-coffeficient-very-reliable/44719165#44719165
208  // Optimized for small values of 'k' (k <= n/2).
209  static constexpr std::uintmax_t
211  {
212  return (k > n) ? (ITK_X_ASSERT(!"Out of range!"), 0)
213  : (k == 0) ? 1 : Math::UnsignedProduct(n, CalculateBinomialCoefficient(n - 1, k - 1)) / k;
214  }
215 
216 
217  // Calculates the number of m-dimensional hypercubes on the boundary of an
218  // n-cube, as described at https://en.wikipedia.org/wiki/Hypercube#Elements
219  // (Which refers to H.S.M. Coxeter, Regular polytopes, 3rd ed., 1973, p.120.)
220  static constexpr std::size_t
221  CalculateNumberOfHypercubesOnBoundaryOfCube(const std::size_t m, const std::size_t n) ITK_NOEXCEPT
222  {
223  // Calculate 2^(n-m) * BinomialCoefficient(n, m)
225  (((2 * m) < n) ?
226  // Calculate either the binomial coefficient of (n, m) or (n, n - m).
227  // Mathematically, both should yield the same number, but the
228  // calculation is optimized for a smaller second argument.
230  : CalculateBinomialCoefficient(n, n - m)));
231  }
232 
233 
234  // Iterates recursively from i = ImageDimension-1 down to m (inclusive).
235  static constexpr std::size_t
236  CalculateSumOfNumberOfHypercubesOnBoundaryOfCube(const std::size_t i, const std::size_t m) ITK_NOEXCEPT
237  {
238  return ITK_X_ASSERT(i >= m),
240  ((i <= m) ? 0 : CalculateSumOfNumberOfHypercubesOnBoundaryOfCube(i - 1, m)));
241  }
242 
243 
245  static constexpr std::size_t
246  CalculateNumberOfConnectedNeighbors(const std::size_t maximumCityblockDistance) ITK_NOEXCEPT
247  {
248  return (((maximumCityblockDistance == 0) || (ImageDimension == 0))
249  ? 0
250  : ((maximumCityblockDistance >= ImageDimension)
253  (ImageDimension - maximumCityblockDistance))));
254  }
255 
256 
258  static constexpr std::size_t
259  CalculateNumberOfOffsets(const std::size_t maximumCityblockDistance, const bool includeCenterPixel) ITK_NOEXCEPT
260  {
261  return (includeCenterPixel ? 1 : 0) + CalculateNumberOfConnectedNeighbors(maximumCityblockDistance);
262  }
263 
264 
265  template <unsigned int VImageDimensionOfFriend, std::size_t VMaximumCityblockDistance, bool VIncludeCenterPixel>
266  friend std::array<
269  VIncludeCenterPixel)>
271 };
272 
273 
275 template <unsigned int VImageDimension, std::size_t VMaximumCityblockDistance, bool VIncludeCenterPixel>
276 std::array<Offset<VImageDimension>,
277  ConnectedImageNeighborhoodShape<VImageDimension>::CalculateNumberOfOffsets(VMaximumCityblockDistance,
278  VIncludeCenterPixel)>
280 {
281  constexpr ConnectedImageNeighborhoodShape<VImageDimension> shape{ VMaximumCityblockDistance, VIncludeCenterPixel };
282  std::array<Offset<VImageDimension>, shape.GetNumberOfOffsets()> offsets;
283  shape.FillOffsets(offsets.data());
284  return offsets;
285 }
287 
288 } // namespace itk
289 
290 #undef ITK_X_ASSERT
291 
292 #endif
itk::ConnectedImageNeighborhoodShape::ImageDimension
static constexpr unsigned int ImageDimension
Definition: itkConnectedImageNeighborhoodShape.h:100
itk::ConnectedImageNeighborhoodShape::GenerateConnectedImageNeighborhoodShapeOffsets
friend std::array< Offset< VImageDimensionOfFriend >, ConnectedImageNeighborhoodShape< VImageDimensionOfFriend >::CalculateNumberOfOffsets(VMaximumCityblockDistance, VIncludeCenterPixel)> GenerateConnectedImageNeighborhoodShapeOffsets() noexcept
Definition: itkConnectedImageNeighborhoodShape.h:279
itkOffset.h
itk::ConnectedImageNeighborhoodShape
Definition: itkConnectedImageNeighborhoodShape.h:97
itk::ConnectedImageNeighborhoodShape::CalculateNumberOfOffsets
static constexpr std::vcl_size_t CalculateNumberOfOffsets(const std::vcl_size_t maximumCityblockDistance, const bool includeCenterPixel) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:259
itk::ConnectedImageNeighborhoodShape::CalculateNumberOfConnectedNeighbors
static constexpr std::vcl_size_t CalculateNumberOfConnectedNeighbors(const std::vcl_size_t maximumCityblockDistance) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:246
itk::ConnectedImageNeighborhoodShape::GetNumberOfOffsets
constexpr std::vcl_size_t GetNumberOfOffsets() const noexcept
Definition: itkConnectedImageNeighborhoodShape.h:125
itk::Math::UnsignedPower
constexpr TReturnType UnsignedPower(const std::uintmax_t base, const std::uintmax_t exponent) noexcept
Definition: itkMath.h:802
itk::ConnectedImageNeighborhoodShape::FillOffsets
void FillOffsets(Offset< ImageDimension > *const offsets) const noexcept
Definition: itkConnectedImageNeighborhoodShape.h:133
itk::ConnectedImageNeighborhoodShape::CalculatePowerOfTwo
static constexpr std::uintmax_t CalculatePowerOfTwo(const std::vcl_size_t n) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:198
itk::ConnectedImageNeighborhoodShape::CalculateNumberOfHypercubesOnBoundaryOfCube
static constexpr std::vcl_size_t CalculateNumberOfHypercubesOnBoundaryOfCube(const std::vcl_size_t m, const std::vcl_size_t n) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:221
itk::uintmax_t
::uintmax_t uintmax_t
Definition: itkIntTypes.h:56
itk::Offset< ImageDimension >
itk::ConnectedImageNeighborhoodShape::m_IncludeCenterPixel
bool m_IncludeCenterPixel
Definition: itkConnectedImageNeighborhoodShape.h:180
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnnulusOperator.h:24
itk::Math::UnsignedProduct
constexpr TReturnType UnsignedProduct(const std::uintmax_t a, const std::uintmax_t b) noexcept
Definition: itkMath.h:780
itk::Offset::begin
iterator begin()
Definition: itkOffset.h:311
ITK_X_ASSERT
#define ITK_X_ASSERT(CHECK)
Definition: itkConnectedImageNeighborhoodShape.h:37
itk::ConnectedImageNeighborhoodShape::ConnectedImageNeighborhoodShape
constexpr ConnectedImageNeighborhoodShape(const std::vcl_size_t maximumCityblockDistance, const bool includeCenterPixel) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:114
itk::ConnectedImageNeighborhoodShape::CalculateSum
static constexpr std::uintmax_t CalculateSum(const std::uintmax_t a, const std::uintmax_t b) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:189
itk::ConnectedImageNeighborhoodShape::CalculateBinomialCoefficient
static constexpr std::uintmax_t CalculateBinomialCoefficient(const std::uintmax_t n, const std::uintmax_t k) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:210
itk::ConnectedImageNeighborhoodShape::m_MaximumCityblockDistance
std::vcl_size_t m_MaximumCityblockDistance
Definition: itkConnectedImageNeighborhoodShape.h:176
itk::ConnectedImageNeighborhoodShape::CalculateSumOfNumberOfHypercubesOnBoundaryOfCube
static constexpr std::vcl_size_t CalculateSumOfNumberOfHypercubesOnBoundaryOfCube(const std::vcl_size_t i, const std::vcl_size_t m) noexcept
Definition: itkConnectedImageNeighborhoodShape.h:236
itkMath.h
itk::ConnectedImageNeighborhoodShape::m_NumberOfOffsets
std::vcl_size_t m_NumberOfOffsets
Definition: itkConnectedImageNeighborhoodShape.h:183
itk::Offset::end
iterator end()
Definition: itkOffset.h:323