3.6.1 沃尔什-哈达玛变换学习视频在线视频

同学们好

这节课我们给大家介绍图像的离散沃尔什-哈达玛变换

之前我们已经介绍了离散傅立叶变换和离散余弦变换

那么这两种变换的 它变换计算复杂度都很高

这节课我们介绍的沃尔什-哈达玛变换

它是一种非正弦函数变换

它的变换矩阵只有正1和负1组成

所以计算比较简单 常用于图像压缩

因为沃尔什-哈达玛变换的变换矩阵只有正1和负1组成

与数值逻辑的两个状态相对应

故更适用于计算机的实现

同时占用空间少 计算简单

在图像的正交变换中得到了广泛的应用

首先 我们来看一下哈达玛变换

因为哈达玛变换的变换核是这样来定义的

当N等于2的n次方的时候

函数的哈达玛变换的变换核可以表示为

h(m,n)等于根号下N分之1 负1的i从0到n减1 bi(m)bi(u)

那么bi(m)bi(u)到底是什么呢？

bi(m)其实是非负整数m的二进制表示的第i位

那bi(u)就是u二进制表示的第i位

这个变化核看起来非常复杂

但是实际上在计算的时候是比较简单的

因为它bi(m)和bi(u)它对应的是二进制表示第i位

那么这个计算起来就比较简单了

因此一维的离散哈达玛变换就可以表示成

fu等于m从0到n减1fm hmu

我们将这种变换核写成矩阵形式大家看起来会更简洁一些

那么哈达玛变换的变换矩阵，最低阶的是H2 它就等于

根号下二分之1，1 1 1-1组成的这样一个矩阵

那么由最低阶我们还可以递推出H2n它所对应的变换矩阵

而H2n就等于 跟二分之1hn hn hn负的hn

大N是等于2的l次方的lI等于1，2去整数

虽然我们之前的变换核看起来很复杂

但是如果有了这两个形式的话

它整个的变化核计算就会非常的简单

有了H2之后就可以依次递推出H2n所对应的这个矩阵的值

比如说 我们看如果是有了H2的话

我们求H4 H4带入刚才的那个式子应该等于

根号下2分之1 h2 h2 h2 -h2

那么这里边，把这个h2带入进去，就变成了

h2前面有个跟二分之一和前面这个跟二分之一相乘

就等于2分之一，这个地方是h2的这个

矩阵里边的表现1 1 1-1，这是h2，这是h2，这是负的h2

我们仔细观察一下这个4乘4的这样一个矩阵 也就是H4

第一行都是一样的 全是1

那么第二行的话是从1到-1 又从-1到1 又从1到-1

所以这一行经过三次变号

那么第三行呢 是1 1 -1 -1 那么这中间有一次变号

最后一行呢 是1 -1 -1 1 有两次变号

是从1变到-1 然后重复一遍到1

所以整个的变号次序好像看起来没有什么顺序

没有什么规律可言

哈达玛变换核的特点其实就是，首先 它有一个递推性

我们可以借助于Hn把H2n进行递推得到

第二个性质 它的变换矩阵HN是一个实的正交变换矩阵

而且它是一个对称的

我们从这个地方可以看出来 它是一个对称矩阵

第三个呢 就是我们刚才说的这个特点

它的行和列的变号次序特别的混乱

有了一维的哈达玛变换

我们得到可以推导得出二维达玛变换的变换核

二维达玛变换的变换核是这样来定义的

这样一个求和的形式

那么这个式子我们还可以把它进一步拆开写

因为上面这个式子是-1的次幂的形式

我们可以把这个中间进行拆成两项

就等于根号下

大家看这个就是我们刚才那个一维的哈达玛变换的变换形式

后面这个也是对应的一维变换的变换核的形式

这就说明这个h(m,n,u,v)是可以分离的

也就是说 哈达玛变换的变换核是可分离的

有了这个变换核 我们就可以把哈达玛变换的这个定义给出

我们把刚才的这个可分离性带入进去之后

就可以得到它可以拆成两部分h(n,v)和h(m,u)

这个拆分之后 这个其实就相当对n做了一个哈达玛变换

然后再对外面的这个m做哈达玛变换

那我们把这个形式写成一个矩阵的形式就可以得到

本来应该是有一个转置

但是我们刚才介绍一维哈达玛变换的时候

我们说它是一个对称矩阵，所以这个转置就没有了

F就直接等于Hn，乘以f再乘以Hn

那么既然它还是一个正交的话

那我们就可以把它的反变换也写出来

f就等于HNF和HN的乘机

从这两个可以看着它的正反变换的公式是一样的

这是因为Hn本身是一个对称正交变换

那有了哈达玛变换之后

我们看一下离散沃尔什变换它是怎么来进行定义的

沃尔什变换的变换核是这样给出的

当N等于2的n次幂的时候

f(m)的离散的沃尔什变换是写成F(u)

那么它的变化核是这样来定义

w(m,u)是等于根号下

那么这个地方呢bi(m)和bn减1减2的u次幂

其实也是对应的这个m的二进制的第i位表示

那么既然有了这个

我们就可以把一维的离散的沃尔什变换写出来

F(u)就等于m从0到n减1 f(m)乘一个ω(m,u)

