автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Численные методы детектирования и исправления геометрических искажений в изображениях текстовых документов

На правах рукописи 004603845

Масалович Антон Андреевич

Численные методы детектирования и исправления геометрических искажений в изображениях текстовых документов

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2010

1 о ИЮН 2010

004603845

Работа выполнена на кафедре Математических Методов Прогнозирования факультета Вычислительной Математики и Кибернетики Московского Государственного университета имени М.В. Ломоносова.

Научный руководитель:

Доктор технических наук, профессор J1.M. Местецкий

Официальные оппоненты:

Доктор физико-математических наук Ю.В. Визильтер Кандидат технических наук И.А. Рейер

Ведущая организация:

Московский физико-технический институт (государственный университет)

Защита состоится 10 июня 2010 г. в 15 часов на заседании диссертационного совета Д 002.017.02 при Учреждении Российской академии наук Вычислительный центр им. A.A. Дородницына РАН по адресу: Москва, улица Вавилова, дом 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра им. A.A. Дородницына Российской академии наук

Автореферат разослан 5 мая 2010 г.

Ученый секретарь диссертационного совета Д 002.017.02, д. ф.-м. н., профессор

В.В. Рязанов

Общая характеристика работы

Предметом настоящего исследования является разработка математического метода компенсации геометрических искажений при оптическом распознавании текстовых документов на основе непрерывного гранично-скелетного представления изображения, создание комплекса программной реализации данного метода и его апробация.

Системы автоматического распознавания текста в электронных документах, оцифрованных с помощью сканеров, получили в настоящее время широкое распространение. При этом современные коммерческие системы распознавания текстов (такие как FineReader, OmniPage, Readlris) достаточно эффективно могут исправлять геометрические искажения документов, полученные при сканировании (такие как искажения в области сгиба книги), и с высоким качеством распознавать большинство отсканированных изображений.

Но в настоящее время помимо задачи распознавания сканированных документов возникает задача распознавания документов, полученных с помощью цифровых фотокамер и камер мобильных телефонов. Это связано с тем, что цифровые фотоаппараты получают все большее распространение. Однако использование цифровых фотоаппаратов для оцифровки текста создает много новых трудностей при распознавании текста. Одной из главных проблем современных фотоаппаратов является то, что они привносят сильные геометрические искажения в изображения документа.

Искажения при фотографировании могут появиться по нескольким независимым друг от друга причинам. Это может быть недостатком используемой оптики - так называемый «эффект бочки». Другая причина состоит в том, что документ при фотографировании расположен не под прямым углом к оси камеры, что порождает перспективные искажения. Искажение также может быть вызвано неровностью исходного документа - к примеру, тем же изгибом в центре книги. При этом перечисленные искажения могут комбинироваться между собой в любом сочетании. Из-за этого невозможно точно описать и предсказать модель искажения сфотографированного документа.

Большинство современных профессиональных систем распознавания текста (в частности, наиболее распространенные системы FineReader, OmniPage, Readlris) рассчитаны на то, что строки текста на изображении будут прямыми и горизонтальными. Малейшие искажения строк текста приводят к сильному ухудшению качества распознавания. Поэтому в последнее время очень большое внимание уделяется методам, позволяющим устранять геометрические искажения в изображениях документов.

В частности можно перечислить следующие работы: Xu-Cheng Yin, Jun Sun, Satoshi Naoi, 2007; Bin Fu, Minghui Wu, Rongfeng Li, Wenxin Li, Zhuoqun Xu, Chunxu Yang, 2007; D. C. Schneider, M. Block, R. Rojas, 2007; В. Gatos, I. Pratikakís, К. Ntirogiannis, 2007, H. Ezaki, S. Uchida, A. Asano, H. Sakoe, 2005; U. Ulges, C. H. Lampert, T. M. Breuel, 2005; Li Zhang, Chew Lim Tan, 2005; A. Yamashita, A. Kawarago, T. Kaneko, K.T. Muira, 2004; M.S. Brown, W.B. Seales; 2004.

Однако, несмотря на возросший интерес к этой области и наличие большого количества различных подходов, универсального алгоритма для решения проблемы геометрических искажений, который бы с одинаковой эффективностью устранял искажения на любых типах текстовых изображений, не было изобретено.

Задачу распрямления искаженных строк в изображении документа обычно разделяют на две подзадачи: выделения и описания строчной структуры в изображении и построения преобразования изображения, при котором эти выявленные строки превратятся в прямолинейные. Известные методы устранения геометрических искажений имеют существенные недостатки при решении обеих подзадач.

Для определения строковой структуры обычно вычисляются базовые линии текста (линии нижней и верхней границ строчных символов). Однако достоверное определение базовых линий представляет собой весьма сложную задачу. Наличие свисающих и выступающих элементов в символах шрифта, знаков препинания и диакритических символов, а также коротких слов в строках приводят к большим ошибкам в определении базовых линий. Неточности в их определении приводят к неправильному описанию строковой структуры.

Описание распрямляющего преобразования обычно осуществляется на основе некоторой параметрической модели заданного класса, например, перспективного искажения, либо цилиндрического искажения внутреннего края страниц книги. Если фактическое искажение не относится к этому классу, то выбранная модель не позволяет подобрать хорошее распрямляющее преобразование. В результате известные методы не являются универсальными, могут исправлять только какой-то ограниченный класс искажений документов, к примеру, перспективные искажения или искажения от сгиба страницы у края книги.

Необходимость разработки новых более универсальных методов устранения геометрических искажений широкого класса, возникающих при сканировании и фотографировании документов, определяют актуальность темы данного исследования.

Целью настоящей работы является создание метода аппроксимации и устранения сложных разнообразных геометрических искажений на изображениях документов для повышения качества их распознавания. Сложность данной задачи определяется трудностями детектирования и формального описания разнообразных искажений текстовых документов, необходимостью построения универсального алгоритма коррекции документов, трудностью выбора критерия качества для решения поставленной задачи.

В практическом аспекте целью работы является создание программного комплекса для устранения геометрических искажений текстовых документов. Данный комплекс должен выполнить предобработку предоставленного ему изображения текстового документа с информацией о расположении текстовых блоков в документе и сформировать новое изображение этого документа, в котором текстовые блоки будут иметь правильную прямоугольную форму, а строки текста расположены вдоль параллельных прямых линий.

Предлагаемый подход к решению задачи основывается на двух новых идеях. Первая идея относится к подзадаче выявления строковой структуры изображения. Предлагается осуществить сегментирование строк изображения путём выявления междустрочных просветов на основе построения и анализа внешнего скелета

3

изображения текста в документе. Вторая идея относится к выбору вида геометрического преобразования изображения. Предлагаемый подход состоит в описании искажения в виде двумерного патча Безье. Эта модель обеспечивает большую гибкость настройки на различные типы сложных искажений.

Научная задача работы состоит в создании метода геометрических преобразований изображений текстовых документов на основе аппроксимации междустрочных просветов с помощью одномерных кривых Безье и общего преобразования изображения в виде двумерного патча Безье.

Научная новизна работы определяется тем, что в рамках настоящего исследования впервые в интересах устранения геометрических искажений в текстовых электронных документах использованы следующие идеи:

• Выполнена сегментация междустрочных просветов и строк в изображении текстового документа на основе непрерывного гранично-скелетного представления изображения, в частности, на основе анализа внешнего скелета текста;

• Выполнена аппроксимация геометрических искажений всего документа в форме двумерного патча Безье;

