An analytical and probabilistic model with concordance for detecting mine-like objects with mirror symmetry

Abstract

Purpose

The purpose is to develop search and detection strategies that maximize the probability of detection of mine-like objects.

Design/methodology/approach

The author have developed a methodology that incorporates variational calculus, number theory and algebra to derive a globally optimal strategy that maximizes the expected probability of detection.

Findings

The author found a set of look angles that globally maximize the probability of detection for a general class of mirror symmetric targets.

Research limitations/implications

The optimal strategies only maximize the probability of detection and not the probability of identification.

Practical implications

In the context of a search and detection operation, there is only a limited time to find the target before life is lost; hence, improving the chance of detection will in real terms be translated into the difference between success or failure, life or death. This rich field of study can be applied to mine countermeasure operations to make sure that the areas of operations are free of mines so that naval operations can be conducted safely.

Originality/value

There are two novel elements in this paper. First, the author determine the set of globally optimal look angles that maximize the probability of detection. Second, the author introduce the phenomenon of concordance between sensor images.

Citation

Nguyen, P.B.U. (2022), "An analytical and probabilistic model with concordance for detecting mine-like objects with mirror symmetry", Journal of Defense Analytics and Logistics, Vol. 5 No. 2, pp. 152-178. https://doi.org/10.1108/JDAL-02-2021-0002

1. Introduction

The aim of a search and detection mission is to detect a target, be it a human body, an aircraft, a mine or a ship. One technique for detecting a target is analyzing sensor images and their characteristics, such as a target's shadow, highlight, orientation, size, contrast, etc. This paper focuses on mathematical modeling inspired by underwater mine detections. In a mathematical sense, the aim of a search and detection mission is to maximize the probability of detection. Given a sensor and a target, we develop a strategy that maximizes the probability of detection. This goal can be achieved by observing a target from a sequence of optimal angles. However, the use of aspect angles is often overlooked in traditional search theories. Indeed, the law of random search (Koopman, 1999) is widely used, yet it assumes no angular dependencies. Likewise, Washburn (2002) does not generally consider angular features. Recently, Onggo and Karatas (2016) described a number of maritime search operations for stationary and moving targets, but they did not consider angular constraints.

Both experimental and theoretical research studies have demonstrated that the probability of detection can be significantly increased by observing a target from more than one angle. Indeed, target saliency depends on its aspect angle. Fixed sensor arrays deployed for target localization and tracking benefit from multi-aspect observations (Ash and Moses, 2008; Bishop et al., 2010; Martinez and Bullo, 2006). The observation of targets in mine-hunting operations using different looks (by which, we mean different angles) is associated with significant improvement in their detection. Even greater improvement is evident when multiple looks are carried out in an optimal manner (Fawcett et al., 2008; Ji and Liao, 2005; Johns Hopkins Applied Physics Laboratory, 2019; Nguyen and Hopkin, 2005; Nguyen et al., 2008, 2014; Runkle et al., 1999; Wettergren and Baylog, 2010; Williams and Hunter, 2015; Zerr et al., 2000).

In the realm of automatic target recognition using synthetic aperture radar images, many recent papers describe how to improve the performance of target recognition using multiple looks (Ding and Wen, 2017; Huan and Pan, 2013; Laubie et al., 2015, 2018; Salvador, 2016; Situ et al., 2016; Zhang et al., 2012). Earlier research (Bhanu and Jones, 2002; Brown, 2003; Jin et al., 2006; Laine and Bauer, 2008; Ruohong et al., 2010; Snyder and Ettinger, 2003; Vespe et al., 2005). This research shows that the performance of target recognition can be significantly improved through the data fusion of observations at different looks (referred to as aspect diversity). One feature shared by previous papers on automatic target recognition is the detailed analysis of the images of realistic targets. By contrast, we provide an analytical model for a general class of mine-like and symmetrical targets, emphasizing the phenomenon of concordance.

Determining the globally optimal angles is not a simple feat. The complexities associated with the computation are nonlinear, multidimensional (each independent look is considered a separate dimension) and, in brief, NP-hard (Törns and Žilinska, 2007). Even when the number of looks is few and the single look probability of detection is simple, the explicit probability of detection for n looks can be hopelessly complicated. Numerical solution (Press et al., 1992) is not an option, as it requires a huge number of calculations for each new scenario. Furthermore, the solution space has many local optima.

Therefore, the problem requires a different approach that is not numerical. We have found a methodology that incorporates variational calculus, number theory and algebra to derive a globally optimal strategy that maximizes the expected probability of detection. This globally optimal solution holds for a large class of targets that exhibit mirror symmetry. The solution consists of simple angles that are intuitive and have analytical expressions. This simplifies the task of planning and executing a search and detection mission.

Our methodology makes use of the symmetry of the problem and several reasonable criteria, such as the periodicity of the single look probability of detection. These criteria apply generally to a target whose shape can be approximated as an ellipsoid.

We will provide a rigorous proof to show that the solution is globally optimal, avoiding the false conclusions based on symmetry that have been made in the past (Waterhouse, 1983; Bouniakovsky, 1854). The concept of symmetry has been used fruitfully many times in history. It is commonly known that the laws of physics obey symmetries, such as Lorentz symmetry (French, 2009) and gauge symmetry (Ryder, 1988). In engineering, symmetry has also played a significant role. For example, symmetry is used in three dimension alignment (Chaouch and Verroust-Blondet, 2009), in shape matching (Kazhdan et al., 2004), etc.

We describe the modelling assumptions in Section 2. We determine all the local optima (the set of all critical points) to the expected probability of detection in Section 3. In Section 4, we prove the global optimality of the equidistant angles (to be defined later). Section 5 contains examples based on a nontrivial single look probability of detection. We conclude in Section 6.

2. Modelling assumptions

Here, we assume a large class of targets that has mirror symmetry, such as a cylinder or an ellipsoid. Most manmade targets (e.g. a ship hull, a mine, etc.) have this symmetry. We focus on one aspect of target detection: the look angle, for depending on the relative orientation of the sensor and the target, the sensor picture will look different at different look angles. In underwater mine-hunting operations, the analysis of other characteristics, such as the highlight and the size of the target, also contributes to the overall probability of detection. We believe that observation of these characteristics will also be improved with our search strategy based on look angles, e.g. highlights change with look angles and different highlights add more information. Analysis of these characteristics is a topic for future research.

