We prove that the density function of the gradient of a sufficiently smooth function , obtained via a random variable transformation of a uniformly distributed random variable, is increasingly closely approximated by the normalized power spectrum of ？as the free parameter . The frequencies act as gradient histogram bins. The result is shown using the stationary phase approximation and standard integration techniques and requires proper ordering of limits. We highlight a relationship with the well-known characteristic function approach to density estimation, and detail why our result is distinct from this method. Our framework for computing the joint density of gradients is extremely fast and straightforward to implement requiring a single Fourier transform operation without explicitly computing the gradients.
References
[1]
Parzen, E. (1962) On the Estimation of a Probability Density Function and the Mode. The Annals of Mathematical Statistics, 33, 1065-1076.
https://doi.org/10.1214/aoms/1177704472
[2]
Rosenblatt, M. (1956) Remarks on Some Nonparametric Estimates of a Density Function. The Annals of Mathematical Statistics, 33, 832-837.
https://doi.org/10.1214/aoms/1177728190
[3]
Silverman, B.W. (1986) Density Estimation for Statistics and Data Analysis. Chapman and Hall/CRC, New York. https://doi.org/10.1007/978-1-4899-3324-9
[4]
Bishop, C.M. (2006) Pattern Recognition and Machine Learning (Information Science and Statistics). Springer, New York.
[5]
Jones, D.S. and Kline, M. (1958) Asymptotic Expansions of Multiple Integrals and the Method of Stationary Phase. Journal of Mathematical Physics, 37, 1-28.
https://doi.org/10.1002/sapm19583711
[6]
Cooke, J.C. (1982) Stationary Phase in Two Dimensions. IMA Journal of Applied Mathematics, 29, 25-37. https://doi.org/10.1093/imamat/29.1.25
[7]
McClure, J.P. and Wong, R. (1991) Two-Dimensional Stationary Phase Approximation: Stationary Point at a Corner. SIAM Journal on Mathematical Analysis, 22, 500-523. https://doi.org/10.1137/0522032
[8]
McClure, J.P. and Wong, R. (1997) Justification of the Stationary Phase Approximation in Time-Domain Asymptotics. Proceedings: Mathematical, Physical and Engineering Sciences, 453, 1019-1031. https://doi.org/10.1098/rspa.1997.0057
[9]
Wong, R. (1989) Asymptotic Approximations of Integrals. Academic Press, New York.
[10]
Wong, R. and McClure, J.P. (1981) On a Method of Asymptotic Evaluation of Multiple Integrals. Mathematics of Computation, 37, 509-521.
https://doi.org/10.2307/2007443
[11]
Dalal, N. and Triggs, B. (2005) Histograms of Oriented Gradients for Human Detection. IEEE Conference on Computer Vision and Pattern Recognition, 20-26 June 2005, San Diego, 886-893. https://doi.org/10.1109/CVPR.2005.177
[12]
Zhu, Q., Yeh, M.-C., Cheng, K.-T. and Avidan, S. (2006) Fast Human Detection Using a Cascade of Histograms of Oriented Gradients. IEEE Conference on Computer Vision and Pattern Recognition, New York, 17-22 June 2006, 1491-1498.
https://doi.org/10.1109/CVPR.2006.119
[13]
Suard, F., Rakotomamonjy, A. and Bensrhair, A. (2006) Pedestrian Detection Using Infrared Images and Histograms of Oriented Gradients. IEEE Conference on Intelligent Vehicles, Tokyo, 13-15 June 2006, 206-212.
https://doi.org/10.1109/IVS.2006.1689629
[14]
Bertozzi, M., Broggi, A., Del Rose, M., Felisa, M., Rakotomamonjy, A. and Suard, F. (2007) A Pedestrian Detector Using Histograms of Oriented Gradients and a Support Vector Machine Classifier. IEEE Conference on Intelligent Transportation Systems, Seattle, 30 September-3 October 2007, 143-148.
https://doi.org/10.1109/ITSC.2007.4357692
[15]
Vapnik, V.N. (1998) Statistical Learning Theory. Wiley-Interscience, New York.
[16]
Hu, R. and Collomosse, J. (2013) A Performance Evaluation of Gradient Field HOG Descriptor for Sketch Based Image Retrieval. Computer Vision and Image Understanding, 117, 790-806. https://doi.org/10.1016/j.cviu.2013.02.005
[17]
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boixo, S., Brandao, F., Buell, D.A., et al. (2019) Quantum Supremacy Using a Programmable Superconducting Processor. Nature, 574, 505-510.
https://doi.org/10.1038/s41586-019-1666-5
[18]
Boixo, S., Isakov, S.V., Smelyanskiy, V.N., Babbush, R., Ding, N., Jiang, Z., Bremner, M.J., Martinis, J.M. and Neven, H. (2018) Characterizing Quantum Supremacy in Near-Term Devices. Nature Physics, 14, 595-600.
https://doi.org/10.1038/s41567-018-0124-x
[19]
Markov, I.G., Fatima, A., Isakov, S.V. and Boixo, S. (2018) Quantum Supremacy Is Both Closer and Farther than It Appears. arXiv:1807.10749 [quant-ph]
[20]
Gurumoorthy, K.S. and Rangarajan, A. (2012) Distance Transform Gradient Density Estimation Using the Stationary Phase Approximation. SIAM Journal on Mathematical Analysis, 44, 4250-4273. https://doi.org/10.1137/110859336
[21]
Bracewell, R.N. (1999) The Fourier Transform and Its Applications. 3rd Edition, McGraw-Hill, New York.
[22]
Fukunaga, K. and Hostetler, L. (1975) The Estimation of the Gradient of a Density Function with Applications in Pattern Recognition. IEEE Transactions on Information Theory, 21, 32-40. https://doi.org/10.1109/TIT.1975.1055330
[23]
Gurumoorthy, K.S. and Rangarajan, A. (2014) Error Bounds for Gradient Density Estimation Computed from a Finite Sample Set Using the Method of Stationary Phase. arXiv:1404.1147 [stat.CO]
[24]
Scott, D. (1979) On Optimal and Data-Based Histograms. Biometrika, 66, 605-610.
https://doi.org/10.1093/biomet/66.3.605
[25]
Cencov, N.N. (1962) Estimation of an Unknown Distribution Density from Observations. Soviet Mathematics, 3, 1559-1562.
[26]
Wahba, G. (1975) Optimal Convergence Properties of Variable Knot, Kernel, and Orthogonal Series Methods for Density Estimation. Annals of Statistics, 3, 15-29.
https://doi.org/10.1214/aos/1176342997
![\"\"](\"Edit_0e7fb90d-b935-4d60-a558-12f7e0c96476.bmp\")
, obtained via a random variable transformation of a uniformly distributed random variable, is increasingly closely approximated by the normalized power spectrum of ![\"\"](\"Edit_86fea1bb-e25b-4b1d-a70a-40cd0283d614.bmp\")
？as the free parameter ![\"\"](\"Edit_10f58c57-5285-4c19-b125-79cced37fbe0.bmp\")
. The frequencies act as gradient histogram bins. The result is shown using the stationary phase approximation and standard integration techniques and requires proper ordering of limits. We highlight a relationship with the well-known characteristic function approach to density estimation, and detail why our result is distinct from this method. Our framework for computing the joint density of gradients is extremely fast and straightforward to implement requiring a single Fourier transform operation without explicitly computing the gradients.
