九州大学学術情報リポジトリ

(1)

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

雑音画像中の軌跡群を検出する構文解析型アルゴリズムに関する研究

高橋, 伸弥

九州大学システム情報知能システム工学

https://doi.org/10.11501/3166853

(2)

(3)

雑音画像中の軌跡群を検出する構文解析型アルゴリズムに関する研究

高橋伸弥

2000年 2

月

(4)

，

5i

r-~

，)/

ハU

つん

vh

υ

︒ ︒

ハハ

U

ハハ

UハhUハハU

5 文脈自由文法モデルを用いた多元信号軌跡の解析 5.1 まえがき.

5.2 文脈自由文法によるモデル化

5.3 CYK法に基づいた解析アルゴリズム 5.3.1 問題の設定

5.3.2 解析テーブル

5.3.3 解析アルゴリズム.

5.4 ビームサーチによる効率化 .

5.4.1 アルゴリズムの計算量と効率化 5.4.2 ビームサーチを導入したアルゴリズム 5.5 .J元信号軌跡検出への一般化

5.6 評価実験

5.6.1 実験の概要

5.6.2 ビームサーチの効果 5.6.3 RGモデルとの比較 . 5.7 まとめ

9 9 9

PO

ハハ

UハハU

1 i 1

ょっムつ

d1吐144﹁ο

円 ︒

{ i

‑ i F i

‑ i

戸i戸i戸iケi

11 11 1

，

79 81

6 結論 83

参考文献 86

A 多元信号軌跡解析システムの実装 90

(7)

第 1章序論

1 . 1 研究の背景

画像からの軌跡の検出はパターン認識/理解のための基本的かっ重要な問題の一つである.近年の計算機利用の急速な拡大に伴い，医用画像処理や図面の自動認識など多くの分野で軌跡の自動検出の高精度化の要求が高まっている.

軌跡を自動検出する方法としては濃度値の最大点を連ねるというのが最も簡単な方法であるが重畳雑音のレベルが高くなると検出性能が急速に低下する.そこで，検出しようとする軌跡の構造に関する知識を用いたモデルを用意し，モデルに一致する軌跡を追跡しようとする方法がとられる.最も単純な例としては，軌跡の連続性や平滑性を利用して検出を行う方法がある.また，対象軌跡、の構造に関する先験的な知識を積極的に利用する方法として構造解析的パターン認識と呼ばれる方法が検討され，システマティックな扱いを容易にするために，文一句‑単語という階層構造を持つ形式文法でモデルを記述し，その構文解析手法を応用して検出する方法が提案されている [1

， ]

[2

， ]

[3].

連続性を用いて軌跡検出を行った例としては， Ncyの行った，

x

^{線写真からの}

機械部品の輪郭線の検出[4]がある.そこでは，画像中の軌跡、探索を最適経路問題と見なし，動的計画法を用いて大局的な最適解を探索することにより，軌跡を検出し

ている.また， Neyは同じ枠組みで，連続性および平滑性を利用した音声ノてラメータ軌跡の検出 [5]も検討している.構文解析的な手法を用いて軌跡検出を行った例としては， Bnnkeらによる，雑音画像中からの正弦曲線の検出が挙げられる [6].そこでは，対象信号の性質を文脈自由文法で記述し解析するという方法を提案しており，

重畳雑音に対してロバストな検出が可能なことを示している.

これらの軌跡検出法の拡張の一方向として，複数軌跡すなわち軌跡群の検出問題

(8)

がある .Kopec [T]はサウンドスペクトログラム中の 3本のホルマント軌跡を動的計画法に基づく軌跡検出アルゴリズムの繰り返し適用で検出している.佐藤ら

[ 8 ]

は心臓エコー画像中の心臓運動軌跡をやはり軌跡検出処理の繰り返し適用で検出している.これらの試みでモデルに利用している事前知識は連続性とか，平滑性といった，個々の軌跡の性質に留まっている.また，処理が個々の軌跡ごとに行われるため，局所的な最適解を求めることになり，大局的な最適解とはいえない軌跡を検出する場合があると予測される.

本研究はこのような問題意識に立ったもので，個々の軌跡、に関する事前知識に加えて軌跡、聞に存在する相互的知識の利用を可能とし，かつ局所解を避けるため軌跡群全体としての最適解を得る枠組みを提案し，その有効性を検討したものである.

1 . 2 研究の概要

本研究は，個々の軌跡の振舞いと軌跡相互間の関係とを考慮したモデルを用いて，軌跡群を高精度に検出することを目的としたものである.本研究で対象とする軌跡、は，時間あるいはそれに代わるインデックスで順序付けられた連続な時間関数信号である.画像中に想定した時間軸上に複数の信号が存在する場合，この信号を軌跡群あるいは多元信号軌跡、と総称する.後者は本数を意識する場合に用い，具体的には 2元信号軌跡 k元信号軌跡、等の表現を用いる. 1本の軌跡は単元信号軌跡

と呼ぶ.

多元信号軌跡を検出するために，個々の軌跡の振舞いと軌跡相互間の関係に関するモデルを形式文法で与え，モデルが生成する軌跡(群)と入力多値画像との間で京大一致をとる形で解析を行う.解析の結果として，検出された軌跡(群)とそれらの各部に対する解釈(ラベル付け)及び一致の度合の評価値を得る.

本研究は大別して 3部より成る.(1)まず，正規文法モデルで生成される軌跡群と最もよく一致する軌跡群を動的計画法により探索するアルゴリズムを提案した.

さらに計算量の低減のためにビームサーチを導入した.テスト画像を対象とした芙験を行い，高精度な軌跡、の検出が可能なことを示した.(2)次に，上記の正規文法モ

(9)

デルを片jし、た軌跡検山アルゴリズムを未知lの遅延を伴う軌跡群を検出する場合へと拡張し，テスト画像を対象とした実験によりアルゴリズムの布効性を示した.(3) 最後に，より複雑な形状の軌跡群を表現するためにモデルを文脈白白文法にレベ

ルアップし， CYE法に基づいた軌跡群の検出アルゴリズムを提案した.テスト jDij

i

象を対象として，正規文法モデルを用いたアルゴリズムとの比較実験を行い，検山手!?

度に関する相対的優位性を示した.

1 . 3 論文の構成

本論文は，以下のように構成される.

第2章は，以下の章への準備を行ったものである.本論文で検出対象とする多冗信号軌跡の定義とそのモデル化について述べいくつかの例を示している.

第3章では，正規文法で記述される軌跡群を検出するためのアルゴリズムを提案している.このアルゴリズムでは，個々の軌跡、の振舞いと軌跡聞の相互関係とに関するモデルを正規文法で記述し動的計画法を用いてモデルに最もよく一致する軌跡群を検出する.さらにビームサーチを導入して計算量の低減をはかる.正弦山線および方形波を対象とした検出実験を行いアルゴリズムの有効性を示している.

第4章では，第3章のアルゴリズムを拡張した，未知の遅延を伴う軌跡群の検出アルゴリズムを提案している.このアルゴリズムでは遅延のない状態での各軌跡の振舞いと軌跡聞の相互関係とに関するモデルを用意し遅延量を最適化パラメータに含めた探索問題を動的計画法を用いて計算することによりモデルに最もよく一致する軌跡群を検出する.正弦曲線を対象とした検出実験を行い，遅延を伴う軌

跡群が検出可能なことを確認している.さらに，方形波を対象として，第3章の子法との比較実験を行い，提案したアルゴリズムが検出精度に関する相対的優位性を持つことを示している.

第 5章では，文脈自由文法で記述される軌跡群の検出法を検討している.CYI¥: 法に基づく検出アルゴリズムを提案しビームサーチによる高速化を検討する.正弦曲線を対象として正規文法モデルを用いる第3章の手法との比較実験を行い，よ

(10)

り高精度な軌跡、検出が可能なことを確認している.

最後に第6章で，論文のまとめと今後の課題について述べる.

(11)

第 2 章

多元信号軌跡とそのモデル化

2 . 1 まえがき

本章では，本論文で検出対象とする多元信号軌跡の定義と，そのモデル化について述べ，いくつかの例を示す.

従来の研究では複数の軌跡を対象とする場合でも個々の軌跡に関する知識に基づいたモデルを使用して軌跡を検出しており，多元信号軌跡であることはほとんど意識していない任1 多元信号の場合，軌跡、群全体の性質をモデルとして与えることで，より高精度な軌跡、群の検出が可能になると考えられる.本章では，この考えに基き，個々の軌跡の性質に加え軌跡、相互間の性質をも考慮して，形式文法により軌跡群をモデル化する方法を検討'する.

2 . 2 多元信号軌跡の定義

図2.1に本研究で対象とする多元信号軌跡の例を示す.この例は人工的に 2本の正弦曲線を生成して雑音を重畳したもので， Bunke [6]が用いた例を 2元信号軌跡に拡張したものである.本論文では，図 2.1のように時間軸t(t = _{1 ，・・} _• ，T)と1次元の空間座標軸 ;l(17二 1，・・.， ̲>:)を想定したディジタル画像

A=

α(:r，

t )

(2.1 )

を扱うこととする.α(:r，t)は時刻 t，位置 zにおける濃度値である.この画像中に含まれる k本の軌跡

x ( t ) = ( : r 1 ( t)

，:r2(t)，・・，:l:A:

( t ) )

が求める軌跡群である注2 以

t王I本研究のように軌跡聞の関係を考慮、して軌跡、を同時検出するアイデアとしては， :MontanarIらの文献[9]に平行な 2本の軌跡の検出について触れられているが，具体的な検討はされていな v) ̲

