Global Optimality Guarantees for Nonconvex Unsupervised Video Segmentation
This work addresses the problem of extracting moving objects from videos without supervision, providing theoretical guarantees for a nonconvex approach, though it is incremental as it builds on existing robust PCA methods.
The paper tackles unsupervised video object segmentation by formulating it as a nonconvex optimization problem using a sum of sparse and low-rank matrices, and derives conditions under which global optimality and uniqueness are guaranteed for the segmentation using local search methods, as illustrated with real video data.
In this paper, we consider the problem of unsupervised video object segmentation via background subtraction. Specifically, we pose the nonsemantic extraction of a video's moving objects as a nonconvex optimization problem via a sum of sparse and low-rank matrices. The resulting formulation, a nonnegative variant of robust principal component analysis, is more computationally tractable than its commonly employed convex relaxation, although not generally solvable to global optimality. In spite of this limitation, we derive intuitive and interpretable conditions on the video data under which the uniqueness and global optimality of the object segmentation are guaranteed using local search methods. We illustrate these novel optimality criteria through example segmentations using real video data.