Random Walk Algorithm

作者: 张王李刘赵孙杨 | 来源:发表于2018-11-22 21:24 被阅读9次

Random Walk Algorithm
random walk
DeepWalk
Final Project:Random Systems
[R] random walk
random walk in python
Technical support web site (URL)
Final Project
基于随机森林的enhancer预测算法
算法与数据结构第一弹

简介

Random Walk 算法是比较早的一种基于图的方法，其原始论文[1]最早发在一个会议上, 后来经过修整发在期刊上[2].

其主要思想是将图像构建成一个无向图模型，然后通过求解对应的dirichlet问题[3, 4]得到分割结果。

本文主要介绍一些random walker算法的原理，推导过程以及一些实验结果。

基于图的分割算法基本概念

图的基本概念

基于图的分割方式被广泛使用在自然图像以及医学图像分割中，如 graph_cut, grab cut, MRF-MAP, CRF, fc-crf等等一些方法，本文主要介绍基于图的其中一种方法，叫random walk算法。

首先简要介绍一些图的基本概念：

一个图模型是一组节点和边的集合： $G=(V,E)$ ,其中 $v\in V$ 叫做图节点(vertices, nodes), $e\in E \subseteq V \times V$ 叫做图像的边，连接了一个图像的两个节点 $v_i v_j$ 的边我们用 $e_{ij}$ 表示。

每一条边我们都给它定义一个权重 $w_{ij}$ ,注意，这里的权重需要满足 $w_{ij}>0$ 。

还有一个概念是一个节点的度（degree）我们定义如下：
$\begin{equation} \tag{1} d_i = \sum{w(e_{ij})} \end{equation}$
这个意思是每个节点的度等于和它相连的边上的权重之和，表示了这个节点的一个属性。

下面的这个图就是一种将我们常见的2维图像表达成图的一种方式（注意，我这里说的是一种方式，说明还有其他的方式，比如下图定义的是节点之间4连通的方式，我们还可以定义为8连通的方式，甚至定义为全连接的方式）。其中圆圈就表示图像的每个像素，相连的曲线就表示每一条边，并且这个边还有一个对应的权重。

一种将2维图像用图表达的方式

权重

在基于图的图像分析算法中，权重是一个基本的概念.一般来说,我们用一个函数来表达两个节点之间的权重,从而可以有各种各样的函数来表示它.这里随机游走算法使用的是高斯权重,其表达是如下:

$\begin{equation} \tag{2} w_{ij} = exp(- \beta (g_i -g_j)^2) \end{equation}$

其中 $g_i$ 表示图像第i个节点处(也就是像素i)的灰度值.

因此这个权重的意义我们可以理解如下,如果两个相邻像素的灰度值越接近,那么他们之间的权重越大,因此他们之间的联系也就越大.

Laplacian Martix (拉普拉斯矩阵)

