CN104065932B - 一种基于修正加权二部图的无重叠视域目标匹配方法 - Google Patents

Abstract

本发明提出一种基于修正加权二部图的无重叠视域目标匹配方法，涉及计算机视觉领域。本发明将无重叠视域目标匹配问题表示成一个最大后验概率问题，从而将目标观测模型与监控网络时空约束信息结合起来，并通过求解加权二部图的最大权匹配解决最大后验概率问题。针对普通加权二部图构造中容易引入错误匹配的问题，本发明提出了一种基于自适应阈值的修正加权二部图构造方法，从而尽可能地避免在构造加权二部图的过程中引入错误的匹配。针对传统KM方法在处理大规模加权二部图匹配问题时计算量过大的弊端，提出了一种基于MH采样的方法近似求解加权二部图的最大权匹配，从而得到无重叠视域目标匹配关系。

Description

一种基于修正加权二部图的无重叠视域目标匹配方法

技术领域

本发明属于计算机视觉领域，具体涉及智能监控领域，特别涉及一种基于修正加权二部图的无重叠视域目标匹配方法。

背景技术

随着摄像机监控技术的发展，对大范围区域进行监控成为了保障人民生命财产安全的一项重要手段。然而，对于区域较大的监控场合来说，使用摄像机覆盖所有的监控区域很不现实。因此，通常采用重点区域覆盖的方法来搭建包含无重叠视域的多摄像机监控系统。对于无重叠视域监控网络，只有确定了目标在不同视域中的匹配关系，才能较好地理解目标在整个监控场景中的行为。但是，无重叠视域环境下的光照变化、场景变化等干扰因素会导致目标在不同视域下的观测值发生变化，从而降低目标正确匹配的概率。因此，需要综合考虑目标信息以及场景信息，从而尽可能地提高无重叠视域下的目标匹配率。

无重叠视域目标匹配问题本质上属于数据融合问题，目的是把观测模型的外表相似信息与监控网络的时空约束信息相融合，从而实现无重叠视域下的目标匹配。国内外研究者对这种数据融合问题进行了研究，取得了一定的成果。如文献“Huang T,RussellA.Object identification:A Bayesian analysis with application to trafficsurveillance[J].Artificial Intelligence.1998,103(1):1-17”建立了一个贝叶斯框架来匹配高速公路上相邻两个摄像机检测到的车辆。文献“Kettnaker V,Zabih R.Bayesianmulti-camera surveillance[C].IEEE Computer Society Conference on ComputerVision and Pattern Recognition.Fort Collins:IEEE,1999.2010-2016”也是用贝叶斯框架实现了室内型人的匹配和识别，将最大后验概率估计问题近似成一个线性规划问题。文献“Javed O,Shafique K.Tracking across multiple cameras with disjoint views[C].Proceedings of the IEEE International Conference on Computer Vision.Nice:IEEE,2003.952-957”不但更加细致深入地给出了外表模型和拓扑关系的估计方法，还使用二分图匹配的方法计算最大后验概率，计算过程符合多项式时间要求。

国内对相关数据融合问题的研究主要是在文献“Javed O,Shafique K.Trackingacross multiple cameras with disjoint views[C].Proceedings of the IEEEInternational Conference on Computer Vision.Nice:IEEE,2003.952-957”的基础上展开的。譬如，文献“刘少华,张茂军,陈旺.无重叠视域多摄像机的数据关联方法[J].计算机应用,2009,29(9):2378-2382”提出了一种基于权重二部图的关联策略，以目标为节点，结合时间约束和空间约束构造边，目标的相似度为边的权重，通过求取二部图的最大权匹配得到最优关联结果。文献“刘少华,赖世铭,张茂军.基于最小费用流模型的无重叠视域多摄像机目标关联方法[J].自动化学报,2010,36(10):1484-1489”提出了一种基于最小费用流的关联方法，修正了二部图关联中过度依赖效用函数的缺点。但是，费用流关联问题的时间复杂度大于二部图关联问题，因此不适用于处理大规模匹配问题。

