抗压缩算法

抗压缩算法（精选7篇）

抗压缩算法 篇1

网络的广泛应用, 以及压缩图像的网络传输, 使半脆弱水印技术成为人们关注的焦点。该水印要求能够承受某种可接受的修改 (如JPEG有损压缩) , 同时对其他的篡改则表现出脆弱性。近年来, 半脆弱数字水印技术开始逐渐得到重视, 涌现出不少半脆弱数字水印方法的论文。文献[1]提出了关于DCT系数在经受JPEG压缩前后的不变特性, 并基于这个原理设计出了能够有效的承受JPEG压缩的半脆弱水印算法。文献[2]设计了基于DWT变换的半脆弱水印算法。该算法选择了小波子带中的一小部分系数进行嵌入, 减小水印嵌入对图像失真的影响。文献[3]根据人眼视觉系统的掩蔽特性模型, 将小波系数分块动态量化, 通过调整块内小波系数的值, 在每个小波系数块中嵌入一个水印信息位。文献[4]提出了一种基于分层的半脆弱数字水印算法, 该算法不仅能够精确定位图像篡改位置, 而且能有效抵抗VQ攻击。该算法仅使用图像所有像素的最低有效位嵌入水印, 这样虽然能保证很好的不可见性, 但不具备篡改恢复功能。为了实现篡改恢复功能, 文献[5]提出了一种基于分层的半脆弱数字水印算法, 用于图像内容完整性认证, 篡改定位和恢复。将水印信息嵌入到原始图像所有像素的2bit最低有效比特, 这样虽然能够抵抗局部修改攻击, 但是对于JPEG压缩等正常处理不具备鲁棒性。

为了使半脆弱水印具有较强的抗JPEG压缩的能力, 同时对恶意篡改能进行有效的检测和恢复, 本文提出了先嵌入恢复水印再生成认证水印的半脆弱水印算法。其中, 将原始图象进行4×4分块, 然后以自同构映射块的平均灰度 (8bit) 作为恢复水印嵌入到该块的每个像素的2bit最低有效比特中, 这样每个块中就有32bit的容量可供嵌入水印, 采用多重嵌入的方法, 重复嵌入4次, 提取水印时采用多数表决的办法, 这样在恢复水印的时候提高了水印的安全性。利用图像块的DCT变换系数生成混沌迭代系统的初始值, 经过数次迭代以后生成待嵌入的认证水印, 选择DCT变换的中频系数之间的关系嵌入。该算法具有很好的抵抗JPEG压缩的能力, 对局部发生的篡改可以有效地检测, 精确定位并进行内容恢复。

1算法设计

本文提出了一种半脆弱数字水印算法用于篡改定位和恢复。其中, 对图像被篡改区域进行滤波处理可精确地定位出图像被篡改的位置, 而被篡改图像块的有效恢复是依赖于嵌入在另一个子块中的特征信息, 该嵌入块的确定是由Torus自同构映射一维变换计算得到的。下面分别介绍恢复水印嵌入、认证水印嵌入、篡改检测定位和恢复。水印算法过程如图1所示。

1.1基于分块的恢复水印嵌入

1.1.1 预处理

假设原始图像I为256灰度级, 大小为M×M, 其中M为4的倍数。对图像进行4×4分块, 得到图象的块数为${\rm N}=\frac{{\rm M}}{4}\times \frac{{\rm M}}{4}$, 按照从左到右, 从上至下的顺序, 对所有分块进行编号, 记为X=1, 2, …, N, 通过Torus自同构变换得到块映射序列A→B→C→D…→A, 并进行水印嵌入, 序列中的每个字母代表一个独立的4×4块, 即块A的亮度特征嵌入到块B中, 块B的亮度特征嵌入到块C中, 依此类推。Torus自同构映射一维变换公式计算一一映射序列, 如式 (1) 所示:

f (X) = (k×X) mod N+1 (1)

(1) 式中, X是原图象的块序号, f (X) 是自同构映射后的块编号, 0≤k<N, 且k必须为素数, k相当于一个密钥, 在不知道k的情况下, 其他人很难得到恢复水印, 从而增强了水印的安全性。只有当密钥k为素数时, X和f (X) 满足一一映射关系, 否则为多对一映射关系。

1.1.2 基于分块的恢复水印生成与嵌入

假设图像块A和B是原始图像I中的2个分块, 它们是一对Torus自同构映射, 即A→B, 计算出A块中所有像素的平均值作为恢复水印, 嵌入到嵌入图象块B每个像素的最后2 bit。图象块B有16个像素, 这样每个块中就有32 bit的容量可供嵌入水印, 采用多重嵌入的方法, 重复嵌入4次。为了提高水印安全性, 可以对B中所有的16个像素用Torus自同构映射进行重新排序, 即

f (i) = (k′×i) mod 16+1 (2)

(2) 式中, i是B块中原来每个像素的顺序 (按照从左到右、从上到下的顺序) , f (i) 是自同构映射后的像素编号。

经过上述步骤的处理, 恢复水印被嵌入到原始图像中。

1.2认证水印的生成与嵌入

1.2.1 认证水印的生成

利用混沌序列作为水印信号, 具有易于生成、数据极多以及初始条件敏感的优势, 将混沌序列的初始值作为嵌入和提取水印的密钥, 不仅简单而且实用。混沌迭代系统定义如下:

f (n+1) =1-η f (n) 2;η∈[0, 2];

f (n) ∈[-1, 1];n=0, 1, 2…… (3)

将嵌入恢复水印的图象进行8×8分块后进行DCT变换, 对变换矩阵zig-zag扫描后得到一个新的一维向量Vi (i=1, 2, …, 64) , 计算

IInitial=${\displaystyle \sum _{i=2}^{21}V}{}_i(4)$

得到混沌迭代系统的初始值f (1) , 带入 (3) 式中迭代n次得到f (n+1) , n为密钥, 提高了水印的安全性。认证水印w的生成如下定义,

$w{}_i=\{\begin{array}{l}1‚f(n+1)>0\\ 0‚f(n+1)\le 0\end{array}i=1,2‚\cdots ,\frac{{\rm M}}{8}\times \frac{{\rm M}}{8}(5)$

1.2.2 认证水印的嵌入

利用DCT系数的关联性来嵌入水印。选中每个8×8块中的固定的两个点 (U1, V1) 、 (U2, V2) , 对应的DCT系数分别为F (U1, V1) 、F (U2, V2) , 如果要嵌入的水印为1, 则令F (U1, V1) >F (U2, V2) ;如果要嵌入的水印为0, 则令F (U1, V1) <F (U2, V2) , 为了保证DCT系数的关联性从而提高水印的鲁棒性, 可以设置一个参数ddifference。例如F (U1, V1) >F (U2, V2) 且F (U1, V1) -F (U2, V2) <k, 则

在每个8×8的块中选择的两个点是 (5, 2) 和 (4, 3) , 这是因为:

1) 它们都处于DCT系数的中频部分且位置接近;

2) 它们在JPEG压缩时有相同的量化系数, 这样就可以很好的抵抗一般的JPEG压缩;

3) 它们在DCT变换后的系数相对较小, 作出改变后图象发生的改变较小。

经过上述步骤就完成了认证水印的嵌入, 再对每个8×8子块做DCT逆变换就得到了嵌入认证水印的图形。

1.3篡改检测和定位

要确定图像是否被篡改, 首先要提取认证水印来确定篡改区域。认证水印的提取是嵌入的逆过程, 将待检测的图像进行8×8分块后进行DCT变换, 对变换矩阵F′ (i, j) (i=1, 2, ……, 8;j=1, 2, …, 8) ;zig-zag扫描后得到一个新的一维向量Vi′ (i=1, 2, …, 64) , 根据 (4) 式计算出混沌迭代系统的初始值f (1) ′, 带入 (3) 式中迭代n次得到f (n+1) ′, 得到

对w1和w2进行比较, 如果w${}_i^1$=w${}_i^2$, 则第i块通过认证, 否则作出篡改标记。

由于对图像的正常修改 (如JPEG压缩) 而被标记的图像子块的分布是随机的, 而被恶意修改区域的图像子块则出现标记聚集。为了实现更精确的恶意篡改定位, 我们对篡改矩阵进行滤波处理。

篡改矩阵如下定义:篡改矩阵是$\frac{{\rm M}}{8}$行$\frac{{\rm M}}{8}$列的二值矩阵, 如果图像第i块矩阵作出篡改标记, 则对应的篡改矩阵的值就设为1, 否则为0。

下面给出稀疏点的定义:在一幅二值图像中 (不包括边界点) , 对于任一像素点, 若满足以下两个条件中任意一个, 即可视为稀疏点:

(1) 该像素点没有一个四连通点与之灰度值相同;

(2) 该像素点有且仅有一个四连通点与之灰度值相同, 但没有与该像素点灰度值相同的八连通点。

为了精确定位篡改区域, 我们需要在篡改矩阵中去掉这些稀疏点.所以, 对篡改矩阵做循环滤波, 直到没有这样的稀疏点存在为止.篡改矩阵在经过上面的滤波方法处理以后, 即得到最终的篡改定位矩阵。根据篡改定位矩阵我们可以找到图像被修改的区域。

1.4篡改恢复

经过水印检测与定位后, 遭受篡改的图像块均做出了标记, 因此只需恢复被篡改图像块, 未做出篡改标记的图像块保持不变。假设图像块X′有篡改标记, 由 (1) 式可知, 在水印嵌入过程中, 图像块X′的灰度特征是嵌入到图像块f (X) 中的。其恢复过程如下:

1) 根据密钥k和式 (1) 计算并定位图像块f (X) ;

2) 如果图像块f (X) 有篡改标记, 则无法恢复图像块X′;

3) 如果图像块f (X) 无篡改标记, 则从图像子块f (X) 每个像素提取最后2 bit, 采用多数表决的反法生成恢复水印, 该恢复水印即为对应图像子块X的灰度特征。

2实验结果

2.1不可见性

为了定量分析本文方法的优越性, 本文使用峰值信噪比PSNR 来带水印图像的质量好坏, 其定义为

${\rm P}S{\rm N}R=10\lg \left[\frac{255{}^2}{{\displaystyle \sum _{j=1}^{{\rm M}}{\displaystyle \sum _{i=1}^{{\rm M}}(}}{\rm I}(i,j)-{{\rm I}}^{\prime }(i,j)){}^2}\right]$ (9)

I和I′分别代表原始图像和嵌入水印的图像, PSNR可以反映原始图像和水印图像对应点之间的均方误差情况, PSNR值越大则表明加水印图像和原始图像之间差别越小, 不可见性越高。PSNR值受到ddifference影响, ddifference值越大则PSNR值越小, 水印的不可见性越低, 但是PSNR值越小则水印鲁棒性越低。图1给出了不同的ddifference值下的PSNR曲线表, 其中横坐标为ddifference值, 纵坐标为PSNR值。本文实验中我们选取ddifference值为0.4, 图3 (a) 为原始图像, 图3 (b) 为当ddifference值为0.4时嵌入恢复水印和认证水印后的图像。

2.2篡改检测与恢复

图4 (a) 和5 (a) 分别给出了剪切攻击和拼贴攻击后的水印图像, 图4 (b) 、5 (b) 给出了图像篡改定位的检测结果, 篡改定位部分用白色显示结果, 由图可见算法对剪切攻击和拼贴攻击有很好的检测效果和定位结果, 图4 (c) 、5 (c) 给出了篡改恢复图像

图6 (a) 、图7 (a) 分别给出了质量因子为50%和70%的JPEG压缩, 图6 (b) 、7 (b) 给出了图像篡改定位的检测结果, 没有显示出虚警检测, 由图可见算法对JPEG压缩所具有很好的鲁棒性。

3结束语

本文设计并实现了一种抗JPEG压缩的半脆弱数字水印算法, 本算法主要有以下几个特点: (1) 将恢复水印信息嵌入到原始图像所有像素的2 bit LSB, 采用多重嵌入的方法, 提高了篡改恢复效果, 算法实现原理简单, 篡改恢复效果好; (2) 将水印信息嵌入到各DCT变换域的中频, 可以保证水印算法对JPEG压缩具有较强的鲁棒性, 并且DCT变换又能够将嵌入的水印能量较好的分布到图像块的各部分, 这在一定程度上保证了所嵌入水印信息的不可见性; (3) 采用滤波的方法避免了JPEG压缩等正常操作造成水印检测的虚警, 提高了篡改检测的精确性; (4) 算法实现了无源提取, 是一种盲水印算法。本文算法经过实验验证可以检测出图像中篡改内容的位置, 并且可以对篡改内容进行有效的恢复, 同时能有效抵抗矢量量化攻击和局部修改攻击。

摘要：基于JPEG压缩的特性, 设计并实现了一种抗JPEG压缩的半脆弱数字水印算法, 用于图像内容完整性认证, 篡改定位和恢复。在嵌入方, 将恢复水印信息重复嵌入到原始图像所有像素的2bit最低有效位;认证水印利用图像块的DCT变换系数和混沌迭代系统生成, 并选择DCT变换的中频系数之间的关系实现嵌入。实验结果表明, 该算法具有很好的抵抗JPEG压缩的能力, 对局部发生的篡改可以有效地检测、精确定位并进行内容恢复。

关键词：半脆弱水印,篡改恢复,联合图像专家组 (Joint Photograplic Experts Group, JPEG) 压缩,DCT变换

参考文献

[1] Lin C Y, Chang S F.Semi-fragile watermarking for authenticating JPEG visual Content.Proceedings of SPIE:The International Society for Optical Engineering, 2000:140—151

[2]Winne D A, Knowles H D, Bull D R, et al.Compression compatible digital watermark algorithm for authenticity verification and localiza-tion.Proceedings of SPIE:The International Society for Optical Engi-neering, 2002:357—367

[3] Wang Xiangyang, Yang Hongying, Chen L, et al.A new semi-fragile image watermarking based on visual masking.Journal of Image and Graphics, 2005;10 (12) :1548—1553

[4] Celik M U. Hierarchical watermarking for secure image authentication with Localization.IEEE Trans on Image Processing, 2002;11 (6) :585—595

[5] Liu Quan, Jiang Xue mei. Journal on Communications, 2007;28 (7)

脉冲压缩雷达抗电子攻击性能研究 篇2

关键词：脉冲压缩,雷达,干扰,匹配滤波器

随着雷达技术的进步, 为了提高雷达的电子对抗性能, 现代雷达通常会采用比较复杂的信号形式, 脉冲压缩技术就是雷达与干扰进行功率对抗的一种有效技术手段, 这种技术包括:采用宽脉冲以提高发射的平均功率, 保证足够的最大作用距离;在接收时, 采用相应的脉冲压缩方法得窄脉冲, 以提高距离分辨力。这样脉冲压缩雷达既能保持窄脉冲的高距离分辨力, 又能获得宽脉冲雷达系统的强检测能力。脉冲压缩技术是使的对雷达难以进行干扰, 而进行有效干扰需要专门的电子攻击技术。

1 脉冲压缩技术 (PC-pulse compression) 的原理

雷达系统中脉冲压缩 (PC) 的应用代表了脉内相干技术在雷达波形中的应用。相干技术不仅改善了雷达性能, 而且还提供了对雷达发射波形不匹配的干扰波形的抗干扰能力。目前实现脉冲压缩的方法主要有两种: (1) 相位编码的脉冲压缩; (2) 线形调频脉冲压缩。

1.1 相位编码脉冲压缩原理

相位编码波形与调频波形不同, 它将脉冲分成许多子脉冲。每个子脉冲的宽度相等, 但各自有特定的相位。每个子脉冲的相位根据一个给定的编码序列来选择。应用最广泛的是二进制相位编码。在这种形式的PC中, 一个持续时间为T的宽脉冲被分为n段, 每段的宽度为。以随机的方式选择每一段的相位, 或为0, 或为。该PC信号的时间带宽乘积等于分段的数目n=T/。此方法的优点是匹配滤波器可以用简单抽头延迟线 (数字移位寄存器) 来实现, 其抽头间隔为子段的宽度, 并且用与合适的随机相位序列对应的相位 (0或) 进行加权。

1.2 线性调频脉冲压缩原理

线形调频脉冲压缩是雷达发射机发射一个宽脉冲调频信号, 回波信号经过一个延迟时间随频率上升而线性减小的无源线性网络后, 被压缩成包络形状为辛克曲线的窄脉冲, 这主要是由于压缩网络的幅频特性和相频特性的不均匀性引起的。

线形调频波形比较容易产生, 但通常输出波形中间有一个很窄很高的主峰 (主瓣) , 旁边有一系列小的付峰 (旁瓣) 。主峰很窄很高, 说明信号通过压缩网络后能量极大的集中于一个窄脉冲内, 但是副峰也消耗了一部份能量, 况且由于副峰的存在还有可能出现强信号的副峰压抑弱信号的现象, 必须给予抑制。

2 脉冲压缩信号的效果分析

2.1 相位编码脉冲压缩雷达信号性能分析

在相位编码PC系统中常常采用巴克码二进制序列。这种序列的特点是电压时间旁瓣相等、幅度为1/n。但比较受限的是, 已知的最长巴克码只有13位 (1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1) , 1对应于0弧度相移, -1对应于弧度相移。

当需要较大的PC比时, 通常采用线性移位寄存器序列。这种序列是用带反馈的移位寄存器产生的。一个N级寄存器可产生最大长度为n=2n-1的序列。对于一个长序列, 最大电压旁瓣近似为 , 而时间带宽因子是n。

如果不要求进行多普勒处理, 则相位编码PC系统可得到不同的码, 这样就能在脉冲到脉冲的基础上改变编码。这种方法能对抗与PC波形同步而产生假目标的干扰机。但是相干地转发截获波形的欺骗对抗干扰机仍能有效地对付这种形式的反干扰措施。

