Dominant Set Clustering Algorithm: A Graph-Theoretic Approach for Image Segmentation

The Dominant-set clustering algorithm is a graph-theoretic clustering method particularly suitable for image segmentation and retrieval tasks. It represents data points as vertices in a graph and constructs a similarity matrix based on inter-vertex similarities, thereby transforming the clustering problem into a graph partitioning problem.

The algorithm's core concept involves identifying "dominant sets" within the graph. A dominant set can be understood as a tightly connected subgraph where internal similarity is high while connections to external nodes are relatively weak. The algorithm iteratively computes weights for each node, ultimately grouping high-weight nodes into the same cluster. In code implementation, this typically involves initializing a uniform weight vector and applying recursive weight updates using the formula: w_i(t+1) = w_i(t) * (A*w(t))_i / (w(t)^T * A * w(t)), where A is the similarity matrix.

Compared to traditional spectral clustering methods, the Dominant-set algorithm exhibits several distinctive characteristics: 1) It doesn't require pre-specifying the number of clusters; 2) It naturally handles asymmetric similarity matrices; 3) It can identify core nodes through weight allocation. These features make it particularly effective for handling complex image data, especially when image region boundaries are unclear or overlapping. The algorithm implementation typically includes functions for similarity matrix construction, iterative weight computation, and cluster extraction based on weight thresholds.

In image segmentation applications, the Dominant-set algorithm treats image pixels or superpixels as nodes, calculating similarities based on features like color and texture. The algorithm automatically determines the number of segmentation regions and effectively preserves semantic boundaries in images. Key implementation steps include feature extraction using methods like RGB/HSV color histograms or texture descriptors, similarity computation using Gaussian kernels, and dominant set extraction through iterative optimization.