Boundary Tracing

Akhirnya draftnya bisa tampil juga. Hari selasa (20071106) yang lalu ada kebutuhan untuk membuat kontur dari sebuah citra gradasi hingga harus menginap karena keesokan harinya akan dipakai. Persoalannya adalah pekerjaan yang harus dilakukan adalah salah satu tugas kuliah citra (IF 5041 Interpretasi dan Pengolahan Citra) yang dulu tidak saya kerjakan (mode nakal) yaitu Boundary Tracing. Akhirnya malam itu lebih tepatnya rabu dini hari saya terpaksa membuat dalam waktu singkat.

Istilah Boundary Tracing dalam kuliah citra lebih dikenal dengan nama ‘menyusuri pantai’. Jika diberikan sebuah citra (asumsi biner / hitam-putih), Maka keluaran yang harus dihasilkan adalah pola penelusuran dalam bentuk chain code, ataupun koleksi titik. Kebetulan untuk kasus yang harus saya kerjakan adalah koleksi titik (vektor).

Ide

Ide dari algoritma yang saya buat adalah sebagai berikut :

  • titik awal dan arah penelusuran sudah ditentukan sebelumnya
  • dalam setiap titik yang dikunjungi, dilakukan scan dari kiri ke kanan terhadap titik-titik yang berada dalam lingkungan ketetanggaan (8-tetangga atau 4 tetangga)
  • kunjungi tetangga pertama yang terlihat

Implementasi

const
  arah : array[0..7] of TPoint = ((x:0;y:-1),
    (x:1;y:-1),
    (x:1;y:0),
    (x:1;y:1),
    (x:0;y:1),
    (x:-1;y:1),
    (x:-1;y:0),
    (x:-1;y:-1));

{ fungsi pembantu }
function is_ok(x, y : integer; b : TBitmap):boolean;
begin
  result := (x>=0) and (x<b.Width) and (y>=0) and (y<b.Height);
end;

{ fungsi susur }
procedure trace_boundary(x, y : integer; b : Tbitmap);
  var
    current, next, p : TPoint;
    current_dir, next_dir : integer;
    i : integer;
    found : boolean;
    pb : array of PArrRGB;
    pa : PArrRGB;
  begin
    setlength(pb, b.Height);
    for i := 0 to high(pb) do pb[i] := b.ScanLine[i];
    current_dir := 2;
    current := Point(x, y);
    repeat
      found := false;
      { cek arah yang aksesibel }
      for i := -2 to 3 do begin
        { hitung alternatif posisi berikutnya }
        next_dir := (8+current_dir+i) mod 8;
        p := arah[next_dir];
        next := Point(current.X+p.X, current.Y+p.Y);
        if (is_ok(next.X, next.Y, b)) then
          {  kondisi berhenti  }
          with pb[next.Y][next.X] do begin
            if (r = 0) and (g = 255) then begin
              break;
            end
            else
            if (r = 255) then begin
              found := true;
              break;
            end;
          end;
      end;
      if found then begin
        { rekam jejak }
        setlength(reg, length(reg)+1);
        reg[high(reg)] := current;
        { tandai pixel yang sudah pernah dikunjungi }
        pb[current.Y][current.X] := wRGB(0, 255, 0);
        { pindah }
        current := next;
        current_dir := next_dir;
      end;
    until not found;
    { rekam posisi terakhir }
    setlength(reg, length(reg)+1);
    reg[high(reg)] := current;
  end;

Pembahasan

algoritma di atas masih banyak kelemahan, diantaranya jika mengunjungi titik ujung (hanya terhubung ke satu tetangga yang sebelumnya pernah dikunjungi), ketetanggaan terpisah/terputus. Intinya, algoritma ini masih sangat kasar (hajar bleh!), belum ada analisis terhadap penanganan kasus-kasus yang menyebabkan algoritma ini menjadi tidak berhasil mendeteksi batas luar.

Pengujian
citra asal
Gambar 1. Citra Asal

citra hasil (chaincode tidak ditampilkan)
Gambar 2. Citra hasil penelusuran pantai

9 comments

  1. tomy · Juli 15, 2008

    Ass. Wr. Wb

    makasih banyak dengan algoritmanya, sangat membantu dalam pengerjaan tugas aku..:)

  2. aiNa · Juli 20, 2008

    mas mau tanya….kemaren dah ai coba tapi PArrRGB koq error ya???katanya incompatible type gt….gmn solusinya?ai klo baca algoritmanya ngerti tapi kalo bikin ato tambah2 yang laen koq jadi bingung ya???ada saran kritik masukan?matur nuwun……………..

  3. aiNa · Juli 20, 2008

    oya error itu gni: pbnya koq gak jadi gak dikenal gmna?kalo diganti Pinteger gt gmn?

  4. pebbie · Juli 20, 2008

    @ai:definisi PArrRGB ada di tulisan saya berjudul ‘mengakses pixel’. memang bukan definisi bawaan dari delphi.

  5. aiNa · Juli 23, 2008

    mas pebbie mau tanya lagi………
    1. scanline itu fungsi sebenarnya buat apa ya mas???
    2. kemaren dah ai coba pada type ai tambah
    wRGB = packed record
    b, g, r : Byte;
    end;
    TArrRGB = array[0..65535] of wRGB;
    PArrRGB = ^TArrRGB; {seperti di mengakses pixel}
    tetapi koq masih banyak error?
    – setlength(reg, length(reg)+1);{Incompatible types}
    – reg[high(reg)] := current; {Array type required}
    – pb[current.Y][current.X] := wRGB(0, 255, 0); { ‘)’ expected but ‘,’ found}
    – ‘UNTIL’ expected but ‘END’ found dan ‘.’ expected but ‘;’ found

    hee…gmn itu mas????

  6. pebbie · Juli 23, 2008

    – setlength(reg, length(reg)+1);{Incompatible types}
    – reg[high(reg)] := current; {Array type required}
    – pb[current.Y][current.X] := wRGB(0, 255, 0); { ‘)’ expected but ‘,’ found}
    – ‘UNTIL’ expected but ‘END’ found dan ‘.’ expected but ‘;’ found

    memang kode yang dipake mbak ai seperti apa?

  7. mdboyz · Januari 29, 2009

    mas… mau nanya mengenai morfologi,gimana sih skrip delphi-nya morfologi secara dilasi pada citra biner?

  8. andrie · Maret 26, 2012

    mas ini pake bahasa bahasa apa ?
    terus ada source lengkapnya ???

    • pebbie · Maret 26, 2012

      ini pake Pascal (Delphi 7).

Tinggalkan Balasan

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

Logo WordPress.com

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

Gambar Twitter

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

Foto Facebook

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

Foto Google+

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

Connecting to %s