Search

Motion estimation plays a crucial role in video coding; the Adaptive Rood Pattern Search (ARPS) algorithm is a well known fast motion estimation algorithm. However, ARPS has certain limitations, such as the lack of an accurate starting motion vector, a fixed Zero Motion Prejudgment (ZMP) threshold unsuitable for fast motion video sequences, and the repetitive use of a Unit Rood Pattern (URP) resulting in increased computational complexity. To address these issues, this paper proposes a novel algorithm called Efficient Adaptive Rood Pattern Search (EARPS). EARPS overcomes these limitations by employing the Full Search algorithm to obtain optimal motion vectors for the first column in each frame, adopting a dynamic ZMP threshold that adapts to varying motion speeds in video sequences and utilizing URP only once to reduce computational overhead. The performance of the new proposed EARPS algorithm is evaluated and compared with that of ARPS algorithm using various video sequences with different motion speeds. The number of searching points and Peak Signal-to-Noise Ratio (PSNR) are used to quantify computing complexity and accuracy. The experimental findings show that EARPS surpasses ARPS in terms of computing complexity while retaining a decent degree of PSNR accuracy. The proposed EARPS motion estimation algorithm main contribution is to achieve high speed with reasonable accuracy, regardless of the type of motion speed in the video frames. The EARPS algorithm offers a substantial advancement over ARPS, delivering a more efficient motion estimation method with broader applicability in video processing. It represents a significant contribution to the development of effective motion estimation algorithms.

The fast increase of the amount of quantitative and qualitative characteristics of digital visual data calls for the improvement of the performance of modern image processing devices. This article proposes new algorithms for 2D digital image processing based on the Winograd method in a general form. An analysis of the obtained results showed that the use of the Winograd method reduces the computational complexity of image processing by up to 84% compared to the traditional direct digital filtering method depending on the filter parameters and image fragments, while not affecting the quality of image processing. The resulting Winograd method transformation matrices and the algorithms developed can be used in image processing systems to improve the performance of the modern microelectronic devices that carry out image denoising, compression, and pattern recognition. Research directions that show promise for further research include hardware implementation on a field-programmable gate array and application-specific integrated circuit, development of algorithms for digital image processing based on the Winograd method in a general form for a 1D wavelet filter bank and for stride convolution used in convolutional neural networks.

Mobile robots with complex onboard equipment are investigated in this article. It is shown that their onboard equipment, for providing the required reliability parameters, must have fault-tolerant properties. For designing such equipment it is necessary to have an adequate model of reliability parameters evaluation. The approach, linked to the creation of the model, based on parallel semi-Markov process apparatus, is considered. At the first stage of modeling, the lifetime of the single block in a complex fault-recovery cycle is determined. Dependences for the calculation of time intervals and probabilities of wandering through ordinary semi-Markov processes for a common case are obtained. At the second stage, ordinary processes are included in the parallel one, which simulates the lifetime of the equipment lifetime as a whole. To simplify calculations, a digital model of faults with the use of the procedure of histogram sampling is proposed. It is shown that the number of samples permits to control both the accuracy and the computational complexity of the procedure for calculating the reliability parameters.

The purpose of the work is to determine the relationship between the computational complexity of controlling a swarm of particles and the available computational resources for choosing the optimal control strategy. We find formulas for the relationship between the available computational complexity, the number of clusters in the swarm, the number of interacting players, and the depth of calculations to search the suboptimal control. Methods. To find the optimal control, the method of maximizing the target objective function is used. The computational complexity of the objective function is determined for suboptimal control on the grid for the maximum number of particle swarms and the minimum of the grid size. To study the swarm dynamics in the configuration space we investigate the properties of the convex hull of the swarm using elements of the particle diffusion theory. Results. The objective function of controlling a swarm of particles in the conditions of interaction with stationary objects and in the presence of competitive swarms is constructed. It is shown that the swarm of particles spread in the configuration space due to instability and mixing in the general situation. Formulas for the maximum possible size of clusters and the number of particles in clusters, the depth of calculation of control steps and the detail of the grid are obtained. The connection between the dynamics of the swarm of controlled particles and the theory of Smolukhowski’s coagulation in colloidal solutions is shown. Conclusion. Constraints on the computational complexity of the control lead to a restriction on the size of the iteration grid for finding the minimax and to a restriction on the number of swarm clusters for which the optimal strategy can be chosen. The clustering capability of the swarm leads to the fact that the product of the number of positions in the grid in the optimization of the number of clusters in a swarm depth calculation steps should be no more than the order of the logarithm of acceptable computational complexity.

