標籤：

圖像處理聚類演算法計算機視覺

K-means,Mean-shift,Cam-shift串燒

07-16

K-means,Mean-shift,Cam-shift串燒

來自專欄楊喬的視覺演算法小屋4 人贊了文章

一直覺得這一系列演算法頗有淵源，卻沒有深究，最近查了一些資料，寫下這個文章，記錄備忘。

我是知識的搬運工

k-means

k-means演算法做機器學習的朋友肯定都很熟悉。

維基百科上面這樣說 k-means演算法：

k-平均演算法源於信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行於數據挖掘領域。k-平均聚類的目的是：把 $n$ 個點（可以是樣本的一次觀察或一個實例）劃分到k個聚類中，使得每個點都屬於離他最近的均值（此即聚類中心）對應的聚類，以之作為聚類的標準。這個問題將歸結為一個把數據空間劃分為Voronoi cells的問題。

現在的k-means多用於聚類，也可用於圖像壓縮。

下面摘抄一段 PR-ML 上面對於k-means演算法的推導過程

我們有一個數據集 ${x_1,.....,x_n}$ ，我們的目標是把這個數據集分成 $n$ 類。

聚類的策略是 找到數據點分別屬於的類別，以及一組向量 ${u_k}$ ，使得每個數據點和與它最近的向量 $u_k$ 之間的距離最小

$J=sum^n_{n=1}sum_{k=1}^kr_{nk}||x_n - u_k||^2$

其中的 $r_{nk}$ 表示，如果數據點 $x_n$ 被分到 $k$ 類，那麼 $r_{nk}$ 為1,否則是零。

那麼現在需要做的就是 $minJ$

這個式子中有兩個待求量， $r_{nk},u_k$ 。

那麼可以分兩步：

固定 $u_k$ 優化 $r_{nk}$ ，使 $J$ 最小。
固定 $r_{nk}$ 優化 $u_k$ ，使 $J$ 最小。

對於第一步，在固定 $u_k$ 的情況下，我們只需要將數據點 $x_n$ 分到離它最近的均值點，即 $r_{nk}=1$

對於第二部，在固定 $r_{nk}$ 的情況下，取目標函數對 $u_k$ 的偏導數，令其為零。有

$2sum^N_{n=1}r_{nk}(x_n-u_k)=0$

$Rightarrow u_k = frac{sum^n_{n=1}r_{nk}x_n}{sum^n_{n=1}r_{nk}}$

即令 $u_k$ 為上一步產生的新的 $k$ 類別的均值。

所以得名 k-means演算法。

實際上 k-means是廣義期望最大演算法的一種形式，我在 EM演算法優化混合高斯建模中寫過推導過程，可以得出同樣結果。

k-means演算法有兩個主要的缺點：

需要先知道k值，如果k值取得不好，效果可能很差。
k-means收斂到局部最優，所以這個演算法優化結果依賴於初始點選取。

k-means演算法在圖像方面可以用來圖像壓縮。

另一方面，k-means演算法與徑向基函數網路也頗有淵源。

k-means演算法的聚類策略是基於數據點間的歐式距離。

而徑向基函數的定義是 $varphi (||x_i-x_j||)$ ，那麼這兩者之間可以說是有聯繫了。

下面主要摘錄用k-means演算法來構建與訓練徑向基函數網路相關知識。

徑向基函數網路是一個三層網路

輸入層： m個節點，m表示輸入數據 $X$ 的維度。
隱含層： K個節點，激活函數使用 $varphi_j(X) = varphi(||X-X_j||)$ 。
輸出層：任意一種線性判別器。

我們重點關注其中的隱含層：

隱含層的作用是將線性不可分的輸入數據通過徑向基函數映射到高維空間（高維空間的維度直接由隱含層的數量決定）,使其線性可分。

其中徑向基函數的中心 $X_j$ 由數據集 $X$ 通過k-means聚類產生。

這樣就做到了，某一類相似的樣本，激活一個隱含層神經元。

