Logo Search packages:      
Sourcecode: scantailor version File versions  Download package

CannyEdgeDetector.cpp

/*
      Scan Tailor - Interactive post-processing tool for scanned pages.
      Copyright (C)  Joseph Artsimovich <joseph.artsimovich@gmail.com>

      This program is free software: you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published by
      the Free Software Foundation, either version 3 of the License, or
      (at your option) any later version.

      This program is distributed in the hope that it will be useful,
      but WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      GNU General Public License for more details.

      You should have received a copy of the GNU General Public License
      along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "CannyEdgeDetector.h"
#include "BinaryImage.h"
#include "GrayImage.h"
#include "Constants.h"
#include "RasterOp.h"
#include "RasterOpGeneric.h"
#include "SeedFill.h"
#include "Connectivity.h"
#include "IntegralImage.h"
#include "MinMaxAccumulator.h"
#include <QRect>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/if.hpp>
#include <cmath>
#include <algorithm>
#include <stdint.h>
#include <assert.h>

#if 0

namespace imageproc
{

BinaryImage cannyEdgeDetector(
      GrayImage const& image, float sigma,
      CannyThresholdingStrategy const& thresholding_strategy)
{
      return cannyEdgeDetector<uint8_t>(
            image.data(), image.size(), image.stride(), sigma, thresholding_strategy
      );
}

namespace canny_impl
{

inline int maxIdx(float values[4])
{
      int const max_01 = values[0] > values[1] ? 0 : 1;
      int const max_23 = values[2] > values[3] ? 2 : 3;
      int const max_0123 = values[max_01] > values[max_23] ? max_01 : max_23;
      return max_0123;
}

BinaryImage nonMaximumSuppression(Grid<Vec2f> const& gradient)
{
      using namespace boost::lambda;

      int const width = gradient.width();
      int const height = gradient.height();

      int const grad_stride = gradient.stride();
      Vec2f const* grad_line = gradient.data() + grad_stride;

      struct PrevNextOffset
      {
            int prev;
            int next;
      };
      PrevNextOffset const offsets[4] = {
            { -1, 1 },
            { -grad_stride, grad_stride },
            { -1 - grad_stride, grad_stride + 1 },
            {  1 - grad_stride, grad_stride - 1 }
      };

      BinaryImage mask(width, height, WHITE);
      int const mask_stride = mask.wordsPerLine();
      uint32_t* mask_line = mask.data() + mask_stride;
      uint32_t const msb = uint32_t(1) << 31;

      for (int y = 1; y < height - 1; ++y) {
            for (int x = 1; x < width - 1; ++x) {
                  Vec2f const grad(grad_line[x]);

                  float const one_over_sqrt2 = float(1.0 / constants::SQRT_2);
                  float dirs[4];
                  dirs[0] = fabs(grad[0]);
                  dirs[1] = fabs(grad[1]);
                  dirs[2] = fabs(one_over_sqrt2 * (grad[0] + grad[1]));
                  dirs[3] = fabs(one_over_sqrt2 * (grad[0] - grad[1]));
                  // All of the 4 above operations are actually dot products
                  // of the gradient vector with various directional unit vectors.

                  int const max_idx = maxIdx(dirs);
                  PrevNextOffset const off(offsets[max_idx]);
                  float const cur = grad_line[x].squaredNorm();
                  float const prev = grad_line[x + off.prev].squaredNorm();
                  float const next = grad_line[x + off.next].squaredNorm();
                  if (cur > prev && cur > next) {
                        // We have a local maximum.
                        mask_line[x >> 5] |= msb >> (x & 31);
                  }
            }

            grad_line += grad_stride;
            mask_line += mask_stride;
      }

      return mask;
}

BinaryImage thresholding(
      Grid<Vec2f>& gradient, BinaryImage const& mask,
      CannyThresholdingStrategy const& thresholding_strategy)
{
      BinaryImage strong_edges;
      BinaryImage all_edges;
      thresholding_strategy.threshold(strong_edges, all_edges, gradient, mask);

      // Weak becomes strong if it's connected to a strong one.
      return seedFill(strong_edges, all_edges, CONN8);
}

// TODO: make it take some kind of a functor that will read the gradient magnitude.
float calcLowerThreshold(
      Grid<Vec2f> const& grid, QRect const rect, double const fraction_below_threshold)
{
      using namespace boost::lambda;

      int const stride = grid.stride();
      MinMaxAccumulator<float> accum;

      Vec2f const* line = grid.data() + rect.top() * stride;
      for (int y = rect.top(); y <= rect.bottom(); ++y, line += stride) {
            for (int x = rect.left(); x <= rect.right(); ++x) {
                  accum(line[x][0]);
            }
      }

      size_t const num_bins = 256;
      std::vector<int> histogram(num_bins);
      double const scale = (num_bins - 1) / accum.max(); // XXX: division by zero

      line = grid.data() + rect.top() * stride;
      for (int y = rect.top(); y <= rect.bottom(); ++y, line += stride) {
            for (int x = rect.left(); x <= rect.right(); ++x) {
                  ++histogram[qRound(line[x][0] * scale)];
            }
      }

      int todo = qRound(rect.width() * rect.height() * fraction_below_threshold);
      size_t i = 0;
      for (; i < num_bins && todo >= 0; ++i) {
            todo -= histogram[i];
      }

      return i * accum.max() / num_bins;
}

} // namespace canny_impl


/*======================== CannyFixedThresholds =========================*/

