Как найти осевую линию двумерной длинной области

Question

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

Спасибо за любые полезные ответы.

Answer 1

[Я сделал это отдельным ответом, потому что подход слишком отличается]

Этот подход применим для рек без ответвлений:

1. Извлечение "левой" и "правой" границыв виде последовательностей координат пикселей
2. Найти соответствие между пикселями от левой и правой границ (например, при динамическом программировании)
3. Определить точки центральной линии как средние точки между двумя соответствующими левой и правой точками

Редактировать:

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

Пример поиска такой последовательности описан здесь: http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 2

Попробуйте найти «Скелетонизация».Примерно это извлечение центральных линий из графических объектов.Для этого есть несколько алгоритмов:

1. постепенно удаляют пиксели, которые не являются частью скелета: http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/azar/skeleton.html#define
2. отправка волны от границ объекта внутрь и поиск самосогласований
3. отправка волны с некоторой части объекта и поиск середины фронта волны