Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
Блин, а я уж подумал что пятница сегодня. Ан нет, только понедельник.
~ deleted joke about bad test example ~
Было трудно, но…
То, что оппик немного вульгарный это я с Вами согласен. Насчет красивости сложно сказать, слишком субъективна будет тут чья-либо оценка. Сама фотография вроде хорошая.
Очень не люблю девушку с цигаркой в зубах. А у этой еще и с грудью на первом фото что-то не то… Потом понял, что это просто не мой фломастер.
Ну вообще то это портрет Мадонны, довольно известный — goo.gl/yCof63
Но на вкус и цвет, как тут правильно заметили…
Но на вкус и цвет, как тут правильно заметили…
ru.wikipedia.org/wiki/Лена_(изображение)
Я бы добавил в конце опрос.
Я сюда зашел потому что:
— Понравилась дама
— Я знаю что такое «перцептуальный»
— Я хотел бы узнать что такое «перцептуальный»
— Интересна тема топика
Прошу не воспринимать всерьез ;)
Я сюда зашел потому что:
— Понравилась дама
— Я знаю что такое «перцептуальный»
— Я хотел бы узнать что такое «перцептуальный»
— Интересна тема топика
Прошу не воспринимать всерьез ;)
Титьки на Хабре! o_O
А есть оценка процента ложных срабатываний и пропуска правильных изображений? Просто без труда придумываются классы изображений, на которых это не будет работать. Любопытно проценты работы по большой базе. Хотя, конечно, там будет много ручного труда.
Живая база сейчас не содержит дубликатов вообще. И подобный способ определения дубликатов нужен, чтобы не допустить их появления. Хотя в планах было прогнать все изображения и сравнить со всеми, но думаю там не будет совпадений и найдет только себя, (или будет не много, но проверю).
Потому что похожих картинок не так много, если есть вообще.
Что касается вообще ложных срабатываний, то тут конечно очень большой простор и реально есть множество фотографий, которые неправильно считаются дубликатами, из-за многих факторов.
Например недавно получил ложный дубликат картинки, где было много фактурных нарезков, хеши которых совпадают и, опять, сиськи (как отличить одни сиськи от других?). Т.е. из-за совпадения некоторого числа фоновых нарезков и форм грудей, две картинки были признаны дубликатами.
И критерии я пытался выставлять так, чтобы лучше не было вообще совпадений, чем были ложные.
Возможно более актуальная база изображений показала бы, что требуется серьезная дороботка получения хешей, может более жесткие правила к формату нарезков, может увеличить разрядность кластеризации, может проверять не просто хеши, а строить последовательности и проверять совпадение очередности, ну и так далее. Пока стояла задача облегчить жизнь при модерации.
Потому что похожих картинок не так много, если есть вообще.
Что касается вообще ложных срабатываний, то тут конечно очень большой простор и реально есть множество фотографий, которые неправильно считаются дубликатами, из-за многих факторов.
Например недавно получил ложный дубликат картинки, где было много фактурных нарезков, хеши которых совпадают и, опять, сиськи (как отличить одни сиськи от других?). Т.е. из-за совпадения некоторого числа фоновых нарезков и форм грудей, две картинки были признаны дубликатами.
И критерии я пытался выставлять так, чтобы лучше не было вообще совпадений, чем были ложные.
Возможно более актуальная база изображений показала бы, что требуется серьезная дороботка получения хешей, может более жесткие правила к формату нарезков, может увеличить разрядность кластеризации, может проверять не просто хеши, а строить последовательности и проверять совпадение очередности, ну и так далее. Пока стояла задача облегчить жизнь при модерации.
Прогнал по своей небольшой базе. Всего 1 250 фотографий. Плюс в том, что визуально мало похожих и нет дубликатов, поэтому найденные дубликаты — это гарантировано ложное срабатывание.
Началось все с ~2 % дубликатов. Пересмотрел выделения хешей, удалил дубли, вместо 191 хеша стало 50, при этом актуальные совпадения остались. Это дало ~0,75 % ложных результатов.
Решил покрутить критерии оценки. Было, например, расстояние Хэмминга не больше 11, что довольно много. Изменил на 8.
Снизил порог отношения найденных хешей к общему числу. И убрал проверку дескрипторов.
Это дало 0% ложных срабатываний.
И, конечно, не факт, что такое соотношение параметров будет давать 100% результат для любого изображения. Возможно требуется корректировка под частные случаи.
Началось все с ~2 % дубликатов. Пересмотрел выделения хешей, удалил дубли, вместо 191 хеша стало 50, при этом актуальные совпадения остались. Это дало ~0,75 % ложных результатов.
Решил покрутить критерии оценки. Было, например, расстояние Хэмминга не больше 11, что довольно много. Изменил на 8.
Снизил порог отношения найденных хешей к общему числу. И убрал проверку дескрипторов.
Это дало 0% ложных срабатываний.
И, конечно, не факт, что такое соотношение параметров будет давать 100% результат для любого изображения. Возможно требуется корректировка под частные случаи.
Мне припомнился алгоритм шинглов, который применяют в поисковых машинах и для борьбы с плагиатом.
1. В качестве «слова» использовать ключевые точки картинки, которые у Вас уже есть. Если точки могут «гулять» в пределах нескольких пикселей, нужно это учесть.
2. Придумать хеш-функцию с параметром от такой ключевой точки.
3. Для каждого изображения рассчитать для каждой точки N хешей (с разными значениями параметра).
4. Для каждого изображения для каждого значения параметра (от 1 до N) выбрать точку, для которой соответствующий хеш минимален.
5. Искать совпавшие хеши среди отобранных: сортировка и проход.
Если из изображения вырезали часть, то велик шанс, что хотя бы одна точка совпадёт и пара дупликатов будет отобрана. Затем каждую подозрительную пару нужно прогнать через более точный алгоритм. Например, перебирать все варианты расположения одного изображения внутри другого. Если находится положение, при котором изображения хорошо накладываются — передавать для проверки человеческим глазом.
1. В качестве «слова» использовать ключевые точки картинки, которые у Вас уже есть. Если точки могут «гулять» в пределах нескольких пикселей, нужно это учесть.
2. Придумать хеш-функцию с параметром от такой ключевой точки.
3. Для каждого изображения рассчитать для каждой точки N хешей (с разными значениями параметра).
4. Для каждого изображения для каждого значения параметра (от 1 до N) выбрать точку, для которой соответствующий хеш минимален.
5. Искать совпавшие хеши среди отобранных: сортировка и проход.
Если из изображения вырезали часть, то велик шанс, что хотя бы одна точка совпадёт и пара дупликатов будет отобрана. Затем каждую подозрительную пару нужно прогнать через более точный алгоритм. Например, перебирать все варианты расположения одного изображения внутри другого. Если находится положение, при котором изображения хорошо накладываются — передавать для проверки человеческим глазом.
А что здесь будет «параметром»? Масштаб? Или что-то другое?
Наверное, лучше сохранить точки с минимальными хешами для кусочков изображения — чтобы при вырезании было больше шансов, что одна из минимальных точек останется. Правда, тогда придётся хранить ещё в 10 раз больше информации, и вырастет шанс ложных срабатываний.
Наверное, лучше сохранить точки с минимальными хешами для кусочков изображения — чтобы при вырезании было больше шансов, что одна из минимальных точек останется. Правда, тогда придётся хранить ещё в 10 раз больше информации, и вырастет шанс ложных срабатываний.
Параметр — это просто число, заложенное в алгоритм вычисления хеша. К примеру, для строк это число можно учитывать, дополнив исходный текст строчным представлением числа: md5(text + X). Иными словами, нам нужно N разных хеш-функций.
Эффективность алгоритма шинглов зависит от выбора «слов». Действительно, можно рассмотреть каждый возможный квадрат 50x50 пикселей, входящий в изображение. Это подход «в лоб». Если он будет работать нормально, можно на нём и остановиться. Если нет, можно рассматривать только ключевые точки.
Эффективность алгоритма шинглов зависит от выбора «слов». Действительно, можно рассмотреть каждый возможный квадрат 50x50 пикселей, входящий в изображение. Это подход «в лоб». Если он будет работать нормально, можно на нём и остановиться. Если нет, можно рассматривать только ключевые точки.
-3. Для каждого изображения рассчитать для каждой точки N хешей (с разными значениями параметра).
Это считай и есть дескрипторы: берется 16 блоков, по 4*4, вокруг точки и получают 8 чисел ориентиров. 16*8 = 128 чисел на точку.
Совпадение считают поиском ближайших точек.
И если будет 1000 точек, получается 128 000 чисел на картинку. Если картинок 1000, то хранить надо 128 млн чисел.
А проверить на совпадение 128 000 числа с первой картинки * 128 млн всего = 1,63*10^13 чтобы найти одну картинку полным перебором.
Тут вопрос как такое проделать в пределах одного небольшого сервера за умеренное время. И все, когда рассказывают как они делают поиск изображений по контенту, упоминают, что пользуют такие дескприпторы в каком-то виде, но каким образом хранят и проверяют, остается без подробного внимания (может вкраце скажут, что есть кластера, есть алгоритмы на деревьях по поиску совпадений). Ну еще это совсем небольшая часть проделываемых манипуляций.
habrahabr.ru/post/143667/ — Вон Яндекс отсеивает за 2 минуты дубликаты из коллекции в миллион изображений на ноутбуке.
И вариантов поиска изображений по признакам очень много, начиная от гистограмм и до мд5 хешей.
Это считай и есть дескрипторы: берется 16 блоков, по 4*4, вокруг точки и получают 8 чисел ориентиров. 16*8 = 128 чисел на точку.
Совпадение считают поиском ближайших точек.
И если будет 1000 точек, получается 128 000 чисел на картинку. Если картинок 1000, то хранить надо 128 млн чисел.
А проверить на совпадение 128 000 числа с первой картинки * 128 млн всего = 1,63*10^13 чтобы найти одну картинку полным перебором.
Тут вопрос как такое проделать в пределах одного небольшого сервера за умеренное время. И все, когда рассказывают как они делают поиск изображений по контенту, упоминают, что пользуют такие дескприпторы в каком-то виде, но каким образом хранят и проверяют, остается без подробного внимания (может вкраце скажут, что есть кластера, есть алгоритмы на деревьях по поиску совпадений). Ну еще это совсем небольшая часть проделываемых манипуляций.
habrahabr.ru/post/143667/ — Вон Яндекс отсеивает за 2 минуты дубликаты из коллекции в миллион изображений на ноутбуке.
И вариантов поиска изображений по признакам очень много, начиная от гистограмм и до мд5 хешей.
Как на счёт поворотов? Ну скажем на 11.5'?
В очень незначительных пределах. И такие хеши не годятся для проверки на такие геометрические преобразования. Возможно есть вариант проверки на последовательность хешей и каждый нарезок будет немного повернут, но в итоге совпадут с не повернутым вариантом.
А если как-нибудь нормализовать геометрию по локальным признакам (наверное даже после кластеризации), например, вписывать фигуру, задаваемую центроидами кластеров (или их крайними точками), в какую-нибудь заранее заданную фигуру (квадрат или треугольник), и хэшировать уже такие нормализованные изображения? Тогда по идее хэш будет инвариантен к масштабированию и поворотам. Правда, все-равно непонятно, как быть с кропами, когда отрезается часть точек кластера, и центр «съезжает».
-хэшировать уже такие нормализованные изображения
Примерно так сейчас я и делаю. В кластере нахожу минимальные и максимальные координаты, а потом смотрю и изменяю координаты так, чтобы были кратны расстоянию к центру кластера.
Это позволяет получать пропорциональные картинки и их легче сравнивать.
Думал что можно обойтись фиксированным размером вырезаемых картинок, но такое не годится. Думал может резать вокруг центра кластера как-то, тоже особо мало результатов. Даже проверял возможность сохранить отношения расстояний от центров кластеров. Т.е. пропорции расстояния, как примерно делатется в SIFT. Но так получается очень много чисел и их сложно сравнивать, чтобы получить адекватные результаты.
Ну и думал, что можно очистить вырезанные изображения и нарисовать там карту точек кластера, и уже делать хеш такой картинки. И еще много чего, но это все не работало.
На счет повороты, то тут они критичны, и если повернуть Лену на 180, то 39% только совпадет, pHash дает 39 расстояние.
Если на 90 градусов, то на 50% совпадет.
А вот масштабы тут не важны.
Примерно так сейчас я и делаю. В кластере нахожу минимальные и максимальные координаты, а потом смотрю и изменяю координаты так, чтобы были кратны расстоянию к центру кластера.
Это позволяет получать пропорциональные картинки и их легче сравнивать.
Думал что можно обойтись фиксированным размером вырезаемых картинок, но такое не годится. Думал может резать вокруг центра кластера как-то, тоже особо мало результатов. Даже проверял возможность сохранить отношения расстояний от центров кластеров. Т.е. пропорции расстояния, как примерно делатется в SIFT. Но так получается очень много чисел и их сложно сравнивать, чтобы получить адекватные результаты.
Ну и думал, что можно очистить вырезанные изображения и нарисовать там карту точек кластера, и уже делать хеш такой картинки. И еще много чего, но это все не работало.
На счет повороты, то тут они критичны, и если повернуть Лену на 180, то 39% только совпадет, pHash дает 39 расстояние.
Если на 90 градусов, то на 50% совпадет.
А вот масштабы тут не важны.
Спасибо за ответ. Про кратность расстояния в кластере из статьи я не понял, теперь вроде сообразил.
Про поворот я имел в виду, что все изображения (включая исходное) поворачиваются, чтобы вписаться в заранее заданную форму. Если вернуться к предложенной картинке, то грубо говоря, нужно уложить Лену горизонтально, головой, например, вправо, независимо от ее исходного положения, тем самым вписав в фиксированную геометрическую фигуру ее признаки (вы сами предложили этот пример) :).
Если фигура, в которую вписываются точки локальных признаков, — квадрат, то да, нужно будет делать 4 сравнения (а то и 8 для поддержки зеркального отражения картинки). Скорее всего количество сравнений можно уменьшить, договорившись, что центр масс всех вписанных точек должен оказаться, скажем, в первом квадранте квадрата.
Немного сумбурно описал, но надеюсь, сумел передать идею.
Про поворот я имел в виду, что все изображения (включая исходное) поворачиваются, чтобы вписаться в заранее заданную форму. Если вернуться к предложенной картинке, то грубо говоря, нужно уложить Лену горизонтально, головой, например, вправо, независимо от ее исходного положения, тем самым вписав в фиксированную геометрическую фигуру ее признаки (вы сами предложили этот пример) :).
Если фигура, в которую вписываются точки локальных признаков, — квадрат, то да, нужно будет делать 4 сравнения (а то и 8 для поддержки зеркального отражения картинки). Скорее всего количество сравнений можно уменьшить, договорившись, что центр масс всех вписанных точек должен оказаться, скажем, в первом квадранте квадрата.
Немного сумбурно описал, но надеюсь, сумел передать идею.
Решал около года назад подобную задачку, но попроще. Была файлопомойка(~10 000 000 файлов) с оригиналами и кропами(делали реальные люди), нужно было избавиться от кропаных файлов(ввиду прогресса стали слишком малы), но записать координаты кропа в sql базу.
Написал скриптик под opencv на c++ и использовал его из php. Просто выводит в консоль x, y, width и height
#include
#include
#include «opencv2/core/core.hpp»
#include «opencv2/features2d/features2d.hpp»
#include «opencv2/highgui/highgui.hpp»
#include «opencv2/calib3d/calib3d.hpp»
#include «opencv2/nonfree/features2d.hpp»
using namespace cv;
void readme();
/** function main */
int main( int argc, char** argv )
{
if( argc != 3 )
{ readme(); return -1; }
Mat img_object = imread( argv[1], CV_LOAD_IMAGE_GRAYSCALE );
Mat img_scene = imread( argv[2], CV_LOAD_IMAGE_GRAYSCALE );
if( !img_object.data || !img_scene.data )
{ std::cout max_dist ) max_dist = dist;
}
//-- Draw only «good» matches (i.e. whose distance is less than 3*min_dist )
std::vector good_matches;
for( int i = 0; i < descriptors_object.rows; i++ )
{ if( matches[i].distance < 3*min_dist )
{ good_matches.push_back( matches[i]); }
}
if (good_matches.size() == 0)
{
std::cout
Написал скриптик под opencv на c++ и использовал его из php. Просто выводит в консоль x, y, width и height
#include
#include
#include «opencv2/core/core.hpp»
#include «opencv2/features2d/features2d.hpp»
#include «opencv2/highgui/highgui.hpp»
#include «opencv2/calib3d/calib3d.hpp»
#include «opencv2/nonfree/features2d.hpp»
using namespace cv;
void readme();
/** function main */
int main( int argc, char** argv )
{
if( argc != 3 )
{ readme(); return -1; }
Mat img_object = imread( argv[1], CV_LOAD_IMAGE_GRAYSCALE );
Mat img_scene = imread( argv[2], CV_LOAD_IMAGE_GRAYSCALE );
if( !img_object.data || !img_scene.data )
{ std::cout max_dist ) max_dist = dist;
}
//-- Draw only «good» matches (i.e. whose distance is less than 3*min_dist )
std::vector good_matches;
for( int i = 0; i < descriptors_object.rows; i++ )
{ if( matches[i].distance < 3*min_dist )
{ good_matches.push_back( matches[i]); }
}
if (good_matches.size() == 0)
{
std::cout
Это была моя первая попытка. Просто использовать SURF и BFMatcher:
Сложность была в том, что каждый раз, при загрузке новой картинки, приходилось бы проходить так по базе (сохраненных точек и дескрипторов) и делать проверку на совпадение. Слишком было бы толсто. Думал, что есть возможность сделать легче.
cv = cv2.SURF( 400 )
kp1,desc1 = cv.detectAndCompute( img1, None )
kp2,desc2 = cv.detectAndCompute( img2, None )
matcher = cv2.BFMatcher( cv2.NORM_L2 )
matches = matcher.knnMatch( desc1, trainDescriptors = desc2, k = 2 )
pairs = filterMatches( kp1, kp2, matches )
Сложность была в том, что каждый раз, при загрузке новой картинки, приходилось бы проходить так по базе (сохраненных точек и дескрипторов) и делать проверку на совпадение. Слишком было бы толсто. Думал, что есть возможность сделать легче.
Характерно, что автор искал лицо.
Напомнило анекдот про поручика, где тот критикует голую девушку, ссылаясь, что что-то во взгляде не понравилось ;)
Напомнило анекдот про поручика, где тот критикует голую девушку, ссылаясь, что что-то во взгляде не понравилось ;)
Хорошая статья и титьки, всегда лучше чем просто хорошая статья!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск кропнутых дубликатов изображений с помощью перцептуальных хешей