Словарь визуальных слов: как создать, зачем использовать, где применять
Автоматическое извлечение информации из деловых документов (счетов-фактур, квитанций, ID) все еще остается сложной задачей из-за отсутствия единого стандарта оформления: несмотря на то, что любой подобный документ содержит определенный набор полей, которые можно извлечь (дата, валюта, общая сумма), расположение элементов сильно отличается в зависимости от типа документа или компании. Также определенные трудности вызывают неоднозначное расположение границ документа, например, из-за смещения изображения на скан-копии. Этот фактор тоже может повлиять на положение искомых областей.
Использование словарей (кодовых книг) визуальных слов, аналогичных Bag-of-Words (BoW), раньше было довольно популярно для обработки изображений (к примеру, для поиска или классификации изображений документов). Мы решили создать принципиально новое решение для извлечения информации из документов, которое бы решало перечисленные выше проблемы предшествующих подходов и базировалось бы на построении и использовании оптимизированного словаря визуальных слов. При этом дополнительным достоинством нашей разработки является то, что обнаружение полей основано только на данных изображения и не требует больших размеченных наборов данных для обучения (fine-tuning) системы на стороне пользователя.
Важно отметить, что наш метод может использоваться как сам по себе, так и как вспомогательный в подходах извлечения данных, основанных на результатах распознавания текста (OCR), или же для облегчения процесса обучения нейронных сетей. Мы в ABBYY уже используем нашу разработку в новых продуктах.
В чем идея и цель?
Основная идея состоит в том, чтобы создать кодовую книгу/словарь визуальных слов из набора документов, по аналогии с методом BoW, для вычисления статистических предикатов позиций полей документа на основе пространственного положения визуальных слов в документе.
Положение целевого поля прогнозируется с использованием условных гистограмм, собранных в фиксированных положениях определенных визуальных слов. А интегрированное (аккумулированное) предсказание, в свою очередь, вычисляется как линейная комбинация, т. е. сумма предсказаний от всех обнаруженных визуальных слов.
В работе мы преследовали основную цель — разработать систему, способную прогнозировать положения значимых полей (important fields/field of interest) в документах с новыми макетами (или даже в новых типах документов), которые ранее были неизвестны системе. Также система должна предусматривать обучение на стороне пользователя, выполняемое на небольшом количестве размеченных документов.
Для корректной работы наше решение главным образом должно полагаться на модальность изображений документов, поскольку в них четко отражается сложная пространственная структура (например, как в деловых документах).
К модальности изображений документов можно отнести следующие характеристики: источник изображения (фотография, скан, факс, почта и т. д.), тип документа (счета-фактуры, квитанции, ID и др.), структура документа (логические блоки, изображения, рукописный текст, логотипы, поля, текст и т. д.).
Что в итоге?
Мы создали словарь визуальных слов на основе ключевых областей в документах, которые были обнаружены с помощью алгоритма Maximally stable extremal regions (MSER) и нескольких типов составных локальных дескрипторов, содержащих как фотометрическую, так и геометрическую информацию о нужных областях. Затем словарь был использован для расчета статистических предикатов для определения локаций нужных полей документа на основе корреляций между визуальными словами и полями документа.
Мы провели тестирование на нашем собственном датасете инвойсов, и получили среднюю топ-10 точность метода 0,918, что соответствует предсказанию положения центра значимого поля в области документа, составляющей лишь ∼3,8% от площади всего документа. При этом для обучения системы были использованы только пять размеченных инвойсов с новым макетом документа.
Построение словаря
Для построения словаря визуальных слов мы использовали некоторый набор документов (назовем его первый набор документов). Он может состоять из любого количества файлов, но мы ориентировались на 4–8 тысяч изображений.
Весь процесс построения словаря мы разделили на пять этапов.
Этап I
На первом этапе к каждому изображению документа применяется последовательность полутоновых морфологических операций (дилатаций). Мы последовательно «наращиваем» темные текстовые области и, соответственно, уменьшаем светлые области без текста.
Если применять серию дилатаций к изображению документа, мы получим серии изображений со все более и более склеившимися текстовыми областями. Иными словами, если исходное изображение бинаризовать, то мы получим отдельные символы (буквы) в виде связных компонент, а после применения дилатаций буквы склеятся в слова, затем в строки, и, наконец, в отдельно расположенные блоки или абзацы текста. В итоге мы получим большой набор тёмных областей разного масштаба, которые, в свою очередь, содержат различные объекты (буквы, слова, строки, блоки текста).
Этап II
В рамкахвторого этапа выполняется извлечение ключевых областей (key/keypoint region) из изображения документа. В нашем случае в качестве ключевых областей выступают связные компоненты (connected components), извлеченные методом MSER из набора предварительно обработанных изображений. При этом следует отметить, что извлечение ключевых областей может быть выполнено и другим методом, например, с использованием адаптивной бинаризации (Niblack, Sauvola и т. п.)
Отметим, что нужные нам связные компоненты должны быть стабильны при изменении порогов бинаризации. Иными словами, когда мы бинаризуем изображение с некоторым набором порогов, то в некотором диапазоне порогов могут возникать устойчивые связные компоненты, которые незначительно меняют свой размер и площадь, если объект имеет хорошо очерченные границы, в то время как на объектах без четких границ при этом сильно меняется размер и площадь выделяемых связных компонент. Такие устойчивые связные компоненты и называют MSER (Maximally Stable Extremal Region). Примеры выделенных регионов MSER разных размеров показаны на рис. 1.
Рис. 1. Исходное изображение документа (а) и регионы MSER разного размера, извлеченные из этого изображения (б), ©, (д).
Площадь выделенных регионов меньше, чем 0,005 (б), 0,01 ©, 0,05 (д) изображения документа. Цвет региона отображает его размер (наименьший регион изображен красным цветом, а наибольший — синим).
Этап III
На третьем этапе для каждой полученной ключевой области выполняется вычисление локальных дескрипторов (векторов признаков). Все дескрипторы рассчитываются для участка изображения в градациях серого.
Однако перед этим необходимо выполнить нормализацию, т.е. приведениеключевых областей к определенному размеру. Для этого строим описывающий прямоугольник для каждого извлеченного региона MSER, а затем масштабируем/преобразуем его в квадратную область некоторого фиксированного размера. Пример нормализации одного региона представлен на рис. 2.
Рис. 2. Пример нормирования области MSER. Зеленым на документе выделена область, которая нормируется к размеру 16×16.
Затем к этой области изображения применяется двумерное дискретное преобразование Фурье. Набор получаемых при этом коэффициентов есть признаковое описание области, которое обладает максимальной информативностью для конечной задачи.
Отметим, что могут применяться и другие эвристические, либо машинно-обучаемые способы извлечения признаков, например фотометрические дескрипторы (SIFT, SURF, BRISK) или геометрические (LLAH).
В нашей работе мы пробовали SIFT, SURF, DFT и DWT и различные их комбинации для того, чтобы выбрать оптимальный способ извлечения признаков. В результате мы остановились на следующем наборе признаков: компоненты преобразования Фурье + два геометрических признака, описывающих соотношение сторон охватывающего прямоугольника исходного региона и его масштаб.
Этап IV
Четвертый этап заключается в кластеризации полученных локальных дескрипторов на K кластеров методом K-средних (k-means), хотя возможно применение и других методов (K-medoids, histogram binning и т. д.).
Центры полученных кластеров будут служить визуальными словами (W) для дальнейшего анализа изображений. Из набора полученных визуальных слов получаем словарь.
Этап V
На пятом этапе для каждого кластера выполняется вычисление стандартного отклонения его локальных дескрипторов от визуального слова. Затем проводится нормализация расстояний между дескриптором и центром кластера на стандартное отклонение, чтобы в дальнейшем можно было использовать евклидово расстояние (Euclidean distance) при обнаружении визуальных слов.
Отметим, что первый набор изображений документов используется только один раз (на этапе разработки) для создания высококачественного словаря визуальных слов. В итоге полученный словарь может использоваться для обработки различных типов документов, а не только тех, на примере которых он был построен.
Способ оценки и оптимизации словаря
Отдельно опишем способ оценки и оптимизации получаемого словаря. Главная цель — обеспечить максимальную взаимную информацию (MI) положения значимого поля документа (F) относительно визуальных слов (W). Для этого необходимо вычислить взаимную информацию двух случайных величин по набору гистограмм распределения относительного положения поля по отношению ко всем визуальным словам, найденным в этом документе. Весь процесс можно разделить на девять шагов (рис. 3).
Рис. 3. Блок-схема процесса оптимизации словаря.
Для того, чтобы оценить качество полученного словаря, мы используем дополнительный (второй) набор документов, отличный от изображений, взятых для его создания.
В этом новом наборе документов мы предварительно разметили значимые поля F («Дата», «Итого», «Компания», «Валюта»), затем было произведено извлечение всех ключевых областей и соответствующих им локальных дескрипторов. Каждый извлеченный локальный дескриптор затем подвергается векторному квантованию с использованием ближайшего визуального слова в словаре (то есть ближайшего центра кластера, полученного при его создании). Мы назвали эту процедуру »обнаружением визуальных слов». Таким образом мы обнаружили все доступные визуальные слова W во втором наборе документов.
Затем мы проводим вычисления:
двумерной гистограммы h (Wi, Wj) распределения координат для каждого конкретного визуального слова W;
двумерной гистограммы h (Fi, Fj) распределения координат для конкретного значимого поля F.
Далее вычисляем условные гистограммы:
условную гистограмму h (Fi, Fj | Wk, Wl) для положения поля F при фиксированном положении (Wk, Wl) визуального слова W;
условную гистограмму h (Wi, Wj | Fk, Fl) положения слова W при фиксированном положении (Fk, Fl) поля F.
Значения бинов двухмерных гистограмм вычисляются для ячеек из пространственной сетки M×N элементов. Для примера M и N мы устанавливаем равным определенному заданному значению, например, M=N=16 или M=N=32 или M=N=64 или M=N=128, однако для этой сетки могут быть использованы и другие значения.
После того, как мы получили все четыре гистограммы, начинается вычисление взаимной информации MI (mutual information) двух случайных величин (W, F): положения поля документа F, и положения визуального слова W, по формуле:
MI (W, F) = H (F) — H (F|W) = H (W) — H (W|F),
где:
— H (F), H (W) — предельные энтропии случайных позиций F и W, вычисленные с использованием гистограммы h (Fi, Fj) и h (Wi, Wj);
— H (F|W) — условная энтропия F при условии, что значение W известно, вычисленная с использованием условной гистограммы h (Fi, Fj | Wk, Wl) и последующего усреднения результата по всем возможным позициям (Wk, Wl);
— H (W|F) — условная энтропия W при условии, что значение F известно (вычисляется по аналогии с H (F|W)).
Взаимная информация MI (W, F) двух случайных величин, позиции поля документа F и позиции слова W, является мерой взаимной зависимости между двумя переменными. Следовательно, если усреднить MI по всем визуальным словам в словаре, мы можем использовать MI в качестве интегрированной меры качества словаря для конкретного значимого поля документа.
Путем экспериментов возможно подобрать оптимальные значения параметров: необходимое количество визуальных слов в словаре, количество и тип дескрипторов, число масштабов, необходимые предобработки, весовые коэффициенты компонент дескрипторов и т. д. Все основные параметры подбираются на основании максимизации целевой функции взаимной информации.
Максимизация целевой функции может быть выполнена как в автоматическом режиме (например, градиентным спуском (Gradient descent), differential evolution и прочими известными методами оптимизации), так и в ручном режиме (перебор параметров, grid search).
Хотим еще раз подчеркнуть, что описанная выше процедура оптимизации с использованием большого количества размеченных документов из второго набора (например, счетов-фактур) выполняется только один раз на этапе разработки метода.
Завершив все описанные шаги, мы получили оптимизированный словарь визуальных слов (построенный на первом, неразмеченном наборе документов с использованием параметров, подобранных с помощью второго, размеченного набора документов), готовый к использованию на стороне пользователя, для обнаружения и извлечения важных полей на изображениях документов.
Вычисление статистических предикатов
После того, как у нас появился словарь визуальных слов, мы можем вычислить статистический предикат P (Fj) для позиции поля Fj в любом документе.
Для каждого визуального слова из словаря мы можем вычислить условную гистограмму h (Fi, Fj | Wk, Wl) позиции для конкретного поля F при фиксированной позиции (Wk, Wl) визуального слова W на документе. При вычислении этой условной гистограммы h, мы используем сдвиг S положения поля F относительно фиксированного положения слова W (для его пространственных координат).
Эта процедура вычисления условной гистограммы повторяется для всех визуальных слов. Также стоит учитывать, что на каждом изображении документа смещение будет свое (разное), но в целом они будут коррелировать друг с другом. Иными словами, условные гистограммы указывают, где примерно находится целевое поле по отношению к каждому визуальному слову.
Затем можно вычислить интегральную двумерную гистограмму h (S (F, W)) сдвига S позиции поля F, которая будет включать сдвиги относительно всех возможных позиций визуального слова W в помеченном наборе данных (h (S) — shift histogram).
Набор N гистограмм сдвига (S (F, Wj)) для всех визуальных слов Wj из словаря вместе с самим оптимизированным словарем являются полным набором данных, которого достаточно для извлечения значимых полей из новых документов. А именно для вычисления статистических предикатов позиций полей на документе.
Если нам необходимо извлечь поля из совершенно нового документа, сначала нужно обнаружить все визуальные слова W, имеющиеся в словаре. Затем для каждого визуального слова Wk словаря вычисляется предикат Pik (F) возможной позиции поля F с использованием соответствующей гистограммы сдвига h (S (F, Wk)), сохраненной вместе со словарем. Интегральный предикат Pk (F) (integral predicate) возможной позиции поля F, на основе всех визуальных слов Wk, вычисляется как сумма отдельных предикатов Pik (F) для всех визуальных слов Wk, имеющихся на документе. То есть все гистограммы накладываются друг на друга с учетом их определенного смещения. В итоге получаемсобранную из всех визуальных слов аккумулированную гистограмму распределения, которая дает предсказание положения целевого поля на документе.
Стоит отметить, что для каждого визуального слова Wk в документе, часть гистограмм сдвига h (S (F, Wk)) может не участвовать в вычислении предиката для этого визуального слова. Это связано с тем, что большие сдвиги могут привести к оценке положения поля F, которое находится за пределами области изображения документа.
Если подытожить: интегральный предикат P (F) возможного положения поля F на основе появления всех визуальных слов в документе может быть вычислен как линейная комбинация отдельных предикатов Pk (F) из различных визуальных слов Wk, обнаруженных в документе.
В качестве примера разберем рис. 5, на котором показаны статистические предикаты поля «Итого» на изображении счета-фактуры. Следует также отметить, что отдельные предикаты, основанные на отдельных визуальных словах, могут плохо предсказывать положение поля, в то время как интегральный предикат (integral predicate), рассчитанный для всех экземпляров визуальных слов, обнаруженных в документе, работает с большей точностью.
Рис. 4. Слева направо: исходное изображение; интегральный предикат P (F) для поля «Итого» (аккумулированная гистограмма); индивидуальный предикат для поля «Итого», основанный на отдельном визуальном слове. Поле «Итого» отмечено синим прямоугольником. Отдельное визуальное слово отмечено зеленым прямоугольником. Цветовая палитра показывает цвета, используемые для различных значений предиката (от 0 внизу до максимального значения вверху палитры).
Полученный статистический предикат P (i, j | F), то есть аккумулированная гистограмма-предсказатель, представляет собой двумерный массив (решетку/сетку) вероятностей появления поля F документа в различных ячейках (i, j) пространственной сетки M×N, наложенной на изображение. При этом могут быть заданы любые значения для M и N (то есть для чеков, например, удобна сетка 26×10, для счетов 16×16 и т. д.). Фактически, мы квантуем пространство по координатам на некоторое количество ячеек. И вот это разбиение на ячейки и есть итоговая гистограмма.
При вычислении гистограмм с использованием набора размеченных изображений документов мы предполагаем, что определенная ячейка содержит поле F (или слово W), если центр прямоугольника поля (или слова) попадает внутрь этой ячейки. Прогноз положения поля F может определяться положением элементов массива предикатов с топ-n значениями.
В каждой ячейке гистограммы содержится какое-то количество голосов от визуальных слов. Та ячейка, которая обладает максимальным количеством голосов, представляет собой топ-1 предсказание. Назовем ячейки сетки, содержащие n максимальных значений предиката P (i, j | F),»топ-n ячейками». Можно использовать любое из топ-1 — топ-5, чтобы искать поле на документе.
Следует обратить внимание, что интегральных гистограмм-предсказателей столько, сколько искомых значимых полей на документе — если N полей, то и N предикатов.
Пример. Предположим, что словарь содержит 800 визуальных слов. При этом на документе нашлось 200 визуальных слов, которые заполнили 200 из 800 гистограмм по всем визуальным словам. Дальше мы берем все 800 гистограмм, аккумулируем с учетом их смещений на документе, и получаем одну гистограмму-предсказатель для одного поля. Для другого поля строим другую гистограмму-предсказатель, собранную аналогичным образом из своих 800 гистограмм. Таким образом, есть тензор из 800 х N-гистограмм, где для каждого из этих N мы берем по 800 гистограмм, складываем с их взаимными положениями и получаем гистограмму-предсказатель (статистический предикат). Когда будут получены N таких статистических предикатов, можно по ним предсказать положение для всех N значимых полей.
Э-э-эксперименты!
Во всех наших экспериментах мы использовали словарь визуальных слов, созданный на основе набора данных из 6 тысяч неразмеченных изображений счетов-фактур с примерно 72 тысячами локальных дескрипторов. Это случайное подмножество нашего датасета, состоящего из 60 тысяч счетов-фактур, который включает различные документы из разных стран и от разных поставщиков.
Счета-фактуры
Для эксперимента со счетами-фактурами мы использовали набор данных, упомянутый выше, и сосредоточились на поиске трех полей: «Итого», «Валюта» и «Дата счета» (мы остановились на трех позициях, но ограничений по их количеству в нашем методе нет).
Для вычисления двумерных гистограмм мы применили сетку из 16×16 ячеек. Подмножество из 34 изображений с одинаковой структурой и от одного производителя было произвольно разделено на 15 обучающих и 19 тестируемых изображений. Для измерения точности во всех наших экспериментах мы применяли кросс-валидацию. В этом эксперименте интегрированный предикат рассчитывался как простая сумма предикатов отдельных визуальных слов.
В итоге мы выяснили, что точность различается для трех полей. Это связано с тем, что их позиции колеблются в разных диапазонах даже для одного шаблона документов:
Таб. 1
Стоит отметить, что мы получили топ-10 точность 0,918 (в среднем по трем полям), используя только 5 размеченных изображений для тестирования.
Точность предсказания соответствует тому, что поле может появиться на участке площадью лишь ~3,8% от всего изображения. Эта информация является очень ценной, когда предлагаемый метод используется в качестве вспомогательного инструмента в подходах, основанных на распознавании текста.
Еще две важные особенности метода
Повышение точности извлечения полей отмечается в том случае, когда минимизированы колебания положения полей у нового типа документа, к которому мы хотим применить словарь визуальных слов.
Для более эффективного решения задачи поиска полей (то есть для повышения точности и скорости) может быть использована предварительная группировка документов по визуальной схожести. Иными словами, если перед работой удается классифицировать документы (разбить на группы по типам документов, по фирме от которой поступили документы и т. д.) так, чтобы они были визуально похожи, то это многократно повысит качество извлечения полей в каждой группе документов. Такая группировка может быть выполнена как в ручном, так и в автоматическом режиме.
Применение
Наш метод может быть использован:
самостоятельно (когда пользователь размечает только несколько обучающих документов. Такой сценарий довольно частый для выполнения реальных задач);
как вспомогательная техника в подходах, основанных на распознавании текста или для облегчения обучения нейронных сетей.
Что дальше?
Дальнейшее развитие нашей разработки может быть направлено на адаптацию предложенного метода к обработке документов, удостоверяющих личность (ID). Предварительные эксперименты показали, что словарь визуальных слов хорошо работает с некоторыми полями таких документов. Также повысить точность в таком эксперименте возможно, если словарь будет содержать важные визуальные слова, соответствующие элементам ID-документов.
Список литературы
Loginov V., Valiukov A., Semenov S., Zagaynov I. Document Data Extraction System Based on Visual Words Codebook. In: Bai X., Karatzas D., Lopresti D. (eds) Document Analysis Systems. DAS 2020. Lecture Notes in Computer Science, vol 12116. Springer, Cham. (2020). link
Augereau, O., Journet, N., Domenger, J.P.: Semi-structured document image matching and recognition. In: Zanibbi, R., Couasnon, B. (eds.) Document Recognition and Retrieval XX. vol. 8658, pp. 13{24. International Society for Optics and Photonics, SPIE (2013). link
Cristani, M., Bertolaso, A., Scannapieco, S., Tomazzoli, C.: Future paradigms of automated processing of business documents. International Journal of Information Management 40, 67{75 (06 2018). link
Daher, H., Bouguelia, M.R., Belad, A., D’Andecy, V.P.: Multipage administrative document stream segmentation. 2014 22nd International Conference on Pattern Recognition pp. 966{971 (2014)
Gao, H., Rusi~nol, M., Karatzas, D., Llados, J., Sato, T., Iwamura, M., Kise, K.: Key-region detection for document images { application to administrative document retrieval. In: 2013 12th International Conference on Document Analysis and Recognition. pp. 230{234 (2013)
Sivic, J., Zisserman, A.: Video Google: A text retrieval approach to object matching in videos. In: IEEE International Conference on Computer Vision. vol. 2, pp. 1470{ 1477 (2003)
Sun, W., Kise, K.: Similar manga retrieval using visual vocabulary based on regions of interest. 2011 International Conference on Document Analysis and Recognition pp. 1075{1079 (2011)
Takeda, K., Kise, K., Iwamura, M.: Real-time document image retrieval for a 10 million pages database with a memory ecient and stability improved LLAH. 2011 International Conference on Document Analysis and Recognition, ICDAR 2011, Beijing, China, September 18–21, 2011 pp. 1054{1058 (2011). link
