如何改進用於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均值確實不使用歐幾里得距離。它使用平方和。擺脫平方根。