１ はじめに
レンジデータ[1]におけるＣＡＤ物体のための、モデルをベースにした完全な視覚システムを実現するにあたって、スピードと正確さが認識における２つの必要不可欠な要素となる。これらのファクタはモデルライブラリとシーンクラッター（scene clutter）の増加に伴い極めて重要になってくる。モデルベースの視覚における従来の研究では、認識時間がモデルベースのサイズあるいはシーンクラッターを無視するようなアルゴリズムが設計されていた。[２，４，５，６，７，８，９，１０，１２，１３，２１]
モデルを表現するためのポイントベースの特徴を用いたシステム[４，６，９，１２，１３]は、通常、物体認識のために概念をインデックス化する。オフラインのモデルをコンパイルするプロセスにおいて、インデックスは点（point）のグループから計算され、これらはアドレスとして探索テーブル（look-up table）に使われる。探索テーブルとは、モデルのアイデンティティや点のグループが記憶されている場所である。認識にはシーンポイントのグループからの同様のアドレスからの計算が伴い、その後、これらのロケーションに配置されたモデルの決定が行われる。このアプローチは、いわゆる「幾何学的ハッシュ法」という名で良く知られるようになった。
より高レベルのプリミティブ（primitives）を使ったシステム（例えば面（surface）、立体（volume）など）は、従来グラフという形で、モデルとシーン物体の両方を表現する。[２，７，８，１０]これらのグラフの中のノードは、プリミティブを表し、リンクはそれらの関係性を表す。認識においては、シーングラフのノード間の写像関数と各モデルグラフのノードが確定される。このプロセスは計算機的に複雑（computationally expensive）なので、モデルベース全体に渡ってそれを繰り返すのは、実用的ではない。明らかにより高速のハッシュ法のコンセプトをグラフ理論モデルに拡張することには疑問が残るが、[８，１０]に記述されたシステムはこの方向への確固たる努力の結果である。
従来はnon-graph theoretic methodは大型ライブラリにおいて、スピードパフォーマンスが高いのだが、 我々はグラフ理論的アプローチgraph theoretic approachを開発し続けることを選んだ。この主な理由はグラフ理論的手法（graph theoretic method）では空間的推論（spatial
reasoning）に知能（intelligence）を注入することが可能となり、それによってより魅力的になるからだ。これはつまり表現がより完成され、認識のみのために最適化されていないということだ。graph theoreticモデルを取り入れたシステムは、欠損したあるいは閉塞したパーツについてより自然に推論することができ、またこの研究が提供しているように物体の部分認識をより広域のappearance class の例として許可することができる。
大型ライブラリでも実行可能なグラフ理論的手法を作るためには、我々は[１５，１６]におけるモデルベースの階層組織化を提案する。また、クラスタリングの考え方を使っているのは我々が初めてではない。例えば[１９]を参照せよ。セクション２では、我々のアプローチについて簡潔に述べる。観測されたデータはＰＳＤとして表される。そして対象モデルはＲＰＳＤとして表される。これらは属性グラフ（attributed graph）の形を一般化したものである。組織化されたモデルベースの構造はオフラインで学習されるものだが、認識中に効率的に使うことが可能である。ここでは唯一の指数関数的（最悪な場合）構造（あるいはグラフ）の照合プロセス（matching process）は組織化された木の根におけるシーンＰＳＤとＲＰＳＤの間に存在する。残された作業は手間のかからない一連の線形テストに単純化される。 我々は１００個のＣＡＤ物体のモデルベースの結果をここに表示する。
モデルベースの視覚システムはまた、一からモデルベースを再設計することなく、新しいモデルを受け入れることができなければならない。すでに組織化された階層の中で、新しいモデルＲＰＳＤのサイトを学習するためには、我々は[１５，１６]に記述された認識戦略を拡張する。[１４]における我々の研究は最初にこのアプローチを紹介し、ここではセクション３において述べる。
[１５，１６]で述べた認識戦略上の本質的な問題の１つはシーンＰＳＤと根ＲＰＳＤの間の指数関数的照合プロセスが特にＰＳＤプリミティブ数の高いクラッターシーンにおいて計算が複雑になりうることだ。セクション４ではこの照合時間を大幅に減少させる幾何学的ハッシュ法戦略を紹介する。既存のグラフ理論的モデル用のハッシュ法スキームと比較して（つまり[８]）ここで述べた戦略は[１２]の古典的な幾何学的ハッシュ法スキームに一歩近づいている。我々は以前行った実験を通じて、高速認識におけるこのスキームの持つ可能性を実演する。
２ 高速認識のための組織化したモデルベース
２・１ 構造記述
シーン内で観測された物体はＰＳＤによって、そのモデルはＲＰＳＤによって表現される。パラメトリックな構造記述を使用する際の考え方はＢｏｙｅｒとＫａｋ[３]の論文に従う。それらはまた、[２０]の初期の構造記述と、不正確な照合に関する論文をもとに作られた。
２・１・１ ＰＳＤとは
ＰＳＤとは対の
のことである。
はプリミティブの集合を表し、
は
分のパラメータ的Ｎ項関係（N-ary relations）の集合を表す。例えば３次元の多面体の場合、平面がプリミティブの集合を構成する。集合
はこれらの面の幾何学的関係をキャプチャーする。
プリミティブは属性の数によって特徴づけられ、それぞれが仮定された値を持っている。従って、
各プリミティブ
は直積集合（product set）、
の中で定義される。ここでＡは属性の集合、Ｖは値の集合を表す。例えば先に検討した多面体の場合、表面積(surface area)はプリミティブの属性の１つである。
関係の集合
はプリミティブ間の相互関係を表す。それぞれの関係は３つの部分から成り立つ：ネーム、そのネームによって識別される相互関係を持つタプルの集合、そしてその関係に参加する各タプルの測定を提供するために、タプル上に呼び出されるパラメータ機能。従って
という名の関係の場合
の場合、
ここで
は
番目の関係の名を表し、
はその関係を持つ
項タプルの集合である。ある特定のタプルの要素はそのタプルの構成要素（constituents）と呼ばれることもある。
という用語は
の各タプルに適用されるパラメータ機能を表す。この機能はどんな種類の値でも、数字、記号あるいは論理、スカラーあるいはベクターでもリターンすることができる。例の多面体の場合は、隣接性adjacencyが
番目に名づけられた関係性かもしれない。どんな２つの隣接した平面同士も、
の要素ペアを構成する。パラメータ機能は２つの表面法線 (surface normal) 間の角度の数値を求める。
２・１・２ ＲＰＳＤとは
ＲＰＳＤを呼び出すにあたり、ある単一物体のノイズフリー表現ですらランダム要素を含むことに留意しておこう。モデルはノイズ、視点、articulationおよびintraclass
variationが発するランダム性をキャプチャーしなければならない。
ＰＳＤを定義した時、ＲＰＳＤはＰＳＤで、ここで
Ｇ＝（Ｐ，Ｒ）、Ｐとはランダム・プリミティブの集合、集合Ｒはランダム・パラメータ関係の集合である。
ランダム・プリミティブ：その構造体の中のプリミティブ特性は、属性の集合によって特徴づけられる。ここでそれぞれの値は離散ランダム変数である。ある結果生じる所定のＰＳＤの場合、プリミティブはシーンに全く存在しないかもしれない（つまり取り除かれているということ）。[２３]に従い、我々はこの不確定性を、プリミティブ
と関連した「ゼロの可能性」(probability of nullity)としてモデル化する。ここで
はゼロあるいはダミーのプリミティブを表すために使われる。
ランダムパラメータ関係：ランダム・プリミティブ・セット分のＮ項パラメータ関係では、各タプルのパラメータ値が離散ランダム変数になる。また、各タプルにはゼロの可能性が結び付けられている
。もちろんこれはタプルの全てのプリミティブがあることを仮定した場合だ。
ランダム表現（ＲＰＳＤ）は、演繹的な世界の知識に対応し、一方決定主義的形態（ＰＳＤ）はある特定の観察を表現している。Wongと
Ghahraman[２２]はランダム属性グラフを扱い、エントロピーの計算およびある所定の結果出力の可能性について詳細に示した。この分析結果をＰＳＤとＲＰＳＤにまで拡張するために、我々はプリミティブの属性値が独立したものであると仮定する。例えばプリミティブの色はその長さから独立したものである。また、プリミティブ同士は互いに独立したものであると仮定されている。そして我々は、ある所定の関係内のタプルと関連づけられたパラメータ値は、その関係内の他のタプル、あるいは他の関係内のタプルに割り当てられた値からも独立していると仮定する。これらの仮定の相対的真実性は、正しいシステム設計次第である。
２・１・３ ＰＳＤ Outcome Probability
２・１・４ ＲＰＳＤエントロピー
２・２ ２つのＲＰＳＤの比較
ＲＰＳＤのモデルベースを階層的に組織化するためには、それらの間に定義される非類似測定（dissimilarity measure）が必要である。一般に、この測定においてより近いモデルＲＰＳＤ同士は一緒にグループ化される。以下にマージＲＰＳＤのコンセプトを紹介する。これらはＲＰＳＤ−ＲＰＳＤ非類似測定の計算における重要なステップである。ＲＰＳＤはまた組織木において非終端頂点（nonterminal nodes）を表すためにマージ（マージ）される。２つのモデルＲＰＳＤをマージした結果、両方のモデルを一緒に表す（それらの統合）。その結果representative ＲＰＳＤができる。以下に定義されたＲＰＳＤ−ＲＰＳＤ非類似測定は、このマージの考え方をもとにしている。
２・２・１ ２つのＲＰＳＤのマージ
マージＲＰＳＤを定義するために、我々はマージ属性グラフの考え方を著しく拡張する[２３]。ライブラリの
の２つのモデルにそれぞれ対応するＲＰＳＤを
とする。それらはマージされ、その結果マージされたモデル
にそれぞれＲＰＳＤ
が生じる。マージＲＰＳＤを構築する過程は２つのステージに分けることができる。最初に
と
との間のマッピングを計算し、その結果最小値
が生じる。ＲＰＳＤ−ＲＰＳＤの非類似性は以下に定義される。アルゴリズムの詳細は[１８]を参照。次に、マージされたＲＰＳＤ
は、プリミティブが０である可能性と、マージされたＲＰＳＤのタプルとそれを表現するランダム変数の分布とともに計算し、この写像関数(mapping function)より得られる。
２・２・２ ＲＰＳＤ−ＲＰＳＤの非類似性
２・３ ＲＰＳＤのモデルベースを組織し、使う
２・４ 実験結果
ここで我々は、１００個の３−ＤＣＡＤ物体のモデルベースを考える。この多面体の（物体）の集合は、単純なピラミッド形から、椅子やテーブルなど複雑なモデルにわたる。我々は最初に、「面積」と「形状」のプリミティブなものとして、平面（planar surface）を用い、属性として「ホールカウンタ」を用いて、各物体の構造的表現をそのＣＡＤモデルから構築した。呼び出された（２重の）パラメトリック関係で唯一名前がついているものは「角度」である。そのパラメータ関数
は２つの結合した表面の間の角度を測る。つまり隣り合った表面だけがタプル集合の関係性を形成する。これらの実験において、モデルベースにおけるＲＰＳＤに関連した可能性情報は合成されたもので、実験目的のためだけのものである。つまり厳密な調査に基づいていない。 この理由により、（８０％周辺の）認識率は特別意味を持たない。同様に全てのモデルは同程度の確率があると推定される。
物体の完全な３−Ｄ記述は、認識のためにシステムに提示されると仮定する。従って全てのプリミティブと関係タプルがnullになる可能性は０である。しかし実際のアプリケーションにおいて、物体の
の記述だけしかなく、ＲＰＳＤモデルは視点を変化させながらランダム性をキャプチャーすべきである。我々は、このことを現在進行中の研究で検討している。面積と角度は均一に１０のレベルに量子化される。ＲＰＳＤの構築において面積と角度の値は「離散ガウス分布」としてモデル化されている。これにはＣＡＤ値の平均とランダム値が伴う。形に関しては、表面の境界の回転機能と３〜７面体の規則的なポリゴンのそれとの間の距離を計算する。面に最も近いレギュラーなポリゴンはＰＳＤにおいて上記の測定距離に基づき属性の形状を表す。（ＲＰＳＤにおいて）これらの量をランダム変数としてモデル化するために、これらの構造の逆数は足し合わせて１つの値にして確率値として使われた。「ホールカウント」は面の穴の数を記録する。この属性に関するランダム性は仮定されていない。
先に述べたように、同種のモデルベースを構造的に組織化する時、スピードアップの比率は理論上のそれに近似する。従って、これらの実験において我々はモデルを３つのクラスにグループ分けした。モデルは１５以上、１０〜１４、１〜９のプリミティブでそれぞれ２８，３７，３５モデルであった。これは構造的な同種性に関するシンプルな実験的概念に対応する。我々は公式を用いてグループにおける各々のＲＰＳＤのペアをそのように非類似的にクラスタリングした後、それぞれのグループを別々に組織化した。図５・２は３番目のサブモデルベースための組織化された木の部分を表している。この時点で最適性を査定することは不可能だが、モデルレンダリングから見て、クラスタリングが合理的であることは一目瞭然である。予想されたように、階層が上がっていくにつれ、クラスタの「ゆるさ」の測定値が増加した。
認識において最初の段階は観測されたＰＳＤにおいてプリミティブ数に従い正確なサブモデルベースを選択することである。先に議論したように、その後認識がなされる。図５・３は４つの異なる物体の非構造化されたケースと組織化による、認識によるスピードアップを比較したものを示している。テストにおける小さなモデルベース（５〜２０の物体）はプリミティブカウントと同様、構造的にも比較的同種である。一方、大きいものはより多様化している。モデル３のプロットではこのレンジで得られたスピードアップ比率は実際、理論上予測されたものよりも大きい。モデル２とモデル３のプロットにおける減少傾向は、プリミティブ数が小さい物体を取り入れた結果である。これらのプリミティブは、組織化されたモデルベースに対して実行しなければならない大型（かつ増加し続ける）根の照合（root match）が簡単にできる。理論上予測されたより総スピードアップが少ないのはこのためである。最後に３５モデル以上のモデルベースのグラフが正の傾斜になっているのは、完全なモデルベースをプリミティブ数で前もってソートした結果である。
３ Incremental Model-base Updating
モデルベースを組織化するプロセスは、オフライン接続で行われる。しかしながら、それは不可能なほど計算量が多い。なぜなら、
l
のＲＰＳＤ−ＲＰＳＤ照合プロセスが存在し、各々がＲＰＳＤプリミティブの数において最悪の場合、指数関数的になる。
l
階層化されたクラスタリングプロセスのそれぞれの層は、ＮＰ完全性（ＮＰcomplete clique-finding
process） を含む。
l
各々の層の（cluster representatives）はいくつかの子ＲＰＳＤをマージして形作られる。マージによって、ＲＰＳＤプリミティブの数が指数関数的に複雑になる。
新しいモデルＲＰＳＤがライブラリに加えられるとき、サイズが
ライブラリのための、複雑で完全に組織化されたプロセスの繰り返しは避けた方が良い。さらに、
モデルライブラリを組織化する際になされた仕事は破棄されてしまう。従って、既存の階層の中で新しいモデルの位置を学習するのが良い。
３・１ 新しいモデルの位置の学習
新しいＲＰＳＤモデルを階層の中に配置するためには、まずライブラリの中に既に存在するモデルの中でそれにもっとも類似したもの[2]を探す。これはシーンＰＳＤに最も近いモデルＲＰＳＤを見つけるという認識のプロセスと同一のものである。我々は単に同一の探索プロセスを呼び出すが、木を行き来する際にＲＰＳＤ−ＲＰＳＤ非類似測定値を使う。この方法は更新されたモデルライブラリを一から組織化するよりも著しく早い。
いったん最も近い既存のモデルを明らかにした後は、組織化された木に新しいモデルを正確に配置しなければならない。図５・４はモデル
が９つのＲＰＳＤによる既存のモデルベースに加えられる例を示す。
番目のレベル（
）の場合、各クラスタのモデルのペアは非類似値
（
）の範囲内にある。これは上記のクラスタリングのアルゴリズムによって実行可能である。
が
に最も似ていると仮定した場合、それをインストールする方法は５通りある。もし
と
の非類似性が
より小さければ、図中に示したように２つの選択肢が存在する。今、我々はケース２を選択しているが、ケース１か２のどちらかを自動的に選択するという戦略の決定を検討中である。もしも非類似性値のうち（
と
）の１つが
より大きく、
は
それぞれに関して、
の非類似性値の範囲内であるとすると、その時はケース３が選択される。他のケースの場合はそれに続く。
いったん新しいモデルの正確な位置が推測されると、木の各レベルにおけるクラスター（representation）ＲＰＳＤが、変更される。図５・４のケース３の場合、ＣとＤ（そしてそれ以降）における新しい（cluster representation）は再計算される。しかしこれは木探索の副産物なので、この時点で特に労力を費やす必要はない。各クラスタにある「ノード・ポインタ・リストnode pointer list」も、これに従って修正される。これによってモデルベースに必要な変更が完了する。
インクリメンタル（漸増）モデルクラスタアルゴリズムは、モデルが階層に加えられる順番によって影響を受けると我々は考える。ただしまだ実験を通してこの感度を測定していない。我々が新しいモデルサイトのみについて決定を下しているという点に注意して欲しい。木の
残りの構造はそのまま保持される。例えば図５・４においてケース１を選択したとしよう。モデル
と
を除いた他の全てのモデルとの間の非類似値が
より大きく
より小さい、ということは大いに可能だ。理想的な解は、クラスタ
を現在の位置から取り除き、それをＤの下に置くことである。木の構造におけるそのような調整をしておけば、将来この問題に取り組む際に役立つに違いない。
組織化されたライブラリの質を測定するたに、我々は組織化された階層中の各レベルにおいてinter-,intra-,２つのクラスタモデルの非類似値を考える。ある特定のレベルにおいては、クラスタ間の非類似測定値
は、そのレベルの異なる２つのクラスタに属する２つのモデルの非類似値平均である。同様に、クラスタ間の非類似値
は、特定のレベルにおける同じクラスタに属する２つのモデル間の非類似値の平均を評価する。そのレベルのメリット数（the figure of merit）は、
. （１６）
で表される。
この測定値が低いものは、良いクラスタリングを意味する。この比率は根において定義されず、その葉において０である。ところで、通常階層が上がるに従い
は単調増加するものではない。
３・２ 実験結果
これらの実験は、先に述べたように大きさで分割し、１００個ＣＡＤ物体のモデルベースで行った。パーティションはそれぞれ、２８、３７、３５モデルを有した。
第一のパーティションは、セクション２で述べたクラスタ理論に従い、はじめに直接組織化された。次の２６モデルはアトランダムに選ばれ、ここでもクラスタ理論に従い再び組織化された。集合からの残った２つのモデルは、上で述べたサイト学習（site-learning）のアルゴリズムを使い、加えられた。表５・１（a）はこのサブライブラリに対応する３つの異なるメリット数を示している。木１において、我々は
の値と２８モデルの直接組織化されたライブラリの各レベルの非類似閾値（dissimilarity thresholds）を示す。木２は２８の集合から選ばれた２６モデルの直接組織化された木に対応している。一方、木３は２つの残ったモデルが挿入された後の、修正された木２に対応している。我々は、全てのレベル（最後を除く）の
の平均として、全体の質の測定値を定義することができる。木１と３のこれらの値は、それぞれ０．４３と０．４１である。それゆえこの（不完全な）メリット数によると、木３の全体の質は木１のそれより若干良いものであるといえる。
我々はサブライブラリ２と３の実験を繰り返した。結果はそれぞれ表５．１（ｂ）と（ｃ）の通り。サブライブラリ２において木２は３３個のモデルを含む。木３において、我々は残りの４つをこのグループから挿入した。４つのモデルを入することは、レベル２と３における
値を減らすことになるが木２と３の全体の測定値はそれぞれ０．３７と０．３８である。これはクラスタの質が若干下降したことを意味している。木１は直接組織化された３７モデルの集合に対応している。その全体の質（０．３９）は、木３のそれより若干低いだけだ。
サブライブラリ３の結果も同様の解釈を行うことができる。ここで、木２は３５の集合からアトランダムに選択された１９のモデルの直接組織化されたモデルベースに対応している。木３残った１６の挿入から生じる。木１は直接組織化された３５のモデル集合である。木２と３を比較した時、各レベルにおいて
が増加していく。これは大量のモデルを加えるとクラスタが「ゆるく」なることを示す。木１と３の全体の値はそれぞれ０・３３と０・３７である。木３はモデルの約４５％を漸増的に加算することによって作られたため、それが木１より良いものになるとは期待できない。しかしながら全体的な質の下降は重要でないし、これは非常に希望の持てるものである。
４ 組織化されたモデル・ベースにおける幾何学的ハッシュ法の使用
２・３で論じた物体認識戦略上では、シーンＰＳＤと根ＲＰＳＤ間の指数関数的照合が障害となる。クラッタシーンの場合、観察ＰＳＤのプリミティブ数が高くなり、このために認識プロセスが計算機的な面で複雑になる。従って我々は、高速照合モデルベース組織と併用して使うことのできる幾何学的ハッシュ法を提案する。ここではまずモデルベース内の全ての各ＣＡＤモデルＲＰＳＤにハッシュ配列を構築する。こうすると、組織木の各「葉」にそれぞれＣＡＤモデルＲＰＳＤとハッシュ配列が関連づけられることになる。木の中間ノードにあるＲＰＳＤに対応するハッシュ・テーブルは、そのすぐ下のハッシュ・テーブル同士をマージさせることによって形成される。このマージプロセスは木の根の方までずっと続いていく。
認識中は、根ＲＰＳＤに対応するハッシュ配列によって、シーンプリミティブと根ＲＰＳＤプリミティブ間のいくつかの写像関数の仮説を立てることができる。次に、これらの仮説化された写像関数のそれぞれは、先に定義したシーンＰＳＤ−根ＲＰＳＤの非類似値を計算することによって確証される。非類似値が最少となるものが残される。次に、２・３で論じた木探索
を行なう。図５・５は５つのＲＰＳＤにおける仮説モデルベースの認識過程を表している。ここでシーンＰＳＤはＲＰＳＤ２を最も近い照合とした。
４・１ ＣＡＤモデルＲＰＳＤ用のハッシュ配列の構築
図５・６における状況を考えてみよう。ここでのプリミティブﾞは平面である。面１、２、３が基礎面（basis surface）の集合を形成し、面４・５が追加の決定面(決定面)だと仮定しよう。決定面の幾何学的構造は、決定面の表面法線の
(scalar triple product)と、どれか２つの基礎面を計算することによってキャプチャーすることができる。この２つの基礎面を選ぶ方法は３通りある。ひとつの決定面につき計算されるこれらのtriple
product 値は幾何学的ハッシュ法でインデックスとして使用することができる。
識別法を改善し、かつＲＰＳＤのフレームワークを残すために、我々は基礎プリミティブ triple (basis primitive triple)に 関して第４のプリミティブの幾何学的構造を表現する、quarternary
namedで、秩序ある関係を行使する。検討される３つの面タイプ（平面、円錐形、球形）につき、基礎タイプの選択法が２７通りあり、決定面の選択法が３通りあるため、８１種のquarternaryな関係が可能である。このような関係の名前のひとつが、”BASIS:VOTER
GEOMETRYPLANAR-PLANAR-PLANAR-PLANAR:PLANAR”(B:VG-PPP:P)である[3]。この関係を構成するタプルは（
）である。ここで各
は平面のプリミティブ、（
）は基礎（basis）,そして
は候補プリミティブである。パラメータ・ベクター(
)はタプルの幾何学的構造を表現するが、ここで
Relation
Identifier,
,
,
,
は基礎（
）について候補プリミティブ
の幾何学的構造をキャプチャーしている点に注目して欲しい。これに対して、
は基礎basisそのものの幾何学的構造をキャプチャーしている。この例においては、同等関係（relation
identifier） は“Ｂ：ＶＧ−ＰＰＰ：Ｐ”である。ベクター(
)はハッシュ配列をインデックス化するために使われる。適切な位置でModel ＩＤとbasis triple の入力をする。また、候補プリミティブのアイデンティティ(Model
ID,triple)とともに (
)の位置に配置する。後に分かることだが、いったんシーンbasis triple に対するモデル(basis) triple
を仮説化すれば、照合されていないシーンの表面とモデルの表面を識別するのがはるかに容易になる。
今度は、計算されたハッシュ配列中の位置に、basis surface tripleに関して決定面の物理的な位置が組み込まれていない点に注目して欲しい。例えば図５・６において
は
に並行しているため、それらはハッシュ配列内の同じ位置でtriple（
）のための入力をそれぞれ作り出す。従って、このような多義性を解決するために決定面の新たな位置情報を記憶する必要がある。ここでは、triple
内の最初の表面から決定面（平面あるいは円錐形） の最大距離と最少距離を選択する。従って配列内のある特定のロケーションへの入力は：
となる。ここで、
はこのロケーションでtriple を決定するモデルプリミティブ（決定面）で、
はtriple内の最初のプリミティブﾞから
の最大・最少距離、などなど。このリスト{Ｖ．．．．}はvoting primitive list と呼ばれる。
決定面
が円錐形で（basis triple が全て平面の場合）、
のnormal とのinner productが正になるように円錐の軸の方向を選択することができる。この場合のインデックス化は先に述べた平面決定面s
の場合と似ている。決定面 が球形のpatch の場合、
とはbasis 表面
(……) から（このパッチの所属する）球形の中心までの距離のことである。先の２つのケースとは異なり、位置（β…）において決定面
の位置情報をエントリーすることはしない。何故ならそれはすでに
においてキャプチャーされているからである。ﾌﾟﾘﾐﾃｨﾌﾞの４タプルs (triple に加えて決定面)に関してはあと７８通り可能だ。これらのケース全てを扱うための一貫した方法を明らかにしたが、（単調な）詳細は省略する。
４・２ ハッシュ配列をマージする
根ＲＰＳＤ用のハッシュ配列を構築するためには、階層を創りながら全てのモデルＲＰＳＤのハッシュテーブルをマージする。組織木内のノードのＲＰＳＤの場合、その子ノードchild node のハッシュテーブルをマージする。ここでは
と
という２つのモデルのハッシュ配列をマージし、マージの結果できたモデル
のための配列を創ることを論じる。
我々は、
と
の対応するハッシュ配列の同じ位置内にあるエントリーを組合わせることによって、マージ・モデル
の配列の特定の位置内のエントリーを得ることができるこれらのエントリー内のそれぞれのﾌﾟﾘﾐﾃｨﾌﾞアイデンティティは、
内の対応するﾌﾟﾘﾐﾃｨﾌﾞアイデンティティに合わせて修正される。いったんこれが完了すると、同じtriple に対して２つの別々のエントリーが存在することもありうる。これらは一つのエントリーにとって代わられ、これら２つのエントリーに属するvoting
primitiveリストたちは、各voting primitive がリスト内に一度づつしか現れないように組合せられる。voting primitives と関連したlocational
constraintsは（それがもし存在する場合だが）、子ﾌﾟﾘﾐﾃｨﾌﾞの対応するconstraints から計算される。図５・７には、モデル
と
のハッシュ配列におけるある特定の位置でマージするエントリーの例が示してある。
４・３ シーンＰＳＤ根ＲＳＰＤ照合を確立する
シーンＰＳＤからprimitive basis triple が選択される。我々の目的は、このシーンtriple にうまく照合する根basis
triple を見つけることである。孤立した物体認識の場合はどんな表面triple でも使える。乱雑なシーンの場合、tripleの表面同士は同じ物体に属していなければならない。しかしこのような選択を演繹的に確証するのは無理である。一つの実際的な解決法として、数多くの表面triple
を検討し、良いモデルtriple 照合が得られたものだけを検討する、という方法がある。ハッシュ法という枠組は「乱雑」clutter
問題をうまく解決してくれると我々は考える。また我々は、「乱雑性（clutter）」内で「良質な」表面triple を選択するという課題を現在研究中である。
照合を仮説化する
シーンＰＳＤの中からsurface triple を選択し、シーンに残存する各surfaces については、根ＲＰＳＤのハッシュ配列内の位置を計算し、それに続くものと同じ方法論を使って配列を創る。voting
scene の表面がこのbasis triple に関連したvoting model surfaces のうち少なくとも一つのlocational
constraint を満たせば、この位置に存在するbasis triple はvote を受ける。シーンbasis triple に含まれていなかった全てのシーンプリミティブﾞがvote
した後、vote を集計する。例えば
以上のvote を受けたmodel triple はscene triple のための照合とみなされ、仮説を形成することになる。
照合を確認verifyする
次に、全ての仮設化されたシーンTriple RPSD照合は評価される。それぞれの仮説について、照合されていないシーンプリミティブと根ＲＰＳＤの照合されていないシーンプリミティブの間の写像関数を見つけなければならない。ハッシュ配列はこの目的のために有効に使うことができる。ある照合されていないシーンプリミティブにおいて、ハッシュ配列内でアクセスすべき位置は先に述べたvoting
法で確定される、つまりscene basis triple との幾何学的関係性を割り出すことによって（確定される）。仮説化されたmodel base
triple はこの位置に存在していなければならない、さもなくばこの照合されていないscene surfaceはマップした結果ゼロになる。ハッシュ配列のこの位置においては、仮説化された根ＲＰＳＤbasis
tripleと関連する各voting 根ＲＰＳＤ表面は同じシーン表面と照合する可能性を持っている。
シーン表面の総数を
としよう。シーンbasis triple に含まれない
個の照合されていない各シーンﾌﾟﾘﾐﾃｨﾌﾞにつき、あらゆる可能なモデル表面のリストが確定される。照合されていないI番目のシーンプリミティブについてｍｌI個の可能性があるとしよう。こうして
個の照合を受けていないpossibilityについては、シーンプリミティブとモデルプリミティブの間に[式]個の可能な写像関数を生成することができる。その後、全て（そして唯一）の一対一の写像関数は、
[１５，１６]で論じたＰＳＤ−根ＲＰＳＤ非類似性測量値を使って再評価される。最も低い非類似値を持つ写像関数が選ばれる。この（最少の）非類似値は、そのscene
tripleを根root model triple に照合するための「コスト」と定義される。
全てのtriple 照合仮説のうちで、コスト機能の最も低いものが残される。また、この確認プロセスは、scene triple に含まれていないシーンプリミティブとＲＰＳＤtriple
に含まれていないＲＰＳＤプリミティブ同士を対にする写像関数を提供してくれる点に注意して欲しい。
４・４ 実験的ハッシュ結果
前回のようにパーティションされた、同一１００物体のモデルベースをここで考えてみよう。我々は、３５モデルという最初のパーティションにおけるハッシュ戦略を実行した。ここで
は０と１００の間で均一に量子化される。オフラインの予備処理においては、配列内の過密を減らすために、normal がscalar
triple product of zeroを生成するtripleは無視する。我々は個々のＣＡＤモデルの配列から始め、組織からされたモデル・ベースの根ＲＰＳＤに対応するハッシュ配列ＨＡ１を創った。ハッシュ法と組織化された階層とハッシュ法のみを使った場合の認識の有効性を比較するために、我々は第二のハッシュ配列ＨＡ２を作った。ここでエントリーはライブラリの全てのモデルに対する(model,
triple)ペアである。これは基本的に、同じモデル集合に対する根ＲＰＳＤ配列あるいは「normal」幾何学的ハッシュ法のマージされていないバージョンである。
ＨＡ１内の異なるsurface triples の数はちょうど８３４で、ＨＡ２の７４１６と比較すると９０％近くの減少が見られる。このＣＡＤモデルの集合は多数の表面が直角で交差しているため、ＨＡ２内のロケーションは非常に過密になる。この過密問題はＨＡ１においては軽減される。ハッシュ配列内の各ロケーションで類似したtriple同士がマージするからである。マージされたハッシュ配列は、「規則的regularな」ハッシュ配列よりも分散し、かつ均一に占められている。どちらの属性もスピードと正確さという面からはかなり好ましいものである。
４・４・１仮説生成テスト
我々は図５・８に示したようにサブ・モデルベースの４種の物体の２・５Ｄ表現を生成した。これらは、我々が仮説生成テストを行った４つのシーンである。従って各シーンには一つの物体があり、そのポーズはモデル物体のそれと異なる。しかしながらモデルとシーン物体の間のscale factor はunity である。
表５・２は、あるscene tripleの集合においてＨＡ１，ＨＡ１によって生成された仮説の数で、source image とsurface
identifiers の3-タプルによって識別されたものだ。最初の行にはその幾何学的構造のみを基準に適性を得たmodel triples の数がある。つまり、ここでは同じβ５、β６、β７、β８値を持つ全てのmodel
triples を選び、”voting” surfaces の効果を無視した。次の3行は、それぞれ１，２、３個以上のvote を受けたmodel triple
の数を表す。ここで、決定面s が確認のために仮説の数を呼び込む力を持っていることは明らかである。
５・２
ＨＡ１、ＨＡ２を４つの異なるイメージで使いながら選択されたscene triples 用に生成された仮説の数。最初の行は、その幾何学的構造のみを基準に適性を得たmodel triples の数を示す。次の3行は、それぞれ１，２、３個以上のvote
を受けたmodel triple の数を示す。
図５・８のイメージ１の場合、最初に検討されるscene triple は（0 1 4）である。ＨＡ１を使って２０４個のmodel triples がtriples の幾何学的構造のみを基準に選ばれた。ここで論じられたvoting
method では出発点
の時、数字が１４５まで減少する。
の時、数字はさらに５まで減少する。ＨＡ２を使用している対応数は１７４０、１０７９と５である。この理由は、triple (0
1 4)における表面が互いに垂直で、（０と４に対して垂直の）決定面３ではＨＡ２の過密なロケーションがアクセスされるからである。マ―ジすることによって過密問題が減少されるので、ＨＡ１を使ったvote
数 vt=1はかなり低い。表面２のnormal はわずかに傾斜しているため、ＨＡ１とＨＡ２のハッシュテーブルの分布の低い領域に打ち込まれkey into、これらの数字は表面３のエフェクトeffect
に支配される。
次にイメージ１のbasis triple基底トリプル （２ ３ ４）を検討する。この場合、テストされるべき仮説の数はどの配列の場合も同じである（そして低い）。ここでもその理由は、表面２の傾斜した線のせいで決定面
１と２が強制的にＨＡ１とＨＡ２の分布の少ない場所に打ち込まれるからである。
イメージ２の場合、（ＨＡ２という観点から見て）「友好的な」傾斜表面がないため、scene triple（０ １ ４）あるいは（１ ２ ４）においても、ある基準において生成された仮説の数はＨＡ１を使った場合よりもＨＡ２を使った場合の方がはるかに大きい。この理由もまた、scene
triple がハッシュ配列の過密地帯に打ち込まれるからで、この問題はＨＡ１よりもＨＡ２の方が顕著だ。この例によってもまた、マージされたハッシュ配列の利点が明白になる。表の残りの結果も同様に解釈することができる。
４・４・２ ＰＳＤ根ＲＰＳＤ照合時間の比較
ハッシュ法を使用する主な目的は、認識中のシーンＰＳＤ根ＲＰＳＤ照合時間を減少させることである。ここに示した実験結果は、ハイブリッド法の有効性を示すものだ。全ての作業はＨＰ９０００/７１５ ３３ＭｈｚＲＩＳＣベースのシステムで、Ｃで実施された。図５・８の４つのイメージについては、２・３で示したアルゴリズムを使ったＰＳＤ根ＲＰＳＤ照合は、それぞれ９４．３、９９．４６、１６０．６９と４９．８５ｓ（秒？）かかった。また表５．３では、source
image によって識別されたscene triples 集合用に配列ＨＡ１と３ タプル-surface identifierを使い、ＰＳＤ根ＲＰＳＤ照合時間を示す。ここではvoting
出発点vtがそれぞれ1,2,3の時の構造的根照合structural root matchと比較した場合の照合時間とスピードアップをリストする[4]。当然、スピードアップはvoting出発点ともに増加するが、これはvtの増加に伴う仮説数の減少の結果である。一般には、表５．２の（ＨＡ１での）仮説数とこれらの時間上の結果を簡単に結びつけることができる。より多くの仮説があればより高い確認すべき仕事verification
loadが出てきて、ハッシュ時間も長くなる。
我々はまた、structural およびハイブリッドのmatching schemes の両方において、正しいモデルおよび４シーンのそれぞれにおける正しいポーズが識別されることを確認した。どのmatching
schemeが正確さにおいて優れているのか、（統計的に）判断するためには、幅広いデータにおいてもっと多くのテストを行う必要がある。この時点では、幾何学的ハッシュ法スキームはプリミティブにおいてより多くの幾何学的なrelational
constraints を強要するため、ハイブリッド法の方がよいパフォーマンスをするであろうと我々は推測する。
５ 結論
我々は最初に、組織化した大型モデルベースを組織化するための情報理論のクラスタリングスキーム（information theoretic
clustering scheme）を提案し、一連の計算機的に複雑な構造的照合プロセスをそのような照合１つで置き換えるという風に、組織化された階層が認識中にいかに効果的に使われるかを示した。次に、我々は（incremental model-base
updating scheme）開発した。その中で、新しいモデルは組織化されたツリーにおいて、その位置を学習する。最後に我々は、認識時間をさらに短縮するために、いかにしてハッシュ法のコンセプトが階層化クラスタリングスキームとともに使われうるかを議論した。我々はまた、このハイブリッドスキームが典型的 ”all-at-once（一度に全部）”的 なハッシュテーブルの構築技術よりも、認識中に生じる仮説の数の削減という点において、効果的であるということに関しても言及している。この方法はハイブリッドアプローチに残っている最小木探索（the minimal tree search）を有に補ってくれる。
上記に述べたモデルベースの組織化と物体認識のアルゴリズムは、距離画像からＣＡＤ物体を認識するように目的づけられている。我々の実験結果は、人工的に生じる画像を元にしていたが、現在のアルゴリズムの改良によって、今後現実のシーンに適したものに変えられていくだろうと考えている。例えば、リアルな距離画像が与えられたとき、表面の推定においてエラーが発見されたら、ある３つのプラナーサーフェスについて、（たったひとつではなく）インデックスの集合を計算し、ハッシュテーブルの対応するロケーションにvoteを出す。我々は現在このような方向で、研究を進めている。
[１６]における我々の研究では、モデルベースが構造において十分似通っているとき、階層化されたクラスタリングは高いスピードアップの値を導く。この状態は非常に大型のモデルベース（何千もの物体）に対しては保証できないので、図５・９に示したように全体の形状と大きさの情報を使ってモデルベースを分離しその後各々のパーティションを階層的に組織化することは不可避となる。この方向性での我々の予備研究については[１７]を参照。その論文ではＲＰＳＤから計算された全体の特徴に基づく分割手法を示している。２層組織のもとで、（incremental model base
updating）アルゴリズムは、新しいＲＰＳＤのための最良のパーティションが最初に選ばれ、その後適切な階層でそのサイトを学習するという風に改良可能である。ハッシュ法のコンセプトはまた、図５・９のアーキテクチャに拡張されることもできる。各々のパーティションについて、我々はここで議論したような（root-representative）ＲＰＳＤのためのマージされたハッシュテーブルを作り出す。結果として生じるハッシュテーブルの集合は、認識のために並列に用いられるだろう。我々はこれらのツールが、非常に大型のモデルベースを用いたリアルかつ乱雑なシーンにおいて、効果的な認識を行うことができると考える。