基于三角形约束的误差控制的图像匹配传播方法

摘要

本发明公开了一种基于三角形约束的误差控制的图像匹配传播方法，包括以下步骤：(1)首先匹配用户指定数量的特征点对，开始在这些特征点形成的三角形网约束下的匹配传播过程；(2)在匹配传播过程中，计算三角形对的优先级，检测出匹配错误的三角形对，并降低三角形对的优先级；(3)不断选取优先级最高的三角形，进行在三角形约束下的匹配，并将匹配点对插入三角形中更新三角形网，最终获取用户指定数量的匹配点对。本发明具有的有益效果：1)该方法能够有效的控制图像匹配过程中出现的匹配误差，从而能减少最终结果中的匹配误差；2)该方法受图像内容差异的影响较小；3)该方法可以很好地应用在遥感图像变化检测中，匹配变化检测所用到的遥感图像。

权利要求

1.一种基于三角形约束的误差控制的图像匹配传播方法，其特征在于包括以下步骤： (1)首先匹配用户指定数量的特征点对，开始在这些特征点形成的三角形网约束下的匹配传播过程； (2)在匹配传播过程中，计算三角形对的优先级，检测出匹配错误的三角形对，并降低三角形对的优先级； (3)不断选取优先级最高的三角形，进行在三角形约束下的匹配，并将匹配点对插入三角形中更新三角形网，最终获取用户指定数量的匹配点对； 步骤(2)中所述的在匹配传播过程中，计算三角形的优先级步骤：一对三角形的优先级的计算公式为： $P=\left\{\begin{array}{cc}(1-\frac{S}{K})(H_1+H_2)(R_1+R_2+R_3)& \mathrm{ifS}\≤K\\ 0& \mathrm{else}\end{array}\right.---\left(1\right)$ 其中H1，H2为两个三角形区域的纹理复杂度，R1，R2，R3为三对顶点的匹配可靠度，S为三角形对的形状相似度，K为形状相似度需要满足的一个阈值，由用户指定，其中三角形对形状的相似度S的计算公式为： $S=\sqrt{{(a-a^{\′})}^2+{(b-b^{\′})}^2+{(c-c^{\′})}^2}---\left(2\right)$ 其中a，b，c为三角形对中一个三角形的三个内角的角度值，a′，b′，c′为另一个三角形的三个内角的角度值； 点对的匹配可靠度R的计算步骤如下： 输入：点对(x，y)； 输出：点对(x，y)的匹配可靠度R 计算公式如下： $R=\frac{\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}\left[(x_{\mathrm{ij}}-\stackrel{\‾}{X})(y_{\mathrm{ij}}-\stackrel{\‾}{Y})\right]}{\sqrt{\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}{(x_{\mathrm{ij}}-\stackrel{\‾}{X})}^2}\sqrt{\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}{(y_{\mathrm{ij}}-\stackrel{\‾}{Y})}^2}}---\left(3\right)$ 其中，m，n为以点x为中心和以点y为中心的两个大小相同窗口的宽和高，以像素为单位；xij为以点x为中心的窗口中一个像素的亮度值，yij为以点y为中心的窗口中一个像素的亮度值，X是以点x为中心的窗口中所有像素亮度值的平均值，Y是以点y为中心的窗口中所有像素亮度值的平均值； 三角形图像区域的纹理复杂度H的计算公式如下： $H=-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{p}_i\log p_i---\left(4\right)$ 其中n为三角形图像区域中像素点的个数，pi是某个像素点的亮度值出现的概率； 步骤(2)中所述的检测出匹配错误的三角形对并降低该三角形对的优先级步骤：如果一对三角形满足如下6个公式中的任何一个，则这对三角形为匹配错误的三角形： (a-b)(a′-b′)＜0 5 (a-c)(a′-c′)＜0 6 (b-c)(b′-c′)＜0 7 (a+b-c)(a′+b′-c′)＜0 8 (a+c-b)(a′+c′-b′)＜0 9 (b+c-a)(b′+c′-a′)＜0 10 其中a，b，c，a′，b′，c′分别为两个三角形的内角的角度值；如果三角形对被检测为坏三角形，就要将其优先级P减去极大量maxRank，极大量maxRank是大于所有可能优先级的值。 步骤(3)中所述的不断选取优先级最高的三角形，进行在该三角形约束下的匹配步骤： 输入：已匹配的三角形对T1，T2，T1内的特征点集P1＝{pi|i＝1，...，N}，T1相邻三角形内的特征点集P1a＝{pi|i＝1，...，N}，T2内的特征点集P2＝{pi|i＝1，...，N}，T2相邻三角形内的特征点集P2a＝{pi|i＝1，...，N}； 输出：新的匹配点对或无匹配点对输出； 步骤1：对P1中的每个点m′，在P2和P2a中寻找匹配度最大的点，得到匹配点对(m′，n′)； 步骤2：对P2中的每个点m″，在P1a中寻找匹配度最大的点，得到匹配点对(m″，n″)，将(m′，n′)和(m″，n″)中匹配度较大的一对点作为最终的匹配点对(m，n)； 步骤3：如果匹配点对(m，n)中的一个点属于P1a或P2a，就不输出匹配点对并将三角形对(T1，T2)设为坏三角形，将坏三角形的优先级减去极大量maxRank；否则，输出(m，n)，并更新三角形网。

说明书

基于三角形约束的误差控制的图像匹配传播方法

技术领域

本发明涉及计算机数字图像处理领域，尤其涉及一种基于三角形约束的误 差控制的图像匹配传播方法。 背景技术
图像匹配技术是一种应用非常广泛的技术。比如图像融合，图像拼接，遥 感图像变化检测，三维重建等都需要用到图像匹配技术。近几年有很多基于图 像特征点的方法被提出用来提高匹配的可靠度。基于图像特征点的图像匹配方 法首先在待匹配的两幅图像中检测特征点，再通过一定的策略找到两幅图像的
特征点的对应关系，即匹配代表同一图像内容的特征点对。视觉接口 2002年会 议论文集中（尸race^Z/"gs o/Ww'o" /Ww/ace, 2002: 178-185)公布了一种稠密匹 配方法，这种方法首先提取图像的边缘，并将图像分为边缘区域和非边缘区域。 边缘区域的点首先匹配，非边缘区域的点在已匹配点的约束下进行匹配。第5 届亚洲计算机视觉会议论文集中[2] (Proceedings of the 5th Asian Conference on Computer Vision, 2002:137〜144)公布了一种半稠密匹配方法，这种方法通过稀疏 匹配方法得到一些可靠匹配的点，然后在以每个匹配点为中心的窗口的约束下 匹配更多的点。《摄影测绘工程和遥感》杂志中(Photogrammetric Engineering & Remote Sensing, 2005， 71(9):1063~1069)公布了一种以三角形为约束的匹配方 法，这种方法首先匹配少量种子点，形成一个初始的三角形网。在每对三角形 中，寻找最匹配的点对插入三角形，并细化三角形网，直到足够多的特征点对 得到匹配。这些方法都首先匹配一些容易匹配的点对，然后在这些点对的约束 下匹配更多的点对。图像匹配传播策略，即如何更好地利用已有点对提供的信 息来匹配更多的点对，对这些方法的最终结果起到很大的作用。
《摄影测绘和遥感ISPRS杂志》中（ISPRS Journal of Photogrammetry and Remote Sensing, 2007, 62(4): 295〜308)公布了三种基于三角形约束的匹配传播策 略，分别是随机匹配传播策略，邻近优先匹配传播策略和自适应匹配传播策略。 这三种策略的比较结果显示根据三角形区域纹理来决定三角形匹配顺序的自适 应匹配策略的效果最好。然而以上提到的图像匹配方法采用的匹配传播策略都 忽略了匹配开始时和匹配传播过程中出现的误匹配，使图像匹配结果受初始误 差以及图像内容差异的影响比较大。 发明内容本发明的目的是克服上述现有方法受初始误差以及图像内容差异影响大的 缺点，提供一种基于三角形约束的误差控制的图像匹配传播方法。基于三角形约束的误差控制的图像匹配传播方法包括以下步骤：(1) 首先匹配用户指定数量的特征点对，开始在这些特征点形成的三角形网 约束下的匹配传播过程；(2) 在匹配传播过程中，计算三角形对的优先级，检测出匹配错误的三角形 对，并降低三角形对的优先级；(3) 不断选取优先级最高的三角形，进行在三角形约束下的匹配，并将匹配 点对插入三角形中更新三角形网，最终获取用户指定数量的匹配点对。步骤（2)中所述的在匹配传播过程中，计算三角形的优先级步骤： 一对三 角形的优先级的计算公式为：尸=(1-|:)(//,2X& +《+《）if S S K 0 else其中Hl5 H2为两个三角形区域的纹理复杂度，Ri， R2, R3为三对顶点的匹配可靠 度，S为三角形对的形状相似度，K为形状相似度需要满足的一个阈值，由用户 指定，其中三角形对形状的相似度S的计算公式为：S =如-fl')2 + (6 - "2 + (c - c')2其中a, b, c为三角形对中一个三角形的三个内角的角度值，a'， b', c'为另一个三角 形的三个内角的角度值；点对的匹配可靠度R的计算步骤如下：输入：点对(x，y);输出：点对(x,y)的匹配可靠度R计算公式如下：'•=1 /=1R =111 i iu w其中，m, n为以点x为中心和以点y为中心的两个大小相同窗口的宽和高， 以像素为单位；Xij为以点x为中心的窗口中一个像素的亮度值，yg为以点y为 中心的窗口中一个像素的亮度值，f是以点x为中心的窗口中所有像素亮度值 的平均值，F是以点y为中心的窗口中所有像素亮度值的平均值。三角形图像区域的纹理复杂度H的计算公式如下：孖=-p,iog/?,其中n为三角形图像区域中像素点的个数，pi个是某个像素点的亮度值出现 的概率。步骤(2)中所述的检测出匹配错误的三角形对并降低该三角形对的优先级步 骤：首先通过判断三角形对的三个内角大小关系是否对应来检测，如果一对三 角形满足如下6个公式中的任何一个，则这对三角形为匹配错误的三角形：(")("'一的<0O — c)(a'—c*)<0(6-，-0<0(a + 6-c)(fl'+6'-0〈0(a + c — 6)(fl'+c'—6')<0(6 + c-cr妙'+c'-a') <0其中a, b， c， a'， b'， c'分别为两个三角形的内角的角度值；如果三角形对被检测为 坏三角形，就要将其优先级P减去极大量maxRank，极大量是大于所有可能优 先级的值。步骤(3)中所述的不断选取优先级最高的三角形，进行在该三角形约束下的匹配步骤：输入：已匹配的三角形对1\,丁2,1\内的特征点集&={#=1，...,>0， Tt相邻 三角形内的特征点集Pla={Pi|i=l,...,N}， T2内的特征点集P2={Pi|i=l,...，N}， T2 相邻三角形内的特征点集P2^Pi^l，.，.,N〉；输出：新的匹配点对或无匹配点对输出；步骤l:对&中的每个点m'，在P2和P^中寻找匹配度最大的点，得到匹 配点对(m', n');步骤2:对P2中的每个点m"，在P^中寻找匹配度最大的点，得到匹配点对(m", n")，将(m', n')和(m", n")中匹配度较大的一对点作为最终的匹配点对(m， n);步骤3:如果匹配点对(m, n)中的一个点属于P^或P2a，就不输出匹配点对 并将三角形对(T!，T2)设为坏三角形，将坏三角形的优先级减去maxRank;否则， 输出(m,n),并更新三角形网。本发明与现有技术相比具有的有益效果：1) 该方法能够有效的控制图像匹配过程中出现的匹配误差，从而能减少最终 结果中的匹配误差；2) 该方法受图像内容差异的影响较小。3) 该方法可以很好得应用在遥感图像变化检测中，匹配变化检测所用到的遥 感图像。附图说明图l(a)是拍摄视角不同造成的不相似的一对三角形中的一个三角形；图l(b)是拍摄视角不同造成的不相似的一对三角形中的另一个三角形；图2是本发明的基于三角形约束的误差控制的图像匹配传播方法工作流程；图3是匹配点对在当前三角形时三角形网的更新方式示意图；图4是匹配点对中有一个点在相邻三角形时三角形网的更新方式示意图；图5(a)是本发明最终产生的三角形网在一幅图中的分布； 图5(b)是本发明最终产生的三角形网在另一幅图中的分布。具体实施方式基于三角形约束的误差控制的图像匹配传播方法包括以下步骤-(1) 首先匹配用户指定数量的特征点对，开始在这些特征点形成的三角形网约束下的匹配传播过程；(2) 在匹配传播过程中，计算三角形对的优先级，检测出匹配错误的三角形 对，并降低三角形对的优先级；(3) 不断选取优先级最高的三角形，进行在三角形约束下的匹配，并将匹配 点对插入三角形中更新三角形网，最终获取用户指定数量的匹配点对。步骤(2)中所述的在匹配传播过程中，计算三角形的优先级步骤： 一对三角形的优先级的计算公式为：P = |(1-f讽叫)(尺+尺ifS - K 0 else8其中Hl5 H2为两个三角形区域的纹理复杂度，Rh R2, R3为三对顶点的匹配可靠 度，S为三角形对的形状相似度，K为形状相似度需要满足的一个阈值，由用户 指定，其中三角形对形状的相似度S的计算公式为：其中a, b, c为三角形对中一个三角形的三个内角的角度值，a', b'， c'为另一个 三角形的三个内角的角度值；点对的匹配可靠度R的计算步骤如下：输入：点对(x,y);输出：点对(x,y)的匹配可靠度R计算公式如下：其中，m, n为以点x为中心和以点y为中心的两个大小相同窗口的宽和高， 以像素为单位；xy为以点x为中心的窗口中一个像素的亮度值，yg为以点y为 中心的窗口中一个像素的亮度值，f是以点x为中心的窗口中所有像素亮度值 的平均值，F是以点y为中心的窗口中所有像素亮度值的平均值。三角形图像区域的纹理复杂度H的计算公式如下：其中n为三角形图像区域中像素点的个数，pi个是某个像素点的亮度值出现 的概率。当一对三角形的一个或多个顶点存在匹配误差或位于存在内容差异的区 域，该三角形对形状相似性就比较低。附图1给出了一种由于拍摄视角不同造 成的己匹配三角形对形状的不相似。三角形形状的不相似会增加在其约束下的 匹配出现误差的可能性，所以将三角形对形状的相似性也作为三角形优先级的2^ = -H A log A计算因素，可以减少匹配误差在匹配过程中的扩散。步骤（2)中所述的检测出匹配错误的三角形对并降低该三角形对的优先级步骤：首先通过判断三角形对的三个内角大小关系是否对应来检测，如果一对 三角形满足如下6个公式中的任何一个，则这对三角形为匹配错误的三角形：0-c)(a'—c*)<0(6-c)(6'-c';xo(a + c —6)(a'+c'—"<0 (6 + c-a)(6'+c'—a') <0其中a, b, c， a', b'， c'分别为两个三角形的内角的角度值；如果三角形对被检测为 坏三角形，就要将其优先级P减去极大量maxRank，极大量是大于所有可能优 先级的值。这样一来，所有的坏三角形的优先级都会低于没有匹配错误的三角 形的优先级，使得存在匹配误差的三角形只在最后作为匹配的约束。步骤（3)中所述的不断选取优先级最高的三角形，进行在该三角形约束下 的匹配步骤：输入：已匹配的三角形对Ti，T2,Td内的特征点集P产(pili-l,…,N)， Ti相邻 三角形内的特征点集Pla={Pi|i=l，...,N}， T2内的特征点集P2={Pi|i=l，...，N}， T2 相邻三角形内的特征点集？23={#=1，...^};输出：新的匹配点对或无匹配点对输出；步骤l:对Pi中的每个点m'，在P2和P2a中寻找匹配度最大的点，得到匹 配点对(m', n');步骤2:对P2中的每个点m"，在P^中寻找匹配度最大的点，得到匹配点 对(m"， n")，将(m'， n')和(m"， n")中匹配度较大的一对点作为最终的匹配点对(m， n);步骤3:如果匹配点对(m， n)中的一个点属于P^或P2a，就不输出匹配点对 并将三角形对(T!,T2)设为坏三角形，将坏三角形的优先级减去maxRank;否则， 输出(m，n)，并更新三角形网。每次三角形约束下的匹配会产生两种结果，第一种结果是新找到的匹配点对中有一个点在当前三角形的相邻三角形内，则当前三角形对为坏三角形，新 找到的匹配点对被舍弃。第二种结果是新找到的匹配点对都在当前三角形内， 则保留找到的匹配点对，并对三角形网络进行更新。附图2给出了本发明的基于三角形约束的误差控制的图像匹配传播方法工作流程图。该方法的具体实施流程如下：1. 首先匹配用户指定数量的特征点对，形成初始的三角形网络，并计算三 角形网中每对三角形的优先级；2. 选择优先级最高且其中存在特征点的三角形，如果没有这样的三角形， 表示匹配结束；3. 在选取的三角形的约束下进行匹配，如果新找到的匹配点对中有一个点 在当前三角形的相邻三角形内，则当前三角形对被认为是坏三角形，并按照坏 三角形的方式来计算其优先级，同时新找到的匹配点对也被舍弃。如果新找到 的匹配点对都在当前三角形内，则保留找到的匹配点对，并进入第4步；4. 更新三角形网的几何结构，对于更新过程中出现的新三角形，按照权利 要求中坏三角形的检测方法来判断其是否是坏三角形，然后，按照三角形的类 型来计算三角形的优先级，继续第2步。实施例下面结合本发明的方法详细说明一对图像的具体匹配步骤，如下：(1) 匹配用户指定数量的特征点对，形成初始的三角形网，并按照权利要求 中提到的方法计算三角形网中每个三角形的优先级。在本例中初始匹配了 23对 点。(2) 选取优先级最高的三角形，进行三角形约束下的匹配。如果新找到的匹 配点对都在当前三角形内，则保留该匹配点对，并更新三角形网。如附图3所 示。如果新找到的匹配点对中有一个点在当前三角形的相邻三角形内，则舍弃 该匹配点对，直接继续下个三角形约束下的匹配，如附图4所示。(3) 不断重复步骤(2)，直到得到用户指定数量的特征点对。附图5给出了最 终得到的部分三角形网在两幅图像中分布情况，每个三角形的顶点就是匹配点 对。其中用白色矩形表示的是初始三角形网中存在的四个 误匹配的点对的邻 域。从图中可以看出，错误点对周围只产生了少量的三角形，而且邻域内除了 错误点对本身外，没有其他匹配错误的点对。说明了本发明提供的方法很好地 控制了匹配误差在匹配传播过程中的扩散。