SmartEngines Sep 16 2015 at 10:59

Поиск периодических элементов защиты Паспорта РФ с помощью преобразования Фурье: часть вторая

8 min

21K

Smart Engines corporate blogAlgorithms*Mathematics*Image processing*Programming*

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

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

Как и в прошлый раз, для этого будет использоваться преобразование Фурье.

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

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

Напомним, что $I(x)$ — исходное изображение длины $N$ , состоящее из двух других: фонового изображения $h(x)$ и изображения $g(x)$ , содержащего периодический шаблон. Изображение $g(x)$ , в свою очередь, мы представили сверткой (convolution) одного экземпляра шаблона $f(x)$ с гребнем Дирака $c(x)$ :

$I(x) = h(x) + g(x) = h(x) + f(x) \ast c(x)$

Так как нам заранее известна структура периодического шаблона (в случае паспорта РФ — размер и период голограмм), для восстановления положения элементов достаточно знать только сдвиг всего шаблона по горизонтали и вертикали, что есть то же самое, что сдвиг одного из “орлов”.

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

Сдвиг сигнала паттерна $g(x)$ равносилен сдвигу импульсной функции $c(x)$ , который приводит к измененной форме $\mathcal{F} c(x)$ . Спектр преобразования Фурье сдвинутого сигнала изменяется только в фазе, оставляя неизменной амплитуду, позволяя, тем самым детектировать периодические паттерны вне независимости от их начального сдвига. Как важное следствие, вся полезная фазовая информация сосредоточена в тех же самых ДПФ позициях (частотах), что и пики амплитуды импульсного сигнала.

Предположим, что $c(x)$ сдвинут вправо на $S$ , тогда:

$\mathcal{F}_k c(x - S) = \mathcal{F}_k c(x) \cdot e^{i \Phi_k},$

$\Phi_k = \Phi \cdot k, \Phi=-\frac{2\pi}{N}S$

Поскольку фазовый угол $\mathcal{F}_k c(x)$ для несмещенного $c(x)$ равен нулю, для смещенного $c(x-S)$ он становится равным $\Phi_k$ . Для получения фазового сдвига $\mathcal{F}_k g(x)$ нам необходимо добавить каждый член $\Phi_k$ к соответствующему фазовому углу в $\mathcal{F}_k f(x)$ для каждого $k$ . Заметим, что любой фазовый угол всегда берется по модулю $2\pi$ и ограничивается интервалом $[-\pi;\pi)$ .

Фазовый сдвиг на $2\pi$ в частотной области представляет сдвиг $N$ во временной области, но $c(x)$ имеет период $T=\frac{N}{M}$ , поэтому мы может избежать избыточности рассмотрением лишь ${s=S \text{ mod } T}$ , обеспечив таким образом $0\le s < T$ . Для удобства, пусть $\phi$ – это фазовый сдвиг, у которого $2\pi$ соответствует временному сдвигу на $s$ , а также пусть $\phi_m$ – это фазовый угол на $m$ 'ом амплитудном пике:

$\phi_m = \phi \cdot m, \phi = -\frac{2\pi}{T}s = \Phi \cdot M$

На рисунке показан пример ДПФ фазы сдвинутого импульсного сигнала с значениями ${N=256}$ , периодом $T=32$ и сдвигом $s = 7$ . Например, $\phi_0 = 0$ и $\phi_6 = (-\frac{2\pi}{32}\cdot 7) \cdot 6 \approx -1,963$ .

А вот так выглядит амплитуда и фаза ДПФ для похожей на шахматную доску сетки Гауссиан:

— ДПФ -->

Для двумерного изображения, фазовый сдвиг $\phi$ теперь состоит из двух компонент $(\phi_x, \phi_y)$ . Введем координатную сетку для ДПФ шахматоподобной системы пиков, показанных на втором и третьем рисунках выше, такую, что центральный пик имеет координаты $(0, 0)$ , пики справа вверху $(2, 0)$ , $(0, 2)$ и так далее; ближайший диагональный пик имеет координаты $(1, 1)$ . В общем случае, пик $(i, j)$ присутствует тогда и только тогда, когда $(i + j)$ – четно.

