Harris Corner Detection

Kategori: Computer Vision , 13 Şubat 2020 , JanFranco


Harris Corner Detection algoritması basit bir teoriye dayanıyor. Resmin bir bölümünden kesit alalım. Bu kesiti x ve y eksenlerinde kaydıralım. Eğer x ve y eksenlerindeki değişim çok az ise burası flat bir bölgedir, düz bir bölgedir. Eğer x ekseninde kaydırdığımızda yüksek bir değişim var ise fakat y ekseninde kaydırdığımızda düşük bir değişim var ise bu bölge bir kenardır. Aynı şey tam tersi için de geçerli. y eksenindeki değişim fazla x eksenindeği değişim az ise kenardır. Eğer iki eksende de yüksek bir değişim var ise bu bölge köşedir:

Harris Corner Det

Harris Corner Detection algoritması aşağıdaki adımlardan oluşur:

1- Gradyan hesaplama
2- Gaussian filtreleme
3- Harris değeri hesabı
4- Non-maximmum supression
5- Thresholding

Algoritmanın ilk adımında x ve y eksenindeki değişimler hesaplanır. Bunu Gradients yazımızda anlatmıştık. Bir kernel resim üzerinde dolaşıyor ve convolutional işlem yapılıyordu. İkinci adımda Gaussian filtreleme yapılır. Bunu da Gaussian Blurring, Filter yazımızda anlatmıştık. Üçüncü adımda (x eksenindeki değişimin karesi * y eksenindeki değişimin karesi) - (x eksenindeki değişim * y eksenindeki değişim)^2 hesaplanır. Dördüncü adımda lokal maxima hesaplanır. Beşinci adımda belirlenen değerden yüksek değeler köşe olarak saptanır.

Algoritmanın arkasındaki matematiğe göz atalım. Öncelikle ana formülümüzü görelim:

Harris Corner Detection

E değişimdir. u ve v değerleri yer değiştirmeledir.
w(x, y) resim üzerindeki penceredir.
I(x+u, y+v) resim üzerindeki pencerenin kaydırıldığı alandaki pikselledir.
I(x, y) penceredeki piksellerdir.

Amacımız E değerinin maksimum olmasıdır. Böylelikle köşeleri tespit edebiliriz. Taylor serisini kullanarak formülü güncelleyeceğiz. Taylor serisinde doğrunun sonsuz kez türevi alınarak doğruya çok yakın bir doğru çizilir:

Harris Corner Detection

Burada eşitliğin bozulmasının sebebi Taylor serisinin sonsuz bir dizi olmasındandır. Sonsuz dizinin sadece ilk 3 terimini aldığımız için asıl doğrumuzu kaybettik. Ix ve Iy türev sonuçlarıdır. Sadeleştirelim, I(x,y) değerleri yok olacak. Kareyi dağıtalım:

Harris Corner Detection

Bu karışık formülü bir matrise dönüştürebiliriz:

Harris Corner Detection

Toplam matrise M dersek:

Harris Corner Detection

Algoritmanın üçüncü adımında yaptığımız işlemleri yapacağız:

Harris Corner Detection

Lambda1 burada Ix^2 Lambda2 ise Iy^2'dir. k değeri bir sabittir. Algoritmanın kurucuları bu değeri 0.04 olarak vermişlerdir. Burada eğer R değeri küçük çıkarsa Lambda1 ve Lambda2 küçük demektir. Yani bölge düzdür. Eğer R değeri 0'dan küçük çıkarsa Lambda1, Lambda2'den veya Lambda2, Lambda1'den oldukça büyüktür. Bu durumda bölge kenardır. R değeri yüksekse Lambda1 ve Lambda2 değerleri birbirine yakın ve büyük değerlerdir. Bu bölge köşedir:

Harris Corner Detection

Harris Corner Detection algoritması, Marovec Corner Detection algoritmasının gelişmiş bir halidir. İki algoritma birbirine oldukça benzemektedir. Hatta E formülü bile aynıdır iki algoritmada. Ancak temel fark Marovec 45 derecelik kırılmalar ararken Harris algoritmasında böyle bir sınırlama yoktur. Bunu resmi rotate ederek görebiliriz.

