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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

РГБ ОД

1 5 ДЕК 1398

СТАРКОВ ЕВГЕНИЙ ФЁДОРОВИЧ

УСТРОЙСТВА РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ СИМВОЛОВ НА ОСНОВЕ ШАБЛОНОВ

специальность 05.13.05 "Элементы и устройства вычислительной техники и систем

управления"

Автореферат Диссертации на соискание ученой степени кандидата технических наук

КУРСК 1996

РАБОТА ВЫПОЛНЕНА В Курском государственном техническом университете

НАУЧНЫЙ РУКОВОДИТЕЛЬ - доктор технических наук,

профессор ТИТОВ B.C.; кандидат технических наук, доцент ДОВГАЛЬ В.М.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: доктор технических наук,".'-

профессор Сизов A.C., кандидат технических наук, доцент Лопин В.Н.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ опытно-конструкторское бюро "Авиаавтоматика"

ЗАЩИТА СОСТОИТСЯ "5В"ноя§РЯ 19Э6 года на заседании

' J г\ 0О

диссертационного совета Д064-.50.02 Курского JV — государственного технического университета по адресу: 305040, т. Курск, ул. 50-лет Октября, д. 94, конференц-зал.

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

АВТОРЕФЕРАТ РАЗОСЛАН "¿?(з" октября 1996 Г.

Учёный секретарь д.т.н., проф.

Кореневский H.A.

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

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

Работа выполйена по плану Гскомвуза РФ на 19921995 г.г. от 16.03.92 г. IV 10-36-41 ИН/10-20-03 (тема "Разработка и исследование характеристик процессорных элементов систем обработки символьной информации"),* а также распоряжением Госкомвуза РФ от 19.02.93 г. 8> 10 "Технические системы обработки символьной информации и изображений" (международный проект).

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

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

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

1. Исследование модифицированной модели спинового стекла для оценки её информативной ёмкости (количество эталонов классифицируемых графических объектов при фиксированном числе, элементов).

2. Разработка метода определения информативных признаков (шаблонов) графических объектов.

3. Анализ свойств спинового стекла для определения его граничных параметров на основе численного моделирования .

4. Моделирование процессов распознавания на основе метода шаблонов и сопоставительный анализ результатов .

5. Разработка последовательных и параллельных специализированных процессоров распознавания изображе-, ний символов и формирования кодов обрабатываемых символов.

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

Научная новизна работы состоит в следующем:

1. Предложена модифицированная математическая мо^. дель спинового стекла, дающая возможность определить' его информационную ёмкость при фиксированном числе элементов и ограничительные условия для используемых эталонов.

}

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

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

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

на этапе классификации и не требуют новых технологиче-

»

ских процессов при их производстве.

На защиту выносятся:

1. Модифицированная математическая модель спино--вого стекла.

2. Метод выделения значимых информативных признаков (шаблонов) спинового стекла.

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

4. Технические средства распознавания в виде устройств последовательного и-параллельного действия.

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

Апробация работы. Основные результаты диссертационной работы докладывались и получили положительную оценку на международной конференции "Оптико-электронные приборы и устройства/в-' системах распознавания образов, обработки изображений тл^ символьной информации" (г.Курск, 1993г.), Юбилейной конференции учёных Курского политехнического института, 2-й международной конференции "Распознавание - 95" (г. Курск, 1995 г.).

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

Структура-й объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения и приложений, содержали* 127 страниц основного текста; содержит 51 рисунок, 74 наименования библиографии и 53 страницы приложений, всего страниц - 184, таблиц 11.

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

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

В первой Елаве проведён анализ состояния и тенденций развития систем обработки изображений графических объектов на примере систем обработки графических изображений символов. Одной из важнейших задач обра-

I <

ботки символов является задача распознавания изображений символов.

С этой целью применяются методы распознавания образов по минимальному расстоянию и метод опорного словаря. Интенсивно развиваются новейшие подходы к созданию структурных -методов распознавания образов. Адаптивные модели и системы представляют ещё один аспект эволюции теории и практики распознавания образов. Одной из перспективных моделей адаптивных систем является "спиновое стекло".

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

•

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

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

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

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

Спиновое стекло в математической модели Хопфилда представляет собой одномерный массив данных

S = (S,.....S Su), ■ (1) ;

lin

где Si » {-1,1J ;

N - число элементов спинового стекла.

Все элементы попарно связаны. Связь между двумя элементами характеризуется коэффициентом связи

vvv (2>

где i » 1,2»M; j - 1,2,„,N; i f j.

Одна матрица коэффициентов связей соответствует двум взаимно инверсным состояниям спинового стекла.

Состояние спинового стекла характеризуется интегральным показателем - суммарной энергией связей

, . (3)

где ДЕ^ -энергия связей i-того элемента;

<4)

Степень близости двух состояний спинового стекла определяется дистанцией по Хеммингу

ф'У)----, (5)

I , .

где Б", Б1 - состояния спинового стекла;

q(Sk, S1) - перекрытие между состояниями S*, S1.

v / \ "kl" 9(S 'S • (6)

/V „, i i

Подставляя в (4) значение коэффициентов связей (2) и полученное выражение для энергии связей i-ro элемента в (3),- получим значение суммарной энергии связей спинового стекла и с. учетом (5) и (6) имеем

E = -N2*(l-2*J(.S,S0))2, (7)

где d(S,S") - дистанция между состояниями S,S°..

Введем новую величину, называемую удельной энергией -

Е--, (8)

" N *М

где M - количество эталонных состояний.

Подставив в (8) значение Е из (7) получим

u M M ■ м

Функция (9) гладкая, принимаёт максимальное значение в точке d=0.5 и минимальное значение в точках d=0 и d=l. Значения функции изменяются в интервалах от нуля до минус единицы. Функция удельной энергии обладает свойством принимать минимальные значения в точках, соответствующих эталонному состоянию и инверсии эталонного состояния спинового стекла. 'Это свойство функции используется для хранения и поиска эталонного состояния спинового стёкла.

Для минимизации функции удельной энергии необходимо, чтобы все значения (4) были меньше нуля

,*S <0. (10)

i i jS IJ J

Отсюда

н

" » ^ 3■ 1 , (11) 5 (О, при .<»>—а.

I О ;

где^и) - значение в момент времени I:;

- значение в! в момент времени С - момент времени до принятия решения об изменении или не изменении текущего элемента;

t+l - момент времени после принятия решения об изменении или не изменении текущего элемента.

Для хранения нескольких эталонных состояний необходимо вычислить обобщенные коэффициенты связей

где К*^ - коэффициенты связей эталонного состояния га;

С учетом (2), (3), (4), (22) имеем

* к и

М ■ >1 } «-1 « 1

На основании (5), (6), (10)"имеем

* —(14)

II М Н

Функция (14) гладкая, имеет один глобальный максимум равный нулю, соответствующий точке в которой значения всех дистанций 0.5, что опровергает гипотезы о наличии много экстремального "ландшафта". Т.к. аргументы функции ограничены в интервала [0;1], функция имеет несколько локальных минимумов. Аргументы функции являются зависимыми между собой. Вид зависимости аргументов определяется заданными эталонами и может быть определён только для каждого конкретного (набора эталонов. В этой связи не представляется возможным заранее

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

Для того чтобы сделать возможным распознавание по методу минимизации энергии необходимо чтобы эталоны отвечали следующим условиям: дистанция между каждой парой эталонов должна лежать а интервале (0,0.5); линия, образованная значениями функции (14) на границе области определения должна быть гладкой; число локальных минимумов функции (14) должно равняться числу эталонов.

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

АЯ--<15> I ' " у а ( J

С учетом (5, 6)

Отоюда следует, что

и

МЯ^гМ^'О^Ч^Ур). >- (17)

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

В третьей главе приведены результаты численного моделирование процессов распознавания с целью получе-

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

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

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

На рис. 1. приведён пример эталонного символа и иаблон этого символа.

График {рис. 2) отражает зависимость погрешности распознавания от коэффициента заполнения спинового

стекла при использовании различных способов распознавания. На графике значение погрешности попадает- в область между соответствующими кривыми. График показывает, что использование модифицированного алгоритма вычисления перекрытия с использованием шаблонов позволяет повысить информативную ёмкость на 30%-35%.

Данные об изменении границы области достоверного распознавания при использовании различных способов отражены на графике (рис. 3). В качестве показателя уровня зашумлённости эталонного символа используется дистанция между искажённым символом и его эталоном. На графике значение уровня зашумлённости попадает в область между соответствующими кривыми. Из графика видно, что использование модифицированного вычисления дистанции по шаблонам позволяет обрабатывать изображения с уровнем зашумлённости до 30%-40%, что существенно превышает возможности распознавания с' использованием известных способов, включая способ Хопфилда.

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

Блок-схема устройства распознавания , символов последовательного действия представлена на рис. 4. Устройство состоит из следующих блоков: блок управления

микропрограммного типа, блок хранения эталонов, блок коэффициентов, блок шаблонов, блок распознавания.

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

В состав блока коэффициентов входят: блок памяти коэффициентов, предназначенный для хранения обобщённых коэффициентов связей и реверсивный счётчик.

В состав блока шаблонов входят: блок памяти шаблонов, сумматор, три регистра, устройство сравнения, блок перевода в дополнительный код.

Блок распознавания осуществляет распознавание текущего символа и подаёт на выход устройства значение его кода. Блок памяти текущего символа осуществляет хранение информации о символе, поступившем для распознавания. Регистр РгН . хранит код текущего эталонного символа. Регистр РгР хранит минимальное значение' дистанции. Счётчик СчВ вычисляет и хранит текущее значение дистанции.

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

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

выполняемые при подготовке эталонов и классификации текущих символов.

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

Блок распознавания осуществляет сравнение текущего символа с•эталонными и шаблонами эталонных символов, используя параллельный блок сравнения, и подаёт на выход устройства значение кода распознанного символа. Схема блока распознавания параллельного действия представлена на рис. 5. В состав блок5 входят: блок памяти текущего символа, один регистр общего назначения, блок сравнения.

Блок сравнения предназначен для сравнения текущего и эталонного символов. Вычисление дистанции произ-»

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

Г=*МЛГ,©Х,)&Я, (18)

где Х1 - значение, элемента эталонного символа;

Хг - значение элемента текущего символа;

Н - значение шаблонного элемента;

¥ - результат сравнения.

Из ячеек формируется блок сравнения. Число ячеек сравнения соответствует количеству элементов в символе. Использование принципа параллельной обработки'ин-

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

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

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

3. На основе метода шаблонов разработаны алгоритмические средства для моделирования процессов распознавания. Получены экспериментальные зависимости для известной и предлагаемой моделей, которые позволили установить, что-"использование метода и алгоритмов на основе шаблонов увеличивает информативную ёмкость спинового стекла на 30%-35% в условиях зашумления текущих конфигураций (подлежащих классификации) до 35%-40% от числа элементов спинового стекла.

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

5. Разработано устройство распознавания параллельного действия, позволяющее увеличить производи-

I

тельность по отношению к устройству классификации последовательного действия в 15-20 раз.

Основные результаты диссертации нашли отражение в работа^:

1. В.М. Довгаль, Е.Ф. Старков. Метод распознавания конфигураций с помощью шаблонов классификации. -М. : ВИНИТИ, Депонированные научные работы. -1992. -№4. -С. 72.-76

2. В.М. Полунин, В. А. Зрайченко, Е.В. Пьянков, Е.Ф. Старков. О магнитоупругом преобразовании магнитной жидкости // Магнитная гидродинамика. -1988. -№ 3. -С. 128-130.

3. Е.Ф. Старков. Об одном способе устранения помех на 'чёрно-белом изображении /Тезисы докладов международной конференции "ОптикО-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации", Курск: КПИ, 1993г., С. 31-32.

4. Е.Ф. Старков, Ф.А. Старков. Метод классификации изображений на основе шаблонов. /Тезисы докладов международной конференции "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации", Курск: КПИ, 1993г. С. 31-33.

5. Е.Ф. Старков. Нейронно-структурная модель распознавания изображений символов• /Тезисы докладов Юбилейной конференции учёных Курского политехнического института. Курск: КПИ, 1994г. С. 98-100.

6. Е.Ф. Старков. Устройство выделения ядра класса изображений /Труды Юбилейной научной конференции. Курск: КурГТУ, 1995 г. С. 62-64.

7. Е.Ф. Старков. Практическое применение устройств оптического ввода символьной информации /Сборник материалов 2-й международной конференции "Распознавание - 95". Курск: КурГТУ, 1995г.. С.197-198.

Пример эталонных символов и их шаблонов

************************** ******* ** * ******* ★ * * * * * * * *

************************** ******* ** * ******* * ** * * * * * *

* ** *** * * * * * *

*** *** *** ** *

★ * * *** *** *★*

★ * * *** • *** ***

* * * *** ******* * * * ******* * * * * * * ** *

* * * * ** ******* ** * ******* * * ** * *** *

* * * * ** *** ***

★ * * * * * *** ***

* ** * * * *** ***

* ** * * * *** * * *

************************** ******* ** * ******* * *** * * * **

************************** ******* ** * ******* * *** * * * * *

000000000000000000 000000000000000000 111 111 111 111 • 111 111 111 111

Рис. 1

График зависимости погрешности распознавания от коэффициента заполнения при использовании различных

методик

Рис. 2,

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

Рис. 3.

Устройство распознавание символов.

Е

агор-

Ы Ы Ы 1т-

Д11

Блок коэффициентов

\—I----

I т

Д5

Блок хранения эталонов

Д8

Блок управления

К

Ц4

Ц —V

Блок шаблонов

Блок распознавания

ТУТ^ЗИ

ДЭ

Рис. 4 .

Елок распознавания параллельного действия.

Рис. 5

График зависимости временной сложности от числа элементов символа

Рис .6

График зависимости количества ячеек сравнения от числа элементов символа

1

\

1 !

1

^

г 1 • 1

1 » *.... ■}. Т-1Т1 ггг.

^~.Рис. 7,.

Соискатель • Е. Ф. Старков

Подписано к печати ЗАЛО.вб • Формат 60 х 84 1/16 Печатных листов 4.5 .Тираж 100 экз. Заказ .

Курский государственный технический университет. 305040. г. Курск, ул. 50 лет Октября, 94.