Physically realizable algorithms for the localization of random pulse-point sources

Abstract

In this paper, we describe algorithms for the optimal search for pulsed-point sources, and the information on their distribution is limited to single-mode functions with a stepped probability distribution density, which makes it possible to physically implement the algorithms. In the process of digital registration and subsequent software processing of fast dynamic processes of various physical nature, one of the most laborious and algorithmically complex tasks is the elimination of impulse noise created by point sources with a random spatial distribution. As a rule, the successful solution of such problems requires highly accurate determination of the coordinates of radiation sources, and in most practically important applications this must be done in a minimum (in statistical terms) time. A pulse-point source will be understood below as an object of negligible angular dimensions (mathematical point), which has a random distribution density () over the search interval (0, ) and generates infinitely short pulses (delta functions) at random times. The pauses between pulses have an exponential distribution density () = exp(− ). It is required for the minimum (in statistical terms) average search time to localize the source with accuracy . The search for an object is carried out using a recording device (receiver) with a view window that can be arbitrarily reconfigured in time. The pulse is fixed if the point source at the moment of pulse generation is in the view window of the detector receiver. When registering a pulse, the position of the source on the coordinate axis is refined, so the search interval is narrowed, and the localization procedure is repeated until the next pulse is fixed, etc. Generally speaking, when constructing a time-optimal search algorithm, the opposite situation is also possible, when at certain points in time the current search range does not narrow, but expands. This approach is most efective when there are significant density diferences in the initial (a priori) distribution of the random sought source. The unimodal stepped distribution density considered in this paper meets these requirements. The main

Keywords

• eol>Pulsed-point sources
• optimal localization algorithms

1. Introduction

advantage of single-mode step functions is that their use allows the development of a physically realizable localization algorithm, implemented by a simply connected scanning window of the detector. Another useful property of step functions is that they are a convenient tool for approximating continuous distribution functions; therefore, any progress in the construction of optimal search algorithms for multistage distribution densities of random impulse sources has a direct impact on progress in the construction of optimal search algorithms for continuous distribution densities.

In mathematical terms, the problem of constructing algorithms for the optimal search for random pulse-point objects are in demand in many scientific and technical applications. In particular, such questions are classic in disciplines related to the detection and evaluation of signal objects [1, 2]. In nuclear physics, such problems are encountered when registering elementary particles with cameras that have a “dead time”, during which the counter is “locked” and the registration of particles does not occur [3]. In the problems of technical diagnostics [4], in the mathematical theory of communication [5] and in the theory of reliability [6], such studies are required in the development of methods for eliminating malfunctions manifested in the form of intermittent failures. In astrophysics and cosmology [7, 8], such problems are encountered when searching for bursters — flaring galactic X-ray sources. In modern sections of computer science, these methods are in demand when constructing algorithms for detecting low-contrast and small-sized objects in noisy digital images [9, 10, 11, 12], and, for example, in signal theory, similar problems arise when assessing the reliability of registration of random point fields [13, 14].

2. Formulation of the problem

The problem solved in the present work is the construction of a time-optimal multistage localization algorithm with a given accuracy of a random pulsed-point source having a unimodal stepwise distribution density over the search interval (see Figure 1).

Unimodality in this case means that the initial function () characterizing the density of the probability distribution of the sought source increases monotonically at the initial section, reaching its maximum ℎ1, and then decreases monotonically as well. Compliance with the singlemodality requirement is necessary for the localization algorithm to be physically realizable by continuous movement of the simply-connected scanning window of the detector receiver. Naturally, the containment process should begin with an inspection of the highest step with an area 1 of height ℎ1 and width 1 (1 = ℎ1 * 1).

It is assumed that the detection (inspection) of the highest step will continue for a period of time 1 (its duration needs to be determined) using the 1 — width aperture (this value also needs to be calculated). Since at the initial stage of the search procedure, only one step with the highest probability distribution ℎ2 is examined, in the absence of recorded pulses, a gradual decrease of the value ℎ1 will occur with a simultaneous increase in the height of all other steps ℎ, = 2, of the original distribution density () (that is, the dynamically changing function of time ℎ1() during this period of time will decrease monotonically, while the heights of the remaining steps will increase monotonically).

Calculation of the duration of the time interval after which the search range must be expanded is one of the main parameters of the optimal localization procedure. Generally speaking, in the absence of signal pulses recorded by the detector, the moment of switching the receiver to extended search should be performed at the moment when the decreasing density ℎ1() coincides with the second highest density ℎ2().

In all calculations, it is necessary to correctly take into account that if a pulse is detected by the detector before the time expires, this will mean that the first stage of localization is completed. Further refinement of the coordinates of the source-generator of random pulses (up to the achievement of the required accuracy) should be carried out exclusively within the aperture (within this aperture, the sought pulse object has a uniform distribution). To conduct such a search, one can use the time-optimal multistage procedure for localizing a random uniformly distributed pulsed-point source [12]. 3. Variational problem determining the optimal localization strategy for a single-modal random pulsed-point source The next step in our article is the formulation of a variational problem, the solution of which will fully determine the optimal parameters of a physically realizable procedure for localizing a random pulse-point source with a unimodal distribution. Without loss of generality, we can assume that the function of the a priori density of the probability distribution of the sought source () presented in the Figure 1 is set on the interval ( 0, 1 ), and the required localization accuracy satisfies the condition 0 < < 1 (if these restrictions are not met, the problem is solved by standard normalization of the absolute accuracy to the length of the search interval ). As noted above, the threshold time 1 for performing the first stage of localization, after which the search procedure must proceed to the next stage, is determined from the equality of the densities ℎ1(1) and ℎ2(1):

1 1 1 = × 1 × ln ℎ1(1 − 1) + ℎ21 ℎ2

.

This threshold sets the duration of the inspection-scanning of the highest step ℎ1; at the end of this procedure (and in the absence of registered impulses), the algorithm must be rebuilt to the second stage of localization. At this second stage, the search for the source will be conducted already in the combined segment ( 2 ) = 1 + 2. To formalize the process of reformatting the 1 search algorithm during its transition from the -th to the next ( + 1)-th stage, it is necessary to calculate the auxiliary values () = () = ℎ()

1 (1 − 1())ℎ(1) + 1()ℎ(2) = ℎ()

2 (1 − 1())ℎ(1) + 1()ℎ(2) = 1

() ; (1 − 1()) + 1() ℎ2 ℎ()

1 1

, (1 − 1()) ℎ() ℎ() + 1() 1 2 and then, using them, determine the parameters characterizing the changed probability density function (+1)(): (+1) = () − 1; (+1) = () + (2); 1 1

(+1) ℎ(+1) = (+1) ,

1(+1) = 1()() + 2()();

() (+1) = +1(),

= 2, (+1); () (+1) = +1,

= 2, (+1); = 2, (+1). ( 2 ) ( 3 ) ( 5 )

The threshold time (1+1) for the maximum duration of the ( + 1)-th stage is given by the expression (1+1) = 1 × (+1) 1 1(+1) × ln ℎ(1+1)(1 − 1(+1)) + ℎ(2+1)1(+1) ℎ(2+1)

1 = × 1((1++11)) × ln (1+1) . ( 4 )

The presence of relations ( 1 )–( 4 ) makes it possible to explicitly represent the total time of localization of the sought source:

⟨ ⟩ = ∑︁ ⟨ ⟩ ⇒ min .

=1 1) ,1 = ( 1 ) + ( 2 ) + · · ·

1 1 not recorded; Here is the a priori probability averaged over all possible segments of the location of the sought source that the first pulse fixation will occur at the search stage with a number , ⟨ ⟩ is the total time of the source localization, provided that the first pulse fixation occurs at the stage with a number . In relation ( 5 ), each of the quantities ⟨ ⟩ is divided into three components: + (1− 1) — the total duration of all stages at which the impulse was tration; tions ( 1 ) and ( 4 ): 2) ,2 — the average time from the beginning of the -th stage to the moment of pulse regis3) ,3 — the average duration of the final stage of the search, which is a multi-stage optimal procedure for localizing a random uniformly distributed source.

The component ,1 does not need to be additionally calculated — it is determined by rela,1 = ( 1 ) + ( 12 ) + · · · 1 + (1− 1) = ∑︁ − 1 (︃ 1 =1 × () 1

The analytical representation of the component ,3 is known [12]: ⟨ * ⟩ = ︃( )︃−

1 () 1 .

Thus, it remains to find the component ,2 that describes the time averaged over the ensemble of realizations that elapses from the beginning of the -th stage to the moment of registration of the first pulse, provided that the pulse was reliably detected at this stage. To do this, first consider the following example. Suppose that we know that a random source generates instant pulses, and the intervals between pulses have an exponential distribution density () = exp(− ), i.e. there is a Poisson source with a power . The source is observed over time . It is reliably known that at least one pulse was recorded during this time. The question is: what is the mathematical expectation ⟨ ⟩ of the time elapsed from the beginning of the observation to the registration of the first pulse? Answer: since unconditional probability of registering at least one pulse in the observation interval of duration is the conditional distribution density of the pause from the beginning of observation to the registration of the first pulse will be written in the form

() = 1 − exp(− ), () =

exp(− ) 1 − exp(− ) , 0 ≤ ≤ ;

> . ∫︁ 0 ⎧ ⎨ Therefore, the average time ⟨ ⟩ will be ∞ ∫︁ 0 ⟨ ⟩ = () = 0 = 1 −

exp(− ) 1 − exp(− ) .

( 6 ) Taking into account ( 4 ), the final expression for the component ,2 takes the form ,2 =

1 1 (1) () − () −

1 () )︃

+ 1 () − () ln

