Parallel Block Sequential Closed-Form Matting With Fan-Shaped Partitions

Applying alpha matting to large images is a challenging task because of its computational complexity. This paper provides a divide and conquer strategy for performing closed-form matting. The matting problem, defined for an entire image, is broken down into systems of linear equations defined for very small blocks of the image. The sizes of the small systems are small enough for us to find solutions efficiently using a direct sparse linear equation system solver. The small systems are solved following a sequential order such that the alpha matte grows from a user scribble. With the block sequential application, matting is performed on fan-shaped partitions in parallel on multiple processing cores. Experiments on large test images as well as on standard benchmark test images show that the proposed parallel block sequential matting provides high quality alpha mattes with good scalability.