Вопрос по image-processing, cbir, sorting, image – Обнаружение почти дублированного изображения [закрыто]

90

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

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

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

<code>0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994 
</code>

RGB Average за изображение отстой, есть что-то похожее?

В настоящее время это одна из самых больших нерешенных проблем в области компьютерных наук. Удачи, приятель. john ktejik
@ Неизвестный. Если вы не удовлетворены каким-либо из текущих ответов, не могли бы вы дать нам дополнительные рекомендации? Мы сделали все возможное, чтобы ответить на ваш вопрос, но без какой-либо обратной связи мы вряд ли найдем что-то лучшее. Naaff
Как сделать «дубликаты»? отличаются? например Будут ли это изображения одного и того же места с разной позой / смещением? Вы, кажется, хотите что-то, что O (nlog (n)) с количеством изображений. Кто-нибудь знает возможно ли это? Кажется, что это может быть .. Justin Scheiner
Ключевой вопрос, думая о том, что вы написали, и о некоторых ответах на связанный вопрос, на которые указал Наафф, вы можете более четко определить, что такое «сходство»; средства. Будет ли изображение, которое идентично, но со смещением в пять пикселей, быть "похожим"? Визуально да ... но для алгоритма ... возможно, нет, если вы не подумали об этом и не учли его. Можете ли вы предоставить более подробную информацию? Будут ли дубликаты точными или просто "близкими"? Вы смотрите на сканы, где они могут отличаться небольшим углом? Как насчет интенсивности? Естьlot переменных здесь ... Beska

Ваш Ответ

12   ответов
4

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

Кажется, код, лежащий в основе tineye, в точности соответствует тому, что задает задающий вопрос, но я не считаю его веб-службой очень полезным, поскольку нет (очевидного) способа дать ему два изображения и задать вопрос. это одно и то же? - второе изображение должно быть на веб-странице и проиндексировано tineye
Может быть, предоставляют API для бизнес-пользователей? С ними нужно связаться по этому поводу.
49

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

Лучший обзор вашего изображения может быть получен, если вы возьмете 2-мерный вейвлет Хаара изображения (это намного проще, чем кажется, просто много усреднения и некоторые квадратные корни, используемые для взвешивания ваших коэффициентов) и просто сохраните k взвешенные коэффициенты в вейвлете как разреженный вектор, нормализуйте его и сохраните, чтобы уменьшить его размер. Вы должны перемасштабировать R G и 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

Похоже, вы косвенно описываете kd-деревья и тому подобное для поиска в пространстве потенциальных кандидатов. Возможно, стоит отметить это.
Ну, причина, по которой я не указал технику, выходящую за рамки смутного намека, состоит в том, что kd-деревья хорошо работают, когда в вашем пространстве относительно небольшое количество измерений. Здесь вы, вероятно, имеете ~ 128 или более измерений, которые малонаселены. Поскольку они редки, большинство значений будут равны нулю, поэтому обход по всем измерениям для разбиения в стиле kd практически бесполезен. По той же причине R-деревья ломаются, оставляя, скорее всего, вашу лучшую ставку: X-деревья. К сожалению, они также близки к пределу производительности, когда сталкиваются с таким количеством измерений.
"Вы должны перемасштабировать R G и B, по крайней мере, заранее, используя веса восприятия, или я рекомендую переключиться на YIQ (или YCoCg, чтобы избежать шума квантования), чтобы можно было выбирать информацию о цвете с пониженной важностью. - а что тогда? Делать вейвлет только для Y или для всех каналов? Если сделать для всех каналов - как измерить сходство изображений с несколькими каналами? добавить точечные продукты каждого канала и учесть это как меру сходства или должно быть какое-то взвешенное добавление?
& Quot; и просто сохраните k наибольших взвешенных коэффициентов в вейвлете в качестве разреженного вектора, & quot; - сохранить за ряд или за весь вейвлет?
8

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

5

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

Является ли изображение "похожим"? к той же картине в обратном порядке?

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

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

Вот ваша идея:

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

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

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

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

1

В большинстве современных подходов к обнаружению близких к дублированию изображений используются интересные точки обнаружения и дескрипторы, описывающие области вокруг таких точек. ЧастоПРОСЕЯТЬ используется. Затем вы можете составить дескрипторы и использовать кластеры в качестве визуального словарного запаса.

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

1

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

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

1

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

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

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

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

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

эта статья 2004 года, не уверен, что это все еще лучший ответ?
15

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

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

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

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

Я сомневаюсь, что это будет работать очень хорошо для этого. Возможно, вы захотите закодировать изображения для каждого поворота, чтобы максимизировать соответствующие совпадения.
Может ли он все еще распознавать повернутые изображения?
10

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

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

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

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

Это спорный вопрос, но вы МОЖЕТЕ использовать одно целое число для представления комбинации любого числа признаков, если, например, функция x = 2 и функция y = 3, функция z = 5 и функция aa = 7, и так далее тогда сила, на которую эта первичная база была поднята в факторизованной форме единственного целого числа, будет значением признака для этого конкретного изображения. Опять же, спорный вопрос, потому что размер числа будет абсурдным. Хотя этот размер можно еще уменьшить ... мы просто говорим о структурированных данных.
Правда. Но реальная цель состоит в том, чтобы расположить числа так, чтобы похожие изображения находились рядом друг с другом в численном отношении. Несмотря на то, что я сказал выше, это возможно. Короче говоря, вы можете решить задачу Traveling Salesperson, чтобы найти минимальный (или почти минимальный) путь по изображениям в n-мерном пространстве (где n - это число функций, которые вы хотите использовать для сравнения изображений). Но это дорого.
1

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

БПФ предоставляет вам только информацию о цвете и никакой информации о положении. Изменение размера игнорирует все элементы ниже заданного размера независимо от влияния на полученное изображение. Серое изображение и шахматная доска могут быть идентичными по этой мере. Вейвлет-подход (Daubechies, Haar и т. Д.) Имеет преимущества предоставления информации как о положении, так и о цвете, компенсируя соотношение информации о положении и цвете в каждой точке данных.
Нет, БПФ изображения содержит всю пространственную информацию оригинала. Вы можете восстановить оригинал из БПФ.homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm   Однако гистограмма, о которой вы могли подумать, не имеет.
2

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

Похожие вопросы