DBSCANで点群データをクラスタリング

DBSCANとは

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）は、データの密集した領域をクラスタとして認識し、データポイント間の密度に基づいてクラスタリングを行うアルゴリズムです。このアルゴリズムは、クラスタの数を事前に指定する必要がなく、ノイズ（どのクラスタにも属さないデータポイント）の検出が可能です。

DBSCANの基本概念

DBSCANは2つのパラメータ、$ \epsilon $（eps）と$ \text{minPts} $を使用します。

• $ \epsilon $（eps）: あるポイントからこの距離以内にある点をそのポイントの近傍とみなす。
• $ \text{minPts} $: クラスタを形成するために必要な近傍点の最小数。

クラスタリングプロセスは以下のステップに従います：

1. 未訪問のポイントをランダムに選択します。
2. 選択したポイントの$ \epsilon $近傍内のポイントを見つけます。
3. 近傍内のポイント数が$ \text{minPts} $未満の場合、このポイントはノイズとしてマークされます。そうでない場合、新しいクラスタが作成されます。
4. 新しいクラスタ内の全ての点に対して、その近傍を見つけ、クラスタに追加します。このステップは、クラスタ内の全ての点の近傍が訪問されるまで続きます。
5. 全ての点が訪問されるまで、ステップ1から4を繰り返します。

OpenSiv3DにおけるDBSCANの実装例

# include <Siv3D.hpp>


struct Cluster {
	Array<size_t> indices;
};

using DBSCANResult = Array<Cluster>;

template <typename PointType>
Array<size_t> RegionQuery(const Array<PointType>& points, size_t index, double eps) {
	Array<size_t> neighbors;
	for (size_t i = 0; i < points.size(); ++i) {
		if (i == index) continue;
		if (points[i].distanceFrom(points[index]) <= eps) {
			neighbors << i;
		}
	}
	return neighbors;
}

template <typename PointType>
DBSCANResult DBSCAN(const Array<PointType>& points, double eps, size_t minPts) {
	Array<bool> visited(points.size(), false);
	DBSCANResult clusters;

	for (size_t i = 0; i < points.size(); ++i) {
		if (visited[i]) continue;
		visited[i] = true;

		Array<size_t> neighbors = RegionQuery(points, i, eps);

		if (neighbors.size() < minPts) continue;

		Cluster cluster;
		cluster.indices << i;

		for (size_t j = 0; j < neighbors.size(); ++j) {
			size_t pointIdx = neighbors[j];
			if (!visited[pointIdx]) {
				visited[pointIdx] = true;
				Array<size_t> pointNeighbors = RegionQuery(points, pointIdx, eps);
				if (pointNeighbors.size() >= minPts) {
					neighbors.append(pointNeighbors);
				}
			}
			if (!cluster.indices.includes(pointIdx)) {
				cluster.indices << pointIdx;
			}
		}
		clusters << cluster;
	}
	return clusters;
}


// 正規分布に基づいたVec2を生成する関数
Vec2 GenerateGaussianVec2(const Vec2& mean, double stddev, DefaultRNG& rng)
{
	NormalDistribution dist{ 0.0, stddev };
	double x = mean.x + dist(rng);
	double y = mean.y + dist(rng);
	return Vec2(x, y);
}

void DrawClusters(const Array<Vec2>& points, const DBSCANResult& result, const Font& font, double radius = 20.0)
{
	for (size_t i = 0; i < result.size(); ++i)
	{
		const Color col = HSV{ (i * 60), 0.5, 0.5 };
		for (const auto& index : result[i].indices)
		{
			Circle{ points[index], radius }.draw(col);
		}
	}
}

void DrawClusterMeans(const Array<Vec2>& points, const DBSCANResult& result, const Font& font)
{
	for (size_t i = 0; i < result.size(); ++i)
	{
		Vec2 mean;
		for (const auto& index : result[i].indices)
		{
			mean += points[index];
		}
		mean /= result[i].indices.size();
		mean.asCircle(40).draw(ColorF{ 0.95 }).drawFrame(2, ColorF{ 0.11 });
		font(i).drawAt(40, mean, ColorF{ 0.11 });
	}
}

void Main()
{
	Scene::SetBackground(ColorF{ 0.6, 0.8, 0.7 });
	const Rect canvasArea(0, 0, 600, 600);
	const Rect guiArea(620, 0, 200, 600);
	const Font font{ FontMethod::MSDF, 36, Typeface::Bold };

	Array<Vec2> points;
	auto& rng = GetDefaultRNG();
	DBSCANResult result;
	bool autoDBSCAN = true;
	double stddev = 10.0;
	double eps = 20.0;
	int minpts = 5;

	while (System::Update())
	{
		if (MouseL.pressed() && canvasArea.contains(Cursor::Pos()))
		{
			const Vec2 basePos = Cursor::PosF();
			for (size_t i = 0; i < 5; ++i)
			{
				const Vec2 pos = GenerateGaussianVec2(basePos, stddev, rng);
				points << pos;
			}
			if (autoDBSCAN)
			{
				result = DBSCAN(points, eps, minpts);
			}
		}

		if (SimpleGUI::CheckBox(autoDBSCAN, U"Auto DBSCAN", Vec2{ 620, 40 })
			|| SimpleGUI::Slider(U"eps:{:.0f}"_fmt(eps), eps, 10.0, 100.0, Vec2{ 620, 90 }, 80.0, 100.0))
		{
			result = DBSCAN(points, eps, minpts);
		}

		if (SimpleGUI::Button(U"Clear", Vec2{ 620, 140 }))
		{
			result.clear();
			points.clear();
		}

		canvasArea.draw(Palette::Gray);

		DrawClusters(points, result, font, eps);

		for (const auto& point : points)
		{
			Circle{ point, 2.0 }.draw(Palette::White);
		}

		DrawClusterMeans(points, result, font);
	}
}

提示されたコードは、OpenSiv3Dライブラリを用いた2次元空間内の点群に対するDBSCANの実装です。以下はその主要な関数と役割です：

• RegionQuery: 与えられた点の$ \epsilon $近傍内の全ての点のインデックスを返します。
• DBSCAN: DBSCANアルゴリズムを実行し、見つかったクラスタのリストを返します。
• GenerateGaussianVec2: 正規分布に基づいてランダムな点を生成します。
• DrawClusters と DrawClusterMeans: クラスタとクラスタの重心を描画します。

ユーザーはマウスを使用してクリックすることで、新しいデータポイントを生成し、autoDBSCANがtrueの場合、自動的にDBSCANアルゴリズムが実行されてクラスタリングを行います。

この実装は、点群データが手に入った際、例えばLiDARやRealsenseを使用した3Dスキャンから得られるデータにDBSCANを適用し、車、木、人などの異なる物体をクラスタとして識別するのに役立ちます。また、画像データなど他のタイプの情報にも適用可能です。

参考資料