• Разработана вычислительная схема построения аппроксимирующего искажения патча Безье на основе вычисления одномерных аппроксимирующих кривых Безье для междустрочных просветов и дальнейшей итерационной подгонки патча Безье. Научная значимость работы состоит в описании геометрических искажений в

изображениях текстовых документов с помощью математической модели двумерного патча Безье, а также в разработке метода параметрической настройки этой модели для конкретных данных.

Практическая значимость состоит в создании и реализации нового метода аппроксимации и удаления геометрических искажений в изображениях текстовых документов, обеспечивающего существенное повышение качества автоматического распознавания текстов.

Обоснованность и достоверность научных положений, выводов и результатов работы подтверждается корректным использованием математического аппарата непрерывного гранично-скелетного представления изображения, кривых и патчей Безье, строгими математическими доказательствами, программной реализацией и вычислительными экспериментами, а также успешным использованием разработанных моделей и методов при решении практических задач. Положения выносимые на защиту:

• Математическая модель описания искажений в виде непрерывной функции преобразования координат, представленной двухмерным патчем Безье.

• Метод детектирования междустрочных просветов текста на основе непрерывного внешнего скелета изображений текстовых блоков.

• Метод сегментации строк текста в изображении на основе найденных междустрочных просветов.

• Метод аппроксимации междустрочных просветов и строк текста кубическими кривыми Безье.

• Метод аппроксимации искажения всего документа с помощью двумерного патча Безье по набору одномерных кривых Безье, аппроксимирующих искривления отдельных междустрочных просветов.

• Метод итерационной подгонки аппроксимирующего патча Безье.

• Метод распрямления изображения документа на основе аппроксимации искажения документа.

Структура диссертации

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и одного приложения с результатами экспериментов. В первой главе содержится:

• Математическая постановка задачи детектирования и устранения геометрических искажений на изображениях текстовых документов.

• Функция оценки качества методов распрямления изображений на основе качества распознавания.

• Обзор существующих решений задачи детектирования и устранения геометрических искажений на изображениях текстовых документов.

• Общая структура предлагаемого метода решения задачи. Во второй главе содержится:

• Определение непрерывного гранично-скелетного представления бинарного растрового изображения.

• Доказательство некоторых свойств скелета изображения.

• Алгоритм предобработки скелета и изображения для лучшего выделения междустрочных ветвей скелета.

• Алгоритм выделения междустрочных ветвей скелета на основе кластеризации ребер скелета.

• Механизм сегментации строк текста на изображении на основе выделенных междустрочных ветвей.

• Метод аппроксимации междустрочных ветвей скелета и строк текста на изображении с помощью одномерных кривых Безье.

• Алгоритм итерационной подгонки кривых Безье при аппроксимации. В третьей главе описывается:

• Метод изменения параметризации кривых Безье.

• Метод построения двумерного патча Безье на основе аппроксимации набора одномерных кривых.

• Алгоритм упрощенной аппроксимации набора кривых патчем Безье на основе аппроксимации наборов опорных точек кривых.

• Процедура построения распрямленного изображения документа на основе использования обратного преобразования патча Безье, аппроксимирующего геометрическое искажение текстового документа.

В четвертой главе описывается программная реализация предложенного алгоритма и содержится отчет о результатах экспериментов на тестовой базе изображений.

В заключении подводятся итоги работы.

Диссертация содержит 132 страницы машинописного текста, 37 рисунков. Список литературы включает 52 наименования.

Апробация. Представленные в работе результаты докладывались и обсуждались на 2-ой международной конференции по анализу и распознаванию изображений с фотокамер (CBDAR-2007, Curitiba, Brazil), 9-ой международной конференции по распознаванию образов и обработке информации (PRIP-2007, Минск, Беларусь), 16-ой и 17-ой международных конференциях по компьютерной графике и машинному зрению (Графикон-2006, Новосибирск; Графикон-2007, Москва).

По теме диссертации опубликовано 6 работ включая статьи в отечественных журналах и трудах международных конференций, в том числе одна статья в журнале из списка ВАК.

Содержание работы

Введение содержит общую характеристику работы, обоснование актуальности темы исследования, цели и задачи диссертационного исследования.

В первой главе описывается общая постановка задачи аппроксимации и устранения геометрических искажений с изображений текстовых документов для повышения качества их распознавания.

Определяется представление бинарного изображения (Г) в виде в виде двумерной функции цвета на плоскости: с: я2 -> )0;i).

Определяется понятие функции геометрического преобразования изображения -

Ставится задача детектирования геометрических искажений на изображениях текстовых документов в виде построения функции геометрического преобразования изображения, которая бы аппроксимировала искажения документа. Определяется процесс построения распрямленного изображения:

7 = ф"'(/)= нс((,и)= с(ф, (м/),ф, (Г, и»)

Предлагается использовать двумерный патч Безье для аппроксимации искажений текстовых документов.

Двумерный патч Безье размерности тхп - это функция д:л2->д:, задаваемая выражением:

<-0/-0

где р„чп2, 1 = о.....п, ] = о.....т - опорные вершины патча (точки на плоскости

изображения), а ¿>,,(/), / = о.....» и ^.с) , у = о.....т- полиномы Бернштейна.

Размерность патча по двум координатам может различаться. Область определения параметров патча 0,и) это вся действительная плоскость. Однако в реальной работе обычно используется область параметров от 0 до 1.

Определяется функция оценки алгоритма детектирования и удаления геометрических искажений с изображения документа через уменьшение ошибок распознавания на исходном и распрямленном документе.

Ф(Г,и): R2 Лг;Ф((,и)=J * ' .: [ФД'.«

ф, (t,uy. я2 -> «;ф, (1,и): л2 r

Ф ,('•")

перевод плоскости изображения в другую плоскость:

Далее в первой главе приводится анализ существующих методов решения задачи диссертации. Показаны недостатки существующих подходов с точки зрения современных систем обработки и распознавания изображений. По результатам анализа формируются требования к разрабатываемому методу.

Далее в первой главе приводится общая структура предлагаемого метода:

1) Предобработка изображения

2) Скелетизация изображения

3) Кластеризация ребер скелета

4) Удаление вертикальных ребер

5) Выделение междустрочных ветвей скелета

6) Выделение строк текста

7) Аппроксимация строк и междустрочных просветов кривыми Безье

8) Построение патча Безье по набору кривых

9) Распрямление изображения

Во второй главе приводится определение непрерывного гранично-скелетного представления изображения. Полигональной областью (ПО) называется ограниченная область, граница которой описывается конечным числом простых непересекающихся полигонов. Полигональная область аппроксимирует растровое бинарное изображение, если при наложении центры всех черных точек растра лежат внутри области, а центры всех белых точек растра лежат вне области. Представление изображения в виде совокупности полигонов минимального периметра, аппроксимирующих черные области на изображении, будем называть непрерывным граничным представлением изображения.

Скелетом полигональной области называется геометрическое место точек на евклидовой плоскости, имеющих не менее двух ближайших точек на границе ПО. Часть скелета, лежащая внутри ПО, образует внутренний скелет, а часть, лежащая вне ПО - внешний скелет области.

Совокупность непрерывного граничного представления изображения и непрерывного скелета, построенного по этому граничному представлению, будем называть непрерывным гранично-скелетным представлением изображения.

Рис. 1. Пример непрерывного гранично-скелетного представления изображения. Описывается представление скелета изображения в виде графа на плоскости: .¡{V,|у,ея2Vл =<у4,уа)|у4,ул где у,- узлы графа (точки на плоскости), г,-

ребра графа (отрезки прямых на плоскости, соединяющие узлы графа).

