JP2002288687A

JP2002288687A - 特徴量算出装置および方法

Info

Publication number: JP2002288687A
Application number: JP2001083710A
Authority: JP
Inventors: Hiroshi Matsuzaki; 弘松▲崎▼; Takao Shibazaki; 隆男柴▲崎▼; Akio Kosaka; 明生小坂; Yukito Furuhashi; 幸人古橋
Original assignee: Olympus Optical Co Ltd
Current assignee: Olympus Corp
Priority date: 2001-03-22
Filing date: 2001-03-22
Publication date: 2002-10-04
Also published as: US20020174406A1; US6906710B2

Abstract

(57)【要約】【課題】すべてのオブジェクトデータに対して系統的
な特徴量の算出を行うことができ、また、多様な特徴量
を定義することが可能で、類似オブジェクトの検索に用
いるときに、より検索精度の良い特徴量を算出すること
が可能な特徴量算出装置、および方法を提供する。【解決手段】オブジェクトの頂点情報を用いて前記オ
ブシェクトの形状を表す３次元オブシェクトデータをボ
リューム形式のデータに変換し、前記変換されたボリュ
ーム形式のデータにおいて前記オブジェクトの特徴量を
算出することを特徴とする特徴量算出装置を用いる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、３次元オブジェク
トの認識や、類似３次元オブジェクトの検索に用いるこ
とが可能な３次元オブジェクトの特徴量を３次元オブジ
ェクトデータより算出する装置および方法に関する。

【０００２】

【従来の技術】近年、デジタル画像が様々な場面で利用
されており、さらに、３次元オブジェクトを表現するデ
ータ形式に関しても、従来からのＣＡＤデータに加え、
商品の３次元オブジェクトデータとして、また、考古学
的遺産、美術、芸術品に関する３次元オブジェクトデー
タ化によるデジタルアーカイブ等、盛んに利用されてい
る。また、これらのデータは増大する一方であり、デー
タの効率的な管理や、利用者の要求するデータを効率よ
く検索する要求が高まっている。

【０００３】このような要求に答えるべく、様々な技術
が提案されており、「類似オブジェクト」の検索技術に
関しても、オブジェクトの持つ特徴を算出し、これらの
特徴量に従って検索を行う方法が提案されている。例え
ば、特開平６-２１５１０５号公報では、３次元幾何情
報として、構成されるポリゴンの頂点の幾何情報、即ち
頂点の座標と、頂点の位相情報、即ち頂点の連結情報を
主情報として利用し、さらに付加情報として、頂点にお
ける法線ベクトル情報、頂点の色情報等を３次元オブジ
ェクトの特徴として利用し、データベース内のオブジェ
クト検索のために利用するものである。また、特開２０
００-２２２４２８では、３次元モデルの検索の際に検
索モデルを簡易化し、簡易化されたモデルから形状を表
す特徴を抽出し、検索モデルと被検索モデルとの特徴量
を比較して類似モデルを検索する手法が述べられてい
る。この方法では、特徴として、モデルの重心と、モデ
ルを構成する各面までの距離の分布、モデルを構成する
隣接する面の法線のなす角度の平均値等が特徴量の例と
して示されている。さらに、"A Content-based Search
Engine for VML Databases " Proceedings. IEEE Compu
ter Society Conrenceon Computer Vision and Pattem
Recognition p.５４１-５４６,１９９８では、VRMLで記
述された３次元オブジェクトの特徴量を抽出し、類似の
オブジェクトを検索する手法について述べられている。
この例においても、３次元オブジェクトの形状を表す特
徴量として、オブジェクトの重心と各頂点までの距離の
標準偏差や、オブジェクトを構成するポリゴンパッチの
面積と、ポリゴンパッチの頂点と重心との距離に相当す
る値との積を統計処理して算出される特徴量が利用され
ている。

【０００４】

【発明が解決しようとする課題】上述した従来技術で
は、３次元モデルの特徴を、特に形状特徴に関し、ワイ
ヤフレームの構造的情報、即ち、頂点の位置の分布、ま
たは、頂点の接続情報により求めている。ところがこれ
らの情報は、頂点位置を利用するという場合、頂点の配
列には規則性、等方性が無いこと、また、頂点の接続情
報を利用するという場合においても、接続関係の生成法
に規則性は特に定められておらず、従って、オブジェク
トを構成するボリゴンパヅチの大きさも均一でなく、そ
のため、すべてのオブジェクトデータに対して特徴量を
系統的に算出することが困難である。さらに、これらの
情報のみから算出できる特徴量の数は限られ、多くの特
徴量を定義することは困難である。従ってこれらの少な
い特徴量のみを用いた検索を行う場合では精度の良い、
効率的な検索を行うことは困難である。

【０００５】さらに、ワイヤフレーム情報が多くの場
合、オブジェクト内部の構造も表現しており、類似形状
オブジェクトの検索を行う際には、通常、外形の類似性
の検索を行うものであり、その場合不要な情報を含んだ
データを用いて特徴量算出を行うことになるために、検
索精度が悪くなるという課題が発生する。例えば、従来
例では重心としてオブジェクトに外接する球体の中心を
重心と定義しているが、オブジェクトが球体に近い場合
にはオブジェクトの重心と定義された重心とは近い位置
になるため、重心としての形状的意味を持つが、オブジ
ェクトが球体形状と異なる形状を持っていた場合には、
オブジェクトの真の重心と定義された重心とは位置的に
異なる値となり、適切な特徴量と呼ぶことはできないと
いう課題を持つことになる。

【０００６】本発明の目的は、前記の点に鑑み、すべて
のオブジェクトデータに対して系統的な特徴量の算出を
行うことができ、また、多様な特徴量を定義することが
可能で、類似オブジェクトの検索に用いるときに、より
検索精度の良い特徴量を算出することが可能な特徴量算
出装置、および方法を提供することである。

【０００７】

【課題を解決するための手段】本発明による特徴量算出
装置および方法は、３次元オブジェクトのデータより特
徴量を算出する装置であり、前記オブジェクトの頂点情
報を用いて前記オブシェクトの形状を表す３次元オブシ
ェクトデータをボリューム形式のデータに変換する変換
手段と、前記変換されたボリューム形式のデータにおい
て前記オブジェクトの特徴量を算出する特徴量算出手段
とを有することを特徴とし、より多くの特徴量を算出可
能になり、かつより適切に形状特徴を表現できる。

【０００８】また、３次元的なオブジェクトデータの特
徴量を算出する方法において、入力される３次元オブジ
ェクトデータは、頂点情報及び頂点連結情報と、３次元
オブジェクトを構成する面のテクスチャ情報とで構成さ
れており、前記３次元オブジェクトデータをボリューム
データに変換する工程と、前記生成されたボリュームデ
ータから、特徴量データ群を算出する工程とを有するこ
とを特徴とし、任意のデ一タを扱うことができる。即
ち、特徴量算出装置に入力する際に、３次元オブジェク
ト生成装置を用いて生成された３次元オブジェクトを入
力することが可能である。

【０００９】

【発明の実施の形態】本発明の実施形態を以下に図面を
用いて説明する。

【００１０】本発明の第１の実施形態のシステム構成図
を図１に示す。

【００１１】図に示すように、１は演算装置であり、２
はＣＲＴやＬＣＤ等のディスプレイ、さらに、３次元立
体表示等のオブジェクトデータ表示部である。また、３
は、キーボード、マウス、タブレット、音声入力等のデ
ータ入力、または操作入力装置をシステム構成要素とし
て持つ。また、前記表示装置２には、データベース内の
オブジェクトを一覧表示するためのオブジェクトカタロ
グ閲覧ウィンドウ、入力したオブジェクトを表示するた
めのオブジェクトレンダリングウィンドウ、検索条件を
設定するためにオブジェクトを複数指定し、それらを一
覧表示するための条件設定ウィンドウ、複数の種類の形
態で検索結果を表示するための検索結果表示ウィンドウ
等の各種ウィンドウから構成されている。

