二
：
【
算
法
】
1.
【
前
置
理
论
】
(1).
最
小
割
割
：对一个网络流图 G=(V,E)，将所有点划分为 S 和 T=V-S 两个集合，其中
源点 st\in S、汇点 ed\in T。
最
小
割
：最小化 \sum_{a\in S,b\in T}c(u,v)，即从 S 集合到 T 集合所有边
的容量之和。
GrabCut 算法中对一种前景/背景的分割方式构造能量函数作为代价。
目标为最小化分割代价。
(2).
高
斯
混
合
模
型
(GMM)
高斯分布（正态分布）：N(x|\mu,\sigma^2)=\frac{1}
{\sqrt{2\pi}\sigma}\exp({-\frac{(x-\mu)^2}{2\sigma^2}})，其中 \mu 为均
值，\sigma^2 为方差
d 维高斯分布：N(\boldsymbol x|\boldsymbol \mu,\boldsymbol
\Sigma)=\frac{1}{\sqrt{(2\pi)^d|\boldsymbol \Sigma|}}\exp(-\frac{1}{2}
(\boldsymbol x-\boldsymbol \mu)^T\boldsymbol \Sigma^{-1}
(\boldsymbol x-\boldsymbol \mu))，其中 \boldsymbol x 为 d 维向量，
\boldsymbol \mu 为 d 维均值向量，\boldsymbol \Sigma 为 d\times d
的协方差矩阵。
高
斯
混
合
模
型
(\text{Gaussian Mixture Model})：K 个高斯分量的混合模
型。简称 \text{GMM}。
K 分量 \text{GMM} 概率密度公式：
P(x)=\sum\limits_{k=1}^{K}P(k)P(x|k)=\sum\limits_{k=1}^{K}w_k
N(x|\mu_k,\Sigma_k)，其中 w_k\geqslant
0,\sum\limits_{k=1}^{K}w_k=1）
w_k 表示第 k 个高斯分量的权重系数，即选择第 k 个分量的概率。
一个 \text{GMM} 中有三组参数：\boldsymbol \theta=\
{\boldsymbol w,\boldsymbol \mu,\boldsymbol \Sigma\} 。
GrabCut 算法中使用两个 d 维高斯混合模型分别对图像前景、背景进
行建模，其中 d 为图像颜色维度。
(3).
极
大
似
然
似
然
函
数
：有 N 个数据点，服从某种分布 Pr(x;\theta)，我们想找到一组参
数 \theta，使得生成这些数据点的概率最大，即求
\arg\max\limits_{\theta}\prod\limits_{i=1}^{N}Pr(x_i;\theta)。
对
数
似
然
函
数
：\arg\max\limits_{\theta}\sum\limits_{i=1}^{N}\ln
(Pr(x_i;\theta))
用 \text{GMM} 来表示数据分布，则预测样本时使用的对数似然函数为：
\arg\max\limits_{\theta}\sum\limits_{i=1}^{N}\ln
\left(\sum\limits_{k=1}^{K}w_k N(x|\mu_k,\Sigma_k)\right)
这里我们并不知道每个样本点 x_i 属于哪个高斯分量，而是寻找一组参
数 \boldsymbol \theta=\{\boldsymbol w,\boldsymbol
\mu,\boldsymbol \Sigma\} 让似然函数最大。
GrabCut 算法为最小化总能量，用的是分布概率的
负
对
数
，即
\arg\min\limits_{\theta}\sum\limits_{i=1}^{N}-\ln (Pr(x_i,\theta))
2.
【
迭
代
能
量
最
小
化
】
(1).
【
能
量
函
数
和参
数
】
图像颜色维度为 d。
z_n 表示每个像素点的颜色信息向量 ，\alpha_n=1/0 表示每个像素点划分
给前景/背景。
对前景、背景分别建一个 d 维 K 分量高斯混合模型
P^{(\alpha=1)},P^{(\alpha=0)}。取 K=5。
\boldsymbol \theta 为两个 \text{GMM} 的学习参数，\boldsymbol
\theta_n=\{\boldsymbol w^{(\alpha)},\boldsymbol
\mu^{(\alpha)},\boldsymbol \Sigma^{(\alpha)}\}。
能
量
函
数
：E(\boldsymbol z,\boldsymbol \alpha,\boldsymbol
\theta)=U(\boldsymbol z,\boldsymbol \alpha,\boldsymbol
\theta)+V(\boldsymbol z,\boldsymbol \alpha,\boldsymbol \theta)，其中
U 为区域项，V 为边界项。
表示使用当前参数进行前/背景划分的代价。
区
域
项
：U(\boldsymbol z,\boldsymbol \alpha,\boldsymbol
\theta)=\sum\limits_{n} -\ln(P^{(\alpha_n)}(z_n)) =\sum\limits_{n} -\ln
\left(\sum\limits_{k=1}^{K}\boldsymbol w_k^{(\alpha_n)} P^{(\alpha_n)}
(z_n|{k})\right)
