Ayrık kosinüs dönüşümü

Ayrık kosinüs dönüşümü veya TCD (adlı İngilizce : DCT veya kesikli kosinüs dönüşümü ) için bir dönüştürme yakındır Fourier dönüşümü kesikli (DFT). İzdüşüm çekirdeği bir kosinüstür ve bu nedenle, çekirdeği karmaşık bir üstel olan ve bu nedenle karmaşık katsayılar oluşturan DFT'nin aksine gerçek katsayılar oluşturur. Bununla birlikte, DCT, daha sonra dengeli sinyale uygulanan DFT'nin bir fonksiyonu olarak ifade edilebilir.

Ayrık kosinüs dönüşümünün en yaygın varyantı , genellikle basitçe "DCT" olarak adlandırılan DCT tip II'dir . Tip III'e karşılık gelen tersi, genellikle basitçe "IDCT" olarak adlandırılır.

Başvurular

DCT ve özellikle DCT- II, sinyal ve görüntü işlemede ve özellikle sıkıştırmada yaygın olarak kullanılmaktadır. DCT gerçekten de enerjinin "yeniden gruplanması" gibi mükemmel bir özelliğe sahiptir: bilgi temelde düşük frekans katsayıları tarafından taşınır. Doğal görüntüler için DCT, bir Markov sinyali için katsayıların optimal ilintisizliğini sağlayan Karhunen-Loève dönüşümüne en çok benzeyen dönüşümdür . Uygulamada, sıkıştırma yöntemleri, bu yüzden doğal bir görüntü gerçekleştirilmesi olarak modellenebilir varsayalım Markov işlemi ve yaklaşık Karhunen-Loeve dönüşümü bir DCT ile de hesaplama karmaşık ve veri bağlıdır. Bir dönüşümün ilgisi, özellikle bir figürde iyi görülür (yan tarafa bakınız). Yalnızca az sayıda katsayı sıfırdan farklıdır ve dekompresyon sırasında ters dönüşüm (IDCT) görüntüsünü yeniden oluşturmak için kullanılabilir. Sıkıştırma açısından kazanç, sıfır veya sıfıra yakın katsayıların ortadan kaldırılmasından gelir. Bu tür bir mekanizma, 8 × 8 boyutundaki piksel bloklarında (karmaşıklık nedeniyle) 2D DCT kullanan JPEG ve MPEG standartlarında kullanılır .

Sıkıştırma ses formatları kayıplı AAC , Vorbis ve MP3 , bu tekniğin değiştirilmiş bir versiyonunu kullanır; ayrık kosinüs dönüşümü değiştirilmiş (in) , MDCT (MDCT English).

DCT ayrıca diferansiyel denklem sistemlerini spektral yöntemlerle çözmek için kullanılır.

Tanım

DCT, tersine çevrilebilir bir doğrusal fonksiyon R N → R N veya eşdeğer olarak ters çevrilebilir bir N × N kare matristir. DCT'nin birkaç küçük varyasyonu vardır. İşte en ünlü dört tür.

DCT dönüşümlerinin hızlı hesaplanması için algoritmaların geliştirilmesi, hesaplaması daha basit olan matrislerin bir ürünü biçiminde tanım matrisini parçalama olasılığına dayanır ve bundan yararlanarak skaler çarpımların sayısını azaltmayı mümkün kılar. sinüzoidal fonksiyonların kimlikleri dikkate değer periyodikliği ve simetrileri . Bu nedenle, bir herhangi bir DCT transform ayrıştırmak R N ayrıştırılarak basit dönüştürmeleri N bir içine asal faktörlerin ürün olarak alt dönüşümler ve oluşturma R n, burada n, bu faktörlerden biridir. Özellikle, N 2'nin kuvveti olduğunda birçok optimizasyon geliştirilmiştir .

Bu, N × N matrisini , aynı alt matrislerin ( normal döşemede düzenlenmiş ve bu nedenle ortak veya yalnızca işaretleriyle farklılaştırılmış gerçek katsayılar kullanılarak) ve üniter veya sıfır katsayılı (-1, 0) matrislerin çarpımı biçiminde yeniden yazmak anlamına gelir. veya 1), ikincisi çarpma gerektirmez.

DCT- I

{\ displaystyle X_ {k} = {\ frac {1} {2}} \ sol (x_ {0} + (- 1) ^ {k} x_ {N-1} \ sağ) + \ toplamı _ {n = 1} ^ {N-2} {x_ {n} \ cos \ left [{\ frac {\ pi} {N-1}} nk \ sağ]}}

Bu dönüşümü yapabilir ortogonal ( hariç çarparak çarpımsal sabiti) x 0 ve x , N -1 √2 ve karşılıklı göre x 0 ve X, N -1 1 / V2 ile. Ancak bu normalleştirme, bir DFT ile yazışmayı bozar .

