BAB 3 PERANCANGAN PROGRAM
3.1.
Gambaran Umum Perancangan Secara umum, program aplikasi fractal compression terdiri dari dua proses utama
yaitu proses kompresi dan proses dekompresi. Algoritma QPIFS yang digunakan pada proses kompresi adalah sebagai berikut :
1. create domain 2. for i = 1 to total range do steps (3), (4), (5), and (6) 3.
if range blok > tolerance then quadtree down
4.
else
5.
transform from domain to range, while distance (domain, range)<=rms)
6.
save best transform
7. end
Rms (root mean square) digunakan untuk menentukan jarak antara blok domain dan blok range, sedangkan tolerance digunakan untuk menentukan batas keseragaman pixel yang diterima pada tiap blok range. Berikut ini tahap-tahap yang dilakukan pada proses kompresi : 1.
Pembacaan file gambar untuk memeriksa apakah bit-bit data dapat dibaca
2.
Alokasi memori untuk proses dan penyimpanan data domain sesuai dengan jumlah domain yang dibuat.
30 3.
Gambar dibagi secara rekursif untuk memudahkan proses encoding dengan membagi menjadi empat kuadran melalui fungsi quadtree.
4.
Dilakukan proses quadtree hingga level enam, dengan asumsi pada level tersebut blok range sudah cukup kecil.
5.
Keempat kuandran diurutkan dari yang paling cerah, kemudian dilakukan transformasi pada masing-masing kuadran. Proses ini berulang untuk setiap kuadran dimulai dari level terdalam di kuadran NW (northwest) hingga kuadran SE (southeast).
6.
Hasil dari setiap transformasi tersebut kemudian dibandingkan dengan domain. Jika nilai perbandingan tersebut mendekati nilai perhitungan rms, maka transformasi dan posisi domain akan ditulis ke dalam file FIC.
7.
Tahap lima dan enam akan berulang untuk seluruh range yang ada dalam gambar hingga diperoleh kumpulan transformasi terbaik
Tahap-tahap proses dekompresi : 1.
Pembacaan transformasi yang disimpan pada file FIC.
2.
Penerapan transformasi pada domain yang dilakukan secara rekursif mulai dari kuadran terdalam hingga seluruh daerah gambar tertutup oleh pixel hasil transformasi
3.
Langkah terakhir adalah penghalusan gambar dengan membuat nilai ratarata dari dua pixel yang berdekatan pada setiap transformasi.
Gambaran yang lebih jelas tentang jalannya program dapat dilihat pada diagram alir berikut :
31
Gambar 3.1 Diagram alir proses kompresi
32
Gambar 3.2 Diagram alir proses dekompresi
3.2.
Modul-modul Perancangan Proses kompresi dan dekompresi tersebut di atas akan dijabarkan secara lebih
mendetil dengan pseudocode, begitu juga fungsi-fungsi atau prosedur-prosedur yang ada.
33 3.2.1. Modul Utama
Modul Frac Fungsi :
Merupakan modul utama yang didalamnya terdapat modul-modul untuk proses kompresi dan dekompresi. Modul ini juga akan menginisialisasi parameter yang digunakan saat pemanggilan kedua proses tersebut. Nilai parameter yang digunakan pada perancangan ini sesuai dengan nilai yang digunakan oleh Yuval Fisher yaitu, nilai toleransi jarak domain dan range adalah delapan, dengan asumsi pada nilai tersebut perbedaan pixel tidak signifikan, nilai
kedalaman
maksimal adalah enam, dengan asumsi pada level tersebut pixel yang terdapat pada blok tersebut sudah cukup seragam. Matriks transformasi yang digunakan dalam perancangan ini berupa matriks 2 x 24 sebagai berikut, 23 17 21 11 15 9 22 16 19 5 13 3 20 10 18 4 7 1 14 8 12 2 6 0 16 22 10 20 8 14 17 23 4 18 2 12 11 21 5 19 0 6 9 15 3 13 1 7 Sedangkan matriks rotasi yang digunakan adalah matriks 2 x 8 berikut, 7 4 5 6 1 2 3 0 2 3 0 1 6 7 4 5 8 nilai tersebut menunjukkan rotasi yang mungkin dilakukan pada sebuah blok dengan melakukan isometri sebagai berikut : 1. identitas (tanpa rotasi) 2. refleksi orthogonal terhadap sumbu tengah vertical blok
34 3. refleksi orthogonal terhadap sumbu tengah horosontal blok 4. refleksi orthogonal terhadap diagonal pertama 5. refleksi orthogonal terhadap diadonal kedua 6. rotasi pada pusat blok sebesar 90o 7. rotasi pada pusat blok sebesar 1800 8. rotasi pada pusat blok sebesar -900
Modul yang dipanggil : -
3.2.2. Modul Proses Compression Modul Compress Fungsi : Melakukan proses kompresi. Pseudocode : Begin Read the size of Raw file Call compute sum to compute the sum of pixel values in domain Call partition image function Close file free memory allocated to domain free memory allocated to image End
Modul yang dipanggil : Compute Sums, Partition Image.
35
Modul Compute Sums Fungsi :
Mengalokasikan memori untuk jumlah domain, memanggil modul Classify, membentuk domain dan menyimpan posisi domain ke dalam data domain.
Pseudocode : Begin allocate memory for number of horizontal domain & vertical domain allocate memory for the size of horizontal domain & vertical domain for (i=0; i<2; ++i) for (j=0; j<2; ++j) for (k=i; k
36 Modul yang dipanggil : Classify. Modul Partition Image Fungsi :
Membagi gambar menjadi bagian-bagian kecil, memanggil fungsi quadtree untuk encoding
Pseudocode : Begin Call Quadtree function If horizontal size != image size Then call Partition image function If vertical size != image size Then call Partition image function End
Modul yang dipanggil : Partition Image, Quadtree. Modul Quadtree Fungsi : Melakukan proses encoding, mencari transformasi terbaik, mencari domain terbaik, menghitung rms. Menyimpan hasil transformasi terbaik, faktor skala terbaik (ialpha) dan offset domain terbaik (ibeta) dalam satu file FIC. Pseudocode : Begin For quadtree depth = 1 to 6 Begin If x/2 & y/2 != 0 then
37 x=x & y=y to x=xsize/2 & y= ysize/2 Quadtree quadrant depth+1 If x/2 & y/2 != 0 then x=xsize/2 & y=y Quadtree quadrant depth+1 If x/2 & y/2 != 0 then x=0 & y= ysize/2 Quadtree quadrant depth+1 If x/2 & y/2 != 0 then x=xsize/2 & y=ysize/2 Quadtree quadrant depth+1 End Return; Call the Classify function For all domain block Transform domain to range Symmetrize operation = apply rotation matrix to domain block Best rms = 10,000,000,000 rms = Compare(domain,range) ; If (rms < best_rms) Then best transform =transform best_domain offset =domain offset best rms = rms best symetrize operation = symetrize operation best domain = domain End if End for
38 If (best_rms > tolerance & depth < 4) Then Begin If x/2 & y/2 != 0 then x=x & y=y to x=xsize/2 & y= ysize/2 Quadtree quadrant depth+1 If x/2 & y/2 != 0 then x=xsize/2 & y=y Quadtree quadrant depth+1 If x/2 & y/2 != 0 then x=0 & y= ysize/2 Quadtree quadrant depth+1 If x/2 & y/2 != 0 then x=xsize/2 & y=ysize/2 Quadtree quadrant depth+1 End Else Pack(best transform, best domain offset, best symmetrize operation,best domain); End if End
Modul yang dipanggil : Compare, Classify, Quadtree.
Modul Classify Quadrant Fungsi : Menghitung nilai rata-rata pixel pada range atau domain, mengurutkan pixel berdasarkan tingkat kecerahan. Pseudocode :
39 Begin If range area Then Begin For quadrant NW to SE Do Call the average1 function to compute the average value of each quadrant End Else Begin For quadrant NW to SE Do Call the average function to compute the average value of each quadrant End End if Repeat until NW < NE < SW < SE If sum i < sum i+1 then swap position End
Modul yang dipanggil : Average. Modul Average Fungsi : Menghitung nilai rata-rata pixel dalam satu kuadran Pseudocode : Begin For (i=x; i<x+xsize; ++i)
40 For (j=y; j
Modul yang dipanggil : -.
Modul Average1 Fungsi : Menghitung nilai rata-rata pixel dalam satu kuadran Pseudocode : Begin For (i=x; i<x+xsize; ++i) For (j=y; j
Modul yang dipanggil : -.
41 Modul Compare Fungsi : Menghitung nilai rms untuk membandingkan domain dan range. Rms dihitung dengan, Rms =
∑ [range( x, y) − domain( x, y)]
2
.
x, y
Pseudocode : Begin pialpha = 0.5 + (alpha + 1)/(2.0 x 1) x (scaling bits) if (pialpha < 0) pialpha = 0 if (pialpha >= scaling bits) pialpha = scaling bits-1 alpha = pialpha/ scaling bits x 2.0 x max scale – max scale beta = (sum – alpha x domain sum) / w2 if (alpha > 0.0) beta = beta + alpha x 256 best beta = 0.5 + beta/(1.0+ absolute alpha) x 256 x offset bits-1 if (best beta< 0) best beta = 0; if (best beta>= 1) best beta = offset bits-1 beta =best beta/offset bits-1 x 1.0+absolute alpha x256 if (alpha > 0.0) beta = beta – alpha x 256 Rms = sum 2 + α ×(α × dom sum 2 − 2 × rdsum + 2 × β × dom sum) + β × ( β × w2 − 2 × rsum) w2 Return rms End
Modul yang dipanggil : -.
42
3.2.3. Modul Proses Decompression
Modul Decompress Fungsi : Melakukan proses dekompresi, membaca file FIC , menginisialisasi gambar awal berupa gambar berwarna hitam dan memanggil fungsifungsi yang mendukung proses tersebut. Pseudocode : Begin Open FIC file Unpack byte; Allocate memory Clear memory buffer Initialize dummy image Call Read transformation function For i = 1 to total transformation do Begin Call the Apply Transformations function End Call the Smooth Image function End
Modul yang dipanggil : Read Transformation, Apply Transformation,
43 Smooth Image.
Modul Read Transformation Fungsi : Membaca transformasi pada file FIC Pseudocode : Begin If depth < 6 then Begin From x=0 & y=0 Quadtree (x/2, y/2) depth+1 From x=x+xsize/2 & y=0 Quadtree (x/2, y/2)depth+1 From x=0 & y= y+ysize/2 Quadtree (x/2, y/2) depth+1 From x=xsize/2 &y=ysize/2 Quadtree (x/2,y/2)depth+1 return; End If depth < 4 & Unpack = true Then Begin Read_Transformations(atx,aty, xsize/2, ysize/2, depth+1); Read_Transformations(atx+xsize/2,aty, xsize/2, ysize/2, depth+1); Read_Transformations(atx,aty+ysize/2, xsize/2, ysize/2, depth+1); Read_Transformations(atx+xsize/2,aty+ysize/2,xsize/2,ysize/2,depth+1); End Else if
44 m_trans = next transformation best transformation = Unpack (transformation bit); best domain offset = Unpack (offset bit); m_trans->scale = transformation; m_trans->offset = domain offset; End if End
Modul yang dipanggil : Read Transformation.
Modul Apply Transformation Fungsi : Menerapkan transformasi pada pixel hingga terbentuk sebuah gambar. Pseudocode : Begin m_trans = &m_transformations; While (next transformation != NULL) Begin m_trans = next transformation; imageDummy= m_trans->scale*pixel + m_trans->offset paint transformed pixel to screen End tempimage = m_image; m_image = m_imageDummy;
45 m_imageDummy = tempimage; End
Modul yang dipanggil : -.
Modul Smooth Image Fungsi :
menghitung nilai rata-rata
dari batasan transformasi untuk
memperhalus gambar hasil dekompresi. Pseudocode : Begin m_trans = &m_transformations; While (m_trans->next != NULL) Begin m_trans = m_trans->next; For for i = 1 to image size Do average =
pixel i + pixel (i + 1) sum of pixel
End End
Modul yang dipanggil : -. 3.3.
State Transition Diagram (STD) Rancangan
46
Layar utama
Klik compression
Klik close keluar dari program
Klik decompression
kompresi
dekompresi
Klik arrow down open file dialog
Klik arrow down open file dialog
Pilih file untuk dikompresi
Pilih file untuk didekompresi
Klik arrow down save file dialog
Klik arrow down open file dialog
Beri nama file output
Beri nama file output
Klik OK proses kompresi
Klik OK proses dekompresi
Gambar proses kompresi
Gambar hasil dekompresi
Gambar 3.3 STD Rancangan Program
3.4.
Rancangan Layar
3.4.1. Rancangan Layar Utama
Exit
47
Gambar 3.4 Rancangan layar utama
3.4.2. Open .raw , .dat dan.FIC
Gambar 3.5 Rancangan layar open .raw, .dat dan .FIC
3.4.3. Save As .FIC
48
Gambar 3.6 Rancangan layar Save As .FIC
3.4.4. Image Viewer
Gambar 3.7 Rancangan layer image viewer