Поиск совпадений между высоким качеством и низким качеством, пиксельными изображениями - возможно ли это? Как?

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

К сожалению, диалоги ужасающего качества содержат важные сопоставления с другой информацией.

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

Можно ли в любом случае автоматизировать этот процесс? Ниже приведен пример двух диалоговых окон (случайно удаленных из изображений Google):

Good quality image

Bad Quality image

Итак, я в настоящее время пытаюсь написать программу на С#, чтобы вытащить эти фотографии из базы данных, прокрутить их, найти те, которые имеют общие фигуры, и вернуть их идентификаторы. Какие у меня лучшие варианты?

+39
источник поделиться
18 ответов

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

badness := 0.0
For x, y over the entire image:
  r, g, b := color at x,y in image 1
  R, G, B := color at x,y in image 2
  badness += (r-R)*(r-R) + (g-G)*(g-G) + (b-B)*(b-B)
badness /= (image width) * (image height)

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


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

Идея состоит в создании четырехъядерного дерева где каждый node представляет средние значения RGB региона, который node представляет. Таким образом, изображение 4x4 будет иметь корень node со значениями RGB, равными среднему значению RGB изображения, его дети будут иметь значения RGB, представляющие среднее значение RGB для их соответствующих областей 2x2, а их дети будут представлять отдельные пиксели. (На практике лучше не углубляться, чем область размером около 16x16, в этот момент вам нужно просто начать сравнивать отдельные пиксели.)

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

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

Если пороговый тест проходит на изображении nxn, просто опустите на следующий уровень вниз и сравните его, как это было изображение 2nx2n. Как только вы получите достаточно низкий уровень, сравните отдельные пиксели. В зависимости от вашего корпуса изображений это может позволить вам пропустить множество сравнений.

+29
источник

Я бы лично пошел на алгоритм хэширования изображений.

