programer skripsi tesis tugas akhir

Tabu Search Dengan C# .Net

Contoh Program Tabu Search Dengan C# .Net

Tabu Search Dengan C# .Net

Tabu Search

Tabu Search merupakan single-solution based metaheuristik yang diperkenalkan oleh Fred Glover pada tahun 1986. Tabu search sangat popular di tahun 90an, dan sampai sekarang masih menjadi salah satu single-solution based metaheuristik yang banyak dipakai untuk menyelesaikan permasalahan optimisasi. Tabu search merupakan metode metaheuristik yang dilandaskan pada pencarian local (local search).

Tabu Search mempunyai tiga komponen penting:
  1. penggunaan struktur memori yang fleksibel, yang memungkinkan evaluasi kriteria dan informasi historis bisa di eksploitasi lebih baik dibandingkan dengan struktur memori yang statis.
  2. penggunaan mekanisme control yang didasarkan interaksi antara kondisi yang membatasi dan kondisi yang mendukung proses pencarian.
  3. penggabungan fungsi memori yang memiliki rentang waktu yang berbeda, dari memori jangka pendek sanpai dengan memori jangka panjang, untuk menerapkan strategi intensifikasi dan diversifikasi.
Untuk menghindari proses pencarian kembali ke kandidat solusi yang pernah dikunjungi, Tabu Search akan mengingat jalur pencarian yang telah dilewati. Kandidat solusi yang sudah dilewati akan disimpan dalam memori, yang disebut Tabu list, dan tidak akan dilewati lagi (karena itu disebut Tabu). Dalam setiap iterasi, memori ini akan diperbaharui. Akan tetapi, menyimpan semua solusi yang pernah ditemukan membutuhkan waktu dan kapasitas memori yang besar, karena dalam setiap iterasi harus dilakukan pencocokkan apakah suatu candidate solusi ada diantara Tabu list, sehingga Tabu list biasanya ditetapkan berukuran konstan dan berisi pergerakan yang Tabu atau Tabu moves (dan bukan solusi yang tabu).

Didalam menerapkan Tabu search, ada beberapa hal yang harus diperhatikan, yaitu:

  1. Tabu list : tujuan dari penggunaan Tabu list (memori jangka pendek) adalah untuk menghindari mengevaluasi kandidat solusi yang pernah dikunjungi sebelumnya. Akan tetapi, menampung semua kandidat solusi yang pernah dievaluasi kedalam Tabu list akan membuat Tabu search menjadi tidak efektif (memerlukan ukuran memori yang besar dan wakt yang lama untuk mengecek apakah suatu candidate solusi pernah dievaluasi atau belum).
  2. Aspiration criteria: umumnya diterapkan jika pergerakan tabu tersebut menghasilkan kandidat solusi yang memiliki nilai yang lebih baik daripada solusi terbaik yang telah dihasilkan.
  3. Intensifikasi (memori jangka menengah):  memori jangka menengah menyimpan sejumlah solusi yang berkualitas (elite solution) yang dihasilkan selama proses pencarian. Memori jangka menengah ini bertujuan untuk memberikan prioritas kepada atribut dari solusi berkualitas tersebut.
  4. Diversifikasi (memori jangka panjang): memori jangka panjang menyimpan infromasi tentang kandidat solusi yang pernah dikunjungi. Berdasarkan infromasi tersebut, memori ini dapat mengeksplorasi area dalam ruang pencarian yang belum dikunjungi.

Prosedure Tabe Search secara garis besar dapat di nyatakan sebagai berikut:



Contoh Program Tabu Search Dengan C# .Net

Berikut ini merupakan contoh program penerapan Tabu Search Dengan menggunakan C# .NET

TabuSearchProgram.cs




