如何改进用于K均值聚类的“哑”矢量量化算法

Question

我需要将依赖于scipy.cluster.vq模块的代码库转换为不使用scipy，以便我可以在C++中实现它。

首先，我试图仅使用numpy复制结果。

从尺寸为MxNx3的图像开始，我使用kmeans与opencv创建“质心”Kx3阵列。

我需要将原始图像的每个像素映射到质心阵列中与原始像素最接近的像素值。

我有它的工作，但性能是可怕的。我确定必须有更高级的方法来计算这个值，我怀疑它与最近的邻居搜索有关（可能？），但不确定。

这是目前我在做什么：我想这可能被称为“强力”的做法

1. 遍历图像
2. 中的每个像素计算该像素与每个之间的欧氏距离中心列表中的像素
3. 返回步骤2中生成的列表中的最小值

4. 将原始图像像素指定为返回最小距离的质心列表的值。所有的

   def vq(self,image,centroids): 
       x,y,z = image.shape 
       Z=np.reshape(image,(x*y,z)) 
       counts = np.zeros(len(centroids)) 
       clusterMap = np.zeros(Z.shape,np.uint8) 
       for i in range(Z.shape[0]): 
        color = Z[i] 
        closestIndex = self.getClosestCenter(color, centroids) 
        counts[closestIndex]+=1# tracking how often each color occurs 
        clusterMap[i] = centroids[closestIndex] 
       return clusterMap,counts 
   
   def getClosestCenter(self,color,centers): 
        distances = [0 for i in range(len(centers))] 
        for i,center in enumerate(centers): 
         distances[i] = self.getDistance(color, center) 
        return distances.index(min(distances)) 
   
   def getDistance(self,value1,value2): 
        if len(value1) !=len(value2): return None #error 
        sum = 0 
        for i in range(len(value1)): 
         sum+=(value1[i]-value2[i])**2 
        return sum**(0.5) 
   

Answer 1

首先，分析代码看到哪儿它是缓慢的。 构造如enumerate可能非常昂贵，因为它们需要创建和垃圾回收许多元组对象。一个好的经验规则是为了避免在内部循环和函数的对象分配（这包括隐藏的对象如元组）

最后但并非最不重要的，k均值确实不使用欧几里得距离。它使用平方和。摆脱平方根。