Моделирование предобработки изображения перед распознаванием рукописного текста. Методический материал для 10-го класса

Моделирование предобработки изображения перед

распознаванием рукописного текста.

Методический материал для 10-го класса

Настоящий методический материал используется  на уроках информатики в 10-м классе и предназначен для иллюстрации практического применения при моделировании реальных систем. Разработан в развитие темы «Модели оптимального планирования» (Параграф 20 И.Г. Семакин и др., Информатика. 10 класс,М.: Бином, Лаборатория  знаний, 2014)

ВВЕДЕНИЕ

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

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

Распознавание текста является одной из задач OCR (оптического распознавания символов). Существуют два основных способа распознавания текста:

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

— Оффлайн распознавание - Работает со статической формой представления текста. Суть заключается в том, что пользователь предоставляет изображение с текстом, и система на основе существующих алгоритмов (будет далее) осуществляет его разбор.

В рамках данной работы я буду опираться на метод оффлайн распознавания.

Цель работы

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

АНАЛИЗ СУЩЕСТВУЮЩИХ РЕШЕНИЙ

Существующие решения и трудности

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

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

— Различный угол наклона слов;

— Низкое качество изображения;

— Выделение фрагментов текста на изображении;

— Сцепленность символов внутри слов

Этапы распознавания

Весь процесс можно разделить на два основных этапа:

— Предварительная обработка изображений;

— Распознавание

         В свою очередь эти этапы можно представить в виде следующей схемы:

Рисунок 1 – Последовательность шагов предобработки изображения

         Данные этапы будут разобраны в данной научной работе.

            Научная новизна

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

ПРЕДОБРАБОТКА ИЗОБРАЖЕНИЯ

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

Рисунок 2 – Исходное изображение

Вначале нам нужно привести изображение к формату “Уровни серого”. Для этого мы воспользуемся функцией пакета OpenCV, вычисляющую взвешенную сумму компонентов RGB, где каждый пиксель рассчитывается по стандартной формуле:

где  – уровень яркости пикселя

 – уровни красного, зеленого и синего пикселей.

Рисунок 3 - Изображение в формате “Уровни серого”

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

Чтобы избежать лишних шумов, нам необходимо использовать методы сглаживания. Наиболее распространенным из них является метод Гаусcа [1].

 (1)

Сигма в данном случае – это стандартное отклонение функции Гауссиана.

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

Метод пороговой бинаризации описывается следующим выражением:

 (2)

Таким образом, если интенсивность пикселя scr(x,y), выше заданного порога thresh, тогда мы присваиваем максимальное значение заданному пикселю, в противном случае устанавливаем ему значение 0.

Рисунок 4 - Пороговой бинаризации с порогом 127

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

Глобальный метод бинаризации

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

            Метод Оцу

Самый известный глобальный метод Оцу [2] отлично зарекомендовал себя в этой области. Алгоритм позволяет разделить пиксели двух классов “полезные” и “фоновые”, рассчитывая такой порог, чтобы внутриклассовая дисперсия была минимальной.

Рисунок 5 – Результат бинаризации методом Оцу

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

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

            Адаптивные методы бинаризации

В методах адаптивной бинаризации [3] значение пороговой яркости изменяется и рассчитывается на основе локальных признаков в окрестности рассматриваемого пикселя.

                Метод Ниблэка

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

, (3)

где  – локальное среднее значение яркости пикселей в окрестности точки

 – локальное среднеквадратическое отклонение (СКО) значений яркости пикселей в окрестности точки

K – коэффициент, определяемый эмпирически и учитывающий, какую часть границы объекта взять в качестве самого объекта. Значение k=-0.2 задает достаточно хорошее разделение объектов, если они представлены черным цветом, а значение k=+0.2, – если объекты представлены белым цветом.

Рисунок 6 – Результат бинаризации методом Ниблэка

Метод Sauvola

