Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.ssau.ru/files/science/conferences/itnt2015/itnt_2015_26.pdf Дата изменения: Tue Aug 4 10:58:17 2015 Дата индексирования: Mon Apr 11 03:58:23 2016 Кодировка: Поисковые слова: stonehenge

SPECIALIZED COMPUTER SYSTEMS FOR MATHEMATICAL MODELING OF DISCRETE POINT STRUCTURES READOUT PROCESS
Aleksandr Reznik, Andrey Torgov, Aleksandr Soloviev Institute of Automation and Electrometry, Siberian Branch, Russian Academy of Sciences
The paper describes the specialized software systems that have been used to solve difficult mathematical problems in digital images processing. The most important part of the work is the fact that software systems created in his study based on not numerical but analytical transformations. It allowed the researchers eventually obtain new mathematical formulas that are responsible for the reliability of the error-free images reading, and also find the way to their rigorous proof.

Development of scientific and technical applications relating to the different fields of knowledge may lead to the formulation of a simple, but extremely difficult (in terms of solution complexity) combinatorial problems. One such example is the determination of the reliability of digital images reading using multiple-threshold-level integrators. The initial problem is formulated in this way: «L n points x1, x2, ..., xn be randomly dropped on an interval (0,1), ie, there are n independent tests of a random variable uniformly distributed in the interval (0,1). Find the probability n,k of an event that there is no subinterval of length containing more than k ps». The general solution of this problem (in a form of exact analytical formulas responsible for the probability of error-free reading), has not been found up to date. Some relations for the simplest cases only have been published [1], also there are some known asymptotic relations [2]. Because of the difficulties encountered when trying to find exact analytical relations for the probability of error-free discrete fields and digital images reading in the case of multithreshold integrators, we made efforts to find the step-by-step solution of our problem. The first and most important step was to find a wide range of analytical formulas responsible for partial solutions of the problem in special cases. To achieve this goal we have been developed specialized methods based on analytical transformations and used them in the computer software systems programming. All the work was started over 30 years ago [3]. Progress is not standing still, there was a lot of improvements: methods, computers, programming languages. Because of that we created several computation systems (all based on analytical transformations): 1. Systems for the first computers based on FORTRAN. 2. Systems based on Matlab special environment. 3. Modern systems for calculation clusters using C++ for parallel computing. Particular solutions obtained from all developed computer software systems helped us to find and prove new formulas responsible for the probability of error-free discrete random fields and digital images reading. Main result of the work is two new formulas mathematically proven for the problem of the partition of the interval for k = 2. 1. For even n, formula (1) for the interval 1/(n/2)< <1/((n/2)-1 is
( Pn,2 ( ) (2 / n)Cnn / 2)1(1 ((n / 2) 1) )n .

P ( )

(0,1)

(1)

99


2. For odd n, formula (2) for the interval 1/(m+1)<<1/m is

P2

m 1, 2

( ) C

m 1 2 m 1

(1 m )

m 1

(1 (m 1) ) m
m 1

2C C

m 2 2 m 1

(1 m )

m 2

(1 (m 1) )


. (2)

m 3 2 m 1

(1 m )

m3

(1 (m 1) )

m2

The formula (1) was prompted by computer and published in 1981 [3], but we managed to obtain a rigorous proof only in 2011 [4]. The formula (2) was found in 2012, and its proof was a much more complex problem than in case (1). The ideas and methods obtained from the proof of formula (1), have been largely used in the proof of formula (2). A detailed proof of the formula (2) can be found in [4]. The developed software systems created in the work have been used to solve problems related to the discrete random fields and digital images analysis. But they are also capable to solve a variety of complex tasks associated with the analytical multidimensional integral expressions calculation. The work is an example of the successful use of the computer in a role sss, qpp «clever» s rr v transformations.
Bibliography [1] S.Uilks. Mathematical Statistics // Moscow, Mir, 1967, 632 p. [2] Parzen, E., Modern Probability Theory and Its Applications // John Wiley and Sons, Inc., New York London, 1960. [3] Reznik A.L., Computer modeling of continuous readout of random discrete -structural images. Avtometriya, 1981(6), pp 3-6. [4] A.L. Reznik, V. M. Efimov, A. A. Solov'ev, and A. V. Torgov. Errorless Readout of Random Discrete Point Fields // Optoelectronics, Instrumentation and Data Processing, 2012, Vol. 48, No. 5, pp. 506 -514.

100