РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ РУКОПИСНЫХ СИМВОЛОВ НА ОСНОВЕ СОРТИРОВКИ ПОЛЯРНЫХ КООРДИНАТ - Студенческий научный форум

V Международная студенческая научная конференция Студенческий научный форум - 2013

РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ РУКОПИСНЫХ СИМВОЛОВ НА ОСНОВЕ СОРТИРОВКИ ПОЛЯРНЫХ КООРДИНАТ

Дзюба А.С. 1, Ромм Я.Е. 1
1ФГБОУ ВПО "ТГПИ имени А.П. Чехова"
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
1. Постановка вопроса. Рассматриваются рукописные буквы русского алфавита и буквы русского шрифта MS Windows, близкие по написанию к рукописным символам. При этом три первые буквы нарисованы одним человеком, четвертая – другим, а пятая буква является шрифтовой. Толщина букв различна или может быть одинаковой для всех образцов. Написание символов схоже, но не идентично. Фон каждого из графических файлов брался светлым, само написание буквы производилось цветом значительно более темным по отношению к фону.

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

2. Описание подхода. Решение задачи осуществляется с помощью запрограммированного алгоритма, основанного на сортировке полярных координат точек символов, – после поворота символов в положение, называемое каноническим: полярная ось направлена вдоль максимального диаметра, начало координат – в середине данного диаметра. Используется устойчивая сортировка с взаимно однозначным соответствием входных и выходных индексов, точнее, модифицированная сортировка подсчетом (ниже – просто сортировка), обладающая данным соответствием индексов [1 - 3].

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

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

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

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

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

Полученные полярные координаты упорядочиваются по возрастанию угла и сохраняются в два массива: углов и радиусов. Элементы этих двух массивов связаны друг с другом соответствием по исходному номеру точки.

Таким образом, получены числовые характеристики рукописного символа (полярные координаты, упорядоченные по возрастанию угла, и количество точек), поданного на вход в виде изображения. Числовые характеристики занесены для удобства в два массива, один из которых – массив радиусов с их входными номерами, второй – массив углов, привязанный к радиусам через ссылки индексов.

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

Всюду в дальнейшем для краткости локально экстремальные элементы именуются экстремумами (максимумами, минимумами соответственно).

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

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

Алгоритм 1

  1. Массив радиусов сортируется по возрастанию с сохранением его в новый массив типа radius. Каждый элемент нового массива сохраняет связь с изначальным его углом поворота за счет переиндексации радиусов (индекс в новом массиве означает место этого элемента в предыдущем массиве).

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

  3. Полученная выборка сортируется по возрастанию угла.

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

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

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

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

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

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

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

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

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

На третьем этапе полученная вторая выборка является входной последовательностью для нового поиска локально максимальных радиусов. Как и на предыдущем этапе, входные данные сначала сортируются по неубыванию значения и сохраняются в массив с переиндексацией. Затем осуществляется поиск из отсортированной второй выборки согласно алгоритму 1. На данном этапе количество локально максимальных радиусов составляет шесть/семь элементов. Такого количества радиусов, соответственно и их целочисленных индексов (индекс отражает порядковый номер экстремального радиуса) оказывается достаточным для составления попарно различных характеристик русскоязычных рукописных символов (6!=720; 7!=5040).

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

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

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

4.1. В перестановках конечной выборки, вырабатываемой программой п. 3.3, выделим характерное для большинства изображений устойчивое сочетание и положение индексов (далее – характеристика), однозначно определяющее конкретный рукописный символ. Точнее, выделим то сочетание в перестановке индексов, которое взаимно однозначно соответствует каждому отдельному символу в рассматриваемом множестве изображений рукописных символов.

Рассмотрим характеристики некоторых изображений символов. На рис. 1 изображена рукописная буква «а», соответственная почерку отдельно взятого человека. На этом и последующих рисунках первая строка содержит номера по порядку, – по количеству максимумов третьей выборки, образованной после трехкратного прореживания входной последовательности полярных радиусов по алгоритму 1. Вторая строка содержит перестановку порядковых номеров третьей выборки после ее сортировки по возрастанию радиусов. Третья строка содержит соответственные порядковым номерам третьей выборки значения локально максимальных радиусов, четвертая строка соответствует полярным углам данных радиусов.

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