Это улучшенный метод Niblack, предотвращающий наложение шума на объект и дающий более точное отделение объекта от фона. В этом методе для обработки изображения, вместо квадратного окна, используется круглое окно радиусом R. Порог яркости в точке (x,y) рассчитывается по формуле:

 (4)

где k – положительный коэффициент, значение которого определяется эмпирически

(обычно принимается k = 0,5);

R – динамический диапазон локального СКО значений яркости пикселей.

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

Рисунок 7 – Результат бинаризации методом Савола

         Метод Вульфа

Данный метод основан на методе Sauvola и включает нормировку локального контраста и среднего значения яркости. Порог рассчитывается по следующей формуле:

где k – фиксированное значение 0.5

М – минимум серого значения изображения

R – максимальное стандартное отклонение значения серого, полученное по всем местным окрестностям

Рисунок 8 – Результат бинаризации методом Вульфа

Сравнительный анализ методов

Теперь проведем сравнительный анализ методов. Выбор метода бинаризации будет выглядеть следующим образом:

Пусть  = 0 или 1. В данном случае  – пиксель на бинаризованном изображении с координатами , полученный методом k.

 = 0 или 1. В данном случае  – пиксель на эталонном изображении, с координатами .

В обоих случаях  , , где m и n – ширина и высота изображения соответственно.

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

Для каждого метода бинаризации рассчитаем стандартные критерии качества: точность, полноту и F-меру.

Точность:

Полнота:

F-мера:

TP – количество совпавших пикселей в эталонном и бинарном изображениях.

FP – количество пикселей, выделенных на бинарном изображении как 1 вместо 0

FN – количество пикселей, выделенных на бинарном изображении как 0 вместо 1

Таблица 1 – Сравнение результатов работы методов бинаризации

Метод	Точность	Полнота	F-мера
Оцу	0.8845	0.6953	0.7785
Ниблэка	0.5183	0.6995	0.5954
Савола	0.7491	0.8104	0.7785
Вульфа	0.5714	0.7452	0.6468

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

ВЫДЕЛЕНИЕ СТРОК

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

— Строки могут изгибаться;

— Элементы различных строк могут пересекаться.

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

Рассмотрим следующие варианты выделения строк:

— Метод вертикальных проекций.

— Сегментированный метод вертикальных проекций

— Улучшенный метод ближайшего соседа

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

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

Метод связных компонент

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

Суть метода связных компонент заключается в том, что мы проходим по всем пикселям изображения матрицей размером 3х3, значения которой соответствуют 1 или 0, в зависимости от цвета пикселя. Когда данная матрица встречает пиксель, равный 1, она проверяет его область на наличие схожих пикселей и принимает решение о создании объекта. В случае с вариантом 8-бит, мы проверяем все пиксели по диагоналям, вертикали и горизонтали.

Рисунок 8 – Метод связных компонент 8 бит

В варианте 4-бит, мы проверяем лишь вертикальные и горизонтальные пиксели.

Рисунок 9 – Метод связных компонент 4 бит

Мы же будем пользоваться 8 битным методом, в виду изгибов наших символов. Воспользовавшись библиотекой skimage.measure, мы получим следующую разметку наших объектов:

Рисунок 10 – Реализация метода связных компонент

         На основе данного метода, в дальнейшем мы будем объединять строки и слова.

Метод вертикальных проекций

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

Рисунок 11 – Тестовое изображение

Рисунок 12 – Гистограмма метода вертикальных проекций

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

Рисунок 13 – Гистограмма сглаженного метода вертикальных проекций

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

         В результате мы получим следующий результат:

        

         Рисунок 14 – Пример извлечения строк

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

Сегментированный метод вертикальных проекций

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

Рисунок 16 – Пример разметки строк сегментированным методом вертикальных проекций

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

Улучшенный метод ближайшего соседа

Идея данного метода [5] заключается в построении всех возможных связей между символами и последовательном объединении символов, входящих в связи, начиная со связей с наименьшим расстоянием.

Алгоритм выглядит следующим образом:

