Hough dönüşümü

Paul Hough tarafından patenti alınmış ve sonrasında Richard Duda^[1] 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,^[2] 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.

Daire denklemi aşağıdaki denklemde belirtilmektedir.

${\displaystyle (x-a)^{2}+(y-b)^{2}=r^{2}}$

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ı:

${\displaystyle a=x-r\times cos(\theta )}$

${\displaystyle b=y-r\times sin(\theta )}$

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

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

Haugh Uzayını 3 boyutlu Accumulator^[3] [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)

1. 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
2. Alınan sahne üzerinde (image, frame ) öncelikle filtreleme operatörleri çalıştırılmalıdır.
3. Sırasıyla Gaussian Bluring, cvtGrayScale (griye çevirme ), Canny Edge Detector operatörleri alınan frame üzerinde uygulanmalıdır.
4. Her pixel için yukarıda belirtilen polar koordinat denklemleri kullanılarak oluşabilecek daireleri merkez ve yarıçapları hesaplanmalıdır.
5. Her pixel aşağıda belirtilen oylama algoritması ile oluşturabileceği daireler oylanmalıdır.
6. Oylanan pixeller için Accumulator A da en fazla oy alan pixeller belirlenen sınırdan fazla oy alanlar ile Hough Transform uzayı belirtilebilir.
7. En fazla oy alan accumulatorde tespit edilmek istenilen dairenin merkez noktasını koordinatları ve yarıçapı bulunmaktadır.
8. En fazla oy alan daire çizdirilir.

Aşağıda oylama algoritması belirtilmektedir.

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