Graph cut Implementation

Type: Iterative Graph Cut / Foreground Extraction
Library: OpenCV (cv2.grabCut)
Application: Background Removal & Object Segmentation

GrabCut is an advanced image segmentation algorithm used to separate a foreground object from the background. Unlike simple thresholding, it uses an iterative process based on Gaussian Mixture Models (GMMs) and Graph Cut optimization. It effectively "learns" the colour distribution of the object and the background to create a clean cutout.

1. Mathematical Formulation

The algorithm treats the image segmentation as an energy minimization problem. The image is represented as a graph where pixels are nodes. The goal is to find a labeling α (foreground or background) that minimizes the energy function E(α):

Where U(α) (Data Term) measures how well a pixel fits the known colour distribution of the foreground/background, and V(α) (Smoothness Term) penalizes labeling discontinuities (encouraging the cut to follow edges rather than cutting through smooth regions).

2. Python Backend Logic (Snippet)

We implement this using OpenCV's grabCut function. Crucially, the algorithm requires two internal state arrays (bgd_model and fgd_model) to store the GMM parameters during iteration.

Note on Masks: The raw output mask contains four values: 0 (Definite Background), 1 (Definite Foreground), 2 (Probable Background), and 3 (Probable Foreground). We must filter these to get the final binary image.

def apply_graph_cut(image, rect):
    # 1. Initialize Memory for GMMs
    # OpenCV requires two 1x65 float64 arrays for internal calculations
    bgd_model = np.zeros((1, 65), np.float64)
    fgd_model = np.zeros((1, 65), np.float64)

    # 2. Prepare the Mask
    mask = np.zeros(image.shape[:2], np.uint8)

    # 3. Run Iterative GrabCut
    # mode=GC_INIT_WITH_RECT initializes using the bounding box
    cv2.grabCut(
        image, mask, rect,
        bgd_model, fgd_model,
        iterCount=10,
        mode=cv2.GC_INIT_WITH_RECT
    )

    # 4. Filter the Result
    # Treat "Probable Background" (2) as Background (0)
    mask_final = np.where((mask == 2) | (mask == 0), 0, 1).astype('uint8')

    return image * mask_final[:, :, np.newaxis]

3. Algorithmic Complexity

GrabCut is computationally expensive compared to standard filters. It utilizes the Min-Cut/Max-Flow algorithm repeatedly.

This makes the complexity roughly linear with the number of pixels N but multiplied by the number of iterations k: O(k × N).

Algorithm Reference: GrabCut Segmentation

1. Mathematical Formulation

2. Python Backend Logic (Snippet)

3. Algorithmic Complexity