第２６卷第５期 信号处理 ＶｏＩＪ ２６． Ｎｏ．５ ２０１０年５月 ＳＩＧＮＡＬ ＰＲＯＣＥＳＳＩＮＧ Ｍａｖ．２０１０ 直线特征立体匹配中的不确定性问题 王继阳 文贡坚 李德仁 （１．国防科技大学电子科学与工程学院ＡＴＲ国防科技重点实验室，长沙４１００７３； ２．武汉大学测绘遥感信息工程国家重点实验室，武汉４３００７２） 摘要：直线特征断裂和提取不完整、过提取是直线特征提取结果中常见的不确定性问题，是影响直线特征立体匹配 结果的关键因素。提出一种以边缘检测结果为依据定量描述这些不确定性的方法，依据已提取直线特征延长线附近边缘点 分布，定义直线特征端点定位的概率密度函数，以单条直线特征的不确定性描述为基础，计算断裂直线特征编组假设的可 靠性测度，进而计算用于衡量立体图像中任意两条直线特征匹配假设可靠性的核线约束测度和灰度相似性测度。应用真实 遥感立体图像，对比已有方法，结果证明了本文方法能够有效提高直线特征匹配结果对于两类直线特征提取不确定性问题 的抑制能力。 关键词：不确定性；直线特征匹配；核线约束；直线特征提取；灰度相似性；断裂直线特征编组 中图分类号：ＴＰ３９１ 文献标识码：Ａ 文章编号：１００３—０５３０（２０１０）０５—０６４１—０７ Ｕｎｃｅｒｔａｉｎｔｙ ｉｎ ｍａｔｃｈｉｎｇ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔｓ ＷＡＮＧ ｊｉ—ｙａｎｇ ＷＥＮ Ｇｏｎｇ－ｊｉａｎ ＬＩ Ｄｅ－ｒｅｎ （１．ＡＴＲ Ｌａｂ ｉｎ Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ ４１００７３； ２．Ｓｔａｔｅ Ｋｅｙ Ｌａｂ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ ｉｎ Ｓｕｒｖｅｙｉｎｇ，Ｍａｐｐｉｎｇ ａｎｄ Ｒｅｍｏｔｅ Ｓｅｎｓｉｎｇ，Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ ４３００７２） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｆｒａｇｍｅｎｔａｔｉｏｎ，ｉｎｃｏｍｐｌｅｔｅ ｅｘｔｒａｃｔｉｏｎ ａｎｄ ｅｘｃｅｓｓｉｖｅ ｅｘｔｒａｃｔｉｏｎ ａｒｅ ｔｈｒｅｅ ｋｉｎｄｓ ｏｆ ｃｏｍｍｏｎ ｕｎｃｅ￣ａｉｎｔｙ ｐｒｏｂｌｅｍｓ ｉｎ ｅｘｔｒａｃｔｉｎｇ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔｓ，ｗｈｉｃｈ ａｒｅ ｃｒｉｔｉｃａｌ ｔｏ ｍａｔｃｈｉｎｇ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔｓ ａｃｒｏｓｓ ｄｉｆｆｅｒｅｎｔ ｉｍａｇｅｓ．Ｂａｓｅｄ ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｅｘｔｒａｃｔｉｎｇ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔｓ，ａ ｍｅｔｈｏｄ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｄｅｓｃｒｉｂｅ ｑｕａｎｔｉｔａｔｉｖｅｌｙ ｔｈｅ ａｂｏｖｅ ｔｗｏ ｐｒｏｂｌｅｍｓ ｂｙ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｅｄｇｅ ｄｅｔｅｃｔｉｏｎ．Ｗｉｔｈ ｔｈｅ ｐｏｓｉｔｉｏｎｓ ａｎｄ ｔｈｅ ｇｒａｄｉｅｎｔｓ ｉｎ ｇｒａｙ ｏｆ ｅｄｇｅ ｐｏｉｎｔｓ ｃｌｏｓｅ ｔｏ ｔｈｅ ｅｘｔｅｎｓｉｏｎ ｏｆ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔｓ，ｔｈｅ ｐｒｏｂａｂｉｌｉｔｙ ｉｎ ｐｃ— ｓｉｔｉｏｎ ｏｆ ｅｎｄｐｏｉｎｔｓ ｏｆ ｅａｃｈ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔ ｉｓ ｄｅｆｉｎｅｄ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ａｂｏｖｅ ｐｒｏｂａｂｉｌｉｔｙ ｅｘｐｒｅｓｓｉｏｎ，ｔｈｅ ｃｒｅｄｉｂｉｌｉｔｙ ｏｆ ｇｒｏｕｐｉｎｇ ｄｉｆ－ ｆｅｒｅｎｔ ｌｉｎｅｓ ｊＳ ｍｅａｓｕｒｅｄ ａｎｄ ｆｕｒｔｈｅｒｍｏｒｅ ｔｈｅ ｍｅａｓｕｒｅ ｔｈａｔ ａｎｙ ｔｗｏ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔｓ ｅｘｔｒａｃｔｅｄ ｆｒｏｍ ｄｉｆｅｒｅｎｔ ｉｍａｇｅｓ ｓａｔｉｓｆｙ ｔｈｅ ｅｐｉｐｏｌａｒ ｃｏｎｓｔｒａｉｎｔ ａｎｄ ｐｈｏｔｏｍｅｔｒｉｃ ｓｉｍｉｌａｒｉｔｙ ｃｏｎｓｔｒａｉｎｔ ｉｓ ｃｏｍｐｕｔｅｄ，ｗｉｔｈ ｗｈｉｃｈ ｔｈｅ ｓｔｒｅｎｇｔｈ ｏｆ ｅａｃｈ ｐｏｔｅｎｔｉａｌ ｓｔｒａｉｇｈｔ ｌｉｎｅ ｓｅｇｍｅｎｔ ｍａｔｃｈｉｎｇ ｐａｉｒ ｉｓ ｇｉｖｅｎ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ｒｅａｌ ｓｔｅｒｅｏ ｒｅｍｏｔｅ ｓｅｎｓｉｎｇ ｉｍａｇｅｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｍｅｔｈｏｄ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ ｉｓ ｃｏｍｐｅｔｉｔｉｖｅ． Ｋｅｙ ｗｏｒｄｓ： ｕｎｃｅｒｔａｉｎｔｙ；ｌｉｎｅ ｍａｔｃｈｉｎｇ；ｅｐｉｐｏｌａｒ ｃｏｎｓｔｒａｉｎｔ；ｌｉｎｅ ｅｘｔｒａｃｔｉｎｇ；ｐｈｏｔｏｍｅｔｒｉｃ ｓｉｍｉｌａｒｉｔｙ；ｆｒａｇｍｅｎｔｅｄ ｌｉｎｅｓ ｇｒｏｕｐｉｎｇ １ 引言 准、目标三维重建以及目标姿态估计等方法的重要实 现手段㈨ ㈣… 。 直线特征匹配的目的是建立两个不同直线特征集 然而，由于图像对比度和图像分辨率较低造成图 中各元素间的对应关系，是模式识别、计算机视觉以及 像模糊或因为图像噪声以及提取算法自身的问题，提 摄影测量等领域长期研究的一个基本问题。在人造目 取直线特征的属性存在着不确定性，包括直线特征提 标场景中，直线成为描述目标结构的主要几何特征，相 取不完整、直线特征断裂、直线特征方向偏离、过提取 对于点特征，直线特征的提取结果可靠性更高，属性信 或虚假提取等。它们严重破坏了不同图像中同名直线 息更丰富，因此，基于直线特征匹配不同视角图像或匹 特征的属性一致性，成为直线特征匹配方法实现的主 配图像与模型的方法成为目标检测、目标识别、图像配 要困难之一 收稿日期：２００９年８月６日；修回日期：２００９年ｌＯ月１６日 基金项目：国家自然科学基金（６０８７２１５３），国家高技术研究发展计划（２００６ＡＡ１２Ｚ１４０），国防科技大学校预研项目（基于 高速相机的武器装备位姿参数测量技术） ６４２ 信号处理 第２６卷 描述直线特征不确定性的思路主要有两个：一是 基于点定位的不确定性定义，以两个端点的不确定性 生成新的可能直线特征。 ２．１ 单条直线特征端点定位的不确定性描述 计算直线特征各种属性的不确定性 “ ；二是基于 如图１所示，直线特征ｚ的端点为（ ，Ｙ，）和（ ：， Ｙ：），它所在直线为ｚ；假定它的真实端点为（ 。， ） 和（ ， ），（ 。，Ｙ ）到（ ， ）的有向距离是ｓｔ，（ ：， Ｙ：）到（ ， ）的有向距离是Ｓ：。 直线拟合过程，直接定义直线特征属性的不确定 性 儿ｍ一．“ 。依据对直线特征不确定性的描述，现有直 线特征匹配方法采用３种不同的方式处理感兴趣的不 确定性问题：（１）不建立任何模型，混合各种因素造成 的不同图像中同名直线特征之间的差异，根据经验或 利用学习机制指定特征的各种属性的可接受误差范 围，较早提出的基于直线特征的匹配方法大都采用这 种机制；（２）不建立具体的模型，以方差的形式表示直 线特征各种属性的不确定性 ，利用Ｂａｙｅｓ网络传导这 种不确定性，计算组合特征、匹配结果或参数估计的不 确定性，在很多基于模型的目标识别或图像配准、姿态 参数估计等问题求解中经常采用；（３）建立统计模 型 或模糊模型 ］，如高斯模型、指数衰减模型 等， 将对单个直线特征属性的不确定性模型进行传播。其 中，前两种方式是以误差门限的形式约束这种特征不 确定性范围的大小，这实际上是隐含的假定了各种特 征不确定性服从均匀分布 ，它们的区别体现在门限 的设定方法不同，第三种方式考虑了直线特征属性的 特点，对不确定性的表达更确切。 大量分析直线特征不确定性的方法以及我们的实 验结果表明，直线特征的倾角误差以及位置偏离对于 直线特征匹配问题的影响相对较小，而影响较大的是 直线特征断裂、提取不完整以及过提取问题，这表现在 直线特征端点定位的不确定性上… 引 。本文将针 对这三类端点定位的不确定性问题展开研究，建立描 述这三类不确定性的概率模型，据此定义更加准确和 可靠的直线特征匹配测度，提高直线特征匹配的正确 率和完整性。 ２直线特征端点定位的不确定性描述 描述直线特征端点定位不确定性的目的在于寻找 直线特征端点的分布规律，在统计意义上，就是计算端 点定位的概率密度函数。造成直线特征端点定位不确 定性的因素是复杂的，从而概率密度函数的建立成为 一个难题。已有方法大多为其指定一般性的模型，如 之前提到的均匀分布、高斯分布或指数衰减分布等，而 模型参数则基于经验判断或学习机制来指定。本文从 直线特征提取的边缘点拟合机制出发，提出了依据边 缘检测结果中沿直线特征延长线排列的未被拟合到任 何一个直线特征中的边缘点建立端点定位的概率密度 函数的方法。首先，以概率密度函数的形式描述单个 直线特征端点定位的不确定性，其次，计算邻近的共线 直线特征形成断裂直线特征编组假设的可靠性测度， 图１ 直线特征端点不确定性不恿图 任意直线特征的两个端点沿直线分布的不确定性 是相互独立的，而且对它们的定位不确定性的描述方 法是一致的。定义直线特征ｚ的端点（ ，Ｙｉ）（ｉ＝１，２） 到对应的真实端点（ ， ）的有向距离服从如下形式 的概率密度函数 ・ｅｘｐ（ｏ－（ｓ ）／（ ・０－ｐ（ ））） ∈（０， ） （Ｓ ）＝ ・ｌ， ・ｅｘｐ（一ｌ，。・（ｓ — ｓ Ｅ［ ，＋∞） ｒＡ・ ６・ｅｘｐ（ ６・Ｓ ） ；∈（一∞，０］ （１） 公式（１）中各符号的简明含义如表１所示。 表１公式（１）中各符号的简明含义 符号 含义 仉，仉 预定义的ｓ。位于区间［ ，＋。。）和（一 ，０］的概率 ｄ，Ｉｔｂ 预定义的指数型概率密度函数的衰减因子 作为直线特征真实端点估计证据的边缘点覆盖范围长度 （Ｓ ） Ｓ 的函数，由作为证据的边缘点计算得到 （Ｓ ） （ ）在 处的导数 由公式（１）， （Ｓ ）被分为３个区间，并且 在每一 个定义区间的概率是确定的，即１一仉一 、 和仇。 （Ｓ ）是 的函数，由端点（ ，Ｙ ）外延长线附近 的一组有效边缘点计算得到。端点（ ，Ｙ ）被视为第０ 个有效边缘点，如果其它任意一个边缘点满足以下几 个约束条件，则它被认为是有效的：①未被拟合到任何 一个直线特征；②它所在位置计算的灰度梯度幅值Ａ 大于设定门限 ，梯度相位 满足ｌ Ｃ０８（ 一０）Ｉ＞ Ｔ，０是拟合得到ｚ的边缘点的梯度相位平均值， 是 预先设定的一个门限；③它到ｚ的距离ｄ小于设定门 第５期 王继阳等：直线特征立体匹配中的不确定性问题 ６４３ 限 ；④将它投影到２上，投影点与靠近（ ，Ｙ ）一侧 的相邻有效边缘点在ｚ上投影的距离ｔ小于一个设定 数的近似将失去意义。由以上定义可以看出，公式（１） 中 （Ｓ ）在区间Ｓ ∈（０， ）的定义式中指数项表达的 含义是 （Ｓ ）在离开点（ ，Ｙ ）距离为Ｓ 的点的前后两 的门限 。将符合所有这些条件的边缘点投影到ｚ 上，依据投影点到端点（ ，Ｙ ）的距离排序，得到有效边 个不同区间上的平均密度之比，显然，这个比值越大， 真实端点位于该点的邻近区间的可能性就越大。 公式（１）中叼 对于每个端点而言是一个常数，满足 缘点集｛Ｐ ｌ ｋ＝１，２，…，Ⅳ｝，任意一个边缘点Ｐ 描述为 （Ａ ，Ｏｔ ，ｄ ，ｔ ）。 公式（１）中 为最后一个边缘点Ｐ 在Ｚ上的投 ～ ｆ ７／ｉｅｘｐ（ｔｙ（Ｓｉ）／（ ・Ｏ．Ｉ（ ）））ｄｓ ＝ｌ一叼。一叼 （４） 从而， 影到（ ，Ｙ ）的距离。 （Ｓ ）描述（ ，．ｙ ）到（ ， ）的 距离小于等于Ｓ 的可能性，它的计算如下式 ７７ ＝（１一叩。一＇７ ） Ｔｓｅｘｐ（ （ ） （ ）））幽 （５） ＝ｋ ＝ｌ Ａ ＋ ・ｌ ＣＯＳ（ ＋。一 ） ｄ ＋ｉ。ｔ ＋ 当Ｓ ∈［ ，＋。。） （Ｓ ）服从参数为 的指数衰 减分布， 是一个正数，决定 （Ｓ ）随Ｓ，增加时的衰减 速度。 其中，Ｗ表示离开（ ，Ｙ ）的距离小于等于Ｓ 范围内的 除第０个有效边缘点以外的有效边缘点数目。由于此 时Ｓ，∈（０，Ｔｓ），因此一定有ｗ＜Ｎ。 （Ｓ ）表示 （Ｓ ）在Ｓ 处的导数，用 （Ｓ ）在［Ｓ ， Ｓ ＋△ ］范围内的密度来近似 ，（ｓｉ）： Ｓ 对于直线特征匹配问题，通常用到的是坐标形式 的表达式。根据概率理论，以ｇ （７２）为例，由于 是 Ｓ，的单调函数，可得 （３） ｇ２（ ）＝ ｛ （ ））‘ 假定 ： ，即得到 （６） 其中， 是一个正的常数，取值不宜过大，否则对于导 ～ ｆ∈Ｊ ＇—（ — ＿＋ ）・Ｙ—：一一Ｊ ・Ｔｓ Ｙ。］／１ ∈ 一］（７ …ｐ ｃ ［一 ， ） 利用与上面类似的方法，可以计算ｇ （ ）。 （ 斗一 （ ・ 同理，可得到 的后验概率密度函数ｇ （ ），对 定义， （ ）被分成两个区间，与Ｓｈｅｎ的方法 相似。 （１－￣７＝ ．可以看出，Ｓｈｅｎ的方法 与本文方法的本质差别 在于，Ｓｈｅｎ的方法对于所有直线特征定义的一致性，而 本文方法则是对于不同直线特征的定义是有差别的。 ２．２断裂直线特征编组问题 如图２所示，两条实线表示直线特征ｚ 和ｆ，，端点 分别为（ ，，Ｙ。）和（ ，Ｙ ）、（ ，Ｙ ）和（ ，Ｙ ），它们到 各自对应的真实端点（ ， ）、（ ， ）、（￣３， ）和 （五， ）的有向距离分别为Ｓ。、Ｓ 、Ｓ 和 ，端点概率密 度函数分别为 （Ｓ ）和 （Ｓ ）、 （Ｓ ）和 （Ｓ ），假定 （ ：，Ｙ ）和（ ， ）是相互邻近的两个端点，它们之问的 ｘｐ（ 信号处理 第２６卷 距离为ｒ。如果ｚ。和ｚ 共线，由它们形成编组假设的可 靠性测度定义为 ＝ （ Ｙ～ｉ：）和（ ｌ２， ，：）。（互，。，Ｙ～ｉ．。）和（ ，．。）满足 核线约束的测度按以下方式计算： 令ｚ＝ 一 Ｓ２＋Ｓ３十』０ ＪＪ ， Ｐ（ ．，）ｄ ｄ ，（９） ｒ ． Ｉ，计算ｚ的分布函数Ｏ（ｚ）为 Ｉ≤ｚ ， ｓ２≤ ２＋ ３＋ 其中， 是一个常数，表示断裂直线特征编组假设允许 跨越没有边缘点证据支持的最大距离， 和 分别表 示端点（ ：，Ｙ：）和（％，Ｙ，）外搜索到的最远有效边缘点 在各自直线上投影到这两个端点的距离，Ｐ（Ｓ：， ，）表示 Ｑ（ｚ）＝ ＪＪ Ｐ（Ｙ～ ， ．。）ｄ “ｄ ， （１１） ，－一 其中，Ｐ（ 于 ， ，Ｙ～Ｊ， ）是 和 ，。的联合概率密度函数，由 ， ， ， 和 。。相互独立，Ｐ（ ， ）＝ｇ （ ，。）・ｇ：． 和 ，的联合概率密度，由于Ｓ 和Ｓ 相互独立，因而， Ｐ（Ｓ ，Ｓ３）＝ｆ２（Ｓ２）・ｆ３（Ｓ，） （１０） 如果 大于预设的一个门限，则认为这一编组假 设是可能成立的，一个新的直线特征将由组成它的ｚ 和ｚ 拟合而成，重新计算它的两个端点定位的概率密 度函数，新生成的直线特征将与其它直线特征建立可 能的匹配对假设。 图２断裂直线特征编组示意图 ３直线特征的可匹配性测度 本文将计算两类可匹配性测度，即核线约束和直 线邻近区域图像灰度相似性。为了叙述方便，对将要 使用的符号做如下规定：在一对立体图像中，左图像中 提取的任意一条直线特征ｌ 的端点为（ ¨，Ｙ１． ）和 （ 啦，Ｙｉ：），对应的真实端点分别为（ ．，。， ¨）和（ ∞， Ｙ ｉ． ）， ． 和 ，：的概率密度函数分别为ｇ （ ，。）和 ｇ啦（Ｙ １．：）；右图像中提取的任意一条直线特征ｚ：的端 点为（ ，，）和（ ；， ），对应的真实端点分别为 （ ｊ， ）和（ ：， ，：），Ｙ～ｉ， 和 ， 的概率密度函数 记为 ，（ ：。 ）和 （Ｙ～ｉ，：）。 ３．１核线约束的不确定性度量 立体匹配中的核线约束通常是针对同名点而言 的，即左（右）图像中一个点Ａ在右（左）图像中的同名 点Ｂ一定在由Ａ在右（左）图像中确定的核线上。对 于直线特征而言，如果它们是同名直线特征，在不考虑 遮挡的情况下，它们的真实端点应该是两对同名点，本 文据此计算两个直线特征满足核线约束的测度。 为了降低表达式的复杂性，本文假定立体图像是经 过核线校正的，即它们的同名核线沿各自坐标系的Ｙ方 向平行排列，且同名点的Ｙ坐标相等。对于直线特征ｚ； 和ｚ ，设待匹配的端点为（霉，。， ，。）和（ ，，， ， ）以及 （Ｙ～ｊ．１）； 对ｑ（ｚ）求导，得到Ｚ的概率密度函数为Ｐ（Ｚ）＝ ｄＱ（ｚ）／ｄｚ，若（ ¨，Ｙ～ｉ．。）和（ 。，Ｙ～ｊ， ）满足核线约束， 显然要求Ｙ～ｉ＝ ，． 对应于ｚ＝０，因而，这两个点满足 核线约束的测度定义为 Ｐ１＝Ｐ（Ｚ）Ｉ ・△ｚ （１２） 类似的，计算（ 啦， ． ）和（ ， ）满足核线约 束的测度 ，进而，定义ｚ 和ｚ；满足核线约束的测度为 ＝ ： （１３） ３．２直线邻近区域灰度相似性的不确定性描述 直线邻近区域灰度相似性通常采用对应区域的灰 度互相关来衡量，选取的对应区域越大，互相关的计算 结果就越能反映两个直线特征可匹配性，但选取的区 域过大，可能使两个区域不再对应一致的物理平面，从 而计算结果引入较大误差，已有大多数算法是选取两 个直线特征在它们完全相对应部分的邻近区域。本文 基于已经定义的直线特征端点定位的概率密度函数， 计算相似性测度时选取由提取直线特征的最大可能对 应的部分，并采取分块计算求和的方法。 如图３所示，一对立体图像，左图像，。和右图像 ，２，实线表示提取的直线特征ｚ 和ｚ 。取ｚ 和ｚ 的四个 端点中Ｙ坐标的最大值和最小值，如图３所示，分别为 Ｙ；， 和Ｙｉｌ２＇延长ｚ 至与核线Ｙ： ． 交于点Ｑ ，延长 至 与核线 ：ｙ啦交于点Ｑ：。选择ｚ 和ｚ 中较长的一个，假 定为ｚ ，且它们的长度之比为ｒ，指定ｚ 的两块邻域矩形 图像块，以点（ ，Ｙｉ． ）与Ｑ 之间的线段为长边，常数ｆ 为宽边，指定ｚ：的两块邻域矩形图像块，以点（ ；．。，Ｙｊ ，。） 与Ｑ：之间的线段为长边，∥ｒ为宽边。以Ａｒ为间隔从 点（ ，Ｙ１）开始在ｆｉ上取点，分别记为ｑ ，ｑ ，ｑ 等，计 ． 算它们在右图像Ｊ。中确定的核线与ｆ：或其延长线的交 点，分别记为ｑ：，ｑ ，ｑ 等，过ｚ 和Ｚ 上这些间隔点作各 自所在直线特征的垂线，假定它们将ｚ 和ｚ；的左、右两 侧邻域图像块各自分成１１，个子图像块，其中，ｚ 的左侧 子图像块记为｛ Ｉ １ ｋ ｎ｝，与之相对应的，ｚ 的右 侧子图像块记为｛ ｌ １ ｋ ｎ｝，ｚ；的左、右侧子图像 块分别记为｛碰 ｌ １ｓＪ｝ｉ ｎ｝和｛ＲＲ，ｋ Ｉ １≤ ｎ｝。 第５期 王继阳等：直线特征立体匹配中的不确定性问题 ６４５ 图３直线邻近区域灰度相似性计算 对｛ＬＬ ｌ １ ｋ≤ｎ｝和｛ ：ｌ １ ｋ ｎ｝中的所有子 图像块进行重采样，得到与ｚ 邻近的子图像块尺寸相 同的子图像块，分别记为｛ ｌ１ ｋ ｎ｝和｛ ｌ １≤ ｋ ｎ｝。计算左、右图像中任意两个相对应的子图像块 的灰度归一化互相关系数，基于此，定义ｚ 和ｚ 的灰度 相似性测度为 ｎ ， ． ｍ ∑ｍａｘ｛Ｆ（ＬＬ ， ），Ｆ（ＬＲ ， ）｝・ （ｑ ，ｑ川）・Ｋ；（ｑ ，ｑ ＋。） （１４） 其中，Ｆ（・，・）表示计算灰度归一化互相关系数的函数， Ｋ （・，・）表示计算左图像中的两个点位于ｚ。的两个真实 端点之问的概率，假定ｑ 的Ｙ坐标为 ，ｑ 的Ｙ坐 标为 ＋，，则 （ｑ ，ｑ川）＝ ＩＪ ｇ¨（Ｙ～¨）・ 歹ｍ＜ｔｚｌｌ＾，歹ｌ＿】＞ｔｚ¨＋ ｇ （Ｙ～ ）ｄ ｄｙ¨ （１５） Ｋ，（．，・）表示计算右图像中的两个点位于ｆ：的两个真实 端点之间的概率，假定ｑ 的Ｙ坐标为乃 ＋ 的Ｙ坐 标为 －，则 ＫＩ（ ， ＋。）＝ Ｊ＝『 ｇ¨ｔ ， ）・ ，２＜２ｊ， ，ｌ＞ ｍ＋１ ． ｇ ， （ ） ，。 ， （１６） 设定一个门限ｍ。，如果ｍ ＞ｍ。，则判定ｚ 和ｚ 可 匹配，且匹配测度为ｍ ３．３直线特征可匹配性测度定义 合并考虑两个直线特征满足核线约束和灰度相似 性约束的测度，简单地定义直线特征ｚ 和ｚ 的可匹配 性测度为核线约束测度和灰度相似性测度的乘积 Ｅ ＝ ，‘ｍ ，， （１７） ４实验 采用真实遥感立体图像，证实本文对于直线特征 端点定位不确定性描述方法的有效性。断裂直线特征 的编组假设是不确定的，可能存在错误，为此，本文设 计的匹配方法中采用了同时保留原有直线特征和编组 生成的新直线特征的方案，在最优匹配结果的选择中， 加入如下约束条件：（１）编组生成的新直线特征与组成 它的原有直线特征不相容；（２）同一个直线特征与至多 一个直线特征（可能是编组得到的新直线特征）相匹 配。在满足这两个约束条件的基础上，选择匹配测度 和最大的匹配对集作为最优匹配结果。最优化算法采 用基于图理论的全局最优化方法 。 ４．１实验条件 （１）实验图像 本实验使用两对经过核线校正的遥感立体图像 （如图４和图８所示）设计了两组实验，对比分别基于 Ｓｈｅｎ １２１定义的指数衰减型和本文提出的边缘证据 支持型的端点定位概率分布模型的直线特征匹配结 果。 （２）实验参数 本实验采用的边缘检测算法是Ｃａｎｎｙ算法 ， 直线特征提取算法是一种稳健的直线提取算法¨ 。 与公式（１）相关的参数， 。＝０．２５， ＝０．１，关 于 和 的设定，假定直线特征的端点到对应的真 实端点的有向距离位于（ ＋１０，＋∞）的概率为 ｒ／。／１０，从而 ＝０．２３０２，假定直线特征的提取端点 到真实端点的有向距离位于（一。。，一５］的概率为 叼 ／１０，从而 ＝０．４６０５；与公式（２）相关的参数， ＝１００（所有灰度梯度幅值被线性压缩至０—２５５）， Ｔ ＝０．７，Ｔ ＝３（像素），Ｔ ＝３（像素）；与公式（３） 相关的参数，Ａｓ＝３（像素）。与公式（９）有关的参 数，Ｔｏ＝５（像素）。 与计算核线约束测度相关的参数，Ａｚ＝２（像 素），同时设定一个门限值Ｔ，＝０．０００３，当依据公式 （１３）计算两个直线特征的核线约束测度值大于 ， 则认为它们满足核线约束；与计算灰度相似性相关 的参数，Ｗ＝５（像素），ｍ ＝０．０３。 （３）其它实验条件 在求解最优匹配结果的过程中，除应用了前文 提到的约束条件之外，还应用了局部的有序性约 束。值得注意的是，Ｓｈｅｎ 应用了拓扑一致性约束 ６４６ 信号处理 第２６卷 用于改善匹配结果，这与本文要说明的特征不确定 性问题无关，为此，在对该方法的实现中去掉了拓扑一 致陛约束；另外，Ｓｈｅｎ¨副提出的方法是对直线连接体进 行匹配，为了方法的可比性，本文一致地对单个的直线特 征进行匹配。 ４．２实验结果 图５和图９是基于Ｓｈｅｎ定义模型的匹配结果，图 ７和图１１是本文方法得到的匹配结果，在所有这些匹 配结果中，未编号的直线特征表示未得到匹配的直线， 在左右图像中编号相同的直线特征表示建立匹配关系 的同名直线特征。在图６和图１０的边缘检测结果中， 红色实线表示提取的直线特征，白色亮点表示本文方 法搜索得到的有效边缘点（检测到的其它无关边缘点 没有显示出来）。 第一组实验： （ｆ１）左图像 （ｂ）右图像 （ａ）左图像 （ｂ）右图像 图１。本文方法搜索到的有效边缘 图ｌ１ 本文方法得到的匹 点（白色亮点）（基于图８） 配结果（基于图８） 如表２所示为两组实验的统计结果， 表示提取 直线数， 表示应匹配直线数，Ⅳｃ表示正确匹配直线 数，Ｒ ＝Ｎ ／Ｎ 表示正确匹配率，Ⅳ 表示错误匹配直线 数，Ｒ ＝ ／（ ＋Ｎ）表示错误匹配率。 表２直线匹配结果统计 图像 Ⅳ本文方法 ｔ Ⅳ Ｓｈｅｎ的方法 Ｎ Ｒ Ｎ Ｒ Ｎ ｅ Ｒｃ Ｎｔ 图４（ａ） ｌ３１ ７６ ５９ ７７．６％ １８ ２３．４％ ７０ ９２．１％ １３ ｌ５．７％ 图４（ｂ） ｌ２４ ６８ ５９ ８６．８％ １８ ２６．５％ ６６ ９７．１％ １３ １６．５％ 图８（ａ） ｌ４８ ８２ ６０ ７３．２％ ２２ ２６．８％ ７１ ８６．６％ ｌ８ ２Ｏ．２％ 图８（ｂ） ｌ５Ｏ ８３ ６０ ７２．３％ ２２ ２６．５％ ７０ ８４．３％ １８ ２Ｏ．５％ ４．３结果分析 从两个方面对本文给出的实验结果进行分析： （１）匹配结果 从表２的匹配结果来看，两种方法得到的匹配错 误率都较高，这是由于图像杂乱的背景以及图像模糊 造成的，就图像质量而言，比近景图像的匹配更难，然 而，与Ｓｈｅｎ的方法相比，本文方法的匹配正确率显著 提高，而匹配错误率则较大幅度降低。对于图７中编 号为１８的直线匹配对，尽管图７（ｂ）中的直线特征的 一个端点显著偏离图７（ａ）中直线特征的相应端点确 定的核线，但如图６（ｂ）所示，该直线特征的端点的有 效边缘点能够弥补直线提取的不足，基于边缘点证据 对原有直线特征进行延长后，利用本文方法计算的核 线约束测度明显增大，图１１中编号为１８和２０的匹配 对也属于这种情况。另外，图７中编号为３、９、１４、１９、 ６２和６６的匹配对是对断裂直线特征的匹配，尤其是编 号为９和６６的两组断裂直线特征，相邻端点距离比较 远，此时，单纯依据相邻端点距离远近判定断裂直线特 征编组假设可靠性的方法，将它们编组在一起将冒很 大的增加编组错误的风险，本文利用搜索得到的有效 边缘点作为证据，可以更可信地实现断裂直线特征的 编组，图１１中编号为６、７、１５、１６、２５、３３、３８和４６的直 线匹配对也属于对断裂直线特征的匹配。 （２）计算性能 Ｓｈｅｎ的方法对于端点定位的概率定义式是解析 的，计算更为容易；本文方法则不具备解析表达式，大 量积分运算需要采用数值计算的方法，得到的只能是 近似值，但本文通过引入插值运算，可以在一定程度上 减小近似误差，并且能够有效避免计算结果分阶段跳 跃的现象。另外，本文没有具体分析边缘证据用于计 算匹配概率的计算量，实验过程表明两种方法的总体 运行时间差异并不显著，计算量主要体现在全局最优 化计算过程中。 ５ 结论 本文以未被拟合的边缘点作为描述直线特征提取 ¨ ］ｊ １●Ｊ］Ｊ １ｊ第５期 王继阳等：直线特征立体匹配中的不确定性问题 ６４７ 不完整和提取断裂两类不确定性的依据，以概率密度 动化学报，２００３，２９（４）：５８９—５９８． 函数的形式对它们进行了定量分析，以此为基础，计算 了融合特征不确定性的直线匹配测度。事实上，把满 足文中几个限定条件的边缘点作为直线段延长或断裂 直线特征编组的证据只是一种假设，然而这种假设是 合理的：首先，选作证据的边缘点不是任意的，而是位 于已提取直线特征的延长线附近，并且其梯度属性与 拟合得到该直线的边缘点相似，因而，已有直线提取结 果可视为合理而可靠的引导信息；其次，核线约束的测 度成为对这种假设的印证，如果直线特征的延长或断 裂直线特征编组假设是错误的，由于不同图像中假设 的非一致性，会使匹配测度值降低，从而，由于边缘点 证据的引入，可以更显著地区分正确与错误的对应性 假设，实验结果也说明了这一点。 从匹配结果看，尽管本文方法能够匹配更多的直 线特征，但错误匹配概率仍然较高，除了图像质量的原 因外，就算法本身，主要的原因是全局最优化算法的使 用，使不存在匹配直线的直线特征得到匹配。下一步 研究的重点将是针对直线特征提取出现严重缺失情况 下的优化算法设计问题。 参考文献 Ｄａｖｉｄ Ｐ，Ｄｅｍｅｎｔｈｏｎ Ｄ．Ｏｂｊｅｃｔ ｒｅｃｏｇｎｉｔｉｏｎ ｉｎ ｈｉｇｈ ｃｌｕｔｔｅｒ ｉｍａｇｅｓ ｕｓｉｎｇ ｌｉｎｅ ｆｅａｔｕｒｅｓ．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １０ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００５，２： １５８１．１５８８． Ｋｉｍ ＺＷ，Ｎｅｖａｔｉａ Ｒ．Ａｕｔｏｍａｔｉｃ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｂｕｉｌｄｉｎｇｓ ｆｒｏｍ ｍｕｌｔｉｐｌｅ ｉｍａｇｅｓ．Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍ— ａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ，２００４，９６（１）：６０—９５， Ｎｏｒｏｎｈａ Ｓ，Ｎｅｖａｔｉａ Ｒ．Ｄｅｔｅｃｔｉｏｎ ａｎｄ ｍｏｄｅｌｉｎｇ ｏｆ ｂｕｉｌｄ— ｉｎｇｓ ｆｒｏｍ ｍｕｈｉｐｌｅ ａｅｒｉａｌ ｉｍａｇｅｓ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００１，２３ （５）：５０１－５１８． Ｓａｌｖｉ Ｊ，Ｍａｔａｂｏｓｃｈ Ｃ，Ｆｏｉｌ Ｄ，ｅｔ ａ１．Ａ ｒｅｖｉｅｗ ｏｆ ｒｅｃｅｎｔ ｒａｎｇｅ ｉｍａｇｅ ｒｅｇｉｓｔｒａｔｉｏｎ ｍｅｔｈｏｄｓ ｗｉｔｈ ａｃｃｕｒａｃｙ ｅｖａｌｕａ— ｔｉｏｎ．Ｉｍａｇｅ ａｎｄ Ｖｉｓｉｏｎ Ｃｏｍｐｕｔｉｎｇ，２００７，２５：５７８－５９６． Ｐａｊａｒｅｓ Ｇ，Ｃｒｕｚ ＪＭ．Ｆｕｚｚｙ ｃｏｇｎｉｔｉｖｅ ｍａｐｓ ｆｏｒ ｓｔｅｒｅｏｖｉｓｉｏｎ ｍａｔｃｈｉｎｇ．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２００６，３９（１ １）：２１０１— ２１１４． Ｊｕｒｉｅ Ｆ．Ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｓｉｍｕｌｔａｎｅｏｕｓ ｐｏｓｅ ａｎｄ ｃｏｒｒｅｓｐｏｎ— ｄｅｎｃｅ ｐｒｏｂｌｅｍ ｕｓｉｎｇ Ｇａｕｓｓｉａｎ ｅｒｒｏｒ ｍｏｄｅ１．１９９９，７３（３）： ３５７—３７３． Ｃｈｒｉｓｔｍａｓ ＷＪ．Ｓｔｒｕｃｔｕｒａｌ ｍａｔｃｈｉｎｇ ｉｎ ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ ｕ— ｓｉｎｇ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｒｅａｓｏｎｉｎｇ．ｔｈｅ Ｔｈｅｓｉｓ ｏｆ ｔｈｅ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｕｒｒｅｙ，１９９５． 孙凤梅，胡宇，胡占义．直线提取中的不确定性研究．自 ［９］ Ｓｈｉｍｓｈｏｎｉ Ｉ，Ｐｏｎｃｅ Ｊ．Ｒｅｃｏｖｅｒｉｎｇ ｔｈｅ ｓｈａｐｅ ｏｆ ｐｏｌｙｈｅｄｒａ ｕｓｉｎｇ ｌｉｎｅ・－ｄｒａｗｉｎｇ ａｎａｌｙｓｉｓ ａｎｄ ｃｏｍｐｌｅｘ ｒｅｆｌｅｃｔａｎｃｅ ｍｏｄ－－ ｅｌｓ．Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ，１９９７，６５ （２）：２９６—３１０． ［１０］Ｊｉ Ｑ，Ｈａｒａｌｉｃｋ ＲＭ．Ｅｒｒｏｒ ｐｒｏｐａｇａｔｉｏｎ ｆｏｒ ｔｈｅ Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍ．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ，２００ １，２２（６—７）： ８１３—８２３． ［１ １］Ｔａｎ ＴＮ，Ｓｕｌｌｉｖａｎ ＧＤ，Ｂａｋｅｒ ＫＤ．Ｍｏｄｅｌ—ｂａｓｅｄ ｌｏｃａｌｉｚａ— ｔｉｏｎ ａｎｄ ｒｅｃｏｇｎｉｔｉｏｎ ｏｆ ｒｏａｄ ｖｅｈｉｃｌｅｓ．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｎｒ－ ｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，１９９８，２７（１）：５—２５． ［１２］Ｓｈｅｎ ＸＱ，Ｐａｌｍｅｒ Ｐ．Ｕｎｃｅｒｔａｉｎｔｙ ｐｒｏｐａｇａｔｉｏｎ ａｎｄ ｔｈｅ ｍａｔｃｈｉｎｇ ｏｆ ｊｕｎｃｔｉｏｎｓ ａｓ ｆｅａｔｕｒｅ ｇｒｏｕｐｉｎｇｓ．ＩＥＥＥ Ｔｒａｎｓ— ａｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０００，２２（１２）：ｌ３８１—１３９５． ［１３］Ｗｅｌｌｓ ＷＭ．Ｓｔａｔｉｓｔｉｃａｌ ａｐｐｒｏａｃｈｅｓ ｔｏ ｆｅａｔｕｒｅ—ｂａｓｅｄ ｏｂｊｅｃｔ ｒｅｃｏｇｎｉｔｉｏｎ．Ｉｎｔｅｍａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， １９９７，２１（１／２）：６３－９８． ［１４］Ｃｈｅｎｇ ＹＱ，Ｗａｎｇ ＸＧ．Ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｐｏｉｎｔｓ ａｎｄ ｌｉｎｅｓ ｗｉｔｈ ｕｎｋｎｏｗｎ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ａｃｒｏｓｓ ｉｍａｇｅｓ．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００１， ４５（２）：１２９—１５６． ［１５］Ｅｔｓｕｊｉ Ｔ，Ａｋｉｒａ Ｔ，Ｈａｒｕｈｉｓａ Ｔ．Ｔｈｅ ｗｏｒｓｔ—ｃａｓｅ ｉｔｍｅ ｃｏｍ— ｐｌｅｘｉｔｙ ｆｏｒ ｇｅｎｅｒａｔｉｎｇ ａｌｌ ｍａｘｉｍａｌ ｃｌｉｑｕｅｓ ａｎｄ ｃｏｍｐｕｔａ— ｔｉｏｎａｌ ｅｘｐｅｒｉｍｅｎｔｓ．Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００６， ３６３：２８—４２． ［１６］Ｃａｎｎｙ ＪＦ．Ａ ｃｏｍｐｕｔａｔｉｏｎａｌ ａｐｐｒｏａｃｈ ｔｏ ｅｄｇｅ ｄｅｔｅｃｔｉｏｎ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌ— ｌｉｇｅｎｔ，１９８６，８（６）：６７９—６９８． ［１７］文贡坚，王润生．一种稳健的直线提取算法．软件学 报，２００１，１２：１６６０—１６６６． 作者简介 王继阳（１９８０一），男，吉林永吉人，信 息与通信工程专业博士研究生，主要研究 领域为摄影测量与遥感，３Ｄ重建。 文贡坚（１９７２一），男，湖南宁乡人，博士，研究员，主要研 究领域为摄影测量与遥感、图像分析和理解、模式识别和人 工智能。 李德仁（１９３９一），男，江苏泰州人，教授，博十生导师，中 国科学院院上，中国工程院院上，欧亚科学院院士，主要研究 领域为以遥感、全球定位系统和地理信息系统为代表的空问 信息科学与技术。
