Computing HOG Features in OpenCV (Python)

10Nov11

Sudah lama tidak menulis di blog *hiyaaa* karena masih beradaptasi dengan aktivitas sebagai dosen (yang tidak cuma mengajar dan meneliti, “maklumlah dosen muda, kalau kata dosen-dosen lain yang sudah lebih senior”). Padahal banyak sekali yang mau ditulis (dan dikerjakan tentunya).

Curhatnya saya hentikan sampai sini saja. Ceritera mengenai pengalaman saya dalam menjalani aktivitas sebagai dosen saya tuliskan di blog kampus. tulisan-tulisan di sini akan tetap saya fokuskan pada hasil utak-atik (terutama kode proof-of-concept) dalam mempelajari topik-topik dalam dunia informatika.

Kali ini saya sedang iseng membuat implementasi dari HOG (Histogram of Oriented Gradients). Fitur ini dikaji secara lebih dalam oleh Navneet Dalal dan Bill Triggs dari INRIA, Perancis untuk mendeteksi pejalan kaki (pedestrian) pada citra di tahun 2005. Sama seperti deskriptor yang digunakan pada SIFT (Scale Invariant Feature Transform *eh, saya belum membahas SIFT ya?*), informasi vektor gradien disimpan dalam koordinat polar (panjang dan arah).

Walaupun HOG *katanya* sudah ada di OpenCV tapi di dokumentasi python sepertinya belum ditambahkan. Python ini sedikit dianaktirikan di OpenCV, saya baru bisa menikmati fasilitas SVM di python di versi 2.3 (dengan python 2.6), karena OpenCV versi 2.2 untuk python hanya berisi modul untuk python versi 2.7. Akhirnya saya terpaksa membuat sendiri. Sebetulnya pembuatan HOG di OpenCV from scratch sudah pernah ditulis oleh Saurabh Goyal di sini. Apa yang saya buat mengadopsi dari yang sudah ditulis di sana (dengan modifikasi sesuka saya tentunya) terutama bagian penghitungan dengan memanfaatkan citra integral. Kode yang ditulis dengan python menurut saya jadi lebih sederhana dan (semoga) lebih mudah dibaca dan dipahami oleh pembaca (setia?) blog ini. Selamat menikmati

Mari kita buka bahasan kita dengan kode dalam python yang akan saya jelaskan setelahnya. Saya menggunakan dua modul yaitu cv(opencv) dan numpy (dengan alias np).

import cv
import numpy as np

def calc_hog(im,numorient=9):
    """
    calculate integral HOG (Histogram of Orientation Gradient) image (w,h,numorient)
    
    calc_hog(im, numorient=9)
    
    returns 
        Integral HOG image

    params 
        im : color image
        numorient : number of orientation bins, default is 9 (-4..4)
    
    """
    sz = cv.GetSize(im)
    gr = cv.CreateImage(sz, 8, 1)
    gx = cv.CreateImage(sz, 32, 1)
    gy = cv.CreateImage(sz, 32, 1)
    
    #convert to grayscale
    cv.CvtColor(im, gr, cv.CV_BGR2GRAY)
    
    #calc gradient using sobel
    cv.Sobel(gr, gx, 1, 0, 3)
    cv.Sobel(gr, gy, 0, 1, 3)
    
    #calc initial result
    hog = np.zeros((sz[1], sz[0], numorient))
    mid = numorient/2
    for y in xrange(0, sz[1]-1):
        for x in xrange(0, sz[0]-1):
            angle = int(round(mid*np.arctan2(gy[y,x], gx[y,x])/np.pi))+mid
            magnitude = np.sqrt(gx[y,x]*gx[y,x]+gy[y,x]*gy[y,x])
            hog[y,x,angle] += magnitude
            
            
    #build integral image
    for x in xrange(1, sz[0]-1):
        for ang in xrange(numorient):
            hog[y,x,ang] += hog[y,x-1,ang]
    for y in xrange(1, sz[1]-1):
        for ang in xrange(numorient):
            hog[y,x,ang] += hog[y-1,x,ang]
    for y in xrange(1, sz[1]-1):
        for x in xrange(1, sz[0]-1):
            for ang in xrange(numorient):
                #tambah kiri dan atas, kurangi dengan kiri-atas
                hog[y,x,ang] += hog[y-1,x,ang] + hog[y,x-1,ang] - hog[y-1,x-1,ang]
    return hog

