Как бороться с репостами или пара слов о перцептивных хешах

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

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

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

Обзор


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

  • Предварительная обработка. На этой стадии изображение приводится к виду, в котором его легче обрабатывать для построения хеша. Это может быть применение различных фильтров (например, Гаусса), обесцвечивание, уменьшение размеров изображения и т.д.
  • Основные вычисления. Из полученного на 1 стадии изображения строится матрица (или вектор). Матрица (вектор) может представлять из себя матрицу частот (например, после преобразования Фурье), гистограмму яркостей, или еще более упрощенное изображение.
  • Построение хеша. Из матрицы (вектора), полученной на 2 стадии берутся некоторые (возможно все) коэффициенты и преобразуются в хеш. Обычно хеш получается размером от 8 до ~100 байт. Вычисленные значения хешей затем сравниваются с помощью функций, вычисляющих «расстояние» между двумя хешами.


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

Перцептивные хеш-алгоритмы


Мы будем рассматривать 4 различных хеш алгоритма: Simple Hash[4], DCT Based Hash[1],[11], Radial Variance Based Hash[1],[5] и Marr- Hildreth Operator Based Hash[1],[6].

Simple Hash (a.k.a Average Hash)

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

  • Уменьшить размер. Самый быстрый способ избавиться от высоких частот — уменьшить изображение. Изображение уменьшается до размера в диапазоне 32х32 и 8х8.
  • Убрать цвет. Маленькое изображение переводится в градации серого, таким образом хеш уменьшается втрое.
  • Вычислить среднее значение цвета для всех пикселей.
  • Построить цепочку битов. Для каждого пикселя делается замена цвета на 1 или 0 в зависимости от того, больше он или меньше среднего.
  • Построить хеш. Перевод 1024 битов в одно значение. Порядок не имеет значения, но обычно биты записываются слева направо, сверху вниз.


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

image
Исходное изображение

image
Полученный «отпечаток»

Discrete Cosine Transform Based Hash (a.k.a. pHash)

Дискретное косинусное преобразование (ДКП, DCT) [7] – одно из ортогональных преобразований, тесно связанное с дискретным преобразованием Фурье (ДПФ) и являющееся гомоморфизмом его векторного пространства. ДКП, как и любое Фурье-ориентированное преобразование, выражает функцию или сигнал (последовательность из конечного числа точек данных) в виде суммы синусоид с различными частотами и амплитудами. ДКП использует только косинусные функции, в отличие от ДПФ, использующего и косинусные, и синусные функции. Существует 8 типов ДКП [7]. Самый распространенный – второй тип. Его мы и будем использовать для построения хеш-функции.
Давайте разберемся, что такое второй тип ДКП:

Пусть x[m], где m = 0,…, N — 1 — последовательность сигнала длин N. Определим второй тип ДКП, как

image

Это выражение можно переписать как:

image

где c[n,m] – элемент матрицы ДКП на пересечении строки с номером n и столбца с номером m.
ДКП матрица определяется как:

image

Данная матрица очень удобна, для вычисления ДКП. ДКП может быть вычислена заранее, для любой необходимой длины. Таким образом ДКП может быть представлена в виде:
ДКП=M×I×M'
Где M – ДКП матрица, I – изображение квадратного размера, M’ – обратная матрица.

Низкочастотные коэффициенты ДКП наиболее стабильны к манипуляциям с изображениями. Это происходит потому, что большая часть информации сигнала, как правило, сосредоточена в нескольких низкочастотных коэффициентах. В качестве матрицы I обычно берется изображение, сжатое до размера 32х32 и упрощенное с помощью различных фильтров, например, обесцвечивания. В итоге получается матрица ДКП (I), в левом верхнем углу которой и находятся низкочастотные коэффициенты. Чтобы построить хеш берется левый верхний блок частот 8x8. Затем из этого блока строится хеш размером 8 байт с помощью нахождения среднего и построения цепочки бит (также, как в Simple Based Hash).
Перечислим шаги построения хеша с помощью данного алгоритма:
  • Убрать цвет. Для подавления ненужных высоких частот;
  • Применить медианный фильтр [8] для уменьшения уровня шума. При этом, изображение разбивается на так называемые «окна», затем каждое окно заменяется медианой [9] для соседних окон;
  • Уменьшить изображение до размера 32x32;
  • Применить ДКП к изображению;
  • Построить хеш.

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