2.2 线性调频脉冲压缩雷达信号性能分析

一个线性调频信号可以表示成复数形式:

PC匹配滤波器的冲击响应是:

该式表明, 匹配滤波器的冲击响应是斜率为负的信号波形。

通常匹配滤波器对一个线性调频信号的输出有比较高的时间旁瓣, 这些旁瓣是不需要的, 因为在大目标附近的一些小目标可能被遮蔽而探测不到。目前解决的办法是用一个窗函数对线性调频信号的幅度进行加权。应用窗函数减小了时间旁瓣, 但是增大了主瓣响应宽度, 因此更难分辨两个紧靠在一起的目标。而且当接收信号上有多普勒频移时, 滤波器就不再匹配了, 输出信号与原样就产生失真, 我们可以用模糊函数来确定匹配滤波器在一个频率范围内的响应。

3 脉冲压缩雷达面临的电子攻击方法研究

PC波形主要用于跟踪雷达和监视雷达。干扰的目的取决于要干扰的雷达类型。一般而言, 在对付PC雷达的波形中, 噪声干扰是效果最差的干扰波形。可以把PC系统的匹配滤波器看成是一个相关器, 与信号完全不相关的噪声得不到任何相关的增益, 而全相关的目标能得到全部处理增益。即便有一点相关性的干扰波形也比随机噪声要有效。

攻击PC雷达的第一步是确定其参数。有两种方法可以应用。较老式的办法是应用包络检波器的电子战支援系统破坏信号内的相位 (频率) 信息, 因此仅依靠PC雷达具有大的脉冲宽度来识别。较新型的系统应用了电路来测量线性调频斜率或相位编码波形码元率。这些系统一般使信号与其延迟后的复制品在相位检测器中进行相关, 以确定相位特性, 其类似于瞬时测频 (IFM) 接收机。

3.1 对抗采用PC波形的跟踪雷达

对于跟踪雷达, 其目的是产生捕获雷达跟踪波门的假目标。在这种工作方式中, 使雷达信号发生相干频移后再被转发回雷达。这种频移转发干扰信号领先于匹配滤波器输出中的真实目标回波。使得采用前沿跟踪的电子防护技术无效。

对抗采用了PC波形的跟踪雷达的转发式干扰需要俘获雷达跟踪波门。为此, 欺骗对抗干扰机必须转发雷达PC波形的相干复制品, 可能加上一些频移, 这种转发的复制信号可以随时间变化。该过程在开始时是以最小的时间延迟转发接收到的雷达脉冲。这样可保证干扰机脉冲与真实信号一起进入雷达的跟踪波门, 能够捕获雷达的自动增益控制 (AGC) 电路。然后欺骗干扰机开始在转发的信号中引入逐渐增加的时延量, 而雷达距离波门电路就开始跟踪较强的信号, 逐渐偏离真实的目标距离。

欺骗干扰机可用DRFM来存储PC信号, 应用这种方法时, 输入信号以等于或大于奈奎斯特速率来取样, 并存储在数字存储器中。需要时对它们钟控输出, 变化成模拟形式发射出去。实际的DRFM把信号下变频到基带上, 在基带上把信号能以数字方式有效地存储起来。利用上下变频振荡器频率的差就可把多普勒频移加到信号上。PC波形的存储给DRFM带来了一些限制, 因为高钟速情况下的存储能力有限, 为了适应长的PC信号, 波形被选通后只存储整个信号的若干小段, 在选通时若干小段信号以首尾相接的方式读出, 因此可以产生与整个波形逼近的信号。图1为用MATLAB画出的线性调频PC滤波器对有频偏信号的输出效果。

3.2 对抗采用PC波形的监视雷达

对于监视雷达, 其目的一般是通过产生背景干扰或产生能压制真实目标检测的同步假目标而掩蔽目标。一个干扰PC监视雷达的通用系统是干扰系统把收到的雷达PC信号存储在数字射频存储器 (DRFM-digital RF memory) 中, 在DRFM中, 信号在整个雷达脉冲间隔内都连续地被重复和放大, 从而产生许多假目标。因为这种假的干扰信号是与雷达相干的, 所以它们可以消除PC网络相对于雷达目标的处理增益。而且, 由于它与雷达的脉冲重复频率 (PRF) 是同步的, 因此它们也与雷达一样可获得检波后积累的增益。

很多情况下DRFM可用一个直接数字频率合成器 (DDS-direct digital synthesizer) 代替而得到类似的效果。它需要把每个威胁雷达相关的参数存储到干扰机的数据库中。然后干扰机中的接收机识别要对抗的特定PC雷达, 测量其关键参数 (例如雷达频率) , 从威胁数据库中取出其余的参数, 在DDS中合成威胁雷达的准相干复制信号, 再在雷达脉冲之间的间隔时间内发射这一复制的信号。DDS法的效果取决于雷达参数的了解或测量精度。

4 结语

虽然脉冲压缩雷达波形具有较强的抗干扰性, 但通过分析可以证明用专门的电子攻击技术也是可以对其进行有效的干扰的。干扰是伴随着雷达的出现而同时出现的, 雷达与反雷达是军用雷达持续发展与不断创新的推动力, 雷达技术的发展取决于相关基础科学技术、专业工程技术及应用新领域的发展, 目前脉冲压缩雷达技术已经取得很大进展, 大大提高脉冲压缩雷达的各项技术指标, 但必须意识到干扰的技术手段也在不断更新进步, 未来脉冲压缩雷达在工作中一定会遇到各种各样的攻击和干扰。

参考文献

[1]康锡章, 康建.电子系统中电子防御的原理和设计[M].北京:海潮出版社, 2012:35-45.

[2]张永顺, 童宁宁, 赵国庆.雷达电子战原理[M].国防工业出版社, 2006:67-89.

[3]刘隆和.海军战术导弹对抗与反对抗技术[M].北京:海潮出版社, 1999:105-110.

[4]施莱赫.电子战[M].北京:解放军出版社, 2007:110-120.

数字影像无损压缩算法研究 篇3

随着计算机技术、通讯技术和生物医学工程技术等相关技术的高速发展, 通过对医学影像进行数字化处理, 进行计算机智能化处理, 将使依据医学影像进行的诊断放弃传统的肉眼观察和主观判断, 并可依据同一影像进行多种疾病的诊断和多科疾病的诊断。在应用计算机技术后, 医学影像将从形态图像向功能图像转变, 对医学影像数据库和特征库的内容进行提取分析, 将可以帮助医生进行科学的诊断, 提高诊断的科学性、客观性和准确性。

应用DICOM3标准和网络通讯协议标准TCP/IP可以方便地实现对直接具有数字化接口的影像设备的成像数据的提取;小波分析 (Wavelet Analysis) 在时域和频域同时具有良好的局部化性质, 而且由于对图像信号的高频成分采用转件精细的时域或频域取样补偿, 从而可以聚焦到对象的任何细节, 这一特点在医学影像分析中将得到较好的应用。

1总体方案设计

ACR和NEMA联合组成委员会在1993年发布的医学数字成像与通信 (Digital Imaging and Communication in Medicine, DICOM) 标准3.0, 是医学影像设备间联网的专用数字接口, 是进行网络通信时应满足的标准协议, 是一组具有DICOM兼容性的设备所共同遵循的协议。在DICOM标准中, 医学图像包含了许多如图像获取设备对图像的分析、医生的报告及患者情况等信息, 这种信息与图像的结合方便了图像的检索、图像的分析和诊断。医学影像处理的总体结构如图1所示。

1.1符合DICOM标准中间件实现方案

DICOM3消息交换的网络支持对应于ISO/OSI定义的网络传输中的会话层、表示层及联接控制服务单元, 这部分底层 (传输控制层、网络层) 的信息交换定义为通用的网络传输协议。在设计实现中将采用智能Agent中间件技术。当设备采集影像数据后, Agent中间件自动将数据传送到医学影像数据库中, 减少不必要操作的处理, 并能保证数据传输的一致性和同步性。

1.2压缩存储中间件实现方案

影像图片大约需要8～15 MHz的存储空间, 为了缩小存储成本和便于网络传输, 必须对图像进行压缩。现阶段常用的压缩存储方案有4种:① 基于JPEG标准下的无损压缩算法JPEG-LS, 这是DICOM标准支持的一种成熟的无损压缩算法;② 基于整数小波变换的单帧图像无损压缩算法, 它利用了医学图像象素之间存在高度的相关性和整数小波的特性;③ 基于三维整数小波的序列图像无损压缩算法, 对整个序列进行无损压缩, 可以有效地提高图像的压缩率;④ 利用JPEG2000标准支持ROI (Region Of Interest 感兴趣区域) 编码的特性, 对图像的ROI进行无损压缩编码, 对次要信息区域 (如背景) 采用高压缩比的有损压缩方法。

本文在综合分析以上4种方案的基础上, 提出了基于适形离散小波变换 (SA-DWT) [1]与整数小波变换相结合的影像无损压缩算法。并应用该方案构件了智能Agent中间件。

1.3检索诊断中间件实现方案

在应用存储的数字化医学影像和影像特征进行诊断时, 需要完成大量的检索和比对处理, 为了减少网络流量, 提高检索速度, 应用了基于小波模极大值及多尺度不变矩相结合的检索算法, 并建立了算法实现的中间件, 运行效果明显, 能够较好地完成影像的检索和诊断作用。

2无损压缩算法研究

无损图像压缩是指解压缩后的图像与原来图像完全相同, 没有任何信息的损失。医学图像是医学诊断和疾病治疗的重要根据, 在临床上具有重要的应用价值。确保医学影像压缩后的高保真度是医学图像压缩首要考虑的因素。现在医学图像常采用无损压缩, 因为它能够精确地还原图像。但是无损图像压缩的缺点是压缩比低, 仅为2～4;而有损图像压缩的压缩比可高达50, 甚至更高。所以将这2种压缩法方法在保证使用要求的基础上结合起来, 在获取高的压缩质量的前提下提高压缩比。本文提出的基于SA-DWT与整数小波变换相结合的压缩算法, 就是应用SA-DWT算法确定感兴趣区域, 对该区域进行无损压缩, 其他区域进行有损压缩, 大大提高了压缩效率, 并不损失影像的医学作用。

2.1SA-DWT算法

传统的二维小波变换都是针对矩形区域进行的, 得到的变换系数个数一般会大于原始区域像素点个数, 而且由于填充, 变换后区域的边界会出现钝化, 所以限制了任意形状区域的编码效率。

现代的患者同一部位的医学影像可以应用到相关的不同的多个诊断过程中, 因此, 整幅影像中可能存在多个特征区域, 而每个区域的形状都不是规则的图形, 不适合采用传统的二维小波变换。本文采用了Li等提出的适形离散小波变换 (SA-DWT) , 该变换可以用于对任意形状的图像对象进行变换, 因此适合与对医学影像中的感兴趣区域进行编码。测试结果表明:

① 变换域的变换系数同像素域的相同;

② 只要采用的L阶小波滤波器具有完全重构特征, 并且下采样的位置已知, 就存在一个唯一的反变换, 可用于完全重构原始的影像;

③ 长度自适应的小波变换保留了分段采样点的位置, 不会产生超出边界的系数。

由于对奇数长度图像信号的剩余采样点进行了缩放, 因此这种任意长度的小波变换得到的低通系数具有相同的尺度, 这就避免了边界处小波系数的突变。

2.2提升算法原理

由Sweldens等提出来的提升方案 (Lift Scheme) 是构造紧支集双正交小波的一种新方法, 被称为“第二代小波”[2], 也叫做整数小波变换。该方法可以将整数映射到整数, 可以实现由SA-DWT算法分割的不同区域内影像的无损压缩。

对于原始信号sj, 经小波分解成为低频信号sj-1和高频细节信号dj-1两部分。有提升方法构成的小波变换包括:分裂 (Split) 、预测 (Predict) 和更新 (Update) 3个步骤。

2.2.1 分裂

此过程是将原始信号sj分裂成2个互不相交的子集sj-1和dj-1, 通常是将这个信号序列分解成偶数序列和奇数序列, 即

split (sj) = (evenj-1, oddj-1) = (sj-1, dj-1) 。

2.2.2 预测

针对数据间的相关性, 可用sj-1去预测dj-1, 故可以采用一个与数据集结构无关的预测算子P, 使得dj-1=p (sj-1) , 这样就可以用子数据集sj-1代替原始数据集sj。若再用子集dj-1与预测值p (sj-1) 之间的差值去代替dj-1, 则此差值反映了二者的逼近程度。如果预测是合理的, 则差值所包含的信息就比原始子集dj-1包含的信息要少得多。预测表达式为:

$\widehat{d}{}_{j-1}=odd{}_{j-1}-p(even{}_{j-1})=d{}_{j-1}-p(s{}_{j-1})$。

将数据集合分成偶数集合和奇数集合后, 最简单的一个预测算子就是用相邻2个偶数的均值来作为它们之间的奇数的预测值, 即

p (sj-1) =s (j, 2k+sj, 2k+2) /2。

由此可得预测表达式为:

$\widehat{d}{}_{j-1,k}=d{}_{j-1,k}-p(s{}_{j-1})=s{}_{j,2k+1}-(s{}_{j,2k}+s{}_{j,2k+2}/2)$。

2.2.3 更新

经过上述2个步骤后, 所产生的系数系数子集sj-1的某些整体性质 (如均值) 并不和原始数据中的性质一致, 因此需要采用更新过程。其目的是通过算子U产生一个更好的子数据集合$\widehat{s}{}_{j-1}$, 使之保持与原始数据集一致的特征。$\widehat{s}{}_{j-1}$定义如下:

$\widehat{s}{}_{j-1}=even{}_{j-1}+U(\widehat{d}{}_{j-1})=s{}_{j-1}+U(\widehat{d}{}_{j-1})$。

具体的更新计算的过程为:

$\widehat{s}{}_{j-1,k}=s{}_{j,2k}+(\widehat{d}{}_{j-1}+\widehat{d}{}_{j-1,k-1})$。

对于数据子集$\widehat{s}{}_{j-1}$重复进行上述相同的3个步骤, 即将$\widehat{s}{}_{j-1}$分解成$\widehat{s}{}_{j-2}$和dj-2, 经过n次分解后, 原始数据sj的小波表示为:

$\{\widehat{\text{s}}{}_{\text{j}-\text{n}},\widehat{\text{d}}{}_{\text{j}-\text{n}},\widehat{\text{d}}{}_{\text{j}-\text{n}+1},\cdots ,\widehat{\text{d}}{}_{\text{j}-2}‚\widehat{\text{d}}{}_{\text{j}-1}\}$。

式中, $\widehat{\text{s}}{}_{\text{j}-\text{n}}$代表了信号的低频部分;$\{\widehat{\text{d}}{}_{\text{j}-\text{n}},\widehat{\text{d}}{}_{\text{j}-\text{n}+1},\cdots ,\widehat{\text{d}}{}_{\text{j}-2},\widehat{\text{d}}{}_{\text{j}-1}\}$代表了信号的高频部分。

重构数据时的提升为:

$\begin{array}{l}s{}_{j-1}=\widehat{s}{}_{j-1}-U(\widehat{d}{}_{j-1})‚\\ d{}_{j-1,l}=d{}_{j-1,l}^{(1)}+a{}_{-1}(s{}_{j-1,l-2}-s{}_{j-1,l-1})‚\\ s{}_j={\rm M}erge(s{}_{j-1},d{}_{j-1})。\end{array}$

2.3整数小波变换

Sweldens已经证明在提升的基础上可以进行整数集到整数集的小波变换。一个整数集合通过小波变换得到的仍然是整数集合。在进行影像压缩编码处理过程中, 不需要对变换后的系数进行量化, 因此可以实现影像的无损压缩。

在进行影像的无损压缩时, 主要采用了S变换和S+P变换。针对影像的特点并结合Haar变换的整型表示方法, 提出如下形式:

S变换之后, 在低通系数sj-1, l的基础上进行线性预测, 以产生新的高通系数dj-1, l, 这就是S+P变换。

2.4实验与分析

在验证算法中, 主要选取了3组MR图像 (256*256*16 bits, 每组30幅) 和2组CT图像 (512*512*16 bits, 每组30幅) , 分别采用了本文提出的算法进行压缩处理, 同时用预测整数小波变换 (简称:PIWT) 、整数小波变换 (IWT) 和差分脉冲编码调制 (DPCM) 等算法对这5组序列影像进行压缩编码, 得到平均压缩率如表1所示。对其中的数据进行分析可知:本算法的压缩率分别比PIWT算法、IWT算法和DPCM算法平均提高81.15%、100.73%和67.61%。表1中的二维算法的压缩率是序列图像中个图像压缩率的平均值。

应用SA-DWT变换可以方便地找到影像中的多个感兴趣区域, 应用整型小波变换对影像象素本身灰度值进行变换, 且保持了变换前后的整数的一致性, 可以实现对感兴趣区域的无损压缩。

在进行若干次提升变换后, 再利用哈夫曼编码对变换后的系数进行编码, 将较好地去除像素间的相关性, 极大地减低了原始图像的信息量。

3结论语

DICOM标准可以方便地将医学影像处理的数据传到计算机中进行处理, HL7标准可以提高医院不同应用软件间的通信能力。根据多媒体技术和关系数据库理论, 建立医学影像数据库。在构建影像数据库和影响特征库时, 为了减少数据存储量, 提高影像传输速率, 而不影响影像的诊断效果的基础上, 本文提出了基于适形离散小波变换 (SA-DWT) 与整数小波变换相结合的影像无损压缩算法, 并构建了该算法的中间件, 在实际的验证测试中, 该算法可以较好地完成影像的压缩存储, 效果良好。

