Алгоритм Хошена – Копельмана

Алгоритм Хошена-Копельмана — это простой и эффективный алгоритм маркировки кластеров в сетке, где сетка представляет собой регулярную сеть ячеек, причем ячейки либо заняты, либо незаняты. Этот алгоритм основан на известном алгоритме поиска объединений . ^{[ 1 ]} Алгоритм был первоначально описан Джозефом Хошеном и Раулем Копельманом в их статье 1976 года «Перколяция и кластерное распределение. I. Метод множественной маркировки кластеров и алгоритм критической концентрации». ^{[ 2 ]}

Теория перколяции

Теория перколяции это изучение поведения и статистики кластеров — на решетках . Предположим, у нас есть большая квадратная решетка, каждая ячейка которой может быть занята с вероятностью p и может быть пустым с вероятностью 1 – p. Каждая группа соседних занятых ячеек образует кластер. Соседи определяются как ячейки, имеющие общую сторону, но не те, которые имеют общий только угол, т.е. мы рассматриваем 4-связную окрестность : верхнюю, нижнюю, левую и правую. Каждая занятая ячейка не зависит от статуса ее окрестности. Количество кластеров, размер каждого кластера и их распределение являются важными темами теории перколяции.

Рисунок (а)

Рисунок (б)

Учитывать 5x5 сетки на рисунках (а) и (б).
На рисунке (а) вероятность занятости равна p = 6/25 = 0.24.
На рисунке (б) вероятность занятости равна p = 16/25 = 0.64.

Алгоритм Хошена – Копельмана для поиска кластеров

В этом алгоритме мы просматриваем сетку в поисках занятых ячеек и помечаем их метками кластеров. Процесс сканирования называется растровым сканированием . Алгоритм начинается со сканирования ячейки сетки за ячейкой и проверки, занята ячейка или нет. Если ячейка занята, то ее необходимо пометить меткой кластера. Эта метка кластера назначается на основе соседей этой ячейки. (Для этого мы собираемся использовать алгоритм Union-Find , который объясняется в следующем разделе.) Если у ячейки нет занятых соседей, то ячейке присваивается новая метка. ^{[ 3 ]}

Алгоритм поиска объединения

Этот алгоритм представляет собой простой метод вычисления классов эквивалентности . Вызов функции union(x,y) возвращает ли элементы x и y являются членами одного и того же класса эквивалентности. Поскольку отношения эквивалентности транзитивны , все элементы, эквивалентные x эквивалентны всем элементам, эквивалентным y. Таким образом, для любого предмета x, существует набор элементов, которые эквивалентны x (называемый классом эквивалентности). Вторая функция find(x) возвращает представительный член класса эквивалентности, которому x принадлежит.

Псевдокод

При растровом сканировании сетки всякий раз, когда встречается занятая ячейка, сканируются соседние ячейки, чтобы проверить, не сканировалась ли какая-либо из них уже. Если мы найдем уже просканированных соседей, union выполняется операция, чтобы указать, что эти соседние ячейки фактически являются членами одного и того же класса эквивалентности. Тогда find операция выполняется для поиска репрезентативного члена того класса эквивалентности, которым будет помечена текущая ячейка.

С другой стороны, если у текущей ячейки нет соседей, ей присваивается новая, ранее неиспользованная метка. Таким образом обрабатывается вся сетка.

Следующий псевдокод взят из Тобина Фрике . реализации того же алгоритма ^{[ 3 ]}

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 = label[x-1, y];
            above = label[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;
}

Пример

Рассмотрим следующий пример. Темные ячейки в сетке figure (a) означают, что они заняты, а белые пусты. Таким образом, запустив алгоритм H–K на этом входе, мы получим результат, как показано на рисунке. figure (b) со всеми помеченными кластерами.

Алгоритм обрабатывает входную сетку ячейку за ячейкой следующим образом: Допустим, сетка представляет собой двумерный массив.

Начиная с ячейки grid[0][0] т.е. первая ячейка. Ячейка занята, и в ней нет ячеек слева или сверху, поэтому мы пометим эту ячейку новой меткой, например 1.
grid[0][1] и grid[0][2] оба незаняты, поэтому они не помечены.
grid[0][3] занято, поэтому проверьте ячейку слева, которая незанята, поэтому мы увеличиваем текущее значение метки и присваиваем метку ячейке как 2.
grid[0][4], grid[0][5] и grid[1][0] незаняты, поэтому они не помечены.
grid[1][1] занято, поэтому проверьте ячейку слева и выше, обе ячейки незаняты, поэтому назначьте новую метку 3.
grid[1][2] занята, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева 3.
grid[1][3] занято, поэтому проверьте ячейку слева и выше, обе ячейки заняты, поэтому объедините два кластера и назначьте метку кластера ячейки выше ячейке слева и этой ячейке, т.е. 2. (При слиянии с использованием алгоритма объединения все ячейки будут помечены меткой 3 к 2)
grid[1][4] занята, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева 2.
grid[1][5] , grid[2][0] и grid[2][1] незаняты, поэтому они не помечены.
grid[2][2] занято, поэтому проверьте ячейку слева и выше, занята только ячейка выше, поэтому присвойте этой ячейке метку ячейки выше 2.
grid[2][3] , grid[2][4] и grid[2][5] незаняты, поэтому они не помечены.
grid[3][0] занято, поэтому проверьте ячейку выше, которая незанята, поэтому мы увеличиваем текущее значение метки и присваиваем метку ячейке как 4.
grid[3][1] занята, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева 4.
grid[3][2] пуст, поэтому не помечен.
grid[3][3] занято, поэтому проверьте ячейку слева и выше, обе ячейки незаняты, поэтому назначьте новую метку 5.
grid[3][4] занята, поэтому проверьте ячейку слева и выше, занята только ячейка слева, поэтому присвойте этой ячейке метку ячейки слева 5.
grid[3][5] , grid[4][0] и grid[4][1] незаняты, поэтому они не помечены.
grid[4][2] занято, поэтому проверьте ячейку слева и выше, обе ячейки незаняты, поэтому назначьте новую метку 6.
grid[4][3] занято, поэтому проверьте ячейку слева и выше, обе ячейки слева и выше заняты, поэтому объедините два кластера и назначьте метку кластера ячейки выше ячейке слева и этой ячейке, т.е. 5. (При слиянии с использованием алгоритма объединения все ячейки будут помечены меткой 6 к 5).
grid[4][4] пуст, поэтому не помечен.
grid[4][5] занято, поэтому проверьте ячейку слева и выше, обе ячейки незаняты, поэтому назначьте новую метку 7.
grid[5][0] , grid[5][1] , grid[5][2] и grid[5][3] незаняты, поэтому они не помечены.
grid[5][4] занято, поэтому проверьте ячейку слева и выше, обе ячейки незаняты, поэтому назначьте новую метку 8.
grid[5][5] занято, поэтому проверьте ячейку слева и выше, обе ячейки слева и выше заняты, поэтому объедините два кластера и назначьте метку кластера ячейки выше ячейке слева и этой ячейке, т.е. 7. (При слиянии с использованием алгоритма объединения все ячейки будут помечены меткой 8 к 7).

Рисунок (а)

Рисунок (б)

Учитывать 6x6 сетки на рисунках (а) и (б).
Рисунок (а). Это входные данные для алгоритма Хошена – Копельмана.
Рисунок (b). Это результат работы алгоритма со всеми помеченными кластерами.

Приложения

Определение площади узловых доменов и длин узловых линий ^{[ 4 ]}
Информация об узловом соединении
Моделирование электропроводности

См. также

Алгоритм кластеризации K-средних
Алгоритм нечеткой кластеризации
Алгоритм кластеризации по Гауссу ( максимизация ожиданий )
Методы кластеризации ^{[ 5 ]}
Алгоритм кластеризации C-средних ^{[ 6 ]}
Маркировка подключенных компонентов

Ссылки

^ https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf ^{[ только URL-адрес PDF ]}
^ Хошен, Дж.; Копельман, Р. (15 октября 1976 г.). «Перколяция и кластерное распределение. I. Методика множественной маркировки кластеров и алгоритм критической концентрации» . Физ. Преподобный Б. 14 (8): 3438–3445. Бибкод : 1976PhRvB..14.3438H . doi : 10.1103/PhysRevB.14.3438 – через APS.
^ Перейти обратно: ^а ^б Фрике, Тобин (21 апреля 2004 г.). «Алгоритм Хошена-Копельмана для идентификации кластеров» . ocf.berkeley.edu . Проверено 17 сентября 2016 г.
^ Кристиан Джоас. «Введение в алгоритм Хошена-Копельмана и его применение к статистике узловых областей» (PDF) . Webhome.weizmann.ac.il . Проверено 17 сентября 2016 г.
^ «Кластеризация» (PDF) .
^ «Нечеткая кластеризация c-средств» .

[1] ttps://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf ^{[ только URL-адрес PDF ]}

[2] Хошен, Дж.; Копельман, Р. (15 октября 1976 г.). «Перколяция и кластерное распределение. I. Методика множественной маркировки кластеров и алгоритм критической концентрации» . Физ. Преподобный Б. 14 (8): 3438–3445. Бибкод : 1976PhRvB..14.3438H . doi : 10.1103/PhysRevB.14.3438 – через APS.

[:0-3] Перейти обратно: ^а ^б Фрике, Тобин (21 апреля 2004 г.). «Алгоритм Хошена-Копельмана для идентификации кластеров» . ocf.berkeley.edu . Проверено 17 сентября 2016 г.

[4] Кристиан Джоас. «Введение в алгоритм Хошена-Копельмана и его применение к статистике узловых областей» (PDF) . Webhome.weizmann.ac.il . Проверено 17 сентября 2016 г.

[5] «Кластеризация» (PDF) .

[6] «Нечеткая кластеризация c-средств» .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]