автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Пирамидальное распознавание изображений на основе бинарных структур

Нижегородский государственный технический университет

На правах рукописи

КОЛЕБАНОВ Сергей Викторович

ПИРАМИДАЛЬНОЕ РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ НА ОСНОВЕ БИНАРНЫХ СТРУКТУР

Специальность 05.13.17. - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

и/1

"" ~ 'Р т

Нижний Новгород -1998

Работа выполнена в Нижегородском государственном техническом университете

Научный руководитель -

член-корресгюндент РАН профессор Кондратьев В.В.

Официальные оппоненты:

доктор технических наук Гергель В.П. кандидат технических наук Мальцев В.Н.

Ведущая организация -

НИИ прикладной математики и кибернетики ННГУ

диссертационного совета Д 063.85.02 Нижегородского государственного технического университета по адресу: 603600, Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета.

Автореферат разослан " 1С " ноября 1998 г.

Защита состоится

1998 г. в ¿5" часов на заседании

Ученый секретарь диссертационного совета

Иванов А.П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

Одним из наиболее существенных результатов научно-технической революции является широкая компьютеризация практически всех областей человеческой деятельности. Бурное развитие средств вычислительной техники привело к тому, что значительные объемы научно-технической, общественной, социально-политической информации, в т.ч. и в виде изображений, переносятся в память ЭВМ и становятся доступными широкому кругу пользователей.

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

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

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

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

Цель работы

Цель работы состоит в повышении эффективности обработки изображений на основе разработки новых алгоритмов анализа, синтеза, описания и распознавания, базирующихся на теории активного восприятия изображений.

Достижение поставленной цели связано с решением следующих задач:

1) разработка общей методики поиска бинарной структуры и двутонового изображения для произвольного полутонового изображения; классификация бинарных структур;

2) разработка (на основе общей методики) алгоритма поиска бинарной структуры, приемлемого по временным и аппаратурным затратам;

3) разработка принципов построения многоуровневого, в виде пирамиды, описания изображений на основе бинарных структур; построение детальных процедур анализа и распознавания изображений с помощью бинарных структур;

4) разработка на базе метода активного восстановления алгоритмов распознавания изображений инвариантно к местоположению объекта в поле зрения, размеру, углу поворота, уровню яркости объекта и фона, растяжению или сжатию по горизонтали и вертикали;

5) исследование возможных погрешностей пирамидального описания, вызванных дискретным представлением изображения, и их учет в процессе распознавания;

6) создание программного обеспечения, реализующего ввод изображения, построение пирамидального описания, создание базы эталонных объектов, распознавание указанного изображения на данной базе эталонов, обучение по указанной выборке объектов, вывод изображений, а также разработка ряда вспомогательных утилит;

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

Научная новизна

В рамках теории активного восприятия изображений введены понятия классов, эквивалентных по бинарной структуре, меры подобия структуры двух изображений; определено понятие бинарной структуры полутонового изображения.

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

Разработаны алгоритмы распознавания изображений, инвариантные к местоположению объекта в поле зрения, размеру, углу поворота, уровню яркости объекта, растяжению или сжатию по горизонтали и вертикали, основанные на методе активного восстановления.

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

Разработаны алгоритмы анализа и кодирования изображений с помощью бинарных структур. Выработана архитектура базы данных для хранения бинарных структур и работы с ними, .предложена общая организация системы распознавания изображений на базе бинарных структур.

Практическая ценность

4

На базе алгоритмов анализа и распознавания изображений с помощью бинарных структур разработана методика пирамидального распознавания

алфавитно-цифровых символов для формирования электронной базы данных, хранящей сведения о пациентах лечебного учреждения, их профилактических прививках и медицинских отводах от прививок. Разработаны алгоритмы распознавания изображений инвариантно к местоположению объекта в поле зрения, размеру, углу поворота, уровню яркости объекта и фона, растяжению или сжатию по горизонтали и вертикали в рамках теории активного восстановления.

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

Внедрение полученных результатов в лечебных учреждениях позволило соответствующему медперсоналу сократить временные затраты на формирования первичной информационной базы, хранящей сведения о профилактических прививках пациентов, и избавиться от значительной части рутинной и трудоемкой работы.

Апробация работы

Основные положения и результаты диссертационной работы докладывались на следующих конференциях, семинарах и научных сессиях:

- Научно-техническая конференция факультета радиоэлектроники и технической кибернетики, посвященная 80-летию НГТУ (Нижний Новгород, 1997 г.);

- Восьмая Всероссийская конференция "Математические методы распознавания образов" (Москва, 1997 г.);

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

- Пятьдесят третья научная сессия Российского научно-технического общества радиотехники, электроники и связи им. А.С.Попова, посвященная Дню радио (Москва, 1998 г.);

- Международная научно-техническая конференция "Нейронные, реля-торные и непрерывнологические сети и модели" ("Neural, relator, continuous-logic systems and models") (Ульяновск, 1998 г.);

- Научно-техническая конференция "Применение математического моделирования для решения задач в науке и технике" (Ижевск, 1998 г.);

Областная конференция "Компьютерные технологии в информатизации здравоохранения Нижегородской области" (Нижний Новгород, 1998).

Публикации

По материалам диссертации опубликовано 10 научных работ.

Структура, объем и содержание работы

Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы, включающего 133 наименований, и 1 приложения. Основная часть работы содержит 101 страниц машинописного текста, 35 рисунков и 2 таблицы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В введении обоснована актуальность темы, сформулирована цель и определены основные задачи исследования.

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

Основные итоги первой главы следующие.

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

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

го восприятия, как целостность, структурированность, стратегия восприятия, обобщенность оснований и стереотипность.

3. На основе краткого анализа проблематики распознавания изображений и обзора разработанных к настоящему времени пирамидальных систем выработаны пути дальнейшего повышения эффективности работы: использование ранее разработанных алгоритмов обработки изображений, адекватный выбор уровня пространственного и яркостного разрешения, распараллеливание вычислений наиболее естественным и эффективным путем, реализация различных стратегий планирования поведения в процессе распознавания, обеспечение возможности настройки вычислительной системы на решение конкретной задачи, разработка адекватных языков высокого уровня и программных сред.

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

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

Массив структурных элементов является полутоновым изображением анализируемого объекта на каждом уровне пирамиды описания. Переход от полутонового изображения к бинарному позволит получить следующие преимущества.

1. Появляется возможность просто и эффективно производить логические операции над бинарными изображениями, используя разработанный аппарат алгебры изображений.

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

3. Снижение расходов машинной памяти под хранение описания изображения.

4. Дополнительная классификация полутоновых изображений по виду соответствующих им бинарных структур. ...

