=Paper=
{{Paper
|id=Vol-3006/30_short_paper
|storemode=property
|title=Physically realizable algorithms for the localization of random pulse-point sources
|pdfUrl=https://ceur-ws.org/Vol-3006/30_short_paper.pdf
|volume=Vol-3006
|authors=Aleksandr L. Reznik,Aleksandr A. Soloviev,Andrey V. Torgov
}}
==Physically realizable algorithms for the localization of random pulse-point sources==
https://ceur-ws.org/Vol-3006/30_short_paper.pdf
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