在Python中使用K-Means聚類和PCA主成分分析進行圖像壓縮

各位讀者好，在這片文章中我們嘗試使用sklearn庫比較k-means聚類算法和主成分分析（PCA）在圖像壓縮上的實現和結果。 壓縮圖像的效果通過占用的減少比例以及和原始圖像的差異大小來評估。 圖像壓縮的目的是在保持與原始圖像的相似性的同時，使圖像占用的空間盡可能地減小，這由圖像的差異百分比表示。 圖像壓縮需要幾個Python庫，如下所示：

# image processingfrom PIL import Imagefrom io import BytesIOimport webcolors# data analysisimport mathimport numpy as npimport pandas as pd# visualizationimport matplotlib.pyplot as pltfrom importlib import reloadfrom mpl_toolkits import mplot3dimport seaborn as sns# modelingfrom sklearn.cluster import KMeansfrom sklearn.decomposition import PCAfrom sklearn.preprocessing import MinMaxScaler

探索圖像

每個顏色通道的圖像圖像中的每個像素都可以表示為三個0到255之間的8位無符號（正）整數，或縮放為三個0到1之間的無符號（正）浮點數。這三個值分別指定紅色，綠色，藍色的強度值，這通常稱為RGB編碼。 在此文章中，我們使用了220 x 220像素的lena.jpg，這是在圖像處理領域廣泛使用的標準測試圖像。

ori_img = Image.open('images/lena.png')ori_img

原始圖像

X = np.array(ori_img.getdata())ori_pixels = X.reshape(*ori_img.size, -1)ori_pixels.shape

圖像儲存方式是形狀為（220、220、3）的3D矩陣。 前兩個值指定圖像的寬度和高度，最后一個值指定RBG編碼。 讓我們確定圖像的其他屬性，即圖像大小（以千字節（KB）為單位）和原色的數量。

def imageByteSize(img): img_file = BytesIO() image = Image.fromarray(np.uint8(img)) image.save(img_file, ’png’) return img_file.tell()/1024ori_img_size = imageByteSize(ori_img)ori_img_n_colors = len(set(ori_img.getdata()))

lena.jpg的原始圖像大小為86 KB，并具有37270種獨特的顏色。 因此，我們可以說lena.jpg中的兩個像素具有相同的精確RGB值的可能性很小。

接下來，讓我們計算圖像的差異作為壓縮結果的基準。

ori_img_total_variance = sum(np.linalg.norm(X - np.mean(X, axis = 0), axis = 1)**2)

我們得到方差為302426700.6427498。 但是我們無法解釋方差本身的價值。 我們稍后將在K-Means聚類中使用它。

k-means聚類

具有三個聚類中心的二維k-means聚類圖像

算法

k-means聚類是一種常用的無監督學習算法，用于將數據集劃分為k個聚類中心，其中k必須由用戶預先指定。 該算法的目標是將現有數據點分類為幾個集群，以便：

同一集群中的數據盡可能相似 來自不同集群的數據盡可能不同

每個集群由聚類中心表示，聚類中心是聚類數據點的平均值。 這是算法：

用戶指定集群數k 從數據集中隨機選擇k個不同的點作為初始聚類中心 將每個數據點分配給最近的聚類中心，通常使用歐幾里得距離 通過取屬于該集群的所有數據點的平均值來計算新聚類中心 重復步驟3和4，直到收斂為止，即聚類中心位置不變

請注意，結果可能并不理想，因為它取決于隨機的初始化。

理念

我們的原始圖像包含數千種顏色。 我們將利用K-Means聚類算法來減少顏色數量，因此它僅需要存儲一定數量的RGB值。 我們將減小圖像尺寸使其更有效率地進行儲存。 我們可以將像素值視為具有（寬度×高度）觀察值和3個與RGB值相對應的特征的數據幀。 對于lena.jpg，我們將具有220×220（48400）個觀測值和3個特征。

因此，我們可以可視化三維圖中的每個像素。 這是前220個像素，代表原始圖像中的第一行像素。

像素值的三維圖

簡單的例子

在我們對顏色數k使用各種值進行迭代之前，讓我們使用k = 2來了解我們的目的。 到本節末，我們希望圖像只有2種顏色。 首先，我們創建一個KMeans對象，該對象適合我們的原始像素X。