【００１２】また、前記演算装置１は、内部でさらに複
数の機能部に分割されており、３次元オブジェクトデー
タの入力部４、オブジェクトデータからボリュームデー
タヘの変換部５、変換されたボリュームデータを解析す
る機能部６、特徴量の算出部７、算出された特徴量をデ
ータベースに登録、蓄積する制御を行う登録部８から構
成される。また、オブジェクトデータ、および算出され
た特徴量を登録、蓄積するためのデータベースは、図１
に示されるように、原データ、および変換されたボリュ
ームデータが蓄積されているデータベース９、及び算出
された特徴量を蓄積するためのデータベース１０として
分散して配置されている。また、原データデータベース
９、および特徴量データベース１０は、複数に分割して
配置されることも可能である。また、ここでは、分散型
データベースの形態として記述してあるが、これは必ず
しも分散型である必要はなく単一のデータベースで構築
することも可能である。また、前記３次元オブジェクト
データ入力手段４はさらに、オブジェクトデータベース
閲覧手段を有し、利用者（ユーザ）は、この閲覧機能に
より、原データデータベース９、または特徴量データベ
ース１０を参照し、登録されている様々な３次元オブジ
ェクトデータを閲覧することができる。そして、この閲
覧機能により表示されたオブジェクト群を閲覧すること
によりデータベース内の任意のオブジェクトを選択しそ
のデータを演算装置内に取り込む。選択されたオブジェ
クトデータに関して、特徴量の算出がなされていないも
のであれば、詳細は後述するが、本発明の手法により特
徴量の算出を行う。また、入力、登録されたオブジェク
トデータの持つ具体的情報は、頂点座標情報列、頂点色
情報列、頂点接続情報列、ポリゴンパッチのテクスチャ
情報から構成されたデータである。また、入力されるオ
ブジェクトデータは、指定されたデータベース以外から
も、電子カタログのような外部のオブジェクトデータベ
ース１１や、インターネットのｗｅｂサイト上に公開さ
れているような任意のデータベース１２に登録されてい
る既存のオブジェクトを選択することも可能であるし、
１３で示す、利用者がＣＡＤや、３次元オブジェクト生
成ツールを利用して任意に作成したオブジェクトデー
タ、さらには、レンジファインダのような３次元オブジ
ェクト撮影、入力装置を用いて入力された２次元画像形
式の３次元オブジェクトデータや、ＣＴやＭＲＩ等の医
用データのようなスライス画像が積層された形態のボリ
ューム形式のデータ、または他の分野で扱われる任意の
ボリュームデータ等、３次元的な形態を表現するデータ
を任意に扱うことが可能である。

【００１３】次に、図２のフローチャート、及び図３に
示す椅子の３次元オブジェクトを具体的なオブジェクト
の例として詳細な処理の流れを述べる。まず、図２に示
すように、３次元オブジェクトデータを入力する（１
４）。ここで、データを入力する方法としては、データ
ベース閲覧手段により表示されたオブジェクト群より選
択する方法、ユーザが任意の形状のオブジェクトデータ
を生成して入力する方法、既存のオブジェクトデータを
探索しそれらのデータを入力する方法がある。そして、
入力された３次元オブジェクトデータは、入力デ一夕判
断手段により、データ形式の判断が行わる（１５）。入
力されたオブジェクトデータタイプが予めボリュームデ
ータであった場合にはボリュームデータに変換する必要
はないが、表示装置にオブジェクトをレンダリングする
場合にはワイヤフレームデータに変換する必要があるの
で、ワイヤフレームデータに変換する（１６）。入力さ
れるオブジェクトデータタイプがワイヤフレームデータ
であれば、１７に進み、レンダリングを行うために、こ
こで内部形式に変換され、ディスプレイに表示される。
表示装置上では、３次元オブジェクトが３次元表示さ
れ、操作入力装置、例えばマウスで画面上で指示を行う
ことにより、オブジェクトを任意視点で表示、拡大縮小
等表示上の操作を行うことができる。また、入力される
オブジェクトデータの各頂点座標は、初期状態で座標系
（Ｘ，Ｙ，Ｚ）が設定されているが、オブジェクトの上
下、前後、左右が正確に設定されていない場合もあるた
め、その場合にはこれらの方向を設定する必要がある。

