Б. Леонтьев - Секреты сканирования на ПК
Альтернативой традиционному шаблонному методу распознавания стало распознавание на основе принципов Целостности, Целенаправленности и Адаптивности.
Согласно принципу целостности, распознаваемый объект рассматривается как целое, состоящее из частей, связанных между собой пространственными отношениями.
Изображение интерпретируется как определенный объект, только если на нем присутствуют все структурные части этого объекта, и эти части находятся в соответствующих отношениях. Сами части получают интерпретацию только в составе гипотезы о предполагаемом объекте.
По принципу целенаправленности распознавание строится как процесс выдвижения и целенаправленной проверки гипотез о целом объекте. Источниками гипотез являются признаковые классификаторы и контекстная информация. Части картинки анализируются не априорно, а только в рамках выдвинутой гипотезы о целом. Традиционный подход, состоящий в интерпретации того, что наблюдается на изображении, заменяется подходом, состоящим в целенаправленном поиске того, что ожидается на изображении.
Принцип адаптивности подразумевает способность системы к самообучению.
Впервые эти принципы были применены на практике в системе распознавания «Графит», которая была разработана под руководством Александра Шамиса в конце 80-х годов. Это была система распознавания рукопечатных знаков.
На этих же принципах в 1993 году фирмой Bit Software (ныне компания ABBYY) была создана система распознавания печатного текста FineReader. В своей работе эта система использовала признаковый классификатор в сочетании с целенаправленной проверкой гипотез о распознаваемых словах по словарю.
Признаковый классификатор использует некоторое количество признаков, которые вычисляются по изображению. Типичная процедура классификации состоит в вычислении степени близости между входным изображением и известными системе классами изображений. В качестве ответа выдается список классов, упорядоченный по степени близости, то есть фактически выдвигался ряд гипотез о принадлежности объекта тому или иному классу.
Как строится процесс распознавания символов в FineReader? Для быстрого порождения предварительного списка гипотез используются, как и ранее, признаковые классификаторы. Эти же классификаторы используются для повышения точности распознавания на изображениях с дефектами. Путем их комбинации выдвигаем гипотезу о том, что может быть на изображении. Каждый классификатор дает не один результат, а несколько лучших, которые объединяются в общий список. Получаем некий набор гипотез о том, что может быть на изображении. Далее гипотезы последовательно проверяются структурным классификатором, который целенаправленно анализирует имеющийся символ, исходя из знаний о его структуре. То есть, когда мы предполагаем, что на изображении может быть буква "а", мы можем целенаправленно проверить те свойства, которые должны быть именно у буквы "а", а не у какой-то другой буквы, сравнивая имеющийся у нас символ со структурным эталоном.
Структурный эталон описывает знак как набор структурных элементов, находящихся в определенных отношениях между собой. Используется четыре типа структурных элементов: отрезок, дуга, кольцо, точка. Отношения задаются как нечеткие логические высказывания. В качестве переменных используются различные атрибуты элементов — длины, описывающие рамки, углы, координаты характерных точек элементов.
Большинство отношений сводится к проверке того, что некоторая величина принадлежит диапазону с нечеткими границами. В результате проверки отношения получается оценка в диапазоне [0..1]. Оценки всех отношений перемножаются, что соответствует нечеткой логической операции AND.
Отношения проверяются сразу же после выделения всех использованных в этом отношении элементов. Если какое-то отношение не выполняется, проверка текущей ветви перебора останавливается. Это ограничивает перебор на ранних стадиях и позволяет избежать комбинаторного взрыва.
Итак, структурный эталон представляет символ в виде набора некоторых структурных элементов. Очевидно, что процесс распознавания должен включать в себя этапы выделения структурных элементов на изображении и сопоставления найденных элементов с эталонами. Видимое решение состоит в том, чтобы делать эти этапы последовательно: сначала выделить элементы, а потом сопоставить их с эталонами. Однако такой порядок действий имеет очень серьезный недостаток. Проблема заключается в том, что априорное выделение элементов неоднозначно. Даже человеку для того, чтобы правильно выделить элементы, недостаточно видеть только часть картинки. Он должен увидеть всю картинку целиком и выдвинуть гипотезу о том, что изображено на всей картинке. Эта гипотеза позволяет снять все неоднозначности — правильно соединить разорванные элементы и мысленно исправить все искажения.
Решение проблемы неоднозначности заключается в том, чтобы не выделять структурные элементы априорно. Вместо этого они должны выделяться прямо в процессе сопоставления эталона с изображением. Наличие гипотезы о предполагаемом содержимом всей картинки позволяет использовать априорные знания об устройстве знака: типах элементов, их относительном положении, допустимых значениях атрибутов. Это позволяет уверенно выделять структурные элементы даже на разорванных и искаженных изображениях.
Если в окончательный список попало более одной гипотезы, они попарно сравниваются с помощью структурных дифференциальных классификаторов. Так, например, если при распознавании символа возникла ситуация, когда структурный классификатор не может однозначно выбрать из двух букв с похожим написанием, то между этими конкурирующими гипотезами делают дифференциальный выбор. В целом этот процесс похож на процесс постановки больному диагноза. В медицине существует понятие дифференциального диагноза. Когда по внешним симптомам поставить диагноз невозможно, приходится проводить более тщательные исследования, вплоть до диагностической операции, чтобы выявить дополнительные симптомы, четко определяющие болезнь. Так и в процессе распознавания. Например, программа не может уверенно распознать символ.
Есть две гипотезы: "l" (латинская "л") и "1" (единица). Чтобы выбрать между этими двумя гипотезами, мы должны целенаправленно проанализировать левый верхний угол изображения, где помещается та единственная деталь, по которой мы можем отличить один символ от другого. Только так возможно будет сделать окончательный вывод о том, какая гипотеза правильна. Причем тщательно исследовать эту единственную деталь мы будем только после того, как у нас останется всего две гипотезы. В этом и заключается целенаправленность предлагаемого подхода. Ибо, если мы решим с самого начала проверять все имеющиеся изображения на наличие огромного количества мелких деталей (ведь пар похожих символов достаточно много, и в каждом конкретном случае деталь, по которой их можно различить, будет меняться), то, во-первых, резко снизится скорость распознавания, а во-вторых, информация об этих мелких деталях будет «засорять» процесс распознавания и помешает опознать буквы, для которых те или иные детали не имеют значения. То есть система станет более восприимчива к помехам.
После того, как работа дифференциального классификатора завершена, мы можем сказать, что непосредственно само распознавание закончено. У нас остается окончательный список гипотез, подлежащий проверке.
Окончательная верификация результата распознавания осуществляется системой контекста. Система контекстной проверки позволяет резко улучшить качество распознавания текстов плохого качества за счет того, что при наличии некоторого количества распознанных букв из слова компьютер может «догадаться», что это за слово, используя словарь. В FineReader удалось без больших потерь в скорости увеличить число рассматриваемых гипотез при анализе контекста, что, в свою очередь, также в лучшую сторону сказывается на точности распознавания текстов очень низкого качества.
В FineReader анализ документа проводится как до, так и после непосредственно распознавания, что позволяет гораздо лучше сохранять внешний вид документа при его экспорте в другие приложения из FineReader. В результате использования совмещенной процедуры значительно улучшилось выделение таблиц и отделение текста от графики. Фактически, основная задача разработчиков FineReader — сделать так, чтобы пользователь получил на выходе документ, полностью совпадающий как по содержанию, так и по внешнему оформлению с документом, который он недавно положил в сканер.
На сегодняшний день система FineReader демонстрирует непревзойденную точность распознавания и высокое качество анализа документа и сохранения его оформления. От версии к версии она совершенствуется, используются новые алгоритмы, появляются новые возможности. Но принципы Целостности, Целенаправленности и Адаптивности остаются неизменными, так как именно эти принципы позволяют машине приблизится к логике мышления, свойственной человеку, и в дальнейшем решать, возможно, гораздо более сложные задачи, чем задача распознавания.
