基于局部环的二维离散W变换线性同余分组算法

AN ALGORITHM FOR COMPUTING 2D—DWT BASED ON LINEAR CONGRUENCES AND LOCAL RING

本文利用线性同余分组和离散Radon变换算法将第Ⅰ类N×N点二维离散W变换转换为一系列第Ⅰ类一维离散W变换来计算,所需不同的一维离散W变换个数等于生成N×N矩阵所需的线性同余组的个数。为了避免二维离散W变换输出的重复计算,本算法将二维离散W变换的输出分解为互不相交的子集,而互不相交子集的二维离散W变换可转换为一系列离散W变换核CWT之和来计算。本文针对N=p,N=p^n(p为素数,n为正整数)N=p_1p_2,(p_1,p_2)=1几种情况分别进行讨论。

I.Gertner recently proposed an algorithm for computing 2D-DFT via discrete Radon transform based on geometric properties ofintegers~[1].In this paper,we will expand the basic idea into thefield of 2D-DWT-I(DHART)and develop a new algorithm forcomputing 2D-DWT-I(DHART).It is shown that the number ofdistinct N-point DWT-I's needed to calculate N×N-point two-dimensional DWT-I's is equal to the number of linear congruencesspanning the N×N grid.If N=P,p a prime number,the number ofdistinct N-point DWT-I's is p+1.If N=p^n,a power of a primenumber,the number of distinct N-point DWT-I's is(p+1)p^(n-1),na positive integer.If N=p_1p_2 is a product of two prime numbers,thenthe number of distinct N-Point DWT-I's needed to caclulate N×N-point two-dimensional DWT-I's is equal to p_1p_2+p_1+p_2+1.If theoutput of 2D-DWT-I can be expressed as the union of disjointsubsets,N-point DWT-I can be calculated by the sum of the coreof DWT-I,CWT,based on the local ring structure.