Discrete cosine transform离散余弦变换
离散余弦变换DCT是一种傅里叶相关变换，是由DFT奇/偶延拓得到。DCT在图像视频编码中应用广泛，在JPEG、HEVC等应用中都有使用。
1.从DFT到DCT
二维离散傅里叶变换DFT公式如下[1]：
可以看到DFT中包含了复数运算，计算复杂度高。然而实际应用中，信号大多数都是实数域上的，使用DFT会造成很大的冗余。
根据欧拉公式，一个复指数信号可以分为实部和虚部两部分（）。实部包含余弦信号，虚部则是正弦信号[2]。DCT就是利用余弦变换，对DFT进行奇/偶延拓，解决了这一问题。
来简单介绍一下奇/偶延拓：
偶延拓，关于对称点偶对称，如下图
奇延拓，关于对称点奇对称，如下图
注意在延拓中，对称点可以是数据点，也可以是两个数据点之间的中心点。
对DFT进行延拓之后，可以得到如下形式，详见[1]：
DCT是通过DFT延拓得到，保持了DFT的特性的同时，对实域进行操作，没有复数计算，计算复杂度低。
2.DCT变换
标准定义的8种DCT类型，其主要区别就是边界点的奇/偶延拓性，一维形式如下[3]：
以上8类DCT中，前四类对应于偶数阶的实偶DFT，后四类对应于奇数阶的实偶DFT。实际应用中，DCT-II应用最为广泛，尤其是在图像视频编码领域，平常一般说的DCT就指的是DCT-II。DCT-III是DCT-II的反变换，一般说的反DCT（IDCT）就指的是DCT-III。
以DCT-II为例，x(n)为时域上的一个N点长度的实数序列，在频率k下，求序列上各点对应余弦项的累加和，得到该频率下的函数值，实际上就是时域到频率的一种变换。当k=0时，各点的余弦项均为1，此时得到的结果X(0)正比于x(n)的和，被称为直流分量。当k>0时，得到各频率下的X(k)被称为交流分量。
3.二维DCT
这里说的均为一般DCT（DCT-II）。
在实际应用中，一般使用二维DCT。比如图像编码中，图像以矩阵形式存储，是一个二维数组，对图像进行二维DCT，可以实现将时域图像转为频率能量分布图，实现能量集中。
下面看两个直观的例子。
例1：假设一个4x4的平坦图像，像素值如下：
10 10 10 10
10 10 10 10
10 10 10 10
10 10 10 10对其进行DCT后的结果为：
40.000000 0.000001 -0.000002 0.000002
0.000001 0.000000 -0.000000 0.000000
-0.000002 -0.000000 0.000000 -0.000000
0.000002 0.000000 -0.000000 0.000000 例2：假设一个4x4的一般图像，像素值如下：
10 20 30 40
20 50 30 20
60 10 20 10
10 50 10 10对其进行DCT后的结果为：
100.000000 16.892467 -14.142138 -14.650753
13.065633 -28.284270 2.241706 7.071069
-14.142138 -23.425280 -10.000001 -17.356736
-5.411958 7.071067 31.543218 28.284270 可见，绝大多数能量都集中到了左上角也就是直流分量，而且结果值是有负值的。
图像中低频分量可以看做是基本图像，高频分量就是边缘轮廓细节信息。绝大多数图像都包含了大量平坦区域，因此DCT变换后大部分能量集中于低频区域（左上角），从而达到去除空间冗余的目的（例2块较小，因此能量集中不明显，块越大能量集中效果越明显）。
4.二维DCT基函数
以二维4x4 DCT-II为例，基函数的图像如下：
共有4x4个基函数，对应不同水平和垂直频率，左上角为直流分量，图中越亮的地方表示值越大。每一个基函数实际是一种假象：左上角基函数表示水平和垂直分量都等于0的基函数，此时认为图像平坦，没有变化；右上角表示水平频率最大而垂直平率为0的的基函数，此时认为图像在水平方向上发生了连续变化。
简而言之，任一4x4的像素块都可以表示为图4所示的4x4个基图像的加权和，其权值就是对应位置的DCT系数。
其他类型的DCT基函数图像这里就不贴了，直接给出各类4x4 DCT基函数图像的matlab代码，有需要自行绘制。
clc;clear all;close all;
%%DCT-1
% N = 4;
% V = sqrt(2 / N)*cos((0:N)'*(0:N)*pi/N);
% V(1,:) = V(1,:) / sqrt(2);
% V(5,:) = V(5,:) / sqrt(2);
% V(:,1) = V(:,1) / sqrt(2);
% V(:,5) = V(:,5) / sqrt(2);
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% for i=0:4
% for j=0:4
% O_DCT(i*6+2:i*6+6,j*6+2:j*6+6) = DCT_base(i*5+1:i*5+5,j*5+1:j*5+5);
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);
%%DCT-2
% N = 4;
% V = sqrt(2 / N)*cos((0:N-1)'*(1:2:2*N-1)*pi/N/2);
% V(1,:) = V(1,:) / sqrt(2);
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% I= mat2gray(DCT_base);
% imshow(I)
% for i=0:N-1
% for j=0:N-1
% O_DCT(i*(N+1)+2:i*(N+1)+(N+1),j*(N+1)+2:j*(N+1)+(N+1)) = DCT_base(i*N+1:i*N+N,j*N+1:j*N+N);
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);
%%DCT-3
% N = 4;
% V = sqrt(2 / N)*cos((1:2:2*N-1)'*(0:N-1)*pi/N/2);
% V(:,1) = V(:,1) / sqrt(2);
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% I= mat2gray(DCT_base);
% imshow(I)
% for i=0:N-1
% for j=0:N-1
% O_DCT(i*(N+1)+2:i*(N+1)+(N+1),j*(N+1)+2:j*(N+1)+(N+1)) = DCT_base(i*N+1:i*N+N,j*N+1:j*N+N);
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);
%%DCT-4
% N = 4;
% V = sqrt(2 / N)*cos((1:2:2*N-1)'*(1:2:2*N-1)*pi/N/2);
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% I= mat2gray(DCT_base);
% imshow(I)
% for i=0:N-1
% for j=0:N-1
% O_DCT(i*(N+1)+2:i*(N+1)+(N+1),j*(N+1)+2:j*(N+1)+(N+1)) = DCT_base(i*N+1:i*N+N,j*N+1:j*N+N);
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);
%%DCT-5
% N = 4;
% V = 2/sqrt(2*N-1)*cos(2*(0:N-1)'*(0:N-1)*pi/(2*N-1));
% V(1,:) = V(1,:) / sqrt(2);
% V(:,1) = V(:,1) / sqrt(2);
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% I= mat2gray(DCT_base);
% imshow(I)
% for i=0:N-1
% for j=0:N-1
% O_DCT(i*(N+1)+2:i*(N+1)+(N+1),j*(N+1)+2:j*(N+1)+(N+1)) = DCT_base(i*N+1:i*N+N,j*N+1:j*N+N);
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);
%%DCT-6
% N = 4;
% V = 2/sqrt(2*N-1)*cos((0:N-1)'*(1:2:2*N-1)*pi/(2*N-1));
% V(1,:) = V(1,:) / sqrt(2);
% V(:,4) = V(:,4) / sqrt(2);
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% I= mat2gray(DCT_base);
% imshow(I)
% for i=0:N-1
% for j=0:N-1
% O_DCT(i*(N+1)+2:i*(N+1)+(N+1),j*(N+1)+2:j*(N+1)+(N+1)) = DCT_base(i*N+1:i*N+N,j*N+1:j*N+N);
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);
%%DCT-7
% N = 4;
% V = 2/sqrt(2*N-1)*cos((1:2:2*N-1)'*(0:N-1)*pi/(2*N-1));
% V(4,:) = V(4,:) / sqrt(2);
% V(:,1) = V(:,1) / sqrt(2);
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% I= mat2gray(DCT_base);
% imshow(I)
% for i=0:N-1
% for j=0:N-1
% O_DCT(i*(N+1)+2:i*(N+1)+(N+1),j*(N+1)+2:j*(N+1)+(N+1)) = DCT_base(i*N+1:i*N+N,j*N+1:j*N+N);
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);
%%DCT-8
% N = 4;
% V = 2/sqrt(2*N-1)*cos((1:2:2*N-3)'*(1:2:2*N-3)*pi/(4*N-2));
% DCT = V';
% DCT_base = DCT(:)* DCT(:)';
% I= mat2gray(DCT_base);
% imshow(I)
% for i=0:N-2
% for j=0:N-2
% O_DCT(i*N+2:i*N+N,j*N+2:j*N+N) = DCT_base(i*(N-1)+1:i*(N-1)+(N-1),j*(N-1)+1:j*(N-1)+(N-1));
% end
% end
% I1= mat2gray(DCT_base);
% I2= mat2gray(O_DCT);
% figure(1)
% imshow(I1);
% figure(2)
% imshow(I2);5.DCT的方向性
在之前的图像视频编码中，使用最多的是DCT-II，这是由于前人统计发现，图像中大部分边缘都是水平/垂直方向的，基于该结果，使用DCT-II能量集中效果更优。
而在视频编码中，DCT主要用于预测残差的变换。预测残差受预测模式影响，会具有更多特性。文献[4]中指出帧内预测残差大小与参考点的距离成正比，沿帧内预测方向增大；帧间预测残差越接近PU边缘越大。因此对于视频编码的残差图像，会存在模式依赖的方向性。于是JEM在原HEVC的基础上，针对这一特性，引入了DST-VII和DCT-VIII，进一步优化变换。下图是DST-VII和DCT-VIII的基函数图像，从左上角的图像可以看出，图像值随着与左上角的距离向各个方向逐渐增大/减小，这样就引入了方向性。
DST-VII
DCT-VIII
JEM的自适应多核变换（详见http://blog.csdn.net/lin453701006/article/details/79026631）就是基于变换的方向性设计，针对不同预测模式，设计了不同的水平/垂直变换核组合。
参考文献：
1.概述·离散余弦变换（DCT）及其实现过程：https://zhuanlan.zhihu.com/p/33845296
2.正弦信号、余弦信号与复指数信号（欧拉公式）:
https://blog.csdn.net/lanchunhui/article/details/54600285
3.万帅, 杨付正. 新一代高效视频编码H.265/HEVC:原理、标准与实现[M]. 电子工业出版社, 2014.
4.Zhao X, Chen J, Karczewicz M, et al. Enhanced Multiple Transform for Video Coding[C]// Data Compression Conference. IEEE, 2016:73-82.