第1期 曹田，等：快速的圆投影图像匹配算法 ·87· 中，即将该点对应mask值设置为m_up和m_left ble中，将对应mask点的值设置为hash table,以 的较大值，如果P点对应相似度大于簇中最相似 此建立新的簇种子点。 点的相似度，则更新簇中最相似点的位置和相似 3)计算下一个点，重复步骤2)，直到所有的 度，否则不更新hash table; 点遍历完，计算结束。 ②反之，如果m_up和m_left都为零，说明 4)最终将hash table中的点位置保存下来。 P是新的点，将P对应位置和相似度放入hash ta- 初始化：mask为全 0,hash table为空 计算当前点P所在子 图与模板的相似度T N T>thresh Y 计算当前点上方和左边点对 将P点对应mask值设 应mask值：m_up、m_le 为max(m_up,m_left) N m up-0 m left=0 N T>hash table[m_p] Y Y table插入[P,T刀. 使用当前P和T更新 不更新 mask[P]=table.size hash table值 hash table 计算下一个点 所有点计算完毕一 Y 结束计算】 图5顶部层次聚类流程图 Fig.5 Top hierarchical clustering flowchart 以LENA图像为例，使用局部聚类之后的 suppression,NMS),选取本层最终候选点。 mask图像如图6所示。 NMS的基本思想是保留局部最大值、抑制非 极大值，计算流程如下：对于候选点列表B及其 对应的相似度S,结果候选点集合为D,采用下面 的计算方式： 1)将候选点集合B根据相似度得分进行降序 排列。 (a)匹配之后的效果 (b)模板 (c)mask图 2)选择具有最大得分的点P,将其从B集合 中移除并加入到最终的候选点集合D中。 图6局部聚类效果 Fig.6 Sketch of local clustering 3)计算B中剩余候选点中与P距离dis,将 dis小于阈值d(此处阈值一般选择为模板的内切 可以看到，使用局部聚类，可以在线性时间内 圆半径)的点从B中移除。 快速滤除干扰点，将相邻候选点聚集成簇，减少 4)重复这个过程，直到B为空或D中候选点 后续候选点数，减少了计算量。 数已超过一定数量。此时D中保留的候选点，作 2.3.2逐层金字塔筛选 为本层最终的候选点集。 上一层得到若干候选点之后，传入本层，对候 NMS流程示意图如图7所示。刚开始O~O, 选点相应位置进行扩大区域方法搜索，如果计算 计算得到的分值分别为0.9、0.7、0.6、0.8；通过选 相似度大于阈值，将其传入到本层候选点集合 择最大得分O,加入候选集D并在B中删除，删 中。但是在本层候选集合中有很多候选点，全都 除B中与O1距离在r以内的点(O2、O),在B中 传入下一层进行扩散搜索是非常耗时的。为了减 选择最大得分的点（仅有O),加入到D中，并将 少运算量，这里引入非极大值抑制(non-maximum 其从B中删除，得到D{O、O}。中，即将该点对应 mask 值设置为 m_up 和 m_left 的较大值，如果 P 点对应相似度大于簇中最相似 点的相似度，则更新簇中最相似点的位置和相似 度，否则不更新 hash_table； ② 反之，如果 m_up 和 m_left 都为零，说明 P 是新的点，将 P 对应位置和相似度放入 hash_ta￾ble 中，将对应 mask 点的值设置为 hash_table，以 此建立新的簇种子点。 3) 计算下一个点，重复步骤 2)，直到所有的 点遍历完，计算结束。 4) 最终将 hash_table 中的点位置保存下来。 初始化：mask为全 0，hash table为空 计算当前点P所在子 图与模板的相似度T T>thresh 计算当前点上方和左边点对 应mask值：m_up、m_left m_up=0 & m_left=0 N N N N Y Y Y Y table插入[P,T], mask[P]=table.size 计算下一个点 将P点对应mask值设 为max(m_up, m_left) T>hash_table[m_p] 使用当前P和T更新 hash_table值 不更新 hash_table 所有点计算完毕 结束计算 图 5 顶部层次聚类流程图 Fig. 5 Top hierarchical clustering flowchart 以 LENA 图像为例，使用局部聚类之后的 mask 图像如图 6 所示。 (a) 匹配之后的效果 (b) 模板 (c) mask图 图 6 局部聚类效果 Fig. 6 Sketch of local clustering 可以看到，使用局部聚类，可以在线性时间内 快速滤除干扰点，将相邻候选点聚集成簇，减少 后续候选点数，减少了计算量。 2.3.2 逐层金字塔筛选 上一层得到若干候选点之后，传入本层，对候 选点相应位置进行扩大区域方法搜索，如果计算 相似度大于阈值，将其传入到本层候选点集合 中。但是在本层候选集合中有很多候选点，全都 传入下一层进行扩散搜索是非常耗时的。为了减 少运算量，这里引入非极大值抑制 (non-maximum suppression, NMS)，选取本层最终候选点。 NMS 的基本思想是保留局部最大值、抑制非 极大值，计算流程如下：对于候选点列表 B 及其 对应的相似度 S，结果候选点集合为 D，采用下面 的计算方式： 1) 将候选点集合 B 根据相似度得分进行降序 排列。 2) 选择具有最大得分的点 P，将其从 B 集合 中移除并加入到最终的候选点集合 D 中。 3) 计算 B 中剩余候选点中与 P 距离 dis，将 dis 小于阈值 d(此处阈值一般选择为模板的内切 圆半径) 的点从 B 中移除。 4) 重复这个过程，直到 B 为空或 D 中候选点 数已超过一定数量。此时 D 中保留的候选点，作 为本层最终的候选点集。 NMS 流程示意图如图 7 所示。刚开始 O1~O4 计算得到的分值分别为 0.9、0.7、0.6、0.8；通过选 择最大得分 O1 加入候选集 D 并在 B 中删除，删 除 B 中与 O1 距离在 r 以内的点 (O2、O3 )，在 B 中 选择最大得分的点 (仅有 O4 )，加入到 D 中，并将 其从 B 中删除，得到 D{O1、O4}。 第 1 期 曹田，等：快速的圆投影图像匹配算法 ·87·