算法快速比较图像/矩阵

Question

有一张图片（imA），大小是10x10像素，还有超过60,000张图片（imN），同样大小也是10x10像素。

所有的图片都是黑白的。

我的任务是找出最少需要多少个点，才能把第一张图片（imA）和其他所有图片（imN）区分开来。抱歉我的英语不好，我会加上图片和评论。

我做的第一件事是把所有的图片转换成一个矩阵，用的是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] 这里的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，这个数字也不少。

有没有更优雅的方法来解决我的问题，而不是用暴力破解呢？

更新：添加图片

第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

10乘10等于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;
    }
}

可能我没有理解问题。如果是这样的话，请再详细解释一下。

Answer 2

我的方法是这样的：

1. 把图片读进一个60,000行、100列的数组，里面的值设为1和0。
2. 逐个像素计算，把每个像素在多少张图片中是“1”，也就是被设置了。
3. 在你的参考图片中，找出那个总和最低的像素。（如果总和是0，那说明只有这个像素能用来区分参考图片和其他所有图片）
4. 现在只看那些该像素为1的图片，重新计算总和，再次找出最低的。
5. 不断重复这个过程，直到要么选出参考图片中的所有设置为1的像素（这意味着无法区分，或者所有像素都需要），要么总和等于1，这表示只有一张图片的那个像素是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

这告诉我们需要16个像素中的7个来把参考图片和其他图片区分开，分别是像素0、1、2、4、5、10和15。

Answer 3

如果我理解你的问题没错的话，你需要计算第一张图片上有多少个点是和所有其他图片都不一样的，不管其他图片之间有什么不同？

如果是这样的话，除非我漏掉了什么，你是不是可以简单地做以下操作：

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]
            }
        }
    }
}

这样你就得到了一个二维矩阵DIFFS，这个矩阵的每个位置都表示原始图片中的对应像素是否和所有其他图片不同。