算法►图像处理

SIFT(Scale-Invariant Feature Transform)

sift基础知识

  • 尺度为$\sigma$ 的高斯尺度空间为 $L(x, y, \sigma) =G(x, y, \sigma) I(x, y, \sigma) $, $$ 是卷积符号

  • 尺度为 $ t$ 的高斯差分为 $D(x, y, t) = L(x, y, kt) - L(x, y, t)$, $k$是乘数常因子。

论文中推荐的参数 $\sigma=1.6$ $k=2^{\frac {1} {3}}$

  1. 建立高斯空间 then DoG空间 (高斯差分)空间

DoG空间每一个维度图片的生成由相邻高斯空间图片相减构成。$L(\sigma) - Img$这一个高斯差分属于尺度为多少的高斯差分，对应于高斯尺度空间中哪一个尺度？

$D(\sigma) \iff L(\sigma )$

  1. 在高斯差分空间寻找极值点（大/小），并对应到高斯空间。这一步就确定关键点的位置和尺度。

  2. 再在高斯空间图像域上，该位置周围选择一个区域，确定该关键点的主方向（分成36个bins，综合周围区域每一个像素的梯度和方向）。

  3. 确定关键点位置、尺度和主方向后，构建一个描述子来描述该关键点。

将关键点周围的区域分块，分别计算块内的直方图，将所有块的梯度直方图组合成一个大的向量

  1. 将坐标轴旋转为关键点的方向。（旋转不变性）
  2. 确定描述子所对应的区域，将区域分成分成小块。
  3. 将关键点附件的像素分配到对应的子区域上，统计每个子区域的梯度值及方向，并分配到8个方向上。得到一个 8 (4 4) = 128维的向量。在对这个向量进行归一化。得到该关键点的descriptor.

More detailed explanation

opencv

  1. Scale-space Extrema Detection

    (x, y, \sigma)

  2. 定位关键点

    step1找到的可能关键点还需要经过更加准确的定位，使用的是尺度空间的泰勒展开。如果该极值点的强度低于阈值（论文中0.03）就拒绝它作为关键点。（OpenCV里面这个参数是contrastThreshold)

    如果该点属于边缘，也拒绝它。Hessian矩阵可以通过确定特征值的大小来判断。如果特征值比率大于某个阈值(edgeThreshold)，则认为他是边缘，也拒绝他。 排除了低对比度以及边缘上的关键点。

  3. 确定主方向

    为每个关键点分配一个主方向。计算关键点附近区域每一个像素点梯度大小和方向，把梯度方向分配到36bins里面，其大小进行高斯加权。直方图最高峰就是该关键点的主方向，任何peak高于80%都作为辅助方向。

  4. 关键点描述子

    在关键点附近1616区域分成 $44$的块，每个块内的像素梯度大小方向分成8bins，一共构成$8 4 * 4=128$维的向量。再针对这个向量进行其他处理以达到光照，旋转不变性。

机器学习

支持向量机 SVM

超平面、核技巧、对偶、KKT条件

  • 超平面

    $W^TX + b = 0$

每个样本点x到超平面的距离

$d = Wx + b$

希望的情况是d > 0，当y > 0

在平面尽量居中，距离尽量远的设想下，问题转换为

$min ||W||^2$

s.t. $y_i(W^Tx + b) >= 1$

由对偶，可将原问题转化为

$\max_\alpha \sum_{i=1}^m\alpha_i -\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_i\cdot x_j \\ subject\space to\space 0 \le \alpha_i \le C, i=1…m, \sum_{i=1}^m{a_iy_i}=0$

对于待预测样本，预测方式

$\sum_{i\in SV} y_i \alpha_i K(x_i, x) + b,$

Reference

  1. Understanding the mathematics behind Support Vector Machines
  2. The Mathematics Behind Support Vector Machine Algorithm (SVM)
  3. sklearn-svm-svc(classification)