本文共 1918 字,大约阅读时间需要 6 分钟。
1.什么是傅里叶变换
傅里叶变换能将满足一定条件的某个表示成三角函数(正弦和/或余弦函数)或者它们的积分的线性组合。在不同的研究领域,傅里叶变换具有多种不同的变体形式,如连续傅里叶变换和。最初傅里叶分析是作为热过程的解析分析的工具被提出的。(摘抄自百度百科)
连续傅里叶变换的公式
连续傅里叶变换的逆变换的公式
通过公式可以看出一个函数,可以用复指数函数的积分来表示,如果通过欧拉公式变换,也可以用三角函数的积分来表示,其中 F(w)表示的是在某频率下的幅值,而 w为基波频率,iw表示频率,一般的傅里叶函数的曲线表示为iw为横轴,F(w)为纵轴。
傅里叶变换可以把一个函数从t域,也就是时域,变换到w域,也就是频域。通过傅里叶变换可以很方便的看出当前信号的频域特性。
2.什么是离散余弦变换
图像的各个像素点之间的变化都是平滑变化的,所以每个像素点和相邻像素点之间都是相关的,而这种相关性对图像的熵编码很不利,详细请查看信息熵的一些资料。所以我们必须通过某种变换,将图像的各个像素之间的相关性去除,其中去相关最好的算法,目前为K-L变换,但是缺乏快速算法,并且变换矩阵不固定,详细可以查看相关资料。目前常用的是离散余弦变换(DCT),由于其良好的去相关效果,可以较快的变换算法,在多媒体编码算法中得到了广泛的使用。
二维DCT变换及其逆变换的公式如下图:
DCT变换不是傅里叶变换,只是其形式有点像傅里叶变换而已。
3.DCT的整数变换
由于三角函数中会有很多小数的部分,不利于计算机处理,所以将小数部分提取出来,在量化中进行处理。具体如下图
前面三个矩阵的运算都为加法,减法,和移位( *2)运算。
4.蝶形算法
两个4x4矩阵的乘法分解开来会有12次加法和16次乘法运算,而根据DCT变换举证的特性,如果我们合并一些中间结果,就可以减少为8次加法,2次乘法运算。这就是著名的蝶形算法,如下图所示:
5.汇编代码分析
DCT的算法和hadamard变换的算法基本相同,只是某一些系数稍微有点不同,如上图所示。
所以我们只分析hadamard的变换
;-----------------------------------------------------------------------------
; void x264_idct4x4dc_mmx( int16_t d[4][4] ) ;----------------------------------------------------------------------------- ;DC分量的hadamard逆变换 cglobal x264_idct4x4dc_mmx, 1,1 movq m3, [r0+24] movq m2, [r0+16] movq m1, [r0+ 8] movq m0, [r0+ 0] ;矩阵中每一个元素都是16bit,所以每一行都是8个字节 WALSH4_1D 0,1,2,3,4 ;一维harmand变换在x86util.asm中有定义,下面会有详细说明 TRANSPOSE4x4W 0,1,2,3,4 ;转置 WALSH4_1D 0,1,2,3,4 ;继续做一维harmand变换 movq [r0+ 0], m0 movq [r0+ 8], m1 movq [r0+16], m2 movq [r0+24], m3 RET %macro WALSH4_1D 5 SUMSUB_BADC m%4, m%3, m%2, m%1, m%5 ; 蝶形算法的前半部分 SUMSUB_BADC m%4, m%2, m%3, m%1, m%5 ; 蝶形算法的后半部分 SWAP %1, %4, %3 %endmacro %macro SUMSUB_BADC 4-5 %if %0==5 SUMSUB_BA %1, %2, %5 ;第一行和第二行的加法和减法结果 SUMSUB_BA %3, %4, %5 ;第三行和第四行的加法和减法结果 %else paddw %1, %2 paddw %3, %4 paddw %2, %2 paddw %4, %4 psubw %2, %1 psubw %4, %3 %endif %endmacro %macro SUMSUB_BA 2-3 ;对两行做加法和减法,并保存结果 %if %0==2 paddw %1, %2 paddw %2, %2 psubw %2, %1 %else mova %3, %1 paddw %1, %2 psubw %2, %3 %endif %endmacro转载地址:http://tsqxb.baihongyu.com/