均值漂移（Meanshift）算法理解

1.均值漂移的基本概念：沿着密度上升方向寻找聚簇点

设想在一个有N个样本点的特征空间
初始确定一个中心点center，计算在设置的半径为D的圆形空间内所有的点（xi）与中心点center的向量
计算整个圆形空间内所有向量的平均值，得到一个偏移均值
将中心点center移动到偏移均值位置
重复移动，直到满足一定条件结束


 

2.均值漂移运算：

2.1 Mean shift的基础公式：
偏移均值

 
Sh:以x为中心点，半径为h的高维球区域； k:包含在Sh范围内点的个数； xi:包含在Sh范围内的点
中心更新


将中心点移动到偏移均值位置

 

Mt为t状态下求得的偏移均值;   xt为t状态下的中心


 

2.2 引入核函数的偏移均值：
核函数
核函数只是用来计算映射到高维空间之后的内积的一种简便方法，目的为让低维的不可分数据变成高维可分。利用核函数，可以忽略映射关系，直接在低维空间中完成计算。
引入核函数的偏移均值
在均值漂移中引入核函数的概念，能够使计算中距离中心的点具有更大的权值，反映距离越短，权值越大的特性。改进的偏移均值：



其中，x为中心点；xi为带宽范围内的点；n为带宽范围内的点的数量；g(x)为对核函数的导数求负


 

3.均值漂移的应用：

聚类（K均值聚类）
图像分割（将图像映射到特征空间，对采样点进行均值漂移聚类）
对象轮廓检验（光线传播算法）
目标跟踪（求解最优化Bhattacharya系数函数）


 

4.均值漂移运算步骤：


1、在未被分类的数据点中随机选择一个点作为中心点；

2、找出离中心点距离在带宽之内的所有点，记做集合M，认为这些点属于簇c。

3、计算从中心点开始到集合M中每个元素的向量，将这些向量相加，得到偏移向量。

4、中心点沿着shift的方向移动，移动距离是偏移向量的模。

5、重复步骤2、3、4，直到偏移向量的大小满足设定的阈值要求，记住此时的中心点。

6、重复1、2、3、4、5直到所有的点都被归类。

7、分类：根据每个类，对每个点的访问频率，取访问频率最大的那个类，作为当前点集的所属类。

均值漂移聚类算法
 聚类算法-均值漂移算法 (Clustering Algorithms - Mean Shift Algorithm)
 均值漂移算法简介 (Introduction to Mean-Shift Algorithm)
As discussed earlier, it is another powerful clustering algorithm used in unsupervised learning. Unlike K-means clustering, it does not make any assumptions; hence it is a non-parametric algorithm.
 如前所述，它是在无监督学习中使用的另一种强大的聚类算法。 与K均值聚类不同，它没有做任何假设； 因此它是一种非参数算法。 
Mean-shift algorithm basically assigns the datapoints to the clusters iteratively by shifting points towards the highest density of datapoints i.e. cluster centroid.
 均值漂移算法基本上是通过将数据点移向最高密度的数据点(即群集质心)来迭代地将数据点分配给群集。 
The difference between K-Means algorithm and Mean-Shift is that later one does not need to specify the number of clusters in advance because the number of clusters will be determined by the algorithm w.r.t data.
 K-Means算法和Mean-Shift算法之间的区别在于，后一种算法无需提前指定聚类数，因为聚类数将由算法的数据确定。 
 均值漂移算法的工作 (Working of Mean-Shift Algorithm)
We can understand the working of Mean-Shift clustering algorithm with the help of following steps −
 通过以下步骤，我们可以了解Mean-Shift聚类算法的工作原理： 
Step 1 − First, start with the data points assigned to a cluster of their own.
 步骤1-首先，从分配给它们自己的群集的数据点开始。 
Step 2 − Next, this algorithm will compute the centroids.
 步骤2-接下来，此算法将计算质心。 
Step 3 − In this step, location of new centroids will be updated.
 步骤3-在此步骤中，新质心的位置将被更新。 
Step 4 − Now, the process will be iterated and moved to the higher density region.
 步骤4-现在，该过程将被迭代并移至更高密度的区域。 
