Image Segmentation with Min-Cut
What you'll learn: How to use the min-cut algorithm to automatically separate foreground objects from the background in an image.
The Core Idea
Image segmentation is the task of dividing an image into meaningful regions—often separating a "foreground" object from the "background." Min-cut provides an elegant way to solve this by modeling the image as a flow network.
Here's how it works:
-
Build a graph: Each pixel becomes a node. Add two special nodes: a source (representing "definitely foreground") and a sink (representing "definitely background").
-
Add edges:
- Connect the source to pixels likely to be foreground (high capacity if brightness/color suggests foreground)
- Connect pixels likely to be background to the sink (high capacity if they look like background)
- Connect neighboring pixels with capacities based on similarity—similar pixels get high capacity (hard to cut), dissimilar pixels get low capacity (easy to cut)
-
Find the min-cut: Run a max-flow algorithm. By the max-flow min-cut theorem, the minimum cut separates the graph into two parts with minimal total edge weight removed. This cut naturally divides pixels into foreground (source side) and background (sink side).
Why It Works
The min-cut finds the "cheapest" way to separate source from sink. Since we assigned low capacities to edges between dissimilar pixels (natural boundaries), the cut follows object edges. High capacities between similar pixels keep coherent regions together.
Key Takeaway: Min-cut transforms image segmentation into a flow problem where the minimum cut automatically finds object boundaries by cutting along edges between dissimilar pixels.