Thinning Processing

Makalah Pengolahan Citra

Thinning Processing

Nama :    1. Muhamad Fitriansyah ( 54410577 )

2. Adry Genialdi (50410235)

Kelas      : 4IA11

UNIVERSITAS GUADARMA

2013

 Pengertian Pengolahan Citra

Pengolahan citra adalah setiap bentuk pengolahan sinyal dimana input adalah gambar, seperti foto atau video bingkai, sedangkan outputdari pengolahan gambar dapat berupa gambar atau sejumlah karakteristik atau parameter yang berkaitan dengan gambar. Kebanyakan gambar-teknik pemrosesan melibatkan atau memperlakukan foto sebagai dimensi dua sinyal dan menerapkan standar-teknik pemrosesan sinyal untuk itu, biasanya hal tersebut mengacu pada pengolahan gambar digital,tetapi dapat juga digunakan untuk optik dan pengolahan gambar analog. Akuisisi gambar atau yang menghasilkan gambar input di tempat pertama disebut sebagai pencitraan.

Pengolahan citra merupakan proses pengolahan dan analisis citra yang banyak melibatkan persepsi visual. Proses ini mempunyai ciri data masukan dan informasi keluaran yang berbentuk citra. Istilah pengolahan citra digital secara umum didefinisikan sebagai pemrosesan citra dua dimensi dengan komputer. Dalam definisi yang lebih luas, pengolahan citra digital juga mencakup semua data dua dimensi. Citra digital adalah barisan bilangan nyata maupun kompleks yang diwakili oleh bit-bit tertentu.

Umumnya citra digital berbentuk persegi panjang atau bujur sangkar (pada beberapa sistem pencitraan ada pula yang berbentuk segienam) yang memiliki lebar dan tinggi tertentu. Ukuran ini biasanya dinyatakan dalam banyaknya titik atau piksel sehingga ukuran citra selalu bernilai bulat. Setiap titik memiliki koordinat sesuai posisinya dalam citra. Koordinat ini biasanya dinyatakan dalam bilangan bulat positif, yang dapat dimulai dari 0 atau 1 tergantung pada sistem yang digunakan. Setiap titik juga memiliki nilai berupa angka digital yang merepresentasikan informasi yang diwakili oleh titik tersebut.

Format data citra digital berhubungan erat dengan warna. Pada kebanyakan kasus, terutama untuk keperluan penampilan secara visual, nilai data digital merepresentasikan warna dari citra yang diolah. Format citra digital yang banyak dipakai adalah Citra Biner (monokrom), Citra Skala Keabuan ( gray scale ), Citra Warna ( true color ), dan Citra Warna Berindeks.

Perangkat sistem pengolah citra dikelompokkan menjadi tiga bagian yaitu:

1. Perangkat keras (hardware)

2. Perangkat lunak (software)

3. Intelejensi manusia (brainware)

Ketiga pengelompokkan sistem pengolah citra tersebut sudah menjadi hal mutlak dalam pengolah citra. Dimana pada komputer-komputer saat ini sudah hampir dikatakan memenuhi standart spesifikasi untuk melakukan pengolahan citra. Namun kenyataanya masih banyak perangkat yang lainnya yang perlu kita lengkapi untuk melakukan pengolahan citra, bukan hanya sekedar komputer, melainkan perangkat-perangkat lainnya yang tidak include dalam sebuah komputer atau PC.

Operasi Pengolahan Citra

1.      Perbaikan kualitas citra(image enhacement)

Tujuan : memperbaiki kualitas citra dengan memanipulasi parameter-parameter citra.

Operasi perbaikan citra :

• •         Perbaikan kontras gelap/terang
• •         Perbaikan tepian objek (edge enhancement)
• •         Penajaman (sharpening)
• •         Pemberian warna semu(pseudocoloring)
• •         Penapisan derau (noise filtering)

2.      Pemugaran citra(image restoration)

Tujuan : menghilangkan cacat pada citra.Perbedaannya dengan perbaikan citra : penyebab degradasi citra diketahui.

Operasi pemugaran citra :