kmeans = KMeans(n_clusters = 2,n_jobs = -1,random_state = 123).fit(X)kmeans_df = pd.DataFrame(kmeans.cluster_centers_, columns = [’Red’, ’Green’, ’Blue’])

然后我們將RGB值轉換為其英文顏色名稱：

def closest_colour(requested_colour): min_colours = {} for key, name in webcolors.CSS3_HEX_TO_NAMES.items(): r_c, g_c, b_c = webcolors.hex_to_rgb(key) rd = (r_c - requested_colour[0]) ** 2 gd = (g_c - requested_colour[1]) ** 2 bd = (b_c - requested_colour[2]) ** 2 min_colours[(rd + gd + bd)] = name return min_colours[min(min_colours.keys())]def get_colour_name(requested_colour): try: closest_name = actual_name = webcolors.rgb_to_name(requested_colour) except ValueError: closest_name = closest_colour(requested_colour) return closest_namekmeans_df['Color Name'] = list(map(get_colour_name, np.uint8(kmeans.cluster_centers_)))kmeans_df

當我們指定2為n_clusters參數值時，我們得到兩個聚類中心。下一步，我們可以通過聚類中心來表示該群集中的每個像素值。 因此，在壓縮圖像中將只有兩個像素值。

def replaceWithCentroid(kmeans): new_pixels = [] for label in kmeans.labels_: pixel_as_centroid = list(kmeans.cluster_centers_[label]) new_pixels.append(pixel_as_centroid) new_pixels = np.array(new_pixels).reshape(*ori_img.size, -1) return new_pixelsnew_pixels = replaceWithCentroid(kmeans)

我們的聚類步驟已經完成，讓我們看一下壓縮圖像的結果。

def plotImage(img_array, size): reload(plt) plt.imshow(np.array(img_array/255).reshape(*size)) plt.axis(’off’) return plt plotImage(new_pixels, new_pixels.shape).show()

只有兩種顏色的壓縮圖片

K-Means僅使用兩種顏色成功地保留了lena.jpg的形狀。 在視覺上，我們可以比較原始圖像相似與壓縮圖像是否相似。 但是，我們如何用程序做到這一點？ 讓我們介紹一組評估壓縮圖像的指標：

在群集平方和（WCSS）中，測量群集中所有點與其群集中心的歐幾里德距離平方的總和。

在群集的平方和（BCSS）之間，測量所有聚類中心之間的歐幾里得距離平方的總和。

解釋方差，衡量壓縮圖像效果可以通過壓縮圖像解釋原始圖像的百分比。 如果將每個像素視為一個單獨的群集，則WCSS等于0。因此，Exparined Variance = 100％。

圖像大小，以千字節為單位，以評估縮小/壓縮性能。

def calculateBCSS(X, kmeans): _, label_counts = np.unique(kmeans.labels_, return_counts = True) diff_cluster_sq = np.linalg.norm(kmeans.cluster_centers_ - np.mean(X, axis = 0), axis = 1)**2 return sum(label_counts * diff_cluster_sq)WCSS = kmeans.inertia_BCSS = calculateBCSS(X, kmeans)exp_var = 100*BCSS/(WCSS + BCSS)print('WCSS: {}'.format(WCSS))print('BCSS: {}'.format(BCSS))print('Explained Variance: {:.3f}%'.format(exp_var))print('Image Size: {:.3f} KB'.format(imageByteSize(new_pixels)))

WCSS: 109260691.314189BCSS: 193071692.34763986Explained Variance: 63.861%Image Size: 4.384 KB

圖像大小從86 KB大幅下降到4.384 KB，但是要注意的是，壓縮圖像解釋原始圖像的能力達到63.861％。 我們期望比這更高的解釋方差百分比。 接下來，我們將重復上述過程并改變𝑘來實現此目標。

重復試驗

在本節中，我們將在𝑘= 2到𝑘= 20之間重復此步驟：

執行k-means以獲取每個像素的聚類中心和聚類標簽 將每個像素替換為其聚類中心。 保存指標值以進行進一步優化：WCSS，BCSS，解釋方差和圖像大小 用越來越多的顏色繪制壓縮圖像

