室外建筑物场景图像的匹 配扩散研究陈占军 2010.01.12大纲宽基线图像准稠密匹配扩散原理宽基线建筑物图像的准稠密匹配扩散的困难及 关键点算法改进：适用于室外建筑物场景图像的匹配 与扩散实验结果存在问题及下一步工作宽基线图像准稠密匹配扩散原理准稠密匹配扩散介绍及其意义宽基线图像准稠密匹配扩散算法准稠密匹配扩散介绍及其意义三种匹配-稀疏匹配: 提取特征点并加以匹配，得到稀疏匹配点，数量很少，一般几十 几千对 -稠密匹配: 通过逐点比较匹配，将第一幅图像中的每个像素点都与第二幅图像 中的像素点比较，找出对应点。(数量巨大。对于一幅1024x768的图像，要 寻找78,6432万对匹配，而搜索计算是这个数字的几百倍以上)稀疏匹配(sparse matching)稠密匹配(dense matching)准稠密匹配(quasi-dense matching)-准稠密匹配：是稀疏匹配和稠密匹配的一个折中（匹配点对数大概几 千几万）。准稠密匹配扩散准稠密匹配扩散 输入输入：两幅对应图像的稀疏匹配，即种子点匹配目的目的：通过扩散，使得两幅图像之间匹配对数增加，并尽 可能均匀，以利于重建。特点特点：1) 匹配点数达到一定量(准稠密) 2) 匹配点分布均匀准稠密匹配扩散的意义稀疏匹配得到的匹配数量太少，不足以用于三维重建；稠密匹配在空间和时间复杂度上太高；准稠密匹配扩散弥补了上述两种匹配的局限性和缺点，具有 更好的适应性。宽基线图像对准稠密匹配扩散-扩散过程初始种子点匹配step1. 初步估计极几何关系step2.确定种子点邻域step3.在种子点邻域内扩 散出可能匹配点step4. 重采样step5 估计基本矩阵step6. 去除错误匹配点最终准稠密匹配作 为 新 的 种 子 点扩散算法介绍输入：初始种子点匹配提取特征点或特征区域，常用的特征检测算法有SIFT，MSER， Harris-Affine, Hessian-Affine等；再用SIFT或Daisy等描述子对特 征进行描述，得到初始对应匹配点；计算初始匹配点的ZNCC分数，并按照ZNCC分数由高到低排列成 种子点队列。1222( ()( )( ()()( ,) ( ()( )( ()() )iI pI pIpIpZNCCp p I pI pIpIp + + =+ + 宽基线图像对准稠密匹配扩散-扩散过程初始种子点匹配step1. 初步估计极几何关系step2.确定种子点邻域step3.在种子点邻域内扩 散出可能匹配点step4. 重采样step5 估计基本矩阵step6. 去除错误匹配点最终准稠密匹配作 为 新 的 种 子 点扩散算法介绍Step1：初步估计几何关系 运用RANSAC算法，由初始种子匹配点估计基本矩阵F。扩散策略：采取最优最先(Best-First)策略，即每次从种子点 队列中取出ZNCC分数最高的种子点，由该种子来扩散出更 多点。Step2：确定当前种子点邻域 以左右图中的种子点和为中心，在其周围选取一个矩形 窗口邻域，。( )N xxx( )N x宽基线图像对准稠密匹配扩散-扩散过程初始种子点匹配step1. 初步估计极几何关系step2.确定种子点邻域step3.在种子点邻域内扩 散出可能匹配点step4. 重采样step5 估计基本矩阵step6. 去除错误匹配点最终准稠密匹配作 为 新 的 种 子 点扩散算法介绍Step3：在种子点邻域内扩散出可能匹配点 对和内的点对，判断其是否满足如下四个 约束条件：(1) 离散二维视差梯度极限约束 在邻域和上，满足二维视差梯度限制的候选 匹配定义为：( , )( , ),( ),( ), () ()N x xu uuN x uN xuuxx =( ,)N x x( )N x( )N x( )N x( )N x(2)灰度相似性约束 采用ZNCC值来度量匹配的相似性，ZNCC值越大， 匹配的可靠性越高.只保留ZNCC值大于一定阈值的匹 配点。(3)置信度约束 置信度的限制是用来防止匹配扩散到灰度过于一致、 纹理信息稀少的区域(如天空)，图像I上某点x的置信 度被定义为：(4)唯一性约束：保证点与点之间的一一映射关系. 扩散示例图：对于满足上述四个约束条件的，列为候选匹配点。并将这 些点作为新的种子点，重复Step2，进一步扩散。宽基线图像对准稠密匹配扩散-扩散过程初始种子点匹配step1. 初步估计极几何关系step2.确定种子点邻域step3.在种子点邻域内扩 散出可能匹配点step4. 重采样step5 估计基本矩阵step6. 去除错误匹配点最终准稠密匹配作 为 新 的 种 子 点扩散算法介绍-Step4：重采样：重采样-调整匹配点的分布1)将第一幅图像分割成8* 8像素大小的正方形小区域。2)对每个小区域中的已有对应点采用RANSAC计算一个仿射 矩阵A。3)假设小区域的中心点为xC，根据仿射矩阵A计算中心点在 另一幅图像中的精确对应位置为A*xC， 组成一队新的采样 匹配：(xC, A*xC)；若小区域内存在种子匹配点，则保留 它；拟合A至少需要3对匹配点。4)根据仿射矩阵A，计算小区域内所有点在另一幅图像中的 对应点。将这些匹配存入结果队列并按ZNCC分数排序，即 是重采样结果。扩散算法介绍Step5：用RANSAC算法估计基本矩阵F。Step6：剔除不满足极线约束的外点。宽基线建筑场景图像扩散的困难及关 键点宽基线建筑场景图像扩散困难 1) 由于纹理单一，导致种子点提取和匹配的数量大大 减少、正确率降低，以及分布不均匀。 2) 由于局部区域的纹理重复，导致扩散存在匹配模糊 问题，从而使扩散出的点不准确。扩散关键点 1) 选取更可靠、能提取特征数量更多的提取算法，并 加以匹配，得到更多种子点。 2) 种子点对邻域的恰当选取，使得两个邻域对应的内 容相同。 3) 采取更好的匹配相似度量准则，降低匹配模糊。扩散算法改进1) 采取较鲁棒的、可靠的特征提取算法MSERDoG， 并对特征点进行匹配，得到初始种子点。2) 以种子点为中心，沿其极线方向选取矩形窗口邻域， 用仿射变换来近似左右图像的局部区域的对应关系。3) 运用自适应支持权重ASW(Adaptive Support- Weight)方法，来度量扩散点的匹配程度。扩散算法改进1: MSERDoG提取算法介绍MSERDoG特征提取算法是指在高斯差分空间 中提取最大稳定极值区域，其思想是从高斯差 分空间中所找到的极值点出发，对每个极值点 都能找到一个最大稳定极值区域。对检测出来 的区域做椭圆拟合，将椭圆通过二阶矩矩阵映 射到单位圆，然后建立SIFT描述子，从而构造 出初始种子匹配点。Zhijun Dai, Yihong Wu and Zhanyi Hu, Maximally Stable Extremal Region on the Difference of Gaussian Space, Machine Vision and Applications, 2009.MSERDoG提取算法优点对于视角变化大的图像，MSERoG在重复率、正确 匹配数量等方面都有优势。如对视角逐渐变化的Graffiti图序列，不同的特征检 测算法在正确匹配数量上比较：SIFT 与MSERDoG提取算法得到的种 子匹配点比较SIFT特征提取得到的种子点（232对）MSERDoG特征提取并通过匹配得到的种子点 （276对）可见扩散算法改进2: 种子点邻域选取种子点对应邻域的选取关系到扩散成功与否。扩散要 求邻域包含的图像内容必须一致。对于短基线图像对，可以沿着种子点的水平方向直接 选取矩形窗口邻域，再进行扩散。对于宽基线图像对，由于透视变换严重，简单地沿水 平方向直接选取矩形窗口会导致扩散失败，所以，可 以在左边图像中，沿种子点极线方向选取矩形窗口邻 域，通过仿射变换映射，得到右边图像的对应区域。A矩阵是对应种子点的邻域仿射变换矩阵，R1, R2 分别代表旋转矩阵，B矩阵是区域P与Q之间的变 换矩阵，自由度为3。上式中R1和R2已知(由基本矩阵F确定极线方 向)，因此只要求出B就能计算出A。 B的自由 度为3，设B有如下形式：参数a控制沿X方向的尺度变化，参数b控制沿 X方向的斜切大小，参数c控制沿Y方向的尺度 变化，如下图所示：仿射变换不改变直线之间的平行关 系以及线段的比例关系，而两条对 极线方向已知，且分别平行于各自 邻域的平行四边形对应两条边。这 就限制了仿射矩阵的形式，减少了 自由度B矩阵的各参数搜索策略：由于邻域窗口选择比较小，如11*11，所以只 要将a、c两参数在1左右小幅度变化搜索，将b 参数在0左右小幅度变化搜索；在搜索过程中， 每次搜索结果对应于一个B矩阵，再由前面关 系式计算出A矩阵，从而也确定了左右种子点 的对应邻域，对这两个邻域做ZNCC相关，若 得到的ZNCC分数最大，则最终保留A。扩散算法改进3: 自适应支持权重ASW (Adaptive Support-Weight)方法ASW是一种度量点的匹配程度的准则，在给定窗口内， 结合颜色信息和几何距离信息，加权求和来计算匹配 代价函数，以此来度量待匹配点的匹配程度。用ASW来度量，可以解决由于纹理单一或纹理重复而 导致的图像匹配模糊问题。K. J. Yoon and I. S. Kweon, “Adaptive support-weight approach for correspondence search,“ IEEE Trans. Pattern Anal. Mach. Intell. 28(4), 650-656 (2006) 扩散算法改进3: 自适应支持权重ASW (Adaptive Support-Weight)方法ASW匹配代价函数(matching cost or dissimilarity)：参考图像窗口目标图像窗口扩散算法改进3: 自适应支持权重ASW (Adaptive Support-Weight)方法像素支持权重：p与q之间在CIELab颜色空间的欧式距离：p与q之间的几何距离： CIELab颜色差值参数： 几何距离参数，由窗口大小决定CIELAB色彩空间根据人眼视觉的 特性，把光线波长转换为亮度和色 相的一套描述色彩数据，其中L描 述色彩的亮度，A描述色彩的范围 从绿色到红色，B描述色彩的范围 从蓝色到黄色。，:表示参考图像和目标图像中分别以， 为中心 的窗口原始匹配代价(raw matching cost)：T：颜色截断值() , , ( ,)min( ),dccd cr g be q qI qIqT= 原始图像窗口窗口内像素权重分布图实验结果初始种子匹配点（276对）极限约束扩散（493601对）重采样及去除外点后结果（3225对）三维重建结果:重建结果：存在问题及下一步工作存在错误匹配点及改进点的精度和扩散的可控性遮挡问题谢谢大家！