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

Question

Имеется одно изображение (imA) размером 10x10px и более 60 000 изображений (imN) 10x10

Все изображения черно-белые

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

Первое, что я сделал, это превратило все изображения в матрицу с numpy

q=0
for file in inputImages:
    eachImage = os.path.join(generatorFolder, file)
    a[q]=numpy.asarray(Image.open(eachImage))
    q+=1

b=numpy.asarray(Image.open(templateimage))

b [y, x, color] раскрасить свой список [255,255,255]

a [1-60000, y, x, color]

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

for y1 in range(b.shape[0]):
    for x1 in range(b.shape[1]):
        for y2 in range(b.shape[0]):
            for x2 in range(b.shape[1]):
                for y3 in range(b.shape[0]):
                    for x3 in range(b.shape[1]):
                        if y1==y2==y3 and x1==x2==x3:continue

                        check=0
                        for a_el in range(a.shape[0]):
                            if numpy.array_equal(b[y1,x1],a[a_el,y1,x1]) and \
                               numpy.array_equal(b[y2,x2],a[a_el,y2,x2]) and \
                               numpy.array_equal(b[y3,x3],a[a_el,y3,x3]):
                                check=1
                                break

                        if not check:return 'its unic dots'

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

получи 100!/ 95!* 60 000 сравнений - 542 070 144 000 000

Правда, я использую немного другой алгоритм, который позволяет превратить это в: 40! / 35! * 60000 = 4.737.657.600.000, что не так уж и мало.

Есть ли способ решить мою проблему красивее, а не грубой силой.

ОБНОВЛЕНИЕ add img

0строка: 3 других изображения (imN) 4x4

1 строка: 0 шаблонное изображение (imA) и 1-3 изображения, где отмечена красная разница (imA XOR imN)

2 строка: 0 изображениегде синим цветом отмечены две точки две точки для сравнения,

    1 image green its difference, red its compare - difference yes - NEXT

    2 image red its compare - difference NO - Break (these two points is not enough to say that imA differs from imN(2))

3 линия: как линия 2, другие точки

4 линия: Мы выбрали две точки, достаточно, чтобы сказать, что imA отличается отImn (1-3)

Answer 1

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

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

boolean[10][10] DIFFS // all values set to TRUE
int[10][10] ORIGINAL  // store first pictures color values

foreach IMAGE in [IMAGES - FIRST IMAGE] {
    int[10][10] CURRENT <- IMAGE // store the current image's color values
    for (i : 0 -> 9) {
        for (j : 0 -> 9) {
            if (DIFFS[i][j]) {
                DIFFS[i][j] = ORIGINAL[i][j] != CURRENT[i][j]
            }
        }
    }
}

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

Answer 2

Мой подход был бы следующим:

1. Считывание изображений в массив 60000 на 100, установленное как 1 и 0.
2. Суммируйте их в расчете на пиксель, чтобы подсчитать, сколько изображений для каждого пикселя "установлено" равным 1 в
3. Выберите пиксель в эталонном изображении с наименьшей суммой.(Если сумма равна 0, то только этот пиксель необходим для различения эталонного изображения и всех остальных)
4. Теперь смотрите только на изображения с установленным битом, пересчитайте суммы и снова выберите самый низкий. * 1 010 *
5. Повторите итеративно до тех пор, либо все заданные биты в опорном изображении не будут выбраны (что означает, что либо не представляется возможным, чтобы отличить его или что все биты необходимы) или до тех пор, сумма не равна 1, что означает,только один образ имеет тот набор битов

в коде 1000 4x4 изображений:.

import numpy

def least_freq_set_pixel(array, must_have):
    # If it is specified that a certain pixels must be set, remove rows that don't have those pixels set
    if must_have != []:
        for i in must_have:
            array = numpy.delete(array, numpy.where(array[:,i] == 0), axis = 0)

    # Calculate the sum for each pixel
    set_in_n = numpy.sum(array, axis = 0)
    my_index = numpy.argmin(set_in_n)

    # Return the pixel number which is set in the fewest images
    return my_index, set_in_n[my_index]


# Create some test data 4x4 images
numpy.random.seed(11)
a = numpy.array([0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0])
b = numpy.random.randint(0,2,(1000,16))


must_have = []
stop = 0
while stop == 0:
    i,j = least_freq_set_pixel(b, must_have)
    print i,j
    # If the pixel is set in more than one image and not all pixels have been selected yet... find the next pixel
    if j > 1 and len(must_have) <= 16:
        must_have.append(i)
    else:
        stop = 1
        print must_have

, который говорит нам, что нам нужно 7 пикселей 16 для разделения опорного изображенияот остальных пикселей 0,1,2,4,5,10 и 15.

Answer 3

Если я правильно понимаю, мы можем полностью переопределить вашу проблему. Я думаю, что вы хотите достичь: быстро определить, соответствует ли определенное изображение одному из предварительно определенных 60000 или ни одному из них. Каждое изображение 10x10 черно-белое.

Ооо, каждое изображение можно интерпретировать как массив 10x10 = 100 бит, и у вас есть 60000 заданных значений, с которыми вы хотите сравнить.

Почему бы вам не преобразовать 60000 изображений в 100-битные целые числа и не отсортировать их. Тогда вы можете довольно эффективно сравнить любое 100-битное целое число и найти попадание или промах.

РЕДАКТИРОВАТЬ: если я правильно понимаю комментарий, изображения гораздо больше. До тех пор, пока известные из них все еще являются управляемым количеством (60 Кбайт, и 600 Кбайт, вероятно, также), вы можете создавать хэши для этих изображений и сортировать и сравнивать их. У вас есть некоторые предварительные затраты на вычисления, но у вас есть только один раз.

Answer 4

10x10 = 100. 100 сравнений между двумя изображениями.у вас есть 60000 изображений.Я думаю, что алгоритм должен быть O (100 * 60000) = O (6000000).Я не знаю Python, но псевдоалгоритм должен быть таким:

int minDistinguishPoints = 100; 
int currentPointsDiff;
Image imA;

foreach (Image myImg in ImageItems)
{
    currentPointsDiff = 0;
    for (int i=0; i<10; i++)
       for (int j=0; j<10; j++)
       {
           if (!imA.GetPixel(i,j).Equals(myImg.GetPixel(i,j)))
           {
               currentPointsDiff++;
           }                
       }
    if (minDistinguishPoints > currentPointsDiff)
    {
        minDistinguishPoints = currentPointsDiff;
    }
}

Может быть, я не понимаю вопроса.Если да, объясните подробнее, пожалуйста.