.. _Contours_Hierarchy:

輪郭の階層情報
*************************

目的
=======

今回は輪郭の階層情報(輪郭における親子関係)を学びます．

理論
=========

これまで輪郭に関する幾つかのチュートリアルを通してOpenCVが提供する輪郭関連の関数の使い方を学んできました． **cv2.findContours()** 関数に **Contour Retrieval Mode** のフラグに対して，普通は **cv2.RETR_LIST** か **cv2.RETR_TREE** を設定するとうまく輪郭検出が出来ていました．しかし，これらのフラグはいったい何を意味しているのでしょうか？

また，三番目の出力である **階層情報(hierarchy)** がありました．まだこのチュートリアルで取り上げていないこの階層情報とは何なのでしょか？輪郭検索モードのフラグとどのような関係にあるのでしょうか？

このチュートリアルは上記のトピックを扱います．

階層情報とは何か？
-------------------

画像中の物体検出に **cv2.findContours()** 関数を使ってきましたよね？時には物体が難しい場所に位置していたり，ある形状の中に別の形状が観測されることもあります．入れ子になった図形のようなものです．このような画像に対して，外側に位置するものを **親(parent)** と呼び，内側に位置するものを **子(child)** と呼びます．このように，画像中の輪郭は互いに独立せずに関係をもつものもあります．そしてある輪郭が別の輪郭につながっているのかどうか指定できます(この輪郭は他の輪郭の子か？それとも親か？など)．個の関係の表現方法を **階層情報** と呼びます．

以下の画像を例にみてみましょう :

    .. image:: images/hierarchy.png
        :alt: Hierarchy Representation
        :align: center
        
この画像中には **0-5** の番号をつけた形状が含まれています． *2 と 2a* はそれぞれ一番外側の箱の外側と内側を表しています．

輪郭0,1,2は **external or outermost(最外部の外側)** と呼ばれ， **hierarchy-0** に属し， **同じ階層レベルsame hierarchy level** と言えます．

次は **輪郭2a** です． **輪郭2の子要素** とみなされます(逆に輪郭2が輪郭2aの親要素とも言えます)．**輪郭2a** は **hierarchy-1** に含まれます．同様に，輪郭3は輪郭2の子要素となり，次に階層に含まれます．最後に輪郭4,5はcontour-3aの子要素となり，最後の階層レベルに含まれます．この命名規則に従うと，輪郭4は輪郭3aの最初の子要素ですが，最初の子要素が輪郭5となるかもしれません．

上記の内容は **same hierarchy level**, **external contour**, **child contour**, **parent contour**, **first child** といった用語を理解するために説明しました．それではOpenCVの内部に入っていきましょう．

OpenCVの階層表現
------------------------------------

各輪郭は自身の情報として，どの階層に属しているか，自身の子要素や親要素などを保持している．OpenCVは4つの値のarrayとして **[Next, Previous, First_Child, Parent]** と表現している．

.. centered:: *"Nextは同一階層レベルに属する次の輪郭を表す．"*

例えば，上記の輪郭0であれば，同一レベルの次の輪郭は輪郭1を指すので， ``Next = 1`` となります．同様に，輪郭1の次の輪郭は輪郭②なので ``Next = 2`` となります．

それでは輪郭2のNextはどうなるでしょうか?同一階層にはこれ以上輪郭がないため， ``Next = -1`` となります．輪郭4のNextは輪郭5となるため ``Next = 5`` となります．

.. centered:: *"Previousは同一階層レベルの一つ前の輪郭を表します．"*

上記のNextの逆です．輪郭1のPreviousは輪郭0となり，輪郭2のPreviousは輪郭1となります．そして，輪郭0にとって前の輪郭は存在しないため，Previousは-1となります．

.. centered:: *"First_Child はその輪郭の最初の子要素を表します．"*

説明するまでもなく，輪郭2のFirst_Childは輪郭2aのインデックスになります．それでは輪郭3aのFirst_Childはどうなるでしょうか?二つの子要素を持っていますがFirst_Childはあくまでも最初の子要素のみを表すため，(今回の例だと) ``First_Child = 4`` となります．

.. centered:: *"Parent はその輪郭の親要素のインデックスを表します．"*

これは **First_Child** の逆です．輪郭4と輪郭5の親要素は輪郭3aとなり，輪郭3aの親要素は輪郭3となります．

.. note:: 子要素や親要素がなければ値は-1となります．

これでOpenCVで使われる階層構造を理解できたので，次は同じ画像を使ってOpenCVの輪郭検出法についてみていきましょう．具体的にはcv2.RETR_LIST, cv2.RETR_TREE, cv2.RETR_CCOMP, cv2.RETR_EXTERNALといったフラグが何を意味するのか学びましょう．

輪郭検出モード
=======================

1. RETR_LIST
--------------

これは4つのフラグの中で(説明のし易さを考えると)最も単純なものです．このフラグを使うと全ての輪郭を検出しますが，輪郭の親子関係は無視されます． **このルールの下では親要素も子要素も同等に扱われるため，単なる輪郭として解釈されます**．つまり，全ての輪郭が同一階層に属することになります．

ここでは3番目と4番目の値が常に―1となり，NextとPreviousには対応するインデックスが格納されることになります．自分自身で試して確認してみてください．

