Accurate and low complex cell histogram generation by bypass the gradient of pixel computation

Histogram of Oriented Gradient (HOG) is a popular feature description for the purpose of object detection. However, HOG algorithm requires a high performance system because of its complex operation set. In HOG algorithm, the cell histogram generation is one of the most complex part, it uses inverse tangent, square, square root, floating point multiplication. In this paper, we propose an accurate and low complex cell histogram generation by bypass the gradient of pixel computation. It employs the bin's boundary angle method to determine the two quantized angles. However, instead of choosing an approximate value of tan, the nearest greater and the nearest smaller of each tan value from the ratios between pixel's derivative in y and x direction are used. The magnitudes of two bins are the solutions of a system of two equations, which represents the equality of the gradient of a pixel and its two bins in both vertical and horizontal direction. The proposed method spends only 30 addition and 40 shift operations to caculate two bins of a pixel. Simulation results show that the percentage of error when reconstructing the differences in x and y direction are always less than 2% with 8-bit length of the fractional part. Additionally, manipulating the precision of gradient magnitude is very simple by pre-defined sine and cosine values of quantized angles. The synthesis results of a hardware implementation of the proposed method occupy 3.57 KGEs in 45nm NanGate standard cell library. The hardware module runs at the maximum frequency of 400 MHz, and the throughput is 0.4 pixel/ns for a single module. It is able to support 48 fps with 4K UHD resolution.