一种基于K-Means聚类法的图像仿射变换控制点选取方法

摘要

本发明涉及一种基于K-Means聚类法的特征点提取与图像匹配方法，借助K-Means聚类算法处理过程(1)为待聚类的特征点分配相应数量的聚类中心；(2)计算每个特征点到聚类中心的距离；(3)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心重复执行步骤(2)和步骤(3)直到达到要求为止；(4)从每个特征点聚类中选取一个离图像中心最远的特征点；(5)提取出匹配的特征点；(6)将最终求出的匹配的特征点用于仿射变换模型参数的计算。本发明实现待配准图像提取的特征点与标准图像中得到的基准特征点间的匹配，选取具有高精度匹配性能的特征点。

说明书

技术领域

本发明涉及特征点匹配方法，尤其是一种基于K-Means聚类法的图像仿射变换控制点选取方法。

背景技术

图像配准是机器视觉领域的一个基本问题，一直是人们研究的热点和难点。图像配准是指在来自不同时间、不同视角或不同传感器的同一场景的两幅或多幅图像之间寻找对应关系。有关图像配准的方法主要分为：基于灰度配准和基于特征配准的方法。

基于灰度配准的方法，也称为相关配准方法，用空间二维滑动模板进行图像配准，不同算法的区别主要体现在相关准则的选择。基于特征点配准方法是首先在原始图像中提取特征，然后建立两幅图像之间特征点的配准关系，具有较高的鲁棒性，比如SURF算法。目前，基于SURF算法图像配准已经得到广泛应用，比如应用于医学图像配准，遥感图像配准等。SURF特征点具有的尺度特性是提取图像中的特征点进行特征点匹配，并将匹配的特征点对用于计算图像配准变换模型参数，使待配准图像准确地变换到标准图像位置，以达到配准目的。特征点的匹配是实现图像配准的关键，匹配的精度直接影响着后续配准的精度。算法中根据SURF特征点描述符中包含的特征点邻域信息，采用K最近邻法可以找出每个特征点潜在的两个最佳匹配点，并通过匹配点的距离最佳值与次佳值比率优选出最佳匹配点对。

根据前文提出的特征点匹配方法，可以实现待配准图像提取的特征点与标准图像中得到的基准特征点间的匹配，匹配成功的特征点对都具有很高的精度。但在实际求解过程中，如何从中选取合适的三个匹配特征点对进行参数计算是实现图像配准则又一个重要因素，如何有效有效特征点是解决问题的关键难题。

发明内容

本发明的目的在于提供一种基于K-Means聚类法的图像仿射变换控制点选取方法，选取最佳的有效特征点，从而获得最佳图像配准。

本发明解决其技术问题是采取以下技术方案实现的：

一种基于K-Means聚类法的图像仿射变换控制点选取方法，其特征在于：利用SURF特征点检测算法在配准图像中检测图像特征点，并根据实际特征点提取的要求，借助K-Means聚类算法处理过程，将特征点的筛选分为以下几个步骤进行实现：

(1)为待聚类的特征点分配相应数量的聚类中心；

(2)计算每个特征点到聚类中心的距离，并将每个点聚类到离该点最近的聚类中；

(3)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心重复执行 步骤(2)和步骤(3)直到聚类中心不再大范围移动或者聚类次数达到要求为止；

(4)在完成所有特征点的聚类后，从每个特征点聚类中选取一个离图像中心最远的特征点，构成一个新的特征点集合；

(5)重新提取的特征点集合中随机选取三个特征点，计算三角形面积，直到最终求出最大的三角形面积，提取出匹配的特征点；

(6)将最终求出的特征点对用于仿射变换模型参数的计算，使待配准图像准确地变换到标准图像位置，以达到配准目的。

而且，所述SURF特征点检测算法是通过计算Hessian矩阵行列式的局部极值来确定特征点的位置，尺度为σ的图像I中点的Hessian矩阵定义为：

$>H=\left(\begin{array}{cc}{L}_{\mathrm{xx}}(\hat{x},\sigma )& L_{\mathrm{xy}}(\hat{x},\sigma )\\ L_{\mathrm{xy}}(\hat{x},\sigma )& L_{\mathrm{yy}}(\hat{x},\sigma )\end{array}\right)$>

式中，L_xx是高斯二阶导同I0(x,y)卷积的结果，其中L_xy,L_yy具有相同的含义。