CannyFixedThresholds::CannyFixedThresholds(float low_threshold, float high_threshold)
: m_lowThreshSq(low_threshold * low_threshold)
, m_highThreshSq(high_threshold * high_threshold)
{
}

void
CannyFixedThresholds::threshold(
      BinaryImage& strong_edges, BinaryImage& all_edges,
      Grid<Vec2f>& gradient, BinaryImage const& mask) const
{
      using namespace boost::lambda;

      QSize const size(gradient.width(), gradient.height());

      // Pre-calculate the squared magnitude of gradient.
      rasterOpGeneric(
            gradient.data(), gradient.stride(), size,
            ret<float&>(_1[0]) = bind(&Vec2f::squaredNorm, _1)
      );

      uint32_t const white = 0;
      uint32_t const black = 1;

      // Get strong edges (in black).
      BinaryImage strong_edges_only(gradient.width(), gradient.height());
      rasterOpGeneric(
            strong_edges_only, gradient.data(), gradient.stride(),
            _1 = if_then_else_return(ret<float const&>(_2[0]) > m_highThreshSq, black, white)
      );

      // Get strong + weak edges (in black).
      BinaryImage strong_plus_weak_edges(gradient.width(), gradient.height());
      rasterOpGeneric(
            strong_plus_weak_edges, gradient.data(), gradient.stride(),
            _1 = if_then_else_return(ret<float const&>(_2[0]) > m_lowThreshSq, black, white)
      );

      rasterOp<RopAnd<RopSrc, RopDst> >(strong_edges_only, mask);
      rasterOp<RopAnd<RopSrc, RopDst> >(strong_plus_weak_edges, mask);

      strong_edges_only.swap(strong_edges);
      strong_plus_weak_edges.swap(all_edges);
}


/*=============== CannyAdaptiveThresholds::LowerThresholdMap ===============*/

class CannyAdaptiveThresholds::LowerThresholdMap
{
public:
      LowerThresholdMap(Grid<Vec2f> const& image, double fraction_below_threshold);

      float operator()(int x, int y) const;
private:
      Grid<float> m_grid;
      int m_segmentWidth;
      int m_segmentHeight;
      int m_subSegmentWidth;
      int m_subSegmentHeight;
};

CannyAdaptiveThresholds::LowerThresholdMap::LowerThresholdMap(
      Grid<Vec2f> const& image, double const fraction_below_threshold)
: m_segmentWidth(0)
, m_segmentHeight(0)
, m_subSegmentWidth(0)
, m_subSegmentHeight(0)
{
      if (image.width() <= 0 || image.height() <= 0) {
            return;
      }

      // XXX: hardcoded constants.
      int const target_hor_segments = 5;
      int const target_vert_segments = 5;
      int const min_sub_segment_width = 40;
      int const min_sub_segment_height = 40;

      int const width = image.width();
      int const height = image.height();

      int num_hor_segments = target_hor_segments;
      int sub_segment_width = width / (num_hor_segments * 2);
      int segment_width = sub_segment_width * 2;
      if (sub_segment_width < min_sub_segment_width) {
            sub_segment_width = min_sub_segment_width;
            segment_width = sub_segment_width * 2;
            num_hor_segments = (width + segment_width - 1) / segment_width;
      }

      int num_vert_segments = target_vert_segments;
      int sub_segment_height = height / (num_vert_segments * 2);
      int segment_height = sub_segment_height * 2;
      if (sub_segment_height < min_sub_segment_height) {
            sub_segment_height = min_sub_segment_height;
            segment_height = sub_segment_height * 2;
            num_vert_segments = (height + segment_height - 1) / segment_height;
      }

      m_segmentWidth = segment_width;
      m_segmentHeight = segment_height;
      m_subSegmentWidth = sub_segment_width;
      m_subSegmentHeight = sub_segment_height;
      Grid<float>(num_hor_segments, num_vert_segments, /*padding=*/1).swap(m_grid);

      // Estimate lower bound for each segment.
      for (int row = 0; row < num_vert_segments; ++row) {
            int const top = row * segment_height;
            int const bottom = std::min<int>(top + segment_height, height); // exclusive
            for (int col = 0; col < num_hor_segments; ++col) {
                  int const left = col * segment_width;
                  int const right = std::min<int>(left + segment_width, width); // exclusive

                  QRect const rect(left, top, right - left, bottom - top);
                  float const lower_threshold = canny_impl::calcLowerThreshold(
                        image, rect, fraction_below_threshold
                  );

                  m_grid(row, col) = lower_threshold;
            }
      }

      // Now fill borders with nearest values from inside the grid.
      m_grid(-1, -1) = m_grid(0, 0);
      m_grid(-1, num_hor_segments) = m_grid(0, num_hor_segments - 1);
      m_grid(num_vert_segments, -1) = m_grid(num_vert_segments - 1, 0);
      m_grid(num_vert_segments, num_hor_segments) = m_grid(num_vert_segments - 1, num_hor_segments - 1);
      for (int col = 0; col < num_hor_segments; ++col) {
            m_grid(-1, col) = m_grid(0, col);
            m_grid(num_vert_segments, col) = m_grid(num_vert_segments - 1, col);
      }
      for (int row = 0; row < num_vert_segments; ++row) {
            m_grid(row, -1) = m_grid(row, 0);
            m_grid(row, num_hor_segments) = m_grid(row, num_hor_segments - 1);
      }
}