(12)

χ

T

図 2.1:多元信号軌跡の例

の例のように，

2

次元図形であって，

(1)いずれかの方向に時間軸tが展開できる

(2) 時間軸に直交するような:r軸をとり，位置(い:え:7.:む:，刈)でのt j濃農度値^σ^α^'，(川え^:⁷⁷^. れる

(3) 濃度の高い画素の連続(軌跡)として時間信号

x ( t )

が含まれている

という条件を満たす画像を対象とする .以下では，説明の簡単化のため，:fi(t) _~

:l:i+ 1 (t)とする.また，上記のような画像中に軌跡として含まれる信号を信号軌跡と呼び¥信号が複数ありうることを明示する場合，

I

^{多元」を付ける.}

2.3 信号軌跡の種々の性質

信号軌跡には，連続性，平滑性などのように比較的，一般的で低レベルなものから，例えば正弦波形，三角波形， U"字形，更にはい最初は 1時刻

3

点の勾配でずち上がり，その後は平坦で……"といった対象の具体的形状を示す高レベルなものまで種々の性質を考えることができる.多元となった場合にはこれに加えて信号軌跡相互間の性質を考える必要が生じる.その場合も 2本の軌跡、はほぼ平行， 2

(13)

本の軌跡が徐々に接近する"， 2本の軌跡、が合流する"といった 2本の軌跡のある時刻での関係を示す低レベルのものから， 2本の軌跡は，一貫して軸対象で，最初平行で，ついで徐々に離れ，その後平行かつ水平に推移し，最後は時間軸に対して垂直な軌跡で合流する"というような具体的な一個の物を記述するレベルまで考えられる.

本研究では，以上のような信号軌跡の種々の性質に対して，軌跡群の低レベルな性質すなわち最も基本的な構成要素である画素の動作を終端記号として定義し，具体的形状を示すような高レベルな性質を形式文法の書換え規則によって記述するこ

