Jason J. Corso

GraphShifts  Dynamic Hierarchical Energy Minimization
People: Jason Corso, Zhuowen Tu (UCLA), Alan Yuille (UCLA)
GraphShifts 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 nonlocal 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
splitandmerge operations as well as small jumps analogous to PDElike
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. Graphshifts
typically converges orders of magnitude faster than conventional minimization
algorithms, like PDEbased methods, and has been shown to be very robust to
initialization.
Shift#  Coronal  Sagittal 
5 


50 


500 


5000 


Other Info:
 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 graphshifts algorithm.
 Here is a video of graphshifts applied to segmentation and classification of subcortical brain structures, which is the original application for which it was invented.
Publications:
[1]

A. Y. C. Chen and J. J. Corso.
Temporally consistent multiclass videoobject segmentation with the
video graphshifts 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 '10Computational 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.
GraphShifts: 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 GraphShifts Algorithm.
In Proceedings of International Workshop on Combinatorial Image
Analysis, volume LNCS 4958, pages 172184, 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 GraphShifts 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 SubCortical Structures by the GraphShifts
Algorithm.
In Proceedings of Information Processing in Medical Imaging
(IPMI), volume LNCS 4584, pages 183197, 2007.
[ bib 
.pdf ]

