关闭“查找”

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

…而且它的工作非常出色，在我的奔腾酷睿2.2GHz、4Gig内存和2600*2700像素的图像上运行了将近800秒：（

有没有什么方法可以稍微优化一下呢？可能是另一种算法或一些特定于Python的优化。在

UPD：我试着用欧几里得的平方，但还是得到了大量的时间。在

Answer 1

您可以使用^{}中的矢量量化函数vq。在

Answer 2

如果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 3

一个简单的优化是放弃sqrt调用。x与sqrt（x）是单调的，由于不需要实际距离，只需要最小距离，所以使用x^2代替。应该有点帮助，因为sqrt很贵。在

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

更新：可能需要对算法进行修改。现在你正在比较每个码本向量和每个像素。它可以加快速度以减少距离计算的次数。在

为此，使用kd-tree可能会更好，这会将对每个像素的搜索从O（codebook）减少到O（log（codebook））。我从来没有在python中这样做过，但是一些google给出了一个可能会工作here的实现。在