range_k_clusters = (2, 21)kmeans_result = []for k in range(*range_k_clusters): # CLUSTERING kmeans = KMeans(n_clusters = k, n_jobs = -1, random_state = 123).fit(X) # REPLACE PIXELS WITH ITS CENTROID new_pixels = replaceWithCentroid(kmeans) # EVALUATE WCSS = kmeans.inertia_ BCSS = calculateBCSS(X, kmeans) exp_var = 100*BCSS/(WCSS + BCSS) metric = { 'No. of Colors': k, 'Centroids': list(map(get_colour_name, np.uint8(kmeans.cluster_centers_))), 'Pixels': new_pixels, 'WCSS': WCSS, 'BCSS': BCSS, 'Explained Variance': exp_var, 'Image Size (KB)': imageByteSize(new_pixels) } kmeans_result.append(metric)kmeans_result = pd.DataFrame(kmeans_result).set_index('No. of Colors')kmeans_result

聚類指標：最佳的顏色種類數

在本節中，我們將嘗試搜索最佳的顏色數（聚類中心）k，以便在保持較高的解釋方差百分比的同時將內存大小減小到盡可能小。

如何確定最佳顏色數k？ 以下是算法：

用直線連接曲線的第一個和最后一個點 計算每個點到該線的垂直距離 將距離最長的點視為拐點

下一個問題，如何在步驟2中計算垂直距離？ 很簡單，我們可以使用從點（x0，y0）到線ax + by + c = 0的距離公式，如下所示：

def locateOptimalElbow(x, y): # START AND FINAL POINTS p1 = (x[0], y[0]) p2 = (x[-1], y[-1]) # EQUATION OF LINE: y = mx + c m = (p2[1] - p1[1]) / (p2[0] - p1[0]) c = (p2[1] - (m * p2[0])) # DISTANCE FROM EACH POINTS TO LINE mx - y + c = 0 a, b = m, -1 dist = np.array([abs(a*x0+b*y0+c)/math.sqrt(a**2+b**2) for x0, y0 in zip(x,y)]) return np.argmax(dist) + x[0]

但是，如果圖形不是增加或減少的曲線函數，該怎么辦？ 我們可以使用有限差分法使用二階導數來定位梯度中變化最劇烈的地方。

什么是有限差分法？ 這是一種數值方法，可以近似離散值的導數。 共有三種類型：

forward差異：

backward差異：

中心差異：

其中：

f’（x）是函數f（x）的一階導數h是步長，在這種情況下，h = 1（顏色數的步長）O（h）是一級誤差項O（h²）是二次誤差項

由于中心差異具有較高的度數誤差項，因此預期它會比其他兩個差異產生更好的結果。 我們僅對第一個點使用前向差異，對最后一個點使用后向差異。

def calculateDerivative(data): derivative = [] for i in range(len(data)): if i == 0: # FORWARD DIFFERENCE d = data[i+1] - data[i] elif i == len(data) - 1: # BACKWARD DIFFERENCE d = data[i] - data[i-1] else: # CENTER DIFFERENCE d = (data[i+1] - data[i-1])/2 derivative.append(d) return np.array(derivative)def locateDrasticChange(x, y): # CALCULATE GRADIENT BY FIRST DERIVATIVE first_derivative = calculateDerivative(np.array(y)) # CALCULATE CHANGE OF GRADIENT BY SECOND DERIVATIVE second_derivative = calculateDerivative(first_derivative)return np.argmax(np.abs(second_derivative)) + x[0]

讓我們搜索每個指標的最佳k值：

optimal_k = []for col in kmeans_result.columns[2:]: optimal_k_dict = {} optimal_k_dict['Metric'] = col if col == 'Image Size (KB)': optimal_k_dict['Method'] = 'Derivative' optimal_k_dict['Optimal k'] = locateDrasticChange(kmeans_result.index, kmeans_result[col].values) else: optimal_k_dict['Method'] = 'Elbow' optimal_k_dict['Optimal k'] = locateOptimalElbow(kmeans_result.index, kmeans_result[col].values) optimal_k.append(optimal_k_dict)optimal_k = pd.DataFrame(optimal_k)optimal_k

我們選擇最大的最優k作為所有最優k的代表，即k = 12。

與原始圖像進行比較

最后，讓我們比較使用k = 12的壓縮圖像和原始圖像的區別。

