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

НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ

УДК 681.3:519.246 (}Д

САМОХВАЛ ВЛАДИМИР АНАТОЛЬЕВИЧ

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

05.13.16 - Применение вычислительной гехиики, математического моделирования и математических методов в научных исследованиях

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

Минск -1998

Работа выполнена в Институте технической кибернетики Национальной Академии наук Беларуси

Научный руководитель: доктор технических наук, профессор Садыхов Р.Х.

Официальные оппоненты: доктор технических наук, профессор Лобанов Б.М., кандидат физико-математических наук, доцент Краснопрошин В.В.

Оппонирующая организация: НИИ "АГАТ", г. Минск

Защита состоится " 6 " октября 1998 г. в 14 час. 30 мин. на заседании совета по защите диссертаций Д01.04.01 при Институте технической кибернетики HAH Беларуси по адресу: 220012, Минск, ул. Сурганова, 6, конференц-зал, тел. 284-20-84.

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

Автореферат разослан " СЗ" С с nsoStTj* 199g Г-

Ученый секретарь совета по защите диссертаций, д.т.н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

- идентификацию объектов на компактной группе некоторых предопределенных классов образов (проблема распознавания стандартизованных/стилизованных рукописных цифр и букв текста);

- верификацию сигнатур (подписей).

Характерной особенностью задач распознавания образов является большой объем данных, подлежащих обработке. Первоочередные требования при решении указанных задач - достижение; максимального быстродействия при обеспечении необходимого уровня распознавания - обусловлены большими объемами потоков данных и уровнем надежности, необходимым для принятия решения. Так, в задаче верификации подписи исходные двумерные массивы отсчетов, подаваемые на вход распознающей схемы, имеют размерность порядка 215*18 байт, а время принятия решения ограничено единицами секунд. Быстродействие систем классификации стилизованных цйфр на порядки выше и лимитируется величиной 10'2 с.

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

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

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

Связь работы с крупными иаучмыми программами и темами. Работа выполнена в лаборатории идентификации систем Института технической кибернетики HAH Беларуси и на кафедре ЭВМ Белорусского государственного университета информатики и радиоэлектроники в рамках следующих НИР:

1. Проект № Т94-145 Фонда фундаментальных исследований Республики Беларусь "Разработка математических моделей, методов и алгоритмов для синтеза оптимальных систем распознавания реального времени", 1995-1996 г.г.

2. Конкурсные программы Министерства Образования и Науки РБ, задание № 96-3046,199бг„ задание №96-3087, 1996-1997г.г.

3. ГНТП " Информатика" , подпрограмма 01, задание 01.02.10 "Разработать систему реального времени для обработки видеоизображений", 1997-1998 г.г.

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

Поставленная цель определяет следующие основные задачи:

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

- анализ преобразований Фоли-Сэммона, Хотеллинга и синтетических ' дискриминантных функций (СДФ) и разработка их модификаций;

- установление взаимосвязи между различными дискриминантными методами и синтез обобщенного классификационного алгоритма;

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

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

Научная новизна работы.

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

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

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

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

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

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

Практическая ценность работы заключается в том, что результаты,

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

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

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

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

- алгоритм расширения 1-мерного усеченного преобразования Адамара на 2-мерный случай;

- алгоритм локального преобразования спектра связности;

- метод и алгоритм выделения информативных признаков на основе операции свертки;

- модифицированный алгоритм построения синтетических дискриминантных функций;

- алгоритм масштабного преобразования.

Личный вклад соискателя. В совместных работах участие руководителя носит постановочный характер. Все данные, представленные в работе, получены автором лично.

Апробация работы. Результаты исследований, включенные в диссертацию, докладывались на Международной конференции по автоматизации, робототехнике и компьютерному видению (1САК.СУ'94, Сингапур, 1994г.), Международном симпозиуме по компьютерным и информационным наукам (ВСВ'К, Турция, 1994г.), Международной конференции по распознаванию образов и анализу изображений (РША'95, Минск, 1995г.), научно-технической конференции "Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления", Минск, 1995г.

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

Структура и объем диссертации. Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения, списка литературы из 92 наименований. Диссертация изложена на 119 страницах машинописного текста, включает 2 таблицы,'иллюстрирована 19 рисунками.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

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

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

- анализ дискриминантных методов и разработку эффективного обобщенного классификационного алгоритма;

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

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

Во второй главе рассматриваются дискриминантные методы на основе преобразований Фоли-Сэммона (ПФС) и Хотеллинга (ПХ), проявляющие оптимальные свойства с точки зрения декластеринга, и методы на основе синтетических дискриминантных функций (СДФ). ПФС и ПХ основаны на критериях, формулируемых в терминах матриц межклассового 5] и внутриклассового разброса 5'г. ПФС разработано для задачи двух классов и интерес представляют два первых дискриминантных вектора <31 и йг. Аналитические выражения для дискриминантных векторов включают произведение 57'Д, где Д - вектор разности средних двух классов. Основная трудность в определении векторов ¿1 и ¿2 заключается в вычислении инверсной матрицы 57', поскольку на практике размерность изображения N обычно больше, чем полное число обучающих изображений М (недоопределенная проблема), матрица сингулярна и обратная матрица 57' не существует. Поэтому инверсия заменяется псевдоинверсной матрицей вычисляемой на основе обращения ковариационной матрицы

изображений . Существование можно обеспечить при условии М < Л' , в результате приходим к ограничению на объем обучающей выборки для отдельного класса М1 < Ы/к, / = 1,..., к , где к - число классов объектов. Ограничивая N < 27» «10'- и учитывая, что для двухклассовой проблемы М1 =N/2 получаем условия реализации ПФС на ЭВМ:

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

лг<100 М., <N/2

(О

конструктивных выборок для каждого класса {М( ~ Мс, / = 1,..., к), а это удобно для оптимизации вычислительного алгоритма, и ограничивая размерность пространства признаков величиной ~ 27, имеем

М = кМс £ 27, (2)

откуда

к<, 2УМС . (3)

Поскольку, как правило, используют Мсй 10 я 23, и для ПХ можно сформулировать условие оптимальности как

к < Л7Л/С®27/23 — 16 . (4)

Синтетическая дискриминантная функция Ь определяется из уравнения

И^Ь = с , (5)

где Шт бй""*- матрица обучающих изображений, с е(Яи"- вектор с постоянными компонентами со. Решение для фильтра Ь записывается в виде

Ь = Щ1ГГГГ)~' с = с , (6)

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

матрицы изображений И1и=Т¥тТ¥. Для задачи распознавания в двух классах можно

к, = с. ,

(7)

причем 0, матрица Ж включает обучающие выборки обоих классов, а

С!г=[ 1 ... 1;0...0], сгт= [0 ... 0; 1 ... 1 ].

Далее устанавливается связь методов ПФС(ПХ) и СДФ. Показано, что выражение (6) можно привести к виду

Ь = Л"'Д , (8)

где Д = ЮГг - корреляционная матрица, которое по форме совпадает с выражением для первого дискриминантного вектора ПФС. Таким образом, все •указанные методы имеют формальное сходство, что позволяет синтезировать обобщенный алгоритм их реализации на основе одной базовой операции - инверсии ковариационной (корреляционной ) матрицы изображений.

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

Построение селектора признаков проводится на базе глобального и локального преобразования. В качестве глобального за основу построения выделителя признаков использовано 1-мерное усеченное преобразование Адамара (УПА). Этот выбор обусловлен следующими свойствами УПА:

- преобразование относится к классу быстрых;

- преобразование обеспечивает сжатие данных в отношении ~ N11о§2 /V;

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

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

1 -мерное УПА генерирует п = 1 коэффициентов спектра мощности, где

N - размерность вектора данных. Предлагается расширение этого преобразования на двумерный случай последовательным применением I-мерного преобразования сначала к строкам (столбцам), а затем к столбцам (строкам) матрицы изображения. Такая модификация приводит к генерации расширенного набора признаков. Так, для изображения размером N - М*.М , где М = 2к , 1-мерное УПА генерирует п = \ogiN + 1 = 2к + 1 информативных признаков. При 2-мерном УПА исходное изображение сжимается в (к + 1)*(к + 1)-магрицу коэффициентов спектра мощности, которые рассматриваются как вектор данных размерности (к + I)2 х 1. Определенное описанным образом 2-мерное УПА обладает всеми свойствами 1-мерного преобразования, сохраняя, в частности, инвариантность к операции сдвига исходного изображения.

Таким образом, выделители признаков на основе 1- и 2-мерного усеченных преобразований Адамара осуществляют следующие пространственные отображения:

1-Р_УПА ^ ЭД^*'

2-Р..ТОЛ ) щ(к+1)*{к+1)

В вычислительном аспекте реализация 1-мерного УПА требует проведения порядка ЗЛ' сложений и /V умножений, а для 2-мерного УПА - ЦТЯ+кМ) и М+кМ соответственно. Тем не менее, 2-мерное преобразование оказывается более эффективным в пересчете на один информативный признак.

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

Более детальный учет структуры изображения, что соответствует расширению набора признаков, может быть выполнен несколькими способами. Во-первых, учет сегментов линий промежуточных направлений (я/8 + Ъг/4, к - 0, 1, 2, 3) достигается увеличением сверточного массива до размеров 5x5 и соответствующим выбором ненулевых элементов маски. На этой основе можно провести преобразование, генерирующее 8 интегральных признаков:

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

пи) -> & , /=0,3.

(Ю)

-> б, , /=0,7.

(Ч)

Формально, описанное выше преобразование осуществляет отображение исходного пространства размерностью N х N в более компактное пространство размерностью L х M, т. е.

-> Пи" (12)

Коэффициент сжатия информации к ~ N11( M х L ) определяется величинами L и М. В свою очередь, L зависит от размеров матрицы преобразования, a M определяет степень дискретизации порога р или, фактически, уровень детализации величин Qitri) (размерность векторов q/ ). Полученные в результате преобразования величины Ф могут быть использованы для построения классификатора, при этом у исследователя имеется возможность варьировать размерность пространства признаков в широких пределах.

Далее в третьей главе вводится новое локальное преобразование - спектр связности. Оно основано на свойстве связности бинарного изображения и заключается в интегральной оценке величин вида

CF-Ï2kFk , (13)

i-0

где CF ~ связность точки F = F(i, j), а индекс к обозначает соседние с F элементы изображения. На основе свойства связности бинарное изображение может быть преобразовано в многоградационное, когда значение каждого единичного пиксела заменяеся величиной его связности, т.е.

F(i,j)-> CF - (14)

С другой стороны, накапливая частоты {f( j) — f(j) + I | C=j } для всех возможных О < С £ 255 по всем единичным пикселам, получаем спектр связности -упорядоченный набор 256 величин, характеризующий локальные свойства точек исходного изображения.

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

Одним из свойств спектра связности является независимость размерности пространства преобразования от размеров исходного изображения. Для произвольного бинарного изображения можно записать

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

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

Таблица 1.

Характеристики объектов экспериментальных исследований

Тип объекта Размер изображения Способ формирования образа Число типов образов Постановка задачи классификации

Рукописная подпись 215^. 216 байт Баллистический Не предопределено 1(2)-классовая

Рукописные цифры 2">байт Стандартизованный >=10 10-классовая

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

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

Задача верификации подписи решалась следующими основными методами. Метод Б1: комбинация селектора признаков на основе 2-и УПА с классификацией на основе ПФС.

Метод Б2: комбинация селектора признаков на основе 2-Т> УПА с классификацией на основе ПХ.

Метод БЗ: комбинация селектора признаков на основе 2-0 УПА с классификацией на основе СДФ.

Метод 84: комбинация селектора признаков на основе преобразования спектра связности с классификацией на основе упрощенной СДФ.

В дополнение к четырем основным методам проводилось сравнение эффективности 2-мерного и 1-мерного преобразований УПА и оценка вклада компонетг 2-мерного

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

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

Метод ОI: с селектором признаков на основе преобразования 1 -О УПА. Метод с селектором признаков на основе преобразования 2-Б УПА. Метод ОЗ: с селектором признаков на основе преобразования спектра связности.

Дополнительно были исследованы две модификации метода БЗ заменой свойства 8-связности на 4х- и 4+-связность, а также эвристический селектор признаков на основе процедуры масштабного отображения.

Рис. 1. Основные модули обобщенной классификационной схемы и реализованные методы моделирования задач классификации рукописной подписи (->) и рукописных цифр (—>).

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

База данных лая проведения сравнительных исследований включает 280 полутоновых образцов формата 256x128, состоящая из оригиналов, выполненных семью лицами Р1-Р7, по 20 каждого типа, и тщательно выполненных подделок, по 20 на каждый тип оригинала, Уточнение статистических показателей для оптимальной классификационной схемы проводилось на дополнительной выборке большого объема, содержащей по 96 оригиналов и подделок.

V) Ю 1» 160 200 » М »-2 0.9 ОЛ «

а) б)

Рис.2. Операционные характеристики (кривые ошибок) в задаче верификации подписи: а) - модель ЙЗ; б) - модель Б4.

а) б)

Рис.3. Диаграммы рассеяния в задаче верификации подписи: а) - модель S1; б) -модель S2.

Уровни корректной классификации составили в среднем 89% для преобразования Хотеллинга и 92% для преобразования Фоли-Сэммона. Вариации по отдельным группам образов оказались в пределах 72% - 94% и 77% - 97% соответственно (табл. 2). Наиболее высокий результат ( >95% ), подтвержденный экспериментом на выборке большого объема, получен методом S4, объединяющем спектр связности с классификацией на упрощенной СДФ.

Таблица 2.

Результаты эксперимента по верификации подписи

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

1-D УПА 2-ОУПА Спектр связности

ПФС 2 - 92% (77% -v 97%) -

ПХ 2 - 89% (72% * 94%) -

СДФ 1 - 85% (68% + 92%) -

2 69% (49% -ä- 81%) 90% (73% + 95%) -•

Упрощенная СДФ 2 77% (55% -85%) ' >95% (86% 100%)

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

База данных для экспериментов состояла из 4000 образцов - 400 на каждый класс. Модели Dl - D3 в задаче идентификации цифр показали уровни кореектных классификаций -80% в различных классах образов. В связи с этим в работе предложено масштабное преобразование, состоящее из нескольких этапов (процедур), которые последовательно реализуют:

1) операцию дилатации изображения DIL (F4Sxi4) -> F14Sx64 ;

2) определение границ объекта, F1-> F2^ , при этом достигается инвариантность к сдвигу;

3) отображение паттерна на сетку 5x3, 1^тХп -* F3;^ .

Включение компонент FmXn в F}x3 проводится с пороговым ограничением. Выбор порога осуществлялся усреднением компонент FSx} с последующей вариацией величины около уровня определяемого соотношением

р-а E[FSx3]±h,

где Е[ ] - оператор взятия математического ожидания, а коэффициент а и допуск Д определялись экспериментально для достижения максимального уровня распознавания.

В результате реализации описанного алгоритма преобразования с последующей классификацией объектов методом уСДФ достигнут уровень распознавания >95% (рис. 4).

000000Ш& ОООООООООо

:М ! I т 111 И 11 < \ М 11 I

гхтш21шшт2.1 \

3333333335 3333 ЗзЗЗ33 !

ЦЩЦЩЦЦЦ1] ч4у ЧШчЧЭД

5555555556" 55556 ^5555 ;

: 66 б6бЪббб 6* кб;6Ь6<0&е<Ьб !

1-ГПШП? 77Т7т?ГТ$\

]ж8ШВ8%ттт&т \

<Э99999ЧЯ9 ШШШрШ

| пш гаюскп = звв ЕШОЮ мпт> ' з :

Рис. 4. Фрагмент базы данных и результат классификации стилизованных цифр: конструктивные (слева на более темном фоне) и тестовые (справа на светлом фоне) образы и ошибки классификации.

ВЫВОДЫ

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

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

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

4. Введено понятие спектра связности - локального преобразования, основанного на свойствах связности бинарного изображения и разработан алгоритм его реализации для выбора информативных признаков изображений. Установлена связь спектра связности и некоторых типов процедур селекции признаков на масках размером 3x3. Показана эффективность спектра как селектора признаков в сравнении с детекторами на основе свертки как по информационной емкости, так и по временным показателям.

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

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

