Frequency Domain - Citra Digital (UTS)

Untuk memenuhi tugas UTS Citra Digital, maka kali ini akan dijelaskan secara singkat tentang Frequency Domain dan juga sub dari Fourier Transform.

I. Frequency Domain

      Frequency Domain atau domain frekuensi mengacu pada analisis fungsi matematika atau sinyal terhadap frekuensi, daripada waktu. Secara sederhana, grafik waktu-domain menunjukkan bagaimana perubahan sinyal dari waktu ke waktu, sedangkan grafik frekuensi-domain menunjukkan berapa banyak sinyal terletak dalam setiap pita frekuensi yang diberikan pada rentang frekuensi. Sebuah representasi frekuensi domain juga dapat mencakup informasi tentang pergeseran fase yang harus diterapkan untuk setiap sinusoid agar dapat bergabung kembali komponen-komponen frekuensi untuk memulihkan sinyal waktu asli.
       Sebuah fungsi atau sinyal yang diberikan dapat dikonversi antara waktu dan frekuensi domain dengan sepasang operator matematika yang disebut transformasi. Contohnya adalah transformasi Fourier, yang mengubah fungsi waktu ke dalam sejumlah gelombang sinus frekuensi yang berbeda, yang masing-masing merupakan komponen frekuensi. The 'spektrum' komponen frekuensi adalah representasi domain frekuensi sinyal. Invers transformasi Fourier mengubah fungsi domain frekuensi kembali ke fungsi waktu. Sebuah analisa spektrum adalah alat yang biasa digunakan untuk memvisualisasikan sinyal dunia nyata dalam domain frekuensi.
      Beberapa teknik pemrosesan sinyal khusus digunakan transformasi yang menghasilkan domain frekuensi waktu bersama, dengan frekuensi sesaat menjadi penghubung utama antara domain waktu dan domain frekuensi.

       Sembarang sinyal spasial mempunyai representasi frekuensi, termasuk pada sebuah citra. Makna frekuensi dalam citra adalah :
·    Komponen frekuensi tinggi dikaitkan dengan perubahan piksel ke piksel secara cepat sepanjang citra. Misal: teks, tekstur, dsb.
·     Komponen frekuensi tinggi dikaitkan dengan fitur berskala besar pada citra. Misal: daerah dengan intensitas konstan, atau piksel yang jumlahnya mendominasi dalam seluruh daerah citra.

             Melalui proses transformasi suatu citra dapat dinyatakan sebagai kombinasi linier dari sinyal dasar (basic signals) yang sering disebut fungsi basis (basic function). Suatu citra yang telah mengalami transformasi dapat diperoleh kembali dengan menggunakan transformasi balik (invers transformation).

II. Fourier Transform

      Fourier Transform atau Transformasi fourier adalah suatu model transformasi yang memindahkan domain spasial atau domain waktu menjadi domain frekuensi. Di dalam pengolahan citra digital transformasi fourier digunakan untuk mengubah domain spasial pada citra menjadi domain frekuensi. Analisis dalam domain frekuensi banyak digunakan seperti filtering. Dengan menggunakan transformasi fourier, sinyal atau citra dapat dilihat sebagai suatu objek dalam domain frekuensi.

    Di dalam pengolahan citra, transformasi Fourier digunakan untuk menganalisis frekuensi pada operasi seperti perekaman citra, perbaikan kualitas citra, restorasi citra, pengkodean, dan lain-lain. Dari analisis frekuensi, kita dapat melakukan perubahan frekuensi pada gambar. Perubahan frekuensi berhubungan dengan spektrum antara gambar yang kabus kontrasnya samapi gambar yang kaya akan rincian visualnya. Sebagai contoh, pada proses perekaman citra mungkin terjadi pengaburan kontras gambar. Pada gambar yang mengalami kekaburan kontras terjadi perubahan intensitas secara perlahan, yang berarti kehilangan informasi frekuensi tinggi. Untuk meningkatkan kualitas gambar, kita menggunakan penapis frekuensi tinggi sehingga pixel yang berkontras kabur dapat dinaikkan intensitasnya.

a. Transformasi Fourier 1D

Transformasi Fourier kontinu 1D dari suatu fungsi waktu f(t) didefinisikan dengan:

dimana F(w) adalah fungsi dalam domain frekwensi

           w adalah frekwensi radial 0 – 2pf,

           atau dapat dituliskan bahwa w = 2pf

Contoh 

Diketahui fungsi f(t) sebagai berikut:

Transformasi Fourier dari f(t) di atas adalah:

Hasil dari transformasi Fourier untuk  0 s/d 2 adalah :

            

b. Transformasi Fourier 2D

          Transformasi Fourier kontinu 2D dari suatu fungsi spasial f(x,y) didefinisikan dengan :

Dimana F(w₁,w₂) adalah fungsi dalam domain frekwensi

             f(x,y) adalah fungsi spasial atau citra

             w₁ dan w₂ adalah frekwensi radial 0 – 2phi.

Transformasi fourier yang digunakan dalam pengolahan citra digital adalah transformasi fourier 2D.

Contoh

Diketahui fungsi spasial f(x,y) berikut:

Transformasi fourier dari f(x,y) di atas adalah:

Hasil dari transformasi fourier untuk 0<w₁,w₂<2phi, adalah sebagai berikut :

Transformasi Fourier semacam ini disebut dengan continuous fourier transform, dan sulit dikomputasi karena ada operasi integral dan sifat kontinunya itu sendiri.

Karena citra adalah gelombang diskrit, maka citra tersebut harus ditransformasikan ke dalam bentuk frekuensi dengan menggunakan Discreate Fourier Transform (DFT).

Untuk citra 2 dimensi, DFT yang digunakan:

Sedangkan inverse DFT (transformasi sinyal frekuensi menjadi sinyal diskrit) digunakan :

Karena nilai FT adalah bilangan kompleks, kadang-kadang kita nyatakan F(u) dalam koordinat polar:

Dimana jarak atau spektrum dinyatakan dengan:

Sudut fase dnyatakan oleh:

Dasar untuk filter linear dalam domain spasial dan frekuensi adalah teori konvolusi, yang dapat dituliskan dengan:

Seperti halnya teori konvolusi, juga bisa mendapatkan hasil yang sama dalam domain frekuensi dengan perkalian antara F(u,v) dengan H(u,v).

III. Transformasi Fourier Diskrit

           Pada pengolahan sinyal dengan komputer digital, fungsi dinyatakan oleh himpunan berhingga nilai diskrit. Transformasi Fourier Diskrit (TFD) ditujukan bagi persoalan yang tidak menghasilkan solusi transformasi Fourier dalam bentuk fungsi malar. Transformasi fourier diskrit atau disebut dengan Discrete Fourier Transform (DFT) adalah model transformasi fourier yang dikenakan pada fungsi diskrit, dan hasilnya juga diskrit. DFT didefinisikan dengan :

IV. Pengaplikasiannya pada Citra Digital

a. Lowpass Filter

Low-pass filtering merupakan metode penghalusan sebuah sinyal atau citra. Smoothing / blurring / penghalusan dicapai dalam domain frekuensi dengan pelemahan frekuensi tinggi. Smoothing dapat membantu menghilangkan noise, karena  noise / interference disebabkan oleh frekuensi tinggi.

Operasi penapisan Lowpass Filter dilaksanakan melalui konvolusi atau tanpa konvolusi. Efek pengaburan citra dapat ditingkatkan dengan menaikkan ukuran kernel. Rahasia kernel yang digunakan untuk keperluan mengaburkan citra seperti berikut :

•  Tinggi dan lebar kernel ganjil.
•  Bobot dalam kernel bersifat simetris terhadap piksel pusat.
• Semua bobot bernilai positif.
• Jumlah keseluruhan bobot sebesar satu.

- Ideal Lowpass Filter (ILPF)

Filter lowpass 2-D yang melewatkan tanpa pelemahan semua frekuensi rendah dalam lingkaran radius D₀ dari origin dan dengan cutoff semua frekuensi di luar lingkaran disebut Ideal Lowpass Filter (ILPF) yang ditentukan oleh fungsi :

di mana D₀ adalah konstanta positif jarak origin dan D(u,v) adalah jarak antara titik (u,v) dalam domain frekuensi dan pusat persegi panjang frekuensi, maka:

contoh :

- Butterworth Lowpass Filter

Fungsi Butterworth lowpass filter (BLPF)  dari order n, dan dengan cutoff frekuensi pada jarak D₀ dari origin, didefinisikan sebagai :

di mana D₀ adalah konstanta positif jarak origin dan D(u,v) adalah jarak antara titik (u,v) dalam domain frekuensi dan pusat persegi panjang frekuensi, maka:

contoh :

b. HighPass Filter
   High Pass Filtering adalah filter yang ditujukan untuk melewatkan frekuensi tinggi dan menghalangi yang berfrekuensi rendah. Hal ini biasadipakai untuk mendapatkan tepi objek dalam citra atau menajamkan citra.Filter lolos-tinggi mempunyai sifat yaitu jumlah seluruh koefisienadalah nol. Selain itu terdapat s ifat sebagai berikut

- Apabila dikenakan pada area dengan perubahan aras keabuan yang lambat (frekuensi rendah), hasil berupa nol atau nilai yang sangatkecil.

