RADIOELECTRONIC AND COMPUTER SYSTEMS

The special class of atomic functions is considered. The atomic function is a solution with compact support of linear differential functional equation with constant coefficients and linear transformations of the argument. The functions considered are used in discrete atomic compression (DAC) of digital images. The algorithm DAC is lossy and provides better compression than JPEG, which is de facto a standard for compression of digital photos, with the same quality of the result. Application of high precision values of atomic functions can improve the efficiency of DAC, as well as provide the development of new technologies for data processing and analysis. This paper aims to develop a low complexity algorithm for computing precise values of the atomic functions considered. Precise values of atomic functions at the point of dense grids are the subject matter of this paper. Formulas of V. O. Rvachev and their generalizations are used. Direct application of them to the computation of atomic functions on dense grids leads to multiple calculations of a great number of similar expressions that should be reduced. In this research, the reduction required is provided. The goal is to develop an algorithm based on V. O. Rvachev’s formulas and their generalizations. The following tasks are solved: to convert these formulas to reduce the number of arithmetic operations and to develop a verification procedure that can be used to check results. In the current research, methods of atomic function theory and dynamic programming algorithms development principles are applied. A numerical scheme for computation of atomic functions at the points of the grid with the step, which is less than each predetermined positive real number, is obtained and a dynamic algorithm based on it is developed. Also, a verification procedure, which is based on the properties of atomic functions, is introduced. The following results are obtained: 1) the algorithm developed provides faster computation than direct application of the corresponding formulas; 2) the algorithm proposed provides precise computation of atomic functions values; 3) procedure of verification has linear complexity in the number of values to be checked. Moreover, the algorithms proposed are implemented using Python programming language and a set of tables of atomic functions values are obtained. Conclusions: results of this research are expected to improve existing data processing technologies based on atomic functions, especially the algorithm DAC, and accelerate the development of new ones.

atomic functions; up-function; dynamic programming; verification; discrete atomic compression

Rvachev, V. L., Rvachev, V. O. Pro odnu finitnu funkciyu [On a finite function]. Proc. Ukr. SSR Acad. Sci, Ser. A., 1971, no. 8, pp. 705-707.

Rvachev, V. A. On approximation by means of the function up(x). Sov. Math. Dokl. 1977, no. 18, pp. 340–342.

Rvachev, V. L., Rvachev, V. A. Neklassicheskie metody teorii priblizhenii v kraevykh zadachakh [Nonclassical methods of approximation theory in boundary value problems]. Kyiv, “Naukova dumka” Publ., 1979. 196 p.

Rvachev, V. A. Compactly supported solutions of functional-differential equations and their applications. Russian Math. Surveys, 1990, vol. 45, no. 1, pp. 87-120.

Gotovac, H., Cvetkovic, V., Andricevic, R. Adaptive Fup multi-resolution approach to flow and advective transport in highly heterogeneous porous media: methodology, accuracy and convergence. Adv. Water Resour., 2009, vol. 32, no. 6, pp. 885-905.

Gotovac, H., Andricevic, R., Gotovac, B. Multi-resolution adaptive modeling of groundwater flow and transport problems. Adv. Water Resour., 2007, vol. 30, vo. 5, pp. 1105-1126.

Brysina, I. V., Makarichev, V. A. Discrete atomic compression of digital images. Radioelectronic and Computer Systems, 2018, vol. 88, no. 4, pp. 17-33. DOI: 10.32620/reks.2018.4.02.

Lukin, V., Brysina, I., Makarichev, V. Discrete Atomic Compression of Digital Images: A Way to Reduce Memory Expenses. In: Integrated Computer Technologies in Mechanical Engineering. Advances in Intelligent Systems and Computing, Springer, Cham, 2020, vol. 1113, pp. 492-502. DOI: 10.1007/978-3-030-37618-5_42.

Makarichev, V., Lukin, V., Brysina, I., Vozel, B., Chehdi, K. Atomic wavelets in lossy and near-lossless image compression. Proc. SPIE 11533, Image and Signal Processing for Remote Sensing XXVI, 2020, vol. 11533. DOI: 10.1117/12.2573970.

Makarichev, V., Lukin, V., Brysina, I. Lossless Discrete Atomic Compression of Full Color Digital Images. Proc. 2021 IEEE 16th International Conference on the Experience of Designing and Application of CAD Systems (CADSM), 2021, pp. 43-46. DOI: 10.1109/CADSM52681.2021.9385239.

Rvachev, V. O., Starets, G. O. Dejaki atomarni funkcii ta jih zastosuvannya [Some atomic functions and their applications]. Proc. Ukr. SSR Acad. Sci, Ser. A., 1983, no. 11, pp. 22-24.

Makarichev, V. A. Approximation of periodic functions by mups(x). Math. Notes, 2013, vol. 93, no. 6, pp. 858-880.

Starets, G. A. Nekotorye svoistva funkcii mupn(x) [Some properties of the function mupn(x)]. Mathematical methods of analysis of dynamic systems, 1983, no. 7, pp. 15-17.

Starets, G. O., Kurpa, L. I. Pro momenty ta znachennia dejakyh atomarnyh funckij [About moments and values of some atomic functions]. Systems of Arms and Military Equipment, 2010, no. 3(23), pp. 162-163.

Starets, G. O., Sidorenko, I. I. Pro atomarni funkcii upm(x) [About atomic functions upm(x)]. Control, Navigation and Communication Systems, 2008, no. 2(6), pp. 175-177.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms: Third Edition, MIT Press, 2009, 1292 p.

Pas, R., Stotzer, E., Terboven, C. Using OpenMP – The Next Step: Affinity, Accelerators, Tasking, and SIMD, MIT Press, 2017, 392 p.

Gropp, W, Lusk, E., Skjellum, A. Using MPI: Portable Parallel Programming with the Message-Passing Interface, MIT Press, 2014, 336 p.

Kharchenko, V., Illiashenko, O, Sklyar, V. Invariant-Based Safety Assessment of FPGA Projects: Conception and Technique. Computers, 2021, vol. 10, no. 10, article id: 125. DOI: 10.3390/computers10100125.

Gregorics, T., Borsi, Z. A unified approach of program verification. Acta Univ. Sapientiae, Informatica, 2017, vol. 9, no. 1, pp. 65-82. DOI: 10.1515/ausi-2017-0005.

Rao, M. V. G., Kumar, P. R., Prasad A. M. Implementation of real time image processing system with FPGA and DSP. Proc. 2016 International Conference on Microelectronics, Computing and Communications (MicroCom), 2016, pp. 1-4.

Li, C., Balla-Arabe, S., Yang, F. Architecture-Aware Optimization Strategies in Real-time Image Processing. Wiley-ISTE Publ., 2017. 177 p.

Pandey, N. K., Diwakar, M. A Review on Cloud based Image Processing Services. Proc. 2020 7th International Conference on Computing for Sustainable Global Development (INDIACom), 2020, pp. 108-112.

Thabet, R., Mahmoudi, R., Bedoui, M. H. Image processing on mobile devices: an overview. Proc. International Image Processing, Applications and Systems Conference, Sfax, Tunisia, 5-7 November 2014, 2014, pp. 1-8.