Как составить визуальный словарь

Словарь визуальных слов: как создать, зачем использовать, где применять

Автоматическое извлечение информации из деловых документов (счетов-фактур, квитанций, 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.

Этап III

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

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

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

Отметим, что могут применяться и другие эвристические, либо машинно-обучаемые способы извлечения признаков, например фотометрические дескрипторы (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).

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

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

Затем мы проводим вычисления:

1. двумерной гистограммы h(W_i,W_j) распределения координат для каждого конкретного визуального слова W;

2. двумерной гистограммы h(F_i,F_j) распределения координат для конкретного значимого поля F.

Далее вычисляем условные гистограммы:

1. условную гистограмму h(F_i,F_j | W_k,W_l) для положения поля F при фиксированном положении (W_k,W_l) визуального слова W;

2. условную гистограмму h(W_i,W_j | F_k,F_l) положения слова W при фиксированном положении (F_k,F_l) поля 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(F_i,F_j) и h(W_i,W_j);

– H(F|W) – условная энтропия F при условии, что значение W известно, вычисленная с использованием условной гистограммы h(F_i,F_j | W_k,W_l) и последующего усреднения результата по всем возможным позициям (W_k,W_l);

– H(W|F) – условная энтропия W при условии, что значение F известно (вычисляется по аналогии с H(F|W)).

Взаимная информация MI(W,F) двух случайных величин, позиции поля документа F и позиции слова W, является мерой взаимной зависимости между двумя переменными. Следовательно, если усреднить MI по всем визуальным словам в словаре, мы можем использовать MI в качестве интегрированной меры качества словаря для конкретного значимого поля документа.

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

Максимизация целевой функции может быть выполнена как в автоматическом режиме (например, градиентным спуском (Gradient descent), differential evolution и прочими известными методами оптимизации), так и в ручном режиме (перебор параметров, grid search).

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

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

Вычисление статистических предикатов

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

Для каждого визуального слова из словаря мы можем вычислить условную гистограмму h(F_i,F_j | W_k,W_l) позиции для конкретного поля F при фиксированной позиции (W_k,W_l) визуального слова W на документе. При вычислении этой условной гистограммы h, мы используем сдвиг S положения поля F относительно фиксированного положения слова W (для его пространственных координат).

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

Затем можно вычислить интегральную двумерную гистограмму h(S(F,W)) сдвига S позиции поля F, которая будет включать сдвиги относительно всех возможных позиций визуального слова W в помеченном наборе данных (h(S) – shift histogram).

Набор N гистограмм сдвига (S(F,W_j)) для всех визуальных слов W_j из словаря вместе с самим оптимизированным словарем являются полным набором данных, которого достаточно для извлечения значимых полей из новых документов. А именно для вычисления статистических предикатов позиций полей на документе.

Если нам необходимо извлечь поля из совершенно нового документа, сначала нужно обнаружить все визуальные слова W, имеющиеся в словаре. Затем для каждого визуального слова W_k словаря вычисляется предикат P_ik(F) возможной позиции поля F с использованием соответствующей гистограммы сдвига h(S(F,W_k)), сохраненной вместе со словарем. Интегральный предикат P_k(F) (integral predicate) возможной позиции поля F, на основе всех визуальных слов W_k, вычисляется как сумма отдельных предикатов P_ik (F) для всех визуальных слов W_k, имеющихся на документе. То есть все гистограммы накладываются друг на друга с учетом их определенного смещения. В итоге получаем собранную из всех визуальных слов аккумулированную гистограмму распределения, которая дает предсказание положения целевого поля на документе.

Стоит отметить, что для каждого визуального слова W_k в документе, часть гистограмм сдвига h(S(F,W_k)) может не участвовать в вычислении предиката для этого визуального слова. Это связано с тем, что большие сдвиги могут привести к оценке положения поля F, которое находится за пределами области изображения документа.

Если подытожить: интегральный предикат P(F) возможного положения поля F на основе появления всех визуальных слов в документе может быть вычислен как линейная комбинация отдельных предикатов P_k(F) из различных визуальных слов W_k, обнаруженных в документе.

В качестве примера разберем рис. 5, на котором показаны статистические предикаты поля «Итого» на изображении счета-фактуры. Следует также отметить, что отдельные предикаты, основанные на отдельных визуальных словах, могут плохо предсказывать положение поля, в то время как интегральный предикат (integral predicate), рассчитанный для всех экземпляров визуальных слов, обнаруженных в документе, работает с большей точностью.

Полученный статистический предикат 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 тестируемых изображений. Для измерения точности во всех наших экспериментах мы применяли кросс-валидацию. В этом эксперименте интегрированный предикат рассчитывался как простая сумма предикатов отдельных визуальных слов.

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

Стоит отметить, что мы получили топ-10 точность 0,918 (в среднем по трем полям), используя только 5 размеченных изображений для тестирования.

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

Еще две важные особенности метода

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

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

Применение

Наш метод может быть использован:

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

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

Что дальше?

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

Список литературы

1. 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

2. 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

3. 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

4. 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)

