Algoritma untuk pemampatan imej digital menggunakan transformasi ortogon. Transformasi kosinus diskret bagi isyarat imej

Transformasi yang digunakan untuk memampatkan imej hendaklah pantas dan, jika boleh, mudah dilaksanakan pada komputer. Ini mengandaikan, pertama sekali, bahawa transformasi sedemikian mestilah linear. Iaitu, nilai yang ditukar DENGAN( ialah gabungan linear (jumlah dengan beberapa faktor atau berat) daripada nilai asal (piksel) dj, dan faktor atau berat yang sepadan ialah nombor tertentu Wij(faktor penukaran). Bermaksud, DENGAN(-]G\- djWij, di mana g, j= 1,2,..., P. Sebagai contoh, apabila P= 4 penjelmaan ini boleh ditulis dalam bentuk matriks yang dalam kes am akan menerima pandangan seterusnya: C \u003d W D. Setiap vektor lajur matriks W dipanggil "vektor asas".

Tugas penting ialah menentukan pekali penukaran wij. Keperluan utama ialah selepas transformasi, nilai dengan\ akan menjadi besar, dan semua kuantiti lain C2, cc, ... akan menjadi kecil. Nisbah asas С( = Ylj djWij mencadangkan bahawa DENGAN( akan menjadi besar jika pemberat Wij akan meningkatkan nilai yang sepadan dj. Ini akan berlaku, sebagai contoh, jika komponen vektor wij Dan dj mempunyai maksud yang sama dan tanda yang sama. sebaliknya, DENGAN( akan menjadi kecil jika beratnya kecil dan separuh daripadanya mempunyai tanda, tanda bertentangan nombor yang sepadan dj. Oleh itu, jika c* besar diperolehi, maka vektor W(j adalah serupa dengan dj vektor asal, dan kecil DENGAN( bermakna bahawa komponen wij sangat berbeza daripada dj. Oleh itu, vektor asas wij boleh ditafsirkan sebagai alat untuk mengekstrak beberapa ciri vektor asal.

Dalam amalan, berat Wij tidak harus bergantung pada data asal. Jika tidak, ia perlu ditambahkan pada fail termampat untuk digunakan oleh penyahkod. Pertimbangan ini, serta fakta bahawa data input adalah piksel, iaitu, nilai bukan negatif, menentukan cara vektor asas dipilih. Vektor pertama, yang menjana Dengan\, hendaklah terdiri daripada nombor rapat, mungkin bertepatan. Ia akan meningkatkan nilai piksel bukan negatif. Dan semua vektor asas yang lain harus terdiri daripada separuh daripada nombor positif, dan pada separuh yang lain - dari negatif. Selepas mendarab dengan nilai positif dan menambahnya bersama-sama, hasilnya akan menjadi nombor yang kecil. (Ini benar terutamanya apabila data asal hampir, dan kita tahu bahawa piksel jiran biasanya bermagnitud hampir.) Ingat bahawa vektor asas ialah beberapa alat untuk mengekstrak ciri daripada data asal. sebab tu Pilihan baik akan ada vektor asas yang sangat berbeza antara satu sama lain dan, oleh itu, boleh mengekstrak ciri yang berbeza. Ini membawa kepada idea bahawa vektor asas sepatutnya saling ortogon. Jika matriks penjelmaan W terdiri daripada vektor ortogon, maka penjelmaan itu dipanggil ortogon. Satu lagi pemerhatian yang membolehkan pilihan vektor asas adalah betul ialah vektor ini mesti mempunyai frekuensi pembalikan yang semakin besar untuk mengekstrak, boleh dikatakan, ciri frekuensi tinggi data boleh mampat apabila mengira nilai yang diubah.

Vektor asas pertama (baris atas W) adalah semua, jadi kekerapannya ialah sifar. Semua vektor lain mempunyai dua +1 dan dua -1, jadi mereka akan memberikan nilai ditukar yang kecil dan frekuensinya (diukur dengan bilangan perubahan aksara setiap baris) meningkat. Matriks ini serupa dengan matriks transformasi Hadamard-Walsh (lihat Persamaan (3.11)). Sebagai contoh, mari kita ubah vektor awal (4,6,5,2)

Hasilnya agak memberangsangkan, kerana jumlahnya dengan\ menjadi besar (berbanding dengan data asal), dan dua nombor lain menjadi kecil. Marilah kita mengira tenaga bagi data asal dan berubah. Tenaga awal ialah 4 2 + b 2 + 5 2 + 2 2 \u003d 81, dan selepas penjelmaan, tenaga menjadi 17 2 + Z 2 + (-5) 2 + I 2 - 324, iaitu empat kali lebih banyak. Tenaga boleh dijimatkan dengan mendarab matriks penjelmaan W dengan faktor 1/2. Produk baharu W-(4,6,5,2)t akan bersamaan dengan (17/2,3/2, -5/2,1/2). Jadi, tenaga dipelihara dan tertumpu pada komponen pertama, dan kini adalah 8.5 2 /81 = 89% daripada jumlah tenaga data asal, di mana komponen pertama menyumbang hanya 20%.

Satu lagi kelebihan matriks W ialah ia juga melakukan transformasi songsang. Data asal (4,6,5,2) dipulihkan menggunakan produk W-(17/2,3/2, -5/2,1/2) i.e.

Kami kini berada dalam kedudukan untuk menghargai kebaikan transformasi ini. Kami mengukur vektor yang diubah (8.5,1.5,-2.5,0.5) dengan membundarkannya kepada integer dan mendapatkan (9.1,-3.0). Kami melakukan transformasi terbalik dan mendapatkan vektor (3.5,6.5,5.5,2.5). Dalam percubaan yang sama, kami hanya akan mengalih keluar dua nombor terkecil dan kita dapat (8. 5.0, -2.5.0), dan kemudian kita melakukan penjelmaan songsang bagi vektor terkuantiti secara kasar ini. Ini menghasilkan data yang dibina semula (3,5.5,5.5,3) yang juga agak hampir dengan yang asal. Jadi, kesimpulan kami: walaupun transformasi mudah dan intuitif ini adalah alat yang baik untuk "memerah" lebihan daripada data asal. Transformasi yang lebih canggih menghasilkan hasil yang membolehkan anda memulihkan data daripadanya ijazah yang tinggi persamaan walaupun dengan kuantisasi yang sangat kasar.

Transformasi yang digunakan untuk memampatkan imej hendaklah pantas dan, jika boleh, mudah dilaksanakan pada komputer. Ini terutamanya membayangkan bahawa transformasi tersebut mestilah linear. Iaitu, nilai yang ditukar adalah kombinasi linear (jumlah dengan beberapa pengganda atau pemberat) daripada nilai asal (piksel), dengan nombor tertentu (faktor transformasi) berfungsi sebagai pengganda atau berat yang sepadan. Jadi, di mana . Sebagai contoh, apabila penjelmaan ini boleh ditulis dalam bentuk matriks

,

yang dalam kes umum akan mengambil bentuk berikut: . Setiap vektor lajur matriks dipanggil "vektor asas".

Tugas penting ialah menentukan pekali penukaran. Keperluan utama ialah selepas transformasi, nilainya akan menjadi besar, dan semua nilai lain akan menjadi kecil. Nisbah asas mengandaikan bahawa ia akan menjadi besar jika pemberat menguatkan nilai yang sepadan. Ini akan berlaku, sebagai contoh, jika komponen vektor dan mempunyai nilai rapat dan tanda yang sama. Sebaliknya, ia akan menjadi kecil jika pemberatnya kecil dan separuh daripadanya mempunyai tanda yang bertentangan dengan nombor yang sepadan . Oleh itu, jika yang besar diperolehi, maka vektor adalah serupa dengan vektor asal, dan yang kecil bermakna bahawa komponen sangat berbeza daripada . Oleh itu, vektor asas boleh ditafsirkan sebagai alat untuk mengekstrak beberapa ciri vektor asal.

Dalam amalan, pemberat tidak harus bergantung pada data asal. Jika tidak, ia perlu ditambahkan pada fail termampat untuk digunakan oleh penyahkod. Pertimbangan ini, serta fakta bahawa data input adalah piksel, iaitu, nilai bukan negatif, menentukan cara vektor asas dipilih. Vektor pertama, yang menjana , mesti terdiri daripada nombor yang hampir, mungkin sepadan. Ia akan meningkatkan nilai piksel bukan negatif. Dan semua vektor asas lain harus terdiri daripada separuh daripada nombor positif, dan separuh lagi - daripada negatif. Selepas mendarab dengan nilai positif dan menambahnya bersama-sama, hasilnya akan menjadi nombor yang kecil. (Ini benar terutamanya apabila data asal hampir, dan kita tahu bahawa piksel jiran biasanya bermagnitud hampir.) Ingat bahawa vektor asas ialah beberapa alat untuk mengekstrak ciri daripada data asal. Oleh itu, pilihan yang baik ialah vektor asas yang sangat berbeza antara satu sama lain dan oleh itu boleh mengekstrak ciri yang berbeza. Ini membawa kepada idea bahawa vektor asas mestilah saling ortogon. Jika matriks penjelmaan terdiri daripada vektor ortogon, maka penjelmaan itu dipanggil ortogon. Satu lagi pemerhatian yang membolehkan pilihan vektor asas adalah betul ialah vektor ini mesti mempunyai frekuensi pembalikan yang semakin besar untuk mengekstrak, boleh dikatakan, ciri frekuensi tinggi data boleh mampat apabila mengira nilai yang diubah.

Sifat-sifat ini dipenuhi oleh matriks ortogonal berikut:

. (3.5)

Vektor asas pertama (baris atas) adalah semua, jadi kekerapannya ialah sifar. Semua vektor lain mempunyai dua +1 dan dua -1, jadi mereka akan memberikan nilai ditukar yang kecil dan frekuensinya (diukur dengan bilangan perubahan aksara setiap baris) meningkat. Matriks ini serupa dengan matriks transformasi Hadamard Walsh (lihat Persamaan (3.11)). Sebagai contoh, mari kita ubah vektor awal (4,6,5,2):

.

Hasilnya agak memberangsangkan, kerana bilangannya menjadi besar (berbanding dengan data asal), dan dua nombor lagi menjadi kecil. Marilah kita mengira tenaga bagi data asal dan berubah. Tenaga awal ialah , dan selepas penukaran, tenaga menjadi, iaitu empat kali lebih besar. Tenaga boleh dijimatkan dengan mendarabkan matriks penjelmaan dengan faktor 1/2. Produk baru akan sama dengan . Jadi tenaga dipelihara dan tertumpu pada komponen pertama, dan ia sekarang daripada jumlah tenaga data awal, di mana komponen pertama menyumbang hanya 20%.

Satu lagi kelebihan matriks ialah ia juga melakukan penjelmaan songsang. Data asal (4,6,5,2) dipulihkan menggunakan produk .

Kami kini berada dalam kedudukan untuk menghargai kebaikan transformasi ini. Kami mengukur vektor yang diubah (8.5,1.5,–2.5,0.5) dengan membundarkannya kepada integer dan mendapatkan (9.1,–3.0). Kami melakukan transformasi terbalik dan mendapatkan vektor (3.5,6.5,5.5,2.5). Dalam percubaan yang serupa, kami hanya mengalih keluar dua nombor terkecil dan mendapatkan (8.5.0,–2.5.0), dan kemudian kami melakukan penjelmaan songsang bagi vektor terkuantiti kasar ini. Ini menghasilkan data yang dibina semula (3,5.5,5.5,3) yang juga agak hampir dengan yang asal. Jadi, kesimpulan kami: walaupun transformasi mudah dan intuitif ini adalah alat yang baik untuk "memerah" lebihan daripada data asal. Transformasi yang lebih canggih menghasilkan keputusan yang membolehkan data dipulihkan dengan tahap persamaan yang tinggi walaupun dengan pengkuantitian yang sangat kasar.

Sesetengah artis memaparkan matahari dalam warna kuning
bintik, dan bintik kuning lain di matahari.
- Pablo Picasso

"Imej dalam poligrafi" - Kekhususan imej dalam poligrafi. Sifat utama poli imej grafik. Buku. Ciri tersendiri kebanyakan seni visual. Pluraliti Watak massa Kebolehcapaian awam. Menyambung imej dengan teks. Seni buku. fon.

"Vektor dan grafik raster" - Primitif vektor ditakrifkan menggunakan penerangan. Prinsip membina imej vektor dan raster. Imej vektor menggunakan jumlah memori yang agak kecil. Jenis grafik komputer. Imej vektor diterangkan dengan berpuluh-puluh dan kadangkala beribu-ribu arahan. Kelemahan grafik raster.

"Grafik komputer" - Masalah utama apabila bekerja dengan grafik raster. Jenis grafik komputer berbeza dalam prinsip pembentukan imej. Grafik komputer. Grafik fraktal. Jenis grafik komputer. Jumlah data yang besar. Piksel. Ciri-ciri perbandingan raster dan grafik vektor. Setiap titik skrin hanya boleh mempunyai dua keadaan - "hitam" atau "putih".

"Mencipta grafik" - Sempadan kanvas. Tugasan 4. Buat lukisan yang terdiri daripada bentuk auto. Buat lukisan menggunakan bar alat Lukisan. Kedudukan imej grafik dalam teks. Sisipkan gambar daripada koleksi ke dalam teks. Kanvas. Ciri perbandingan grafik raster dan vektor. Ciri-ciri mencipta imej vektor dalam Word 2003.

"Imej kepala manusia" - Wajah sejuk dan mati yang lain Ditutup dengan palang, seperti penjara bawah tanah. Yang lain seperti menara yang tidak didiami oleh sesiapa pun dan memandang ke luar tingkap untuk masa yang lama. Apakah potret? Perkadaran wajah seseorang. Imej ciri muka. Wajah dan emosi seseorang. N. Zabolotsky. Apakah wajah-wajah itu? Lukisan kepala manusia. Sesungguhnya dunia ini hebat dan indah!

"Bitmaps" - Kesimpulan pada percubaan. merah. Apakah warna asas yang digunakan oleh komputer? Pengekodan raster maklumat grafik. Peta bit. Piksel warna yang berbeza. Biru (turquoise). Kelabu. Merah jambu. Palet komputer moden. Semua warna boleh dinomborkan, dan setiap nombor boleh ditukar menjadi kod binari.

Kawalan

Komunikasi, komunikasi, elektronik radio dan peranti digital

Algoritma untuk menukar imej sumber berdasarkan transformasi ortogon Untuk tujuan apakah algoritma untuk mengubah imej asal berdasarkan transformasi ortogon boleh digunakan?Apakah persamaan dan perbezaan antara transformasi Fourier diskret dan jenis transformasi ortogon yang lain. Salah satu jenis penjelmaan ortogon ialah penjelmaan Fourier diskret. Dalam proses transformasi ortogon imej dengan korelasi yang kuat antara unsur jiran, ...

2.4. Algoritma untuk mengubah imej sumber berdasarkan transformasi ortogon (Untuk tujuan apakah algoritma untuk mengubah imej sumber berdasarkan transformasi ortogon boleh digunakan? Apakah persamaan dan perbezaan antara transformasi Fourier diskret dan jenis transformasi ortogon yang lain?).

Dalam sesetengah kes, untuk mengurangkan jumlah data atau memudahkan prosedur untuk mengekstrak ciri objek pada peringkat pengecaman berikutnya, adalah dinasihatkan untuk mengubah tatasusunan dua dimensi yang asal dahulu [Е i , j ] ke dalam tatasusunan nilai pekali [ F u , v ], yang mempunyai format MxN yang sama seperti imej asal.

Tatasusunan sekunder atau sebaliknya matriks pekali dipanggil transformasi. Salah satu jenis penjelmaan ortogon ialah penjelmaan Fourier diskret. Dalam kes penjelmaan Fourier, pengubah hanyalah spektrum spatial dua dimensi imej.

Dalam kes umum, sebarang penjelmaan imej asal berdasarkan operator ortogon boleh dianggap sebagai operasi penguraian imej kepada spektrum dua dimensi umum, dan pekali (iaitu, unsur penjelmaan) sebagai amplitud bagi yang sepadan. komponen spektrum. Ambil perhatian bahawa jika dalam kes ini fungsi bukan harmoni digunakan sebagai fungsi asas, maka konsep frekuensi ruang harus digeneralisasikan dan konsep jujukan harus digunakan.

urutan dipanggil nilai yang sama dengan separuh bilangan purata sifar lintasan seunit masa atau seunit panjang.

Dalam proses penjelmaan ortogon imej yang mempunyai perkaitan yang kuat antara elemen bersebelahan, perkaitan (pemutihan) berlaku. Oleh itu, nilai-nilai unsur-unsur transformasi ternyata hampir tidak berkorelasi. Tidak seperti tatasusunan asal, yang dicirikan oleh taburan purata tenaga isyarat antara unsur, taburan tenaga isyarat dalam transformasi adalah sangat tidak sekata. Bahagian utama tenaga diambil kira oleh unsur-unsur dengan kecil nombor siri(iaitu, kepada jujukan spatial rendah) dan hanya sebahagian kecil kepada yang lain (lihat Rajah 2. 3).

nasi. 2. 3. Pengagihan tenaga isyarat antara elemen individu
dalam tatasusunan asal (a) dan dalam penjelmaan (b).

Keadaan ini membolehkan kita sama ada membuang (iaitu, menganggap sama dengan sifar) paling unsur-unsur transformasi (yang bermaksud, pada dasarnya, penapisan spatial frekuensi rendah), atau kuantitinya ke dalam sebilangan kecil tahap menggunakan bilangan bit minimum kod binari.

Mari kita pertimbangkan beberapa jenis transformasi ortogon yang paling biasa digunakan dalam pemprosesan imej digital.

Di sini pekali F u secara amnya ialah nombor kompleks

Transformasi Fourier Diskret

Setiap pekali kompleks boleh digantikan dengan dua komponen sebenar. Komponen ini masing-masing mencirikan spektrum diskret spatial amplitud dan fasa dan ditakrifkan seperti berikut:

Kelemahan utama transformasi Fourier diskret ialah jumlah pengiraan yang agak besar, serta keperluan untuk menjimatkan sebilangan besar komponen transformasi berbanding dengan transformasi ortogon lain dengan ralat pembinaan semula imej yang sama (iaitu, dengan kehilangan maklumat yang sama). Di samping itu, untuk menyimpan komponen individu bagi pekali kompleks, jumlah memori yang lebih besar diperlukan daripada nilai sebenar unsur-unsur tatasusunan asal. Bercakap tentang transformasi Fourier diskret, kita harus menyebut kemungkinan menggunakan algoritma yang dibangunkan khasTransformasi Fourier Pantas, serta peranti pengkomputeran khusus untuk pelaksanaannya yang dipanggilpemproses sistolik.

Walsh berubah(untuk M = N )

Sebaliknya, pekali b k (Z ) ditakrifkan seperti berikut: b k (Z ) adalah sama dengan nilai k -digit ke-kod binari nombor itu Z yang terdiri daripada l digit binari. Jika, sebagai contoh, Z = 10, i.e. 10 10 \u003d 1010 2, kemudian
b0 = 0; b1 = 1; b2 = 0; b 3 = 1.

b k ditentukan mengikut peraturan definisi mereka dalam transformasi Walsh.

Transformasi Hadamard(untuk M = N )

Jelas sekali semua jenis transformasi ortogon boleh diterbalikkan, iaitu, menggunakan prosedur penjelmaan songsang, anda boleh memulihkan imej asal daripada transformasi.

Biarkan [E i , j ] tatasusunan format imej sumber NxN , di mana j nombor baris, i bilangan lajur elemen (bilangan elemen dalam satu baris); [ F u , v ] transformasi imej yang mempunyai format yang sama NxN , di mana anda dan v nombor baris dan nombor lajur bagi unsur-unsur transformasi, masing-masing. Kemudian, dalam kes umum, tanpa mengira jenis transformasi ortogon, kami menulis

di mana a (i , j , u , v ) dan b (i , j , u , v ) fungsi asas penjelmaan langsung dan songsang, masing-masing.

Dari sudut praktikal, adalah penting untuk ambil perhatian bahawa semua jenis transformasi ortogon yang dipertimbangkan di atas boleh dipisahkan dalam pembolehubah. Oleh itu, pengiraan transformasi ortogon dua dimensi langsung dan songsang boleh dikurangkan kepada pelaksanaan berurutan transformasi satu dimensi.

Di sini a str(i, u), b(i, u) dan a(j, v), b(j, v) fungsi asas penjelmaan langsung dan songsang, masing-masing, sepanjang arah baris dan lajur.

Untuk kemudahan rakaman dan pengiraan, adalah dinasihatkan untuk menggunakan radas matriks

Di sini [A e] dan [A str ] matriks penjelmaan langsung; [ V e ] dan [ V str ] matriks penjelmaan songsang; [A str ] t dan [V str ] t matriks yang diperoleh dengan memindahkan matriks [ A str ] dan [ V str ].

Sudah tentu, tanpa mengira bentuknya perwakilan matematik, transformasi ortogon langsung dan songsang tatasusunan dua dimensi memerlukan, dalam kes umum, kos pengiraan yang ketara. Ini harus diambil kira semasa mereka bentuk

ATSN beroperasi dalam masa nyata. Walau bagaimanapun, apabila pemprosesan digital imej binari, prosedur transformasi ortogon sangat dipermudahkan, terutamanya dalam kes menggunakan fungsi asas binari (Walsh, Hadamard, dll.).

Serta karya lain yang mungkin menarik minat anda
7090.		ekonomi dunia. Jawapan kepada soalan peperiksaan	255.04KB
	ekonomi dunia. Jawapan kepada soalan peperiksaan Intipati ekonomi dunia dan ekonomi dunia (dunia). ekonomi dunia dalam kesusasteraan ekonomi moden, ia digunakan untuk merujuk kepada kedua-dua sistem negara dan ekonomi.
7091.		Agama dunia. Tutorial	188.67KB
	Pengenalan Seorang penjelajah yang terbang ke planet kita dari angkasa lepas mungkin menyimpulkan bahawa kita sedang menderita penyakit lucah dan sangat misteri dengan pelbagai simptom yang mengejutkan. Dia memaksa beberapa orang membakar, memotong atau mengebom mereka dengan kejam...
7092.		Skolastik zaman pertengahan F. Aquinas	43.53KB
	Skolastik Abad Pertengahan F. Aquinas Ciri-ciri Zaman Pertengahan Era Zaman Pertengahan berlangsung lebih dari seribu tahun. Para saintis menganggap permulaan Zaman Pertengahan - kejatuhan Empayar Rom (abad ke-5 M), apabila agama Kristian akhirnya ditubuhkan ...
7093.		Pemasaran perkhidmatan pelanggan	49.99KB
	Pengenalan Dalam ekonomi pasaran, banyak masalah pengeluar komoditi tidak dapat diselesaikan sepenuhnya dengan bantuan kaedah tradisional pengurusan. Ia diperlukan untuk mewujudkan sistem pengurusan yang memastikan kecekapan unit perniagaan dalam...
7094.		Magnetometer pada SQUID	108.5KB
	Magnetometer pada SQUID. Superkonduktiviti. Parameter asas superkonduktor. Fenomena superkonduktiviti ialah pada suhu tertentu yang hampir dengan sifar mutlak, rintangan elektrik hilang dalam sesetengah bahan. Suhu ini...
7095.		Sosiolinguistik. Ceramah. Stratifikasi sosial bahasa	190KB
	Kuliah mengenai kursus Sosiolinguistik. Kuliah 1. Mata pelajaran sosiolinguistik dan kaedah analisis sosiolinguistik. Subjek kajian sosiolinguistik ialah masalah manusia dan masyarakat. Objek langsung sosiolinguistik adalah...
7096.		Teknologi produk daging emulsi	65.69KB
	Kuliah 4. Teknologi produk daging emulsi.
7097.		Asas Pengaturcaraan Pascal	81.53KB
	Kursus pendek ceramah. Asas pengaturcaraan dalam Pengenalan Pascal. Pertama sekali, perlu diingatkan bahawa kajian bahasa pengaturcaraan adalah pengenalan dengan peraturan formal untuk menulis algoritma untuk pelaksanaan berikutnya oleh komputer.
7098.		Psikosomatik. Kursus kuliah	279KB
	Nota kuliah Psikosomatik Psikosomatik: definisi konsep. gejala penukaran. sindrom berfungsi. Psikosomatosis Patogenesis gangguan psikosomatik Teori dan model psikosomatik. Arah berorientasikan ciri...

Salah satu cara yang paling biasa untuk memproses isyarat satu dimensi dan pelbagai dimensi, termasuk imej, ialah transformasi ortogon. Peranan transformasi ortogon amat hebat dalam menyelesaikan masalah mengurangkan kadar penghantaran simbol binari dalam televisyen digital dan, akibatnya, mengurangkan lebar jalur komunikasi yang diperlukan. Intipati transformasi ortogon adalah untuk mewakili isyarat asal sebagai jumlah fungsi asas ortogon.

Ingat bahawa fungsi x(t) dan y(t) dipanggil ortogon pada selang (t 1 , t 2) jika ia produk skalar sifar

Takrifan ini boleh diperluaskan kepada isyarat diskret yang diwakili oleh jujukan nombor. Isyarat diskret x(n) dan y(n), mempunyai N sampel setiap satu, dipanggil ortogon jika keadaan

Salah satu yang paling contoh terkenal aplikasi penjelmaan ortogon ialah pengembangan isyarat berkala x dalam siri Fourier

Di mana: ; T - tempoh pengulangan isyarat x(t).

Pekali sebenar siri Fourier ditentukan oleh hubungan

DALAM bentuk kompleks pengembangan dalam siri Fourier mempunyai bentuk:

Amplitud kompleks harmonik;

j ialah unit khayalan.

Dalam siri Fourier, bukan sahaja isyarat berkala yang mempunyai tempoh T, tetapi juga isyarat yang berbeza daripada 0 sahaja dalam selang masa (-T/2, T/2) boleh diuraikan. Dalam kes ini, penerusan berkala isyarat pada keseluruhan paksi masa dengan tempoh T digunakan.

Pertimbangkan isyarat diskret x(n) berbeza daripada 0 pada n = 0.1, …, N-1. Untuk isyarat sedemikian, ia juga mungkin untuk memperkenalkan pengembangan dari segi asas fungsi sinusoidal. Oleh kerana spektrum frekuensi isyarat sampel mesti dibatasi dari atas mengikut keadaan teorem Kotelnikov, ia kekal dalam pengembangan isyarat diskret nombor terhingga komponen frekuensi, yang merupakan fungsi harmonik kompleks diskret. Pengembangan ini, yang dipanggil Discrete Fourier Transform (DFT), mempunyai bentuk

N=0, 1…N-1,(2.6)

di mana pekali DFT X(k) ditakrifkan oleh hubungan

K=0, 1…N-1,(2.7)

Ingat bahawa mencari pekali X(k) mengikut (2.7) biasanya dipanggil DFT langsung, dan mendapatkan isyarat daripada pekali ini mengikut (2.6) dipanggil DFT songsang.

Dalam hubungan ini, bukannya kamiran, jumlah muncul, kerana isyarat asal tidak berterusan, tetapi diskret. Kekerapan yang digunakan dalam penguraian isyarat analog dan mempunyai rad/s dimensi sepadan dengan nilai tanpa dimensi dalam DFT, di mana k=0, 1…N-1. Nisbah menunjukkan bahagian frekuensi pensampelan yang merupakan kekerapan harmonik diskret yang diberikan.

Pekali DFT X(k) dan faktor eksponen dalam (2.6), (2.7) ialah nombor kompleks. Setiap nombor kompleks disimpan dalam memori digital sebagai sepasang nombor nyata yang mewakili bahagian nyata dan khayalannya. Penambahan dua nombor kompleks memerlukan prestasi dua operasi penambahan nombor nyata - bahagian nyata dan khayalan ditambah secara berasingan. Pendaraban dua nombor kompleks memerlukan empat pendaraban dan dua penambahan nombor nyata. Oleh itu, pelaksanaan DFT dalam bentuk yang kompleks membawa kepada peningkatan yang ketara dalam jumlah memori dan masa pengiraan yang diperlukan.

Untuk berurusan sahaja nombor nyata, biasanya menggunakan pengembangan transformasi kosinus diskret (DCT), yang diterangkan oleh hubungan:

di mana pekali DCT ditentukan oleh formula

Seperti dalam kes DFT, mencari pekali C(k) dengan (2.9) dipanggil DCT langsung, dan perwakilan isyarat dalam bentuk (2.8) dipanggil DCT songsang.

Begitu juga, seseorang boleh menulis hubungan untuk DFT dan DCT langsung dan songsang dalam kes dua dimensi. Isyarat diskret dua dimensi, sebagai contoh, bingkai tunggal isyarat televisyen digital, diwakili oleh matriks nilai x(m, n), di mana m = 0 ... M-1 ialah nombor sampel dalam garisan, n = 0 .., N-1 ialah nombor baris dalam bingkai.

DFT dua dimensi langsung mempunyai bentuk:

k=0…M-1, l=0…N-1,

di mana X(k,l) ialah pekali DFT kompleks yang mewakili spektrum frekuensi spatial imej.

DFT dua dimensi songsang mewakili penguraian imej dari segi fungsi asas:

Pekali bagi DCT langsung dua dimensi ditentukan oleh formula:

DCT dua dimensi songsang mempunyai bentuk:

Kuantiti dan ialah frekuensi spatial diskret, dalam koordinat mendatar dan menegak, masing-masing, yang dinyatakan sebagai kuantiti tanpa dimensi yang mempunyai makna yang sama dengan frekuensi diskret dalam kes satu dimensi. Setiap frekuensi spatial diskret adalah berkadar dengan nisbah tempoh pensampelan spatial untuk koordinat tertentu kepada tempoh spatial komponen frekuensi ini. Tempoh spatial diukur dalam unit jarak.

Pada rajah. Rajah 2.3 menunjukkan fungsi asas DCT dua dimensi untuk M = 8, N = 8 sebagai gambar skala kelabu. Kawasan cahaya sepadan dengan nilai-nilai positif, manakala yang gelap adalah negatif.

nasi. 2.3.

Contoh yang ditunjukkan:

• a) k = 1, l = 0; b) k = 0, l = 1; c) k = 1, l = 1;
• d) k = 0, l = 2; e) k = 1, l = 2; f) k = 2 ,l = 2;
• g) k = 4, l = 2; h) k = 7, l = 1; i) k = 7, l = 7.

