Computing HOG features

Question

I have one problem in the second step which is to accumulate weighted votes for gradient orientation over spatial cells.

Assuming the cell is 8*8. Let me use two matrix GO[8][8]([1 9]), GM[8][8] to represent the gradient orientation and gradient magnitude respectively. The gradient orientation ranges from 0 - 180 and there are 9 orientation bins.

According to my understanding of HOG, for every pixel in a cell, adding its gradient magnitude to its corresponding orientation bin. In this way, we can have the histogram for every cell.

But there is one sentence thats confusing me.

"To reduce aliasing, votes(gradient magnitude) are interpolated trilinearly between the neighbouring bin centers in both orientation and position."¹

Why interpolated? How to interpolate? Can someone explains more detailed? No reducing aliasing.

Thanks in advance.

---

¹ This sentence is in Navneet Dalal's PHD thesis, p38, line 4.

Answer 1

Interpolation is a standard technique for computing histograms. The idea here is that each value is not simply placed into one bin, but is distributed between two neighboring bins (assuming a 1d histogram), based on how far away it is from the center of the original bin.

The purpose of this is to deal with situations when a small error in your measurement can cause a value to be placed into a different bin. This is a very good thing to do for any type of histogram, not just for HOGs, assuming you have the CPU cycles.

There is also bi-linear and tri-linear interpolation for 2d and 3d histograms, where each value is distributed between 4 and 8 neighboring bins respectively.