Algorithm Fast Compare Images \ Matrix

There is one image (imA) size 10x10px and more 60 000 images (imN) 10x10 All images are black and white The task of finding the minimum number of points with which to distinguish t

Solution 1:

If I understand your question correctly, you need to calculate the number of points on the first picture, which is different from all the other pictures, irrespective of how the other pictures differ from each other?

If this is case, unless I'm missing something, can you not simply do something like the following:

boolean[10][10] DIFFS // all values set to TRUEint[10][10] ORIGINAL  // store first pictures color valuesforeach IMAGE in [IMAGES - FIRST IMAGE] {
    int[10][10] CURRENT <- IMAGE // store the current image's color valuesfor (i : 0 -> 9) {
        for (j : 0 -> 9) {
            if (DIFFS[i][j]) {
                DIFFS[i][j] = ORIGINAL[i][j] != CURRENT[i][j]
            }
        }
    }
}

Then you are left with a 2-dimensional matrix DIFFS where each position indicates if the corresponding pixel in the original image differs from all the other pictures.

Solution 2:

My approach would be:

1. Read images into a 60,000 by 100 array, set as 1's and 0's.
2. Sum them on a per pixel basis to get a count of how many images each pixel is "set" to 1 in
3. Pick the pixel in your reference image which has the lowest sum. (If the sum is 0, then only that pixel is required to distinguish between the reference image and all the others)
4. Now looking only at images with that bit set, re-calculate the sums and pick the lowest again.
5. Repeat iteratively until either all the set bits in the reference image are selected (which means that either it is not possible to distinguish it or that all bits are required) or until the sum is equal to 1 which means only one image has that bit set.

In code, for 1000 4x4 images:

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 setif 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 imagesreturn 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 = 0while 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 pixelif j > 1and len(must_have) <= 16:
        must_have.append(i)
    else:
        stop = 1print must_have

which tells us that we need 7 pixels of the 16 to separate the reference image from the rest, pixels 0,1,2,4,5,10 and 15.

Solution 3:

10x10 = 100. 100 comparisons between two images. you have 60000 images. I think that algorithm have to be O(100 * 60000) = O(6000000). I don't know python, but pseudo-algorithm should be like that:

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

May be I don't understand question. If so, explain some more detail, please.

Solution 4:

If I understand correctly, we can completely redefine your problem. What I think you want to achieve: quickly identify, whether a certain given image equals one out predefined 60000 or none of these. Every image is 10x10 black/white.

Sooo every image can be interpreted as a 10x10=100 bit array, and you have 60000 predetermined given, against which you want to compare.

Why don't you just convert your 60000 images into 100bit-integers, and sort these. Then you can quite efficiently compare any 100bit-integer and find a hit or miss.

EDIT: if I understand the comment correctly, the images are much larger. As long as the known ones are still a manageable amount (60k is, and 600k is probably also), you could generate hashes for these images and sort and compare these. You have some up-front computing cost, but you have it only once.