Содержание к диссертации
Введение
1 Аналитический обзор существующих методов защиты 27
1.1 Классификация 27
1.2 Традиционные методы 28
1.2.1 Методы, используемые на стадии разработке макета документа 28
1.2.2 Методы защиты на базе специального оборудования и материалов 29
1.2.3 Недостатки традиционных методов 31
1.3 Алоритмическая защита 32
1.3.1 Видимая маркировка 32
1.3.2 Цифровые водяные знаки 35
1.3.3 Недостатки существующих алгоритмических методов . 41
1.4 Выводы: задачи, подлежащие решению 42
2 Анализ математических методов обработки изображений 43
2.1 Изображение как сигнал 43
2.2 Гистрограмма интенсивности 44
2.3 Базисные функции 46
2.4 Спектральное представление 47
2.5 Свертка и корреляция 50
2.6 Корреляция в широком смысле 51
2.7 Передаточная функция в линейных системах 52
2.8 Деконволюция 55
2.9 Дифференцирование и детектирование границ 60
2.10 Теорема Котельникова и sine-интерполяция 62
2.11 Выводы 65
3 Разработка метода алгоритмической защиты 69
3.1 Введение 69
3.2 Предлагаемые принципы защиты от копирования 71
3.2.1 Преобразование изображение в процессе копирования . 71
3.2.2 Предлагаемый метод защиты: характеристика, обучение и тесты 73
3.2.3 Оценка вероятности гипотез 79
3.2.4 Вычисление контрольных характеристик 82
3.3 Определение местонахождения ЦП 87
3.3.1 Грубое позиционирование 87
3.3.2 Прецизионное позиционирование 94
3.3.3 Определение угла наклона 95
3.4 Круговой штрихкод 96
3.5 Коррекция ошибок данных ЦП 99
3.6 Шифрование данных ЦП 99
3.7 Выводы 100
4 Разработка гибридного метода непараметрической классификации 102
4.1 Вступление 102
4.2 Постановка задачи 103
4.3 Параметрические и непараметрические классификаторы 106
4.4 Два метода непараметрической классификации 107
4.4.1 Мера сходства/различия 107
4.4.2 Окно Парзена 108
4.4.3 к ближайших соседей (&-NN) 109
4.5 Нечёткость обучающего набора НО
4.6 Гибридный метод 111
4.7 Выводы 115
5 Разработка метода быстрого интегрального преобразования 117
5.1 Введение 117
5.2 Разностный метод 118
5.3 Сравнение с известными методами 121
5.4 Приложение к обработке изображения 123
5.5 Практическое применение 125
5.6 Выводы 127
6 Разработка генератора фрактала 128
6.1 Требования 128
6.2 Обзор существующих фракталов 129
6.2.1 Геометрические фракталы 130
6.2.2 Алгебраические фракталы 130
6.2.3 Симметричные розетки 134
6.2.4 Детерминированные и
стохастические фракталы 135
6.2.5 Необходимость в разработке нового фрактала 136
6.3 Фрактал на базе плоской кристаллической решётки 137
6.3.1 7-фракталы 141
6.3.2 13-фракталы 141
6.3.3 19-фракталы 142
6.4 Раскраска фрактала 142
6.5 Возмущающие функции 144
6.6 Выводы 147
7 Результаты испытаний 150
7.1 Описание программного продукта 150
7.2 Испытания 152
7.2.1 Изготовление поддельной копии 153
7.2.2 Основные проблемы изготовления копии 154
7.2.3 Влияние на характеристики 154
7.2.4 Использованное оборудование 154
7.2.5 Результаты испытаний 155
7.3 Оценка разработанной технологии 156
7.3.1 Преимущества 156
7.3.2 Недостатки 157
7.3.3 Дальнейшая разработка 157
7.3.4 Область применения 158
Выводы 169
Литература
- Методы, используемые на стадии разработке макета документа
- Передаточная функция в линейных системах
- Преобразование изображение в процессе копирования .
- Параметрические и непараметрические классификаторы
Введение к работе
Общая характеристика работы
Актуальность проблемы Документооборот, бумажный и электронный, является неотъемлемой частью человеческой деятельности. Не смотря на то, что в последние десятилетия электронный документооборот существенно повысил эффективность экономической деятельности, «бумажные технологии» остаются на сегодняшний день важным средством обмена информацией (документы, книги, этикетки), взаиморасчётов (наличные деньги, чеки, ценные бумаги, билеты, акцизные марки) и идентификации личности (паспорта, пропуска, удостоверения). Однако, случаи незаконного копирования пока имеют место достаточно часто. Этому способствует то, что средства копирования становятся всё качественнее и доступнее по цене. В первую очередь, здесь следует выделить цифровые студии на базе профессионального сканера, компьютера с графическим пакетами и цифрового устройства вывода.
Технологии защиты и проверки печатной продукции развиваются в направлении удорожания печатного процесса, использования уникального оборудования и специальных расходных материалов. Это делает защиту менее доступной широкому кругу потребителей: малого и среднего бизнеса, а так же индивидуальных пользователям. Здесь по-прежнему используется традиционные средства информационной безопасности — подписи и чернильные печати. Для указанного круга пользователей являются актуальным следующие проблемы:
Защита от копирования ставит перед собой задачу эффективного распознавания оригинальных документов и уличения подделок, т. е. несанкционированных копий. Документу придаются такие свойства, которые утрачиваются при воспроизведении на копирующим оборудовании. Важно, чтобы эти свойства не менялись в процессе использования документа и не могли повторяться злоумышленниками.
Контроль целостности подразумевает установление факта несанкционированного изменения содержания (например, изменение номинальный стоимости ценной бумаги, фамилии, имени).
Машинная идентификация, как правило, реализуется с помощью специальной маркировки, содержащей код. Примером является широко распространённый штрихкод, используемый для маркировки розничных товаров.
Аутентификация есть подтверждение факта того, что отправитель (автор документа), действительно является тем лицом, за кого он себя выдает.
Эти задачи могут быть решены при помощи так называемых алгоритмических методов защиты документов. В основе алгоритмических методов лежат вычислительные алгоритмы обработки изображения и криптографии. Эти методы противопоставляются традиционным методам защиты, которые опираются на неповторимость процесса печати.
Объектом исследования являются алгоритмические методы защиты от копирования и методы распознавания защитной маркировки на печатных документах.
Целями диссертации являются:
создание теоретической базы алгоритмической защиты документов;
разработка технологии алгоритмической защиты документов.
Методы исследования В работе применены методы цифровой обработки сигналов, теория вероятности и математическая статистика, теория детерминированного хаоса, фрактальная геометрия, криптография и теория кодирования.
Задачи Для достижения указанных целей в диссертации выполнены:
анализ существующих методов защиты;
выбор математического аппарата для описания преобразования изображения в процессе печати, сканирования и несанкционированного копирования злоумышленником;
выявление статистических различий между цифровыми изображениями оригинального и скопированного документов;
моделирование «прохождения» изображения через систему принтер-сканер;
разработка генератора псевдо-случайного фрактального изображения на базе итерационных уравнений;
разработка и тестирование алгоритмов:
генерации фракталов;
кодирования и декодирования данных (битового массива) в изображении;
вычисления статистических параметров изображения, чувствительных к копированию;
принятия решения о достоверности документа на основе рассчитанных параметров; оценка разброса значений параметров;
разработка макета программного обеспечения, позволяющего произвести адаптацию метода;
экспериментальная проверка разработанного метода.
Научную новизну составляют:
математическая модель преобразования изображения в системе «принтер-сканер»;
теоретическое обоснование метода защиты;
фрактал на базе кластера плоской кристаллической решетки;
схема кодирования информации в виде кругового штрихкода;
метод дискретного интегрального преобразования изображения;
метод непараметрической нечёткой классификации, имеющий приложение в задачах распознавания образов.
Практическую ценность представляют
технология защиты печатных документов путём нанесения и сканирования цветной маркировки;
метод установления факта подделки для проведения экспертиз;
алгоритм поиска ЦП на документе и прецизионного вычисления её координат на отсканированном изображении.
алгоритм обнаружения точного местонахождения цветной маркировки на документе;
алгоритм быстрого интегрального преобразования изображения;
алгоритм непараметрической нечёткой классификации.
Реализация результатов работы Разработанные методы, модели, алгоритмы, программное обеспечение использованы ООО «Диахром» (РФ) и «ДТЛ» (Великобритания) при разработке комплекса защиты печатных документов. По теме диссертации были сделаны доклады и опубликованы тезисы на конференциях (в том числе международной) [63, 11], подана заявка на патент [58], опубликованы статьи [13, 12]. В работе использованы некоторые идеи и результаты, опубликованные в английской диссертации [62].
Структура диссертации Диссертация состоит из введения, семи глав, описания алгоритмов, выводов и списка литературы. Объем диссертации составляет 175 страниц и 50 рисунков.
Краткое содержание Введение
Во введении обоснована актуальность диссертационной работы; сформулированы цель и задачи, исследовательский метод, научная новизна, практическая ценность; представлено краткое содержание диссертации.
Методы, используемые на стадии разработке макета документа
Эффект объёмного изображения строится на особенностях человеческого зрительного восприятия. Если изображения скомпоновать с помощью математических программ и точно его напечатать, можно достигнуть специального эффекта. При продолжительном взгляде на картинку наблюдатель начинает замечать скрытый рисунок или текст.
Эффект скрытого изображения заключается в том, что если повернуть лист бумаги под определённым углом, то в нём появляются новые элементы. Современные программы могут делать два линейных растра, замаскированных пер пендикулярно один в другом. В этом случае скрытая картинка проявляется при взгляде на рисунок под очень маленьким углом.
Нестандартный текст
На стадии разработки макета в картинку вводят мелкие «дефекты» — нестандартный шрифт, неровные по высоте или ширине «прыгающие» буквы, линии, меняющие толщину и т. п. При большом объёме текста есть вероятность, что злоумышленники не заметят этих недостатков или не смогут легко их повторить. Этот метод работает с бумагами, которые должен проверять лишь ограниченный круг должностных лиц. В эту категорию входят удостоверения, банковские документы и т. п.
Микротекст
Микротекст — строки символов воспринимаемые человеческим глазом в виде сплошной непрерывной линии, но читаемый с помощью лупы. Такие элементы защищают продукцию и повышают сложность её воспроизведения на традиционном полиграфическом оборудовании. Микротекстовые включения присутствуют на большинстве ценных и полуценных бумагах.
Методы защиты на базе специального оборудования и материалов
Орловская печать
В ряде защитных технологий особое место занимает способ печати, изобретённый И. И. Орловым в 1891 году. Суть способа заключается в том, что печать многокрасочного изображения производится с одной печатной формы с использованием промежуточных красочных шаблонов, имеющих рисунок для каждого цвета оригинала. Каждый красочный рисунок шаблона передаёт своё красочное изображение на сводный вал и затем на сборную форму, имеющую рисунок всего оригинала. Это позволяет за один прогон листа через печатную машину переносить на оттиск без каких-либо смещений или разрывов многокрасочный рисунок. Наиболее характерно точность совпадения красок проявляется на стыках линий, переходящих из одного цвета в другой.
Эксклюзивное право на применение Орловской печати в России принадлежит объединению «Гознак» [9].
Специальная бумага
В бумаге для ценных документов часто используют явные и/или скрытые защитные элементы, в частности: общий и локальный многотоновый водяной знак; филигранный водяной знак; металлизированная нить; защитная нить с микротекстом и свечением в ультрафиолетовом излучении; различные виды защитных волокон; индивидуальные композиции по видам волокнистых полуфабрикатов; конфетти и другие защитные включения при хаотичном и регулярном распределении их в бумаге; химические виды защиты. Специальные краски
Специальные краски широко применяются для защиты документов и распознаются как и человеком так и оборудованием. Защитные краски могут обладать следующими свойствами: Изменение под воздействием химических средств, при попытке удаления или исправления уже имеющихся надписей; Эффект люминесценции в ультрафиолетовых и инфракрасных лучах; Магнитизм; Другие оптико-электронные свойства, распознаваемые специальными приборами. Голограммы
Голограммы стали впервые применяться в качестве защитных элементов в начале 1980-х годов и теперь часто используются в производстве банкнот, документов и пластиковых карт. Голограммы часто комбинируются с другими защитными технологиями. Различают голограммы холодного и горячего тиснения.
Передаточная функция в линейных системах
Системой в смысле английского термина imaging system будем называть произвольный преобразователь изображения. Физическими примерами систем являются электрическая цепь, оптическая система линз, а так же их комбинация — электронно-оптический прибор.
В общем случае система может быть задана оператором L, который воздействует на исходное изображение / и возвращает преобразованное изображение s: s(x,y) = L[f(x,y)].
Математически, система есть отображание множества входных функций (изображений) во множество выходных функций. Свойство линейности системы может быть выражено как L[af(x, у) + Ьд(х, у)] = aL[f(x, у)] + bL[g(x, у)] для всех функций /, д и всех констант а, Ь. В линейной системе можно разделить входную функцию на элементарные составляющие функции, передать эти функции через систему и получить преобразованные элементарные функции, которые в сумме дадут преобразованную исходную функцию.
Входное изображение можно записать как линейную комбинацию дельта-функций (импульсов), сдвигаемых по осям координат, 00 00 f(x, у) = J j Да/, у Щх - х Щу - у ) dx dy . —ОО -00 Применяя оператор системы, имеем ОО ОО s(x,y) = L[f(x,y)} = J J fix y YL x-x iy-y dx dy . Ответ системы в точке (х,у) на возмущение от импульса в точке (х ,у ) есть функция р(х,у;х ,у ) = L[S(x - х )5(у - у )].
Функцию р будем называть реакцией на импульсное возмущение (IRF от англ. Impulse Response Function). В оптике, функцияр так же называется функцией рассеяния точки (PSF от англ. Point Spread Function). В линейной оптической системе, 00 00 Ф,У)= / / f(x ,y )p(x,y;x ,y )dx dy . —00 —00 Приведем примеры линейных систем [22, 6]: 1. Дифракция Фраунгофера , . А і exp(ikz) (.Ах"1 + у2)\ р{х,у-х,у) = - к-— -explikK Jexp 2. Дифракция Френеля (хх +уу) Z Ф, у; , У ) = j p ехр ([( - х )г + (у- j/ )2])
Если функция реакция системы на импульсное возмущение зависит только от разницы координат (х — х ) и (у — у ), а не отдельно от каждой координаты, то есть, р(х,у;х ,у ) = р{х -х1,у- у ), то оператор системы может быть просто записан в виде свертки 00 00 Ф, у)= f(x , у )р(х х ,у- у ) dx dy = /(g) р. -00 —00
Такая система является стационарной. В оптике, стационарные системы называется изопланатическими. Это свойство требует, чтобы функция рассеяния точки и абберации не зависили от угла зрения. Несмотря на это допущение, линейные и изоплапатические системы является хорошим приближением многих физических систем.
Теорема о свёртки позволяет описать линейную систему в частотной области: Ь\кх, ку) = г [кх, ку)-г\Кх) ку) где 00 00 Р(кх, ку) = / р(х, у) ехр[-2тгі(кхх + куу)] dx dy —00 —00
Образ Р в литературе называется передаточной функцией (transfer function). Применительно к предметной области диссертации, мы можем рассматривать следующую цепочку преобразований как единую систему: бумага f(x,y)- y Принтер У Сканер —у s(x,y), (2.2) где f(x, у) — оригинал-макет документа, s(x, у) — сосканированный документ. С некоторыми допущениями (в первую очередь, конечную разрешающую способность) мы можем описать прохождение сигнала (изображения) через систему (2.2) следующим уравнением s = fp + n, (2.3) где р — ядро свертки, п — аддитивный шум. Это фундаментальное уравнение позволяет моделировать преобразование изображения в системе принтер-сканер.
Преобразование изображение в процессе копирования .
Рассмотрим «жизненный цикл» оригинального (неподдельного) документа: бумага fm,n - Принтер Сканер - sm ni где /т п — оригинал-макет документа, sm n — отсканированный документ. Пусть оператор -РПр описывает преобразование принтера, и оператор Рск — преобразование сканера. Тогда sm,n = - CKl-f:np[/m,nJJ — ск- пр/т,П) где, согласно выбранной модели в разделе 2.7, Рпрfm,n = Pm,n S /m,n + nm,ni (3-1) Рскїт,п = Vm,n fm,n + nm,n- W-2) Композицию преобразований принтера и сканера можно представить как АрАк/m.n = Р „ 8 О «n S /m,n + п) + % = = {Рт,п „) /т,я + fen Р,п + П«я) = = Pm,n fm,n +
В эту модель можно добавить функцию q(fm,n), отражающую нелинейность принтера-сканера по передаче интенсивности пиксела: np CKjm,n = Q\Jm,n)Pm,n }т,п "Т nm,n- І"-"/
Вид функции q(fm,n) обуславливается, во-первых, дискретизацией интенсивности (конечное число разрядов АЦП, ограниченное число тонов принтера) и, во-вторых, сложностью передачи очень светлых и очень темных областей. На рис. 3.4 (тонкая линия) построена эмпирическая функция д(/Ш)П).
Такая модель учитывает распространённые физические явления: расфокусировка (размывание изображение); ограниченная разрешающая способность принтера и сканера; нелинейная передаточная характеристика по интенсивности; шум фотоэлементов сканера (CCD); дефекты бумаги и чернил (отчасти); но не учитывает следующие искажения: цветовые искажения, в первую очередь, диффузионная передача полуто нов в принтере, преобразование цвета RGB в неидеальные чернила CMYK, и обратно; геометрические искажения (непропорциональное масштабирование), возникающие из-за неидеальной работы механизмов принтера и сканера.
Главным допущением разработанной технологии является, то что, считается, злоумышленник не имеет доступа к оригинал-макету ЦП, то есть, к её исходной цифровой версии. В этом случае, копию документа можно сделать только путем сканирования отпечатанного образца, и «жизненный цикл» поддельного документа имеет вид /, 771 ,П Принтер автора бумага Сканер злоум. цифр, изобр. Принтер злоум. бумага Сканер автора - S тп,п Пусть автор и злоумышленник используют одно и тоже оборудование (в противном случае, искажение документа будет ещё более существенным). Обозначим Jm,n = Jm,ni Л _ р р fO Jm,n — гск прУгп)П) Jm,n =ск- np/jn,n = ск-Гпр-г ск- пр/т,п Тогда задача распознавания сводится к обнаружению разницы между первыми отпечатком f n и его копией /Д(Я.
Точный расчёт преобразования Рск-Рпр на практике представляет собой нереша-емую задачу ввиду многообразия оборудования и нелинейности их свойств, в том числе тех, которые не учитываются моделью (3.3). Поэтому установить разницу между fmn11 fmn удаётся только эмпирическими методами. Суть эмпирического подхода сводятся к численной оценке преобразования / п = РскРПр/т,п путём предварительного сканирования заведомо оригинального отпечатка. Далее необходимо сравнить этот контрольный образец с отсканированным документом, подлежащей проверке. Здесь можно рассмотреть два подхода: 1. прямое попиксельное сравнение двух растровых изображений; 2. сравнение статистических параметров после предварительного преобразования изображений.
Подход 1 в реальной ситуации применить сложно, так как невозможно добиться полного совмещения пикселов двух изображений. В процессе печати и сканирования изображение подвергается неравномерным геометрическим преобразованиям. Нетривальной задачей является определение точных координат и угла ЦП (раздел 3.3). Другим неприемлемым недостатком этого подхода является необходимость обучать систему каждый раз, когда меняется пользовательская информация ЦП.
Параметрические и непараметрические классификаторы
Статистические классификаторы можно разделить на две группы с точки зрения способа оценки вероятностей класса:
В параметрических методах, необходима предварительная информация о форме функции плотности вероятности pj, и в процессе обучения вычисляется оценка параметров этой функции. Например, часто используются функция нормального распределения Pj=Pj{x,fi,a) = —-=е 2 , ау/27г где {І и а — параметры, получаемые из обучающего набора Т. Этот подход не эффективен, когда нет предварительной информации о форме функции плотности распределения, или она имеет сложный вид (например, несколько локальных максимумов). Непараметрические методы позволяют получить оценку вероятности напрямую из обучающего набора Т: Pj=Pj(x,T).
Непараметрические методы могут работать со сложными многомерными функциями распределения. Очевидно, такой подход более универсальный, но ресурсоёмкий. Далее речь пойдёт о непараметрических классификаторах.
В литературе [31] выделяют два эффективных метода непараметрической классификации — окно Парзена (Parzen window) и &-NN (к Nearest Neighbours — А ближайших соседа). Ряд альтернативных подходов [44] обеспечивают высокое качество распознавания, но два упомянутых метода, взятые за основу в настоящей работе, привлекательны своей простотой и универсальностью. В их основе лежит мера сходства/различия между образами.
Пусть необходимо сравнить два образа с признаками х и у. Распространённой мерой является евклидово расстояние заданное в D-мерном пространстве признаков. При расчёте меры важно учитывать масштаб признаков, т. к. признаки с большим диапазоном значений подавляют остальных. Для этого признаки могут быть нормализированы: где нормализирующие коэффициенты w = (w\,... ,wj)) определяются в процессе обучения. В w может быть так же учтён вес признака.
Евклидова мера работает с пространствами небольшой размерности (D 30). При больших D, расстояние между двумя случайными точками стремиться к одной величине, а все точки находятся на поверхности гиперсферы. В литературе известны так же альтернативные меры, такие как /„-норма, супремум-норма и расстояние Махаланобиса, однако в задачах распознавания они используются реже.
Пусть дана выборка {у„} из N точек. Тогда оценка вероятности в точке х есть M-W.Z { ) (4Л) n=l N где #() — «окно» или ядро — гладкая сглаживающая функция; и а — относительный размер окна. В пределе N — сю и а — 0, функция р(х) приближается к действительной плотности распределения р(х) [57]. Окном часто является гауссовская функция, тогда
Основной проблемой данного подхода является выбор размера окна а. В случае, когда точки уп неравномерно распределены в пространстве признаков, а должна адаптивно выбираться исходя из их локальной плотности. В статье [47] предложен метод адаптивной подстройки размера окна на основе оценки дисперсии в точки х. Так же следует так же отметить, что выражение (4.1) описывает идеальный случай и не учитывает возможные ошибки признаков х и у„.
Вычисление суммы (4.1) ресурсоёмко в случае большой выборки. Ряд методов [43, 45] был предложено для решения этой проблемы, в частности на базе оптимального сокращённого набора из {уп} [39].
Пусть дана выборка {уп} из N точек. Выберем число соседних точек к N, например, к = y/N [31]. Тогда оценка ПР в точке х есть (x) = NV Ty где Vk(x) — объем наименьшей гиперсферы, которая содержит к точек, ближайших к х. Другими словами, для того чтобы отнести точку х к тому или иному классу, необходимо зафиксировать к и сравнить размеры (радиусы) окрестностей Vfc(x) покрывающие к точек из {уп}, ближайших к х. Тогда класс с наименьшим Vfc(x) будет наиболее вероятным.
Недостатком метода &-NN является то, что в нём не учитывается расстояния между рассматриваемой точке х и точками выборки {уп} внутри окрестности Vfc(x). Очевидно, ближайшие точки должны иметь большей вес, чем остальные. Другой проблемой метода является выбор оптимального к в случае неоднородности выборок по каждому классу.
