Сегментация изображения текста

Евгений Борисов

суббота, 9 августа 2008 г.

1 Введение

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

В данном случае мы предполагаем, что изображение текста правильно ориентированно, т.е. строки ровные и картинка не повёрнута относительно наблюдателя (рис.1).

**Рисунок 1:**изображение текста

Сегментацию изображения текста будем проводить в три этапа:

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

Будем рассматривать изображение текста в градациях серого. Исходное изображение можно представить как матрицу яркостей точек B

B={b_ij}

0≤b_ij≤b^max

i=1... n ; j=1... m

где n - ширина картинки, m - высота картинки

Для определённости будем считать, что максимальное значение яркости (b^max ) соответствует чёрному цвету а минимальное (равное 0) - белому.

2 Сегментация строк

Задача выделения строк сводиться к нахождению верхних и нижних граней строк текста, изображённого на исходной картинке.

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

Сначала для всех пиксельных строк исходного изображения находим их средние значения яркости

$\begin{displaymath}s_j = s_j(B) = \frac{1}{n}\cdot\sum\limits_{i=1}^{n} b_{ij}\end{displaymath}$
Затем определяем среднее значение яркости всего изображения

$\begin{displaymath}s(B) = \frac{1}{m}\cdot\sum\limits_{j=1}^{m} s_j(B)\end{displaymath}$
Средняя яркость в межстрочных промежутках текста должна быть невелика (в идеальном случае она равна нулю). Поэтому яркость верхней границы текстовой строки можно выразить через среднюю яркость изображения

s^t= k^t * s(B)

где 0<k^t<1 - коэффициент
Аналогично яркость нижней границы текстовой строки, также может быть выражена через среднюю яркость всего изображения

s^b= k^b * s(B)

где 0<k^b<1 - коэффициент

Работа алгоритма сегментации строк заключается в последовательном просмотре массива средних значений (s₁,...,s_m) и выявлении множества пар индексов (s^t_i,s^b_i) пиксельных строк, соответствующих верхней s^t_i и нижней s^b_i граням изображения строки номер i, удовлетворяющих следующим условиям.

Условия верхней границы текстовой строки.
Начало текстовой строки или области устойчивого повышения яркости фиксируется, если выполняется следующий комплекс условий:
- яркость текущей пиксельной строки превышает границу s^t
- яркость двух предыдущих пиксельных строк ниже этой границы
- яркость трех последующих строк выше границы s^b
т.е. в пиксельной строке с номером i начинается изображение текстовой строки если

(s_i-2 < s^t) ^ (s_i-1 < s^t) ^ (s_i > s^b) ^ (s_i+1 > s^b) ^ (s_i+2 > s^b) ^ (s_i+3 > s^b)
Условия нижней границы текстовой строки.
Конец области устойчивого повышения яркости определяется, если выполняется следующие условия:
- было зафиксировано начало области
- яркость текущей пиксельной строки превышает границу s^t
- яркость последующей пиксельной строки ниже границы s^b
Или:
- было зафиксировано начало области
- яркость трех последующих строк ниже границы s^b
т.е. в пиксельной строке с номером i заканчивается изображение текстовой строки, если ранее было определено, что строка началась, и выполняется условие

( (s_i > s^t) ^ (s_i+1 < s^b) ) v ( (s_i+1 < s^b) ^ (s_i+2 < s^b) ^ (s_i+3 < s^b) )

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

Чтобы избежать этого, необходимо расширить найденные границы. Можно предложить следующий алгоритм расширения границ. Среди найденных текстовых строк определяется строка с минимальной высотой H_min и, затем все границы с каждой стороны расширяются на величину 0.3 * H_min. Это не приводит к слиянию строк, т.к. межстрочные интервалы текста, как правило, больше чем высота строки (рис.2).

**Рисунок 2:**изображение текста с выделенными строками

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

3 Сегментация слов

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

**Рисунок 3:**выделенное изображение строки

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

Пороговый фильтр повышения контрастности