因此，利用无监督学习方法自适应学习多摄像机监控网络的拓扑结构，对于多摄像机监控系统能否应用于实际至关重要。在无重叠视域目标匹配方法中，主要有以下三点需要注意：(1)如何对目标自身信息与外部环境信息进行融合，构建无重叠视域目标匹配方法框架；(2)如何利用成熟的方法解决所构建的无重叠视域目标匹配问题；(3)在利用图论方法解决无重叠视域目标匹配问题时，如何尽可能避免引入错误匹配关系，并提高匹配的速度。

发明内容

本发明的目的在于提出一种基于修正加权二部图的无重叠视域目标匹配方法。此方法对无重叠视域下光照变化、环境差异对目标匹配造成的影响具有很强的鲁棒性。

本发明的技术方案为：将无重叠视域目标匹配表示成最大后验概率问题，在构造最大后验概率问题时，综合考虑了目标观测模型与监控网络时空约束。构造加权二部图，通过求解二部图的最大权匹配从而解决最大后验概率问题。针对普通加权二部图构造中容易引入错误匹配的问题，提出一种基于自适应阈值的修正加权二部图构造方法，从而尽可能地避免在构造加权二部图的过程中引入错误的匹配。针对传统KM方法在处理大规模加权二部图匹配问题时计算量过大的弊端，提出一种基于MH采样的方法近似计算加权二部图的最大权匹配，从而得到无重叠视域目标匹配关系。

本发明的具体实现步骤依次为：

1)确定目标观测模型

2)确定监控网络时空约束

3)划分时空最小单元

4)构造最大后验概率问题

5)计算自适应阈值

6)构造修正加权二部图

7)MH方法近似求解加权二部图的最大权匹配

附图说明

图1是本发明基于修正加权二部图的无重叠视域目标匹配方法的系统流程图

图2(a)是本发明使用的主颜色特征的提取示意图

图2(b)是本发明使用的空间纹理特征的提取示意图

图3是本发明中监控网络拓扑示意图

图4是本发明中空间最小单元划分示意图

图5是本发明中时间最小单元划分示意图

图6是本发明中修正加权二部图示意图

具体实施方式

图1给出了基于修正加权二部图的无重叠视域目标匹配方法的系统流程图：使用最大后验概率框架描述无重叠视域目标匹配问题，在构造最大后验概率框架时，综合考虑了目标观测模型与监控网络时空约束。本发明提取了目标的主颜色特征与空间纹理特征，构造出对光照差异、环境变化有较强鲁棒性的目标观测模型。本发明在假设监控网络拓扑已知的前提下，从拓扑中得到监控网络的时空约束。根据监控网络的时空约束，将监控网络拓扑按独立性原则与最小化原则划分为多个最小单元，对于最小单元中的任意消失目标，其再次出现仍然位于最小单元中。对于任意最小单元内的目标匹配问题，利用贝叶斯推断准则将其表示为最大后验概率问题。本发明利用图论的方法解决最大后验概率问题，将求解最大后验概率问题转化为求解加权二部图的最大权匹配问题，进而得到无重叠视域目标的匹配关系。针对普通加权二部图构造中容易引入错误匹配的问题，本发明提出了一种基于自适应阈值的修正加权二部图构造方法，从而尽可能地避免在构造加权二部图的过程中引入错误的匹配。针对传统KM方法在处理大规模加权二部 图匹配问题时计算量过大的弊端，提出了一种基于MH采样的方法近似计算加权二部图的最大权匹配，从而得到无重叠视域目标匹配关系。

本发明的具体操作步骤

1)构造目标观测模型

