A Faster Method for Tracking and Scoring Videos Corresponding to Sentences

Haonan Yu, Daniel Paul Barrett, Jeffrey Mark SiskindarXiv 2014 · arXiv

Abstract

Matching complex natural language sentences to video sequences is a significant bottleneck in computer vision due to the exponential complexity of discrete combinatorial optimization. This paper presents a polynomial-time approach for sentence tracking by relaxing the problem into a continuous space and utilizing the Growth Transform algorithm. We prove that the global optimum of the relaxed problem is identical to the original discrete problem. Our method achieves near-optimal results with a relative error of 2.22% to 5.08% while scaling to complex scenarios that would take decades to compute using traditional Viterbi-based methods.

Introduction

The "sentence tracker" is a framework designed to link natural language to visual data. For a query such as, "The person to the left of the chair carried the backpack away from the traffic cone towards the stool," a computer must simultaneously track multiple objects while ensuring their spatial relationships and movements match the verbs and prepositions in the sentence.

Example of multi-object tracking for complex sentential descriptions involving a person, traffic cone, trash can, and backpack.

Prior methods relied on the Viterbi algorithm to find the best possible match. However, the computational cost of Viterbi in this context is exponential relative to the number of objects and words. For sentences with several participants, the search space becomes so vast that it is practically intractable, limiting systems to very few detections per frame and very short sentences.

Methodology

The core contribution of this work is a mathematical reformulation of the tracking cost function that shifts the problem from discrete selection to continuous optimization.

  1. Indicator Variables and Continuous Relaxation: Instead of using discrete indices to pick a detection, the authors employ indicator variables. They relax the constraint that these variables must be binary (0 or 1), allowing them to exist anywhere in the range $[0, 1]$. This transforms a "hard" combinatorial problem into a "smooth" optimization problem.
  2. Global Optimum Equivalence: Crucially, the authors provide a proof (Theorem 1) showing that the global optimum of this relaxed continuous problem is identical to the global optimum of the original discrete problem. This ensures that no accuracy is lost through the relaxation process.
  3. Growth Transform (GT): To solve the resulting high-degree polynomial objective, the authors use the Growth Transform algorithm. GT is an iterative local-search technique that is well-suited for these types of constrained non-linear programs, moving the space complexity from exponential to linear in terms of the number of nouns.

Experimental Results

The method was evaluated using a dataset of 94 video clips, each with two to five sentential annotations. The experiments scaled the number of detections ($J$) up to 120 per frame and the number of HMM states ($K$) up to 9, significantly exceeding the limits of prior approaches.

Comparison of tracking distributions across different detection counts (J) and HMM states (K), highlighting the intractability of Viterbi at higher scales.

Scalability and Accuracy

The Growth Transform method demonstrated massive scalability. For the most complex examples, the authors estimate that computing the global optimum using the old Viterbi method would have taken 20 years on a modern computer; the new method produced the result in minutes. Despite this speedup, accuracy remained high: when compared against cases where the global optimum was still calculable, the GT method found solutions with a relative error of only 2.22% to 5.08%.

Robustness

The system successfully handled a high number of object detections ($J=120$), allowing for noisier and more realistic object detection inputs. Because the new optimization method targets the exact same cost function as previous models, it offers "plug-and-play" compatibility with existing video retrieval or sentence generation systems.

Conclusion

By shifting from discrete combinatorial optimization to a continuous relaxation, this research transforms sentence tracking from an intractable problem into one that runs in polynomial time. While the Growth Transform is a local search method that can occasionally require random restarts to avoid local optima, its practical performance and mathematical "tightness" represent a significant leap forward. Future work will focus on extending this faster inference method to the language acquisition (training) phase, where word meanings are learned directly from video-sentence pairs.

Summary updated

Abstract

Prior work presented the sentence tracker, a method for scoring how well a sentence describes a video clip or alternatively how well a video clip depicts a sentence. We present an improved method for optimizing the same cost function employed by this prior work, reducing the space complexity from exponential in the sentence length to polynomial, as well as producing a qualitatively identical result in time polynomial in the sentence length instead of exponential. Since this new method is plug-compatible with the prior method, it can be used for the same applications: video retrieval with sentential queries, generating sentential descriptions of video clips, and focusing the attention of a tracker with a sentence, while allowing these applications to scale with significantly larger numbers of object detections, word meanings modeled with HMMs with significantly larger numbers of states, and significantly longer sentences, with no appreciable degradation in quality of results.
BibTeX
@misc{yu2014faster,
  author = {Haonan Yu and Daniel Paul Barrett and Jeffrey Mark Siskind},
  title = {{A Faster Method for Tracking and Scoring Videos Corresponding to Sentences}},
  year = {2014},
  eprint = {1411.4064},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1411.4064},
}
Figure