Radial Variance Based Hash

Идея алгоритма Radial Variance Based Hash состоит в построении лучевого вектора дисперсии (ЛВД) на основе преобразования Радона [5]. Затем к ЛВД применяется ДКП и вычисляется хеш. Преобразование Радона — это интегральное преобразование функции многих переменных вдоль прямой. Оно устойчиво к обработке изображений с помощью различных манипуляций (например, сжатия) и геометрических преобразований (например, поворотов). В двумерном случае преобразование Радона для функции f(x,y) выглядит так:

image

Преобразование Радона имеет простой геометрический смысл – это интеграл от функции вдоль прямой, перпендикулярной вектору n = (cos a,sin a) и проходящей на расстоянии s (измеренного вдоль вектора n, с соответствующим знаком) от начала координат.

image

Чтобы преобразование Радона расширить для дискретных изображений, линейный интеграл по прямой d = x ∙ cos α + y ∙ sin α может быть аппроксимирован путем суммирования значений всех пикселей, лежащих в линии шириной один пиксель:

image

Позже было обнаружено, что лучше использовать дисперсию вместо суммы значений пикселей вдоль линии проекции [6]. Дисперсия намного лучше обрабатывает яркостные разрывы вдоль линии проекции. Такие яркостные разрывы появляются из-за краев, которые ортогональны линии проекции.
Теперь определим лучевой вектор дисперсии. Пусть Г(α) – набор пикселей на линии проекции, соответствующей данному углу. Пусть (x′, y′) – координаты центрального пикселя на изображении. x, y принадлежат Г(α) тогда и только тогда, когда

image

Теперь определим лучевой вектор дисперсии (radial variance vector):
Пусть I(x,y) обозначает яркость пикселя (x,y), #Г(α) – мощность множества, тогда лучевой вектор дисперсии R[α], где α = 0,1, … ,179 определим как

image

Достаточно построить вектор по 180 значениям угла, так как преобразование Радона является симметричным. Полученный вектор можно использовать для построения хеша, но в этом алгоритме предлагается еще некоторое улучшение — применить ДКП к полученному вектору. В результате получится вектор, наследующий все важные свойства ДКП. В качестве хеша берутся первые 40 коэффициентов полученного вектора, которые соответствуют низким частотам. Таким образом, размер полученного хеша — 40 байт.
Итак, перечислим шаги построения хеша с помощью данного алгоритма:
  • Убрать цвет для подавления ненужных высоких частот;
  • Размыть изображение (blurring) с помощью использования Гауссова размытия [10]. Изображение преобразуется с помощью функции Гаусса для подавления некоторых шумов;
  • Применить гамма-коррекцию для устранения блеклости изображения.
  • Построить лучевой вектор дисперсии;
  • Применить ДКП к вектору дисперсии;
  • Построить хеш.

Для сравнения хешей этого типа используется поиск пика взаимнокорреляционной функции.

Marr-Hildreth Operator Based Hash

Оператор Марра-Хилдрета [16] позволяет определять края на изображении. Вообще говоря, границу на изображении можно определить как край или контур, отделяющий соседние части изображения, которые имеют сравнительно отличные характеристики в соответствии с некоторыми особенностями. Этими особенностями могут быть цвет или текстура, но чаще всего используется серая градация цвета изображения (яркость). Результатом определения границ является карта границ. Карта границ описывает классификацию границ для каждого пикселя изображения. Если границы определять как резкое изменение яркости, то для их нахождения можно использовать производные или градиент.
Пусть функция image обозначает уровень яркости для линии (одномерный массив пикселей). Первый подход определения границ заключается в нахождении локальных экстремумов функции, то есть первых производных. Второй подход (метод Лапласа) заключается в нахождении вторых производных image [1].
Оба подхода могут быть адаптированы для случая двумерных дискретных изображений, но с некоторыми проблемами. Для нахождения производных в дискретном случае требуется аппроксимация. Кроме того, шум на изображении может значительно ухудшить процесс поиска границ. Поэтому перед определением границ к изображению нужно применить какой-либо фильтр, подавляющий шумы. Для построения хеша можно выбрать алгоритм, использующий оператор Лапласа (2 подход) и фильтр Гаусса.
Определим непрерывный Лапласиан (оператор Лапласа):
Пусть image определяет яркость на изображении. Тогда непрерывный Лапласиан определим как:

