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

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

Четрафилов Иван Димитров

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И СИСТЕМ РАСПОЗНАВАНИЯ ОПТИЧЕСКИХ ОБРАЗОВ ПОЛИЯЗЫКОВЫХ ТЕКСТОВ

Специальность 05.13.11 - "Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат

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

Москва - 1998

, /

Работа выполнена в Московском эвджетачесхом институте (гсш1П£схои университете)

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

Официальные ошюаешы: Допор тосеговсхих тук профессор Вапш ЕН. Доктор фгаио-шгаоптхих наук, доцсвг Козлов В.Н.

Воущвс прсящшянк Московский государственный горный университет

Зашита состоится .мв^Фа- 1998 года в /^^ттатиятдяссертапионного совета К_053.16.09 в Моаоовасаш эвергагосжом институте (геашчесжон университете) по адресу: 111250, г. Москва, ул. Красноюиармшнаж, д, 17,ауд

С д иссертацией можно ознакомиться в библиотеке МЭИ.

Автореферат разослан _1998 года.

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

к.тл., доцент ^ АЛ.Доротеяко

Общая характеристика работы

Актуальность темы. Одной ил основных задач кибернетики является задача распознавания образов. Интерес к этой проблеме обусловлен супкх'пювапием широкой) кругл jvii/шчных отр;»слей науки и техники, сшишпых с рачбиепием множества объектов па классы и распознаванием кл;юса, которому irpni/цтпый обычег

Задача р.)сгк)знапания ревюстся на некотором множат*' обьект», определенной для конкретной ее иостанонки. В частности, обычегами мосут являп,ся печатные темпы, и более узкой ноггановкг - печатные тексты щх'Д'южеиий на не|«лч))Х)м множестве языков. Ашичэтккииш iiiuvui н ЭВМ текстоных документов nMeei приложение по многих облжчях науки, техники и культуры - при ончлппи банков лчннм.ч, автоматизации проеютцхшания, иоднпшкг издатй и т.д.

Автоматизированный ввод данных с бумажных носителей включает дна :тпша -получение оптического об|хш докумогга, ппдаиемот жх-редстиом некоторого оптической) прибора в компьютерной иамягги, и !юслс/(ующес распознавание оптического образа документа - ссвдшие текстовот фаада, отражающего содержание и структуру документа.

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

Сложность irmpom этана определяется множеством «jwnrn >|*>n, которые должны учитываем'» при сщгшин матсмагичтсот и ii|*>i |vimmh< >т обеспечении соответствующих автоматизированных рабочих мот. Главным из них является |iaiH(»)6|xi)ne тчегжеиий присугпиующих п н:«)б|>ажсшшх документов и возникающих пеледгпше низкою качюти или шрифтовых опЛчнюстей самих документом и вносимых оптическими нрибщьчми. Искажения п|х»1влякш°ы как |хнрмвы и:«)6|Х1Жсиии отдельных символов или как посторонние июиочения, нарушающие их тополошю, и.чн как слипания соссуцшх символов, что возможно также и н неискаженных (>1IIM'ictчеих обцичх (липпуры).

11)мкгичсское применение программных'и аппаратных ([Х'дпн автоматичен« >и> luxvui ачагшвой шк)х>рма|inn н компьютер накладыют- па используемые м них ашорнпчы цгпашанания ш,какие щЛикииы по тчпогш н помехоупончшгхти. 11;ишчие „чаже небольшою количества ошибок способно свели на пег пр'имуиитва 01 испольюпапия такою комплекса ti:»-:ia по Сходимости П|х>|«>дить поуухЛную о|х|х>графичоскую проверку полученного документ. При ;лг>м нсюлирмс тины искажений приводят к ошибкам, которые нситможн» crn«>ppeicrnpoivvn> средствами шггоматичоскш проверки сшггакгиса. При вводе q>'mmmv»,iio чипых и птсишатых документов современные OCR-программы обладают ;ia»ivuu.iMH хар;исгерттика>ш ско|**-щ и точности распознавания. При наличии разрывов или слипаний в изоб^окепиях символов ;гш характеристики значительно уху/шиются.

Предлагаемые в тон работе алгоритмы я первичного рж'пшнавания ф)рмы символа позволяют повысить точтхп imw текстг«*«"! тк}*)рм;и1ии при iimmnpi.rx

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

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

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

Осионныс научные результаты.

•предложены и исследованы методы параметризации оптических образов символов но элементам среднею и внешнего контуров их изображения;

•рар/хгпшы методы назначения и проекций раснашавания символов в условиях нсоп|хлслеппости упорядочения и количества (ирометров распознаваемых (и гшчоских образов.

•докатана устойчивость алгоритмов обучения для распознавания часгично-упорадоченных объектов и получены опенки сложности процесса обучения;

•преуцюжена и реализована в виде инструментального программного комплекса КОНЦСШ1ИЯ сети принятия решений для организации процесса распознавания оптических образов тсксгов.

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

Эгам определяется новизна постановки задачи и прсуугагаемых в работе методов на|>ач('грн:1ации и распознавания изображений нолиялыковых текстов:

-При параметризации допускается неопрсдслешкхлъ упорядочения и количества (|х>рмируемых признаков, а рацыботанные методы назначения и проекций пшволятог принимать ранение с учетом как этой методологической намфедикятосги, гак и «сходной поопредалетюсги объект. Метода галпекетнопо анализа устраняют пиицх-дслетих-гь одццювания иолиязыковых текстов.

-Обтювапо применение припиши усиления эталона дня уменьшения 1г<<11||х'дсло||||огП1 |хчнаюн(сш правила.

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

п:юб|Х1Жсний.

-Показано, что нреудаарителыюе линешюс упорядочение обучающей выборки, согласованное с се естественным частичным упорядочением, обеспечивает усп»1Чивосп> процессов обучения распотипанию.

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

Научная и практическая значимость (м-зуш.татон il|xvni»iceiiiibie метды паргчстрилщии и |»пкхн1л№шш и;тб|*1жсшш iriírnm |>>гшн|»шл аиоршмичикую бшу теории раснозианшшя обраюп.

(VtVHoií ПОДХОД НШНОЛЯСГ HIXVHVM Mtri'li па МОДСЛЫЮМ y|X>IIIIC нозможпсхти комплексного исиольлонання цшичпых мен »дон и приемок шцхннпртиции и.»)6|>ажепии и цхпшпанапня обраюп с последующем (Х'лли.ипиеи и имд|' традиционных или параллельных ii|X)qxwMiii.ix систем.

Ра'1|*/хГ1ТШО шктрумонталыкю lf|X)fp'iMMIKlC обсПК'ЧСНИе Д'|И КСХ'УК'ДОН'ШШ! iioiiiiix меюдои [xk iKviilaiiamui и |>амках ceieinii модели.

Обоснонанность и досгонерность результат«!!, Ре.|улыаты обиснонлны математически и н|х'дстаи1пелы1ыми iaiM(a>i<rifpf k.imk :ikc пери ментами, нодтерждчющимн дигпмгртхт!. оспонпых научных иынодон и пцтильпость ni.if*ijv"! ачтритмичехкои 6,111.1 ргк'итнанашш.

Нне/цк'пие. ИщьУхппиные [цюцхчммы исполкюнаткт. к ДО "!'<х-ц(атил1>" Д'(я aimiMaiitíuutu обработки документации и СНПО "Комета" для «хуцшия макета рабочей) моста озвучивания текстов для слепых но планам Москонского научного центра по культуре и информацж)Ш1Ым технологиям при МГУ, а также при выполнении науч1го-исследогатад1,ской работы в МЭИ. Научные результаты и iipoqxiMMiibto комплексы используются «учебном процессе н МЭИ.

Ащюбация работы. Резулыап.1 работы обсужлдлись па 15-м Междунаро;июм симпозиуме "Лосичоское уиц-ииюпие. IhrmjuiCKiyiviutMC нн(|>ормацнош1ыс технологии и страп-ши" Международной) <(х)рума информатики щи M<Dl I—í)2, Несмирного кошросса ITS-92, на конференциях"Информациони1>1е средстпа и технологии" Меж<|уна|Х)дп1>1Х форумоп информатизации МФИ-4Д МФИ-íM, МФИ-95 Всемирных кошрешнг ITS—fXí, 1TS-94, ITS-ÍA"), Мосюш 1992-9.) r.r., а также на Vil Мелу|уна|хуиюи конфе|Х'Пции "Итсдлектуа'п.пые сипемы", Мсх кна, НЛ7 i.

Структура диссертации. Дисщлания «хтонт из инедепия, ниш гллн, заключения, cuneta литгротурм it содержит Ж сцхшии ичспл, 'i> рисунком, 4 таблицы. Hii6.iiioi|xi(|)iw содержит 78 наименовании.

Содержание работы

lio виедеши обосновывается выбор темы исследовании, ее актуальность, научное и nixucnviecKoe значение. Описывается пруту)*» ))«боты, приводятся 'Х'поинме положения, выносимые на защиту.

В нерпой главе даю П|ху|,ысюрня :вд!'ш и ее оок|х\менное »хтояние. Раесмт)ХЧ]Ы различные аспекты проблемы |>аспозпанапия оптических обраюп шмиязыкопых текстов. Обсуж/ииотся свойства, которыми должны облает» алгоритмы рапншаиапия. Уточняется постановка .Вд1чи диссертации и рассматриваются ншможпые подходы к tv решению.

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

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

Оицх'мпшые <тфс|>1»1 применения систем распознавания iiaic/wvu>in;uOT -жесткие требования 11]хишлы1осги кодироишия таких символов. Как пример могут быть |i,ii'cM(rr|)cniii мм/км годтгели.'клн п|х>|раммпый комплекс или система шнучииапия текста,—В первом случае символы одинаковой формы представляются разными шрифгачи и .зависимости от алфавита (языка), которому принадлюкит фратмягг ичеи'га, а но irmjxiM случае - но рапному учитываются при озвучивании.

Задача |хк.ткхчиаиаиия усложняется и наличием в изображений текстов ри-шмиых искажений, кегторые возникают вследствие нилкопо качества и 1нрифтовых i»ii(V'miii»-u'Ü самих докумпгиш, или шкхятш на :riaii.lx n|xyiii,ipiri<yii>Hoü чГцх/кпш (>1гшч<\ коп>о<>р;ш. TaioiMn исгсокениями являются:

-пс|Х'К1*'ы с'1)хж, которые Moiyr привести к нарушению струюуры выходною документа и к неправильному кодированию прописных и строчных символов;

-различные типы разрьгоов в изображениях символов, имеющих при отсутствии искажении связную топологию;

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

Система распознавания образов текстов должна ренить следующие задачи: •Задачи предварительной обработки изображения.

Фильтрашш призвана обеспечить наилучшие показатели яркости и контрастности изображения, и удалить точечный uiyM.

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

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

•;&Vi;i4a определения характерной тон(Ш>гии образа симкхла. Некоторые с имволы разных алфавитов, цифры и знаки пунктуации могут иметь о.ошакпиую форму в зависимости от используемой комбинации шрифтов. Например в латинском и кириллическом алфавитах символ "А" имеет одинаковое начертание, символы "О", "о" и цифра "О" тоже выглядят одинаково. Аналогич1ия иеодштичность может возникать и вследствие некоторых щхущаритслшгых этапов обработки и:пбражения (сканирование, фильтрация), а гакже из-за способа парчметршзации используемых алгоритмов распознавания. Именно поэтому ие1П]1алы юй задачей распознавания текстов является распознавание характерной топологии (шейпа) образа симихта. •Задай постобработки.

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

б

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

Во trmpoii глшх- рассматриваются математические модели обраюв символов, методы ппрамстрилтции, мего.чы первичною и точного аиали.ча формы символов, проблема слипшихся симмшм.

Наличие символов, которые имеют лить тонкие, локальные различия в своих ха|тактерных toikvioiwix ("Л" и "Э", "h" и "IV', "П" и "Л", "О" и "Q" и др.) обуслалливжт нолешопь ведения отношения тш1е|>'игпкхти ма множит*;' нкчмюв — тчерантными являются meüni>i похожих символов, различия юпорых moivv иече:*пь при игклжешшх.

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

Таким обратом задача распознала! шя икйиа сподится к задаче он редело вед класса толерантности и далее к задаче о многоэтапном внутриклассовом доуточнении. На первом этапе с использованием быстр!,ix, устойчивых и легко обучаемых алгоритмов осуществляется распознавание с точностью до класса толерантности, а на ято|*)м с иегюлкювшшем чуосп»ггелыгых к деталям алгорттчои п^ж.ит/иггея равнение внутри класса.

Классы толеранпкхти формируются в процессе вычислительного эксперимента и анапт типичных ошибок распознавания. Для каждой пары мюипов о;икнх» класса толера) mкхли должны 6i>m> описаны локальные топологические (ххУхчпкхти, которые различают эти шейпы. К.чк правило эти оеобешкхлп могут бьт> выявлены при качественном и кшшчоепхчшом ;шачи:>е впешнет контура и:х>6р;1жения символа.

В |vrfícrir иосжукнш! ряд алтритмон параметризации и распознавания пкч'ша. Как наиболее подходящие дня этот» важнеинкто этапа предлагаются метод назначений па первичном и метод нргх'кции па уточняющем этапах

Модель па ik'ikiik' среднего контура. Метод назначении. Метод намичепий основан |и использовании структурной модели изображения символа как ои|Х'делс1Шым обратом связанных фрагментов. Для определения основных характеристик фрагментов используется cpcvunu'i контур изображения. Принцип действия исчюлы^емого н работе ачторитма "стенной огонь" схож с получением иестцк-мот каркаса нек<т>]х>й конструкции псхую сжипшия внешней) слоя. В реш.чыате получается скелет, отмокающий струкчуру символа, а тшоке сле.чуювше хлциагрпстики фрасмешои - относительные (ххтмеры и коор/цшаты х.'цмктсрных точек фрагааггов (начало, конец и др.), нлошддь описанного нрямоугольншеа, длина и тип линии. Модсш» символа подставляет совокупность описаний соспшляюших фратмаггов и описание их связности.

Мсчод предполагает использование и качестве эталонов максимально упрощенных струюурных моделей символов. Для уменьшения ие|х>ятпости отказа от

ртпознанания и улучшения обучаемости вюдится эффект "размытия" путем внесения Л(*'гат»чно широких интервалов изменения количественных характеристик.

Распознавание осуществляется на основе установления меры соответствия между входной и эталонными моделями. В условиях искажений возможны нарушения упорядочения, связности, характера и количества фрагментов распознаваемого изображения. Тогда для установления соответствия между фрагментов распознаваемой и шаблонной модели применяется классическая палача о назначении. Ранение этой .tíVti'iii является та подстановка фрагментов обраэда и шаблона, при которой тапк'итмие меж;1у ними наилучшее. Исхоуцп.к; данные при атом образуются по кп.'шчегглгпным хар-илгрнстпкам моделей.

Пусть И'(и,у) - матрица размера AfxM, где М, JV- количество фрагаептов днух mo;i(vi<-¡¡, ASA/, оостяшсй из вековых кгоффиниентов w^ характеризующих степень |кш1ичия ха]х1кгеристик /—ix) фрагмапа нервоп) и j~го фршжчгта второго изображения. При этом для эта/или могут быть выбраны носовые коэффициенты, определяющие степень участия числовых характеристик его фрагментов в формировании матрицы IV, то ость меру соответствия элементам неизвестного июбражения в зависимости от их числовых и качественных характеристик. Сумма

íV /-i

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

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

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

Наиболее успению алгоритм распознает искаженные изображения, «)держащие разрывы двух ти1юв*.

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

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

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

к

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

Для того, чтобы обеспечить устойчивую (чабту н н условиях разрывов :mni катетрии разработана модификация, при которой происходит искусстпепнос дробление ф|хи"мсптов эталона. Таким образом </>р;>боп<а этого класса разрывов сводится к обрабоп<с искажений второго класса. Дробление осутеспишстся без нарупюнии связей фрагментов эталона. Степень дробления оп|х-деляст точность нашачений.

Основным преимуществом описанного подхода к <|х>рмиро!ешию и использованию эталонов янлястся сю информатишкхть, кото/мя д<х.тшастся за счет предложенною метода структурного описания модели изображения символа. Алгоритмы распознавшим при этом облапают хорошей обучаемостью, эффективно обеспечивая (ксышение базы эталонов. Они устойчивы в условиях типичных разрывов и точечных шумов. Недостатком метода является метшкающш потеря точности иэ-яа использования алгоритмов выделения среднего контура. В результате образуются некоторые классы толерантных символов, для которых необходимо проводить доугочняюпшй анализ. OrcW/ia п'ьгтсйкт возможность использования алгоритмов этого подхода только на первичном ."mine раеншнававия шсйнов.

Основным недостатком алгоритмов является переборный хацистор задачи о назначении. В случаях когда структура симтла включает бол1>нюе число крупных фрагментов вычислительные ;taT(Xi'rw сильно itKipacraior. На практике эта проблема решается с использованием |»yia :>вристичсских правил, которые выявляют заведомо недопустимые подстановки фци ментов.

Метод н|х)скций. Подход бамрупся на аналше (х-обешкх-ий внешнего кошу|>а и:шб|);ш'нпя. В распоп ктж'мом уч;ктке образа выделяется система пложенных прямоут.ibiii.ix ф|>агмсшов, |*1сширнк>щихси в одном из чпы|х:х иамщилспий. Фрагменты ха|хисггри:гуит-.я щхх-кциями по выбранному 1иш|хшлснию. Динамик;» изменения щххчеций стихчствует степени вы]Х1Жсмн(кти тополотчсской (х'обеншх.ти и оц( 'ниимчся рядом количественных характеристик.

Па основе подобных иа|)амстров можно анализировать более сложные топологические особсшюсти, н;и1римср стене:и> симмет|)ичп0сги и:*)бражеиия, сепень наклона кривых, глубину выемок и др. Получаемые количеспхчшые характеристики Moiyr исполыовапся при перемещении но сети принятия ренкчшй. На их основе может «хущеепшяпюя огтоброжспис дискретного объекта и метрическое пространство, nixvie чего имможпо нрнмгнепие классичаких методов р;к°ншнав;шия. К|х>мс топ» появляйся 1*1!М()Ж1Кхть оценки степени Iit-oiijxvicviciин*ти |X':iy.'iiiiani ралкмпавания.

При таком подходе модель и.зоб|Х1Жсния представляет гобои совокупность качехтвенных и количественных параметров, харастеризую!них топологическую особенность заданного участка импура. Она формируется функцией-программой вычисления этих параметров на основе ряда базовых функций.

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

И(Г К1Ш|>Н1-П«'1||||>К' ||а|К1МГГрЫ IXipMIIJMMGUIbl, 'ГП> обоСИеЧЩШТ IICIiUUH°HM(Xrn> ОТ

горизонтальных и вертикальных размеров изображения. Возможность конструироишия деревьев принятия ранений обеспечивает гибкость описания (хибешкхггей ф|хи M(.:irtt>u и устойчивую jxifxny в условиях разных шрифтов. Недостатком является сложность конституирования дераи принятия решении о выявлении (хи/хишхтгй нмкшиии. Мсюд ii|xx.'Ki(iiii удобен для ил юлкюнаннл на вп)ричиых этапах определения шейна символа.

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

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

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

Алгоритм обучения с использованием "размытых" образов элементов обучающей выборки описывается следующим образом:

1. Образовать список ЬЛ из M (по числу классов объектов) пар (<помср класса>, 11) где 1J- пустые а теки размытых образов;

2. Для o4qxyuiora элемента входной последовательности (л, К;д) найти в списке Lj\ первый элемент (Л L") такой, что список L' «¡держит элемент ;/', ¿i'<Jt,

Принять v^T, если указанный элемент существует, шшче значение г считается неопределенным.

3. Если значение v определено и v*Ka), найти в списке La элемент (/(а), /.);

ю

если в списке Ь нет элемента ¿¿'<л, то включить элемент получаемый "размьпием" элемента а в этот список, исключить из послсдпен) элементы и

повторить пункты 2, 3, иначе переставить в списке Ьл элемент (Да), и па место, пре/ипестпующсс элементу Оз", /.");

если же значение V оказалось неопределенным, то найти в списке 1. \ злемент (А;!), О и включит!) элемента в этот спиаж.

11)*>|«),ипся сравнение алюр|ГГМои, испольтующих мстричссчсие счюйства обсчетов с алгоритмами раснашатния ч,-*тично-у|юрядочениых обычегов с цел!>ю выявления сходства с|*)йсгв разных моделей, келорые определяют в известном ш>ое результативн(х.ть процессов обучения.

Характерные особенности метрического подхода показываются на приме)*' персенгронного подхода. Приводится алгоритм обучения иеротттропа, в результате работы которого строится решающее правило распознанания — разделяющая гиперплоскость. Сходимость обучающего алгоритма докатана американским математиком А. Новиков!,1М. Он показал, что в случае обучения распознаванию л и пей ш )~ра:у 1,ел им ых объектов число коррекции решающего правила ограничено сверху.

Альтернативой методическою подхода является модель ¡хшшпавания частачно-уно()ядочеп1(|»1х объектов. В качеспх.' решающего правила алгоритмы обучения формируют спиаж, включающий некоторые обкчеты из обучающей выборки, <<»н|»<|«1)к/|,и'М1,к' н<тот)|х1Й 1111(|»)рмлкн<'Н, патишюпк'И (Н^х'.чг.лгп, их клкгы, а пиокс (по сопоставлению со всеми элементами списка) - класс лк>бот п|х'Д1 .являемого для распознавания обчлкта. По существу, такие решающие пришла [цх-дставлягот собой сжатые п|х'дст;шлепия обучающей информации, при :гтом сжатие и нгкгтиновление дшных ехчювано па схюбеп костях отношения частичного поряд)<я на множестве обшстов из обучающей выборки.

( '¡хитиичктя /дач по/1хода к построению алгоритмов обучения - с накоплением и с забыванием. Алгоритмы с отоплением пречнолапиот предварителыкх! накоплитс и упорядочение обучающей выборки и являются устойчивыми. Алгортмы с забыванием не требуют наличия всей обучающей выборки и допускают предъявление обучающих элементов п произвольном порядке. Ценой за отсутствие "буфера" обучшощей псхх'ВДоватслыкхти является необхо/щмехть неоднократных повторений ос элементов и вследствие :т»(т> увеличение ее длины и числа необходимых изменений обучающего навила. Алгоритмы с забыванием эквивалентны ;и!п>ритмам с накоплением но результату рабетты и в этом смысле они устойчивы.

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

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

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

Алтритм обучения А с забыванием называется устойчивым, если после обработки конечного числа квазипериодов он формирует устойчивый список Ьд. Последний, В1>шолняя роль решающего правила, позволяет восстанавливать значаше

для любого элемента аеК.

У|х)веш> К^ частично упорядоченного множеспи К образуется его минимальными элементами, уровень К,- - минимальными элементами его подмножества, не содержащего элемента» урошюй К'¡, /</.

Порядком р частично упорядоченного множества назовем наибольшее число р, такое, что

Теорема 1. Существует обучающая последовательность длины [Л[, по которой любой алгоритм обучения с забыванием формирует устойчивый список Ьд.

Теорема 2. Список Ьд, формируемый данным алгоритмом с забыванием, единственен и получается при обработке любой обучающей последовательности, содержащей не более />И квазипериадов, где р - норядеж частичио-унорндоченното мж)жесгва.

Получети верхняя оценка числа изменений решающего правила при обучении 1*кткинлна1шю ч.-гтично-упорялрченнь1Х объектов с забыванием:

Теорема 3. Пусть К - частично упорядоченное множество. Тогда число 1С1МС1КЩИЙ нашила принятия решений при (¿учении с ¡ыбыванием меньше величины 2)4 Верхняя оценка достигается в случае когда частичный порядок на К будет линейным н»|»|;иа>м, а обучающая нех'лсдогспелмкхть будст имен. рекуррентную структуру вида:

где (- частичная переключательная функция, соответствующая обучающей выборки, ¡У)- единственный в дашюм случае наименьший элемент множества К, и » - операция конкатенации с совмещением общего конца и начала Iю;июслсуктачелыкхлей.

Теорема 4. Число изменений правила принятия решений при обучении с :ыбын.'ишем раиккшаванию элементов бинарной булевой сгруюуры {0, 1>" меньше величины 2"н/?1. Верхняя оценка достигается в случае когда бинарная булева структура будет иметь рекуррентную структуру вида:

йх.х...... ,х)*йх,1.....х)»йх,х.....1)*((0.....0),(Л0, ..., О.....х)*

*йх,1.....х)*йх,х,..,1>-

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

12

уио|>ядочс1ШЫх обычсгов наблюдается аналог гсо|х\\1ы Новикова о суикгтпованин верхней 11vи11titi>i числа 1«>р|хч<цпи |м■■ iuiioii(t'lж> пошила.

Покачано, что ггри обеспечении накопления и iKxviq/iytowm тпилотчетло упорядочстгя элементов обучающей выборки гарантируется свершение П|*>ц<хга обучения Hix'jie об^Лики шхледпего злемеичл. (>1мсч;ичгм, чв> сунм'птилиие критерия окон'ишия щхщеаа «тбучеиии, например, по miчпду мниими:чции qxyuteil квадратичной ошибки Хо и Кашьяна и метрической нории цлспшнавапия гаюке обусловлено использованием при юокдой итерации всех обычетов обучающей выборю).

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

I) связи с :ним возникает П|х>блсма цхшщхчшя 11|х'д<чатпичыккч1| ючждого эталона, дчя чего и используется описанный в н|х'ды'1ущсй главе прием "рачмытия" ;гг,июп<т. ¡^кхжпритх'пл один из способов ее (хчнеппя в jxiMivix кпмбипаторио-лотичсского подхода к распознаванию с использованием частичной) и линейного порядка.

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

Результат первичного распознавания шейной представляется в виде некоторого ciщека из кодов тейпов, кшрдипат соответствующих им и.зобр;1жепин символов ix> входном документе и оценки noipeimiocni распознавания. Для кодирования результатов вторичного рвюпазн.чвштя тейпов используется двухбш"гп1ая система кодирования UNICODE, которая признана обеспечить алфавитную универсальность в условиях глобализации информациошп.к систем.

Как правило порядок кластеризации изображений отдельных символов не соответствует илизиеипому (ылюложению символов в слонах и строках. Учет контекстной ин<|х>рм;1ции ншполяет /рхтаточно точно отследить струюуру документа и разречпип) ноо;июзначп(хти пюйпон прописных и строчных символов, а также при . некоторых oi-рапичениях даст возможность правильно различать схожие шейпы символов разных алфавитов. Для этой цели вводится ряд отпомюшш на множестве символов.

Для разрешения инутриалфтитных нгоднтнашкхтей шпчятся отношения: -дуалыкхги. Дуальные считаются те пары сим1*>лов о/и ют алфшятга, которые имекл о.линаковью шейпы в своем строчном и прописном варианте;

-ipvniia упарньгх отношений, которые определяют тип символа - iuu|>[i;i, зшж нункчушиш, диамарк, строчные и прописные символы.

Для разрешения межалфавитных неоднозначностей вводятся отношения: -¡жвивалентности. Отдельно взятый класс эквивалентных символов содержит ixie символы разных алфавитов, у которых неразличимые вюйпы;

-ipynna (тпюнкний, перечисляющие состав алфавитов, которые П1ху1усмоггрены для ivicnoai ииания.

1.1

Межалфавитныс неоджхшачжкто мгауг бьггь разрешены только при наличии ш-шлорых допущений ort исхо;июм текпе, стример Т|х<х>ли|ис о том, 'flu слово «уцержит только символы о;икмх» апфавта. Однако это требование не поможет разрешить случай когда слово или предложение не содержит уникальных символов он i xv глеи hoi о алфшита. В этом случае /цстся предупреждение о мшожной нсп;1позначн<хти код|1|*>нашш.

Для выявления структуры документа вводятся функции:

-лин у|х)нпей верхней и нижней границы символа но (лиотению к всх)бражаемой линии уровня строки;

-общепринятые горизонтальные и вертикалышк пропорции символов.

Таким об|>а;»)М каждый ачемент (ыспшнаваемых ал<]1авиюв может бьггь опиат вышеперечисленными отношениями и функциями в некоторой информационной базе IV1Я контскспюй обработки. Для повышения точности распознавания можно ввести большое число дополнительных отношений и функций и таким образом совершенствовать базу. Признаками, которые могут быть отражены, могут быть, например:

-количество связных областей символов;

-пространственное наложение составляющих частей символов;

-характерные шрифтовые особенности символов, например наиболее вероятные моста слипания символа в зависимости or сю соседей;

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

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

Выводы

1. На основе анализа особа пкхлей распознавания оптических образов нолиязыковых текстов при наличии искажений сформулированы ■ тробовштя к современным OCR-системам:

- устойчивость к искажениям оптических образов;

- адекватность структурирования документа;

- правильное кодирование символов одинаковой формы.

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

14

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

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

4. Разработан ряд алгоритмов для первичнот и уточняющега эталон распознавания тонолошческой ф>рмы онтичн кого образа символа, (хлюианных на различных еп> математических моделях, отражающих особенности как сродней линии, так и внешнего контура, и учитывающие частичную упорядоченность изображений, а также неопределенность упорядочения и количества их параметров. На основе компьютерных экспериментов с использованием различных методов р; опознавания выбраны i«u< обеспечивающие уггойчшххть к искажениям определенного iciitera предложенные для этих целей метод назначения и метод проекций. При глом обоснован принцип сочетания методов распознавания, основанных 1И использовании упорядочения и метрического подхода, а также четкости и рамытости при принятии решения.

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

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

7. Введен ряд отношений на мтжостве символов, используемых при контекстном ;ш;1ли.эе результатов распознавания формы симкхча. Г1|ку|дожспы алгоритмы ;уш отслеживания структуры документа, а т.жже для оп}х;делеиия алфпнитнои принадлежности пкйна.

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

Публикации автора по теме диссертации

1. Фролов А.В., Фролов Д.А., Четр;»филов И. Д. Распознавание в интеллектуальных системах функционального типа. / / Htпглдсктуалып>к системы. Т. 2. Выи. 1-4. 1997, С. 201-216.

2. Фролов А.Б., Чеграфшюн И.Д. О некоторых подходах к распознаванию оптических образов текстов. // Интеллектуальные системы. Т. 2. Вып. 1-4. 1997, С. 189-200.

3. Фролов А.Б., Четрафилов И.Д. Сети принятия ранений для распознавания оптических образов при наличии искажений. // Вестник МЭИ. N:6, 1997.

4. Фролов А.Б., Савельев В.Е., Фролов Д.А., Четрафилов И.Д. Адаптивные информационные технологии распознавания в САПР и техническом диагностировании. // Тез. докл. Всемирный конгресс ITS-92. Международный форум информатизации МФИ-92. Москва, 1992, С. 11-12.

5. Фролов А.Б., Фролов Д.А., Хомяков П.Б., Четрафилов И.Д. SLANG -про1раммный комплекс автоматизации проектирования OCR-технологии. // Тез. докл. Всемирный кошрсос ITS-Ш. Международный форум информатизации МФИ-М. Молам, 1«Д С. 29-30.

6. Фролов А.Б., Фролов Д.А., Хомяков П.Б., Четрафилов И.Д. Распознавание оптических образов тюлиязыковых текстов. // Тез. докл. Всемирный конгресс ITS-94. Между1 иродньш форум информатизшщи МФИ-94. Москва, 1994.

7. Четрафилов И.Д. Обьектно-орие1пирова1шый подход при распознавании документом. // Тез. докл. Всемирный конгресс ITS-95. Между!iapo/р£ый форум информатизации МФИ-05. Москва, 1995, С. 184—185.

Печ. л. Тираж /QQ_Заказ

Типография М.ЭИ, Краешжазармеиная, 13