beberapa langkah yang dilakukan dalam membuat citra hog integral a.l.:

• menghitung citra gradien dengan memanfaatkan operator sobel
• membuat citra histogram untuk menampung diskretisasi sudut/orientasi (sebanyak orientasi yang diperlukan, harus berjumlah ganjil), saya memanfaatkan array dari numpy.
• membuat citra integral terhadap setiap orientasi.

Pada contoh kode di atas, saya membuat array berdimensi 3 berukuran lebar citra x tinggi citra x banyaknya elemen orientasi yang diinginkan. banyaknya orientasi selalu ganjil supaya simetris dalam menskalakan perhitungan sudut orientasi (misal -n div 2,…,-1, 0, 1,…,n div 2). citra 3 dimensi ini juga bisa didekomposisi menjadi kumpulan citra sebanyak n yang masing-masing mewakili tiap sudut.

penggunaan citra integral akan memudahkan untuk membuat fitur HOG dalam berbagai skala resolusi karena kompleksitas komputasi untuk menghitung fitur HOG berukuran 8×8 piksel, 16×16 piksel, atau NxN berapapun N sama saja (2 penjumlahan dan 2 pengurangan). Hal ini akan sangat bermanfaat karena biasanya fitur HOG tidak digunakan dalam satu skala resolusi saja melainkan multi-skala. Implementasi Dalal dan Triggs menggunakan banyak skala sedangkan pengembangan oleh Pedro F. Felzenzswalb yang memenangkan perlombaan PASCAL VOC tahun 2009 menggunakan dua buah skala dan cakupan (root dan kumpulan part).

langkah selanjutnya adalah memanfaatkan citra HOG integral untuk menghitung fitur HOG.

def calc_hog_block(hogim, r):
    """
    calculate HOG feature given a rectangle and integral HOG image
    
    returns
        HOG feature (not normalized)

    params
        hogim : integral HOG image
        r : 4-tuple representing rect (left,top,right,bottom)
    """
    numorient = hogim.shape[2]
    result = np.zeros(numorient)
    for ang in xrange(numorient):
        result[ang] = hogim[r[1],r[0],ang] + hogim[r[3],r[2],ang] - hogim[r[1],r[2],ang] - hogim[r[3],r[0],ang]

    return result

Seperti terlihat pada kode di atas, berapapun dimensi area yang akan dihitung fitur HOG lokalnya kompleksitasnya konstan. Hasil histogram di atas tidak dinormalisasi melainkan diserahkan kepada kode yang menggunakan setelahnya. Hal ini disebabkan ada beberapa kombinasi norm yang dapat digunakan untuk menormalisasi vektor/histogram yang dihasilkan dari fungsi di atas.

Sebagai contoh pemanfaatan fitur HOG agar tulisannya tidak terlalu panjang, saya akan tampilkan bagaimana memvisualisasikan fitur HOG pada setiap area citra.

