PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
TRANSFORMASI FOURIER DISKRIT DAN APLIKASINYA PADA KOMPRESI CITRA DIGITAL
Skripsi
Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika
Oleh: Ayu Sri Wulandari NIM: 103114004
PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2014
i
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DISCRETE FOURIER TRANSFORM AND ITS APPLICATION IN IMAGE DIGITAL COMPRESSION
Thesis Presented As a Partial Fulfillment of the Requirements to Obtain the Sarjana Sains Degree in Mathematics
By: Ayu Sri Wulandari Student Number: 103114004
MATHEMATICS STUDY PROGRAM, DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2014
ii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
SKRIPSI
TRANSFORMASI FOURIER DISKRIT DAN APLIKASII\TYA PADA KOMPRESI CITRA DIGITAL
-\
'.Y:d" Disusun oleh:
.*dftffiH"e O NI%$ffi114004
1$ffi3 :-effiS
';.,' ,r!
r;- *a
.\
I
-A,
Telah
oleh:
*t'be"'oocd fsetujui
ffif
, ^11
Pembimbing
Tanggal 26
( Dr.rer.nat. Herrj, Pribawanto S. )
111
Januan2}ll
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
SKRIPSI
TRANSFORMASI FOURIER DISKRIT DAN APLIKASINYA PADA KOMPRESI CITRA DIGITAL Dipersiapkan dan ditulis oleh:
Ayu Sri Wulandari
NIM: 103114004 Telah dipertahankan di depan Panitia Penguji pada tangg al 29
J
anuai
201 5
dan dinyatakan memenuhi syarat.
SUSUNAN PANITIA PENGUJI
t{rdutun *,
Nama Lengkap
Ketua
:
&rl ,fu-rt"L
k. Ig. Aris Dwiatmoko, M.Sc.
-
Sekretaris : Y. G. Hartono, Ph.D.
Anggota
:
Dr.rer.nat.Herry Pribawanto
S.
Yogyakarta,
2Z
Februari 2015
Fakultas Sains dan Teknologi
Universitas Sanata Dharma Dekan
f"#tX \'.
'-cvc.xo . Prima Rosa, S.Si,
1V
M.Sc. )
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
PERTTYATAAN KEASLIAN KARYA
Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis
ini
tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam kutipan dan daftar pustak4 sebagaimana layaknya karya ilmiah.
Yogyakarta, 26 J anuari 201 5
w
Penulis
I //'
Ayu Sri Wulandari
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
HALAMAN PERSEMBAHAN
“Don’t limit yourself, many people limit themselves to what they think they can do. You can go as far as your mind lets you. What you believe, remember, you can achieve.” - MARY KAY ASH -
Skripsi ini penulis persembahkan kepada: Tuhan Yesus Kristus dan Bunda Maria, Bapak Stefanus Wagiyo (alm) dan Ibu Ch. Sri Nursilowati, Kakak-kakak tersayang (Indah, Aris, Daniel), serta sahabat-sahabat yang selalu berada di sisi saya. Terima kasih atas semua dukungan yang diberikan.
vi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
LEMBAR PER}IYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAII T]NTUK KEPENTINGAN AKADEMIS Saya yang bertanda tangan di bawah
ini, mahasiswi Universitas Sanata Dharma:
Ayu Sri Wulandari
Nama
:
NIM
: 10 3114004
Demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul: Transformasi Fourier Dislcrit dan Aplikasinya pada Kompresi Citra Digital Beserta perangkat yang diperlukan (bila ada). Dengan demikian saya memberikan kepada Perpustakaan Universitas Sanata Dharma unutk menyimpan, mengalihkan
ke dalam bentuk media lain, mengelolanya dalam bentuk pangkalan
data,
mendistribusikan secara terbatas, dan mempublikasikannya di internet atau media
lain untuk kepentingan akademis tanpa perlu meminta ijin dari saya maupun memberikan royalti kepada saya selama tetap mencantumkan nama saya sebagai penulis.
Demikian pernyataan ini saya buat dengan sebenarnya. Dibuat di Yogyakarta Pada tanggal: 26 Januari 20 I 5
Yang menyatakan J
W1 T t-12 -tr-
t r'l
(Ayu Sri Wulandari)
v1l
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ABSTRAK
Tulisan ini membahas tentang Transformasi Fourier Diskrit (TFD) yang merupakan implementasi dari transformasi Fourier. Transformasi Fourier Diskrit mentransformasikan suatu fungsi pada domain ruang/waktu ke domain frekuensi. Transformasi Fourier Diskrit dapat digunakan dalam pemrosesan sinyal atau citra, seperti penyaringan sinyal, dekomposisi spektral, dan kompresi sinyal atau citra. Pada bagian akhir tulisan ini akan dibahas mengenai aplikasi transformasi Fourier diskrit pada kompresi citra digital, khususnya citra beraras keabu-abuan. Dalam bidang matematika, transformasi Fourier Diskrit mentransformasikan suatu vektor menjadi vektor yang lebih sederhana dan apabila diinverskan kembali vektor hasilnya serupa dengan vektor aslinya. Suatu nilai ambang batas mempunyai pengaruh besar dalam pemampatan data menggunakan transformasi Fourier Diskrit. Nilai ambang batas ini akan menentukan nilai-nilai frekuensi yang harus dianggap nol. Apabila nilai ambang batas semakin kecil (mendekati nol), maka hasil pemampatannya serupa dengan data aslinya. Kata kunci: Transformasi Fourier, Transformasi Fourier Diskrit, Kompresi, Sinyal, Citra Digital, Citra Beraras Keabu-abuan.
viii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ABSTRACT
This thesis discusses the Discrete Fourier transform (DFT), which is an implementation of the Fourier transform. Discrete Fourier Transform to transform a function on the domain space/time domain to the domain frequency. Discrete Fourier transform can be used in signal or image processing, such as signal filtering, spectral decomposition, and signal or data compression. In the final section of this thesis will discuss the application of the Discrete Fourier transform on the digital image compression, especially grayscale image. In mathematics, the Discrete Fourier transform to transform a vector into a vector that is more simple and if it is inversed back, it will have similar properties as the original one. A threshold value is significance to the data compression using Discrete Fourier transform. This threshold value will determine the frequency values that should be considered zero. If the threshold is getting smaller (close to zero), then the compression have similar properties as the original one. Key words: Fourier Transform, Discrete Fourier Transform, Compression, Signal, Digital Image, Grayscale Image.
ix
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
KATA PENGANTAR
Puji dan Syukur penulis haturkan kepada Tuhan Yesus atas segala cinta kasih-Nya yang melimpah sehingga penulis dapat menyelesaikan skripsi untuk memenuhi tugas akhir dalam menempuh gelar Sarjana (S1) di Universitas Sanata Dharma dengan lancar dan baik. Selama penulisan skripsi ini, penulis menyadari bahwa banyak pihak yang telah berperan besar dalam bimbingan, dukungan dan bantuannya bagi penulis untuk menyelesaikan skripsi ini. Oleh karena itu, penulis ingin mengucapkan terimakasih yang sebesar-besarnya kepada: 1.
Tuhan Yesus Kristus atas berkat dan penyertaan-Nya selama proses penulisan skripsi ini sehingga penulis dapat menyelesaikan skripsi ini dengan baik.
2.
Bapak Dr.rer.nat. Herry Pribawanto, M.Si., selaku dosen pembimbing skripsi yang telah membimbing, mendampingi, dan memberikan masukan kepada penulis selama proses penulisan skripsi ini.
3.
Bapak Y.G. Hartono, Ph.D., selaku Ketua Program Studi Matematika dan dosen pembimbing skripsi yang telah membimbing, mendampingi, dan memberikan masukan kepada penulis selama proses penulisan skripsi ini.
4.
Ibu Paulina H. Prima Rosa, S.Si., M.Sc., selaku Dekan Fakultas Sains dan Teknologi Universitas Sanata Dharma Yogyakarta.
5.
Bapak Ir. Ign. Aris Dwiatmoko, M.Sc., selaku Dosen Pembimbing Akademik
6.
Bapak, Ibu, dan Romo, dosen program studi Matematika yang senantiasa memberikan motivasi dan dukungan kepada penulis.
x
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
7.
Bapak Z. Tukija dan para staf sekretariat Fakultas Sains dan Teknologi lainnya yang telah banyak membantu dalam proses administrasi.
8.
Perpustakaan USD yang telah membantu menyediakan bahan dan fasilitas selama proses penulisan skripsi ini.
9.
Bapak Stephanus Wagiyo (alm) dan Ibu Ch. Sri Nursilowati, selaku orang tua penulis, kakak-kakakku tersayang Indah, Daniel dan Aris dan segenap keluarga atas segala doa dan dukungannya kepada penulis.
10. Sahabat-sahabat terdekatku, Happy adik almamaterku, dan teman-teman prodi Matematika terkhusus angkatan 2010: Arga, Celly, Astri, Agnes, Dini, Leny, Marsel, Pandu, Yosi, Roy, Ratri, Tika, Yohan, Sari; atas doa, semangat dan kebersamaan yang diberikan kepada penulis. 11. Semua pihak yang tidak dapat disebutkan satu per satu yang telah membantu dalam penyusunan skripsi ini. Penulis menyadari bahwa masih ada kekurangan dalam penulisan skripsi ini. Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun demi kesempurnaan skripsi ini.
Yogyakarta, 26 Januari 2015
Penulis
xi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR ISI
HALAMAN JUDUL ........................................................................................
i
HALAMAN PERSETUJUAN.......................................................................
iii
HALAMAN PENGESAHAN.........................................................................
iv
HALAMAN PERNYATAAN KEASLIAN TULISAN................................
v
HALAMAN PERSEMBAHAN......................................................................
vi
ABSTRAK.......................................................................................................
viii
ABSTRACT.....................................................................................................
ix
KATA PENGANTAR.....................................................................................
x
DAFTAR ISI....................................................................................................
xii
DAFTAR TABEL............................................................................................
xv
DAFTAR GAMBAR.......................................................................................
xvi
BAB I PENDAHULUAN................................................................................
1
1.1. Latar Belakang............................................................................................
1
1.2. Perumusan Masalah.....................................................................................
11
1.3. Pembatasan Masalah....................................................................................
11
1.4. Tujuan Penelitian.........................................................................................
11
1.5. Manfaat Penulisan.......................................................................................
12
1.6. Metode Penulisan........................................................................................
12
1.7. Sistematika Penulisan..................................................................................
12
BAB II LANDASAN TEORI..........................................................................
14
2.1. Aljabar Fungsi.............................................................................................
14
2.1.1. Periode Fungsi...................................................................................
14
2.1.2. Kekontinyuan Fungsi.........................................................................
14
xii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2.1.3. Turunan Fungsi..................................................................................
16
2.1.4. Fungsi Mulus.......................................................................................
17
2.1.5. Bilangan Kompleks............................................................................
18
2.1.6. Konjugat Kompleks............................................................................
18
2.1.7. Fungsi Eksponensial Kompleks.........................................................
19
2.2. Aljabar Matriks............................................................................................
20
2.2.1. Matriks Identitas...............................................................................
20
2.2.2. Invers Matriks....................................................................................
20
2.2.3. Matriks Simetris..................................................................................
22
2.2.4. Matriks Uniter...................................................................................
22
2.2.5. Ruang Hasilkali Dalam dan Norma...................................................
23
2.2.6. Ortogonalitas.....................................................................................
26
BAB III TRANSFORMASI FOURIER DISKRIT......................................
27
3.1. Deret Fourier...............................................................................................
27
3.2. Transformasi Fourier....................................................................................
37
3.2.1. Sifat-sifat Dasar Transformasi Fourier..............................................
41
3.3. Transformasi Fourier Diskrit.......................................................................
48
3.3.1. Definisi Transformasi Fourier Diskrit...............................................
49
3.3.2. Sifat-sifat Dasar Transformasi Fourier Diskrit...................................
68
3.3.3. Transformasi Fourier Diskrit 2 Dimensi............................................
74
3.3.4. Transformasi Fourier Diskrit pada Kompresi Sinyal..........................
84
BAB IV APLIKASI TRANSFORMASI FOURIER DISKRIT..................
88
4.1. Citra Diskrit.................................................................................................
88
4.2. Citra Beraras Keabu-abuan.........................................................................
88
4.3. Kompresi Citra Beraras Keabu-abuan..........................................................
89
xiii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB V PENUTUP...........................................................................................
96
5.1. Kesimpulan...................................................................................................
96
5.2. Saran............................................................................................................
97
DAFTAR PUSTAKA......................................................................................
98
LAMPIRAN.....................................................................................................
99
xiv
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR TABEL
Tabel 3.1.............................................................................................................
57
Tabel 3.2..............................................................................................................
58
Tabel 4.1.............................................................................................................
93
Tabel 4.2.............................................................................................................
94
xv
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR GAMBAR
Gambar 1.1.........................................................................................................
2
Gambar 1.2.........................................................................................................
2
Gambar 1.3.........................................................................................................
3
Gambar 1.4.........................................................................................................
4
Gambar 1.5.........................................................................................................
5
Gambar 1.6.........................................................................................................
6
Gambar 1.7.........................................................................................................
8
Gambar 1.8.........................................................................................................
8
Gambar 1.9.........................................................................................................
9
Gambar 1.10.......................................................................................................
9
Gambar 1.11........................................................................................................
10
Gambar 1.12........................................................................................................
10
Gambar 2.1.........................................................................................................
16
Gambar 2.2.........................................................................................................
18
Gambar 3.1.........................................................................................................
40
Gambar 3.2.........................................................................................................
48
Gambar 3.3.........................................................................................................
49
Gambar 3.4.........................................................................................................
58
Gambar 3.5.........................................................................................................
59
Gambar 3.6.........................................................................................................
75
Gambar 3.7.........................................................................................................
85
Gambar 3.8.........................................................................................................
86
Gambar 4.1.........................................................................................................
89
xvi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Gambar 4.2.........................................................................................................
90
Gambar 4.3.........................................................................................................
91
Gambar 4.4.........................................................................................................
92
Gambar 4.5.........................................................................................................
94
Gambar 4.6.........................................................................................................
95
xvii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB I PENDAHULUAN
1.1. Latar Belakang Masalah Citra merupakan suatu kombinasi antara titik-titik, garis, bidang dan warna untuk menciptakan sebuah tiruan dari obyek nyata. Citra dapat difungsikan sebagai suatu simbol untuk menyampaikan pesan antar manusia. Dalam kehidupan sehari-hari, citra hanya tampak dalam bentuk dua dimensi dan tiga dimensi. Citra dalam wujud dua dimensi dapat berupa suatu citra digital, sedangkan citra dalam wujud tiga dimensi dapat berupa patung atau ukiran. Citra digital merupakan gambar tiruan dari suatu obyek nyata yang diciptakan oleh perangkat optik seperti kamera, akan tetapi ukuran resolusi dari citra digital sangat besar sehingga akan berdampak dalam penyimpanan dan proses pengiriman gambar. Oleh karena itu, untuk menyelesaikan masalah tersebut perlu dilakukan minimisasi ukuran resolusi yang dikenal dengan kompresi. Kompresi atau pemampatan merupakan proses memadatkan ukuran resolusi suatu data untuk menghasilkan representasi digital yang padat atau mampat namun tetap dapat mewakili kuantitas informasi yang terkandung pada data tersebut. Pada citra digital, kompresi mengarah pada meminimisasi jumlah bit rate untuk representasi digital. Oleh karena itu, data asli yang telah dikompresi akan lebih efisien dalam penyimpanannya dan mempersingkat
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2
waktu dalam pertukaran ataupun pengirimannya. Berikut beberapa contoh citra asli dan hasil kompresinya:
Gambar 1.1. Citra asli berukuran 77,9 kilobyte (kiri). Citra terkompresi berukuran 19,11 kilobyte (kanan). (Sumber: https://old.ntchosting.com/multimedia/jpg-image-file-format.html)
Gambar 1.2. Citra asli (kiri) dan citra terkompresi (kanan). (Sumber: http://petapixel.com/2009/12/22/why-higher-iso-leads-to-largerfile-sizes)
Berdasarkan
kandungan
informasi
pada
citra
hasil
kompresi,
pemampatan/kompresi dikelompokkan menjadi dua, yaitu pemampatan tanpa kehilangan (lossless compression) dan pemampatan berkehilangan (lossy compression). 1.
Pemampatan tanpa kehilangan (lossless compression) adalah teknik pemampatan yang mampu memadatkan data sama persis seperti data semula. Maksudnya, tidak ada informasi yang hilang atau harus dikurangi dalam proses untuk mengurangi ukuran besar data. Contohnya,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
3
apabila berkas citra digital berukuran 256x256 berwarna polos (setiap pixel berwarna sama) dan tiap pixelnya berukuran 4 byte, tanpa pemadatan, berkas harus disimpan berukuran 4 kali 256x256, sama dengan 262144 byte. Namun, dengan pemadatan, maka data yang perlu disimpan hanya data satu warna tersebut. Jadi, data yang perlu disimpan hanyalah 4 byte ditambah beberapa byte untuk menandakan pengulangan pixel yang sama.
Gambar 1.3. Ilustrasi Lossless Compression JPEG 2000. Gambar asli (atas); Gambar terkompresi 1 berukuran 4990 kilobyte (kiri bawah); Gambar terkompresi 2 berukuran 4184 kilobyte (kanan bawah). (Sumber: http://www.steves-digicams.com/knowledge-center/whateverhappened-to-jpeg2000.html)
2.
Pemampatan
berkehilangan
(lossy
compression)
adalah
teknik
pemampatan dengan memangkas bagian-bagian data yang kurang penting supaya ukuran data bisa dikecilkan. Teknik kompresi ini paling sering digunakan untuk mengompres data multimedia. Teknik ini
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
4
menghasilkan ratio kompresi yang lebih besar daripada metode lossless. Misal terdapat citra digital asli berukuran 12,249 byte, kemudian dilakukan kompresi dengan JPEG kualitas 30 dan ukurannya menjadi 1,869 byte berarti citra digital tersebut 85% lebih kecil dan ratio kompresinya 15%. Contoh format gambar yang teknik kompresinya menggunakan lossy compression adalah JPEG.
Gambar 1.4. Ilustrasi Lossy Compression. Gambar asli berukuran 12 kilobyte (kiri); Gambar terkompresi 85% berukuran 1,8 kilobyte (tengah); Gambar terkompresi 96% berukuran 0.56 kilobyte (kanan). (Sumber:https://onramps.instructure.com/courses/1196409/pages/compressio n-algorithms)
Dari sudut pandang matematis, citra digital merupakan suatu array yang berisi nilai-nilai real maupun komplek yang direpresentasikan dengan deretan bit tertentu. Citra digital dapat didefinisikan sebagai fungsi f (x, y) berukuran M baris dan N kolom (M x N), dengan x dan y adalah koordinat spasial, dan amplitudo f di koordinat (x, y) dinamakan tingkat keabu-abuan dari citra pada titik tersebut (lihat Gambar 1.5) dengan nilai x,y dan f berhingga dan bernilai diskrit.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
5
Gambar 1.5. Koordinat citra digital.
Secara matematis, citra digital dapat dituliskan dalam bentuk matriks sebagai berikut:
f (0,0) f (1,0) f ( x, y ) f ( M 1,0)
f (0,1) f (1,1)
f ( M 1,1)
f (0, N 1) f (1, N 1) . f ( M 1, N 1)
Banyak metode yang dapat digunakan untuk melakukan kompresi, antara lain metode Huffman, RLE (Run Length Encoding), metode ShannonFano, kompresi citra berbasis transformasi, dan sebagainya. Dalam bidang matematika, salah satu teori yang dapat diterapkan untuk melakukan kompresi citra berbasis transformasi adalah Transformasi Fourier Diskrit. Dalam ilmu matematika, analisis Fourier berumur kurang lebih 200 tahun. Pada tahun 1807, Jean Baptiste Fourier mempresentasikan makalahnya tentang teori konduksi panas di Paris Academy. Pemaparan tersebut menjadi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
6
awal munculnya analisis Fourier. Terdapat dua masalah lain yang menjadi akar dari munculnya analisis Fourier. Masalah pertama adalah cara untuk mendeskripsikan getaran yang diciptakan oleh senar yang bergetar bila kedua ujungnya diikat dengan kencang. Masalah ini mengarah pada persamaan gelombang, seperti yang telah dirumuskan oleh matematikawan Jean d’Alembert, Leonhard Euler, Daniel Bernoulli, dan Joseph-Louis Lagrange. Matematikawan Bernoulli memberikan penyelesaian berbentuk deret trigonometri y A sin x cos at B sin 2 x cos 2at ...
dengan x adalah koordinat spasial dan t adalah variabel waktu. Penyelesaian yang diberikan oleh Bernoulli ini menyerupai bentuk kontinyu dari deret Fourier. Sedangkan, Euler dan Lagrange menDiskritisasi masalah getaran tersebut dengan menggambarkan bahwa senar tersebut terdiri dari partikelpartikel yang terbatas dan partikel-partikel tersebut saling terhubung (Gambar 1.6).
Gambar 1.6. Ilustrari getaran dari senar yang diDiskritisasi.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
7
Penyelesaian dari masalah Diskritisasi tersebut ialah dengan mencari sampelsampel dari fungsi yang menggambarkan pergerakan senar tersebut. Lagrange memberikan penyelesaian berbentuk jumlahan fungsi sinus dari berbagai frekuensi yang beragam. Penyelesaiannya ini merupakan dasar transformasi sinus Fourier Diskrit. Masalah kedua yaitu, menentukan orbit dari bendabenda langit. Euler, Lagrange dan Alexis Claude Clairaut membuat pemikiran dasar di mana data yang diambil dari pengamatan diaproksimasi dengan kombinasi linear dari fungsi periodik. Perhitungan koefisien dalam ekspansi trigonometri ini mengarah ke perhitungan yang kemudian akan disebut dengan transformasi Fourier Diskrit. Transformasi Fourier Diskrit dapat diterapkan untuk menganalisis data, dekomposisi spektral, penyaringan sinyal, pemrosesan citra (image processing), seperti kompresi citra, dan lain-lain. Sebagai contoh, pada penelitian terbaru mengenai Trapridge Glacier di daerah teritorial Yukon, Kanada. Pada penelitian tersebut, data yang digunakan berasal dari data yang dikumpulkan dengan sensor-sensor pada hamparan gletser, yang diletakkan 80 meter di bawah permukaan air. Secara khusus, pengukuran kekeruhan (jumlah bahan tersuspensi) air subglacial diambil setiap Δt = 10 menit 0,0069 hari. Bila diplot, data ini menghasilkan kurva bergerigi seperti yang ditunjukkan dalam Gambar 1.7 (waktu meningkat ke kanan dan nilai-nilai kekeruhan diplot pada sumbu vertikal).
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
8
tingkat kekeruhan t (hari) Gambar 1.7. Grafik dari data asli yang terdiri dari N = 368 data, pengukuran kekeruhan air diambil setiap Δt = 10 menit.
Grafik data asli di atas menunjukkan pola dan ketidakteraturan. Pada skala terbesar dari grafik terlihat suatu pola seperti gelombang dengan periodenya sekitar satu hari. Pada skala waktu yang lebih kecil, data tampaknya terinfeksi dengan osilasi frekuensi tinggi yang sebagian disebabkan karena derau. Kemudian, analisis data kekeruhan tersebut dengan mengurangkan setiap nilai dari data kekeruhan dengan rata-rata dari keseluruhan data kekeruhan.
data asli – rata-rata data
t Gambar 1.8. Grafik data yang setiap data asli dikurangkan dengan rata-rata datanya.
Nilai data yang muncul sebagai fluktuasi nilai rata-rata dari nol. Dengan kumpulan data yang disesuaikan, dari data tersebut dapat diperoleh dekomposisi spektral/frekuensinya dengan menggunakan konsep dari transformasi Fourier Diskrit. Hasilnya dapat dilihat pada Gambar 1.9.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
9
f Gambar 1.9. Grafik spektrum data setelah diterapkan transformasi Fourier Diskrit (sumbu horisontal merupakan frekuensi dan sumbu vertikal merupakan ukuran bobot relatif dari masing-masing frekuensi dalam struktur keseluruhan data kekeruhan). Dari grafik spektrum di atas terlihat bahwa sebagian besar ‘energi’ dalam data berada pada frekuensi yang lebih rendah.
f
Gambar 1.10. Perbesaran dari grafik spektrum data pada frekuensi rendah. Dari gambar 1.7 dapat dilihat bahwa dari data asli muncul ‘derau’. ‘Derau’ yang muncul karena kontribusi semua frekuensi tinggi dalam spektrum, sehingga untuk mengatasi ‘derau’ tersebut dilakukan penyaringan. Istilah dari penyaringan dapat digambarkan dengan sederhana, yaitu menghilangkan semua frekuensi yang tinggi pada spektrum di atas frekuensi yang dipilih.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
10
Spektrum baru yang terbentuk direkonstruksi dengan invers dari transformasi Fourier Diskrit, sehingga dapat dihasilkan data yang grafiknya lebih mulus dari data aslinya.
t Gambar 1.11. Grafik dari data asli setelah dilakukan penyaringan (dengan menghilangkan frekuensi di atas 50).
t Gambar 1.12. Grafik mulus dari data asli setelah dilakukan penyaringan (dengan menghilangkan frekuensi di atas 10).
Masalah di atas memberikan ilustrasi tentang penerapan transformasi Fourier Diskrit dalam dekomposisi spektral dan penyaringan sinyal. Dalam tulisan ini, penerapan transformasi Fourier Diskrit yang akan dibahas ialah penerapan transformasi Fourier Diskrit dalam pemrosesan citra, khususnya dalam kompresi pada citra digital
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
11
1.2. Perumusan Masalah Pokok permasalahan yang akan dibahas dalam tulisan ini dirumuskan sebagai berikut. 1.
Apa yang dimaksud dengan Transformasi Fourier Diskrit dan bagaimana landasan teoritisnya?
2.
Bagaimana penerapan Transformasi Fourier Diskrit pada kompresi citra digital?
3.
Bagaimana algoritma dan pemrograman MATLAB untuk kompresi citra digital dengan Transformasi Fourier Diskrit?
1.3. Pembatasan Masalah Penulis akan membatasi beberapa hal untuk uraian masalah yang akan dibahas, yaitu: 1.
Fungsi domain spasial pada citra digital yang akan dibahas dalam tulisan ini merupakan fungsi yang periodik.
2.
Tulisan ini hanya akan membahas penerapan transformasi Fourier Diskrit 2D.
3.
Penerapan transformasi Fourier Diskrit 2D hanya dibatasi pada citra digital beraras keabu-abuan.
1.4. Tujuan Penulisan Tujuan penulisan ini adalah mengetahui konsep deret Fourier, transformasi Fourier, transfromasi Fourier Diskrit dan penerapannya dalam kompresi citra digital. Sebagai tambahan, akan dipelajari juga bagaimana algoritma dan pemrogramannya dengan MATLAB. Tulisan ini juga disusun
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
12
sebagai pemenuhan tugas akhir dalam program studi Matematika Universitas Sanata Dharma. 1.5. Manfaat Penulisan Manfaat penulisan ini adalah memperoleh pengetahuan mengenai konsep transformasi Fourier Diskrit dan penerapannya dalam kompresi citra digital. Selain itu, dapat juga dibuat algoritma dan pemrograman MATLAB sehingga proses komputasi lebih efektif dan efisien. 1.6. Metode Penulisan Metode yang digunakan penulis adalah metode studi pustaka, yaitu dengan mempelajari buku-buku yang berkaitan dengan pengolahan citra, sinyal, transformasi Fourier Diskrit dan penerapannya dalam kompresi citra. 1.7. Sistematika Penulisan BAB I PENDAHULUAN 1.1. Latar Belakang 1.2. Rumusan Masalah 1.3. Batasan Masalah 1.4. Tujuan Penulisan 1.5. Manfaat Penulisan 1.6. Metode Penulisan 1.7. Sistematika Penulisan BAB II LANDASAN TEORI 2.1. Aljabar Fungsi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2.2. Aljabar Matriks BAB III TRANSFORMASI FOURIER DISKRIT 3.1. Deret Fourier 3.2. Transformasi Fourier 3.3. Transformasi Fourier Diskrit BAB IV APLIKASI TRANSFORMASI FOURIER DISKRIT BAB V PENUTUP 5.1. Kesimpulan 5.2. Saran DAFTAR PUSTAKA LAMPIRAN
13
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB II LANDASAN TEORI
2.1. Aljabar Fungsi 2.1.1. Periode Fungsi Definisi 2.1 Suatu fungsi f dikatakan periodik jika terdapat suatu bilangan positif
p sedemikian sehingga f x p f x untuk semua bilangan riil x di dalam daerah asal f . Bilangan p tersebut disebut periode f . Contoh 2.1 Fungsi f x sin x mempunyai periode 2 , sebab
f x 2 sin x 2 sin x cos 2 cos x sin 2 sin x , x ℝ .
2.1.2. Kekontinyuan Fungsi Definisi 2.2 Fungsi f x dikatakan kontinyu di suatu titik c , jika f c terdefinisi dan lim f x f c . xc
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
15
Definisi 2.3 Suatu fungsi
f
dikatakan kontinyu pada interval [a,b] jika fungsi
tersebut kontinyu di semua titik pada interval a, b dan jika
lim f ( x) f a
x a
dan lim f ( x) f b . x b
Fungsi f dikatakan kontinyu sepotong-sepotong pada [a,b] jika interval tersebut dapat dibagi menjadi subinterval berhingga dan pada setiap subinterval tersebut f kontinyu. Contoh 2.2 Misal, x 1 2 2 f ( x) x ln x 1 x 1 ln x 1 5
untuk - 1 x 0, untuk 0 x 1, untuk 1 x 2.
Fungsi f x merupakan fungsi kontinyu sepotong-sepotong karena fungsi tersebut kontinyu pada setiap subinterval 1, 0, 0,1 dan 1, 2 (lihat Gambar 2.1) .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Gambar 2.1. Grafik dari fungsi sepotong-sepotong interval 1, 2 .
16
f x pada
2.1.3. Turunan Fungsi Definisi 2.4 Turunan suatu fungsi f adalah fungsi lain f ' (dibaca “ f aksen”) yang nilainya di sebarang bilangan x adalah f ' x lim h 0
f x h f x h
asalkan limit ini ada dan bukan atau . Contoh 2.3 Jika f x x 3 7 x , maka f ' x lim h 0
f x h f x h
x h 7x h x 3
lim h 0
lim h 0
3
7x
h x 3 3x 2 h 3xh 2 h 3 7 x 7h x 3 7 x h
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
lim
3 x 2 h 3 xh 2 h 3 7 h h
lim
h 3 x 2 3 xh h 2 7 h
h 0
h 0
lim 3 x 2 3 xh h 2 7 h 0
17
3 x 2 7.
2.1.4. Fungsi Mulus Definisi 2.5 Suatu fungsi f dikatakan mulus pada suatu interval a, b jika f dan
f ' kontinyu pada interval tersebut. Contoh 2.4 Misal,
x 1 2 2 g ( x) x 2 ln x 1 2 x 1 ln x 1 5
untuk - 1 x 0, untuk 0 x 1, untuk 1 x 2,
dan 1 2 g ' ( x) 2 x ln x x 2x 1 ln x 1 x 1
untuk - 1 x 0, untuk 0 x 1, untuk 1 x 2.
Fungsi g x merupakan fungsi mulus sepotong-sepotong karena fungsi tersebut kontinyu sepotong-sepotong pada setiap subinterval
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1, 0, 0,1
dan
1, 2
18
dan fungsi turunan g' x juga kontinyu
sepotong-sepotong pada setiap subinterval tersebut.
Gambar 2.2. Grafik dari fungsi mulus sepotong-sepotong g x (kiri) dan g' x (kanan) pada interval 1, 2 .
2.1.5. Bilangan Kompleks Definisi 2.6 Jika z x i y menyatakan sembarang bilangan kompleks, maka
x Rez merupakan bagian riil dari z dan y Imz merupakan bagian imajiner dari z . Rez dan Imz merupakan bilangan riil.
2.1.6. Konjugat Kompleks Definisi 2.7 Untuk setiap bilangan kompleks z x i y , maka bilangan kompleks z xi y
disebut sebagai konjugat dari bilangan z .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Contoh 2.5 Misal, z 3 i 5 , maka konjugat kompleksnya adalah z 3 i5.
2.1.7. Fungsi Eksponensial Kompleks Definisi 2.8 Untuk bilangan kompleks z x i y didefinisikan e z e x cos y i sin y .
Jika diambil z i y , y ℝ, maka e z e iy cos y i sin y , untuk y ℝ,
yang dikenal juga dengan nama rumus Euler. Lemma 2.1 Untuk semua x, y ℝ berlaku 1. e i x2 e ix , 2. eix 1 , 3. eix e ix , 4. e ix e iy e i x y , 5. e ix / e iy e i x y , 6.
d ix e ie ix . dx
19
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
20
2.2. Aljabar Matriks 2.2.1. Matriks Identitas Definisi 2.9 Matriks persegi yang elemen diagonal utamanya bernilai 1 dan elemen lainnya 0 disebut sebagai matriks identitas. Matriks identitas dinotasikan dengan I ,
1 0 0 0 1 0 . I 0 0 1
2.2.2. Invers Matriks Definisi 2.10 Jika A merupakan matriks persegi, dan jika ada suatu matriks A1 dengan ukuran matriks yang sama dengan A sedemikian sehingga
AA1 A1 A I , maka A disebut sebagai matriks nonsingular (atau invertible), dan A1 disebut invers dari A . Contoh 2.6
2 5 3 5 Misal A dan A1 , maka 1 3 1 2 2 5 3 5 1 0 AA 1 I, 1 3 1 2 0 1 3 5 2 5 1 0 A1 A I. 1 2 1 3 0 1 Jadi, A merupakan matriks nonsingular.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
21
Teorema 2.1 Jika A adalah matriks invertible, dan jika B dan C merupakan invers dari
A , maka
B C ; yang berarti, suatu matriks invertible
mempunyai invers tunggal. Bukti: Karena B adalah invers dari A , kita punya BA I . Kemudian, kalikan kedua ruas dengan C , sehingga diperoleh
BAC IC BAC C. Karena C juga merupakan invers dari A , kita punya AC I . Sehingga, ruas kiri dari persamaan di atas dapat ditulis kembali sebagai
BAC B AC BI B , ini mengakibatkan B C . Teorema 2.2 Jika A dan B matriks invertible dengan ukuran matriks yang sama, maka AB invertible dan AB B 1 A1 . 1
Bukti:
Akan ditunjukkan: AB B 1 A1 B 1 A1 AB I .
AB B 1 A1 ABB 1 A1 AIA1 AA1 I ,
B
1
A1 AB B 1 A1 A B B 1 IB B 1 B I .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
22
2.2.3. Matriks Simetris Definisi 2.11 Matriks persegi A disebut matriks simetris jika
AT A .
Secara aljabar, suatu matriks A aij simetris jika dan hanya jika
Aij A ji
(atau aij a ji ).
Contoh 2.7
2 9 2 3 Misal, A , maka AT . 3 5 9 5
2.2.4. Matriks Uniter Definisi 2.12 Jika
A
merupakan matriks dengan elemen-elemennya berupa
bilangan kompleks (matriks kompleks), maka transpose konjugat dari A , dinotasikan dengan A* , didefinisikan oleh T
A* A . Contoh 2.8
i 0 1 i Misal, A , maka transpose konjugat dari A ialah 2 3 2i i
2 1 i A A i 3 2i . 0 i *
T
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
23
Definisi 2.13 Matriks kompleks persegi A dikatakan uniter jika
A1 A* atau atau A* A I .
2.2.5. Ruang Hasilkali Dalam dan Norma Definisi 2.14 Hasilkali dalam pada ruang vektor V adalah suatu operasi pada V yang memetakan setiap pasang vektor-vektor x dan y di dalam V dengan sebuah bilangan riil x, y yang memenuhi syarat berikut: i.
x, x 0 dengan x, x 0 jika hanya jika x 0 .
ii.
x, y y, x untuk semua x, y V .
iii.
x y, z x, z y, z untuk semua x, y, z V dan semua skalar dan .
Suatu ruang vektor V yang dilengkapi dengan hasilkali dalam disebut ruang hasilkali dalam. Definisi 2.15
x1 y1 x2 y2 Jika diberikan vektor x dan y , maka hasilkali dalam y x n n x dengan y pada ruang vektor ℝ𝑛 adalah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
x, y x T y x1
x2
24
y1 y xn 2 y n n
x1 y1 x 2 y 2 x n y n xi y i . i 1
Contoh 2.9 Jika
1 2 x dan y , 3 5 maka hasilkali dalam dari x dengan y pada ruang vektor ℝ2 adalah
2 x, y x T y 1 3 2 15 13 . 5 Definisi 2.16 a11 a1n b11 b1n Jika diberikan matriks A dan B , a b m1 a mn m1 bmn
maka hasilkali dalam dari A dan B pada ruang vektor ℝ𝑚 ×𝑛 adalah m
A, B i 1
n
a j 1
ij
bij .
Contoh 2.10 Jika
1 4 1 7 dan B , A 2 3 2 0 maka hasilkali dalam dari A dan B pada ruang vektor ℝ2×2 adalah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
25
1 4 1 7 1 28 4 0 33 . A, B 2 3 2 0 Definisi 2.17 Hasil kali dalam dari dua buah vektor
x x1 ,, xn dan
y y1 , , yn dengan xi , yi ℂ pada ruang vektor ℂ adalah n
x, y xi yi . i 1
Definisi 2.18 Hasilkali dalam dari dua fungsi f dan g di dalam ruang fungsi bernilai kompleks yang didefinisikan dalam interval a, b adalah b
f , g f x g x dx . a
Definisi 2.19 Suatu ruang vektor V dikatakan ruang linear bernorma jika untuk setiap vektor v V dikaitkan dengan suatu bilangan riil v yang disebut norma dari v yang memenuhi: 1.
v 0 dengan v 0 jika dan hanya jika v 0 ,
2.
v v untuk setiap skalar ,
3. v w v w (ketaksamaan segitiga) untuk semua v, w V .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
26
Definisi 2.20 Jika V suatu ruang hasilkali dalam, maka persamaan
v
v, v untuk semua v V ,
mendefinisikan suatu norma pada V . Contoh 2.11
1 Jika x , maka x 3
x, x 1 9 10 .
2.2.6. Ortogonalitas Definisi 2.21 Dua vektor x dan y di ℝ𝑛 dikatakan ortogonal jika dan hanya jika
x, y 0 . Contoh 2.12 Vektor-vektor
v1 1, 2, 2, 4 dan v 2 2, 1, 4, 2 merupakan dua vektor yang ortogonal di ℝ4 , sebab
v1 v 2 1 2 2 1 2 4 4 2 2 2 8 8 0 . Contoh 2.13 Fungsi
f t sin t dan g t cos t ortogonal di ruang fungsi
2 L2 , f : , R | f x dx sebab -
f , g sin t cost dt
1 1 sin 2t dt cos2t 0. 2 4
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB III TRANSFORMASI FOURIER DISKRIT
Pada bab ini, terdapat tiga subbab yang akan dibahas untuk memahami transformasi Fourier Diskrit, yaitu: Deret Fourier Transformasi Fourier Transformasi Fourier Diskrit 3.1. Deret Fourier Deret Fourier menguraikan suatu sinyal pada
,
ke dalam
komponen-komponen yang bergetar dengan frekuensi-frekuensi berupa bilangan bulat. Berikut akan dibahas mengenai definisi dari deret Fourier dalam bentuk kompleks dan riil. Definisi 3.1 Misal f merupakan suatu fungsi yang bersifat periodik dengan periode A ℝ.
Maka deret Fourier yang berasosiasi dengan f merupakan deret trigonometri
f ( x) ~
c e
k
i 2 kx A
k
dengan A
1 2 c k f ( x)e i 2 kx A dx . A A 2
(3.1)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
28
Simbol ~ berarti bahwa deret Fourier berasosiasi dengan fungsi f . Untuk membuat (3.1) lebih kuat, yaitu nilai ruas kiri dan kanannya sama di setiap titik, maka akan ditunjukkan bahwa nilai koefisien ck benar dan hal tersebut bergantung pada sifat ortogonalitas. Untuk menyatakan sifat ortogonalitas digunakan notasi yang disebut sebagai modular Kronecker delta. Definisi 3.2 Misalkan k bilangan bulat, kita definisikan ˆN k dengan
1
jika k 0 atau k kelipatan N ,
0
lainnya.
ˆN k Contoh 3.1
Jika diketahui N = 4 dan k = {-3, 0, 1,8}, maka modular Kronecker delta bernilai ˆ4 3 0, ˆ4 0 1, ˆ4 1 0, dan ˆ4 8 1. Teorema 3.1 (Ortogonalitas dari Fungsi Eksponensial Kompleks) i 2 kx Misal j dan k bilangan bulat. Maka fungsi eksponensial kompleks e
memenuhi A 2
e
i 2 jx A 2 i kx A
e
dx A ( j k ) .
A2
Bukti: Bila j – k = 0 ( j = k), maka ( j k ) 1 A 2
Akan dibuktikan:
e
A2
i 2 jx A 2 i kx A
e
dx A
A
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
A 2
e
i 2 jx A 2 i kx A
e
A2
A 2
dx e i 2
A j k x
dx
A2 A 2
A 2
e dx 1 dx x2 A A
0
A2
2
A2
A A 2A A 2 2 2
Bila j – k 0 ( j k), maka ( j k ) 0 A 2
Akan dibuktikan:
e
i 2 jx A 2 i kx A
e
dx 0
A2 A 2
e
A2
i 2 jx A 2 i kx A
e
A 2
dx ei 2
A j k x
dx
A2 A 2
2 j k x i sin 2 j k x dx cos A A A2 A 2
A 2
2 j k x dx i sin 2 j k x dx cos A A A2 A2 A
2 1 2 x 2 sin j k x 2 j k A A2 A A
2 1 2 2 j k x i x cos 2 j k A A2 A
29
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
30
A
2 A 2 j k x x 2 sin 2 j k A A 2
A
2 A 2 j k x i x 2 cos 2 j k A A 2
2 2 sin j k x A A2 A 2 x A 2 j k 2 2 i cos j k x A A2 A
A x 2 sin j k sin j k 2 j k 0 0 i cos j k cos j k
i
A x 2 cos j k cos j k 2 j k 0
0 Ortogonalitas pada kasus kontinyu juga dapat dipandang sebagai ortogonalitas dari vektor-vektor dalam suatu ruang fungsi yang didefinisikan dalam interval I. Di dalam ruang vektor L2 A 2 , A 2 fungsi-fungsi bernilai kompleks pada interval A 2 , A 2, fungsi-fungsi ω k ( x) e i 2 kx
bersifat ortogonal karena
A
, k ℤ
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
31
A 2
ω x ω x dx
ω j ,ωk
j
k
A2 A 2
e
i 2 jx A
e i 2 kx A dx
A2
A ( j k ).
Untuk mencari koefisien ck , diasumsikan bahwa fungsi f dengan periode A merupakan jumlahan dari deret Fourier, sehingga
f ( x)
c e
i 2 jx A
j
j
.
Kedua ruas persamaan ini dikalikan dengan 1 Ae i 2 kx
A
dan asumsikan
pengintegralan suku demi suku terhadap A 2 , A 2 diperbolehkan, A
A
1 2 f ( x) e i 2 kx A dx A A 2
1 2 A A
c
j
j
e i 2 j k x A dx
2
A
1 2 i 2 j k x A c dx j A A e j 2 j k
ck
Dengan sifat ortogonalitas, 1 A dikali integral bernilai nol kecuali saat j k . Satu-satunya suku yang tersisa dalam deret di ruas kanan bila j k ialah A
1 2 ck f ( x) e i 2 kx A dx. A A 2
Contoh 3.2 Perhatikan fungsi berikut
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 f x 1
jk 0 x jk x 0.
Tentukan deret Fourier dari f . Diketahui:
A , maka A 2 . 2
Maka koefisien dari deret Fouriernya adalah A
1 2 ck f x e i 2 k x A dx A A 2
1 2
e
i k x
dx
1 1 e i k x dx 2 0 2
1 e i k x 2 i k
0
0
e
ik x
dx
e i k x ik
0
e ik 1 1 e ik i k ik ik ik
1 2
1 2 2e ik 2 i k ik
2i 1 e ik i i 1 e ik i1 cosk k i i k k k 0
jika k ganjil jika k genap.
Sehingga deret Fourier dari f adalah
ck e i 2 kx
k
A
2i
2n 1 e
n
i 2 2 n 1 x 2
.
32
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
33
Definisi 3.3 Misal f adalah fungsi bernilai riil dengan periode A. Maka deret Fourier yang berasosiasi dengan f merupakan deret trigonometri f x ~
a0 2kx 2kx ak cos bk sin , 2 k 1 A k 1 A
dengan A
2 2 a0 f x dx, A A
(3.2)
2
A
2 2 2kx ak f x cos dx A A A
(3.3)
2
untuk k = 1, 2, ..., dan A
2 2 2kx bk f x sin dx A A A
(3.4)
2
untuk k = 1, 2, ... Contoh 3.3 Misal,
1 f x 0
jika 0 x 1, lainnya.
Hitung deret Fourier dari f pada interval 2 x 2 . Diketahui:
A 2 , maka A 4 . 2
Maka koefisien deret Fouriernya adalah 2
1
2 1 1 1 1 a0 f x dx 1 dx x 0 . 4 2 20 2 2
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
34
Untuk k 1 2 1 1 sin k 2 2 k x kx kx , ak f x cos sin dx cos dx 4 2 20 k 2 0 k 4 2 2
1
1
ketika k genap, sin k 2 0 maka ak 0 , sedangkan ketika k 2n 1 ganjil, sink 2 1n , sehingga kita peroleh
ak
n 1 , 2n 1
k 2n 1, n 0,1,... .
2 2 k x f x sin dx 4 2 4 2
bk
1
1 1 kx kx sin dx cos 20 2 k 2 0 1
cos k 2 1 k k
1 cosk 2 1, k
ketika k 4m , bk 0
1 ketika k 4m 1, bk 4m 1 dengan m 0,1,... . 1 ketika k 4m 2 , bk 2m 1 1 ketika k 4m 3 , bk 4m 3 Jadi, deret Fourier dari f adalah f x
a0 2kx 2kx a k cos bk sin 2 k 1 4 k 1 4
dengan an , bn yang diberikan di atas.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
35
Jika f merupakan suatu fungsi bernilai riil, bentuk riil dari deret Fourier dapat diturunkan dari bentuk kompleksnya dan sebaliknya. Pertama, uraikan bentuk kompleks deret Fourier ke dalam suku-suku positif dan negatif: f x ~
ck ei 2 kx
A
k
1
ck ei 2 kx A c0e0 ck ei 2 kx
k
A
k 1
1
ck ei 2 kx A c0 ck ei 2 kx
k
A
.
(3.5)
k 1
Jika f merupakan fungsi bernilai riil, maka ck ck karena A
c k
A
1 2 f x ei 2 kx A A
A
2
1 2 dx f x e i 2 kx A A
A
dx ck .
2
Oleh karena itu, (3.5) menjadi
k 1
k 1
f x ~ c0 ck ei 2 kx A ck ei 2 kx A . Karena z z 2 Rez untuk setiap z ℂ, persamaan ini dapat ditulis sebagai
f x ~ c0 2 Re ck ei 2 kx A . k 1
(3.6)
Hubungan antara ck dan ak , bk dapat diturunkan dengan menggunakan rumus Euler, sehingga diperoleh: A
A
a 1 2 1 2 c0 f x e 0 dx f x dx 0 . A A A A 2 2
2
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
36
A
1 2 ck f ( x) e i 2 kx A dx A A 2
2kx 1 2 2kx f ( x) cos i sin dx A A A A 2 A
2 12 2kx 2kx f ( x) cos dx i f ( x) sin dx A A A A A 2 2 A
A
A bk 1 A ak i A 2 2
1A 1 ak ibk ak ibk , A 2 2
untuk k 1.
Dengan menggunakan persamaan (3.6), kita peroleh f x ~ c0 2 Re ck e i 2 kx A k 1
a ibk a0 2 Re k 2 k 1 2
2kx 2kx cos i sin A A
a0 2kx 2kx 2kx 2kx Re ak cos bk sin i ak sin bk cos 2 k 1 A A A A
a0 2kx 2kx ak cos bk sin 2 k 1 A A
a0 2kx 2kx ak cos bk sin , 2 k 1 A k 1 A
yang merupakan bentuk riil dari deret Fourier f . Selanjutnya akan ditunjukkan kekonvergenan dari deret Fourier. Sebelum membahas hal tersebut, kita berikan definisi berikut.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
37
Definisi 3.4 Limit kiri dan kanan dari f di titik x didefinisikan sebagai berikut. Limit kiri
: f x 0 lim f x h . h0
Limit kanan: f x 0 lim f x h . h0
Fungsi f dikatakan terdiferensial kiri dan kanan di x jika limitnya ada: f ' x 0 lim h 0
f x h f x f x h f x dan f ' x 0 lim . h 0 h h
Teorema 3.2. (Kekonvergenan Deret Fourier) Misal f merupakan fungsi yang periodik dan kontinyu sepotong-sepotong. Jika x adalah titik di mana f terdiferensial kiri dan kanan (tetapi tidak kontinyu). maka deret Fourier dari f di x konvergen ke f x 0 f x 0 . 2
Bukti: Bukti dapat dilihat pada buku Albert Boggess: A First Course in Wavelets with Fourier Analysis, hal.70, tahun 2001 . Pada subbab selanjutnya akan dibahas mengenai transformasi Fourier.
3.2. Transformasi Fourier Transformasi Fourier merupakan bentuk kontinyu dari deret Fourier. Transformasi Fourier menguraikan suatu sinyal yang terdefinisi pada sebuah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
38
interval waktu yang tak berhingga ke dalam suatu komponen dengan frekuensi , di mana merupakan bilangan riil atau kompleks. Definisi 3.5 Diberikan fungsi f terdefinisi dalam interval (-,) dan mempunyai sifat,
f x dx ,
(3.7)
maka fˆ dengan fˆ
f x e
i 2 x
dx ,
(3.8)
fˆ disebut Transformasi Fourier dari f dan
f x
fˆ e
i 2 x
d ,
(3.9)
disebut sebagai invers Transformasi Fourier fˆ ( dan i 1 merupakan satuan imajiner). Contoh 3.4 Diberikan fungsi f x e
x Diketahui: x x Jadi,
x
. Tunjukkan fungsi tersebut memenuhi (3.7).
,x 0 ,x 0
, maka f x e
x
x e x e
,x 0 ,x 0
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
e
x
dx e
x
39
dx
0
0
x x e dx e dx
ex
0
ex
0
(e 0 e ) (e e 0 ) (1 0) (0 1) 2
Selain fungsi pada Contoh 3.4, terdapat fungsi-fungsi lainnya yang mempunyai sifat tersebut, misal, fungsi kepadatan peluang, fungsi probabilitas kontinyu, dan sebagainya. Dari sifat fungsi f , maka fungsi fˆ juga memenuhi (3.7), berarti fˆ terdefinisi dengan baik pada (-,).
fˆ
f x e
i 2 x
dx
fˆ
f x e
i 2 x
dx
f x e
i 2 x
dx
sifat ketaksamaan segitiga
untuk integral
f x e
i 2 x
dx
f x dx .
e
i 2 x
1
Fungsi output transformasi fˆ didefinisikan pada domain frekuensi atau domain transformasi, sedangkan fungsi input f didefinisikan pada
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
40
domain spasial jika x merupakan koordinat spasial, atau dalam domain waktu jika f adalah fungsi yang bergantung pada waktu spasial. Contoh 3.5 Misal, f x 1 pada interval x . Maka transformasi Fourier dari f adalah fˆ
f x e
i 2 x
dx
e
i 2 x
1 dx e i 2 x i 2
2 2 1 e i 2 e i 2 i 2
1 cos 2 2 i sin 2 2 cos 2 2 i sin 2 2 i 2
1 sin 2 2 i 2 sin 2 2 . i 2
Gambar 3.1. Grafik fungsi f pada interval , (kiri) dan fungsi fˆ pada interval , (kanan).
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
41
Selanjutnya akan dibahas mengenai sifat-sifat dasar dari transformasi Fourier. 3.2.1. Sifat-sifat Dasar Transformasi Fourier Untuk membahas sifat-sifat dasar transformasi Fourier akan digunakan notasi alternatif ℱ f fˆ , dengan ℱ menyatakan transformasi Fourier dari f . Operator Fourier ℱ dianggap sebagai pemetaan yang domain dan rangenya merupakan ruang fungsi bernilai kompleks yang didefinisikan pada garis bilangan riil. Input dari ℱ adalah sebuah fungsi, katakanlah f , dan menghasilkan output berupa fungsi lain, ℱ f fˆ . Sedangkan, invers dari transformasi Fourier menggunakan notasi operator sebagai berikut
ℱ −1 fˆ x f x . Teorema 3.3 Misalkan f dan g merupakan fungsi terdiferensial yang terdefinisi pada garis bilangan riil dengan f x 0 untuk x yang semakin membesar
lim f x 0 . x 1. Transformasi Fourier dan inversnya bersifat linear, artinya untuk sebarang konstanta c ℱ f g ℱ f + ℱ g dan ℱ cf c ℱ f .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
42
ℱ −1 fˆ gˆ ℱ −1 fˆ + ℱ −1 gˆ dan ℱ −1 cfˆ c ℱ −1 fˆ . 2. Transformasi Fourier dari suatu hasilkali f dengan x n diberikan oleh
dn ℱ x f x i ℱ f . d n n
n
3. Invers transformasi Fourier dari suatu hasilkali f dengan n diberikan oleh
n n d ℱ −1 n fˆ x i ℱ −1 fˆ x . dx n
4. Transformasi Fourier dari suatu turunan ke- n diberikan oleh
ℱ f n i 2 ℱ f n
( f n menyatakan turunan ke- n dari f ). 5. Invers transformasi Fourier dari suatu turunan ke- n diberikan oleh
n ℱ −1 fˆ n x i 2 x ℱ −1 fˆ x .
6. Transformasi Fourier dari suatu translasi diberikan oleh ℱ f x a e i a ℱ f . 7. Transformasi Fourier dari suatu rescaling diberikan oleh ℱ f bx
1 ℱ f . b b
8. Jika f x 0 untuk x 0 , maka ℱ f ℒ f i 2 , dengan ℒ f merupakan transformasi Laplace dari f yang didefinisikan oleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
43
ℒ f s f x e xs dx . 0
Bukti: 1. Sifat linear dari transformasi Fourier diperoleh dari sifat linear integral:
ℱ f g =
f x g x e
i 2 x
dx
f x e i 2 x dx
=
g x e
i 2 x
dx
= ℱ f ℱ g . ℱ cf =
cf x e
i 2 x
dx
= c f x e i 2 x dx
= c ℱ f .
fˆ gˆ e
ℱ −1 fˆ gˆ x =
i 2 x
d
=
fˆ ei 2 x d
gˆ e
= ℱ −1 f x ℱ −1 g x . ℱ
−1
cfˆ x =
cfˆ e
i 2 x
d
= c fˆ ei 2 x d
i 2 x
d
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
44
= c ℱ −1 f x . 2. Transformasi Fourier dari suatu hasil kali f dengan x n , kita punya
ℱ x n f x
x f x e n
i 2 x
dx .
Gunakan persamaan
x n f x e i 2 x i
n
dn f x e i 2 x , n d
sehingga kita memperoleh
ℱ x n f x i
n
i
n
dn f x e i 2 x dx n d
dn ℱ f . d n
3. Invers transformasi Fourier dari suatu hasil kali f dengan n , kita punya
ℱ −1 n fˆ n fˆ e i 2 x d .
Gunakan persamaan
n fˆ e i 2 x i n
dn ˆ f e i 2 x , n dx
sehingga kita memperoleh
n ˆ n d ℱ −1 n fˆ x i f e i 2 x d n dx
i
n
dn ℱ −1 fˆ x . n dx
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
45
4. Transformasi Fourier dari turunan ke- n f , kita punya
ℱ f n x
f n x e i 2 x dx .
Kemudian integralkan menggunakan rumus integral parsial; yaitu,
u dv u v
Dengan
dv f n x dx
dan
v du .
u e i 2 x , maka
v f n1 x
dan
du i 2 e i 2 x dx , maka diperoleh
f n x e i 2 x dx e i 2 x f n1 x
i 2 f n1 x e i 2 x dx .
Karena f x 0 untuk nilai x yang besar maka kita peroleh
f
n
x e
i 2 x
dx i 2 f n1 x e i 2 x dx .
Catatan: Integral parsial mereduksi banyaknya turunan f satu demi satu ( f n menjadi f n1 ). Kita juga memperoleh faktor i 2 . Dengan mengulang proses tersebut n 1 kali, kita memproleh
f n x e i 2 x dx i 2
n
f x e
i 2 x
dx
i 2 ℱ f . n
5. Invers transformasi Fourier dari turunan ke- n fˆ , kita punya ℱ
−1
fˆ n x
fˆ n ei 2 x d .
Kemudian integralkan menggunakan rumus integral parsial; yaitu,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
u dv u v
Dengan
dv fˆ n d
v du
.
u ei 2 x , maka
dan
46
v fˆ n1 dan
du i 2 x ei2 x d , maka diperoleh
fˆ n ei 2 x d ei 2 x fˆ n1
i 2 x fˆ n1 ei 2 x d .
Karena f x 0 untuk nilai x yang besar maka kita peroleh
fˆ n ei 2 x d i 2 x fˆ n1 ei 2 x d .
Catatan: Integral parsial mereduksi banyaknya turunan f satu demi satu ( f n menjadi f n1 ). Kita juga memperoleh faktor i 2 x . Dengan mengulang proses tersebut n 1 kali, kita memperoleh
n fˆ n ei 2 x d i 2 x
fˆ e
i 2 x
d
n i 2 x ℱ −1 fˆ x .
6. Dengan menggunakan definisi transformasi Fourier, kita mempunyai
ℱ f x a
f x a e
i 2 x
dx .
Misal, s x a , sehingga x s a dan dx ds . Kita peroleh ℱ f s
f s e
i 2 s a
ds
f s e
i 2 s
e i 2 a ds
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
f s e
e i 2 a
i 2 s
47
ds
.
e i 2 a ℱ f
7. Dengan menggunakan definisi transformasi Fourier, kita mempunyai ℱ f bx
f bx e
i 2 x
dx .
Misal, t bx , sehingga x
t dt dan dx . Kita peroleh b b
ℱ f t
f t e
t i 2 b
f t e
i 2 t b
dt b
dt b
i 2 t 1 f t e b dt b
1 ℱ f . b b
8. Diketahui: f x 0 untuk x 0 , kita peroleh
ℱ f
f x e
i 2 x
dx
0
f x e
dx f x e i 2 x dx 0 i 2 x
0
f x e i 2 x dx 0
Misal, s i 2 , maka dengan definisi transformasi Laplace diperoleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
48
ℱ f f x e sx dx ℒ f s = ℒ f i 2 . 0
Dengan pengetahuan tentang deret Fourier dan transformasi Fourier pada subbab sebelumnya, selanjutnya akan dibahas mengenai transformasi Fourier Diskrit yang merupakan topik utama dari tulisan ini.
3.3. Transformasi Fourier Diskrit Transformasi Fourier dan deret Fourier digunakan untuk menganalisis sinyal-sinyal kontinyu seperti grafik pada Gambar 3.2. Tetapi, sinyal-sinyal yang ada dalam kebanyakan aplikasi saat ini merupakan sinyal Diskrit, Gambar 3.3, seperti sinyal yang berasal dari pemutar CD/DVD.
Gambar 3.2. Sinyal Kontinu
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
49
Gambar 3.3. Sinyal Diskrit
Berikut definisi dari transformasi Fourier Diskrit. 3.3.1. Definisi Transformasi Fourier Diskrit Berdasarkan pada Definisi 3.5, diasumsikan fungsi yang diberikan itu terbatas (misalnya, f mungkin mewakili gambar yang memiliki batasbatas yang terdefinisi dengan baik) atau, f diasumsikan nol di luar beberapa interval terbatas. Maka, untuk saat ini diasumsikan bahwa f x 0 untuk
x A 2 , A banyaknya grid. Transformasi Fourier pada fungsi dengan batas tertentu tersebut diberikan oleh
fˆ
f x e
i 2 x
dx
A 2
f x e
i 2 x
dx
(3.10)
A2
Integral tersebut yang akan diaproksimasi secara numerik. Interval integrasi
A 2 , A 2
dibagi menjadi N subinterval
dengan panjang x A N . Diasumsikan N genap, dengan banyaknya grid N+1 sama dengan banyaknya titik yang didefinisikan oleh titik-titik
xn nx untuk n N 2 : N 2 . Dengan demikian titik-titik gridnya ialah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
x N 2
50
A A , , x0 0, , x N . 2 2 2
Kemudian, diasumsikan bahwa fungsi f terdefinisi pada titik-titik grid tersebut. Integran dari persamaan (3.10) sebagai
g x f x e i 2 x , dan terapkan aturan trapesium untuk mengaproksimasi integral (3.10):
x A g x dx g 2 A 2 2 2 A 2
N 1 2
n N2 1
A g xn g . 2
Diasumsikan g A 2 g A 2 , sehingga aproksimasi aturan trapesium dapat ditulis A 2
fˆ g x dx
x
N 2
g xn
n N2 1
A2
A N
N 2
f xn e i 2 xn .
n N2 1
Aproksimasi dari fˆ dapat dihitung untuk setiap . Karena aproksimasi fˆ bergantung pada nilai , maka harus ditentukan banyaknya nilai yang digunakan untuk aproksimasi dan yang mana saja nilai-nilai tersebut.
Dibutuhkan
aproksimasi
nilai-nilai
sampel
f xn
untuk
menentukan
fˆ ( ) , dan sebaliknya. Karena N nilai dari f xn digunakan
dalam aproksimasi aturan trapesium, maka ada N nilai juga untuk pada aproksimasi fˆ ( ) .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
51
Hubungan Kebalikan
A N dan x
1 N
(3.11)
Hubungan kebalikan mengaitkan antara domain spasial dan domain frekuensi. Dua hubungan kebalikan ini saling bergantung (dependent). Pada domain spasial dengan interval
A / 2, A / 2
titik-titik grid dinyatakan
dengan xn nx dan jarak antar titik gridnya Δx. Sedangkan pada domain frekuensi dengan interval / 2, / 2 titik-titik grid dinyatakan dengan
k k dan jarak antar titik gridnya Δ. Diasumsikan terdapat N titik pada kedua domain tersebut. Andaikan semua modus (sinus dan kosinus) memiliki periode bulat pada
A / 2, A / 2. Gelombang dengan periode terbesar (satu periode penuh pada A / 2, A / 2) disebut sebagai modus dasar. Gelombang ini juga memiliki frekuensi 1/A periode per satuan panjang. Frekuensi ini merupakan frekuensi terendah pada A / 2, A / 2 dan dinotasikan dengan
1 , A
dan ini akan menjadi jarak antar titik grid pada domain frekuensi. Karena terdapat N titik grid pada domain frekuensi / 2, / 2 dengan jarak antar titik grid Δ, sama halnya pada domain spasial di mana A Nx , maka pada domain frekuensi
N.
Dengan mengkombinasikan dua
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
pernyataan,
52
1 dan N , maka diperoleh hubungan kebalikan A
yang pertama, yaitu N
N atau A N . A
Hubungan kebalikan yang pertama ini menyatakan bahwa jarak interval pada domain spasial berbanding terbalik dengan jarak interval pada domain frekuensi. Dengan kata lain, jika A bertambah, ini mengakibatkan periode pada domain spasial bertambah panjang dan frekuensi Δ menurun, bila Δ menurun maka jarak interval pada domain frekuensi juga menurun. Telah diketahui bahwa pada domain spasial A / 2, A / 2 dibagi menjadi N subinterval grid dengan jarak antar grid Δx dan A Nx . Dengan mengkombinasikan dua pernyataan,
1 dan A Nx , maka A
diperoleh hubungan kebalikan yang kedua, yaitu 1 1 A Nx atau x . N
Hubungan kebalikan yang kedua ini menyatakan bahwa jarak antar titik-titik grid pada kedua domain berbanding terbalik. Dengan hubungan kebalikan, aturan aproksimasi trapesium sebelumnya dapat diselesaikan dengan langkah yang lebih singkat. Misalkan
f n untuk menotasikan nilai-nilai sampel f xn untuk n N 2 1: N 2 . Untuk mengakprosimasi fˆ pada titik-titik grid frekuensi k k k A ,
xn k disederhanakan menjadi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
xnk nx k
53
nA k nk . N A N
Sehingga, jumlahan dalam aturan trapesium menjadi
fˆ k
N 2
A N
fn e
i 2 k xn
n N2 1
N 2
A N
f n e i 2 n k N .
n N2 1
Oleh karena itu, aproksimasi transformasi Fourier fˆ pada titik-titik grid frekuensi k k A diberikan oleh k fˆ k fˆ A
A 2
f x e
N
i 2 k x N
A2
2 1 A f n e i 2 n k N , (3.12) N n N2 1
Fk
untuk k N 2 1 : N 2 . Fk
pada (3.12) merupakan definisi dari
transformasi Fourier Diskrit. Bila diberikan N nilai sampel f n , maka transformasi Fourier Diskrit memuat N koefisien
1 Fk N
N 2
n N2 1
f n e i 2 n k
N
(3.13)
untuk k N 2 1 : N 2 . Dari hasil aproksimasi dengan aturan trapesium (3.7), dapat disimpulkan bahwa aproksimasi untuk transformasi Fourier
fˆ k diberikan oleh fˆ k AFk . Untuk mempermudah penulisan (3.13), dimisalkan, 2 2 i sin , N N
N e i 2 / N cos sehingga
Nnk e i 2 / N
nk
e i 2 n k / N dan Nnk e i 2 / N e i 2 n k / N . nk
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
54
Definisi 3.6 Misal N bilangan bulat genap positif dan f n barisan N bilangan kompleks dengan n N 2 1 : N 2 , maka bentuk transformasi Fourier Diskritnya adalah 1 Fk N
N 2
n N2 1
f n Nnk
(3.14)
untuk k N 2 1 : N 2 . Misal N bilangan bulat ganjil positif dan f n barisan N bilangan kompleks dengan
n N 1 2 : N 1 2 , maka bentuk transformasi Fourier
Diskritnya adalah 1 Fk N
N 1 2
n N21
f n Nnk
(3.15)
untuk k N 1 2 : N 1 2 . Untuk mendefinisikan transformasi Fourier Diskrit dari barisan f n akan digunakan notasi 𝒟{𝑓𝑛 }, dan 𝒟{𝑓𝑛 }𝑘 untuk menunjukkan elemen transformasi ke k, sehingga 𝒟{𝑓𝑛 }𝑘 = 𝐹𝑘 . Terdapat banyak bentuk alternatif untuk mendefinisikan transformasi Fourier Diskrit. Misalnya, bila input TFD merupakan barisan yang bergantung pada waktu akan lebih mudah menggunakan indeks 0 : N 1 . Untuk penerapan lainnya (domain spasial), seperti rekonstruksi citra dari proyeksi, akan lebih mudah untuk menempatkan titik asal di tengah ruang gambar, yang mengarah ke Definisi 3.6.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
55
Definisi 3.7 Misal N bilangan bulat positif dan f n barisan N bilangan kompleks dengan n 0 : N 1, maka bentuk transformasi Fourier Diskritnya adalah 1 N
Fk
N 1
f n N nk
n0
(3.16)
untuk k 0 : N 1 . Bentuk alternatif TFD (3.16) setara dengan bentuk TFD (3.14). Salah satu keuntungan dari Definisi 3.7 adalah bahwa rumus tersebut tidak bergantung pada genap/ganjilnya N . Secara umum, output dari transformasi Fourier Diskrit, Fk , adalah barisan bernilai kompleks dan juga merupakan barisan dengan periode N yang memenuhi Fk Fk N , N Fk N n2 N 1 1 2 N 1 N 1 N
N
N 2
n
N 1 2
2 n( k N ) fn N N n 1 2
N
N 2
n
N 1 2
2 nk nN fn N N n 1 2
N
N 2
n
N 1 2
2 f n N nk N nN N n 1 2
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 N 1 N 1 N
56
N
N 2
n
N 1 2
2 f n Nnk e i 2n N n 1 2
N
N 2
n
N 1 2
2 nk f n N 1 N n 1 2
N
N 2
N n 1 2
2 N f n Nnk Fk 2 N n 1 2 N n 1
.
2
Dari rumus TFD dapat ditentukan bagian riil dan imajinernya. Bagian riil dinotasikan dengan ReFk dan bagian imajiner dinotasikan dengan ImFk . Notasi tersebut juga digunakan untuk menunjukkan bagian riil dan
imajiner dari input barisan
f n , yaitu Re f n dan Im f n , sehingga
diperoleh Fk sebagai berikut: 1 Fk N
1 N
1 N
N 2
n
f n Nnk
N 1 2
N 2
Re f i Im f e n
n
i 2 n k / N
n
N 1 2
N 2
2 n k 2 n k Re f i Im f cos N i sin N n
n
N 1 2
n
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 N
N 2
2 n k 2 n k Re f n cos Im f n sin N N
n
57
N 1 2
2 n k 2 n k i Im f n cos Re f n sin N N
1 N
i N
N 2
2 n k 2 n k Re f n cos Im f n sin N N
n
N 1 2
N 2
n
N 1 2
2 n k 2 n k Im f n cos Re f n sin . N N
Oleh karena itu, bagian riil dan imajiner dari Fk didefinisikan sebagai berikut. Bentuk Riil dan Imajiner Transformasi Fourier Diskrit ReFk
ImFk
1 N 1 N
N 2
n
N 1 2
N 2
n
N 1 2
2 n k 2 n k Re f n cos Im f n sin N N 2 n k 2 n k Im f n cos Re f n sin N N
Contoh 3.6 Perhatikan 12 titik barisan bernilai riil f n yang diberikan dalam Tabel 3.1. n,k -5 -4 -3 -2 -1 0 1
Re{ f n } 0.7630 -0.1205 -0.0649 0.6133 -0.2697 -0.7216 -0.0993
Im{ f n } 0 0 0 0 0 0 0
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2 3 4 5 6
0.9787 -0.5689 -0.1080 -0.3685 0.0293
58
0 0 0 0 0
Tabel 3.1. 12 titik numerik bernilai riil dari f n 1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
-0.2
-0.2
-0.4
-0.4
-0.6
-0.6
-0.8
-0.8
-1
-1
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
Gambar 3.4. Bagian riil (kiri) dan bagian imajiner (kanan) dari 12 titik input barisan f n .
Maka transformasi Fourier Diskrit dari barisan bernilai riil f n adalah: Fk
1 6 f n 12nk , 12 n 5
untuk k 5 : 6 . Transformasi Fourier Diskrit dari barisan bernilai riil f n juga terdiri dari 12 titik barisan Fk yang diberikan dalam Tabel 3.2. n,k -5 -4 -3 -2 -1 0 1 2
Re{ Fk } 0.0684 -0.1684 -0.2143 -0.0606 -0.0418 0.0052 -0.0418 -0.0606
Im{ Fk } -0.1093 0.0685 -0.0381 0.1194 -0.0548 0 0.0548 -0.1194
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
59
3 -0.2143 0.0381 4 -0.1684 -0.0685 5 0.0684 0.1093 6 0.1066 0.0000 Tabel 3.2. 12 titik numerik transformasi Fourier Diskrit barisan f n . 0.2
0.2
0.15
0.15
0.1
0.1
0.05
0.05
0
0
-0.05
-0.05
-0.1
-0.1
-0.15
-0.15
-0.2
-0.2 -5
-4
-3
-2
-1
0
1
2
3
4
5
6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
Gambar 3.5. Bagian riil (kiri) dan bagian imajiner (kanan) dari Fk .
Transformasi Fourier Diskrit digunakan karena terdapat suatu masalah yang muncul dalam domain spasial (atau temporal) yang dapat ditransformasi menjadi masalah yang lebih sederhana dalam domain lainnya. Penyelesaian yang diperoleh dari domain kedua harus diubah kembali ke domain aslinya. Untuk mengubahnya, suatu invers transformasi diperlukan. Definisi 3.8 Misal N bilangan bulat positif genap dan Fk adalah barisan bilangan kompleks N dengan k N 2 1 : N 2 . Maka invers transformasi Fourier Diskritnya adalah fn
N 2
k N2 1
Fk Nnk
(3.17)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
60
untuk n N 2 1 : N 2 . Jika N bilangan bulat positif ganjil dan Fk adalah barisan bilangan kompleks N dengan k N 1 2 1 : N 1 2 . Maka invers transformasi Fourier Diskritnya adalah fn
N 1 2
Fk Nnk
k N21
(3.18)
untuk n N 1 2 1 : N 1 2 . Definisi ini bersifat periodik pada barisan f n yang memenuhi f n f n N ,
N f n N k2 N 1 1 2 N 1 N 1 N 1 N
N
N 2
k
N 1 2
2 ( n N ) k Fk N N k 1 2
N
N 2
k
N 1 2
2 Fk Nnk Nk N k 1 2
N
N 2
k
N 1 2
2 Fk Nnk NNk N k 1 2
N
N 2
k
N 1 2
2 Fk Nnk ei 2k N k 1 2
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 N 1 N
61
N
N 2
k
N 1 2
2 Fk Nnk 1 N k 1 2
N
N 2
k
N 1 2
2 N nk Fk N fn 2 N . k 1 2 N k 1 2
Seperti pada TFD, untuk mendefinisikan invers transformasi Fourier Diskrit dari barisan Fk akan digunakan notasi 𝒟 −1 {𝐹𝑘 }, dan 𝒟 −1 {𝐹𝑘 }𝑛 yang menyatakan elemen ke n dari invers transformasinya, sehingga 𝒟 −1 {𝐹𝑘 }𝑛 = 𝑓𝑛 . Notasi tersebut menunjukkan bahwa TFD dan ITFD merupakan invers satu sama lain, tetapi faktanya belum ditunjukkan. Maka selanjutnya akan ditunjukkan bahwa operator 𝒟 dan 𝒟 −1 memenuhi hubungan invers 𝒟 −1 {𝒟 𝑓𝑛 }𝑛 = 𝑓𝑛 dan 𝒟{𝒟 −1 𝐹𝑘 }𝑘 = 𝐹𝑘 . Untuk membuktikan rumus invers, membutuhkan sifat ortogonalitas dari fungsi eksponensial. Teorema 3.4 (Ortogonalitas) Jika j dan k bilangan bulat dan N bilangan bulat positif, maka N 1
e n 0
i 2 n j N
e i 2 n k
N
Nˆn j k .
(3.19)
Bukti: Misalkan N ei 2 N . Perhatikan bahwa N bilangan kompleks Nk untuk
k 0 : N 1 , yang disebut sebagai akar satuan ke-N karena memenuhi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
e k N N
i 2 k N N
62
ei 2 k 1 ,
dan oleh karena itu z N 1 0 . Nk adalah salah satu dari akar satuan ke N untuk setiap bilangan bulat k, tetapi barisan Nk k berperiode N
kN N k
e e cos 2 i sin 2 1
Nk NN
k
k N
i 2N / N k
k N
i 2 k
k N k N
k
k
k N k
Sehingga himpunan akar-akar ini dapat ditentukan oleh N k untuk setiap bilangan bulat N berturut-turut k. Pertama, kita faktorkan polinomial z N 1 seperti berikut
z N 1 z 1 z N 1 z N 2 z 1 N 1
z 1 z n n 0
Diketahui bahwa Nk adalah akar dari z N 1 0 , ada dua kasus untuk diperhatikan. Jika dimisalkan z Nj k di mana j k bukan kelipatan N, maka z 1 , dan kita mempunyai N 1
z n 0
N 1
n
N j k n 0 . n 0
Kasus lain, jika j k kelipatan N maka z Nj k 1 dan N 1
z n 0
n
N 1
N 1
n 0
n 0
N j k n 1 N .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
63
Sifat ortogonalitas terbukti dari kedua kasus tersebut. Sifat ortogonalitas (Teorema 3.4) juga dapat dibuktikan dengan langkah yang berbeda, yaitu dengan menerapkan deret geometri: N 1
an n 0
1 aN . 1 a
Akan dibuktikan: N 1
e
i 2 n j N
e i 2 n k
N
n 0
N Nˆn j k 0
jika j k 0 jika j k 0.
Untuk j k 0 ,
e N 1
i 2 j k N n
n 0
1 e i 2 j k N 1 e i 2 j k N
N
1 e i 2 j k 1 e i 2 j k N
0 1 cos 2 j k isin 2 j k i 2 j k N 1 e
0.
Untuk j k 0 ,
e N 1
e 1 N .
i 2 j k N n
n 0
Karena barisan Nk
N 1
N 1
0 n
n 0
berperiode
n 0
N , sifat ortogonal berlaku ketika
penjumlahan dalam (3.16) dihitung terhadap setiap N nilai n berturutturut; dengan kata lain, P N 1
n P
e i 2 nj N e i 2 n k
N
NˆN j k
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
64
untuk setiap bilangan bulat P. Sifat ortogonal transformasi Fourier Diskrit merupakan sebuah hubungan antara vektor-vektor. Dengan demikian jika terdapat N vektor kompleks
N0 Nk ω k N2 k N 1k N
,
maka N 1
ω j , ω k Nnj Nnk
*
(definisi hasil kali dalam)
n 0
N
e
N
e i 2 k
N 1
e i 2 n j
i 2 k N *
n 0
N 1
e i 2 n j
N
(definisi Nnk ) (sifat konjugat kompleks)
n 0
NˆN ( j k )
(Teorema 3.3)
Jadi, ω j , ω k NˆN ( j k )
dan sembarang
N nilai k berturut-turut menghasilkan himpunan vektor
yang ortogonal. Teorema 3.5 (Invers) Jika f n adalah barisan N bilangan kompleks dan Fk 𝒟 𝑓𝑛 Transformasi Fourier dari barisan f n , maka 𝒟 −1 𝒟 𝑓𝑛
𝑘 𝑛
𝑘
= fn .
adalah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
65
Bukti: Diketahui:
fn 𝒟
−1
𝐹𝑘
𝑛
N 2
Fk
1 dan Fk 𝒟 𝑓𝑛 𝑘 N
nk N
k N 1 2
N 2
f n Nnk .
n N2 1
Kombinasikan definisi 𝒟 dan 𝒟 −1 , sehingga 𝒟 −1 𝒟 𝑓𝑛
𝑘 𝑛
= 𝒟 −1 𝐹𝑘
N 2
F
(definisi 𝒟 𝑓𝑛
𝑛
(definisi 𝒟 −1 𝐹𝑘
Nnk
k
𝑘
)
𝑛
)
k N2 1
1 k N2 1 N N 2
1 N 1 N 1 N
N 2
k N2
j N2 1
1
nk N
N 2
j N2 1
j N2 1
N 2
j N2 1
N 2
fj
N 2
f j N jk Nnk
N 2
k N2 1
N 2
fj
k N2 1
(definisi Fk )
f j N jk
(aturan sigma)
Nnk N jk
(aturan sigma)
Nk ( n j )
(aturan pangkat)
NˆN n j
Penjumlahan n j pada persamaan terakhir di atas tidak nol hanya jika j n , sehingga persamaan terakhir tersebut menjadi 𝒟 −1 𝒟 𝑓𝑛 Dengan
menggunakan
𝑘 𝑛
1 N fn fn . N
langkah-langkah
yang
sama
membuktikan Teorema 3.5 dapat ditunjukkan bahwa 𝒟 𝒟 −1 𝐹𝑘 𝐹𝑘 .
untuk 𝑛
𝑘
=
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
𝒟 𝒟 −1 𝐹𝑘
𝑛
𝑘
= 𝒟 𝑓𝑛 1 N
(definisi 𝒟 −1 𝐹𝑘
𝑘
N 2
f n Nnk
(definisi 𝒟 𝑓𝑛
2 F nj nk j N j N 1 N 2
(definisi f n )
N
)
)
N
N
N
2 1 2 nk F j Nnj N j N N n N2 1 2 1
1 N
𝑘
𝑛
n N2 1
1 2 N n N2 1
1 N
66
N 2
N 2
Fj
j N2 1
n N2 1
N 2
N 2
Fj
j N2 1
(aturan sigma)
Nnj Nnk
(aturan sigma)
Nn j k
(aturan pangkat)
n N2 1
NˆN ( j k )
Penjumlahan j k pada persamaan terakhir di atas tidak nol hanya jika j k dan persamaan terakhir tersebut menjadi 𝒟 𝒟 −1 𝐹𝑘
𝑛
𝑘
=
1 N Fk = 𝐹𝑘 . N
Transformasi Fourier Diskrit (TFD) merupakan pemetaan dari N nilai f n ke N nilai Fk . Oleh karena itu, transformasi Fourier Diskrit dapat dinyatakan sebagai perkalian dari suatu vektor dengan N elemen dengan suatu matriks N N . Untuk menyatakan transformasi Fourier Diskrit dalam bentuk matriks akan lebih mudah bila menggunakan Definisi 3.7. Definisi 3.9 Jika f menyatakan vektor dari data input,
f f 0 , f1 , f 2 ,, f N 1 , T
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
67
dan F menyatakan vektor dari nilai output,
F F0 , F1 , F2 , , FN 1 , T
maka transformasi Fourier Diskrit dapat ditulis: F Wf ,
dengan
N0 0 N 1 0 W N N 0 N
N0 N1 N 2
N0 N 2 N 4
N 1 N
2 N 1 N
N N 1 N 2 N 1 . N 1 N 1 N
N0
Matriks W (matriks Fourier) merupakan matriks persegi dan matriks nonsingular, yaitu matriks yang mempunyai invers. Matriks ini mempunyai sifat-sifat penting, antara lain:
Karena
TFD
invertible
(nonsingular),
maka
matriks
tersebut
mempunyai invers yaitu W 1 .
Matriks W simetris, sehingga WT W .
Invers dari W merupakan suatu perkalian dari konjugat komplek W sendiri:
W 1 N W. Oleh karena itu, NWW * I (
*
menyatakan transpose konjugat dan I
merupakan matriks identitas), dan W merupakan matriks uniter terhadap faktor N. Faktor N dapat dimasukkan pada definisi TFD dan invers TFD, dalam kasus WW * I .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
68
Contoh 3.7 1 3 2 2 Diberikan N 3 sehingga 3 e i 2 3 cos . i sin i 2 2 3 3
Matriks Fouriernya adalah 30 1 W 30 3 0 3
30 30 1 1 1 1 1 2 1 3 3 1 3 32 . 3 1 3 2 31 32 34
Jika f 1 7 2 maka transformasi Fourier Diskrit f adalah T
1 1 1 F Wf 1 31 3 1 3 2
1 32 31
1 1 7 2 7 1 1 7 1 2 2 3 3 3 2 1 7 3 2 2 31 10 3 -1,1667 - i 1,4434 . -1,1667 + i 1,4434
Pada subbab selanjutnya akan dibahas mengenai sifat-sifat dari transformasi Fourier Diskrit 3.3.2. Sifat-sifat Dasar Transformasi Fourier Diskrit Sama halnya dengan deret Fourier dan transformasi Fourier, transformasi Fourier Diskrit memiliki sifat-sifat yang berguna untuk menyelesaikan banyak masalah. Misalnya, suatu masalah tertentu pada suatu domain (domain spasial atau waktu) dapat dirumuskan kembali ke dalam bentuk yang lebih sederhana pada domain frekuensi. Penghubung antara kedua domain tersebut adalah transformasi Fourier Diskrit dan sifatsifat dari transformasi Fourier Diskrit yang menjelaskan bagaimana suatu
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
69
masalah yang diberikan dimodifikasi dari domain yang satu ke domain yang lainnya. Untuk memaparkan sifat-sifat transformasi Fourier Diskrit akan digunakan rumus TFD (3.14) dan inversnya (3.17). Berikut beberapa sifatsifat dasar dari transformasi Fourier Diskrit. 1. Periodik Barisan-barisan fungsi kompleks Fk dan f n didefinisikan oleh
N titik, sehingga (3.11) dan (3.14) memiliki sifat periodik. Dengan kata lain, (3.11) dan (3.14) berperiode N , yang berarti bahwa N 2
Fk N n N 1 2
1 N 1 N 1 N 1 N
N
N 2
n
N 1 2
2 n( k N ) fn N N n 1 2
N
N 2
n
N 1 2
2 f n N nk nN N n 1 2
N
N 2
n
N 1 2
2 nk nN fn N N N n 1 2
N
N 2
n
N 1 2
2 f n N nk e i 2n N n 1 2
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 N 1 N
N
N 2
N 1 2
n
2 f n N nk 1 N n 1 2
N
N 2
N 1 2
n
2 N nk fn N Fk 2 N , n 1 2 N n 1 2
dan N
N f n N k2 N 1 1 2 N 1 N
N 2
k
N 1 2
2 ( n N ) k Fk N N k 1 2
N
N 2
k
1 N
1 N
1 N 1 N
N 1 2
2 Fk Nnk Nk N k 1 2
N
N 2
k
N 1 2
2 Fk Nnk NNk N k 1 2
N
N 2
k
N 1 2
2 Fk Nnk e i 2k N k 1 2
N
N 2
k
N 1 2
2 Fk Nnk 1 N k 1 2
N
N 2
k
N 1 2
2 N nk Fk N fn 2 N k 1 2 N k 1 2
70
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
71
berlaku untuk semua n, k ℤ+. Sifat tersebut diturunkan secara langsung dari pernyataan bahwa
n k N N k
Nnk NnN
k
Nnk e i 2nN / N
Nnk e i 2n
k
k
Nnk cos 2n i sin 2n k
Nnk 1 k
Nnk
k
dan
n N k N n , k
Nnk NNk
n , k
Nnk e i 2Nk / N
Nnk e i 2k
n , k
n , k
Nnk cos 2k i sin 2k n ,k
Nnk 1 n ,k
Nnk
n , k
.
2. Linear Salah satu sifat dasar dari TFD adalah linear: transformasi Fourier Diskrit dari kombinasi linear barisan-barisan input TFD adalah sama dengan kombinasi linear TFDnya. Sifat linear memungkinkan untuk memisahkan sinyal-sinyal ke dalam komponen-komponen yang bervariasi (dasar untuk analisis spektral). Sifat linear dapat ditunjukkan dengan cara berikut.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
72
Jika f n dan g n merupakan barisan bernilai kompleks sejumlah
N , dan dan adalah bilangan kompleks, maka 𝒟 f n g n k 𝒟 f n k 𝒟 g n k . Sifat tersebut mengikuti pernyataan berikut: 𝒟 f n g n k
1 N
N 2
f
n
g n Nnk
n N2 1
1 N
N 2
fn
nk N
n N2 1
1 N
N 2
g n Nnk
n N2 1
𝒟 f n k 𝒟 g n k . Sifat linearitas juga berlaku untuk invers transformasi Fourier Diskrit, yaitu: Jika Fk dan G k merupakan barisan bernilai kompleks sejumlah N , dan dan adalah bilangan kompleks, maka 𝒟 −1 Fk Gk n 𝒟 −1 Fk n 𝒟 −1 Gk n . Sifat tersebut mengikuti pernyataan berikut: 𝒟
−1
Fk G k n
N 2
F
k
Gk Nnk
n N2 1
N 2
n N2 1
Fk
nk N
N 2
Gk Nnk
n N2 1
𝒟 −1 Fk n 𝒟 −1 Gk n . 3. Pergeseran dan Modulasi Dua sifat yang saling berhubungan dan memiliki akibat yang penting adalah pergeseran dan modulasi. Sifat pergeseran menjelaskan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
73
akibat dari suatu barisan TFD yang telah digeser (atau ditranslasi). Suatu barisan f n yang telah digeser ke kanan sebesar j satuan dengan menggunakan invers dari transformasi Fourier Diskrit dapat ditulis sebagai
f n j
N 2
Fk Nn j k
k N2 1
N 2
F
k
N jk Nnk
k N2 1
𝒟 −1 Fk N jk n . Dari pernyataan terakhir dapat ditulis pernyataan berikut 𝒟 f n j k Fk N jk . Dengan kata lain, transformasi suatu barisan yang telah digeser ke kanan sebesar j satuan berakibat merotasi barisan asli koefisien TFD di bidang kompleks; pada faktanya, koefisien awal Fk dirotasi dengan sudut 2jk N . Sifat modulasi atau sifat pergeseran frekuensi memberikan akibat pada modulasi barisan input, yaitu, mengalikan elemen-elemen barisan input f n dengan Nnj , dengan j suatu bilangan bulat.
𝒟 fn
nj N k
1 N 1 N
N 2
f
n
Nnj Nnk
n N2 1
N 2
n N2 1
f n Nn k j
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
74
𝒟 f n k j Fk j . Sifat tersebut menjelaskan bahwa jika suatu barisan input dimodulasi dengan modus cos2 n j atau sin 2 n j dengan frekuensi j siklus pada domain maka akan menghasilkan TFD yang digeser sebesar j satuan.
3.3.3. Transformasi Fourier Diskrit 2 Dimensi Transformasi Fourier Diskrit 2 dimensi merupakan perluasan dari transformasi Fourier Diskrit 1 dimensi (transformasi Fourier Diskrit), sehingga prinsip-prinsip yang terdapat pada transformasi Fourier Diskrit 2 dimensi sama dengan transformasi Fourier Diskrit 1 dimensi. Pembedanya ialah fungsi yang dikenakan pada transformasi Fourier Diskrit 2 dimensi memiliki 2 variabel bebas. Oleh karena itu, pada subbab ini kita harus memandang input dari transformasi Fourier Diskrit 2 dimensi berupa suatu data array yang dinyatakan dalam suatu bidang. Sama halnya dengan transformasi Fourier Diskrit 1 dimensi, definisi dari transformasi Fourier Diskrit 2 dimensi dimulai dengan penjabaran input. Input yang diberikan dapat berupa suatu bentuk Diskrit (misal, data sampel) atau bentuk kontinyu (fungsi dua variabel). Untuk saat ini diasumsikan bahwa fungsi f terdefinisi pada A A B B x, y : x , y . 2 2 2 2
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
75
Seperti dalam kasus 1 dimensi fungsi f harus diberi sampel untuk dapat diselesaikan secara numerik. Untuk membuat sampel pada daerah tersebut suatu bidang koordinat dibentuk dengan jarak antar titik koordinat seragam yaitu x A M dalam sumbu horisontal dan y B M dalam sumbu vertikal. Titik-titik koordinat yang terbentuk (Gambar 3.6) diberikan oleh
xm , yn mx, ny dengan m M 2 1 : M 2 dan n N 2 1 : N 2 .
Gambar 3.6. (Kiri) Bidang koordinat spasial. (Kanan) Bidang koordinat frekuensi dengan jarak antar titik-titik koordinat m , n ialah
M pada sumbu horisontal dan m M 2 1 : M 2 dan n N 2 1 : N 2 .
N
dengan
Fungsi input f dapat disampelkan dengan mencatat nilainya pada titik-titik koordinat tersebut sehingga menghasilkan barisan (array) bilangan dari f mn f xm , y n . Sebagai antisipasi penggunaan array f mn sebagai input TFD, kita harus menganggap jika f mn mempunyai periode ganda, yang berarti
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
76
f m M ,n f mn dan f m,n N f mn .
Sekarang diasumsikan bahwa barisan input f mn terpisah, artinya fungsi
f mn g m hn . Dengan asumsi ini, barisan g m dan hn dapat
dinyatakan berdasarkan definisi invers transformasi Fourier Diskrit 1 dimensi, sehingga M 2
gm
G j
mj M
N 2
dan hn
j M2 1
H k Nnk ,
(3.20)
k N2 1
untuk m M 2 1 : M 2 dan n N 2 1 : N 2 . Dari (3.20), dapat dilihat bahwa G j dan H k merupakan koefisien TFD dari g m dan hn , yaitu
1 Gj M
M 2
g m
mj M
m M2 1
1 dan H k N
N 2
hn Nnk ,
n N2 1
dengan j M 2 1 : M 2 dan k N 2 1 : N 2 . Dengan penjabaran secara terpisah di atas, barisan f mn g m hn dapat dikonstruksikan dari perkalian antara g m dan hn , sehingga 2 2 g m hn G j Mmj H k Nnk j M2 1 k N2 1 N
M
f mn
M 2
j M2 1
M 2
j M2 1
N 2
G j H k Mmj Nnk k N 1 2
N 2
k N2 1
F jk
F jk Mmj Nnk ,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
untuk
m M 2 1: M 2
dan
77
n N 2 1 : N 2 . Sekarang kita
memiliki koefisien baru yaitu, F jk , F jk G j H k . Sama halnya dengan barisan f mn , koefisien F jk juga dapat dikonstruksikan dari perkalian antara G j dan H k , sehingga
1 F jk G j H k M
M 2
g m
mj M
m M2 1
1 MN
N 2
M 2
m M2 1
1 N
N 2
n N2 1
hn N nk
f mn M mj N nk ,
n N2 1
untuk j M 2 1 : M 2 dan k N 2 1 : N 2 . Definisi 3.10 (Transformasi Fourier Diskrit 2 dimensi) Jika diberikan suatu input M N array f mn , maka
1 F jk MN
N 2
M 2
m M2 1
f mn Mmj Nnk ,
(3.21)
n N2 1
untuk j M 2 1 : M 2 dan k N 2 1 : N 2 . Definisi 3.11 (Invers transformasi Fourier Diskrit 2 dimensi) Jika diberikan suatu input M N array F jk , maka
f mn
M 2
j M2
1
N 2
F jk Mmj Nnk ,
(3.22)
k N2 1
untuk m M 2 1 : M 2 dan n N 2 1 : N 2 . Selanjutnya akan ditunjukkan bahwa (3.21) dan (3.22) berperiodik M pada indeks pertama dan berperiodik N pada indeks kedua dan juga
akan ditunjukkan bahwa (3.21) dan (3.22) saling berinvers satu sama lain.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
78
Seperti pada kasus 1 dimensi, sifat invers bergantung pada ortogonalitas.
ω jk dengan
Pertama, akan ditunjukkan ortogonalitas dari vektor
jk ω mn Mmj Nnk . Perhatikan hasil kali dalam Diskrit dua modus dengan
frekuensi j, k dan j0 , k 0 ,
ω ,ω jk
j0 k 0
N 2
M 2
m M2 1
m M2
j0 k 0 jk ω mn ω mn
n N2 1 N 2
M 2
1
n N2
Mmj Nnk M mj N nk . 0
0
1
Dengan sifat perkalian eksponensial ( Na Nb Nab ) diperoleh M 2
m M2 1
N 2
mj M
nk N
mj0 M
nk0 N
N 2
M 2
m M2 1
n N2 1
0
0
n N2 1
M 2
Mm j j Nn k k
m j j0 M
m M2 1
N 2
Nn k k
0
n N2 1
M ˆM j j0 N ˆN k j0 .
Dengan sifat ortogonalitas dua dimensi tersebut, dapat ditunjukkan bahwa (3.20) dan (3.21) berinvers satu sama lain. Misalkan,
f mn 𝒟
−1
F
jk mn
M 2
j M2
1
N 2
k N2
F jk Mmj Nnk
1
dan F jk 𝒟 f mn jk
1 MN
M 2
𝑗𝑘 𝑚𝑛
𝒟 −1 𝐹𝑗𝑘
𝑚𝑛
m M2 1 n N2 1
Sehingga dapat ditunjukkan bahwa, 𝒟 −1 𝒟 𝑓𝑚𝑛
N 2
f mn Mmj Nnk .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
N 2
M 2
79
F jk Mmj Nnk
j M2 1 k N2 1
1 MN
N 2
M 2
j M2 1 k N2 1
1 MN
1 MN
j0 M2 1
N 2
M 2
f
j0 M2 1 k 0 N2 1
f
j0 M2 1 k 0 N2 1
j0 k 0
M 2
N 2
M j j N k k Mmj Nnk 0
0
j M2 1 k N2 1
N 2
M 2
N 2
M 2
j0 k 0
mj nk j0 j k 0 k f j0 k 0 M N M N k 0 N2 1 N 2
M 2
Mj m j Nk n k 0
0
j M 1 k N 1
2 2
MNˆM m j0 ˆN n k 0
Penjumlahan m j0 dan n k 0 pada persamaan terakhir di atas tidak bernilai nol tetapi jika m j0 dan n k 0 maka persamaan terakhir tersebut menjadi 𝒟 −1 𝒟 𝑓𝑚𝑛 Dengan
𝑗𝑘 𝑚𝑛
menggunakan
ditunjukkan juga 𝒟 𝒟 −1 𝐹𝑗𝑘 𝒟 𝒟 −1 𝐹𝑗𝑘
𝑚𝑛 𝑗𝑘
𝒟 𝑓𝑚𝑛 1 MN 1 MN 1 MN
1 MN f mn f mn . MN
langkah-langkah
𝑚𝑛 𝑗𝑘
yang
sama
dapat
F jk .
𝑗𝑘
N 2
M 2
f mn M mj N nk
m M2 1 n N2 1 N 2
M 2
M
m M2 1 n N2 1 N 2
M 2
j0 M2
2 j M 0 2 1
1
F
k 0 N2
1
j0 k 0
F
k 0 N2 1 N 2
M 2
m M2
1
N 2
n N2
1
Mmj Nnk M mj N nk 0
j0 k 0
0
Mmj Nnk M mj N nk 0
0
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 MN
N 2
M 2
F
j0 M2 1 k 0 N2 1
N 2
M 2
j0 k 0
Mm j j Nn k 0
0 k
80
m M2 1 n N2 1
MNˆM j0 j ˆN k 0 k
Penjumlahan
j0 j
dan k 0 k pada persamaan terakhir di atas tidak
bernilai nol tetapi jika j0 j dan k 0 k maka persamaan terakhir tersebut menjadi 𝒟 𝒟 −1 𝐹𝑗𝑘
𝑚𝑛 𝑗𝑘
1 MN F jk F jk . MN
Sama halnya dengan transformasi Fourier Diskrit 1 dimensi, transformasi Fourier Diskrit 2 dimensi juga mempunyai bentuk alternatif, yaitu: Definisi 3.12 Jika diberikan suatu input M N array f mn , maka 1 F jk MN
M 1 N 1
m 0
n 0
f mn Mmj nnk ,
(3.23)
dengan j 0 : M 1 dan k 0 : N 1. Ada beberapa sifat dalam TFD 2 dimensi yang mengikuti sifat-sifat dasar TFD 1 dimensi, yaitu: Misal 𝒟 merupakan transformasi Fourier Diskrit dua dimensi M N , maka 1. 𝒟 periodik: 𝒟 f mn j M ,k N 𝒟 f mn jk . M
𝒟 f mn j M ,k N
N
2 2 1 f mn Mm j M Nn k N MN m M2 1 n N2 1
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 MN 1 MN 1 MN 1 MN
N 2
M 2
81
f mn Mmj M mM Nnk N nN
m M2 1 n N2 1 N 2
M 2
f mn Mmj Nnk M mM N nN
m M2 1 n N2 1 N 2
M 2
f mn Mmj Nnk e i 2 m e i 2 n
m M2 1 n N2 1 N 2
M 2
f mn Mmj Nnk
m M2 1 n N2 1
𝒟 f mn jk . 2. 𝒟
bersifat
𝒟 f mn g mn jk F jk G jk ,
linear:
dan
konstanta. 𝒟 f mn g mn jk
M
N
M 2
N 2
2 2 1 f mn g mn Mmj Nnk MN m M2 1 n N2 1
1 MN
f
mn
m M2 1 n N2 1
1 MN
N 2
M 2
f mn M mj N nk
m M2 1 n N2 1
1 MN
M 2
N 2
g mn M mj N nk
m M2 1 n N2 1
F jk G jk .
Dengan cara yang sama dapat dibuktikan pula:
3. Pergeseran: 𝒟 f mm0 ,nn0
M m0 j N n0k F jk .
F j j0 ,k k0 .
4. Rotasi: 𝒟 M mj0 N nk0 f mn
jk
jk
M mj N nk g mn M mj N nk
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
82
Transformasi Fourier Diskrit 2 dimensi merupakan pemetaan dari
M N nilai f mn ke M N nilai F jk . Oleh karena itu, transformasi Fourier Diskrit 2 dimensi dapat dinyatakan sebagai perkalian dari suatu matriks dengan M elemen baris dan N elemen kolom dengan matriks M M dan matriks N N .
Definisi 3.13 Transformasi Fourier Diskrit 2 dimensi pada Definisi 3.12 dapat dihitung sebagai F2 WM f 2 WN , T
di mana
M0 0 M 1 0 WM M M 0 M
M0 M1 M 2
M0 M 2 M 4
M 1 M
2 M 1 M
M 1 M 1 M
M0
M 1 M 2 M 1 M
dan
N0 0 N 1 0 WN N N 0 N
N0 N1 N 2
N0 N 2 N 4
N 1 N
2 N 1 N
N N 1 N 2 N 1 N 1 N 1 N
N0
merupakan matriks Fourier. Contoh 3.8
1 2 5 Hitung transformasi Fourier Diskrit 2-dimensi dari f . 6 7 11
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
83
Diketahui: M 2 dan N 3 sehingga
M 2 e i 2 2 e i cos i sin 1 dan
N 3 e i 2 3 cos2 3 i sin2 3 1 2 i 3 2 . Matriks Fouriernya adalah
20 W2 0 2
20 1 1 , untuk m 0 : 1 dan j 0 : 1 , dan 21 1 21
30 W3 30 30
30 30 1 1 1 1 2 1 3 3 1 3 32 , untuk n 0 : 2 dan k 0 : 2 . 32 3 4 1 32 31
Berdasarkan definisi 3.13, maka transformasi Fourier Diskrit 2 dimensinya adalah
F2 W2f 2 W3
T
1 7 6 1 621
1 1 1 1 1 1 1 2 5 1 1 1 3 3 2 1 2 1 2 6 7 11 3 2 1 1 3 3 9 2 721
1 1 1 1 2 1 3 3 5 1121 2 1 1 3 3 16
1 1 1 9 16 1 7 1 1 3 3 2 6 5 5 6 2 1 1 3 3 1 2 1 32 7 93 163 6 16 5 531 632
7 932 1631 5 532 631
1 32 5,5 i 6,0622 5,5 i 6,0622 0,5 i 0,8660 6 16 0,5 i 0,8660 5,3333 0,9167 i 1,0104 0,9167 i 1,0104 . 0,0833 i 0,1443 2,6667 0,0833 i 0,1443
T
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
84
3.3.4. Transformasi Fourier Diskrit pada Kompresi Sinyal Bila diberikan suatu sampel sinyal x dengan elemen-elemen
xk f kt , 0 k N 1 untuk beberapa fungsi f yang terdefinisi pada
0,1 , dengan
t 1 N . Berikut tahapan kompresi dengan menggunakan
transformasi Fourier Diskrit: 1.
Tentukan X , Transformasi Fourier Diskrit dari sinyal x .
2.
Tentukan suatu nilai ambang batas (threshold) yang disimbolkan dengan c antara 0 c 1 .
3.
Tentukan M max 0k N 1 X k .
4.
~ Definisikan X ℂ𝑁 dengan komponen
X k , ~ Xk 0,
jika X k cM , jika X k cM .
Tahap 2 sampai tahap 4 merupakan tahapan di mana frekuensifrekuensi yang tidak signifikan dieliminasi, yaitu dengan membuat nol setiap koefisien Fourier X yang berada di bawah nilai ambang batas. ~ Vektor X akan menjadi vektor sinyal yang terkompresi. Bila terdapat
banyak elemen-elemen
~ ~ X k 0 , maka X
akan mudah untuk
dikompresi. 5.
~ Tentukan ~ x , invers transformasi Fourier Diskrit dari X . Tahapan ini
merupakan tahapan dekompresi. Vektor ~ x merupakan vektor sinyal yang terkompresi. Vektor ~ x tersebut harus mengaproksimasi x .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
85
Untuk mengetahui hasil kompresi tersebut baik atau tidak, hitung kesalahan relatifnya dengan rumus kesalahan relatif
x~ x x
100 .
Semakin kecil persentase galat relatif yang diperoleh, maka kompresi citra digital asli yang dihasilkan semakin baik. Contoh 3.9 Misal diberikan fungsi
f t (t t 2 ) 2 yang merepresentasikan suatu
sinyal, didefinisikan pada interval tertutup 0,1 dengan N 256 . Grafik fungsi f digambarkan pada Gambar 3.7 (Kiri). Grafik TFD dari f
yang dinyatakan dengan pasangan k , Fk
2
Fk ,
N dengan 127 k 128 ,
digambarkan pada Gambar 3.7 (Kanan). 0.07 0.06
0.25
0.05 0.04
TFD f
f(t)=(t-(t2))2
0.2
0.03
0.15
0.1 0.02 0.05
0.01 0
0
0.2
0.4
0.6 t
Gambar 3.7. TFD dari f .
0.8
1
0
-100
-50
0 k
50
100
(Kiri) Grafik fungsi f t (t t 2 ) 2 dan (Kanan) Grafik
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
86
Pilih sebuah nilai ambang batas (threshold), misal c 0.001 . Kemudian, hitung M max 0k 255 Fk , diperoleh M 8.5 . Dengan nilai ambang batas tersebut, maka dapat diperoleh suatu vektor ~ baru, yaitu F , merupakan vektor yang akan menjadi sinyal yang ~ terkompresi. Dari vektor F dengan menggunakan definisi 3.8 diperoleh
~ f , merupakan vektor dari sinyal yang terkompresi.
Kemudian dihitung kesalahan relatifnya dengan rumus
kesalahan relatif
~ f f f
100 1,35999661 1,36 %.
Dari tingkat kesalahan relatif tersebut dapat disimpulkan bahwa sinyal hasil kompresi serupa dengan sinyal aslinya. Sinyal asli
Sinyal Terkompresi
0.07
0.07
0.06
0.06
0.05
0.05
0.04
0.04
0.03
0.03
0.02
0.02
0.01
0.01
0
0
0.2
0.4
0.6
0.8
1
0
0
0.2
0.4
0.6
0.8
1
Gambar 3.8. Sinyal asli (kiri) dan sinyal terkompresi (kanan). Hasil dari kompresi sinyal dengan transformasi Fourier Diskrit adalah sebagai berikut,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Dari hasil tersebut dapat dihitung besarnya presentase kompresi, yaitu
resolusi sinyal terkompresi 100 Presentase 1 resolusi sinyal asli 1136 1 100 44,53 %. 2048 Artinya, sinyal asli terkompresi sebesar 44.53%.
87
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB IV APLIKASI TRANSFORMASI FOURIER DISKRIT
Pada bab ini akan dibahas mengenai aplikasi transformasi Fourier Diskrit pada kompresi citra digital beraras keabu-abuan. Pertama-tama akan dibahas mengenai citra diskrit dan citra beraras keabu-abuan.
4.1. Citra Diskrit Citra diskrit atau citra digital merupakan suatu array yang berisi nilainilai real maupun komplek yang direpresentasikan dengan deretan bit tertentu. Citra digital dapat didefinisikan sebagai fungsi f x, y berukuran M baris dan N kolom M N , dengan x dan y adalah koordinat spasial, dan amplitudo f di koordinat x, y yang merupakan tingkat keabu-abuan dari citra. Citra diskrit atau digital dapat dituliskan dalam bentuk matriks sebagai berikut:
f (0,0) f (1,0) f f ( M 1,0)
f (0,1) f (1,1)
f ( M 1,1)
f (0, N 1) f (1, N 1) . f ( M 1, N 1)
4.2. Citra Beraras Keabu-abuan Citra beraras keabu-abuan dimodelkan sebagai suatu fungsi bernilai riil g x, y yang terdefinisi pada suatu bidang 2 dimensi, yaitu . Nilai
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
89
g x, y menyatakan intensitas keabu-abuan dari citra di titik x, y pada bidang . Citra beraras keabu-abuan juga dapat dinyatakan dengan matriks
M N
yang komponen elemen-elemennya merupakan bilangan bulat.
Berikut matriks dari citra beraras keabu-abuan:
g (0,1) g (0, N 1) g (0,0) g (1,0) g (1,1) g (1, N 1) g . g ( M 1,0) g ( M 1,1) g ( M 1, N 1) Untuk citra 8-bit, nilai intensitas keabu-abuan bernilai dari 0 sampai 255 = 28 1 . Nilai 0 merepresentasikan hitam murni dan nilai 255 merepresentasikan putih murni.
Gambar 4.1. Contoh citra beraras keabu-abuan.
4.3. Kompresi Citra Beraras Keabu-abuan Tahapan pada kompresi citra beraras keabu-abuan secara garis besar sama seperti tahapan pada kompresi sinyal. Dalam kompresi citra beraras
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
90
keabu-abuan transformasi Fourier Diskrit yang digunakan ialah transformasi Fourier Diskrit 2 dimensi. Berikut tahapan kompresi citra beraras keabuabuan: 1.
Inputkan suatu citra yang akan dikompresi ke dalam Matlab dengan perintah imread, misal, z=imread('happy.jpg');.
Kemudian konstruksikan citra asli menjadi citra beraras keabu-abuan dengan zg=im2double(rgb2gray(z));.
Citra Asli
Citra Beraras Keabu-abuan
Gambar 4.2. Citra asli ‘happy.jpg’ (kiri) dan citra beraras keabu-abuan ‘happy.jpg’ (kanan).
2.
Hitung transformasi Fourier Diskrit 2 dimensi dari citra beraras keabuabuan ‘happy.jpg’.
3.
Pilih suatu nilai ambang batas (threshold) antara 0 dan 1. Misal,
c 0.001 . 4.
Tentukan nilai maksimum dari mutlak transformasi Fourier Diskrit 2 dimensi yang diperoleh pada tahap 2. Sehingga diperoleh,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
91
M 229460 . 5.
Membuat nol semua frekuensi dari nilai mutlak transformasi Fourier Diskrit 2 dimensi yang berada di bawah nilai ambang batas.
6.
Hitung invers transformasi Fourier Diskrit 2 dimensi dari hasil pada tahap 5. Citra hasil pada tahap ini merupakan citra terkompresi.
7.
Untuk mengetahui besarnya kesalahan dari citra terkompresi, hitung kesalahan relatifnya dengan rumus
kesalahan relatif
citra beraras keabuan zg citra terkompresi zc citra beraras keabuan zg ,
100
sehingga diperoleh, kesalahan relatif 1,93172887 1,93 % .
Dari tingkat kesalahan relatif tersebut dapat disimpulkan bahwa citra kompresi hampir serupa dengan citra aslinya. Citra Asli
Citra Beraras Keabu-abuan
Citra Terkompresi
Gambar 4.3. Citra output dari algoritma kompresi citra dengan transformasi Fourier Diskrit 2 dimensi.
Berikut hasil dari kompresi citra beraras keabu-abuan dengan transformasi Fourier Diskrit 2 dimensi,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
92
Dari hasil tersebut dapat dihitung besarnya persentase kompresi, resolusi citra terkompresi Persentase 1 100 resolusi citra keabuan 95472 1 100 95,989. 2380000
Artinya, citra beraras keabuan terkompresi sebesar 95,99 %. Bila nilai ambang batas c 0.01 , maka hasil kompresinya adalah Citra Asli
Citra Beraras Keabu-abuan
Gambar 4.4. Citra output dengan c = 0,01.
Citra Terkompresi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
93
Hasil dari kompresi citra beraras keabu-abuan dengan transformasi Fourier Diskrit 2 dimensinya adalah
Kesalahan relatif yang diperoleh sebesar 6,5 % dan persentase kompresi yang diperoleh ialah 3408 Persentase 1 100 99,85 % , 2380000
artinya citra beraras keabu-abuan terkompresi sebesar 99,85 %. Dengan langkah yang sama untuk nilai ambang batas yang berbeda diperoleh kesalahan relatif sebagai berikut: c Kesalahan Relatif (%)
10 5
10 4
0,001
0.0036
0,2199
1,9317
0,01
0,05
0,1
0,5
6,4955 15,0256 19,4186 28,8257
Tabel 4.1. Tingkat galat relatif.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
94
GRAFIK KESALAHAN RELATIF
kesalahan relatif (dalam %)
30 25 20 15 10 5 0
0
0.05
0.1
0.15
0.2 0.25 0.3 nilai ambang batas
0.35
0.4
0.45
0.5
Gambar 4.5. Grafik kesalahan relatif. Dari grafik kesalahan relatif (Gambar 4.5), terlihat bahwa semakin besar nilai ambang yang dipilih maka akan semakin besar juga kesalahan relatif yang diperoleh. Sebab dengan nilai ambang batas yang besar, banyak nilai frekuensi-frekuensi yang tidak signifikan (di bawah nilai ambang batas) dibuat nol. Dengan nilai ambang batas yang berbeda juga dapat diperoleh besarnya persentase citra asli yang terkompresi sebagai berikut: c Persentase (%)
10 4
5 10 4
7 10 4
0,001
0,005
0,01
0,05
4,91 50,44
88,66
93,37
95,99
99,72
99,86
99,91
10 4
Tabel 4.2. Persentase citra asli yang terkompresi.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
95
persentase citra terkompresi (dalam %)
GRAFIK PERSENTASE CITRA ASLI YANG TERKOMPRESI 100
80
60
40
20
0
0
0.005
0.01
0.015
0.02 0.025 0.03 nilai ambang batas
0.035
0.04
0.045
0.05
Gambar 4.6. Grafik besarnya persentase citra asli yang terkompresi. Dari grafik pada Gambar 4.6, terlihat bahwa semakin besar nilai ambang batas yang dipilih maka semakin besar pula persentase citra beraras keabuabuan yang terkompresi. Tahapan kompresi di atas merupakan algoritma kompresi dengan menggunakan transformasi Fourier Diskrit, khususnya transformasi Fourier Diskrit 2 dimensi.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB V PENUTUP
5.1. Kesimpulan Dalam bidang ilmu komputer, sinyal atau citra digital pada suatu ruang waktu dapat dikonversikan ke dalam bentuk vektor. Selanjutnya, vektor yang merepresentasikan sinyal atau citra tersebut ditransformasi ke domain frekuensi dengan transformasi Fourier. Implementasi dari transformasi Fourier adalah Transformasi Fourier Diskrit (TFD). Transformasi Fourier
Diskrit dapat
digunakan dalam proses
pemampatan data, baik data berupa suatu sinyal atau citra digital pada suatu domain waktu. Data tersebut terlebih dahulu dikonversikan ke dalam bentuk vektor atau matriks, misalkan x . Kemudian, vektor atau matriks tersebut ditransformasikan ke dalam ruang frekuensi dengan transformasi Fourier Diskrit. Output dari transformasi tersebut berupa vektor atau matriks dengan ukuran yang sama dengan vektor atau matriks aslinya, misalkan X . Elemenelemen yang tidak memiliki pengaruh besar di X dianggap nol, sehingga ~ akan menghasilkan suatu vektor atau matriks baru yaitu X . Kemudian, pada ~ vektor atau matriks X dilakukan inversi dengan invers transformasi Fourier
Diskrit yang menghasilkan suatu vektor atau matriks yang serupa dengan vektor atau matriks aslinya, yaitu ~ x. Nilai
ambang
batas
(threshold)
sangat
berpengaruh
dalam
pemampatan data menggunakan transformasi Fourier Diskrit. Nilai ambang
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
97
batas ini akan menentukan nilai-nilai frekuensi manakah yang harus dianggap nol. Apabila nilai ambang batas semakin kecil mendekati nol, maka hasil kompresi terhadap sinyal atau citra digital semakin serupa dengan sinyal atau citra digital aslinya dan kesalahan yang dihasilkan dari sinyal atau citra digital pun akan semakin mendekati nol. Dengan nilai ambang batas ini, jumlah bit rate (ukuran resolusi) sinyal atau citra digital yang terkompresi akan menjadi lebih kecil dari sinyal atau citra digital aslinya. Pada contoh aplikasi transformasi Fourier Diskrit terlihat benar bahwa transformasi Fourier Diskrit dapat mentransformasikan suatu vektor menjadi vektor yang lebih sederhana dan apabila diinverskan kembali vektor hasilnya serupa dengan vektor aslinya (tidak mengalami perubahan yang signifikan). Hal ini terlihat pada kesalahan relatif yang dihasilkan.
5.2. Saran Dalam skripsi ini hanya dibahas mengenai aplikasi transformasi Fourier Diskrit pada kompresi citra. Bagi penelitian-penelitian selanjutnya dapat membahas lebih luas mengenai aplikasi lain dari transformasi Fourier Diskrit, seperti penyaringan sinyal.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
98
DAFTAR PUSTAKA
Anton, Howard. & Robert C. Busby. 2003. Contemporary Linear Algebra. New Jersey: Wiley.
Boggess, Albert. & Francis J. Narcowich. 2001. A First Course in Wavelets with Fourier Analysis (1st ed). New Jersey: Pearson Prentice-Hall.
Briggs, William L. & Van Emden Henson. 1995. The DFT: An Owner's Manual For The Discrete Fourier Transform. Philadelphia: Siam.
Broughton, S. Allen. & Kurt Bryan. 2009. Discrete Fourier Analysis and Wavelets: Application to Signal and Image Processing. Canada: Wiley. Purcell, Edwin J, dkk. 2007. Calculus (9th ed). New Jersey: Pearson Prentice-Hall. Putra, Darma. 2010. Pengolahan Citra Digital. Yogyakarta: Penerbit ANDI. Soemantri, R. 1994. Diktat: Fungsi Variabel Kompleks. Yogyakarta: Universitas Sanata Dharma.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
99
LAMPIRAN
Lampiran 1 clc clear all %Algoritma Penyelesaian Contoh 3.6 N=12; n=linspace(-5,6,N); k=n; x=[0.7630,-0.1205,-0.0649,0.6133,-0.2697,-0.7216,-0.0993,0.9787,0.5689,-0.1080,-0.3685,0.0293] for l=1:N for s=1:N omg(s)=exp(-2i*pi*n(s)/N); end X(l)=dot(x,(omg.^k(l)))/N; end X for l=1:N for s=1:N omgi(s)=exp(2i*pi*k(s)/N); end xi(l)=dot(X,conj(omgi.^n(l))); end subplot(221),plot(n,real(x)) axis([-5 6 -1 1]) subplot(222),plot(n,imag(x)) axis([-5 6 -1 1]) subplot(223),plot(k,real(X)) axis([-5 6 -1 1]) subplot(224),plot(k,imag(X)) axis([-5 6 -1 1])
Lampiran 2 clc clear all %Algoritma Penyelesaian Contoh 3.8 f=[1 2 5;6 7 11] M=2; N=3; wm=exp(2*i*pi/M); wn=exp(2*i*pi/N); Wm=zeros(M,M);
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Wn=zeros(N,N); %Algoritma TFD 2 dimensi for m=1:M for j=1:M Wm(m,j)=(1/M)*wm^(-(m-1)*(j-1)); end end for n=1:N for k=1:N Wn(n,k)=(1/N)*wn^(-(n-1)*(k-1)); end end F=(Wm*f)*transpose(Wn) %Algoritma invers TFD 2 dimensi for m=1:M for j=1:M Wmi(m,j)=(1/M)*wm^((m-1)*(j-1)); end end for n=1:N for k=1:N Wni(n,k)=(1/N)*wn^((n-1)*(k-1)); end end Finv=abs((Wmi*F)*transpose(Wni))*M*N
Lampiran 3 clc clear all tic %Algoritma Penyelesaian Contoh 3.9 N=256; t=linspace(0,1,N); k=linspace(-127,128,N); f=(t-(t.^2)).^2; %Transformasi Fourier Diskrit for m=1:N omg(m)=exp(-2i*pi*m/N); end for l=1:N F(l)=dot(f,(omg.^k(l))); end b=abs(F); y=(b.^2)/N;
100
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
101
%Algoritma Kompresi c=0.001; M=max(b); p=c*M; for s=1:N if b(s)>=p Ftilda(s)=F(s); else Ftilda(s)=0; end end %Invers Transformasi Fourier Diskrit for a=1:N ftilda(a)=abs(dot(Ftilda,conj(omg.^a)))/N; end Kesalahan_relatif=(norm(f-ftilda)/norm(f))*100;
sp_Ftilda=sparse(Ftilda); sp_ftilda=real(spfun(@ifft,sp_Ftilda)); Sinyal_asli=f; whos 'Sinyal_asli' Sinyal_terkompresi=sp_ftilda; whos 'Sinyal_terkompresi' disp('------------------------------------------------------------------'); disp(' Nilai ambang batas Kesalahan relatif '); disp('------------------------------------------------------------------'); fprintf('%20.5f %35.8f\n',c,Kesalahan_relatif); disp('------------------------------------------------------------------'); subplot(121),plot(t,f) title('Sinyal asli') subplot(122),plot(t,ftilda) title('Sinyal Terkompresi') Waktu_proses_detik=toc
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
102
Lampiran 4 clc clear all disp('------------------------------------------------------------------'); disp(' ##### KOMPRESI CITRA KEABUAN TRANSFORMASI FOURIER DISKRIT #####'); disp('------------------------------------------------------------------'); tic %Algoritma mengubah citra warna menjadi citra beraras keabuan z=imread('happy.jpg'); %Membaca citra input sebagai matriks zg=im2double(rgb2gray(z)); %Mengubah citra input menjadi citra beraras keabuan [M,N]=size(zg); %Ukuran matriks dari citra keabuan %Transformasi Fourier Diskrit 2 Dimensi Z=fft2(zg); %Algoritma Kompresi Zabs=abs(Z); maks=max(max(Zabs)); c=0.05; b=c*maks; Zc=(Zabs>b).*Z; for m=1:M for n=1:N if Zabs(m,n)>=b Zc(m,n)=Z(m,n); else Zc(m,n)=0; end end end %Invers Transformasi Fourier Diskrit 2 Dimensi zc=real(ifft2(Zc)); kesalahan_relatif=100*(norm(zg-zc)/norm(zg)); Citra_asli=z; whos 'Citra_asli' Citra_keabuan=zg; whos 'Citra_keabuan' Citra_terkompresi=sparse(abs(Zc)); whos 'Citra_terkompresi'
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
103
disp('------------------------------------------------------------------'); disp(' Nilai ambang batas Kesalahan relatif '); disp('------------------------------------------------------------------'); fprintf('%20.5f %35.8f\n',c,kesalahan_relatif); disp('------------------------------------------------------------------'); figure; subplot(1,3,1), imshow(z), title('Citra Asli') subplot(1,3,2), imshow(zg), title('Citra Beraras Keabu-abuan') subplot(1,3,3), imshow(zc), title('Citra Terkompresi') Waktu_proses_detik=toc