.. _Watershed:

Watershedアルゴリズムを使った画像の領域分割
*********************************************

目的
=====

このチュートリアルでは
    * watershedアルゴリズムを使ったマーカベースの領域分割の使い方を学びます．
    * 以下の関数の使い方を学びます: **cv2.watershed()**
    
理論
========

あらゆるグレースケール画像は地形学的な表面とみなせます．高い画素値は峰や坂，低い画素値は谷を意味します．全ての独立した谷(極小値)を異なる色をした水(ラベル)で満たすことから始めましょう．水位の上昇と共に，近隣の峰や坂に依存しますが，異なる色をした水が混ざります．この事態を避けるために水が混ざってしまう場所に境界を作成します．この水を満たす作業と境界の作成を，全ての峰が水面より下になるまで続けます．作成した境界が領域分割の結果になります．これがwatershedアルゴリズムの "哲学" です．以下のサイトにアニメーションを使った詳しい説明が乗っています `CMM webpage on watershed <http://cmm.ensmp.fr/~beucher/wtshed.html>`_ ．

しかし，この方法を使うとノイズや画像中の不連続性によってoversegmentedされた結果になってしまいます．そこでOpenCVは全ての極小値に対応する点に対して統合されるべきか否かを指定するwatershedアルゴリズムを実装しました．自分の知っている対象物体に異なったラベルを与えます．前景だと保障できる領域もしくは単色の物体に対してラベルを与えます．背景だと保証できる領域もしくは物体ではないと思える領域についてはラベルとして0を与えます．これが設定したマーカになります．次にwatershedアルゴリズムを適用します．設定したマーカはラベルの値と共に更新され，境界領域に画素の値は―1になります．

実装(コード)
=============

相互に接している物体の領域分割にwatershedアルゴリズムと共に距離変換を使った例を示します．

以下の画像のコインはお互いに接しています．しきい値処理を施してもお互いは接したままです．

    .. image:: images/water_coins.jpg
        :alt: Coins
        :align: center
    
コインの概算から始めます．大津の二値化を適用しましょう．
::

    import numpy as np
    import cv2
    from matplotlib import pyplot as plt

    img = cv2.imread('coins.png')
    gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    ret, thresh = cv2.threshold(gray,0,255,cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)

結果:

    .. image:: images/water_thresh.jpg
        :alt: Thresholding
        :align: center
        
二値画像中から小さな白いノイズを取り除かなければいけません．モーフォロジカル処理にを使いましょう．物体中の小さな穴を消すにはクロージング処理を使います．これで物体の中心近辺の領域は前景，物体から離れた領域は背景であることが保証できます．唯一，コインと境界領域がどちらであるか不確かな領域です．

コインであると確信している領域の検出をする必要があります．収縮処理(Erosion)によって境界の領域を消します．収縮処理の結果残ったものが何であれ，コインであることは確かです．この方法は物体がお互いに接していなければうまくいきます．しかし今扱っている画像では物体が互いに接しています．別の方法として，距離変換をした画像に対してしきい値処理をする方法があります．次に，コインではないと確信している領域を見つける必要があります．背景検出のために，結果画像に対して膨張処理(dilation)を適用すると物体の境界が大きくなります．このようにして，背景領域が消去されるため，結果の背景内の領域に何があろうとも，それが背景だと確認を持てます．下の画像を見てください．

    .. image:: images/water_fgbg.jpg
        :alt: Foreground and Background
        :align: center

コインなのかそれとも拝啓なのかどちらか分からない領域が残っており，この判断をWatershedアルゴリズムによって行います．これらの領域は通常，前景と背景が交わるコインの境界近辺になります(もしくは二つのコインが交わる場所)．この領域をボーダー(境界?)と呼びます．ボーダーは前景と確信している領域sure_fgを背景と確信している領域sure_bgから引いた領域になります．
::
    
    # noise removal
    kernel = np.ones((3,3),np.uint8)
    opening = cv2.morphologyEx(thresh,cv2.MORPH_OPEN,kernel, iterations = 2)

    # sure background area
    sure_bg = cv2.dilate(opening,kernel,iterations=3)

    # Finding sure foreground area
    dist_transform = cv2.distanceTransform(opening,cv2.DIST_L2,5)
    ret, sure_fg = cv2.threshold(dist_transform,0.7*dist_transform.max(),255,0)

    # Finding unknown region
    sure_fg = np.uint8(sure_fg)
    unknown = cv2.subtract(sure_bg,sure_fg)
    
結果を見てみましょう．しきい値処理された画像(右)上では，コインだと確信できる領域を検出できており，更に各領域が分離されています(前景領域の抽出のみで十分なケース，つまり相互に接している物体を切り分ける必要が無い時もあるでしょう．そのような時は距離変換を使う必要はありません．収縮処理(erosion)だけで十分です．)．

    .. image:: images/water_dt.jpg
        :alt: Distance Transform
        :align: center         

今，どの領域がコインでどの領域が背景であるか分かっています．そこでマーカを作成し，その中の領域にラベルを与えます．ここでマーカは入力画像と同じサイズ，データタイプはint32となる配列です．前景か背景か確信が持てる領域は正の値であればどのような値をラベル付けしても構いません．ただし，それぞれの領域には異なるラベルを与え，どちらの領域か分からない領域に関してはラベル値として0を与えてください．このために， **cv2.connectedComponents()** 関数を使います．この関数は画像の背景に0というラベルを与え，それ以外の物体に対して1から順にラベルをつけていく処理をします．

しかし，背景に対して0ラベルを与えるとwatershedアルゴリズムが未知の領域だとみなしてしまいます．そこで，別の整数値を与えましょう． ``unknown`` として定義された未知の領域に対して0を与えるようにしてください．
::

    # Marker labelling
    ret, markers = cv2.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:: images/water_marker.jpg
        :alt: Marker Image
        :align: center  
        
マーカの準備が出来ました．最後の処理であるwatershedアルゴリズムを適用しましょう．マーカ画像は変更されます．境界領域の値が-1になります．
::

    markers = cv2.watershed(img,markers)
    img[markers == -1] = [255,0,0]
    
以下に示す結果を見てください．接しているコインがうまく分離できている場所と分離できていない場所があるのが分かります．

    .. image:: images/water_result.jpg
        :alt: Result
        :align: center

        
補足資料
======================

#. CMMの `Watershed Tranformation <http://cmm.ensmp.fr/~beucher/wtshed.html>`_ のページ

課題
==============

#. OpenCVのサンプルに含まれている `watershed.py` を実行して色々と遊んでみてください．