On the statistics of anomalous clumps in random point images

Abstract

New algorithms for calculating exact analytical formulas describing two related probabilities are proposed, substantiated and software implemented: 1) the probability of the formation of anomalously large local groups in a random point image; 2) the probability of the absence of significant local groupings in a random point image.

Keywords

• eol>Random point image
• computer analysis
• local groupings

1. Introduction

In many scientific and technical disciplines, when solving applied problems related to digital image and signal processing, it becomes necessary to assess the degree of randomness of the analyzed image fragments, depending on the presence or absence of local groupings of point objects on them (as a result, the analyzed fragment significantly difers from ambient background). Such problems arise in many scientific and technical disciplines and can be both purely theoretical [1, 2] and purely applied [3]. For example, the presence of local clumps in processed aerospace images [4, 5] may indicate the presence of latent objects within the analyzed fragment that require more detailed study. In computer processing of biomedical images, one of the most important moments of the preliminary processing stage is the search for abnormal heterogeneities and thickenings, which may be evidence of various diseasecausing abnormalities that require priority attention [6, 7]. In correlation rhythmography, a method is known that makes it possible to construct prognostic assessments of the possibility of restoration of sinus rhythm by a set of intervals on the cardiogram that form an autoregressive cloud (scatterogram) [8, 9].

Mathematically similar problems arise when studying the process of registering random point fields using a scanning aperture with a limited number of threshold levels. When fixing random coordinates of small-sized (ideally, point) objects that form such a field, a failure occurs at the moment when the number of signal point objects located within the scanning aperture exceeds the specified threshold level. It is shown in [ 10] that in cases where the analyzed image is formed by a random Poisson flux of constant intensity, the two-dimensional problem of estimating the probability that the registration process will be carried out without failures is reduced (this is achieved by means of standard factorization) to the following one-dimensional problem:

“It is required to find the probability of the event that if points are randomly dropped on the interval ( 0, 1 ), not a single grouping will be formed, located in a certain subinterval Ω ⊂ ( 0, 1 ), having a length and including more than points”.

When solving applied problems related to the detection of abnormally large clumps in the analyzed images (as, for example, in the above-mentioned problems related to the processing and analysis of aerospace or biomedical images), knowledge of probability formulas ,() is required in which the value of the integer parameter is as close as possible to the value . In such cases, it becomes necessary to know the exact analytical dependencies ,− 1(), ,− 2(), ,− 3(), etc. In particular, the probability ,− 1() corresponds to the fact that if n points are randomly thrown over the interval ( 0, 1 ), all of them will not “merge” into one -grouping, the probability ,− 2() is that no -grouping with a size larger than − 2 will be formed, the probability ,− 3() — that no -groupings larger than − 3 will be formed, etc.

On the other hand, in a number of applied problems, on the contrary, it is required to know the exact analytical relations for the probabilities when the value of the threshold parameter is minimal, i.e. when = 1, 2, 3, etc. Such formulas are needed in cases when, by the nature of the research, it is required to estimate the probability that, within the studied interval, the distribution of random point markers-objects is such that the number of any -group does not exceed the threshold level = 1, 2, 3, etc. The purpose of this work is to propose analytical methods and software algorithms for finding exact probabilistic formulas ,() for both the maximum (that is, as close as possible to ) and the minimum values of the threshold parameter . 2. Obtaining particular solutions to a problem using computer analytics programs The simplicity of the problem posed in the introduction is illusory, and its analytical solution is known only for the simplest case = 1 [11, 12]: ,() = (1 − ( − 1)),

1 0 ≤ ≤ − 1 .

Formula ( 1 ) describes the probability of an event that if points are randomly dropped onto the interval ( 0, 1 ), not a single -group will be formed containing at least 2 points, that all the ejected points will be located between themselves at a distance exceeding . The classical way to obtain solution ( 1 ) is to represent the desired probability in the form of an easily integrable iterated integral [11]: ,1() = !

1 ∫︁ (− 1) ⎧⎪⎨ ∫︁− ⎩⎪(− 2) − 1 . . .

⎧ 4− ⎨ ∫︁ ⎩ 2 3 ⎧ 3− ⎨ ∫︁ ⎩ 2 ⎧ 2− ⎨ ∫︁ ⎩ 0 1 ⎫⎫⎫⎫ ⎬⎬⎬⎬⎪ ⎭⎭⎭⎪⎭ .

( 1 )

Solution ( 1 ) can be obtained in a diferent way. For example, in [ 10], a simple probabilisticgeometric method was proposed that allows one to calculate the probability ( 1 ) without resorting to the procedure of multidimensional integration. Thus, it is not dificult to nfid a solution to the main problem when = 1. But for > 1 the problem becomes much more complicated. Here, our eforts have led to the results that will be given below.

First, note that for arbitrary fixed values of and , the desired solution can be represented in the form of an -fold integral: where the domain of integration ,() is given by the system of linear inequalities 1 . . . ,

( 2 ) < − 1 < < 1, ,() = ! ∫︁

∫︁ · · · ,() ⎧ 0 < 1 < 2 < · · · ⎪ ⎪⎪⎪⎪ +1 − 1 > , ⎨ +2 − 2 > ,

. ⎪⎪⎪ .. ⎪ ⎪⎩ − − > .

To calculate integral ( 2 ), we developed a method of successive dimensionality reduction based on the step-by-step replacement of the initial -fold integral with a set of structurally similar, but having dimension one less than the iterated integrals. Further, formalizing this method and applying cyclic recursion, two systems for analytical calculation of probabilities were designed and implemented as a computer software in order to calculate the desired piecewisepolynomial dependence in the form of functions of the continuous parameter . One system calculates the limits of integration for each of the iterated integrals into which the original -fold integral ( 2 ) decomposes; the second software system is based on multiple diferentiation of the integral ( 2 ) with respect to the parameter . In addition to the two mentioned software systems, a third algorithmic scheme was also developed and implemented as software, using a discrete-combinatorial model to calculate probabilistic formulas ,().

Analytical calculations performed using the listed software systems made it possible to find a complete set of partial formulas ,() in all ranges of variation of the continuous parameter for all values of integer parameters and up to = 14. Note that their calculation is associated with a large amount of routine operations on setting the limits of integration, checking intermediate systems of inequalities for consistency, and performing direct integration in -dimensional space, which is almost impossible to do “manually” even for = 4. Therefore, all the necessary software calculations were carried out using the parallel computing algorithms the use of high-performance computing clusters [13]. 2.1. Algorithms for software and analytical calculation of probabilistic formulas ,() At the next stage, we tried, using the analysis of the obtained partial results, to establish and, if possible, reveal the general laws governing the formation of probability formulas for the case > 1. And several of these analytic patterns were indeed discovered and subsequently rigorously proved. First, for = − 1, a simple dependence was traced and later prove. First, for = − 1, a simple dependence was traced and later proved

,− 1() = 1 − − 1 + ( − 1). (It should be recalled that formula ( 3 ) describes the probability that if points are randomly dropped onto the interval ( 0, 1 ), they will not all “merge” into one compact -grouping.) For = − 2, the relationship ,() is more complex: ,− 2() = ⎧ ⎪⎨ 1 − 22− 2(1 − )2 − 2, ⎪⎩ 1 − 2 + (2 − 1) − 22− 2(1 − )2, 1 0 ≤ ≤ 2 ; 1 2 ≤ ≤ 1.

For = − 3, the dependence ,() becomes so complicated that its reconstruction by analyzing particular software solutions is a completely independent and dificult task: , − 3() = (> 6) ⎧ 1 − 2 + 1(6 − 4− 1) + 2(− 3 + − 2)+ ⎪ ⎪⎪⎨ +3(9 − 18− 1 + 12− 2 − 3− 3), ⎪ 1− 2 + (2− 1) + 1(1− )(− 2− 1 + 2(2− 1)− 1)+ ⎪ ⎪⎩ +2(1− )2(− 2 + (2− 1)− 2) − 33− 3(1− )3, 1 0 ≤ ≤ 2 ; 1 2 ≤ ≤ 1.

Formulas ( 3 )–( 5 ) are confirmed both by software calculations and by direct analytical integration. 2.2. Formulas ,() found using software, analytical and discretecombinatorial algorithms The purpose of developing discrete-combinatorial methods for calculating formulas ,() is that they can be used to try to find a general solution for = 2 by analogy with formula ( 1 ), which is valid for = 1. Unfortunately, this task turned out to be much more dificult than it seemed before the start of the research. This is primarily due to the fact that, in contrast to the case = 1, the probability ,() consists of several piecewise-homogeneous fragments, continuously joined at the points of “connection”. Secondly, the formula itself changes depending on the parity of . Thirdly, finding patterns in each of the parameter ranges variation requires the creation of an individual scheme for transferring each continuous problem corresponding to a given specific range to its own very complex discrete-probabilistic problem.

In our proposed reduction scheme, generalized Catalan numbers appear in all subproblems (i.e., in all ranges of variation of the parameter ). Knowing their explicit form is required when ordering interdependent random number sequences. Most of these probabilistic-combinatorial problems turned out to be more convenient to fomulate and solve in a “word-linguistic” form. In a number of cases, it was possible to use the technique of finding monotonic paths in Weyl chambers [14].

