Physically realizable algorithms for the localization of random pulse-point sources Aleksandr L. Reznik1 , Aleksandr A. Soloviev1 and Andrey V. Torgov1 1 Institute of Automation and Electrometry of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia 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. Keywords Pulsed-point sources, optimal localization algorithms. 1. Introduction 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 effective when there are significant density differences 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 SDM-2021: All-Russian conference, August 24–27, 2021, Novosibirsk, Russia " reznik@iae.nsk.su (A. L. Reznik); soloviev@iae.nsk.su (A. A. Soloviev); torgov@iae.nsk.su (A. V. Torgov) Β© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 252 Aleksandr L. Reznik et al. CEUR Workshop Proceedings 252–259 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). Figure 1: An example of a single-mode stepped distribution density of a random pulse-point source on a search interval. 253 Aleksandr L. Reznik et al. CEUR Workshop Proceedings 252–259 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 single- modality 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 βˆ’ 𝑃1 ) + β„Ž2 𝑃1 𝑑1 = Γ— Γ— ln . (1) πœ† 𝑙1 β„Ž2 254 Aleksandr L. Reznik et al. CEUR Workshop Proceedings 252–259 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 (2) already in the combined segment 𝑑1 = 𝑑1 + 𝑑2 . To formalize the process of reformatting the search algorithm during its transition from the 𝑖-th to the next (𝑖 + 1)-th stage, it is necessary to calculate the auxiliary values (𝑖) β„Ž1 1 𝐾 (𝑖) = (𝑖) (𝑖) (𝑖) (𝑖) = (𝑖) ; (2) (1 βˆ’ 𝑃1 )β„Ž1 + 𝑃1 β„Ž2 (𝑖) (𝑖) β„Ž (1 βˆ’ 𝑃1 ) + 𝑃1 2(𝑖) β„Ž1 (𝑖) β„Ž2 1 π‘˜ (𝑖) = (𝑖) (𝑖) (𝑖) (𝑖) = (𝑖) , (1 βˆ’ 𝑃1 )β„Ž1 + 𝑃1 β„Ž2 (𝑖) β„Ž1 (𝑖) (1 βˆ’ 𝑃1 ) (𝑖) + 𝑃1 β„Ž2 and then, using them, determine the parameters characterizing the changed probability density function 𝑓 (𝑖+1) (π‘₯): 𝑛(𝑖+1) = 𝑛(𝑖) βˆ’ 1; (𝑖+1) (𝑖) (𝑖) (𝑖) 𝑃1 = 𝑃1 π‘˜ (𝑖) + 𝑃2 𝐾 (𝑖) ; (𝑖+1) π‘ƒπ‘š = π‘ƒπ‘š+1 𝐾 (𝑖) , π‘š = 2, 𝑛(𝑖+1) ; (𝑖+1) 𝑑1 (𝑖) = 𝑑1 + 𝑑2 ; (𝑖) 𝑑(𝑖+1) π‘š = π‘‘π‘š+1 , (𝑖) π‘š = 2, 𝑛(𝑖+1) ; (3) (𝑖+1) π‘ƒπ‘š β„Ž(𝑖+1) π‘š = (𝑖+1) , π‘š = 2, 𝑛(𝑖+1) . π‘‘π‘š (𝑖+1) The threshold time 𝑑1 for the maximum duration of the (𝑖 + 1)-th stage is given by the expression (𝑖+1) (𝑖+1) (𝑖+1) (𝑖+1) (𝑖+1) (𝑖+1) (𝑖+1) 1 𝑑1 β„Ž (1 βˆ’ 𝑃1 ) + β„Ž2 𝑃1 1 𝑑1 1 𝑑1 = Γ— (𝑖+1) Γ— ln 1 (𝑖+1) = Γ— (𝑖+1) Γ— ln (𝑖+1) . (4) πœ† 𝑙 β„Ž2 πœ† 𝑙 π‘˜ 1 1 The presence of relations (1)–(4) makes it possible to explicitly represent the total time of localization of the sought source: 𝑛 βˆ‘οΈ ⟨𝜏 ⟩ = 𝑄𝑗 βŸ¨π‘‡π‘— ⟩ β‡’ min . (5) 𝑗=1 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) (2) (π‘—βˆ’1) 1) 𝑇𝑗,1 = 𝑑1 + 𝑑1 + Β· Β· Β· + 𝑑1 β€” the total duration of all stages at which the impulse was not recorded; 255 Aleksandr L. Reznik et al. CEUR Workshop Proceedings 252–259 2) 𝑇𝑗,2 β€” the average time from the beginning of the 𝑗-th stage to the moment of pulse regis- tration; 3) 𝑇𝑗,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- tions (1) and (4): π‘—βˆ’1 (οΈƒ )οΈƒ (π‘š) (1) (2) (π‘—βˆ’1) βˆ‘οΈ 1 𝑑 1 1 𝑇𝑗,1 = 𝑑1 + 𝑑1 + Β· Β· Β· + 𝑑1 = Γ— (π‘š) Γ— ln (π‘š) . πœ† 𝑙 π‘˜ π‘š=1 1 The analytical representation of the component 𝑇𝑗,3 is known [12]: (οΈƒ )οΈƒβˆ’ 1 π‘€π‘œπ‘π‘‘ 1 * (︁ πœ€ )︁ π‘€π‘œπ‘π‘‘ πœ€ 𝑇𝑗,3 = βŸ¨πœπ‘œπ‘π‘‘ ⟩= (𝑗) . πœ† 𝐿 πœ† 𝑗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 βˆ«οΈπ‘‡ 𝑔(𝑑)𝑑𝑑 = 1 βˆ’ exp(βˆ’πœ‡π‘‡ ), 0 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 ⎧ ⎨ πœ‡ exp(βˆ’πœ‡π‘‘) , 0 ≀ 𝑑 ≀ 𝑇; 𝑔𝑇 (𝑑) = 1 βˆ’ exp(βˆ’πœ‡π‘‡ ) 0 𝑑 > 𝑇. ⎩ Therefore, the average time ⟨𝜏 βŸ©π‘‡ will be βˆ«οΈπ‘‡ π‘‘πœ‡ exp(βˆ’πœ‡π‘‘)𝑑𝑑 ∫︁∞ 1 exp(βˆ’πœ‡π‘‡ ) ⟨𝜏 βŸ©π‘‡ = 𝑑𝑔𝑇 (𝑑)𝑑𝑑 = 0 = βˆ’π‘‡ . (6) 1 βˆ’ exp(πœ‡π‘‡ ) πœ‡ 1 βˆ’ exp(βˆ’πœ‡π‘‡ ) 0 256 Aleksandr L. Reznik et al. CEUR Workshop Proceedings 252–259 Taking into account (4), the final expression for the component 𝑇𝑗,2 takes the form (οΈƒ )οΈƒ (𝑗) (𝑗) (𝑗) 1 𝑑1 (𝑗) π‘˜ 1 𝑑1 π‘˜ (𝑗) 1 𝑇𝑗,2 = βˆ’ 𝑑1 = 1βˆ’ ln . (7) πœ† 𝑙(𝑗) 1 βˆ’ π‘˜ (𝑗) πœ† 𝑙(𝑗) 1 βˆ’ π‘˜ (𝑗) π‘˜ (𝑗) 1 1 As a result, the variational problem (5), which determines the optimal strategy for localizing a random pulse-point source with a unimodal stepwise distribution, is reduced to minimizing the expression 𝑛 (οΈƒ π‘—βˆ’1 (οΈƒ )οΈƒ (π‘š) βˆ‘οΈ 𝑄𝑗 βˆ‘οΈ 𝑑1 1 ⟨𝜏 ⟩ = (π‘š) Γ— ln (π‘š) + πœ† 𝑙 π‘˜ 𝑗=1 π‘š=1 1 (οΈƒ (οΈƒ )οΈƒ)οΈƒ )οΈƒ (8) (𝑗) 𝑑1 π‘˜ (𝑗) 1 * (𝑗) + (1 βˆ’ 𝛿𝑗𝑛 ) (𝑗) 1 βˆ’ (𝑗) ln (𝑗) + βŸ¨πœπ‘œπ‘π‘‘ (πœ€/𝑙1 )⟩ β‡’ min 𝑙 1 βˆ’ π‘˜ π‘˜ 1 (𝑗) with respect to the parameters 𝑙1 , 𝑗 = 1, 𝑛 βˆ’ 1. (π‘š) (𝑗) All quantities 𝑄𝑗 , 𝑑1 , π‘˜ (π‘š) included in (8), do not depend on variables 𝑙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 * (πœ€/𝑙(𝑗) )⟩ is determined in a standard way (see [14]). source βŸ¨πœπ‘œπ‘π‘‘ 1 Two small clarifications relate to the specifics of the final, 𝑛-th stage of the search, which may be needed if it is not possible to fix the impulse at any of the 𝑛 βˆ’ 1 initial stages. The first clarification refers to the multiplier (1 βˆ’ 𝛿𝑗𝑛 ), where π‘‘π‘’π‘™π‘‘π‘Žπ‘—π‘› is the Kronecker symbol. 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 11 = 𝑑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 )οΈƒ 𝑛 )οΈƒ 1 βˆ‘οΈ 1 βˆ‘οΈ * (𝑠) ⟨𝜏 ⟩ = (𝑗) 𝐴 (𝑠) + 𝑄𝑠 βŸ¨πœπ‘œπ‘π‘‘ (πœ€/𝑙1 )⟩ β‡’ min . (9) πœ† 𝑙 𝑠=1 1 𝑠=1 The notation is introduced here βŽ› ⎞ 𝑛 (οΈƒ )οΈƒ 1 π‘˜ (𝑠) 1 (𝑠) (𝑠) βˆ‘οΈ (𝑠) 𝐴 = βŽπ‘‘1 ln (𝑠) 𝑄𝑗 ⎠ + 𝑑1 1βˆ’ ln , π‘˜ 𝑗=𝑠+1 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 257 Aleksandr L. Reznik et al. CEUR Workshop Proceedings 252–259 (𝑠) search βŸ¨πœπ‘œπ‘π‘‘ * ⟩ on the required localization accuracy πœ€/𝑙 .Therefore, when solving applied prob- 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. 19- 01-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. 258 Aleksandr L. Reznik et al. CEUR Workshop Proceedings 252–259 [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 algo- rithms 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 discrete- point fields // Optoelectronics, Instrumentation and Data Processing. 2012. Vol. 48. No. 5. P. 506–514. 259