- Apabila dikenakan pada area yang perubahan aras keabuannya cepat(frekuensi tinggi), hasil konvolusi bernilai sangat besar.Rahasia kernel yang digunakan untuk keperluan mendeteksi tepiseperti berikut :

- Tinggi dan lebar kernel ganjil.

- Bobot dalam kernel bersifat simetris terhadap piksel pusat.

- Bobot pusat kernel bernilai positif.

- Bobot tetangga pusat kernel bernilai negatif (dapat menggunakan 4-ketetanggan atau 8 ketetanggaan).

- Jumlah keseluruhan bobot sebesar satu.
  
 High Pass Filtering dapat dilakukan dengan cara yang berkebalikan dengan cara yang dilakukan pada low pass filtering, yaitu dengan menghilangkan elemen-elemen (nilai-nilai) pada pusat matriks dan mempertahankan nilai-nilai yang lain. Secara sederhana hal ini dapat dilakukan dengan membuat lingkaran yang berkebalikan dengan yang digunakan pada low pass filtering. 

Teori Bahasa Outomata(TUgas 1 dan 2)

SOAL :

Tugas 1

Bagaimana proses pencarian pada Google :

                   Cara kerja Mesin Pencari Google

Salah satu inovasi utama adalah PageRank, sebuah teknologi yang menentukan "pentingnya" dari sebuah halaman web dengan melihat, apakah terdapat link halaman lain ke halaman web tsb berserta data lainnya? Google menggunakan lebih dari 200 sinyal, termasuk PageRank dan memperbarui algoritma ini setiap minggu. Sebagai contoh, google menawarkan hasil pencarian yang dipersonalisasi berdasarkan riwayat web Anda dan lokasi.

Kelengkapan.

Google diluncurkan pada tahun 1998 hanya dengan 25 juta halaman, saat itu merupakan sebagian kecil dari web. Kini google mempunyai indeks bermiliar-miliar halaman web, dan indeks google adalah sekitar 100 juta gigabyte. Google terus berinvestasi untuk menambah kelengkapan layanan kami. Pada tahun 2007 kami memperkenalkan Universal Search, yang membuat pencarian lebih komprehensif dengan mengintegrasikan gambar, video, berita, buku dan lebih ke hasil pencarian utama kami.

Kesegaran.

Pada masa awal, Googlebots merayapi Web setiap tiga atau empat bulan, yang berarti bahwa informasi yang Anda ditemukan di Google biasanya adalah dari per tanggal. Sekarang google terus merangkak Web memastikan bahwa Anda dapat menemukan berita terbaru, blog dan update status tiap menit atau bahkan detik setelah mereka mem-posting sebuah artikel.

Kecepatan.

Rata-rata waktu respon query kita kira-kira seperempat detik. Sebagai perbandingan, rata-rata berkedip mata adalah satu-sepersepuluh detik. Kecepatan adalah prioritas pencari utama, itulah sebabnya mengapa pada umumnya google tidak mengaktifkan fitur baru jika mereka akan memperlambat layanan google ke bawah. Sebaliknya, insinyur mesin pencari google selalu bekerja tidak hanya pada fitur baru, melainkan juga cara-cara untuk membuat pencarian lebih cepat. Selain smart coding, di belakang google telah mengembangkan sistem komputasi pendistribusian untuk memastikan Anda mendapatkan waktu respon yang cepat. Dengan teknologi seperti autocomplete dan Google Instan , google membantu menemukan istilah pencarian untuk hasil yang Anda cari, bahkan sebelum Anda selesai mengetik.Bagaimana proses pencarian pada Google :

                   Cara kerja Mesin Pencari Google

Salah satu inovasi utama adalah PageRank, sebuah teknologi yang menentukan "pentingnya" dari sebuah halaman web dengan melihat, apakah terdapat link halaman lain ke halaman web tsb berserta data lainnya? Google menggunakan lebih dari 200 sinyal, termasuk PageRank dan memperbarui algoritma ini setiap minggu. Sebagai contoh, google menawarkan hasil pencarian yang dipersonalisasi berdasarkan riwayat web Anda dan lokasi.

Kelengkapan.

Google diluncurkan pada tahun 1998 hanya dengan 25 juta halaman, saat itu merupakan sebagian kecil dari web. Kini google mempunyai indeks bermiliar-miliar halaman web, dan indeks google adalah sekitar 100 juta gigabyte. Google terus berinvestasi untuk menambah kelengkapan layanan kami. Pada tahun 2007 kami memperkenalkan Universal Search, yang membuat pencarian lebih komprehensif dengan mengintegrasikan gambar, video, berita, buku dan lebih ke hasil pencarian utama kami.

Kesegaran.

Pada masa awal, Googlebots merayapi Web setiap tiga atau empat bulan, yang berarti bahwa informasi yang Anda ditemukan di Google biasanya adalah dari per tanggal. Sekarang google terus merangkak Web memastikan bahwa Anda dapat menemukan berita terbaru, blog dan update status tiap menit atau bahkan detik setelah mereka mem-posting sebuah artikel.

Kecepatan.

Rata-rata waktu respon query kita kira-kira seperempat detik. Sebagai perbandingan, rata-rata berkedip mata adalah satu-sepersepuluh detik. Kecepatan adalah prioritas pencari utama, itulah sebabnya mengapa pada umumnya google tidak mengaktifkan fitur baru jika mereka akan memperlambat layanan google ke bawah. Sebaliknya, insinyur mesin pencari google selalu bekerja tidak hanya pada fitur baru, melainkan juga cara-cara untuk membuat pencarian lebih cepat. Selain smart coding, di belakang google telah mengembangkan sistem komputasi pendistribusian untuk memastikan Anda mendapatkan waktu respon yang cepat. Dengan teknologi seperti autocomplete dan Google Instan , google membantu menemukan istilah pencarian untuk hasil yang Anda cari, bahkan sebelum Anda selesai mengetik.

Tugas 2 

1.      Buatlah bahasa minimal 5 buah dengan aturan himpunan string terdiri dari n buah ≤ diikuti oleh n+2      ∑”

2.     

Jawaban :

1.      n=0 diikuti n+2 =1

a.      n =1 diikuti 0111

b.      n =2 diikuti 001111

c.       n =3 diikuti 00011111

d.      n =4 diikuti 0000111111

e.       n =5 diikuti 000001111111

2.  Diketahui :        S = {ﻍ,00,001,111}

       P ={ﻍ 101,111,001,11}

Ditanya : S union P  ??  

Maka S union P ={ﻍ ,00,001,101,11,111}

3.   Lakukan operasi konkatenasi di soal nomor 2 ?

   diketahui :

 S = {ﻍ,00,001,111}

 P ={ﻍ ,101,111,001,11}

Maka S konkatenasi P={00,001,101,11,111,00101,00111,00001,0011,001101,001111,001001,00111,111101,111111,111001,11111}

TUGAS 3 (DFSA/DFA) DAN TUGAS 4 (TEORI BAHASA DAN OTOMATA)

Deterministic Finite Automata

Finite State Automata (FSA)adalah model matematika yang dapat menerima input dan mengeluarkan output. FSA Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi. FSA  Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini. Mekanisme kerja dapat diaplikasikan FSA pada : elevator, text editor, analisa leksikal, pencek parity.

TUGAS 3

DFSA/DFA (Tugas 1 Teori Bahasa & Otomata)

1.)   Buatlah tabel transisinya

2.)   Bacalah input              

                                          a = abbabbaaa

                                          b = bbbabbaa

                                          c = ab

Jawaban : 

1.) Tabel Transisi : 

                   δ         a            b

        →     q0     q0,q2       q1

        *       q1     q1,q2       q2

                 q2        -           q0,q1

2.) Baca Inputnya menjadi :

a. Jika T diberi input abbabbaaa dengan State awal (q0, abbabbaaa), maka :

q0, abbabbaaa   ┣ T (q0, bbabbaaa)

                          ┣ T (q1, babbaaa)

                          ┣ T (q1, abbaaa)

                          ┣ T (q2, bbaaa)

                          ┣ T (q1,baaa)

                          ┣ T (q1,aaa)

                          ┣ T (q1,aa)

                          ┣ T (q1,a)

                          ┣ T (q1,e)

Karena (q0, abbabbaaa) ┣ * T jadi abbabbaaa diterima T

b. Jika T diberi input bbbabbaa dengan State awal(q0, bbbabbaa), maka :

q0, bbbabbaa      ┣ T (q1,bbabbaa)

                           ┣ T (q1,babbaa)

                           ┣ T (q1,abbaa)

                           ┣ T (q2,bbaa)

                           ┣ T (q0,baa)

                           ┣ T(q1,aa)

                           ┣ T(q1,a)

                           ┣ T (q1,e)

Karena (q0,bbbabbaa) ┣ * T jadi bbbabbaa diterima T

c. Jika T diberi input ab dengan State awal (q0,ab), maka :

q0, ab    ┣ T (q0,b)

              ┣ T (q1,e)

Karena (q0,ab) ┣ * T jadi AB diterima T

TUGAS 4

1.) Soal : 

Dari diagram state di atas tentukan :

  a. ABAAAAB

  b. BBBBAAA

  c. BABABAB

Jawaban : 

  a. ABAAAAB

                             

  b. BBBBAAA

  c. BABABAB

sumber : https://fairuzelsaid.wordpress.com/2011/05/01/teori-bahasa-dan-otomata-finite-state-automata/