Information-Theoretic Bounds on Target Recognition Performance Based on Degraded Image Data.
AbstractThis paper derives bounds on the performance of statistical object recognition systems, wherein an image of a target is observed by a remote sensor. Detection and recognition problems are modeled as composite hypothesis testing problems involving nuisance parameters. We develop information-theoretic performance bounds on target recognition based on statistical models for sensors and data, and examine conditions under which these bounds are tight. In particular, we examine the validity of asymptotic approximations to probability of error in such imaging problems. Problems involving Gaussian, Poisson, and multiplicative noise, and random pixel deletions are considered, as well as least-favorable Gaussian clutter. A sixth application involving compressed sensor image data is considered in some detail. This study provides a systematic and computationally attractive framework for analytically characterizing target recognition performance under complicated, non-Gaussian models and optimizing system parameters.
Introduction
Typical target recognition problems involve detection and classification of targets as well as
estimation of target parameters such as location and orientation. A set of possible targets
comprises objects such as tanks, trucks, and planes. The scene in which targets are present is
acquired by sensors such as coherent laser radar imagers, Synthetic Aperture Radar systems,
forward-looking infrared radar (FLIR) systems, and hyperspectral sensors [1, 2]. These imaging
sensors are used for object recognition in numerous military and civilian applications. To
exploit the capabilities of these sensors in a target-recognition context, image-understanding
algorithms are required to interpret remote observations of complex scenes. In this context,
a pattern-theoretic framework [3, 4] using a deformable template representation of targets
is considered. The targets are modeled as deformations of rigid-body templates, and variability
of pose is introduced via rigid-body motions. The various other unknown parameters
such as target class and thermodynamic profile that characterize within-class variability are
modeled statistically. Statistical models for scene clutter and sensors are also determined.
A statistical approach provides a systematic framework for integrating prior knowledge
about the scene and targets with observational models and for fusing information from
multiple sensors. Once accurate statistical models have been identified, it is in principle
possible to compute optimal solutions to problems of detection, classification and parameter
estimation by application of basic principles of statistical inference [5, 6]. Even when optimal
algorithms are computationally intractable, statistical theory provides fundamental bounds
on the performance of any algorithm. The practical benefits of this approach have been
documented in prior work on target recognition [3, 4] and in related problems [7].
Target classification can often be described as a composite hypothesis-testing problem.
The various hypotheses are the di#erent target types of interest and the null hypothesis
(no target present in the scene). Probabilistic models are formulated under each hypothesis.
These models may be complicated due to dependencies on various unknown parameters, such
as target orientation, motion, and reflectance properties. Such parameters may be viewed
as nuisance parameters, leading to the composite hypothesis-testing formulation.
Additional di#culties are introduced when the sensors are located at a remote location,
e.g., on a mobile platform. In this case, the sensor data are transmitted over a bandwidth-limited
communication channel prior to processing by the computer that hosts the target
recognition algorithm. Lossy compression algorithms are used to e#ciently transmit sensor
data to the host computer. This operation degrades recognition performance, so it is important
to select the compression algorithm carefully. While heuristic evaluation methods are
used in current practice [8], it would be preferable to select the parameters of the compression
algorithm (as well as other system parameters) so as to optimize fundamental measures
of recognition performance. Such measures include Bayesian cost or Bayesian probability of
error, but they are typically intractable.
For such complex problems, an attractive alternative is to work with criteria that are
both tractable and meaningful approximations to the "ideal" performance measures above.
Natural candidates include the Cherno# and Kullback-Leibler distances [6], [9]. Cherno#
distances provide upper bounds and asymptotic expressions for the probability of error (P e ) in
detection problems, and Kullback-Leibler distances provide upper bounds on the probability
of miss (P miss ) for a fixed probability of false alarm (P f ). Both Cherno# and Kullback-Leibler
distances belong to the broad category of measures studied by Ali and Silvey, which
quantify the distance or dissimilarity between two distributions [10]. These distances satisfy
certain axioms of statistical inference which makes them particularly attractive in problems
involving quantization and multisensor data fusion.
Our driving application, used throughout to illustrate the theory and its numerous possible
applications, is the detection of a known target with unknown orientation. The sensor
data are corrupted by additive white Gaussian noise and are subjected to lossy compression
using a transform image coder. We show that despite the nonlinearity introduced by
the quantizers, tractable information-theoretic bounds on detection performance can still be
derived.
For composite hypothesis testing involving unknown nuisance parameters, even information-theoretic
distances are di#cult to evaluate. In this case, we develop tractable upper
and lower bounds on these distances, as well as precise expressions for asymptotic probabilities
of error. The tightness of these bounds is evaluated through theoretical analysis as well
as Monte-Carlo simulations. Finally, we extend the theory developed for binary hypothesis
testing to M-ary case, which covers recognition problems involving multiple target classes.
The paper is organized as follows. Sec. 2 describes the system model and the likelihood
ratio test (LRT) used by an optimal detector. Sec. 3 introduces Ali-Silvey distances and
the properties that make them attractive in target recognition problems. Sec. 4 briefly
reviews basic asymptotic properties of Cherno# bounds. In Sec. 5, performance bounds
for a simple detection problem involving compressed, noisy data are derived and compared
with actual probability of error using theoretical analysis and numerical simulations. The
analysis is extended to more complex detection problems involving nuisance parameters in
Sec. 6. Bounds on classification of multiple targets are derived in Sec. 7, and conclusions are
presented in Sec. 8.
System Model
To demonstrate the key ideas and concepts behind our methodology, we first consider a
composite binary detection problem. The task of the detection algorithm is to determine
whether a known target is present or not. There may be unknown nuisance parameters
associated with the target. The methods developed in the binary case are extended to the
classification of multiple targets in Sec. 7.
2.1 Image Model
Consider a target depending on an unknown parameter # taking its values in some set #. For
instance, the target may be a known template with unknown orientation. For ground-based
targets, # would then be the special orthogonal group SO(2) of rotation matrices [3]. In
the general pattern-theoretic framework of Miller et al. [3], templates are CAD (computer-
aided design) representations of two-dimensional surface manifolds of rigid objects, and # is
an element of a Lie group # whose elements characterize deformations of the template. In
infrared imaging problems, # may be a vector or a smoothly varying function describing the
unknown thermodynamic state of the target. In each case, the target is denoted I(#) and is
completely known if # is known. Target parameterizations reduce the variability of targets
to a low-dimensional, unknown parameter #.
2.2 Sensor Model
The target I(#) is seen through a projection map T , and the projected image T I(#) is
captured by a noisy sensor. Let I D be the sensor data, an N-pixel image. These data are
related to the true image T I(#) through some probabilistic map p(I D
|#). For instance, we
shall apply our analysis to an additive white Gaussian noise model, in which case I
T I(#, where # is sensor noise with mean zero and variance # 2 . Here p(I D
|#) is an
N-variate Gaussian distribution with mean T I(#) and covariance matrix equal to # 2 times
the N -N identity matrix. Figs. 1 and 2 show two examples that will be used to illustrate
the theory: 64 - 64-pixel images of a ground-based T62 tank at orientation
truck at orientation along with noisy sensor data I D . The signal-to-noise is defined
as
denotes the Euclidean norm of x. The SNR in the example of
Figs. 1 and 2 is 15 dB.
2.3 Data Model
In order to account for the need to transmit remote sensor data I D to a central computer
[8], we include a model for lossy compression in our formulation. A special case of this setup
is the conventional detection problem in which the sensor data are directly available to the
target detection algorithm. We restrict our attention to the class of transform-based coders
which are ubiquitous in practice. Transform coding is attractive due to its good compression
performance and low computational complexity [11], and this model simplifies the theoretical
analysis as well.
We use the following simplified mathematical model. Let U be the unitary (orthonormal)
transform used by the coder, and c be the transformed image data. In practice,
U could be a wavelet transform, or a discrete cosine transform, as in the JPEG image
compression standard. We denote the transform of the projected image T I(#) by
UT I(#). Signal energy is preserved under orthonormal transforms, so
and ||c D
||.
The transform coe#cients c D are quantized. The quantized coe#cients are denoted by
We assume that scalar quantizers Q n are
applied to each individual coe#cient: - c D
. The standard choice
used in our experiments is uniform scalar quantizers with a deadzone near zero, see Fig. 3.
In other words, the nonlinear operation Q is separable. The resulting decompressed image
I di#ers from I D due to quantization errors. Throughout this paper, we will use
the tilde (-) symbol to denote quantities pertaining to quantized data. Fig. 4 summarizes
our model for clean images I(#), noisy sensor data I D , and observed (compressed) data -
I D .
2.4 Conditionally Independent Data Sets
In a variety of target recognition problems, the data -
I D may be partitioned into components
that are statistically independent, conditioned on the target I(#). This property simplifies
our analysis as it suggests the use of asymptotic techniques, and is encountered in applications
such as the following.
1. Sensor noise in various imaging modalities can be modeled as independent and identically
distributed (i.i.d.) Gaussian noise (see Sec. 2.2), multiplicative noise (in coherent
imaging systems), or Poisson noise (in noncoherent optical imaging systems). In each
case, individual pixels of the image data -
I D are independent, conditioned on the illuminating
image field T I(#).
2. When -
I D are multisensor data, the degradations introduced by individual sensors are
often independent, even though individual sensors may involve complicated statistical
models.
3. In our main application of interest, sensor noise is i.i.d. Gaussian, and transform
coe#cients are individually quantized. The sensor noise w viewed in the orthonormal
transform domain is still i.i.d. Gaussian noise, so the degradations introduced by the
cascade of sensor noise and coe#cient quantization are independent: the observed
transform coe#cients - c D
are independent, given #. (The discrete
distribution of these coe#cients is obtained by integration of the distribution of c n (#)+
over the quantization cells.)
2.5 Detection Problem
Under the image, sensor and data models above, target detection can be formulated as a
binary statistical hypothesis test. If H 0 and H 1 refer to the hypotheses that the target is
absent or present, respectively, we have
I D
I D ),
I D
I D
|#
(2)
In Bayesian
detection, the uncertainty about # is modeled using a prior distribution #. Under
I D are distributed according to the mixture distribution
I D
I D
|#) d#. (3)
2.6 Optimal Likelihood Ratio Detector
Under hypotheses H 1 and H 0 , -
I D is distributed according to pdf's -
. The likelihood
I D
I D )/-p 0 ( -
I D ) is a su#cient statistic for detection, i.e., all we need to know is
the likelihood ratio for deciding between the hypotheses H 1 and H 0 [5]. The likelihood ratio
is invariant to invertible operations such as the transform U in a transform coder. Under a
variety of optimality criteria, the detection algorithm takes the form of a LRT 1
I D
I D )
I D )
#, (4)
where # is an appropriate threshold. The value of # depends on the optimality criterion [5].
In a Neyman-Pearson test, the threshold # is chosen such that for a given probability of false
the probability of miss (P miss ) is minimized. Under the minimum-probability-
of-error rule, the optimal decision is -
I D
I D )], where - i is
prior probability for hypothesis H i . The LRT in (4) is then optimal when # is equal to the
of the prior probabilities. The probability of error, in this case, is 2
I D
I D
I D , (5)
expectation under hypothesis H 0 . Of interest is also the conditional
probability of error P e|# , which characterizes detection performance under a specific target
configuration (#).
We consider two detection problems. The first is a simple hypothesis-testing problem:
the set # reduces to a singleton. The second problem is a composite hypothesis-testing
In (4), we implicitly assume that a randomized decision is made in the case -
I D
We use the same notation for integrals such as (5) whether the integration variable -
I D is continuous- or
discrete-valued. The measure d -
I D used is either a Lebesgue or a counting measure.
problem.
Detection problem 1: No nuisance parameters. In this problem, # is known, so the
target T I(#) is deterministic, and the detection problem becomes a simple binary hypothesis
testing problem. We assume, as in Sec. 2.4, that the data can be partitioned into independent
components. To make the discussion concrete, we focus on the third case in Sec. 2.4:
i.i.d. Gaussian sensor noise and transform coding. The distributions of the transform coefficients
under H 0 and H 1 are given by -
respectively. The likelihood ratio -
is the product of the likelihood ratios L(-c D
individual coe#cients:
. (6)
Hence the log likelihood ratio is the sum of the log likelihood ratios of each coe#cient.
Detection problem 2: Presence of nuisance parameters. In this case, the nuisance
parameter # is modeled as random with prior #. Under H 1 , the distribution of the
compressed data - c D is the mixture
|#) is the product of the marginals -
|#). The LRT in (4) can be computed
using the mixture in (7). As we shall see in Sec. 6, the presence of a mixture in the model
introduces significant computational and analytical complications.
3 Information-Theoretic Bounds on Detection
The previous section formulated target detection based on compressed data as a statistical
hypothesis testing problem. The threshold # in the LRT (4) can be chosen to minimize the
probability of error P e or the probability of miss (P miss ), for a given value of P f . Unfor-
tunately, both P e and P miss are intractable functions of the N-variate distributions -
and, in general, can only be evaluated experimentally. Hence, it is not feasible
to optimize the parameters of high-dimensional nonlinear systems such as lossy image
coders with respect to P e or P miss . This motivated us to investigate a general category of
performance measures that provide tractable bounds on P e and P miss . Since the ability to
distinguish between two statistical hypotheses depends on the respective conditional distributions
of the data, measures of distance or dissimilarity between two distributions are
natural performance metrics.
Ali and Silvey studied a generic category of distances that measure the dissimilarity
between two distributions [10]. The Ali-Silvey class of distances is based on an axiomatic
definition and takes the general form:
where f is any increasing function, C is any convex function on [0, #), -
is the likelihood ratio for the data, and E 0 is the expectation under hypothesis H 0 . It
is convenient to also allow pairs (f, C) where f is decreasing and C is concave. Kassam
[12] and Poor and Thomas [13] have shown how these performance metrics can be used for
optimal quantizer design in detection problems. In addition to convexity properties, Ali-
Silvey distances possess two attractive properties: they are invariant under application of
invertible maps to the data, and they are decreased under application of many-to-one maps
such as quantization [12], [13]. Specifically,
Observe that
where f(- ln(-) is convex decreasing and is concave, is in the
Ali-Silvey class (8). Even though P e is not a practical choice for design, there exist two
distances in the Ali-Silvey class that are closely related to P f and P miss .
The first are Cherno# distances [5], [6],[9]:
I D
I D )
I D )
I
where again, f is convex decreasing and C is concave. For this is same as the
Bhattacharyya distance [6], [9]. Cherno# distances give an upper bound on both P f and
where # is the threshold in the LRT of (4), and P i [-] is the probability under hypothesis H i .
For the minimum-probability-of-error rule, together with (13) give an
upper bound on P e . This bound can be tightened in scale factor [5] to give
We also use Kullback-Leibler distances [9]:
I D )
I D )
I D )
I
Here f is linear increasing and C is convex. The motivation for considering (15) is Stein's
lemma [9]. Under some conditions, this lemma relates the asymptotic probability of a miss
to the Kullback-Leibler distance D(-) between probability distributions with and without
the target, for a fixed small probability of false alarm:
where the asymptotic equality symbol f(N) # g(N) means that lim N#
The Kullback-Leibler and Cherno# distances are related by the formulas
d
ds
d
ds
The direct relationship to P f , P miss and P e makes the Kullback-Leibler and Cherno# distances
an appropriate choice for obtaining performance bounds. To illustrate these concepts,
consider our simple hypothesis-testing problem based on the Gaussian model in Sec. 2.2, in
the absence of compression. In this case, the distances (11) and (15) take the simple form
SNR.
Hence for Gaussian data, both the Kullback-Leibler and Cherno# distances are proportional
to SNR. For non-Gaussian data (such as our compressed data), there is no direct relationship
between SNR and detection performance. We shall shortly see that the distances (11) and
can still be conveniently evaluated in problems where data compression takes place. We
first examine conditions under which (11) and (15) give tight bounds on target detection.
4 Asymptotic Expressions
The Cherno# bounds (12), (13) and (14) on P f , P miss and P e hold for any distribution
of the data and any sample size N . In many problems, N is large, the data contains
many independent components (see Sec. 2.4), and the central limit theorem applies to the
distribution of the log likelihood ratio. The results in Sec. 3 can then be strengthened
we refer the reader to Van Trees [17, Ch. 2.7] for a lucid exposition of the main
ideas and results. The first fundamental result is that the quantities -
are in fact asymptotic to max s#(0,1) D s (-p 0 , -
While this gives a precise exponential
rate for the convergence of this probabilities to zero, these results can be further strengthened
using asymptotic integral expansion techniques. This yields exact asymptotic expressions
for Specifically, define for notational convenience
and let - # be the first and second derivatives of -(s). Then, for large sample
size, there exists s # (0, 1) such that
. The exponential factors in (19) and (20) are equal to the upper bounds
in (12) and (13), but the central-limit-theorem analysis provides a multiplicative factor that
can be significant. If the prior probabilities of H 0 and H 1 are equal, one can combine (19)
and (20) to obtain the following asymptotic approximation to
e -(s) . (21)
For the Gaussian model above, maximization of (18) with respect to s gives the optimal
Cherno# exponent
e -SNR/8 , (22)
which holds for large SNR.
The applicability of these asymptotic conditions to target recognition is examined next.
5 Bounds for Target Detection Without Nuisance Parameter

We first consider Detection Problem 1 in Sec. 2.6, and derive performance bounds for the
optimal LRT detector (4). The logarithm of the likelihood ratio (6) is the sum of the
marginal log likelihood ratios
L n for each transform coe#cient. Hence the Cherno# and
Kullback-Leibler distances in (11) and (15) are additive over the N transform coe#cients:
This additivity property simplifies the analysis and design of some systems using (23) or
(24) as the optimality criterion. For instance, the paper [14] shows how to optimally design
transform coders subject to bit rate constraints using (23) as the performance measure, and
the thesis [15] compares the performance of wavelet and DCT coders using such performance
measures. The additivity property of Cherno# and Kullback-Leibler distances applies to any
problem in which the data can be partitioned into independent components (see Sec. 2.4).
5.1 Example
To investigate the applicability of the above theory to target detection, we conducted experiments
using a database of T62 tank images generated using the PRISM 3 simulation package.
The images were corrupted by i.i.d. Gaussian sensor noise, as described in Sec. 2.2. Fig. 1
shows one such image at orientation along with noisy sensor data I D
dB). The noisy image data were compressed using a wavelet coder with Daubechies' length-4
D4 wavelet filter, four decomposition levels, and dead-zone scalar quantizers [16]. The dead
zone of these quantizers was twice the step size. Under this model, the received transform
coe#cients - c D
are independent. Their distributions -
p 1,n under hypotheses H 0 and
were computed by numerical integration of the Gaussian distribution for the unquantized
coe#cients c D
n over all quantization bins. Bit rates were estimated using the first-order
entropy
for the data in the presence of the target. (The entropy of the compressed image data in
the absence of a target is slightly lower.) Both hypotheses H 0 and H 1 were assumed to be
3 Courtesy Dr. Alvin Curran, Thermo Analytics, Calumet, MI.
equally likely. We used the optimal LRT detector for the compressed data:
We analyzed the e#ects of compression (measured by the bit rate of the compressed
data) on detection performance. The probability of error P e is guaranteed to decrease with
bit rate, because - ln P e is in the Ali-Silvey class. Fig. 5 compares three estimates of the
probability of error P e . The first estimate was computed using Monte-Carlo simulations with
di#erent noise realizations. The accuracy of this estimate is very high due to large number
of independent experiments performed. The second estimate, -
P e,s is computed using the
Cherno# upper bound (14) evaluated at bound). The motivation
for choosing is that this choice is quasi-optimal, see Fig. 6. For large bit rates,
quantization e#ects are negligible, and P e tends to the probability of error for unquantized
data. Since those data are Gaussian-distributed, an exact expression for P e is available. For
equal priors (-
z e -x 2 /2 dx is
Marcum's Q-function. For large SNR, we have P e # 2
# /SNR exp(-SNR/8) [5]. From
(18), the Cherno# distance is maximum at and so the Cherno# bound (14) is2 exp(-D s #(-
exp(-SNR/8). This bound is approximately four times larger than
the actual P e at high bit rates. At lower rates, the upper bound is slightly less conservative.
The third estimate of P e in Fig. 5 is discussed next.
5.2 On the Accuracy of Asymptotic Cherno# Approximations
In order to improve the upper bound (14), it is tempting to use the asymptotic expression
(21) for the Cherno# bound. Since this bound was established using central limit theorem
arguments, we expect it to be applicable, when the log likelihood ratio is the sum of N independent
components, and N is large. However, in the problem of Sec. 5.1, these components
(-c D
n ) are not identically distributed, so the validity of (21) hinges on whether the central
limit theorem for independent, but not identically distributed components, applies. Roughly
speaking, this requires that any individual component ln -
L n in the sum of log likelihood ratios
be small relative to the sum; more precisely, it is su#cient that the Lindeberg condition
holds [18, Ch. XV.6].
The Lindeberg condition is approximately satisfied for the application in Sec. 5.1, so the
asymptotic expression (21) is quite accurate, as shown in Fig. 5. In general, the Lindeberg
conditions can be expected to approximately hold for high-resolution imaging sensors, or
when multiple copies of the same scene (with di#erent noise realizations) are available. These
conditions are not likely to be satisfied in applications involving targets with relatively few
pixels on target. Even for a relatively large target like the one in Fig. 1, the Lindeberg
conditions do not hold well at very low bit rates, because most transformed coe#cients
are quantized to zero, and the log likelihood ratio is dominated by only a few significant
components.
6 Bounds for Target Detection With Nuisance Parameter

We now consider a more complicated scenario involving nuisance parameters # modeled as
random, with prior #. Under H 1 , the distribution of the data -
I D is the mixture
distribution (7).
As in Sec. 5, the performance of the optimal detector can be evaluated using Cherno#
bounds, which are tight under some conditions. However, here image coe#cients are no
longer independent, and the log likelihood is no longer additive over these coe#cients. Hence
the distances are given by N-dimensional integrals which in general cannot be evaluated
analytically. Fortunately, it is possible to derive bounds on these information-theoretic
distances that are useful and tractable performance measures.
6.1 Upper Bounds on Ali-Silvey Distances
To circumvent the di#culty of evaluating exact distances, we can compute an average dis-
tance, averaged over #, which turns out to be an upper bound on the exact Ali-Silvey dis-
tance. From (3), the likelihood ratio is the weighted average of the conditional likelihood
ratios L(-c D
p1 (-c D
L(-c D
|#) d#. (27)
From Jensen's inequality [9], we have
L(-c D
|#) d#
C(L(-c D
|#) d#
for any convex function C(-) and any pdf #). Hence for any Ali-Silvey measure of the form
L(-c D
|#) d#
|#) d#
where the inequality holds because f is increasing, and the last equality follows from the
definition of Ali-Silvey distances in (8). The result (28) also applies if f is decreasing and C
is concave.
First we apply (28) to - ln P e , which as discussed in Sec. 3 is an Ali-Silvey distance. In
this case, P
where P e|# refers to the probability of error given #, and has been evaluated in Sec. 5.
According to (29), the probability of error is at least equal to the average of the conditional
probability of error.
For the Cherno# and Kullback-Leibler distances in (11) and (15), (28) yields
There are two important points to be made here. First, even if the performance index
was independent on #, (28) would in general not be satisfied with equality.
A much stronger condition would need to be satisfied, namely, L(-c D
|#) would have to be
independent of # for each - c D , implying that # plays no role in the inference. Hence equality is
achieved in (28) only in trivial cases. Second, for nonlinear functions f , the expression (28)
is not the same as the average distance # d(-p 0 , -
increasing
(resp. decreasing) and C is convex (resp. concave), Jensen's inequality implies that the
average distance is an upper bound on (28):
In particular, the inequality (31) applies to Cherno# distances. In this case, (28) can be
further upper-bounded by the average distance # D s (-p 0 , -
We refer to (28) as
the "average f -1 distance" upper bound.
Next, let us see how the average bound on Cherno# distance relates to P e . From (14),
Because the inequalities do not go in the same direction, the right-hand side of (32) can only
serve as an approximation to P e .
6.2 Lower Bounds on Ali-Silvey Distances
We also explore the possibility of having simple lower bounds on Kullback-Leibler and Cher-
no# distances that provide upper bounds on P f and P e . Lower bounds on Cherno# distances
yield upper bounds on P e , and hence unbeatable bounds on the performance of any target
detection algorithm. The minimization of a distance d(-p 0 , -
possible mixture distributions
of the form (7) is illustrated in Fig. 10a. One might conjecture that the
distance is lower-bounded by the distance corresponding to the least favorable #:
worst )), where # worst
However, this inequality does not hold in general 4 . Likewise, the inequality P e # P e|#worst
does not hold in general. Still, the concept of least-favorable # plays a central role in the
asymptotic analysis of Sec. 6.3 below, as well as in minimax detection [21, Ch. 9]. From the
results in Sec. 5, we immediately obtain an upper bound on the probability of error of the
e|#worst # - 1-s
worst
6.3 Asymptotic Expressions
Significant simplifications arise in an asymptotic scenario, as the asymptotic expressions for
probability of error are dominated by the least-favorable #. The classical paper [22] presents
similar results in a closely related context. To understand the basic idea, consider the simple
case of a prior distribution concentrated at two values # 1 and # 2 , where D s (-p 0 , -
. For large N , the distributions -
and -
increasingly well separated, so their support sets become essentially
disjoint. Then
functional #) of the prior #, and the greatest lower bound on #) is
obtained by minimizing #) over the (convex)
set# of all priors. For the conjecture to be true, the
minimum would need to arise at an extremal point of the
set# This property would hold if #) was
concave, but generally does not hold for convex #) [20]. However, similar arguments show that the most
favorable prior # is a mass distribution. The resulting upper bound on d(p 0 , very useful though,
because we have already established the tighter upper bound (31).
A formal proof of this result is beyond the scope of this paper; see [22] for an example of such
analysis. A similar result holds if the prior distribution is concentrated at an arbitrary finite
number of points, and even for continuous priors, under some smoothness assumptions. In
other words, the inequality (33) holds with asymptotic equality for Cherno# distances:
worst )), where # worst
A tractable asymptotic approximation to P e is then obtained via (21), where
6.4 Example
In this section, we compare the bounds in Secs. 6.1 and 6.2 and the asymptotic approximation
(35) in Sec. 6.3 with the actual P e . Experiments were performed on the same database as in
Sec. 5.1. Again, the images were corrupted by i.i.d. Gaussian sensor noise and compressed
using the same wavelet coder. From (4) and (27), the optimal LRT takes the form
#) d#
where the prior #) is uniform. In our implementation, we approximated the integral from
by a summation over 36 orientations 0 We used the LRT above
and Monte-Carlo simulations to accurately estimate P e . We also evaluated the average
approximation (32) to P e , the upper bound (34) on the probability of error of a minimax
detector, and the asymptotic expression (21) (35) for P e .
Figs. 7 and 8 show these quantities as a function of bit rate for tank and truck imagery
at average SNR of 14 dB. Bit rate was computed using the first-order entropy (25), where
approximated by an average over 36 orientations, as described
above. We found that the average approximation (32) to P e is relatively accurate for both
tank and truck imagery. On the other hand, the upper bound (34) on P e is very loose for
the tank data as compared to the truck image data. The asymptotic approximation (21)
(35) is remarkably accurate for the truck data, but is o# by a factor of approximately two
for the tank data. This can be explained by examining Fig. 9, which shows SNR (which
is proportional to the Kullback-Leibler and Cherno# distances in the case of uncompressed
Gaussian data) as a function of the orientation parameter #. Clean tank images at certain
angles have very low energy content. These are seen as negative spikes in the tank image
SNR curve. The Cherno# distance for these worst-case angles give an overly conservative
upper bound on P e . Moreover, the spikes are very narrow, so convergence to the asymptotic
approximation (35) is slow. On the other hand, the clean image energy content does not
vary much with orientation for truck imagery, so the lower- and upper-bound curves are
relatively close, and the asymptotic approximation (35) is accurate. The variability of SNR
with target orientation is shown in Fig. 9 for tank and truck imagery.
Though the average approximation to P e in (32) is close to P e for the tank imagery, this
may not be true in general, as discussed in Sec. 6.1. The tightness of these bounds depend
on the variation of SNR with orientation (see Fig. 9).
7 M-ary Hypothesis Testing: Multiple-Target Case
Until now, we have considered a binary detection problem in which the receiver decides
whether a known target is present or not. This analysis can be extended to the case where
the alphabet of possible targets consists of M # 2 possible targets. This includes our binary
detection problem as a special case, in which 2, and the second hypothesis is a null
hypothesis. Using notation similar to that in Sec. 2, we assume that for there
are nuisance parameters # i # i associated with target type i, and let I i
i with nuisance parameter # i # i . Hence, the detection problem in the transform domain
can be formulated as an M-ary hypothesis test:
I D
I D
The parameters # i are modeled as random with priors # i
the data -
I D follow a mixture distribution -
I D ). Information-theoretic distances between
pairs of such distributions can be derived using methods similar to the binary case.
For the M-ary hypothesis test in (37), the optimal decision under the minimum-probability-
of-error rule is -
I D
I D )], where - i is the prior probability
for hypothesis H i . The probability of error P e , in this case, can be upper bounded using the
union-of-events bound [23]:
where is the probability of deciding H j when the correct hypothesis was H i , and
I D )>- i -
I D )|H
I D )>- j -
I D )|H j
represents the probability of error for a binary hypothesis test between H i and H j . The
inequality (38) follows from
I D ))|H i
I D )>- i -
I D )|H i ], (41)
and (39) follows from the Cherno# bound in (14). The Cherno# distance between distributions
takes the form
I D
I D )
I D )
I
I D )], 0 < s < 1,
I D
I D )/-p i ( -
I D ) is the ratio of the pdf's under hypotheses H i and H i .
The right-hand side of (39) gives an upper bound on P e in terms of Cherno# distances.
For simple hypotheses, the sets # i are singletons, and analysis similar to Sec. 5 applies. The
asymptotic tightness of the Cherno# bound on P e (i, j) for this case holds in the qualified
sense discussed in Sec. 4. Likewise, inequalities (38) and (41) are tight if all the hypotheses H i
are "far apart" from each other. Specifically, under some conditions (such as i.i.d. data), one
pair of hypotheses (i # , dominates the bounds on P e in (39), asymptotically as N #.
The pair (i # , is the one that has least Cherno# distance D s (-p i , -
Proposition 7.1 below shows that d(-p i , -
satisfies an inequality analogous to (28). The
proof of the proposition is given in the appendix.
Proposition 7.1 Let d(-p i , -
I D ))) be an Ali-Silvey distance between distributions
I D
I D )/-p i ( -
I D ) is the likelihood ratio between hypotheses
j depend on random parameters # i # i and # j # j with respective
priors # i
# . (42)
The assumptions of Proposition 7.1 hold for both Cherno# and Kullback-Leibler distances
in (11) and (15). Using the average upper bound (42) on Cherno# distance in (39),
we obtain an average approximation on P e similar to that in Sec. 6. We also note that
it is di#cult to derive nontrivial lower bounds on d(-p i , -
for the reasons described in
Sec. 6.2. Finally, under asymptotic conditions, P e is given by (21) where the exponent
takes an asymptotic form similar to (35):
The distance d(-p i , -
corresponding to mixture distributions -
in Fig. 10b. The probability of error is asymptotically determined by the worst-case
pair of angles corresponding to mass distributions # i and # j .
8 Conclusion
We have developed a systematic framework in which to analytically characterize target recognition
performance and facilitate optimization of system parameters. Probability of error
is usually an intractable function of system parameters, but information-theoretic distances
like Kullback-Leibler and Cherno# distances can be advantageously used as performance
measures. In some cases, simple analytical expressions can be obtained. These distances
provide asymptotically tight bounds on P e . We have studied and qualified the nature of the
gap with respect to asymptotic performance in a practical target recognition problem. We
reemphasize that our methodology is directly applicable to a broad class of object recognition
problems. In the presence of nuisance parameters such as target pose or thermodynamic
state, expressions for information-theoretic distances are often unwieldy, but convexity arguments
show that average distance is an upper bound on the true distance; and asymptotic
arguments provide simple asymptotic approximations.
Due to their simplicity, these expressions provide insights into a problem that we have
not dwelled upon: the optimal design of target recognition parameters such as parameters
of a lossy image compression algorithm. This provides a theoretically motivated alternative
to heuristic design techniques used in the target recognition literature [8]. This issue needs
to be explored in detail and is a challenging area for future research.

Acknowledgement

. The authors thank Dr. Aaron Lanterman and Mark C. Johnson
for reading a draft of this paper and making valuable suggestions.
A Proof of Proposition 7.1
We derive the upper bound (42) in two steps. First, we define
I D
I D
I D )
,
I D
I D )
I D
. (44)
we have from (44), L ij ( -
I D
I D
Hence
the first step follows directly from (28):
I
I D
# . (45)
From (44), L ji ( -
I D
I D )/-p j ( -
I D
I D
the expectation in the right-hand
side of (45) can be written as
I D
I D )C(L
I D
I D
I D )
I D
I D
I D
I D
I D
I D
function g(-). It can be shown that if C(x) is convex
for . Hence the argument of E j [-] in (46) is a
convex function of L ji ( -
I D
implies that L ji ( -
I D
I D
I D
I D
I D
I D
Hence
from (28), (46) can be upper bounded by averaging over
I D
I D
I D
I D
I D
where the equality follows by repeating the steps of (46) in reverse order with L ji ( -
I D
replaced by L ji ( -
I D
Equations (45) and (47) lead to (42). #



--R

"Aided and Automatic Target Recognition Based Upon Sensory Inputs from Image Forming Systems,"
IEEE Transactions on Image Processing
"Automatic target recognition via jump-di#usion algorithms,"
"Hilbert-Schmidt Lower Bounds for Estimators on Matrix Lie Groups for ATR,"
An Introduction to Signal Detection and Estimation.
Boston: Academic Press
"Bounds on Shape Recognition Performance,"
"Data Compression Issues in Automatic Target Recognition and the Measuring of Distortion,"
Elements of Information Theory.
"A general class of coe#cients of divergence of one distribution from another,"

"Optimal quantization for signal detection,"
"Applications of Ali-Silvey distance measures in the design of generalized quantizers for binary decision systems,"
"Optimal Design of Transform Coders for Image Classification,"
"Image recognition from compressed data: performance analysis,"
A Wavelet Tour of Signal Processing
Modulation Theory
An Introduction to Probability Theory and Its Applications
Large Deviation Techniques in Decision
Convex Analysis

" Information-Theoretic Asymptotics of Bayes Meth- ods,"
New York: McGraw-Hill
--TR

--CTR
Lavanya Vasudevan , Antonio Ortega , Urbashi Mitra, Application-specific compression for time delay estimation in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
M. E. Shaikin, Statistical Estimation and Classification on Commutative Covariance Structures, Automation and Remote Control, v.64 n.8, p.1264-1274, August
object recognition;multisensor data fusion;imaging sensors;performance metrics;data compression;automatic target recognition