Мне нужно получить список дубликатов картинок в папке с миллионом файлов. Хочу это сделать путем создания ID для каждой картинки, а потом сравнивать по этому ID. Одинаковые картинки но с разными разрешениями также должны считаться дубликатами. Какие варианты предложите?

Это сообщение отредактировал(а) DoZENT - 28.5.2010, 10:06

Вместо ИД, можно взять среднее значение, яркости

esperanto, пробовал не по яркости, а нахождением среднего цвета - все черные картинки считаются одинаковыми

Все черные картинки и есть одинаковые разве нет?

esperanto, нет, есть картинки с черным фоном, который составляет 80% изображения, а в центре - изображены разные объекты

В любом случае это произойдет.

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

Если ИД это одно, число ты делаем редукцию в одномерное пространство. И тем более множество "похожих" перейдут в одну картинку.

Вместо пространства размерностью 1, можно например взять размерность 9. - Разделить картинку на 9 равных прямоугольников и для каждого посчитать средее.

-------------------------

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

Но ВСЕГДА будут разные изображения,  которые будут трактоваться как одинаковое, ибо мы переходим в пространство с меньшей размерностью

DoZENT, можно в качестве id хранить всю картинку - большое число. Только в этом случае не произойдёт потери информации.э

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

Добавлено через 5 минут и 21 секунду
можно так,

1. использовать маленькую характеристику (допустим средний цвет), для получения списков картинок подозрительных на одинаковость.
2. проверить каждый список картинок, подозрительных на одинаковость, на реальную одинаковость

Миллион это так мало. Для хранения миллиона надо всего 2.5 байта. На самом деле что бы сравнить картинки надо пройтись по всем пикселам только этот метод дает хорошее качество сравнения. Но ускорить сравнение мы можем для этого надо уменьшить число параметров по которым будем сравнивать. В принципе уменьшение подгонка картинке под 64x64 дает хороший результат. Так как еще пикселы могут отличаться незначительно, то  берем интенсивность пикселя и отбрасываем младшие 4 бита. И того имеем 1388 байта.  Так как 1388 на 1 000 000 = 1гбайт это много то предлагается взять от этих байт простой хэш 4 байтовй к примеру CRC и его использовать для сравнения.

Остальное додумай сам.

Добавлено через 3 минуты и 52 секунды
Брать среднее арифметическое, не есть правильное. Фактически при съемки одного объекта днем и ночью вы получити разные характеристики. Фактически тут надо отталкиваться от восприятия человека.

Это сообщение отредактировал(а) Pavia - 28.5.2010, 18:03

Вообще-то в условии не сказано, что изображение одного объекта днём и ночью это одно и то же изображение. 

Могу предложить такой алгоритм. Не знаю насколько он будет эффективно искать одинаковые, но думаю будет.

Нужно найти среднее взвешенное не яркостей пикселей а их координат. Но координаты умножать на коэфициент яркости. То есть:

AVGX = Сумма(i*(ярк[i,j]/max_ярк) )/Кол-во_пикс
AVGY = Сумма(j*(ярк[i,j]/max_ярк) )/Кол-во_пикс

тут max_ярк = 240 (в соответствии с цветовой моделью HLS)
      Кол-во_пикс = ширина * высота
       ярк[i,j] = яркость пикселя с координатами i, j по цветовой модели HLS

Вот, в результате вы получите две координаты в пространстве данной картинки. Если вы их разделите на ширину и высоту, то получите координаты в относительных единица (от 0 до 1). Таким образом для каждой картинки нужно хранить два числа Х и Y, которые вы посчитали. А при сравнении искать расстояние между этими координатами и если оно меньше заданного лимита, считайте, что картинки одинаковые.

Почему вы так думаете? 

DoZENT, в качестве ИДа для картинки выберите CRC32. Если ЦРЦшные коды всё же будут у некоторых картинок совпадать, можно добавить дополнительный код (например, контрольную сумму Флетчера).
Если форматы сжатия без потерь (гиф, пнг, тифф, бмп,...) и каждый раз палитра одинаковой глубины - то всё будет ОК. Ну и, если разные разрешения (и разные форматы сжатия) - то ИДы надо, естественно, считать для "разжатых" в память картинок. А вот если глубина палитры варьируется и используется сжатие с потерями (жпег, например) - то никакой расчет хэшей для картинок (и последующее определение эквивалентности картинок через равенство хэш-кодов) не подойдет, надо будет собирать какой-то эмпирический алгоритм (сначала сравниваем размеры картинок, потом, если размеры совпали, что-то другое, и т.д. до тех пор, пока не решим, одинаковые ли картинки или всё-таки разные).

Плохая идея.

Ваша идея:



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

Вы заблуждаетесь.

Чем же СРС лучше чем среднее?