Патент на изобретение №2387006

(54) ПРЕДСТАВЛЕНИЕ ЦИФРОВЫХ МАТЕРИАЛОВ, ОСНОВАННОЕ НА ИНВАРИАНТНОСТЯХ МАТРИЦ

(57) Реферат:

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

Область техники, к которой относится изобретение

Это изобретение в целом относится к технологии представления сигналов.

Уровень техники

Цифровые материалы часто распространяются потребителям по частным и общедоступным сетям – таким как интранет или Интернет. В дополнение, эти материалы распространяются потребителям посредством фиксированных считываемых компьютером носителей, таких как компакт-диск (CD-ROM), универсальный цифровой диск (DVD), магнитная дискета или жесткий магнитный диск (например, предварительно загруженный жесткий диск).

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

“Цифровые материалы” является общим обозначением, используемым в настоящей заявке для обозначения электронным образом хранимого или передаваемого контента (содержимого). Примеры цифровых материалов включают в себя изображения, аудиоклипы, видео, мультимедийную информацию, программное обеспечение и данные. В зависимости от контекста цифровые материалы могут также быть названы “цифровой сигнал”, “сигнал контента”, “цифровой поток битов”, “мультимедийный сигнал”, “цифровой объект”, “объект”, “сигнал” и тому подобное.

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

Хэширование

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

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

Ограничения обычного хэширования

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

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

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

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

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

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

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

Применения технологий хэширования

Существуют многие и различные применения технологий хэширования. Некоторые включают в себя антипиратство, категоризацию контента, распознавание контента, вставку водяных знаков, основанное на контенте генерирование ключей и синхронизацию в аудио- и видеопотоках.

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

Сущность изобретения

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

Краткое описание чертежей

Аналогичные ссылочные позиции используются на всех чертежах для ссылки на аналогичные элементы и признаки.

Фиг.1 – блок-схема, показывающая описываемую методологическую реализацию.

Фиг.2 – блок-схема описываемой реализации.

Фиг.3 – пример компьютерной операционной среды, допускающей (полную или частичную) реализацию по меньшей мере одного описываемого варианта осуществления.

Подробное описание

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

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

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

Один пример воплощения Представления Цифровых Материалов, основанного на инвариантностях матриц, может быть назван “иллюстративное средство представления материалов”.

При упоминании рандомизации следует понимать, что эта рандомизация выполняется посредством генератора (например, RC4) псевдослучайных чисел, начальное число которого является секретным ключом (k), где этот ключ противнику неизвестен.

Введение

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

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

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

Квазиглобальные характеристики

Квазиглобальные характеристики являются представителями (типичными представлениями) общих характеристик группы или коллекции индивидуальных элементов. Например, они могут быть статистиками или признаками “областей” (т.е. “сегментов”). Квазиглобальные характеристики не являются представителями (представлениями) индивидуальных локальных характеристик индивидуальных элементов; скорее они являются представителями перцепциального (воспринимаемого) контента группы (например, сегментов) как целого.

Квазиглобальные характеристики могут быть определены (заданы) посредством математического или статистического представления группы. Например, это может быть среднее цветовых значений всех пикселей в группе. Следовательно, такие квазиглобальные характеристики могут также называться “статистическими характеристиками”. Локальные характеристики не представляют робастных статистических характеристик.

Обозначения

Ниже заглавные буквы (например, A, B, C) представляют матрицы, строчные буквы с векторной нотацией (например, ~a, ~b, ~c) представляют векторы-столбцы, а строчные буквы представляют скаляры (например, a, b, c). Секретный ключ представлен посредством k.

Здесь используются следующие математические определения:

– Двумерное представление цифровых материалов размера n x n.

– Единичная матрица размера n x n.

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

– Транспонирование матрицы А.

– Норма Фробенуса матрицы A, определенная как

где a_k,l является элементом A в строке k и столбце l.

– Эрмитово сопряженная матрица для матрицы A. Отметим, что A^H=A^L для вещественных матриц.

– L₂ норма вектора, которая определена как

где является k-ым элементом ~.

– матрица DCT преобразования размера m для 1-мерных сигналов длины m. Отметим, что 2-мерное DCT преобразование матрицы I (размер m x m) определяется как

– матрица DWT преобразования размера m для 1-мерных сигналов длины m. Отметим, что 2-мерное DWT преобразование матрицы I (размер m x m) определяется как

– Вес Хемминга бинарного вектора ~a.

– SVD матрицы определяется как:

где

– ортогональные собственные векторы матрицы AA^H (и в общем случае могут не быть уникальными (однозначными)). называются левыми сингулярными векторами A.

– ортогональные собственные векторы матрицы A^HA (и в общем случае могут не быть уникальными). называются правыми сингулярными векторами A.

–: Диагональная вещественная матрица размера m x m, где i-ый диагональный элемент, a_i, называется i-ым сингулярным значением. Без потери общности можно предполагать, что

Сингулярное разложение(SVD)

Иллюстративное средство представления материалов захватывает сущность геометрической информации, в то же время обеспечивает уменьшение размерности. SVD имеет некоторые доказуемые свойства оптимальности: “лучшая” меньшей размерности (скажем K-мерная) аппроксимация матрицы (скажем ранга N, N>=K) в смысле нормы Фробенуса обеспечивается первыми K сингулярными векторами и соответствующими сингулярными значениями.

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

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

Вместо преобразований DCT/DWT-типа с фиксированным базисом иллюстративное средство представления материалов использует сингулярное разложение (SVD). В случае SVD иллюстративное средство представления материалов выбирает оптимальные базисные векторы в смысле L₂ нормы (см. уравнение (1) ниже). Более того, для заданной матрицы ее SVD единственно. В качестве аналогии, если цифровой материал представлен вектором в некотором пространстве векторов высокой размерности, то сингулярные векторы дают информацию об оптимальном направлении по отношению к материалу в смысле уравнения (1), в то время как сингулярные значения дают информацию о расстоянии вдоль этого направления. Следовательно, сингулярные векторы, которые соответствуют большим сингулярным векторам, естественно подвержены любой атаке масштабирования и другим малым модификациям обычной обработки сигналов.

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

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

Свойства SVD

Ниже описаны математические свойства SVD. Пусть является SVD для А. Тогда

1) Левые сингулярные векторы являются ортогональным базисом для пространства столбцов A.

2) Правые сингулярные векторы являются ортогональным базисом для пространства строк A.

3) Имеем

где и

где являются сингулярными значениями, соответствующие сингулярные векторы.

Хэширование

Хэш-функции, используемой иллюстративным средством представления материалов, передают входные значения – цифровой материал (такой как изображение) I и секретный ключ k. Эта хэш-функция формирует короткий вектор из множества мощности 2^k. Желательно, чтобы перцепциальное хэш-значение было с высокой вероятностью идентично для всех перцепциально сходных цифровых материалов. Также желательно, чтобы два перцепциально различных цифровых материала с высокой вероятностью формировали несвязанные хэш-значения. Такая хэш-функция является преобразованием “много в один”. С другой стороны, для большинства применений может быть достаточно иметь приблизительно сходные (соответственно различные) хэш-значения для перцепциально сходных (соответственно различных) входных значений с высокой вероятностью, т.е. эта хэш-функция может проявлять постепенное изменение.

Требования для такой хэш-функции заданы в виде:

1) Рандомизация: Для любого данного входного значения его хэш-значение должно быть приблизительно равномерно распределено между всеми возможными выходными значениями. Мера вероятности задается секретным ключом.

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

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

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

Методологические реализации иллюстративного

средства представления материалов

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

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

На этапе 120 иллюстративное средство представления материалов псевдослучайным образом формирует многочисленные области из I. Число областей может быть равно p и форма этих областей может быть, например, прямоугольником. Форма этих областей может различаться от реализации к реализации.

Хотя и не обязательно, эти области могут перекрываться друг с другом. Однако может иметь место реализация, которая требует такого перекрытия. И наоборот, может иметь место реализация, которая не допускает перекрытия.

Это действие представлено посредством: A_i является матрицей, которая представляет i-ую псевдослучайную область (например, прямоугольник размера m x m), взятую из цифровых материалов. Отметим, что каждая из этих областей может быть матрицей других размеров и это может быть легко использовано в таком подходе без затруднений.

На этапе 130 формируются векторы характеристик (каждый из которых может быть обозначен из каждой области A_i посредством преобразования на основе SVD. Это формирование векторов характеристик может в общем быть описано как

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

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

В этих реализациях может быть создано так, чтобы давал верхние q сингулярных значений из прямоугольника A_i. Другая возможность заключается в создании так, чтобы давало верхние q сингулярных векторов (левые, правые или вместе). Они являются q сингулярными векторами, которые соответствуют наибольшим q значениям. Естественно, в обоих случаях параметр q должен быть выбран правильно; например, логическое решение может требовать q<

В некоторых реализациях можно выбрать p=1 и A_i так, чтобы они соответствовали всему изображению. Отметим, что этот вариант не обладает какой-либо случайностью; следовательно, это более подходит для не соперничающих (не противоречащих) применений хэширования изображений.

Альтернативно, другие реализации могут выполнять дополнительную обработку, чтобы сформировать даже более гладкие результаты. Этапы 140, 150, 160 и 170 показывают это.

На этапе 140 иллюстративное средство представления материалов формирует вторичное представление J цифровых материалов посредством использования псевдослучайной комбинации векторов характеристик. На этом этапе эти векторы, сформированные как часть этапа 130, могут рассматриваться как “промежуточные” векторы характеристик.

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

Пусть где (соответственно является первым левым (соответственно правым) сингулярным вектором i-ой подсекции. Тогда иллюстративное средство представления материалов псевдослучайным образом формирует гладкое представление J из множества Г: При данном псевдослучайно выбранном начальном сингулярном векторе продолжает формироваться J посредством выбора и замены последующих векторов из Г, таких что следующий выбранный вектор является ближайшим к предыдущему вектору в смысле L₂ нормы.

Следовательно, после 2p шагов все элементы Г являются псевдослучайно переупорядоченными и сформировано J (размера m x 2p). Отметим, что метрика L₂ может быть заменена любой другой подходящей метрикой (возможно рандомизированной) при формировании J, так чтобы были достигнуты непрерывность и гладкость. Гладкий характер для J может быть желательным в некоторых реализациях.

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

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

Это действие представлено посредством: B_i является матрицей, которая представляет i-ую псевдослучайную область (например прямоугольник размера d x d), взятую из вторичного представления J этих цифровых материалов. Отметим, что в этой реализации прямоугольники могут иметь разные размеры. В других реализациях прямоугольники могут иметь одинаковый размер.

На этапе 160 генерируется новый набор векторов характеристик (каждый из которых может быть обозначен из каждой области B_i посредством преобразования на основе SVD. Это формирование векторов характеристик может быть в общем описано как

Эти векторы характеристик являются хэш-значениями. Преобразование на основе SVD является хэш-функцией, которая использует SVD. Примеры хэш-функций описаны ниже в разделе озаглавленном “Хэш-функции на основе SVD”. Эти преобразования (T₁ и T₂) на основе SVD могут быть одинаковыми или отличаться друг от друга.

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

Хэш-функции на основе SVD

В этом разделе описано несколько функций хэширования, которые могут быть использованы преобразованиями (T₁ и T₂) на основе SVD, введенными выше при описании фиг.1.

Хэш-функции SVD-SVD

При заданном изображении, например, иллюстративное средство представления материалов псевдослучайным образом выбирает p под-изображений Затем иллюстративное средство представления материалов находит SVD каждого под-изображения:

где U_i, V_i являются вещественными левой и правой матрицами m x m сингулярных векторов соответственно, и S_i – вещественной диагональной матрицей m x m , состоящей из сингулярных значений вдоль диагонали.

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

DCT-SVD

В качестве варианта подхода SVD-SVD иллюстративное средство представления материалов использует 2D-DCT преобразование в качестве начального преобразования (T_l) на этапе 130. После нахождения 2D-DCT для каждого под-изображения Ai

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

Коэффициенты в этом диапазоне частот затем сохраняются как вектор для каждой области A_i. Упорядочивание элементов ~{d_i} зависит от пользователя и возможно может быть использовано для введения дополнительной случайности. Затем формируется вторичное представление, следуя тем же путем, посредством выбора случайных векторов из множества и псевдослучайного формирования гладкого представления J. Затем, иллюстративное средство представления материалов применяет SVD к J:

и сохраняет первые левый и правый сингулярные векторы в качестве хэш-векторов.

DWT-SVD

Это является вариантом подхода DCT-SVD, где 2D-DCT заменено на 2D-DWT. После получения случайных прямоугольников A_i из изображения, l-уровень DWT применяется к каждому A_i. DC поддиапазоны хранятся в качестве векторов ~ чтобы сформировать вторичное представление J на следующей стадии. Затем к J применяется SVD:

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

Бинарное SVD

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

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

где – бинарные векторы и бинарная операция Исключающее ИЛИ. Другие сингулярные векторы могут быть найдены альтернативно, так что (k+1)-ая сингулярная векторная пара выводится из для суммирования.

Следовательно, после задания порога первые бинарные сингулярные векторы для каждого бинарного под-изображения являются найденными и формируют множество После формирования вторичного бинарного представления J_b на второй стадии иллюстративное средство представления материалов продолжает использовать бинарное SVD на r псевдослучайно выбранных областях. Окончательное значение задается посредством

Прямое SVD

T_l может использоваться как тождественное преобразование и использовать подсекции непосредственно. Эта идея легко применима к бинарным цифровым материалам (таким как бинарное изображение I_b), которые могут быть сформированы после задания порога. Из каждой подсекции A_i размера m x m векторы ~ формируются напрямую из выборок из материалов. Вторичное представление J генерируется непосредственно из Затем иллюстративное средство представления материалов применяет SVD к J:

и сохраняет первые левый и правый сингулярные векторы как хэш-векторы.

Иллюстративная система для генерирования представления цифровых материалов

Фиг.2 показывает иллюстративную систему 200 для генерирования представления цифровых материалов, которая является примером воплощения иллюстративного средства представления материалов.

Система 200 генерирует представление (например, хэш-значение) цифрового материала. В этом примере цифровой материал является изображением. Система 200 включает в себя модуль 210 получения материалов, модуль 220 разбиения, модуль 230 вычисления статистик областей и устройство 240 вывода.

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

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

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

В этом варианте реализации эти области в самом деле перекрываются друг с другом.

Для каждой области модуль 230 вычисления статистик областей вычисляет статистики множества областей, сгенерированных модулем 220 разбиения. Статистики для каждой области вычисляются. Эти статистики, вычисленные модулем 230 вычисления, могут быть векторами характеристик, описанными выше при описании этапов 130 и 160.

Устройство 240 вывода представляет результаты (для каждой области или комбинированно) модуля 230 вычисления статистик областей. Такие результаты могут храниться или использоваться для дальнейших вычислений.

Примеры применений для иллюстративного

средства представления материалов

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

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

Иллюстративная компьютерная система и среда

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

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

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

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

Компьютерная среда 300 включает в себя компьютерное устройство общего назначения в виде компьютера 302. Компоненты компьютера 302 могут включать в себя, но не ограничены ими, один или более процессоров или процессорных устройств 304, системную память 306 и системную шину 308, которая подсоединяет различные системные компоненты, включая процессор 304, к системной памяти 306.

Системная шина 308 представляет собой одну или более любых из нескольких типов структур шин, включающих в себя шину памяти или контроллер памяти, периферийную шину, ускоренный графический порт, и процессор или локальную шину, использующую любую из множества шинных архитектур. В качестве примера такие архитектуры могут включать в себя CardBus, плату Международной ассоциации производителей плат памяти для персональных компьютеров (PCMCIA), ускоренный графический порт (AGP), интерфейс малых компьютерных систем (SCSI), универсальную последовательную шину (USB), IEEE 1394, локальную шину Ассоциации по стандартам в области видеоэлектроники (VESA) и шину соединения периферийных устройств (PCI), также известную как шина расширения (Mezzanine bus).

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

Системная память 306 включает в себя считываемые процессором носители в виде энергозависимой памяти, такой как оперативное запоминающее устройство (RAM) 310, и/или энергонезависимой памяти, такой как постоянное запоминающее устройство (ROM) 312. Базовая система 314 ввода/вывода (BIOS), содержащая базовые процедуры, которые помогают передавать информацию между элементами в компьютере 302, например, в процессе запуска, хранится в ROM 312. RAM 310 обычно содержит данные и/или программные модули, которые непосредственно доступны и/или в текущий момент обрабатываются процессорным устройством 304.

Компьютер 302 может также включать в себя другие съемные/стационарные, энергозависимые/энергонезависимые компьютерные запоминающие носители. В качестве примера, фиг.3 иллюстрирует привод 316 жестких дисков для чтения с или записи на стационарный энергонезависимый магнитный носитель (не показан), привод 318 магнитных дисков для чтения с или записи на съемный энергонезависимый магнитный диск 320 (например “флоппи-диск”) и привод 322 оптических дисков для чтения с и/или записи на съемный энергонезависимый оптический диск 324, такой как CD-ROM, DVD-ROM или другие оптические носители. Привод 316 жестких дисков, привод 318 магнитных дисков и привод 322 оптических дисков каждый подсоединен к системной шине 308 посредством одного или более интерфейсов 326 носителей данных. Альтернативно, привод 316 жестких дисков, привод 318 магнитных дисков и привод 322 оптических дисков могут подсоединяться к системной шине 308 посредством одного или более интерфейсов (не показаны).

Эти приводы и связанные с ними считываемые процессором носители обеспечивают энергонезависимое хранение считываемых компьютером инструкций, структур данных, программных модулей и других данных для компьютера 302. Хотя этот пример иллюстрирует жесткий диск 316, съемный магнитный диск 320 и съемный оптический диск 316, должно быть принято во внимание, что другие типы считываемых процессором носителей, которые могут хранить данные, и к которым компьютер может осуществлять доступ, такие как магнитные кассеты или другие магнитные запоминающие устройства, платы флэш-памяти, CD-ROM, универсальные цифровые диски (DVD) или другие оптические накопители, оперативные запоминающие устройства (RAM), постоянные запоминающие устройства (ROM), электрически стираемые программируемые постоянные запоминающие устройства (EEPROM) и подобные, также могут быть использованы, чтобы реализовать иллюстративную компьютерную систему и среду.

Любое число программных модулей может храниться на жестком диске 316, магнитном диске 320, оптическом диске 324, ROM 312 и/или RAM 310, включая, например, операционную систему 326, одну или более прикладных программ 328, другие программные модули 330 и программные данные 332.

Пользователь может вводить команды и информацию в компьютер 302 посредством устройств ввода, таких как клавиатура 334 и указывающее устройство 336 (например, “мышь”). Другие устройства 338 ввода (конкретно не показаны) могут включать в себя микрофон, джойстик, игровую панель, спутниковую параболическую антенну, последовательный порт, сканер и/или подобное. Эти и другие устройства ввода подсоединены к процессорному устройству 304 посредством интерфейсов 340 ввода/вывода, которые присоединены к системной шине 308, но могут быть подсоединены посредством других интерфейсов и структур шин, таких как параллельный порт, игровой порт или универсальная последовательная шина (USB).

Монитор 342 или другой тип устройства отображения также может быть подсоединен к системной шине 308 посредством интерфейса, такого как видеоадаптер 344. В дополнение к монитору 342 другие периферийные устройства вывода могут включать в себя компоненты, такие как громкоговорители (не показаны) и принтер 346, которые могут быть подсоединены к компьютеру 302 посредством интерфейсов 340 ввода/вывода.

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

Логические соединения между компьютером 302 и удаленным компьютером 348 показаны как локальная сеть (LAN) 350 и глобальная сеть (WAN) 352. Такие сетевые среды являются обычным явлением в учреждениях, компьютерных сетях масштаба предприятия, во внутренних сетях и в Интернет. Такие сетевые среды могут быть проводными или беспроводными.

Будучи реализован в локальной сетевой среде (LAN), компьютер 302 подсоединяется к локальной сети 350 посредством сетевого интерфейса или адаптера 354. Будучи реализован в глобальной сетевой среде (WAN), компьютер 302 обычно включает в себя модем 356 или другие средства для установки связи через глобальную сеть 352. Модем 356, который может быть внутренним или внешним по отношению к компьютеру 302, может подсоединяться к системной шине 308 посредством интерфейсов 340 ввода/вывода или других подходящих механизмов. Также следует принять во внимание, что показанные сетевые соединения являются иллюстративными, и что могут быть использованы другие средства установки связи (связей) между компьютерами 302 и 348.

В сетевой среде, такой как показанная компьютерная среда 300, программные модули, показанные для компьютера 302 или его части, могут храниться в удаленном запоминающем устройстве. В качестве примера, удаленные прикладные программы 358 располагаются на запоминающем устройстве удаленного компьютера 348. В целях иллюстрации прикладные программы и другие исполнимые программные компоненты, такие как операционная система, показаны здесь как дискретные блоки, хотя понимается, что такие программы и компоненты располагаются в различное время на различных запоминающих компонентах компьютерного устройства 302 и исполняются процессором (процессорами) данных компьютера.

Исполняемые процессором инструкции

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

Иллюстративная операционная среда

Фиг.3 иллюстрирует пример подходящей операционной среды 300, в которой может быть реализовано иллюстративное средство представления материалов. Более конкретно, иллюстративное(ые) средство(а) представления материалов, описанное выше, может быть реализовано (полностью или частично) любыми программными модулями 328-330 и/или операционной системой 326, изображенными на фиг.3, или их частями.

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

Считываемые процессором носители

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

“Компьютерные запоминающие носители” включают в себя энергозависимые и энергонезависимые, съемные и стационарные носители, реализованные любым способом или по любой технологии для хранения информации, такой как считываемые компьютером инструкции (команды), структуры данных, программные модули или другие данные. Компьютерные запоминающие носители включают в себя, но не ограничены ими, RAM, ROM, EEPROM, флэш-память или память по другой технологии, CD-ROM, универсальные цифровые диски (DVD) или другие оптические накопители, магнитные кассеты, магнитную ленту, магнитный дисковый накопитель или другие магнитные запоминающие устройства, или любой другой носитель, который может использоваться для хранения необходимой информации, и к которому может быть осуществлен доступ компьютером.

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

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

Заключение

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

Формула изобретения

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

2. Носитель по п.1, в котором по меньшей мере некоторые из областей упомянутого множества перекрываются.

3. Носитель по п.1, в котором упомянутый этап разбиения содержит этап псевдослучайного сегментирования упомянутого материала.

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

5. Компьютер, содержащий один или более считываемых процессором носителей по п.1.

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

7. Система по п.6, в которой по меньшей мере некоторые из упомянутого множества областей перекрываются.

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

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

РИСУНКИ