一种DTT域的二维线性卷积算法

Two dimensional linear convolution in discrete trigonometric transform domain

提出了一种在二维离散三角变换(DTT)域进行线性卷积的算法.首先推导出N1×N2的二维离散余弦变换Ⅱ型(DCT-Ⅱ)与2N1×2N2的二维离散傅里叶变换(DFT)之间的关系式,并将二维DFT的卷积乘积表达式转换成在对应的二维DTT域表示;然后给出了线性滤波器下输出信号的DCT-Ⅱ与输入信号的DTT之间关系的显式表达式;最后,分析了该算法的复杂度.结果表明,当滤波器大于5×5时,该算法计算复杂度远低于常见的空间域滤波算法.另外,在已知二维信号平移后的DCT-Ⅱ系数情况下,该算法比DFT域滤波算法具有更高的计算效率.

A novel algorithm for 2-D linear convolution in the discrete trigonometric transform （DTT） domain is proposed. First, the relationship between 2-D type-Ⅱ discrete cosine transform （ DCT- Ⅱ ） with a block size of N1 × N2 and the 2-D discrete Fourier transform （ DPT ） with a block size of 2N1 × 2N2 is derived, and the representation of the convolution multiplication properties of 2- D DFT is converted into the corresponding 2-D DTT. Secondly, the explicit expression of the rela- tionship between the DCT-Ⅱ of the output signal and the DTT of the input signal for the linear filter is given. Finally, the computational complexity of the proposed algorithm is analyzed. The results show that the proposed algorithm has lower computational complexity than the common spatial domain based method when the filter size is larger than 5 × 5. In addition, the algorithm is more efficient than the DFT domain filtering algorithm if the DCT- Ⅱ coefficients of the translated input signal are known.