拉普拉斯矩阵[4]可以反映出一个图的很多有用信息,其定义方式如下.
$\begin{equation} \tag{3} L_{v_{i}v_{j}}=\left\{ \begin{array}{rcl} d_{v_{i}} & & \text{if i == j}\\ -w_{ij} & & \text{if $v_i$ and $v_j$ are adjacent}\\ 0 && \text{otherwise} \end{array} \right. \end{equation}$

其中 $d_{v_{i}}$ 就是公式( $1$ )中的节点 $v_{i}$ 的度, $w_{ij}$ 表示节点 $i, j$ 的权重.

我们可以用一个直观的图像来解释Laplacian Martix的概念,如下图:

Laplacian Martix

一个Laplacian Matrix可以看成是一个Degree Matrix和一个Adjacency Matrix相减得到.
$\begin{equation} \tag{4} L = D - A \end{equation}$
解释一下,从左边第一个图我们可以看出该图一共有6个节点,因此三个矩阵都用一个 $6\times 6$ 的矩阵来表示.

图像的度矩阵(Degree Matrix)[6]揭示了图中节点的性质,如图左2所示.例如,如果我们将左1图中两个节点中的权重设置为1,那么因为节点5中有三条边从这个节点中止(也就是说有三条边和节点5相连),因此在Degree Matrix为(5, 5)的地方就设置为3,其他节点同理.此时我们结合公式(1)以及图左2就可以理解什么是Degree Matrix了.
图像的邻接矩阵(Adjacency matrix)[7]解释了两个节点之间的关系.如图右2所示.例如,当节点2和节点1之间有一条连接线时,那么我们就将Adjacency matrix的(1, 2)和(2,1)处设置为1,其他连接线同理类推.不难看出一条性质,就是Adjacency matrix总是沿着对角线对称的.
结合公式( $3$ )( $4$ )以及下图,我们不难理解图的Laplacian Matrix的概念.

随机游走算法的思想

到这里我们提前总结一下随机游走算法的主要思想,读者可以读完后面的内容再回来重新回顾这里:
随机游走算法将图像分割问题转化成一个随机游走的任务(task)问题,通过将任务建模为一个离散的Dirichlet问题[4]并求解,从而得到分割结果.

一个例子

接下来我将举一个例子来形象的解释一下随机游走算法是怎么工作的[8,9]:

随机游走例子

假设我们有如下任务:一个随即游走者(random walker)的任务是沿着图示的直线运动,每次只能运动相邻的一个整数点.当他在点x(x=1,2,3,4)时,有两种选择,以0.5的概率向左走,或者以0.5的概率向右走.当他走到5点时,认为完成任务,也即到家;当走到0时,认为任务失败,无论走到0还是5,都停止走动.

问题是: 求这个人在任意一点处到达点5的概率.

分析:

设 $p(x)$ 是Random Walker在到达0之前能够到达5的概率,那么 $p(x)$ 具有如下性质:

$\begin{equation} \tag{5} p(0) = 0 \end{equation}$

$\begin{equation} \tag{6} p(5) = 1 \end{equation}$

$\begin{equation} \tag{7} p(x) = \frac{1}{2}p(x-1) + \frac{1}{2}p(x+1), x=[1,2,3,4] \end{equation}$
公式(5)和(6)表示:如果从0出发,由于直接停止运动,且不可能到达5点,因此概率为0;如果从5出发,直接就达到5点,且停止运动,因此概率为1.

公式(7)表示Random Walker从任意一个其他点出发,到达5点的概率.这个公式直接看可能有点不好理解,我们可以这样解释它:假设E是事件小人从点x[x=1,2,3,4]到达节点5,F是事件小人从x点先向左走,G是事件小人从x点先向右走,显然F和G是不能同时发生的,且我们从题目中已经知道向左走和向右走的概率分别是0.5,因此有下面的公式:
$\begin{equation} \tag{8} p(E) = p(F)P(E \text{ given } F) + p(G)p(E \text{ given } G) \end{equation}$
对比公式(8),我们不难理解公式(7)的意义.

结合公式(5-7),我们可以得到下面一组方程:

$\begin{equation} \tag{9} p(0) = 0 \end{equation}$

$\begin{equation} \tag{10} p(1) = \frac{1}{2} p(0) + \frac{1}{2}p(2) \end{equation}$

$\begin{equation} \tag{11} p(2) = \frac{1}{2} p(1) + \frac{1}{2}p(3) \end{equation}$

$\begin{equation} \tag{12} p(3) = \frac{1}{2} p(2) + \frac{1}{2}p(4) \end{equation}$

$\begin{equation} \tag{13} p(4) = \frac{1}{2} p(3) + \frac{1}{2}p(5) \end{equation}$

$\begin{equation} \tag{14} p(5) = 1 \end{equation}$

整理之后如下:
$\begin{bmatrix} 1 \\ 1 & -2 & 1 \\ & 1 & -2 & 1 \\ & & 1 & -2 & 1 \\ & & & 1 & -2 & 1 \\ & & & & & 1 \end{bmatrix} \begin{bmatrix} p(0) \\ p(1) \\ p(2) \\ p(3) \\ p(4) \\ p(5) \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0\\ 0\\ 1 \end{bmatrix}$

可见,上述的一个求任意一点到达节点5的概率问题,被我们转化为一个求解一组线性方程组的问题,因为系数矩阵为满秩矩阵,因此方程组必有一组解.

简单推导

直观理解

注意:随机游走算法需要事先人为的划定一些点作为标记点,比如,如果我们要在背景中将前景的某个物体分割出来,就必须在背景中选取一个或者一组点,并且在前景也选取一个或一组点作为初始条件.类比上面的例子,就好像我们让 $p(0)=0,p(5)=1$ 一样.否者线性方程组无法求解.

对于没有标记的点,我们需要分别计算这个点随机在整个图中随机游走的过程中首次到达前景和背景的概率,然后取概率大一类的作为该点所属的类别.如下图所示:

随机游走算法摘自文献[2]

左上为原始图像, $L_1, L_2, L_3$ 分别代表人工标记的三个标记点,问号的部分就是没有标记的点. 我们的任务就是根据标记的点,将图像中没有标记的点分割成三部分,其中 $L_1, L_2, L_3$ 分别代表
三个部分中的一个代表的点. 和刚才的例子类似,我们需要计算出三张图,即左下,右下,右上这三张图,每张图代表没有标记的点首次随机游走到不同标记点的概率,然后取最大的概率对应的label作为该点所属的类别,从而达到分割的目的.

公式推导

算法主要优化如下问题:

$\begin{equation} \tag{15} Q(x) = \frac{1}{2} x^T L x \end{equation}$
其中x表示待分割图像对应的图向量,L是其对应的拉普拉斯矩阵.

为了求解公式(15),我们把图上的节点分为两部分,一部分是已经标记的记为 $X_M$ ,另一部分为没有标记的记为 $X_U$ ,并且重新组合拉普拉斯矩阵为如下格式:

$L = \begin{bmatrix} L_M & B \\ B^T & L^U \end{bmatrix}$
则
$\begin{align} D(X_U) &= \frac{1}{2} \begin{bmatrix} \tag{16} X_M^T & X_U^T \end{bmatrix} \begin{bmatrix} L_M & B \\ B^T & L_U \end{bmatrix} \begin{bmatrix} X_M\\ X_U \end{bmatrix} \\ \tag{17} & = \frac{1}{2} (X_M^T L_M X_M + 2 X_U^T B^T X_M + X_U^T L_U X_U) \end{align}$

D对 $X_U$ 求导并令导数为0,我们可以得到下面的等式:
$\begin{equation} \tag{18} L_U X_U = -B^T X_M \end{equation}$
我们把标记的节点 $v_i$ 和其labels用函数的方式对应起来,即 $Q(v_i) = s$ ,其中s的取值最大为K,K即图像中要分割的区域数.

令
$\begin{equation} \tag{19} m_i^s=\left\{ \begin{array}{rcl} 1 & & Q(v_i)=s\\ 0 & & Q(v_i)\ne s\\ \end{array} \right. \end{equation}$
则有:
$\begin{equation} \tag{20} L_U X^s = -B^T m^s \end{equation}$
将s个方程组合到一起,有:
$\begin{equation} \tag{21} L_U X = -B^T M \end{equation}$

剩下的任务就是使用优化算法如共轭梯度下降来求解线性方程组(也即公式(21))了.

注意

上述推导过程只是粗略的把过程写了一下,至于为什么能够把首达问题转化为Dirichlet问题?为什么可以通过优化公式(15)就可以得到分割结果?Laplacian矩阵是如何构建的?以及一些推导的细节问题这里不过多介绍,详情请参考文献[1,2].另外再插一句, 在实现过程中,其核心部分在于构建Laplacian矩阵 $L$ 和矩阵 $B$ .详情参考源码.

实验结果

随机游走算法分割结果

参考文献

[1] L. Grady and G. Funka-Lea, “Multi-label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials,” in Computer Vision and Mathematical Methods in Medical and Biomedical Image Analysis, vol. 3117, M. Sonka, I. A. Kakadiaris, and J. Kybic, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 230–245.

[2] L. Grady, “Random Walks for Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 11, pp. 1768–1783, Nov. 2006.

[3] https://en.wikipedia.org/wiki/Dirichlet_problem

[4] [1]L. Grady and E. L. Schwartz, “Anisotropic Interpolation on Graphs: The Combinatorial Dirichlet Problem,” p. 19.

[5] https://en.wikipedia.org/wiki/Laplacian_matrix

[6] https://en.wikipedia.org/wiki/Degree_matrix

[7] https://en.wikipedia.org/wiki/Adjacency_matrix

[8] Random Walks分割

[9] P. G. Doyle and J. L. Snell, “Random walks and electric networks,” p. 118.

Random Walk Algorithm
简介 Random Walk 算法是比较早的一种基于图的方法，其原始论文[1]最早发在一个会议上, 后来经过修整发...
random walk
随机游走（random walk），其实感觉并不随机，因为每次计算的结果应该是相同，至少是相似的。表A dog|...
DeepWalk
Random Walk and Word2Vec
Final Project:Random Systems
Back Ground A random walk is a mathematical object which ...
[R] random walk
随机游走（random walk）也称随机漫步，随机行走等是指基于过去的表现，无法预测将来的发展步骤和方向。核心概...
random walk in python
当我以龟速在python入门的世界中挣扎的时候，遇到了一个熟悉的事物——random walk。所以这篇文章就用来...
Technical support web site (URL)
This app uses a random algorithm to generate numerical va...
Final Project
Since we have learned some Random Walk theory in Statisti...
基于随机森林的enhancer预测算法
RFECS: A Random-Forest Based Algorithm for Enhancer Ident...
算法与数据结构第一弹
Algorithm Chap01 prerequisite generate random array The b...

Random Walk Algorithm

简介

基于图的分割算法基本概念

图的基本概念

权重

Laplacian Martix (拉普拉斯矩阵)

随机游走算法的思想

一个例子

简单推导

直观理解

公式推导

注意

实验结果

参考文献

相关文章

Random Walk Algorithm

random walk

DeepWalk

Final Project:Random Systems

[R] random walk

random walk in python

Technical support web site (URL)

Final Project

基于随机森林的enhancer预测算法

算法与数据结构第一弹

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员