Анализ метода распознавания символов, основанного на полиномиальной регрессии

Аннотация

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

Abstract

Present work contains new results of analysis of method at recognition of handprinted figures on base, coinciding with base of education. Materials concern to features of recognition and mutual location of 'average' rasters (or polynomial vectors) of different symbols, and also (in context with them) images of symbols. Generalization of got datum and shown more early monotonous decrease of average estimation of recognition of images of symbol on measure 'removing' is executed from 'average' polynomial vector of this symbol. Notions are entered finely -, average - and large-scale phenomena at description of given recognition method. Presence of structures is shown on average - and large-scale levels.

Настоящая работа является непосредственным продолжением [5] из серии [1-5], посвященной одному современному точному методу распознавания символов. Он основан на линейном регрессионном анализе [6-14]. Метод обладает высоким качеством распознавания и монотонностью оценок [2,3].

Результаты получены на базе рукопечатных цифр, которая используется как для обучения, так и для распознавания.

В работе [5] исследовано поведение оценки распознавания при увеличении «расстояния» между полиномиальным вектором, построенным по растру символа, и «среднестатистическим» вектором этого символа по базе. Проведено сравнение с результатами [4], где рассматривалось «расстояние» между растром и «среднестатистическим» растром для каждого из символов.

Настоящая работа содержит новый материал, относящийся к «среднестатистическим» растрам и векторам. Выполнено обобщение этих данных и результатов работы [5]. Введены понятия мелко-, средне- и крупномасштабных явлений при описании метода распознавания. Показано наличие структур на средне- и крупномасштабном уровнях.

1.1. Постановка задачи. Задача распознавания символов состоит в разработке алгоритма, позволяющего по данному растру изображения (рис.1) определить, какому символу из некоторого конечного множества с K элементами он соответствует. Представлением символа является растр, состоящий из N=N1´N2 серых или черно-белых пикселей. Перенумеровав все пиксели растра, запоминаем в i-ой компоненте (1£i£N) вектора vÎR^N состояние i-го пикселя, а именно, 0 или 1 в случае черно-белого растра и значение на отрезке [0,1] для серого растра. Пусть V={v} – совокупность всевозможных растров. Очевидно, VÍR^N, причем если пиксели черно-белые, то V={0,1}^N – конечное множество, элементами которого являются последовательности из нулей и единиц длины N. Если пиксели серые, то V=[0,1]^N– N-мерный единичный куб в R^N.

Математическая постановка задачи распознавания состоит в следующем. Пусть для некоторого растра vÎV можно найти p_k(v) – вероятность того, что растр изображает символ с порядковым номером k, 1£k£K. Тогда распознанным считается символ с порядковым номером k_o, где

Для решения задачи следует вычислить вектор вероятностей (p₁(v), p₂(v),…, p_K(v)). Он может быть найден на основе метода наименьших квадратов.

1.2. Метод наименьших квадратов. Отождествим k-й символ с базисным вектором e_k=(0…1…0) (1 на k-м месте, 1£k£K) из R^K, причем Y={e₁,…,e_K}. Пусть p(v,y) – вероятность наступления события (v,y), vÎV, yÎY (если V континуально, то плотность вероятности). Наступление события (v,y) означает, что выпадает растр v, и этот растр изображает символ y. Тогда вероятность p_k(v) – это условная вероятность p_k(v)=p(e_k|v)=p(v,e_k)/. С другой стороны, имеет место следующий результат [6,12]:

достигает минимума на векторе d(v)=(p₁(v),…,p_K(v)), причем min берется по всем непрерывным d: V® R^K.

В Теореме 1 ||×|| - евклидова норма в R^K, и для любой функции f: V´Y® R через E{f(v,y)} обозначено математическое ожидание случайной величины f:

(в случае конечного V или Y интегрирование по соответствующей переменной заменяется на сумму). Итак, требуемый вектор вероятностей (p₁(v),…,p_K(v)) ищется как решение экстремальной задачи (1). Приближенное решение задачи (1) может быть найдено методом полиномиальной регрессии.

1.3. Метод полиномиальной регрессии. Приближенные значения компонент вектора (p₁(v),…,p_K(v)) будем искать в виде многочленов от координат v=(v₁,…,v_N):

Суммы в правых частях равенств (2) конечные и определяются выбором базисных мономов. А именно, если

конечный вектор размерности L из выбранных и приведенных в (2) базисных мономов, упорядоченных определенным образом, то в векторном виде соотношения (2) можно записать так:

