文档介绍：第31卷第4期 信阳农林学院学报 Vol. 31 No. 4
2021年 12月 研究方向：计算机应用研究。
• 133 •第31卷第4期 信阳农林学院学报 2021年12月
提取特征
使用具有不相交的节点集U和V、E边集和权重函数s的加权二分图G=(UUV,E,w)来表示两个连
续时间步的分配问题。假设在特征提取过程中已经生成了快照S,和S,+j的不同特征对象集合，如图1所
示。时间步t和t + 1中的每个特征对象分别由集合U和V中的节点表示。
集合u和v中节点之间的边表示底层特征对象之间的潜在对应关系。为此,计算每对节点(M,v)eu
XV之间的相似度值，使用两个特征对象之间的归一化体积重叠作为其相似度的度量。假设O ”，O”UQ是
组成各个特征对象的域点集，归一化重叠定义为：
_ io„noj
c u,v max( |O„ I , IO„ I )
该相似性度量的取值范围是[0, □，如果相似度的值接近1,说明特征对象之间的相似度更高。对于所
有节点对(",w)，若其所对应的c(“，o)大于0,则在集合E中插入一条边(“，◎),并使用该相似度值作为边
权重w(w ,w) =c(w ,v);否则,则将边("，0)的权重设置为0„
为了避免对所有特征对象进行比较，通过在两个时间步长中对所有顶点进行线性遍历来构建相似度矩
阵，并计算对象的出现次数。基于这个计数结果,就可以使用式(1)计算c(”e)。给定时间步长的特征对象
之间的对应关系是通过在图G上找到最大权重、最大基数匹配M来确定的。该过程对应于在图中找到边
的子集，使得集合U和V中的每个节点都与在所有潜在的最大基数匹配中，恰好有一条边，并且与这些边相
关联的权重总和是最大的。解决这个匹配问题等价于解决线性分配问题(Linear Assignment Problem,
LAP)WO
虽然假设了特征具有空间填充结构，但是得到的权重矩阵仍然是稀疏的：由于只有少数特征发生重叠，
因此生成了大量的0元素。鉴于此属性,选择了 Cost Scaling Push-Relabel(CSPR)伪流算法来解决匹配问
题，该算法的复杂度为O(^WlE|Zog(|U|C_))[5]„该算法基于这样一种思想，将LSP转换为流网络N
并在其中找到最大权重流来求解LSP。该变换构造了一个源节点并将其连接到集合U中的每个节点，并构
• 134 •郑瑾：基于图优化的时变特征跟踪算法研究
造了一个