В предыдущем посте всё ушло в формулирование текущего состояния. Обещанная тема "Линейного МРП-преобразования" даже не была затронута. Поэтому продолжим.
Основным методом анализа и характеризации линии является сканирование следованием по её скелетону. Пример простой линии с обозначенным белыми точками скелетоном дан на Fig. 3. Программа обозначила чуть смещённым «фантомный образ» оригинала, построенный в процессе следования по скелетону с использованием рангов МРП-точек.
Следуя «из конца в конец» простой линии и подсчитывая текущее соотношение единичных шагов по направлению Y (dy) и по направлению X (dx), оценивая стабильность или переменчивость этого соотношения по некоторому базису, можно распознавать линию: квазипрямая—кривая (см. Fig. 4).
Говоря о взаиморасположении объектов вообще и линий в частности, следует не упускать из вида следующее обстоятельство, порождённое парадигмой «объект — это связная область». С одной стороны, реальный объект может включать топологические разрывы, например, штриховые линии или погрешности печати. Как представляется, они преодолеваются имитацией инерционного следования по трассе-скелетону. С другой стороны, касание или пересечение объектов порождает восприятие их нашей системой как единого объекта, который, вообще говоря, подлежит анализу и расчленению на составляющие. В общем, все эти аспекты восприятия связаны со следованием по трассе-скелетону.
Следование по линии
Исходной рассматриваемой моделью у нас является «слепой мозг», который к настоящему пункту получил возможность обнаруживать объекты, оценивать их размеры, классифицировать (тело—линия). В любом случае весь дальнейший анализ опирается на МРП-точки. Но всё, что мы сейчас знаем о множестве МРП-точек — это его распад на col-окрашенные подмножества в поле изображения Result. У каждого такого подмножества (объекта) есть точка входа — центр (y0, x0). И система может, отправляясь из этой точки, не имея априори никаких знаний о геометрии этой кучи, попытаться последовательно кучу перебрать, перемещаясь в соседнюю (по шаблону) МРП-точку и т.д., заблокировав возвратные шаги. Таким образом построены кривые FF9, FF11 из поста "Текущее состояние-20" (ТС20). А если в этом движении ввести ещё условие инертности — предпочтительности предыдущего очередному шагу направления, то удаётся выделить линию из пересечения (Fig. 5).
Такое следование в известной мере подобно движению слепого, ощупывающего в доступной окрестности рукой окружающее. И в некоторых ситуациях оно заводит в тупик, что уже отмечалось нами в «ТС20».
Там же (в «ТС20») был представлен метод трассирования через генерацию потенциального градиентного поля внутри объекта. Источник «излучения» вначале устанавливается в «центральную» точку объекта. Определяется наиудалённейшая от «центра» МРП-точка — МРП-точка с мин. или макс. потенциалом (в зависимости от того, используется инкрементное или декрементное излучение) — это конец линии. Затем источник помещается в эту концевую точку и определяется опять наиудалённейшая (от этого конца) точка — 2-й конец линии. Из этого 2-го конца осуществляется следование по МРП-точкам по градиенту поля к точке-источнику (1-му концу), прослеживая всю линию. В таком исполнении трассирование всегда приведёт к точке-источнику (своего рода «ариаднова нить»). Т.е. линию определяет пара максимально взаимоудалённых точек МРП-конгломерата — концов.
Затруднения возникли при попытке детального анализа пересекающихся линий (см. Fig. 5, b) — как надёжно идентифицировать все концы — вопрос, а алгоритм построен на концах. Вот как удалось программе разложить это пересечение — Fig. 6. Программа выдала вместе с изображениями линий с обозначенными белыми точками их скелетонами распознанные фрагменты линий — отрезки от концов до точки пересечения; построила по МРП-представлению их «фантомы» (пространственно смещённые чуть более светлые изображения).
Линейный МРП на скелетоне
Повторимся, затруднение вызывает идентификация концов. А если концов или пересечений много (например, таблицы), то применение описанных процедур становится громоздким. Всплывают данные биофизики зрительного анализатора: имеются нейроны-детекторы линий. Логика работы над нашей системой привела меня к возможности реализации давно вынашиваемой идеи линейного МРП, способного выполнять роль детектора линий.
Ввиду важности воспроизводим здесь рисунок из «ТС20» со схемой МРП-ячейки (Fig. 7).
Вновь предлагаемое линейное МРП-преобразование использует имеющийся конструктив однородной сети. Но мы наделяем его новыми дополнительными свойствами. Наша сеть должна обладать ещё режимами работы, когда ячейка становится диполем. Причём с несколькими режимами:
– горизонтального диполя (с левой частью 1-8-7 и правой 3-4-5);
– вертикального диполя (с верхней частью 1-2-3 и нижней частью 5-6-7).
Эти режимы практически испытаны на моём макете. Но для функциональной полноты можно предложить и ещё два:
– 1-й диагональный (8-1-2 --> 4-5-6);
– 2-й диагональный (2-3-4 --> 6-7-8).
Алгоритм линейного МРП-поля (обозначать будем LMRP) работает только на изображении Result (т.е. в «мире» скелетонов, т.е. МРП-точек).
Работа алгоритма LMRP полностью аналогична работе базового MRP-алгоритма с той лишь разницей, что окрестностью являются МРП-точки соответствующего режиму диполя (в нашем случае: либо горизонталь, либо вертикаль). Для реализации какого-либо режима точно также производится многошаговая итерационная процедура с ростом рангов производных LMRP-полей.
В «горизонтальном» режиме алгоритм различает «левую» окрестность и «правую» и осуществляет на n-й итерации перевод L-ранга=(n-1) текущей точки на следующую ступень n, если в её «левой» окрестности нашлась хоть одна точка с L-рангом не менее (n-1) и аналогично в «правой».
Подобно этому реализуется «вертикальный» режим.
Точно так же, как в базовой МРП-процедуре, выполняется следующая фаза фильтрации «независимых» LMRP-полей, которые являются результирующим представлением линии.
Эксперименты производились с LMRP-диполями горизонтальным и вертикальным, из-за того что, как указывалось, решаемой задачей является приблизиться к чтению нот. Поэтому в дальнейшем и предъявляемые системе входные изображения включали в основном горизонтали и вертикали. Хотя, надо сказать, что и наклонные линии при определённых условиях вполне «воспринимались». На Fig. 8, a, показано пересечение рисованных горизонтали и вертикали. И та и другая в результате представляются по одной LMRP-точке и значениями их L-рангов в соответствующих массивах — аналогов массива Ring. По этим координатам и значениям программа построила шаблонные (идеальные) горизонтальную и вертикальную линии, слегка их сместив по вертикали (для наглядности). Истинные же скелетоны и контуры линий воспроизведены более светлым цветом.
Далее приведены примеры детектирования в комплексных линейных объектах.
А вот пример членения на элементы рисованного «почти прямоугольника» (Fig. 12). Как видно, этому алгоритму концы не нужны.
Всё это — подступы к решению проблемы, как выделять из связной области наложенные (пересекающиеся) объекты. Вот пример картинки с двумя линиями и ното-подобными пятнами, расположенными между линиями и на линии (Fig. 13). Системе предъявлен препарат рисованной картинки. Распознавания произведено двумя шагами. На одном шаге методом линейного МРП по всему множеству точек скелетонов (MRP-точек) абстрагируются шаблоны двух линий (Fig. 13, b), а на другом шаге производится линейное МРП над фильтрованными по рангам скелетонами — ранг > R, где R — ранг точек линии (Fig. 13, с).