7. Экспериментально установлены границы эффективности дискриминантных методов для двух типов задач распознавания символов и показаны уровни корректного распознавания более 90% для задачи верификации подписи и более 95% при классификации стилизованных рукописных цифр.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Sadykhov R.H., Samokhval V.A. System Design for Signature Verification in Reduced Dimension Space/ Proceedings of the 3-d International Conference on Automation, Robotics and Computer Vision - ICARCV'94. -Singapore. -1994. - P.907-910.

2. Sadykhov R.H., Samokhval V.A. PC-based System for Signature Verification/ Proceedings of the DC International Symposium on Computer and Information Sciences - ISCIS-IX, Turkey. -1994. -P.77-81.

3. Sadykhov R.H., Samokhval V.A. Method and Algorithm of Identification Based on Spectral Representations / Proceedings of the 3-d International Conference "Pattern recognition and Image Analysis".-Minsk.-1995.-Y.3.-P.35-42.

4. Samokhval V.A., Sadykhov R.H. The Use of Connectivity Spectrum for Signature Verification/ Proceedings of the 3-d International Conference "Pattern Recognition and Image Analysis".-Minsk.-1995.-V.3.-P. 43-4«.

5. Samokhval V.A., Sadykhov R.H. Comparative Study of 1- and 2-D Truncated Hadamard Transforms for Signature Verification/ Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления. Материалы научно-техн. конф. Часть I. - Минск. БГУ. - 1995. - С. 64-68.

6. Садыхов Р.Х., Самохвал В.А. Верификация подписи на основе трансляционных инвариантов/ Тез. докл. респуб. науч.-тех. конф., посвящ. 30-летшо БПИ. -Брест. -1996. - с. 109-110.

7. Садыхов Р.Х., Самохвал В.А. Система верификации рукописной подписи: методы и алгоритмы/Теория и техника передачи, приема и обработки информации. -Тез. докл. 2-й междунар. конф. -Туапсе.-1996.' -4.2. -с. 105-106.

8. Садыхов Р.Х., Самохвал В.А. Верификация подписи на основе аппарата дискриминантных функций/ Вести АН Беларуси. -1997. -Сер.физ.-мат. наук. -№3. -С.123-126.

РЭЗЮМЭ САМАХВАЛ Уладамф Анатольев1Ч

Распрацоука метадау 1 алгарыгмау распазнавння рукашсных ймвалау на аснове апарата дыскрымшантных функцьш

Юпочавыя словы: распазнаванне рукашсных амвалау, пераутварэнш Фоль Сэммана, Хогэллшга, ин-гэтычныя дыскрымшантныя функцьн, пераутварэнне Адамара, спектр звязнасщ.

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

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

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

РЕЗЮМЕ САМОХВАЛ Владимир Анатольевич

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

Ключевые слова: распознавание рукописных символов, преобразования Фоли-Сэммона, Хотеллинга, синтетические дискриминантные функции, преобразование Адамара, спектр связности.

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

Приводятся алгоритмы построения дискриминантных векторов и некоторые их модификации. Устанавливается связь дискриминантных векторов преобразования Фоли-Сэммона (Хотеллинга) и синтетических дискриминантных функций, проводится обобщение условий существования решений и базовых процедур вычисления и на этой основе разрабатывается обобщенный алгоритм классификации на группе дискриминантных методов анализа.

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

SUMMARY

SAMOKHVAL Vladimir Anatolievich

DESIGN OF METHODS AND ALGORITHMS FOR HANDWRITTEN CHARACTER RECOGNITION ON THE BASIS OF DISCRIMINANT FUNCTION

APPARATUS

Key words: handwritten character recognition, Foley-Sammon transform, Hotelling transform, synthetic discriminant functions, Hadamard transform, connectivity spectrum.

Image recognition model based on data compression by global/local transform followed by application of discriminant functions for classification is suggested. Image feature selection algorithms based on truncated Hadamard transforms and connectivity spectrum transform are adduced. Feature selection methods on the basis of convolution operation arc proposed.

There are adduced algorithms of constructing discriminant vectors and some their modifications. The relation between Foley-Sammon transform discriminant vectors and synthetic discriminant functions is established, generalizations of decision existance conditions and basic calculating procedures are carried out, and on this platform generalized classification algorithm based on the group of discriminant analysis methods is developed.

Different recognition models are programmed and the effectiveness of proposed approach is shown experimentally on the tasks of handwritten character recognition.