Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1




НазваниеСтруктурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1
Дата публикации28.09.2014
Размер86.4 Kb.
ТипДокументы
shkolnie.ru > Информатика > Документы


структурнЫЙ подход и принципы формирования примитивов в задаче распознавания составных объектов 1
Ю.Г. Васин2, Л.И. Лебедев 2
2 Научно-исследовательский институт прикладной математики и кибернетики
Нижегородского государственного университета им. Н.И. Лобачевского
603005, Россия, Нижний Новгород, ул. Ульянова, 10, НИИ ПМК.
E-mail: vasin@focus.ac.su, lebedev@pmk.unn.ru


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



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

^ Постановка задачи и методы решений
Отсюда, решение задачи распознавания

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

Очевидным фактом является то, что получить примитивы с уникальной формой, не содержащих проблемных участков, удаться не для всех эталонов. Поэтому, возможно формирование описаний непроизводных элементов на базе фрагментов контуров, идентичных у многих эталонов, которые будут образовывать некоторые классы этих примитивов. Более того, такие фрагменты могут встречаться несколько раз и на одном и том же эталоне. Это примитивы группы . Примером примитива этой группы может служить фрагмент E1, E2, E3, E4 контура буквы "Н" шрифта Times New Roman, имеющий форму скобы "└┘" соответствующих размеров, как это показано на рис. 1.


Этому примитиву будет соответствовать класс эталонов, содержащий символы "Н", "П", "Ц","Е", то есть

C("└┘")={"Н", "П", "Ц","Е"} (1)

При этом с заданным пороговом уровнем сходства будет определено контурным корреляционно-экстремальным методом по одному фрагменту на буквах "П", "Ц","Е", сходному с примитивом "└┘", а на букве "Н" два участка. (Минимальный уровень сходства устанавливался по результатам масштабирования примитива на полпункта и вычисления соответствующего порогового коэффициента сходства). Дальнейшей идентификации символов в классе C("└┘") можно провести путем задания дополнительного набора примитивов, отражающих форму символов данного класса. Однако, можно решить эту задачу менее затратными процедурами, не привлекая к решению контурный корреляционно-экстремальный метод. Для этого определим контрольные точки эталонов. Первая группа контрольных точек определяет ориентацию эталона, а вторая относительное местоположение. Для символов шрифта их естественной ориентацией является линия надписи, а точкой относительного местоположения - геометрический центр. На рис. 1 ориентацию и линию надписи буквы "Н" определяют точки D1и D2, геометрический центр - точка M, а габаритное описание задано узловыми точками прямоугольника G1,G2,G3,G4. Теперь, если габаритное описание эталонов и контрольных точек связано с местоположением фрагментов на эталонах, обеспечивающих заданный уровень сходства с примитивом, то идентифицировать символы в классах при известном направлении надписи достаточно просто. Действительно, если направление надписи задано ортом , то контурный корреляционно-экстремальный метод определит ориентацию фрагмента объекта относительно примитива "└┘" вектором . Для буквы "Е" скалярное произведение векторов и приближенно даст ноль, для одного фрагмента буквы "Н" и "Ц" оно будет равно единице, а для буквы "П" и другого фрагмента "Н" – минус единице. Отсюда, с учетом факта наличия двух фрагментов, сходных с примитивом "└┘" у буквы "Н" правила вывода структурного распознавания объектов класса C("└┘") при известном направлении надписи достаточно просты. При неизвестном направлении надписи относительно орта можно сделать три предположения: либо он совпадает с вектором , либо противоположно направлен, либо перпендикулярен. Далее, используя контрольные точки, следует сделать попытку определения истинного направления надписи или уменьшения их числа возможных вариантов, причем эти попытки необходимо предпринимать после каждого нижеописанного шага. Следующий шаг состоит в исключении из рассмотрения бесперспективных для распознавания дискретных объектов формируемых на основе эталонов данного класса. Эта процедура так же осуществляется при использовании контрольных точек. На рис. 2 проиллюстрирована ситуация, в которой в качестве части составного объекта выступает буква "П".

