Tree search algorithm for target detection in image sequences.

Given a time sequence of digital images of a high-noise environment, the authors address the problem of detecting pixel-sized, barely discernible moving objects whose positions and trajectories are unknown. The sequences may be temporally sparse and contain significant frame-to-frame drifting background clutter, as caused by relative motion between the sensor array and natural terrain, ocean, or clouds. A general, two-step approach is presented. First, time correlation and space-varying background structure are removed. The resulting innovations sequence is modeled by an independent and identically distributed (i.i.d.) Gaussian random field. Second, a large, dense set of pixel-sized space-time trajectories are hypothesized and tested in the innovations sequence. The search space, typically containing thousands of trajectories per pixel per image, is organized into a tree structure. A sequential statistical technique, multistage hypothesis testing, optimized for the innovations model, is used to test the multiple hypotheses and prune the tree-structured list of candidate trajectories. This results in an efficient algorithm with analyzable performance and processing requirements.