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

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

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

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

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

Вот пример кода на 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;
}

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

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

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

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