一种基于点线对偶的图像匹配方法

摘要

本发明公开了一种基于点线对偶的图像匹配方法，包括：从参考图像R和目标图像S中分别提取直线，以得到参考直线集合和目标直线集合，分别将参考直线集合和目标直线集合中所有的直线段从图像空间映射到对偶空间，以得到参考对偶点集

说明书

技术领域

本发明属于计算机视觉和图像处理领域，更具体地，涉及一种基于点 线对偶的图像匹配方法。

背景技术

图像匹配是计算机视觉中一个十分重要的问题，是实现图像分析和图 像理解等高级视觉功能的一个基本步骤，在生产装配自动化、质量检测、 目标识别定位、安防监控、超分辨率重建、全景拼接、医学图像融合等众 多领域有着广泛应用。

在图像匹配中，一个关键的问题是选择何种特征，合适的特征可以使 得匹配过程快速、匹配结果稳定且准确。数字图像最基本的特征是的灰度， 基于灰度的图像匹配是最早提出、研究最多的图像匹配技术之一，然而存 在对光照变化、噪声敏感等缺点。为了提高图像匹配的稳定性和速度，角 点、边缘、直线、圆弧等几何基元被从图像中提取出来并被用作匹配特征， 基于几何基元的图像匹配对图像进行了更高层次的分析，排除了许多无用 信息，所使用的特征具有更加直观、明确的意义，是目前图像匹配技术研 究的热点。

点是最常用的几何基元，如何选择点对图像匹配的结果有重要影响。 点的数目多，则匹配精度较高，但速度较慢；反之，则精度降低，速度提 高。直线可以通过对边缘进行各种处理之后得到，进一步除去了离群点和 噪声点，是更加高级的几何基元。一般来说，从图像中提取的直线的数量 要远远少于提取的点的数量，所以使用直线作为特征的图像匹配算法会具 有更高的计算效率。有些直线匹配方法首先利用部分直线生成一些可能的 匹配假设，然后利用其余的直线来进行验证。有些直线匹配方法使用直线 之间的交点来完成匹配。有些直线匹配方法根据直线邻域内的像素信息构 造高维特征向量，然后通过比较特征向量的相似性完成匹配。但是目前大 多数的直线匹配方法都是在图像空间进行的，对由于噪声和污染导致的直 线段断裂破碎，以及由于部分遮挡导致的直线段断开等情况难以进行直观 而有效地处理，所以严重影响了匹配过程的高效性和匹配结果的稳定性。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于点线对 偶的图像匹配方法，其目的在于通过首先将直线从图像空间转换到对偶空 间变成点，从而将直线匹配问题转化为点集匹配问题，然后在对偶空间进 行点融合，最后在对偶空间中匹配两个点集，从而实现图像匹配，以此等 效地把图像空间中断裂破碎的多条直线段重新融合为一条直线段，提高了 匹配效率和稳定性。

为实现上述目的，按照本发明的一个方面，提供了一种基于点线对偶 的图像匹配方法，包括以下步骤：

（1）从参考图像R和目标图像S中分别提取直线，以得到参考直线集 合和目标直线集合，其中从R中提取的参考直线集合记为共 有m条直线段，从S中提取的目标直线集合记为共有n条直 线段；

（2）分别将参考直线集合和目标直线集合中所有的直线段从图像空间 映射到对偶空间，以得到参考对偶点集共有m个对偶点，以 及目标对偶点集共有n个对偶点；

（3）分别将参考对偶点集和目标对偶点集中邻近的对偶点进行融合， 以得到新的参考对偶点集和新的目标对偶点集；

（3-1）设置计数器i=1，计数器cnt=1，状态数组[St₁，St₂，…,St_m]=1；

（3-2）判断i是否小于等于m，若是则转入步骤（3-3），否则获得新 的参考对偶点集共有u个对偶点，并转入步骤（3-13）；

（3-3）判断St_i是否等于1，若是则转入步骤（3-4），否则转入步骤 （3-12）；

（3-4）设置待融合对偶点集G为空集，从参考对偶点集中取出第i个 参考对偶点其坐标是(θ_i,ρ_i)，将其加入G，并设置St_i=0；

（3-5）设置计数器j=1；

（3-6）判断j是否小于等于m，若是则转入步骤（3-7），否则转入步 骤（3-11）；

（3-7）判断j是否等于i，或者St_j是否等于0，若是则进入步骤（3-10）， 否则直接进入步骤（3-8）；

（3-8）判断|θ_j-θ_i|＜T_θ且|ρ_j-ρ_i|＜T_ρ是否成立，若成立则进入步骤（3-9）， 否则进入步骤（3-10），其中T_θ和T_ρ为预设的阈值；

（3-9）将第j个参考对偶点加入待融合对偶点集G，并设置St_j=0；

（3-10）设置j=j+1，然后返回步骤（3-6）；

（3-11）将待融合对偶点集G中的所有参考对偶点进行融合，以得到 新的参考对偶点其坐标为(θ′,ρ′)，设置cnt=cnt+1；

（3-12）设置i=i+1，然后返回步骤（3-2）；

（3-13）对于目标对偶点集中的所有目标对偶点，采用与上述步骤 （3-1）到（3-12）相同的步骤，以获得新的目标对偶点集共有v个对偶点；

（4）估计新的参考对偶点集和新的目标对偶点集之间的旋转变换参 数；

（5）估计新的参考对偶点集和新的目标对偶点集之间的平移变换参 数。

优选地，步骤（3-11）中参考对偶点的坐标(θ′,ρ′)具体是采用以下 公式：

${\theta }^{\prime }=\underset{z=1}{\overset{k}{\Sigma }}{w}_z{\theta }_z/\underset{z=1}{\overset{k}{\Sigma }}{w}_z,$${\rho }^{\prime }=\underset{z=1}{\overset{k}{\Sigma }}{w}_z{\rho }_z/\underset{z=1}{\overset{k}{\Sigma }}{w}_z$

其中，k是待融合对偶点集G中参考对偶点的数量；w_z是加权系数，其 值等于与参考对偶点对应的直线段的长度，其中z是1到k之间的任 意整数。

优选地，步骤（4）包括以下子步骤：

（4-1）设置计数器cti=1，初始化累加数组[A₁，A₂，…A₁₈₀]=0；

（4-2）判断cti是否小于等于u，若是则转入步骤（4-3），否则进入 步骤（4-9）；

（4-3）设置计数器ctj=1；

（4-4）判断ctj是否小于等于v，若是则转入步骤（4-5），否则进入 步骤（4-8）；

（4-5）判断ctj是否等于cti，若是则进入步骤（4-7），否则直接进 入步骤（4-6）；

（4-6）根据下式计算其相应的φ，并且令A_φ=A_φ+1；

$\phi =[{\theta }_{\mathrm{cti}}^{\prime R}-{\theta }_{\mathrm{ctj}}^{\prime S}+180]$

其中，[·]表示取整。

（4-7）设置ctj=ctj+1，然后返回步骤（4-4）；

（4-8）设置cti=cti+1，然后返回步骤（4-2）；

（4-9）找出[A₁，A₂，…A₁₈₀]中数值最大的元素，记为A_φ，其对应的φ_max=φ 就是旋转参数。

优选地，步骤（5）包括以下子步骤：

（5-1）设置计数器a=1，累加矩阵其 中height是目标图像S的高度，width是目标图像S的宽度，最大值max=0， 平移参数t_xmax=0，t_ymax=0；

（5-2）判断a是否小于等于u，若是则转入步骤（5-3），否则过程结 束；

（5-3）设置计数器b=1；

（5-4）判断b是否小于等于v，若是则转入步骤（5-5），否则进入步 骤（5-18）；

（5-5）设置计数器c=1；

（5-6）判断c是否小于等于u，若是则转入步骤（5-7），否则进入步 骤（5-17）；

（5-7）判断c是否等于a，若是则进入步骤（5-13），否则直接进入步 骤（5-8）；

（5-8）设置计数器d=1；

（5-9）判断d是否小于等于v，若是则转入步骤（5-10），否则进入步 骤（5-13）；

（5-10）判断d是否等于b，若是则进入步骤（5-12），否则直接进入 步骤（5-11）；

（5-11）根据下式计算其相应的(t_x,t_y)，并且令B_tx,ty=B_tx,ty+1；

