Классификация графических объектов на иероглифических документах
Потребность в определении типов областей, найденных на изображении при распознавании текста. Рассмотрен подход к решению подобной задачи на примере анализа иероглифических документов. Приведены результаты экспериментальной апробации предложенного подхода.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 18.01.2018 |
| Размер файла | 43,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
КЛАССИФИКАЦИЯ ГРАФИЧЕСКИХ ОБЪЕКТОВ НА ИЕРОГЛИФИЧЕСКИХ ДОКУМЕНТАХ
К.Б. Стаценко (Konstantin_S@abbyy.com)
Московский физико-технический институт, Москва
Д.Г. Дерягин (Dmitry_D@abbyy.com)
А.В. Мякутин (Andrew_M@abbyy.com)
Компания ABBYY, Москва
Частью процесса распознавания текста является анализ структуры обрабатываемого документа. В ходе такого анализа возникает потребность в определении типов областей, найденных на изображении. В данной статье рассмотрен подход к решению подобной задачи на примере анализа иероглифических документов. В статье также приведены результаты экспериментальной апробации предложенного подхода.
Введение. Современное программное обеспечение для распознавания текста представляет собой сложный комплекс различных подсистем, отвечающих за те или иные его функции. Данная статья коснется одной из них, предназначенной для анализа документа. Она необходима для поиска и локализации графических объектов, таких как картинки, таблицы, рукописный и печатный текст, диаграммы и т.п. В статье затрагиваются подходы к решению задачи классификации отдельных символов и их последовательностей на печатных иероглифических документах. Описываемые здесь классификаторы предназначены для работы с фрагментами текста, в то время как другие полезные объекты (картинки, разделители) должны быть обработаны отдельно, и будут рассматриваться как мусор.
1. Постановка задачи
Будем рассматривать черно-белую страницу с черным текстом на белом фоне (участки белого текста на черном фоне должны быть предварительно инвертированы). В процессе низкоуровневой сегментации подобного изображения на нем выделяются объекты, которые могут оказаться фрагментами текста, оформления (элементами картинок или диаграмм, черными или точечными разделителями и т.п.) или мусором (неоднородности бумаги, посторонние объекты за краями сканируемого листа, тени в области переплета и т.п.). Они, как правило, представляют собой связные черные области или группы таких областей, объединенных исходя из их размеров и геометрического положения.
Каждый объект характеризуется вектором свойств p из шести элементов, соответствующих его ширине, высоте, количеству черных пикселей, количеству горизонтальных RLE штрихов, количеству вертикальных RLE штрихов и количеству белых дырок (RLE штрих представляет собой непрерывную последовательность черных пикселей и описывается двумя числами - начальной и конечной позициями). Свойства подсчитываются на этапе выделения и объединения черных областей, при этом в результирующем множестве могут одновременно присутствовать как составные, так и составляющие их объекты.
В результате классификации выделенных таким образом объектов, для каждого из них требуется определить, является ли он словом (цепочкой иероглифов), символом (отдельным иероглифом) или мусором, при этом отличать слово от символа не требуется (допускается одновременное отнесение объекта к обоим этим классам). Для описания принадлежности объектов к классам используется система качеств. Объект характеризуется двумя переменными, изменяющимися от нуля (худшее качество) до единицы (лучшее качество) которые соответствуют качествам символа и слова. Если обе они близки к нулю, то объект считается мусором.
2. Решение задачи
Чтобы вычислить искомые качества необходимо задать две функции вида F(p): X[0, 1] на множестве X векторов свойств. Для этого предлагается несколько подходов, объединенных общей идеей. В каждом из них искомая функция F(p) представляется с помощью набора простых функций fi(p), зависящих от некоторых параметров. Эти параметры предлагается определять при помощи различных алгоритмов неконтролируемой кластеризации.
Метод, основанный на алгоритме ISODATA
Описание метода. В первом из предлагаемых методов каждая функция F(p) представлялась с помощью набора простых функций fi(p), которые в свою очередь представлялись в виде произведения пороговой функции t(p, a, b, c, d) следующим образом:
(2.1)
где: pj - j-ая компонента вектора p; aij, bij, cijиdij - параметры пороговой функции; K - количество компонент p. Другими словами, F(p) помещает объект с вектором свойств p в один или несколько кластеров Nc, описываемых при помощи функций fi(p). Пороговая функциязадавалась следующим образом(2.2):
(2.2)
графический иероглифический документ
Отсюда видно, что каждый кластер представлял собой K-мерный параллелепипед с нечеткой границей, размеры и ширина границы которого задавались при помощи параметров aij, bij, cijиdij. Область, занимаемая такими кластерами в пространстве свойств, может иметь достаточно сложный вид, особенно, при большем их количестве. Это позволяет достаточно точно описывать подмножества объектов рассматриваемых типов (символы и слова), однако чрезмерное увеличение числа кластеров может привести к переобученности (overfitting) и замедляет работу классификатора.
Чтобы ограничить количество кластеров, необходимых для определения искомых функций и, в то же время, не утратить возможность описывать геометрически сложные области на множестве X векторов свойств pX, пороговая функция tвычислялась не от компонент p, а от значений признаков qj. Каждый признак задавался при помощи подбираемой экспериментально функции qj(p). В итоге выражение (2.1) приобрело следующий вид:
(2.3)
где K' - количество признаков, вообще говоря, не совпадающее с размерностью p.
Другими словами, функция F задавалась не на множестве свойств X, а на некотором множестве Y. Введение признаков, имеющих четкий физический смысл упрощало настройку и отладку классификатора.
Подбор признаков. Поскольку число исходных свойств было изначально фиксированным и небольшим, количество признаков также предполагалось ограничить пятью - семью. В этом случае создание автомата для подбора признаков было признано нецелесообразным.
На первом этапе подбора был сформирован ориентировочный набор признаков, которые казались наиболее полезными. В него вошли:
1. Отношение количества черного к полусумме количеств вертикальных и горизонтальных RLE штрихов (средняя толщина черты иероглифа).
2. Отношение ширины к высоте.
3. Количество белых связных областей (дублировал соответствующее свойство).
4. Отношение количества черного к площади объекта.
5. Полусумма количеств вертикальных и горизонтальных RLE штрихов (длинна границы черное/белое).
6. Отношение количества горизонтальных RLE штрихов к площади объекта (плотность горизонтальных RLE штрихов).
7. Отношение количества вертикальных RLE штрихов к площади объекта (плотность вертикальных RLE штрихов).
Все признаки нормировались так, чтобы все они были безразмерными величинами. Для выяснения значимости признаков проводилось сравнение качества классификации при использовании всех семи признаков с качеством классификации при использовании только шести из них. По результатам сравнения худший признак был удален. В результате повторного выполнения описанной процедуры был удален признак №7. В третий раз малоинформативных признаков процедура не выявила.
На втором этапе был рассмотрен набор новых признаков - кандидатов на включение, в него вошли:
1. Отношение количеств вертикальных и горизонтальных RLE штрихов.
2. Ширина объекта.
3. Высота объекта.
4. Отношение количества белых дырок к количеству черного (плотность дырок).
5. Отношение количества дырок к полусумме количеств вертикальных и горизонтальных RLE штрихов.
6. Отношение количества черного к произведению высоты объекта на количество вертикальных RLE штрихов (относительная средняя длинна вертикального RLE штриха).
7. Отношение количества черного к произведению ширины объекта на количество горизонтальных RLE штрихов (относительная средняя длинна горизонтального RLE штриха).
Полезность признаков нового набора оценивалась так же, как и предыдущего, с той лишь разницей, что признаки не исключались, а добавлялись. Исходным вариантом служил набор из пяти признаков, полученный в ходе предыдущего этапа настройки.
Таким образом, был получен окончательный перечень используемых признаков. Аналогичная процедура выполнялась и для классификатора на базе алгоритма EM, который будет описан ниже.
Обучение. Определение количества кластеров и их параметров осуществлялось автоматически в процессе обучения классификатора. Для этого использовался алгоритм неконтролируемой кластеризации ISODATA [Jainetal., 1999]. Его основная идея заключается в минимизации суммы квадратов расстояний до центров кластеров. При этом количество кластеров может меняться в ходе итеративного процесса вследствие разделения и слияния. Разделение кластера выполняется в том случае, если его дисперсия вдоль одной из координат превышает порог разделения. Слияние кластеров осуществляется, когда расстояние между их центрами оказывается меньше порога слияния.
После того как при помощи описанного алгоритма определялись координаты центров кластеров в пространстве признаков и наборы объектов из обучающей выборки, вошедших в каждый кластер, подбирались значения параметров aij, bij, cijиdij. Это делалось таким образом, чтобы j: j[1; K'] в пограничные интервалы (aij; bij) и (cij; dij) попал заданный небольшой процент точек i-го кластера, в то время как в интервал (aij; dij) должно было попасть большинство точек этого кластера.
Тестирование. Результаты работы построенного таким образом классификатора проверялись на тестовой выборке, состоящей из заранее разбитых по классам экземпляров слов, букв и мусора. В выборку входили тексты напечатанные различными шрифтами на японском, китайском и корейском языках. Слово считалось классифицированным «уверенно» если соответствующая оценка классификатора превышала 0,5, если оценка лежала в промежутке [0,5; 0,1] объект считался классифицированным «неуверенно», иначе «потерянным». Этот же принцип действовал и для символов. Мусор считался «отвергнутым» если наибольшая из двух оценок не превышает 0,1, если же она оказывается в промежутке [0,5; 0,1] то объект считался классифицированным «неуверенно», иначе «пропущенным». В таблице 1 приведены результаты проверки.
Табл.1.
|
Примененный классификатор |
Слов потеряно |
Слов неуверенно |
Символов потеряно |
Символов неуверенно |
Мусора пропущено |
Мусора неуверенно |
|
|
На основе алгоритма ISODATA |
4,8% |
5,1% |
0,35% |
1,8% |
1,1% |
1,8% |
|
|
На основе алгоритма ЕМ |
0,12% |
1,0% |
0,25% |
1,1% |
1,0% |
1,1% |
|
|
На основе алгоритма ЕМ с упрощенными признаками |
0,15% |
0,9% |
0,31% |
1,2% |
1,2% |
0,9% |
|
|
Упрощенный, на основе алгоритма ЕМ |
0,18% |
1,4% |
0,47% |
1,0% |
1,8% |
1,4% |
Описание метода. Для снижения требований к признакам и повышения надежности классификации был предложен второй подход. Он основан на аппроксимации искомых функций при помощи кластеров, которые описываются не как многомерные параллелепипеды, а при помощи многомерного нормального распределения:
, (2.4)
где i - радиус-вектор центра, а i - матрица ковариации i-ого кластера.
В этом случае искомые функции F(p) записываются как:
, (2.5)
, (2.6)
где i - вес i-ого кластера, индексы w, c и t соответствуют функциям для слов, символов и мусора, а q(p) - векторная функция с координатами qj(p). Как видно из (2.5), в отличие от (2.3), в расчете F(p) участвуют не только положительные, но и отрицательные примеры (в виде кластеров мусора t(q)).
Таким образом, если функции w,c,t(q(p)) будут описывать плотности вероятности pw,c,t в пространстве X с точностью до ненулевого множителя, зависящего только от p, то искомые оценки Fw(p) и Fc(p) будут иметь простой физический смысл. Они окажутся равными вероятностям того, что объект, имеющий свойства p, принадлежит к классам слов и символов соответственно. Если функция q-1:YXинъективная, непрерывно дифференцируемая и якобиан J(q-1)?0, то для выполнения вышеуказанного условия достаточно, чтобы функция (2.6) описывала плотность вероятности случайной величины q в пространстве Y.
Обучение. Пусть иероглифы делятся на группы в зависимости от особенностей их начертания (например, от количества штрихов) с вероятностями i. При условии, что иероглиф принадлежит одной из таких групп, будем рассматривать описывающую его случайную величину q как линейную комбинацию N независимых, нормально распределенных случайных величин (скрытых параметров) gi. Другими словами, будем описывать плотность иероглифов i-ой группы в пространстве признаков как (2.4), а относительную частоту встречаемости этой группы как i. В этом случае (2.6) будет соответствовать плотности вероятности q.
Используя метод наибольшего правдоподобия для нахождения неизвестных i, i и i, входящих в выражение (2.6), необходимо максимизировать функцию правдоподобия
Здесь - совокупность искомых переменных i,i и i, i[1;N], P(U,) - плотность вероятности совместного распределения U и , U - обучающая выборка, состоящая из M величин qi, J - скрытый параметр, описывающий распределение точек qj по классам. Для этого применялся алгоритм EM (ExpectationMaximization) [Рассел и др., 2007], [Dellaert, 2002], суть которого заключается в итеративной оптимизации значений искомых переменных в присутствии скрытых параметров, от которых необходимо избавиться интегрированием. Каждая итерация алгоритма состоит из двух шагов. На первом шаге (expectation) производится оценка распределения скрытых параметров, исходя из оценки значений искомых переменных, полученной в предыдущей итерации. На втором шаге (maximization) выполняется поиск новой оценки для искомых переменных, доставляющей максимум функции правдоподобия с учетом нового распределения скрытых параметров. Можно доказать [McLachlanet al., 1997], что данный алгоритм сойдется к локальному максимуму функции P(U,).
Тестирование. Предложенный классификатор проверялся при помощи того же метода и на тех же данных что и предыдущий. Во второй строке таблицы 1 приведены результаты проверки. Видно существенное увеличение качества классификации слов, а также улучшения по остальным параметрам в сравнении с результатами предыдущего классификатора. Для достижения этого результата использовалось шесть безразмерных признаков, подобранных при помощи описанного выше алгоритма. В третьей строке упомянутой таблицы приведены результаты классификации, при условии использования восьми признаков. Шесть из них были равны значениям свойств, а оставшиеся два: площади объекта и произведению количества горизонтальных RLE штрихов на длину. Поскольку классификатор способен обучатся произвольной линейной комбинации признаков, результаты лишь незначительно ухудшились. Два дополнительных признака представляли собой нелинейные компоненты наиболее значимых признаков, использовавшихся в предыдущем тестировании (относительного количества черного и относительной длины горизонтального RLE штриха).
К недостаткам описанного алгоритма можно отнести замедление процесса классификации приблизительно в 3 раза вследствие усложнения формул для расчетаF(p) и опасность возникновения переобученности из-за большого количества независимых переменных, параметризующих решающее правило.
Метод, основанный на алгоритме EM (упрощенный).
Описание метода. Для того чтобы устранить недостатки предыдущего метода, а именно, увеличить скорость классификации и уменьшить риск переобучения, но в то же время сохранить такие его достоинства как ясный физический смысл результата классификации и отсутствие необходимости особым образом нормировать признаки, был предложен третий метод. Так же как и предыдущий, он основан на аппроксимации искомых функций при помощи кластеров, которые описываются многомерными нормальными распределениями. Однако теперь, случайные величины, описываемые этими распределениями, считаются независимыми. В этом случае формула (2.4) будет выглядеть так:
,
где ji - j-аякомпонента радиус-вектора центра i-ого кластера, ji2 - дисперсия j-ой случайной величины, при условии, что она принадлежит i-ому кластеру, qjj-аякомпонента вектора q. Обучение данного классификатора основано на алгоритме EM и полностью аналогично описанному выше. В четвертой стоке таблицы 1 приведены результаты тестирования этого классификатора. Результаты говорят о том, что упрощенный EM в отличие от EM, не способен обучаться произвольным линейным комбинациям признаков, соответствующий их подбор вновь становится актуальным. Тем не менее, в отличие от классификатора на базе алгоритма ISODATA, отсутствует необходимость в специальном нормировании признаков. Альтернативой тщательному их подбору является увеличение количества кластеров.
Заключение. В данной статье были описаны три подхода к классификации графических объектов на странице. Метод на основе алгоритма ISODATA обладает большей скоростью, показывает неплохие результаты при различении отдельных иероглифов и мусора, но хуже справляется с классификацией слов и требует более тщательной подборки признаков. Метод на основе алгоритма EM более универсален, неприхотлив и точен, способен обучатся линейным комбинациям признаков, хотя требует большего времени для своей работы и может приводить к переобучению. Упрощенный метод на основе алгоритма EM сочетает в себе ряд достоинств и недостатков двух предыдущих, занимая промежуточную позицию. Он не способен обучатся линейным комбинациям признаков, однако не требует их нормирования, скорость его работы сравнима с первым классификатором, а количество обучаемых переменных существенно меньше чем у второго.
Список литературы
[Рассел и др., 2007] РасселС., НорвигП. Искусственный интеллект. Современныйподход. - М.:Вильямс, 2007 г.
[Dellaert, 2002]Dellaert. F. The Expectation Maximization Algorithm: Georgia Institute of Technology. Technical Report number GIT-GVU-02-20. 2002.
[Jain et al., 1999] JainA.K., MurtyM.N., FlynnP.J.. Data Clustering: A Review: ACM Computing Surveys. 1999. Т. 31, № 3.
[McLachlan et al., 1997] McLachlanG., KrishnanT. The EM algorithm and extensions: Wiley series in probability and statistics. John Wiley & Sons. 1997.
[Zheng et al., 2004] ZhengY., LiH., DoermannD. Machine Printed Text and Handwriting Identification in Noisy Document Images: Ieee transactions on pattern analysis and machine intelligence. 2004, т. 26, № 3.
Размещено на Allbest.ru
...Подобные документы
Существующие методы нахождения графических примитивов и программных реализаций. Базовое преобразование Хафа: поиск прямых, выделение окружностей на изображении, нахождение кривых высшего порядка. Составление руководства программиста и пользователя.
курсовая работа [2,7 M], добавлен 20.03.2012Практическое усвоение технологии вставки в текст документа разных графических объектов, созданных средствами Word и других дополнений MS Office. Схема алгоритма вычисления функции вида X=f(X)*E. Диалоговое окно. Вставка диаграммы.
лабораторная работа [162,8 K], добавлен 22.05.2007Задачи компьютерного зрения. Анализ, разработка и реализация алгоритмов поиска и определения движения объекта, его свойств и характеристик. Алгоритмы поиска и обработки найденных областей движения. Метод коррекции. Нахождение объекта по цветовому диапазон
статья [2,5 M], добавлен 29.09.2008Поведенческий подход к решению задачи определения внешнего вида ребенка по параметрам родителей. Принцип работы нейросимулятора. Проектирование персептронов, зависимость погрешностей обучения и обобщения от числа нейронов внутренних слоев персептрона.
презентация [208,1 K], добавлен 14.08.2013Виды графических редакторов. Форматы файлов для хранения растровых графических изображений. Среда графического редактора. Панели инструментов и режимы работы графических редакторов. Инструменты редактирования рисунка. Изменение шрифта текста на рисунке.
контрольная работа [246,6 K], добавлен 16.12.2010Общие сведения о текстовом редакторе Microsoft Word. Форматирование текста, настройка параметров абзаца, ввод символов. Средство создания списков, копирование и перемещение участков текста, работа со стилями, таблицами, вставка графических объектов.
реферат [60,5 K], добавлен 15.09.2009Графические возможности текстовых процессоров Microsoft Office Word и Open office.org. Вставка в документы рисунков и других объектов. Встраивание и связывание объектов. Преобразование текста посредством Microsoft WordArt. Виды графических объектов.
реферат [4,3 M], добавлен 17.06.2015Системный подход как метод анализа объектов в процессе проектирования, задачи: принятия оптимального решения, разбиение задачи на части. Анализ требований, предъявляемых к проектам технических систем: эргономические, патентно-правовые, экономические.
лекция [149,3 K], добавлен 13.08.2013Возможности Word по созданию и размещению графики в текстовых документах. Вставка объекта, созданного в другом графическом редакторе (Paint, Microsoft Drawing, Paintbrush). Создание растровых и векторных графических объектов. Рисунки из коллекции Clipart.
лабораторная работа [255,9 K], добавлен 15.11.2010Файлы BGI и содержимое модуля Graph, инициализация и закрытие графических режимов, их классификация, анализ и управление. Рисование графических примитивов и фигур, управление цветами и шаблонами, вывод текста, выбор шрифта и стиля, сжатия изображения.
реферат [65,3 K], добавлен 31.05.2010Разработка факультативного курса по редактированию графических объектов в программе GIMP. Основные понятия растровой графики, интерфейс программы, окна, диалоги и панели. Добавление отсутствующих элементов, Создание из фотографии "карандашного рисунка".
дипломная работа [5,5 M], добавлен 17.12.2012Тематический план курса разработки цифрового образовательного ресурса по технологии создания электронных графических документов (электронных книг). Особенности сканирования, программное обеспечение. Основные возможности программы ABBYY Fine Reader.
дипломная работа [3,7 M], добавлен 07.07.2011Защита информации и ее сжатие. Поиск, распознавание информационных объектов (текста и образов). Роль ключа в шифровании. Прогнозирование временных рядов. Классификация документов, выбор и оценка многокритериальных альтернатив. Принятие решений и вывод.
реферат [140,1 K], добавлен 19.10.2008Создание Web-документов (от простейших статических до документов на основе динамического HTML): форматирование текста, создание списков, таблиц, встраивание различных объектов, использование средств интерактивного общения с пользователем.
методичка [45,5 K], добавлен 27.10.2010Стандартная и каноническая форма записи задачи линейного программирования. Ее запись на листе MS Excel. Математическая модель транспортной задачи, состоящей в определении оптимального плана перевозок некоторого однородного груза, результаты ее решения.
контрольная работа [1,1 M], добавлен 25.01.2016Описание математических методов представления и обработки графических изображений. Описание разработанного программного дополнения. Описание функций и их атрибутов. Представление и обработка графических изображений. Результаты тестирования программы.
курсовая работа [1,7 M], добавлен 27.01.2015Описание решения задачи, ее постановка, общий подход к решению. Представление исходных данных, условий задачи и целей ее решения. Составление алгоритма решения поставленной задачи. Написание программного обеспечения и тестирование конечного продукта.
курсовая работа [1,1 M], добавлен 03.07.2011Рассмотрение особенностей работы с текстовым редактором Microsoft Word: описание возможностей ввода, редактирования, форматирования текста, запуска и настройки редактора формул, вставки изображений, графических объектов, рисунков, создания таблиц.
контрольная работа [1002,5 K], добавлен 31.03.2010Обзор алгоритмов распознания объектов на двумерных изображениях. Выбор языка программирования. Обнаружение устойчивых признаков изображения. Исследование алгоритмов поиска объектов на плоскости. Модификация алгоритма поиска максимума дискретной функции.
дипломная работа [1,0 M], добавлен 16.06.2013Форматирование текста, работа с таблицами. Добавление графических объектов в документ. Создание формул, построение диаграмм. Основные приемы работы в электронных таблицах Excel. Графические возможности в Microsoft Word. Решений нелинейных уравнений.
контрольная работа [743,9 K], добавлен 27.05.2013
