Расчет длины объектов в двоичном изображении - алгоритм

Question

Мне нужно рассчитать длину объекта в двоичном изображении (максимальное расстояние между пикселями внутри объекта). Поскольку это двоичное изображение, мы можем рассматривать его как двумерный массив со значениями 0 (белый) и 1 (черный). Мне нужен умный (и желательно простой) алгоритм для выполнения этой операции. Помните, что на изображении много объектов.

Изображение для уточнения:

альтернативный текст http://cl.ly/489019a048c1bf20c6bb/content

Пример входного изображения:

альтернативный текст http://cl.ly/f5c379e59deef435f365/content

Answer 1

Я думаю, что проблема проста, если граница объекта выпуклая и нет трех вершин на линии (т.е. ни одна вершина не может быть удалена без изменения многоугольника): тогда вы можете просто выбрать две точки случайным образом и использовать простой поиск типа градиентного спуска, чтобы найти самую длинную строку:

Start with random vertices A, B
See if the line A' - B is longer than A - B where A' is the point left of A; if so, replace A with A'
See if the line A' - B is longer than A - B where A' is the point right of A; if so, replace A with A'
Do the same for B
repeat until convergence

Так что я бы предложил найти выпуклую оболочку для каждого начального объекта, удалив все вершины «излишков» (чтобы обеспечить сходимость) и запустив алгоритм, описанный выше.

Построение выпуклой оболочки - это операция O (n log n) IIRC, где n - количество граничных пикселей. Должно быть довольно эффективным для небольших объектов, подобных этим. РЕДАКТИРОВАТЬ : Я только что вспомнил, что O (n log n) для алгоритма выпуклой оболочки была необходима для сортировки точек. Если граничные точки являются результатом анализа подключенных компонентов, они уже отсортированы. Таким образом, весь алгоритм должен выполняться за O (n) время, где n - количество граничных точек. (Тем не менее, это большая работа, потому что вам, возможно, придется написать собственный алгоритм выпуклой оболочки или изменить его, чтобы пропустить сортировку.)

Добавить: Ответ на комментарий

Если вам не нужна точность 100%, вы можете просто подогнать эллипс к каждому шарику и рассчитать длину большой оси: это можно вычислить из центральных моментов (IIRC это просто квадрат корень, если наибольшее собственное значение ковариационной матрицы), поэтому это операция O (n), которая может быть эффективно рассчитана за один проход по изображению. У него есть дополнительное преимущество, заключающееся в том, что он учитывает все пиксели большого двоичного объекта, а не только две экстремальные точки, т. Е. На него гораздо меньше влияет шум.

Answer 2

Найдите длину главной оси эллипса, который имеет те же самые нормализованные вторые центральные моменты, что и область. В MATLAB вы можете использовать regionprops.

Answer 3

Я бы предложил попробовать "обратное" преобразование расстояния. В волшебном мире математической морфологии (извините, я не смог устоять перед аллитерацией), преобразование расстояния дает вам самое близкое расстояние каждого пикселя до ближайшего граничного пикселя. В вашем случае вас интересует самое дальнее расстояние до граничного пикселя, поэтому я ловко применил «обратный» префикс.

Вы можете найти информацию о дистанционном преобразовании здесь и здесь . Я полагаю, что Matlab реализует преобразование расстояния согласно здесь . Это привело бы меня к мысли, что вы можете найти реализацию преобразования расстояния с открытым исходным кодом в октава . Кроме того, меня ничуть не удивило бы, если бы opencv реализовал это.

Я не задумывался об этом, но мне было интуитивно понятно, что вы должны иметь возможность обратить преобразование расстояния и рассчитать его примерно за то же время, что и исходное преобразование расстояния.

Answer 4

Я думаю, вы могли бы рассмотреть использование алгоритма поиска в ширину .

Основная идея состоит в том, что вы перебираете каждую строку и столбец изображения, и если вы еще не посетили узел (узел - это строка и столбец с цветным пикселем), то сначала нужно запустить ширину поиск. Вы бы посещали каждый узел, который могли, и отслеживали максимальные и минимальные точки для объекта.

Вот пример кода C ++ (не проверен):

#include <vector>
#include <queue>
#include <cmath>
using namespace std;

// used to transition from given row, col to each of the
// 8 different directions
int dr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dc[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

// WHITE or COLORED cells
const int WHITE = 0;
const int COLORED = 1;

// number of rows and columns
int nrows = 2000;
int ncols = 2000;

// assume G is the image
int G[2000][2000];

// the "visited array"
bool vis[2000][2000];

// get distance between 2 points
inline double getdist(double x1, double y1, double x2, double y2) {
  double d1 = x1 - x2;
  double d2 = y1 - y2;
  return sqrt(d1*d1+d2*d2);
}

// this function performs the breadth first search
double bfs(int startRow, int startCol) {
  queue< int > q;

  q.push(startRow);
  q.push(startCol);

  vector< pair< int, int > > points;

  while(!q.empty()) {
    int r = q.front();
    q.pop();
    int c = q.front();
    q.pop();

    // already visited?
    if (vis[r][c])
      continue;


    points.push_back(make_pair(r,c));     

    vis[r][c] = true;

    // try all eight directions
    for(int i = 0; i < 8; ++i) {
      int nr = r + dr[i];
      int nc = c + dc[i];

      if (nr < 0 || nr >= nrows || nc < 0 || nc >= ncols)
        continue; // out of bounds

      // push next node on queue  
      q.push(nr);
      q.push(nc);

    }    
  }

  // the distance is maximum difference between any 2 points encountered in the BFS
  double diff = 0;
  for(int i = 0; i < (int)points.size(); ++i) {
    for(int j = i+1; j < (int)points.size(); ++j) {
      diff = max(diff,getdist(points[i].first,points[i].second,points[j].first,points[j].second));
    }
  }
  return diff;
}

int main() {

  vector< double > lengths;

  memset(vis,false,sizeof vis);  
  for(int r = 0; r < nrows; ++r) {
    for(int c = 0; c < ncols; ++c) {
      if (G[r][c] == WHITE)
        continue; // we don't care about cells without objects
      if (vis[r][c])
        continue; // we've already processed this object

      // find the length of this object
      double len = bfs(r,c);
      lengths.push_back(len);
    }
  }

  return 0;
}

Answer 5

Очень грубый подход с использованием грубой силы должен был бы сначала идентифицировать все краевые пиксели (любой черный пиксель в объекте, смежном с не черным пикселем) и вычислить расстояния между всеми возможными парами краевых пикселей. Самое длинное из этих расстояний даст вам длину объекта.

Если объекты всегда имеют форму, подобную имеющейся в вашем образце, вы можете ускорить это, оценивая только пиксели с самыми высокими и самыми низкими значениями x и y внутри объекта.