где A – матрица размера L´K, столбцами которой являются векторы а⁽¹⁾,…, а^(K).

Каждый такой вектор составлен из коэффициентов при мономах соответствующей строки (2) (с совпадающим верхним индексом), упорядоченных так же, как в векторе x(v). Следовательно, приближенный поиск вектора вероятностей p(v) сводится к нахождению матрицы A. Учитывая результат Теоремы 1, следует понимать, что матрица А является решением экстремальной задачи:

где min берется по всевозможным матрицам А размера L´K.

Теорема 2. Матрица А размера L´K доставляет решение экстремальной задаче (3) тогда и только тогда, когда А является решением матричного уравнения

Итак, согласно методу полиномиальной регрессии

Заметим, что если x(v)=(1,v₁, … ,v_N)^T, то метод полиномиальной регрессии называется методом линейной регрессии [12].

1.4. Вычисление матриц E{x(v) x(v)^Т}, E{x(v) y^Т} основано на следующем результате математической статистики. Пусть имеется датчик случайных векторов, распределенных по неизвестному нам закону p(v,y):

Тогда математическое ожидание любой случайной величины f(v,y) может быть вычислено из предельного равенства:

Если J достаточно большое, то верно приближенное равенство:

Набор [v⁽¹⁾,y⁽¹⁾], …, [v⁽^J⁾,y⁽^J⁾] практически реализуется некоторой базой данных, а вычисления по формуле (5) называются обучением. В данном случае f(v,y) = x_i(v)x_j(v) или f(v,y) = x_i(v)y_k , и по определению

А согласно формуле (5), получим выражение для практического вычисления:

1.5. Практическое нахождение матрицы А. Согласно (4) и (6), имеем следующее приближенное значение для А:

В [7] показано, что правую часть (7) можно вычислить по следующей рекуррентной процедуре, где А₀и G₀ заданы:

Введение вспомогательной матрицы G_jразмера L´L помогает избежать процедуры обращения матрицы в (7). Реально выбор параметров a_jпроизводится экспериментально. Вообще на практике используются следующие две упрощенные модификации процедуры (8).

Модификация А. G_jº Е, A_j=A_j_-1-x⁽^j⁾[Ax⁽^j⁾-y⁽^j⁾]^T (9)

2. Развитие и практическая реализация метода распознавания

2.1. Некоторые замечания. Следует сразу отметить, что ниже рассматривается только Модификация Б, так как, в отличие от Модификации А, именно в этом случае получены приемлемые практические результаты. Поэтому не исследовалась постановка задачи c уравнениями, записанными в общем виде, и вследствие этого с существенно более медленными алгоритмами обучения и распознавания. Мы будем использовать серые растры размера N=256=16´16. Масштабирование образов до размера 16х16 сохраняет особенности геометрии исходных символов (рис.1).

2.2. Построение вектора x. Используются два варианта вектора x: короткий и длинный. Для более длинного вектора больше размеры таблицы (матрицы) распознавания, медленнее осуществляется обучение и распознавание, но качество распознавания выше. Длинный вектор строится так:

{(dv_i)_r⁴}, {(dv_i)_y⁴}, {(dv_i)_r(dv_i)_y}, {(dv_i)_r²(dv_i)_y²}, {(dv_i)_r⁴(dv_i)_y⁴},

Короткий вектор составлен из элементов длинного вектора в первой строке (11)

В (11) и (12) выражения в фигурных скобках соответствуют цепочкам элементов вектора, вычисляемым по всем пикселям растра (за исключением указанных ниже случаев). Через (dv_i)_rи (dv_i)_yобозначены конечные центральные разности величин v_iпо ортогональным направлениям ориентации растра – нижние индексы r и y соответственно. Если имеется нижний индекс L (left) или D (down), то это означает, что соответствующие величины относятся к пикселю слева или снизу от рассматриваемого. Компоненты вектора x, не имеющие индекса L или D, вычисляются для всех пикселей растра; с индексом L – кроме левых граничных; с индексом D – кроме нижних граничных пикселей. Вне растра считаем, что v_i=0 (используется при вычислении конечных разностей на границе растра). Для длинного вектора x к перечисленному в (11) добавляются компоненты, являющиеся средним арифметическим значений v_i(по восьми пикселям, окружающим данный), а также квадраты этих компонент.

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

2.3. Алгоритмы обучения и распознавания (модификация Б). При обучении элементы матрицы D (10) вычисляются так. Для каждого j-го элемента базы символов последовательно, начиная с первого и заканчивая J-м (последним), строится вектор xсогласно (11) или (12). Попутно рассчитываются значения компонент вспомогательного вектора mпо рекуррентной формуле:

По окончании этой процедуры для последнего элемента имеем согласно (10):

После того, как завершено вычисление G_J, элементы матрицы A_j (8) рассчитываются следующим образом. Выполняется еще один проход по базе и для каждого j-го элемента базы символов, начиная с первого и заканчивая J-м, строится вектор x^j согласно (11) или (12). Попутно вычисляется A_j:

На этом этап обучения закончен: матрица A=A_Jполучена.

Распознавание осуществляется следующим образом. Для серого изображения размером 16х16 пикселей строится вектор x согласно (11) или (12). После этого по формуле (2’), используя A=A_J (15), вычисляются оценки, соответствующие каждому из возможных символов. Затем выбирается символ с максимальной оценкой. Получаемые оценки могут выходить за рамки отрезка [0,1] из-за того, что используемый метод является приближенным. Отрицательные значения искусственно обнулялись, а те, которые были больше 1, делались равными 1. Практика распознавания показала приемлемость такого довольно грубого способа коррекции оценок.

3.1. Особенности обучения и распознавания. При анализе метода распознавания аналогично [5] как обучение, так и распознавание будет проводиться на одной и той же графической базе данных, содержащей изображения и коды символов. Это делается для обеспечения «чистоты эксперимента», поскольку результат распознавания на символьных последовательностях, «посторонних» для обучающей базы, может сильно отличаться для разных последовательностей. Данная проблема детально рассматривалась в [4].

В настоящей работе аналогично [5] при обучении и распознавании использовалась модификация длинного вектора х – (11). После многократного обучения по базе в 174 778 элементов с полученной матрицей распознается 99,5% элементов (173 897 изображений распознаются верно, 881 – неверно).

Результатом распознавания образа является код символа и его целочисленная оценка, лежащая в диапазоне [1,255] (оценка 255 является наилучшей). Эта новая оценка получается следующим образом. В результате умножения оценки на 255 старый непрерывный диапазон оценок [0,1] (см. пп.1, 2) переходит в новый (также непрерывный) [0,255], после чего проводится дискретизация, а именно, [0,1]→1, (1,2]→2,…, (254,255]→255.

3.2. Поведение средней оценки распознавания и функции распределения при отклонении от «среднестатистического» растра. Несомненный интерес вызывает решение вопроса о том, имеются ли какие-нибудь закономерности в выставлении оценок распознавания изображений символов, или оно носит абсолютно хаотический характер. Аналогично, представляется важным понять характер распределения изображений символов.

На рис.2а, 3а представлены диаграммы зависимости средней оценки распознавания символа (9 и 1 соответственно) от величины отклонения между его растрами и «среднестатистическим» растром этого символа. Для цифр 0, 2, 3, 4, 5, 6, 7, 8 диаграммы аналогичны приведенной на рис.2а.

Для «среднестатистического» растра конкретного символа значение в пикселе, имеющем номер i, равно среднему арифметическому значений i-х пикселей по всем растрам этого символа. Расстояние между растрами v=(v₁,…,v_N) и u=(u₁,…,u_N) определяется так: вычисляется модуль разности значений в i-х пикселях, затем производится суммирование по всем N пикселям:

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

Отрезок [v_true_min, v_true_max] (оси абсцисс на рис.2а, 3а) был поделен на 20 равных по длине частей – отрезок и 19 полуинтервалов: [v_true_min, v_true_min + dv], (v_true_min + dv, v_true_min + 2dv], … , (v_true_min + 19dv, v_true_min + 20dv], где dv = (v_true_max - v_true_min)/20. Затем для совокупности изображений, попадающих в каждый такой участок, вычислялась средняя оценка распознавания (оси ординат на рис. 2а, 3а). Она не убывает монотонно по мере «удаления» растров от «среднестатистического», а для «1» принимает значение 255 на наибольшем удалении от «среднестатистического» образа. Диаграмма 2а и аналогичные для цифр 0, 2, 3, 4, 5, 6, 7, 8 имеют тенденцию к убыванию, но велик уровень шумов.

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

Для неправильно распознанных образов символа диапазон отклонений между его растрами и «среднестатистическим» растром этого символа по рассматриваемой базе находится от минимального v_false_min до максимального v_false_max. В таблице 1 приведены значения этих величин для символов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, а также средняя оценка неправильного распознавания Р_false. Они приблизительно в два раза меньше, чем оценки правильного распознавания. Если сравнить v_true_min некоторого символа и v_false_min любого другого (или того же) символа, то v_true_min < v_false_min.

