Найти туннель "осевой линии"?

Question

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

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

Любые идеи о том, как я мог бы сделать это?

Answer 1

---

«Алгоритм», который хорошо работает с локализованными изменениями данных.

---

Взгляд критика

Благо

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

Плохой

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

И Гадкий

Уродливая часть в том, что вам нужно иметь возможность заливать карту, что не всегда возможно. Несколько дней назад я опубликовал комментарий с вопросом, можно ли заполнить ваши графики, но ответа не получил. Поэтому я решил опубликовать его в любом случае.

---

Эскиз

Идея такова:

1. Использование обработки изображений для получения тонкой линии пикселей, представляющих центральную траекторию
2. Разделение изображения на куски, соразмерное с туннелем самых тонких проходов
3. В каждом разделе представить точку в «центре масс» содержащихся пикселей
4. Используйте эти пиксели для представления вершин графика
5. Добавление ребер в график на основе политики «ближнего соседа»
6. Убрать паразитные маленькие циклы в индуцированном графике
7. Конец - Остальные края представляют желаемый путь

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

---

Участок

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

A- Начните с красивого туннеля с заливным изображением

B- Применить преобразование расстояния

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

C- Свернуть изображение с соответствующим ядром

Выбранное ядро ​​является ядром Лапласа Гаусса радиуса пикселя 2. Оно обладает магическим свойством усиления краев уровня серого, как вы можете видеть ниже.

D - обрезание уровней серого и бинаризация изображения

Чтобы получить красивый вид на центральную линию!

Комментарий

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

E- раздел изображения

Вот когда появляются некоторые преимущества алгоритма: вы можете начать использовать параллельную обработку или решить обрабатывать каждый сегмент за раз. Вы также можете сравнить полученные сегменты с предыдущим прогоном и повторно использовать предыдущие результаты

F- Центр обнаружения масс

Все белые точки в каждом подизображении заменены только одной точкой в ​​центре масс.
X<sub>CM</sub> = (&Sigma; <sub>i∈<i>Points</i></sub> X<sub>i</sub>)/NumPoints<br>
Y<sub>CM</sub> = (&Sigma; <sub>i∈<i>Points</i></sub> Y<sub>i</sub>)/NumPoints

Белые пиксели плохо различимы (асимптотическитрудно с параметром "а" возраст ), но там они есть.

G- Настройка графика из вершин

Сформируйте график, используя выбранные точки в качестве вершины.Все еще нет краев.

H- выберите края-кандидаты

Используя евклидово расстояние между точками, выберите подходящие ребра.Отсечение используется для выбора подходящего набора ребер.Здесь мы используем 1,5 субизображения.

Как видите, в полученном графике есть несколько небольших циклов, которые мы собираемся удалить на следующем шаге.

H- УдалитьМалые циклы

Используя процедуру обнаружения циклов, мы удаляем небольшие циклы до определенной длины.Длина отсечения зависит от нескольких параметров, и вы должны определить ее эмпирически для своего семейства графиков

I- Вот и все!

Вы можете видеть, что результирующая центральная линия смещена немного вверх.Причина в том, что я наложил изображения различного типа в Mathematica ... и я перестал пытаться убедить программу делать то, что я хочу:)

---

Несколько выстрелов

Во время тестирования я собрал несколько изображений.Это, наверное, самые не туннельные вещи в мире, но мои Туннели-101 сбились с пути.

Во всяком случае, вот они.Помните, что у меня смещение на несколько пикселей вверх ...

HTH!

.

Обновление

На всякий случай, если у вас есть доступ к Mathematica 8 (я получил его сегодня), есть новая функция Разбавление .Просто посмотрите:

Answer 2

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

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

Answer 3

Скважина в Python с использованием пакета skimage Это простая задача, как указано ниже.

import pylab as pl
from skimage import morphology as mp

tun = 1-pl.imread('tunnel.png')[...,0]        #your tunnel image
skl = mp.medial_axis(tun)                     #skeleton

pl.subplot(121)
pl.imshow(tun,cmap=pl.cm.gray)
pl.subplot(122)
pl.imshow(skl,cmap=pl.cm.gray)
pl.show()