A Theoretical Comparison among Recursive Algorithms for Fast Computation of Zernike Moments Using the Concept of Time Complexity — Oak Academic Publishing
Research ArticleOpen AccessGoogle Scholar indexed
A Theoretical Comparison among Recursive Algorithms for Fast Computation of Zernike Moments Using the Concept of Time Complexity
School of Advanced Technologies in Medicine, Isfahan University of Medical Sciences, Isfahan, Iran
,
Medical Image and Signal Processing Research Center, Isfahan University of Medical Sciences, Isfahan, Iran
,
Computer Department, Islamic Azad University Najafabad Branch, Isfahan, Iran
,
English Department, Islamic Azad University Najafabad Branch, Isfahan, Iran
1 School of Advanced Technologies in Medicine, Isfahan University of Medical Sciences, Isfahan, Iran
2 Medical Image and Signal Processing Research Center, Isfahan University of Medical Sciences, Isfahan, Iran
3 Computer Department, Islamic Azad University Najafabad Branch, Isfahan, Iran
4 English Department, Islamic Azad University Najafabad Branch, Isfahan, Iran
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 cause s 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 co mplexity. In this study, we have analyzed the selected algorithms and calculate d 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 th ese 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 complexit ies, some other approaches did not make any significant difference compa r ed to the classical algorithm.
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
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
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
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.
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
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
Vorobyov, M. (2011) Shape Classification Using Zernike Moments. Semantic Scholar, 1-22.
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
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
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
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
Jagerman, L.S. (2007) Ophthalmologists, Meet Zernike and Fourier! Trafford Publishing, Bloomington, Indiana, USA.
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
Roggemann, M.C. and Welsh, B.M. (2018) Imaging through Turbulence. CRC Press, Boca Raton, Florida, USA.
Camesasca, F.I. (2007) Refractive Surface Ablation: PRK, LASEK, Epi-LASIK, Custom, PTK, and Retreatment. Slack Incorporated, West Deptford, New Jersey, USA.
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
Hampson, K.M. (2008) Adaptive Optics and Vision. Journal of Modern Optics, 55, 3425-3467. https://doi.org/10.1080/09500340802541777
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
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
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
Kintner, E.C. (1976) On the Mathematical Properties of the Zernike Polynomials. Optica Acta, 23, 679-680. https://doi.org/10.1080/713819334
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
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
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
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
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
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
T'kindt, V. and Billaut, J.-C. (2006) Multicriteria Scheduling: Theory, Models and Algorithms. Springer Science & Business Media, Berlin.
Neapolitan, R.E., Neapolitan, R. and Naimipour, K. (2010) Foundations of Algorithms. Jones & Bartlett Learning, Burlington, USA.
Du, D.-Z. and Ko, K.-I. (2011) Theory of Computational Complexity. John Wiley & Sons, USA.
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
Skiena, S.S. (1998) The Algorithm Design Manual: Text. Springer Science & Business Media, Berlin.
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.
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
Goldreich, O. (2008) Computational Complexity: A Conceptual Perspective. ACM Sigact News, 39, 35-39. https://doi.org/10.1145/1412700.1412710
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
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
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
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
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
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
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
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
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
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