HOG (Histogram of Oriented Gradients)

Refs

From Lilian Weng’s blog (có codes)

Phạm Đình Khánh | Bài 17 - Thuật toán HOG (Histrogram of oriented gradient) ← có codes

⭐ C34 | HOG Feature Vector Calculation | Computer Vision | Object Detection | EvODN - YouTube

C37 | Dalal & Triggs Object Detection | HOG + SVM | Computer Vision | Machine Learning | EvODN - YouTube

Infos

Trước khi các thuật toán DL ra đời (YOLO, SSD, Faster RCNN,…)

Một thuật toán cổ điển để xử lý ảnh + cũng khá hiệu quả! → object detection

Những ứng dụng

human detection (this article)

face detection (biểu diễn đường nét khuôn mặt theo độ lớn các vector)

HOG tạo các feature cho các bài toán phân loại ảnh.

How HOG works?

Từ cái hình thiệt bự → lấy 1 khung hình chỉ bao quanh người

Ví dụ, ref.

Mỗi hình chia thành lưới blocks, mỗi block gồm 8x8 pixels. Sau đó mỗi pixel (của 64 cái), tính gradient magnitude (GM) & gradient direction (GD) → cần tính tổng cộng (8x8)x2

Ví dụ cách tính GM và GD ở mỗi pixel (ref)

Chia GD theo 9 bins (do GD trong hình trên → mỗi bin là 20) ← Có nghĩa là thay vì các gradient direction đi mọi hướng từ 0→180 độ thì ta chỉ xét 9 hướng “feature” tương ứng với 9 bins mà thôi!

Sau đó GD và GM sẽ được ghép cặp với nhau theo từng pixel → nếu cái nào “nằm giữa” (ko rơi ngay vào các đầu mút như 0, 20, 40,…) thì sẽ chia theo phần nó chiếm trong GD (hình dưới 10 nằm ngay giữa nên chia 4 thành 2,2).

Nó không hẳn là 1 cái bin kiểu [a,b]. Chỉ là mình chọn ra 9 “độ” đại diện (feature) thì sẽ có lần lượt 0, 20, 40,…., 160. Suy ra:

10 cách 0 10, cách 20 cũng 10 → chia 2

Còn nếu 15: 15 cách 0 = 3*(15 cách 20) ← nó gần 20 hơn 3 lần so với nó gần 0 nên chia bin 20 nhiều hơn 3 lần → giả sử GD là 8 thì sẽ chia cho bin 20 6, còn bin 0 là 2.

Còn ở hình này: 165 gần 160 khoảng cách 5 trong khi gần 0 khoảng cách 180-165= 15 (gấp 3) → chia cho bin 160 3 lần chia cho bin 0 → 85/4*3 = 63.75 cho bin 60.

Tính tổng tất cả GM thuộc cùng 1 bin

Mỗi vector đại diện cho 1 bin, độ dài của vector chính là độ cao của mỗi bin.

Then we slide a 2x2 cells (thus 16x16 pixels) block across the image.

Then chuẩn hoá (eg. 2 bức ảnh cùng nội dung nhưng 1 cái tối hơn thì vector histogram cũng sẽ gấp đôi ← cần chuẩn hoá để 2 bức này có cùng 1 vector biểu diễn)

Tính toán HOG feature ← Sau khi chuẩn hóa các véc tơ histogram, chúng ta sẽ concatenate các véc tơ 1x36 này thành một véc tơ lớn (36 = 9 vector đặc trưng x 4 blocks đã chọn trước khi slice). Đây chính là véc tơ HOG đại diện cho toàn bộ hình ảnh.

Biểu diễn phân phối HOG trên ảnh

Đối với mỗi một ô trên lưới ô vuông, chúng ta biểu diễn phân phối HOG bao gồm nhóm 9 véc tơ chung gốc chiều dài bằng độ lớn gradient và góc bằng phương gradient. Khi đó chiều của nhóm các véc tơ sẽ tương đối giống với dáng của vận động viên trong ảnh, đặc biệt là tại các vị trí chân và tay.

Một ví dụ khác. Ref.

Sau đó áp dụng HOG kết hợp với SVM chẳng hạn để detect object

Code

👇 Code lấy ở đây.