Пусть исходное изображение (или часть исходного изображения) представлено, в соответствии с теорией активного восприятия, массивом М структурных элементов:

М = { апт еО,Р~1: п = Гд ш = }, (О

где Р - число уровней яркости любого элемента массива.

Система фильтров Р есть

ГР-лп.Щ _ _

£|-1,+1}:п = 1,4,т = 1,4)

Тогда описанием изображения М на системе фильтров Р является множество ц={|1]}, где

'м = {ц,м = 0Л5}

4 4. (3)

п = 1т = 1

Изображение М вида (1) будем считать полутоновым.

Изображение М является двутоновым с уровнями и, и и3, где Ч) < и2, если имеет вид:

|М - { апт е{и,,и2} : п = 1,4, т =1,4 } Цеб/Р^, и2 еО,Р-1 ' (4)

Изображение М является бинарным, если имеет вид:

М = {апт £{0,1} = (5)

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

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

анализируемого изображения.

Пусть имеется произвольное изображение вида (1) с описанием (3). Изменение изображения по яркости и фону приведет лишь к изменению модуля вектора изображения {ц,} в 15-мерном пространстве, но не его направления.

Тогда произвольному изображению М вида (1) с описанием (3) в 15-мерном пространстве {(¿¡} может быть поставлен в соответствие орт ц°. Данный орт является инвариантным к изменению изображения М по яркости, фону и вычисляется следующим образом:

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

В таком случае справедливо следующее утверждение, вводящее меру подобия структуры двух изображений: для произвольных изображений М( и М2 вида (1) с описанием (3) мера подобия их структуры определяется косинусом угла между векторами {ц1;) и {ц2,} либо между ортами {(а01,} и {ц02,} этих векторов соответственно, где

,5 (7)

cosa = if7Г¥- = 2>^ц?2 .

г 1г I '=!

Имеется 65536 бинарных изображений вида (5), составляющих множество Кб бинарных изображений. Структура каждого из этих изображений оп-

ределяется соответствующим вектором {ц«} и может быть представлена графически данным изображением. Каждый класс изображений, эквивалентных по бинарной структуре, может быть представлен ортом {ц0«}. Степень близости произвольного изображения М к классу бинарных изображений есть косинус угла между соответствующими векторами описаний.

В этом случае справедливо следующее утверждение: для произвольного изображения М вида(1) с ортом (6) из множества Кб бинарных изображений наиболее близким по структуре является изображение М„пт вида (5) с ортом {fAmi}- Мера подобия структур М и Mim есть

Бинарной структурой произвольного изображения М вида (1) называется бинарное изображение М0Пт вида (5) с ортом {ц0О1т} вида (6), найденное согласно (8).

Таким образом, с помощью (8) появляется возможность для произвольного изображения М вида (1) из всего имеющегося множества бинарных изображений выбрать наиболее подходящее ему по структуре.

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

Далее предлагается алгоритм быстрого поиска угла, наиболее близкого по направлению к заданному, позволяющий ускорить алгоритм поиска бинарной структуры примерно в 580 раз и избежать перебора всего множества ортов бинарных структур. Суть алгоритма - определение некоторой окрестности, необходимо содержащей искомую бинарную структуру, и производство поиска только в этой окрестности. Произведенная экспериментальная проверка алгоритма поиска угла подтверждает высокую экономию времени при поиске бинарной структуры.

В последнем подпункте главы определяется вектор г, который характеризует состав изображения и используется в качестве основного критерия классификации бинарных структур; приводится таблица полученных классов. Производится краткий анализ полученных классов.

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

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

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

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

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

Пусть произвольная область О содержит п пикселов, каждый из которых принимает целочисленное значение в диапазоне от 0 до (Р-1) единиц. Тогда число всевозможных изображений в этой области равно:

V = Р\ (9)

* изо 1 '

а количество всевозможных визуальных масс:

У,м=1 + (Р-1)п. (Ю)

Пусть функция К-п.р^), отражает зависимость числа всевозможных изображений для данной в при фиксированных п и Р. На основании (9) и (10), а также результатах проведенных исследований справедливо: зависимость Кпр(5) носит симметричный характер; максимального значения функция Яп,р(3) достигает в центральном диапазоне Б; при изменении п,Р характер зависимости Я„ г(8) не меняется.

При цифровой обработке изображение объекта представляет собой матрицу пикселов размером Н<хМу. Согласно полученным в главе 2 утверждениям для обеспечения инвариантности распознавания объекта описывающий прямоугольник должен изменяться пропорционально изменению габаритов объекта. С другой стороны, размеры описывающего прямоугольника должны быть кратны величине 6°, где Э - число уровней пирамиды описания, 52 - коэффициент дробления структурного элемента при переходе от уровня к уровню. Таким образом, в общем случае габариты объекта и стороны описывающего прямоугольника не равны, то есть возникает погрешность габаритного описания, обусловленная цифровой формой представления изображения.

Пусть в, и Оу - стороны описывающего прямоугольника, найденные для описания .объекта с габаритами МххЫу на пирамиде до уровня В. Ох и вычисляются по формуле:

|ах(кх) = коиш6ц(мх/50).5п

[одк^юиш^/б0)^0'

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

[ДОу(Му) = Оу-М/ ( }

а относительные погрешности габаритного описания Ех и Еу - по

формуле:

XV х/ ^ ^ (13)

уС у) су су

Максимальная абсолютная погрешность ДСХПШ и максимальная относительная погрешность Ехпих габаритного описания равны:

ДОхтах=ДОугоах=5с-1, (Н)

Е =1-^- (15)

^хтах 1 20"

Таким образом, при дискретном анализе изображения возникает погрешность габаритного описания. Этот факт следует учитывать в процессе распознавания.

В четвертой главе производится экспериментальное исследование влияния габаритной погрешности на пирамидальное описание объекта; экспериментальное исследование влияния шумов различной природы и интенсивности (случайных с равномерным, гауссовым законами распределения вероятности и регулярных типа "линия", "сетка") на пирамидальное описание; сравнение описания эталона и его различных структурных вариаций. Разрабатывается общая организация системы распознавания изображений с помощью бинарных структур, ее реализация в системе реальной СУБД. Производится расчет объема памяти для хранения изображения в виде пирамидального описания и в виде бинарных структур. Наконец, обсуждается решение задачи ввода информации в базу данных с печатного листа, в которой используется научный материал всех четырех глав.

При цифровой обработке изображение объекта представляет собой матрицу пикселов размером Размеры Ох и описывающего прямоугольника должны быть кратны величине 6°, где Б - число уровней пирамиды описания, б2 - коэффициент дробления структурного элемента при переходе от уровня к уровню. Таким образом, в общем случае габариты объекта и стороны описывающего прямоугольника не равны, то есть имеет место погрешность габаритного описания, обусловленная цифровой формой представления изображения. В свою очередь, погрешность габаритного описания является причиной погрешности пирамидального описания ц..

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

равен б"; при уменьшении объекта величины Дц и Ец возрастают, что объясняется возрастающим влиянием габаритной погрешности; чем больше величина 5°, тем больше описание объекта подвергается влиянию габаритной погрешности; бинарная структура является устойчивой к влиянию габаритной погрешности.

В подавляющем большинстве случаев в реальных изображениях объекты (полезные сигналы) искажены шумами различной природы и интенсивности, что следует учитывать при разработке систем технического зрения. С этой целью было произведено: исследование влияния некоторых видов шумов на пирамидальное описание вообще и бинарные структуры в частности; исследование меры сходства пирамидального описание и описания на основе бинарных структур между эталоном и его структурными вариациями. Исследование показало: пирамидальное описание и описание на основе бинарных структур на более высоких уровнях иерархии более устойчиво к шумам и вариациям, чем на более низких; сравнение меры сходства для эталона тестового класса и его зашумленных копий (сравнение внутри класса) и этой же меры для эталона тестового класса и эталонов других классов (сравнение между классами) указывает на то, что внутри класса мера сходства больше, чем между классами. Таким образом, пирамидальное описание и описание на основе бинарных структур устойчивы к данным шумам и структурным вариациям.

После исследования влияния габаритной погрешности и шумов рассматривается общая организация системы распознавания изображений на основе бинарных структур. Центральной частью системы являются база бинарных структур и программа их поиска. Программа поиска бинарных структур реализует алгоритм, подробно описанный во второй главе, используя при этом базу бинарных структур. Каждая запись этой базы содержит следующую информацию о конкретной бинарной структуре: уникальный номер (от О до 65535); массив структурных элементов (матрица размерностью 4x4); описание ц; орт направлений номер класса, к которому принадлежит структура. Совместно с базой содержатся 15 индексных файлов для быстрого поиска заданной бинарной структуры.

В результате проведения необходимых вычислений получены следующие формулы вычисления объемов памяти для хранения пирамиды описания, пирамиды структурных элементов, а также их совокупности соответственно:

4>п = 2] 16 • 82( М) • уоп , (16)

¡=1

V = У 16-82('"° • V (17)

мсэ " умсэ >

1=1

V =У16-5201)(у + у ), (18)

ОП + МСЭ " V *оп 'мсз/'

ы

где ЫхЫ - размерность массива изображения; б2 - коэффициент дробления структурного элемента при переходе от уровня к уровню (N=5*); у0„ -объем памяти для хранения одного элемента в векторе ц; умо - объем памяти для хранения одного члена в массиве структурных элементов, для хранения элементарного массива структурных элементов и его описания требуется, согласно вышеприведенным рассуждениям, 96 байт. Поскольку для хранения массива размерностью 4x4 и его описания с помощью бинарных структур требуется всего 2 байта (под уникальный номер структуры), требуемый объем памяти уменьшается в 48 раз.

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

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

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

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

В приложении приведены справки о внедрении результатов диссертационной работы при решении практических задач.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработан ряд алгоритмов бинаризации произвольного изображения в зависимости от критерия оптимальности. Проведен сравнительный анализ этих алгоритмов, и выработан окончательный алгоритм поиска двутонового изображения и бинарной структуры, основанный на методе угловой бинаризации по минимуму евклидова расстояния между векторами описаний. Таким образом, от практически неограниченного множества полутоновых изображений произведен переход к достаточно малочисленному множеству бинарных образов.

3. Определен вектор Ъ, который характеризует состав изображения и используется в качестве основного критерия классификации бинарных структур. Произведена их классификация по указанному вектору.

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

5. Произведено исследование описания на различных уровнях пирами-

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

6. Произведено исследование перехода области пикселов в ее визуальную массу, на котором базируется получение массива структурных элементов. Показано, что характеризующая этот процесс зависимость Р-п.р^) носит симметричный характер, максимального значения функция Кп,р($) достигает в центральном диапазоне 8, при изменении п, Р характер зависимости Кп р(8; не меняется.

7, Исследована погрешность габаритного описания, обусловленная дискретным характером представления изображения, получены формулы абсолютной, относительной и максимальной погрешностей габаритного описания.

й. Проведено экспериментальное исследование влияния габаритной погрешности на пирамидальное описание изображения. Установлено: данная зависимость носит периодический характер (период вычислен); бинарная структура является устойчивой к влиянию габаритной погрешности.

9. Про ведено экспериментальное исследование влияния шумов различной природы и интенсивности на пирамидальное описание изображения у соответствующие бинарные структуры; выполнено сравнение описания эталона и его различных структурных вариаций. В результате установлено: пирамидальное описание и описание на основе бинарных структур на боле£ высоких уровнях более устойчиво к шумам и вариациям, чем на более низких; внутриклассовое расстояние (между эталоном и его зашумленными копиями, между эталоном и его структурными вариациями) значительнс меньше, чем между классами. Таким образом, пирамидальное описание ^ описание на основе бинарных структур оказались устойчивы к данным шумам и структурным вариациям.

10*. Рассмотрена в общем виде, архитектура системы распознавания изображений с помощью бинарных структур, подробно разработана центральная часть данной системы - база бинарных структур. Показано, что при хра нении изображения в виде бинарных структур имеет место 48-кратная эко номия памяти по сравнению с обычным пирамидальным описанием.

11. Разработана программная система, решающая задачу автоматизиро ванного формирования с бумажного носителя электронной базы данны> профилактических прививок. В этой программной системе в практически? целях используется научный материал, полученный в диссертации. Выше

указанная программная система позволяет медперсоналу сократить временные затраты на ввод в базу новой информации и избавиться от значительной

мае ni рутинной и трудоемкой работы.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Кондратьев В.В., Утробин В.А., Колебанов C.B. Поиск и использование информативных точек на базе метода активного восстановления изображений // Научно-техническая конференция факультета радиоэлектроники и технической кибернетики: Тез. докл.- Н.Новгород: НГТУ, 1997,- С. 36.

2. Кондратьев В.В., Колебанов C.B., Утробин В.А. Пирамидальная система распознавания алфавитно-цифровых символов // Математические методы распознавания образов: Тез. докл. Восьмой Всероссийской конф. - М., 1997.-С. 164-66.

3. Колебанов C.B. Двухэтапная схема поиска оптимальных бинарных структур для пирамидального распознавания изображений У/ Научно-техническая конференция факультета информационных систем и технологий: Тез. докл. - Н.Новгород: НГТУ, 1998. - С. 50.

4. Колебанов C.B. Применение оптимальных бинарных структур как предикатов для задачи распознавания изображений // Научно-техническая конференция факультета информационных систем и технологий: Тез. докл. -Н.Новгорол: НГТУ, 1998, - С. 49.

5. Колебанов C.B. Распознавание изображений на основе оптимальных бинарных структур // Пятьдесят третья научная сессия, посвященной Дню радио: Тез. докл.- М„ 1998,- С. 240-241.

6. Колебанов C.B., Кондратьев В.В., Утробин В.А. Предикатный анализ изображений на базе пирамидальной системы для задачи принятия решений // Нейронные, реляторные и непрерывно-логические сети и модели: Сб. тр. межд. научно-техн. конф, - Ульяновск: УлГТУ, 1998. - Т.). - С. 100-102.

7. Колебанов C.B., Рогинский A.B. Алгоритмическое обеспечение пирамидальной системы распознавания изображений // Применение математического моделирования для решения задач в науке и технике: Сб. науч. тр. конф. - Ижевск, 1998, - С. 45-54.

8. Кондратьев В.В., Колебанов C.B. Инвариантное распознавание изображений на базе метода активного восстановления // Применение математического моделирования для решения задач в науке и технике: Сб. науч. тр. конф. - Ижевск, 1998. - С. 54-59.

9. Колебанов C.B. Автоматизированное формирование базы профилактических прививок на основе пирамидальной системы распознавания изобра-

жений // Компьютерные технологии в информатизации здравоохранения Нижегородской области: Сб. науч. тр. конф. - Н.Новгород, 1998. - С. 5962.

10. Колебанов C.B. Свойства оптимальных бинарных структур и алгоритм их поиска на базе метода активного восстановления изображений // Системы обработки информации и управления: Межвуз. сб. науч. тр. - Н.Новгород: НГТУ, 1998.-С. 91-97.

Подписано в печать 10.11.98. Формат 60x84 '/16. Бумага офсетная. Печать офсетная. Уч.-иэд. л. 1,0. Тираж 80 экз. Заказ 497.

Типография НГТУ. 603600, Нижний Новгород, ул. Минина, 24.

ВВЕДЕНИЕ.

1. ПИРАМИДАЛЬНОЕ РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ: 14 АНАЛИЗ СОСТОЯНИЯ И ПУТИ ПОВЫШЕНИЯ ЭФФЕК

ТИВНОСТИ РАБОТЫ.

1.1. Краткий обзор пирамидальных систем распознавания 15 изображений.

1.2. Направления повышения эффективности работы пира- 34 мидальных систем.

1.3. Цель и задачи исследования. 40 Выводы первой главы.

2. ПОНЯТИЕ БИНАРНЫХ СТРУКТУР. ПОИСК И КЛАССИ

ФИКАЦИЯ БИНАРНЫХ СТРУКТУР.

2.1. Пирамидальное описание изображения.

2.2. Определение бинарных структур.

2.3. Поиск бинарных структур.

2.4. Классификация бинарных структур. 76 Выводы второй главы.

3. ИНВАРИАНТНОСТЬ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ

НА БАЗЕ МЕТОДА АКТИВНОГО ВОССТАНОВЛЕНИЯ.

3.1. Исследование инвариантности описания изображения 84 на основе метода активного восстановления.

3.2. Исследование процесса перехода области пикселов в 102 визуальную массу.

3.3. Исследование габаритной погрешности пирамидально- 107 го описания изображения.

Выводы третьей главы.

4. ПРИМЕНЕНИЕ БИНАРНЫХ СТРУКТУР ДЛЯ ПИРАМИ- 113 ДАЛЬНОГО РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ.

4.1. Экспериментальное исследование влияния габаритной 114 погрешности на пирамидальное описание.

4.2. Экспериментальное исследование влияния шумов раз- 117 личной природы и интенсивности на пирамидальное описание.

4.3. Общая организация системы распознавания изображе- 128 ний с помощью бинарных структур.

4.4. Решение задачи ввода информации в базу данных с пе- 135 чатного листа.

Выводы четвертой главы.

Актуальность темы. Одним из наиболее существенных результатов научно-технической революции является широкая компьютеризация практически всех областей человеческой деятельности. Бурное развитие средств вычислительной техники привело к тому, что значительные объемы научно-технической, общественной, социально-политической информации, в т.ч. и в виде изображений, переносятся в память ЭВМ и становятся доступными широкому кругу пользователей.

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

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

С одной стороны, проблема построения эффективного (для распознавания) описания структуры объекта, представленного в виде изображения, в настоящее время продолжает оставаться актуальной. С другой стороны, в работе [55] предложена перспективная теория распознавания изображений - теория активного восприятия изображений. Эта теория базируется на достоверно известных и подтвержденных многочисленными нейрофизиологическими и электрофизиологическими исследованиями фактах работы естественных зрительных систем. На данный момент в рамках теории разработаны теоретические основы анализа и синтеза изображений. В то же время необходимо дальнейшее развитие предложенных принципов обработки изображений "вглубь": разработка алгоритмов распознавания изображений в конкретных предметных областях; изучение эффективности работы этих алгоритмов в условиях шумов различной природы и интенсивности; проведение исследований по сравнению эффективности работы вновь полученных и уже имеющихся алгоритмов распознавания изображений; разработка методик описания эталонных объектов и процедур обучения распознаванию.

Результаты, полученные в диссертационной работе, базируются на теоретических и прикладных трудах Бравермана Э.М., Бакута П.А., Берта П.Дж., Вапника В.Н., Васина Ю.Г., Глезера В.Д., Глушкова В.М., Горелика A.JL, Гуревича И.Б., Гренандера У., Журавлева Ю.И., Евреинова Э.В., Калмана Р., Катыса Г.П., Колмогорова А.Н., Колмогорова Г.С., Кондратьева В.В., Лорьера Ж.-JI., Ляпунова A.A., Марра Д., Минского М., Прэтта У., Розена В.В., Розенблатта Ф., Розенфельда А., Скрипкина В.А., Утробина В.А., Цыпкина ЯЗ., Яншина В.В. и многих других российских и зарубежных ученых, внесших значительный вклад в развитие теории и практики распознавания образов и анализа сцен.

Цель работы состоит в повышении эффективности обработки изображений на основе разработки новых алгоритмов анализа, синтеза, описания и распознавания, базирующихся на теории активного восприятия изображений.

Достижение поставленной цели связано с решением следующих задач:

1) разработка общей методики поиска бинарной структуры и двутоно-вого изображения для произвольного полутонового изображения; классификация бинарных структур;

2) разработка (на основе общей методики) алгоритма поиска бинарной структуры, приемлемого по временным и аппаратурным затратам;