Python üzerinden OpenCV kütüphanesindeki cv2.cornerHarris methodunu kullanarak bu algoritmayı kullanabiliriz. Methodun parametreleri:

img - Input görüntü. Grayscale, float32 tipli bir resim olmalıdır.
blockSize - Harris Corner Detection algoritmasının kayan bir pencere ile çalıştığını belirtmiştim. Bu kayan pencerenin boyutudur. Algoritmada determinant, trace gibi işlemler olduğundan pencere mutlaka kare olmalıdır. Bu nedenle (2, 2) şeklinde bir tuple değil direk 2 değerini yazmalıyız. (2 örnektir)
ksize - Algoritma arka planda x ve y eksenlerinde türev aldığını söylemiştim. Bunu Sobel methodu ile yapıyor. Sobel methodu için ksize parametresidir.
k - Formüldeki sabit değerdir. Yukarıda bahsettiğim gibi 0.04 alabiliriz.

Örnek yapalım. Kütüphaneyi ve resmi alalım:


import cv2

img = cv2.imread('../data/chessboard_mat.jpg')
cv2.imshow("Chess", img)
cv2.waitKey(0)
>>

Harris Corner Detection

Algoritmanın çalışabilmesi için resmi grayscal hale çevirelim. Methodu çağıralım ve bir threshold değeri belirleyelim. Bu threshold değerinin üstündeki değerleri kırmızıya boyayalım:


grayImg = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)
dst = cv2.cornerHarris(src=grayImg, blockSize=3, ksize=5, k=0.04)
img[dst > .06 * dst.max()] = [0, 0, 255]
cv2.imshow("Chess", img)
cv2.waitKey(0)
Harris Corner Detection

OpenCV kütüphanesini kullanmadan algoritmayı kullanalım:

(Resmi okuduk, grayscal hale çevirdik, x-y eksenlerinde türevlerini aldık, gaussian blur uyguladık)
...



size_y = im.shape[0]
size_x = im.shape[1]
window_size = 5
half_size = 2
threshold = 3*10**6

for i in range(half_size, size_y-half_size):
    for j in range(half_size, size_x -half_size):
        sxx = 0; sxy = 0; syy= 0
        for k in range(window_size * window_size): # go over window
            im_valx = int(imxg[i + k/window_size - half_size][j+ k%window_size- half_size])
            im_valy = int(imyg[i + k/window_size - half_size][j+ k%window_size- half_size])
            sxx+= im_valx ** 2
            sxy+= im_valx * im_valy
            syy+= im_valy ** 2
        det = syy * sxx - sxy**2
        trace = syy + sxx
        R = det - 0.05 * trace ** 2
        if R > threshold:
            result[i-1:i+1,j-1:j+1,1] = 255
Bu kod aşağıdaki linkten alınmıştır:

https://gist.github.com/Akaame/b6587077a018c3b4a98cd477feddf705

Koddada görüyoruz ki R değerinin küçük çıkması im_valx, im_valy değişkenlerine bağlı. Bu değişkenlerin küçük çıkması değişimin olmadığını yani bölgenin flat düz olduğunu gösterir. im_valx ve im_valy değişkenleri arasında büyük bir fark varsa bu durumda det değişkeni ki bu değişken R değerini büyük oranda etkiliyor, negatif çıkacaktır. det değişkeninin hesaplarken sonda sxy ^ 2 işlemi mevcut. Bu kısımdaki sonuç her türlü büyük çıkacağından, syy * sxx hesabının mutlaka büyük olması gerekiyor. Bu hesabın büyük olması için de bu iki değişkenin birbirine yakın olması gerekiyor. R değeri büyük çıktığında köşemizi bulduk demektir.


Sonraki Yazı: Good Features to Track
Yorumlar

Henüz bir yorum bulunmuyor.