There are two novel elements in our model. First, we determine the set of globally optimal look angles that maximizes the probability of detection. Second, we introduce the phenomenon of concordance between sensor images.

Figure 1 shows an example of an underwater mine known as a Manta. Figure 2 shows two sonar pictures of a mine on a relatively benign seabed: one taken at 85° (left) and the other at 0° (right). Some of the sonar images were collected by an Autonomous Underwater Vehicle Trial equipped with a side-scan sonar at Loch Earn, Scotland in November 2010. Machine learning algorithms have been developed and tested against sonar imagery data (Wang et al., 2014; Shao and Japkowicz, 2014). While the algorithms discover the optimal angles, this is not the same as an analytical solution, as presented here. The premise of our assumption is that the detection probability is maximal if a target is viewed from its broad side, and it gradually degrades and reaches a minimum if a target is viewed from its short side.

We make the following assumptions:

1. Pictures are captured at the same range;

2. The detection probability for one look is maximal when a target is viewed at its broad side;

3. The detection probability for one look decreases monotonically as the look angle moves away from the broad side view;

4. The shadow of a target is a semicircle;

5. The detection probability for one look is quantitatively proportional to the normalized and observed cross-section of the target (Nguyen and Mirshak, 2016);

6. The detection probability for one look is further compounded by θ/π where θ is the angle that subtends the shadow of the target as shown in Figure 3;

7. The detection probability for one look is periodic with a period equal to π  due to the symmetry of the target;

8. To illustrate, we assume that the detection probability for one look at the look angle x and the subtended angle θ is equal to g¯(x, θ)=(θ/π)⋅(1−g(x)) where g(x)=sin(x)2 is shown in Figure 4 (this corresponds approximately to the normalized cross section of an ellipsoid). Note that this probability of detection is not equal to the area size of the shadow of a target. We interpret θ/π as the normalized angle of the circular sector, and (1−g(x)) is the diameter of the circular sector. By definition, 0≤(1−g(x))≤1 is the normalized cross-section of a target. That is, the diameter of the circular sector is less than or equal to one. In reality, g(x) depends on the kind of target that we are looking for. Since we aim to maximize the expected detection probability, which is an average, the details in g(x) are not expected to vary the expected value substantially if 1−g(x) is a good representation of the cross-section of the target.

9. This means that the detection probability for one look is maximal at the look angle  x=0 and

10. The orientation of the target is uniformly random, i.e. the density distribution of the look angle is equal to 1/π (we do not know the orientation of the target).

For the sake of argument, we consider the shadow of a target to be a semicircle (Figure 3). The exact shape of the shadow will not matter. We will show this when we discuss the phenomenon of concordance. This kind of shape for the shadow of a target is similar to the shadow of a sphere (Figure 5).

However, unlike a sphere, the shadow of a target has a different diameter (cross section) at a different look angle x. Therefore, we simulate the cross-section of an ellipsoid using, for example, sin(x)2 as shown in Figure 4.

The use of g(x)=sin(x)2 assumes that the minimal detection probability for one look is zero percent while the maximal detection probability for one look is 100%. This is not realistic. Normally, the minimal detection probability for one look (smallest cross section) is greater than zero percent while the maximal detection probability for one look (largest cross-section) is less than 100%. Therefore, to accommodate this reality, we model ga,b(x)=a+b⋅sin(x)2 where a+b<1 and a, b>0. The parameters a and b  are related to the normalized cross section of the target: a corresponds to the broad size of the target while a+b corresponds to the short size of the target. Nguyen and Mirshak (2016) show that with a=0 and b=0.8, ga,b(x) is similar to the normalized cross-section of an ellipsoid (Figure 6) with parametrization: a1=1.60 m, a2=0.325 m, a3=0.325 m where r⇀=(a1⋅cos⁡θ⋅cos⁡φ,a2⋅cos⁡θ⋅sin⁡φ, a3⋅sin⁡θ).

For completeness, the complement of the normalized cross section of an ellipsoid is shown below:

ge(x)=1−cos(x)2+(a2a1)2⋅sin(x)2

We note that there are two kinds of detection probability. The first kind, g¯, is the single look detection probability, which depends on the orientation of the target and varies between 0 and 1. The second kind of detection probability Pn with concordance or Pn′ without concordance is the expected detection probability based on n looks, which varies between 0.5 and one (P1, P1′=0.5) as shown later. Here, we refer to the look angle simply as “the angle,” while the expected detection probability is referred to as “the detection probability.”

The aim is to maximize the detection probability of n  looks. We, and others, have attempted to solve this problem in the past. To do that, we have assumed that each image is independent; therefore, the outcomes can be described as a Bernoulli process (a binomial density distribution). This assumption is not correct, since analyzing the same image twice (at the same range and the same angle) does not yield additional information. Despite that, we have shown that the global optimal angles for n looks consist of the equidistant angles, i.e. (0, π/n, …, (n−1)⋅π/n). A proof of global optimality was found by identifying all local critical points and showing that each one gives a detection probability that is less than or equal to the one of the equidistant angles.

In this paper, we correct that oversight by introducing the phenomenon of concordance. That is, the pictures are in accord. If the angles are the same, then there is no improvement in the detection probability. The improvement from two pictures increases as the relative angle between the two pictures increases. This phenomenon of concordance assumes that the signal-to-noise ratios of the pictures are high. If the signal-to-noise ratios are low, then signal averaging (Hassan and Anwar, 2010) from multiple pictures at the same angle reduces the noise and hence improves the probability of detection. We note that concordance is not the same as correlation. In probability and statistics, the coefficient of correlation is defined through the covariance between two variables, and it is not a probability. Concordance in this paper represents a probability. However, in the community, we sometimes refer loosely to concordance as correlation.

To illustrate the idea of concordance, we provide three looks at an ellipsoid (Figure 7). The look angles are 0°, 10° and 90° in Panel A, B and C of Figure 7 (not drawn to scale). Panel A and B are similar: together they do not yield more information than either one does separately. However, Panel C is completely different from Panel A and B. Therefore, Panel C adds more information to Panel A and B. We say that Panel A and B are closely in accord while Panel A and Panel B are not in accord with Panel C.

