Сшивка линий с эффективным использованием памяти на очень больших изображениях

Предпосылки

Я работаю с очень большими наборами данных со спутников радаров с синтезированной апертурой. Их можно рассматривать как полутоновые изображения с широким динамическим диапазоном порядка 10 тыс. Пикселей на стороне.

Недавно я разрабатывал приложения одномасштабного варианта метода алгоритма обнаружения гребней в пространстве масштабов Линдеберга. для обнаружения линейных особенностей на изображении SAR. Это улучшение по сравнению с использованием направленных фильтров или преобразования Хафа - методов, которые использовались ранее, поскольку они менее затратны в вычислительном отношении, чем любой из них. (Я представлю некоторые недавние результаты на JURSE 2011 в апреле, и я могу загрузить препринт, если это будет полезно).

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

struct ridge_t { unsigned char top, left, bottom, right };
int rows, cols;
struct ridge_t *ridges;  /* An array of rows*cols ridge entries */

Запись в гребнях содержит сегмент гребня, если ровно два из верхних , left , right и bottom имеют значения в диапазоне от 0 до 128. Предположим, у меня есть:

ridge_t entry;
entry.top = 25; entry.left = 255; entry.bottom = 255; entry.right = 76;

Затем я могу найти начало сегмента гребня (x1 , y1) и end (x2, y2):

float x1, y1, x2, y2;
x1 = (float) col + (float) entry.top / 128.0;
y1 = (float) row;
x2 = (float) col + 1;
y2 = (float) row + (float) entry.right / 128.0;

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

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

Тривиально определить, соединены ли два соседних места, содержащие сегменты гребня. Если у меня есть ridge1 в (x, y) и ridge2 в (x + 1, y), то они являются частями одной линии, если 0 ridge1.right и ridge2.left = ridge1.right .

Задача

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

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

Что читатели предлагают в качестве возможного подхода? Похоже, что в прошлом кто-то придумал эффективный способ сделать ...