Цель хэширования изображения заключается в преобразовании содержимого изображения в последовательность признаков, чтобы получить сжатое представление. Эта последовательность признаков (т.е. Вектор бит) должна быть достаточно короткой для быстрого согласования и сохранения различимых признаков для измерения подобия. [/P >

Существует несколько алгоритмов, которые свободно доступны через сообщества с открытым исходным кодом.

Простой пример можно найти в в этой статье, где д-р Нил Кроветц показывает, как алгоритм Average Hash работы:

  • Уменьшить размер. Самый быстрый способ удаления высоких частот и деталей - уменьшить изображение. В этом случае сжимайте его до 8x8, чтобы было 64 общих пикселя. Не беспокойтесь, сохраняя соотношение сторон, просто сокрушите его, чтобы он соответствовал квадрату 8x8. Таким образом, хеш будет соответствовать любому изменению изображения независимо от масштаба или соотношения сторон.
  • Уменьшить цвет. Крошечное изображение 8x8 преобразуется в оттенки серого. Это изменяет хэш от 64 пикселей (64 красных, 64 зеленых и 64 синий) до 64 общих цветов.
  • Средний цвет. Вычислите среднее значение 64 цветов.
  • Вычислить биты. Это интересная часть. Каждый бит просто устанавливается в зависимости от того, находится ли значение цвета выше или ниже среднего.
  • Построить хеш. Установите 64 бита в 64-битное целое число. Порядок не имеет значения, до тех пор, пока вы согласны. (Я устанавливаю биты слева направо, сверху вниз, используя big-endian.)

Дэвид Оффедал написал приложение командной строки С# которые могут классифицировать и сравнивать изображения с использованием алгоритма Average Hash. (Я тестировал его реализацию с вашими образцами изображений, и я получил сходство 98,4%).

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

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


Edit

Вы можете найти простой пример здесь (он включает тестовый набор из 40 изображений и получает оценку 40/40).

+14
источник

Коммерческий TinEye API - действительно хороший вариант.

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

ps здесь, где те две случайные фотографии, которые вы вытащили из google, пришли из: http://www.tineye.com/search/1ec9ebbf1b5b3b81cb52a7e8dbf42cb63126b4ea/

+6
источник

Здесь тема обсуждает сходство изображений с алгоритмами, уже реализованными в OpenCV библиотека. У вас не должно возникнуть проблемы с импортированием низкоуровневых функций в ваше приложение С#.

+5
источник

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

script для проверки пары для сходства будет около 10 строк следующим образом:

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

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

+4
источник

Я бы сделал что-то вроде этого:

  • Если вы уже знаете, как размытые изображения были размыты, примените ту же функцию к изображениям высокого качества перед сравнением.

    • Затем сравните изображения с использованием наименьших квадратов, как было предложено выше.
    • Самое низкое значение должно дать вам совпадение. В идеале вы получите 0, если оба изображения идентичны.
    • Чтобы ускорить работу, вы можете выполнить большинство сравнений с изображениями с пониженной дискретизацией, а затем уточнить выбранную подвыборку изображений
  • Если вы не знаете, попробуйте различные возможные функции (сжатие JPEG, понижающая дискретизация,...) и повторите

+2
источник

Вы можете попробовать Content-Based Image Retrieval (CBIR).

Скажем прямо:

  • Для каждого изображения в базе данных создайте отпечаток с помощью Преобразование Фурье
  • Загрузите исходное изображение, сделайте отпечаток изображение
  • Вычислить евклидово расстояние между источником и всем изображения в базе данных
  • Сортировка результатов
+2
источник

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

  • Примените алгоритм Хеширования изображений, предложенный @Paolo Morreti, ко всем изображениям
  • Для каждого изображения в одном наборе найдите подмножество изображений с хешем ближе, чем заданное расстояние
  • В этом сокращенном пространстве поиска теперь можно применить дорогостоящие методы сопоставления, предложенные @Running Wild или @Raskolnikov... лучший выигрыш.
+2
источник

IMHO, лучшее решение - размыть оба изображения, а затем использовать некоторую меру подобия (корреляция/взаимная информация и т.д.), чтобы получить выбор K (K = 5 может быть?).

+1
источник

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

ShapeContext построен для этих точных вещей (сравнение изображений на основе взаимных форм)

Ссылки на реализацию ShapeContext: Оригинальная публикация Goot ppt по теме Страница CodeProject о ShapeContext

* Возможно, вам потребуется попробовать несколько методов выделения контуров, таких как пороговые значения или преобразование Фурье, или взглянуть на эту страницу CodeProject об извлечении контуров

Удачи.

+1
источник

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

Поэтому я рекомендую использовать метрику разности пикселей, только если у вас есть простейшая форма проблемы (изображения одинаковы во всех характеристиках, но качество отличается, и, кстати, почему качество отличается? jpeg-артефакты или просто перемасштабировать?), в противном случае Я рекомендую использовать нормированную кросс-корреляцию, это более стабильная метрика. Вы можете сделать это с помощью FFTW или с OpenCV.

+1
источник

Если плохое качество является результатом низкого разрешения, то:

  • масштабировать высокое качество изображения до низкого качества изображения (или масштабировать оба до равного низкого разрешения)
  • сравнить каждый пиксельный цвет для поиска ближайшего соответствия

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

+1
источник

Вы можете попробовать алгоритм сопоставления блоков, хотя я не уверен в его точной эффективности против вашей конкретной проблемы - http://scien.stanford.edu/pages/labsite/2001/ee368/projects2001/dropbox/project17/block.html - http://www.aforgenet.com/framework/docs/html/05d0ab7d-a1ae-7ea5-9f7b-a966c7824669.htm

Даже если это не сработает, вы все равно должны проверить библиотеку Aforge.net. Здесь есть несколько инструментов (включая блокировку блоков), которые могут помочь вам в этом процессе - http://www.aforgenet.com/

0
источник

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

0
источник

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

Справочник PSNR

Ваш код должен выглядеть так:

sum = 0.0
for(imageHeight){
  for(imageWidth){
    errorR = firstImage(r,x,y) - secondImage(r,x,y)
    errorG = firstImage(g,x,y) - secondImage(g,x,y)
    errorB = firstImage(b,x,y) - secondImage(b,x,y)
    totalError = square(errorR) + square(errorG) + square(errorB)
  }
  sum += totalError
}
meanSquaredError = (sum / (imageHeight * imageWidth)) / 3
0
источник

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

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

Согласование изображений может использовать много ресурсов, если у вас много изображений. Может быть, многопроходный подход - хорошая идея? Например: Передача 1: использовать простые измерения, такие как соотношение сторон к изображениям группы (поля ширины и высоты в db?) (Вычислительно дешево) Передача 2: совпадение или группировка по гистограмме для 1-го канала (или всех каналов) (относительно дешево)

Я также рекомендую OpenCV. Вы можете использовать его с c, С++ и Python (и вскоре Java).

0
источник

Просто вслух:

Если вы используете два изображения, которые следует сравнивать в виде слоев и объединять их (вычесть один из другого), вы получаете новое изображение (некоторые программы рисования могут быть написаны сценарием для пакетного преобразования, или вы можете использовать графический процессор, написав крошечная программа DirectX или OpenGL)

Затем вам нужно будет получить яркость полученного изображения; чем темнее, тем лучше матч.

0
источник

Вы пробовали методы контура/порога в сочетании со средним окном ходьбы (для значений RGB)?

0
источник

Посмотрите другие вопросы по меткам или Задайте вопрос