boost/gil/extension/numeric/algorithm.hpp

   1 //
   2 // Copyright 2005-2007 Adobe Systems Incorporated
   3 // Copyright 2019 Pranam Lashkari <plashkari628@gmail.com>
   4 //
   5 // Distributed under the Boost Software License, Version 1.0
   6 // See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt
   8 //
   9 #ifndef BOOST_GIL_EXTENSION_NUMERIC_ALGORITHM_HPP
  10 #define BOOST_GIL_EXTENSION_NUMERIC_ALGORITHM_HPP
  11
  12 #include <boost/gil/extension/numeric/pixel_numeric_operations.hpp>
  13
  14 #include <boost/gil/metafunctions.hpp>
  15 #include <boost/gil/pixel_iterator.hpp>
  16 #include <boost/gil/image.hpp>
  17
  18 #include <boost/assert.hpp>
  19
  20 #include <algorithm>
  21 #include <iterator>
  22 #include <numeric>
  23 #include <type_traits>
  24
  25 namespace boost { namespace gil {
  26
  27 /// \brief Reference proxy associated with a type that has a \p "reference" member type alias.
  28 ///
  29 /// The reference proxy is the reference type, but with stripped-out C++ reference.
  30 /// Models PixelConcept.
  31 template <typename T>
  32 struct pixel_proxy : std::remove_reference<typename T::reference> {};
  33
  34 /// \brief std::for_each for a pair of iterators
  35 template <typename Iterator1, typename Iterator2, typename BinaryFunction>
  36 BinaryFunction for_each(Iterator1 first1, Iterator1 last1, Iterator2 first2, BinaryFunction f)
  37 {
  38     while (first1 != last1)
  39         f(*first1++, *first2++);
  40     return f;
  41 }
  42
  43 template <typename SrcIterator, typename DstIterator>
  44 inline
  45 auto assign_pixels(SrcIterator src, SrcIterator src_end, DstIterator dst) -> DstIterator
  46 {
  47     for_each(src, src_end, dst,
  48         pixel_assigns_t
  49         <
  50             typename pixel_proxy<typename std::iterator_traits<SrcIterator>::value_type>::type,
  51             typename pixel_proxy<typename std::iterator_traits<DstIterator>::value_type>::type
  52         >());
  53     return dst + (src_end - src);
  54 }
  55
  56 namespace detail {
  57
  58 template <std::size_t Size>
  59 struct inner_product_k_t
  60 {
  61     template
  62     <
  63         class InputIterator1,
  64         class InputIterator2,
  65         class T,
  66         class BinaryOperation1,
  67         class BinaryOperation2
  68     >
  69     static T apply(
  70         InputIterator1 first1,
  71         InputIterator2 first2, T init,
  72         BinaryOperation1 binary_op1,
  73         BinaryOperation2 binary_op2)
  74     {
  75         init = binary_op1(init, binary_op2(*first1, *first2));
  76         return inner_product_k_t<Size - 1>::template apply(
  77             first1 + 1, first2 + 1, init, binary_op1, binary_op2);
  78     }
  79 };
  80
  81 template <>
  82 struct inner_product_k_t<0>
  83 {
  84     template
  85     <
  86         class InputIterator1,
  87         class InputIterator2,
  88         class T,
  89         class BinaryOperation1,
  90         class BinaryOperation2
  91     >
  92     static T apply(
  93         InputIterator1 first1,
  94         InputIterator2 first2,
  95         T init,
  96         BinaryOperation1 binary_op1,
  97         BinaryOperation2 binary_op2)
  98     {
  99         return init;
 100     }
 101 };
 102
 103 } // namespace detail
 104
 105 /// static version of std::inner_product
 106 template
 107 <
 108     std::size_t Size,
 109     class InputIterator1,
 110     class InputIterator2,
 111     class T,
 112     class BinaryOperation1,
 113     class BinaryOperation2
 114 >
 115 BOOST_FORCEINLINE
 116 T inner_product_k(
 117     InputIterator1 first1,
 118     InputIterator2 first2,
 119     T init,
 120     BinaryOperation1 binary_op1,
 121     BinaryOperation2 binary_op2)
 122 {
 123     return detail::inner_product_k_t<Size>::template apply(
 124         first1, first2, init, binary_op1, binary_op2);
 125 }
 126
 127 /// \brief 1D un-guarded cross-correlation with a variable-size kernel
 128 template
 129 <
 130     typename PixelAccum,
 131     typename SrcIterator,
 132     typename KernelIterator,
 133     typename Size,
 134     typename DstIterator
 135 >
 136 inline
 137 auto correlate_pixels_n(
 138     SrcIterator src_begin,
 139     SrcIterator src_end,
 140     KernelIterator kernel_begin,
 141     Size kernel_size,
 142     DstIterator dst_begin)
 143     -> DstIterator
 144 {
 145     using src_pixel_ref_t = typename pixel_proxy
 146         <
 147             typename std::iterator_traits<SrcIterator>::value_type
 148         >::type;
 149     using dst_pixel_ref_t = typename pixel_proxy
 150         <
 151             typename std::iterator_traits<DstIterator>::value_type
 152         >::type;
 153     using kernel_value_t = typename std::iterator_traits<KernelIterator>::value_type;
 154
 155     PixelAccum accum_zero;
 156     pixel_zeros_t<PixelAccum>()(accum_zero);
 157     while (src_begin != src_end)
 158     {
 159         pixel_assigns_t<PixelAccum, dst_pixel_ref_t>()(
 160             std::inner_product(
 161                 src_begin,
 162                 src_begin + kernel_size,
 163                 kernel_begin,
 164                 accum_zero,
 165                 pixel_plus_t<PixelAccum, PixelAccum, PixelAccum>(),
 166                 pixel_multiplies_scalar_t<src_pixel_ref_t, kernel_value_t, PixelAccum>()),
 167             *dst_begin);
 168
 169         ++src_begin;
 170         ++dst_begin;
 171     }
 172     return dst_begin;
 173 }
 174
 175 /// \brief 1D un-guarded cross-correlation with a fixed-size kernel
 176 template
 177 <
 178     std::size_t Size,
 179     typename PixelAccum,
 180     typename SrcIterator,
 181     typename KernelIterator,
 182     typename DstIterator
 183 >
 184 inline
 185 auto correlate_pixels_k(
 186     SrcIterator src_begin,
 187     SrcIterator src_end,
 188     KernelIterator kernel_begin,
 189     DstIterator dst_begin)
 190     -> DstIterator
 191 {
 192     using src_pixel_ref_t = typename pixel_proxy
 193         <
 194             typename std::iterator_traits<SrcIterator>::value_type
 195         >::type;
 196     using dst_pixel_ref_t = typename pixel_proxy
 197         <
 198             typename std::iterator_traits<DstIterator>::value_type
 199         >::type;
 200     using kernel_type = typename std::iterator_traits<KernelIterator>::value_type;
 201
 202     PixelAccum accum_zero;
 203     pixel_zeros_t<PixelAccum>()(accum_zero);
 204     while (src_begin != src_end)
 205     {
 206         pixel_assigns_t<PixelAccum, dst_pixel_ref_t>()(
 207             inner_product_k<Size>(
 208                 src_begin,
 209                 kernel_begin,
 210                 accum_zero,
 211                 pixel_plus_t<PixelAccum, PixelAccum, PixelAccum>(),
 212                 pixel_multiplies_scalar_t<src_pixel_ref_t, kernel_type, PixelAccum>()),
 213             *dst_begin);
 214
 215         ++src_begin;
 216         ++dst_begin;
 217     }
 218     return dst_begin;
 219 }
 220
 221 /// \brief destination is set to be product of the source and a scalar
 222 /// \tparam PixelAccum - TODO
 223 /// \tparam SrcView Models ImageViewConcept
 224 /// \tparam DstView Models MutableImageViewConcept
 225 template <typename PixelAccum, typename SrcView, typename Scalar, typename DstView>
 226 inline
 227 void view_multiplies_scalar(SrcView const& src_view, Scalar const& scalar, DstView const& dst_view)
 228 {
 229     static_assert(std::is_scalar<Scalar>::value, "Scalar is not scalar");
 230     BOOST_ASSERT(src_view.dimensions() == dst_view.dimensions());
 231     using src_pixel_ref_t = typename pixel_proxy<typename SrcView::value_type>::type;
 232     using dst_pixel_ref_t = typename pixel_proxy<typename DstView::value_type>::type;
 233     using y_coord_t = typename SrcView::y_coord_t;
 234
 235     y_coord_t const height = src_view.height();
 236     for (y_coord_t y = 0; y < height; ++y)
 237     {
 238         typename SrcView::x_iterator it_src = src_view.row_begin(y);
 239         typename DstView::x_iterator it_dst = dst_view.row_begin(y);
 240         typename SrcView::x_iterator it_src_end = src_view.row_end(y);
 241         while (it_src != it_src_end)
 242         {
 243             pixel_assigns_t<PixelAccum, dst_pixel_ref_t>()(
 244                 pixel_multiplies_scalar_t<src_pixel_ref_t, Scalar, PixelAccum>()(*it_src, scalar),
 245                 *it_dst);
 246
 247             ++it_src;
 248             ++it_dst;
 249         }
 250     }
 251 }
 252
 253
 254 /// \ingroup ImageAlgorithms
 255 /// \brief Boundary options for image boundary extension
 256 enum class boundary_option
 257 {
 258     output_ignore,  /// do nothing to the output
 259     output_zero,    /// set the output to zero
 260     extend_padded,  /// assume the source boundaries to be padded already
 261     extend_zero,    /// assume the source boundaries to be zero
 262     extend_constant /// assume the source boundaries to be the boundary value
 263 };
 264
 265 namespace detail
 266 {
 267
 268 template <typename SrcView, typename RltView>
 269 void extend_row_impl(
 270     SrcView src_view,
 271     RltView result_view,
 272     std::size_t extend_count,
 273     boundary_option option)
 274 {
 275     std::ptrdiff_t extend_count_ = static_cast<std::ptrdiff_t>(extend_count);
 276
 277     if (option == boundary_option::extend_constant)
 278     {
 279         for (std::ptrdiff_t i = 0; i < result_view.height(); i++)
 280         {
 281             if(i >= extend_count_ && i < extend_count_ + src_view.height())
 282             {
 283                 assign_pixels(
 284                     src_view.row_begin(i - extend_count_),
 285                     src_view.row_end(i - extend_count_),
 286                     result_view.row_begin(i)
 287                 );
 288             }
 289             else if(i < extend_count_)
 290             {
 291                 assign_pixels(src_view.row_begin(0), src_view.row_end(0), result_view.row_begin(i));
 292             }
 293             else
 294             {
 295                 assign_pixels(
 296                     src_view.row_begin(src_view.height() - 1),
 297                     src_view.row_end(src_view.height() - 1),
 298                     result_view.row_begin(i)
 299                 );
 300             }
 301
 302         }
 303     }
 304     else if (option == boundary_option::extend_zero)
 305     {
 306         typename SrcView::value_type acc_zero;
 307         pixel_zeros_t<typename SrcView::value_type>()(acc_zero);
 308
 309         for (std::ptrdiff_t i = 0; i < result_view.height(); i++)
 310         {
 311             if (i >= extend_count_ && i < extend_count_ + src_view.height())
 312             {
 313                 assign_pixels(
 314                     src_view.row_begin(i - extend_count_),
 315                     src_view.row_end(i - extend_count_),
 316                     result_view.row_begin(i)
 317                 );
 318             }
 319             else
 320             {
 321                 std::fill_n(result_view.row_begin(i), result_view.width(), acc_zero);
 322             }
 323         }
 324     }
 325     else if (option == boundary_option::extend_padded)
 326     {
 327         auto original_view = subimage_view(
 328             src_view,
 329             0,
 330             -extend_count,
 331             src_view.width(),
 332             src_view.height() + (2 * extend_count)
 333         );
 334         for (std::ptrdiff_t i = 0; i < result_view.height(); i++)
 335         {
 336             assign_pixels(
 337                 original_view.row_begin(i),
 338                 original_view.row_end(i),
 339                 result_view.row_begin(i)
 340             );
 341         }
 342     }
 343     else
 344     {
 345         BOOST_ASSERT_MSG(false, "Invalid boundary option");
 346     }
 347 }
 348
 349 } //namespace detail
 350
 351
 352 /// \brief adds new row at top and bottom.
 353 /// Image padding introduces new pixels around the edges of an image.
 354 /// The border provides space for annotations or acts as a boundary when using advanced filtering techniques.
 355 /// \tparam SrcView Models ImageViewConcept
 356 /// \tparam extend_count number of rows to be added each side
 357 /// \tparam option - TODO
 358 template <typename SrcView>
 359 auto extend_row(
 360     SrcView src_view,
 361     std::size_t extend_count,
 362     boundary_option option
 363 ) -> typename gil::image<typename SrcView::value_type>
 364 {
 365     typename gil::image<typename SrcView::value_type>
 366         result_img(src_view.width(), src_view.height() + (2 * extend_count));
 367
 368     auto result_view = view(result_img);
 369     detail::extend_row_impl(src_view, result_view, extend_count, option);
 370     return result_img;
 371 }
 372
 373
 374 /// \brief adds new column at left and right.
 375 /// Image padding introduces new pixels around the edges of an image.
 376 /// The border provides space for annotations or acts as a boundary when using advanced filtering techniques.
 377 /// \tparam SrcView Models ImageViewConcept
 378 /// \tparam extend_count number of columns to be added each side
 379 /// \tparam option - TODO
 380 template <typename SrcView>
 381 auto extend_col(
 382     SrcView src_view,
 383     std::size_t extend_count,
 384     boundary_option option
 385 ) -> typename gil::image<typename SrcView::value_type>
 386 {
 387     auto src_view_rotate = rotated90cw_view(src_view);
 388
 389     typename gil::image<typename SrcView::value_type>
 390         result_img(src_view.width() + (2 * extend_count), src_view.height());
 391
 392     auto result_view = rotated90cw_view(view(result_img));
 393     detail::extend_row_impl(src_view_rotate, result_view, extend_count, option);
 394     return result_img;
 395 }
 396
 397 /// \brief adds new row and column at all sides.
 398 /// Image padding introduces new pixels around the edges of an image.
 399 /// The border provides space for annotations or acts as a boundary when using advanced filtering techniques.
 400 /// \tparam SrcView Models ImageViewConcept
 401 /// \tparam extend_count number of rows/column to be added each side
 402 /// \tparam option - TODO
 403 template <typename SrcView>
 404 auto extend_boundary(
 405     SrcView src_view,
 406     std::size_t extend_count,
 407     boundary_option option
 408 ) -> typename gil::image<typename SrcView::value_type>
 409 {
 410     if (option == boundary_option::extend_padded)
 411     {
 412         typename gil::image<typename SrcView::value_type>
 413             result_img(src_view.width()+(2 * extend_count), src_view.height()+(2 * extend_count));
 414         typename gil::image<typename SrcView::value_type>::view_t result_view = view(result_img);
 415
 416         auto original_view = subimage_view(
 417             src_view,
 418             -extend_count,
 419             -extend_count,
 420             src_view.width() + (2 * extend_count),
 421             src_view.height() + (2 * extend_count)
 422         );
 423
 424         for (std::ptrdiff_t i = 0; i < result_view.height(); i++)
 425         {
 426             assign_pixels(
 427                 original_view.row_begin(i),
 428                 original_view.row_end(i),
 429                 result_view.row_begin(i)
 430             );
 431         }
 432
 433         return result_img;
 434     }
 435
 436     auto auxilary_img = extend_col(src_view, extend_count, option);
 437     return extend_row(view(auxilary_img), extend_count, option);
 438 }
 439
 440 }} // namespace boost::gil
 441
 442 #endif