(57)【特許請求の範囲】
【請求項１】
物体の表面上の複数点の３次元座標からなる点群データを取得する工程と、該点群データから該物体の表面形状を特徴づけるパラメータ・セットを抽出する工程と、該パラメータ・セットを分類して、分類されたパラメータ・セット群にインデックスを付す工程と、該インデックスと前記点群データ又はパラメータ・セット群とを関連づけて記憶装置に記録する工程を具備し、
前記点群データを取得する工程は、３次元座標標本化装置を利用して３次元座標系を３次元メッシュに区切り、該物体の表面の点がそこに存在する場合にそのメッシュ内の代表点の座標をその測定点の点群データとする工程、或いは、３次元形状測定装置を利用して、前記物体表面の測定点の座標を測定し、測定された座標を点群データとする工程であり、前記パラメータ・セットを抽出する工程は、前記点群データの中心座標を求め、主成分分析法を利用して固有値を求め、該中心座標を原点として固有ベクトルを軸とする標準直交座標を定め、前記物体表面の点群データを該標準直交座標による点群データに変換し、変換された点群データをフーリエ展開して２次元余弦フーリエ係数を算出するステップを含み、
前記インデックスを付す工程は、前記パラメータ・セットの前記固有値、フーリエ係数及び固有値の比の各々について、その値の範囲により複数のクラスに分割し、分割された各クラスに適宜の整数を対応させ、該クラス又は整数の組合せに対するインデックスを定義し、該パラメータ・セットの各クラスに対して該インデックスを付するステップからなり、
前記記録工程は、前記記憶装置の共通のアドレスに前記点群データ、前記変換された点群データ、パラメータ・セットの各データと該インデックスを第１記録領域に記録し、第２記録領域に前記インデックスを索引とし、索引に対応する記録領域に前記点群データ、及びそれらのアドレスを記録するステップからなり、
前記各工程をコンピュータに基づいて実行させることを特徴とする物体の形状類別のためのデータベースの作成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、３次元物体の形状による分類方法及び同装置の技術分野に属する。 さらに、具体的には３次元物体の形状から特徴パラメータを機械的に算出し、特徴パラメータの値によりインデックスを付与して分類する方法等の技術分野に属する。
【０００２】
【従来の技術】
従来から、形状の異なる３次元物体を区別して、分類する方法が必要とされていた。例えば、考古学的な発掘土品（骨、壷、石器類など）を既に発掘されている出土品と比較したりする場合や、自動車の車体の設計で、新しく設計したデザインを過去に設計した車体のデザインと比較する場合、人間の歯形を人物鑑定に利用する場合には、過去に得られている形状データをデータベースとして蓄積し、新しい形状をこのデータベースから検索する方法が有用視されている。
【０００３】
このようなデータベースを作成し、検索する方法としては、物体の形状に関する人間に既に知られている形状（球、正立方体、正四面体など）を利用して、物体の形状を特徴づけたり、又は物体の機能面から、形状を特徴づけて分類する方法があった。このような方法は人間の個人差のため分類が異なったり、また、無数に近い形状に対しては、分類が一定の法則に基づいて行われないため複雑になりすぎて、データベースを作成することが困難であった。
【０００４】
また、別の方法としては物体全体を連続的に写真撮影し、その２次元データ全体に対して主成分分析を行い、そこから得られるパラメータのうちいくつかを３次元物体の形状の特徴を表すパラメータとして採用し、その採用されたパラメータに従って、物体を分類する方法が従来から提案されている。この方法は３次元物体の周囲を連続的に撮影して展開した２次元画像をもとに特徴パラメータを計算するために、分類が対象物の撮影方法に依存したり、またパラメータを計算するための計算量が膨大になり、実用化が困難であった。
【０００５】
また、物体の形状を数式で表現し、その数式や係数パラメータに基づいて分類する方法も提案されていた。しかし、この方法は類似形状の物体でも数式や係数が著しく異なり、類似形状とされず、正確な分類が困難であった。
【０００６】
【発明が解決しようとする課題】
以上述べたように、従来技術では、類別が人間の主観に左右されたり、計算量が膨大で実用化に困難であるという課題があった。本発明は３次元物体の形状を客観的に処理し、かつ計算も実用可能な範囲の有効な分類法及び、その分類法に基づくデータベースの作成並びに検索方法を提供することを課題としている。
【０００７】
【課題を解決するための手段】
上記課題を解決するために本発明は以下の手段を採用している。即ち、
請求項１記載の発明は、物体の表面上の複数点の３次元座標からなる点群データを取得する工程と、該点群データから該物体の表面形状を特徴づけるパラメータ・セットを抽出する工程と、該パラメータ・セットを分類して、分類されたパラメータ・セット群にインデックスを付す工程と、該インデックスと前記点群データ又はパラメータ・セット群とを関連づけて記憶装置に記録する工程を具備し、
前記点群データを取得する工程は、３次元座標標本化装置を利用して３次元座標系を３次元メッシュに区切り、該物体の表面の点がそこに存在する場合にそのメッシュ内の代表点の座標をその測定点の点群データとする工程、或いは、３次元形状測定装置を利用して、前記物体表面の測定点の座標を測定し、測定された座標を点群データとする工程であり、前記パラメータ・セットを抽出する工程は、前記点群データの中心座標を求め、主成分分析法を利用して固有値を求め、該中心座標を原点として固有ベクトルを軸とする標準直交座標を定め、前記物体表面の点群データを該標準直交座標による点群データに変換し、変換された点群データをフーリエ展開して２次元余弦フーリエ係数を算出するステップを含み、
前記インデックスを付す工程は、前記パラメータ・セットの前記固有値、フーリエ係数及び固有値の比の各々について、その値の範囲により複数のクラスに分割し、分割された各クラスに適宜の整数を対応させ、該クラス又は整数の組合せに対するインデックスを定義し、該パラメータ・セットの各クラスに対して該インデックスを付するステップからなり、
前記記録工程は、前記記憶装置の共通のアドレスに前記点群データ、前記変換された点群データ、パラメータ・セットの各データと該インデックスを第１記録領域に記録し、第２記録領域に前記インデックスを索引とし、索引に対応する記録領域に前記点群データ、及びそれらのアドレスを記録するステップからなり、
前記各工程をコンピュータに基づいて実行させることを特徴としている。
【００１５】
【発明の実施形態】
図１は本発明を実施した実施形態のデータベースの作成方法の手順を示す図である。以下図面を利用して説明する。図１において、ステップＳ１では、対象とする３次元物体（以下、対象物体という）表面上の複数の点の実際の３次元座標系（以下、実系という）における３次元座標値を求め、点群データとしてメモリーに記録する。３次元座標を求める方法としては、実在の対象物体を３次元形状測定装置を使用して求めてもよいし、対象物体の形状がＣＡＤデータとして与えられている場合は３次元座標標本化装置（又は同標本化方法）を使用して求めてもよい。３次元座標標本化装置は既知の装置である。例えばＣＡＤによって半径１の球が数式（１）
【数１】
0004649030.tif 000002
のように表現されている場合は点群データを以下のようにして求める。即ち、最初にＸ−Ｙ平面を細かなメッシュで区切る。次にあるメッシュの中心座標（ｘ，ｙ）に対して数式（１）を満たすｚ座標を求め、３次元座標（ｘ，ｙ，ｚ）を１つの点の座標とする。これを全てのメッシュに対して計算して、Ｘ−Ｙ平面をベースとした半径１の球の点群データが求められる。なお、Ｘ−Ｙ平面に対して垂直な面の点がまばらになることを防ぐために、同様のことをＹ−Ｚ平面、Ｚ−Ｘ平面に対して行うことが望ましい。
【００１６】
ステップＳ２は、対象物体の形状を表すパラメータを求める工程で、標準直交座標系を求めるステップＳ２１と、ステップＳ１で求めた点群データを標準直交座標系による表示に変換するステップＳ２２と、変換された点群データに数値計算的な処理を施して２次元余弦フーリエ係数を求めるステップＳ２３とからなる。標準直交座標を求めるステップＳ２１は実系における対象物体の座標決定の自由度を失くし、画一化するために行うもので図２に示すステップからなる。ステップＳ１０１で点群データの重心を求める。ここで重心は一般に使用されている対象物体の質量の重心（対象物体が均質な場合体積の重心）ではなく、表面積に対するものであり、データの各座標に対する平均値を意味する。
【００１７】
ステップＳ１０２では、求められた重心を原点として主成分分析を行う。主成分分析法は多次元観測変量（データ）を無相関でかつ重要度の順序がついた変量（データ）に変換する次元縮小法の１つとして知られている方法であり、多次元の変量データの変化を少数個の変量データで説明することを目的にしている従来技術である。主成分分析によって得られた最大固有値（λ１）に対応する固有ベクトル（第１主成分）を標準直交座標系のｘ軸とする。次に、第１主成分に直交する平面における最大固有値（λ２）を求め、これに対応する固有ベクトル（第２主成分）を標準直交座標系のｙ軸とする。ｘ軸、ｙ軸とそれぞれに直交する固有ベクトルは一意に定まり、これをｚ軸とし、対応する固有値を（λ３）とする。
【００１８】
図３は、対角軸の長さが異なる８面体を標準直交座標系で表した図である。図４（Ａ）は、標準直交座標系で表された８面体をｘ軸、ｙ軸、ｚ軸方向に２倍、３倍に引き伸ばした場合の固有値の変化を示し、図４（Ｂ）はｘ軸方向のみを２倍、３倍に引き伸ばした場合の固有値の変化を示す。図４（Ａ）、（Ｂ）から理解できるように、物体の大きさを各軸方向の固有値で代表させると最大固有値（λ１）が物体の大きさを示す目安となり、また、物体を各軸方向に等倍または異なった比率で伸縮させると対応する固有値が増減する。従って固有値又は固有値の比をパラメータに選定すれば、物体の標準座標系での各軸における伸縮状態が把握できる。
【００１９】
固有値の大きさだけでは対象物体の形状を把握できないので、ステップＳ２３で２次元フーリエ係数を求める。フーリエ係数は関数ｆ（・）をフーリエ展開したときの係数である。ここではｚ座標の値を関数ｆ（ｘ，ｙ）で表し、関数ｆ（ｘ，ｙ）のフーリエ係数を求める。なお、関数ｆ（ｘ，ｙ）は図３から分かるように同一の（ｘ，ｙ）に対して一般に正及び負の値（２値）をとる。また、対称形の場合フーリエ係数がゼロになる。それを避けるため正と負に分けて求める。即ち、ｚ≧０の範囲とｚ≦０の範囲に分けてフーリエ係数を求める。また、フーリエ係数にｓｉｎの項を含ませるとｓｉｎは奇関数であるために左右が打ち消し合って小さな値となるのでｃｏｓの組み合わせを用いる。
【００２０】
フーリエ係数ａ〔ｍ，ｎ〕を数式（２）で定義する。なお、記号「・」は乗算を示す（以下同じ）。
【数２】
0004649030.tif 000003
なお数式（２）で、ＮはＺ座標が正の場合（ｚ≧０）となる点の全個数であり、Ｌｘはこの場合のｘiの最大値ｘmaxとｘiの最小値ｘminとの差Ｌｘ＝ｘmax−ｘminである。Ｌｙも同様にＬｙ＝ｙmax−ｙminである。同様にＺ座標がｚ≦０の場合に対してフーリエ係数ａ´〔ｍ，ｎ〕を数式（３）で定義する。
【数３】
0004649030.tif 000004
数式（３）で、ＭはＺ座標がｚ≦０となる点の全個数であり、Ｌｘはこの場合のｘiの最大値ｘmaxとｘiの最小値ｘminとの差Ｌｘ＝ｘmax−ｘminである。Ｌｙも同様にＬｙ＝ｙmax−ｙminである。
【００２１】
図５、図６は基本的な形状として、Ｌ型、８面体、立方体、球、円柱、及び円錐を選んでフーリエ係数ａ〔ｍ，ｎ〕を求め、ａ〔０，０〕で正規化した結果を示す図である。図５は前記形状について８個の２次元余弦フーリエ係数ａ〔０，１〕、……ａ〔２，２〕の大きさを比較した結果を示す。図６は前記各形状について８個の２次元余弦フーリエ係数ａ〔０，１〕、ａ〔０，２〕、ａ〔１，０〕、ａ〔１，１〕、……ａ〔２，２〕の分布（変化）を示した図である。図５、図６から明らかなように、物体の表面形状の差異によってフーリエ係数の分布形状に著しい差異が認められるし、係数の数値の大きさにも差異が認められる。このことは、本方法による有効性を示しているものと考えられる。
【００２２】
さらに図９に示すようなＬ型、Ｔ型、トライポット型について、直径ｄとパイプ長さＬの比ｈ＝Ｌ／ｄが変化した場合の固有値とフーリエ係数の変化を図１０（Ａ）、（Ｂ）に示す。比ｈはｈ＝３，５，６の場合について求め、固有値は最大固有値で正規化した値を示し、フーリエ係数はａ〔０，０〕で正規化した値を示す。正規化した値は絶対的なスケールに影響されず同じ値になるからである。（Ｂ）に示す正規化されたフーリエ係数はｈ＝５とｈ＝６の場合について各フーリエ係数とも略一致し、人間の持っている類似の観念と略一致していることが分かる。即ち、本方法による分類は人間の類似の観念に近い分類の可能性を示唆している。
【００２３】
ステップＳ３では得られたパラメータを処理してインデックスを付す工程であり、この工程は全てのパラメータを複数のクラスに分割を行うステップＳ３１とインデックスを付すステップＳ３２とからなる。ステップＳ３１ではパラメータとして固有値（λ１）と固有値の比（λ２／λ１）、（λ３／λ１）及びフーリエ係数ａ〔ｍ，ｎ〕、ａ´〔ｍ，ｎ〕を選択パラメータとする。各パラメータを丸めて、Ｋ個(例えばＫ＝１００）のクラスに分割する。この分割されたクラスの集合に（００）から（９９）までの整数を対応させる。例えば固有値（λ１）に対しては固有値（λ１）の最小値と最大値をλMIN、λMAXと仮定し、λ１´＝（（λ１-λMIN）／Ｌ)・１００を求めて、求めたλ１´を四捨五入して丸め、（０〜９９）の整数に対応させる。ただし、Ｌ＝λMAX-λMIN  である。
【００２４】
また、比（λ２／λ１）、（λ３／λ１）は〔０，１〕の範囲にあるので、それぞれ１００倍して四捨五入して丸め、（０〜９９）の整数に対応させる。同様にａ〔ｍ，ｎ〕／ａ〔０，０〕は（−１，１）の範囲にあるのでａ〔ｍ，ｎ〕＝（ａ〔ｍ，ｎ〕／ａ〔０，０〕＋１）・５０として得られた数値ａ〔ｍ，ｎ〕を四捨五入して丸め、（０〜９９）の整数を対応させる。ａ´〔ｍ，ｎ〕についても同様に行う。以上の手続きにより、全てのパラメータは（０〜９９）の整数で表されたクラスと対応づけられる。
【００２５】
ステップＳ３２では、クラスの集合{Ｃｉ：ｉ＝１，２，……，ｎ}に対してインデックスＪに対応させる。インデックスＪとしては、各パラメータのクラスを一定の順序で並べた整数の組合せ（又は配列）としてもよいし、１つの大きな整数に対応させて表してもよい。後者の例としては、例えば各パラメータのクラスを２桁の整数Ｉｐｉで表し、各クラスを一定の順序で並べて、インデックスＪを、
【数４】
0004649030.tif 000005
数式４で表現としてもよい。ステップＳ４ではこのようにして得られたインデックスと実系で得られた点群データとを対応させてメモリに記録する。データの記録方式として、例えば図７に示すように行う。即ち、メモリＡ領域には実系で得られた点群データをアドレスａ１に記録し、次の点群データをアドレスａ２に記録する。次にステップＳ２１で得られた固有値、固有ベクトルを記録し、その下にステップＳ２２で得られた標準直交座標に変換された点群データを記録する。その次にステップＳ２３で得られる特徴パラメータとして２次元余弦フーリエ係数の値を記録し、その下に付与されたインデックスＪ１を記録する。
【００２６】
一方メモリＢ領域は付与されたインデックスＪ１と検索に便利なデータ並びに点群データのアドレスを記録する。まず、付与されたインデックスＪ１に対してそのインデックスに属するパラメータの範囲を記録し、同一のインデックスＪ１に対して得られた順に番号と各パラメータの値と点群データが入っているアドレスａ１を記録する。この操作手順を得られた点群データの全てについて行う。これによって、インデックスと点群データとが関連付けられて、データベースが作成される。
【００２７】
以上データベース作成方法の１例について説明したが、特徴パラメータの分割の組数によっては同じインデックスをもつ点群データの個数が集中し、検索が不便になる場合も起こり得る。このような場合には割込命令により、又は自動的にパラメータの分割組数を変更して、統合又は細分割を行わせるようにしてもよい。即ち、上記した例において選択したパラメータがｋ個で、各パラメータを１００個の組に分類しており、全体で（１００＊＊ｋ）個の組に分類される。この結果、分類される組数が多すぎて、インデックスに対応するデータが存在しない場合が多く発生し、インデックスによる検索に不都合が生じる場合がある。このような場合においてはパラメータの分割組数を小さくするなどしてデータベースの構成を対象物体の性質により修正する。
【００２８】
図８は、検索の手順をしめすアルゴリズムのフローチャートを示す。図８において、ステップＳ１〜ステップＳ３はデータベースの作成手順（図１参照）で述べた手順と同一又は類似である。即ち、検索する対象物体の点群データを得る。この点群データはデータベースの作成時の座標系と同じであってもよいし、異なっていてもよい。異なっている場合は必要があれば変換して一致させる。また、直接標準直交座標系で表された点群データであってもよい。得られた点群データから、データベース作成時のパラメータを算出し、同じ方法でインデックスを付ける。
【００２９】
ステップＳ４では検索方法を選択する。検索方法が唯一であると、同じインデックスをもつ形状が多過ぎたり、皆無であったりして検索が困難になる。このため、複数の検索方法を用意しておき、その中から選択させて検索を行う。或いは必要なパラメータを要求させて、パラメータによって検索方法を変更するようにしてもよい。例えば検索する対象物体のインデックスを構成するパラメータに重みを付けるようにして、データベースのインデックスとの重み付き距離（例えば重み付き２乗和）の小さいものを類似形状としてもよい。或いは特徴パラメータの値の組を大分類と小分類に分けてもよい。例えばパラメータが２桁の整数で表されている場合は１桁目と２桁目の整数が同一の場合のみパラメータを同じとする小分類と１桁目の整数を無視して２桁目の整数が同じならば同一のパラメータとみなしてインデックスを同一とし、大分類としてもよい。ステップＳ５では、同一のインデックスとして検索されたものを出力する。同一のインデックスのデータがない場合は最も近いものを出力するようにしてもよい。
【００３０】
以上、この発明の実施形態、実施例を図面により詳述してきたが、具体的な構成はこの実施例に限られるものではなく、この発明の要旨を逸脱しない範囲の設計の変更等があってもこの発明に含まれる。例えば、以上述べた実施形態では３次元直交座標系を採用した場合について述べてきたが、点群データを円柱座標系による表示、又は極座標系による表示した場合も適用可能であり、本発明の範囲内に入る。
【００３１】
【発明の効果】
以上説明したように、この発明の構成によれば、３次元物体の形状の分類が自動的（機械的）に行われるため人間の個人差を排除した分類が可能になるという効果が得られる。また形状の微細な差異も分類可能であり、さらに計算量が膨大なものにならないため実用的かつ有用な分類法が可能になるという効果が得られる。
【図面の簡単な説明】
【図１】  本発明の実施形態の手続流れを示すフローチャートである。
【図２】  標準直交座標系を求める手続流れを示す。
【図３】  ８面体の斜視図を示す。
【図４】  （Ａ）、（Ｂ）は軸方向に引き伸ばした場合の固有値の変化割合を示す。
【図５】  各種の形状における２次元余弦フーリエ係数の比較を示す。
【図６】  各種の形状における２次元余弦フーリエ係数の比較を示す。
【図７】  データベースに記録する記録方式の例を示す。
【図８】  本発明の検索方法の流れを示すフローチャートである。
【図９】  Ｌ型、Ｔ型、トライポット型の斜視図を示す。
【図１０】  太さ対長さの比を変化させた場合の固有値の変化（Ａ）、及びフーリエ係数の変化（Ｂ）を示す。
【符号の説明】
【図１】
0004649030.tif 000006
【図２】
0004649030.tif 000007
【図３】
0004649030.tif 000008
【図４】
0004649030.tif 000009
【図５】
0004649030.tif 000010
【図６】
0004649030.tif 000011
【図７】
0004649030.tif 000012
【図８】
0004649030.tif 000013
【図９】
0004649030.tif 000014
【図１０】
0004649030.tif 000015