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

Question

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

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

Я пытаюсь найти «fingerprint» изображений, чтобы я мог быстро найти их.

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

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

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

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

Answer 1

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

TinEye обычно не найти похожие изображения (т.е. разные изображение с тем же предметом); он находит точные совпадения, включая те, которые были обрезаны, отредактированы или изменены.

Теперь, я сказал, я просто предполагаю, что вы знаете, о чем вы спрашиваете, и что вы действительно хотите найти все похожие изображения, а не только отредактированные точные копии.

Если вы хотите попробовать и углубиться в детали, я бы предложил поискать бумаги по Sivic, Zisserman и Nister, Stewenius. Идея, которую эти две статьи (а также довольно много других в последнее время) использовала, заключается в том, чтобы попытаться применить методы текстового поиска к базам данных изображений и выполнить поиск в базе данных изображений таким же образом, что Google будет искать его документ (веб-страница) база данных.

first документ, с которым я связался, является хорошей отправной точкой для такого подхода, так как он обращается главным образом к большому вопросу: Что такое «слова» на изображениях?. Методы поиска текста сосредоточены на словах и основывают их методы подобия на вычислениях, включая количество слов. Таким образом, успешное представление изображений в виде коллекций визуальных слов является первым шагом к применению методов текстового поиска для баз изображений.

Документ second затем расширяется по идее использования текстовых технологий, представляя более подходящую структуру поиска. Благодаря этому они обеспечивают более быструю обработку изображений и большие базы данных изображений.Они также предлагают, как создать дескриптор изображения на основе базовой структуры поиска.

Функции, используемые в качестве визуальных слов в обеих документах, должны удовлетворять вашим ограничениям по инвариантности, а вторая определенно должна иметь возможность работать с требуемым размером базы данных (возможно, даже работа с 1-й работой будет работать).

Наконец, я рекомендую искать новые документы от тех же авторов (я уверен, что Нистер сделал что-то новое, просто потому, что подход из связанной бумаги был достаточным для меня до сих пор), глядя на некоторые из их ссылок и просто в основном ищут документы, касающиеся Изображение на основе содержимого (индексирование и) (CBIR) - это очень популярный предмет прямо сейчас, поэтому должно быть много.