People: Jason Corso, Zhuowen Tu (UCLA), Alan Yuille (UCLA)

Graph-Shifts is an energy minimization algorithm that manipulates a dynamic hierarchical decomposition of the data to rapidly and robustly minimize an energy function. It is a steepest descent minimizer that explores a non-local search space during minimization. A dynamic hierarchical representation makes exploration of this large search space plausible, and it facilitates both large jumps in the energy space analogous to combined split-and-merge operations as well as small jumps analogous to PDE-like moves. We use a deterministic approach to quickly choose the optimal move at each iteration. It has been applied in 2D and 3D joint image segmentation and classification in medical images, as depicted below for the segmentation of subcortical brain structures, and natural images as depicted at the semantic image labeling page. Graph-shifts typically converges orders of magnitude faster than conventional minimization algorithms, like PDE-based methods, and has been shown to be very robust to initialization.

• Code is available, along with a simple example dataset. [Java][Data Zip] C++ code is in development, but early results show the Java code to be faster!? We can provide no help in running this code and can retain no liability for it. If you use it in your publications, please cite either our IPMI 2007 or CVPR 2008 paper.
• Here is a short talk describing the graph-shifts algorithm.
• Here is a video of graph-shifts applied to segmentation and classification of sub-cortical brain structures, which is the original application for which it was invented.

[1]	A. Y. C. Chen and J. J. Corso. Temporally consistent multi-class video-object segmentation with the video graph-shifts algorithm. In Proceedings of the 2011 IEEE Workshop on Motion and Video Computing, 2011. [ bib | code | project | .pdf ]
[2]	A. Y. C. Chen and J. J. Corso. On the effects of normalization in adaptive MRF hierarchies. In Proceedings of CompImage '10-Computational Modeling of Objects Presented in Images, 2010. [ bib | .pdf ]
[3]	A. Y. C. Chen, J. J. Corso, and L. Wang. HOPS: Efficient region labeling using higher order proxy neighborhoods. In Proceedings of International Conference on Pattern Recognition, 2008. [ bib | .pdf ]
[4]	J. J. Corso, A. Yuille, and Z. Tu. Graph-Shifts: Natural Image Labeling by Dynamic Hierarchical Computing. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2008. [ bib | code | project | .pdf ]
[5]	J. J. Corso, Z. Tu, and A. Yuille. MRF Labeling with a Graph-Shifts Algorithm. In Proceedings of International Workshop on Combinatorial Image Analysis, volume LNCS 4958, pages 172-184, 2008. [ bib | .pdf ]
[6]	J. J. Corso, A. L. Yuille, N. L. Sicotte, and A. Toga. Detection and Segmentation of Pathological Structures by the Extended Graph-Shifts Algorithm. In Proceedings of Medical Image Computing and Computer Aided Intervention (MICCAI), 2007. [ bib | .pdf ]
[7]	J. J. Corso, Z. Tu, A. Yuille, and A. W. Toga. Segmentation of Sub-Cortical Structures by the Graph-Shifts Algorithm. In Proceedings of Information Processing in Medical Imaging (IPMI), volume LNCS 4584, pages 183-197, 2007. [ bib | .pdf ]