一种新的余弦变换

A New Cosine Transform

摘要: 作为一种有效的时频分析工具，分数余弦变换具有保实性，在信号和图像处理领域获得广泛的应用，但其计算复杂度较高。为解决此问题，本文引入Kronecker以及N的分解，将大矩阵分为小矩阵，将其并行运算，由于引入的变换在一般意义上不是经典的余弦变换，因此我们将其称为离散伪分数余弦变换(Discrete Pseudo-Fractional Cosine Transform)，同时推导出这种新变化的定义及证明其性质。

Abstract: As an effective time-frequency analysis tool, fractional cosine transform has fidelity and has been widely used in the field of signal and image processing, but its computational complexity is high. In order to solve this problem, in this paper, Kronecker and N decomposition are introduced, the large matrix is divided into small matrices, and it is operated in parallel, because the introduced transformation is not a classical cosine transformation in the general sense, so we call it Discrete Pseudo-Fractional Cosine Transform, and at the same time derive the definition of this new change and prove its properties.

1. 引言

离散余弦变换(Discrete Cosine Transform, DCT)由Ahmed等人于1974年首次提出，广泛应用于语音和图像处理中，此后各位研究者引入了各种快速算法来减少变换中涉及的乘法次数。由于余弦变换与傅里叶变换在数学上有明确的关系，因此分数余弦变换可以通过傅里叶变换推导得到。Pei [1] 等人提出了一种将离散余弦变换的特征值和特种向量推广到分数阶的方法，将这新变化称之为离散分数余弦变换(Discrete Fractional Cosine Transformation, DFrCT)，其定义是基于离散余弦变换核的特征分解，将DFT Hermite特征向量用于推导将是很理想的选择。Cariolaro [2] 在同一条线上介绍并开发了分数离散余弦变换，讨论了多重性和计算方面，指出了分数傅里叶变换的异同。徐九南等人 [3] 将一维离散余弦变换的变换核扩展到二维分数形式，得到Pei形式的二维离散分数余弦变换。通过整数阶余弦变换的线性叠加构造一种改进形式的二维离散分数余弦变换，并基于特征值和特征向量理论，分析2种离散分数余弦变换的周期关系。数值仿真结果表明2种形式可以达到相同的变换结果，适用于图像编码、数字水印等领域。Lima J B [4] 介绍了定义余弦类型的随机离散分数变换的系统过程，该过程基于生成矩阵方法的扩展，用于构造此类变换的特征向量，根据自由参数的数量对它们进行了表征，并说明了它们在图像加密 [5] 中的适用性。

本文是在离散分数余弦变换的基础上，引入新的变换。当N很大时，高阶的矩阵运算量就较大，计算复杂度高，为解决此问题，本文引入了Kronecker以及N的分解，可以将大矩阵分为小矩阵，将其并行运算。而这时的变换和通常定义的余弦变换不同，所以将其称之为离散伪分数余弦变换。

文章其余结构如下，在第2节中，我们介绍了一些预备知识以及性质的证明；第3节中是新的余弦变换的推导过程，及新变化性质的证明；最后对本文进行了总结。

2. 预备知识

2.1. 离散分数余弦变换核矩阵

由于傅里叶变换与余弦变换(DCT)、正弦变换(DST)具有内在联系，从而可以根据分数阶傅里叶变换推广出分数余弦变换、分数正弦变换 [1]。离散分数傅里叶变换(Discrete Fractional Fourier Transform, DFrFT)的运算可分成对奇信号与偶信号的运算，即离散分数余弦变换(DFrCT)与离散分数正弦变换(DFrST)。选取离散分数余弦变换，将余弦变换的特征值、特征向量推广到分数阶得到离散分数余弦变换。

所有的DFT、DCT和DST变换的核矩阵都具有无限的特征值，由于DCT矩阵可以导出DFrCT。因为DFT Hermite特征向量定义的DFrFT与连续DFrFT具有相似的输出，并具有一致性，可加性和可逆性。所以DFT Hermite特征向量用于推导DFrCT将是很理想的选择。

对于DFrCT核矩阵，特征向量 ${\hat{v}}_k$ 的特征值 ${\text{e}}^{-jk\alpha }$ (k为偶数)，则用角参数 $\alpha$ 构造N点DFrCT核矩阵的步骤如下：

1) 计算2(N-1)点DFT Hermite偶特征向量， $v={\left[v_0,v_1,\cdots ,v_{N-2},v_{N-1},v_{N-2},\cdots ,v_1\right]}^{\text{T}}$ ，则 $F_{2N-2}v=\lambda v\left(\lambda =1,-1\right)$ 。

2) 用 $\hat{v}={\left[v_0,\sqrt{2}{v}_1,\cdots ,\sqrt{2}{v}_{N-2},v_{N-1}\right]}^{\text{T}}$ 从DFT Hermite偶特征向量计算DCT特征向量。

3) 通过以下等式确定离散分数余弦变换内核：

$C_N^{\alpha }={\hat{V}}_N{\hat{D}}_V^{2\alpha /\pi }{\hat{V}}_N^{\text{T}}={\hat{V}}_N\left[\begin{array}{cccc}1& & & 0\\ & {\text{e}}^{-2j\alpha }& & \\ & & \ddots & \\ 0& & & {\text{e}}^{-j2\left(N-1\right)\alpha }\end{array}\right]$ (1-1)

其中 ${\hat{V}}_N=\left[{\hat{v}}_0|{\hat{v}}_2|\cdots |{\hat{v}}_{2N-2}\right]$ 。

2.2. 离散分数余弦变换性质

1) 酉性： ${\left(C_N^{\alpha }\right)}^{*}={\left(C_N^{\alpha }\right)}^{-1}=C_N^{-\alpha }$ 。

证明：① 因为

$\begin{array}{c}{\left(C_N^{\alpha }\right)}^{*}={\left[V_N{D}_N^{\alpha }{V}_N^{\text{T}}\right]}^{*}\\ ={\left(V_N^{\text{T}}\right)}^{*}{\left(D_N^{\alpha }\right)}^{*}{V}_N^{\ast }\\ =V_N\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{2j\alpha }& & \\ & & \ddots & \\ & & & {\text{e}}^{2j\left(N-1\right)\alpha }\end{array}\right]V_N^{\text{T}}\end{array}$

又因为 $C_N^{-\alpha }=V_N\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{2j\alpha }& & \\ & & \ddots & \\ & & & {\text{e}}^{2j\left(N-1\right)\alpha }\end{array}\right]V_N^{\text{T}}={\left(C_N^{\alpha }\right)}^{*}$

所以

${\left(C_N^{\alpha }\right)}^{*}=C_N^{-\alpha }$

② 因为

$\begin{array}{c}{C}_N^{\alpha }{C}_N^{-\alpha }=\left(V_N{D}_N^{\alpha }{V}_N^{\text{T}}\right)\left(V_N{D}_N^{-\alpha }{V}_N^{\text{T}}\right)\\ =V_N\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{-2j\alpha }& & \\ & & \ddots & \\ & & & {\text{e}}^{-2j\left(N-1\right)\alpha }\end{array}\right]\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{2j\alpha }& & \\ & & \ddots & \\ & & & {\text{e}}^{2j\left(N-1\right)\alpha }\end{array}\right]V_N^{\text{T}}\\ =I\end{array}$

则 $C_N^{-\alpha }$ 为 $C_N^{\alpha }$ 的逆矩阵，所以 $C_N^{-\alpha }={\left(C_N^{\alpha }\right)}^{-1}$ 。

综上

${\left(C_N^{\alpha }\right)}^{*}={\left(C_N^{\alpha }\right)}^{-1}=C_N^{-\alpha }$

2) 旋转可加性： $C_N^{\alpha }{C}_N^{\beta }=C_N^{\alpha +\beta }$ 。

证明：

$\begin{array}{c}{C}_N^{\alpha }{C}_N^{\beta }=\left(V_N{D}_N^{\alpha }{V}_N^{\text{T}}\right)\left(V_N{D}_N^{\beta }{V}_N^{\text{T}}\right)\\ =V_N\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{-2j\alpha }& & \\ & & \ddots & \\ & & & {\text{e}}^{-2j\left(N-1\right)\alpha }\end{array}\right]\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{-2j\beta }& & \\ & & \ddots & \\ & & & {\text{e}}^{-2j\left(N-1\right)\beta }\end{array}\right]V_N^{\text{T}}=V_N\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{-2j\left(\alpha +\beta \right)}& & \\ & & \ddots & \\ & & & {\text{e}}^{-2j\left(N-1\right)\left(\alpha +\beta \right)}\end{array}\right]V_N^{\text{T}}\end{array}$

又因为

$C_N^{\alpha +\beta }=V_N\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{-2j\left(\alpha +\beta \right)}& & \\ & & \ddots & \\ & & & {\text{e}}^{-2j\left(N-1\right)\left(\alpha +\beta \right)}\end{array}\right]V_N^{\text{T}}$

所以 $C_N^{\alpha }{C}_N^{\beta }=C_N^{\alpha +\beta }$ 。

3) 周期性： $C_N^{\alpha +\pi }=C_N^{\alpha }$ 。

证明：

$C_N^{\alpha +\pi }=V_N\left[\begin{array}{cccc}1& & & \\ & {\text{e}}^{-2j\left(\alpha +\pi \right)}& & \\ & & \ddots & \\ & & & {\text{e}}^{-2j\left(N-1\right)\left(\alpha +\pi \right)}\end{array}\right]V_N^{\text{T}}$

因为

$\begin{array}{c}{\text{e}}^{-j2\left(\alpha +\pi \right)}=\cos \left(2\alpha +2\pi \right)-\sin \left(2\alpha +2\pi \right)\\ =\cos 2\alpha -\sin 2\alpha \\ ={\text{e}}^{-j2\alpha }\end{array}$

所以

$C_N^{\alpha +\pi }=C_N^{\alpha }$

3. 一种新的余弦变换

3.1. 定义

为了确定一个新的变换矩阵，首先将假设为一个合数的变换矩阵N的阶数表示为正整数 $N=N_1,N_2,\cdots ,N_k\left(k\ge 2\right)$ 的乘积。其 $N_1,N_2,\cdots ,N_K$ 可以是素数也可以不是。

通过以下方式定义类似分数余弦变换矩阵：

$C_N^{\left(\alpha ,N_1,N_2,\cdots ,N_K\right)}=C_{N_1}^{\alpha }\otimes C_{N_2}^{\alpha }\otimes \cdots \otimes C_{N_K}^{\alpha }$ (3-1)

其中 $C_{N_k}^{\alpha },k=1,2,\cdots ,K$ 是具有分数参数 $\alpha$ 的离散分数余弦变换， $\otimes$ 表示矩阵运算的张量积。

3.2. 性质

公式(3-1)中定义的矩阵 $C_N^{\left(\alpha ,N_1,N_2,\cdots ,N_K\right)}$ 取决于如何将N分解为整数的乘积。现在我们将证明以这种方式定义的矩阵满足分数变换矩阵的大部分性质，即酉性和旋转可加性。

1) 酉性： ${\left(C_N^{\left(\alpha ,N_1,\cdots ,N_K\right)}\right)}^{-1}={\left(C_N^{\left(\alpha ,N_1,\cdots ,N_K\right)}\right)}^{*}=C_N^{\left(-\alpha ,N_1,\cdots ,N_K\right)}$

证明：① 左式 $={\left(C_{N_1}^{\alpha }\otimes C_{N_2}^{\alpha }\otimes \cdots \otimes C_{N_K}^{\alpha }\right)}^{-1}$ 。

因为对于任何可逆矩阵A和B，由克罗内克积性质知有 ${\left(A\otimes B\right)}^{-1}=A^{-1}\otimes B^{-1}$ 。

上式可得：

${\left(C_{N_1}^{\alpha }\otimes C_{N_2}^{\alpha }\otimes \cdots \otimes C_{N_K}^{\alpha }\right)}^{-1}={\left(C_{N_1}^{\alpha }\right)}^{-1}\otimes {\left(C_{N_2}^{\alpha }\right)}^{-1}\otimes \cdots \otimes {\left(C_{N_K}^{\alpha }\right)}^{-1}$

由离散分数余弦变换性质知：

${\left(C_{N_k}^{\alpha }\right)}^{-1}=C_{N_k}^{-\alpha }$

所以 ${\left(C_{N_1}^{\alpha }\right)}^{-1}\otimes {\left(C_{N_2}^{\alpha }\right)}^{-1}\otimes \cdots \otimes {\left(C_{N_K}^{\alpha }\right)}^{-1}=C_{N_1}^{-\alpha }\otimes C_{N_2}^{-\alpha }\otimes \cdots \otimes C_{N_K}^{-\alpha }=C_N^{\left(-\alpha ,N_1,N_2,\cdots ,N_K\right)}$ 。

则 ${\left(C_N^{\left(\alpha ,N_1,\cdots ,N_K\right)}\right)}^{-1}=C_N^{\left(-\alpha ,N_1,N_2,\cdots ,N_K\right)}$ 。

② 由等式(2-1)知 ${\left(C_N^{\left(\alpha ,N_1,\cdots ,N_K\right)}\right)}^{*}={\left(C_{N_1}^{\alpha }\otimes C_{N_2}^{\alpha }\otimes \cdots \otimes C_{N_K}^{\alpha }\right)}^{*}$ 。

因为对于任何矩阵A和B，由克罗内克积性质知有：

${\left(A\otimes B\right)}^{*}=A^{*}\otimes B^{*}$

所以有

${\left(C_{N_1}^{\alpha }\otimes C_{N_2}^{\alpha }\otimes \cdots \otimes C_{N_K}^{\alpha }\right)}^{*}={\left(C_{N_1}^{\alpha }\right)}^{*}\otimes {\left(C_{N_2}^{\alpha }\right)}^{*}\otimes \cdots \otimes {\left(C_{N_K}^{\alpha }\right)}^{*}$

由离散分数余弦变换性质知

${\left(C_{N_k}^{\alpha }\right)}^{*}=C_{N_k}^{-\alpha }$

则

${\left(C_N^{\left(\alpha ,N_1,\cdots ,N_K\right)}\right)}^{*}=C_N^{\left(-\alpha ,N_1,N_2,\cdots ,N_K\right)}$

综上

${\left(C_N^{\left(\alpha ,N_1,\cdots ,N_K\right)}\right)}^{-1}={\left(C_N^{\left(\alpha ,N_1,\cdots ,N_K\right)}\right)}^{*}=C_N^{\left(-\alpha ,N_1,\cdots ,N_K\right)}$

2) 指数可加性： $C_N^{\left(\alpha ,N_1,N_2,\cdots ,N_K\right)}{C}_N^{\left(\beta ,N_1,N_2,\cdots ,N_K\right)}=C_N^{\left(\alpha +\beta ,N_1,N_2,\cdots ,N_K\right)}$ 。

证明：由等式(2-1)知

$C_N^{\left(\alpha ,N_1,N_2,\cdots ,N_K\right)}{C}_N^{\left(\beta ,N_1,N_2,\cdots ,N_K\right)}=\left(C_{N_1}^{\alpha }\otimes C_{N_2}^{\alpha }\otimes \cdots C_{N_K}^{\alpha }\right)\left(C_{N_1}^{\beta }\otimes C_{N_2}^{\beta }\otimes \cdots \otimes C_{N_K}^{\beta }\right)$

又因为对于任何矩阵A、B、C和D，由克罗内克积性质知有

$\left(A\otimes B\right)\left(C\otimes D\right)=AC\otimes BD$

可得：

$\left(C_{N_1}^{\alpha }\otimes C_{N_2}^{\alpha }\otimes \cdots \otimes C_{N_K}^{\alpha }\right)\left(C_{N_1}^{\beta }\otimes C_{N_2}^{\beta }\otimes \cdots \otimes C_{N_K}^{\beta }\right)=\left(C_{N_1}^{\alpha }{C}_{N_1}^{\beta }\right)\otimes \left(C_{N_2}^{\alpha }{C}_{N_2}^{\beta }\right)\otimes \cdots \otimes \left(C_{N_K}^{\alpha }{C}_{N_K}^{\beta }\right)$

因为由离散分数余弦变换性质知

$C_{N_k}^{\alpha }{C}_{N_k}^{\beta }=C_{N_k}^{\alpha +\beta }$

则 $\left(C_{N_1}^{\alpha }{C}_{N_1}^{\beta }\right)\otimes \left(C_{N_2}^{\alpha }{C}_{N_2}^{\beta }\right)\otimes \cdots \otimes \left(C_{N_K}^{\alpha }{C}_{N_K}^{\beta }\right)=C_{N_1}^{\alpha +\beta }\otimes C_{N_2}^{\alpha +\beta }\otimes \cdots \otimes C_{N_K}^{\alpha +\beta }=C_N^{\left(\alpha +\beta ,N_1,N_2,\cdots ,N_K\right)}$

可证得

$C_N^{\left(\alpha ,N_1,N_2,\cdots ,N_K\right)}{C}_N^{\left(\beta ,N_1,N_2,\cdots ,N_K\right)}=C_N^{\left(\alpha +\beta ,N_1,N_2,\cdots ,N_K\right)}$

4. 总结

这篇文章推导出一种新的余弦变换，对于变换矩阵N的阶很大时，我们就可以通过对N的分解以及Kronecker，将大矩阵分为小矩阵，将其并行运算，从而减低计算复杂度。除此之外，对于新的余弦变换的应用也值得进一步研究，比如在图像加密领域里的应用以及与图像加密其他算法结合应用，这些都可以在今后的研究中加以思考和讨论。