Histogram of Oriented Gradients (HOG)

1 Submission

• Assignment due: Sep 20 (11:55pm)
• Individual assignment
• 1 page summary write-up with resulting visualization (more than 1 page assign- ment will be automatically returned.).
• Submission through Canvas.
• You will complete HOG.py that contains the following functions:
  • extract_hog
  • get_differential_filter
  • filter_image
  • get_gradient
  • build_histogram
  • get_block_descriptor

The code can be downloaded from
https://www-users.cs.umn.edu/~hspark/csci5561_F2019/HOG.zip.

• The function that does not comply with its specification will not be graded (no credit).
• The code must be run with Python 3 interpreter.
• Required python packages: numpy,matplotlib, andopencv.
  • numpy & matplotlib: https://scipy.org/install.html
  • opencv:https://pypi.org/project/opencv-python/
• You are not allowed to use any high level python functions of image processing and computer vision, e.g.,cv2.filter2D. Please consult with TA if you are not sure about the list of allowed functions.
• We provide a visualization code. The resulting HOG descriptor must be able to be visualized with the provided code: def visualize_hog_block(im, hog, cell_size, block_size)

Histogram of Oriented Gradients (HOG)

2 HOG

Figure 1: Histogram of oriented gradients. HOG feature is extracted and visualized for (a) the entire image and (b) zoom-in image. The orientation and magnitude of the red lines represents the gradient components in a local cell.

In this assignment, you will implement a variant of HOG (Histogram of Oriented Gradi- ents) in Python proposed by Dalal and Trigg [1] (2015 Longuet-Higgins Prize Winner). It had been long standing top representation (until deep learning) for the object detec- tion task with a deformable part model by combining with a SVM classifier [2]. Given an input image, your algorithm will compute the HOG feature and visualize as shown in Figure 1 (the line directions are perpendicular to the gradient to show edge alignment). The orientation and magnitude of the red lines represents the gradient components in a local cell.

def extract_hog(im): ... return hog Input: input gray-scale image withuint8format. Output:HOG descriptor. Description: You will compute the HOG descriptor of input imageim. The pseudo- code can be found below:

Algorithm 1HOG 1: Convert the gray-scale image tofloatformat and normalize to range [0, 1]. 2: Get differential images usingget_differential_filterandfilter_image 3: Compute the gradients usingget_gradient 4: Build the histogram of oriented gradients for all cells usingbuild_histogram 5: Build the descriptor of all blocks with normalization usingget_block_descriptor 6: Return a long vector (hog) by concatenating all block descriptors.

Histogram of Oriented Gradients (HOG)

2.1 Image filtering

m

n

(a) Input image (b) Differential along x
direction

(c) Differential along y
direction

Figure 2: (a) Input image dimension. (b-c) Differential image alongxandydirections.

def get_differential_filter(): ... return filter_x, filter_y Input: none. Output: filter_xandfilter_yare 3×3 filters that differentiate alongxandydi- rections, respectively. Description: You will compute the gradient by differentiating the image alongxand ydirections. This code will output the differential filters.

def filter_image(im, filter): ... return im_filtered Input: imis the gray scalem×nimage (Figure 2(a)) converted to float format and filteris a filter (k×kmatrix) Output: im_filteredism×nfiltered image. You may need to pad zeros on the boundary on the input image to get the same size filtered image. Description:Given an image and filter, you will compute the filtered image. Given the two functions above, you can generate differential images by visualizing the magnitude of the filter response as shown in Figure 2(b) and 2(c).

Histogram of Oriented Gradients (HOG)

2.2 Gradient Computation

(a) Magnitude

0

20

40

60

80

100

120

140

160

180

(b) Angle (c) Gradient (d) Zoomed eye (e) Zoomed neck

Figure 3: Visualization of (a) magnitude and (b) orientation of image gradients. (c-e) Visualization of gradients at every 3rd pixel (the magnitudes are re-scaled for illustrative purpose.).

def get_gradient(im_dx, im_dy): ... return grad_mag, grad_angle Input: im_dxandim_dyare thexandydifferential images (size:m×n). Output:grad_magandgrad_angleare the magnitude and orientation of the gradient images (size:m×n). Note that the range of the angle should be [0,π), i.e., unsigned angle (θ==θ+π). Description:Given the differential images, you will compute the magnitude and angle of the gradient. Using the gradients, you can visualize and have some sense with the image, i.e., the magnitude of the gradient is proportional to the contrast (edge) of the lo- cal patch and the orientation is perpendicular to the edge direction as shown in Figure 3.

