Fast Volume Seam Carving With Multipass Dynamic Programming

In volume seam carving, i.e., seam carving for 3D cost volume, an optimal seam surface can be derived by graph cuts, resulting from sophisticated graph construction. To date, the graph-cut algorithm is the only solution for volume seam carving. However, it is not suitable for practical use because it incurs a heavy computational load. We propose a multipass dynamic programming (DP)-based approach for volume seam carving, which reduces computation time and memory consumption while maintaining a similar image quality as that of graph cuts. Our multipass DP scheme is achieved by conducting DP in two directions to accumulate the cost in a 3D volume and then tracing back to find the best seam. In our multipass DP, a suboptimal seam surface is created instead of a global optimal one, and it has been experimentally confirmed by more than 198 crowdsourced workers that such suboptimal seams are good enough for image processing. The proposed scheme offers two options: a continuous method that ensures the connectivity of seam surfaces and a discontinuous method that ensures the connectivity in only one direction. We applied the proposed volume seam carving method based on multipass DP to conventional video retargeting and tone mapping. These two applications are completely different; however, the volume seam carving method can be applied similarly by changing the axes of the cost volume. Even though the results obtained using our methods were similar to those obtained by graph cuts, our computation time was approximately 90 times faster that of graph cuts and the memory usage was eight times smaller than that of graph cuts. We also extend the idea of tone mapping to the contrast enhancement method based on volume seam carving.