Далее решается задача очистки скелета, которая позволяет удалить из скелета все ребра, лежащие между частями одного черного объекта. Процедура очистки скелета состоит в рекурсивном удалении из скелета всех конечных ребер. Процедура повторяется до тех пор, пока в скелете не останется конечных ребер. После удаления конечных ребер скелета все новые получившиеся конечные вершины будут инцидентны каждая только одному черному объекту. Таким образом, можно повторить процедуру удаления конечных ребер, не потеряв при этом ребра, инцидентные двум различным объектам на изображении. С помощью данной процедуры из скелета будут удалены все ребра, инцидентные одному объекту. Доказательство корректности процедуры очистки скелета приведено в диссертации.

Пр,0*Г ГЮп^'оп'ЬеарргоаЛ I Пуег1еа1: <» ^НаЫЛ (й теак^.

- ' шогют р'«иге МегарЪцЕь^

Лиу Наппа гЬшиЬ«

™ \ Наппа 1кшиЬп ¡¡фкЛ

Рис. 2. Скелет изображения без обработки и с предложенной обработкой изображения и скелета.

Затем решается задача выделения в скелете ребер, лежащих между строками текста. Выделение рёбер скелета, относящихся к междустрочным просветам, осуществляется на основе предложенного алгоритма кластеризации ветвей скелета.

По всем углам наклона ветвей скелета строится гистограмма углов наклона. После построения гистограммы определяется порог, разделяющий два кластера. Для определения порога предлагается следующий механизм кластеризации. Для каждого возможного значения порогового угла (с шагом в один градус) определяется показатель разделимости получающихся кластеров. Для этого слева и справа от порога определяется среднее значение гистограммы (мя и м,) и дисперсия значений гистограммы (ок и ). Показатель разделимости кластеров для данного порога определяется как отношение суммы дисперсий внутри кластеров к расстоянию между средними значениями кластеров:

Содержательно показатель разделимости описывает отношение внутриклассового рассеяния к межклассовому.

Порог, разделяющий кластеры, выбирается как порог с наименьшим значением показателя разделимости кластеров.

11 с а, p ' "i £ I

« S 4 : m- 1 III 1 Ii I IpjlL

Рис. 3. Пример гистограммы углов наклона ветвей скелета с определенным

порогом.

После кластеризации ветвей скелета из скелета удаляются все ветви, не лежащие между соседними строками текста. После применения ряда эмпирических правил для разрешения неоднозначностей в скелете остаются только ветви скелета разделяющие соседние строки текста._

. л,1 »hat «те the change" ÄdMiü. о! щ..

Рис. 4. Скелет изображения до фильтрации вертикальных ветвей и после выделения междустрочных ветвей скелета.

На основе набора междустрочных ветвей скелета предлагается механизм сегментации строк текста на изображении. Задача сегментации строк на изображении по имеющимся междустрочным ветвям скелета сводится к задаче нахождения соседних по вертикали междустрочных ветвей скелета и определения для каждой

Realization _ discussed in eenmiizationj ^¡sc^egin ßenera^atiofiJ J&fM^ Indio;

'Chapters 5 instances are Chapters b Tndffi.

instance saiv instanc^are Chapter 13.

"discussed m ~Chaptert3> 'biscussedjn 'Chspisrl^'

Рис. 5. Пример сегментации строк текста на изображении.

Далее предлагается метод построения аппроксимации ломанной линии на изображении и области строки текста на изображении с помощью одномерных кривых Безье.

Одномерная кривая Безье - это параметрическая кривая на плоскости, задаваемая выражением:

1-0

гдс р( е л2,/ = 0,...,/7

- опорные вершины кривой (точки на плоскости изображения), а

ь. п(О-, = 0....." ■ базисные функции кривой Безье, называемые также полиномами

Бернштейна, и — степень полинома, / — порядковый номер опорной вершины.

Область определения параметров кривой (0 это вся действительная прямая. Однако в реальной работе обычно используется область параметра от 0 до 1.

Для аппроксимации набора точек на плоскости )£?,),./ = о.....к кривой Безье

£„(') = ! поставим в соответствие каждой точке определенное значение параметра

<-о

аппроксимирующей кривой: д1 ->/у,у = о,...,*.

Если набор точек на плоскости - это ломанная линия (набор точек, в котором все пары соседних точек соединены отрезками кривой) (как для аппроксимации междустрочной ветви скелета), то в качестве начальной параметризации для каждой точки бралось отношение длины ломанной от начала до данной точки ко всей длине ломанной.

Если набор точек на плоскости - это набор черных объектов (как для аппроксимации области строки текста на изображении), то в качестве начальной параметризации для каждой точки бралась просто координата по х данной точки.

В качестве расстояния от набора точек на плоскости до кривой будем использовать суммарное квадратичное отклонение точек от соответствующих точек кривой:

Теорема 1. Кривая Безье £„(/) = £р,ь,,(0 наилучшего приближения для набора точек

(-0

= на плоскости имеет опорные точки, координаты которых являются решением двух систем линейных уравнений:

2>(й.а-)

В работе предложен следующий итерационный механизм подгонки аппроксимирующей кривой Безье:

После того как построена кривая по предварительным параметрам, для каждой аппроксимируемой точки находится ближайшая точка на построенной кривой. С аппроксимируемой точкой ассоциируется значение параметра найденной ближайшей точки. Полученные параметры используются при построении новой аппроксимирующей кривой. Процедура повторяется пока разница в оценке аппроксимации на соседних шагах не будет меньше предопределенного порога -

Теорема 3. На каждом новом шаге расстояние от построенной кривой до набора точек не увеличивается. То есть, для произвольной пары соседних шагов с номерами 1 и (1+1) суммарное расстояние между набором точек и построенной кривой на новом вм шаге будет не больше, чем расстояние о' на предыдущем шаге.

Следствие. Предложенный метод итерационной подгонки сходится, причём начиная некоторой итерации условие останова для него выполняется.

В главе три описывается механизм изменения параметризации для кривой Безье

в,(') = 1р,-ъ,„(о с отрезка [0,1] на произвольный отрезок [<„»2], то есть построение кривой

(-0

ВЛ')=1Ц-Ь,ЛО, такой, что для любого I:

(-0

£ р,-К, (0=Д,С) = в,(—ч = £ я, „

.-о 1,-1, м>

Задачу изменения параметризации можно упростить, если решать ее в два этапа. Сначала параметры исходной кривой сжимаются в V раз. То есть

/ Оч ~ и)

параметризация меняется с отрезка ¡о, 1] до отрезка [О,/,-(,]. Затем параметры сдвигаются на -г,. То есть параметризация меняется с отрезка (о,;, -/,] до отрезка (г,,/2].

В диссертации показывается, что задача растяжения и сдвига параметров кривой сводится к решению системы линейных уравнений для определения координат опорных точек кривых и приводится решение этих систем линейных уравнений для кривых третьего порядка.

Далее в главе три ставится задача аппроксимации набора одномерных кривых двумерным патчем Безье.

Двумерный патч Безье размерности (тхи) - это функция я: я2 п2, задаваемая выражением:

в,.(1,и) = £ £ р1 ■ ь,й, (о Л. СО >

где р,г < = о,...,и, 7 = о.....т - опорные вершины патча (точки на плоскости), а

ь,,( 1), / = о.....п и ¿Л„(и), / = о.....т- полиномы Бернштейна.

Если в патче Безье зафиксировать один параметр <« = «„)> т0 получившаяся функция по второму параметру I будет одномерной кривой Безье на плоскости:

в,„ (/,«.)=¿(г/1,А- («„)) а, со=в, (/)

Задача аппроксимации набора кривых на изображении текста с помощью патча Безье ставится следующим образом:

Есть набор кривых = Для каждой кривой в'(О из набора

1-0

зафиксируем три параметра: и„, 12*.

Будем считать, что каждой кривой в'с) из набора соответствует некая кривая из патча, полученная фиксацией в патче параметра и„:

£40=1(1/; А-О^АДО-

Будем считать, что началу кривой в'(0) соответствует значение кривой из патча в точке в1 <<'), а концу кривой /;'0) соответствует значение кривой из патча в точке :

в'сЬ-

В диссертации приведены различные методы определения значений параметров для кривы.

Определим расстояние между двумя точками на плоскости, как стандартное евклидово расстояние:

Определим расстояние от одной кривой Безье до другой как интеграл по параметру первой кривой квадратичного расстояния между соответствующими точками обеих кривых:

Тогда для аппроксимации набора кривых патчем Безье нужно построить патч, который бы минимизировал отклонение кривых из набора от соответствующих кривых из патча с учетом определенных параметров:

1ММ&)!

Теорема 4. Координаты опорных точек патча Безье порядка (их»), аппроксимирующего набор кривых Безье .в4(0= ¿йЧ.(')■•*= 1.....к, являются решением

»-о

двух следующих систем линейных уравнений размерности (шх«) :

Г-О

¿¿¿о;,-г„>си-о

>-0 г-0

I*

с,;„=\т (и, > а„ (»»)■{ о*/., (о у

Назовем набор кривых в*(<)=£О",К.оу кривыми с одинаковой параметризацией, если для любого =о,»* =1. В диссертации предлагается метод перехода от задачи

аппроксимации произвольного набора кривых к набору кривых с одинаковой параметризацией путем изменения параметризации отдельных кривых.

Далее в работе предлагается альтернативный, более быстрый алгоритм аппроксимации набора кривых с одинаковой параметризацией патчем Безье по опорным точкам кривых.

Теорема 5. Отклонение аппроксимирующего патча Безье от набора исходных кривых с одинаковой параметризацией всегда меньше или равно, чем суммарное расстояние между опорными точками исходных кривых и линейной комбинацией опорных точек патча Безье.

" + 1 /.о ^ )

Таким образом, мы заменяем задачу аппроксимации набора кривых с одинаковой параметризацией на следующую задачу:

Дан набор кривых с одинаковой параметризацией в'(0=2йЧ.(0". * = .

/«о

Рассмотрим набор контрольных точек кривых с одинаковым порядковым

номером - ¡о,'), к = 1.....к. Сопоставим каждой точке из набора то же значение

параметра щ, что соответствует исходной кривой. Тогда мы можем построить кривую Безье в,(«)= | (и), аппроксимирующую данный набор точек:

«,(")= £яд„(и): ¿(Р(«,(«,).а'» —

Для каждого порядкового номера I контрольных точек ¡д.} исходных кривых (от О до и) получаем набор из ™+1 контрольных точек аппроксимирующей кривой. Таким образом, всего получается набор из (т+1)х(» + 1) контрольных точек. Эти точки и используются для построения патча Безье._

^РошЕз &ош аД1 * 1шеоп Ше шшке.

сшта УС оКэд Гонг УбГ

Ыс йегк

. ромИк.

уегНса! йпЫР. щпм яппгоюШйа^-РШ»« с™««

----- ------ --—- ' { ¡а сЬе огаег

ОС.......... .

1Уш огс!ег ''те Бш1<1 Ща^Щ

Б^зЛ"" ЬиШ апс!

Рис. 6. Пример построения патча Безье.

Теорема 6. Если аппроксимировать п+1 наборов опорных точек с помощью кривых Безье и максимальное отклонение построенных аппроксимирующих кривых от соответствующего набора точек будет меньше е, то суммарное отклонение построенного по опорным точкам этих кривых патча от набора исходных кривых будет также меньше е.

Далее в работе приводится процесс итерационной подгонки патча Безье:

Для каждой кривой из исходного набора оценим расстояние от данной кривой до соответствующей кривой из патча и посчитаем среднее квадратов расстояний между построенным патчем и набором кривых. После этого удалим из исходного набора кривых все кривые, для которых получившееся отклонение от кривых из патча в п раз больше чем среднее отклонение для всего набора кривых. После этого построим новый аппроксимирующий патч по уменьшенному набору кривых.

We delete from skel- We delete from skel-

eton int :rline b •anches eton int :rline b ■anches

that dot s not fl to cre- that dot s not fl to cre-

ated pat :h. Aft r doing ated pat ch. Aftc r doing

so we m build t le patch so we r< build t ie patch

using branchc all re ч —- •naining using branchc Such ac all re s. justing naining allows

Such ac justing allows

us to m ¡tximiz« preei- us to m iximize preei-

sion of our d ;formi sion of our di forma-

tion app roximationT" tion approximation.

Рис. 7. Патч Безье до и после итерационной подгонки. Далее в работе приводится механизм построения распрямленного изображения с помощью обратного преобразования от патча Безье, аппроксимирующего искажение документа:

6. ^dD*

J30 ^^

invtwe'tl0"' Г>а тгт dacmi!" ^ <"* « mot, оГ

Du'1"8 dZt orjou шг '»С "»fft ot сод° ч

далриor IF" ,iai™ =f DDoS ад^чЗ

fcrprovidiag Information Att open. other b^f1- Ч 4 да,, to wrc^- .OTUOt/plMwcrd information .lit*»; ,,P>biu,

W^fZ of providing tb rat«.. The IP «¡^ " Ь«ч|

^Г^, » consider carciuily befort «Ы„&

S^-tc. ^ Л» *en to release their <Z ^ £

fcrfj ».bdi d«* but » .fa«М-*,

Li,««» »bout ^ Лиг «Ы fad pubftcfy, и„ иоеот?^

йог „«¿Ч-Х» 1« "»Cltion-ГЬ,Ьч4 ,f>T,u annot P«vc w,^»

^mlsh.b.r.edfc'Iibd

6. DcrilMDdcn«App**ta

During your tavestigadon. you may determine thar one or more of pur o»i computen are atmcling someone. or you may obtain IRC traffic or eommind/ccnttd traffic from ■ DDoS burlier or agent thar identifies vlctlma of DDoS attacks Vox ij H4t want to be responsible for providing information thar opens other hosts up to ibui Ьесаше you have essentially given account/password information allowing their rtmott control, or for them to be trivially taken over by someone с lie. Of course, someone dit may find them and take them over anyway before you release informsdon, butstleat you could not be accused of providing the means. The IP addresses of victims ik another thing that you want to consider carefully before releasing, and then уоц пцу want to talk to the victim sites and allow them to release their own lnforraadon.

Nanus oftndividuab involved (especially ifsuapectcd ofperforming iDDcS attack) should be held dosely, but provided to law enforcement. Releasing names of suspects, or making statements about them and thar акШ level publicly, can sometimes result ir their ttuddnfjeu in retaliation. Perhaps worse, if you cannoc prove your allrptiau you

Рис. 8. Пример работы предлагаемого алгоритма. В четвертой главе работы приводится описание программного комплекса, реализующего предложенный алгоритм.

Основные функции программной реализации

1) Загрузка произвольного изображения документа.

2) Ручное выделение на изображении текстового блока.

3) Ручное удаление с изображения не нужной разметки с возможностью последующего восстановления при построении распрямленного изображения.

4) Построение непрерывного гранично-скелетного представления изображения выделенного текстового блока.

5) Фильтрация скелета изображения выделенного блока и выделение в нем ветвей, лежащих между строками текста на изображении.

6) Аппроксимация искривления междустрочных ветвей скелета кривыми Безье.

7) Выделение отдельных строк текста на изображении на основе данных о междустрочных кривых.

8) Построение аппроксимации кривыми Безье выделенных строк на изображении.

9) Аппроксимация геометрических искажений всего выделенного блока патчем Безье на основе информации об аппроксимации искажений отдельных междустрочных просветов в тексте и отдельных строк текста.

10) Создание распрямленного изображения на основе аппроксимации искажения документа патчем Безье.

11) Сохранение распрямленного изображения в файл.

12) Визуализация результатов работы каждого этапа алгоритма (построенного скелета, выделенных междустрочных ветвей, построенного патча Безье, распрямленного изображения).