5. 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)

6. 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)

7. 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)

8. 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

Если вы хотите работать в международной IT-компании и создавать высокотехнологичные продукты, то в моей команде открыта вакансия: https://www.abbyy.com/ru/company/careers/open-positions/1474/?senior-software-developer-cv-s

Автоматическое извлечение информации из деловых документов (счетов-фактур, квитанций, 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.

Этап III

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

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

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

Отметим, что могут применяться и другие эвристические, либо машинно-обучаемые способы извлечения признаков, например фотометрические дескрипторы (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).

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

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

Затем мы проводим вычисления:

1. двумерной гистограммы h(W_i,W_j) распределения координат для каждого конкретного визуального слова W;

2. двумерной гистограммы h(F_i,F_j) распределения координат для конкретного значимого поля F.

Далее вычисляем условные гистограммы:

1. условную гистограмму h(F_i,F_j | W_k,W_l) для положения поля F при фиксированном положении (W_k,W_l) визуального слова W;

2. условную гистограмму h(W_i,W_j | F_k,F_l) положения слова W при фиксированном положении (F_k,F_l) поля 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(F_i,F_j) и h(W_i,W_j);

– H(F|W) – условная энтропия F при условии, что значение W известно, вычисленная с использованием условной гистограммы h(F_i,F_j | W_k,W_l) и последующего усреднения результата по всем возможным позициям (W_k,W_l);

– H(W|F) – условная энтропия W при условии, что значение F известно (вычисляется по аналогии с H(F|W)).

Взаимная информация MI(W,F) двух случайных величин, позиции поля документа F и позиции слова W, является мерой взаимной зависимости между двумя переменными. Следовательно, если усреднить MI по всем визуальным словам в словаре, мы можем использовать MI в качестве интегрированной меры качества словаря для конкретного значимого поля документа.

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

Максимизация целевой функции может быть выполнена как в автоматическом режиме (например, градиентным спуском (Gradient descent), differential evolution и прочими известными методами оптимизации), так и в ручном режиме (перебор параметров, grid search).

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

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

Вычисление статистических предикатов

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

Для каждого визуального слова из словаря мы можем вычислить условную гистограмму h(F_i,F_j | W_k,W_l) позиции для конкретного поля F при фиксированной позиции (W_k,W_l) визуального слова W на документе. При вычислении этой условной гистограммы h, мы используем сдвиг S положения поля F относительно фиксированного положения слова W (для его пространственных координат).

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

Затем можно вычислить интегральную двумерную гистограмму h(S(F,W)) сдвига S позиции поля F, которая будет включать сдвиги относительно всех возможных позиций визуального слова W в помеченном наборе данных (h(S) – shift histogram).

Набор N гистограмм сдвига (S(F,W_j)) для всех визуальных слов W_j из словаря вместе с самим оптимизированным словарем являются полным набором данных, которого достаточно для извлечения значимых полей из новых документов. А именно для вычисления статистических предикатов позиций полей на документе.

Если нам необходимо извлечь поля из совершенно нового документа, сначала нужно обнаружить все визуальные слова W, имеющиеся в словаре. Затем для каждого визуального слова W_k словаря вычисляется предикат P_ik(F) возможной позиции поля F с использованием соответствующей гистограммы сдвига h(S(F,W_k)), сохраненной вместе со словарем. Интегральный предикат P_k(F) (integral predicate) возможной позиции поля F, на основе всех визуальных слов W_k, вычисляется как сумма отдельных предикатов P_ik (F) для всех визуальных слов W_k, имеющихся на документе. То есть все гистограммы накладываются друг на друга с учетом их определенного смещения. В итоге получаем собранную из всех визуальных слов аккумулированную гистограмму распределения, которая дает предсказание положения целевого поля на документе.

Стоит отметить, что для каждого визуального слова W_k в документе, часть гистограмм сдвига h(S(F,W_k)) может не участвовать в вычислении предиката для этого визуального слова. Это связано с тем, что большие сдвиги могут привести к оценке положения поля F, которое находится за пределами области изображения документа.

Если подытожить: интегральный предикат P(F) возможного положения поля F на основе появления всех визуальных слов в документе может быть вычислен как линейная комбинация отдельных предикатов P_k(F) из различных визуальных слов W_k, обнаруженных в документе.

В качестве примера разберем рис. 5, на котором показаны статистические предикаты поля «Итого» на изображении счета-фактуры. Следует также отметить, что отдельные предикаты, основанные на отдельных визуальных словах, могут плохо предсказывать положение поля, в то время как интегральный предикат (integral predicate), рассчитанный для всех экземпляров визуальных слов, обнаруженных в документе, работает с большей точностью.

Полученный статистический предикат 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 тестируемых изображений. Для измерения точности во всех наших экспериментах мы применяли кросс-валидацию. В этом эксперименте интегрированный предикат рассчитывался как простая сумма предикатов отдельных визуальных слов.

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

Стоит отметить, что мы получили топ-10 точность 0,918 (в среднем по трем полям), используя только 5 размеченных изображений для тестирования.

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

Еще две важные особенности метода

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

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

Применение

Наш метод может быть использован:

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

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

Что дальше?

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

Список литературы

1. 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

2. 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

3. 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

4. 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)

