画像の分割・統合による粗輪郭からの対象物抽出の分割順次処理

Osaka Gakuin University Repository

Title

画像の分割・統合による粗輪郭からの対象物抽出の分割 順次処理

Blockwise Processing of Object Extraction from Rough Trace of Contour with Block Division and Integration of Image

Author(s) 淡 誠一郎 (Seiichiro Dan)

Citation 大阪学院大学 人文自然論叢（THE BULLETIN OF THE CULTURAL AND NATURAL SCIENCES IN OSAKA GAKUIN UNIVERSITY)，61-62：23-40

Issue Date 2011.03.31 Resource Type Article/ 論説 Resource Version

URL Right Additional Information

大阪学院大学 人文 自然論叢 <論 説

>

第6162号 2011年 3月

画像 の分割 ・統合 に よる粗 輪 郭 か らの

対象物抽 出の分割順次処理

淡

誠 一 郎

Blockwise

Processing

of

Object Extraction

from

Rough Trace

of

Contour

with

Block Division

and

Integration

of

Image

Sellchiro]Dan

概 要 本論文では、画像合成のための対話形式の対象物抽出アルゴリズムを取 り上げ、問題分 割 による処理の効率化 について検討する。対象 とす る手法 は、粗輪郭 とよばれ る太 く大 ま かに描 いた輪郭線 を一定の順序で細線化す ることによ り、対象物 の輪郭 に沿 った閉曲線 を 得 る手法である。 この手法は、アルゴリズムが単純 な割 に良好 な抽 出結果が得 られ ること で知 られているが、全体的な処理であ り、繰 り返 し計算 を伴 うために計算量が大 きいのが 欠点である。 このアルゴリズムは、画像全体の画素 を順序付 け して逐次的に処理す るため、 理屈の上では問題分割の考 え方 とは相いれない。 しか し、輪郭線の トレースは直観的には 局所的な処理であ り、問題分割や並列処理 と親和性が高いはずである。本稿では、画像 を 分割 して当該 アルゴリズムを適用 した場合の問題点 を分析 し、それを克服で きるような画 像分割・統合法 を提案す る。

1.は

じめ に 画像理解や コンピュー タビジ ョンの研究 において、画像 を意味のあるい くつかの領域 に 分割 した り、画像か ら物体や人物の存在す る候補領域 を抽出 した りす る処理 は、情景理解 にいたる前段階処理 と位置づ け られてお り、認識や理解の前提 として達成すべ き重要 な処 理である。 しか し、何 をもって意味のある領域 とみなすかは、情景のみによって決 まるこ とが らではな く、個人の背景知識や、問題、 目的によって も変化す る。それ らを計算機 シ - 23 -―

人 文 自 然 論 叢 61-62 ステムが推 し測 ることは困難であ り、対象を限定することな しに、対象物抽出を完全 自動 化す ることは、事実上不可能 といって よい。 本研究は画像か らの対象物抽出を扱 うものであるが、その 目的は画像の合成、す なわち、 あ る画像 中の人物や物体 を抜 き出 し、別の背景画像 と合成す ることを想定 している (図 1)。 対象の識別が 目的の場合 は、重要 な特徴 さえ損 なわれていなければ、抽 出される領 域 はそれほ ど厳密でな くて も構 わない。 しか し、 ここでは画像合成 を目的 としているので、 なるべ く物体の輪郭 を忠実に とらえることが肝要 となる。 「

ヽ

吟

_リ

背 景 画像 図

1

画像か らの対象物抽出と画像合成

鍼

う

テ レビ番組の制作現場 などでは、 クロマキー合成 (色の着いたスクリー ンを背景に用 い、 同系色 を透明化 して背景映像 と合成す る方法

)な

どが用い られるが、既存の写真の一部 を 切 り出 して使 いたい ような場合 にはクロマキー合成は使 えない。上 に述べた ように、一般 の画像か ら人間の意図す る任意の対象物 を切 り出す ことは困難であるゆえ、人間がデ ジタ 抽 出対象 を含む画像 合 成画像 図

2

輪郭線 トレー スツー ルの使 用例 (P」ntgraphlc2,Ver1 0 0)

画像の分割・統合 による粗輪郭か らの対象物抽 出の分割順次処理 図

3

粗輪郭からの対象物抽出 イザペ ンやマ ウス等で輪郭線 をなぞって対象 を指定せ ざるをえない。 しか し、デジタイザ ペ ンやマ ウスで輪郭 を正確 に トレースす るのはなかなか骨の折れ る作業である。最近の フ ォ トレタッチ ソフ トには、大雑把 に トレースす るだけで、対象のエ ッジに沿 うように トレ ース線 をフィッ トさせて くれるツールをもつ もの もあるが、背景が複雑だ と意図せぬ結果 とな り、む しろ煩 わ しくさえある (図 2)。 これに対 し、井上 ら

[1,2]は

、 まず手動で輪郭の存在領域 を幅のある閉曲線 (以下、 粗輪郭 とよぶ

)で

大 まかに与 え、エ ッジ強度 (明度の空 間微分値

)に

基づ く走査順序で こ の領域 を細線化す ることで対象物 の正確 な輪郭線 を得 ようとす る手法 を提案 した (図 3)。 この手法 はアルゴリズムの単純 さの割 には良好 な抽出結果が得 られるのが特徴 であるが、 通常の細線化 に比べ て計算量が非常に大 きくなるのが難点である。淡 ら

[3]は

井上 らの アルゴリズムの見直 しを行い、デー タ構造 とアルゴリズムの実装方法の工夫 によ り、周囲 長1000画素程度の対象物の抽 出で数十倍の改善率が得 られることを報告 している。 画像処理 は、広い範囲の画素 を参照 して行われる大局的処理 と、各画素の近傍や小領域 内の画素だけを参照 して行 われる局所的処理 に大別で きる。井上 らの方法 は、粗輪郭中の 画素全体 をエ ッジ強度の弱 い順 に処理 してい くため、画像全体 を参照す る大局的処理 (以 下では全体的処理 とよぶ

)で

ある。 この事情 は改良手法で も変わ らない。 一方、人が物体の輪郭線 をベ ンで トレースす る場合 を考 えてみると、トレースは今 まさ にベ ン先がおかれた点の比較的狭 い近傍だけを見て行 うのが普通であ り、輪郭位置の判 断 が遠 く離れた部位の影響 を受 けるとは考 え難い。例 えば、人物の トレースな ら、頭頂部の トレース時に遠 く離れた腕や脚 に 目を向ける必要はなかろう。おそ らく顎や頬 さえも頭頂 部の輪郭の半J断には影響 を与 えない。 この ことは、輪郭線抽 出のアルゴリズムが画像全体 ではな く、小領域の情報だけを基 にした計算 となるように改 良可能であることを示唆 して いる。淡

[4]は

その可能性 を探 るべ く、画像 を単純 にい くつかの区画 に分割 して処理 し、 結果を統合 した場合 についての基礎実験 を試み、分割処理や並列処理の可能性 と問題点 に ついて考察 した。本稿 では、そこで指摘 された問題点への対応 について検討 し、粗輪郭か ―- 25 -―

人 文 自 然 論 叢 61-62 らの対象物抽 出の分割処理手法 を提 案す る。

2.粗

輪 郭 か らの 対 象 物 抽 出 ア ル ゴ リズ ム まず、対象 となるアルゴリズムの概要は以下の とお りである。 入力 :[抽 出対象画像](濃淡画像) [粗輪郭画像

](2値

画像) 本 アルゴリズムでは、対象物の輪郭 を太い線で粗 く トレース した閉曲線 を “粗 輪郭

"と

よび、粗輪郭上の画素 を1、 それ以外 を0と _した

2値

_{画像 を粗輪郭画像} とよぶ。 手順

:

粗輪郭 を構成す る画素の うち、削除 して も粗輪郭領域の連結性が保存 されるよ うな画素の中で、抽出対象画像 における同位置のエ ッジ強度が最 も弱い点 を見つ け、順次取 り除いてい く。削除可能な画素が無 くなった時点で幅1画素の閉 じた 輪郭線が得 られる。得 られた輪郭線の内部 を対象物 として出力す る。 井上 らのオ リジナルのアルゴ リズム (図

4(a))で

はエ ッジ強度の弱い順 に画素 を走査 し、最初 に見つかった削除可能な画素 を輪郭線画像か ら削除 した後 に再びエ ッジ強度の最 も弱 い画素か ら走査 をや り直す。 これに対 し、淡 らの改良 アルゴリズム (図

4(b))で

は エ ッジ強度をキー とし、削除可能な画素をデータとする平衡木を用いることにより、削除 可能 なエ ッジ強度最弱の画素 を即座 に取 り出せ る工夫がなされている。 なお、削除 して も連結性が保存 されるか どうかは、連結数 (領域の境界線がその画素 を 通過する回数

)に

よ り、機械的に判定可能である [3]。

3.問

題 分 割 と並 列 化 に関 す る基 本 的 考 察 両 アルゴリズムの計算量 については、淡 ら

[3]に

詳 しい考察がある。井上 らのオ リジ ナルのアルゴリズムの計算時間は (粗輪郭の画素数

)×

(削除可能画素の検索 に要す る平 均時間

)に

比例 し、 これは o(粗 輪郭の画素数2)と見つ もることがで きる。 これに対 し、 淡 らによる改良アルゴリズムの計算時間は (粗輪郭の画素数

)×

(平衡木への粗輪郭の境 界画素デー タの挿入

/削

除処理 にかかる平均時間

)に

比例するので、0(粗輪郭の画素数 × log(輪郭長

))と

見つ もることがで きる。 計算量が非線形かつ線形以上のオー ダで増加す るので、分割 によって問題のサ イズが縮 小で きるのであれば逐次処理であって も高速化が実現で きる。それを並列処理すれば飛躍 的に時間短縮で きる可能性 もある。 しか し、残念 なが ら両 アルゴリズムは走査順序が領域

画像の分割・統合による粗輪郭か らの対象物抽出の分割順次処理

(b)淡らの改良アルゴリズム

粗輪郭か らの対象物抽出アルゴリズム (文献 [3] よ り)

図4

Soding of pixels in a lhicf

boundary line area according lo

lheir eQe inlensity.

