Содержание к диссертации
Введение
1 Геометрические искажения в изображениях текстовых документов и проблема их исправления 12
1.1 Постановка задачи 12
1.1.1 Изображение документа 12
1.1.2 Текст документа 14
1.1.3 Предобработка и нормализация изображения документа 17
1.1.4 Функция преобразования изображения 17
1.1.5 Математическая постановка задачи распрямления строк текста на изображении документа 19
1.1.6 Оценка результата при исправлении искажений 21
1.2 Анализ существующих решений 23
1.2.1 Выделение на изображении слов и строк текста 23
1.2.2 Построение функции искажения вертикальных границ текста... 25
1.2.3 Построение функции деформации строк текста 25
1.2.4 Общие замечания 27
1.3 Структура предлагаемого метода 28
2 Строковая сегментация и детектирование искажений в изображениях текстовых документов 33
2.1 Непрерывное гранично-скелетное представление изображения 33
2.1.1 Граница и скелет изображения 33
2.1.2 Скелет полигональной области и его свойства 35
2.1.3 Скелетный граф полигональной области 38
2.1.4 Внешний скелет изображения него свойства 39
2.2 Сегментация изображения текста на основе внешнего скелета 42
2.2.1 Предобработка изображения 42
2.2.2 Предобработка скелета 44
2.3 Выделение межстрочных ветвей скелета 47
2.3.1 Определение ветвей скелета и операций с ними 47
2.3.2 Кластеризация ребер скелета 52
2.4 Постобработка скелета 56
2.5 Сегментация отдельных строк текста 59
2.6 Аппроксимация строк документа 63
2.6.1 Построение аппроксимации ломаной линии кривой Безье 63
2.6.2 Аппроксимации строк текста кривыми Безье 66
2.7 Итерационная подгонка аппроксимации 68
2.7.1 Общее описание метода итерационной подгонки кривой 68
2.7.2 Нахождение ближайшей точки на кривой 70
2.7.3 Доказательство сходимости метода подгонки 71
2.8 Выводы по главе 2 74
3 Исправление геометрических искажений на основе аппроксимации их двухмерными патчами Безье 76
3.1 Использование метода аппроксимации в работе 76
3.2 Изменение параметризации кривой Безье 77
3.2.1 Постановка задачи 77
3.2.2 Растяжение параметров кривой Безье 79
3.2.3 Сдвиг параметров кривой Безье 80
3.3 Построение двумерного патча Безье на основе набора одномерных кривых 81
3.3.1 Постановка задачи 81
3.3.2 Метод аппроксимации семейства кривых патчем Безье 86
3.3.3 Аппроксимация набора кривых Безье по опорным точкам 90
3.3.4 Метод итерационной подгонки патча Безье 95
3.4 Исправление геометрических искажений на изображении текста.. 98
3.4.1 Общая процедура построения распрямленного изображения 98
3.4.2 Определение цвета пикселя 100
3.5 Выводы по главе 3 103
4 Программный комплекс и вычислительные эксперименты 104
4.1 Программная реализация алгоритма 104
4.1.1 Основные функции программной реализации 104
4.1.2 Описание программной реализации 105
4.1.3 Шаги алгоритма 106
4.1.4 Описание пунктов меню в главном окне 109
4.2 Результаты экспериментов 109
4.2.1 Основной эксперимент 109
4.2.2 Результаты эксперимента 114
4.2.3 Сравнение с мировым уровнем 116
Заключение 118
Список литературы 121
Приложение 1 127
- Анализ существующих решений
- Сегментация изображения текста на основе внешнего скелета
- Изменение параметризации кривой Безье
- Результаты экспериментов
Введение к работе
Оптическое распознавание символов (англ. Optical Character Recognition, OCR) — конвертация изображений символов и букв в текст, редактируемый на компьютере [7,8]. На вход системы оптического распознания текста приходит цифровое растровое изображение сканированного или сфотографированного документа, на выходе система должна сформировать текст, который содержит это изображение, в виде, пригодном для сохранения в одном из форматов электронных текстовых документов.
Оцифровка документов — это процесс перевода бумажных документов в электронный (цифровой) вид [7,8]. В зависимости от формата сохраняемых в компьютере документов (графического или тектового) различают два подхода к оцифровке:
Получение копий страниц в виде графических (обычно растровых) изображений, осуществляемое путём сканирования или фотографирования с последующей обработкой и сохранением в одном из форматов графических файлов. В этом случае полностью сохраняется оригинальная вёрстка документа и исключается появление каких-либо ошибок, связанных с переводом содержимого документа в текстовый формат. Однако при хранении документов в графическом формате невозможен контекстный поиск в архивах, а также извлечение фрагментов текста, например, для цитирования.
Оптическое распознавание текста с последующим сохранением полученного текста в одном из форматов электронных текстовьгх документов. В этом случае становится возможен полномасштабный текстовый поиск по документу и индексация больших массивов
5 электронных книг, однако затрудняется воспроизведение оригинальной вёрстки, изображений, схем и формул, практически неизбежными становятся ошибки распознавания.
В последнее время всё чаще применяется смешанный подход: текст документа распознаётся в автоматическом режиме и сохраняется вместе с оригинальными растровыми изображениями страниц, что позволяет совместить преимущества обоих подходов.
Ранее для получения электронной версии бумажных документов применялся ручной набор текст документа в электронном текстовом редакторе. Однако ручной набор — это очень долгий и дорогостоящий процесс по сравнению с автоматическим распознаванием текста.
Системы автоматического распознавания текста в электронных документах, оцифрованных с помощью сканеров, получили в настоящее время широкое распространение. Качество современных систем распознавания находится примерно на уровне 99% правильно распознанных символов для изображений с нормальным качеством. К сожалению, далеко не всегда документы, предназначенные для распознавания, бывают хорошо и ясно отсканированы. На качество распознавания влияет множество факторов. Среди наиболее важных факторов можно отметить качество печати в исходном документе, загрязненность исходного документа, размер шрифта в исходном документе, разрешающую способность сканирующего устройства, которая определяет размер символов шрифта в точках растрового изображения. Современные коммерческие системы распознавания текстов (такие как FineReader, OmniPage, Readlris) достаточно эффективно могут распознавать большинство изображений, полученных с помощью сканера.
Однако в настоящее время помимо задачи распознавания сканированных документов возникает задача распознавания документов, полученных с помощью цифровых фотокамер. Это связано с тем, что цифровые фотоаппараты получают все большее распространение. В частности, за последние несколько лет появилось достаточно большое количество систем для оцифровки документов, которые основаны на цифровых фотоаппаратах. Система на основе цифрового фотоаппарата работает в несколько раз быстрее обычного сканера, так как в нем не тратится время на физическое передвижение сканирующей планки. Однако использование цифровых фотоаппаратов для оцифровки текста создает много новых трудностей при распознавании текста. К примеру, из-за использования вспышки или плохого освещения часть изображения может быть затемнена, а часть наоборот слишком освещена. В результате использования недорогих камер и объективов («непрофессионального оборудования») или из-за плохих настроек изображение целиком или его часть может быть сильно размыта. Из-за использования слишком большого времени экспозиции изображение может быть смазано. Также одной из главных проблем современных фотоаппаратов является то, что они привносят геометрические искажения в изображения документа.
Нужно заметить, что проблема геометрических искажений на изображении документа существовала еще до начала широкого использования цифровых фотоаппаратов для оцифровки текста. В частности, при сканировании толстых книг очень часто возникают искажения на изображении страницы в области сгиба книги. Однако эти искажения имеют достаточно четко детектируемую и описываемую структуру. Поэтому для исправления искажений на сгибе книге придумано очень много различных методов и систем. Разработаны как методы
7 обработки и удаления искажений в оцифрованном изображении, так и специальные «книжные» сканеры, которые позволяют избежать искажений при сканировании книги (рассчитанные на то, что сканируемая книга раскрыта не полностью).
Однако с появлением и началом повсеместного использования цифровых фотоаппаратов проблема стала более сложной и актуальной. Искажения при фотографировании могут появиться по нескольким независимым друг от друга причинам. Это может быть недостатком используемой оптики - так называемый «эффект бочки». Другая причина состоит в том, что документ при фотографировании расположен не под прямым углом к оси камеры, что порождает перспективные искажения. Искажение также может быть вызвано неровностью исходного документа - к примеру, тем же изгибом в центре книги. Еще одна проблема заключается в том, что эти искажения могут комбинироваться между собой в любом сочетании. Из-за этого невозможно точно описать и предсказать модель искажения сфотографированного документа.
Большинство современных профессиональных систем распознавания текста (таких как FineReader, OmniPage, Readlris) рассчитаны на то, что строки текста на изображении будут прямыми и горизонтальными. Малейшие искажения строк текста приводят к сильному ухудшению качества распознавания. Поэтому в последнее время очень большое внимание уделяется методам, позволяющим устранять геометрические искажения в изображениях документов. В частности, в рамках самой крупной международной конференции по анализу и распознаванию документов ICDAR (International Conference on Document Analysis and Recognition) проводилось сравнительное тестирование методов распрямления текстовых строк на изображениях документов [10]. Метод,
8 описанный в диссертации, также принимал участие в этом тестировании в 2007 году [2]. Также в рамках тестирования впервые была сформирована большая общедоступная база документов с геометрическими искажениями [11]. Создание такой базы позволяет легко сравнивать между собой различные методы распрямления текстовых строк на изображении.
Однако, несмотря на возросший интерес к этой области и наличие большого количества новых методов устранения геометрических искажений ([15-24]), универсального метода для решения этой проблемы, который бы с одинаковой эффективностью устранял искажения на любых типах текстовых изображений, не было изобретено.
Таким образом, задача устранения геометрических искажений в изображениях текстовых документов является весьма актуальной и нуждается в разработке эффективных методов решения с использованием новых идей.
Целью настоящей работы является создание метода аппроксимации и устранения сложных разнообразных геометрических искажений на изображениях документов для повышения качества их распознавания. Сложность данной задачи определяется трудностями детектирования и формального описания разнообразных искажений текстовых документов, необходимостью построения универсального алгоритма коррекции документов, трудностью выбора критерия качества для решения поставленной задачи.
В практическом аспекте целью работы является создание программного комплекса для устранения геометрических искажений текстовых документов. Данный комплекс должен выполнить предобработку предоставленного ему изображения текстового документа с информацией о расположении текстовых блоков в документе и
9 сформировать новое изображение этого документа, в котором текстовые блоки имеют правильную прямоугольную форму, а строки текста расположены вдоль параллельных прямых линий.
Предлагаемый подход к решению задачи основывается на двух новых идеях. Первая идея относится к подзадаче выявления строковой структуры изображения. Предлагается осуществить сегментирование строк изображения путём выявления междустрочных просветов на основе построения и анализа внешнего скелета изображения текста в документе. Вторая идея относится к выбору вида геометрического преобразования изображения. Предлагаемый подход состоит в описании искажения в виде двумерного патча Безье. Эта модель обеспечивает большую гибкость настройки на различные типы сложных искажений.
Научная задача работы состоит в создании метода геометрических преобразований изображений текстовых документов на основе аппроксимации междустрочных просветов с помощью одномерных кривых Безье и общего преобразования изображения в виде двумерного патча Безье.
На защиту выносятся следующие положения.
Математическая модель описания искажений в виде непрерывной функции преобразования координат, представленной двухмерным патчем Безье.
Метод детектирования междустрочных просветов текста на основе «непрерывного» внешнего скелета изображения текстовых блоков.
Метод сегментации строк текста в изображении на основе найденных междустрочных просветов.
Метод аппроксимации междустрочных просветов и строк текста кубическими кривыми Безье.
Метод аппроксимации искажения всего документа с помощью двумерного патча Безье по набору одномерных кривых Безье, аппроксимирующих искривления отдельных междустрочных просветов.
Метод итерационной подгонки аппроксимирующего патча Безье.
Метод распрямления изображения документа на основе аппроксимации искажения документа.
Научная новизна работы определяется тем, что в рамках настоящего исследования впервые в интересах устранения геометрических искажений в текстовых электронных документах использованы следующие идеи:
Выполнена сегментация междустрочных просветов и строк в изображении текстового документа на основе непрерывного гранично-скелетного представления изображения, в частности, на основе анализа внешнего скелета текста;
Выполнена аппроксимация геометрических искажений всего документа в форме двумерного патча Безье;
Разработана вычислительная схема построения аппроксимирующего двумерного патча Безье на основе вычисления одномерных аппроксимирующих кривых Безье для междустрочных просветов и дальнейшей итерационной подгонки патча Безье.
Научная значимость работы состоит в описании геометрических искажений в изображениях текстовых документов с помощью математической модели двумерного патча Безье, а также в разработке метода параметрической настройки этой модели для конкретных данных.
Практическая значимость состоит в создании и реализации нового метода аппроксимации и удаления геометрических искажений в изображениях текстовых документов, обеспечивающего существенное повышение качества автоматического распознавания текстов.
Обоснованность и достоверность научных положений, выводов и результатов работы подтверждается корректным использованием математического аппарата непрерывного гранично-скелетного представления изображения, кривых и патчей Безье, строгими математическими доказательствами, программной реализацией и вычислительными экспериментами, а также успешным использованием разработанных моделей и методов при решении практических задач.
Основные результаты работы опубликованы в работах [1-6], в том числе в издании [1], входящем в список ВАК.
Анализ существующих решений
Для выделения на изображении строк или слов текста обычно используется следующая простая процедура. Изображение размывается с помощью сильного фильтра. Чем больше размывается изображение, тем более далекие черные объекты на изображении сливаются друг с другом. Предполагается, что для большинства документов расстояние между строками текста меньше, чем между соседними словами в одной строке. А расстояние между двумя словами в одной строке, меньше чем расстояние между двумя соседними буквами в пределах одного слова.
Соответственно, в зависимости от степени размытия изображения можно добиться того, что или все буквы внутри каждого слова на изображении сольются в один объект ([15,19]) или все слова внутри одной строки текста сольются в один объект ([16,17]).
Описанный метод весьма чувствителен к выбору степени размытия изображения и, если этот выбор сделан неточно, он может давать неправильные результаты. Поэтому иногда используются более сложные механизмы выделения строк. К примеру, строки текста могут выделяться с помощью итеративной процедуры, когда определяются некоторые начальные приближения для строк текста, а затем к строкам начинают последовательно добавляться близкие черные объекты и близкие строки текста начинают склеиваться между собой.
Также для большинства алгоритмов достаточно найти не строку текста, а какую-нибудь характерную линию, проходящую через всю строку текста. В качестве такой линии могут выступать как серединная линия строки (цепочка центральных черных точек в каждом вертикальном столбце пикселей в строке) — [16,17], так и базовая линия строки — линия, по которой написан текст в строке. Для нахождения базовой линии строк также иногда используется построение градиентного изображения, когда на изображении отмечаются только точки перехода по вертикали с черного на белое и назад ([18]).
Вертикальная линия границы текста является важным признаком для распрямления строк в изображении текстового документа. В большинстве работ по методам удаления геометрических искажений на изображениях документов не применяется сложных алгоритмов для определения искажения вертикальных границ текста.
В некоторых работах предполагается, что вертикальные границы текста вообще были не искажены (что все вертикальные прямые линии остались прямыми и вертикальными) — [19]. В других работах предполагается, что вертикальные прямые линии на изображении остаются прямыми, но могут идти не под прямым углом к направлению строк [15-18]. При этом для определения угла наклона вертикальных линий используется левая и правая границы текста ([16,17]) или информация об угле наклона вертикальных объектов на изображении (в частности высоких букв) - [15].
Очень важную роль при решении задачи играет выбор класса функций, описывающих возможное искажение изображения. Будем их называть функциями деформации. Для построения функции деформации строк текста обычно используются некоторые заранее определенные модели искажения изображения. В зависимости от первоначальной модели метод построения функции искажения может существенно отличаться.
К примеру, если на документе предполагаются только перспективные искажения (как при фотографировании плоского документа под углом), то в таком случае для определения искажения строк достаточно лишь найти точку схода для всех строк на изображении ([15]). При перспективном искажении все прямые линии, которые были параллельными на исходном изображении, преобразуются в набор прямых линий, пересекающихся в одной точке. Такая точка и называется точкой схода. Для нахождения точки схода строк текста достаточно взять линейную аппроксимацию каждого слова на изображении и найти, в какой точке пересекаются продолжения всех полученных отрезков.
Сегментация изображения текста на основе внешнего скелета
Черные объекты в обрабатываемом изображении — это буквы в тексте или отдельные части букв. Буквы объединены в слова. В словах буквы стоят на небольшом расстоянии, в несколько раз меньшем, чем расстояние между строчек текста. При этом даже на сильно искривленном тексте соседние буквы будут находиться по горизонтали приблизительно на одном уровне. Каждое слово текста для потребностей алгоритма удаления геометрических искажений лучше обрабатывать как единый объект -чтобы не работать с ребрами скелета изображения, лежащими между двумя соседними буквами в слове.
Для объединения соседних символов мы делаем черными короткие белые горизонтальные пропуски на изображении. Иными словами, если расстояние между двумя черными точками в одной строке пикселей меньше предопределенного порога, то мы заливаем черным цветом этот белый промежуток.
Максимальное расстояние между пикселями для заливки определяется пропорционально разрешению исходного изображения. В данной работе использовался порог в одну десятую разрешения, определенный эмпирически по тестовым изображениям. Описание тестовых изображений и описание проведенных экспериментов приведено далее в главе 4.
Разрешение изображения — это величина, показывающая, как пиксели на изображении соотносятся с размерами на реальном документе. Разрешение изображения измеряется обычно в пикселях на дюйм (dpi -pixels per inch). Для изображений, полученных с помощью сканера, разрешение всегда определено. Для цифровых фотографий в коммерческих системах распознавания текста (например, в FineReader 9) существуют специальные методы для определения разрешения.
К примеру, для изображения в 300 dpi (стандартное разрешение для сканированных документов) получается порог в 30 пикселей - то есть сливались вместе все объекты, расстояние по горизонтали между которыми на исходном документе было меньше 2,5 миллиметра. Примеры скелета на изображении без залитых строк и с заливанием показаны на рисунках 7-8.
Данная обработка позволяет избавиться от множества ненужных для разрабатываемого алгоритма ветвей скелета.
Стоит отметить, что предобработка делается на изображении только для построения скелета. Впоследствии, во время исправления геометрических искажений используется оригинальное изображение, а не обработанное изображение, по которому строился скелет.
Стоит отметить, что для потребностей алгоритма аппроксимации геометрических искажений изображения нужен только внешний скелет изображения. Поэтому внутренний скелет изображения просто не строится.
После того как скелет построен, часть ребер в нем можно удалить еще до классификации ребер на лежащие между объектами одной строки и объектами из разных строк. Не нужные для разрабатываемого алгоритма ребра скелета - это ребра, лежащие между различными частями одного объекта. Для удаления таких ребер можно использовать несколько разных методов.
Описанный выше процесс построения скелета позволяет запоминать в процессе работы, с какими объектами связано каждое ребро скелета. Поэтому удаление ребер, относящихся только к одному объекту, является тривиальной задачей.
Если информация об инцидентных ребру скелета объектах по каким-то причинам недоступна, то можно применить более сложный метод. Каждое конечное ребро скелета (ребро, заканчивающиеся конечным узлом скелета из которого не выходит других ребер) может принадлежать только одной связанной черной области (свойства 6 и 7 из раздела 2.1.4).
Процедура очистки скелета состоит в следующем: последовательно удаляются все конечные ребра скелета. У оставшихся ребер соответствующим образом корректируется информация о соседних ребрах. После удаления конечных ребер скелета все новые получившиеся конечные вершины будут инцидентны каждая только одному черному объекту (свойства 8 и 9 из раздела 2.1.4). Таким образом, можно повторить процедуру удаления конечных ребер, не потеряв при этом ребра, инцидентные двум различным объектам на изображении. Процедура повторяется до тех пор, пока в скелете не останется конечных ребер. С помощью данной процедуры из скелета будут удалены только ребра, инцидентные одному объекту.
Изменение параметризации кривой Безье
На некоторых этапах работы алгоритма требовалось построить вспомогательную аппроксимацию ветвей скелета с помощью кривых первого или второго порядка для определения различных параметров ветви. В таких случаях итерационная процедура не применялась. Аппроксимация строилась по предварительно определенным параметрам угловых точек ломаной линии. В частности, итерационная процедура не использовалась, когда нужно было строить линейные аппроксимации ветвей скелета для определения угла наклона ветви скелета. Также итерационная процедура не использовалась при построении квадратичной аппроксимации ветвей скелета для оценки искривления ветви.
Также итерационная процедура не использовалась при построении аппроксимации частей строк текста кривыми Безье. Так как количество черных пикселей в строке, которые нужно аппроксимировать было значительно больше, чем число вершин в стандартной ломаной междустрочной линии, то итерационная подгонка такой кривой становилась слишком затратным по времени механизмом. Итерационная процедура применялась при аппроксимации ветвей скелета кривыми Безье, при построении финальной аппроксимации ветвей кривыми третьего порядка, которые использовались для построения общего патча Безье, аппроксимирующего искажение исходного документа. В процессе работы описываемого алгоритма (в частности, во время создания двумерного патча Безье) необходимо менять параметризацию кривой Безье. Пусть есть некоторая кривая Безье Bn{t) = ЕЗДД( ). Нужно изменить ее параметризацию с отрезка [0,1] до отрезка [?,,/2]- Иными словами, нужно построить новую кривую Безье 5И(0 = ЕЗД,л (0 такую, что для любого t будет выполняться условие: Таким образом, решается следующая задача. Имеется кривая Безье B„{t) = YlPlbtn{t). Нужно изменить ее параметризацию с отрезка [0,1] до 1=0 отрезка [tx,t2]. То есть построить кривую Bn{i) = Y,P,bin(t), такую что: 1=0 Представим левую и правую часть приведенного выше выражения в виде обычного полинома от t (для этого нужно раскрыть скобки в полиномах Бернштейна bin (?)).
Чтобы равенство выполнялось для любого t, множители у каждой степени t должны быть равны между собой. Если приравнять эти множители друг другу, то получится линейная система относительно \р\ из 2 х п уравнений. Решая эту систему можно получить все координаты контрольных точек строящейся кривой. Для кубической кривой Безье полиномы Бернштейна будут представлены так с раскрытыми скобками: И в задаче изменения параметризации нужно найти такие координаты новых контрольных точек, что: Задачу изменения параметризации можно упростить, если решать ее в два этапа. Сначала параметры исходной кривой сжимаются в Ь раз. То есть параметризация меняется с отрезка [ОД] до отрезка [0,t2 -м]. Затем параметры сдвигаются на —м. То есть параметризация меняется с отрезка [0, t2 - tx ] до отрезка [м, , ]. Решается следующая задача. Имеется кривая Безье Bn(t)= Y,P,b, „ (/) Нужно растянуть ее параметры в а раз. То есть построить кривую BSt) = Если представить тоже уравнение в виде многочленов от t, то получится следующее выражение: Если в этом уравнении раскрыть скобки и приравнять коэффициенты при различных степенях t, то получится следующая система линейных уравнений: Если в этом уравнении раскрыть скобки и приравнять коэффициенты при различных степенях t, то получится следующая система линейных уравнений
Результаты экспериментов
Для определения корректности и проверки качества работы предложенного алгоритма была проведена серия экспериментов.
В качестве тестовой базы для проведения эксперимента была использована публичная тестовая база отсканированных изображений документов с геометрическими искажениями [11].
В тестовую базу входит 102 изображения. Каждое изображение — это сканированное изображение одной страницы из какой-либо книги. Все изображения черно-белые. На изображениях текст расположен в одну колонку с редкими включениями боковых сносок. На большинстве изображений текст занимает всю страницу. Размер текста на изображениях в среднем был 14 пунктов. Первые 11 изображений были отсканированы с разрешением в 300 dpi. Все остальные изображения были отсканированы с разрешением 450 dpi.
Эксперимент состоял в следующем: каждое изображение из тестовой базы распрямлялось с помощью описанного алгоритма. Затем с помощью программы FineReader 9.0 Professional распознавалось исходное изображение и распрямленное изображение. Программа FineReader 9.0 была выбрана за высокое качество распознавания (по разным оценкам это или самая точная система распознавания в мире для европейских языков или вторая по точности после OmniPage). Точность выбранной программы даже на плохих текстах позволяет надеяться, что главным фактором, влияющим на качество распознавания документов из тестовой базы, была именно степень выпрямления строк.
Оценивался процент исправленных за счет распрямления ошибок распознавания. Также оценивалась с помощью предложенного выше механизма степень искривления построенного на изображении патча Безье до и после распрямления.
В ходе эксперимента было проведено сравнение распрямления текста со сглаживанием (с созданием серого изображения) и без сглаживания (с созданием черно-белого изображения).
Пример одного изображения из тестовой базы и результаты удаления геометрических искажений на этом документе приведены на рисунках 35-36.
