Histogram of Oriented Gradient in Numpy

Di tulisan terdahulu saya pernah mencoba menulis tentang menghitung fitur HOG lalu tulisan tentang mempercepat perhitungan hog dengan menggunakan inlince c++ dari scipy. Tulisan kali ini sebetulnya hampir sama dengan tulisan terdahulu, yaitu menghitung fitur yang sama, yang berbeda adalah tulisan yang dulu dibuat dengan menggunakan interface opencv versi 1 (import cv) sedangkan tulisan kali ini dibuat menggunakan interface versi kedua (cv2). Pada opencv versi pertama, objek citra disimpan menggunakan struktur berbasis C (IplImage) sedangkan di versi 2, objek citra sudah terintegrasi dengan Numpy array (ndarray) dan opencv versi 2 sudah ditulis ulang dengan menggunakan C++. Dengan terintegrasinya struktur penyimpanan citra menjadi array numpy, maka operasi2 pengolahan citra jadi seperti yang dilakukan dengan MATLAB. operasi-operasi tertentu juga menjadi makin mudah melalui operasi array slicing yang ada pada Numpy. Oleh sebab itu, saya coba membuat algoritma penghitungan fitur HOG yang mengeksploitasi fasiltas yang ada di Numpy yang lebih cepat karena menghindari loop yang eksplisit dilakukan pada kode python tetapi mendelegasikan operasi yang bersifat element-wise ke numpy.

modul yang diimpor
kalau di versi opencv pertama modul yang digunakan adalah cv, maka sekarang adalah cv2. modul cv masih dapat diakses untuk menjaga kompatibilitas ke versi sebelumnya menjadi submodul di dalam cv2.

# jika ingin menggunakan antarmuka opencv versi 1
import cv2.cv as cv 
# interface opencv versi 2
import numpy as np
import cv2

Menghitung HOG secara umum
fitur HOG yang dibahas pada tulisan ini adalah varian penyederhanaan dari varian-varian utama yang digunakan saat ini :

  • varian HOG Dalal-Triggs untuk pedestrian detection
  • varian HOG Felzenswalb untuk deformable part model di PASCAL VOC (Visual Object Categories/Classes) Challenge


Algoritma penghitungan fitur HOG umumnya dilakukan dengan memampatkan informasi pada area berukuran tertentu (umumnya 8×8 piksel) pada citra menjadi satu piksel yang disebut sel. Masing-masing sel merupakan array berdimensi n. Di algoritma yang saya bahas, N adalah banyaknya orientasi gradien. Pada algoritma di bawah, penghitungan fitur HOG dilakukan dalam 2 tahap yaitu menghitung integral image gradien dari citra dan penyusunan ke dalam sel. Citra integral (integral image) digunakan agar penghitungan citra sel menjadi lebih cepat dengan semakin besarnya ukuran sel karena kompleksitas penghitungan tiap selnya konstan. Dengan demikian, semakin besar ukuran sel maka semakin sedikit sel yang harus dihitung. Penggunaan citra integral juga dimaksudkan agar perhitungan beberapa citra sel dalam berbagai skala sel hanya perlu dilakukan dengan satu kali menghitung gradien.

def calc_hog(im,numorient=9,cellSize=(8,8)):
    ihog = calc_hog_base(im, numorient)
    return calc_hog_cells(ihog, numorient, cellSize)

Pada algoritma di atas, ihog dapat digunakan berkali-kali jika dibutuhkan perhitungan citra sel dengan berbagai ukuran sel.

Menghitung citra integral orientasi gradien

def calc_hog_base(im, numorient=9):
    # calculate gradient using sobel operator
    gray = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)

    gray = preprocess(gray) #preprocess gray image before calculating gradient

    gx = cv2.Sobel(gray, cv2.CV_32F, 1, 0)
    gy = cv2.Sobel(gray, cv2.CV_32F, 0, 1)
    
    # calculate gradient magnitude
    mag = np.sqrt(gx*gx+gy*gy)

    # calculate gradient orientation and discretize to numorient values
    mid = numorient/2
    magor = mid+(mid*np.arctan2(gy, gx)/np.pi).astype(np.uint32)
    
    # calculate hog in pixels by grouping each pixel based on gradient orientation
    hog = np.zeros((im.shape[0], im.shape[1], numorient))
    for orien in xrange(magor.min(), magor.max()+1):
        mask = magor==orien
        hog[:,:,orien][mask] = mag[mask] + magor[mask]

    # calculate integral hog
    ihog = cv2.integral(hog)
    
    return ihog