Sifat yang luar biasa bagi penguraian isyarat video dalam asas DCT ialah setiap fungsi asas mengandungi maklumat tentang keseluruhan imej sekaligus. Bilangan fungsi asas yang digunakan untuk menguraikan isyarat video menentukan ketepatan perwakilan imej.

Selaras dengan , secara amnya, adalah mungkin untuk menganggarkan kos sumber pengkomputeran apabila melaksanakan DFT langsung dan songsang, sebagai berkadar dengan N 2 . Begitu juga, boleh ditunjukkan bahawa pengiraan DFT hadapan dan songsang dua dimensi memerlukan beberapa operasi yang berkadar dengan N 2 M 2 .

Contohnya, mengira DFT untuk blok imej segi empat sama yang mengandungi unsur 8x8 (piksel) memerlukan kira-kira 16×10 3 pendaraban dan penambahan. Dan pengiraan DFT bingkai televisyen hitam-putih bagi piawaian penguraian konvensional yang mengandungi 720x576 piksel akan memerlukan kira-kira 8·10 11 operasi. Jika pengiraan dilakukan pada komputer yang melakukan 10 6 operasi pada nombor nyata sesaat, masa pengiraan DFT ialah 8 10 5 s atau lebih daripada 200 jam. Jelas sekali, untuk mengira DFT imej televisyen dalam masa nyata, i. , adalah perlu untuk mencari cara untuk mengurangkan bilangan operasi yang diperlukan.