Unsurprisingly, the equidistant angles still globally optimize the detection probability for n looks even when concordance is accounted for. This indicates that our probabilistic model for concordance is correct. The proof for the case with concordance now becomes more natural. Note that the idea of concordance was previously mentioned in (Nguyen and Mirshak, 2016).

To clarify: Figure 8 defines the angle x while Figure 9 displays the symmetry of a target, and Figure 6 shows g  as a function of x.

3. A probabilistic model with concordance

Before we describe the general model of concordance for n looks, we will derive in detail the case of two looks. An example of two looks is shown in Figure 10: μ0 is the first look, and μ1 is the second look while  x is the orientation of the target.

Theorem 3A.

The probability of detection for two looks without concordance.

Without concordance (assuming the two looks are independent such that the circular sectors are equal to π), the probability of detection for two looks can be written as follows:

(1) P2′(μ⇀)=1−∫0πdxπ⋅(1−g¯(x+μ0, π))⋅(1−g¯(x+μ1, π))=1−∫0πdxπ⋅g(x)⋅g(x+μ1−μ0) =1−∫0πdxπ⋅g(x)⋅g(x+μ)

Proof of Theorem 3A.

The first equality in Equation (1) holds, since the integral represents the nondetection probability for two looks one at μ0  and the second at μ1. The second equality holds since g(x) has a period equal to π. The third equality holds since μ=μ1−μ0. QED.

Theorem 3B.

The probability of detection for two looks with concordance and the concordant ρ.

With concordance (assuming the two looks are not independent), the probability of detection for two looks can be written as follows:

(2) P2(μ⇀)=1−∫0πdxπ⋅g(x+μ0)⋅[ρ(μ1−μ0)+(1−ρ(μ1−μ0))g(x+μ1)]=1−∫0πdxπ⋅g(x)⋅[ρ(μ)+(1−ρ(μ))g(x+μ)]

where ρ(μ) simulates the phenomenon of concordance. We name ρ(μ)=1−μ/π the concordant.

Proof of Theorem 3B.

To derive the probability of detection for two looks with concordance, we consider two shadows at two different look angles (Figure 11). The shadow of the first look is the upper blue semicircle while the shadow of the second look is the red stripe semicircle rotated by μ with respect to the blue semicircle. The diameter of the blue semicircle is (1−g(x)) while the diameter of the red semicircle is equal to 1. Therefore, the diameter of the red semicircle is always greater than or equal to the diameter of the blue semicircle.

We deem that new information occurs only when the two sectors of the two semicircles do not overlap. That is, new information corresponds to the circular sector with red stripe subtended by the angle μ.

The probability of detection given the first look with look angle x can be expressed as follows:

P1∼dxπ⋅ππ(1−g(x))=dxπ⋅(1−g(x))

(where dx/π assumes that the orientation of the target is uniformly random). Similarly, the probability of no detection given the first look can be expressed as follows:

Q1=1−P1∼dxπ⋅g(x)

The outcomes after the first look are therefore

P1+Q1

That is, P1 and Q1 are probabilities and at the same time represent the outcomes. P1 represents the outcome that the target is detected while Q1 represents the outcome that the target is not detected. If the target is detected, it remains detected. If the target is not detected, it can be detected or remains not detected at the next look.

The second look with look angle x+μ has two sectors with two corresponding separate contributions. The first contribution (μ/π)=1−ρ(μ) is outside of the sector of the first look, which is considered nondetected and hence provides additional probability of detection. The second contribution  (1−μ/π)=ρ(μ) overlaps with the sector of the first look, which is already considered as detected and hence does not add to the probability of detection.

The outcomes are now as follows:

(P1+Q1)(ρ(μ)+(1−ρ(μ)))=P1+Q1(ρ(μ)+(1−ρ(μ)))

The above equality holds since the detection of the first look (the event P1) is not affected by the second look. However, the nondetection of the first look (the event Q1) can be affected. That is, the second look could provide detection after the first look nondetection. There are two possibilities following the first look nondetection:

1. Q1⋅(1−ρ(μ)) corresponds to the nonoverlapping sector between the shadow of the first look and that of the second look. Hence, this contributes to new information with additional detection probability Q1⋅(1−ρ(μ))⋅(1−g(x+μ)) where (1−g(x+μ)) is the normalized cross section of a target at the second look angle (x+μ);

2. Q1⋅ρ(μ) corresponds to the area that has already been observed. Hence, this has no contribution to the detection probability.

Summing the probabilities of detection, we get the detection probability for two looks (one with look angle x and another with look angle x+μ) can be written as follows:

P2=P1+Q1(1−ρ(μ))(1−g(x+μ))

where P1 is the probability of detection due to the first look, and Q1(1−ρ(μ))(1−g(x+μ)) is the additional detection probability due to the second look with concordance. Simple algebra dictates that

P2=1−g(x)(ρ(μ)+(1−ρ(μ))g(x+μ))⋅dxπ

Integrating over all possible angles x, with concordance, the probability of detection for two looks can be written as follows:

(3) P2(μ⇀)=1−∫0πdxπ⋅g(x+μ0)⋅[ρ(μ1−μ0)+(1−ρ(μ1−μ0))g(x+μ1)]=1−∫0πdxπ⋅g(x)⋅[ρ(μ)+(1−ρ(μ))g(x+μ)]

where ρ(μ) simulates the phenomenon of concordance: g(x)⋅ρ(μ) represents information from the first look but no new information from the second look at μ while g(x)⋅(1−ρ(μ))⋅g(x+μ) represents information from the first look in addition to new information from the second look. QED.

Theorem 3C.

Properties of the concordant ρ(μ).

