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

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

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

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

вы можете обменять хранение и точность путем увеличения или уменьшения к.

сортировка по одной числовой оценке будет неразрешимой для такого рода проблемы классификации. Если вы думаете об этом, это потребует изображения должны быть только в состоянии "изменить" вдоль одной оси, но это не так. Это зачем нужен вектор функции. В случае вейвлета Хаара его примерно там, где происходят самые резкие разрывы в изображении. Вы можете вычислить расстояние между изображениями попарно, но поскольку все, что у вас есть, - это метрика расстояния, линейный порядок не может выразить "треугольник" из 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 / документы / chum_bmvc08. pdf

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

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

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

Что делает быстрый запрос изображения с несколькими разрешениями, это разбивает изображение на 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 или что-то в этом роде. Очевидно, что это не хорошо, потому что красный вес чрезмерно.

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

---

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

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

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

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

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

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

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

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

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

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

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

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