Sift算法
Sfit算法的实质是在不同的尺度空间上查找关键点（特征点），计算关键点的大小、方向、尺度信息，利用这些信息组成关键点对特征点进行描述的问题。Sift所查找的关键点都是一些十分突出，不会因光照，仿射便函和噪声等因素而变换的“稳定”特征点，如角点、边缘点、暗区的亮点以及亮区的暗点等。匹配的过程就是对比这些特征点的过程，这个流程可以用下图表述：


Sfit特征提取和匹配具体步骤


生成高斯差分金字塔（DOG金字塔），尺度空间构建


空间极值点检测（关键点的初步查探）


稳定关键点的精确定位


稳定关键点方向信息分配


关键点描述


特征点匹配


1. 生成高斯差分金字塔（DOG金字塔），尺度空间构建
主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测不同分辨率上的关键点提取等。
各尺度下图像的模糊度逐渐变大，能够模拟人在距离目标由近到远时目标物体在视网膜上的形成过程。
尺度空间构建的基础是DOG金字塔，DOG金字塔构建的基础是高斯金字塔




【1】 图像金字塔

图像金字塔是一种以多分辨率来解释图像的结构，通过对原始图像进行多尺度像素采样的方式，生成N个不同分辨率的图像。把具有最高级别分辨率的图像放在底部，以金字塔形状排列，往上是一系列像素（尺寸）逐渐降低的图像，一直到金字塔的顶部只包含一个像素点的图像，这就构成了传统意义上的图像金字塔。



获得图像金字塔一般包括二个步骤：


利用低通滤波器平滑图像


对平滑图像进行抽样（采样）


有两种采样方式——上采样（分辨率逐级升高）和下采样（分辨率逐级降低）

上采样：



下采样：


【2】高斯金字塔

高斯金字塔式在Sift算子中提出来的概念，首先高斯金字塔并不是一个金字塔，而是有很多组（Octave）金字塔构成，并且每组金字塔都包含若干层（Interval）。
高斯金字塔构建过程：


先将原图像扩大一倍之后作为高斯金字塔的第1组第1层，将第1组第1层图像经高斯卷积（其实就是高斯平滑或称高斯滤波）之后作为第1组金字塔的第2层，高斯卷积函数为：



对于参数σ，在Sift算子中取的是固定值1.6。


将σ乘以一个比例系数k,等到一个新的平滑因子σ=k*σ，用它来平滑第1组第2层图像，结果图像作为第3层。


如此这般重复，最后得到L层图像，在同一组中，每一层图像的尺寸都是一样的，只是平滑系数不一样。它们对应的平滑系数分别为：0，σ，kσ，k2σ,k3σ……k^(L-2)σ。


将第1组倒数第三层图像作比例因子为2的降采样，得到的图像作为第2组的第1层，然后对第2组的第1层图像做平滑因子为σ的高斯平滑，得到第2组的第2层，就像步骤2中一样，如此得到第2组的L层图像，同组内它们的尺寸是一样的，对应的平滑系数分别为：0，σ，kσ，k2σ,k3σ……k^(L-2)σ。但是在尺寸方面第2组是第1组图像的一半。


这样反复执行，就可以得到一共O组，每组L层，共计O*L个图像，这些图像一起就构成了高斯金字塔，结构如下：



在同一组内，不同层图像的尺寸是一样的，后一层图像的高斯平滑因子σ是前一层图像平滑因子的k倍；
在不同组内，后一组第一个图像是前一组倒数第三个图像的二分之一采样，图像大小是前一组的一半；

高斯金字塔图像效果如下，分别是第1组的4层和第2组的4层：



【3】尺度空间

图像的尺度空间解决的问题是如何对图像在所有尺度下描述的问题。
在高斯金字塔中一共生成O组L层不同尺度的图像，这两个量合起来（O，L）就构成了高斯金字塔的尺度空间，也就是说以高斯金字塔的组O作为二维坐标系的一个坐标，不同层L作为另一个坐标，则给定的一组坐标（O,L）就可以唯一确定高斯金字塔中的一幅图像。
尺度空间的形象表述：



上图中尺度空间中k前的系数n表示的是第一组图像尺寸是当前组图像尺寸的n倍。
【4】DOG金字塔

差分金字塔，DOG（Difference of Gaussian）金字塔是在高斯金字塔的基础上构建起来的，其实生成高斯金字塔的目的就是为了构建DOG金字塔。
DOG金字塔的第1组第1层是由高斯金字塔的第1组第2层减第1组第1层得到的。以此类推，逐组逐层生成每一个差分图像，所有差分图像构成差分金字塔。概括为DOG金字塔的第o组第l层图像是有高斯金字塔的第o组第l+1层减第o组第l层得到的。

DOG金字塔的构建可以用下图描述：



每一组在层数上，DOG金字塔比高斯金字塔少一层。后续Sift特征点的提取都是在DOG金字塔上进行的。

DOG金字塔的显示效果如下：



这些长得黑乎乎的图像就是差分金字塔的实际显示效果，只在第1组第1层差分图像上模糊可以看到一个轮廓。但其实这里边包含了大量特征点信息，只是我们人眼已经分辨不出来了。
下边对这些DOG图像进行归一化，可有很明显的看到差分图像所蕴含的特征，并且有一些特征是在不同模糊程度、不同尺度下都存在的，这些特征正是Sift所要提取的“稳定”特征：


2. 空间极值点检测（关键点的初步查探）
为了寻找DOG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度空间域的相邻点大或者小，如下图所示：



在二维图像空间，中心点与它33邻域内的8个点做比较，在同一组内的尺度空间上，中心点和上下相邻的两层图像的29个点作比较，如此可以保证检测到的关键点在尺度空间和二维图像空间上都是局部极值点。
3.稳定关键点的精确定位
DOG值对噪声和边缘比较敏感，所以在第2步的尺度空间中检测到的局部极值点还要经过进一步的筛选，去除不稳定和错误检测出的极值点，另一点就是在构建高斯金字塔过程中采用了下采样的图像，在下采样图像中提取的极值点对应在原始图像中的确切位置，也是要在本步骤中解决的问题。
4. 稳定关键点方向信息分配
稳定的极值点是在不同尺度空间下提取的，这保证了关键点的尺度不变性。为关键点分配方向信息所要解决的问题是使得关键点对图像角度和旋转具有不变性。方向的分配是通过求每个极值点的梯度来实现的。
对于任一关键点，其梯度幅值表述为：



梯度方向为：



分配给关键点的方向并不直接是关键点的梯度方向，而是按照一种梯度方向直方图的方式给出的。
具体的方法是：计算以关键点为中心的邻域内所有点的梯度方向，当然梯度方向一定是在0~360°范围内，对这些梯度方向归一化到36个方向内，每个方向代表了10°的范围。然后累计落到每个方向内的关键点个数，以此生成梯度方向直方图。


将梯度方向直方图中纵坐标最大的项代表的方向分配给当前关键点作为主方向，若在梯度直方图中存在一个相当于主峰值80%能量的峰值，则将这个方向认为是关键点的辅方向。辅方向的设计可以增强匹配的鲁棒性，Lowe指出，大概有15%的关键点具有辅方向，而恰恰是这15%的关键点对稳定匹配起到关键作用。
5. 关键点描述
对关键点的描述是后续实现匹配的关键步骤，描述其实就是一种以数学方式定义关键的过程。描述子不但包含关键点，也包括关键点周围对其有贡献的邻域点。
描述的思路是：对关键点周围像素区域分块，计算快内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象表述。
如下图，对于22块，每块的所有像素点的荼毒做高斯加权，每块最终取8个方向，即可以生成228维度的向量，以这228维向量作为中心关键点的数学描述。



David G.Lowed的实验结果表明：对每个关键点，采用44*8共128维向量的描述子进项关键点表征，综合效果最佳：


6. 特征点匹配
特征点的匹配是通过计算两组特征点的128维的关键点的欧式距离实现的。欧式距离越小，则相似度越高，当欧式距离小于设定的阈值时，可以判定为匹配成功。

Sift特征匹配效果：

数据分析的具体步骤
1）从数据仓库导数据进入宽表：宽表就是字段比较多的数据库表
2）数据分层抽样：需要保证分层出来的样本比例同原始数据基本一致
3）数据类型选择：连续型还是离散型
4）缺失值处理
5）异常值处理：第一个异常值为无效异常值，但是第二个异常值可能属于有效异常值
6）自变量分类
7）强相关变量：聪明变量

1）从数据仓库导数据进入宽表：宽表就是字段比较多的数据库表
2）数据分层抽样：需要保证分层出来的样本比例同原始数据基本一致
3）数据类型选择：连续型还是离散型

连续变量：用于业务收入趋势分析、销售额预测分析、RFM分析
离散变量：信用评级、分类预测

4）缺失值处理
5）异常值处理：第一个异常值为无效异常值，但是第二个异常值可能属于有效异常值
6）自变量分类
7）强相关变量：聪明变量

有意义的变量不会超过10-15个
信息差IV值大于0.3代表变量的预测力较强

抽样步骤

定义目标群体：明确调查的全部对象及其范围。
	
定义抽样框：抽样框又称“抽样框架”、“抽样结构”，是指对可以选择作为样本的总体单位列出名册或排序编号，以确定总体的抽样范围和结构。
	
