Localized Hierarchical Graph Cuts

We describe a low memory, parallelizable implementation of graph cut based MRF energy minimization that solves pixel labeling problems. We first solve the problem on a low resolution version of the image and make use of the technique of hierarchical graph cuts to obtain a narrow band of uncertainty in the high resolution image within which the labeling needs to be solved. We then sub-divide the narrow band into overlapping regions and solve the labeling problem for each of the regions separately. The overlapping regions are used to provide boundary conditions that force the labeling to be continuous. The key advantages of the method are low memory usage, cache friendliness and the potential for parallel execution. The solutions obtained are close to the global optimum. We demonstrate our method on the bi-label image segmentation and the multi-label image stitching problems.