【００１４】次に、操作入力装置による視点変更操作に
より、オブジェクトの前後、左右、上下の方向を設定す
ることによりオブジェクトの３次元座標系（ｘ，ｙ，
ｚ）を設定する。具体的には、オブジェクトの上下方向
と表示装置の上下方向を一致させ、かつ正面視点になる
ように表示し、この状態で正面設定メニュー、またはボ
タンで設定の指定を行い、すべての頂点座標を変換す
る。この変換により、原オブジェクトデータの持つ頂点
座標データ列Ｖ_１（Ｘ_１，Ｙ_１，Ｚ_１），・・・，Ｖ_Ｎ
（Ｘ_Ｎ，Ｙ_Ｎ，Ｚ_Ｎ）は、Ｖ_１（ｘ_１，ｙ_１，ｚ_１），
・・・，Ｖ_Ｎ（ｘ_Ｎ，ｙ_Ｎ，ｚ_Ｎ）に変換される。ま
た、頂点接続情報データ列は、Ｐ_１（Ｖ_１１，Ｖ_１２，
Ｖ_１３），・・・，Ｐ_Ｍ（Ｖ_Ｎ１，Ｖ_Ｎ２，Ｖ_Ｎ３）、
テクスチャ情報を、Ｔ_１（Ｖ_１１，Ｖ_１２，Ｖ_１３），
・・・，Ｔ_Ｍ（Ｖ_Ｎ１，Ｖ_Ｎ２，Ｖ_Ｎ３）と表すことに
する。

【００１５】次に、ボリュームデータヘの変換処理方法
を述べる。先ず、すべての頂点データの各座標成分を比
較し、ｘ，ｙ，ｚの最大値、最小値を求めることにより
オブジェクトに外接する直方体を設定し（１９）、ボク
セルデータヘの変換を実行する（２０）。具体的な変換
方法は、直方体の何れかの面に対して平行な切断面と、
ポリゴンを生成する線分との交点をすべて求め、オブジ
ェクトの内部と、外部とを判別し、この面内を２値化す
る処理を、オブジェクトを切断する面を適当に設定した
スライスピッチにより移動し、これらのすべての切断面
に対して同様な処理を行うことによりボクセルより構成
されるボリュームデータとして生成する方法である。

【００１６】次に、図３の椅子のオブジェクトで説明を
行う。図３に示すように、入力された３次元オブジェク
トをレンダリングした画像が２８に示すものであり、こ
の椅子オブジェクトは、２９で示すようなワイヤフレー
ムから構成されている。このオブジェクトに対して外接
直方体を設定すると、３０のようになる。この外接直方
体の上面に平行な面で、上部より順次オブジェクトとの
切断面を生成し、オブジェクト内部と外部とをそれぞ
れ、黒と白で表示すると、３１〜３４に示す図のように
なる。切断する面の２次元画像の分解能、及び切断する
面の間隔を適当に設定することによりボクセルデータの
集合となり、これがボリュームデータである。そして、
図２に戻ってこのようにして生成されたボリュームデー
タより特徴量を算出する（２１）。ここで、ボリューム
データの持つ情報として、ｘ，ｙ，ｚ座標系における各
方向の画素数を、Ｋ，Ｌ，Ｍ、画素間隔を、ｘ_ｄｉｖ，
ｙ_ｄ _ｉｖ，ｚ_ｄｉｖとすると外接直方体各辺の長さ：
Ｘ，Ｙ，Ｚは、Ｘ＝Ｋ・ｘ_ｄｉ _ｖ，Ｙ＝Ｌ・ｙ_ｄｉｖ，
Ｚ＝Ｍ・ｚ_ｄｉｖとして表すことができる。Ｋ，Ｌ，Ｍ
は、任意に設定することが可能である。変換されたボリ
ュームデータを、

【数１】

【００１７】とする。ここで算出される特徴量として、
外接直方体の体積Ｖ_ｒｅｃｔ＝ＸＹＺ、外接直方体の表
面積Ｓ_ｒｅｃｔ＝２（ＸＹ＋ＹＺ＋ＺＸ）を用いること
ができる。これらの特徴量は、オブジェクトの大きさに
関する特徴として利用することができる。また、ボリュ
ームデータを楕円体として近似することにより特徴量を
定義することも可能であるので、前処理として近似楕円
体を算出しておく。ここでは、近似楕円体の中心の３次
元座標

【数２】

【００１８】、近似楕円体の長軸、および短軸の方向ベ
クトル、また、３つの軸の長さＸ^ｅｌ ^{ｌｉｐｓｅ}，Ｙ
^{ｅｌｌｉｐｓｅ}，Ｚ^{ｅｌｌｉｐｓｅ}が算出される。ま
た、オブジェクト重心位置

【数３】

【００１９】も前処理として算出する。外接直方体中心
をオブジェクト中心

【数４】

【００２０】と定義することにすれば、オブジェクト中
心、重心、近似楕円体中心の３つの点の位置が特徴を算
出するための基本量として利用できることになる。ボリ
ュームデータの特徴量としては、オブジェクトの体積Ｖ
_ｏｂｊ、近似楕円体の体積Ｖ_ｅ _{ｌｌｉｐｓｅ}＝πＸ
_{ｅｌｌｉｐｓｅ}，Ｙ_{ｅｌｌｉｐｓｅ}，
Ｚ_{ｅｌｌｉｐｓｅ}，／６、オブジェクトの表面積Ｓ
_ｏｂｊ、近似楕円体の表面積Ｓ_{ｅｌｌｉｐｓｅ}、中心、
重心、近似楕円体中心に対する分散、中心、重心、近似
楕円体中心それぞれを原点とする３軸周りの慣性モーメ
ント、およびこれらの慣性モーメントの各軸方向に分割
したヒストグラムを定義することができる。これらの特
徴量は、下記の定義式により算出される。

【００２１】

【数５】

【００２２】

【数６】

【００２３】として、オブジェクト中心、重心、近似楕
円体中心を与えることにより、各点に対する分散特徴と
なる。但し、

【数７】

【００２４】慣性モーメント：

【数８】

【００２５】但し、

【数９】は、点ｒ（ｉ，ｊ，ｋ）からＸ_ｉ軸に下ろした垂線の足
の位置ベクトル。

【００２６】Ｘ軸を、直方体中心、重心、近似楕円体中
心をそれぞれ原点とする３つの直交する座標軸とするこ
とにより９つの特徴量が定義できる。

【００２７】慣性モーメントのヒストグラムは、

【数１０】

【００２８】但し、Ｗはヒストグラム作成における一つ
の領域の幅(単位：ピクセル)、Ｎは分割数ＮＷ＝Ｋとし
て算出できる。

【００２９】また、オブジェクトの形状複雑度Ｆ
_{ｃｏｍｐｌｅｘｉｔｙ}を表すと考えることのできるオブ
ジェクト表面積とオブジェクト体積との比

【数１１】

【００３０】を算出することができる。（但し、球の場
合に、１となるように係数を設定）外接直方体の中心に
対する、重心、または近似楕円体の中心位置の偏りの比
率は、それぞれ（Ｇ_ｘ．Ｃ^ｒｅｃｔ _ｘ）／Ｘ_ｒｅｃｔ，（Ｇ_ｙ．Ｃ
^ｒｅｃｔ _ｙ）／Ｙ_ｒｅｃｔ，（Ｇ_ｚ．Ｃ^ｒｅｃｔ _ｚ）／
Ｚ_ｒｅｃｔ（Ｇ_ｘ．Ｃ^{ｅｌｌｉｐｓｅ} _ｘ）／Ｘ_ｒｅｃｔ，（Ｇ_ｙ．
Ｃ^{ｅｌｌｉｐｓｅ} _ｙ）／Ｙ_ｒｅｃｔ，（Ｇ_ｚ．Ｃ
^{ｅｌｌｉｐｓｅ} _ｚ）／Ｚ_ｒｅｃｔで与えられ、これらの特徴はオブジェクトの形状の偏り
の方向を表現するものとして利用できる。

【００３１】さらに、各軸方向の大きさの比：Ｘ
_ｒｅｃｔ／Ｙ_ｒｅｃｔ，Ｙ_ｒｅｃｔ／Ｚ_ｒ _ｅｃｔ，Ｚ
_ｒｅｃｔ／Ｘ_ｒｅｃｔ、近似楕円体の各軸の比：Ｘ_{ｅｌｌｉｐｓｅ}／Ｙ
_{ｅｌｌｉｐｓｅ}，Ｙ_{ｅｌｌｉｐ} _ｓｅ／
Ｚ_{ｅｌｌｉｐｓｅ}，Ｚ_{ｅｌｌｉｐｓｅ}／Ｘ
_{ｅｌｌｉｐｓｅ}、真球率：ｍｉｎ（Ｘ_{ｅｌｌｉｐｓｅ}，
Ｙ_{ｅｌｌｉｐｓｅ}，Ｚ_{ｅｌｌｉｐｓｅ}）、および、真立
方体率：ｍｉｎ（Ｘ，Ｙ，Ｚ）／ｍａｘ（Ｘ，Ｙ，Ｚ）
の４つの特徴は、オブジェクトの細長さの度合いと方
向、外接直方体占有率Ｖ_ｏｂｊ／Ｖ_ｒｅｃｔは、外接直方体
との類似性、近似楕円体体積率：Ｖ_ｏｂｊ／Ｖ
_{ｅｌｌｉｐｓｅ}は近似楕円体との類似性を示す特徴とし
て利用できる。また、共起行列、さらには共起行列より
算出される方向性２次モーメントの比や、３次元フーリ
エ特徴としてのＭＰＳ(Metric Pattern Signature)やＡ
ＰＳ(Angular Pattern Signature)を特徴として定義す
ることも可能でる。

【００３２】ここまでボリューム変換されたデータより
算出される特徴量を例として述べたが、オブジェクトを
ある方向から見たときの特徴量として、投影距離画像を
考えることができる。ボリュームデータをオブジェクト
を任意の面に対して投影した場合、投影面よりオブジェ
クト表面で、投影面より遠い位置にある方の表面までの
距離値を持つような距離画像を生成することができる
が、この距離画像から算出される特徴量もオブジェクト
の特徴量として利用することが可能である。２２では、
オブジェクトの外接直方体の６つの各面にオブジェクト
を投影した距離画像を生成し、各距離画像から特徴量を
算出する（２３）。ここでも、具体的な例として図３の
椅子オブジェクトで考えることにすれば、このボリュー
ムデータを外接直方体の正面、背面、左面、右面、上
面、下面の６つの面に投影した距離画像を生成すると、
３５〜４０の画像となる。これらの画像は、画素の明度
で距離情報を表現しており、明るい画素ほど投影面より
遠い位置にある点であるものとして描画している。距離
画像から算出される特徴量としては、距離値のヒストグ
ラムや、距離画像の各画素で定義できる曲率のヒストグ
ラムを用いることができる。さらに、距離画像を、複数
の解像度に変換するウェーブレット変換を行い、各解像
度における各領域の値をベクトルとして表した量を特徴
として利用することも可能である。

【００３３】以上、ボリュームデータに変換されたデー
タより算出される特徴量について述べてきたが、原ワイ
ヤフレームデータから算出される特徴量も算出すること
が可能であり、これらのワイヤフレーム的特徴と、ボリ
ューム的特徴量とを合成して定義できる特徴を算出する
ことにより、より多様性のある特徴を算出することが可
能であり、類似オブジェクト検索においても有効な手段
となる。

【００３４】そこで、ワイヤフレーム的特徴量を算出し
ておくことにする（２４）。ワイヤフレームから算出さ
れる特徴としては、入力されるオブジェクトデータは、
ポリゴンパッチの集合として与えられているため、各ポ
リゴンパッチの面積の総和Ｓや、ポリゴンパッチの面積
とポリゴンパッチの単位法線ベクトルの積の総和で与え
られる拡張ガウス球Ｓ_{ｇａｕｓｓ}等が定義できる。

【００３５】

【数１２】

【００３６】但し、Ｎはパッチ数、Ｓ_ｋはｋ番目のパッ
チの面積、ｎ_ｋはｋ番目のパッチの単位法線ベクトルボ
リュームデータ、ワイヤフレームデータそれぞれより特
徴量を算出したがこれらの特徴を組み合わせて定義され
る特徴を２５で算出する。

【００３７】以上、２５の機能で算出される特徴量は何
れも３次元画像の持つ特有な特徴であり、他にも、３次
元的な特徴を表すような値であればどのような値を用い
てもよい。

【００３８】算出された特徴量は、２６において、演算
装置１の内部で特徴量ファイルとして生成され、２７で
データベースに登録され、特徴量算出の処理を終了す
る。

【００３９】データベース登録の際には、特徴量ファイ
ルと共に、変換されたボリュームデータファイルも併せ
て、原オブジェクトデータと関連付けを行った上でデー
タベース内に登録、保存される。さらに、これまで、主
に形状に関する特徴について述べてきたが、入力される
原オブジェクトデータはテクスチャ情報を持っているた
め、この情報を特徴量として加えることは可能であり、
その他、算出される特徴量は、幾つかの種類に分類が可
能なものである。異なる種類の特徴、即ち形状、大き
さ、テクスチャ（色に関する特徴も含む）、位置等を特
徴ベクトルの要素として定義し、さらにこれらの特徴量
を幾つかの種類にグループ分けしておくことにより、特
徴量の種類を検索条件として検索をすることも可能とな
りより多様性のある検索を行うことが可能となる。次
に、算出された特徴量を利用する際には、各特徴を成分
として持つn次元ベクトルとして表現することができ、
この特徴ベクトルを利用して、類似オブジェクト検索を
行うことができる。

【００４０】次に、類似オブジェクト検索法について
は、図４を用いて説明する。４１でオブジェクトデータ
の入力を行い、４２で４３のデータベースを参照し、入
力されたデータの特徴量が算出済みであるか否かの判断
を行う。特徴量が算出されていなければ４４で本発明の
方法により特徴量を算出し、特徴ベクトルとして設定す
る。特徴量が算出済みであれば特徴算出は省略でき、４
５でデータベース内のすべてのオブジェクトの持つ特徴
ベクトルとの比較を行い、４６で検索結果を類似度の順
に出力する。４４で算出された特徴が、ｆ_１〜ｆ_ＭのＭ
個であり、検索を行うデータベース内のデータがＩ_１〜
Ｉ_ＮのＮ個あるとして、特徴量行列Ｆを

【数１３】

【００４１】式(１)とすると、q番目の３次元画像
Ｉ_ｑ、の特徴量ベクトル

【数１４】

【００４２】

【数１５】

【００４３】は式(２)として表現される。式(２)におい
て、ｋ_ｊを乗ずることにより、各特徴項は正規化された
ものとなっている。

【００４４】但し、式内の各項は、

【数１６】

【００４５】

【数１７】

【００４６】として定義される値であり、ｗ_ｊは各特徴
の重み係数である。前記式(２)の特徴ベクトルにより類
似度を定義することができる。すなわち、検索の対象と
する画像がＩ_ｐであるとき、データベース内の他の画像
Ｉ_ｑとの類似度関数を、

【数１８】

【００４７】とすれば、Ｓｉｍ（ｐ，ｑ）が小さいほど
類似性が高いことになる。データベース内のすべての画
像に対してこの関数を計算することにより類似度の順序
を決定することができる。

【００４８】

【発明の効果】３次元オブジェクトデータを格子状の規
則性のあるボリュームタイプのデータに変換した後で、
変換されたデータに対して特徴量算出演算を行うことに
より、すべてのオブジェクトデータに対して系統的な特
徴量の算出を行うことができ、また、多様な特徴量を定
義することが可能で、類似オブジェクトの検索に用いた
ときに、より検索精度の良い特徴量を算出することが可
能な特徴量算出装置、および方法を提供することを目的
とする。

【図面の簡単な説明】

【図１】本発明の実施形態に係る

【図２】本発明の実施形態に係る

【図３】本発明の実施形態に係る

【図４】本発明の実施形態に係る

【符号の説明】

