Use numpy to quickly iterate over pixels

Question

I have two images of resolution 4095x4095 and every pixel has a different color (no duplicate pixels within one image). I am trying to build a "map" describing the movement of each pixel between the two images.

What I have now is a working, but very naive algorithm, that simply loops through all pixels until it finds a match, at which point it moves to the next pixel. This is approach would take several years to iterate over all pixels in my images. I was wondering if I could use numpy to speed this up. So far I wasn't able to make it work.

Working, but slow algorithm:

import PIL
import time
from PIL import Image

raw = Image.open('image1.png')
rawLoad = raw.load()
rendered = Image.open('image2.png')
renderedLoad = rendered.load()
counter = 1
timer = time.time()

for rendered_x in range(rendered.width):
        for rendered_y in range(rendered.height):
            for raw_x in range(raw.width):
                    for raw_y in range(raw.height):
                        if rawLoad[raw_x, raw_y] == renderedLoad[rendered_x, rendered_y]:
                            print('Found pixel no. '+str(counter)+' pos '+str(rendered_x)+' '+str(rendered_y)+' in position '+str(raw_x)+' '+str(raw_y)+'. Took '+str(round(time.time() - timer, 2))+' s.')
                            break
                    else:
                        continue
                    break
            counter += 1
            timer = time.time()

And the output:

Found pixel no. 1 pos 0 0 in position 2710 901. Took 6.29 s.
Found pixel no. 2 pos 0 1 in position 2148 901. Took 4.84 s.
Found pixel no. 3 pos 0 2 in position 1793 1365. Took 3.92 s.
Found pixel no. 4 pos 0 3 in position 774 1365. Took 1.54 s.
Found pixel no. 5 pos 0 4 in position 4049 1365. Took 7.93 s.
Found pixel no. 6 pos 0 5 in position 2982 1373. Took 4.94 s.
Found pixel no. 7 pos 0 6 in position 2163 1373. Took 4.41 s.
Found pixel no. 8 pos 0 7 in position 1286 1822. Took 2.17 s.
Found pixel no. 9 pos 0 8 in position 211 1822. Took 0.34 s.
Found pixel no. 10 pos 0 9 in position 2710 1813. Took 4.23 s.
Found pixel no. 11 pos 0 10 in position 1891 1813. Took 2.98 s.

If somebody with more numpy experience could show me the direction, that would be highly appreciated.

Answer 1

You can get an O(n) algorithm if you're willing to use O(n) space. Make a dictionary containing the pixel values as key and the location of that pixel as the value. Code example:

# Assume raw_img and rendered_img are saved as variables

height, width = raw_img.shape

# Save all values from raw_img in dictionary
img_dict = {}
for i in range(height):
    for j in range(width):
        pixel_val = raw_img[i, j]
        img_dict[pixel_val] = (i, j)


# Loop over the values in the rendered img and lookup in dictionary
for i in range(height):
    for j in range(width):
        pixel_val = rendered_img[i, j]
        if pixel_val in img_dict:
            raw_img_coord = img_dict[pixel_val]
            print(f"Found pixel {pixel_val} at {i, j} in rendered_img matching " +
                  f"pos {raw_img_coord} in raw_img")