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

Иллюстрации

Показать все

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

Реферат

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

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

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

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

Одно из решений проблемы защиты напечатанных документов описано в выложенной патентной заявке США 20090125723 [1], где описывается метод кодирования цифровых данных на поверхности документа посредством использования инфракрасных чернил. Кодированная поверхность состоит из плотно размещенных, примыкающих друг к другу тегов. Кодирование поверхности осуществляется таким образом, чтобы поле захвата информации было достаточно большим для гарантии успешного считывания всего тега и идентификации области, содержащей тег. Данный способ обеспечивает успешное считывание информации с поверхности документа с помощью специального считывающего устройства в форме ручки. К недостаткам метода, описываемого в заявке, следует отнести необходимость в специальных устройствах печати и считывания информации.

В выложенной патентной заявке США 20080292129 [2] предлагается способ нанесения дополнительной информации в печатный документ за счет внедрения специальных информационных меток в предопределенные позиции. Метки, состоящие из набора точек, ставятся на свободные области документа. После этого изображение преобразовывается для печати и печатается.

Наиболее близким к заявляемому изобретению является решение, описанное в выложенной патентной заявке США 20090021795 [3]. В ней предложен способ внедрения идентификационных меток в псевдослучайные позиции документа, а также система для реализации предложенного способа. Метки представляют собой кластер из черных или белых точек для белых или черных областей документа соответственно. Предполагается, что созданные подобным способом метки будут устойчивы к изменению контраста изображения и процессу растеризации, выполняемому в результате передачи документа по факсу. Недостатком такого способа является высокая вероятность утраты содержащейся в метках информации при незначительных повреждениях документа.

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

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

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

- преобразуют (растрируют) исходный документ в растровое изображение;

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

- определяют на растрированном изображении все возможные позиции для встраивания конфигураций точек;

- встраивают конфигурации точек на обнаруженные позиции;

- печатают растрированное изображение со встроенными данными.

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

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

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

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

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

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

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

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

Заявляемый способ извлечения встроенной скрытой информации включает в себя следующие операции:

- сканируют печатный документ;

- бинаризуют сканированное изображение;

- исключают из рассмотрения близкорасположенные связанные области;

- выявляют встроенные конфигурации точек;

- вычисляют распределение встречаемости единичных значений битов;

- восстанавливают порции данных;

- извлекают скрытое сообщение.

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

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

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

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

- модуль встраивания данных, выполненный с возможностью выявления на входном растрированном изображении всех возможных позиций, пригодных для встраивания конфигураций точек, и встраивания последовательности конфигураций точек с их многократным повторением на выявленные позиции растрового изображения, причем выход модуля встраивания данных соединен с входом модуля вывода;

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

Заявляемая система, предназначенная для извлечения скрытых данных из печатного документа, состоит из следующих модулей:

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

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

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

- модуль извлечения скрытых данных, выполненный с возможностью анализа входящих данных о распределении встречаемости единичных значений битов для каждой порции данных и извлечения скрытых данных, причем выход модуля извлечения скрытых данных связан с входом модуля вывода;

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

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

Фиг.1. Системы встраивания и извлечения скрытых цифровых данных в/из печатного документа;

Фиг.2. Блок-схема этапов способа встраивания скрытых данных в печатаемый документ;

Фиг.3. Представление служебных меток;

Фиг.4. Пример порции данных и схемы компоновки данных в конфигурации точек;

Фиг.5. Пример размещения конфигурации точек;

Фиг.6. Блок-схема этапов поиска позиции для встраивания конфигурации точек;

Фиг.7. Примеры конфигураций точек (размеры встраиваемых точек увеличены в четыре раза для демонстрационных целей);

Фиг.8. Блок-схема этапов способа извлечения скрытых данных из напечатанного документа;

Фиг.9. Блок-схема этапов распознавания служебных меток;

Фиг.10. Блок-схема этапов обнаружения достоверных конфигураций точек;

Фиг.11. Примеры распознавания конфигураций точек;

