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

Answer 2

我怀疑使用纯numpy所能做的最好的就是使用O(N log N)解决方案，使用argsort。Numpy不直接支持散列表。

假设你有一对2D图像，A和B。讨论的内容告诉您如何将像素按排序顺序放置(这两者是相同的)。另一个像素的倒排告诉您如何将这些像素放置到另一个像素中：

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)算法，该算法也适用于使用dicts的非混叠图像。为了完整起见，下面是构造查找表的一种更短(而且可能更快)的方法：

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

nditer产生的像素值是数组中的一个视图，因此，如果需要，您可以随时修改。

Answer 3

试着用字典。

由于您提到每个图像本身都有唯一的像素集，那么只需迭代该图像的像素一次，以枚举或存储像素描述，将其作为以值作为其位置的字典中的键。一旦您完成了这两个图像的字典，它将是疯狂的比较，通过检查一个键在另一个。

伪码：

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

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

在执行的时间上共享结果。