Harris Feature Detector

Merhabalar, bu yazımda Harris feature detector algoritmasını birlikte anlatacağım.

Harris Corner Detektörü, her piksel için her yönde süregelen yerel yoğunluk değişikliklerini ölçeklendirmeye çalışır. Daha genel ifadeyle belirli bi alan içerisindeki piksellerin baskın ortogonal gradyan yönlerinin seçilmesi işlemidir.

Genel hatlarıyla anlatmaya çalışacağım, ayrıca wiki üzerinden bakabilirsiniz genel yapısına. Yazının sonuna yardımcı linkler de ekledim.

Kod yazarken adımlarımız şu şekilde olacak:

1) İlk olarak Gauss filtersi uygula

2) x ve y yönlerinde gradyanlarını bul ve Ix Iy değişkenlerine ata

3) Harris algoritmasını uygulaya

  • t değikeninde bir eşik değeri ve W değişkeninde sabit boyutlu pencere tanımla, sonrasında filtrelerle gradyanları (Ix,Iy) hesapla
  • Belirlenen pencere(W) içerisindeki tüm piksellerde G matrisini1 hesapla
  • Eğer en küçük tekil değer ro(G), t’den büyükse o pikseli feature point olarak işaretle

4) Feature’ların yerlerini orijinal resmin üzerine çizdir.

1G matrisimiz burada:

İlk olarak GaussianFilter fonksiyonumuzu yazıp görüntümüzü işleyelim.

def GaussianFilter(img): 
    # 3x3 Gauss kerneli oluşturuyoruz
    kernel = np.ones((3,3), dtype='float64')
    size = 3
    mean = int(size/2)
    sigma = 1 # standart sapmayı 1 olarak aldım
    sumAll = 0
    for i in range(size):
        for j in range(size):
            kernel[i,j] = math.exp(-1* ((math.pow( (i-mean)/sigma, 2.0) + (math.pow((j-mean)/sigma, 2.0)) ) / (2* math.pow(sigma,2)) )) / (sigma * math.pow(2*math.pi, 1/2))
            sumAll += kernel[i,j]
    # normalizing kernel
    for i in range(size):
        for j in range(size):
            kernel[i,j] /= sumAll
    # Oluşturulan kernel ile görüntümüzü konvolüsyona tabi tutuyoruz   
    img = convolution(img, kernel) # filtered image

Son satırdaki konvolüsyon fonksiyonumuz ise:

def convolution(img, dest):
    #res = img
    [h,w] = img.shape
    [kh, kw] = dest.shape # kernel shape
    kr = int(kh/2) # kernel radius
    res = np.zeros(img.shape)
    sumAll2=0
    for i in range(0+kr,h-kr):
        for j in range(0+kr,w-kr):
            for k in range(-1 * kr, kr + 1):
                for m in range(-1 * kr, kr + 1):
                    res[i,j] += dest[k,m]*img[i+k, j+m]
                    sumAll2+=res[i,j]
    res[i,j] /= sumAll2
    res[:,0] = res[:, 1]
    res[:,w-1] = res[:, w-2]
    res[0,:] = res[1,:]
    res[h-1,:] = res[h-2,:]
    res=res.astype(np.uint8)
    return res

İkinci adımımız olan gradyanların hesaplanmasına geliyoruz. Aşağıdaki kod görüntü üzerinde x yönündeki min ve maks gradyanları çizdiriyor. Ardından gradient structure tensor(second-moment matrix) dediğimiz G matrisimizi hesaplıyoruz.  Oluşan matrisin trace’ini calculateTrace() fonksiyonuyla hesaplıyoruz. En sonunda başta algoritmada belirttiğimiz t eşik değeri üzerinde olanları calculateThres() fonksiyonu yardımıyla çizdiriyoruz ve çıktımızı alıyoruz.

calculateThres fonksiyonu ->

def calculateGradients(img):
    [h,w]= img.shape
    grad_x = np.zeros((h,w), dtype = 'float64')
    grad_y = np.zeros((h,w), dtype = 'float64')
    print('Gradyanlar hesaplanıyor')
    # piksel piksel türevleri hesaplıyoruz
    for i in range(h):
        for j in range(w):
            if(j >= w-1): # son kolonda
                grad_y[i,j] = (img[i,j] - img[i,j-1]) / 2
            elif (j== 0): # ilk kolonda
                grad_y[i,j] = (img[i,j+1] - img[i,j]) / 2
            else: # ilk ve son kolon arasında gezinirken
                grad_y[i,j] = (img[i,j+1] - img[i,j-1]) / 2
            if(i >= h-1): # son satırda
                grad_x[i,j] = (img[i,j] - img[i-1,j]) / 2
            elif (i== 0): # ilk satırda
                grad_x[i,j] = (img[i+1,j] - img[i,j]) / 2
            else: # ilk ve son satır arasında
                grad_x[i,j] = (img[i+1,j] - img[i-1,j]) / 2
    #gradyanlarımızı kaydetmek için dosya açıyoruz 
    try:
        fP = open(('xgrad.txt'), 'w')
        maxGradX = 0
        minGradX = 0
        maxTuple = [0,0]
        minTuple = [0,0]
        for i in range(h):
            for j in range(w):
                fP.write(str(i) + ' '  +  str(j) + ' ' +  str(grad_x[i,j]) + '\n')

                if(grad_x[i,j] > maxGradX):
                    maxGradX = grad_x[i,j]
                    maxTuple = [i,j]
                if(grad_x[i,j] < minGradX):
                    minGradX = grad_x[i,j]
                    minTuple = [i,j]
        fP.close()

        # Burada yaptığımız şey x yönündeki
        # gradyanın minimum ve maksimum değerlerini 
        # çizdirip kaydetmek
        pointed=img.copy()
        pointed[maxTuple[0],:] = 255
        pointed[:,maxTuple[1]] = 255
        
        pointed[minTuple[0],:] = 2
        pointed[:,minTuple[1]] = 2

        cv2.imwrite('pointed.jpg', pointed)
    except:
        print('cannot open file')
    structTensor = createStructureTensor(img, grad_x, grad_y)
    R = calculateTrace(img, structTensor)
    calculateThres(img,R)

def calculateTrace(img,M):
    h,w = img.shape
    R = np.zeros((h,w), dtype = 'float64')
    k = 0.04
    for x in range(h):
        for y in range(w):
            deter = M[x,y,0,0]*M[x,y,1,1] - (M[x,y,1,0] * M[x,y,1,0])
            trace = M[x,y,0,0]+M[x,y,1,1]
            R[x,y] = (deter - (trace**2)*k)
    return R

def calculateThres(img,R):
    h,w = img.shape
    corners = np.zeros((h,w,3),dtype=np.uint8)
    corners[:,:,0]=img
    corners[:,:,1]=img
    corners[:,:,2]=img
    
    t = 400000
    for x in range(h):
        for y in range(w):
            if R[x,y] > t:
                corners[x,y] = [0,254,0]
                print(str(x) + ' ' + str(y) + ' ' + str (R[x,y]))
    # Köşeleri bulunmuş görüntümüzü çıktı olarak alıyoruz
    cv2.imwrite('result.jpg', corners)
 
def createStructureTensor(img,Ix,Iy):
        h,w = img.shape
        structTensor = np.zeros((h,w,2,2),dtype='float64')
        Ixx = Ix*Ix
        Ixy = Ix*Iy
        Iyx = Iy*Ix
        Iyy = Iy*Iy

        for x in range(h):
            for y in range(w):
                for i in range(-1,2):
                    for j in range(-1,2):
                        if not(x+j<0 or x+j >= h or y+i <0 or y+i >= w):
                            structTensor[x,y,0,0]+=Ixx[x+j][y+i]
                            structTensor[x,y,0,1]+=Ixy[x+j][y+i]
                            structTensor[x,y,1,0]+=Iyx[x+j][y+i]
                            structTensor[x,y,1,1]+=Iyy[x+j][y+i]
        return structTensor

import math
import numpy as np
import cv2
path="lena.jpg"
inputImage = cv2.imread(path,cv2.IMREAD_GRAYSCALE)
filtered = GaussianFilter(inputImage) # Birinci adım
calculateGradients(filtered) #İkinci ve üçüncü adım

Yardımcı linkler:

https://en.wikipedia.org/wiki/Structure_tensor

https://matlabcorner.wordpress.com/2012/11/17/does-harris-corner-detector-finds-corners-intuitive-explanation-to-harris-corner-detector/

https://www.youtube.com/watch?v=P35WsRDnTsU&t=41m12s

https://docs.opencv.org/3.4/d4/d70/tutorial_anisotropic_image_segmentation_by_a_gst.html

https://docs.opencv.org/3.4.2/dc/d0d/tutorial_py_features_harris.html

http://www.vlfeat.org/overview/sift.html

http://demo.ipol.im/demo/82/

Leave a Reply

Your email address will not be published. Required fields are marked *