5. 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)

6. 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)

7. 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)

8. 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

Если вы хотите работать в международной IT-компании и создавать высокотехнологичные продукты, то в моей команде открыта вакансия: https://www.abbyy.com/ru/company/careers/open-positions/1474/?senior-software-developer-cv-s

Adobe Design is accustomed to working on large-scale projects. But when four people from the team said yes to a pro bono project that resulted in a collaboration with literally hundreds of volunteer designers from around the world, the scale wasn’t just large, it was global.

Adobe’s involvement began early on, shortly after Douglas Gayeton, co-founder of The Lexicon and Nathan Shedroff, designer and founder of the Design MBA programs at California College of the Arts (CCA), conceived of a way to aid communication and collaboration between food industry sectors by creating Foodicons, a universal visual language describing food systems.

Through a series of introductions Gayeton and Shedroff connected with program manager Lisa Pedee, who organizes pro bono collaborations for Adobe Design. A master of pairing the right people with the right projects, she knew exactly who to contact: Senior design manager Sonja Hernandez had not only been a pro bono partner many times prior, she and her team are skilled at creating massive icon libraries (together they create approximately 15,000 icons each year for Adobe products).

It wasn’t long before Nayane de Souza Hablitzel and Isabelle Hamlin — experience designers passionate about iconography — had volunteered.

Trading words for pictures

The visual vocabulary Shedroff and Gayeton imagined would be less likely to get watered-down by overuse or misuse. It could be used by farmers, food producers, and retailers and encourage more specific dialogue by unifying and differentiating subtle characteristics of terminology. And it could prevent a word like “irrigation” being used without descriptors, without nuance, instead of more specific terms (like deficit irrigation, scheduled irrigation, reduced irrigation, drip irrigation, precision irrigation, or subsurface irrigation).

Six types of irrigation defined by Foodicons. Clockwise from top right: Deficit Irrigation/Scheduled Irrigation/Reduced Irrigation/Drip Irrigation, Foodicons team; Precision Irrigation/Subsurface Irrigation, Jeanette Pantelides.

They envisioned the language being created by a partnership between food experts and designers.

So they outlined the International Foodicons Challenge, a worldwide call to designers to contribute to an open-source icon system. And through Green Brown Blue, The Lexicon’s 501(c)3 accelerator addressing global challenges facing food systems, they called in experts from the food industry to help prioritize a group of terms to create the language’s foundation. Finally Shedroff began working with CCA instructor Eric Heiman to create a real-world prototyping assignment, with the same food experts as clients, for TBD*, CCA’s student-run design studio.

The first prototyping of Green Brown Blue’s Foodicons by CCA’s design studio. Clockwise from top right: No-till Farming, Jennifer Lam, Livestock, Yufan Niu, Water, MoMo Gao, Climate Smart, Ileana Garay, Supply Cycle, Yufan Niu, Net-caught Fish, Keston Hinds Cruz.