3) разработка принципов построения многоуровневого, в виде пирамиды, описания изображений на основе бинарных структур; построение детальных процедур анализа и распознавания изображений с помощью бинарных структур;

4) разработка на базе метода активного восстановления алгоритмов распознавания изображений инвариантно к местоположению объекта в поле зрения, размеру, углу поворота, уровню яркости объекта и фона, растяжению или сжатию по горизонтали и вертикали;

5) исследование возможных погрешностей пирамидального описания, вызванных дискретным представлением изображения, и их учет в процессе распознавания;

6) создание программного обеспечения, реализующего ввод изображения, построение пирамидального описания, создание базы эталонных объектов, распознавание указанного изображения на данной базе эталонов, обучение по указанной выборке объектов, вывод изображений, а также разработка ряда вспомогательных утилит;

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

Методика исследования. Решение задач проводилось с использованием методов имитационного моделирования, теории распознавания образов, математического программирования, методов вычислительной математики и математической статистики, теории множеств и абстрактной алгебры. Достоверность теоретических исследований подтверждена результатами реализации моделей, алгоритмов и программ при решении практических задач распознавания изображений.

Научная новизна. В рамках теории активного восприятия изображений введены понятия классов, эквивалентных по бинарной структуре, меры подобия структуры двух изображений; определено понятие бинарной структуры полутонового изображения.

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

