查找定义颜色中最近的像素 space - 使用 numpy 快速实现

Question

我一直在做一个任务，我在其中实现了图像量化的中值切割——只用有限的像素集来表示整个图像。我实现了该算法，现在我正在尝试实现该部分，我将每个像素分配给通过中值切割找到的集合中的一个代表。所以，我有变量 'color_space'，它是形状为 (n,3) 的 2d ndarray，其中 n 是代表的数量。然后我有变量'img'，这是形状的原始图像（行，列，3）。

现在我想根据欧氏距离为图像中的每个像素找到最近的像素（bin）。我能够得到这个解决方案：

    for row in range(img.shape[0]):
       for column in range(img.shape[1]):
          img[row][column] = color_space[np.linalg.norm(color_space - img[row][column], axis=1).argmin()]

它的作用是，对于图像中的每个像素，它计算向量 if 与每个 bin 的距离，然后取最近的一个。问题是，这个解决方案非常慢，我想对其进行矢量化 - 我不想为每个像素获取矢量，而是想获取一个矩阵，例如第一行将是我的代码中计算的第一个距离矢量等...

这个问题可以转化为一个问题，我想做一个矩阵乘法，但不是得到两个向量的点积，而是得到它们的欧氏距离。有没有解决此类问题的好方法？ numpy 中的一些通用解决方案，如果我们想在 numpy 中执行 'matrix multiplication'，但是函数 Rn x Rn -> R 不需要是点积，而是例如欧氏距离。当然，对于乘法，原图应该resize到(row*columns, 3)，但这是一个细节。

我一直在研究文档和搜索网络，但没有找到任何好的方法。

请注意，我不希望别人解决我的作业，我想出的解决方案是完全可以的，我只是好奇我是否可以在尝试正确学习 numpy 时加快速度。

感谢您的任何建议！

Answer 1

我觉得这样的做法可能会多一点numpy-ish/pythonic:

import numpy as np
from typing import *
from numpy import linalg as LA

# assume color_space is defined as a constant somewhere above and is of shape (n,3)

nearest_pixel_idxs: Callable[[np.ndarray], int] = lambda rgb: return LA.norm(color_space - rgb, axis=1).argmin()

img: np.ndarray = color_space[np.apply_along_axis(nearest_pixel_idxs, 1, img.reshape((-1, 3)))]

为什么这个解决方案可能更有效：

它依赖于可并行化的 apply_along_axis 函数 nearest_pixel_idxs() 而不是嵌套的 for-loops。这是通过重塑 img 实现的，从而消除了对双重索引的需要。
它避免重复写入 color_space，只在最后索引一次。

如果您希望我更深入地了解这些内容，请告诉我 - 很乐意提供帮助。

Answer 2

下面是用于向量化您的问题的 MWE。见评论解释。

import numpy

# these are just random array declaration to work with. 
image = numpy.random.rand(32, 32, 3)
color_space = numpy.random.rand(10,3)

# your code. I modified it to pick indexes
result = numpy.zeros((32,32))
for row in range(image.shape[0]):
    for column in range(image.shape[1]):
        result[row][column] = numpy.linalg.norm(color_space - image[row][column], axis=1).argmin()
result = result.astype(numpy.int)

# here we reshape for broadcasting correctly. 
image = image.reshape(1,32,32,3)
color_space = color_space.reshape(10, 1,1,3)

# compute the norm on last axis, which is RGB values
result_norm = numpy.linalg.norm(image-color_space, axis=3)

# now compute the vectorized argmin 
result_vectorized = result_norm.argmin(axis=0)

print(numpy.allclose(result, result_vectorized))

最终，您可以通过 color_space[result] 得到正确的解决方案。您可能必须删除在颜色 space 中添加的额外尺寸，才能在最后的操作中获得正确的形状。

Answer 3

你可以先广播得到所有的组合，然后计算每一个范数。然后你可以从那里选择最小的。

a = np.array([[1,2,3],
              [2,3,4],
              [3,4,5]])
b = np.array([[1,2,3],
              [3,4,5]])
a = np.repeat(a.reshape(a.shape[0],1,3), b.shape[0], axis = 1)
b = np.repeat(b.reshape(1,b.shape[0],3), a.shape[0], axis = 0)
np.linalg.norm(a - b, axis = 2)

结果的每一行代表a中的行到b

中每个代表的距离

array([[0.        , 3.46410162],
       [1.73205081, 1.73205081],
       [3.46410162, 0.        ]])

然后您可以使用 argmin 获得最终结果。

IMO 使用（@Umang Gupta 提出的）numpy 的自动广播比使用 repeat 更好。

查找定义颜色中最近的像素 space - 使用 numpy 快速实现

Finding nearest pixel in defined color space - quick implementation using numpy

python

performance

numpy

euclidean-distance