Dense depth-map extraction approaches either suffer from limited accuracy and robustness when run on natural images or from long computation times due to complex global optimizations. Recent improvements in massively parallel execution architectures found in today's graphics processing units motivated us to parallelize the global optimization process. In this article we present our analytical approach and a parallel implementation in OpenCL of a multi-label graph-cut algorithm. Our approach accomodates a third camera perspective through which we can improve occlusion handling in order to generate high quality depth maps. Through experiments on natural images we show that our implementation scales linearly and achieves close-to realtime performance.