Содержание к диссертации
Введение
ГЛАВА 1. Методы и алгоритмы обработки изображений документов в информационных системах 10
1.1. Информационные системы, использующие изображения документов 10
1.2. Методы обработки изображений документов 19
1.3. Методы классификации изображений документов 30
Выводы 42
ГЛАВА 2. Гармонизация алгоритмов обработки изображений документов 43
2.1. Предлагаемая методика гармонизации алгоритмов обработки изображений документов 43
2.2. Восстановление контраста 48
2.3. Обратное растрирование 58
2.3.1. Обратное растрирование с помощью разреженного кодирования 59
2.3.2. Оценка качества обратного растрирования 65
Выводы 68
ГЛАВА 3. Обнаружение информационных блоков 70
3.1. Поиск текста, таблиц и изображений 70
3.1.1. Устойчивый метод выделения текстовых блоков 71
3.1.2. Поиск таблиц и изображений 76
3.2. Маркировка связных компонент 78
Выводы 94
ГЛАВА 4. Классификация изображений документов 96
4.1. Устойчивые методы извлечения признаков шаблона документа 97
4.1.1. Пространственный локальный двоичный шаблон 97
4.1.2. Векторы Фишера на основе смеси распределений Бернулли 99
4.2. Классификация изображений документов путём объединения нескольких классификаторов 102
4.3. Исследование разработанных алгоритмов с помощью автоматически сгенерированных данных 106
4.3.1. Генерация базы данных документов на основе реальных шаблонов 106
4.3.2. Исследование разработанного алгоритма быстрой классификации 110
Выводы 114
Заключение 116
Список литературы
- Методы обработки изображений документов
- Обратное растрирование с помощью разреженного кодирования
- Устойчивый метод выделения текстовых блоков
- Классификация изображений документов путём объединения нескольких классификаторов
Введение к работе
Актуальность темы. Интенсивное развитие информационных систем в
последние десятилетия позволило в значительной степени автоматизировать
процессы создания и обработки документов, необходимых для
функционирования государственных органов и коммерческих предприятий. Обработка изображений сканированных документов представляет собой комплексный процесс, включающий в себя не только изменение самого изображения, но и извлечение большого количества информации о цвете, типе документа, содержании и графике. Интернет-сервисы, например Evernote, WizNote, Google Drive и их аналоги, позволяют извлекать текст из любой фотографии, содержащей буквенные символы, поэтому крупные и средние компании для поддержки своего документооборота требуют аналогичной функциональности и от информационных систем, что обуславливает встраивание отдельных функций интеллектуальной обработки изображений.
Производители программного обеспечения для информационных систем предоставляют решения подобного рода, однако предлагаемые ими алгоритмы требуют детальной настройки под нужды конкретного заказчика. В научно-исследовательских работах преобладает тенденция к минимизации труда человека путём повсеместного внедрения методов машинного обучения. Исследователи не ставят своей целью создать всеобъемлющую и универсальную технологию обработки изображений сканированных документов, а решают узкие конкретные задачи. Сопряжение множества разнородных алгоритмов в рамках единой технологии приводит либо к падению общей скорости работы за счёт высокой вычислительной сложности, либо к снижению качества обработки изображений из-за слабой согласованности отдельных алгоритмов.
В связи с этим актуальной является проблема разработки и согласования (гармонизации) алгоритмов анализа и обработки изображений сканированных документов. В диссертационной работе п редлагаются новые алгоритмы контрастирования, обратного растрирования, маркировки связных компонент, извлечения текста и выделения структурных признаков, дополняющие друг друга с учётом возможностей современного аппаратного обеспечения и особенностей решаемой задачи. Разработанная методика классификации структурных элементов сканированных документов объединяет предложенные алгоритмы, позволяя достичь высоких показателей точности классификации и скорости обработки.
Степень разработанности темы. Решению различных проблем, связанных с обработкой и анализом изображений сканированных документов, посвящено большое количество работ, выполненных отечественными и зарубежными учеными.
Проблема низкого контраста решается путём применения методов адаптивного контрастирования, предложенных И. Сафоновым, Р. Соболем, Л. Тао, Н. Морони, К. Зуйдервельдом и другими. В существующих подходах применяется разделение изображения на локальные области по жестко заданной сетке, что не позволяет корректно изменять контраст документов, состоящих из однородного фона и рисунков.
Другая проблема связана с эффектом муара из-за наложения растровых сеток сканера и принтера. Методам устранения данного эффекта посвящены работы Г. Галло, К. Дабова, И. Курилина, однако в них текстура изображений восстанавливается не полностью.
Методы выделения ключевых признаков текста, рисунков и таблиц, характеризующих документ внутри информационной системы, описаны в статьях А. Гордо, Ф. Цезарини, С. Усилина, С. Чена, Дж. Кумара, Х. Гао, С. Бухари и других. Указанные подходы не способны извлекать текст из сканированных документов низкого разрешения.
Методы классификации документов, основанные на выделенных гетерогенных признаках, предложены М. Дилигенти, Е. Аппиани, Дж. Лиангом, Х. Сако и С. Тейлором. Данные методы разработаны в предположении, что документ имеет однородный фон, следовательно, точность классификации существенно снижается при сложном изображении в качестве фона.
Вышеуказанные алгоритмы созданы для решения узкого класса задач, что приводит к их несогласованности при совместной работе и снижению быстродействия информационной системы. Решением данной проблемы является создание методики согласования алгоритмов, что требует переработки существующих и создания новых алгоритмов, отвечающих одинаковым требованиям.
Цель и задачи работы. Целью диссертации является разработка научно-обоснованного алгоритмического обеспечения информационных систем для анализа и обработки изображений сканированных документов, а также соответствующей методики согласования разработанных алгоритмов, обеспечивающих высокую точность классификации структурных элементов документов при повышенном быстродействии.
Для достижения поставленной цели решаются следующие задачи:
-
разработка теоретических положений и методики гармонизации алгоритмов обработки изображений сканированных документов;
-
разработка алгоритма адаптивного локального улучшения контраста изображений сканированных документов;
-
разработка алгоритма обратного растрирования печатных изображений;
-
разработка алгоритмов поиска текстовых областей, таблиц, маркировки связных компонент и извлечения признаков изображений сканированных документов;
5. разработка на основе предложенной методики гармонизации алгоритма классификации структурных элементов изображений документов, объединяющего полученные алгоритмы в виде единой технологии анализа и обработки изображений сканированных документов. Научная новизна. В диссертационной работе получены следующие новые
научные результаты.
-
Предложена методика гармонизации алгоритмов обработки изображений сканированных документов на основе многократного повторного применения результатов работы алгоритмов и полутоновых изображений.
-
Разработаны алгоритм адаптивного локального улучшения контраста изображений сканированных документов, использующий сглаживание параметров кривых преобразования между соседними областями с помощью графа связности, и метрика сравнения структурной схожести изображений, полученная путем модификации метрики SSIM.
-
Разработан алгоритм восстановления растрированных изображений на основании модели оператора растрирования и предложен оригинальный подход к сравнению восстановленных изображений.
-
Разработаны алгоритмы поиска текстовых областей, таблиц и маркировки связных компонент на изображениях сканированных документов, использующие дескриптор длин полутоновых отрезков, структурный тензор и карту смежности блоков изображения.
-
Разработаны алгоритмы извлечения ключевых признаков структурных элементов сканированных документов с помощью длин полутоновых отрезков, пространственного локального двоичного шаблона, векторов Фишера на основе распределения Бернулли и алгоритм классификации структурных элементов документов, использующий двухступенчатый подход к объединению нескольких классификаторов. Методы достоверности исследования. Для решения поставленных задач
в работе использовались элементы теории вероятностей и математической статистики, теории оптимального оценивания и фильтрации, численные методы вычислений. О ценка качества работы алгоритмов проводилась на основе статистического моделирования на ЭВМ путем сравнения с существующими аналогами на репрезентативных тестовых выборках.
Практическая значимость. Разработанные алгоритмы обработки и анализа изображений документов и алгоритм классификации, использующий набор г армонизированных алгоритмов, внедрены компанией ООО «Исследовательский центр Самсунг» в качестве программно-аппаратного комплекса, написанного на языке стандарта C++11 с применением библиотеки OpenCV 3.0.0 для загрузки и манипуляции изображениями, что подтверждается соответствующим актом внедрения.
Апробация работы. Основные результаты работы докладывались и получили положительную оценку на международных и российских научно-
технических конференциях: Color Imaging XX: Displaying, Processing, Hardcopy, and Applications, San-Francisco, USA, 2015; XII МНТК “Распознавание-2015”, Курск, 2015; Mediterranean Embedded Computing MECO’2015, Budva, Montenegro, 2015; Visual Information Processing and Communication VII, San-Francisco, USA, 2016; Mediterranean Embedded Computing MECO’2016, Bar, Montenegro, 2016.
Публикации. По теме диссертации опубликовано 8 работ, в том числе 1 патент, 2 работы в журналах ВАК, 3 работы изданы на английском языке и индексированы в базах IEEE и SCOPUS, 1 работа в международном сборнике на английском языке и 1 работа в тезисах конференций. Одна публикация отмечена дипломом за лучшую научную работу.
Личный вклад автора. Все основные результаты диссертации, опубликованные в приведенных работах в составе коллектива авторов – методика гармонизации, алгоритмы контрастирования, обратного растрирования, нахождения текста, таблиц и изображений, извлечения признаков и классификации сканированных документов и сравнение данных алгоритмов с существующими аналогами – получены автором лично.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав и заключения. Работа содержит 140 страниц основного текста, в том числе 35 рисунков, 13 таблиц, список использованных источников из 233 наименований.
-
Методика гармонизации алгоритмов обработки и анализа изображений сканированных документов, позволяющая достичь высоких целевых показателей работы информационной системы при относительно малом времени обработки каждого документа.
-
Алгоритм адаптивного локального контрастирования изображений сканированных документов с использованием предварительной сегментации и алгоритм восстановления растрированных изображений на основе методов разреженного кодирования, позволяющий снизить ошибку восстановления на 7 % и повысить число похожих дескрипторов на 5 % в сравнении с известными алгоритмами.
-
Алгоритмы нахождения текста и таблиц на изображениях сканированных документов с помощью структурного тензора и адаптивной бинаризации, достигающие точности 84 % по метрике F1, и а лгоритмы извлечения ключевых признаков изображений сканированных документов с использованием пространственного локального двоичного шаблона, гистограммы длин полутоновых отрезков и векторов Фишера на основе распределения Бернулли, позволяющие повысить точность классификации на 10 % в сравнении с известными алгоритмами.
4. Алгоритм классификации структурных признаков изображений сканированных документов с помощью нескольких классификаторов, основанный на разработанной методике гармонизации и повышающий скорость обработки изображений до 2,2 раз в сравнении с известными алгоритмами объединения классификаторов.
Методы обработки изображений документов
Текстовые блоки делятся на рукописные и печатные. С точки зрения обнаружения текста разница между ними не существенна: многие алгоритмы успешно способны обнаруживать оба вида [43]. Распознавание производится несколькими различными способами: посимвольно с последующей корректировкой ошибок методами оценки правдоподобия [44], по отдельным словам, или с помощью скользящего окна [33] аналогично тому, как это делается при распознавании речи. Последний способ является наиболее точным, поскольку учитывает информацию о соседних словах и позволяет распознавать любые виды текста, содержащие различные шрифты, начертания символов и языки. Недостатком всех подходов является высокая сложность: применение алгоритмов OCR существенно увеличивает время обработки документа, что недопустимо при большом потоке данных.
Выделение визуальных признаков текста для последующего распознавания делается следующими способами: путем сравнения каждого символа с неким эталоном (данный подход широко применяется в компании Abbyy), выделения дескрипторов формы [45] или характеристических признаков символов [46] и использованием сверточных нейросетей [33]. Первые два способа относятся к классическим подходам, в то время как третий активно развивается, однако они обладают неоспоримым преимуществом: для о бучения сверточной нейросети необходимо большое (десятки тысяч) количество объектов в обучающей выборке и длительное время (многие сети обучаются неделями), в то время как традиционные подходы можно адаптировать под конкретную задачу значительно быстрее. Вместе с тем, точность распознавания традиционных подходов существенно уступает свёрточным нейросетям.
Важной задачей обработки документов является извлечение ключевых слов. Крупный шрифт используется для обозначения заголовков, которые содержат ключевые слова, характеризующие основной текст. Аналогичную функцию выполняют слова, выделенные курсивом или жирным начертанием. Извлечение ключевых слов относится к задачам суммаризации текста.
Некоторые документы маркируются с помощью буквенно-цифровых индексов, позволяющих однозначно их идентифицировать. Примером подобного подхода может служить система маркировки юридических документов, применяющаяся во многих компаниях. Распознавание буквенно-цифровых индексов не требует настолько же сложных алгоритмов, как в случае с распознаванием произвольного текста, так как количество символов ограничено, а их начертание и расположение обычно заранее известны. Вместе с тем, если для алгоритмов, распознающих текст общего вида, ошибки в распознавании отдельных символов вполне допустимы, то при распознавании индексов неправильно распознанный символ может привести к серьезным последствиям, что обуславливает наличие особо жестких требований к подобным алгоритмам. Недостаток алгоритмов распознавания индексов аналогичен методам, использующим штрих коды: для корректного функционирования системы необходимо маркировать все документы, что может быть невозможно в отдельных случаях.
Ещё одним элементом документа являются таблицы. Формально они относятся к текстовым блокам, но на практике практически любая таблица состоит как из текстовых, так и из структурных элементов (линий), которые находятся с помощью различных алгоритмов. Линии используются в задачах распознавания печатных форм. Примером является распознавание бланков ЕГЭ (единого государственного экзамена). Расположение таблицы в документе и ее структура несёт важную информацию о типе документа и позволяет различать документы между собой. Существует два подхода к распознаванию таблиц. Первый основан на поиске линий [47], второй использует данные о взаимном расположении текстовых строк, пытаясь обнаружить одинаково выровненные слова [48] (рисунок 5). Существующие методы распознавания таблиц либо не используют текст в качестве признака, либо применяют алгоритмы OCR и адаптивной бинаризации для его поиска. Первый подход не является верным, так как в большинстве случаев текст несёт важную информацию о содержимом таблицы. Второй подход
является более корректным, но обладает существенным недостатком: как было сказано выше, OCR требует значительного времени, а адаптивная бинаризация не позволяет корректно отделить текст от фона в ряде случаев.
Обратное растрирование с помощью разреженного кодирования
Для сравнения различных алгоритмов локального контрастирования предлагается новая метрика оценки структурной схожести двух изображений (раздел 2.3.2), позволяющая корректно оценивать появление артефактов. Теоретически и практически показывается преимущество разработанной метрики над существующей метрикой SSIM (Structural Similarity Index Metric; метрика индекса структурного подобия), являющейся стандартом для данного типа задач.
Изображение с восстановленным контрастом используется для поиска текста. Последний делится на два этапа: поиск регионов MSER-SI (Maximal Stable Extremal Regions Supremum / Infimum; супремум / инфимум наибольших устойчивых экстремальных областей), являющихся текстовыми кандидатами, и классификация найденных регионов на текст и не текст. Регионы типа MSER-SI, предлагаются в данной работе в качестве альтернативы известным регионам типа MSER (раздел 3.1.1). Главным достоинством предложенной модели MSER-SI является возможность обнаружения мелких текстовых областей, которые не способен обнаружить MSER. Классификация на текст и не текст производится путём извлечения разработанного дескриптора GRLH (Grayscale Runlength Histogram; гистограмма длин полутоновых отрезков). Данный дескриптор извлекает признаки из полутонового изображения, что позволяет избежать бинаризации.
GRLH повторно используется при классификации документов на основании визуальной схожести, что позволяет избежать дополнительных вычислений. Извлечённые текстовые области передаются в алгоритм выделения таблиц (раздел 3.1.2). Разработанный алгоритм основан на выделении линий изображения с помощью структурного тензора с последующей обработкой морфологическими операциями, что позволяет находить линии на изображениях любой сложности. Изображения выделяются с помощью найденных с использованием структурного тензора линий путём выделения областей с большим количеством сильных границ. Все вышеуказанные алгоритмы используют в ходе работы маркировку связных компонент. Последняя является ключевым этапом от скорости работы которого зависит скорость работы прочих алгоритмов. В данной диссертационной работе предлагается параллельный алгоритм маркировки связных компонент на GPU (Graphics Processing Unit; графический ускоритель) с использованием эквивалентных блоков (раздел 3.2). Разработанный алгоритм существенно превосходит существующие алгоритмы параллельной маркировки при обработке изображений документов, содержащих текст, в то время как прочие алгоритмы нацелены на обработку изображений общего вида и за счёт этого уступают ему в данном типе задач.
Найденные изображения и фон обрабатываются путём применения разработанного алгоритма обратного растрирования, что позволяет устранить растровую сетку (раздел 2.3). Удаление последней необходимо для улучшения визуального восприятия и повышения точности работы алгоритмов классификации изображений документов по визуальной схожести. Для сравнения существующих алгоритмов с разработанным предлагается новая методика, включающая метрики MSSSIM (Multi Scale Structural Similarity Index Metric; многомасштабная метрика индекса структурного подобия), BRISQUE и пересечение гистограмм BRISK. MSSSIM показывает структурную схожесть двух изображений, BRISQUE – безреференсную оценку визуального качества, а пересечение гистограмм BRISK – схожесть изображений с точки зрения алгоритма сравнения дескрипторов.
Все предыдущие алгоритмы применяются в качестве вспомогательных этапов функционирования разработанного алгоритма классификации изображений документов (Глава 4). Предлагаемые дескрипторы GRLH и SLBP (Spatial Local Binary Pattern; пространственный локальный двоичный шаблон), дополненные дескриптором BMMFV (Bernoulli Mixture Model Fisher Vectors; векторы Фишера на основе смеси распределений Бернулли), используются для извлечения разных типов ключевых признаков, что позволяет повысить устойчивость классификатора к наличию шума. Ключевой особенностью разработанной методики является скорость обработки документа: при классификации в обязательном порядке извлекается только дескриптор GRLH, который используется так же при поиске текста, а SLBP и BMMFV применяются только в случае, если правдоподобие решения, принятого на основе GRLH низко. Это позволяет избежать больших накладных расходов при извлечении нескольких дескрипторов.
При классификации найденный текст отделяется от фона, что позволяет существенно повысить точность распознавания. В разделе 4.3.2 показывается, что разработанная методика существенно превосходит существующие подходы при наличии на изображениях документов фона. Исходя из определённых в данном разделе требований к тестовым выборкам, было сгенерировано несколько коллекций документов, использованных для тестирования разработанной методики. Гармонизация алгоритмов позволяет существенно повысить точность классификации изображений документов при снижении времени работы.
Устойчивый метод выделения текстовых блоков
Алгоритм MSER находит любые области, удовлетворяющие формулировке (3.3), независимо от того, содержат они текст или нет. Задача поиска реальных текстовых областей среди всех кандидатов, найденных MSER, выполняется путём извлечения разработанного дескриптора GRLH (Grayscale Runlength Histogram; гистограмма длин полутоновых отрезков) для каждого кандидата с последующей классификацией последних на текстовые и не текстовые.
Классический алгоритм RLH (Runlength Histogram; гистограмма длин отрезков) [128] строит гистограмму длин отрезков, извлечённых из бинарного изображения. Как было сказано выше, главным недостатком бинаризации в случае обработки текста является сложность подбора порога бинаризации, позволяющего отделить буквы от фона. Разработанный дескриптор GRLH решает данную проблему путём перехода от отрезков бинарного изображения к отрезкам полутонового изображения. В последнем случае под отрезком понимается линия, яркость которой изменяется монотонно, без резких скачков. GRLH извлекается следующим образом: 1. Для каждого направления (вертикальное, горизонтальное и два диагональных, вдоль главной и побочной диагоналей) находятся отрезки, переходы яркости между границами которых составляют более 50 уровней.
Строятся гистограммы длин найденных отрезков для каждого направления: если длинна отрезка /г 128, то номер ячейки гистограммы, соответствующей данному отрезку, находится по формуле (3.4): ht — log2 It + [ci/cmax q\ hmax, (3.4) иначе по формуле (3.5): ht — log2 It + [cmax q\ hmax, (3.5) где Cj - средняя яркость отрезка, /г его длина, стах = 255 - максимальное значение яркости, q = 4 - количество уровней квантования, а hmax = 6 - число ячеек гистограммы для каждого уровня. 3. Полученные гистограммы объединяются в единый вектор признаков разме ром 96 и нормализуются в диапазоне [0; 1]. Классификация извлечённых дескрипторов производится с помощью SVM (Support Vector Machine; Машина опорных векторов) с ядром 2 (3.6): К(х,у) — —yYli=i—"—1 , (3.6) где параметр = 0.005, а вес, использующийся при нахождении разделяющей гиперплоскости в SVM, С = 10.
Найденный текст используются для поиска таблиц, изображений и повышения точности классификации документов. В первом случае достаточно знания о расположении ограничивающих прямоугольниках текстовых областей, во втором необходимо точное знание формы символов. Разработанный алгоритм MSER-SI, использующий формулировку (3.3) для поиска экстремальных регионов, находит только области, содержащие текст, но не сами символы. Выделение отдельных символов производится путём применения алгоритма [219] в каждой области.
Найденные символы отделяются от фона для последующего использования. Обработка текста связана с необходимостью маркировки связных областей, когда каждой области ставится в соответствие уникальный номер и строится карта меток, что позволяет манипулировать областями как отдельными объектами. Разработанный алгоритм маркировки связных областей подробно рассматриваются в разделе 3.2.
Для тестирования разработанного алгоритма была использована коллекция сканированных документов [220], содержащая набор документов с выполненной вручную разметкой, отделяющей тестовые области и изображения. В качестве критерия качества использовались метрики точности (precision), отзыва (recall) и F1, являющейся комбинацией предыдущих двух метрик. Оценивалось два показателя: общее число найденных текстовых областей и число корректно распознанных областей. В первом случае найденной областью считалась та, у которой пересечение с размеченной зоной составляло не менее 70 %. Соответственно, если алгоритм находил все размеченные текстовые зоны, точность оказывалась равна 100 %. Во втором случае оценивалось то, какое количество зон было распознано правильно.
Таблица 3 содержит результат сравнения количества найденных областей с помощью алгоритмов MSER и MSER-SI, предложенного в данной диссертационной работе. Предложенный алгоритм находит значительно большее число текстовых областей, что позволяет успешно применять его для задач поиска текста.
В таблице 4 показаны результаты сравнения точности классификации областей на текстовые и не текстовые с помощью дескрипторов RLH и GRLH, предложенного в данной диссертационной работе. В обоих случаях текстовые области находились с помощью алгоритма MSER-SI, а классификация проводилась с помощью машины опорных векторов с ядром (3.6). Точность (precision) предложенного дескриптора GRLH несколько ниже, чему классического RLH дескриптора, но отзыв заметно выше, что отражается на результатах оценки работы алгоритма с помощью метрики F1.
Классификация изображений документов путём объединения нескольких классификаторов
Описанные выше алгоритмы необходимы для работы разработанного метода классификации изображений документов (см. рисунок 6). На первом этапе изображение документа улучшается с помощью алгоритма контрастирования, описанного в разделе 2.2. Это позволяет повысить качество последующих алгоритмов детектирования объектов и выделения ключевых точек. Затем на изображении документа детектируются текст, таблицы и рисунки (см. раздел 3.1). Рисунки обрабатываются с помощью алгоритма обратного растрирования (раздел 2.3), который необходим для удаления растровой сетки, негативно влияющей как на восприятие изображения на экране монитора, так и на извлечение ключевых точек. Все структурные элементы документа, не являющиеся текстом, таблицами и рисунками, удаляются из исходного изображения.
Оставшиеся структурные элементы сильно отличаются друг от друга: текст состоит из большого числа простых фигур малого размера, таблицы содержат множество пересекающихся линий, а изображения представляются в виде набора ключевых точек, организованных в двумерные структуры. Отсутствие универсального дескриптора для описания всех трёх типов элементов приводит к необходимости использовать три различных дескриптора, каждый из которых наилучшим образом представляет свой структурный элемент. Разработанные дескрипторы описываются в разделе 4.1.
Классификация изображений документов с помощью классификаторов, построенных на основе данных дескрипторов в отдельности, позволяет достичь высокой точности, однако в сложных случаях необходимо использование всех трёх дескрипторов. В разделе 4.2 даётся описание решающей системы, позволяющей использовать все три дескриптора для повышения точности классификации при сохранении высокой скорости работы за счёт оценки правдоподобия получаемых результатов, что позволяет задействовать только часть дескрипторов в простых случаях. В данной диссертационной работе используется три типа разработанных дескрипторов: пространственный локальный двоичный шаблон (SLBP; Spatial Local Binary Pattern), применяемый для классификации текста и изображений, гистограмма длин полутоновых отрезков (GRLH; Grayscale Runlength Histogram), использующаяся для классификации текста и таблиц, и векторы Фишера на основе смеси распределений Бернулли (BMMFV; Bernoulli Mixture Model Fisher Vectors), применяемые для классификации текста и изображений. Первый дескриптор описан в разделе 4.1.1, второй - в разделе 3.1.1, а третий - в разделе 4.1.2.
Первый из перечисленных дескрипторов - это пространственный локальный двоичный шаблон. Важным свойством классического дескриптора LBP (Local Binary Pattern; локальный двоичный шаблон) [223] является способность кодировать пространственные отношения между соседними пикселями. Иными словами, LBP эффективно кодирует текстуры, к которым в том числе относятся и блоки текста документа. Разработанный дескриптор SLBP расширяет возможности LBP за счёт учёта не только соседних пикселей, но и соседних областей, кодируя отношения между ними.
Он вычисляется следующим образом: на первом этапе изображение рекурсивно разбивается на 21 блок таким образом (рисунок 31), что первым блоком является само изображение, а остальными - его четверти и 16-е части. Аналогичное разбиение применяется при классификации изображений документов с помощью дескриптора GRLH. Каждая часть масштабируется до размера 100х100 пикселей, и для каждого пикселя полученной части извлекается локальный двоичный шаблон (4.1): LBP(go) = У s{gQ,g{)-2l 1, (4.1) =1 где g0 - текущий пиксель, a gj - і-й сосед текущего пикселя. s(g0, gj) - функция сравнения яркости пикселей, возвращающая двоичный код в виде 0 или 1 (4.2):
Расположение соседних пикселей в разработанном дескрипторе SLBP отличается от такового в обычном локальном двоичном шаблоне: расстояние от центрального пикселя до его соседей составляет 3 пикселя, что позволяет кодировать отношения между далёкими пикселями (рисунок 32).
Рисунок 31. Рекурсивное разбиение изображения при вычислении разработанного дескриптора SLBP (Spatial Local Binary Pattern; пространственный локальный двоичный шаблон). Сверху - масштабирование участка изображения, снизу - сетка пространственных блоков.
Полученные бинарные коды формируют целое 8-битное число, которое кодирует отношения между пикселями. С помощью полученных для каждого блока чисел строится гистограмма, состоящая из 8 ячеек. Все ячейки нормализуются в диапазоне [0;1]. Гистограммы всех блоков объединяются в единый вектор признаков размером 21 изображений х 8 ячеек =168.
Для тестирования разработанного дескриптора SLBP была использована выборка FlexRot, которая подробно описывается в разделе 4.3.1. В качестве классификатора применялась машина опорных векторов с ядром (3.6) и параметрами Y= 0.5 иС = 10. 35 255 200 128 105 содержит результаты сравнения. Видно, что разработанный дескриптор SLBP значительно превосходит LBP по всем характеристикам. Масштабирование блоков изображения к размеру 100x100 пикселей положительно влияет на точность распознавания, что доказывает состоятельность подобного подхода.
Сравнение дескрипторов LBP (Local Binary Pattern; локальный двоичный шаблон) и SLBP (Spatial Local Binary Pattern; пространственный локальный двоичный шаблон). Дескриптор Точность, % LBP 62.9 SLBP без масшт. 76.4 SLBP 89.4
Кодирование изображений и текста производится с помощью векторов Фишера, построенных над смесью распределений Бернулли, которая, в свою очередь, используется для кластеризации двоичных дескрипторов BRISK (Binary Robust Invariant Scalable Keypoints; двоичные устойчивые инвариантные масштабируемые ключевые точки) [216].
Как правило, векторы Фишера строятся на основе гауссового распределения, что отражает предположение о нормальности распределения случайных величин, являющихся элементами векторов признаков. При извлечении двоичных
100 дескрипторов, таких как BRISK, основной единицей дескриптора являются двоичные числа, соответственно, предположение о нормальности не выполняется. Распределение Бернулли описывает распределение подобных случайных величин более корректно, поэтому в данной работе используется именно оно.