Content deleted Content added
m Task 18 (cosmetic): eval 5 templates: del empty params (13×); hyphenate params (2×); |
m Open access bot: url-access updated in citation with #oabot. |
||
| (16 intermediate revisions by 12 users not shown) | |||
Line 1:
{{short description|Algorithm for labeling clusters on a grid}}
{{Machine learning bar}}
The '''Hoshen–Kopelman algorithm''' is a simple and efficient [[algorithm]] for labeling [[Cluster analysis|clusters]] on a grid, where the grid is a regular [[
== Percolation theory ==
[[Percolation theory]] is the study of the behavior and [[statistics]] of [[cluster analysis|clusters]] on [[Lattice graph|lattices]]. Suppose we have a large square lattice where each cell can be occupied with the [[probability]] <code>p</code> and can be empty with the probability <code>1 – ''p''</code>. Each group of neighboring occupied cells forms a cluster. Neighbors are defined as cells having a common side but not those sharing only a corner i.e. we consider the [[Pixel connectivity|4-connected neighborhood]] that is top, bottom, left and right. Each occupied cell is independent of the status of its neighborhood. The number of clusters, the size of each cluster and their distribution are important topics in percolation theory.
{| style="margin: auto;"
|-
| <gallery>
Occupied_Grids_P_%3D_0.24.png |
</gallery>||<gallery>
Occupied_Grids_P_%3D_0.64.png |
</gallery>|| Consider <code>5x5</code> grids in
|}
== Hoshen–Kopelman algorithm for cluster finding ==
In this algorithm, we scan through a grid looking for occupied cells and labeling them with cluster labels. The scanning process is called
== Union-find algorithm ==
This algorithm is
== Pseudocode ==
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
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]] 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 |access-date=2016-09-17}}</ref> On completion, the cluster labels may be found in <code>labels</code>. Not shown is the second raster scan of the grid needed to produce the example output. In that scan, the value at <code>label[x,y]</code> is replaced by <code>find(label[x,y])</code>.
'''Raster Scan and Labeling on the Grid'''
largest_label = 0;
label = zeros[n_columns, n_rows]
labels = [0:n_columns*n_rows] /* Array containing integers from 0 to the size of the image. */
for x in 0 to n_columns {
for y in 0 to n_rows {
if occupied[x, y] then
left =
above =
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. */
Line 49 ⟶ 52:
'''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];
Line 63 ⟶ 68:
x = z;
}
return y;
}
== Example ==
Consider the following example. The dark cells in the grid in
The algorithm processes the input grid, cell by cell, as follows: Let's say that grid is a two-dimensional array.
Line 79 ⟶ 85:
* <code>grid[1][4]</code> is occupied so check cell to the left and above, only the cell to the left is occupied so assign the label of a cell on the left to this cell <code>2</code>.
* <code>grid[1][5]</code> , <code>grid[2][0]</code> and <code>grid[2][1]</code> are unoccupied so they are not labeled.
* <code>grid[2][2]</code> is occupied so check cell to the left and above, only cell above is occupied so assign the label of the cell above to this cell <code>
* <code>grid[2][3]</code> , <code>grid[2][4]</code> and <code>grid[2][5]</code> are unoccupied so they are not labeled.
* <code>grid[3][0]</code> is occupied so check cell above which is unoccupied so we increment the current label value and assign the label to the cell as <code>4</code>.
Line 91 ⟶ 97:
* <code>grid[4][4]</code> is unoccupied so it is not labeled.
* <code>grid[4][5]</code> is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label <code>7</code>.
* <code>grid[5][0]</code> , <code>grid[5][1]</code> , <code>grid[5][2]</code> and <code>grid[5][3]</code> are unoccupied so they are not labeled.
* <code>grid[5][4]</code> is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label <code>8</code>.
* <code>grid[5][5]</code> is occupied so check cell to the left and above, both, cell to the left and above are occupied so merge the two clusters and assign the cluster label of the cell above to the cell on the left and to this cell i.e. <code>7</code>. (Merging using union algorithm will label all the cells with label <code>8</code> to <code>7</code>).
{| style="margin: auto;"
|-
| <gallery>
H-K algorithm Input.png |
</gallery>||<gallery>
H-K algorithm output.png |
</gallery>|| Consider <code>6x6</code> grids in figure (
|}
== Applications ==
* Determination of Nodal Domain Area and Nodal Line Lengths <ref>{{cite web|url=https://webhome.weizmann.ac.il/home/feamit/nodalweek/c_joas_nodalweek.pdf
* [[Connectivity (graph theory)|Nodal Connectivity Information]]
* Modeling of [[Electrical resistivity and conductivity|electrical conduction]]
| |||