Computation Cost Reduction for Superposition of One-Dimensional Signal with Gaps by Pyramid Method

Relevance. The article considers the problem of computational cost reduction for signal superposition. It is being solved in various applications, such as delay estimation of the radio and satellite channels, navigation, medicine task, echolocation, measuring devices repeatability. The feature of the researchable task is processing of signals with gaps. If the existing methods are applied to the signal processing, then it leads to time processing increasing or insufficient superposition accuracy. The solution will allow reducing the requirement of calculation equipment (processor) and increasing the decision-making efficiency.  

Purpose of the work. Computational cost reduction by the decreasing of the number hypotheses (offsets) by pyramid representation for signal superposition.

Methods. An optimization method for extremum searching that corresponds to offset base on the pyramid representation, a modified Lucas-Kanade method for additive and multiplicative deviation of the signal.

Results. A metric for comparing the signal with gaps was proposed. The two-stage algorithm was developed. The first stage estimates the offsets with sampling step precision by pyramid representation. The second stage estimates the offset with subsampling precision by the Lucas-Kanade method. Recommendations of the hypotheses number (offsets) for global extremum determination are presented. The developed algorithm in comparison to the current algorithm allows decreasing the processing time by 10 times with similar precision.

The work's scientific novelty is the enhanced method for processing the signal with gaps by pyramid representation.

Practical significance. The result can be used to reduce the computational cost for one-dimensional signal processing. Also it can be used for image superposition with different scale and rotation for real-time machine vision systems.

1. GOST 9238-2013. Construction and rolling stock clearance diagrams. Moscow: Standartinform Publ., 2014. (in Russ.)

2. Myasnikov E.V. Determination of parameters of geometric transformations for combining portrait images. Computer Optics. 2007;31(3):77–82. (in Russ.) EDN:IUDQGV

3. Chkan A.V. Improving Real Performance of RCS when solving digital image processing tasks using fast fourier transform. Izvestiya SFedU. Engineering Sciences. 2020;7(217):152–163. (in Russ.) DOI:10.18522/2311-3103-2020-7-152-163. EDN:VRSEWY

4. Myasnikov V.V., Glumov N.I., Sergeev V.V. Parallel-Recursive Methods of Local Description of Digital Images. Samara: Samara University Publ.; 2023. 100 p. (in Russ.)

5. Kuzmin S.V. Scale-Invariant Delay Estimation Between Two One-Dimensional Digital Signals. Infokommunikacionnye Tehnologii. 2011;9(2):7–10. (in Russ.) EDN:NUMYPF

6. Kuzmin S.V. Normalized Correlation Function for Signal Analysis with Different Sample Rates. Infokommunikacionnye Tehnologii. 2011;9(4):19–23. (in Russ.) EDN:OWQWDH

7. Diyazitdinov R.R. Improving the Lucas-Kanade Algorithm for Combining Digital Video Signals Against the Background of Additive and Multiplicative Interference. Proceedings of the XIth International Conference on Fundamental Problems of Optics – 2019, 21–25 October 2019, St. Petersburg, Russian Federation. St. Petersburg: ITMO University Publ. p.194-196. (in Russ.) EDN:VZGJXY

8. Bessmeltsev V., Bulushev E. Fast Image Registration Algorithm for Automated Inspection of Laser Micromachining. Computer Optics. 2014;38(2):343–350. (in Russ.) DOI:10.18287/0134-2452-2014-38-2-343-350. EDN:SFAZFL

9. Smirnov S.A., Babayan P.V., Ershov M.D., Muraviev V.S. Development and Optimization of Algorithm for Vehicle Tracking on Video Using Lucas-Kanade Method with Pyramids. Proceedings in Cybernetics. 2020;2(38):58–67. (in Russ.) DOI:10.34822/1999-7604-2020-2-58-67. EDN:YNCLHD

10. Gorbachev R.A., Zaripov M.N., Shishkov D.L. An Intelligent System of Technical Vision for Detecting Obstacles and Predicting the Behavior of Moving Objects on Railway Tracks. Izvestiya SFedU. Engineering Sciences. 2022;1(225):256–268. (in Russ.) DOI:10.18522/2311-3103-2022-1-256-268. EDN:VCMTHQ