Для произвольного символа G из рассматриваемых цифр 0, … , 9 диапазон отклонений между растрами изображений всех символов, кроме G, и «среднестатистическим» растром цифры G по рассматриваемой базе находится от минимального ┐v_min до максимального ┐v_max. В таблице 2 приведены значения этих величин для каждого из возможных символов G: 0, …, 9. Отметим, что при сравнении v_false_max некоторого символа и ┐v_max произвольного символа, имеем: v_false_max < ┐v_max.

Кроме того, любая из трех «минимальных» величин (v_true_min, v_false_min, ┐v_min) некоторого символа меньше, чем любая «максимальная» величина (v_true_max, v_false_max, ┐v_max) произвольного символа.

3.3. Поведение средней оценки распознавания и функции распределения при отклонении от «среднестатистического» вектора. На рис.2в, 3в даны диаграммы зависимости средней оценки распознавания символа (9 и 1 соответственно) от величины отклонения между полиномиальным вектором х, построенным по его растру, и «среднестатистическим» полиномиальным вектором этого символа. Для остальных цифр диаграммы аналогичны рис.2в.

Для «среднестатистического» полиномиального вектора конкретного символа значение в каждой компоненте вектора, имеющей номер i, равно среднему арифметическому значений i-х компонент по всем растрам рассматриваемого символа. Расстояние между векторами v=(v₁,…,v_L) и u=(u₁,…,u_L) определяется так: вычисляется модуль разности значений в i-х компонентах и проводится суммирование по всем L компонентам:

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

Отрезок [х_true_min, х_true_max] (оси абсцисс на рис.2в, 3в) был поделен на 20 равных по длине частей – отрезок и 19 полуинтервалов: [х_true_min, х_true_min + хdv], (х_true_min + хdv, х_true_min + 2хdv], … , (х_true_min + 19хdv, х_true_min + 20хdv], где хdv = (х_true_max – х_true_min)/20. Затем для совокупности изображений, имеющих полиномиальные векторы, попадающие в каждый такой участок, вычислялась средняя оценка распознавания (оси ординат на рис. 2в, 3в). На этих рисунках видно, что средняя оценка распознавания для каждого из рассматриваемых символов на соответствующем этому символу отрезке [х_true_min, х_true_max] убывает монотонно (с некоторыми шумовыми погрешностями) по мере «удаления» от «среднестатистического» вектора, а для «1» сначала монотонно убывает, а затем монотонно увеличивается и принимает максимальное значение 255 на предпоследнем интервале удаления от «среднестатистического» вектора (также с некоторыми погрешностями). Уровень шумов в этих зависимостях существенно ниже, а степень монотонности выше, чем в аналогичных зависимостях для средней оценки распознавания при отклонении от «среднестатистического» растра.

На рис.2г, 3г приведены диаграммы - «дискретный» аналог функции распределения для распознанных верно изображений символов 0, 1 (для 2, … , 9 аналогично). А именно, ось абсцисс такая же, как указано в предыдущем абзаце для рис.2в, 3в, а по оси ординат отложено количество правильно распознанных изображений, попавших в каждую двадцатую часть отрезка [х_true_min, х_true_max].

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

Дальнейшие действия были проделаны для «среднестатистических» векторов, поскольку в использующих их зависимостях уровень шумов существенно ниже, чем для «среднестатистических» растров. Найдя первоначальное «среднестатистическое» значение полиномиального вектора х0, мы отделили ту часть изображений, полиномиальные векторы которых удалены от соответствующего х_true_min более чем на 2/3 величины х_true_max-х_true_min и построили для них «среднестатистическй» вектор х1. Оказалось, что для изображений, векторы которых к х1 ближе, чем к х0, при удалении от х1 оценка монотонно падает (рис.3ж). Всего оказалось 714 таких изображений. Для оставшихся 32388 изображений построили новый среднестатистический вектор х2, при отклонении от которого имела место аналогичная закономерность (рис.3д). Для каждой из выделенных подбаз построили функции распределения (соответственно рис.3з, рис.3е), которые оказались схожи с функциями распределения других символов. Дополнительные итерации, несомненно, улучшили бы степень разделения подбаз.

