Download PDFOpen PDF in browser

Analysis of Kruskal's Algorithm for Segmenting Image

EasyChair Preprint no. 4987

11 pagesDate: February 8, 2021


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 ST1 = {T11, T12, ..., T1p}, ST2 = {T21, T22, ..., T2q}, respectively, is set of disjoint sub-tree of MST1, MST2 after the edge with the greater weight of the threshold is removed, and P(Tij) is the set of points on sub tree Tij, 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(T1s) = P(T2t).

Keyphrases: minimum spanning tree, Segmentation, Sub Tree

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Efron Manik},
  title = {Analysis of Kruskal's Algorithm  for Segmenting Image},
  howpublished = {EasyChair Preprint no. 4987},

  year = {EasyChair, 2021}}
Download PDFOpen PDF in browser