ABOUT PRECEDENT IDENTIFICATION OF IMAGE FRAGMENTS SCANNED MANUSCRIPT

Full Text

Введение Технологии обработки изображений скани- рованных рукописных текстов (СРТ) разраба- тываются и постоянно развиваются. Основная направленность существующих технологий рас- познавании рукописных текстов состоит в том, чтобы превратить их в печатный, с которым затем можно работать средствами соответствующих текстовых процессоров. Несмотря на опреде- ленную закрытость сведений о математических основах и алгоритмах обработки изображений СКТ, можно отметить, что чаще всего использу- ются некоторые шаблоны рукописных букв, с по- мощью которых и реализуются решающие про- цедуры идентификации букв [1-5]. Ясно, что эти процедуры достаточно трудоемкие и невозможно избежать ошибок ввиду изменчивости почерка пишущего даже в одном документе. Причем речь идет о проверке справедливости многих гипотез. личиям фрагментов, сформированных в разные моменты времени при написании одних и тех же словоформ одним и тем же автором. Целью работы является создание для инфор- мационно-аналитических систем безопасности технологии обработки изображений СРТ, позво- ляющей по заданному фрагменту (прецеденту) отыскивать идентичные остальные. Прежде все- го речь может идти о фрагментах, образованных начертанием одного из слов (словные фрагмен- ты), которые будем называть ключевыми. Материалы и методы В рамках сложившейся терминологии такую технологию обработки изображений СРТ пред- ставляется естественным называть прецедентной идентификацией. Для создания такой технологии необходимо по крайней мере разработать: метод принятия решений о справедливости Очевидно, что процедура поиска фрагментов начальной гипотезы: H0 - сравниваемые фраг- СРТ, образованных заданной словоформой, яв- ляется более простой с точки зрения принятия решений, так как имеется в виду проверка толь- ко одной гипотезы об идентичности фрагмен- тов. В частности, в общем случае это приводит к уменьшению вероятностей ошибочных решений. С позиций математических основ решения такой задачи следует отметить, что в отличие от отдельных символов их совокупность в словном фрагменте представляет собой некоторую систе- му, обладающую вполне определенным совокуп- ным свойством. Таким свойством является квази- периодичность контуров символов (букв) вдоль строк, причем для каждой словоформы можно ожидать отличий в этой характеристике. Поэто- му естественной математической основой поис- ка идентичных фрагментов СРТ могут служить частотные представления в области простран- ственных частот, что реализуется с применением аппарата анализа Фурье. Имея в виду известное равенство Парсеваля между квадратами евклидо- вых норм фрагментов и их трансформант Фурье, можно показать, что квазипериодичность при- водит к повышенной концентрации последней в узких частотных диапазонах. Таким образом адекватной основой обработки СРТ является суб- полосный анализ. Современный подход к анали- зу Фурье предполагает явное вычисление трансформант Фурье или КИХ-фильтрацию [6]. Отличием предлагаемого в статье подхода к субполосному анализу является использование аппарата субполосных матриц [7-9]. Отметим, что такой подход позволяет обеспечить инвари- антность принятия решений к возможным отменты изображений идентичны заданному; метод обучения, позволяющий по одному прецеденту описать класс, которому принадле- жат идентичные фрагменты. Совокупность этих методов представляет со- бой метод прецедентной идентификации фраг- ментов сканированных изображений рукописного текста. Основу метода принятия решений составляет мера идентичности сравниваемых фрагментов, в которой используются так называемые призна- ки. Главное требование к набору признаков (при- знаковое пространство) состоит в адекватности отражения свойств прецедента с точки зрения эффективности описания класса идентичных ему фрагментов. Отметим, что эффективность долж- на оцениваться с позиций решающей процедуры. В общем случае используемые признаки в классе идентичных фрагментов (образованных одними и теми же словоформами) должны иметь малую изменчивость и достаточно резко изменяться при выходе из этого класса. Если принять во внимание трудности сегмен- тации фрагментов изображений рукописного тек- ста на буквы, то естественным подходом пред- ставляется сопоставление фрагментов в целом. Таким образом, при формировании пространства признаков необходимо отразить состав симво- лов фрагмента прецедента и последовательность их начертания. Иными словами, основную роль должна играть динамика изменений символов. Изменчивость начертаний символов даже од- ним и тем же человеком затрудняет использова- ние мер близости фрагментов в виде евклидовой нормы разности сравниваемых фрагментов. По- этому возникает необходимость поиска таких преобразований исходных данных, которые ма- M i (z) fik exp(- j(k -1)z). k 1 (8) лочувствительны к вариативности начертаний символов и стабильно отображают их состав и Пусть теперь строки фрагментов изображений близки в смысле выполнения тождества: последовательность начертания. i {1,..., N} i (z) (z), - z . (9) В рамках данной работы в качестве таких пре- образований предлагается использовать субпо- лосные представления в области пространствен- Тогда представление (7) дает выражение для спектра: X (z) sin(MzN / 2) / sin(Mz / 2) ных частот. exp(- jMz( N -1) / 2) (z). (10) Некоторые определения и соотношения Субполосные представления заключают- Очевидно, что квадрат модуля спектра вида определяется соотношением: 2 ся в следующем. Пусть матрица F { fik }, | X (z) | (sin(MzN / 2) / i 1,..., N : k 1,..., M состоит из значений пик- / sin(Mz / 2))2 | (z) |2 . (11) селей некоторого фрагмента изображения рукописного текста. В дальнейшем предполагается, что величина N определяется на этапе задания Таким образом, в спектре будут наблюдаться всплески в точках: прецедента (исходного словного фрагмента) и zk 2 k / M , k 0, 1,..., M / 2, (12) равна количеству занимаемых им строк, а M - ко- личество учитываемых столбцов соответственно. Очевидно, что количество вовлекаемых в анализ пикселей равно произведению этих чисел: где знаменатель (11) будет стремиться к нулю. С другой стороны, строки фрагмента также содержат символы, которые могут располагать- ся почти периодически на расстоянии ширины K N * M . (1) символов букв. Представляется, что все буквы, В этих условиях можно определить вектор написанные одним и тем же человеком, имеют близкую ширину и словный фрагмент содержит x (x1 ,..., xK ) ', где штрих означает транспонирование, а компоненты определяются соотношени- ями: их целое количество. Это приводит к тому, что точки максимумов (12) первого сомножителя в могут совпадать с максимумами последнего x f , , m 1,..., K , (2) сомножителя. Иными словами, возможна высогде m im km im [(m -1) / M ] 1; km m - [(m -1) / M ]* M . (3) кая концентрация энергии рассматриваемого век- тора в отдельных субполосах пространственных частот. Субполосный анализ векторов предполагает, Здесь и в дальнейших формулах квадратные скобки означают целую часть числа. Таким образом, имеется в виду построчное развертывание рассматриваемого фрагмента. Трансформанта Фурье (спектр) такого вектора что их свойства оцениваются, исходя из некото- рого разбиения области (6) на субполосы, кото- рые в рамках данной работы предлагается задать следующим образом: определяется соотношением: K X (z) xm exp(- j(m -1)z). m 1 (5) где 0 (- / K , / K ]; r (-(2r 1) / K , - (2r -1) / 3] ((2r -1) / 3,(2r 1) / K ]. (13) (14) Ясно, что спектр (5) является периодической функцией пространственной круговой частоты z. r 1,..., R [(K -1) / 2]. (15) Поэтому принято рассматривать только один сег- мент его области определения (основной лепе- сток): Основу математического аппарата субполосного анализа составляют субполосные матрицы [10; 11]: - z . (6) A {ar }, i, k 1,..., K , (16) Имея в виду соответствие (2), соотношению (5) можно придать следующий вид: N r ik элементы которых для рассматриваемого разби- ения частотной полосы определяются соотноше- ниями: X (z) exp(- j(i -1)Mz) i (z), i 1 (7) ik a0 sin( (i - k) / K ) / (17) где / (i - k), ii a0 1 / K; ar 2a0 cos(z (i - k )), r 1,..., R. (18) Иными словами, отрезки спектров совпадают, ik ik r Справедливы [10] соотношения, определя- ющие части энергий векторов, попадающие в вы- бранные субполосы: что является важным свойством и в дальнейшем используется при разработке решающей проце- дуры прецедентной идентификации фрагментов изображений. Pr (x) z r r | X (z) |2 dz / 2 x ' A x. (19) Принятие решений об идентичности Таким образом, субполосные матрицы явля- ются неотрицательно определенными, а их сим- метрия позволяет представить их в виде произ- ведения [12]: сравниваемых фрагментов В качестве основной характеристики преце- дента предлагается использовать понятие сово- купности информационных субполос вида (13) и A Q L Q' , (20) (14): r r r r r где Qr (q1 ...qK ) - ортогональная матрица собr r S r , r RS (32) ственных векторов, а Lr diag( 1 ,..., K ) - диагональная матрица собственных чисел, удовлет- воряющих условиям: которые удовлетворяют условиям: r x r P ( ) h , (33) Ar Qr Qr Lr . (21) где 2 1 2 K 1 r r ... r 0. (22) h0 2 || x || / K; hr 2h0 , r 0; (34) Подстановка (20) в (19) дает: K r k k RS - множество их индексов, а символ ||..|| озна- чает евклидову норму вектора. Совокупности информационных субполос со- P (x) r ( r )2 , k 1 (23) ответствует суммарная субполосная матрица: k где r - проекции вектора на собственные векто- AS Ar , (35) ры субполосной матрицы: r r k (qk , x) K i 1 r xi qik . (24) r RS которая также является симметричной и неот- рицательно определенной. Поэтому она также Важно отметить, что только часть собственпредставима в виде: A Q L Q' , (36) ных чисел субполосной матрицы может быть отлична от нуля [10]. То есть имеют место доста- точно точные равенства: S S S S причем собственные числа удовлетворяют (22) и часть из них близки к нулю: r k Jrj 0, k 1,..., K - Jr . (25) 0, S k JS k 1,..., K - JS . (37) При этом для матрицы с элементами (17) это Поэтому вектор количество определяется соотношением: yS Q1S 1S (38) J0 [K 0 / ] 4 5, (26) будет обладать свойством тогда как для остальных это значение удваивается: PS (x - yS ) 0. (39) Jr 2 * J0 10. Поэтому векторы: (27) Таким образом, для спектра вектора (37) вы- полняется тождество: r r r r r y Q1 Q1' x Q1 1 , (28) YS (z) X (z), z S . (40) где Q1r матрицы, которые состоят из части исгде S - объединение субполос, дополняющих ходных собственных векторов: совокупность S до полной области (6). r r Q1r (q1 ...qJ ), (29) Отметим, что матрица Q1S состоит из первых и 1 r r - часть соответствующих проекций на них, соответствующих ненулевым собственным чисудовлетворяют равенству: r yr x P ( - ) 0. (30) лам собственных векторов, а проекции на них определяются из соотношения ' Таким образом, в соответствии с определени- 1S Q1S x. (41) ем (19) для отрезков спектров исходного вектора и вектора (28) в среднеквадратическом смысле выполняются тождества: Использование неравенств вида (33) при формировании суммарной субполосной матрицы дает неравенство: 2 Yr (z) X (z), z r . (31) PS (x) PS (x) ||x || -PS (x), (42) Таким образом, неучитываемые субполосы содержат тем меньше энергии, чем больше энерто область значений, когда начальная гипотеза отвергается (критическая область), имеет вид гии приходится на информационные. G (h ,1). (49) Из равенства [10]: Для определения нижней границы критичеk S z S | GkS (z) |2 dz / 2 , (43) ской области используется обучение на основе некоторой выборки векторов. В данном случае где подынтегральная функция является спектром соответствующего собственного вектора, следу- ет, что учет в представлении (38) только ненуле- вых собственных чисел позволяет отфильтровать малоэнергетические компоненты, которые часто обусловлены шумами. необходимо на основе прецедента смоделировать обучающую выборку векторов, которые отвечают некоторому критерию идентичности. Такое моде- лирование принято называть аугментацией [13]. В качестве признака идентичности предлагается использовать условие Поэтому в качестве решающей функции (РФ) u y v , n 1,..., Nm, (50) при оценке идентичности с прецедентом векто- v где n S n (vn ,..., vn ) ' - векторы, состоящие из псевров u (u1 ,...,uK ) ' предлагается использовать n 1 K форму: JS дослучайных гауссовых чисел, квадраты евклидовых норм которых удовлетворяют равенству (x,u) 1 - | kS kS | / || 1S |||| 1S | |, k 1 (44) || v n S ||2 || x ||2 -P (x). (51) где имеется в виду вектор проекций β1 Q1' u. S (45) В качестве нижней границы критической области предлагается использовать максимальное значение РФ вида (44): q k Отметим, что если вектор S является собh max (x,un ), 1 n Nm, (52) ственным вектором субполосной матрицы (35), когда размер обучающей выборки удовлетворяет k то и -q S является собственным вектором с тем же равенству собственным числом. Поэтому абсолютные значения компонент векторов (41) и (45) равны про- Nm [1 / ] 1. (53) екциям сравниваемых векторов на собственные направления субполосной матрицы. При этом иг- норируются возможные фазовые сдвиги, обуслов- ленные неидентичностью написания символов. В качестве проверяемой начальной гипотезы, естественно, использовать следующее: H0 : сопо- ставляемые векторы идентичны. На основе неравенств между средним ариф- метическим и средним геометрическим и Коши- Шварца для (44) получаем неравенство: 0 (x,u) 1 - Здесь квадратная скобка снова означает целую часть числа. Заключение В рамках данной работы получены соотно- шения, определяющие решающую процедуру, которую предлагается использовать для поиска идентичных словных фрагментов изображений сканированного рукописного текста на основе од- ного из заранее заданных (прецедента). Алгоритм обработки изображений в рамках данной проце- JS S kS kS (46) дуры имеет следующие основные этапы: задание -J ( | k 1 |)1/ JS / || 1|||| 1||, прецедента и формирование вектора (2); на основе неравенств (33) формирование субполосной в котором равенство в левой части достигается при полной идентичности сравниваемых векто- ров. Ввиду изменчивости записей одной и той же словоформы такое значение РФ практически не- достижимо, и надо определять некоторое значе- ние (порог), когда выполняется неравенство для условной вероятности: матрицы вида (35); формирование векторов (38) и (41); с использование принципов аугментации (50) и (51) формирование обучающей выборки и вычисление границы критической области на ос- нове соотношений (52) и (53), предполагая, что вероятность ошибок первого рода задана. Исследования выполнены при поддержке Ver( (x ,u) h / u XX ) , (47) гранта 20-07-00241а. где символ Ver означает вероятность; XX - мно- жество идентичных векторов; наклонная черта означает условие; - вероятность ошибок пер- вого рода. Так как имеет место равенство

About the authors

E. G Zhilyakov

Belgorod State National Research University

Email: zhilyakov@bsu.edu.ru
Belgorod, Russian Federation

A. N Zalivin

Belgorod University of Cooperation of Economics and Law

Email: zalivin@bsu.edu.ru
Belgorod, Russian Federation

S. P Belov

Belgorod University of Cooperation of Economics and Law

Email: belovssergei@gmail.com
Belgorod, Russian Federation

D. A Chernomorets

Belgorod State National Research University

Email: chernomorets_d@bsu.edu.ru
Belgorod, Russian Federation

N. V Vasilyeva

Belgorod State National Research University

Email: vasileva@bsu.edu.ru
Belgorod, Russian Federation

References

Supplementary files