1 )︃)︃ () + ⟨ *(/1())⟩

⇒ min )︃ ( 7 ) ( 8 ) ( 9 ) with respect to the parameters (), = 1, − 1.

1 All quantities , (), () included in ( 8 ), do not depend on variables (), = 1, − 1 1 1 and can be calculated in advance; source power and localization accuracy are known; the average execution time of the procedure for the optimal search for a uniformly distributed source ⟨ *(/1

())⟩ is determined in a standard way (see [14]).

Two small clarifications relate to the specifics of the final, ifrst clarification refers to the multiplier ( may be needed if it is not possible to fix the impulse at any of the − -th stage of the search, which 1 initial stages. The The presence of this factor in expression ( 8 ) is explained by the fact that at the -th stage, the procedure for optimal localization of a uniformly distributed signal source is immediately carried out, without carrying out an additional reduced stage, ending with the fixation of the pulse. The second clarification also concerns the final -th stage: since the entire search interval ( 0, 1 ) is detected on it, then formally it should be set 1(1) = () = 1. 1 Before proceeding to finding an analytical solution to the optimization problem ( 8 ), we need to carry out a number of transformations. First, we rewrite relation ( 8 ) in an equivalent form, ordering all terms in accordance with the varied parameters (), = 1, − 1 1 1 − ), where is the Kronecker symbol. ⟨ ⟩ = 1

︃( ⎛ ∑︁ − 1 1 =1 1 () () )︃ =1 + ∑︁ ⟨ *(/1())⟩

⇒ min . )︃ The notation is introduced here () = ⎝(1) ln

1 ()

=+1

⎞ ∑︁ ⎠ + 1 () ︃( 1 − 1 () − () ln

1 )︃ () moreover, all quantities included in () and do not depend on variables (), = 1, − 1 1 and can be calculated in advance. Carrying out a rigorous optimization procedure in relation to expression ( 9 ) is complicated by the complex dependence of the average time of the optimal ().Therefore, when solving applied probsearch ⟨ *⟩ on the required localization accuracy /1 lems in which it becomes necessary to minimize the average time of detection and localization of small-sized pulsed sources, it can be recommended to use an approximation that describes ())⟩ in asymptotics, i.e. with high requirements for localization accuracy: the function ⟨ *(/1 () 1, = 1 × () , = 1, − 1 ( 10 ) minimizing the average localization time ( 9 ). Thus, the variational problem ( 8 ) has been solved: the optimal sizes of the scanning windows are found at each of the − 1 preliminary stages. The optimal threshold scan duration for each of them is determined by the relationship ( 4 ). The search ends with a multistage procedure for the optimal localization of a uniformly distributed random pulse source, which ensures the achievement of the required accuracy .

4. Conclusion

The main feature of the proposed algorithms for the optimal localization of random pulsed-point sources with a multi-stage unimodal probability density distribution over the search interval is that in practical applications they can be physically implemented by moving a connected scanning aperture with a dynamically programmable viewing size.

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] Poor H. An introduction to signal detection and estimation . New York: Springer-Verlag, 1985 . 262 p.

[2] Guimei G. , Xuemei X. , Wenzhe Y. , Quan L. , Guangming S. , Jinjian W. Feature-fused SSD : Fast detection for small objects // Cornell University Library. 2018 . arXiv: 1709 : 05054 . 8 p.

[3] Grupen C. , Buvat I. Handbook of particle detection and imaging . Berlin: Springer, 2011 . 1268 p.

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

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

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

[7] Zhu X. , Wen L. , Hobbs G. et al. Detection and localization of single-source gravitational waves with pulsar timing arrays // Monthly Notices of the Royal Astronomical Society . Oxford Academic Press, 2015 . Vol. 449 . No. 2. P. 1650 - 1663 .

[8] Weinberg S. Cosmology . New York: Oxford University Press, 2008 . 593 p.

[9] 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 .

[10] Klochko V.K. Detection of moving objects by a passive scanning system // Optoelectronics, Instrumentation and Data Processing . 2019 . Vol. 55 . No. 1. P. 59 - 65 .

[11] Reznik A.L. , Solov' ev A.A. , Torgov A.V. Algorithms for optimal localization of a random point-pulse source uniformly distributed over a search interval // Pattern Recognition and Image Analysis . 2018 . Vol. 28 . No. 2. P. 354 -- 361 .

[12] 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 .

[13] Kirichuk V.S. , Mokin K. Yu ., Reznik A.L. Algorithms for processing of series of digital aerospace images based on automatic search for the conjugate points // Pattern Recognition and Image Analysis . 2001 . Vol. 11 . No. 1. P. 192 - 194 .

[14] Reznik A.L. , Efimov V.M. , Solov' ev A.A. , Torgov A.V. Errorless readout of random discretepoint fields // Optoelectronics, Instrumentation and Data Processing . 2012 . Vol. 48 . No. 5. P. 506 - 514 .