以上に説明した，FSAモデルを用いた多元信号軌跡解析アルゴリズムの計算 について考察する.サイズ̲¥:"x T の入力画像から， 2元信号軌跡を検出する場合，
与えられた FSAモデルの状態数を
I Q I
，遷移規則数を￨ム!とすると，各時刻 tで( : 7 :
1， T2，P) (1三Cl<
:r2三)':，jJε
Q)の評価を行うため，時間計算量は 0(1ム1̲¥:"2T)となる.また検出に必要な解析テーブルのサイズすなわち空間計算量は， 0(1ο1_~2T) となる.特に，探索空間のサイズは _~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，tI p)に続く軌跡の探索を打ち切る.耳支 適な余裕定数入の値は対象画像の品質や与えられるモデルによって異なるため，実 験的に求める必要がある.3 . 5 元 数 た に 関 す る 一 般 化
3.5.1 軌跡の探索空間と解析テーブル
前節までに説明したアルゴリズムを，k本の軌跡x(t)
=
(:rl(t)， :l:2(t)，・・・3九・(t)) を検出するアルゴリズムに一般化する.まずk本の軌跡に対して，探索空間 (x，
t1 p) を用意する (x=(:rlバ2，・ ，:rk)，l三:r1 :S; :1: 2 :S; ..三九三̲¥"，1三f三T，
p:状態).与えられた
FSA
モデルの状態遷移規則にしたがって，t =0
の 初 期 状 態 か ら 各 状 態 に対応するそれぞれの探索空間を経由して，t二 T での最終状態f
まで至る経路の うち最大の累積濃度値を与える経路を見つける.まず上記の探索空間に対応して次のような解析テーブルを用意する.
の時刻までの最大累積濃度値を記憶する.
• 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
1f ) ]
(3.21)によって，モデルに最もよく 一致する軌跡の評価値を計算し，
(Xi f) =
叫ア
x[ g (
ん)(XiTI
f)] (3.22) によって，最終状態f
における軌跡群の終端￡を決定する.この点から，up(ん)(xJI
(j) を参照してパックトラックすることにより 求める軌跡を検出する.3 . 6 評価実験
3 . 6 . 1 実験の概要
以上に説明した多元信号軌跡解析アルゴリズムをワークステーション上に実装 し，アルゴリズムの性能評価のためにテスト画像に対する検出実験を行った.実装 の詳細については付録で説明する.
まず， 2元信号軌跡を対象として検出能力とピームサーチの効果とについて実験 を行った (3.6.2節‑‑‑3.6.5節).さらに， 3.5節で説明した 3本以上の軌跡の検出アルゴ リズムの動作確認のための検出実験を行った (3.6.6節).
2本の軌跡を含むテスト画像としては ( a) 平行な 2本の正弦曲線(図 3.5(a))
( b )
周期が等しく振幅が異なる2
本の正弦曲線(図3 . 5 ( b ) )
(c) 2本の方形波(図 3.5(c))
を含む 3種類の画像を用意した.ここで(a)，(b)の軌跡群は，文 献[8]の心臓エコー 信号を想定したものあり ，(c)の軌跡群は，個別基本動作 垂直"を検出する評価 式の動作確認のために用意したものである.上 記 (a)，(b)ベc)の軌跡の濃度値を一定 (255) として，各軌跡、をそれぞれ含む 3種類の画像に，一様乱数によって作成した 256階調の雑音を重畳した画像，各 100枚をテスト画像とした.100枚のテスト画 像は，乱数の初期値を変えて雑音を重畳したものであり，雑音の平均電力は同程度
X
X
(a)paralleltwo T sinusoids.
X
X
X
(C)two rectangular T waves
図 3.5:実験に使用した 2元信号軌跡
X
T (a) noise‑distorted image
including paral恰Itwo sinusoids.
(SNR 9.0[dB])
T
QU
I‑AU
e o
割 凶
配‑ m
nド
q v
n o ow
司l l A Y E
. h u
︐︐
s z︑
4︐I
4︐ ︐
x
T (b) noise‑distorted image
including non‑parallel two sinusoids.
(SNR 9.1 [dB])
x
T (c) noise‑distorted image
including two rectangular waves.
(SNR 10.6 [dB])
図 3.6:雑音を重畳したテスト画像の例
実験結果の評価には，式
( 3 . 2 3 )
，( 3 . 2 4 )
で定義される平均2
乗誤差(rv 1 S E )
および 検出率 (TrackingRate: TR)を用いた.但し， :r 1 ( t )) :: 7.2 ( t )は真の軌跡、の時刻 tにお ける :7.:座標を表し，王:1(t)，
:I:2(t)は検出軌跡の時刻 fにおける :τ座標を表す庄3 平均 2乗誤差は真の軌跡、と検出軌跡、との類似度を示したものであり 検出率は真の軌跡、と検出軌跡とが一致する割合を示したものである.
M
四=安佐川ト
:1:1(t))2+ 川
注3.r( t)が垂直である場合には，垂直な軌跡の端点の座標を .r(t)とする.
?
TR こ す さ { b (
.r1 ( t )‑I : 1 ( t ) ) + b (
.r:2 ( t ) ‑
.l' 2 ( t ) ) }
x 100 (%). (3，2.J) ここで，仰 ) = ( ; : ; ; :
(3.25)また，テスト画像の品質を評価するために，次式で計算される
SN
比を用いた.2552 S1¥lR二 101og1o
雑音の平均電力 [clB]. (3.26) なお 3.6.2‑‑‑‑‑3.6.4節の検出実験には， 3.4節で説明したビームサーチは使用してい ない.ビームサーチの効果については， 3.6.5節で検討する.
3 . 6 . 2 2 本の平行な正弦曲線の検出
図3.6(a)に例示したようなテス ト画像100枚を対象として， 2種類のモデルを用 いた検出実験を行った.使用したモデルは次の2種である.
( A )
制約条件として連続性のみを与えたモデル (B) 平行な 2本の台形波のモデル(表 3.2及び凶 3.7)但し，
( A )
，( B )
の 両 方 に 引 く 乃 の制約条件を与える.( A )
のモデルを与える解析法 は，多元信号軌跡、のモデル化を行わずに連続な軌跡を一本ずつ逐次検出する場合に 相当する.(B)のモデルは，正弦曲線の近似としての台形波のモデルであり，表 3.2 及び図 3.7によって与えられる.図3.7の状態遷移図の各記号には?表 3.2の a，b，cが それぞれ対応する.ここでは軌跡の最大傾斜を ¥7=
2とした.この FSAモデルは，水平，" 単調増加"， 水平"， 単調減少 "を繰り返す平行な 2本の軌跡を表す
( a
，
*b*a*c* )*という記号列を出力する.図3.8に，検出した軌跡、の例を示す.左から1)1買に，入力画像，連続性のみのモデ ル
( A )
を与えた場合の検出軌跡，平行な台形波のモデル( B )
を与えた場合の検出軌表
3 . 2 :
平行な2
本 の 正 弦 曲 線 の 検 出 に 用 い る 記 号 辞 書 出力記号 元 数 個 別 基 本 動 作n k 軌 跡 1(.r]) 軌 跡 2
( : r 2 )
a 2
2 T→ 01' " ノ・
C 2 7・̲ 01'
1 ' " "
a :
軌跡1，2ともに水平b:軌跡 1，2は水平または単調増加 軌跡問の関係は平行 c 軌跡1，2は水平または単調減少，軌跡、間の関係は平行
C
相 互 基 本 動 作
s‑
8‑
a
図 3.7:台 形 波 近似正 弦 波 モ デ ル に 対 す る 状 態 遷 移 図 (S:初期状態， A:最終状態)
を用いた場合に最高の検出率を示したテス ト画 像 に 対 す る 結 果 で あ り ， 下 段 は 最 低 の検出率を示したテス ト画 像 に 対 す る 結 果 で あ る.
表
3 . 3
に，連 続 性 の み の モ デ ル( A )
と，平行な台形波のモデル( B )
のそれぞれに よる検出率の分布を示す.また検出率と平均 2乗 誤 差 の 平 均 値 を 併 せ て 示 す . 表 か ら，正 弦 曲 線 の 近 似 と し て の 平 行 な 2本の台形波モデルを与えることで，より高車両 度 な 検 出 が 可 能 で あ る こ と が わ か る.X
x
Input Image
x
" ~/へ". /
1r'~
・へ¥ / J¥
J/￨ (x
T TR: 74.6%. MSE: 0.09
T TR: 67.2%， MSE: 0.090 detected trajectories with continuity condition only. (Model (A) )
X
xp~
11 ~lt
X
X~~_/'，-r-ヘ〉
~ /人'へ
11 ，~j 、)I ~ T TR: 83.6%. MSE: 0.045
detected trajectories with trapezoidal wave mode. ( l Model (8) )
図 3.8:連続性のみのモデル (A)と平行な台形波モデル (B)による軌跡、の検出例
表 3.3:平行な 2本の正弦曲線を含んだ雑音画像に対する解析結果
検出率(%) モデル
未 満 以上
( A )
連続性のみ (B)平行な台形波90 84
90 80 16
80 70 47 70 60 47 60 50 6
平均検出率(%) 69.2 92.7 平均 NISE 0.12 0.025
図3.8の下段に示すように 平行な台形波のモデルを与えても検出を誤るケース がある.誤検出の部分でも，軌跡、は 水平"， 単調増加"， 水平"， 単調減少"
表 3..1:周期が等 しく振幅の異なる 2本の正弦由線の検出に用いる記号辞 出力記号 元 数 個別基本動作 相互基本動作
n k 軌跡 1(:r1) 軌跡 2
( : : 7
2) a 2 γ→2 T~ or 7 ノ・ 1 ・ノ S= 01・S<
C 2 T~ 01・，."" T'¥̲ ~ or S>
a :
軌跡 1，2ともに水平b:軌 跡 lは水平または単調 増 加 軌 跡2は単調増加 軌跡間の関係は平行または間隔 縮 小
c 軌 跡 1は水平または単調減 少 軌跡、2は単調減 少 軌 跡 問 の 関 係 は 平 行 ま た は 間 隔 拡 大
を繰り返す，というモデルに従う軌跡、であることから，台形波モデルによる正弦曲 線の近似が不十分なためであるといえる.
より厳密に軌跡をモデル化するためには
FSA
よりも高度な記述能力を持つ文 法レベルへ拡張する必要がある.また 平滑性"を考慮することにより，検出性能を高めることができると考えられる.
3 . 6 . 3 周期が等しく振幅の異なる 2 本の正弦曲線の検出
3.6.2節の実験は，振幅が等しい正弦曲線を対象として， 平行"という強い制約 をもっモデルを使用したものである.このモデルは 振幅が異なる場合には使用で きないため， 間隔拡大"? 間隔縮小"を制約としたモデルを用いて，周期が等し く振幅の異なる 2本の正弦曲線を検出する実験を行った.
実験は図 3.6(b)に例示したようなテスト画像 100枚を対象として行い，モデル には
(C) 周期が等しく振￨隔が異なる 2本の台形波のモデル(表 3.4及び図 3.7)
を使用した.このモデルは，平行な 2本 の 台 形 波 の モ デ ル (表 3.2，図 3.7))の出
力記号の定義を変更したものであり， FSAの状態遷移規則は同ーのものを使用して いる.
図3.9に入力画像と検出軌跡を示す.上段は 100枚のテスト画像の中で，台形波 のモデル
( C )
を用いた場合に最高の検出率を示したテスト画像に対する結果であり，下段は最低の検出率を示したテスト画像に対する結果である.
表 3.5に，台形波モデル (C)を与えた場合の検出率の分布と平均検出率，平均2 乗 誤差を示す.比較のために， 3.6.2節で用いた連続性のみを制約とするモデル (A)
を与えた場合の結果も併せて示す.
表 か ら わ か る よ う に ， 周 期 が 等 し く 振l隔が異なる 2本の台形波のモデルを与え ることで，連続性のみのモデルと比較して，より高精度な検出が可能であることが わかる.図3.9下段の検出軌跡を見ると，正弦曲線のピーク付近で誤検出が生じてい る.誤検出の部分でもモデルに従う軌跡が検出されていることから， 3.6.2節 の 実 験 結果と同じく，台形波モデルによる正弦曲線の近似が不十分なためであるといえる.
3 . 6 . 4 2 本の方形波の検出
次 に ， 個 別 基 本 動 作 で あ る 垂 直 " を 評 価 す る 式 の 動 作 確 認 を す る た め に ， 図 3.6(c)に例示したよつなテスト画像 100枚を対象とする検出実験を行った.モデル には，
( D )
2本の方形波のモデル(表3.6及び図 3.10)を使用した.このモデルは，表3.6に定義した a‑gに対して， (ど仁lb*fc*eb*g)*とい う記号列を出力する.この記号列はゾ 水平平行"， いずれか l本の軌跡は垂直'¥
という動作を繰り返す 2本の軌跡、を表している注4
判 3.11に入力画像と検出軌跡を示す.上段は 100枚 の テ ス ト 画 像 の 中 で 最 高 の 検出率を示した入力画像とその検出軌跡であり，下段は最低の検出率を示した入力
注4正確には， 水平平行(間隔小)"， 軌跡1垂直(下向き)，軌跡2水平"， 水平平行"， 軌跡 1水平，軌跡2垂直(上向き)"， 水平平行(間隔大)" ， 軌跡1垂直(上向き)，軌跡2水平'¥