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

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

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

В оптимальном случае я ищу алгоритм, который будет давать каждому изображению оценку (например, целочисленную оценку, такую ​​как Среднее значение RGB), и я могу просто отсортировать по этой оценке. Одинаковые баллы или баллы рядом друг с другом являются возможными дубликатами.

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

Среднее значение RGB на изображение - отстой, есть ли что-то подобное?

Было проведено много исследований по поиску изображений и мерам сходства. Это непростая проблема. В общем, одного одного intбудет недостаточно, чтобы определить, очень ли похожи изображения. У вас будет высокий процент ложных срабатываний.

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

Если вы ищете что-то более простое, но определенно более специальное, в этом SO-вопросе есть несколько достойных идей.

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

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

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

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

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

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

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

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

Если вам нужна более высокая точность обнаружения, можно использовать алгоритмы minHash и tf-idf с вейвлетом Хаара (или гистограммой) для более надежного редактирования:

http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

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

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

Я реализовал для этого очень надежный алгоритм, который называется Fast Multiresolution Image Querying . Мой (древний, неподдерживаемый) код для этого: здесь .

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

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

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

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

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

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

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

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

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

Изображение "похоже" на то же изображение в перевернутом виде?

Бьюсь об заклад, вы можете найти множество «близких вызовов», разбив изображения на части 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. Самый высокий вес зеленый, затем красный, затем синий, чтобы соответствовать зрительной чувствительности человека.

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

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

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

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

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

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

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

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

Итак, если мы видим отношение общих визуальных слов двух изображений ко всем визуальным словам этих изображений, вы оцениваете сходство между изображениями. Есть много интересных статей. Одним из них является обнаружение почти повторяющихся изображений: minHash и tf-idf Weighting.

Например, используя расширение IMMI и IMMI, вы можете изучить множество различных способов измерения сходства между изображениями: http://spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension- для-Rapidminer-5

Определив некоторый порог и выбрав какой-либо метод, вы можете измерить сходство.