Kode di atas ada bagian yang memanggil prosedur preprocess. Bagian ini bertujuan untuk mempersiapkan citra, karena persepsi mata terhadap perbedaan intensitas tidak linier (power law). Isi dari prosedur praproses ada 2 yaitu gamma correction dan contrast enhancement. Koreksi gamma dilakukan dengan menskalakan intensitas pada domain eksponensial dan peningkatan kontras dilakukan dengan equalisasi histogram.

Percepatan dilakukan dengan ekspresi operasi matriks seperti yang umum ditemukan dalam MATLAB. Vektorisasi dilakukan dengan menggunakan mask.

def preprocess(img):
    # gamma correction 1/4 followed by contrast boost (histogram equalization)
    return cv2.equalizeHist((np.power(img/255., 0.25)*255).astype(np.uint8))

Menghitung citra sel
Untuk menghitung citra sel dari citra integral dilakukan dengan melakukan penjumlahan dan pengurangan pada 4 titik sudut area yang akan dihitung (kiri atas + kanan bawah – kiri bawah – kanan atas).

def calc_hog_cells(ihog, numorient=9,cellSize=(8,8)):
    # calculate the dimension of hog cells image
    im_dim = np.array(ihog.shape[:2])-1
    h, w = iSize = np.ceil(im_dim/np.array(cellSize)).astype(np.uint8)
    
    # group hog into cells
    cells = np.zeros((h,w,numorient))
    for y in xrange(0, h):
        for x in xrange(0, w): 
            t = y*cellSize[1]
            l = x*cellSize[0]
            d = t + cellSize[1]
            r = l + cellSize[0]

            cells[y,x] = ihog[t,l] + ihog[d,r] - ihog[t,r] - ihog[d,l]
                
    return cells

Memvisualisasikan fitur HOG
Untuk menampilkan seperti apa fitur HOG, prosedur berikut melakukan penggambaran pada setiap sel dan digambarkan dengan menggunakan garis sesuai sudut orientasinya. Banyaknya elemen dalam histogram divisualisasikan dengan intensitas yang semakin tinggi. Kemudian citra ditransformasi sebagai Hue dalam HSV sehingga intensitas tertinggi akan berwarna merah/terang sedangkan intensitas terrendah akan berwarna merah.

def draw_hog(im, cells, cellSize):
    """
    visualize hog cells
    
    params
        im  : original image (shape is required)
        cells   : hog image cells
        cellSize    : pair specifying the size of the hog cells
    """
    orig = np.zeros(cellSize, dtype=np.uint8)
    template = [orig]
    ch,cw,numorient = cells.shape
    
    # create direction glyphs
    cv2.line(orig, (0, cellSize[1]/2), 
                (cellSize[0]-1, cellSize[1]/2), 
                (255,255,255), 1, 8)

    step = (180./(numorient))
    for k in xrange(1, numorient):
        orig = rotateImage(orig, step)
        template.append(orig)
    
    # create target image (greyscale)
    tmp = np.zeros(im.shape[:2])
    
    n = len(template)
    mid = numorient/2

    # draw overlay glyphs
    for k in xrange(0, numorient):
        cmax = cells[:,:,k].max()
        for x in xrange(0, cw):
            for y in xrange(0, ch):
                x1 = (x)*cellSize[0]+cellSize[0]/2
                y1 = (y)*cellSize[1]+cellSize[1]/2
                overlayImage(template[(k+1) % n], 
                             tmp, x1, y1, cells[y,x,k])

    img = im.copy()
    gry = (255*tmp/tmp.max()).astype(np.uint8)
    hue = (120*tmp/tmp.max()).astype(np.uint8)

    mask = gry > 10
    im[:,:,2][mask] = 255-gry[mask]
    img[:,:,1:] = 255
    img[:,:,0] = 120-hue
    img = cv2.cvtColor(img, cv2.COLOR_HSV2BGR)

    cv2.imshow("hog", img)

def overlayImage(src, target, x, y, value=1.0):
    """
    adds target to src at x, y position multiplied by value
    target offset is it's center
    """
    mid = np.array(src.shape[:2])/2
    y1 = y-mid[0]
    x1 = x-mid[1]
    target[y1:y1+src.shape[0], x1:x1+src.shape[1]] += src[:,:] * value

Hasilnya akan tampak pada gambar berikut.

citra HOG dengan sel berukuran 8x8

citra HOG dengan sel berukuran 8×8

citra HOG dengan sel berukuran 4x4

citra HOG dengan sel berukuran 4×4

gambar asal

gambar asal

Sebagai tambahan, saya tampilkan juga kode untuk menghitung fitur hog per window. sebetulnya ada beberapa hal yang berbeda dengan terminologi umum tentang fitur HOG yaitu blok dan window. Pada algoritma di bawah, window adalah blok sedangkan blok pada algoritma HOG versi Dalal-Triggs blok merupakan satu tahapan untuk melakukan normalisasi/smoothing sebelum melakukan ekstraksi sehingga perlu istilah baru yaitu window. fungsi di bawah menghasilkan list of rectangle dan list of feature. setiap fitur berasosiasi dengan informasi jendela tempat fitur tersebut diukur.