$\begin{displaymath} b_{ij} = \left\{\begin{array}{ccc} b_{max} & ; & b_{ij} > b_0\\ 0 & ; & b_{ij} \leq b_0 \\ \end{array}\right. \end{displaymath}$

где i=1... n ; j=1... m ; b₀ - порог яркости
Такое преобразование, при правильно выбранном пороге b₀, помогает снизить уровень шума, т.е. убрать значительное количество лишних точек (рис.4).

Рисунок 4:результат работы порогового фильтра
"Размазывающий" фильтр - для каждой яркой(чёрной) точки исходного изображения закрашиваем соседние точки.
В результате такого преобразования близкие точки объединяются в непрерывную область и вместо множества маленьких точек получаем картинку состоящую из нескольких сплошных пятен с достаточно чёткой границей (рис.5).

Рисунок 5:результат работы "размазывающего" фильтра

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

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

$\begin{displaymath}c_i = c_i(B) = \frac{1}{m}\cdot\sum\limits_{j=1}^{m} b_{ij}\end{displaymath}$

где m, - высота текущей строки в точках
Затем определяем среднее значение яркости для данного изображения строки

$\begin{displaymath}c(B) = \frac{1}{n}\cdot\sum\limits_{i=1}^{n} c_i(B)\end{displaymath}$

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

c^l= k^l * c(B)

где 0<k^l<1 - коэффициент
Аналогично яркость правой границы (конец слова), также может быть выражена через среднюю яркость всего изображения

c^r= k^r * c(B)

где 0<k^r<1 - коэффициент

Работа алгоритма сегментации слов заключается в последовательном просмотре множества средних значений яркости столбцов (c₁,...,c_n) и выявлении множества пар индексов (c^l_i,c^r_i) пиксельных строк, соответствующих левой c^l_i и правой c^r_i граням изображения слова номер i, удовлетворяющих следующим условиям (рис.6).

Условия левой границы (начало слова).
Начало слова или области устойчивого повышения яркости фиксируется, если выполняются следующие условия;
- яркость текущего и последующего пиксельного столбца превышает левую границу яркости для слова c^l
- яркость предыдущего пиксельного столбца ниже этой границы
т.е. в пиксельном столбце с номером j начинается изображение слова если

(c_j-1 < c^l) ^ (c_j > c^l) ^ (c_j+1 > c^l)
Условия правой границы (конец слова).
Конец области устойчивого повышения яркости определяется, если выполняются следующие условия;
- было зафиксировано начало слова
- яркость текущего и четырех последующих пиксельных столбцов ниже границы яркости межсловного интервала c^r
- яркость двух предыдущих пиксельных столбцов выше этой границы
т.е. слово заканчивается в пиксельном столбце с номером j , если ранее было определено, что слово началось, и выполняется условие

(c_j-2 > c^r) ^ (c_j-1 > c^r) ^ (c_j < c^r) ^ (c_j+1 < c^r) ^ (c_j+2 < c^r) ^ (c_j+3 < c^r) ^ (c_j+4 < c^r)

**Рисунок 6:**изображение строки с выделенными словами

4 Сегментация символов

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

**Рисунок 7:**изображение слова

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

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

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

Конечная цель работы - найти индексы столбцов-границ между символами.

4.1 Поиск локальных минимумов яркости

Поиск локальных минимумов средней яркости столбцов cⁱ происходит на смежных интервалах изменения индекса столбца. Размер интервала выбирается исходя из высоты строки. Для большинства шрифтов отношение ширины символа к его высоте не превышает величину 0.3. Поэтому размер интервала выбран

d_j = 0.3 * m

где m - высота слова в точках.

Поиск минимумов работает следующим образом.

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

$\begin{displaymath}c_i = c_i(B) = \frac{1}{m}\cdot\sum\limits_{j=1}^{m} b_{ij}\end{displaymath}$

где m - высота слова в точках.
Среди значений c_i первый минимум ищем на отрезке i=1,...,d_j.
Предположим, что он нашелся для индекса i¹_min.
Следующий минимум ищем на отрезке i=(i¹_min+1),...,(i¹_min+1+d_j).
Процедура поиска повторяется, до достижения границы ( i=n ) изображения слова. Все значения индекса i^j_min , соответствующих локальным минимумам, сохраняются в списке W₀ (рис.8).

**Рисунок 8:**изображение слова с локальными минимумами средней яркости столбцов

4.2 Удаление ложных границ

Удаление ложных межсимвольных границ будем проводить в несколько этапов.

Локальный минимум яркости в столбце номер i является "кандидатом" на принадлежность к межсимвольному интервалу, если значение средней яркости c_i в этом столбце меньше определённой границы яркости c^b и при этом значение средней яркости в столбцах отстоящих от данного локального минимума на 2 пикселя слева или справа больше границы яркости. Границу яркости можно определить через среднюю яркость картинки.

$\begin{displaymath}c^b = k^b \cdot \frac{1}{n}\cdot\sum\limits_{i=1}^{n} c_i(B)\end{displaymath}$

где 0<k^b<1 . - коэффициент, n - ширина изображения слова в точках.
Первое условие межсимвольных границы можно записать в следующем виде.

(c_i < c^b) ^ ( (c_i-2 > c^b) v (c_i+2 > c^b) )

В результате из списка индексов локальных минимумов W₀ удаляются индексы столбцов, средняя яркость которых не удовлетворяет этому условию, формируется второй список W₁ индексов-"кандидатов" в межсимвольные границы (рис.9).

Рисунок 9: изображение слова после удаления части ложных границ
Выявление связей между столбцами пикселей. На этом шаге алгоритма сегментации будем анализировать связность изображений символов и убирать из списка W₁ ложные границы, которые разрезают символ на части. Это может происходить с широкими слабосвязанными символами, например символы русского алфавита П, Н, Ц. Причём, символ может быть связан, либо в верхней (П), либо в средней (Н), либо в нижней части (Ц) пиксельных столбцов. Чтобы избежать неправильной классификации связности, разделим изображение на три уровня по вертикали и будем анализировать эти уровни отдельно друг от друга. Разделение изображения символа на части происходит в следующей пропорции: верхний уровень - 30% от высоты символа, средний уровень - 40% от высоты символа, нижний уровень - 30% от высоты символа.
Сформулируем условия связности двух соседних пиксельных столбцов k и k+1.
1. Для максимумов яркости трех уровней b_{k h₁},b_{k m₁},b_{k l₁} столбца k и максимумов яркости трех уровней b_{(k+1) h₂},b_{(k+1) m₂},b_{(k+1) l₂} столбца k+1 должно выполняться условие
  
  ( h₁= h₂ ) v ( m₁ = m₂ ) v ( l₁ = l₂ )
2. Средняя яркость столбца k должна быть меньше максимума яркости соседнего столбца k+1
  
  c(k) < c_max(k+1)
3. максимум яркости в столбце k должен быть больше удвоенного абсолютного значения разности между значениями максимумов яркости столбца k и соседнего столбца k+1
  
  c_max(k) > 2 * | c_max(k) - c_max(k+1) |
Если для данного столбца выполняются все условия связности с соседями слева и справа то граница удаляется как ложная, в противном случае выполняется ещё одна проверка. Расстояние до предыдущей (левой) границы d_k должно быть больше допустимого минимума d_min.

d_k > d_min.

d_min= 0.4 * n.

где n - высота изображения слова
В результате из списка индексов "кандидатов" W₁ удаляются индексы столбцов, которые имеют связь с соседями слева и справа, формируется конечный список индексов границ W₂ (рис.10).

Рисунок 10: изображение слова после обработки

Исходные тексты программы [ здесь ]

Литература

1: Распознавание текстовых изображений - http://ocr.apmath.spbu.ru

Evgeny S. Borisov
2008-08-09

При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.