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

更新時間：2020年04月10日 10:30:04 作者：deephub

這篇文章主要介紹了在Python中使用K-Means聚類和PCA主成分分析進(jìn)行圖像壓縮，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

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

# image processing
from PIL import Image
from io import BytesIO
import webcolors

# data analysis
import math
import numpy as np
import pandas as pd

# visualization
import matplotlib.pyplot as plt
from importlib import reload
from mpl_toolkits import mplot3d
import seaborn as sns

# modeling
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
from sklearn.preprocessing import MinMaxScaler

探索圖像

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

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編碼。讓我們確定圖像的其他屬性，即圖像大小（以千字節(jié)（KB）為單位）和原色的數(shù)量。

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

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

接下來，讓我們計(jì)算圖像的差異作為壓縮結(jié)果的基準(zhǔn)。

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聚類是一種常用的無監(jiān)督學(xué)習(xí)算法，用于將數(shù)據(jù)集劃分為k個聚類中心，其中k必須由用戶預(yù)先指定。該算法的目標(biāo)是將現(xiàn)有數(shù)據(jù)點(diǎn)分類為幾個集群，以便：

同一集群中的數(shù)據(jù)盡可能相似
來自不同集群的數(shù)據(jù)盡可能不同

每個集群由聚類中心表示，聚類中心是聚類數(shù)據(jù)點(diǎn)的平均值。這是算法：

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

請注意，結(jié)果可能并不理想，因?yàn)樗Q于隨機(jī)的初始化。

理念

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

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

像素值的三維圖

簡單的例子

在我們對顏色數(shù)k使用各種值進(jìn)行迭代之前，讓我們使用k = 2來了解我們的目的。到本節(jié)末，我們希望圖像只有2種顏色。首先，我們創(chuàng)建一個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值轉(zhuǎn)換為其英文顏色名稱：

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_name
kmeans_df["Color Name"] = list(map(get_colour_name, np.uint8(kmeans.cluster_centers_)))
kmeans_df

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

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_pixels
new_pixels = replaceWithCentroid(kmeans)

我們的聚類步驟已經(jīng)完成，讓我們看一下壓縮圖像的結(jié)果。

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的形狀。在視覺上，我們可以比較原始圖像相似與壓縮圖像是否相似。但是，我們?nèi)绾斡贸绦蜃龅竭@一點(diǎn)？讓我們介紹一組評估壓縮圖像的指標(biāo)：

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

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

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

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

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.314189
BCSS: 193071692.34763986
Explained Variance: 63.861%
Image Size: 4.384 KB

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

重復(fù)試驗(yàn)

在本節(jié)中，我們將在𝑘= 2到𝑘= 20之間重復(fù)此步驟：

執(zhí)行k-means以獲取每個像素的聚類中心和聚類標(biāo)簽
將每個像素替換為其聚類中心。
保存指標(biāo)值以進(jìn)行進(jìn)一步優(yōu)化：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

聚類指標(biāo)：最佳的顏色種類數(shù)

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

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

用直線連接曲線的第一個和最后一個點(diǎn)
計(jì)算每個點(diǎn)到該線的垂直距離
將距離最長的點(diǎn)視為拐點(diǎn)

下一個問題，如何在步驟2中計(jì)算垂直距離？很簡單，我們可以使用從點(diǎn)（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]

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

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

forward差異：

backward差異：

中心差異：

其中：

f'（x）是函數(shù)f（x）的一階導(dǎo)數(shù)
h是步長，在這種情況下，h = 1（顏色數(shù)的步長）
O（h）是一級誤差項(xiàng)
O（h²）是二次誤差項(xiàng)

由于中心差異具有較高的度數(shù)誤差項(xiàng)，因此預(yù)期它會比其他兩個差異產(chǎn)生更好的結(jié)果。我們僅對第一個點(diǎn)使用前向差異，對最后一個點(diǎn)使用后向差異。

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]

讓我們搜索每個指標(biāo)的最佳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

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

與原始圖像進(jìn)行比較

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

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％，這真是太好了！接下來，我們執(zhí)行PCA，看看它是否可以優(yōu)于k-means。

主成分分析（PCA）

概念

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

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

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

其中：

Z_reduce的尺寸為m×n_select
V_reduce的維數(shù)為n×n_select
T是矩陣轉(zhuǎn)置運(yùn)算

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

理念

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

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

RGB通道的主要組件

在每個顏色通道上執(zhí)行PCA，從而得到PCA投影（或分?jǐn)?shù)）和主成分（軸），它們都將是形狀為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的可視化信息不足，隨機(jī)性很大。我們應(yīng)該引入一個稱為解釋方差的指標(biāo)來評估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

重復(fù)試驗(yàn)

在本節(jié)中，我們將重復(fù)以下步驟從n_select到n_select = 220：

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

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指標(biāo)：主成分的最佳數(shù)量

在本節(jié)中，我們將嘗試搜索最佳數(shù)量的PC，以在達(dá)到預(yù)期的解釋方差的同時，使內(nèi)存占用盡可能最小。

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

從圖中可以得出結(jié)論，應(yīng)當(dāng)33個主成分，因?yàn)樗o我們提供了較小的圖像大小和相當(dāng)高的解釋方差，并且比使用19個主要成分更接近原始圖像。

與原始圖像進(jìn)行比較

最后，讓對壓縮圖像和原始圖像進(jìn)行比較。

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的結(jié)果。

k-means和PCA的比較

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

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

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

使用k-means縮小圖像大?。?9.012％
使用PCA縮小圖像大?。?.825％

結(jié)論

我們使用無監(jiān)督學(xué)習(xí)算法成功地實(shí)現(xiàn)了圖像壓縮，例如k-means聚類和使用主成分分析（PCA）進(jìn)行降維。

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

使用最長垂直距離的方法
使用有限差分法和二階導(dǎo)數(shù)

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

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

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

另一個建議是嘗試連續(xù)執(zhí)行兩種方法來進(jìn)行圖像縮小，即先用k-means再用PCA，或是先用PCA再用k-means。

作者：Tomy Tjandra

deephub翻譯組：孟翔杰

到此這篇關(guān)于在Python中使用K-Means聚類和PCA主成分分析進(jìn)行圖像壓縮的文章就介紹到這了,更多相關(guān)Python 圖像壓縮內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: