天空 Blond - 离散傅里叶变换
type: channel
link: https://skyblond.info/tag/%E7%A6%BB%E6%95%A3%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2/
items: 【代码札记】初探图片隐写术（Steganography）之DFT隐写

【代码札记】初探图片隐写术（Steganography）之DFT隐写
type: item
date: 2023-07-01T13:57:00+08:00
description: 比起隐写，我认为DFT更像是盲水印。在各种D*T中，DFT看起来应该是相对简单的一个。DCT我有个大概印象，但DWT我实在不知道是什么高端的玩意儿。总之，本文将讨论在DFT变换域隐写数据。什么是DFTDFT全称Discrete Fourier transform，即离散傅里叶变换。那什么是傅里叶变换呢？我不知道该怎么给你解释，但你可以参考这个视频。简单地说，傅里叶变换是一种拆解信号的过程。以音频信号为例，一段录音对于计算机来说就是麦克风在时间尺度上对气压进行采样，一段录音可以看作是气压在时间上的函数。可是对于人的听觉来说，气压并不是特别有效的信息，而气压的变化才是。气压在某个固定周期内重复波动，这近似就算是频率了。我们的耳朵能够感受到频率，但计算机只能收录气压的采样，那怎么才能让计算机分析出人能够感知的频率呢？傅里叶变换就能够做到这件事。对于一维信号（只有一个变量），傅里叶变换将信号拆解成一系列正弦或余弦信号的叠加，而这里的正弦或余弦信号就是纯粹的频率。换句话说，傅里叶变换允许你用一系列纯粹的频率来表示一段音频（例如三倍的440Hz加上五倍的320Hz）。类似地，离散傅里叶变换是作用在离散信号上的。在理想情况下，声音应该是气压在时间上的连续函数，但对于计算机来说，声音则是每隔一段时间对气压的采样，它并不连续。因此将傅里叶变换推广到这种离散信号上，就变成了离散傅里叶变换。这在计算方式上变了，但在原理上没有改变。对于图像这样的二维信号（两个变量，x、y），傅里叶变换同样将其拆解为频率，但这里的频率并不是人耳能听到的频率了，它指的是像素明暗的周期性变化，而这里的频率也具有两个参数，分别表示水平频率（x方向）和垂直频率（y方向）。如果一个频率是(5,0)，那么这个频率看起来应该是水平方向的明暗交替；而频率(0,5)则是竖直方向的明暗交替；而频率(5,5)则是从左上角到右下角方向的明暗交替。如果光看文字难以想象的话，我推荐观看这个视频。从DFT到FFT离散傅里叶变换的计算其实不难，并没有什么特别高神的东西：$$ F(x)=\sum_{n=0}^{N-1}e^{-i\frac{2\pi}{N}nx}f(x) $$其中F(x)是傅里叶变换，f(x)是原来的信号。如果是二维的话，根据二维傅里叶变换的分离性，可以分解为在两个方向上分别进行傅里叶变换：即先以行为单位，计算x方向的傅里叶变换，然后以列为单位，计算y方向的傅里叶变换：suspend fun ComplexChannel.fft2d(): ComplexChannel = coroutineScope { // result: [height, width] val rowTransformed = this@fft2d.indices.map { y -> // feed each horizontal line into fft async { FFT.fft(this@fft2d[y]) } }.awaitAll() // here we calculate based on columns // aka the output shape is [width, height] val columnTransformed = this@fft2d[0].indices.map { x -> // we need to collect each vertical line async { val columnData = Array(this@fft2d.size) { y -> rowTransformed[y][x] } FFT.fft(columnData) } }.awaitAll() // recover the structure back to [height, weight] Array(this@fft2d.size) { y -> Array(this@fft2d[0].size) { x -> columnTransformed[x][y] } } }但如果你仔细观察DCT的定义的话，你会发现这个算法其实并不高效。在处理$e^{-i}$那部分时，需要使用欧拉公式将其变换为三角函数，这对于计算机来说本身就是一个难事了，更加雪上加霜的是，计算傅里叶变换的一个点就要对整个输入空间遍历一次。我们先看按行计算的傅里叶变换，假设图片宽度是w，那么计算一个点的傅里叶变换就要遍历w次，而完整计算一行就需要遍历$w^2$次，这还是一行，如果图片的高为h，那么光是按行计算就要遍历$hw^2$次；接下来再考虑按列计算，类似地，要$wh^2$次遍历。当你看到复杂度里面带着平方的时候，大概就能想到它算起来不会很快。为了解决这个问题，人们想出了FFT，快速傅里叶变换。由于我不是很在行数学，…