图像匹配

图像主要可以分为两大类：

1. 像素匹配：两帧图像间完整的匹配关系，计算复杂度高，因此通常以特征匹配为基础。
2. 特征匹配：两帧图像间关键的匹配关系，计算复杂度相对较低，可建立匹配关系的高层描述，是图像匹配的重点研究内容。方法由“特征提取”（feature detection）、“特征匹配”（feature matching）两个步骤构成。

主流的图像匹配方法主要是采用特征提取：卷积的形式。它的做法是：用其邻域的加权平均值替换每个像素。而这个weight称为filter kernel。

以下是一个3*3大小的filter（box filter）的weiht示例：

卷积（convolution）

为了能够将卷积公式与傅里叶变换建立联系，所以在进行卷积的时候，一般先将kernel进行翻转。

数字图像是一个二维的离散信号，对数字图像做卷积操作其实就是利用卷积核（卷积模板）在图像上滑动，将图像点上的像素灰度值与对应的卷积核上的数值相乘，然后将所有相乘后的值相加作为卷积核中间像素对应的图像上像素的灰度值，并最终滑动完所有图像的过程。

上图可以清晰的表征出整个卷积过程中一次相乘后相加的结果：该图片选用3x3的卷积核，卷积核内共有九个数值，所以图片右上角公式中一共有九行，而每一行都是图像像素值与卷积核上数值相乘，最终结果-8代替了原图像中对应位置处的1。这样沿着图片步长为1滑动，每一个滑动后都一次相乘再相加的工作，就可以得到最终的输出结果。除此之外，卷积核的选择有一些规则：
1）卷积核的大小一般是奇数，这样的话它是按照中间的像素点中心对称的，所以卷积核一般都是3x3，5x5或者7x7。有了中心，便有了半径的概念，例如5x5大小的核的半径就是2。
2）卷积核所有的元素之和一般要等于1，这是为了原始图像的能量（亮度）守恒。其实也有卷积核元素相加不为1的情况。
3）如果滤波器矩阵所有元素之和大于1，那么滤波后的图像就会比原图像更亮，反之，如果小于1，那么得到的图像就会变暗。如果和为0，图像不会变黑，但也会非常暗。

4）对于滤波后的结构，可能会出现负数或者大于255的数值。对这种情况，我们将他们直接截断到0和255之间即可。对于负数，也可以取绝对值。

边界问题

上面的图片说明了图像的卷积操作，但是也反映出一个问题，如上图，原始图片尺寸为7*7，卷积核的大小为3*3，当卷积核沿着图片滑动后，只能滑动出一个5*5的图片出来，这就造成了卷积后的图片和卷积前的图片尺寸不一致，这显然不是想要的结果，所以为了避免这种情况，需要先对原始图片做边界填充处理。对于上面的情况，需要先把原始图像填充为9*9的尺寸。

常用的区域填充方法包括（例如，用3*3定义原始图像的尺寸，补充为9*9的尺寸）：

原始图像：

1. 补零填充

2. 边界复制填充

3. 镜像填充

4. 块填充

Sobel operator

Sobel算子主要用于获得数字图像的一阶梯度，常见的应用和物理意义是边缘检测。

原理

Sobel算子有两个滤波矩阵：和 Gy, 用来计算横向的梯度, 用来计算纵向的梯度。下图是具体的滤波器：

【注】：当kernel的大小为3x3时，上面显示的Sobel kernel可能会产生明显的不准确性（因为Sobel只是导数的近似值）。使用了以下的kernel可以有效地解决这种问题：

Sobel算子的用途

它可以用来对图像进行边缘检测, 或者用来计算某个像素点的法线向量. 这里需要注意的是:
边缘检测时：用于检测纵向边缘，用于检测横向边缘。
计算法线时：用于计算法线的横向偏移，用于计算法线的纵向偏移。

Fourier transform

傅里叶变换是一种线性积分变换，用于信号在时域（或空域）和频域之间的变换。

时域，即世界随时间的变化而发生的最直观的改变。严格上说，是信号与时间的对应关系。

频域 ，相对于时域而言，不容易通过直接观察得到的，但是却是一种最简单的方式，可以用来描述这个世界的运动规律。严格上说，频域是时间与状态的对应关系。

时域主要用来直观的观察变换，而频域则是描述变换的一个趋势。例如，暂时把频域作为一个矢量来看，类似于用速度描述一个人的状态；而路程和时间的关系，则体现速度的快慢。但是，在一个很微小的时间内（人是感觉不到变化的）。所以同样的，就很难描述这个时间里面发生的事。但是，频域就能时刻展现这个变换的趋势，通过计算就可以很直观的看到整个变换了。

例如下图，能够直观的看到小球在t1时刻的位置和t2时刻的位置，但是看不到在这两个时刻，小球的速度是多少，只知道速度的快慢，也就是小球在下一刻移动的距离远近，而这个速度就是在数学上严谨的一个描述性的矢量，就是所说的频域。

模板匹配（matchTemplate)

模板匹配是一种用于查找与模板图像（patch）匹配（相似）的图像区域的技术。

虽然patch必须是矩形，但并非所有矩形都是相关的。 在这种情况下，可以利用mask来进行隔离，从而找到匹配的patch部分。

模板匹配是一种最原始、最基本的模式识别方法，研究某一特定对象物的图案位于图像的什么地方，进而识别对象物，这就是一个匹配问题。它是图像处理中最基本、最常用的匹配方法。模板匹配具有自身的局限性，主要表现在它只能进行平行移动，若原图像中的匹配目标发生旋转或大小变化，该算法无效。

简而言之，模板匹配就是在整个图像区域发现与给定子图像匹配的小块区域

工作原理

在待检测图像上，从左到右，从上向下计算模板图像与重叠子图像的匹配度，匹配程度越大，两者相同的可能性越大。

图像放缩中最近邻插值和双线性插值的基本原理

最近邻插值

例如，有一张3x3的256级灰度图（原始图把它叫做源图，src），假设其像素矩阵如下图所示：