Наложение примитива на соответствующий фрагмент контура буквы позволяет получить различные габаритные описания эталонов из класса C("└┘"). На рисунке показано полученное габаритное описание буквы "Н". Так как контрольные точки, задающие ориентацию буквы "Н" лежат вне области составного объекта, то формирование дискретного объекта на основе ее габаритного описания следует исключить. Последний этап принятия решений по сокращению числа возможных претендентов проводится на основе сформированных описаний дискретных объектов по габаритам эталонов класса, не исключенных из рассмотрения на предыдущих шагах. Отсев осуществляется по несоответствию размеров полученного дискретного объекта эталонным размерам, на основании габаритных описаний которого он был получен. Так в нашем примере на рис. 2 высота получаемого дискретного объекта, сформированного на основе габаритного описания буквы "Н" значительно меньше и высоты самого символа и высотной характеристики составного объекта. Оставшиеся после этого этапа не отбракованные дискретные объекты подлежат распознаванию контурным корреляционно-экстремальным методом определения сходства плоских форм. При неизвестном направлении надписи из класса C("└┘") предложенные правила вывода структурного метода не дают решения по распознаванию букв "Н", "Ц". Однако, в любом случае для распознавания объектов из класса C("└┘") необходимо одновременно использовать не более трех эталонов, включая примитив и сформировать по соответствующим габаритным описаниям не более трех дискретных объектов.

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

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

, (2)

где - расстояние между -той и -ой точками в описаниях или примитива или фрагмента. Тогда габаритное описание этого эталона , в системе координат примитива можно получить по формуле

(3)

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

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

Список литературы

  1. Васин Ю.Г., Лебедев Л.И., Распознавание составных объектов изображения на базе структурного и корреляционно--экстремальных методов. // Математические методы распознавания образов (ММРО-13-2007): I3-ая Всеросс. конф.: Тез. докл., 2007.

____________________________________________________________________

1Работа выполнена при поддержке РФФИ, проект № 05-01-00590.

Похожие:

Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconМодели и алгоритмы обнаружения локальных закономерностей в задаче...

Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconФормализация лексического значения слова в задаче распознавания ситуаций...

Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconО возможности применения алгоритмов мгуа в задаче распознавания препятствий...
Томский Государственный Университет Систем Управления и Радиоэлектроники, Россия, г. Томск, 634050, пр. Ленина, д. 40, тел. 834-041,...
Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconКонкурентоспособность как фактор формирования стратегии предприятия
Этот подход характерен для классической экономической теории. Третий подход[5] определяет конкуренцию как критерий, по которому определяется...
Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 icon«теоретические основы информатики»
Теория кодирования. Виды кодирования. Оптимальные коды. Теория автоматов. Теория распознавания. Общая характеристика задач распознавания...
Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconПрограмма
Хх века. В освещении проблематики историко-литературной науки выделены принципы конкретного историзма, ценностный подход к литературным...
Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconПрограмма вступительного экзамена в аспирантуру по специальности
Хх века. В освещении проблематики историко-литературной науки выделены принципы конкретного историзма, ценностный подход к литературным...
Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 icon«Как устроен компьютер»
Обучающая создать условия для формирования первичного представления об устройстве компьютера, о назначении его составных частей
Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconК. В. Григоричев Региональная миграционная политика 2000-х: содержание, инструменты, контексты
Иными словами, речь идет о задаче формирования региональной миграционной политики, учитывающей специфику того или иного региона для...
Структурный подход и принципы формирования примитивов в задаче распознавания составных объектов 1 iconПринцип минимума суммы информационных рассогласований для независимых...
Нижний Новгород, ул. Тропинина, 4–17, тел.(8-831)277-61-96, e-mail
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница