14年SIFT总结+神经网络

14年SIFT论文总结

1.方法

• 利用SIFT尺度不变特征变换的方法来提取关键信息的一种方法

1.1分词：将手写图像分割为每个独立的单词

• 先使用大津法（最大类间方差）将笔迹的灰度图像转化为二值图像（a变为b）。

  • 假设以阈值T为图像背景与目标的分割界限，目标像素占图像总像素的比例为$w_0$，平均灰度为$u_0$；背景像素占比为$w_1$，平均灰度为$u_1$，图像总平均灰度为u，背景和目标的方差为g。则：

  $\begin{array}{c} u=w_{0} \times u_{0}+w_{1} \times u_{1} \\ g=w_{0} \times\left(u_{0}-u\right)^{2}+w_{1} \times\left(u_{1}-u\right)^{2} \\ g=w_{0} \times w_{1} \times\left(u_{0}-u_{1}\right)^{2} 或\\ g=\frac{w_{0}}{1-w_{0}} \times\left(u_{0}-u\right)^{2} \end{array}$

  • 当方差g最大时，灰度T就是最佳阈值。
  • 大津法，按照图像的灰度特性，将图像分成背景和目标两个部分。当取到最佳阈值时，两者之间的差别是最大的，背景和目标之间的类间方差如果越大，则说明构成图像的两个部分之间差别越大，出错概率就会越小（使方差最大的那个阈值就是我们想要的）。

• 获取图像b中的所有连接组件的高度，计算他们的平均高度$h_a$。
• 使用高斯拉普拉斯滤波器对图像b进行滤波得到图像c。因为同一个词之间内部的距离会小于不同词之间的距离，所以选取适当的方差就可以分离单词。同一个单词之间的连接组件艰巨与单词高度成正比，所以使用图像b中所有连接组件的平均高度$h_a$来确定过滤器的方差$σ = 2.5*h_a$（方差越大，图片越模糊）。

• 再利用大津法对图像c进行二值化得到图像d。

• 将图像b中的单词向图像d的区域上分配，把重叠的区域合并，再拆分重叠边界，得到最终分割好的字词区间WRs，图像f，g。

1.2特征提取

• SIFT特征提取：主要有四个步骤，尺度空间构造、关键点定位、方向分配和关键点特征提取。

  • 在第一阶段制度空间构造，原始图像被分解成高斯金字塔，金字塔的每一层被叫做octave，octave通过使用具有不同方差的DoG滤波器（差分高斯函数，利用两个相邻的高斯函数平滑参数，如0.3和0.4。两个图像相减，得到的就是差分高斯函数的图像）在相应的金字塔层卷积初始图像而进一步分解成若干个子层。

    

    • DoG（Different of Guassian）差分高斯函数：
    • 左边的四张图（包括原始图）是不同参数下高斯滤波结果的图像。
    • 对高斯滤波后的图片（相邻状态下）依次进行两两相减可得到右边的三个高斯函数的差分图（简称DOG）。然后根据上面的模型，依次求中间图片每个像素与该像素同尺度的8个相邻点以及上下相邻尺度对应的9*2共26个点的极值。一个点如果在DOG空间本层以及上下两层的26个领域中是最大值和最小值时，就认为该点是图像在该尺度下的一个特征点。
    • 图像金字塔：以多分辨率来处理图像的一种方法，金字塔底部是待处理图像的高分辨率表示，顶部是低分辨率表示，当金字塔向上层移动时，尺寸和分辨率都会降低。为了图像在任何尺度下都能有对应的特征点
    • 高斯金字塔就是在提取图像时使用高斯滤波。

  • 第二阶段检测出稳定的关键点：本质上去除DoG局部曲率非常不对称的像素，尺度就是平滑参数相差的值

    • 网上的一种

    • 通过拟和三维二次函数以精确确定关键点的位置和尺度 (达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应), 以增强匹配稳定性、提高抗噪声能力, 在这里使用近似Harris Corner检测器。

    • 他的空间尺度函数泰勒展开，对其求导并令为零

    • $D(\mathrm{x})=D+\frac{\partial D^{T}}{\partial \mathrm{x}}^{T} \mathrm{x}+\frac{1}{2} \mathrm{x}^{\mathrm{T}} \frac{\partial^{2} D}{\partial \mathrm{x}^{2}} \mathrm{x}$

    • $\hat{\mathrm{x}}=-\frac{\partial^{2} D^{-1}}{\partial \mathrm{x}^{2}} \quad \frac{\partial D}{\partial \mathrm{x}} \text {. }$

    • 在已经检测到的特征点中，要去掉对比度低的特征点和不稳定的边缘相应点。去除低对比度的点，将公式3带入公式2，即在DoG的极值点处取值得到，若值大于0.03该特征点就留下来：

    • $D(\hat{\mathbf{x}})=D+\frac{1}{2} \frac{\partial D^{T}}{\partial \mathbf{x}} \hat{\mathbf{x}}$

    • 边缘不好点的去除：一个定义不好的高斯查分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个黑塞矩阵求解（是一个多元函数的二阶偏导书构成的方阵，描述了函数的局部曲率）

    $H=\left[\begin{array}{cc} D_{x x} & D_{x y} \\ D_{x y} & D_{y y} \end{array}\right]$

    • 主曲率和H矩阵的特征值成正比，最终比较曲率是否在矩阵特征半径某个范围内即可

  • 第三阶段：计算关键点的方向（利用关键点邻域像素的梯度方向分布特征为每个关键点制定方向参数，使其具备旋转不变性质），下面为（x，y）处梯度的模长和方向公式

  $\begin{array}{l} m(x, y)=\sqrt{(L(x+1, y)-L(x-1, y))^{2}+(L(x, y+1)-L(x, y-1))^{2}} \\ \theta(x, y)=a \tan 2((L(x, y+1)-L(x, y-1)) /(L(x+1, y)-L(x-1, y))) \end{array}$

  • 第四阶段：为每个关键点生成一个描述子

    • 先将坐标轴旋转到关键点的方向，以确保旋转不变，以关键点为中心取8x8的窗口
    • 然后在每4x4的小块上计算8个方向的梯度直方图，即可形成一个种子点，共生成4个种子点，每个种子点有8个方向向量信息，对于特征匹配时也会有很好的容错性。
    • 这样就是每个特征点生成的描述子有4x8=32维的描述子
    • 如果是16x16，就可以生成4x4x8=128维的描述子

    

    

• SDS为特征点描述子

• SOH为尺度和方向直方图

1.3码本生成

• 给定一副手写文档图像，先通过分词得到多个单词区域WRs。对于每个WR，使用SIFT检测关键点，并提取关键点的描述子、尺度和方向。为了使特征的数量有限，将训练样本中提取的关键点SDs聚类成N个类，并用其中心表示每个类别。形成一个大小为N的码本。

