Projeler · Proje 5

3B nokta bulutunu kümeleme

Robotun LiDAR taramasında nesneleri etiket görmeden ayırmak: k-ortalamalar, DBSCAN ve PCA

Senaryo. Depoda duran bir robotun döner LiDAR’ı çevresini 360° tarar ve bir nokta bulutu üretir: zemindeki halkalar, bir koli yığını, bir varil, bir insan, bir palet ve bir dolap; havada da birkaç sahte yansıma. Robot hangi noktanın hangi nesneye ait olduğunu bilmez. Çarpmadan dolaşmak için önce bu noktaları nesnelere ayırması gerekir.

Amaç. Beş nesnenin beşini de ayrı birer küme olarak bulmak: her nesnenin noktalarının en az %90’ı tek bir kümede, o kümenin de en az %90’ı o nesne olmalı. Sahte yansımalar hiçbir nesneye katılmamalı.

3B sahne yükleniyor…

tarama: 0 / 1640 nokta

Sürükle: döndür · iki parmak / tekerlek: yakınlaş

Algoritma: 0 k-ortalamalar, 1 DBSCAN 1DBSCAN yarıçapı eps (m) 0.35k-ortalamalar küme sayısı k 5PCA: 0 kapalı (3B), 1 açık (2B) 0Tohum 7

Eğitim paneli

Eğitim çalıştırılıyor…

Model bu sayfada, tarayıcında sıfırdan eğitilir (sabit tohum: aynı ayarlarla her seferinde aynı sonuç). Eğitim her karede küçük parçalar hâlinde yapılır; sekme ya da sahne görünmezken durur.

Adımlar

Tarama: ışın döndükçe noktalar açı sırasıyla gelir. Her nokta yalnız üç sayıdır (x, y, z); renk, etiket ya da nesne adı yok.
Zemin ayıklama: 0,08 m’nin altındaki her nokta zemin sayılır ve atılır. Bulutun yarısından fazlası zemindir; atılmazsa bütün nesneleri birbirine bağlayan dev bir küme olur.
PCA (isteğe bağlı): kalan noktaların kovaryans matrisi çıkarılır, özvektörleri en çok yayılan yönlerdir. Bu sahnede ilk iki yön yatay düzleme yakındır; yükseklik en az bilgiyi taşır ve atılır. Bulut gözünün önünde iki boyuta yassılır.
k-ortalamalar: k merkez seçilir, her nokta en yakın merkeze katılır, merkez kendi noktalarının ortalamasına taşınır; hiçbir atama değişmeyene kadar. Kötü bir başlangıç iki nesneyi tek kümede birleştirebilir; bu yüzden 10 başlangıç denenir ve en sıkısı oynatılır. Her nokta bir kümeye girmek zorundadır, sahte yansımalar da.
DBSCAN: eps yarıçaplı kürede en az 6 komşusu olan nokta çekirdektir. Küme bir çekirdekten başlar ve çekirdekten çekirdeğe genişler. Hiçbir kümeye ulaşmayan nokta gürültüdür; küme sayısını kimse söylemez.
Ölçüm: her nesne en çok örtüştüğü kümeyle eşleşir. Tablo satırlarda gerçek nesneleri, sütunlarda bulunan kümeleri sayar; köşegen ne kadar doluysa ayırma o kadar iyidir.

Model

Yükseklik eşiğiyle zemin ayıklama, sonra iki kümeleme algoritmasından biri: k-ortalamalar (k-ortalamalar++ başlangıcı, Lloyd turları) ya da DBSCAN (yoğunluk tabanlı, eps yarıçapı, en az 6 komşu). İkisi de kursun 2B derslerinin 3B genellemesidir. PCA açıkken kovaryans matrisinin özvektörleri bulunur ve nokta bulutu en çok değişen iki yöne izdüşürülür; kümeleme bu iki sayı üzerinde yapılır.

Kullanılan dersler: k-means: etiketsiz gruplar · DBSCAN: yoğunluğa göre kümeler · Temel bileşen analizi (PCA)

Kendin dene

Algoritmayı DBSCAN bırak, eps’i 0,35’ten 0,15’e indir. Komşu kürelerin içi boşalır: her nesne parçalara bölünür, 20’den fazla küçük küme ve 160’tan fazla gürültü noktası çıkar, bulunan nesne sayısı 0’a düşer. Sonra eps’i 1’e çıkar: nesneler yine ayrı kalır çünkü aralarında metrelerce boşluk var, ama sahte yansımaların bir kısmı nesnelere yapışır.
Algoritmayı k-ortalamalar yap (algo 0) ve k = 5 ile beş nesnenin beşini de bul. Sonra k’yı 3 yap: komşu nesneler aynı kümede birleşir ve en fazla 2 nesne bulunur. k-ortalamalar gürültü bilmez; her sahte yansıma bir nesneye eklenir.
PCA’yı aç (pca 1). İlk iki bileşen varyansın %98’inden fazlasını taşır; bulut yassılır ve DBSCAN aynı eps ile yine beş nesneyi de bulur. Üç sayı yerine iki sayı yetti, çünkü bu depoda nesneler üst üste değil yan yana duruyor.

Python karşılığı

nokta_bulutu.pypython

import numpy as np
tarama = np.genfromtxt('lidar-3b.csv', delimiter=',', skip_header=1)[:, :3] # (N, 3) nokta, metre: x ileri, y sol, z yukarı
P = tarama[tarama[:, 2] > 0.08] # zemini at
mu = P.mean(0)
val, vec = np.linalg.eigh(np.cov((P - mu).T)) # kovaryansın özvektörleri
val, vec = val[::-1], vec[:, ::-1] # büyükten küçüğe
print("açıklanan varyans", val / val.sum())
Z = (P - mu) @ vec[:, :2] # PCA: 3 sayıdan 2 sayıya
def kmeans(X, k, rng):
C = X[rng.choice(len(X), k, replace=False)] # rastgele merkezler
while True:
g = ((X[:, None] - C) ** 2).sum(2).argmin(1) # en yakın merkez
C2 = np.array([X[g == j].mean(0) for j in range(k)]) # grubun ortalaması
if np.allclose(C, C2): return g
C = C2
def dbscan(X, eps=0.35, min_pts=6):
D = ((X[:, None] - X) ** 2).sum(2) <= eps ** 2 # eps küresindeki komşular
core = D.sum(1) >= min_pts # çekirdek noktalar
g, k = np.full(len(X), -1), 0 # -1: gürültü
for i in np.flatnonzero(core):
if g[i] != -1: continue
g[i], kuyruk = k, [i] # yeni küme
while kuyruk:
j = kuyruk.pop()
if not core[j]: continue # sınır noktası genişlemez
for t in np.flatnonzero(D[j] & (g == -1)):
g[t] = k; kuyruk.append(t)
k += 1
return g
etiket = dbscan(P) # ya da kmeans(Z, 5, np.random.default_rng(0))
def siluet(X, g): # ortalama siluet skoru (gürültü hariç)
X, g = X[g >= 0], g[g >= 0]
L = np.unique(g)
if len(L) < 2: return 0.0
D = np.sqrt(((X[:, None] - X) ** 2).sum(2))
ort = np.stack([D[:, g == l].sum(1) / np.maximum(1, (g == l).sum() - (g == l)) for l in L], 1) # her kümeye ortalama uzaklık
a = ort[np.arange(len(g)), np.searchsorted(L, g)] # kendi kümesi
b = np.where(L[None] == g[:, None], np.inf, ort).min(1) # en yakın diğer küme
return float(np.mean((b - a) / np.maximum(a, b)))
history = {'eps': [], 'clusters': [], 'noise_share': [], 'silhouette': []} # geçmiş: eps taraması
for e in (0.2, 0.3, 0.35, 0.4, 0.5, 0.6):
g = dbscan(P, eps=e)
history['eps'].append(e); history['clusters'].append(int(g.max() + 1))
history['noise_share'].append(float((g < 0).mean())); history['silhouette'].append(siluet(P, g))
for row in zip(*history.values()): print(' '.join(f'{k}={v:.3f}' for k, v in zip(history, row))) # tablo
import csv
with open('egitim_gecmisi.csv', 'w', newline='') as f: # geçmişi CSV'ye yaz
csv.writer(f).writerows([list(history), *zip(*history.values())])
try:
import matplotlib.pyplot as plt # varsa grafik çiz
fig, (a1, a2) = plt.subplots(1, 2, figsize=(9, 3.5))
a1.plot(history['eps'], history['clusters'], 'o-'); a1.set_xlabel('eps'); a1.set_ylabel('clusters')
a2.scatter(P[:, 0], P[:, 1], c=etiket, s=4, cmap='tab10'); a2.set_aspect('equal') # kümeler (üstten görünüş)
plt.show()
except ImportError:
print('matplotlib yok: grafik atlandı')

Veri seti

Tüm veri setleri →

