El algoritmo de Hoshen-Kopelman es un algoritmo simple y eficiente para etiquetar conglomerados en una cuadrícula, donde la cuadrícula es una red regular de celdas, con celdas ocupadas o desocupadas. Este algoritmo se basa en un conocido algoritmo de búsqueda de uniones . [1] El algoritmo fue descrito originalmente por Joseph Hoshen y Raoul Kopelman en su artículo de 1976 "Percolation and Cluster Distribution. I. Cluster Multiple Labeling Technique and Critical Concentration Algorithm". [2]
La teoría de la percolación es el estudio del comportamiento y las estadísticas de los cúmulos en redes . Supongamos que tenemos una gran red cuadrada donde cada celda puede estar ocupada con la probabilidad p y puede estar vacía con la probabilidad . Cada grupo de celdas vecinas ocupadas forma un cúmulo. Los vecinos se definen como celdas que tienen un lado común pero no aquellas que comparten solo una esquina, es decir, consideramos el vecindario 4-conectado que es superior, inferior, izquierdo y derecho. Cada celda ocupada es independiente del estado de su vecindario. El número de cúmulos, el tamaño de cada cúmulo y su distribución son temas importantes en la teoría de la percolación.1 – p
En este algoritmo, escaneamos una cuadrícula en busca de celdas ocupadas y las etiquetamos con etiquetas de grupo. El proceso de escaneo se denomina escaneo raster . El algoritmo comienza escaneando la cuadrícula celda por celda y verificando si la celda está ocupada o no. Si la celda está ocupada, entonces debe etiquetarse con una etiqueta de grupo. Esta etiqueta de grupo se asigna en función de los vecinos de esa celda. (Para esto, vamos a utilizar el algoritmo Union-Find que se explica en la siguiente sección). Si la celda no tiene ningún vecino ocupado, entonces se le asigna una nueva etiqueta. [3]
Este algoritmo es un método simple para calcular clases de equivalencia . Al llamar a la función , union(x,y)se devuelve si los elementos xy yson miembros de la misma clase de equivalencia. Debido a que las relaciones de equivalencia son transitivas , todos los elementos equivalentes a xson equivalentes a todos los elementos equivalentes a y. Por lo tanto, para cualquier elemento x, hay un conjunto de elementos que son todos equivalentes a x(llamado la clase de equivalencia). Una segunda función find(x)devuelve un miembro representativo de la clase de equivalencia a la que xpertenece.
Durante el escaneo de la cuadrícula, cada vez que se encuentra una celda ocupada, se escanean las celdas vecinas para verificar si alguna de ellas ya ha sido escaneada. Si encontramos celdas vecinas ya escaneadas, unionse realiza la operación para especificar que estas celdas vecinas son, de hecho, miembros de la misma clase de equivalencia. Luego, findse realiza la operación para encontrar un miembro representativo de esa clase de equivalencia con el que se etiquetará la celda actual.
Por otro lado, si la celda actual no tiene vecinas, se le asigna una nueva etiqueta que no se haya utilizado anteriormente. De esta manera se procesa toda la cuadrícula.
El siguiente pseudocódigo hace referencia a la implementación del mismo algoritmo por parte de Tobin Fricke. [3]
Escaneo de trama y etiquetado en la cuadrículaetiqueta_más_grande = 0;etiqueta = ceros[n_columnas, n_filas]etiquetas = [0:n_columnas*n_filas] /* Matriz que contiene números enteros desde 0 hasta el tamaño de la imagen. */para x en 0 a n_columnas { para y en 0 a n_filas { si está ocupado[x, y] entonces izquierda = etiqueta[x-1, y]; arriba = etiqueta[x, y-1]; si (izquierda == 0) y (arriba == 0) entonces /* Ni una etiqueta arriba ni a la izquierda. */ largest_label = largest_label + 1; /* Crea una nueva etiqueta de clúster aún no utilizada. */ etiqueta[x, y] = etiqueta_más_grande; de lo contrario si (izquierda != 0) y (arriba == 0) entonces /* Un vecino, a la izquierda. */ etiqueta[x, y] = buscar(izquierda); de lo contrario si (izquierda == 0) y (arriba != 0) entonces /* Un vecino, arriba. */ etiqueta[x, y] = buscar(arriba); else /* Vecinos TANTO a la izquierda como a arriba. */ union(left,above); /* Vincula los clústeres izquierdo y superior. */ etiqueta[x, y] = buscar(izquierda); }}Uniónanular unión(int x, int y) { etiquetas[find(x)] = find(y);}Encontrarint buscar(int x) { int y = x; mientras (etiquetas[y] != y) y = etiquetas[y]; mientras (etiquetas[x] != x) { int z = etiquetas[x]; etiquetas[x] = y; x = z; } devuelve y;}Considere el siguiente ejemplo. Las celdas oscuras en la cuadrícula figure (a)representan que están ocupadas y las blancas están vacías. Por lo tanto, al ejecutar el algoritmo H–K en esta entrada, obtendríamos el resultado que se muestra en figure (b)con todos los clústeres etiquetados.
El algoritmo procesa la cuadrícula de entrada, celda por celda, de la siguiente manera: Digamos que la cuadrícula es una matriz bidimensional.
grid[0][0]es decir, la primera celda. La celda está ocupada y no tiene celdas a la izquierda o arriba, por lo que etiquetaremos esta celda con una nueva etiqueta, por ejemplo 1.grid[0][1]y grid[0][2]ambos están desocupados por lo que no están etiquetados.grid[0][3]está ocupado, así que verifique la celda a la izquierda que está desocupada, por lo que incrementamos el valor de la etiqueta actual y asignamos la etiqueta a la celda como 2.grid[0][4], grid[0][5]y grid[1][0]están desocupados por lo que no están etiquetados.grid[1][1]está ocupado, así que verifique las celdas a la izquierda y arriba, ambas celdas están desocupadas, así que asigne una nueva etiqueta 3.grid[1][2]está ocupado, así que verifique la celda a la izquierda y arriba, solo la celda a la izquierda está ocupada, así que asigne la etiqueta de una celda a la izquierda a esta celda 3.grid[1][3]está ocupado, así que verifique las celdas de la izquierda y de arriba; ambas celdas están ocupadas, así que fusione los dos grupos y asigne la etiqueta del grupo de la celda de arriba a la celda de la izquierda y a esta celda, es decir 2. (La fusión mediante el algoritmo de unión etiquetará todas las celdas con la etiqueta 3como 2)grid[1][4]está ocupado, así que verifique la celda a la izquierda y arriba, solo la celda a la izquierda está ocupada, así que asigne la etiqueta de una celda a la izquierda a esta celda 2.grid[1][5], grid[2][0]y grid[2][1]están desocupados por lo que no están etiquetados.grid[2][2]está ocupado, así que verifique la celda a la izquierda y arriba, solo la celda de arriba está ocupada, así que asigne la etiqueta de la celda de arriba a esta celda 2.grid[2][3], grid[2][4]y grid[2][5]están desocupados por lo que no están etiquetados.grid[3][0]está ocupado, así que verifique la celda encima que está desocupada, por lo que incrementamos el valor de la etiqueta actual y asignamos la etiqueta a la celda como 4.grid[3][1]está ocupado, así que verifique la celda a la izquierda y arriba, solo la celda a la izquierda está ocupada, así que asigne la etiqueta de la celda de la izquierda a esta celda 4.grid[3][2]Está desocupado por lo que no está etiquetado.grid[3][3]está ocupado, así que verifique las celdas a la izquierda y arriba, ambas celdas están desocupadas, así que asigne una nueva etiqueta 5.grid[3][4]está ocupado, así que verifique la celda a la izquierda y arriba, solo la celda a la izquierda está ocupada, así que asigne la etiqueta de la celda de la izquierda a esta celda 5.grid[3][5], grid[4][0]y grid[4][1]están desocupados por lo que no están etiquetados.grid[4][2]está ocupado, así que verifique las celdas a la izquierda y arriba, ambas celdas están desocupadas, así que asigne una nueva etiqueta 6.grid[4][3]está ocupado, así que verifique la celda a la izquierda y arriba, ambas, la celda a la izquierda y arriba están ocupadas, así que combine los dos grupos y asigne la etiqueta del grupo de la celda de arriba a la celda de la izquierda y a esta celda, es decir 5. (Combinar usando el algoritmo de unión etiquetará todas las celdas con la etiqueta 6a 5).grid[4][4]Está desocupado por lo que no está etiquetado.grid[4][5]está ocupado, así que verifique las celdas a la izquierda y arriba, ambas celdas están desocupadas, así que asigne una nueva etiqueta 7.grid[5][0], grid[5][1], grid[5][2]y grid[5][3]están desocupados por lo que no están etiquetados.grid[5][4]está ocupado, así que verifique las celdas a la izquierda y arriba, ambas celdas están desocupadas, así que asigne una nueva etiqueta 8.grid[5][5]está ocupado, así que verifique la celda a la izquierda y arriba, ambas, la celda a la izquierda y arriba están ocupadas, así que combine los dos grupos y asigne la etiqueta del grupo de la celda de arriba a la celda de la izquierda y a esta celda, es decir 7. (Combinar usando el algoritmo de unión etiquetará todas las celdas con la etiqueta 8a 7).