Применяя вновь теорему о ДПФ сдвинутого сигнала, можно расширить уравнение сдвига и показать, что фазовый угол $\phi_{i, j}$ на $(i, j)$ пике для двумерного импульсного сигнала равен:

$\phi_{i, j} = i \cdot \phi_x + j \cdot \phi_y$

Как и для одномерного случая, для получения сдвинутой фазы $\mathcal{F}_{i, j} g(x)$ необходимо добавить $\phi_{i, j}$ к соответствующей фазе $\mathcal{F}_{i, j}f(x)$ .

Поиск периодического шаблона

Для определения точного местоположения периодического паттерна достаточно оценить его фазовый сдвиг $\phi = (\phi_x, \phi_y)$ , поскольку его пиксельная периодическая структура заранее известна. Пиксельный сдвиг $s = (s_x, s_y)$ , впоследствии, нетрудно восстановить по информации о фазовом сдвиге.

Вырезание, масштабирование и предобработка изображения

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

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

— обработка -->

— ДПФ -->

Как и ожидалось, амплитуда ДПФ имеет заметные пики с распределением, похожим на шахматную доску.

Предобработка спектра

В соответствии с моделью изображения, исходное изображение состоит из трех независимых сигналов: фонового изображения $h(x)$ и единичного образца периодического паттерна $f(x)$ , который свертывается со сдвинутым импульсным сигналом $c(x)$ , чтобы получить периодический паттерн $g(x)$ :

$I(x) = h(x) + f(x) * c(x)$

После выполнения ДПФ на $I(x)$ , мы имеем:

$\label{eq:immodel_dft_base} \mathcal{F} I(x) = \mathcal{F} h(x) + \mathcal{F} f(x) \cdot \mathcal{F} c(x)$

Для получения сдвига фаз $\phi$ , хранящегося в $c(x)$ , из $\mathcal{F} I(x)$ , которое мы вычислили для данного изображения, нам необходимо постепенно подавить остальные компоненты уравнения.

Подавление спектра фона

Если фон $h(x)$ после препроцессинга достаточно однороден на обрабатываемых документах, возможно простое вычисление усредненного спектра $\mathcal{F} h(x)$ на изображениях документов, на которых отсутствует искомый периодический паттерн, с последующим его вычитанием из $\mathcal{F} I(x)$ .

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

Ранее мы уже упоминали тот факт, что ДПФ позиции (частоты) без пиков не содержат полезной информации касательно периодических паттернов, поскольку они представляют фон. Предположив, что $\mathcal{F} h(x)$ является гладким, мы можем интерполировать его вклад в каждый пик $\mathcal{F} I(x, y)$ , основываясь на значениях в соседних с пиком позициях. Усредненное значение $\overline{\mathcal{F} I(x', y')}$ по $(x, y)$ по ближайшим соседям пика $\{\mathcal{F} I(x', y')\}$ в 3x3 окне является приемлемой оценкой $\mathcal{F} h(x, y)$ для вычитания из $\mathcal{F} I(x, y)$ , чтобы вычистить фон:

$\mathcal{F} I(x, y) \leftarrow \mathcal{F} I(x, y) - \overline{\mathcal{F} I(x', y')}$

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

— ДПФ, вычитание спектра фона, обратное ДПФ ---->

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

Подавление спектра экземпляров паттерна

После удаления фонового спектра у нас осталось $\mathcal{F} f(x) \cdot \mathcal{F} c(x)$ . При перемножении двух комплексных чисел, их фазы складываются. Тогда, для достижения фазового угла $\mathcal{F} c(i, j)$ у пика $(i, j)$ , соответствующий фазовый угол спектра единичного экземпляра периодического паттерна $\mathcal{F} f(i, j)$ должен быть вычтен.

