Apply Walsh Hadamard Transform (WHT) on Image Patches of Odd Size

Question

I was reading this paper on optical flow, which as apart of the algorithm makes use Walsh-Hadamard transform on image patches of size 2r+1. So far, where ever I have looked, I could only find that WHTs require matrices of orders of powers of 2. In a footnote, they have mentioned splitting the patches in the middle for this purpose into sizes of r and r+1 which is something that I don't understand.

The paper: Flow Fields: Dense Correspondence Fields for Highly Accurate Large Displacement Optical Flow Estimation.

Answer 1

The relevant section in the paper is given by:

They use the method in the paper (Which is referenced as [6]): Computing Nearest Neighbor Fields via Propagation Assisted Kd Trees:

While Computing Nearest Neighbor Fields via Propagation Assisted Kd Trees is using 16 bases they use only 9.

The trick used is as following:

So computing 9 basis requires the patch to be a multiplication of 3.
So they split the patch of (2r + 1) x (2r + 1) into 4 patches of either r x r or (r + 1) x (r + 1) (2 of each) and then importable it make compatible so its vectorized size is a multiplication of 3.