AzoftR&DРазработка алгоритма нечёткого поиска в распознанном тексте

Разработка алгоритма нечёткого поиска в распознанном тексте

Иван Ожиганов Декабрь 14, 2016

Разработка алгоритма нечёткого поиска в распознанном тексте

Сегодня автоматизированные системы оптического распознавания текста показывают довольно высокие результаты в точном распознавании символов. Тем не менее, 100%-ной точности инженерам-исследователям пока добиться не удалось. Поэтому в научном и R&D сообществе всё ещё актуальны вопросы поиска информации и исправления ошибок в распознанном тексте. Для их решения применяются коррекции текста с помощью словаря языка, на котором создан текст, или языковой модели. В частности, для поиска информации используют языковые модели word2vec и сиамскую сеть LSTM.

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

Цель исследования – повышение точности извлечения информации из распознанного текста.

Обзор исследования:

1. Постановка задачи поиска информации в распознанном тексте
2. Применение эвристического алгоритма
3. Выбор в пользу методов машинного обучения
4. Использование полносвёрточной нейронной сети для решения задачи
5. Применение рекуррентной нейронной сети LSTM для решения задачи

1. Постановка задачи поиска информации в распознанном тексте

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

Наша задача в этом случае – извлечь из текста определённые данные: список покупок, ИНН, дату и другие. Текст на изображениях распознаётся с ошибками. Это наглядно подтверждают картинки с чеками и распознанный текст: рис. 1 и рис. 2. Также в этом можно убедиться по изображениям 3 и 4, где представлены секция покупок и одна обозначенная покупка соответственно.

Пример картинки чека с текстомРис. 1. Пример картинки чека с текстом

Пример распознанного текстаРис. 2. Пример распознанного текста

Секция покупокРис. 3. Секция покупок

Покупка в чекеРис. 4. Покупка в чеке

2. Применение эвристического алгоритма

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

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

3. Выбор в пользу методов машинного обучения

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

По сути, машинное обучение представляет собой обучение модели на примерах. Представьте себе модель (например, сеть LSTM), которая обучается на большом количестве вручную размеченных примеров. Затем обученная модель применяется для разметки новых примеров, ранее не участвовавших в тренировке.

В сравнении с эвристиками машинное обучение имеет ряд преимуществ:

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

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

4. Использование полносвёрточной нейронной сети

С помощью полносвёрточной нейронной сети мы попытались создать систему поиска покупок в тексте.

Пример

Применение полносвёрточной нейросети к поиску покупокРис. 5. Применение полносвёрточной нейросети к поиску покупок

Здесь в тексте покупки отмечены символами “_”, что означает “начало покупки”, и “^” – “конец покупки”. Cимволы “_” и “^” были вставлены в текст вручную. Ожидалось, что сеть обучится на размеченных вручную примерах и затем будет находить покупки в новых чеках, не участвовавших в тренировке.

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

Кодирование слова “соль” в изображениеРис. 6. Кодирование слова “соль” в изображение

Кодирование осуществлялось по принципу:

Iij=1 если символ с номером i на позициии j
Iij=0 иначе

Где Iij – двумерный массив изображения

Размер Iij – d x L

Где d – длина алфавита, L – длина текста.