Step 5 − At last, it will be stopped once the centroids reach at position from where it cannot move further.
 步骤5-最后，一旦质心到达无法继续移动的位置，它将停止。 
 用Python实现 (Implementation in Python)
It is a simple example to understand how Mean-Shift algorithm works. In this example, we are going to first generate 2D dataset containing 4 different blobs and after that will apply Mean-Shift algorithm to see the result.
 这是一个了解均值漂移算法工作原理的简单示例。 在此示例中，我们将首先生成包含4个不同Blob的2D数据集，然后将应用Mean-Shift算法查看结果。 

%matplotlib inline
import numpy as np
from sklearn.cluster import MeanShift
import matplotlib.pyplot as plt
from matplotlib import style
style.use("ggplot")
from sklearn.datasets.samples_generator import make_blobs
centers = [[3,3,3],[4,5,5],[3,10,10]]
X, _ = make_blobs(n_samples = 700, centers = centers, cluster_std = 0.5)
plt.scatter(X[:,0],X[:,1])
plt.show()



ms = MeanShift()
ms.fit(X)
labels = ms.labels_
cluster_centers = ms.cluster_centers_
print(cluster_centers)
n_clusters_ = len(np.unique(labels))
print("Estimated clusters:", n_clusters_)
colors = 10*['r.','g.','b.','c.','k.','y.','m.']
for i in range(len(X)):
    plt.plot(X[i][0], X[i][1], colors[labels[i]], markersize = 3)
plt.scatter(cluster_centers[:,0],cluster_centers[:,1],
    marker=".",color='k', s=20, linewidths = 5, zorder=10)
plt.show()

Output
 输出量 

[[ 2.98462798 9.9733794 10.02629344]
[ 3.94758484 4.99122771 4.99349433]
[ 3.00788996 3.03851268 2.99183033]]
Estimated clusters: 3


 的优点和缺点 (Advantages and Disadvantages)
 优点 (Advantages)
The following are some advantages of Mean-Shift clustering algorithm −
 以下是Mean-Shift聚类算法的一些优点- 
It does not need to make any model assumption as like in K-means or Gaussian mixture.
 它不需要像K-means或高斯混合中那样做出任何模型假设。 
It can also model the complex clusters which have nonconvex shape.
 它还可以对具有非凸形状的复杂簇进行建模。 
It only needs one parameter named bandwidth which automatically determines the number of clusters.
 它只需要一个名为带宽的参数即可自动确定群集数。 
There is no issue of local minima as like in K-means.
 像K-means一样，没有局部最小值的问题。 
No problem generated from outliers.
 异常值不会产生任何问题。 
 缺点 (Disadvantages)
The following are some disadvantages of Mean-Shift clustering algorithm −
 以下是Mean-Shift聚类算法的一些缺点- 
Mean-shift algorithm does not work well in case of high dimension, where number of clusters changes abruptly.
 在集群数量突然变化的高维情况下，均值漂移算法不能很好地工作。 
We do not have any direct control on the number of clusters but in some applications, we need a specific number of clusters.
 我们无法直接控制集群的数量，但是在某些应用程序中，我们需要特定数量的集群。 
It cannot differentiate between meaningful and meaningless modes.
 它无法区分有意义的模式和无意义的模式。 
翻译自: https://www.tutorialspoint.com/machine_learning_with_python/clustering_algorithms_mean_shift_algorithm.htm
均值漂移聚类算法

均值漂移（Meanshift）算法理解

1.均值漂移的基本概念：沿着密度上升方向寻找聚簇点


设想在一个有N个样本点的特征空间

初始确定一个中心点center，计算在设置的半径为D的圆形空间内所有的点（xi）与中心点center的向量

计算整个圆形空间内所有向量的平均值，得到一个偏移均值

将中心点center移动到偏移均值位置

重复移动，直到满足一定条件结束


 

2.均值漂移运算：


2.1 Mean shift的基础公式：

偏移均值



Sh:以x为中心点，半径为h的高维球区域； k:包含在Sh范围内点的个数； xi:包含在Sh范围内的点

中心更新



将中心点移动到偏移均值位置

 

 

 

Mt为t状态下求得的偏移均值;   xt为t状态下的中心


 


2.2 引入核函数的偏移均值：

核函数