Проблема состоит в том, что спектр периодического паттерна, как правило, неизвестен. Одним из возможных решений является экспериментальное вычисление фазы представленного образца паттерна и его последующее вычитание. В наших экспериментах мы использовали другой путь, предполагая, что фазовый вклад $\mathcal{F} f(i, j)$ постоянен, значит, к результирующему сдвигу $\phi$ добавляется еще один константный сдвиг. Эта сдвиговая константа может быть оценена экспериментально как систематическая ошибка на тестовом наборе данных.

Восстановление фазового сдвига

По окончании предобработки спектра мы имеем фазовый угол импульсного сигнала $c(x)$ , который предположительно содержит всю необходимую информацию про фазовый сдвиг ${\phi=(\phi_x, \phi_y)^T}$ .
Мы можем построить систему уравнений (каждое уравнение соответствует $(i, j)$ пику) по модулю $2\pi$ :

$\begin{cases} \dots \\ i\cdot\phi_x + j\cdot\phi_y = \phi_{i, j} \pmod{2\pi} \\ \dots \\ \end{cases}$

Или, в матричной форме:

$A\phi = b \pmod{2\pi}$

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

Эта система переопределена, т.к. она имеет $n$ уравнений (по числу рассматриваемых пиков) и только 2 переменные: $\phi_x$ и $\phi_y$ . Переопределенные системы уравнений могут быть приближенно решены методом наименьших квадратов (МНК) поиском решения, минимизирующего сумму квадратов невязок. Однако, эта система является системой по модулю $2\pi$ поэтому напрямую МНК не может быть применен, но мы можем вычислить начальное решение и скорректировать его последовательным решением системы.

Вычисление начального решения

Посмотрим на два уравнения для пиков под номерами $(2, 0)$ и $(0, 2)$ :

$\begin{cases} 2\cdot\phi_x + 0\cdot\phi_y = \phi_{2, 0} \pmod{2\pi} \\ 0\cdot\phi_x + 2\cdot\phi_y = \phi_{0, 2} \pmod{2\pi} \end{cases}$

Эта система имеет 4 допустимых решения: $(\frac{\phi_{2, 0}}{2},\frac{\phi_{0, 2}}{2})$ , $(\frac{\phi_{2, 0}}{2}+\pi,\frac{\phi_{0, 2}}{2})$ , $(\frac{\phi_{2, 0}}{2},\frac{\phi_{0, 2}}{2}+\pi)$ и $(\frac{\phi_{2, 0}}{2}+\pi,\frac{\phi_{0, 2}}{2}+\pi)$ . Из-за подобной шахматной доске структуры пиковых паттернов в нашем случае, а также, поскольку $2\pi$ представляет собой сдвиг на единичный период, первое с четвертым решения идентичны, как и второе с третьим. Остается два потенциальных решения: $\phi^*_1 = (\frac{\phi_{2, 0}}{2},\frac{\phi_{0, 2}}{2})^T$ и $\phi^*_2 = (\frac{\phi_{2, 0}}{2}+\pi,\frac{\phi_{0, 2}}{2})^T$ .

Для выбора правильного решения мы можем добавить к системе два оставшихся уравнения для пиков $(1, 1)$ и $(1, -1)$ , вновь сделав систему переопределенной. Тогда, значение невязки $\delta_k$ вычисляется для $k$ -го решения $\phi^*_k$ с учетом всех $n=4$ уравнений:

$\delta_k = \frac{1}{n}\sum_{i, j}{\left(\begin{pmatrix}i & j\end{pmatrix} \cdot\phi^*_k - \phi_{i, j}\right)^2} = \frac{1}{n}|A\phi^*_k-b|^2$

Отметим, что промежуточные вычисления, затрагивающие фазовые углы (вычисление разностей), выполняются в $[-\pi; \pi)$ .

Наконец, решение $\phi^*_k$ , имеющее наименьшее значение $\delta_k$ выбирается в качестве $\phi^*$ , поскольку другое решение будет иметь намного большее значения невязки. Большое значение $\delta_k$ для $\phi^*_k$ может означать ложное обнаружение пика.

Корректировка решения

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

На данном этапе выбранное решение $\phi^*$ является все еще верным, но может быть уточнено с использованием фазовой информации в других пиках, а не только по двум первым. Вычтем $A\phi^*$ (используя $n=4$ уравнения) из обоих частей системы уравнений, сдвинув таким образом пространство решений по $\phi^*$ и получив следующую переопределенную систему уравнений для корректирующего решения $\theta$ :

$\label{eq:correction_phase} A\theta = b - A\phi^*$

Предполагая, что в первом приближении решения мы ошиблись не больше, чем на $\pi$ , мы можем не брать систему по модулю $2\pi$ , т.к. после сдвига системы каждое уравнение будет внутри $2\pi$ , что означает, что мы может приближенно решить систему, используя метод наименьших квадратов. После того, как решение $\theta^*$ найдено, оно должно быть добавлено к ранее найденному начальному решению $\phi^*$ в качестве корректирующего значения.

До сих пор мы рассматривали уравнения для первых 4 пиков $(i, j)$ имеющих $(|i| + |j|)$ сумму равную 2 (и $i \ge 0$ из-за симметричности ДПФ), но ведь существуют другие пики с суммами, равными 4, 6 и так далее. Причина, почему они не были добавлены ранее, состоит в том, что при увеличении $(|i| + |j|)$ увеличивается и количество подходящих решений системы, и тем ближе они становятся друг к другу по модулю $2\pi$ .

Для использования информации о фазовом сдвиге, содержащейся в остальных пиках, мы можем повторить вышеописанный процесс корректировки начального решения, заменив $\phi^*$ скорректированным решением, полученным для суммы, равной 4 и используя все уравнения, имеющие сумму, равную 6 и так далее, до достижения требуемой точности. Предполагая, что с увеличением итерации ошибка уменьшается, каждое уравнение будет находиться в пределах $2\pi$ , что позволяет применять МНК для решения системы.

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

Теперь, имея фазовый сдвиг $\phi = (\phi_x, \phi_y)$ , мы можем легко преобразовать его обратно в пиксельный сдвиг $s = (s_x, s_y)$ . Зная период и размер паттернов, мы можем восстановить положение каждого паттерна решетки. Размер и положение вырезанного региона, который мы использовали в процессе обработки, также известны, поэтому мы можем получить позиции паттернов на исходном изображении документа.

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

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

Экспериментальные результаты

Мы использовали набор данных из 484 изображений отсканированных российских паспортов, имеющих голографическое заполнение. Для каждого изображения в наборе мы подготовили истиное значение пиксельного сдвига его периодического паттерна. Таблица ниже содержит экспериментальные результаты для этого набора данных с усредненным значением невязки смещения как меры точности.
Ошибка задана в процентах от стороны единичного паттерна. Предобработка состояла из сжатия к размеру 56x58 и морфологической операции замыкания; при решении системы для получения фазового сдвига были рассмотрены $n=4$ уравнений пиков.

Подавление фона	Корректировка с МНК	x ошибка	y ошибка	Общая ошибка
Отсутствует	Отсутствует	2.13	6.40	6.75
Присутствует	Отсутствует	2.09	6.04	6.40
Отсутствует	Присутствует	2.19	5.05	5.50
Присутствует	Присутствует	2.20	4.77	5.25

Следующий рисунок показывает распределение $x$ и $y$ ошибок для худшего (слева) и лучшего (справа) метода. Черные ячейки представляют ошибку по $x$ , а белые – по $y$ .

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

Заключение

Мы предложили метод поиска периодических шаблонов на изображениях документов, который использует дискретное преобразование Фурье и показал среднюю ошибку поиска в $6\%$ (от стороны периодического элемента) на наборе из 484 изображений.
О подробностях применения нами этого метода мы расскажем в одной из следующих статей.

Tags:

Hubs: