One of the coolest approaches I've seen does some cool inference on fully connected Conditional Random Fields via high-dimensional filtering. Amazing results.

http://vladlen.info/publications/efficient-inference-in-full...