評価実験

X 

X 

(a) original image 

X 

T  (b) an example of distorted 

image with binary noise 

刈 5.3:テスト画像

表 5.2:検出が成功した画像数(解析率) テスト画イ象 ビームサイズ R

10  20  50  100  200  250  2値雑音 (b) 100  100  100  100  100  100  256階調雑音 (c)

。

48  84  99  100 

はB=Oとした.テスト画像として，濃度値一定 (255)の軌跡、を含む図 5.3(札)の画 像に 2値 (0，255)の雑音を重畳した画像(以下， 2値雑音画像)と， 256階調の雑音を 重畳した画像(以下，多値雑音画像)の 2種類をそれぞれ100枚ずつ使用した.テス

ト画像の例を図 5.3(b)，(c)に示す.モデルには表5.1，図 5.1に示した台形波の CFG モデルを使用した.ここでは 軌 跡 の 最 大 傾 斜 を マ =1とした.

ビーム幅 Rが小さすぎる場合，解析テーブルの (0，T)に開始記号Sが生成され ず，軌跡の検出に失敗する場合が生じる.そこで，開始記号Sで表される軌跡が検 出できた画像の割合を解析率と定義し，それぞれの画像に対する解析率と Rの関係 を調べた.結果を表5.2に示す.

2値雑音画像と多値雑音画像とに対するビームサーチの効果をそれぞれ図5.4， I災

5.5に示す.図の横軸はビーム幅Rである.グラフ右端の R =∞ は ビームサーチ を用いない場合に相当する.縦軸には平均検出率と平均実行時間 解析テーブル上 に格納される平均要素数を示しである.この平均要素数にほぼ比例する量が必要な 記憶量となる.また，検出に失敗した場合の検出率は

0%

として，平均検出率を計算

した.

ビームサーチを用いない場合

( R

=∞)の平均実行時間は，どちらの画像でも約 2.2 X 10⁴秒 で あ っ た.2値雑音画像に対しては 検出率の劣化のない

R

= 10で 平均実行時聞が約 0.3秒であり ビームサーチを用いない場合に比して約5桁の高 速化となった.多値雑音画像に対しては，検出率の劣化のない R

= 

250で平均実 行時間が約 12秒であり ビームサーチを用いない場合に比して約 3桁の高速化と

なった.

一方，解析テーブル上に格納される平 均 要 素 数 (以下， 平均要素数)は，ビーム サーチを用いない場合，どちらの画像でも約1.2X 10⁶であった.2値雑音画像に対 しては， 平均要素数は約.J.5x 10:³ 

( R 

= 10)，多値雑音画像に対しては，平均要素 数は約 5.1X 10.¹ (R 

= 

250)となり，ビームサーチを用いない場合に比して，約2‑‑‑‑‑

3桁 の 効率化を得た.

以上の結果から，ビームサーチによる大幅な計算量の低減が可能であることが確 認できた.

5 . 6 . 3   R G モデルとの比較

図5.6(a)の3種類のテスト画像(サイズ :̲¥"" 

= 

64， T 

= 

128)を用いて， 第3章の RGモデルを用いる手法に対する検出能力の比較実 験を行った.Irn勾c1， Inlagc2に は一様分布に従う雑音を重畳し， Imagc3には濃度値一定の変調波を重畳した.

これらのテスト画像に対する検出軌跡を図 5.6に示す.(b)は本章で提案したア ルゴリズムによる検出軌跡である.モデルには 5.6.2節と同様の CFGモデルを使 用した.ただし軌跡の最大傾斜はマ =2とした.(c)は第3章のアルゴリズムによる 検出軌跡である.モデルには， (ど♂b*cホ)*という記号列を生成する RGモデルを使 用した.各記号は，表5.1の記号と同様である.検 出 率 (TR)，平均 2乗誤差 (NISE)

を各検出結果の下に示す.

図 5.6(b)の検出に要した実行時間は， Image1， Image2， Image3に対して，そ れぞれ5.1X 10²秒 (R二 30，8二 100)，1.1 X 10⁴秒 (R= 50，8 = 100)， 5.4 X 10²秒

(R = 10， 8 = 200)となった.括 弧 内 に 示 し た ビ ー ム サ ー チ の パ ラ メ ー タ は予備実 験によって決定した.第3章のアルゴリズムを用いて図 5.6(c)の検出に要した実行 時間は， Image 1，2，3とも約 7秒であった.

