Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 46
Все невероятное просто.
Сегодня, зайдя в очередной раз на хабр, наткнулся на вот эту интересную статью. Там описывается алгоритм хэширования изображений. Когда я читал эту статью, мне пришла в голову мысль, как можно изменить этот алгоритм, чтобы он кушал изображения, у которых сильно различается, например, яркость (но сами изображения при этом идентичны).
Это вступление статьи, которая уже лежит у меня в черновиках. Если будет карма, то смогу опубликовать ее и буду очень всем благодарен.
Сразу говорю, что метод, который там описывается, возможно уже давно существует, но там есть еще готовый код (класс на пхп), реализующий этот алгоритм.
Это вступление статьи, которая уже лежит у меня в черновиках. Если будет карма, то смогу опубликовать ее и буду очень всем благодарен.
Сразу говорю, что метод, который там описывается, возможно уже давно существует, но там есть еще готовый код (класс на пхп), реализующий этот алгоритм.
Большое спасибо за статью. Сам сталкивался с подобной задачей некоторое время назад, только речь шла о видео файлах. Подскажите, вам не попадались методики, позволяющие осуществлять эффективный поиск изображений, измененных с помощью афинных преобразований и кропинга?
Конечно напрашиваются инвариантные дескрипторы из SIFT, SURF и тд, но мне кажется это выйдет очень ресурсоемко.
построение дескриптора — 80..120мс работы одного ядра. фигня.
поиск по дескрипторам — нужно строить индекс. если сможете сделать древовидный индекс, это не так уж и ресурсоёмко
поиск по дескрипторам — нужно строить индекс. если сможете сделать древовидный индекс, это не так уж и ресурсоёмко
Читал, захотел чтоб тут были ссылки на https://ru.wikipedia.org/wiki/Масштабно-инвариантная_трансформация_признаков и Построение SIFT дескрипторов и задача сопоставления изображений. Так что пусть будут.
Это Вы Ализару вопросы задаете, да?
C женой он смешно придумал )
А я думал что все сложнее!
Спасибо автору за идеи!
Пошел писать код для своей узкой задачки. :)
Спасибо автору за идеи!
Пошел писать код для своей узкой задачки. :)
Спасибо автору. Такой вопрос, как думаете, можно ли с помощью этого алгоритма организовать распознавание лиц людей. Тоесть выделять лицо из изображения будет другой алгоритм, а вот идентифицировать уже алгоритм на основе перцептивного хэша?
Каждому пикселю значения 255 или -255? Ну-ну.
Да, ваши хэши не держат поворот. Где-то 10% падения точности на каждый градус поворота. Поправили заваленный горизонт на фотке — и вот уже опаньки. Серебряной пули не бывает, увы. :(
Да, ваши хэши не держат поворот. Где-то 10% падения точности на каждый градус поворота. Поправили заваленный горизонт на фотке — и вот уже опаньки. Серебряной пули не бывает, увы. :(
решал задачу поиска похожих изображений. так вот, описанный метод — не работает. достаточно чуть-чуть повернуть картинку, и привет. достаточно нанести на картинку надпись — и это уже «другая» картинка. кропим — и опять нет совпадения.
обычно такая задача решается
1. выделением features (sift, surf)
2. умением по наборам features сказать, похожи ли картинки
3. индексацией features (кстати, flann — говно)
обычно такая задача решается
1. выделением features (sift, surf)
2. умением по наборам features сказать, похожи ли картинки
3. индексацией features (кстати, flann — говно)
Чем вам flann то не угодил?
куча негативного опыта. дело было так: в самом начале я использовал просто вычисление расстояние и выбор наименьшего. ну, самый тупой возможный вариант.
когда дескрескрипторов было примерно 100 тысяч, я решил попробовать flann. сделал, запустил, работает. kdtree. работает, естественно, сильно быстрее. но несколько раз ловил сегфолты (уже не помню, при индексации или при первом поиске)
тогда я убрал flann, вернул линейный поиск, но перевёл дескрипторы в int и сделал вычисление расстояние через sse intrinsics. и стало даже немного быстрее, чем с flann, хотя алгоритм всё такой же тупой.
сделал самостоятельно дерево, скорость возросла на несколько порядков.
сейчас у меня проиндексировано порядка 15 млн дескрипторов, и поиск ближайшего дескриптора занимает 0.006 секунд (у одного ядра. то есть компьютер с 24 ядрами может делать 4 тысячи поисков в секунду. ну, если бы он занимался только этим)
но, возможно, я просто неправильно что-то делал с flann — такое тоже возможно. поделитесь опытом?
когда дескрескрипторов было примерно 100 тысяч, я решил попробовать flann. сделал, запустил, работает. kdtree. работает, естественно, сильно быстрее. но несколько раз ловил сегфолты (уже не помню, при индексации или при первом поиске)
тогда я убрал flann, вернул линейный поиск, но перевёл дескрипторы в int и сделал вычисление расстояние через sse intrinsics. и стало даже немного быстрее, чем с flann, хотя алгоритм всё такой же тупой.
сделал самостоятельно дерево, скорость возросла на несколько порядков.
сейчас у меня проиндексировано порядка 15 млн дескрипторов, и поиск ближайшего дескриптора занимает 0.006 секунд (у одного ядра. то есть компьютер с 24 ядрами может делать 4 тысячи поисков в секунду. ну, если бы он занимался только этим)
но, возможно, я просто неправильно что-то делал с flann — такое тоже возможно. поделитесь опытом?
А вот как, интересно, TinEye находит сходство, если одна фотография обрезана?
Или наоборот, вокруг добавлен лишний контент?
Классический пример — фотография и она же, вставленная в демотиватор.
Или наоборот, вокруг добавлен лишний контент?
Классический пример — фотография и она же, вставленная в демотиватор.
Долго думал прежде чем отписаться: если это и работает, то в очень ограниченном прикладе. Как правильно говорили выше — сбор признаков, их анализ и распознавание! Тут в виде признака — слабенький хеш, и это плохо. Ну к примеру, если вместо этого хеша, брать специально обработанные компоненты разложения Фурье — то лучше получится + инвариантность к повороту и масштабу можно обеспечить. Дилетантство вижу я тут :).
Кстати недавно закончился конкурс от Яндекса. Темой конкурсного задания был анализ визуального сходства изображений. Вот там в комментариях описывают алгоритмы http://clubs.ya.ru/i...m_no=896. Так я к тому, что там можно почитать про реальные результаты полученные при обработке изображений и можно сравнить алгоритмы, описанные выше в комментариях.
Что касается данного метода, то он интересен, но как поведет себя в реальности (например, на той же выборке, что давалась на конкурсе) надо проверить.
Что касается данного метода, то он интересен, но как поведет себя в реальности (например, на той же выборке, что давалась на конкурсе) надо проверить.
никогда не говорите девушке ты моя «следующая жена»
Статью, увы, писал дилетант, похоже не имеющий никакого представления о прикладном разделе компьютерного зрения именуемого CBIR. Для быстрого и краткого ознакомления рекомендую для начала почитать статью Википедии по приведённой ссылке.
Вместо престранного термина «перцептивный хэш-алгоритм» куда более уместно использовать «низкоуровневые признаки изображения» (low-level image features).
В остальном, всем интересующимся темой предлагаю ознакомиться со следующим:
Вместо престранного термина «перцептивный хэш-алгоритм» куда более уместно использовать «низкоуровневые признаки изображения» (low-level image features).
В остальном, всем интересующимся темой предлагаю ознакомиться со следующим:
- презентация «Поиск изображений. Методы индексирования изображений. Методы на основе хэш-функций. Обучение метрик. Фильтры объектов для классификации и поиска изображений.» (из курса лекций Введение в компьютерное зрение)
- доклад «Методы поиска изображений по содержанию»
- статья «Сервисы контентного интернет-поиска изображений» (конечно, далёкие от масштаба и популярности TinEye)
- James Z. Wang research group
некоторые алгоритмы:
обзорная статья
Image retrieval: ideas, influences, and trends of the new age
- Fast multiresolution image querying (реализован в опенсорсном проекте imgSeek)
- Wavelet-based image indexing techniques with partial sketch retrieval capability
- Content-based image indexing and searching using Daubechies' wavelets
- Integrated Region Matching for Image Retrieval, A Scalable Integrated Region-Based Image Retrieval System (реализован в системе SIMPLIcity)
- FAST: Toward more effective and efficient image retrieval
обзорная статья
Image retrieval: ideas, influences, and trends of the new age
А существуют какие-нибудь готовые решения? Как продукт, не как библиотеки? Скажем, есть массив изображений, хочется наладить по нему поиск с тем или иным критерием похожести — есть ли софт, который может и проиндексировать и сложить индекс куда надо и потом искать по нему?
Желательно опенсорц, конечно, потому что проприетарщины за дикие мегабаксы понятно что много.
Желательно опенсорц, конечно, потому что проприетарщины за дикие мегабаксы понятно что много.
Из опенсорс, увы, среди более-менее законченных и готовых к применению продуктов выбирать особенно не из чего…
Глючный и не шибко быстрый imgSeek.
Есть ещё какой-то не очень понятный с лицензионной точки зрения freeware/open source российской разработки AntiDupl. Старые версии автор писал на С++, теперь перешёл на .NET. Не знаю, правда, как у него обстоят дела с поиском произвольных изображений в коллекции, программа в основном заточена на автоматический поиск дубликатов.
Из фриварных попробуйте img(Rummager). Впринципе, довольно функциональный, поддерживает различные метрики, но в высокой скорости работы не замечен.
Статью про него img(Rummager): An interactive content based image retrieval system можете скачать на сайте по ссылке. Там же есть и другие интересные на тему CBIR.
Глючный и не шибко быстрый imgSeek.
Есть ещё какой-то не очень понятный с лицензионной точки зрения freeware/open source российской разработки AntiDupl. Старые версии автор писал на С++, теперь перешёл на .NET. Не знаю, правда, как у него обстоят дела с поиском произвольных изображений в коллекции, программа в основном заточена на автоматический поиск дубликатов.
Из фриварных попробуйте img(Rummager). Впринципе, довольно функциональный, поддерживает различные метрики, но в высокой скорости работы не замечен.
Статью про него img(Rummager): An interactive content based image retrieval system можете скачать на сайте по ссылке. Там же есть и другие интересные на тему CBIR.
Спасибо большое за ссылки!
А для поиска одинаковых видео что-нибудь есть? Особенно интересно если видео в разных кодеках и разных качествах.
Кроме убогенького Duplicate Video Search, думаю, ничего.
Более серьёзный VSC частным пользователям не доступен.
Более серьёзный VSC частным пользователям не доступен.
И вот ещё:
Video Comparer by Eric Bohain
Video Comparer by Eric Bohain
Лили, лапушка!
Напишу на случай, если кто-то будет делать 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 если меньше.
«На первый взгляд картинка кажется бессмысленным набором шарообразных очертаний, но если присмотреться, то можно заметить, что тёмные области соответствуют тем же областям на фотографии (причёска и полоса на заднем фоне в правой части фотографии.»
Это бред, картинка и её фурье-образ могут быть похожи только случайно.
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 если меньше.
«На первый взгляд картинка кажется бессмысленным набором шарообразных очертаний, но если присмотреться, то можно заметить, что тёмные области соответствуют тем же областям на фотографии (причёска и полоса на заднем фоне в правой части фотографии.»
Это бред, картинка и её фурье-образ могут быть похожи только случайно.
А примера такого же пошагового алгоритма DCT применительно именно к пиксельной матрице (п.3 на пальцах) нету ли где-нибудь?
Ну, это просто перемножение матриц: res = dct × src × dctTransp
src — матрица яркостей картинки
dctTransp — это транспонированная матрица dct
dct — это такая матрица www-rohan.sdsu.edu/doc/matlab/toolbox/images/transfo7.html (у нас M=32)
Но вообще, этот pHash особого смысла не имеет — огромное число ложных срабатываний, на более-менее большой базе им пользоваться невозможно.
src — матрица яркостей картинки
dctTransp — это транспонированная матрица dct
dct — это такая матрица www-rohan.sdsu.edu/doc/matlab/toolbox/images/transfo7.html (у нас M=32)
Но вообще, этот pHash особого смысла не имеет — огромное число ложных срабатываний, на более-менее большой базе им пользоваться невозможно.
Спасибо за правку алгоритма, реализовал его после простого первого варианта «по среднему» — реально работает гораздо лучше первого метода: для однотипных картинок разного размера — вполне достаточно, если сравнивать расстояние Хэмминга в пределах 20% от размерности матрицы. А простой метод — полная лажа.
Спасибо, очень пригодился ваш пост. Только в 3.2.1 при вычислении хэша в качестве порога берётся не среднее, а медиана.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
«Выглядит похоже». Как работает перцептивный хэш