Selected Research Projects
1. Decision Theory and Statistical Tests
1.1. Minimax-Invariant Regret Tests
1.2. Asymptotic Optimality in Sequential Testing Multiple Hypotheses for General Non-i.i.d.
Models
A substantial part of the development of sequential hypothesis testing in the last three decades has been directed towards proving asymptotic optimality of modifications of sequential probability ratio test and improving the performance of tests for many simple and composite hypotheses when observations are independent and identically distributed (i.i.d.). In this case, log-likelihood ratios (LLRs) of hypotheses are random walks and this fact is essentially used in theoretical study. However, in many practical problems the " i.i.d." assumption is not fulfilled. Also in most applications there is a prior uncertainty which results either in incomplete knowledge of distributions (nuisance parameters, parametric uncertainty) or in complete ignorance of underlying distributions (nonparametric uncertainty). Thus, hypotheses become composite and one needs to apply invariant sequential tests or nonparametric sequential tests based on, say, rank-order statistics. In such a case even if observed data may be considered as i.i.d. random variables, the invariant versions of LLRs (constructed on a maximal invariant) fail to be random walks.
In the present work we investigate the asymptotic problem of sequential testing of finitely many composite hypotheses for statistical models with nuisance parameters assuming that the probabilities of errors are small. An observed stochastic process is assumed to be of a very general structure. It is shown that certain sequential tests asymptotically minimize not only expected sample size but also all the moments of the stopping time distribution under fairly general conditions. These conditions allow us to consider models that include correlated and nonhomogeneous processes observed either in discrete or continuous time. The considered sequential tests are based on Markov "accepting" and "rejecting" times for hypotheses and, in essence, are specific combinations of one-sided sequential probability ratio tests. The conditions of asymptotic optimality are formulated in terms of r-quick convergence (t -> infinity) of LLRs normalized to f(t), where f(t) is a fairly general, non-negative, increasing function and t is a time parameter. A general solution is illustrated by particular examples which are of importance for various practical applications.
1.3. Asymptotic Optimality in Quickest Change-Point Detection Problems
The problem of rapid detection of abrupt changes in stochastic systems and processes is of importance for a variety of applications such as signal and image processing, quality control engineering, computer intrusion detection, chemical or biological warfare agent detection systems, failure detection in various systems, target detection in surveillance systems, etc. In all these applications sensors monitoring the environment take observations that undergo a change in distribution in response to a change in the environment. The change occurs at an unknown point in time, and the practitioners’ goal is to detect it as quickly as possible, while avoiding frequent false alarms.
There are several thrusts of research that are outlined below.
1.3.1. General Bayesian Theory of Quickest Change Detection
The optimal detection procedure for detecting changes in independent and identically distributed (i.i.d.) sequences in a Bayesian setting was derived by Shiryaev in the 1960s. However, the analysis of the performance of this procedure in terms of the average detection delay and the average probability of false alarm (PFA) has been an open problem. We develop a general asymptotic change-point detection theory that is not limited to a restrictive i.i.d. assumption. In particular, we investigate the performance of the Shiryaev procedure for general discrete-time as well as continuous-time stochastic models and for an arbitrary prior distribution of the change point in the asymptotic setting, where the false alarm probability approaches zero. We show that the Shiryaev procedure is asymptotically optimal in the general non-i.i.d. case under mild conditions. We also show that the two popular non-Bayesian detection procedures, namely the Page and the Shiryaev-Roberts-Pollak procedures, are generally not optimal (even asymptotically) under the Bayesian criterion. The results of this study are shown to be especially important in studying the asymptotics of decentralized change detection procedures.
In addition, we consider a less conventional approach where the constraint is imposed on the global, supremum false alarm probability rather then on a traditional average PFA. An asymptotically optimal Bayesian change detection procedure is proposed and thoroughly evaluated as the global PFA approaches zero. In essence, the proposed procedure is nothing but a Shiryaev test with a curved, increasing in time boundary. The asymptotic optimality results hold not only for i.i.d. data models but also for general, non-i.i.d. stochastic models, whenever a log-likelihood ratio process for prechange and postchange hypotheses obeys the strong law of large numbers with a certain rate of convergence.
1.3.2. Optimality of Multichart Change Detection Tests
We study (sequential) multichart change detection procedures, such as multichart CUSUM and Shiryaev- Roberts detection tests, for detecting changes in multichannel systems and problems with finitely many parameter values. More specifically, we are interested in the following multipopulation (or “multichannel”) generalization of a conventional change-point detection problem. Suppose there are N mutually independent populations. At an unknown time a change occurs, and one of the populations (and only one) changes its statistical properties. The goal of a statistician is to detect this change as rapidly as possible while maintaining the false alarm rate (FAR) at a given (low) level.
We show that the N-CUSUM and N-Shiryaev-Roberts detection procedures are asymptotically minimax optimal (i.e., minimize the worst case average detection delay) for low FAR as either the average run length (ARL) to false alarm goes to infinity or the local probability of false alarm (PFA) goes to zero. This result is valid not only for a traditional i.i.d. case but also for general stochastic models when populations are independent.
1.3.3. Asymptotic Solution to a Multidecision Change-Point Problem
The following multidecision quickest detection problem is considered. There are N independent populations
which are either statistically identical or the change occurs in one of them at unknown point in time.
It is necessary to detect the change in distribution as soon as possible (after it occurs) and indicate which
population is “corrupted.” The rate of false alarms and misidentification rate should be controlled by given
levels.
It is known that in the case of one population, the CUSUM detection procedure of Page (1954) and the
randomized Shiryaev-Roberts detection procedure proposed by Pollak (1986) minimize the expected detection
lag for a given false alarm rate. On the other hand, it is known that the Armitage-Lorden-Tartakovsky
type multidecision sequential probability ratio test asymptotically minimizes the expected sample size when
the probabilities of wrong decisions are small. Based on these results we propose multihypothesis versions
of the Page and Shiryaev-Roberts procedures and prove that they are asymptotically optimal as the false
alarm rate is low and the probabilities of misclassification go to zero. Specifically, it is shown that under
certain conditions the proposed detection/identification procedures asymptotically minimize the trade-off
between any positive moment of the detection lag and the rates of false alarms and misclassification in the
worst case scenario. At the same time the corresponding sequential detection/identification procedures are
computationally simple.
1.3.4. Asymptotic Exponentiality of Run Length to False Alarm in Change Detection Problems
A conventional measure of the FAR in change-point detection problems is the average run length (ARL) to false alarm. An important question is “Why is the ARL to false alarm a good performance metric of the FAR?” In order to answer this question we prove that suitably standardized stopping times of several conventional change detection procedures are asymptotically Exp(1) distributed when the ARL goes to infinity. It is shown that for CUSUM and Shiryaev-Roberts procedures this result is a particular case of a more general result for weak convergence and convergence of moment generating functions of first exit times associated with nonnegative Harris-recurrent Markov processes.
Figures 1(a) and 1(b) show the logarithm of the empirical (MC estimates) survival functions logP(N >
y) for the CUSUM and Shiryaev-Roberts procedures, where N is the normalized by the ARL corresponding
stopping time, along with the logarithm of the exponential probability plot log e−y = −y. These figures
correspond to the exponential example where the change occurs from Exp(1) to Exp(1/(1+q)) and q = 3.
The quantile-quantile plots (QQ-plots) for the stopping times are shown in Figures 2(a) and 2(b). These
figures show that the exponential distribution approximates the distributions of the stopping times very
well. It is seen that the exponential approximation works very well already for ARL = 120 − 160. When
considering that in practical applications the values of the ARL to false alarm usually range from 300 and
upwards, the exponential distribution seems to be a perfect fit.
2. Information Fusion in Distributed Decentralized Systems
It is assumed that there is a multisensor distributed system that, based on the information from all sensors
(generally compressed), should make a decision. We consider both hypothesis testing and change detection
problems. Both scenarios are important for a variety of applications including detection and recognition of targets by multiple-resolution-element radar and infrared systems, rapid detection of intrusions in computer
networks, etc.
In the former case (testing hypotheses), we consider a distributed multisensor system in which each sensor tests a finite number of composite hypotheses in a sequential manner. Then the decisions are transmitted to a fusion center, which combines them to improve the performance of the system. First, we study the behavior of an invariant sequential test for many composite hypotheses assuming that distributions of observations under each hypothesis are not exactly known due to the presence of nuisance parameters. In particular, we show that, under general conditions, the proposed sequential test is asymptotically optimal in the sense that it minimizes any positive moment of the stopping time distribution when error probabilities are small. We then use a non-sequential fusion rule for fusion of local decisions. This fusion rule waits until all the local decisions in all sensors are made and then fuses them. It is optimal in the sense of minimizing the average probability of error or the maximal probability of error. Finally, general results are applied to the problem of target detection in a multisensor, multiresolution system. We consider two statistical models which frequently arise in the target detection area. The first model is related to the detection of a non-fluctuating target in the presence of clutter with unknown mean and variance. The second problem is detection of a slowly fluctuating target in white Gaussian noise with unknown variance.
The latter case deals with quickest change detection in multisensor distributed systems. In the conventional
formulation of the change-point detection problem, there is a sequence of observations whose
distribution changes at some unknown point in time, and the goal is to detect this change as quickly as possible,
subject to false alarm constraints. It is known that in the i.i.d. case, Page’s CUSUM procedure and the
Shiryaev-Roberts detection procedure minimize the expected detection delay, subject to a constraint on the
average run length (ARL) to false alarm. In this research, we present effective decentralized detection procedures
for the multisensor situations where the information available for decision-making is spread across
a set of geographically distributed sensors. We present asymptotically optimal procedures for two scenarios.
In the first scenario, the sensors send quantized versions of their observations to a fusion center where the
change detection is performed based on all the sensor messages. In the second scenario, the sensors perform
local change detection using either CUSUM or Shiryaev-Roberts procedures and send their final decisions to
the fusion center for combining. We show that the proposed decentralized procedures for the latter scenario
have the same first order asymptotic performance as the centralized CUSUM or Shiryaev-Roberts procedures
that have access to all of the sensor observations. We also present numerical results for two examples
involving Gaussian and Poisson observations.
The general results are applied to the two important application areas—target detection in surveillance
systems and attack/intrusion detection in distributed computer networks. Experimental results show that the
proposed detection methods are highly efficient.
3. Speech Recognition and Speaker Identification
3.1 A New Algorithm for Initialization of the HMM Learning
One of the major problems in speech recognition and speaker identification is the development of effective learning procedure to estimate parameters of the model based on training data. Many techniques have been proposed for the solution of this problem. Among them is the generalized K-means segmental algorithm (L. Rabiner and B. Juang) which uses two stages: optimization and estimation. For the hidden Markov model (HMM), the optimization is carried out by using the generalized Viterbi algorithm which finds an optimal sequence of states starting with some initial estimates of the model parameters (initialization). It is known that this algorithm is quite sensitive to initialization. Our experiments show that the commonly used "uniform presegmentation" is ineffective for many speech recognition problems. We have developed a new initialization algorithm for the left-to-right HMMs based on change-point detection method. From the statistical standpoint any state transition in the HMM leads to changes in stochastic properties of the observed data. The idea is very simple - to detect these changes as quickly as possible using sequential change-point detection algorithm. Then the detected change points are used as an initial segmentation and HMM parameters are estimated on the basis of obtained presegmentation. We assume Gaussian mixture model for observed data in each state of the HMM. Simulation and experiments with speech databases show that with such a segmentation the Viterbi algorithm almost always estimates the true trajectory very accurately. It is proved that the proposed technique guarantees convergence of the iterative learning algorithm to the true model. In addition, our algorithm does not require exact knowledge of the number of HMM states which traditionally is assumed to be fixed in advance. It detects transitions and determines the number of states in the course of learning.
3.2 An Asymptotically Minimax Speaker Identification Algorithm
The speaker identification problem is to classify a speech signal into one of V
(V>=2) reference speakers. From the statistical point of view this task may be
formulated as a multi-decision problem (testing many composite hypotheses). There are two
major factors that affect performance of speaker identification algorithms. The first one
is the size of speaker population. The second factor is the presence of noise and signal
degradation (fluctuations) imposed by using remote microphones, by transmission over
telephone lines, etc. Recently D. Reynolds (1995) examined the performance of
text-independent speaker identification for different speaker population sizes (up to 630)
for clean, wideband, and telephone speech. The results of this study show that the
influence of the number of speakers is extremely strong for the telephone (noisy) speech.
In fact, with telephone network degradations, the probability of true identification (PTI)
essentially decreases as V increases. For instance, with the 630 speakers, there is
a difference of 39% between PTI for clean and noisy conditions. This is not surprising and
could be expected since noise addition and signal fluctuations generate mismatches between
training and testing data.
To reduce the influence of noise and degradations we propose the robust adaptive statistical algorithm based on the minimax regret approach developed recently by Tartakovsky (1995) for general statistical models with nuisance parameters. In contrast to the conventional approach which exploits estimates of the model parameters based on training data only, this algorithm is based on joint use of training and testing sequences to obtain a more reliable adjustment of model parameters.
We applied this idea to the speaker identification problem with minimum overall probability of wrong identification. The developed adaptive classifier exploits the ``constrained'' maximum likelihood estimators of unknown parameters based on both training and testing data. It is shown that this algorithm is asymptotically minimax as the number of test observations is big enough and robust under given constraints on mismatch between testing and training conditions. Specifically, it minimizes the probability of error in the worst case with respect to prior probabilities of hypotheses and given constraints on variation between models in testing and training phases, as the size of testing sample goes to infinity. The performance analysis shows that the algorithm is especially effective in the case where mismatch between testing and training conditions is not arbitrarily large, but allows only restricted deviation. The proposed adaptive identification algorithm based on joint unsupervised and supervised learning is much more robust as compared to the conventional algorithm for noisy speech.
3.3 A Nonparametric Method for Speaker Identification
Perhaps the most interesting and difficult speaker recognition problem corresponds to the case where one wants to identify a speaker in a given pool in the presence of impostors. This represents the combination of speaker verification and identification. There are training data which may be used to determine the models for speakers in the pool but there are no training data for impostors. We consider a simpler problem when a particular target speaker should be tested against an impostor (i.e., binary decision problem). We formulate this problem as a nonparametric two-sample problem and use a multivariate permutation rank order test.
Specifically, let X = (X1, ..., Xn) and Y =( Y1, ... Ym) be testing and training sequences, respectively. Here Xj = (X1,j, ..., Xp,j) and Yj = (Y1,j, ... , Yp,j) are vectors of cepstral or wavelet coefficients obtained in the j-th frame. If the test utterance corresponds to the target speaker, then the hypothesis "H: FX(z) = FY(z) for all z" is true, where FX and FY are multivariate c.d.f. of Xk and Yk which are supposed to be unknown. If the test utterance corresponds to an impostor, this equality is violated. To build the test we first form ranks of Xn,j in the combined sample (Y, X), then we use linear rank-order statistic which is sensitive to location changes. Based on this statistic we are able to construct a similar test of a fixed size, since the conditional distribution of this statistic, under a permutational probability measure generated by (n+m)! permutations of the columns of the rank matrix, has a completely specified form. Next, in our case m > 64, n > 300, p = 10-15, and hence one can use normal approximation. Due to this fact it is not necessary to use random threshold; it may be determined in advance.
The results of the experiment with 1996 speech data sets show that the nonparametric multivariate rank-order test has the performance close to that of the test based on Gaussian mixture model with 50-100 mixtures. However, computationally the nonparametric test is much simpler.
Click here for more information
4. Selected Applications
4.1. Network Security: Anomaly-based Intrusion Detection System
During the past few years, considerable interest in the field of defense against cyber-terrorism in general, and network intrusion detection in particular, has been induced by a series of external and internal attacks on important corporate and governmental networks, server clusters, and other network resources. This interest has been further fueled by external distributed denial-of-service (DOS) attacks against several well known Internet servers such as Yahoo, Amazon, eBay, and E.Trade. Other examples are Internet-wide worm attacks and stealthy attacks by intruders posing as regular users. Software allowing hackers to initiate many varieties of external (e.g., DOS and worm) and internal (e.g., Address Resolution Protocol Men-in-the-Middle (ARP MiM)) attacks is becoming more and more available and easy to use. The aforementioned attacks represent serious threats for information systems, causing failures and interrupting services to users. As a result, the defense against these serious threats is rapidly gaining importance.
A wide variety of intrusion detection methods have been proposed in the literature. Several of them analyze different data streams, such as data mining for network traffic, statistical analysis for audit records, sequence analysis for operating system calls, information retrieval and inductive learning. A number of defense methods have been proposed for dealing with DOS attacks. For example, SYN cookies, SYN defender, SYN cache, and SYN proxying can be used to counter TCP (Transmission Control Protocol) SYN flooding attacks. However, these defense tools are installed at the firewall of the victim server or inside the victim server and do not indicate the sources of the SYN flooding. Therefore, these tools have to use the expensive IP traceback to locate the flooding sources.
Existing intrusion detection systems (IDSs) can be classified as either Signature Detection Systems or Anomaly Detection Systems. Signature-based detection systems detect attacks by comparing the observed patterns of the network traffic with known attack signatures from a database. If the true attack belongs to the class of attacks listed in the database, then it can be successfully detected and, moreover, identified/classified. Anomaly-based IDSs compare the parameters of the observed traffic with legitimate network traffic. The attack is declared once a deviation from legitimate traffic is observed. Both classes of systems have certain pros and cons.
Our approach belongs to the class of anomaly IDS. Typically network intrusions (e.g., DOS, worm, port-scanning, and ARP MiM attacks) occur at unknown points in time and lead to changes in the statistical properties of certain observables. It is therefore intuitively appealing to formulate the problem of detecting attacks as a quickest change-point detection problem: to detect changes in statistical models as rapidly as possible (i.e., with minimal average delays) while maintaining the false alarm rate (FAR) at a given level.
The goal of this research is to show that recent advances in the change-point detection theory can be successfully applied in the design of anomaly IDSs for early detection of intrusions in computer networks. We show that the asymptotic theory that has been developed is useful in intrusion detection problems and allows for the development of efficient algorithms that are easily implemented and, at the same time, have certain optimality properties. This method is robust, does not have any computational overhead, and does not use expensive traceback.
Two basic nonparametric detection algorithms have been developed: (1) An adaptive nonparametric CUSUM algorithm sensitive to detection of changes in mean values (e.g., mean values of the number of UDP or ICMP packets), and (2) Binary CUSUM based on preliminary binary quantization (or “in-frame” detection) with subsequent application of the likelihood ratio-based CUSUM statistic. The first test is efficient when optimized, while the second one is optimal for binary data and has very minor loss in efficiency compared to the first optimized one (15-30%). In certain scenarios, however, the binary CUSUM test appears to be more efficient.
We present the results of testing the nonparametric CUSUM and binary CUSUM procedures’ abilities to detect a TCP SYN flooding attack based on real network traffic data collected and made available by the MIT Lincoln Laboratory (see http://www.ll.mit.edu/IST/ideval/ ). The attack consisted of three hijacked servers sending multiple TCP connections to a victim host. The goal of the attack was to prevent other hosts from connecting to the server by overloading its resources and those of the network. Resampling of the traffic was used to estimate the performance of the algorithms.
In the considered scenario, the mean increase was from approximately 12.5 to 16.04, while there was also decrease in the standard deviation of the observed packet numbers from 17.96 to 13.54. Since the binary CUSUM test is sensitive to changes not only in mean values but in variance as well, it performed best.
The plots in Figure 3 illustrate the typical behavior of the detection statistics for the nonparametric and binary CUSUM tests. It is seen that the statistics fluctuate not very far from the zero reflection barrier for the legitimate traffic but start drifting upward rapidly after the attack occurs. It is also seen that the binary CUSUM detection statistic has much less variability under the no-attack hypothesis, which results in lower threshold values for the same FAR. This is the second reason why the binary CUSUM test performed better than the nonparametric CUSUM test.
As we have previously hypothesized, the use of multichart tests is extremely important for detecting UDP, ICMP and TCP SYN flooding attacks. We now further verify this hypothesis, i.e., show that the proposed multichannel (multichart) detection procedures typically perform significantly better than singlechannel counterparts. To prove this fact we use several real data sets with real UDP and TCP SYN flooding attacks. Therefore, we may conclude that so far the need for multichart detection tests has been underestimated.
We used two data sets with the packet traces captured on SONET OC-48 links by CAIDA monitors. A bidirectional link from San Jose, CA to Seattle, WA that belongs to the US backbone Internet Service Provider (ISP) was monitored. The traces were collected by a Linux-based monitor with Dag 4.11 network cards and packet capture software originally developed at the University of Waikato and currently produced by Endace. We present a comparison between the single channel nonparametric CUSUM (SNP-CUSUM) and its multichannel counterpart (MNP-CUSUM) in terms of their performance metrics: Average Detection Delay (ADD) and FAR.
We now present results of the experiment that illustrate the performance of these algorithms for the
detection of a low intensity UDP flooding attack. Figure 4 shows the time-series of the total number of UDP
packets in a sample period 0.015 msec. It is seen that attack traffic is not distinguishable from normal traffic.
Closer, off-line examination revealed that this attack consists of sending a Trojan horse called trojan.dasda
from one source from port 10100 to one destination on port 44097. Trojan.dasda is a Trojan horse that can
download and execute remote files and open a back-door on an infected computer.
In the single channel case, no distinction is made based on the size of the packets. The pre-change
mean is 87 packets per sample period (pkts/sp) and the post-change mean is 94 pkts/sp. In the multichannel
case, packet sizes are subdivided into 13 separate channels (bins). The following is the range of packet
sizes that defines thirteen channels: {0-40, 41-60, 61-64, 65-70, 71-75, 76-80, 81-100,101-300, 301-500,
501-700, 701-1000, 1001-1300,1301-1500} bytes. The flooding attack occurs in the channel 7 with the prechange
mean 10.3 pkts/sp and the post-change mean 20 pkts/sp. Observe that during the attack the sender
sends twice as much packets of a particular size. Splitting into size bins and using multichannel detection
helps us to localize the attack and, therefore, to detect it more rapidly. To confirm this we have used
resampling techniques to obtain performance of both tests. The results show that the ADD is significantly
smaller in the multichannel case as compared to the single-channel case for the same FAR. For example, for
−log(FAR) = 7, the ADD for the MNP-CUSUM is 2 sec while for the SNP-CUSUM the ADD is 26 sec,
i.e., ADD is thirteen times larger in the single channel case.
In addition, the important practical aspect of the multichannel approach is that the channels may be interpreted as different populations, i.e., different kinds of attacks. This allows for the development of an easily upgradeable IDS that can be setup to detect various attacks at the same time. For instance, we can set up separate channels for simultaneous detection of UDP flooding, Smurf and SYN flooding attacks. We can also include a channel for detection of port scanners.
Finally, the efficiency of the developed MNP-CUSUM based IDS has been evaluated for the LANDER ISI/USC data sets that contain distributed DOS attacks. Click here to watch a clip with the results of detection of an ICMP DDOS attack.
Click here for further results from the previous research supported by DARPA
- Intrusion Detection
- Information Assuarance
4.2. Detection and Tracking of Low-Intensity Objects in Heavy Clutter
The problem of efficient clutter rejection is a challenge for space-based infrared (IR) and Space Tracking and Surveillance System (STSS) sensors with chaotically vibrating lines-of-sight (LOS) that have to provide early detection and tracking of missile launches in the presence of highly-structured cloud backgrounds. In such systems, the intensities of cluttered backgrounds due to solar scattering by clouds, aerosols and earth surface (ground, sea, etc.) or by IR airglow emissions are typically dozens and even hundreds of times greater than either sensor noise or the intensities of the targets to be first detected and then tracked. As a result, reliable target detection and subsequent tracking is impossible without clutter rejection to, or even below, the level of sensor noise.
Most existing clutter rejection technologies for unstabilized or mechanically stabilized platforms rely on spatial-only or simple differencing image processing methods. However, the results of our study show that even the best spatial-only filters as well as an industry standard differencing method are not efficient enough, especially in unfavorable conditions typical for applications of interest. Moreover, these filters cannot be combined with temporal processing in cases where clutter is nonhomogeneous in time due to platform vibrations (jitter), which is always the case.In this project, we argue that the level of clutter suppression required for reliable detection and tracking (20 dB and higher) can be achieved only by implementing spatial-temporal and/or space-temporal-spectral (i.e., multispectral) filtering rather than spatial filtering. Note that in order to make temporal processing and multispectral fusion efficient, clutter rejection algorithms must be supplemented by very accurate jitter estimation and scene stabilization techniques (i.e., super-stabilization) that compensate for platform vibrations and eliminate residual frame misalignment. Our image registration/stabilization techniques are entirely different from those previously used. Stabilization is performed iteratively in the course of clutter rejection, and the corresponding stabilization algorithm is a part of the clutter rejection system. We show that this novel approach is extremely efficient in applications of interest. Our spatial-temporal iterative method allows not only for very accurate interpolation but also for very accurate image reconstruction and, therefore, clutter suppression in a wide spectrum of conditions, including highly structured scenes characteristic for IR solar cloud clutter.
To address super-stabilization and super-rejection challenges, we use the following idea, which allows us to avoid the use of expensive equipment for “super-stabilization.” The idea is to use clutter itself for stabilization. Indeed, since clutter is typically highly correlated in time and changes slowly during certain periods of time (depending on weather conditions, season, etc.), substantial temporal changes in these intervals occur only due to jitter. Since clutter is normally much more intense than sensor noise, it can be effectively used for instability estimation and compensation. When the registration problem is solved, i.e., the scene is stabilized, we can build an effective spatial-temporal scheme for clutter rejection, in which case, clutter can be suppressed to the level of sensor noise or even lower. We develop novel statistical parametric and nonparametric spatial-temporal-spectral techniques for clutter suppression (CLS) and scene stabilization. The corresponding stabilization and CLS algorithms are robust since they are invariant to prior uncertainty with respect to clutter statistical properties and adaptive with respect to clutter variability. An important feature of the developed CLS algorithms is that they allow for reducing the cost of expensive mechanical stabilizers.
Extensive experiments presented below show that the proposed algorithm gives a substantial gain compared to the best existing spatial techniques as well as to the industry standard temporal differencing method. The results of simulations also show that any particular clutter rejection filter is not uniformly optimal for all possible conditions. Since environmental conditions may change quite dramatically, it is important to develop a bank of CLS filters along with a procedure of automatic selection of the best filter and its parameters for specifically encountered conditions. To this end, a reconfigurable CLS system that includes a bank of filters was developed. This system utilizes auto-tuning and auto-selection procedures for optimal configuration, reducing susceptibility to sensor vibrations and to changes in environmental conditions. These procedures use an overall system quality metric that is a function of the current sub-system performance indices, including expected SNR, clutter severity metric, false alarm rate, and tracking quality.
4.2.1. Space-Based Early Detection and Tracking System
The focus is on developing algorithms and software for SBIRS-HIGH (high-altitude and geostationary
orbits) that include adaptive clutter suppression (CLS), target detection and multiple target tracking for a
variety of observation conditions; tuning and optimization of these algorithms for particular scenarios; and
testing and validation through synthetic simulations and processing of real data. The primary goal is to
develop a viable prototype of the multiple target tracking system that includes a reconfigurable, adaptive
clutter suppression system that can be tested using a built-in simulator which mimics real environments.
The developed space-based system and corresponding software tools have the following functionalities and
capabilities:
1. Possibility of working with external data sets of interest for users (e.g., real data), which are presented
in a specific standard format.
2. Built-in generator of image sequences with moving point illumination sources (targets), background
clutter due to cloud cover, jitter due to platform vibrations, and sensor noise.
3. A bank of clutter suppression filters with a reconfigurable architecture and ability to compensate for
strong signals from bright targets and outliers.
4. Auto-tuning and auto-selection algorithms that allow for automatic selection of the optimal filter from
the bank for current conditions.
5. In-frame detection algorithms with stabilization of the false alarm rate.
6. Multitarget tracking algorithms, in particular:
(a) Change-point detection-based track initiation algorithms
(b) Identification of detections as belonging to existing tracks
(c) Forming new tracks and deletion of false tracks
(d) Change-point detection-based track termination
7. Preliminary target track classification based on parameters of a polynomial model in 2D space.
8. Performance evaluation (probability of detection, false alarm rate, tracking accuracy) for synthetic
data (physics-based models) and real data.
9. Graphical user interface (GUI) for visualization of the results of processing and for input data and
parameters.
A general block-diagram of the system with the corresponding data/signal processing flow is shown in
Figure 5. Note that the block-diagram does not show the GUI that is a centerpiece of the system. This
interface is being used as a part of a testbed to test the system performance for particular scenarios and to
visualize the results of data processing. Click here to see a clip that demonstrates detection and
tracking of two low-SNR point targets in heavy clutter.
4.2.2. Adaptive Spatial-Temporal and Multispectral Image Processing Methods for Clutter Removal, Scene Stabilization, and Target Tracking
The developed baseline CLS technique is based on a multi-parametric approximation of clutter that leads to an adaptive spatial-temporal filter. The “coefficients” of the filter are calculated adaptively according to the minimum distance algorithm. The adaptive spatial-temporal filter allows one to suppress any background, regardless of its spatial variation. It not only whitens the data but also corrects all translational distortions. Note that in this particular project, we are interested in geostationary staring IR sensors for which rotational distortions can be neglected. The algorithm can be modified to compensate for rotational and zooming distortions which is important in certain conditions, e.g., for low-earth and airborne platforms. Extensive experiments show that the proposed algorithm gives a substantial gain compared to the best existing spatial techniques as well as to the industry standard temporal differencing method.
Figures 6 and 7 illustrate the results of clutter suppression and target detection and tracking for different observation conditions. The following parameters were used in simulated experiments: Geostationary orbit; FOV (field-of-view) 128 × 128 pixels with pixel size 30 − 35 microradians; instantaneous FOV fluctuates around the reference FOV because of LOS vibrations (vibration amplitude about one-half of a pixel size); Clutter Suppression and Image Stabilization System with Adaptive Reconfigurable Architecture point targets move with constant velocity 0.5 − 1 pix/sec; frame rate 1 fps; Gaussian PSF. The efficiency of CLS algorithms and software have been demonstrated by processing of data sets obtained from the simulator (the imitation model of images) that takes into account generalized hardware/sensor parameters, clutter and LOS vibrations. We have simulated various scenarios under a variety of conditions.
Fig. 6 illustrates tracking of two weak targets with S(C+N)R = 0.1. In this example, the algorithm of auto-selection has chosen the Fourier filter as the best filter from the bank. This filter almost completely suppressed clutter (STD of residuals STD of sensor noise). Targets were immediately detected and tracked from the beginning to the end, as can be seen from Fig. 6(c). Fig. 6(b) shows the results for the Spatial-only CLS filter. The spatial filter fails: targets are not tracked when this filter is used. In Figures 6(b), 6(c) and in all similar figures below, the squares with no dots inside and no tracks attached represent instantaneous detections (“blips”) part of which are false. False detections, however, did not lead to real false alarms, since no false tracks were formed. The squares with dots inside and with tracks attached represent true targets that were confirmed and tracked.
Next, we performed a detailed comparative study of the industry standard differencing method with our clutter rejection techniques. The differencing clutter rejection method simply subtracts two consecutive frames. It is therefore equivalent to our temporal window-limited clutter rejection filter (implemented in the bank of CLS filters) with the window size of 2 frames.
We first comment on this algorithm. The first important observation is that the differencing algorithm may work well if, and only if, almost complete stabilization (sub-sub-pixel) is performed. It also requires an independent stabilization algorithm in contrast to most our CLS filters where stabilization is performed in the course of and jointly with clutter rejection. The reason is obvious— this algorithm is not only robust but, by contrast, it is quite sensitive to any changes that occur between consequent images. In addition, a simple subtraction of frames doubles the intensity of sensor noise. Therefore, small weak targets will not be detected and tracked even if clutter is suppressed.
We now confirm these points by experiments with synthetic data. In order to “enhance” the capability of the differencing algorithm we used ideal conditions in terms of stabilization – without jitter. As we will see, even in these conditions the algorithm performs poorly, as can be expected from the above argument.
We simulated an image sequence with moderately intense clutter. Two weak targets were inserted in the sequence. We first used the Wavelet spatial-temporal filter with the window 20 frames. The results were very successful – the standard deviation of the residual clutter was below the noise level and both targets were tracked, as can be seen in Fig. 7(b). By contrast, the differencing method was not able to track targets– only part of the trajectory of one target was tracked, as seen from Fig. 7(c).
Movie 1 - Clutter suppression and target tracking for synthetic data
Movie 2 - Clutter suppression and target tracking for real AirForce Lab data
Additional information and a brief outline of another similar project (shipboard IRST) can be found at
Link with the IRST project
5. Image Stabilization and Enhancement
Super Stabilization Challenges – Various computer vision techniques are successfully used in many different applications such as video compression, target tracking, or object recognition. In particular, digital image stabilization plays a key role in contemporary digital video systems, such as digital cameras and navigation tools. During video capture, the camera often vibrates, which leads to undesirable trembling of the recorded video. In the simplest case, this phenomenon only involves a small vibration of the camera’s optic axis. However, in principle, large shifts (e.g., up to half a frame) are also possible, especially if strong magnification is used during the recording. More complicated cases might also develop. For example, the camera might not only vibrate, but also change its orientation and position in space. In all these cases, the problem of compensating the movement of the camera in order to obtain a stabilized image is of paramount importance, which is often referred to as the registration problem.
Global Motion Model – We have chosen an affine motion model permitting translation and rotation that is sufficient for our applications. This provides a good tradeoff of capability and computational complexity requirements. In addition to translational and rotational stabilization, a more general model supporting scaling is being developed.
Software Tools – The developed software tools, called ImageStabilizer, implement stabilization filters for registration of an input video stream and produce two output video streams, the stabilized video and the mosaic video. The designed StabilizationFilter supports real-time processing of full-size video streams (640×480 pixel images at 30 frames per second rates). ImageStabilizer implements a Directshow interface for reading and parsing a video stream. This implementation uses Intel OpenCV library and Intel Performance Primitives (IPP v 4.0) to use full hardware support of Intel Pentium 4 Architecture.
Video-MTI Applications – Instead of expending exorbitant computational resources on the registration of every pixel (traditional approach), only pixels that are potential detections are registered and the registration is a simple mapping. Advanced data association techniques are then used to compensate for the remaining inaccuracies in the registration process. Unlike differencing methods that begin by translating, rotating and de-warping every pixel, the initial step in our approach reduces the number of pixels to be further processed by several orders of magnitude. This reduces every aspect of the processing cost: size, weight, power and time-line. All these aspects are important in airborne MTI (Moving Target Indicator) applications, and especially in UAV (Unmanned Arial Vehicles) applications.
Click here for more information