使用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

我怀疑使用纯numpy最好的方法是使用^{}的O(N log N)解决方案。Numpy不直接支持哈希表

假设您有一对2D图像，A和B。argsort-of-one告诉您如何按排序顺序放置像素（两者的排序顺序相同）。另一个的倒argsort告诉您如何将这些像素放置到另一个：

toSortedA = np.argsort(A.ravel())
fromSortedB = np.argsort(np.argsort(B.ravel()))

现在，您可以通过使用索引将A转换为B

index = np.unravel_index(toSortedA[fromSortedB], A.shape)

这假设图像之间的所有像素都是相同的，只是随意移动

PS

其他答案正确地指定了O(n)算法，该算法也适用于使用dict的非无序图像。为了完整起见，这里有一种更短（可能更快）的方法来构造查找表：

it = np.nditer(raw_image, flags=['multi_index'])
raw_dict = {pixel.item(): it.multi_index for pixel in it}

由^{}生成的像素值是数组中的一个视图，因此，如果需要，您可以边走边修改

Answer 2

尝试使用字典。
由于您提到每个图像本身都有一组唯一的像素，因此只需对该图像的像素进行一次迭代，即可枚举或将像素描述作为键存储在字典中，并将值作为其位置。 一旦您使用完两个图像的字典，通过检查其中一个的键在另一个中的存在情况来比较这两个将是非常快的。

伪代码：

raw = Image.load(raw)
rendered = Image.load(rendered)

raw_dict = {}
rendered_dict = {}

for(i,j in row,col in raw):
    raw_dict[raw[i][j]] = str(i)+"_"+str(j)

for(i,j in row,col in rendered):
    rendered_dict[rendered[i][j]] = str(i)+"_"+str(j)

现在您有了两个包含所有像素信息的字典。
迭代其中一个以检查另一个字典中是否存在密钥。

for(key in rendered_dict):
    if(raw_dict.containsKey(key)):
        print("Found match: Rendered(",rendered_dict[key],") at Raw(",raw_dict[key]")")

使用这种方法，您最多可以按线性顺序在像素上迭代三次。

在执行时间方面分享结果

Answer 3

如果你愿意使用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")