How do I explain the Histogram of Oriented Gradients algorithm to a layman?
Finding the "gradient" of a pixel is finding if there is an edge passing through that pixel, the orientation of that egde and how visible is this edge.
As we are taking into account the direction of the edges, we say "oriented gradients".
The "histogram" counts how many pixels have an edge with a specific orientation. The pixels that have visible edges count more than the pixels that have soft edges.
For example if we have a square in the image, we will see that the HOG has a lot of pixels counted in the vertical direction, and the same amount of pixels counted in the horizontal direction, no pixels would get counted in the diagonal directions. If we had a rectangle laying flat, there would be more pixels in the horizontal direction than in the vertical, because the horizontal edges are longer. If we had a diamond, we would count pixels with diagonal edges. This way you can recognize shapes just comparing the histograms (how many pixels have edges in each direction).
If we need to find squares (or faces, or people or anything) of a specific size, we divide the image in blocks of the size of the squares we want to find and compare the HOG that we obtain with the HOG of the thing that we are searching.
I have found the lecture given by Dr. Silvio on HoG to be extremely effective in explaining the concept. I have used to this when I was studying myself and also for explanation to others and it has worked really well every time. HTH
PS - Copyrights for the slides belong to Dr. Silvio and his group.