如果把这副图放大为 4x4大小的图像，那么该怎么做呢？第一步，先把4x4的矩阵画出来，如下所示(矩阵的每个像素目前都是未知数，需要被填充，这个将要被填充的图的叫做目标图，dst）：

然后，需要对这个空的矩阵进行填值，要填的值从src中来。先填写dst最左上角的象素，坐标为(0,0)。该坐标对应src中的坐标为：

利用上述公式，便可以可以找到对应的src的坐标：

这样便找到了src的对应坐标，就可以把src中坐标为(0,0)处的234像素值填进dest的(0,0)这个位置上。

寻找目标图中坐标为(1,0)像素对应dest中的坐标。利用公式，可得：

结果发现，得到的坐标里面竟然有小数。计算机里的图像是数字图像，像素已经是最小单位，所以像素的坐标必须都是整数。这时，采用的采用四舍五入的方法（也可以采用直接舍掉小数位的方法），把非整数坐标转换成整数，得到(1,0)。

依次填充每个像素，放大后的图像便诞生了，其像素矩阵为：

这种放大图像的方法叫做：最临近插值算法。它是一种最基本、最简单的图像缩放算法，效果也是最不好的，放大后的图像有很严重的马赛克，缩小后的图像有很严重的失真

这种方法效果造成了严重的图像失真。比如，当由dst的坐标反推得到src的的坐标时，得到的是一个浮点数时，采用了四舍五入的方法（即，直接采用了和这个浮点数最接近的像素的值）。这种方法是很不科学的，当推得坐标值为0.75时，不应该就简单的取为1。目标像素值其实应该根据这个源图中虚拟的点四周的四个真实的点，按照一定的规律计算出来，这样才能达到更好的缩放效果。

双线性插值

双线性插值算法是一种比较好的图像缩放算法，它充分利用了源图中虚拟点四周的四个真实存在的像素值，来共同决定目标图中的一个像素值，因此缩放效果比简单的最邻近插值要好很多。

双线性插值，就是两个方向的线性插值加起来。所以，只要了解什么是线性插值，分别在x轴和y轴都做一遍，就是双线性插值。

线性插值的概念非常简单，就是两个点A、B中间插入一个点C（点C坐标在AB连线上），直接让C的值落在AB的值的连线上就行。

例如，A点坐标(0,0)，值为3；B点坐标(0,2)，值为5。对坐标为(0,1)的点C进行插值，就让C落在AB线上，值为4就可以。但是，如果C不在AB的线上怎么办？所以，就有了双线性插值。

如图，已知Q12、Q22、Q11、Q21，但要插值的点为P点，这就需要用双线性插值。首先，在x轴方向上，对R1和R2两个点进行插值，然后根据R1和R2对P点进行插值，这就是所谓的双线性插值。

假如我们想得到未知函数在点 的值，假设我们已知函数在四个点的值。

首先，在x方向进行线性插值，得到：

然后，在y方向进行线性插值，得到：

这样就得到所要的结果：

如果选择一个坐标系统使得在点 的四个已知点坐标分别为(0, 0)、(0,1)、(1,0)和(1,1)，则插值公式就可以化简为：

或用矩阵运算表示为：

双线性插值算法描述如下:
对于一个目的像素，设置坐标通过反向变换得到的浮点坐标为(i+u,j+v)（其中i、j均为浮点坐标的整数部分，u、v为浮点坐标的小数部分，是取值[0,1)区间的浮点数）。则这个像素的值f(i+u,j+v)可由原图像中坐标为(i,j)、(i+1,j)、(i,j+1)、(i+1,j+1)所对应的周围四个像素的值决定，即：

其中，表示源图像(i,j)处的的像素值。

依旧用刚才的例子，现在，假如目标图的像素坐标为(1,1)，那么反推得到对应于源图的坐标是(0.75,0.75)。这其实只是一个概念上的虚拟像素，实际在源图中并不存在这样一个像素，那么目标图的像素(1,1)的取值不能由这个虚拟像素来决定，而应该由源图的这四个像素共同决定：(0,0)、(0,1)、(1,0)、(1,1)。而由于(0.75,0.75)离(1,1)要更近一些，那么(1,1)所起的决定作用更大一些。从上述公式中的系数uv=0.75×0.75可以体现出来，而(0.75,0.75)离(0,0)最远，所以(0,0)所起的决定作用就要小一些，公式中系数为(1-u)(1-v)=0.25×0.25也体现了这一特点。

双线性插法的计算比最邻近点法复杂，计算量较大，但没有灰度不连续的缺点，结果基本令人满意。它具有低通滤波性质，使高频分量受损，图像轮廓可能会有一点模糊。

加速以及优化策略

单纯按照上述实现的插值算法只能勉强完成插值的功能，速度和效果都不理想，在具体代码实现的时候有些小技巧：

• 源图像和目标图像几何中心的对齐。
• 将浮点运算转换成整数运算

源图像和目标图像几何中心的对齐　　

方法：在计算源图像的虚拟浮点坐标的时候，一般情况为：

　　
中心对齐(OpenCV也是如此)：

原理：
将公式变形:

相当于在原始的浮点坐标上加上了这样一个控制因子，该项的符号可正可负，与的比值，也就是当前插值是扩大还是缩小图像有关。至于它的的作用，看一个例子：假设源图像是3*3，中心点坐标为(1,1)，目标图像是9*9，中心点坐标为(4,4)。在进行插值映射的时候，尽可能均匀地用到源图像的像素信息，最直观的就是：(4,4)映射到(1,1)。现在直接计算，也就是我们在插值的时候所利用的像素集中在图像的右下方，而不是均匀分布整个图像。现在考虑中心点对齐，，刚好满足我们的要求。

将浮点运算转换成整数运算

直接进行计算的话，由于计算的和都是浮点数，后续会进行大量的乘法，而图像数据量又大，速度不理想。解决思路是：浮点运算→整数运算→左右移位运算。

放大的主要对象是u，v这些浮点数，OpenCV选择的放大倍数是2048（利用左移11位操作就可以达到放大目的）。选取合适的放大倍数需要从三个方面考虑：

• 精度问题，如果这个数取得过小，那么经过计算后可能会导致结果出现较大的误差
• 这个数不能太大，太大会导致计算过程超过长整形所能表达的范围
• 速度考虑。假如放大倍数取为12，那么算式在最后的结果中应该需要除以12*12=144，但是如果取为16，则最后的除数为16*16=256。这个数字好，可以用右移来实现，而右移要比普通的整除快很多

直方图均衡化

很多时候，图片看起来的效果不是那么清晰，这时便可以对图像进行一些处理来扩大图像的像素值显示的范围。

例如，有些图像整体像素值偏低，图像中的一些特征看的不是很清晰，只是隐约看到一些轮廓痕迹，这时便可以经过图像直方图均衡化之后使得图像看起来亮一些，也便于后续的处理。直方图均衡化是灰度变换的一个重要应用，它高效且易于实现，广泛应用于图像增强处理中。图像的像素灰度变化是随机的，直方图的图形高低不齐，直方图均衡化就是用一定的算法使直方图大致平和的方法。

图像的直方图是什么?

• 直方图是图像中像素强度分布的图形表达方式
• 它统计了每一个强度值所具有的像素个数

简而言之，直方图均衡化是通过拉伸像素强度分布范围来增强图像对比度的一种方法。

HOG（方向梯度直方图，Histogram of Oriented Gradient）

HOG是一种能对物体进行检测的、基于形状边缘特征的描述算子，它的基本思想是：利用梯度信息能很好的反映图像目标的边缘信息，并通过局部梯度的大小将图像局部的外观和形状特征化。利用梯度HOG特征并结合其他特征对人体进行检测得到了较好的结果。

HOG特征提取的主要步骤:

颜色空间的归一化

在现实的情况，图像目标会出现在不同的环境中，光照也会有所不一样，颜色空间归一化就是：对整幅图像的颜色信息作归一化处理，从而减少不同光照及背景的影响，也为了提高检测的鲁棒性。引入图像Gamma和颜色空间归一化来作为特征提取的预处理手段（RGB还有LAB色彩空间能使检测结果大致相同且能起到积极的影响。此外，分别在每个颜色通道上使用两种不同的Gamma归一化方式，取平方根或者使用对数法，最终验证这一预处理对检测的结果几乎没有影响，而不能对图像进行高斯平滑处理，因平滑处理会降低图像目标边缘信息的辨识度，影响检测结果）。

为了减少光照因素的影响，首先需要将整个图像进行规范化（归一化）。在图像的纹理强度中，局部的表层曝光贡献的比重较大，所以，这种压缩处理能够有效地降低图像局部的阴影和光照变化。因为颜色信息作用不大，通常先转化为灰度图。

Gamma压缩公式：

梯度计算

边缘是由图像局部特征包括灰度、颜色和纹理的突变导致的。一幅图像中，相邻的像素点之间变化比较少，区域变化比较平坦，则梯度幅值就会比较小；反之，则梯度幅值就会比较大（梯度在图像中对应的就是其一阶导数）。

模拟图像中任一像素点的梯度是一个矢量：

数字图像中像素点的梯度是用差分来计算的：

一维离散微分模板在将图像的梯度信息简单、快速且有效地计算出来，其公式如下：

梯度的幅值及方向计算公式如下：

不同的梯度运算模板的检测效果上也不一样。使用简单的一维离散微分模板和梯度算子分别得到x和y方向梯度（得到的检测效果是最好的，而使用其他形式的梯度运算模板如Prewitt和Sobel等算子，不仅增加运算量而同时也降低了其检测效果）。然后再利用公式计算该像素点的梯度大小和方向

计算细胞单元的梯度直方图

这一步的主要目的是为局部图像区域提供一个编码，同时能够保持对图像中人体对象的姿势和外观的弱敏感性。

对于整个目标窗口，需要将其分成互不重叠大小相同的细胞单元（cell），然后分别计算出每个cell的梯度信息，包括梯度大小和梯度方向。

将像素的梯度方向在0-360°区间内，平均划分为9个bins（超过9个时，不仅检测性能没有明显的提高，反而增加了检测运算量）。每个cell内的像素为其所在的梯度方向直方图进行加权投票，加权的权值可以是像素本身的梯度幅值，也可以是幅值的平方或平方根等，而若使用平方或平方根，实验的检测性能会有所降低，使用梯度幅值的实验效果更可靠。

对组合成块的梯度直方图作归一化

从梯度计算公式中可以看出，梯度幅值绝对值的大小容易受到前景与背景对比度及局部光照的影响，要减少这种影响得到较准确的检测效果就必须对局部细胞单元进行归一化处理。

归一化的基本思想：将几个细胞单元（cell）组合成更大的块（block），这时，整幅图像就可看成是待检测窗口，将更大的块看成是滑动窗口，依次从左到右从上到下进行滑动，得到一些有重复细胞单元的块及一些相同细胞单元（cell）在不同块（block）中的梯度信息，再对这些块（block）信息分别作归一化处理，不同的细胞单元尺寸大小及不同块的尺寸大小会影响最终的检测效果。

假设检测的窗口的尺寸为64×64像素，分成4×4=16个细胞单元(cell)，如下图，16×16像素是每个细胞单元的大小，块（block）是由相邻的2×2=4个细胞单元组成的（如图紫色的小框）。滑动窗口的大小为一个块的大小，依次将滑动窗口从左到右从上到下进行滑动来获得整个待测窗口的边缘信息，得到9个块，统计这9个块在9个不同方向上的梯度信息，在整个窗口中得到的梯度特征是9×9=81维的向量。

在实际情况中，检测窗口的大小为128×64像素，一个细胞单元的大小为8×8像素，由2×2个细胞单元组成大小为16×16像素的块，一个细胞单元的梯度直方图化成9个bins，块的移动步长是8个像素，则检测窗口在图像中移动的步长也为8个像素，这样检测窗口就有((128-16)/8+1)×((64-16)/8+1)= 105个块，一个块有4个细胞单元，每个细胞单元的HOG特征向量长度是9，则最终的HOG特征描述符大小就是105×4×9 = 3780维。

范数（）、范数（）

归一化计算公式为：
归一化：

平方根归一化：

归一化：

对归一化梯度特征进行SVM分类：

如下图所示，对于滑动窗口提取的2个窗口，分别计算出归一化的梯度特征，然后应用SVM实现是人还是背景的分类判定。

HOG特征的优点：

• 由于HOG是在图像的局部方格单元上操作，所以它对图像几何和光学的形变都能保持很好的不变性，这两种形变只会出现在更大的空间领域上。
• 在粗的空域抽样、精细的方向抽样以及较强的局部光学归一化等条件下，只要行人大体上能够保持直立的姿势，可以容许行人有一些细微的肢体动作，这些细微的动作可以被忽略而不影响检测效果。

因此，HOG特征是特别适合于做图像中的人体检测的。

OpenCV中HOG的源码分析

LBP特征

LBP（Local Binary Pattern）指局部二值模式，是一种用来描述图像局部特征的算子，LBP特征具有灰度不变性和旋转不变性等显著优点。由于LBP特征计算简单、效果较好，因此LBP特征在计算机视觉的许多领域都得到了广泛的应用，LBP特征比较出名的应用是用在人脸识别和目标检测中。

1. 原始LBP特征描述及计算方法

原始的LBP算子定义在像素3×3的邻域内，以邻域中心像素为阈值，相邻的8个像素的灰度值与邻域中心的像素值进行比较，若周围像素大于中心像素值，则该像素点的位置被标记为1，否则为0。这样，3×3邻域内的8个点经过比较可产生8位二进制数，将这8位二进制数依次排列形成一个二进制数字，这个二进制数字就是中心像素的LBP值，LBP值共有种可能，因此LBP值有256种。中心像素的LBP值反映了该像素周围区域的纹理信息。

【注】：计算LBP特征的图像必须是灰度图，如果是彩色图，需要先转换成灰度图。
上述过程用图像表示为：

其对应的公式为：

2. LBP特征的改进

2.1 圆形LBP特征（Circular LBP or Extended LBP）

由于原始LBP特征使用的是固定邻域内的灰度值，因此当图像的尺度发生变化时，LBP特征的编码将会发生错误，LBP特征将不能正确的反映像素点周围的纹理信息。

基本的LBP算子的最大缺陷在于：它只覆盖了一个固定半径范围内的小区域，这显然不能满足不同尺寸和频率纹理的需要。为了适应不同尺度的纹理特征，并达到灰度和旋转不变性的要求，将3×3邻域扩展到任意邻域，并用圆形邻域代替了正方形邻域，改进后的 LBP 算子允许在半径为R的圆形邻域内有任意多个像素点。从而得到了诸如半径为R的圆形区域内，含有P个采样点的LBP算子：

图像白化

白化的目的是去除输入数据的冗余信息。例如：训练数据是图像，由于图像中相邻像素之间具有很强的相关性，因此输入是冗余的。白化的目的就是降低输入的冗余性。

输入数据集，经过白化处理后，生成的新数据集满足两个条件：一是特征相关性较低；二是特征具有相同的方差。白化算法的实现过程：

• 第一步操作是 PCA，求出新特征空间中的新坐标
• 第二步是对新的坐标进行方差归一化操作

白化分为 PCA 白化、ZCA 白化，算法实现步骤如下：

1. PCA 预处理：

左图表示原始数据 X，然后通过协方差矩阵可以求得特征向量 u1、u2，然后把每个数据点，投影到这两个新的特征向量（这两个特征向量是不变且正交的），得到进行坐标如下：

2. PCA 白化

PCA 白化是指对上面的 PCA 的新坐标 X’，每一维的特征做一个标准差归一化处理。从上面可以看到，在新的坐标空间中，(x1,x2) 两个坐标轴方向的数据明显标准差不同，因此接着要对新的每一维坐标做一个标准差归一化处理。

3. ZCA 白化

ZCA 白化是在 PCA 白化的基础上，把上面 PCA 白化的结果，又变换到原来坐标系下的坐标。