РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ
Контрольная работа
по предмету «Информатика»
на тему: «Этапы развития и сравнительный анализпрограмм оптического распознавания »
СтуденткаИльина О.О.
Тольятти, 2010
Введение
оптическое распознавание коррекция ошибка
Приработе с первоисточниками (или, как принято говорить при описании офисныхтехнологий, с исходными документами) наиболее оптимальным может оказаться вводкакой-либо первичной текстовой информации без помощи клавиатуры. Такой способможет быть реализован получением данных из глобальных или локальныхкомпьютерных сетей, посредством распознавания речи или оптическогораспознавания текста. В данной статье пойдет речь о последнем из названныхспособов.
Имеятекст, напечатанный в типографии, на пишущей машинке, на принтере,копировальном аппарате, в факс-машине, то есть буквально текст любогопроисхождения, теперь — даже написанным от руки, Вы можете без помощиклавиатуры получить его в электронном виде для последующего редактирования,перевода или хранения на компьютере. Для этого Вам потребуются сканер ипрограмма, называемая системой оптического распознавания — OCR. Каждый такойпрограммный продукт имеет простейший автоматический режим «сканируй ираспознавай», реализованный с помощью одной кнопки. Однако для того, чтобыдостигнуть лучших из возможных для данной системы результатов, желательно (анередко и обязательно) предварительно заниматься «ручной» настройкойсистемы распознавания на конкретный вид текста, а точнее на способ и качествоначертаний букв и других знаков. Чтобы проделывать такие настройки, в менюпрограмм обязательно отражены соответствующие регуляторы, но пользоваться имиудобнее при некотором знакомстве с принципами оптического распознавания.
Какработает система оптического распознавания
Фактически,когда Вы читаете (например книгу), то не представляете, какую работу делает Вашмозг, чтобы преобразовать образцы чернильных или типографских меток восмысленный текст. Компьютеры, однако, еще борются за решение этой одной изосновных задач при создании машинного интеллекта.
Современноесостояние OCR отвечает уровню, при котором довольно много систем могут бытьвесьма надежны, когда они имеют дело с чистым четким текстом, однакокомпьютерным программам все же еще далеко до того, чтобы предложитьпользователю такую же безупречную точность, как предлагает другой помощник мозгачеловека — калькулятор. Большинство систем OCR работают с растровымизображением, которое получено через факс-модем или сканер. Для тех, ктоникогда не видел OCR, обозначим скороговоркой этапы распознаванияотсканированной страницы с точки зрения манипуляций над изображением текста.Делая «первый шаг», OCR должен разбить страницу на блоки текста,основанного на особенностях правого и левого выравнивания и наличия несколькихколонок. Потом эти блоки разбиваются в индивидуальные метки чернил (типографскойкраски и т.п.), которые, как правило, соответствуют отдельным буквам. Алгоритмраспознавания делает предположения относительно соответствия чернильных метоксимволам; а затем делается выбор каждой буквы и цифры. В результате страницавосстанавливается в символах текста (причем, в соответствующем оригиналуформате).
OCR-системымогут достигать наилучшей точности распознавания свыше 99 процентов длякачественных изображений, составленных из обычных шрифтов. Хотя это числокажется почти совершенным, уровень ошибок все же удручает, потому что, еслиимеется приблизительно 1500 символов на странице, то даже при коэффициентеуспешного распознавания 99,9% получается одна или две ошибки на страницу,требуя человеческого контроля результатов для гарантирования правильностисоответствия оригиналу. Встречающиеся в жизни тексты порой весьма далеки отсовершенных, и процент точности распознавания для «плохих» текстовчасто недопустим для большинства приложений. Грязные изображения — здесьнаиболее очевидная проблема, потому что даже малые пятна могут затенятьопределяющие части символа или преобразовывать один в другой.
Еслидокумент был ксерокопирован, нередко возникают разрывы и слияния символов(такие тексты нередко возникают и при сканировании). Любой из этих эффектовможет заставлять ошибаться, потому что некоторые из OCR систем полагают, чтокаждая соединенная черная метка должна быть одиночным символом.
Страница,расположенная с нарушением границ или перекосом, создает немного искаженныесимвольные изображения, которые могут путать программное обеспечениераспознавания. Даже, когда изображения — чистые, странные или декоративныеначертания могут вызывать проблемы, потому что они растягивают символы вразличные формы для художественного эффекта. Кроме того буквы могут иметьвариации среди начертаний того же самого наименования шрифта, когда, к примеру,символы, воспроизведенные принтером HP DeskJet, отличны от символов, которыенапечатаны на Apple LaserWriter.
Разработкаалгоритмов, которые позволяют распознавать символы, несмотря на эти проблемы — трудная задача. Разработчики должны сбалансировать потребность в гибкости ПО стребованием его точности. Если программное обеспечение не достаточно гибко, тооно будет неточно сегментировать символ, когда будет сталкиваться с различнымивариациями начертания. С другой стороны, слишком много гибкости может такжевызывать ошибки. К примеру, отличие между «b» и «h» внижнем регистре не очень большое, и гибкий алгоритм может спутать их.
Делениетекста на символы
Однаиз наиболее недорешенных задач в OCR — сегментация отдельных символов. Этопроисходит потому, что границы между буквами часто нечеткие, штрихи соседнихбукв соприкасаются, и это мешает делить слова на символы. Например, две илиболее буквы распознаются как одна, или одна — как две или три. Существуютшрифты, у которых, несмотря на общее хорошее качество печати, встречаютсясклейки (например, в шрифте Tense). Порою, увидев отсканированное изображение,в котором буквы сливаются на большей площади листа с текстом, можно заранеесказать, что данный текст не распознается корректно, и сэкономить свое время,даже не запустив программу на распознавание.
Образстраницы и распознавание по шаблонам
Программноеобеспечение OCR обычно работает с большим растровым изображением страницы изсканера. Изображения со стандартной степенью разрешения получаютсясканированием с точностью 300x300 пикселей на дюйм. Изображение бумажного листаформата A4 (11 формата) при этом разрешении занимает около 1 Мбайт памяти.Изображения c более тонким разрешением возможны с применением более дорогихсканеров, но они часто непрактичны для OCR-приложений из-за большой требуемойпамяти для изображений или длительности самого процесса сканирования. Крометого, увеличение разрешения сканера не приносит пользы, если качество оригиналанедостаточно хорошее. Анализируя изображения, исходящие из факсимильных машин,подбирают разрешение, проверяя отличия от имеющихся шаблонов символов (самаямаленькая их величина при самом близком соответствии).
Поэтой причине, большинство систем имеет шаблоны, созданные для различныхначертаний. После нескольких слов, программное обеспечение определяет основноеиспользуемое начертание и ищет соответствующие пары только с этим начертанием.В некоторых случаях программное обеспечение использует численные значениячастей символа (пропорций), чтобы определить новый шрифт. Это может улучшатьэффективность распознавания до других стилей печати, типа курсива или жирногоначертания слова, найденного на странице.
Такимобразом, при распознавании по шаблонам представление описания похоже напредставление входных объектов, и описание сравнивается с ними непосредственно.
Программараспознавания TypeReader фирмы ExperVision использует машинно-зависимыеалгоритмы, чтобы найти наиболее важные пиксели для различения символов. Берется30 различных вариантов символа (которые исходят из 30 различных документов) и вкаждом из этих примеров анализируется по 100 пикселей, чтобы определить то,какие из них наиболее вероятно должны быть характеристикой для специфическогосимвола (к примеру, пиксели на нижней части «A» всегда чисты и т.д.). Краевые элементы изображения вдоль границ символа часто исключаются этиманализом, потому что они могут быть темны в чистых изображениях, но чисты встраницах с пониженной четкостью. Машинный алгоритм ранжирует 100 пикселей отболее до менее непротиворечивых для каждого из символов.
Однакоэтого шага не достаточно из-за подобия между буквами. Например, в нижнемрегистре «h», «k», «f», «l», и«t» имеют общие длинные вертикальные штрихи слева, и пиксели вдольэтого штриха не будут передавать различия этих символов. По этой причине,программное обеспечение фирмы ExperVision находит 24 пикселя, которые являютсянаиболее непротиворечивыми у всех символов в алфавите, и удаляет их из спискадля индивидуальных символов. Пиксели, которые оставлены, должны с наибольшейвероятностью быть уникальными.
Такимобразом, требуется создать шаблон целостного описания символа, так чтобы любоеизображение буквы в него попадало, а любые допустимые изображения других букв — нет. В чистом виде шаблонное описание может применяться только дляраспознавания печатных символов. Заметим, что рукописные шрифты тожераспознаются с применением шаблонов (только «более хитрых»), ноодновременно со структурным подходом.
Структурныйподход
Самаяпродаваемая в мире система OCR — Caere OmniPage Professional используеталгоритм, который не должен настраиваться на индивидуальное начертание, потомучто он основан на нахождении общих специфических особенностей символов. Этасистема содержит 100 различных «экспертных систем», которые вдействительности являются только алгоритмами для идентификации 100 различныхсимволов: верхнего и нижнего регистра от «A» до «Z», записичисел и символов пунктуации. Каждая из этих экспертных систем ищет«особенности» начертаний типа «островов»,«полуостровов», точек, прямых оттисков и дуг. Экспертные системытакже рассматривают горизонтальные и вертикальные проекции оттисков буквы иобращают внимание на основные особенности в созданных кривых, суммируя в нихчисло темных пикселей.
Очевидно,что «t» всегда состоит из жирного вертикального штриха, поперечного сгоризонтальным штрихом. Дизайнер шрифта может включать в него засечки илисдвигать расположение пересечений, но человек может без труда выяснять иигнорировать эти отличия. Основанные на шаблоне подходы должны создать шаблоныдля каждого возможного шрифта (программа ExperVision, к примеру, использует2100 таких начертаний). Caere напротив пробует находить сущность каждого символана основе структурного подхода.
Нечеткийтекст может стать специфической проблемой для этих структурных алгоритмов,потому что отсутствующий пиксель может разбивать длинный штрих или кривую.Аналогично, дополнительное пятно грязи могло закрывать петлю записи числа«5» и заставлять ее выглядеть наподобие «6» согласнооснованному на особенности начертания алгоритму. Алгоритм на основе шаблоновздесь не имеет таких проблем, потому что остальные пиксели в «5»выровнялись бы правильно.
Контекстноераспознавание
Людиспособны быстро различить на бумаге «h» и «b» еще и потому,что они знают контекст слова, в котором встречаются эти буквы. По этой причинепрограммное обеспечение системы OCR включает словари для помощи алгоритмамраспознавания. Словари предоставляют справки во многих случаях, но быстроотказывают, когда, скажем, программное обеспечение сталкивается с именамисобственными, которые не находятся в словаре.
КорпорацияXerox имеет один из наиболее сложных пакетов программ с контекстным анализом.Пакет, называемый Lexifier (сокращение для «лексическийклассификатор»), содержит большинство главных правил записи буквенныхструктур или принятых образцов номеров телефонов. Он помогает интерпретироватьимена собственные типа Lexifier, которые кажутся совершенно правильноанглийскими, но не находятся в словаре. Этот эффект особенно заметен вроссийской программе FineReader, который чаще, чем в среднем по всем символам,ошибается в словах, которые отсутствует в его словаре (к примеру, названия фирмему даются тяжело).
Такимобразом, алгоритм распознавания в самом общем виде состоит в последовательномвыдвижении и проверке гипотез, причем порядок их выдвижения управляетсязаложенными в программу знаниями об исследуемом предмете и результатамипроверки предыдущих гипотез (производится дополнительный анализ объекта врамках выдвинутой гипотезы).
Основноетребование к предварительной обработке — не потерять о входном объектесущественную информацию. Поскольку для выделения целого требуются его части, адля нахождения частей требуется целое, целостный процесс восприятия можетпроисходить только в рамках гипотезы о воспринимаемом объекте — в целом.
Еслипрограмма должна приближаться к качеству восприятия текста человеком, то,скорее всего, она может успешно использовать алгоритм,«подсмотренный» у человека-читателя. Читая предложение, человекузнает буквы, воспринимает слова, связывает их в синтаксические конструкции ипонимает смысл предложения. Все процессы происходят одновременно, влияя друг надруга, а окончательное решение принимается на основе полного учета ихрезультатов.
Какбыло показано в примерах, целостное описание класса объектов восприятия должноудовлетворять двум свойствам: во-первых, все объекты данного класса должныудовлетворять этому описанию, во-вторых, ни один объект другого класса недолжен удовлетворять описанию.
Процессвыдвижения и проверки гипотез явно отражен в алгоритмах программы (каждаягипотеза имеет числовую оценку или операцию сравнения). Обычно гипотезывыдвигаются последовательно, объединяются в список и сортируются на основепредварительной оценки гипотезы. Окончательный выбор гипотезы делается в рамкахконтекста, с привлечением, возможно, дополнительных источников знания.
Коррекцияошибок
Подходв построении шаблонов в программе TypeReader настроен так, чтобы найти базовыепиксели в широком диапазоне документов. Разорванные символы находятсяавтоматически, потому что программное обеспечение избегает пикселей в указанномдоверительном интервале, которые могут исчезать в плохих изображениях.Программное обеспечение только должно найти места, в которых произошлоразбиение или размывание символов. Caere также имеет частный алгоритм дляразорванных символов.
Всепрограммы оптического распознавания позволяют проводить проверку ошибок пользователем,используя одновременное исходное изображение в окне экрана: нет необходимостиконсультироваться с бумажной версией. К примеру, программа TypeReaderпросматривает строки текста для поиска ошибок клавишей табуляции (программноеобеспечение помещает отсечение изображения за текстом так, чтобы Вы моглисравнивать текст с изображением без того, чтобы переместить взгляд). Ручнойпоиск ошибок в русских программах распознавания происходит аналогично.
Крометого, уже к 1993 году была продемонстрировано, что можно делать компьютерныепрограммы, использующие многие «человеческие» способы анализатекстового распознавания: OCR обучаются, чтобы делать лучше работу снеразборчивыми рукописными символами и метками, подобно зачеркиванию илиподчеркиванию. Но пока дальше демонстрационных трюков эти достижения не слишкомпошли.
Увеличениескорости бесклавиатурного ввода документов в технологиях электронногодокументооборота
Скоростьраспознавания порядка одного документа в минуту, считая накладные расходы накоррекцию, не позволяет говорить об удовлетворительном уровне автоматизацииввода больших потоков бумаг. Ведь скоростные сканеры Fujitsu в настоящее времяпозволяют вводить документы со скоростью 20-50 документов в минуту. Адекватныескорости оптического распознавания до недавнего времени не были достигнуты.
Однакоэта скорость, не имеющая первостепенного значения для отдельно взятого«писателя», использующего бесклавиатурный ввод материаловпервоисточников, необходима в архивах.
Ещев 1995 году были предложены два радикальных способа решения этой проблемы.
Однимиз них стало использование всех ресурсов Pentium-процессоров в системахраспознавания. Для этого фирмой Intel при участии российских разработчиков былисозданы специальные библиотеки для программ OCR (в рамках широкоразрекламированной программы NSP — позднее замененной программой MMX).
Какбыло сказано, при структурном подходе описание представляется в виде графа,узлами которого являются элементы входного объекта, а дугами — пространственныеотношения между этими элементами. При этом производится преобразование входногообъекта в представление, удобное для дальнейшей обработки (для«посвященных» можно упомянуть, к примеру, здесь векторизациюизображения, преобразование Фурье), либо в получение всевозможных вариантовсегментации входного объекта, из которых путем выдвижения и проверки гипотезвыбирается правильный (построение графа линейного деления слова,предварительное выделение объектов при распознавании формы).
Именнотакие операции (свертки, преобразования Фурье и др.) были оптимизированы нанизком уровне для Pentium-процессоров, а соответствующие библиотеки бесплатнопредоставлены фирмой Intel разработчикам. Еще более кардинальный способ былреализован в России, когда была создана установка распознавания (на базе OCRфирмы «Окрус»), использующая параллельные вычисления наиболеетрудоемких операций на транспьютерах. Но дальнейшего развития этот экспериментне получил.
Заключение
Главныйвывод в данном разговоре об OCR — это то, что описываемые системы многое умеюти являются полноправными системами в пакете программ «электронногоофиса». Их надо иметь.
Еслиже делать выводы о закономерностях в построении программ OCR, то можно сказатьследующее.
Шаблонноеописание проще и эффективней в реализации, но, в отличие от структурного, непозволяет описывать объекты с высокой степенью изменчивости. В простейшемслучае, шаблонное описание может применяться для распознавания печатныхсимволов, а структурное — для рукописных. Отметим, что все современные российскиепрограммы распознавания — Autor, CuneiForm и FineReader — являютсяструктурно-шаблонными. По-видимому, только сочетание этих двух методовобеспечивает приемлемую надежность. Целостность процесса восприятия программныхпродуктов OCR предполагает, что все исследуемый объект должен представляться иобрабатываться по возможности весь сразу, а источники знания должны работать повозможности одновременно: каждая фраза подвергается распознаванию, словарной иконтекстной обработке (для создания обратной связи от контекстной обработки краспознаванию).
Списоклитературы
1.Новиков Ф., Яценко А. MicrosoftOffice 2000 в целом. СПб.,1999.
2.Рабин Ч. Эффективная работа с MicrosoftOffice 2000. СПб., 2000.
3.Айден К., Фибельман Х., Крамер М. Аппаратные средства РС. СПб., 1997