下载掌阅APP，畅读海量书库
立即打开
点迹融合航迹关联优化求解算法需要建立一种求最优解的准则，即假设树管理策略，内容包括：计分规则、搜索规则、修剪规则、评估规则等。假设树管理策略的质量很大程度上决定了关联的正确率和实时性。
通过分析现有数据结构中树的基本原理，结合关联目标的特性，设计一种假设树管理策略。基本思路是：在采用计分方式对关联假设进行有效评价的基础上，通过修剪，删去最不可靠的分枝（树枝），确定关联成功的分枝（树枝），以提高后续分类的速度和分类新数据的能力，对一些误相关的情况及时修正。
点迹融合航迹关联质量是关于航迹关联历史情况的度量，它以数值形式表示，其大小反映了点迹融合航迹正确关联的可靠程度。计分规则是评价关联质量的重要手段，它根据关联成功的次数，赋予不同关联假设得分。
来自融合航迹库 A 的航迹 i 和传感器 B 的航迹 j 在 k 时刻的关联质量用 Fom （ k ）表示，其计算式为
式中， Fom （ k ）≥0， Fom 值位于假设树的第二层。此层结构中的每个元素即每个关联假设都有一个 Fom 值表示航迹正确关联的可靠程度，其初始值为0，若下一个时刻关联假设成立，则给这个关联假设的 Fom 值加1，同时，对该关联假设同一层中的共有父节点下的其他关联航迹的 Fom 值减1，直到 Fom 为0。
匈牙利解法依据“在系数矩阵中任何行或列加上或减去同一常数并不改变分配方案”的原则，在保证“系数矩阵元素不能出现负数”和“变换使每行每列至少有一个0元素”的前提下，对系数矩阵做适当变换后，选取新矩阵中的0元素，旨在选中完成某项任务花费时间最少的某人，以得到问题的最优解。
从式（3.2.5）可知，该分配问题是特殊的整数规划问题，可采用以下方法转化为标准的分配问题：把关联矩阵 A =（ α ij ） n 1 × n 2 扩展成 n 阶方阵，其中 n =max｛ n 1 ， n 2 ｝，用0元素将 A 补齐 n 阶方阵，所补的0元素行或列被认为是虚拟目标。
匈牙利解法的实现流程如图2.20所示，具体步骤如下：
图2.20 匈牙利解法的实现流程
（1）构建方阵，用0元素将关联矩阵补成 n 阶方阵。
（2）变换关联矩阵 A 到等价矩阵′ A ，在各行（列）中分别减去该行（列）的最小元素，使各行各列都出现0元素。
（3）圈0元素，对′ A 中的0元素作分配标记，作覆盖所有0元素的最少数目的直线集合，直至矩阵′ A 中所有的0元素都被划去为止。若能圈出不同行不同列的 n 个0元素，则已可得出最优解，转（5），否则转（4）。
（4）调整关联矩阵，从未被直线覆盖的元素中找出最小值 d ，未画横线的各行都减 d ，已画竖线的各列都加 d ，转（3）继续进行。
（5）最优分配，令被圈0元素对应位置 x ij =1，其余 x ij =0，这就得到整个分配的最优解，输出分配结果，若有多组解，则给出多组解的点迹—融合航迹配对关系。
该方法可以在不丢失最优解的前提下将可行解的范围逐步缩小，迅速得到最优解。对于目标极大化问题，即式（2.4.5）中的目标函数若为
。此时令
（其中
n
=max｛
n
1
，
n
2
｝）和
M
-
α
ij
≥0，于是考虑目标函数为
的问题，仍用上面的方法求解，所得最小解即为对应原问题的最大解。
下面以两传感器多目标跟踪为例进行解析，如图2.21所示。
图2.21 两传感器多目标跟踪
假设目标位置以二维直角坐标形式给出，横轴为 X 坐标，纵轴为 Y 坐标，单位均为米（m）。传感器1输出5个点迹，传感器2输出5个点迹，且点迹数据经过前期预处理，两传感器输出点迹的坐标如表2.1所列，点迹的位置估计误差方差100m。
表2.1 两传感器输出点迹的坐标
根据式（2.4.2）计算不同传感器的点迹融合航迹两两之间的统计距离 α ij ，得到关联矩阵
关联矩阵中的元素为两传感器的点迹融合航迹两两之间的距离值，性能指标是距离和最小。采用上面的匈牙利解法，得到的关联结果如表2.2所列。
表2.2 两传感器之间的点迹配对关系
由仿真结果可以看出，利用匈牙利解法能够准确地求出问题的最优解，正确地给出点迹融合航迹关联的判断。该方法求解点迹融合航迹关联问题不需要选择门限，而是在一定的约束条件下在全局范围内寻找问题的最优解，匈牙利解法能够有效地解决此类问题，且易于实现。
建立多假设树之后，按照一定准则完成关联判断，判断准则如下：
（1）任取1个第1层子树，在该子树的第2层中找到 Fom 值最大的子节点 P ；然后根据子节点 P 的目标编号及其所属信息源编号的唯一性，找到该编号在其他第1层子树中对应的子节点 P i 的 Fom 值；如果子节点 P 的 Fom 值最大，则认为子节点 P 对应的目标有效关联，否则，找出 P 和 P i 中次大者。
（2）如果1个第1层子树全部搜索完毕，则搜索另外的第1层子树，按照（1）进行处理。
算法对假设树中关联假设事件逐层搜索，当搜索完假设树中所有关联假设事件后，才能找到最大 Fom 值及其对应的关联假设。当两条航迹连续多次关联成功之后，可视为固定关联，在后续的关联检验中，不再进行关联检验，直接进入航迹合成阶段。为了减小假设树的计算量，算法将第2层子树的叶子节点个数设置为 L ，即保留同一关联假设 L 个历史时刻信息，同时，子节点个数 L 可以根据需要调整大小。