Разработаны алгоритмы распознавания изображений инвариантно к местоположению объекта в поле зрения, размеру, углу поворота, уровню яркости объекта, растяжению или сжатию по горизонтали и вертикали, основанные на методе активного восстановления.

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

Разработаны алгоритмы анализа и кодирования изображений с помощью бинарных структур. Выработана архитектура базы данных для хранения бинарных структур и работы с ними, предложена общая организация системы распознавания изображений на базе бинарных структур.

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

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

Разработано программное обеспечение, реализующее построенные алгоритмы и модели и обеспечивающее решение ряда практических задач по обработке изображений и автоматизированному вводу информации с бумажного носителя в ЭВМ.

Внедрение полученных результатов в лечебных учреждениях позволило соответствующему медперсоналу сократить временные затраты на формирования первичной информационной базы, хранящей сведения о профилактических прививках пациентов, и избавиться от значительной части рутинной и трудоемкой работы.

Апробация работы. Основные положения и результаты диссертационной работы докладывались на следующих конференциях, семинарах и научных сессиях:

- Научно-техническая конференция факультета радиоэлектроники и технической кибернетики, посвященная 80-летию НГТУ (Нижний Новгород, 1997 г.);

- Восьмая Всероссийская конференция "Математические методы распознавания образов" (Москва, 1997 г.);

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

