Морфологическая обработка контурных изображений в системах распознавания текстовых символов

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

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

Рассмотрим две базовые морфологические операции: расширение и сжатие, которые являются основополагающими в большинстве алгоритмов морфологической обработки изображений [1]. Пусть А и В - конечные множества из пространства Z ². Тогда расширение множества А по множеству В определится как

А ® В -{ z |(( В ' ) _г n Л ) с А }, (1) где В' является центральным отражением множества В , В' - { v | v = - b , b e В }; а ( В ) _г определяет параллельный перенос или сдвиг множества В в точку z = (z₁, z₂) по следующему правилу:

( В ) _г - { щ | щ - b + z , b e В }.

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

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

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

Существует морфологическая операция, обратная операция расширения, называемая сжатием множества А по примитиву В :

А ^ В-МВ^ с А }. (2)

Иными словами, сжатие множества А по примитиву В определяется как множество всех таких точек z , при сдвиге в которые множество В целиком содержится во множестве А . Одним из частых применений операции сжатия является исключение несущественных (по размерам) деталей двоичного изображения.

Операции расширения и сжатия являются двойственными операциями по отношению к операциям дополнения и центрального отражения:

с_еа ® в С , ( А В ), (3)

где С_ЕА - дополнение множества А относительно множества Е (множество Е в данном случае можно интерпретировать как изображение реального мира).

Приведем доказательство выражения (3). Согласно определению операции расширения (1),

С^ ® # - { z |(( В ) _г n С Е А ) с С е А }.

Поскольку (( В ) _г п С_ЕА ) с С_ЕА , то ( В ) _г п С_ЕА ^ 0 . Следовательно (с учетом справедливости соотношения С_ЕС_ЕА - А ), получим

С е А Ф В - { z |( В ) _г n С Е А * 0 }- С е С еМ В ) ; П С е А * 0 }.

Дополнением для множества z , удовлетворяющего условию ( В ) п С_ЕА ^ 0 , является множество таких z , что ( В ) _г п С_ЕА - 0 . Поэтому последнее выражение можно переписать следующим образом:

С^ ® # - С Е { z |( В ) _г n С Е А - 0 } -

• -    С еМ В ) ; П А ^ 0 } - С е {^( В ) _г с А }, что и означает выполнение равенства (3) в соответствии с определением операции сжатия.

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

Операция открытия множества А по примитиву В обозначается как. А О В и определяется равенством

А°В -(Ае В ) ® В .

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

Операция закрытия множества А по примитиву В , обозначаемая как А • В , имеет вид

А • В-(А®В)е В и обозначает, что к результату операции расширения множества А по примитиву В применяется операция сжатия по примитиву В.

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

С е ( А • В )- С е( А )о В ' .           (4)

Приведем доказательство выражения (4). Преобразуем левую часть соотношения (4) в соответствии с определениями операций расширения (1) и сжатия (2):

С е ( А • В ) - С Е ({ z |(( В 2 \о А ) с А } е В ) -

• -    С Е ({ z |( В ) _г с (( В^г ) р А ) с А )}) - С е ({^( В ) ₂ с А )}).

Поскольку множество (В)г содержится во множестве А, то (В).рСЕА - 0. Дополнением для множества z, удов- летворяющего данному условию, является множество таких z, что (В)_пСеА * 0. Поэтому последнее выражение можно переписать следующим образом:

С_е ( А • В ) - { z |(( S ) _z n C^ ) * 0 } - { z |(( S ) _z n C^ ) с С^ }.

Теперь преобразуем правую часть соотношения (4) в соответствии с определениями операций сжатия (2) и расширения (3):

С е ( А ) °В 2 - { _г |( В ‘ ) _г с С Е А }) ® В 2 -

-{<( В ) р СА ) с СА }.

Поскольку обе части соотношения (4) приведены к общему выражению, то равенство (4) доказано.

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

• а)    А ° В является подмножеством А , т. е. вложенным изображением;

• б)    если С есть подмножество В , то С ВВ является подмножеством В °В ;

в)( А⁰В ) °В - А°В .

Операция закрытия имеет аналогичные свойства:

• а)    множество А является подмножеством, т. е. вложенным изображением А • В ;

• б)    если С есть подмножество В , то С • В является подмножеством В • В ;

• в)    ( А • В ) • В - А • В .

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

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

Морфологическое преобразование «успех / неудача» является основным методом обнаружения на изображении объектов определенных размеров и формы. Представим множество В как В - ( В ₁, В ₂), где В ₁ - множество элементов В , относящихся к интересующему объекту; В ₂ - множество элементов окружающего фона. Преобразование «успех / неудача» имеет следующий вид:

А ® В -(Ае В ₁) п ( С_е А6 В ₂).        (5)

Выражение (5) можно интерпретировать следующим образом. Множество А ® В содержит все точки, в которых одновременно для множества элементов объекта В ₁ имеется эквивалент во множестве А , а для множества элементов фона В ₂ - эквивалент в дополнении к множеству А (во множестве СА)- В этом случае говорят, что имеет место «успех».

Используя определение разности множеств и соотношение двойственности между операциями сжатия (2) и расширения (1), равенство (5) можно переписать в виде

А ® В -(Ае В ₁)\( А ® В ₂ ‘ ).

Совместное использование примитива В^ связанного с интересующим объектом, и примитива В2, связанного с фоном, базируется на том соображении, что два и более объекта различимы только в том случае, если они образованы непересекающимися множествами. Иными словам, на изображении должна присутствовать область фона вокруг каждого объекта шириной не менее одного пикселя.

