Фан_Ногк_Хоанг_Диссертация. Алгоритмы обработки и анализа символов вейвлетпреобразованием, методом главных компонент и нейронными сетями

• Название: Алгоритмы обработки и анализа символов вейвлетпреобразованием, методом главных компонент и нейронными сетями
• Дата: 13.10.2022
• Размер: 3.2 Mb.
• Имя файла: Фан_Ногк_Хоанг_Диссертация.pdf
• Тип: Диссертация; #732105
• страница: 3 из 7

Глава 2.
Применение вейвлет-преобразования,
метода главных компонент и нейронных сетей для
распознавания символов и фрагментов печатных
текстов
В данной главе предложен и описан способ построения классификатора для распознавания символов, основанный на нейронных сетях. Разработан и описан алгоритм распознавания символов, основанный на вейвлет- преобразовании, методе главных компонент и нейронных сетях. Создан и описан алгоритм распознавания фрагментов текстов, основанный на разработанном алгоритме распознавания символов и способе выделения символов из фрагмента текста.
2.1
Предложенный алгоритм распознавания
символов
Распознавание образов является одной из самых изученных задач в таких областях как цифровая обработка изображений, компьютерное зрение, биометрия, создание интеллектуальных систем безопасности и контроля доступа и т.п. Тем не менее, в области распознавания образов продолжают представлять большой научный и практический интерес такие задачи как распознавание лиц, жестов, отпечатков пальцев, печатных и рукописных символов, печатных текстов и т.д.
В данной главе предложен новый алгоритм распознавания символов, основанный на вейвлет-преобразовании, методе главных компонент и многослойных нейронных сетях. Алгоритм распознавания символов работает следующим образом.
Шаг 1. Обучение нейронных сетей.
Шаг 1.1. Выделение характерных признаков символов из обучающей выборки на основе применения вейвлет-преобразования.
Шаг 1.2. Уменьшение размерности векторов выделенных признаков методом главных компонент.

43
Шаг 1.3. Обучение нейронных сетей полученными векторами выделенных признаков символов.
Шаг 2. Распознавание символа.
Шаг 2.1. Выделение характерных признаков распознаваемого символа из тестовой выборки на основе применения вейвлет- преобразования.
Шаг 2.2. Уменьшение размерности вектора выделенных признаков методом главных компонент.
Шаг 2.3. Распознавание символа обученными нейронными сетями.
2.1.1
Выделение признаков изображений символов
Главной задачей в каждом виде обработки изображения является нахождение эффективного представления, позволяющего отобразить изображение в компактной форме. В современной теории и практике обработки сигналов активно используются преобразования специального вида – вейвлеты, показавшие свою эффективность в спектральном анализе сигналов [10, 95].
Вейвлет-преобразования успешно применяются для извлечения признаков изображений при решении таких задач как классификация изображений текстур [28, 35, 67, 75, 96], классификация изображений объектов, таких как: здание, рыба, трава, люди, автомобиль, самолет, помидор, яблоко и т.д. [5, 14, 16, 51, 82, 90, 109, 113].
Кроме этого, комбинация вейвлет-преобразования и МГК показала свою эффективность для решения задач распознавания образов. В работах [7,
8] предложен алгоритм, основанный на методе Виолы-Джонса, вейвлет- преобразовании и МГК для распознавания множества лиц на изображениях и видеопоследовательностях. Результаты проведенных экспериментов на основе этого алгоритма показали, что точность распознавания составляет

98,4%.
В работе [15] предложен алгоритм, основанный на алгоритме CAMShift,

44 методе Виолы-Джонса, вейвлет-преобразовании и МГК для распознавания жестов на видеопоследовательности. Точность результата распознавания этого алгоритма составляет

94,6%.
Скорость обработки указанных двух алгоритмов достаточно быстрая,
7–14 кадров в секунду для алгоритма распознавания множества лиц, 25–30 кадров в секунду для алгоритма распознавания жестов. Эта скорость позволяет программам, реализованным на основе разработанных алгоритмов, работать в режиме реального времени.
В работах [7, 8, 15] проводилось исследование зависимости эффективности результатов распознавания лиц и жестов от типа вейвлетов и показано, что при использовании комбинации вейвлет-преобразования Хаара и МГК получены наилучшие результаты распознавания. Кроме того, для вейвлет-преобразования Хаара характерны простота реализации и высокая скорость вычисления [12, 13].
Таким образом, можно сделать вывод о целесообразности применения вейвлет-преобразования Хаара и МГК для решения задач распознавания символов и фрагментов печатных текстов с приемлемой скоростью обработки.
Вейвлет Хаара является базисным вейвлет-преобразованием, с помощью которого можно разложить одномерный дискретный сигнал
1 2
( ,
,...,
)
N
f
f
f
f

на два компонента равного размера. Первый компонент называется средним или аппроксимацией (approximation), а второй – различием (difference) или детализацией (detail). Значения среднего подсигнала
1 1
2
/2
( ,
,...,
)
N
a
a a
a

на первом уровне разложения вычисляются по следующей формуле [6]:
2 1
2
,
1,2,3,...,
/ 2,
2
n
n
n
f
f
a
n
N




(2.1) а значения детализирующего подсигнала
1 1
2
/2
( ,
,...,
)
N
d
d d
d

на этом же уровне разложения определяются следующим образом:

45 2
1 2
,
1,2,3,...,
/ 2.
2
n
n
n
f
f
d
n
N




(2.2)
В результате получаются два новых сигнала:
{
}
n
a
a

и
{
},
1,...,
/ 2
n
d
d
n
N


. Первый сигнал является огрубленной версией исходного дискретного сигнала. Во втором сигнале содержится информация, необходимая для восстановления исходного дискретного сигнала.
2 1
,
2
n
n
n
a
d
f



(2.3)
2 2
n
n
n
a
d
f


(2.4)
Рассмотрим простой пример для того, чтобы понять как работает двумерное вейвлет-преобразование Хаара. Пусть имеется следующий двумерный сигнал
1 2
3 4
4 3
2 1
5 6
7 8
8 7
6 5
I













При применении одномерного вейвлет-преобразования Хаара к первой строке, значения коэффициентов аппроксимации вычисляются по формуле
(2.1)
1 2
1 2 3 4
и
,
2 2
a
a




а значения коэффициентов различия вычисляются по формуле (2.2)
1 2
1 2 3 4
и
2 2
d
d




Аналогично к остальным строкам матрицы I применяется одномерное вейвлет-преобразование Хаара. В результате получается новая матрица, первые два столбца которой содержат значения коэффициентов аппроксимации каждой строки, а последующие два столбца – значения коэффициентов различия.

46 одномерное преобразование
Хаара на строках
1 2
3 4
3 7
:
1 1
4 3
2 1
7 3
:
1 1
1 5
6 7
8 11 15 :
1 1
2 8
7 6
5 15 11 :
1 1





























Затем к столбцам полученной матрицы применяется одномерное вейвлет-преобразование Хаара. В результате получается преобразованная матрица первого уровня. одномерное преобразование
Хаара на столбцах
5 5
:
0 0
3 7
:
1 1
13 13
:
0 0
7 3
:
1 1
1 11 15 :
1 1
2 2
2
:
1 1
15 11 :
1 1
2 2
:
1 1













  























Преобразованная матрица делится на четыре подматрицы
5 5
0 0
2 2
1 1
,
,
и
13 13 0
0 2
2 1
1
LL
HL
LH
HH


































Таким образом, двумерное вейвлет-преобразование Хаара состоит из поочередного применения одномерного вейвлет-преобразования Хаара к строкам и столбцам этой матрицы. В результате исходное изображение делится на четыре подматрицы (квадранта) равного размера. На рис. 2.1 представлены четыре квадранта преобразованного изображения со стандартными обозначениями: LL, LH, HL и HH. Квадрант LL содержит низкочастотные вейвлет-коэффициенты, HH – высокочастотные вейвлет- коэффициенты (буква L означает Low и буква H – High) [18].
Рисунок 2.1.
Полученные квадранты при применении вейвлет-
преобразования

