1

有一个彩色图像(h,w,3)，一个具有N =h*w 像素的 numpy 形状数组；有一个shape数组标签(h,w)，每个标签都是 1 和M之间的整数。N是 10^6-10^7，M是 10^3-10^4。

我需要生成一个结果图像 (h,w,3)，其中标记为 l 的每个像素的颜色是标记为 l 的所有像素的平均颜色。IE：

def recolor1(image, labels):
    result = np.empty(shape=(h,w,3))
    for label in np.unique(labels):
        mask = labels==label
        mean = np.mean(image[mask], axis=0)
        result[mask] = mean
    return result

代码很简单，但运行时间为O(MN)（计算时间mask为O(N)，循环运行M次）。

O(N)recolor2是可能的。基本上你会检查标签和图像像素两次。首先计算一个由标签索引的辅助数组，在其中保存每个主数组的总和以及该标签的像素数。然后计算每个标签的平均值。然后你再次检查标签和像素，计算结果。找到平均值的 O(M) 时间是噪声。

用recolor2Python 编写， N=1000000recolor1和recolor2M=1000 在 ~4s 时收支平衡。正如预期的那样，recolor1对于 M=5000，' 的时间线性增长到 ~20 秒，而recolor2' 的时间基本保持不变。

相对较小的图像 4s 不是很好，对于较大的图像会变得更糟。我不是 numpy 和相关库的专家。那里有 O(N) 解决方案吗？

4

1 回答 1

2

让我们尝试np.bincount遍历通道：

result = np.stack([np.bincount(labels.flat, weights=img[...,i].flat)[labels-1] 
                   for i in range(3)],
                  axis=-1)

这在我的系统上大约需要 35 毫秒h,w,M = 1000,1000,1000。

注意这计算总和，但平均值应该很容易。

于 2021-02-05T15:43:41.957 回答