Fast, Exact Euclidean Distance Transform, Linear Complexity

[thevinn]

Is this useful?

FAST AND EXACT SIGNED EUCLIDEAN DISTANCE TRANSFORMATION WITH LINEAR COMPLEXITY

[anthony]

Interesting. But distance is already a two pass algorithm or O(n), unless 'constrained'. This seems to rely on heavy parrellel processing. I would have to read more thoughly, but it is low priority on my already heavy to-do list.

[thevinn]

The original link turned out to be bunk. I found another paper that reviews the latest exact distance transform methods, here's that paper:

2D Euclidean Distance Transform Algorithms, A Comparative Survey

Based on the work in the paper, I chose the algorithm described by Meijster, Roerdink, and Hesselink:

A General Algorithm for Computing Distance Transforms in Linear Time

The paper was straightforward, and I was able to roll my own version of it using generic programming:

Code: Select all

struct EuclideanMetric
{
  static inline int f (int x_i, int gi) noexcept
  {
    return (x_i*x_i)+gi*gi;
  }

  static inline int sep (int i, int u, int gi, int gu, int) noexcept
  {
    return (u*u - i*i + gu*gu - gi*gi) / (2*(u-i));
  }
};

struct ManhattanMetric
{
  static inline int f (int x_i, int gi) noexcept
  {
    return abs (x_i) + gi;
  }

  static inline int sep (int i, int u, int gi, int gu, int inf) noexcept
  {
    if (gu >= gi + u - i)
      return inf;
    else if (gi > gu + u - i)
      return -inf;
    else
      return (gu - gi + u + i) / 2;
  }
};

struct ChessMetric
{
  static inline int f (int x_i, int gi) noexcept
  {
    return jmax (abs (x_i), gi);
  }

  static inline int sep (int i, int u, int gi, int gu, int) noexcept
  {
    if (gi < gu)
      return jmax (i+gu, (i+u)/2);
    else
      return jmin (u-gi, (i+u)/2);
  }
};

template <class Functor, class BoolImage, class Metric>
static void calculate (Functor f, BoolImage test, int const m, int n, Metric metric)
{
  std::vector <int> g (m * n);

  int const inf = m + n;

  // phase 1
  {
    for (int x = 0; x < m; ++x)
    {
      g [x] = test (x, 0) ? 0 : inf;

      // scan 1
      for (int y = 1; y < n; ++y)
      {
        int const ym = y*m;
        g [x+ym] = test (x, y) ? 0 : 1 + g [x+ym-m];
      }

      // scan 2
      for (int y = n-2; y >=0; --y)
      {
        int const ym = y*m;

        if (g [x+ym+m] < g [x+ym])
          g [x+ym] = 1 + g[x+ym+m];
      }
    }
  }

  // phase 2
  {
    std::vector <int> s (jmax (m, n));
    std::vector <int> t (jmax (m, n));

    for (int y = 0; y < n; ++y)
    {
      int q = 0;
      s [0] = 0;
      t [0] = 0;

      int const ym = y*m;

      // scan 3
      for (int u = 1; u < m; ++u)
      {
        while (q >= 0 && metric.f (t[q]-s[q], g[s[q]+ym]) > metric.f (t[q]-u, g[u+ym]))
          q--;

        if (q < 0)
        {
          q = 0;
          s [0] = u;
        }
        else
        {
          int const w = 1 + metric.sep (s[q], u, g[s[q]+ym], g[u+ym], inf);

          if (w < m)
          {
            ++q;
            s[q] = u;
            t[q] = w;
          }
        }
      }

      // scan 4
      for (int u = m-1; u >= 0; --u)
      {
        int const d = metric.f (u-s[q], g[s[q]+ym]);
        f (u, y, d);
        if (u == t[q])
          --q;
      }
    }
  }
}

My code example has no external dependencies aside from the Standard C++ Template Library and will work with any type of images, with suitable choice of types for Functor and BoolImage.

Here's a screenshot of my demo application which uses the EDT as the first step of the Bevel and Emboss style:



This is my open source project for implementing Layer Styles (my code is MIT licensed):

LayerEffects on Github

And the downloads:

Ready to run executables: