3.4. АЛГОРИТМЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ

Сущность предварительной обработки.

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

Рис. 3.2. Предварительная обработка

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

Неодинаковость ширины линий относится к систематическим отклонениям. К числу отклонений, носящих случайный характер,

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

Рис. 3.3. Заполнение пустот

Утоньшение.

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

Будем рассматривать три последовательные строки растра . Выделим в i-й строке произвольный элемент, который обозначим через а. Этот элемент имеет в выбранных строках восемь соседних элементов, которые обозначили цифрами как показано на рис. 3.4, Основная идея процедуры утоньшения заключается в том, чтобы отыскать на изображении крайние сверху, снизу, справа и слева элементы, а затем вынести решение о возможности их удаления с соблюдением перечисленных выше условий. Естественно элемент а считать крайним сверху, если он и элемент 6 зачернены, а элемент 2 незачернен. Формально эту ситуацию можно выразить так: элемент является крайним сверху, если равна единице

Рис. 3.4. Нумерация элементов окна 3X3

следующая булева функция, в которой символы переменных совпадают с номерами элементов на рис. 3.4:

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

Таким образом, элементу а будет придаваться нулевое значение при равенстве единице следующей функции:

Функция должна быть вычислена для каждого элемента строк» растра, поэтому выражение (3.2) запишем в векторной форме

Здесь — векторы, определяющие соответственно инверсию строки, строку в исходном растре и т. д., — вектор, единичные компоненты которого определяют элементы строки, значения которых необходимо сменить с 1 на 0.

Элемент растра является крайним слева, если равна единице функция Этот элемент подлежит стиранию, если функция равна единице. Следовательно,

Рассуждая таким же образом, получим векторы и определяющие подлежащие стиранию крайние нижние и крайние правые элементы растра:

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

Здесь символ обозначает операцию сложения по модулю 2. На рис. 3.5, б — показаны полученные моделированием на ЭВМ результаты последовательного применения преобразований (3.6) к находящемуся на растре символу (рис. 3.5, а). Окончательный результат утоньшения представлен на рис. 3.5, е.

Результаты моделирования алгоритма на ЭВМ показали, что для утоньшения требуется не более циклов, где — максимальная толщина линии в исходном символе.

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

(см. скан)

Рис. 3.5. Последовательное преобразование при утоньшении: а - исходный символ; б - д - промежуточные результаты; е — окончательное изображение

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

Рис. 3.6. Стирание бахромы

Для повышения надежности распознавания каждому циклу утоньшения целесообразно предпослать цикл Коррекции символа. Цикл коррекции подобен циклу утоньшения и состоит также из четырех этапов — стирания бахромы и фона сверху, слева, снизу, справа. На рис. 3.8 показаны ситуации, в которых элемент растра считается концевой точкой сверху. Из рисунка легко записать выражение для двоичного вектора единичные компоненты которого есть верхние концевые точки в i-й строке

Для стирания верхних концевых точек необходимо выполнить преобразование символа по формуле

(см. скан)

Рис. 3.7. Утоньшение и стирание бахромы: а — исходный символ; б — результат только утоньшения; в — результат последовательных утоньшений, чередующихся со стиранием концевых точек

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

Рис. 3.8. Окна с концевой точкой сверху

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

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

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

В [55] описаны более универсальные алгоритмы предварительной обработки. Рассмотренные же простые и эффективные методы распознавания дают вполне приемлемые результаты