13) Возможность сохранения в файл изображений с результатами работы каждого этапа алгоритма.

Далее приводятся результаты тестирования предложенного алгоритма на тестовой базе изображений.

В качестве тестовой базы для проведения эксперимента была использована публичная тестовая база изображений документов с геометрическими искажениями.

В тестовую базу входит 102 изображения. Каждое изображение — это сканированное изображение одной страницы из какой-либо книги. Все изображения черно-белые. На изображениях текст расположен в одну колонку с редкими включениями боковых сносок. На большинстве изображений текст занимает всю страницу. Размер текста на изображениях в среднем был 14 пунктов. Первые 11 изображений были отсканированы с разрешением в 300 dpi. Все остальные изображения были отсканированы с разрешением 450 dpi.

Эксперимент состоял в следующем: каждое изображение из тестовой базы распрямлялось с помощью описанного алгоритма. Затем с помощью программы FineReader 9.0 Professional распознавалось исходное изображение и распрямленное изображение. Оценивался процент исправленных за счет распрямления ошибок распознавания. Также оценивалась с помощью предложенного выше механизма степень искривления построенного на изображении патча Безье до и после распрямления.

На большинстве изображений предложенный алгоритм существенно улучшил качество распознавания - это видно из гистограммы на рисунке 9. В среднем количество ошибок распознавания после применения вышеописанного алгоритма уменьшается на 82 процента (от числа ошибок на искривленном изображении). А медиана улучшения качества составила 92,28 процента.

