Object Detection

For each $X\times Y$ sub-image in the original image, we have to calculate $(x-y)^2 = x^2 - 2xy + y^2$ and sum them up.
Now calculating $x^2$ and $y^2$ is relatively simple, as it can be handled using cumulative sum. But calculating the term $xy$ brings additional complexity.
We can do convolution to do that in $O(n*log(n))$ time using FFT, where $n$ is the total size of the grid. How do we do that?

Let’s first convert the 2D image to a 1D array. We write the elements in the array row wise, $A_{1,1}, A_{1,2}, A_{1,3}, \dots, A_{1,m}, A_{2,1}, A_{2,2}, A_{2,3}, \dots, A_{2,m}, A_{3,1}, \dots, \dots, A_{n,m}$.

Now for calculating the distances match, let’s first put the sub-image at the top-left corner and pad the sub-image with zeroes to make both of the image equal-sized. After that convert that image to a 1D array like the previous one. Now, the dot product of those two images will be the sum of all $xy$ pairs. The dot product can be calculated in $O(n)$, but for all possible sub-images if we calculate that, the complexity will become $O(n*n)$ which will not be enough.

Notice that if we do 1 right shift to our padded sub-image, it moves the image one column to the right. and if we continue this we can replicate all possible sub-image pairs doing only right shifts. Using convolution we can calculate all those dot products in a single iteration. Use FFT for convolution and we got a complexity of $O(n*log(n))$.

How to calculate dot products of all the cyclic shifts using convolution(FFT)? This blog explains it better if you’re interested.