Fast Closed-Form Matting Using a Hierarchical Data Structure

Image/video matting is one of the key operations in many image/video editing applications. Although previous methods can generate high-quality matting results, their high computational cost in processing high-resolution image and video data often limits their usability. In this paper, we present a unified acceleration method for closed-form image and video matting using a hierarchical data structure, which achieves an excellent compromise between quality and speed. We first apply a Gaussian KD tree to adaptively cluster the input high-dimensional image and video feature space into a low-dimensional feature space. Then, we solve the affinity-weighted Laplacian alpha matting in the reduced feature space. The final matting results are derived using detail-aware alpha interpolation. Our algorithm can be fully parallelized by exploiting advanced graphics hardware, which can further accelerate the matting computation. Our method accelerates existing methods by at least an order of magnitude with good quality, and also greatly reduces the memory consumption. This acceleration strategy is also extended to support other affinity-based matting approaches, which makes it a more general accelerating framework for a variety of matting methods. Finally, we apply the presented method to accelerate image and video dehazing, and image shadow detection and removal.