image

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

image

где * обозначает свертку функций. Чтобы построить карту границ, нужно найти обращения в ноль дискретного оператора image.
Теперь рассмотрим оператор Марра-Хилдрета. Он также называется Лапласиан от фильтра Гаусса (LoG) – это особенный тип дискретного оператора Лапласа. LoG конструируется с помощью применения оператора Лапласа к фильтру (функции) Гаусса. Особенность этого оператора в том, что он может выделять границы в определенном масштабе. Переменную масштаба можно варьировать для того, чтобы лучше выявить границы.
Фильтр Гаусса определим как:

image

Свертку с операцией Лапласа можно поменять местами, потому что производная и свертка – линейные операторы:

image

Это свойство позволяет заранее вычислить оператор image, потому что он никак не зависит от изображения (image).
(оператор Марра-Хилдрета, Лапласиан от фильтра Гаусса, LoG). LoG hc(x, y) определим как:

image

Чтобы использовать LoG в дискретной форме, сделаем дискретизацию данного уравнения, подставив нужную переменную масштаба. По умолчанию ее значение принимается как 1.0. Затем фильтр можно применить к изображению, используя дискретную свертку.
Определим дискретную свертку:
Пусть x,y,z — пиксельная ширина, длина и глубина изображения I.
Результат R свертки изображения I c маской M определим как:

image

Теперь перечислим шаги алгоритма, использующего для построения хеша оператор Марра-Хилдрета:
  • Убрать цвет для подавления ненужных высоких частот;
  • Перевести изображение в размер 128x128;
  • Размыть изображение(blurring). Изображение преобразуется с помощью функции Гаусса для подавления некоторых шумов [10];
  • Построить оператор Марра-Хилдрета;
  • Применить дискретную свертку к LoG и изображению. Получится
    изображение, на котором четко видны скачки яркости;
  • Преобразовать изображение в гистограмму. Изображение разбивается на маленькие блоки(5x5), в которых суммируются значения яркостей.
  • Построить хеш из гистограммы. Гистограмма разбивается на блоки 3x3. Для этих блоков считается среднее значение яркости и используется метод построения цепочки битов. Получается бинарный хеш размером 64 байта.

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

Функции сравнения перцептивных хеш-значений


Расстояние Хэмминга

Расстояние Хэмминга определяет количество различных позиций между двумя бинарными последовательностями.
Определение:
Пусть А – алфавит конечной длины. image – бинарные последовательности (векторы). Расстояние Хэмминга Δ между x и y определим как:

image

Этот способ сравнения хеш-значений используется в методе DCT Based Hash. Хеш занимает размер 8 байт, поэтому расстояние Хэмминга лежит в отрезке [0, 64]. Чем меньше значение Δ, тем более похожи изображения.
Для облегчения сравнения расстояние Хэмминга можно нормировать с помощью длины векторов:

image

Нормированное расстояние Хэмминга используется в алгоритмах Simple Hash и Marr-Hildreth Operator Based Hash. Расстояние Хэмминга лежит в промежутке [0,1] и чем ближе Δ к 0, тем более похожи изображения.

Пик взаимнокорреляционной функции

Корреляцию между двумя сигналами определим как:

image

где x(t) и y(t) — две непрерывные функции вещественных чисел. Функция rxy(t) описывает смещение этих двух сигналов относительно времени T. Переменная T определяет насколько сигнал смещен слева. Если сигналы x(t) и y(t) различны, функция rxy T называется взаимнокорреляционной.
Определим Нормированную взаимнокорреляционную функцию:
Пусть xi и yi, где i = 0, … N − 1 – две последовательности вещественных чисел, а N – длина обеих последовательностей. НВФ с задержкой d определим как:

image

где mx и my обозначают среднее значение для соответствующей последовательности.
Пик взаимнокорреляционной функции (PCC) – максимальное значение функции rd, которое может быть достигнуто на промежутке d = 0, N.
PCC используется для сравнения хеш-значений в алгоритме Radial Variance Based Hash. PCC ∈ [0,1], чем больше его значение, тем более похожи изображения.

Несколько слов о практике


Мы рассмотрели 4 различных подхода в реализации хеш алгоритмов. Областей применения перцептивный хешей широк, от поиска похожих изображений, до выявления спама на картинках.

В своем проекте мы используем перцептивный хеш для выявления дубликатов изображений. При этом зачастую удается успешно сравнивать между собой изображения, содержащие watermark’и (полученные из разных источников) или изображения с обрезанными краями.
Лучшим алгоритмом для поиска дубликатов можно считать Radial Variance Based Hash, однако его крайне трудно применять на больших объемах данных, из-за очень трудоемкого сравнения хешей.

Для себя мы выбрали DCT based Hash. Мы используем 64 битный хэш, этого вполне хватает для поиска дубликатов, однако столь малый размер хеша неизбежно приводит к коллизиям. С коллизиями мы боремся построением гистограммы (спектра) для изображения.
Каждая компонента спектра означает относительное количество цветов того или иного под диапазона в изображении, другими словами показывает распределение цветов по изображению. Выглядит это примерно вот так:

image

Таким образом, мы сначала ищем изображения сравнивая хеш, а потом сравниваем гистограммы, если гистограммы значительно отличаются, то такое изображение не считается похожим. Сами гистограммы можно сравнивать считая взаимную корреляцию также, как при сравнении Radial Variance Based Hash, с помощью взаимной корреляции Пирсона:
image

Если данная тема интересна сообществу, в следующей статье я расскажу конкретно о нашей реализации DCT hash, а также о способах поиска дистанции Хемминга.

