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

И •• С

ЧЕРНОВИЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. ЮРИЯ ФЕДЬКОЕИЧА

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

ФРАТАВЧАН Валерий Григорьевич

ИАТЕНАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ РУКОПИСНОГО РАБОЧЕГО^ НЕСТА НАТЕКАТИКА - ПРОФАШИСТА

Специальность 05.13. 1 б - применение вычислительной техники, математических методов и математического моделирования в научных исследованиях

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

Чернов:® - 1992.

Работа выполнена на кафедре Математических проблем управления и кибернетики Черновицкого государственного университета им. Юрия Федьковича.

научный руководитель - доктор фиэ, -мат. наук,

профессор ки?иченко Н. Ф.

Официальные оппоненты - доктор технических наук,

профессор винпюк т.к.

кандидат Физ. -мат. наук, допент Черевко И. Н.

Ведущая организация - Киевски'1 государственный университет

в_<г/_часов на заседании специализированного совета к 066.16.05 черновицкого государственного университета по адре< 274012, Чернове.!-12, ул. Коцюбинского, 2, ЧГУ. математический Факуль-ауд. 8.

С диссертацией можно ознакомиться в библиотеке ЧГУ

(ул. Леси Украинки, 23) 1 Автореферат разослан"^?.

Ученый секретари специализированного совета, кандидат Физикo-мaтeмaти"D'■^'u,'

Зашита диссертации состоится

_ 1992 Г.

наук.доцент

САДОВЯК А. Н

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

КТУАЛЬНОСГЬ ТЕГ'. В настоящее время, в связи с применением вы-ислительных средств в разных сферах человеческой деятельнос-и и с бнстрнн увеличением обьенов обрабатываемой информации, ольиое внимание уделяется разработке аппаратных и программах средств взаимодействия человека и ЭЕГГ. Особый интерес впивают системы оперативного ввода графической символьной ин-юрмашш при помоши графических планшетов и сканирующих ус-'Ройств. В связи с этим возникает необходимость разработки 1лгоритмов кодирования и распознавания графических изображе-шй символов, среди зсдач распознавания алфавитно-цифровой графической информации особое место заминает задача ввода руко-шсных слитных текстов. Задаче ввода рукописных натентгичес-<их и программных текстов, их распознавания и обучению рас-юзнавания при приненении графического планшета посвяшена паяная диссертационная работа.

ЦЕЛЬ РАБОТЫ.

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

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

3.Разработка алгоритмов адаптивного обучения - распознавания слитных рукописных текстов.

МЕТОДЫ ИССЛЕДОВАНИИ. Для решения поставленных в работе задач были использованы результаты и положения теории Формальных

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

НАУЧНАЯ НОВИЗНА.

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

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

3.Предложена Форма хранения обобщенных эталонных образов рукописных символов в вше графов грамматического разбора. "

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

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

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

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

Разработанные методы могут быть применены во многих системах анализа и распознавания дискретных сигналов последовательного характера.

СНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАИИТУ. .Разработанные алгоритмы сегментации,аппроксимации и кодирования слитных рукописных текстов, онгинальная система непроиз-¡одннх элементов и разработаннй алгоритм однозначного их вы-.еления.

