I was calculating which would be faster in computation, Inverse Fast Fourier Transform or Histogram Of Gradient but I am unable to calculate its running time.
What would be the running time of Histogram Of Gradient if the image has 'p' pixels ?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Running time depends wholly on hardware. You can also have more precise or less precise implementations, leading to different execution times. Computational complexity is O(p). Why are you unable to determine running time? $\endgroup$– Cris LuengoCommented Mar 22, 2018 at 20:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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&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
