一种通用的视频编码的镜头级压缩算法研究

1、华中科技大学硕士学位论文一种通用的视频编码的镜头级压缩算法研究姓名：吴平凡申请学位级别：硕士专业：软件工程指导教师：张科峰20080520摘 要随着信息技术的飞速发展，人们对多媒体信息业务的需求与日俱增。尽管人们在努力增加通道带宽和提高信道传输速率，但多媒体数据压缩技术仍受到人们广泛的关注，进行高压缩率的视频编码的研究已成为当前数字信号处理领域的热点问题之一。现有的视频压缩主要是基于帧的压缩，即帧内压缩和相邻帧间的压缩，通过帧内的压缩和相邻帧间压缩确实可以大大的压缩视频的数据，但是其也忽视了不相邻帧间的压缩情况。随着视频压缩的发展，不相邻帧间的冗余的压缩显得十分必要。本文主要研究视频不相邻帧间

2、的冗余，即视频镜头级冗余。对有镜头冗余的视频进行压缩，以提高视频文件的压缩率。通过理论分析，验证了镜头压缩算法的可行性和有效性。本文是基于已知镜头的边界的压缩，提出通过检测镜头内部的关键帧的方法以比较两个镜头是否冗余，从而进行镜头压缩。由于视频镜头级的冗余常是场景的冗余，因此本文通过字典压缩的方法来减小压缩算法的时间复杂度。本文通过DirectShow设计filters对存在镜头冗余的视频数据进行压缩，试验结果表明在支持DirectShow编译码的视频编码格式文件中，存在镜头冗余的视频，能够取得较好的压缩效果，测试视频的压缩比可达1.06: 1。关键词：视频编码，视频压缩算法，视频存储，镜头压

3、缩IAbstractWith the rapid development of information technology, multimedia information business people on the ever-increasing demands. Although people in their efforts to increase access bandwidth and improve access speeds， but the multimedia data compression technology is still widespread concern H

4、igh compression ratio of the video coding has become the current field of digital signal processing one of the hot issues.The existing video compression is mainly based on the frame of compression, that is, intra-frame compression and the adjacent compression, Through intra-frame compression and adj

5、acent indeed can greatly compressed video data compression, but it ignore the situation in no neighboring frame compression. With the development of video compression, the compression of the redundancy of the no-adjacent frame is very necessary.This paper studies the redundancy of not adjacent frame

6、 in video, video shot redundant.A repetition of the shot compressed to enhance the video compression ratio. Through theoretical analysis, verify the feasibility and effectiveness of the shot compression algorithm. This article is based on known video-compression of the border， made by detecting the

7、key Frame of shot to compare the two shotes are redundant, so the shot of the video can be compressed. As video shot at scene of redundancy is often redundant and therefore this paper， sliding window approach to reduce the compression algorithm of the time complexity.By design DirectShow filters on

8、the shot there redundant video data compression. By design DirectShow filters on the shot there redundant video data compression.The results show that support DirectShow codecs in the video encoding format， the existence of the video shot redundancy,to achieve good compression effect. The compressio

9、n ratio of the test video is up to 1.06: 1Keywords: Video coding Video compression algorithm Video storeShot compressionII独 创 性 声 明本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知，除文中已标明引用的内容外，本论文不包含任何其他人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：年 月 日学位论文版权使用授权书本学位论文作者完

10、全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保 密，在_年解密后适用本授权书。本论文属于不保密。（请在以上方框内打“”）学位论文作者签名： 指导教师签名：年 月 日 年 月 日1 绪 论本章首先简要介绍课题的背景及研究意义，然后阐述国内外视频压缩研究的主要编码的标准和算法及存在问题，提出本文的压缩算法，最后介绍本文的组织结构。1.1 课题背景及研究意义随着信息技术的飞速发展，人们对多

11、媒体信息业务的需求与日俱增。尽管人们在努力增加通道带宽和提高信道传输速率，但多媒体数据压缩技术仍受到人们广泛的关注，进行高压缩率的视频编码的研究已成为当前数字信号处理领域的热点问题之一。视频信息传输存储所需要的巨大带宽和内存必须依赖于视频压缩技术的使用。因此多媒体信息大多以压缩的格式存储。研究视频图像数据可以发现其中存在大量的冗余。减少图像的冗余度就可以极大地减少图像的数据量。视频图像数据的冗余主要是以下几个方面：1.空间冗余度：同一景物表面上各数字采样点的颜色间往往存在着空间连贯性。因此通过改变物体表面颜色的象素存储方式来利用空间连贯性，达到减少数据量的目的。2.时间冗余度：序列图像为位于时

12、间轴区间内的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体。只不过移动物体所在的空间位置略有不同，所以前后帧的数据存在极大的相关性。除此以外，还存在着信息熵冗余、视觉冗余、结构冗余、知识冗余、纹理统计冗余等1。在存储视频信息方面，存在大量的完全相同的信息的重复性存储，浪费了大量的存储空间。例如对电视的播放的信息的处理，其中就有很多重复的广告片段，而存储相关的信息就会增加存储的容量，对相关的重复信息的压缩将能给存储带来很大的便利。特别是在现在的网络时代，网络视频的存储，索引及视频搜索成为新的研究热点，而网络多媒体文件存在大量的大段完全相同的重复冗余，如何使用更少的空间存储不必要的信息，成

13、为急需解决的问题。本文提出的压缩能较便利的压缩存在重复性镜头的视频，为视频的存储及传输节省大量的空间。11.2 视频编码技术1.2.1 视频编码标准视频编码领域的标准化工作从1990年开始，国际电联（International Telegraph Union, ITU）H.261标准朝着高压缩率方向发展，数字视频电话信号以n64 kb/s（n=1，2，330）的数据率在综合业务数字网（Integrated Service Digital Network, ISDN）信道上传输。自从那时以后，国际电联和动态图像专家组（Moving Pictures Experts Group, MPEG）发布了

14、一系列国际视频编码标准，目标是能应用于多个领域。ITU-T为了可以在低比特率下传输可视电话的信号，于1995年发布了H.263标准和在2002年发布了H.264标准（如同ISO-MPEG和ITU发展的一个交点）。H.264提供了更广阔的比特率，而且在应用上提供更好的压缩效率和附加功能，本质上包括所有H.263的应用领域，图1-1显示了视频压缩标准的演变过程。图 1-1视频压缩标准的演变过程ISO-MPEG在1993年发布了MPEG-1标准，而且一起又发布了MPEG-2标准现在应用最广泛的视频压缩标准。即使MPEG-1最初发展是应用于在CD上存储压缩视频，MPEG-1也广泛地应用于英特网上的视频

15、传送。MPEG-2是为数字电视信号在大约4-6 Mb/s传输下而开发的，而且已经被指示用于全球范围内的数字电视中。MPEG-4是为在甚低比特率下的视频压缩和提供基于对象的额外功能而开发的。MPEG-4已经成为英特网流、无线视频、消费型数码摄像机、移动电话和掌上计算机上最广泛使用的标 2准。所有的上述标准都是建立在基于块的运动补偿离散余弦变换（Discrete Cosine Transform, DCT）方法之上。然而，在过去十年间，基本方法的各种细节被提炼出来，导致了更复杂、也更有效率的压缩标准。表现在基于先进的运动向量精度和更复杂的运动模式而产生的更高压缩比。ITU-H.264是目前在压缩效

16、率方面最先进的标准。在H.264（MPEG-4/AVC）标准中，在沿用基于内容算术编码上采用可变尺寸宏模块的更高精度运动补偿预测2。另外一个新颖之处是在H.264中引用长期帧内存，它可以存储在过去的时间预测的多帧图像，但是也增加了复杂性。在编码器和译码器中大部分的先进技术都会越来越复杂这个趋势了。然而，过去十年也已经见证了处理器的速度上的改进和VLSI设计的算法在实时运行上的进步。将来的编码策略将满足减少复杂性限制。1.2.2 视频编码压缩算法为了解决视频获取后的存储问题，现在有很多的编码方法来去除视频中存在的冗余。按失真分包括有损编码和无损编码，当今流行的编码基本上是有损编码，包括帧内压缩编

17、码和帧间压缩编码。图1-2大致对视频压缩算法进行了分类，下面的几种为常用的编码算法：图1-2 视频压缩算法大致分类常用视频编码：1. 视频帧内编码（1）熵编码：旨在去除信源的统计冗余信息，霍夫曼编码是最常见的熵编码方法。常用的熵编码还有算术编码，仙农码和游程编码等。所有这些编码方式都不引起 3信息的损失，因而称为无损编码。（2）变换编码：也是一种降低信源空间冗余度的压缩方法。各种正交变换（例如，K-L变换，余弦变换，沃什变换等）都能在不同程度上减少随机向量的相关性。由于变换所产生的变换系数之间的相关性很小，可以分别独立地对其进行处理；而且信号经大多数正交变换后，能量都集中在少数系数上，从而实现

18、数据压缩。2. 视频帧间编码（1）预测编码 ：旨在去除相邻像素之间的冗余度，差分脉码调制（Differential pulse code modulation, DPCM）是它的一种基本方法。（2）具有运动补偿的帧间预测编码，包括序列图像的运动估值和帧间预测编码。比较成熟的估值方法主要分为两大类：块匹配方法和像素递归法。两类方法都只估计物体的平移，其中块匹配方法应用比较广泛。帧间预测与消除空间冗余的预测编码相类似，即不直接传送当前帧（k帧）的像素值x，而是传送x与前一帧的对应像素x之间的差值。（3）其它压缩编码方式 ：如子带滤波/小波变换，向量量化，分形编码及基于模型的编码等3。最新的MPEG

