Алгоритм сравнения изображений - PullRequest
42 голосов
/ 30 ноября 2009

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

Есть предложения по улучшению алгоритма?

Кстати, я говорю о том, чтобы сравнить тысячи изображений ...

Edit: Вот пример моих снимков (микроскопический):

im1:

enter image description here

im2:

enter image description here

im3:

enter image description here

im1 и im2 одинаковы, но немного смещены / вырезаны, im3 должны быть распознаны как совершенно разные ...

Edit: Проблема решена с предложениями Питера Хансена! Работает очень хорошо! Спасибо за все ответы! Некоторые результаты можно найти здесь http://labtools.ipk -gatersleben.de / изображение% 20comparison / изображение% 20comparision.pdf

Ответы [ 9 ]

37 голосов
/ 30 ноября 2009

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

Там также есть ссылки на более ранние вопросы, которые содержат еще больше ссылок и хороших ответов.

Вот реализация, использующая некоторые идеи со Scipy, используя ваши три изображения выше (сохраненные как im1.jpg, im2.jpg, im3.jpg, соответственно). Окончательный результат показывает im1 по сравнению с самим собой в качестве базовой линии, а затем каждое изображение сравнивается с другими.

>>> import scipy as sp
>>> from scipy.misc import imread
>>> from scipy.signal.signaltools import correlate2d as c2d
>>>
>>> def get(i):
...     # get JPG image as Scipy array, RGB (3 layer)
...     data = imread('im%s.jpg' % i)
...     # convert to grey-scale using W3C luminance calc
...     data = sp.inner(data, [299, 587, 114]) / 1000.0
...     # normalize per http://en.wikipedia.org/wiki/Cross-correlation
...     return (data - data.mean()) / data.std()
...
>>> im1 = get(1)
>>> im2 = get(2)
>>> im3 = get(3)
>>> im1.shape
(105, 401)
>>> im2.shape
(109, 373)
>>> im3.shape
(121, 457)
>>> c11 = c2d(im1, im1, mode='same')  # baseline
>>> c12 = c2d(im1, im2, mode='same')
>>> c13 = c2d(im1, im3, mode='same')
>>> c23 = c2d(im2, im3, mode='same')
>>> c11.max(), c12.max(), c13.max(), c23.max()
(42105.00000000259, 39898.103896795357, 16482.883608327804, 15873.465425120798)

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

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

13 голосов
/ 30 ноября 2009

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

  1. Разделить изображение на красный, зеленый и синий
  2. Создать нормализованные гистограммы для красного, зеленого и синего каналов и объединить их в вектор (r0...rn, g0...gn, b0...bn), где n - количество "сегментов", 256 должно быть достаточно
  3. вычтите эту гистограмму из гистограммы другого изображения и вычислите расстояние

вот код с numpy и pil

r = numpy.asarray(im.convert( "RGB", (1,0,0,0, 1,0,0,0, 1,0,0,0) ))
g = numpy.asarray(im.convert( "RGB", (0,1,0,0, 0,1,0,0, 0,1,0,0) ))
b = numpy.asarray(im.convert( "RGB", (0,0,1,0, 0,0,1,0, 0,0,1,0) ))
hr, h_bins = numpy.histogram(r, bins=256, new=True, normed=True)
hg, h_bins = numpy.histogram(g, bins=256, new=True, normed=True)
hb, h_bins = numpy.histogram(b, bins=256, new=True, normed=True)
hist = numpy.array([hr, hg, hb]).ravel()

если у вас есть две гистограммы, вы можете получить расстояние следующим образом:

diff = hist1 - hist2
distance = numpy.sqrt(numpy.dot(diff, diff))

Если два изображения идентичны, расстояние равно 0, чем больше они расходятся, тем больше расстояние.

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

6 голосов
/ 04 декабря 2009

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

a = asarray(Image.open('c603225337.jpg').convert('L'))
b = asarray(Image.open('9b78f22f42.jpg').convert('L'))
f1 = rfftn(a)
f2 = rfftn(b)
g =  f1 * f2
c = irfftn(g)

Это не будет работать так, как написано, поскольку изображения имеют разные размеры, а выходные данные не взвешены или не нормализованы вообще.

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

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

6 голосов
/ 30 ноября 2009

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

БПФ должно быть в порядке ( numpy имеет реализацию для двумерных матриц ), но я всегда слышу, что вейвлеты лучше подходят для такого рода задач ^ _ ^

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

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

import Image
import numpy
import sys

def main():
    img1 = Image.open(sys.argv[1])
    img2 = Image.open(sys.argv[2])

    if img1.size != img2.size or img1.getbands() != img2.getbands():
        return -1

    s = 0
    for band_index, band in enumerate(img1.getbands()):
        m1 = numpy.fft.fft2(numpy.array([p[band_index] for p in img1.getdata()]).reshape(*img1.size))
        m2 = numpy.fft.fft2(numpy.array([p[band_index] for p in img2.getdata()]).reshape(*img2.size))
        s += numpy.sum(numpy.abs(m1-m2))
    print s

if __name__ == "__main__":
    sys.exit(main())

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

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

2 голосов
/ 30 ноября 2009

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

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

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

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

1 голос
/ 30 ноября 2009

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

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

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

0 голосов
/ 03 мая 2019

Я предлагаю решение, основанное на индексе подобия Жакара по гистограммам изображений. Смотри: https://en.wikipedia.org/wiki/Jaccard_index#Weighted_Jaccard_similarity_and_distance

