Сравнение изображений - быстрый алгоритм

https://stackoverflow.com/questions/843972

20-08-2019
|

Вопрос

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

Например:Если вы хотите сократить объем хранения одного и того же изображения в сотни раз, вы можете сохранить одну его копию и предоставить на нее справочные ссылки.Когда вводится новое изображение, вы хотите сравнить его с существующим изображением, чтобы убедиться, что оно не является дубликатом...идеи?

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

Решение

Ниже представлены три подхода к решению этой проблемы (а есть и множество других).

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

Сопоставление ключевых точек

Лучше, чем выбрать 100 случайных точек, выбрать 100. важный точки.Определенные части изображения содержат больше информации, чем другие (особенно по краям и углам), и именно эти части вы захотите использовать для интеллектуального сопоставления изображений.Google "извлечение ключевых точек" и "сопоставление ключевых точек", и вы найдете довольно много научных статей на эту тему.В эти дни, Ключевые точки SIFT являются, пожалуй, самыми популярными, поскольку они могут сопоставлять изображения при разных масштабах, поворотах и освещении.Некоторые реализации SIFT можно найти здесь.

Одним из недостатков сопоставления ключевых точек является время работы наивной реализации:O(n^2m), где n — количество ключевых точек в каждом изображении, а m — количество изображений в базе данных.Некоторые умные алгоритмы могут быстрее находить ближайшее совпадение, например квадродеревья или разбиение двоичного пространства.

Альтернативное решение:Гистограммный метод

Другое менее надежное, но потенциально более быстрое решение — построить гистограммы признаков для каждого изображения и выбрать изображение, гистограмма которого ближе всего к гистограмме входного изображения.Я реализовал это, будучи студентом, и мы использовали три цветовые гистограммы (красную, зеленую и синюю) и две текстурные гистограммы: направление и масштаб.Подробности я расскажу ниже, но должен отметить, что это работало хорошо только для сопоставления изображений, ОЧЕНЬ похожих на изображения из базы данных.Перемасштабированные, повернутые или обесцвеченные изображения при использовании этого метода могут оказаться неудачными, но небольшие изменения, такие как обрезка, не нарушат алгоритм.

Вычислить цветовые гистограммы очень просто: просто выберите диапазон для сегментов гистограммы и для каждого диапазона подсчитайте количество пикселей с цветом в этом диапазоне.Например, рассмотрим «зеленую» гистограмму и предположим, что мы выбрали для нашей гистограммы 4 сегмента:0–63, 64–127, 128–191 и 192–255.Затем для каждого пикселя мы смотрим на зеленое значение и добавляем значение к соответствующему сегменту.Когда мы закончим подсчет, мы разделим общее количество каждого сегмента на количество пикселей во всем изображении, чтобы получить нормализованную гистограмму для зеленого канала.

Для гистограммы направления текстуры мы начали с обнаружения краев на изображении.Каждая точка края имеет вектор нормали, указывающий в направлении, перпендикулярном краю.Мы квантовали угол вектора нормали в один из 6 сегментов между 0 и PI (поскольку ребра имеют симметрию 180 градусов, мы преобразовали углы между -PI и 0 в диапазон между 0 и PI).После подсчета количества краевых точек в каждом направлении у нас есть ненормализованная гистограмма, представляющая направление текстуры, которую мы нормализовали, разделив каждый сегмент на общее количество краевых точек в изображении.

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

Теперь у вас есть 5 гистограмм для каждого изображения.Чтобы сравнить два изображения, вы берете абсолютное значение разницы между каждым сегментом гистограммы, а затем суммируете эти значения.Например, чтобы сравнить изображения A и B, мы должны вычислить

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1|

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

Третий вариант — ключевые точки + деревья решений

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

Обновлять:

Моя ошибка: статья Semantic Texton Forests посвящена не сопоставлению изображений, а скорее маркировке регионов.Оригинальная статья, в которой выполняется сопоставление, такова: Распознавание ключевых точек с использованием рандомизированных деревьев.Кроме того, приведенные ниже статьи продолжают развивать идеи и представляют современное состояние (ок.2010):