(4) 1−ρ(μ)={μ/π0≤μ<π/21−μ/ππ/2≤μ≤π

Due to the symmetry of the problem, the function ρ(μ) must satisfy a number of criteria:

1. μ=|μ|;

2. 1≥ρ(μ)≥0;

3. ρ(μ) decreases as a function of  μ;

4. ρ(μ+π)=ρ(μ);

5. ρ(0)=1 and

6. Appropriate periodic extensions.

Proof of Theorem 3C.

Theorem 3B shows that ρ(μ)=1−μ/π. Criterion a implies that the function ρ(μ) does not distinguish one look from another: only their difference matters. Criterion b implies that the function ρ(μ) is a probability. Criterion c implies that there is less concordance when μ  increases. Criterion d implies the target has a symmetry that is periodic with period equal to π. Criterion e implies that there is no new information if it is the same look, i.e. g(x)⋅(ρ(μ)+(1−ρ(μ))g(x+μ))]μ=0=g(x). Criterion f implies that

1−ρ(μ)={μ/π0≤μ<π/21−μ/ππ/2≤μ≤π

This is so, since an ellipsoidal target is symmetric: the left hand side is the mirror of the right hand side. QED.

Knowing that for small μ, ρ(μ)≈e−μ/π, we propose a general model of concordance such that

(5)ρ(μ)={e−α⋅μ0≤μ≤π/2e−α⋅(π−μ)π/2<μ≤π

This function satisfies all the properties listed above with appropriate periodic extensions in addition to the appealing characteristic that ρ(a)⋅ρ(b)=ρ(a+b). That is, the concordance between two looks separated by a+b is the product of the function ρ(μ) at a and the function ρ(μ) at b. The corresponding geometry is shown in Figure 12.

The function in Equation (5) is of course an assumption. The exact expression of the function ρ(μ) depends on the shape and characteristics of the target. However, our model of concordance is flexible in the choice of α and allows us to simulate the phenomenon of concordance with some generalities.

For illustration, we plot ρ as a function of μ in Figure 13. Knowing ρ(μ) allows us to determine the probability of detection for two looks. There are many ways to optimize the probability of detection for two looks. Here, we plot out the probability of detection for two looks as a function  μ in Figure 14 with g(x)=sin(x)2. Figure 14 shows that the probability of detection for two looks is maximal when μ=π/2 in both cases with and without concordance. We also observe that if μ=0, π, we have two identical images. Yet, in the case without concordance (green curve), there is an improvement from one look (blue curve) to two looks. This indicates that the probability of detection without concordance is incorrect as we essentially analyze only one image (two identical images). What is more, in the case with concordance (red curve), the probability of detection for two looks is the same as the one for one look, i.e. when  μ=0, π. This indicates that the probability of detection with concordance is correct and has the right limits.

Theorem 3D.

Probability of detection without concordance for n looks.

(6) Pn(μ⇀)=1−1n⋅{∫0πdxπ⋅g(x+μ0)⋅∏i=1n−1[ρ(μi−μi−1)+(1−ρ(μi−μi−1))g(x+μi)]}−1n⋅{μ0→μ1, μ1→μ2, …, μn−1→μ0}−1n⋅{circular permutations of μi (i=0, …, n−1)}

Proof of Theorem 3D.

Equation (2) is technically correct but is difficult to generalize from two looks to n looks. We need to make it symmetric. That is,

(7) P2(μ⇀)=1−12⋅{∫0πdxπ⋅g(x+μ0)⋅[ρ(μ1−μ0)+(1−ρ(μ1−μ0))g(x+μ1)]}−12⋅∫0πdxπ{μ0↔μ1}

The first integral corresponds to the fact that μ0 is accorded with μ1, and the second integral corresponds to the fact that μ1 is accorded with μ0 where μ1≥μ0 (mod π). Using the characteristics of g(x) and the characteristics of  ρ(μ), we show that Equation (7) is the same as Equation (2). We can now generalize to the case of  n looks (n≥2):

Pn(μ⇀)=1−1n⋅{∫0πdxπ⋅g(x+μ0)⋅∏i=1n−1[ρ(μi−μi−1)+(1−ρ(μi−μi−1))g(x+μi)]} −1n⋅∫0πdxπ⋅{μ0→μ1, μ1→μ2, …, μn−1→μ0} −1n⋅∫0πdxπ{circular permutations of μi (i=0, ..., n−1)}

where the looks μi (i=0, …, n−1) are sorted in increasing order such that 0=μ0≤μ1≤…≤μn−1≤π. Note that due to the periodicity of g(x), we can always set μ0=0. From this point on we will use μ0=0 to alleviate the notation. For example, with n=3 looks, the probability of detection can be written as follows:

(8) P3(μ⇀)=1−13⋅{∫0πdxπ⋅g(x)⋅[ρ(μ1)+(1−ρ(μ1))g(x+μ1)]⋅[ρ(μ2−μ1)+(1−ρ(μ2−μ1))g(x+μ2)]}−13⋅{∫0πdxπ⋅g(x+μ1)⋅[ρ(μ2−μ1)+(1−ρ(μ2−μ1))g(x+μ2)]⋅[ρ(μ2)+(1−ρ(μ2))g(x)]}−13⋅{∫0πdxπ⋅g(x+μ2)⋅[ρ(μ2)+(1−ρ(μ2))g(x)]⋅[ρ(μ1)+(1−ρ(μ1))g(x+μ1)]}

QED

Equation (8) is a model with concordance where we assume concordance between consecutive looks only. Technically, based on our definition of concordance, each look is accorded to all other looks. For example, with four looks, the first look is accorded with the second, the third and the fourth look, while the second look is accorded with the first, the third and the fourth look, etc. This topic awaits further investigation. However, we believe that the optimal look angles will stay the same.

4. Global optimization

Naturally, we search for the look angles that will maximize the probability of detection for n looks so that we can find the target as quickly as possible. In previous unpublished work, we show that the probability of detection for n looks without concordance is globally maximal with the equidistant angles μe⇀=(0, π/n, …, (n−1)⋅π/n). Here, we assert that the equidistant angles also globally maximize the probability of detection for  n looks with concordance.

Theorem 4A.

Globally optimal looks.

The globally optimal looks are the equidistant angles μe⇀=(0, π/n, …, (n−1)⋅π/n).

Proof of Theorem 4A.

Gelfand and Fomin (1963) dictate that if F is the integrand in Equation (7) and K(μ⇀) is the constraint such that μ⇀ are constant parameters equal to C⇀ that are independent of  x:

(9) F(μ⇀)=1n⋅g(x)⋅∏i=1n−1(ρ(μi−μi−1)+(1−ρ(μi−μi−1)⋅g(x+μi)))+(circular permutations of μi(i=0, …, n−1))K(μ⇀)=μ⇀=C⇀

then there exists a function λ⇀(x) such that

(10) Fμi+λi(x)⋅Kμi=0

for i=0, …, n−1 where λ⇀(x) is invariant if we replace μ⇀ by −μ⇀.

This signifies that the critical points μ⇀=μ⇀∗ occur when F(μ⇀∗)=F(−μ⇀∗)  if we set μ0∗=0. There are two symmetries involved. The first allows the freedom to set any angle μi0∗=0. That is, {μi∗, i=0, …, n−1}={μi∗−μi0∗, i=0, …, n−1} (mod π). The second allows the freedom to set all angles to their negative values. That is, {μi∗, i=0, …, n−1}={−μi∗, i=0, …, n−1} (mod π).

For example, let n=4 and let μ⇀=(0, π/4, 2⋅π/3, 3⋅π/4); we plot out  2⋅μ⇀ on a circle in Figure 15. The roots are symmetrical with respect to the horizontal axis in Panel A. We rotate the roots by π around the horizontal axis in Panel B and by π/2 clockwise in Panel C. In all three panels, the roots are symmetrical with respect to the horizontal axis. This example determines all the critical points for the probability of detection with n  looks.

Upon inspection, there are two types of critical points that satisfy both symmetries. Type 1 critical points consist of two sets. The first set can be written as {0, π/m, …, (m−1)⋅π/m} while the second set as {0, π/(2⋅m), …, (2⋅m−1)⋅π/(2⋅m)}. Each set of points could appear more than once in a way such that 1≤m, 2⋅m≤n. Type 2 critical points consist of one set {0, μ, …, (n−1)⋅μ}  that can also appear more than once where  μ=m⋅πn and  m=1, …, n−1.

The commonality of these critical points is that the zero root occurs at least twice except for the equidistant angles. We will show that if the zero root occurs more than once, then the corresponding critical point cannot be globally optimal.

We will show this by replacing the second zero root by  −ε: the new probability of detection will be greater than the one with two zeroes. For example, assuming three looks, the critical points are as follows:

1. (0, 0, 0);

2. (0, 0, π/2) equivalent to (0, π/2, π/2) and

3. (0, π/3, 2⋅π/3)

Examining the second critical point (0, 0, π/2), we will show that  (−ε, 0, π/2)  yields a better detection probability than the one based on (0, 0, π/2) for  ε>0 and infinitesimal. The two detection probabilities can be written as follows:

P((0, 0, π/2))=P((0, π/2))=1−12⋅∫0πdxπ⋅g(x)⋅(ρ(π2)+(1−ρ(π2))⋅g(x+π2))−12⋅∫0πdxπ⋅g(x+π2)⋅(ρ(π2)+(1−ρ(π2))⋅g(x))=1−∫0πdxπ⋅g(x)⋅(ρ(π2)+(1−ρ(π2))⋅g(x+π2))

For clarity, we define

gˆ2=∫0πdxπ⋅g(x)⋅(ρ(π2)+(1−ρ(π2))⋅g(x+π2))

P((−ε, 0, π/2))=1−(A+B+C)

where

A=13⋅∫0πdxπ⋅g(x−ε)⋅[ρ(ε)+(1−ρ(ε))⋅g(x)]⋅[ρ(π2)+(1−ρ(π2))⋅g(x+π2)]

B=13⋅∫0πdxπ⋅g(x)⋅[ρ(π2)+(1−ρ(π2))⋅g(x+π2)]⋅[ρ(π2+ε)+(1−ρ(π2+ε))⋅g(x−ε)]

C=13⋅∫0πdxπ⋅g(x+π2)⋅[ρ(π2+ε)+(1−ρ(π2+ε))⋅g(x−ε)]⋅[ρ(ε)+(1−ρ(ε))⋅g(x)]

Expanding in terms of ε  such as

g(x−ε)=g(x)−ε⋅g′(x)+O(ε2)

ρ(ε)=ρ(0)−α⋅ε⋅ρ(0)+O(ε2)

And the local optimality of the critical point (obtained through symmetry) such as

13⋅∫0πdxπ⋅g′(x)⋅[ρ(0)+(1−ρ(0))⋅g(x)]⋅[ρ(π2)+(1−ρ(π2))⋅g(x+π2)]=0

We can show that the O(ε) of A, B and C are such that

A≤13⋅gˆ2−α⋅ε3⋅∫0πdxπ⋅g(x)⋅(1−g(x))⋅[ρ(π2)+(1−ρ(π2))⋅g(x+π2)]B≤13⋅gˆ2−α⋅ε3⋅∫0πdxπ⋅g(x)⋅(1−g(x))⋅ρ(π2)⋅[ρ(π2)+(1−ρ(π2))⋅g(x+π2)]C≤13⋅gˆ2−α⋅ε3⋅∫0πdxπ⋅(1−ρ(π2))⋅g(x)⋅(1−g(x))⋅g(x+π2)

Therefore,

A+B+C≤gˆ2

This means that

P((−ε, 0, π/2))>P((0, 0, π/2))

which implies that P((0, 0, π/2))  cannot be the globally maximal detection probability. This pattern holds in general. That is, if there are two zero roots (0, 0, ∗) (possibly more), then we replace them by (−ε, 0, ∗); the replacement will generate a greater detection probability than the one with two zero roots (*represents the remaining roots that are unchanged).

The only critical point that does not have at least two zero roots consists of the equidistant angles (roots). This shows that the equidistant angles generate the globally maximal detection probability since they represent the only critical point among all critical points that is not sub-optimal. QED. The general proof is shown in Appendix 1.

We observe that for the equidistant angles each integral in Equation (7) is equal to one another. To determine the probability of detection, we only need to perform one integral.

5. Examples – ga,b(x)=a+b×sin(x)2

In Nguyen and Mirshak (2016), the detection probability of n equidistant angles without concordance:

(11)Pn′(μe⇀)=1−24n

where μe⇀=(0, πn, …, (n−1)⋅πn), g(x)=sin(x)2 and we make use of the following identity:

sin(n⋅x)222⋅n−2=∏k=0n−1sin(x+k⋅πn)2

Theorem 5A.

The detection probability for  n equidistant angles with concordance can be written as follows:

(12) Pn(μe⇀)=1−14n⋅{(1+ρ)2⋅n−1+(1−ρ)2⋅n−1}

where for simplicity, we write ρ=ρ(πn) here and in the remainder of the paper.

Proof of Theorem 5A.

We make use of two identities from (Gradshteyn and Ryzhik, 1979a, b):

cos⁡h(n⋅ϕ)−cos(n⋅x)=2n−1⋅∏k=0n−1{cos⁡h(ϕ)−cos(x+2⋅k⋅πn)}

∫0πdx⋅cos(n⋅x)1+a⋅cos(x)=π1−a2⋅(1−a2−1a)n

with a2<1. We also observe that

∏k=1n−1{cos⁡h(ϕ)−cos(x+2⋅k⋅πn)}=12n−1⋅cos⁡h(n⋅ϕ)−cos(n⋅x)cos⁡h(ϕ)−cos(x) =C(x)

where the lower bound of k=1. As well,

∏k=0n−1{ρ+(1−ρ)⋅sin2(x+k⋅πn)}=∏k=0n−1{(1+ρ2)−(1−ρ2)⋅cos(2⋅x+2⋅k⋅πn)}=(1−ρ2)n⋅∏k=0n−1{cos⁡h(ϕ)−cos(2⋅x+2⋅k⋅πn)}=(1−ρ)n22⋅n−1⋅{cos⁡h(n⋅ϕ)−cos(2⋅n⋅x)}=D(x)

sin2(x)⋅∏k=1n−1{ρ+(1−ρ)⋅sin2(x+k⋅πn)}=11−ρ⋅{D(x)−ρ⋅C(x)}

cos⁡h(ϕ)=1+ρ1−ρ=u

cos⁡h(n⋅ϕ)=12⋅{(cosh(ϕ)+sin⁡h(ϕ))n+(cos⁡h(ϕ)−sin⁡h(ϕ))n}=12⋅{(u+u2−1)n+(u−u2−1)n}

(1−ρ)n⋅cos⁡h(n⋅ϕ)=12⋅{(1+ρ)2⋅n+(1−ρ)2⋅n}

QED

For illustration, we plot the probability of detection as a function of number of looks in Figure 16.

The first order effect is that the probability of detection almost doubles from one look to two looks whether we consider concordance or not. This illustrates the benefit of multiple looks.

The second-order effect is the difference between two cases with and without concordance. With concordance, we assume α=1, 2. Without concordance, the probability of detection approaches 100% as the number of looks increases. However, with concordance, the probability of detection reaches an asymptotic value that is less than 100%. In fact, the limit as n→∞ can be determined to be

(13)limn→∞Pn(μe⇀)=1−12⋅e−α⋅π/2

which is the probability of detection for one look compounded with the minimal concordance. As α→∞, we recover the case without concordance. That is, limα→∞limn→∞Pn(μe⇀)=1. Note that there are two conflicting patterns in the case with concordance. That is, as the number of looks increases, the probability of nondetection decreases as 1/4n. However, the concordance also increases, i.e. ρ→1, which reduces the probability of detection. This can be seen in the first term of Equation (12), i.e. (1+ρ)2⋅n−1. As a whole, however, the probability of detection with concordance still increases with the number of looks. Generally, the difference in the probability of detection between the case without concordance and the case with concordance (α=1) is about ten percent for three looks or more. If we consider five targets, the probability of detection for each target without concordance is 0.993, while the probability of detection with concordance is 0.855. The probability of detecting all five targets without concordance is 0.9935=0.962 and with concordance is 0.8555=0.458. This is substantial as there is a probability of 0.542 that we do not detect at least one target with concordance.

Figure 17 shows the significant improvement in the probability of detection due to multiple looks especially from one look to two looks. However, this improvement must be tempered by the phenomenon of concordance since it yields a lower probability of detection than the one without concordance. Therefore, when planning for search and detection, we must be cautious because of concordance.

Theorem 5B.

Assuming

ga,b(x)=a+b⋅sin(x)2 , the probability of detection with concordance for n looks can be written as follows:

(14)Pa,b,n(μe⇀)=1−tn2n⋅(1−ρ)⋅{(1+1−r2)n⋅(1−ρt⋅1−r2)+(1−1−r2)n⋅(1+ρt⋅1−r2)}

where

(15)t=ρ+(1−ρ)⋅(a+b2)

and

(16)r=(1−ρ)⋅b2ρ+(1−ρ)⋅(a+b2)<1

Proof of Theorem 5B.

The same methodology as applied in Theorem in 5A can be used to determine the probability of detection for  n equidistant angles. QED.

There is also an asymptotic limit to the probability of detection with concordance for equidistant angles when we assume the two parameters a and b:

(17)limn→∞Pa,b,n(μe⇀)=1−(a+b2)⋅e−α⋅π⋅(1−a−b2)

If we let a=0 and b=1, we obtain results consistent with Equation (10). The asymptotic limit is not only of academic interest. We could design an experiment with many looks, measure the associated probability of detection experimentally and from this determine the parameter α that models concordance. It is expected that  α depends on the sensor and the type of target. Figure 17 shows the probability of detection as a function of number of looks with and without concordance. It is seen that the probability of detection with concordance is less than the probability of detection without concordance. As discussed earlier, the probability of detection without concordance is over estimated. This is potentially dangerous: one could infer that all the targets such as explosive mines are detected with some confidence level while it is not the case.

Figure 17 shows the probability of detection as a function of number of looks for multiple values of a. The parameter a generates the same effect as that of the single look probability of no detection: as a decreases, the probability of detection increases.

Figure 18 shows the probability of detection as a function of number of looks for multiple values of b. Like parameter a, parameter b generates the same effect as that of the single look probability of no detection: as b decreases, the probability of detection increases.

5.1 Search patterns

Based on the optimal look angles, we have developed corresponding search patterns (Figure 19). The colored map shows the density distribution of targets in the search area. Targets are more densely distributed in the center of the search area than around its borders. Panel A of Figure 19 corresponds to one look, Panel B to two looks and Panel C to three looks. As we have shown by our proof of global optimality for μ=π/n, the optimal offset between the angles of a given number of looks is given by dividing 180° by the number of looks. Hence, when n looks = 2, the optimal angle between the two looks is π/2, (90 deg), when n looks = 3, the optimum between them is π/3, (60 deg) and so on. Panel A shows a lawn mowing pattern done with a single look angle. Panel B shows two looks, using the optimal 90 deg offset. Panel C shows three looks, again with the optimal offset between the three, which is 60 deg, as noted above. The probabilities of detection without concordance in Panel 19 A, 19 B and 19 C are, respectively, 0.5⋅λ, 0.875⋅λ and 0.969⋅λ where λ is a parameter that includes other factors, such as the dependency on the range from the target to the searcher or highlights, etc. The corresponding probabilities of detection with concordance are, respectively, 0.5⋅λ, 0.797⋅λ and 0.84⋅λ with α=1.

The illustration shows evidence of superior target detection ability as we increase the number of looks and offset each of their angles optimally (brighter colors indicate greater detection probabilities).

Note that in the multiple look case, multiple searchers can carry out the searches at the same time or one searcher can carry out a set of parallel searches (lawn mowing pattern). When completed, the same searcher can carry out the next set of parallel searches. Other search patterns can be found in Bays et al. (2011).

6. Discussion and conclusion

This paper describes a phenomenon, concordance, that is little known in the open literature. Concordance suitably determines the probability of detection. Without concordance, the probability of detection is over estimated, an oversight that affects resource planning for search and detection operations and puts personnel in danger, especially in mine countermeasure operations.

In addition, we have derived the functional expression for the function ρ(μ). Using the function ρ(μ) and the model of concordance, we have established that the equidistant angles globally maximize the probability of detection. The global optimality holds for a large class of targets that have mirror symmetry. We also note that the corresponding optimization problem is NP-hard. Without symmetry, it is intractable even if we seek numerical values only.

We have also derived the asymptotic limit of the probability of detection as the number of looks approaches infinity. This allows parameter α that defines the function ρ(μ) through experiments to be measured. For illustration, we model the single look probability of detection as a normalized cross-section of an ellipsoid. The resulting probability of detection for n looks has a closed form of expression that accounts for the number of looks, the cross-section of the target from different angles as well as its short side and its broad side.

It is our hope that this material will be taught to and used by search and rescue operators because it fundamentally changes the way we model detection theory from analyses of sensor images.

In a Bayesian approach, such as the search for the Scorpion submarine (Richardson and Stone, 1971), we could plan for the number of looks n to obtain a desired probability of detection for each grid. Each time a grid is visited, the Bayesian probabilities are updated. A grid could be visited n times. However, when a grid is revisited, the searcher would scan the area with an offset that corresponds to π/n. For example, with three looks, there will be three scans as shown in Panel C of Figure 19. Each scan will yield a different look.

Our approach may also generate optimal solutions for objects that display a different type of symmetry, such as rotational symmetry (looks similar after rotation), cyclic symmetry (several mirror planes passing through a fixed axis) and dihedral symmetry (several mirror planes passing through a fixed axis with one perpendicular to the axis) (Chaouch and Verroust-Blondet, 2009; Li et al., 2016).

We note that important symmetrical targets may appear nonsymmetrical: they may be partially hidden or fragmented. In these cases, multiple looks still provide valuable information. Detailed knowledge of the target also adds to an optimal search path.

Laine and Bauer (2008) describe how to recognize nonsymmetrical targets with multiple sources and multiple looks. Situ et al. (2016) also considers multiple looks for synthetic aperture radar combat identification. Situ et al. (2016) and Laine and Bauer (2008) both provide robust classifying algorithms to identify a target with a high confidence level. These papers examine false positive and false negative events. Several other techniques, including concatenating images, a Bayesian classifier, wavelet decomposition and principal components analysis, also show improved performance in target recognition (Huan and Pan, 2013; Ding and Wen, 2017; Laubie et al., 2015, 2018; Salvador, 2016; Situ et al., 2016; Zhang et al., 2012).

Other search and detection approaches are drawn from game theory (Dambreville and Le Cadre, 2007) as well as exhaustive searches that include integration of the concept of multiple look angles into the search models (Chung and Silvestrini, 2014).

These papers examine the recognition and identification of a target but in less detail than our approach. Generally, our strategy yields detections of potential targets which complement the goals of previous research. Also, to the best of our knowledge, these previous techniques do not provide an analytical model.

Once an object is deemed a potential target, further information may be obtained by taking more pictures at additional looks or by making a video, enabling identification of the potential target as a friend or an enemy. A mistake in identification could lead to friendly fire and damage to infrastructure.

In the context of a search and detection operation, there is limited time to find the target before life is lost. In real terms, improving the chance of detection translates into the difference between success or failure, life or death.

Figures

Figure 1

A manta mine

Figure 2

Actual mine observed at 85° (left) and at 0° (right)

Figure 3

Shadow of a target

Figure 4

Probability of not detecting a single target as a function of look angle (θ=π)

Figure 5

Shadow of a sphere

Figure 6

A mine modeled as an ellipsoid

Figure 7

An example of the phenomenon of concordance (the cross section of an ellipsoid viewed from different look angles)

Figure 8

Cylindrical target observed at look angle  x

Figure 9

Symmetries of the target

Figure 10

An example of two looks

Figure 11

Overlapping shadow illustration

Figure 12

Transitivity of the exponential function

Figure 13

ρ as a function of μ for three values of α

Figure 14

Probability of detection for one look and two looks as a function of μ

Figure 15

Symmetries of {2⋅μi|i=0, …, 3}={0, π/2, π, 3⋅π/2}

Figure 16

Probability of detection as a function of number of looks with and without concordance assuming g(x)=sin(x)2

Figure 17

Probability of detection as a function of number of looks assuming g(x)=ga,b(x)=a+b⋅sin(x)2  with b=0.8  and =1

Figure 18

Probability of detection as a function of number of looks assuming g(x)=ga,b(x)=a+b⋅sin(x)2 with a=0.1 and =1

Figure 19

Search patterns: one look (A), two looks (B) and three looks (C)

Appendix 1 Global optimality of the equidistant angles

In this Appendix, we prove that the equidistant angles yield the global optimal detection probability. In Section 4, we identified two types of critical points. Type 1 critical points consist of {0, π/m, …, (m−1)⋅π/m} and {0, π/(2⋅m), …, (2⋅m−1)⋅π/(2⋅m)}. Each of them could appear more than once in a way such that  1≤m, 2⋅m≤n. Type 2 critical points consist of {0, μ, …, (n−1)⋅μ}  that can also appear more than once where μ=m⋅πn  and  m=1, …, n−1.

Due to concordance, any angle that is repeated more than once has the same effect as if it is single look angle. For example,

P((0, 0, π/2))=P((0, π/2))

This implies that the detection probability of either Type 1 critical points or Type 2 critical points can be written as follows:

P((0, μ, 2⋅μ, …, (s−1)⋅μ))

where s⋅μ=π and none of the angles in the set {0, μ, 2⋅μ, …, (s−1)⋅μ} is repeated. With the exception for the equidistant angles, we can assume that s<n. We will show that

P((−ε, 0, μ, 2⋅μ, …, (s−1)⋅μ))≥P((0, μ, 2⋅μ, …, (s−1)⋅μ))

That is, the probability of detection on the LHS at angle −ε and the angles {0, μ, 2⋅μ, …, (s−1)⋅μ} is greater than or equal to the one on the RHS at the angles {0, μ, 2⋅μ, …, (s−1)⋅μ} only. Since s<n, the probability of detection on the LHS corresponds to s+1(≤n) looks. This ensures that the LHS is within the constraint of n looks. This is so since if not, we could argue that with more than n  looks the corresponding probability of detection could be greater than those with n  looks or less. Hence, it would not show the optimality of n  looks.

Before we provide the proof, we define the notation below:

gˆs=∫0πdxπ⋅g(x)⋅(ρ(μ)+(1−ρ(μ))⋅g(x+μ))⋅…⋅(ρ(μ)+(1−ρ(μ))⋅g(x+(s−1)⋅μ))

Ps=P((0, μ, …, (s−1)⋅μ))=1−gˆs

Pε=P((−ε, 0, μ, …, (s−1)⋅μ))=1−gˆε

(A1)gˆε=1s+1⋅∫0πdxπ⋅{g(x−ε)⋅[ρ(ε)+q(ε)⋅g(x)]⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]+g(x)⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]⋅[ρ(μ+ε)+q(μ+ε)⋅g(x−ε)]+g(x+μ)⋅[ρ(μ)+q(μ)⋅g(x+2⋅μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]⋅[ρ(μ+ε)+q(μ+ε)⋅g(x−ε)]⋅[ρ(ε)+q(ε)⋅g(x)]+…+g(x+(s−1)⋅μ)⋅[ρ(μ+ε)+q(μ+ε)⋅g(x−ε)]⋅[ρ(ε)+q(ε)⋅g(x)]⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−2)⋅μ)]}

