讲述了那个函数在那点紧邻的变化率,能够如此敞亮生成式方法紧即使数量是怎么着

一 、基本概念

1.微积分

导数:二个函数在某一点的导数叙述了那些函数在那点紧邻的变化率。
$$
f'(a) = \lim_{h \rightarrow 0} \frac{f(a+h)-f(a)}{h}
$$
梯度:多元函数的导数正是梯度。

一阶导数和梯度(gradient)

​ $f'(x)$ ;
$$
\nabla f(\bf{X}) = \frac{\partial f(\bf{X})}{\partial \bf{X}} =
\begin{bmatrix}
\frac{\partial f(\bf{X})}{\partial {x_1}} \
\frac{\partial f(\bf{X})}{\partial {x_2}} \
\vdots\
\frac{\partial f(\bf{X})}{\partial {x_n}} \
\end{bmatrix}
$$
二阶导数与Hessian矩阵

$f”(x)$;
$$
\bf{H}(x)= \nabla^2f(\bf{X}) = \begin{bmatrix}
\frac{\partial ^2 f(\bf{X})}{\partial {x_1}^2} & \frac{\partial
^2 f(\bf{X})}{\partial {x_1}\partial {x_2}} & \cdots &
\frac{\partial ^2 f(\bf{X})}{\partial {x_1}\partial {x_n}} &\
\frac{\partial ^2 f(\bf{X})}{\partial {x_2}\partial {x_1}} &
\frac{\partial ^2 f(\bf{X})}{\partial {x_2}^2} & \cdots &
\frac{\partial ^2 f(\bf{X})}{\partial {x_2}\partial {x_n}} &\
\vdots & \vdots & \ddots & \vdots \
\frac{\partial ^2 f(\bf{X})}{\partial {x_n}\partial {x_1}} &
\frac{\partial ^2 f(\bf{X})}{\partial {x_n}\partial {x_2}} &
\cdots & \frac{\partial ^2 f(\bf{X})}{\partial {x_n}^2} &\
\end{bmatrix}
$$
Taylor级数

输入为标量的Taylor级数:
$$
f(x_k + \delta) \approx f(x_k) +f'(x_k)\delta +
\frac{1}{2}f”(x_k)\delta^2 + \cdots
+\frac{1}{n!}f{(n)}(x\_k)\\deltan
$$
输入为矢量的泰勒级数(前三项):
$$
f(\bf{x}_k + \bf{\delta}) \approx f(x_k) +\nabla^Tf(\bf{x}_k)
\bf{\delta} +
\frac{1}{2}\bf{\delta^T}f”(\bf{x}_k)\bf{\delta}
$$
此时 满足 $\nabla^T f(\bf{x}_k) =0​$ 的点为平稳点,假如还有:

​ $\nabla^2 f(\bf{x}_k) > 0$ ,即 为正定矩阵,则
$\bf{x}_k$为一凶暴局地非常的小值点(反之,严格局部十分的大值点)

​ 如果 $\nabla^2 f(\bf{x}_k) =0$ ,即为不定矩阵,则是多少个鞍点(如
$f(x)=x^3,x=0$时),此时内需考虑三阶导数。

问题为何优化时精选梯度方向,梯度方向为什么是生成最快的取向?

:由Taylor级数展开式的前两项 $f(\bf{x}_k + \bf{\delta}) \approx
f(x_k) +\nabla^Tf(\bf{x}_k) \bf{\delta} $ 可知,当$\delta$
是2个模不变但方向不明显的矢量时,此时 $f(\bf{x}_k + \bf{\delta}) –
f(x_k) \approx \nabla^Tf(\bf{x}_k) \bf{\delta} $ , 可知,当
$\delta = \nabla f(\bf{x}_k)$ 时,$\nabla^Tf(\bf{x}_k)
\bf{\delta} = ||\nabla^2(\bf{x}_k) || $
,此时获得最大的差值,也便是说 $\delta$ 取梯度方向是生成最大。
梯度下落法中的迭代方法正是负梯度方向,因为该方向降低最快!

壹 、背景知识

角点corner:能够将角点看做七个边缘的交叉处,在多个方向上都有较大的生成。具体可由下图中分辨出来:

