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:

Jika citra tersebut diterapkan operasi deteksi edge canny maka hasilnya akan sebagai berikut:

hasil canny edge detection untuk citra ujung

About these ads

Filed under: delphi, image processing, programming   |  19 Komentar
Kaitkata:canny, edge detection