При этом на исходных изображениях средний процент ошибок распознавания был равен 19,75%. А на распрямленных с помощью предложенного метода изображениях процент ошибок распознавания составил 2,15%. Стоит отметить, что это существенное улучшение качества распознавания поврежденных изображений: даже на идеальных документах современные системы распознавания не гарантируют качество распознавания меньше 1% процента ошибок.

Всего на трех изображениях из тестовой базы алгоритм ухудшил качество распознавания. На испорченных изображениях было небольшое искривление и очень мало текста — из-за этого метод не смог выделить достаточное количество междустрочных просветов и добавил небольшие искажения в документ. Стоит отметить, что такие случаи легко детектировать и не проводить на подобных изображения процедуру удаления геометрических искажений. Такое детектирование не входило в задачи данной диссертации и может быть проведено стандартными методами известных систем распознавания._

35

30 ■ КД

О 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 35 Улучшение качества распознавания, %

Рис. 9. Гистограмма улучшения качества распознавания изображений после применения алгоритма удаления геометрических искажений.

Таким образом, предложенный механизм детектирования и удаления геометрических искажений с изображений текстовых документов полностью доказал свою эффективность на обычных искривленных изображениях. При этом стоит учитывать, что предложенный механизм способен устранять и более серьезные искажения с изображений документов, за счет увеличения степени аппроксимирующего патча Безье.

Заключение содержит основные результаты диссертационного исследования.

Весь иллюстративный материал диссертации и автореферата был получен с использованием разработанного программного комплекса.

Публикации по теме диссертации:

[1] А.А. Масялович, "Численные методы детектирования и удаления геометрических искажении в изображениях текстовых документов", журнал "Информационные технологии", №5,2009, стр. 57-61.

[2] A. Masalovitch, L. Mestetskiy, "Usage of continuous skeletal representation for document images de-warping", Proceedings of the Second International Workshop on Camera-Based Document Analysis and Recognition (CBDAR-2007), 2007, Curitiba, Brazil, pp. 45-52.

[3] A. Masalovitch, L. Mestetskiy, "Document Image Deformation Approximated by the Means of Continuous Skeletal Representation of the Image", Pattern Recognition and Information Processing - Proceedings of Ninth International Conference (PRIP-2007), 2007, Minsk, Belarus, pp. 279-284.

[4] А.А. Масалович, Jl.M. Местецкий, "Использование патча Безье для аппроксимации искажения текстовых документов", Труды 17-ой Международной Конференции по Компьютерной Графике и Зрению (Графикон-2007), 2007, Москва, Россия, pp. 239243.

[5] A. Masalovitch, L. Mestetskiy, "Usage of 2-Dimensional Bezier Patch for Document Images Deformation Approximation", 8-th International Conference on Pattern Recognition and Images Analysis: New Information Tecnologies - Conference Proceedings (PRIA-8-2007), Volume 3, Yoshkar-Ola, Russian Federation, pp. 51-26.

[6] А.А. Масалович, Jl.M. Местецкий, "Распрямление текстовых строк на основе непрерывного гранично-скелетного представления изображений", Труды 16-ой Международной Конференции по Компьютерной Графике и Зрению (Графикон-2006), 2006, Новосибирск, Россия.

Подписано в печать: 04.05.10

Объем: 1,5 усл.печ.л. Тираж: 100 экз. Заказ № 256909 Отпечатано в типографии «Реглет» 119526, г.Москва, пр-т Вернадского, 39 (495) 363-78-90; www.reglet.ru

Оглавление.

Введение.

1 Геометрические искажения в изображениях текстовых документов и проблема их исправления.

1.1 Постановка задачи.

1.1.1 Изображение документа.

1.1.2 Текст документа.

1.1.3 Предобработка и нормализация изображения документа.

1.1.4 Функция преобразования изображения.

1.1.5 Математическая постановка задачи распрямления строк текста на изображении документа.

1.1.6 Оценка результата при исправлении искажений.

1.2 Анализ существующих решений.

1.2.1 Выделение на изображении слов и строк текста.

1.2.2 Построение функции искажения вертикальных границ текста.

1.2.3 Построение функции деформации строк текста.

1.2.4 Общие замечания.

1.3 Структура предлагаемого метода.

1.4 Выводы по главе 1.

2 Строковая сегментация и детектирование искажений в изображениях текстовых документов.

2.1 Непрерывное гранично-скелетное представление изображения.

2.1.1 Граница и скелет изображения.

2.1.2 Скелет полигональной области и его свойства.

2.1.3 Скелетный граф полигональной области.

2.1.4 Внешний скелет изображения и его свойства.

2.2 Сегментация изображения текста на основе внешнего скелета.

2.2.1 Предобработка изображения.

2.2.2 Предобработка скелета.

2.3 Выделение межстрочных ветвей скелета.

2.3.1 Определение ветвей скелета и операций с ними.

2.3.2 Кластеризация ребер скелета.

2.4 Постобработка скелета.

2.5 Сегментация отдельных строк текста.

2.6 Аппроксимация строк документа.

2.6.1 Построение аппроксимации ломаной линии кривой Безье.

2.6.2 Аппроксимации строк текста кривыми Безье.

2.7 Итерационная подгонка аппроксимации.

2.7.1 Общее описание метода итерационной подгонки кривой.

2.7.2 Нахождение ближайшей точки на кривой.

2.7.3 Доказательство сходимости метода подгонки.