Быстрое распознавание ключевых точек с использованием случайных папоротников - быстрее и масштабируемее, чем Lepetit 06
~~КРАТКИЙ:Двоичные устойчивые независимые элементарные функции~~ - менее надежный, но очень быстрый. Я думаю, что цель здесь - сопоставление в реальном времени на смартфонах и других портативных устройствах.

Другие советы

Лучший метод, который я знаю, — это использовать Perceptual Hash.Кажется, есть хорошая реализация такого хеша с открытым исходным кодом, доступная по адресу:

http://phash.org/

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

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

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

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

Наверху самые быстрые алгоритмы;внизу самый медленный (хотя и более точный).Вы можете пропустить медленные, если хорошее совпадение найдено на более быстром уровне.

на основе хэша файла (md5, sha1 и т. д.) для точных дубликатов
перцепционное хеширование (phash) для масштабированных изображений
на основе функций (SIFT) для модифицированных изображений

У меня очень хорошие результаты с phash.Точность хорошая для масштабированных изображений.Это не подходит для (перцептивно) измененных изображений (обрезанных, повернутых, зеркальных и т. д.).Чтобы справиться со скоростью хеширования, мы должны использовать дисковый кеш/базу данных для хранения хэшей для стога сена.

Самое приятное в phash то, что как только вы создадите свою хеш-базу данных (которая для меня составляет около 1000 изображений в секунду), поиск может быть очень, очень быстрым, особенно если вы можете хранить всю хэш-базу данных в памяти.Это довольно практично, поскольку размер хеша составляет всего 8 байт.

Например, если у вас 1 миллион изображений, потребуется массив из 1 миллиона 64-битных хэш-значений (8 МБ).На некоторых процессорах это помещается в кэш L2/L3!На практике я видел сравнение Corei7 со скоростью более 1 Гигахамма в секунду, это всего лишь вопрос пропускной способности памяти процессора.База данных на 1 миллиард изображений практична на 64-битном процессоре (требуется 8 ГБ ОЗУ), а время поиска не будет превышать 1 секунды!

Для модифицированных/обрезанных изображений может показаться, что инвариантный к преобразованию детектор функций/ключевых точек, такой как SIFT, является подходящим вариантом.SIFT создаст хорошие ключевые точки, которые позволят обнаружить обрезку/поворот/зеркало и т. д.Однако сравнение дескрипторов происходит очень медленно по сравнению с расстоянием Хэмминга, используемым phash.Это серьезное ограничение.Необходимо выполнить множество сравнений, поскольку существует максимальное число сравнений дескриптора IxJxK для поиска одного изображения (I = количество изображений стога сена, J = целевые ключевые точки на изображение стога сена, K = целевые ключевые точки на изображение иглы).

Чтобы обойти проблему скорости, я попытался использовать фазирование вокруг каждой найденной ключевой точки, используя размер/радиус объекта для определения подпрямоугольника.Хитрость в том, чтобы сделать эту работу хорошей, заключается в увеличении/уменьшении радиуса для создания различных уровней субпрямоугольников (на изображении иглы).Обычно первый уровень (немасштабированный) соответствует, однако часто требуется еще несколько.Я не уверен на 100%, почему это работает, но могу предположить, что это позволяет использовать функции, которые слишком малы для работы phash (phash масштабирует изображения до 32x32).

Другая проблема заключается в том, что SIFT не будет оптимально распределять ключевые точки.Если на изображении есть участок с большим количеством краев, ключевые точки будут группироваться там, и вы не получите их в другой области.Я использую GridAdaptedFeatureDetector в OpenCV для улучшения распространения.Не знаю, какой размер сетки лучше, я использую небольшую сетку (1x3 или 3x1 в зависимости от ориентации изображения).

Вероятно, вы захотите масштабировать все изображения стога сена (и иглы) до меньшего размера перед обнаружением объекта (я использую 210 пикселей по максимальному размеру).Это уменьшит шум на изображении (всегда проблема для алгоритмов компьютерного зрения), а также сфокусирует детектор на более заметных деталях.

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

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

