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.
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.
- 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.
- 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.
- 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.
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