Problem formulation

In this setting, we assume that the targets move nondeterministically. In particular, when a shadow $s_i$ splits into shadows $s_j, s_k$ , the targets inside $s_i$ can split in any possible way as long as the numbers of targets in $s_j, s_k$ are both nonnegative. The component events and FOV events are assumed to be observed without error. Given such assumptions, the observation history can be partitioned into two inputs to our filter algorithm:

1. A sequence of shadow and FOV events, and
2. The initial conditions of targets in the shadows at time $t = t_0$ .

A typical initial condition for a shadow takes the form

$$\{(a_1,l_1,u_1),(a_2,l_2,u_2),\ldots,(a_k,l_k,u_k)\} ,$$ (1)

in which $a_i$ denotes a subset of target attributes (such as having red color). We assume that elements of the set $\{a_i\}$ for a shadow are pairwise disjoint: If $a_i$ has red color, then no $a_j, j \ne i$ can include targets with the attribute of having red color. The corresponding $l_i$ and $u_i$ denote the lower and upper bounds on the number of targets in the shadow with attribute $a_i$ . For example, we may know that at the beginning, a shadow have $6$ to $9$ green targets and $5$ targets that may be blue or red. In this case, the initial condition can be written as

$$\{(c = green,6,9),(c = blue \textrm{ or } red, 5, 5)\}.$$

With these inputs, the main task is to determine the lower and upper bounds on the number of targets in any given set of shadows at $t = t_f$ for any combinations of attributes.

To make the explanation of the algorithm clear, we first work with a single attribute and ignore FOV events. We also assume for the moment that the initial conditions are tight in the sense that all possible choices of values must be consistent with the later observations (for example, we cannot have a initial condition of $4$ to $6$ targets in a shadow and later find that it is only possible to have $2$ targets in it). We will then show how FOV events, multiple attributes, and other extensions can be handled incrementally.