局部特征匹配

Size: px

Start display at page:

Download "局部特征匹配"

竣雷
4 years ago
Views:

1 University of Science and Technology of China 局部特征匹配谱聚类, 图匹配陈述人 : 曹梦霏辅导老师 : 庄连生

2 一二三背景介绍研究内容对应性研究算法基本原理特征匹配算法结果与总结

3 一背景介绍

4 一背景介绍 ( 一 ) 问题引入与相关领域 : 人工智能数据挖掘模式识别图模型几何信息矩阵谱获取特定模式匹配数学模型对应关系

5 一背景介绍 ( 二 ) 匹配相关应用 : 可变形模板用于识别 1 ( 相比于人工标定 ) 1 (CVPR05) Alexander C. Berg, Tamara L. Berg, Shape Matching and Object Recognition using Low Distortion Correspondence

6 一背景介绍 ( 二 ) 匹配相关应用 : 图像语义理解, 分层目标语义 2 ( 几何信息, 共生关系 ) 2 (ICCV07) Devi Parikh and Tsuhan Chen, Unsupervised Learning of Hierarchical Semantics of Objects (hsos)

7 二研究内容对应性研究算法基本原理特征匹配算法

8 二研究內容对应性研究 ( 一 ) 方法类别 ( 从对数据信息的使用的角度 ): 1. 直接比较数据集合间各元素在特征空间的距离例如 : 穷举, 金字塔核算法 ( 间接 ) 2. 一致性度量利用匹配对之间的关系获得匹配对的集合例如 : 距离角度一致性

9 二研究內容对应性研究 ( 二 ) 1. 精确度比较相似度 : (i-i ),(i-j ),(j-i ),(j-j ) 鲁棒性 2. 计算复杂度比较一致性 : (i-j) v.s. (i -j )

10 二研究内容对应性研究算法基本原理特征匹配算法图匹配模型谱聚类

11 二研究內容算法基本原理特征空间 & 平面信息数学工具对应性关系集合局部特征点及特征描述符图匹配模型谱聚类匹配

12 二研究內容算法基本原理图匹配模型 ( 一 ) 图匹配问题 : 对于一个模型图 G M =(V M,E M ), 一个数据图 G D =(V D, E D ), 并满足 V M = V D, 处理所有信息并判决两图的相似性精确图匹配问题 : 寻找一个同态映射 f:v D V M, 其中对任意 (u,v) E D, 有 (f(u),f(v)) E M 非精确图匹配问题 : 定义一个目标函数以获取其极值为目标得到图的最佳匹配

13 二研究內容算法基本原理图匹配模型 ( 二 ) 目标 : 获得正确匹配矩阵 y, 其中 y ii {0,1}: 当第一个图中的结点 i 映射到第二个图中的 i, 则 y ii =1, 否则 y ii =0 方法 : 通过二次规划得出最优匹配矩阵 y* argmax ii' ii' ii ' jj ' ii ' jj ' y ii' ii' y c y d y y * [ ] 特征空间信息平面空间一致性难点 : 二次规划常常是 np-hard 问题

14 二研究內容算法基本原理谱聚类分类, 优点直接特征向量聚类主类计算简单准确多类不稳定普适任意数据集形状普适任意模式图拉普拉斯聚类精确鲁棒计算复杂快速, 精确原理上, 该算法具有图论和矩阵分析的理论基础

15 二研究内容对应性研究算法基本原理特征匹配算法

16 二研究內容特征匹配算法 ( 一 ) ( 一 ) 实际流程获取局部特征点图匹配模型获得对应关系点集 P 映射 (a,b) 谱聚类 Pairwise 的主类点集 Q

17 二研究內容特征匹配算法 ( 二 ) ( 二 ) 算法步骤 Step1: 提取特征点并获得可能的匹配对集 Δ={p 1,p 2,,p m } Step2: 计算一致性矩阵矩阵 M: M ij agreement ( pi, p j ), i j; M similarity( p ); ii ( i) ( i) i( a, b ) Step3: 计算矩阵 M 的主特征值 λ 及对应的特征向量 x Step4: 从 x 中取最大元素获得对应的正确的匹配对, 并依据约束利用每个已获得的匹配删除对应不可能的匹配对 ; 即将该元素和被约束的匹配对的对应元素值赋 0 Step5: 若 x 为全 0 向量则结束获得全部对应关系, 否则返回 Step4

