2012/06/18 by Jiabing Wang, Wang, Jiabing, Jiaye Chen +1
Computer Science · #Advanced Image and Video Retrieval Techniques #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Medical Image Segmentation Techniques #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1206.4605
ICML2012
arxiv created 2012/06/18 · openalex publication_date 2012/06/18 · arxiv updated 2012/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a weighted and complete graph G = (V, E), V denotes the set of n objects to be clustered, and the weight d(u, v) associated with an edge (u, v) belonging to E denotes the dissimilarity between objects u and v. The diameter of a cluster is the maximum dissimilarity between pairs of objects in the cluster, and the split of a cluster is the minimum dissimilarity between objects within the cluster and objects outside the cluster. In this paper, we propose a new criterion for measuring the goodness of clusters: the ratio of the minimum split to the maximum diameter, and the objective is to maximize the ratio. For k = 2, we present an exact algorithm. For k >= 3, we prove that the problem is NP-hard and present a factor of 2 approximation algorithm on the precondition that the weights associated with E satisfy the triangle inequality. The worst-case runtime of both algorithms is O(n3). We compare the proposed algorithms with the Normalized Cut by applying them to image segmentation. The experimental results on both natural and synthetic images demonstrate the effectiveness of the proposed algorithms.