核函数只是用来计算映射到高维空间之后的内积的一种简便方法，目的为让低维的不可分数据变成高维可分。利用核函数，可以忽略映射关系，直接在低维空间中完成计算。

引入核函数的偏移均值

在均值漂移中引入核函数的概念，能够使计算中距离中心的点具有更大的权值，反映距离越短，权值越大的特性。改进的偏移均值：





其中，x为中心点；xi为带宽范围内的点；n为带宽范围内的点的数量；g(x)为对核函数的导数求负


 

3.均值漂移的应用：


聚类（K均值聚类）

图像分割（将图像映射到特征空间，对采样点进行均值漂移聚类）

对象轮廓检验（光线传播算法）

目标跟踪（求解最优化Bhattacharya系数函数）


 

4.均值漂移运算步骤：


 

1、在未被分类的数据点中随机选择一个点作为中心点；

 

2、找出离中心点距离在带宽之内的所有点，记做集合M，认为这些点属于簇c。

 

3、计算从中心点开始到集合M中每个元素的向量，将这些向量相加，得到偏移向量。

 

4、中心点沿着shift的方向移动，移动距离是偏移向量的模。

 

5、重复步骤2、3、4，直到偏移向量的大小满足设定的阈值要求，记住此时的中心点。

 

6、重复1、2、3、4、5直到所有的点都被归类。

 

7、分类：根据每个类，对每个点的访问频率，取访问频率最大的那个类，作为当前点集的所属类。


 

⚠️这篇是按4.1.0翻译的，你懂得。



⚠️除了版本之外，其他还是照旧，Meanshift and Camshift，附原文。


目标

在本章，

我们会学到均值漂移和连续自适应均值漂移算法来找出并追踪视频中的物体。
均值漂移

均值漂移背后的灵感很简单。假设即有一组点。(它可以是一个好像直方图反向投射出来的像素分布)。而你有一个小窗口(也许是个圆形的)然后你得移动那个窗口到最大点密度(或者窗口框住说最多点数量)的区域。如下图所示：



初始化的窗口由蓝色的圆"C1"来表示。它最初的圆心用蓝色的正方形"C1_o"标记出来了。但如果你找出这个圆形窗口中所有点的质心，你就会得到"C1_r"点(用蓝色小圆圈标出了)，它是这个圆实际的质心。很明显它们(质心和圆心)并不匹配，所以，移动窗口，使新窗口的圆圈与先前的质心相匹配。然后再次找到新的质心。很可能，它们还是不匹配。然后再继续递归移动这个圆圈，直到圆的中心和质心落在同一点(或者有一个小的期望误差)。最后得到的是一个具有最大像素分布的窗口。它用绿色的圆"C2"标记出来了。如图所示，它框住了最多的点。下面在一张静态图像上演示整个过程：



所以我们通常传入直方图的反向投影图像以及一个初始对象的位置。当这个对象移动的时候，移动明显会反映到直方图的反向投影图上。因此，均值漂移算法将窗口移动到具有最大的密度的新位置。

OpenCV里的均值漂移

要使用OpenCV里的均值漂移，首先我们需要设置目标对象，找出它的直方图，这样我们才能在每一帧上来进行反向映射，然后使用均值漂移算法。我们还需要提供窗口的初始位置。对于直方图，这里只考虑色调。此外，为了避免由于低光而产生的错误值，使用cv.inRange()函数丢弃低光值。

import numpy as np
import cv2 as cv
cap = cv.VideoCapture('slow.flv')
# take first frame of the video
ret,frame = cap.read()
# setup initial location of window
r,h,c,w = 250,90,400,125  # simply hardcoded the values
track_window = (c,r,w,h)
# set up the ROI for tracking
roi = frame[r:r+h, c:c+w]
hsv_roi =  cv.cvtColor(roi, cv.COLOR_BGR2HSV)
mask = cv.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
roi_hist = cv.calcHist([hsv_roi],[0],mask,[180],[0,180])
cv.normalize(roi_hist,roi_hist,0,255,cv.NORM_MINMAX)
# Setup the termination criteria, either 10 iteration or move by atleast 1 pt
term_crit = ( cv.TERM_CRITERIA_EPS | cv.TERM_CRITERIA_COUNT, 10, 1 )
while(1):
    ret ,frame = cap.read()
    if ret == True:
        hsv = cv.cvtColor(frame, cv.COLOR_BGR2HSV)
        dst = cv.calcBackProject([hsv],[0],roi_hist,[0,180],1)
        # apply meanshift to get the new location
        ret, track_window = cv.meanShift(dst, track_window, term_crit)
        # Draw it on image
        x,y,w,h = track_window
        img2 = cv.rectangle(frame, (x,y), (x+w,y+h), 255,2)
        cv.imshow('img2',img2)
        k = cv.waitKey(60) & 0xff
        if k == 27:
            break
        else:
            cv.imwrite(chr(k)+".jpg",img2)
    else:
        break
