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

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

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

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

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

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

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

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

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

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

w i j = e x p ( − β ( g i − g j ) 2 ) (2) \tag{2} w_{ij} = exp(- \beta (g_i -g_j)^2) wij​=exp(−β(gi​−gj​)2)(2)

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

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

拉普拉斯矩阵[4]可以反映出一个图的很多有用信息,其定义方式如下. L v i v j = { d v i if i == j − w i j if  v i  and  v j  are adjacent 0 otherwise (3) \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. Lvi​vj​​=⎩⎨⎧​dvi​​−wij​0​​if i == jif vi​ and vj​ are adjacentotherwise​(3)

其中 d v i d_{v_{i}} dvi​​就是公式( 1 1 1)中的节点 v i v_{i} vi​ 的度, w i j w_{ij} wij​ 表示节点 i , j i, j i,j 的权重.

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

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

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

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

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

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

分析:

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

p ( 0 ) = 0 (5) \tag{5} p(0) = 0 p(0)=0(5)

p ( 5 ) = 1 (6) \tag{6} p(5) = 1 p(5)=1(6)

p ( x ) = 1 2 p ( x − 1 ) + 1 2 p ( x + 1 ) , x = [ 1 , 2 , 3 , 4 ] (7) \tag{7} p(x) = \frac{1}{2}p(x-1) + \frac{1}{2}p(x+1), x=[1,2,3,4] p(x)=21​p(x−1)+21​p(x+1),x=[1,2,3,4](7) 公式(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,因此有下面的公式: p ( E ) = p ( F ) P ( E  given  F ) + p ( G ) p ( E  given  G ) (8) p(E) = p(F)P(E \text{ given } F) + p(G)p(E \text{ given } G) \tag 8 p(E)=p(F)P(E given F)+p(G)p(E given G)(8) 对比公式(8),我们不难理解公式(7)的意义.

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

p ( 0 ) = 0 (9) \tag{9} p(0) = 0 p(0)=0(9)

p ( 1 ) = 1 2 p ( 0 ) + 1 2 p ( 2 ) (10) \tag{10} p(1) = \frac{1}{2} p(0) + \frac{1}{2}p(2) p(1)=21​p(0)+21​p(2)(10)

p ( 2 ) = 1 2 p ( 1 ) + 1 2 p ( 3 ) (11) \tag{11} p(2) = \frac{1}{2} p(1) + \frac{1}{2}p(3) p(2)=21​p(1)+21​p(3)(11)

p ( 3 ) = 1 2 p ( 2 ) + 1 2 p ( 4 ) (12) \tag{12} p(3) = \frac{1}{2} p(2) + \frac{1}{2}p(4) p(3)=21​p(2)+21​p(4)(12)

p ( 4 ) = 1 2 p ( 3 ) + 1 2 p ( 5 ) (13) \tag{13} p(4) = \frac{1}{2} p(3) + \frac{1}{2}p(5) p(4)=21​p(3)+21​p(5)(13)

p ( 5 ) = 1 (14) \tag{14} p(5) = 1 p(5)=1(14)

整理之后如下:

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

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

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

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

算法主要优化如下问题:

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

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

L = [ L M B B T L U ] L = \begin{bmatrix} L_M & B \\ B^T & L^U \end{bmatrix} L=[LM​BT​BLU​] 则 D对 X U X_U XU​求导并令导数为0,我们可以得到下面的等式: L U X U = − B T X M (18) \tag{18} L_U X_U = -B^T X_M LU​XU​=−BTXM​(18) 我们把标记的节点 v i v_i vi​和其labels用函数的方式对应起来,即 Q ( v i ) = s Q(v_i) = s Q(vi​)=s,其中s的取值最大为K,K即图像中要分割的区域数.

令 m i s = { 1 Q ( v i ) = s 0 Q ( v i ) ≠ s (19) \tag{19} m_i^s=\left\{ \begin{array}{rcl} 1 & & Q(v_i)=s\\ 0 & & Q(v_i)\ne s\\ \end{array} \right. mis​={10​​Q(vi​)=sQ(vi​)​=s​(19) 则有: L U X s = − B T m s (20) \tag{20} L_U X^s = -B^T m^s LU​Xs=−BTms(20) 将s个方程组合到一起,有: L U X = − B T M (21) \tag{21} L_U X = -B^T M LU​X=−BTM(21)

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

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