Depo taraması (3B nokta bulutu)lidar-3b.csv · 1640 satır · 4 sütun
Veri setini indir

Kodu tarayıcıda çalıştırPython · NumPy · matplotlib · Pyodide

Python ve NumPy bu sayfada, tarayıcında çalışır (Pyodide). Kodu değiştirip yeniden çalıştırabilirsin; dersin veri setleri çalışma klasöründe hazır. Kod matplotlib kullanırsa grafikler çıktının altında görünür, yazdığı dosyalar (ör. egitim_gecmisi.csv) indirilebilir.

nokta_bulutu.pypython

import numpy as np
tarama = np.genfromtxt('lidar-3b.csv', delimiter=',', skip_header=1)[:, :3]  # (N, 3) nokta, metre: x ileri, y sol, z yukarı
P = tarama[tarama[:, 2] > 0.08]               # zemini at
mu = P.mean(0)
val, vec = np.linalg.eigh(np.cov((P - mu).T))  # kovaryansın özvektörleri
val, vec = val[::-1], vec[:, ::-1]            # büyükten küçüğe
print("açıklanan varyans", val / val.sum())
Z = (P - mu) @ vec[:, :2]                     # PCA: 3 sayıdan 2 sayıya
def kmeans(X, k, rng):
    C = X[rng.choice(len(X), k, replace=False)]  # rastgele merkezler
    while True:
        g = ((X[:, None] - C) ** 2).sum(2).argmin(1)  # en yakın merkez
        C2 = np.array([X[g == j].mean(0) for j in range(k)])  # grubun ortalaması
        if np.allclose(C, C2): return g
        C = C2
def dbscan(X, eps=0.35, min_pts=6):
    D = ((X[:, None] - X) ** 2).sum(2) <= eps ** 2  # eps küresindeki komşular
    core = D.sum(1) >= min_pts                # çekirdek noktalar
    g, k = np.full(len(X), -1), 0             # -1: gürültü
    for i in np.flatnonzero(core):
        if g[i] != -1: continue
        g[i], kuyruk = k, [i]                 # yeni küme
        while kuyruk:
            j = kuyruk.pop()
            if not core[j]: continue          # sınır noktası genişlemez
            for t in np.flatnonzero(D[j] & (g == -1)):
                g[t] = k; kuyruk.append(t)
        k += 1
    return g
etiket = dbscan(P)                            # ya da kmeans(Z, 5, np.random.default_rng(0))
def siluet(X, g):                             # ortalama siluet skoru (gürültü hariç)
    X, g = X[g >= 0], g[g >= 0]
    L = np.unique(g)
    if len(L) < 2: return 0.0
    D = np.sqrt(((X[:, None] - X) ** 2).sum(2))
    ort = np.stack([D[:, g == l].sum(1) / np.maximum(1, (g == l).sum() - (g == l)) for l in L], 1)  # her kümeye ortalama uzaklık
    a = ort[np.arange(len(g)), np.searchsorted(L, g)]  # kendi kümesi
    b = np.where(L[None] == g[:, None], np.inf, ort).min(1)  # en yakın diğer küme
    return float(np.mean((b - a) / np.maximum(a, b)))
history = {'eps': [], 'clusters': [], 'noise_share': [], 'silhouette': []}  # geçmiş: eps taraması
for e in (0.2, 0.3, 0.35, 0.4, 0.5, 0.6):
    g = dbscan(P, eps=e)
    history['eps'].append(e); history['clusters'].append(int(g.max() + 1))
    history['noise_share'].append(float((g < 0).mean())); history['silhouette'].append(siluet(P, g))
for row in zip(*history.values()): print('  '.join(f'{k}={v:.3f}' for k, v in zip(history, row)))  # tablo
import csv
with open('egitim_gecmisi.csv', 'w', newline='') as f:  # geçmişi CSV'ye yaz
    csv.writer(f).writerows([list(history), *zip(*history.values())])
try:
    import matplotlib.pyplot as plt           # varsa grafik çiz
    fig, (a1, a2) = plt.subplots(1, 2, figsize=(9, 3.5))
    a1.plot(history['eps'], history['clusters'], 'o-'); a1.set_xlabel('eps'); a1.set_ylabel('clusters')
    a2.scatter(P[:, 0], P[:, 1], c=etiket, s=4, cmap='tab10'); a2.set_aspect('equal')  # kümeler (üstten görünüş)
    plt.show()
except ImportError:
    print('matplotlib yok: grafik atlandı')

Kendi CSV’ni yükle

Çıktı

Çıktı burada görünecek.