19、-4 AVC/H.264和Windows Media视频编码器都采用了运动估计和补偿模块用来消除相邻图像间的冗余信息，熵编码模块用来消除编码信号的冗余性，变换量化模块根据人的视觉系统对视频信号的细微变化的不敏感性丢失部分信息，从而提高压缩比。以上的各种编码技术都是在帧内的压缩及相邻的连续的帧间压缩，通过相应的变换，如DCT变换或小波变换，实现小尺度上的单帧和相邻帧压缩，而忽视了更大尺度上的不连续的帧间压缩，而随着科技的发展，不连续帧间的压缩即段间压缩技术显得至关重要。本课题研究的视频的镜头级压缩为处理视频的时间冗余度。是一种无损编码，通过对已知镜头的边界视频的压缩，把冗余的段进行裁剪和压缩，跳

20、出传统的帧内的压缩及相邻的连续的帧间压缩，实现大尺度的帧间压缩，从而提高视频的压缩率。此算法不是对视频文件进行微尺度的帧间压缩，而是宏观的尺度上对视频的分段进行压 4缩。通过压缩可以节省存在大量镜头重复的视频的存储空间。1.2.3 常见视频格式为了便于介绍对于视频文件的通用压缩算法，先需了解相关流行的视频文件格式，本算法的通用性是指的对于各视频文件的文件格式的通用性。1）AVI（Audio Video Interleaved）格式AVI的名字叫做音频视频交错格式。它是由Microsoft公司开发的一种数字音频与视频文件格式，原先仅仅用于微软的窗口视频操作环境（Microsoft Video f

21、or Windows, VFW），现在已被大多数操作系统直接支持。AVI格式允许视频和音频交错在一起同步播放，但AVI文件没有限定压缩标准，由此就造成不同的AVI格式之间往往互不兼容。不同压缩标准生成的AVI文件，就必须使用相应的解压缩算法才能将之播放出来。常用的AVI播放驱动程序，主要有Microsoft Video for Windows或Windows 95/98中的Video，以及Intel公司的Indeo Video等等4。 由于AVI只提供了视频音频流的存储模式，在压制AVI文件时，可以根据自己选定的压缩编码模式进行压缩。在后面的测试文件中，本文采用了AVI的格式进行解压缩和编码，

22、其中编码是按DirectShow中的已有的编码Filters来设置的。2）MOV格式QuickTime格式大家可能不怎么熟悉，因为它是Apple公司开发的一种音频、视频文件格式。QuickTime用于保存音频和视频信息，现在它被包括Apple Mac OS、Microsoft Windows 95/98/NT在内的所有主流计算机平台支持。QuickTime文件格式支持25位彩色，支持领先的集成压缩技术，提供150多种视频效果，并配有提供了200多种MIDI兼容音响和设备的声音装置5。新版的QuickTime的MOV也可以作为一种流文件格式，包含了基于Internet应用的关键特性。3）MPEG

23、/MPG/DAT格式MPEG是由国际标准化组织ISO（International Standards Organization）与IEC（International Electronic Committee）于1988年联合成立，专门致力于运动图像（MPEG视频）及其伴音编码（MPEG音频）标准化工作。MPEG是运动图像压缩算法的国际标准，现已被几乎所有的计算机平台共同支持。和前面某些视频格式不同的是，MPEG 5是在保证影像质量的基础上采用有损压缩方法减少运动图像中的冗余信息从而达到高压缩比的目的。MPEG压缩标准是针对运动图像而设计的，其基本方法是：在单位时间内采集并保存第一帧信息，然后只

24、存储其余帧相对第一帧发生变化的部分，从而达到压缩的目的。MPEG的压缩比最高可达200: 1，压缩效率之高由此可见一斑。Video CD （VCD）、Super VCD （SVCD）、DVD （Digital Versatile Disk）就是全面采用MPEG技术而产生出来的6。在后面的测试中，本文也使用了MPEG-1/2的文件进行测试，为了使程序简便起见，在对mpeg文件解压后，在编码阶段对其进行了AVI封装。由于MPEG-4有专利权的问题，对MPEG-4的测试拟采用XviD4.0，XviD5.0，但是DirectShow不支持XviD4.0，XviD5.0的译码，需要另设计Filters对

25、其进行译码。4）RM（Real Media）格式RM格式是RealNetworks公司开发的一种新型流式视频文件格式。RealAudio用来传输音频资料，RealVideo用来传输连续视频数，RealMedia可以根据网络数据传输速率的不同制定了不同的压缩比率，从而实现在低速率的广域网上进行影像数据的实时传送和实时播放。RealVideo除了可以以普通的视频文件形式播放之外，还可以与RealServer服务器相配合，由RealServer负责广播RealMedia视频文件，在数据传输过程中可以边下载边由RealPlayer播放视频影像，而不必像大多数视频文件那样，必须先下载然后才能播放。5）A

26、SF（Advanced Streaming Format）格式Microsoft公司推出的高级流格式ASF，也是一个在Internet上实时传播多媒体的技术标准。ASF的主要部件是NetShow服务器和NetShow播放器。有独立的编码器将媒体信息编译成ASF流，然后发送到NetShow服务器，再由NetShow服务器将ASF流发送给网络上的所有NetShow播放器，从而实现单路广播或多路广播7。1.3 论文结构和主要内容第一章是绪论，目的在于介绍视频压缩的意义。首先对视频信息的存储的发展和特点进行了简介，阐述了视频编码相关压缩的重要性，接着简要介绍了视频编码标准和视频编码算法相关技术的国内外

27、研究动态，提出其存在的问题及本设计的指导思 6想，最后介绍本文的组织结构。第二章依现有的视频压缩算法存在的问题，介绍本镜头压缩算法的思想及框架，在压缩中需要解决的问题。基于视频文件的实现流程，压缩文件的编码及解码流程及镜头压缩算法的可行性和有效性。第三章介绍了镜头的边界检测方法，获取镜头冗余的方法。提出采用比较镜头内的关键帧的方法来简化对镜头的检测，避免对镜头进行一帧一帧的比较，降低了检测的效率，最后通过提供的关键帧检测工具验证了用关键帧代替镜头检测的合理性。同时采用字典压缩来减少视频搜索的复杂度问题。第四章是采用DirectShow软件在VC+6.0的基础上设计Filters以实现对视频文件

28、的压缩编码及解码播放，最后给出再此基础上的镜头压缩算法的在像素域和在压缩域同标准算法（MPEG-2）对比的实验结果。第五章是结论，对全文进行总结。72 视频编码的镜头压缩的压缩算法现有的图像压缩算法中无论是基于单一帧图像的熵编码，变换编码，还是基于帧间压缩的预测编码都是以帧为基本的压缩编码单元，研究图像帧的特点，如图像内部像素特征的连续性或统计特性，帧间的连续性等来找出视频帧内或帧间存在的冗余，进行编码，从而对整个视频进行压缩。基于帧的编码，很好的解决了对原始图像（像素域）的压缩，但随着视频技术的发展，在存储和网络传输过程中，视频段（压缩域内）的冗余越来越多，而以帧为编码单元的视频压缩技术无法

29、很好的解决此类的压缩问题，因此本文提出基于镜头的压缩算法以便能更好的解决这方面的冗余问题。2.1 镜头压缩算法框架2.1.1 采用基于镜头的压缩算法需要解决的问题1.镜头压缩算法的通用性问题：对于现有的视频文件格式多种多样，需要考虑对像素域内的视频数据和压缩域内的视频数据的压缩。2.由于对流行的avi，asf，mpg，rm等格式，视频数据是以数据流的形式来存储的，而要想对数据流中的镜头帧进行操作，必须得把视频镜头都封装成各自的小的包，然后再定义一种大的包格式对它们进行打包，这要就会产生如果压缩的量不够，视频文件比原始的视频文件较大的问题。（下一节作介绍）3.由于是基于镜头的压缩，因此必须知道镜

30、头的边界，以便确定镜头的大小及属性，但是现在视频边界检测还在进一步研究中，因此测试是需要标准的视频（大家公认的视频）来做测试。在压缩中同样要解决镜头冗余的判别问题，即什么样的镜头才算视频中存在镜头冗余，怎么样才能更好，更快，更准的判断镜头冗余。（第三章作介绍）4.一般视频格式avi，asf等对数据流的顺序操作是基于帧的，即采用frame_count+的方式来实现数据流的播放和呈现。而此算法如果还是基于此，那么将无法播放压缩掉的镜头帧，因此需要对索引进行操作和设计，即index_count+。（第四章做介绍）5.由于AVI格式带有索引项，可以对视频数据进行索引，原拟采用AVI格式进行压 8缩测试

31、，但是发现avi格式的index项是回放功能定位信息，顺序播放时，是按数据流顺序播放，不依赖index的信息。因此无法在avi文件格式下进行压缩。2.1.2 镜头压缩算法的思想随着视频技术的飞速发展，视频存储和网络传输中出现了很多整段整段的重复的视频，如电视插播的广告，体育赛事的回放等，以一段4秒钟100帧的640480的24位图像重复的视频镜头为例，设其视频压缩的压缩比为30: 1，其存在的冗余也有100 640480/3=2930 KB。因此如何减少这方面的视频存储空间，减小传送视频所需要的带宽是现在急需解决的问题，也是有意义的问题。含镜头冗余的原视频段其他视频段第k,删除图2-1 镜头压

