(57)【要約】【課題】三次元モデルを効率的に検索すること。【解決手段】三次元モデル検索装置は、モデル正規化部と、二次元画像生成部と、モデル記述部と、検索部とを備える。モデル正規化部は、検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、三次元モデルの重心をシステム座標系の原点に一致させる。二次元画像生成部は、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する。モデル記述部は、二次元画像に基づいて三次元モデルのモデル記述子を生成する。検索部は、モデル記述子に基づいて、複数の三次元モデルを記憶するモデルライブラリから三次元モデルにマッチした三次元モデルを検索する。【選択図】図１
2012043419.tif 000002
【特許請求の範囲】
【請求項１】
検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させるモデル正規化部と、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する二次元画像生成部と、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成するモデル記述部と、
前記モデル記述子に基づいて、複数の三次元モデルを記憶するモデルライブラリから前記三次元モデルにマッチした三次元モデルを検索する検索部と、
を備える三次元モデル検索装置。
【請求項２】
前記三次元モデルの表面をポリゴンメッシュの形式に変換するモデル表面処理部を更に備える、請求項１に記載の三次元モデル検索装置。
【請求項３】
前記二次元画像生成部は、
投影平面と交差するポリゴンを投影平面の正方向における正方向ポリゴンと投影平面の負方向における負方向ポリゴンとに区分するポリゴン処理部と、
前記システム座標系の各座標軸の正方向におけるポリゴンと負方向とにおけるポリゴンとを相応する投影平面に投影したポリゴンのそれぞれに対して充填を行って前記二次元画像を生成するポリゴン充填部と、
を備える、請求項２に記載の三次元モデル検索装置。
【請求項４】
前記ポリゴン充填部は、前記システム座標系の各座標軸の正方向におけるポリゴンと負方向におけるポリゴンとに対して、各ポリゴン毎の各頂点の投影平面への垂線の足を算出し、垂線の足により構成されるポリゴン領域を充填する、請求項３に記載の三次元モデル検索装置。
【請求項５】
前記ポリゴンは三角形又は四角形である、請求項４に記載の三次元モデル検索装置。
【請求項６】
前記検索部は、前記三次元モデルの２４個の特徴ベクトルと前記モデルライブラリにおける三次元モデルの相応する特徴ベクトルとの距離を算出することにより、前記モデルライブラリから前記三次元モデルにマッチした三次元モデルを検索する、請求項１〜５の何れかに記載の三次元モデル検索装置。
【請求項７】
三次元モデル検索装置が、
検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させ、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成し、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成し、
前記モデル記述子に基づいて、複数の三次元モデルを記憶するモデルライブラリから前記三次元モデルにマッチした三次元モデルを検索すること、
を含む三次元モデル検索方法。
【請求項８】
検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させるモデル正規化部と、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する二次元画像生成部と、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成するモデル記述部と、
を備えるモデルライブラリ生成装置。
【請求項９】
モデルライブラリ生成装置が、
検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させ、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成し、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成すること、
を含むモデルライブラリ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は三次元モデル検索装置、三次元モデル検索方法、モデルライブラリ生成装置及びモデルライブラリ生成方法に関する。
【背景技術】
【０００２】
近年、計測結果や測定結果として三次元データを取得する技術、コンピュータ支援設計（ＣＡＤ：computer  aided  design）の技術、グラフィックスハードウェア技術が進歩している。これに伴い、ネットワーク上及び各種の特定のデータベース上に存在する三次元モデルの数が急激に増加している。一方、高精度な三次元モデルの設計にはコストが高くなり、時間もかかる。したがって、既存の三次元モデルを有効に利用することが非常に重要である。しかしながら、大量の三次元モデルの中から有用な三次元モデルを探すことは困難である。このようなことから、有用な三次元モデルを検索する方法が研究されている。
【０００３】
現在、三次元モデルを検索する多種類の方法が知られている。これらの方法は、キーワードによる検索方法及びコンテンツによる検索方法の２つのカテゴリに分けられる。キーワードによる検索方法では、三次元モデルが語義の階層で記述され、三次元モデルの特徴が、一連の属性データ、例えば寸法、材料、色及び種類等により表現される。また、コンテンツによる検索方法は、三次元モデル自身のコンテンツを加味して三次元モデルを検索する。以前は、三次元モデルの数が多くなかったので、キーワードによる検索方法が比較的実用的なものであったが、三次元モデルの数が急激に増加したので、同じような属性データを持つ三次元モデルが多く探すのが難しい場合がある。また、属性データが多少違っていても類似した形状の三次元モデルを検索したい場合も多く、コンテンツによる検索方法が注目されている。コンテンツによる検索方法は、特徴ベクトルによる検索方法、トポロジー構造による検索方法及び二次元画像による検索方法の三種類に大別される。
【０００４】
特徴ベクトルによる検索方法において、一つの特徴ベクトルを用いて三次元の物体を記述する。ここで、形状分布が最も有名な方法である。形状分布法は、特徴の抽出と三次元モデルの比較とにおいて高い効率を有する。しかしながら、特徴ベクトルが簡単であり、三次元モデルの情報の記述が十分な正確性を有していないので、検索の正確性が低く、理想的な検索方法ではない。このような方法は、簡単で且つ効率的であるため、予備的な分類手法として他の方法に組み込まれる場合がある。
【０００５】
トポロジー構造による検索方法において、三次元モデルの構造特徴は、ツリー又はグラフの方式により表現される。そして、ツリー又はグラフをマッチングさせることにより二つの三次元モデルを比較する。トポロジー構造は、三次元モデルの形状の直接的で且つ重要な情報を提供する。また、このような特徴はアフィン不変性を有する。しかしながら、トポロジー構造は、三次元モデルの微かな変形に対して感度が高く、且つツリー又はグラフのマッチングには時間がかかる。これらの欠点によりトポロジー構造による検索方法は、実用化が制限されている。
【０００６】
二次元画像による検索方法において、三次元モデルに基づいて一連の二次元画像を生成し、相応する二次元画像を比較することによって三次元画像を比較する。ここで、ライトフィールド記述子法と、特徴グラフ法とは最も多く利用されている二次元画像による三次元モデルの検索方法である。
【０００７】
ライトフィールド記述子法において、１０個のライトフィールド記述子を利用して一つの三次元モデルの特徴を表現する。各ライトフィールド記述子のそれぞれは、１０個の二次元画像の特徴を含み、これらのライトフィールド記述子を比較することにより三次元モデルを比較する。三次元モデルに基づいて二次元画像を生成する場合、正十二面体をモデルの中心に配置して、正十二面体の二十個の頂点を視点として正射影で２０個の二次元画像を生成する。生成した２０個の二次元画像うち、対向する頂点を視点とする二つの画像は同一であるため、１０個の二次元画像を残す。そして、これら１０個の二次元画像に基づいて一つのライトフィールド記述子を生成する。正十二面体を回転させることにより、異なる二次元画像を取得し、更に異なるライトフィールド記述子を取得する。ライトフィールド記述子法において、１０個のライトフィールド記述子を生成し、マッチした画像間の距離の累積により二つのライトフィールド記述子を比較する。１０個のライトフィールド記述子の取得において、合計１００個の二次元画像をレンダリングすることになる。
【０００８】
特徴グラフ法において、正二十面体を三次元モデルの中心に配置し、正二十面体の各ポリゴンを分割して一様に分布する８０個のポリゴンを取得する。そして、取得した８０個のポリゴンの中心を視点として正射影で最初の８０個のグラフを取得する。続いて、三次元モデルのそれぞれに対して、最初の８０個のグラフから幾つかの代表的なグラフを選択する。そして、ベイズ確率論に基づいて、三次元モデルのそれぞれの代表的なグラフから、検索する画像に対応するグラフを探し出し、更に、インデックスとデータベースモデルとの類似性を算出する。
【０００９】
三次元モデルの検索方法について総括した文献によれば、特徴ベクトルによる検索方法及びトポロジー構造による検索方法と比べると、二次元画像による検索方法は、より良い検索結果を取得することができる。
【００１０】
また、二次元画像による三次元モデルを検索する装置及び三次元モデルを検索する方法が提案されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００９−８０７９６号公報
【非特許文献】
【００１２】
【非特許文献１】R.  Osada,  R.  Funkhouser,  T.  Chazelle:  Shape  distributions.  ACM  Transactions  on  Graphics,  21(5),  807--832(2002)。
【非特許文献２】M.  Hilaga,  Y.  Shinagawa,  T.  Kohmura,  T.L.  Kunii:  Topology  matching  for  fully  automatic  similarity  estimation  of  3D  shapes.  Proceedings  SIGGRAPH,  203--212(2001)。
【非特許文献３】C.  Ding-Yun,  T.  Xiaopei,  S.  Yute,  O.  Ming:  On  visual  similarity  based  3D  model  retrieval.  Proceedings  of  European  association  for  Computer  Graphics,  22(3),  223--232(2003)。
【非特許文献４】T.F.  Ansqry,  J.Vandeborre,  M.  Daoudi:  A  framework  for  3D  CAD  models  retrieval  from  2D  images.  Annual  of  telecommunications  technologies  and  tools  for  3D  imaging.  Vol.60  (11-12),  2005。
【非特許文献５】P.  Shilane,  P.  Min,  M.  Kazhdan,  T.  Funkhouser:  The  Priceton  shape  benchmark.  Proceedings  of  the  international  conference  on  Shape  modeling,  167--178(2004)。
【非特許文献６】N.  Iyer,  S.  Jayanti,  K.  Ramani:  An  engineering  shape  benchmark  for  3D  models.  Proceedings  of  ASME  IDETC/CIE,  24--28(2005)。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述した従来の技術では、二次元画像による検索方法では、三次元モデルを効率的に検索することができないという課題があった。具体的には、各文献に言及された二次元画像による方法では、処理する画像の数が多くなるため、特徴抽出及びモデル比較のプロセスに時間がかかり、実用化が制限されている。
【００１４】
開示の技術は、上記に鑑みてなされたものであって、二次元画像による検索方法で、三次元モデルを効率的に検索することができる三次元モデル検索装置、三次元モデル検索方法、モデルライブラリ生成装置及びモデルライブラリ生成方法を提供する。
【課題を解決するための手段】
【００１５】
本発明による別の一態様は、三次元モデル検索装置である。三次元モデル検索装置は、検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、三次元モデルの重心を前記システム座標系の原点に一致させるモデル正規化部を備える。また、三次元モデル検索装置は、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する二次元画像生成部を備える。また、三次元モデル検索装置は、二次元画像に基づいて三次元モデルのモデル記述子を生成するモデル記述部を備える。また、三次元モデル検索装置は、モデル記述子に基づいて、複数の三次元モデルを記憶するモデルライブラリから三次元モデルにマッチした三次元モデルを検索する検索部を備える。
【００１６】
本発明による別の一態様は、三次元モデル検索方法である。三次元モデル検索方法において、三次元モデル検索装置が、検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、三次元モデルの重心をシステム座標系の原点に一致させる。また、三次元モデル検索装置が、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する。また、三次元モデル検索装置が、二次元画像に基づいて三次元モデルのモデル記述子を生成する。また、三次元モデル検索装置が、モデル記述子に基づいて、複数の三次元モデルを記憶するモデルライブラリから前記三次元モデルにマッチした三次元モデルを検索する。
【００１７】
本発明によるまた別の一態様はモデルライブラリ生成装置である。モデルライブラリ生成装置は、検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、三次元モデルの重心をシステム座標系の原点に一致させるモデル正規化部を備える。また、モデルライブラリ生成装置は、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する二次元画像生成部を備える。また、モデルライブラリ生成装置は、二次元画像に基づいて三次元モデルのモデル記述子を生成するモデル記述部を備える。
【００１８】
本発明によるまた別の一態様はモデルライブラリ生成方法である。モデルライブラリ生成方法において、モデルライブラリ生成装置が、検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、三次元モデルの重心を前記システム座標系の原点に一致させる。また、モデルライブラリ生成装置が、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する。また、モデルライブラリ生成装置が、二次元画像に基づいて三次元モデルのモデル記述子を生成する。
【００１９】
また、本発明による別の一態様は、更に機器読取可能のプログラムコードを含む記憶媒体を提供する。プログラムコードは、情報処理装置に実行されると、情報処理装置に、本発明による三次元モデル検索方法及びモデルライブラリ生成方法を実行させる。
【００２０】
また、本発明による別の一態様は、更に機器実行可能のコマンドを含むプログラム製品を提供する。コマンドは、情報処理装置に実行されると、その情報処理装置に、本発明による三次元モデル検索方法及びモデルライブラリ生成方法を実行させる。
【発明の効果】
【００２１】
本願の開示する三次元モデル検索装置、三次元モデル検索方法、モデルライブラリ生成装置及びモデルライブラリ生成方法の一つの態様によれば、三次元モデルを効率的に検索することができるという効果を奏する。
【図面の簡単な説明】
【００２２】
【図１】図１は、実施例１に係る三次元モデル検索システムの構成を示すブロック図である。
【図２】図２は、Ｎｏｒｍａｌ−ＰＣＡ方法を用いた三角形の面積の算出及び法線方向の算出を説明する図である。
【図３】図３は、主軸方向の検出結果の例を示す図である。
【図４】図４は、実施例１に係る三次元モデル検索システムに含まれる二次元画像生成部の構成を示すブロック図である。
【図５】図５は、実施例１に係るポリゴン充填を説明する図である。
【図６】図６は、実施例２に係る三次元モデル検索システムの構成を示すブロック図である。
【図７】図７は、三次元モデル検索方法の処理手順を示すフローチャートである。
【図８】図８は、二次元画像生成処理の処理手順を示すフローチャートである。
【図９】図９は、モデルライブラリ生成方法の処理手順を示すフローチャートである。
【図１０】図１０は、三次元モデル検索プログラム及びモデルライブラリ生成プログラムを実行するコンピュータの構成を示す図である。
【発明を実施するための形態】
【００２３】
以下では、本発明の目的、特徴と効果をより容易に理解できるように、図面に基づいて、本発明に係る実施例を説明する。また、図面における構成部は本発明の動作を示すためのものに過ぎない。図面において、同一又は類似の技術的特徴又は構成部には、同一又は類似の符号を付与して示す。
【００２４】
また、説明を明確で簡潔にするために、実施形態の特徴のすべてを明細書に記載しているわけではない。しかし、このような実施例を実用化する場合、開発者は、実施形態に特定される多くのことを決定しなければならない。例えば、開発者は、システム及び業務に関連する制約条件に実施形態を適合させる。また、開発者は、実施形態に応じてこれらの制約条件を変更する。また、実用化には複雑で時間が必要であるが、開示技術からアイデアを得た当業者にとっては、これらは実用化に伴う義務に過ぎない。
【００２５】
また、開示技術が不明確になることを防ぐため、図面において、開示技術と直接関係する装置の構成部及び/又は処理ステップのみを示し、開示技術と直接関係しない他のものについては、詳細な説明を省略している。また、開示技術の一個の図面又は一種類の実施形態において説明された要素と特徴は、一個又はそれ以上の他の図面或は実施形態において示された要素及び特徴と組み合わせることができる。
【実施例１】
【００２６】
図１は、実施例１に係る三次元モデル検索システムの構成を示すブロック図である。本実施例による三次元モデル検索システムにおいて、三次元モデル検索装置１１０は、検索対象である三次元モデル１２０とモデルライブラリ１３０における三次元モデルとを解析する。そして、三次元モデル検索装置１１０は、入力された検索対象である三次元モデル１２０にマッチした三次元モデルをモデルライブラリ１３０から検索し、最終的に検索結果を出力する。
【００２７】
検索対象である三次元モデル１２０を入力するために用いられる入力装置は、例えばキーボード、マウス、タッチパネル、記憶媒体インターフェース、ネットワークインターフェース等検索対象である三次元モデル１２０を入力可能な任意の入力装置であっても良い。なお、記憶媒体インターフェースには、ディスクドライブ、光ディスクドライブ等を含む。検索結果を出力するために用いられる出力装置は、例えばディスプレイ、ネットワークインターフェース、記憶媒体インターフェース等検索された三次元モデルを出力可能な任意の出力装置であっても良い。モデルライブラリ１３０は、メモリに構築されたデータベースにより構成されても良く、大量の三次元モデルを記憶する。なお、メモリには、ローカルメモリとネットワークメモリとを含む。
【００２８】
実施例１に係る三次元モデル検索装置１１０は、モデル表面処理部１１０１と、モデル正規化部１１０３と、二次元画像生成部１１０５と、モデル記述部１１０７と、検索部１１０９とを備える。モデル表面処理部１１０１は、三次元モデルの表面をポリゴンメッシュの形式に変換する。モデル正規化部１１０３は、三次元モデルに対して回転及び/又は平行移動を行って三次元モデルの主軸方向を三次元空間における座標軸方向と一致させ、三次元モデルの重心をシステム座標系の原点と一致させる。二次元画像生成部１１０５は、システム座標系の各座標軸の正と負の方向のそれぞれにおいて三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する。モデル記述部１１０７は、生成された二次元画像に基づいて三次元モデルのモデル記述子を生成する。検索部１１０９は、生成されたモデル記述子に基づいて、モデルライブラリ１３０から、検索対象である三次元モデル１２０にマッチした三次元モデルを検索する。そして、検索部１１０９は、検索して、マッチした三次元モデルを検索結果として出力する。
【００２９】
ここで、実施例１に係る三次元モデル検索装置１１０におけるモデル表面処理部１１０１は、選択可能な構成部であり、必要に応じて選択される。例えば、メッシュ化処理が行われた三次元モデルが入力される場合、三次元モデル検索装置１１０は、モデル表面処理部１１０１を含まなくてもよい。
【００３０】
三次元モデル検索装置１１０は、パーソナルコンピュータ、ワークステーション、ＰＤＡ(パーソナルデジタルアシスタント)等の情報処理機器により実現することができる。情報処理機器の構成については、後に図１０を用いて詳細に説明する。具体的には、情報処理機器のＣＰＵ(中央処理装置)及び相応するプログラムにより、モデル表面処理部１１０１と、モデル正規化部１１０３と、二次元画像生成部１１０５と、モデル記述部１１０７と、検索部１１０９とを実現することができる。
【００３１】
次に、本実施例における三次元モデル検索装置１１０の各部を詳細に説明する。
【００３２】
検索対象である三次元モデル１２０を入力されると、当該検索対象である三次元モデル１２０がまず三次元モデル検索装置１１０のモデル表面処理部１１０１に転送される。モデル表面処理部１１０１では、三次元モデルの表面がポリゴンメッシュの形式、例えば三角形メッシュ、四角形メッシュ等に変換される。
【００３３】
モデル表面処理部１１０１は、三次元モデルに対してメッシュ化処理を行った後に、ポリゴンメッシュの形式の三次元モデルをモデル正規化部１１０３に転送する。
【００３４】
モデル正規化部１１０３は、三次元モデルの主軸方向をシステム座標系における座標軸に一致させ、且つ三次元モデルの重心をシステム座標系における原点に一致させることで、三次元モデルに対して正規化を行う。一般的に、三次元モデルを任意の方向で三次元空間の任意の場所に位置させることができる。モデル正規化部１１０３は、正規化をするため、三次元モデルに対して平行移動と回転移動とを行う。
【００３５】
モデル正規化部１１０３は、まず三次元モデルの重心の座標を算出する。そして、モデル正規化部１１０３は、算出した三次元モデルの重心の座標に対して平行移動を行うことによって、三次元モデルの重心の座標をシステム座標系の原点に変換する。三次元モデルに対する平行移動は、当分野における公知の方法を採用することができるので、具体的な説明を省略する。
【００３６】
モデル正規化部１１０３による回転移動について説明する。従来技術において、例えば主成分分析(principal  component  analysis:PCA)など、三次元モデルに対して回転移動を行う幾つかの方法が提案されている。しかしながら、経験的に幾つかの類似の三次元モデルについては、主成分分析により安定な主軸方向を取得することができない。
【００３７】
これに対して、本発明の発明者は、特許文献１においてＮｏｒｍａｌ−ＰＣＡ(N-PCA)と呼ばれるモデル正規化方法を提案している。この方法では、まず、モデルの主軸方向を抽出し、その後、抽出された主軸方向を用いて三次元モデルを正規化する。
【００３８】
一般的に、三次元モデルは三角形メッシュにより構成される。また、三角形の法線方向の分布は、三次元モデルの方向情報を提供する。したがって、本発明のＮ−ＰＣＡ方法では、モデルにおける全ての三角形の法線方向の分布情報を考慮してモデルの主軸方向を検出する。以下に、図２を用いて、Ｎ−ＰＣＡ方法で三次元モデルに対して回転移動して正規化を行う処理を詳細に説明する。図２は、Ｎｏｒｍａｌ−ＰＣＡ方法を用いた三角形の面積の算出及び法線方向の算出を説明する図である。
【００３９】
モデル正規化部１１０３は、まず、各三角形ｔｉの面積ａｉ及び法線方向ベクトルｐｉ（ｉ＝１，２，．．．，ｆＣｎｔ）を算出する。ここで、ｆＣｎｔは三次元モデルに含まれる三角形の数を示す。
【００４０】
図２に示すように、三角形ｔｉの頂点をＡ、Ｂ、Ｃとし、三つの辺の長さをｌａ、ｌｂ、ｌｃとすると、三角形の面積ａｉは式（１）により算出することができる。ここで、ｓ＝（ｌａ＋ｌｂ＋ｌｃ）／２は、三角形の半周長を示し、＊は、乗算を示す。
【数１】
2012043419.tif 000003
【００４１】
三角形の法線方向ベクトルｐｉは式（２）により得ることができる。
【数２】
2012043419.tif 000004
【００４２】
モデル正規化部１１０３は、全ての三角形の法線方向を算出した後に、三角形の法線方向の分布情報に基づいて三次元モデルの三つの主軸方向を取得する。以下に詳細な処理を説明する。
【００４３】
モデル正規化部１１０３は、先ず、式（３）により、法線方向の重み分布行列Ｍを算出する。
【数３】
2012043419.tif 000005
【００４４】
モデル正規化部１１０３は、行列Ｍに対して特徴値分解を行って三つの特徴ベクトルと特徴値とを取得する。これら三つの特徴ベクトルは主軸方向、即ちベクトルｐａ１、ベクトルｐａ２、ベクトルｐａ３、となる。
【００４５】
モデル正規化部１１０３は、下の式（４）により、モデルの各頂点を正規化する。
【数４】
2012043419.tif 000006
【００４６】
図３は、主軸方向の検出結果の例を示す図である。モデル正規化部１１０３は、Ｎ−ＰＣＡ方法を利用することにより、三次元モデルの主軸方向を正確で且つ安定的に検出することができ、このうえで正規化を行う。モデル正規化部１１０３は、正規化を行った後に、モデルの主軸方向がシステム座標系の座標軸となると共に、モデルの重心が座標系の原点まで平行移動する。
【００４７】
ここで、本発明による当該三次元モデルの検索システムにおいて、上述のように、モデル正規化部１１０３は、モデル表面処理部１１０１によりポリゴンメッシュの形式に変換された三次元モデルの表面を処理する。しかし、この処理は必須ではなく、他の正規化方式を採用しても良い。この場合、三次元モデルの表面はポリゴンメッシュの形式でなくてもよい。この場合に、モデル表面処理部１１０１による処理は、モデル正規化部１１０３による正規化の処理の後に実行されても良い。或いは、入力された三次元モデルが既に、三角形メッシュ等のポリゴンメッシュの形式である場合、実施例１に係る三次元モデル検索装置１１０において、モデル表面処理部１１０１による処理を省略することができる。
【００４８】
次に、二次元画像生成部１１０５は、モデル表面処理部１１０１及びモデル正規化部１１０３により処理された三次元モデルに対して、システム座標系の各座標軸の正と負の方向のそれぞれにおいてポリゴンメッシュの投影を行って複数の二次元画像を生成する。
【００４９】
二次元画像生成部１１０５は、主に６個の二次元画像を生成する。二次元画像は、グレー画像又は二値画像であっても良い。また、二次元画像は、同一の寸法に設定されても良く、座標範囲に基づいて各画像の寸法を設定されても良い。
【００５０】
６個の二次元画像は、投影方向によってそれぞれ上面、下面図、左面、右面図、正面、背面図と呼ばれる。上面、下面図は、Ｚ軸方向に沿ってｘ−ｙ平面へ投影される二次元画像である。左面、右面図は、ｙ軸方向に沿ってｘ−ｚ平面へ投影される二次元画像である。正面、背面図は、ｘ軸方向に沿ってｙ−ｚ平面へ投影される二次元画像である。二次元画像生成部１１０５は、二次元画像生成のプロセスにおいて、各座標軸の正方向と負方向との二つの方向に沿って、例えば、上面、下面図、一対の画像を生成する。
【００５１】
二次元画像生成部１１０５は、この処理において、主に二つの操作、即ち各ポリゴンメッシュを処理し、ポリゴン充填アルゴリズムにより二次元画像を生成する。図４は、実施例１に係る三次元モデル検索システムに含まれる二次元画像生成部の構成を示すブロック図である。図４に示したように、実施例１に係る二次元画像生成部１１０５は、ポリゴン処理部１１０５１と、ポリゴン充填部１１０５３とを備える。
【００５２】
ポリゴン処理部１１０５１は、投影平面を通り抜けるポリゴンを投影平面の正方向における正方向ポリゴンと、投影平面の負方向における負方向ポリゴンとに区分する。例えば、ポリゴン処理部１１０５１は、入力された三次元モデルが三角形メッシュにより構成される場合に、各三角形メッシュを順に処理し、処理した三角形メッシュが投影平面を通り抜けるか否かを判定する。ポリゴン処理部１１０５１は、処理した三角形メッシュが投影平面を通り抜けると判定した場合に、処理した三角形メッシュを二つの部分、即ち投影平面の正方向における部分と、投影平面の負方向における部分とに分ける。上面、下面図を例とする場合に、処理待ちの三角形メッシュは、完全にｘ−ｙ(ｚ=０)平面の上方に位置すれば、ポリゴン処理部１１０５１は、処理が必要なく、直接、後述するポリゴン充填処理を実行する。三角形メッシュが完全にｘ−ｙ(ｚ=０)平面の下方に位置すれば、ポリゴン処理部１１０５１は、同様に処理が必要なく、直接、後述するポリゴン充填を実行する。しかしながら、この二つの場合以外、すなわち、三角形の平面がｚ=０平面と交差する場合、ポリゴン処理部１１０５１は、三角形平面とｚ=０平面との交差線に沿って三角形平面を二つの部分に分割する。ポリゴン処理部１１０５１は、他の図面についても、類似の処理を行うことにより、各投影平面を通り抜ける全てのポリゴンを投影平面の正方向における正方向ポリゴンと、投影平面の負方向における負方向ポリゴンとに分ける。
【００５３】
ポリゴン充填部１１０５３は、各座標軸の正方向と負方向とにおけるポリゴンの相応する投影平面への投影ポリゴンのそれぞれに対して充填を行って二次元画像を生成する。ポリゴン充填部１１０５３は、選定された投影方向と投影平面に対して、条件を満たす各ポリゴンを順に処理する。上面図の生成プロセスを例とする場合に、条件を満たすポリゴンとは、完全にｚ＝０平面の上方に位置する各ポリゴンであり、ここのポリゴンは、一般的に三角形と四角形であり且つ凸ポリゴンである。ここで、ポリゴン充填部１１０５３は、ｘ又はｙ方向に沿って走査する方法を用いてポリゴンに対して充填を行う。
【００５４】
ポリゴン充填部１１０５３は、ポリゴンを充填する前に、先ずポリゴンを投影平面において投影させる。ポリゴン充填部１１０５３は、各ポリゴン毎の各頂点に対してその投影平面への垂線の足を算出し、これらの垂線の足によりポリゴン領域を形成する。次に、ポリゴン充填部１１０５３は、垂線の足により形成されたポリゴン領域を充填する。
【００５５】
以下に、図５に示した三角形を例としてポリゴン充填処理を簡単に説明する。図５は、実施例１に係るポリゴン充填を説明する図である。ポリゴン充填部１１０５３は、ｙ方向の大小順序に従って低い順又は高い順で順に走査を行って、三角形領域を充填する。ポリゴン充填部１１０５３は、走査線毎に、三角形との二つの交差点を算出し、二つの交差点の間の領域を充填する。ここで、ポリゴン充填部１１０５３は、必要に応じて、白画素で充填して二値画像を取得しても良く、或は幾何学情報に基づいて相応する位置のグレー値を算出し又は更新してグレー画像を取得しても良い。
【００５６】
特許文献１及び他の従来の技術に採用されたサンプリングポイントによる方法に比べると、三角形領域を直接に投影することにより、不均一なサンプリングによるノイズを解消でき、より良い効率を実現することもできる。
【００５７】
二次元画像生成部１１０５は、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する。そして、モデル記述部１１０７は、二次元画像生成部１１０５により生成された二次元画像に基づいて、二次元画像毎に有効な特徴を抽出して三次元モデルのモデル記述子を生成する。
【００５８】
二次元画像毎の特徴の抽出については、例えばフーリエ変換、曲率尺度空間(CSS)による画像の記述子、Ｚｅｒｎｉｋｅモーメント等、複数の方法が知られている。本発明では、モデル記述部１１０７は、一例としてＺｅｒｎｉｋｅモーメントを用いて６個の二次元画像を記述する。このような方法は、形状特徴の記述に有効である。このような方法に関する詳細は、K.Whoi-Yul,K.Yong-Sung:A  region-based  shape  descriptor  using  Zernike  moments.Signal  Processing:Image  Communication,vol.16,page.95-1102,12005を参照できる。以下に、モデル記述部１１０７がＺｅｒｎｉｋｅモーメントを利用して三次元モデルの各画像毎の記述子を取得する操作を簡単に説明する。
【００５９】
モデル記述部１１０７は、１個のデジタル画像ｆ（ｘ，ｙ）について、この（ｎ，ｍ）階数のＺｅｒｎｉｋｅモーメントＡｎｍを式（５）により算出する。ただし、ｍはゼロ以外の整数で、且つ、ｎ−｜ｍ｜が偶数、及び｜ｍ｜≦ｎという二つの条件を満すものとする。ここで、ｍは二つの条件を満す非負整数である。ｆ（ｘ，ｙ）は（ｘ，ｙ）画素のグレー値、ｆ（ｘ０，ｙ０）は画像の中心、Ｖｎ，ｍ（ｘ，Ｙ）は単位円内に定義される基底関数を示す。ここで、当該基底関数のグループは完全直交基底を構成する。また、Ｖ＊ｎ，ｍ（ｘ，Ｙ）はＶｎ，ｍ（ｘ，Ｙ）の複素共役である。Ｚｅｒｎｉｋｅモーメントを算出する前に、画像における各点から画像中心までの最大距離が１になるように画像を正規化する必要がある。
【数５】
2012043419.tif 000007
【００６０】
モデル記述部１１０７は、式（５）中の基底関数Ｖｎ，ｍ（ｘ，Ｙ）を式（６）により算出する。
【数６】
2012043419.tif 000008
【００６１】
モデル記述部１１０７は、式（６）中のＺｅｒｎｉｋｅの半径方向多項式Ｒｎ，ｍ（ρ）を式（７）により算出する。ここで、！は階乗演算を示す。
【数７】
2012043419.tif 000009
【００６２】
モデル記述部１１０７は、式（５）に基づいて画像の各階数のＺｅｒｎｉｋｅモーメント、即ち、Ｍ＝｛Ａ００，Ａ１０，Ａ２０，Ａ２２，Ａ３１，Ａ３３，・・・｝を算出し、Ｚｅｒｎｉｋｅの各階数のモーメントのノルムを特徴ベクトルとする。ＯｒｄｅｒをＺｅｒｎｉｋｅの階数とすれば、特徴ベクトルの長さは式（８）となる。画像毎の特徴は一つのＤ次元の実数ベクトルで表される。
【数８】
2012043419.tif 000010
【００６３】
以上のように、画像毎の特徴は一つのＤ次元の実数ベクトルで表されるため、二つの画像を比較する場合に、二つの特徴ベクトルの間の距離、例えばユークリッド距離や絶対距離等で表現することができる。ベクトルｆ１、ベクトルｆ２を用いて２個の画像の特徴を表す場合に、そのユークリッド距離は式（９）、絶対距離は式（１０）となる。
【数９】
2012043419.tif 000011
【００６４】
ユークリッド距離及び絶対値距離の算出は周知のことである。ユークリッド距離及び絶対値距離を距離の測定値とする他、別の方法、例えば相関性等を採用しても良い。
【００６５】
これにより、生成された各二次元画像のそれぞれに対しては、Ｚｅｒｎｉｋｅモーメントのノルムをその特徴とすることができる。このような特徴は以下の特性を有する。即ち、１）回転不変性。Ｚｅｒｎｉｋｅモーメントのノルムは回転不変性を有する。２）表現の有効性。直交基底が採用されるため、特徴に冗長情報が含まれない。３）ロバスト性。この特徴はノイズと形状の微かな変形に対して不敏感である。４）有効性及びマルチスケール表現の特徴。低階数のＺｅｒｎｉｋｅモーメントは形状情報の全体を表現するが、高階数のモーメントは詳細情報を表現する。その他の形式のモーメントに比べると、１個の画像を良好に記述するために低次元のＺｅｒｎｉｋｅモーメントの特徴を利用すれば良い。
【００６６】
したがって、モデル記述部１１０７は、１個の三次元モデルに基づいて生成された全ての二次元画像のＺｅｒｎｉｋｅモーメントの集合を三次元モデルの記述子とすることができる。
【００６７】
ここまでの、モデル表面処理部１１０１、モデル正規化部１１０３、二次元画像生成部１１０５、及びモデル記述部１１０７の処理により、検索対象である三次元モデル１２０の記述子とモデルライブラリ１３０におけるモデルの記述子とがそれぞれ得られる。この記述子は検索部１１０９に転送される。検索部１１０９は、入力された検索対象である三次元モデル１２０の記述子に最もマッチした三次元モデルの記述子をモデルライブラリ１３０から検索する。
【００６８】
二次元画像を利用して三次元モデルをマッチングするキーポイントは、二次元画像間の対応関係の特定にある。実施例１に係る検索部１１０９は、まず全ての可能な座標軸変換を考慮し、検索対象である三次元モデルの６個の画像の特徴を一連の特徴ベクトルに変換する。
【００６９】
一つの六面体を例として全ての可能な座標変換を考慮する。六面立体は上、下、左、右、前、後の６個の面により構成される。入力された三次元モデルに対してモデル正規化部１１０３により正規化補正したため、ここでは任意角度の回転ではなく、座標軸変換のみを考慮する。検索部１１０９は、６個の画像については、全ての可能な座標軸変換関係を全面的に列挙すると、下の表１に示した合計２４種類の実際存在の順列を取得する。ここでは、依然として画像ペアの形式で画像を順列する。
【表１】
2012043419.tif 000012
【００７０】
つまり、検索部１１０９は、表１に基づいて二次元画像生成部１１０５により生成された上、下、左、右、前、後の二次元画像の特徴に対して順列・組み合わせを算出して、三次元モデルのモデル記述子を２４個の特徴ベクトルに変換し表示する。このうち、各行が一つの特徴ベクトルを形成する。
【００７１】
次に、検索部１１０９は、三次元モデルの記述子に基づいて、検索対象である三次元モデルと、モデルライブラリ１３０における全てのモデルとの距離を算出する。そして、検索部１１０９は、モデルライブラリ１３０におけるモデルに対して距離の小さい順にソートを行って、最終的なマッチングリストを取得する。
【００７２】
具体的に、検索部１１０９は、検索対象である三次元モデル１２０の２４個の特徴ベクトルのそれぞれと、モデルライブラリ１３０における各三次元モデル毎の特徴ベクトルとの距離を順に算出して２４個の距離を取得し、最小の距離を二つのモデルの距離として選択する。検索対象である三次元モデルと、モデルライブラリ１３０における全てのモデルとを比較して、その間の距離を算出した後に、検索部１１０９は、モデルライブラリ１３０から三次元モデルにマッチした三次元モデルを検出する。
【００７３】
検索結果として、検索部１１０９は、距離算出結果をソートし、検索対象である三次元モデル１２０との距離の最も小さい三次元モデルを出力する。検索部１１０９は、複数の候補を出力し、ユーザによる判定と選択とを受付けても良い。
【００７４】
また、検索部１１０９は、モデルライブラリ１３０における三次元モデルを表１に基づいて２４個の特徴ベクトルで記述してモデルライブラリ１３０に記憶させても良い。この場合、三次元モデルを解析する場合に、検索部１１０９は、検索対象であるモデルを１個の特徴ベクトルで記述して、モデルライブラリ１３０における三次元モデルの各特徴ベクトルと順に比較し、距離を算出すれば良い。しかし、この場合に、モデルライブラリ１３０の特徴を記憶する領域を多く必要とする。
【００７５】
実施例１における三次元モデル検索システムにおいて、全ての２４種類の可能な順列・組み合わせは表１に全面的に列挙され、実際のモデル座標軸間の回転及び変換である。このため、特許文献１及びその他の従来技術において採用された技術案に比べると、実施例１に係る三次元モデル検索システムは、より合理的な三次元モデルの比較結果を取得できる。また、実施例１に係る三次元モデル検索システムは、演算時間を削減することができるので、検索効率を向上することができる。
【実施例２】
【００７６】
次に、図６を用いて実施例２に係る三次元モデル検索システムを説明する。図６は、実施例２に係る三次元モデル検索システムの構成を示すブロック図である。
【００７７】
実施例１に係る三次元モデルの検索システムは、利用者により検索要求、即ち検索対象である三次元モデルが入力されると、検索対象である三次元モデルと、モデルライブラリにおける三次元モデルとのそれぞれを処理して記述子をそれぞれ生成する。そして、実施例１に係る三次元モデルの検索システムは、記述子に基づいて検索を行う。しかしながら、このようにすると、モデルライブラリにおける三次元モデルに対する処理が毎回必要となるため、検索時の処理量が大きくなり、効率が低下する。したがって、実施例２では、予めモデルライブラリにおける三次元モデルを処理して、各モデルの記述子を生成し、生成された記述子を相応するモデルに関連付けてモデルライブラリに記憶する。そして、利用者により検索要求が入力された場合、入力された検索対象である三次元モデルのみに対して処理して記述子を生成し、検索対象である三次元モデルの記述子とモデルライブラリに記憶された記述子とを比較して三次元モデルの検索を行う。さらに、実施例２の構成は実施例１と同様である。以下に、実施例１と同じ部分に関する説明を省略し、実施例１との相違点のみを詳細に説明する。
【００７８】
図６に示すように、実施例２に係る三次元モデル検索システムは、三次元モデル検索装置６１０と、モデルライブラリ生成装置６２０と、モデルライブラリ６４０とを備える。
【００７９】
実施例２において、利用者は入力装置を介して検索対象である三次元モデル６３０を三次元モデル検索装置６１０に入力する。三次元モデル検索装置６１０は、入力された検索対象である三次元モデルを処理して検索対象である三次元モデル６３０の記述子を生成する。そして、三次元モデル検索装置６１０は、生成した記述子に基づいて、モデルライブラリ６４０から、検索対象である三次元モデルの記述子にマッチしたモデル記述子を検出することにより、検索対象である三次元モデルにマッチした三次元モデルを検索する。そして、三次元モデル検索装置６１０は、出力装置を介して検索結果を出力する。
【００８０】
モデルライブラリ６４０は、モデルライブラリ生成装置６２０に接続される。モデルライブラリ生成装置６２０は、予め、又はモデルライブラリ６４０に新たな三次元モデルが追加されるたびに、モデルライブラリ６４０における三次元モデルを処理して相応するモデル記述子を生成する。そして、モデルライブラリ生成装置６２０は、生成したモデル記述子を三次元モデルに関連付けてモデルライブラリ６４０に記憶する。
【００８１】
モデルライブラリ生成装置６２０は、モデル表面処理部６２０１と、モデル正規化部６２０３と、二次元画像生成部６２０５と、モデル記述部６２０７とを備える。モデル表面処理部６２０１は、実施例１におけるモデル表面処理部１１０１と同様であり、モデル正規化部６２０３は、実施例１におけるモデル正規化部１１０３と同様である。二次元画像生成部６２０５は、実施例１における二次元画像生成部１１０５と同様であり、モデル記述部６２０７は、実施例１におけるモデル記述部１１０７と同様である。具体的に、モデル表面処理部６２０１は、三次元モデルの表面をポリゴンメッシュの形式に変換し、ポリゴンメッシュの形式の三次元モデルをモデル正規化部６２０３に転送する。モデル正規化部６２０３は、モデルライブラリ６４０における三次元モデルに対して正規化の処理を行う。すなわち、モデル正規化部６２０３は、三次元モデルの主軸をシステム座標系の三つの座標軸に一致させ、三次元モデルの重心をシステム座標系の原点に一致させ、補正された三次元モデルを二次元画像生成部６２０５に転送する。次に、二次元画像生成部６２０５は、システム座標系の各座標軸の正方向と負方向とにおいて三次元モデルに対してポリゴンメッシュの投影を行って６個の二次元画像を生成し、生成された二次元画像をモデル記述部６２０７に転送する。モデル記述部６２０７は、二次元画像毎のＺｅｒｎｉｋｅモーメントを算出し、全ての二次元画像のＺｅｒｎｉｋｅモーメントの集合を当該三次元モデルの記述子とする。生成された記述子を相応する三次元モデルに関連付けてモデルライブラリ６４０に記憶する。
【００８２】
同様に、モデル表面処理部６２０１は、選択可能な手段であり、必要ではない場合に実施例２に係るモデルライブラリ生成装置６２０に含まれなくても良い。また、その他の方式を採用してモデルの正規化の処理を行う場合に、モデル正規化部６２０３において三次元モデルの正規化の処理をした後に、モデル表面処理部６２０１により三次元モデルに対してポリゴンメッシュ化処理を行っても良い。
【００８３】
三次元モデル検索装置６１０は、モデル表面処理部６１０１と、モデル正規化部６１０３と、二次元画像生成部６１０５と、モデル記述部６１０７と、検索部６１０９とを備える。モデル表面処理部６１０１は、実施例１におけるモデル表面処理部１１０１と同様であり、モデル正規化部６１０３は、実施例１におけるモデル正規化部１１０３と同様である。二次元画像生成部６１０５は、実施例１における二次元画像生成部１１０５と同様であり、モデル記述部６１０７は、実施例１におけるモデル記述部１１０７と同様である。検索部６１０９は、実施例１における、検索部１１０９と同様である。
【００８４】
具体的に、利用者により入力装置を介して検索対象である三次元モデルが入力されると、モデル表面処理部６１０１は、三次元モデルの表面をポリゴンメッシュの形式に変換し、ポリゴンメッシュの形式の三次元モデルをモデル正規化部６１０３に転送する。モデル正規化部６１０３は、検索対象である三次元モデルに対して正規化の処理を行うことにより、三次元モデルの主軸をシステム座標系の三つの座標軸に一致させ、三次元モデルの重心をシステム座標系の原点に一致させる。そして、モデル正規化部６１０３は、正規化した三次元モデルを二次元画像生成部６１０５に転送する。次に、二次元画像生成部６１０５は、座標系の各座標軸の正方向と負方向とにおいて三次元モデルに対してポリゴンメッシュの投影を行って６個の二次元画像を生成し、生成した二次元画像をモデル記述部６１０７に転送する。モデル記述部６１０７は、二次元画像毎のＺｅｒｎｉｋｅモーメントを算出し、全ての二次元画像のＺｅｒｎｉｋｅモーメントの集合を三次元モデルの記述子とする。最後に、検索部６１０９は、表１に従って、上、下、左、右、前、後の二次元画像の特徴に対して順列・組み合わせを算出することにより、三次元モデルの記述子を２４個の特徴ベクトルに変換する。その後に、検索部６１０９は、検索対象である三次元モデルの前記２４個の特徴ベクトルのそれぞれと、モデルライブラリ６４０における各三次元モデル毎の特徴ベクトルとの距離を順に算出して２４個の距離を取得し、最小の距離を二つのモデルの距離として選択する。検索部１１０９は、検索対象である三次元モデルとモデルライブラリ６４０における全てのモデルとを比較して、その間の距離を算出した後に、モデルライブラリ６４０から三次元モデルにマッチした三次元モデルを検出して検索結果として出力装置を介して出力する。
【００８５】
同様に、モデル表面処理部６１０１は、選択可能な手段であっても良く、必要ではない場合に実施例２に係る三次元モデル検索装置６１０に含まれなくても良い。また、その他の方式を採用してモデルの正規化の処理を行う場合に、モデル正規化部６１０３において三次元モデルに対して正規化の処理を行った後に、モデル表面処理部６１０１により三次元モデルに対してポリゴンメッシュ化処理を行っても良い。
【００８６】
本発明の実施例２によれば、予めモデルライブラリ６４０における三次元モデルに対して各自の記述子を生成しておくため、検索を行うたびにモデルライブラリ６４０における三次元モデルに対して処理を行う必要がない。このため、検索対象である三次元モデルのみに対して処理を行えば良く、検索時の処理量を更に低減できるので、検索効率を向上できる。
【００８７】
また、実施例２の説明において、三次元モデルとモデル記述子とが関連付けられて同一のモデルライブラリ６４０に記憶される場合を例として説明したが、これに限定されるものではない。例えば三次元モデルとモデル記述子とを異なるモデルライブラリ６４０に記憶しても良い。この場合に、三次元モデル検索装置６１０は、モデル記述子が記憶されたモデルライブラリ６４０にアクセスし、検索対象である三次元モデル６３０にマッチしたモデル記述子を検索する。そして、検索されたモデル記述子を索引として、三次元モデルが記憶されたモデルライブラリ６４０から相応する三次元モデルを抽出して検索結果として出力する。
【００８８】
以上のように、図１から図６を用いて本発明による各実施例における三次元モデル検索システム、三次元モデル検索装置、及びモデルライブラリ生成装置を説明した。以下に、図７から図９を用いて三次元モデル検索方法の処理手順及びモデルライブラリ生成方法の処理手順を説明する。
【００８９】
図７は、三次元モデル検索方法の処理手順を示すフローチャートである。
【００９０】
図７に示したように、当該実施例による三次元モデルの検索方法は、モデル表面処理ステップＳ７０１と、モデル正規化ステップＳ７０３と、二次元画像生成ステップＳ７０５と、モデル記述ステップＳ７０７と、検索ステップＳ７０９とを含む。モデル表面処理ステップＳ７０１は、三次元モデルの表面をポリゴンメッシュの形式に変換する。モデル正規化ステップＳ７０３は、三次元モデルに対して回転及び/又は平行移動を行うことにより、三次元モデルの主軸方向を三次元空間の座標軸の方向に一致させ、三次元モデルの重心をシステム座標系の原点に一致させる。二次元画像生成ステップＳ７０５は、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する。モデル記述ステップＳ７０７は、二次元画像に基づいて三次元モデルのモデル記述子を生成する。検索ステップＳ７０９は、モデル記述子に基づいてモデルライブラリ６４０から三次元モデルにマッチした三次元モデルを検索する。
【００９１】
図８は、二次元画像生成処理の処理手順を示すフローチャートである。本発明の具体的な一実施例によれば、図８に示したように、二次元画像生成ステップＳ７０５は、ポリゴン処理ステップＳ７０５１と、ポリゴン充填ステップＳ７０５３とを含む。ポリゴン処理ステップＳ７０５１は、投影平面を通り抜けるポリゴンを投影平面の正方向における正方向ポリゴンと投影平面の負方向における負方向ポリゴンとに区分する。ポリゴン充填ステップＳ７０５３は、各座標軸の正方向と負方向とにおけるポリゴンを相応の投影平面に投影したポリゴンを充填して二次元画像を生成する。
【００９２】
当該実施例による三次元モデルの検索方法に含まれるモデル表面処理ステップＳ７０１は、図１を参照して説明した実施例１に係る三次元モデル検索装置１１０に含まれるモデル表面処理部１１０１における処理と同様である。また、モデル正規化ステップＳ７０３は、モデル正規化部１１０３における処理と同様であり、二次元画像生成ステップＳ７０５は、二次元画像生成部１１０５における処理と同様である。モデル記述ステップＳ７０７は、モデル記述部１１０７における処理と同様であり検索ステップＳ７０９は、検索部１１０９における処理と同様である。このことから、説明を簡潔にするために、これらステップの詳細な説明を省略する。
【００９３】
また、当該実施例による二次元画像生成ステップＳ７０５に含まれるポリゴン処理ステップＳ７０５１は、図４を参照して説明された実施例１に係る二次元画像生成部１１０５に含まれるポリゴン処理部１１０５１と同様である。また、ポリゴン充填ステップＳ７０５３は、ポリゴン充填部１１０５３における処理と同様である。このことから、説明を簡潔にするためにこれらステップの詳細な説明も省略する。
【００９４】
ここで、モデル表面処理ステップＳ７０１は、選択可能なステップであり、必要ではない場合に当該実施例による三次元モデル検索方法に含まれなくても良い。また、その他の方式を採用してモデルの正規化の処理を行う場合に、モデル正規化ステップＳ７０３において三次元モデルに対して正規化の処理を行った後に、モデル表面処理ステップＳ７０１により三次元モデルに対してポリゴンメッシュ化処理を行っても良い。
【００９５】
上述したように図１と図６を参照して本発明による実施例１と実施例２とに係る三次元モデル検索システムに対する説明を行った。これと同様に、実施例１の処理方式と類似した方式に従って、検索対象である三次元モデルとモデルライブラリ６４０における三次元モデルとに対して、以下の処理を実行する。すなわち、モデル表面処理ステップＳ７０１、モデル正規化ステップＳ７０３、二次元画像生成ステップＳ７０５、及びモデル記述ステップＳ７０７等の各ステップの処理を同時に行う。そして、最後に検索ステップＳ７０９において、モデルライブラリ６４０から検索対象である三次元モデルにマッチした三次元モデルを検出して検索結果として出力する。
【００９６】
実施例２の処理方式と類似した方式に従って、解析を行う前に、モデルライブラリ６４０における三次元モデルに対して、予め以下の処理を実行する。すなわち、モデル表面処理ステップＳ７０１、モデル正規化ステップＳ７０３、二次元画像生成ステップＳ７０５、及びモデル記述ステップＳ７０７等の各ステップの処理を行っておくことにより、モデルライブラリ６４０における三次元モデルの記述子を生成する。三次元モデルの解析を実際に行う場合に、解析しようとする三次元モデルのみに対して同様にＳ７０１からＳ７０７の処理を行えば良い。その後に、検索ステップＳ７０９において、モデルライブラリ６４０から、検索対象である三次元モデルにマッチした三次元モデルを検索して検索結果として出力する。この処理方法によれば、更に検索速度を速くし、検索効率を向上することができる。
【００９７】
図９は、モデルライブラリ生成方法の処理手順を示すフローチャートである。図９に示したように、当該実施例によるモデルライブラリ生成方法は、モデル表面処理ステップＳ９０１と、モデル正規化ステップＳ９０３と、二次元画像生成ステップＳ９０５と、モデル記述ステップＳ９０７とを含む。モデル表面処理ステップＳ９０１は、三次元モデルの表面をポリゴンメッシュの形式に変換する。モデル正規化ステップＳ９０３は、三次元モデルに対して回転及び/又は平行移動を行うことにより、三次元モデルの主軸方向を三次元空間の座標軸の方向に一致させ、三次元モデルの重心をシステム座標系の原点に一致させる。二次元画像生成ステップＳ９０５は、システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する。モデル記述ステップＳ９０７は、二次元画像に基づいて三次元モデルのモデル記述子を生成し、生成されたモデル記述子を対応する三次元モデルに関連付けてモデルライブラリ６４０に記憶する。
【００９８】
当該実施例によるモデルライブラリ生成方法に含まれるモデル表面処理ステップＳ９０１は、図６を参照して説明した実施例２のモデルライブラリ生成装置６２０に含まれるモデル表面処理部６２０１における処理と同様である。モデル正規化ステップＳ９０３は、モデル正規化部６２０３における処理と同様であり、二次元画像生成ステップＳ９０５は、二次元画像生成部６２０５における処理と同様である。モデル記述ステップＳ９０７は、モデル記述部６２０７における処理と同様である。このことから、説明を簡潔にするためにこれらステップの詳細な説明を省略する。
【００９９】
同様に、モデル表面処理ステップＳ９０１も選択可能なステップであり、必要ではない場合に当該実施例による三次元モデルの検索方法に含まれなくても良い。また、その他の方式を採用してモデルの正規化の処理を行う場合に、モデル正規化ステップＳ９０３において三次元モデルに対して正規化の処理を行った後に、モデル表面処理ステップＳ９０１により三次元モデルに対してポリゴンメッシュ化処理を行っても良い。
【０１００】
また、上記の装置における各装置、構成部は、ソフトウェア、ファームウェア、ハードウェア或いはそれらの組み合わせによって実現することができる。実現に使用可能な具体的な手法又は方式は当業者に周知の技術であるので、ここでは説明を省略する。ソフトウェア又はファームウェアにより実現する場合には、記憶媒体又はネットワークから専用のハードウェア構成を持つコンピュータに対してこのソフトウェアを構成するプログラムをインストールする。そして、このコンピュータは、各種プログラムがインストールされると、各種機能等を実行する。例えば、図１０を用いて、プログラムを実行するコンピュータの一例を説明する。図１０は、三次元モデル検索プログラム及びモデルライブラリ生成プログラムを実行するコンピュータの構成を示す図である。
【０１０１】
図１０に示すコンピュータ１０００において、中央処理装置（CPU）１００１は、読取専用メモリ（ROM）１００２に記憶されるプログラム又はメモリ部１００８からランダムアクセスメモリ（RAM）１００３に展開されたプログラムに従って、各種の処理を実行する。ＲＡＭ１００３には、必要に応じてＣＰＵ１００１が各種の処理を実行する場合等に必要なデータが記憶されている。ＣＰＵ１００１、ＲＯＭ１００２及びＲＡＭ１００３はバス１００４を介して互いに接続されている。入力／出力インターフェース１００５もバス１００４に接続されている。
【０１０２】
入力部１００６と、出力部１００７と、メモリ部１００８と、通信部１００９とは、入力／出力インターフェース１００５に接続されている。例えば、入力部１００６は、キーボード、マウス等を含む。例えば、出力部１００７は、ディスプレイ、例えばブラウン管（CRT）、液晶ディスプレイ（LCD）等とスピーカ等を含む。メモリ部１００８は、ハードディスク等を含む。通信部１００９は、ネットワークインターフェースカード、例えばLANカード、モデム等を含む。通信部１００９は、ネットワーク、例えばインターネットを経由して通信処理を実行する。入力／出力インターフェース１００５には、必要に応じて、ドライブ１０１０が接続されてもよい。ドライブ１０１０には、必要に応じて、取り外し可能な媒体１０１１が取り付けられてもよい。そして、取り外し可能な媒体１０１１の中から読み出されたコンピュータプログラムが必要に応じてメモリ部１００８にインストールされる。なお、取り外し可能な媒体１０１１は、例えば磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等である。
【０１０３】
ソフトウェアで一連の処理を実現する場合、例えばインターネットなどのネットワーク、又は例えば取り外し可能な媒体１０１１などの記憶媒体からソフトウェアを構成するプログラムをインストールする。
【０１０４】
このような記憶媒体は、図１０に示すような、その中にプログラムが記憶されているものであって、デバイスから離れて配送されることでユーザにプログラムを提供する取り外し可能な媒体１０１１には限定されるものではない。取り外し可能な媒体１０１１の例として、磁気ディスク（フロッピー（登録商標）ディスク含む）、光ディスク（コンパクトディスクリードオンリーメモリ（CD−ROM）やディジタルヴァーサタイルディスク（DVD）を含む）、光磁気ディスク（ミニディスク（登録商標）含む）及び半導体メモリを含む。または、記憶媒体はＲＯＭ１００２、メモリ部１００８に含まれるハードディスクなどであっても良い。その中にプログラムが記憶されており、且つこれらを含むデバイスと一緒にユーザに配送される。
【０１０５】
本発明は更に、機器で読取可能な命令コードが記憶されたプログラム製品を提供する。命令コードが機器で読取られて実行されると、本発明による実施例の方法を実行することができる。
【０１０６】
また、機器で読取り可能な命令コードが記憶されたプログラム製品を搭載する記憶媒体も本発明の開示の範囲に含まれる。この記憶媒体は、フロッピーディスク、光ディスク、光磁気ディスク、メモリカード、メモリスティック等を含むが、これらに限定されるものではない。
【０１０７】
以上の本発明の具体的な実施例の説明においては、一種の実施形態について説明した特徴は、同一或は類似の形態で一つ又は複数の他の実施形態で使用されたり、他の実施形態における特徴と組み合わせたり、置き換えたりすることができる。
【０１０８】
また、専門用語“含む／有する”が本文で使用される場合には、特徴、要素、ステップ又はコンポーネントの存在を意味するが、一つ又は複数の他の特徴、要素、ステップ又はコンポーネントの存在又は付加を排除するものではない。
【０１０９】
また、本発明の方法における各ステップは、明細書において説明した時間順に実行することには限定されず、その他の時間順序に従って、並行に或は独立に実行されてもよい。従って、本明細書で説明した方法の実行順序は本発明の技術的範囲を限定するものではない。
【０１１０】
上記に本発明の具体的実施例を説明することにより本発明を開示したが、前記の全ての実施例と例示はいずれも例示的なものであり、限定的なものではない。当業者は添付の特許請求の範囲の技術的思想に基づいて、本発明に対する各種の変更、改良或は均等物を設計することができる。これらの変更、改良或は均等物については本発明の保護範囲内に含まれるものである。
【０１１１】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１１２】
（付記１）検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させるモデル正規化部と、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する二次元画像生成部と、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成するモデル記述部と、
前記モデル記述子に基づいて、複数の三次元モデルを記憶するモデルライブラリから前記三次元モデルにマッチした三次元モデルを検索する検索部と、
を備える三次元モデル検索装置。
【０１１３】
（付記２）前記三次元モデルの表面をポリゴンメッシュの形式に変換するモデル表面処理部を更に備える、付記１に記載の三次元モデル検索装置。
【０１１４】
（付記３）前記二次元画像生成部は、
投影平面と交差するポリゴンを投影平面の正方向における正方向ポリゴンと投影平面の負方向における負方向ポリゴンとに区分するポリゴン処理部と、
前記システム座標系の各座標軸の正方向におけるポリゴンと負方向とにおけるポリゴンとを相応する投影平面に投影したポリゴンのそれぞれに対して充填を行って前記二次元画像を生成するポリゴン充填部と、
を備える、付記２に記載の三次元モデル検索装置。
【０１１５】
（付記４）前記ポリゴン充填部は、前記システム座標系の各座標軸の正方向におけるポリゴンと負方向におけるポリゴンとに対して、各ポリゴン毎の各頂点の投影平面への垂線の足を算出し、垂線の足により構成されるポリゴン領域を充填する、付記３に記載の三次元モデル検索装置。
【０１１６】
（付記５）前記ポリゴンは三角形又は四角形である、付記４に記載の三次元モデル検索装置。
【０１１７】
（付記６）前記二次元画像はグレー画像又は二値画像である、付記５に記載の三次元モデル検索装置。
【０１１８】
（付記７）前記検索部は、一行が一つの特徴ベクトルを形成する下記の表に基づいて、前記モデル記述部により生成された上、下、左、右、前、後の二次元画像の特徴に対して、順列及び組合せを算出し、前記三次元モデルのモデル記述子を２４個の特徴ベクトルに変換する、付記１〜６の何れかに記載の三次元モデル検索装置。
【表１】
2012043419.tif 000013
【０１１９】
（付記８）前記検索部は、前記三次元モデルの２４個の特徴ベクトルと前記モデルライブラリにおける三次元モデルの相応する特徴ベクトルとの距離を算出することにより、前記モデルライブラリから前記三次元モデルにマッチした三次元モデルを検索する、付記７に記載の三次元モデル検索装置。
【０１２０】
（付記９）三次元モデル検索装置が、
検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させ、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成し、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成し、
前記モデル記述子に基づいて、複数の三次元モデルを記憶するモデルライブラリから前記三次元モデルにマッチした三次元モデルを検索すること、
を含む三次元モデル検索方法。
【０１２１】
（付記１０）前記三次元モデル検索装置が、
前記三次元モデルの表面をポリゴンメッシュの形式に変換することを更に含む付記９に記載の三次元モデル検索方法。
【０１２２】
（付記１１）前記複数の二次元画像を生成するステップは、
投影平面と交差するポリゴンを投影平面の正方向における正方向ポリゴンと投影平面の負方向における負方向ポリゴンとに区分し、
前記システム座標系の各座標軸の正方向におけるポリゴンと負方向とにおけるポリゴンとを相応する投影平面に投影したポリゴンのそれぞれに対して充填を行って前記二次元画像を生成すること、
を含む、付記１０に記載の三次元モデル検索方法。
【０１２３】
（付記１２）前記二次元画像を生成する処理は、
前記システム座標系の各座標軸の正方向におけるポリゴンと負方向におけるポリゴンとに対して、各ポリゴン毎の各頂点の投影平面への垂線の足を算出し、垂線の足により構成されるポリゴン領域を充填する、付記１１に記載の三次元モデル検索方法。
【０１２４】
（付記１３）前記ポリゴンは三角形又は四角形である、付記１２に記載の三次元モデル検索方法。
【０１２５】
（付記１４）前記二次元画像はグレー画像又は二値画像である、付記１３に記載の三次元モデル検索方法。
【０１２６】
（付記１５）前記検索する処理は、
一行が一つの特徴ベクトルを形成する下記の表に基づいて、前記モデル記述部により生成された上、下、左、右、前、後の二次元画像の特徴に対して、順列及び組合せを算出し、前記三次元モデルのモデル記述子を２４個の特徴ベクトルに変換する、付記９〜１４の何れかに記載の三次元モデル検索方法。
【表１】
2012043419.tif 000014
【０１２７】
（付記１６）前記検索する処理は、
前記三次元モデルの２４個の特徴ベクトルと前記モデルライブラリにおける三次元モデルの相応する特徴ベクトルとの距離を算出することにより、前記モデルライブラリから前記三次元モデルにマッチした三次元モデルを検索する、付記１５に記載の三次元モデル検索方法。
【０１２８】
（付記１７）検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させるモデル正規化部と、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成する二次元画像生成部と、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成するモデル記述部と、
を備えるモデルライブラリ生成装置。
【０１２９】
（付記１８）前記三次元モデルの表面をポリゴンメッシュの形式に変換するモデル表面処理部を更に備える、付記１７に記載のモデルライブラリ生成装置。
【０１３０】
（付記１９）モデルライブラリ生成装置が、
検索対象である三次元モデルに対して回転及び/又は平行移動を行うことにより、前記三次元モデルの主軸方向を三次元空間のシステム座標系の座標軸の方向に一致させ、前記三次元モデルの重心を前記システム座標系の原点に一致させ、
前記システム座標系の各座標軸の正方向と負方向とのそれぞれにおいて、前記三次元モデルに対してポリゴンメッシュの投影を行って複数の二次元画像を生成し、
前記二次元画像に基づいて前記三次元モデルのモデル記述子を生成すること、
を含むモデルライブラリ生成方法。
【０１３１】
（付記２０）前記モデルライブラリ生成装置が、
前記三次元モデルの表面をポリゴンメッシュの形式に変換することを更に含む、付記１９に記載のモデルライブラリ生成方法。
【符号の説明】
【０１３２】
１１０、６１０  三次元モデル検索装置
１１０１、６１０１、６２０１  モデル表面処理部
１１０３、６１０３、６２０３  モデル正規化部
１１０５、６１０５、６２０５  二次元画像生成部
１１０５１  ポリゴン処理部
１１０５３  ポリゴン充填部
１１０７、６１０７、６２０７  モデル記述部
１１０９、６１０９  検索部
６２０  モデルライブラリ生成装置
１０００  コンピュータ
１００１  ＣＰＵ
１００２  ＲＯＭ
１００３  ＲＡＭ
１００４  バス
１００５  入力／出力インターフェース
１００６  入力部
１００７  出力部
１００８  メモリ部
１００９  通信部
１０１０  ドライブ
１０１１  取外し可能な媒体
【図１】
2012043419.tif 000015
【図２】
2012043419.tif 000016
【図３】
2012043419.tif 000017
【図４】
2012043419.tif 000018
【図５】
2012043419.tif 000019
【図６】
2012043419.tif 000020
【図７】
2012043419.tif 000021
【図８】
2012043419.tif 000022
【図９】
2012043419.tif 000023
【図１０】
2012043419.tif 000024