relative_size = ori_vs_kmeans.loc['Color-Reduced', 'Image Size (KB)']/ori_vs_kmeans.loc['Original', 'Image Size (KB)']print('Reduction: {:.3f}% from original image size'.format((1-relative_size)*100))print('Explained Variance: {:.3f}%'.format(ori_vs_kmeans.loc['Color-Reduced', 'Explained Variance']))

縮小比例：原始圖像的79.012％解釋方差：95.916％

通過使用k-means，我們可以將圖像大小減少79.012％，而解釋方差為95.916％，這真是太好了！ 接下來，我們執行PCA，看看它是否可以優于k-means。

主成分分析（PCA）

概念

PCA是用于降維的無監督學習技術之一。 它從協方差矩陣計算出特征向量，然后將其稱為主軸，并按稱為解釋方差百分比的特征值進行遞減排序。 然后將數據集居中并投影到形成主要成分（或分數）的主軸上。 為了減少數據維度，我們僅保留一定數量的主成分n來解釋原始數據集的方差，而忽略其余部分。

假設我們有一個X_ori數據集，其中包含m個觀察值和n個特征。 減去每行的平均值，我們得到居中的數據X。然后，PCA將為每個特征計算k個特征向量，從而產生形狀為n×k的矩陣V。 PCA投影或分數將以Z = XV給出，其中Z的尺寸為m×k。

降維時，我們在X_ori中選擇n_select小于n。 以下是我們使用所選PC重建矩陣X的方法：

其中：

Z_reduce的尺寸為m×n_selectV_reduce的維數為n×n_selectT是矩陣轉置運算

最后，我們添加均值以得到原始圖像的最終PCA，如下所示：

理念

我們將通過選擇要使用的主分量n_select利用PCA來減小圖像尺寸，以便它僅存儲重要像素以保留原始圖像的特征，從而使其在存儲中更加有效。

我們的原始圖像包含三個顏色通道：紅色，綠色和藍色。 對于每個顏色通道，我們將像素視為具有（高度）觀察值和（寬度）特征的2D矩陣。 在lena.jpg中，我們有三個2D矩陣，其中包含220個觀測值和220個特征。

RGB通道的主要組件

在每個顏色通道上執行PCA，從而得到PCA投影（或分數）和主成分（軸），它們都將是形狀為220×220的矩陣形式。

res = []cum_var = []X_t = np.transpose(X)for channel in range(3): # SEPARATE EACH RGB CHANNEL pixel = X_t[channel].reshape(*ori_pixels.shape[:2]) # PCA pca = PCA(random_state = 123) pixel_pca = pca.fit_transform(pixel) pca_dict = { 'Projection': pixel_pca, 'Components': pca.components_, 'Mean': pca.mean_ } res.append(pca_dict) # EVALUATION cum_var.append(np.cumsum(pca.explained_variance_ratio_))

我們可以可視化每個顏色通道的主要成分，如下所示：

PC的可視化信息不足，隨機性很大。 我們應該引入一個稱為解釋方差的指標來評估PC性能。 取值范圍是0到100％，表示原始圖像和壓縮圖像之間的相似度。

cum_var_df = pd.DataFrame(np.array(cum_var).T * 100, index = range(1, pca.n_components_+1), columns = ['Explained Variance by Red', 'Explained Variance by Green', 'Explained Variance by Blue'])cum_var_df['Explained Variance'] = cum_var_df.mean(axis = 1)cum_var_df

重復試驗

在本節中，我們將重復以下步驟從n_select到n_select = 220：

區分PCA投影的前n_select列和組件的前n_select行 使用PCA建立公式和原始圖像 對紅色，綠色和藍色每個顏色通道重復步驟1-2。 將三種顏色通道的PCA重構組合為一個3D矩陣 保存指標值(解釋方差，圖像大小和顏色數量)以進行進一步優化 用越來越多的主成分繪制壓縮（重構）圖像

