Есть способ быстро сравнить одно изображение со множеством других изображений?

Question

[Evgeny_A]

Здравствуйте!

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

def compareImage(file_to_compare, folder):

	# file_to_compare это путь до картинки, которую загрузил юзер
	# folder это папка в которой картинки с которыми нужно сравнить картинку юзера

	photos_in_folder = os.listdir(folder)

	if len(photos_in_folder) > 0:

		for image in photos_in_folder:

			other_image = str(image)

			if file_to_compare != other_image:

				if os.path.isfile(file_to_compare) and os.path.isfile(other_image):

					h1 = Image.open(file_to_compare).histogram()
					h2 = Image.open(other_image).histogram()

					result = math.sqrt(reduce(operator.add, map(lambda a,b: (a-b)**2, h1, h2))/len(h1))

					if result and result < 150:

						# Найден дубль
						return True

	else:

		logging.info('нет фотографий для сравнения. Пропускаем')

	# Картинка юзера уникальная
	return False

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

Вопрос — возможно ли сравнить одно изображение сразу с множеством других, чтобы это это было быстрее, чем сравнение по парам, при условиях что:

1. Сравнивать нужно именно содержимое изображений, а не их размер, хеш, адрес, вес и т.д
   
2. Каждый раз, когда юзер загружает картинку, мне нужно обновлять информацию об уже имеющихся на сервере картинок, поэтому строить, например, индекс раз в сутки нельзя, он будет не актуальным
   
3. Не могу себе позволить держать в оперативке уже имеющиеся на сервере картинке, так как их очень много, а оперативка ограничена (если например, исключить из цепочки медленную файловую систему)
   
4. Уже использую SSD накопитель и оптимизировать файловую систему мне кажется больше некуда
   

Буду благодарен за идеи или ссылки на реализации, где можно подглядеть принцип сравнения.

Answer 1

[Вадим Шаталов]

Самая дорогая операция тут - это Image.open(file_to_compare).histogram()
Для каждой загружаемой картинки высчитывай хеш и храни в базе, чтобы потом не пересчитывать дважды

Answer 2

[gh0sty]

Генерь hash и не парься. Он уникален и думаю можно найти быстрый генератор, а поиск подобных - быстрый. В hash-функцию можно засунуть любые стандартизированные, нормированные данные.