float
CannyAdaptiveThresholds::LowerThresholdMap::operator()(int x, int y) const
{
      int const left_segment = x / m_segmentWidth;
      int const right_segment = left_segment + 1;
      int const top_segment = y / m_segmentHeight;
      int const bottom_segment = top_segment + 1;

      double const left_dist = (x - left_segment * m_segmentWidth + 0.5) / m_segmentWidth;
      double const right_dist = (right_segment * m_segmentWidth - 0.5 - x) / m_segmentWidth;
      double const top_dist = (y - top_segment * m_segmentHeight + 0.5) / m_segmentHeight;
      double const bottom_dist = (bottom_segment * m_segmentHeight - 0.5 - y) / m_segmentHeight;
      assert(left_dist > 0.0 && left_dist < 1.0);
      assert(right_dist > 0.0 && right_dist < 1.0);
      assert(top_dist > 0.0 && top_dist < 1.0);
      assert(bottom_dist > 0.0 && bottom_dist < 1.0);

      float threshold = 0;
      threshold += m_grid(top_segment, left_segment) * bottom_dist * right_dist;
      threshold += m_grid(top_segment, right_segment) * bottom_dist * left_dist;
      threshold += m_grid(bottom_segment, left_segment) * top_dist * right_dist;
      threshold += m_grid(bottom_segment, right_segment) * top_dist * left_dist;

      return threshold;
}


/*======================== CannyAdaptiveThresholds =========================*/

CannyAdaptiveThresholds::CannyAdaptiveThresholds(QSize const& neighbourhood)
: m_neighbourhood(neighbourhood)
{
}

void
CannyAdaptiveThresholds::threshold(
      BinaryImage& strong_edges, BinaryImage& all_edges,
      Grid<Vec2f>& gradient, BinaryImage const& mask) const
{
      using namespace std;
      using namespace boost::lambda;

      int const width = gradient.width();
      int const height = gradient.height();

      // Pre-calculate the magnitude of gradient.
      rasterOpGeneric(
            gradient.data(), gradient.stride(), QSize(width, height),
            ret<float&>(_1[0]) = bind(&Vec2f::norm, _1)
      );

      //float const low_threshold = canny_impl::calcLowerThreshold(gradient, QRect(0, 0, width, height), 0.7);
      //float const high_threshold = 1.2f * low_threshold;

      LowerThresholdMap const lower_threshold_map(gradient, 0.7);

      int const grid_stride = gradient.stride();
      Vec2f const* grid_line = gradient.data();

      BinaryImage low_thresh_img(mask);
      int const low_thresh_stride = low_thresh_img.wordsPerLine();
      uint32_t* low_thresh_line = low_thresh_img.data();

      BinaryImage high_thresh_img(mask);
      int const high_thresh_stride = high_thresh_img.wordsPerLine();
      uint32_t* high_thresh_line = high_thresh_img.data();

      uint32_t const msb = uint32_t(1) << 31;
      for (int y = 0; y < height; ++y) {
            for (int x = 0; x < width; ++x) {
                  float const low_threshold = lower_threshold_map(x, y);
                  float const high_threshold = low_threshold + 5.f;
                  float const mag = grid_line[x][0];

                  if (mag < low_threshold) {
                        low_thresh_line[x >> 5] &= ~(msb >> (x & 31));
                  }
                  if (mag < high_threshold) {
                        high_thresh_line[x >> 5] &= ~(msb >> (x & 31));
                  }
            }

            grid_line += grid_stride;
            low_thresh_line += low_thresh_stride;
            high_thresh_line += high_thresh_stride;
      }

      high_thresh_img.swap(strong_edges);
      low_thresh_img.swap(all_edges);
}

} // namespace imageproc

#endif

Generated by  Doxygen 1.6.0   Back to index