The paper investigates the problems of reduction (decomposition) of multidimensional data models in the form of hypercube OLAP structures. OLAP data processing does not allow changes in the dimension of space. With the increase in data volumes, the productivity of computing cubic structures decreases. Methods for reducing large data cubes to sub-cubes with smaller volumes can solve the problem of reducing computing performance.The reduction problems are considered for cases when the cube lattice has already determined criteria aggregation, and the cube decomposition into smaller cubes is needed to reduce the computation time of the full lattice when dynamically changing data in the cube.The objective of the paper is to find conditions for reducing the computational complexity of solving data analysis problems by reduction methods, to obtain exact quantitative boundaries for reducing the complexity of decomposition methods from the class of polynomial degrees of complexity, to establish the nature of the dependence of computational performance on the structural properties of a hypercube, and to determine the quantitative boundaries of computational performance for solving decomposition problems of data aggregation .The study of the computational complexity of decomposition methods for the analysis of multidimensional hyper-cubes of polynomial-logarithmic and polynomial degrees of complexity is carried out. An exact upper limit is found for reducing the complexity of decomposition methods for analyzing the initial OLAP - data hypercube with respect to non-decomposition ones and based on them criteria are proved for the effective application of reduction methods for analyzing hypercube structures in comparison with traditional non-reduction methods.Examples of decomposition methods of cube structures are presented, both reducing and increasing computational complexity in comparison with calculations using the full model.The results obtained can be used in processing and analysis of information arrays of hypercube structures of analytical OLAP-systems belonging to the BigData class, or ultra-large computer multidimensional data systems.

The subject of research in the article are algorithms for fast calculation of autoregression coefficients in digital spectral analysis and estimation of the number of arithmetic operations required for their implementation. The aim of the article – comparative analysis of the speed of different algorithms for calculating the coefficients of autoregression as part of the algorithms of spectral analysis, including analysis of the complexity of their microcontroller implementation. Tasks to be solved: selection of spectral analysis methods suitable for diagnostics of technological equipment, analysis of methods for calculating autoregression coefficients and derivation of relations for estimating software complexity of algorithms and calculation of numerical estimates of addition and multiplication for some algorithms, adaptation of developed methods and estimates to microcontrollers. spectrum Applied methods: algorithm theory, Fourier transform, natural series, microcontroller programming. The results obtained: it is shown that spectral estimation methods based on Yul-Walker equations, which require the calculation of autoaggression coefficients, combine sufficient resolution and resistance to interference with acceptable implementation complexity. Estimates of the number of additions and multiplications for the Levinson, Durbin, and Trench algorithms are obtained, and their comparative analysis is performed. The calculation times for microcontroller arithmetic with fixed and floating points were count upon. Conclusions: When constructing spectrum analyzers for the diagnosis of technological equipment, it is advisable to use the Yul-Walker method. A comparison of Levinson, Durbin, and Trench algorithms for calculating autoregression coefficients showed that the Trench method requires a minimum number of additions, and the Durbin method requires a minimum number of multiplications. At microcontroller realization of spectrum analyzers, it is necessary to consider features of the arithmetic used by the controller. The Trench method is the fastest in the case of floating-point arithmetic and small-scale modeling. In other cases, Durbin's method is more effective.

An approach enabling partial generalization of the Green–Sasao hierarchy for polynomial forms of Boolean functions to the case of an arbitrary finite field was introduced. The exact value of the Shannon function was obtained for the class of pseudo-Kroneker and free-Kronecker forms of n-ary functions over an arbitrary finite field Fq. The value found is equal to qn−1. The previously known result for Boolean functions was generalized.

Subject of Research. The paper presents encoding and decoding method for video information obtained from video surveillance cameras in transport. The method is based on the usage of adaptive three-dimensional discrete cosine transform. Video compression typically has two goals: to reduce spatial redundancy between image elements and temporal redundancy between successive frames. The basic principle of spatial encoding is the consideration of the correlation of the adjacent pixel brightnesses, and the basic principle of interframe encoding is prognosis and motion compensation for the interpolated sample positions in the reference frame in all known standard video codecs such as H. 26х and MPEG-x. Method. The method is characterized by applying an adaptive cosine transform in the signal space and with respect to time, and the sizes of the cubes are unspecified depending on spartial and time statistical characteristics of the image signal. Main Results. The results show that the proposed algorithm can improve the encoding and decoding efficiency of images taking into account the specifics of the transport images. The best performance is achieved at low and medium traffic intensity. At the same time, the algorithm computational complexity is reduced by 4-5 times while maintaining the quality of the restored video streams in comparison with codec standards. Practical Relevance. The proposed algorithms based on adaptive cosine transform give the possibility: firstly, to decrease the transmission rate of the transport sequences by 2–2.5 times compared to the classical cosine transform with the size of cubes equal to (8 × 8 × 8); secondly, to reduce significantly computational costs in the implementation of transport video surveillance systems in real time compared to standard codecs. The results of the work can be recommended to specialists in the field of video information encoding and decoding to provide the necessary transmission speed at a given distortion level.