利用成熟的特征提取技术提取目标特征，进而构造目标观测模型。考虑到无重叠视域下光照变化、背景差异等环境因素都会对目标成像造成影响，进而降低目标观测模型的辨别能力，本发明综合考虑了目标的主颜色特征与空间纹理特征，构造出对环境变化因素比较鲁棒的目标观测模型。主颜色特征描述了目标的宏观信息，本发明使用K均值聚类方法提取目标的主颜色特征，并利用标准化RGB距离计算主颜色间的相似度，从而提高了主颜色特征对光照变化的鲁棒性。空间纹理特征描述了目标的细节信息，本发明将目标分块，并在每个子块不同方向上统计满足梯度条件的像素数目，从而得到用直方图表示的空间纹理特征。本发明使用加权方法将主颜色特征与空间纹理特征融合起来，构造目标观测模型。本发明所用到的主颜色特征的提取示意图如图2(a)所示，其中任意子图左侧为检测到的目标，右侧为所提取的15种主颜色；本发明所用到的空间纹理特征的提取示意图如图2(b)所示，其中任意子图左侧为检测到的目标，中间为梯度图像及分块情况，右侧为表示空间纹理特征的直方图。

2)确定监控网络时空约束

本发明在假设监控网络拓扑已知的前提下，从监控网络拓扑中获取网络的时空约束信息。监控网络的时空约束包括网络中节点的可达性以及平均通过时间，节点可达性可以通过监控网络拓扑中的连通边确定。如果拓扑中某两个节点之间存在连通边，那么这两个节点对应的监控区域是可达的。对于拓扑中连通的两节点，其转移时间分布通常由一个单高斯分布决定，那么这两个点对应的网络节点间的平均通过时间为单高斯分布的均值。本发明所用到的监控网络拓扑示意图如图3所示，其中，黑色箭头表示拓扑节点间的连通性。

3)划分时空最小单元

对于无重叠视域目标匹配问题，相同目标可能会在多个地点、多个时刻出现，从而导致目标匹配问题存在较大不确定性。本发明提出了时空最小单元的概念，在任意时空最小单元中，消失观测值对应的目标再次出现时，只可能在此最小单元 所确定的空间范围内，而且出现的时间必须在此最小单元所确定的时间范围内。时空最小单元的划分将整个监控网络、所有时间段内的目标匹配问题分解为独立的观测值两两匹配问题，从而最大程度上消除了目标匹配中的不确定性。时空最小单元划分必须遵循两个原则，分别是完备性原则与最小化原则。

假设对于某个包含k个节点的独立单元U(U＝{node_i|i＝1,2,…,k})，U的空间最小单元划分必须满足下面两条原则：

①完备性原则：从单元U中任意节点node_i消失的目标，其再次出现时所在的节点node_j满足node_j∈U；同样的，在单元U中任意节点node_j出现的目标，其上一次消失时所在的节点满足node_i∈U。

②最小化原则：在满足完备性的基础上，令每个单元包含最少数目的节点。

时间最小单元划分中的完备性原则与最小化原则与空间最小单元划分的完备性原则与最小化原则类似。

如图4所示为本发明中的空间最小单元划分示意图，分割过程如下：首先去掉图中的虚线连接，将原先的连通图变成非连通图，此时图中的每个连通子图就表示一个空间最小单元。由于每个单元都是连通图，对单元中的任意节点而言，与其连通的节点必然仍在该单元内，这样就满足了单元分割的完备性原则。如果将单元内任意节点分离出去，那么对与该节点连通的其他节点来说，与其连通的节点不在同一单元内，就违反了完备性原则。因而，单元内没有任何节点可以分离出去，这样就满足了单元分割的最小化原则。对于图4所示的拓扑结构，可以得到两个独立单元，分别是{3,8,10,11,14}以及{4,7,9}。

如图5所示为本发明中的时间最小单元划分示意图，分割过程如下：首先，确定图中的消失观测值与出现观测值。假设观测值O₄ ¹表示在t1时刻节点4检测到的第1个观测值，将其分为O₄ ^1-以及O₄ ¹⁺，分为位于图的两侧。按照相同的方法添加完所有观测值后，利用拓扑节点间的时间可达性列出不同观测值的连通情况，并将每个子连通空间作为一个时间最小单元。以图5为例，两个最小时间单元分别是{t1-t1:t1-t4}以及{t2-t5:t6-t8}。

