FoF（friends-of-friends）アルゴリズムを2値画像に適用してみた

はじめに

FoF（friends-of-friends）アルゴリズムは、点群データに対するクラスタリング手法としてよく知られています。以下の記事で紹介されているように、距離の敷居値 $r$ を一つ決め、「近い点同士をつないでいく」だけの非常に単純なアルゴリズムです。

一方、画像処理では、2 値化画像に対して 4近傍・8近傍といった近傍定義に基づく連結成分解析が広く用いられています（記事参照）。

実は、2 値化画像も前景ピクセルを点集合として見れば、FoF をそのまま適用できます。また、4近傍・8近傍連結は、FoF における距離 $r$ を特定の値に固定した特殊な場合として捉えることもできます。この記事では、FoF を点群ではなく画像に適用する例を紹介します。

本記事の実装コードは、Google Colab こちら からも実行できます。

2値画像を用意する

まず、画像内に 3 つの点群クラスタを作り、それを 2 値画像として表現します。各クラスタの点数はポアソン揺らぎに従い、完全にランダムではないが、ある程度の構造を持つ画像になります。

import numpy as np
import matplotlib.pyplot as plt

SEED = 11
H, W = 64, 64
N_CLUSTER = 3
LAMBDA = 100
SIGMA = 3.0

rng = np.random.default_rng(SEED)

points = []
centers = rng.uniform(10, H-10, size=(N_CLUSTER, 2))

for cy, cx in centers:
    n = rng.poisson(LAMBDA)
    ys = rng.normal(cy, SIGMA, n)
    xs = rng.normal(cx, SIGMA, n)
    points.append(np.column_stack([ys, xs]))

points = np.vstack(points)

binary = np.zeros((H, W), dtype=int)
ys = points[:, 0].astype(int)
xs = points[:, 1].astype(int)

mask = (0 <= ys) & (ys < H) & (0 <= xs) & (xs < W)
binary[ys[mask], xs[mask]] = 1

plt.imshow(binary, cmap="gray", interpolation="nearest")
plt.xticks([]); plt.yticks([])
plt.show()

白い部分を前景、黒い部分を背景とします。ここでは、この前景ピクセルを FoF で分類します。

FoF を画像に適用する

前景ピクセルを点群として取り出し、FoF を実行します。やっていることは、点群データに対する FoF と全く同じです。ここでは、4 種類の半径 $r = 1, \sqrt{2}, 3, 5$ を用意して実行します。

from scipy.spatial import cKDTree

def fof_binary(binary, r):
    ys, xs = np.where(binary > 0)
    pts = np.column_stack([xs, ys])

    tree = cKDTree(pts)
    labels = np.zeros(len(pts), dtype=int)
    visited = np.zeros(len(pts), dtype=bool)

    lab = 1
    for i in range(len(pts)):
        if visited[i]:
            continue
        stack = [i]
        while stack:
            j = stack.pop()
            if visited[j]:
                continue
            visited[j] = True
            labels[j] = lab
            for k in tree.query_ball_point(pts[j], r):
                if not visited[k]:
                    stack.append(k)
        lab += 1

    img = np.zeros(binary.shape, dtype=int)
    for (x, y), l in zip(pts, labels):
        img[y, x] = l

    return img


r_list = [1.0, np.sqrt(2), 3.0, 5.0]
fig, axes = plt.subplots(1, len(r_list), figsize=(10, 3))

for ax, r in zip(axes, r_list):
    img = fof_binary(binary, r)
    ax.imshow(img, cmap="tab20", interpolation="nearest")
    ax.set_title(f"r = {r}")
    ax.set_xticks([]); ax.set_yticks([])

plt.tight_layout()
plt.show()

同じ色で表示されている領域が、一つのクラスタに対応します（カラーマップは 20 色のみのため、異なるクラスタが同じ色になる場合があります）。

距離 $r = 1$ の場合、上下左右のピクセルのみが連結されるため、これは 4近傍連結に対応します。
次に $r = \sqrt{2}$ とすると、斜め方向のピクセルも連結対象に含まれ、8近傍連結に対応します。
つまり、4近傍・8近傍は、FoF における距離 $r$ を特定の値に固定した、非常に特殊な場合と考えることもできます。

さらに $r$ を大きくしていくと、同一クラスタ内の点はより強く結合され、やがて空間的に離れていたクラスタ同士も連結され始めます。このように FoF では、距離 $r$ がそのまま「どこまでを同じクラスタとみなすか」という定義になっていることが分かります。

おわりに

FoF は点群データだけでなく、2 値画像にもそのまま適用できます。画像を点集合として見るだけでよく、4近傍・8近傍は FoF の特別な場合と考えられます。本記事の例が、FoF を画像として眺める一つの参考になれば幸いです。

関連記事