Power Watershed: A Unifying Graph-Based Optimization Framework.

Area of Science:

• Computer Vision
• Image Processing
• Computational Mathematics

Background:

• Graph-based methods like graph cuts, random walker, and shortest path are common for image segmentation.
• These methods rely on energy minimization frameworks with varying parameters.
• The watershed algorithm, another segmentation technique, has not been fully integrated into this unified framework.

Purpose of the Study:

• To extend the common energy framework for graph-based image segmentation.
• To incorporate the optimal spanning forest (watershed) algorithm into this unified framework.
• To introduce a new family of segmentation algorithms, termed "power watershed".

Main Methods:

• Unified a common energy function for graph cuts, random walker, and shortest path algorithms by introducing parameter q.
• Introduced a new parameter p to include the optimal spanning forest (watershed) algorithm within the same framework.
• Proposed the "power watershed" algorithm by fixing p and varying q, extending traditional watershed segmentation.

Main Results:

• The "power watershed" algorithm, particularly with q=2, yields a multilabel, scale, and contrast-invariant segmentation.
• This specific configuration provides a unique global optimum, achieved in practice in quasi-linear time.
• The integration of watershed into the energy minimization framework enables new applications and model optimizations.

Conclusions:

• The generalized framework unifies several key image segmentation algorithms.
• The novel "power watershed" offers an efficient and robust method for image segmentation with desirable invariance properties.
• This work opens new avenues for watershed-based segmentation and optimization in broader applications.