Проанализировано, как соотносится монотонный характер убывания средней оценки распознавания при удалении от «среднестатистического» вектора с функциями распределения верно распознанных изображений для различных оценок распознавания. Изучение указанных закономерностей проведено на примере символа «8». Рассмотрены следующие диапазоны оценок распознавания: [255, 250), [250, 240), [240, 230), [230, 220), [220, 210), [210, 200), [200, 190), [190, 180), [180, 170), [170, 160), [160, 150), [150, 140), [140, 130), [130, 120). Проводить исследования для более низких оценок нецелесообразно, поскольку количество оставшихся изображений, не попавших в описанные полуинтервалы, невелико и сопоставимо с количеством неправильно распознанных растров. Для изображений, получивших оценку распознавания внутри каждого из этих полуинтервалов, построены соответствующие функции распределения. На рис.4а-4д приведены графики - «дискретный» аналог описанных функций распределения. А именно, ось абсцисс такая же, как указано ранее в настоящем разделе 3.3 для рис.2в, 3в, 2г, 3г а по оси ординат отложено количество правильно распознанных изображений, получивших оценку из соответствующего диапазона и попавших в каждую вышеописанную двадцатую часть отрезка [х_true_min, х_true_max].

На рис.4а приведен такой же график для всего «совокупного» спектра оценок распознавания, полученных изображениями цифры 8 (соответствующий диаграмме, аналогичной рис. 2г, 3г), обозначенный в «легенде» диапазоном «0-255». Здесь же имеются графики функций распределения для диапазонов [255, 250) и [250, 240), указанные в «легенде» как «250-255» «240-250» соответственно. Использование диапазона [255, 250), который вдвое меньше каждого из указанных на рис. 4б, 4в, 4г, 4д объясняется тем, что в этот полуинтервал попадает большое количество символов, как это нетрудно увидеть на рис.4а при сравнении графиков «250-255» и «240-250».

В серии рис.4а – 4г для удобства в проведении сопоставления каждый предыдущий и последующий рисунки содержат по одному общему графику. Так для рис.4а, 4б общим является «240-250», рис.4б, 4в объединяет «210-220», а рис.4в, 4г роднит «180-190», а рис.4г, 4д - «150-160».

Итак, на каждом из двадцати частей отрезка [х_true_min, х_true_max] средняя оценка получается суммированием оценок 1, 2, 3, …, 254, 255 с весами, определяемыми средней величиной (по этому отрезку) функции вероятности соответствующей оценки. Из этого становится понятным, что полученный результат, а именно, монотонное убывание средней оценки распознавания, далеко не очевиден. Он соответствует наличию структуры в ряду случайных событий.

Диапазон отклонений между полиномиальным вектором неправильно распознанного изображения символа и «среднестатистическим» вектором этого символа по рассматриваемой базе находится от минимального х_false_min до максимального х_false_max. В таблице 2 приведены значения этих величин для каждого из символов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Для произвольного символа G из рассматриваемых цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 диапазон отклонений между полиномиальными векторами изображений всех символов, кроме G, и «среднестатистическим» вектором цифры G по рассматриваемой базе находится от минимального ┐х_min до максимального ┐х_max. В таблице 2 приведены значения этих величин для каждого из возможных символов G: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Отметим, что для каждого из рассматриваемых цифр х_true_min < ┐х_min < х_false_min; кроме того, х_true_max < ┐х_max; а также х_false_max < ┐х_max. Следовательно, для каждого символа G можно выделить полуинтервал [х_true_min, ┐х_min), в котором находятся только правильно распознанные изображения этого символа; внутри полуинтервала [┐х_min, х_false_min) имеются правильно распознанные изображения символа G и изображения символов, отличных от G; в полуинтервале (MAX(х_true_max, х_false_max), ┐х_max] лежат только изображения символов, отличных от G; внутри отрезка [х_false_min, MIN(х_true_max, х_false_max)] содержатся любые изображения (и правильно, и неправильно распознанные изображения символа G, а также отличные от G символы); в полуинтервале (MIN(х_true_max, х_false_max), MAX(х_true_max, х_false_max)] - отличные от G символы, а также при х_true_max > х_false_max (для цифр 0, 1, 3, 5, 6, 8, 9)- правильно, а при х_true_max < х_false_max (для 2, 4, 7) - неправильно распознанные изображения символа G (соответственно рис.5а, 5б).

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

Отметим, что соотношения, приведенные в двух предыдущих абзацах, не выполняются для приведенных в таблице 1 аналогичных величин в терминах растров (v_true_min, ┐v_min, v_false_min, v_true_max, v_false_max, ┐v_max). Следовательно, выявленное для полиномиальных векторов структурированное расположение символов при удалении от «среднестатистического» вектора не имеет места в терминах растров.

