首页 > 编程语言 >算法学习笔记(46): 离散余弦变换(DCT)

算法学习笔记(46): 离散余弦变换(DCT)

时间:2024-03-16 21:33:59浏览次数:30  
标签:frac 46 sum 余弦 int DCT pi omega dt

前置知识:离散傅里叶变换

傅里叶变换在上文中更多的是 OI 中的理解以及应用。但是傅里叶变换奥秘还很多。

回顾 \(\omega_n\) 在傅里叶变换中的定义:\(e^{i \frac {2\pi} n}\),存在 \(\omega_n^n = 1\) 的性质。意味着离散傅里叶变换实际上是周期性的,这也变相的解释了为什么存在循环卷积的性质。

傅里叶级数

我们回顾什么是傅里叶级数。傅里叶断言,对于任何周期信号 \(x(t)\) 都可以表示为成谐波关系的虚指数信号的线性组合,即:

\[x(t) = \sum_{k = - \infty}^{\infty} a_k e^{jk \omega_0 t} \]

虽然后来证明当 \(x(t)\) 满足狄里赫利条件时才成立……

周期信号 \(x(t)\) 满足存在一个正值 \(T\) 满足:

\[\forall t, x(t) = x(t + T) \]

最小的 \(T\) 称为基波周期,\(w_0 = \frac {2\pi} T\) 称为基波频率。

如果我们知道了一个 \(x(t)\) 该如何求 \(a_k\) 呢?

利用积分:

\[\int_0^T x(t) e^{-jn \omega_0 t} dt = \int_0^T \sum_{k = - \infty}^{\infty} a_k e^{jk\omega_0 t} e^{-jn \omega_0 t} dt \]

将后面变形:

\[\int_0^T \sum_{k = - \infty}^{\infty} a_k e^{jk\omega_0 t} e^{-jn \omega_0 t} dt = \sum_k a_k \left[ \int_0^T e^{j(k - n)\omega_0 t} dt \right] \]

注意到:

\[\int_0^T e^{j(k - n)\omega_0 t} dt = \int_0^T \cos[(k - n)\omega_0 t] dt + i \int_0^T \sin[(k - n) \omega_0 t] dt \]

中,存在:

\[\int_0^T \sin[(k - n) \omega_0 t] dt = \begin{cases} T & k = n \\ 0 & k \ne n \end{cases} \]

所以:

\[a_k = \frac 1 T \int_0^T x(t) e^{-jk\omega_0 t} dt \]

DCT 变换与 DFT 的联系

DCT 实际上就是 DFT 的一种特殊形式。

在傅立叶级数的推导中:

\[\int_0^T \sin[(k - n) \omega_0 t] dt = \begin{cases} T & k = n \\ 0 & k \ne n \end{cases} \]

是非常有趣的。

这反映出了如果对一个周期为 \(T\),并且周期内是个奇函数的函数 \(\int_0^T\),结果一定 \(= 0\),反之不为 \(0\)。

那么我们考虑将一个一般的周期信号变成一个周期内的偶函数,这样和 \(\sin\) 这个奇函数相乘后还是奇函数,积分出来也就没了,从而使得 DFT 的虚部没了。

上面所说的连续的情况,但是实际上离散的情况也是一样。

考察 DFT 的式子:

\[b_k = \sum_{i = 0}^{n - 1} \omega_n^{ik}a_i \]

令 \(m = 2n\),使得 \(a_k = a_{m - k - 1}\),那么其 DFT:

\[b_k = \sum_{i = 0}^{m - 1} \omega_m^{ik} a_i = \sum_{i = 0}^{n - 1} a_i \left(\omega^{ik} + \omega^{(2n-k-1)k}\right) \]

发现并不优美,考虑将幂平移 \(\frac k 2\):

\[\begin{aligned} b_k &= \sum_{i = 0}^{m - 1} a_j \omega^{kj + \frac k 2} \\ &= \sum_{i = 0}^{n - 1} a_j \left[ \left(\cos \frac {\pi k (n + \frac 12)} n + \cos \frac {- \pi k (n + \frac 12)} n \right) + i\left(\sin \frac {\pi k (n + \frac 12)} n + \sin \frac {- \pi k (n + \frac 12)} n \right) \right] \\ &= 2 \sum_{i = 0}^{n - 1} a_j \cos \frac {\pi k(n + \frac 12)} n \end{aligned} \]

中间是利用 \(e^{ix} = \cos x + i \sin x\) 展开推导而来。

发现虚部直接没了,这符合前面得出的结论。