Herhangi bir pozitif N için tanımlanan diğer tiplerin aksine , DCT- I'in tanımlanmadığını unutmayın . ${\ displaystyle N \ leq 2}$

DCT- II

{\ displaystyle X_ {k} = \ toplam _ {n = 0} ^ {N-1} {x_ {n} \ cos \ left [{\ frac {\ pi} {N}} \ left (n + {\ frac {1} {2}} \ sağ) k \ sağ]}}

Bu DCT varyantı en yaygın olanıdır ve yaygın olarak kullanılmaktadır. Genellikle basitçe "DCT" olarak anılır. DCT- I için olduğu gibi , X 0'ı 1 / √2 ile çarparak bu dönüşümü ortogonal yapabiliriz . Bu standartlaştırılmış form pratikte yaygın olarak kullanılmaktadır, ancak DFT ile yazışmaları bozmaktadır .

N = 8 için örnek

N = 8 durumu (JPEG ve MPEG'de kullanılan) için bu dönüşümün optimize edilmiş bir gelişimi, dönüşümün matris biçiminde yeniden yazılması ve gerekli skaler çarpımların sayısını azaltmak için ayrıştırmanın çarpanlarına atılmasıyla elde edilir. Örneğin, Chen'in algoritması tarafından çarpanlara ayırma için aşağıdaki ayrıştırma kullanılır, burada ortogonal hale getirilmiştir (yukarıdaki açıklamaya bakın):

Sabit hesaplama katsayıları

{\ displaystyle {\ begin {pmatrix} C_ {1} \\ C_ {2} \\ C_ {3} \\ C_ {4} \\ C_ {5} \\ C_ {6} \\ C_ {7} \ end {pmatrix}} = {\ sqrt {\ frac {2} {N}}}. {\ begin {pmatrix} \ cos {\ frac {\ pi} {16}} \\\ cos {\ frac {2 \ pi} {16}} \\\ cos {\ frac {3 \ pi} {16}} \\\ cos {\ frac {4 \ pi} {16}} \\\ cos {\ frac {5 \ pi} {16}} \\\ cos {\ frac {6 \ pi} {16}} \\\ cos {\ frac {7 \ pi} {16}} \\\ end {pmatrix}} \ yaklaşık {\ begin { pmatrix} 0.49039 \\ 0.46194 \\ 0.41573 \\ 0.35355 \\ 0.27779 \\ 0.19134 \\ 0.09755 \ end {pmatrix}}}

DCT (8) (hızlı hesaplama yöntemi)

{\ displaystyle {\ begin {pmatrix} X_ {0} \\ X_ {2} \\ X_ {4} \\ X_ {6} \ end {pmatrix}} = {\ begin {bmatrix} C_ {4} & C_ {4} & C_ {4} & C_ {4} \\ C_ {2} & C_ {6} & - C_ {6} & - C_ {2} \\ C_ {4} & - C_ {4} & - C_ {4} & C_ {4} \\ C_ {6} & - C_ {2} & C_ {2} & - C_ {6} \ end {bmatrix}}. {\ Begin {pmatrix} x_ {0} + x_ {7} \\ x_ {1} + x_ {6} \\ x_ {2} + x_ {5} \\ x_ {3} + x_ {4} \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} X_ {1} \\ X_ {3} \\ X_ {5} \\ X_ {7} \ end {pmatrix}} = {\ begin {bmatrix} C_ {1} & C_ {3} & C_ {5} & C_ {7} \\ C_ {3} & - C_ {7} & - C_ {1} & - C_ {5} \\ C_ {5} & - C_ {1} & C_ {7} & C_ {3} \\ C_ {7} & - C_ {5} & C_ {3} & - C_ {1} \ end {bmatrix}}. {\ Begin {pmatrix} x_ {0} - x_ {7} \\ x_ {1} -x_ {6} \\ x_ {2} -x_ {5} \\ x_ {3} -x_ {4} \ end {pmatrix}}}

Tek boyutlu bir DCT için optimize edilmiş formül, genellikle iki boyutlu uzayda (transpozisyon ve kompozisyon yoluyla) olduğu gibi kullanılır; bu formül, 1024 çarpmanın (temel formül) hesaplamasını yalnızca 8 × 8'lik bir görüntü bloğunun işlenmesinde (512 çarpma yapan her 8 değer satırı için 32 çarpımdan oluşan iki geçiş) önemli ölçüde 512 çarpıma indirmeyi mümkün kılar; ancak, optimizasyonlar, iki geçişin (yatay ve dikey) bileşiminin kendisini yalnızca 256'dan 91'e (veya daha yeni araştırmalara göre daha da az) daha da düşürmek için optimize ederek hala mümkündür.

