Analysis of Kruskal's Algorithm for Segmenting Image

EasyChair Preprint 4987

Abstract

Clustering / segmentation is widely used in the field of data mining.  Pixel of the image is seen as a point and the edge is seen as the difference in intensity for two adjacent points. Then we determine the minimum spanning tree using Kruskal's algorithm. Edge that weight is greater than a threshold discarded, so that will be formed several sub tree. Threshold used to cut the minimum spanning tree generated by Kruskal's algorithm. Suppose S_T1 = {T₁₁, T₁₂, ..., T_1p}, S_T2 = {T₂₁, T₂₂, ..., T_2q}, respectively, is set of disjoint sub-tree of MST1, MST2 after the edge with the greater weight of the threshold is removed, and P(T_ij) is the set of points on sub tree T_ij, for i = 1, 2, dan j = 1, 2, ..., max{p,q}. Then p = q, and for each s Î {1, 2, ..., p}, there are  t Î {1, 2, ..., p} such that P(T_1s) = P(T_2t).

Keyphrases: Segmentation, Sub Tree, minimum spanning tree

@booklet{EasyChair:4987,
  author    = {Efron Manik},
  title     = {Analysis of Kruskal's Algorithm  for Segmenting Image},
  howpublished = {EasyChair Preprint 4987},
  year      = {EasyChair, 2021}}