Многие документы содержат защитные элементы, такие как голограммы, водяные знаки, гильош и т.д. В процессе сканирования таких документов возникает проблема — защитные элементы мешают системам распознавания (OCR). При разработке Smart PassportReader мы провели исследование, направленное на поиск и устранение подобных защитных элементов с изображений документов.

Рассмотрим пример паспорта гражданина РФ, на котором легко увидеть периодический голографический узор.



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

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

Модель изображения


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

Пусть I(x) — исходное изображение длины N, состоящее из двух других: фонового изображения h(x) и изображения, содержащего периодический шаблон g(x):


Обычно, фоном на документах называют всё, кроме текстовой информации; в данном же случае фон — всё, кроме периодического шаблона.

Мы можем считать, что количество одиночных экземпляров (изображений одного “орла” на паспорте РФ), составляющих шаблон, заранее известно и равно M. При их равномерном распределении период между ними будет равен T = N / M. Тогда, изображение шаблона g(x) может быть представлено суммой одиночных экземпляров f(x), сдвинутых на соответствующую величину:


Однако, шаблон g(x) можно представить более удобным способом. В обработке сигналов часто используется дельта-функция \delta(x), равная единице при x = 0 и нулю в противном случае. Сейчас мы на примере покажем, чем обусловлена ее популярность.

Рассмотрим функцию c(x), составленную из суммы дельта-функций с периодом T. Дельта-функции у нее находятся там, где находится соответствующий экземпляр шаблона f(x), а в остальных местах — нули. Такую функцию называют Dirac comb (гребень Дирака, потому что кому-то она напоминает расческу) или Impulse train.


На рисунке показан пример гребня Дирака для N = 256 и M = 8 (T = 256 / 8 = 32).



Тогда, периодический сигнал шаблона g(x) можно представить как свертку (convolution) одного экземпляра шаблона f(x) с гребнем Дирака c(x):


Можете быть уверены: любой, кто только что использовал слова “периодический” и “свертка” в одном предложении, сейчас начнет рассказывать про преобразование Фурье.

Дискретное преобразование Фурье от периодического шаблона


Обозначим дискретное преобразование Фурье (ДПФ) от g(x) как . Напомним, что ДПФ переводит массив чисел длины N в массив комплексных чисел той же длины, где на k позиции находится информация (амплитуда и фазовый сдвиг) о гармонике с частотой , составляющей исходный сигнал.

Одним из важнейших свойств преобразования Фурье является теорема о свертке, по которой Фурье-спектр свертки оригинальных сигналов является произведением их Фурье-спектров:


Рассмотрим отдельно ДПФ от гребня Дирака . Известно, что ДПФ одной дельта-функции равно:


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


Комплексная экспонента является периодической от с периодом , а равно единице. Легко заметить, что для k, кратных M (k = 0, M, 2M, …), сумма становится равна M, поскольку каждый член суммы становится равен единице, а всего членов М. Сложнее заметить то, что для остальных значений k (не кратных М) равняется нулю, потому что все члены суммы взаимоуничтожаются. Если интересно доказать этот факт — попробуйте нарисовать на окружности M точек с интервалом (угол для m-й точки ), а потом отдельно просуммируйте их координаты — сначала x, а потом y.

Мы получили важный факт — преобразование Фурье от суммы M равномерно распределенных дельта-функций также является суммой дельта функций (умноженной на M), но уже с периодом M:


Другими словами, если в исходном сигнале с предыдущей иллюстрации уместилось M = 8 дельта-функций, то, вне зависимости от длины сигнала, ДПФ будет иметь “пики” через каждые 8 позиций, как показано на рисунке (показаны действительные части, так как мнимые всегда равны нулю).



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


Таким образом, мы можем легко “узнать” периодический сигнал, посмотрев только на его ДПФ.

ДПФ при сдвиге изображения периодического шаблона


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

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

Двумерный случай


Для двумерных изображений, на которых и требуется детектировать периодический шаблон, ситуация очень похожая: к горизонтальному периоду добавляется вертикальный, а на ДПФ все так же присутствует картинка с “пиками”, но теперь двумерная. Например, для 5х4 решетки из Гауссианов амплитуда ДПФ выглядит вот так:

----> ДПФ ---->

Расстояние между пиками на ДПФ по горизонтали — 5, а по вертикали — 4, что равно количеству “вместившихся” экземпляров на исходной картинке.

На паспортах РФ периодический голографический шаблон выглядит несколько иначе и похож на шахматную доску:

----> ДПФ ---->

Амплитуда ДПФ также похожа на шахматную доску с расстоянием 4 между пиками по вертикали и горизонтали, но сами горизонтали и вертикали проходят через каждые 2 пикселя. Это вызвано тем, что шахматную доску можно представить как сумму двух решеток, одна из которых сдвинута по диагонали. Так как ДПФ линейно, то ДПФ шахматной доски будет суммой ДПФ решеток.

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

Детектирование периодического шаблона


Основная идея метода в том, чтобы проверить амплитуду ДПФ изображения и убедиться, что она содержит ожидаемую структуру пиков.

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



Важно очень точно определить требуемые размеры региона, потому что ошибка даже в 5% может сильно испортить картинку ДПФ амплитуды — ведь сигнал перестанет быть периодическим.

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