1.     Находятся такие пары объектов, что угол между линией, соединяющей первый объект со вторым, и линией, параллельной оси , не больше максимального и не меньше минимального углов (-28<α<20), а расстояние по горизонтали между объектами не превышает максимального(10)

2.     Связи упорядочиваются по возрастанию расстояний между объектами

3.     Каждый объект помещается в отдельную строку

4.     Для каждой связи проверяются следующие условия:

4.1.  Если для первого объекта не задан следующий за ним объект, а для второго не задан предыдущий, то объединим строки

4.2.  Если объекты соединить нельзя, найдем вертикальное расстояние между объектами, и если данное расстояние меньше минимального, то объединим строки

4.3. Символы в строке упорядочиваются по горизонтальным координатам центров символов

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

·        Центр символа заглавной буквы значительно выше центра следующего символа

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

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

Сравнительный анализ методов

     Сравнительный анализ проводился на экспериментальной базе IAM Handwriting Database(43 изображения). Основным сравнительным качеством данных методов будем считать – количество верно отнесенных объектов к строке(q), ко всем символам(v).

Таблица 2 – Сравнение результатов работы методов сегментации строк

Метод	F	Q	V
Метод вертикальных проекций	0.821	1693	2061
Сегментированный метод вертикальных проекций	0.861	1775	2061
Улучшенный метод ближайшего соседа	0,915	1887	2061

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1.     Gaussian Smooth // Сглаживание Гауссиана : веб-учебник. URL: http://homepages.inf.ed.ac.uk/rbf/HIPR2/gsmooth.htm

2.     Метод Оцу // бесплатная онлайн энциклопедия. URL: https://ru.wikipedia.org/wiki/Метод_Оцу

3.     IAM Handwriting database // Свободная база данных английского рукописного текста : веб-сайт. URL: http://www.fki.inf.unibe.ch/databases/iam-handwriting-database

4.     Rashmi Saini, Engineering College. Document Image Binarization Techniques, Developments and Related Issues: A Review// International Journal of Computer Applications (0975 – 8887), Volume 116 – No. 7, April 2015

5.     Jesper Dürebrandt, Segmentation and Beautification of Handwriting using Mobile Devices// UPTEC F 15016 Examensarbete 30 hp April 2015

6.     Гиппиев М.Б., Жуков А.В., Рогов А.А., Скабин А.В. Распознавание строк в стенографических документах // Современные проблемы науки и образования. – 2013. – № 4.

7.     Vassilis Papavassiliou, Themos Stafylakis, Vassilis Katsouro, and George Carayannis. Handwritten document image segmentation into text lines and words. Pattern Recognition, 43:369–377, 2010.

8.     Bastien Moysset and Christopher Kermorvant. On the evaluation of handwritten text line detection algorithms. 12th International Conference on Document Analysis and Recognition (ICDAR), pages 185–189, 2013.

9.     Fei Yin et al. Handwritten Text Line Segmentation by Clustering with Distance Metric Learning. Proceedings of 11th International Conference on Frontiers in Handwriting Recognition, 2008.

10. Meng-Ling Feng and Yap-Peng Tan. Contrast adaptive binarization of low quality document images. IEICE Electronics Express, Vol.1, No. 16,501-506.

ПРИЛОЖЕНИЕ А

Листинги подпрограмм предобработки изображения

А.1 Листинг подпрограммы метода вертикальных проекций

def VPP(img):

    arr = []

    i = 0

    chislo = 0

    for y in range(img.shape[0]):

        for x in range(img.shape[1]):

            if (img[y,x] == 0):

                chislo = chislo + 1

        arr.append(chislo)

        chislo = 0

    y = np.array(arr)

    x = np.array(range(img.shape[0]))

    y_new = savgol_filter(y, 23, 3)

    plt.plot(x,y_new, color='green')

    return x,y_new

A.2 Листинг подпрограммы поиска точек максимума

