第三章离散余弦变换KL变换

13．8离散哈达玛变换(DHT)3.8.1哈达玛矩阵3.8.2离散哈达玛变换(DHT)23.8.1哈达玛矩阵Hadamard矩阵：定义元素只有+1和-1组成的正交方阵，各行或各列之间彼此是正交的，它要求图象的大小是。最低阶哈达码矩阵为：21111H,2nNNN3阶次为2的整数次幂哈达玛变换具有简单的递推关系：2221111NNNNNNHHHHHHHH类推有：其中是矩阵直基(Kronecker)的符号。思考：如何证明为哈达码矩阵，必为哈达码矩阵。NH2NH45111111111111111122224＝－HHHHH6•例如：N=8时，有：81111111111111111111111111111111111111111111111111111111111111111H710,12;,0,1,2,...,1;niiibubxnkHuxNxuNbIIk式中：是的二进制表示的第位。N阶哈达码矩阵第（u,x）个元素可用如下公式生成：8哈达码矩阵性质：11.[][][]2.[][]13.[][]TNNNTNNNNHHNIHHHHN4.矩阵的行与行（或列与列）交换不影响矩阵的正交性93．8.2离散哈达玛变换(DHT)以哈达码矩阵作为变换矩阵所组成的变换为哈达码变换。哈达玛变换最大的优点的变换核矩阵具有简单的递推关系。1)一维离散哈达玛变换一维哈达玛变换核为：101,12;,0,1,2,...,1;niiibxbunkgxuNNxuNbIIk式中：是的二进制表示的第位。10对应的一维哈达玛变换为：一维哈达玛反变换为：哈达玛反变换与正变换除相差常数项外，其型式基本相同。1011()()001()()(,)()(1)niiiNNbxbuxxHufxgxufxN10()()(,)(1)niiibxbuhxu1011()()00()()(,)()(1)niiiNNbxbuxxfxHuhxuHu一维哈达玛反变换核：11哈达码变换的优点：1.由于变换核只有＋1，－1两个值，因此变换只需进行加、减法运算。计算时间比傅立叶变换短，没有乘法，计算精度高。2.正反变换只差因子1/N,因此正反变换的计算完全相同，算法简单。3.由于在变换核中不存在正、余弦函数，所以计算机实现时，不会因字长有限而产生附加噪声。122）二维离散哈达玛变换1010110011001,,11,,1niiiiiniiiiiNNbxbubybvxyNNbxbubybvuvHuvfxyNfxyHuvN101(,,,)(,,,)1niiiiibxbubybvgxyuvhxyuvN二维哈达玛变换核为：正、反变换核，以及正反变换的形式完全相同。对应的二维哈达玛变换为：13哈达玛变换核是可分离的和对称的，二维变换可分成二步一维变换来实现，也存在快速算法FHT。14例：求下列图像的哈达玛变换。121331111113311111121331111113311111ff151111111331111111111331111111111113311111441111133111118004000000000000FHfH解：24000000000000000F163．9K－L变换3.9.2K－L变换3.9.1图像协方差矩阵17K-L（Karhunen-Loeve）变换也称为特征向量变换、主分量变换或霍特林(Hotelling)变换，它是完全从图像的统计性质出发实现的变换。在获取、通过通讯信道传输任何一幅图像时，总是混杂有许多随机干扰因素，我们实际获得的大部分图像都含有随机的性质，称其为随机图像。K-L变换这是针对这类广泛的随机图像提出来的，当对图像施加了K-L变换后，由变换结果而恢复的图像将是原图像在统计意义上最佳逼进。18表示所研究图像的的一个样本，采用向量形式表示：if),(yxfNN0,00,10,11,01,11,01,1iiiiiiiifffNfXfNfNfNN21N维的随机向量19选取合适的变换T，变换后向量Y：（1）Y是具有个分量的向量。（2）经Y反变换后恢复的，和原图像X具有均方误差最小。Y=[T]X2minEXXX2MN称满足这两个条件的正交变换[T]为K-L变换。20图像均值、协方差矩阵定义：均值：XEmX协方差：TXXXmXmXEC3.9.1图像协方差矩阵21数字特征的计算：111111LXiiLLTTTXiXiXiiXXiimXLCXmXmXXmmLM由于帧数是有限值，其平均值向量和X向量的协方差矩阵可近似表示为：LXmXC223.9.2K－L变换设：是协方差矩阵对应的特征向量和特征值，其中iie和2321NXC那么，K－L变换核矩阵A的用的特征向量构成：XC222222212222111211NNNNNNeeeeeeeeeA得K－L变换式：XmXAY表示K－L变换式由中心化图像向量与变换矩阵A相乘而得的变换图像向量Y。XXm23•A按照特征值的大小顺序排列的特征向量构成的变换阵，特征值小的部分对图像的影响不大。图像的能量主要集中在较大的特征值上。i24K－L变换的基本性质：（1）（2）Y的协方差矩阵为：0XXYAmXEAmXAEYEmTXTTXXTXXTTYYYAACAmXmXAEAmAXAmAXEYYEmYmYEC25（3）由Lawley和Maxwell证明：表明K－L变换具有极好的去相关性。20021NYC264）K－L反变换由：XmXAY得：XmYAX1由于A矩阵的各行都是正交归一化矢量，所以，可得：TxX=AY+m1TAA27K-L变换的优点：1.完全去除原信号X中的相关性。2.将Y截短时，均方误差最小，并等于所舍去的特征值之和。3.若将N个特征按大小顺序排列，即，若将舍去后，保留了原信号的最大能量。110N11Nm2829正是由于K-L变换的最大优点是去相关性能很好，所以可将它用于图像数据的旋转或压缩处理。但是，二维K-L变换不是可分离的变换，不能通过求两次一维的K-L变换来完成二维K-L变换的运算。同时它是一种和图像数据有关的变换，在变换中，必须计算图像数据的协方差矩阵的特征值和特征向量，计算量庞大，因此这就造成了K-L变换难以应用到实际(尤其是实时应用)中去的主要原因。22NN30对于一阶马尔可夫过程而言，DCT变换的性能十分接近K－L变换，这是经常采用DCT变换的原因。人们一方面继续寻求解特征值与特征向量的快速算法，另一方面则寻找一些虽不是“最佳”、但也有较好的去相关与能量集中的性能且容易实现的一些变换方法。而K-L变换就常常作为对这些变换性能的评价标准。K－L变换具有理论意义。313．10离散余弦变换（DCT）3．10．1一维离散余弦变换3．10．2二维离散余弦变换3．10．3二维快速DCT32傅立叶变换的缺点是要进行复数运算，在数据的描述上相当于实数的两倍。为此，我们希望有一种能够达到相同功能的变换。在此期望下，产生了DCT变换。333.10.1一维离散余弦变换正变换核：1,...,2,11,...,2,1,0:212cos2,10,NuNxNuxNuxgNxg式中一维DCT为：NuxxfNuCxfNCNxNx212cos2101010(3.6.1)34同样，一维DCT反变换核与正变换核一样，反变换为：11212cos201NuNuxuCNCNxf式中，x=0,1,2,…,N-1离散余弦变换（DiscreteCosineTransform)的变换核为实数的余弦函数。特点：＊计算速度快,没有DFT的复数运算＊对于一阶马尔可夫过程的随机过程信号，DCT是K－L变换的最好近似。353.10.2二维离散余弦变换二维DCT为：110011001100110010,0,2120,,cos2212,0,cos221212,,coscos22,1,2,...,1NNxyNNxyNNxyNNxyCfxyNyvCvfxyNNxuCufxyNNxuyvCuvfxyNNNuvN36二维DCT反变换为：NvyNuxvuCNNuxuCNNvyvCNCNyxfNuNvNuNv212cos212cos,2212cos0,2212cos,020,01,11111111式中，x,y=0,1,2,…,N-1从式中可以看出，二维DCT变换核是可分离的，可以逐次利用一维DCT算法进行计算。此外，通过观察可以发现DCT与DFT的关系：373839同样，如考虑DFT的虚数部分，对应着离散正弦变换DST可以用快速傅立叶变换算法实现快速离散余弦变换。40•DCT变换的应用：余弦变换实际上是傅立叶变换的实数部分。余弦变换主要用于图象的压缩，如目前的国际压缩标准的JPEG格式中就用到了DCT变换。具体的做法与DFT相似，给高频系数大间隔量化，低频部分小间隔量化。4142小波变换•小波变换在时域和频域中都具有良好的局部化特性，在图像处理中有广泛的应用。