3.4. Распознавание «среднестатистических» растров и векторов различных символов. Вышеприведенные результаты получены с использованием «среднестатистических» растров и векторов. Возникает естественный вопрос, а будут ли они сами верно распознаны при помощи описанного метода? Если да, то каковы оценки распознавания? Оказалось, что как «среднестатистические» растры, так и векторы распознаются верно для всех символов. Очевидно, что любое изображение распознается как перечень из десяти альтернатив для каждого из символов 0 - 9 с соответствующей оценкой. Альтернативы нумеруются по мере убывания оценок. Для правильно распознанного символа оценка 0^ой альтернативы, естественно, и есть оценка распознавания. Интерес представляет не только она, но и оценка 1^ой альтернативы. Соотношение между этими оценками говорит о «контрастности» распознавания: чем больше различаются оценка 0^ой альтернативы и оценка 1^ой альтернативы, тем больше контрастность распознавания. В таблице 3 для каждой из цифр от 0 до 9 приведены оценки распознавания «среднестатистических» растров Р_v_-средн (0^ая альтернатива), а также Р_v_-средн (1^ая альтернатива). Аналогично, даны оценки распознавания «среднестатистических» векторов Р_{х-средн} (0^ая альтернатива), а также Р_{х-средн} (1^ая альтернатива). Для каждой цифры оценка распознавания «среднестатистического» растра ниже, чем соответствующего вектора. Оценка первой альтернативы для любого «среднестатистического» растра выше, чем оценка первой альтернативы для любого «среднестатистического» вектора (как того же символа, так и другого). Следовательно, «среднестатистические» растры имеют меньшую контрастность, чем соответствующие векторы. Разброс оценок (разница между максимальной и минимальной оценками) при распознавании «среднестатистических» растров равен 229-105=124. Он намного выше, чем имеющийся у векторов (240-219=21). В таблице в двух последних столбцах для каждого символа указано сначала общее количество изображений, а затем число / доля (выраженная в процентах) неправильно распознанных изображений.

3.5. Расстояния между «среднестатистическими» растрами и векторами различных символов. В дополнение к таблице 1 (п.3.2.) приведем данные о расстоянии между «среднестатистическими» растрами различных символов. В таблице 4 по горизонтали и по вертикали указаны цифры от 0 до 9. На пересечении столбцов и строк даны расстояния между «среднестатистическими» растрами соответствующих цифр.

Расстояние между «среднестатистическими» растрами цифр 4 и 9 является минимальным и равно 34,3, а для 0 и 1 соответствующее расстояние - максимальное, его значение 81,6. Чисто визуально это понятно.

Аналогично, в дополнение к таблице 2 (п.3.3.) приведем данные о расстоянии между «среднестатистическими» векторами различных символов. В таблице 5 по горизонтали и по вертикали указаны цифры от 0 до 9. На пересечении столбцов и строк даны расстояния между «среднестатистическими» векторами соответствующих цифр.

Расстояние между «среднестатистическими» векторами цифр 8 и 9 является минимальным (что отличается от случая с растрами) и равно 1902, а для 0 и 1 соответствующее расстояние – максимальное (как и для растров), его значение 4358. Это также укладывается в рамки визуального представления о сходстве и различии символов. Тот факт, что пара наиближайших «среднестатистических» растров не совпадает с парой наиближайших «среднестатистических» векторов горит о существенной перестройке «метрики» при переходе от растрового к векторному подходу.

В этом же заключается причина того, что между таблицами 4 и 5 не наблюдается заметного соответствия: большему / меньшему значению расстоянию между «среднестатистическими» растрами не всегда соответствует большее / меньшее расстояние между «среднестатистическими» векторами.

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

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

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

Расчеты показали, что среди верно распознанных 173 897 изображений растры наименее удалены от «среднестатистического» растра соответствующего символа для 152153 изображений, что составляет 87,50% от их числа. Аналогично, полиномиальные векторы наименее удалены от «среднестатистического» вектора соответствующего символа для 153720 изображений, что составляет 88,40% от их числа.

Соответственно, среди неверно распознанных 881 изображений растры наименее удалены от «среднестатистического» растра символа, получившего максимальную оценку всего лишь для 470 изображений, что составляет 53,35% от их числа. Аналогично, среди неверно распознанных 881 изображений полиномиальные векторы наименее удалены от «среднестатистического» вектора символа, получившего максимальную оценку всего лишь для 454 изображений, что составляет 51,53% от их числа.

