Implementasi Canny Edge Detector

07Jan10

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.

function canny( b: TBitmap ): TBitmap;
var
  kv, kh            : array[0..2, 0..2] of real;
  i, j, k, l        : integer;
  p                 : array of PArrRGB;
  mag, gx, gy       : array of array of real;
  bg, br            : TBitmap;
  dir               : real;
  tmp, dx, dy       : integer;
  pr                : ParrRGB;
  ap                : array of TPoint;
  edge              : array of array of boolean;
  pt                : array of tpoint;
  thrlow, thrhigh   : real;

  function trace( x, y: integer ): boolean;
  var
    i, j            : integer;

    function ok( x, y: integer ): boolean;
    begin
      result := ( x >= 0 ) and ( y >= 0 ) and ( x < b.Width ) and ( y < b.Height );
    end;
  begin
    result := false;
    if not edge[y][x] then exit;

    edge[y][x] := false;
    result := mag[y][x] >= thrlow;
    for j := -1 to 1 do
      for i := -1 to 1 do
        if ok( x + i, y + j ) then
          result := trace( x + i, y + j ) or result;

    //jika hasil rekursi menghasilkan true 
    //(terhubung dengan piksel yang nilainya lebih besar dari hi-threshold)
    if result then begin
      pr := br.ScanLine[y];
      pr[x] := rgb_hitam;//citra yang baru berwarna latar putih
    end;
  end;
begin
  bg := gaussian( b, 1 );
  result := citra_create( b.Width, b.Height );//buat citra(bitmap) baru 

  setlength( p, b.Height );
  for j := 0 to high( p ) do
    p[j] := bg.ScanLine[j];

  setlength( gx, b.Height );
  for j := 0 to high( gx ) do
    setlength( gx[j], b.Width );

  setlength( gy, b.Height );
  for j := 0 to high( gx ) do
    setlength( gy[j], b.Width );

  setlength( mag, b.Height );
  for j := 0 to high( mag ) do
    setlength( mag[j], b.Width );

  setlength( edge, b.Height );
  for j := 0 to high( edge ) do
    setlength( edge[j], b.Width );

  //hitung gradien gx dan gy menggunakan operator sobel
  for j := 1 to b.Height - 2 do begin
    for i := 1 to b.Width - 2 do begin
      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 );
      gx[j][i] := ( p[j - 1][i + 1].r - p[j - 1][i - 1].r )
        + 2 * ( p[j][i + 1].r - p[j][i - 1].r )
        + ( p[j + 1][i + 1].r - p[j + 1][i - 1].r );
      mag[j][i] := sqrt( gx[j][i] * gx[j][i] + gy[j][i] * gy[j][i] );
    end;
  end;

  //non-maximal suppression
  for j := 1 to b.Height - 2 do begin
    for i := 1 to b.Width - 2 do begin
      dir := arctan2( gy[j][i], gx[j][i] );
      dx := round( cos( dir ) );
      dy := round( sin( dir ) );

      edge[j][i] := ( mag[j][i] >= mag[j + dy][i + dx] ) and ( mag[j][i] >= mag[j - dy][i - dx] );
      if edge[j][i] then begin
        edge[j + dy][i + dx] := false;
        edge[j - dy][i - dx] := false;
      end;
    end;
  end;

  //apply hysteresis
  thrlow := 10;
  thrhigh := 90;
  br := result;
  for j := 1 to b.Height - 2 do begin
    for i := 1 to b.Width - 2 do begin
      if edge[j][i] and (mag[y][x] >= thrhigh) then trace( i, j );//trace melakukan edge-linking
    end;
  end;
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

About these ads


21 Responses to “Implementasi Canny Edge Detector”

  1. nice info bgt ka, buat TA aku..
    setelah yg pas tugas pengcit gagal mengimplementasikan Canny, hehe..
    thx a lot

  2. ka peb mau nanya, itu threshold yg bawah ga kepake?
    mungkin di fungsi trace harusnya ada pengecekan dulu apa magnitudenya di bawah thrlow atau tidak..

    • 3 pebbie

      ah iya, makasi koreksinya

      mending ditambahin di fungsi trace aja

      result := result and (mag[y][x] >= thrlow);
      

      sebelum if result then…

  3. Nice for info mas …
    good luck yup ..

  4. 5 wulan

    ka peb, saya coba buat citra wajah, trus hasilnya ga baguuuus :(
    ada saran edge detector yg bagus buat citra wajah ga ka?

    • 6 pebbie

      gak bagusnya kayak apa n citra wajahnya dalam kondisi kayak apa lan? afaik, edge di citra wajah emang sensitif sama pencahayaan dan resolusi (termasuk koefisien untuk gaussian blur).
      klo teknik edge-detection lain setelah canny ada teknik yang basisnya
      - phase congruency (di homepagenya P. Kovesi)
      - fresnel diffraction (klo ga salah pernah baca di pattern rec. letters thn 2007 tapi belom sempet dimengerti)

  5. malam, berkunjung….kunjungi blogku ya. tukaran link juga ya.. Btw kok kelihatannya susah banget!!!

  6. Good Job Peebb … Lama tak jumpa di delphi-ID makin mahir ajj master …
    Sharing laghii dunk .. kali ini laplacian ama prewwit ya .. kalo bisa sekalian gabor + wavelet buat 3D nya … Hhe … Nice Tutorial master ;-)

  7. Aku juga pingin diskusi tentang pengolahan citra

  8. thanks to info,,,n suces tyuzzzz..,

  9. 11 Ibam

    peb, gw abis gugling “canny operator in android”, terus nemu blog http://winner-playnow.blogspot.com/2010/04/implementasi-canny-edge-detector.html , pas gw baca2 gw mikir “kok gaya ngomongnya kaya pebbie ya” -_-’

    jadilah gw gugling lagi paragraf2nya, taunya bener sumbernya dari sini -__-” empu blog itu nge-rip-off banyak blog2 lain juga ternyata :|

    • wah, sama persis :| thx infonya ya bam

  10. 13 sano

    mas bisa minta aplikasi jadinya g?soalnya binun kalo cmn sepenggal skript hehe..
    thanks

  11. 14 Sewa Mobil Bandung

    berat banget bahasannya gan, sumpah ane ngak faham,, Thanks infonya…

  12. wah mantab nih… apa boleh minta aplikasi langsung di delphi,.? terima kasih….

    • Waduh! maaf, kodenya bagian dari program lain yang lebih besar. silakan dicoba sendiri. gabung dengan kode di tulisan saya yang lain (tulisan tentang gaussian blur) dan tulisan berjudul “mengakses piksel”

  13. 17 widhi_candra@yahoo.com

    gan kalo ada moment invariant gan source code di delphi ,mohon bantuanya

  14. Hallo mas Pebbie…
    salam kenal, saya Nico, mau nanya mengenari rgb_hitam , kenapa saya ganti clBlack tidak bisa, atau saya ganti dgn n0l semua tidak bisa… mohon pencerahannya. Trimakasih.
    ohya satu lagi mas, di Unit Gaussian blur ada fungsi warna_create , mohon pencerahannya utk fungsi ini jg. Skali lagi Trimakasih Banyak atas pencerahannya.

    • coba cek http://pebbie.wordpress.com/2007/04/03/mengakses-pixel/

  15. Reblogged this on Leopoldlucky's and commented:
    just what im looking for.

  16. izin sedot mz, bwt TA ni, tnk!!!! bgus bgt….


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s


Ikuti

Get every new post delivered to your Inbox.

Bergabunglah dengan 2.078 pengikut lainnya.

%d bloggers like this: