Алгоритм сравнения изображений

Question

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

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

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

Редактировать:Вот пример моих фотографий (микроскопических):

im1:

im2:

im3:

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

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

Answer 1

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", упомянутого в ответах на другой вопрос, или с пикселизацией.Тот факт, что у вас есть изображения разных размеров, усложняет ситуацию, но вы не предоставили достаточно информации о степени разделки, которую можно было бы ожидать, поэтому трудно дать конкретный ответ, который учитывал бы это.

Answer 2

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

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, чем больше они расходятся, тем больше расстояние.

Для меня это неплохо работало с фотографиями, но не сработало с графикой, такой как тексты и логотипы.

Answer 3

Вам действительно нужно уточнить вопрос получше, но, глядя на эти 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)

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Answer 7

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

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

• соответствующим образом сместите изображение сравнения

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

Измерение сдвига не составляет труда.

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

Примечание:

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

Answer 8

Чтобы заставить импорт корректно работать в моем 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

Затем я изменил импорт Snowflake на эти:

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

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

Answer 9

Я предлагаю решение, основанное на индексе сходства Джаккарда на гистограммах изображений.Видишь: 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), поскольку они, конечно, изменяют распределение цветов при изменении размера.

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