Як боротися з репостами або пара слів про прецептивных хешах

У цій публікації мова йтиме про підходи до побудови прецептивных хешів зображення і можливості їхнього використання (наприклад, пошук дублікатів).

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

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

Огляд

Існує багато різних підходів до формування прецептивного хеш зображення. Всіх їх об'єднує 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, JJ,
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



Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.