目的

今回は、輪郭の階層構造、すなわち輪郭における親子関係について学ぶ。

理論

これまでの輪郭に関する数回の記事では、OpenCVが提供する輪郭関連のいくつかの関数を扱ってきた。しかし cv.findContours() 関数を使って画像中の輪郭を見つける際には、Contour Retrieval Mode（輪郭検索モード）という引数を渡してきた。通常は cv.RETR_LIST または cv.RETR_TREE を渡し、それでうまく動作した。しかし、これは実際には何を意味するのだろうか？

また、出力としては3つの配列が得られた。1つ目は画像、2つ目は輪郭、そしてもう1つ hierarchy と名付けた出力である（前の記事のコードを参照してほしい）。しかし、この hierarchy はこれまでどこにも使ってこなかった。では、この hierarchy とは何で、何のためにあるのだろうか？前述の関数引数とはどのような関係があるのだろうか？

それがこの記事で扱う内容である。

階層構造とは何か?

通常、画像中のオブジェクトを検出するために cv.findContours() 関数を使う。オブジェクトはそれぞれ異なる位置にあることもある。しかし、ある形状が別の形状の内部にある場合もある。ちょうど入れ子になった図形のようにである。この場合、外側のものを 親(parent)、内側のものを 子(child) と呼ぶ。このように、画像中の輪郭は互いに何らかの関係を持つ。そして、ある輪郭が他の輪郭とどう繋がっているか、例えば他の輪郭の子なのか、親なのかといったことを表現できる。この関係の表現を 階層構造(Hierarchy) と呼ぶ。

以下の例の画像を考える:

image

この画像には、0-5 と番号を付けたいくつかの形状がある。2 と 2a は最も外側のボックスの外側輪郭と内側輪郭を表す。

ここで、輪郭 0,1,2 は 外側または最も外側(external or outermost) である。これらは hierarchy-0 にある、あるいは単純に 同じ階層レベル(same hierarchy level) にあると言える。

次に contour-2a がくる。これは contour-2 の子 と見なせる（逆に言えば、contour-2 は contour-2a の親である）。これを hierarchy-1 としよう。同様に contour-3 は contour-2a の子であり、次の階層に入る。最後に、contour 4 と 5 は contour-3a の子であり、最後の階層レベルに入る。ボックスに番号を付けた順序から言えば、contour-4 が contour-3a の最初の子であると言える（contour-5 であってもよい）。

これらのことに触れたのは、同じ階層レベル(same hierarchy level)、外側輪郭(external contour)、子輪郭(child contour)、親輪郭(parent contour)、最初の子(first child) といった用語を理解してもらうためである。では、OpenCVに入っていこう。

OpenCV における階層構造の表現

このように、各輪郭は、自分がどの階層にあるか、誰が子で誰が親かといった独自の情報を持つ。OpenCVはこれを4つの値の配列として表現する : [Next, Previous, First_Child, Parent]

"Next denotes next contour at the same hierarchical level."

例えば、この図の contour-0 を取り上げる。同じレベルにおける次の輪郭は誰だろうか？ contour-1 である。したがって単純に Next = 1 とする。同様に Contour-1 について、次は contour-2 である。よって Next = 2 となる。

contour-2 はどうだろうか？同じレベルに次の輪郭はない。したがって単純に Next = -1 とする。contour-4 はどうだろうか？これは contour-5 と同じレベルにある。したがってその次の輪郭は contour-5 であり、Next = 5 となる。

"Previous denotes previous contour at the same hierarchical level."

これは上と同様である。contour-1 の前の輪郭は、同じレベルの contour-0 である。同様に contour-2 については contour-1 である。そして contour-0 については前のものがないので、-1 とする。

"First_Child denotes its first child contour."

特に説明は必要ない。contour-2 については、子は contour-2a である。したがって contour-2a に対応するインデックス値を取る。contour-3a はどうだろうか？これには2つの子がある。しかし最初の子だけを取る。それは contour-4 である。したがって contour-3a については First_Child = 4 となる。

"Parent denotes index of its parent contour."

これは First_Child のちょうど逆である。contour-4 と contour-5 の両方について、親輪郭は contour-3a である。contour-3a については contour-3 であり、以下同様である。

覚え書き: 子や親がない場合、そのフィールドは -1 とされる