- Пятьдесят третья научная сессия Российского научно-технического общества радиотехники, электроники и связи им. А.С.Попова, посвященная Дню радио (Москва, 1998 г.);

- Международная научно-техническая конференция "Нейронные, реляторные и непрерывнологические сети и модели" ("Neural, relator, continuous-logic systems and models") (Ульяновск, 1998 г.);

- Научно-техническая конференция "Применение математического моделирования для решения задач в науке и технике" (Ижевск, 1998 г.);

- Областная конференция "Компьютерные технологии в информатизации здравоохранения Нижегородской области" (Нижний Новгород, 1998).

Публикации. По материалам диссертации опубликовано 10 научных работ.

Структура, объем и содержание работы. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы, включающего 133 наименований, и 1 приложения. Основная часть работы содержит 101 страниц машинописного текста, 35 рисунков и 2 таблицы.

Основные результаты работы заключаются в следующем.

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

2. Разработан ряд алгоритмов бинаризации произвольного изображения в зависимости от критерия оптимальности. Проведен сравнительный анализ этих алгоритмов, и выработан окончательный алгоритм поиска двутонового изображения и бинарной структуры, основанный на методе угловой бинаризации по минимуму евклидова расстояния между векторами описаний. Таким образом, от практически неограниченного множества полутоновых изображений произведен переход к достаточно малочисленному множеству бинарных образов.

3. Определен вектор который характеризует состав изображения и используется в качестве основного критерия классификации бинарных структур. Произведена их классификация по указанному вектору.

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

5. Произведено исследование описания на различных уровнях пирамиды при таких преобразованиях, как циклический сдвиг, масштабирование, поворот. Показано, что для данных преобразований абсолютная разница описания на верхних уровнях пирамиды больше, чем на нижних; относительная разница описания на верхних уровнях пирамиды меньше, чем на нижних; при незначительной величине преобразования относительное изменение описания на первом уровне также незначительно.

6. Произведено исследование перехода области пикселов в ее визуальную массу, на котором базируется получение массива структурных элементов. Показано, что характеризующая этот процесс зависимость 11П р(8) носит симметричный характер, максимального значения функция КП;Р(8) достигает в центральном диапазоне 8, при изменении п, Р характер зависимости К.п,р(8) не меняется.

7. Исследована погрешность габаритного описания, обусловленная дискретным характером представления изображения, получены формулы абсолютной, относительной и максимальной погрешностей.

8. Проведено экспериментальное исследование влияния габаритной погрешности на пирамидальное описание изображения. Установлено: данная зависимость носит периодический характер (период вычислен); бинарная структура является устойчивой к влиянию габаритной погрешности.

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

10. Рассмотрена в общем виде архитектура системы распознавания изображений с помощью бинарных структур, подробно разработана центральная часть данной системы - база бинарных структур. Показано, что при хранении изображения в виде бинарных структур имеет место 48-кратная экономия памяти по сравнению с обычным пирамидальным описанием.

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

ЗАКЛЮЧЕНИЕ

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

1. Адаптивные методы обработки изображений. Сборник научных трудов. / Под ред.Л.П.Ярославского. - М.:Наука , 1988. - 242с.

2. Адаптивные телеизмерительные системы / Под ред. А.В.Фремке. -Л.: Энергоиздат., Ленингр. отд ние, 1981. - 248с.

3. Александров В.В., Горский Н.Д. Представление и обработка изображений: Рекурсивный подход. Л.: Наука, 1985. - 192с.

4. Алоимокос Дж. Зрительное определение формы // ТИИЭР. 1988. -Т.76,№8. -С. 50-69.

5. Ардалионов Л.В., Симаранов С.Ю. О задаче распознавания отдельных символов в печатном тексте // Известия АН. Техническая кибернетика. 1993. - № 6. - С. 61 - 75.

6. Ахмед Н., Pao K.P. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980. - 248с.

7. Байчи Р. Активное восприятие // ТИИЭР. 1988. - Т. 76. - № 8. - С. 164- 174.

