Для упорядоченных значений атрибутов находится Евклидово расстояние:
где n - количество атрибутов.
Для строковых переменных, которые не могут быть упорядочены, может быть применена функция отличия, которая задается следующим образом:
Часто перед расчетом расстояния необходима нормализация. Приведем некоторые полезные формулы.
Минимаксная нормализация:
Нормализация с помощью стандартного отклонения:
где уx - стандартное отклонение, Xср - среднее значение.
При нахождении расстояния иногда учитывают значимость атрибутов. Она определяется экспертом или аналитиком субъективно, полагаясь на собственный опыт. В таком случае при нахождении расстояния каждый i - ый квадрат разности в сумме умножается на коэффициент Zi. Например, если атрибут A в три раза важнее атрибута B (ZA = 3, ZB = 1), то расстояние будет находиться следующим образом:
Подобный прием называют растяжением осей (stretching the axes), что позволяет снизить ошибку классификации. Следует отметить, что если для записи B ближайшем соседом является А, то это не означает, что В - ближайший сосед А. Данная ситуация представлена на рисунке 2. При k = 1 ближайшей для точки B будет точка A, а для A - X. При увеличении коэффициента до k = 7, точка B так же не будет входить в число соседей точки A.
Рисунок 2 - Ближайшие соседи А и B
На следующем шаге, когда найдены записи, наиболее похожие на новую, необходимо решить, как они влияют на класс новой записи. Для этого используется функция сочетания (combination function). Одним из основных вариантов такой функции является простое невзвешенное голосование (simple unweighted voting).
Простое невзвешенное голосование
Вначале, определив число k, мы узнали, сколько записей будет иметь право голоса при определении класса. Затем мы выявили эти записи, расстояние от которых до новой оказалось минимальным. Теперь можно приступить к простому невзвешенному голосованию. Расстояние от каждой записи при голосовании здесь больше не играет роли. Все имеют равные права в определении класса. Запись отдает предпочтение тому классу, к которому она принадлежит, а тот, который наберет наибольшее количество голосов, присваивается новой записи. Но что делать в случае, если несколько классов набрали равное количество голосов? Эту проблему снимает взвешенное голосование (weighted voting).
Взвешенное голосование
В такой ситуации учитывается также и расстояние до новой записи. Чем меньше расстояние, тем более значимый вклад вносит голос. Голоса за класс находятся по следующей формуле:
где d2(X, Yi) - квадрат расстояния от известной записи Yi до новой X;
n - количество известных записей класса, для которого рассчитываются голоса; class - наименование класса.
Класс, набравший наибольшее количество голосов, присуждается новой записи. При этом вероятность того, что несколько классов наберут одинаковые голоса, гораздо ниже. Совершенно очевидно, что при k = 1 новой записи присваивается класс самого ближайшего соседа.
5. Заключение по аналитическому обзору
Представленные ранее существующие OCR - системы являются хорошими и качественными продуктами в своей области использования. Однако специфика предметной области данной работы требует более узкоспециализированного программного обеспечения. Изображения документов необходимо получать путем сканирования через веб - камеру либо с помощью загрузки в систему через браузер. На текущий момент времени рассмотренные системы не позволяют решать данную задачу. Решение задачи имеет смысл разделить на несколько этапов: сегментацию изображения (определение фотографии, выделение текстовых блоков), секторизацию текстовых блоков (выделение символов в словах) и распознавание (определение символа) текста.
Что касается методов, как правило, проблемой является низкая устойчивость алгоритмов к воздействию внешних условий, затрудняющих качество распознавания: уровень освещения; качество изображения; наличие наклона изображения. При этом алгоритмы, устойчивые к внешним условиям, зачастую оказываются требовательны к аппаратным и вычислительным ресурсам, что затрудняет применение их в системах, работающих в реальном времени. Несомненно, из представленного списка лучшей можно считать ABBYY FineReader. Но это система широкого профиля, кроме того, она является платной. Она поддерживает массу ненужных в данной предметной области сканирования документов, удостоверяющих личность, функций. В работе будет использоваться алгоритм k ближайших соседей для решения задачи распознавания символов на текстовых блоках.
Данный алгоритм обучения с учителем (существует обучающая выборка) достаточно прост в понимании и отлично подходит для решения задачи распознавания символов. В рамках данного проекта рассматривается как раз такая ситуация: требуется извлекать текст из выделенных текстовых блоков на отсканированном документе. Обучающая выборка присутствует. В отличии от нейронных сетей данный алгоритм на узких задачах быстрее, а его точность зависит от подбора параметров. Так как скорость распознавания документа имеет важное значение в разработке системы, то нейронная сеть здесь не подходит.
Программная реализация алгоритма относительно проста. Результат работы алгоритма легко поддаётся интерпретации. Экспертам в различных областях вполне понятна логика работы алгоритма, основанная на нахождении схожих объектов. Возможность модификации алгоритма, путём использования наиболее подходящих функций сочетания и метрик позволяет подстроить алгоритм под конкретную задачу. Тема распознавания символов на текущий момент времени во многом изучена и с каждым годом в этой области появляются все более совершенные алгоритмы.
6. Алгоритм распознавания текста
6.1 Общее решение задачи
Процесс решения задачи распознавания документов можно представить в виде последовательности шагов, изображенных на рисунке 3.
В данной работе предлагается алгоритм распознавания предварительно выделенных текстовых блоков на сканируемом изображении документа. Задача захвата изображения с камеры или его загрузки в систему, а также выделения документа на изображении, не рассматривается. В работе рассматриваются задачи получения изображения, его сегментация, секторизация, распознавание текста и подготовка итогового отчета по результатам распознавания.
Рисунок 3 - Общая схема решения задачи распознавания документов
6.2 Структурная схема и описание алгоритма
Краткая структурная схема алгоритма представлена на рисунке 4.
Разрабатываемый алгоритм распознавания документов можно представить в виде следующей последовательности шагов:
Шаг 1. Захват изображения (получение).
Шаг 2. Конвертация изображения в градации серого.
Шаг 3. Бинаризация изображения.
Шаг 4. Выделение фотографии.
Шаг 5. Выделение границ текстовых блоков.
Шаг 6. Секторизация текстовых блоков.
Шаг 7. Выделение границ символов на текстовых блоков.
Шаг 8. Классификация изображений полученных символов, определение значений.
Шаг 9. Объединение результатов в отчет.
Рисунок 4 - Структурная схема алгоритма
6.3 Методы цифровой обработки изображений
6.3.1 Преобразование в оттенки серого
Оттенки серого (Grayscale) -- цветовой режим изображений, которые отображаются в оттенках серого цвета, размещённые в виде таблицы в качестве эталонов яркости белого цвета. Чаще всего используют ступенчатое изображение равномерного ряда оптических плотностей нейтрально-серых полей. Широко применяется в цветоведении и колористике, для оценки и измерений качества тонопередачи при фотографической съемке, сканировании, при копировальных и печатных процессах (полиграфия).
6.3.2 Пороговая обработка и бинаризация
Операция порогового разделения, которая в результате дает бинарное изображение, называется бинаризацией. Целью операции бинаризации является радикальное уменьшение количества информации, содержащейся на изображении. В процессе бинаризации исходное полутоновое изображение преобразуется в черно - белое, пиксели которого имеют только два значения - 0 и 1 .
6.3.3 Выделение контуров
Наиболее известными и часто используемыми методами выделения контуров являются методы Робертса, Превитта и Собеля. Все указанные методы основываются на одном из базовых свойств сигнала яркости - разрывности. Наиболее общим способом поиска разрывов является обработка изображения с помощью скользящей маски, называемой также фильтром, ядром, окном или шаблоном, которая представляет собой некую квадратную матрицу, соответствующую указанной группе пикселей исходного изображения. Элементы матрицы принято называть коэффициентами. Оперирование такой матрицей в каких - либо локальных преобразованиях называется пространственной фильтрацией.
Алгоритмы Робертса и Собеля больше подходят для задачи выделения контуров, однако метод Собеля - это усовершенствованный метод Робертса и он дает более качественный результат выделения границ изображения т.к. является изотропным и позволяет выделять перепады яркостей любых направлений, поэтому в работе выбран данный метод. В задаче присутствует два этапа, когда происходит выделение контуров: сегментация исходного изображения и секторизация текстовых блоков. В первой задаче используется фильтр Собеля, во второй - фильтр Робертса. Такой выбор обусловлен тем, что опытным путем был выявлен тот, факт, что фильтр Робертса на небольших изображениях отрабатывает с высокой точностью, при этом фильтр Собеля не позволяет выделить символы в текстовых блоках.
6.3.4. Поиск контуров
После применения всех необходимых фильтров к изображению, можно выделить на изображении области, содержащие текстовые блоки или символы. На рисунке 2.9 можно посмотреть пример сегментированного изображения, где текстовые блоки отрисованы после этапа поиска контуров.
6.4 Выделение фотографии
Для поиска портретной фотографии человека используется каскадный классификатор Хаара. Библиотека OpenCV содержит готовые реализации многих алгоритмов машинного обучения, однако для корректной их работы, классификаторы следует предварительно обучить. Обучающая выборка для каскадного классификатора Хаара также реализована в рамках данной библиотеки.
6.5 Сегментация изображения
На оставшемся изображении после выделения фотографии так же требуется выделить текстовые блоки. Текстовый блок - это одна конкретная строка (слово) в документе. Путем преобразования изображения сначала в оттенки серого, затем после применения фильтров морфологической обработки дилатации и замыкания, производится выделение границ текстовых блоков. Полученные контуры выделяются на исходном изображении и для дальнейшей работы «вырезаются» в отдельные самостоятельные изображения для дальнейших преобразований.
6.6 Секторизация текстовых блоков
Секторизация (выделение символов (букв, цифр)) в каждом текстовом блоке, распознавание текста, сохранение результата в базе. Когда документ разбит на блоки, эти блоки в цикле перебираются и к каждому применяется секторизация, а затем распознавание. В процессе секторизации используются те же методы и алгоритмы, что и при сегментации. По сути, процесс секторизации - это сегментация сегмента исходного документа. В процессе секторизации изображения к изображению применяются следующие алгоритмы в указанном порядке:
1. преобразование в оттенки серого;
2. бинаризация изображения;
3. применение алгоритма Робертса;
4. выделение контуров с помощью порогового преобразования к бинарному изображению;
6.7 Классификация сегментов текстовых блоков
Задача классификации сегментов текстовых блоков - задача распознавания символа, изображенного в секторе. На данном этапе набор секторов текстового блока подвергается обработке через алгоритм k ближайших соседей и на выходе получаем распознанный текст. Внутри алгоритма распознается каждая буква. Когда каждая буква распознана, собирается готовое слово. Также должна быть обучающая выборка всех букв и цифр.
Рисунок 5 - Обучающая выборка
Эта выборка используется для поиска похожих символов на те, что пытаемся распознать. На рисунке 5 представлен пример такой выборки.
Обучающая выборка состоит из 53 изображении, размером 100Ч100.
42 буквы, 10 цифр, 1 знак препинания.
Для распознавания символов был выбран алгоритм k ближайших соседей.
7. Распознавание символов онлайн
Распознавание символов онлайн иногда путают с оптическим распознаванием символов. Последний -- это офлайн - метод, работающий со статической формой представления текста, в то время как онлайн - распознавание символов учитывает движения во время письма. Например, в онлайн - распознавании, использующем PenPoint OS или планшетный ПК, можно определить, с какой стороны пишется строка: справа налево или слева направо.