面向方形基准标记字典生成的标记间距离最大化：最大团精确方法与紧凑排布启发式方法

《Journal of Imaging》：Maximizing Inter-Marker Distance in Square Fiducial Marker Dictionary Generation

　　

方形基准标记（square fiducial markers）为相机定位任务中的视觉参考建立提供稳健且高效的方式，其将可靠检测与通过嵌入式二进制码实现的唯一识别相结合。此类系统的稳健性在很大程度上取决于有效码之间的最小距离：更大的距离能够校正更多比特错误并降低标记误识别风险。本文提出两种生成具有大标记间距离（inter-marker distance）的方形标记字典的方法。第一种是精确方法，将字典生成问题表述为最大团问题（maximum-clique problem）。与既往精确方法相比，该方法可在更广的情形下获得最优解，尽管其内存与计算需求仍将实际适用性限制于小标记尺寸（3×3与4×4比特）。第二种是基于排布（packing-based）的次优方法，其以增量方式构建字典，并可扩展至更大的码尺寸与字典尺寸。实验结果表明，所提方法优于现有字典生成方法，能够构建具有增强误差检测与误差校正能力的更大字典。源代码与生成的字典已公开可用。

研究背景与问题：相机定位是增强现实、机器人导航与三维重建等计算机视觉应用的基础需求，其关键在于建立真实世界点与图像投影之间的可靠对应。方形基准标记以黑色边框便于检测，以四角提供位姿估计所需点，并以内部二进制码实现唯一识别。标记系统由其字典（dictionary）表征，即被接受为有效标记的二进制码集合；检测时需定位方形候选并解码内部比特以判断是否为有效标记。字典的关键属性是标记间距离（inter-marker distance），即考虑标记可能被观测的不同方式后，任意两个有效标记之间的最小汉明距离（Hamming distance，两个等长二进制串中不同比特位的数量）。距离越大，对像素噪声、模糊和不良光照所致比特解码错误的容忍度越高，误识别风险越低。测量该距离时需考虑两类变换：标记在图像中可能旋转，因此四种旋转应视为等价；标记可能经镜面或反射面观测，从而反转比特模式。现有标记库多提供预定义字典，但未必适合特定应用所需标记数量或码尺寸，且不总能达到最佳标记间距离；已有生成方法中，仅基于混合整数线性规划（mixed-integer linear programming, MILP）的精确表述保证最优，但计算成本限制其适用于小标记与小字典尺寸。因此，研究人员开展研究以提出更广适用的精确方法和可扩展的次优方法，并提升字典的误差检测与误差校正能力。
研究人员提出两种互补方法。其一为所提最优方法（Proposed Optimal），将字典生成表述为最大团问题，在可处理的小标记尺寸上获得比既往精确MILP更广范围的最优解；其二为所提次优方法（Proposed Suboptimal），受最优字典呈现紧凑结构这一观察启发，以基于排布的启发式增量构建字典，使新增标记在满足目标距离约束下尽可能紧凑，从而为后续标记留出空间并扩展至更大码尺寸与字典尺寸。实验表明，所提次优方法在2000个评估配置中达到或超过所有竞争方法的标记间距离，并在约72%的配置中获得严格更大的距离，说明其能产生具有更强误差检测与误差校正能力、更低误识别风险的字典。
关键技术方法概括（不超过250字）：研究人员以类似集合（analogous set，同一标记在旋转/反射下的等价观测集合）定义标记间距离与自距离（self-distance，标记与其自身非原始变换观测间的最小距离），并以此形式化字典生成。精确方法对固定目标距离u构建无向图，顶点为自距离不小于u的标记代表，边连接距离不小于u的标记，递减u求最大团（maximum clique，图中两两相连的最大顶点子集），最大团即该距离下最大字典。次优方法对每个u从空字典增量插入标记，每步求解二进制整数优化问题，使用Google OR-Tools的CP-SAT求解器，目标为在满足距离约束下使新标记尽量紧凑，并设时间限制与重启策略；最大团实例用Konc和Jane?i?分支定界算法求解。实验考虑仅旋转情形，覆盖3×3与4×4比特等标记尺寸、至多500个字典尺寸的2000个配置，每配置用5个随机种子取均值，每次求解限时150 s；不涉及样本队列来源。
研究结果：
6.1 Results of the Optimal Method（最优方法结果）：通过在不同目标距离下构建最大团图并与既往最优MILP方法比较，研究人员得出所提最优方法在更广实例上保证最优。在可完整求解的小尺寸标记上，方法计算所有可能字典尺寸的最优字典，最大非零标记间距离字典含120个标记，首次给出完整最优曲线；在4×4比特标记上，当目标距离使最大团图过密时求解时间急剧增加，超过31个标记的字典无法获得，31标记字典耗时超过四天，随后三天以上未找到更大解，总计算超过一周。尽管如此，该方法显著扩展了可最优求解的实例范围。
6.2 Results of the Suboptimal Method（次优方法结果）：通过将所提排布式方法与MILP次优方法、Greedy、ArUco、AprilTag及限时最大团方法比较，研究人员得出所提次优方法在每一评估配置中匹配或优于其他方法；在2000个字典中1431例（约72%）严格更大。原文给出的案例中，某一标记尺寸下所提方法生成至少500个标记且保持距离12，而最佳替代在同距离下少于300个标记；另一案例中所提方法生成至少500个标记且距离8，而最佳替代约100个标记；在评估范围内竞争方法降至6时，所提方法保持8。运行间标准差多数为零，其余很低。
6.2.1 Generation Time（生成时间）：通过比较累积生成时间，研究人员得出字典生成时间通常不是主要问题，因为字典通常只需生成一次。较小标记上ArUco、AprilTag与Greedy最耗时，所提次优与MILP最快；较大标记上所提次优耗时明显增加，原因在于紧凑排布目标使求解器常持续搜索至时间限制，且目标距离降低时需从空字典重启。时间限制分析显示10 s略差，50 s以上所得距离相近且总时间显著降低，但为对所有方法采用同一计算标准，实验保留150 s；在所有评估时间限制下，所提方法仍优于竞争方法。
6.2.2 Effect of the Compact-Packing Objective（紧凑排布目标的作用）：通过消融比较带紧凑排布目标与仅返回任意可行标记的变体，研究人员得出紧凑排布目标从不产生更小标记间距离，并在小中标记上明显改善结果；移除目标可降低计算成本，较大标记上成本降低约26倍与41倍，表明该目标对更大距离有贡献但伴随计算代价。
6.2.3 Marker Complexity（标记复杂度）：通过比特转移率（相邻异值单元对占比）比较生成字典，研究人员得出所提方法虽未施加复杂度约束，但其标记复杂度在各标记尺寸上相似，仅略低于AprilTag与ArUco；将标记复杂度约束显式纳入表述留作未来工作。
讨论部分总结：所提最优方法将字典生成表述为最大团问题，较既往精确方法扩展了最优可解范围，但受内存与最大团求解时间限制，仍限于小标记尺寸和中等字典尺寸；最优字典的紧凑结构启发了可扩展的排布式次优方法，后者通过增量插入并强调紧凑放置，在标记间距离上显著优于既往方法，产生更强误差检测与误差校正能力及更低误识别风险，并在约72%的2000个配置中取得严格更大距离。未来工作包括以替代团求解算法和表述缓解最优方法计算与内存限制，评估替代求解器，开展反射感知设置的全面实验，以及显式加入标记复杂度约束。
研究结论翻译：基准标记字典的标记间距离是决定其误差检测与误差校正能力的关键因素。本工作提出两种生成具有大标记间距离的方形基准标记字典的方法。所提最优方法将字典生成表述为最大团问题，并比既往精确方法在更广情形下计算最优字典。然而，受内存需求所限，其适用性仍限于小标记尺寸；受求解大规模最大团实例所需时间所限，其适用性仍限于中等字典尺寸。尽管存在这些限制，最优字典中观察到的紧凑结构促成了第二种方法。所提次优方法通过将每个新标记在目标距离允许范围内尽可能紧凑地放置来增量构建字典，并可扩展至精确方法无法企及的标记与字典尺寸。实验结果表明，所提方法在标记间距离方面显著优于既往方法，产生具有更强误差检测与误差校正能力以及更低标记误识别风险的字典。具体而言，所提次优方法在2000个评估配置中达到或超过所有竞争方法的标记间距离，并在约72%的配置中获得严格更大的距离。未来工作将集中于通过探索替代团求解算法和表述来扩展最优最大团表述对更大实例的适用性，以缓解其当前计算与内存限制。更一般地，评估两种所提方法的替代求解器可进一步了解其计算效率与所得字典质量。此外，尽管本研究聚焦仅旋转情形，所提方法可通过修改类似集合定义轻松扩展以考虑反射。因此，反射感知设置下的全面实验评估也留作未来工作。最后，尽管所提方法已产生复杂度与现有方法相当的标记，但将标记复杂度约束显式纳入表述以进一步降低与自然图像模式混淆，是另一个有趣的未来工作方向。两种方法的源代码与实验中生成的字典已公开可用。