下一步的研究工作将针对目前影像压缩存储算法和影像检索的算法进行深入研究和比较, 进一步发展各种医学影像内容分析的理论和技术, 深入研究能够充分表示医学图像内容的各种特征, 进一步发展系统架构、性能评价、相似性度量方法、人机交互方式、高维度检索和智能诊断等技术。

参考文献

[1]CINKLER K.Very Low Bit-rate Wavelet Video Coding[J].IEEE Journal on Selected Areas in Communication, 1998, 16 (1) :4-11.

基于数据压缩算法的研究 篇4

随着信息技术和计算机技术的飞速发展, 人们面对的数据越来越多, 在数据储存和传输的过程中, 数据压缩[1]的地位越来越重要。一般来说, 数据压缩可以按压缩的失真度分为有损压缩和无损压缩[2]。有损压缩顾名思义就是把使用压缩技术后的数据进行解码还原, 得到的数据与之前的数据不是完全一样, 却不会使人们对原始资料引起错误的理解。有损压缩一般应用在压缩后的数据不一定要和原始数据完全一致的场合。无损压缩就是指把压缩后的数据进行解码还原, 得到的数据与原始数据一模一样, 没有改变。目前流行的无损压缩编码有哈夫曼编码、LZW编码、算术编码、行程编码等。

目前, 数字化和网络化正在给我们的生活带来翻天覆地的变化, 图像的数字化也将成为一个必然的趋势。占据我们大量存储空间和传输带宽的图像, 如果采用数字化处理, 会使得图像数据有如下优点: (1) 数字化处理后的图像容易储存而且方便处理, 不再是一块难嚼的鸡肋, 能够满足人们的各种需求; (2) 数字化处理后的图像在传输过程中容易传输且快速; (3) 数字化处理后的图像与原始图像一样高分辨率, 优质量; (4) 数字化处理后的图像更增强了稳定性和传输过程中的抗干扰能力。但是, 通常数字化后的图像仍然面临着对海量数据的存储与传送问题。所以, 在计算机的存储空间和信道有限的条件下, 怎样高质量、高效率地对数字化后的图像进行可靠压缩成为计算机技术的热门研究领域。

Lempel-Ziv-Welch (LZW) 编码就是一种主要用于图像数据压缩的算法。这种算法对一些简单平滑的图像和一些噪声小的数据具有比较高的压缩比, 而且本算法有比较快的压缩和解压缩速度。本文主要介绍了LZW算法, 并给出了一个编码实例, 通过实验结果可以证明这是一种有效的数据压缩方法。

二、LZW算法

LZW算法是在数据压缩经典算法LZ77和LZ78二者的基础上改进而成的, 由Terry Welch于1984年提出[3,4]。

LZW算法在开始压缩之前, 字典中只有单个字符和编码的串表。开始压缩时, 读入字符串, 按一定的顺序与字典中已包含的字串进行匹配, 如果能够匹配成功, 则将匹配好的字符串对应编码输出;如果不能进一步匹配, 则将导致匹配失败的字符与之前的字符串合并在一起, 加入串表并给以相应编码。

LZW算法的串表具有前缀性[5], 即表中任何一个字符串的前缀字符也在串表中。也就是说, 如果由某个字符串P和某个单字符C所组成的字符串PC在表中, 则P也在表中。C叫作前级串P的扩展字符。

LZW算法与LZ78算法有着相似的编码和解码过程。这两种算法的主要区别在于进行编码时, 因为在压缩时, 字典中已经包含有每个单字符及其编码的串表, 所以在LZW算法的码字中省略了LZ78算法的码字中关于未匹配字符这项, 只是含有已经匹配成功的字符串的索引值, 由此来降低LZW算法的码字的长度以便提高数据压缩比;解码时, 由于表中需要的未匹配字符要在解压缩下一个输入码字后才可以获得, 因此建表的过程相对于压缩时要推迟一步。

三、LZW算法实例

本文使用VC来编译代码和制作界面。

在压缩开始时, 首先要对存放字符串的hash表、结束标志、清除标志、输入/输出缓冲的位置进行初始化。必须使hash表不是空值, 从0开始记输出缓冲位。需要定义前缀字符串Old和当前读入字符Pixel。如果Old+Pixel字符串存在hash串表当中, 就从中取出该字符串的索引编号Index。

部分代码可表示为:

如果Old+Pixel字符串不在hash串表当中, 就把Old+Pixel字符串添加到String Table编码表。

部分代码可表示为:

进行压缩完成后要清除hash表。在数据解码过程中, hash串表能依据原始字典和Index再次生成。

数据的解压缩过程其实是压缩的逆过程。首先还是必须对字符串表、清除标志、结束标志和输入/输出进行初始化。需要定义前缀字符串Old和当前读入字符Pixel (当前输入的经压缩后的字符) 。如果Code既不是清除标志也不是结束标志时, 算法进行数据解码工作。

部分代码可表示为:

进行解码完成后, 要清空m_pStrBegin指针, 即清空指向String Table表的指针。

下面我们采用一个示例图像, 使用本文的LZW算法来进行压缩。原始图像zuoye如图1所示, 是一个大小为486 Byte, 宽度和高度均为12像素的彩色图像。本文用VC做的界面图, 选择zuoye为压缩文件后, 单击编码按钮就可进行压缩操作。压缩结果如图2所示。

图2压缩结果图

从图2可知, 原文件大小为486字节, 利用LZW算法进行压缩后为132字节, 压缩率为27%。

四、结论

通过实验结果可以看出, 本文提出的算法是一种有效的无损数据压缩算法。许多学者一直在对LZW及其派生算法加以不断地改进和完善, 使之成为了当今数据压缩的主流算法。

参考文献

[1]David Salomon.吴乐南, 等.数据压缩原理与应用 (第二版) [M].北京:电子工业出版社, 2007.

[2]侯阳.数据压缩技术及C语言实例[M].北京:学苑出版社, 2005.

[3]张凤林, 刘思峰.一个改进的LZW数据压缩算法[J].小型微机计算机系统, 2010, 27 (10) .

[4]林小竹, 籍俊伟.一种改进的LZW压缩算法[J].计算机工程, 2009, 31 (14) .

压缩感知稀疏信号重构算法研究 篇5

关键词：压缩感知,平滑函数,l0范数,信号重构

不同于传统的奈奎斯特 (Nyquist) 采样定理, 压缩感知理论 (Compressed Sensing, CS) [1,2]充分利用信号稀疏性或者可压缩性, 将采样与压缩同时进行, 通过一个观测矩阵将高维信号投影到低维空间, 再通过求解一个优化问题从少量的观测值中实现原信号的精确重构。它极大的降低了采样的复杂度, 节约了采用所需时间, 减小数据获取、传输及处理的压力, 因此CS一出现便引起广大研究人员的关注, 目前其应用研究已经涉及到众多领域, 如图像信号处理[3,4]、语音信号处理[5,6]等等。

压缩感知主要包括三个方面即:信号的稀疏表示, 线性测量, 重构算法。其中稀疏信号重构算法是该理论的至关重要的环节, 其作用是利用尽可能少的测量值来精确地重构出原始信号。目前国内已出现的具有代表性的压缩感知信号重构算法主要有:基于l0范数最小化的贪婪迭代匹配追踪系列算法, 如正交匹配追踪 (Orthogonal Matching Pursuit, OMP) [7]、梯度类算法[8]等;基于l1范数最小化的凸优化算法, 如基追踪算法 (Basis Pursuit, BP) [9]、迭代阈值类算法[10]等;以贝叶斯统计为代表的非凸优化算法, 如FOCUSS[11]算法等。上述算法各有优缺点。

Hosein Mohimani等人2009年提出的平滑l0范数 (Smoothed l0 Norm, SL0) 算法[12], 该算法使用带参数的平滑函数去逼近向量的最小l0范数, 将求解最小l0范数问题转化为平滑函数的极值问题。在此算法的基础上, 文献[13]构造了TSL0 (Thresholded SL0) 算法。针对平滑函数的选取问题, 本文提出一种新的平滑函数序列近似l0范数, 实现稀疏信号的精确重构。仿真结果表明, 该算法在信号测量个数以及稀疏度相同的情况下, 重构概率优于OMP算法和SL0算法。

1 信号重构模型

设将N维实信号α∈RN×1为K稀疏向量, 即该信号包含为K个非零值, 其中K≤N。对该信号进行压缩观测, 将高维信号投影到低维空间,

其中Φ为观测矩阵, Φ∈RM×N, K

上式方程中未知数的个数N大于个数M, 是欠定方程因此有无穷解。充分利用信号α的稀疏特性, 通过附加一定的限制条件可以求解上述方程组。其求解模型为:

2 改进SL0重构算法

