摘要
二维离散正弦变换（２ＤＤＳＴ）在数字图象处理中有重要应用。由于ＤＳＴ核的可分离性，２ＤＤＳＴ通常可用行列法由一维快速正弦变换（１ＤＦＳＴ）算法计算。将一维离散正弦变换－Ⅱ（１ＤＤＳＴ－Ⅱ）的快速递归算法推广到二维，提出了一种按频率抽取的２ｍ×２ｍ点矢量基二维离散正弦变换－Ⅱ的快速算法。该算法把Ｎ×Ｎ点ＤＳＴ－Ⅱ分解成四个×点ＤＳＴ－Ⅱ，重复进行这一过程直到最后分解成２×２点ＤＳＴ－Ⅱ。文中首先对１ＤＦＳＴ算法作了简单的代数推导；然后将该算法采用矢量基分解方式推广到二维，讨论了序列分解与Ｋｒｏｎｅｃｋｅｒ矩阵积两种表示方法，给出了信号流图；最后分析了计算复杂性，并与常用的行列法进行了比较。矢量基二维ＤＳＴ－Ⅱ的快速算法蝶形结构规则，数值稳定，与行列法相比，乘法运算量节省了２５％。
The two-dimensional discrete sine transform (2-D DST) finds important applications in digital image processing. Due to the separability of the DST kernel,the 2-D DST can be usually computed by use of the row-column method and a one-dimensional fast sine transform (1-D FST) algorithm. In this paper the fast recursive algorithm for the one-di-mensional discrete sine transform-Ⅱ(1-D DST-Ⅱ) suggested in [6] is extended to two dimensions using the vector-radix decomposition to obtain a fast algorithm for decimation-in-frequency, (2m×2m) -point,vector-radix,two-dimensional discrete sine transform-Ⅱ. The vector-radix approach decomposes the (N×N )-point DST-Ⅱ into four (N/2×N/2)-point DST-Ⅱ's. The process is repeated until only trivial (2×2)-point DST-Ⅱ'S remain. First,a simple algebraic derivation of the algorithm in [6] is presented in this paper. Then, the algorithm is extended to 2-D by means of the vector-radix approach. Derivation based on both the sequence splitting and Kronecker matrix product method is discussed. The signal flowgraph is given. Finally,the computational complexity is analysed and a comparison of this algorithm is made with the commonly used row-column method. The resulting algorithm has regular butterfly structure. It is numerically stable and saves 25% in multiplication operations as compared with the row-column method.
出处
《南京航空航天大学学报》
CAS
CSCD
1994年第2期207-215,共9页
Journal of Nanjing University of Aeronautics & Astronautics
关键词
信息处理
图象处理
离散正弦变换
signal processing
image processing
fast transformations
two-dimensional discrete sine transform-Ⅱ
fast recursive algorithms
vector-radix decomposition
