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

1. Мартьянов В. И. Комбинаторные задачи высокой сложности и анализ плоских контурных изображений / В. И. Мартьянов, М. Д. Каташевцев // Изв. Иркут. гос. ун-та. Сер. Математика. – 2013. – №4. – С. 31–47.

2. Каташевцев М. Д. Волновая скелетизация / М. Д. Каташевцев // Вестн. Иркут. гос. техн. ун-та. – 2013. – № 7. – C. 89–92.

3. Обзор приложений логико-эвристических методов решения комбинаторных задач высокой сложности / В. И. Мартьянов, В. В. Архипов, М. Д. Каташевцев, Д. В. Пахомов // Современные технологии. Системный анализ. Моделирование / ИрГУПС. – 2010. – № 4(28). – С. 61–67.

4. Гери М. Вычислительные машины и труднорешаемые задачи / М. Гери, Д. Джонсон. — М. : Мир, 1982. – 419 с.

5. Мальцев А. И. Алгебраические системы / А. И. Мальцев. – М. : Наука, 1967. – 324 с.

6. Беллман Р. Динамическое программирование / Р. Беллман. — М. : Изд-во иностр. лит., 1960. – 400 с.