# MRF
**Repository Path**: kklei/MRF
## Basic Information
- **Project Name**: MRF
- **Description**: Markov Random Field
- **Primary Language**: Python
- **License**: MPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-04-11
- **Last Updated**: 2021-04-11
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# **Probabilistic Graphical Model**
- [**Probabilistic Graphical Model**](#probabilistic-graphical-model)
- [**Theory**](#theory)
- [**Markov Random Field**](#markov-random-field)
- [**MRF for Image Segmentation**](#mrf-for-image-segmentation)
- [**MRF for Image Denoise**](#mrf-for-image-denoise)
- [**TODO**](#todo)
- [**Implement**](#implement)
- [**Reference**](#reference)
> 概率图模型（PGM），形式上由图结构组成，图中一个节点（node）表示一个或一组随机变量，而node之间的连接为边（edge），表示变量之间的关系。根据图是否有向性分为两类：
- 有向图模型/贝叶斯网络（Bayesian Network），因果关系
- 无向图模型/马尔可夫随机场（Markov Random Field, MRF），相关关系
> Basic definition
- 先验：根据统计历史上的经验、常识当下事件发生的概率
- 关于某个变量 $p$ 的概率分布 $p(\theta)$
- 似然：当下事件由果及因发生的概率
- 对于结果 $x$，在参数集合 $\theta$ 上的似然，就是在给定这些参数值的基础上，观察到的结果的概率 $L(\theta|x)=p(x|\theta)$
- 后验：当下事件由因及果发生的概率
- 关于参数 $\theta$ 在给定的证据信息 $X$ 下的概率： $p(\theta|x)$。后验概率定义如下：(后验分布 正比于 先验分布 × 似然函数)
$$
p(\theta|x)= \frac{p(x|\theta)p(θ)}{p(x)}
$$
## **Theory**
### **Markov Random Field**
Figure 1: Example of MRF
> 如上图所示一个简单的MRF，其中edge表示node之间的相互关系，如$x_2$和$x_3$之间的相互关系可用势函数度量：
$$
\psi(x_2, x_3) = \begin{cases} 2, & x_2 = x_3 \\ 0.1, & otherwise \\ \end{cases}
$$
> 这样说明模型偏向于$x_2$和$x_3$取相同的值。势函数刻画了局部变量之间的相关关系，它应该是非负的函数。为了满足非负性，指数函数常被用于定义势函数：
$$
\psi(x) = e^{(-H(x))}
$$
> $H(x)$为变量$x$上的实值函数，常见形式为：
$$
H(x) = \sum_{u,v \in x, u\ne v} \alpha_{uv}x_ux_v + \sum_{v\in x} \beta_{v}x_v
$$
> 其中 $\alpha_{uv}$ 和 $\beta_{v}$ 是需要学习的参数，称为参数估计。
> 将模型变量的联合概率分布分解为一组子集概率分布乘积？
- 全局马尔可夫性（global Markov property）
$$
p(x_{A},x_{B}|x_{C}) = P(x_{A}|x_{C})P(x_{B}|x_{C})
$$
- 局部马尔可夫性（local Markov property）
$$
p(x_{v},x_{o}|x_{w}) = P(x_{v}|x_{w})P(x_{o}|x_{w})
$$
- 成对马尔可夫性（pairwise Markov property）
$$
p(x_{i},x_{j}|x_{\setminus{i,j}}) = P(x_{i}|x_{\setminus{i,j}})P(x_{j}|x_{\setminus{i,j}})
$$
>> 其中 $x_{\setminus{i,j}}$ 表示所有 $x$ 变量除去 $x_i$ 和$x_j$ 的集合。
> 团（Clique）：图节点的子集，子集中任意节点间有边相连。若在一个团中加入其他任何节点都不再形成团，则称该团为极大团。
Figure 2: Example of Clique
> 其中，$x_1$和$x_2$是一个团，$x_2$、$x_3$、$x_4$也是一个团，并且为极大团。在MRF中，多个变量联合概率分布可以基于团分解为多个势函数乘积，每个团为一个势函数。所以Fig.1中联合概率分布 $p(x)$ 定义为
$$
p(x) = \frac{1}{Z}\psi_{12}(x_1, x_2)\psi_{16}(x_1, x_6)\psi_{23}(x_2, x_3)\psi_{56}(x_5, x_6)\psi_{245}(x_2, x_4, x_5)
$$
>> Z为归一化因子
#### **MRF for Image Segmentation**
- 将图像分割问题转化为图像的标记（label）问题。
- 标记场是用来对待测对象的像素进行跟踪标记，特征场是拟合原始的观测数据，尽可能准确的反映每一个像素位置的特征信息，使图像分割的结果能保留更多的细节信息。
> 根据贝叶斯估计准则和最大后验概率准则，将后验概率转换为先验概率和似然函数的乘积，其中，似然函数视为一个高斯分布，先验概率通过MRF转换为Gibbs分布得到。最后更新标记场使得概率最大，得到最佳分割。
- Markov随机场描述图像的局部性质，Gibbs随机场由随机场的全局性质来刻画。
- Harmmersley-Clifford定理：邻域系统 M 在集合 S 中，若 S 上随机场 X 符合Gibbs随机场，那么 X 也是一个Markov随机场。
> 图像 $Y$ 大小为 $M*N$，对于图像中任意一个像素 $y_{i}$ 分割后对应的标记为 $x_i$，两个随机场定义为：
- $X=\{x_i, i\in S\}$ 是图像分割后的类别标号，$x_i=1,2,···L$ 表示分割成L个区域，但是其类别状态不能直接观测到。
- $Y=\{y_i, i \in S\}$ 是可观测的随机场，即图像的灰度场。
> 分割问题描述为：
- 根据贝叶斯准则，最优分割准则为：
$$
\hat{X} = {\underset{X}{arg\,max}}\, p(X|Y) = {\underset{X}{arg\,max}}\, \frac{p(Y|X)p(X)}{p(Y)} \propto {\underset{X}{arg\,max}}\, p(Y|X)p(X)
$$
> 对于给定的图像，$Y$ 已知，$p(Y)$为常数，所以上式等价于：${\underset{X}{arg\,max}}\, p(Y|X)p(X)$
> 而随机场X是MRF，具有正概率性和Markov性。由MRF与Gibbs分布的等价性可知：
$$
p(X) = \prod_{i=1}^{M\ast N}p(x_i) = \frac{\prod_{i=1}^{M\ast N} exp(-\sum_{c\in C} V_c(x_i))}{\sum_{x_i=1}^{L} exp(-\sum_{c\in C} V_c(x_i))}
$$
> 式中$V_c(x_i)$是包含$x_i$的基团$c$的势函数，$C$是所有基团的集合。
> 观测量似然概率：（通常认为像素强度值服从高斯分布）
$$
p(y_i|x_i) = \frac{1}{\sqrt{2\pi}\sigma_{x_i}}exp(-\frac{(y_i-\mu_{x_i})^2}{2\sigma_{x_i}^2})
$$
> 对于定义的Clique potentials有以下值：
- singleton: $= \log P(Y|X)$
- doubleton:
$$V_{c_2}(i, j)=\beta \delta(x_i, x_j)=\begin{cases} -\beta, & x_i = x_j \\ +\beta, & otherwise \\ \end{cases}$$
> MRF模型的能量方程：
$$
U(X) = \sum_i (\log {\sqrt{2\pi}\sigma_{x_i}} + \frac{(y_i-\mu_{x_i})^2}{2\sigma_{x_i}^2}) + \sum_{i, j}\beta\delta(x_i, x_j)
$$
- Recall:
$$
p(X|Y) = \frac{1}{Z}exp(-U(X)) = \frac{1}{Z}exp(-\sum_{c \in C}V_c(X))
$$
- Hence:
$$
\hat{X}^{MAP} = \underset{X\in \Omega}{arg\,max}\,P(X|Y) = \underset{X\in \Omega}{arg\,min}\, U(X)
$$
> 一般采用条件迭代模式（ICM）方法，逐像素的最大化条件概率来更新结果。
#### **MRF for Image Denoise**
- 主要是深刻理解 **势函数**，假若给二值图加入噪声，得到观测的图像$Y$，实际图像为$X$，我们目标是通过$Y$来推断出$X$。
- 噪声较小，$x_i$和$y_i$之间有很强的相关性，同时图像相邻像素$x_i$和$y_i$的相关性也很强。
> 势函数定义为：
$$
E(x, y) = h\sum_i x_i - \beta\sum_{\{i,j\}} x_iy_i - \eta\sum_i x_iy_i
$$
> 包含两种团块，第一种是 $x_i$和$y_i$，第二种是$x_i$和相邻像素$x_j$。给不同的系数来调节势函数中的权重。计算概率$p(x,y)=\frac{1}{Z}exp\{-E(x,y)\}$最大，即$E(x,y)$最小。
## **TODO**
- MRF
- [x] [Segmentation](./mrf_aca.py)
- [x] [Denoise](./mrf_denoise.py)
- [ ] Validation
## **Implement**
- Environment
- Python3
- numpy
- cv2 or scipy or PIL
- matplotlib
- ...
- Results Visualization
- MRF
- Segmentation
- Denoised
## **Reference**
-
-
- ...