32、缩算法的原理图2-1表示存在冗余镜头的视频压缩原理：含镜头重复的原视频段中存在第K段个第N段视频是相同的（第K段视频中不一定只包含了一个镜头，很多情况下包含的不只一个镜头），然而在存储和传输时，这2段却要做重复的处理。压缩后将每段视频添加索引项后，第N段的内容即可以用带有索引项和位置偏移项的包头来代替。当读到第N段视频时，读包头后，依索引的偏移量读第K段视频的内容，因此节省了重复存储第N段视频的空间，实现了对视频的压缩。图2-2描述了视频镜头级压缩的基本压缩流程。9图2-2 镜头压缩算法的压缩流程示意图2.2 视频镜头压缩算法的验证及编解码流程2.2.1 关于场景的压缩由于镜头一般不是孤立的，

33、多个镜头组成了场景，对镜头的压缩更多的是对场景的压缩。采用冒泡法对视频进行比较和压缩显然无法满足大数据量的压缩，由算法思想可以知道，采用无损压缩算法即可以更好的解决收索与压缩效率问题。现有的无损压缩算法包括了统计方法和字典方法。现有的统计方法包括霍夫曼编码，算术编码，游程编码，香农-费诺编码等。字典方法包括了LZ77，LZ78，LZW系列及相关改进算法810。由第一章的介绍知道，以上的编码方式都为熵编码，现比较其中的主要几种编码算法。1. 霍夫曼（Huffman）编码：霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码

34、的长度较短；而对于出现频率低10的信息，编码长度较长。这样处理全部信息的总码长一定小于实际信息的符号长度11。由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。其编码长度不统一，硬件实现也有难度。对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100的编码效率；若信号源符号的概率相等，则编码效率最低。2. 算术编码算术编码没有延用编码技术中用一个特定的代码代替一个输入符号啊的一般做法，它把要压缩处理的整段数据映像到一段实数半开区间0，1)内的某一区段，构造初小于1且大于或等于0的数值。这个数值是输入数据流的唯一可译代码。用算术编码算法需要对源文件进行两

35、遍扫描处理。第一次扫描统计出各字符出现的次数，然后第二次调整统计数字的范围和数量级，使之适应算术编码方法。3. 游程编码游程编码又称“运行长度编码”或“行程编码”，是一种统计编码，对于二值图有效。行程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”。行程编码因此而得名），使符号长度少于原始数据的长度。行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。4. LZ77及LZ78编码LZ77的主要思想是把已输入数据流的一部分作为字典。编码器为输入流开一个窗口，并随着字符的编码而把窗口中数

36、据从已压缩数据到待压缩数据，这种方法是基于一个滑动窗口的。LZ78是采用一个保存先前所遇到的字符串的字典。这个字典开始为空(或几乎是空的)，其大小仅受限制于可用的存储空间。编码器输出双字段的标识，第一个字段是指向字典的指针，第二个字段是字符的编码12。字典中什么也不删除，相对于LZ77这既是一个优点（因为将要输入的字符串都可被早已出现的字符串压缩），也是一个不利条件（由于字典趋于快速膨胀，全部可用空间将很快被填满）。5. LZW编码11LZW是LZ78的一个流行的变形，其标识只包含一个指向字典的指针。LZW编码先把字母表中的所有字符初始化到字典中，编码器逐个输入字符并累积字符串。每输入一个字符

37、就被串接在后面，然后在字典中查找，只要在字典中查找到，该过程就继续进行。分析了以上各算法的利弊之处，基于算法的要求，采用字典方法处理场景的冗余较为合适。在字典算法中无论的LZ77，LZ78，还是LZW，都是基于字符串的压缩，而图像是基于帧的，要使能够移植字典压缩的思想，需要在封装中采用对镜头的进行序列编码，字符化，再进行字典压缩。字典压缩算法对压缩的效率没有很大的提高，但是能减少视频段的搜索复杂度。2.2.2 镜头压缩算法的实现镜头压缩算法是基于存在重复镜头的，以一般的多媒体文件为源文件进行压缩，最终比较的为多媒体源文件提取出来的视频文件和压缩后的视频文件。图3-3为视频镜头压缩的算法实现流程

38、:1. 读取源文件：读取多媒体的源文件可以是经编码后再以avi，asf，mkv等文件格式封装的形式；也可以是直接的编码后文件，如mpg等文件格式；也可以是未经编码的原始视频文件，如3gp等文件格式。2. 音视频分割：读取多媒体的源文件可能不仅包含了视频文件，也包含了音频文件。对于视频的压缩，需要分离出音频部分和视频部分，以便于对视频数据的压缩。由于音频，视频采用的压缩方法不一致，在处理镜头压缩的时候先不考虑对音频的数据压缩。3. 视频解码：视频的解码，确定文件的各帧，镜头包含的帧4. 镜头段编码封装，添加序列号：把经视频边界检测得到的视频镜头内的图像帧封装在一起编码，添加镜头序列号，以0，1，

39、2 形式标明是该段镜头。5. 镜头段相同性比较：通过第三章的对镜头冗余的比较方法比较视频中存在的镜头段冗余。12图2-3 镜头压缩算法实现流程图6. 重新分配序列号：如果有后面的镜头段和前面的相同，则把后面相同的镜头的序列号改成前面的序列号。如：原来序列号：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14存在相同镜头后的序列号：0 1 2 3 4 1 2 3 8 9 10 11 0 13 14以上标明原来的5，6，7段和1，2，3段相同，修改序列号为1，2，3；12段镜头和0段相同，修改为0，其他的视频镜头段的序号不变。7. 对镜头段序列号进行字典压缩：由于视频中镜头一般不

40、是独立的，多个语义相 13关的镜头组成了场景。对每个镜头进行单独压缩的时间复杂度为 ，而采用LZW字典的压缩方法的在解决上面的存在5，6，7和1，2，3的镜头冗余时可以节省算法搜索的时间复杂度（虽然在空间存储上包头占用空间比例较少（由后面介绍），显然在这种情况下采用字典的算法较适合。采用VC+6.0对压缩算法中添加LZW算法的接口函数，实现对镜头搜索及压缩。8. 添加自定义的文件头：由于对视频文件进行了镜头的重编码，采用镜头的索引方式来解决视频的播放播放（呈现）问题，使用索引自加模式来播放（呈现）视频的内容，而不是采用如avi等文件格式的帧自加模式进行视频的播放。因此需要自定义文件头，定义文件

41、的播放模式来进行播放。2.2.3 文件的编码和解码的流程1.文件的编码文件采用对每个镜头段数据进行打包，当然，如果存在连续的N个镜头段的冗余（场景的冗余）时，采用LZW压缩算法对场景中的若干个冗余的镜头进行打包（可以节省N-1个包长还有对镜头打包的时间），然后再对所有打包后的镜头包总的进行再打包。其总的文件信息的定义如图2-4：图2-4 自定义文件的文件格式其文件头数据结构描述：14typedef struct indexheaderFOURCC fcc; /类型说明，识别码DWORD dwFmsize; /包头长度DWORD dwTotalFrame; /总帧数BYTE byBits /视频

42、播放比特率struct indexDWORDLONG qwOffset; /对于基准的偏移DWORD dwSize; /偏移大小 DWORD dwDuration; /持续时间Index ;INDEXHEADER;数据包的数据头结构描述：Typedef struct dataheaderFOURCC fcc; /类型说明，识别码WORD wIndexNo; /镜头序列号DATAHEADER;图2-5为整体的数据空间占用情况：图 2-5 自定义文件的文件头格式2.压缩效率（1）设有压缩后n个视频镜头段，即存在n个索引块，设其含有的平均数据量为M，因此文件头占整个文件数据的比例为（以字节为单位）：

43、=11+12n （2-1） 11+(12+M)n由此式可知，当镜头数n一定时，镜头平均数据量M越大，文件头在整个数据中占的比率就越小。15当镜头平均数据量M一定时，镜头数越大，那么文件头在整个数据中占的比率也越小。因此镜头数越多，镜头平均数据量越大，从文件头信息方面来说，就对文件的压缩效率就越高。 （2）定义压缩前后文件的压缩比:压缩比=输入流的大小输出流的大小M(n+k) （2-2） 11+(12+M)n设视频有k个相同的镜头，那么文件的压缩比为: F=有上式可知，当视频没有镜头相同时，即k=0时，压缩比小于1，即视频没有被压缩，反而变大了。因此本算法需要基于有重复的视频镜头的基础的。令F

44、1，即存在数据的压缩时，则有k11+12nM （2-3）由于镜头数n肯定小于镜头所含的数据量的大小，并且相差的等级较大，因此可以得出3-3中的后面项的数值不会大于1，即应该是k 1，也即是当存在一个镜头冗余时就可实现数据压缩。为公式的严谨性，作如下的统计来说明。统计4种视频，包括电视新闻，连续剧，体育节目，娱乐节目的20段视频，其总帧数为485532帧，总共含的镜头数为3115，所以基于统计的镜头平均数据量为：M=4855326404803311530 （2-4） =4.57Mb 所以要想使最后的数据存在压缩，那么最少需要冗余的镜头数为：k11+1231150.034.57Mb （2-5） 即

45、只需要事重复镜头大于0.03个就能实现压缩，即包头占视频的数据量非常小，相差2个数量级。由此可知，只要存在一个镜头的冗余，那么就可以实现对数据的压缩。16由上面的统计可知视频的平均含帧数为156帧，而以30帧每秒的播放速度，那么每隔5秒即存在镜头的切换，对于实际的视频传输，是合理的和正常的。同时也可以得到当存在大于0.03156=4.58帧的视频完全重复是即可以实现对数据的压缩。当然这个压缩比比较小，存在越多的帧重复，越多的镜头重复，那么压缩比就越大，压缩的效果就越好。以上的验证只是从实际的测量说明了镜头压缩算法的可行性，即当存在镜头冗余时，使用镜头压缩算法，视频数据流是存在压缩压缩效果的。而

46、理论上视频的数据量相对于包头数据也非常大，相差2个数量级，因此添加自定义的包头，对数据量的影响不大，当存在镜头冗余时，镜头压缩是可行的。对式2-2进行化简，由于M 11，所以FM(n+k)(12+M)n （2-6）又由于一般M 12，所以F1+kn （2-7）即可以得出，当相同的镜头数k越多，那么压缩比率就越高，压缩后的镜头数越少，那么压缩比率就越高。3.文件的解码编码后的文件，在通用的视频解码器上无法解码，需要另设计解码器filters，设计并注册filters后生成控件，可以在Windows提供的播放器上播放，第四章作介绍。在此先简要介绍视频的解码流程。图2-6为经镜头压缩处理后的视频的解

47、码流程。（1）读文件头读文件的文件头，确定文件的标识码，如果能识别定义的标识码，则到下一步，否则结束。（2）读文件格式文件头的总长读文件头的格式总长，以确定文件头的范围和数据的范围，确定偏移的基地址；读文件的总帧数来确定文件的大体数据量的大小；读文件的播放比特率，确定文件的 17播放速度。图2-6 读数据流程图（3）读索引列表视频数据是以索引的形式来读取的。而一般视频格式AVI，ASF等对数据流的顺序操作是基于帧的，即采用frame_count+的方式来实现数据流的播放和呈现。而此算法如果还是基于此，那么将无法播放压缩掉的镜头帧，此处需要对索引进行操作，即index_count+。（4）按索引

48、序列读取数据由索引序列列表提供的信息及文件数据头的序列信息来逐一的读取视频数据。 182.3 小结本节阐述现有的视频压缩算法对某些视频压缩中存在的问题，提出本文视频镜头压缩算法的基本思想及实现流程，通过对常用的无损算法的说明和分析，最后提出对镜头数据包索引采用字典算法解决在压缩镜头中存在的场景压缩的问题，通过对算法的理论验证，验证了算法对镜头压缩的可行性，压缩效率，算法复杂度等问题。同时阐述了对文件的编码和解码流程。193 镜头冗余的判断上章阐述了本镜头压缩算法的基本思想即实现的流程等问题，但是需要首先解决的问题是镜头冗余的判断和压缩。因此本节解决冗余判断方面问题。在对镜头相关的特性进行阐述基

49、础上，本节的工作在于通过对视频镜头的分析，在视频分割的前提下，对待压缩的存在镜头级别冗余的视频中，提取关键帧。通过对关键帧的比较实现对视频镜头冗余的判断。同时也介绍了相关的视频索引，比较了视频索引和视频的镜头冗余判断的差别。3.1 镜头及镜头特征3.1.1 视频构成及视频特征1在讨论视频镜头冗余分析之前，先介绍视频构成的几个基本概念：视频数据从结构上自顶向下可分为视频序列、 视频场景、镜头和帧，如下图3-1所示。图3-1 视频分层结构图（1） 帧视频可以看作是一个连续静态图像的序列，其中的每一幅静态图像称为一帧。（2）镜头由摄像机记录下来的一段连续的帧序列，它是一段视频的物理组成单元。（3）关

50、键帧一幅能描述镜头主要内容的帧。根据内容的复杂程度，一个镜头可以有一个或多 20个关键帧。关键帧的选取有很多定义方式，现在有很多种提取关键帧的方法。（4）场景由一些语义相关的镜头组成，这些镜头不一定在时间上连续。场景描述了一个独立的故事单元（或者说是一个高层概念），它是一段视频的语义组成单元。 在后面的压缩算法中，主要处理视频种存在的场景的压缩问题。一般来说，一段视频由一些描述独立故事单元的场景构成；一个场景由一些语义相关的镜头组成；而每个镜头是由一些连续的帧构成，它可由一个或多个关键帧表示。2视频特征在视频的镜头比较中，需要利用视频的特征来解决镜头边界检测乃至基于内容的视频检索技术，在此镜头

