(57)【特許請求の範囲】
【請求項１】
与えられた三次元物体データからポリゴン情報を抽出するポリゴン情報抽出ステップと、
前記ポリゴン情報抽出ステップで抽出されたポリゴンの大きさを決められた一定の大きさ以下にするポリゴン分割ステップと、
前記ポリゴン分割ステップで分割されたポリゴン情報をもとに三次元物体の特徴量を抽出するポリゴン特徴量抽出ステップと、
前記ポリゴン特徴量抽出ステップで抽出された特徴量情報を蓄積する蓄積ステップと、
検索キーを入力する検索条件入力ステップと、
２つの三次元物体の類似度を計算する三次元特徴量情報比較ステップとを有し、
与えられた三次元物体データを蓄積する際には、三次元物体データからポリゴン情報を抽出し、ポリゴンの大きさを一定の大きさ以下に分割し、分割されたポリゴン情報から三次元物体の特徴量を抽出して特徴量情報を蓄積することを特徴とし、
三次元物体を検索する際には、検索キーを入力し、入力された検索キーと蓄積された三次元物体との類似度を計算し、類似した形状を持つ三次元物体を出力することを特徴とする三次元物体データベースの検索方法。
【請求項２】
ポリゴン特徴量抽出ステップにおいて、ポリゴンの面情報から面積を計算し、計算した面積を形状特徴量として抽出することを特徴とする請求項１記載の三次元物体データベースの検索方法。
【請求項３】
ポリゴン特徴量抽出ステップにおいて、ポリゴンの面情報から法線ベクトルを計算し、計算した法線ベクトルを形状特徴量として抽出することを特徴とする請求項１記載の三次元物体データベースの検索方法。
【請求項４】
与えられた三次元物体データからポリゴン情報を抽出するポリゴン情報抽出手順、
前記ポリゴン情報抽出手順で抽出されたポリゴンの大きさを決められた一定の大きさ以下にするポリゴン分割手順、
前記ポリゴン分割手順で分割されたポリゴン情報をもとに三次元物体の特徴量を抽出するポリゴン特徴量抽出手順、
前記ポリゴン特徴量抽出手順で抽出された特徴量情報を蓄積する蓄積手順、
２つの三次元物体の類似度を計算する三次元特徴量情報比較手順をコンピュータに実行させるためのプログラムを記録し、
三次元物体データからポリゴン情報を抽出し、ポリゴンの大きさを一定の大きさ以下に分割し、分割されたポリゴン情報から三次元物体の特徴量を抽出して特徴量情報を蓄積し、
入力された検索キーと蓄積された三次元物体との類似度を計算し、類似した形状を持つ三次元物体を出力する手順をコンピュータに実行させるための三次元物体データベースの検索プログラムを記録した記録媒体。
【請求項５】
ポリゴン特徴量抽出手順において、ポリゴンの面情報から面積を計算し、計算した面積を形状特徴量として抽出することを特徴とする請求項４記載の三次元物体データベースの検索プログラムを記録した記録媒体。
【請求項６】
ポリゴン特徴量抽出手順において、ポリゴンの面情報から法線ベクトルを計算し、計算した法線ベクトルを形状特徴量として抽出することを特徴とする請求項４記載の三次元物体データベースの検索プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、三次元物体データベース、特に形状が類似した三次元物体を検索する三次元物体データベースの検索方法及び三次元物体データベースの検索プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
形状が類似した三次元物体を検索する手法の従来の技術としては、例えば、鈴木一史、加藤俊一、築根秀男：“主観的類似度に適応した３次元多面体の検索”：電子情報通信学会論文誌、Ｄ−Ｉ，Ｖｏｌ．Ｊ８２−Ｄ−Ｉ  Ｎｏ．１，ｐｐ．１８４−１９２，１９９９がある。これは、ポリゴンを用いて表現された三次元物体において、頂点情報を物理的な形状の特徴として用いている。
【０００３】
具体的には、三次元物体を囲む外接直方体を縦・横・高さでｎ等分し、ｎ３  個のセルに分割する。そして、各セルに含まれるポリゴンの頂点の数を数え、その値を全体の頂点数で割って正規化し、その物体の特徴量とする。
【０００４】
以上の方法により、頂点の分布をその物体の形や複雑さを近似した特徴量とすることができ、その特徴量の比較をすることで、２つの三次元物体の形状の類似度を計算することができる。
【０００５】
【発明が解決しようとする課題】
前述した方法では、以下のような問題点がある。
【０００６】
（１）  頂点情報のみを用いた形状特徴量の問題
ポリゴン情報は、「頂点情報」に加え、その頂点がどのように接続されて面を構成しているかという「面情報」を持っている。
【０００７】
しかし、前述の方法では、頂点情報のみを用いて三次元物体の形状特徴を表現しようとするため、図１１（ａ）と図１１（ｂ）に示すように、頂点の位置は同一であっても、それらを接続した面の構成が異なる２つの物体を「同一の形状」と判断してしまう虞がある。
【０００８】
（２）  ポリゴンの大きさに依存した形状特徴量の問題
図１２（ａ），（ｂ）に示すように、２種類の方法で表現された立方体を考える。
【０００９】
図１２（ａ）の立方体は、多数のポリゴンによって、立方体の１つの面を構成している。図１２（ｂ）の立方体は、１つのポリゴンで立方体の１つの面を構成している。
【００１０】
この２つの立方体から、前述の手法で特徴量を取り出す。例として、立方体を縦・横・高さで３等分し、９個のセルに分割する。そして、各セルに含まれるポリゴンの頂点の数を数え、その値を全体の頂点数で割って正規化し、その物体の特徴量とする。
【００１１】
こうして得られた特徴量をヒストグラムで示したものが図１２（ｃ），（ｄ）に示すように得られる。同じ立方体であるにも関わらず、ヒストグラムには大きな差が生じている。図１２（ｂ）の立方体は、面が存在していても頂点が含まれていないセルが多数あるのがその原因である。そのため、この２つの物体は「違う形状」と判断されてしまう虞がある。
【００１２】
本発明は上記の事情に鑑みてなされたもので、形状が類似した三次元物体を精度良く検索することができる三次元物体データベースの検索方法及び三次元物体データベースの検索プログラムを記録した記録媒体を提供することを目的とする。
【００１３】
【課題を解決するための手段】
上記目的を達成するために本発明の三次元物体データベースの検索方法は、与えられた三次元物体データからポリゴン情報を抽出するポリゴン情報抽出ステップと、前記ポリゴン情報抽出ステップで抽出されたポリゴンの大きさを決められた一定の大きさ以下にするポリゴン分割ステップと、前記ポリゴン分割ステップで分割されたポリゴン情報をもとに三次元物体の特徴量を抽出するポリゴン特徴量抽出ステップと、前記ポリゴン特徴量抽出ステップで抽出された特徴量情報を蓄積する蓄積ステップと、検索キーを入力する検索条件入力ステップと、２つの三次元物体の類似度を計算する三次元特徴量情報比較ステップとを有し、与えられた三次元物体データを蓄積する際には、三次元物体データからポリゴン情報を抽出し、ポリゴンの大きさを一定の大きさ以下に分割し、分割されたポリゴン情報から三次元物体の特徴量を抽出して特徴量情報を蓄積することを特徴とし、三次元物体を検索する際には、検索キーを入力し、入力された検索キーと蓄積された三次元物体との類似度を計算し、類似した形状を持つ三次元物体を出力することを特徴とする。
【００１４】
また本発明の三次元物体データベースの検索方法は、前記ポリゴン特徴量抽出ステップにおいて、ポリゴンの面情報から面積を計算し、計算した面積を形状特徴量として抽出することを特徴とする。
【００１５】
また本発明の三次元物体データベースの検索方法は、前記ポリゴン特徴量抽出ステップにおいて、ポリゴンの面情報から法線ベクトルを計算し、計算した法線ベクトルを形状特徴量として抽出することを特徴とする。
【００１６】
また本発明の三次元物体データベースの検索プログラムを記録した記録媒体は、与えられた三次元物体データからポリゴン情報を抽出するポリゴン情報抽出手順、前記ポリゴン情報抽出手順で抽出されたポリゴンの大きさを決められた一定の大きさ以下にするポリゴン分割手順、前記ポリゴン分割手順で分割されたポリゴン情報をもとに三次元物体の特徴量を抽出するポリゴン特徴量抽出手順、前記ポリゴン特徴量抽出手順で抽出された特徴量情報を蓄積する蓄積手順、２つの三次元物体の類似度を計算する三次元特徴量情報比較手順をコンピュータに実行させるためのプログラムを記録し、三次元物体データからポリゴン情報を抽出し、ポリゴンの大きさを一定の大きさ以下に分割し、分割されたポリゴン情報から三次元物体の特徴量を抽出して特徴量情報を蓄積し、入力された検索キーと蓄積された三次元物体との類似度を計算し、類似した形状を持つ三次元物体を出力する手順をコンピュータに実行させるためのものである。
【００１７】
また本発明の三次元物体データベースの検索プログラムを記録した記録媒体は、前記ポリゴン特徴量抽出手順において、ポリゴンの面情報から面積を計算し、計算した面積を形状特徴量として抽出することを特徴とするものである。
【００１８】
また本発明の三次元物体データベースの検索プログラムを記録した記録媒体は、前記ポリゴン特徴量抽出手順において、ポリゴンの面情報から法線ベクトルを計算し、計算した法線ベクトルを形状特徴量として抽出することを特徴とするものである。
【００１９】
【発明の実施の形態】
以下図面を参照して本発明の実施形態例を詳細に説明する。
【００２０】
本発明の三次元物体データベースの検索方法は、ポリゴン情報抽出ステップと、ポリゴン分割ステップと、ポリゴン特徴量抽出ステップと、蓄積ステップと、検索条件入力ステップと、三次元特徴量情報比較ステップとからなる。
【００２１】
前記ポリゴン情報抽出ステップは、三次元物体データから、ポリゴンを構成するために必要な頂点情報と、その頂点がどのように接続されて面を構成しているかという面情報を抽出する。
【００２２】
前記ポリゴン分割ステップは、前記ポリゴン情報抽出ステップで抽出されたポリゴン情報から面の面積を求め、この面積が決められた一定の値以下になるように、ポリゴンを分割する。
【００２３】
前記ポリゴン特徴量抽出ステップは、前記ポリゴン分割ステップで分割されたポリゴン情報をもとに、ポリゴンの面情報に基づく三次元物体の特徴量を抽出する。特徴量は、多次元ベクトルの形で表現する。
【００２４】
前記蓄積ステップは、前記ポリゴン特徴量抽出ステップで抽出され入力された三次元物体を蓄積する。また、抽出したポリゴン特徴量情報から三次元物体へのインデックスを作成し、蓄積する。
【００２５】
前記検索条件入力ステップは、三次元物体を検索するためのキーとなる物体を入力する。
【００２６】
前記三次元特徴量情報比較ステップは、前記検索条件入力ステップで検索キーとして指定された三次元物体と前記蓄積ステップで蓄積された三次元物体とのポリゴン特徴量を比較することにより、類似度を設定し、類似度の高いものを出力する。類似度は、特徴量の多次元ベクトル間の距離が近いものほど高い。
【００２７】
本発明では、三次元物体からポリゴン情報抽出ステップによってポリゴン情報を抽出し、そのポリゴンをポリゴン分割ステップによってポリゴンの面積が決められた一定の値以下になるまで、ポリゴンを繰り返し分割することができる。これにより、次にポリゴン情報から特徴量を抽出する際、もともとの三次元物体を構成するポリゴンの大きさに左右されにくい特徴量が抽出できるようになる。その際、ポリゴンの分割は、１つの面を一定のルールに基づいて分割するだけなので、もともとの三次元物体の形状が失われることはない。
【００２８】
そして、ポリゴン特徴量抽出ステップによって、分割されたポリゴン情報から、
１．ポリゴンの面積
２．ポリゴンの法線ベクトル
を求め、これら物体形状の特徴量を特徴量ベクトルの形で抽出することができる。これにより、精度の高い三次元物体類似度検索が可能になる。
【００２９】
この特徴量ベクトルは、蓄積ステップによってインデックスがつけられデータベースに蓄積される。
【００３０】
検索時には、三次元特徴量情報比較ステップによって、検索キーとして指定された三次元物体の持つ多次元特徴量ベクトルと、蓄積された三次元物体の持つ多次元特徴量ベクトルとの距離を計算し、距離の近いものほど類似度が高いものとしてリスト出力することができる。
【００３１】
【実施例】
この発明の実施例を示す。
【００３２】
［実施例１］
図１は、本発明の実施例１を説明するための構成説明図である。図において、１１は三次元物体検索装置、１２は三次元物体入力装置、１３は表示装置、１４は検索条件入力装置である。
【００３３】
本発明の実施例１では、三次元物体の特徴として、ポリゴンの面積を利用している。
【００３４】
本発明の実施例１の動作は、「三次元物体特徴量抽出フェーズ」と、それを呼び出す「三次元物体蓄積フェーズ」「三次元物体検索フェーズ」で構成されている。以下、各フェーズの動作を説明する。
【００３５】
「三次元物体特徴量抽出フェーズ」
図２は、三次元物体特徴量抽出フェーズの動作を説明するフローチャートである。
【００３６】
まず、ポリゴン情報抽出部１５によって、三次元物体入力装置１２から入力された三次元物体から、ポリゴンの頂点情報と、その頂点がどのように接続されて面を構成しているかという面情報を取り出す。
【００３７】
次に、ポリゴン分割部１６が、ある一定の値Ｓ以上の面積のポリゴンを分割する（Ｓの決定手法の例については後述する）。ポリゴンの分割手法としては、図３に示すように、例えばポリゴンが全て三角ポリゴンの場合、各辺を２等分して新しい頂点を設定し、ポリゴンを４分割するといった手法を用いる。
【００３８】
そして、ポリゴン特徴量抽出部１７で、分割された各ポリゴンの面積分布から特徴量を抽出する。具体的には、次のように抽出する。
【００３９】
１．各ポリゴンの重心と面積を求める。
【００４０】
２．三次元物体を囲む外接直方体を縦・横・高さでｎ等分し、ｎ３  個のセルに分割する。セル毎に変数ｃｉ  （ｉ＝１…ｎ３  ）を用意し、その値を要素とするｎ３  次元の特徴量ベクトルＣ（ｃ１  ，ｃ２  ，…，ｃｎ３）を考える。
【００４１】
３．各ポリゴンの重心がどのセルに含まれるか調べ、該当するＣの次元にそのポリゴンの面積を加算する。
【００４２】
４．全てのポリゴンについて処理したら、Ｃの各次元をポリゴンの総面積で除算し、正規化する。
【００４３】
ところで、特徴量ベクトルの各要素の元になるセルは、三次元物体の外接直方体を縦・横・高さでｎ等分して作られる。この時、あるポリゴンの面が含まれるセルには、そのポリゴンの重心ができるだけ存在していることが望ましい。
【００４４】
図４で簡単に説明する。図４（ａ）のように、分割したセルの大きさに対してポリゴンのサイズが大きいと、面が含まれているのに特徴量ベクトルに反映されないセルが発生する。そこで、例えば、分割するセル直方体の各面のうちもっとも小さいものの面積にするといった手法を用いて、前段で述べたポリゴン分割部１６で分割の指標として用いる面積Ｓの値を決定する。その値を用いて、ポリゴン分割部１６でポリゴンのサイズをセルに対して十分小さくすることで、図４（ｂ）のように、面が含まれるセルにそのポリゴンの重心が存在するようになり、特徴量の精度が向上する。
【００４５】
以上の処理により、三次元物体に対する面積分布の特徴量ベクトルを得る。
【００４６】
「三次元物体蓄積フェーズ」
図５は、三次元物体蓄積フェーズの動作を説明するフローチャートである。
【００４７】
まず、三次元物体入力装置１２を用いて、データベースに蓄積する三次元物体を入力する。
【００４８】
次に、先に説明した三次元物体特徴量抽出フェーズを呼び出し、入力した三次元物体の特徴量ベクトルを計算する。
【００４９】
そして、得られた三次元物体に対する特徴量ベクトルを、蓄積部１８でインデックスをつけ、メモリ１９に蓄積する。
【００５０】
「三次元物体検索フェーズ」
図６は、三次元物体検索フェーズの動作を説明するフローチャートである。
【００５１】
まず、検索キーとなる三次元物体を三次元物体入力装置１２を用いて入力する。
【００５２】
次に、先に説明した三次元物体特徴量抽出フェーズを呼び出し、入力した三次元物体の特徴量ベクトルを計算する。
【００５３】
また、上位何件を検索するかなどといった検索条件を検索条件入力装置１４を用いて検索条件入力部２０に入力する。
【００５４】
そして、得られた検索キーの特徴量ベクトルをもとに、三次元特徴量情報比較部２１が、メモリ１９に蓄積された三次元物体の特徴量ベクトルとの類似距離を計算する。その類似距離が短いものを類似度の高い三次元物体であると判断し、類似度上位のものを検索結果として表示装置１３に出力する。
【００５５】
［実施例２］
次に、本発明の実施例２を説明する。本発明の実施例２の構成は、本発明の実施例１の構成（図１）と同様である。
【００５６】
本発明の実施例２では、本発明の実施例１と比べ、ポリゴンの位置を外接直方体の重心との相対位置で扱っている。そのため、三次元物体特徴量抽出フェーズが以下のようになっている。
【００５７】
「三次元物体特徴量抽出フェーズ」
図７は、本発明の実施例２の三次元物体特徴量抽出フェーズの動作を説明するフローチャートである。
【００５８】
まず、ポリゴン情報抽出部１５によって、三次元物体入力装置１２から入力された三次元物体から、ポリゴンの頂点情報と、その頂点がどのように接続されて面を構成しているかという面情報を取り出す。
【００５９】
次に、ポリゴン分割部１６が、ある一定の値Ｓ以上の面積のポリゴンを分割する。
【００６０】
そして、ポリゴン特徴量抽出部１７で、分割された各ポリゴンから次のように特徴量を抽出する。
【００６１】
１．三次元物体を囲む外接直方体の重心位置ベクトルＧ→を求める。
【００６２】
２．各ポリゴンの重心位置ベクトルｇｊ  →を求める。（ｊ＝１…分割されたポリゴンの数）
３．各ポリゴンの面積ｓｊ  を求める。
【００６３】
４．外接直方体の重心と各ポリゴンの重心とを結ぶベクトルＧｇｊ  →の長さ｜Ｇｇｊ  →｜を求める。
【００６４】
５．｜Ｇｇｊ  →｜の理論上の最大値はＧ→から外接直方体の頂点までの距離なので、その範囲をｍ等分して｜Ｇｇｊ  →｜の値の離散化をする。
【００６５】
→変数ｒｉ  （ｉ＝１…ｍ）を用意し、その値を要素とするｍ次元の特徴量ベクトルＲ（ｒ１  ，ｒ２  ，…ｒｍ  ）を考える。
【００６６】
６．｜Ｇｇｊ  →｜の値がどの範囲に含まれるか調べ、該当するｍ次元の特徴量ベクトルＲ（ｒ１  ，ｒ２  ，…ｒｍ  ）の次元にそのポリゴンの面積を加算する。
【００６７】
７．全てのポリゴンについて処理したら、ｍ次元の特徴量ベクトルＲ（ｒ１  ，ｒ２  ，…ｒｍ  ）の各次元をポリゴンの総面積で除算し、正規化する。
【００６８】
以上の処理により、三次元物体の外接直方体重心に対する各ポリゴンの相対的な面積の分布による特徴量ベクトルを得る。
【００６９】
これ以外のフェーズのフローチャートは、本発明の実施例１の場合と同様である。
【００７０】
［実施例３］
次に、本発明の実施例３を説明する。本発明の実施例３の構成は、本発明の実施例１の構成（図１）と同様である。
【００７１】
本発明の実施例３では、三次元物体の特徴として、ポリゴンの法線ベクトルを利用している。そのため、本発明の実施例１と比べ、三次元物体特徴量抽出フェーズが以下のようになっている。
【００７２】
「三次元物体特徴量抽出フェーズ」
図８は、本発明の実施例３の三次元物体特徴量抽出フェーズの動作を説明するフローチャートである。
【００７３】
まず、ポリゴン情報抽出部１５によって、三次元物体入力装置１２から入力された三次元物体から、ポリゴンの頂点情報と、その頂点がどのように接続されて面を構成しているかという面情報を取り出す。
【００７４】
次に、ポリゴン分割部１６が、ある一定の値Ｓ以上の面積のポリゴンを分割する。
【００７５】
そして、ポリゴン特徴量抽出部１７で、分割された各ポリゴンから次のように特徴量を抽出する。
【００７６】
１．三次元物体を囲む外接直方体の重心位置ベクトルＧ→を求める。
【００７７】
２．各ポリゴンの重心位置ベクトルｇｊ  →を求める。（ｊ＝１…分割されたポリゴンの数）
３．各ポリゴンの面積ｓｊ  を求める。
【００７８】
４．各ポリゴンの法線ベクトルｎｊ  →を求める。
【００７９】
５．外接直方体の重心と各ポリゴンの重心とを結ぶベクトルＧｇｊ  →の長さを１とした単位ベクトルｃｊ  →を求める。
【００８０】
ｃｊ  →＝Ｇｇｊ  →／｜Ｇｇｊ  →｜
６．単位ベクトルｃｊ  →と各ポリゴンの法線ベクトルｎｊ  →の内積Ｉｊ  を求める。
【００８１】
→単位ベクトルと法線ベクトルの長さは１に正規化されているため、内積Ｉｊ  は各ポリゴンの外接直方体重心に対する向きを表現している。
【００８２】
７．内積は−１．０〜１．０の値をとるので、この範囲をｍ等分して内積値の離散化をする。
【００８３】
→変数ｄｉ  （ｉ＝１…ｍ）を用意し、その値を要素とするｍ次元の特徴量ベクトルＤ（ｄ１  ，ｄ２  ，…ｄｍ  ）を考える。
【００８４】
８．内積Ｉｊ  の値がどの範囲に含まれるか調べ、該当するｍ次元の特徴量ベクトルＤ（ｄ１  ，ｄ２  ，…ｄｍ  ）の次元にそのポリゴンの面積を加算する。
【００８５】
９．全てのポリゴンについて処理したら、ｍ次元の特徴量ベクトルＤ（ｄ１  ，ｄ２  ，…ｄｍ  ）の各次元をポリゴンの総面積で除算し、正規化する。
【００８６】
以上の処理により、三次元物体の外接直方体重心に対する各ポリゴンの相対的な向きの分布による特徴量ベクトルを得る。
【００８７】
これ以外のフェーズのフローチャートは、本発明の実施例１の場合と同様である。
【００８８】
こうすることで、ポリゴンの面積だけでなく、面の向きをも考慮にいれた三次元物体の検索が可能になる。
【００８９】
［実施例４］
次に、本発明の実施例４を説明する。本発明の実施例４の構成は、本発明の実施例１の構成（図１）と同様である。
【００９０】
本発明の実施例４では、三次元物体の特徴として、ポリゴンの法線ベクトルを本発明の実施例３の場合とは違った形で利用している。そのため、本発明の実施例３と比べ、三次元物体特徴量抽出フェーズが以下のようになっている。
【００９１】
「三次元物体特徴量抽出フェーズ」
図９は、本発明の実施例４の三次元物体特徴量抽出フェーズの動作を説明するフローチャートである。
【００９２】
まず、ポリゴン情報抽出部１５によって、三次元物体入力装置１２から入力された三次元物体から、ポリゴンの頂点情報と、その頂点がどのように接続されて面を構成しているかという面情報を取り出す。
【００９３】
次に、ポリゴン分割部１６が、ある一定の値Ｓ以上の面積のポリゴンを分割する。
【００９４】
そして、ポリゴン特徴量抽出部１７で、分割された各ポリゴンから次のように特徴量を抽出する。
【００９５】
１．各ポリゴンの面積ｓｊ  を求める。（ｊ＝１…分割されたポリゴンの数）
２．各ポリゴンの法線ベクトルｎｊ  →を求める。
【００９６】
３．各ポリゴンの法線ベクトルｎｊ  →＝（ｘｊ  ，ｙｊ  ，ｚｊ  ）を図１０に示すような極座標形式（ｒｊ  ，θｊ  ，ψｊ  ）に変換する（法線ベクトルの長さは１なので、ｒｊ  ＝１である）。
【００９７】
４．θ，ψは−π〜πの値をとるので、この範囲をそれぞれｌ等分して、極座標空間をｌ２  個に離散化する。
【００９８】
→変数ｐｉ  （ｉ＝１…ｌ２  ）を用意し、その値を要素とするｌ２  次元の特徴量ベクトルＰ（ｐ１  ，ｐ２  ，…ｐｌ２  ）を考える。
【００９９】
５．各ポリゴンの法線ベクトルがどの範囲に含まれるか調べ、該当するｌ２  次元の特徴量ベクトルＰ（ｐ１  ，ｐ２  ，…ｐｌ２  ）の次元にそのポリゴンの面積を加算する。
【０１００】
６．全てのポリゴンについて処理したら、ｌ２  次元の特徴量ベクトルＰ（ｐ１  ，ｐ２  ，…ｐｌ２  ）の各次元をポリゴンの総面積で除算し、正規化する。
【０１０１】
以上の処理により、三次元物体における各ポリゴンの向きそのものの分布による特徴量ベクトルを得る。
【０１０２】
これ以外のフェーズのフローチャートは、本発明の実施例１の場合と同様である。
【０１０３】
こうすることで、ポリゴンの面積だけでなく、面の向きをも考慮に入れた三次元物体の検索が可能になる。
【０１０４】
［実施例のまとめ］
以上述べた各実施例に示すように、本発明によれば、
・ポリゴンの大きさを決められた一定の値以下になるようにポリゴンを分割する手法
・三次元物体のポリゴン情報から、ポリゴンの大きさ（面積）に関する特徴量を抽出する手法
・三次元物体のポリゴン情報から、ポリゴンの向き（法線ベクトル）に関する特徴量を抽出する手法
・抽出した特徴量を用いて、三次元物体の類似検索を行なう手法
を確立できる。
【０１０５】
また、本発明の各実施例では、特徴量を１つ１つ独立に扱っているが、これらの特徴量をまとめて扱い、どの特徴量をどのくらい重視するかという重み付けをして複合検索を行なうこともできる。
【０１０６】
尚、本発明における三次元物体データベースの検索方法は、具体的にはパーソナルコンピュータ（ＰＣ）等のコンピュータにより、予め所定のコンピュータ読み取り可能な記録媒体に記録された三次元物体データベースの検索プログラムに基づいて実行される。
【０１０７】
すなわち、本発明の三次元物体データベースの検索プログラムを記録したコンピュータ読み取り可能な記録媒体は、与えられた三次元物体データからポリゴン情報を抽出するポリゴン情報抽出手順、前記ポリゴン情報抽出手順で抽出されたポリゴンの大きさを決められた一定の大きさ以下にするポリゴン分割手順、前記ポリゴン分割手順で分割されたポリゴン情報をもとに三次元物体の特徴量を抽出するポリゴン特徴量抽出手順、前記ポリゴン特徴量抽出手順で抽出された特徴量情報を蓄積する蓄積手順、２つの三次元物体の類似度を計算する三次元特徴量情報比較手順をコンピュータに実行させるためのプログラムを記録し、三次元物体データからポリゴン情報を抽出し、ポリゴンの大きさを一定の大きさ以下に分割し、分割されたポリゴン情報から三次元物体の特徴量を抽出して特徴量情報を蓄積し、入力された検索キーと蓄積された三次元物体との類似度を計算し、類似した形状を持つ三次元物体を出力する手順をコンピュータに実行させるための三次元物体データベースの検索プログラムを記録する。
【０１０８】
また本発明の三次元物体データベースの検索プログラムを記録したコンピュータ読み取り可能な記録媒体は、前記ポリゴン特徴量抽出手順において、ポリゴンの面情報から面積を計算し、計算した面積を形状特徴量として抽出することを特徴とする。
【０１０９】
また本発明の三次元物体データベースの検索プログラムを記録したコンピュータ読み取り可能な記録媒体は、前記ポリゴン特徴量抽出手順において、ポリゴンの面情報から法線ベクトルを計算し、計算した法線ベクトルを形状特徴量として抽出することを特徴とする。
【０１１０】
【発明の効果】
以上述べたように本発明によれば、三次元物体データベースの検索において
・ポリゴンの大きさを決められたある一定の値以下になるように分割し、ポリゴンの大きさの違いによる類似度差異を吸収すること
・三次元物体のポリゴン情報から、形状の特徴として面情報を
１．ポリゴンの大きさ（面積）による特徴量
２．ポリゴンの向き（法線ベクトル）による特徴量
の形で抽出すること
・抽出した特徴量を用いて、三次元物体の類似検索を行なうこと
が可能になる。
【図面の簡単な説明】
【図１】本発明の実施例１を示す構成説明図である。
【図２】本発明の実施例１に係る三次元物体特徴量抽出フェーズの動作を示すフローチャートである。
【図３】本発明の実施例１に係るポリゴン分割例を示す説明図である。
【図４】本発明の実施例１に係るセルに重心が含まれる例を示す説明図である。
【図５】本発明の実施例１に係る三次元物体蓄積フェーズの動作を示すフローチャートである。
【図６】本発明の実施例１に係る三次元物体検索フェーズの動作を示すフローチャートである。
【図７】本発明の実施例２に係る三次元物体特徴量抽出フェーズの動作を示すフローチャートである。
【図８】本発明の実施例３に係る三次元物体特徴量抽出フェーズの動作を示すフローチャートである。
【図９】本発明の実施例４に係る三次元物体特徴量抽出フェーズの動作を示すフローチャートである。
【図１０】本発明の実施例４に係る極座標を示す説明図である。
【図１１】従来の頂点情報のみを用いた形状特徴量の問題を示す説明図である。
【図１２】従来のポリゴンの大きさに依存した形状特徴量の問題を示す説明図である。
【符号の説明】
１１  三次元物体検索装置
１２  三次元物体入力装置、
１３  表示装置、
１４  検索条件入力装置、
１５  ポリゴン情報抽出部、
１６  ポリゴン分割部、
１７  ポリゴン特徴量抽出部、
１８  蓄積部、
１９  メモリ
２０  検索条件入力部、
２１  三次元特徴量情報比較部、
【図１】
0003614761.tif 000002
【図２】
0003614761.tif 000003
【図３】
0003614761.tif 000004
【図４】
0003614761.tif 000005
【図５】
0003614761.tif 000006
【図６】
0003614761.tif 000007
【図７】
0003614761.tif 000008
【図８】
0003614761.tif 000009
【図９】
0003614761.tif 000010
【図１０】
0003614761.tif 000011
【図１１】
0003614761.tif 000012
【図１２】
0003614761.tif 000013