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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

Вы можете попробовать запустить 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 3

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

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

Я провел несколько экспериментов на ноутбуке с процессором Intel Core 2 Duo L7100, и 8-мегапиксельный JPEG занимает около 1 секунды для сжатия в формат PPM, затем еще 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 использует для поиска похожих изображений.