模式分析（一）概率密度估计及Meanshift算法

2020-04-04 本文已影响0人升不上三段的大鱼

一、概率密度估计

概率密度估计，简单说就是从离散的数据中估计出连续的概率密度函数。这里的离散数据即收集到的样本，它们来自的类别可能拥有某种统计学上的特征。最常见的密度估计方法是直方图，直方图是一种很直观的对数据样本分布进行可视化的方法。
概率密度估计可以分为参数估计和非参数估计：

参数估计：假设数据服从某一个分布（比如高斯分布），并从数据样本估计概率密度函数的参数，比如HMM, MLE等。
非参数估计：模型能估计出任意分布的数据，比如核密度估计。

二、Meanshift算法

图像的特征空间是一个基于输入的映射，输入图像上的一个小的自己映射到多维空间上的一个点，当整个输入都被映射到特征空间里，特征空间里的密度分布就能反映出输入的特征。结构位置的特征空间只能用非参数估计的方法分析，有两类非参数聚类方法：分层聚类核密度估计。密度估计的基本原理是把特征空间看作是一个所表示参数的概率密度函数，密集的区域就对应着概率密度函数的区域最大值，也就是这个未知分布的模式,然后就能得到相应的聚类。

1. 核密度估计

核密度估计是最常用的密度估计方法，给定 $n$ 个数据点 $x_{i}, i =1,2,...n$ ，分布在 $d$ 维空间 $R^d$ ，有多变量核密度估计的核 $K(x)$ ，对称正定带宽矩阵 $H$ ，在点 $x$ 得到的 $\hat{f}(x) = \frac{1}{n}\sum\limits_i^nK_{H}(x-x_{i})$ ，其中 $K_{H}(x) = |H|^{-1/2}K(H^{-1/2}x)$
常用的带宽矩阵 $H = h^2I$ ，只用一个参数 $h$ ，简化了运算，带入上面的核密度估计公式可以得到 $\hat{f}(x) = \frac{1}{nh^d}\sum\limits_i^nK(\frac{x-x_{i}}{h})$
$h^d：d$ 维空间里边长为 $h$ 的多为立方体的体积
核密度估计的用密度和它的估计值之间的均方差来判断。Epanechnikov核有最小的渐进逼近均方差， $K_{E}(x) = \begin{cases} 1-x & \quad \text{if } 0<=x <=1\\ 0 & \quad \text{if } x>1 \end{cases}$
Epanechnikov核在边界不可分，所以也常用
$K_{N}(x) = exp(-\frac{1}{2} x)$
带入核密度公式之后概率密度估计公式可以写为 $\hat{f}_{h,K}(x) = \frac{c_{k,d}}{nh_{d}}\sum\limits_i^nk(\|\frac{x-x_{i}}{h}\|^2)$
分析 $f(x)$ 的特征空间的第一步，就是找到它的模式（mode），mode它一般都在梯度为0的位置，而 mean shift 是一个不需要估计密度就能找到0的方法。

2. 密度梯度估计

上面的公式求梯度 $\nabla\hat{f}_{h,K}(x)= \frac{2c_{k,d}}{nh_{d+2}}\sum\limits_i^n(x-x_{i})k'(\|\frac{x-x_{i}}{h}\|^2)$
定义 $g(x) = -k'(x)$ ，可以得到 $\nabla\hat{f}_{h,K}(x)= \frac{2c_{k,d}}{nh_{d+2}}\sum\limits_i^n(x-x_{i})g(\|\frac{x-x_{i}}{h}\|^2)$
$= \frac{2c_{k,d}}{nh_{d+2}}[\sum\limits_i^ng(\|\frac{x-x_{i}}{h}\|^2) ][\frac{\sum\limits_i^nx_{i} g(\|\frac{x-x_{i}}{h}\|^2)}{\sum\limits_i^n g(\|\frac{x-x_{i}}{h}\|^2)} -x]$
第二项总是正数，所以只要第三项为0，梯度变为0，得到mean shift $m_{h,G}(x) = \frac{\sum\limits_i^nx_{i} g(\|\frac{x-x_{i}}{h}\|^2)}{\sum\limits_i^n g(\|\frac{x-x_{i}}{h}\|^2)} -x$
也就是一个范围内的数据点的权重均值与中心点 $x$ 的差。
mean shift的步骤就是重复：

计算mean shift向量 $m_{h,G}(x)$
根据向量移动核 $G(x)$ 的窗口到下一个中心点
直到收敛到梯度为0的点。
核 $G(x)$ 的中心点为 $y_{j+1} = \frac{\sum\limits_i^nx_{i} g(\|\frac{x-x_{i}}{h}\|^2)}{\sum\limits_i^n g(\|\frac{x-x_{i}}{h}\|^2)}$ j=1,2,...

3. Mean shift 的应用

Mean shift滤波，做图像平滑去噪等，以及图像分割。

参考文献：
[1] Comaniciu D, Meer P. Mean shift: A robust approach toward feature space analysis[J]. IEEE Transactions on pattern analysis and machine intelligence, 2002, 24(5): 603-619.