$\left(\begin{array}{c}{t}_x=\left[\frac{({\rho }_b^{\prime S}-{\rho }_a^{\prime R})\sin {\theta }_c^{\prime R}-({\rho }_d^{\prime S}-{\rho }_c^{\prime R})\sin {\theta }_a^{\prime R}}{\sin ({\theta }_c^{\prime R}-{\theta }_a^{\prime R})}\right]\\ t_y=\left[\frac{({\rho }_b^{\prime S}-{\rho }_a^{\prime R})\cos {\theta }_c^{\prime R}-({\rho }_d^{\prime S}-{\rho }_c^{\prime R})\cos {\theta }_a^{\prime R}}{\sin ({\theta }_a^{\prime R}-{\theta }_c^{\prime R})}\right]\end{array}\right)---\left(4\right)$

其中，[·]表示取整。

（5-12）设置d=d+1，然后返回步骤（5-9）；

（5-13）设置c=c+1，然后返回步骤（5-6）；

（5-14）找出中数值最大的元素，记为 B_txab,tyab，并记录可能的平移参数t_xab，t_yab；

（5-15）判断max是否大于B_txab,tyab，若是则进入步骤（5-17），否则直 接进入步骤（5-16）；

（5-16）设置max=B_txab,tyab，t_xmax=t_xab，t_ymax=t_yab；

（5-17）设置b=b+1，然后返回步骤（5-4）；

（5-18）设置a=a+1，然后返回步骤（5-2）。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够 取得下列有益效果：

1、本发明通过将直线从图像空间映射到对偶空间变成点，并且在对偶 空间进行点融合，解决了断裂破碎的直线段造成的匹配效率低下和稳定性 差的问题；

2、本发明利用点集匹配的方法解决了直线匹配的问题，实现了具有旋 转、平移、光照变化和部分遮挡的图像之间的高效稳定匹配。

附图说明

图1是本发明基于点线对偶的图像匹配方法的流程图。

图2是将直线段从图像空间映射到对偶空间获得对偶点的示意图。

图3是对偶点融合方法的流程图。

图4是对偶点融合在对偶空间和图像空间效果的示意图。

图5是估计模板图像和目标图像之间的旋转变换参数方法的流程图。

图6是估计模板图像和目标图像之间的平移变换参数方法的流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的 本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可 以相互组合。

本发明提出了一种新的直线匹配方法来完成图像匹配，利用点线对偶 将图像空间中的直线段映射为对偶点，利用对偶点融合等效地将断裂破碎 的直线段重新融合为同一条直线段，利用对偶点集进行图像匹配。

本发明基于点线对偶的图像匹配方法如图1所示，其使用了两幅图像 （但本发明并不限于两幅图像），即参考图像和目标图像，对每个图像的处 理流程是相同的，本方法包括以下步骤：

（1）从参考图像和目标图像中分别提取直线，以得到参考直线集合和 目标直线集合；具体而言，在进行直线提取时，首先从图像中提取边缘， 然后对边缘进行分割和拟合，从而得到直线；例如，把参考图像记为R，把 目标图像记为S，从R中提取的参考直线集合记为共有m条 直线段，从S中提取的目标直线集合记为共有n条直线段。

（2）分别将参考直线集合和目标直线集合中所有的直线段从图像空间 映射到对偶空间，可以得到参考对偶点集共有m个对偶点， 以及目标对偶点集共有n个对偶点；具体而言，参照图2， 把图像空间中的任意一条直线记为L，在L上任取两个点(x₁,y₁)和(x₂,y₂)， 将L映射到对偶空间，根据式（1）可以求出其对偶点p的坐标(θ,ρ)：

$\left(\begin{array}{c}\theta =\arctan \frac{x_1-x_2}{y_2-y_1}\\ \rho =x_1\cos \theta +y_1\sin \theta \end{array}\right)---\left(1\right)$

（3）分别将参考对偶点集和目标对偶点集中邻近的对偶点进行融合， 以得到新的参考对偶点集和新的目标对偶点集；如图3所示，本步骤包括 以下子步骤：

