Objective

• Understand graph cut operations and implement interactive segmentation by providing foreground and background markers on an image or selecting a region containing the foreground using a bounding box.
• Implement image segmentation using clustering methods (K-means algorithm).

Implementation

1. Interactive Segmentation with Graph Cut

Image Selection

Two types of images were selected: one where foreground and background are clearly distinguishable, and another where they are not easily separable.

Implementation Code

import cv2
import numpy as np

# Load and resize image
source_image = cv2.imread('building.jpg')
source_image = cv2.resize(source_image, (960, 720))

# Initialize segmentation mask
segmentation_mask = np.zeros(source_image.shape[:2], np.uint8)

# Background and foreground models
background_model = np.zeros((1, 65), np.float64)
foreground_model = np.zeros((1, 65), np.float64)

# Mouse callback for rectangle selection
def rectangle_selector(event, x, y, flags, param):
    global start_x, start_y, is_drawing, selection_complete

    if event == cv2.EVENT_LBUTTONDOWN:
        is_drawing = True
        start_x, start_y = x, y

    elif event == cv2.EVENT_MOUSEMOVE:
        if is_drawing:
            temp_image = source_image.copy()
            cv2.rectangle(temp_image, (start_x, start_y), (x, y), (0, 255, 0), 2)
            cv2.imshow('input_image', temp_image)

    elif event == cv2.EVENT_LBUTTONUP:
        is_drawing = False
        selection_complete = True
        cv2.rectangle(source_image, (start_x, start_y), (x, y), (0, 255, 0), 2)
        
        # Define rectangle coordinates
        rect_coords = (min(start_x, x), min(start_y, y), 
                      abs(start_x - x), abs(start_y - y))
        
        # Apply GrabCut algorithm
        cv2.grabCut(source_image, segmentation_mask, rect_coords, 
                   background_model, foreground_model, 5, cv2.GC_INIT_WITH_RECT)
        cv2.imshow('input_image', source_image)

# Setup mouse callback
cv2.namedWindow('input_image')
cv2.setMouseCallback('input_image', rectangle_selector)

is_drawing = False
start_x, start_y = -1, -1
selection_complete = False

while True:
    cv2.imshow('input_image', source_image)
    key = cv2.waitKey(1) & 0xFF

    if selection_complete:
        # Generate segmented output
        output_mask = np.where((segmentation_mask == 2) | (segmentation_mask == 0), 
                              0, 1).astype('uint8')
        segmented_result = source_image * output_mask[:, :, np.newaxis]
        cv2.imshow('segmented_output', segmented_result)

    if key == 27:  # ESC key
        break

cv2.destroyAllWindows()

Results

The algorithm was tested on both types of images:

1. Images with clear foreground-background distinction
2. Images with ambiguous foreground-background boundaries

Algorithm Explanation

The implementation utilizes OpenCV's GrabCut algorithm, which is based on graph cut theory. This approach categorizes image pixels into four groups: definite background, probable background, probable foreground, and definite foreground. The algorithm iteratively refines these classifications until convergence.

The process involves:

• Loading the input image and initializing a mask for segmentation results
• Setting up background and foreground models for color distribution analysis
• Implementing mouse interaction to define rectangular regions of interest
• Applying the GrabCut algorithm upon completing the rectangular selection

2. Image Segmentation via K-Means Clustering

Implementation Code

import numpy as np
import cv2
from sklearn.cluster import KMeans

# Load and preprocess image
input_img = cv2.imread('building.jpg')
input_img = cv2.resize(input_img, (960, 720))
input_img = cv2.cvtColor(input_img, cv2.COLOR_BGR2RGB)

# Reshape image data for clustering
height, width, channels = input_img.shape
pixel_data = input_img.reshape((height * width, channels))

# Apply K-means clustering with 3 clusters
clustering_model = KMeans(n_clusters=3, random_state=0)
clustering_model.fit(pixel_data)

# Extract cluster information
cluster_labels = clustering_model.labels_
cluster_centers = clustering_model.cluster_centers_

# Reshape labels back to image dimensions
cluster_labels = cluster_labels.reshape((height, width))
clustered_image = np.zeros((height, width, channels), dtype=np.uint8)

# Assign colors based on cluster centers
for row in range(height):
    for col in range(width):
        clustered_image[row, col] = cluster_centers[cluster_labels[row, col]]

# Display results
cv2.imshow('Original_Image', input_img)
cv2.imshow('Clustered_Result', clustered_image)
cv2.waitKey(0)
cv2.destroyAllWindows()

Results

Similar testing was performed on both image categories to evaluate clustering performance.

Methodology Explanation

This approach employs the K-means clustering algorithm, a partition-based clustering technique that divides the dataset into K distinct clusters. Each data point is assigned to the cluster whose center is closest to it.

Key steps in the implementation:

• Image loading and conversion to RGB color space
• Data reshaping to create a feature matrix suitable for clustering
• Application of scikit-learn's KMeans implementation
• Post-processing to reconstruct the segmented image from cluster assignments