The Probabilistic Multi-Hypothesis Tracker (PMHT) was developed in the early 1990s by Roy Streit and Tod Luginbuhl. Since that time many advances and improvements have been made to this elegant algorithm that is linearly efficient in processing as the number of targets, sensors, and clutter increases. This paper documents the many advances to the PMHT by several different contributors over the past two decades. The history continues and looks as promising as ever for this algorithm as we present the latest advancement—the Maximum Likelihood, Histogram Probabilistic Multi-Hypothesis Tracker (ML-HPMHT)—and the exciting results of this potential game-changer in tracking unresolved, dim targets in highly cluttered environments. This new algorithm, which we are calling the Quanta Tracking algorithm, detects and tracks with high accuracy targets that are unresolved in pixels or range bins.
KEYWORDS: Staring arrays, Photons, Signal to noise ratio, Target detection, Data modeling, Point spread functions, Infrared imaging, Sensors, Detection and tracking algorithms, Infrared radiation
In this paper, we address the problem of passive tracking of multiple targets with the help of images obtained from passive
infrared (IR) platforms. Conventional approaches to this problem, which involve thresholding, measurement detection, data
association and filtering, encounter problems due to target energy being spread across multiple cells of the IR imagery. A
histogram based probabilistic multi-hypothesis tracking (H-PMHT) approach provides an automatic means of modeling
targets that are spread in multiple cells in the imaging sensor(s) by relaxing the need for hard decisions on measurement
detection and data association. Further, we generalize the conventional HPMHT by adding an extra layer of EM iteration
that yields the maximum likelihood (ML) estimate of the number of targets. With the help of simulated focal plane array
(FPA) images, we demonstrate the applicability of MLHPMHT for enumerating and tracking multiple targets.
KEYWORDS: Sensors, Missiles, Expectation maximization algorithms, 3D acquisition, 3D metrology, Passive sensors, Detection and tracking algorithms, Monte Carlo methods, Annealing, Environmental sensing
Fusing data together for target tracking is a complex problem. There are two key steps. First, the raw observations must
be associated with existing tracks or used to form new tracks. Once the association has been done, then the tracks can be
updated and filtered with the new data. The updating and filtering is usually the easier of the two parts and it is the
association that can lead to most of the complexity in target tracking. When associating data (either measurements or
tracks or both) with existing tracks, the separation between the tracks is critical to how difficult the association decisions
will be. If the tracks are widely separated then the association decisions can be relatively easy. On the other hand, when
the tracks are closely spaced the association decisions can be very difficult or nearly impossible. When the tracks or
measurements are in three dimensions (such as with active sensors) the association can be accomplished in all three
dimension thus making an easier distinction of targets that may be very close in two dimensions, but distant in the third
dimension. However, when there are only two dimensions (as for passive sensors) observed by a sensor, targets that are
widely separated may appear to be very close or even unresolved. In this paper, we will discuss the issues involved with
applying the Probabilistic Multi-Hypothesis Tracking (PMHT) algorithm to fusing either measurements or tracks from
passive sensors.
KEYWORDS: Detection and tracking algorithms, Algorithm development, Sensors, Radar, Missiles, Monte Carlo methods, Defense and security, Performance modeling, Systems modeling, Computer simulations
The term benchmark originates from the chiseled horizontal marks that surveyors made, into which an angle-iron could
be placed to bracket ("bench") a leveling rod, thus ensuring that the leveling rod can be repositioned in exactly the same
place in the future. A benchmark in computer terms is the result of running a computer program, or a set of programs, in
order to assess the relative performance of an object by running a number of standard tests and trials against it. This
paper will discuss the history of simulation benchmarks that are being used by multiple branches of the military and
agencies of the US government. These benchmarks range from missile defense applications to chemical biological
situations. Typically, a benchmark is used with Monte Carlo runs in order to tease out how algorithms deal with
variability and the range of possible inputs. We will also describe problems that can be solved by a benchmark.
KEYWORDS: Detection and tracking algorithms, Sensors, Monte Carlo methods, Radar, Error analysis, Expectation maximization algorithms, Time metrology, Performance modeling, Received signal strength, Optical resolution
Target tracking is limited by the resolution of the sensors providing the measurements. If two objects are in close
proximity, they will return just one measurement in most instances. When these two objects separate enough to return
two distinct measurements, the question then is: where did the objects actually separate? The actual separation point
may be of interest and finding that separation point is the topic of this paper. Using the Probabilistic Multi-Hypothesis
Tracking (PMHT) algorithm allows measurements to be "shared" between tracks, and therefore makes an excellent
algorithm when there are closely-spaced unresolved measurements. In this paper, we will give an overview of how we
apply the PMHT algorithm to this separation estimation problem, and then we apply the algorithm to two aircraft flying
in formation and then separating. The results are obtained from a high-fidelity simulation environment and provide a
good test for this developing approach.
KEYWORDS: Signal to noise ratio, Target detection, Sensors, Switches, Kinematics, Radar, Mahalanobis distance, Signal processing, Time metrology, Detection and tracking algorithms
Closely-spaced (but resolved) targets pose a significant challenge for single-frame unique measurement-to-track
data association algorithms. This is due to the similarity of the Mahalanobis distances between the closely-spaced
measurements and tracks. Contrary to conventional wisdom, adding target feature information (e.g.,
target amplitude) does not necessarily improve the probability of correctly assigning measurements to tracks.
In this paper, the theoretical limitations of using radar cross section (RCS) data to aid in measurement-totrack
association are reviewed. The results of a high-fidelity simulation assessment of the benefits of RCSaided
measurement-to-track association (using the Signal-to-Noise Ratio) are given and other possibilities for
RCS-aided tracking are discussed. Namely, we show the analytical results of our investigation into using RCS
information to determine the presence of merged measurements.
KEYWORDS: Expectation maximization algorithms, Detection and tracking algorithms, Error analysis, Monte Carlo methods, Statistical analysis, Matrices, Computer simulations, Weapons, Data processing, Personal digital assistants
The Probabilistic Multi-Hypothesis Tracker (PMHT) has been demonstrated to be an effective multi-target
tracker while retaining linear computational complexity in the number of measurements and targets. However
PMHT only provides a point estimate for target tracks. The "covariance" returned by the PMHT is a byproduct
of applying the Expectation-Maximization algorithm to maximize the PMHT likelihood function and
is not intended to be the track estimate covariance. In this paper we derive a consistent covariance estimator
for PMHT. By re-introducing the constraint that the sum of the PMHT weights (posterior probabilities that a
measurement is target-originated) across measurements sum to unity, a covariance based on Probabilistic Data
Association (PDA) principles is derived. We show through simulations that the resulting covariance provides a
consistent covariance for the PMHT track estimates.
There has been some work both in the statistics and engineering literature that gives the posterior covariance
for ML Gaussian-mixture estimation, and the PMHT can be viewed as a tracker whose genesis is of
MAP Gaussian-mixture estimation with a Gaussian prior. The expressions and calculations are, unfortunately,
complicated. Consequently we also report on a novel and intuitive way to derive these via calculus.
KEYWORDS: Sensors, Composites, Detection and tracking algorithms, Missiles, Monte Carlo methods, X band, Radar, Switches, Error analysis, Coastal modeling
The Probabilistic Multi-Hypothesis Tracker (PMHT) is an emerging algorithm that has shown some success and is
intriguing because of its elegance and extensibility in many different aspects. It is a tracking algorithm that offers an
alternative to the Multiple Hypothesis Tracker (MHT) in the multiple-frame tracking arena. Instead of enumerating
many of the possibilities of track-to-measurement assignments, the PMHT uses a probabilistic approach to assign
the likely "weight" of each measurement to contribute to each track. This paper presents the ongoing results of
research using the PMHT algorithm as a network-level composite tracker on distributed platforms. In addition, the
methods necessary to implement the PMHT in a realistic simulation are discussed. It further describes the
techniques that have been tried to ensure a single integrated air picture (SIAP) across the platforms.
In 1995, Streit and Luginbuhl introduced a new tracking algorithm1, which offered a balance between the single-frame approach of the Probabilistic Data Association Filter (PDAF) and the multiple frame approach of the Multiple Hypothesis Tracker (MHT). With single-frame tracking algorithms, only information that has been received to date is used to determine the association between tracks and measurements. These decisions are made based on available data and are not changed even when future data may indicate that a decision was incorrect. On the other hand, in multi-frame algorithms, hard decisions are delayed until some time in the future, thus allowing the possibility that incorrect association decisions may be corrected with more data. This paper presents the initial results of some new research using the PMHT algorithm as a composite tracker on distributed platforms. In addition, the methods necessary to implement the PMHT in a realistic simulation are discussed. It further describes the techniques that have been tried to ensure a single integrated air picture (SIAP) across the platforms. The PMHT uses both past and present data without enumerating most of the possibility measurement-to-track assignments. Instead the PMHT uses probabilistic weightings via Gaussian mixtures to define the relationship between measurements and tracks.
Methods have been developed to apply Multiple Hypothesis Tracking (MHT) to a distributed multiple platform system for tracking missile targets. The major issue that must be addressed is the requirement for a single integrated air picture (SIAP) to be maintained across the multiple platforms. Communication delays and failures mean that the platforms will, in general, form different MHT hypotheses with resultant different output tracks presented to the users. Thus, logic, described in this paper, has been developed to ensure that similar data association decisions will be made across the multiple platforms.
KEYWORDS: Detection and tracking algorithms, Error analysis, Monte Carlo methods, Algorithm development, Data processing, Solids, Sensors, Thulium, Time metrology, Computer engineering
Since the early 1990s, significant research has been done on a relatively new algorithm called the Probabilistic Multi-Hypothesis Tracker (PMHT). The majority of this research has concluded that there are a few weaknesses with this approach to tracking targets in the presence of clutter. First, the number of targets that are being tracked needs to be known a priori. Second, in order for the algorithm to operate properly, a very good initiation must be performed. Without a very close initiation, the PMHT usually fails to lock on to the target correctly. To address both of these issues, a hybrid approach is proposed. This hybrid approach will use a Multi-Hypothesis Tracking (MHT) algorithm to initiate new tracks and to continue tracking them until a track is stable. Then it will hand these tracks off to the PMHT to maintain. The MHT is very good at initiating new tracks, and the PMHT is best at maintaining multiple tracks because the algorithm's complexity with tracking additional targets grows linearly as opposed to exponentially.
Tracking multiple targets in a cluttered environment is extremely difficult. Traditional approaches use simple techniques to determine what are the true measurements by a combination of gating and some form of a nearest neighbor association. As clutter densities increase, these traditional algorithms fail to perform well. To counter this problem, the multi-hypothesis tracking (MHT) algorithm was developed. This approach enumerates almost every conceivable possible combination of measurements to determine the most likely. This process quickly becomes very complex and requires vast amounts of memory in order to store all of the possible tracks. To avoid this complexity, more sophisticated single hypothesis data association techniques have been developed, such as the probabilistic data association filter (PDAF). These algorithms have enjoyed some success but do not take advantage of any future data to help clarify ambiguous situations. On the other hand, the probabilistic multi-hypothesis tracking (PMHT) algorithm, proposed by Streit and Luginbuhl in 1995, attempts to use the best aspects of the MHT and the PDAF. In the PMHT algorithm, data is processed in batches, thereby using information from before and after each measurement to determine the likelihood of each measurement-to-track association. Furthermore, like the PDAF, it does not attempt to make hard assignments or enumerate all possible combinations. but instead associates each measurement with each track based upon its probability of association. Actual performance and initialization of the PMHT algorithm in the presence of significant clutter has not been adequately researched. This study focuses on the performance of the PMHT algorithm in dense clutter and the initialization thereof. In addition, the effectiveness of measurement attribute data is analyzed, especially as it relates to algorithm initialization. Further, it compares the performance of this algorithm to the nearest neighbor, MHT, and PDAF.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.