4.3 Image Clustering and Segmentation

4.3.1 K-Means Clustering

K-means clustering is a simple, widely used algorithm for partitioning a dataset into $K$ clusters.

• Goal: Divide a set of data points into $K$ clusters, where each data point belongs to the cluster with the nearest mean (centroid).

• Algorithm Description:

  • Input:

    • $X=\{x_1,x_2,...,x_n\}$, a set of data points (e.g., pixel color values).
    • $K$, the number of desired clusters.

  • Output:

    • $C=\{c_1,c_2,...,c_K\}$, a set of clusters, where each $c_k$ represents a group of data points.

  • Steps:

    1. Initialization: Randomly select $K$ cluster centers (means), denoted as $m_1,m_2,...,m_K$. These are initial guesses for the cluster centroids.
    2. Assignment: Calculate the distance between each data point $x_i$ and all cluster means $m_k$. Assign $x_i$ to the cluster with the nearest cluster mean. Common distance metrics include Euclidean distance.
    3. Update: Recalculate the new means (centroids) for each cluster. The new mean $m_k$ of cluster $c_k$ is the average of all data points assigned to that cluster.
    4. Iteration: Repeat steps 2 and 3 until no data point changes its cluster assignment, or a maximum number of iterations is reached. This indicates convergence.

• Objective Function (Sum of Squared Error - SSE)

  • K-means aims to minimize the Sum of Squared Error (SSE) function, also known as the within-cluster variance.

  • Formula:

    $J(C)={\sum }_{k=1}^K{J}_k$

    where $J_k$ is the SSE of the $k$th cluster.

    $J_k={\sum }_{x_i\in c_k}||x_i-m_k|{|}^2$

  • $m_k$ is the mean of cluster $c_k$.

  • $|c_k|$ is the number of instances (data points) in cluster $c_k$.
  • $||x_i-m_k|{|}^2$ represents the squared Euclidean distance between data point $x_i$ and the mean $m_k$ of its assigned cluster.

• Applications in Color Quantization

  • K-means is frequently used for color quantization, which reduces the number of colors in an image.
  • Each pixel’s RGB color vector is treated as a data point.
  • K-means groups similar colors together, and each cluster represents a quantized color.
  • The cluster centroid becomes the representative color for all pixels in that cluster.

• Limitations

  • The key issue with a K-means clustering is the parameter K.
  • The final cluster depends on intial cluster means.
  • Sensitivity to Initial Seeds: The final clustering result can vary significantly depending on the initial random selection of cluster centers.
  • Need to Specify K: The algorithm requires the user to specify the number of clusters ($K$) a priori, which may not be known in advance. An incorrect $K$ can lead to poor clustering.
  • Assumption of Spherical Clusters: K-means implicitly assumes that clusters are spherical and equally sized, which may not be true for all datasets.
  • Local Optima: The algorithm can converge to a local optimum of the SSE function, which may not be the global optimum.

4.3.2 JSEG Segmentation

JSEG is an image segmentation method that leverages both color and texture information. It assumes that regions with similar colors also tend to have similar textures.

• Belief: Color regions and textures usually correspond within an image. A homogeneous color region often corresponds to a homogeneous texture region.

• Steps:

  1. Color Quantization:

     • The pixel colors of the input image are quantized into a smaller number of color classes.
     • A clustering algorithm (like K-means) can be used for this quantization.
     • This reduces the computational complexity and noise sensitivity.

  2. Color Map Creation:

     • Each pixel in the original image is replaced by its corresponding color class label (e.g., 1, 2, 3, …).
     • This creates a “class map,” where each number represents a quantized color.
     • Region growing will be performed on this class map.

  3. J-Image Computation:

     • This is the core of the JSEG method. A “J-image” is created to represent local homogeneity.

     • A local window (e.g., 3x3, 5x5) is moved across the class map.

     • For each window position, a $J$ value is calculated, representing the local variance (using SSE).

     • Formula:

       $J_k={\sum }_{x_i\in c_k}||x_i-m_k|{|}^2$

       • $J_k$ is simillar to SSE.
       • $x_i$ The SSE is related to the variance over a local neighborhood, neighborhoods with relatively uniform colors (or little to no texture)tend to have small $J$ values while neighborhoods with high $J$ values correspond to region boundaries or edges.
       • $m_k$ is the mean.

     • Interpretation:

       • Low $J$ values: Indicate relatively uniform color/texture within the window (likely within a region).
       • High $J$ values: Indicate significant color/texture variation (likely at region boundaries or edges). * The window size determine the sharpness of the J-image.

  4. Region Growing (Based on J-Image):

     • A region growing algorithm is applied to the J-image.
     • Seed Selection: Starts with areas (pixels) having the lowest $J$ values (most homogeneous regions).
     • Growing: Iteratively expands the regions by adding neighboring pixels with similar $J$ values, guided by a threshold.
     • The region growing is repeated using a J-image with smaller scale untill the average $\bar{J}$ value stops decresing.
     • This process groups pixels with similar local characteristics into regions.

  5. Region Merging:

     • After region growing, an optional merging step can be performed.
     • Adjacent regions with similar average colors are merged.
     • This helps to reduce over-segmentation (too many small regions) caused by minor texture variations.

• Advantages:

  • Combines Color and Texture: Uses both color and texture information, leading to more robust segmentation than methods relying on color alone.
  • Less Fragmented Segmentation: Tends to produce less fragmented regions compared to simple K-means clustering.

• Limitations:

  • Parameter Sensitivity: Performance depends on several parameters:
    • Number of quantized colors.
    • Seed selection threshold for region growing.
    • Color similarity threshold for region merging.
    • Window size for J-image computation.
  • Computational Cost: Can be computationally expensive, especially for large images. The J-image calculation and region growing are iterative processes.
  • Over-segmentation: Can still produce over-segmentation in highly textured regions.
  • Doesn’t gurrenty about the global optimality.