where q(x)=1−ρ(x).

There are s+1 terms in gˆε. We will show that each of them is less than or equal to gˆs. Hence, gˆε≤gˆs which implies that  Pε=1−gˆε≥1−gˆs=Ps. This shows that Ps cannot be the globally optimal probability of detection since there is another set of look angles {−ε, 0, μ, 2⋅μ, …, (s−1)⋅μ} that yield a greater probability of detection than Ps. Since Ps  is the probability of detection of any critical points except the set of equidistant angles. By elimination, the set of equidistant angles must be the globally optimal critical point.

Even though there are s+1 terms in gˆε, there are only three types of dependencies on  ε:

1. g(x−ε)⋅[ρ(ε)+q(ε)⋅g(x)];

2. [ρ(μ+ε)+q(μ+ε)⋅g(x−ε)] and

3. [ρ(μ+ε)+q(μ+ε)⋅g(x−ε)]⋅[ρ(ε)+q(ε)⋅g(x)].

For each type, we expand to the first order of O(ε) and show that the contribution O(ε0)=O(1)≤gˆss+1 while the O(ε) is negative. This indicates that

(A2)gˆε≤1s+1⋅(∑i=1s+1gˆs−α⋅ε⋅M)≤gˆs

where M is a finite positive number. To do that, we gather O(1) terms and O(ε)  terms. Any O(ε) terms involving g′(x) will be equal to zero due to the symmetry and the local optimality of the critical point. As a result, each term in Equation (A2) is less than or equal to gˆss+1−α⋅ε⋅M for some finite and positive number M. For illustration, we perform the expansion of type A. Given that for an infinitesimal ε,

