Hough dönüşümü

Paul Hough tarafından patenti alınmış ve sonrasında Richard Duda ve Peter Hart tarafından geliştirilmiş olan Hough Dönüşümü, görüntülerdeki doğru ve daireleri tespit etmeyi kolaylaştıran,  bilgisayarda görme ve görüntü işleme alanlarında kullanılan algoritmalar bütünüdür. Bu algoritmalar basit bir oylama mantığıyla çalışmaktadır. Dana H. Ballard, daha farklı nesne çıkarımlarında kullanabilmek için 1981 yılında, Hough Dönüşümü için daha genel bir algoritma ortaya koymuştur.

Hough Dönüşümü ile daire tespiti 
Daire denklemi aşağıdaki denklemde belirtilmektedir.

Burada merkezi  M(a,b) olan r yarıçaplı daire denklemi belirtilmektedir.

Hough Transform algoritmasında ise dairenin polar coordinat sistemindeki denklemi kullanılmaktadır

.

Dairenin kutupsal koordinatları:

Merkezi M(a,b) olan ve r yarıçaplı dairenin polar coordinat denklemi yukarıda belirtilmektedir.

Hough Transform Accumulator 
Daireyi tespit ederken İki boyutlu uzaydan Hough Space ( Hough Uzayı) 'na geçiş yapmamız gerekiyor.

Haugh Uzayını 3 boyutlu Accumulator [a,b,r] olarak belirtelim.

Hough uzayını 3 boyutlu bir dizi ile belirtebiliriz.

A[a,b,r] dizisi için

a : merkez x koordinatı, b : merkez y koordinatı , r : radius(yarıçap)

Hough Tramsform Daire Tespit Algoritması 
 Hough Transform uzayı için oluşturduğumuz Accumulator A[a,b,r] dizisinin tüm elemanlarına başlangıçta 0 atanmalı.   Her A[a,b,r ] = 0
 Alınan sahne üzerinde  ( image , frame ) öncelikle filtreleme operatörleri çalıştırılmalıdır.
 Sırasıyla Gaussian Bluring , cvtGrayScale ( griye çevirme ) , Canny Edge Detector operatörleri alınan frame üzerinde uygulanmalıdır.
 Her pixel için yukarıda belirtilen polar koordinat denklemleri kullanılarak oluşabilecek daireleri merkez ve yarıçapları hesaplanmalıdır.
 Her pixel aşağıda belirtilen oylama algoritması ile oluşturabileceği daireler oylanmalıdır.
 Oylanan pixeller  için Accumulator A da en fazla oy alan pixeller belirlenen sınırdan fazla oy alanlar ile Hough Transform uzayı belirtilebilir.
 En fazla oy alan accumulatorde  tespit edilmek istenilen  dairenin merkez noktasını koordinatları ve yarıçapı bulunmaktadır.
 En fazla oy alan daire çizdirilir. 
Aşağıda oylama algoritması belirtilmektedir.

Oylama Algoritması 

 For pixel(x,y)
   For radius r = 10 to r = 60 //olası yarıçaplar
     For theta θ = 0 to 360 // θ radiana çevrilmeli 
          a=x-r\times cos(θ)  //merkez koordinatları
          b=y-r\times sin(θ)  //merkez koordinatları 
          A[a,b,r] +=1; //oylama işlemi
      end
    end
 end

Notlar 

Bilgisayar
Algoritmalar