Растровые пути следуя алгоритмам

Question

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

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

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

Есть идеи?

Answer 1

Самой простой идеей, вероятно, является использование A * алгоритма , где каждый пиксель является узлом, а стоимость узла - темной пикселой.

Обновление: найдено хорошее учебник .

Answer 2

Один из способов сделать это:

1. Отфильтруйте изображение, чтобы приблизить его к черно-белым пикселям.
2. Нарисуйте линию через белые пиксели. Для этого начните с белого пикселя. Нарисуйте линию от этого пикселя до каждого белого пикселя на расстоянии 2 (или около 3), но игнорируйте пиксели около предыдущей линии. Продолжайте, пока не закроете каждый пиксель не близко (2 или 3 пикселя) от линии. Вам придется внести некоторые незначительные корректировки, чтобы он работал хорошо.
3. Соедините конечные точки линий, которые вы нарисовали. Если рядом находятся две конечные точки (1 или 2 пикселя?), Соедините их. Вы должны получить несколько строк, состоящих из множества коротких сегментов, возможно, с несколькими петлями и вилками.
4. Избавьтесь от любых маленьких петель в линиях и разделите линии на вилках, чтобы у вас было несколько линий, состоящих из множества коротких сегментов.
5. Уменьшить очки. Для каждой линии проверьте, является ли она почти прямой. Если так, удалите все внутренние пункты. Если нет, то рекурсивно проверяйте две половины линии, пока не дойдете до минимальной длины сегмента.
6. При желании вы можете разместить сплайн-кривую по линиям в этой точке.
7. Прибыль.

Потребуется некоторая настройка, чтобы заставить его работать хорошо, но это возможно сделать таким образом. Еще один вариант - обвести белые участки, если они шире, чем 1, 2 или 3 пикселя, и затем объединить двойные линии.

Answer 3

Если вы делаете это в больших масштабах или для исследования, вы можете попробовать ничуть http://en.wikipedia.org/wiki/Ant_colony_optimization,, но если вы делаете это за деньги, просто возьмите что-то вроде заливки http://en.wikipedia.org/wiki/Flood_fill

Answer 4

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

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