Creating a design system

In March 2020 Hablitzel and Hamlin began by researching imagery, iconography, and agricultural terminology (not just familiar phrases like “cage-free “and “pasture raised” but more complex concepts like “keystone species” and “soil microbes”).

Shedroff and Douglas had chosen the hexagonal icon shape as a metaphor for the agricultural world (bees and honeycombs) and the “hive mind” approach to Foodicons. Hablitzel and Hamlin expanded it: They subtracted corners, left gaps, and added dashed lines, arrows, and fills to provide for different meanings, and began thinking about color to ensure that if it was used, it would be used intentionally. And when they began to develop the library of art that would comprise the language inside the hexagons, they made one of the most significant breakthroughs of Foodicons… a series of modifiers (a clock, plus/minus signs, arrows, a checkmark) that would extend its vocabulary.

Modifiers used in the Food Equity icon — a hand holding an apple — incrementally change the meaning. Clockwise from top right: need more (plus), verified (checkmark), improving (up arrow), and time sensitive (clock).

Because TBD* had learned so much while prototyping, Hablitzel and Hamlin moved quickly.

Once they’d developed an approach, their primary considerations during refinement were simplicity and scalability: Gaps, stroke size, the specific placement of interior art, modifiers, the variety of hexagon styles all had to support every icon being readable and understandable at every size. They eventually compiled all of this information into a set of design guidelines, a modular system of shapes, metaphors, templates, and a library of elements that would make the language consistent no matter how many different designers were creating them.

The Grid, a layer in the Illustrator Template file, specifies how and where to place elements inside the hexagon.

To ensure their design instructions were clear Hablitzel and Hamlin tested them by creating icons (imagining they knew nothing more than the information they were supplying to other designers) and then asked their Adobe Design colleagues to do the same. Based on what they learned during these sessions they removed instructions from their guidelines that were too complex or that didn’t produce the results they intended.

A challenge unfolds

With that part of their task complete Isabelle and Hablitzel ‘s attention turned to the design of a website and a set of e-cards. The multipurpose Foodicons site<u>,</u> created in partnership with The Lexicon’s digital producer Pier Giorgio Provenzano, would eventually house the entire icon library but its primary purpose at launch was as a gateway for designers to sign up for the challenges and download the templates and guidelines. This final work set in motion the global design invitation that Douglas and Shedroff had envisioned.

Samples from a social media e-card campaign to introduce the design challenge. Each is composed of an icon with a transparent gradient background superimposed over a related Adobe Stock image.

The first International Foodicons Challenge launched in December 2020.

Contributing designers were asked to detail their process in digital workbooks. So when they started submitting, the work consisted of pages and pages of notes and sketches outlining rough concepts. Initial design reviews were followed by time-intensive design development, where the focus shifted to adherence to guidelines.

Throughout these initial rounds, Hablitzel and Hamlin (and the rest of the team) carefully considered the feedback they were providing to ensure it would remain consistent throughout the series of challenges. Changes to the design guidelines, the templates, and even the instructions were based on the submissions they saw during these first rounds of the first challenge.

Three more challenges like it would follow. Each was open for two months and no icon was selected unless every judge agreed on its clarity, validity, and… good design.

A global library let loose

The fourth and final challenge ended in early September. At that time more than 600 icons, by 390 designers, from 58 countries had been created.

Since then, the Foodicons library has been uploaded to The Noun Project, the most comprehensive open-source icon collection, and unveiled at the FAO World Food Forum (WFF), a global youth-led movement to transform world food systems.

WFF will continue to add new terms yearly so the crowdsourced and open-sourced project is far from over and Gayeton and Shedroff will stay on as advisors.

But since the goal for Hablitzel and Hamlin was to create a system that would result in a library of icons, their work is complete. As is Pedee and Hernandez’s who’ve worked behind-the-scenes (judging icons, offering advice, building bridges, making connections, and supporting their team) from the beginning.

The project lasted 18 months and together the group of four has invested over 350 hours.

It would have been impossible for any of them to predict the level of commitment they were making, or how much time and effort they would pour into it. But they’d do it all over again. Because what Hamlin and Hablitzel understand now, and Pedee and Hernandez already knew, is that every project like it offers an opportunity to showcase, outside of Adobe Design, the efforts and strengths and talents of a team.