輸出層的作用是線性判別，輸出層與隱含層之間的權重，可以通過在線最小二乘迭代法計算。

Mean-shift

mean-shift演算法形式與k-means演算法十分相似，應該是一脈相承，同氣連枝的。

其迭代更新公式為：

$m(x) = frac{sum_{x_iin N_x}K(x_i-x)x_i}{sum_{x_iin N_x}K(x_i-x)}$

其中 $K(x_i-x)$ 代表核函數，可用高斯核進行距離估計

$k(x_i-x) = e^{-c||x_i-x||^2}$

$N(x)$ 表示 $x$ 的鄰域，在這個鄰域內使用距離估計，鄰域外為零。

和上面的k-means迭代公式進行比較，可知：

mean-shift是在已經知道數據點標籤的情況下，迭代尋找最優中心點的過程。

我們來推導一下：

取目標函數： $f(x) = sum K(x_j-x) = sum e^{-c|||x_j-x||^2}$

求其對 $x$ 的導數：

$igtriangledown f = sum K(x_j-x)*[2c(x_j-x)]$

$frac{ igtriangledown f}{2c} =sum K(x_j-x)(x_j-x)$

$frac{ igtriangledown f}{2c} = sum K(x_j-x)x_j-sum K(x_j-x)x$

$frac{ igtriangledown f}{sum K(x_j-x)} =frac {sum K(x_j-x)x_j}{sum K(x_j-x)}-x = Delta x$

由上式可以看出，

mean-shift演算法每一步調整的方向，是沿著核函數的和的梯度方向，這與上面k-means演算法的推導是相一致的。
還可以看出 $Delta x$ 是自適應的，它反比於 $sum K(x_j-x)$ 。

mean-shift在圖像領域有許多應用。

第一個應用就是運動目標跟蹤

圖來自 opencv官網

基於mean-shift的跟蹤主要是通過直方圖的反向投影來獲得目標在圖像中位置的概率估計，從概率估計圖中使用均值漂移到概率最大點。

實際上，使用 mean-shift相當於兩個過程：

使用核函數對原概率圖進行濾波。
在濾波後的圖像上執行梯度上升。

這個演算法啟發我們，可以通過計算目標在圖像中的後驗概率估計，從生成的概率圖片中執行梯度上升來搜尋目標。但是，這種方法實際上只有在有前後時間關係的視頻中起作用，因為後驗概率在圖片中的分布不是一個全局凸函數。這是做圖像目標定位的根本難點，凸優化理論基本不能用。

第二個應用是圖像濾波，實際上也有一點圖像分割、圖像壓縮的味道。

思路是： 對圖像中每一個點都執行一次特定半徑的均值漂移，用收斂點的均值像素值代替原來點的像素值。

實際上說這樣的演算法是濾波也不太合適，說是完全的圖像分割也不太合適。

它起到的效果是讓色彩、位置相近的區域變成一塊區域，其中相近的程度取決於所選擇的核大小。而且，如果一塊色彩區域比核的大小要小，那麼它可能會消失掉。

圖片來自GitHub

在查找mean-shift資料時，我發現相關理論不少，我會新開一欄，仔細深入的介紹。

Cam-shift

cam-shift又是在mean-shift基礎上的升華。

在mean-shift演算法中，如何選擇窗口大小，是一個問題，窗口選的太大，太小都不好。

尤其是在一個視頻序列中，如果你需要跟蹤的目標物迎面走來或者背馳而去，那麼目標物的尺度大小都會發生顯著的變化。

cam-shift是作用在視頻序列上面的，它先用mean-shift演算法找到物體中心點，再通過計算物體的二階矩來加上一些先驗知識來產生迭代公式，具體的演算法我也沒有看懂，等待機緣，懂了再補上。

推薦閱讀：

※Unified Spectral Clustering with Optimal Graph
※信息檢索の扁平聚類：Flat Clustering
※凝聚式層次聚類演算法的初步理解
※K-Means原理分析與手動實現
※譜聚類演算法

TAG:計算機視覺 | 聚類演算法 | 圖像處理 |