【画像処理】PythonでOpenCVを使わずにラベリング処理


PythonでOpenCVを使わずにラベリング処理
今回は、画像処理講座としては少し飛びますが、業務でラベリングを使う機会があったため、PythonでOpenCVを使わずにラベリング処理を学んでいきます。
画像の入出力やグレースケール変換時にOpenCVを使っていますが、ラベリング処理では一切使いません。
それぞれのバージョンはPython 3.8.2、OpenCV 4.2.0になります。

# ラベリングとは
二値化処理された画像において、白の部分（または黒の部分）が連続した画素に同じ番号を割り振る処理をラベリングと言います。基本的には「各ピクセルがどのグループに属しているのか」の分類をしています。
通常、同じ番号(グループ)ごとの面積（画素数）や幅、高さなどの特徴量を求めて欠陥検査や分類処理などに用いられます。

# なぜラベリングをするのか
ラベリングの目的は、画像内の物体を検出して、画像内における物体の位置や面積などの特徴量を取得するためです。
例えば、「1.1 入力画像」における物体の数を数えたい場合、2値化でその物体を抽出した後に、ラベリング処理を行うことで「1.2 処理画像」のように物体数を取得することができます。

|1.1 入力画像|1.2 処理画像|
|:--:|:--:|
|![sample.png](https://user-images.githubusercontent.com/74283288/106982626-c8250200-67a7-11eb-9b3a-207542b82a97.jpg)物体数：?|![label.png](https://user-images.githubusercontent.com/74283288/106982630-c9562f00-67a7-11eb-973d-aed0b69e75be.png)物体数：6|

# ラベリングの仕組み(実装編)
ラベリングには、縦と横方向に連続している部分のみを同じラベルにする4近傍と、全方向に連続しているすべてのピクセルを同じラベルにする8近傍の2種類あります。

今回は8近傍のラベリングを例に説明します。
① まず画像を走査するにあたり、画像外アクセスを防ぐために画像の周りに幅1ピクセルの外枠を取り付けます。
![border_interpolate](https://user-images.githubusercontent.com/74283288/106980262-30251980-67a3-11eb-8486-8f25910e67be.png)

```Python:labeling_algorithm.py

# 画像の外周に幅1ピクセルの外枠をつける(走査時のピクセル外アクセスをなくすため)
    def _border_interpolate(self):
        # 上下の外枠を追加
        horizontal_line = np.zeros_like(self.bin_img[0])
        self.bin_img = np.insert(self.bin_img, [0, len(self.bin_img)], horizontal_line, axis=0)

        # 左右の外枠を追加
        vertical_line = np.zeros((len(self.bin_img), 1))
        self.bin_img = np.insert(self.bin_img, [0, len(self.bin_img[0])], vertical_line, axis=1)

```

② ラベル番号自体の管理をするため、画像と同じ大きさ(外枠付き)のラベルテーブルを作成し、すべてのピクセルに0のラベルを割り当てます。

![label_table](https://user-images.githubusercontent.com/74283288/106980242-2bf8fc00-67a3-11eb-9525-eba82018301f.png)

同時に、ラベルの衝突を解決するのに必要なルックアップテーブルも用意しておきます。
ラベルの衝突とは、本来1つの物体(1つのラベル群)としてラベリングされるべきところに複数のラベルが割り当てられている状態のことを言います。

ルックアップテーブルのarrayは各ラベル番号を表していて、elementは本来あるべきラベル番号を表しています。
例えば、ラベルの衝突が起きた場合、衝突したラベルの一方をもう一方のラベルに書き換える必要があるため、ルックアップテーブルを使って本来あるべきラベル番号を書き換えて管理しています。具体的な使い方は、下で説明します。

![lookup_table](https://user-images.githubusercontent.com/74283288/106980239-2ac7cf00-67a3-11eb-877c-ebfd351c2440.png)

```Python:labeling_algorithm.py

        # ラベルテーブル作成
        self.label_table = np.zeros_like(self.bin_img)

        # ルックアップテーブル作成
        self.lookup_table = [0]

```

③ 画像左上から走査して、ピクセル(画素)の値が255(白)だった場合、左・左上・上・右上ピクセルのラベル番号を参照します。

![scan](https://user-images.githubusercontent.com/74283288/106987466-dcb9c800-67b0-11eb-8886-4d82738f2c08.png)
![neighbor_pixel](https://user-images.githubusercontent.com/74283288/106980243-2bf8fc00-67a3-11eb-9f76-2ab3b3423036.png)
本来は、8近傍なので8方向すべてを見る必要がありますが、右・左下、下、右下のピクセルは、走査していく方向にあるピクセルなので、2重に参照することを防ぐ意味で上記4つのみを参照しています。

```Python:labeling_algorithm.py

        # 走査時の近傍指定
        neighbor_shape = np.array([1,1,1,1,0,0,0,0,0])

        # 走査
        height, width = self.bin_img.shape[:2]
        for y in range(height):
            for x in range(width):
                if(self.bin_img[y][x] != 255):
                    continue

                # ラベルテーブルを取得
                label_around_pixel = self._get_neighbor_label(y, x)

                # 注目画素周辺のラベルを参照・ルックアップテーブル更新
                labels = self._update_table(label_around_pixel, neighbor_shape)

                # ラベルテーブル更新
                self._set_neighbor_label(y, x, labels)

```

④ 参照したラベル番号がすべて0(初期値)であれば「最後に割り振った番号＋１」のラベル番号をルックアップテーブルに付与＆ラベルテーブルにも同じラベル番号を付与します。

![labeling_1](https://user-images.githubusercontent.com/74283288/106980245-2c919280-67a3-11eb-99da-eba736eae0c5.png)
![labeling_2](https://user-images.githubusercontent.com/74283288/106980246-2c919280-67a3-11eb-84aa-81f96e3d7ab6.png)

⑤ 参照したラベル番号がすべて0ではない場合は、参照した中で0以外の最小の番号を付与＆ルックアップテーブルにある付与しなかったラベル番号を付与した番号に書き換える＆ラベルテーブルにも同じラベル番号を付与します。

![labeling_3](https://user-images.githubusercontent.com/74283288/106980247-2d2a2900-67a3-11eb-8569-0c434513f940.png)
![labeling_4](https://user-images.githubusercontent.com/74283288/106980248-2d2a2900-67a3-11eb-9ab2-cfc07a8d3c62.png)
⑤-①ここでラベルの衝突が起こっています。本来、ラベル2はラベル1と同じ物体として認識されるべきですが、別々のラベルが割り当てられています。そこで、ルックアップテーブルの2番目の要素を1に書き換えます。
![labeling_5](https://user-images.githubusercontent.com/74283288/106980250-2dc2bf80-67a3-11eb-8a80-01d9b0aa92b4.png)
![labeling_6](https://user-images.githubusercontent.com/74283288/106980251-2dc2bf80-67a3-11eb-889f-93818996d54c.png)
![labeling_7](https://user-images.githubusercontent.com/74283288/106980252-2e5b5600-67a3-11eb-9793-b1934ae45280.png)
![labeling_8](https://user-images.githubusercontent.com/74283288/106980253-2e5b5600-67a3-11eb-8d5b-c24189c72597.png)
![labeling_9](https://user-images.githubusercontent.com/74283288/106980258-2ef3ec80-67a3-11eb-992f-03ad70e62bf6.png)

```Python:labeling_algorithm.py

    # 注目画素周辺のラベルを参照・ルックアップテーブル更新
    def _update_table(self, all_label, neighbor_shape):
        around_label = np.where(neighbor_shape == 1, all_label, -1)
        label_index = np.where(around_label != -1)
        focus_pixels_label = around_label[label_index]

        # 注目画素の周辺ラベル番号がすべて0か
        if np.all(focus_pixels_label == 0) == True:
            if all_label[4] == 0:
                around_label[4] = self.label_table.max() + 1
                self.lookup_table.append(int(self.label_table.max() + 1))
        
        # 注目画素の周辺ラベル番号が複数ある
        else:
            uptozero_index = np.where(around_label > 0)
            min_label = around_label[uptozero_index].min()
            around_label[uptozero_index] = min_label
            around_label[4] = min_label

            # around_labelとall_labelのuptozero_index部分の差分を見て、ルックアップテーブル更新
            for index in uptozero_index[0]:
                self.lookup_table[all_label[index]] = around_label[index]
            
        return around_label

```

⑥ ラベル同士の衝突を解決します。

![resolve_collision](https://user-images.githubusercontent.com/74283288/106980259-2f8c8300-67a3-11eb-8534-e9e079703fcd.png)

```Python:labeling_algorithm.py

    # ラベルの衝突を解決
    def _resolve_collision(self):
        for nLabel in reversed(range(len(self.lookup_table))):
            tmp = []
            array_num = nLabel
            element = self.lookup_table[nLabel]

            while element != array_num:
                tmp.append(array_num)
                array_num = element
                element = self.lookup_table[element]

            for t in tmp:
               self.lookup_table[t] = element

```
⑦ ルックアップテーブル内の不連続なラベルを修正します。


```Python:

    # 不連続なラベルを埋める
    def _compress_table(self):
        new_label = []
        for array in range(len(self.lookup_table)):
            if array == self.lookup_table[array]:
                new_label.append(array)

        for l in new_label:
            self.lookup_table = np.where(self.lookup_table == l, new_label.index(l), self.lookup_table)

```

⑧ 修正したルックアップテーブルを参照して、ラベルテーブルを更新します。

![resolve_collision](https://user-images.githubusercontent.com/74283288/106980259-2f8c8300-67a3-11eb-8534-e9e079703fcd.png)

```Python:labeling_algorithm.py

    # ルックアップテーブルを参照して、ラベルテーブルを更新
    def _update_label_table(self):
        for array, nLabel in enumerate(self.lookup_table):
            self.label_table = np.where(self.label_table == array, nLabel, self.label_table)

```

⑨ 最後に、画像に追加した枠を削除します。

![border_cutoff](https://user-images.githubusercontent.com/74283288/106980261-30251980-67a3-11eb-83e1-6bc9f76de60d.png)

```Python:labeling_algorithm.py

    # 画像に追加した外枠の切り落とし
    def _border_cutoff(self):
        # 上下の外枠を削除
        self.label_table = np.delete(self.label_table, [0, len(self.label_table)-1], axis=0)

        # 左右の外枠を削除
        self.label_table = np.delete(self.label_table, [0, len(self.label_table[0])-1], axis=1)

```

以上の手順でラベリングが完了します。
実際の実装コードは[こちら](https://github.com/spc-ehara/qiita_image_processing/blob/master/28th/labeling_algorithm.py)にあります。(github)


試しに「2.1 入力画像」を使って実行してみました。

|2.1 入力画像|2.2 処理画像|
|:--:|:--:|
|![sample.png](https://user-images.githubusercontent.com/74283288/106082899-e911a580-615e-11eb-83e0-195dbb426b93.png)|![label.png](https://user-images.githubusercontent.com/74283288/106540192-cb6b8400-6542-11eb-966a-56f69e10b390.png)|

「2.2 処理画像」はどの図形もきれいに取れているのがわかると思います。

次に、もう少し難易度の高い「3.1 入力画像」で実行してみます。

|3.1 入力画像|3.2 処理画像|
|:--:|:--:|
|![sample.png](https://user-images.githubusercontent.com/74283288/106981210-f523e580-67a4-11eb-9639-c02e562665a4.png)|![label.png](https://user-images.githubusercontent.com/74283288/106981202-f228f500-67a4-11eb-928a-01cce061d8c7.png)|

「3.2 処理画像」もきれいにラベリングできているのがわかります。

最後に、ラベリングに失敗しやすい典型的な画像「4.1 入力画像」で実行してみます。

|4.1 入力画像|4.2 処理画像|
|:--:|:--:|
|![sample.png](https://user-images.githubusercontent.com/74283288/106981238-00771100-67a5-11eb-9daa-e1468ee338cf.png)|![label.png](https://user-images.githubusercontent.com/74283288/106981601-9ca11800-67a5-11eb-9d58-5d5b580d4027.png)|


「4.2 処理画像」では、画像右上の部分が別のラベルに分かれていて、うまく取れていないのがわかります。
つまり、上記のアルゴリズムでは簡単な図形はうまくラベリングできるものの、少し複雑な画像になるともう少し工夫が必要なようです。
近々、記事ではうまくいかなかった難易度の高い画像について挑戦し、更新していきます。

# さいごに
今回は、「PythonでOpenCVを使わずにラベリング処理」について解説しました。

それでは引き続きよろしくお願いいたします。

目次は以下の記事からご覧になれます。

https://qiita.com/spc_ehara/items/e425b6dcc0398299c40d#%E7%9B%AE%E6%AC%A1