Номера по порядку

1

2

3

4

5

6

7

Перестановка индексов

7

5

2

3

4

1

6

Экстремальные радиусы

31,427

51,213

56,405

63,167

63,632

67,537

71,345

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

356,809

238,68

117,016

196,32

202,889

56,396

334,469

Буква

 

Рис. 1. Первый вариант рукописной буквы «а», нарисованной первым человеком, и построение ее идентификаторов

Для данного и последующих изображений символа «а» (рис. 1 – 5) индекс 6 чаще всего (в трех из пяти представленных случаев) находится на последней позиции, индекс 4 находится с точностью до единицы в центре: на четвертой ±1 позиции, индекс 5 всегда рядом с точностью до единицы с индексом 2. Индекс 4 находится рядом с индексом 1 или через одну позицию от него.

На рис. 1 эти особенности содержит подстановка

(1)

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

1

2

4

5

3

6

Экстремальные радиусы

35,512

59,014

63,043

64,976

66,992

78,411

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

21,307

61,582

156,732

210,621

123,438

335,034

Буква

 

Рис. 2. Второй вариант рукописной буквы «а», нарисованной первым человеком, и построение ее идентификаторов

На рис. 2 характерные для данного символа особенности содержит подстановка

(2)

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

5

1

4

2

3

6

Экстремальные радиусы

56,368

63,38

68,343

69,613

77,514

83,688

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

0,47

352,645

239,931

104,668

309,605

65,786

Буква

 

Рис. 3. Третий вариант рукописной буквы «а», нарисованной первым человеком, и построение ее идентификаторов

На рис. 3 характерные для данного символа особенности содержит подстановка

(3)

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

1

6

4

3

5

2

Экстремальные радиусы

29,139

29,38

65,588

70,538

72,374

75,918

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

0,47

352,645

239,931

104,668

309,605

65,786

Буква

 

Рис. 4. Вариант рукописной буквы «а», нарисованной вторым человеком, и построение ее идентификаторов

На рис. 4 характерные для данного символа особенности содержит подстановка

(4)

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

6

3

5

2

4

1

Экстремальные радиусы

28,689

39,402

45,618

51,697

53,918

66,014

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

358,721

150,571

333,099

76,94

219,976

49,717

буква

 

Рис. 5. Шрифтовая буква «а» (курсив шрифта Times New Roman) и построение ее идентификаторов

На рис. 5 характерные для данного символа особенности содержит подстановка

(5)

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

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

Примером использование дополнительной характеристики «положение центра рукописного символа» можно взять буквы «а» и «т» (рис. 18 и рис. 19).

Рис. 18. Различные виды буквы «а». Положение ее центра и радиусов конечной выборки (центр находится в пересечении радиусов)

Рис. 19. Различные виды буквы «т». Положение ее центра и радиусов конечной выборки (центр находится в пересечении радиусов)

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

Примером «резкого скачка значения радиуса» можно взять букву «б» (рис. 20 – рис. 23).

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

3

2

1

6

5

4

Экстремальные радиусы

18,256

20,077

21,84

83,139

88,882

98,37

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

29,81

8,812

0,198

260,194

104,437

52,532

буква

 

Рис. 20. Первый вариант рукописной буквы «б», нарисованной первым человеком, и построение ее идентификаторов

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

1

4

6

5

3

2

Экстремальные радиусы

25,082

36,01

53,079

79,877

84,905

100,651

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

0,461

194,142

319,036

279,425

101,494

46,659

буква

 

Рис. 21. Второй вариант рукописной буквы «б», нарисованной первым человеком, и построение ее идентификаторов

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

4

1

6

5

3

2

Экстремальные радиусы

23,248

25,035

27,038

84,54

87,063

102,955

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

188,894

0,928

358,74

282,315

106,666

52,25

буква

 

Рис. 22. Третий вариант рукописной буквы «б», нарисованной первым человеком, и построение ее идентификаторов

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

3

2

4

1

6

5

Экстремальные радиусы

9,823

10,142

10,646

10,919

67,64

82,419

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

24,772

12,041

41,943

0,608

261,429

65,698

буква

 

Рис. 23. Вариант рукописной буквы «б», нарисованной вторым человеком, и построение ее идентификаторов

4.3. Характеристика образцов букв, написанных одним человеком, более сходна, что указывает на возможность различать не только саму букву, но и почерк человека, написавшего эту букву.

Рассмотрим примеры, подтверждающие данный факт.

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

1

4

3

6

2

5

Экстремальные радиусы

21,55

22,132

22,173

51,329

64,445

92,752

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

16,376

195,526

164,097

345,417

111,219

258,605

буква

 

Рис. 27. Первый вариант рукописной буквы «р», написанной первым человеком, и построения ее идентификаторов

Для данного и последующих изображений символов «р» (рис. 27 - 29) последними двумя индексами являются два и пять. Индекс четыре находится на первой или второй позиции. Индекс шесть находится на третьей или четвертой позиции.

На рис. 27 для символов «р» особенности содержит подстановка

(21)

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

4

3

1

6

2

5

Экстремальные радиусы

21,75

22,024

29,994

53,789

68,708

96,208

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

199,054

158,981

41,564

353,488

109,167

261,297

буква

 

Рис. 28. Второй вариант рукописной буквы «р», написанной первым человеком, и построения ее идентификаторов

На рис. 28 для символов «р» особенности содержит подстановка

(22)

Номера по порядку

1

2

3

4

5

6

Перестановка индексов

3

4

6

1

2

5

Экстремальные радиусы

17,349

17,416

31,324

38,747

52,692

83,265

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

154,669

205,79

358,944

15,605

84,207

258,443

буква

 

Рис. 29. Третий вариант рукописной буквы «р», написанной первым человеком, и построения ее идентификаторов

На рис. 29 для символов «р» особенности содержит подстановка

(23)

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

4.4. Если циклически поворачивать нулевое направление полярных координат по/против часовой стрелке до ближайшего угла элемента конечной выборки, то это приведет к изменению нумерации элементов конечной выборки и впоследствии – к изменению порядка следования индексов. Количество различных таких поворотов будет конечно, потому как ровно через общее число элементов конечной выборки, порядок следования индексов начнет повторяться. В одной из таких последовательностей индексов появится устойчивая характеристика рукописного символа, отличная от всех других. Причем для данной операции необходимо и достаточно получить выборку ровно из 6 элементов.

г(Л).bmp

г(Шрифт).bmp

г.bmp

г1.bmp

г2.bmp

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

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

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

Список литературы

  1. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. – 1994. – № 5. – С. 3 – 23.

  2. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. – 1995. – № 4. – С. 13 – 37.

  3. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочленов на основе сортировки. I // Кибернетика и системный анализ. – 2007. – № 1. – С. 165 – 183.

  4. Ромм Я.Е., Дзюба А.С. Метод распознавания рукописных символов на основе сортировки полярных координат / ТГПИ. – Таганрог, 2012. – 42 с. Деп. в ВИНИТИ 14.11.2012, № 418 – В2012.

  5. Tou J.T., Gonzalez R.C. Pattern recognition principles. – 1974. – Addison-Wesley publishing company.

  6. Ян Д.Е. Исследование, развитие и реализация методов автоматического распознавания рукописных текстов в компьютерных системах : диссертация на соискание ученой степени кандидата физико-математических наук : Москва,

2003.- 179 с.: РГБ ОД, 61 03-1/788-7.

  1. Горошкин А. Н. Применение векторного подхода к распознаванию рукописных символов: научная статья. Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева, 2006. - 15-17 с.

  2. Рюмин О.Г. Разработка и исследование алгоритмов распознавания изображений на основе определения экстремальных признаков замкнутых контуров с помощью сортировки – Таганрог: ТТИ ЮФУ, 2008, автореферат диссертации на соискание ученой степени канд. техн. наук. – 16 с.

Просмотров работы: 2936