47
Процесс выделения признаков символа происходит следующим образом. Вначале область, содержащая символ, приводится к размеру 64×64 пикселя. Затем к полученному изображению применяется вейвлет- преобразование и извлекаются низкочастотные вейвлет-коэффициенты. В результате получается матрица, состоящая из 32×32 низкочастотных вейвлет- коэффициентов.
Для того чтобы выделить локальные характерные признаки символа, его изображение делится на 12 частей с одинаковым размером 32×32 пикселя
(рис. 2.2). Затем к каждой части применяется вейвлет-преобразование и извлекаются низкочастотные вейвлет-коэффициенты.
В результате получаются 12 матриц, каждая из которых состоит из 16×16 низкочастотных вейвлет-коэффициентов.
После этого составляется вектор характерных признаков символа, элементами которого являются все низкочастотные вейвлет-коэффициенты, полученные на предыдущих шагах. В результате получается вектор характерных признаков символа
I

, состоящий из 32×32 + 12×16×16 = 4096 элементов (рис. 2.2).
Рисунок 2.2.
Выделение характерных признаков символа «A»

48
2.1.2
Уменьшение размерности вектора признаков
Перед подачей на входы нейронных сетей размерность вектора
признаков уменьшается. Для решения этой задачи предлагается использование метода главных компонент (МГК).
МГК был создан с целью уменьшения размерности векторов признаков, которые используется для решения задачи распознавания образов.
При решении задачи распознавания лиц, используются главные компоненты распределения лиц, представляющие собой собственные векторы ковариационной матрицы набора соответствующих изображений. Эти собственные векторы можно рассматривать как набор характерных признаков изображений лиц, их можно представить как некое приближение к изображению лица [11]. Эти векторы принято называются собственными лицами (eigenfaces).
МГК также является одним из распространенных и эффективных методов выделения признаков, предназначенных для решения задач распознавания образов. В работах [29, 31, 64, 83, 102, 103, 112, 117] МГК показал свои работоспособность, эффективность и надежность при решении задачи распознавания лиц. В работе [81] показано, что при распознавании лиц использование комбинации вейвлет-преобразования и МГК для извлечения признаков изображений эффективнее, чем использование только вейвлет-преобразования или использование только МГК.
Уменьшение размерности вектора признаков символа на основе МГК происходит следующим образом. Вначале создается пространство собственных символов, используя набор М изображений символов. При этом
М намного меньше 4096. Создание пространства собственных символов выполняется следующим образом.
К каждому из М изображений применяется разработанный способ выделения характерных признаков. В результате получается набор векторов признаков
1
,...,
M
I
I


. Затем составляется средний вектор, значение каждого элемента которого по всем М векторам признаков вычисляется по формуле:

49 ср
1 1
M
n
n
I
I
M





(2.5)
Далее из каждого вектора признаков вычитается средний вектор ср
,
1,...,
n
n
Ф
I
I
n
M
 




(2.6)
После этого создается пространство, состоящее из K собственных векторов
k
u

ковариационной матрицы C, которые наилучшим образом описывают распределение значений М векторов признаков (K<M)
1 1
1
,
{
,...,
}.
M
T
T
n
n
M
n
C
Ф Ф
AA
A
Ф
Ф
M





 


(2.7)
При этом k-ый вектор
k
u

удовлетворяет условию максимизации следующего выражения:
2 1
1
(
)
M
T
k
k
n
n
u Ф
M






(2.8) и условию ортогональности:
1,
0, иначе
T
l
k
l
k
u u


 

 
(2.9)
Векторы
k
u

и величины
k

представляют собственные векторы и собственные значения ковариационной матрицы C.
Для создания этого пространства вначале нужно вычислить M собственных векторов
l
u

матрицы C с использованием векторов
i
v