На изображении 6 для простоты представлен ограниченный алфавит. В реальности мы использовали полный алфавит из русских и английских букв, специальных символов (пробел, %, #, и другие) и цифр, а также дополнительного символа переноса строки для кодирования многострочного текста.

В результате получилось следующее.

На вход нейронной сети подается такое изображение, а на выходе получается изображение Oj с размером 1 x L такое, что:

Oj=1 если символ на позиции j принадлежит какой-нибудь покупке
Oj=0 если символ на позиции j не принадлежит никакой покупке

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

Работа свёртки первого свёрточного слояРис. 7. Работа свёртки первого свёрточного слоя

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

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

Архитектура полносвёрточной нейронной сетиРис. 8. Архитектура полносвёрточной нейронной сети

Слои макс-пулинга pool1 и pool2 имели шаг (stride), равный 1. Исходя из этого, после пулинга масштаб сигнала не менялся. Для обучения сети мы написали скрипты на Python с использованием библиотеки Theano.

Пример выхода сетиРис. 9. Пример выхода сети

Ещё один пример выхода сетиРис. 10. Ещё один пример выхода сети

На изображениях 9 и 10 показаны примеры выходов сети на тестовом датасете. Синяя линия показывает выход сети. Красная – какой выход должен быть в идеале (ground truth). Ось x – номер позиции символа. По оси y – вероятность определённого символа принадлежать какой-нибудь покупке. Когда красная линия находится на уровне 1.0, это означает, что в данном месте находится какая-то покупка. Есть короткие провалы в значение 0.0, которые означают символы перевода строки. Они не принадлежат какой-либо покупке.

Мы осуществили множество попыток обучения сети с разными параметрами и разной архитектурой. Во всех попытках проявилось переобучение: значение функции потерь (loss) на тренировочном датасете приблизительно составляло 0.002, а на тестовом датасете – 0.016. Из-за переобучения не удалось добиться приемлемого результата.

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

5. Применение рекуррентной нейронной сети LSTM

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

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

Пример определения секции покупок

Выделение секции покупок в чекеРис. 11. Выделение секции покупок в чеке

Здесь символ “<” обозначает начало секции покупок, а символ “>” обозначает конец секции покупок. Символы “<” и “>” были вставлены в распознанный текст вручную. Архитектура LSTM сети представлена на изображении 12.

Архитектура рекуррентной нейросети LSTMРис. 12. Архитектура рекуррентной нейросети LSTM

Есть 2 слоя LSTM. Первый LSTM слой бежит вдоль текста слева направо. Второй LSTM слой бежит в обратном направлении по тексту справа налево. Выходы обоих LSTM слоёв объединяются и входят в полносвязный слой (dense). Из полносвязного слоя выходит разметка (labeling) – ответ сети. LSTM сети обладают памятью, поэтому в данной архитектуре полносвязный слой на указанной позиции теоретически знает обо всех символах как слева по тексту до него, так и справа.

Символы кодируются во входном слое методом one-hot encoding:

Ii=1, если номер символа равен i
Ii=0, иначе

Где I- входной вектор для одного символа.

Другими словами, на вход сети подаётся последовательность векторов, где размерность каждого вектора равна длине алфавита, а количество векторов равно количеству символов в тексте. На выходе сети мы получаем последовательность двумерных векторов.

Сеть обучается по следующему принципу:

O1=1.0 и O2=0.0, если символ не принадлежит секции покупок
O1=0.0 и O2=1.0, если символ принадлежит секции покупок

Где O - выходной вектор для одного символа.

Таким образом, значение O2 после обучения на стадии тестирования – это вероятность символа принадлежать секции покупок. На стадии тестирования проверяется условие O2>O1. Если это условие выполняется, то ответом сети считается, что данный символ принадлежит секции покупок. Если не выполняется, то символ не принадлежит секции покупок.

В исследовании наш тренировочный датасет состоял примерно из 200 оригинальных чеков. Он был искусственно увеличен (augmented) до 600 чеков. При увеличении датасета добавлялись случайные ошибки и случайный обмен секциями покупок между случайной парой чеков. Мы тренировали нейросеть с использованием библиотек Theano+Lasagne в Python и решателя ADAM. На изображении 13 показан пример эволюции потерь (loss) во время тренировки.

Пример графика потерьРис. 13. Пример графика потерь

Ось x – номер шага решателя, ось y – потери (loss). Видно, что сеть обучается достаточно нестабильно. Мы планируем бороться с такой нестабильностью двумя способами:

  • Попробовать классический SDG решатель вместо ADAM
  • Уменьшать learning rate

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

Пример разметки секции покупок LSTM  сетью на тестеРис. 14. Пример разметки секции покупок LSTM сетью на тесте

Заключение

Наше исследование показывает, что разработка алгоритма нечёткого поиска информации в распознанном тексте – это не вопрос одного метода. Для того чтобы добиться стоящих результатов, необходимо сравнить несколько подходов экспериментальным путём. Это нам удалось реализовать в полной мере. Более того, в процессе применения различных методов мы остановились на самом убедительном из них – алгоритме поиска данных с применением рекуррентной сети LSTM. Именно LSTM сеть позволяет искать в тексте информацию с заданным шаблоном. Всё, что требуется для обеспечения надёжности результатов – достаточно большой тренировочный датасет и сохранение стабильного процесса обучения. Дополнительным плюсом для повышения точности поиска может стать использование эвристик на выходе сети.

Комментарии

комментарии