Евгений Борисов
суббота, 9 августа 2008 г.
При рассмотрении задачи оптического распознавания текста (OCR) возникает проблема сегментации символов или выделения изображений отдельных символов на картинке с изображением текста. В этой статье предлагается решение такой задачи сегментации, основанное на работе [1].
В данном случае мы предполагаем, что изображение текста правильно ориентированно, т.е. строки ровные и картинка не повёрнута относительно наблюдателя (рис.1).
Сегментацию изображения текста будем проводить в три этапа:
Будем рассматривать изображение текста в градациях серого. Исходное изображение можно представить как матрицу яркостей точек B
0≤bij≤bmax
i=1... n ; j=1... m
Для определённости будем считать, что максимальное значение яркости (bmax ) соответствует чёрному цвету а минимальное (равное 0) - белому.
Задача выделения строк сводиться к нахождению верхних и нижних граней строк текста, изображённого на исходной картинке.
Алгоритм сегментации строк основывается на том, что средняя яркость в изображениях межстрочных промежутках существенно ниже средней яркости в изображениях текстовых строк.
Работа алгоритма сегментации строк заключается в последовательном просмотре массива средних значений (s1,...,sm) и выявлении множества пар индексов (sti,sbi) пиксельных строк, соответствующих верхней sti и нижней sbi граням изображения строки номер i, удовлетворяющих следующим условиям.
Начало текстовой строки или области устойчивого повышения яркости фиксируется, если выполняется следующий комплекс условий:
т.е. в пиксельной строке с номером i начинается изображение текстовой строки если
Конец области устойчивого повышения яркости определяется, если выполняется следующие условия:
Или:
т.е. в пиксельной строке с номером i заканчивается изображение текстовой строки, если ранее было определено, что строка началась, и выполняется условие
В результате формируется множество пар индексов верхних и нижних граней строк. Разность между этими индексами дает высоты текстовых строк. Однако такой алгоритм находит среднюю высоту каждой текстовой строки и "срезает" символы, выступающие по высоте за эту среднюю высоту.
Чтобы избежать этого, необходимо расширить найденные границы. Можно предложить следующий алгоритм расширения границ. Среди найденных текстовых строк определяется строка с минимальной высотой Hmin и, затем все границы с каждой стороны расширяются на величину 0.3 * Hmin. Это не приводит к слиянию строк, т.к. межстрочные интервалы текста, как правило, больше чем высота строки (рис.2).
Таким образом, в результате работы алгоритма на исходном изображении отмечается положение всех текстовых строк.
На втором этапе решения задачи сегментации изображения текста, из изображений строк. Входом для алгоритма сегментации слов служит изображение, какой либо одной текстовой строки, которое получается из исходного изображения документа после применения к нему алгоритма сегментации строк (рис.3).
Для улучшения качества работы алгоритма выделения слов из строки вначале его работы выполняются два преобразования входного изображения.
где i=1... n ; j=1... m ; b0 - порог яркости
Такое преобразование, при правильно выбранном пороге b0, помогает снизить уровень шума, т.е. убрать значительное количество лишних точек (рис.4).
В результате такого преобразования близкие точки объединяются в непрерывную область и вместо множества маленьких точек получаем картинку состоящую из нескольких сплошных пятен с достаточно чёткой границей (рис.5).
Далее выполняем собственно процедуру сегментации. Алгоритм сегментации слов основывается на том, что средняя яркость в межсловных интервалах существенно ниже средней яркости в изображениях слов. Он похож на алгоритм сегментации строк, только просмотр идет по пиксельным столбцам изображения строки.
где m, - высота текущей строки в точках
где n, - ширина текущей строки в точках
Работа алгоритма сегментации слов заключается в последовательном просмотре множества средних значений яркости столбцов (c1,...,cn) и выявлении множества пар индексов (cli,cri) пиксельных строк, соответствующих левой cli и правой cri граням изображения слова номер i, удовлетворяющих следующим условиям (рис.6).
Начало слова или области устойчивого повышения яркости фиксируется, если выполняются следующие условия;
т.е. в пиксельном столбце с номером
j
начинается изображение слова если
Конец области устойчивого повышения яркости определяется, если выполняются следующие условия;
т.е. слово заканчивается в пиксельном столбце с номером
j ,
если ранее
было определено, что слово началось, и выполняется условие
В большинстве изображений слов символы расположены близко друг к другу и межсимвольные интервалы не так ярко выражены, как в случае межстрочных или межсловных интервалов (рис.7). Поэтому алгоритм сегментации символов сложнее и не так очевиден как рассмотренные ранее алгоритмы сегментации строк и слов.
Входом для алгоритма сегментации символов служит изображение, какого либо слова, которое получается из изображения текстовой строки после применения к нему алгоритма сегментации слов.
Алгоритм сегментации символов основывается на том, что средняя яркость в межсимвольных интервалах, по крайней мере, ниже средней яркости в изображениях символов. Его (алгоритма сегментации) общая схема состоит из двух основных частей.
Конечная цель работы - найти индексы столбцов-границ между символами.
Поиск локальных минимумов средней яркости столбцов
ci
происходит на смежных
интервалах изменения индекса столбца.
Размер интервала выбирается исходя из высоты строки.
Для большинства шрифтов отношение ширины символа к его высоте не превышает
величину
0.3. Поэтому размер интервала выбран
Поиск минимумов работает следующим образом.
где m - высота слова в точках.
Удаление ложных межсимвольных границ будем проводить в несколько этапов.
Первое условие межсимвольных границы можно записать в следующем виде.
В результате из списка индексов локальных минимумов W0 удаляются индексы столбцов, средняя яркость которых не удовлетворяет этому условию, формируется второй список W1 индексов-"кандидатов" в межсимвольные границы (рис.9).
Сформулируем условия связности двух соседних пиксельных столбцов k и k+1.
Если для данного столбца выполняются все условия связности с соседями слева и справа то граница удаляется как ложная, в противном случае выполняется ещё одна проверка. Расстояние до предыдущей (левой) границы dk должно быть больше допустимого минимума dmin.
В результате из списка индексов "кандидатов" W1 удаляются индексы столбцов, которые имеют связь с соседями слева и справа, формируется конечный список индексов границ W2 (рис.10).
Исходные тексты программы [ здесь ]