精华内容
下载资源
问答
  • 拉普拉斯特征选择算法
    千次阅读
    2022-01-26 09:57:21


    拉普拉斯特征映射(Laplacian Eigenmaps,LE)是一种降维方法,之前有讲过一种比较常见的降维算法: PCA

    LE在图嵌入中有一些应用,所以这里总结一下。

    1. 一些定义

    G = ( V , E ) G=(V,E) G=(V,E) ∣ V ∣ = n |V|=n V=n W W W为邻接矩阵, D D D为图的度矩阵(对角阵),有 D i i = ∑ j = 1 n w i j D_{ii}=\sum_{j=1}^nw_{ij} Dii=j=1nwij

    图的拉普拉斯矩阵定义:
    L = D − W L=D-W L=DW
    需要注意的是,对于有向图来说, W W W可以为出度矩阵,也可以为入度矩阵,视具体情况而定。我们下面讨论的都是无向图的拉普拉斯矩阵。

    对于实对称矩阵 L L L,有以下性质:对任意非零列向量 y = [ y 1 , . . . , y n ] T y=[y_1,...,y_n]^T y=[y1,...,yn]T,我们有:
    y T L y = 1 2 ∑ i = 1 n ∑ j = 1 n w i j ( y i − y j ) 2 ≥ 0 y^TLy=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nw_{ij}(y_i-y_j)^2\geq0 yTLy=21i=1nj=1nwij(yiyj)20
    L L L是半正定的。证明如下:
    y T L y = y T D y − y T W y = ∑ i = 1 n D i i y i 2 − ∑ i = 1 n ∑ j = 1 n y i y j w i j = 1 2 ( ∑ i = 1 n D i i y i 2 − 2 ∑ i = 1 n ∑ j = 1 n y i y j w i j + ∑ j = 1 n D j j y j 2 ) = 1 2 ( ∑ i = 1 n ( ∑ j = 1 n w i j ) y i 2 − 2 ∑ i = 1 n ∑ j = 1 n y i y j w i j + ∑ j = 1 n ( ∑ i = 1 n w i j ) y j 2 ) = 1 2 ∑ i = 1 n ∑ j = 1 n w i j ( y i − y j ) 2 \begin{aligned} y^TLy&=y^TDy-y^TWy\\ &=\sum_{i=1}^nD_{ii}y_i^2-\sum_{i=1}^n\sum_{j=1}^ny_iy_jw_{ij}\\ &=\frac{1}{2}(\sum_{i=1}^nD_{ii}y_i^2-2\sum_{i=1}^n\sum_{j=1}^ny_iy_jw_{ij}+\sum_{j=1}^nD_{jj}y_j^2)\\ &=\frac{1}{2}(\sum_{i=1}^n(\sum_{j=1}^nw_{ij})y_i^2-2\sum_{i=1}^n\sum_{j=1}^ny_iy_jw_{ij}+\sum_{j=1}^n(\sum_{i=1}^nw_{ij})y_j^2)\\ &=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nw_{ij}(y_i-y_j)^2 \end{aligned} yTLy=yTDyyTWy=i=1nDiiyi2i=1nj=1nyiyjwij=21(i=1nDiiyi22i=1nj=1nyiyjwij+j=1nDjjyj2)=21(i=1n(j=1nwij)yi22i=1nj=1nyiyjwij+j=1n(i=1nwij)yj2)=21i=1nj=1nwij(yiyj)2

    2. 矩阵的迹求导

    对LE的推导需要补充一些数学知识:
    ∂ t r ( A T B A ) ∂ A = ( B + B T ) A   ∂ t r ( A B A T C ) ∂ A = C A B + C T A B T \frac{\partial tr(A^TBA)}{\partial A}=(B+B^T)A\\ \ \\ \frac{\partial tr(ABA^TC)}{\partial A}=CAB+C^TAB^T Atr(ATBA)=(B+BT)A Atr(ABATC)=CAB+CTABT

    3. LE

    3.1 目标函数

    在图嵌入中,我们的目的是得到每个顶点的低维向量表示,假设嵌入向量维度为 m m m

    LE的思想:如果两个数据实例 i i i j j j很相似,那么它们在降维后的目标子空间中应该尽量接近。

    而在图嵌入中,衡量两个节点是否相似的最直接度量为一阶邻近度,两个节点 v i v_i vi v j v_j vj间的一阶邻近度即两个节点间相连边的权重。

    一阶邻近度通常意味着真实世界网络中两个节点的相似性。正所谓近朱者赤近墨者黑,比如在社交网络中成为朋友的人往往有相似的兴趣爱好,又比如万维网上相互链接的网页往往谈论类似的话题。由于这种重要性,现有的许多图嵌入算法在设计目标函数时都会保持一阶邻近度。

    因此,LE的思想可以重新表述为:如果两个节点在原始图中彼此相邻,那么它们的低维嵌入向量应该彼此接近。

    我们设节点 v i v_i vi v j v_j vj的向量表示分别为 y i ∈ R m y_i\in R^m yiRm y j ∈ R m y_j\in R^m yjRm,鉴于此,我们就可以得出LE的目标函数:
    m i n    1 2 ∑ i = 1 n ∑ j = 1 n ∣ ∣ y i − y j ∣ ∣ 2 w i j min\ \ \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n||y_i-y_j||^2w_{ij} min  21i=1nj=1nyiyj2wij
    从目标函数可以看出,如果两个节点 v i v_i vi v j v_j vj的一阶邻近度 w i j w_{ij} wij较大(很相似),那么我们在最小化目标函数时,就会更多地考虑二者间的差异。

    假设 y i y_i yi是一个列向量,那么 y i 2 = y i T y i y_i^2=y_i^Ty_i yi2=yiTyi

    下面开始对目标函数进行化简:
    1 2 ∑ i = 1 n ∑ j = 1 n ∣ ∣ y i − y j ∣ ∣ 2 w i j = 1 2 ∑ i = 1 n ∑ j = 1 n ( y i T y i w i j − 2 y i y j w i j + y j T y j w i j ) w i j = 1 2 ∑ i = 1 n ( ∑ j = 1 n w i j ) y i T y i − ∑ i = 1 n ∑ j = 1 n y i y j w i j + 1 2 ∑ j = 1 n ( ∑ i = 1 n w i j ) y j T y j = 1 2 ∑ i = 1 n D i i y i T y i − ∑ i = 1 n ∑ j = 1 n y i y j w i j + 1 2 ∑ i = 1 n D i i y i T y i = ∑ i = 1 n D i i y i T y i − ∑ i = 1 n ∑ j = 1 n y i y j w i j = t r ( Y T D Y ) − t r ( Y T W Y ) = t r ( Y T ( D − W ) Y ) = t r ( Y T L Y ) \begin{aligned} &\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n||y_i-y_j||^2w_{ij}\\ =&\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n(y_i^Ty_iw_{ij}-2y_iy_jw_{ij}+y_j^Ty_jw_{ij})w_{ij}\\ =&\frac{1}{2}\sum_{i=1}^n(\sum_{j=1}^nw_{ij})y_i^Ty_i-\sum_{i=1}^n\sum_{j=1}^ny_iy_jw_{ij}+\frac{1}{2}\sum_{j=1}^n(\sum_{i=1}^nw_{ij})y_j^Ty_j\\ =&\frac{1}{2}\sum_{i=1}^nD_{ii}y_i^Ty_i-\sum_{i=1}^n\sum_{j=1}^ny_iy_jw_{ij}+\frac{1}{2}\sum_{i=1}^nD_{ii}y_i^Ty_i\\ =&\sum_{i=1}^nD_{ii}y_i^Ty_i-\sum_{i=1}^n\sum_{j=1}^ny_iy_jw_{ij}\\ =&tr(Y^TDY)-tr(Y^TWY)\\ =&tr(Y^T(D-W)Y)\\ =&tr(Y^TLY) \end{aligned} =======21i=1nj=1nyiyj2wij21i=1nj=1n(yiTyiwij2yiyjwij+yjTyjwij)wij21i=1n(j=1nwij)yiTyii=1nj=1nyiyjwij+21j=1n(i=1nwij)yjTyj21i=1nDiiyiTyii=1nj=1nyiyjwij+21i=1nDiiyiTyii=1nDiiyiTyii=1nj=1nyiyjwijtr(YTDY)tr(YTWY)tr(YT(DW)Y)tr(YTLY)
    其中, Y = ( y 1 , . . . , y n ) T Y=(y_1,...,y_n)^T Y=(y1,...,yn)T t r ( A ) tr(A) tr(A)表示对矩阵 A A A求秩(对角线之和)。

    3.2 约束条件

    考虑到目标函数:
    m i n    1 2 ∑ i = 1 n ∑ j = 1 n ∣ ∣ y i − y j ∣ ∣ 2 w i j min\ \ \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n||y_i-y_j||^2w_{ij} min  21i=1nj=1nyiyj2wij
    我们不妨设想一种极端情况,假设所有节点都映射到了同一个位置,也就是所有节点的嵌入向量 y y y相同,那么此时目标函数肯定有最小值0。又比如我们就假设所有节点的嵌入向量全部为0向量,此时目标函数也有最小值0。

    以上两种情况是毫无意义的。此外,在上述情况下, y y y的维度也是任意的。因此,为了得到唯一解,我们需要对节点最终的嵌入向量 y y y做一些限制。

    一个最简单的限制就是:我们希望最终得到的所有节点的嵌入向量 y y y能够尽可能地去填充 R m R^m Rm空间,而不是挤在一起。举个例子,假设 m = 2 m=2 m=2,那么我们不希望所有节点的嵌入向量 y y y(一个点)挤在一起,或者就只是聚集在某一条直线附近,而是尽可能的去散开,因为如果聚在一起就表示图中所有节点具有类似的性质,这显然是不科学的,我们只是需要邻接的节点的嵌入向量相似即可。

    为了理解限制条件,我查阅了拉普拉斯特征映射的论文,论文中给出的限制条件为:
    Y T D Y = I Y^TDY=I YTDY=I
    原文中关于约束条件 Y T D Y = 1 Y^TDY=1 YTDY=1的描述为: Y T D Y = 1 Y^TDY=1 YTDY=1这一限制条件删除了嵌入中的任意比例因子。也就是说,每一个 y i y_i yi的尺度被固定了。

    至于为什么选则 D D D而不是其他矩阵,原文中给出的解释为:度矩阵 D D D可以很好地提供节点自身的一个度量。我们可以这样理解: D D D可以描述每一个节点在graph中的重要性,如果我们使用 D D D y y y的尺度进行限制,那么我们可以使得 y y y R m R^m Rm上分布更加均匀,也就是前面我们提到的:我们希望最终得到的所有节点的嵌入向量 y y y能够尽可能地去填充 R m R^m Rm空间,而不是挤在一起。

    3.3 优化

    有了 y i T D y i = 1 y_i^TDy_i=1 yiTDyi=1这一限制条件后,我们可以构造拉格朗日函数如下:
    L = t r ( Y T L Y ) − ∑ i = 1 n λ i ( 1 − y i T D y i ) L=tr(Y^TLY)-\sum_{i=1}^n\lambda_i(1-y_i^TDy_i) L=tr(YTLY)i=1nλi(1yiTDyi)
    我们令 Λ \Lambda Λ为一个对角阵,对角阵上的元素 Λ i i = λ i \Lambda_{ii}=\lambda_i Λii=λi,因此,上述拉格朗日函数可以变为矩阵形式:
    L = t r ( Y T L Y ) − t r ( Λ ( Y T D Y − I ) ) L=tr(Y^TLY)-tr(\Lambda(Y^TDY-I)) L=tr(YTLY)tr(Λ(YTDYI))
    对于第一项,由第二节中求导公式(1)可知:
    ∂ t r ( Y T L Y ) ∂ Y = ( L + L T ) Y \frac{\partial tr(Y^TLY)}{\partial Y}=(L+L^T)Y Ytr(YTLY)=(L+LT)Y
    对于第二项,由第二节中求导公式(2)可知:
    ∂ t r ( Λ Y T D Y ) ∂ Y = D Y Λ + D T Y Λ T \frac{\partial tr(\Lambda Y^TDY)}{\partial Y}=DY\Lambda+D^TY\Lambda^T Ytr(ΛYTDY)=DYΛ+DTYΛT
    因此我们有:
    ∂ L ∂ Y = L Y + L T Y + D Y Λ + D T Y Λ T = 2 L Y + 2 D Y Λ = 0 \begin{aligned} \frac{\partial L}{\partial Y}&=LY+L^TY+DY\Lambda+D^TY\Lambda^T\\ &=2LY+2DY\Lambda=0 \end{aligned} YL=LY+LTY+DYΛ+DTYΛT=2LY+2DYΛ=0
    解得:
    L Y = − D Y Λ LY=-DY\Lambda LY=DYΛ
    写成一般形式为: L y i = λ i D y i Ly_i=\lambda_iDy_i Lyi=λiDyi

    3.4 广义特征值问题

    上述问题转为广义特征值求解问题:
    L y = λ D y Ly=\lambda Dy Ly=λDy

    所谓广义特征值问题:对于实对称矩阵 A A A和实对称正定矩阵 B B B,如果有非零解 x x x满足:
    A x = λ B x Ax=\lambda Bx Ax=λBx
    则称 λ \lambda λ A A A相对于 B B B的特征值。

    在本文中, L L L是实对称矩阵, D D D首先是实对称矩阵,其次 D D D也是正定的,这点很好证明,便不再叙述。

    那么到底如何求解广义特征值文题呢?我们知道,一般特征值的表达形式为:
    A x = λ x Ax=\lambda x Ax=λx
    对于一般特征值求解,我们可以转为:
    ( A − λ E ) x = 0 (A-\lambda E)x=0 (AλE)x=0

    那么我们可以尝试将广义特征值问题转为此类问题。

    首先,我们将矩阵 B B B进行Cholesky分解:
    B = G G T B=GG^T B=GGT
    其中 G G G为下三角矩阵。

    然后有:
    A x = λ G G T x Ax=\lambda GG^Tx Ax=λGGTx
    两边乘上 G − 1 G^{-1} G1
    G − 1 A x = λ G T x G^{-1}Ax=\lambda G^Tx G1Ax=λGTx
    然后:
    G − 1 A x = λ G T x   G − 1 A ( ( G T ) − 1 G T ) x = λ G T x \begin{aligned} G^{-1}Ax&=\lambda G^Tx \ \\ G^{-1}A((G^T)^{-1}G^T)x&=\lambda G^Tx \end{aligned} G1AxG1A((GT)1GT)x=λGTx =λGTx
    这时两边都出现了 G T x G^Tx GTx,我们将其合并:
    ( G − 1 A ( G T ) − 1 ) ( G T x ) = λ ( G T x ) (G^{-1}A(G^T)^{-1})(G^Tx)=\lambda (G^Tx) (G1A(GT)1)(GTx)=λ(GTx)
    我们令:
    G − 1 A ( G T ) − 1 = T   G T x = s \begin{aligned} G^{-1}A(G^T)^{-1}&=T \ \\ G^Tx&=s \end{aligned} G1A(GT)1GTx=T =s
    于是原问题变为一般特征值的求解问题:
    T s = λ s Ts=\lambda s Ts=λs
    然后,我们就能求出矩阵 T T T的特征值 s s s,进而解出 x x x

    3.5 结果

    经过3.4之后,得到了 L y i = λ D y i Ly_i=\lambda Dy_i Lyi=λDyi中的解向量 y i y_i yi然后选取最小的 m m m个非零特征值对应的特征向量作为节点的嵌入向量。

    为什么要选取非零特征值的特征向量?根据 L L L的性质, L L L的行和为0。因此,从 L y i = λ D y i Ly_i=\lambda Dy_i Lyi=λDyi可以看出, L L L具有广义特征值0和对应的特征向量 1 = ( 1 , . . . , 1 ) T 1=(1,...,1)^T 1=(1,...,1)T,由如果 1 = ( 1 , . . . , 1 ) T 1=(1,...,1)^T 1=(1,...,1)T被选中,那么每一个节点的嵌入向量中的某一维度将全是1,那么嵌入向量将退化到更低一维的空间中。

    为什么要选取 m m m个最小的特征值对应的特征向量?参考网上说法:我们将 L Y = − D Y Λ LY=-DY\Lambda LY=DYΛ代回到原目标函数 t r ( Y T L Y ) tr(Y^TLY) tr(YTLY)中,可以得到:
    m i n    t r ( − Y T D Y Λ ) min\ \ tr(-Y^TDY\Lambda) min  tr(YTDYΛ)
    又由于有限制条件:
    Y T D Y = I Y^TDY=I YTDY=I
    所以最终目标函数为:
    m i n    t r ( − Λ ) min \ \ tr(-\Lambda) min  tr(Λ)
    这里 t r ( Λ ) = λ 1 + . . . + λ n tr(\Lambda)=\lambda_1+...+\lambda_n tr(Λ)=λ1+...+λn,目标函数即为特征值之和,为了使得目标函数最小化,当然应该选择最小的 m m m个特征值。

    更多相关内容
  • 拉普拉斯分数(Laplacian score)是由 He 等人提出的一种经典的无监督特征选择算法。 内容主要为:Laplacian score的Matlab实现 其中,main文件为示例文件,可以通过运行main文件来得到对应的Laplacian分数。具体功能...
  • 拉普拉斯特征映射算法,简单易懂,降维处理,求流形的必备程序
  • 研究拉普拉斯特征映射算法(Laplacian eigenmap,LE)对离群点的敏感性,提出一种具有鲁棒性的拉普拉斯特征映射算法(robust Laplacian eigenmap,RLE)。该方法在离群点检测的基础上,利用鲁棒PCA算法(robust PCA...
  • 基于监督拉普拉斯特征映射算法的人脸识别.pdf
  • 提出了一种面向行为识别的拉普拉斯特征映射算法的改进方法。首先,将Kinect提供的关节点数据作为姿态特征,采用Levenstein距离改进流形学习算法中的拉普拉斯特征映射算法,并映射到二维空间得到待识别行为的嵌入空间...
  • 拉普拉斯特征图是一种流形降维方法。主要分为四个步骤 1、邻接图的构建。可以通过KNN或半径法来确定邻居样本点。对每个邻居样本点都连接一条边 2、选定边的权值。可以通过heat kernel法()确定,也可以直接设为1 ...

    拉普拉斯特征图是一种流形降维方法。主要分为四个步骤

    1、邻接图的构建。可以通过KNN或半径法来确定邻居样本点。对每个邻居样本点都连接一条边

    2、选定边的权值。可以通过heat kernel法(w_{ij}=exp(-\frac{||x_i-x_j||^2}{t}))确定,也可以直接设为1

    3、特征值分解

    Lf=\lambda Df

    D是对角权值矩阵,D_{ii}=\sum_jw_{ji}

    4、低维嵌入

    L就是拉普拉斯矩阵,L = D - W

    对其进行特征值分解,假设降到d'维,将分解后的特征值排序,第一个特征值应该等于0,从第二个特征值开始,依次选取d'个特征值对应的特征向量,构成特征空间。

    下面上代码。我运用的是瑞士卷数据集,适用于流形降维。

    import matplotlib
    import matplotlib.pyplot as plt
    from numpy import *
    import numpy as np
    from sklearn import datasets
    
    # Adjacency graph construction with KNN method
    # 参考《机器学习实战》
    def KNN(inX, dataSet, k):
        dataSetSize = dataSet.shape[0]
        diffMat = tile(inX,(dataSetSize,1))-dataSet
        sqDiffMat = array(diffMat)**2
        sqDistances = sqDiffMat.sum(axis=1)
        distances = sqDistances**0.5
        sortedDistIndicies = distances.argsort()
        return sortedDistIndicies[0:k]
    
    def LaplacianEigen(dataMat, k, t):  # t是权值公示中指数部分的分母
        m = shape(dataMat)[0]
        W = mat(zeros([m,m]))  # 权重矩阵
        D = mat(zeros([m,m]))  # 特征值分解用到
        # Choosing the weight
        for i in range(m):
            kIndex = KNN(dataMat[i,:],dataMat,k)
            for j in range(k):
                sqDiffVec = dataMat[i,:]-dataMat[kIndex[j],:]  # X_i-X_j
                sqDiffVec = array(sqDiffVec)**2
                sqDistances = sqDiffVec.sum()
                W[i,kIndex[j]] = math.exp(-sqDistances/t)  # 求W_ij
                D[i,i] += W[i,kIndex[j]]
        L = D-W
        Dinv = np.linalg.inv(D)
        X = np.dot(D.I,L)
        lamda,f = np.linalg.eig(X)  # Eigen decomposition
        return lamda, f

    运行结果

    展开全文
  • 基于Matlab的拉普拉斯图像增强算法与设计.pdf
  • 今天小编就为大家分享一篇python实现拉普拉斯特征图降维示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 简单图像融合(加权平均、像素选大、像素选小)算法拉普拉斯金字塔算法的Matlab实现 GUI界面 简单图像融合(加权平均、像素选大、像素选小)算法拉普拉斯金字塔算法的Matlab实现 GUI界面
  • 拉普拉斯加权聚类算法.pdf
  • Visual C++数字图像处理典型算法及实现,拉普拉斯锐化算法实现
  • 拉普拉斯特征映射

    2019-01-07 15:28:42
    拉普拉斯特征映射。机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,...
  • 在该算法框架下,进一步提出的高斯差分算子,在计算法向拉普拉斯时对于特征线的梯度方向和切线方向做不同的过滤处理,从而更好地反映特征线的走向。算法更加鲁棒,对于包含几何噪声和非均匀网格化的三维模型,其生成...
  • 使用USM算法锐化图像的MATLAB程序,使用了模板相乘卷积的原理,其中更改模板便可以更改算法,比如使用拉普拉斯锐化模板便就改造成了拉普拉斯滤波,可改造性及移植性较好,注释较多,适合初学者。
  • 在经典的拉普拉斯图像锐化中,所有像素都被一一处理,这导致大量的计算。 在CPU上进行传统的拉普拉斯锐化处理非常耗时,特别是对于那些大图片... 实验结果证明,两种新算法在计算速度方面均优于传统的基于OpenCV算法
  • 这些天在看论文的时候,了解到这么一个强大的算法,打算写篇文记录下心得吧。一些图像融合算法图像拼接主要可以分为两个步骤:图像配准和图像融合。其中图像配准的目的是将图一场景中不同视角的图像...

    继图像拼接的课程设计之后,对这方面依旧十分感兴趣。很巧合的是,数图老师表示刚好手上有这么一个项目,要用到这方面的知识,可以让我去作为毕业设计。虽然距离毕业还远,不过如果能选到一个感兴趣并且有一定深度的题目还是很好的。这些天在看论文的时候,了解到这么一个强大的算法,打算写篇文记录下心得吧。

    一些图像融合算法

    图像拼接主要可以分为两个步骤:图像配准和图像融合。其中图像配准的目的是将图一场景中不同视角的图像投影到同一平面并进行对准。比如我之前这篇博客中使用SIFT特征检测和单应矩阵的目的,就是进行图像配准。

    图像配准

    经过图像配准之后,就需要进行图像融合。而图像融合的目的就是使两幅图像的重叠区域过渡自然且平滑。在上图中,可以看到明显的边界,这对拼接来说是无法接受的。这主要是因为外部亮度的变化(天空飘过了一朵萌萌的云彩?)以及曝光时相机参数不一致导致的。要消除或缓和这种现象,就需要进行图像融合。

    主流的图像融合算法有:

    1)加权平均法。这个很好理解,即简单的使用加权的方式从左边过渡到右边。这种方法效果一般,但算法实现极其简单,速度快。课设时我用的就是这个方法。

    2)羽化算法 。这种方法过渡会比加权平均法自然,但会造成不好的模糊效果。

    3)拉普拉斯金字塔融合。有的地方也称为多分辨率融合算法。这种方法是将图像建立一个拉普拉斯金字塔,其中金字塔的每一层都包含了图像不同的频段。分开不同频段进行融合效果出奇的好。这也是本文主要介绍的方法。

    高斯金字塔、拉普拉斯金字塔

    之前在写SIFT相关博客的时候说到过高斯金字塔。图像金字塔的意思无非就是对原图进行下采样,然后塞到一个C++的Vector或者其他什么语言中的数组里。在可视化的时候,最大的图像放在最下面,最小的图像放在最上面,所以称为图像金字塔。

    图像金字塔

    而高斯金字塔的每一层的构建步骤分为两步:首先对下一层的图像进行高斯模糊。这个步骤相信读者都了解,是图像处理中最基本的概念。然后删除模糊后的图像的偶数行和列,就得到了当前层的图像了。不断进行这个步骤,最终就得到了高斯金字塔。

    拉普拉斯金字塔的构造需要用到高斯金字塔。拉普拉斯金字塔第i层的数学定义如下

    每一层的定义

    意思是拉普拉斯金字塔每一层的图像为同一层高斯金字塔的图像减去上一层的图像进行上采样并高斯模糊的结果。说的有点绕,可以看网上的这幅图进行理解。

    高斯金字塔与拉普拉斯金字塔的关系

    算法原理

    1)首先建立两幅图像高斯金字塔,然后建立一定层数的拉普拉斯金字塔。拉普拉斯金字塔的层数越高,融合效果越好。层数N作为一个参数。

    2)传入一个mask掩膜,代表了融合的位置。比如说想在两图的中间进行融合,那么掩膜图像的左半为255,右半为0,反过来是一样的。根据这个mask建立一个高斯金字塔,用于后续融合,层数为N+1。

    3)根据mask将两幅图像的拉普拉斯金字塔的图像进行相加,mask为权值。相加的结果即为一个新的金字塔。同时,两幅图像的高斯金字塔的N+1层也进行这个操作,记这个图像为IMG1。

    4)根据这个新的金字塔重建出最终的图像,重建的过程跟一般的拉普拉斯金字塔一样。首先对IMG1上采样,然后跟新金字塔的顶层相加,得到IMG2。IMG2进行上采样后跟下一层相加,得到IMG3。重复这个过程,最终得到的结果就是拉普拉斯金字塔融合算法的结果。

    因为mask建立金字塔的过程中使用了高斯模糊,所以融合的边缘是比较平滑的。

    算法实现

    类实现主要参考其他博客

    /**************************************************************

    * Created by 杨帮杰 on 1/1/2019

    * Right to use this code in any way you want without

    * warranty, support or any guarantee of it working

    * E-mail: yangbangjie1998@qq.com

    * Association: SCAU 华南农业大学

    **************************************************************/

    #include

    #include

    #include

    using namespace std;

    using namespace cv;

    #define IMG1_PATH "/home/jacob/图片/blend1.jpg"

    #define IMG2_PATH "/home/jacob/图片/blend2.jpg"

    /**

    * @brief The LaplacianBlending class

    * @private leftImg & rightImg 用于拼接的左图和右图

    * @private blendMask 用于融合的掩膜,值为加权平均的系数

    * @ref https://blog.csdn.net/abcjennifer/article/details/7628655

    */

    class LaplacianBlending {

    private:

    Mat leftImg;

    Mat rightImg;

    Mat blendMask;

    //Laplacian Pyramids

    vector leftLapPyr, rightLapPyr, resultLapPyr;

    Mat leftHighestLevel, rightHighestLevel, resultHighestLevel;

    //mask为三通道方便矩阵相乘

    vector maskGaussianPyramid;

    int levels;

    void buildPyramids()

    {

    buildLaplacianPyramid(leftImg, leftLapPyr, leftHighestLevel);

    buildLaplacianPyramid(rightImg, rightLapPyr, rightHighestLevel);

    buildGaussianPyramid();

    }

    void buildGaussianPyramid()

    {

    //金字塔内容为每一层的掩模

    assert(leftLapPyr.size()>0);

    maskGaussianPyramid.clear();

    Mat currentImg;

    cvtColor(blendMask, currentImg, CV_GRAY2BGR);

    //保存mask金字塔的每一层图像

    maskGaussianPyramid.push_back(currentImg); //0-level

    currentImg = blendMask;

    for (int l = 1; l

    Mat _down;

    if (leftLapPyr.size() > l)

    pyrDown(currentImg, _down, leftLapPyr[l].size());

    else

    pyrDown(currentImg, _down, leftHighestLevel.size()); //lowest level

    Mat down;

    cvtColor(_down, down, CV_GRAY2BGR);

    //add color blend mask into mask Pyramid

    maskGaussianPyramid.push_back(down);

    string winName = to_string(l);

    imshow(winName,down);

    currentImg = _down;

    }

    }

    void buildLaplacianPyramid(const Mat& img, vector& lapPyr, Mat& HighestLevel)

    {

    lapPyr.clear();

    Mat currentImg = img;

    for (int l = 0; l

    Mat down, up;

    pyrDown(currentImg, down);

    pyrUp(down, up, currentImg.size());

    Mat lap = currentImg - up;

    lapPyr.push_back(lap);

    currentImg = down;

    }

    currentImg.copyTo(HighestLevel);

    }

    Mat reconstructImgFromLapPyramid()

    {

    //将左右laplacian图像拼成的resultLapPyr金字塔中每一层

    //从上到下插值放大并与残差相加,即得blend图像结果

    Mat currentImg = resultHighestLevel;

    for (int l = levels - 1; l >= 0; l--)

    {

    Mat up;

    pyrUp(currentImg, up, resultLapPyr[l].size());

    currentImg = up + resultLapPyr[l];

    }

    return currentImg;

    }

    void blendLapPyrs()

    {

    //获得每层金字塔中直接用左右两图Laplacian变换拼成的图像resultLapPyr

    resultHighestLevel = leftHighestLevel.mul(maskGaussianPyramid.back()) +

    rightHighestLevel.mul(Scalar(1.0, 1.0, 1.0) - maskGaussianPyramid.back());

    for (int l = 0; l

    {

    Mat A = leftLapPyr[l].mul(maskGaussianPyramid[l]);

    Mat antiMask = Scalar(1.0, 1.0, 1.0) - maskGaussianPyramid[l];

    Mat B = rightLapPyr[l].mul(antiMask);

    Mat blendedLevel = A + B;

    resultLapPyr.push_back(blendedLevel);

    }

    }

    public:

    LaplacianBlending(const Mat& _left, const Mat& _right, const Mat& _blendMask, int _levels) ://construct function, used in LaplacianBlending lb(l,r,m,4);

    leftImg(_left), rightImg(_right), blendMask(_blendMask), levels(_levels)

    {

    assert(_left.size() == _right.size());

    assert(_left.size() == _blendMask.size());

    //创建拉普拉斯金字塔和高斯金字塔

    buildPyramids();

    //每层金字塔图像合并为一个

    blendLapPyrs();

    };

    Mat blend()

    {

    //重建拉普拉斯金字塔

    return reconstructImgFromLapPyramid();

    }

    };

    Mat LaplacianBlend(const Mat &left, const Mat &right, const Mat &mask)

    {

    LaplacianBlending laplaceBlend(left, right, mask, 10);

    return laplaceBlend.blend();

    }

    int main() {

    Mat leftImg = imread(IMG1_PATH);

    Mat rightImg = imread(IMG2_PATH);

    int hight = leftImg.rows;

    int width = leftImg.cols;

    Mat leftImg32f, rightImg32f;

    leftImg.convertTo(leftImg32f, CV_32F);

    rightImg.convertTo(rightImg32f, CV_32F);

    //创建用于混合的掩膜,这里在中间进行混合

    Mat mask = Mat::zeros(hight, width, CV_32FC1);

    mask(Range::all(), Range(0, mask.cols * 0.5)) = 1.0;

    Mat blendImg = LaplacianBlend(leftImg32f, rightImg32f, mask);

    blendImg.convertTo(blendImg, CV_8UC3);

    imshow("left", leftImg);

    imshow("right", rightImg);

    imshow("blended", blendImg);

    waitKey(0);

    return 0;

    }

    左图

    右图

    融合结果

    后记

    可以看到,融合结果简直惊艳。话说写完这篇博客的时候已经是2019的元旦了,如果你能看到这里,就祝你新年快乐吧~~

    展开全文
  • 为了验证和改进使用Gaver-Stehfest算法获得的反演解,对数字反演进行了直接拉普拉斯变换,以与原始函数进行比较。 数值直接拉普拉斯变换是使用合成辛普森规则实现的。 研究涉及周期和振荡函数的具有挑战性的数值...
  • 针对拉普拉斯特征映射(LE)只能保持局部近邻信息,对新测试点无法描述的不足,提出一种基于二维核主成分分析的拉普拉斯特征映射算法(2D-KPCA LE)。与核二维主成分分析算法(K2DPCA)不同,该算法首先对训练样本...
  • 1.领域:matlab,基于高斯金字塔和拉普拉斯金字塔完成图像融合算法 2.内容:题目,基于高斯金字塔和拉普拉斯金字塔完成图像融合算法matlab仿真.+代码操作视频 3.用处:用于基于高斯金字塔和拉普拉斯金字塔完成...
  • 流行学习算法拉普拉斯特征映射,特征约简
  • 降维分为:特征选择 和 特征提取 特征选择:是从含有冗余信息以及噪声信息的数据中找出主要变量; 特征提取:是去掉原来的数据,生成新的变量,可以寻找数据内部的本质结构特征。 降维的过程是通过对输入的原始数据...

    高维数据降维之拉普拉斯特征映射 LE

    高维数据降维是指采用某种映射方法,降低随机变量的数量,例如将数据点从高维空间映射到低维空间中,从而实现维度减少。

    降维分为:特征选择 和 特征提取
    特征选择:是从含有冗余信息以及噪声信息的数据中找出主要变量;
    特征提取:是去掉原来的数据,生成新的变量,可以寻找数据内部的本质结构特征。

    降维的过程是通过对输入的原始数据特征进行学习,得到一个映射函数,实现将输入样本映射后到低维空间中之后,原始数据特征并没有明显的损失,通常情况下新空间的维度要小于原空间的维度。目前大部分降维算法是处理向量形式的数据。

    拉普拉斯特征映射 LE

    拉普拉斯特征映射 LE 解决问题的思路和 LLE 相似,是一种基于图的降维算法,使相互关联的点在降维后的空间中尽可能地靠近。

    通过构建邻接矩阵为 W W W 的图来重构数据流形的局部结构特征,如果两个数据实例 i i i j j j 很相似,那么 i i i j j j 在降维后目标子空间中也应该接近。设数据实例的数目为 n n n ,目标子空间(即降维后的维度)为 m m m ,定义 n × m n\times m n×m 大小的矩阵 Y Y Y ,其中每一个行向量 y i y_i yi 是数据实例 i i i 在目标子空间中的向量表示。为了让样本 i i i j j j 在降维后的子空间里尽量接近,优化的目标函数为:
    m i n ∑ ∣ ∣ y i − y j ∣ ∣ 2 w i j min\sum||y_{i}-y_{j}||^{2}w_{ij} minyiyj2wij ,也就是 i 和 j 距离平方求和乘以权重的最小值!

    权重值可以是图中样本间的连接数来度量。

    化简: L y = λ D y L_{y} = \lambda D_{y} Ly=λDy

    其中 L 和 D 均为对称矩阵,由于目标函数是求最小值,所以通过求得 m 个最小非零特征值所对应的特征向量,即可达到降维的目的。

    拉普拉斯特征映射基本步骤:

    (1) 构建无向图,将所有的样本以点连接成一个图,例如使用 KNN 算法,将每个点最近的 k 个点进行连接,其中 k 是自己设定的值;

    (2) 构建图的权值矩阵,通过点之间的关联程度来确定点与点之间的权重大小,例如,两个点之间如果相连接,则权重为1,否则为0;

    (3) 特征映射,通过公式 L y = λ D y L_{y} = \lambda D_{y} Ly=λDy 计算拉普拉斯矩阵 L 的特征向量和特征值,用最小的 m 个非零特征值对应的特征向量作为降维的结果。

    例子

    # 例子:
    from sklearn import manifold, datasets
    import numpy as np
    import matplotlib.pyplot as plt
    
    X,color = datasets.make_swiss_roll(n_samples = 1500)
    
    ax = plt.subplot(projection = '3d')
    # 原始数据
    ax.scatter(X[:,0],X[:,1],X[:,2],c = color, cmap=plt.cm.Spectral)  
    # 调整三维视角
    ax.view_init(4,-50)  
    

    在这里插入图片描述

    # 2维10个近邻点
    se = manifold.SpectralEmbedding(n_components=2,n_neighbors=10)
    # 将原始样本投射到新的子空间中
    Y = se.fit_transform(X)  
    
    # LE 降维后可视化
    plt.scatter(Y[:,0],Y[:,1],c=color,cmap=plt.cm.Spectral)
    

    在这里插入图片描述
    对比原始样本在三维空间和降维之后在二维空间的分布情况,可以看到,在高维和低维空间中的样本分布形状发生了变化,但降维后样本之间的联系并没有改变!!!

    展开全文
  • 目的进一步提高色域映射质量,深入研究空间色域映射算法。方法利用高斯拉普拉斯算子...结论基于高斯拉普拉斯算子的色域映射算法能够提高图像的映射质量,但是空间色域映射算法映射质量并不一定优于非空间类色域映射算法
  • 流形学习之拉普拉斯特征映射

    千次阅读 2021-01-29 01:43:29
    接着,我们重点介绍拉普拉斯特征映射算法;最后,本文将给出拉普拉斯特征特征映射算法代码。 流形学习 流形学习是一种非线性降维方法,能够从高维数据中发现低维流形结构,得到高维和低维之间的映射关系,从而实现...
  • 利用MATLAB实现拉普拉斯贝叶斯算法,用在压缩感知中,仿真了信号重建的过程,对该过程有进一步的认识
  • 基于Matlab的拉普拉斯图像增强算法与设计.rar
  • 基于拉普拉斯收缩的三维模型骨架提取算法及其Matlab实现,冀伟杰,谢鑫,介绍了三维模型骨架的概念及其数学表达,介绍了几种常用三维模型骨架提取算法的原理及适用性。选择基于拉普拉斯收缩的三维模型骨
  • 1.领域:matlab,拉普拉斯金字塔的图像融合算法 2.内容:基于拉普拉斯金字塔的图像融合算法matlab仿真+代码操作视频 3.用处:用于拉普拉斯金字塔的图像融合算法编程学习 4.指向人群:本硕博等教研学习使用 5....
  • 针对基于图的多标签特征选择方法忽略图拉普拉斯矩阵的动态变化,且利用逻辑标签来指导特征选择过程而丢失标签信息等问题,提出了一种基于动态图拉普拉斯矩阵和实值标签的多标签特征选择方法。该方法利用特征矩阵的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,085
精华内容 8,434
关键字:

拉普拉斯特征选择算法