, являющихся собственными векторами матрицы
T
L
A A

. Каждый вектор
l
u

вычисляется по следующей формуле:
1 1
,
1,
,
M
l
lk
k
k
u
v Ф l
M
M






(2.10)
Затем из M полученных векторов выбираются K собственных векторов, имеющих наибольшие собственные значения. Пространством собственных символов является набор выбранных K собственных векторов (рис. 2.3).
Значение K определяется эмпирическим способом.

50
Рисунок 2.3.
Создание пространства собственных символов
После того как создано пространство собственных символов, уменьшение размерности вектора характерных признаков символа вх
I

осуществляется следующим образом.
Вначале вектор признаков символа разлагается по K имеющимся собственным символам
i
u

и вычисляются соответствующие коэффициенты разложения, определяющиеся по формуле: вх ср
(
),
1,..., .
T
i
i
w
u
I
I
i
K






(2.11)
Затем составляется вектор, описывающий вклад каждого собственного символа в представление входного вектора признаков символа:
1
{ ,...,
}.
T
K
w
w
 

(2.12)
В результате уменьшения размерности получается новый вектор признаков символа


, состоящий из K элементов. При этом K намного меньше 4096 (рис. 2.4).
Рисунок 2.4.
Уменьшение размерности вектора признаков символа

51
2.1.3
Распознавание символов нейронными сетями
В качестве классификатора предлагается использование многослойных нейронных сетей, поскольку они обеспечивают высокую скорость и точность распознавания [55]. В работе [58] предложен алгоритм распознавания лиц, основанный на многослойных нейронных сетях. На основе идеи этого алгоритма в данной диссертации предложен способ построения
классификатора для распознавания символов на основе многослойных нейронных сетей.
Особенностью данного подхода является создание для каждого символа обучающей выборки специальной нейронной сети, обучаемой алгоритмом с обратным распространением ошибки. Входом каждой нейронной сети является вектор характерных признаков


(K элементов).
Количество нейронов скрытого слоя равно 70% количества нейронов входного слоя. Выходной слой имеет только один нейрон, возвращающий значение в пределах от 0 до 1. Использование специальной нейронной сети для каждого символа обучающей выборки позволяет ускорить процесс обучения нейронной сети. Структура специальной нейронной сети представлена на рис. 2.5.
Рисунок 2.5.
Структура специальной многослойной нейронной сети

52
Каждая нейронная сеть определяет степень близости распознаваемого символа к только одному из символов обучающей выборки. Распознавание входного символа нейронными сетями происходит следующим образом.
Вначале извлекается вектор признаков символа и уменьшается его размерность. Затем полученный вектор признаков подается на входы всех обученных нейронных сетей. Входной символ распознается как символ обучающей выборки, нейронная сеть которого возвращает наибольшее значение (рис. 2.6).
Кроме того, использование специальной нейронной сети для каждого символа обучающей выборки обеспечивает возможность рассмотрения второго варианта результата распознавания. Вторым предположением является символ обучающей выборки, нейронная сеть которого возвращает второе наибольшее значение. Преимущество рассмотрения двух вариантов распознавания проявляется в случае распознавания похожих по написанию символов, таких как {c, C}, {o, O}, {p, P}, {s, S}, {u, U}, {v, V}, {w, W}, {x,
X} и {z, Z} (рис. 2.6).
Рисунок 2.6.
Распознавание символа нейронными сетями
2.2
Предложенный алгоритм распознавания
фрагментов печатных текстов
Для выполнения процесса распознавания фрагмента печатного текста необходимо решить задачу выделения символов из блока текста. Эти выделенные символы являются входами процесса распознавания символов.

53
На основе разработанного алгоритма распознавания символов, в данной диссертации предложен новый алгоритм распознавания
фрагментов печатных текстов. Алгоритм состоит из следующих шагов.
Шаг 1. Выделение символов из фрагмента текста.
Шаг 1.1. Поворот наклонного изображения фрагмента текста.
Шаг 1.2. Выделение строк из фрагмента текста.
Шаг 1.3. Выделение слов из строк.
Шаг 1.4. Выделение символов из слов.
Шаг 2. Распознавание выделенных символов.
Шаг 2.1. Извлечение характерных признаков выделенных символов на основе применения вейвлет-преобразования.
Шаг 2.2. Уменьшение размерности векторов извлеченных признаков методом главных компонент.
Шаг 2.3. Распознавание символов обученными нейронными сетями.
2.2.1
Выделение символов из фрагмента текста
В рамках данной диссертационной работы, главной задачей является эффективность распознавания символов фрагмента печатного текста. Таким образом, в данной работе не рассматриваются задача выделения таблиц, блоков текста и изображений из содержания документа, а также задача выделения абзацев из блока текста. В работе [98] проведен обзор различных методов сегментации символов, таких как White Space and Pitch (WSP),
Projection Analysis (PA), Connected Component Analysis (CCA) и других и показано, что метод PA является эффективным, простым и быстрым для выделения печатных символов. Предполагается, что имеется бинарное изображение фрагмента текста. Процесс выделения символов из фрагмента текста осуществляется следующим образом.
Шаг 1. Поворот наклонного изображения фрагмента текста:
Символы, использующиеся при обучении, расположены вертикально в горизонтальных строках. Однако, при сканировании строки фрагмента текста могут быть расположены не горизонтально. Таким образом, для того чтобы

54 горизонтально расположить строки изображение фрагмента текста необходимо повернуть. Для решения этой задачи используется проекция изображения на ось Y (рис. 2.7).
Рисунок 2.7.
Пример наклонного текста и его проекция на ось Y
Вводятся следующие термины для горизонтальной проекции: «белая строка» – строка, на которой нет ни одной черной точки; «черная строка» – строка, на которой расположена хотя бы одна черная точка. Поворот изображения фрагмента текста заключается в нахождении повернутого изображения, проекция которого имеет наибольшее количество «белых строк». Пример результата поворота наклонного изображения фрагмента текста представлен на рис. 2.8.
Рисунок 2.8.
Пример результата поворота наклонного текста: а, б)
исходное изображение текста и его проекция на ось Y; в, г) повернутое
изображение и его проекция на ось Y

55
Шаг 2. Выделение строк: На этом шаге строки фрагмента текста выделяются на основе использования проекции повернутого изображения на ось Y, полученного на первом шаге. Область строки определяется последовательностью только «черных строк». Верхняя и нижняя границы строки определяются относительно этой области. Пример выделения строк фрагмента текста представлен на рис. 2.9.
Рисунок 2.9.
Результат выделения строк проекцией на ось Y
Шаг 3. Выделение слов: На этом шаге слова каждой из строк, полученных во втором шаге, выделяются на основе применения проекции этой строки на ось X (рис. 2.10).
Вводятся следующие термины для вертикальной проекции: «белый столбец» – столбец, на котором нет ни одной черной точки; «черный столбец» – столбец, на котором расположена хотя бы одна черная точка. На основе результатов эмпирического способа «пробел» в строке определяется последовательностью только «белых столбцов», количество которых больше чем 8. Области слов выделяются на основе информации о полученных пробелах. Левая и правая границы слов определяются в соответствии с этими областями. Пример результата выделения слов в строке представлен на рис.
2.10.

56
Рисунок 2.10.
Результат выделения слов строки проекцией на ось Х
Шаг 4. Выделение символов: На этом шаге выделяются символы каждого из слов, полученных на третьем шаге. Для описания алгоритма, вводится следующий термин: «соединяющийся столбец» – столбец, на котором расположена последовательность черных точек, количество которых больше или равно 1, соединяющаяся с черными точками соседних столбцов.
Примеры этих «соединяющихся столбцов» представлены на рис. 2.11
Рисунок 2.11.
Примеры «соединяющихся столбцов»
Выделение символов из слова осуществляется следующим образом.
Вначале слово сканируется слева-направо и обнаруживается первая

57 последовательность «соединяющихся столбцов». Затем определяются левая и правая границы возможной области первого символа. Полученная возможная область сканируется сверху-вниз и Y-координата первой черной точки является верхней границей области символа. Затем полученная область сканируется снизу-вверх и Y-координата первой черной точки является нижней границей области символа. Сканирование слова слева-направо продолжается, пока все содержащиеся в нем символы не будут выделены.
Пример выделения символов слов «Recipe:» представлен на рис. 2.12.
Рисунок 2.12.
Пример выделения символов слова «Recipe:»
2.2.2
Распознавание фрагмента текста
Таким образом, процесс распознавания фрагмента текста состоит из двух шагов. Вначале выделяются символы из фрагмента текста (раздел 2.2.1) и в результате получается набор областей выделенных символов. Затем каждый из выделенных символов распознается с использованием процесса распознавания символов (раздел 2.1).
Распознавание каждого выделенного символа происходит следующим образом. Вначале извлекается вектор характерных признаков символа. Затем осуществляется сокращение размерности извлеченного вектора признаков.
Полученный вектор с меньшей размерностью подается на входы обученных

58 нейронных сетей для распознавания выделенного символа. Схема процесса распознавания фрагмента печатного текста представлена на рис. 2.13.
Рисунок 2.13.
Схема процесса распознавания печатных текстов
2.2.3
Распознавание похожих по написанию символов
Существуют похожие по написанию символы, такие как {c, C}, {o, O},
{p, P}, {s, S}, {u, U}, {v, V}, {w, W}, {x, X} и {z, Z}. Эти символы зачастую неправильно распознаются. На рис. 2.14 приведен пример представления букв «s», «S» после того как размеры их изображений увеличиваются до одинакового размера 64×64 пикселя. Таким образом, при распознавании фрагмента печатного текста необходимо выполнить дополнительный процесс отдельного распознавания похожих по написанию символов.
Рисунок 2.14.
Изображения области букв «s», «S» и их представления
после увеличения размера до 64×64 пикселя
Строки текста обычно содержат следующие характеристики: верхняя, главная, основная и нижняя границы; верхняя, средняя и нижняя области

59
(рис. 2.15).
Рисунок 2.15.
Характеристики строки текста
Таким образом, области символов можно разделить на четыре типа, примеры которых представлены на рис. 2.16. Первым типом является область символа, имеющая верхнее и нижнее свободное пространство. Область символа второго типа содержит только верхнее свободное пространство, а область символа третьего типа имеет только нижнее свободное пространство.
Четвертым типом является область символа, которая не имеет ни верхнего, ни нижнего свободного пространства.
Для вышеперечисленных похожих по написанию символов создается дополнительное пространство собственных символов и соответствующие им нейронные сети. Процесс распознавания фрагмента печатного текста с учетом отдельного распознавания похожих по написанию символов осуществляется следующим образом.

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

61
2.3
Основные результаты и выводы по главе 2
В данной главе приведено подробное описание предложенного способа построения классификатора для распознавания символов, реализованного алгоритма распознавания символов и разработанного алгоритма распознавания фрагментов печатных текстов.
Впервые предложен способ построения классификатора для распознавания символов, основанный на многослойных нейронных сетях.
Особенностью данного подхода является создание для каждого символа обучающей выборки специальной нейронной сети, обучаемой алгоритмом с обратным распространением ошибки. Каждая нейронная сеть определяет степень близости распознаваемого символа к только одному из символов обучающей выборки.
Разработан новый алгоритм распознавания символов, основанный на вейвлет-преобразовании, методе главных компонент и нейронных сетях. В разработанном алгоритме вейвлет-преобразование применяется для выделения признаков символов, метод главных компонент осуществляет сокращение размерности векторов признаков, а нейронные сети используются в качестве классификатора.
Создан оригинальный алгоритм распознавания фрагментов печатных текстов, основанный на способе выделения символов из фрагмента текста и разработанном алгоритме распознавания символов.

62