Histogram of Oriented Gradients (HOG)

2.3 Orientation Binning

Ignore thi s sha de d are a

cell_s ize

Store gradi ent mag

4 3,

M

N

( u , v )

(a) orihisto

165  15  45  75  105  135  165 

Sum

of

magni

tude

s

(b) Histogram per cell

Figure 4: (a) Histogram of oriented gradients can be built by (b) binning the gradients to corresponding bin.

def build_histogram(grad_mag, grad_angle, cell_size): ... return ori_histo Input: grad_magandgrad_angleare the magnitude and orientation of the gradient images (size:m×n);cell_sizeis the size of each cell, which is a positive integer. Output: ori_histois a 3D tensor with size M×N×6 where M andN are the number of cells alongyandxaxes, respectively, i.e.,M =bm/cell_sizecandN = bn/cell_sizecwhereb·cis the round-off operation as shown in Figure 4(a). Description:Given the magnitude and orientation of the gradients per pixel, you can build the histogram of oriented gradients for each cell.

ori_histo(i,j,k) =

∑

(u,v)∈Ci,j

grad_mag(u,v) ifgrad_angle(u,v)∈θk (1)

whereCi,jis a set of xandy coordinates within the (i,j) cell, andθk is the angle range of each bin, e.g.,θ 1 = [165◦, 180 ◦)∪[0◦, 15 ◦),θ 2 = [15◦, 45 ◦), θ 3 = [45◦, 75 ◦), θ 4 = [75◦, 105 ◦),θ 5 = [105◦, 135 ◦), andθ 6 = [135◦, 165 ◦). Therefore,ori_histo(i,j,:) returns the histogram of the oriented gradients at (i,j) cell as shown in Figure 4(b). Using theori_histo, you can visualize HOG per cell where the magnitude of the line proportional to the histogram as shown in Figure 1. Typicalcell_sizeis 8.

Histogram of Oriented Gradients (HOG)

2.4 Block Normalization

Bl oc k2x2 bl oc k

Concatena tion of HOG
and normalization

Bl oc k

M

N

(a) Block descriptor

Bl oc k

M -

N -

(b) Block overlap with stride 1

Figure 5: HOG is normalized to account illumination and contrast to form a descriptor for a block. (a) HOG within (1,1) block is concatenated and normalized to form a long vector of size 24. (b) This applies to the rest block with overlap and stride 1 to form the normalized HOG.

def get_block_descriptor(ori_histo, block_size): ... return ori_histo_normalized Input:ori_histois the histogram of oriented gradients without normalization.block_size is the size of each block (e.g., the number of cells in each row/column), which is a pos- itive integer. Output:ori_histo_normalizedis the normalized histogram (size: (M−(block_size− 1))×(N−(block_size−1))×(6×block_size^2 ). Description:To account for changes in illumination and contrast, the gradient strengths must be locally normalized, which requires grouping the cells together into larger, spa- tially connected blocks (adjacent cells). Given the histogram of oriented gradients, you applyL 2 normalization as follow:

1. Build a descriptor of the first block by concatenating the HOG within the block. You can useblock_size=2, i.e., 2×2 block will contain 2× 2 ×6 entries that will be concatenated to form one long vector as shown in Figure 5(a).
2. Normalize the descriptor as follow:

ˆhi=√∑hi
ih

2
i+e^2

(2)

wherehiis theithelement of the histogram andhˆiis the normalized histogram.
eis the normalization constant to prevent division by zero (e.g.,e= 0.001).

3. Assign the normalized histogram toori_histo_normalized(1,1) (white dot lo- cation in Figure 5(a)).
4. Move to the next blockori_histo_normalized(1,2) with the stride 1 and iterate 1-3 steps above.

Histogram of Oriented Gradients (HOG)

The resultingori_histo_normalizedwill have the size of (M−1)×(N−1)×24.

Histogram of Oriented Gradients (HOG)

References

[1] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” in CVPR, 2005.

[2] P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan, “Object de- tection with discriminatively trained part based models,”TPAMI, 2010.