SL0重建算法主要采用最速下降法和梯度投影原理, 其关键问题是选取合适的平滑连续函数来逼近l0范数, 通过一个平滑的连续函数来近似逼近向量的最小l0范数, 使得l0范数最小的量就是所求的最优解。文献[12]中采用来近似l0范数。通过改变参数σ, 可以获得最小l0范数解。为了进一步提高其逼近性能, 本文采用如下形式函数作为平滑函数, 来近似l0范数, 显然有

记Fσ (α) =N-Ni=∑1fσ (αi) , α0表示向量α非零元素的个数。其中参数σ的大小决定了逼近的程度, 当σ=0时, 由于, 因此式 (3) 的解就是式 (1) 的解。实际上无法令σ=0, 因此只能通过选择一个递减序列σ1, σ2, σ3, 对每一个σi值对应的目标函数求最优值, 直到σ足够小为止。

采用上述平滑函数结合梯度投影方法进行优化求解, 算法具体步骤如下:

第1步:设定初始值, 重建向量x=ΦTy, 初始余量0r=0, 平滑函数的初始参数σ=1。

第2步:求解-Fσ的梯度d;

第3步:利用修正牛顿算法求得x=x+μd。

第4步:利用梯度投影得到x=x-ΦT (ΦΦT) -1 (Φx-y) , 同时计算余量r=y-Φx。

第5步:得到最优值。

3 仿真分析

为了验证算法的重构性能, 本文通过MATLAB处理平台对算法进行仿真测试。选取信号y=Φα, Φ∈RM×N为服从高斯分布的随机矩阵, α由非零元素±1组成的离散信号, 信号长度N=256。μ取0.5, 重复200次实验, 改变信号的稀疏度和测量次数, 重构概率的变化情况曲线如图1、图2所示。

从图1可以看出测量次数 (M=128) 一定时, 随着信号稀疏度的增加, 三种算法的重构概率逐渐减小, 当稀疏度为40时, 本文算法依然有着较高的重构概率, OMP, SL0算法重构概率相对较低。从图2可以看出, 稀疏度一定时 (稀疏度K=30) , 随着测量次数的增加, 信号重建的概率逐渐增加, 本文算法在相同测量次数情况下有着较高的重构概率。

4 结论

基于压缩传感理论的重构算法研究 篇6

奈奎斯特采样定理指出,为了能重构出原始信号,带限信号的采样频率必须不小于信号最高频率的两倍[1]。然而随着信号带宽逐渐加宽,提高采样率所带来的硬件成本是非常昂贵的[2],这无疑给相应的硬件设备带来了极大的挑战,因而使得宽带信号的处理变得日益困难[3]。

在传统的信号处理过程中,以图像信号为例,首先通过采样取得完整的信号样本,采样过程须满足采样定理;再将信号在某个域(例如频域、小波域等)内进行变换,使信号稀疏化,而后只存储变换后小部分较大的值,最后解码出原始信号。信号处理之后丢弃了大部分采样所得的数据,实现了数据压缩,但不影响最终结果的重建[4]。

2004年D.Donoho[5]、T.Tao[6]及E.Candes[7]等人提出了一种新型的信息处理理论,即压缩传感[8,9](Compressed Sampling,CS)或称为Compressed Sensing、Compressive Sensing,它开启了信号采样的新革命。

与采样定理的区别在于,压缩传感理论表明只要信号通过某种变换后可以稀疏表示,就能以较低的频率进行全局性采样,该采样频率可以远小于采样定理所要求的标准,从而获得少量的全局信号观测值,再通过重建算法将初始信号从测量值中解码出来。

压缩传感理论(下文简称为CS理论)主要包括信号的稀疏表示、非线性编码测量以及重建算法3个部分[10]。

CS理论虽然目前处于研究的初始阶段,但发展迅速,已经发展了多种形式,例如Bayesian CS理论、1-BIT CS理论、无限维CS理论、分布CS理论、变形CS理论等,已成为学术界的研究热点。

由于目前国内对该领域的研究尚处于起步阶段,本研究将对压缩传感理论进行详细介绍,对其中所涉及的关键技术进行综述和整理。笔者在总结现有常用重构算法的基础上,介绍最小均方差线性估计(MMSE)算法,该算法在低采样率下重构效果较好,且适用于工程实际,本研究通过图像的仿真重构突出MMSE算法的优越性及其在实践领域的应用潜力。

1 信号稀疏表示

假如信号中只有极少数非零元素,则该信号是稀疏的。时域信号大都具有非稀疏性,然而通过一些变换则可变得稀疏。

对于离散信号x(n),n∈[1,2,⋯,n],它可以用N×1维的基向量 来线性表示。假设这些基向量都是正交的,则信号x可表示为:

式中:x,s—N×1矩阵;ψ—N×N矩阵;sk=x,ψk=ψTkx。

如果信号x通过变换域ψ的作用后,变换向量中只有K个非零元素sk时,但大部分情况下该条件难以严格满足,因此也可以是具有K个远大于零的系数,此时信号是可压缩的,就可以称s为信号x的K稀疏表示,ψ为信号x的稀疏变换基。

压缩传感理论的先决条件是信号必须经过某种变换后可以稀疏表示。信号的稀疏表示就是将信号作用到某变换域内,大部分的转换系数都较小,此时变换矢量是稀疏的,因此它可以被视为初始信号的简明表示[11]形式。

常用的变换域有快速傅立叶变换(FFT)、离散余弦变换(DCT)、离散小波变换(DWT)[12]、Gabor变换[13]Curvelet变换[14]以及冗余字典[15,16]等。

2 编码测量

CS不是直接测量初始信号,而是测量信号与一个非相关的系统(下文将该系统简称为测量矩阵)作用之后的信号,每一个测量值是所有样本信号的线性组合,因此每个测量值包括了所有采样信号的信息。为此它可看作是全局采样,而奈奎斯特则可看作是局部采样。