def find_extrems(x, y):

    ind = argrelextrema(y, np.greater)

    x_dots = x[ind]

    y_dots = y[ind]

    max = DeleteExtrems(y_dots)

    x_dots,y_dots = DeleteMassive(x_dots,y_dots,max)

    for i in sorted(x_dots):

        binarize[i, :] = 1

    plt.plot(x_dots, y_dots, 'o')

    return x_dots

A.3 Листинг подпрограммы бинаризации методом Оцу

def binary(image):

    blur = cv2.GaussianBlur(image,(3,3),0)

    img = cv2.threshold(blur,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)[1]

    return img

A.4 Листинг подпрограммы метода связных компонент

def CC(img,BinImage)

labImage = label(BinImage, connectivity=2, background=1)

LabeledImage = label2rgb(labImage, image=img)

return LabledImage

А.5 Листинг подпрограммы расчета метрик качества

def TruePositive(etalon,binarize):

    _TruePositive = 0

    for y in range(etalon.shape[1]):

        for x in range(etalon.shape[0]):

            if (etalon[x,y][0] == binarize[x,y][0]):

                _TruePositive = _TruePositive + 1

    return _TruePositive

def FalsePositive(etalon,binarize):

    _FalsePositive = 0

    for y in range(etalon.shape[1]):

        for x in range(etalon.shape[0]):

            if (etalon[x,y][0] == 255):

                if(binarize[x,y][0] == 0):

                   _FalsePositive = _FalsePositive + 1

    return _FalsePositive

def FalseNegative(etalon,binarize):

    _FalseNegative  = 0

    for y in range(etalon.shape[1]):

        for x in range(etalon.shape[0]):

            if (etalon[x,y][0] == 0):

                if (binarize[x,y][0] == 255):

                    _FalseNegative = _FalseNegative + 1

    return _FalseNegative

def criterias(binarize,etalon):

    Precision = float(TruePositive(etalon,binarize))/(float(TruePositive(etalon,binarize))+float(FalsePositive(etalon,binarize)))

    Recall = float(TruePositive(etalon,binarize))/(float(TruePositive(etalon,binarize))+float(FalseNegative(etalon,binarize)))

    F = 2 * (Precision * Recall)/(Precision + Recall)

    return Precision,Recall,F

А.6 Листинг подпрограммы проверки входимости элемента

def SearchInsight(mas):

    for first in mas:

        y1min, x1min, y1max, x1max = first.bbox

        for second in mas:

            y2min, x2min, y2max, x2max = second.bbox

            if (y2min > y1min and x2min > x1min and y2max < y1max and x2max < x1max):

                mas.remove(second)

                SearchInsight(mas)

    Return

А.7 Листинг подпрограммы выделения строк методом вертикальных проекций

def Extract_Lines():

for i in lines:

        Max_Y = 0

        Min_Y = 10000

        for j in i:

            y1, x1, y2, x2 = j.bbox

            if (Max_Y < y2):

                Max_Y = y2

            if (Min_Y > y1):

                Min_Y = y1

        for i in range(binarize.shape[1]):

               y = Min_Y

               while (y < Max_Y):

                   if (binarize[y][i] == 0):

                       etaln[y][i] = currentColor

                   y += 1

        currentColor = RandomColor(currentColor)

        img = binarize[Min_Y:Max_Y,0:binarize.shape[1]]

        cv2.imwrite(str(count) + '.png',img)

        count += 1

 return

A.8 Листинг подпрограммы отнесения объекта к строке

Def EditLines(x_dots,props):

lines = []

for i in range(len(x_dots)):

    lines.append([])

    for j in props:

        if (math.fabs(j.centroid[0] - x_dots[i]) < median):

            lines[i].append(j)

return lines

Краткое описание документа:

Настоящий методический материал используется на уроках информатики в 10-м классе и предназначен для иллюстрации практического применения при моделировании реальных систем. Разработан в развитие темы «Модели оптимального планирования» (Параграф 20 И.Г. Семакин и др., Информатика. 10 класс,М.: Бином, Лаборатория знаний, 2014)