using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace TabuSearch
{
  class Program
  {
    // metode yang menghitung nilai fungsi tujuan
    static double vrijednostFunkcije(double x1, double x2)
    {
      // memanfaatkan untuk mengevaluasi fungsi
      double y = 1.8 * Math.Pow(x1, 2) + 0.04 * Math.Pow(x1, 4) - 0.55 * Math.Pow(x1, 3) + 2 * Math.Pow(x2, 2) + 5;      
      return Math.Round(y, 2);
    }

    // Metode poin pencetakan dan nilai-nilainya
    static void isprintajTacke(Tacka[,] myTacka)
    {
      for (int i = 0; i < 15; i++)
      {
        Console.WriteLine("Red br. {0}", i+1);
        for (int j = 0; j < 14; j++)
        {
          Console.WriteLine("({0},{1}): ({2},{3}) -> {4}", i, j, myTacka[i, j].x1, myTacka[i, j].x2, myTacka[i, j].vrijednost);
        }
        Console.WriteLine();
      }
    }

    static void Main(string[] args)
    {
      Console.WriteLine("Having Fun with Tabu Search Problem!");
      
      Tacka[,] myTacka = new Tacka[15,14]; // Array multidimensi objek Tacka (Point): (15-1) baris dan (14-1) kolom
      double[] arrX1 = { -3.0, -2.0, -1.0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // Data for Columns(x1): 14
      double[] arrX2 = {- 3.50, -3, -2.50, -2, -1.50, -1, -0.50, 0, 0.5, 1.0, 1.5, 2, 2.5, 3, 3.50 }; // Data for rows(x2): 15      
             
      for (int i = 0; i < 15; i++)  // Baris
      {
        for (int j = 0; j < 14; j++) // Kolom
        {
          myTacka[i, j] = new Tacka(arrX1[j], arrX2[i], vrijednostFunkcije(arrX1[j], arrX2[i])); // Kolona, Red, Vrijednost          
        }
      }
      // Mencetak semua poin dan nilai-nilainya
      isprintajTacke(myTacka);

      // Membuat Daftar Taboo
      TabuList<Tacka> myTabu = new TabuList<Tacka>();

      // Ukuran Daftar Taboo
      myTabu.TLL = 20; 
   
      // Mengkoordinasikan sistem
      KoordinatniSistem ks = new KoordinatniSistem(1,12); // (kolom, baris)   

      //Menambahkan nilai awal awal ke Daftar Taboo
      Tacka tmp = new Tacka(-2, 2.5, 29.74);
      myTabu.addTaboo(tmp);

      // Jumlah iterasi
      ks.brojIteracija = 30;

      // Minimum global yang awal di titik awal - Namun, itu berubah kemudian selama proses pencarian
      ks.global_min = tmp;

      Console.WriteLine("Writing the route!");
      Console.WriteLine("(X1, X2) -> Y\n");
   
      // Cari untuk minimum global
      ks.Pretraga(myTacka, myTabu);
             
      // Tampilkan hasil proses pencarian
      Console.WriteLine("Global minimum is: ({0},{1}) => {2}", ks.global_min.x1, ks.global_min.x2, ks.global_min.vrijednost);   
   // Minimum global ditemukan di beberapa jumlah iterasi adalah ...
      Console.WriteLine("Number of iterations: {0}", ks.brojIteracija);
      Console.ReadLine();
    }
  }
}



TabuList.cs



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TabuSearch
{
  public class TabuList&lt;T&gt; 
  {
    private Queue&lt;Tacka&gt; myQueue = new Queue&lt;Tacka&gt;();
    private int tabu_list_length;

    public int TLL
    {
      get { return tabu_list_length; }
      set { tabu_list_length = value; }
    }

    public void addTaboo(Tacka c)
    {
      if (myQueue.Count() &gt;= this.TLL)
      {
        this.removeTaboo();
      }
      myQueue.Enqueue(c);
    }

    public void removeTaboo()
    {
      myQueue.Dequeue();
    }

    public bool containsTaboo(Tacka c)
    {
      var x = from t in myQueue where t.x1 == c.x1 &amp;&amp; t.x2 == c.x2 &amp;&amp; t.vrijednost == c.vrijednost select t;
      return x.Count() &gt; 0;  
    }    
  }
}



IComparable.cs



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace TabuSearch
{
    public interface IComparable
    {
        int CompareTo(object o);
    }
}



KoordinatniSistem.cs



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace TabuSearch
{
   class KoordinatniSistem
   {
    private int x;
    private int y;
    private int broj_iteracija;
    private int trenutni_broj_iteracija = 1;
    public Tacka global_min = new Tacka(); 
 // variabel jenis Tacka untuk menyimpan koordinat 
 // dan nilai minimum global yang

    public KoordinatniSistem() { }

    // kolom, baris
    public KoordinatniSistem(int x1, int x2 )
    {
       x = x1; // kolom
       y = x2; // baris
    }

    public int SPx1 // kolom
    {
       get { return x; }
       set { x = value; }
    }
    public int SPx2 // baris
    {
       get { return y; }
       set { y = value; }
    }
    public int brojIteracija
    {
       get { return broj_iteracija; }
       set { broj_iteracija = value; }
    }

    public void Pretraga(Tacka[,] myTacka, TabuList&lt;Tacka&gt; myTabu)
    {
       // Array multidimensi sementara objek Tacka
       Tacka[] tempTacka = new Tacka[8];
       int k1 = 0;
       for (int i = -1; i &lt;= 1; i++)    
       {
        for (int j = -1; j &lt;= 1; j++)  
        {           
           if (i == 0 &amp; j == 0)    
           { continue; }           
           else
           {   
            try 
            {
               tempTacka[k1] = new Tacka(myTacka[SPx2 + j, SPx1 + i].x1, myTacka[SPx2 + j, SPx1 + i].x2, myTacka[SPx2 + j, SPx1 + i].vrijednost);
               k1++;
            }
            catch // Jika di perbatasan sistem koordinat
            { 
               tempTacka[k1++] = new Tacka(0,0,0); 
            } 
           }           
        }
       }
       // Sorting array sementara
       try
       {   Array.Sort(tempTacka);  }
       catch (Exception e)
       {   Console.WriteLine(e.Message);   }
       
       // Menampilkan poin lingkungan, diurutkan berdasarkan nilai-nilai fungsi tujuan - OPTIONAL
       // ispisTempTacaka(tempTacka);

       // Melewati array sementara
       foreach(Tacka t in tempTacka)
       {
        if (t.vrijednost == 0)  // Kondisi yang nilai titik sementara tidak sama dengan 0
        { continue; }
        else 
        {
           if (myTabu.containsTaboo(t))
           {   // Kondisi yang nilai titik sementara tidak dalam daftar Taboo  
           }
           else 
           {
            // Jika nilai titik sementara memiliki nilai yang lebih kecil dari minimum global yang ditetapkan sebelumnya, nilai minimum global diperbarui
            if (t.vrijednost &lt; global_min.vrijednost)
               { global_min = new Tacka(t.x1, t.x2, t.vrijednost); }

            // Tampilan poin melalui proses pencarian berjalan! Membuat rute!
            Console.WriteLine(&quot;({0},{1}) -&gt; {2}&quot;,t.x1,t.x2,t.vrijednost);
            myTabu.addTaboo(t);        //   Jika tidak, tambahkan titik dari array temporarnog dalam daftar Tabu dan segera menghentikan :)
            this.SPx1 = lociranjeSPX1(t);   //   Pengaturan koordinat x1
            this.SPx2 = lociranjeSPX2(t);   //   Pengaturan koordinat x2
            // Kaunter yang penting di mana kita iterasi dan berhenti di set
            if (trenutni_broj_iteracija ==  broj_iteracija)     
            { break; }
            else 
            {
               trenutni_broj_iteracija++;               
               Pretraga(myTacka, myTabu);
            }
            
            break;
           }           
        }
       }
       

    }



    public void ispisTempTacaka(Tacka[] tempTacka)
    {
       // Loop untuk mencetak nilai yang dipilih poin sekitarnya (x1, x2)
       foreach (Tacka t in tempTacka)
       { Console.WriteLine(&quot;({0},{1}) \t -&gt; {2}&quot;, t.x1, t.x2, t.vrijednost); }
       Console.WriteLine(&quot;------------------&quot;);
    }

    int lociranjeSPX1(Tacka t)
    {
       double[] arrX1 = { -3.0, -2.0, -1.0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
       int r = 0;
       for (int i = 0; i &lt; arrX1.Length; i++)
       {
        if (t.x1 == arrX1[i])
        { r = i; }
       }
       return r;
    }

    int lociranjeSPX2(Tacka t)
    {
       double[] arrX2 = { -3.50, -3, -2.50, -2, -1.50, -1, -0.50, 0, 0.5, 1.0, 1.5, 2, 2.5, 3, 3.50 }; 
       int r = 0;
       for (int i = 0; i &lt; arrX2.Length; i++)
       {
        if (t.x2 == arrX2[i])
        { r = i; }
       }
       return r;
    }
   
   }
}



Metode Tabu Search C/C++

Contoh Program Metode Tabu Search C/C++

Metode Tabu Search C/C++

Dalam metode Tabu Search, dalam rangka meningkatkan efisiensi proses eksplorasi, beberapa informasi sejarah yang berkaitan dengan evolusi pencarian disimpan (pada dasarnya jadwal melalui solusi mengunjungi). Informasi tersebut akan digunakan untuk memandu pencarian dari satu solusi untuk yang berikutnya menghindari bersepeda. Ini adalah salah satu fitur yang paling penting dari algoritma ini.

Mengingat sebuah contoh x, algoritma dimulai dari solusi awal (biasanya satu random). Pada iterasi setiap memiliki untuk menemukan solusi baru dengan membuat gerakan lokal atas solusi saat ini. The `` solusi berikutnya '' adalah yang terbaik di antara semua (atau bagian dari) solusi yang mungkin di lingkungan. Untuk melaksanakan proses eksplorasi, solusi baru saja mengunjungi harus dihindari. Untuk tujuan ini daftar tabu dipertahankan. Oleh karena itu sekali solusi dikunjungi gerakan dari yang diperoleh dianggap tabu. Catatan yang akan berubah seiring eksplorasi, sehingga dalam arti tertentu kita memiliki lingkungan yang dinamis dibandingkan dengan algoritma pencarian lokal sebelumnya di mana tetap statis.

Biasanya ada dua jenis daftar tabu, memori jangka panjang mempertahankan sejarah melalui semua proses eksplorasi secara keseluruhan dan memori jangka pendek untuk menjaga gerakan tabu yang terakhir dikunjungi. Sebuah gerakan dengan status tabu (gerakan tabu) dihindari untuk diterapkan, kecuali memenuhi kriteria aspirasi tertentu. Ini bertujuan untuk menghindari jatuh ke optima lokal.

Mengingat bahwa ukuran daftar tabu adalah tetap sebelum tangan setiap elemen dari daftar milik untuk sejumlah iterasi dibatasi oleh diberikan nilai maksimum dan minimum. Kerangka termasuk dalam dokumentasi ini menerapkan opsi ini. Nilai maksimum dan minimum yang diberikan oleh pengguna.

Ada dua macam kondisi dalam algoritma Tabu Search berhenti. Yang pertama harus dilakukan dengan Tabu Search secara keseluruhan (ketika algoritma selesai) dan yang kedua adalah kondisi berhenti selama pencarian dari `` yang terbaik '' di antara semua solusi.

Beberapa kondisi berhenti khas adalah sebagai berikut: kosong, jumlah maksimum solusi untuk dijelajahi adalah tetap, jumlah iterasi sejak perbaikan terakhir adalah lebih besar dari jumlah yang ditentukan, jumlah iterasi dari algoritma TS adalah tetap.

Pelaksanaan kerangka Tabu Search

Merupakan implementasi dari Tabu Search kerangka menggabungkan fitur baru telah dilakukan pada bulan-bulan terakhir. Implementasi ini memungkinkan pengguna untuk menentukan dengan mudah bagaimana mengintensifkan dan diversifikasi pencarian. Dalam rilis sebelumnya kerangka titik ini tidak eksplisit. Kedua funcionalitites (intensifikasi dan diversifikasi) yang dalam metode Tabu Search tetapi tidak sepenuhnya tetap di mana untuk menerapkannya. Semua algoritma mengacu Tabu Search aplikasi yang telah kita lihat melakukannya dengan cara tersembunyi (pada dasarnya beacause mereka implementasi ad hoc). Kami telah membuat fungsi ini secara eksplisit dan menerapkannya dalam cara yang terstruktur.

Diagram berikut menunjukkan bagaimana fungsi ini telah dimasukkan dalam versi saat ini kerangka dari Tabu Search :

Metode Tabu Search
Metode Tabu Search

Contoh Program Tabu Search Dengan C++

TabuSearch.cc



#include "TabuSearch.hh"
#include "TabuSearch.imp.hh"


namespace TabuSearch
{

   SetUpParams::SetUpParams ()
   {
   }
  ostream& operator<< (ostream& os, const SetUpParams& setup)
   {
      os << "CONFIGURATION -------------------------------------------" << endl << endl;
      os << "\t" << "nb.indep. runs : " << setup.independent_runs    << endl;
      os << "\t" << "nb.iterations  : " << setup.nb_iterations       << endl;
      os << "\t" << "delta function : " << setup.use_delta_function  << endl;
      os << "\t" << "known subopt.  : " << setup.known_suboptimum    << endl;
      os << "\t" << "max.neighbors  : " << setup.max_neighbors       << endl;
      os << "\t" << "tabu size      : " << setup.tabu_size           << endl;
      os << "\t" << "min.tabu status: " << setup.min_tabu_status     << endl;
      os << "\t" << "max.tabu status: " << setup.max_tabu_status     << endl;
      os << "\t" << "max.repetitions: " << setup.max_repetitions     << endl;
      os << "\t" << "nb.diversific. : " << setup.nb_diversifications << endl;
      os << "\t" << "nb.intensific. : " << setup.nb_intensifications << endl << endl;

      return os;
   }

   istream& operator>> (istream& is, SetUpParams& setup)
   {
      is >> setup.independent_runs;
      is >> setup.nb_iterations;
      is >> setup.use_delta_function;
      is >> setup.known_suboptimum;
      is >> setup.max_neighbors;
      is >> setup.tabu_size;
      is >> setup.min_tabu_status;
      is >> setup.max_tabu_status;
      is >> setup.max_repetitions;
      is >> setup.nb_diversifications;
      is >> setup.nb_intensifications;
      return is;
   }
  opacket& operator<< (opacket& op, const SetUpParams& setup)
   {
      return op;
   }
  ipacket& operator>> (ipacket& ip, SetUpParams& setup)
   {
      return ip;
   }

  Problem::Problem ()
   {
   }
  Direction Problem::direction() const
   {
      return minimize;
   }
  Problem& Problem::operator= (const Problem& pbm)
   {
      return *this;
   }
  bool Problem::operator== (const Problem& pbm) const
   {
      return false;
   }
  bool Problem::operator!= (const Problem& pbm) const
   {
      return !((*this)==pbm);
   }
  ostream& operator<< (ostream& os, const Problem& pbm)
   {
      return os;
   }
  istream& operator>> (istream& is, Problem& pbm)
   {      
      return is;
   }
  opacket& operator<< (opacket& op, const Problem& pbm)
   {
      return op;
   }
  ipacket& operator>> (ipacket& ip, Problem& pbm)
   {
      return ip;
   }   

  Solution::Solution (const Problem& pbm)
   {
   }

   
   void Solution::initial_solution()
   {
   }
   
   
   void Solution::escape() 
   {
   }
  double Solution::fitness () const
   {
      double cost=0.0;

      return cost;
   }
  double Solution::delta (const Movement& mov) const
   {
      double differential=0.0;
      
      return differential;
   }
  bool Solution::aspiration (const Movement& mov, const TabuStorage& ts,
                        const State& state) const
   {
      bool aspirated=false;

      return aspirated;
   }
  void Solution::apply (const Movement& mov)
   {
   }
  void Solution::unapply (const Movement& mov)
   {
   }
  void Solution::penalize()
   {
   }
  void Solution::unpenalize()
   {
   }
   
   void Solution::reward()
   {
   }
  void Solution::unreward()
   {
   }

   Solution& Solution::operator= (const Solution& sol)
   {
      return *this;
   }
  bool Solution::operator== (const Solution& sol) const
   {
      bool equal=false;
   
      return equal;
   }
  bool Solution::operator!= (const Solution& sol) const
   {
      return !((*this)==sol);
   }
  ostream& operator<< (ostream& os, const Solution& sol)
   {
      return os;
   }
  istream& operator>> (istream& is, Solution& sol)
   {
      return is;
   }
  opacket& operator<< (opacket& op, const Solution& sol)
   {
      return op;
   }
  ipacket& operator>> (ipacket& ip, Solution& sol)
   {
      return ip;
   }

  Movement::Movement ()
   {
      tabulife = 0;
   }
  void Movement::generate()
   {
   }
  void Movement::invert ()
   {
   }
  Movement& Movement::operator= (const Movement& mov)
   {
      return *this;
   }
  bool operator== (const Movement& mov1, const Movement& mov2)
   {
      bool equal = false;
      
      return equal;
   }

   bool operator!= (const Movement& mov1, const Movement& mov2)
   {
      return !(mov1==mov2);
   }
  ostream& operator<< (ostream& os, const Movement& mov)
   { 
      return os;
   }
  istream& operator>> (istream& is, Movement& mov)
   {
      return is;
   }
  opacket& operator<< (opacket& op, const Movement& mov)
   {
      return op;
   }
  ipacket& operator>> (ipacket& ip, Movement& mov)
   {
      return ip;
   }

  UserStatistics::UserStatistics()
   {
   }
  ostream& operator<< (ostream& os, const UserStatistics& ustat)
   {
      return os;
   }
  opacket& operator<< (opacket& op, const UserStatistics& ustat)
   {
      return op;
   }

   bool choose_best_move (const Problem& pbm, const Solution& sol,
                          const SetUpParams& setup, const TabuStorage& ts, 
                     const State& state, Movement& mov)
   {
      bool found=false;
      
      return found;
   }
  bool choose_best_all (const Problem& pbm, const Solution& sol,
                    const SetUpParams& setup, const TabuStorage& ts, 
                    const State& state, Movement& mov)
   {
      bool found=false;

      return found;
   }
  bool terminateQ (const Problem& pbm, const Solution& sol,
                   const SetUpParams& setup, const int current_iter)
   {
      return (current_iter >= setup.nb_iterations);
   }
}

TabuSearch.hh




#ifndef INC_USR_TABUSEARCH
#define INC_USR_TABUSEARCH

#include <iostream.h>
#include <mallba/iopacket.hh>
#include <LEDA/list.h>


namespace TabuSearch {

  class Movement;
  class TabuStorage;
  class State;
//  class Tabu2List;

  class SetUpParams {
  
 public:

   int    independent_runs;
   int    nb_iterations;   // 1000*N
   bool   use_delta_function;
   double known_suboptimum;
   int    max_neighbors;
   int    tabu_size;    // n/2...3n/2
   int    min_tabu_status;
   int    max_tabu_status;
   int    max_repetitions;   // 100*N
   int    nb_diversifications; // 10*N;
   int    nb_intensifications; // 10*N;

   SetUpParams ();

   friend ostream& operator<< (ostream& os, const SetUpParams& setup);
   friend istream& operator>> (istream& is, SetUpParams& setup);
   friend opacket& operator<< (opacket& op, const SetUpParams& setup);
   friend ipacket& operator>> (ipacket& ip, SetUpParams& setup);
  };

  enum Direction { minimize = -1, maximize = 1 };
  class Problem {
 public:

   Problem ();
   Direction direction () const;

   Problem& operator=  (const Problem& pbm);
   bool     operator== (const Problem& pbm) const;
   bool     operator!= (const Problem& pbm) const;

   friend ostream& operator<< (ostream& os, const Problem& pbm);
   friend istream& operator>> (istream& is, Problem& pbm);
   friend opacket& operator<< (opacket& op, const Problem& pbm);
   friend ipacket& operator>> (ipacket& ip, Problem& pbm);
  };

  class Solution {
   public:
   Solution (const Problem& pbm);
   void   initial_solution();
   void   escape();
   
   double fitness () const;
   double delta (const Movement& mov) const;
   bool   aspiration (const Movement& mov, const TabuStorage& ts, const State& state) const;

   void   apply ( const Movement& mov );
   void   unapply ( const Movement& mov );

   void   penalize();
   void   unpenalize();
   
   void   reward();
   void   unreward();

   Solution& operator=  (const Solution& sol);
   bool      operator== (const Solution& sol) const;
   bool      operator!= (const Solution& sol) const;

   friend ostream& operator<< (ostream& os, const Solution& sol);
   friend istream& operator>> (istream& is, Solution& sol);
   friend opacket& operator<< (opacket& op, const Solution& sol);
   friend ipacket& operator>> (ipacket& ip, Solution& sol);
  };

  class Movement {

 public:

   int tabulife;

   Movement ();

   void generate ();
   void invert ();

   Movement& operator= (const Movement& mov);
   friend bool operator== (const Movement&, const Movement&);
   friend bool operator!= (const Movement&, const Movement&);
   
   friend ostream& operator<< (ostream& os, const Movement& mov);
   friend istream& operator>> (istream& is, Movement& mov);
   friend opacket& operator<< (opacket& op, const Movement& mov);
   friend ipacket& operator>> (ipacket& ip, Movement& mov);
  };
  
  class TabuStorage {

 private:
 
   const SetUpParams& config;
   const Problem&     problem;
   list<Movement>     tlist;

 public:

   TabuStorage (const SetUpParams& setup, const Problem& pbm);
       
   bool is_in_tabu_storage (const Movement& mov, const Solution& sol, const State& state) const;
   bool is_tabu (const Movement& mov, const Solution& sol, const State& state) const;
   void make_tabu (Movement& mov, const Solution& sol, const State& state);
   void make_tabu_inv (Movement& mov, const Solution& sol, const State& state);
   void update ();   
   int  size () const;
  };

  class UserStatistics {

  public:

   int total_nb_tabu_moves;
   int total_nb_explored_moves;

   UserStatistics ();

   friend ostream& operator<< (ostream& os, const UserStatistics& ustat);
   friend opacket& operator<< (opacket& op, const UserStatistics& ustat);
  };

  bool choose_best_move (const Problem& pbm, const Solution& sol, 
       const SetUpParams& setup, const TabuStorage& ts,
     const State& state, Movement& mov);

  bool choose_best_all (const Problem& pbm, const Solution& sol, 
      const SetUpParams& setup, const TabuStorage& ts,
    const State& state, Movement& mov);

  bool terminateQ (const Problem& pbm, const Solution& sol, const SetUpParams& setup,
         const int current_iter);
}

#endif




Algoritma Rijndael AES Advanced Encryption Standard

Contoh Program Algoritma Rijndael AES Advanced Encryption Standard

Algoritma Rijndael AES Advanced Encryption Standard

Algoritma Rijndael

Seperti pd DES, Rijndael memakai substitusi & permutasi, & sejumlah putaran (cipher berulang) – setiap putaran mengunakan kunci internal yg berbeda (kunci setiap putaran disebut round key). Tetapi tidak seperti DES yg berorientasi bit, Rijndael beroperasi dalam orientasi byte (untuk memangkuskan implementasi algoritma ke dalam software & hardware).

Garis besar Algoritma Rijndael yg beroperasi pd blok 128-bit dng kunci 128-bit adl sebagai berikut (di luar proses pembangkitan round key):

AddRoundKey: melakukan XOR antara state awal (plainteks) dng cipher key. Tahap ini disebut juga initial round.

Putaran sebanyak Nr – 1 kali. Proses yg dilakukan pd setiap putaran adalah:
  1. SubBytes: substitusi byte dng memakai tabel substitusi (S-box).
  2. ShiftRows: pergeseran baris-baris array state secara wrapping.
  3. MixColumns: mengacak data di setiap kolom array state.
  4. AddRoundKey: melakukan XOR antara state sekarang round key.

Final round: proses untuk putaran terakhir:

  1. SubBytes
  2. ShiftRows
  3. AddRoundKey

Algoritma kriptografi bernama Rijndael yg didesain oleh  oleh Vincent Rijmen dan John Daemen asal Belgia keluar sebagai pemenang kontes algoritma kriptografi pengganti DES yg diadakan oleh NIST (National Institutes of  Standards and Technology) milik pemerintah Amerika Serikat pd 26 November 2001. Algoritma Rijndael inilah yg kemudian dikenal dng Advanced Encryption Standard (AES). Setelah mengalami bbrp proses standardisasi oleh NIST, Rijndael kemudian diadopsi menjadi standard algoritma kriptografi secara resmi pd 22 Mei 2002. pd 2006, AES adl salah satu algoritma terpopuler yg dipakai dalam kriptografi kunci simetrik.

Dalam kriptografi, Advanced Encryption Standard (AES) merupakan standar enkripsi dng kunci-simetris yg diadopsi oleh pemerintah Amerika Serikat. Standar ini terdiri atas 3 blok cipher, yaitu AES-128, AES-192 and AES-256, yg diadopsi dari koleksi yg lebih besar yg awalnya diterbitkan sebagaiRijndael. Masing-masing cipher memiliki ukuran 128-bit, dng ukuran kunci masing-masing 128, 192, & 256 bit. AES telah dianalisis secara luas & sekarang dipakai di seluruh dunia, seperti halnya dng pendahulunya, Data Encryption Standard (DES).

AES diumumkan oleh Institut Nasional Standar & Teknologi (NIST) sebagaiStandar Pemrosesan Informasi Federal (FIPS) publikasi 197 (FIPS 197) pd tanggal26 November 2001 setelah proses standarisasi selama 5 tahun, di mana ada 15 desain enkripsi yg disajikan & dievaluasi, sebelum Rijndael terpilih sebagai yg paling cocok. AES efektif menjadi standar pemerintah Federal pd tanggal 26 Mei 2002setelah persetujuan dari Menteri Perdagangan. AES tersedia dalam berbagai paket enkripsi yg berbeda. AES adl standar yg pertama yg dapat diakses publik & sandi-terbuka yg disetujui oleh NSA untuk informasi rahasia. Salah satu alasan mengapa AES encryption bekerja dng baik adl metode enkripsi ini bekerja pd bbrp network layer pd saat yg sama.

Walaupun AES & Rijndael dipakai secara bergantian, terdapat bbrp perbedaan yg dapat dng mudah diketahui. Sementara AES memakai blok cipher fix 128-bit, Rijndael dapat memakai blok cipher apa saja & kunci 32-bit. Ukuran kunci & blok cipher yg dipakai memiliki berkisar antara 128-bit sampai 256-bit. AES ini adl algoritma block cipher dng memakai sistem permutasi & substitusi (P-Box & S-Box) bukan dng jaringan Feistel sebagaiman block cipher pd umumnya. Tidak seperti DES yg berorientasi bit, Rijndael beroperasi dalam orientasi byte. Setiap putaran mengunakan kunci internal yg berbeda (disebut round key). Enciphering melibatkan operasi substitusi & permutasi. Jenis AES terbagi 3, yaitu :

  1. AES-128
  2. AES-192
  3. AES-256 

Pengelompokkan jenis AES ini adl berdasarkan panjang kunci yg dipakai. Angka-angka di belakang kata AES menggambarkan panjang kunci yg dipakai pd tipa-tiap AES. Selain itu, hal yg membedakan dari masing-masing AES ini adl banyaknya round yg dipakai. AES-128 memakai 10 round, AES-192 sebanyak 12 round, & AES-256 sebanyak 14 round.

Berikut adl tabel diagramnya:

Algoritma Rijndael AES Advanced Encryption Standard
Algoritma Rijndael AES Advanced Encryption Standard

S memiliki ukuran block yg tetap sepanjang 128 bit & ukuran kunci sepanjang 128, 192, atau 256 bit. Tidak seperti Rijndael yg  block & kuncinya dapat berukuran kelipatan 32 bit dng ukuran minimum 128 bit & maksimum 256 bit. Berdasarkan ukuran block yg tetap, AES bekerja pd matriks berukuran 4x4 di mana tiap-tiap sel matriks terdiri atas 1 byte (8 bit). Sedangkan Rijndael sendiri dapat mempunyai ukuran matriks yg lebih dari itu dng menambahkan kolom sebanyak yg diperlukan.

Garis besar Algoritma Rijndael yg beroperasi pd blok  128-bit dng kunci 128-bit adl sebagai berikut (di luar proses pembangkitan round key):

  • AddRoundKey: melakukan XOR antara state awal (plainteks) dng cipher key. Tahap ini disebut juga initial round.
  • Putaran sebanyak Nr – 1 kali. Proses yg dilakukan pd setiap putaran adalah:
  • SubBytes: substitusi byte dng memakai tabel substitusi (S-box).
  • ShiftRows: pergeseran baris-baris array state secara wrapping.
  • MixColumns: mengacak data di masing-masing kolom array state.
  • AddRoundKey: melakukan XOR antara state sekarang round key.
  • Final round: proses untuk putaran terakhir:
  • SubBytes
  • ShiftRows
  • AddRoundKey

GAMBAR DIAGRAM AES

Algoritma Rijndael AES Advanced Encryption Standard
Algoritma Rijndael AES Advanced Encryption Standard

Selama kalkulasi plainteks menjadi cipherteks, status sekarang dari data disimpan di dalam array of bytes dua dimensi, state, yg berukuran NROWS ´ NCOLS.

  • Untuk blok data 128-bit, ukuran state adl 4 ´ 4.
  •  Elemen array state diacu sebagai S[r,c], 0 £ r < 4 & 0 £ c < Nb (Nb adl panjang blok dibagi 32.
  • Pada AES-128, Nb = 128/32 = 4)

Contoh gambarannya
Algoritma Rijndael AES Advanced Encryption Standard
Algoritma Rijndael AES Advanced Encryption Standard



Contoh: (elemen state & kunci dalam notasi HEX)
Algoritma Rijndael AES Advanced Encryption Standard
Algoritma Rijndael AES Advanced Encryption Standard


Contoh Program Rijndael AES Sederhana dng Java



import java.security.Security;
import javax.crypto.Cipher;
import javax.crypto.spec.SecretKeySpec;

public class Main {
  public static void main(String[] args) throws Exception {
    Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider());
    byte[] input = "tes".getBytes();
    byte[] keyBytes = new byte[] { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09,
        0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f };

    SecretKeySpec key = new SecretKeySpec(keyBytes, "AES");

    Cipher cipher = Cipher.getInstance("AES/ECB/PKCS7Padding", "BC");

    System.out.println(new String(input));

    // encryption pass
    cipher.init(Cipher.ENCRYPT_MODE, key);

    byte[] cipherText = new byte[cipher.getOutputSize(input.length)];
    int ctLength = cipher.update(input, 0, input.length, cipherText, 0);
    ctLength += cipher.doFinal(cipherText, ctLength);
    System.out.println(new String(cipherText));
    System.out.println(ctLength);

    // decryption pass
    cipher.init(Cipher.DECRYPT_MODE, key);
    byte[] plainText = new byte[cipher.getOutputSize(ctLength)];
    int ptLength = cipher.update(cipherText, 0, ctLength, plainText, 0);
    ptLength += cipher.doFinal(plainText, ptLength);
    System.out.println(new String(plainText));
    System.out.println(ptLength);
  }
}



Kohonen SOM (Self-organizing map) di matlab

Contoh Program Kohonen SOM (Self-organizing map) di matlab

Kohonen SOM (Self-organizing map) di matlab

Self-Organizing Map (SOM)

Self-Organizing Map merupakan salah satu model jaringan saraf yang paling populer. Ini termasuk dalam kategori jaringan pembelajaran kompetitif. Self-Organizing Map didasarkan pada pembelajaran tanpa pengawasan, yang berarti bahwa tidak ada campur tangan manusia yang diperlukan selama pembelajaran dan kebutuhan sedikit yang diketahui tentang karakteristik input data. Kita bisa, misalnya, menggunakan SOM untuk data pengelompokan tanpa mengetahui keanggotaan kelas input data. SOM dapat digunakan untuk mendeteksi fitur yang melekat masalah dan dengan demikian juga telah disebut SOFM, Self-Organizing Feature Peta. Self-Organizing Map dikembangkan oleh profesor Kohonen. SOM telah terbukti berguna dalam banyak aplikasi.

Properti topologi melestarikan berarti bahwa pemetaan mempertahankan jarak relatif antara poin. Tempat yang dekat satu sama lain di ruang input dipetakan ke unit peta dekatnya di SOM. Demikian SOM dapat berfungsi sebagai alat klaster menganalisis data dimensi tinggi. Juga, SOM memiliki kemampuan untuk menggeneralisasi. Kemampuan generalisasi berarti bahwa jaringan dapat mengenali atau ciri input tidak pernah ditemukan sebelumnya. Sebuah masukan baru berasimilasi dengan unit peta itu dipetakan ke.

Self-Organizing Map adalah array dua dimensi neuron:

displaymath1935

Hal ini diilustrasikan dalam Gambar 2.3. Salah satu neuron adalah vektor disebut vektor codebook

displaymath1937


Ini memiliki dimensi yang sama dengan vektor input (n berdimensi). Neuron yang terhubung ke neuron yang berdekatan dengan hubungan lingkungan. Ini menentukan topologi, atau struktur, dari peta. Biasanya, neuron saling terhubung satu sama lain melalui topologi empat persegi panjang atau heksagonal. Dalam Gambar 2.3 hubungan topologi ditunjukkan oleh garis antara neuron.

Kohonen SOM (Self-organizing map) di matlab
Kohonen SOM (Self-organizing map) di matlab

Dalam algoritma SOM dasar, hubungan topologi dan jumlah neuron yang tetap dari awal. Jumlah ini neuron menentukan skala atau granularity dari model yang dihasilkan. Temukan skala mempengaruhi akurasi dan kemampuan generalisasi model. Ini harus diperhitungkan bahwa generalisasi dan akurasi adalah tujuan bertentangan. Dengan meningkatkan pertama, kita kehilangan pada kedua, dan sebaliknya.

Kohonen SOM (Self-organizing map) di matlab
Kohonen SOM (Self-organizing map) di matlab

Contoh Program Self-organizing map

Berikut ini adalah kode menerapkan SOM pada tulisan tangan recongnition digit. Aku hanya digunakan sepuluh gambar angka tulisan tangan. Setiap gambar diubah ukurannya 30 × 30 dan membentuk kembali ke kolom vektor 900 × 1. Data dalam kode di bawah ini training set. Ini adalah coolection vektor kolom 900-dimensi.

Kohonen Matlab Code



%//Matlab script
%//-- 10 x 10 map

data = double(data);
%// toal number of nodes
totalW = 100;
%//initialization of weights
w = rand(900, totalW);
%// the initial learning rate
eta0 = 0.1;
%// the current learning rate (updated every epoch)
etaN = eta0;
%// the constant for calculating learning rate
tau2 = 1000;

%//map index
[I,J] = ind2sub([10, 10], 1:100);

N = size(data,2);

alpha = 0.5;
%// the size of neighbor
sig0 = 200;

sigN = sig0;
%// tau 1 for updateing sigma
tau1 = 1000/log(sigN);

%i is number of epoch
for i=1:2000
    %// j is index of each image.
    %// it should iterate through data in a random order rewrite!!
    for j=1:N
        x = data(:,j);
        dist = sum( sqrt((w - repmat(x,1,totalW)).^2),1);

        %// find the winner
        [v ind] = min(dist);
        %// the 2-D index
        ri = [I(ind), J(ind)];

        %// distance between this node and the winner node.
        dist = 1/(sqrt(2*pi)*sigN).*exp( sum(( ([I( : ), J( : )] - repmat(ri, totalW,1)) .^2) ,2)/(-2*sigN)) * etaN;

        %// updating weights
        for rr = 1:100
            w(:,rr) = w(:,rr) + dist(rr).*( x - w(:,rr));
        end
    end

    %// update learning rate
    etaN = eta0 * exp(-i/tau2);
    %// update sigma
    %sigN = sigN/2;
    sigN = sig0*exp(-i/tau1);

    %//show the weights every 100 epoch
    if mod(i,200) == 1
        figure;
        axis off;
        hold on;
        for l = 1:100
            [lr lc] = ind2sub([10, 10], l);
            subplot(10,10,l);
            axis off;
            imagesc(reshape(w(:,l),30,30));
            axis off;
        end
        hold off;
    end
end

hasil:

Lihat transisi antara nomor yang berbeda?

SOM


Metode Otsu Implementasi Java

Contoh Program Metode Otsu Implementasi Java

Metode Otsu Implementasi Java

Dalam thresholding global, kita memilih nilai ambang tunggal untuk seluruh dokumen. Jadi strategi yang baik untuk digunakan saat sebagian dari dokumen memiliki sifat yang mirip (seperti dalam salah satu bagian isnt lebih gelap dari yang lain, misalnya).

Salah satu metode yang paling menonjol untuk menentukan ambang batas global seleksi ambang batas otsu. Metode Otsu yang mendalam mencari ambang yang meminimalkan varians kelas intra. Tujuan dari thresholding adalah untuk membagi piksel dari gambar yang diberikan menjadi dua kelas Hitam dan Putih (binarization). Jika kita mempertimbangkan citra skala abu-abu sebagai lapisan sisik abu-abu, maka kita perlu menentukan tingkat Gl abu-abu di atas yang pixel akan hitam, dan sisanya akan menjadi putih.

Persamaan Otsu Thresholding

Dalam metode Otsu itu kami mendalam mencari ambang yang meminimalkan varians kelas intra (varians dalam kelas), yang didefinisikan sebagai jumlah tertimbang varians dari dua kelas:

\sigma^2_w(t)=\omega_1(t)\sigma^2_1(t)+\omega_2(t)\sigma^2_2(t)

Bobot \omega_i adalah probabilitas dari dua kelas dipisahkan oleh t ambang batas dan \sigma^2_ i saya adalah variasi dari kelas-kelas ini.

Otsu menunjukkan bahwa meminimalkan varians kelas intra sama memaksimalkan antar kelas varians

\sigma^2_b(t)=\sigma^2-\sigma^2_w(t)=\omega_1(t)\omega_2(t)\left[\mu_1(t)-\mu_2(t)\right]^2

yang dinyatakan dalam hal probabilitas kelas \omega_i dan sarana kelas \mu_i

Probabilitas kelas \omega_1(t) dihitung dari histogram sebagai t:

\omega_1(t)=\Sigma_0^t p(i)

sedangkan kelas mean \mu_1(t) adalah:

\mu_1(t)=\left[\Sigma_0^t p(i)\,x(i)\right]/\omega_1

di mana x(i) adalah nilai di tengah-i histogram bin. Demikian pula, Anda dapat menghitung \omega_2(t) dan \mu_2 di sisi kanan histogram untuk sampah besar dari t.

Probabilitas kelas dan sarana kelas dapat dihitung iteratif. Ide ini menghasilkan suatu algoritma yang efektif.

Metode Otsu menghasilkan ambang batas pada 0: 1 skala. Batas ini berlaku untuk rentang dinamis intensitas pixel hadir dalam gambar. Misalnya, yang gambar hanya mengandung intensitas pixel di kisaran 155-255, ambang Otsu 0,75 akan memetakan untuk nilai ambang batas grayscale dari 230 (tidak 191 seperti itu jika gambar yang terdapat piksel dalam berbagai 0 -255). Gambar foto umum akan cenderung mengandung berbagai intensitas pixel, membuatnya menjadi titik bisu, tetapi aplikasi lain sensitif terhadap perbedaan

Algoritma

  1. Hitung histogram dan probabilitas setiap tingkat intensitas
  2. Mengatur awal \omega_i(0) dan \mu_i(0)
  3. Langkah melalui semua kemungkinan ambang t = intensitas t = 1 \ldots  - Memperbarui  \omega_i dan \mu_i  - Hitung \sigma^2_b(t)
  4. Ambang batas yang diinginkan sesuai dengan maksimal \sigma^2_b(t)
  5. Anda dapat menghitung dua maxima (dan dua ambang batas yang sesuai). \sigma^2_{b1}(t) adalah max lebih besar dan \sigma^2_{b2}(t) adalah lebih besar atau sama maksimum
  6. Diinginkan threshold = \frac{\text{threshold}_1 + \text{threshold}_2 }{2}

Contoh Program Metode Otsu Implementasi Java

Berikut ini adalah penerapan contoh program implementasi Metode Otsu dengan menggunakan bahasa pemrograman Java.



package otsu;
 

public class otsuThresholdingService {
 
    public double getOtsuThreshold(int[] grayScaleValues) {
 
        int[] n = getHistogram(grayScaleValues);
        double[] p = getProbabilities(n, grayScaleValues.length);
        double [] Wo = getWo(p);
        double W = getW(p);
        double [] W1 = getW1(Wo, W);
        double UT = getUT(p);
        double [] Ut = getUt(p);
        double [] Uo = getUo(Ut, Wo);
        double [] U1 = getU1(UT, Ut, Uo);
        double sigmaSqrT = getSigmaSqrT(UT,p);
        double [] sigmaSqrBt = getSigmaSqrBt(Wo, W1, U1, Uo);
        double [] eta = getEta(sigmaSqrBt,sigmaSqrT);
 
        return getMaxIndex(eta);
 
    }
 
    private int[] getHistogram(int[] grayScaleValues) {
        int[] histogram = new int[256];
 
        for (int index = 0; index < grayScaleValues.length; index++) {
            histogram[grayScaleValues[index]]++;
        }
        return histogram;
    }
 
    private double[] getProbabilities(int[] histogram, int totalPixels) {
 
        double[] probability = new double[histogram.length];
 
        for (int index = 0; index < probability.length; index++) {
            probability[index] = ((double) histogram[index]) / ((double) totalPixels);
        }
 
        return probability;
    }
 
    private double[] getWo(double[] probability) {
 
        double[] Wo = new double[probability.length];
        Wo[0] = probability[0];
 
        for (int index = 1; index < Wo.length; index++) {
            Wo[index] = Wo[index - 1] + probability[index];
        }
 
        return Wo;
    }
 
    private double getW(double[] probability) {
 
        double W = 0;
 
        for (int index = 0; index < probability.length; index++) {
            W += probability[index];
        }
 
        return W;
    }
 
    private double[] getW1(double[] Wo, double W) {
 
        double[] W1 = new double[Wo.length];
 
        for (int index = 0; index < W1.length; index++) {
            W1[index] = W - Wo[index];
        }
 
        return W1;
    }
 
    private double getUT(double[] probability) {
 
        double UT = 0;
 
        for (int index = 0; index < probability.length; index++) {
            UT += (((double) index) * probability[index]);
        }
 
        return UT;
 
    }
 
    private double[] getUt(double[] probability) {
 
        double[] Ut = new double[probability.length];
 
        Ut[0] = 0;
        for (int index = 1; index < probability.length; index++) {
            Ut[index] = Ut[index - 1] + (((double) index) * probability[index]);
        }
 
        return Ut;
    }
 
    private double[] getUo(double[] Ut, double[] Wo) {
 
        double[] Uo = new double[Ut.length];
 
        for (int index = 0; index < Ut.length; index++) {
            Uo[index] = Ut[index] / Wo[index];
        }
 
        return Uo;
 
    }
 
    private double[] getU1(double UT, double[] Ut, double[] Uo) {
 
        double[] U1 = new double[Ut.length];
 
        for (int index = 0; index < U1.length; index++) {
            U1[index] = (UT - Ut[index]) / (1 - Uo[index]);
        }
 
        return U1;
 
    }
 
    private double getSigmaSqrT(double UT, double[] probability) {
 
        double sigmaSqrT = 0;
 
        for (int index = 0; index < probability.length; index++) {
            sigmaSqrT += (Math.pow((index - UT), 2) * probability[index]);
        }
 
        return sigmaSqrT;
 
    }
 
    private double[] getSigmaSqrBt(double[] Wo, double[] W1, double[] U1, double[] Uo) {
        double sigmaSqrBt[] = new double[Wo.length];
 
        for (int index = 0; index < sigmaSqrBt.length; index++) {
            sigmaSqrBt[index] = Wo[index] * W1[index] * Math.pow((U1[index] - Uo[index]), 2);
        }
 
        return sigmaSqrBt;
    }
 
    private int getMaxIndex(double [] array){
 
        int maxIndex = 0;
        for(int i=0;i<array.length;i++){
            if(array[maxIndex]<array[i]){
            maxIndex=i;
            }
        }
        return maxIndex;
 
    }
 
    private double[] getEta(double[] sigmaSqrBt, double sigmaSqrT) {
       double eta[] = new double[sigmaSqrBt.length];
        for(int index= 0; index<sigmaSqrBt.length;index++){
            eta[index] = sigmaSqrBt[index]/sigmaSqrT;
       }
        return eta;
    }
}


Metode Otsu Thresholding OpenCV C++

Contoh Program Metode Otsu Thresholding OpenCV C++

Metode Otsu Thresholding OpenCV C++

Metode Otsu 

Tujuan dari metode otsu adalah membagi histogram citra gray level kedalam dua daerah yang
berbeda secara otomatis tanpa membutuhkan bantuan user untuk memasukkan nilai ambang
Pendekatan yang dilakukan oleh metode otsu adalah dengan melakukan analisis diskriminan yaitu menentukan suatu variabel yang dapat membedakan antara dua atau lebih kelompok yang muncul secara alami. Analisis Diskriminan akan memaksimumkan variable tersebut agar dapat membagi objek latardepan (foreground) dan latarbelakang (background).

Dalam metode Otsu itu kami mendalam mencari ambang yang meminimalkan varians kelas intra (varians dalam kelas), yang didefinisikan sebagai jumlah tertimbang varians dari dua kelas:

\sigma^2_w(t)=\omega_1(t)\sigma^2_1(t)+\omega_2(t)\sigma^2_2(t)

Bobot \omega_i adalah probabilitas dari dua kelas dipisahkan oleh t ambang batas dan \sigma^2_ i saya adalah variasi dari kelas-kelas ini.

Otsu menunjukkan bahwa meminimalkan varians kelas intra sama memaksimalkan antar kelas varians

\sigma^2_b(t)=\sigma^2-\sigma^2_w(t)=\omega_1(t)\omega_2(t)\left[\mu_1(t)-\mu_2(t)\right]^2

yang dinyatakan dalam hal probabilitas kelas \omega_i dan sarana kelas \mu_i

Probabilitas kelas \omega_1(t) dihitung dari histogram sebagai t:

\omega_1(t)=\Sigma_0^t p(i)

sedangkan kelas mean \mu_1(t) adalah:

\mu_1(t)=\left[\Sigma_0^t p(i)\,x(i)\right]/\omega_1

di mana x(i) adalah nilai di tengah-i histogram bin. Demikian pula, Anda dapat menghitung \omega_2(t) dan \mu_2 di sisi kanan histogram untuk sampah besar dari t.

Probabilitas kelas dan sarana kelas dapat dihitung iteratif. Ide ini menghasilkan suatu algoritma yang efektif.

Metode Otsu menghasilkan ambang batas pada 0: 1 skala. Batas ini berlaku untuk rentang dinamis intensitas pixel hadir dalam gambar. Misalnya, yang gambar hanya mengandung intensitas pixel di kisaran 155-255, ambang Otsu 0,75 akan memetakan untuk nilai ambang batas grayscale dari 230 (tidak 191 seperti itu jika gambar yang terdapat piksel dalam berbagai 0 -255). Gambar foto umum akan cenderung mengandung berbagai intensitas pixel, membuatnya menjadi titik bisu, tetapi aplikasi lain sensitif terhadap perbedaan

Algoritma

  1. Hitung histogram dan probabilitas setiap tingkat intensitas
  2. Mengatur awal \omega_i(0) dan \mu_i(0)
  3. Langkah melalui semua kemungkinan ambang t = intensitas t = 1 \ldots  - Memperbarui  \omega_i dan \mu_i  - Hitung \sigma^2_b(t)
  4. Ambang batas yang diinginkan sesuai dengan maksimal \sigma^2_b(t)
  5. Anda dapat menghitung dua maxima (dan dua ambang batas yang sesuai). \sigma^2_{b1}(t) adalah max lebih besar dan \sigma^2_{b2}(t) adalah lebih besar atau sama maksimum
  6. Diinginkan threshold = \frac{\text{threshold}_1 + \text{threshold}_2 }{2}


Metode Otsu Thresholding OpenCV C++

Saya menulis utilitas ini untuk menunjukkan algoritma Otsu thresholding otomatis. Saya menggunakan frankfurt.jpg gambar (sumber: Wikipedia). Nama ini keras-kode.

Ini adalah gambar asli:


Gambar berikut menunjukkan hasil dari algoritma Otsu. Besar tetapi perlu beberapa perbaikan. Jadi kita akan menerapkan operasi morfologi penutupan.



Hasil algoritma Otsu dengan penutupan (pelebaran maka erosi) dapat dilihat di bawah ini:


Operasi penutupan di atas digunakan elemen penataan berikut:

  [0, 0, 1, 0, 0;
   1, 1, 1, 1, 1;
   1, 1, 1, 1, 1;
   1, 1, 1, 1, 1;
   0, 0, 1, 0, 0]

Jika Anda mengambil gambar biner akhir dan menerapkannya ke gambar asli, Anda akan melihat bahwa sebagian besar latar belakang dihapus. Beberapa luas bangunan di sebelah kiri juga telah dihapus tapi yang diharapkan karena kesamaan antara intensitas dan intensitas latar belakang (langit tampilan).



Implementasi Program Dengan OpenCV

Berikut ini adalah penerapan contoh program Metode Otsu Thresholding dengan OpenCV C++



#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <opencv2/opencv.hpp>
#include <limits>
 
using namespace cv;
using namespace std;
 
/**
 * Fungsi ini memanfaatkan Mat << operator.
 */
void dump(const Mat &mat, const char* fname)
{
    ofstream filestream;
    filestream.open (fname);
    filestream << mat << endl << endl;
    filestream.close();
}
 
/**
 * Digunakan untuk menghindari noise di gambar.
 */
void applyGaussian(cv::Mat &input, cv::Mat &output) {
    double sigma = 1.5;
    cv::Mat gaussKernel = cv::getGaussianKernel(9,sigma,CV_32F);
    cv::GaussianBlur( input, output, cv::Size(3,3), 1.5);
}
 
/**
 * Ini mirip dengan pelaksanaan Robert Laganière.
 * Lihat bukunya: OpenCV 2 Computer Vision Application Programming Cookbook.
 */
cv::Mat showHistogram(const cv::Mat &inImage){
 
    cv::MatND hist;
    // Untuk skala abu-abu [0: 255] kita memiliki 256 tempat sampah
    const int bins[1] = {256};
    const float hranges[2] = {0.0, 255.0};
    const float* ranges[1] = { hranges };
    const int channels[1] = {1};
 
    cv::calcHist(const_cast<mat>(&inImage),
            1,             //histogram dari 1 gambar saja
            channels,
            cv::Mat(),     // tidak ada masker yang digunakan
            hist,          // histogram keluaran
            1,             // 1D histogram
            bins,
            ranges         // rentang nilai pixel
    );
 
    // Dapatkan min dan max nilai bin
    double maxVal=0;
    double minVal=0;
    cv::minMaxLoc(hist, &minVal, &maxVal, 0, 0);
 
    // Gambar untuk menampilkan histogram
    cv::Mat histImg(bins[0], bins[0], CV_8U, cv::Scalar(255));
 
    // Memetakan titik tertinggi 95% dari histogram tinggi untuk 
 // meninggalkan beberapa ruang kosong di bagian atas
    const int histHeight = bins[0];
    const int maxHeight = 0.95 * histHeight;
 
    cv::Mat_<float>::iterator it    = hist.begin<float>();
    cv::Mat_<float>::iterator itend = hist.end<float>();
 
    int barPosition = 0;
    for ( ; it != itend; ++it) {
        float histValue = (*it);
        int barHeight = ( histValue * maxHeight ) / maxVal;
        cv::line(histImg,
                // mulai baris dari bawah, dan naik berdasarkan barHeight
                // Ingat (0,0) adalah sudut kiri atas
                cv::Point(barPosition, histHeight),
                cv::Point(barPosition, histHeight - barHeight),
                cv::Scalar::all(0));
        barPosition++;
    }
 
    return histImg;
}
 
void applyClosing( cv::Mat &binaryImage, int element_radius = 2 ) {
    int element_type   = cv::MORPH_ELLIPSE;
 
    // Unsur penataan digunakan untuk pelebaran dan erosi.
    Mat element = cv::getStructuringElement( element_type,
            Size( 2*element_radius + 1, 2*element_radius+1 ),
            Point( element_radius, element_radius ) );
 
    dump( element, "element.data" );
 
    cv::dilate(binaryImage, binaryImage,
            element,
            Point(-1, -1),
            2
    );
 
    cv::erode(binaryImage, binaryImage,
            element,
            // Posisi jangkar dalam elemen struktur.
            // Nilai default -1, -1 berarti bahwa jangkar di tengah elemen
            Point(-1, -1),
            // Iterasi: berapa kali operasi ini diterapkan
            2
    );
}
 
int main(int argc, char *argv[])
{
    cout << "Compiled with OpenCV version " << CV_VERSION << endl;
    Mat inImage = cv::imread("frankfurt.jpg");
 
    imshow("Original", inImage);
 
    Mat histgram = showHistogram(inImage);
    imshow("Histogram", histgram);
 
    Mat grayImage;
    cvtColor(inImage, grayImage, CV_RGB2GRAY);
 
    applyGaussian( grayImage, grayImage );
 
    // algoritma  Otsu thresholding bekerja dengan baik 
 // ketika histogram memiliki distribusi bimodal.
    // Ini akan menemukan nilai ambang batas yang memaksimalkan 
    // varians kelas tambahan sementara
    // Menjaga kelas intra varians rendah.
    cv::Mat binaryImage;
    cv::threshold(grayImage, binaryImage
            , 0    // nilai tidak penting untuk Otsu thresholding
            , 255  // kita bisa memilih nilai bukan nol. 255 (putih) memudahkan untuk melihat gambar biner
            , cv::THRESH_OTSU | cv::THRESH_BINARY_INV);
 
    applyClosing( binaryImage, 2 );
    imshow("Binary", binaryImage);
 
    cv::Mat outImage = cv::Mat::zeros( inImage.rows, inImage.cols, inImage.type() );
    inImage.copyTo( outImage, binaryImage );
    imshow("Result", outImage);
 
    waitKey(0);
 
    return EXIT_SUCCESS;
}




Konsultasi gratis