基于图像的三维建模——特征点检测与匹配

点击上方“3D视觉工坊”，选择“星标”

干货第一时间送达

作者：梦寐mayshine

链接：https://zhuanlan.zhihu.com/p/128937547

本文转载自知乎，作者已授权，未经许可请勿二次转载。

特征点：检测子（给一副图像找到特征点的位置）+描述子（特征向量，用于特征匹配）

一、图像特征介绍

1、图像特征点的应用

• 相机标定：棋盘格角点阴影格式固定，不同视角检测到点可以得到匹配结果，标定相机内参

• 图像拼接：不同视角匹配恢复相机姿态

• 稠密重建：间接使用特征点作为种子点扩散匹配得到稠密点云

• 场景理解：词袋方法，特征点为中心生成关键词袋（关键特征）进行场景识别

2、图像特征点的检测方法

• 人工设计检测算法：sift、surf、orb、fast、hog

• 基于深度学习的方法：人脸关键点检测、3D match点云匹配

• 场景中的人工标记点：影视场景背景简单的标记，特殊二维码设计（快速，精度低）

3、图像特征点的基本要求

• 差异性：视觉上场景上比较显著点，灰度变化明显，边缘点等

• 重复性：同一个特征在不同视角中重复出现，旋转、光度、尺度不变性

二、特征检测子

1、Harris 角点检测（早期，原理简单，视频跟踪，快速检测）

https://zhuanlan.zhihu.com/p/90393907

动机：特征点具有局部差异性

• 以每个点为中心取一个窗口，例如，5×5/7×7的像素，描述特征点周围环境

• 此点具有差异性->窗口往任意方向移动，则周围环境变化较大->具有局部差异性

• 最小二乘线性系统

• 加和符号：表示窗口内每个像素

• w：表示权重，权值1或者以点为中心的高斯权重（离点越近权重越大）

• I：表示像素，RGB/灰度

• u，v：窗口移动的方向

• H：harris矩阵，由两个方向上的梯度构建而成

• 图像梯度：

• Harris矩阵：

Harris矩阵H 的特征值分析

• 两个特征值反映相互垂直方向上的变化情况，分别代表变化最快和最慢的方向，特征值大变化快，特征值小变化慢

• 

• λ1 ≈ λ2 ≈ 0， 两个方向上变化都很小，兴趣点位于光滑区域

• λ1 > 0 , λ2 ≈ 0 ，一个方向变化快，一个方向变化慢，兴趣点位于边缘区域

• λ1 , λ2 > 0 ， 两个方向变化都很快，兴趣点位于角点区域（容易判断）

• 反映特征值情况，trace为迹

• k的值越小，检测子越敏感

• 只有当λ1和λ2同时取得最大值时，C才能取得较大值

• 避免了特征值分解，提高检测计算效率

• 非极大值抑制(Non-maximal Suppression) 选取局部响应最大值，避免重复的检测

算法流程：

• 0）滤波、平滑，避免出现阶跃函数

• 1）计算图像水平和垂直方向的梯度

• 2）计算每个像素位置的Harris矩阵

• 3）计算每个像素位置的Harris角点响应值

• 3+）非极大值抑制

• 4）找到Harris角点响应值大于给定阈值且局部最大的位置作为特征点

检测结果：

2、基于LoG的多尺度特征检测子

• 动机：Harris角点检测不具有尺度不变性，让特征点具有尺度不变性

• 解决方法：尺度归一化LoG算子，处理尺度的变化

• LoG算子：Lindeberg(1993)提出Laplacian of Gaussian (LoG)函数的极值点对应着特征点

尺度空间：

• 一副图像使用不同大小滤波核滤波（e.g.高斯滤波），越大的滤波核越模糊，分辨率越小，不同滤波核滤波后的空间为尺度空间=3维空间（图像+尺度），模拟人类视觉，较远物体模糊，一系列滤波核构成的不同分辨率图像为尺度空间->LoG能够处理不同尺度的图像

• LoG算子^[1]形式：高斯滤波性质：卷积->求拉普拉斯算子==求拉普拉斯算子->卷积               其中 是LoG算子

• 尺度归一化LoG^[2]（使得具有可比性=汇率）：其中 是尺度归一化LoG算子

• 不同尺度下的LoG响应值不具有可比性

• 构建尺度空间，同时在位置空间和 尺度空间寻找归一化LoG极值(极大 /极小)点作为特征点

• 不同尺度下 的响应值

• LoG特征检测算法流程

• 1）计算不同尺度上的尺度归一化LoG函数值

• 2）同时在位置和尺度构成的三维空间上寻找 尺度归一化LoG的极值点

• 3）进行非极大值抑制，减少重复检测 （去除冗余、保持稳定性）

• 检测结果：效果好，LoG计算量大

3、基于DoG的多尺度特征检测子（SIFT）——稳定和鲁棒

• LoG可以由DoG近似：Lowe(2004)提出归一化LoG近似等价于相邻尺度的高斯差分(DoG)

• 高斯空间：

• 高斯差分DoG：相邻的空间做差，极点处对应特征点

• 尺度空间的构建

• • 高斯空间

  • 高斯差分

  • 有效差分 （尺度空间有上下两个邻域才行，边界无效）

  • 任意设置

  • • 阶数：O=3  （octave=阶，每阶图像尺寸减少一半,阶数高->运算量大->尺度变化大）

    • 每阶有效差分数：S=3（每个阶内划分数）

    • 每阶层数：N=S+3

• 特征点位置的确定：

• 1）尺度空间和图像空间上：3*3窗口，26个邻域，找极值点比其他都要大DoG，LoG找极大值或极小值

• 2）横轴向代表离散位置，纵轴代表DoG响应值，在极值点邻域内求二阶函数的极值=准确像素位置

• 亚像素特征点位置的确定

• • x： 为三维，坐标空间+尺度空间

  • f(x)： 为DoG值

  • x0： 检测到离散坐标下的极大值点

  • 任务：在x0附近近似一个二阶函数，求二阶函数极值得到更准确的亚像素极值位置

• 矩阵的表达-1阶

• 矩阵的表达-2阶

• 极值点有可能是边缘点，->除去边缘点：DoG在边缘处值较大，需要避免检测到边缘点

• 计算主方向：通过统计梯度直方图的方法确定主方向，使算法具有旋转不变性

• SIFT特征检测流程：旋转不变性、尺度不变性、亮度 变化不变性，对视角变化、仿射变换有一定程度的稳定性

• • 1）计算图像尺度空间：

  • 2）DoG极值点检测与定位：保留 的特征点

  • 3）边缘点去除： 

  • 4）计算主方向

  • 5）生成描述子

  • 6）检测结果

4、快速特征点检测方法：——实时性要求高

• FAST特征点^[3]：Feature from Accelerated Segment Test

• • 特性：通过检测局部像素灰度变化来确认特征点的位置，速度快，SIFT的100倍；不具有尺度和旋转不变性

  • 流程：

  • • 1）以候选点p为圆心构建一个离散圆

    • 2）比较圆周上的像素与p点像素值

    • 3）当有连续的n个像素值明显亮于或者暗于p时，p被检测为特征点，例Fast9,Fast12

  • 检测：

Oriented FAST (ORB)

• • 获取尺度不变性：构建图像金字塔，在金字塔 每一层上检测关键点

  • 获取旋转不变性 ：通过灰度质心法(Intensity Centroid) 确定图像主方向

  • 图像块B上的矩定义为：

  • 图像块B的质心定义为 ：

  • 计算方向角 ：

  • 检测结果：

三、特征描述子

特征描述子 Feature Descriptor

• 每个特征点独特的身份认证

• 同一空间点在不同视角的特征点具有高度相似的描述子

• 不同特征点的的描述子差异性尽量大

• 通常描述子是一个具有固定长度的向量

特征支持区域

• 主方向:进行旋转并重新插值

• 特征尺度:影响支持区域的大小

1、基于直方图的描述子

（1）用于微小运动的描述子 ^[4]（e.g.相邻两帧视频）

• 定义：以特征点为中心的矩形区域内所有像素的灰度值作为描述子

• 特性：适用于微小变化的图像对 图像存在明显的旋转、尺度、光照和透视变换时不稳定

（2）Sift描述子——旋转主方向

• 定义：根据主方向对支持区域进行旋转，并通过双线性插值重构

• 特性：图像归一化处理，去除光照变化

• 统计局部梯度信息流程：

• • 1）将区域划分成4x4的block ；

  • 2）每个block内统计梯度方向 的直方图(高斯加权梯度作为系数)

（2）Sift描述子——生成描述子

（2）Sift描述子——归一化处理

• 处理方式

• • 1）门限处理-直方图每个方向的梯度幅值不超过0.2

  • 2）描述子长度归一化

• 特性：归一化处理提升了特征点光度变化的不变性

• SIFT描述子变种：PCA-SIFT/SURF

（3）GLOH描述子^[5]：Gradient Location-orientation Histogram

• 一共有1+2x8=17 个blocks

• 每个blocks计算16个方向的直方图

• 描述子共16x17=272维

• 通过PCA可以降维到128

（4）DAISY描述子^[6]：每个圆的半径对应高斯的尺度

2、基于不变性的描述子

3、二进制描述子——BRIEF

• 描述子形式：描述向量由N个0或者1组成 N=128,256,512

• 描述子特性：生成速度快（汉明距离），匹配效率高 ，简单有效；不具有旋转不变性

• 描述子流程：

• • 1）图像进行如高斯滤波预处理——去除噪声

  • 2）在支持区域内随机采样N对大小5×5的patch

  • 3）比较patch内像素和的大小，并保留结果构成特征向量  p(x),p(y)是简历在x，y处的patch

四、特征匹配

计算两幅图像中特征描述子的匹配关系

1、距离度量

归一化互相关，1 ->非常匹配，0->不匹配

2、匹配策略

最近邻：加了距离约束，防止孤立点

3、高效匹配

4、特征匹配验证                

参考

1. T. Lindeberg. Detecting salient blob-like image structures and their scales with a scalespace primal sketch: A method for focus-of-attention. International Journal of Computer Vision, 11(3):283–318, Dec. 1993.

2. T. Lindeberg. Feature detection with automatic scale selection. International Journal of Computer Vision, 30(2):79–116, Nov. 1998.

3. E. Rosten and T. Drummond. Fusing points and lines for high performance tracking. In IEEE International Conference on Computer Vision (ICCV), 2005.

4. Scharstein, D. and Szeliski, R. (2002). A taxonomy and evaluation of dense two-framestereo correspondence algorithms. International Journal of Computer Vision, 47(1):7–42.

5. Mikolajczyk, K. and Schmid, C. (2005). A performance evaluation of local descriptors.IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10):1615–1630.

6. S. Winder and M. Brown. Learning local image descriptors. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2007.

推荐阅读：

吐血整理|3D视觉系统化学习路线

那些精贵的3D视觉系统学习资源总结（附书籍、网址与视频教程）

超全的3D视觉数据集汇总

大盘点|6D姿态估计算法汇总(上)

大盘点|6D姿态估计算法汇总（下）

机器人抓取汇总|涉及目标检测、分割、姿态识别、抓取点检测、路径规划

汇总|3D点云目标检测算法

汇总|3D人脸重建算法

那些年，我们一起刷过的计算机视觉比赛

总结|深度学习实现缺陷检测

深度学习在3-D环境重建中的应用

汇总|医学图像分析领域论文

大盘点|OCR算法汇总

重磅！3DCVer-学术论文写作投稿 交流群已成立

扫码添加小助手微信，可申请加入3D视觉工坊-学术论文写作与投稿 微信交流群，旨在交流顶会（ICRA/IROS/ROBIO/CVPR/ICCV/ECCV等）、顶刊（IJCV/TPAMI/TIP等）、SCI、EI等写作与投稿事宜。

同时也可申请加入我们的细分方向交流群，目前主要有3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流等微信群，请扫描下面微信号加群，备注：”研究方向+学校/公司+昵称“，例如：”3D视觉 + 上海交大 + 静静“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进去相关微信群。原创投稿也请联系。

▲长按加微信群或投稿

▲长按关注公众号

3D视觉从入门到精通知识星球：针对3D视觉领域的知识点汇总、入门进阶学习路线、最新paper分享、疑问解答四个方面进行深耕，更有各类大厂的算法工程人员进行技术指导。与此同时，星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息，打造成集技术与就业为一体的铁杆粉丝聚集区，近1000+星球成员为创造更好的AI世界共同进步，知识星球入口：

学习3D视觉核心技术，扫描查看介绍，3天内无条件退款

 圈里有高质量教程资料、可答疑解惑、助你高效解决问题