We propose a novel linear method for scale invariant figure ground separation in images and videos. Figure ground separation is treated as a superpixel labeling problem. We optimize superpixel foreground and background labeling so that the object foreground estimation matches model color histogram, its area and perimeter are consistent with object shape prior, and the foreground superpixels form a connected region. This optimization problem is challenging due to high-order soft and hard global constraints among large number of superpixels. We devise a scale invariant linear method that gives an integer solution with a guaranteed error bound via a branch and cut procedure. The proposed method does not rely on motion continuity and works on static images and videos with abrupt motion. Our experimental results on both synthetic ground truth data and real images show that the proposed method is efficient and robust over object appearance changes, large deformation and strong background clutter.