Фиг.12. Примеры извлечения информации из конфигураций меток.

Система для реализации способа встраивания скрытой цифровой информации в печатаемый документ показана на Фиг.1.1. Модуль 102 формирования изображения предназначен для преобразования входного документа в форму растрированного бинарного изображения. Для этого может быть использовано любое подходящее для этой цели устройство, как, например, сканер, цифровая фотокамера, процессор растровых изображений (RIP) и т.п. Бинарные изображения для каждого цветового канала являются естественными для печатающих электрофотографических и струйных устройств, поэтому процессор растровых изображений предпочтителен для реализации указанного модуля в заявленном изобретении. Растрированное изображение передается на вход модуля 103 встраивания данных. Генератор 101 последовательности конфигураций точек разделяет входное информационное сообщение, предназначенное для встраивания в печатаемый документ, на порции данных и подготавливает последовательность изображений конфигураций точек в соответствии с предопределенным правилом. Каждая конфигурация точек в этой последовательности кодирует одну порцию данных. Последовательность конфигураций точек передается в модуль 103 встраивания данных. Модуль 103 выявляет позиции для встраивания конфигураций меток во входное бинарное изображение. Конфигурации точек встраиваются из подготовленной последовательности в циклическом порядке с повторением одних и тех же конфигураций на разных местах документа. Бинарное изображение со встроенной информацией передается далее в модуль 104 вывода для формирования печатного документа. Для этой цели может быть использован принтер, плоттер или другие подобные печатающие устройства.

Система для реализации способа извлечения цифровой информации из печатного документа показана на Фиг.1.2. Модуль 105 захвата изображения выполнен с возможностью получения цифрового изображения входного печатного документа. В качестве модуля захвата изображения может использоваться любое устройство, позволяющее получить цифровое отображение бумажного оригинала напечатанного документа, например сканер, цифровая фотокамера и т.п. Предпочтительным вариантом для реализации указанного модуля заявленного изобретения является планшетный сканер. Выходное цифровое изображение из модуля 105 передается в модуль 107 обнаружения конфигураций точек для обнаружения скрытой в документе информации. Результат извлечения данных из каждой обнаруженной конфигурации точек, кодирующей определенную порцию данных, передается в модуль 106 вычисления распределения встречаемости единичных значений битов. Каждый элемент распределения описывает количество единичных значений соответствующего бита в последовательности извлекаемой скрытой информации. В данном случае вместо «четких» значений 1 или 0 для каждого бита формируется вероятность того, что бит равен единице. Распределение встречаемости единичных значений битов в извлекаемом сообщении и количества обнаруженных конфигураций точек передаются в модуль 108 извлечения скрытых данных. Извлеченная скрытая информация передается в модуль 109 вывода. В качестве модуля вывода может использоваться любое устройство, пригодное для визуализации извлеченных данных пользователю, например дисплей, принтер и т.п., или система управления безопасностью, применяемая для контроля за обращением печатных документов. Все перечисленные блоки и модули могут быть выполнены в виде системы на кристалле (SoC), или в виде программируемой логической матрицы (FPGA), или в виде специализированной интегральной схемы (ASIC). Работа модулей ясна из их описания и описания соответствующего способа.

Фиг.2 демонстрирует обобщенные этапы заявляемого способа встраивания скрытых данных в печатаемый документ. На шаге 201 получают исходный PDL документ с последующей растеризацией документа в бинарное изображение на шаге 202. В данном случае PDL (Page Description Language) - это язык описания страниц документа, сообщающий печатающему устройству, как должен выглядеть печатаемый документ, например, PostScript фирмы Adobe, HP-GL и PCL компании HP. На шаге 203 разделяют информацию, предназначенную для скрытого встраивания в печатаемый документ, на порции данных и генерируют последовательность конфигураций точек, кодирующих эти порции данных в соответствии с предопределенным правилом. Каждая порция данных снабжается собственных уникальным порядковым номером. На шаге 204 выявляют возможные позиции для внедрения подготовленных конфигураций точек, которые встраиваются на следующем шаге 205 в циклическом порядке, т.е. после встраивания последней конфигурации точек из последовательности повторно начинают с встраивания первой конфигурации. И так происходит до тех пор, пока все позиции на печатаемом документе, пригодные для встраивания порций данных, не будут заполнены. Такой подход позволяет достичь равномерного распределения одинаковых порций данных по изображению, что обеспечивает высокую устойчивость встраиваемого сообщения к модификациям и повреждениям напечатанного документа. На шаге 206 печатают модифицированное бинарное изображение.

В предпочтительном варианте изобретения каждая конфигурация точек включает в себя множество упорядоченных точек минимального печатаемого размера, обладающих четырехсторонней или двухсторонней симметрией. Такой подход обеспечивает модификацию печатаемого документа, практически незаметную для невооруженного глаза. Под минимальным печатаемым размером подразумевается такой размер точки, который позволяет гарантировать закрепление красящего вещества на листе бумаги как минимум для 70% встраиваемых точек. Минимальный размер точек зависит от характеристик печатающего устройства. Например, точки минимального размера при печати с разрешением 600 dpi могут состоять из одного, двух, трех или четырех аппаратных пикселей. Для черно-белой печати точки ставятся черного цвета, соответственно для цветной печати могут применяться используемые основные цвета. Например, для CMYK печати точки могут быть черного, желтого, голубого, пурпурного цветов. Использование желтого цвета при цветной печати является предпочтительным вариантом, так как желтые точки человек практически не может обнаружить невооруженным глазом.

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

В предпочтительном варианте заявляемого изобретения конфигурации точек включают в себя четыре служебные метки, показанные на Фиг.3. Служебные метки 301 располагаются по углам конфигурации 305 точек и состоят из трех точек (см. Фиг.3.1), формирующих вершины прямоугольных треугольников. Стороны треугольника имеют предопределенный размер, и их прямой угол 302 направлен в сторону центра конфигурации точек. Длина а горизонтальной стороны 304 треугольника всегда превышает длину b вертикальной стороны 303. Такое расположение служебных меток позволяет определить позицию тела конфигурации точек, даже если была обнаружена только одна служебная метка. В предпочтительном варианте заявляемого изобретения а≈0.5 мм (11 точек для разрешения печати 600 dpi), b≈0.4 мм (9 точек для разрешения печати 600 dpi). Например, на Фиг.3.2 представлены служебные метки, расположенные в заданных положениях относительно тела закодированной порции данных. Для специалиста в данной области очевидно, что возможны и иные варианты применения изобретения, позволяющие идентифицировать присутствие конфигурации точек на изображении. Например, служебные метки могут быть представлены в другом количестве или конфигурации или совсем отсутствовать, в этом случае скрытая информация может быть обнаружена за счет поиска в документе определенных геометрических структур, присущих используемым конфигурациям точек, кодирующих порции данных.

В предпочтительном варианте изобретения тело конфигурации точек образуется с помощью расположения точек минимального печатаемого размера на прямоугольной сетке с заданным шагом. Для повышения устойчивости встраиваемой информации каждый бит, кодируемый в конфигурации точек, повторяется четыре раза. Если значение бита равняется единице, то точка печатается, если значение равно нулю, то точка будет отсутствовать. Пример расположения кодируемой информации внутри тела конфигурации точек с четырехсторонней симметрией показан на Фиг.4. В предпочтительном варианте изобретения информация, кодируемая конфигурацией точек, состоит из 16 битов (Фиг.4.1), разделенных на две основные части: порядковый номер 401 ID с битом 402 четности и порция 403 данных встраиваемого сообщения bN, соответствующая порядковому номеру. В приведенном примере порядковый номер кодируется тремя битами ID0, ID1, ID2 с одним битом четности ID3. Порция данных определяется двенадцатью битами (b0-b11). Такой подход предусматривает последовательность, состоящую максимум из восьми порций данных с уникальными порядковыми номерами. Соответственно, максимальная емкость встраиваемой информации в документ не может превышать 12·8=96 битов. Для порядкового номера, описываемого четырьмя битами, максимальная емкость возрастает до 11·16=176 битов. Для специалиста в данной области очевидно, что возможны и иные варианты применения изобретения, позволяющие изменять максимальную емкость встраиваемой информации, компоновку используемых конфигураций точек и их количество.

На Фиг.4.2, 4.3 представлены варианты возможных компоновок тела конфигураций точек. Показанные схемы компоновки имеют четырехстороннюю (Фиг.4.2) и двустороннюю (Фиг.4.3) симметрию. Схема компоновки с четырехсторонней симметрией (Фиг.4.2) инвариантна к повороту на 90 градусов и, соответственно, при двусторонней симметрии (Фиг.4.3) данные инвариантны к повороту на 180 градусов.

На Фиг.5 показан шаблон конфигурации точек. В данном случае для наглядности изображение соответствует варианту конфигурации точек с единичными значениями всех битов. Шаг прямоугольной сетки m превышает соответствующий шаг для служебных меток. Такая разница предоставляет собой хороший отличительный признак для распознавания точек, относящихся к служебным меткам и телу конфигурации точек. В предпочтительном варианте изобретения m≈1 мм (25 аппаратных пикселей для разрешения печати 600 dpi). Служебные метки располагаются на расстоянии d от крайней точки тела конфигурации точек, d≈0.6 мм (15 аппаратных точек для 600 dpi разрешения печати).

Многократное повторение одинаковых порций данных на печатаемом документе обеспечивает сохранение встроенной скрытой информации, несмотря на частичную потерю встраиваемых точек. Соответственно частичная потеря внедренных в документ точек не влияет на успешное извлечение встроенного сообщения, и конфигурации точек могут незначительно перекрываться с небольшими объектами, такими как символы, линии, точки и т.п. Блок-схема основных этапов шага 204 для обнаружения возможных позиций на документе для встраивания конфигураций точек более детально показана на Фиг.6. На шаге 601 определяют позицию для конфигурации точек, при которой будут свободны участки изображения для встраивания четырех служебных меток. Если такая позиция была обнаружена, тогда рассматривается область изображения, ограниченная служебными метками. На шаге 602 обнаруживают печатаемые элементы изображения, находящиеся в анализируемой области, вычисляют их площадь. Текущая позиция считается пригодной для встраивания конфигурации точек 603, если площадь каждого из печатаемых элементов, находящихся на интересующем участке, и их общая площадь не превышают предопределенных значений.

В качестве примера на Фиг.7 приводятся фрагменты бинарного изображения со встроенными конфигурациями точек. Для наглядности встроенные точки увеличены в четыре раза. Фрагмент на Фиг.7.1 иллюстрирует конфигурацию точек в свободной области изображения. Фрагменты на Фиг.7.2, 7.3 описывают примеры встроенных конфигураций точек на частично занятых участках.

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

Следующие два шага предназначены для первичной классификации связанных областей на изображении как принадлежащих встроенным конфигурациям точек или нет. Для этого на шаге 803 выявляют на бинарном изображении связанные области, состоящие из примыкающих друг к другу точек. В процессе выполнения этого шага выбирают только маленькие связанные области (пятна), площадь которых меньше, чем предопределенное значение. В предпочтительном варианте изобретения максимально допустимый размер соответствует 0.25 кв. мм (9 пикселей при разрешения сканирования в 300 dpi), при этом считается, что область имеет компактную форму и расположена внутри квадрата со стороной 0.25 мм (3 пикселя при разрешении сканирования в 300 dpi). На шаге 804 отбрасывают из рассмотрения те связанные области, для которых в пределах предопределенного расстояния присутствуют другие объекты. В предпочтительном варианте изобретения это расстояние равняется 0,3 мм от края анализируемой области (4 пикселя при разрешении сканирования в 300 dpi).

Последующие этапы ориентированы на выбор и распознавание связанных областей, принадлежащих встроенным конфигурациям точек. На шаге 805 вычисляют центры масс связанных областей, выбранных на предыдущем этапе. Результирующие координаты служат в качестве оценок позиций внедренных точек на этапе печати. На шаге 806 распознают служебные метки. Далее за счет анализа этих меток на шаге 807 обнаруживают достоверные конфигурации точек, для которых вероятность правильного обнаружения достаточно высока. Выбор достоверных конфигураций точек осуществляется на основе учета требований, которым они должны соответствовать. Более подробно эти условия перечислены ниже. На шаге 808 оценивают ориентацию (наклон, скос) изображения посредством анализа ориентации обнаруженных достоверных конфигураций точек. На шаге 809 выявляют менее достоверные конфигурации точек, пропущенные на шаге 807, при этом используется информация об оценке ориентации сканированного документа. На шаге 810 вычисляют распределение встречаемости единичных значений битов для конфигураций точек с одинаковыми порядковыми номерами. Все обнаруженные к этому моменту конфигурации точек упорядочиваются в соответствии с их порядковыми номерами. В ходе этого шага восстанавливается регулярная прямоугольная сетка внутри каждой обнаруженной конфигурации точек, позволяющая определить позиции встроенных точек внутри этой конфигурации на печатном документе. Присутствие связанной области (пятна) на вычисленной позиции узла сетки трактуется как единичное значение связанного с этой позицией бита. Количество единичных значений бита, суммированное для всех порций данных, в которых он присутствует, определяет его вес и служит в дальнейшем для принятия решения о действительном значении этого бита в извлекаемой информации. Элементами распределения являются упомянутые выше веса, т.е. количества найденных единичных значений каждого бита в порции данных. На шаге 811 преобразуют веса битов непосредственно в их значения посредством расчета порога для каждой порции данных и сравнения с этим порогом. На шаге 812 получают целое извлеченное сообщение за счет выстраивания порций данных в цепочки в соответствии с их порядковыми номерами. Наиболее важные этапы описаны более подробно ниже.

Более подробно этап 806 обнаружения служебных меток иллюстрируется блок-схемой на Фиг.9. Группа близкорасположенных связанных областей может считаться служебной меткой (см. Фиг.3), если они соответствуют нескольким предопределенным условиям. На шаге 901 проверяют соответствие предопределенному диапазону значений евклидова расстояния между теми соседними областями на бинарном изображении, которые получены после фильтрации на шагах 803 и 804. В предпочтительном варианте изобретения расстояние между соседними областями должно быть менее 0,6 мм (7 пикселей при разрешении сканирования 300 dpi). На шаге 902 проверяют количество областей в выбранной группе. Если их количество не равняется двум или трем, то анализируемые области считаются шумом (шаг 905) и отбрасываются из рассмотрения. Если количество областей равняется трем (шаг 903), и один из углов между линиями, проведенными через центры анализируемых областей, с допустимой погрешностью близок к 90 градусам (шаг 904), то эта группа из трех областей маркируется как обнаруженная служебная метка (шаг 906). В противном случае если количество областей равняется двум, то пара областей маркируется как частично поврежденная служебная метка (шаг 907). В дальнейшем анализе частично поврежденная служебная метка будет рассматриваться как метка, не содержащая информации о местоположении относительно нее всей конфигурации точек.