Ayrıca yukarıdaki ilk matrisin birçok ortak çarpmanın yeniden yazılmasına da izin verdiğini unutmayın (ve bu nedenle yukarıdaki formül, ortak alt ifadeleri gruplandırırsak, 32 çarpmadan çok daha azını gerektirir 16). Bu bir DCT dönüşümü kendisi olduğu için hala kolayca ilk matris emebildiğini R 4 iki alt matrisler ayrılabilir, R 2 .

Çok sayıda çalışma, bu dönüşümün streslerin bir fonksiyonu olarak nasıl optimize edilebileceğini göstermiştir, özellikle dönüşüm sıkıştırma için kullanıldığında , çünkü dönüşüm enerjinin çoğunu düşük indeksli x i katsayılarında yoğunlaştırmayı mümkün kılar . az enerji yoğunlaştıran diğerleri, başlangıçtaki uzamsal sinyale düşük bir katkı sağlar ve niceleme aşamaları sırasında sıfıra düşürülür . Bu nedenle, son katsayıları temsil etmek için gerekli olan kesinlik daha düşük veya hatta sıfırdır ve skaler çarpımların hesaplanması için kullanılan sabit katsayılar C i , kesinliklerini sabitleyerek ve çarpma tekniklerini kullanarak spesifik optimizasyonun amacı olabilir. genel bir çarpma kullanmaya gerek kalmadan daha az sayıda ekleme-kayma.

Bununla birlikte, bu hesaplama algoritması (olduğu gibi sunulur, tek boyutlu 8 noktalı DCT'yi 16 çarpma ile hesaplar), alt matrislerin çarpanlara ayrılmasıyla aşağıdaki tüm optimizasyonların temelini oluşturur. Loeffler'in algoritması şu anda yayınlanan en verimli algoritmadır (Chen'in algoritması ile 16 yerine aynı 8 noktalı DCT için 11 çarpma ile, ancak bazı katsayılar iki çarpmaya maruz kalır ve bu, algoritmayı daha az kararlı hale getirebilir). Hatta 8 noktalı DCT dönüşümü için gerekli olan teorik asgari çarpma sayısının 11'den az olamayacağı da gösterilmiştir, bu da 11 skaler çarpma algoritmasını ham performans açısından optimal hale getirir (sıraya göre sadece kararlılık açısından farklılık gösterirler) çarpımların yapıldığı ve bu nedenle ara ürünler için gerekli olan kesinlik).

Bununla birlikte, Loeffler'in algoritması, çıktılar üzerindeki 11 skaler çarpımın 8'ini gruplandırır, bu da bu çarpımları aşağıdaki niceleme adımı ile gruplamayı mümkün kılar (bu, tüm noktayı oluşturur): 2B 8 × 8 dönüşümü için, 8 × 11 satır dönüşümü için çarpmalara ve sütunlar için sadece 8 × 3 çarpımlara ihtiyaç vardır, yani nicemleme ile son 64 skaler çarpma gerçekleştirilirse toplam 112 çarpma (Chen'in algoritması ile 256 yerine). JPEG ve MPEG sıkıştırma standartlarında daha fazla ayrıntı mevcuttur .

DCT- III

{\ displaystyle X_ {k} = {\ frac {1} {2}} x_ {0} + \ sum _ {n = 1} ^ {N-1} {x_ {n} \ cos \ left [{\ frac {\ pi} {N}} n \ left (k + {\ frac {1} {2}} \ sağ) \ sağ]}}

DCT- III DCT-II dönüşümü tersidir. "DCT Inverse" adı ve kısaltması (İngilizce) "IDCT" olarak daha iyi bilinir.

DCT-I için olduğu gibi, x 0'ı √2 ile çarparak bu dönüşümü ortogonal yapabiliriz . Bu standartlaştırılmış form pratikte yaygın olarak kullanılmaktadır, ancak DFT ile yazışmaları bozmaktadır .

N = 8 için örnek

Yukarıdaki örneği alarak, Chen'in algoritmasında da kullanılan bir ters ayrıştırma (burada ortogonalleştirilmiş) elde ederiz:

IDCT (8) (hızlı hesaplama yöntemi)

{\ displaystyle {\ begin {pmatrix} x_ {0} \\ x_ {1} \\ x_ {2} \\ x_ {3} \ end {pmatrix}} = {\ begin {bmatrix} C_ {4} & C_ {2} & C_ {4} & C_ {6} \\ C_ {4} & C_ {6} & - C_ {4} & - C_ {2} \\ C_ {4} & - C_ {6} & - C_ {4} & C_ {2} \\ C_ {4} & - C_ {2} & C_ {4} & - C_ {6} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {0} \ \ X_ {2} \ \ X_ {4} \\ X_ {6} \ end {pmatrix}} + {\ begin {bmatrix} C_ {1} & C_ {3} & C_ {5} & C_ {7} \ \ C_ {3} & - C_ {7} & - C_ {1} & - C_ {5} \\ C_ {5} & - C_ {1} & C_ {7} & C_ {3} \\ C_ {7 } & - C_ {5} & C_ {3} & -C_ {1} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {1} \\ X_ {3} \\ X_ {5} \\ X_ {7} \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} x_ {7} \\ x_ {6} \\ x_ {5} \\ x_ {4} \ end {pmatrix}} = {\ begin {bmatrix} C_ {4} & C_ {2} & C_ {4} & C_ {6} \\ C_ {4} & C_ {6} & - C_ {4} & - C_ {2} \\ C_ {4} & - C_ {6} & - C_ {4} & C_ {2} \\ C_ {4} & - C_ {2} & C_ {4} & - C_ {6} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {0} \ \ X_ {2} \ \ X_ {4} \\ X_ {6} \ end {pmatrix}} - {\ begin {bmatrix} C_ {1} & C_ {3} & C_ {5} & C_ {7} \ \ C_ {3} & - C_ {7} & - C_ {1} & - C_ {5} \\ C_ {5} & - C_ {1} & C_ {7} & C_ {3} \\ C_ {7 } & - C_ {5} & C_ {3} & -C_ {1} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {1} \\ X_ {3} \\ X_ {5} \\ X_ {7} \ end {pmatrix}}}

Yine, bu matris ürününün skaler değerlendirmesi, gerekli skaler çarpımların sayısında azalmaya izin veren birçok yaygın alt ifade içerir.

DCT- IV

{\ displaystyle X_ {k} = \ toplam _ {n = 0} ^ {N-1} {x_ {n} \ cos \ left [{\ frac {\ pi} {N}} \ left (n + {\ frac {1} {2}} \ sağ) \ left (k + {\ frac {1} {2}} \ sağ) \ sağ]}}

DCT- IV , ortogonal bir matristir .

Referanslar

W. Chen, CH Smith ve SC Fralick, "Ayrık kosinüs dönüşümü için hızlı bir hesaplama algoritması", IEEE Trans. Yaygın. , Uçuş. COM-25, s. 1004-1009, Eylül. 1977.
C. Loeffler, A. Ligtenberg ve G. Moschytz, “11 Çarpma ile Pratik Hızlı 1D DCT Algoritmaları”, Uluslararası Akustik, Konuşma ve Sinyal İşleme Konferansı Bildiriler Kitabı , s. 988-991, 1989

(en) [PDF] Hesaplama açısından verimli, yüksek kaliteli Cordic tabanlı bir DCT , B. Heyne, CC Sun, J. Goetze ve SJ Ruan : Cordic dönüşümü, karmaşıklık analizi ve elde edilen performansların karşılaştırılmasıyla Loeffler hesaplama algoritmasının iyileştirilmesi , 8 noktalı DCT dönüşümünün hesaplanması için (PDF).

Kaynakça

KR Rao ve P. Yip, Ayrık Kosinüs Dönüşümü: Algoritmalar, Avantajlar, Uygulamalar (Academic Press, Boston, 1990).
AV Oppenheim, RW Schafer ve JR Buck, Discrete-Time Signal Processing , ikinci baskı (Prentice-Hall, New Jersey, 1999).
SA Martucci, "Simetrik evrişim ve ayrık sinüs ve kosinüs dönüşümleri", IEEE Trans. Sig. İşleme SP-42 , 1038-1051 (1994).
Matteo Frigo ve Steven G. Johnson: FFTW , http://www.fftw.org/ . Bir veya daha fazla boyutta, rastgele boyutta hızlı DCT'leri (tip I-IV) hesaplayabilen ücretsiz ( GPL ) C kitaplığı. Ayrıca M. Frigo ve SG Johnson, " The Design and Implementation of FFTW3 ," Proceedings of the IEEE 93 (2), 216-231 (2005).
E. Feig, S. Winograd. "Ayrık kosinüs dönüşümü için hızlı algoritmalar", Sinyal İşleme IEEE İşlemleri 40 (9), 2174-2193 (1992).
P. Duhamel ve M. Vetterli, "Hızlı Fourier dönüşümleri: öğretici inceleme ve son teknoloji ürünü", Signal Processing 19 , 259–299 (1990).
John Makhoul, "Bir ve iki boyutta hızlı bir kosinüs dönüşümü," IEEE Trans. Akust. Speech Sig. Proc. 28 (1), 27-34 (1980).

Ayrıca görün

Fourier dönüşümü
Ayrık Fourier dönüşümü
JPEG - JPEG formatında uygulanan DCT sıkıştırması

Dış bağlantılar