(57)【特許請求の範囲】
【請求項１】
複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、前記ベクトルは、少なくとも１つの画像におけるスケール不変特徴を識別するために、スケール不変特徴を表す、ソフトウェアプログラムを用いてコンピュータが実行する方法において、
i. 選択された参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
ii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iii.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、
iv.  前記特定のベクトルの最適マッチングを、
a.  前記参照点ベクトルと前記特定のベクトルとの間の距離ｄspecificを計算する工程と、
b.  計算された前記距離ｄspecificに最も近い距離ｄを備えたベクトルを持つ１つまたは複数の前記グループを識別する工程と、
c.  前記特定のベクトルに最も近い距離ｄminimumを持つ１つまたは複数の識別された前記グループの中の１つまたは複数の前記ベクトルを識別する工程と、
d.  ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の前記参照点ベクトルから、距離ｄを備えた任意の追加のグループを識別する工程と、
e.  前記インターバルの中のすべてのグループが検討されるまで、工程iv.c.および工程iv.d.を繰り返す工程と、
によって識別する工程と、を備えた方法。
【請求項２】
検討されるべき次のグループは、ｄspecificに最も近い距離ｄを持つ未検討のグループである、請求項１記載の方法。
【請求項３】
前記ベクトルは、多次元である、請求項１または２に記載の方法。
【請求項４】
前記距離ｄ、ｄgroup、ｄspecificおよびｄminimumは、ユークリッド距離、マハラノビス距離、マンハッタン距離、チェビシェフ距離、およびミンコフスキー距離から成るグループの中から選択される距離として計算される、請求項１乃至３のいずれか一項に記載の方法。
【請求項５】
前記距離ｄ、ｄgroup、ｄspecificおよびｄminimumは、ユークリッド距離として計算される、請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
前記参照点ベクトルは、前記データセットの中から選択される、請求項１乃至５のいずれか一項に記載の方法。
【請求項７】
前記参照点ベクトルは、前記データセットの中点として選択される、請求項１乃至５のいずれか一項に記載の方法。
【請求項８】
複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、前記ベクトルは、少なくとも１つの画像におけるスケール不変特徴を次に識別するために、少なくとも１つの画像におけるスケール不変特徴を表す、ソフトウェアプログラムを用いてコンピュータが実行する方法において、
i. 選択された参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
ii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iii.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法。
【請求項９】
少なくとも１つの画像におけるスケール不変特徴を識別するために、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするために使用される、請求項８記載の方法であって、
iv.  前記特定のベクトルの最適マッチングを、
a.  前記参照点ベクトルと前記特定のベクトルとの間の距離ｄspecificを計算する工程と、
b.  計算された前記距離ｄspecificに最も近い距離ｄを備えたベクトルを持つ１つまたは複数の前記グループを識別する工程と、
c.  前記特定のベクトルに最も近い距離ｄminimumを持つ１つまたは複数の識別された前記グループの中の１つまたは複数の前記ベクトルを識別する工程と、
d.  ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の前記参照点ベクトルから、距離ｄを備えた任意の追加のグループを識別する工程と、
e.  前記インターバルの中のすべてのグループが検討されるまで、工程iv.c.および工程iv.d.を繰り返す工程と、
によって識別する工程と、をさらに備えた方法。
【請求項１０】
複数の画素によって画成された原画像において、異なるスケールにわたって安定している画像特徴を識別するための、請求項１乃至９のいずれか一項に記載の方法であって、
a.  程度の異なるボケを前記原画像に適用することによって得られた差分を計算することによって、前記原画像から、多数の差分画像を取得する工程と、
b.  前記多数の差分画像において画素幅極値を配置する工程と、
c.  各差分画像において各画素について画素勾配ベクトルを生成する工程と、
d.  請求項１乃至９のいずれか一項に記載の方法を適用して、ベクトルの方位を、各差分画像に関連付けられた実際の最大および最小幅画素のそれぞれに関連付ける工程と、を備えた方法。
【請求項１１】
複数の画素によって画成された画像におけるスケール不変特徴を識別するための画像処理装置であって、
請求項１乃至１０のいずれか一項に記載の方法を実施するように構成されたプロセッサ回路を備えた、画像処理装置。
【請求項１２】
前記画像処理装置は多数のチップを備え、各チップは、請求項１の工程iv.の前記特定のベクトルの前記最適マッチングの識別の一部を実行するように構成されている、請求項１１記載の画像処理装置。
【請求項１３】
前記画像処理装置は、ＧＰＵ、ＤＳＰ、ＦＰＧＡおよびＡＳＩＣから成るグループの中から選択された少なくとも１つの要素を備える、請求項１１または１２に記載の画像処理装置。
【請求項１４】
前記画像処理装置は、前記参照点ベクトルを記憶するための手段、前記データセットの、記憶された前記ベクトル、前記距離ｄおよびｄgroup、および前記特定のベクトルを受け取るための手段を備える、請求項１１乃至１３のいずれか一項に記載の画像処理装置。
【請求項１５】
コンピュータプログラムであって、前記プログラムがコンピュータ上で実行されたときに請求項１乃至１０のいずれか一項のすべての工程を実行するためのプログラムコード手段を備えた、コンピュータプログラム。
【請求項１６】
請求項１乃至１０のいずれか一項に記載の方法を実行するソフトウェアプログラム。
【請求項１７】
複数の画素によって画成された画像におけるスケール不変特徴を識別するように成された、請求項１６記載のソフトウェアプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最近傍（ニアレスト・ネイバー）を見つけ出すための方法および装置に関する。特に、本発明は、最近傍を見つけ出すために、ベクトルのような多次元データを記憶し、探索し、マッチングすることに関する。この方法は、ＳＩＦＴアルゴリズムの一部として特に有用である。
【背景技術】
【０００２】
米国特許第６７１１２９３号の発明者であるロウエ(Lowe)は、限られた計算量のみを用いて高い確率で最近傍を識別できる最適ビン優先探索法として知られているｋ−ｄ木アルゴリズムの改良を使用した。
【０００３】
米国特許出願公開２０１０／００６７７４５は、ビデオにおけるオブジェクトのクラスタ化および識別のための方法を開示する。特に、この方法は、顔画像の識別に関わる。この方法は、同一人物に関連していると推定されるビデオオブジェクトのクラスターを使用する。新しい画像は、そのクラスターまでの距離が、予め決められた第１閾値距離よりも小さいとき、既存のクラスターに属するものと見なされる。新しい画像は、その距離が、（第１閾値距離よりも小さい）第２閾値距離よりも大きいとき、クラスターの一部になる。
【０００４】
イエ、エル(Ye, L.)等の"Autocannibalistic
and Anyspace Indexing Algorithms with Applications to Sensor date Mining",
Dept. of Computer Science & Eng., University of California, Riverside, USA,
85-96は、変更されたオーチャードアルゴリズムを提供する。ここで、メモリーへの負荷を軽減するために速度が犠牲となる。メモリーを節約するために速度をどれだけ犠牲にするかは、設計上の選択である。しかしながら、いかなる場合においても、アルゴリズムは、最小限のスペースを要求する。オーチャードアルゴリズムにおいて、データセットにおける各アイテムについて、その近傍（ネイバー）の記憶されたリストが計算される。これは、大きなデータセットのための大量のメモリーを必要とする。変更されたオーチャードアルゴリズムにおいて、互いに近接するアイテムの列は、スペースを節約するために削除される。かくして、探索アルゴリズムは、メモリースペースのために速度を犠牲にする。イエ(Ye)等は、さらに、アルゴリズムを最適化するための動的メモリー割当てを提案する。
【０００５】
ビダル・ルイズ、イー(Vidal Ruiz, E.)の"An algorithm for finding nearest neighbours in
(approximately) constant average time", Patten Recognition Letters 4
(1986), 145-157は、ほぼ一定の平均時間計算量において（即ち、データセットサイズとは無関係に）、所定のサンプルの最近傍を見つけ出すためのアルゴリズムに関する。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
最近傍探索問題（近接探索としても知られている最近傍探索、類似探索、または最近接点探索）は、多くの適用分野で生じている。適用分野としては、これらに限定される訳ではないが、パターン認識（特に工学文字認識）、統計分類（ｋ近傍法）、コンピュータビジョン、データベースにおける内容型画像検索、符号理論、データ圧縮、レコメンデーションシステム、インターネットマーケティング、ＤＮＡシーケンシング、スペルチェック（正しいスペルの提示）、剽窃検知、プロスポーツ選手のキャリアパスを予測するための類似スコア、クラスター分析（通常はユークリッド距離に基づいて、同じクラスターにおける観察が、ある意味で類似するように、サブセット、即ちクラスターの中に観察のセットを割り当てること）、多変量密度推定およびパターン分類、および機会学習が含まれる。
【課題を解決するための手段】
【０００７】
本発明の発明者は、探索時間を短縮することができ、追加的に探索時間を短縮することを可能にしつつ、更に容易に並行処理に適合できる方法を考え出した。
【０００８】
本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法に関し、この方法は、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程であって、
a.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する、工程と、
iv.  前記特定のベクトルの最適マッチングを、
a.  前記参照点ベクトルと前記特定のベクトルとの間の距離ｄspecificを計算する工程と、
b.  計算された前記距離ｄspecificに最も近い距離ｄを備えたベクトルを持つ１つまたは複数の前記グループを識別する工程と、
c.  前記特定のベクトルに最も近い距離ｄminimumを持つ１つまたは複数の識別された前記グループの中の１つまたは複数の前記ベクトルを識別する工程と、
d.  ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の前記参照点ベクトルから、距離ｄを備えた任意の追加のグループを識別する工程と、
e.  前記インターバルの中のすべてのグループが検討されるまで、工程iv.c.および工程iv.d.を繰り返す工程と、
によって識別する工程と、を備える。
【０００９】
当業者は、本方法がマトリクスおよびテンソルにも適合可能であることを理解するであろう。
【００１０】
より良いマッチングのための探索が、並行処理に適合可能である。
【００１１】
当業者は、さらに、この方法が、第２の最良適合、第３の最良適合等を見つけ出すために容易に適合可能であることを理解するであろう。
【００１２】
本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、前記ベクトルは、少なくとも１つの画像におけるスケール不変特徴を識別するために、スケール不変特徴を表す、方法において、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程であって、
a.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する、工程と、
iv.  前記特定のベクトルの最適マッチングを、
a.  前記参照点ベクトルと前記特定のベクトルとの間の距離ｄspecificを計算する工程と、
b.  計算された前記距離ｄspecificに最も近い距離ｄを備えたベクトルを持つ１つまたは複数の前記グループを識別する工程と、
c.  前記特定のベクトルに最も近い距離ｄminimumを持つ１つまたは複数の識別された前記グループの中の１つまたは複数の前記ベクトルを識別する工程と、
d.  ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の前記参照点ベクトルから、距離ｄを備えた任意の追加のグループを識別する工程と、
e.  前記インターバルの中のすべてのグループが検討されるまで、工程iv.c.および工程iv.d.を繰り返す工程と、
によって識別する工程と、を備えた方法に関する。
【００１３】
本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iv.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。
【００１４】
この特徴は、データセットの中からの特定のベクトルの迅速な次のマッチングを可能とする。
【００１５】
本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、前記ベクトルは、少なくとも１つの画像におけるスケール不変特徴を次に識別するために、少なくとも１つの画像におけるスケール不変特徴を表す、方法において、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iv.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。
【００１６】
本発明の一つの態様によれば、それは、複数の画素によって画成された原画像において、異なるスケールにわたって安定している画像特徴を識別するための方法であって、
a.  程度の異なるボケを前記原画像に適用することによって得られた差分を計算することによって、前記原画像から、多数の差分画像を取得する工程と、
b.  前記多数の差分画像において画素幅極値を配置する工程と、
c.  各差分画像において各画素について画素勾配ベクトルを生成する工程と、
d.  請求項１乃至９のいずれか一項に記載の方法を適用して、ベクトルの方位を、各差分画像に関連付けられた実際の最大および最小幅画素のそれぞれに関連付ける工程と、を備えた方法に関する。
【００１７】
本発明の一つの態様によれば、それは、複数の画素によって画成された画像におけるスケール不変特徴を識別するための画像処理装置であって、本発明による方法を実施するように構成されたプロセッサ回路を備えた、画像処理装置に関する。
【００１８】
本発明の一つの態様によれば、それは、本発明による方法を実行するソフトウェアプログラムに関する。
【００１９】
本発明の一つの態様によれば、それは、コンピュータプログラムであって、前記プログラムがコンピュータ上で実行されたときに、方法に関する請求項のいずれか一つのすべての工程を実行するためのプログラムコード手段を備えた、コンピュータプログラムに関する。
【００２０】
本発明の一つの態様によれば、それは、コンピュータプログラム製品であって、前記プログラム製品がコンピュータ上で実行されたときに、方法に関する請求項のいずれか一つの方法を実行するためのコンピュータ読取り可能な媒体上に記憶されたプログラムコード手段を備えたコンピュータプログラム製品に関する。
【００２１】
追加的な態様および実施形態を以下に示す。
【００２２】
本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iv.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、
v.  前記特定のベクトルの最適マッチングを、
a.  前記参照点ベクトルと前記特定のベクトルとの間の距離ｄspecificを計算する工程と、
b.  計算された前記距離ｄspecificに最も近い距離ｄを備えたベクトルを持つ１つまたは複数の前記グループを識別する工程と、
c.  前記特定のベクトルに最も近い距離ｄminimumを持つ１つまたは複数の識別された前記グループの中の１つまたは複数の前記ベクトルを識別する工程と、
d.  ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の前記参照点ベクトルから、距離ｄを備えた任意の追加のグループを識別する工程と、
e.  前記インターバルの中のすべてのグループが検討されるまで、工程v.c.および工程v.d.を繰り返す工程と、
によって識別する工程と、を備えた方法に関する。
【００２３】
ｄspecific−ｄminimumはゼロよりも小さいかも知れないので、ゼロおよびｄspecific−ｄminimumの大きい方を採用する必要がある。
【００２４】
好ましくは、インターバル全体が使用され、このインターバル全体は、i) ゼロおよびｄspecific−ｄminimumの大きい方、およびii) ｄspecific＋ｄminimumの制限値の前記参照点ベクトルからの距離を持つグループを含んでいる。好ましさではより劣る方法において、良好な候補が求められる場合にのみ、例えば時間を節約するために、このインターバルの中のグループのみが使用される。
【００２５】
より良いマッチングが識別されるにつれて、距離ｄminimumが短くなる。故に、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルがより短くなり、検討すべき追加のグループの数が減少する。
【００２６】
より良いマッチングのための探索が、並行処理に適合可能であり、例えば、ｄspecificよりも短い距離ｄを持つグループについて、およびｄspecificよりも長い距離ｄを持つグルーブについて独立に、探索が実施されるかも知れない。そのような独立の探索は、これまでに識別された最短距離ｄminimumについて適切に比較し、それに続いて分配することを可能とする。
【００２７】
この方法は、さらに、第２の最良適合、第３の最良適合等を見つけ出すために容易に適合可能である。
【００２８】
本発明の一つの実施形態によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、前記ベクトルは、少なくとも１つの画像におけるスケール不変特徴を識別するために、スケール不変特徴を表す、方法において、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iv.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、
v.  前記特定のベクトルの最適マッチングを、
a.  前記参照点ベクトルと前記特定のベクトルとの間の距離ｄspecificを計算する工程と、
b.  計算された前記距離ｄspecificに最も近い距離ｄを備えたベクトルを持つ１つまたは複数の前記グループを識別する工程と、
c.  前記特定のベクトルに最も近い距離ｄminimumを持つ１つまたは複数の識別された前記グループの中の１つまたは複数の前記ベクトルを識別する工程と、
d.  ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の前記参照点ベクトルから、距離ｄを備えた任意の追加のグループを識別する工程と、
e.  前記インターバルの中のすべてのグループが検討されるまで、工程v.c.および工程v.d.を繰り返す工程と、
によって識別する工程と、を備える方法に関する。
【００２９】
本発明の一つの実施形態によれば、それは、検討されるべき次のグループが、ｄspecificに最も近い距離ｄを持つ未検討のグループである、方法に関する。未検討のグループとは、そのグループのベクトルが、ｄminimumよりも特定のベクトルに近いベクトルの識別のための検討が未だ行われていないグループである。
【００３０】
これに代えて、探索は、例えば、ｄspecificに最も近い距離ｄを持つグループからスタートし、未検討のグループの中を下降しまたは上昇するように行われるかも知れないし、或いは、好ましくは、並行処理を用いることによって、下降と上昇が同時に行われる。
【００３１】
本発明の一つの実施形態によれば、それは、ベクトルが少なくとも１つの画像の中の特徴を表す、方法に関する。
【００３２】
本発明の一つの実施形態によれば、それは、ベクトルが少なくとも１つの画像の中のスケール不変特徴を表す、方法に関する。
【００３３】
本発明の一つの実施形態によれば、それは、少なくとも１つの画像の中のスケール不変特徴を識別するために使用される方法に関する。
【００３４】
本発明の一つの実施形態によれば、それは、ベクトルが多次元である、方法に関する。
【００３５】
本発明の一つの実施形態によれば、それは、前記距離ｄ、ｄgroup、ｄspecificおよびｄminimumは、ユークリッド距離、マハラノビス距離、マンハッタン距離、チェビシェフ距離、およびミンコフスキー距離から成るグループの中から選択される距離として計算される、方法に関する。マハラノビス距離は、距離メトリックスケール不変量を作成するための共分散マトリックスの基づく正規化を意味する。マンハッタン距離は、軸整列された方向のみに従う距離の測定を意味する。チェビシェフ距離は、最も重要なディメンション(dimension）のみが関連すると仮定した距離の測定を意味する。ミンコフスキー距離は、ユークリッド距離、マンハッタン距離、およびチェビシェフ距離を統合する一般化を意味する。
【００３６】
本発明の一つの実施形態によれば、それは、前記距離ｄ、ｄgroup、ｄspecificおよびｄminimumは、ユークリッド距離として計算される、方法に関する。
【００３７】
本発明の一つの実施形態によれば、それは、前記参照点ベクトルがデータセットの中から選択される、方法に関する。
【００３８】
本発明の一つの実施形態によれば、それは、前記参照点ベクトルがデータセットの中点として選択される、方法に関する。
【００３９】
本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法において、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iv.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。
【００４０】
本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、前記ベクトルは、少なくとも１つの画像におけるスケール不変特徴を次に識別するために、少なくとも１つの画像におけるスケール不変特徴を表す、方法において、
i.  参照点ベクトルを選択する工程と、
ii.  前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離ｄを計算する工程と、
iii.  前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離ｄgroupを持つベクトルのグループにソートする工程と、
iv.  その後、２つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第２ベクトルが前記グループの第１ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。
【００４１】
本発明の一つの実施形態によれば、それは、好ましくは少なくとも１つの画像におけるスケール不変特徴を識別するために、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするために使用される方法の特徴に関し、この方法は、
v.  前記特定のベクトルの最適マッチングを、
a.  前記参照点ベクトルと前記特定のベクトルとの間の距離ｄspecificを計算する工程と、
b.  計算された前記距離ｄspecificに最も近い距離ｄを備えたベクトルを持つ１つまたは複数の前記グループを識別する工程と、
c.  前記特定のベクトルに最も近い距離ｄminimumを持つ１つまたは複数の識別された前記グループの中の１つまたは複数の前記ベクトルを識別する工程と、
d.  ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の前記参照点ベクトルから、距離ｄを備えた任意の追加のグループを識別する工程と、
e.  前記インターバルの中のすべてのグループが検討されるまで、工程v.c.および工程v.d.を繰り返す工程と、
によって識別する工程と、をさらに備える。
【００４２】
この実施形態は、この方法の特徴が、最初にデータセットを編成し、続いて各マッチングが急速に完了することを許容するかも知れないことを示す。
【００４３】
本発明の一つの実施形態によれば、それは、複数の画素によって画成された原画像において、異なるスケールにわたって安定している画像特徴を識別するための、本発明による方法であって、
a.  程度の異なるボケを前記原画像に適用することによって得られた差分を計算することによって、前記原画像から、多数の差分画像を取得する工程と、
b.  前記多数の差分画像において画素幅極値を配置する工程と、
c.  各差分画像において各画素について画素勾配ベクトルを生成する工程と、
d.  請求項１乃至９のいずれか一項に記載の方法を適用して、ベクトルの方位を、各差分画像に関連付けられた実際の最大および最小幅画素のそれぞれに関連付ける工程と、を備えた方法に関する。
【００４４】
本発明の一つの実施形態によれば、それは、複数の画素によって画成された画像におけるスケール不変特徴を識別するための画像処理装置であって、本発明による方法を実施するように構成されたプロセッサ回路を備えた、画像処理装置に関する。
【００４５】
本発明の一つの実施形態によれば、それは、本発明の画像処理装置に関し、前記画像処理装置は多数のチップを備え、各チップは、特定のベクトルの前記最適マッチングの識別の一部を実行するように構成されている。
【００４６】
本発明の一つの実施形態によれば、それは、本発明の画像処理装置に関し、前記画像処理装置は、ＧＰＵ、ＤＳＰ、ＦＰＧＡおよびＡＳＩＣから成るグループの中から選択された少なくとも１つの要素を備える。
【００４７】
本発明の一つの実施形態によれば、それは、本発明の画像処理装置に関し、前記画像処理装置は、前記参照点ベクトルを記憶するための手段、前記データセットの、記憶された前記ベクトル、前記距離ｄおよびｄgroup、および前記特定のベクトルを受け取るための手段を備える。
【００４８】
本発明の一つの実施形態によれば、それは、コンピュータプログラムであって、前記プログラムがコンピュータ上で実行されたときに請求項のいずれか一項のすべての工程を実行するためのプログラムコード手段を備えた、コンピュータプログラムに関する。
【００４９】
本発明の一つの実施形態によれば、それは、コンピュータプログラム製品であって、前記プログラム製品がコンピュータ上で実行されたときに請求項のいずれか一項の方法を実行するためのコンピュータ読取り可能な媒体上に記憶されたプログラムコード手段を備えたコンピュータプログラム製品に関する。
【００５０】
本発明の一つの実施形態によれば、それは、本発明による方法を実行するためのソフトウェアプログラムに関する。
【００５１】
本発明の一つの実施形態によれば、それは、複数の画素によって画成された画像におけるスケール不変特徴を識別するように成された、本発明によるソフトウェアプログラムに関する。
【００５２】
すべての引用文献は、参照により組み込まれたものとする。
【００５３】
添付の図面および例は、本発明を限定するのではなく説明するために提供される。当業者において、本発明の態様、実施形態、および請求項を組み合わせ可能であることは明らかである。
【００５４】
以下に図面が紹介されており、続いて幾つかの図面がさらに説明されている。
【図面の簡単な説明】
【００５５】
【図１】図１は、データベースサイズの関数としての、予想される探索の数を示す。
【図２】図２は、再編成されたメモリーの図解例を示す。
【図３】図３は、ユークリッド空間における円状の点マッピングの図解例を示す。
【図４】図４は、ソートされたＦＩＦＯロケーション・データ・フィールド
【図５】図５は、拡張されたＦＩＦＯにおけるデータ配列の図解例を示す。
【図５Ｂ】図５Ｂは、データソートプロセスの実施形態を概説する。
【図５Ｃ】図５Ｃは、ベクトルマッチングプロセスの実施形態を概説する。
【図５Ｄ】図５Ｄは、粗いフェッチの実施形態を概説する。
【図５Ｅ】図５Ｅは、細かいフェッチの実施形態を概説する。
【図５Ｆ】図５Ｆは、細かいフェッチの実施形態を概説する。
【図６】図６は、第１のソート法を表すフローチャートを示す。
【図７】図７は、第２のソート法を表すフローチャートを示す。
【図８】図８は、粗いフェッチングおよびデータベクトルマッチング法を表すフローチャートを示す。
【図９】図９は、小さなデータベースのための粗いフェッチングおよびデータベクトルマッチング法を表すフローチャートを示す。
【図１０】図１０は、図９の続きを示す。
【図１１】図１１は、図９の続きを示す。
【図１２】図１２は、図９の続きを示す。
【図１３】図１３は、本発明の方法のための模式的なハードウェア実装例を示す。
【図１４】図１４は、ユークリッド空間におけるマッピングの図解例を示す。参照点ベクトル（矢印１の先端によって示される）が選択されている。図１４において、それは、軸の原点にて示されている。参照点ベクトルまで等距離のベクトルは、一緒にグループ化される。これは、図１４において円で示されており、このグループについての参照点ベクトルからの等距離は、ｄgroupである。マッチングされるべき、参照点ベクトルと特定のベクトル（矢印２の先端によって示される）の間の距離ｄspecificが計算される。ｄspecificに最も近いｄgroupを持つベクトルのグループが選択される。これらの中から、特定のベクトルまでの最小距離ｄminimumを備えたベクトルが見つけ出される。続いて、ゼロよりも大きく、ｄspecific−ｄminimumからｄspecific＋ｄminimumのインターバルの中の距離を備えた未検討のグループのみが検討される必要がある。より小さな最小距離ｄminimumを備えたベクトルが識別されるにつれて、より良いマッチングを識別するために探索が必要となる未検討のグループが少なくなる。
【発明を実施するための形態】
【００５６】
本例は、メモリー要素にてｎ次元データベクトルを組織化し、探索することにより、高速データベクトルマッチングについての本発明の実施形態を実施する方法に関する。この方法は、多次元探索キー（例えば、レンジ探索および最近傍探索）を含む探索のような、幾つかの適用にとって有益である。この方法は、探索をスピードアップするような方法で特別なメモリー・コンストラクションにおいて参照データベクトルを静的に構築し、動的に入力されたデータベクトルをリアルタイムでマッチングすることに依存している。
【００５７】
この方法および本発明は、log2(サイズ)のファクターまでのデータベクトル間のマッチングを見つけ出すためのデータベース内の探索数を潜在的に低減する。ここで、「サイズ」とは、データベクトルの数における参照データベースのサイズである。これは図１に図解されている。
【００５８】
この方法は、ＦＰＧＡおよびＡＳＩＣのようなＧＰＵ、ＤＳＰおよび並列処理ハードウェアにおいて実行され得る。
【００５９】
この方法は、適応性のある加速された探索を可能とする特別の編成に参照データベクトル構築し、来入データベクトルにスキームをマッチングすることによって機能する。この方法は、ソートフェーズ、並びに探索およびマッチングフェーズを含む。
【００６０】
メモリー要素内に任意に編成されたｎ次元参照データベクトルのデータベースを仮定すれば、この方法は、参照データベクトルの中から、マッチングまたは新しく来入データベクトルまでの最近傍参照データベクトルを見つけ出すという問題を解決する。マッチングデータベクトルは、この文脈においては、来入データベクトルまで最小距離（例えばユークリッド距離）を持つベクトルとして定義される。
【００６１】
この方法では、参照データベクトルは、共通の参照データベクトルまでの昇順距離の関数としてメモリー内で最初に再編成される。共通の参照データベクトルは、既存のデータベクトルのセットから、任意または明確な基準のいずれかによって選択される。再編成が終了すると、編成されたメモリーの最初の位置でのデータベクトルは、共通の参照ベクトルまでの最小距離を持つデータベクトルを含む。ソートされたメモリー内の次のアドレスは、参照までの同じ最小距離を持つデータベクトルの残りを、そのようなベクトルが存在する場合にはこれを保持する。さもなければ、これらの昇順アドレスは、共通の参照ベクトルまでの昇順距離を備えた参照データベクトルを保持する。共通の参照までの同じ距離を持つベクトルは、以下の方法にて編成される。すなわち、もしメモリー内のアドレス「Ｘ」が、共通の参照までの距離「Ｙ」を備えたデータベクトル「Ａ」を保持している場合、位置「Ｘ＋１」は、参照データベクトルのデータベクトル「Ｂ」を保持し、このときの参照データベクトルは、共通の参照までの同じ距離「Ｙ」を持ち、同時に「Ａ」までの最小距離を持つベクトル（そのようなベクトルが存在する場合には）である。そして、位置「Ｘ＋２」は、共通の参照までの距離「Ｙ」および「Ｂ」までの最小距離を持つベクトル「Ｃ」を（ここでもまた、そのようなベクトルが存在する場合には）保持する。図２は、ソートされたメモリー編成の図解例を提供する。この図において、点「Ｄ」は、共通の参照までの絶対的な最小距離を有し、それ故に最初のメモリーアドレスに配置されている、単一データベクトルを表している。点「Ｓ」は、共通の参照までの、次に最も短い距離を持つデータベクトルを表しており、以下同様である。この図において、点「Ａ」、「Ｂ」、「Ｃ」は、共通の参照点までの等しい距離を持つ３つのデータベクトルを表している。点「Ｂ」は、「Ａ」によって表される参照データベクトルまでの最も短い距離を持つデータベクトルを表し、同様に、点「Ｃ」は、「Ｂ」によって表される参照データベクトルまでの最も短い距離を備えた参照データベクトルを表している。
【００６２】
ソートを行う際に、繰り返しのデータベクトルが除去される。結果として得られるアレイの中の各データベクトルは、共通の参照点までのその距離と一緒に、同じメモリー位置において、インデックス化および探索を容易にする他のデータフィールドと一緒に保存される。これは図４に例示されている。
【００６３】
上述の方法でデータベクトルが再編成されると、既存の参照データベクトルの中からの、外来データベクトルへの最適マッチングまたは最近傍の迅速な決定が、連続近似法を用いて可能となる。この方法では、共通の参照ベクトルまでの外来データベクトルの距離が最初に計算され、編成されたアレイの中央位置に保存された距離と比較される。計算された距離が、保存された距離よりも小さい場合には、メモリースペースの下半分にて最適マッチングが見つけ出されると推定される。この場合、次の探索は、計算された距離を、メモリースペースの下半分の中央のメモリー位置に保存されたデータベクトルと比較することによって起こる。それとは逆に、計算された距離が、メモリースペースの中央にある保存された距離よりも大きいことが分かった場合には、最近傍は、編成されたメモリーの上半分の位置に見つけ出されると推定される。この場合、次の探索は、計算された距離を、メモリースペースの上半分の中央位置に保存された距離と比較することによって行われる。最後に、計算された距離が、保存された距離に等しい場合は、最近傍は、中央メモリー位置の周囲に保存された参照データベクトルの一つであると推定される。
【００６４】
この方法においては、ｎ次元データベクトルが、粗く保存されており、データベクトルによって表された、単一の、任意に選択された参照点までの距離の昇順にてＦＩＦＯの中に保存されている。かくして、図３の例に示されているように、すべての参照データベクトルが共通の参照点までの距離の関数として点にマッピングされたユークリッド空間が生成される。保存された参照点の共通の参照点までのそれぞれの距離は、フェッチングプロセスの際にこれらを再度計算しなければならない事態を回避するために、同じメモリーアドレスにおいて参照点と一緒に随意に保存され、これのコストは、メモリーサイズへの追加的な要求であろう。
【００６５】
参照点は、保存されたデータベクトルの一つであり、かくして、保存されたメモリー要素、例えばＦＩＦＯの中の最初の点は、参照までの最小距離を持つデータベクトルである。保存されたメモリーの中の次のアドレスは、任意に編成され、参照までの次の最小距離を持つベクトルがこれに続く、参照までの同じ最小距離を持つすべてのデータベクトルを保持し、以下同様である。故に、保存されたメモリー内の最後のアドレスは、参照データベクトルまでの最大距離を持つデータベクトルのセットを保持する。図３の例においては、中心参照点の周囲の内側円が、その周囲に、参照までの最小距離を持つデータベクトルを表す点を含んでおり、太い黒い周囲の外側円が、例参照データセットの中から参照までの最大距離のデータベクトルを表す点を含んでいる。
【００６６】
図３に示されているように、参照点までの等しい距離を備えたデータ点は、円の周囲を形成しており、この円は、参照点に中心が置かれており、該距離に等しい半径を備えている。粗いソートに続く細かいソートにおいては、これらの点もまた、以下の方法にて、それらの相互距離の関数としてＦＩＦＯ内に編成される。すなわち、連続メモリーアドレスは、互いに最も近い点を含んでおり、それらの間の最も短い距離によって識別される（例えば、もしアドレス「ｘ」が、共通の参照点までの距離「ｙ」を備えたデータ点「Ａ」を含む場合、アドレス「ｘ＋１」は、「Ａ」まで最も短い距離を持ち、共通の参照データ点まで同じ距離「ｙ」を持つ、データ点「Ｂ」を、そのような点が、マッピングされた参照点のセットの中に存在する場合には、含むであろう（図３参照）。）図６および図７は、粗いソートプロセスおよび細かいソートプロセスをそれぞれ例示している。
【００６７】
粗いソートフェーズおよび細かいソートフェーズは、来入データベクトルとのマッチングのために迅速な探索参照データベクトルを助けるＦＩＦＯ／メモリーおよびデータ構造を提供する。単一の、ソートされたＦＩＦＯ／メモリー位置でのデータ構造が図４に例示されており、結果として得られるＦＩＦＯ／メモリー構造が図５に例示されている。
【００６８】
これらの図によって示されているように、拡張ＦＩＦＯ／メモリー内の各位置は、以下のデータフィールドを含んでいる（下線付与）：
データ・ベクトル・フィールド
参照点から成るｎ次元データベクトルを表すデータフィールド。
【００６９】
距離フィールド（随意）
本明細書中で共通の参照点と呼ばれている、選択された共通の参照データベクトルまでの特定のデータベクトルの計算された距離を表すデータフィールド。これは、随意のフィールドである。これは、メモリーサイズへの要求を軽減するために除去することができる。除去された場合には、オンザフライで必要に応じて距離が計算される。
【００７０】
サイズ／インデックスフィールドおよび繰返しフラグフィールド
サイズ／インデックス（ｓｚ／ｎｄｘ）フィールドは、サイズまたはインデックスを表す２つの値のうちの１つを含む。ＦＩＦＯ／メモリー位置が、距離フィールドにて与えられた距離を備えた最初のデータベクトルを含む場合、フィールドは、共通の参照までの同じ距離を持つデータベクトルセットのサイズを表す値を含むか、さもなければ、フィールドは、参照までの同じ距離を備えた連続データベクトルの増大されたインデックスを表す数を含んでいるだろう。
【００７１】
繰返しフラグフィールドは、距離フィールドが以前のＦＩＦＯ位置から繰り返される場合に「１」にセットされ、それ以外は「０」にリセットされるフィールドである。図５の例において、アドレス「０００００」でのサイズ／インデックスフィールド内の数「３」は、選択された参照点までの距離「ｘｘｘｘ」を持つ参照データベクトルの全体の数が３つであることを示している。アドレス「０００００」での繰返しフラグフィールド内の「０」は、データベクトルフィールド内のデータベクトルが、参照点までの距離「ｘｘｘｘ」を持つＦＩＦＯ内の最初のものであることを示している。アドレス「００００１」において、繰返しフラグは、この位置でのデータベクトルが、参照点まで、先行するアドレス（この場合は「０００００」）でのデータベクトルと同じ距離を持っていることを示すために、「１」にセットされ、サイズ／インデックスフィールド内のインデックス値「１」は、手元にあるものと同じ参照までの距離を備えた参照データベクトルを持つＦＩＦＯ内の以前の位置が１つのみであることを示し、アドレス「００００３」での値「３」は、このアドレスでのデータベクトルと同じ参照点までの距離を持つ参照データベクトルを保存する、以前のＦＩＦＯ位置が、全体で３つであることを示している。
【００７２】
来入データベクトルの、共通の参照点までの距離は、オンザフライで計算され、ソートされたＦＩＦＯ内の保存された距離と粗く比較され−或いは、ここでもまたオンザフライで計算され−、来入点を取り囲むかも知れない円の周囲に最も近い円周囲を見つけ出す。最も近い円周囲は、図８のフローチャートによって例示されたように見つけ出される。同図においては、以下の略語が使用されている。
【００７３】
・Ａｄｄｒ．：用語ＦＩＦＯアドレスを短縮したもの。
【００７４】
・Ｓｔｒｔ．：スタートの略語である（即ち、「ｓｔｒｔ  Ａｄｄｒ」は、ＦＩＦＯ内の探索スタートアドレスであるスタートアドレスの略語である。Ｅｎｄ  Ａｄｄｒ．は、探索エンドアドレスである）。略語「ｓｔｒｔ」が単独で使用される場合、それは探索スタートアドレスを意味する。
【００７５】
・Ｅｎｄ：探索エンドアドレスを意味する。
【００７６】
・Ｄｉｓｔ：距離（ディスタンス）の略語である。
【００７７】
・Ｅｕｃｌ．：ユークリッドの略語である。図において、ユークリッド距離が例として使用されており、「Ｅｕｃｌ．Ｄｉｓｔ．」のように示されている。
【００７８】
・Ｒｅｓ：結果（リザルト）の略字である。図において、ｒｅｓはレジスターとして扱われている。
【００７９】
・Ｃｒｎｔ．：現在（カレント）を意味している。この略語が単独で使用される場合、それは現在のＦＩＦＯアドレスを意味する。
【００８０】
・Ｎｄｘ．：インデックスの略語であり、本明細書中で先に説明したように、ｎｄｘデータフィールドによって表されるインデックスを意味している。図５参照。
【００８１】
・Ｒｅｖ．：用語リバースの略語である。ここで、ｒｅｖ．はフラグであり、セット時にＦＩＦＯからの読み込みが現在の円の最後の点から起こるようにする。図３を参照すれば、それは点「Ｄ」であろう。ここで、このアイデアは、比較点の無関係を飛び越える。
【００８２】
・Ｒｄ．は読み込み（リード）の略語である。ここでは、ＦＩＦＯ読込みアドレスを示すために使用され、ＦＩＦＯ書込みアドレスと区別される。
【００８３】
・サイズは、図５に例示されているように、「ｓｚ」フィールド内の値を参照している。
【００８４】
・繰返しフラグ：これは、図５に例示されているように、Ｒｅｐ．ｆｌａｇの値である。
【００８５】
・最初：これは、粗い探索によって見つけ出される最初のＦＩＦＯ探索アドレスである。
【００８６】
そして、最初は最も近い円周囲および隣接の周囲上の点の中から、来入点までの最小距離を備えた最も近い点を見つけ出すために、比較がリファインされる。図９、図１０、図１１、および図１２は、細かい探索およびマッチングのプロセスを例示している。
付録
ＳＩＦＴ特徴のような画像特徴は、ベクトルによって表されるかも知れない。これは、以下に示す引用によって本付録の中に例示されている。
【００８７】
当業者は、例えば米国特許第６７１１２９３号およびWikipediaから、ＳＩＦＴ法に精通している。米国特許第６７１１２９３号は、「サブ領域記述子のセット(sets of subregion descriptors)」という用語を用いており、Wikipediaは、これに代えて、「記述子ベクトル(descriptor vector)」、「ベクトル(vector)」、「記述子(descriptor)」という用語を用いている。本件特許請求の範囲および明細書の残余部分においては、「ベクトル(vector)」の用語を用いている。
【００８８】
Wikipediaからの引用「スケール不変特徴変換」（以下強調付加）。
【００８９】
キーポイント記述子
以前の工程は、キーポイント位置を特定のスケールにて見つけ出し、それらに方位を割り当てた。これにより、画像位置、スケールおよび回転への不変性を確保する。さて、我々は、イルミネーション、３Ｄ視点などの残余の変量に対して記述子はその弁別性が高く且つ部分的に不変であるように、各キーポイントについて記述子ベクトルを算定することを欲する。この工程は、スケールにおいてキーポイントスケールに最も近い画像上で実施される。
【００９０】
最初に、方位ヒストグラムのセットが、各８ビンを備えた４×４ピクセル近傍上で生成される。これらのヒストグラムは、各ヒストグラムが原近傍領域の４×４サブ領域からのサンプルを含むように、キーポイントの周りの１６×１６領域の中のサンプルの大きさおよび方位の値から算定する。この大きさは、さらに、記述子窓の幅の半分に等しいσを備えたガウス関数によって重み付される。そして、記述子は、これらヒストグラムの値のすべてのベクトルになる。各８ビンを備えた４×４＝１６ヒストグラムがあるので、ベクトルは１２８要素を持つ。そして、このベクトルは、不変性を高めてイルミネーション内の変化をアフィンするために、単位長さに正規化される。非線形イルミネーションの影響を低減するために、０．２の閾値が適用され、ベクトルが再び正規化される。
【００９１】
記述子のディメンション、即ち１２８は、高いように見えるけれど、これよりも低いディメンションを備えた記述子は、マッチングタスクの範囲にわたって同様に機能することができず・・・および、最近傍を見つけ出すために使用される概算ＢＢＦ（下記参照）法の故に演算コストが抑制される。より長い記述子は、より良い働きをするが、ずっと良い訳でなく、歪みおよび閉塞の感度が増大するという追加の危険がある。それはまた、特徴マッチング精度が、５０度までの視点変化について５０％よりも高いことを示している。それ故、ＳＩＦＴ記述子は、小さなアフィン変化に対して不変である。ＳＩＦＴ記述子の弁別性を試験するために、試験データベース内のキーポイントの数を変化させて、マッチング精度もまた測定された。そして、非常に大きなデータベースサイズに対して、マッチング精度は非常に僅かしか低下しないことが示されており、かくして、ＳＩＦＴ特徴の弁別性が高いことが示されている。
【００９２】
米国特許第６７１１２９３号、段落［００７１］の記述からの引用
もし、ブロック１９８において、サブ領域内の対象の最後の点が検討されると、ブロック２０２は、プロセッサー２２に対して、角コンポーネントセットおよびこれらの関連するコンポーネント記述子要素を、領域と関連して保存するように指示する。かくして、各全領域について、８セットのコンポーネントサブ領域記述子が、全数で１２８あり、極値について全領域を表している、ということが分かる。８セットのコンポーネントサブ領域記述子は、画像の１つのスケール不変特徴を表す。・・・
【図１】
0005944406.tif 000002
【図２】
0005944406.tif 000003
【図３】
0005944406.tif 000004
【図４】
0005944406.tif 000005
【図５】
0005944406.tif 000006
【図５Ｂ】
0005944406.tif 000007
【図５Ｃ】
0005944406.tif 000008
【図５Ｄ】
0005944406.tif 000009
【図５Ｅ】
0005944406.tif 000010
【図５Ｆ】
0005944406.tif 000011
【図６】
0005944406.tif 000012
【図７】
0005944406.tif 000013
【図８】
0005944406.tif 000014
【図９】
0005944406.tif 000015
【図１０】
0005944406.tif 000016
【図１１】
0005944406.tif 000017
【図１２】
0005944406.tif 000018
【図１３】
0005944406.tif 000019
【図１４】
0005944406.tif 000020