这个地方是一个变换核把变换核乘进去

我们就可以得到一维离散沃尔什变换的公式

那我们也看一下 当n等于4的时候

这个W4应该等于多少

其实就是说这个沃尔什变换的变换矩阵应该是什么

它是等于2分之1,1 1 1 1

第二行是1 1 -1 -1 第三行是1 -1 -1 1

第四行是1 -1 1 -1 那么，我们再总结一下它的变号规律

第一行是完全一样的 没有变号

第二行对应的是从1到-1 有一次变号

第三行对应的是从1到-1 然后再从-1到1 对应了两次变号

第四行的对着的是1到-1 -1到1 然后再从1到-1 这是三次变号

所以我们统计它的变号次数，发现它是从0123按自然数排列的

这就有了一定的规律性

那我们把沃尔什变换和哈达玛变换结合来看的话

这个矩阵其实是一样的，只不过是变号次数不一样

因此我们总结一下沃尔什变换它的特点

首先第一个，行或者是列的变号次数是有自然顺序决定的

我们刚才只看了它的行，因为它是一个对称的矩阵

所以它的列的变号次序也是一样的

第二个是变换核可由哈达玛变换核间接得到

怎么间接得到呢，就像我们刚才已经知道

哈达玛变换的变换矩阵是可以递推得到的

那递推得到之后，只不过是它的变号次序混乱

我们把它的变号次序统计出来之后

把这个变号次序按自然数排列

把它的行进行调整就可以得到这个沃尔什变换了

沃尔什变换是一个实的正交的对称矩阵

我们通过这个矩阵的形式也可以看出来

那二维的沃尔什变换的变换矩阵应该是什么样子的呢

F就应该等于WNf乘以WN

那就是这个形式是由于WN它是一个对称的矩阵来决定的

所以它那个转置就没有了

那么二维离散沃尔什变换的变换公式就可以写成这样一个形式

那同样的话 它的反变换也可以直接给出

f就应该等于WNF乘以WN

那我们接下来看一下二维沃尔什-哈达玛变换它有什么特点呢

第一 都是可分离的正交变换

这个可以通过它的变换核给推导出来

第二个都是实函数的变换

这个就与之前的离散傅立叶变换是不一样的

它的计算量就比较简单

而且它这个 大家看它的矩阵里面都是+1和-1

第三是正反变换的形式完全相同的

也就是这个变换矩阵是完全一样的

那这样的话 我们就少了它求这个矩阵的逆

或者求它的矩阵的转制的这样一个比较繁琐的过程

第四呢 变化核中不存在正余弦函数

所以用计算机计算时不会因为字长有限而产生附件的噪声

第五 由于它是正交变换所以它有很好的能量的集中作用

这个我们通过下面的例子可以看出来

比如说 如果我没给出了一个4乘4的这样一个图像f1

它的像素的值是1111第二列是3333

第三列也是3 第四列全是1

那么对于这样一个我们去做沃尔什和哈达玛变换

我们可以计算一下,因为这个时候n等于4

我们去先推导出哈达玛变换的变换矩阵

我们可以通过H2等于

那么这个就是哈达玛变换的变换矩阵

将其带入到这个公式里边,可以求得哈达玛变换的结果

F1就等于H4乘以fH4

最终的结果 大家可以看到

其余地方都是0 只有在右上角和左上角有值

也就是说它的能量就集中在了左上角和右上角

这样也证明了这个哈达玛变换它是有能量集中的作用

那么进一步我们看一下这个图像,它的沃尔什变换的结果

因为H4我们算出来了

我们可以对这个它的变号次序按自然数进行排序就可以得到W4

就是沃尔什变换的变换矩阵

W4可以推导出来 推导出来之后

我们就可以计算这个图像 它的沃尔什变换的结果

那么它跟刚才的有一点小小的不同就是

它的这个-4的这个位置集中在变到了

这个第一行的第三列的这个位置上

但是它们都是有这个能量集中的作用

就是因为它们是正交变换

我们看一下第二个例子

第二个例子是一个像素全为1的这样图像

也就是说它是一个平坦的图像 里边没有变化

对于这种图像 我们对它去做沃尔什-哈达玛变换之后

发现它的结果完全是相同的

而且最后得到的结果只有在第一个角上是有一个4的值

其它全是0 那也就说这样的图像就是一个平坦的图像

我们经过用哈达玛和沃尔什的正交变换之后

发现它的能量全集中在左上角

也就证明了我们说的这个离散沃尔什-哈达玛变换

它有能量集中的作用

从上面这两个例子可以看出

离散哈达玛变换和沃尔什变换都满足变换前后能量守恒

也就说是，你要计算能量的话

这个地方求和出来跟这个地方求和出来是一样的

我们通过这个能量公式

可以计算它变换前后的能量 它的能量是守恒的

但是相比于原图像的数据

变换后的这个数据的系数更集中

所以它有能量集中的作用

而且这个数据分布越均匀

通过沃尔什-哈达玛变换之后 它的能量越集中

这样的话 对图像的压缩是非常有益的

对于一些变换平坦的需求可能不需要去了解它的细节的问题

所以我就把这一部分进行压缩就可以

好,这节课我们就讲到这,谢谢