PCB场景平面点集重复晶格最小基元R0检测算法优化问询

问题背景 #

输入为M个带整数颜色标记的平面点构成的集合(p_1,c_1),...,(p_M,c_M)，对应矩形印刷电路板（PCB）上的不同类型多边形，点集满足如下规则：

• 平移等价性：若多边形p_j = v + p_i（即两个多边形为平移v的重合关系），则对应点满足P(p_j) = v + P(p_i)，且同类型多边形对应点的颜色标记完全一致
• PCB整体为正交有限晶格重复排布结构：
  • 存在最小不可再分的轴对齐基元矩形R0，R0无法由更小的子基元通过相同晶格平移规则拼接得到
  • 晶格由平行于坐标轴的正交向量w1、w2生成，所有格点满足形式p*w_1 + q*w_2 + w_0，其中整数p、q的取值范围为0 ≤ p ≤ P、0 ≤ q ≤ Q
  • R0经所有格点平移得到的矩形集合v_i + R0两两无重叠，完整拼接构成整块PCB
    检测目标为从输入带色点集中，准确恢复最小基元矩形R0及对应的全部平移向量v_i。

现有方案及缺陷 #

当前落地的算法流程分为三步：

1. 初始种子矩形R_s选取
   • 构建覆盖所有输入点、尺寸为(g_x,g_y)的网格G，所有网格点初始计数值置0
   • 将每个输入点p映射到其对应的网格坐标(p_x,p_y)
   • 对每个点对应网格点周围[p_x-d,p_x+d] × [p_y-d,p_y+d]的方形区域内所有网格点计数值加1，完成点集的网格“涂抹”平滑处理
   • 查找网格G中的计数值最大值val_max，筛选计数值不低于val_max90%（或95%，为可调参数）的点集L，选取L中字典序最靠左上的点p_0=(i_{x0},i_{y0})
   • 提取包含p0、网格计数值高于val_max50%的连通域，取该连通域的轴对齐外接矩形
   • 上述外接矩形即为初始种子矩形R_s
2. 对R_s和全点集做互相关运算，匹配点集中所有R_s的出现位置，得到候选平移向量集合v_1,...,v_N
3. 迭代扩大R_s为R_s'，扩大过程的约束为：所有候选平移向量作用后的v_i + R_s'都能在点集中匹配到一致的内容；当R_s'无法继续扩大时，将当前矩形作为检测输出的R0

该方案在多数常规场景下可正常输出结果，但存在固有失效风险：

• 典型失效案例为2×6排布基元的PCB场景，算法选取的种子R_s在单个真实基元内部就重复出现16次，全程共检测到192个误匹配位置，导致第三步的矩形扩大过程提前终止，无法得到正确的R0
• 纯局部特征选种存在本质缺陷：若选中基元内部本身存在重复的局部图案作为种子，会产生大量无效平移匹配，直接干扰后续扩种逻辑
• 替换为全局自相关方案也无法解决该问题：小偏移量对应的互相关峰值往往高于真实基元平移步长对应的峰值，无法直接从中提取正确的平移周期。

需求 #

需要可稳定正确检测最小基元矩形R0的改进算法，或可保证最终结果正确收敛到R0的鲁棒种子矩形R_s选取方案。

内容的提问来源于stack exchange，提问作者Jürgen Böhm