В 2023 году первой российской коммерческой технологии распознавания текста исполнилось ровно 30 лет. В честь этой знаковой даты мы решили подготовить серию материалов о том, когда появились и что из себя представляли первые отечественные OCR. Кто был главными участниками в гонке по созданию систем распознаванию? Как так вышло, что в середине 90-х OCR была признана второй по значимости софтовой разработкой после ОС? Как выглядела первая OCR-ка для Mac? Ответим на эти и многие другие вопросы, присаживайтесь поудобнее.

Во время подготовки текстов мы побеседовали с директором по науке и душой нашей компании, доктором технических наук, профессором, членом-корреспондентом РАН Владимиром Львовичем Арлазаровым. Он – как, кстати, и еще несколько членов нашей команды Smart Engines – принимал непосредственное участие в создании первых систем автоматического ввода текста.  

Сегодня речь пойдет про OCR Tiger и про то, как эта система работает.

Первые шаги на пути OCR-революции

Но сперва перенесемся в более ранний период, начало XX века – именно тогда начали появляться первые алгоритмы распознавания символов. В 1932 году отечественный инженер В. Агапов разработал машину, способную вводить цифры в счетное устройство путем сравнения с набором “эталонов”. 

В 60–70-е появилась россыпь алгоритмов распознавания образов символов. Но они носили модельный характер. Хотя все понимали, что задача сложная и важная, не было ни экспериментальной базы (примеры “рисовались” самими авторами программ), ни широкого применения. Тексты по-прежнему перепечатывались руками.

Ситуация заметно изменилась лишь к концу 80-х. На то было две основные причины:

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

• появились сканеры, которые могли с большой скоростью загрузить в ЭВМ изображения с любым количеством текста. 

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

Кто научил компьютеры читать? 

Одним из таких мест оказался Институт системного анализа РАН. Там разработку первой коммерческой OCR в конце 80-х возглавил Владимир Львович Арлазаров, доктор технических наук, пионер в области искусственного интеллекта и всемирно известный ученый. В 1990 группа при его руководстве стала лауреатом премии Совета Министров СССР.

К тому моменту он уже имел колоссальный опыт в решении интеллектуальных задач, таких как разработка операционных и информационных систем, СУБД, создание шахматных программ. 

Так, именно Владимир Арлазаров вместе со своей командой создал шахматную программу “Каисса”, получившую название в честь вымышленной богини шахмат и ставшую первым чемпионом мира по шахматам среди шахматных программ (1974). Он был одним из авторов теоремы “четырех русских”. “Советский Microsoft” СУБД “ИНЕС”, которую в Советском Союзе использовали одновременно несколько тысяч предприятий – кстати, тоже достижение команды Владимира Львовича. 

В самом конце 80-х-начале 90-х он занялся распознаванием текстов. В разработке программы вместе с ним участвовал большой коллектив ученых ИСА РАН – Эдуард Коммисарчик, Александр Талалай, Игорь Фараджев, Андрей Леман, Михаил Климентьев, Алексей Петров, Василий Постников, Олег Славин, Владимир Троянкер. 

“Мы договорились с издательством “Художественная литература”, что сделаем для них OCR, с помощью которой они смогут оцифровывать старые книги. Поскольку в советское время для печати использовалось всего несколько гарнитур, то есть шрифтовых наборов, то и программу мы обучили распознавать их ограниченное количество. Так стало возможным засунуть страницу в сканер, отсканировать ее и тут же распознать, причем делать это стало возможным в любых количествах”, – вспоминает Владимир Львович Арлазаров.

Программа получила название OCR Tiger, а ее продажей занялась организованная Владимиром Львовичем Арлазаровым в 1993 году компания “Когнитивные технологии”. Вместе с ним управление компанией осуществляла Ольга Ускова, дочь коллеги и одного из разработчиков "Каиссы" Анатолия Ускова.

Это была, пожалуй, первая в России коммерческая разработка OCR.  FineReader от компании Bit Software выйдет спустя полгода.

Что есть OCR и с чем ее едят?

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

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

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

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

•  поиск иллюстраций;

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

•  поиск границ колонок текста;

•  поиск границ символьных строк;

•  поиск границ слов;

•  поиск границ символов.

Отметим, что алфавит распознавания должен включать не только символы естественного языка и цифры, но и специальные символы (несколько видов скобок, знаки номера и процентов, знаки валют и т.п.) и знаки препинания.

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

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

Как работает классификатор?

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

Основной характеристикой классификатора считается его точность — процент правильно выдаваемых ответов, посчитанных на некоторой значимой выборке.

На самом деле, классификаторы выдают обычно несколько вариантов ответа (например, все возможные), снабжая каждый оценкой. Эта оценка служит суррогатом субъективной (с точки зрения классификатора) вероятности правильности данного варианта ответа. Если нужен единственный ответ, то выбирается вариант с  максимальной оценкой. Но во многих случаях наличие нескольких вариантов полезно. Например, в OCR часто используются лингвистические постобработчики вроде словарей, массивов и триграмм, у которых свои оценки возможности или вероятности тех или иных сочетаний символов в слове. 

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

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

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

Первые два классификатора имеют точность 98,5%, но не обладают монотонностью оценок. У первого вероятность количества ошибок практически не зависит от интервала оценок, а второй дает выбираемому ответу всегда наивысшую оценку.
Третий классификатор имеет меньшую точность – 97%. Но благодаря монотонности оценок его использование предпочтительнее. Ведь если рассматривать только объекты, получившие оценку больше 75 (а их 85%), то будем иметь почти абсолютную точность. И даже для объектов, имеющих оценку больше 50 (а их уже 95%), точность все еще близка к 99%.

