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

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 с.

Код для цитирования: Скопировать