１…演算装置、２…表示装置、４…入力部、５…変換
部、６…機能部、７…算出部、８…登録部、９、１０、
１２…データベース

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁷ 識別記号ＦＩテーマコート゛(参考）Ｇ０６Ｔ 7/60 １５０Ｇ０６Ｔ 7/60 １５０Ｚ (72)発明者小坂明生東京都渋谷区幡ヶ谷２丁目43番２号オリンパス光学工業株式会社内 (72)発明者古橋幸人東京都渋谷区幡ヶ谷２丁目43番２号オリンパス光学工業株式会社内Ｆターム(参考） 5B075 NK06 PR06 QM08 5B080 AA17 AA18 GA22 5L096 AA09 BA18 CA21 DA02 FA18 FA55 FA59 FA60 FA62 HA09 JA11

Claims

【特許請求の範囲】

【請求項１】３次元オブジェクトデータの特徴量を算
出する装置であり、入力された３次元オブジェクトデー
タであり、ワイヤーフレームデータ又はポリゴンバッチ
等の、頂点情報および頂点連結情報と３次元オブジェク
トを構成する面のテクスチャ情報とで構成された３次元
オブジェクトデータをボリュームデータに変検する手段
と、前記変換されたボリュームデータから、特徴量データ群
を算出する手段とを有することを特徴とする特徴量算出
装置。
【請求項２】少なくとも算出された特徴量を原３次元
オブジェクトデータと関連付けてデータベースに登録す
る手段をさらに有することを特徴とする請求項１記載の
特徴量算出装置。
【請求項３】前記ボリュームデータに変換する手段
は、前記オブジェクトを切断する平面と前記オブジェク
トデータのワイヤーフレームとを構成する線分との交点
群を導出する手段と、前記交点群よりオブジェクト内部と外部との判断を行う
ことにより生成するボリュームデータにおける前記切断
面内の情報を生成する手段とを有することを特徴とする
請求項１に記載の特徴量算出装置。
【請求項４】前記３次元オブジェクトデータより生成
されたボリュームデータを任意の方向に投影し、その投
影された投影面から前記３次元オブジェクトの表面まで
の距離を画素値として持つ距離画像を１種類以上生成す
る手段と、前記距離画像の特徴量を算出する手段とを有することを
特徴とする請求項１に記載の特徴量算出装置。
【請求項５】前記算出される特徴量は、ボリュームデ
ータに変換したデータから算出される特徴量と、原ワイ
ヤーフレームデータより算出される特徴量とを組み合わ
せて生成されることを特徴とする請求項１に記載の特徴
量算出装置。
【請求項６】前記入力される３次元オブジェクトデー
タは、利用者による手書きステッチによる３次元オブジ
ェクト生成ツール、または、ＣＡＤによる３次元オブジ
ェクト生成ツールによって生成されたもの、または、３
次元オブジェクト入力装置により入力されたものである
ことを特徴とする請求項１乃至５までの何れか１つに記
載の特徴量算出装置。
【請求項７】前記３次元オブジェクトデータとして、
ボリューム形式のデータが入力された場合には、直接特
徴量の算出を行うことを特徴とする請求項１乃至６まで
の何れか１つに記載の特徴量算出装置。
【請求項８】前記算出される特徴量は、形状、または
大きさ、またはオブジェクト表面のテクスチャ、または
前記の何れか２つ以上を統合したものであることを特徴
とする請求項１乃至７までの何れか１つに記載の特徴量
算出装置。
【請求項９】３次元的なオブジェクトデータの特徴量
を算出する方法において、入力される３次元オブジェクトデータは、頂点情報及び
頂点連結情報と、３次元オブジェクトを構成する面のテ
クスチャ情報とで構成されており、前記３次元オブジェ
クトデータをボリュームデータに変換する工程と、前記生成されたボリュームデータから、特徴量データ群
を算出する工程とを有することを特徴とする特徴量算出
方法。
【請求項１０】少なくとも算出された特徴量を原３次
元オブジェクトデータと関連付けしてデータベースに登
録する手段を有することを特徴とする請求項９に記載の
特徴量算出方法。
【請求項１１】前記ボリュームデータヘの変換手段
は、前記オブジェクトを切断する平面と前記オブジェクトデ
ータのワイヤフレームとを構成する線分との交点群を導
出する工程と、前記交点群よりオブジェクト内部と外部との判断を行う
ことにより生成するボリュームデータにおける前記切断
面内の情報を生成する工程とを有し、ボリュームデータ
に変換することを特徴とする請求項９に記載の特徴量算
出方法。
【請求項１２】前記３次元オブジェクトデータより生
成されたボリュームデータを任意の方向に投影し、この
投影された投影面から前記３次元オブジェクトの表面ま
での距離を画素値として持つ距離画像を１種類以上生成
する工程と、前記距離画像の特徴量を算出する工程とを
有することを特徴とする請求項９に記載の特徴量算出方
法。
【請求項１３】前記算出される特徴量は、ボリューム
データに変換したデータから算出される特徴量と、原ワ
イヤフレームデータより算出される特徴量とを組み合わ
せて生成されることを特徴とする請求項９に記載の特徴
量算出方法。
【請求項１４】前記入力される３次元オブジェクトデ
ータは、利用者による手書きスケッチによる３次元オブ
ジェクト生成ツール、または、ＣＡＤによる３次元オブ
ジェクト生成ツールによって生成されたもの、または、
３次元オブジェクト入力装置により入力されたものであ
ることを特徴とする請求項９乃至１３までのいずれか１
つに記載の特徴量算出方法。
【請求項１５】前記３次元オブジェクトデータとし
て、ボリューム形式のデータが入力された場合には、直
接特徴量の算出を行うことを特徴とする請求項９乃至１
４までのいずれか１つに記載の特徴量算出方法。
【請求項１６】前記算出される特徴量は、形状、また
は大きさ、またはオブジェクト表面のテクスチャ、また
は前記のいずれか２つ以上を統合したものであることを
特徴とする請求項９乃至１５までのいずれか１つに記載
の特徴量算出方法。