3A

領域分割

In [1]:
import cv2
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches # 円を描画

領域分割

色によるクラス分け（画像のみ）

  • 例えば、画素(RGB)や位置(x,y)の似たものをグループ分けする。
  • 二値分類(FG/BG分類)で有名なのがクロマキー（青色・緑色背景）

k-means法</h3

予めクラス数 $k$ を指定してクラスタリング。

  1. $k$ 個の代表点をランダムにサンプリング（$k$ 個をデータの中からとってきても良いし、完全にランダムでばらまいても良い。）
  2. 全てのデータ点から一番近い代表点を $1$ つ探す。
  3. $k$ 個のグループの重心を計算し、それを新たな代表点とする。
  4. 2,3を繰り返す。
In [2]:
from kerasy.ML.KMeans import KMeans
In [3]:
def decomposeImg(path, K):
    imgsize = 4
    fig = plt.figure(figsize=(imgsize*2,imgsize*1))
    
    bgr_img = cv2.imread(path)
    rgb_img = cv2.cvtColor(bgr_img, cv2.COLOR_BGR2RGB)
    img_shape = rgb_img.shape
    # Original Image.
    ax_org = fig.add_subplot(1,2,1)
    ax_org.imshow(rgb_img)
    ax_org.set_title(f"Original"), ax_org.set_xticks([]), ax_org.set_yticks([])
    
    #=== KMeans ===
    x = rgb_img.reshape(-1, 3)
    model = KMeans(K=K, random_state=0)
    model.fit(x)
    cls,mu = model.predict(x)
    mu = mu.astype(int)
    for k in range(K):
        x[cls==k] = mu[k]
        
    # KMeansed Image.
    ax_K = fig.add_subplot(1,2,2)
    ax_K.imshow(x.reshape(img_shape))
    ax_K.set_title(f"K={K}"), ax_K.set_xticks([]), ax_K.set_yticks([])
    
    n_col = 4
    n_row = K//n_col if K%n_col==0 else K//n_col+1
    fig = plt.figure(figsize=(imgsize*n_col,imgsize*n_row))
    for i,k in enumerate(range(K)):
        ax = fig.add_subplot(n_row,n_col,i+1)
        data = np.zeros(shape=x.shape)
        data[cls==k] = mu[k]
        ax.imshow(data.astype(int).reshape(img_shape))
        ax.set_title(f"Color No.{i+1:<0{len(str(K))}}, rgb=({','.join(mu[k].astype(int).astype(str))})")
        ax.set_xticks([]), ax.set_yticks([])
    plt.tight_layout()
    plt.show()
In [4]:
decomposeImg(path="lenna.png", K=8)

mean-shift法

  • 画像領域の分割や対象画像の追跡に用いられる手法。
  • $d$ 次元の特徴量（ex. $\mathrm{R,G,B},x,y$）を持った $N$ 個のデータ点 $\mathbf{x}_i$ が分布しているときに、この点群 $\mathbf{x}_i$ を標本点として得られるような確率密度関数 $f(\mathbf{x})$ を考え、その標本点から確率密度関数 $f(\mathbf{x})$ の極大点を探索する手法。
  • 点群が集中している場所は確率密度関数 $f(\mathbf{x})$ の値が高く、まばらな場所は低くなる。
  • ある任意の観測点 $\mathbf{y}_j$ から半径 $h$ の超球を考え、その範囲にある点群 $\mathbf{x}_i$ の平均 $\mathbf{x}_c$ を計算し、その位置に観測点 $\mathbf{y}_{j+1}$ を移動する。この操作を繰り返すと観測点は最大勾配の方向に移動し、やがて極大点に収束する。 このように、「近傍の点群の平均(mean)位置に移動(shift)を繰り返し、極大点を求める方法」からミーンシフト法(mean-shift)と呼ばれる。
In [5]:
fig, ax = plt.subplots(figsize=(6,6))
# Circle
r = 0.7
c = patches.Circle(xy=(0,0), radius=r, ec='black', fill=False)
ax.add_patch(c)
# Sample Data
X,Y = np.random.RandomState(123).uniform(low=-0.3, high=1, size=(2,50))
cls = np.sqrt(X**2 + Y**2)<r
ax.scatter(X,Y,c=cls, cmap="Set1_r", alpha=0.7)
# Center
ax.scatter(0,0, color="black", s=100)
ax.text(0.05,-0.05,"$\mathbf{y}_{j}$", fontsize=12)
# Mean
mux,muy = np.mean(X[cls]), np.mean(Y[cls])
ax.scatter(mux, muy, color="black", marker='*', s=100)
ax.text(mux+0.05,muy,"$\mathbf{x}_c(=\mathbf{y}_{j+1})$", fontsize=12)
# Arrow
ax.annotate(
    '', xy=(mux,muy), xytext=(0,0),
    arrowprops=dict(width=2,headwidth=8,headlength=10, connectionstyle='arc3',facecolor='blue',edgecolor='blue')
)
# Radius
ax.plot((0,0),(0,-r), color="black")
ax.text(0.05,-r/2,"r",fontsize=12)