:. Форма представления обобщенны:: эталонных образов в виде [аправленных графов грамматического разбора структуры конту->ов.

¡.Алгоритм восстановления граФопсдобных грамматик описания >укопнсных образов на ограшпенной последовательности сзуча-жги выборки.

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

М1РОБАШШ РАБОТЫ. Основные положения диссертационной работы докладывались и обсуждались на: Республиканской конференции "Проблемы распознавания"(Киев, 1990)¡Международной конференции "Проблемы создания адаптивных систем" (Кишинев. 1990) -■ Всесоюзной конференции "проблемы создания систем обработки, анализа и понимания изображений"(Ташкент, 1991); Международной конференции "Проблемы украинизация компьютеров" (Львов, 1991), .на республиканском семинаре "Математические проблены управления" (г. Черновцы,рук. проф.н. ф.Кириченко), а также неоднократно на рабочей семинаре каФедры математических проблен управления и кибернетики Черновицкого госуниверситета. ПУБЛИКАЦИИ. По теме и результатам работы опубликованы печатные работы. Результаты исследований докладывались на конференциях и семинарах.

структура объем диссертации, диссертационная работа изложена на печатных страницах машинописного текста, иллюстри-//1

руется рисунками и состоит из введения, трех глав, заклю-

л

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

приложении,

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

во ВВЕДЕНИИ обоснована актуальность проводимых исследива-ний, сфорнулированы цели и задачи работы, описаны основные положения, понятия, разработанные подходы и методы решения задачи распознавай!'!, описаны научные и практические полученные результаты, структура диссертации и основные положения, выносимые на зашит.

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

- осуществление программного интерфейса"планшет-компьютер",

- выбор систены непроизводных элементов для описания рукописных синволов,

- выработка процедур сегментации, аппроксимации рукописных символов непроизводными элементами, "гашение" понех, искажений и неточностей,

- разработка алгоритма быстрого и эффективного грамматического анализа,

- реализация процедур автоматического синтеза грамматических правил в процессе обучения,

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

ПЕРВАЯ ГЛАВА посвяшена описанию и аргументации ЕЫбора системы непроизводных элементов для приближения и описания

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

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

5

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

Ъкр < ч. ♦

где *Ъ - длина непроизводных элементов,

7. ^ =Ух2 + у2 '

ОС, ' Тскгаш координаты "карандаша" в относительной системе координат, после чего сегмент аппроксимируется непроизводным элементом С1. исходя из условия:

СI - агд^гг \%а/>- С¿\ , I - 8.

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

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

и А-*- и-с£ В , сАеЧь , А,&е\/л.

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

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

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

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

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

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

оценка, определявшая дугу перехода е новый i + Ct -ft узел на графе-эталоне, и сумнарная оценка сопоставимости граФов в текущих узлах, исходя пз условия нининуна:

5 (а/ ¿1= 5(1) + пг in d (L + a), О^а^А

где - текущий узел эталона,

¿^^о- номер очередного узла графа-этаяона, SftJ ' суммарная оценка в текушем узле, S(c слшрная оценка в новом узле,

А - коли 1ество дуг возможных переходов из узла L в следующие уалы графа-эталона, CL(L->Cl) вокальная оценка сопоставления J -того узла граФа-реализацшг узлом графа-эта-

лона.

локальная оценка d(i) определяется пороговой Функцией: » t j"0, код t- -го узла граФа-эталока и J то узла

^ граФ..1--реализащш совпадает,

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

ЪУ 'ur W и

9

и,:. 1 (пилкрн MCU03JJHHHX ««irai»!

вления. Эталоны, несовместимые с указанным кодом исключаются из дальнейшего рассмотрения (становятся пассивными). в каждом графе-эталоне один узел отмечен как конечный, и распознанными считаются эталоны, на которых сопоставление достигает конечных узлов. Если таких эталонов несколько, окончательно распознанным считается символ, конструктивно совместимый с сосечними синодами. Следует отметить, что не все символы но.тно распознавать при лоиоии данного алгоритма. [iot--.~-.rKi рукописные слитные комбинации символов нельзя "¡¡гостевать без учета контекста ( "ши" и "иш", '"ан" и

;.• нити,; члгоритм, ревизованный на ПЭВМ класса 1ВИ РС АТ, нозгпгдет вводить и распознавать 2-3 символа в секунду .из расчета алфавита в юо символов, что соответствует реальной средней скорости разборчивого письма.

ВТОРАЯ ГЛАВА посвящена вопросам обучения. В обием случае задача обучения распознаванию образов состоит в следушен. "Учитель" делит возмож1ше ситуации на некоторое число классов. Требуется создать такую процедуру, которая после "наблюдения за действиями "учителя" классифицировала бы ситуации примерно так же, как и он. При структурно-лингвистическом подходе к распознаванию образов обучение состоит в восстановлении грамматик структурного описания (или грамматического поиска) по конечному множеству грамматически правильных образов - обучающей выборке.

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

- все члены выборки - топологически правильные символы одного класса,

- все члены выборки имеют один и тот же порядок обхода контура символа,

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

Процедура обучения состоит из нескольких этапов:

- ввод, аппроксимация, кодирование очередного символа обучавшей выборки,

- построение граФа-реализашш ствола обучавшей выборки,

- восстановление обобщенного граФа-эталона грамматики структурного описания символов класса.

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

граФ-эталон граф-эталон * граф-реализация,

где * - операция объединения направленных графов,

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

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

В результате операции объединения:

Операция объединения направленная графов осуществляется по правилам:

- узлы графа-эталона и графа-реализации просматриваются последовательно попарно,

"недостающему" узлу на графе-реализапш! ставится в соответствие обходящая дуга на графе-эталоне,

- "лишний" узел граФа-реализации вставляется между соответствующими младшим и старшим узлами граФа-эталона (например код вставляется между кодами 1 и ).

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

ТРЕТЬЯ ГЛАВА посвяшена разработке реальной адаптивной :истемн ввода текстово-граФической информации математических текстов и текстов прогрэмн с графического планшета и ее :инхронного распознавания, в главе описаны назначение,

j"6

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

система 'осуществляет:

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

- распознавание рукописного текста в рамках одного определенного почерка или одного стандарта стволов,

- обучение системы оригинальному почерку или новой стандартной системе символов,

- хранение эталонов символьных стандартов и эталонов оригинальных почерков для их дальнейшего использования,

- хранение распознанной информации.

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

- выбор Файла эталонов символов.

- распознавание.

- обучение.

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

В ЗАКЛЮЧЕНИИ диссертации указываются возможности применения система распознавония. а также отдельных ее элемениов

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

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

ОСНОВНЫЕ вывода И РЕЗУЛЬТАТЫ: 1. Разработаны алгоритмы ввода, сегментации, апроксимании и одирования контуров слитно написанных рукописных текстов. : качестве системы непроизводных элементов структурного писания в условиях ввода с графического планшета аелесо-бразно использовать систему цепочного кодирования Гузнаяа. азработан алгоритм однозначного кодирования контуров сис-'емой Гузмана.

г.Разработана Форма представления грамматик структурного шисания или обобщенных эталонных образов классов рукопис-шх символов в виде направленных графов грамматического 'азбора структуры контуров.

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

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

5.На основе описанных выше результатов разработана адаптируемая к конкретным почеркам система ввода и распознавания рукописных слитнонаписанных программных текстов.

Основные результаты диссертации описаны в следующих работах:

1. Гайдайчук П. В. .Еирнченко Н. Ф. .фратавчан В. г. Исследования .проблем математического обеспечения САПР обЬектов управления, цифровой обработай информации и рукописного интерфейса в черновицком госуниверситете, //Проблемы создания систем обработки, анализа и понимания изображений, тез. докл. всесоюзной конференции. Ташкент:АН УзССР. 1991 г. с. 130. г. Кириченко Н. Ф., фратавчан в. г., гайдайчук И, в. Распознавание украиноязычных слитных текстов. //Проблемы украинизации компьютеров. Тез. докл. междунар. конференции. Львов: ИК АН Украины. 1991 г. с. Т.

3. фратавчан в, Г. применение методов композиции, динамического программирования, поиска на графах В распознаваний рукописных символов, //кибернетика. Киев: ИК АН Украины, (печ.)