Самый простой способ — сильно уменьшить размер изображения. В нашем случае мы делали уменьшение до 56х58, когда исходный размер был 910х938, т.е. в 16 раз по каждой стороне картинки. Вдобавок, можно использовать морфологическое замыкание, чтобы убрать остатки текста и прочих мелких деталей на изображении:

----> ---->

Наконец, пришло время посмотреть, как выглядит амплитуда ДПФ от обработанного изображения в окрестности центра:

----> ДПФ ---->

На рисунке отчетливо видна структура пиков, которую мы и ожидали. Для наглядности, приведем пример ДПФ от региона изображения паспорта, на котором изначально не было голографического узора:

----> ДПФ ---->


Видно, что вышеупомянутой пиковой структуры тут нет.

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

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

Трудоемкость метода


Давайте еще раз опишем основные шаги метода и их трудоемкость:

  • Уменьшение размера изображения с N до N*: O(N)
  • Обработка уменьшенного изображения: O(N*)
  • Быстрое дискретное преобразование Фурье: O(N* log N*)
  • Анализ наличия пиковой структуры на амплитуде Фурье-спектра: O(1)

Важно заметить, что вся обработка изображения и последующее дискретное преобразование Фурье происходит на сильно уменьшенной картинке, которая, к тому же, имеет постоянный размер N*, не зависящий от исходного размера изображения. Поэтому, мы можем считерить и сказать, что трудоемкость нашего алгоритма — O(N), где N — размер исходного изображения, потому что все остальное становится константой.

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

Результаты


Мы использовали 3 набора с отсканированными изображениями паспортов РФ: один из них положительный, т.е. содержащий изображения с голографическими узорами, а другие два — отрицательные. На первом из отрицательных наборов присутствовали паспорта РФ с печатным текстом, а на втором — с рукописным (да, такие еще существуют).

Описание набора данных Количество изображений Принято Отвергнуто
Положительный 484 99,38% 0,62%
Отрицательный, печатный текст 522 1,72% 98,28%
Отрицательный, рукописный текст 204 0,00% 100,00%

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

Заключение


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

Наш метод решает задачу детектирования, т.е. ответа да/нет на вопрос присутствия периодического шаблона на изображении. Но можно ли расширить метод, чтобы после положительного детектирования он еще и говорил, где именно находятся все элементы этого шаблона? Да, можно, и мы это умеем делать, причем также через анализ Фурье-спектра (теперь — фазы, а не амплитуды), но об этом — в другой раз.

Комментарии (18)


  1. lockywolf
    02.06.2015 12:34

    Хе. Круто звучит.


  1. EndUser
    02.06.2015 13:04
    -1

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


    1. SmartEngines Автор
      02.06.2015 13:22
      +1

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


      1. EndUser
        04.06.2015 13:18

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


        1. SmartEngines Автор
          04.06.2015 16:43

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


  1. denis_g
    02.06.2015 14:22
    +5

    Действительно полезная статья. Для некоторых ;)

    Скрытый текст


  1. RobotVzryvatelMin
    02.06.2015 17:05
    +1

    А вы в курсе, что обрезать картинку в вашей задаче до целого числа периодов вовсе не нужно?


    1. SmartEngines Автор
      02.06.2015 17:28
      +1

      Спасибо за ценное замечание! Действительно, если число периодов не целое, но хотя бы один период присутствует, то можно продолжить картинку до целого числа периодов и свести задачу к описанной.
      С другой стороны, появляется риск получить периодические элементы там, где их изначально не было, а также возможны небольшие проблемы со «стыковкой» периодических элементов шаблона.


      1. RobotVzryvatelMin
        02.06.2015 18:25

        Про получить периодические элементы я не понял. Вроде бы такого не должно быть. А про стыковку все так. Но +1 к числу периодов наверняка пересилят по эффекту.

        Кроме того кажется, что можно добить нулями, а не копией. А в модель сигнала явно ввести умножение на ступеньку.


        1. SmartEngines Автор
          02.06.2015 19:21
          +1

          Под полученными периодическими элементами имелись в виду случайные контрастные фоновые элементы, которые, при повторении, могут в Фурье-спектре внезапно выглядеть, как требуемые периодические. Хотя, при должном рассмотрении, эта ситуация должна решаться.

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


          1. RobotVzryvatelMin
            02.06.2015 19:24
            +1

            Да, с умножением я лоханулся. А вот доклейка наверняка улучшит метод.


  1. RobotVzryvatelMin
    02.06.2015 18:20

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


    1. RobotVzryvatelMin
      02.06.2015 18:21

      Там еще и наклоны будут наверняка…


    1. SmartEngines Автор
      02.06.2015 18:30

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


  1. RobotVzryvatelMin
    02.06.2015 18:29

    А еще у вас в теореме о свертке опечатка. Ха-ха!


    1. SmartEngines Автор
      02.06.2015 18:47

      Спасибо, исправили — очень неудобно ТеХовые формулы писать не напрямую, а через сторонние сайты перегонять в картинки.


  1. Calvrack
    02.06.2015 20:46

    Меня очень смущает картинка про применение ДПФ к гауссианам, должны вроде не квадратные точки а гауссианы получаться?


    1. SmartEngines Автор
      02.06.2015 21:30

      Каждая квадратная точка — это один пиксель. Такая решетка из пикселей получается по той же причине, что и в одномерном случае — спектр гауссианы умножается на спектр периодической решетки (который, как мы показали, также является периодической решеткой), с которой она свернута.