Этап обнаружения достоверных конфигураций точек (шаг 807) более подробно представлен блок-схемой, показанной на Фиг.10. На шаге 1001 выбирают первую обнаруженную ранее и не участвующую в анализе служебную метку. На шаге 1002 вычисляют ориентацию текущей служебной метки и ее положение в конфигурации точек. Для этого используется различие между длинами сторон треугольника служебной метки (см. Фиг.3.1) и оценка угла между ними. В соответствии с предпочтительным вариантом изобретения положение служебной метки в конфигурации точек может быть следующим: верхнее левое, верхнее правое, нижнее левое и нижнее правое (см. Фиг.5). На шаге 1003 вычисляют ориентацию конфигурации точек на основе учета ориентации и положения выбранной служебной метки. Результатом является расчет предполагаемых позиций остальных служебных меток. На шаге 1004 обнаруживают остальные служебные метки в соответствии с оценкой их местоположения. Дальнейшие шаги в основном предназначаются для определения достоверности обнаруженной конфигурации точек посредством проверки ряда условий. Этот подход предназначен для уменьшения вероятности ложного обнаружения. На шаге 1005 проверяют количество обнаруженных служебных меток в конфигурации. Это количество должно быть больше одной. На шаге 1006 проверяют соответствие ориентации обнаруженных служебных меток предполагаемым. На шаге 1007 проверяют количество связанных областей внутри обнаруженной конфигурации точек, которое должно превышать предопределенное минимальное значение. В предпочтительном варианте изобретения минимальное количество областей внутри конфигурации меток равняется семи. На шаге 1008 проверяют совпадение центра масс областей внутри обнаруженной конфигурации точек с ее центром с учетом допустимого смещения. На шаге 1009 проверяют соответствие четности извлеченного из обнаруженной конфигурации точек порядкового номера значению бита четности. Это необходимо для того, чтобы избежать ошибок при определении порядкового номера соответствующей порции данных, закодированной в обнаруженной конфигурации точек. Кроме указанных условий также выполняется анализ достоверности этих данных. Для этого вычисляют распределение встречаемости единичных значений обнаруженных битов, каждый из которых потом соотносится с одной из категорий: достоверное значение бита и недостоверное. Для предпочтительного варианта изобретения в качестве битов с недостоверным значением выступают биты, для которых количество единичных значений, обнаруженных в анализируемой конфигурации точек, равняется одному. Такие значения, предположительно, могут являться результатом шума. Отношение количества достоверных битов к недостоверным, по меньшей мере, должно превышать два. Конфигурацию точек, для которой выполняются указанные условия, маркируют (шаг 1010) как достоверную, а служебные метки - как обнаруженные и не нуждающиеся в дальнейшем анализе. Если одно из условий было нарушено, то рассматриваемую служебную метку обозначают как уже участвующую в анализе, и переходят к другой метке. Эта процедура повторяется до тех пор, пока все обнаруженные служебные метки не будут рассмотрены.

Основные этапы обнаружения и распознавания конфигурации точек проиллюстрированы на Фиг.11. Фрагмент исходного бинарного изображения с внедренной конфигурацией точек для разрешения печати 600 dpi показан на Фиг.11.1. На Фиг.11.2 показан результат бинаризации сканированного изображения с разрешением сканирования 300 dpi. Можно заметить, что часть встроенных точек была потеряна в процессе печати и сканирования. На Фиг.11.3 показан результат распознавания конфигурации точек, включая служебные метки. Квадратом обведены области обнаруженных служебных меток, кругом обведены области частично поврежденных служебных меток. Крестом обозначены обнаруженные элементы тела конфигурации точек, кодирующие порцию данных с порядковым номером и битом четности.

На Фиг.12 проиллюстрирован процесс получения порции данных на примере конфигурации точек с Фиг.11. Для сравнения на Фиг.12.1 приведены исходное и результирующее распределения встречаемости единичных значений для каждого бита. Встроенная информация повторяется четыре раза в конфигурации точек, на рисунке она обозначена светло-серыми полосами. Элементы извлеченной информации обозначены полосами темно-серого цвета. Максимальное количество встречаемости единичных значений битов равняется трем, минимальное - единице, ложные обнаружения отсутствуют. Соответственно около 47% процентов всех встроенных точек были утеряны. Несмотря на частичную потерю данных накопление статистики по всем конфигурациям точек с одинаковыми порядковыми номерами позволяет восстановить информацию с высокой точностью. Бит четности обеспечивает дополнительный контроль правильности извлечения информации. На