OCR изнутри, или как устроена «распознавалка»

Свой опыт

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

При подготовке этой «темы» я с большим удовольствием перелистал несколько книг, изданных в 60-70-е годы и посвященных «будущему кибернетики». Среди чудесных дискуссий о роботах, искусственном интеллекте, «воспроизводстве» киберов и даже «электронной модели капиталистической системы» обнаружились не менее жаркие споры о распознавании образов; во многом эти споры достаточно актуальны и сегодня.

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

Итак, вроде бы все просто. Прекрасная модель перед нами, вернее — в нас самих. Обычный человек, не «кибернетик» и не «философ», вероятно, вполне внятно может описать действия центральной нервной системы при распознавании образов. Этому обучает чуть ли не школьный курс биологии.

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

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

И все же большинство подобных примеров в действительности трудно отнести к «распознаванию образов» c большой буквы.

Лучше всего идею «настоящего» и «ненастоящего» искусственного интеллекта с прицелом на рассматриваемую проблему демонстрирует, на мой взгляд, один из сюжетов Станислава Лема («У роботов — свои притчи»).

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

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

И началось соревнование… Трурль перепрограммировал своего умного робота для других фабрик, но этот робот оказался очень дорогим. Тем временем его оппонент придумывал, на первый взгляд, примитивные и лишенные «интеллекта» системы, используя для решения разных задач то эффект трения, то (при большой номенклатуре деталей) радиоактивные метки, позволявшие с тем же успехом, что и при использовании «умного» робота, но гораздо дешевле, добиваться аналогичных результатов.

Формально (если учесть, что непоэтические сетки на конвейере так же, как и робот, сортировали детали) и то и другое техническое решение занимались «распознаванием». С точки зрения практики конструирования механизмов, чем надежнее и проще механизм, тем лучше!

И все-таки в глубине души мы понимаем, что «распознаванием» занимался именно робот. Решение этого ребуса оставим философам. Для нас интереснее другое.

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

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

Результат будет один и тот же, только во втором случае мы, надо думать, получим определенный выигрыш и ощутим вкус прогресса. Вкус для человека жизненно необходимый. Не стоит абсолютизировать и логические распознающие системы, хотя лучших пока, кажется, нет. Мы с вами падаем, ломаем руки, наносим себе раны ножами несмотря на «знания», «опыт» и т. п. А согласно истории, приведенной Рудольфом Баландиным в книге «Распознавание в природе и природа распознавания», на одном из конгрессов по распознаванию образов ученые мужи не узнали (не распознали, хочется добавить) в толпе прилетевшего коллегу, которого встречали. И потому, что тот помогал даме с ребенком и катил коляску, в то время как его ожидали «одного». Шутки шутками, но речь-то идет об отделении ценной информации от шума!

 

Механическая машинистка
Николай Никольский, сотрудник компании Cognitive Technologies, рассказал мне как-то еще один крайне показательный анекдот. На презентации компания должна была показывать новые модели сканеров, кажется, от НР и работу сними системы Cunei Form. И, чтобы не было скучно, решили пошутить. За пару дней до события одного из коллег нарядили во фрак и сфотографировали, затем фотографию отсканировали, а графический файл сохранили. На презентации, рассказывая о потрясающих возможностях сканера, Никольский без тени улыбки пригласил коллегу во фраке на сцену, предложил «подсадной утке» подойти к сканеру поближе и включил его на считывание при открытой крышке. Ассистент тем временем аккуратненько открыл в графическом редакторе заранее сделанную картинку и предъявил публике. Но ожидаемой реакции зала не последовало. На недоуменный вопрос устроителей презентации: «Ну как?», из зала прозвучало уж совсем неожиданное: «А что вы гордитесь, давно надо было так сделать»!

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

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

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

В этом раунде обмена технологическими аргументами играют, как вы уже догадались, наши старые знакомые — Cognitive Technologies и Bit Software. Достаточно взять подшивку «Компьютерры», чтобы вспомнить споры о качестве новых версий, судебные разбирательства, а также различные маркетинговые ходы.

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

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

Сегодня оба игрока демонстрируют завидную настойчивость в подписании ОЕМ-контрактов (как правило, с производителями сканеров) и в заключении контрактов с крупными госструктурами. Довольно долго обсуждался любопытный ход Cognitive Technologies в сторону АS/400. Ну, да не об этом сегодня речь.

Кстати, я познакомился с OCR года полтора назад. С одной стороны, у нас в редакции никогда не держали машинисток, прекрасно понимая, чем такие эксперименты заканчиваются, с другой — необходимо было работать с факсами компаний для рубрики «News in Brief». И, наконец, вводить всю эту красоту руками было лень. Результаты были, разумеется, разными, и иногда исправление ошибок занимало примерно то же время, которое ушло бы на ручной ввод. Но так было интереснее.

На самом деле OCR здорово выручают в случае с массовым, поточным вводом и распознаванием текстов. Это касается проектов наподобие Национальной службы новостей, всякого рода анкетирований, голосований, формирования электронных копий библиотек, архивов и музейных коллекций. Тем более что благодаря активной деятельности производителей принтеров, факсов и копиров «безбумажная информатика», о которой мы мечтали вслед за Глушковым, пока так и не расцвела. Мы, кажется, производим все больше бумажных документов несмотря на разные системы управления деловыми процессами и «электронные офисы». А Россия уж точно еще надолго останется хорошим рынком для систем OCR.

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

Системы OCR уже овладели секретами сегментации текстов, отделения картинок от основного документа, работают с таблицами, визитками и даже с рукописью, правда, стандартизованной, «рукопечатной». Иными словами, писать вы должны точно так, как если бы писали почтовый индекс на конверте. Так что «распознавалки» становятся, как принято говорить, «все более интеллектуальными». Не говоря о том, что практически те же технологии могут быть перенесены в сферу распознавания, например, речи.

При этом, как говорил Гете: «Мир видит каждый в облике ином, И каждый прав, — так много смысла в нем». Будущее систем оптического распознавания символов их разработчики видят по-разному. По-разному они подошли и к написанию статей. Но это их право. Мы предоставили компаниям возможность в равных объемах рассказать об устройстве, развитии своих систем все, что они сочли нужным; статьи расположены в алфавитном порядке: сначала «Бит», затем Cognitive. Слово за ними. А на десерт будет независимый эксперт… в маске.

 

Внутри черного ящика

О технологии распознавания символов рассказывают разработчики системы FineReader.
Казалось бы, все просто
Как же все это работает?
Распознаем символы
Секреты
Заключение

Шаблонные системы

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

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

Структурные системы

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

Структурными элементами являются составляющие символ линии. Так, для буквы «р» — это вертикальный отрезок и дуга.

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

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

Признаковые системы

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

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

Казалось бы, все просто

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

Итак, всем нам ясно, что распознавание текста состоит «всего навсего» в преобразовании изображения страницы в текст. Только вот добиться этого, оказывается, не так просто.

Компанией «Бит» была разработана специальная технология распознавания символов, которая получила название «фонтанного преобразования», а на ее основе — коммерческий продукт, получивший высокую оценку как специалистов, так и пользователей. Это система оптического распознавания FineReader. Сегодня на рынке представлена уже третья версия продукта, которая работает не только с текстом, но и с формами, таблицами, а разработчики уже колдуют над новой, четвертой версией FineReader, которая будет распознавать не только печатный, но и рукописный текст.

Как же все это работает?

Основные принципы, или целостность восприятия

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

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

После того как выдвинуто предположение о воспринимаемом объекте, выделяются и интерпретируются его части. Затем предпринимается попытка «собрать», «воссоздать» из них целое, чтобы проверить правильность исходной гипотезы. Разумеется, воспринимаемый объект может интерпретироваться в рамках более крупного целого.

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

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

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

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

Существует два вида целостного описания: шаблонное и структурное.

В первом случае описание представляет собой изображение в растровом или векторном представлении, и задан класс преобразований (например, поворот, масштабирование и пр.).

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

Конечно, шаблонное описание проще в реализации, чем структурное.

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

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

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

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

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

