Jason J. Corso
|
Graph-Shifts -- Dynamic Hierarchical Energy Minimization
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.
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 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.
Publications:
[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 ]
|
|