分块压缩

分块压缩（精选3篇）

分块压缩 篇1

0 引言

人脸作为进行身份鉴别的一种生物特征, 一直受到研究人员的关注, 但人脸特征很复杂, 如何准确地进行人脸识别已成为模式识别领域的一个难点和热点, 它作为模式识别领域中一个富有挑战性的课题, 具有广泛的应用前景和研究价值[1,2]。近几年, 国内外学者提出很多人脸识别的方法, 也取得了不错的效果。但目前还有很多方面有待深入研究, 如光照、表情变化、遮挡和噪声问题等[3]。

压缩感知 (Compressive Sensing, 简称CS) [4]是近几年流行起来的一个新领域, 由Candes[5]、Terres Tao[6]等人提出, 文献[7]指出, 当一个信号具有稀疏性, 或者在某个变换域是稀疏的, 或是可压缩的, 就可以用一个与变换基不相关的观测矩阵将变换所得的高维信号投影到一个低维空间上, 同时这种投影保持了重建信号所需的信息, 然后通过求解一个最优化问题就可以从这些少量的投影中重构出原始信号。目前, CS理论是一个快速发展的技术, 在信号处理和图像识别等领域取得了很好的效果, 如医学图像处理、生物传感、光谱分析和遥感图像处理等。

基于压缩感知的人脸识别 (SRC) 把所有的训练图像组成一个样本集, 然后把待测图像用训练样本的线性组合来表示, 通过求解稀疏系数来判断待测人脸图像的类别。该方法取得了良好的识别效果, 但是对于噪声和遮挡图像, 识别效果不是特别理想。介于此, 提出了分块的基于压缩感知的人脸识别算法。

1 基于压缩感知的人脸识别

假设每一类训练样本的数量足够多[8], 第k类训练样本矩阵表示Ak=[vk, 1, vk, 2, ..., vk, nk]∈Rm×nk, 其中nk表示第k类训练图像的数目, 表示第k类第nk张人脸图像, 则同样属于该类的待测样本向量y∈Rm可以用该类训练样本的线性组合表示为:

由于样本所属类别k是未知的, 将所有w个类别的n个训练样本串接在一起, 组成一个新的训练集矩阵A:

则待测图像y就可以用所有的训练样本线性表示为:

如果待测图像属第k个人, 则在理想情况下, x=[0, ..., 0, αk, 1, αk, 2, ..., αk, n, 0, ..., 0]T∈Rn, 即只有第k类的值是非零的元素, 可见x是一个稀疏向量。

接着对每一个y解出其稀疏向量x, 一旦得到x, 结合已知的训练样本矩阵A, 即可以知道待测图像y的类别。

将上述理论表示成数学模型, 即为:

但在人脸识别中, 对图像进行降维后, 通常有维数m

这样就将原本的NP问题转化为求解l1范数最小化问题。对于式 (5) 可以采用多种方法求解, 用正交匹配追踪算法 (OMP) [10]进行求解, 得到待测图像的稀疏解后, 就可以对测试图像进行判别归类。图1为Extended Yale B人脸数据库中第2类第5幅图像进行稀疏表示后的结果, 其稀疏系数对应800个训练样本 (每类40幅训练图像) 的线性组合, 较大的2个系数0.424 5、0.771 6, 其对应的序列值为78、71, 均属于第2类样本, 因此, 可以判定测试图像为第2类人脸图像。

然而, 在实际计算中, 由于噪声等误差的存在, 很难得到只有某一类的系数为较大非零值的情况, 所以如果得到的结果中有2类或者2类以上存在较大非零值时, 就可以用下面的重构误差方法进行判断:

用与第k类相关的元素, 将测试图像y的估计值写为 ) (向量δk (x) 为x中与第k类相关的非零元素) , 接着计算所有y^k与y之间的差, 并将差最小的k置为y的类别:

2 改进的分块人脸识别

遮挡问题是人脸识别中的常见问题, 也是人脸识别系统设计的重点和难点。要将人脸识别系统推广到实际应用中, 遮挡问题是必须要得到解决的。实际情况中, 人的头发、眼镜和伤疤等外部环境都可能导致人的面部被遮挡, 而用户不可能控制这些外部环境的干扰去配合人脸识别系统, 因此必须找到切实可行的方法解决这一难题。受外界因素的影响, 图像在采集和传输过程中不可避免地会产生噪声, 从而影响人脸识别系统的识别效果, 因此噪声问题也是人脸识别系统不可忽略的一部分。

针对上述问题, 提出了一种基于分块的压缩感知人脸识别算法。首先输入训练图像和测试图像, 利用分块算法对每一幅训练图像和测试图像进行分块, 再将每一个子图像块进行向量化, 然后采用正交匹配追踪算法 (OMP) 对分块后的图像进行匹配识别并得到一个局部残差, 通过这个残差值判断出每一子图像块的所属类别, 看这些子图像块所属哪一类别的数目最多, 最多的那类即为整幅测试图像的识别结果。若子图像块所属的类别数目有2个或2个以上是相等的, 则通过将每个子图像块的局部残差相加计算出测试图像对于数据库中所有人脸图像的最终残差值, 然后选择最终残差值最小的分类作为测试图像的识别结果。

算法的执行流程如下:

(1) 从人脸图像数据库抽取k张人脸图像并存入训练集A中, 从人脸数据库中提取出另外w张人脸图像作为测试集B中的元素, 设定分块数为p×q块;

(2) 遍历训练集A中的图像并依次对k张人脸图像进行分块, 得到p×q块子图像, 训练集A中第i幅图像的第j个子图像块表示Ai, j (i=1, 2, …, k, j=1, 2, …, p×q) ;

(3) 依此遍历测试集B中的元素并对w张人脸图像进行分块, 对测试集B中第s幅图像进行分块得到的第j个子图像块表示为Bs, j (s=1, 2, …, w, j=1, 2, …, p×q) ;

(4) 用训练集A中每幅图像的第j个子图像块构成一个新的训练样本矩阵Aj, 然后对测试集中的第s幅图像的第j个子图像块Bs, j与新的训练样本矩阵Aj进行SRC算法求解, 得到残差最小值作为子残差rs, j, 根据rs, j找出Aj中与Bs, j图片最匹配的图像, 判断Bs, j所属的类别。令j分别等于1, 2, …, p×q, 重复该步骤;

(5) 统计测试集中第s幅图像p×q块子图像所属的类别, 类别数量最多的即为第s幅图的最终识别结果;

(6) 若出现类别数量相同的情况, 则对Bs, j和Ai, j进行SRC算法匹配, 得到子残差Ri, j, 令j分别等于1, 2, …, p×q, 重复该步骤。计算总残差 , 然后对Ai+1执行 (4) , 遍历完成后通过寻找min (Ri) 比较总残差, 找出A中与测试集的第s幅图像最匹配的图片作为结果;

(7) 计算识别率, 程序运行结束。

3 仿真实验结果及分析

3.1 仿真实验

本实验使用Extended Yale B人脸图像数据库, 该数据库共有38个人在不同光照条件下的共2 432张人脸图像, 每张图像都是在严格条件下采集的, 且经过统一的裁剪, 其图像分辨率为192×168。实验中随机选取每个人的40幅图像作为训练样本集, 另外20幅作为测试图像。

本实验主要研究椒盐噪声、高斯噪声、乘性噪声下的人脸图像以及分别遮挡住鼻子、眼睛、嘴、一部分脸蛋的图像进行识别的识别效果, 如图2和图3所示。由于子块数目过多会影响计算的复杂度, 子块数目过少会降低抗遮挡能力, 所以子块数目的选择很重要, 通过反复实验, 发现分块数为4×4时效果最好, 故本实验设定分块数为4×4。

分别用原始SRC人脸识别方法和改进的分块人脸识别方法对不同噪声污染后的人脸图像进行了识别, 并对其进行了详细的比较, 识别效果如表1 (实验结果为5次实验的平均值) 所示。

表2显示的数据是分别用原始SRC人脸识别方法和改进的分块人脸识别方法对遮挡人脸各种部位后的人脸图像进行识别的识别效果 (实验结果为5次实验的平均值) 。

3.2 结果分析

由实验结果可以看出对于噪声图像, 2种方法的识别效果几乎相同, 椒盐噪声和高斯噪声图像的识别率都在96%左右, 乘性噪声图像的识别率均为98.25%, 2种方法对噪声图像都具有很好的识别效果, 但改进效果不明显。

