九州工業大学研究報告（工学）No．58 1989年3月 69
画像の複雑さによる多値画像の領域分割に関する考察
（昭」和63年11月30日 原稿受付）
電気工学科計算機コース鎌田清一郎 江 川 護 河 口 英 二
AStudy on Image Segmentation for Multi−Valued Image using Picture Complexity by Seiichiro KAMATA Mamoru EGAWA Eiji KAWAGUCHI
Abstract
This paper discribes a study for image＄egmentation using picture complexity． When an N bit 三mage is thresholded at each gray．level，2N一ユbinary pa枕ems are produced． In acc（）rdance wl也the human v輌si《）n system， thresh◎lded biMry pattem sh◎uld be simple， i、 e．， the pic知re complex量之y should be locally minimum at the optimum threshold point on the complexity curve， The complex．
ity curve is defined as the picture complexity change along the 2N thresholding values from O to 2N．
1． Amodified image segmentaion algorithm based upon the sp§t．and−merge approach is imro．
duced t◎1緬玄P・琉e edge輌n伝mat輌・n，輌nclud呈ng thresholding vぬe，輌n缶segme撤at三〇n decisions．
Experiments were carried out using sample image data． The results are discussed．
してエッジ追跡が失敗しやすくなり，処理が複雑かつ処 1．はじめに
理量が膨大となってしまう。従って，本論では処理の単 画像理解における領域分割は，原画像データから抽象 純さ，並列化の面で前者の場合について局所領域の閾値 的な記号データに置き換えるための基本領域の抽出と捉 処理を領域分割の観点から考察する。
えることができる。領域分割手法は従来から多くの研究 谷口等④は多値画像の二値化処理における閾値の最 が行なわれおり（1）（2）（3），大別すると次の3つに分類 適性について論じたがこれはゲシュタルト心理学にお できる。 ける「人間が画像の中に何らかの意味情報を見いだそう （a）濃度ヒストグラムによる閾値処理 とするとき，なるべく単純なパターンとして画像を捉え （b）Split and Merge る」という特性を利用したものである。人間の視覚にお （c）エッジ抽出と境界追跡による分割 ける一特性を考えると，画像中のパターンを識別すると （⇒は最も基本的な方式で多画像を細かな正方領域に分 きはパターンがより簡単になるように捉えていると考え 割してその領域内の濃度ヒストグラムの多峰性を利用し られる。すなわち，いくつかの領域に分割するとき，そ て閾値処理し，基本領域に分割する場合である。また， の閾値を与えられた多値画像が簡単なパターンとなるよ くb）は画像の階層性を利用したデータ量削減のための基本 うに決定することができればよい。本論ではまず，画像 的な手法と言える。（C）はエッジ抽出の結果から領域の境 の複雑さと閾値処理についてその概要を示し，次に，画 界を追跡するものである。（a），（b）は平坦な部分を重視し 像の複雑さを尺度にして，局所領域内の評価を行いなが ているのに対し，（c）についてはエッジ部分に重点をおい ら階層的に領域分割する手法について述べる。最後に，
た手法である。しかし，（c）はエッジ抽出問題さらに， 他の領域分割法との比較実験を通して本手法を考察する。
エッジ部分でわずかにぼけたノイズ部分を含む画像に対
2．多値画像の複雑さ 、よる閾値処理 値画像がその影響で非常に複雑になるためである・次に・
θ1を越えると今度は逆に簡単な二値画像となっていく。
2．1二値画像のDF表現における複雑さの尺度（4） さらに，進めていくと，文字部の濃度レベルθ2付近に 2R×2Rの二値画像が図一1（a）のように与えられると， なると今度はまた複雑になっていく。その後は，2Nに その4分木は図一1（b）のように示される。DF表現（6） 近づくにしたがってほとんど真っ白の二値画像になって は4分木の 葉ノード を 0 または 1 に， 葉でない しまう。このように，与えられた多値画像が簡単なパ ノード を （ に対応させる表記法である。また，表記 ターンとなるように閾値を決定することを考える。この の順序は4分割画面内で左下→右下→左上→右上である。 ことは複雑さを尺度とした閾値処理による基本領域の抽 図一1の場合，（（01011（110（10000となる。このとき， 出と捉えることができる。
複雑さの尺度は
3．階層的領域分割 葉ノードの数
Cp＝・・ （1） 3．1階層的分割処理
によって与えられる。複雑さCpは0から1までの値を 一般に多値画像は画像全体で複雑さの変化を見てみる とり，最も複雑になるのは市松模様の場合である。 と，単峰性を示すものが殆どであるが，局所部分につい 2．2 多値画像の閏値処理 て見ると多峰性を示すようになる。このことから本論で 画素Nビットの多値画像を各濃度レベルごとにスラ は画像を全体から局所へと階層的に複雑さを尺度とした
イスすると2N−1通りの二値画像が得られる。このこ 閾値処理を行うことを考える。ある領域で単純に多峰性 値画像に複雑さの尺度を導入し，濃度レベルに対する複 が現れた場合にすぐ分割するのは領域の概略を知るには 雑さの変化を見ると図一2のように単峰性あるいは多峰 好都合であるが，細部まで見ようとするとさらに小領域 性を示す曲線が現れる。この濃度レベルに対する複雑さ でみる必要がある。すなわち，多峰性を示す場合でも閾 の曲線を以下・複雑さ曲線と呼ぶ。閾値処理が可能なの 値処理出来ないいくつかの領域が一つの峰に混在してい は多峰性を示す画像であって，複雑さの曲線上で極小点 る場合も考えられる。この判断は図一3（b）に示される一 に分割した場合，原画像においてある濃度レベル範囲の つの峰に閾値処理した場合の，閾値の上限θ1と下限θ2 複数の領域に分割されるのがわかる。例えば，図一3（a）
に示される文字の2値化処理の場合をσ‖にとって説明す Cp
る。図一3（b）に示される複数さ曲線を濃度レベル0から 次第に見ていくと，段々とスライスして得られた二値画 像が複雑になり，背景部の濃度レベルθ1付近で二値画 像が極めて複雑な画像を示す。これは，濃度レベルがほ ぼ一疋の平坦な部分にノイズが乗ると，スライスした二
Cp
ノへ＼ ノ▽＼
｛ 、 濃度レベル 濃度レベル
（a）単峰性 （b）多峰性
図一2 単峰性と多峰性
Cp
（a）二値画像 （b）4分木 0 θ1 θ2 濃度レベル （a）多値画像 （b）複雑さ曲線
図一1 二値画像の4分木 図一3 多値画像の複雑さ曲線
画像の複雑さによる多値画像の領域分割に関する考察 71
の差によって求めることにする。すなわち， が存在する。これを図一6｛b）のようにR・1，R・2に分割 ｝θ1＿θパ しなければならない。これは領域R内の連結関係を調べ
2・＞H1 （2）ることは嫁めることができる．
であれぱさらに小領域に分割し，そうでなければ，そ Pτocedure ex垣τim．region（r，⇒M，P）
れ以上の小領域分割を行わない。また，多峰性か否かを （1）領域r，α内の画像f（x，y）に対して，
見るため，極小点の抽出においては両端の極大点レ1， S1 ：f（x， y）＜pユ，
レ2に対して， S2 ：Pl≦f（x， y）〈p2，
Cp（レo） ‥・
m・・［C・（・1），C・（・，）］≦H2 ｛3） SM，PM．1≦f（罵，）〈，脇
を満たすとき，μoを極小点とする。 SM＋1：PM≦f（x， y）
次にアルゴリズムを示す。ただし，分割の方法は4分 となる基本領域ラベルS1， S2，…， SM， SM＋1を求 木を考え，αは図一4に示される局所画像のアドレスで， め，その領域の情報を領域情報テーブルに追加格納 rは局所画像の大きさを示す画面の次数である。 する。
Pr◎cedure seg（r，の （2）基本領域S1内で連結しない部分領域S 1， S 2，…を
（1）各濃度レベルに対して・複雑さの曲線を求める。 抽出し，再びラベル付けをし，領域情報テーブルに
（2）複雑さの曲線で極小点数Mと極小点P1， P2，…， 追加格納する。
PMを計算する。 （3）retum、
（3）極小点数M≧1かつ・式（2）を満たすとき 領域情報テーブルは図一一7のように基本領域Siの含ま ext．prim工egion（r・α・M・P）・ れる正方領域アドレスα，正方領域サイズr， Si内の濃
（4）それ以外のとき 度レベルの上限θ㎜。xと下限θ㎜、。，ピク位置θ。，そし
seg（r＋1，α00）， て，正方領域の外周の上下左右の隣接状況である。隣接 seg（r＋1，α01）， 状況は外周上の（上端，開始点，終点），（下端，開始点，
seg（r十1，α10）， 終点〉，（左端，開始点，終点），（右端，開始点，終点）
seg（r十1，α11）， で与えられる。
（5） Re知m、
ここで，ext pr輌m reg輌◎nは最も基本となる領域の抽出 CP を行う手続きである。この詳細に分割した領域を基本領
域と呼ぶ。すなわち，図一5（・）に示される複雑さ曲線に おいてθ1，θ2で囲まれた部分は図一5（b）における領域
八
Rに相当する。しかし，このとき，図一6（∋に示される 0 θユ θ、 濃度レベル ような2つの領域が同じ濃度レベルを有するような場合
（a）複雑さ曲線 （b）基本領域
図一5 閾値処理と基本領域の関係
（2，1010）
（2，1000）
（1，00） （1，01）
（r，の
R3 R3
（a） θ
図一4 画面上のアドレスαと次数r 図一6 基本領域内分離
ラベル 領域アドレス 領域サイズ 相対指標 θm。x θmln θP 隣接関係
α1
ｿ2 c
rl 窒Q
F
30 U0 c
60 X5 c
50 V9 c
（上，5，8）
i下，1，9）
@ … 図一7 領域情報テーブル
3・2 ボトムアップ併合処理 によって求められる。最終的な結果は図一9に示される トップダウン的に分割した基本領域から，ボトムアッ 併合テーブルに格納する。
プ処理により領域併合処理を行う。この処理における基 procedure Merge 準となる指標は領域のピーク位置，濃度レベルの上限， （1）i＝o．
下限である。すなわち，図一8に示されるように隣接す （2）すべての基本領域Siについて処理終了であればス る併合領域R1， R2間でピーク位置θ3とθ 3との差と， テップ（7）へ。
θ1，θ2とθ 1，θ 2の重なり具合いによって併合かを （3）領域情報テーブルより基本領域Siをとってくる。
決定する。すなわち， （4）基本領域S、に対して併合テーブル内の隣接するす 1θ3一θ 31〈H3かつ べての併合領域R、とのθ3とθ 3との差，θ1，θ2 0verlap．region（θ1，θ2，θ 1，θ 2）＞H4 （4） とθ 1，θ 2の比較により併合するかどうかを決定 であれば併合し，それ以外は併合しない。ここで，関数 する。併合であれば併合領域R、に基本領域S、を追 overlap−regionは線分［θ1，θ2］と［θ 1，θ 2］の重なっ 加する。
た部分の長さをρとすると，［θ1，θ2］∪［θ 1，θ 2］に （5）i＝i＋1．
対する［θ1，θ2］∩［θ 1，θ 2］の比で与えられ， （6）ステップ（2）へ。
…一一一 c（ ρ ﾆ、，θ・、）−mi。（θ，，θ・，）（5）（7）
I鷲竺㌫㌶誉㌶脅れ1よ
（8）return．
Cp 々ノ θ3
1太 4・実験
iii l 1 4．1領域数の評価
0 θ1 θ2 パラメータH1， H2， H3， H4に対する基本領域数と
Cp
併合領域数との関係について述べる。表一1にはパラ 〆θ 3 メータH1， H2と基本領域数との関係，また，表一2に
，， ， はパラメータH3， H4と併合領域数との関係を示す。原
川 l
l！ ： 画像は図一10 に示されるGIRL（512×512画素，1画
分割領域 基本領域
S1， S3， Slo r2， S5， S7， S20
@ …
0 θ㌧ θ 2 素当り8ビット）である。また，それぞれのパラメータ に対して得られた諸特性を以下に示す。
図一8 併合のためのパラメータ
a）H1は正規分布を仮定した場合の分散に相当する。基 本領域の個数はH1の増加に対して反比例して少な くなる。
基本領域 b）H2は基本領域の個数に比例するパラメータであるが S1， S3， Slo 複雑さ曲線上の極小点の抽出ミスを防ぐため，0．9〜
S2， S5・S7・S20 0．98で設定する。このパラメータに対する基本領域 の個数はそれほど変化しない。
図一9 併合テーブル c）H3は，変化領域数を見てみるとH3＝3程度までは
画像の複雑さによる多値画像の領域分割に関する考察 73
表一1 H1， H2と基本領域数との関係 状を求めることができる。しかし，細かな分割が困難で，
抽出できでいない部分がかなり存在する。本手法では 基本領域数 エッジ部分がほぼ抽出され，大体の人物の輪郭などが確 訳： 認できる・牛・・（・）が併合領撒が多い場合である坑 1719 正方領域の輪郭がかなり目につく。図一11（c）はその正方 1131 領域の輪郭の発生を少なく抑えた場合である。図一11（d）
2568 は基本領域が少ない場合で，Spilit and Merge法の結果 2530 に近くなっている。しかし，人物の左肩付近で濃度変化 の滑らかな部分に対してエッジ抽出を失敗しているが，
このような部分がパラメータの調整によっても困難な部 表一2 H3， H4と併合領域数との関係（H1＝0． 分である。画像理解における領域分割を考えた場合は情 6・他＝0・98・基本領域勤567） 報の抜けが少なくてすむように図一11（b＞のパラメータ設 併合領域数 定が妥当であろう。
H
H2 基本領域数
0．3 0．90 2446
◎．4 ◎．9◎ 21◎0 0．5 0．90 1719
◎．6 （》．9◎ 1306
0．7 0．90 1131
◎．3 O．92 2551
0．3 0．94 2568
◇．3 o．95 2§79
0．3 0．96 2530
0．3 o．98 2487
H3 H4 併合領域数
1