Разумеется, надо еще придумать, что делать с остальными 5 (или 15) процентами ненадежно распознанных объектов. Для этого существуют различные механизмы. В OCR Tiger распознанный текст попадал в специальный текстовый редактор. Редактор показывал распознанный текст, «подсвечивая» подозрительные места. При подведении курсора к такому месту в отдельном окне показывался соответствующий фрагмент изображения, чтобы человек мог увидеть и, если надо, сам подправить финальный текст. (Надо только понимать, что в реальных OCR-системах, в отличие от нашего иллюстративного примера, не бывает 5% подозрительных символов: 0,2-0,3% для обычных текстов – уже довольно большое число).

Другое решение – предъявить подозрительные объекты еще одному классификатору, существенно отличному от первого, а затем скомбинировать результаты. 

Полосатое распознавание: OCR Tiger

Как мы уже сказали, OCR Tiger, о которой ниже пойдет речь, предназначалась для распознавания книг. В первых версиях система умела распознавать страницы, напечатанные одним шрифтом и одним размером шрифта (кеглем). Кроме того, она позволяла распознавать страницы с несколькими колонками и сохранять результаты в собственный формат или формат TXT. 

Сканировать изображения система умела с помощью сканеров нескольких типов – планшетного, протяжного или ручного. Ручные сканеры пользовались повышенным спросом в 90-е годы из-за своей дешевизны. Правда, они имели один существенный недостаток – размер сканера был меньше страницы А4. Эту проблему OCR Tiger успешно решал, объединяя оцифрованные ручным сканером распознанные части одной страницы.

Вот еще несколько любопытных фактов о программе:

• OCR Tiger имел собственный интерфейс, в том числе для редактирования распознанного текста;

• OCR Tiger функционировал в операционной системе MS DOS и умещался в 640 Кбайт памяти;

• На компьютере без русификации была возможна виртуальная клавиатура;

В более поздних версиях программы были предусмотрены гарнитуры Times New Roman, Курьер, Академическая, Журнальная, Машинопись и появилась возможность обрабатывать страницы с несколькими шрифтами разных размеров. Оптимальный шрифт подбирался для каждой из строк, что, впрочем, существенно замедляло процесс распознавания.

Среднее время распознавания книжной страницы на процессоре Intel 80386 с тактовой частотой 33 МГц не превышало 10 секунд. Количество ошибок распознавания на книжной странице хорошего качества не превышало 1-2. И быстродействие, и точность обеспечивались алгоритмами распознавания. Эти алгоритмы были разработаны в предположении, что обрабатываются буквы одного единственного шрифта.

Метод сравнения с эталонами 

Для этого и других описываемых методов распознавания символов используется представление символа в виде матрицы бинарных значений, в которой 0 соответствовал фону, а 1 – тексту и другим печатным объектам. Перед началом распознавания страницы границы символов неизвестны. Первыми кандидатами на роль символов являются компоненты связности. В OCR Tiger извлечение компоненты связности проводилось параллельно с процессом сканирования. Это было возможным благодаря возврату управления центральному процессору после отправки в порт компьютера инструкции с запросом получения порции строк сканируемого растра.

Описываемый метод был создан группой сотрудников ИСА РАН (тогда ВНИИСИ): В. Л. Арлазаров, А. Б. Талалай, А. В. Карзанов. Алгоритм обучения основывался на сумме образов символов, соответствующих одной букве. В идеальном случае обучающее множество образов одного символа из одного шрифта содержало достаточно близкие образы. Образы всех таких символов подвергались нормализации посредством центрирования. Представлением образа являлись множество точек , таких что . Нормализованные образы суммировались в один суммарный образ .

Построение кластера символа, а затем идеального образа или эталона в OCR Tiger велось вручную. Тем не менее, вопросам сбора кластеров и их анализу посвящено много научных работ, которые и привели к методу адаптивного распознавания в системе оптического распознавания следующего поколения CuneiForm (подробно расскажем про нее в следующей части).

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

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

Метод распределения масс

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

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

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

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

Поиск границ символов 

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

1) построение множества возможных границ символов;
2) организация перебора для нахождения наилучшего варианта распознавания последовательности символов;
3) извлечение образов символов и их распознавание.

Промышленное применение OCR Tiger

OCR Tiger был реализован в виде коммерческого продукта, предназначенного для частных лиц и организаций. OCR Tiger умел работать с несколькими классами сканеров: Hewlett Packard, Epson, Logitek, Dextra и других, в частности, с российским проекционным сканером Унискан.

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

Вместо заключения

Так, в этой статье мы рассказали про первую отечественную коммерческую OCR – Tiger. Созданная командой матерых ученых, она была реализована в виде коммерческого продукта, предназначенного для частных лиц и организаций.

На следующей неделе мы подробно расскажем про еще одну OCR-систему – CuneiForm, как ученые РАН состязались с выпускниками МФТИ и какое развитие получили технологии распознавания текста в 2000-х.

А пока предлагаем ознакомиться с нашими более ранними материалами:

• Миссия выполнима: как Smart Engines обучила нейросеть распознавать все страницы паспорта РФ и находить подделки

• Нейросеть распознает 15 документов за 1 секунду. А так можно было?

Настоящая публикация создана на основе научной статьи Slavin, O. A., Arlazarov,V. L.: Algorithms of the Tiger and CuneiForm Optical Character Recognition Software. Pattern Recognition and Image Analysis. Special Issue: Scientific schools of the Federal Research Center “Computer science and control” of the Russian Academy of Sciences, V.L. Arlazarov’s Scientific School. (2023)