Bir ve iki boyutlu ayrık kosinüs dönüşümü

Abstract

ÖZET Bu çalışmada amaçlanan 1 -boyutlu Ayrık Kosinüs Dönüşümlerinden (AKD) yararlanarak, 2-boyutlu Ayrık Kosinüs Dönüşümlerinin klasik yöntemlere göre daha az sayıda işlem ile hesaplanmasıdır. 1-boyutlu AKD hesaplama yöntemi olarak rekürsif yaklaşım seçilmiştir. Bu yaklaşım kullanılarak, N tane 1-boyutlu AKD yardımıyla NXN boyutlarındaki AKD'nün elde edilme yöntemi incelenmişdir. Seçilen yöntemlerin diğer yöntemlerle, hesaplama sırasında kullanılan matematiksel işlem sayılan açısından, karşılaştırmaları yapılmıştır. Bu karşılaştırmalardan da görüleceği üzere sunulan yöntemler, diğer yöntemlere göre, hesaplama sırasında kullanılan toplam işlem sayısı açısından en düşükler arasında yer almaktadır.

SUMMARY DISCRETE COSINE TRANSFORM The discrete cosine transform (DCT) has found wide application in image and signal processing in general, and in data compression, filtering, and feature extraction in particular. Since its introduction, many fast algorithms for computing the DCT have been published. These algorithms can be classified into one of the following categories based on their methods of approach: a) indirect computation, b) direct factorization, or c) recursive computation. Fast Fourier transforms (FFTs) and Walsh-Hadamard transforms are used in obtain the DCT in a), but unnecessary operations are often involved in the computation steps. Using sparse matrix factorization, the algorithms in b) gain the speed advantages over the other methods because a unitary matrix, theoretically, can always be factorized into products of relatively sparse matrices. These direct factorization algorithms have been tailored to DCT matrices and require a smaller number of multiplications or additions. The fast DCT algorithm presented by Wang requires the use of a different type of DCT in addition to ordinary DCT. A new DCT algorithm by Lee requires inversion and division of the cosine coefficients, which causes numerical instabilities because of roundoff errors in finite lentgh registers. By improving upon the factorization of Wang, Suehiro and Hatori demonstrated a faster DCT algorithm. The recursive approach in c) is intended to generate higher order DCT's from lower order DCT's. In this paper this recursive approach is studied with details. The method for implementing the present algorithm requires fewer multipliers and adders than other methods, and it does not need to perform coefficient inversions and divisions as in. As a trade off, shifting and multiplexing operations are required in this method. However, as known in digital implementation, shifting operations are much faster than multiplications or additions. Moreover, the resulting architecture is quite regular for large scale implementations in parallel processing environments. vnI. ONE DIMENSIONAL DCT According to the definition of the DCT [1], for a given data sequence {x`;n = 0,1,2,...,N-1}, the DCT data sequence {zk; k = 0, 1, 2,...,N-1} is given by the following relation: 9g N-l zk(N,x) = ^-£xncos k=0,l,2,...,N-l n (2n + l)k/2N (a) where 1 i k = 0 k*0 Since sk affects only the amplitude of Zq component, for convenience, ek will be assumed to be equal to unity with z,, scaled up by v2. The DCT defined in (a) can be written in matrix form as: z = - T(N)x N (b) where x and z are column vectors denoting the input and DCT data sequences arranged in natural order. T(N) is used to designate the DCT matrix of order N as defined in (a). For clarity, the normalization factor 2/N will be neglected until the end. To give the reader a better understanding of the properties of T(N), a few simple examples are presented which can be derived directly from (b), where we have assumed that N is a power of 2. vuiThe 2nd-order DCT (N=2) is 1 1 a -a (c) If we teke into account the actual value of ek, then T(2) is the same as the 2nd-order Hadamard matrix multiplied by the constant a, where a = 1/ 4l. The 4th-order DCT (N=4) is 1111 a -a a -a P -8 -p 8 8 P -8 -p x, (d) where a=7?. P=C0SUJ and 8 = sin - The 8th-order DCT (N=8) is 11111 -a a -a a -a -8 -p 8 p -8 P -8 -p 8 p jn, -v -y -X -/x v -y X -/i -v -X ]X v -y X (e) IXwhere k = cos '*^ 16 Vio/ Y = cos - u = sin ( 1A.(n/ - u = sin - 16 J U6j From the results in the preceding examples, we can observe the following recursive property for the DCT matrices: T(N) = r>n jk/ k^j N /*J. Uy -Di ±(K/ İJ CD where f is the DCT matrix T with rows and columns being permutated in a specific order. The upper half of the above Nth-order DCT matrix corresponds to two (N/2)th-order DCT matrices. In the following section this proposition is proved.2. TWO DIMENSIONAL DCT In this section generating 2-dimensional DCT from 1 -dimensional DCT will be studied. For a given 2-D data sequence /x8;i, j = 0,1,...,N - 1], the 2-D DCT sequence {Ynm;m,n= 0,l,...,N-l} is given by Y = ran N`' N`* (2i + l)m (2j + l)n - u(m)u(n)£ ZXÜC0S OXT ffC0S nxr * N i-o j=o iM 2N (g) where u(m) = ' //JÎ, m = 0 1. m *0 By neglecting the scale factor 4/N u(m)u(n), the equation in (g) can be rewritten as below: 1 [*=!«=! (2i + l)m+(2j + n) «=!£i (2i + l)m-(2j + n) ] y-.-TlZL*00» T 7i+LZxucos - `' 2 [^ i=o j=o 2N m,n = l,l,2,...,N-l i=Q j-0 2N (h) By introducing an integer variable q«{. which is a quotient of pi + (p-l)/2 divided by N, the input sequence can be grouped into following groups: Rp=jxiWi = 0,l,2,...,N-l, j(p;a) = pi + (p-l)/2-Nqpi(h.i) Rp=xij(tnb):i = 0,l,2,...,N-l, j(p;b) = N-l-pi-(p-l)/2 + Nqpi p=l,3,5,...,N-l (h.ii) XIBy the use of this grouping the equation in (h) can be written as follows: 1 ^ ^,, (2i + l)(m + pn) ±! N (2i + l)(m-pn) - p=I L i=0 ~** 1=0 podd neven 2N 1 N-l.I» £(`*) (^P^-^P-b))0»' (2i + l)(m + pn) ^,..ip. (2i + l)(m-pn) p=! L'=0 podd 2N n +£(-!) (*.xp»> - Xtw»)60*` 2N ' '` nodd It can be seen that the expressions (0 N-l Z. (2i + l)(m + pn) i=0 -J^ 0) N-l w s (2i + l)(m-pn) i=0 2N (k) N-l q Z(-l)*(X*K.)-XiKp;b))C0S' i=0 (2i + l)(m+pn) 2N 71 (1) and vv,>, v- (2i + l)(m-pn) i»0 ^^ (m) taken from the definition in (i) corresponds to 1-D DCT. Thus, NXN DCT can be generated from N 1-D DCT. Xll