Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 11:16, 27 November 2019

Revision as of 15:32, 31 December 2019

Line 22:

This algorithm is a simple method for computing [[equivalence class]]es. Calling the function <code>union(x,y)</code> specifies that, items <code>x</code> and <code>y</code> are members of the same equivalence class. Because equivalence relations are [[Transitive relation|transitive]]; all the items equivalent to <code>x</code> are equivalent to all the items equivalent to <code>y</code>. Thus for any item <code>x</code>, there is a set of items which are all equivalent to <code>x</code> . This set is the equivalence class of which <code>x</code> is a member. A second function <code>find(x)</code> returns a representative member of the equivalence class to which <code>x</code> belongs.

== Pseudo-codePseudocode ==

During the [[raster scan]] of the grid, whenever an occupied cell is encountered, neighboring cells are scanned to check whether any of them have already been scanned. If we find already scanned neighbors, the <code>union</code> operation is performed, to specify that these neighboring cells are in fact members of the same equivalence class. Then the<code>find</code> operation is performed to find a representative member of that equivalence class with which the current cell will be labeled.

On the other hand, if the current cell has no neighbors, it is assigned a new, previously unused, label. The entire grid is processed in this way.

Following [[Pseudocode|pseudo-codepseudocode]] is referred from [https://www.ocf.berkeley.edu/~fricke/ Tobin Fricke's] implementation of the same algorithm.<ref name=":0">{{cite web|url=https://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html |title=The Hoshen-Kopelman Algorithm for cluster identification|first=Tobin |last=Fricke |website=ocf.berkeley.edu |date=2004-04-21 |accessdate=2016-09-17}}</ref>

'''Raster Scan and Labeling on the Grid'''

largest_label = 0;

for x in 0 to n_columns {

for y in 0 to n_rows {

if occupied[x, y] then

left = occupied[x-1, y];

above = occupied[x, y-1];

if (left == 0) and (above == 0) then /* Neither a label above nor to the left. */

largest_label = largest_label + 1; /* Make a new, as-yet-unused cluster label. */

label[x, y] = largest_label;

else if (left != 0) and (above == 0) then /* One neighbor, to the left. */

label[x, y] = find(left);

else if (left == 0) and (above != 0) then /* One neighbor, above. */

label[x, y] = find(above);

else /* Neighbors BOTH to the left and above. */

union(left,above); /* Link the left and above clusters. */

label[x, y] = find(left);

}

}

}

'''Union'''

void union(int x, int y) {

labels[find(x)] = find(y);

}

}

'''Find'''

int find(int x) {

int y = x;

while (labels[y] != y)

y = labels[y];

while (labels[x] != x) {

int z = labels[x];

labels[x] = y;

x = z;

}

return y;

}

}

== Example ==