И.М.Журавель "Краткий курс теории обработки изображений"

В оглавление книги \ К предыдущему разделу \ К следующему разделу

Распознавание рукописных знаков

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

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

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

,

где , , -- -й элемент изображения, являющийся одним из элементарных изображений ; - длина изображения.

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

,

где - -й элемент эталона, определенный на множестве допустимых направлений .

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

Для построения алгоритма распознавания используется метод максимального правдоподобия. Решающее правило определяется выражением

.

(1)

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

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

,

(2)

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

С учетом выражения (2) решающее правило может быть определено следующим образом:

.

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

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

Здесь - кратчайший путь из начальной вершины в вершину с индексами . Значение дает длину кратчайшего пути.

Эталон находится простым перебором.

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

Рис. 1. Процесс синтеза эталона: / - 4 - штрихи.

Рис. 2. Граф, состоящий из трех штрихов.

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

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

Граф представляет собой наибольший из возможных эталонов данного класса. Граф, приведенный на рис. 2, состоит из трех штрихов. Вертикальные линии графа соответствуют элементам входного изображения. Минимальная длина эталона 7, максимальная 12. Входное изображение состоит из 11 элементов. Каждая вершина графа определяется тремя координатами: , где - номер элемента входного изображения.

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

где - результат сравнения элементов эталона с элементом входного изображения ; - номер последнего в штрихе обязательного элемента; - номер последнего в штрихе необязательного элемента.

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

Рассмотрим коротко историю создания некоторых первых отечественных и зарубежных читающих автоматов. Заметные успехи в области практического применения систем для распознавания визуальных изображений достигнуты главным образом в создании устройств для распознавания изображений печатных букв и цифр. Существующие автоматы позволяют читать с требуемой надежностью только знаки фиксированных начертаний. Попытки создания автоматов для визуального чтения рукописных букв произвольного начертания пока нельзя считать успешными [2].

Если заглянуть в историю, то среди первых разработок, прошедших испытания, можно выделить читающие автоматы Р711 и РУТА-701 Вильнюсского СКВ вычислительных машин.

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

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

Автомат РУТА-701 предназначен для ввода в вычислительную машину многострочных документов. Автомат читает десять цифр и четыре служебных символа. Рукописные цифры должны, так же как и в автомате Р711, вписываться в небольшие прямоугольники, заранее напечатанные на документе краской, не воспринимаемой автоматом. Максимальная скорость чтения автомата составляет 220 знаков в секунду. Вероятность ошибки имеет порядок . Машинописные цифры распознаются методом сравнения с эталоном, рукописные цифры - с помощью специально выбранной системы признаков. В обоих случаях необходима центровка изображения.

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

Многошрифтовой автомат фирмы "Radio Corporation of America" был сконструирован так, что изображение в нем считывается с помощью электронно-лучевой трубки типа "бегущий луч" и фотоумножителя, а затем воспроизводится на экране двухлучевого кинескопа в виде позитива и негатива. С помощью оптического размножителя полученные на экране изображения проектируются на эталонные маски, которые представляют собой высококонтрастные позитивные и негативные изображения эталона. Позитивное изображение накладывается на эталон-негатив, а негативное изображение - на эталон-позитив. Степень несовпадения распознаваемого знака с данным эталоном характеризуется результирующим световым потоком по каждому каналу. Распознавание производится по наименьшему световому потоку. В каждом канале установлены фотоумножители и интеграторы, которые преобразуют световые потоки в соответствующие электрические сигналы. В автомате предусмотрена специальная система управления, которая выполняет следующие действия: переключение операций (поиск знака, поиск строки, чтение знака) и центровку знака. Кроме того, в автомате используется так называемая принудительная идеализация распознаваемых знаков. Это осуществляется с помощью специальной системы автоматического регулирования яркости и контрастности изображения распознаваемого знака, полученного на экране двухлучевого кинескопа.

Автомат позволяет считывать и вводить в ЦВМ две печатные строки со стандартного бланка размером мм. Скорость подачи документов составляет 6 документов в секунду, скорость чтения - 500 знаков в секунду. Автомат обладает высокой надежностью распознавания: одна ошибка на 200 000 знаков, т. е. число ошибочных ответов не превышает 0,0005%. Следует, однако, отметить, что приведенные цифры характеризуют испытание 16-канального макета, причем при оценке надежности не указывается качество печати распознаваемых знаков.

Уровень развития современных средств распознавания печатных символов достаточно высокий, что позволяет применять их даже на бытовом уровне при распознавании печатных символов отсканированных документов. Распознавание рукописных знаков остается пока открытой задачей.

Литература.

1. Ковалевский В.А. Оптимальный алгоритм распознавания некоторых последовательностей изображений. - Кибернетика, 1967, № 4, с. 75 - 81.
2. Васильев В.И. Распознающие системы. Киев: Наукова думка, 1983.

В оглавление книги \ К предыдущему разделу \ К следующему разделу