? 一
4.6 評価実験
4 . 6 . 1 実験の概要
本章で提案した，遅延を伴う複数の軌跡を検出するアルゴリズムの性能評価のた めに，テスト画像を対象として検出実験を行った.使用したテスト画像は，
(i)遅延を伴う
2
本の正弦曲線(図 4.5(a)) (ii )遅延を伴う 2本の方形波(図4.10(a))(iii)遅延を伴う 3本の正弦曲線(図4.13(a))
という濃度値一定 (255)の軌跡群をそれぞれ含む 3種類の画像に， 一様乱数によっ て作成した 256階調の雑音を重畳したもの各 100枚ずつである.100枚のテスト画 像は，乱数の初期値を変えて雑音を重畳したものであり，雑音の平均電力は同程度 である.(i)の軌跡の遅延は d=7であり， (ii)の軌跡の遅延は d= ‑11である.ま た(iii)の軌跡の遅延は
d
2二 6，の=‑5である.図4.5(b)，4.10(b)， 4.13(b)にテスト画像の例を示す.
実験には，CPU : Alpha 21164A ( 500NIHz ) (SPECint95 : 15.4， SPECfp95:
2l.1 )の計算機を使用した.実験結果の評価には，3.6.1節 で 定 義 し た 式(3.23)の平 均 2乗 誤 差 (NISE)および式 (3.24)の検出率 (TrackingRate: TR)をk元 信 号 軌 跡
に拡張した次式を用いた.
AJSE
二 剖 主 主川 ト
:7:{(t))2，
(4.10)%
ハUハU
×
7ハU
K
乞
MT
h L
凶
1
一 げ
T R 一 一
(4.11)
4 . 6 . 2 遅延を伴う 2 本の正弦曲線の検出
図 4.5(b)に例示したようなテスト画像 100枚に対して，遅延を伴う 2本 の 正 弦
X
Xl¥ / /一‑'"， / / ヘ ¥ / ( ¥
¥ ー / / ¥ ) / ¥ー/// ...̲// .//~-""''''''''''' ....... .r .... 一-~... / ー ¥ 11 ，，........ ~，.../ ""-.~...-// "'-~一/\)/
x 1 (a) two sinusoidal curves with phase delay
(b) noise‑distorted image (SNR: 9.0 [dB])
T'
了'
図 ↓
5 :
テスト画像の例(̲¥"=6
‑‑1)T '
二2 5 6 )
デ ル に は 正 弦 曲 線 の 台 形 波 近 似 と し て 4.2節 で 示 し た FSAモ デ ル を 使 用 し た. まず，提案したアルゴリズムによる遅延検出の妥当性を確認するために， ‑50
<
rl
<
50の 範 囲 の 遅 延 dに対する軌跡、の検出実験を行った. 4.3.1節 の ア ル ゴ リ ズ ム で は ， 各 時 刻fに お い て 探 索 範 囲 の 遅 延dを並列的に評価するが，ここではビーム サ ー チ を 行 わ ず に 各 遅 延dに対して t=
Tの 最 終 状 態 ま で 評 価 を 行 い，遅 延 量 d を 仮 定 し た 場 合 の 累 積 濃 度 値 Gd(Ajんイ) と 検 出 軌 跡 の 検 出 率 と を 調 べ た.ここで， Gd(A，んイ)は次式で与えられる.Gd(AjM )
二 山 出
[U(.L'li.1'2iT)dI
f)] ( 4.12)図‑‑1.6に 実 験 結 果 を 示 す.横 軸 は 遅 延，縦軸は 平 均 検 出 率 お よ び 平 均 累 積 濃 度 値 である.図 か ら ， 最 適 な 対 応 を 与 え る 遅 延 rl=7で 最 大 の 累 積 濃 度 値 を 得 て い る こ とが確認できる.また遅延 d =7における検出軌跡の平均検出率は
9 5 . 2
1{，であった.辺‑‑1.7に，遅 延rl=7における検出軌跡、の例を示す1王2 図 の 上 段 は ， テ ス ト 画 像
ィE'2検出された2本の軌跡 rl(t)(1三f三
T )
と.r2'(t)( d +
1三f三T + d )
の( d +
1三f三T )
の区間を図示している.
ポ 80 ω
~ 60
。 I
cumulative scorec
二~
(.)
C ，，̲
ヘ ミ ミ
h u o
50000
tracking rate
〆
100
45000
ω﹂
0 0 ω ω
﹀一
日何
一コ
に﹂
コυ 40000
35000 20
30000 50 40 7 20
。
‑20
‑40 0
・50
d
図 4.6:遅延量に対する累積濃度値と検出率の変化 phase delay
x2 x1
~
/一¥
~ ~
/ヘ'" /~
~ ~ X
d+1 T+d
(i) highest tracking rate case
d=7， TR: 99.00/0 MSE: 0.005
X x2
Ayt ︐G 十T
(ii) lowest tracking rate case
d=7， TR: 91.50/0 MSE: 0.021 d+1
4.7: 検出軌跡の例(_~
=
64，
T=
200)ち ょ
100枚の中で最も検出率が高かったテス ト画像に対する結果であり，図の下段は，最 も検出率が低かったテスト画像に対する結果である.下段に示すように， 3.6.2節の 実験結果と同じく ピーク付近で検出を誤るケースがあったが 100枚のテスト而 像全てに対して，最適な対応、を示す遅延rl=7で最大の累積濃度値を得ることがで
きた.
以上の結果から，本章で提案したアルゴリズムにより，遅延を伴う軌跡を検出で きることが確認できた.
4 . 6 . 3 ビームサ ーチの効果
次に，ビームサーチの効果に関する実験を行った.使用した入力画像とモデルは 4.6.2節と同様で、ある.
遅延の探索範囲を
‑D+7
三d三D +
7(D
= ‑4:9)として，ビームサーチの余裕定 数を変化させ，計算量の低減効果を調べた.実験結果を図 4.8に示す.図の縦軸は，解析率および平均検出率，平均実行時間を示し 横軸は余裕定数入を示している.こ こで，解析率は，
式(
4.6)において最終状態f
の軌跡が検出でき，かつ，検出軌跡 の遅延が正しい遅延量であった画像の割合である.また，グラフ右端の入二 ∞ は， ピームサーチを用いない場合に相当する.刻 4.8から，入=1000で100枚の画像全てに対して，検出率を劣化させずに正し い遅延の軌跡、が検出できていることがわかる.ビームサーチを用いない場合(入 二 ∞) の平均実行時間は約 9.8X 102秒 で あ っ た の に 対 し，入二 1000では，平均実行時 間約 4.4x 10秒となり，ビームサーチを用いない場合に比して約 1/20の高速化と なった.
次に，ビームサーチを使用した場合の遅延の探索範囲 Dに対する平均実行時間 の変化を調べた.実験結果を図 4.9に示す.縦軸に平均実行時間 横軸に遅延の探糸 範囲 Dを示している.遅延の探索は，‑D+7三d三D+ 7 (0三D三49)の範囲 で行った.実線はビームサーチを使用した場合の平均実行時間 破線はビームサー チを使用しなかった場合の平均実行時間である.余裕定数は 入=1000とした.こ の入により，どの探索範囲の場合でも累積濃度値の低下を招くことなく，最適な遅延
103 .‑‑‑.
c/)
CD
E
C 0 102芯
場・4コ
0..
E O
仁J
•
10
入
1000
margln
実 行 時 間 の 変 化
‑一
hH
‑ 一
C )
ノ
・ ナ : ;
i ‑ ‑ T
‑ a O i
‑‑
‑
一⁝
e O
‑ 一
S O
一 一
mJ JJ・ ‑ ‑
一 :: : 加 入 : ::
d
一 い
H
F一w
r
⁝ 一 一 一 一 一
一 一 以 一 一
一 一
. ‑‑ ‑
‑‑ ‑
‑‑‑‑M
・・
.•••
•••
・・••• ・ ・ ιr
・ ・ ・
・・ト・・
・ ・ ・
一/
一/一一 ' '
︐r '
一
3 0 2 0 0 1
{ω
]ω
EZ
CO
ZS
コ巳
E0
0
解析率，
余裕定数に対する検出手，
図 4.8
49 40 30
20 10
0.1 0
D
図 4.9:遅 延 の 探 索 範 囲 に 対 す る 実 行 時 間 の 変 化
s e a r c h r a n g e
X
X
1(a)two rectangular waves with phase delay TF
X
(b) noise‑distorted image (SNR: 9.0 [dB])
r
刈-1 .10: テスト画像の例 (_~ = 6 ，‑1.T' = 256)
とその軌跡を検出することができた. グラフから ~A節で示したビームサーチに
より時間計算量の低減効果が得られていることがわかる.実行時間は探索範囲IIJ@D に対して線形に増加している.結果として l桁から 2桁の高速化が実現された.
4 . 6 . 4 遅延を伴う 2 本の方形波の検出
刈<‑1.10(b)に例示したようなテス ト画像100枚に対して，遅延を伴う 2本の方形 波の検出実験を行った.これらの入力画像中から
T
= 200の軌跡を検出する.モデルには，表 ~.1の各記号を出力記号とする図 ~.11の FSA を用いた. この FSA モデルによって出力される記号列は(<1*])・(*cl) *であり， 水平平行(間隔小)" ， 軌 跡 1，2共に垂直，" 水平平行(間隔大)"に 軌跡 1，2共に垂直"とし寸動作を繰 り返す軸対象な 2本の軌跡、を表している.このモデルは，第3章の実験で用いたモ デルよりも，少ない状態数 ・出力記号で表された簡単なモデルとなっているが，よ
り厳密なモデルとなっている.
遅延の探索範囲を‑15三rl三0として検出実験を行った.実験の結果， 100枚の
表4.1:遅延を伴う 2本 の 方 形 波 の 検 出 に 用 い る 記 号 辞書 出力記号 元 数 個 別 基 本 動 作 相 互 基 本 動 作
n. k 軌 跡 1(:1." t) 軌 跡 2(.C2)
a 2 γ
一
STI( ，
3"二 10)2 s̲.
C 2 Sw (Jゴ'IU二 10)
2 S~
a 軌跡 1，2共に水平かつ間隔小
b:軌跡lは垂直(下向き)，軌跡2は垂直(上向き)， 2本の軌跡は軸対称、
c 軌跡 1，2共に水平行かつ間隔大
d:軌跡1は垂直(上向き)，軌跡2は垂直(下向き)， 2本の軌跡は軸対称、
C
d
刻 4.11:2本の方形波モデルの状態遷移図
( S
:初期状態、， A，
B:最終状態)X X
x2 x1 x2
‑d+1
resut by the present algorithm d=‑11. TR: 100.00/0 MSE: 0.00
イ‑
4︐ ︐ . X
T+d T
result by the algorithm in Chapter 3 TR: 93.50/0 MSE: 0.25
(i) highest tracking rate case
X X
x2 x1 x2
‑d+1
resutl by the present algorithm d=‑1 0， TR: 96.50/0 MSE: 0.21
4︐ ︐
d︐
︐ .
4︐
︐ ︐
F
x
‑ d
十T 丁
result by the algorithm in Chapter 3 TR: 93.50/0 MSE: 0.20
(ii) lowest tracking rate case
災14.12:検出軌跡の例(̲¥'"
=
64， T=
200)テス ト画像のうち 97枚に対して 最適な対応を与える遅延 d= ‑11で最大の累積 濃度値を得ることができ，検出軌跡の平均検出率は 99.2% となった.比較のために，
3.6.4節のモデル(表 3.6，図 3.10)を用いて，第3章の手法による検出実験 を 行った 結果，平均検出率は 96.8% となった.
刻4.12に軌跡の検出結果の例を示す.図の上段は 本章で提案した手法により最 も高い検出率を得たテスト 画像に対する結果であり 下段は最も低い検出率を得た テスト画像に対する結果である.左は図 4.11のモデルを用いて遅延探索を行った結 果であり，右は 3.6.4節のモデルを使用し，第3章のアルゴリズムによ って検出した 結果である.
X
X
¥
/〆
¥ ︑
へ
ノ/ / ¥ ¥ ¥ ¥/ / / / ¥ ︿
/ f / ¥ ¥ ¥ ¥
/ / /
f '
¥ ¥
X
(b) noise‑distorted image (SNR: 9.0 [dB])
了'
図.J:.13:テスト 画像の例(̲¥"= 6.J:j T'二256)
本章で提案したアルゴリズムによる平均実行時間は，ビームサーチを行わない場 合のl.1X 102秒に対し，ビームサーチを行った場合(入二 1300)ではl.0x 10秒と なった.一方，第3章のアルゴリズムでは，ビームサーチを行わない場合， 2..J: x 10
秒，ビームサーチを行った場合(入=500)では.J:A秒であった.なお，これらの入は 予備実験により決定したものである.
以上の実験結果より，遅延を伴う軌跡群の検出において，本章で提案したアルゴ リズムが第3章 の ア ル ゴリズムに比して，検出精度に関する相対的優位性を持つこ とが確認できた.
4.6.5 遅延を伴う 3 本の正弦曲線の検出
図.J:.13(b)に例示したようなテス ト画像100枚に対して，遅延を伴う 3本の正弦 曲 線 の 検 出 実 験 を 行 っ た . こ れ ら の 入 力 画 像 中 か ら
T
= 200の3本 の 軌 跡 を 検 出 する.表4.2:遅延を伴う 3本の正弦曲線のための記号辞書(台形波近似)
出力記号 元 数 個 別 基 本 動 作 相 互 基 本 動 作
η 軌 跡 1(:rd 軌 跡 2
( : r
2) 軌 跡 3(勺) (.1'1，
:1'2) (.i2，
.1':3)a 3 に 01'?~ γ→ 01' ?~ '1¥. S戸乙 5= 01' S>
3 γ「 γ→ 01' 'l'̲， s';::::，
C 3 γ→
d 3 1・→ 01'γノ s';::::，
e 3 γ→ 01'γ/ γ→ 01'γ/ γ/ s';::::， 5= 01・S<
a 軌跡 1，2はともに単調減少または水平，軌跡3は単調減少，軌跡 1，2の間の関係 はほぼ平行，軌跡2，3の聞の関係は平行または間隔縮小
b:軌跡 1，2はともに水平，軌跡3は単調減少または水平，軌跡2，3の問の関係はほ ぼ平行
c 軌跡 1，2， 3はともに水平
d:軌跡1，2はともに水平，軌跡3は単調増加または水平，軌跡2，3の間の関係はほ ぼ平行
e 軌跡1，2はともに単調増加または水平，軌跡3は単調増加，軌跡 1，2の間の関係 はほぼ平行，軌跡2，3の聞の関係は平行または間隔拡大
e
図 4.14: 3本 の 正 弦 曲 線 の 検 出 に 用 い る F8Aモデル(台形波近似)(8:初期状態ー C
，
D，
E:最終状態、)X x3
d2+1
(i) highest tracking rate case d2=6，d3=ー5，TR: 96.80/0 MSE: 0.007
X x3
21 fv 3
x x d
十T
d2十1
(ii) lowest tracking rate case d2=7， d3=‑4， TR: 90.20/0 MSE: 0.031 図 4.15:検出軌跡の例(̲/¥
=
64， T=
200)2元基本動作 1および 2は，それぞれ:rlと 乃 の 聞 の 関 係 と T2と:r3の聞の関係 とを示している.:rlと.T3の間の関係は省略した.ここでは，振I隔が:r3， :r 2， :1: 1の順 に減衰する 3本の正弦曲線を想定して モデル化を行った.この FSAモデルによ っ て出力される記号列は， (どb*ccl*e、l*cb: *)*である.
遅延の探索範囲を d1= 0，1 :::; d2 :::; 10， ‑10 :::; d3 :::; ‑1とし，ビームサーチに 用いる余裕定数を入二 400とした.この入は予備実験により決定した.図 4.15に軌 跡の検出結果の例を示す.図の上段は 図4.14のモデルを用いた場合にテスト画像 100枚の中で最も検出率が高かったテスト画像に対する結果であり，図の下段は，最
も検出率が低かったテスト画像に対する結果である注3
100枚のテスト画像に対する軌跡、の検出軌跡の平均検出率は 93.1%であった. 100枚のテス ト画像のうち，テスト画像に与えた遅延と同じ遅延量d2二6;d3 = ‑5
検出された3本の軌跡τt(t)(1三t三T)と 2(t)(d2 + 1三t三T+ d2) .T3(t) (d:+ 1 ::;
を得た"田俊は.J3枚(平均検出二十三 93.2M)であり，遅延量rl'2.= i. rl 3;= ‑.Jを得た I!lij像 は32枚(平均検出率93.01;')，遅延量 rl'2.二 5，rl 3;= ‑6を得た間像は 25枚(平均検，
' H
2手03.31;')，であった.いずれも軌跡2と3との聞の遅延量が，rl'2.
ーの=
11となっ ていることからわかるように，軌跡2.3に対しては遅延の検出が成功していると言 えるが，軌跡 1に対する遅延はモデルに吸収されたと考えられる.またそれぞれの画像に対する平均実 行 時間は，ビームサーチを行わない場合の 3.8 X 10.1秒に対し，ビームサーチを行った場合には 6.9X 102秒とな り，約2桁の 高速化となった.
4.7 まとめ
本章では，未知の遅延・位相差を伴う軌跡群を検出するアルゴリズムに関して検 討した.このアルゴリズムは，零遅延状態すなわち遅延による位置ずれの無い場合 の軌跡群を FSλ でモデル化し モデルに最もよく 一 致する軌跡群とその遅延量を 検出するものである.遅延量を最適化パラメータに含めた探索問題を動的計画法で 計算することにより，未知の遅延を伴う軌跡群の検出を可能とした.
正弦曲線を対象とした検出実験を行い 提案したアルゴリズムによって遅延を伴 う軌跡群を検出できることを確認し，ビームサーチの導入により約 1‑‑2桁の高速化 を実現した.また，遅延を伴う方形波を対象として，第 3章のアルゴリズムとの比 較実験を行い，本章で提案したアルゴリズムによ ってより高精度な検出が可能にな
ることを示した.
第3章で用いた方形波モデルと ，本章で用いた方形波モデルのように， 一般に同 の軌跡、に複数のモデル化が可能である.このような場合 最適なモデル化を選却 するという最適設計問題が残されている.