Histogram of Gradient
For the sake of putting some numbers to this question, I implemented a basic histogram of gradient from scikit-image (skimage.feature.hog). Here is the timing data for HOG with default parameters applied to the skimage.data.astronaut image in b&amp;w and rescaled to have the given dimensions:

Image dimensions......(102, 102)
3.49 ms ± 26.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Image dimensions......(256, 256)
27.5 ms ± 295 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Image dimensions......(512, 512)
123 ms ± 2.88 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Image dimensions......(768, 768)
284 ms ± 9.18 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Image dimensions......(1024, 1024)
509 ms ± 8.62 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Image dimensions......(2048, 2048)
2 s ± 15.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


And here is timing data for the inverse Fourier transform (np.fft.ifft2) on the Fourier transform of the same set of images. (Note that taking the Fourier transform is not included in the timing results)

Image dimensions......(102, 102)
684 µs ± 32.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Image dimensions......(256, 256)
2.51 ms ± 26.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Image dimensions......(512, 512)
21 ms ± 519 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Image dimensions......(768, 768)
42.5 ms ± 621 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Image dimensions......(1024, 1024)
85.9 ms ± 1.47 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Image dimensions......(2048, 2048)
381 ms ± 9.18 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


Graph of the timing data