因此,压缩传感理论可综合理解为:在某变换基ψ=[ψ1,ψ2,⋯,ψN]上具有K稀疏的信号x∈RN,通过它在另一不相关基Φ=(Φ1T,Φ2T,⋯,ΦMT)上的M(K

获得近似或精确重构,即为:

式中:y—M×1测量向量;Φ—M×N测量矩阵;x—N×1矩阵;Θ—传感矩阵,Θ=Φψ。

压缩传感理论的理论模型如图1所示。

由上述表达可知,y的维数小于x的维数,有无穷个解,因此很难重构出初始信号。但由于s是K稀疏的,且K

为了能重构出原始信号x,测量次数必须达到M=O(K ln(N)),而且传感矩阵也一定要满足受限等距特性(RIP)准则[17,18],但RIP准则计算复杂度相对较高,常用其等价条件,即稀疏变换基不应与测量矩阵相关。

实际应用中稀疏矩阵会因信号的改变而不同,所以希望找到能普遍适用的测量矩阵,能与任意稀疏基都不相关。对一维信号的重构,往往选用高斯矩阵和伯努利矩阵等;对二维信号则常选用随机分布矩阵、Hadamard矩阵以及部分傅立叶变换矩阵等。

3 重构算法

重构算法是CS理论的核心,重构算法的主要内容是从M维的测量向量y中重构出稀疏度为K的信号x。

通过求解式(2)的逆命题,可以求得稀疏系数s=ψTx,理论证明信号重构问题与最小l0范数具有等价性,因此重构问题可转化下式:

式中:||∙||0—l0范数,数学意义是计算信号非零元素的个数。

但上述优化问题是NP-hard问题,理论证明,当测量矩阵满足RIP准则时,l0优化问题与l1优化问题具有等价性,从而将NP-hard问题变为数值上容易处理的优化问题,那么式(3)即转化为l1最小范数下的最优化问题:

最小l1范数优化问题是一个线性规划的凸优化问题,典型的算法代表是基追踪(BP)算法。

本研究整理了相关算法,特别是重构算法中的贪婪算法,该算法目前具有代表性和较高的使用频率。

贪婪算法经常不断发展和完善,已有多种变形,主要包括匹配追踪(MP[19])、正交匹配追踪(OMP[20])、正则化的正交匹配追踪(ROMP[21])、压缩采样匹配追踪(Co Sa MP)以及逐步正交匹配追踪(STOMP[22])等。

本研究详细介绍了贪婪算法的数学原理,并介绍了MMSE算法,该算法在低采样率下能实现较高质量的重构,以下即为算法的详细介绍。

3.1 匹配追踪

匹配追踪(Matching pursuit,MP)算法主要是从y=Φx中重构出最稀疏的x。算法主要是从测量矩阵Φ中,选取出与信号y最为匹配的列向量,也可以称之为原子,来建立一个稀疏逼近,再求出信号的残差;通过若干次迭代,依次不断选取出与对应信号残差相匹配的原子,构建原子组合,那么信号y就能够由所选取原子的线性组合,与最终的残差之和来表示。假如残差在误差范围之内,那么信号y就可以简化为由所选原子的线性组合来简洁表示。

3.2 正交匹配追踪

MP算法是对信号在选定的原子上进行投影,它是不正交的,需要经过多次迭代,算法方能收敛,因此结果不是最优的。

而正交匹配追踪算法(OMP)则有效地解决了这个问题,该算法采用了相同的原子选择准则,区别在于残差的更新方式有所不同。OMP在每次迭代之后,对所有已选择原子进行正交化,使残差与所有已选择原子所生成的子空间正交。经过正交化处理原子被选定以后,在后续的迭代中将再也不能被选取,通过对已选取的原子集合逐步进行正交化处理,因此缩小了迭代的次数,确保了迭代的最优性。

3.3 正则化正交匹配追踪算法

Needell等人为了解决OMP算法中满足RIP准则但有时仍无法精确重构的问题,适时地推出了正则正交匹配追踪算法(Regularized orthogonal matching pursuit,ROMP),该算法对所有稀疏信号和满足RIP准则的测量矩阵都能实现精确地重建。

与OMP的区别在于,该算法先采用相干性,选取出多个符合条件的原子作为候选集合;然后根据正则化原理从候选原子集合选定出符合条件的原子集合,然后纳入支持集,快速实现原子的有效选择。

ROMP算法需要先对信号的稀疏度进行估计,然后才能重建原始信号。但实验表明,对稀疏度的估计要求较高,如稀疏度估计过大,则重建质量较差,不能达到精确重构的效果;如稀疏估计太小,则可能经过几次迭代后仍不能达到停止条件。

3.4 最小均方差线性估计

为了使 最小,现有的CS方法通过直接法得到x的初始解 ,其中 。而分块CS算法由最小均方差线性估计(MMSE)求出初始解 ,其中 表示第i个重建图像块的向量形式,逆可压缩测量矩阵ΦB=Rxx(ΦB)T(ΦBRxx(ΦB)T)-1,其中Rxx表示输入信号的自相关函数,它采用AR的相关系数为0.95的模型来近似。由于ΦB的尺度较小,MMSE算法易于实现[23]。

4 仿真结果对比

为了说明上述算法的重构效果,本研究采用大小为256×256的Boat图像进行重构实验。算法中采用小波基作为稀疏变换基,利用高斯随机矩阵作为测量矩阵,Boat的原始图像如图2所示。

Boat图像在采样率为10%时MP、OMP、ROMP以及MMSE算法的重建效果如图3所示。由图3可见,在采样率相同的情况下,MMSE算法进行图像重构的效果明显优于MP、OMP和ROMP算法,三者要在采样率为60%时才能达到该重构效果。

随着采样率的提高,各算法重构质量都有明显提高,但MMSE算法的重构效果始终明显优于MP、OMP、ROMP算法。当采样率为10%,后3种算法效果较差,重建后无法重构原始图像,但MMSE算法重建图像质量依然较高,仍然可以重建原始图像,显示了很大的优越性。

笔者研究发现MMSE算法模型与实物重构模型类似,有着较好的应用潜力,目前国内压缩传感理论大都停留在理论研究阶段,鲜有涉及硬件系统开发应用,如能设计出一套与实物重构模型相匹配的硬件系统,MMSE算法将在实践中体现出低采样率下重构质量较高的优势,将是实践领域的另一突破。

5 结束语

本研究主要阐述了压缩传感理论,并深入研究了重建算法中使用频率较高且具代表性的MP、OMP、ROMP算法,对其原理进行了较为详细的论述,与此同时对性能稳定、重构质量较好的最小均方差线性估计(MMSE)方法也进行了介绍。笔者通过各算法对二维图像进行了仿真重构,突出了MMSE算法在低采样率下重构质量较好的特点,并指出其在实践中有着较好的应用潜力。

压缩传感理论引起了信号处理领域的重大改变,它丰富了信息获取理论,而且对其他学科产生了很好的启迪和借鉴作用,有着良好的应用前景,但如何将其应用于工程实践则是另一个严峻的机遇和挑战。

摘要：针对国内压缩传感理论(CS)尚处于起步以及理论研究阶段,为深入阐述该理论及对其实践应用性进行探索,将压缩传感理论从信号的稀疏表示、编码测量以及重构算法3个方面展开了较为详细的论述,并深入地阐述了重构算法中具有代表性的匹配追踪、正交匹配追踪、正则化正交匹配追踪算法。并进一步介绍了最小均方差线性估计(MMSE)算法,通过与常用重构算法的仿真对比,突出了MMSE算法在低采样率下的优越性。研究结果表明,该算法在实践中具有较好的应用潜力。

视频压缩中运动估计算法的研究 篇7

近年来,多媒体技术的飞速发展,在众多应用领域,对视频图像的实时压缩提出了更高的要求,快速、高效的压缩算法是解决这一问题的关键。

运动估计是视频压缩编码系统中非常重要的模块,它直接影响到视频数据压缩编码的效率和编码质量。运动估计越准确,编码的效率就越高,解码出来的视频质量就越好。同时,运动估计的计算复杂度在整个视频数据压缩编码系统中最大,占整个系统计算量的50%以上。因此,运动估计性能的好坏不仅很大程度上决定了视频图像压缩编码的质量,还根本性地决定了整个视频压缩编码系统的实时性能。

研究高效的运动估计算法对提高视频数据压缩编码的效率有着非常重要的实际意义,是解决目前视频数据中高效压缩问题的有效途径。因此,运动估计作为实现视频压缩的核心技术,一直是视频压缩领域的研究热点。

1 MVFAST算法

Hosur和Kai-Kuang Ma等人在1999年提出了动矢量场自适应搜索算法(motion vector field adaptive search technology,MVFAST)[1]。在2000年3月的MPEG Noordwijkerhout会议上,MVFAST作为运动估计的核心算法被纳入MPEG-4新增的第7部分。

1.1 算法基本思想

MVFAST算法的基本思想是以视频运动的时空相关性为基础,首先通过搜索起始点的预测使当前块的初始运动矢量有可能接近最终运动矢量;其次通过简单有效的视频分类和合适的搜索模式,使其能根据视频运动的类型进行自适应的搜索;最后采用高效的搜索中止准则以保证搜索结果在这个预测的起点附近结束时具有足够的精度,从而实现快速且精度高的运动矢量搜索。

1.2 基本方法

大菱形搜索模式的方法如下:

Step 1:按照图1(a)的点位近9点搜索,如果中心点的SAD值最小,则转到Step 3,否则转到Step 2。

Step 2:将搜索中心移到在上次搜索中得到的最小SAD值对应的点位上,再进行1次大菱形搜索,如果中心点的SAD值最小,则转到Step 3;否则,重复执行Step 2。

Step 3:将大菱形搜索模式转换为小菱形搜索模式,并将搜索中心移到在上次搜索中得到的最小SAD值对应的点位上,只进行1次小菱形搜索,将得到的最小SAD值对应的点位设置为最终的运动矢量值。

小菱形搜索模式的方法如下:

Step 1:按照图1(b)的点位进行5点搜索,如果中心点的SAD值最小,则中心点对应的位置就是最后的运动矢量值,否则转到Step 2。

Step 2:将搜索中心移到在上次搜索中得到的最小SAD值对应的点位上,再进行1次小菱形搜索,如果中心点的SAD值最小,则选择中心点的位置为最终的运动矢量;否则,重复执行Step 2。

MVFAST算法考虑几个相邻块的运动矢量确定菱形搜索的起始点,并根据宏块的不同运动强度自适应地选择大小模板来进行匹配搜索,在图像质量和速度上都表现出了好的性能,而且不需要辅助内存来存储搜索点和运动矢量。

2 改进算法思想

2.1 块运动类型划分的改进

运动物体的整体性和视频运动的连续性致使视频的运动具有时间和空间上的相关性,这种相关性可以用来预测当前块的运动方向和运动大小,因此对当前块的运动类型进行划分。一般而言,当前块与前一帧对应位置块的像素值绝对差和SAD在一定程度上反映出图像变化的剧烈程度。SAD值大,反映图像变化大,运动速度快;SAD值小,反映图像改变小,图像变化不明显。因此可利用与前一帧对应位置块的SAD值来进行块运动类型划分[2]。为更准确地划分块运动类型,改进算法综合使用这两类依据,使得当相邻参考块与当前块的相关性较弱时,不至于引起不准确的运动类型划分。

改进算法的块运动类型划分依据如下:设参考块的运动矢量集合为V={V0,V1,V2,V3,V4}。其中,V0=(0,0),Vi=(xi,yi)(i≠0)为图2中的1,2,3和4块的运动向量。对于V中的所有候选矢量,令li=|xi|+|yi|,L=max{l1,l2,l3,l4},设定阈值L1和L2。令当前块与前一帧对应位置块中像素值的SAD值为SAD0,设定阈值T1和T2。当SAD0≤T1时,当前块被认为是静止块;当T1T2且L≤L2时,当前块被认为是中等运动块;否则当前块被认为是大运动块。

这种划分方法相对MVFAST算法中的方法加强了划分的条件判断,但并未因使用与前一帧对应位置块的SAD值而增加计算量和存储复杂度,因为当前块与前一帧对应位置块中像素值的SAD值SAD0在进行静止块检测时已计算出,而且在静止块检测后,就可以进行此块运动类型的判断,无需存储SAD0值。

2.2 起始搜索点预测

改进算法采用了MVFAST算法中起始搜索点的选取方式,即搜索起始点根据当前块的运动类型进行设定:如果当前块为小运动块或中等运动块时,意味着子块的最优运动矢量位于(0,0)附近较小的区域内,无需进行起始点预测;如果当前块为大运动类型块,其最优运动矢量往往偏离中心点(0,0)较远,精确预测的搜索起始点更接近物体的真实运动矢量,从而减少搜索点数。

视频运动的时空相关性可以用来对搜索起点进行预测[3,4],其基本思想是:用空间位置上相邻且已经编码的块或时间上相邻且已编码的块的运动来预测当前块的初始运动矢量,再以此为起点做进一步的搜索。综合考虑计算量和预测效果等因素,选择左上,右上3个空间相邻块(如图2中的1,2,3)和上一帧对应位置块(如图2中的4)中运动矢量的对应点作为候选点进行预测。

搜索起点预测的主要方法有中值法、加权法和SAD比较法。因为SAD比较法的预测精度最好,能够最快地寻找到最优矢量,同时它所得出的预测起始点必然是某个相邻块的运动矢量,使得运动矢量场具有连续性,利于差分编码,所以改进算法采用了SAD比较法来预测搜索起始点。

2.3 大运动块的相对运动类型划分

改进算法加强判定小、中等运动类型的条件,使得更多的块判定为大运动块,要进行起始点的预测。这样,一方面更多的块由于使用预测的起始点进行匹配搜索而减少搜索点数,加快搜索速度;另一方面,由于块间相关性的不同,预测的准确性必然不同,若对这些大运动块采用相同的搜索策略,必然造成搜索不足或搜索冗余。因此考虑将大运动块在搜索起始点预测后进行相对预测点的相对运动类型的划分,将大运动块分为相对静止块、相对小运动块和相对大运动块。为避免复杂条件计算,其判别仅利用当前块与预测起始点对应块的像素值的SAD值,令其为SADp。如果SADp≤T1,则判定当前块为相对静止块;如果T1T2,则判定当前块为相对大运动块。

2.4 搜索模式

搜索模式根据图像宏块的移动剧烈程度不同而不同,但是搜索模式也不宜复杂。在兼顾速度和精度的要求下,改进算法根据预测的运动剧烈程度选用不同的搜索模式:小运动使用简化的小菱形搜索模式,即只进行一次小菱形搜索;中运动使用小菱形搜索模式;大运动根据起始搜索点预测的准确性自适应地选择搜索模式,相对小运动块使用简化的小菱形搜索模式,相对大运动块使用小菱形搜索模式。

2.5 搜索中止准则

为提高算法的速度,一些算法使用了SAD阈值作为搜索中止的条件,即当SAD值小于某一阈值时中止搜索过程。MVFAST采用固定的阈值,PMVFAST则以当前块中左边、上边和右上边相邻块的最小SAD的最小值作为阈值。事实上,固定的阈值不具有普适性,而当前帧相邻块的最小SAD分布在数值上也没有很明确的相关性。但相邻帧对应位置块的最小SAD值间普遍存在着某种比例关系,其平均比值在0.95～1.07之间。为此,改进算法的搜索中止准则是:以参考帧对应位置块的最小SAD值乘以某个系数作为SAD阈值,即若SAD

3 改进算法描述[7,8,9,10]

改进算法的具体描述如下:

(1)初始化阈值。根据实验经验值选取阈值L1=1,L2=2。若当前块为第一个P帧内的块,阈值T1设为512,否则,T1=a×Ref_SAD,其中,a为常数,设定为0.95,Ref_SAD为参考帧对应位置块的最小SAD值。若T1<512,设定T1=512;若T1>1 024,设定T1=1 024。阈值T2设定为T2=T1+256。

(2)静止块检测。搜索零矢量位置(0,0)点,得出该点的SAD值SAD0,如果SAD0≤T1,则判定该块为静止块,(0,0)位置即为最优运动矢量。

(3)运动类型检测。对于非静止块,计算L,当T1T2且L≤L2时,当前块被认为是中等运动块;否则当前块被认为是大运动块。

(4)初始搜索点的选取。根据当前块的运动类型设定搜索起始点,如果当前块为小运动块或中等运动块时,无需进行起始点预测,以中心点(0,0)为搜索起点;如果当前块为大运动类型,计算运动矢量集合V中的每个运动矢量对应的SAD值,将最小SAD值对应的运动矢量Vn所对应的点作为搜索起始点。

(5)执行搜索。对于小运动块,只使用1次小菱形搜索,就输出运动矢量,并保存最小SAD值。对于中等运动块,使用小菱形搜索至最优点在小菱形中心点,输出运动矢量,并保存最小SAD值;对于大运动块,在搜索起点预测后,计算SADp,当SADp≤T1时,当前块被认为是相对静止块,提前结束搜索;当T1T2时,当前块被认为是相对大运动块,使用小菱形搜索至最优点在小菱形中心点,输出运动矢量,并保存最小SAD值。在执行搜索的过程中,一旦满足提前结束搜索条件SAD≤T1,结束搜索,输出运动矢量,并保存最小SAD值。

4 改进算法性能测试

采用改进算法分别对Mother and daughter序列中,Foreman序列的前100帧和Football序列的前90帧进行实验。表1、表2列出FS,MVFAST,PMV-FAST和改进算法的实验结果。其中,各项评估标准均为序列各帧的平均值,加速倍数和ΔPSNR均以FS算法的搜索结果为基准。

dB

表1、表2实验数据表明,与FS算法相比,改进算法在PSNR稍有下降的情况下,搜索速度得到大幅度提高;与MVFAST和PMVFAST算法相比,改进算法在PSNR稍有下降的情况下,搜索点数分别平均下降1.86个和1.09个。

图3给出了压缩前Foreman序列的第98帧图像及其解码后的恢复图像。可以看出,改进算法在加快运动估计搜索速度的同时,图像质量并没有明显下降。

实验结果表明,本文提出的改进运动矢量场自适应运动估计算法具有搜索速度上的明显优势,但恢复图像质量只稍有下降。

5 结语

基于对MVFAST算法的分析,充分利用视频图像的特点和运动矢量分布特性,提出了一种改进的运动矢量场自适应运动估计算法。改进算法基于MVFAST分级搜索的思想,优化了运动强度的划分方法,引入了相对运动类型的划分来对大运动块自适应地选择搜索模式,搜索中尽量使用简单策略,并自适应地提前结束搜索。实验结果表明,改进算法具有搜索速度上的明显优势,但恢复图像质量稍有下降。

摘要：MVFAST算法是视频压缩中一种重要的运动估计算法,但其缺乏是对图像时域相关性的考虑会造成不恰当的运动类型划分。因此,针对这个问题提出一种改进的运动矢量场自适应运动估计算法。该算法基于MVFAST分级搜索的思想,通过优化运动强度的划分方法,引入相对运动类型的划分来对大运动块自适应地选择搜索模式,使用简单的搜索策略,自适应地提前结束搜索。实验结果表明,该改进算法与MVFAST算法相比,在图像质量稍有下降的前提下,具有搜索速度上的明显优势。

关键词：视频压缩,运动估计,块匹配,搜索策略

参考文献

[1]HOSUR P I,MA K K.Motion vector field adaptive fast motion estimation[C]//Proc.2nd Int.Conf.Information, Communications and Signal Processing.Singapore:ICICSP, 1999:79-88.

[2]魏星,蒋建国,齐美彬.基于选择预测的自适应运动估计算法[J].中国图像图形学报,2005,10(7):873-877.

[3]HSIEH C H,LU P C,SHYN J S,et al.Motion estimation algorithm using interblock correlation[J].Electronics Letters, 1990,26(5):276-277.

[4]施建良,潘健,余松煌.区域运动相关性的运动估计方法[J].上海交通大学学报,1998,32(9):6-9.

[5]徐丽琨,黄登山.基于H.263视频压缩的新钻石搜索算法[J].微计算机应用,2005,26(5):516-520.

[6]徐丽琨,黄登山.基于H.263标准的视频压缩算法的优化及研发[J].电力系统通信,2005,26(7):31-34,41.

[7]武媛媛,郭英,苏兮,等.改进的十字菱形搜索算法[J].中国体视学与图像分析,2009(2):168-172.

[8]刘锋,庄奕琪,何威.一种新的算法可编程的运动估计协处理器[J].电路与系统学报,2007(5):126-130.

[9]何军球,赵欢.基于运动复杂度的快速模式选择算法[J].计算机工程与应用,2009(7):79-81.

[10]黎仁国.基于图像复杂度SAD计算的H.264全搜索快速算法[J].绵阳师范学院学报,2009,28(1):88-90.