8. Бакут П.А., Колмогоров Г.С. Сегментация изображений: методы выделения границ областей // Зарубежная радиоэлектроника. -1987. -№ 10.-С. 33 52.

9. Берт П.Дж. Интеллектуальное восприятие в пирамидальной зрительной машине // ТИИЭР. 1988. - Т.76, № 8. - С. 175 - 186.

10. Вакульский O.A. Построение иерархического описания цифровых изображений // Космическая наука и техника. 1990. - № 5. - С. 6871.

11. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М.: Наука, 1974. - 416с.

12. Васин Ю.Г., Пашков A.B. Решение задачи видимости с использованием бинарных рекурсивных структур представления видеоинформации // Межвуз. сб. науч. тр. Автоматизация обработки сложной графической информации. Н.Новгород, 1990. - С. 5 - 29.

13. Воробьев К.Ю., Тимонькин Г.Н., Харченко В.С., Мельников В.А. Иерархическая обработка изображений и пирамидальные системы // Зарубежная радиоэлектроника. 1991. - № 7. - С. 51 - 61.

14. Горелик А.А., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. М.: Радио и связь, 1985. - 160с.

15. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. М.: Радио и связь, 1985. - 160с.

16. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1984. 222с.

17. Горский Н.Д. Автоматическое распознавание рукописного текста // Проблемы информатизации. 1994. - № 1 - 2. - С. 75 - 81.

18. Гренандер У. Лекции по теории образов: Анализ образов. М.: Мир, 1981.-448с.

19. Гренандер У. Лекции по теории образов: Регулярные структуры. -М.: Мир, 1983. -430с.

20. Гренандер У. Лекции по теории образов: Синтез образов. М.: Мир, 1979.-383с.

21. Гуревич И.Б. Проблемы распознавания изображений // Распознавание, классификация, прогноз. Математические методы и их применение: ежегодник. Вып. 1. М.: Наука, 1988. - С. 280 - 329.

22. Гуревич И.Б. Проблемы распознавания изображений // Распознавание, классификация, прогноз. Математические методы и их применение: ежегодник. Вып. 1. М.: Наука, 1988. - С. 280 - 329.

23. Дидук H.H. Свойства дискретных пространств неопределенности. Уточнение основной теоремы кодирования // Кибернетика и системный анализ. 1994. - № 1. - С. 14-24.

24. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.-511с.

25. Дыдычкин А.Е., Орлова Е.А., Савин A.A., Советников Ю.Н. Организация иерархического алгоритма распознавания машинописных знаков // Вопросы радиоэлектроники. Серия ЭВТ. 1984. - № 8. - С. 75-81.

26. Евреинов Э.В. Распределенная обработка информации и распределенные вычислительные системы. М.: Знание, 1983. - 64с.

27. Журавлев Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. Математические методы и их применение: ежегодник. Вып. 1. М.: Наука, 1988. - С. 9- 16.

28. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение: ежегодник. Вып. 2. М.: Наука, 1989.-С. 5-72.

29. Завалишин Н.В., Мучник И.Б. Модели зрительного восприятия и алгоритм анализа изображений. М.: Наука, 1974. - 344с.

30. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972.-208с.

31. Зайцев-Зотов В.И. Метод распознавания машинописных знаков в широком диапазоне качества печати // Вопросы радиоэлектроники. Серия ЭВТ. 1982. - № 9. - С. 3 - 14.

32. Зрительное опознание и его нейрофизиологические механизмы // Под ред. В.Д. Глезер. Л.: Наука, 1975. - 272с.

33. Интеллектуальные системы распознавания текстов // Computer Direct. 1995.-№2.-С. 46-48.

34. Калеватых A.B., Павлов Б.А. Обзор современных методов автоматизированного анализа изображений // Автоматика и телемеханика.- 1995.-№9.-С. 3-21.

35. Кантони В., Левиальди С. Мультипроцессорные системы для обработки изображений // ТИИЭР. 1988. - Т. 76. - № 8. - С. 118 - 130.

36. Катыс Г.П. Обработка визуальной информации. М.: Машиностроение, 1990.-320с.

37. Кнут Д. Искусство программирования. М.: Радио и связь, 1985. -Т.2. - 340с.

38. Ковалевский В.А., Гимельфарб Г.Л., Возиянов А.Ф. Оптические читающие автоматы. Киев: Техника, 1980. - 207с.

39. Козлов Ю.М. Адаптация и обучение в робототехнике. М.: Наука, 1990.-248с.

40. Колебанов C.B. Двухэтапная схема поиска оптимальных бинарных структур для пирамидального распознавания изображений // Научно-техническая конференция факультета информационных систем и технологий: Тез. докл. Н.Новгород: НГТУ, 1998. - С. 50.

41. Колебанов C.B. Применение оптимальных бинарных структур как предикатов для задачи распознавания изображений // Научно-техническая конференция факультета информационных систем и технологий: Тез. докл. Н.Новгород: НГТУ, 1998. - С. 49.

42. Колебанов C.B. Распознавание изображений на основе оптимальных бинарных структур // Пятьдесят третья научная сессия, посвященной Дню радио: Тез. докл.- M., 1998.- С. 240-241.

43. Колебанов C.B. Свойства оптимальных бинарных структур и алго-рим их поиска на базе метода активного восстановления изображений // Системы обработки информации и управления: Межвуз. сб. науч. тр. Н.Новгород: НГТУ, 1998. - С. 91-97.

44. Колебанов C.B., Рогинский A.B. Алгоритмическое обеспечение пирамидальной системы распознавания изображений // Применение математического моделирования для решения задач в науке и технике: Сб. науч. тр. конф. Ижевск, 1998. - С. 45-54.

45. Кондратьев В. В., Утробин В.А. Математическая модель процесса идентификации в условиях априорной неопределенности // Применение математического моделирования для решения задач в науке и технике: Сб. тр. конф. Ижевск, 1997. - С. 63-73.

46. Кондратьев В.В., Колебанов C.B. Инвариантное распознавание изображений на базе метода активного восстановления // Применение математического моделирования для решения задач в науке и технике: Сб. науч. тр. конф. Ижевск, 1998. - С. 54-59.

47. Кондратьев В.В., Колебанов C.B., Утробин В.А. Пирамидальная система распознавания алфавитно-цифровых символов // Математические методы распознавания образов: Тез. докл. Восьмой Всес\российской конф. М., 1997. - С. 164-66.

48. Кондратьев В.В., Утробин В.А. Активное восстановление решение проблемы неопределенности // ДАН. - 1996, т.350, №3. - С. 315-317.

49. Кондратьев В.В., Утробин В.А. Информационный подход к моделированию целостного зрительного восприятия // ДАН. 1994. -Т.338,№5.-С. 610-612.

