В статье описываются результаты исследования по созданию универсальной программной системы для автоматизированного распознавания исторических рукописных текстов, включая исторические стенограммы XIX и начала XX веков. Рассматривается проблема получения оригинальной графики символов исторических рукописных документов, поиск схожих график в базе знаний, определения строк текста, приводится математическая модель дешифровки стенограмм. Кроме этого описывается прототип автоматизированной системы распознания рукописных исторических документов.
Проблема понимания текстов - один из важнейших вопросов истории. На сегодняшний день в архивах России накопился большой объем нерасшифрованных стенографических документов. Современные стенографисты и ученые испытывают существенные проблемы при дешифровке историических стенограмм. Во-первых, в XIX и начале XX веков стенография в России находилась в процессе становления, поэтому существующие документы зашифрованы в разных системах. Современная стенография существенно отличается от исторических систем стенографии XIX века, и нет специалистов, обладающих знаниями о системах стенографической записи того времени. Еще одной трудностью дешифровки является то, что стенографист при шифровании мог использовать свои нестандартные символы (обозначения), так как часто расшифровкой занимался тоже он. Кроме того, некоторые символы стенографической записи имеют схожее написание, но в зависимости от некоторых физических параметров, например, таких как размеры, имеют разные значения. Труды 14-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» — RCDL-2012, Переславль-Залесский, Россия, 15-18 октября 2012 г.
Автоматизация дешифровки исторических стенограмм состоит из следующих шагов: бинаризация исторических рукописных доку
ментов; создание БД графики стенографических симво
лов; кластеризация изображений стенографических
символов; создание базы знаний стенографических симво
лов; методы выделения строк в рукописных истории
ческих документах; поиск символа в базе знаний; математическая модель распознавания символа. 2 Бинаризация исторических рукописных документов
Из-за состаренности рукописных материалов и того что стенографические записи сделаны простым карандашом на пожелтевшей бумаге возникает проблема с бинаризацией изображения. Пороговый метод по цветовым компонентам (RBG), оказался не приемлемый для данной задачи, так как пиксели фона и символов имеют схожие значения цветовых компонент. Как видно на гистограммах (рис. 1) отсутствие двух явно выраженных пиков не позволяет выбрать пороговое значение для бинаризации. Такие же результаты получаются (рис. 1), если использовать разложение по цветовой схеме HSB (оттенок, насыщенность, яркость). Производя бинаризацию только по пороговому значению яркости, можно получить достаточно четкие символы, с малым количеством шума. Аналогичные результаты получены в [6] при распознавании банковских чеков.
рис. 1 Гистограммы цветовых схем
RGB (а) и HBS (б) Кроме того, был опробован метод бинаризации Оцу [3], но он так же как и предыдущие методы не давал хороших результатов при бинаризации, т.к. отсутствовали два явно выраженных пика. В нашем случае хорошее качество бинаризации дал метод с экспериментально найденным пороговым значением яркости 13% относительно общего числа пикселей. 3 База данных оригинальной графики стенографических символов
Для распознания стенограмм необходимы оригинальные символы, который использовал стенографист в своих записях, так как стенографист мог видоизменять и модернизировать символы стенографической системы, которую он использовал. Выделение символов на рукописных исторических документах имеет следующие особенности: оригинальное изображение удовлетворительного качества из-за следующего ряда причин: - рукописям порядка 150 лет; - запись производилась простым карандашом на пожелтевшей бумаге, которая имеет различные повреждения (перегибы, разрывы, просвечивание надписей с другой стороны листа); - наличие сторонних записей, пометок, которые не носят смысловой нагрузки, но пересекаются со стенографическими записями. при бинаризации происходили разрывы символов, т.к. некоторые пиксели символа имели схожий цвет с пикселями бумаги; при сегментации возникала необходимость разбиения символов, написанных слитно, на отдельные символы.
Было написано приложение позволяющее получать оригинальную графику символов из стенограмм. Как видно из рис. 2, на котором представлен интерфейс данного приложения, основное рабочее окно разделено на две части. В левой части находится оригинальное изображение стенограммы, из которой нужно получить графики символов. В правой части находятся уже полученные графики символов, причем они располагаются с полым соответствием расположения на оригинальном изображении.
Для создания оригинальной графики символа, пользователь должен выделить символ на оригинальном изображении и нажать на "горячую клавишу" или их комбинацию. Далее приложение производит бинаризацию и сегментацию выделенного фрагмента. Если при сегментации было получено несколько сегментов, то приложение предлагает пользователю выбрать, те, которые, по его мнению, соответствуют данному символу, и система производит связывание [4] "разорванных частей". Если пользователя не устраивает результат, то он может быть отредактирован во встроенном графическом редакторе. После этого система производит поиск в базе данных ранее полученных график символов, схожие, и предлагает пользователю выбрать, если нет схожих символ добавляется в базу данных. рис. 2 Интерфейс модуля создания оригинальной
графики символов.
Было обработано 29 листов стенографических записей и получено более 2500 изображений символов. После этого возникла задача их кластеризации. 4 Кластеризация изображений стенографических символов
Для решения этой задачи были проанализированы следующие методы сравнения символов:
Поиск с использование эталона заключатся в том, что изображение символа используется как шаблон и сравнивается с изображениями других символов. При сравнении изображений вычисляется расстояние Хэмминга. ρ( x, y ) = D( x, y )⊕G( x, y ), x = 1..w, y = 1..h
Формально это означает сравнения значений каждого пикселя изображения первого символа со значением соответствующего пикселя второго символа. При этом значения принадлежат множеству {0,1}. Значения пикселей логически складываются, после чего происходит подсчет уровня совпадения, который равен числу нулей в полученной матрице, разделенному на общее число точек. Если полученный уровень превосходит заданный порог, то изображения считаются схожими.
При пороговых значениях уровня совпадения от 80% данный метод обладает высокой точностью поиска, но при этом полнота поиска крайне мала. Логическое сравнение с эталоном показывает плохие результаты для сложных символов, что происходит из-за того, что человек пишет символы по-разному. Меняются углы, размер и толщина символа. При сравнении скелетов символов исключается различие толщины символов, но усиливается различие в зависимости от других факторов написания символа. Скелетизация символов производилась алгоритмом Зонга Суня [5].
Метод сравнения расстояний является быстрым методом сравнения символов. Принцип данного метода заключается в построении отрезков по заранее заданному правилу и определение их длин. После вычисления длины заносятся в базу данных. В работе мы использовали метод краевых расстояний. Принцип работы метода краевых расстояний заключается в следующем, из базы знаний выбираются символы отношения высоты к ширине которых находится в некоторой окрестности. Это позволяет сократить множество символов, в котором осуществляется поиск. У текущего символа измеряются длины отрезков {l1,l2,…,l8} (см. рис. 3). Далее длины отрезков текущего символа сравниваются с отрезками из базы данных. Расстояние между символами измеряется как эвклидово расстояние между полученными отрезками.
рис. 4 Сравнение расстояний.
Метод моментов основан на вычислении
расстояний между моментами изображений. Мы
использовали инвариантные моменты Ху [2].
Рассмотрим процесс вычисления моментов Ху.
Пусть f(x,y) функция интенсивности точек
бинарного изображения, которая принимает значения «0»
и «1» (где «0» – черный цвет, а «1» - белый). При
сравнении изображений мы работаем с
дискретными величинами, поэтому от непрерывного
значения момента (
∞ ∞
M pq= −∫∞ −∫∞ x p yq f ( x , y ) dxdy, p , q= 0,1 ,2 , .. . (
M pq= ∑ ∑ x p yq f ( x , y ) (
μ pq = ∑ ∑ ( x − x ) p( y− y )q f ( x , y ) (
μ pq
η pq инвариантен при
масштабировании. В формуле (
Ниже приведены моменты Ху, которые инвариантны при сдвиге, масштабировании и повороте. На основании полученных данных был сделан вывод, что моменты Ху не позволяют определить, похожи стенографические символы или нет.
Комбинированный метод представляет собой линейную комбинацию с весовыми коэффициентами, описанных выше методов. Точность описанных выше методов оказалась недостаточной и, поэтому, была применена модификация метода "сравнения контуров", приведенного в [1]. Примененная модификация метода заключается в следующем. На контуре символа случайным образом выбирается 100 точек. Для каждой точки строиться круговая гистограмма, состоящая из 60 областей. Подсчитывается количество, попавших точек из 100 выбранных, в каждую из областей. Расстояние между множествами точек на двух изображениях ищется как хи-квадрат. С помощью "венгерского метода" подбирается такая комбинация попарной связи точек, которая минимизирует суммарное расстояние. Это расстояние и является расстоянием между двумя изображениями. Проведенные эксперименты показали, что расстояние между одинаковыми символами колеблется от 200 до 500, между похожими от 450 до 900, между +( 3η21 η03 )(η21 + η03 )[ 3(η30 + η12 )2 (η21 + η03 )2 ] φ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 ] Одинаковые символы расстояние Hu1 0,2147 0,2094 0,2176 0,2117 0,1938
Hu5
Hu2 0,0139 0,0109 0,0136 0,0053 0,0034
Hu6
Hu3 1,5925E
05 1,8696E
05 5,6078 3,0727E
05 5,6286E06
Hu4 1,2413E
05 1,7896E
05 4,3674E
05 9,3077E
06 4,7169E
06
Hu7 3,5408E-11 1,7090E-10
8,5411E-07 3,1893E-10 1,2221E-06
-7,3859E-11 2,1551E-09 3,6388E-06
-1,6609E-10 1,5224E-10 1,6644E-07
3,9974E-11 2,4304E-11 7,9079E-08
1,5291E-13 рис. 1 Значения моментов В ходе исследования были вычислены моменты Ху для коллекции стенографических символов. Как видно из рис. 5, разброс значений конкретных моментов для похожих символов может различаться на несколько порядков, в то время как значения различных символов могут быть значительно ближе.
рис. 6 Метод сравнения контуров.
Кластеризация полученных изображений осуществлялась методом иерархического кластерного анализа, используя полученную таблицу расстояний между выделенными изображениями. Таким образом, были выделены 395 кластеров. Общее количество кластеров превышает число стенографических символов, так как текст содержит цифры и буквы (слова, записанные обычным образом). 5 Методы выделения строк в рукописных исторических документах
При распознании стенограмм появилась проблема выделения строк (линий). Выделение строк является одним из ключевых в расшифровки стенограмм, так как значение символа зависит от его места нахождения в строке. Символы могут быть: надстрочными, подстрочными, и обычные. Так как стенограммы писались на нелинованных листах, с большим количеством исправлений и зачеркиваний, а так же с искривлением строки, поэтому в тексте сложно выделить явно выраженные строки.
Для выделения строк были испробованы следующие методы: Проекция центров тяжести символов. Были спроецированы центры тяжестей символов, но не возможно было выделить ярко выраженные пики, т.к. строки имеют кривизну; Проекция черных пикселей символов. При проекции черных стали более выделены пики соответствующие строками (см. рис. 8 верхний). Но при искривлении строк, а так же при большом количество зачеркиваний и исправлений, некоторые строки не соответствуют пикам (см. рис. 8 нижний); Алгоритм поиска ближайшего символа в строке.
Символ считается ближайшим, если символ находится от текущего в секторе 60 градусов с наименьшим расстоянием. Вес близости символа рассчитывается по формуле: где d – угол между прямой соединяющей центры символов и осью ОХ, k – коэффициент схожести , l – расстояние до символа (см. рис. 7). Из-за подстрочных и надстрочных символов некоторые символы не соответствовали строке или же происходит пропуск символов. Рис. 7. Результат работы алгоритма поиска
ближайшего символа Не один из выше перечисленных методов, не дает правильный результат в случае с рукописными историческими документами. Для выделения строк используется комбинированный алгоритм на основе поиска ближайшего символа в рамках строк, полученных сочетанием алгоритмов проекции черных символов и центров символов. Данный алгоритм был обучен на порядке 100 строк, выделенных из пяти разобранных документов. 6 Математическая модель распознавания символа
Основной задачей в расшифровке документов – это сопоставление каждому символу его значение, но каждый символ может иметь несколько значений, либо же схожие по написанию символы могут иметь совершенно разные значения. Для данной задачи была составлена математическая модель, но на данном этапе исследования, пока не достаточно информации для проверки эффективности её работы.
Обозначим через x1,, xn последовательность стенографических очень часто определяются
символов. К стенографические неоднозначно. Для сожалению, символы символа xk обозначим через xk ,, xlk множество его
1 k возможных распознаваний. Каждому распознанному символу xik на основании БЗ ставиться в соответствии ки y1ki ,, ymkiki . примет вид y1i1 ,, y njin .
j1 n его возможные
трактовРис. 8. Проекция черных пикселей символов
Ставится задача найти такой набор индексов,
чтобы вероятность правильного распознавания была
максимальной.
max Rxik , xk Rxikk , xk
max Rxik , xk
1ilk
В первом слагаемом правой части формулы (
ik
его возможным эталонным значением. Во втором
слагаемом правой части формулы (
ik3 k означает частоту появления комбинации символов xk3 xik в стенограммах.
ik3 k
Второе слагаемое в правой части формулы (
P ykik jk yk3ik3yk1ik-1 jk3 jk1 k3ik3 ykik
N y jk3 jk N yk3ik3 yk1ik-1 1 jk3 jk1
, где
k3ik3 ykik N y jk3 jk частота
появления фрагмента текста yk3ik3 y kjik . Данная оценка
jk3 k производится на основании анализа текстов автора,
(
На рис. 9 представлен интерфейс прототипа автоматизированной системы распознавания рукописных исторических документов в виде Webприложения. Система имеет 3 рабочих области. Область оригинального изображения стенограммы, область разобранной стенограммы, область с расшифрованным текстом стенограммы, а также всплывающее окно с возможными вариантами расшифровки символа. рис. 9 Интерфейс прототипа Web-приложения автоматизированной системы распознания
рукописных исторических документов При выделении символа на оригинальной стенограмме, выделенный фрагмент бинаризуется, сегментируется и выделяется символ. Во второй области отображается в соответствующем месте. Далее в третьей области отображается дешифрованный текущий символ, с возможными альтернативными вариантами дешифрования. Система, анализируя исходное изображение при вводе символов, производит автоматическое дешифрование схожих символов или групп символов.
Данное web-приложение находится на этапе прототипа, в котором реализованы основные этапы получения графики символа для его расшифровки. 8 Заключение
На данном этапе разработки автоматизированной системы распознания исторических рукописных документов следующее: было реализовано и
получено Был реализован и внедрен модуль получение оригинальной графики символов, использованных при написании стенограмм Сниткиной. Было обработано порядка 25 стенограмм и было получено более 3 тысяч график символов; Был разработан алгоритм для выделения строк в стенограммах, но данный алгоритм требует универсализации, т.к. корректность выделения строк зависит от подбора параметров, которые различны на различных стенограммах; Разработанная математическая модель дешифровки текста проходит апробирование, которое затруднено тем, что словарь значений стенографических символов в настоящий момент находится на этапе наполнения. Наполнение происходит исходя из правил описанных в учебнике [7], по которому обучалась Сниткина; Создан прототип системы в виде 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 manuscripts, including historical shorthand records dating back to the 19th and early 20th centuries. We discuss the problem of getting the original graphical representation of symbols from historical manuscripts using a threshold digitization method. We search for a similar graphical representation of symbols in the database. Moreover we present a prototype of a computerized recognition system of historical manuscripts.