RGモデルを用いた (c)の結果では，雑音の影響が顕著であるのに比べ， CFGモ デルを用いた (b)の結果では，より高精度に軌跡が検出されていることがわかる.こ れは， RGよりも高度な記述能力を持つ CFGを用いたことで，軌跡の検出能力が両 くなったことを示している.以上により，本章 で提案した CFGモデルに基づく手

ω一 心 何 日 ︒ c一ω﹂出斗Vム﹀

O

C一

の で

ω E

ω 一ω﹄O﹂

ω2

E コ

c a

ω]

ωE

ZC

OZ

S コ 己

E0

ロ

0

10⁷ 

10³  10⁵ 

10 

0.1 

C幻

1000  100 

beam s i z e  R 

図 5.4: 2値 雑音を重 畳したテスト 画 像(b)に 対 す る ビ ー ム サ ー チ の 効 果

ω一D

a g

o c

一ω﹂国己﹀‑﹀

O

C一

E C

ω ε

ω 一ω﹄O﹂

ωD

E コ

C A U

{ ω

} ω

E Z

C O

一 芯 日 コ 己 E

00

口

10⁷  10⁵ 

10³  10  100 

0.1 

C幻

1000  0  100 

10 

beam s i z e  R 

図 5.5:256階 調 雑 音 を 重畳 したテスト画 像 (c)に 対 す る ビ ー ム サ ー チ の 効 果

X 

Image 3 

4E︐ .  

1 x  

TR: 84.0%， MSE: 0.052 

x 

~ ~

r、、 f 、 ， " ..、

J， 、 ど ，、 . ・ 、 .，  、ー プ 、 ̲ ' 、F 、司J

‑ ^~ ー

x 

X 

(a) input  Images 

(b) detected  trajectories  with CFG 

TR: 80.1 %，  MSE: 0.11 

X 

Y ︑︑

ハ

/ノノ

︑︑ ︑

ん

¥ ︑

A

一

︐ ︐ 

TR: 95.7%， MSE: 0.026 

X 

(c) detected  trajectories 

with RG  ~/戸-..._"，../ヘ"，"，~/"--'.__.l t 

TR: 71.9%， MSE: 0.12  TR: 61.3%， MSE: 0.17 

テスト画像と検出軌跡

TR: 94.1 %，  MSE: 0.033 

図 5.6

できた.

台形波近似したモデルを用い 第3章での実験との比較のため，

本章の実験では，

正弦曲線をより厳密にモデ 3.6.2節でも触れたように，

て正弦曲線の検出を行った.

ヲ‑

'‑ー

振幅や周期といった軌跡、の特徴をモデル化する必要がある.

ル化するためには，

局所的な振舞いにより定義づけ れらを多元信号軌跡、のモデルに組み込むためには，

振 rp~ や周期のパラメータを制御するための情報を組

られた多元基本動作に対して，

み込む必要がある.

5 . 7   まとめ

CYK法に基 文脈自由文法で記述される軌跡群の検出法を検討した.

本章では，

ビームサーチによる高速化を検討した.

づく検出アルゴリズムを提案し，

正規文法モデルを用いる第 3章の手法と 正弦曲線を対象とした比較実験を行い，

る計算量の低減効果を実験的に検討し，約2‑‑‑3桁の計算量の低減が可能であること を確認した.

立 早

6

諮 問

第 結

本研究は，雑音画像中に含まれる軌跡群を高精度に検出する構文解析型アルゴリ ズムを検討したものである.

軌跡群を検出するために従来試みられた方法は 単独の軌跡検出処理を単純に 繰り返すものであり，処理が個々の軌跡ごとに行われるものであった.これに対し，

本研究では，従来用いられていた個々の軌跡に関する事前知識だけでなく軌跡問に 存在する相互的知識をも利用可能とし かっ局所解を避けるため軌跡群全体として の最適解を得る枠組みを提案し その有効性を検討した.

本研究の内容は大別して次の3部よりなる.

(1)正規文法による軌跡群モデル記述と動的計画法に基づく解析アルゴリズムの 提 案

(2)軌跡、聞に遅延が存在する場合への解析アルゴリズムの拡張 (3)文脈自由文法モデルと CYE型解析アルゴリズムへの高度化

加えて，これらの各部においてビームサーチの導入による高速化改良と，実験的評 価が含まれる.

以下に各章で述べたことを要約して本論文のまとめとし 最後に今後の課題につ いて検討する.

