Eksperimen Markov Random Field untuk Binerisasi Citra

20Sep11

Kemarin saya mencoba mengimplementasi Markov Random Field untuk mempelajari prinsip2 implementasinya. Sebetulnya agak bingung juga untuk membuat implementasinya karena kebanyakan referensi yang membahas topik ini penuh dengan notasi matematik dan istilah-istilah yang buat saya masih asing (mungkin pernah dengar tapi belum terlalu paham). Sampai akhirnya cari-cari dan nemu sampel kode dalam C++ dari situs hackchina. Markov Random Field (selanjutnya saya tulis MRF) atau jaringan markov adalah model probabilistik pada struktur graf tak berarah(graphical model). Berbeda dengan jaringan bayes (Bayesian Network) yang diajarkan di kuliah intelejensia buatan yang merupakan model probabilistik pada graf berarah. Prinsip yang digunakan pada MRF adalah optimasi energi. Setelah saya implementasi, saya merasa ada sedikit kemiripan dengan prinsip optimasi probabilistik pada Ant Colony Optimization.

Saya menggunakan MRF untuk memodelkan proses binerisasi citra. Masukan proses ini diasumsikan adalah citra grayscale. Memodelkan proses binerisasi citra menggunakan MRF dimulai dengan membuat model energi potensial terhadap clique (subgraf yang merupakan graf komplit) pada graf. Citra dianggap sebagai graf berstruktur grid dengan tiap piksel sebagai simpul dan terhubung dengan piksel tetangganya (saya menggunakan ketetanggaan 4 untuk menghubungkan antar piksel). Setiap konfigurasi pelabelan piksel dapat dievaluasi energinya secara keseluruhan sebagai jumlah dari energi pada tiap piksel. Pelabelan/Pewarnaan piksel yang optimal dicapai bila energi yang berasosiasi dengan konfigurasi tersebut adalah minimal terhadap pelabelan lainnya.

Karena saya sudah akrab dengan model optimasi berbasis populasi seperti algoritma genetik, ant colony, atau particle swarm saya tadinya berniat mencari konfigurasi pelabelan dengan menggunakan teknik ini. Niat ini kemudian saya urungkan karena malas membayangkan memori dan waktu yang diperlukan untuk mencari konfigurasi yang optimal (kalau N adalah besar populasi, maka perlu N citra tambahan untuk algoritma genetik dan 2N untuk PSO). Akhirnya dengan berat hati saya paksakan diri untuk mempelajari teknik optimasi dengan menggunakan Gibbs sampler.

Energi ini bisa dianalogikan sebagai risiko untuk menggunakan pelabelan yang dipilih. Saya menggunakan pairwise clique (subgraf yang terdiri dari 2 simpul) sebagai orde tertinggi untuk memodelkan energi potensial. Energi potensial pada tiap piksel adalah risiko nilai suatu piksel dibandingkan dengan ‘ground truth’ prior. ‘ground truth’ ini saya modelkan secara sederhana seperti thresholding menggunakan nilai mutlak 128. Energi potensial pada pasangan piksel merupakan smoothness prior yaitu estimasi risiko jika pelabelan suatu piksel terhadap tetangganya. secara keseluruhan, proses binerisasi ini mirip dengan proses binerisasi yang deterministik yang dilanjutkan dengan penghalusan.

Kode berikut adalah potongan prosedur yang saya buat di delphi. Beberapa bagian saya buang seperti misalnya pemodelan temperatur untuk proses sampling dan pembatasan pengulangan. Model Prior juga saya ganti dari yang berbasis statistik tiap label menjadi nilai mutlak.

procedure TForm1.do_mrf;
const N4            : array[0..3] of TPoint = ((X: - 1; Y: 0), (X: 1; Y: 0), (X: 0; Y: - 1), (X: 0; Y: 1));
const NLABEL        = 2;

