Zernike polynomials have been used in different
fields such as optics, astronomy, and digital image analysis for many years. To
form these polynomials, Zernike moments are essential to be determined. One of
the main issues in realizing the moments is using factorial terms in their
equation which causes higher time complexity. As
a solution, several methods have been presented to reduce the time complexity
of these polynomials in recent years. The purpose of this research is to study
several methods among the most popular recursive methods for fast Zernike
computation and compare them together by a
global theoretical evaluation system called worst-case time complexity. In this study, we have analyzed the
selected algorithms and calculated the worst-case time complexity for
each one. After that, the results are represented and explained and finally, a
conclusion has been made by comparing these criteria among the studied algorithms. According to time complexity, we
have observed that although some algorithms such as Wee method and Modified Prata method were successful in having the
smaller time complexities, some other
approaches did not make any significant difference compared to the classical algorithm.
References
[1]
Navarro, R., Arines, J. and Rivera, R. (2009) Direct and Inverse Discrete Zernike Transform. Optics express, 17, 24269-24281. https://doi.org/10.1364/OE.17.024269
[2]
Lane, R. and Tallon, M. (1992) Wave-Front Reconstruction Using a Shack-Hartmann Sensor. Applied Optics, 31, 6902-6908. https://doi.org/10.1364/AO.31.006902
[3]
Hse, H. and Newton, A.R. (2004) Sketched Symbol Recognition Using Zernike Moments. Proceedings of the 17th International Conference on Pattern Recognition, 26-26 August 2004, Cambridge, UK, 367-370. https://doi.org/10.1109/ICPR.2004.1334128
[4]
Kumar, N., Tan, Q.F. and Narayanan, S.S. (2012) Object Classification in Sidescan Sonar Images with Sparse Representation Techniques. IEEE International Conference on Acoustics, Speech and Signal Processing, 25-30 March 2012, Kyoto, Japan, 1333-1336.
[5]
Li, W., Xiao, C. and Liu, Y. (2013) Low-Order Auditory Zernike Moment: A Novel Approach for Robust Music Identification in the Compressed Domain. EURASIP Journal on Advances in Signal Processing, 2013, Article No. 132. https://doi.org/10.1186/1687-6180-2013-132
[6]
Gwo, C. and Deng, A. (2016) Blur Image Edge to Enhance Zernike Moments for Object Recognition. Journal of Computer and Communications, 4, 79-91. https://doi.org/10.4236/jcc.2016.415007
[7]
Vorobyov, M. (2011) Shape Classification Using Zernike Moments. Semantic Scholar, 1-22.
[8]
Sarıyanidi, E., Dağlı, V., Tek, S.C., et al. (2012) Local Zernike Moments: A New Representation for Face Recognition. 19th IEEE International Conference on Image Processing, 30 September-3 October 2012, Orlando, FL, USA, 585-588. https://doi.org/10.1109/ICIP.2012.6466927
[9]
Farokhi, S., Shamsuddin, S.M., Sheikh, U.U., Flusser, J., Khansari, M. and Jafari-Khouzani, K. (2014) Near Infrared Face Recognition by Combining Zernike Moments and Undecimated Discrete Wavelet Transform. Digital Signal Processing, 31, 13-27. https://doi.org/10.1016/j.dsp.2014.04.008
[10]
Iscan, Z., Dokur, Z. and Ölmez, T. (2010) Tumor Detection by Using Zernike Moments on Segmented Magnetic Resonance Brain Images. Expert Systems with Applications, 37, 2540-2549. https://doi.org/10.1016/j.eswa.2009.08.003
[11]
Schwiegerling, J. (1997) Cone Dimensions in Keratoconus Using Zernike Polynomials. Optometry and vision scince, 74, 963-969. https://doi.org/10.1097/00006324-199711000-00029
[12]
Jagerman, L.S. (2007) Ophthalmologists, Meet Zernike and Fourier! Trafford Publishing, Bloomington, Indiana, USA.
[13]
Chong, C.-W., Raveendran, P. and Mukundan, R. (2003) Translation Invariants of Zernike Moments. Pattern Recognition, 36, 1765-1773. https://doi.org/10.1016/S0031-3203(02)00353-9
[14]
Roggemann, M.C. and Welsh, B.M. (2018) Imaging through Turbulence. CRC Press, Boca Raton, Florida, USA.
[15]
Camesasca, F.I. (2007) Refractive Surface Ablation: PRK, LASEK, Epi-LASIK, Custom, PTK, and Retreatment. Slack Incorporated, West Deptford, New Jersey, USA.
[16]
Doyle, K.B., Genberg, V.L. and Michels, G.J. (2002) Integrated Optomechanical Analysis. SPIE Press, Bellingham, Washington, USA. https://doi.org/10.1117/3.460595
[17]
Hampson, K.M. (2008) Adaptive Optics and Vision. Journal of Modern Optics, 55, 3425-3467. https://doi.org/10.1080/09500340802541777
[18]
Díaz, J.A., Fernáandez-Dorado, J., Pizarro, C. and Arasa, J. (2009) Zernike Coefficients for Concentric, Circular Scaled Pupils: An Equivalent Expression. Journal of Modern Optics, 56, 131-137. https://doi.org/10.1080/09500340802531224
[19]
Zhang, A., Rao, C., Zhang, Y. and Jiang, W. (2004) Sampling Error Analysis of Shack-Hartmann Wavefront Sensor with Variable Subaperture Pixels. Journal of Modern Optics, 51, 2267-2278. https://doi.org/10.1080/09500340408232655
[20]
Mas, D., Perez, J., Vazquez, C., Hernandez, C. and Illueca, C. (2003) Near-Field Light Distributions Propagated from Human Corneas: Determination of Relevant Patterns. Journal of Modern Optics, 50, 1335-1352. https://doi.org/10.1080/09500340308235208
[21]
Kintner, E.C. (1976) On the Mathematical Properties of the Zernike Polynomials. Optica Acta, 23, 679-680. https://doi.org/10.1080/713819334
[22]
Prata, A. and Rusch, W. (1989) Algorithm for Computation of Zernike Polynomials Expansion Coefficients. Applied Optics, 28, 749-754. https://doi.org/10.1364/AO.28.000749
[23]
Belkasim, S., Ahmadi, M. and Shridhar, M. (1996) Efficient Algorithm for Fast Computation of Zernike Moments. Journal of the Franklin Institute, 333, 577-581. https://doi.org/10.1016/0016-0032(96)00017-8
[24]
Chong, C.-W., Raveendran, P. and Mukundan, R. (2003) A Comparative Analysis of Algorithms for Fast Computation of Zernike Moments. Pattern Recognition, 36, 731-742. https://doi.org/10.1016/S0031-3203(02)00091-2
[25]
Wee, C.-Y., Paramesran, R. and Takeda, F. (2004) New Computational Methods for Full and Subset Zernike Moments. Information Sciences, 159, 203-220. https://doi.org/10.1016/j.ins.2003.08.006
[26]
Amayeh, G., Erol, A., Bebis, G. and Nicolescu, M. (2005) Accurate and Efficient Computation of High Order Zernike Moments. In: International Symposium on Visual Computing, Springer, Berlin, 462-469. https://doi.org/10.1007/11595755_56
[27]
Singh, C. and Walia, E. (2010) Fast and Numerically Stable Methods for the Computation of Zernike Moments. Pattern Recognition, 43, 2497-2506. https://doi.org/10.1016/j.patcog.2010.02.005
[28]
T'kindt, V. and Billaut, J.-C. (2006) Multicriteria Scheduling: Theory, Models and Algorithms. Springer Science & Business Media, Berlin.
[29]
Neapolitan, R.E., Neapolitan, R. and Naimipour, K. (2010) Foundations of Algorithms. Jones & Bartlett Learning, Burlington, USA.
[30]
Du, D.-Z. and Ko, K.-I. (2011) Theory of Computational Complexity. John Wiley & Sons, USA.
[31]
Goldman, S.A. and Goldman, K.J. (2007) A Practical Guide to Data Structures and Algorithms Using Java. Chapman and Hall/CRC, New York. https://doi.org/10.1201/9781420010336
[32]
Skiena, S.S. (1998) The Algorithm Design Manual: Text. Springer Science & Business Media, Berlin.
[33]
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A. and Protasi, M. (2012) Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer Science & Business Media, Berlin.
[34]
Furia, C.A., Mandrioli, D., Morzenti, A. and Rossi, M. (2010) Modeling Time in Computing: A Taxonomy and a Comparative Survey. ACM Computing Surveys, 42, Article No. 6. https://doi.org/10.1145/1667062.1667063
[35]
Goldreich, O. (2008) Computational Complexity: A Conceptual Perspective. ACM Sigact News, 39, 35-39. https://doi.org/10.1145/1412700.1412710
[36]
Iskander, D.R., Collins, M.J. and Davis, B. (2001) Optimal Modeling of Corneal Surfaces with Zernike Polynomials. IEEE Transactions on Biomedical Engineering, 48, 87-95. https://doi.org/10.1109/10.900255
[37]
Toharia, P., Robles, O.D., Rodríguez, á. and Pastor, L. (2007) A Study of Zernike Invariants for Content-Based Image Retrieval. In: Mery, D. and Rueda, L., Eds., Advances in Image and Video Technology, Springer, Berlin, 944-957. https://doi.org/10.1007/978-3-540-77129-6_79
[38]
Von Zernike, F. (1934) Beugungstheorie des schneidenver-fahrens und seiner verbesserten form, der phasenkontrastmethode. Physica, 1, 689-704. https://doi.org/10.1016/S0031-8914(34)80259-5
[39]
Twa, M.D., Parthasarathy, S., Raasch, T.W. and Bullimore, M. (2003) Decision Tree Classification of Spatial Data Patterns from Videokeratography Using Zernike Polynomials. Proceedings of the 2003 SIAM International Conference on Data Mining (SIAM), San Francisco, CA, USA, 1-3 May 2003, 3-12. https://doi.org/10.1137/1.9781611972733.1
[40]
Lombardo, M. and Lombardo, G. (2010) Wave Aberration of Human Eyes and New Descriptors of Image Optical Quality and Visual Performance. Journal of Cataract & Refractive Surgery, 36, 313-331. https://doi.org/10.1016/j.jcrs.2009.09.026
[41]
Guirao, A., Williams, D.R., et al. (2003) A Method to Predict Refractive Errors from Wave Aberration Data. Optometry and Vision Science, 80, 36-42. https://doi.org/10.1097/00006324-200301000-00006
[42]
Dubinin, A., Cherezova, T., Belyakov, A. and Kudryashov, A. (2008) Human Retina Imaging: Widening of High Resolution Area. Journal of Modern Optics, 55, 671-681. https://doi.org/10.1080/09500340701467710
[43]
Lakshminarayanan, V. and Fleck, A. (2011) Zernike Polynomials: A Guide. Journal of Modern Optics, 58, 545-561. https://doi.org/10.1080/09500340.2011.554896
[44]
He, J.C., Sun, P., Held, R., Thorn, F., Sun, X. and Gwiazda, J.E. (2002) Wavefront Aberrations in Eyes of Emmetropic and Moderately Myopic School Children and Young Adults. Vision Research, 42, 1063-1070. https://doi.org/10.1016/S0042-6989(02)00035-4
[45]
Papakostas, G.A., Boutalis, Y.S., Papaodysseus, C. and Fragoulis, D.K. (2008) Numerical Stability of Fast Computation Algorithms of Zernike Moments. Applied Mathematics and Computation, 195, 326-345. https://doi.org/10.1016/j.amc.2007.04.110