2.8 Выводы по главе 2.

3 Исправление геометрических искажений на основе аппроксимации их двухмерными патчами Безье.

3.1 Использование метода аппроксимации в работе.

3.2 Изменение параметризации кривой Безье.

3.2.1 Постановка задачи.

3.2.2 Растяжение параметров кривой Безье.

3.2.3 Сдвиг параметров кривой Безье.

3.3 Построение двумерного патча Безье на основе набора одномерных кривых.

3.3.1 Постановка задачи.

3.3.2 Метод аппроксимации семейства кривых патчем Безье.

3.3.3 Аппроксимация набора кривых Безье по опорным точкам.

3.3.4 Метод итерационной подгонки патча Безье.

3.4 Исправление геометрических искажений на изображении текста.

3.4.1 Общая процедура построения распрямленного изображения.

3.4.2 Определение цвета пикселя.

3.5 Выводы по главе 3.

4 Программный комплекс и вычислительные эксперименты.

4.1 Программная реализация алгоритма.

4.1.1 Основные функции программной реализации.

4.1.2 Описание программной реализации.

4.1.3 Шаги алгоритма.

4.1.4 Описание пунктов меню в главном окне.

4.2 Результаты экспериментов.

4.2.1 Основной эксперимент.

4.2.2 Результаты эксперимента.

4.2.3 Сравнение с мировым уровнем.

4.3 Выводы по главе 4.

Оптическое распознавание символов (англ. Optical Character Recognition, OCR) — конвертация изображений символов и букв в текст, редактируемый на компьютере [7,8]. На вход системы оптического распознания текста приходит цифровое растровое изображение сканированного или сфотографированного документа, на выходе система должна сформировать текст, который содержит это изображение, в виде, пригодном для сохранения в одном из форматов электронных текстовых документов.

Оцифровка документов — это процесс перевода бумажных документов в электронный (цифровой) вид [7,8]. В зависимости от формата сохраняемых в компьютере документов (графического или текстового) различают два подхода к оцифровке:

1) Получение копий страниц в виде графических (обычно растровых) изображений, осуществляемое путём сканирования или фотографирования с последующей обработкой и сохранением в одном из форматов графических файлов. В этом случае полностью сохраняется оригинальная вёрстка документа и исключается появление каких-либо ошибок, связанных с переводом содержимого документа в текстовый формат. Однако при хранении документов в графическом формате невозможен контекстный поиск в архивах, а также извлечение фрагментов текста, например, для цитирования.

2) Оптическое распознавание текста с последующим сохранением полученного текста в одном из форматов электронных текстовых документов. В этом случае становится возможен полномасштабный текстовый поиск по документу и индексация больших массивов электронных книг, однако затрудняется воспроизведение оригинальной вёрстки, изображений, схем и формул, практически неизбежными становятся ошибки распознавания.

В последнее время всё чаще применяется смешанный подход: текст документа распознаётся в автоматическом режиме и сохраняется вместе с оригинальными растровыми изображениями страниц, что позволяет совместить преимущества обоих подходов.

Ранее для получения электронной версии бумажных документов применялся ручной набор текст документа в электронном текстовом редакторе. Однако ручной набор — это очень долгий и дорогостоящий процесс по сравнению с автоматическим распознаванием текста.

Системы автоматического распознавания текста в электронных документах, оцифрованных с помощью сканеров, получили в настоящее время широкое распространение. Качество современных систем распознавания находится примерно на уровне 99% правильно распознанных символов для изображений с нормальным качеством. К сожалению, далеко не всегда документы, предназначенные для распознавания, бывают хорошо и ясно отсканированы. На качество распознавания влияет множество факторов. Среди наиболее важных факторов можно отметить качество печати в исходном документе, загрязненность исходного документа, размер шрифта в исходном документе, разрешающую способность сканирующего устройства, которая определяет размер символов шрифта в точках растрового изображения. Современные коммерческие системы распознавания текстов (такие как FineReader, OmniPage, Readlris) достаточно эффективно могут распознавать большинство изображений, полученных с помощью сканера.

Однако в настоящее время помимо задачи распознавания сканированных документов возникает задача распознавания документов, полученных с помощью цифровых фотокамер. Это связано с тем, что цифровые фотоаппараты получают все большее распространение. В частности, за последние несколько лет появилось достаточно большое количество систем для оцифровки документов, которые основаны на цифровых фотоаппаратах. Система на основе цифрового фотоаппарата работает в несколько раз быстрее обычного сканера, так как в нем не тратится время на физическое передвижение сканирующей планки. Однако использование цифровых фотоаппаратов для оцифровки текста создает много новых трудностей при распознавании текста. К примеру, из-за использования вспышки или плохого освещения часть изображения может быть затемнена, а часть наоборот слишком освещена. В результате использования недорогих камер и объективов («непрофессионального оборудования») или из-за плохих настроек изображение целиком или его часть может быть сильно размыта. Из-за использования слишком большого времени экспозиции изображение может быть смазано. Также одной из главных проблем современных фотоаппаратов является то, что они привносят геометрические искажения в изображения документа.

Нужно заметить, что проблема геометрических искажений на изображении документа существовала еще до начала широкого использования цифровых фотоаппаратов для оцифровки текста. В частности, при сканировании толстых книг очень часто возникают искажения на изображении страницы в области сгиба книги. Однако эти искажения имеют достаточно четко детектируемую и описываемую структуру. Поэтому для исправления искажений на сгибе книге придумано очень много различных методов и систем. Разработаны как методы обработки и удаления искажений в оцифрованном изображении, так и специальные «книжные» сканеры, которые позволяют избежать искажений при сканировании книги (рассчитанные на то, что сканируемая книга раскрыта не полностью).

Однако с появлением и началом повсеместного использования цифровых фотоаппаратов проблема стала более сложной и актуальной. Искажения при фотографировании могут появиться по нескольким независимым друг от друга причинам. Это может быть недостатком используемой оптики - так называемый «эффект бочки». Другая причина состоит в том, что документ при фотографировании расположен не под прямым углом к оси камеры, что порождает перспективные искажения. Искажение также может быть вызвано неровностью исходного документа - к примеру, тем же изгибом в центре книги. Еще одна проблема заключается в том, что эти искажения могут комбинироваться между собой в любом сочетании. Из-за этого невозможно точно описать и предсказать модель искажения сфотографированного документа.

Большинство современных профессиональных систем распознавания текста (таких как FineReader, OmniPage, Readlris) рассчитаны на то, что строки текста на изображении будут прямыми и горизонтальными. Малейшие искажения строк текста приводят к сильному ухудшению качества распознавания. Поэтому в последнее время очень большое внимание уделяется методам, позволяющим устранять геометрические искажения в изображениях документов. В частности, в рамках самой крупной международной конференции по анализу и распознаванию документов ICDAR (International Conference on Document Analysis and Recognition) проводилось сравнительное тестирование методов распрямления текстовых строк на изображениях документов [10]. Метод, описанный в диссертации, также принимал участие в этом тестировании в 2007 году [2]. Также в рамках тестирования впервые была сформирована большая общедоступная база документов с геометрическими искажениями [11]. Создание такой базы позволяет легко сравнивать между собой различные методы распрямления текстовых строк на изображении.

Однако, несмотря на возросший интерес к этой области и наличие большого количества новых методов устранения геометрических искажений ([15-24]), универсального метода для решения этой проблемы, который бы с одинаковой эффективностью устранял искажения на любых типах текстовых изображений, не было изобретено.

Таким образом, задача устранения геометрических искажений в изображениях текстовых документов является весьма актуальной и нуждается в разработке эффективных методов решения с использованием новых идей.

