Automatic scene cut detection in video is often very useful for several video processing tasks but is a hard problem to solve particularly for fades, or when transitions are gradual.

What are the approaches to scene/shot cut detection from a complexity and robustness perspective?