1from skimage.feature import hog
2from sklearn import svm
3from matplotlib import pyplot as plt
4
5ppc = 16
6hog_images = []
7hog_features = []
8for image in data_gray:
9    fd,hog_image = hog(image, orientations=8, pixels_per_cell=(ppc,ppc),cells_per_block=(4, 4),block_norm= 'L2',visualise=True)
10    hog_images.append(hog_image)
11    hog_features.append(fd)
12    
13plt.imshow(hog_images[51])

Trong đây có đầy đủ các tham số cho các bước ở trên: orientations (ở trên là 9, đây là 8), pixels_per_cell (ở trên là 8, đây là 16), cells_per_block (ô vuông để slice, trên là 2x2, đây là 4x4)

👇 Cũng có thể code thông qua OpenCV (code lấy ở đây)

1import cv2
2
3# Load the image and convert to grayscale
4img = cv2.imread('image.jpg')
5gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
6
7# define each block as 4x4 cells of 64x64 pixels each
8cell_size = (128, 128)      # h x w in pixels
9block_size = (4, 4)         # h x w in cells
10win_size = (8, 6)           # h x w in cells
11
12nbins = 9  # number of orientation bins
13img_size = img.shape[:2]  # h x w in pixels
14
15# create a HOG object
16hog = cv2.HOGDescriptor(
17    _winSize=(win_size[1] * cell_size[1],
18              win_size[0] * cell_size[0]),
19    _blockSize=(block_size[1] * cell_size[1],
20                block_size[0] * cell_size[0]),
21    _blockStride=(cell_size[1], cell_size[0]),
22    _cellSize=(cell_size[1], cell_size[0]),
23    _nbins=nbins
24)
25n_cells = (img_size[0] // cell_size[0], img_size[1] // cell_size[1])
26
27# find features as a 1xN vector, then reshape into spatial hierarchy
28hog_feats = hog.compute(img)
29hog_feats = hog_feats.reshape(
30    n_cells[1] - win_size[1] + 1,
31    n_cells[0] - win_size[0] + 1,
32    win_size[1] - block_size[1] + 1,
33    win_size[0] - block_size[0] + 1,
34    block_size[1],
35    block_size[0],
36    nbins)
37print(hog_feats.shape)

Or detect people in an image using directly OpenCV

1import cv2
2
3# Load the image and convert it to grayscale
4img = cv2.imread('people.jpg')
5
6hog = cv2.HOGDescriptor()
7hog.setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector())
8
9# Detect people in the image
10locations, confidence = hog.detectMultiScale(img)
11
12# Draw rectangles around the detected people
13for (x, y, w, h) in locations:
14    cv2.rectangle(img, (x, y), (x + w, y + h), (0, 0, 255), 5)
15
16# Display the image with detected people
17cv2.imshow('People', img)
18cv2.waitKey(0)
19cv2.destroyAllWindows()

Understand HOC (archived)

HOG + SVG (support vector machine)

⭐ An example of codes using HOG and SVG on Kaggle.

👇 (video của cái đứa ở trên luôn) HOG + SVM & Dalal & Triggs (25K citations)

Steps to get the SVG coefficients

(Cái hình đen bên phải ở hình dưới)

1K images with people

1K images without people

HOG features of the images

Train SVM Classifier

Sliding windows

QUESTION: Làm sao để có thể detect được người trong 1 hình lớn? ← làm sao biết người đó đứng ở đâu mà có được ái khung bao quanh?

→ Using sliding windows → for each of window: sử dụng HOG và use SVM để xác định xem có người hay ko!

Bắt đầu từ góc trên bên trái, nhích từng chút một sang phải rùi xuống dưới. Xong áp dụng thuật toán HOG và đưa vào SVM để check xem có phải người hay không. Nếu phải thì xác định được position của khung, còn ko thì tiếp tục.

Ví chúng ta dùng sliding windows nên chúng ta có thể biết được coordinates của windows khi tìm thấy object!

Problem: Nếu sliding window quá lớn / quá nhỏ so với object? → Dùng technique “Image Pyramid”

Image pyramid technique

Start with original image → phát hiện some object → down scale hình rùi slide windows → phát hiện (hoặc ko) object → làm cho đến khi nào phát hiện được object quá khổ thì thui!

❓ Down scale bao nhiêu? Down đến khi nào?