pca_results = []for n in range(1, pca.n_components_+1): # SELECT N-COMPONENTS FROM PC temp_res = [] for channel in range(3): pca_channel = res[channel] pca_pixel = pca_channel['Projection'][:, :n] pca_comp = pca_channel['Components'][:n, :] pca_mean = pca_channel['Mean'] compressed_pixel = np.dot(pca_pixel, pca_comp) + pca_mean temp_res.append(compressed_pixel.T) compressed_image = np.transpose(temp_res) pca_dict = { 'n': n, 'Pixels': compressed_image, 'Explained Variance': cum_var_df['Explained Variance'][n], 'Image Size (KB)': imageByteSize(compressed_image), 'No. of Colors': len(np.unique(np.uint8(compressed_image).reshape(-1, 3), axis = 0)) } pca_results.append(pca_dict)pca_results = pd.DataFrame(pca_results).set_index('n')pca_results.head()

PCA指標：主成分的最佳數量

在本節中，我們將嘗試搜索最佳數量的PC，以在達到預期的解釋方差的同時，使內存占用盡可能最小。

我們想通過分析解釋方差來獲得最佳主成分數，這是思考過程：左圖：我們需要19、33和73個主成分才能分別解釋原始圖像的方差的90％，95％和99％。中圖：但是需要權衡取舍，解釋方差越大，圖像尺寸就越大。 黑色虛線表示原始圖像尺寸，我們要在此線下方選擇n。 因此，選擇19或33個主成分。右圖：如果將n從19增加到33，然后再增加到73，則圖像中存在的顏色數量將減少。

從圖中可以得出結論，應當33個主成分，因為它給我們提供了較小的圖像大小和相當高的解釋方差，并且比使用19個主要成分更接近原始圖像。

與原始圖像進行比較

最后，讓對壓縮圖像和原始圖像進行比較。

relative_size = ori_vs_pca.loc['PC-Reduced', 'Image Size (KB)']/ori_vs_kmeans.loc['Original', 'Image Size (KB)']print('Reduction: {:.3f}% from original image size'.format((1-relative_size)*100))print('Explained Variance: {:.3f}%'.format(ori_vs_pca.loc['PC-Reduced', 'Explained Variance']))

縮小比例：原始圖像大小的6.825％解釋方差：95.072％

通過使用PCA，我們只能將圖像大小減小6.825％，并且壓縮后的圖像成功捕獲了原始圖像的95.072％的特征。 接下來，我們比較k-means和PCA的結果。

k-means和PCA的比較

我們考慮幾個指標，以比較使用k-means和PCA壓縮圖像的效果：

圖片大小（以千字節為單位）解釋方差圖像中存在的顏色數

reduction_kmeans = (1-final_compare.loc['Color-Reduced', 'Image Size (KB)'] / ori_img_size) * 100reduction_pca = (1-final_compare.loc['PC-Reduced', 'Image Size (KB)'] / ori_img_size) * 100print('Image Size Reduction using K-Means: {:.3f}%'.format(reduction_kmeans))print('Image Size Reduction using PCA: {:.3f}%'.format(reduction_pca))

使用k-means縮小圖像大小：79.012％使用PCA縮小圖像大小：6.825％

結論

我們使用無監督學習算法成功地實現了圖像壓縮，例如k-means聚類和使用主成分分析（PCA）進行降維。

在k-means中，通常通過可視化來主觀地選擇最佳聚類中心數k。 在這里，我們提出兩種選擇方法，即：

使用最長垂直距離的方法 使用有限差分法和二階導數

在PCA中，確定使用的PC數量首先要考慮解釋方差，然后還要考慮圖像大小減小的比例和減少顏色的數量，以分析它們與原始圖像的相似性。

使用k-means，圖像大小減小到79.012％，僅12種顏色就能解釋原始圖像的95.916％差異。 使用PCA，圖像大小減小僅為6.825％，并根據我們的目標解釋了95,072％的差異。 在經過PCA縮小的圖像中，與原始圖像相比，存在更多的顏色數量，表明存在噪音。 從主觀上可以看出，PCA壓縮的圖像更加粗糙。

與PCA相比，更建議使用k-means來縮小圖像尺寸，但是如果我們要保持原始圖像的整體色彩，請使用PCA。

另一個建議是嘗試連續執行兩種方法來進行圖像縮小，即先用k-means再用PCA，或是先用PCA再用k-means。

作者：Tomy Tjandra

deephub翻譯組：孟翔杰

到此這篇關于在Python中使用K-Means聚類和PCA主成分分析進行圖像壓縮的文章就介紹到這了,更多相關Python 圖像壓縮內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！