Распознаём символы

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

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

Шаблонные системы

Структурные системы

Признаковые системы

Секреты.

Структурно пятенный эталон

Фонтанное преобразование совмещает в себе достоинства шаблонной и структурной систем и, по нашему мнению, позволяет избежать недостатков, присущих каждой из них по отдельности. В основе этой технологии лежит использование структурно-пятенного эталона. Он позволяет представить изображения в виде набора пятен, связанных между собой n-арными отношениями, задающими структуру символа. Эти отношения (то есть расположение пятен друг относительно друга) образуют структурные элементы, составляющие символ. Так, например, отрезок — это один тип n-арных отношений между пятнами, эллипс — другой, дуга — третий. Другие отношения задают пространственное расположение образующих символ элементов.

В эталоне задаются:

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

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

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

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

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

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

Заключение

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

Слово «фонтанный» происходит от английского слова font, что значит шрифт.

Базой называют совокупность шаблонов, используемых в системе.

Достаточным условием целостности описания является отображаемость описания.

Элементы, которые, будучи выделены на изображении, запрещают отнести его к данному классу.

Уроки машинного чтения от Cognitive Technologies
Задача распознавания слитного текста значительно сложнее задач распознавания отдельных символов лов. Ее решение в нашей системе основано на взаимодействии структурного, признакового, растровой дифференциального и лингвистического уровней. Но из-за ограниченности объема статьи основное внимание мы уделили главному структурному уровню.

Долгое время для многих пользователей компания СодпШуе Technologies ассоциировалась лишь с разработками систем оптического распознавания текстов. Но в последнее время нам удалось значительно расширить спектр применения OCR и разработать новые, отвечающие требованиям рынка продукты и технологии. Однако сегодня нас интересуют именно системы OCR их устройство и принципы функционирования. А начнем мы с самого простого случая распознавания — «гладких» текстов.

«Гладкие» тексты

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

Работает система по принципу «одной кнопки». Это означает, что при нажатии кнопки «Сканируй и Распознавай» запускается весь процесс обработки документа: сканирование, фрагментация страницы на текстовые и графические блоки, распознавание текста, проверка орфографии и формирование выходного файла. Но что за всем этим стоит?

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

Заглянем внутрь системы CuneiForm ’96 (или OCR-системы MacTiger для Macintosh) и посмотрим, каким же образом ей удается «понимать» текст.

За распознавание текста отвечает целый ряд модулей (сканирование, выбор яркости, предобработка документа, фрагментация и др.), каждый из которых решает свою задачу. Интереснее всего для нас сегодня, разумеется, модуль распознавания. На вход модуля поступает полученное после сканирования изображение. Теперь необходимо сопоставить каждому элементу изображения символ АSCII-таблицы (то есть получить собственно текст, готовый для редактирования).

В CuneiForm используется несколько методов подобного сопоставления. Во-первых, образ каждого символа раскладывается на отдельные элементы — события. К примеру, событием является фрагмент от одной линии пересечения до другой. Совокупность событий представляет собой компактное описание символа. Другие методы основаны на соотношении «масс» отдельных элементов символов и описании их характерных признаков (закругления, прямые, углы и т.д.). По каждому из этих описаний существуют базы данных, в которых находятся соответствующие эталоны. Поступающий на обработку элемент изображения сравнивается с эталоном. А затем на основании этого сравнения решающая функция выносит вердикт о соответствии изображения конкретному символу.

Кроме того, существуют алгоритмы, которые позволяют работать с текстами низкого качества. Так, для разрезания «склеенных» символов существует метод оценки оптимальных разбиений (наши ноу-хау — технологии FustCut и PowerCut). И напротив, для соединения «рассыпанных» элементов разработан механизм их соединения.

В CuneiForm ’96 мы впервые применили алгоритмы самообучения (или адаптивного распознавания). Принцип их работы состоит в следующем. В каждом тексте присутствуют четко и нечетко пропечатанные символы. Если после того как система распознала текст (как это делает обычная система, например предыдущая версия OCR CuneiForm 2.95), выясняется, что точность оказалась ниже пороговой, производится дораспознавание текста на основе шрифта, который генерируется системой по хорошо пропечатанным символам. Здесь разработчики соединили достоинства двух типов систем распознавания: омни- и мультишрифтовые. Напомним, что первые позволяют распознавать любые шрифты без дополнительного обучения, вторые же более устойчивы при распознавании низкокачественных текстов. Результаты применения CuneiForm ’96 показали, что использование самообучающихся алгоритмов позволяет поднять точность распознавания низкокачественных текстов в четыре-пять раз! Но главное, пожалуй, в том, что самообучающиеся системы обладают гораздо большим потенциалом повышения точности распознавания.

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

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

Распознавание символов по их графическому представлению – одна из самых старых и традиционных задач искусственного интеллекта. Еще в 60—70-е годы были написаны десятки диссертаций и предложены сотни методов решения этой проблемы. Достаточно сказать, что изданная в 1969 году в Киеве библиография работ по OCR включала 245 названий! Любопытно также, что один из первых методов распознавания символов, предложенный американским ученым К. Фу, был именно структурным. В то же время методы распознавания, основанные на изучении набора признаков, были и остаются очень популярными.

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

Главным недостатком распознавания по признакам является его незащищенность от образований, вообще не являющихся буквами, — почему бы им не иметь присущих буквам признаков? А такое часто случается. В результате чего «склейка» из нескольких букв разрезается неудачно. Все методы имеют недостатки, и, разумеется, лучше применять их комбинации. Теоретически это просто. Однако только в конце восьмидесятых годов, когда сканеры и компьютеры стали широко доступны, были созданы программы, позволяющие подойти к этой задаче практически.

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

С этой точки зрения можно только приветствовать появление новых методов, таких как «фонтанное преобразование» или «метод распределения масс». Но главное — довести разработку до конечного результата — работающего программного продукта.В этом, мне кажется, СодпШуе Technologies и ВН Зо^аге преуспел и.

Хочется особо отметить реализацию в системе CuneiForm адаптивных или самообучающихся алгоритмов — давней мечты разработчиков систем OCR.

Идея эта настолько стара и очевидна, что трудно назвать ее автора. Давайте разобьем все множество букв текста (например, страницы) на группы. Математики называют их кластерами. В одну группу отнесем символы, «похожие» друг на друга. Вообще говоря, мы получим столько кластеров, сколько букв разных начертаний имеется в тексте. Теперь можно распознавать уже не отдельные буквы, а целые группы. Разумеется, сделать это значительно проще. Мы, например, гарантированы от рассмотрения случайных образований, каждый признак может быть проверен на многих буквах и т. д. К тому же, распознав кластер, мы распознаем сразу много букв.

В принципе, можно осуществлять распознавание таким способом, даже не зная начертаний букв, подобно тому, как расшифровывают письмена неизвестных языков. Все это так, но на пути самообучения стоит столько препятствий, что пробиться через них совсем не просто. И понятие «похожести» очень трудно определить, и что делать с кластерами, содержащими один символ, неизвестно, да и сравнивать все встретившиеся буквы друг с другом очень долго. По-видимому, авторы CuneiForm преодолели эти трудности, опираясь на уже имеющееся вполне приличное распознавание.
Системы распознавания стали интеллектуальными. Стоит обратить внимание и на то, что интеллектуальная сторона программ не ограничивается распознаванием только текста: развиваются направления распознавания визитных карточек, ценных бумаг, таблиц, стандарты форм. Каждая из этих программу требует решения целого класса задач. Но главное, разработчики не забывают об основной задаче таких систем. Речь идет о вводе информации в базы данных и другие системы хранения и поиска информации. Действительно, распознавание редко бывает необходимо по себе. Распознанный текст необходимо сразу же поместить в среду, где его можно будет легко найти, извлечь содержательную формацию, обработать и т. п. По этому представление программа распознавания в комплексе с программой-архивом выглядит перспективным, целостным подходом к решению проблемы обработки документов.

 

Добавить комментарий

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.