g(x−ε)=g(x)−ε⋅g′(x)+O(ε2)

and

ρ(ε)=ρ(0)⋅(1−α⋅ε)+O(ε2)=1−α⋅ε+O(ε2)

As (0)=1, substituting the two expressions above into type A we get

g(x−ε)⋅[ρ(ε)+q(ε)⋅g(x)]=g(x)−α⋅ε⋅g(x)⋅(1−g(x))−ε⋅g′(x)+O(ε2)

This entails that

(A3)1s+1⋅∫0πdxπ⋅g(x−ε)⋅[ρ(ε)+q(ε)⋅g(x)]⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]=1s+1⋅∫0πdxπ⋅[g(x)−α⋅ε⋅g(x)⋅(1−g(x))−ε⋅g′(x)+O(ε2)]⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]=1s+1⋅∫0πdxπ⋅[g(x)−α⋅ε⋅g(x)⋅(1−g(x))+O(ε2)]⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]=1s+1⋅(gˆs−α⋅ε⋅∫0πdxπ⋅[g(x)⋅(1−g(x))]⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]+O(ε2))≤1s+1⋅gˆs

The first equality is due to the expansion in  ε. The second equality is due to the local optimality, i.e. ∫0πdx⋅g′(x)⋅[ρ(μ)+q(μ)⋅g(x+μ)]⋅…⋅[ρ(μ)+q(μ)⋅g(x+(s−1)⋅μ)]=0. The third equality is due to rearranging the second equality so that the O(ε) is evident. The following inequality is due to the fact each term making up O(ε) is nonnegative. Similar results can be drawn with type b and type c. QED.