Обнаружение почти дублирующегося изображения [закрывается]

Существует библиотека C ("libphash" - http://phash.org/ ), которая вычисляет "перцепционный хэш" изображения и позволяет вам определять похожие изображения, сравнивая хеши (так что вам не нужно сравнивать каждое изображение напрямую с каждым другим изображением), но, к сожалению, это показалось мне не очень точным, когда я попробовал.

Одним из решений является выполнение сравнения RMS / RSS для каждой пары изображений, необходимых для выполнения пузырьковой сортировки. Во-вторых, вы можете выполнить FFT для каждого изображения и выполнить некоторое усреднение по оси, чтобы получить одно целое число для каждого изображения, которое вы будете использовать в качестве индекса для сортировки. Вы можете рассмотреть возможность проведения любого сравнения с версией оригинала с измененным размером (25%, 10%) в зависимости от того, насколько маленькую разницу вы решите игнорировать и сколько ускорения вам потребуется. Сообщите мне, если эти решения интересны, и мы можем обсудить их, или я могу предоставить образец кода.

Вы должны решить, что такое «подобное». Контраст? Оттенок?

Является ли изображение «похожим» на то же изображение в перевернутом виде?

Держу пари, вы можете найти много «близких вызовов», разбив изображения на части 4x4 и получив средний цвет для каждой ячейки сетки . У вас будет шестнадцать баллов за изображение. Чтобы судить о сходстве, вы должны просто сложить сумму квадратов различий между изображениями.

Я не думаю, что один хэш имеет смысл, если только он не противоречит одной концепции, такой как оттенок, яркость или контраст.

Вот пример ваша идея:

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

Прежде всего, я собираюсь предположить, что это десятичные числа R * (2 ^ 16) + G * (2 ^ 8) + B или что-то в этом роде. Очевидно, это бесполезно, потому что красный имеет чрезмерный вес.

Было бы лучше перейти в пространство HSV . Вы можете распределить биты HSV из в хэш, или вы можете просто установить H, S или V индивидуально, или у вас может быть три хэша на изображение.

---

Еще одна вещь. Если вы установите вес R, G и B. Наибольший вес будет зеленым, затем красным, а затем синим, чтобы соответствовать зрительной чувствительности человека.

Я предположил, что другое программное обеспечение для поиска дублированных изображений выполняет БПФ на изображениях и сохраняет значения различных частот в виде векторов:

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

, а затем вы можете сравнить два изображения на равенство , вычислив расстояние между весовыми векторами двух изображений:

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

Картинка имеет множество особенностей, поэтому, если вы не ограничитесь одним, например средней яркостью, вы имеете дело с n-мерным проблемным пространством.

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

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

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

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

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

Я реализовал для этого очень надежный алгоритм, который называется Быстрый запрос изображений с разным разрешением . Мой (древний, неподдерживаемый) код для этого здесь .

Функция Fast Multiresolution Image Querying разделяет изображение на 3 части на основе цветового пространства YIQ (лучше для сопоставления различий, чем RGB). Затем изображение по существу сжимается с использованием вейвлет-алгоритма до тех пор, пока не станут доступны только наиболее заметные особенности каждого цветового пространства. Эти точки хранятся в структуре данных. Изображения запроса проходят один и тот же процесс, и основные элементы изображения запроса сравниваются с таковыми в сохраненной базе данных. Чем больше совпадений, тем больше вероятность, что изображения похожи.

Алгоритм часто используется для функции «запрос за эскизом». Мое программное обеспечение позволяло вводить изображения запросов только через URL-адрес, поэтому пользовательского интерфейса не было. Однако я обнаружил, что он отлично работает для сопоставления миниатюр с большой версией этого изображения.

Намного более впечатляющим, чем мое программное обеспечение, является retrievr , которое позволяет вам опробовать алгоритм FMIQ, используя изображения Flickr в качестве источника. . Очень круто! Попробуйте сделать это с помощью наброска или исходного изображения, и вы увидите, насколько хорошо это работает.

В эпоху веб-сервисов вы могли бы попробовать http://tineye.com

Я бы порекомендовал отказаться от простого использования гистограммы RGB.

Более качественный анализ вашего изображения может быть получен, если вы возьмете двумерный вейвлет Хаара изображения (это намного проще, чем кажется, это всего лишь много усреднений и несколько квадратных корней, используемых для взвешивания ваших коэффициентов) и просто сохраните k наибольших взвешенных коэффициентов в вейвлете как разреженный вектор, нормализовать его и сохранить, чтобы уменьшить его размер. Вам следует изменить масштаб RG и B с использованием перцепционных весов заранее, по крайней мере, или я бы рекомендовал переключиться на YIQ (или YCoCg, чтобы избежать шума квантования), чтобы вы могли сэмплировать информацию о цветности с меньшей важностью.

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

Вы можете найти компромисс между хранением и точностью, увеличивая или уменьшая k.

Сортировка по одной числовой оценке будет трудноразрешимым для такого рода проблем классификации. Если подумать, это потребует, чтобы изображения могли «изменяться» только вдоль одной оси, но это не так. Вот почему вам нужен вектор функций. В случае вейвлета Хаара это примерно то место, где возникают самые резкие разрывы в изображении. Вы можете вычислить расстояние между изображениями попарно, но, поскольку все, что у вас есть, это метрика расстояния, линейное упорядочение не может выразить «треугольник». из 3 изображений, которые все одинаково удалены. (т.е. представьте себе изображение, которое полностью зеленое, изображение, которое полностью является красным, и изображение, которое полностью синее.)

Это означает, что любое реальное решение вашей проблемы потребует O (n ^ 2) операций в числе изображений, которые у вас есть. В то время как, если бы можно было линеаризовать меру, вы могли бы потребовать только O (n log n) или O (n), если мера подходила, скажем, для сортировки по основанию. Тем не менее, вам не нужно тратить O (n ^ 2), поскольку на практике вам не нужно просеивать весь набор, вам просто нужно найти то, что ближе, чем некоторый порог. Таким образом, применяя один из нескольких методов для разделения вашего разреженного векторного пространства, вы можете получить гораздо более быструю асимптотику для «нахождения k изображений, которые более похожи, чем заданный порог». основан на извлечении дополнительных функций из вейвлетов для поиска повернутых или масштабированных участков изображений и т. д., но это, вероятно, выходит за рамки объема работы, которую вы хотели бы выполнить.

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

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

Итак, если мы увидим о соотношении общих визуальных слов двух изображений ко всем визуальным словам этих изображений, которые вы оцениваете сходство между изображениями. Есть много интересных статей. Одним из них является недалеко от дубликата обнаружения изображения: Minhash и TF-IDF Waiting

Вопрос Хороший способ идентифицировать похожие изображения? , кажется, дает ответ на ваш вопрос.