观测值之间的连通情况是通过拓扑节点的时间可达性估计得到的，假设节点4与节点9的转移时间分布服从N(μ,σ²)，那么对于观测值O₄ ^1-与O₉ ¹⁺，连通情况可以如下定义：

其中，t4-t9表示目标通过节点的时间，阈值3σ是根据高斯分布中的3σ准则得到的。

4)构造最大后验概率问题

无重叠视域目标匹配就是通过特定的数据融合方法将目标观测模型与监控网络时空约束融合起来，从而得到准确的目标匹配信息。贝叶斯推断是一种常用的数据融合方法，本发明利用贝叶斯推断准则将无重叠视域目标匹配问题表示成一个最大后验概率问题。假设在某个时空最小单元内，检测到Mi个消失的观测值，记作O_i＝{O_i ¹,O_i ²,…,O_i ^Mi}，其中O_i ^m表示该最小单元中第i个摄像机捕捉到的第m个目标的信息，包括目标的观测模型O_i ^m(app)与时空约束关系O_i ^m(st)。由于目标的观测模型与目标在监控网络中出现的时间与位置无关，因此可以认为O_i ^m(app)与O_i ^m(st)相互独立。同理，检测到N_j个出现的观测值，记作O_j＝{O_j ¹,O_j ²,…,O_j ^Nj}。令表示观测值对(O_i ^m,O_j ⁿ)相互关联，那么，无重叠视域目标匹配问题可以表示为寻找一个匹配集合满足以下条件：

①∈A当且仅当O_i ^m及O_j ⁿ属于同一目标；

②一个观测值至多只有一个前继及一个后继，即对所有有

假设是目标匹配问题的一个解，并且所有的匹配相互独立，那么目标匹配问题可以表示为：

其中，表示检测到观测值O_i ^m与O_j ⁿ之后，匹配发生的概率。通过贝叶斯推断可以得到：

可以将目标的观测模型O_i ^m(app)及时空约束信息O_i ^m(st)引入到目标匹配问题中，定义如下：

其中，表示目标的观测模型匹配率， 表示拓扑结构的时空约束信息，表示目标从摄像机C_i到C_j的转移概率，p(O_i ^m,O_j ⁿ)使用一个常数尺度因子表示(假定目标出现属于均匀分布)。

无重叠视野目标匹配问题就是寻找令后验概率最大时的解A*：

5)计算自适应阈值

在传统的加权二部图构造过程中，仅仅根据拓扑结构的时空约束向二部图中添加连通边，边的权重为待匹配观测值对的相似度。但是，某些错误的观测值对也可能符合时空约束条件，因此被添加到加权二部图中，并最终导致关联错误。本发明提出自适应阈值来控制加权二部图中连通边的添加，该阈值必须满足下述两个标准：

①如果待匹配观测值的相似度普遍较大，说明坏境的改变对目标匹配的影响较小，此时应该增加阈值，从而排除错误的观测值对；反之，如果待匹配观测值的相似度普遍较小，此时应该减小阈值，从而防止排除正确的匹配关系。

②如果某个最小单元中消失观测值数目与出现观测值数目不一致，说明可能发生了误检测或盲区替换，此时应该增加阈值，从而排除非理想观测值对。

基于上述两条原则，本发明提出的自适应阈值的计算过程如下所述：对于任意的消失观测值，计算其与出现观测值的相似度，并将最大相似度添加到集合U中。对每个消失观测值进行类似处理后，将U降序排列得到一个包含n个元素的集合。假设正确的观测值对大于总观测值对数目的一半(误检测或盲区替换的发生概率都比较小)，取出U中前一半元素{u₀,u₁,…,u_m}，动态阈值Φ定义如下：

