Метрика для поиска похожих изображений в базе данных
Существует множество различных алгоритмов для вычисления сходства между двумя изображениями, но я не могу найти ничего о том, как вы будете хранить эту информацию в базе данных, чтобы вы могли быстро найти похожие изображения.
Под "похожим" я подразумеваю точные дубликаты, которые были повернуты (с шагом 90 градусов), откорректированы по цвету и / или повторно сохранены (сжатие JPEG с потерями).
Я пытаюсь придумать " отпечатки пальцев" изображений, чтобы я мог быстро их найти.
Лучшее, что я придумала, - это создание гистограммы в оттенках серого. С 16 ящиками и 256 оттенками серого я могу легко создать 16-байтовый отпечаток. Это работает достаточно хорошо, но не так надежно, как хотелось бы.
Другое решение, которое я попробовал, состояло в том, чтобы изменить размеры изображений, повернуть их так, чтобы они все были одинаково ориентированы, настроить их в градациях серого, нормализовать гистограммы, а затем уменьшить их до 8x8 и уменьшить цвета до 16 оттенков серого. Хотя миниатюрные изображения были очень похожи, они обычно были на пиксель или два меньше, что означает, что точное соответствие не может работать.
Без точного соответствия я не верю, что существует какой-либо эффективный способ сгруппировать похожие фотографии (без сравнения каждой фотографии с каждой другой фотографией, т. Е. O(n^2)).
Итак, (1) Как я могу создать, я создаю отпечаток пальца / подпись, которая инвариантна к требованиям, упомянутым выше? Или (2) если это невозможно, какую другую метрику я могу использовать, чтобы по одному изображению я мог найти лучшие совпадения в базе данных из тысяч?
1 ответ
В вашем вопросе есть одна маленькая запутанная вещь: "отпечаток", на который вы ссылаетесь, явно не предназначен для поиска похожих изображений (цитата):
TinEye обычно не находит похожие изображения (т.е. другое изображение с тем же предметом); он находит точные совпадения, включая те, которые были обрезаны, отредактированы или изменены.
Тем не менее, я просто собираюсь предположить, что вы знаете, о чем вы спрашиваете, и что вы действительно хотите иметь возможность найти все похожие изображения, а не только отредактированные точные копии.
Если вы хотите попытаться вникнуть в подробности, я бы посоветовал поискать документы Сивича, Циссермана и Нистера, Стивениуса. Идея, которую использовали эти две статьи (как и многие другие в последнее время), состоит в том, чтобы попытаться применить методы текстового поиска к базам данных изображений и выполнить поиск в базе данных изображений таким же образом, как Google будет искать этот документ (веб-страницу).) база данных.
Первая статья, на которую я ссылаюсь, является хорошей отправной точкой для такого подхода, поскольку он затрагивает главным образом большой вопрос: каковы "слова" на изображениях?, Все методы текстового поиска сосредоточены на словах и основываются на показателях сходства на вычислениях, включая количество слов. Таким образом, успешное представление изображений в виде наборов визуальных слов является первым шагом к применению методов текстового поиска к базам данных изображений.
Затем вторая статья расширяет идею использования текстовых техник, представляя более подходящую структуру поиска. Благодаря этому они обеспечивают более быстрый поиск изображений и большие базы данных изображений. Они также предлагают, как создать дескриптор изображения на основе базовой структуры поиска.
Функции, используемые в качестве визуальных слов в обеих статьях, должны удовлетворять вашим ограничениям инвариантности, а вторая, безусловно, должна быть в состоянии работать с вашим необходимым размером базы данных (возможно, подойдет даже подход из первой статьи).
Наконец, я рекомендую поискать новые статьи от тех же авторов (я уверен, что Нистер сделал что-то новое, просто мне хватило подхода из связанной статьи до сих пор), поискать некоторые из их ссылок и просто вообще найти для работ, касающихся контентного поиска изображений (индексации и поиска) (CBIR) - сейчас это очень популярная тема, поэтому их должно быть много.