找到最近的向量

Question

最近我写了一个算法，用来对RGB图像进行量化。每个像素用一个(R,G,B)向量表示，而量化的代码本就是一组三维向量。图像中的每个像素需要被映射到与之在欧几里得距离上（更准确地说，是平方欧几里得距离）最接近的代码本像素上，也就是说要“替换成”那个像素。

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，4GB内存的电脑上处理一个2600*2700像素的图像居然花了将近800秒:(

有没有什么办法可以优化一下这个过程？也许换个算法或者一些Python特有的优化方法。

更新: 我尝试使用平方欧几里得距离，结果还是耗时巨大。

Answer 1

如果X的值非常大，你会打印i很多次，这样会影响程序的运行速度。想要更详细的答案，可以继续往下看。

为了找出你程序中性能瓶颈的地方，我建议使用一个计时装饰器，类似于下面的代码：

from functools import wraps
import time

def time_this(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        finish = time.time()
        elapsed = (finish - start) * 1000
        print '{0}: {1} ms'.format(func.__name__, elapsed)
        return result
    return wrapper

我曾经在某个地方看到过这个装饰器，从那以后我一直用它来找出我的代码运行慢的地方。你可以把你的算法分解成一系列独立的函数，然后用这个装饰器装饰这些函数，这样就能看到每个函数调用花了多长时间。接下来，你可以调整哪些语句放在哪些函数里，看看这样做能否改善装饰函数的运行时间。主要你要关注两件事：1）执行时间很长的语句，或者2）执行时间不一定很长，但执行次数很多的语句，这样即使是很小的性能提升也会对整体性能产生很大影响。

祝你好运！

Answer 2

你可以使用一个叫做 vq 的向量量化函数，这个函数来自于 scipy.cluster.vq 这个库。

Answer 3

一个简单的优化方法是去掉 sqrt 这个计算。x 和 sqrt(x) 是单调递增的关系，而你其实不需要真实的距离，只需要最小距离，所以可以用 x^2 来代替。这样做会有点帮助，因为计算平方根是比较耗费资源的。

这个小技巧在处理距离时经常用到。例如，如果你有一个距离阈值，可以用阈值的平方来代替，省去计算平方根。在绝对距离需要的时候，才需要用到平方根。对于相对距离，可以直接省略平方根。

更新一下：可能需要改变算法。目前你是把每个代码本向量和每个像素进行比较。减少距离计算的次数会让速度更快。

你可以考虑使用一个 kd-tree，这样可以把每个像素的搜索时间从 O(代码本) 降到 O(log(代码本))。我自己在 Python 中没有做过这个，但通过一些搜索找到了一些可能有效的实现 在这里。