选择抽样方法：确定抽样测算所使用的抽样方法。
	
确定样本数量：确定抽样测算需要的样本数量，样本数越大精确度越高。
	
收集数据：从抽取的样本中收取测算数据。
已美国大选民意调查为例
仅考虑18岁以上且有资格投票的人。
	
抽样框是每一个选区的所有投票人列表。
	
选择使用概率抽样方法，因为每一张选票都是等价的，还可以将不同背景的人进行分层，使用分层抽样。
	
样本数为选区人口1%
	
通过电话访问样本人员，通过提问获取投票意向。
概率抽样

概率抽样是指在调查总体样本中的每个单位都具有同等可能性被抽中的机会。又称随机抽样，概率抽样以概率理论和随机原则为依据来抽取样本的抽样，是使总体中的每一个单位都有一个事先已知的非零概率被抽中的抽样。总体单位被抽中的概率可以通过样本设计来规定，通过某种随机化操作来实现，虽然随机样本一般不会与总体完全一致。

简单随机抽样/单纯随机抽样/纯随机抽样/SRS抽样

概念：简单随机抽样也称为单纯随机抽样、纯随机抽样、SRS抽样 ，是指从总体N个单位中任意抽取n个单位作为样本，使每个可能的样本被抽中的概率相等的一种抽样方式。

例子：从投票人列表中根据随机数抽取样本。

优点：简单，直接。

缺点：结果不确定性太强，每次结果可能不一样。

蒙特卡罗方法采用重复随机抽样的方法对未知参数进行估计。

分层抽样/类型抽样

概念：分层抽样法也叫类型抽样法。它是从一个可以分成不同子总体（或称为层）的总体中，按规定的比例从不同层中随机抽取样品（个体）的方法。

例子：

优点：样本的代表性比较好，抽样误差比较小。

缺点：抽样手续较简单随机抽样还要繁杂些

定量调查中的分层抽样是一种卓越的概率抽样方式，在调查中经常被使用。

聚类抽样/整群抽样

聚类取样（Cluster Sampling）又称整群抽样。是将总体中各单位归并成若干个互不交叉、互不重复的集合，称之为群；然后以群为抽样单位抽取样本的一种抽样方式。应用整群抽样时，要求各群有较好的代表性，即群内各单位的差异要大，群间差异要小。

在上面的例子中，我们将人口分为5个群。每个群由4个个体组成，我们在样本中选取了第4个群。我们可以根据样本大小包含更多的群。

当我们集中在一个特定领域或区域时，就会使用这种类型的抽样。

系统抽样/等距抽样/机械抽样

先将总体的全部单元按照一定顺序排列，采用简单随机抽样抽取第一个样本单元(或称为随机起点)，再顺序抽取其余的样本单元，这类抽样方法被称为等距抽样(Systematic Sampling)。等距抽样又称为机械抽样、系统抽样。等距抽样往往不能给出估计量的估计方差。

在这种类型的抽样中，第一个个体是随机选择的，其他个体是使用固定的“抽样间隔”选择的。让我们举一个简单的例子来理解这一点。

系统抽样比简单随机抽样更方便。然而，如果我们在人群中选择项目时存在一种潜在的模式，这也可能导致偏差(尽管这种情况发生的几率非常低)。

非概率抽样

非概率抽样是指调查者根据自己的方便或主观判断抽取样本的方法。它不是严格按随机抽样原则来抽取样本，所以失去了大数定律的存在基础，也就无法确定抽样误差,无法正确地说明样本的统计值在多大程度上适合于总体。虽然根据样本调查的结果也可在一定程度上说明总体的性质，特征，但不能从数量上推断总体。非概率抽样主要有偶遇抽样,主观抽样，定额抽样,滚雪球抽样等

1.随意抽样/便利抽样

方便抽样又称随意抽样、偶遇抽样，是一种为配合研究主题而由调查者于特定的时间和特定社区的某一位置上，随意选择回答者的非概率抽样方法。这种抽样方法适合于对一些特殊情况的调查，像一些时过境迁的突发性事件或现象(违章驾车、骚乱、聚众闹事等等)。通过在当场抽取样本询问当事者、目击者、旁观者以及过往的行人，可以了解事件发生的经过、原因以及对事件的看法和态度。

这里，假设编号为4、7、12、15和20的个体想要成为样本的一部分，因此，我们将把它们包含在样本中。

便利抽样容易产生显著的偏见，因为抽样可能不能代表诸如宗教或人口的性别等具体特征。

2.判断抽样/立意抽样

立意抽样是指当调查人员对自己的研究领域十分熟悉，对调查总体比较了解时采用这种抽样方法，可获代表性较高的样本。这种抽样方法多应用于总体小而内部差异大的情况，以及在总体边界无法确定或因研究者的时间与人力、物力有限时采用。例如，要对福建省旅游市场状况进行调查，有关部门选择厦门、武夷山、泰宁金湖等旅游风景区做为样本调查，这就是立意抽样。

假设，我们的专家认为，应该将编号为1、7、10、15和19的人作为我们的样本，因为它们可以帮助我们更好地推断人口。你可以想象，配额抽样同样也容易受到专家的偏见，不一定具有代表性。

3.配额抽样/定额抽样

配额抽样也称“定额抽样”，是指调查人员将调查总体样本按一定标志分类或分层，确定各类（层）单位的样本数额，在配额内任意抽选样本的抽样方式。

配额抽样和分层随机抽样既有相似之处，也有很大区别。配额抽样和分层随机抽样有相似的地方，都是事先对总体中所有单位按其属性、特征分类，这些属性、特征我们称之为“控制特性。”例如市场调查中消费者的性别、年龄、收入、职业、文化程度等等。然后，按各个控制特性，分配样本数额。但它与分层抽样又有区别，分层抽样是按随机原则在层内抽选样本，而配额抽样则是由调查人员在配额内主观判断选定样本。

在这种抽样中，我们根据预先确定的总体特征来选择样本。考虑到我们必须为我们的样本我们选择一个倍数为4的个体:

因此，编号为4、8、12、16和20的个人已经为我们的样本保留。

在配额抽样中，选择的样本可能不是未考虑的人口特征的最佳代表。

4.滚雪球抽样

滚雪球抽样是指先随机选择一些被访者并对其实施访问，再请他们提供另外一些属于所研究目标总体的调查对象，根据所形成的线索选择此后的调查对象。滚雪球抽样往往用于对稀少群体的调查。在滚雪球抽样中，首先选择一组调查单位，对其实施调查之后，再请他们提供另外一些属于研究总体的调查对象，调查人员根据所提供的线索，进行此后的调查。

在这里，我们随机选择了1个人作为样本，然后他推荐了6个人，6个人推荐了11个人，依此类推。

雪球抽样有很大的选择偏见风险，因为被引用的个体将与推荐他们的个体具有共同的特征。

 

参考：

https://blog.csdn.net/fendouaini/article/details/102579343

分层抽样的具体程序是：把总体各单位分成两个或两个以上的相互独立的完全的组（如男性和女性），从两个或两个以上的组中进行简单随机抽样，样本相互独立。总体各单位按主要标志加以分组，分组的标志与关心的总体特征相关。例如，正在进行有关啤酒品牌知名度方面的调查，初步判别，在啤酒方面男性的知识与和女性的不同，那么性别应是划分层次的适当标准。如果不以这种方式进行分层抽样，分层抽样就得不到什么效果，花再多时间、精力和物资也是白费。

分层抽样与简单随机抽样相比，往往选择分层抽样，因为它有显著的潜在统计效果。也就是说，如果从相同的总体中抽取两个样本，一个是分层样本，另一个是简单随机抽样样本，那么相对来说，分层样本的误差更小些。另一方面，如果目标是获得一个确定的抽样误差水平，那么更小的分层样本将达到这一目标。

 

各层样本数的确定方法有3种：

①分层定比。即各层样本数与该层总体数的比值相等。例如，样本大小n=50，总体N=500，则n/N=0.1 即为样本比例，每层均按这个比例确定该层样本数。

②奈曼法。即各层应抽样本数与该层总体数及其标准差的积成正比。

③非比例分配法。当某个层次包含的个案数在总体中所占比例太小时，为使该层的特征在样本中得到足够的反映，可人为地适当增加该层样本数在总体样本中的比例。但这样做会增加推论的复杂性。

在调查实践中，为提高分层样本的精确度实际上要付出一些代价。通常，现实正确的分层抽样一般有三个步骤：

首先，辩明突出的（重要的）人口统计特征和分类特征，这些特征与所研究的行为相关。例如，研究某种产品的消费率时，按常理认为男性和女性有不同的平均消费比率。为了把性别作为有意义的分层标志，调查者肯定能够拿出资料证明男性与女性的消费水平明显不同。用这种方式可识别出各种不同的显著特征。调查表明，一般来说，识别出 6 个重要的显著特征后，再增加显著特征的辨别对于提高样本代表性就没有多大帮助了。

第二，确定在每个层次上总体的比例（如性别已被确定为一个显著的特征，那么总体中男性占多少比例，女性占多少比例呢？）。利用这个比例，可计算出样本中每组（层）应调查的人数。

最后，调查者必须从每层中抽取独立简单随机样本。