cv.destroyAllWindows()
cap.release()

下面给出我使用的视频中的其中三帧：



(译者附，该例中的使用的文件已经在git上被删除，我翻墙找到了。盘1nwTS8L3k-2sG0ry5bbrXYQ码7gi4)

连续自适应的均值漂移

你是否靠近去看了刚才那个结果呢？这里有个问题。我们的窗口在汽车处于远处和靠近摄像头的近处总是保持一个固定的大小。这不太好。我们得使窗口适应目标对象的大小和旋转角度。这个解决方案又一次来自"OpenCV Labs"，它被叫做CAMshift (连续自适应均值漂移) 由Gary Bradsky在他1998年的论文"Computer Vision Face Tracking for Use in a Perceptual User Interface"中发布。

它首先应用meanshift算法。一旦meanshift收敛，它就按公式来更新窗口的大小，同时还计算了最佳拟合椭圆的方向。它通过新的放缩搜索窗口和以前的窗口位置再次应用了均值漂移。此过程将继续迭代，直到达到所需的精度为止。



OpenCV里的Camshift

它也和均值漂移一样，但它返回了一个旋转之后的矩形(那就是我们需要的结果)，当然还有这个矩形的参数(用来传入下次迭代中的搜索窗口)。看下面的代码：

import numpy as np
import cv2 as cv
cap = cv.VideoCapture('slow.flv')
# take first frame of the video
ret,frame = cap.read()
# setup initial location of window
r,h,c,w = 250,90,400,125  # simply hardcoded the values
track_window = (c,r,w,h)
# set up the ROI for tracking
roi = frame[r:r+h, c:c+w]
hsv_roi =  cv.cvtColor(roi, cv.COLOR_BGR2HSV)
mask = cv.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
roi_hist = cv.calcHist([hsv_roi],[0],mask,[180],[0,180])
cv.normalize(roi_hist,roi_hist,0,255,cv.NORM_MINMAX)
# Setup the termination criteria, either 10 iteration or move by atleast 1 pt
term_crit = ( cv.TERM_CRITERIA_EPS | cv.TERM_CRITERIA_COUNT, 10, 1 )
while(1):
    ret ,frame = cap.read()
    if ret == True:
        hsv = cv.cvtColor(frame, cv.COLOR_BGR2HSV)
        dst = cv.calcBackProject([hsv],[0],roi_hist,[0,180],1)
        # apply meanshift to get the new location
        ret, track_window = cv.CamShift(dst, track_window, term_crit)
        # Draw it on image
        pts = cv.boxPoints(ret)
        pts = np.int0(pts)
        img2 = cv.polylines(frame,[pts],True, 255,2)
        cv.imshow('img2',img2)
        k = cv.waitKey(60) & 0xff
        if k == 27:
            break
        else:
            cv.imwrite(chr(k)+".jpg",img2)
    else:
        break
cv.destroyAllWindows()
cap.release()

结果的其中三帧显示如下：



额外资源

法语维基百科页面 Camshift。(本文中两个动图就是从这偷的。)
	
Bradski, G.R., "Real time face and object tracking as a component of a perceptual user interface," Applications of Computer Vision, 1998. WACV '98. Proceedings., Fourth IEEE Workshop on , vol., no., pp.214,219, 19-21 Oct 1998
练习

OpenCV 有一个 camshift 的 Python 例子在交互式示例上，使用它、破解它、理解它。
上篇：【翻译：OpenCV-Python教程】特征匹配加单应性找出物体 

下篇：【翻译：OpenCV-Python教程】光流