• 利用SOM聚类算法生成SD码本，依据经验，选择大小为N=300。

  • SOM（Self Organizing Maps）自组织映射神经网络，对数据无监督学习聚类。

  • 只有输入层和隐藏层的神经网络，隐藏层中的一个节点代表一个需要聚成的类。

  • 训练时采用竞争学习的方式，每个输入的样例在隐藏层中找到一个和他最匹配的节点，成为他的激活节点。然后使用随机梯度下降法更新激活节点的参数。同时，和激活点邻近的点也会根据他们的距离激活节点远近适当的更新参数

  • SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。

    • BP神经网络：输入，隐层，输出层。又称反向传播神经网络， 通过样本数据的训练，不断修正网络权值和阈值使误差函数沿负梯度方向下降，逼近期望输出。

      • 隐层公式：$l=\sqrt{n+m}+a$，n为输入神经元个数，m为输出神经元个数，a为1～10之间常数。
      • 偏置是为了描述训练数据中没有的特征。
      • BP层与层之间的关系是通过激活函数来描述的。激活函数必须满足处处可导。
      • BP训练开始前，对网络的权重和偏置值进行初始化，权重取-1～1之间一个随机数，偏置取0～1之间一个随机数。每一次迭代都使用训练集的所有样本。设定误差函数
      • 利用网络期望输出和实际输出，计算误差函数对输出层各个神经元的偏导数。
      • 利用输出层各个神经元的偏导数和隐含层神经元的输出来修正权值
      • 利用输入层各个神经元的偏导数和隐含层神经元的输出来修正权值
      • 网络初始化：输入层节点个数问$n$，隐含层节点为$l$，输出层节点个数为$m$。输入层到隐含层的权重为$w_{ij}$，偏置为$a_j$，隐含层到输出层权重为$w_{jk}$，偏置为$b_k$。学习速率为$\eta$，激励函数为$g(x),x$为激励函数。i从1～n，j从1～l，k从1～m。
      • 三层bp神经网络隐含层输出$H_j$为：

      $H_{j}=\left(\sum_{i=1}^{n} \omega_{i j} x_{i}+a_{j}\right)$

      • 输出层的输出$O_k$：

      $O_{k}=\sum_{j=1}^{l} H_{j} \omega_{j k}+b_{k}$

      • 误差的计算：

      $E=\frac{1}{2} \sum_{k=1}^{m}\left(Y_{k}-O_{k}\right)^{2}$

      • 权值的更新：

      $\left\{\begin{array}{c} \omega_{i j}=\omega_{i j}+\eta H_{j}\left(1-H_{j}\right) x_{i} \sum_{k=1}^{m} \omega_{j k} e_{k} \\ \omega_{j k}=\omega_{j k}+\eta H_{j} e_{k} \end{array}\right.$

      • 误差反向传播，目标是使误差函数达到最小值，使用梯度下降算法，公式就能推出来上边这个
      • 偏置的更新：公式推倒…

    • 梯度下降算法：找到最快下山的路。$j$是关于$\Theta$的函数，当前处于$\Theta^0$点，要从这个点走到$j$的最小值，相当于走到山底。首先需要确定前进的方向，就是梯度反方向，然后确定每一步的步长或学习率$\alpha$。以此迭代，直到找到最小的值。

    $\Theta^{1}=\Theta^{0}-\alpha \nabla J(\Theta)$

    • SOM步骤：随机初始化权重，寻找最近的神经元，更新邻近神经元的权重，梯度下降学习。

      • 判别函数定义为输入向量i和神经元j的权值之间的欧几里得距离
      • 如果$S_{ij}$是神经元i和j之间的横向距离，则T为拓扑邻域：

      $T_{j, I(x)}=\exp \left(-\frac{S_{j, I(x)}^{2}}{2 \sigma^{2}}\right)$

      • $I(x)$是获胜神经元索引
      • 更新权重的方式

      $\Delta w_{j i}=\eta(t) \cdot T_{j, I(x)}(t) \cdot\left(x_{i}-w_{j i}\right)$

      • 初始化权重$w_j$，从输入空间抽取一个训练输入样本x，安全中匹配最近的神经元$I(x)$，更新拓扑邻域内权重$\Delta w_{j i}$
      • 最终看某个范围内的值就是一类。拓扑半径的距离N=self.GetN(t).

1.4特征匹配和融合

• $I_1$和$I_2$表示两个笔迹图像，$u=(u_1,u_2,\ldots,u_N)$和$v=(v_1,v_2,\ldots,v_N)$分别代表他们的SDSs，$x=\left(x_{1}, x_{2}, \ldots, x_{M}\right)$ 和$y=\left(y_{1}, y_{2}, \ldots, y_{M}\right)$分别代表他们的SOHs。
• 采用曼哈顿距离来测量两个样本的SDSs的u和v：

$D_{1}(u, v)=\sum_{i=1}^{N}\left|u_{i}-v_{i}\right|$

• SOHs中索引大的组件的值的差异比索引小的组件的值小的多。如果我们仍然使用曼哈顿距离来衡量SOH之间的差异，那么大索引的差异将小于小索引的组件。所以采用卡方距离赋予小值分量更多的权重来提高他们的重要性：

$D_{2}(x, y)=\sum_{j=1}^{M} \frac{\left(x_{j}-y_{j}\right)^{2}}{\left(x_{j}+y_{j}\right)}$

• 将两个D归一化到$[0,1]$区间上，融合这两个距离形成新的距离，以比较两张图像之间的差异：

$D\left(I_{1}, I_{2}\right)=w \times D_{1}(u, v)+(1-w) \times D_{2}(x, y)$

• $0 \leq w \leq 1$是一个权重，是依赖于数据库的，可以通过交叉验证来确定。