使用 numpy 快速迭代像素

Question

我有两个分辨率为 4095x4095 的图像，每个像素都有不同的颜色（一个图像中没有重复的像素）。我正在尝试构建一个“地图”，描述两个图像之间每个像素的移动。

我现在拥有的是一种有效但非常幼稚的算法，它只是循环遍历所有像素，直到找到匹配项，然后移动到下一个像素。这种方法需要数年时间才能遍历图像中的所有像素。我想知道是否可以使用 numpy 来加快速度。到目前为止，我无法让它发挥作用。

工作，但缓慢的算法：

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()

和输出：

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.

如果有更多麻木经验的人可以向我展示方向，那将不胜感激。

Answer 1

如果您愿意使用 O(n) 空间，您可以获得 O(n) 算法。制作一个字典，其中包含像素值作为键，该像素的位置作为值。代码示例：

# 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")