Целью настоящей работы является создание метода аппроксимации и устранения сложных разнообразных геометрических искажений на изображениях документов для повышения качества их распознавания. Сложность данной задачи определяется трудностями детектирования и формального описания разнообразных искажений текстовых документов, необходимостью построения универсального алгоритма коррекции документов, трудностью выбора критерия качества для решения поставленной задачи.

В практическом аспекте целью работы является создание программного комплекса для устранения геометрических искажений текстовых документов. Данный комплекс должен выполнить предобработку предоставленного ему изображения текстового документа с информацией о расположении текстовых блоков в документе и сформировать новое изображение этого документа, в котором текстовые блоки имеют правильную прямоугольную форму, а строки текста расположены вдоль параллельных прямых линий.

Предлагаемый подход к решению задачи основывается на двух новых идеях. Первая идея относится к подзадаче выявления строковой структуры изображения. Предлагается осуществить сегментирование строк изображения путём выявления междустрочных просветов на основе построения и анализа внешнего скелета изображения текста в документе. Вторая идея относится к выбору вида геометрического преобразования изображения. Предлагаемый подход состоит в описании искажения в виде двумерного патча Безье. Эта модель обеспечивает большую гибкость настройки на различные типы сложных искажений.

Научная задача работы состоит в создании метода геометрических преобразований изображений текстовых документов на основе аппроксимации междустрочных просветов с помощью одномерных кривых Безье и общего преобразования изображения в виде двумерного патча Безье.

На защиту выносятся следующие положения.

1) Математическая модель описания искажений в виде непрерывной функции преобразования координат, представленной двухмерным патчем Безье.

2) Метод детектирования междустрочных просветов текста на основе «непрерывного» внешнего скелета изображения текстовых блоков.

3) Метод сегментации строк текста в изображении на основе найденных междустрочных просветов.

4) Метод аппроксимации междустрочных просветов и строк текста кубическими кривыми Безье.

5) Метод аппроксимации искажения всего документа с помощью двумерного патча Безье по набору одномерных кривых Безье, аппроксимирующих искривления отдельных междустрочных просветов.

6) Метод итерационной подгонки аппроксимирующего патча Безье.

7) Метод распрямления изображения документа на основе аппроксимации искажения документа.

Научная новизна работы определяется тем, что в рамках настоящего исследования впервые в интересах устранения геометрических искажений в текстовых электронных документах использованы следующие идеи:

1) Выполнена сегментация междустрочных просветов и строк в изображении текстового документа на основе непрерывного гранично-скелетного представления изображения, в частности, на основе анализа внешнего скелета текста;

2) Выполнена аппроксимация геометрических искажений всего документа в форме двумерного патча Безье;

3) Разработана вычислительная схема построения аппроксимирующего двумерного патча Безье на основе вычисления одномерных аппроксимирующих кривых Безье для междустрочных просветов и дальнейшей итерационной подгонки патча Безье.

Научная значимость работы состоит в описании геометрических искажений в изображениях текстовых документов с помощью математической модели двумерного патча Безье, а также в разработке метода параметрической настройки этой модели для конкретных данных.

Практическая значимость состоит в создании и реализации нового метода аппроксимации и удаления геометрических искажений в изображениях текстовых документов, обеспечивающего существенное повышение качества автоматического распознавания текстов.

Обоснованность и достоверность научных положений, выводов и результатов работы подтверждается корректным использованием математического аппарата непрерывного гранично-скелетного представления изображения, кривых и патчей Безье, строгими математическими доказательствами, программной реализацией и вычислительными экспериментами, а также успешным использованием разработанных моделей и методов при решении практических задач.

Основные результаты работы опубликованы в работах [1-6], в том числе в издании [1], входящем в список ВАК.

4.3 Выводы по главе 4

1) Поскольку исходное правильное изображение документа с прямолинейными строками не может быть использовано при оценке качества исправления искажений, для получения соответствующих оценок следует использовать результаты сравнительного анализа ошибок распознавания текста при использовании алгоритмов исправления искажений и при их отсутствии.

2) Оценка работоспособности предложенных алгоритмов осуществлена на основе разработки программного обеспечения, реализующего указанные алгоритмы, и вычислительных экспериментов с большими объемами реальных изображений текстовых документов.

3) Проведенные эксперименты показали, что предложенные алгоритмы являются реализуемыми, обеспечивают необходимое качество и вычислительную эффективность.

На основании экспериментов показано, что применение разработанных методов исправления искажений на этапе предобработки перед распознаванием текста позволяет существенно повысить качество распознавания. Уровень ошибок распознавания уменьшается с 20% до 2%, что является весьма существенным для систем этого класса.

4) Эксперименты, проведенные в рамках международного контекста по исправлению искажений документов, показали, что разработанные методы обеспечивают в целом качество предобработки на уровне лучших известных мировых аналогов. При этом выявляется существенное преимущество предлагаемого метода в части гибкости при обработке сильно искажённых изображений документов.

5) Разработанные методы и экспериментальное программное обеспечение могут быть использованы при создании промышленных систем оцифровки тестовых документов.

Заключение

В данной работе описан метод удаления геометрических искажений с изображений текстовых документов. В рамках исследования были получены и обоснованы следующие результаты:

1) сформулирована математическая постановка задача детектирования и исправления геометрических искажений на растровом изображении текстового документа;

2) предложено использовать двумерные кубические патчи Безье в качестве универсального класса функций для аппроксимации искажений документа;

3) сформулирован критерий оценки работы механизма по детектированию и исправлению искажений документа;

4) сформулированы принципы использования ветвей непрерывного гранично-скелетного представления изображения для детектирования и аппроксимации междустрочных просветов в тексте на изображении документа;

5) предложен алгоритм кластеризации и фильтрации ветвей скелета изображения для нахождения ветвей скелета, лежащих между различными строками текста;

6) предложен механизм выделения на изображении областей, содержащих отдельные строки текста, на основе разделения изображения междустрочными ветвями скелета;

7) предложен механизм аппроксимации искажения междустрочных просветов текста на основе аппроксимации междустрочных ветвей скелета кубическими кривыми Безье;

8) предложен механизм аппроксимации искажения строк текста на изображении кривыми Безье;

9) построен механизм итерационной подгонки кривой Безье, аппроксимирующей набор точек;

10) предложен механизм аппроксимации набора кривых Безье с помощью патча Безье;

11) предложен ускоренный алгоритм аппроксимации набора кривых Безье патчем Безье и была доказана правомочность его использования;

12) описан процесс итерационной подгонки построенного патча Безье;

13) построен механизм удаления геометрических искажений с изображения документа. В качестве основы для алгоритма удаления искажений использовалась построенная на предыдущем шаге аппроксимация геометрического искажения изображения.

В работе приведен обзор существующих решений проблемы устранения геометрических искажений, выявлены основные недостатки существующих методов решения. Главной целью данной работы было создание метода, свободного от указанных недостатков. Эта задача была успешно решена, что подтверждается проведенным исследованием.

В ходе исследования была проведена серия экспериментов для оценки качества предлагаемого решения. Эксперименты показали высокую надежность разработанного метода. В качестве оценки качества метода использовалось качество распознавания большого набора документов до и после устранения искажений. Также эксперименты использовались для оптимизации путей реализации некоторых шагов предложенного метода.

Разработанный метод отличается высокой эффективностью, что доказано серией экспериментов. Также разработанный метод обладает большой гибкостью, которая позволяет ему эффективно детектировать и удалять практически любые геометрические искажения, появившиеся на документе в процессе сканирования или фотографирования.

