The problem of detecting features of interest in large video collections is addressed in this paper. The authors’ model uses a “second-order Markov model with a node for each frame and a state variable that indicates whether [the] frame is relevant to [the] ... query,” which might, for example, be face detection. The major issue is that accurate algorithms are computationally expensive. The algorithm of Krause and Guestrin [1] is of order (B²)(n³), where n is the number of nodes in the Markov chain used by the algorithm and B is the number of places in the video to which the algorithm is applied. The main contribution of the paper shows how one can use a mix of a less accurate algorithm and a more accurate one--based on Krause and Guestrin’s algorithm--to produce a less computationally expensive recognition system.

The basic idea is to divide the computational resources into two chunks. One chunk is used to separate the Markov chain into a number of “consecutive intervals where the first and last variables of each interval are observed.” The authors describe how, subject to an additional reasonable assumption, the resources of the remaining chunk can be optimally allocated to more accurate observations within each interval. The paper contains a detailed example that illustrates the technique and reports on experiments with motion detection and face detection, showing that the authors’ approach provides significant benefits.