Для правильно распознанных символов описанные результаты получены раздельно по каждому из символов 0, 1, …, 9 и представлены в таблицах 6(1) - 6(2) для растров, а также 7(1) - 7(2) для полиномиальных векторов.

По таблицам 6(1) - 6(2) видно, что для каждого из символов растры наибольшего количества изображений ближе всего к «своему» «среднестатистическому» растру (их доля указана в последнем столбце таблицы 6(2)).

По таблицам 7(1) - 7(2) видно, что для каждого из символов полиномиальные векторы наибольшего количества изображений ближе всего к «своему» «среднестатистическому» вектору (их доля указана в последнем столбце таблицы 7(2)).

При сопоставлении таблиц 6(1) - 6(2) и 7(1) - 7(2) видно, что они существенно различаются. Можно привести огромное количество примеров несоответствия данных. Достаточно уже сравнить вторые столбцы таблиц 6(2) и 7(2), относящиеся к «среднестатистическим» растру и вектору символа 5. Значительные расхождения имеются также и в последних столбцах таблиц 6(2) и 7(2), так что к приведенным общим по всем символам цифрам о наименее удаленных от «среднестатистического» растра изображениях (87,50%) и наименее удаленных от «среднестатистического» вектора изображениях (88,40%) следует добавить данные о разбросе по различным символам из последних столбцов таблиц.

Для неправильно распознанных символов также соответствующие результаты получены раздельно по каждому из получивших наивысшую оценку символов 0, 1, …, 9 и представлены в таблицах 8(1) - 8(2) для растров, а также 9(1) - 9(2) для полиномиальных векторов.

По таблицам 8(1) - 8(2) видно, что не для каждого из символов растры наибольшего количества изображений ближе всего к «своему» «среднестатистическому» растру.

По таблицам 9(1) - 9(2) видно, что не для каждого из символов полиномиальные векторы наибольшего количества изображений ближе всего к «своему» «среднестатистическому» вектору.

В таблицах 8(1) - 8(2) и 9(1) - 9(2) отсутствует последний столбец, имеющийся в таблицах 6(1) - 6(2) и 7(1) - 7(2). Это понятно, поскольку в первом столбце указаны не сами распознаваемые символы, а те ошибочные символы, в качестве которых они были распознаны.

Следует отметить, что между таблицами 8(1) - 8(2) и 9(1) - 9(2) наблюдается определенное сходство, в отличие от таблиц 6(1) - 6(2) и 7(1) - 7(2). Видимо, это говорит о том, что для неправильно распознанных символов использование полиномиальных векторов вместо растров добавляет небольшое количество информации о символах, в отличие от ситуации с правильно распознанными символами, для которых переход от растров к полиномиальным векторам существенно увеличивает количество информации и приводит к перестраиванию структуры распознавания (таблицы 6(1) - 6(2), 7(1) - 7(2)).

4. Выводы

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

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

К среднемасштабным следует отнести те, при описании которых принципиальным является наличие (или построение) «среднестатистических» растров и векторов различных символов, но не используется механизм осреднения оценок (или он является несущественным, служит каким-то второстепенным целям, и от него легко отказаться). Сюда нужно причислить: 1) получение «среднестатистических» растров и векторов различных символов, 2) их распознавание и нахождение оценок распознавания, 3) определение расстояния между ними (естественно, для растров и векторов отдельно), 4) построение функций распределения (необязательно осредненных по частичным диапазонам отклонения – это делалось исключительно для удобства рисования картинок) при отклонения от «среднестатистических» растров / векторов, причем как для всей совокупности оценок, так и для отдельных оценок или их частичных диапазонов, 5) обнаружение наличия структуры при отклонении от «среднестатистического» растра / вектора символа правильно, неправильно распознанных изображений этого символа, а также «чужих» символов, 6) определение среди распознанных изображений символа доли тех, для которых наиближайшим является «свой» «среднестатистический» растр / вектор, 7) вычисление среди нераспознанных изображений символа доли тех, для которых наиближайшим является получивший максимальную оценку среднестатистический растр / вектор, 8) решение ориентироваться на полиномиальные векторы, а не на растры, поскольку использование последних сопряжено с присутствием существенных шумовых помех. Помимо указанных восьми пунктов могут быть их комбинации и модификации. Следует только отметить, что среднемасштабные явления надо поделить на те, в которых используются «среднестатистические» растры / векторы различных символов – они «ближе» к мелкомасштабным, а также на ориентированные только на «среднестатистический» растр / вектор одного символа – эти ближе к крупномасштабным. Такое деление на две подгруппы сделать нетрудно. Уже на этом среднемасштабном уровне над «хаосом» мелкомасштабных» явлений выявлено наличие структуры – в расположении правильно, неправильно распознанных, а также «чужих» символов при удалении от «среднестатистического» вектора.

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

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

