  This paper formulates and presents a solution to the new problem of budgeted
semantic video segmentation. Given a video, the goal is to accurately assign a
semantic class label to every pixel in the video within a specified time
budget. Typical approaches to such labeling problems, such as Conditional
Random Fields (CRFs), focus on maximizing accuracy but do not provide a
principled method for satisfying a time budget. For video data, the time
required by CRF and related methods is often dominated by the time to compute
low-level descriptors of supervoxels across the video. Our key contribution is
the new budgeted inference framework for CRF models that intelligently selects
the most useful subsets of descriptors to run on subsets of supervoxels within
the time budget. The objective is to maintain an accuracy as close as possible
to the CRF model with no time bound, while remaining within the time budget.
Our second contribution is the algorithm for learning a policy for the sparse
selection of supervoxels and their descriptors for budgeted CRF inference. This
learning algorithm is derived by casting our problem in the framework of Markov
Decision Processes, and then instantiating a state-of-the-art policy learning
algorithm known as Classification-Based Approximate Policy Iteration. Our
experiments on multiple video datasets show that our learning approach and
framework is able to significantly reduce computation time, and maintain
competitive accuracy under varying budgets.