さて、OpenCVで使われる階層構造のスタイルが分かったので、上で示したのと同じ画像を使ってOpenCVの輪郭検索モード(Contour Retrieval Modes)を確認していこう。すなわち cv.RETR_LIST、cv.RETR_TREE、cv.RETR_CCOMP、cv.RETR_EXTERNAL などのフラグは何を意味するのか？

輪郭の取得モード

1. RETR_LIST

これは4つのフラグの中で（説明の観点から）最も単純なものである。単純にすべての輪郭を取得するが、親子関係は一切作らない。このルールのもとでは親も子も対等であり、いずれも単なる輪郭にすぎない。すなわち、すべて同じ階層レベルに属する。

したがってここでは、階層配列の3番目と4番目の項は常に -1 になる。しかし当然ながら、Next と Previous の項にはそれぞれ対応する値が入る。

2. RETR_EXTERNAL

このフラグを使うと、最も外側の輪郭だけが返される。すべての子輪郭は無視される。この方式では、各ファミリーで最年長者だけが扱われ、ほかのメンバーは考慮されない、と言える。

3. RETR_CCOMP

このフラグはすべての輪郭を取得し、それらを2レベルの階層構造に並べる。すなわち、オブジェクトの外側輪郭（つまりその境界）は hierarchy-1 に配置される。そしてオブジェクト内部の穴の輪郭（もしあれば）は hierarchy-2 に配置される。その内部にさらにオブジェクトがあれば、その輪郭は再び hierarchy-1 に配置される。そしてその穴は hierarchy-2 に、以下同様である。

黒い背景に「大きな白いゼロ」がある画像を考えてみよう。ゼロの外側の円は第1階層に属し、ゼロの内側の円は第2階層に属する。

簡単な画像で説明できる。ここでは輪郭の順序を赤色で、それが属する階層を緑色で（1か2のいずれか）ラベル付けしてある。順序はOpenCVが輪郭を検出する順序と同じである。

image

では最初の輪郭、すなわち contour-0 を考える。これは hierarchy-1 にある。2つの穴、contours 1&2 を持ち、それらは hierarchy-2 に属する。したがって contour-0 について、同じ階層レベルの次の輪郭は contour-3 である。そして前のものはない。最初の子は hierarchy-2 の contour-1 である。hierarchy-1 にあるため親はない。したがってその hierarchy 配列は [3,-1,1,-1] となる

次に contour-1 を取り上げる。これは hierarchy-2 にある。同じ階層（contour-1 の親のもとで）の次のものは contour-2 である。前のものはない。子はないが、親は contour-0 である。したがって配列は [2,-1,-1,0] となる。

同様に contour-2 : これは hierarchy-2 にある。contour-0 のもとで同じ階層に次の輪郭はない。したがって Next はない。前のものは contour-1 である。子はなく、親は contour-0 である。したがって配列は [-1,1,-1,0] となる。

Contour - 3 : hierarchy-1 の次は contour-5 である。前のものは contour-0 である。子は contour-4 で、親はない。したがって配列は [5,0,4,-1] となる。

Contour - 4 : これは contour-3 のもとで hierarchy 2 にあり、兄弟はない。したがって next も previous も child もなく、親は contour-3 である。したがって配列は [-1,-1,-1,3] となる。

4. RETR_TREE

そしてこれが最後の登場人物、Mr.Perfect である。これはすべての輪郭を取得し、完全な家系の階層リストを作成する。誰が祖父で、父で、息子で、孫で、さらにそれを超えてまで教えてくれる... :)。

例えば、上の画像を取り上げ、cv.RETR_TREE 用にコードを書き直し、OpenCVが返す結果に従って輪郭を並べ替え、それを分析した。ここでも、赤い文字は輪郭の番号を、緑の文字は階層の順序を表す。

image

contour-0 を取り上げる : これは hierarchy-0 にある。同じ階層の次の輪郭は contour-7 である。前の輪郭はない。子は contour-1 である。そして親はない。したがって配列は [7,-1,1,-1] となる。

contour-2 を見てみよう。これは hierarchy-1 にある。同じレベルに輪郭はない。前の輪郭もない。子は contour-2、親は contour-0 である。したがって配列は [-1,-1,2,0] となる。