A problem to describe the complexity class BPP in terms of a logical language is considered. BPP (abbreviation for bounded-error probablistic polynomial time) represents the class of computational decision problems that are efficiently solvable in polynomial time. The class BPP has an important practical significance since as it includes the largest spectrum of applied problems. At the same time till now, it was supposed that BPP cannot be characterized because of semantic constraints imposed on Turing machines recognizing languages in BPP. Using a new method of characteristical sets we are the first to provide a logical characterization of the class BPP as a decidable fragment of the second-order logic.

The paper presents an obfuscation problem, in which indistinguishability is considered relatively to programs with distinguishable functionality. The functionality remains undisclosed owing to unknown parameters in the program’s input. An attacker that can run only polynomial time algorithms will not be able to distinguish the program’s functionality without having the input key. Thus, it was named a key obfuscator. The article sets a problem of creating key obfuscators and efficient algorithms for their operation. The obfuscator’s general scheme of operation for logic schemes of any functionality is presented. Proof of a theorem is provided, which states that the obfuscator presented is a key obfuscator. The possibility of finding key obfuscator’s efficient operation algorithms for specific applications is established. Key-based obfuscation enables finding solutions for tasks such as open storage and execution of a program code in an untrusted computational environment and makes it more difficult to carry out injection attacks and analysis of distributed computing. Authentication and confirmation of rights for using software can be another application of key obfuscation, because without the key program code is useless.

The problems of synthesis of the efficient algorithms for digital processing of discrete signals require transforming the signal spectra from one basis system into other. The rational solution to this problem is to construct the Fourier kernel, which is a spectrum of some basis functions, according to the system of functions of the other basis. However, Fourier kernel properties are not equally studied and described for all basis systems of practical importance. The article sets a task and presents an original way to solve the problem of mutual transformation of trigonometric Fourier spectrum into Walsh spectrum of different basis systems.The relevance of this theoretical and applied problem is stipulated, on the one hand, by the prevalence of trigonometric Fourier basis for harmonic representation of digital signals, and, on the other hand, by the fact that Walsh basis systems allow us to have efficient algorithms to simulate signals. The problem solution is achieved through building the Fourier kernel of a special structure that allows us to establish independent groups of Fourier and Walsh spectrum coefficients for further reducing the computational complexity of the transform algorithms.The article analyzes the properties of the system of trigonometric Fourier functions and shows its completeness. Considers the Walsh function basis systems in three versions, namely those of Hadamard, Paley, and Hartmut giving different ordering and analytical descriptions of the functions that make up the basis. Proves a completeness of these systems.Sequentially, for each of the three Walsh systems the analytical curves for the Fourier kernel components are obtained, and Fourier kernel themselves are built with binary rational number of samples of basis functions. The kernels are presented in matrix form and, as an example, recorded for a particular value of the discrete interval of N, equal to 8. The analysis spectral coefficients of the Fourier kernel components, allowed us to combine the nonzero coefficients in independent groups in each of the three cases of transformations. The original rules for group formation are formulated both for particular value of N, and in general terms.The formation rules of groups, group-by-group and common Parseval equalities were used to obtain descriptions of algorithms for mutual transformation of trigonometric Fourier spectrum into Hadamard, Paley and Hartmut spectra. An analytical record of these algorithms enables speaking of the Fourier kernels as of the new operators of spectra transformation. The computational complexity evaluation of operators showed the effectiveness of their use owing to more than three times reduction of the number of arithmetic operations as compared to the conventional method, i.e. direct calculation of the Walsh spectra. Because of this property the proposed operators become useful when solving the tasks of real-time discrete systems modeling.In the long run, there is a plan to solve a similar task for the mutual transformation of Walsh and Hartley spectra: both a Hartley basis system and a trigonometric system reflect the frequency structure of the signal that serves a useful purpose in terms of theory and practice.