50. Кондратьев В.В., Утробин В.А. Модель зрительного восприятия в нейросетевом базисе // Международная научно-техническая конференция: сб. Нейронные сети и модели. 1995. - Т.1. - С. 73-74.

51. Кондратьев В.В., Утробин В.А. Основы теории активного восприятия изображений. Н.Новгород: НГТУ, 1997. - 249 с.

52. Кондратьев В.В., Утробин В.А. Формализация описания изображения в условиях неопределенности // Математические методы распознавания образов: Тез. докл. международной конф. М., 1995. - С. 34.

53. Кондратьев В.В., Утробин В.А. Формирование описания изображения в условиях неопределенности // ДАН. 1995. - Т.347, № 3. -С.316-318.'

54. Кондратьев В.В., Утробин В.А., Шаповал A.B. Обработка изображений на основе психофизиологии зрительного восприятия // 6-я Всероссийская научно-техническая конференция.: Тез. докладов. -Н.Новгород, 1993.- С.57.

55. КондратьевВ.В., Утробин В.А. Симметрия пятимерного евклидова пространства // ДАН. 1997, т.356, №2. - С. 178-181.

56. Котович Н.В. Система распознавания рукописных символов. Исследование емкости модели // Вопросы кибернетики. 1992. - № 177.-С. 81-86.

57. Красильников H.H. Новое в развитиии обобщенной функциональной модели зрения для информационных систем // Автометрия. -1992.-№2. -С. 73-78.

58. Красильников H.H. Обобщенная функциональная модель зрения и ее применение в системах обработки и передачи изображений // Автометрия. 1990. - № 6. - С. 7-14.

59. Куафе Ф. Взаимодействие робота с внешней средой. М.: Мир, 1985.- 538с.

60. Куликовский Ю.И. Алгебраические методы в распознавании образов // Кибернетический сб. Вып. 14. М.: Мир, 1977. - С. 178 - 226.

61. Кун С. Матричные процессоры на СБИС. М.: Мир, 1991. - 672с.

62. Купчинаус С.Ю. Структурно-иерархический метод описания и распознавания графических изображений // Вестник Удмуртского университета. 1994. - № 2. - С. 95-101.

63. Куссуль Э.М., Касаткин A.M., Касаткина JI.M. и др. Нейрокомпьютеры и интеллектуальные роботы. Киев.: Наукова думка, 1991. -315с.

64. Ланге М.М. Древовидная сегментация образов для ускорения анализа сцен // Прикладные проблемы искусственного интеллекта. -М.: Государственный комитет РСФСР по экологии и природопользованию АН СССР, 1991. С. 27-39.

65. Лани М.М. О распознавании образов с использованием иерархических представлений // Проблемы обработки информации в робото-технических системах. М.: Институт физико-технических проблем РАН, 1993. - С. 19-27.

66. Лорьер Ж.-Л. Системы искусственного интеллекта. М.: Мир, 1991.- 568с.

67. Лотон Д.Т., Макконел К.С. Системы понимания изображений // ТИИЭР. 1988. - Т.76, №8. - С. 209 - 227.

68. Марр Д. Информационный подход к представлению и обработке зрительных образов у человека. М.: Радио и связь, 1987. - 402с.

69. Мелихов А.Н., Бернштейн Л.С., Коровин С.Я. Ситуационные советующие системы с нечеткой логикой. М.: Наука, 1990. - 285с.

70. Месарович М., Мако Д., Танахара И. Теория иерархических многоуровневых систем. М.: Мир, 1973. - 344с.

71. Минский М. Структура для представления знаний // Психология машинного зрения / Под ред. П. Уинстон. М.: Мир, 1978. - С. 249- 340.

72. Николаев A.B. Оптическое распознавание символов // Компьютер Пресс.- 1990.-№11.-С. 51-55.

73. Николаев A.B. Оптическое распознавание символов // Компьютер Пресс. 1990. - № 4. - С. 52 - 56.

74. Проектирование специализированных информационно вычислительных систем / Ю.М. Смирнов, Г.Н. Воробьев, Е.С. Потапов, В.В. Сюзов; Под ред.Ю.М. Смирнова. - М.: Высш. шк., 1984. - 359с.

75. Прэтт У. Цифровая обработка изображений: В 2т. М.: Мир, 1982. Т.2. - 480с.

76. Психологический словарь / Под ред. В.В. Давыдова. М.: Педагогика, 1983. - 448с.

77. Психология машинного зрения / Под ред. П. Уинстон. М.: Мир, 1978.-344с.

78. Распознавание образов: состояние и перспективы / Верхаген К., Дёйн Р., Грун Ф.и др. М.: Радио и связь, 1985. - 104с.

79. Реконструкция изображений / Под ред. Г. Старка. М.: Мир, 1992. -636с.

80. Розен В.В. Цель оптимальность - решение (математические модели принятия оптимальных решений). - М.: Радио и связь, 1974. -347с.

81. Розенфельд А. Машинное зрение: Основные принципы // ТИИЭР. -1988.-Т.76, №8.-С. 10- 16.

82. Розенфельд А. Распознавание и обработка изображений. М.: Мир, 1972.-232с.

83. Рок И. Введение в зрительное восприятие. Т.1. М.: Педагогика, 1980. -230с.

84. Савин A.A., Солохин И.П., Васильев В.Н. Иерархическая организация процесса распознавания рукописных знаков // Вопросы радиоэлектроники. Серия ЭВТ. 1982. - № 9. - С. 76 - 86.

85. Сатерленд Н.С. Человеколюбивые машины. В кн.: Человеческие способности машин. М.: Сов. радио, 1971. - С. 23 - 28.

86. СБИС для распознавания образов и обработки изображений / Под ред. К. Фу. М.: Мир, 1988. - 248с.

87. Системы оптического распознавания символов // Информатика. -М.: Машиностроение, 1995. № 3 - 4. - С. 27.

88. Системы технического зрения. / Писаревский А.Н., Чернявский А.Ф., Афанасьев Г.К. и др. Под общ. ред. Писаревского А.Н. JL: Машиностроение, 1988. - 424 с.

89. Соколов E.H., Вайткявичус Г.Г. Нейроинтеллект: от нейрона к нейрокомпьютеру. М.: Наука, 1989. - 180с.

90. Стаут К.Ф. Реализация алгоритмов машинного зрения в параллельных вычислительных архитектурах // ТИИЭР 1988. - Т.76, №8. - С. 145 - 163.

91. Стыскин Б.М. Линейная фильтрация при пирамидальном представлении изображений // Многопроцессорные вычислительные структуры. Таганрог, 1989. - № И. - С. 51-55.

92. Террайен Ч.У., Куатьери Т.Ф., Даджон Д.Е. Алгоритмы анализа изображений, основанные на статистических моделях // ТИИЭР.1986.-Т. 74.-№4.-С. 4-25.

93. Техническое зрение / Под ред. А. Пью. М.: Машиностроение,1987.-413с.

94. Трухаев Р.И. Модели принятия решений в условиях неопределенности. М.: Наука, 1981. - 257с.

95. Ту Дж., Гонзалес Р. Принципы распознавания образов. М.: Мир, 1978.-315с.

96. Утробин В.А. Методы обработки изображений в условиях априорной неопределенности: Дис. . док. техн. наук.- Н.Новгород, 1998.-348с.

97. Утробин В.А. Потенциальные операторы оценивания изображений // Системы обработки информации и управления: Межвуз. сб. науч. тр. Н.Новгород, 1996. С. 17 - 26.

98. Утробин В.А. Симметрийный анализ изображения // Математические методы распознавания образов: Тез. докл. конференции с международным участием, посвященной 60-летию акад. РАН Ю.И. Журавлева. Пущино, 1995. - С. 62 - 63.

99. Фишер Р. От поверхностей к объектам. Машинное зрение и анализ трехмерных сцен. М.: Радио и связь, 1993. - 288с.

100. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977.-319с.

101. Харалик P.M. Статистический и структурный подходы к распознаванию структур // ТИИЭР 1979. - Т.67, №5. - С. 95 - 120.

102. Хорн Б. Определение формы по данным о полутонах // Психология машинного зрения / Под ред. П. Уинстон. М.: Мир, 1978, с. 137 -184.

103. Чукин Ю.В. Структуры данных для представления изображений // Зарубежная радиоэлектроника. 1983. - №8. - С. 35 - 47.

104. Чэн Ш.-К. Принципы проектирования систем визуальной информации. М.: Мир, 1994. - 408с.112. трейдер Ю.А. Равенство, сходство, порядок. М.: Наука, 1971. -254с.

105. Элементы теории биологических анализаторов / Под ред. Н.В. По-зина. М.: Наука, 1978. - 360с.

106. Яншин В.В. Анализ и обработка изображений: Принципы и алгоритмы. М.: Машиностроение, 1995. - 112с.

107. Ясинявичус Р. Параллельные пространственно временные вычислительные структуры. - Вильнюс: Мокслас, 1988. - 183с.

108. Brice C.R., Fennema C.L. Scene Analysis Using Regions // Artificial Inteligence, 1970, vol.1, p. 205 226.

109. Eckstein W. Generalized Gray Morfology for the Extraction of high Objects // The 4-th open Russian - German workshop "Pattern Recognition and Image Analysis" Valday, the Russian Federation, March 3 -9, 1996, p.51 -55.

110. Horn B.K.P., Brooks M.J. The variational approach to shape from shading // Comput., Vision, Graphics and Image Process., 1986, vol.33, p.174 208.

111. Jayakumar H.F., Li R., Youssef M. Parallel algorithms for recognizing handwritten characters using shape features // Pattern Recognition. -1989.-22, №6.-C. 641 652.

112. Kondrat'ev V.V., Utrobin V. A. Fundamentals of the Active Image Restoration Process Theory// Pattern Recognition and Image Analysis.1996, v.7,№l. P. 49-69.

113. Kondrat'ev V.V., Utrobin V. A. Information Model of Decision Acceptance Process for Image Recognition // Computer science, ASRM.1997, №2. -P. 123-146.

114. Kondrat'ev V.V., Utrobin V. A. Uncovering the Uncertainty in the Identification Problem // Pattern Recognition and Image analysis. 1997, V.7, №2. - P. 250-259.

115. Kondrat'ev V.V., Utrobm V. A. Indétermination Uncovering Model in Identification Problem // The 4-th Open Russian-German Workshop "Pattern Recognition and Image Analysis" Valday, The Russian Federation March 3-9, 1996 pp.80-82.

116. Lu Y. Machine printed character segmentation an overview // Pattern Recognition. - 1995. - 28, № 1. - C. 67 - 80.

117. Moukrim A., Muller C. NN and heuristic approach to character recognition //Artif. Neural Networks: Proc. Int. Conf. 1991. - C. 1099 - 1102.

118. Niemann H. Knowledge Based Image Analysis as an Optimization Problem // Pattern Recognition and Image Analysis. - 1994. - Vol. 4, № 4.-Pp. 428 -445.

119. Optical character recognition // Inf. Media and Technol. 1990. - 23, № 1. - C. 16 - 17.

120. Stringa L. Efficient classification of totally unconstrained handwritten numerals with a trainable multilayer network // Pattern Recognition Letter. 1989. - 10, № 4. - C. 273 - 280.

121. Tappert C.C., Suen C.Y., Wakahara T. The state of the art in on line handwritten recognition // IEEE Trans. Pattern Anal, and Mac. Intellect.- 1990. 12, №8.-C. 787- 808.

122. Wang G.-E., Wang J.-F. A new hierarchical approach for recognition of unconstrained handwritten numerals // IEEE Ttrans. Consum. Electron. -1994.- 40, №3.-C. 428 -436.1. УТВЕРЖДАЮ:14 поликлиники № 2 «Сокол»авотдела г. Н.Новгорода1. Боряк А.М.

123. Специалисты поликлиники ознакомлены с возможностями, техническими характеристиками и режимами работы программной системы.

124. Установлено, что вышеуказанная программная система позволяет соответствующему медперсоналу сократить временные затраты на ввод в базу новой информации и избавиться от значительной части рутинной и трудоемкой работы.

125. Программный пакет будет использоваться, начиная с 1999 г., в данном лечебном учреждении для автоматизированного ввода информации в базу данных профилактических прививок и медицинских отводов пациентов.

126. Научный руководитель лаборатории службы АСУП АО «НАЗ «Сокол» к.т.н. доцент МТУСИ Зельманов С.С.1. УТВЕРЖДАЮ:

127. Гл. врач поликлиники № 51 «сого района г.Н.Новгорода ()*' Гаврилова Г.Г.1. Справка о внедрении.

128. Специалисты поликлиники ознакомлены с возможностями, техническими характеристиками и режимами работы программной системы.

129. Установлено, что вышеуказанная программная система позволяет соответствующему медперсоналу сократить временные затраты на ввод в базу новой информации и избавиться от значительной части рутинной и трудоемкой работы.

130. Программный пакет будет использоваться, начиная с 1999 г., в данном лечебном учреждении для автоматизированного ввода информации в базу данных профилактических прививок и медицинских отводов пациентов.

131. Научный руководитель лаборатории службы АСУП АО «НАЗ «Сокол» к.т.н. доцент МТУСИ1. Зельманов С.С.