Утончение множества А по примитиву В , обозначаемое как А.В ,можно определить с помощью преобразования «успех / неудача»:

А .В - А \( А ® В ) - А п С_е ( А ® В ).

Интерес при этом представляет только поиск в исходном множестве мест совпадения объекта с конфигурацией пикселей примитива В , так что в преобразования «успех / неудача» не участвует окружающий фон.

Возможно симметричное утончение множества А , основанное на последовательном применении примитивов

В-В1,В2,В3, _,В", где примитив В' получается из примитива В'-1 поворотом. На первом шаге производится утончение множества А по примитиву В1, затем полученный результат подвергается утончению по примитиву В2 и т. д., вплоть до и-го шага с примитивом В". Процесс повторяется до тех пор, пока наблюдаются изменения. Каждый шаг утончения выполняется с помощью соотношения (5).

Утолщение представляет собой двойственную морфологическую операцию по отношению к утончению

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

Отметим, что рассмотренные выше базовые морфологические операции расширения, сжатия, открытия и закрытия можно распространить на полутоновые изображении. В этом случае предполагается, что в морфологических алгоритмах участвуют цифровые изображения, заданные функциями/(х,у) и Ъ(х,у), где/(х,у) - исходное изображение; Ъ(х,у) - изображение примитива. Тогда полутоновая операция расширения /по Ъ определяется как

(f ® b)(s, t)-max{/(s-x, t-y) +

+Ъ(х,y)\(s-х, t-y) E В ;(х,у) Е В _Ъ }, (7) где В и В _Ъ - области определений изображений/и Ъ соответственно; s и t - сдвиги координат по осям X и У. Условие, заключающееся в том, что координаты (s - х) и (t-у) должны находиться в области определения./ ахи у - в области определения Ъ, является аналогом условия в определении двоичной операции расширения, которое требует, чтобы два множества пересекались хотя бы в одном элементе. Кроме того, уравнение (7) по форме аналогично определению двумерной свертки с точностью до замены суммирования операцией взятия максимума, а умножения - сложением.

Аналогичным образом определяется полутоновая операция сжатия /по Ъ:

(/и b)(s, t) = min[/(s + х, t +y) -

• -b(x,y)\(s+x,t+y) e D^ (x,y) e D^ , (8) где D _/ .и D _b - области определений изображений/и b соответственно. Условие, состоящее в том, что координаты (s + х) и (t +у) должны находиться в области определения /, а х и у - в области определения b, аналогично условию в определении двоичной операции сжатия, которое требует, чтобы примитив полностью находился внутри исходного множества. По форме уравнение (8) повторяет уравнение двумерной корреляции с точностью до замены суммирования операцией взятия минимума, а умножения - вычитанием.

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

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

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

1	0	- 1		1	2	1
2	0	- 2		0	0	0
1	0	- 1		- 1	- 2	- 1
2	1	0		0	1	2
1	0	- 1		- 1	0	1
0	- 1	- 2		- 2	- 1	0

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

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

• 1    - 8 1 .

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

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

а                     б

Рис. 1. Маски морфологической обработки: а - крестообразная 3 x 3; б - квадратная 2 x 2

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

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

Часто в системах распознавания рукописных символов входное изображение после операции сканирования имеет произвольную ориентацию. Для определения ориентации и приведения изображения к нормализованному виду (строки должны быть расположены горизонтально) обнаруженные информативные зоны подвергаются дополнительному анализу Таким образом будет получено ориентированное изображение с выделенными зонами, содержащими рукописные символы (рис. 3).

Затем найденные информативные текстовые зоны сегментируются на изображения, содержащие отдельные рукописные слова и символы. Каждое сегментированное изображение подвергается фильтрации, в результате которой получается контурное изображение. При этом в качестве фильтра можно использовать фильтр Робертса A ' = IA - D | + | B - C |, или А ' = V ( A - D ) ² + ( B - C ) ² , где А' - новое значение яркости текущего пикселя; А -значение яркости текущего пикселя; В - значение яркости пикселя снизу от текущего пикселя; С - значение яркости пикселя справа от текущего пикселя;^ - значение яркости пикселя, расположенного по диагонали от текущего пикселя.

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

На основе представленного выше теоретического подхода было разработано программное обеспечение для морфологической обработке печатных текстовых символов в среде интегрированной разработки приложений Delphi 2005. Экранный интерфейс представляет собой две матрицы 50 x 50 элементов, в которых отображается оригинал изображения символов (например, из файла или нарисованных пользователем), а также панель управления, с помощью которой можно отобразить вид маски и выбрать ее размеры. Также имеется возможность наложить шум на оригинал изображения в заданном процентном соотношении (этот показатель пользователь может устанавливать по желанию). Программное обеспечение позволяет выполнять базовые морфологические операции в любой последовательности. Было проведено тестирование на 280 образцах, каждый из которых подвергался трем степеням зашумления (3,5,7 %). В зависимости от заполненности матрицы контурными фрагментами и возможными шумами при использовании алгоритма динамического выбора шага производительность возрастала на 11...47%.

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

Рис. 2. Стадии морфологической обработки: а - изображение-оригинал; б - изображение после операции закрытия; в - изображение после операции открытия

а                                                        б

Рис. 3. Пример выделения информативных текстовых зон: а - оригинал изображения;

б - изображение после многократной операции расширения

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