第1章では，本研究の背景と位置付け，その概要について述べた.

第2章では，以下の章への準備として，本論文で対象とする多元信号軌跡の定義 と，そのモデル化について説明した多元信号軌跡をモデル化するために，イ同々の軌 跡の局所的な振舞いと軌跡相互間の関係の組合せを用いて終端記号を定義し，多7じ

信号軌跡の全体的な構造を書換え規則によりモデル化する方法を示した.

第3章では，正規文法で記述される軌跡群を検出するアルゴリズムを提案した.

このアルゴリズムは，多元信号軌跡に関するモデルを正規文法と等価な有限状態オー トマトンで記述し， モデルに最もよく一致する軌跡群を動的計画法により検出す るものである.正弦曲線および方形波を対象とした検出実験を行い，モデルに従う 軌跡を追跡することにより，雑音に対してロバストな解析が可能になることを示し，

アルゴリズムの有効性を確認した.ビームサーチを導入することにより，約 1‑‑2桁 の計算量の低減を実現した.また 3元以上の軌跡を検出するアルゴリズムへと一般 化し，分岐，合流を含む 3元以上の軌跡群が検出可能なことを確認した.

第4章では，第3章のアルゴリズムを拡張した，未知の遅延を伴う軌跡群の検出 アルゴリズムを提案した.このアルゴリズムは 零遅延状態での個々の軌跡の振舞 いと軌跡聞の相互関係とを用いて，軌跡群を正規文法によりモデル化し，遅延量を 取適化パラメータ に含めた探索問題を動的計画法により計算し モデルに最もよく

致する軌跡群を検出するものである.正弦曲線を対象とした検出実験を行い，提 案したアルゴリズムによって遅延を伴う軌跡群を検出できることを確認し，ビーム サーチの導入により約 1‑‑2桁の高速化を実現した.さらに，遅延を伴う方形波を対 象として，第 3章のアルゴリズムとの比較実験を行い，本章で提案したアルゴリズ

ムによってより高精度な検出が可能になることを示した.

第5章では，文脈自由文法で記述される，より複雑な軌跡群の検出法を検討した.

CYK法に基づく検出アルゴリズムを提案し ビームサーチの導入による計算量の効 半化を検討した.正弦曲線を対象として，正規文法モデルを用いる第 3章の手法と

の比較実験を行い，文脈自由文法モデルを用いる手法が，より高精度な軌跡検出の 能力を有することを確認した.またビームサーチによる計算量の低減効果を実験的

に検討し，約 2‑‑3桁の計算量の効率化が可能であることを示した.

今後の検討課題としては，本論文で提案したアルゴリズムの実画像への適用が挙 げられる.実画像に適用する場合，対象に応じた基本動作の追加/拡張が必要になっ

てくると考えられる.特に，平滑性を考慮した軌跡検出法へ拡張することは検出精 度を高める上で有効であると予想、される.また，本論文では文脈自由文法までを対 象としたが，より複雑なパターンの記述のためには，上位の文法への拡張が必要と

なると考えられる.さらに モデルの設計に関して，最適なモデルの決定法やモデ ル記述のためのユーザインタフェイスの実装などが検討課題として残されている.

本研究の拡張としては，動画像中からの軌跡の検出が考えられる.具体的には，

動画像中の物体追跡や医用動画像からの生体臓器の輪郭線の追跡，ジェスチャ認識 がある.本研究で提案した多元信号軌跡解析アルゴリズムを，これらの動画像に適 用するためには， 3次元における多元基本動作の定義を検討する必要がある.

謝辞

九州大学迫江博昭教授には 本研究の機会を頂き 九州大学大学院修士課程・博 士後期課程を通じて，長期にわたり多大なる御指導 ・御鞭捷を賜わった.ここに謹 んで感謝の意を表します.

本論文をまとめるにあたり有益な御助言を賜わった長谷川勉教授 谷口倫一郎教 授に深く感謝致します.

鎌田清一郎助教授，片山喜規助手 内田誠一助手には 研究に関する有益な御不 唆を頂いた.また研究環境の整備など多くの御支援を頂いた.ここに深く感謝致し ます.迫 江 ・鎌田研究室の諸氏には 研究生活を公私ともに支えて頂いた.ここに 御礼を申し上げます.

最後に，研究生活を精神的 ・経済的に支えてくれた両親に深く感謝します.

ドキュメント内 九州大学学術情報リポジトリ (ページ 83-101)