（信号与信息处理专业论文）基于压缩感知理论的视频帧间信号编码研究.pdf

中文摘要 随着信息技术的高速发展，人们对于信息的需求量也急剧增加。传统的时域 采样定理指出，采样频率要达到信号最高频率的二倍以上才能无失真恢复。随着 信息的增加，信号的带宽也在变宽，这就对采样设备的性能提出了更高的要求， 增大了信号处理的难度。近年新提出的压缩感知理论( c o m p r e s s e ds e n s i n g ) 是 基于信号的稀疏性，通过选择适当的观测矩阵进行非相关性测量，得到信号的少 量观测值，实现信号的压缩，利用最优化算法，可以从少量观测值中以高概率重 构出信号。 对比于m p e g - 2 的预测编码技术，本文提出了一种基于压缩感知理论的视频 帧间信号编码方案。结合传统的视频编码方案，使用运动估值与运动补偿进行预 测，获取帧间差值信号，利用帧间信号的稀疏性，分块地对帧间信号进行压缩感 知采样编码，随后进行熵编码，以实现进一步压缩。本编码方案省去了传统编码 中的变换编码过程，同时对于数据的稀疏分布问题处理方式上，不再使用游程编 码，而是直接采用稀疏变换将稀疏信号非稀疏化，节省了部分运算量。 本文利用标准测试序列进行了一系列编码试验，分析了稀疏化阈值、采样倍 率、分块大小、观测矩阵及重构算法的选择对于编码性能的影响，同时在质量近 似的情况下与m p e g 2t e s tm o d e l5 ( t m 5 ) 编码器对比了编码性能。 关键词：压缩感知，有损压缩，帧间编码，稀疏数据 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n i q u e s ，t h ed e m a n df o ri n f o r m a t i o n o fp e o p l ei si n c r e a s i n gd r a m a t i c a l l y t h et r a d i t i o n a lt e m p o r a ls a m p l i n gt h e o r e m i n d i c a t e s ，s i g n a l sc a l lb er e c o v e r e dw i t h o u td i s t o r t i o no nc o n d i t i o nt h a tt h es i g n a l sa re s a m p l e da tar a t ea tl e a s tt w i c et h eh i g h e s tf r e q u e n c yp r e s e n ti nt h es i g n a l s a st h e a m o u n to fi n f o r m a t i o ni n c r e a s e s ，s i g n a l sw i l lh a v ew i d e rb a n d w i d t h ，w h i c hr a i s e s h i g h e rd e m a n df o rs a m p l i n gd e v i c e sa n dm a k e si tm o r ed i f f i c u l tt op r o c e s ss i g n a l s i n r e c e n ty e a r s ，t a o ，c a n d 6 s ，d o n o h o ，e r eh a v ep r o p o s e dt h e c o m p r e s s e ds e n s i n g t h e o r y ( c s ) ，w h i c hm a n a g e st oc o m p r e s ss i g n a l sb a s e do nt h es p a r s i t yo fs i g n a l sb y m e a n so fi n c o h e r e n tm e a s u r e m e n tw i t hp r o p e rm e a s u r e m e n tm a t r i c e s s i g n a l sc a nb e r e c o n s t r u c t e dw i t hh i g hp r o b a b i l i t yf r o mo n l yaf e wo b s e r v a t i o n sw i t ho p t i m i z a t i o n a l g o r i t h m c o m p a r e dw i t hm p e g - 2p r e d i c t i v ec o d i n gt e c h n i q u e s ，ac o m p r e s s e ds e n s i n g - b a s e d i n t e r - f r a m ec o d i n gs c h e m ef o rd i g i t a lv i d e o si sp r o p o s e di nt h i st h e s i s c o m b i n e dw i t h t h et r a d i t i o n a lv i d e oc o d i n gs c h e m e ，m o t i o ne v a l u a t i o na n dm o t i o nc o m p e n s a t i o na r e u s e dt oa c h i e v ei n t e r - f r a m ed i f f e r e n c e s i n t e r - f r a m es i g n a l sa r es a m p l e da n dc o d e d w i t hc st h e o r yb l o c kb yb l o c kb a s e do nt h es p a r s i t y , a n de n t r o p yc o d i n ga r eu t i l i z e d f o rf t w t h e rc o m p r e s s i o n as e r i e so fv i d e oc o d i n ge x p e r i m e n t sa r ep e r f o r m e do ns t a n d a r dt e s ts e q u e n c e s t h e i n f l u e n c eo nt h e c o d i n gp e r f o r m a n c ei sa n a l y z e di nt e r m so ft h es e l e c t i o no f m e a s u r e m e n tm a t r i c e s ，r e c o n s t r u c t i o na l g o r i t h ma n d p a r a m e t e r ss u c ha ss p a r s i f i c a t i o n t h r e s h o l d , s a m p l i n gr a t i o ，s i z e o fb l o c k sa n ds o o n m e a n w h i l e ，t h ec o d i n g p e r f o r m a n c ei sc o m p a r e dw i t ht h a to fm p e g - 2t e s tm o d e l5c o d e ro nc o n d i t i o no f s i m i l a rv i d e oq u a l i t y k e yw o r d s ： c o m p r e s s e ds e n s i n g ，l o s s yc o m p r e s s i o n ，i n t e r - f r a m ec o d i n g ， s p a r s ed a t a 第一章绪论 1 1 课题研究背景 第一章绪论 随着信息社会的不断发展，人们对于信息的需求与日剧增，这就使得信息的 获取越来越重要，而基于香农奈奎斯特采样定理的要求，对信息的采样频率都 必须为信息带宽的2 倍以上，这就使得采样环节负担很重。像超带宽信号这样采 样只好采用低通滤波器滤波后再采样。为了满足奈奎斯特采样频率的要求，在传 感器网络中的采样设备昂贵而且笨重。研究表明，香农奈奎斯特采样定理是能 够使信号在采样后能够精确重建的充分条件，而非必要条件，能否突破香农一奈 奎斯特采样定理的限制，采用低于甚至远低于2 倍信号带宽的采样频率依然可以 完美的重建原信号就成为了科研人员和工程技术人员探究的问题。 令人激动的是，最近几年新兴起的一个理论压缩感知( c o m p r e s s e d s e n s i n g ) 就从数学上解决了这个问题。压缩感知理论是一个信号获取和信 号重构的框架，以原始信号在某个变换域中具有稀疏表示为前提，这个信号可以 通过一组很小的测量值进行重构。这个测量值是用一个与变换域的变换矩阵不相 关的测量矩阵来测量得到的。有趣的是，一个像噪声一样的随机矩阵就可以满足 这样的测量需求。 在日常的实际应用中，j p e g 、m p e g 等有损压缩编码标准在图像、音频、 视频等方面取得了很大成就，尤其是视频压缩。当根据人的感知特性舍弃掉一些 不影响视觉、听觉效果的数据，压缩比会大大增加。传统的图像和视频编码方式 中，在获取了场景的图像后，对图像进行离散余弦变换( d i s c r e t ec o s i n e t r a n s f o f i n d c t ) ，变换系数中有很多为零或者携带可以忽略的信息，这些系数经过量化被 舍弃。因此，在最初，对那些可以被忽略和舍弃的信息进行采样形成了采样过程 不必要的负担。这就使得压缩感知理论成为解决数字图像、数字视频高采样率和 高压缩比之间资源耗费矛盾的一个很好的备选方案。 视频帧间信号编码技术中的帧差信号表示的相邻两帧之间相对应像素间的 差值。在物体不做剧烈运动和不频繁切换场景的视频中，这个帧差信号矩阵往往 具有大量的零值，具有可压缩性和稀疏性。而帧差信号具有可压缩性和稀疏性的 特性恰好符合压缩感知理论的要求，若能将压缩感知理论引入到视频帧间信号编 码技术中，就可以利用较小的测量值表示整个帧差信号，同时还具有较强的鲁棒 性，这将能使视频编码的效率有较大地提升同时在部分数据损失或者有噪声存在 的情况下依然可以较好地完成任务。 第一章绪论 1 2 研究现状 压缩感知理论的核心思想就是对原始信号或图像进行随机投影，获得少量观 测值，利用信号或图像具有稀疏性表示的先验知识利用最优化的方法来进行信号 的重构。 目前压缩感知理论的研究虽然处于起步阶段，但已经表现出了强大的生命 力，已成为数学领域和工程应用领域的一大研究热点。许多知名大学，如美国的 麻省理工学院、斯坦福大学、莱斯大学，都成立了专门课题组对压缩感知进行研 究。2 0 0 8 年起，英特尔公司、贝尔实验室、谷歌公司等知名企业也开始组织研 究压缩感知。 压缩感知理论的三个重要要素分别为信号的系数变换、稀疏信号的非相关性 测量和稀疏信号的重构方法，其中信号的非相关性测量和重构方法成为研究的重 点和热点。 目前非相关测量主要采用线性测量。d o n o h o 在文献【l 】中指出了观测矩阵所 必须具备的三个条件，并指出大部分一致分布的随机矩阵都具备这三个条件，均 可作为观测矩阵，如：部分f o u r i e r 集、部分h a d a m a r d 集、一致分布的随机投 影集等。然而使用这些观测矩阵并不能保证百分之百地精确重构信号，只能保证 以很高的概率恢复出信号。文献【2 】从信息论的角度描述了信息论与压缩感知之 间的关系：在模拟系统中，观测噪声也是影响观测次数的重要因素，为了能够解 释这个问题，作者从信息论的角度研究了稀疏信号的率失真函数，同时指出了观 测噪声对信号重建产生的影响。 压缩感知问题的求解是一个在满足获得观测值的条件下，寻求最稀疏解r 即 最少非零值) 的过程，是个，o 非凸优化问题【3 】。但，o 问题是一个典型的n p h a r d 问题，不易求解。目前的重构算法可以大致分为以下三类： ( 1 ) 贪婪追踪算法。 该方法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号。这类算 法中最经典的匹配追踪( m a t c h i n gp u r s u i t ，m p ) 算法1 4 ，它在每一步迭代中， 从原子库中寻找与剩余分量最为接近的院子作为匹配原子。文献【5 】提出了正交 匹配追踪( o r t h o g o n a lm a t c h i n gp u r s u i t ，o m p ) 算法，它在每一步迭代中都要对 所选的全部原子进行正交化处理。 ( 2 ) 凸松弛法 这类方法通过将非凸问题转化为凸问题求解找到信号的逼近。如基追踪 ( b a s i cp u r s u i t ) 算法f 6 】，内点法【7 】，梯度投影法【8 1 和迭代阈值法【9 】o ( 3 ) 组合算法 2 第一章绪论 这类方法要求信号的采样支持通过分组测试快速重建，常见的方法有傅里叶 采样【1 0 】，链式追鼎】等。 学术界将压缩感知理论应用在图像、视频编码方面的工作也做了很多。文献 【1 2 q b 提出了一种对自然图像编码的方法，它将压缩感知理论和小波变换结合起 来，基于块进行压缩感知采样。文献 1 3 】提出了一种基于加权的压缩感知图像压 缩方法，引入的加权矩阵会对有助于在采样过程中在d c t 域获取更多信息，以 提高重建的精度。文献d 4 提出了一种视频压缩编码方式，每一帧按块进行编码， 只对满足稀疏性测试的块进行压缩感知采样编码，其余块仍然按照传统的编码方 式进行压缩编码。仿真结果表明，该方法对于视频的y 分量节省了5 0 的存储 空间，质量相对于传统编码方式却只下降了很少。 1 3 本文所做的研究工作以及章节安排 本文的研究工作基于现有的压缩感知理论，结合现有的m p e g 2 视频编码 框架，提出了一种新的视频帧间信号编码方法，将视频帧间信号编码过程分为帧 间差值信号提取、预处理、c s 测量编码、量化、熵编码五个主要部分，解码过 程也对应为熵解码、反量化、c s 重构、后处理、重构解码帧五个部分。以多种 现存的非相关测量方法和c s 重构方法为基础，使用了多个标准测试序列进行试 验，对比新方法与传统视频方法的重构质量、码率等方面的性能，分析所提出的 方法的优势与不足。 全文章节安排如下： 第一章绪论，简单地介绍压缩感知理论和视频帧间信号编码技术。 第二章压缩感知理论介绍，较为详细地介绍压缩感知理论研究的起源与现 状，与传统理论，尤其是与香农奈奎斯特采样定理，相比较的优势。同时还介 绍了压缩感知理论中信号的稀疏表示、观测矩阵设计和重构算法三个主要内容。 第三章视频帧间信号编码技术，首先回顾了m p e g 2 视频压缩编码系统和 预测编码算法，接着主要以m p e g 2 视频编码为例介绍了传统的视频帧间信号 编码技术，最后提出了基于压缩感知理论的视频帧间信号编码技术。 第四章试验测试与结果分析，利用多个标准测试序列对第三章提出的编码方 法进行有针对性的测试，根据试验数据分析新方法相对于传统方法的优势与不 t ， 足。 第五章总结与展望，一方面对本文总结，另一方面对今后的工作进行展望。 3 第二章压缩感知理论简介 第二章压缩感知理论简介 信息的获取方式与处理方法都是当今信息时代的重要课题，由于现实世界 中的各种自然现象普遍都具有模拟化特征，信息采样技术便成为了数字化的信息 世界与之相沟通的重要桥梁。传统的信息获取与处理过程可分为高速采样、变换、 压缩、传输和解压缩等几个步骤，如图2 1 所示。在采样过程中，著名的香农 奈奎斯特采样定理一直是其重要的理论基础。它指出，采样频率必须达到被采样 的模拟信号频谱中最高频率的两倍以上才能精确地恢复信号。这一定理奠定了现 在几乎所有信号获取方法的理论基础，广泛应用于日常生产生活中，例如音视频 处理设备和医疗成像器材等等。然而，随着信息技术的高速发展，人们对于信息 数量的需求急剧增加，携带信息的信号带宽也越来越宽，根据奈奎斯特采样定理 建立起来的信号处理方法就要求采样的速度和处理的速率也就越来越高，处理难 度不断增加。例如在超宽带通信和信号处理、核磁共振成像、高速数模转换器、 雷达遥感成像、传感器网络等的实际应用中，巨大数量的数据传输和存储就是一 项非常艰难的工作。 图2 - l 传统的信号获取和处理过程 另一个方面，如果在实际应用中允许一定的失真存在，为了降低存储、处 理和传输的成本，人们常常采取有损压缩的方式以较少的数据量来表示信号。在 信号的压缩过程中，通常要先对信号进行某种变换( 如傅立叶变换、离散余弦变 换或者小波变换等) 。在进行适当变换后，我们往往可以得到一个具有少量大数 值和大量小数值的系数集合，其中的小数值系数大都为零值或者很接近零值。这 意味着在其所对应域中的信号的能量往往会集中在这些少数大系数中，因此，只 要对这些少数的大系数进行编码，同时舍弃掉零值和接近于零值的系数便可以在 解码过程中高度近似地恢复原数据而不影响原信号中所包含信息的内容和效果。 这些被舍弃的大量数据对于一个信号来说是不重要的或者是冗余的，而这样的行 为就造成了大量采样资源的浪费。例如现在的数码相机都具有千万像素甚至更高 4 第二章压缩感知理论简介 的图像传感器，而经过压缩后存储起来的只有区区几百k b p s 的数据。可见采样 资源浪费巨大，同时还造成了能源的过度消耗。当然，日常生活中的消费级数码 相机并不在意这些问题，但若想应用在设置数千个传感器的传感器网络中，在几 个月的时间里这些传感器不停地同时采集数据，像这样的消耗就是巨大浪费，可 以说是代价昂贵。 从目前看来，香农奈奎斯特采样定理所提出的采样频率是采样所得信号能 够得到完全重构原信号的充分条件，而并非必要条件。于是，人们很自然的想到 能否跳出香农一奈奎斯特采样定理的束缚去建立一种新的信号采样理论，在保证 信息有效采样、处理以及传输的前提下，用远低于奈奎斯特采样定理所要求的采 样速率对信号进行采样，同时还能完全恢复原信号，也即是能否将对信号本身的 采样转换为对于信息内容的采样。如果这个问题能够解决，将极大地降低信号采 样频率以及减少在数据存储和传输中的代价，显著地提高信号处理效率，为信息 技术的发展带来革命性的发展。 最近几年来，一种新颖的理论o m p r e s s e ds e n s i n r 出现在我们的视 野中( 也有人称之为c o m p r e s s i v es a m p l i n g ) ，中文翻译为“压缩感知 或“压缩 传感”( 本文均采用“压缩感知 ) 。该理论指出，在原始信号是可压缩的或者在 某个变换域甲中是稀疏的情况下，可以用一个与变换基不相关的观测矩阵将这 个高维信号投影到一个低维的空间上。重构信号时，在信号具有稀疏性的前提下， 我们可以通过求解优化问题的方式从这些少量投影中高概率的恢复出原信号。压 缩感知理论突破了香农- 奈奎斯特采样定理的限制，采样频率不再决定于信号的 带宽，而是决定于信号的内容与结构，为信息采样和处理开辟了全新的思路。 在日常生活中我们常见的信号( 如声音和图像信号) 在时间域大部分都不 是稀疏信号，但只要经过某种适当的变换将其投影到某个变换域中，该信号就具 有了稀疏性。在压缩感知理论中，对于这些信号的采样和压缩可以同时低速率地 进行，这样就使得传感器的采样成本大大降低。信号的重构采取的是优化计算方 法，虽然计算量很大，但随着计算机性能日益提高，这已经不再是难题。压缩感 知理论的应用前景非常广阔，如在压缩成像、模拟信号转换、x 射线和生物医学 等等领域。 2 1 压缩感知的基本问题描述 设有一个实数的一维有限长离散信号咒可以看作是r 空间的一个n x l 维 的列向量，其元素为x m ，其中n - - 1 ，2 ，。 假设尺空间中的任意信号都可 以用n x l 维的正交基砂，磴。的线性组合来表示。由、玉，来表示妙，圪，作为列向量 第二章压缩感知理论简介 组成的n x n 维矩阵，则, z = 砂。y ：少】，于是任意信号x 就可以表示为： n x = b 或x = w o ( 2 1 ) t - i 其中e 是投影系数( b = ( x ，) ) ，o = h 岛钆r 为投影系数构成的 n x l 维列向量。显然，o 是x 通过甲变换后的投影到该变换域的另一种等价表 示。例如我们可以认为彳是信号在时域的表示，0 则是该信号在频域、d c t 域 或者小波域等等的表示。如果 所含元素中非零个数m 是远远小于的，则表 示该信号是稀疏的并可以进行压缩。 压缩感知理论是由数学家t a o 、c a n d 6 s 和d o n o h o 教授等人于2 0 0 4 年首先 提出的。c a n d 6 s 随后在数学上证明了只要信号在某个正交空间中是稀疏的，就 可以使用较低频率的采样信号，同时以高概率地重构该信号。在相关研究基础上， 压缩感知的理论于2 0 0 6 年正式发表。其核心思想就是对稀疏信号进行同步进行 压缩和采样，在确保获得重构原信号所需信息的前提下，用非自适应线性投影的 方式对信号进行采样，即把原信号投影到一个低维的空间获得观测值，然后根据 设计好的重构算法通过观测值重构信号。压缩感知理论的优点在于其观测值的数 据量远远小于传统采样方式所获得的数据量，突破了香农- 奈奎斯特采样定理的 束缚。压缩感知理论的整个过程如图2 2 所示。 第一步第二步 第三步 图2 2 压缩感知理论框架 设有长度为的一维信号x 在某一组正交基甲上的变换系数是稀疏的，设 该系数向量为o 。压缩感知可分为以下三个步骤进行：第一步，求出变换系数 = 甲7 x ，0 是x 在该变换域的等价或者近似的稀疏表示：第二步，设计一个 平稳的且与变换基甲不相关的m x n 维观测矩阵( 其中脉 ) ，对。进行观 第二章压缩感知理论简介 测并得到观测值y = = d 甲r x ，该过程也可以看作是信号x 通过矩阵爿岱进 行的非自适应观测：y = 彳岱x ( 其中彳a = o 、l ，7 ) ，这里的a c s 被称为c s 信息 算子【”】，该算子的每一行都可以看作是一个传感器，它与信号相乘，获得了信 号的一部分信息；最后，利用0 一范数下的最优化问题来求解x 的精确或近似逼 近x ： m i n 渺x l l 。 s t a c s x = 0 甲r x = y ( 2 2 ) 求解式2 2 所得到的向量x 便是在变换基甲上的最稀疏解，也就是我们所 需的重构信号。对于式2 2 解的方法以及与其相等价或近似等价的最优化方法是 近年来研究的热点，在后文中将做进一步地介绍。 综上所述，压缩感知理论主要包括了信号的稀疏表示、观测矩阵设计和信号 重构三个方面的内容，下面本文将就这三部分内容做进一步详细说明。 2 2 信号的稀疏表示 在一般情况下，自然界中绝大部分可压缩的信号在适当的变换域中的系数是 按一定量级呈现指数衰减的，这些系数中只有非常少的是大数值，还有很多是小 数值或者是零值，经过量化后将这些小系数舍弃掉，用剩下的大系数就可以在一 定允许误差内很好的重构原信号。通常，在常见的时域或空间域中的自然信号都 是非稀疏的，而通过某些适当的变换后得到的等价表示就是稀疏的了。具体而言， 对于一幅自然图像，其中几乎所有的像素值都是非零的，但如果将其进行离散余 弦变换( d c t ) 后，除了少数d c t 系数值较大外，其余大多数d c t 系数的绝对 值都是接近于零的，并且这些有限的大系数就包含了原始图像的绝大部分信息。 如图2 3 所示，图( a ) 中表示的是一幅大小为2 5 6 2 5 6 的灰度原始图像，其 d c t 系数如图( b ) 所示，可见大部分d c t 系数都是在零值附近，图( c ) 是由 绝对值较大的约1 5 0 0 0 个系数重构出来的图像，所需要保存的数据量只是原始图 像的2 3 左右，可以看出重构图像与原始图像差别很小，但是需要保存的信息量 大为减少。 从傅立叶变换到d c t 变换、沃尔什哈达玛变换再到小波变换以及多尺度几 何分析等等，科学家们的研究目的就是如何在不同的函数空间中使信号能够得到 更加简洁、更加直接的表示，不同的函数空间对应于信号处理中不同的域，可以 说所有这些变换都是旨在分析信号的特征并尽可能稀疏的表示它，研究如何使更 多的能量集中在尽量少的系数中。 7 第二章压缩感知理论简介 2 3 观测矩阵的设计 在压缩感知理论中，长度为的信号x 经过变换后得到了变换域的稀疏系数 向量0 = 甲7 x 后，需要设计一个观测矩阵( m x n 维，脉 ) ，其目的是要 得到m 个观测值，并保证能够利用这m 个观测值重构出原信号x 或者在变换基 甲下与x 等价的稀疏的系数向量o 。如果在观测时信号x 中的信息被破坏了， 重构就是无法实现的。整个观测过程实际上就是利用m x n 维观测矩阵m 中m 个行向量娩出对稀疏的系数向量 进行投影，即计算。和各个观测向量舫) 兰。 之i 日- j 的内积，得到m 个观测值y ，= ( o ，仍) ( f = 1 , 2 ，m ) ，记观测向量 y = ( y 1 ，y 2 ，y 肘) 7 ，即 y = 西 = 西甲r x = 彳a x( 2 5 ) 图2 4 形象地说明了式( 2 5 ) ，( a ) 图表示稀疏域选择d c t 变换域，观测 矩阵为g a u s s 矩阵，( b ) 图为( a ) 图的另一种表现形式，变换后得到的列向量。 是稀疏的，这里k = 4 ，观测值】，是非零系数谚对应的四个列向量( 图中用方框标 识出) 的线性组合。我们可以看出，观测的过程是非自适应的，也就是说与x 的变化无关的。 y w 2 。毓聋 l而。 画 m 哪巾： ( a )( b ) 图2 _ 4 压缩感知理论观测矩阵示意图 为了能够重构稀疏信号，t a o 和c a n d ：s 给出并证明了c s 信息算子彳a 必须 满足约束等距性条1 牛【1 9 】。对于任意c r i r i 和常数艿r ( o ，1 ) ，如果 ( 1 一以删；0 斧c 黔( 1 + 以删i ( 2 6 ) 成立，其中tc l ，。，z e , l r i k ，彳尸为彳口中由索引t 所指示的相关列构 成的大小为k i t i 的子矩阵，则称矩阵a c s 满足约束等距性( r e s t r i c t e di s o m e t r y p r o p e r t y ，r i p ) 。而通常来看，对于一个k 项稀疏信号x ( 其k 个非零值的位置 是未知的) ，式( 2 2 ) 可以从y 中精确地重构出x 的充分条件是c s 信息算子彳岱 对于3 k 稀疏信号c 和常数或r ( o ，1 ) 有3 k 约束等距性，即 第二章压缩感知理论简介 ( 1 一磊x 删；s0 斧c 昏( 1 + 磊x 删i v c e r 旷i( 2 - 7 ) 其中tc 1 ，) 吲3 k 。 由有限等距性质所给出的存在确定解的充分必要条件与c a n d 6 s 和t a o 等人 提出的在观测矩阵作用下稀疏信号必须保持其几何性质的要求相一致，即要使得 信号完全恢复，必须要保证两个不同的尽项稀疏信号不会被观测矩阵投影到同 一个采样的集合中去，这就是要求从观测矩阵中抽取的每m 个列向量构成的矩 阵必须是可逆的。 然而，判断一个给定的c s 信息算子彳a 是否具有r i p 性质是一个非常复杂 的问题。若一个信号在某变换域中是稀疏的，变换矩阵甲是一个确定的矩阵， 能否找到一种易于实现r i p 条件替代方法的重任就落在了观测矩阵的设计上 了。文献 1 5 】指出如果能够保证观测矩阵m 和稀疏变换矩阵甲不相关，则a c s 满 足r i p 性质的概率很大。这里的不相关是指观测矩阵m 中的某个行向量切， 不能 用渺， 稀疏表示。不相关性越强，其表示时所需系数越多；反之，若系数较少则 说明相关性较强。若观测矩阵选用高斯随机矩阵便可以高概率地保证不相关性和 满足r i p 性质的要求。例如，可以构造多个零均值，方差为1 n 的随机高斯函数 作为观测矩阵的元素妒，这样c s 信息算子彳岱就以很高的概率满足r i p 性质 了。高斯观测矩阵的特点是它几乎与任意的变换矩阵、王，都不相关，因此所需的 观测次数最小，但其缺点也很多，高斯矩阵所需的存储空间很大而且由于其非结 构化的性质导致重构过程的计算复杂度很高。另外，矩阵中每个值都服从对称 b e r n o u l l i 分布的二值随机矩阵也是观测矩阵不错的选择。有研究表明，当 k c xm l n ( n m ) ( k 为稀疏度、c 为常数) 时，原信号被准确重构的概率极 大而且重构的速度也非常理想。 能够使c s 信息算子彳a 满足r i p 条件的其它观测矩阵还有很多，如傅立叶 矩阵、一致球观测矩阵、局部傅立叶矩阵、局部哈达玛矩阵以及托普利兹矩阵 ( t o e p l i t z ) 等等【1 8 】。d o 等提出了结构化随机矩阵【2 0 1 ，该矩阵几乎与所有正交矩 阵都不相关同时又可以分解，该矩阵可以看作是局部傅立叶变换阵、随机高斯和 二值随机矩阵的混合模型，具有其各自的优点。 2 4 信号重构算法 在压缩感知理论中，信号重构算法指的是由经肘次测量的观测值】，重构出 长度为n ( 脉 ，口与x 是n xl 矩阵，甲是n x n 矩阵。当信号x 在某个基甲 上仅有取 n 个非零系数( 或远大于0 的系数) 做时，称叩是信号x 的稀疏基， 即信号x 在这组基上是稀疏的。常用的稀疏基有：正( 余) 弦基、小波基、c h i r p l e t 级以及c u r v e l c t 基等。 m p e g 2 的视频帧间信号可以近似认为在当前域上就具有稀疏性，这就为后 续使用压缩感知的方法进行视频编码提供了可能。但是，视频帧间信号的稀疏性 也是受一些条件所影响的，如视频内容的变化剧烈程度、运动估值与运动补偿算 法等。当视频内容变化比较快时，即使使用了运动估值与运动补偿算法进行预测， 编码帧与预测帧仍然有较大差异，这就使帧间信号的零值减少，稀疏性降低；当 视频内容变化缓慢时，预测帧就会与编码帧很接近。帧间信号的稀疏性就会很高。 不同的运动估值算法在进行预测时，搜索的范围、搜索的精度、匹配的准则都会 1 9 第三章视频帧问信号编码技术 有所差异，因而带有运动补偿的预测帧也各有差异，帧间信号的稀疏性会有不同。 3 3 2 传统编码方式 m p e g 2 视频压缩编码中对于p 帧和b 帧使用帧间预测编码方式，它们的差 别是在运动估值时使用的参考帧选取不同。p 帧使用前向预测，b 帧使用双向预 测。在形成预测帧后，计算当前编码帧与预测帧的帧差，得到的帧间差值信号。 传统的帧间差值信号编码要经过：离散余弦变换( d i s c r e t ec o s i n et r a n s f o r m ， d c t ) 、量化、变字长编码三个典型步骤。解码则相应地经过：反离散余弦变换 ( i n v e r td i s c r e t ec o s m et r a n s f o r m ，i d c t ) 、反量化、变字长解码三个步骤。 首先，类似于i 帧的帧内编码方式，将帧间差值信号的亮度( y ) 残差图像 和两个色差( u 和v ) 残差图像划分成许多8 8 个像素的块( b l o c k ) 。每4 个2 2 排列的亮度残差块和空间上相对应的色差残差块组合成一个宏块( m a c r o b l o c k ，m b ) ，如4 ：2 ：0 的色度格式，一个宏块由4 个亮度残差块和2 个色度残差 块组成。对每一个块进行二维d c t ，以消除空域相关性。 设由8 8 像素组成的像块用矩阵x 表示，其正交变换后的8 x 8 系数块用 矩阵l ，表示，则二维d c t 和d c t 公式如下： y = c x c t x = c t y c( 3 - 4 ) 其中c 表示8 8 的d c t 矩阵，c 1 。是其转置矩阵。 8 8 的d c t 矩阵c 的第f 行，第，列元素按下式定义： q = 扛0 ，o 7 8 ( 3 5 ) i 1c 。s i ( 2 f j + 1 ) 7 rl s f 7 ，0 j 7 21 6 残差块经变换成为由8 8 个d c t 系数组成的系数块，位于系数块左上角的 第一个系数称为d c ( d i r e c tc u r r e n t ) 系数，其余6 3 个系数称为a c ( a l t e r n a t i v e c u r r e n t ) 系数。 接着，使用m p e g 2 标准中规定的或自定义的量化加权矩阵形进行量化。 m p e g 2 标准中规定用于4 ：2 ：0 格式的p 帧、b 帧亮度和色度帧间差值信号的量 化加权矩阵为所有元素都为1 6 的8 8 的系数矩阵。系数的量化除了决定于量化 加权矩阵外，还决定于量化尺度因子r ，引入量化尺度因子的作用是可以根据 图像内容变化和编码的码率控制策略灵活调整量化间隔，使码率维持在恒定水 平。量化时，按照如下公式进行( 式中忽略了一些次要因素) ： 2 0 第三章视频帧问信号编码技术 ，1 ，、 4 f ；r o u n d i 卫l 。 l 嘞 q # = r o u n d ( 赤) 6 ， 其中，肋为第f 行，第列的d c t 系数，w 为量化矩阵形第f 行，第列的量 化权重值。 解码端对q 进行反量化恢复d c t 系数按照量化的逆过程即可实现，如式 ( 3 - 7 ) 所示。 吒= q ：f 嘞f j l 6 ( 3 - 7 ) 量化后的d c t 系数矩阵变得稀疏，大部分位于系数矩阵右下角的表示高频 分量的系数被量化为零，实现了较高压缩比的数据压缩。当然，这部分的编码方 式是有损压缩，在解码端是无法恢复的，所引入的误差仅为量化误差。 接下来进行游程编码。通过z 型扫描或交替扫描方式，将量化的二维d c t 系数矩阵变换为一维序列，序列的每一个元素都是二元数组( r u n ，l e v e l ) ，其中 砌表示连零的长度，l e v e l 表示连零的系数后出现的首个非零值。当剩下的所有 系数都为零时，用符号e o b ( e n do f b l o c k ) 来表示。通过对游程长度进行游程 编码来替代逐个传输零值进一步实现了的数据压缩。 最后，对游程编码后的d c t 系数进行变字长编码，m p e g 2 中使用了霍夫 曼编码方式，对出现概率大的符号使用短码编码，出现概率小的符号使用长码编 码，从而从统计上获得较短的平均码长。为了实时进行霍夫曼编码及解码，通常 按( r u n ，l e v e l ) 组合成的符号及其概率与霍夫曼码字的对应关系预先定义好码表， 只需以符号为地址通过查表方式就可以完成霍夫曼编码与解码。游程编码和霍夫 曼编码均为无损压缩，从统计上对数据进行了进一步压缩。 总的来说，传统的帧间差值信号编码方式就是以d c t 变换和量化的有损压 缩与变字长编码的无损压缩相结合，实现了较高压缩比的视频压缩编码。 3 3 3 基于压缩感知的帧间信号编码过程 本节结合传统的视频帧间差值信号压缩编码框架，根据帧间差值信号的近似 稀疏性，基于压缩感知理论，提出了一种新的视频帧问信号编码方式。 压缩感知的方法自产生以来因其低采样率、高效率、高压缩比等优点备受瞩 目，而且应用领域广泛。使用压缩感知的方法对信号进行测量编码的前提就是信 号具有稀疏性。m p e g 2 编码过程中的视频帧间信号正具有这样的稀疏性或近似 稀疏性，因此结合压缩感知理论对视频帧间信号进行测量编码是可行的，也是压 第一章视频帧问信号编码技术 缩感知理论很有价值的一种应用。 本文提出的基于压缩感知的视频帧间信号编解码系统的结构如图3 3 所示。 图3 3 基于压缩感知的视频帧间信号编解码框图 该视频帧间信号编码过程分为帧间差值信号提取、预处理、c s 测量编码、 量化、熵编码五个主要部分，解码过程也对应为熵解码、反量化、c s 重构、后 处理、重构解码帧五个部分。 编码过程具体如下： 1 、帧间差值信号提获取 。 对于视频帧间差值信号的获取仍借助于m p e g 2 的预测编码算法，以1 6 1 6 像素的宏块为单位，进行运动估值和运动补偿形成预测帧。其中，如果某宏 块进行运动补偿后，预测误差大于一定门限值，则放弃预测，对该宏块使用帧内 模式进行编码，预测帧对应宏块清空( 如在t m 5 中，统一置为1 2 8 ) 。如果某宏 块不进行运动补偿，直接使用空间位置对应的宏块作为预测，预测误差小于一定 门限值，则不进行补偿，且对预测误差跳过不编码，即预测误差全部置零，以提 高编码效率。 本编码方法仅针对于m p e g 2 编码过程中的p 帧进行编码，通过计算编码 帧与带有运动补偿的预测帧的帧差，完成帧间差值信号的提取。 2 、预处理 预处理过程如图3 - 4 所示，主要包括信号稀疏化、分块、维度转换和三部分。 ( 1 ) 信号稀疏化：虽然第一步提取的视频帧间差值信号含有一定数量的零 值，有的可以近似认为信号具有稀疏性，但是由于宏块编码模式选择的不同、视 频内容变化剧烈程度的不同、不同编码系统使用运动估值与运动补偿算法不同， 会导致帧间差值信号的稀疏程度差异很大，有时甚至不够稀疏，直接影响c s 重 构质量。因此在这步需要对信号进一步稀疏化，对于小于稀疏化阈值r 的帧差值 统一置零。尽管如此，这样处理引起的失真比起传统帧间信号编码中的有损压缩 引起的失真也要小得多，同时这样处理有助于c s 测量编码方法发挥作用。 第三章视频帧问信号编码技术 ( 2 ) 分块：本方法使用c s 测量编码进行视频帧间信号编码是分多块进行 的，而不是整帧帧差信号一次完成c s 测量编码，这与传统编码方式中分块进行 d c t 变换是类似的。将一帧帧差图像划分成多个m m 的块，逐个处理，其中 m 取图像宽和高的一个公约数。如一幅3 5 2 2 8 8 的图像可以取m = - 1 6 或3 2 。 ( 3 ) 维度转换g 经过提取和分块后得到的帧差信号是二维信号，本编码系 统在c s 测量编码过程中使用的是一维的测量方法，所以需要将已分块的图像信 号，每一块都按列扫描成一维信号，以备c s 测量编码环节使用。 帧间差值信号吨至三三三至 l 叫 二至三二 叫( 三至乎一维稀疏信号 图3 _ 4 预处理流程 3 、c s 测量编码 c s 测量编码通过测量矩阵西与转化为一维信号的帧间信号相乘，获得观测 值，即完成信号从高维度空间向低维度空间的映射。按照预处理环节划分的块， 逐块进行测量编码，完成整帧帧间信号的压缩编码。 c s 测量编码虽然步骤简单，运算也并不复杂，只包含乘法和加法，但却是 本编码方案比较关键的一步，通过这一步完成了帧间差值信号的压缩。观测矩阵 的选取直接影响了压缩编码的重构质量，通常可以随机高斯观测矩阵、f o u r i e r 观测矩阵和随机伯努利观测矩阵等。 4 、量化 帧间信号通过随机观测矩阵测量得到的观测值通常是小数，保留过多小数位 会使运算量增加，而且没有很大的意义，同时给后续的熵编码过程增加了很大困 难，因此需要进行量化。但是，本编码方案的量化不同于传统压缩编码中的量化， 传统压缩编码中的量化是通过舍弃一些人眼不敏感的高频分量系数来进一步进 行压缩，它也是传统编码中有损压缩的主要部分。而本方案的量化通过对观测值 扩大一定的倍数并取整来改变它的表示方式，同时在精度上不引起太大损失，进 而进行熵编码，来实现进一步数据压缩。 5 、熵编码 熵编码仍然采用霍夫曼编码。这种熵编码是无损压缩编码方式，可以从统计 上对数据进行进一步压缩，同时不会因为失真问题而影响c s 重构。 本视频帧间信号编码方案的解码过程其实是编码的逆过程，其具体过程如 下： 1 、熵解码 第三章视频帧问信号编码技术 进行霍夫曼解码， 2 、反量化 与量化过程相反， 3 、c s 重构 解出经过量化的c s 测量编码观测值。 获得有较小量化误差的c s 测量编码观测值。 c s 重构是本方案解码过程中最为重要的一步，也是计算量最大的一步。如 本文第二章所述，c s 的重构过程实际是求解一定条件下的最优化问题的过程。 常用的算法有l 1 范数最小化方法、最小全变分法等。 4 、后处理 后处理过程如图3 5 所示，包括取整、维度转换两个部分。 。( 1 ) 取整：由上一步c s 重构算法，基本恢复出视频帧间差值信号。尽管 与原始帧差信号相差不多，但是数值都是小数，无法用于图像显示。因此，对重 构出的数值进行四舍五入，得到可以用于图像显示的整数帧差值。 ( 2 ) 维度转换：与预处理中维度转换相对应，将一维信号重新扫描成二维 图像差值信号，以用于整帧的重构。 j t t 唯q - 二j 亘三二) 至三乎二维帧差信号 图3 5 后处理流程 5 、解码帧重构 将解得的视频帧间信号与预测帧相加，得到重构帧图像，至此本方案视频解 码完成。 该视频帧间信号编码方案基于压缩感知理论，但又结合了传统的视频编码方 式，现从理论上将本编码方案与传统的帧间编码方案进行简单的比较： 相同点： ( 1 ) 预测方式相同 本编码方案和传统编码方案都使用了运动估值与运动补偿进行预测，获取帧 间差值信号，对预测误差进行编码。 ( 2 ) 熵编码方式相同 本编码方案和传统编码方案都使用了霍夫曼编码来达到去除统计信息冗余， 实现压缩的目的。 不同点： ( 1 ) 变换编码是否选取方面不同。 传统编码方案是通过在变换域舍弃视觉上的冗余信息达到压缩的目的。本编 第三章视频帧问信号编码技术 码方案省去了基于d c t 的变换编码过程，直接进行c s 采样编码，节省了变换 过程计算量； ( 2 ) 数据的稀疏分布