图像处理与分析 图像特征匹配 授课教师 : 孙剑 jiansun@mail.xjtu.edu.cn http://jiansun.gr.xjtu.edu.cn 西安交通大学数学与统计学院
目录 l 为什么要进行特征提取? l Harris 角点检测 l 特征检测器 (Feature detector) l 特征描述子 (Feature descriptor)
图像特征提取 l 图像特征提取 : 提取图像中的关键特征点 ( 例如边 角点等 ), 并对这些特征点进行描述 图像特征被用于图像的匹配 识别和检索等
应用实例 : 建立全景图 l 生成图像全景图 : 从不同角度拍摄大的场景中的多幅图像, 将多幅图像拼成一幅全景图像 全景图像例子 : 由多幅图像拼合而成, 一般的相机均有此功能 参考文献 :M. Brown and D. G. Lowe. Recognising Panoramas. ICCV 2003
应用实例 : 建立全景图 l 需要匹配多幅图像 : 多幅图像匹配可以通过两两图像匹配实现
应用实例 : 建立全景图 图像匹配步骤 1: 从两幅图像中检测特征点 从两幅图像中检测出的特征点用圆形表示
应用实例 : 建立全景图 图像匹配步骤 2: 匹配两幅图像中的特征点
应用实例 : 建立全景图 图像匹配步骤 3: 通过匹配点对计算两幅图像之间的几何变换 (Homography), 并将右图按照该几何变换进行变换, 融合两幅图像得到拼合而成的全景图
图像特征提取 l 关键问题 1: 在两幅图像中检测到重复出现的特征点 如何正确匹配特征点? no chance to match!?
图像特征提取 l 图像特征提取的其他应用 : 图像的匹配 (homography, fundamental matrix) 三维重建 物体识别 图像数据库的检索 机器人的导航
目录 l 为什么要进行特征提取? l Harris 角点检测 l 尺度不变特征检测器 (Feature detector) l 特征描述子 (Feature descriptor)
Harris 角点检测子 特征点检测的典型算法 : Harris 角点检测子 参考文献 :C.Harris, M.Stephens. A Combined Corner and Edge Detector. 1988
Harris 角点检测子 l 基本思想 : 通过分析局部图像块的性质判断像素点是否为角点 判断标准是 : 向任何方向移动该窗口都会导致亮度的显著变化
Harris 角点检测子 flat : 在所有方向平移窗口, 亮度均不变 edge : 沿着边的方向平移窗口, 亮度不变 corner : 在所有方向平移窗口, 亮度均变化
数学模型 : Harris 角点检测子 当窗口平移向量 [u,v] 时的亮度变化为 : xy, [ ] 2 Euv (,) = wxy (, ) I( x+ uy, + v) I(, xy) 窗口函数 平移后的亮度值 原亮度值 窗口函数 w(x,y) = 或 1 in window, 0 outside Gaussian
Harris 角点检测子 当平移向量 [u,v] 很小时, 亮度变化量可以由下式逼近 ( 泰勒展开 ) u Euv (, ) [ uv,] M v M 是一个 2 * 2 矩阵 : M 2 Ix IxI y = w(, x y) 2 xy, II x y Iy
Harris 角点检测子 特征值分析 u Euv (, ) [ uv,] M v v 1, v 2 eigenvalues of M 变化最快的方向 等值椭圆 :E(u,v) = const (v max ) -1/2 (vmin )-1/2 变化最慢的方向
Harris 角点检测子 通过分析 M 的特征值, 确定像素点的类型 : v 2 Edge v 2 >> v 1 Corner v 1 和 v 2 都很大 v 1 ~ v 2 ; E 在当窗口向各个方向平移时均变换很大 v 1 和 v 2 都很小 ; E 在当窗口向各个方向平移时均接近不变 Flat Edge v 1 >> v 2 v 1
Harris 角点检测子 角点检测响应强度 : R= det M k M ( trace ) 2 det M trace M = λλ 1 2 = λ + λ 1 2 (k = 0.04-0.06)
Harris 角点检测子 Corner: R > 0 v 2 Edge R < 0 Corner edge:r < 0 flat: R 很小 R > 0 Flat R small Edge R < 0 v 1
Harris 角点检测子 l 算法 : 寻找 R 值很大的点 (R > threshold) 保留为局部极大 R 的点
Harris 角点检测子 例子
Harris 角点检测子 例子 计算角点响应值 R
Harris 角点检测子 例子 找到具有较大角点响应 R 的像素点 : R>threshold
Harris 角点检测子 例子 仅保留具有局部极大 R 值的像素点作为特征点
Harris 角点检测子 例子
Harris 角点检测子 性质 l 旋转不变性 椭圆旋转但是形状未发生变化, 特征值保持不变
Harris 角点检测子 性质 l 不具有尺度不变性 所有点都被认为是边 (edge) 角点!
目录 l 为什么要进行特征提取? l Harris 角点检测 l 尺度不变特征点检测器 l 特征描述子 (Feature descriptor)
尺度不变特征点检测 例如进行尺度不变的角点检测 : 主要思想 : 找到最优的尺度使得某个函数 f 具有局部最大值 f 通常定义为 : Laplacian 滤波响应
Slide from Tinne Tuytelaars Lindeberg et et al, al., 1996
目录 l 为什么要进行特征提取? l Harris 角点检测 l 尺度不变特征点检测器 l 特征描述子
特征描述子 给定检测出的特征点, 如何匹配这些特征点? 特征描述子 : 需要将特征点的局部区域描述为一个向量 ( 称为特征描述 ), 通过匹配这些向量实现特征点匹配?
特征描述子? 特征描述子要求具有不变性 : 当图像发生变换 ( 平移 尺度 旋转等 ), 特征点仍然能准确匹配 目前最好的特征描述之一 : SIFT David Lowe, UBC http://www.cs.ubc.ca/~lowe/keypoints/
特征描述子 实现变换不变性的图像匹配 : 1. 特征检测子需要有不变性 Harris 检测子对图像平移和旋转具有不变性 为实现尺度不变性, 通常在 Laplacian 尺度空间中选择最优尺度 2. 特征描述子需要有不变性 最简单的描述子 : 采用像素点周围的小图像块 对旋转和放缩变换均不具有不变性 以下将设计具有不变性的特征描述子
特征描述子 如何实现旋转不变性 : 找到特征点周围小窗口的主方向, 主方向由 M 矩阵的最大特征值对应特征向量确定 将窗口旋转, 使得特征点主方向成为窗口的主方向 Figure by Matthew Brown
特征描述子 Multiscale Oriented PatcheS descriptor 取像素点周围 40x40 的图像块 ( 沿着特征点主方向 ) 将图像块放缩到 8 x 8 将图像块进行正规化 : 减去均值, 并除以窗口的方差 ( 消除亮度的影响 ) 40 pixels 8 pixels CSE 576: Computer Vision Adapted from slide by Matthew Brown
特征描述子的多尺度检测 : 特征描述子
特征描述子 基本想法 : Scale Invariant Feature Transform (SIFT) 在特征点周围取 16x16 图像窗口 ( 沿着特征点主方向 ) 计算每个像素点的梯度 去除弱梯度点 ( 即梯度模小于阈值的点 ) 将窗口分成 4 x 4 的子区域, 计算每个小区域内的梯度角度直方图 梯度方向直方图 Adapted from slide by David Lowe
特征描述子 Scale Invariant Feature Transform (SIFT) 16 个子窗口 * 8 方向 = 128 维向量 Adapted from slide by David Lowe
SIFT 的性质 : 对拍摄视角具有鲁棒性 对亮度变化具有鲁棒性 快速计算 SIFT 程序 : 特征描述子 http://people.csail.mit.edu/albert/ladypack/wiki/index.php/ Known_implementations_of_SIFT
目录 l 为什么要进行特征提取? l Harris 角点检测 l 尺度不变特征点检测器 l 特征描述子 l 特征点匹配
特征点匹配 给定图 I 1 中的特征点, 如何找到图 I 2 中的最优匹配点? 1. 定义特征点的描述子之间距离 2. 计算图 I 1 中的特征点描述子与图 I 2 中所有特征点之间的距离, 找到最小距离的特征点作为匹配点
特征点匹配 如何定义两个特征点 f 1, f 2 之间距离? 最简单的定义 :SSD(f 1, f 2 ) 两个特征描述子之间元素差的平方和 f 1 f 2 I 1 I 2
特征点匹配 如何定义两个特征点 f 1, f 2 之间距离? 更好的算法 : distance ratio= SSD(f 1, f 2 ) / SSD(f 1, f 2 ) f 2 是 I 2 中与 f 1 具有最小 SSD 距离的匹配点 f 2 是 I 2 中与 f 1 具有第二小 SSD 距离的匹配点 distance ratio 小于某阈值的匹配点认为是正确匹配点 f 1 f ' 2 f 2 I 1 I 2
特征点匹配 如何测度特征匹配的性能? 50 75 200 特征距离
特征点匹配 50 75 true match 200 false match 特征点匹配 取特征描述子距离的不同阈值会导致不同的匹配结果 True positives = 检测出的特征点对中正确的数量 False positives = 检测出的特征点对中错误的数量
特征点匹配 如何测度特征匹配的性能? 1 0.7 # true positives # matching features (positives) true positive rate 0 0.1 false positive rate 1 # false positives # unmatched features (negatives)
特征点匹配 1 ROC 曲线 ( Receiver Operator Characteristic ) 0.7 # true positives # matching features (positives) true positive rate ROC 曲线 0 0.1 false positive rate 1 # false positives # unmatched features (negatives) ROC 曲线下的面积 (AUC) 越大越好 For more info: http://en.wikipedia.org/wiki/receiver_operating_characteristic
应用实例 : 物体识别
应用实例 NASA Mars Rover images with SIFT feature matches Figure by Noah Snavely
作业 l 复习 SIFT 特征子, 并尝试 SIFT 特征子的程序 David G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110 尝试算法程序 : http://www.cs.ubc.ca/~lowe/keypoints/