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

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

Введение

Настоящая работа является очередной в серии [1 - 4], посвященной одному из современных точных методов распознавания символов. Он основан на линейном регрессионном анализе [5 - 13]. Практика использования данного метода и сравнение его с другими способами распознавания подтвердили, что он удовлетворяет высоким требованиям по качеству распознавания, быстродействию, монотонности оценок [2, 3]. Заметим, что результаты работы [4] получены с использованием новой модификации метода, имеющей еще более высокое качество распознавания.

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

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

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

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

Для «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_ko(v)=max p_k(v),  1£k£K

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

Метод наименьших квадратов.  Отождествим 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]:

Теорема 1. Экстремальная задача

E{||d(v)-y||²}min                                                     (1)

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

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

         E{f(v,y)}

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

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

         p₁(v) @ c+ ++…

p₂(v) @ c+ ++…                                                             (2)

………………………………………….

p_K(v) @ c+ ++…       

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

x(v)=(1,v₁, … ,v_N, … )^T

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

         p(v) = (p₁(v),…,p_K(v)) @ A^Tx(v)                                                                     (2’)

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

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

         E{||А^Тx(v)-y||²}min                                                                (3)

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

         Имеет место следующий результат [4].

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

E{x(v) x(v)^Т}А = E{x(v) y^Т}                                                         (4)

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

         p(v) @ А^Тx(v),               А = E{x(v) x(v)^Т}^-1 E{x(v) y^Т}  

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

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

[v⁽¹⁾,y ⁽¹⁾], [v⁽²⁾,y ⁽²⁾],…

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

         E{ f(v,y) } =

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

E{f(v,y)}@                                (5)

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

E{x(v) x(v)^Т} = [E{x_i(v)x_j(v)}]_1£i,j£L = []_1£i,j£L

         E{x(v) y^Т}=[E{x_i(v)y_k}]_{1£i£L, 1£k£K} =

         []_{1£i£L, 1£k£K}= []_{1£i£L, 1£k£K}

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

E{x(v) x(v)^Т}@,    E{x(v) y^Т}@                       (6)

где  x^(j) = x(v^(j)), 1£j£J

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

         А @ ()^-1()                                                         (7)

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

         A_j = A_j-1-a_jG_jx^(j)[Ax^(j)-y^(j)]^T ,   a_j = 1/J

         G_j = [G_j-1-a_j]          1£j£J                                  (8)

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

         Модификация А.        G_j º Е

                   A_j = A_j-1-x^(j)[Ax^(j)-y^(j)]^T                                                                       (9)

         Модификация Б.  G_jºD^-1,

D=diag(E{x},E{x},…,E{x})                                                                        (10)

Рис. 1. Образы 16х16 рукопечатных цифр

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

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

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

x =(1, {v_i}, {v_i²}, {(dv_i)_r}, {(dv_i)_r²}, {(dv_i)_y}, {(dv_i)_y²},

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

{(dv_i)_r((dv_i)_r)_L},{(dv_i)_y((dv_i)_y)_L},{(dv_i)_r((dv_i)_y)_L},                                                     (11)

{(dv_i)_y((dv_i)_r)_L}, {(dv_i)_r((dv_i)_r)_D}, {(dv_i)_y((dv_i)_y)_D},

{(dv_i)_r((dv_i)_y)_D}, {(dv_i)_y((dv_i)_r)_D})

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

х=(1, {v_i}, {v_i²}, {(dv_i)_r}, {(dv_i)_r²}, {(dv_i)_y}, {(dv_i)_y²})                                            (12)  

В (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 (по восьми пикселям, окружающим данный), а также квадраты этих компонент. Отметим, что набор компонентов вектора х подобран в процессе численных экспериментов. А именно, среди множества рассмотренных вариантов оставлены те, которые делают заметный вклад в улучшение распознавания.

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

m = (1-β) m+ β (x),           j=1,…,J ,    p=1,…,L                                   (13)

β=1/j

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

         G_J º D^-1 = diag(1/m, 1/m,…, 1/m)                                                           (14)

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

         a = a- a_j x(ax- y)/m,     a_j = 1/J                                       (15)

         A = [a],          j=1,…,J ,    p=1,…,L     ,    k = 1,…,K     

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

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

 3. Распознавание символов обучающей базы

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

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

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

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

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

||v-u|| =                                                    (16)  

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

 Делим отрезок [v_true_min, v_true_max] (оси абсцисс на рис.2а-11а) на 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а-11а). На этих диаграммах видно, что средняя оценка распознавания ни для одного из рассматриваемых символов на соответствующем этому символу отрезке [v_true_min, v_true_max] не убывает монотонно по мере «удаления» растров от «среднестатистического» растра, а для «1» принимает максимальное значение 255 на наибольшем удалении от «среднестатистического» образа. Некоторые диаграммы имеют общую тенденцию к убыванию, но на эту закономерность накладывается высокий уровень шумов. 

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

Для неправильно распознанных образов символа диапазон отклонений между его растрами и «среднестатистическим» растром этого символа по рассматриваемой базе находится от минимального v_false_min до максимального v_false_max. В таблице 1 приведены значения этих величин для каждого из символов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, а также средняя оценка неправильного распознавания Р_false. Это оценка, с которой один из перечисленных символов принимается за какой-то другой. Следовательно, оценка, с которой он принимается сам за себя, еще ниже. Но даже приведенные оценки неправильного распознавания Р_false намного меньше (приблизительно в два раза), чем оценки правильного распознавания. Отметим, что для каждого из рассматриваемых символов v_true_min < v_false_min. Тем не менее, диапазон [v_true_min, v_true_max]  отличается от [v_false_min, v_false_max] не очень существенно. Следовательно, поскольку доля неправильно распознанных символов весьма незначительна, «дискретный» аналог функции распределения для всех изображений (распознанных как верно, так и неверно) каждого из символов 0, 1, … , 9 мало отличается от приведенных на рис.2б-11б.

Таблица 1

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

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

||v-u|| =                                                                                   (17)

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

 Делим отрезок [х_true_min, х_true_max] (оси абсцисс на рис.2в-11в) на 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в-11в). На этих рисунках видно, что средняя оценка распознавания для каждого из рассматриваемых символов на соответствующем этому символу отрезке [х_true_min, х_true_max] убывает монотонно (с некоторыми шумовыми погрешностями) по мере «удаления» от «среднестатистического» вектора, а для «1» сначала монотонно убывает,  а затем монотонно увеличивается и принимает максимальное значение 255 на предпоследнем интервале удаления от «среднестатистического» вектора (также с некоторыми погрешностями). Уровень шумов  в этих зависимостях существенно ниже, а, следовательно, степень монотонности выше, чем в аналогичных зависимостях для средней оценки распознавания при отклонении от «среднестатистического» растра.

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

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

Выше описаны результаты двух типов: в терминах растров и  полиномиальных векторов. Возникает вопрос, как их сравнивать? Для каждого символа одни и те же правильно распознанные изображения находятся в первом случае на отрезке [v_true_min, v_true_max], а во втором на  [х_true_min, х_true_max].  Предлагается идеология, основанная на преобразовании соответствующей оси абсцисс координаты посредством выравнивания по длине диапазонов отклонения растров / векторов правильно распознанных изображений каждого из символов от «среднестатистических» растра / вектора данного символа, а именно [v_true_min, v_true_max] и [х_true_min, х_true_max] . В этих целях вводятся «отнормированные» (по величине соответствующего диапазона) координаты.

Таблица 2

В таблице 1 приводятся значения величины v_true_max/v_true_min, а в таблице 2 – соответственно х_true_max/х_true_min. Сравнение показывает, что для каждого из символов v_true_max/v_true_min > х_true_max/х_true_min. Следовательно, как нетрудно показать, v_true_max/(v_true_max-v_true_min) < х_true_max/(х_true_max-х_true_min), а также v_true_min/(v_true_max-v_true_min)  <  х_true_min/(х_true_max-х_true_min). Эти два неравенства означают, что если на одном луче отложить «отнормированные» координаты v_true/(v_true_max-v_true_min) и х_true/(х_true_max-х_true_min), то v_true_max/(v_true_max-v_true_min) будет находиться левее (ближе к началу луча), чем х_true_max/(х_true_max-х_true_min); аналогично, v_true_min/(v_true_max-v_true_min)  будет левее (ближе к началу луча), чем  х_true_min/(х_true_max-х_true_min). Точка 0 (начало луча) соответствует  «среднестатистическому» растру   / вектору. Следовательно, в описанных «отнормированных» координатах для каждого из символов имеет место следующее: величина удаления отрезка, на котором находятся растры правильно распознанных  изображений, от  «среднестатистического» растра меньше, чем максимальное удаление отрезка векторов правильно распознанных  изображений от  «среднестатистического» вектора.

Сравним поведение оценки распознавания при отклонении от «среднестатистического» растра (рис.2а-11а) и вектора (рис.2в-11в). Как уже отмечалось, уровень шумов  в  диаграммах с вектором существенно ниже, а, следовательно, степень монотонности выше, чем в диаграммах с растром.

Для более детального сопоставления совместим отрезки между минимальным и максимальным отклонениями от «среднестатистических» растра [v_true_min, v_true_max]  и полиномиального вектора [х_true_min, х_true_max].  Математически это можно представить так, что точке с координатой  v_true на первом отрезке соответствует точка с координатой х_true=х_true_min+(v_true-v_true_min)·(х_true_max-х_true_min)/(v_true_max -  v_true_min). На рис.2д-11д  точка 0 соответствует минимальному отклонению от «среднестатистического» растра / вектора; здесь приведены графики, построенные по соответствующим диаграммам (рис.2а-11а, рис.2в-11в).  Вблизи точки 0 и до половины или до третьей части (в зависимости от символа) величины максимального отклонения от 0  средняя оценка распознавания для вектора выше, чем для растра. Для более отдаленных участков ситуация меняется на противоположную (в некоторых случаях для максимально удаленных участках указанная закономерность не выполнялось, но это неважно, т.к. количество находящихся там символов ничтожно, как видно на рис.2б-11б, рис.2г-11г).  Описанное поведение оценки распознавания наблюдалось для всех символов, кроме «1».

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

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

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

4. Выводы

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

Средняя оценка распознавания для каждого из рассматриваемых символов убывает монотонно (с некоторыми шумовыми погрешностями) по мере «удаления» от «среднестатистического» вектора, а для «1» сначала монотонно убывает,  а затем монотонно увеличивается и принимает максимальное значение 255 на предпоследнем интервале удаления от «среднестатистического» вектора (также с некоторыми погрешностями). Уровень шумов  в этих зависимостях существенно ниже, а, следовательно, степень монотонности выше, чем в зависимостях при отклонении от «среднестатистического» растра.

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

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

Литература

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

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

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

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

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

[6]     Nilson  N. J. Learning Machines, McGraw-Hill, New York, 1965.

[7]     Schürmann J. Polynomklassifikatoren, Oldenbourg, München, 1977.

[8]     Schürmann J. Pattern Сlassification,  John Wiley&Sons, Inc., 1996.

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

[10]   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.

[11]   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.

[12]   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.

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

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