#algorithm #image-processing
#алгоритм #обработка изображений
Вопрос:
Я хочу реализовать быстрый алгоритм для прореживания двоичного изображения. (https://en.wikipedia.org/wiki/Thinning_ (морфология))
Я знаю об алгоритмах Чжан-Суена и Го-Холла, но они очень медленные, поскольку выполняют несколько проходов по всему изображению.
Я нашел этот сайт (https://sites.google.com/site/rameyarnaud/research/c/voronoi ), который объявляет о более быстрых реализациях, основанных на идее эволюции только пикселов контура. Предположительно, этот подход приводит к линейному (по количеству пикселей)) или слегка сверхлинейному времени обработки (при условии, что каждый проход занимает время, пропорциональное длине текущих контуров, в конечном итоге равное размеру скелета).
С другой стороны, я знаю, что скелет соответствует гребням на карте расстояний, а (морфологическая) карта расстояний может быть вычислена за линейное время. ПОЭТОМУ я подозреваю, что при локальной обработке карты расстояний скелет может быть обнаружен, но я точно не знаю, как это сделать.
Итак, мои вопросы:
- знаете ли вы, как определить пиксели скелета на карте расстояний, или
- знаете ли вы опубликованный алгоритм для выполнения прореживания за линейное время?
Комментарии:
1. Вам нужен довольно гладкий скелет или фактическая медиальная ось? Последний довольно чувствителен к шуму на границе.
2. Возможно, полезно для вашего первого вопроса: en.wikipedia.org/wiki/Ridge_detection
3. Похоже, он делает один проход по всем пикселям, чтобы получить таблицу координат пикселей тела, соприкасающихся с не-телом. Теперь он может перемещаться по таблице, чтобы применить правила прореживания только к пикселям тела, которые могут быть удалены. Когда он удаляет один, относительно легко обновить таблицу, если она правильно сохранена, например, с помощью ключей Мортона ( en.wikipedia.org/wiki/Z-order_curve ).
4. @NicoSchertler: Я использую «Эффективное двоичное прореживание изображений с использованием карт окрестностей Джозефа М. Сайхоша, Graphics Gems IV», сам основанный на алгоритме Розенфельда, который имеет приемлемое поведение. Я предполагаю, что он имеет тип MAT. Вы можете подтвердить?
5. @samgak: может быть, но я предполагаю, что должен быть специальный способ поиска гребней на этих картах расстояний.