0

На входе много изображений, а на выходе определяет дубликат среди этих многих изображений

3
  • ru.stackoverflow.com/q/445159/178988
    – Qwertiy
    5 мая 2016 в 23:23
  • @Qwertiy Уточните, что это за ссылка и как она относится к этому вопросу?
    – Kromster
    6 мая 2016 в 5:21
  • В вопросе недостаточно информации. Попиксельное совпадение или примерное? Насколкьо разные картинки должны определяться как дубликаты - размер, поворот, фрагменты, другие искажения?
    – Kromster
    6 мая 2016 в 5:28

3 ответа 3

4

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

Способ 1:

  1. Группируем картинки по размеру (в пикселях)
  2. Выбираем рандомные координаты пикселя и группируем картинки по его цвету
  3. Повторяем пункт 1 в каждой группе до получения достаточно мелких групп
  4. В мелких группах сравниваем картинки попарно попиксельно

Способ 2:

  1. Группируем картинки по размеру (в пикселях).
  2. Получаем из картинок массив rgba-пикселей
  3. Строим префиксное дерево (или как там оно называется), добавив в начало размеры
  4. Если последовательность заканчивается в том же листе, значит картинки совпадают
2
  • Не плохие варианты, рекомендую сделать пред сравнение. Эти алгоритмы будут хороши при должной реализации но все равно трудо затратные. Перед их запуском сравните картинки по хэш суммам хотя бы. 6 мая 2016 в 6:05
  • @Makarenko_I_V, мне не кажется, что подсчёт хэшей даст выигрыш. Или имеется в виду хэш файла? Тогда это не то, поскольку мои способы предполагают, что одинаковые картинки в разных форматах (или с разными метаданными) - это всё же дубликаты, если попиксельно они совпадают, а хеши файлов раскидают их в разные группы.
    – Qwertiy
    6 мая 2016 в 6:38
1

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

  1. Сжать все изображения до размера 16*16.
  2. Обесцветить полученные картинки до состояний пикселей 0 и 1.
  3. Найти расстояние Хемминга между образцом и всеми проверяемыми значениями. Поделить полученные значения на 256, вычесть их из единицы и умножить на сто — получите процент схожести.

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

1

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.