对于遮挡图像, 改进的基于压缩感知的人脸识别方法比原始的SRC在识别率上有很大的提高, 平均多出7%~8%以上, 取得了很好的识别效果, 说明改进的分块方法对于遮挡的鲁棒性相对于原SRC算法在识别性能上得到了进一步的提升, 具有较好的鲁棒性和识别效果。从表2的数据可以看出遮挡住人的眼睛、鼻子和嘴, 对识别效果会产生很大的影响, 但挡住脸蛋儿对整个识别率的影响几乎没有。

4 结束语

对原有的基于压缩感知人脸识别算法进行了深入的分析和研究, 并在SRC算法的基础上加入了分块思想, 一方面保留了原SRC算法的优越性, 同时又使遮挡问题得到了很好的解决。由于分块算法是直接对原始像素进行处理, 不会像其他特征提取算法那样造成图像信息的丢失, 同时分块也很好地避免了图像中局部信息损坏对整体识别效果的影响。但是, 改进的分块人脸识别方法对噪声图像的识别效果没有多大提高, 在以后的研究工作中, 需要进一步探索新方法, 使其对噪声和遮挡问题都具有很好的识别效果和性能。

摘要：基于压缩感知的人脸识别算法 (SRC) 利用了高维数据分布的稀疏性进行建模, 能够很好地解决图像高维处理问题, 有效地避免维数灾难。对基于压缩感知的人脸识别算法的基本原理进行了深入地分析和研究, 并对SRC算法进行了改进, 提出了基于分块思想的压缩感知人脸识别算法, 解决了人脸图像识别中存在的遮挡问题, 避免了特征提取过程所造成的图像信息丢失, 也避免了图像中局部信息的损坏对整体识别效果的影响。通过仿真实验表明改进算法的识别率比SRC算法的识别率提高了7%8%。

关键词：人脸识别,压缩感知,分块,遮挡

参考文献

[1]王映辉.人脸识别原理、方法与技术[M].北京:科学出版社, 2010.

[2]GEMMEKE J, HAMME H, CRANEN B, et al.Compres-sive Sensing for Missing Data Imputation in Noise RobustSpeech Recognition[J].IEEE Journal of Selected Topicsin Signal Processing, 2010, 4 (2) :272-287.

[3]QIAO Li-shan, CHEN Song-can, TAN Xiao-yang, et al.Sparsity Preserving Projections with Applications to FaceRecognition[J].Pattern Recognition, 2010, 4 (2) :331-341.

[4]BAY H, ESS A, TUYTELAARS T, et al.SURF:Speededup robust features[J].Computer Vision and Image Under-standing, 2008, 110 (3) :346-359.

[5]DONOHO D L, TSAIG Y.Extensions of Compressed Sens-ing[J].Signal Proeessing, 2006, 86 (3) :533-548.

[6]CANDES E, ROMBERG J, TAO T.Robust UncertaintyPrinciples:Exact Signal Reconstruction from Highly In-complete Frequency Information[J].IEEE Trans on Infor-mation Theory, 2006, 52 (2) :489-509.

[7]DONOHO D L.Compressed Sensing[J].IEEE Trans.onInformation Theory, 2006, 52 (4) :1289-1306.

[8]WRIGHT J, YANG Y, GANESH A, et al.Robust FaceRecognition via Sparse Representation[J].Pattern Analy-sis and Machine Intelligence, 2009, 31 (2) :210-227.

[9]CANDES E, WAKIN M.An Introduction to CompressiveSampling[J].Signal Processing Magazine, 2008, 25 (2) :21-30.

[10]HAUPT J, NOWAK R.Compressed Sampling for SignalDetection[C]//IEEE International Conference onAcoustics, Speech, and Signal Processing.Honolulu, Ha-waii, USA:2007:1509-1512.

分块压缩 篇2

该领域的关键问题集中在信号的重构算法上, 基于匹配追踪算法 (Matching Pursuit, MP) , 能够在信号被采样后, 直接提取其特征量。由于其迭代结果都是非最优的, 因此, 迭代多次才能获得收敛。正交匹配追踪算法, 即OMP算法与MP算法相同, 均采用原子选择准则, 不同的是, 该算法通过递归处理选择的原子集合, 以此保证迭代最优, 有效的减少迭代次数[2]。

