极客教程简单物体检测第一步—-滑动窗口（Sliding Window）+HOG
从这里开始进行物体检测吧！
物体检测是检测图像中到底有什么东西的任务。例如，图像在[x_1, y_1, x_2, y_2]处有一只狗。像这样把物体圈出来的矩形我们称之为Bounding-box。
下面实现简单物体检测算法：
- 从图像左上角开始进行滑动窗口扫描；
- 在滑动的过程中，会依次圈出很多矩形区域；
- 裁剪出每个矩形区域对应的图像，并对裁剪出的图像提取特征（HOG，SIFT等）；
- 使用分类器（CNN，SVM等）以确定每个矩形是否包含目标。
这样做的话，会得到一些裁剪过的图像和其对应的矩形的坐标。目前，物体检测主要通过深度学习（Faster R-CNN、YOLO、SSD等）进行，但是这种滑动窗口方法在深度学习开始流行之前已成为主流。为了学习检测的基础知识我们使用滑动窗口来进行检测。
我们实现步骤1至步骤3。
在imorimany.jpg上检测蝾螈的头吧！条件如下：
- 矩形使用以下方法表示：
# [h, w]
recs = np.array(((42, 42), (56, 56), (70, 70)), dtype=np.float32)
- 滑动步长为4个像素（每次滑动一个像素固然是好的，但这样需要大量计算，处理时间会变长）；
- 如果矩形超过图像边界，改变矩形的形状使其不超过图像的边界；
- 将裁剪出的矩形部分大小调整为32\times32；
- 计算HOG特征值时 cell 大小取8\times8。
python实现：
import cv2
import numpy as np
np.random.seed(0)
# get HOG
def HOG(img):
# Grayscale
def BGR2GRAY(img):
gray = 0.2126 * img[..., 2] + 0.7152 * img[..., 1] + 0.0722 * img[..., 0]
return gray
# Magnitude and gradient
def get_gradXY(gray):
H, W = gray.shape
# padding before grad
gray = np.pad(gray, (1, 1), 'edge')
# get grad x
gx = gray[1:H+1, 2:] - gray[1:H+1, :W]
# get grad y
gy = gray[2:, 1:W+1] - gray[:H, 1:W+1]
# replace 0 with
gx[gx == 0] = 1e-6
return gx, gy
# get magnitude and gradient
def get_MagGrad(gx, gy):
# get gradient maginitude
magnitude = np.sqrt(gx ** 2 + gy ** 2)
# get gradient angle
gradient = np.arctan(gy / gx)
gradient[gradient < 0] = np.pi / 2 + gradient[gradient < 0] + np.pi / 2
return magnitude, gradient
# Gradient histogram
def quantization(gradient):
# prepare quantization table
gradient_quantized = np.zeros_like(gradient, dtype=np.int)
# quantization base
d = np.pi / 9
# quantization
for i in range(9):
gradient_quantized[np.where((gradient >= d * i) & (gradient <= d * (i + 1)))] = i
return gradient_quantized
# get gradient histogram
def gradient_histogram(gradient_quantized, magnitude, N=8):
# get shape
H, W = magnitude.shape
# get cell num
cell_N_H = H // N
cell_N_W = W // N
histogram = np.zeros((cell_N_H, cell_N_W, 9), dtype=np.float32)
# each pixel
for y in range(cell_N_H):
for x in range(cell_N_W):
for j in range(N):
for i in range(N):
histogram[y, x, gradient_quantized[y * 4 + j, x * 4 + i]] += magnitude[y * 4 + j, x * 4 + i]
return histogram
# histogram normalization
def normalization(histogram, C=3, epsilon=1):
cell_N_H, cell_N_W, _ = histogram.shape
## each histogram
for y in range(cell_N_H):
for x in range(cell_N_W):
#for i in range(9):
histogram[y, x] /= np.sqrt(np.sum(histogram[max(y - 1, 0) : min(y + 2, cell_N_H),
max(x - 1, 0) : min(x + 2, cell_N_W)] ** 2) + epsilon)
return histogram
# 1. BGR -> Gray
gray = BGR2GRAY(img)
# 1. Gray -> Gradient x and y
gx, gy = get_gradXY(gray)
# 2. get gradient magnitude and angle
magnitude, gradient = get_MagGrad(gx, gy)
# 3. Quantization
gradient_quantized = quantization(gradient)
# 4. Gradient histogram
histogram = gradient_histogram(gradient_quantized, magnitude)
# 5. Histogram normalization
histogram = normalization(histogram)
return histogram
# get IoU overlap ratio
def iou(a, b):
# get area of a
area_a = (a[2] - a[0]) * (a[3] - a[1])
# get area of b
area_b = (b[2] - b[0]) * (b[3] - b[1])
# get left top x of IoU
iou_x1 = np.maximum(a[0], b[0])
# get left top y of IoU
iou_y1 = np.maximum(a[1], b[1])
# get right bottom of IoU
iou_x2 = np.minimum(a[2], b[2])
# get right bottom of IoU
iou_y2 = np.minimum(a[3], b[3])
# get width of IoU
iou_w = iou_x2 - iou_x1
# get height of IoU
iou_h = iou_y2 - iou_y1
# get area of IoU
area_iou = iou_w * iou_h
# get overlap ratio between IoU and all area
iou = area_iou / (area_a + area_b - area_iou)
return iou
# resize using bi-linear
def resize(img, h, w):
# get shape
_h, _w, _c = img.shape
# get resize ratio
ah = 1. * h / _h
aw = 1. * w / _w
# get index of each y
y = np.arange(h).repeat(w).reshape(w, -1)
# get index of each x
x = np.tile(np.arange(w), (h, 1))
# get coordinate toward x and y of resized image
y = (y / ah)
x = (x / aw)
# transfer to int
ix = np.floor(x).astype(np.int32)
iy = np.floor(y).astype(np.int32)
# clip index
ix = np.minimum(ix, _w-2)
iy = np.minimum(iy, _h-2)
# get distance between original image index and resized image index
dx = x - ix
dy = y - iy
dx = np.tile(dx, [_c, 1, 1]).transpose(1, 2, 0)
dy = np.tile(dy, [_c, 1, 1]).transpose(1, 2, 0)
# resize
out = (1 - dx) * (1 - dy) * img[iy, ix] + dx * (1 - dy) * img[iy, ix + 1] + (1 - dx) * dy * img[iy + 1, ix] + dx * dy * img[iy + 1, ix + 1]
out[out > 255] = 255
return out
# sliding window
def sliding_window(img, H_size=32):
# get shape
H, W, _ = img.shape
# base rectangle [h, w]
recs = np.array(((42, 42), (56, 56), (70, 70)), dtype=np.float32)
# sliding window
for y in range(0, H, 4):
for x in range(0, W, 4):
for rec in recs:
# get half size of ractangle
dh = int(rec[0] // 2)
dw = int(rec[1] // 2)
# get left top x
x1 = max(x - dw, 0)
# get left top y
x2 = min(x + dw, W)
# get right bottom x
y1 = max(y - dh, 0)
# get right bottom y
y2 = min(y + dh, H)
# crop region
region = img[max(y - dh, 0) : min(y + dh, H), max(x - dw, 0) : min(x + dw, W)]
# resize crop region
region = resize(region, H_size, H_size)
# get HOG feature
region_hog = HOG(region).ravel()
# read detect target image
img = cv2.imread("imori_many.jpg")
sliding_window(img)