本站原创0引言
形状或图像的配准是图像处理、模式识别和计算机视觉等领域中一个基础而又重要的问题,其目标是找到使两形状或图像的特征对应起来的空间变换和对应关系.由于点特征普遍存在且易于获得,该问题通常被描述成一个点匹配问题.在现实中,点配准往往由于非刚性形变、位置噪声和出格点等因素的存在而变得难以解决.为解决这些问题,Besl、Chui、Thayananthan等提出了各种不同的算法[1].Besl等的迭代最近点（Iterated Closest Point, ICP）算法[2]基于最近邻确定对应关系,对应关系和空间变换被交替求解.该算法简单、速度快,但其粗糙的求对应关系的方法容易使能量函数陷入局部极小.对此,Chui等提出一种基于模糊指派[3]和确定性退火[4]的鲁棒点匹配算法（Robust Point Matching, RPM）[5].RPM算法是ICP算法的一种改进.其中,点对应关系被松弛成模糊状态,确定性退火则被用于寻优.该算法对显著非刚性形变、位置噪声和随机出格点干扰具有鲁棒性,但存在较多出格点时,算法将变得不太稳定.Belongie等针对对应关系求解问题,提出一种形状上下文（Shape Context,SC）的特征描述方法[6].该方法对每一点构造形状上下文,它描述了局部区域内其他点相对于该点的位置分布,所有点的形状上下文差别最小的对应关系作为所求解.该方法的缺点是相邻的两点有可能被映射成另一形状上相距很远的两点.针对SC算法无法保持对应关系连续性[7]的缺点,Thayananthan等对于曲线/轮廓匹配问题,提出了一种基于动态规划的算法[8].在该算法中,形状上下文被用于搜索对应点,动态规划[9]被用于使对应关系满足连续性的要求.但由于采用动态规划,该算法只能处理模板点集可以表示成顺序点集的情形.Zheng等则采用另外一种思路来弥补SC算法的不足,得到一种保持局部邻域结构（Preserving Local Neighborhood Structure,PLNS）的算法[10].在该算法中,形状上下文被用于对算法进行初始化,松弛法[11]被用于加强可以保持局部邻域结构的对应关系,削弱不能保持局部领域结构的对应关系.但该算法当目标点集中存在多个相似结构时,配准效果将变差.
本文针对SC算法无法保持对应关系连续性的缺点,提出一种基于线形规划[12]的特征点配准算法（Linear Programming based SC,LPSC）.点配准被建模成一个能量函数最小化问题.在该能量函数中,形状上下文距离被用于引导求解对应关系,相似变换被用于对对应关系的连续性进行约束,可以通过线性规划找到该问题的最优解.
同本文算法相关的是Jiang等的特征点匹配算法[13-14].区别在于Jiang的算法需要额外预先对模板形状进行三角划分,同时对对应关系的约束项不同于本文算法,本文提出的LPSC算法直接采用相似变换模型构造约束项,计算量更小一些.