src/seam.cc

   1 #include <cmath>
   2 #include <limits>
   3 #include <vector>
   4
   5 #include <mln/border/duplicate.hh>
   6 #include <mln/geom/ncols.hh>
   7 #include <mln/geom/nrows.hh>
   8 #include <mln/literal/colors.hh>
   9
  10 #include "all.hh"
  11
  12 using namespace mln;
  13
  14 /// Generic 3-argument implementation of \c min.
  15 template <typename T>
  16 static inline
  17 const T&
  18 min (const T& v1, const T& v2, const T& v3)
  19 {
  20   return std::min (v1, std::min (v2, v3));
  21 }
  22
  23 /** \internal
  24  *  \param nrg The energy in a given image.
  25  *  \return an image that contains the cumulative minimum energy for all
  26  *  possible connected seam in \a nrg.  Implements the function \c M
  27  *  described in the paper of Avidan and Shamir, section 3.
  28  */
  29 static inline
  30 image2d<float>
  31 accumulate_nrg (const image2d<float> nrg)
  32 {
  33   image2d<float> accu (nrg.domain ());
  34   border::duplicate (nrg);
  35   unsigned cols = geom::ncols (nrg);
  36   unsigned rows = geom::nrows (nrg);
  37
  38   // Initialize the first line with the nrg
  39   for (unsigned c = 0; c < cols; ++c)
  40     accu.at (0, c) = nrg.at (0, c);
  41
  42   for (unsigned r = 1; r < rows; ++r)
  43     for (unsigned c = 0; c < cols; ++c)
  44       accu.at (r, c) = nrg.at (r, c)
  45         + min (accu.at (r - 1, c - 1),
  46                accu.at (r - 1, c),
  47                accu.at (r - 1, c + 1));
  48   return accu;
  49 }
  50
  51 /** \internal
  52  *  \return the minimum value on the \a row of \a accu_nrg, by considering
  53  *  only the values in the range [ \a colmin .. \a colmax [.
  54  */
  55 static inline
  56 unsigned
  57 get_min_nrg_on_row (const image2d<float> accu_nrg, unsigned row,
  58                     unsigned colmin, unsigned colmax)
  59 {
  60   assert (colmin < colmax);
  61   float nrg = std::numeric_limits<float>::max ();
  62   unsigned c = colmin;
  63   unsigned mincol = colmin;
  64
  65   for (; c < colmax; ++c)
  66     if (accu_nrg.at (row, c) < nrg)
  67     {
  68       nrg = accu_nrg.at (row, c);
  69       mincol = c;
  70     }
  71   return mincol;
  72 }
  73
  74 /** \internal
  75  * \return the minimum value on the \a row of \a accu_nrg.
  76  */
  77 static inline
  78 unsigned
  79 get_min_nrg_on_row (const image2d<float> accu_nrg, unsigned row)
  80 {
  81   return get_min_nrg_on_row (accu_nrg, row, 0, geom::ncols (accu_nrg));
  82 }
  83
  84 /** \internal
  85  *  Find the path of the seam in an image containing the cumulative minimum
  86  *  energy.
  87  *  \param accu_nrg The cumulative minimum energy for all possible connected
  88  *  seam (called \c M in the paper of Avidan and Shamir, section 3).
  89  */
  90 static inline
  91 std::vector<unsigned>
  92 find_path (const image2d<float> accu_nrg)
  93 {
  94   unsigned rows = geom::nrows (accu_nrg);
  95   unsigned cols = geom::ncols (accu_nrg);
  96   assert (rows > 1);
  97   std::vector<unsigned> seam_path (rows);
  98
  99   // Find the minimum on the last line
 100   seam_path.at (rows - 1) = get_min_nrg_on_row (accu_nrg, rows - 1);
 101
 102   // Find the path by following the minimums backwards
 103   unsigned r = rows - 1;
 104   do {
 105     assert (r > 0);
 106     unsigned cur_col = seam_path.at (r);
 107     --r;
 108     seam_path.at (r) = get_min_nrg_on_row (accu_nrg, r,
 109                                            cur_col ? cur_col - 1 : 0U,
 110                                            std::min (cur_col + 2, cols));
 111   } while (r);
 112
 113   return seam_path;
 114 }
 115
 116 std::vector<unsigned>
 117 find_vertical_seam (const image2d<float> nrg)
 118 {
 119   image2d<float> accu_nrg = accumulate_nrg (nrg);
 120   std::vector<unsigned> seam_path = find_path (accu_nrg);
 121   return seam_path;
 122 }
 123
 124 template <typename T>
 125 image2d<T>
 126 carve_vertical_seam (const image2d<T> img, const std::vector<unsigned>& path)
 127 {
 128   unsigned cols = geom::ncols (img);
 129   unsigned rows = geom::nrows (img);
 130   image2d<T> carved (rows, cols - 1);
 131   typename image2d<T>::fwd_piter p (img.domain ());
 132
 133   for (unsigned r = 0; r < rows; ++r)
 134   {
 135     unsigned seam_at_col = path.at (r);
 136     for (unsigned c = 0; c < seam_at_col; ++c)
 137       carved.at (r, c) = img.at (r, c);
 138     for (unsigned c = seam_at_col; c < cols; ++c)
 139       carved.at (r, c) = img.at (r, c + 1);
 140   }
 141
 142   return carved;
 143 }
 144
 145 // Instantiate for the types we use.
 146 template image2d<rgb8>
 147 carve_vertical_seam<rgb8>(const image2d<rgb8> img,
 148                           const std::vector<unsigned>& path);
 149 template image2d<float>
 150 carve_vertical_seam<float>(const image2d<float> img,
 151                            const std::vector<unsigned>& path);
 152
 153 image2d<rgb8>
 154 uncarve_vertical_seam (const image2d<rgb8> img, const std::vector<unsigned>& path)
 155 {
 156   unsigned cols = geom::ncols (img);
 157   unsigned rows = geom::nrows (img);
 158   image2d<rgb8> uncarved (rows, cols + 1);
 159   image2d<rgb8>::fwd_piter p (img.domain ());
 160
 161   for (unsigned r = 0; r < rows; ++r)
 162   {
 163     unsigned seam_at_col = path.at (r);
 164     for (unsigned c = 0; c < seam_at_col; ++c)
 165       uncarved.at (r, c) = img.at (r, c);
 166     uncarved.at (r, seam_at_col) = mln::literal::red;
 167     for (unsigned c = seam_at_col; c < cols; ++c)
 168       uncarved.at (r, c + 1) = img.at (r, c);
 169   }
 170
 171   return uncarved;
 172 }