def calc_hog_descriptor(cells, cellSize, blockSize=(2,2),blockStride=(1,1)): 
    result = {}
    
    # extract feature using sliding window
    rects = []  # list of rectangle
    feats = [] # list of features
    
    # calculate the number of required block when there is overlap (blockstride < blocksize)
    h, w = cells.shape[:2]
    nblock = (np.array([w,h]) -1 - np.array(blockSize)) / np.array(blockStride)
    
    # calculate overlapping block
    for y in xrange(0, nblock[1]):
        for x in xrange(0, nblock[0]):
            t = y * blockStride[1]
            d = t + blockSize[1]
            
            l = x * blockStride[0]
            r = l + blockSize[0]
            
            rects.append((l*cellSize[0], t*cellSize[1], r*cellSize[0], d*cellSize[1]))
            
            # get concatenation of histogram as 1D array
            window = cells[t:d,l:r].copy().reshape((-1))
            
            # contrast stretch again
            w_min = window.min()
            w_max = window.max()
            window = window-w_min / (w_max-w_min)
            
            feats.append(window)

    result['rects'] = rects
    result['feats'] = feats
    return result

Penutup
Fitur HOG yang dibahas di sini merupakan versi penyederhanaan dari fitur HOG yang umum. Sifat fitur ini masih kurang diskriminatif dibandingkan fitur yang digunakan pada deteksi pejalan kaki atau untuk deteksi kategori objek. Meskipun demikian, fitur yang ditampilkan di sini cukup untuk digunakan pada tekstur yang memiliki pola yang cukup diskriminatif seperti pada gambar berikut (klasifikasi patch ditandai dengan kotak kuning).

deteksi menara komunikasi

deteksi menara komunikasi

8 comments

  1. Constantin · November 27, 2014

    Hi, where does the rotateImage() come from in draw_hog, it does not seem to be defined.

    • pebbie · Desember 11, 2014

      Hi Constantin, sorry for the late response. Thanks for noticing. The rotateImage function is short for using GetRotationMatrix2D and WarpAffine functions from opencv for rotating the image at arbitrary integer angle using the image center as rotation center. unfortunately I can’t update the code now. I’ll add an update when i get access to the code repo at another machine. until then, i hope you can manage to find some alternative implementations.

  2. gobib · Februari 17

    lagi nyari2 tutorial opencv, terima kasih mas pebbie.
    Kalau inputnya video kira2 gimana ya mas pebbie? saya lagi belajar deteksi benda menggunakan webcam

    • pebbie · Februari 17

      di opencv ada lbpcascade prebuilt untuk deteksi wajah(objek)

      • gobib · Februari 18

        udah coba tapi pake yang haar cascade yang people detect, cuma kurang akurat hehe, dan baru ke gambar sih belum ke video.

        dapat info kalo pake hog bisa lebih akurat, tapi belum tau bagaimana caranya

        makasih mas infonya

  3. Ade · 11 Days Ago

    Selamat pagi mas pebbie,
    saya sedang mengerjakan tugas akhir S1 saya mengenai pendeteksian Objek Menggunakan Deformable Part Model, saya masih bingung bagaimana cara membuat data training baru berdasarkan dataset yang saya buat, bebarapa referensi sudah saya coba, saya belum bisa-bisa, mohon pencerahannya mas pebbie, terimakasih.
    saya menjalankan di system windows 64 bit, untuk referensi DPMnya saya temukan disini : https://github.com/ApprenticeZ/voc-release-3.1-win,

    terimakasih

    • pebbie · 10 Days Ago

      Halo Ade,

      contoh data untuk training ada di voc dataset. deskripsi formatnya ada di dokumentasinya. ada juga beberapa script untuk konversi anotasi dari tools lain ke format training file pascal voc.

  4. diodev · 10 Days Ago

    Kak mau nanya tentang HOG, karena saya mengambil topik tugas akhir ttg image processing dengan metode HOG.
    1. Apa aja ya parameter yang membuat akurasi sistem tinggi dengan HOG?
    2. kelebihan HOG sendiri apa?
    3. bisa kah HOG dijadikan metode untuk ekstraksi ciri berupa warna agar bisa diklasifikasi ke beberapa kelas? contohnya Kualitas AA, A, B gitu kak… makasih sebelumnya.

    Kalo ada waktu tolong jawab ya kak ke email saya aja ya kak
    terimakasih sebelumnya maaf kepanjangan nanya nya hehe

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s