Поиск похожих изображений, разбор одного алгоритма

[Germanjon]

1.Одинаковые изображения разного размера (длина-ширина) корректно сравниваются?
2. Остаётся вопрос корректности приведения к чёрно-белому формату. В данном случае ярко-белое снежное поле и голубое небо могут оцениваться как одинаковое изображение. Возможно, имеет смысл делать четыре проверки векторов — «Чёрно-белые» и по каждому из цветов RGB.

[Aquahawk]

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

[rjhdby]

1. Да, там же сетка относительная, а не абсолютная. Плюс значение узла вычисляется в области, размер которой завязан на общие размеры изображений. Скажу больше — растянутые изображения тоже ищутся.
2. Точность, конечно, будет больше, но это в 4 раза больше данных со всеми сопутствующими накладными расходами. На практике метод отлично справляется опираясь только на чёрно-белый вариант.

[arandomic]

Не сравнивали с другими perceptual hash алгоритмами?
Т.е. подготовить набор изображений и их искаженных версий и сравнить вашу реализацию с другими по количеству false positive/false negative ошибок. Ну и по скорости обработки большого количества фотографий.
Например с blockhash?

[rjhdby]

Скажем так, выбирал не я и было это давно. :)
Возможно я и проведу такое сравнение, но, с очень большой долей вероятности, делать это придется в свободное от работы время, поскольку качество текущей реализации соответствует рабочим ожиданиям.
По скорости — в конце статьи есть ссылка на предыдущую, с "попугаями". В контейнере на локальном буке поиск по 10М изображений отрабатывает за ~1.5 секунды. Ищет хорошо (на тестовом наборе нашла все, что нужно и ничего, что не нужно)

[sgjurano]

1.5 секунды на поиск? Это очень много, faiss позволяет получить время поиска порядка 50 ms при поиске по миллиардному индексу, hnsw справится за единицы ms (хотя строиться миллиардный индекс будет пару недель).

[rjhdby]

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

[sgjurano]

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

[aamonster]

Устойчивость к кропу проверяли? Вызывает некоторые сомнения, особенно при наличии выраженной текстуры на изображении.

[rjhdby]

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

[rjhdby]

промахнулся.

[lavilav]

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

[arandomic]

perceptual hash — общее название нескольких алгоритмов, можете указать конкретнее, какую реализацию используете?

[lavilav]

radial hash

[avallac]

Данная тема для меня близка и интересна. Есть несколько вопросов. Как я вижу, ваш метод неустойчив к кропу и поворотам. Почему не используете ключевые точки и дескрипторы? Там множество хороших алгоритмов. Какая нагрузка на ваш поисковой движок? (Количество изображений/запросов в секунду).

Моя реализация устойчива к кропу/ресайзу/ватермаркам/поворотам. База 100M на 3х древних серверах (порядка сдвоенного Xeon E5430), ищет порядка 2 картинки в секунду.

[lavilav]

вы делали для себя или это продукт?

[avallac]

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

У меня есть презентация:
www.youtube.com/watch?v=gD7dSBcL9AI

[rjhdby]

Вот самое интересное то и не рассказали! :D
Спасибо, очень интересно было посмотреть.

[avallac]

Нуууу да, меня уже поругали. Я с эту тему еще рассказывал на DevFest, там как раз все внутренние части описаны. И про дерево и про борьбу с коллизиями. Но организаторы так и не выложили видео :(

[vagran]

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

[rjhdby]

Почему не используете ключевые точки и дескрипторы?

Как я ответил выше — этот алгоритм был выбран довольно давно и не мной. Моей задачей было переписать реализацию для большего соответствия требованиям компании. Собственно поэтому про ключевые точки и дескрипторы я прокомментировать не смогу. Sad, but true.

Моя реализация устойчива к кропу/ресайзу/ватермаркам/поворотам.

А можно на нее посмотреть?

[avallac]

Постом выше я скинул ссылку на мой рассказ по этой теме. Если хотите пощупать поближе, пишите в личку :)

[Arseny_Info]

Кажется, что сейчас использовать классическое компьютерное зрение, а не deep learning — чаще плохая идея.
В качестве бейзлайна можно достать дескрипторы картинок из любой предобученной сети (например, какой-нибудь resnet, обученный на imagenet), сложить их в какую-то структуру для быстрого поиска похожих (например, github.com/spotify/annoy) и быстро искать. По точности будет явно не хуже, скорость поиска — тоже, а главное достоинство — когда точности перестанет хватать, можно будет переобучить сетку на своих данных и добиться точности, близкой к идеальной.

[david_mz]

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

[rjhdby]

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

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