Метрика для поиска похожих изображений в базе данных

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

Под «похожими» я подразумеваю точные дубликаты, которые были повернуты (с шагом 90 градусов ), скорректированы цвета -и/или повторно -сохранены (сжатие jpeg с потерями ).

Я пытаюсь придумать «отпечатки пальцев » изображений, чтобы я мог их быстро найти.

Лучшее, что я пока придумал, это создать гистограмму в градациях серого . Имея 16 бинов и 256 оттенков серого, я могу легко создать 16 -байтовый отпечаток. Это работает достаточно хорошо, но не так надежно, как хотелось бы.

Другим решением, которое я попробовал, было изменить размер изображений, повернуть их , чтобы все они были ориентированы одинаково, оттенить их серым, нормализовать гистограммы, а затем уменьшить их примерно до 8x8 и уменьшить цвета до 16 оттенков серого. Хотя миниатюрные изображения были очень похожи, они обычно отличались на один или два пикселя, а это означает, что точное совпадение не может работать.

Без точного -сопоставления я не верю, что существует какой-либо эффективный способ сгруппировать похожие фотографии (без сравнения каждой фотографии с каждой другой фотографией, то есть O (n^2 )).

Итак, (1 )Как я могу создать отпечаток пальца/подпись, инвариантный к упомянутым выше требованиям? Или, (2 ), если это невозможно, какую другую метрику я могу использовать, чтобы при наличии одного изображения я мог найти его лучшие совпадения в базе данных из тысяч?