Список литературы
[1] Egmont-Petersen, M., de Ridder, D., Handels, H. «Image processing with
neural networks — a review». Pattern Recognition 35 (10), pp. 2279–2301(2002)
[2] Christoph Zauner. Implementation and Benchmarking of Perceptual Image
Hash Functions (2010)
[3] Locality-sensitive hashing.
en.wikipedia.org/wiki/Locality-sensitive_hashing
[4] Simple and DCT perceptual hash-algorithms.
www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-
It.html
[5] Standaert, F.X., Lefebvre, F., Rouvroy, G., Macq, B.M., Quisquater, J.J.,
and Legat, J.D.: Practical evaluation of a radial soft hash algorithm. In
Proceedings of the International Symposium on Information Technology:
Coding and Computing (ITCC), vol. 2, pp. 89-94. IEEE, Apr. 2005
[6] D. Marrand, E. Hildret. Theory of edge detection, pp. 187-215 (1979)
[7] en.wikipedia.org/wiki/Discrete_cosine_transform
[8] en.wikipedia.org/wiki/Median_filter
[9] en.wikipedia.org/wiki/Median
[10] en.wikipedia.org/wiki/Gaussian_blur
[11] Zeng Jie. A Novel Block-DCT and PCA Based Image Perceptual Hashing
Algorithm. IJCSI International Journal of Computer Science Issues, Vol. 10,
Issue 1, No 3, January 2013
[12] de.wikipedia.org/wiki/Marr-Hildreth-Operator

Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 26
  • +17
    Накидали бы ссылок на статьи которые неоднократно на эту тему на Хабре были. Вот одна сходу — habrahabr.ru/post/120562/
    Ещё была одна или две.
    А то вроде как боретесь с репостами… ;)
  • +1
    Как-то странно «прецептивный» в начале текста перетекло в «перцептивный» :-)
    • 0
      Поправил, спасибо :)
    • +1
      Мне вот интересно, какой хэш будет находить картинки с измененным кадрированием (как в плюс, так и в минус).
      Классические примеры:
      — демотиватор и картинка из него
      — картинка, которую подрезали снизу, чтобы убрать копирайт сайта
      — групповое фото, обрезанное сбоку, чтобы убрать одного человека
      — фрагмент карты/схема и она же целиком
      Ну и так далее.
      • +1
        Хеш вполне справляется с картинками, которые подрезали снизу. Я описывал в статье такие случаи.
        Что касается более глобальных изменений, вроде демотиватора или фрагмента изображения, то ответ скорее нет чем да. Перцептивный хеш не позволяет сделать выводы о фрагментах данных. Т.е. мы не можем ответить на вопрос где именно данные различаются? Мы получаем ответ на вопрос насколько они похожи.
        Для таких случаев больше подходит SURF.
        • +1
          Любой алгоритм который считает интегральный хеш на все изображение, хеши по регулярной сетке(пирамиду коэффициентов по регулярной сетке) не найдут такие изображения.
          А еще в этих хешах нет инварианта к изменению освещения, баланса белого и т.п.
        • +1
          Спасибо за статью, узнал кое-что новое. Кому интересно вот моя реализация (полу)игрушечного дублятора изображений на основе pHash (но без гистограмм): github.com/thekvs/imgdupl
        • +1
          Как думаете, можно ли построить такой хэш для текста?
          • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              Можно, такие решения существуют. Сходу приходит в голову Simhash или Cognitive Hash.
              • 0
                Круто. Я нашёл упоминание cognitive hash всего в одной научной работе, китайского авторства.
              • 0
                Есть еще классический алгоритм rolling хеша. Хотя меня всегда больше волновала задача, как обеспечить быстрый лукап по нечетким хешам, потому как считать расстояние Хемминга крайне затратно. Вариант с сортировкой был бы неплох, но там есть свои проблемы, особенно когда база хешей быстро меняется.
              • 0
                Какой процент коллизий на 64-битном хэше Вы получили?
                И на каком объеме базы?
                Строите ли Вы гистограммы в реальном времени или считаете заранее и храните?
                • +1
                  Объем базы был 6 тысяч популярных картинок собранных на просторах интернета. Процент коллизий составляет примерно 10%.
                  Гистограммы считаем заранее и храним. В реальном времени рассчитывается только расстояние Хэмминга и взаимная корреляция гистограмм.
                  • 0
                    Для такой базы процент коллизий очень высокий.
                    С ростом базы, он, естественно, будет повышаться. Для многих реальных баз в миллионы и сотни миллионов объектов такой хэш не слишком подойдет.
                    Как Вы считаете?
                    • 0
                      Сказать трудно, я начинал разработку с базой в 3к картинок, коллизий тоже было около 10%. В общем случае, пространство картинок счетно и бесконечно, а 64 битный хэш конечен. Исходя из этого, с ростом базы количество коллизий будет расти. Но ведь в реальном мире мы имеем дело с изображениями людей, машин, котиков, а это накладывает определенные ограничения на пространство картинок. Ведь мы не будем смотреть на случайный набор пикселей. Так что говорить о зависимости кол-ва коллизий от кол-ва картинок я не берусь.
                      В целом, если такая проблема имеет место быть, выходов из этих ситуаций можно рассмотреть много, увеличение хэша, использование дополнительных алгоритмов, для уточнения результата (SURF например).
                • 0
                  Пространство любого хэша намного меньше определяемого его длиной.
                  А количество коллизий, вообще говоря, подчиняется обычной теории вероятностей. Кроме, конечно, случаев, связанных с особенностями работы хэша.
                  Ведь получается, что, если процент коллизий постоянен при удвоении базы (как у Вас), то тогда коллизии между старыми и новыми картинками отсутствуют напрочь.
                  Такой эффект может иметь место только если хэш на новых картинках работает совершенно иначе, чем на старых. Например, были кошки, стали машины, и хэш это «понимает» и дает разные значения.
                  • +1
                    Попробуйте для оценки близости гистограмм расстояние Дженсен-Шеннона, основанное на дивергенции Кулбак-Лейблера. В своем проекте мы на нем остановились.
                    • 0
                      Спасибо за наводку.
                      • 0
                        С помощью этого расстояния мы считаем новостные сюжеты на Вебграунде.
                        • 0
                          А в каком формате удобнее хранить гистограмму, для последующей работы с ней?
                          • 0
                            Стандартно: как набор относительных частот.
                            Можно, конечно, и абсолютные частоты использовать, но это только в случае, если суммарная частота одна.
                        • 0
                          Статья хороша — есть над чем поразмышлять :)
                          +1
                          • 0
                            А есть ли пример реализации сравнения гистограмм (один DCT дает много коллизий)? В виде какой-нибудь консольной утилиты или перл-модуля (в идеале).

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