# toccgh

Compute track probabilities using the CGH algorithm

## Description

## Examples

### Tracker Operating Characteristic Curves

The tracker operating characteristic (TOC) curve is a plot of the probability of a target track as a function of the probability of a false track. Plot the TOC curves for three different values of signal-to-noise ratio (SNR) assuming a 2/3 confirmation logic and use a one-dimensional constant-velocity Kalman filter to generate the tracker gate growth sequence.

Compute the probability of detection and the probability of false alarm for SNR values of 3, 6, and 9 dB. Assume a coherent receiver with a nonfluctuating target. Generate 20 probability-of-false-alarm values logarithmically equally spaced between ${10}^{-10}$ and ${10}^{-3}$ and calculate the corresponding probabilities of detection.

SNRdB = [3 6 9]; [pd,pfa] = rocsnr(SNRdB,'SignalType','NonfluctuatingCoherent', ... 'NumPoints',20,'MaxPfa',1e-3);

Compute and plot the TOC curves and the corresponding receiver operating characteristic (ROC) curves.

toccgh(pd,pfa)

### Compute Track Probabilities

Compute the probability of target track, the probability of false track, and the expected number of false tracks corresponding to a probability of detection of 0.9, a probability of false alarm of ${10}^{-6}$, and a 3-of-5 track confirmation logic.

pd = 0.9; pfa = 1e-6; logic = [3 5];

Use a modified version of the default one-dimensional constant-velocity Kalman filter to generate the tracker gate growth sequence. Specify an update time of 0.3 second and a maximum target acceleration of 20 meters per square second.

KFpars = {'UpdateTime',0.3,'MaxAcceleration',20};

Compute the probabilities and the expected number of false tracks.

`[pdf,pft,eft] = toccgh(pd,pfa,'ConfirmationThreshold',logic,KFpars{:})`

pdf = 0.9963

pft = 2.1555e-19

eft = 1

### Custom Gate Growth Sequence

Use the common gate history algorithm to compute the probability of target track and the probability of track for a probability of detection of 0.5 and a probability of false alarm of ${10}^{-3}$. Use a custom gate growth sequence and a confirmation threshold of 3/4.

pd = 0.5; pfa = 1e-3; cp = [3 4]; gs = [21 39 95 125];

Compute the probabilities.

[pdf,pft] = toccgh(pd,pfa,'ConfirmationThreshold',cp, ... 'GateGrowthSequence',gs)

pdf = 0.5132

pft = 9.9973e-07

### Varying False-Alarm Probabilities

Investigate how receiver operating characteristic (ROC) and tracker operating characteristic (TOC) curves change with the probability of false alarm.

Compute probability-of-detection and signal-to-noise-ratio (SNR) values corresponding to probabilities of false alarm of ${10}^{-4}$ and ${10}^{-6}$. Assume a coherent receiver with a nonfluctuating target. Plot the resulting ROC curves. Use larger markers to denote a larger SNR value.

pfa = [1e-4 1e-6]; [pd,SNRdB] = rocpfa(pfa,'SignalType','NonfluctuatingCoherent'); scatter(SNRdB,pd,max(SNRdB,1),'filled') title('Receiver Operating Characteristic (ROC)') xlabel('SNR (dB)') ylabel('P_d') grid on title(legend('10^{-6}','10^{-4}'),'P_{fa}')

Compute the TOC curves using the probabilities of detection and probabilities of false alarm that you obtained. As the SNR increases, the probability of a false track in the presence of target detection increases. As the SNR decreases, the probability of target detection decreases, thereby increasing the probability of a false track.