P[nl:

nt

pixel P[n]-nq, 1 tErdlbud O d.l.tsd thar: rumborolpiEls

′

′ ︶

︲︲

︲一ヽ

︰︲

︲ Ｆ

︲ ︲

︲ヽ ︲

_ヽ︲

PDSSib!e to deletepixel PrnJ? Delelon of PraJ fYnJ.鮨口

=0

Modttcation of赫 (a)井上 らの オ リジナ ルア ル ゴ リズム

Condruction

ol

avalanced tre€ 7 of reruyable phels usinglhe edge

inten$ity asfte key. Here,

mrldD; the pixel

d#

having lhe

minimum key in 7.

DeleOon of mntt fЮm 7_

Reconstructlon of■ making use of heね 耐that only the 8-neighboring ptxels of he deleted

PiXOl may be reded_

まず左 半分

一

一

_{31t 3■■31■}

褒

_{3‐ 3333}

‐

澄」

一

0 13日□13■131‐₃₁₁₃

一

』 塁 d

一

(a)通 常 の逐 次 処 理 人 文 自 然 論 叢

6162

(b)分 害J順次処 理 固定 エ リア

一

図

5

分割順 次処 理 と並 列処理の シ ミュ レー シ ョン (ケー (c)並 列 処 理 ス1) 左右 のエ リア

一

一

一

画像 の分割 ・統 合 に よる粗輪 郭 か らの対象物抽 出の分割順 次処理 固 定 エ リア

￢製

==LttЪ

処理にスイッチ

岸

鶴

(a)通常 の逐次処理 (b)分 割 順 次処 理 図

6

分割順 次処理 と並 列処理 の シ ミュ レー (c)並 列 処 理 シ ョン (ケー ス2) まず左 半分 を処理 1 1

11

,11

中

輔

１ ３ ３ ３ ■ 34

F

一

一

一

―

―

一

一

一

―- 29 -―

人 文 自 然 論 叢 61-62 全体 におけるエ ッジ強度順 と決め られてお り、処理結果はその順序 に依存するため、同一 の結果 を得ねばならない とい う制約の下では基本的に分割順次処理や並列処理はで きない。 試み に、簡単 なモデルケースで分割順次処理 と並列処理 をシミュ レー トしてみた。図5,

6に

その様子 を示す。ケース

1(図 5)は

対象物が両 アルゴリズムの想定 している理想的 な輪郭 を持つ場合、すなわち対象物の輪郭 (粗輪郭ではな く、対象の厳密 な輪郭線

)が

、 輪郭画素のエ ッジ強度

>

その近傍の輪郭以外の画素のエ ッジ強度 とい う条件 を満 た しているケースの一例である。 また、ケース

2(図 6)は

この条件が成 立 しない例である。 両図 とも一番上段 の図が初期状態であ り、太線内が粗輪郭領域 を表す。着色部分が粗輸 郭 として指定 した領域で、その7inさ と数値が各画素のエ ッジ強度 を表す もの とす る。粗輸 郭外の画素 は説明に無関係 なので省略 し自で示 してある。

(a)が

基本 となる逐次処理の結 果、

(b)が

分割順次処理、

(c)が

並列処理 した場合の処理過程である。分割処理 (b,c) の場合 は、左右

2分

割 と仮定 し、分割順次処理

(b)で

は左 の領域 を先 に処理 した後 に右 を処理、並列処理

(c)で

はまず領域 の境界 (中央の ライ ン

)に

位置す る画素 を固定 して 境界上 を除 く左右の領域 をそれぞれ並列 に処理 し、各 々の結果 を合成 した後に境界上の画 素 を処理する もの と仮定 して処理 をシ ミュレー トした。 逐次処理 (a)の場合、初期状態での粗輪郭内の画素中、エ ッジ強度最小で連結性 を損 なわず に削除可能な画素は、両ケースとも右端中央の画素だけである。 まず、最初 にその 画素が削除 され、エ ッジ強度最小で削除可能な画素が順次削除 されてい く。同 じ強度の画 素 が 同時 に削 除可能 であ る場 合 の削 除順序 は任 意 であ る。 オ リジナ ルの ア ルゴ リズ ム

[1]で

は、画像 デー タのスキ ャン順、すなわち下 よ りは上、上下の位置 も同 じな ら右 よ りは左 の画素が優先的に削除 されると考えてよい。 また、改良アルゴリズム

[3]の

場合 は、平衡木に挿入 された順、つ ま り、その画素が削除可能 となった時期の早い順である。 ここでは改良アルゴリズムを前提 として シミュ レー トした。 まず、ケース

1(図 5)で

は、逐次処理、分割順次処理、並列処理の最終的な結果 は一 致 した。 このモデルケースは一例 に過 ぎないので、すべてをこの結果か ら推 し量 ることは 危険であるが、明確 な強い輪郭 を持つ対象物では同様の結果になるであろうことは推測で きる。次にケース

2(図 6)で

は、

3つ

の処理方式の最終結果はすべて異 なる。 この簡単 なシ ミュ レー シ ョン結果か ら分かることが二点ある。 まず一点は、分割順次あるいは並列 処理 した場合、オリジナルの逐次処理の結果 と異なる輪郭線が得 られて しまう場合 もある とい うこと、 もう一点は、逐次処理の結果が必ず しも最 も理想的 とは限 らない とい うこと である。粗輪郭内のエ ッジ強度の強い部分をつ ないだ閉曲線 を得 るとい う本来の意図か ら す ると、図

6(a)よ

りもむ しろ図

6(b)の

方が結果 として望 ましく、 さらに言 えば、 もし

画像の分割 。統合による粗輪郭からの対象物抽出の分割順次処理 人が トレースす るな ら最外殻の画素 をつないだ閉曲線 を輪郭 として選ぶであろ う。 この こ とか らも、全体的処理の結果 を絶対視する必然性 はない ことが わかる。

(b)分

割 しない場合 の抽 出結果

(c)10×

10分 割 ` 図

7

単純 分割 に よる分割順 次処理 の基礎 実験 結 果 (a)対象画像 (粗輪 郭 を重畳 表示 した もの。サ イズ は640× 480)

(c)10×

10分 割 の場合 の抽 出結果

-31-人 文 自 然 論 叢

6162

表

1

単純な分割順次処理結果 とオリジナルの結果との一致度

10

図

8

領域数 と平均再帰段数の関係

4.分

割処理 の基 礎 実 験 画像 を単純 に

N×

Nの

区画に分割 して、左か ら右、上￨から下 という順で、左上の区画 か ら順に区画ごとに淡 らの改良版アルゴリズムを適用 し、対象物抽出を試みた。抽出結果 の例 を図

7に

示す。

(a)が

実験対象画像であり、粗い輪郭線 を重畳表示 してある。 この画 像 を単純に

NXNに

分割 して区画 ごとに輪郭線を決定する。

(b)が

分割 しない場合の抽 出結果、(c)は10×10に分割 した場合の抽出結果 (対象物の含まれる区画 のみ表示

)で

あ る。輪郭位置が分割 しない場合 とどの程度一致するかを表

1に

示す。“領域数

"と

は

N×

Nの

区画のうち粗輪郭領域を含む区画の数である。“不一致画素数

"と

は分割 しない場合 の結果 と一致 しない画素の数である、多 くの場合、ずれは隣接画素への移動であ り目視で 8.5 ５     ７     ５ ７             ６

再

帰

段

数

画面分割数 領域数 不一致画素数 一致度 (%) 2× 2 4 1 99.9% 3× 3 8 47 97.0% 4× 4 12 18 98.9% 5× 5 14 35 97.8% 6× 6 18 50 96.8% 7× 7 26 80 94.9% 8× 8 31 53 96.6% 9× 9 34 126 92.0%

10X10

41 123 92.2% (*オリジナルの細線化輪郭画素数:1569)

画像の分割・統合による粗輪郭か らの対象物抽 出の分割順次処理 は識別 で きない。 大 き く位置ず れ を起 こ してい る箇所 を図

7(c)で

は円で 囲 って示 してあ る。 これ らの部 分 は画像 の分 割線 の格 子 点 が粗 輪 郭 内部 に位 置 した り、 区画 の境 界線 が粗 輪 郭 をス ラ イス するように横切 った りす る場所であることがわか る。ほかの画像 について も実験 したが、 同様であった。 この ような状況 を避けるように分割すれば大 きなずれは発生 しない もの と 予想 される。 先にも述べた ように淡 らの改良アルゴリズム

[3]で

はエ ッジ強度 をキー とす る平衡木 で削除可能 な画素 を管理 してお り、計算時間のほ とん どは平衡木へ のデー タの挿入 と削除 で消費 される。平衡木へのデー タの挿入 と削除は再帰的なプログラム として実装 されてお り、再帰呼出 しの段数 に比例 した処理時間を消費す る。そ こで、領域数 とデー タ挿入 。削 除操作の平均再帰呼出段数 との関係 を調べ てみた。結果 を図

8に

示す。 ちなみ に、デー タ の挿入・削除の総回数は分割数 による大 きな変動 はな く、ほぼ一定 と見 なせ る。 したが っ て、分割順次処理で も計算時間は短縮で きることがわかる。

5.分

割 処 理 の 問 題 点 と対 処 法

5.1

問題点の分析 区画の格子点が粗輪郭内に位置 した り、区画の境界線で粗輪郭がスライス された りす る ときに、分割順次処理で得 られる輪郭位置が変動す る原因について考察す る。前提 として、 分割せず に処理 した場合 に、対象物の輪郭線 は理想的な形で得 られる もの とす る。す なわ ち、結果 として得 られる輪郭線上のすべての画素 に対 し、その近傍 において次の条件が成 立 している もの とす る。 輪郭画素のエ ッジ強度

>

輪郭以外の画素のエ ッジ強度 粗輪郭 は閉曲線状の領域 であるので、

2つ

の領域境界線 を持つ。1つは対象物の外側領 域 との境界線、 もう1つは内側領域 との境界線である。画像 の分割単位が矩形 の区画であ るもの とすれば、粗輪郭は区画 を構成す る

4つ

の辺 によって分断 される。区画の辺 に よっ て粗輪郭か ら切 り取 られた領域が、図

9(a)の

ように

2つ

の断面 を持 ち、その断面が外側 の境界 と内側の境界の橋渡 しとなっているような場合 には、エ ッジ強度の弱い順 に画素 を 取 り除いてい くと、理想的な輪郭位置の画素が残 ることは 自明であ り、分割 しない場合 と 同 じ結果が得 られるはずである。 図

9(b)は

ある区画の右下隅の頂点が右肩上が りの粗輪郭内部 に位置 した場合の処理の 様子 を示 している。区画が左か ら右、上か ら下の順 に順次処理 されてい くもの とす る と、 図の左上の区画 を処理す る段 階ではそれ以外 の区画は固定 されているので、結果的 に左上 ―- 33 -―

人 文 自 然 論 叢 (a)分割が結果 に影響 しない ケース

_区

画 の境 ←

界

_は

M舞

(b)分割が結 果 に悪影響 す るケー ス1 61-62 粗 輪 郭 理想 (c)分割が結果に悪影響するケース 2

鶉 躙 鰺 輻

図

9

分割位置が抽出結果に及ぼす影響 区画内の粗輪郭画素 はすべて除去 されて しまい、理想的な結果 とずれが生 じる。右下以外 の区画の隅が粗輪郭内部 に位置す る場合 も同様である。図

9(c)は

、区画の境界線が粗輪 郭 をス ライスす るように通 る場合である。 この場合 も、(b)と同様、上の区画内の粗輪郭 画素 はすべて除去 されて しまう。

5.2

区画の統合による問題点への対処法 画像 を単純 に等間隔に区画化 した場合、運悪 く上で述べた ような不具合の起 こるケース が発生するのは避 け られない。そ こで、 まず画像 を等間隔の区画に分割 した上で、不具合 が生 じる可能性 のある区画が見つかった場合 には、その区画 と隣接する区画 を統合 して処 理単位 を拡大す ることで、不具合 を回避することにする。区画の統合アルゴリズムを図10 に示す。 図11のモデルケースを例 に統合 アルゴリズムを説明す る。

まず、区画 Alで は、区画の辺が粗輪郭領域を輸切 りにする形で外部から内部へと横切

って通っている。このようなケースでは図

10の

アルゴリズムの☆の終了条件が直ちに成立

画像 の分割・統合 に よる粗 輪 郭 か らの対 象物抽 出の分割順 次処理

記 号 の意 味

1,」:処理 対象 区画の行番号 と列番号(先頭 は 1)

Imax,Jmax:画

像 の分 割 数,縦Imax,横」max

ln:粗

輪 郭 の 内側境界画素 の集合

Out:粗

輪 郭 の外側境界画素 の集合 R:区画統合されてできる拡 大 区画 (矩 形領域)

M:拡

大 区画 Rの 横 区画数と縦 区画 数 の和

x←

min(M-1,」 m ax―

J+1):

]+(y-1)〉 Im ax

R←

区画(1,」)を左上隅として含む、 横

x区

画、縦

y区

画分の矩形領域:

E←

Rの右辺および下辺と粗輪郭領域の 交わ り線 分 の集 合i

Ve∈ E,Pl,P2:eの

端 点, (Pl∈In)∧(P2∈Out)

V(Pl∈ Out)∧

(P2∈In) Rを出力して終了 〉(lm ax-1)+(」 m ax―J)+2 例 外 として終 了 (粗輪郭 が画像領域外 に はみ 出てい た場合 等) 図

10

区画統 合 アル ゴ リズム ―- 35 -―

人 文 自 然 論 叢

6162

Al A2 Bl 図

11

区画統合の様子 す るので、区画統合 は発生 しない。区画 Blも 同様である。区画A2は区画の隅が粗輪郭内 部 に位 置す るケースである。 このケースでは☆ の条件が満 た されず、② のステ ップで

M

が インクリメ ン トされて、

M=3と

して① に戻 る。変数

Mは

統合 される区画の縦 と横 の 区画数の和 を表 し、最初 は

2(統

合 な し

)に

セ ッ トされている。統合が必要 な場合 は、

M

の値 は

1ず

つ イ ンク リメ ン トされてい く。

M=3を

満 たす区画の統合 の仕方 は、縦

1横

2か

縦

2横 1か

の二通 りであ り、 この順 に統合が試み られる。結果 として、区画A2は下 の区画 B2と 統合 されてアルゴリズムは終了す る。区画A3は

2区

画の統合では☆の条件 は 満 た されないので、

M=4と

な り、横

3縦

1、 _横

2縦

2、 横

1縦 3の

区画統合が順 に試 み られる。その結果、A3は A4.B3.B4と 統合 される。 対象画像

表

2

単純 分割 と区画統合 を行 う場合 との不一致画素 数 の比較 画面分割 数 単純分割 の場合 区画統合 を行 った場合 領域数 不一致画素 数 領域 数 不一致 画素 数 2× 2 4 1 4 2 3× 3 8 6 1 4× 4 0 1 5× 5 1 1 6× 6 18 50 5 4 7× 7 26 80 7 10 8× 8 20 9× 9 126 48 10×10 41 26 0 (*オ リジナ ルの細 線化輪 郭画素 数 :1569) 画像の分割・統合による粗輪郭か らの対象物抽出の分割順次処理 図

12

区画統合の結果

5.3

実験結果 区画の分割 。統合 アルゴリズムをインプ リメ ン トし、領域抽出実験 を試みた。表

1の

基 礎実験 と比較す るために、図

7(a)を

対象画像、初期分割 を 2×

2∼

10×10と し、単純分 割の場合 と区画統合 を行 った場合 について実験 した。各ケースの領域数 と不一致画素数 を 表

2に

示す。 “不一致画素数

"は

、分割 しないで処理 した場合の抽 出結果 と一致 しない輪 郭画素の数である。区画統合 を行 った場合の方が、単純分割 と比べて不一致画素数が大幅 に減少 していることがわかる。 初期分割 を10×10,40× 30と して区画統合 した結果 を図12に示す。左が10×10、 右が40 ×30の結果である。た またまではあるが、10×10分割の場合、分割 しないで処理 した結果 との不一致はな く、 まった く同一の抽 出結果が得 られた。40×30分 割の場合、不一致画素 数は、統合 な しでは417で あったが、統合あ りでは86と大 きく改善 された。 区画統合 アルゴリズムでは必要 に応 じて区画のサ イズが決 まるので、初期分割数 はい く ら大 きくて もよ く、初期分割の区画幅が粗輪郭の幅 よ り少 し大 きくなる ぐらいに設定 して おけばよい。副次的ではあるが これは区画統合 の長所である。単純分割の場合、分割数 を ―- 37 -―

人 文 自 然 論 叢

6162

決 め る 目安 が ない。分割 数が大 き くなればなるほ ど、 区画の粗輪郭上 に格子点が存在 す る 確 率 は高 くな り、全 体 的処 理 の結 果 と多 くの不一致箇所 が生 じる し、運が悪 ければ小 さい 粗 輪 郭 の分割結果 分割順次処理での抽出結果 基準 となる抽出結果(非分割)

17/1536

不一致

/輪

郭長 目視で分かる不一致箇所

43/1283

38/1208

72/2677

図

13

区画統合後 の粗 輪郭の分割結果 と対象物抽 出結 果

画像の分割・統合による粗輪郭か らの対象物抽 出の分割順次処理 分割数で あ って も生 じる。 なお、図12で区画の格子点が粗輪郭内部 に位置 しているように見 える箇所があるが、実 際の区画統合 は区画 ごとに細線化 を施 しなが ら順次実行 してい くので、格子点が初期状態 の粗輪郭内に位置 していて も、その区画が処理 される時点では内部点ではな くなっている ためである。 ほかの画像 について も比較実験 を試み、良好 な結果が得 られることを確認 した。結果 の 一部を図13に示す。左端の列 は抽出対象画像 に粗輪郭 と分割線 を重畳表示 した画像、 中央 の列が分割順次処理の抽出結果、右の列 は比較対象 となる分割せず に処理 した場合の抽 出 結果である。図中に示 された数字 は、「不一致画素数

/抽

出対象物 の輪郭画素数」 であ る。 上

3つ

の画像 は512×512ピクセルで、初期分割が16×16、 一番下の画像 は1024× 1024ピ ク セルで初期分割 は32×32である。分割順次処理の結果 と比較対象の結果 は、注意深 く観察 しない とほ とん ど違いが分か らない。判別可能な不一致箇所 を丸で示 した。 以上の結果によ り、粗輪郭か らの対象物輪郭線抽 出処理 は、分割方法 を工夫すれば分割 順次処理可能であることが検証で きた。

6.む

すび

粗輪郭か らの対象物抽 出手法の空間的な問題分割の可能性 について検討 した。今 回議論 の対象 とした手法では、抽 出結果 は画素の処理順序 に依存 して変化す るはずであ り、その 順序が画像全体の画素 に対 して定義 されているため、理屈の上では、分割処理す る と得 ら れる結果 は違 って くることがある。実際、基礎実験 として行 った単純 な分割では、部分領 域の境界付近で、得 られる輪郭に大 きなひずみが認め られた。本稿 ではその不具合 を極力 抑 えることので きる、画像の分割・統合法 を提案 し、実験 的にその有効性が検証で きた。 今後の課題 としては、 まず、並列処理の可能性 の検討が挙げ られる。今回行 った実験 は分 割順次処理であ り、それだけで も計算時間の短縮 につ なが るはずであるが、並列処理がで きればさらに時間短縮が期待で きる。 また、粗輪郭 を用いる他のアイデア として、 スネー クによる輪郭線抽 出手法 (エッジ強度に比例 した引力場 を仮定 して環状 に配置 した点列 を 輪郭部分 に吸着 させ る手法

)[5]を

粗輪郭内に限定 して動作 させ る とい う方法 を考 えて お り、その実装 と今回の結果 との比較 も行いたい。 参 考 文 献

[1]井

上誠喜:“画像 合成 のための対象物 の抽 出法

",信

学論 (D―II),Vol.J74_DII, No 10,pp 1411_1418(1991).

[2]井

上 誠喜_,小山広 毅:“動 画 像合 成 の ための対 象物 の抽 出 とはめ込み法",テ レビジ ョ ―- 39 -―

[3]

[4]

[5]

人 文 自 然 論 叢 61-62 ン学会誌 ,Vol.47,No.7,pp.999-1005(1993). 淡 誠 一 郎,鄭小 江,北橋 忠 宏 :“対 話 型 対 象 物 抽 出 アル ゴ リズ ムの高速化

",信

学 論 (D―Ⅱ),Vol.J79‐DⅡ , No.11, pp.1984-1987(1996). 淡 誠 一郎:“粗 輪 郭 か らの対象物 抽 出 アル ゴ リズムの並列化 につ いて

",第

56回 情 報 処 理 学 会全 国大 会,3P‐04,論文 集分冊2,pp.133-134(1998).

Kass,M.,Witkin,A.,Terzopoulos,D.: “_{Snake:Active Contour Models",International} Journal of Computer Vision,pp.321-331(1988).