Разработанный метод участвовал в независимом международном тестировании, где показал результаты сравнимые по качеству с альтернативными методами, участвующими в тестировании. Сравнение показало, что уровень предложенного метода соответствует лучшим мировым аналогам, а по некоторым аспектам превосходит их. При этом выявляется существенное преимущество предлагаемого метода в части гибкости при обработке сильно искажённых изображений документов.

Таким образом, поставленная в работе научная задача успешно решена.

1. А.А. Масалович, "Численные методы детектирования и удаления геометрических искажений в изображениях текстовых документов", журнал "Информационные технологии", №5, 2009, стр. 57-61.

2. A.A. Масалович, JI.M. Местецкий, "Использование патча Безье для аппроксимации искажения текстовых документов", Труды 17-ой Международной Конференции по Компьютерной Графике и Зрению (Графикон-2007), 2007, Москва, Россия, стр. 239-243.

3. A.A. Масалович, JI.M. Местецкий, "Распрямление текстовых строк на основе непрерывного гранично-скелетного представления изображений", Труды 16-ой Международной Конференции по Компьютерной Графике и Зрению (Графикон-2006), 2006, Новосибирск, Россия.

4. Arms, William Y., "Digital libraries", Cambridge, Massachusetts, USA, MIT Press, 2000, http://www.cs.cornell.edu/wya/DigLib/MS1999/Glossary.html

5. University of Leeds, Leeds Electronic Text Centre, Glossary, http://etext.leeds.ac.uk/glossary.html

6. В. И. Левенштейн. "Двоичные коды с исправлением выпадений, вставок и замещений символов". Доклады Академий Наук СССР, 1965. 163.4:845-848

7. JI.M. Местецкий, "Непрерывная Морфология Бинарных Изображений: Фигуры, Скелеты, Циркуляры", Москва, ФИЗМАТ ЛИТ, 2009.

8. Л.М. Местецкий, "Скелет многосвязной многоугольной фигуры", Труды 15-ой Международной Конференции по Компьютерной Графике и Зрению (Графикон-2005), 2005, Новосибирск, Россия.

9. Л.М. Местецкий, "Непрерывный скелет бинарного растрового изображения", Труды Международной Конференции по Компьютерной Графике и Зрению (Графикон-98), 1998, Новосибирск, Россия.

10. Bin Fu, Minghui Wu, Rongfeng Li, Wenxin Li, Zhuoqun Xu, Chunxu Yang, "A model-based book dewarping method using text line detection",

11. Proceedings of the Second International Workshop on Camera-Based Document Analysis and Recognition (CBDAR-2007), 2007, Curitiba, Brazil, pp. 63-70.

12. D. C. Schneider, M. Block, R. Rojas, "Robust document warping with interpolated vector fields", Proceedings of the 9-th International Conference on Document Analysis and Recognition (ICDAR-2007), 2007, Curitiba, Brazil, pp. 113-117.

13. B. Gatos, I. Pratikakis, K. Ntirogiannis, "Segmentation based recovery of arbitrarily warped document images", Proceedings of the 9-th International Conference on Document Analysis and Recognition (ICDAR-2007), 2007, Curitiba, Brazil, pp. 989-993.

14. H. Ezaki, S. Uchida, A. Asano, H. Sakoe, "Dewarping of document images by global optimization", Proceedings of the 8-th International Conference on Document Analysis and Recognition (ICDAR-2005), 2005, Seoul, South Korea, pp. 302-306.

15. U. Ulges, С. H. Lampert, Т. M. Breuel, "A Fast and Stable Approach for Restoration of Warped Document Images", Proceedings of the 8-th International Conference on Document Analysis and Recognition (ICDAR-2005), 2005, Seoul, South Korea, pp. 384-388.

16. Li Zhang, Chew Lim Tan, "Warped Image Restoration with Application to Digital Libraries", Proceedings of the 8-th International Conference on Document Analysis and Recognition (ICDAR-2005), 2005, Seoul, South Korea, pp. 192- 196.

17. A. Yamashita, A. Kawarago, Т. Kaneko, К.Т. Muira, "Shape reconstruction and image restoration for non-flat surfaces of documents with a stereo vision system", Proceedings of international conference ICPR, 2004, pp 482-485.

18. M.S. Brown, W.B. Seales, "Image Restoration of Arbitrarily Warped Documents", IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 26, Issue 10, 2004, pp. 1295 — 1306.

19. Graphics Gems, A. Glassner (editor), Academic Press, 1990, ISBN: 0122861663.

20. Graphics Gems II, J. Arvo (editor), Academic Press, 1991, ISBN: 0120644819.

21. Graphics Gems III, D. Kirk (editor), Academic Press, 1992, ISBN: 0124096735.

22. Graphics Gems IV, P. Heckbert (editor), Academic Press, 1994, ISBN: 0123361559.

23. Graphics Gems V, A. Paeth (editor), Academic Press, 1995, ISBN: 0125434553.

24. А. Дж. Роджерс, Математические основы машинной графики. — М.: Мир, 2001.

25. Т. Sederberg, Bezier curves,http://www.tsplines.com/resources/class notes/Bezier curves.pdf

26. J.D. Foley et al.: Computer Graphics: Principles and Practice in C, 2nd ed., Addison Wesley, 1992.

27. R. E. Barnhill and R. F. Riesenfeld (editors), Computer Aided Geometric Design, Academic Press, 1974.

28. G. Farin, Curves and surfaces for computer aided design, Academic Press, 1988.

29. D. E. Knuth, MetaFont: the Program, Addison-Wesley, 1986.

30. R. H. В artels, J. C. Beatty, B. A. Barsky, "Bezier Curves". Ch. 10 in "An Introduction to Splines for Use in Computer Graphics and Geometric Modelling". San Francisco, California, USA: Morgan Kaufmann, pp. 211-245, 1998.

31. С. H. Бернштейн, Собрание сочинений, Москва, 1952.

32. W. Boehm, A. Miiller, "On de Casteljau's algorithm", Computer Aided Geometric Design, Volume 16, Issue 7, August 1999, Pages 587-605.

33. L. Piegl, Fundamental Developments of Computer Aided Geometric Design. San Diego, California, USA: Academic Press, 1993.

34. G. G. Lorentz, Bernstein Polynomials. Toronto: University of Toronto Press, 1953.

35. И.М. Гельфанд Лекции по линейной алгебре. ООО "Добросвет", 1998.

36. В. А. Ильин, Э. Г. Позняк Линейная алгебра, Москва: Наука — Физматлит, 1999.

37. В. А. Ильин, Г. Д. Ким Линейная алгебра и аналитическая геометрия, Москва: ТК Велби, Изд-во Проспект, 2007

38. G. Н. Golub, С. F. Van Loan, "Matrix Computations (3rd ed.)", Johns Hopkins, 1996.

39. K. A. Atkinson, An Introduction to Numerical Analysis (2nd ed.), New York: John Wiley & Sons, 1989.

40. А.А. Самарский, Введение в численные методы, Наука, 1987.

41. А.А. Самарский, А.В. Гулин, Численные методы, Наука, 1989.

42. Х.Д. Икрамов, Численное решение матричных уравнений, Наука, 1984.

43. M. Abramowitz, I. A. Stegun. "Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing". New York: Dover, 1972.

44. P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7.

45. С. T. Kelley, Solving Nonlinear Equations with Newton's Method, no 1 in Fundamentals of Algorithms, SIAM, 2003. ISBN 0-89871-546-6.

46. R.W. Farebrother, (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-82477661-9.