var
  bi, bo            : TBitmap;
  i, j, k           : integer;
  p1, po            : array of PArrRGB;
  lf                : array of array of 0..NLABEL - 1; //labeling configuration
  cur_energy, z, r  : real;
  delta             : real;
  prev_energy, total_energy: real;
  step, max_step    : integer;
  Energy            : array[0..NLABEL - 1] of real;

  function Vc1(x, y, l: integer): real;
  {
    risiko jika label suatu pixel berbeda dari prior
  }
  begin
    result := abs(l * 255 - p1[y][x].r);//prior kecenderungan absolut
  end;

  function Vc2(x, y, l: integer): real;
  {
    risiko kalau suatu pixel diberi label berbeda dengan label tetangganya (pairwise clique)
  }
  var
    n               : integer;
    dl, dx          : real;
  begin
    result := 0;
    for n := 0 to 3 do begin
      dl := abs(lf[y + N4[n].Y][x + N4[n].X] - l);
      dx := abs(p1[y + N4[n].Y][x + N4[n].X].r - p1[y][x].r);
      result := result + dl * dx;
    end;
  end;

  function Vc(x, y, l: integer): real;
  {
    total risiko suatu pixel (x,y) diberi label l
  }
  begin
    result := Vc1(x, y, l) + Vc2(x, y, l);
  end;

  function calc_energy: real;
  {
    total risiko pelabelan seluruh piksel
  }
  var i, j          : integer;
  begin
    result := 0.0;
    for j := 1 to bo.Height - 2 do
      for i := 1 to bo.Width - 2 do
        result := result + Vc(i, j, lf[j][i]);
    result := result / (bo.Width * bo.Height);
  end;

  procedure initialize;
  {
    inisialisasi dengan nilai prior
  }
  var
    i, j, k         : integer;
    min_v, v        : real;
  begin
    for j := 1 to bo.Height - 2 do begin
      for i := 1 to bo.Width - 2 do begin

        min_v := MAXINT;
        for k := 0 to NLABEL - 1 do begin
          v := Vc1(i, j, k);
          if v < min_v then begin
            min_v := v;
            lf[j][i] := k;
          end;
        end;

      end;
    end;
  end;

  procedure display_output;
  var
    j, i, tmp       : integer;
  begin
    for j := 0 to bo.Height - 1 do begin
      for i := 0 to bo.Width - 1 do begin
        if lf[j][i] = 1 then tmp := 255 else tmp := 0;
        po[j][i] := warna_create(tmp, tmp, tmp);
      end;
    end;
    Image1.Picture.Bitmap.Assign(bo);
    Image1.Refresh;
  end;

begin
  //bi := citra_filter_mean(Image1.Picture.Bitmap, KMEAN);//pakai ini untuk kasus denoising citra biner
  bi := citra_make_greyscale(image1.picture.bitmap);
  bo := citra_clone(bi);

  setlength(p1, bi.Height);
  setlength(po, bo.Height);
  for j := 0 to bi.Height - 1 do p1[j] := bi.ScanLine[j];
  for j := 0 to bo.Height - 1 do po[j] := bo.ScanLine[j];

  setlength(lf, bo.Height);
  for j := 0 to bo.Height - 1 do setlength(lf[j], bo.Width);

  step := 0;
  max_step := 50;

  initialize;
  prev_energy := calc_energy;
  display_output;

  repeat
    //gibbs sampling on every site
    for j := 1 to bo.Height - 2 do begin
      for i := 1 to bo.Width - 2 do begin

        total_energy := 0;
        for k := 0 to NLABEL - 1 do begin
          Energy[k] := exp(-Vc(i, j, k));
          total_energy := total_energy + Energy[k];
        end;
        r := random;
        z := 0;
        for k := 0 to NLABEL - 1 do begin
          try
          z := z + Energy[k] / total_energy;
          except
            showmessage(format('TotalE=%f',[total_energy]));
          end;
          if z > r then begin
            lf[j][i] := k;
            break;
          end;
        end;

      end;
    end;
    
    display_output;

    cur_energy := calc_energy;
    delta := cur_energy - prev_energy;
    Caption := format('#%d E=%.5f', [step, delta]);
    prev_energy := cur_energy;

    inc(step);
  until (abs(delta) < 1e-3) or (step >= max_step);
  
  setlength(p1, 0);
  setlength(po, 0);
  for j := 0 to bo.Height-1 do setlength(lf[j], 0);
  setlength(lf, 0);
  bo.Free;
  bi.Free;
end;

Hasilnya bisa dilihat pada gambar berikut :

citra asal


citra biner menggunakan global threshold


citra biner menggunakan MRF


beda hasil threshold manual dengan MRF

Model MRF di atas (khususnya bagian prior 1-clique) tidak efektif untuk citra yang tidak terlalu kontras (misal citra teks yang pencahayaannya kurang bagus) atau pembersihan citra biner yang ber-noise seperti pada contoh berikut.

noisy

jika menggunakan model MRF seperti kode di atas hasilnya akan seperti ini.

noisy_mrf1

Untuk mengatasi kasus seperti itu, saya mencoba melakukan smoothing citra awal yang sudah biner menjadi grayscale menggunakan mean filter. sehingga hasil akhirnya menjadi seperti ini (cukup memuaskan).

noisy_mrf

MRF juga dapat diterapkan pada graf penalaran First-Order Logic (FOL) yang diberi atribut probabilitas pada tiap term-nya. Kombinasi FOL dengan MRF disebut juga sebagai Markov-Logic Network (MLN). Pada kasus MLN pelabelan dilakukan pada unifikasi term dan busur graf dimodelkan sebagai ketergantugan antar instansiasi dari term. MLN ini saya gunakan dalam riset untuk membaca tulisan tangan (handwriting recognition) sebagai mesin inferensi dengan memanfaatkan relasi spasial antar objek (region/titik kontur). Mudah-mudahan bisa diselesaikan segera supaya bisa saya bagikan di blog ini. ;)

About these ads


No Responses Yet to “Eksperimen Markov Random Field untuk Binerisasi Citra”

  1. Tinggalkan sebuah Komentar

Berikan 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.141 pengikut lainnya.

%d blogger menyukai ini: