DCT原理及其在视频压缩编码中的实现.pdf

1 DCT 原理及其在视频压缩编码中的实现原理及其在视频压缩编码中的实现 孙娟 北京邮电大学电信工程学院 北京 100876 E mail sunjuan1983 摘摘 要 要 本文以视频压缩编码为背景 从 DCT 的基本原理入手 介绍了 DCT 在压缩编码实 现过程中的快速算法 LLM 算法 提升格式的快速 DCT 算法 详细介绍了基于提升格式的 BinDCT 的实现原理和特性 并对各种算法性能进行比较和分析 关键词 关键词 DCT 提升格式 旋转矩阵 1 引言引言 在图像数据压缩技术中 正交变换编码是一种基本而有效的编码方法 它极大的利用了 图像数据的空间相关性 使图像数据的压缩能够达到很高的比率 它主要是利用数学变换的 方法 使用极少量的离散信号来表示大量的时域连续信号 常用的数学变换有很多种 比如 离散傅立叶变换 Disperse Fourier Transfer 沃尔什变换 哈尔变换 斜变换 离散余弦 变换 Discrete Cosine Transform 离散正弦变换 Discrete Sine Transform K L 变换等 其中 K L 变换为理想状态下的最佳变换方法 但是 由于 K L 变换没有快速的变换算法 而 DCT DFT 和 DST 都具有与 K L 变换近似的良好性质 尤其是当一阶马尔可夫过程相邻 元素相关系数 逼近 1 时 DCT 的近似性能远远优于其它两者 因此 图像压缩标准中 使用 DCT 变换来实现纹理编码 由于 DCT 变换在各种编码标准中要被反复调用 因此 其 代码执行效率对实时视频压缩起着至关重要的作用 实际应用中 如何实现 DCT 变换的编 码及如何用硬件电路实现这种编码变换是使用者关心的问题 为减少二维 DCT 的计算复杂度 人们提出了各种快速算法 1989 年 Loeffler 便构造出 仅有 11 个乘法和 29 个加法的 DCT 算法 LLM 被称之为 最终解决方案 但是算法中乘法 运算 无论是在硬件实现中还是在软件实现中都是耗费巨大的 尽管随着新的数字信号处理 器和芯片的发展 快速 DCT 算法变得更加有效 但是并没有从根本上解决制约速度的关键 问题 直到1998年T Tran受提升结构启发 运用三步提升结构和紧缩提升结构 改造W Chen 在 1977 提出的以旋转矩阵为基础结构的快速 DCT 算法 最终实现了一种没有乘法的快速 DCT 算法 BinDCT 在速度上获得了重大突破 本文首先介绍 DCT 变换的基本原理 介 绍现有的快速 DCT 算法的实现及其特点 然后给出这些算法的综合性能比较 2 DCT 变换原理变换原理 2 1 DCT 变换的图像压缩原理变换的图像压缩原理 图像信息一般都具有高度的相关性 因此任何压缩机制的目的在于除去数据中存在的相 关性 相关性就是根据给出的一部份数据来判断出其相邻的数据 在实际中存在很多数据相 关性 常见的有 空间相关性 频率相关性 时间相关性等 6 在图像压缩编码中 减少空间相关性的主要方法是正交变换 图像经过正交变换后 能 够实现图像数据压缩的物理本质在于经过多维坐标系中的适当的坐标旋转和变换 能够把散 布在各个坐标轴上的原始图像数据 在新的坐标系中集中到少数坐标轴上 因而能够用较少 的编码比特数来表示一幅图像 实现图像的压缩编码 从数学上看 用于图像压缩编码的正交变换有很多种 如 K L 变换 DCT 变换 Fourier 变换 Walsh 变换等 根据均方差最小准则 K L 具有最佳变换特性 DCT 变换次之 但是 2 K L 变换实现起来计算量很大 因此常用 DCT 变换替代 图像数据经过 DCT 变换 可实现用一个和原来不同的数学基来表示数据 其数据的相 关性能够显露出来或被拆开 在这种新基下 大部分的系数都接近于零 可以忽略 于是可 以将余下的信息存储在一个较小的数据包里 由此 实现了图像的压缩 2 2 一维一维 DCT 变换原理变换原理 设 0 1 1 X mmN 是对带宽有限信号 x t 取样得到的数据序列 共 N 个样值 其一维离散余弦变换 1D DCT 定义为 1 1 0 2 21 cos 2 N m mu Y uC uX m NN u 1 2 N 1 公式 1 其中 1 2 0 1 u C u 其他 一维离散余弦的逆变换 1D IDCT 定义为 1 1 0 2 21 Y u cos 2 N m mu X mC u NN m 1 2 N 1 公式 2 两者的变换核都是 1 2 21 cos 2 mu a u mC u NN 0 1 1 a u muN 公式 3 2 3二维二维DCT变换原理变换原理 一 维 离 散 余 弦 变 换 的 定 义 可 推 广 到 二 维 离 散 预 弦 变 换 2D DCT 设 0 1 1 0 1 1 X m nmMnN 为二维图像信号数据矩阵 而二维离散余弦 变换定义为 1 11 00 2 21 21 coscos 22 MN mn munv Y u vC u C vX m n MNMN 其中 u 0 1 M 1 v 0 1 N 1 1 2 0 1 u v C u C v 其他 公式 4 二维离散预弦变换逆变换 2D IDCT 定义为 1 11 00 2 21 21 coscos 22 MN uv munv X m nC u C v Y u v MNMN m 0 1 M 1 n 0 1 N 1 公式 5 把变换核分离可得两次一维 DCT 变换 1 12 2 21 2 21 cos cos 22 a u v m na u m a v n munv C uC v MMNN 公式 6 3 2 4 视频压缩编码中的视频压缩编码中的DCT变换变换 利用离散余弦变换进行视频压缩编码 首先要将输入的图像分解为 8 8 的块 然后对每 个块进行二维离散变换把每个块转变成 64 个 DCT 系数值 最后将变换得到的 DCT 系数进 行编码和传送 解码时对每个块进行二维 DCT 反变换 最后再将反变换后的块组合成图像 因此二维 DCT 变换可具体化为 3 77 00 1 21 21 coscos 41616 mn munv Y u vC u C vX m n 其中 u 0 1 7 v 0 1 7 公式 7 即将 8 8 的二维 DCT 变换转化为两个为 N 8 的一维 DCT 变换 3 DCT 算法的实现和性能比较算法的实现和性能比较 3 1 LLM算法算法 如果只是简单的利用 DCT 定义式中的对称性 也能给出一种快速 DCT 变换 它需要要 22 次乘法和 28 次加法 Ligtenberg 和 Vetterli 改进了 DCT 的代数分解方法 用快速算法减 少了计算量 使得计算一个 8 点 DCT 变换只需 22 次乘法和 28 次加法 2 这种算法称之为 LLM 算法 其如图 1 所示 最左边是变换前的时域信号 最右边是变换后的频域信号 其 中 C 代表 cos S 代表 sin 图 1 LLM 算法流程图 2C3 8 2 2S3 8 2S3 8 2C3 8 X 0 X 4 X 2 X 6 X 1 X 7 X 5 X 3 S 16 S 16 C 16 C 16 C 16 S3 16 C3 16 C3 16 S3 16 2 X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 4 3 2 基于提升格式的快速基于提升格式的快速DCT算法算法 从图 1 可以看出 影响运算速度的是诸如 4 3 8 3 16 7 16 等这些旋转角 度 为了提升运算速度 必须进一步对这些形式进行变换 早在 1977 年 WEN HSIUNG CHEN 便给出了一种以旋转矩阵为基础的 DCT 快速算法 如图 2 所示 其算法由 13 个乘法和 29 个加法组成 较 LLM 算法稍慢 但却是完全不同于平面旋转因子的尺度提审结构 1999 年 T Tran 以 W Chen 的提升结构为基础 运用三步提升结构和紧缩提升结构 将 DCT 算法中 的乘法因子分离出来 并使得 DCT 和 IDCT 中的乘法因子互为倒数关系 在利用对称性无 损的舍去这些乘性因子 或将他们划归到解码器的其他步骤中去 借此来消除旋转计算 加 快 DCT 算法 4 图2 提升格式的DCT算法流程图 可将旋转矩阵以三步提升格式表示成为如下形式 图3 a 翻转的旋转矩阵 b 基于翻转的旋转矩阵的紧缩提升结构 S7 16 C7 16 C7 16 S3 16 S7 16 S 4 S 4 S 8 X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 0 X 4 X 2 X 6 X 1 X 7 X 5 X 3 S3 16 cos a cos a X1 X2 Y2 Y1 sin a sin a sinacosa X1 X2 Y2 Y11 sin a sin a 1 tana Y2 5 通过这种方式实现整个算法无乘结构 可用加法和移位来实现逼近乘法 首先将提升参 数表示成二值数得形式 比如当旋转的角度为 3 16 时 转换为紧缩提升格式后参数中的 u 0 461939766 其二进制形式为 0 011101 可以根据不同的精度要求表示为各种整数形 式 1 2 7 16 或 15 32 整数经进一步简化 如用 1 2 1 32 来替代 15 32 由此可用 k 2 m k m 均为整数 的形式近似表示这些提升参数 就可以将复杂的乘法运算转化为简单的 位移和加法运算 这种算法称之为 BinDCT 算法 5 BinDCT 算法将计算的复杂度大大减低 并且更利于软硬件实现 其实现方式如图 4 所示 图中左边为 DCT 变换 右边为 IDCT 变 换 根据二值数精度的不同 整数 DCT 的参数 P1 P5 U1 U4 的取值不同 但 均为 k 2 m k m 均为整数 表 1 是根据二值数的不同精度 得到的算法组合 图4 基于提升格式的DCT改进算法流程图 表1 不同精度的提升格式DCT算法 序号 P1 U1 P2 U2 P3 P4 U4 P5 移位 加法 BinDCT1 1 2 1 2 1 1 2 1 4 1 2 3 4 1 2 9 28 BinDCT2 1 2 3 8 7 8 1 2 3 167 16 3 4 3 8 14 33 BinDCT3 3 8 3 8 7 8 1 2 3 167 16 11 163 8 17 36 P4 U4 P5 P2 U2 P3 U3 P1 U1 X 6 1 2 X 0 X 1 X 2 X 6 X 4 X 5 X 3 X 7 X 0 X 1 X 5 X 3 X 4 X 2 X 7 6 3 3 各种算法性能的比较各种算法性能的比较 DCT 变换的改进旨在改善算法速度 便于软硬件实现 在这个方面 BinDCT 由于将乘 法转变为移位和加法的逼近算法 在速度上有明显的优越性 根据仿真结果 表 2 给出了各 个算法的性能比较 表2 快速DCT算法的性能比较 算法类型 W Chen LLM BinDCT1 BinDCT3 乘法次数 13 11 0 0 加法次数 29 29 9 23 移位次数 0 0 28 42 平均速度 秒 1 万次 1 3407 1 2810 0 2711 0 3102 4 结论结论 如表 2 所示 随着 DCT 算法的改进 其运行速率越来越快 与传统算法相比 BinDCT 将乘法运算转化为位移和加法运算 这意味着 DCT 软件效率的提高或硬件设计的简化 并 且 BinDCT 算法可调整二值数的精度 因此可根据系统的需要获得速度和精度的最佳平衡 参考文献参考文献 1 E Feiga ndS W inograd On the multiplcative Complexity of discrete cosine transform IEE Trans In formation Theory Vol 38 pp 1387 1391Ju l1992 2 C L oeffler A L ightenberg an dQMoschytz P racticalfa st1d d ctal gorithmsw ith1 1m ultiplications P roc IE EEI CASSPV ol 2 pp 98 8 991 Fe b 1989 3 P Duhamel and H H Mida New2 dct algorithms suitable for visi implementation Proc IEEEI CASSP pp 1805 1808 1987 4 W H Chen C H Smith and S C Fr alick A Fast Computational Algorithm for the Discrete Cosine Transform IEEE Trans on Communications Vol COM 25 pp 1004 1009 1977 5 胡玲 DCT算法的改进及其在IP视频压缩协议中的应用 江苏省通信学会论文集 6 张春田 苏育挺 张静 数字图像压缩编码 清华大学出版社 DCT Theory and Impl