18 二研究內容特征匹配算法 ( 三 ) : 在目前两篇使用该思想的文章中, 一致性矩阵中的几何约束信息来自于显式的两个潜在点对的距离与方向的差别思想 :1) 挖掘更为鲁棒的显式平面约束信息 2) 利用训练学习出最佳一致性度量 : 具体实现过程中, 谱聚类的主特征向量具有一定数值特征 ; 利用此特征获得寻求主类时的阈值计算思想 :1) 理论推导数值关系解 2) 利用训练学习出最佳阈值

19 三结果与总结

20 三结果与总结实验结果 ( 一 ) ( 一 ) 仿真实验实验平台数据及参照实验方法解释 : MATLAB 2008a,fedora 7 OS rand(),randn() 1 linprog 实验结果 : (1) 精度 & 鲁棒性 (2) 时间复杂度 1 (CVPR05) Alexander C. Berg, Tamara L. Berg, Shape Matching and Object Recognition using Low Distortion Correspondence

21 三结果与总结实验结果 ( 一 ) (1) (1) 精度 & 鲁棒性高斯噪声外点干扰

22 三结果与总结实验结果 ( 一 ) (2) (2) 时间复杂度点数时间 /s 基于谱聚类基于一次规划倍数

23 三结果与总结实验结果 ( 二 ) ( 二 ) 图像实验实验平台解释 : MATLAB 2008a,fedora 7 OS 3 DOG 特征提取算子 SIFT 特征描述符实验结果 : 外点去除图示及过程变量优化 3 D. Lowe,

24 三结果与总结实验结果 ( 二 ) (1) 1) 能够较好的去除外点, 并保留正确匹配的点 (1/77) (1/37) 2) 隐含问题 : 左边两组匹配图的谱处理的阈值要求并不相同 ; 一组适合的阈值可能导致另一组发生正确匹配对误除或错误匹配对漏检

25 三结果与总结实验结果 ( 二 ) (2) 解决思路 : 1) 寻找更鲁棒的一致性度量 2) 大样本寻训练阈值缺点 : 由于阈值随干扰变化而变, 因此并非固定值, 不具备普适性 3) 理论计算 & 变量估计缺点 : 缺乏理论支撑

26 三结果与总结实验结果 ( 二 ) (3) 理论上, 理想情况下主特征向量元为 : 1 n, 其中 n 为正确匹配数特征集 P np 个特征特征集 Q nq 个特征特征向量元 1/sqrt(n), n 为正确匹配数阈值 <1/sqrt(n) 上图为实际问题模型, 正是闭环导致无法精确求解 ; 但是可以利用相关变量以及样本, 得到近似的估计关系式

27 三结果与总结实验结果 ( 二 ) (4), 例 :( 结果中五组图片获得全部且保持正确匹配 ) Sift features (left) Sift features (right) Number of initial matches Info of wrong matches Min error (1)Box 错 *e-17 Max value Min value (2)basmati 错 (3)Tmp 错 (4)lena (scale) (5)lena (roatate) 无错 *e 无错 ζ 为两特征集中特征数目的小者 η 为主特征向量最大元素扰动关系 ( 估计量 ) 数值变化规律和 = * * =tan( ) 720

28 三结果与总结总结 1) 工作总结 : 通过对 100 余篇论文的调研, 初步理解当前领域中该课题所有相关工作 ; 并着重实现了两种方法, 在理论论证和实验验证中发现较多问题并提出一定改进 2) 工作计划 :a. 挖掘一致性度量的新模式 ( 显式或基于学习的方法 ) b. 谱聚类自身稳定性改进 ( 包括变量优化处理等 ) c. 针对实际应用的变化移植

29 University of Science and Technology of China 谢谢 ^_^

涓浗鏂囧寲

涓浗鏂囧寲第三部分中国文化一选择题 111. 中国古代伟大的思想家和教育家被联合国教科文组织列为世界十大文化名人之一 A. 庄子 B. 老子 C. 韩非子 D. 孔子答案 :D 112. 第一部被介绍到西方去的中国古代戏曲是, 它是著名的元杂剧四大悲剧