计算机视觉——Harris,SIFT

视觉github:https://github.com/g107904/Computer_Vision_task

SVD分解:
对于一个矩阵A,分解成A = U S V^{T}
其中U是正交矩阵,S为对角矩阵,V为正交矩阵。
最小二乘法:
对于min({|Ax-b|}^2),有

    \[{|Ax-b|}^2 = {|Ax-b|}^T |Ax-b| = x^T A^T A x - b^T A x - x^T A^T b + b^T b\]

    \[ \begin{split} \frac{\partial L}{\partial x} = 2 A^T A x - 2 A^T b  = 0 \rightarrow 2(V S^T U^T U S V^T x - V S^T U^T b) = 0 \\ \rightarrow V S^T S V^T x = V S^T U^T b \\ \rightarrow x = V S^{-1} U^{T} b, r(A) = n \end{split} \]

如果A不是方阵,

    \[{\begin{bmatrix} S_1 \\ 0 \end{bmatrix}}^{T} \begin{bmatrix} S_1 \\ 0 \end{bmatrix} V^T x = {\begin{bmatrix} S_1 \\ 0 \end{bmatrix}}^{T} U^T b \rightarrow {S_1}^T S_1 V^T x = {\begin{bmatrix} S_1 \\ 0 \end{bmatrix}}^{T} U^T b \rightarrow x = V {\begin{bmatrix} {S_1}^{-1} \\ 0^T \end{bmatrix} U^T b\]

Harris角点检测:
利用当前矩形框与周边矩形框的差异来度量当前点的独特性。

    \[\sum_{(m,n)} w(m,n) ([I(x+u+m,y+v+n) - I(x+m,y+n)])^2\]

    \[taylor: I(x+u+m,y+v+n) = I(x+m,y+n) + \frac{\partial I}{\partial x} u + \frac{\partial I}{\partial y} v\]

    \[  \begin{split} & \sum_{(m,n)} w(m,n) ([I(x+u+m,y+v+n) - I(x+m,y+n)])^2  \\ \rightarrow & \sum_{(m,n)} w(m,n) ([\frac{\partial I(x+m,y+n)}{\partial x} u + \frac{\partial I(x+m,y+n)}{\partial y} v])^2  \\ \rightarrow & \sum_{(m,n)} w(m,n) (\begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} I_x(x+m,y+n) \\ I_y(x+m,y+n) \end{bmatrix} \\ & \begin{bmatrix} I_x(x+m,y+n) & I_y(x+m,y+n) \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} )  \\ \rightarrow & \sum_{(m,n)} w(m,n) (\begin{bmatrix} u & v \end{bmatrix} \\ & \begin{bmatrix} {I_x(x+m,y+n)}^2 & I_x(x+m,y+n)I_y(x+m,y+n) \\ I_y(x+m,y+n)I_x(x+m,y+n) & {I_y(x+m,y+n)}^2 \end{bmatrix} \\ & \begin{bmatrix} u \\ v \end{bmatrix} ) \\ \rightarrow & \begin{bmatrix} u & v \end{bmatrix} \\ & \begin{bmatrix} {\sum_{(m,n)} w(m,n)I_x(x+m,y+n)}^2 & \sum_{(m,n)} w(m,n)I_x(x+m,y+n)I_y(x+m,y+n) \\ \sum_{(m,n)} w(m,n)I_y(x+m,y+n)I_x(x+m,y+n) & {\sum_{(m,n)} w(m,n)I_y(x+m,y+n)}^2 \end{bmatrix} \\ & \begin{bmatrix} u \\ v \end{bmatrix} \end{split} \]

其中,

    \[\begin{bmatrix} {\sum_{(m,n)} w(m,n)I_x(x+m,y+n)}^2 & \sum_{(m,n)} w(m,n)I_x(x+m,y+n)I_y(x+m,y+n) \\ \sum_{(m,n)} w(m,n)I_y(x+m,y+n)I_x(x+m,y+n) & {\sum_{(m,n)} w(m,n)I_y(x+m,y+n)}^2 \end{bmatrix}\]

就是哈里斯矩阵。
矩阵特征值\lambda_1,\lambda_2
行列式值det(M) = \lambda_1 \lambda_2
trace(M) = \lambda_1 + \lambda_2
cornerness = det(M) - \lambda trace(M)^2
cornerness值大,\lambda_1值大,\lambda_2值大,是角点。
比较两个点的差异:
SAD:

    \[SAD = \sum_{n= -N}^{N} \sum_{m=-M}^{M} |I_1(x+m,y+n)-I_2(x'+m,y'+n)|\]

MSE:

    \[MSE = \frac{\sum_{n= -N}^{N} \sum_{m=-M}^{M} {(I_1(x+m,y+n)-I_2(x'+m,y'+n))}^2}{(2N+1)(2M+1)}\]

NCC:

    \[NCC = \frac{\sum_{n= -N}^{N} \sum_{m=-M}^{M} (I_1(x+m,y+n)-\mu_1)(I_2(x'+m,y'+n)-\mu_2)}{{std}_1 {std}_2},\]

    \[\mu_1 = \frac{\sum_{n= -N}^{N} \sum_{m=-M}^{M} I_1(x+m,y+n)}{(2N+1)(2M+1)},\mu_2 = \frac{\sum_{n= -N}^{N} \sum_{m=-M}^{M} I_2(x'+m,y'+n)}{(2N+1)(2M+1)},\]

    \[{std}_1 = \sqrt{\frac{\sum_{n= -N}^{N} \sum_{m=-M}^{M} {(I_1(x+m,y+n)-\mu_1)}^2}{(2N+1)(2M+1)-1}},\]

    \[{std}_2 = \sqrt{\frac{\sum_{n= -N}^{N} \sum_{m=-M}^{M} {(I_2(x'+m,y'+n)-\mu_2)}^2}{(2N+1)(2M+1)-1}}\]

SIFT特征点:
第一步:
构建多尺度的高斯拉普拉斯图像。
高斯平滑系数\sigma,对应高斯函数G(x,y,\sigma)= \frac{1}{2 \pi {\sigma}^2} e^{-\frac{x^2+y^2}{2{\sigma}^2}}
第一组第一层为原图像expand之后的图像,一共有s+3层,每一层的平滑系数是k^{\frac{r}{s}} \sigma,其中r=0,1,2,...,s+2是层序号,k = 2^{\frac{1}{s}}
为保持平滑系数的连续,下一组的第一层图像由上一层倒数第三层图像直接降采样得到。
高斯卷积性质:

    \[I \bigotimes G(:,:,\sigma_1) \bigotimes G(:,:,\sigma_2) \bigotimes ... \bigotimes G(:,:,\sigma_n) = I \bigotimes G(:,:,\sqrt{\sigma_1^2+\sigma_2^2+...+\sigma_n^2})\]

所以,有

    \[I \bigotimes G(:,:,k^2 \sigma) = I \bigotimes G(:,:,\sqrt{\sigma^2+(k^2-1) \sigma^2}) = I \bigotimes G(:,:,\sigma) \bigotimes G(:,:,\sqrt{(k^2-1) \sigma^2})\]

可以利用前一层图像迭代生成下一层图像,减少计算量。
LOG:
利用高斯拉普拉斯算子生成的金字塔。

    \[\Delta G = \frac{\partial^2 G}{\partial x^2} + \frac{\partial^2 G}{\partial y^2}\]

    \[\widetilde{\Delta} G = \sigma^2(\frac{\partial^2 G}{\partial x^2} + \frac{\partial^2 G}{\partial y^2})\]

DOG:

    \[DOG = I \bigotimes G - I,I \bigotimes G \bigotimes G - I \bigotimes G,...\]

Lindeberg证明用\sigma^2标准化的高斯拉普拉斯(\nabla^2 G, LOG, Laplacian of Gauss)有着真正的尺度无关的特性,而Mikolajczyk发现,相比于其他一系列函数(比如梯度,Hessian,Harris角点函数等),用\sigma^2标准化的高斯拉普拉斯(\sigma^2 \nabla^2 G)有着更稳定的图像特征,因此该函数是我们理想的寻找特征点的函数。而在此,我们利用DoG来近似。

    \[\sigma \Delta G = \frac{\partial G}{\partial \sigma} \approx \frac{G(x,y,k \sigma)-G(x,y,\sigma)}{k \sigma - \sigma} \rightarrow G(x,y,k \sigma) - G(x,y,\sigma) \approx (k-1) \sigma^2  \Delta G\]

所以,

    \[DOG = I \bigotimes G(x,y,k \sigma) - I \bigotimes G(x,y,\sigma) = I \bigotimes (G(x,y,k \sigma) - G(x,y,\sigma)) \approx I \bigotimes (k-1) \sigma^2  \Delta G\]

从另一角度看,令L = I \bigotimes G

    \[\frac{L(x,y,k \sigma) - L(x,y,\sigma)}{k \sigma - \sigma} \approx \frac{\partial L}{\partial \sigma} = \frac{\partial (I \bigotimes G)}{\partial \sigma} =I \frac{\partial G}{\partial \sigma}\]

高斯差分图像是对尺度的有限差分.
第二步:
在DOG里找空间和尺度意义上的极值点,具体地,在r-1,r,r+1的DOG中,找r层的极值点,对周边26点进行判断是否是局部极小值或是局部极大值,这就是特征点。
第三步:
估计特征点方向。
取特征点周围区域,对区域内的每个点,将梯度离散化成8个方向,计算落在每个方向上的梯度强度值,再乘以距离函数,对方向进行投票。
每个点对它梯度方向的两个近似离散方向的贡献分别为:

    \[G*Mag*(1-\frac{\theta}{\frac{\pi}{4}}),G*Mag*\frac{\theta}{\frac{\pi}{4}}\]

其中,\theta是梯度方向和离散方向的夹角,G是距离函数,常用高斯函数。
最后,值最大的方向即为特征点方向。
第四步:
计算描述子,在特征点周围16*16区域,取4*4个cell,其中每个cell为8*8。
在每个cell里面将每个点的梯度方向减去特征点方向,离散化方向,累加高斯加权后的梯度值到8个方向中,最后得到的梯度直方图就是描述子,每个cell有8个方向,有16个cell,最后描述子为128维。
第五步:
归一化,
clipping:

    \[f(i) = \left\{ \begin{aligned} f(i),  & f(i) \ge 0.2 \\ 0.2,     &  f(i) > 0.2 \end{aligned} \right.\]

normalize:

    \[f = \frac{f}{{||f||}_2}\]

L2_norm:

    \[{||f||}_2 = \sqrt{\sum_{1}^{128} f^2 (i)}\]

HOG特征:
1)灰度化;

2)归一化;

3)计算梯度(包括大小和方向)。

4)将图像划分成小cells(例如4*4像素/cell);

5)统计每个cell的梯度直方图(不同梯度的个数),形成每个cell的descriptor;

6)将每几个cell组成一个block(例如2*2个cell/block),一个block内所有cell的特征descriptor串联起来便得到该block的HOG特征descriptor。

7)将所有block的HOG特征descriptor串联起来就可以得到HOG特征descriptor。

发表评论

电子邮件地址不会被公开。 必填项已用*标注