Вы можете вычислить разницу в распределении цветов пикселей. Это действительно довольно инвариантно для переводов.

from PIL.Image import Image
from typing import List

def jaccard_similarity(im1: Image, im2: Image) -> float:
    """Compute the similarity between two images.
    First, for each image an histogram of the pixels distribution is extracted.
    Then, the similarity between the histograms is compared using the weighted Jaccard index of similarity, defined as:
    Jsimilarity = sum(min(b1_i, b2_i)) / sum(max(b1_i, b2_i)
    where b1_i, and b2_i are the ith histogram bin of images 1 and 2, respectively.

    The two images must have same resolution and number of channels (depth).

    See: https://en.wikipedia.org/wiki/Jaccard_index
    Where it is also called Ruzicka similarity."""

    if im1.size != im2.size:
        raise Exception("Images must have the same size. Found {} and {}".format(im1.size, im2.size))

    n_channels_1 = len(im1.getbands())
    n_channels_2 = len(im2.getbands())
    if n_channels_1 != n_channels_2:
        raise Exception("Images must have the same number of channels. Found {} and {}".format(n_channels_1, n_channels_2))

    assert n_channels_1 == n_channels_2

    sum_mins = 0
    sum_maxs = 0

    hi1 = im1.histogram()  # type: List[int]
    hi2 = im2.histogram()  # type: List[int]

    # Since the two images have the same amount of channels, they must have the same amount of bins in the histogram.
    assert len(hi1) == len(hi2)

    for b1, b2 in zip(hi1, hi2):
        min_b = min(b1, b2)
        sum_mins += min_b
        max_b = max(b1, b2)
        sum_maxs += max_b

    jaccard_index = sum_mins / sum_maxs

    return jaccard_index

Что касается среднеквадратичной ошибки, индекс Жакара всегда лежит в диапазоне [0,1], что позволяет сравнивать изображения разных размеров.

Затем вы можете сравнить два изображения, но после изменения масштаба до одинакового размера! Или количество пикселей должно быть как-то нормализовано. Я использовал это:

import sys

from skincare.common.utils import jaccard_similarity

import PIL.Image
from PIL.Image import Image

file1 = sys.argv[1]
file2 = sys.argv[2]

im1 = PIL.Image.open(file1)  # type: Image
im2 = PIL.Image.open(file2)  # type: Image

print("Image 1: mode={}, size={}".format(im1.mode, im1.size))
print("Image 2: mode={}, size={}".format(im2.mode, im2.size))

if im1.size != im2.size:
    print("Resizing image 2 to {}".format(im1.size))
    im2 = im2.resize(im1.size, resample=PIL.Image.BILINEAR)

j = jaccard_similarity(im1, im2)
print("Jaccard similarity index = {}".format(j))

Тестирование на ваших изображениях:

$ python CompareTwoImages.py im1.jpg im2.jpg
Image 1: mode=RGB, size=(401, 105)
Image 2: mode=RGB, size=(373, 109)
Resizing image 2 to (401, 105)
Jaccard similarity index = 0.7238955686269157
$ python CompareTwoImages.py im1.jpg im3.jpg 
Image 1: mode=RGB, size=(401, 105)
Image 2: mode=RGB, size=(457, 121)
Resizing image 2 to (401, 105)
Jaccard similarity index = 0.22785529941822316
$ python CompareTwoImages.py im2.jpg im3.jpg 
Image 1: mode=RGB, size=(373, 109)
Image 2: mode=RGB, size=(457, 121)
Resizing image 2 to (373, 109)
Jaccard similarity index = 0.29066426814105445

Вы также можете поэкспериментировать с различными фильтрами передискретизации (такими как NEAREST или LANCZOS), поскольку они, конечно, изменяют распределение цвета при изменении размера.

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

0 голосов
/ 30 апреля 2017

Для правильной работы импорта на моем Ubuntu 16.04 (по состоянию на апрель 2017 года) я установил python 2.7 и эти:

sudo apt-get install python-dev
sudo apt-get install libtiff5-dev libjpeg8-dev zlib1g-dev libfreetype6-dev liblcms2-dev libwebp-dev tcl8.6-dev tk8.6-dev python-tk
sudo apt-get install python-scipy
sudo pip install pillow

Затем я изменил импорт Снежинки на эти:

import scipy as sp
from scipy.ndimage import imread
from scipy.signal.signaltools import correlate2d as c2d

Как здорово, что сценарий Снежинки сработал для меня 8 лет спустя!

0 голосов
/ 30 ноября 2009

Я думаю, вы могли бы сделать что-то вроде этого:

  • оценка вертикального / горизонтального смещения эталонного изображения по сравнению со сравнительным изображением. простой SAD (сумма абсолютной разности) с векторами движения будет делать для.

  • соответственно сместить изображение сравнения

  • вычислите корреляцию Пирсона, которую вы пытались сделать

Измерение сдвига не сложно.

  • Возьмите область (скажем, около 32x32) в изображении сравнения.
  • Сдвиньте его на x пикселей по горизонтали и y пикселей по вертикали.
  • Вычислить SAD (сумма абсолютной разницы) с.р. Исходное изображение
  • Сделайте это для нескольких значений x и y в небольшом диапазоне (-10, +10)
  • Найдите место, где разница минимальна
  • Выберите это значение как вектор движения смещения

Примечание:

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

...