とを考える.

以下，本論文では，多元信号軌跡の局所的な振舞いを多元基本動作と呼ぶことにする.軌跡の本数

( k )

を明示する場合には，

k

元基本動作と呼ぶ.特に単元信号軌跡の場合には単元基本動作と呼ぶ.

2.4 構造記述文法

軌跡群の構造は，表2.1で定義される形式文法を用いてモデル化される.ここで，

開始記号 Sはt= 1から t=

T

に至る軌跡群の全体構造に対応し，非終端記号は凹像中の時間的部分構造に対応する.終端記号は多元基本動作の制約条件を満たす画素の動作に対応する.以下，立体の英大文字(例えば

A

，

B

，

C

など)で非終端記号，

立体の英小文字(例えば州入cなど)で終端記号，ギリシャ小文字(例えばα

， s ，

γなど)で長さ O以上の記号列を表すものとする.ここで，記号列の長さとは記号列中に含まれる記号の個数を示す.以下では，終端記号aがη個連続した記号列を aの n連接と呼び，どと表す (η:自然数).また任意個数の連接はどと表す.

形式文法は，書換え規則の性質から， (1)正規文法， (2)文脈自由文法， (3)文脈依存文法， (4)句構造文法の4種に分類される.本論文では，まず第3章で，最も某本となる正規文法モデルを用いた多元信号軌跡の検出アルゴリズムを検討し，第 5 章で文脈自由文法へと拡張する.正規文法および文脈自由文法の書換え規則は次の

(14)

表 2.1:形式文法の定義

G

=

( 1

公，1‑今，

P

，

S )

1!~v 非終端記号(英大文字)の集合時 : 終端記号(英小文字)の集合