ax.set_xlim(-1,1)
ax.set_ylim(-1,1)
plt.show()

カーネル密度関数を用いた確率密度関数の推定

  • $d$ 次元空間内の $N$ 個の点群 $\mathbf{x}_i$ を考える。この点群をある確率分布に従う標本と考えたとき、$d$ 次元空間内の任意の点 $\mathbf{x}$ における確率密度関数 $f(\mathbf{x})$ は、以下の方法で推定される。 $$f(\mathbf{x}) = \frac{c_{kd}}{Nh^{d}}\sum_{i=1}^Nk\left(\left|\frac{\mathbf{x}-\mathbf{x}_i}{h}\right|^2\right)$$
    • $c_{hd}$ は、確率密度関数 $f(\mathbf{x})$ 全体の積分を $1$ にするための正規化係数。
    • $k(t)$ は、カーネル関数 $K(t)$ のプロファイルで、$K(t)=k(|t|^2)$
  • 以下の２つのカーネルが代表的である。
ガウシアンカーネル(Gaussian) エパネックニコフカーネル(Epanechnikov)
$$K(t) = \exp\left(-\frac{\mid t\mid^2}{2}\right)$$ $$K(t) = \begin{cases}1- \mid t\mid^2 & (\mid t\mid\leq1)\\0 & (\text{otherwise})\end{cases}$$

確率密度関数の勾配

  • 勾配法(gradient method)を用いて極大点を逐次的に求めるために、確率密度関数の勾配 $\nabla f(\mathbf{x})$ を求める。 $$ \begin{aligned} \nabla f(\mathbf{x}) &= \frac{2c_{kd}}{Nh^{d+2}}\sum_{i=1}^Nk'\left(\left|\frac{\mathbf{x}-\mathbf{x}_i}{h}\right|^2\right)\left(\mathbf{x}-\mathbf{x}_i\right)\\ &= \frac{2c_{kd}}{Nh^{d+2}}\sum_{i=1}^N\left(g_i\mathbf{x}_i-g_i\mathbf{x}\right), \quad g(t) = -k'(t),g'(t)=g\left(\left|\frac{\mathbf{x}-\mathbf{x}_i}{h}\right|\right)^2\\ &= \frac{2c_{kd}}{Nh^{d+2}}\left\{\sum_{i=1}^Ng_i\right\}\left\{\frac{\sum_{i=1}^Ng_i\mathbf{x}_i}{\sum_{i=1}^Ng_i}-\mathbf{x}\right\} \end{aligned} $$
項 説明
$$\frac{2c_{kd}}{Nh^{d+2}}\left\{\sum_{i=1}^Ng_i\right\}$$ ガウシアンカーネルやエパネックニコフカーネルを用いた場合、正になる。
$$\left\{\frac{\sum_{i=1}^Ng_i\mathbf{x}_i}{\sum_{i=1}^Ng_i}-\mathbf{x}\right\}$$ ミーンシフトと呼ばれる項で、観測点 $\mathbf{x}$ の近傍のデータ点群 $\mathbf{x}_i$ の加重平均位置と $\mathbf{x}$ 自身の差分ベクトルを示す。

勾配法を用いた極大点探索（ミーンシフト法）

  1. 初期化：$\mathbf{y}_0\leftarrow\mathbf{x}$
  2. 更新（ミーンシフト） $$\mathbf{y}_{j+1}\leftarrow \mathbf{y}_j + \left(\frac{\sum_{i=1}^Ng_i\mathbf{x}_i}{\sum_{i=1}^Ng_i}-\mathbf{y}_j\right) = \frac{\sum_{i=1}^Ng_i\mathbf{x}_i}{\sum_{i=1}^Ng_i}$$
  3. $|\mathbf{y}_{j+1}-\mathbf{y}_j|<\text{threshold}$ となるまで2を繰り返す。
  4. 収束した $\mathbf{y}_{j+1}$ を極大点として出力する。

※ 一般的な勾配法では、更新式 $\mathbf{y}_{j+1}\rightarrow\mathbf{y}_i + \alpha\nabla f$ のステップ数 $\alpha$ を与える必要があるが、ミーンシフト法ではベクトルの大きさは自動的に計算されるので、$\alpha$ を与える必要がない（らしい…）。

ミーンシフト法を用いたクラスタリングへの応用