• •         Penghilangan kesamaran (deblurring)
• •         Penghilangan derau (noise)

3.      Pemampatan citra (image compression)

Tujuan : citra direpresentasikan dalam bentuk lebih kompak, sehingga keperluan memori lebih sedikit namun dengan tetap mempertahankan kualitas gambar (misal dari .BMP menjadi .JPG)

4.      Segmentasi citra (image segmentation)

Tujuan : memecah suatu citra ke dalam beberapa segmen dengan suatu kriteria tertentu.

Berkaitan erat dengan pengenalan pola.

5.      Pengorakan citra (image analysis)

Tujuan : menghitung besaran kuantitatif dari citra untuk menghasilkan deskripsinya. Diperlukan untuk melokalisasi objek yang diinginkan dari sekelilingnya

Operasi pengorakan citra :

• –        Pendeteksian tepi objek (edge detection)
• –        Ekstraksi batas (boundary)
• –        Represenasi daerah (region)

Rekonstruksi citra (Image recontruction)

Tujuan : membentuk ulang objek dari beberapa citra hasil proyeksi.

Aplikasi Pengolahan Citra dan Pengenalan Pola

•Bidang Perdagangan

–        Pembacaan bar codepada barang di supermarket

–        Pengenalan huruf/angka pada formulir secara otomatis

•Bidang Militer

–        Mengenali peluru kendali melalui sensor visual

–        Mengidentifikasi jenis pesawat musuh

•Bidang Kedokteran

–        Deteksi kanker dengan sinar X

–        Rekonstruksi foto janin hasil USG

•Bidang Biologi

–        Penenalan kromosom melalui gambar mikroskopik

•Komunikasi Data

–        Pemampatan citra transmisi

•Hiburan

–        Pemampatan video MPEG

•Robotika

–        Visual guided autonomous navigation

•Pemetaan

–        Klasifikasi penggunaan tanah melalui foto udara

•Geologi

–        Mengenali jenis bebatuan melalui foto udara

•Hukum

–        Pengenalan sidik jari

–        Pengenalan foto narapidana

Fungsi Pengolahan Citra ( Image Processing)

Pengolahan citra memiliki beberapa fungsi, diantaranya adalah:

-          Digunakan sebagai proses memperbaiki kualitas citra agar mudah diinterpretasi oleh manusia atau computer

–        Digunakan untuk Teknik pengolahan citra dengan mentrasformasikan citra menjadi citra lain

contoh : pemampatan citra (image compression)

–        Sebagai proses awal (preprocessing) dari komputer visi.

i      Selanjutnya >>

S

Thinning Processing

Pengertian Thinning

Thinning merupakan salah satu image processing yang digunakan untuk mengurangi ukuran dari suatu image (image size) dengan tetap mempertahankan informasi dan karakteristik penting dari image tersebut. Hal ini diimplementasikan dengan mengubah image awal dengan pola binary menjadi representasi kerangka (skeletal representation) image tersebut.

Thinning merupakan tahapan yang penting dalam proses image processing. Hal ini dikarenakan prosedur thinning memainkan peranan yang penting dalam suatu ruang lingkup yang luas dari masalah yang timbul dalam image processing. Ruang lingkup tersebut dapat bermula dari pengawasan otomatis dari sirkuit yang dicetak sampai pada penghitungan serat-serat asbes dalam penyaring udara.

Representasi kerangka dari suatu image—hasil dari proses thinning—memiliki sejumlah sifat dan ciri-ciri yang bermanfaat, diantaranya ukurannya yang kecil (karena pengurangan jumlah data dalam jumlah yang besar) dan pertahanan komponen struktur utama dari pola tersebut (komponen-komponen tersebut dapat digunakan pada saat penganalisaan bentuk).

Metodologi Image-Thinning

Metodologi dari thinning diartikan sebagai algoritma-algoritma atau prosedur-prosedur yang dapat digunakan untuk melakukan proses thinning tersebut. Suatu metode (algoritma/ prosedur) thinning yang baik seharusnya melindungi dan mempertahankan topologi, panjang, dan orientasi dari image yang di-thinning. Sementara itu, hasil proses thinning (skeletal representation) seharusnya mampu merepresentasikan fitur-fitur utama seperti penggabungan, pojok (sudut), dan titik akhir.

