Watershedアルゴリズムによる画像セグメンテーション

目的

本章では、

• watershed（分水嶺）アルゴリズムを用いたマーカーベースの画像セグメンテーションの使い方を学ぶ
• 次の関数を扱う: cv.watershed()

理論

任意のグレースケール画像は、高い輝度が山や丘を、低い輝度が谷を表す地形面として見ることができる。まず、孤立した各谷（局所的最小値）に異なる色の水（ラベル）を満たしていく。水位が上がるにつれて、近くの山（勾配）の状況に応じて、異なる谷からの水（当然ながら異なる色）が合流し始める。それを避けるため、水が合流する位置に障壁を築く。すべての山が水没するまで、水を満たし障壁を築く作業を続ける。そうして作った障壁がセグメンテーション結果を与える。これがwatershedの背後にある「考え方」である。いくつかのアニメーションを使って理解するには、watershedに関するCMMのウェブページ を参照するとよい。

しかしこのアプローチでは、ノイズや画像中のその他の不規則性により過分割された結果が得られる。そこでOpenCVは、どの谷点をマージしどれをマージしないかを指定するマーカーベースのwatershedアルゴリズムを実装している。これは対話的な画像セグメンテーションである。やることは、わかっている物体に異なるラベルを付けることである。前景や物体であると確信できる領域をある色（または輝度）でラベル付けし、背景や物体でないと確信できる領域を別の色でラベル付けし、最後に何であるか確信できない領域を 0 でラベル付けする。これがマーカーである。そしてwatershedアルゴリズムを適用する。すると、与えたラベルでマーカーが更新され、物体の境界は -1 の値を持つことになる。

コード

以下では、互いに接触している物体を分割するために、距離変換 (Distance Transform) とwatershedを併用する例を見ていく。

下のコイン画像を考える。コインは互いに接触している。たとえしきい値処理をしても、コインは互いに接触したままになる。

image

まず、コインのおおよその推定を見つけることから始める。そのために、大津の二値化 (Otsu's binarization) を使うことができる。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
 
img = cv.imread('coins.png')
assert img is not None, "file could not be read, check with os.path.exists()"
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
ret, thresh = cv.threshold(gray,0,255,cv.THRESH_BINARY_INV+cv.THRESH_OTSU)

結果：

image

次に、画像中の小さな白いノイズを除去する必要がある。そのためにはモルフォロジーのオープニングを使うことができる。物体中の小さな穴を除去するには、モルフォロジーのクロージングを使うことができる。これで、物体の中心近くの領域が前景であり、物体から十分離れた領域が背景であることは確実にわかる。確信できないのはコインの境界領域だけである。

そこで、コインであると確信できる領域を抽出する必要がある。収縮は境界ピクセルを除去する。したがって残ったものは、確実にコインであるといえる。これは物体同士が接触していなければ機能する。しかし接触しているため、もう1つの良い選択肢は距離変換を求めて適切なしきい値を適用することである。次に、コインでないと確信できる領域を見つける必要がある。そのために結果を膨張させる。膨張は物体の境界を背景へと広げる。こうすることで、境界領域が除去されるため、結果における背景領域が本当に背景であることを確実にできる。下の画像を参照のこと。

image

残りの領域は、コインなのか背景なのか判断がつかない部分である。これはwatershedアルゴリズムが見つけるべき領域である。これらの領域は通常、前景と背景が接するコインの境界付近（あるいは異なる2つのコインが接する箇所）に存在する。これを境界 (border) と呼ぶ。これは sure_bg 領域から sure_fg 領域を引くことで得られる。

# noise removal
kernel = np.ones((3,3),np.uint8)
opening = cv.morphologyEx(thresh,cv.MORPH_OPEN,kernel, iterations = 2)
 
# sure background area
sure_bg = cv.dilate(opening,kernel,iterations=3)
 
# Finding sure foreground area
dist_transform = cv.distanceTransform(opening,cv.DIST_L2,5)
ret, sure_fg = cv.threshold(dist_transform,0.7*dist_transform.max(),255,0)
 
# Finding unknown region
sure_fg = np.uint8(sure_fg)
unknown = cv.subtract(sure_bg,sure_fg)

結果を見てみよう。しきい値処理した画像では、確実にコインだと分かる領域がいくつか得られ、それらは互いに分離されている。（場合によっては、互いに接する物体を分離することではなく、前景のセグメンテーションだけに関心があるかもしれない。その場合は距離変換を使う必要はなく、収縮 (erosion) だけで十分である。収縮は確実な前景領域を抽出するもう1つの方法に過ぎない。）

image

これで、どこが確実にコインの領域で、どこが背景なのかが分かった。そこでマーカー（元画像と同じサイズだが int32 型の配列）を作成し、その中の領域にラベルを付ける。確実に分かっている領域（前景か背景かを問わず）には任意の正の整数を、ただし異なる整数を付け、確実には分からない領域は0のままにしておく。これには cv.connectedComponents() を使う。この関数は画像の背景を0でラベル付けし、その他の物体には1から始まる整数でラベルを付ける。

ただし、背景を0でマークすると、watershedはそれを未知の領域とみなしてしまう。そのため、背景は別の整数でマークしたい。代わりに、unknown で定義した未知領域を0でマークすることにする。

# Marker labelling
ret, markers = cv.connectedComponents(sure_fg)
 
# Add one to all labels so that sure background is not 0, but 1
markers = markers+1
 
# Now, mark the region of unknown with zero
markers[unknown==255] = 0

JETカラーマップで表示した結果を見てみよう。濃い青の領域が未知領域を示している。確実なコインは異なる値で色付けされている。確実な背景である残りの領域は、未知領域に比べて明るい青で示されている。

image

これでマーカーの準備が整った。いよいよ最終ステップ、watershedの適用である。すると、マーカー画像が変更される。境界領域は -1 でマークされる。

markers = cv.watershed(img,markers)
img[markers == -1] = [255,0,0]

以下の結果を見てみよう。コインによっては、接している領域が適切にセグメンテーションされているが、そうでないものもある。

image

追加リソース

1. CMMのページ Watershed Transformation

演習

1. OpenCVのサンプルには、watershedによるセグメンテーションのインタラクティブなサンプル watershed.py がある。実行して、楽しんで、そして学んでみよう。