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

Введение к работе

Актуальность темы диссертации. Среди множества задач обработки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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