图像特征提取 姜伟 智能系统与控制研究所
图像特征提取 特 征 点 Harris corners
图像特征提取 直线
图像特征提取 区域
图像特征提取 特征点的提取 Harris 角点检测算子 Sift 特征点检测 SURF 特征点检测 直线的提取 Canny 算子 区域的特征提取 MSER (Maximally stable extremal region)
特征点的提取 提取点特征的作用 图像的点特征是许多计算机视觉算法的基础 : 使用特征点来代表图像的内容 运动目标跟踪 物体识别 图像配准 全景图像拼接 三维重建
一类重要的点特征 : 角点 角点 (corner points): 局部窗口沿各方向移动, 均产生明显变化的点 图像局部曲线曲率突变的点 典型的角点检测算法 : Harris 角点检测 CSS 角点检测
不同类型的角点
什么是好的角点检测算法? 检测出图像中 真实的 角点 准确的定位性能 很高的重复检测率 ( 稳定性好 ) 具有对噪声的鲁棒性 具有较高的计算效率
Harris 角点检测 C.Harris, M. Stephens. A Combined Corner and Edge Detector. Proc of 4th Alvey Vision Conference, 1988. C.Harris was with The Plessey Company plc. U.K. in 1988.
Harris 角点检测基本思想 从图像局部的小窗口观察图像特征 角点定义 窗口向任意方向的移动都导致图像灰度的明显变化
Harris 角点检测基本思想 平坦区域 : 任意方向移动, 无灰度变化 边缘 : 沿着边缘方向移动, 无灰度变化 角点 : 沿任意方向移动, 明显灰度变化
Harris 检测 : 数学表达 将图像窗口平移 [u,v] 产生灰度变化 E(u,v) 窗口函数 平移后的图像灰度 图像灰度 窗口函数 w(x,y) = 或 1 in window, 0 outside Gaussian
Harris 检测 : 数学表达 2 2 2 2 2 2 I v I uv I I u I v I u y y x x y x v u I I I I I I v u y y x y x x 2 2 由 : 得 :
Harris 检测 : 数学表达 于是对于局部微小的移动量 [u,v], 可以近似得到下面的表达 : 其中 M 是 2 2 矩阵, 可由图像的导数求得 :
Harris 检测 : 数学表达 窗口移动导致的图像变化 : 实对称矩阵 M 的特征值分析 max, min M 的特征值 E(u,v) 的椭圆形式 快速变化的方向 缓慢变化的方向 ( max ) -1/2 ( min) -1/2
Harris 检测 : 数学表达 通过 M 的两个特征值的大小对图像点进行分类 : 2 Edge 2 >> 1 Corner 1 和 2 都较大且数值相当 1 ~ 2 ; 图像窗口在所有方向上移动都产生明显灰度变化 如果 1 和 2 都很小, 图像窗口在所有方向上移动都无明显灰度变化 Flat region Edge 1 >> 2 1
Harris 检测 : 数学表达 定义 : 角点响应函数 R (k empirical constant, k = 0.04-0.06) k = 0.04
R 的等高线图 (k=0.2)
R 的等高线图 (k=0.1)
R 的等高线图 (k=0.05)
Harris 检测 : 数学表达 2 Edge R < 0 Corner R > 0 R 只与 M 的特征值有关 角点 :R 为大数值正数 边缘 :R 为大数值负数 平坦区 :R 为小数值 Flat R small Edge R < 0 1
Harris 角点检测 算法 : 对角点响应函数 R 进行阈值处理 : R > threshold 提取 R 的局部极大值
Harris 角点检测 : 流程
Harris 角点检测 : 流程角点响应函数 R
提取 R 的局部极值 Harris 角点检测 : 流程
Harris 角点检测 : 流程
Harris 角点检测 : 小结 沿方向 [u,v] 的平均灰度变化可以表达成双线性形式 : 使用 M 的特征值表达图像点局部灰度变化的情况, 定义角点响应函数 : 一个好的角点沿着任意方向移动都将导致明显的图像灰度变化, 即 :R 具有大的正数值
Harris 角点的性质 旋转不变性 : 椭圆转过一定角度但是其形状保持不变 ( 特征值保持不变 ) 角点响应函数 R 对于图像的旋转具有不变性
Harris 角点的性质 对于图像灰度的仿射变化具有部分的不变性 只使用了图像导数 => 对于灰度平移变化不变 I I + b 对于图像灰度的尺度变化 : I a I 阈值 R R x (image coordinate) x (image coordinate)
Harris 角点的性质 对于图像几何尺度变化不具有不变性 : 图像缩小 这几个点被分类为边缘点角点!
Harris 角点的性质 随尺度变化,Harris 角点检测的性能下降 Repeatability rate: # correspondences # possible correspondences C.Schmid et.al. Evaluation of Interest Point Detectors. IJCV 2000
SIFT 特征点检测 David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, Vol. 60, Page 91-110, Nov 2004. (1997-) Professor of Computer Science, University of British Columbia
几何变化 旋转 图像变化的类型 : 相似 ( 旋转 + 各向相同的尺度缩放 ) 仿射 ( 非各向相同的尺度缩放 ) 适用于 : 物体局部为平面 灰度变化 仿射灰度变化 (I a I + b)
SIFT SIFT - Scale Invariant Feature Transform 一种特征提取算法 (Lowe 1999, 2004) DoG 特征检测 + SIFT 描述子 SIFT 描述子性能评价最佳 (Mikolajczyk&Schmid, 2005) 迄今使用最为广泛的一种特征
SIFT 特征的性质 不变性 对图像的旋转和尺度变化具有不变性 对三维视角变化和光照变化具有很强的适应性 局部特征, 在遮挡和场景杂乱时仍保持不变性 辨别力强 特征之间相互区分的能力强, 有利于匹配 数量多 一般 500 500 的图像能提取出约 2000 个特征点 扩展性强
SIFT 特征提取算法流程 输入图像 多尺度空间极值点检测 关键点的精确定位 SIFT 算法在 DoG 尺度空间中提取极值点并进行优化从而获取特征点 关键点的主方向计算 描述子的构造 特征向量
尺度空间的定义 目的 : 检测在尺度变化时仍然稳定的特征 定义图像的尺度空间 : 其中 : 尺度参数, 当连续变化, 构成图像的尺度空间
图像尺度空间
高斯差分尺度空间 为了在尺度空间中检测稳定的关键点, 构造高斯差分尺度空间 高斯差分尺度空间 ( 高斯差分 DoG: Difference of Gaussian) 几个理由 : (1) 计算效率高 : 高斯卷积, 减法 (2) 高斯差分是对尺度归一化 LoG 的一个很好的近似, 而尺度归一化的 LoG 空间具有真正的尺度不变性 (Lindegerg 1994) (3) 实验比较表明, 从尺度归一化 LoG 空间中提取的图像特征的尺度稳定性最好, 优于梯度 Hessian 或 Harris 角点函数
高斯差分尺度空间
DoG 尺度空间极值点检测 建立的三维尺度空间形式 极值点检测 : 在三维尺度空间 中, 搜索每个点的 26 邻域, 若该点为局部极值点, 则保存为候选关键点
关键点的精确定位 三元二次函数拟合 改变关键点的初始位置 x, 重复计算精细偏移量 T 2 D 1 T D D(x) D x x x 2 x 2 x 计算精细偏移量 ˆx 2 D 2 x 1 D x x ˆ ( ˆ xy, ˆ, ˆ) T 若中的三个变量任意一个偏移量大于 0.5 ( 精确极值点更接近于另一个邻点 )
H 去除对比度低的点 去除不稳定的关键点 D(x) ˆ 1 D 2 x 去除边缘上的点利用 Hessian 矩阵 H 判断关键点是否位于边缘 D D xx xy D D xy yy 设定阈值 设两个特征值之间的比值为 r: D D(x) ˆ 0.03 Tr ( H) ( + ) ( r + ) ( r 1) (10 1) Det( H) r r 10 2 2 2 2 2 1 2 2 2 1 2 2 2 H 的两个特征值对应两个方向上的主曲率大小 在边缘位置, 两个特征值的比值大于阈值 r 1 2 通过计算 H 的迹和行列式避免直接求特征值, 减少了计算量. T xˆ
SIFT 描述子的构造 三维直方图的计算 将关键点邻域划分为 4 4 个子区域 梯度方向划分为 8 个方向 直方图的值为梯度幅值的累加 得到一个 4 4 8=128 维向量 主方向
直方图 (Histogram) 直方图表示的是图像中每一灰度之间的统计关系, 用横坐标表示灰度级, 纵坐标表示频数 原始定义 推广 一般意义
特征点主方向 以特征点 X 为中心的圆形邻域 梯度 梯度幅角
主方向的运算 分圆周为角度区间 统计梯度幅值和 抛物线插值 精确定位主方向
主方向校正 主方向
SIFT 描述子的构造 主方向
梯度幅值的插值运算 l 2 2 1 l l 1 1
SIFT 描述子的特点 SIFT 描述子的特点 直方图统计 : 提高了对图像局部形变的适应能力 子区域划分 : 弥补了丢失的位置信息, 增强辨别力 16 16 的邻域和 4 4 的子区域都进行了类似于高斯函数的加权处理, 强化中心区域, 淡化边缘区域的影响
描述子的不变性 尺度不变 根据关键点的尺度选取高斯图像和邻域大小 旋转不变 将邻域内每点的位置和梯度方向根据关键点的主方向进行旋转 适应复杂几何变形 采用分块直方图统计 高斯加权等细节处理 适应复杂光照变化 线性光照 : 归一化 128 维向量 非线性光照 : 将 128 维中所有大于 0.2 的元素赋值为 0.2
SIFT 特征匹配 匹配准则 NNDR (Nearest Neighbor Distance Ratio) 搜索策略 BBF 算法 (Best Bin First ) (Beis&Lowe, 1997)
例子 原始图像大小 233*189 像素 多尺度 DoG 空间中的极值点 832 个
例子 对比度阈值处理 832 729 去除边缘上的点 729 536
SIFT 点 - 视角和旋转变化 视角变化 旋转 + 尺度变化
SIFT 点 - 光照和尺度变化 光照变化 尺度变化
SURF: Speeded-Up Robust Features ECCV2006,CVIU2008 Herbert Bay a, Andreas Ess a, Tinne Tuytellares b, Luc Van Gool a,b a ETH Zurich b Katholieke Unviersiteit Leuven ( 苏黎世理工学院 ) ( 鲁汶大学 ) Switzerland Belgium 77
提纲 SURF 特点 SURF 检测 SURF 描述 实验及实验结果 结论 78
SURF 实现的主要方法 Detector: 积分图像 (Integral Images) 基于 Hessian Matrix 的兴趣点检测尺度空间表示兴趣点定位 Descriptor: 指定方向 基于 Haar 小波响应和的描述子计算 描述子的快速索引匹配 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 79
Detection_ 积分图像 (Integral Images) Second order derivative and Haar-wavelet response Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 80
Detection_ Fast-Hessian Detector Hessian 矩阵 : H( x, ) L L xx xy ( x, ) ( x, ) L L xy yy ( x, ) ( x, ) L xx ( x, ) 是图像和二阶高斯差分 g( ) 22 的卷积, 即图像的 x 多尺度 Gaussian Laplacian 结果 本文不认为 Lindeberg 高斯尺度空间理论在任何情况下都完全正确, 并认为其可以进行简化, 本文采用了 box filters 简化代替 LOG 即 Dxx 近似 Lxx 9 9 的 box filters 近似 Gaussian 在的二阶差分, 并作为最小尺度 ( 最高分辨率 ) Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 81
Detection_ Fast-Hessian Detector D yy D xy 能量转换 : Blob 响应 det( H approx ) D xx D yy (0.9D xy 2 ) Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 82
Detection_ 尺度空间表示 传统描述子 (SIFT) 尺度空间保持 filter 不变, 依赖上层结果, 改变图像大小 SURF 保持图像大小不变, 改变 filter 的尺度大小, 提高速度和精度 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 83
Detection_ 尺度空间表示 24*2=48 12*2=24 6*2=12 6 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 84
Detection_ 兴趣点定位 Steps: 1. 设置阈值, 确定候选兴趣点 2. 非极大抑制 3. 内插子像素精确定位 拟合 3D 二次曲线内插得到 x,y 和 σ 子像素精确定位非极大抑制 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 85
Description _ 指定方向 可多能少是 sliding windows? 6 个 文章没有说, x response y response 兴趣点周围的 6s 半径圆范围的采样点 (s = the scale at which the point was detected) Side length = 4s 采用积分图像,6 次模版滤波操作可完成响应的计算 ( 利用积分图像进行加减运算 ) Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 86
Description _ 指定方向 响应以兴趣点为中心进行高斯加权 (2.5s) Haar 小波响应以矢量形式表示 在 / 3 范围的滑动窗口内计算响应的和 水平方向和垂直方向分别求和, 两个响应和产生一个新的矢量 最长矢量对应的扇形方向作为兴趣点的主方向 Upright SURF(U-SURF) 不用计算主方向, 在旋转角在 +/-15 o 鲁棒 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 87
Description _ 描述子计算 1. 确定兴趣区域 (20s x 20s), 并切分为 4 4 的方形区域 2. 由指定的主方向, 在 5 5 采样点上计算 Harr 小波响应 dx 和 dy 3. 对响应 dx 和 dy 进行高斯加权 ( 以兴趣点为中心, ) 3.3s 4. 分别对子区域的 dx,dy, dx, dy 响应求和 5. 归一化为单位向量 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 88
Description _ 描述子计算 向量长度 :4 4 4=64, 以该向量作为 SURF 描述子, 对旋转, 尺度, 亮度和对比度变化具有不变性 SURF-36:3 3 子区域,distinctive 差, 匹配速度快 SURF-128: 在 dy>0 和 dy<0 情况下分别计算 dx dx dy dy 同样分两种情况计算, 这样得到 128 维矢量,distinctive 强, 匹配速度慢 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 89
Description _ 快速索引匹配 利用 Laplacian 的符号信息, 可以进行快速索引匹配 利用 Hessian 矩阵 trace( 反映了对比类型 ) 的符号 Trace = Lxx + Lyy 匹配相同 trace 符号的描述子, 提高速度 Detector: 积分图像 Fast-Hessian 尺度空间 兴趣点定位 Descriptor: 主方向 描述子计算 快速索引匹配 90
实验及实验结果 ( 时间比较 ) 数据 :http://www.robots.ox.ac.uk/~vgg/research/affine/ 91
实验及实验结果 (Detector 性能比较 ) Walls, viewpoint change Graffiti, viewpoint change Leuven, brightness change Boat, zoom and rotation 92
实验及实验结果 (descriptor 性能比较 ) Walls, viewpoint change of 50 degrees Boat, scale factor 2 Bikes, image blur Trees, image blur Leuven, brightness change Ubc, JPEG compression 93
结论 SURF 速度快, 较 SIFT 速度检测和匹配, 有 3 倍速度提高, 性能和 SIFT 大体相当 SURF 在图像模糊和旋转不变上优于 SIFT SURF 在图像视点变化和光照变化上略差于 SIFT 94
区域特征提取, MSER J.Matas. Robust Wide Baseline Stereo from Maximally Stable Extremal Regions,BMVC2002 Faculty of Electrical Engineering, Czech Technical University, Prague.
使用区域特征表达图像的内容
应用 : 视角差异导致的几何形变 大视角下的图像特征匹配问题 : 同一场景中相同的物体内容, 在大视角拍摄条件下, 发生明显的几何形变 相同形状的窗口不能代表同样的场景内容! 随视角变化的椭圆区域可以包含相同的图像内容 使用区域来代表图像内容
介绍 : 仿射不变区域特征 仿射不变区域特征 : 可以处理图像之间的仿射形变 形状不确定, 相同物体的特征区域随视角变化而变化 特征区域可以在不同视角和光照下被稳定地检测到 前提条件 场景中物体局部表面可以近似为平面 透视产生的形变可以忽略 区域特征之间的几何形变可以近似为 仿射变换
一种区域特征提取方法 MSER MSER = Maximally Stable Extremal Regions 目前业界认为是性能最好的仿射不变区域 MSER 是当使用不同的灰度阈值对图像进行二值化时得到的最稳定的区域 对于图像灰度的仿射变化具有不变性 稳定性, 区域的支持集相对灰度变化稳定 可以检测不同精细程度的区域
MSER 提取过程 使用一系列灰度阈值对图像进行二值化处理 对于每个阈值得到的二值图像, 得到相应的黑色区域与白色区域 在比较宽的灰度阈值范围内保持形状稳定的区域就是 MSERs 评判标准 : da/dt A: 二值图像区域面积,t: 灰度阈值
MSER Maximally Stable Extremal Regions 提取极值区域 提取最稳定极值区域 使用椭圆形来近似图像区域 J.Matas. Robust Wide Baseline Stereo from Maximally Stable Extremal Regions,BMVC2002
MSER 例子 原始图像暗区 MSER(112 个 ) 亮区 MSER(105 个 )
MSER 椭圆表达 使用一个椭圆形代表 MSER 区域 可以将这个椭圆形进行归一化, 使用圆形的区域进行表达 可以在圆形区域内使用 SIFT 描述子进行描述
构造仿射不变性区域 待匹配的图像 分别提取仿射不变区域 用椭圆代表区域的形状 将椭圆归一化为单位圆 旋转对齐主方向, 灰度归一化
参考资料 : J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust Wide baseline Stereo from Maximally Stable Extremal Regions. In Proc. of the British Machine Vision Conference, vol. 1, pages 384 393, 2002. K.Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir, L. Van Gool. A Comparison of Affine Region Detectors, IJCV2005.