[pct,pcf] = toccgh(pd.',pfa); scatter(pcf,pct,max(SNRdB,1),'filled') set(gca,'XScale','log') title('Tracker Operating Characteristic (TOC)') xlabel('P_{FT}') ylabel('P_{DT}') grid on title(legend('10^{-6}','10^{-4}'),'P_{fa}')

## Input Arguments

`pd`

— Probability of detection

vector | matrix

Probability of detection, specified as a vector or a matrix of values in the range [0, 1].

**Note**

If you use `rocpfa`

to obtain `pd`

, you
must transpose the output before using it as input to
`toccgh`

. If you use `rocsnr`

to obtain
`pd`

, you do not have to transpose the output.

**Example: **`[pd,pfa] = rocsnr(6)`

returns single-pulse detection
probabilities and false-alarm probabilities for a coherent receiver with a
nonfluctuating target and a signal-to-noise ratio of 6 dB.

**Data Types: **`double`

`pfa`

— Probability of false alarm

vector

Probability of false alarm per cell (bin), specified as a vector of values in the range [0, 1].

**Tip**

Use `pfa`

values of 10^{–3} or smaller to satisfy the assumptions of the common gate history
algorithm.

**Example: **`[pd,pfa] = rocsnr(6)`

returns single-pulse detection
probabilities and false-alarm probabilities for a coherent receiver with a
nonfluctuating target and a signal-to-noise ratio of 6 dB.

**Data Types: **`double`

### Name-Value Arguments

Specify optional pairs of arguments as
`Name1=Value1,...,NameN=ValueN`

, where `Name`

is
the argument name and `Value`

is the corresponding value.
Name-value arguments must appear after other arguments, but the order of the
pairs does not matter.

*
Before R2021a, use commas to separate each name and value, and enclose*
`Name`

*in quotes.*

**Example: **`'UpdateTime',0.25,'MaximumAcceleration',8`

specifies that the
1-*D* constant-velocity track Kalman filter used to compute the track
gate growth has an update time of 0.25 second and a maximum acceleration of targets of
interest of 8 meters per square second.

`ConfirmationThreshold`

— Confirmation threshold

`[2 3]`

(default) | two-element row vector of positive integers | positive integer scalar

Confirmation threshold, specified as a two-element row vector of positive integers
or a scalar. The two-element vector [*M*
*N*] corresponds to an *M*-out-of-*N*
or *M*/*N* confirmation logic, a test that
stipulates that an event must occur at least *M* times in
*N* consecutive updates.

A track is confirmed if there are at least

*M*detections in*N*updates.A track is deleted if there are less than

*M*detections in*N*updates.

If this argument is specified as a scalar,
`toccgh`

treats it as a two-element vector with identical
elements. *N* cannot be larger than 50.

**Data Types: **`double`

`NumCells`

— Number of cells

`16384`

(default) | positive integer scalar

Number of cells, specified as a positive integer scalar. Use this argument to compute the expected number of false tracks.

**Data Types: **`double`

`NumTargets`

— Number of targets

`1`

(default) | positive integer scalar

Number of targets, specified as a positive integer scalar. Use this argument to compute the expected number of false tracks.

**Data Types: **`double`

`UpdateTime`

— Update time for Kalman filter

`0.5`

(default) | positive scalar in seconds

Update time for the default one-dimensional constant-velocity Kalman filter, specified as a positive scalar in seconds. This argument impacts the track gate growth.

**Data Types: **`double`

`MaxAcceleration`

— Maximum acceleration of targets of interest

`10`

(default) | nonnegative scalar in meters per square second

Maximum acceleration of targets of interest, specified as a nonnegative scalar in meters per square second. Use this input to tune the process noise in the default one-dimensional constant-velocity Kalman filter. This argument impacts the track gate growth.

**Data Types: **`double`

`Resolution`

— Range and range-rate resolution

`[1 1]`

(default) | two-element row vector of positive values

Range and range-rate resolution, specified as a two-element row vector of positive
values. The first element of `'Resolution'`

is the range resolution
in meters. The second element of `'Resolution'`

is the range rate
resolution in meters per second. This argument is used to convert the predicted
tracker gate size to bins.

**Data Types: **`double`

`GateGrowthSequence`

— Tracker gate growth sequence

vector of positive integers

Tracker gate growth sequence, specified as a vector of positive integers. The
values in the vector represent gate sizes in bins corresponding to
*N* possible misses in *N* updates, where
*N* is specified using
`'ConfirmationThreshold'`

. If
`'ConfirmationThreshold'`

is a two-element vector, then
*N* is the second element of the vector.

If this argument is not specified, `toccgh`

generates the
tracker gate growth sequence using a one-dimensional constant-velocity Kalman filter
implemented as a `trackingKF`

object with these settings:

Update time — 0.5 second

Maximum target acceleration — 10 meters per square second

Range resolution — 1 meter

Range rate resolution — 1 meter per second

`StateTransitionModel`

—`[1 dt; 0 1]`

, where`dt`

is the update time`StateCovariance`

—`[0 0; 0 0]`

, which means the initial state is known perfectly`MeasurementNoise`

—`0`

`ProcessNoise`

—`[dt^4/4 dt^3/2; dt^3/2 dt^2]*q`

, where`dt`

is the update time, the tuning parameter`q`

is`amax^2*dt`

, and`amax`

is the maximum acceleration. The tuning parameter is given in Equation 1.5.2-5 of [2].

To compute the gate sizes, the algorithm:

Uses the

`predict`

function to compute the predicted state error covariance matrix.Calculates the area of the error ellipse as

*π*times the product of the square roots of the eigenvalues of the covariance matrix.Divides the area of the error ellipse by the bin area to express the gate size in bins. The bin area is the product of the range resolution and the range rate resolution.

If this argument is specified, then the `'UpdateTime'`

,
`'MaxAcceleration'`

, and `'Resolution'`

arguments are ignored.

**Example: **`[21 39 95 125 155 259 301]`

specifies a tracker grate
growth sequence that occurs on some radar applications.

**Data Types: **`double`

## Output Arguments

`pdt`

— Probability of true target track in presence of false alarms

matrix

Probability of true target track in the presence of false alarms, returned as a
matrix. `pdt`

has the same size as `pd`

.

`pft`

— Probability of false track in presence of targets

matrix

Probability of false alarm track in the presence of targets, returned as a matrix.
`pft`

has the same size as `pd`

.

`eft`

— Expected number of false tracks

matrix

Expected number of false tracks, returned as a matrix of the same size as
`pd`

. `toccgh`

computes the expected number
of tracks using

$${E}_{\text{ft}}={P}_{\text{ft,nt}}{N}_{\text{c}}+{P}_{\text{ft}}{N}_{\text{t}},$$

where *P*_{ft,nt} is the probability of false track in the absence of targets, *N*_{c} is the number of resolution cells specified in
`'NumCells'`

, *P*_{ft} is the probability of false track in the presence of targets, and *N*_{t} is the number of targets specified in
`'NumTargets'`

.

## More About

### Common Gate History Algorithm

The common gate history (CGH) algorithm was developed by Bar-Shalom and collaborators and published in [1]. For more information about the CGH algorithm, see Assessing Performance with the Tracker Operating Characteristic.

The algorithm proceeds under these assumptions:

A track is one of these:

Detections from targets only

Detections from false alarms only

Detections from targets and from false alarms

The probability of more than one false alarm in a gate is low, which is true when the probability of false alarm

*P*_{fa}is low (*P*_{fa}≤ 10^{–3}).The location of a target in a gate obeys a uniform spatial distribution.

The algorithm sequentially generates the gate history vector *ω* = [*ω _{l}*,

*ω*,

_{lt}*λ*], where:

*ω*is the number of time steps since the last detection, either of a target or of a false alarm._{l}*ω*is the number of time steps since the last detection of a target._{lt}*λ*is the number of detections.

The state vector evolves as a Markov chain by means of these steps:

The algorithm initially creates a track. Only two events can initialize a track:

A target detection

A false alarm

There are only four types of events that continue a track:

*A*_{1}—*No detection*Events of Type 1 occur with probability

$$P\left\{{A}_{1}\right\}=\left(1-\frac{g\left({\omega}_{l}\right)}{g\left({\omega}_{lt}\right)}{P}_{\text{d}}\right){\left(1-{P}_{\text{fa}}\right)}^{g\left({\omega}_{l}\right)}$$

where

*P*_{d}is the probability of detection specified using`pd`

,*P*_{fa}is the probability of false alarm specified using`pfa`

,*g*(*ω*) is the gate size at step_{l}*ω*, and_{l}*g*(*ω*) is the gate size at step_{lt}*ω*._{lt}**Note**To reduce

*P*_{d}to a lower effective value,`toccgh`

weights it with the ratio$$\frac{g\left({\omega}_{l}\right)}{g\left({\omega}_{lt}\right)}=\frac{\text{Actualgatesize}}{\text{Sizeofgatetakingintoaccountthetimeelapsedsincethelasttargetdetection}},$$

which assumes a uniform spatial distribution of the location of a target in a gate. The gate sizes are specified using

`'GateGrowthSequence'`

.Events of Type 1 update the gate history vector as [

*ω*,_{l}*ω*,_{lt}*λ*] ➔ [*ω*+ 1,_{l}*ω*+ 1,_{lt}*λ*].*A*_{2}—*Target detection*Events of Type 2 occur with probability

$$P\left\{{A}_{2}\right\}=\frac{g\left({\omega}_{l}\right)}{g\left({\omega}_{lt}\right)}{P}_{\text{d}}{\left(1-{P}_{\text{fa}}\right)}^{g\left({\omega}_{l}\right)}$$

and update the gate history vector as [

*ω*,_{l}*ω*,_{lt}*λ*] ➔ [1, 1,*λ*+ 1].*A*_{3}—*False alarm*Events of Type 3 occur with probability

$$P\left\{{A}_{3}\right\}=\left(1-{\left(1-{P}_{\text{fa}}\right)}^{g\left({\omega}_{l}\right)}\right)\left(1-\frac{g\left({\omega}_{l}\right)}{g\left({\omega}_{lt}\right)}{P}_{\text{d}}\right)$$

and update the gate history vector as [

*ω*,_{l}*ω*,_{lt}*λ*] ➔ [1,*ω*+ 1,_{lt}*λ*+ 1].*A*_{4}—*Target detection and false alarm*Events of Type 4 occur with probability

$$P\left\{{A}_{4}\right\}=\left(1-{\left(1-{P}_{\text{fa}}\right)}^{g\left({\omega}_{l}\right)}\right)\left(\frac{g\left({\omega}_{l}\right)}{g\left({\omega}_{lt}\right)}{P}_{\text{d}}\right)$$

and cause the track to split into a false track and a true track:

*A*_{s,2a}— Continue with*A*_{3}, updating [*ω*,_{l}*ω*,_{lt}*λ*] ➔ [1,*ω*+ 1,_{lt}*λ*+ 1].*A*_{s,2b}— Continue with*A*_{2}, updating [*ω*,_{l}*ω*,_{lt}*λ*] ➔ [1, 1,*λ*+ 1].

At each step, the algorithm multiplies each track probability by the probability of the event that continues the track.

The procedure then lumps together the tracks that have a common gate history vector

*ω*by adding their probabilities:Tracks continued with

*A*_{4}are lumped with tracks that continue with*A*_{3}(one false alarm only).Tracks continued with

*A*_{4}are lumped with tracks that continue with*A*_{2}(target detection only).

This step controls the number of track states within the Markov chain.

At the end, the algorithm computes and assigns the final probabilities:

A

*target track*is a sequence of detections that satisfies the*M*/*N*confirmation logic and contains at least one detection from a target. To compute the probability of target track:Determine the sequences that satisfy the confirmation logic under the assumption

*A*_{s,2b}that*A*_{4}yields*A*_{2}.Separately store these probabilities.

To compute the probability of false track:

Compute the probability of target track under the assumption

*A*_{s,2a}that*A*_{4}yields*A*_{3}.Subtract this probability from the probability of all detection sequences that satisfy the confirmation logic.

## References

[1] Bar‐Shalom, Yaakov, Leon J. Campo,
and Peter B. Luh. "From Receiver Operating Characteristic to System Operating Characteristic:
Evaluation of a Track Formation System." *IEEE ^{®} Transactions on Automatic Control* 35, no. 2 (February 1990):
172–79. https://doi.org/10.1109/9.45173.

[2] Bar-Shalom, Yaakov, Peter K.
Willett, and Xin Tian. *Tracking and Data Fusion: A Handbook of
Algorithms*. Storrs, CT: YBS Publishing, 2011.

## Extended Capabilities

### C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

## Version History

**Introduced in R2021a**

## Open Example

You have a modified version of this example. Do you want to open this example with your edits?

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

# Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)