Secara umum, image-thinning berguna untuk mengurangi tresholded citra output yang dihasilkan dari edge detector, menjadi garis dengan ukuran ketebalan satu pixel saja. Untuk mewujudkan kegunaan ini, terdapat algoritma sederhana yang dapat diaplikasikan, yakni sebagai berikut:

Umpamakan semua piksel pada batas-batas daerah foreground (contohnya titik-titik pada foreground hanya memiliki satu background neighbour. Hapus semua titik yang memiliki foreground neighbour lebih dari satu. Lakukan berulang-ulang sampai konvergen.

Atau dengan rumus sederhana: thin (i, j) = i – hit -dan-miss (i, j)

Algoritma ini tidak bisa memberikan efek pada pixel-pixel di akhir garis. Cara ini dapat disempurnakan dengan cara melakukan hit-dan-miss dengan struktur elemen yang dirotasikan 90⁰.

Namun, selain dari algoritma sederhana di atas, masih terdapat beberapa jenis metodologi dari image-thinning yang diklasifikasikan sebagai berikut:

a.       berdasarkan tipe image yang akan dilakukan proses thinning.

1.      Binary Image Algorithm

2.      Gray-scale Image Algorithm

b.      berdasarkan unsur-unsur image yang dipertimbangkan untuk melakukan proses thinning.

1.      Local Algorithm

2.      Non-local Algorithm

c.       berdasarkan algortima matematika yang diterapkan dan hasil proses thinning yang dihasilkan.

1.      Stentiford thinning Algorithm

2.      Zhang Suen thinning Algorithm

3.      Simple Edge Detection thinning Algorithm

4.      Canny Edge Detection thinning Algorithm

5.   Combination

Dari tiga klassifikasi di atas, kami lebih menekankan proses thinning dengan metodologi berdasarkan tipe image (yakni Binary Image Algorithm dan Gray-scale Image Algorithm). Oleh karena itu, dalam makalah ini, kami akan membahas lebih mendetil mengenai kedua algoritma tersebut. Selain itu, kami juga akan memperlihatkan hasil proses thinning suatu image dengan mengimplementasikan kedua algoritma tersebut.

Adapun penjelasan dari tiap klasifikasi metodologi di atas adalah sebagai berikut:

A.          Berdasarkan tipe image yang akan dilakukan proses thinning.

Binary Image Algorithm

Seperti halnya operator morfologi lainnya, operasi thinning dipengaruhi oleh suatu struktur elemen. Struktur elemen biner yang digunakan dalam thinning adalah transformasi hit-dan-miss. (Mengenai struktur elemen dan transformasi hit-dan-miss akan dibahas pada bagian berikutnya).

Proses thinning dari suatu image i, dengan struktur elemen j, adalah:

thin (i, j) = i – hit -dan-miss (i, j)

dimana subtraksi (pengurangan) yang dilakukan disini adalah substraksi logik yang didefinisikan sebagai X-Y = X  NOT Y

         Gray-scale Image Algorithm

Gray-scale Thinning Algorithm diimplementasikan berdasarkan analisa binary image. Hal ini menyatakan bahwa untuk melakukan proses thinning pada gray-scale image, hal pertama yang harus dilakukan adalah meng-convert gray-scale image tersebut menjadi binary image terlebih dahulu. Proses ini dikenal dengan proses theresholding. Setelah itu, baru dapat dilakukan proses thinning sama seperti proses thinning pada binary image yang telah dijelaskan pada bagian sebelumnya. Dengan demikian:

gray-scale image algorithm

=  (gray-scale image convert to binary image--theresholding) +

 binary image algorithm

Dengan pendekatan ini (theresholding), algoritma penerapan thinning pada sebuah citra gray-scale menjadi tidak jauh berbeda dengan penerapannya pada citra biner. Yang membedakan keduanya hanyalah adanya proses thresholding pada tahap awal thinning untuk terlebih dahulu mengubah citra gray-scale tersebut menjadi sebuah citra biner.

Pada proses thresholding, ditetapkan suatu nilai batas / ambang, dimana elemen-elemen (piksel) pada citra yang nilainya lebih kecil daripada nilai batas tersebut ‘dimatikan’, dan elemen-elemen lainnya dianggap ‘menyala’, dan keduanya diubah nilainya sesuai statusnya (seperti dijelaskan pada bagian sebelumnya, kedua status ini hanya memiliki dua kemungkinan nilai, yaitu 0 atau 1).

Proses ini juga diterapkan dalam proses thinning citra berwarna, dengan terlebih dahulu mengubah citra berwarna (RGB) tersebut menjadi citra gray-scale. Hal ini dapat dilakukan dengan cara mengganti nilai setiap elemen dari citra berwarna dengan nilai rata-rata komponen merah, hijau, dan biru dari elemen tersebut.

Prinsip algoritma gray-scale thinning:

Kebanyakan gray-scale thinning algorithm dibangun untuk meng-extract objek dan menipiskannya untuk memisahkan dari image background.  Berikut adalah algoritma thinning untuk gray-scale image:

1. Layer Processing

Dalam hal ini kita anggap bahwa gray-scale image sebagai suatu set of layer dan proses dari setiap layer adalah binary image. Jika seluruh layer diproses secara sequential dari atas ke bawah maka hasil dari pemrosesan layer terakhir akan berkorespondensi terhadap pemrosesan seluruh gray-scale image.

2. Image Iteration

Image thinning terdiri dari 4 standard iterasi yaitu:

1. Utara
2. Selatan
3. Timur
4. Barat

3. Pixel Processing

Selama pixel processing, kita melakukan dua operasi utama yaitu: pixel analysis (bagaimana menganalisa pixel dan tetangganya) dan pixel value changing (bagaimana mengubah central pixel value).

A. Pixel Analysis

Thinning algorithm terdiri dari:

a. utara

b. selatan

c. timur

d. barat.

Kita gunakan kondisi berikut untuk iterasi. Pixel diubah jika terjadi kondisi berikut:

 

 pi adalah 8 tetangga

Tergantung dari sejumlah tetangganya, pixel yang menghasilkan gray skeleton masing-masing dikelompokkan sebagai end points, normal points dan branch points. End points dan branch points disebut feature point. Himpunan bagian dari skeleton yang dibatasi oleh feature points disebut dengan skeleton branch. Jika skeleton branch termasuk dalam end point maka itu disebut open branch, sedangkan yang lain disebut dengan closed branch. Ketika pixel analysis telah dilakukan, nilainya sebaiknya diubah, ini dapat dilakukan secara sequential maupun pararel.

B. Pixel Changing

pixel changing in sequential layer processing

Dalam bentuk ini, citra diproses dari layer dengan nilai maksimal ke yang lebih minimal.  Pixel untuk masing-masing layer memiliki lebih dari sebuah ambang yang ditentukan sebagi skeleton pixel, selain itu pixel ini termasuk dari background. Algorithma ini menghasilkan kualitas skeleton/kerangka yang bagus. Hasilnya bisa dilhat sebagai berikut:

Pixel changing in parallel layer processing

Pendekatan ini didasarkan pada proses yang secara serempak pada seluruh image latyer. Dalam kasus ini, pixel yang memenuhi kondisi diatas menurun 1. Hal ini menyebabkan penghilangan edge pixel dari setiap iterasi. Pengulangan dari iterasi ini, menghasilkan penurunan lapisan-lapisan ketika ini bukan skeleton element. Efek ini datang dari perbedaan kecepatan thinning layer. Hasilnya bisa dilihat sebagai berikut:

4.Skeleton binarisation

Pengubahan kerangka dalam bentuk binary dilakukan dalam satu image scan. Jika pixel yang dianalisa minimal memiliki satu dari empat neighbours-nya (p0,  p2, p4, p6) dengan nilai kurang dari nilai gray masing-masing atau seluruh 8 tetangganya adalah kurang dari nilai gray nya, maka nilai binernya berubah menjadi 1 atau berubah menjadi 0.

Selanjutnya >>

Thinning Processing

B.     Berdasarkan unsur-unsur image yang dipertimbangkan untuk melakukan proses thinning.

Local-algorithm merupakan metode, yang dalam implementasinya, hanya mempertimbangkan jendela ketetanggaan yang kecil dari suatu pixel.  Selanjutnya, berdasarkan pandangan yang terbatas tersebut, algoritma ini akan memutuskan keberadaan dari pixel tersebut (apakah pixel tersebut dibuang atau dipertahankan). Sebagian besar dari metodologi (algoritma) dalam melakukan proses thinning, dapat dikategorikan sebagai local-algorithm ini.

Sementara itu, dalam non-local algorithm, unsur-unsur yang dipertimbangkan mencakup ruang lingkup yang lebih luas. Adapun ciri khas dari pengimplementasian metodologi non-local ini adalah sebagai berikut:

a.       secara khusus mengkomputasi suatu representasi kerangka dari suatu kontur atau run-length encoding dari suatu image;

b.      mengaplikasikan suatu kombinasi dari informasi kerangka dan kontur;

c.       mempertimbangkan jendela ketetanggaan dari suatu pixel dalam memutuskan keberadaan dari pixel tersebut;

d.      mengaplikasikan suatu representasi grafik/ kurva.

C.    Berdasarkan algortima matematika yang diterapkan dan hasil proses thinning yang dihasilkan.

Stentiford dan Zhang Suen thinning Algorithm sama-sama menghasilkan garis-garis pixel pada pusat dari suatu daerah yang tebal (image yang akan diterapkan proses thinning).

Stentiford thinning Algorithm merupakan metode yang cenderung menghasilkan garis-garis yang mengikuti (sesuai dengan) kurva dengan baik, sehingga menghasilkan vektor-vektor yang secara akurat merefleksikan suatu image asli.

Zhang Suen thinning Algorithm merupakan metode yang cenderung memiliki kinerja yang lebih baik pada saat mengektrak garis-garis lurus dari suatu raster, sehingga dapat menghasilkan vektor-vektor yang bermanfaat dari suatu image asli. Vektor-vektor tersebut secara utama terdiri dari garis-garis lurus.

Simple dan Canny Edge Detection thinning Algorithm menghasilkan garis-garis pixel pada ujung (tepi) dari suatu daerah yang tebal. Simple dan Canny Edge Detection thinning Algorithm sama-sama merupakan metode yang melakukan deteksi terhadap ujung (tepi) dari suatu image. Secara prinsip, kedua metode ini memiliki persamaan-persamaan dalam melakukan proses thinning.

Adapun beberapa persamaan tersebut antara lain:

1.      Kedua Edge Detection thinning Algorithm ini sama-sama merupakan metode yang melakukan proses thinning dengan terlebih dahulu mencari ujung (tepi) dari suatu obyek.

2.      Kedua Edge Detection thinning Algorithm ini sama-sama sangat berguna dan sesuai untuk diterapkan pada image fotografik atau image yang terdiri dari daerah padat (tebal), dimana kita hanya ingin meng-vektor-kan garis besar (sketsa) dari image tersebut.

3.      Kedua Edge Detection thinning Algorithm ini sama-sama memiliki kinerja terbaik ketika diimplementasikan pada image yang memiliki tepi dengan perbedaan yang tinggi.

4.      Kedua Edge Detection thinning Algorithm ini sama-sama—pada saat implementasi—tidak melakukan proses thinning pada suatu image secara penuh. Hal ini mengakibatkan kita perlu melakukan metode lainnya (Stentiford, Zhang Suen, atau kombinasi thinning Algorithm)—setelah melakukan metode Edge Detection—untuk dapat melengkapi proses thinning pada image tersebut.

Sementara perbedaan kedua metode Edge Detection ini antara lain adalah:

1.      Canny Edge Detection thinning Algorithm memerlukan tambahan memory saat melakukan proses thinning, sementara metode Simple tidak memerlukannya. Metode Canny menggunakan memory dalam jumlah yang besar selama pemrosesan, sehingga metode ini tidak sesuai untuk raster¹ yang sangat besar atau keadaan dimana ukuran memory kecil.

2.      Canny Edge Detection thinning Algorithm menerapkan lebih banyak operasi matematikam dibandingkan metode Simple dan mempunyai setting optional yang dapat meningkatkan hasil thinning. (metode Canny jauh lebih rumit dibandingkan metode Simple).

Combination thinning algorithm menggunakan beberapa teori dari metode Stentiford dan Zhang Suen. Metode ini cenderung lebih baik diimplementasikan pada sudut yang bersiku-siku dibandingkan metode Steintiford dan Zhang Suen, dengan tetap mempertahankan pengenalan garis lurus yang baik dan kurva yang halus. Metode thinning ini akan memperpendek beberapa garis, yang mungkin akan kurang mendukung untuk citra-citra tertentu.

Ada beberapa komponen penting yang perlu diketahui dan dipahmai dalam melakukan proses thinning, seperti struktur elemen (kernel) dan tranformasi hit-dan-miss (hit-and-miss transformation).

Struktur elemen

Struktur elemen atau biasa disebut sebagai kernel, berisi pola yang mengkhususkan koordinat dari beberapa titik yang memiliki relatifitas yang sama ke suatu pusat (origin). Biasanya direpresentasikan menggunakan koordinat kartesian untuk setiap elemen sebagai kotak-kotak kecil. 

Contoh berbagai ukuran dari beberapa struktur elemen:

Origin tidak perlu harus di tengah, namun biasanya di tengah.           

Struktur elemen dengan ukuran 3 x 3 adalah yang paling banyak digunakan.

Setiap titik bisa memiliki nilai. Umumnya untuk mengoperasikan suatu binary image seperti erosion, keseluruhan element hanya memiliki sebuah nilai, yaitu 1 (satu). Pada thinning atau grayscale morphological operations  dapat memiliki nilai yang lain.

Pada kotak-kotak yang kosong, yang artinya tidak memiliki nilai, biasanya dire-presentasikan dengan menggunakan 0 (nol).

Ketika morphological operation dilakukan, origin dari structuring elements diposisikan pada setiap pixel pada citra input, lalu nilai dari structuring elements yang bersesuaian dibandingkan dengan nilai dari pixel citra. Detil dari perbandingan ini dan efeknya tergantung dari jenis operator, pada hal ini adalah structuring elements yang digunakan.

Transformasi hit -dan-miss

Transformasi hit-dan-miss adalah operasi morfologi yang umum yang dapat digunakan untuk memisahkan pola pixel-pixel foreground dan background pada suatu citra.

Operasi hit -dan-miss dilakukan dengan mentranslasikan struktur elemen ke seluruh pixel pada citra, kemudian membandingkan struktur elemen dengan pixel dari citra di bawahnya. Jika pixel-pixel foreground dan background pada struktur elemen cocok (match) dengan pixel-pixel foreground dan background pada citra, maka pixel yang berada di bawah struktur elemen di-set menjadi warna foreground. Jika tidak cocok, maka pixel tersebut dijadikan warna background. Pixel foreground dinyatakan dengan angka 1 dan pixel background dinyatakan dengan angka 0.

Contoh: struktur elemen berikut:

dapat digunakan untuk menemukan posisi sudut kanan (right angle convex corner) dari suatu citra. Untuk dapat menemukan semua sudut dalam citra biner, kita harus melakukan transformasi hit-dan-miss sebanyak empat kali dengan empat elemen berbeda yang merepresentasikan empat jenis sudut yang ditemukan dalam citra biner tersebut. Empat bentuk elemen tersebut adalah:

Setelah menemukan lokasi dari setiap orientasi sudut, kita kemudian melakukan operasi OR dari semua citra untuk mendapat hasil akhir yang menunjukkan lokasi dari semua sudut kanan pada orientasi apapun.

Citra dibawah ini menunjukkan proses hit-dan-miss yang dilakukan pada suatu citra biner sederhana.

1. Citra Biner

2. Citra Gray-scale

Tahap 3. Citra hasil setelah dilakukan proses thinning

Selanjutnya >>