Graph Theoretical Optimization of Prediction Structure in Multiview Video Coding

An algorithm to construct the optimal prediction structure in multiview video coding (MVC) is proposed in this work. We employ the graph theory as a framework. By considering each frame as a vertex and the motion compensation or disparity compensation as an edge, we represent a prediction structure as a spanning tree. Then, we obtain the optimal structure by finding the minimum spanning tree using the Prim´s algorithm. Simulation results demonstrate that the proposed algorithm provides about 0.2-0.4 dB better PSNR performance than the conventional prediction structure, and about 1.5 dB better performance than the simulcast.