[论文笔记] Randomized Trees for Real-Time Keypoint Recognition

Paper:V. Lepetit, P. Lagger, and P. Fua. Randomized Trees for Real-Time Keypoint Recognition. In Proceedings of the Conference on Computer Vision and Pattern Recognition, San Diego, CA, June 2005.


问题描述:文章是作者在前作基础上(04年ICCV)的完善之作,研究广泛意义上的特征点匹配问题,应用于相机定标、目标检测等各种领域。特征点匹配算法发展到现在,虽然对形状、视点、光照等变化及遮挡等逐渐变得鲁棒,但是没有算法引入过目标的三维信息和可能可以获得的训练图片等,匹配效果还有较大的提升空间。文章提出的算法引入了这些额外的信息,离线合成目标稳定特征点的各个视角,实时通过多类随机决策树将检测到的特征点分类(识别对应视角),最终使用RANSAC-method估计目标的3D姿态,达到匹配的目的。算法有效、实时、鲁棒。

训练数据的获取
对于立体目标,至少需要2张训练图片;对于平面目标,至少1张。对于目标的每一个特征点,生成其在各个视点下以其为中心的patch合集,如下图所示。假设目标是平面的,简单的仿射变换即可,定义缩放、选择、扭曲等参数,通过随机参数的方式生成样例;但对于立体的目标,至少需要2张不同视角的图片,用于重建目标的三维模型,再通过渲染技术生成样例(或者像google街景一样使用基于图像的渲染技术)。注:只适用于非凹体。所有的样本在训练之前还会进行高斯化、2D朝向估计与对齐的预处理,作为归一化的手段,使得分类更为容易。
2011-5-10 14-11-42

特征点的选择和识别
在众多样本及实时数据中,由于目标的扭曲、视点遮挡等原因,特征点并不一直保持统一。出于鲁棒性的考虑,需要选择其中最稳定的特征点,即在大多数视点下都能被检测到的特征点。另外,合成的样本图片被加入白噪声(接近真实的相机拍摄结果)和噪声背景,使得训练结果天然地对图像噪声鲁棒。
特征点的识别,文章中使用的多类随机决策树(或随机决策森林),相对于前作中的KNN算法更为高效,而且天然地适用于多类分类的问题。决策树节点的test使用简单的像素亮度对比。在实时识别中,图像的每个特征点patch的分类,由从每棵决策树获得的分类置信分布的平均值决定(取其最大者)。当置信值小于某一阈值时,认为该特征点不与任一目标特征点匹配。

结果
文章称,训练20棵10-depth的决策树森林,在普通PC上需要约15min,能够达到至少80%的识别率。实时的识别速度能够达到camera frame的速度,也就是约30fps。微软在kinect的核心算法中也借鉴了这篇文章的思路,并使用GPU加速识别过程,最后加上基于mean-shift的骨架生成,也是实时的速度,因此文章所称的实时效率是可信的。在效果上,文章对比了SIFT算法,称在高distort的情况下,SIFT只能检测到很少的匹配特征点,而此算法依旧;但在处理Scale情况时没有SIFT鲁棒,但这与算法框架本身无关,只是因为在选择特征点时没有使用多scale的特征。


文章的亮点在于其算法框架,即将特征点匹配问题转化为特征点的分类问题。其次,通过渲染技术生成特征点在各个视点下的Patch,也很有新意。是一种逆问题与正问题的结合思路。而且,此算法的效率也十分美。不过,相对于其他特征点匹配算法,需要训练,即是它的创新,也是它的弱点。毕竟,想要获得好的结果,一两张训练数据总是不太让人信任的;况且,需要训练的算法,其通用性往往受到制约,其易用性也自然比不上拈来即可用的算法。但不可否认,这是一个很有意思的算法。