def draw_hog(target, ihog, cellsize=8):
    """
    visualize HOG features
    
    returns
        None
        
    params
        target  : target image
        ihog    : integral HOG image
        cellsize: size of HOG feature to be visualized (default 8x8)
        
    """
    ow,oh = cv.GetSize(target)
    halfcell = cellsize/2
    w,h = ow/cellsize,oh/cellsize
    norient = ihog.shape[2]
    mid = norient/2

    for y in xrange(h-1):
        for x in xrange(w-1):
            px,py=x*cellsize,y*cellsize
            #feat = calc_hog_block(ihog, (px,py,max(px+cellsize, ow-1),max(py+cellsize, oh-1)))
            feat = calc_hog_block(ihog, (px, py, px+cellsize, py+cellsize))
            px += halfcell
            py += halfcell
            
            #L1-norm, nice for visualization
            mag = np.sum(feat)
            maxv = np.max(feat)
            if mag > 1e-3:
                nfeat = feat/maxv
                N = norient
                fdraw = []
                for i in xrange(N):
                    angmax = nfeat.argmax()
                    valmax = nfeat[angmax]
                    x1 = int(round(valmax*halfcell*np.sin((angmax-mid)*np.pi/mid)))
                    y1 = int(round(valmax*halfcell*np.cos((angmax-mid)*np.pi/mid)))
                    gv = int(round(255*feat[angmax]/mag))
                    
                    #don't draw if less than a threshold
                    if gv < 30:
                        break
                    fdraw.insert(0, (x1,y1,gv))
                    nfeat[angmax] = 0.
                    
                #draw from smallest to highest gradient magnitude
                for i in xrange(len(fdraw)):
                    x1,y1,gv = fdraw[i]
                    cv.Line(target, (px-x1,py+y1), (px+x1,py-y1), cv.CV_RGB(gv, gv, gv), 1, 8)
            else:
                #don't draw if there's no reponse
                pass

cellsize adalah ukuran dari area yang dihitung untuk mendapatkan HOG lokal. Setiap histogram digambarkan sebagai garis yang orientasinya menyesuaikan. Ada sedikit perbedaan di sini yaitu arah kemiringan garis yang divisualisasikan bukan menggambarkan arah gradien melainkan diputar 90 derajat (tegak lurus) atau normal dari gradien. Hal ini dilakukan untuk memudahkan evaluasi secara visual karena garis yang digambar bersesuaian dengan puncak dari gradien di citra asal.

Contoh penggunaan fungsi-fungsi dan prosedur di atas ada pada kode berikut.

im = cv.LoadImage('gambar.jpg')

#image for visualization
vhog = cv.CreateImage(cv.GetSize(im), 8, 1)

hog = calc_hog(im)

draw_hog(vhog, hog, 8)
cv.ShowImage('hi', vhog)

#clear for reuse
cv.Set(vhog, 0)

draw_hog(vhog, hog, 16)
cv.ShowImage('lo', vhog)

key = cv.WaitKey(0)

Kekurangan dari kode di atas adalah, untuk menghitung citra HOG diperlukan waktu yang cukup lama yang mungkin disebabkan oleh overhead di python dan numpy. Karena saya masih bereksperimen dan belum berencana membuat aplikasi yang interaktif menggunakan HOG, Hal ini masih ditoleransi. Mungkin saya akan mempertimbangkan untuk menggunakan interface lain untuk memanfaatkan fitur HOG ini (C,C++,atau C#). Contoh hasil penghitungan dan visualisasi fitur HOG dapat dilihat pada gambar-gambar berikut.

citra asal

Tampilan fitur HOG dengan parameter area lokal 8x8 piksel

Tampilan fitur HOG dengan parameter area lokal 4x4 piksel

Sampai dengan kondisi di atas, saya masih ragu melakukan klasifikasi (misal mendeteksi objek mobil pada citra di atas) hanya dengan melihat visualisasinya saja tampak kurang diskriminatif. Sepertinya masih perlu dibuktikan apakah bisa melakukan deteksi objek hanya berdasarkan fitur HOG tersebut. Mari kita lanjutkan lain kali saja.

ralat

• untuk menampilkan gambarnya harusnya cos untuk y dan sin untuk x, dan tanda untuk y dinegasikan, gambar akan diupdate segera.

hasil visualisasi HOG 8x8 (yang benar)

visualisasi HOG 4x4 (yang benar)

jadi selama ini yang salah itu cara visualisasinya. Kalau begini saya jadi optimis mencoba menerapkan SVM untuk klasifikasi objek (mobil misalny). Mungkin juga mengasosiasikan model bagian dengan segmentation mask untuk digabung dengan grabcut (eh, ngebocorin kerjaan).

About these ads

Filed under: computer vision, hacking, image processing, programming   |  6 Komentar
Kaitkata:hog, opencv, python