2. 概率论

随机变量

积累分布函数

概率密度函数

高斯分布

单身同分布定理

  1. Discriminant  Learning Algorithms(判别式方法) and Generative Learning
    Algorithms(生成式方法)

图片 1

3. 线性代数

方阵的特征值(Eigenvalues)与特征向量(Eigenvectors)
$$
\bf{Ax}= \lambda \bf{x}
$$

图片 2

特征向量

特征值和特征向量的几何意义与物理意义**:

矩阵是数学中这几个抽象的贰个概念,广义上咱们得以将矩阵看作1个移动。即矩阵乘法对应了二个变换,是把自由多少个向量变成另3个势头或长度都大概不一样的新向量。在这些变换进程中,原向量主要爆发旋转、伸缩的变化。
要是矩阵对某些或一些向量只爆发伸缩变换,而不对那些向量产生旋转的功效,那么那几个向量就称为那一个矩阵的特征向量,伸缩的比重就是特征值。其大体意义就是运动的动静:特征向量在2个矩阵的功能下作伸缩运动,伸缩的宽度由特征值明确。

图片 3

特征值示意图

特性分解的质量

对于 $\bf{Ax_i} = \lambda \bf{x_i}$
,假若全体的特征值都不雷同,则附和的装有特征向量都线性无关。此时
$\bf{A}$ 能够被对角化为:
$$
\bf{A=V \Lambda V^{-1}}
$$
其中 $\bf{V=[x_1,x_2,\cdots,x_n]}$ , $\Lambda = Diag
(\lambda_1,\lambda_2,\cdots, \lambda_n)$ 。

并不是兼具的方阵都得以被对角化,那里首要考虑对称矩阵($A=
A^T$)的性状分解。

只要1个对称矩阵的特征值都不一样等,则其对应的兼具特征向量正交。($\bf{UUT=UTU=I}$)
$$
\begin{split} \bf{A =U \Lambda U^T=\begin{bmatrix}
u_1,u_2,\cdots,u_n \end{bmatrix} } \begin{bmatrix}\lambda_1 &
&\ & \ddots &\ & & \lambda_n\end{bmatrix} \begin{bmatrix}
\bf{u_1^T\ u_2^T\ \vdots\u_n^T} \end{bmatrix} = \sum_{i=1}^n
\lambda_i \bf{u_iu_i^T}
\end{split}
$$
对称矩阵的特征值都以实数。

二次型**(Quadratic Form):

给定矩阵 $\bf{A} \in R^{m \times n}$ ,函数
$$
\bf{x^TAx=\sum\sum}x_ix_ja_{ij}
$$
被号称二遍型。

固然对于拥有 $\bf{x} \in R^n$ ,有 $\bf{x^TAx} \geq 0$
,则为半正定矩阵,此时 $\lambda(\bf{A}) \geq 0$ .

天性分解的利用——PCA的本质

PCA的真相就是协方差矩阵的对角化

现行反革命广大的形式识别方法有二种,一种是判别式方法;一种是生成式方法。能够那样了然生成式方法主假诺数码是怎么生成的,从计算学的角度而言正是人云亦云数据的遍布distribution;而判别式方法,不管多少是什么样变迁而是通过数量内在的分化直白实行归类恐怕回归。举个例子你现有的task是去辨别一段语音属于哪一类语言。那么生成式模型便是您先让您的model先去学习种种可能性的语言,然后利用你学到的学问来对您要甄其他语音做分类;而判别式模型是依照语音中的lingustic
characteristic语言学特色来分辨那段语音。July_Zh1博文认为生成式方法首要体现同类数据里面包车型大巴相似度,判别式方法反映数据里面的的差别度。Fihser
Kernel结合了两边的差距。PENVISIONML中有尤其理论的解说,有趣味能够参照。

 

4. 凸优化难点

凸集:二个集结中随心所欲两点的连线都在该集合中,则这些集合是贰个凸集。

二个函数 $f$ 是凸函数,满足:

  • 它的定义域是凸集;

  • 对此定义域中的任意两点 $x_1$、 $x_2$, 对任意 $0 \leq \alpha
    \leq 1$, 有

$$
f(\alpha x_1 +(1-\alpha)x_2) \leq \alpha f(x_1) + (1-\alpha)
f(x_2)
$$

机械学习中的凸优化难题是一类格外的优化难题。凸优化难点的款型是
$$
\min_{x\in S}f(x)
$$
当中 $f(x)$是凸函数,可行域 $S$ 是凸集。或等价为:
$$
\min_xf(x) \ \text{subject to} \quad g_i(x) \leq 0, \text{for}
\quad i=1,2,\cdots,k
$$
中间$f(x)$ 和具有的束缚函数 $g_i(x)都是凸函数。

凸优化难题的品质:它的一些最优解一定是全局最优解。

  1. Fisher Information matrix

趣味点interest
point:兴趣点是图像中能够较鲁棒的检查和测试出来的点,它不光局限于角点.
也足以是灰度图像十分的大值可能不大值点等

设一任意变量$x$

贰 、哈Rees角点检查和测试

如果$x$

Harris 算子是 Haris & Stephens 一九九〇年在 “A
Combined Corner and 艾德ge Detector” 中提议的 提议的检查和测试算法,
今后早就变成图像匹配中常用的算法.

为一而再型随机变量,那么$x$的分布$p(x|\theta)$能够用正态分布模拟: $p(x|\theta)

\frac{1}{\sqrt{2\pi\sigma^2}}exp\left\{-\frac{(x-u)^2}{2\sigma^2}\right\}$

假定$x$是离散型随机变量,那么$x$的分布能够能够用项目分布categorical
distribution模拟: $p(x|\theta) = \prod_{k=1}^{K}\theta_k^{x_k}$

式中: $0 \leq \theta_k \geq 1, \sum_k \theta_k = 1$

定义Fisher Score 为: $g(\theta,x) = \triangledown_\theta
ln(p|\mathbf{\theta}) $

定义Fisher Information Matrirx 为: $ F =
E_x\left[g(\theta,x),g(\theta,x)^T\right] $

二、 Fisher Kernel Methods

比方大家磨练多少集为 $ X_t$,对应的Label 为 $S_t
$(±1)(先考虑唯有两类样本的景况) 。设 $X$  为测试样本,$\hat{S}
$为对测试样本预测值。

我们有:$\hat{S}$ = $sign\left (\sum_t S_t\lambda_t
K(X_t,X)\right )$;

而对核函数有以下方式: $ K(X_i,X_i) = \phi_{X_i}^T \phi_{X_j} $.

 对于每三个新样本的展望值$\hat{S}$是由原本样本的Label $S_t$
”加权”获得。而“加权”由两片段组成:1)$\lambda_t$ 2) $K(X_t,X) $

其一Kernel描述的是锻炼样本$X_t$
和测试样本$X$之间的相似度,Kernel有许各个,这里选拔的是Fisher Kernel.
使用$U_x$代表Fisher Score, $F_\lambda$ 代表 Fisher Information
Matrix。

即使将函数数看作一种炫耀格局,那么那么些等式代表着我们不必要将每一个样本真的映射到核空间实行总计,而只要显著核函数对应的$\phi_x$直接对函数进行测算就足以获得将样本映射到核空间的功用。(那也是永葆向量机最重庆大学的trick之一)

$\phi_x$ 正是大家定义的Fisher Vector

对于Fisher Kernel我们有: $\phi_x = F_\lambda^{-\frac{1}{2}}U_x$ 

对应的样本生成模型为:培洛霉素M(Gaussian Mixture Model)
即$X$服从的遍布为土霉素M模型。此时$X = x_1,…,x_N$ 代表培洛霉素M中一密密麻麻变量。

二 、对图像使用Fisher Encoding

Fisher encoding
的主导思想正是用核糖霉素M去创设1个视觉字典,本质上是用似然函数的梯度来宣布一幅图像。

  1. 阿奇霉素M构建视觉词典

对此图像而言$x$能够表示图像的天性(比如SIFT特征),一幅图像有许多风味$X =
x_1,…x_T$ 

对此奇霉素M model  $X$的遍布为:

$$p(X|\omega,\mu,\sum)$$

$\omega,\mu,\sum$分别为奇霉素M中各样特征的权重,均值,协方差。

  1. 计算Fisher Vector

