高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于移位序列进行相关值计算的快速算法设计

刁哲军 陈嘉兴 刘志华

吴卫华, 江晶, 冯讯, 刘重阳. 基于高斯混合势化概率假设密度的脉冲多普勒雷达多目标跟踪算法[J]. 电子与信息学报, 2015, 37(6): 1490-1494. doi: 10.11999/JEIT141232
引用本文: 刁哲军, 陈嘉兴, 刘志华. 一种基于移位序列进行相关值计算的快速算法设计[J]. 电子与信息学报, 2007, 29(10): 2441-2443. doi: 10.3724/SP.J.1146.2006.00412
Wu Wei-hua, Jiang Jing, Feng Xun, Liu Chong-yang. Multi-target Tracking Algorithm Based on GaussianMixture Cardinalized Probability Hypothesis[J]. Journal of Electronics & Information Technology, 2015, 37(6): 1490-1494. doi: 10.11999/JEIT141232
Citation: Diao Zhe-jun, Chen Jia-xing, Liu Zhi-hua. A Fast Algorithm Design for Computing Correlation Value Based on the Shift Sequences[J]. Journal of Electronics & Information Technology, 2007, 29(10): 2441-2443. doi: 10.3724/SP.J.1146.2006.00412

一种基于移位序列进行相关值计算的快速算法设计

doi: 10.3724/SP.J.1146.2006.00412
基金项目: 

河北师范大学博士基金(L2005B27)资助项目

A Fast Algorithm Design for Computing Correlation Value Based on the Shift Sequences

  • 摘要: 该文针对以往传统的计算相关值算法,提出了移位序列分析法,得到了一种新的求相关值的算法。利用此法在理论上对相控序列的相关值进行了分析,得到的结果与原有结果是一致的,证明了该算法的正确性;在数值计算上对多种长度的序列进行了新老算法的比较,可以看出新算法非常快速地得出了结果。因此通过此法,既可以对已知的大量序列进行快速计算,从而得到有理想相关值的序列族;又可以很快捷地计算出将要构造的新序列的相关值,看其是否符合要求,从而判断其是否能够应用到相应的系统当中。
  • 压缩感知(Compressed Sensing, CS)是一种探寻欠定线性系统稀疏解的技术,用于获取和重构稀疏或可压缩的信号。该方法利用信号稀疏的特性,在远小于Nyquist采样率的条件下,用随机采样获取信号的离散样本,通过非线性重建算法完美地重建信号[1]。压缩感知理论基于信号的可压缩性,通过低维空间、低分辨率和欠Nyquist采样数据的非相关观测来实现高维信号的感知,丰富了信号恢复的优化策略,促进了数学理论和工程应用的结合。

    常见的压缩感知算法包括:匹配追踪(Matching Pursuit, MP)算法[2]、迭代阈值(Iterative Hard Thresholding, IHT)算法[3]和全变分(Total Variation, TV)算法[4]等。以上算法中,TV算法具有较高的重构精度和所需测量值较少的特点,并且能够很好地保留图像的边缘信息,但由于基于变分过程,往往会导致严重的阶梯效应,使图像纹理出现缺失而过度平滑。Zhang等人[5]结合TV算法和非局部正则化提出了基于非局部正则化的全变分(Total Variation based on Nonlocal Regularization, TVNR)算法,增强了图像的细节纹理,但该算法复杂度高,计算时间长,不适用实时处理。刘亚男等人[6]将分数阶微分作为正则化项,提出了分数阶全变分(Fractional Order Total Variation, FOTV)算法,在低频分量损失有限的情况下大幅度增加高频分量,由低分辨率图像重构得到纹理细节较清晰的高分辨率图像,但Ma等人[7]的研究指出,在图像信号中噪声和结构信息均属于高频成分,因此FOTV在提升图像细节的同时也放大了加性噪声,导致了该算法在噪声环境下失效,缩小了该算法的实际应用范围。目前针对抗噪声性能的研究工作主要集中在具体实验装置改进[8,9]或测量矩阵的优化上[10,11],大多数图像重构算法仅考虑了无噪声条件下的图像重构[12,13],而兼顾图像重构和抗噪声性能的算法报道较少[14]。在实际成像系统中,具有较好抗噪声性能的图像重构算法能有效地提高图像重构的质量,并且能够为单像素成像等计算成像实验系统的图像重构提供较好的解决方案。

    本文较详细地分析了分数阶微分模型和高斯平滑滤波的原理,结合Li等人[15]提出的增广拉格朗日交替方向算法,给出了一种基于高斯平滑压缩感知分数阶全变分(Fractional Order Total Variation based on Gaussian Smooth, FOTVGS)算法。在求解优化目标函数的过程中,使用交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)[16]将优化目标函数划分为两个子问题进行求解,并使用高斯平滑滤波算子更新拉格朗日梯度算子,改进了FOTV的抗噪声性能,使FOTV具有良好的鲁棒性。

    对满足狄利克雷条件的函数,其傅里叶变换为

    F(w)=+f(t)ejwtdt
    (1)

    利用傅里叶变换的微分性质

    Dαf(t)FT(jw)αF(w)=dα(w)F(w)
    (2)

    其中,dα(w)=(jw)α=λα(w)ejθα(w),幅频特性函数为λα(w)=|w|α,相频特性函数为θα(w)=απ/2sgn(w),即分数阶微分算符为线性时不变系统,在不同阶次(1α2)下的分数阶微分算子的幅频特性如图1所示。

    图 1  分数阶次α对信号幅频特性的影响

    为简要说明分数阶次α对信号幅频特性的影响,图1中低频和高频均被归一化,0.5~1.0 Hz表示低频区,1.0~1.5 Hz表示高频区,随着分数阶次α增大,分数阶微分算子对高频分量的幅度拉升作用逐渐增强,呈现出非线性增长,同时对低频分量的幅度有一定的抑制作用。为了提高信号的高频分量,同时使得低频信息不至于损失过多,一般选取1~2之间的阶数。本文以0.1为间隔,经过多次经验验证,当α=1.7时,重构的图像能获得最佳的峰值信噪比(Peak Signal to Noise Ratio, PSNR)和结构相似度(Structural SIMilarity, SSIM),为此本文采用α=1.7

    高斯平滑是一种线性平滑滤波,利用2维高斯分布函数生成高斯模板,扫描图像中的每一个像素,将邻域内像素的加权平均值作为新图像中模板中心位置的像素值。2维高斯滤波使用高斯核为xy两个1维高斯核的乘积,其形式如式(3)

    G(x,y)=12πσ2exp(x2+y22σ2)
    (3)

    本文利用其去噪特性,结合拉格朗日交替方向算法,改进分数阶全变分算法,增强了算法的抗噪声性能。其中,高斯平滑的过程如式(4)

    G(i,j)=k,lf(i+k,j+l)×h(k,l)
    (4)

    其中,h为高斯核函数,也称为权值。

    利用自然图像具有梯度最小化的先验信息,通过研究自然图像在梯度域的稀疏性,传统的全变分算法为

    min|Du|,y=Au
    (5)

    为减小梯度效应,结合分数阶微分,式(5)转化为

    min|Dαu|,y=Au
    (6)

    其中,D=[Dv,Dh]分别代表垂直和水平分数阶微分算子,ARM×N为投影矩阵,u为原始图像,y为测量值。由于原优化问题带有约束,并且不可微分。引入中间变量w,式(6)等价于式(7)

    minw,uw1,w=Dαu,y=Au
    (7)

    构建拉格朗日函数,将有约束的优化问题转换为无约束的优化问题

    L(w,u)=minw,uw1νT(Dαuw)+β2Dαuw22λT(Auy)+γ2Auy22
    (8)

    其中,βγ为惩罚因子,νλ为拉格朗日梯度算子。利用增广拉格朗日方法迭代求解问题式(9)、式(10)来进一步求解无约束问题式(8)

    (wk+1,uk+1)=argminL(w,u)
    (9)
    ν(k+1)=ν(k)β(w(k+1)Dαν(k+1))ν(k+1)=Gν(k+1)λ(k+1)=λ(k)γ(yAu(k+1))}
    (10)

    从式(10)可知,在每次更新ν时,使用高斯平滑滤波算子G更新拉格朗日梯度算子,以起到滤除分数阶微分造成的加性噪声高频分量增加部分。

    式(8)由于其不可微分,很难得到解析解,本文采用ADMM方法将原始问题转化成若干个子问题并逐一求解。

    (1) w子问题。对于给定u,经过简化后,与w有关的优化问题表示为

    wk+1=minww1νT(wDαu)+β2wDαu22
    (11)

    根据2D shrinkage-like定理[17],式(11)的封闭形式为

    w(k+1)=max{|Dαuνβ|1β,0}×sgn(Dαuνβ)
    (12)

    (2)u子问题。通过式(12)得到了w的情况下,求解子u问题等价于式(13),其中w已经由上述w子问题求得,视为定值

    uk+1=minu{νT(Dαuw)+β2Dαuw22λT(Auy)+γ2Auy22}
    (13)

    式(13)是一个2次方程,其离散梯度d可被简化为d=DαT(βDαuνβw)+AT(γ(Auy)λ),令 d=0得到式(13)的解析解为

    uk+1=H1(DαTν+ATλ+γATy+βDαTw)
    (14)

    其中,H=(βDαTDα+γATA),考虑到Moore-Penrose广义逆求解在数值计算上计算成本过高,因此,这里采用具有最优步长的最速梯度下降方法,通过式(15)和式(16)进行迭代求解

    uk+1=ukηkdk
    (15)
    dk=iβi(Dαi)T(Dαiuwk+1i)(Dαi)Tνi)+γAT(Auy)ATλ
    (16)

    其中,ηk=abs(dTd/dTHd)表示Barzilai-Borwein步长因子,dk表示梯度,通过反复迭代,可以求出uk+1

    解决wu两个子问题,得到每次迭代中的wu,然后通过式(10),更新拉格朗日算子νλ。再继续回到上述两个子问题更新下一次的wu,如此迭代,便可用较少的测量值重构出完整的图像。具体算法如表1

    表 1  改进算法流程
     输入:测量矩阵A,测量值y,相关参数ν, λ, β, γ, α
     初始化:u=ATy, ν=0, λ=0, β=26, γ=27, α=27
     While (目标函数式(8)未达到最优解) do
       While u(k+1)uk2ε do
         利用式(12)求解w子问题
         利用式(13)求解u子问题
       End while
     利用式(10),使用高斯平滑滤波算子G更新拉格朗日梯度算子
     使用式(4),将输入图像的像素值作为权重,乘以相关核
     将上面各步得到的结果相加后输出
     End while
     输出:恢复的图像u
    下载: 导出CSV 
    | 显示表格

    仿真数据源选取斯坦福大学和南加州大学图像库的4幅像素为256×256的图像(Lena, Boats, Barbara, Peppers)作为原始图像,如图2所示。

    图 2  实验原始图

    通过仿真实验,在不同采样率和不同的加性噪声下,将5种算法进行定性和定量对比。本实验中,测量矩阵采用高斯随机矩阵,分数阶次α为1.7,相关参数βγ的初始化根据Li等人的经验,分别设定为26, 27。迭代截止条件等其他参数根据个人经验值设定。实验使用的硬件配置为四核Intel®Core(TM)i53317U CPU@1.70 GHz的PC端,仿真软件采用MATLAB R2018b。

    本文利用高斯平滑算子更新拉格朗日梯度算子,抑制分数阶微分对噪声的放大。图3给出了在采样率为0.1, SNR=10 dB时,加入高斯平滑算子前后,Barbara图像的梯度算子ν的变化对比图。在迭代过程中,梯度算子ν共更新了12次,本文选取了5次作为实验对比图。

    图 3  高斯平滑算子加入前后,梯度算子更新变化对比图

    图3所示,随着算法的迭代进行,算子ν包含的图像梯度信息逐渐增多,同时弥漫在梯度算子上的噪声也随之增大,通过对比图3(a)图3(b),特别是第2次和第4次迭代,可以发现在加入高斯平滑后,能有效地抑制分数阶微分对噪声的放大,从而提高重构精度。

    本研究组在实际单像素成像系统中,将实验时外界的环境噪声和器件的热噪声等效成图像测量值的加性高斯白噪声模型,测量值的SNR变化范围为10~35 dB,本文仿真了5种算法在不同采样率和测量值无噪声与有噪声情况下的图像重构PSNR,通过10次测量求平均PSNR,结果如表2

    表 2  在无噪声(测量值SNR=)和有噪声情况下5种算法图像重构峰值信噪比(PSNR: dB)
    采样率0.10.2
    SNR (dB)10202530351020253035
    BarbaraTV12.5316.2618.7719.3920.4322.0613.6217.2519.8320.4821.6624.12
    TVNR13.5016.7318.9219.8321.5323.0614.5417.8220.2321.5622.2325.05
    FOTV10.8315.5516.3918.2819.8624.3512.9116.7718.1019.2420.0425.56
    TVGS13.1016.5718.4318.7620.0421.5314.1217.7319.9419.5220.6223.21
    FOTVGS14.3217.9319.1720.3622.3025.2815.2518.3720.7722.1023.3126.35
    LenaTV16.6520.4822.5323.9624.0325.2918.3322.1023.4325.2426.9428.42
    TVNR17.8721.4223.1024.4025.1526.3419.5423.0324.9326.9427.5528.93
    FOTV15.9319.4021.5822.7823.4427.8117.2121.2222.3024.1925.1229.38
    TVGS17.2820.9822.7823.5223.8724.7218.8822.7424.2325.1426.2128.02
    FOTVGS18.6922.5924.4125.4226.4627.9320.3924.4725.3827.5828.2030.77
    BoatsTV14.7518.5820.1321.3022.5123.2115.5719.3821.0022.9124.2826.66
    TVNR15.9319.7420.9921.9423.0123.7516.5520.3422.8823.6524.8727.12
    FOTV13.5117.3718.8920.8621.3924.6014.2118.7520.7821.9323.9327.86
    TVGS15.3319.0020.2321.0222.0623.0116.0219.9321.2122.8224.0126.03
    FOTVGS17.1020.8622.3723.5524.3725.4617.8223.2624.6925.1526.8428.69
    PeppersTV16.6620.5121.1922.5423.5324.0317.8921.7523.2424.6525.3026.06
    TVNR17.5221.7922.3623.1124.0024.7818.7723.2324.8825.9426.2327.83
    FOTV15.7519.1320.2321.4722.7225.6616.5120.9622.4123.7124.5128.41
    TVGS17.2121.5521.2422.3123.1723.8418.2522.5523.9424.7125.0225.87
    FOTVGS18.6322.3523.7924.4725.3226.3319.5424.7725.4426.1127.3228.88
    采样率0.30.4
    SNR (dB)10202530351020253035
    BarbaraTV14.6918.5521.0522.5023.4026.3316.5520.4523.6424.9825.9028.11
    TVNR15.7719.4921.9723.8724.5827.3317.6322.3724.5325.7826.4529.49
    FOTV13.9318.5619.0421.5122.5427.9515.3419.2422.2123.4824.2429.98
    TVGS15.4319.0321.2422.4723.2126.0017.2121.2324.0125.0725.7927.91
    FOTVGS16.8320.3622.4524.3425.1428.5718.5623.6625.4926.0327.8630.47
    LenaTV19.4123.9025.7227.4228.0131.1421.3125.8027.8629.7330.0132.62
    TVNR21.3225.4526.1128.0129.2131.9522.4126.9728.9930.0131.5233.43
    FOTV18.3322.9724.5025.9327.1832.6620.4524.8525.0627.1129.9934.53
    TVGS20.7824.3525.9627.5127.9430.9922.1726.6527.9929.7029.8832.39
    FOTVGS22.4526.3627.6929.0230.0333.1023.5827.5129.7331.4832.8935.36
    BoatsTV17.8823.0124.1925.2726.5528.3519.2325.3626.0027.4128.2829.87
    TVNR19.5324.9425.2426.4527.1428.8320.8226.6527.2128.7729.5630.29
    FOTV17.0222.9423.1224.5625.5129.2518.8824.1625.7826.0327.6430.68
    TVGS18.7724.6824.2325.1026.3528.0120.5926.1826.5527.4628.0029.51
    FOTVGS20.4525.4926.2227.1828.0329.6721.9627.4228.6929.1530.2431.43
    PeppersTV18.6123.4024.2225.0426.7427.9619.9724.0625.6126.9728.1629.71
    TVNR19.9324.8225.9626.9227.7128.3221.3225.3626.9927.9828.7229.92
    FOTV17.4420.6722.5824.2325.3529.1118.5423.6624.9726.0527.1430.51
    TVGS19.6624.5424.4225.0226.4527.3120.8625.8825.9726.8729.0329.41
    FOTVGS21.2325.3526.7927.4728.8929.4222.3926.7727.4428.3529.1130.89
    下载: 导出CSV 
    | 显示表格

    表2可知,在相同的采样率下,本文所提FOTVGS算法有最大的PSNR。在无噪声(SNR=)情况下,通过对4幅图像在不同采样率下的PSNR求平均,FOTVGS算法相比于文献[6]中的FOTV算法平均PSNR提高0.66 dB,最大提高1.39 dB。在噪声(SNR为10~35 dB)情况下,对比于只含高斯平滑的全变分(Total Variation with Gaussian Smooth, TVGS)算法,在大噪声情况(SNR<25 dB),文献[4]中的TV算法会受到噪声干扰导致性能差于TVGS算法,而在小噪声情况下(SNR>25 dB)TV算法性能要好于TVGS算法,根据经验判断,可能是大噪声情况下,平滑算子去除的噪声较多,而小噪声情况下,平滑算子使图像过于平滑导致细节丢失。与无噪声情况下的结果相反,在噪声环境下,FOTV算法受噪声影响较大,文献[5]提出的TVNR算法性能好于FOTV算法,FOTV算法是最差的图像重构算法,而改进的FOTVGS算法却弥补了该算法的缺陷。通过对4幅图像在不同采样率下和不同测量噪声情况下求平均,给出的FOTVGS算法相比于FOTV算法平均PSNR提高3.11 dB,最大提高4.68 dB。

    图4展示了在采样率为0.2时无噪声(SNR=),测量值的SNR=25 dB以及采样率为0.1,测量值SNR=10 dB时3种情况下的5种算法对标准Lena图像的重构。

    图 4  无噪声和噪声环境下重构对比图

    图4(a)图4(d)显示了在无噪声情况下,5种算法重构图像纹理细节对比,由每幅子图的右下角展示的帽子环带的放大图可以看出,对比于FOTV算法,给出的FOTVGS算法在图像纹理细节上与其相近,甚至比其有更多的纹理细节。图4(f)图4(j)展示了在测量值SNR=25 dB时5种算法重构的图像弥漫着形似椒盐噪声的噪声点,分数阶微分对噪声高频成分的放大作用导致FOTV算法具有最大的噪声值。本文给出的FOTVGS算法所重构的图像相比其他4种算法具有较小的噪声和较多的纹理细节,可见,FOTVGS算法有较强的抗噪声性能。图4(k)图4(o)展示了在测量值SNR=10 dB和采样率为0.1时,5种算法的图像重构对比,在此种极端情况下,FOTV算法重构的图像噪声点较多,TVGS算法虽然噪声较小,但同时也导致了图像过于平滑,如图4中帽子环带信息缺失,从中可以看到改进的FOTVGS算法图像重构效果要好于其他4种,这与表2中给出的图像评价指标一致。

    图5给出了在采样率为0.2情况下,5种算法在不同的噪声水平下的结构相似度(SSIM)变化值,其中测量值的SNR变化范围为10~35 dB。图中可知,在采样率为0.2的情况下,5种算法重构图像的SSIM随着噪声的增加逐渐减小。在相同的SNR下,FOTV算法有最小的SSIM,表明该算法不适合有噪声情况,本文改进的FOTVGS算法有最大的SSIM,说明该算法提高了原算法(FOTV)的抗噪声性能。

    为定量对比5种算法的算法复杂度,图6给出了5种算法在无噪声和噪声环境下(SNR变化范围10~35 dB)的平均图像重构时间对比图。

    图6可知,与FOTV算法相比,改进的FOTVGS算法在不增加过多的处理时间的情况下,具有FOTV算法提高图像纹理细节的特性同时克服了其较差的抗噪声性能。

    本文详细分析了分数阶全变分和高斯平滑的数学模型,给出的FOTVGS算法解决了FOTV算法引起的梯度效应导致的图像纹理细节丢失和FOTV算法抗噪声性能较差的问题。文中对该算法进行了详细的分析,采用ADMM算法求解,给出了具体的求解过程,在求解过程中采用高斯平滑算子更新拉格朗日梯度算子,在较好地保留图像纹理细节的同时提高了原有算法的抗噪声性能。在算法时间复杂度方面,改进的算法在不增加过多图像重构时间的基础上,增强了图像重构的纹理细节。因此,该算法为单像素成像等计算成像的实际成像系统提供了行之有效的图像重构方法。

    图 5  采样率为0.2情况下5种算法的重构SSIM曲线
    图 6  无噪声和噪声环境下5种算法在不同采样率下平均重构时间对比图
  • Gong Guang. Theory and applications of q-ary interleaved sequences[J].IEEE Trans.on Information Theory.1995, 41(3):400-411[2]Gong Guang. New designs for signal sets with low cross correlation, balance property and large linear span: GF(p) case[J].IEEE Trans. on Information Theory.2002, 48(11):2847-2867[3]康凯,郭伟,吴诗其. 一类新的性能优异的伪随机序列GMW相控序列[J].电子学报, 2000, 28(11A): 73-75. Kang Kai, Guo Wei, and Wu Shi-qi. A new family of pseudorandom sequences with good propertiesGMW phase controlled sequences. Acta Electronica Sinica[J], 2000, 28(11A): 73-75.[4]严春林,周亮,李少谦. 相控序列的改进采用级连GMW序列构造相控序列[J]. 电子学报, 2003, 31(5): 797-800. Yan Chun-lin, Zhou Liang, and Li Shao-qian. A new pseudo-random sequencephase controlled sequences and its improvement. Acta Electronica Sinica[J], 2003, 31(5): 797- 800.[5]严春林,周亮,李少谦.一种由移位序列生成GMW序列和级连GMW序列的新算法[J].电子与信息学报.2003, 25(5):650-653浏览
  • 加载中
计量
  • 文章访问数:  3240
  • HTML全文浏览量:  92
  • PDF下载量:  745
  • 被引次数: 0
出版历程
  • 收稿日期:  2006-04-03
  • 修回日期:  2006-11-09
  • 刊出日期:  2007-10-19

目录

/

返回文章
返回