$d$ 次元空間中の $N$ 個の点群 $\mathbf{x}_i$ が与えられた時に、密に分布する点群をクラスタとして分割する。

  1. 各点にミーンシフト法を適用し、収束位置 $\mathbf{x}_i^c$ を計算する。
  2. 任意の2個の点 $\mathbf{x}_i,\mathbf{x}_j$ について、その収束位置が閾値以下なら（$|\mathbf{x}_i-\mathbf{x}_j|<\text{threshold}$）、この2点を同じ極大点として同じクラスタに入れる。

1,2より、全ての点群 $\mathbf{x}_i$ を同じ収束位置（極大点）に属するものごとにクラスタに識別する。

  • 全ての点 $\mathbf{x}_i$ でこの処理を行わなければならないが、並行化できる。
  • k-means手法とは異なり、クラスタの数を予め指定する必要がない。

ミーンシフト法を用いたカラー画像の領域分割

  • カラー画像の $N$ 個の各画素の位置 $\mathbf{x}_i$ とその画素値 $\mathbf{v}_i=\left(R_i,G_i,B_i\right)$ とし、画素位置-画素値を結合した5次元空間内の点 $\mathbf{z}_i=(\mathbf{x}_i,\mathbf{v}_i)$ を考える。
  • 「距離および色が近い画素が5次元空間内でクラスタを形成している」とみて、ミーンシフト法で各画素をクラスタリングする。
  • 画素位置に関するバンド幅 $h_s$、画素値に関するバンド幅 $h_r$ を与え、全ての $z_i$ にミーンシフトを行い、収束位置 $\mathbf{z}^c=(\mathbf{x}^c,\mathbf{v}^c)$ を計算する。
  • $\mathbf{x}_i$ の画素値を、収束位置の画素の値 $(R^c,G^c,B^c)$ に置き換えることによって、画像の平滑化ができる。
  • ミーンシフトは、以下の通り計算する。 $$f(\mathbf{x}) = \frac{c}{Nh_s^2h_r^3}\sum_{i=1}^Nk\left(\left|\frac{\mathbf{x}^s-\mathbf{x}^s_i}{h_s}\right|^2\right)k\left(\left|\frac{\mathbf{x}^r-\mathbf{x}^r_i}{h_r}\right|^2\right)$$
  • したがって、以下のとおりに位置を更新する。 $$\mathbf{y}^{s}_{j+1} = \frac{\sum_{i=1}^Ng_{i}^s\mathbf{x}_i^s}{\sum_{i=1}^Ng_i^s},\quad\mathbf{y}^{r}_{j+1} = \frac{\sum_{i=1}^Ng_{i}^r\mathbf{x}_i^r}{\sum_{i=1}^Ng_i^r}$$
  • $(h_s,h_r)$ のパラメータを大きくすると、より大きな領域に同色が統合され、大まかに分割される。
In [6]:
from sklearn.cluster import MeanShift
In [7]:
import time
s = time.time()

imgsize = 4
fig = plt.figure(figsize=(imgsize*2,imgsize*1))
path = "lenna.png"
bgr_img = cv2.imread(path)
rgb_img = cv2.cvtColor(bgr_img, cv2.COLOR_BGR2RGB)
img_shape = rgb_img.shape
# Original Image.
ax_org = fig.add_subplot(1,2,1)
ax_org.imshow(rgb_img)
ax_org.set_title(f"Original"), ax_org.set_xticks([]), ax_org.set_yticks([])

#=== MeanShift ===
x = rgb_img.reshape(-1, 3)
model = MeanShift()
model.fit(x)
cls = model.predict(x)
mu = model.cluster_centers_.astype(int)
K = max(cls)+1
for k in range(K):
    x[cls==k] = mu[k]

# MeanShifted Image.
ax_Mean = fig.add_subplot(1,2,2)
ax_Mean.imshow(x.reshape(img_shape))
ax_Mean.set_title(f"n_cluster={K}"), ax_Mean.set_xticks([]), ax_Mean.set_yticks([])

n_col = 4
n_row = K//n_col if K%n_col==0 else K//n_col+1
fig = plt.figure(figsize=(imgsize*n_col,imgsize*n_row))
for i,k in enumerate(range(K)):
    ax = fig.add_subplot(n_row,n_col,i+1)
    data = np.zeros(shape=x.shape)
    data[cls==k] = mu[k]
    ax.imshow(data.astype(int).reshape(img_shape))
    ax.set_title(f"Color No.{i+1:<0{len(str(K))}}, rgb=({','.join(mu[k].astype(int).astype(str))})")
    ax.set_xticks([]), ax.set_yticks([])
plt.tight_layout()

e= time.time()
print(f"Processing time: {int((e-s)//60):>02}m {(e-s)%60:.3f}s")

plt.show()

Processing time: 31m 13.287s
In [ ]:
hidden
Table of Contents
Published
Last Updated
Category
映像メディア工学
Tags
Contact
Other contents
  • Home
  • Blog
  • Front-End
  • Kerasy
  • Python-Charmers
  • Translation-Gummy