沈乐君马尔科夫讲义11MRF

马尔科夫随机场与实时多目标 跟踪算法 沈乐君 sljcool@sina.com http://www.shenlejun.cn MRF的应用实例 • 利用马尔科夫随机场进行噪声图像的分割 • 马尔科夫随机场结合粒子滤波器进行实时多 目标跟踪 目录 • 马尔科夫随机场（MRF）的介绍 • 基于MRF的噪声图像分割 • 粒子滤波器的介绍 • 综合MRF与粒子滤波器进行多目标跟踪 • 自助重要性采样（BISP）的实时多目标跟踪 MRF简介 • 马尔可夫随机场（Markov Random Field）是 计算机视觉、图像处理等研究的重要工具。 • 它在图像处理中的应用广泛。它不仅可处理 底层视觉（图像分割、边缘 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 ），还可用 于中高层视觉处理（多目标跟踪、场景分析 和理解）。 MRF的应用 • 图像除噪和图像增强 MRF的应用 • 图像恢复 Roth and Black, CVPR 2005 MRF的应用 • 去除杂波（Clutter Removal） Zhu and Mumford PAMI, 1997. MRF的应用 • 超解析度（Super-resolution） Bill Freeman ICCV99 MRF的应用 立体视觉 MRF的应用 运动矢量 MRF的应用 • 目标检测与识别。对目标的部分与整体关系 进行建模。 随机场 • 随机场（Random Field）是一种被广泛应用 的随机数学模型。之所以它的应用广泛，是 因为它的定义非常简洁和通用。 • 下面介绍其核心定义。 随机场 • Collection of n sites S • Hidden random variable xi at each site i • Label set L – Each site takes on label l∈L • Neighborhood system N – Ni neighbors of site I – Explicit dependencies between neighbors 随机场 • Collection of n sites S • 位置S，刻画随机变量 xi的空间关系。 – 网格 eg.4个像素 – 遮挡 eg.5个目标 随机场 • 其它各种类型的S 随机场 • Hidden random variable xi at each site i • 随机变量xi是我们在图像处理过程中感兴趣的量。 xi是隐变量，也就是随机场中的未知量。xi常被噪声污染，所以是随机变量。xi共有多个，所以叫做 随机场。 – 像素的真实类别标签，如：1,2,3,4 – 目标的真实位置，如：横坐标=10.2, 纵坐标=4.5 • 为了求解X，常引入可观测变量y，它是已知量， 代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf CCD获取的真实图像信息。 • Label set L • 标签L是变量x的取值空间，它是离散或连续的。 随机场 • Neighborhood system N • 隐变量xi常常与其 它变量相关。用N 刻画变量与其它变 量的相关性。 • 依赖关系对应于无 向图中的边。 马尔科夫随机场 • Random field with Markov property • P(xi| xS\i) = P(xi| xNi) – Where S\i denotes set S excluding element i • Conditional probabilities depend only on neighborhood – Probability of xi taking on some value same given all other nodes as given just neighbors • 赋予随机场马尔科夫性，最重要的目的就是降低模 型的计算代价。cf.蝴蝶效应、颜色革命与利比亚 马尔科夫随机场 • 在点对马尔科夫随机场（Pairwise Markov Random Fields）中引入观测变量yi，对隐变量xi进行贝叶斯 推理。下面先介绍贝叶斯公式： • P(X|Y) = P(Y|X) P(X) / P(Y) Y: 图像 X: 分类标签 (下页解释X,Y) 马尔科夫随机场 • 其中，X是全部隐变量组成的向量，Y是全部观测 变量组成的向量。Y是已知图像，X是未知的图像 分割结果。如果图像大小是128x128，那么，X是 16384维向量。假设每个像素有4种状态，那么X共 有4128*128≈109864种可能。 • 如何在庞大的可能空间中寻找最佳的图像分割结 果？显然，用贪婪法求解是不现实的。这是一个典 型的组合优化问题。于是，图像分割问题转换为最 优化问题。大量的图像处理问题，最终都能被转化 成为最优化问题。(下页是最优化示意图) 马尔科夫随机场 X(0)→……→X* 函数f(X)是什么？ 起点X(0)如何得到？ 用什么最优化方法？ X(0) … … X* 函数形态 • 首先，考虑f(X)，也就是联合概率P(X,Y) image patches Ψ(xi, xj) image scene scene patches Φ(xi, yi) 函数形态 • 点对马尔科夫随机场的联合概率公式 scene image Scene-scene compatibility function neighboring scene nodes local observations Image-scene compatibility function ∏∏ ΦΨ= i i ji ji xxxZ yxP ,(),(1),( , iy ) 起始解 • 其次，考虑优化的起点，也就是X的初始解X(0)。 假设像素之间相互独立，使得像素之间相互独立 地进行分类或标记。也就是暂时忽略联合概率公 式中的边势函数。 ∏∏= i ii ji ji yxxxZ YXP ),(),(1),( , φϕ 起始解 • 相互独立假设，使得我们仅考虑每个像素的分类 或标记。可是，解是 X(0): 初始解 )()|()|( iiiii xPxyPyxP ∝ )|(),( iiii yxPyx =φ ∏= i ii yxZ YXP ),(1),( )0( φ Y: 图像 μ1 μ2 μ3 μ4 （运行程序观察参数） 直方图 最优化方法 • 什么是概率推理？已知观测Y，以及MRF模型的参 数（如均值μ1=76.1），推理出令联合概率公式最 大的X的值。也叫做MAP推理（Maximum A Posteriori）。换句话说，在可能解空间中，搜索使 联合概率最高的解。 • 如果随机变量X拥有离散的样本空间，MAP就是一 个组合优化问题。如果随机变量是连续的样本空 间，MAP就是一个数值优化问题。 • 可是，MRF推理的困难在于：非线性；解析不可 解；仅利用梯度信息，容易陷入局部极值； 概率推理 • 基于MRF的概率推理分为精确推理和近似推 理两类。后者使用取样方法来近似求解。 – Gibbs sampling, simulated annealing – Iterated condtionalmodes (ICM) – Metroplis sampling – Variational methods – Belief propagation – Graph cuts 取样方法 • 取样方法：通过某种算法产生大量样本，取 后验概率最大的样本为解。 …… Y: 图像 X(0) X(1) X(n) 取样方法 • 在取样时，考虑像素之间的依赖关系。 ∏∏= i ii ji ji yxxxZ YXP ),(),(1),( , φϕ ⎪⎩ ⎪⎨⎧ ≠ = ji ji ji xxif xxif xx β αϕ ),( 例如α= 0.8 β=0.2 取样方法 • 吉布斯取样（Gibbs sampling）方法用于产生 样本。直观解释：根据邻域N3的变量的值来 产生样本。模拟退火（simulated annealing） 用于寻找全局最优值。 x1 x2 x3 x4 x5 ? ? 取样方法 • 教程 人力资源管理pdf成真迷上我教程下载西门子数控教程protel99se入门教程fi6130z安装使用教程 与源代码： • UGM: A Matlab toolbox for probabilistic undirected graphical models • 网址：http://www.cs.ubc.ca/~schmidtm/ 蒙特卡洛仿真 • 假设生成了N个样本。如前文，可用于求MAP： • 如果N趋向于无穷，可以求积分： • 用N个样本来表示概率密度分布： 蒙特卡洛仿真 • 已知Y，可以用N个样本描述P(X|Y)的分布。 • 在前文中X表示像素，现在表示目标的坐标。目标 跟踪的任务，就是求解已知图像Y，和已知上一时 刻的目标位置的条件下，目标X的值。 )|(~}{ 1111 −−=− tt N r r t yxPx 1111 )|()|()|()|( −−−−∫= ttttttttt dxyxPxxPxyPyxP η 当前状态 观测方程 动态方程 上一时刻状态 粒子滤波器 • 动态方程 Specifies how objects move between frames • 观测方程 Specifies the likelihood of an object being in a specific state (i.e. at a specific location) 1111 )|()|()|()|( −−−−∫= ttttttttt dxyxPxxPxyPyxP η 粒子滤波器 • 初始状态P(x0)：目标检测或手工选中 粒子滤波器 • 最简单的动态方程是高斯窗口 粒子滤波器 • 好一点的动态方程，根据上一时刻的速度预 测高斯窗口的中心位置。 粒子滤波器 • 观测方程基于HSV色彩直方图模型 粒子滤波器 • 观测方程的似然度计算的是两个直方图之间 的巴氏距离： 粒子滤波器 • 粒子滤波器的核心思想a set of weighted particles approximates the filtering distribution ∑ −≈ r r tttttt xxPxyPyxP )()|()|( 1 1111 )|()|()|()|( −−−−∫≈ ttttttttt dxyxPxxPxyPyxP 基于MRF的粒子滤波器 • 基于MRF的粒子滤波器还要考虑目标间的关系。 （n是目标个数，E目标间的遮挡关系） ∑∏∏ = − ∈ ≈ r n i r tiit Eji jtittttt xxPxxXYPYXP 1 )1( , )(),()|()|( ϕ ∑ −≈ r r tttttt xxPxyPyxP )()|()|( 1 基于MRF的粒子滤波器 • 边势函数Ψ表达了目标间的关系，是MRF设 计的关键。惩罚完全重叠的目标！ ) )( ),( 9exp(),( 2 ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛×−= i ji jiji xarea xxoverlap xxϕ [1]Z. Khan, T. Balch, and F. Dellaert. MCMC-based particle filtering for tracking a variable number of interacting targets. PAMI, 27(11):1805–1918, 2005. [2] T. Yu and Y. Wu. Collaborative tracking of multiple targets. In IEEE CVPR, 2004. [3] Lejun Shen. (appear soon! ) 基于MRF的粒子滤波器 • 如何利用粒子滤波器进行MRF推理呢？ – JPF（联合状态粒子滤波） – MCMC（马尔科夫链蒙特卡洛）法 – Mean-Field （均值场变分法） – DMOT（分布式法） – BISP（作者:沈乐君。它是一种基于MRF的实时 多目标跟踪算法，尚未发表） 展示MCMC方法 * Khan et al., “MCMC-Based Particle Filtering for Tracking a Variable Number of Interacting Targets”, PAMI, 2005. 展示MFMC方法 T. Yu and Y. Wu. Collaborative tracking of multiple targets. In IEEE CVPR, 2004. 展示BISP方法 Er：误差 Ct：运算时间 谢谢！ 马尔科夫随机场与实时多目标跟踪算法 MRF的应用实例 目录 MRF简介 MRF的应用 MRF的应用 MRF的应用 MRF的应用 MRF的应用 MRF的应用 MRF的应用 随机场 随机场 随机场 随机场 随机场 随机场 马尔科夫随机场 马尔科夫随机场 马尔科夫随机场 马尔科夫随机场 函数形态 函数形态 起始解 起始解 最优化方法 概率推理 取样方法 取样方法 取样方法 取样方法 蒙特卡洛仿真 蒙特卡洛仿真 粒子滤波器 粒子滤波器 粒子滤波器 粒子滤波器 粒子滤波器 粒子滤波器 粒子滤波器 基于MRF的粒子滤波器 基于MRF的粒子滤波器 基于MRF的粒子滤波器 展示MCMC方法 展示MFMC方法 展示BISP方法