p : 書換え規則(0'→グ)の集合 S : 開始記号 Sε VN

(1) 正規文法 A → aB または A → a (2) 文脈自由文法 A→

P

これらの文法により生成された記号列はそれぞれ正規言語文脈自由言語と呼ばれる.文脈白白文法は正規文法と比較してより高度な言語記述能力を持つ.例えば，記号列 anb'''は正規文法では記述不可能だが文脈自由文法では記述可能である.使用する文法の記述能力が高いほど厳密なモデル化が可能となる.

2 . 5 多元基本動作の定義

多元信号軌跡、をモデル化するために，まずモデル文法の終端記号に対応する多元基本動作を定義する.多元基本動作は，多元信号軌跡としての軌跡群の局所的性質を表すものであり，個々の軌跡の振舞いと軌跡、相互間の関係とよりなる.前者を個別基本動作，後者を相互基本動作と呼ぶ.個別および相互基本動作としては種々考えられるが，ここでは基本的なものだけを用意し，必要に応じて追加していく方針をとる.

(15)

2 . 5 . 1 個別基本動作

まず個々の軌跡の局所的な動作を表す個別基本動作を定義する.表 2.2に，基本セットとして用意した個別基本動作を示す.表中の制約条件が軌跡の局所的振荒いを示し，隣接する時刻の :7・座標ド =.r(t)とU二

r (

t ‑1)の問の関係を与える.各個別基本動作を図2.2に示す.ここで，図中の実線矢印は，各個別基本動作の制約条件を満たすよつな， 1時刻前の座標からの遷移を示している.本論文では連続な軌跡を扱っているので，①の九(連続)はデフォルトと考えるべきである.¥7は検出対象とする軌跡、の最大傾斜である.これを超える傾斜の軌跡は垂直とみなして，⑥

③で処理する.

2 . 5 . 2 相互基本動作

次に 2本の軌跡間の関係を表す相互基本動作を定義する.表2.3に，基本セットとして用意した相互基本動作を示す.表中の制約条件は隣接する時刻における ::t 座標:t:1二木1( t ) ， ;7.: 2 = ;7.: 2 ( t )とYl二 : r1 (t ‑

1 )

， Y2 = :r 2 (t ‑

1 )

との間の関係を与える. 表に示した相互基本動作のうち，① ⑤を図 2.3に示す.

2 . 5 . 3 3 本以上の軌跡の相互基本動作

3本以上の軌跡群に対しては，隣りあう 2本の軌跡問の相互基本動作の組合せによって記述することとする.ここでは，隣接する軌跡聞にのみ相互基本動作を指定することとし，

k

本の軌跡に対して，

k ‑

1組の相互基本動作を指定する.例えば， :7̲: 1 ( t ) ， :1: 2 ( t ) ) :f 3 ( t )の3本の軌跡に対しては，ぇ:1 (t)と:f2(t)の問の相互基本動作と， :f2 (t)と勺(t)の問の相互基本動作を指定し， :7: 1 (t)と:r3(t)の間の相互基本動作を省略する.

(16)

表 2.2:個別基本動作の例

個別基本動作制約条件(マ三 0)

① ^F、~ ^{連続} ^.¹・‑守三 .lJ三lキ勺

② 水平

③ ¹・/ 単調増加 rーマ三 .1/く .1

④ ^I^"^"^'^‑^.^̲ ^{単調減少} ¹^:

<

^!^J~ ./" +マ

⑤ ^"^/^ノ(0) 勾配指定 (れ:勾配)

⑤ 垂直グく./"‑ ¥7 01" 1/

> . " /

+マ

⑦ 垂直(上向き) グく 1'‑ ¥7

③ 垂直(下向き) y

>

./"+マ

tj1 y=x+2 y=x+1

y=x u

・ ‑

^xl ^y=x^U ¹

・

^{x l} ^{.、与・・・杢}^{. x}

y=x・1 y=x・2

① 連続 ② 水平

浮

④ 単調減少 ⑤ 勾配指定

図 2.2:¥7二2の場合の個別基本動作 (実線矢印 :制約条件を満たす遷移，破線矢印 : 制約条件を満たさない遷移 )

(17)

表2.3:相互基本動作の例

相互基本動作制約条件

① S‑ 平行

Y 2 ‑ Y 1 =

:1・2‑

. 1 : 1

② S< 間隔拡大

Y 2 ‑ Y 1 <

.r2 ‑.7:1

③ S> 間隔縮小

Y 2 ‑Y 1 >

:山一 Tl

④ ^S~ ^{軸対象} :r 1 ‑

Y 1 = Y 2 ‑

^:^L^・2

⑤ S仁分岐 .rlく :1・

2

，

Y l

二

Y 2 =

y

⑥ Sコ ^{合流} ^T1

=

:1・2二 .1・，

Y 1 < Y 2

⑦ Sa(s) 間隔指定 (グ:間隔) :rl ‑:1:2 グ

③ S1U

( 1

ゴ

w )

^{間隔大 (}^凡 ^:間隔) ^{T1 ‑ T}²

> f 3 w

⑨ ηS(/3η) 間隔小(仇:間隔) :f1 ‑ 勺く。『

t;1 y2

I L

x2

y

日

²

_l _: _t _: _:

Y 1 l y1

x1 x1

I

① 平行 ② 間隔拡大 ① 間隔縮小

*

.，

よx2

y2~ y~， X2 ^y2

￨、ヲト..x y1 平、~I ^司~ x1 y1

x1

① 軸対称 ① 分岐 @ 合流

(18)

表 2.4:記号辞書の例

終端記号元数個別基本動作

1・ε1争 k 軌跡 1(./"1) 軌跡 2

( : C 2 )

a γ→ 0'1γノ ×

2 γ¥

C 2 T'¥̲ γノ

九:水平または単調増加 (単元信号軌跡、) b: 軌跡 1は単調減少，軌跡 2は水平

2 . 5 . 4 多元基本動作

相互基本動作制約条件

× r ‑ ¥7

: S

y

: S

:1 1

'1くy]三:r:1

+ マ

:r2二

Y 2

:1' 1く Yl三:1'1

+ マ

s‑‑ 1'2 ‑ ¥7

: S Y 2

く T2 :t:] ‑

Y l

二

Y 2

一.L・2

L ̲

c 軌跡、 1は単調減少，軌跡、2は単調増加，

2本の軌跡は軸対称

多元基本動作は，個別基本動作と相互基本動作の組合せで指定される.多元基本動作の制約条件を満たす画素の動作すなわち個別及び相互基本動作の制約条件を同時に満たす画素の動作が，終端記号となる.表2.4に，終端記号を定義するための記号辞書の例を示す.表の右端に，各終端記号に対する多元基本動作としての制約条件を示す.これらの制約条件は，表2.2

，

2.3を参照することにより求めることができるため，次節以降の記号辞書では省略する.表中の一"は基本動作を特に指定しない場合，もしくは他の基本動作により自明である場合を意味する.また表中の x"は，単元信号軌跡に対する相互基本動作指定のように基本動作の指定が不可能な箇所である.

(19)

x

x2

x1 t

;←a*+;+ーb*一→;.ゲ白一一b女一‑‑..:

図 2.4:多元信号軌跡の例 1(2本の軌跡)

終端記号元数個別基本動作相互基本動作 vε V

y

軌跡 1(:rl) 軌跡2(:r2)

a 2 γノ 1・→ 01' γ/ 5=: 01' ~

2 T'¥̲ γ‑， 01' '1""‑.，. &二01' S<

a 軌跡 lは単調増加，軌跡2は水平または単調増加，軌跡問の関係は平行または間隔縮小

b:軌跡 lは単調減少，軌跡2は水平または単調減少軌跡、聞の関係は平行または間隔拡大

2 . 6 多元信号軌跡のモデル化の例

以上の基本動作を用いた多元信号軌跡のモデル化の例を以下に示す.

多元信号軌跡のモデル化の例 1

図2.4の軌跡をモデル化するために，表2.5の記号辞を用意する.表に定義された終端記号&】bを使用すると，図の 2本の軌跡をい*b*)*と表すことができる.この記号列は， 2本の軌跡がともに単調増加しながら間隔縮小する状態と単調減少しな

(20)

x

x2

x1

t . ‑

a

、

^b.^.^.^一^一^c^*^ー→^d^.^e^*^.^.^.^f^.^.^.^{ゲギ} t 図 2.5:多元信号軌跡の例 2(矢印)

終端記号元数個別基本動作相互基本動作 vεlケ k 軌跡 1

( : r 1 )

軌跡2

( : r

2)

& 1 ‑‑v. × ×

2 Sc ancl S‑;:.

C 2 _ー_ー_→ γ→

2 δ)

C 2 7 ・ノ 1・¥ s‑...‑

f (2→)1 γノ 7"" らむlcl，~

a :

連続(単元軌跡)

b:垂直(下向き)な軌跡 1と垂直(上向き)な軌跡、2の2本の軸対称、な軌跡に分岐

c :

2本の軌跡、ともに水平

d:軌跡 1は垂直(下向き)，軌跡2は垂直(上向き)， 2本の軌跡は軸対称 e 軌跡 1は単調増加軌跡2は単調減少 2本の軌跡は軸対称、

f:軌跡 1は単調増加軌跡2は単調減少 2本の軌跡は軸対称、かつ 1本の軌跡に合流

(21)

する正規文法の書換え規則は，開始記号を

S

，非終端記号を

A j B

として，

s

→孔'.，....J..，

S→

a B . A

→

a A . A

→

b B ) B

→

bB.B

→

a A . B

→

b

となる.

次に図 2.5の軌跡のモデル化の例を示す.表 2.6で定義された終端記号仕fを使用することにより図の軌跡をど

b c * c l e

マゲと表すことができる . ここで，どに対応する軌跡としては図中に示されていない任意の連続な軌跡、を想定している.この記号列を生成する正規文法の書換え規則は，開始記号を

S

A j B i C ) D

として，

s

^→

^aA ⁾ ^A

^→

^aA ^j ^A

^→

^bB ⁾ ^B

^→

^C ^B ⁱ ^B

^→

^c ^l ^C ⁾ ^C

^→

^c ^C ⁾ ^C

^→fD;

^D

^→

aD.D

→

a

となる.

図 2.5の軌跡に対して，水平平行な部分(胴)と間隔縮小する部分(頭)との聞の← 短に関する記述を追加する場合には文脈自由文法を用いてモデル化する必要がある.

この場合，表 2.6の終端記号

a ‑ f

を使用することにより，図の軌跡をど

b c m c l e η f

ど('m.

>

η)と表すことができる.この記号列は，開始記号を

S

A ) B

，

C ) D j E

として，

s

→

A b B D e f A ) A

→

aA

，

A

→

a . B

→

c B ) B

→

c ) D

→

CDE

，

C

→

c . D

→

c

l

，

E

→

e

という文脈自由文法の書換え規則により生成できる.

2.7 まとめ

本章では，検出対象とする多元信号軌跡、の定義と，そのモデル化について述べ，

いくつかの例を示した.本章で提案した多元信号軌跡のモデル化は，個々の軌跡、の

局所的振舞いだけでなく軌跡相互間の関係も考慮した方がより高精度な軌跡、の検出が可能になるとの考えに基づくものである.個々の軌跡の局所的振舞いを示す個別基本動作と，軌跡相互間の関係を示す相互基本動作とを用意し，それらの組合せにより多元基本動作を定義した.多元基本動作の制約条件を満たすような画素の動

(22)

2.2， 2.3で示した個別/相互基本動作は現段階で準備した基本的なものを例として示したものであり必要に応じて追加することができる.

(23)

第 3 章

正規文法モデルを用いた多元信号軌跡の解析

3 . 1 まえがき

本章では，軌跡群検出法研究の第一段階として，正規文法(以下，

RG)

モデルと動的計画法とに基づく検出法を提案する.

RG

モデルと等価な有限状態、オートマトン (以下，

F S A )

モデルを準備し，

FSA

モデルによって出力される軌跡群と入力多値画像との問で最大一致をとる形で解析を行う.

FSA

の各状態は軌跡群の時間的部分構造に対応し，出力記号は多元基本動作の制約条件を満たす画素の動作に対応する.局所的な決定は行わずに

FSA

によって制御される状態の遷移と各状態で指定される経路群とを動的計画法(以下， DP) [10] によって並列的に探索することによりモデルに最大一致する軌跡群を定める.なお処理対象となる入力画像は濃淡画像のままであって線分候補の抽出等の前処理は一切想定していないことを注意しておく .

以上の考えに基づいて多元信号軌跡解析アルゴリズムを構築し，さらにビームサーチ[11]を導入して計算量の効率化をはかる.説明の簡略化のため，まず、単冗および2元信号軌跡の検出について記述する.3本以上の軌跡の検出への一般化は 3.5節で論じる.

(24)

3 . 2 有限状態オートマトンによる多元信号軌跡のモデル

イヒ

次式で定義される FSAを用いた多元信号軌跡のモデル化について説明する.

FSA =

(Q， ~; ム，qo，

F )

﹄tF〆︑ ^q^J ^1l^ム ^︑^︐^F^︑^S^B^B

Q:状態集合

{ ρ )

u:出力記号集合

{ n }

(出力記号 η は多元基本動作(RGでの終端記号)に対応する) ム:状態、選移規則 (b(p，川 =q は IJ-Lq を意味する. ただし p，q ε Qiηε~) qo:初期状態 qoε Q

F:最終状態集合

{ f } f

εF C Q

まず，実際の画像との接点となる各出力記号を，多元基本動作により定義する. 次に具体的な全体構造および部分構造を各状態で定義する.さらに状態間の遷移規則を与える.例として表 3.1の出力記号を想定し遷移規則が図 3.1の状態遷移￨文のように与えられる場合を考える.この遷移規則はどb*という記号列を出力する.

すなわち，最初は水平平行で，ある時刻(状態遷移点 (A→ B))を境にして単調増

加かつ間隔拡大に変化するような 2本の軌跡を表すモデルとなっている.このモデルによって生成される 2本の軌跡の例を図 3.2に示す.

3 . 3 多元信号軌跡の解析アルゴリズム

3 . 3 . 1 問題の設定

入力画像A =α(:r，

t )

の中から，与えられた FSAモデルに最大一致する軌跡群を

検出するという問題を考える.この問題は，モデルに従う軌跡群のうち，その軌跡上の濃度値の総和が最大になるものを探索する問題である.例えば2本の軌跡、の場合，

(25)

出力記号元数個別基本動作相互基本動作

T/ k 軌跡 1

( : r l )

軌跡2

( : r 2 )

a 2 γ→

2 1 ・ノ γノ Sく

a :

軌跡1， 2ともに水平

b:軌跡1， 2ともに単調増加，軌跡聞の間隔は拡大

b

刈

3 . 1 : FSA

によるモデルの記述

( S

:初期状態，

B :

最終状態)

3ピ

a‑‑‑‑̲‑̲ ι* 0‑‑‑‑.: x2

x1

t

図

3 . 2 :FSA

モデルが出力する軌跡、の例

(26)

FSAモデルM が出力する軌跡群の集合をL(M)とすると， {( .r 1 ) t); (:1' 2

J )

}ε L(M) という条件の下，目的関数

乞

T

( α ( . r 1 ，

t)

+ ^a ⁽ ^.

⁷^:²^句t)) (3.2 ) 1=1

を，

L (

^λイ)に関して最大化する問題として定式化することができる.すなわち

G(A)M)=~n出 L(ルイ)

E

T

二

(α(:r1't)

+

α(:r2， t))

{(X] ，1)，(X2，1)}εL(A;f )

(3.3 )

この最大化問題は，時刻fを段とする多段決定過程と見なすことができ， DPを用いて解くことができる.各段での出力記号の評価は， 2.5.1節で説明した個別基本動作と 2.5.2節で説明した相互基本動作とに対する制約条件の下で DP漸化式を計算す

ることにより行われる.

以下では，まず単元基本動作を評価する DP漸化式について説明し，次いで2元基本動作を評価する DP漸化式を説明する.その後，それぞれの DP漸化式と FSA

を統合した解析アルゴリズムを構築する.

3 . 3 . 2 単元基本動作の評価

単元信号軌跡の基本動作である単元基本動作は， 2.5.1節で定義した個別基本動作によって指定される.表 2.2の個別基本動作 ① ⑤ は，次の DP漸化式によって評価される.

g (

川

t ) =

^α⁽^え73t)+mpxlg(U31‑1)l

( 3

.4 )

ここでg(:円t)は，座標(:r，t)までの最大累積濃度値である.g(:r， t)には， (:1'， t)が軌跡上にあると仮定した場合の，軌跡の評価値 α(:rグ)が累積される.yは点(川t)に接続する 1時刻前の点の :r座標である.この

u

に対する制約の与え方によって，衣 2.2の個別基本動作 ① ⑤が指定される.

個別基本動作⑥ ③(垂直)は別の DP漸化式(3.5)によって評価される.

(27)

111 ti it l‑

‑I

ll i‑

‑1

1i J l

4't uu

n y

+

‑

1i jJ一_l

T Z一lll

川一

U

Z 2

円一

ト

﹁lll﹄l

'1 SI ll i‑

‑L

X

内Gym

‑ 一

4l

οコ (3.5 )

右辺第 l項の

α : (

川

t )

の和は，垂直成分を評価するための項である.1 時刻の遷移待に積算を行う他の基本動作とのバランスのため，この和を垂直成分の線分長で平均化している在1

3 . 3 . 3 2 元基本動作の評価

2元信号軌跡の基本動作である 2元基本動作は， 2.5.2節で説明したように，個別基本動作と相互基本動作の組合せにより定義される.

2

元基本動作の評価は，与

えられた制約条件の下で，次の DP漸化式を計算することによって行われる.

g(:7.:1， :.7:2， t) =α(.1:1，.':.72，t)

+ 守安

[g(Y1，Y2， t ‑1)] i (3.6)

。~(:r: 1，t)+ α( 勾?の

α (

川，:1:2，t)二 2

( 3 . 7 )

ここで g('.:.71，:r2，t)は，座標(.T1，t)， ('.:.72， t)までの 2本の軌跡の最大累積濃度値であり

， α(:r 1 ， :1: 2， t)は時刻 tにおける 2個の画素(川，t)，(:"1²，t)の平均濃度値である. g(::t1' ::7.2， t)には，(:1.1，t)，(::t2パ)が軌跡上にあると仮定した場合の， 2本の軌跡、の平均濃度値が累積される.Y1， Y2は，それぞれ点(川，t)，(:r2' t)に接続する 1時刻前の点のえ:座標を表す.この Yl

，

Y2に与える制約条件によって， 2元基本動作が指定される.個別基本動作として，垂直"が指定されている場合には，式 (3.11)を2元に拡張した評価式を使用する.なお，式

( 3 . 7 )

において濃度値の平均を用いているのは，

分岐，合流などによって生じる元数の変化に対応するためである注2

j主lこの平均化を行わないと垂直成分が優先して検出される傾向が生じる.式(3.5)はこのような傾向は好ましくないとの立場をとったものである.

注2平均化を行わないと元数の多い軌跡を検出する傾向が生じる.

(28)

3 . 3 . 4 解析アルゴリズムの構築

前節までに説明した

DP

漸化式と

FSA

を統合して解析アルゴリズムを構築する.

この解析アルゴリズムは，連続音声認識に用いられるフレーム同期

DP

法

[ 1 1 ] . [ 1 2 ]

に類似した考え方に基づいている.フレーム同期

DP

法は単語列の生成モデルに某づく連続音声認識法で，各フレーム(時刻)を単語遷移点と仮定して最適な単語列と遷移点を探索する.ここでは，最適な記号列と状態遷移点の探索に同様のアルゴリズムを用いる .

3 . 3 . 5 基本的な考え方と軌跡の探索空間

FSA

の各状態 ρ毎に探索空間

( x

，t，

p )

を対応させ，与えられた状態遷移規則にしたがって，t = 0の初期状態からそれぞれの探索空間を経由して t = Tでの京終状態

f

に至る経路のうち，累積濃度値g(x

，

T

I

^f⁾が最大になる経路を見つける.

図

3 . 3

に，

3 . 2

節で例示したモデルを用いて，入力画像 α(:Lス)から

2

本の軌跡どb* が検出される様子を示す.状態 A，Bに対応して 2個の探索空間を用意し，各々で記号列どおよびb本に対応する 2本の軌跡を検出する.検出すべき軌跡は最初は状態、A

にあり，何処かの時点で状態Bに移り，最後は状態Bで終了する.このような 2本の軌跡で，時間全体にわたっての軌跡上の平均濃度値の累積値が最大になるものを探索する.

各々の状態に対応する軌跡の基本動作は，式 (3 .4 )~(3.6) の DP によって評価されることは，すでに述べたとおりである.あらたに考慮する必要があるのは状態間の遷移である . 以下にその解析アルゴリズムを示す.

3 . 3 . 6 解析アルゴリズム

いま状態聞の遷移が，状態遷移規則 d(p

，

η)二 qによって行われるとする (p

，

q

ε

仏 ηε~) .

3 . 3 . 2

，

3 . 3 . 3

節の

D P

式を拡張し，この状態遷移規則の制御を組み込むことによって解析アルゴリズムを得る.

図

3 . 3

の探索空間に対応して次のような解析テーブルを用意する.

(29)

X

s t a t e A

X↑

a ( x ， t )

¹

i n p u t image

X1 ~ ~

.

12‑‑‑‑‑‑t T

a a . . . . . . ・ . . . . . . . . . . . a

_bb

・ . .

^H

・・

b

図 3.3:解析アルゴリズムの概念図

• g(:r， tlq) :時刻 tで状態 qにあり，軌跡が1本 (k= 1)で:むを通るとしたときの，その時刻までの最大累積濃度値を記憶する.

• bp(:l、スIq):上記に対応し， 1時刻前の状態、 p と軌跡、の位置

u

とを記憶する.

• g(:rl' :r2， tlq) :時刻fで状態、qにあり，軌跡が2本

( k =

2)で川，:7.:2を通るとしたときの，その時刻までの最大累積濃度値を記憶する.

• bp(川，:r2， t

I

q) :上記に対応し，1時刻前の状態 p と軌跡の位置 uとを記憶する.

初期設定

初期状態 qoでの元数kによって，以下のように初期設定を行う.

(30)

(i) k = 1の時，

n u n U

O A UA 二

﹂ア

υ4ρt

OJ

∞

〆1

11 '

︑

1_l it t

p 一一

ハU

〆rtt¥

円りJ (3.8 )

(ii) k二 2の時，

n円

∞

fE lt

九F

BE E‑

‑

一一

︑︐Jゆ

ii

ハU

内ノ

‑

︑︐丸

︑︐︑f

リJη ' l ¥

jJ二 qo

，

pヂqo・

(3.9)

時刻fにおける処理

f二 1，2，・・

，

T の各時刻で各状態 qにおいて，各ぇ:(単元の場合)，各

( r :

1， :7:2)

( 2元の場合)に対し，次の [lJ‑ [3Jを実行する. [ 1

J

単元信号軌跡検出

式 (3.4)に対応して，表2.2の① 1ーから ⑤ 1/(0)のいずれかの記号 nにより状態、pから状態qへ遷移する各:1に対して， ]J， yをパラメータとして

g(T.，tlq)

=

α

( 1 :

， t)

+

m，?̲x m̲ax [g(y， t ‑1

I

p)] (3.10)

p y

b(p，η)=q

を計算し

ι

，上式の最適なパラメ一夕

ω (

p，

) ω

y ^を^b^句^p⁽^川^:¹¹

約条件は，状態遷移規則 d(

ω

^p

^，

^η^川)二 ^q^の記号^η^，^{によつて与えられる}^.^ここで同^ーの

基本動作の継続は，同一状態の連続を示す遷移規則 d(p，^η)=pによって実現する.

式 (3.5)に対応しては，表 2.2に⑥ ③で示した個別基本動作垂直 "(Tl，rr，Tj)で定義された記号ηによって遷移する状態qにおいて，各:7・に対して，p

，

yをパラメー

タとする次の式が評価される.

I

_0αC~ ， t)

I

g (

ぇ，:t

I q )

= ln.~x m^~x ¹¹~ ^‑^y^.^.^.¹^I ，

+

9 (y， t ‑1

I p )

1 6

仏

︑︑

1a︐r

‑ E ム

11ムqJ 〆

︐r s︑

上式の計算の後，最適なパラメータ (p

，

y)をbp(:r

，

t

I

q)に格納する.個別基本動作垂直"は継続を許さないものとし，p戸qなる d(p，n) = qに対して，式(3.11)が評価される.

(31)

s t a t e A

g ( x ， t / C )

g( ， x

t /

B )

争 f

夫??印

^，

^t/

^A)

H t ¥ a ( x ; ふ)

X=(X1，X2)

υ

図 3.4:DP 漸化式の計算の様子

[ 2

J

2元信号軌跡検出式 (3.6)に対応して，

g(九 :7:2，t I

q )

=α(^{九九}t)+mpxT

宏

[g(Yl，Y2， t ‑1 I p)] (3.12)

o(p，n)=q

を計算し，up(川，:7:2， t I q)に上式の最適なパラメータ (p

，

Yl

，

Y2)を格納する.ここで，

パラメータ Yl

，

Y2に対する制約条件は， 2元基本動作を表す η によって与えられる.

2元の場合においても，基本動作が継続を許されているならば，p = qなる 6(p，η) = qを評価し，継続が許されていないならば，p

#

qとする.図 3.4に式

(3.12)の処理の様子を示す.

[ 3

J

元数の変更

相互基本動作のうち， Sc(分岐)"と Sコ(合流)"では，それぞれk

=

1→ 2，

k二 2→ lなる元数の変化が生じる.よって，分岐の場合には式 (3.10)，(3.11)を計算した後，

qLqL ︑︐也︑︐a︑

= 4

ナ

︑ι︑t

'EA3E&

おお

P4

千ι

川∞

'︑ll/ZEE‑ バ民一

・ ‑

一一 PA

4'LV

内ノ﹄

fl¥

円UJ (3.13)

(32)

によって元数の変更を行う.合流の場合には式 (3.12)を計算した後，

g(.r， t 1 p)ニク(.rⁱ.r， t 1 p) (3.1.J) によって元数の変更を行う.

バックトラックによる最適軌跡の検出

t = T までの処理が終了した時点で

( : : . 1 ，

f)^二 argma.x[g(川T1 f)] (3.15)

または

(ん;九f)= argmax

[ g ( . C l

，^山 ^T¹f)] t'iF︑︑〆っο ‑ょ‑ uhハ '^'^{l '}^︑^︑

によって，軌跡の終端と最終状態とを決定する.この点から b旬'p(:川lt

b句'pベ(~川1，匂，t

川 I q ω )

を参照してパツクトラツクすることにより，求める軌跡を検出する.

検出された軌跡とモデルとの一致度は，

G(A ， M) =

m

ァ

^[⁹⁽^:

: 1 ， T

1 f)] (3.17)

または

G(

μ

A

，

M片=)

m 〉 : f

旬[g(:え芯1工川 :

によつて計算される.なお，式 (3.17)，(3.18)で求められた軌跡の評価値が極端に小さい場合は，モデルに対応する軌跡は検出されなかったと判定する.

3.4 ビームサーチによる計算量の低減

以上に説明した，FSAモデルを用いた多元信号軌跡解析アルゴリズムの計算について考察する.サイズ̲¥:"x T の入力画像から， 2元信号軌跡を検出する場合，

与えられた FSAモデルの状態数を

I Q I

，遷移規則数を￨ム!とすると，各時刻 tで

( : 7 :

¹， T2，P) (1三^C^l

<

^:^r2三)':，jJ

ε

Q)の評価を行うため，時間計算量は 0(1ム1̲¥:"2T)

(33)

となる.また検出に必要な解析テーブルのサイズすなわち空間計算量は， ₀₍_1ο1_{_~}₂_T₎ となる.特に，探索空間のサイズは _~2 に比例するため探索空間の圧縮によるアルゴリズムの効率化が必要となる.

そこで探索空間を圧縮するための方法として連続音声認識などで用いられているビームサーチ (bcarnscarch) [11]の導入を検討する.ビームサーチは，最適経路と

して可能性の低いものは以後の計算から除外するという枝刈りを行い，枝刈りの結果残った点だけを計算することで，探索空間を圧縮し計算量を大幅に低減する効率化手法である.ここで，枝刈り条件をパスした点の集合をビームと呼ぶ.

枝刈りは，各時刻での累積濃度値gと枝刈りの基準として用意するしきい値との比較により行われる.しきい値の求め方としては様々な方法が考えられるが，ここでは，文献[11]で用いている方法を採用する.各時刻t‑1でgn^{川二} max[g(xJ‑1

1

p)] (x = (~l:何) Or

( : r

l(t)，.1'2(t)) )を求め，

B (

t)二 9nw.l一入(入:余裕分を与える定数)をし

きい値とし， g(x， t 1 p)が

B (

t)未満の点 (x，t^Ip)に続く軌跡の探索を打ち切る.耳支適な余裕定数入の値は対象画像の品質や与えられるモデルによって異なるため，実験的に求める必要がある.

3 . 5 元数たに関する一般化

3.5.1 軌跡の探索空間と解析テーブル

前節までに説明したアルゴリズムを，k本の軌跡x(t)

=

(:rl(t)， :l:2(t)，・・・³九・(t)) を検出するアルゴリズムに一般化する.まずk本の軌跡に対して，探索空間 (x

，

t¹p) を用意する (x=(:rlバ2，・，:rk)，l三:r1 :S; :1: 2 :S; ..三九三̲¥"，1三f三T

，

p:状態).

与えられた

FSA

モデルの状態遷移規則にしたがって，t =

0

の初期状態から各状態に対応するそれぞれの探索空間を経由して，t二 T での最終状態

f

まで至る経路のうち最大の累積濃度値を与える経路を見つける.

まず上記の探索空間に対応して次のような解析テーブルを用意する.

(34)

の時刻までの最大累積濃度値を記憶する.

• up(ん)(xJ1 q) :上記に対応し， 1時刻前の軌跡の位置

ν

と状態ρとを記憶する.

3 . 5 . 2 解析アルゴリズム

初期設定

時刻 t= 0で，初期状態f]

o

での元数kに対し，以下のように初期設定を行う.

n u

nu

oiOA

=

﹂

f

pa υ4

白川

∞

fB

EE

'

︑

FBEEt

‑ ‑

︑jqSFA

n u

z

r' '

t︑︑

1K

円UJ (3.19)

各時刻tにおける処理

t = 1，2，・・・

，

Tの各時刻で各状態 qにおいて，各Zに対し 3.3.6節と同様の処理を行う.式 (3.6)に対応して DP漸化式は，p，

ν =

(Yl

，

Y2^γ ^.

，

yん)をパラメータとして，

ザ ) ( Z 3 tlq)=; 芝山 ? 巾

m^以 m^以 g(k)(ν

ス ‑

1 1 p)1 (3.20)

κ‑ァ‑ p Y L j

γ 1=1 5l(p，n)=q

となる.ただし個別基本動作として垂直"が指定されている場合には，式(3.11) をk元信号軌跡に拡張した式を評価する.

以上の k本の軌跡を検出するアルゴリズムの時間計算量，空間計算量はそれぞれ

0 ( 1

ム

1 ‑ > :

んT)，O(IQI̲>:kT)となるが， 3.4節で説明したビームサーチを一般化して適することで，計算量の低減が可能である.枝刈りの基準には 3.4節と同様の基準を用いる.すなわち，各時刻t‑1であnαェ二 rnax[g(k)(X，t‑11 p)]を求め，e( t) = gnw.x一入をしきい値としてがん)(x

，什

p)

<

e(t)であるような点 (x

，

t1 p)に続く軌跡の探索を打ち切る.

1¥ックトラック

t = T までの処理が終了した時点で

G(A

ぅ

M) = でア [ g ( 川， T

1

f ) ]

⁽³^.²¹⁾

九州大学学術情報リポジトリ