本发明的优点和积极效果是：

本发明从匹配特征点的分布来研究如何选取有效的三组特征点对进行参数计算，从而实现待配准图像提取的特征点与标准图像中得到的基准特征点间的匹配，选取具有高精度匹配性能的特征点。

附图说明

图1为不同组合的3组匹配特征点对(构成3个三角形面积)；

图2为特征点构成的三角形面积/全图像面积与PSNR值的关系；

图3为特征点聚类的结果；

图4为最终用于计算配准变换模型参数的3个特征点；

图5为9×9盒子滤波模板；

图6为特征点的主方向的选取；

图7特征描述符的构成。

具体实施方式

下面结合附图并通过具体实施例对本发明作进一步详述，以下实施例只是描述性的，不是限定性的，不能以此限定本发明的保护范围。

一种基于K-Means聚类法的图像仿射变换控制点选取方法,利用SURF特征点检测算法在配准图像中检测图像特征点，并根据实际特征点提取的要求，借助K-Means聚类算法处理过程，将特征点的筛选分为以下几个步骤进行实现：

(1)为待聚类的特征点分配相应数量的聚类中心；

(2)计算每个特征点到聚类中心的距离，并将每个点聚类到离该点最近的聚类中；

(3)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心重复执行步骤(2)和步骤(3)直到聚类中心不再大范围移动或者聚类次数达到要求为止；

(4)在完成所有特征点的聚类后，从每个特征点聚类中选取一个离图像图像中心最远的特征点，构成一个新的特征点集合；

(5)重新提取的特征点集合中随机选取三个特征点，计算三角形面积，直到最终求出最大的三角形面积，提取出匹配的特征点；

(6)将最终求出的匹配的特征点用于仿射变换模型参数的计算，使待配准图像准确地变换到标准图像位置，以达到配准目的。

特征点的获取是利用SURF特征点检测算法在配准图像中检测得到。

SURF特征点检测算法是在SIFT算法的基础上提出的一种速度快、鲁棒性强的特征提取算法。该算法不仅对图像旋转、平移、缩放和噪声具有较好的鲁棒性，而且对光照变化和视角变化不变性以及图像模糊度有较好的处理。同时，通过引入积分图像和盒子滤波器，在运算速度上大约提高了3倍，综合性能更加优越。

SURF特征点检测算法是通过计算Hessian矩阵行列式的局部极值来确定特征点的位置。其中，尺度为σ的图像I中点的Hessian矩阵定义为：

$>H=\left(\begin{array}{cc}{L}_{\mathrm{xx}}(\hat{x},\sigma )& L_{\mathrm{xy}}(\hat{x},\sigma )\\ L_{\mathrm{xy}}(\hat{x},\sigma )& L_{\mathrm{yy}}(\hat{x},\sigma )\end{array}\right)$>

式中，L_xx是高斯二阶导同I＝(x,y)卷积的结果，其中L_xy,L_yy具有相同的含义。

SURF算法采用盒子滤波来近似二阶高斯滤波，构造出一种快速Hessian矩阵，并使用积分图像来加速卷积以提高计算速度。

其中，如图5所示为9×9的盒子滤波模板。为了使SURF特征具有尺度不变性，需要构造尺度空间，并在各个尺度空间下通过快速Hessian矩阵行列式得到局部极值点。在此，SURF算法采用不同大小的盒子滤波器与源图像进行卷积以获得不同尺度空间的特征描述。通过盒子滤波处理后，x方向的值记作D_xx，xy方向的值记作D_xy，y方向的值记作D_yy。由于盒子滤波是二阶高斯滤波的近似估计，因此引入比例因子ω(ω近似取0.9)，进一步求解得到快速Hessian矩阵的行列表达式为：

ΔH＝D_xx(x)D_yy(x)-(ωD_xy(x))²

其中，Δ为图像点I(x,y)周围区域的盒子滤波器响应值，用Δ进行极值点的检测。

根据快速Hessian矩阵求出尺度图像在各个尺度空间下局部的极值点后，将每个局部极值点及同一尺度的8个相邻点以及它上下两个尺度的各9个点构成一个3×3×3的立体邻域。将尺度空间的每个极值点与立体邻域相邻的26个点进行比较，只有当局部极值点的值均大于(或小于)所有26个相邻点时，才将此局部极值点作为候选特征点。为了能够对候选特征点进行亚像素定位，可以在尺度空间和图像空间中进行插值，得到稳定的特征点位置及所在的尺度值。