Cara paling radikal untuk mengurangkan jumlah pengiraan ialah menggunakan algoritma DFT pantas yang ditemui pada tahun 60-an, dipanggil algoritma Fast Fourier Transform (FFT). Algoritma pantas untuk pengiraan DFT diterangkan secara terperinci dalam banyak sumber sastera dan tidak dipertimbangkan di sini.

FFT 2D boleh diuraikan menjadi urutan FFT 1D. Bilangan operasi yang diperlukan ternyata berkadar. Untuk contoh bingkai televisyen 720x576 piksel di atas, nilai ini ternyata lebih kurang 8·10 6 , iaitu 10 5 kali kurang daripada bilangan operasi yang diperlukan untuk mengira DFT secara langsung.

Terdapat juga algoritma pantas untuk mengira DCT. Seperti yang akan dilihat daripada yang berikut, dalam televisyen digital, peranan utama dimainkan oleh DCT blok 8x8 piksel, yang menggunakan algoritma untuk pengiraan pantas DCT satu dimensi bagi segmen isyarat digital yang mengandungi lapan elemen. Dalam kes ini, DCT pertama kali dikira untuk setiap lajur blok elemen imej, dan kemudian DCT dikira untuk setiap baris dalam matriks nombor 8x8 yang terhasil.

Dalam peralatan moden, termasuk yang untuk televisyen digital, DFT dan DCT biasanya dilakukan dalam masa nyata menggunakan pemproses isyarat digital (DSP) atau perkakasan khas, seperti peranti pengkomputeran selari.

DCT mendasari kaedah pengekodan yang paling banyak digunakan pada masa ini JPEG, MPEG-1, MPEG-2, yang akan diterangkan dalam Bahagian 2.2.