其中，表示选中元素的均值，用来表示环境因素对于动态阈值设定的影响。n表示最小单元中消失目标观测值数目。P_a表示自适应参数，用来调整阈值，如果最小单元中消失目标的观测值数目与出现目标的观测值数目不一致，需要增加P_a的值以提高阈值。

6)构造修正加权二部图

在理想条件(时空最小单元中的消失观测值与出现观测值一一对应)下，将最大后验概率问题转化为加权二部图的描述过程如下：假设在某个最小单元中，消失观测值与出现观测值分别构成加权二部图的两个点集，表示为X＝{x₁,x₂,…,x_m}与V＝{v₁,v₂,…,v_m}。利用监控网络的时空约束判断任意观测值对x_i-v_j的连通性，从而构成加权二部图的边。对于某条连通的边x_i-v_j，计算x_i与v_j的观测模型匹配率，作为边的权重。如此，就将原始最大后验概率问题转化为加权二部图问题。对于本发明提出的修正加权二部图的构造，并未简单将满足时空约束的观测值对添加到加权二部图中，而是按照1)中的方法计算自适应阈值Φ，然后将观测模型匹配率≥Φ的观测值对添加到加权二部图中，从而构造出修正加权二部图。本发明所构造的修正加权二部图示意图如图6所示，该图包含4对消失、出现观测值，黑色连线表示加权二部图的边，边权w_ij表示x_i与v_j的观测模型匹配率。

7)MH方法近似求解加权二部图的最大权匹配

利用MH方法计算二部图的最大权匹配，首先要将加权二部图问题转化成MH方法所需要的形式，即定义目标状态x、“提议函数”Q(x,·)以及概率分布函数P(x)。假设对于加权二部图G＝{U,V,E}，选取点集U进行匹配。令x表示当前的状态空间，x∈{0,1}|E|，xij表示边(ui,vj)的匹配关系，xij＝1表示ui与vj匹配，即ui与vj之间有连通边；反之，xij＝0表示ui与vj不匹配。令Q(x’|xt)表示“提议函数”，即如何从当前状态xt下推断出下一时刻的可能状态x’。由于此处要解决的是二部图加权匹配问题，因此本发明定义“提议函数”为任取两对观测值并交换它们的连通关系，即：取出ui与vj、um与vn,当前状态为xij＝1并且xmn＝1，经过“提议函数”处理后xin＝1并且xmj＝1，其余点的连通关系保持不变。在计算接受概率时，本发明综合考虑了“提议函数”Q(x’|xt)与概率分布函数P(x)，即令f(x’)＝Q(x’|xt)P(x’)。f(x)的定义如下：

①当任意选取的两对点包含共享点时(即一侧的两个点与另一侧的相同点连接)，f(x)＝0；

②当任意选取的两对点不包含共享点时，即当前状态的加权值。

在实际计算时，对于第②步中的计算当前状态的加权值，只需要考虑变换连通关系的那两对观测值对整体加权值的影响即可。如果选中的某对点是不可能连通的，那么令该对点的权值为-1，从而对错误的连接进行惩罚。方法2给出了基于MH采样近似的二部图最大权匹配流程。

方法1(基于MH采样近似的二部图最大权匹配)

1:Initializing：x₀,t＝0,f(x_t)＝0；

2:loop

3:Sample x’from Q(x’|x_t)；

4:Sample U from U(0,1)；

5:Calculate the acceptance ratio

6:if U≤α(x_t|x’)then

7: x_t+1＝x’；

8:else

9:x_t+1＝x_t；

10:end if

11:t＝t+1；

12:end loop 。

Claims (2)

1.一种基于修正加权二部图的无重叠视域目标匹配方法，其特征在于，使用最大后验概率问题描述无重叠视域目标匹配，在构造最大后验概率问题时，综合考虑目标观测模型与监控网络时空约束；构造加权二部图，通过解二部图的最大权匹配以解决最大后验概率问题；具体包括以下步骤：

1)确定目标观测模型；

所述目标观测模型的构造可选用颜色特征、纹理特征、形状特征中的一种或几种进行组合，对于上面所述的任意特征，都包含大量的子特征，所述子特征包括但不限于：颜色特征包括主颜色特征、RGB直方图特征、HSV直方图特征，纹理特征包括边缘特征、HOG特征、LBP特征，形状特征包括面积特征、离散度特征；

2)确定监控网络时空约束；

监控网络时空约束的确定中，所述监控网络的时空约束包括网络中节点的可达性以及平均通过时间，这两种信息可以通过人为给定，也可以从监控网络拓扑中获得；

3)划分时空最小单元；

根据监控网络的时空约束，将监控网络拓扑按完备性原则与最小化原则划分为多个最小单元，对于最小单元中的任意消失目标，其再次出现仍然位于最小单元中；

4)构造最大后验概率问题；

利用贝叶斯推断准则将无重叠视域目标匹配问题表示成一个最大后验概率问题，假设i、j、k、l表示监控网络中摄像机的序号，m、n、c、d表示不同摄像机捕捉到的目标的序号，在某个时空最小单元内，检测到M_i个消失的观测值，记作O_i＝{O_i ¹,O_i ²,…,O_i ^Mi}，其中O_i ^m表示该最小单元中第i个摄像机捕捉到的第m个目标的信息，包括目标的观测模型O_i ^m(app)与时空约束关系O_i ^m(st)，由于目标的观测模型与目标在监控网络中出现的时间与位置无关，因此可以认为O_i ^m(app)与O_i ^m(st)相互独立；同理，检测到N_j个出现的观测值，记作O_j＝{O_j ¹,O_j ²,…,O_j ^Nj}，令表示观测值对(O_i ^m,O_j ⁿ)相互关联，那么，无重叠视域目标匹配问题可以表示为寻找一个匹配集合满足以下条件：

①当且仅当O_i ^m及O_j ⁿ属于同一目标；

②一个观测值至多只有一个前继及一个后继，即对所有有

假设是目标匹配问题的一个解，并且所有的匹配相互独立，那么目标匹配问题可以表示为：

其中，表示检测到观测值O_i ^m与O_j ⁿ之后，匹配发生的概率；通过贝叶斯推断可以得到：

可以将目标的观测模型O_i ^m(app)及时空约束信息O_i ^m(st)引入到目标匹配问题中，定义如下：

其中，表示目标的观测模型匹配率，表示拓扑结构的时空约束信息，表示目标从摄像机C_i到C_j的转移概率，使用一个常数尺度因子表示，假定目标出现属于均匀分布；

无重叠视域目标匹配问题就是寻找令后验概率最大时的解A^*：

5)计算自适应阈值；

该阈值必须满足下述两个标准：

①如果待匹配观测值的相似度普遍较大，说明环境的改变对目标匹配的影响较小，此时应该增加阈值，从而排除错误的观测值对；反之，如果待匹配观测值的相似度普遍较小，此时应该减小阈值，从而防止排除正确的匹配关系；

②如果某个最小单元中消失观测值数目与出现观测值数目不一致，说明可能发生了误检测或盲区替换，此时应该增加阈值，从而排除非理想观测值对；

基于该阈值必须满足两个标准①②，所述自适应阈值的计算过程如下所述：对于任意的消失观测值，计算其与出现观测值的相似度，并将最大相似度添加到集合U中，对每个消失观测值进行类似处理后，将U降序排列得到一个包含q个元素的集合；假设正确的观测值对大于总观测值对数目的一半，误检测或盲区替换的发生概率都比较小，取出U中前一半元素{u₀,u₁,…,u_r}，动态阈值Φ定义如下：

其中，r＝(q/2)-1，表示选中元素的均值，用来表示环境因素对于动态阈值设定的影响，q表示最小单元中消失目标观测值数目，P_n表示自适应参数，用来调整阈值，如果最小单元中消失目标的观测值数目与出现目标的观测值数目不一致，需要增加P_n的值以提高阈值；

6)构造修正加权二部图；

在理想条件时空最小单元中的消失观测值与出现观测值一一对应的情况下，将最大后验概率问题转化为加权二部图的描述过程如下：假设在某个最小单元中，消失观测值与出现观测值分别构成加权二部图的两个点集，表示为X＝{x₁,x₂,…,x_λ}与V＝{v₁,v₂,…,v_λ}；利用监控网络的时空约束判断任意观测值对x_b-v_h的连通性，从而构成加权二部图的边，对于某条连通的边x_b-v_h，计算x_b与v_h的观测模型匹配率，作为边的权重，如此，就将原始最大后验概率问题转化为加权二部图问题；

按照步骤5)中的方法计算自适应阈值Φ，然后将观测模型匹配率的观测值对添加到加权二部图中，从而构造出修正加权二部图；

7)MH采样的加权二部图的最大权匹配近似求解主要步骤：

a)MH(Metropolis-Hastings)采样方法

所述MH采样方法中的“提议函数”Q(x,y)必须满足以下三个条件：

i，当x固定时，Q(x,·)是一个概率密度函数；

ii，对于任意的x、y，Q(x,y)可以计算出来；

iii，当x固定时，可以方便的从Q(x,y)中产生随机数；

在满足上述条件的前提下，“提议函数”Q(x,y)理论上是可以任意选取的；MH采样方法利用“提议函数”Q(x,·)从当前分布x_t中生成下一刻的可能分布x’，并定义接受概率判断是否接收状态x’为新的状态；MH采样方法通过“提议函数”更新状态，并计算接受概率以判断是否接受新的状态，如果不接受新的状态，那么当前状态仍然是前一时刻的状态，接受概率揭示了当前状态与新的状态哪个更加接近于目标的真实状态，通过不断地更新状态并判断是否接受新状态，可以逐渐逼近目标的真实状态；

b)基于MH采样的近似二部图最大权匹配求解

利用MH采样方法计算二部图的最大权匹配，首先要将加权二部图问题转化成MH采样方法所需要的形式，即定义目标状态x、“提议函数”Q(x,·)以及概率分布函数P(x)，假设对于加权二部图G＝{U,V,E}，选取点集U进行匹配，令x表示当前的状态空间，x∈{0,1}^|E|，x_bh表示边(u_b,v_h)的匹配关系，x_bh＝1表示u_b与v_h匹配，即u_b与v_h之间有连通边；反之，x_bh＝0表示u_b与v_h不匹配；令Q(x’|x_t)表示“提议函数”，即如何从当前状态x_t下推断出下一时刻的可能状态x’；由于此处要解决的是二部图加权匹配问题，因此定义“提议函数”为任取两对观测值并交换它们的连通关系，即：取出u_b与v_h、u_λ与v_z，当前状态为x_bh＝1并且x_λz＝1，经过“提议函数”处理后x_bz＝1并且x_λh＝1，其余点的连通关系保持不变；在计算接受概率时，综合考虑“提议函数”Q(x’|x_t)与概率分布函数P(x)，即令f(x’)＝Q(x’|x_t)P(x’)，f(x)的定义如下：

(b-1)当任意选取的两对点包含共享点时，即一侧的两个点与另一侧的相同点连接，f(x)＝0；

(b-2)当任意选取的两对点不包含共享点时，即当前状态的加权值；

对于第(b-2)步中的计算当前状态的加权值，只需要考虑变换连通关系的那两对观测值对整体加权值的影响即可，如果选中的某对点是不可能连通的，那么令该对点的权值为-1，从而对错误的连接进行惩罚。

2.根据权利要求1所述的基于修正加权二部图的无重叠视域目标匹配方法，其特征在于，所述步骤1)中子特征使用主颜色特征与HOG特征组合建立目标观测模型。