51、冗余判断中也需要用到视频特征方面技术。从广义上讲，图像的特征包括基于文本(语义)特征(如关键词、注释等)和视觉特征(如色彩、纹理、形状、对象表面等)两类。以下主要介绍图像视觉特征的方面的基础。以下我们简单介绍几种常用的特征。（1）颜色空间常用的颜色空间有RGB、HIS、YUV、Lu*v*、La*b*和Munsell空间13。RGB颜色由红、绿和蓝表示，是最常用的颜色空间。HIS反映了人观察颜色的方式，较好地符合人的视觉感知特征，其中I表示亮度，H表示色调，S表示饱和度。YUV和YIQ彩色空间主要用于视频传输和编码，其中Y为亮度分量，UV或IQ为色差分量。Lu*v*和La*b*为均匀色度空间，其

52、中色差可以由欧氏空间距离度量。Munsell系统是从心理学的角度，根据颜色视觉的特点所指定的颜色分类和定标的系统，它由以H(色调)、V(明度)和C(色度)为基础系统排列的色卡组成。（2）颜色直方图颜色直方图是在许多图像应用中被广泛采用的颜色特征。它所描述的是不同色彩在整幅图像中所占的比例，而并不关心每种色彩所处的空间位置，即无法描述图像中的对象或物体。颜色直方图可以基于不同的颜色空间和坐标系。计算颜色直方图需要将颜色空间进行颜色量化。然后，通过计算颜色落在每个小区间内的象素数量可以得到颜色直方图。21（3）统计特征任何概率分布都可以由它的矩来表征。因此，如果将颜色分布作为一种概率分布的话，颜色

53、分布就可以由它的矩来表示。图像大部分内容信息主要集中在低阶矩上，因而我们计算每一个颜色通道的前三阶中心矩。令pij(c)是在图像颜色空间中第c个颜色通道的(i，j)处象素值，帧大小为MN，则该通道的前三阶矩分别为：1E(c)=MNp(c) （3-1） iji=1j=1M2(pij(c)E(c)i=1j=1NMN1/2MN1(c)=MN1S(c)=MN （3-2） 1/33pcEc()() （3-3） iji=1j=1从这些特征中找到镜头检测及索引的重要特征，根据这些重要特征来构造检测测度函数，从而达到有效的检测。第一类是标准的RGB空间，在镜头过渡的过程当中度量三种基本颜色的变化；第二类是HS

54、V空间，它是衡量帧间亮度、色度和饱和度的变化。在具体计算每一帧时，对于RGB和HSV分量计算每一帧的均值；第三类和第四类是直方图特征，从灰度以及不同的颜色空间来度量镜头间的变化；最后一类就是统计特征，计算每一帧的亮度分量V的均值、方差和偏态。具体特征选取和表示如下所示14。a. 图像的红色(R)，绿色(G)和蓝色分量(B)；b. 图像的色度(H)，饱和度(S)和亮度分量(V)；c. 灰度直方图(G-H)，RGB颜色直方图(Rgb-H)及HSV颜色直方图(Hsv-H)；d. 统计特征：均值(M)，方差(St)和偏态(P)。3.1.2 基于像素域的方法视频镜头分析方法可以分为像素域视频镜头分析和压

55、缩域视频镜头分析。像素域视频镜头分析的操作对象是直接获取的数据或者是对压缩数据完全译码后的数据，而压缩域视频镜头分析直接在压缩后的数据进行操作，不需要或者不完全译码。图3-2描述了压缩域和非压缩域的视频检测示意图。22图 3-2 压缩域与非压缩域检测示意图像素域特征包括图像特征和运动特征。其中图像特征包括颜色、纹理和形状特征。运动特征是指与时间有关的镜头特征，包括摄像机运动特征、场景对象的运动特征。在上节有介绍视频像素域特征方面的内容。通过对以上的特征检测和分析就可以得到视频的相关的信息。后面的测试中也包含了像素域内本镜头压缩算法和标准视频压缩算法（MPEG-2）的比较。3.1.3 基于压缩域

56、的方法压缩域特征包括 DC 图像、AC 系数、宏块、运动向量和位速率等1.基于 DC 图像由于 DC 图像是原 88 像素图像块的直流系数反变换得到的压缩子图，因此基本包含了原图像的全局信息，故以前基于非压缩域的方法可以使用，而且计算量较原始图像小。I 帧的 DC 图像可以直接从 DCT 系数中的直流系数中获得，P 帧和 B 帧的 DC 图像往往要经过帧间运动补偿才能计算出来，故一般采用近似计算提取 DC 图像。如 Yeung M M提出基于人体感知模型的距离计算模型15。首先进行子采样，以DC 系数为主进行反变换，得到压缩子图即 DC 图像，并进行帧间的比较定出关键帧。Yeo B提出首先根据估计算法重建 DC 序列16，并讨论了基于相邻像素比较和颜色统计比较方法来生成关键帧的方法：基于相邻像素比较对摄像机和对象运动相对敏感一点，基于颜色统计比较方法相对计算量大一点。Sethi I K的方法只利用了 I 帧 DC 系数的亮度直方图，根据2直方图比较生成关键帧17。23通过上面的