Graph Cuts project



In this project, we combined our interests to implement a graph cut algorithm for stereo correspondence and performed evaluation against a baseline algorithm using normalized cross correlation (NCC) across a variety of metrics.

Specifically, we investigated on the effectiveness of labeling disparities and handling occlusions for the graph cut algorithm.

We used a pre-aligned stereo image dataset with ground truth disparities from Middlebury College to benchmark performance.


Workflow diagram

Workflow diagram






[1] D. Scharstein and R. Szeliski, “A Taxonomy and Evaluation of Dense TwoFrame Stereo Correspondence Algorithms,” Int’l J. Computer Vision, 2002.
[2] Y. Boykov and V. Kolmogorov, “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision”, In IEEE transactions on Pattern Analysis and Machine Intelligence (PAMI), vol 26, no.9, pp 1124-1137, Sept 2004.
[3] V. Kolmogorov and R. Zabih, “Computing visual correspondence with occlusions using graph cuts”, In ICCV, volume II, pages 508–515, 2001.
[4] Scharstein, D., Hirschmüller, H., Kitajima, Y., Krathwohl, G., Nešić, N., Wang, X., & Westling, P. (n.d.). HighResolution Stereo Datasets with Subpixel-Accurate Ground Truth. Lecture Notes in Computer Science Pattern Recognition, 3142.
[5] M. Bleyer and C. Breiteneder, “Stereo Matching – State-of-the-Art and Research Challenges,” in Advanced Topics in Computer Vision. Springer, 2013, pp. 143–179
[6] K.-J. Yoon and I.-S. Kweon. “Locally Adaptive Support-Weight Approach for Visual Correspondence Search”. In CVPR, pp.924–931, 2005.
[7] M. Bleyer, C. Rhemann, and C. Rother, “Patchmatch Stereo—Stereo Matching with Slanted Support Windows,” Proc. British Machine Vision Conf., 2011
[8] I. J. Cox, S. L. Hingorani, S. B. Rao, and B. M. Maggs, ” A maximum likelihood stereo algorithm.”, in CVIU, 63(3):542–567, 1996.
[9] Victor Lempitsky, Carsten Rother, and Andrew Blake, “Logcut-efficient graph cut optimization for markov random fields,” in Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on. IEEE, 2007, pp. 1–8.
[10] J. Zbontar and Y. LeCun. “Stereo Matching by Training a Convolutional Neural Network to Compare Image Patches”, in CVPR, 1510.05970, 2015.
[11] M. G. Mozerov and J. V. D. Weijer, “Accurate Stereo Matching by Two-Step Energy Minimization,” IEEE Transactions on Image Processing, pp. 1153-1163
[12] H. Hirschmuller and D. Scharstein. “Evaluation of cost functions for stereo matching.” In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2007).
[13] S. Birchfield and C. Tomasi, “A Pixel Dissimilarity Measure That Is Insensitive to Image Sampling”, In IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 401-406, 1998.

Globally Optimizing Graph Partitioning Problems Using Message Passing

Efficient Graph-Based Image Segmentation


There are no reviews yet.

Be the first to review “Graph Cuts project”

Your email address will not be published. Required fields are marked *