In the case ≥ 2 for the probabilities ,(), we could not find a general compact analytical relation similar to formula ( 1 ) for = 1. However, using all the above computer and discretecombinatorial tools, including software-analytical calculations and generalized Catalan numbers, ( 3 ) ( 4 ) ( 5 ) we have established and then proved a number of particular previously unknown analytical dependencies. In particular, for → 0, an asymptotic formula, common for arbitrary , was established: ,2() = 0 + 2(− + 2)2 + 3(4 − 10)3 + 4(32 − 37 + 86)4+ + 5(− 402 + 394 − 922)5 + 6(− 153 + 6252 − 5171 − 12086)6+ + 7(4203 − 107242 + 79996 − 187002)7+ + 8(1054 − 105703 + 2054992 − 1426841 + 3336406)8+ + 9(50404 − 1557083 + 22676642 − 17317506 + 52315558)9+ + 10(− 9455 + 1890004 − 157946253 + 3896871812 − 3798029823+

For even values of = 2 on the segment 1/ < < 1/( − 1), the previously stated hypothesis formula is rigorously proved

1 2,2() = + 1 2(1 − ( − 1))2.

For even values of = 2 on the segment 1/( + 1) < < 1/, the formula is established 2,2() = 2(1 − ( − 1))2 − 2− 1(1 − ( − 1))2− − 2− 2(1 − )+2(1 − ( − 2))− 2+ + 22− 3(1 − )+3(1 − ( − 2))− 3− − 2− 4(1 − )+4(1 − ( − 2))− 4.

For odd values = 2 + 1 on the segment 1/( + 1) < < 1/, the formula is established 2+1,2() = 2++11(1 − )+1(1 − ( − 1))− − 22++21(1 − )+2(1 − ( − 1))− 1+ + 2++31(1 − )+3(1 − ( − 1))− 2.

3. Conclusion

The results presented in this paper were obtained with the help of specially created instruments of machine analytics, as well as with the use of generalized Catalan numbers, which made it possible to transfer the inherently continuous problem of finding probabilistic formulas to the category of discrete-combinatorial ones. The eficiency of the proposed discrete-combinatorial methods allows us to hope for further progress in solving the described “continuous” problem, up to finding a general analytical formula for arbitrary values of the integer parameters and in all variation ranges of the continuous parameter . The presence of such a generalized analytical solution would provide researchers with an additional tool for assessing whether the analyzed point image is random or regular.

Acknowledgments

This work was supported in part by the Russian Foundation for Basic Research (project No. 1901-00128), and Ministry of Science and Higher Education of the Russian Federation (project No. 121022000116-0).

References

[1] Shannon C.E. A mathematical theory of communication // The Bell System Technical Journal . 1948 . Vol. 27 . Is. 3. P. 379 - 423 .

[2] Gnedenko B.V. , Belyayev Y.K. , Solovyev A.D. Mathematical methods of reliability theory . New York: Academic press, 1969 . 518 p.

[3] Birger I.A . Technical diagnostic. Moscow: Mashinostroenie, 1978 . 240 p. (In Russ .)

[4] Gromilin G.I. , Kosykh V.P. , Popov S.A. , Streltsov V.A. Suppression of the background with drastic brightness jumps in a sequence of images of dynamic small-size objects // Optoelectronics, Instrumentation and Data Processing . 2019 . Vol. 55 . No. 3. P. 213 - 221 .

[5] Reznik A.L. , Tuzikov A.V. , Soloviev A.A. , Torgov A.V. , Kovalev V . A. Time-optimal algorithms focused on the search for random pulsed-point sources // Computer Optics. 2019 . Vol. 43 . No. 4. P. 605 - 610 .

[6] Ablameiko S.V. , Anischenko V.V. , Lapitsky V.A. , Tuzikov A.V. Medical information technologies and systems . Minsk: OIPI NAS Belarus, 2007 . 176 p.

[7] Wójcik W. , Pavlov S. , Kalimoldayev M. Information technology in medical diagnostics . London: CRC Press, 2019 . 336 p.

[8] Poggio T. , Girosi F . Networks for approximation and learning // Proceedings of the IEEE. 1990 . Vol. 78 . P. 1481 - 1497 .

[9] Stinton P. , Tinker I. , Vickery I.C. , Yahe S.P. The scatterogram. A new method for continuous electrocardiographic monitoring // Cardiovascular Research. 1972 . Vol. 6 . P. 598 - 604 .

[10] Reznik A.L. , Efimov V.M. , Solov' ev A.A. , Torgov A.V. Reliability of readout of random point ifelds with a limited number of threshold levels of the scanning aperture // Optoelectronics, Instrumentation and Data Processing . 2014 . Vol. 50 . No. 6. P. 582 - 588 .

[11] Parzen E. Modern probability theory and its applications . New York; London: John Wiley & Sons Inc., 1960 . 464 p.

[12] Wilks S . Mathematical statistics. Princeton: Princeton University Press, 1944 . 284 p.

[13] Reznik A.L. , Tuzikov A.V. , Soloview A.A. , Torgov A.V. Intelligent software support for analysis of random digital images // Computational Technologies. 2018 . Vol. 23 . No. 5. P. 70 - 81 .

[14] Gessel I.M. , Zeilberger D. Random walk in a Weyl chamber // Proceedings of the AMS . 1992 . Vol. 115 . No. 1. P. 27 - 31 .