（3-1）设置计数器i=1，计数器cnt=1，状态数组[St₁，St₂，…,St_m]=1； 每个参考对偶点都与状态数组中的一个元素对应；

（3-2）判断i是否小于等于m，若是则转入步骤（3-3），否则获得新 的参考对偶点集共有u个对偶点，并转入步骤（3-13）；

（3-3）判断St_i是否等于1，若是则转入步骤（3-4），否则转入步骤 （3-12）；

（3-4）设置待融合对偶点集G为空集，从参考对偶点集中取出第i个 参考对偶点其坐标是(θ_i,ρ_i)，将其加入G，并设置St_i=0；

（3-5）设置计数器j=1；

（3-6）判断j是否小于等于m，若是则转入步骤（3-7），否则转入步 骤（3-11）；

（3-7）判断j是否等于i，或者St_j是否等于0，若是则进入步骤（3-10）， 否则直接进入步骤（3-8）；

（3-8）判断|θ_j-θ_i|＜T_θ且|ρ_j-ρ_i|＜T_ρ是否成立，若成立则进入步骤（3-9）， 否则进入步骤（3-10），其中T_θ和T_ρ为预设的阈值，T_θ的取值范围是0到20 度，T_ρ的取值范围是0到50像素点；

（3-9）将第j个参考对偶点加入待融合对偶点集G，并设置St_j=0；

（3-10）设置j=j+1，然后返回步骤（3-6）；

（3-11）将待融合对偶点集G中的所有参考对偶点进行融合，以得到 新的参考对偶点其坐标为(θ′,ρ′)，设置cnt=cnt+1；具体采用以下公 式：

${\theta }^{\prime }=\underset{z=1}{\overset{k}{\Sigma }}{w}_z{\theta }_z/\underset{z=1}{\overset{k}{\Sigma }}{w}_z,$${\rho }^{\prime }=\underset{z=1}{\overset{k}{\Sigma }}{w}_z{\rho }_z/\underset{z=1}{\overset{k}{\Sigma }}{w}_z---\left(2\right)$

其中，k是待融合对偶点集G中参考对偶点的数量；w_z是加权系数，其 值等于与参考对偶点对应的直线段的长度，其中z是1到k之间的任 意整数；

（3-12）设置i=i+1，然后返回步骤（3-2）；

（3-13）对于目标对偶点集中的所有目标对偶点，采用与上述步骤 （3-1）到（3-12）相同的步骤，以获得新的目标对偶点集共有v个对偶点；

具体地，参照图4，在对偶空间中，以对偶点p₁为中心，在虚线框所示 的其邻域内有两个对偶点p₂和p₃，对偶点p₁，p₂和p₃彼此之间的距离非常 接近，因此这三个对偶点被融合为一个新的对偶点p'，相应地，在图像空 间中，与对偶点p₁，p₂和p₃对应的直线段L₁，L₂和L₃被融合为一条新的直 线段L'。

本步骤的优点在于，通过通过点融合解决了断裂破碎的直线段造成的 匹配效率低下和稳定性差的问题。

（4）估计新的参考对偶点集和新的目标对偶点集之间的旋转变换参 数；如图5所示，本步骤包括以下子步骤：

（4-1）设置计数器cti=1，初始化累加数组[A₁，A₂，…A₁₈₀]=0；

（4-2）判断cti是否小于等于u，若是则转入步骤（4-3），否则进入 步骤（4-9）；

（4-3）设置计数器ctj=1；

（4-4）判断ctj是否小于等于v，若是则转入步骤（4-5），否则进入 步骤（4-8）；

（4-5）判断ctj是否等于cti，若是则进入步骤（4-7），否则直接进 入步骤（4-6）；

（4-6）根据式（3）计算其相应的φ，并且令A_φ=A_φ+1；

$\phi =[{\theta }_{\mathrm{cti}}^{\prime R}-{\theta }_{\mathrm{ctj}}^{\prime S}+180]---\left(3\right)$

其中，[·]表示取整。

（4-7）设置ctj=ctj+1，然后返回步骤（4-4）；

（4-8）设置cti=cti+1，然后返回步骤（4-2）；

（4-9）找出[A₁，A₂，…A₁₈₀]中数值最大的元素，记为A_φ，其对应的φ_max=φ 就是旋转参数；

具体地，为了求出旋转变换参数，需要建立一个累加数组[A₁，A₂，…A₁₈₀]， 然后对新的参考对偶点集中的每一个点即cti=1,2,…,u， 和新的目标对偶点集中的每一个点即ctj=1,2,…,v， 根据式（3）计算其相应的φ并对A_φ进行更新，遍历所有点对之后，累加数 组中数值最大的元素A_φ对应的φ就是最终求出的旋转变换参数φ_max。

（5）估计新的参考对偶点集和新的目标对偶点集之间的平移变换参 数；如图6所示，本步骤包括以下子步骤：

（5-1）设置计数器a=1，累加矩阵其 中height是目标图像S的高度，width是目标图像S的宽度，最大值max=0， 平移参数t_xmax=0，t_ymax=0；

（5-2）判断a是否小于等于u，若是则转入步骤（5-3），否则过程结 束；

（5-3）设置计数器b=1；

（5-4）判断b是否小于等于v，若是则转入步骤（5-5），否则进入步 骤（5-18）；

（5-5）设置计数器c=1；

（5-6）判断c是否小于等于u，若是则转入步骤（5-7），否则进入步 骤（5-17）；

（5-7）判断c是否等于a，若是则进入步骤（5-13），否则直接进入步 骤（5-8）；

（5-8）设置计数器d=1；

（5-9）判断d是否小于等于v，若是则转入步骤（5-10），否则进入步 骤（5-13）；

（5-10）判断d是否等于b，若是则进入步骤（5-12），否则直接进入 步骤（5-11）；

（5-11）根据式（4）计算其相应的(t_x,t_y)，并且令B_tx,ty=B_tx,ty+1；

$\left(\begin{array}{c}{t}_x=\left[\frac{({\rho }_b^{\prime S}-{\rho }_a^{\prime R})\sin {\theta }_c^{\prime R}-({\rho }_d^{\prime S}-{\rho }_c^{\prime R})\sin {\theta }_a^{\prime R}}{\sin ({\theta }_c^{\prime R}-{\theta }_a^{\prime R})}\right]\\ t_y=\left[\frac{({\rho }_b^{\prime S}-{\rho }_a^{\prime R})\cos {\theta }_c^{\prime R}-({\rho }_d^{\prime S}-{\rho }_c^{\prime R})\cos {\theta }_a^{\prime R}}{\sin ({\theta }_a^{\prime R}-{\theta }_c^{\prime R})}\right]\end{array}\right)---\left(4\right)$

其中，[·]表示取整。

（5-12）设置d=d+1，然后返回步骤（5-9）；

（5-13）设置c=c+1，然后返回步骤（5-6）；

（5-14）找出中数值最大的元素，记为 B_txab,tyab，并记录可能的平移参数t_xab，t_yab；

（5-15）判断max是否大于B_txab,tyab，若是则进入步骤（5-17），否则直 接进入步骤（5-16）；

（5-16）设置max=B_txab,tyab，t_xmax=t_xab，t_ymax=t_yab；

（5-17）设置b=b+1，然后返回步骤（5-4）；

（5-18）设置a=a+1，然后返回步骤（5-2）；

具体地，为了求出平移变换参数t_x和t_y，需要建立一个累加矩阵 然后从新的参考对偶点集中任选一个点 再从新的参考对偶点集中任选一个点并假设 它们是对应的。

选定对应的对偶点对和之后，对新的参考对偶点集中除之外的 每一个点即c=1,2,…,u并且c≠a，和新的目标对偶 点集中除之外的每一个点即d=1,2,…,v并且d≠b， 根据式（4）计算其相应的t_x和t_y并对B_tx,ty进行更新，遍历所有点对之后， 累加矩阵中数值最大的元素B_txab,tyab对应的(t_xab,t_yab)就是平移变换参数的一 个可能的估计值。

对每一对可能对应的对偶点对和都进行一轮计算，都会得到一个 数值最大的元素B_txab,tyab和一个可能的平移变换参数估计值(t_xab,t_yab)。然后， 从所有的数值最大的元素中选择数值最大的那个，其对应的(t_xmax,t_ymax)就 是最终求出的平移变换参数。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。