以下に私が実験した結果を示します．各行が一つの輪郭に対応しています．例えば，一行目は輪郭0を表しており，次の輪郭が輪郭1であるためNext = 1となっています．一方で，前の輪郭は無いのでPrevious = 0となります．上述したように，残りの二つの数値は-1となります．

::

    >>> hierarchy
    array([[[ 1, -1, -1, -1],
            [ 2,  0, -1, -1],
            [ 3,  1, -1, -1],
            [ 4,  2, -1, -1],
            [ 5,  3, -1, -1],
            [ 6,  4, -1, -1],
            [ 7,  5, -1, -1],
            [-1,  6, -1, -1]]])
            
階層に関する特徴を使わないのであればこのモードを選択すると良いでしょう．

2. RETR_EXTERNAL
------------------

このフラグを使うと，全子要素は無視され最も外側の輪郭のみが返されます． **このルールの下では，家族の最も年上のモノのみが残り，その他の家族は無視されると言えます :)**．

例の画像中では最も外側の輪郭，すなわち階層レベルが0の輪郭は何個あるでしょうか?たったの3個，輪郭0，1，2です．それではこのフラグを使って実際に輪郭検出をしてみましょう．RETR_LISTを使った結果を比較してみましょう:
::

    >>> hierarchy
    array([[[ 1, -1, -1, -1],
            [ 2,  0, -1, -1],
            [-1,  1, -1, -1]]])
            
最も外側の輪郭のみを検出したい時にこのフラグを使いましょう．

3. RETR_CCOMP
------------------           

このフラグは全輪郭を検出し，2レベルの階層に分類します．物体の外側の輪郭は階層1，物体の内側の穴などの輪郭は階層2と分類されます．もし物体内に物体がある場合は，その物体は階層1となり，その穴は階層2となります．

黒地に白く書かれた0を想像してみてください．0の外側の円は第一の階層，内側の円は第二の階層に属します．

例として以下の画像を見てください．輪郭のインデックスを赤い文字，その輪郭が属する階層を緑いろの文字で書きました．インデックスはOpenCVが検出する輪郭の順番と同じようになっています．

    .. image:: images/ccomp_hierarchy.png
        :alt: CCOMP Hierarchy
        :align: center

輪郭0は階層1に属しています．輪郭0が持つ二つの穴である輪郭1と輪郭②はどちらも階層2に属しています．輪郭0の同一階層レベルの次の輪郭は輪郭3となり，前の輪郭は存在しません．First_Childは階層2に属する輪郭1となり，Parentはありません．結果として，輪郭0の階層arrayは[3,-1,1,-1]となります．

次に輪郭1を見てみましょう．Nextは同一階層に属している(輪郭1のParentの下)輪郭2です．前の輪郭，子要素はありませんが親は輪郭0になります．結果として，階層arrayは[2,-1,-1,0]となります．

同様に輪郭2は階層2となり，Nextはありませんが，Previousは輪郭1となります．子要素はなく，親は0となるため階層arrayは[-1,1,-1,0]となります．

階層1に属する輪郭3のNextは輪郭5，Previousは輪郭0，Childは輪郭4となり，Parentはありません．よって，階層arrayは[5,0,4,-1]です．

輪郭3の下の階層2に属する輪郭4は同一階層に輪郭がないため，NextもPreviousも―1となります．子要素もありませんが，Parentは輪郭3なので，階層arrayは[-1,-1,-1,3]となります．

他の輪郭については自分で考えてみてください．関数を使って得られた結果は以下のようになりました:
::

    >>> hierarchy
    array([[[ 3, -1,  1, -1],
            [ 2, -1, -1,  0],
            [-1,  1, -1,  0],
            [ 5,  0,  4, -1],
            [-1, -1, -1,  3],
            [ 7,  3,  6, -1],
            [-1, -1, -1,  5],
            [ 8,  5, -1, -1],
            [-1,  7, -1, -1]]])
            

4. RETR_TREE
------------------ 

これが最後のフラグです．全輪郭を検出し，全階層情報を保持します． **家族について祖父，父，息子，孫，...と全情報を保持します... :)**．

例えば，上記の画像に対してcv2.RETR_TREEを使って得られた結果に基づいて輪郭のインデックス及び階層のインデックスを描いた図を以下に示します．

    .. image:: images/tree_hierarchy.png
        :alt: CCOMP Hierarchy
        :align: center

輪郭0は階層0に属します．次の輪郭は同一階層内に属する輪郭7となります．前の輪郭はなく，子要素は輪郭1となります．親要素は無いため，階層arrayは[7,-1,1,-1]となります．

輪郭2は階層1となり，同一階層には他に輪郭がないため，Next, previousは共に―1となります．Childは輪郭2，Parentは輪郭0となるため，階層arrayは[-1,-1,2,0]です．

RETR_CCOMPの例と同様，その他の輪郭については自分で計算してみてください．以下に関数を使って得られた結果を示します:
::

    >>> hierarchy
    array([[[ 7, -1,  1, -1],
            [-1, -1,  2,  0],
            [-1, -1,  3,  1],
            [-1, -1,  4,  2],
            [-1, -1,  5,  3],
            [ 6, -1, -1,  4],
            [-1,  5, -1,  4],
            [ 8,  0, -1, -1],
            [-1,  7, -1, -1]]])
            
補足資料
=======================

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