О дешифровке рукописных исторических документов © А. А. Рогов © А. В. Скабин © И. А. Штеркель Петрозаводский Государственный Университет, Петрозаводск rogov@psu.karelia.ru artb00g@gmail.com shterkel_ivan@psu.karelia.ru Аннотация Таким образом, для введения в научный оборот В статье описываются результаты новых документов необходимо описание и исследования по созданию универсальной дешифровка исторических стенограмм. Для программной системы для автоматизиро- решения этой задачи необходимо создать ванного распознавания исторических руко- универсальную программную систему писных текстов, включая исторические автоматизированного распознавания исторических стенограммы XIX и начала XX веков. рукописных текстов, включая исторические Рассматривается проблема получения ори- стенограммы XIX и начала XX веков. К гинальной графики символов исторических отличительным свойствам разрабатываемой рукописных документов, поиск схожих системы относятся: учет индивидуальных знаков график в базе знаний, определения строк разных стенографистов, возможность критического текста, приводится математическая модель анализа, использование словаря для подсказки при дешифровки стенограмм. Кроме этого опи- дешифровке текста и т.д. [8]. Информационная сывается прототип автоматизированной система будет находиться в открытом доступе и системы распознания рукописных истори- предлагаться к использованию работниками ческих документов. архивов, научными сотрудниками, исследователями текстологам. Отлаживать систему было принято Данное исследование поддержано грантом решение на стенограммах А.Г. Сниткиной, частично РГНФ № 11-01-12026в. расшифрованных Ц. М. Пошемянской, и учебнике 1 Введение П. Ольхина [7]. Автоматизация дешифровки исторических Проблема понимания текстов - один из стенограмм состоит из следующих шагов: важнейших вопросов истории. На сегодняшний день  бинаризация исторических рукописных доку- в архивах России накопился большой объем ментов; нерасшифрованных стенографических документов. Современные стенографисты и ученые испытывают  создание БД графики стенографических симво- существенные проблемы при дешифровке истории- лов; ческих стенограмм. Во-первых, в XIX и начале XX  кластеризация изображений стенографических веков стенография в России находилась в процессе символов; становления, поэтому существующие документы  создание базы знаний стенографических симво- зашифрованы в разных системах. Современная лов; стенография существенно отличается от исторических систем стенографии XIX века, и нет  методы выделения строк в рукописных истории- специалистов, обладающих знаниями о системах ческих документах; стенографической записи того времени. Еще одной  поиск символа в базе знаний; трудностью дешифровки является то, что стено-  математическая модель распознавания символа. графист при шифровании мог использовать свои нестандартные символы (обозначения), так как часто расшифровкой занимался тоже он. Кроме 2 Бинаризация исторических того, некоторые символы стенографической записи рукописных документов имеют схожее написание, но в зависимости от Из-за состаренности рукописных материалов и некоторых физических параметров, например, таких того что стенографические записи сделаны простым как размеры, имеют разные значения. карандашом на пожелтевшей бумаге возникает проблема с бинаризацией изображения. Пороговый Труды 14-й Всероссийской научной конференции метод по цветовым компонентам (RBG), оказался не «Электронные библиотеки: перспективные методы и приемлемый для данной задачи, так как пиксели технологии, электронные коллекции» — RCDL-2012, Переславль-Залесский, Россия, 15-18 октября 2012 г. фона и символов имеют схожие значения цветовых 74 компонент. Как видно на гистограммах (рис. 1) Было написано приложение позволяющее отсутствие двух явно выраженных пиков не получать оригинальную графику символов из стено- позволяет выбрать пороговое значение для грамм. Как видно из рис. 2, на котором представлен бинаризации. Такие же результаты получаются (рис. интерфейс данного приложения, основное рабочее 1), если использовать разложение по цветовой схеме окно разделено на две части. В левой части HSB (оттенок, насыщенность, яркость). Производя находится оригинальное изображение стенограммы, бинаризацию только по пороговому значению из которой нужно получить графики символов. В яркости, можно получить достаточно четкие симво- правой части находятся уже полученные графики лы, с малым количеством шума. Аналогичные символов, причем они располагаются с полым результаты получены в [6] при распознавании соответствием расположения на оригинальном банковских чеков. изображении. Для создания оригинальной графики символа, пользователь должен выделить символ на оригинальном изображении и нажать на "горячую клавишу" или их комбинацию. Далее приложение производит бинаризацию и сегментацию выделен- ного фрагмента. Если при сегментации было получено несколько сегментов, то приложение предлагает пользователю выбрать, те, которые, по его мнению, соответствуют данному символу, и система производит связывание [4] "разорванных частей". Если пользователя не устраивает результат, то он может быть отредактирован во встроенном рис. 1 Гистограммы цветовых схем графическом редакторе. После этого система произ- RGB (а) и HBS (б) водит поиск в базе данных ранее полученных Кроме того, был опробован метод бинаризации график символов, схожие, и предлагает пользова- Оцу [3], но он так же как и предыдущие методы не телю выбрать, если нет схожих символ добавляется давал хороших результатов при бинаризации, т.к. в базу данных. отсутствовали два явно выраженных пика. В нашем случае хорошее качество бинаризации дал метод с экспериментально найденным пороговым значением яркости 13% относительно общего числа пикселей. 3 База данных оригинальной графики стенографических символов Для распознания стенограмм необходимы оригинальные символы, который использовал стенографист в своих записях, так как стенографист мог видоизменять и модернизировать символы стен- ографической системы, которую он использовал. Выделение символов на рукописных исторических документах имеет следующие особенности:  оригинальное изображение удовлетворительного качества из-за следующего ряда причин: - рукописям порядка 150 лет; - запись производилась простым карандашом на рис. 2 Интерфейс модуля создания оригинальной пожелтевшей бумаге, которая имеет различные графики символов. повреждения (перегибы, разрывы, просвечива- ние надписей с другой стороны листа); - наличие сторонних записей, пометок, которые Было обработано 29 листов стенографических не носят смысловой нагрузки, но пересекаются записей и получено более 2500 изображений со стенографическими записями. символов. После этого возникла задача их класте- ризации.  при бинаризации происходили разрывы символов, т.к. некоторые пиксели символа имели схожий 4 Кластеризация изображений цвет с пикселями бумаги; стенографических символов  при сегментации возникала необходимость разбиения символов, написанных слитно, на Для решения этой задачи были проанализиро- отдельные символы. ваны следующие методы сравнения символов: 75  логическое сравнение с эталоном;  сравнение со скелетом эталона;  метод сравнения расстояний;  метод моментов  комбинированный метод;  сравнения контуров. Поиск с использование эталона заключатся в том, что изображение символа используется как шаблон и сравнивается с изображениями других рис. 3 Метод краевых расстояний. символов. При сравнении изображений вычисляется Проведенные испытания показали, что для расстояние Хэмминга. большинства похожих символов исследуемой ρ( x, y ) = D( x, y )⊕G( x, y ), x = 1..w, y = 1..h коллекции расстояние не превышает значения 100. Примеры приведены на рис. 4. Формально это означает сравнения значений каждого пикселя изображения первого символа со значением соответствующего пикселя второго Похожие символы расстояние символа. При этом значения принадлежат множеству {0,1}. Значения пикселей логически складываются, после чего происходит подсчет 23.6 уровня совпадения, который равен числу нулей в полученной матрице, разделенному на общее число точек. Если полученный уровень превосходит заданный порог, то изображения считаются 57.3 схожими. При пороговых значениях уровня совпадения от 80% данный метод обладает высокой точностью Разные символы расстояние поиска, но при этом полнота поиска крайне мала. Логическое сравнение с эталоном показывает пло- хие результаты для сложных символов, что 121.8 происходит из-за того, что человек пишет символы по-разному. Меняются углы, размер и толщина символа. При сравнении скелетов символов исключается различие толщины символов, но усиливается различие в зависимости от других фак- 128.2 торов написания символа. Скелетизация символов производилась алгоритмом Зонга Суня [5]. Метод сравнения расстояний является быстрым рис. 4 Сравнение расстояний. методом сравнения символов. Принцип данного метода заключается в построении отрезков по заранее заданному правилу и определение их длин. Метод моментов основан на вычислении После вычисления длины заносятся в базу данных. расстояний между моментами изображений. Мы В работе мы использовали метод краевых использовали инвариантные моменты Ху [2]. расстояний. Принцип работы метода краевых Рассмотрим процесс вычисления моментов Ху. расстояний заключается в следующем, из базы Пусть f(x,y) функция интенсивности точек бинар- знаний выбираются символы отношения высоты к ного изображения, которая принимает значения «0» ширине которых находится в некоторой окрест- и «1» (где «0» – черный цвет, а «1» - белый). При ности. Это позволяет сократить множество сравнении изображений мы работаем с символов, в котором осуществляется поиск. У дискретными величинами, поэтому от непрерывного текущего символа измеряются длины отрезков значения момента (1) мы переходим к дискретному {l1,l2,…,l8} (см. рис. 3). Далее длины отрезков теку- случаю (2). Значение p – порядок x, q – порядок y. щего символа сравниваются с отрезками из базы данных. Расстояние между символами измеряется ∞ ∞ как эвклидово расстояние между полученными M pq = ∫ ∫ x p y q f ( x , y ) dxdy, p , q= 0,1 ,2 , .. . ( 1 ) −∞ − ∞ отрезками. M pq= ∑ ∑ x p y q f ( x , y ) (2 ) x y 76 Далее переходим к центральным моментам, На основании полученных данных был сделан которые инвариантны при сдвиге изображения. вывод, что моменты Ху не позволяют определить, похожи стенографические символы или нет. μ pq = ∑ ∑ ( x − x ) p ( y− y )q f ( x , y ) ( 3) Комбинированный метод представляет собой x y линейную комбинацию с весовыми коэффици- μ pq ентами, описанных выше методов. Точность η pq = (4) описанных выше методов оказалась недостаточной μ ( 1+ p+q 2 ) и, поэтому, была применена модификация метода 00 "сравнения контуров", приведенного в [1]. Примененная модификация метода заключается в Момент η pq инвариантен при масштабирова- следующем. На контуре символа случайным нии. В формуле (4) μ 00 интерпретируется как образом выбирается 100 точек. Для каждой точки полная масса изображения. строиться круговая гистограмма, состоящая из 60 Ниже приведены моменты Ху, которые областей. Подсчитывается количество, попавших инвариантны при сдвиге, масштабировании и точек из 100 выбранных, в каждую из областей. повороте. Расстояние между множествами точек на двух изображениях ищется как хи-квадрат. С помощью φ1 = η 20 + η 02 "венгерского метода" подбирается такая комби- φ 2 = (η 20 + η 02 ) 2 + 4η11 2 нация попарной связи точек, которая минимизирует суммарное расстояние. Это расстояние и является φ3 = (η30  3η12 ) 2 + (η 21  μ 03 ) 2 расстоянием между двумя изображениями. Прове- φ 4 = (η30  3η12 ) 2 + (η 21 + μ 03 ) 2 денные эксперименты показали, что расстояние φ5 = (η30  3η12 )(η30 + η12 )[(η30 + η12 ) 2  3(η 21 + η 03 ) 2 ] между одинаковыми символами колеблется от 200 + ( 3η 21  η 03 )(η 21 + η 03 )[ 3(η30 + η12 ) 2  (η 21 + η 03 ) 2 ] до 500, между похожими от 450 до 900, между φ6 = (η 20  η 02 )[(η30 + η12 ) 2  (η 21 + η 03 ) 2 ] + 4η11 (η30 + η12 )(η 21 + η 03 ) разными от 900. Примеры приведены на рис. 6. φ7 = ( 3η 21  η 03 )(η 21 + η 03 )[ 3(η30 + η12 ) 2  (η 21 + η 03 ) 2 ] Одинаковые символы расстояние  (η30  3η12 )(η 21 + η 03 )[ 3(η30 + η12 ) 2  (η 21 + η 03 ) 2 ] 405 Hu1 Hu2 Hu3 Hu4 1,5925E- 1,2413E- 0,2147 0,0139 05 05 297 1,8696E- 1,7896E- 0,2094 0,0109 05 05 Похожие символы расстояние 4,3674E- 0,2176 0,0136 5,6078 05 547 3,0727E- 9,3077E- 0,2117 0,0053 05 06 5,6286E- 4,7169E- 0,1938 0,0034 06 06 662 Hu5 Hu6 Hu7 Разные символы расстояние 1,7090E-10 8,5411E-07 3,5408E-11 1222 3,1893E-10 1,2221E-06 -7,3859E-11 2,1551E-09 3,6388E-06 -1,6609E-10 1343 1,5224E-10 1,6644E-07 3,9974E-11 рис. 6 Метод сравнения контуров. 2,4304E-11 7,9079E-08 1,5291E-13 Кластеризация полученных изображений рис. 1 Значения моментов осуществлялась методом иерархического кластер- ного анализа, используя полученную таблицу В ходе исследования были вычислены моменты расстояний между выделенными изображениями. Ху для коллекции стенографических символов. Как Таким образом, были выделены 395 кластеров. видно из рис. 5, разброс значений конкретных Общее количество кластеров превышает число моментов для похожих символов может различаться стенографических символов, так как текст содержит на несколько порядков, в то время как значения цифры и буквы (слова, записанные обычным различных символов могут быть значительно ближе. образом). 77 5 Методы выделения строк в 6 Математическая модель рукописных исторических документах распознавания символа При распознании стенограмм появилась пробле- Основной задачей в расшифровке документов – ма выделения строк (линий). Выделение строк это сопоставление каждому символу его значение, является одним из ключевых в расшифровки но каждый символ может иметь несколько значе- стенограмм, так как значение символа зависит от его ний, либо же схожие по написанию символы могут места нахождения в строке. Символы могут быть: иметь совершенно разные значения. Для данной надстрочными, подстрочными, и обычные. Так как задачи была составлена математическая модель, но стенограммы писались на нелинованных листах, с на данном этапе исследования, пока не достаточно большим количеством исправлений и зачерки- информации для проверки эффективности её ваний, а так же с искривлением строки, поэтому в работы. тексте сложно выделить явно выраженные строки. Обозначим через x1 ,, xn последовательность Для выделения строк были испробованы следую- щие методы: стенографических символов. К сожалению, очень часто стенографические символы  Проекция центров тяжести символов. Были определяются неоднозначно. Для символа спроецированы центры тяжестей символов, но не возможно было выделить ярко выраженные xk обозначим через x1k ,, xlkk множество его пики, т.к. строки имеют кривизну; возможных распознаваний. Каждому распознан-  Проекция черных пикселей символов. При k ному символу xi на основании БЗ ставиться в проекции черных стали более выделены пики соответствии его возможные трактов- соответствующие строками (см. рис. 8 верхний). ki ki Но при искривлении строк, а так же при ки y1 ,, ymki . Тогда распознанный текст большом количество зачеркиваний и 1i ni исправлений, некоторые строки не примет вид y j 1 ,, y j n . 1 n соответствуют пикам (см. рис. 8 нижний);  Алгоритм поиска ближайшего символа в строке. Символ считается ближайшим, если символ находится от текущего в секторе 60 градусов с наименьшим расстоянием. Вес близости символа рассчитывается по формуле: где d – угол между прямой соединяющей центры символов и осью ОХ, k – коэффициент схожести , l – расстояние до символа (см. рис. 7). Из-за подстрочных и надстрочных символов некоторые символы не соответствовали строке или же происходит пропуск символов. Рис. 7. Результат работы алгоритма поиска ближайшего символа Не один из выше перечисленных методов, не дает правильный результат в случае с рукописными историческими документами. Для выделения строк используется комбинированный алгоритм на основе поиска ближайшего символа в рамках строк, полученных сочетанием алгоритмов проекции Рис. 8. Проекция черных пикселей символов черных символов и центров символов. Данный алгоритм был обучен на порядке 100 строк, выделенных из пяти разобранных документов. Ставится задача найти такой набор индексов, чтобы вероятность правильного распознавания была максимальной. 78  1 * ni*  P y1ji*1  y j*i1  max P y1ji1  y nijn , где максимум n  1 n  в данном случае Ф.М. Достоевского. Оценка k-го сомножителя при k  3 производится аналогично. берется по всем Коэффициенты a, b настраиваются в зависимости 1  i1  l1 , 1  j1  m1i1 ,, 1  in  ln , от качества распознавания стенограммы. 1  jn  mnin . Оценим вероятность P y j 1  y j n .  1i 1 ni n  7 Прототип Web-приложения системы На основании формулы Байеса она равна автоматизированной системы       распознания рукописных исторических P y1ji1  y nijn = P y1ij1  P y nijn 1i  n 1i  (1) документов 1 n 1  n y j 1 y j n -1   1 n 1  На рис. 9 представлен интерфейс прототипа Оценка k-го (k>3) сомножителя в правой части автоматизированной системы распознавания формулы (1) имеет вид: рукописных исторических документов в виде Web-   приложения. Система имеет 3 рабочих области. P y kijk 1i  k 1i   aP xikk x k 3 x k 1   Область оригинального изображения стенограммы,  i k 1  область разобранной стенограммы, область с  k y j 1 y j k -1  ik  3  1 k 1  расшифрованным текстом стенограммы, а также всплывающее окно с возможными вариантами   1  a P y kijkk  k 3 ik 3 k 1ik -1  расшифровки символа. (2)  y y   j k 3 j k 1  Первое слагаемое в правой части формулы (2) характеризует точность распознавания стенографического символа. Оно вычисляется как взвешенная сумма: max Rx , x  Rx , x  k k i k ik k P x   b 1 i  l k max Rx , x  k ik xik  3 xik 1   k 3 k 1  k i k 1 i  l k 1  b N x  k 3 ik  3 x k ik  .  N x k 3 ik  3 x k 1 ik 1  1 (3) В первом слагаемом правой части формулы (3)   R xikk , xk означает расстояние между символом и его возможным эталонным значением. Во втором слагаемом правой части формулы (3) N xik 3  xik  k 3 k  рис. 9 Интерфейс прототипа Web-приложения автоматизированной системы распознания означает частоту появления комбинации символов рукописных исторических документов xikk 33  xikk в стенограммах. При выделении символа на оригинальной Второе слагаемое в правой части формулы (2) стенограмме, выделенный фрагмент бинаризуется, характеризует вероятность появления данного сегментируется и выделяется символ. Во второй фрагмента текста. Оно оценивается как области отображается в соответствующем месте.   Далее в третьей области отображается дешифро-  kik  P y j  k  3  i  k 1 ik -1   ванный текущий символ, с возможными альтерна-  k y k  3 y  тивными вариантами дешифрования. Система,  j k 3 j k 1  анализируя исходное изображение при вводе  N y jk 3ik 3  y kijk  , символов, производит автоматическое дешифрова-   1 k 3 k ние схожих символов или групп символов. N y jk 3ik 3  y jk 1ik -1 Данное web-приложение находится на этапе k 3 k 1   частота появления прототипа, в котором реализованы основные этапы где N y jk 3ik 3  y kijk получения графики символа для его расшифровки. k 3 k k 3ik 3 8 Заключение фрагмента текста y j  y kijk . Данная оценка k 3 k производится на основании анализа текстов автора, На данном этапе разработки автоматизированной системы распознания исторических рукописных 79 документов было реализовано и получено [5] Zhang, T.Y. A fast parallel algorithm for thinning следующее: digital patterns / T. Y. Zhang, C. Y. Suen //  Был реализован и внедрен модуль получение Commun. ACM. − 1984. − Vol. 27, №3. – P. 236- оригинальной графики символов, использован- 239. ных при написании стенограмм Сниткиной. [6] Горский Н., Анисимов В., Горская Л. Распозна- Было обработано порядка 25 стенограмм и было вание рукописного текста: от теории к практи- получено более 3 тысяч график символов; ке. – СПб.: Политехника, 1997 г.  Был разработан алгоритм для выделения строк в [7] Ольхин П. Руководство к русской стеногра- стенограммах, но данный алгоритм требует фии. - СПб.: Типография доктора М. Хана, универсализации, т.к. корректность выделения 1866 г строк зависит от подбора параметров, которые [8] Рогов А.А., Скабин А.В., Талбонен А.Н., различны на различных стенограммах; Штеркель И.А. Некоторые особенности созда- ния автоматизированной системы дешифровки  Разработанная математическая модель дешиф- исторических стенограмм //Интернет и совре- ровки текста проходит апробирование, которое менное общество: сборник научных статей. затруднено тем, что словарь значений стено- Материалы XIV Всероссийской объединенной графических символов в настоящий момент находится на этапе наполнения. Наполнение конференции «Интернет и современное происходит исходя из правил описанных в общество». Санкт-Петербург, 12-14 октября учебнике [7], по которому обучалась Сниткина; 2011 г. – СПб.: Из-во ООО «МультиПро- жектСистемСервис», 2011. – С. 132-138.  Создан прототип системы в виде web- приложения. Данный прототип не является окончательным и самостоятельным программ- About the the decoding of handwritten мным продуктом, он требует доработки, опти- мизации, для удобной работы пользо-вателей с historical documents ним. Aleksandr Rogov, Artem Skabin, Ivan Shterkel Литература The article describes the process of creating a universal computerized recognition system of historical [1] Belongie, S.; Malik, J.; Puzicha, J.; , "Shape manuscripts, including historical shorthand records matching and object recognition using shape dating back to the 19th and early 20th centuries. We contexts," Pattern Analysis and Machine discuss the problem of getting the original graphical Intelligence, IEEE Transactions on , vol.24, no.4, representation of symbols from historical manuscripts pp.509-522, Apr 2002 using a threshold digitization method. We search for a [2] Hu M.K. Visual pattern recognition by moment similar graphical representation of symbols in the invariants. / M.K. Hu // IRE Transactions on database. Moreover we present a prototype of a Information Theory 8 − 1962 – P. 179–187. computerized recognition system of historical [3] N. Otsu (1979). «A threshold selection method manuscripts. from gray-level histograms». IEEE Trans. Sys., Man., Cyber. 9: 62-66 [4] P Nagabhushan, Basavaraj S Anami. A know- ledge-based approach for recognition of handwriting Pitman shorthand language storkes. / P Nagabhushan, Basavaraj S Anami // Sadhana. – 2002. - Vol. 27, Part 5. -P. 685–698. 80