Самый быстрый способ вычисления «визуальной» контрольной суммы изображения

Question

Я хочу создать систему идентификации для каталогизации изображений.Я не могу использовать md5(), так как это изменится, если я изменю теги EXIF ​​​​изображения.

В настоящее время я использую контрольную сумму SHA1, вычисленную imagemagick.Он работает отлично, но очень, очень медленно на больших изображениях (~ 15 секунд на четырехъядерном процессоре Xeon для 21-мегапиксельного JPG).

Существуют ли другие «визуальные» методы однозначной идентификации изображения, которые были бы быстрее?

Answer 1

Вы можете попробовать запустить MD5 с реальными растровыми данными вместо файла JPEG.Я тестировал на своей машине (также четырехъядерный процессор Xeon), и следующее изображение выполняется примерно за 900 мс на 23-мегапиксельном изображении.

uint32_t width  = MagickGetImageWidth(imageWand);
uint32_t height = MagickGetImageHeight(imageWand);

uint8_t *imageData = malloc(width * height * 3);

MagickExportImagePixels(imageWand,
   0, 0, width, height, "RGB", CharPixel, imageData);

unsigned char *imageDigest = MD5(imageData, width * height * 3, NULL);

free(imageData);

Answer 2

что вы подразумеваете под «визуальной контрольной суммой»?упомянутые вами алгоритмы (md5/sha/crc) работают на основе байтов, но не учитывают визуальную информацию изображения.Если вы конвертируете одно из изображений в JPEG, в двух файлах будет одно и то же изображение, но с совершенно разными контрольными суммами md5/sha/crc.

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

Если все ваши файлы изображений получены непосредственно с камеры, это еще лучше:вы можете извлечь предварительно созданную миниатюру exif с помощью exiv2 (обычно всего несколько килобайт) и вычислить ее контрольную сумму.

О подходе уменьшения масштаба:Также имейте в виду тот факт, что ImageMagick может изменить свои алгоритмы масштабирования в будущем, что приведет к аннулированию ваших контрольных сумм (тогда изменится структура байтов уменьшенных версий).

Answer 3

Как заметил Тодд Янделл, MD5, вероятно, достаточно быстр.Если нет, вы можете получить что-то еще быстрее, используя 32-битную или 64-битную версию. КПР для вашей контрольной суммы.Основное отличие состоит в том, что любой может создать новое изображение с тем же CRC;это очень легко подделать.Подделать контрольную сумму MD5 довольно сложно.Небольшое отличие состоит в том, что CRC имеет гораздо меньше битов, но если у вас не очень большое количество изображений, коллизия все равно маловероятна.

exiftool утверждает, что может извлечь двоичное изображение из файла JPEG, чтобы вы могли вычислить контрольную сумму без распаковки, но на странице руководства я не могу понять, как это сделать.

Я провел несколько экспериментов на ноутбуке с процессором Intel Core 2 Duo L7100, и для сжатия 8-мегапиксельного JPEG в формат PPM требуется около 1 секунды, а затем еще 1 секунда для вычисления контрольной суммы.Время контрольной суммы не сильно отличалось при использовании md5sum, sum, и sha1sum.Поэтому лучше всего найти способ извлечь двоичные данные без их распаковки.

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

djpeg -scale 1/8 big.jpg | /usr/bin/sha1sum   # 0.70s
djpeg            big.jpg | /usr/bin/sha1sum   # 2.15s

Answer 4

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