蓝色的点表示观测到的变量,就是像素值。粉色的点表示隐藏变量,就是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的情况。常用的函数有如下几种
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发送如下信息
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] 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_tGMVo_sNbC10N6zQlX0GAERu8oGTVXRE9tYMglgmwChORDXQW7A-V2CVy4Bse100ycPwWDJDe4eLlaFajdSveocaaTZzcoAo7o8iNCuLchIx-byf9KxNIav9cKzSgkWUBJ25ZMMGJIved1zvXlg04hVyFLAPwoJw5EBO7Xw-ot-zyTxqH-7UMYP0c-wNvCWAyBA441uWVglyPNMKcQ6ZpNB_uiM1lE_b8v4hatpDeKoYyHa9mO_czEXEp8EWpvnufjm06LSQDuif5f_UR-vhdyEL6j3pWo_NT7qHRaFVNT4eV3ketE-FpmihaVk4QsOhCtie6dan_IKzfaBDLEHD0V6xlVeAuTQaLuMBPSxsVUmdNu9EbbdEmwcplmkx6GWbsSKC4ZYmFGmi1rj1TsabQD3rY_ad2oRBsVbE-LLisTRqw3jjwwtZy0DTKWn2582a1z7s2OaS3xtI2Ohw30AYD1Tilw51RSnyzf-kxMY4QD1SQ5lWFk0lkBoilg0Vlj6F8SPTtTTmG69ji74AT4HnR2ZB_UMnzySufDablvBfPWFCz_TN5SC4oDASq0nfGwSVuH2n2P7rY0Q4vXd7arkHd7UcQ8ytn0aos7cazgy9E5l99xeR0PVjFWnFRUGCRut9UgYuug3V8ZnwpedS7vcuGOwQ0xU0FW-QZ6alT3_fMPIFzQnp9KIooOec_hG-_Z6uG-QLWVvwHfeWjZ_P6vZPNaSwIhKh4h6P5-D_D-gL6opT9iU2S0tWkg1tfix967Az2ZmZ7cF9_ePHUarSSR=s0-d)
等式左边表示从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] 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_umfiM2ZdD_AO8wD7Tu5MrwUSeU_Pzm5Viw-BMo8v_CUS9Ds2NIOw4pxKxcEzYukeeYD3V-jWCdivTYzfQ2BQgt_n3SaDEe9S8qFl3JcWKp43ZOnkxHzyX2qPro14alUu0CNULT0NpWnWcyenuFSP2akxOzaAFJ29JEuqK20SyzHeH2HPieL44zX0wLOZhIMkMcaWmxN-oNXPVO4bTMifKRBKMlR7RoZn2UY8dYWSABEY76tykFnfaKI6N5T7z8eSQ9aIn7sKgEA5mD6eFu8bbReiDutPCWoaU4N2Gtoi7Hm_j272nyuiDMTASsf0_5UC-F-Y_DuBGEy5HTViD3kAmLHKz_6qUSwv9w8iFP5rWDq8EYUo6ULJl8BQnJdo8_maK7QhILjo7RqraVa3ZAsUV2liZ0cVZe1A3nHDeJZtrUf_QBPrMX3V207dnn_0XQb7P7p0jJ0njyt_T8K1lWTBaQSso=s0-d)
所以对于每个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] 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_siBHY3YBOa5tsEfPFCMaV2n8p9iiU2rta84ASsQqR6pd_TtX3WbnrRh2xWHDAXvUtlgyCfSj8BH1Szmtu82OcA23BE_ZP6m_cmWwEQxJA3ktfzt5v4OuA5yoTah1nPHCSbrlozK4NaXE9lJGrBMW-j1_AcgmWOnKec9Uhxh1X12906pvNlDDwXBabpqtMHydmirSzy8Wv1xWd98IwxsJz0WPASnowHlxHrReCZU3KviKbM1vNU6JW7-MoTv5nX1Erp2BHxScNQoHiPg2HBNiJjuX4bq4-yuOG-ZbcNNScUZ9vqImx2lEWvHEPyro1XCCYsCApRQAF2rBWmBzjAgk_ipk2oid0wpVdJi0Jzill37Th1lWjgAHa2uaeMUB3low9dsPnfVoq-4Ms-GXK8CflGVu8Y1U5AhqSWheBjqbbSMRH94Eplvxi8xQBuZkNrItAJj5Bo4F8uVsJDd5tgyn3Wvibq8Stt8KMDx9KMOHMglQKWvrcFmgEnTiUpyzkb1fpzoIuMl1zehOqQW0rZ-AdU7Oh65mGJLO_Nx6AZvCMlij52XorIpWMKqV4KIpb1Nt6Nl6vSN5vLuMPDgkdVLTIkMQjPEVM8NclAX2cLOikX_AQzankKmOsvJEJWfZcHWv-8t9YhcT0AU6p4728i1-Txe42LRJGJ7DqCVSZ_XRmKPOSllepZTcekfFTyDAhNS6XfY4ciLTBIV5_GaQGDVu5z6Yt28y9zjig1ne3Afiw9BFF-xXbL9eTgcuraDfK1e7iXlD8nwTohWjeo=s0-d)
现在不再求和,而是计算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] 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_sXs-iYi0MUdi4_Vignf7zYIZran5NLEpH7u8mTNZdar2Y2IiksLOxy36t_tFJa3znggdsrFRbQyc92lbmMCmZv6we-kcZEsru5qX-EeBC0ms20d68GXKYtA2m1CihHZpl9F9lGq2KnMSsRXg2zh0-CftJv-qt4mrYah2kkr6mqUyU6JAbDqIQZljEHqYQNx7w4rcy6L7UJi6EXYWnMZEguChRvsfv8mn9gSr0VxsGmCadeeVjs3Lp_GvPW5-hmnmB9MVY_mxsqldvsnnRebPm2NUMtitddwnPKkoFA0At9uJQFDMjTBcgJncMBVVoQ6WbtcIjVkDspj-aZxclEd5oGuho4Mz39083piwrNeIm2PFYBE9vNOxxoA7tBYhW7S3vgNVFMhdPwCaiczbyntXpA03Hshu6dhlXJRzcm1wQf5jMsQ3dc4u6rEsda9jJhVTapSaJaXqGYmZxzlJp3Gex80lPqj_AuVpNHXKp08LEhEVXGz8sL2CiyHNsNuFbSXMiY9FIFb-2NcusfT2eBPtPtZuDAuTsHWBTJdX9u64qXMuvON7mCJinefcw2lm6nX5cyYDWbqofqVLEdWOQU6NrhTZDMS8rsqvvzF7AA=s0-d)
这是个求解最小值的问题。在初始化的时候所有的数值都是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之间的数.
No comments:
Post a Comment