sift和meanshift原理和算法.doc

SIFT算法由D.G.Lowe 1999年提出，2004年完善总结，论文发表在2004年的IJCV上：David G. Lowe, Distinctive image features from scale-invariant keypoints, International Journal of Computer Vision, 60, 2 (2004), pp. 91-110后来Y.Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。SIFT方法一经推出就在图像处理界引起巨大反响，其方法效果良好、实现便捷，很快风靡世界。很多图像检测、识别的应用里都能找到sift方法的身影SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。算法的主要特点为：a) SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。 b) 独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配23。 c) 多量性，即使少数的几个物体也可以产生大量SIFT特征向量。 d) 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。 e) 可扩展性，可以很方便的与其他形式的特征向量进行联合。SIFT算法主要步骤：1）检测尺度空间极值点2）精确定位极值点3）为每个关键点指定方向参数4）关键点描述子的生成SIFT算法详细尺度空间理论目的是模拟图像数据的多尺度特征。 高斯卷积核是实现尺度变换的唯一线性核，于是一副二维图像的尺度空间定义为：L(x,y,e) = G(x,y,e)*I(x,y)其中G(x,y,e)是尺度可变高斯函数，G(x,y,e) = 1/2*pi*e2 * exp -(x2+ y2)/2e2 （x，y）是空间坐标， e是尺度坐标。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。D(x,y,e) = (G(x,y,ke) - G(x,y,e) * I(x,y) = L(x,y,ke) - L(x,y,e)DOG算子计算简单，是尺度归一化的LoG算子的近似。Gaussian卷积是有尺寸大小的，使用同一尺寸的滤波器对两幅包含有不同尺寸的同一物体的图像求局部最值将有可能出现一方求得最值而另一方却没 有的情况，但是容易知道假如物体的尺寸都一致的话它们的局部最值将会相 同。SIFT的精妙之处在于采用图像金字塔的方法解决这一问题，我们可以把两幅图像想象成是连续的，分别以它们作为底面作四棱锥，就像金字塔，那么每一个 截面与原图像相似，那么两个金字塔中必然会有包含大小一致的物体的无穷个截面，但应用只能是离散的，所以我们只能构造有限层，层数越多当然越好，但处理时 间会相应增加，层数太少不行，因为向下采样的截面中可能找不到尺寸大小一致的两个物体的图像。有了图像金字塔就可以对每一层求出局部最值，但是这样的稳定 点数目将会十分可观，所以需要使用某种方法抑制去除一部分点，但又使得同一尺度下的稳定点得以保存图像金字塔的构建：图像金字塔共O组，每组有S层，下一组的图像由上一组图像降采样得到。图1 Two octaves of a Gaussian scale-space image pyramid with s =2 intervals. The first image in the second octave is created by down sampling the second to last image in the previous图2 The difference of two adjacent intervals in the Gaussian scale-space pyramid create an interval in the difference-of-Gaussian pyramid (shown in green).空间极值点检测为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图3所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的92个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。构建尺度空间需确定的参数e 尺度空间坐标 O octave坐标 S sub-level 坐标注：octaves 的索引可能是负的。第一组索引常常设为0或者-1,当设为-1的时候，图像在计算高斯尺度空间前先扩大一倍。空间坐标x是组octave的函数，设 是0组的空间坐标，注：在Lowe的文章中，Lowe使用了如下的参数：在组o=-1，图像用双线性插值扩大一倍（对于扩大的图像 ）。精确确定极值点位置 通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。 边缘响应的去除一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个2x2 的Hessian矩阵H求出:导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令为最大特征值关键点方向分配 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。 在实际计算时，我 们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0360度，其中每10度一个柱，总共36个柱。直方图的 峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。图4是采用7个柱时使用梯度直方图为关键点确定主方向的示例。 图4 由梯度方向直方图确定主梯度方向 在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。一个关键点可能会被指定具有多个方向（一个主方向，一个以上辅方向），这可以增强匹配的鲁棒性53。 至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向。由此可以确定一个SIFT特征区域（在实验章节用椭圆或箭头表示）。陈运文特征点描述子生成 由关键点邻域梯度信息生成特征向量 接 下来以关键点为中心取88的窗口。图5-4左部分的中央黑点为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，箭头方向代表该像素的 梯度方向，箭头长度代表梯度模值，图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每44的小块上计算8个方向的梯 度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图5右部分所示。此图中一个关键点由22共4个种子点组成，每个种子点有8个方向向量 信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。 实际计算过程中，为了增强 匹配的稳健性，Lowe建议对每个关键点使用44共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的SIFT特征 向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。 当 两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其 与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈 值，SIFT匹配点数目会减少，但更加稳定。SIFT算法的实际匹配效果如下：记得刚读研究生的时候，学习的第一个算法就是meanshift算法，所以一直记忆犹新，今天和大家分享一下Meanshift算法，如有错误，请在线交流。Mean Shift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束.1. Meanshift推导给定d维空间Rd的n个样本点 ,i=1,n,在空间中任选一点x，那么Mean Shift向量的基本形式定义为:Sk是一个半径为h的高维球区域,满足以下关系的y点的集合,k表示在这n个样本点xi中,有k个点落入Sk区域中.以上是官方的说法，即书上的定义，我的理解就是，在d维空间中，任选一个点，然后以这个点为圆心，h为半径做一个高维球，因为有d维，d可能大于 2，所以是高维球。落在这个球内的所有点和圆心都会产生一个向量，向量是以圆心为起点落在球内的点位终点。然后把这些向量都相加。相加的结果就是 Meanshift向量。如图所以。其中黄色箭头就是Mh（meanshift向量）。再以meanshift向量的终点为圆心，再做一个高维的球。如下图所以，重复以上步骤，就可得到一个meanshift向量。如此重复下去，meanshift算法可以收敛到概率密度最大得地方。也就是最稠密的地方。最终的结果如下：Meanshift推导：把基本的meanshift向量加入核函数.那么，meanshift算法变形为 (1)解释一下K()核函数，h为半径，Ck,d/nhd 为单位密度，要使得上式f得到最大，最容易想到的就是对上式进行求导，的确meanshift就是对上式进行求导.(2)令：K(x)叫做g(x)的影子核，名字听上去听深奥的，也就是求导的负方向，那么上式可以表示对于上式，如果才用高斯核，那么，第一项就等于fh,k第二项就相当于一个meanshift向量的式子：那么（2）就可以表示为下图分析的构成，如图所以，可以很清晰的表达其构成。要使得=0，当且仅当=0，可以得出新的圆心坐标： （3）上面介绍了meanshift的流程，但是比较散，下面具体给出它的算法流程。1. 选择空间中x为圆心，以h为半径为半径，做一个高维球，落在所有球内的所有点xi2. 计算，如果, 则利用（3）计算x，返回1.2.meanshift在图像上的聚类：真正大牛的人就能创造算法，例如像meanshift，em这个样的算法，这样的创新才能推动整个学科的发展。还有的人就是把算法运用的实际的运用中，推动整个工业进步，也就是技术的进步。下面介绍meashift算法怎样运用到图像上的聚类核跟踪。一般一个图像就是个矩阵，像素点均匀的分布在图像上，就没有点的稠密性。所以怎样来定义点的概率密度，这才是最关键的。如果我们就算点x的概率密度，采用的方法如下：以x为圆心，以h为半径。落在球内的点位xi 定义二个模式规则。（1）x像素点的颜色与xi像素点颜色越相近，我们定义概率密度越高。（2）离x的位置越近的像素点xi，定义概率密度越高。所以定义总的概率密度，是二个规则概率密度乘积的结果，可以（4）表示（4）其中：代表空间位置的信息，离远点越近，其值就越大，表示颜色信息，颜色越相似，其值越大。如图左上角图片，按照（4）计算的概率密度如图右上。利用meanshift对其聚类，可得到左下角的图。 本文翻译自维基百科，英文原文地址是：/wiki/ransac，如果您英语不错，建议您直接查看原文。 RANSAC是“RANdom SAmple Consensus（随机抽样一致）”的缩写。它可以从一组包含“局外点”的观测数据集中，通过迭代方式估计数学模型的参数。它是一种不确定的算法它 有一定的概率得出一个合理的结果；为了提高概率必须提高迭代次数。该算法最早由Fischler和Bolles于1981年提出。 RANSAC的基本假设是：（1）数据由“局内点”组成，例如：数据的分布可以用一些模型参数来解释；（2）“局外点”是不能适应该模型的数据；（3）除此之外的数据属于噪声。 局外点产生的原因有：噪声的极值；错误的测量方法；对数据的错误假设。 RANSAC也做了以下假设：给定一组（通常很小的）局内点，存在一个可以估计模型参数的过程；而该模型能够解释或者适用于局内点。本文内容1 示例2 概述3 算法4 参数5 优点与缺点6 应用7 参考文献8 外部链接一、示例 一个简单的例子是从一组观测数据中找出合适的2维直线。假设观测数据中包含局内点和局外点，其中局内点近似的被直线所通过，而局外点远离于直线。简单的最 小二乘法不能找到适应于局内点的直线，原因是最小二乘法尽量去适应包括局外点在内的所有点。相反，RANSAC能得出一个仅仅用局内点计算出模型，并且概 率还足够高。但是，RANSAC并不能保证结果一定正确，为了保证算法有足够高的合理概率，我们必须小心的选择算法的参数。左图：包含很多局外点的数据集 右图：RANSAC找到的直线（局外点并不影响结果）二、概述 RANSAC算法的输入是一组观测数据，一个可以解释或者适应于观测数据的参数化模型，一些可信的参数。 RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证： 1.有一个模型适应于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。 2.用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。 3.如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。 4.然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。 5.最后，通过估计局内点与模型的错误率来评估模型。 这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用。三、算法 伪码形式的算法如下所示：输入：data 一组观测数据model 适应于数据的模型n 适用于模型的最少数据个数k 算法的迭代次数t 用于决定数据是否适应于模型的阀值d 判定模型是否适用于数据集的数据数目输出：best_model 跟数据最匹配的模型参数（如果没有找到好的模型，返回null）best_consensus_set 估计出模型的数据点best_error 跟数据相关的估计出的模型错误iterations = 0best_model = nullbest_consensus_set = nullbest_error = 无穷大while ( iterations k ) maybe_inliers = 从数据集中随机选择n个点 maybe_model = 适合于maybe_inliers的模型参数 consensus_set = maybe_inliers for ( 每个数据集中不属于maybe_inliers的点 ） if ( 如果点适合于maybe_model，且错误小于t ） 将点添加到consensus_set if （ consensus_set中的元素数目大于d ） 已经找到了好的模型，现在测试该模型到底有多好 better_model = 适合于consensus_set中所有点的模型参数 this_error = better_model究竟如何适合这些点的度量 if ( this_error best_error ) 我们发现了比以前好的模型，保存该模型直到更好的模型出现 best_model = better_model best_consensus_set = consensus_set best_error = this_error 增加迭代次数返回 best_model, best_consensus_set, best_error RANSAC算法的可能变化包括以下几种： （1）如果发现了一种足够好的模型（该模型有足够小的错误率），则跳出主循环。这样可能会节约计算额外参数的时间。 （2）直接从maybe_model计算this_error，而不从consensus_set重新估计模型。这样可能会节约比较两种模型错误的时间，但可能会对噪声更敏感。四、参数 我们不得不根据特定的问题和数据集通过实验来确定参数t和d。然而参数k（迭代次数）可以从理论结果推断。当我们从