Изображение иголки может иметь меньше ключевых точек, чем изображения стога сена, и при этом получать хорошие результаты.Добавление большего количества не обязательно принесет вам огромную прибыль, например, при J=400 и K=40 мой показатель успеха составляет около 92%.При J=400 и K=400 процент попаданий возрастает только до 96%.

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

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

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

У меня есть идея, которая может сработать и, скорее всего, будет очень быстрой.Вы можете подготовить изображение, сказать, что разрешение 80x60 или сопоставимо, и преобразовать его в серую шкалу (после подгруппировки это будет быстрее).Обработайте оба изображения, которые хотите сравнить.Затем запустите нормализованную сумму квадратных различий между двумя изображениями (изображение запроса и каждое из DB) или даже лучшую нормализованную перекрестную корреляцию, что дает отклик ближе к 1, если оба изображения похожи.Затем, если изображения схожи, вы можете перейти к более сложным методам, чтобы убедиться, что это те же изображения.Очевидно, что этот алгоритм является линейным с точки зрения количества изображений в вашей базе данных, поэтому, хотя он будет очень быстро до 10000 изображений в секунду на современном оборудовании.Если вам нужна инвариантность для вращения, то для этого небольшого изображения может быть рассчитан доминирующий градиент, а затем вся система координат может быть повернута на каноническую ориентацию, хотя и будет медленнее.И нет, здесь нет никакой инвариантности к масштабу.

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

Я считаю, что уменьшение размера изображения почти до размера значка, скажем, 48x48, затем преобразование в оттенки серого, а затем учет разницы между пикселями или дельты, должно работать хорошо.Поскольку мы сравниваем изменение цвета пикселя, а не фактический цвет пикселя, не имеет значения, станет ли изображение немного светлее или темнее.Большие изменения будут иметь значение, поскольку пиксели, которые станут слишком светлыми/темными, будут потеряны.Вы можете применить это к одной строке или к любому количеству строк, чтобы повысить точность.В лучшем случае вам придется сделать 47x47=2209 вычитаний, чтобы сформировать сопоставимый Ключ.

Выбор 100 случайных точек может означать, что похожие (а иногда даже разные) изображения будут помечены как одинаковые, а это, как я полагаю, не то, что вам нужно.Хэши MD5 не будут работать, если изображения имеют разные форматы (png, jpeg и т. д.), разные размеры или разные метаданные.Уменьшение всех изображений до меньшего размера — хороший вариант, сравнение пикселей не должно занимать слишком много времени, если вы используете хорошую библиотеку изображений/быстрый язык и размер достаточно мал.

Вы можете попробовать сделать их крошечными, а затем, если они одинаковые, выполнить еще одно сравнение с большим размером - это может быть хорошее сочетание скорости и точности...

Если у вас большое количество изображений, просмотрите Фильтр Блума, который использует несколько хешей для получения вероятностного, но эффективного результата.Если количество изображений невелико, то криптографического хэша, такого как md5, должно быть достаточно.

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

Я хочу сказать, что я искал в Интернете повсюду, пытаясь найти идеальное решение.Я даже разработал собственный алгоритм обнаружения границ.
Я оценил скорость и точность нескольких моделей.Мои изображения с белым фоном очень хорошо работают с фазированием.Нравиться Редкалькс сказал: я рекомендую фаш или ахаш. НЕ используйте хеширование MD5 или любые другие криптографические хеши.Если только вам не нужны ТОЧНЫЕ совпадения изображений.Любое изменение размера или манипуляция, происходящая между изображениями, приведет к другому хешу.

Для phash/ahash проверьте это: хэш изображения

Я хотел расширить пост *redcalx*, опубликовав свой код и свою точность.

Что я делаю:

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

Вот некоторые из моих результатов:

item1  item2  totalaccuracy
desk1  desk2       3
desk2  phone1     22
chair1 desk1      17
phone1 chair1     34

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

Надеюсь это поможет!

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow