Бинаризация рукописного лабиринта
 

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

• Если ветка маршрута имеет один и более поворотов, она помечается синим цветом
• Если ветка маршрута имеет один и более тупиков, она помечается красным цветом
• Если ветка маршрута имеет хотя бы один поворот, она не может иметь более одного тупика

На матрице MxN жук благополучно проходит весь маршрут до конца, попутно составляя строку токенов (фигурки тетрамино и пентамино), что отображено в gif-анимации. Проблема только в одном: Жук может двигать по пути шириной в 1 пиксел. Следовательно, имеется редактор лабиринтов.

Вопрос: Какие фильтры следует применять, если лабиринт нарисован от руки маркером или мелом на доске под любым углом?:write:
Уточнения: В самом начале виден корявый лабиринт, нарисованый от руки в Paint. Потом он оквадрачивается в матрицу (всё прорисовал вручную, каждый кадр).:-?
Варианты: Пробовал классический FloodFill с составлением массива координат линий заливки - слишком много данных и не знаю, как систематизировать. Хотел применять алгоритм чтения QR-кода, но мне не нужны три ключевых квадрата на углах.:agree: Так же пытался пустить жука с "радаром", который двигается в направлении дальнего горизонта и составляет список поворотов, но не смог сформулировать в скрипте (js+canvas). А выгугленный алгоритм использует уже бинаризованый лабиринт с шагом в 1 пиксел.

Спасибо!

вероятно, Line fitting, или методы аппроксимации набора точек прямой

Что касается обхода лабиринта - отдельная тема. Я бегло посмотрел статью. На первый взгляд ни о чем :)
См. в сторону
1. Неинформированные методы поиска (в пространстве состояний)
2. Информированные методы поиска (в пространстве состояний)
3. Визуализация работы информированных методов поиска

---

Если интересно, почти все неинформированные методы я реализовал в рамках своего проекта
https://github.com/nervgh/recursive-iterator
http://javascript.ru/forum/project/5...-iterator.html

Информированные(й) в рамках форка (на скорую руку)
http://javascript.ru/forum/project/1...tml#post377012

Думаю, меня не совсем так поняли.:)
Нужно кривой лабиринт, нарисованый на бумаге и захваченый WebCamer'ой в режиме реального времени обойти. Мой "жук" его обходит только в случае, когда путь имеет ширину в 1 пиксел.
Тем самым, мне нужен фильтр, который не просто векторизирует растровую размазню 1:1, а просто составляет список координат горизонтальных и вертикальных коридоров.

Вот как на анимашке ниже:
Сначала - два варианта одного лабиринта от руки (кривой и ещё кривее), а потом ровные фиолетовые линии. В конце - многократный зум микроскопического лабиринта 14x10 пикселей.:dance:
Т.е. мне надо изображение 128x110 аккуратно уменьшить до 14x10, сохранив структуру маршрута для жука.
(построчная заливка и прочие методы не дают нужного результата)

Спасибо!:thanks:

ответ на этот вопрос в первом предложении моего предыдущего поста

Хм. Извиняюсь.
Я привык работать с растровыми изображениями (типа используя mmx/sse на ассемблере фильтровать кадры), а вот векторные алгоритмы - тёмное дело. Вот что выдаёт мой скрипт в окне FireFox. Некоторые линии прорисовываются дважды.

Алгоритм: Нахожу первую чёрную точку.

1. Используя Math sin/cos по всему радиусу определяю максимально длинную линию, запоминая её координаты
2. Разбиваю всю линию на массив отдельных точек и, как в пункте 1, по всему радиусу ищу максимум

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

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

В идеале (в бинарном массиве) формируется таблица декодирования (в матрице жук её формирует):

• ESWN (EAST + SOUTH + WEST + NORTH) (UpperCase - путь имеет повороты) - старт-кольцо
• wsn или wns (west + south + north или west + south + north) (LowerCase - путь имеет тупики) - фигурка ├ тетриса
• WN (WEST + NORTH) - фигурка └ тетриса
• N (NORTH) - фигурка │ тетриса
• WS - фигурка ┌
• NWS
• sw
• SE
• en
• SEN

В итоге получается "├└│┌⊓┤└┴⊔" в массиве 14x10.

Paguo-86PK, ok, я тебя понял. Моя ссылкабыла немного про другое.

Не знаю зачем тебе это надо, но задача любопытная :)

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

Описываю ниже свое понимание
Упрощенный вариант
1. определить размер кисти
2. выпрямить линии
3. сжать до "однопиксельных" размеров


Попытаюсь описать как
на примере конкретно взятой линии
- имеем точки, описывающие линию (A - начало, B - конец)
- строим вектор AB по этим точкам (выделено зеленым)
- помещаем его в двумерную координатную плоскость (x-y) так, как показано на рисунке
- т.о. теперь имеем три вектора OX, OY, AB
- ищем угол между векторами OX & AB
- ищем угол между векторами OY & AB
- сравниваем углы, какой меньше, в ту сторону и выпрямляем
- выпрямление происходит на длину вектора согласно шагу кисти

https://yadi.sk/d/K63ZmF-1iR4up

Ну, что, товарищи, кто
1. расставит на этом (original) безобразии опорные точки (pivot_points)
2. и представит его в виде векторов (линий)
? :)

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

Алгоритм - бета-вариант
 

Я это примерно и делаю.

Чтобы не быть голословным, в архиве - мой сырейщий алгоритм (работает лишь в Opera 12 и FireFox почему-то:blink: А chrome только с --disable-web-security) и gif-лабиринт, который выдаёт пачку дублирующих линий. Нужно, как в п.1, определить размер кисти и учитывать его.

(в gif'ке первый кадр я подправил так, чтобы чтение начиналось с нужной позиции: В идеале, чтение начинается с кольца (восток+юг+запад+север) и если в кадре лабиринт перевёрнут, алгоритм должен это учитывать. Но до этого пока очень далеко)