python - 找到最接近的向量

Question

最近我编写了量化 RGB 图像的算法。每个像素都由一个 (R,G,B) 向量表示，量化码本是一对 3 维向量。图像的每个像素都需要映射到(例如，“替换为”)欧几里德距离(更准确地说，平方欧几里德距离)最接近的码本像素。我是这样做的:

class EuclideanMetric(DistanceMetric):
    def __call__(self, x, y):
        d = x - y
        return sqrt(sum(d * d, -1))

class Quantizer(object):
    def __init__(self, codebook, distanceMetric = EuclideanMetric()):
        self._codebook = codebook
        self._distMetric = distanceMetric

    def quantize(self, imageArray):
        quantizedRaster = zeros(imageArray.shape)

        X = quantizedRaster.shape[0]
        Y = quantizedRaster.shape[1]
        for i in xrange(0, X):
            print i
            for j in xrange(0, Y):
                dist = self._distMetric(imageArray[i,j], self._codebook)
                code = argmin(dist)
                quantizedRaster[i,j] = self._codebook[code]

        return quantizedRaster

...而且效果非常好，在我的 Pentium Core Duo 2.2 GHz、4 GB 内存和 2600*2700 像素的图像上运行了近 800 秒:(

有没有办法稍微优化一下？也许是其他算法或一些特定于 Python 的优化。

UPD:我尝试使用平方欧几里德，但仍然花费了大量时间。

Answer 1

一个简单的优化是删除 sqrt 调用。 x 与 sqrt(x) 是单调的，并且由于您不需要实际距离，只需要最小距离，因此使用 x^2 代替。应该会有所帮助，因为 sqrt 很昂贵。

这个技巧在处理距离时经常使用。例如，如果您有距离阈值，则可以使用阈值^2 并在距离计算中删除 sqrt。实际上，只有当需要绝对距离时才需要开方。对于相对距离，请删除 sqrt。

更新:那么可能需要更改算法。现在您正在将每个码本向量与每个像素进行比较。减少距离计算的数量会加快速度。

使用 kd-tree 可能会做得更好为此，这会将每个像素的搜索从 O(codebook) 减少到 O(log(codebook))。我从来没有在 python 中这样做过，但是一些谷歌搜索给出了一个可能有效的实现 here .