Литература

[1] Гавриков М.Б., Пестрякова Н. В. "Метод полиномиальной регрессии в задачах распознавания печатных и рукопечатных символов", //Препринт ИПМатем. РАН, М., 2004, №22, 12 стр.

[2] Гавриков М.Б., Пестрякова Н. В., Славин О.А, Фарсобина В.В.. "Развитие метода полиномиальной регрессии и практическое применение в задаче распознавания", //Препринт ИПМатем. РАН, М., 2006, №25, 21 стр.

[3] Гавриков М.Б., Мисюрев А.В., Пестрякова Н.В., Славин О.А. Развитие метода полиномиальной регрессии и практическое применение в задаче распознавания символов. Автоматика и Телемеханика. 2006, №3, С. 119-134.

[4] Гавриков М.Б., Пестрякова Н. В., Усков А.В., Фарсобина В.В. "О некоторых свойствах метода распознавания символов, основанного на полиномиальной регрессии", //Препринт ИПМатем. РАН, М., 2007, №69, 20 стр.

[5] Гавриков М.Б., Пестрякова Н. В., Усков А.В., Фарсобина В.В. "О некоторых свойствах оценки метода распознавания символов, основанного на полиномиальной регрессии", //Препринт ИПМатем. РАН, М., 2008, №7, 28 стр.

[6] Sebestyen G.S. Decision Making Processes in Pattern Recognition, MacMillan, New York, 1962.

[10] Albert A.E. and Gardner L.A. Stochastic Approximation and Nonlinear Regression // Research Monograph 42. MIT Press, Cambridge, MA, 1966.

[11] Becker D. and Schürmann J. Zur verstärkten Berucksichtigung schlecht erkennbarer Zeichen in der Lernstichprobe // Wissenschaftliche Berichte AEG-Telefunken 45, 1972, pp. 97 – 105.

[12] Pao Y.-H. The Functional Link Net: Basis for an Integrated Neural-Net Computing Environment // in Yoh-Han Pao (ed.) Adaptive Pattern Recognition and Neural Networks, Addisson-Wesley, Reading, MA, 1989, pp. 197-222.

[13] Franke J. On the Functional Classifier, in Association Francaise pour la Cybernetique Economique et Technique (AFCET), Paris // Proceedings of the First International Conference on Document Analysis and Recognition, St. Malo, 1991, pp.481-489.

[14] Дж.Себер. Линейный регрессионный анализ. М.:”Мир”, 1980.

[15] Линник Ю.В. Метод наименьших квадратов и основы математико - статистической теории обработки наблюдений. М.:”Физматлит”, 1958.

стической теории обработки наблюдений. М.:”Физматлит”, 1958.

Анализ метода распознавания символов, основанного на полиномиальной регрессии

( Analysis of method of character recognition, based on polynomial regression
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Гавриков М.Б., Пестрякова Н.В., Усков А.В., Фарсобина В.В.
(M.B.Gavrikov, N.V.Pestryakova, A.V.Uskov, V.V.Farsobina)

ИПМ им. М.В.Келдыша РАН

Москва, 2008

Аннотация

Abstract

4. Выводы

Литература

Рисунки

Анализ метода распознавания символов, основанного на полиномиальной регрессии ( Analysis of method of character recognition, based on polynomial regression Preprint, Inst. Appl. Math., the Russian Academy of Science)

Гавриков М.Б., Пестрякова Н.В., Усков А.В., Фарсобина В.В. (M.B.Gavrikov, N.V.Pestryakova, A.V.Uskov, V.V.Farsobina) ИПМ им. М.В.Келдыша РАН

Москва, 2008

Аннотация

Abstract

4. Выводы

Литература

Рисунки

Анализ метода распознавания символов, основанного на полиномиальной регрессии

( Analysis of method of character recognition, based on polynomial regression
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Гавриков М.Б., Пестрякова Н.В., Усков А.В., Фарсобина В.В.
(M.B.Gavrikov, N.V.Pestryakova, A.V.Uskov, V.V.Farsobina)

ИПМ им. М.В.Келдыша РАН