СOMPUTATIONAL COMPLEXITY ANALYSIS OF RECURRENT DATA PROCESSING ALGORITHMS IN OPTICAL COHERENCE TOMOGRAPHY

M. A. Volynsky, I. P. Gurov, P. A. Ermolaev, P. S. Skakov


Read the full article 
Article in Русский


Abstract
The paper deals with the basic principles of signals representation in optical coherence tomography with the usage of dynamic systems theory formalism. Computational complexity of algorithms for dynamic estimation of signals parameters is analyzed, such as extended Kalman filter and sequential Monte-Carlo method. It is shown that processing time of one discrete-time sample of the signal by extended Kalman filter increases polynomially with sizes of parameters vector and observation vector. Processing time of one discrete-time sample of the signal by sequential Monte-Carlo method depends linearly both on sizes of parameters vector and observation vector, and on the number of generating random vectors. Experimental results of processing time measurement by each algorithm are described. It is shown that processing time of the signal containing 500 discrete-time samples by extended Kalman filter in the case of the simplest model is approximately equal to 0.1 seconds and increases several times with complication of the model. Processing time of the same signal by sequential Monte-Carlo methods with fixed number of generated random vectors is equal to 0.7 seconds and slightly increases with complication of the model, approximately by 1.5 times. Obtained results may be used for estimation of expected data processing time by recurrent dynamic estimation algorithms in optical coherence tomography systems.

Keywords: optical coherence tomography, interferometric signals processing, computational complexity, extended Kalman filter, sequential Monte-Carlo method

Acknowledgements. Работа выполнена при финансовой поддержке Министерства образования и науки Российской Федерации.

References
 1.     Deck L., de Groot P. High-speed non-contact profiler based on scanning white light interferometry. Applied Optics, 1994, vol. 33, no. 31, pp. 7334–7338.
2.     Gurov I.P. Opticheskaya kogerentnaya tomografiya: printsipy, problemy i perspektivy [Optical coherence tomography: basics, problems and prospects]. In Problemy Kogerentnoi i Nelineinoi Optiki [Problems of Coherence and Nonlinear Optics] / Eds I.P. Gurov, S.A. Kozlov. St. Petersburg, SPbSU ITMO Publ., 2004, pp. 6–30.
3.     Fercher A. Optical coherence tomography. Journal of Biomedical Optics, 1996, vol. 1, no. 2, pp. 157–173.
4.     Volynshy M.A., Vorob'yeva E.A., Gurov I.P., Margaryants N.B. Beskontaktnyi kontrol' mikroob"ektov metodami interferometrii maloi kogerentnosti i opticheskoi kogerentnoi tomografii [Remote testing of microlens with the use of low-coherence interferometry and optical coherence tomography]. Izv. vuzov. Priborostroenie,2011, vol. 54, no. 2, pp. 75–82.
5.     Wyant J.C. Interferometric optical metrology: basic principles and new systems. Laser Focus with Fiveroptic Technology, 1982, vol. 18, no. 5, pp. 65–71.
6.     Alarousu E., Krehut L., Prykari T., Myllyla R. Study on the use of optical coherence tomography in measurements of paper properties. Measurement Science and Technology, 2005, vol. 16, no. 5, pp. 1131–1137. doi: 10.1088/0957-0233/16/5/012
7.     Gurov I., Volynsky M. Interference fringe analysis based on recurrence computational algorithms. Optics and Lasers in Engineering, 2012, vol. 50, no. 4, pp. 514–521. doi: 10.1016/j.optlaseng.2011.07.015
8.     Green D.H., Knuth D.E. Mathematics for the Analysis of Algorithms. 2nd ed. Boston, Basel, Stuttgart: Birkhauser, 1982, 107 p.
9.     Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 2nd ed. Cambridge, MIT Press, 2006, 1312 p.
10.Gurov I., Ermolaeva E., Zakharov A. Analysis of low-coherence interference fringes by the Kalman filtering method. Journal of the Optical Society of America A: Optics and Image Science, and Vision, 2004, vol. 21, no. 2, pp. 242–251. doi: 10.1364/JOSAA.21.000242
11.Kalman R.E. A new approach to linear filtering and prediction problems. Trans. ASME, J. Basic Eng., 1960, vol. 82, pp. 35–45.
12.Simon D. Optimal state estimation: Kalman, H∞, and Nonlinear Approaches. NY, John Wiley & Sons Inc., 2006, 526 p.
13.Simon D. Using nonlinear Kalman filtering to estimate signals. Embedded Systems Design, 2006, vol. 19, no. 7, pp. 38–53.
14.Doucet A., de Freitas N., Gordon N. Sequential Monte Carlo methods in practice. NY, Springer-Verlag, 2001, 583 p.
15.Gordon N.J., Salmond D.J., Smith A.F.M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings Part F: Radar and Signal Processing, 1993, vol. 140, no. 2, pp. 107–113.
16.Ristic B., Arulampalam S., Gordon N. Beyond the Kalman filter: Particle Filters for Tracking Applications. Boston, Artech House, 2004, 318 p.
17.Gilks W., Berzuini C. Following a moving target – Monte Carlo inference for dynamic Bayesian models. Journal of the Royal Statistical Society. Series B: Statistical Maethodology, 2001, vol. 63, no. 1, pp. 127–146.
18.Volynsky M.A., Gurov I.P., Ermolaev P.A., Skakov P.S. Dinamicheskoe otsenivanie parametrov interferometricheskikh signalov na osnove posledovatel'nogo metoda Monte-Karlo [Dynamic parameters estimation of interferometric signals based on sequential Monte Carlo method]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2014, no. 3 (91), pp. 18–23.
19.Ermolaev P.A. Dinamicheskoe otsenivanie parametrov interferometricheskikh signalov metodom rasshirennoi fil'tratsii Kalmana vtorogo poryadka [Dynamic estimation for parameters of interference signals by the second order extended Kalman filtering]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2014, no. 2 (90), pp. 17–22.
20.Gurov I.P., Zakharov A.S., Taratin M.A. Analiz i optimizatsiya vychislitel'nogo protsessa nelineinoi diskretnoi fil'tratsii Kalmana [Analysis and optimization of computational process of the nonlinear discrete Kalman filtration]. Izv. vuzov. Priborostroenie, 2004, vol. 47, no. 8, pp. 42–48.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2019 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.

Яндекс.Метрика