插值使用的二次拟合函数为：

$>D\left(x\right)=D+\frac{{\partial D}^T}{\partial X}X+\frac{1}{2}{X}^T\frac{\partial D}{{\partial X}^2}X$>

对函数求导得到极值点为：

$>\hat{X}=-\frac{{\partial }^2{D}^{-1}}{{\partial X}^2}\frac{\partial D}{\partial X}$>

函数在极值点处的极值为：

$>D\left(\hat{X}\right)=D+\frac{1}{2}\frac{{\partial D}^T}{\partial X}\hat{X}$>

实验中剔除D(x)＜0.03的候选特征点。

SURF特征点的描述 

为保持特征点的旋转不变性，在特征点位置确定以后，为每一个特征点进行主方向的确定。为此，在以特征点为中心，计算半径为6σ(σ为特征点的尺度)的圆形区域内，对图像在x和y方向进行Harr小波(Harr小波边长取4σ)响应运算，并使用尺度为2σ的高斯加权函数对Harr小波响应值进行高斯加权，使得越靠近特征点的响应贡献越大；然后用π/3大小的扇形区域范围遍历整个圆形区域，并将域内水平方向响应和垂直方向响应的矢量和模的最大值的方向定义为特征点的主方向(如图6所示)。

然后，以特征点为中心，构造一边垂直于主方向且边长为20σ的正方形窗口区域，并将该窗口区域划分成4×4的子区域。在每一个子区域内，进行5σ×5σ个采样点的水平方向和垂直方向的Harr小波响应的计算，分别记作d_x和d_y，同样使用尺度为2σ的高斯加权函数对Harr小波响应值进行高斯加权，以增加对几何变换的鲁棒性。然后将每个子区域的响应值和响应值的绝对值相加形成Σd_x，Σd_y，Σ|d_x|，Σ|d_y|。由此，每个子区域就形成了一个四维特征描述向量V:

V＝(Σd_x,Σd_x,Σ|d_x|,Σ|d_y|)

对于每一个特征点，形成4×4×4＝64维的特征向量。为保证对光照的不变性，对特征向量进行归一化处理，得到最终的SURF描述符，如图7所示。

特征点的匹配 

特征点的匹配是实现图像配准的关键，匹配的精度直接影响着后续配准的精度。算法中根据SURF特征点描述符中包含的特征点邻域信息，采用K最近邻法可以找出每个特征点潜在的两个最佳匹配点，并通过匹配点的距离最佳值与次佳值比率优选出最佳匹配点对。

设M₁、M₂分别为两幅图像I₁、I₂分别采用SURF提取的待匹配特征点集合，对M₁中的任一特征点m_1i，M₂中与m_1i的欧式距离最小的两个特征点分别为m_2j,m'_2j，对应距离分别为d_ij，d'_ij，如果d_ij≤α*d'_ij(实验取α＝0.65)，则认为m_1i与m_2j为优选的匹配点对。

利用上面的方法可以得到标准图像和待配准图像所有的匹配点对 其中S、D分别为标准图像和待配准图像完成匹配的特征点集。由于这些匹配点对中存在着一定的误匹配点对，本文采用三角形相似的方法对其进行提纯。在特征点集S、D中任取三个匹配点对P₁与Q₁、P₂与Q₂、和P₃与Q₃，构成虚拟的三角形ΔP₁P₂P₃和ΔQ₁Q₂Q₃，并形成一个三角形对，其三边的长度分别设为lp₁、lp₂、lp₃和lq₁、lq₂、lq₃，如果满足下式中的关系，则表明选取的匹配点对均为有效点对，否则存在误匹配点对，给予剔除，实现特征点对的提纯：

$>\frac{{\mathrm{lp}}_1}{l{q}_1}\approx \frac{{\mathrm{lp}}_2}{{\mathrm{lq}}_2}\approx \frac{{\mathrm{lp}}_3}{{\mathrm{lq}}_3}$>

本实施例实验中边长比之间的误差控制在0.02。

尽管为说明目的公开了本发明的实施例和附图，但是本领域的技术人员可以理解：在不脱离本发明及所附权利要求的精神和范围内，各种替换、变化和修改都是可能的，因此，本发明的范围不局限于实施例和附图所公开的内容。