1 压缩感知与OMP算法

1.1 压缩感知

信号压缩处理中, 先对待压缩数据进行采样, 采样频率高于信号带宽二倍。将取得的采样值, 变换到其稀疏域上, 获取相应系数。去掉编码中不必要的零值或接近零值, 保留有效值。对保留的有效值进行编码后储存或传输。很明显, 这样处理流程对信号采集端, 产生巨大压力, 而计算量的增加并没有缩减时间, 同时浪费采样资源。压缩感知理论, 能够避免采样频率的限制, 而将计算复杂部分交给解码端实现, 通过这种手段, 能够降低采集端的计算量, 实现高效传输。

假设, 某一维信号x, 为一信号的子项, 各项数据都在实数域上, 其表达式定义为x=[X1, X2, ..., XN]T, 长度为N。对该信号进行CS采样, 得到y值, 定义为观测信号, 这种过程可以表示为:

观测值y长度小于N, 设为M, 称矩阵 (37) 为观测矩阵, 矩阵大小为M×N。研究的图像信号通常为非稀疏, 因此, 需要将x变换到其某一稀疏域上, 即

其中, s为信号x稀疏变换后所得的变换值, 稀疏度用K表示。

合并上述两公式, 得到

由于式 (1) 需要解出的x是欠定方程的未知数, 无法直接从观测值计算得到方程解。因此, 求解目标转变为该方程组所有解中, 最稀疏的x值, 即为CS压缩信号恢复值。问题转换为P0求解最优l0范数问题。

上式求解是一个NP问题, 结合CS理论约束等距性RIP (Restricted Isomtry Proper) 条件, 则能够高概率重构原始信号。

其中, 观测矩阵满足

对于原始信号x, 如果信号需要稀疏变换, 其变换矩阵与观测矩阵不相关, 则方程很大概率上满足约束等距性质。问题可以进一步转化为l1范数求解, 即:

l1范数最小化问题可使用基追踪求解, 并转换为线性问题, 通过凸优化算法求解。

1.2 OMP算法步骤

输入数据包括:观测矩阵、采样值、稀疏度, 分别用Φ、y、K表示。

输出无法精确求出, 因此以x的K-稀疏逼近x代替。

1) 令残差r0=y, 索引集非空, 迭代次数t=1。

2) 求残差r和传感矩阵的列内积中最大值对应的脚注, 即

3) 索引集得到更新, 进而求解重建集合

4) 利用最小二乘法逼近待重构数据近似解:

5) 更新残差值:

6) 判断t>K, 若满足则不再更新残差, 反之, 从步骤2) 开始继续执行。

虽然OMP算法与MP算法, 同样运用原子选择原则, 但其不同点, 在于迭代中通过递归后, 所选全部原子得到正交化处理, 因而, 能够减少该算法的迭代次数[3]。

2 重构分析及梯度判决

2.1 图像分块重构步骤

1) 对待处理图像A分成相等大小的正方块, 假定待测图像大小为N*N, 其每块分解成n*n大小。分块过小不利于CS正确处理, 分块过大, 会使迭代次数增加, 不利于计算。经测试, 本文试验256*256的图像, 选取块大小为4*4。

2) 对分块图像进行二维DCT变换。针对4*4图像, 选取相同的观测矩阵, 常规采用高斯矩阵。应用CS理论, 观测分块图像, 得到测量值。

3) 根据测量值和观测矩阵, 应用OMP算法恢复数据, 得到块重构图像。

2.2 实验结果与分析

本文使用matlab仿真, 实现图像经过CS采样, 分块时域图像DCT变换。所得结果如图1所示。应用OMP算法, 将分块图像重构结果, 如图2所示。计算其峰值信噪比, PSNR值为308.1476。

3 结论

本文研究压缩感知理论在图像信号方面的应用。采用压缩感知降低采集端复杂度, 应用计算能力较强设备在接收端, 采用OMP算法重构图像。试验表明, 通过选取适合的块大小, 能够提高图像重构质量。

