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

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



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

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

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

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

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


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

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


Однако, шаблон g(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%

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

Заключение

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

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