蓝色的点表示观测到的变量，就是像素值。粉色的点表示隐藏变量，就是disparity。通常隐藏变量叫做label。node之间的link表示dependency，比如中间粉色的点只跟周围四个点和上面的蓝色的点有关。这个某点只跟周围点有关的假设就是Markov假设。这个假设使我们能够高效的求解隐藏变量。
如果用MRF来表达stereo vision，它的energy function就是
Y表示观测变量，X表示隐藏变量。i是pixel的index，j是xi相邻的node。给定一个图像Y和一些label X，这个能量方程求得了每个link的cost的和。我们的目标是找到一个label X，比如disparity map，使得这个能量方程最小化。接下来我们分开来看data cost和smoothness cost。
Datacost主要指把label xi赋值给data yi造成的cost。对于正确的匹配，datacost很低。对错误的匹配datacost就很高。常用的衡量datacost的有差值绝对值的和，SSD等。
Smoothness cost确保相邻像素有相同的label。我们需要一个函数来惩罚相邻像素有不同label的情况。常用的函数有如下几种
Also known as the Potts model.
Truncated linear model.
Truncated quadratic model.Loopy Belief Propagation
因为图像中有很多像素，disparity value也有很多可能，所以很难找到MRF的精确解。LBP提供了一种方法来寻找近似解，类似的方法还有graph cut, ICM.不过LBP不保证convergence。
LBP是中用来传输信息的方法，当一个node收到了所有信息的时候，它就发给相邻node一个信息。下图展示了从x1传送到x2的过程。
x1首先需要从A,B,C,D接收到信息，然后才会给x2传输信息。x2不会返回给x1信息。准确来说信息的定义是
，表示从node i发送label l的信息给node j。换言之就是node i对node j属于label l的belief。这些信息只在隐藏变量之间传递。一个完整的信息包含所有可能的label。比如node i会给node j发送如下信息
，表示从node i发送label l的信息给node j。换言之就是node i对node j属于label l的belief。这些信息只在隐藏变量之间传递。一个完整的信息包含所有可能的label。比如node i会给node j发送如下信息
hey node j，我认为你是label 0，概率是s0
hey node j，我认为你是label 1，概率是s1
。。。
Node i记载了所有关于node j的可能性。概率的计算取决于MRF。
LBP的第一步是初始化信息。因为node要等到所有相邻node都发送信息，这就变成了一个鸡生蛋蛋生鸡的问题，因为所有node都会等待其他node发送信息，实际上谁也没有发送任何东西。为了解决这个问题，我们把所有信息都初始化成一个常数，通常是0或1.
LBP主体算法是iterative的。如同其他iterative的算法，我们可以在一定循环次数后结束，或者到energy的变化小于一个阈值。在每个iteration，信息在MRF中传递。信息传递的次序是随机的。一旦这个过程结束，我们就可以根据每个node的belief计算这个node的label。
接下来我们一个个来看信息更新，初始化，和belief的步骤，和三个不同算法sum product，max product, min sum。
用于信息更新的sum product
![msg_{i \rightarrow j}\left( l \right) = \sum\limits_{l' \in \mbox{all labels}} \left[ \begin{array}{c} exp\left(-DataCost\left(y_i,l'\right)\right) exp\left(-SmoothnessCost\left(l,l'\right)\right) \times \\ \prod\limits_{k=\left( \begin{array}{c} \mbox{neighbours of i} \\ \mbox{except j} \end{array} \right)} msg_{k\rightarrow i}\left(l'\right) \end{array} \right]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_thI706NgDPLGc_t8Ptx2CdwclfYi5GuZKDFblYGrZwpRRW1ePtSOc8-arxqwhFuh3mfxlypKu14yn17EL9Nx827ys_h1XkwZjKP8IrsVnNfokCLRJWKGQiIZdnOwSL1Qoo_YezMhgCCdBFzQY37dA2SfGoh7Y8PVnKDQ4jQUl-XULZARbddCrTixSDkfezTZP50iwMuSm5OPYZG8rZ55Z1kt1FXkUxXeEMytL2lHov-Cayskvqc9i4b1gGgK1iJfETUdVpzm-dCiD6iuo2zg5amjWangJjBQ_pqRhnzGyuZSsDDwfn6z10saJRnRsVguflY8fwbZSwzRSjN_B0rkCDSdXX-j1ls1Yn9LFlqB6m8c0p33nT7tbmAFOf_Pm4Rn5KbB75MREKWRaTkJ5PZF8d-0cbUVfwEIv_z2NsBbGNM-OKz03MywTXMWhVxaoOvSpUwJVMtoi46N04a3E8_K9TTY21jYXib5OHn3ehBm6zyjs-Jd4y2DJ1rz_O5mn-aQByU7YIIP_tyvHA0OuOrRPAmsb9ajDHxQ9NIPLIFJslq1jQaPVj9jn_zG9imjzaGhB2xfr-GG1Z6-yDDroopEVtMKC0xxzY-ueJ5T9tIwYpn11IQJIftLUTNmHgDcA7a1MAadCrOSctrj5g-BAucCF3v9gIi-4rV2pSzM8MuyNTmz8KmF-V9pylSe9cWQxbRzolynu_gxt_OgolKSlbKb_4OCSuEt6m7IDbZW2R36PRxMJVnzt2RzNAJvrXUZn-BjJQmlo3TEPRyBSBOEoN=s0-d "msg_{i \rightarrow j}\left( l \right) = \sum\limits_{l' \in \mbox{all labels}} \left[ \begin{array}{c} exp\left(-DataCost\left(y_i,l'\right)\right) exp\left(-SmoothnessCost\left(l,l'\right)\right) \times \\ \prod\limits_{k=\left( \begin{array}{c} \mbox{neighbours of i} \\ \mbox{except j} \end{array} \right)} msg_{k\rightarrow i}\left(l'\right) \end{array} \right]")
等式左边表示从node i发到node j，关于label l的信息。右边的y表示图像像素。这里我们遍历所有的label，在disparity map中共有15种。因为有加和，内积的计算，所以叫sum product。这个算法用于概率的计算，所以要用exp函数把data cost, smoothness cost，转换到在0到1之间的概率，这个概率越大越好。在中括号里面的是data cost, smoothness cost对于label l的所有信息的joint probability. 中括号外面的加和是对概率在变量l上的marginalization.
一个完整的信息是一个矢量
![msg_{i \rightarrow j}=\left[ \begin{array}{c} msg_{i \rightarrow j}\left(0\right)\\ msg_{i \rightarrow j}\left(1\right)\\ msg_{i \rightarrow j}\left(2\right)\\{..} \end{array} \right]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sWH9CWBpUBDoYXw4NX5az7R3uldUNMJbYGILaY9Rmw1psphdsnS3Jbsi1-KJF2IHo9xOesuQIUaHpMqfV4VvD0oX7W5Ac8P_HNM683O5gBlNq7nFtLmsV4foUwI5WmYH0ysBtLqZEqsSsfrwI1Ys_udXUlTptSuGFFLVBxEzo9EYeicmu_Ln8UDT3dTDIm3JGZNt3-_OdxlXPHaoiNBYrBGFBnOpO1Ci-h2UJtfvczL1iZ3REQ22UdKWW5DcTXcpBBbq3beIm0QYx8geTuYJlfFSE-kRCyv5gIBy_FQadbtYQyFD82s7NmcTpNaQoUphwWlBrqNQVjcd55hmpY3tR-8HbA0Hm4Ip17dHP6Oay3fb26TicgyCUz_W0oep5eqYOYs_T6fjpIdus42fG9wJ52i683nYWyn7zk7S3h-7jpM3SQJgPJ2hbFqlokdhOXhjXbEz2tZShoKX5ikUPxJnuVAqQ=s0-d "msg_{i \rightarrow j}=\left[ \begin{array}{c} msg_{i \rightarrow j}\left(0\right)\\ msg_{i \rightarrow j}\left(1\right)\\ msg_{i \rightarrow j}\left(2\right)\\{..} \end{array} \right]")
所以对于每个label都要遍历所有可能，复杂度就是O（L^2）.
连续对概率做乘积的时候，很快就会接近0.为了避免这个情况，我们要把信息向量normalize
进行初始化的时候，所有信息的概率都设为1.每个node的belief是所有信息的乘积。
这是node i对于label l的belief。为了找到最合适的label，需要遍历所有label然后找到最高的belief。
用于信息更新的max product
sum product可以找到每个node的最佳label。但是总体来说并不一定是最优解。举例来说，假设有两个变量x，y
表格外边的是变量的marginal。如果用单独的marginal计算，我们会选择x=1, y = 0,得到P(x=1,y=0) = 0.4。但是最佳的解是p(x=0,y=0) = 0.5。我们最关心的是Joint probability。此类问题经常会在maximum a posteriori (MAP)求解中出现，因为这时我们想找到全局的最优解。max product在sum product的基础上做了一点点改变
![msg_{i \rightarrow j}\left( l \right) = \max\limits_{l' \in \mbox{all labels}} \left[ \begin{array}{c} exp\left(-DataCost\left(y_i,l'\right)\right) exp\left(-SmoothnessCost\left(l,l'\right)\right) \times \\ \prod\limits_{k=\left(\begin{array}{c} \mbox{neighours of i} \\ \mbox{except j} \end{array} \right)} msg_{k\rightarrow i}\left(l'\right) \end{array} \right]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vIPBSJDTi6gb69BqfAXmUBlRRFmAJosttfzWf0DGo4jpd3kuRBZak-AbWa8_VgrGY5ito5wcEAjPgJ6tUzXegvumLFfbll8U7XwvwmDyHbQIqJDFhaVeskhYCtzfMasd0yhW_t_pQrL2SCr-1Diau3z0KaxdGf0WY7TgQwLTZbhz3Jz3X4u8Z6xznSYxsjz-tn5GFo8-xXTnq2RxCfQkop9-p5ZVTVEinXwfUdzdQjgkk8_EN0aH709Zzyfc0xz2dVKS6_EeoA9YRwlZQKOTAZ_Zgt0My4E6x3AAftKF5Iyg9VBIe4UHBlEoqrxIPo6hxre6Fg2tWzhi2Krq0z3TzDPgnlKZAcfG3r_4wQMQVCfJ0lewvleANCz0G2TAIFRym0iLmFv6z6o5nnG8ncRWno8ZJDIRQucH-G_AIIkbu5VTdlJFaeFw9MwVf7rfnf53S3r-Cuqash-SQ7jFt3yNT5CH2JV_UNFgMlSNzNKgTysLPk0Q1iAnGLHZRi2aKthbOvZoPnq9W91LXEoZYky-0RG4yjuHEQRajubE-HUaSdUR2CxVbrgrG-7BMk8Ws2oZ4i9RlJkB1LDbE1NJNc_Tcl84xLceRI0CMCuG216D2YMz5Ju92xUHsxafLZslmesjiemW1xiPo6KV4NecQXfBGn-HeMYIYvDRqVgBs4Sa37OCIsu-hlH5ARhMaKBOLxpu7izv5vwqOtZSPgvLXPRwYMwTH_DRuXnR4AaNgTju0R23SwLRxZOg_NsulbDc5sjypyZltay5fMvpwA=s0-d "msg_{i \rightarrow j}\left( l \right) = \max\limits_{l' \in \mbox{all labels}} \left[ \begin{array}{c} exp\left(-DataCost\left(y_i,l'\right)\right) exp\left(-SmoothnessCost\left(l,l'\right)\right) \times \\ \prod\limits_{k=\left(\begin{array}{c} \mbox{neighours of i} \\ \mbox{except j} \end{array} \right)} msg_{k\rightarrow i}\left(l'\right) \end{array} \right]")
现在不再求和，而是计算marginal probability的最大值。
用来更新信息的min sum
和max sum相似，min sum也是计算每个node的max marginal，不过是在log space中。
![msg_{i \rightarrow j}\left( l \right) = \min\limits_{l' \in \mbox{all labels}} \left[ \begin{array}{c} DataCost\left(y_i,l'\right) + SmoothnessCost\left(l,l'\right) + \\ \sum\limits_{k=\mbox{neighours of i except j}} msg_{k\rightarrow i}\left(l'\right) \end{array} \right]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sOPVQt-Nj2q9zhdcdQYlhqe58d8pAsMyhBNr5egjERSOj9t6eypFuAenk0Wl677ad24RB9v8zNBUlrwJKj3rrgIWA0MXwt1kH0zY8hmIhOQvbR-FFj0SNZEaJPsF2InVYfwMELCw0AySdw7uK4SamdrhJBMPZoWNMBK7qdzD3hGd2XZbunXzjoeUhWcmaKhfpV1C6pkkAn9xIbxskedgRojQPVaodi8CLLs7_OSQlrVYeypIM0BS5a8HluSgkwtoBkP1QKhwu2cou8fTdRblYa33rAMOfv4QwN7CHYAQB_8jctBbDz10TWwo_RV7l98pxfASt6hVMcVh7E9sONXTWQlCIslNl2B1envO2ixuZeDy5gZ2c_Wkm-mPn9IElu4LlLT_s8v-E2WT9FSsXz91568hyqtKVYO42tHtKiOHIKdG9IdX7pImAPq-ReS4y0vHDAxlVkGCHEL2aXPwa3P_bSKNYBZQP4wfMPEw8XL0NdNOYQRxSuC6V0A00Sm0Hhv0RhRy7gejobrN936MwwZukITMbDWCiUNKOvKarkD0waZYLyHibZNRqoU3Ftgb9dC4BTTo-TqRHrnk-hjcUECXosYCXm5yuGEknSXI_L=s0-d "msg_{i \rightarrow j}\left( l \right) = \min\limits_{l' \in \mbox{all labels}} \left[ \begin{array}{c} DataCost\left(y_i,l'\right) + SmoothnessCost\left(l,l'\right) + \\ \sum\limits_{k=\mbox{neighours of i except j}} msg_{k\rightarrow i}\left(l'\right) \end{array} \right]")
这是个求解最小值的问题。在初始化的时候所有的数值都是0. 这时的belief是
用于信息更新的sum product
等式左边表示从node i发到node j，关于label l的信息。右边的y表示图像像素。这里我们遍历所有的label，在disparity map中共有15种。因为有加和，内积的计算，所以叫sum product。这个算法用于概率的计算，所以要用exp函数把data cost, smoothness cost，转换到在0到1之间的概率，这个概率越大越好。在中括号里面的是data cost, smoothness cost对于label l的所有信息的joint probability. 中括号外面的加和是对概率在变量l上的marginalization.
一个完整的信息是一个矢量
所以对于每个label都要遍历所有可能，复杂度就是O（L^2）.
连续对概率做乘积的时候，很快就会接近0.为了避免这个情况，我们要把信息向量normalize
进行初始化的时候，所有信息的概率都设为1.每个node的belief是所有信息的乘积。
这是node i对于label l的belief。为了找到最合适的label，需要遍历所有label然后找到最高的belief。
用于信息更新的max product
sum product可以找到每个node的最佳label。但是总体来说并不一定是最优解。举例来说，假设有两个变量x，y
| P(x,y) | x=0 | x=1 | |
| y=0 | 0.5 | 0.4 | P(y=0) = 0.9 |
| y=1 | 0.1 | 0.3 | P(y=1) = 0.4 |
| P(x=0) = 0.6 | P(x=1) = 0.7 |
现在不再求和，而是计算marginal probability的最大值。
用来更新信息的min sum
和max sum相似，min sum也是计算每个node的max marginal，不过是在log space中。
这是个求解最小值的问题。在初始化的时候所有的数值都是0. 这时的belief是
不过因为我们其实在找最小值，称它为cost更合适。
在这些方法中，min sum是最方便实现的，它没有exp函数，只有加和。如果用sum product的话，就要在exp里面加上scaling来避免underflow。eg. exp(-DataCost(…)*scaling) * exp(-SmoothnessCost(..)*scaling), scaling是 0 到1之间的数.
