はじめに
「分割・統合（Split & Merge）法」は、領域分割の手法の一つです。「領域分割」とは、1枚の画像を性質（特徴）が一様である部分領域に分割することです。分割・統合法は、単純で興味深いアルゴリズムを利用しているが特長で、具体的には以下のような目的で利用されます。
- 画像を同じような色の領域に分ける
- レントゲン写真を同じような模様に分ける
- 部分領域の形から被写体が何かを推測する
- 航空写真から道路を抽出する
- 人物画像から服を抽出する
ここでは、最も簡単な「色を基準に分割する方法」を解説します。また、時間のかかる処理なので、高速化にも注力します。
また余談ですが、この方法を改良して「PRMUアルゴリズムコンテスト」に応募された方が審査員特別賞を受賞されました！
対象読者
C++言語とWin32APIの基礎を習得している方を対象とします。C++言語はクラスの基礎がわかっていれば大丈夫です。画像の入出力方法については解説しませんが、便利なクラスを付加しますので、よくわからない方は使い方だけを覚えて下さい。DIB（デバイス独立ビットマップ）やDIBSectionがわからない方、画像入出力を勉強したい方は私のホームページに来て下さい。
必要な環境
Visual C++ .NET 2002で開発し、Windows XP SP2で動作確認を行っています。Windowsプログラムが動く環境が必要です。時間のかかるプログラムなので、あまりに遅い環境は非推奨です。
理論
分割・統合法は、その名前が示すとおり、分割と統合を組み合わせて領域分割を行う手法です。図2のように、「分割過程」で領域を小さな四角形に分割し、「統合過程」でそれらを統合して多角形に成長させていきます。この手法の利点は、処理の自由度が高いことですが、処理に時間がかかるという欠点もあります。
図2は分割・統合法の概念図です（クリックすると拡大）。分割が終わった後で統合することに注意して下さい。
分割過程
分割の手順は以下のようになります。
- 画像全体を一つの部分領域と見なす。
- 対象とする部分領域が一様ではない（複数の部分領域に分けられる）と判断した場合は、縦横に2等分する（つまり4等分）。
- 1/4に分割された各部分領域において、再び「2.」の処理を行う。
- 上記「2.」「3.」の処理を、各部分領域の画像の性質が一様になるまで繰り返す。
「2.」で分割を判断する基準を「分割条件」と呼ぶことにします。分割条件は最終結果を左右する重要な要素です。分割条件には色々なものが考えられますが、今回は最も基本的な濃度ヒストグラムを利用します。この際、濃度ヒストグラムが「単峰性」なら画像の性質が一様であると判断し、「多峰性」なら画像の性質は一様ではないと判断します。
「山」はヒストグラムの盛り上がっているところを指し、「谷」は凹んでいるところを指します。また、山の最も高い位置を「山頂」、谷の最も低い位置を「谷底」と言うことにします。
濃度=(R+G+B)/3です。ヒストグラムの単峰性を判定する処理は、一つの研究テーマになるほど奥深いものです。ヒストグラムは一般に複雑な形状をしているので、単純に傾きを調べるような手法では全く通用しません。しかし、これといった手法が確立されているわけでもありません。今回は、簡易なアルゴリズムとして、以下の手法で単峰性を判定することにします。
- ヒストグラムを平滑化する。
- 最も高い山頂に隣接する、左の谷底から右の谷底までの面積（つまり、最も大きい山の面積）を求める。
- 「2.」で計算した面積とヒストグラム全体の面積との割合を求めます。
- 「3.」で求めた割合が、ある値以上なら単峰性とします。
ここで指定する割合は、分割の可否を左右する重要な要素です。試行錯誤してみて下さい。
分割過程で重要なポイントは、部分領域を縦横に2等分（4等分）するということです。最適な分割位置などは全く考えずに、単純に等分してしまうのです。複雑な条件で最適な分割位置を求めていけば、分割回数は減るかもしれません。しかし、処理時間は短縮されるでしょうか。むしろ増大するかもしれません。それならば、単純なアルゴリズムのままの方が良いでしょう。無駄に分割されたとしても、統合段階で相殺されるので問題ありません。
統合過程
統合の手順は以下のようになります。
- 分割後の各部分領域の性質を調べる。
- 自分と上下左右に隣接する二つの部分領域の性質の差が、ある値未満なら、これら二つの部分領域を一つに統合する。
- 上記「1.」、「2.」の処理を、統合すべき部分領域が無くなるまで繰り返す。
統合条件も最終結果を左右する重要な要素です。性質としては、分割の時に用いた濃度を、統合でも用いるのが普通です。具体的には、濃度の平均値、分散、標準偏差など、いろいろ考えられますが、今回は最も基本的な濃度の平均値を用いることにします。隣接した部分領域の平均値の差が、ある値未満の場合は統合します。
なお部分領域を統合すると、平均濃度値を計算し直すことになるので、どこから走査するかで最終結果が異なるものになる可能性があります。しかし、この問題には対処しようがないので、考えないことにします。
微小領域の統合
以上が分割・統合法のアルゴリズムですが、実用的には、面積の小さすぎる領域は分割しても意味がない場合もあるでしょう。従って、微小領域は、隣接する最も性質の近い領域に統合するオプションを用意します。隣接領域の判定は、単純に上下左右を調べるだけでは足りません。この段階では、領域の形状は複雑になっているので、微小領域の輪郭をトレースすることによって隣接領域を調べます。
以上をまとめると、微小領域の統合の手順は以下のようになります。
- ある値より面積の小さい領域を探す
- その部分領域の輪郭をトレースする
- 隣接領域の中で、最も性質の近い隣接領域と統合する
- 上記「1.」、「2.」、「3.」の処理を、統合すべき部分領域が無くなるまで繰り返す