然后我们成功的学会了 DCT。

IDCT

由于 DCT 本质上就是 DFT,所以 IDCT 本质上就是 IDFT。所以理解是简单的了。

标签:frac,46,sum,余弦,int,DCT,pi,omega,dt
From: https://www.cnblogs.com/jeefy/p/18077655

相关文章

  • 【LeetCode 1466】重新规划路线
    题目描述原题链接:LeetCode.1466重新规划路线解题思路路线网形成一棵树,说明每个节点都参与两条路线,或作为起点或作为终点;要想所有城市都可以通往城市0,必须要把所有逆向的路线都变更一次方向,逆向路线总数量即为答案;朴素BFS版本从城市0出发,遍历每个从已通城市出发的......
  • 信息学奥赛一本通:1146:判断字符串是否为回文
    【题目描述】输入一个字符串,输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。【输入】输入为一行字符串(字符串中没有空白字符,字符串长度不超过100)。【输出】如果字符串是回文,输出yes;否则,输出no。【输入样例】abcdedcba【输出样例】yes【参考程序......
  • 代码随想录算法训练营第day46|139.单词拆分 、多重背包
    目录139.单词拆分多重背包 139.单词拆分力扣题目链接(opensnewwindow)给定一个非空字符串s和一个包含非空单词的列表wordDict,判定 s是否可以被空格拆分为一个或多个在字典中出现的单词。说明:拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单......
  • BJDCTF2020[encode]
    题目:encode,地址:encode查壳发现时upx壳,使用工具脱壳命令"upx-d",如果遇到工具脱不了的壳就手动脱壳,手动脱壳请帅哥美女*们看这篇手动脱壳。使用ida打开,观察逻辑后重命名函数:逻辑为一个换表base64+异或+RC4。其中RC4可以根据函数传入key,进而生成Box盒子来判断:知道逻辑后......
  • 一维时间序列的离散正交Stockwell变换和离散余弦Stockwell变换
    MATLAB环境下一维时间序列信号的离散正交Stockwell变换和离散余弦Stockwell变换。Stockwell变换是一种对短时傅立叶变换STFT和小波变换WT扩展的时频分析方法。Stockwell变换将傅里叶变换的绝对相位保持特性与WT的频率相关分析和多分辨率特性结合起来。离散正交Stockwell变换......
  • PostgreSQL从入门到精通教程 - 第46讲:poc-tpch测试
       PostgreSQL从小白到专家,是从入门逐渐能力提升的一个系列教程,内容包括对PG基础的认知、包括安装使用、包括角色权限、包括维护管理、、等内容,希望对热爱PG、学习PG的同学们有帮助,欢迎持续关注CUUGPG技术大讲堂。 第46讲:POC-TPCH测试  内容1:TPC-H介绍内容2:TPC-H......
  • 【MATLAB源码-第146期】基于matlab的信源编码仿真GUI,对比霍夫曼编码,算术编码和LZ编码
    操作环境:MATLAB2022a1、算法描述霍夫曼编码、算术编码和LZ编码是三种广泛应用于数据压缩领域的编码技术。它们各自拥有独特的设计哲学、实现方式和适用场景,因此在压缩效率、编解码速度和内存使用等方面表现出不同的特点。接下来详细描述这三种编码技术,并对它们进行比较。......
  • [BJDCTF2020]Easy MD5 1
    [BJDCTF2020]EasyMD51审题看到一个登录框,并且题目为ezMD5,猜测使用md5绕过SQL知识点md5的绕过解题使用ffifdyop绕过SQL查看源代码弱比较绕过输入?a[]=1&b[]=2发现为===强比较,由于md5对数组不敏感也可以使用数组绕过,这是md5的另一个特性,就是md5无法对数组进行......
  • leetcode回溯法典型例题:39.组合总和、40组合总和 II、46.全排列、47.全排列 II
    leetcode回溯法典型例题:39.组合总和、40组合总和II、46.全排列、47.全排列II39.组合总和39.组合总和-力扣(LeetCode)思路构建组合使用递归的方式构建出所有组合。由题意可知,元素可以无限取用,所以我们构建的时候每确定一个数字,进入更深层递归的时候,每个数字都可以取用(此......
  • 46_docker-compose_nginx
    1.安装Docker-composecurl-L"https://github.com/docker/compose/releases/download/v2.17.2/docker-compose-$(uname-s)-$(uname-m)"-o/usr/local/bin/docker-composechmod+x/usr/local/bin/docker-composeln-s/usr/local/bin/docker-compose/usr/b......