boost/gil/extension/numeric/convolve.hpp

   1 //
   2 // Copyright 2005-2007 Adobe Systems Incorporated
   3 // Copyright 2019 Miral Shah <miralshah2211@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_CONVOLVE_HPP
  10 #define BOOST_GIL_EXTENSION_NUMERIC_CONVOLVE_HPP
  11
  12 #include <boost/gil/extension/numeric/algorithm.hpp>
  13 #include <boost/gil/extension/numeric/kernel.hpp>
  14 #include <boost/gil/extension/numeric/pixel_numeric_operations.hpp>
  15
  16 #include <boost/gil/algorithm.hpp>
  17 #include <boost/gil/image_view_factory.hpp>
  18 #include <boost/gil/metafunctions.hpp>
  19
  20 #include <boost/assert.hpp>
  21
  22 #include <algorithm>
  23 #include <cstddef>
  24 #include <functional>
  25 #include <type_traits>
  26 #include <vector>
  27
  28 namespace boost { namespace gil {
  29
  30 // 2D spatial seperable convolutions and cross-correlations
  31
  32 namespace detail {
  33
  34 /// \brief Compute the cross-correlation of 1D kernel with the rows of an image
  35 /// \tparam PixelAccum - TODO
  36 /// \tparam SrcView Models ImageViewConcept
  37 /// \tparam Kernel - TODO
  38 /// \tparam DstView Models MutableImageViewConcept
  39 /// \tparam Correlator - TODO
  40 /// \param src_view
  41 /// \param kernel - TODO
  42 /// \param dst_view Destination where new computed values of pixels are assigned to
  43 /// \param option - TODO
  44 /// \param correlator - TODO
  45 template
  46 <
  47     typename PixelAccum,
  48     typename SrcView,
  49     typename Kernel,
  50     typename DstView,
  51     typename Correlator
  52 >
  53 void correlate_rows_impl(
  54     SrcView const& src_view,
  55     Kernel const& kernel,
  56     DstView const& dst_view,
  57     boundary_option option,
  58     Correlator correlator)
  59 {
  60     BOOST_ASSERT(src_view.dimensions() == dst_view.dimensions());
  61     BOOST_ASSERT(kernel.size() != 0);
  62
  63     if(kernel.size() == 1)
  64     {
  65         // Reduces to a multiplication
  66         view_multiplies_scalar<PixelAccum>(src_view, *kernel.begin(), dst_view);
  67         return;
  68     }
  69
  70     using src_pixel_ref_t = typename pixel_proxy<typename SrcView::value_type>::type;
  71     using dst_pixel_ref_t = typename pixel_proxy<typename DstView::value_type>::type;
  72     using x_coord_t = typename SrcView::x_coord_t;
  73     using y_coord_t = typename SrcView::y_coord_t;
  74
  75     x_coord_t const width = src_view.width();
  76     y_coord_t const height = src_view.height();
  77     if (width == 0)
  78         return;
  79
  80     PixelAccum acc_zero;
  81     pixel_zeros_t<PixelAccum>()(acc_zero);
  82     if (option == boundary_option::output_ignore || option == boundary_option::output_zero)
  83     {
  84         typename DstView::value_type dst_zero;
  85         pixel_assigns_t<PixelAccum, dst_pixel_ref_t>()(acc_zero, dst_zero);
  86         if (width < static_cast<x_coord_t>(kernel.size()))
  87         {
  88             if (option == boundary_option::output_zero)
  89                 fill_pixels(dst_view, dst_zero);
  90         }
  91         else
  92         {
  93             std::vector<PixelAccum> buffer(width);
  94             for (y_coord_t y = 0; y < height; ++y)
  95             {
  96                 assign_pixels(src_view.row_begin(y), src_view.row_end(y), &buffer.front());
  97                 typename DstView::x_iterator it_dst = dst_view.row_begin(y);
  98                 if (option == boundary_option::output_zero)
  99                     std::fill_n(it_dst, kernel.left_size(), dst_zero);
 100                 it_dst += kernel.left_size();
 101                 correlator(&buffer.front(), &buffer.front() + width + 1 - kernel.size(),
 102                            kernel.begin(), it_dst);
 103                 it_dst += width + 1 - kernel.size();
 104                 if (option == boundary_option::output_zero)
 105                     std::fill_n(it_dst, kernel.right_size(), dst_zero);
 106             }
 107         }
 108     }
 109     else
 110     {
 111         std::vector<PixelAccum> buffer(width + kernel.size() - 1);
 112         for (y_coord_t y = 0; y < height; ++y)
 113         {
 114             PixelAccum *it_buffer = &buffer.front();
 115             if (option == boundary_option::extend_padded)
 116             {
 117                 assign_pixels(
 118                     src_view.row_begin(y) - kernel.left_size(),
 119                     src_view.row_end(y) + kernel.right_size(),
 120                     it_buffer);
 121             }
 122             else if (option == boundary_option::extend_zero)
 123             {
 124                 std::fill_n(it_buffer, kernel.left_size(), acc_zero);
 125                 it_buffer += kernel.left_size();
 126                 assign_pixels(src_view.row_begin(y), src_view.row_end(y), it_buffer);
 127                 it_buffer += width;
 128                 std::fill_n(it_buffer, kernel.right_size(), acc_zero);
 129             }
 130             else if (option == boundary_option::extend_constant)
 131             {
 132                 PixelAccum filler;
 133                 pixel_assigns_t<src_pixel_ref_t, PixelAccum>()(*src_view.row_begin(y), filler);
 134                 std::fill_n(it_buffer, kernel.left_size(), filler);
 135                 it_buffer += kernel.left_size();
 136                 assign_pixels(src_view.row_begin(y), src_view.row_end(y), it_buffer);
 137                 it_buffer += width;
 138                 pixel_assigns_t<src_pixel_ref_t, PixelAccum>()(src_view.row_end(y)[-1], filler);
 139                 std::fill_n(it_buffer, kernel.right_size(), filler);
 140             }
 141
 142             correlator(
 143                 &buffer.front(), &buffer.front() + width,
 144                 kernel.begin(),
 145                 dst_view.row_begin(y));
 146         }
 147     }
 148 }
 149
 150 template <typename PixelAccum>
 151 class correlator_n
 152 {
 153 public:
 154     correlator_n(std::size_t size) : size_(size) {}
 155
 156     template <typename SrcIterator, typename KernelIterator, typename DstIterator>
 157     void operator()(
 158         SrcIterator src_begin,
 159         SrcIterator src_end,
 160         KernelIterator kernel_begin,
 161         DstIterator dst_begin)
 162     {
 163         correlate_pixels_n<PixelAccum>(src_begin, src_end, kernel_begin, size_, dst_begin);
 164     }
 165
 166 private:
 167     std::size_t size_{0};
 168 };
 169
 170 template <std::size_t Size, typename PixelAccum>
 171 struct correlator_k
 172 {
 173     template <typename SrcIterator, typename KernelIterator, typename DstIterator>
 174     void operator()(
 175         SrcIterator src_begin,
 176         SrcIterator src_end,
 177         KernelIterator kernel_begin,
 178         DstIterator dst_begin)
 179     {
 180         correlate_pixels_k<Size, PixelAccum>(src_begin, src_end, kernel_begin, dst_begin);
 181     }
 182 };
 183
 184 } // namespace detail
 185
 186 /// \ingroup ImageAlgorithms
 187 /// \brief Correlate 1D variable-size kernel along the rows of image
 188 /// \tparam PixelAccum TODO
 189 /// \tparam SrcView Models ImageViewConcept
 190 /// \tparam Kernel TODO
 191 /// \tparam DstView Models MutableImageViewConcept
 192 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 193 BOOST_FORCEINLINE
 194 void correlate_rows(
 195     SrcView const& src_view,
 196     Kernel const& kernel,
 197     DstView const& dst_view,
 198     boundary_option option = boundary_option::extend_zero)
 199 {
 200     detail::correlate_rows_impl<PixelAccum>(
 201         src_view, kernel, dst_view, option, detail::correlator_n<PixelAccum>(kernel.size()));
 202 }
 203
 204 /// \ingroup ImageAlgorithms
 205 /// \brief Correlate 1D variable-size kernel along the columns of image
 206 /// \tparam PixelAccum TODO
 207 /// \tparam SrcView Models ImageViewConcept
 208 /// \tparam Kernel TODO
 209 /// \tparam DstView Models MutableImageViewConcept
 210 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 211 BOOST_FORCEINLINE
 212 void correlate_cols(
 213     SrcView const& src_view,
 214     Kernel const& kernel,
 215     DstView const& dst_view,
 216     boundary_option option = boundary_option::extend_zero)
 217 {
 218     correlate_rows<PixelAccum>(
 219         transposed_view(src_view), kernel, transposed_view(dst_view), option);
 220 }
 221
 222 /// \ingroup ImageAlgorithms
 223 /// \brief Convolve 1D variable-size kernel along the rows of image
 224 /// \tparam PixelAccum TODO
 225 /// \tparam SrcView Models ImageViewConcept
 226 /// \tparam Kernel TODO
 227 /// \tparam DstView Models MutableImageViewConcept
 228 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 229 BOOST_FORCEINLINE
 230 void convolve_rows(
 231     SrcView const& src_view,
 232     Kernel const& kernel,
 233     DstView const& dst_view,
 234     boundary_option option = boundary_option::extend_zero)
 235 {
 236     correlate_rows<PixelAccum>(src_view, reverse_kernel(kernel), dst_view, option);
 237 }
 238
 239 /// \ingroup ImageAlgorithms
 240 /// \brief Convolve 1D variable-size kernel along the columns of image
 241 /// \tparam PixelAccum TODO
 242 /// \tparam SrcView Models ImageViewConcept
 243 /// \tparam Kernel TODO
 244 /// \tparam DstView Models MutableImageViewConcept
 245 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 246 BOOST_FORCEINLINE
 247 void convolve_cols(
 248     SrcView const& src_view,
 249     Kernel const& kernel,
 250     DstView const& dst_view,
 251     boundary_option option = boundary_option::extend_zero)
 252 {
 253     convolve_rows<PixelAccum>(
 254         transposed_view(src_view), kernel, transposed_view(dst_view), option);
 255 }
 256
 257 /// \ingroup ImageAlgorithms
 258 /// \brief Correlate 1D fixed-size kernel along the rows of image
 259 /// \tparam PixelAccum TODO
 260 /// \tparam SrcView Models ImageViewConcept
 261 /// \tparam Kernel TODO
 262 /// \tparam DstView Models MutableImageViewConcept
 263 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 264 BOOST_FORCEINLINE
 265 void correlate_rows_fixed(
 266     SrcView const& src_view,
 267     Kernel const& kernel,
 268     DstView const& dst_view,
 269     boundary_option option = boundary_option::extend_zero)
 270 {
 271     using correlator = detail::correlator_k<Kernel::static_size, PixelAccum>;
 272     detail::correlate_rows_impl<PixelAccum>(src_view, kernel, dst_view, option, correlator{});
 273 }
 274
 275 /// \ingroup ImageAlgorithms
 276 /// \brief Correlate 1D fixed-size kernel along the columns of image
 277 /// \tparam PixelAccum TODO
 278 /// \tparam SrcView Models ImageViewConcept
 279 /// \tparam Kernel TODO
 280 /// \tparam DstView Models MutableImageViewConcept
 281 template <typename PixelAccum,typename SrcView,typename Kernel,typename DstView>
 282 BOOST_FORCEINLINE
 283 void correlate_cols_fixed(
 284     SrcView const& src_view,
 285     Kernel const& kernel,
 286     DstView const& dst_view,
 287     boundary_option option = boundary_option::extend_zero)
 288 {
 289     correlate_rows_fixed<PixelAccum>(
 290         transposed_view(src_view), kernel, transposed_view(dst_view), option);
 291 }
 292
 293 /// \ingroup ImageAlgorithms
 294 /// \brief Convolve 1D fixed-size kernel along the rows of image
 295 /// \tparam PixelAccum TODO
 296 /// \tparam SrcView Models ImageViewConcept
 297 /// \tparam Kernel TODO
 298 /// \tparam DstView Models MutableImageViewConcept
 299 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 300 BOOST_FORCEINLINE
 301 void convolve_rows_fixed(
 302     SrcView const& src_view,
 303     Kernel const& kernel,
 304     DstView const& dst_view,
 305     boundary_option option = boundary_option::extend_zero)
 306 {
 307     correlate_rows_fixed<PixelAccum>(src_view, reverse_kernel(kernel), dst_view, option);
 308 }
 309
 310 /// \ingroup ImageAlgorithms
 311 /// \brief Convolve 1D fixed-size kernel along the columns of image
 312 /// \tparam PixelAccum TODO
 313 /// \tparam SrcView Models ImageViewConcept
 314 /// \tparam Kernel TODO
 315 /// \tparam DstView Models MutableImageViewConcept
 316 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 317 BOOST_FORCEINLINE
 318 void convolve_cols_fixed(
 319     SrcView const& src_view,
 320     Kernel const& kernel,
 321     DstView const& dst_view,
 322     boundary_option option = boundary_option::extend_zero)
 323 {
 324     convolve_rows_fixed<PixelAccum>(
 325         transposed_view(src_view), kernel, transposed_view(dst_view), option);
 326 }
 327
 328 namespace detail
 329 {
 330
 331 /// \ingroup ImageAlgorithms
 332 /// \brief Convolve 1D variable-size kernel along both rows and columns of image
 333 /// \tparam PixelAccum TODO
 334 /// \tparam SrcView Models ImageViewConcept
 335 /// \tparam Kernel TODO
 336 /// \tparam DstView Models MutableImageViewConcept
 337 template <typename PixelAccum, typename SrcView, typename Kernel, typename DstView>
 338 BOOST_FORCEINLINE
 339 void convolve_1d(
 340     SrcView const& src_view,
 341     Kernel const& kernel,
 342     DstView const& dst_view,
 343     boundary_option option = boundary_option::extend_zero)
 344 {
 345     convolve_rows<PixelAccum>(src_view, kernel, dst_view, option);
 346     convolve_cols<PixelAccum>(dst_view, kernel, dst_view, option);
 347 }
 348
 349 template <typename SrcView, typename DstView, typename Kernel>
 350 void convolve_2d_impl(SrcView const& src_view, DstView const& dst_view, Kernel const& kernel)
 351 {
 352     int flip_ker_row, flip_ker_col, row_boundary, col_boundary;
 353     float aux_total;
 354     for (std::ptrdiff_t view_row = 0; view_row < src_view.height(); ++view_row)
 355     {
 356         for (std::ptrdiff_t view_col = 0; view_col < src_view.width(); ++view_col)
 357         {
 358             aux_total = 0.0f;
 359             for (std::size_t kernel_row = 0; kernel_row < kernel.size(); ++kernel_row)
 360             {
 361                 flip_ker_row = kernel.size() - 1 - kernel_row;      // row index of flipped kernel
 362
 363                 for (std::size_t kernel_col = 0; kernel_col < kernel.size(); ++kernel_col)
 364                 {
 365                     flip_ker_col = kernel.size() - 1 - kernel_col; // column index of flipped kernel
 366
 367                     // index of input signal, used for checking boundary
 368                     row_boundary = view_row + (kernel.center_y() - flip_ker_row);
 369                     col_boundary = view_col + (kernel.center_x() - flip_ker_col);
 370
 371                     // ignore input samples which are out of bound
 372                     if (row_boundary >= 0 && row_boundary < src_view.height() &&
 373                         col_boundary >= 0 && col_boundary < src_view.width())
 374                     {
 375                         aux_total +=
 376                             src_view(col_boundary, row_boundary) *
 377                             kernel.at(flip_ker_row, flip_ker_col);
 378                     }
 379                 }
 380             }
 381             dst_view(view_col, view_row) = aux_total;
 382         }
 383     }
 384 }
 385
 386 /// \ingroup ImageAlgorithms
 387 /// \brief convolve_2d can only use convolve_option_extend_zero as convolve_boundary_option
 388 ///  this is the default option and cannot be changed for now
 389 ///  (In future there are plans to improve the algorithm and allow user to use other options as well)
 390 /// \tparam SrcView Models ImageViewConcept
 391 /// \tparam Kernel TODO
 392 /// \tparam DstView Models MutableImageViewConcept
 393 template <typename SrcView, typename DstView, typename Kernel>
 394 void convolve_2d(SrcView const& src_view, Kernel const& kernel, DstView const& dst_view)
 395 {
 396     BOOST_ASSERT(src_view.dimensions() == dst_view.dimensions());
 397     BOOST_ASSERT(kernel.size() != 0);
 398
 399     gil_function_requires<ImageViewConcept<SrcView>>();
 400     gil_function_requires<MutableImageViewConcept<DstView>>();
 401     static_assert(color_spaces_are_compatible
 402     <
 403         typename color_space_type<SrcView>::type,
 404         typename color_space_type<DstView>::type
 405     >::value, "Source and destination views must have pixels with the same color space");
 406
 407     for (std::size_t i = 0; i < src_view.num_channels(); i++)
 408     {
 409         detail::convolve_2d_impl(
 410             nth_channel_view(src_view, i),
 411             nth_channel_view(dst_view, i),
 412             kernel
 413         );
 414     }
 415 }
 416
 417 }}} // namespace boost::gil::detail
 418
 419 #endif