DEIM Forum 2013 E10-2

投影データに対する検索領域指定方法の提案
飛田 雄樹†

片山薫†† 首都大学東京システムデザイン学部 〒 191-0065 東京都日野市旭が丘 6-6
E-mail: †hida-yuki@sd.tmu.ac.jp, ††kaoru@tmu.ac.jp
あらまし

本稿では，X 線撮影や CT スキャン等に利用される投影データによって構築されるデータベースからクエリデータを検索する際，検索領域を指定し検索を行う手法を提案する．我々の提案手法の特徴として，投影データを投影前の元データに復元せずに行えるという点が挙げられる．この手法を用いると，投影データ全体を調べることができる．クエリデータの有無を判断する手法として，位相限定相関法を利用した．
キーワード

投影データ，データ検索，位相限定相関法

Yuki HIDA† and Kaoru KATAYAMA†† Graduate School of System Design, Tokyo Metropolitan University
6-6 Asahigaoka, Hino, Tokyo, 191–0065 Japan
E-mail: †hida-yuki@sd.tmu.ac.jp, ††kaoru@tmu.ac.jp

1. は じ め にエリデータ以外のデータが含まれいたとしても，クエリデータの検索を回転を許容して行うための手法として，検索領域のX 線投影や CT スキャン等では，ラドン変換により得られ限定を提案する．本手法では，検索領域に指定した範囲の投影る投影データを求め，投影データを逆変換することにより投影を，データ検索が行える精度で抽出し，指定範囲にクエリデー前の元データを再構成している．また，ラドン変換を用いたパタが存在するかどうかを，回転を許容して検索することにより，ターンマッチングや物体の姿勢検出は長谷川や坪井らにより提データ検索を行えるようにした．

案されている．[1]〜 [5] これらは投影データでは，画像の回転角

本論文では，まず，2 章で関連研究について述べる．次に，3が平行移動に置き換わることを利用している．また長谷川の提章では回転を許容してデータ検索を行える説明としてラドン変案 [3] による振幅限定対数ラドン変換により，拡大縮小量も垂換の説明を，また検索データの有無判断する手法として用い位直移動に置き換えられるようになった．これらの実験では対象相限定相関法を紹介する．4 章では我々の提案手法を紹介し，物体以外の部分を 0 として実験を行なっている．これはラドン

5 章で実験結果について述べる．最後に 6 章で本研究により分変換が様々な角度で線積分の投影を行うため，対象物体以外のかったことをまとめる．

情報が投影データに含まれてしまうためである．以上のことから，クエリデータ以外の情報が含まれた投影データ内部にクエ

2. 関 連 研 究

リデータが存在するかどうかを回転を許容して検索をする場合，本研究ではラドン変換により得られる投影データを利用しクエリデータが存在する部分のみの情報を抽出する必要がある．て，回転を許容したデータ検索を行った．ここではラドン変換

以下クエリデータに対して，クエリデータとクエリデータ以を使った，2 データ間の回転角推定や拡大・縮小率推定の手法

外のデータで構成されるものを元データとし，元データの投について紹介する．坪井ら [2] はラドン変換と一次元位相限定影データを検索対象とする．ラドン変換によって得られる投影相関を用いた対象物体の位置と姿勢を検出する手法を提案した．

データはその性質上，検索体調のサイズとクエリデータのサイその手法を拡張させ，投影画像を動径に沿って一次元フーリエズが大きくなるにつれ，クエリデータ以外の情報が多く含まれ変換し，振幅成分を抽出し，投影画像を極座標平面で表すことてしまい，位相限定相関関数の相関値が低くなりデータ検索がにより，対象物体の平行移動を不変とし，対数を取ることによ不可能になってしまう．そのためこれまでの手法の多くは，クり拡大・縮小を許容した検出法を長谷川ら [3] が提案した．まエリデータ以外が 0 のものを扱ってきたが，実際にはクエリた，長谷川らは振幅限定対数ラドン変換を用いた足跡画像の照データ以外のデータを含む場合が多く，投影データを用いたク合を行い，SIFT [9] など画像特徴点を検出し，回転，拡大縮小エリデータの検出が難しい．そこで，本研究では検索対象にクに不変な特徴量を算出する手法と比較している．[5] 二階堂らは

歯のレントゲンから歯の歪みやズレの位置合わせを行うために，e−ϕ0 (u,v) は F0 (u, v) の位相スペクトルを表している．

画像をフーリエ変換した際に得られる振幅スペクトルを利用す

F0 (x, y)，F1 (x, y) の相互相関をる手法を提案した．[11] [12] また，回転角や拡大・縮小率推定には平行移動量を推定する手法が必要であり，本研究を含め，多くは位相限定相関法 [10] を用いている．

3. 準C(u, v) =F1 (u, v)F0 (u, v)∗|F1 (u, v)F0 (u, v)∗ |= eϕ0 (u,v)−ϕ1 (u,v)

備(1)とする．F0 (u, v)∗ は F0 (u, v) の複素共役を表す．次に (1) 式

ここでは元データを投影データに変換するラドン変換と，回転角推定に用いる位相限定相関法について紹介する．

を 2 次元逆フーリエ変換することにより位相限定相関関数

c(x, y) を得る．f1 (x, y) が f0 (x, y) を (∆x, ∆y) だけ平行移

3. 1 ラドン変換

動させたデータであるならば，位相限定相関関数 c(x, y) はここでは 2 次元データに対するラドン変換について述べる．

(x, y) = (∆x, ∆y) でピーク値をとるデルタ関数に近い関数となる．そのため，c(x, y) がピーク値をとる座標を求めることに

x 軸，y 軸を角度 θ だけ回転させた座標軸をより，2 つのデータ間の平行移動量が推定できる．

s = x cos θ + y sin θ

4. 提 案 手 法

t = −x cos θ + y sin θとすると，2 次元データ f (x, y) のラドン変換 g(s, θ) は
∫ ∞g(s, θ) =f (s cos θ − t sin θ, s sin θ + t cos θ)dt−∞∫ ∫ ∞=−∞

投影データのデータ検索を行う際に，問題となるのは，検索対象にはクエリデータの他に多くのデータが入っており，ラドン変換により様々な角度で線積分の投影が計算されるため，クエリデータのみの情報を抽出することが難しいことである．こf (x, y)δ(s − x cos θ − y sin θ)dxdyの問題点解説の例として検索対象の投影データを図 2(a)，クエリデータを図 2(b) とする．

により，求められる．本研究の実装では MATLAB を用いており，ラドン変換は図 1 のように各ピクセルを 4 つのサブピクセルに分割し，投影される検出器を計算し，検出を行った．また，◦◦投影は (0◦ <= θ < 180 ) を 1 間隔で行った．

pixel(a) 検索対象の投影データsubpixel(b) クエリデータ

図 2 例に用いた図

図 2(a) は図 3 の投影データであるため，クエリデータの投影 (図 4) の情報も含まれるが，それ以外の図 5(a) の投影デー
タ図 5(b) もラドン変換により足し合わされているため，クエsn+2リデータの正しい検出が不可能である．

sn+1
sn
sn-2

sn-1

θ
図1

ラドン変換

3. 2 位相限定相関法 [10]ある 2 つの 2 次元データ f0 (x, y)，f1 (x, y) が与えられたとき，それぞれの 2 次元フーリエ変換を

F0 (u, v) = |F0 (u, v)|e−ϕ0 (u,v)
F1 (u, v) = |F1 (u, v)|e−ϕ1 (u,v)とする．ここで |F0 (u, v)| は F0 (u, v) の振幅スペクトルを表し，

図 3 図 2(a) の元データ

図 4 図 2(b) の投影

4. 2 検索領域を限定するための重み付け手法
ここでは Algorithm1 の 2〜6 について述べる．例として図 8のような 8 × 8 行列の投影データで構成された検索対象と 4 × 4行列のクエリデータをあげる．ここで，4 × 4 行列のクエリデー
タは検索対象の投影とサイズを合わせるために 0 を付加し，サイズをあわせている．

クエリデータ以外の部分

クエリデータ以外の部分の投影

図 5 クエリデータ以外の部分とその部分の投影

実際に検索対象を図 2(a)，また図 2(b) を 45◦ 回転させている図 6 をクエリデータとし，この 2 つのデータを対象にクエリ

31 32 32 50 36 30 25 4522 33 42 49 36 28 31 25
32 20 36 63 20 47 24 2132 39 30 39 32 37 45 2235 33 31 34 34 42 37 35
20 29 22 52 32 46 36 21
17 19 26 52 39 45 25 1914 25 35 35 39 43 29 3600000000(a) 検索対象 (投影データ)

データの検出を行ったが，図 7 と表 1 から位相限定相関関数の図800000000007114000099920000165300001116000000000000000000(b) クエリデータ

検索対象 (投影データ) とクエリデータ

ピークが立たず，正しく検出が行われていないことがわかる．
図 9 は検索対象の元データであり，中心の 4 × 4 行列にクエリデータがあることがわかる．図 10 は図 8(b) の投影である．
16193812

図 7 重み付けを行わずに

図 6 クエリデータ検索を行った結果

2432467418711419619992597916532352111686515124618245997100000000

図 9 図 8(a) の元データ

07
77000013 29 15 911 25 15 8
10 31 8 1011 18 19 1118 17 16 152 32 16 121 18 27 16
1 9 23 28

図 100000044500000000

図 8(b) の投影

Algorithm1 STEP2，3
表1

相関値グラフ図 7 の詳細な数値
図7回転角

相関値

27◦0.03216

63◦0.03149

152◦0.02436

34◦0.02359

そこで本論文では投影データを用いてデータ検索を行うために，検索領域を限定する手法を提案する．

4. 1 投影データのデータ検索アルゴリズム
検索対象となる投影データ g0 に入力されたクエリデータ f1

次に検索対象全体に 1 を置いた行列 (図 11(a)) と，検索範囲として指定する部分を 1 とした行列 (図 11(b)) を作成する．
1
1111111111111111111111111111111111111111111111111111111111111110000000000000000001111000011110000111100001111000000000000000000(a) 検索対象全体に(b) 検索領域にのみ1 を置いた行列

1 を置いた行列

図 11

全体に対する検索領域の割合を求めるための行列が含まれているかどうかを検索するための手法を Algorithm1にまとめる．

Algorithm 1 提案手法：投影データのデータ検索アルゴリズム
Inputs: 検索対象 g0 ，クエリデータ f1 ，検索範囲
Outputs: 相関値
1: クエリデータの投影データ g1 をとる
2: 検索対象全体に 1 を置き，その投影をとり，それを’A’ とする
3: 検索範囲に指定された部分に 1 を置き，’B’ を作成する
4: C = B/A を計算し，重み’C’ を作成する
5: 検索対象の投影 g0 と’C’ を掛け合わせ，’D’ を作成する
6: ここで’D’ と g1 を 1 次元フーリエ変換により振幅成分を抽出する
7: 振幅成分を抽出した 2 つのデータを用いてデータ検索を行う

8676855388588745896988598915989139887888888911989139874789588
4348547000000000
1110000

432342114575455444344444433344
55000001
1200000000(a) 検索対象全体に(b) 検索領域にのみ1 を置いた行列の投影

1 を置いた投影

図 12

全体に対する検索領域の割合を求めるための投影

Algorithm1 STEP4，5
検索領域を決めると，その領域は投影上ではどの部分にどの程度重みを持つかが計算できる．図 12(b) の例では，行列の数字が大きいほど，重みが大きい．これを利用し，検索領域に指定した範囲の内部にクエリデータが存在するかどうかを検索する．検索を行いたい領域の投影 (図 12(b)) を，全体に 1 を置いた投影 (図 12(a)) で割り，重み行列 (図 13) を算出する．重
み行列を検索対象 (図 8(a)) に掛け合わせることにより，図 14の行列を求めることができる．この行列とクエリデータの投影(a) クエリデータが実際に(図 10) を用いて位相限定相関関数を求めることによりピークの存在している位置
図 16検出が行えるため，データ検索が可能となる．この例では説明(b) 投影データ

検索位置に移動させたクエリデータとその投影の分かりやすさのために，正解領域をそのまま検索領域としたが，実際は回転を許容したデータ検索を行うため，クエリデー

5. 評 価 実 験タのデータサイズより大きい値を検索領域に指定する．
ここでは，提案手法である投影データを用いたデータ検索
00000000.00 .00 .50 .50 .50 .50 .00 .00.00 .13 .33 .56 .50 .33 .00 .00.00 .20 .33 .47 .43 .27 .00 .00.00 .13 .33 .56 .50 .33 .00 .00.00 .00 .50 .50 .50 .50 .00 .00.00 .00 .25 .56 .50 .44 .11 .00.00 .00 .20 .38 .50 .38 .20 .00.00 .00 .11 .44 .50 .56 .25 .00

図 13 重 み 行 列

図 140445000016 25 18 1514 27 18 912 29 9 1310 22 16 1216 17 17 216 29 16 205 20 20 174 16 20 240000045700000000

重みを掛け合わせた行列

アルゴリズムについての評価実験について述べる．本実験では，LENNA(図 3)256 × 256[pixel] を使用した．LENNA の全体をラドン変換により投影データに変換し，その投影データ(図 2(a)) を検索対象とした．また，図 3 の一部を切り取ったものをクエリデータとして様々な条件で実験を行った．

5. 1 重み付けを行ったデータ検索
ク エ リ デ ー タ を 図 6 と し ，ク エ リ デ ー タ の サ イ ズ は ，64 × 64[pixel] である．このクエリデータは図 3 の (96, 96)

Algorithm1 STEP6
ここでは，STEP6 での一次元フーリエ変換について述べる．ク
エリデータを図 3 の (192, 192) から (256, 256) の 64 × 64[pixel]を切り取り 45◦ 回転させた図 15(a) とすると，投影は図 15(b)のようになる．しかし，実際にはクエリデータは図 3 上の中央ではなく右隅にあるため，図 16(a) のように，検索範囲を変更するたびに，投影を計算し直さなくてはならず，処理に多くのから (160, 160) の部分を切り取ったものである．また，クエリ
データは元データに対して 45◦ 回転させている．
検索範囲に指定する範囲サイズは 72 × 72[pixel] とした．表2 の図は重み付けを行いまた検索範囲として正解データを含む範囲で実験を行った結果，図は重み付けを行いまた検索範囲として正解データを含まない範囲で実験を行った結果である．

手間がかかってしまう．その処理を省くために，坪井ら [1] [2]

表 2 相関値グラフの詳細な数値により提案されているラドン変換によって得られた投影データ

図 17図 18を 1 次元フーリエ変換し，振幅成分を抽出する手法を用いた．

回転角相関値

回転角相関値

これにより，クエリデータの平行移動量に不変になることを利

45◦0.0372636◦

0.02233

34◦

0.02281162◦

0.02152135◦

0.01979115◦

0.02127

0.0187641◦

0.02111

用し，検索対象上に存在するクエリデータの平行移動量を無視できるため，検索範囲を変更するたびに，投影を計算し直す手

29◦

間を省いた．実際にクエリデータを中央に置いた場合と，検索範囲に置いた場合の実験結果については 評価実験 5. に示す．

表 2 を見ると，正しい回転角は検出されていないことがわかる．また，相関値のグラフを見てもピークが立っておらず，正しくクエリデータを検出できていないことがわかる．次に，以下にクエリデータを含む範囲を検索範囲とした場合と，クエリデータを含まない範囲を検索範囲とした場合についてまとめる．
表 2 と相関値の図から正しい検索範囲を指定すると，正しい回転角が推定されており，鋭いピークが検出されるため，クエリデータが存在していると判断できる．逆に，正しくない検(a) クエリデータ
図 15(b) 投影データ

クエリデータとその投影索範囲を指定すると，正しい回転角が推定できず，ピークも検出されていないことから，クエリデータは存在しないと判断できる．

図 17 検索範囲にクエリデータを含む場合

図 20

図 16(a) を検索した場合の相関値

表 3 相関値グラフの詳細な数値
図 19回転角

図 20

相関値

回転角

相関値

45◦

0.0411345◦

0.0400846◦

0.0259446◦

0.03230168◦

0.0250444◦

0.0318153◦

0.02375127◦0.02804

5. 3 検索範囲サイズ
ここでは，検索範囲に指定するサイズの限界についての評価実験について述べる．実験には同様に検索対象として図 2(a)，クエリデータとして図 6 を用いた．実験は検索範囲を 66 × 66，
図 18 検索範囲にクエリデータを含まない場合

72 × 72，80 × 80，90 × 90，100 × 100，110 × 110 と変更し，相関値を比べた．相関値をまとめたものを表 4 に示す．

5. 2 平行移動量不変に関する評価実験
ここでは，Algorithm1 STEP6 で，振幅成分を抽出し，平行移動量に不変としていることに関する評価実験について述べ

表 4 検索範囲による相関値の変動

66 × 66

72 × 72

80 × 80

回転角

相関値

回転角

相関値

回転角

相関値

45◦

0.0509445◦

0.0372645◦

0.02860

なくても結果に影響はないということが図 19，図 20，表 3 か40◦

0.0461146◦

0.0298044◦0.02811

らわかる．

39◦

0.0398540◦0.0264340◦

0.027930.0343034◦0.02281135◦

0.02551

る．検索位置を変更する度にクエリデータの投影をとりなおさ38◦

90 × 90

100 × 100

110 × 110

回転角

相関値

回転角

相関値

回転角

相関値

45◦

0.0314935◦

0.0265652◦

0.02564106◦

0.02795

19◦

0.0250346◦

0.0231140◦

0.02484

7◦0.02359169◦

0.0229752◦

0.02283

12◦0.0229055◦

0.02262

表 4 から，検索範囲はクエリデータにより近いサイズのほうが相関値の値が高く，より正解データに近い答えが得られることがわかる．検索範囲が大きくなってしまうと，クエリデータ以外の情報が多く入ってしまうため，正しい答えを得ることができず，データの検索が難しくなってしまう．
図 19

図 15(a) を検索した場合の相関値

5. 4 検索範囲にクエリデータが含まれる割合
ここでは，指定した検索範囲にクエリデータがどの程度含まれていれば検索可能となるかについて述べる．実験として，80 × 80 という検索範囲にクエリデータが 95%，90%，85%，80% の割合で含まれている場合の相関値を表 5 に示す．
表 5 検索範囲による相関値の変動

95%

90%

回転角

相関値

回転角相関値

45◦

0.0302645◦

0.0276544◦0.02498135◦

0.0196517◦0.02419137◦

0.019080.02061

119◦

111◦

85%

0.0189880%

回転角相関値

回転角

相関値

45◦

0.02390137◦

0.0258944◦

0.0215545◦

0.02343141◦

0.02131109◦

0.02267119◦

0.0212444◦

0.02223

表 5 から正しくピーク値が検出されるためには，クエリデー
タの 85% 以上が検索範囲に入っている必要があることがわかる．クエリデータがより検索範囲に含まれているほど，相関値が高くなることがわかる．

6. ま と め
本論文では，投影データで構成された検索対象となるデータベース内部にクエリデータを含むかどうかを回転を許容して検索するための手法として，検索領域指定方法のアルゴリズムを提案した．この手法では検索対象にクエリデータ以外のデータが存在している場合でも，回転を許容してデータ検索を行えるようになった．また，データ検索には検索対象の元データを必要とせず，投影データを逆変換する処理を減らすことができる．
しかし，実験によっては位相限定相関関数の相関値がそれほど高くなく，他の相関値に埋もれてしまい，正しくデータ検索が行われているかどうか判別しづらい実験結果もある．この問題を解消するには，クエリの画素値などを考慮した重み付けのアルゴリズムを今後研究する必要がある．

文

献[1] Tsuboi, T., Masubuchi, A., Hirai, S., Yamamoto,S.,Ohnishi, K., and Arimoto, S., “Video-frame Rate Detection of Position and Orientation of Planar Motion Objects using One-sided Radon Transform”, Proc. IEEE Int.
Conf. on Robotics and Automation, Vol. 2, pp.1233-1238,
Seoul,May, 2001
[2] 坪井 辰彦，平井 慎一 “ラドン変換と一次元位相限定相関を用いた複数物体の平面移動検出”, 電子情報通信学会論文誌 D-Vol.J87-D- No.10 pp1963-1972 2004
[3] M.Hasegawa,“Proposal of pattern matching using log autocorrelation on Radon transform” Proc.International Symposium on Communication and Information Techonologies(ISCIT2007),Oct. 2007[4] 長谷川 誠 “パターンマッチングにおける振幅限定対数ラドン変換法の提案”, 電子情報通信学会論文誌 D Vol.J92-D No.10
pp1720-1722 2009[5] 長谷川 誠，金指 正和，田中 一基，片岡 隆之 “振幅限定対数ラドン変換を用いた足跡画像の照合”, 電子情報通信学会論文誌 D
Vol.J93-D No.11 pp2483-2494 2010[6] 大西 弘之，鈴木 寿, 有本 卓，“ハフおよびフーリエ変換を用いた回転と平行移動の検出”，電子情報通信学会論文誌,D- ，情報・システム， -情報処理，J80-D-2(7)，pp.1668-1675，1997[7] 大西 弘之，鈴木 寿, 有本 卓，“ハフおよびフーリエ変換を用いた拡大・回転・平行移動検出法の部品位置決めへの応用”，日本
ロボット学会誌，Vol.16，No.2，pp.232-240，1998[8] 伊藤 康一，青木 孝文，中島 寛，小林 孝次，樋口 龍雄 “位相限定相関法を用いた掌紋認証アルゴリズム”，MIRU2006[9] D.Lowe,“Object recognition from local scale invariant features”, Proc.ICCV,pp1150-1157,1999.
[10] C.D.Kuglin and D.C.Hines,“The phase correlation image alignment method”Proc.Int Conf. Cybernetics andSociety,pp.163-165,1975.
[11] 二階堂 旭，伊藤 康一，青木 孝文，小菅 栄子，川股 亮太 “位相限定相関法に基づく歯科 X 線写真の高精度位置合わせアルゴリズム”，第 22 回 信号処理シンポジウム，2007[12] A.Nikaido, K.Ito, T.Aoki, E.Kosuge, R.Kawamata“A Dental Radiograph Registration Algorithm Using Phase-BasedImage Matching for Human Identification”,ISPACS 2006