Course contentsShow
← Computer Science
Lesson 1051 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Image Segmentation with Min-Cut

Apply min-cut to partition pixels into foreground and background in image segmentation.

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:

  1. Build a graph: Each pixel becomes a node. Add two special nodes: a source (representing "definitely foreground") and a sink (representing "definitely background").

  2. 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)
  3. 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.