摘要：本文研究压缩感知对一维信号处理的方法 , 将该思想应用于图像处理领域。通过将图像分块, 得到带压缩数据, 经DCT变换, 使得图像信号映射到其稀疏区域。将压缩信号, 采用OMP算法, 恢复得到分块图像, 实现图像重构。

关键词：压缩感知,图像处理,OMP

参考文献

[1]喻玲娟, 谢晓春.压缩感知理论简介[J].电视技术, 2008, 32 (12) :16-18.

[2]刘亚峰, 刘昱, 段继忠, 等.基于DSP的OMP算法实现及音频信号处理[J].电声技术, 2012, 36 (2) :60-63.

分块压缩 篇3

关键词：LZW算法,数据压缩,电子词典,哈希表

0.引言

数据压缩是计算机与软件领域不可或缺的重要组成部分。数据压缩早已广泛地应用于数据的传输、数据存储等领域以减少传输时间和节省存储空间。目前,在桌面应用中常用的压缩工具已经有Win Zip、Win RAR等,虽然在嵌入式领域没有比较统一的压缩工具,但是嵌入式领域的数据压缩要求更高,条件更苛刻,因为在嵌入式系统中处理速度、内存资源等相对桌面系统来说都非常有限。本文的实现方式是为了应用于嵌入式系统的场合,特别适用于电子词典字词数据库压缩的应用。

1. LZW算法处理过程

LZW是一种先进的基于字典或者称为串表的压缩算法。它的基本思想就是以8位的字符为基本单位,用固定长度的数据对可变长的字符串进行编码,只要编码数据长度比字符串长度短就能达到压缩的效果。

在压缩过程中,先在串表中建立256个单字符字符串的表项,然后从待压缩字符流中取第一个字符作为前缀字符串。进入循环,取第二个字符作为后缀字符。如果前缀字符串与后缀字符构成的新字符串是第一次出现的,即没有出现在当前串表中,就将前缀字符串的编码输出,同时对这个新的字符串进行编码并添加到串表中,然后将后缀字符作为下一次循环的前缀字符串处理。相反,如果这个新构成的字符串已经出现在当前串表中,那么只需要将新字符串作为下一次循环的前缀字符串处理。这之后又从待压缩字符流中取出下一个字符作为后缀字符,重复以上处理过程直至数据压缩完成。LZW的解压过程与压缩过程基本一致。

2. 算法实现的改进

2.1 变长编码代替定长编码,提高压缩比

数据压缩的本质是尽量减少数据存储中的冗余信息,使压缩后数据达到最大信息熵。LZW算法在对前缀字符串进行编码时需要对单字符字符串建立256项的相应串表,然后才能从256开始编码,256用二进制表示需要9位。实现中从257开始编码,256作为结束码。如果数据足够长,编码将超过9位,甚至10位、11位或更长,编码值在256-511之间时只需要9位,编码值在512-1023之间时只需要10位,依次类推。假设串表项数有4096项,则可以编码到12位。如果使用12位的定长编码,那么编码只需9位、10位、11位时分别有3位、2位和1位的冗余信息。为了进一步提高压缩比应当将这部分冗余信息压缩,所以需要使用9位到12位的变长编码,使当前的编码位数随着所需要的位数变化。如果串表项已经填满4096项时数据还没有压缩完毕,则可以将串表项清除重新从9位开始编码。而且串表清除后不需添加清除标志,就可以顺利地实现前后的无缝连接,解压时能够自动判断串表已填满。实现中编码的最大长度使用宏定义,原则上只需要修改宏定义就可以方便地改变最长编码。

2.2 利用哈希表形式组织串表,加速压缩过程

在压缩过程中,有一步需要判断前缀字符串与后缀字符组合成的新字符串是否在当前串表中,这是很费时间的一个操作。通常都会使用哈希表方式组织串表来加速判断过程。哈希表必须有哈希函数、数据项和主键三个构成因素,这里的数据项就是串表项中前缀字符串编码和后缀字符两部分,而主键就是当前串表项字符串的编码。为了确保在哈希表内查找时不会进入死循环并且进一步加速查找过程,实现中主键初始化位0x FFFF,向串表添加数据项时主键就使用字符串的编码值。如果数据项直接定义成字符串,则无论是字符串的对比还是存储都会带来很多问题。这里巧妙地使用前缀字符串的编码与后缀字符构成数据项,使哈希表的数据项长度固定并加快对比。哈希函数使用常用的余数法:

即,哈希表项索引(哈希值)=哈希表数据项mod哈希表的项数

注意,这里哈希表的项数不能取2的整数次幂,如果这样哈希值只能取到数据项的后几位从而没能反映数据项的所有信息。应当略超过2的整数次幂。哈希表难免会出现冲突。当出现冲突时就将哈希值跳过固定的表项数循环判断。

2.3 引入索引表,加速哈希式串表更新

用LZW算法对数据进行压缩是利用了数据中字符串连续出现的特性,使编码所代表的字符串尽可能的长。从编码过程可以看出,每当前缀字符串与后缀字符构成的字符串已经在串表中出现时都不会有数据输出而是将这个字符串作为下一个前缀字符串,以达到字符串最长化的效果。我们可以推测出压缩与解压过程中所创建的串表有这样一种规律,即串表靠前部分的编码所代表的字符串大多数相对较短而靠后部分的编码所代表的字符串大多数相对较长,使编码字符串形成一种有波动的犹如锯齿型的串表。因为靠后的字符串能充分利用前面编码的字符串进行编码。这种前后编码之间的关系使得每个编码的字符串都可以通过与它相关的前面的编码和对应后缀字符来恢复。

2.4 利用堆栈优化解压过程

前面已经说到,可以利用编码之间的前后逻辑关系将编码恢复为字符串。串表每一项的数据项部分存储的是前缀字符串的编码和后缀字符。这里要注意串表每一项的编码部分是对这一项中前缀字符串与后缀字符所构成的字符串的编码,后缀字符在前缀字符串的后面。同时注意到这里对编码恢复字符串时后面的字符先得到而前面的字符后得到,正好可以利用堆栈“后进先出、先进后出”的规律倒换顺序。利用堆栈之后就可以对解压过程进行优化,加快解压过程。

利用堆栈将解压过程优化后的伪代码表述如下:

3. 测试结果与效率分析

3.1 程序的测试结果

本节给出程序测试的平均结果。这些数据都是在728MHz主频,256MB内存的奔三PC机上经大量数据测试得到的平均值,且所有数据都是以国标码编码的。压缩百分比=(压缩前数据字节数–压缩后数据字节数)/压缩前数据字节数。压缩百分比P与数据压缩领域常用的压缩比R的关系是:R=1/(1-P)。压缩(解压)时间=数据的总压缩(解压)时间/块数,即压缩时间反映压缩单个内存块大小的平均时间而解压时间反映的是解压原压缩前是单个内存块大小的平均时间。

3.2 效率与结果分析

从以上表格的数据可以看出下面的几点规律。第一点,分块的大小对于压缩百分比并没有明显的影响,而增加最长编码位数对压缩百分比有显著提高。这是由LZW算法本身与程序所采用的最长编码位数决定的。编码位数一定时串表项的数量也固定了。当分块的大小达到一定程度时串表会清除重建,这样分块大小超过这个相应的大小就对压缩百分比基本没有影响。而增加最长编码位数就可以使串表项数量增加,这样就对压缩百分比有显著提高,但同时要占用更多内存资源。第二点,解压速度明显比压缩速度快。这是由于压缩过程中串表用哈希表形式组织而解压过程中是顺序表,哈希表查找速度比顺序表慢。第三点,不同类型的数据压缩百分比是不一样的。这种数据压缩的实现方式适合应用于电子词典数据。

4. 结论

从测试的结果看到,该算法针对电子词典的数据压缩百分比可以超过50%,而且数据解压过程非常迅速,每64KB只需大约7ms。程序解压过程占用的内存资源也非常少,最长编码位数为12位时只需要20KB再加上两个块的大小。这种压缩率比较高、解压速度比较快、占用内存比较少的特性决定了这种算法与实现适合应用于嵌入式的场合,特别是在嵌入式的电子词典的场合。

参考文献

[1]Welch T A.A Technique for High-performance Data Compression[J].IEEE Computer,1984,17(6):8-18.

[2]David Salomon.Data Compression:The Complete Reference[M].3rd edition.Germany:Springer,2004.

[3]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1998.4.