Mengawali tahun baru, saya akan bercerita tentang hal yang pernah saya janjikan di tulisan sebelumnya yaitu implementasi canny edge detection. Algoritma canny edge detection merupakan salah satu teknik edge detection yang cukup populer penggunaannya dalam pengolahan citra. Salah satu alasannya adalah ketebalan edge yang bernilai satu piksel yang dimaksudkan untuk melokalisasi posisi edge pada citra secara sepresisi mungkin.
Algoritma canny edge detection secara umum (detilnya tidak baku atau bisa divariasikan) beroperasi sebagai berikut :
1. Penghalusan untuk mengurangi dampak noise terhadap pendeteksian edge
2. Menghitung potensi gradien citra
3. non-maximal supression dari gradien citra untuk melokalisasi edge secara presisi
4. hysteresis thresholding untuk melakukan klasifikasi akhir
Penghalusan citra
Biasanya teknik yang digunakan pada tahap ini adalah Gaussian Blur. Proses Gaussian Blur dapat dilakukan terhadap citra secara keseluruhan (hasil akhir berupa 1 citra baru), atau dilakukan terpisah (hasil akhir berupa dua buah citra yaitu blur horizontal dan vertikal). Hasil dari gaussian blur akan digunakan dalam langkah selanjutnya yaitu menentukan potensi gradien citra.
Menghitung potensi gradien citra
Gradien merupakan operator yang paling mendekati definisi dari sebuah edge. Oleh sebab itu dalam kuliah pengolahan citra, operator berbasis turunan menjadi materi pengantar. Ada dua buah operator yang akan saya sebutkan dalam tulisan ini yaitu operator Sobel dan Kirsch (silakan cari sendiri deskripsi kedua operator ini ;) ). Kedua operator ini mewakili dua buah pendekatan yang memiliki landasan ide yang berbeda dalam menghitung gradien.
Pada langkah menghitung potensi gradien citra ada dua buah informasi yang dibutuhkan yaitu kekuatan edge (edge strength/magnitude), dan arah edge (edge direction/orientation). Operator sobel memanfaatkan dua buah template edge pada dua arah tegak lurus (horizontal dan vertikal) dan menghitung arah edge dari arctangent kedua nilai tersebut. Lain halnya dengan operator Kirsch yang menggunakan template sebanyak delapan yang mewakili 8 arah sehingga orientasi edge dapat ditunjukkan oleh template dengan respon magnitudo terbesar.
Non-maximal Supression
Hasil penerapan operator gradien untuk menghitung potensi gradien di tahap sebelumnya tidak memberi informasi secara spesifik tentang lokasi dari edge yang dicari. Alternatifnya adalah menggunakan operator zero-crossing yang digunakan oleh algoritma deteksi Marr-Hildreth. Non-maximal supression bertujuan membuang potensi gradien di suatu piksel dari kandidat edge jika piksel tersebut bukan merupakan maksimal lokal pada arah edge di posisi piksel tersebut (di sinilah arah gradien diperlukan).
hysteresis thresholding
Hasil dari langkah non-maximal suppression adalah citra yang berisi kandidat edge serta intensitas dari kekuatan edge di posisi piksel tersebut. Langkah terakhir adalah thresholding atau klasifikasi tiap piksel apakah termasuk dalam kategori piksel edge atau tidak. Pada tahap ini bisa saja menggunakan threshold yang berdasarkan pada satu nilai tertentu. Namun pemilihan threshold yang hanya menggunakan satu nilai ini memiliki keterbatasan yaitu adanya kemungkinan piksel yang hilang padahal sebetulnya meruapakan piksel edge (false-negative) ataupun dimasukkannya piksel yang sebetulnya merupakan noise sebagai piksel edge (false-positive). Oleh sebab itu dalam melakukan klasifikasi tidak hanya diperlukan intensitas dari kekuatan edge sebagai pertimbangan namun juga topologi (keterhubungan antar-piksel) lokal dari piksel tersebut.
Sederhananya hysteresis thresholding adalah klasifikasi dengan dua buah nilai High-threshold dan Low-Threshold. suatu piksel disahkan sebagai piksel edge jika nilainya lebih besar atau sama dengan High-Threshold (thresholding umum) atau (di sini kaidah tambahannya) jika piksel tersebut memiliki intensitas kekuatan edge yang lebih besar dari Low-Threshold dan terhubung dengan piksel yang nilainya lebih besar dari High-Threshold. Untuk menentukan keterhubungan suatu piksel dengan piksel lainnya digunakan teknik yang dinamakan edge-linking yang pada dasarnya sama dengan flood-fill (di kuliah grafika).
Kode Implementasi
Kode berikut memanfaatkan definisi piksel (TWarnaRGB, PArrRGB), dan fungsi gaussian blur dari tulisan sebelumnya.
view source
print?
001 function canny( b: TBitmap ): TBitmap;
002 var
003 kv, kh : array[0..2, 0..2] of real;
004 i, j, k, l : integer;
005 p : array of PArrRGB;
006 mag, gx, gy : array of array of real;
007 bg, br : TBitmap;
008 dir : real;
009 tmp, dx, dy : integer;
010 pr : ParrRGB;
011 ap : array of TPoint;
012 edge : array of array of boolean;
013 pt : array of tpoint;
014 thrlow, thrhigh : real;
015
016 function trace( x, y: integer ): boolean;
017 var
018 i, j : integer;
019
020 function ok( x, y: integer ): boolean;
021 begin
022 result := ( x >= 0 ) and ( y >= 0 ) and ( x < b.Width ) and ( y < b.Height );
023 end;
024 begin
025 result := false;
026 if not edge[y][x] then exit;
027
028 edge[y][x] := false;
029 result := mag[y][x] >= thrhigh;
030 for j := -1 to 1 do
031 for i := -1 to 1 do
032 if ok( x + i, y + j ) then
033 result := trace( x + i, y + j ) or result;
034
035 //jika hasil rekursi menghasilkan true
036 //(terhubung dengan piksel yang nilainya lebih besar dari hi-threshold)
037 if result then begin
038 pr := br.ScanLine[y];
039 pr[x] := rgb_hitam;//citra yang baru berwarna latar putih
040 end;
041 end;
042 begin
043 bg := gaussian( b, 1 );
044 result := citra_create( b.Width, b.Height );//buat citra(bitmap) baru
045
046 setlength( p, b.Height );
047 for j := 0 to high( p ) do
048 p[j] := bg.ScanLine[j];
049
050 setlength( gx, b.Height );
051 for j := 0 to high( gx ) do
052 setlength( gx[j], b.Width );
053
054 setlength( gy, b.Height );
055 for j := 0 to high( gx ) do
056 setlength( gy[j], b.Width );
057
058 setlength( mag, b.Height );
059 for j := 0 to high( mag ) do
060 setlength( mag[j], b.Width );
061
062 setlength( edge, b.Height );
063 for j := 0 to high( edge ) do
064 setlength( edge[j], b.Width );
065
066 //hitung gradien gx dan gy menggunakan operator sobel
067 for j := 1 to b.Height - 2 do begin
068 for i := 1 to b.Width - 2 do begin
069 gy[j][i] := ( p[j + 1][i - 1].r - p[j - 1][i - 1].r ) + 2 * ( p[j + 1][i].r - p[j - 1][i].r ) + ( p[j + 1][i + 1].r - p[j - 1][i + 1].r );
070 gx[j][i] := ( p[j - 1][i + 1].r - p[j - 1][i - 1].r )
071 + 2 * ( p[j][i + 1].r - p[j][i - 1].r )
072 + ( p[j + 1][i + 1].r - p[j + 1][i - 1].r );
073 mag[j][i] := sqrt( gx[j][i] * gx[j][i] + gy[j][i] * gy[j][i] );
074 end;
075 end;
076
077 //non-maximal suppression
078 for j := 1 to b.Height - 2 do begin
079 for i := 1 to b.Width - 2 do begin
080 dir := arctan2( gy[j][i], gx[j][i] );
081 dx := round( cos( dir ) );
082 dy := round( sin( dir ) );
083
084 edge[j][i] := ( mag[j][i] >= mag[j + dy][i + dx] ) and ( mag[j][i] >= mag[j - dy][i - dx] );
085 if edge[j][i] then begin
086 edge[j + dy][i + dx] := false;
087 edge[j - dy][i - dx] := false;
088 end;
089 end;
090 end;
091
092 //apply hysteresis
093 thrlow := 10;
094 thrhigh := 90;
095 br := result;
096 for j := 1 to b.Height - 2 do begin
097 for i := 1 to b.Width - 2 do begin
098 if edge[j][i] then trace( i, j );//trace melakukan edge-linking
099 end;
100 end;
101 end;
hasil
Walaupun hasil canny edge detection dapat dibilang ‘baik’ namun terdapat kasus degenerasi yang terjadi jika terdapat “sudut pojok” sehingga disebut corner effect seperti pada contoh kasus citra berikut:
citra kasus efek pojok
Jika citra tersebut diterapkan operasi deteksi edge canny maka hasilnya akan sebagai berikut:
efek pojok
hasil canny edge detection untuk citra ujung
Tidak ada komentar:
Posting Komentar