An improved algorithm for the synthesis of the secondary structure of algebraic Bayesian networks represented by a minimal join graph is proposed in the paper. The algorithm differs from the previously offered one so that it relies on the incremental principle, uses specially selected edges and, finally, eliminates redundant edges by a greedy algorithm. The correct operation of the incremental algorithm is mathematically proved. Comparison of the computational complexity of the new (incremental) algorithm implementation and two well-known (greedy and direct) is made by means of statistical estimates of complexity, based on the sample values of the runtime ratio of software implementations of two compared algorithms. Theoretical complexity estimates of the greedy and direct algorithms have been obtained earlier, but are not suitable for comparative analysis, as they are based on the hidden characteristics of the secondary structure, which can be calculated only when it is built. To minimize the influence of random factors at calculating the ratio average program runtime is used obtained by N launches on the same set of workloads. The sample values of ratio is formed for M sets of equal power K. According to the sample values the median is calculated, as well as the other statistics that characterize the spread: borders of the 97% confidence interval along with the first and the third quartiles. Sets of loads are stochastically generated according to the specified parameters using the algorithm described in the paper. The stochastic algorithms generating a set of loads with given power, as well as collecting the statistical data and calculating of statistical estimates of the ratio of forward and greedy algorithm to the incremental algorithm runtimes is described in the paper. A series of experiments is carried out in which N is changed in the range 1, 2 ... 9, 10, 26, 42 ... 170.They have showed that the incremental algorithm speed exceeds the forward and greedy ones, moreover in the 10-170 load sets power range this finding is statistically significant (97% level). The results of experiments are visualized using a graphs library Highcharts. The developed incremental algorithm is designed for application in problems solving of algebraic Bayesian networks machine learning.

Complex system engineering based on the automaton models requires a reasoned data structure selection to implement them. The problem of automaton representation and data structure selection to be used in it has been understudied. Arbitrary data structure selection for automaton model software implementation leads to unnecessary computational burden and reduces the developed system efficiency. This article proposes an approach to the reasoned selection of data structures to represent finite algoristic automaton basic models and gives practical considerations based on it.Static and dynamic data structures are proposed for three main ways to assign Mealy and Moore automatons: a transition table, a matrix of coupling and a transition graph. A thirddimensional array, a rectangular matrix and a matrix of lists are the static structures. Dynamic structures are list-oriented structures: two-level and three-level Ayliff vectors and a multi-linked list. These structures allow us to store all required information about finite state automaton model components - characteristic set cardinalities and data of transition and output functions.A criterion system is proposed for data structure comparative evaluation in virtue of algorithmic features of automata theory problems. The criteria focused on capacitive and time computational complexity of operations performed in tasks such as equivalent automaton conversions, proving of automaton equivalence and isomorphism, and automaton minimization.A data structure comparative analysis based on the criterion system has done for both static and dynamic type. The analysis showed advantages of the third-dimensional array, matrix and two-level Ayliff vector. These are structures that assign automaton by transition table. For these structures an experiment was done to measure the execution time of automation operations included in criterion system.The analysis of experiment results showed that a dynamic structure - two-level Ayliff vector - is more beneficial for an increasing task dimension. Static structures such us the thirddimensional array and matrix should be preferred to represent only automaton with small component set cardinalities.The article results may find application in software system development using the automata theory when a memory and time consumption minimization of finite state automaton model processing is required. In prospect, it is necessary to work at an optimization of data structures representing the finite state automaton basic models and algorithms to solve problems with their use. Other models that have a practical application are also of interest, for example, nondeterministic automatons. It is advisable to explore machine implementation aspects of such models in terms of computational complexity of applied algorithms.

The object of study of this paper is to define accurate methods for solving combinatorial optimization problems of structural synthesis. The aim of the work is to systemize the exact methods of discrete optimization and define their applicability to solve practical problems.The article presents the analysis, generalization and systematization of classical methods and algorithms described in the educational and scientific literature.As a result of research a systematic presentation of combinatorial methods for discrete optimization described in various sources is given, their capabilities are described and properties of the tasks to be solved using the appropriate methods are specified.

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.

Digital signature schemes can fulfill an actual task of ensuring fairness and transparency of electronic election. However, existing standards and protocols need modification into blind signature and additional security check by the anonymity criterion. The author examines blind signature protocol provided by Russian scientists. It is proposed to improve scheme's efficiency by changing inner mathematics. Elliptic curves over vector finite field enable parallel processing in group operation and reduce integer range. These advantages are illustrated by computational example. Also, improved protocol investigation by the anonymity criterion is provided in the article. The author proves that mathematics change do not affect protocol security. [ABSTRACT FROM AUTHOR]

The present paper offers a modified procedure for learning Bayesian network in terms of the statistical data. Moreover, the introduced recursive formulas enable the computational process optimization, and the implemented algorithm of heuristic search for discovering BN structure allows avoiding dependence of vertices from their initial ordering. [ABSTRACT FROM AUTHOR]