Пользователь
81,4
рейтинг
3 июня 2011 в 17:31

Разработка → «Выглядит похоже». Как работает перцептивный хэш перевод

За последние несколько месяцев несколько человек спросили меня, как работает TinEye и как в принципе работает поиск похожих картинок.

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

Это восприятие!

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

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

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

Выглядит неплохо

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

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



1. Уменьшить размер. Самый быстрый способ избавиться от высоких частот — уменьшить изображение. В данном случае мы уменьшаем его до 8х8, так что общее число пикселей составляет 64. Можно не заботиться о пропорциях, просто загоняйте его в квадрат восемь на восемь. Таким образом, хэш будет соответствовать всем вариантам изображения, независимо от размера и соотношения сторон.

=

2. Убрать цвет. Маленькое изображение переводится в градации серого, так что хэш уменьшается втрое: с 64 пикселей (64 значения красного, 64 зелёного и 64 синего) всего до 64 значений цвета.

3. Найти среднее. Вычислите среднее значение для всех 64 цветов.

4. Цепочка битов. Это самое забавное: для каждого цвета вы получаете 1 или 0 в зависимости от того, он больше или меньше среднего.

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

= = 8f373714acfcf4d0

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

Если вам нужно сравнить две картинки, то просто строите хэш для каждой из них и подсчитываете количество разных битов (это расстояние Хэмминга). Нулевое расстояние означает, что это, скорее всего, одинаковые картинки (или вариации одного изображения). Дистанция 5 означает, что картинки в чём-то отличаются, но в целом всё равно довольно близки друг к другу. Если дистанция 10 или больше, то это, вероятно, совершенно разные изображения.

Пробуем pHash

Хэш по среднему простой и быстрый, но он даёт сбои. Например, может не найти дубликат картинки после гамма-коррекции или изменения цветовой гистограммы. Это объясняется тем, что цвета меняются в нелинейной масштабе, так что смещается положение «среднего» и многие биты меняют свои значения.

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

1. Уменьшить размер. Как и в случае хэша по среднему, pHash работает на маленьком размере картинки. Однако, здесь изображение больше, чем 8х8, вот 32x32 хороший размер. На самом деле это делается ради упрощения DCT, а не для устранения высоких частот.



2. Убрать цвет. Аналогично, цветовые каналы убирают, чтобы упростить дальнейшие вычисления.

3. Запустить дискретное косинусное преобразование. DCT разбивает картинку на набор частот и векторов. В то время как алгоритм JPEG прогоняет DCT на блоках 8x8, в данном алгоритме DCT работает на 32x32.

4. Сократить DCT. Это магический шаг. В то время как первоначальный блок был 32x32, сохраните только левый верхний блок 8x8. В нём содержатся самые низкие частоты из картинки.

5. Вычислить среднее значение. Как и в хэше по среднему, здесь вычисляется среднее значение DCT, оно вычисляется на блоке 8x8 и нужно исключить из расчёта самый первый коэффициент, чтобы убрать из описания хэша пустую информацию, например, одинаковые цвета.

6. Ещё сократить DCT. Тоже магический шаг. Присвойте каждому из 64 DCT-значений 0 или 1 в зависимости от того, оно больше или меньше среднего. Такой вариант уже выдержит без проблем гамма-коррекцию или изменение гистограммы.

7. Постройте хэш. 64 бита превращаются в 64-битное значение, здесь тоже порядок не имеет значения. Чтобы посмотреть, на что похож отпечаток визуально, можно присвоить каждому пикселю значения +255 и -255, в зависимости от того, там 1 или 0, и преобразовать DCT 32x32 (с нулями для высоких частот) обратно в изображение 32x32.

= 8a0303769b3ec8cd

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

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

Лучший в своём классе?

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

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

Разновидности

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

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

Если вы можете сравнивать картинки, то перед вами открываются совершенно новые перспективы. Например, поисковик GazoPa позволяет рисовать картинку на экране. Как и в случае с TinEye, я не знаю всех деталей их алгоритма, но похоже на какой-то вариант перцептивного хэша. И поскольку хэш-функция сводит всё что угодно на низкие частоты, то мой кривой рисунок трёх фигурок с ручками-палочками может сравниться с другими изображениями, в том числе с фотографиями, на которых изображены трое людей.
Перевод: Dr. Neal Krawetz
Анатолий Ализар @alizar
карма
751,5
рейтинг 81,4
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (42)

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

      Это вступление статьи, которая уже лежит у меня в черновиках. Если будет карма, то смогу опубликовать ее и буду очень всем благодарен.

      Сразу говорю, что метод, который там описывается, возможно уже давно существует, но там есть еще готовый код (класс на пхп), реализующий этот алгоритм.
  • +1
    Большое спасибо за статью. Сам сталкивался с подобной задачей некоторое время назад, только речь шла о видео файлах. Подскажите, вам не попадались методики, позволяющие осуществлять эффективный поиск изображений, измененных с помощью афинных преобразований и кропинга?
    • +1
      Конечно напрашиваются инвариантные дескрипторы из SIFT, SURF и тд, но мне кажется это выйдет очень ресурсоемко.
      • 0
        построение дескриптора — 80..120мс работы одного ядра. фигня.
        поиск по дескрипторам — нужно строить индекс. если сможете сделать древовидный индекс, это не так уж и ресурсоёмко
    • +10
      Это Вы Ализару вопросы задаете, да?
  • +4
    C женой он смешно придумал )
    • +3
      только в данном случае, наверно правильнее сказать «моей следующей жены». Если я, конечно, ничего не пропустил, и он действительно не собирается на ней жениться.
  • +13
    Ммм, Элисон Ханниган :)
  • 0
    А я думал что все сложнее!
    Спасибо автору за идеи!
    Пошел писать код для своей узкой задачки. :)
  • 0
    Спасибо автору. Такой вопрос, как думаете, можно ли с помощью этого алгоритма организовать распознавание лиц людей. Тоесть выделять лицо из изображения будет другой алгоритм, а вот идентифицировать уже алгоритм на основе перцептивного хэша?
    • 0
      Нет, потому что: (из статьи) «Итоговый хэш не изменится, если картинку масштабировать, сжать или растянуть. Изменение яркости или контраста, или даже манипуляции с цветами тоже сильно не повлияет на результат.» Не думаю, что разные изображения одного лица можно свести к таким преобразованиям.
  • +1
    Каждому пикселю значения 255 или -255? Ну-ну.
    Да, ваши хэши не держат поворот. Где-то 10% падения точности на каждый градус поворота. Поправили заваленный горизонт на фотке — и вот уже опаньки. Серебряной пули не бывает, увы. :(
  • +8
    решал задачу поиска похожих изображений. так вот, описанный метод — не работает. достаточно чуть-чуть повернуть картинку, и привет. достаточно нанести на картинку надпись — и это уже «другая» картинка. кропим — и опять нет совпадения.

    обычно такая задача решается
    1. выделением features (sift, surf)
    2. умением по наборам features сказать, похожи ли картинки
    3. индексацией features (кстати, flann — говно)
    • +1
      Чем вам flann то не угодил?
      • 0
        куча негативного опыта. дело было так: в самом начале я использовал просто вычисление расстояние и выбор наименьшего. ну, самый тупой возможный вариант.
        когда дескрескрипторов было примерно 100 тысяч, я решил попробовать flann. сделал, запустил, работает. kdtree. работает, естественно, сильно быстрее. но несколько раз ловил сегфолты (уже не помню, при индексации или при первом поиске)
        тогда я убрал flann, вернул линейный поиск, но перевёл дескрипторы в int и сделал вычисление расстояние через sse intrinsics. и стало даже немного быстрее, чем с flann, хотя алгоритм всё такой же тупой.
        сделал самостоятельно дерево, скорость возросла на несколько порядков.

        сейчас у меня проиндексировано порядка 15 млн дескрипторов, и поиск ближайшего дескриптора занимает 0.006 секунд (у одного ядра. то есть компьютер с 24 ядрами может делать 4 тысячи поисков в секунду. ну, если бы он занимался только этим)

        но, возможно, я просто неправильно что-то делал с flann — такое тоже возможно. поделитесь опытом?
        • 0
          да, уточню. речь идёт об opencv::flann.
        • 0
          По какому принципу в int переводили? Сколько знаков после запятой брали?
  • 0
    А вот как, интересно, TinEye находит сходство, если одна фотография обрезана?
    Или наоборот, вокруг добавлен лишний контент?
    Классический пример — фотография и она же, вставленная в демотиватор.
    • 0
      Когда-то давно, когда я был студентом, я делал поиск картинок по гистограмме цветов. Собственно знаний тогда никаких не было, поэтому придумал что придумал, но на удивление это неплохо работало. В том числе если к примеру добавить какие-то объекты вроде однородного текста или фигур.
      • 0
        Верное направление — гистограмма — самый инвариантный к искажениям набор признаков.
        • –2
          гистограммы — самый примитив и древность в области поиска изображений по содержимому (визуальному подобию)
  • 0
    Долго думал прежде чем отписаться: если это и работает, то в очень ограниченном прикладе. Как правильно говорили выше — сбор признаков, их анализ и распознавание! Тут в виде признака — слабенький хеш, и это плохо. Ну к примеру, если вместо этого хеша, брать специально обработанные компоненты разложения Фурье — то лучше получится + инвариантность к повороту и масштабу можно обеспечить. Дилетантство вижу я тут :).
  • +2
    Кстати недавно закончился конкурс от Яндекса. Темой конкурсного задания был анализ визуального сходства изображений. Вот там в комментариях описывают алгоритмы http://clubs.ya.ru/i...m_no=896. Так я к тому, что там можно почитать про реальные результаты полученные при обработке изображений и можно сравнить алгоритмы, описанные выше в комментариях.
    Что касается данного метода, то он интересен, но как поведет себя в реальности (например, на той же выборке, что давалась на конкурсе) надо проверить.
  • +2
    никогда не говорите девушке ты моя «следующая жена»
  • НЛО прилетело и опубликовало эту надпись здесь
  • +6
    Статью, увы, писал дилетант, похоже не имеющий никакого представления о прикладном разделе компьютерного зрения именуемого CBIR. Для быстрого и краткого ознакомления рекомендую для начала почитать статью Википедии по приведённой ссылке.
    Вместо престранного термина «перцептивный хэш-алгоритм» куда более уместно использовать «низкоуровневые признаки изображения» (low-level image features).

    В остальном, всем интересующимся темой предлагаю ознакомиться со следующим:
      • 0
        А существуют какие-нибудь готовые решения? Как продукт, не как библиотеки? Скажем, есть массив изображений, хочется наладить по нему поиск с тем или иным критерием похожести — есть ли софт, который может и проиндексировать и сложить индекс куда надо и потом искать по нему?

        Желательно опенсорц, конечно, потому что проприетарщины за дикие мегабаксы понятно что много.
        • +1
          Из опенсорс, увы, среди более-менее законченных и готовых к применению продуктов выбирать особенно не из чего…
          Глючный и не шибко быстрый imgSeek.
          Есть ещё какой-то не очень понятный с лицензионной точки зрения freeware/open source российской разработки AntiDupl. Старые версии автор писал на С++, теперь перешёл на .NET. Не знаю, правда, как у него обстоят дела с поиском произвольных изображений в коллекции, программа в основном заточена на автоматический поиск дубликатов.
          Из фриварных попробуйте img(Rummager). Впринципе, довольно функциональный, поддерживает различные метрики, но в высокой скорости работы не замечен.
          Статью про него img(Rummager): An interactive content based image retrieval system можете скачать на сайте по ссылке. Там же есть и другие интересные на тему CBIR.
          • +1
            Спасибо большое за ссылки!
          • 0
            А для поиска одинаковых видео что-нибудь есть? Особенно интересно если видео в разных кодеках и разных качествах.
  • 0
    спасибо за статью!
    набросал первый вариант рассчёта хэша на OpenCV:
    image
    • +4
      Вы не поверите, но очень трудно будет найти похожих кошек :)
  • –1
    Лили, лапушка!
  • 0
    Напишу на случай, если кто-то будет делать pHash по описанию в этой статье. В статье написана ЧУШЬ. Правильный алгоритм DCT-pHash такой (описан в phash.org/docs/pubs/thesis_zauner.pdf, раздел 3.2.1):

    1. Картинка уменьшается до 32×32
    2. Переводится в grayscale
    3. Применяется DCT 32×32
    4. (вот тут разница) Из полученной матрицы 32×32 берётся подматрица 8×8 со сдвигом 1×1 от верхнего левого угла (!). То есть, если наша 32×32 пронумерована как 0..31×0..31, то мы берём пересечение 1..8×1..8.
    5. Вычисляем среднее значение величин полученной матрицы
    6. Составляем из 64 величин матрицы 64-битовый массив, в котором бит равен 1, если значение величины больше среднего, 0 если меньше.

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

    Это бред, картинка и её фурье-образ могут быть похожи только случайно.
    • 0
      А примера такого же пошагового алгоритма DCT применительно именно к пиксельной матрице (п.3 на пальцах) нету ли где-нибудь?
      • 0
        Ну, это просто перемножение матриц: res = dct × src × dctTransp
        src — матрица яркостей картинки
        dctTransp — это транспонированная матрица dct
        dct — это такая матрица www-rohan.sdsu.edu/doc/matlab/toolbox/images/transfo7.html (у нас M=32)

        Но вообще, этот pHash особого смысла не имеет — огромное число ложных срабатываний, на более-менее большой базе им пользоваться невозможно.
        • 0
          Спасибо за правку алгоритма, реализовал его после простого первого варианта «по среднему» — реально работает гораздо лучше первого метода: для однотипных картинок разного размера — вполне достаточно, если сравнивать расстояние Хэмминга в пределах 20% от размерности матрицы. А простой метод — полная лажа.
  • 0
    Наткнулся на эту статью, когда искал информацию о перцептивных хешах.
    Я пишу диплом на тему «обнаружение дупликатов изображений с помощью перцептивных хешей».
    В программировании почти ничего не понимаю, на предыдущих курсах работали только в матлаб, а здесь как я понимаю нужно разбираться в c++, что точно не про меня. С темой так получилось, что мне дали такую. Предлагалось разработать код программы для поиска лиц.
    Может ли кто-то помочь мне с этим? Я пытаюсь разобраться, но всё очень плохо доходит. Диплом уже скоро защищать, а я только предоставил описание трех типов алгоритмов ahash, phash и dhash.
    Спасибо!

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