首先定义:

$$L(X|\lambda) = logp(X|\lambda) = \sum_{t=1}^{T}
logp(x_t|\lambda)$$.

图像中种种特征都是并行独立的:

$$p(x_t|\lambda) = \sum_{i=1}^{N}w_ip_i(x_t|\lambda)$$.

$p_i$位GMM中第i个component的pdf,$w_i$为其权值,
$\sum_{i=1}^Nw_i=1$.

每个component $p_i$是种类高斯函数,期pdf如下:

图片 4

D是特征向量的维数,$\sum_i^-一人协方差矩阵

再定义特征$x_t$由第i个Gaussian
component生成概率,那里运用了贝叶斯公式:

$$\gamma_t(i) = p(i|x_t,\lambda) =
\frac{w_ip_i(x_t|\lambda)}{\sum_{j=1}^Nw_jp_j(x_t|\lambda)}$$

接下来对一一参数求偏导:

$$U_x = \left[ \frac{\partial
L(X|\lambda)}{\partial{\omega_i}}, \frac{\partial{L(X|\lambda)}}{\partial{\mu_i^d}}, \frac{\partial{L(X|\lambda)}}{\partial{\sigma_i^d}}
\right]$$

图片 5

那里i是指第i个component,d是指特征$x_t$的维度,偏导是对各样componnet求,各样特征的维度都要总括,$U_X$维度是(2*D+1)*N,又由于$\omega_i$有约束$\sum_i
\omega_i=1$,所以会少多个即兴变量,所以$U_x$ 最后的维度是(2D+1)*N-1.

对下面的多少个公式分别引入四个照应的fisher matrix:

$$ f_{w_i} = T\left(\frac{1}{w_i} + \frac{1}{w_1} \right) $$

$$ f_{u_i^d} = \frac{Tw_i}{\sigma_i^d)^2} $$

$$ f_{\sigma_i^d} = \frac{2T\omega_i}{(\sigma_i^d)^2}$$

以往便可求得归一化的fisher vector.

叁 、怎么着运用vl_feat进行fisher kernel encoding

 

参考资料:

  1. 【Paper】: The Devil is in the details: an evaluation of recent
    feature encoding methods

相比较了在对象识别领域不一致encoding feature 的功能

  1. 何以行使vl_feat计算Fisher Vectors:

http://www.vlfeat.org/overview/encodings.html

  1. 哪些选拔vl_feat实现GMM

http://www.vlfeat.org/overview/gmm.html

4. Fisher information matrix for Gaussian and categorical distributions

https://www.ii.pwr.edu.pl/~tomczak/PDF/%5bJMT%5dFisher\_inf.pdf

  1. Fisher Vector Encoding

http://www.cs.ucf.edu/courses/cap6412/spr2014/papers/Fisher-Vector-Encoding.pdf

  1. 【Paper】: Exploiting generative models in discriminative
    classifiers 

Fisher Kerner 的推理和论述

7【Paper】: Fisher Kernels on Visual Vocabularies for Image
Categorization

http://www.cs.ucf.edu/courses/cap6412/spr2014/papers/2006-034.pdf

  1. 【Paper】: Improving the Fisher Kernel for Large-Scale Image
    Classification

Fisher Kernel的优化

  1. Fisher Vector and Fisher Score

http://blog.csdn.net/happyer88/article/details/46576379

 对于一幅索罗德GB图像大家很很不难获取corner 是种种方向梯度值较大的点, 定义
函数WSSD(Weighted Sum Squared Difference)为:

$$S(x,y) = \sum_{u} \sum_{v}w(u,v)(I((u+x,v+y)-I(u,v))^2 (1)$$

个中$w(u,v)$能够当做采样窗,能够选拔矩形窗函数,也能够挑选高斯窗函数:

图片 6

$I(u+x,v+y)-I(u,v)$能够用作像素值变化量(梯度):

使用泰勒进行:$I(u+x,v+y) \approx I(u,v)+I_x(u,v)x+I_y(u,v)y (2)$

(1)代入(2) $S(x,y) \approx \sum_u \sum_v w(u,v) (I_x(u,v)x +
I_y(u,v)y)^2$

写成$S(x,y) \approx (x,y) A (x,y)^T $

里面 A 为 二阶梯度矩阵(structure tensor/ second-moment matrix)

$$A = \sum_u \sum_v w(u,v) \begin{bmatrix} I_x^2& I_x I_y
\\ I_x I_y & I_y^2 \end{bmatrix} $$

将A定义为哈Rees Matrix,A 的特征值有三种情景:

  1. $\lambda_1 \approx 0, \lambda_2 \approx 0$,那么点$x$不是兴趣点

2. $\lambda_1 \approx 0,
\lambda_2$为三个较大的正数, 那么点$x$为边缘点(edge)

3. $\lambda_1, \lambda_2$都为二个较大的正数, 那么点$x$为角点(corner)

出于特征值的一个钱打二14个结是 computationally expensive,引入如下函数

$M_c = \lambda_1\lambda_2 – \kappa(\lambda_1+\lambda_2)^2 =
det(A) – \kappa trace^2(A) $

为了去除加权常数$\kappa$ 直接总计

$M_{c}^{‘}  =  \frac{det(A)}{trace(A)+\epsilon}$

三 、角点匹配

 哈Rees角点检查和测试仅仅检查和测试出兴趣点地方,可是往往我们实行角点检查和测试的目标是为着拓展图像间的趣味点同盟,大家在每二个兴趣点参预descriptors描述子音信,给出相比较描述子消息的方法.
哈Rees角点的,描述子是由周围像素值块batch的灰度值,以及用于比较归一化的相关矩阵构成。

日常,八个高低同等的像素块I_1(x)和I_2(x) 的相关矩阵为:
$$c(I_1,I_2) = \sum_x f(I_1(x),I_2(x))$$

$f函数随着方法变化而生成,c(I_1,I_2)$值越大,像素块相似度越高.

对相互关矩阵进行归一化获得normalized cross correlation :

$$ncc(I_1,I_2) = \frac{1}{n-2} \sum_x
\frac{(I_1(x)-\mu_1)}{\sigma_1} \cdot
\frac{(I_2(x)-\mu_2)}{\sigma_2}$$

其中$\mu$为像素块的均值,\sigma为专业差.
ncc对图像的亮度变化有所更好的安稳性.

四、python实现

python版本:2.7

依赖包: numpy,scipy,PIL, matplotlib

 

 

 图片:

trees_002.jpg

图片 7

trees003.jpg

图片 8

from PIL import Image
from scipy.ndimage import filters
from numpy import *
from pylab import *

def compute_harris_response(im,sigma=3):
    """Compute the Harris corner detector response function for each 
    pixel in a graylevel image."""

    #derivative
    imx = zeros(im.shape)
    filters.gaussian_filter(im,(sigma,sigma),(0,1),imx)

    imy = zeros(im.shape)
    filters.gaussian_filter(im,(sigma,sigma),(1,0),imy)

    #compute components of the Harris matrix

    Wxx = filters.gaussian_filter(imx*imx,sigma)
    Wxy = filters.gaussian_filter(imx*imy,sigma)
    Wyy = filters.gaussian_filter(imy*imy,sigma)

    #determinant and trace

    Wdet = Wxx*Wyy-Wxy**2
    Wtr = Wxx+Wyy
    return Wdet/Wtr


def get_harris_points(harrisim,min_dist=10,threshold=0.1):
    """Return corners from a Harris response image min_dist is the
    minimum number of pixels separating corners and image boundary."""

    #find top corner candidates above a threshold
    corner_threshold  = harrisim.max()*threshold
    harrisim_t = 1*(harrisim>corner_threshold)

    #get coordiantes of candidate
    coords = array(harrisim_t.nonzero()).T

    #...and their valus
    candicates_values = [harrisim[c[0],c[1]] for c in coords]

    #sort candicates
    index = argsort(candicates_values)

    #sort allowed point loaction in array
    allowed_location = zeros(harrisim.shape)
    allowed_location[min_dist:-min_dist,min_dist:-min_dist] = 1

    #select the best points taking min_distance into account 
    filtered_coords = []
    for i in index:
        if  allowed_location[coords[i,0],coords[i,1]]==1:
            filtered_coords.append(coords[i])
            allowed_location[(coords[i,0]-min_dist):(coords[i,0]+min_dist),
                              (coords[i,1]-min_dist):(coords[i,1]+min_dist)]=0
    return filtered_coords

def plot_harris_points(image,filtered_coords):
    """plots corners found in image."""
    figure
    gray()
    imshow(image)
    plot([p[1] for p in filtered_coords],[p[0] for p in filtered_coords],'*')
    axis('off')
    show()

def get_descriptors(image,filter_coords,wid=5):
    """For each point return pixel values around the point using a neihborhood
    of 2*width+1."""
    desc=[]
    for coords in filter_coords:
        patch = image[coords[0]-wid:coords[0]+wid+1,
                      coords[1]-wid:coords[1]+wid+1].flatten()
        desc.append(patch) # use append to add new elements
    return desc

def match(desc1,desc2,threshold=0.5):
    """For each corner point descriptor in the first image, select its match
    to second image using normalized cross correlation."""

    n = len(desc1[0]) #num of harris descriptors
    #pair-wise distance
    d = -ones((len(desc1),len(desc2)))
    for i in range(len(desc1)):
        for j in range(len(desc2)):
            d1 = (desc1[i]-mean(desc1[i]))/std(desc1[i])
            d2 = (desc2[j]-mean(desc2[j]))/std(desc2[j])
            ncc_value = sum(d1*d2)/(n-1)
            if ncc_value>threshold:
                d[i,j] = ncc_value

    ndx = argsort(-d) 
    matchscores = ndx[:,0]

    return matchscores

def match_twosided(desc1,desc2,threshold=0.5):
    """two sided symmetric version of match()."""
    matches_12 = match(desc1,desc2,threshold)
    matches_21 = match(desc2,desc1,threshold)

    ndx_12 = where(matches_12>=0)[0]
    print ndx_12.dtype
    # remove matches that are not symmetric
    for n in ndx_12:
        if matches_21[matches_12[n]] !=n:
            matches_12[n] = -1
    return matches_12    

def appendimages(im1,im2):
    """Return a new image that appends that two images side-by-side."""

    #select the image with the fewest rows and fill in enough empty rows
    rows1 = im1.shape[0]
    rows2 = im2.shape[0]

    if rows1<rows2:
        im1 = concatenate((im1,zeros((rows2-rows1,im1.shape[1]))),axis=0)
    elif rows1<rows2:
        im2 = concatenate((im2,zeros((rows1-rows2,im2.shape[1]))),axis=0)
    return concatenate((im1,im2),axis=1)
def plot_matches(im1,im2,locs1,locs2,matchscores,show_below=True):
    """show a figure with lines joinging the accepted matches
    Input:im1,im2(images as arrays),locs1,locs2,(feature locations),
          metachscores(as output from 'match()'),
          show_below(if images should be shown matches)."""
    im3 = appendimages(im1,im2)
    if show_below:
        im3 = vstack((im3,im3))

    imshow(im3)

    cols1 = im1.shape[1]
    for i,m in enumerate(matchscores):
        if m>0:
            plot([locs1[i][1],locs2[m][1]+cols1],[locs1[i][0],locs2[m][0]],'c')
    axis('off')

"""
im = array(Image.open('F:lena.bmp').convert('1'))
harrisim = compute_harris_response(im)
filtered_coords = get_harris_points(harrisim,6)
plot_harris_points(im,filtered_coords)
"""

im1 = array(Image.open('trees_002.jpg').convert('L'))
im2 = array(Image.open('trees_003.jpg').convert('L'))

wid = 5

harrisim = compute_harris_response(im1,5)
filtered_coords1 = get_harris_points(harrisim,wid+1)
d1 = get_descriptors(im1,filtered_coords1,wid)

harrisim = compute_harris_response(im2,5)
filtered_coords2 = get_harris_points(harrisim,wid+1)
d2 = get_descriptors(im2,filtered_coords2,wid)

print 'starting matching'
matches = match_twosided(d1,d2)

figure()
gray()
plot_matches(im1,im2,filtered_coords1,filtered_coords2,matches)
show()

 运营结果:

 图片 9

 

相关文章