(57)【要約】【課題】構造物データの検索に適した特徴量を効率的に算出できる。【解決手段】記憶部１ａは、複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を記憶する。演算部１ｂは、記憶部１ａからグラフの情報を取得する。演算部１ｂは、対称多項式の演算に用いられる次数およびパラメータをグラフの情報に基づいて決定する。演算部１ｂは、決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する。【選択図】図１
2015191617.tif 000002
【特許請求の範囲】
【請求項１】
複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を取得し、
対称多項式の演算に用いられる次数およびパラメータを前記情報に基づいて決定し、
決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する、
処理をコンピュータに実行させる算出プログラム。
【請求項２】
前記決定では、グラフの情報に含まれる重みの分布に基づいて、次数およびパラメータを決定する、請求項１記載の算出プログラム。
【請求項３】
前記演算は、次数およびパラメータが大きいほど重みの乗算回数が増える演算であり、
前記決定では、重みの相対誤差が大きいほど次数およびパラメータを小さい値とする、請求項２記載の算出プログラム。
【請求項４】
前記決定では、複数の構造物データに対応する複数のグラフの情報に基づいて、次数およびパラメータを決定する、請求項１乃至３の何れか１項に記載の算出プログラム。
【請求項５】
前記決定では、特徴量の算出対象の構造物データ毎に、当該構造物データに対応するグラフの情報から次数およびパラメータを決定する、請求項１乃至３の何れか１項に記載の算出プログラム。
【請求項６】
前記算出では、グラフに含まれるノードおよびエッジの重みの情報を反映させた行列を生成し、第１の種類の対称多項式を用いて当該行列をベクトルに変換し、前記第１の種類の対称多項式または第２の種類の対称多項式の何れかに前記ベクトルの各要素を代入することで特徴量を算出する、請求項１乃至５の何れか１項に記載の算出プログラム。
【請求項７】
複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を記憶する記憶部と、
対称多項式の演算に用いられる次数およびパラメータを前記情報に基づいて決定し、
決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する、演算部と、
を有する算出装置。
【請求項８】
コンピュータが、
複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を取得し、
対称多項式の演算に用いられる次数およびパラメータを前記情報に基づいて決定し、
決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する、
算出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は算出プログラム、算出装置および算出方法に関する。
【背景技術】
【０００２】
現在、３次元モデルの描画を支援するソフトウェアが利用されている。例えば、製図を支援する技術として、ＣＡＤ（Computer Aided Design）がある。ＣＡＤのソフトウェアを実行するコンピュータは、入力デバイスを用いたユーザの入力操作に応じて３次元の構造物を描画し、ディスプレイに表示させる。ユーザは、ディスプレイに描画された内容を視認することで、構造物の立体的なイメージを把握しながら製図を行える。
【０００３】
例えば、コンピュータでは、３次元の座標情報を用いて３次元の形状を表し得る。３次元の形状を表すデータ形式の一例にＳＴＬ（Standard Triangulated Language）がある。ＳＴＬでは、複数の三角形の組合せで３次元モデルの形状を表す。ＳＴＬデータは、１つの三角形に対し、３つの頂点の座標と三角形の面に対する法線ベクトルとの情報を含む。
【０００４】
ところで、ある３次元モデルに対して、別の３次元モデルを検索することがある。例えば、製品の設計において、ある部品に類似する形状の部品を設計済であるかを確認して重複設計を抑える場合である。そこで、３次元モデルに対して形状が類似する他の３次元モデルを検索する方法が考えられている。例えば、３次元モデルの形状の特徴を定量化する。特徴を表す量（特徴量）が近似する３次元モデル同士は、形状も類似していると考えられる。複数の種類の特徴量を含む特徴ベクトルを用いて検索を行うこともある。
【０００５】
例えば、ボクセル化および細線化を用いて３次元オブジェクトをスケルトングラフに変換し、スケルトングラフを更に処理して、探索用のグラフ関連特徴ベクトル成分（稜線ループやノード等の数）を識別する提案がある。また、３次元画像の検索における照会用の特性記述子として、３次元モデルのボリュームやバウンディング球体（物体モデルの最長軸の半分に等しい半径の球体）の半径、色のヒストグラムおよびウェーブレット係数などを用いる提案もある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００６−５２０９４８号公報
【特許文献２】特表２００３−５１８２９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記のように構造物の３次元形状を多角形の組合せとして表すことがある。構造物の頂点は多角形の頂点により表され、構造物の２つの頂点を結ぶ辺は多角形の辺により表される。このとき、構造物の頂点をノード、構造物の２つの頂点を結ぶ辺をエッジとし、ノードやエッジに所定の重みを設定した重み付きグラフを構造物データから生成し、重み付きグラフの特徴量を構造物データの特徴量とすることが考えられる。そこで、構造物データの検索に適した特徴量をどのように効率的に求めるかが問題となる。
【０００８】
例えば、形状検索用のグラフの特徴量には、ノードへの番号付けの順序に依存しないこと（対称群不変性）が求められる。ところが、ノードの重みのように対称性が考慮されていない量から対称群不変な量を計算するとき、ノード数に応じてその計算コストが極度に増大するおそれがある。
【０００９】
１つの側面では、本発明は、構造物データの検索に適した特徴量を効率的に算出できる算出プログラム、算出装置および算出方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、算出プログラムが提供される。この算出プログラムは、複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を取得し、対称多項式の演算に用いられる次数およびパラメータをグラフの情報に基づいて決定し、決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する、処理をコンピュータに実行させる。
【００１１】
また、１つの態様では、算出装置が提供される。この算出装置は、記憶部と演算部とを有する。記憶部は、複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を記憶する。演算部は、対称多項式の演算に用いられる次数およびパラメータを記憶部に記憶された情報に基づいて決定し、決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する。
【００１２】
また、１つの態様では、算出方法が提供される。この算出方法では、コンピュータが、複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を取得し、対称多項式の演算に用いられる次数およびパラメータをグラフの情報に基づいて決定し、決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する。
【発明の効果】
【００１３】
１つの側面では、構造物データの検索に適した特徴量を効率的に算出できる。
【図面の簡単な説明】
【００１４】
【図１】第１の実施の形態の算出装置を示す図である。
【図２】第２の実施の形態の算出装置のハードウェア例を示す図である。
【図３】ポリゴンおよび構造物の例を示す図である。
【図４】算出装置の機能例を示す図である。
【図５】skew Young図形の例である。
【図６】構造物データの例を示す図である。
【図７】グラフデータの例を示す図である。
【図８】四面体の例を示す図である。
【図９】次数およびパラメータの決定例を示すフローチャートである。
【図１０】特徴ベクトルの算出例（その１）を示すフローチャートである。
【図１１】特徴ベクトルの算出例（その２）を示すフローチャートである。
【図１２】特徴ベクトルの算出例（その３）を示すフローチャートである。
【図１３】特徴ベクトルの算出例（その４）を示すフローチャートである。
【図１４】特徴ベクトルの算出例（その５）を示すフローチャートである。
【図１５】特徴ベクトルの算出例（その６）を示すフローチャートである。
【図１６】特徴ベクトルの算出例（その７）を示すフローチャートである。
【図１７】特徴ベクトルの算出例（その８）を示すフローチャートである。
【図１８】ノードへの番号付けの例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の算出装置を示す図である。算出装置１は、３次元の構造物を示す構造物データの特徴量を計算する。ここで、構造物データでは、構造物は複数の多角形により表される。具体的には、構造物の表面を複数の多角形の平面の組合せにより近似的に表す。ここで、多角形を意味するポリゴン（polygon）という用語を、物体を３次元で表現する際の要素としての多角形を示す用語として用いることもある。例えば、ポリゴンを三角形とするデータ形式としてＳＴＬがある。
【００１６】
算出装置１は、１つの構造物データに対して複数の種類の特徴量を計算してもよい。複数の種類の特徴量を総称して特徴ベクトルと呼ぶこともある。例えば、特徴量（または特徴ベクトル）は、構造物データの検索に用いられる。検索を行う装置は、検索クエリで指定された構造物データの特徴量とライブラリ内の構造物データの特徴量とを照合することで、指定された構造物データが示す形状に類似するライブラリ内の他の構造物データを検索し得る。検索結果は、検索を行う装置に接続されたディスプレイに表示されたり、検索クエリの入力元の端末装置に送信されたりする。算出装置１が検索機能を有してもよい。
【００１７】
類似形状の検索機能は、例えば、部品などの設計において重複設計を抑える場合や、ある部品が原因で製品の故障が発生したときに、類似する部品の故障履歴や故障原因を調べる場合に利用され得る。
【００１８】
算出装置１は、記憶部１ａおよび演算部１ｂを有する。記憶部１ａは、ＲＡＭ（Random Access Memory）などの揮発性記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。演算部１ｂは、例えば、プロセッサを含む。プロセッサは、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）でもよいし、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路でもよい。また、プロセッサは、複数のプロセッサの集合（マルチプロセッサ）でもよい。プロセッサは、例えば、記憶部１ａに記憶されたプログラムを実行するものでもよい。
【００１９】
記憶部１ａは、構造物データに対応するグラフの情報を記憶する。グラフは、構造物データで示される構造物の頂点をノード、構造物の２つの頂点（ノードに対応する）を結ぶ辺をエッジとする。エッジで接続されたノードは、互いに隣接する関係にあるといえる。ここで、構造物の頂点は多角形の頂点により表され、構造物の２つの頂点を結ぶ辺は多角形の辺により表される。具体的には、構造物の１つの頂点は、３以上の多角形により共有される頂点に対応する。構造物の２つの頂点を結ぶ１つの辺は隣接する２つの多角形により共有される辺に対応する。
【００２０】
また、グラフは、ノードおよびエッジに対する所定の重みを含む。例えば、構造物の重心と頂点との距離を当該頂点に対応するノードの重みとし、辺の長さを当該辺に対応するエッジの重みとすることが考えられる。この場合、ノードおよびエッジの重みは、構造物の大きさや構造物の辺同士の角度などの形状が反映された情報であると考えられる。例えば、構造物がＮ個（Ｎは４以上の整数）の頂点を含むとする。各ノードの重みをＮ個の要素をもつベクトルＸで表し、各エッジの重みをＮ行Ｎ列の行列Ｗにより表す。
【００２１】
【数１】
2015191617.tif 000003
【００２２】
【数２】
2015191617.tif 000004
【００２３】
式（１）において、ベクトルＸのｊ列目（ｊは１≦ｊ≦Ｎの整数）の要素はｊ個目のノードの重みに相当する。式（２）において、ｉ行ｊ列目（ｉは１≦ｉ≦Ｎの整数）の要素は、ｉ個目のノードとｊ個目のノードとを結ぶエッジの重みに相当する。行列Ｗでは、対角要素およびエッジが存在しないノード間に相当する要素は“０”である。
【００２４】
演算部１ｂは、記憶部１ａに記憶されたグラフの情報を取得し、対称多項式の演算に用いられる次数およびパラメータをグラフの情報に基づいて決定する。演算部１ｂは、決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する。
【００２５】
ここで、形状検索用のグラフの特徴量には、ノードへの番号付けの順序に依存しないこと（対称群不変性）が求められる。そこで、演算部１ｂは、ノードへの番号付けの順序に依存しない量（対称群不変量）をグラフから求め、構造物データの特徴量とする。演算部１ｂは、そのための演算に対称多項式を用いる。対称多項式は、ｎ変数多項式で、ｎ個の変数を入れ替えても値が変わらない性質（対称群不変性）をもつ。すると、次のようにして特徴量を計算し得る。まず、ベクトルＸに対しＮ行Ｎ列の行列Ｄ（Ｘ）を定義する。行列Ｄ（Ｘ）の各要素は式（３）で表せる。
【００２６】
【数３】
2015191617.tif 000005
【００２７】
式（３）において、δはクロネッカーのデルタであり、δi=j＝１、δi≠j＝０である。このとき、行列Ｗと行列Ｄ（Ｘ）とを用いた次の行列Ｍlが考えられる。
【００２８】
【数４】
2015191617.tif 000006
【００２９】
行列ＷＤ（Ｘ）は、エッジの重みを考慮して、各ノードの重みを隣接するノードへ伝搬させる操作を示す。式（４）の添え字ｌ（ｌは１以上の整数）で示されるパラメータは、その操作をｌ回実行することを意味する。ここで、以下では対称多項式の一例として冪和対称多項式ｐを考える。ｋ次の冪和対称多項式ｐkは式（５）で表せる。
【００３０】
【数５】
2015191617.tif 000007
【００３１】
演算部１ｂは、冪和対称多項式ｐkに行列Ｍlの要素をあてはめるために、２階のテンソル（行列Ｍで表される量）を１階のテンソル（ベクトルで表される量）に変換する。１つの方法としては、行列Ｍlの対角要素（対角成分）をもつベクトル（Ｎ個の要素をもつ）を生成することが考えられる。その場合、演算部１ｂは、式（６）のように、行列Ｍlの対角要素を冪和対称多項式ｐkの各変数に代入することで、対称群不変量ｐk,lを求めることができる。
【００３２】
【数６】
2015191617.tif 000008
【００３３】
なお、２階のテンソルから１階のテンソルへ変換する方法は他の方法でもよい。例えば、行列Ｍlのｊ列目の各要素の和を１つの要素として、合計Ｎ個の要素をもつベクトルを生成してもよい。また、行列Ｍlのｉ行目の各要素の和を１つの要素として、合計Ｎ個の要素をもつベクトルを生成してもよい。
【００３４】
あるいは、行列Ｍlのｉ行目（またはｊ列目）の各要素（Ｎ個ある）をｐk,lに代入して、Ｎ個の要素をもつベクトルを生成し、その計算結果を更に冪和対称多項式に代入してもよい。例えば、ｊ列目のＮ個の要素を用いてＮ個のｐk,lを計算し、その計算結果を更に冪和対称多項式に代入して求まる値ｐk,l'は、式（７）のように表せる。ｐk,l'も対称群不変量である。
【００３５】
【数７】
2015191617.tif 000009
【００３６】
式（６）や式（７）の対称多項式の演算には、次数ｋおよびパラメータｌが用いられる。演算部１ｂは、次数ｋおよびパラメータｌをグラフの情報に基づいて決定する。例えば、演算部１ｂは、ノードやエッジの重みの分布（例えば、ばらつきの度合い）に応じて次数ｋとパラメータｌとを決定することが考えられる。ばらつきの度合いを示す量としては、例えば、ノードやエッジの重みの相対誤差（標準偏差÷平均）が考えられる。
【００３７】
より具体的には、ライブラリに登録された全て（あるいは一部）の構造物データのグラフがもつ重みの相対誤差が大きいほど、次数ｋおよびパラメータｌを小さい値とする。言い換えれば、ライブラリに登録された全て（あるいは一部）の構造物データのグラフがもつ重みの相対誤差が小さいほど、次数ｋおよびパラメータｌを大きい値とする。
【００３８】
演算部１ｂは、ノードおよびエッジの何れかに着目して相対誤差を評価してもよいし、ノードおよびエッジの両方に着目して相対誤差を評価してもよい。また、演算部１ｂは、次数ｋ＝Ｋ、パラメータｌ＝Ｌと決定したとき、１≦ｋ≦Ｋ，１≦ｌ≦Ｌの全ての整数ｋ，ｌの組合せについて特徴量を計算し、各特徴量を要素にもつ特徴ベクトルを生成してもよい。
【００３９】
算出装置１によれば、複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報が取得される。対称多項式の演算に用いられる次数およびパラメータがグラフの情報に基づいて決定される。決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量が算出される。これにより、構造物データの検索に適した特徴量を効率的に算出できる。具体的には次の通りである。
【００４０】
形状検索用のグラフの特徴量には、ノードへの番号付けの順序に依存しないこと（対称群不変性）が求められる。同じ形状でもノードへの番号付けの順序が違えば異なる特徴量となるようでは、検索を適切に行えないからである。
【００４１】
対称群不変性をもたない量を、対称群不変性をもつ量（対称群不変量）に変換するとき、その計算コストが問題となる。グラフのノード数をＮとすると、対称群の位数はＮ！となり、それらを全て考慮にいれた対称群不変量を、ノードやエッジの重みから計算するのは容易でない。
【００４２】
例えば、単純に、（ｘ1a1ｘ2a2・・・ｘNaN）＋（ｘ2a1ｘ1a2・・・ｘNaN）＋・・・＋（ｘNa1ｘN-1a2・・・ｘ1aN）（指数ａ１，ａ２，・・・，ａＮは互いに異なり、各指数に対し変数を入れ換えて作った全パターンの項について和をとる。項数はＮ！）を計算して特徴量とすることも考えられる。しかし、この計算はＯ（Ｎ！）の計算複雑性（Ｏ（Ｎ！）の計算量）となり、ノード数の増加に対して計算コストが極度に増大してしまう。このため、構造物の頂点数が増大するほど特徴量を算出するための計算コストが膨大になる。また、例えば、クリーク（ノードの部分集合のうち、部分集合に属する任意の２つのノード間にエッジが存在するもの）の数を求めるなど、ＮＰ（Non-deterministic Polynomial time）困難な問題を用いると、計算コストが膨大となり現実的でない。
【００４３】
そこで、算出装置１は、特徴量の計算に対称多項式を用いることで、対称群不変量を計算する際の計算コストを軽減する。上記の冪和対称多項式の例によれば、式（７）を用いてもＯ（Ｎ2）の計算複雑性に抑えることができる。
【００４４】
このとき、算出装置１は、グラフの情報から次数ｋやパラメータｌを決定する。前述のように、ノードおよびエッジの重みは、構造物の形状を反映した情報であると考えられる。例えば、式（６）で示されるように、重みの乗算回数は次数ｋとパラメータｌとの積ｋｌで求められる。乗算は一般に値の違いを大きくする。重みの差異が特徴量に極端に大きく反映され過ぎると、比較的小さな形状の差異が比較的大きな特徴量の差異として表されてしまい、検索時の特徴量の照合において、類似の判定が困難になるおそれがある。
【００４５】
そこで、演算部１ｂは、乗算で重みの違いが極端に大きくならないように次数ｋおよびパラメータｌをグラフの重みの情報から動的に調整することで、類似形状の検索用途に適した特徴量を算出できる。また、算出装置１によれば乗算回数ｋｌを所定の基準で制限できるので、グラフの情報によらずに固定的にｋ，ｌを決定して無暗に乗算を重ねるよりも、検索に適した特徴量を比較的小さな計算コストで取得できる。
【００４６】
［第２の実施の形態］
図２は、第２の実施の形態の算出装置のハードウェア例を示す図である。算出装置１００は、ＣＡＤによる３次元での構造物の設計を支援する。算出装置１００は、ユーザによる操作入力を受け付けると、当該操作入力に応じた３次元の図形を算出装置１００に接続されたディスプレイに表示させる。ユーザは、算出装置１００に対して既存の（設計済の）構造物のデータの検索を依頼できる。
【００４７】
例えば、ユーザは、算出装置１００を用いて、所定の３次元構造を描き、当該構造に類似する他の構造物を算出装置１００に検索させる。算出装置１００は、指定された構造物に形状が類似する他の構造物をライブラリから検索し、ユーザに提示する。ライブラリは、設計済である種々の構造物データを格納したデータベースである。ライブラリは、算出装置１００に内蔵された記憶装置に格納される。ライブラリは、算出装置１００が接続するネットワーク１０に接続された記憶装置に格納されていてもよい。以下の説明では、構造物の形状を示す３次元モデル（多面体）を指して、単に構造物と称することがある。
【００４８】
算出装置１００は、プロセッサ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、読み取り装置１０６および通信インタフェース１０７を有する。各ユニットは算出装置１００のバスに接続されている。
【００４９】
プロセッサ１０１は、算出装置１００の情報処理を制御する。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどである。プロセッサ１０１は、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどのうちの２以上の要素の組み合わせであってもよい。
【００５０】
ＲＡＭ１０２は、算出装置１００の主記憶装置である。ＲＡＭ１０２は、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ１０２は、プロセッサ１０１による処理に用いる各種データを記憶する。
【００５１】
ＨＤＤ１０３は、算出装置１００の補助記憶装置である。ＨＤＤ１０３は、内蔵した磁気ディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。算出装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の補助記憶装置を備えてもよく、複数の補助記憶装置を備えてもよい。
【００５２】
画像信号処理部１０４は、プロセッサ１０１からの命令に従って、算出装置１００に接続されたディスプレイ１１に画像を出力する。ディスプレイ１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【００５３】
入力信号処理部１０５は、算出装置１００に接続された入力デバイス１２から入力信号を取得し、プロセッサ１０１に出力する。入力デバイス１２としては、例えば、マウス、デジタイザおよびタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００５４】
読み取り装置１０６は、記録媒体１３に記録されたプログラムやデータを読み取る装置である。記録媒体１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。また、記録媒体１３として、例えば、フラッシュメモリカードなどの不揮発性の半導体メモリを使用することもできる。読み取り装置１０６は、例えば、プロセッサ１０１からの命令に従って、記録媒体１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００５５】
通信インタフェース１０７は、ネットワーク１０を介して他の装置と通信を行う。通信インタフェース１０７は、有線通信インタフェースでもよいし、無線通信インタフェースでもよい。
【００５６】
図３は、ポリゴンおよび構造物の例を示す図である。図３（Ａ）は、構造物を形成する１つのポリゴンを例示している。第２の実施の形態では、ポリゴンの一例として三角形を想定する。算出装置１００は、例えばＳＴＬ形式の構造物データによりポリゴンを管理する。ただし、四角形や五角形など、他の多角形でもよい。図３（Ｂ）は、複数のポリゴンで形成される構造物として、八面体を例示している。八面体の表面は複数のポリゴンの組合せによって表される。図３（Ｂ）では表側の４つのポリゴンの法線ベクトルも示されている。
【００５７】
ポリゴン５１は、三角形の３つの頂点Ｋ１，Ｋ２，Ｋ３の座標およびポリゴン５１の表側の表面に対する法線ベクトルｒの情報を含む。法線ベクトルｒの長さは単位長さでもよい。座標および法線ベクトルは、直交するｘ，ｙ，ｚの３軸に対する座標値を用いて表される。
【００５８】
なお、ポリゴン５１の表裏は、構造物データにおける３つの頂点Ｋ１，Ｋ２，Ｋ３の座標の定義の順番により区別することもできる。頂点Ｋ１，Ｋ２，Ｋ３はポリゴン５１の表側から見たときに、１つ目の頂点から反時計周りに２つ目の頂点、３つ目の頂点と順番に定義される。
【００５９】
図４は、算出装置の機能例を示す図である。算出装置１００は、記憶部１１０、グラフ化部１２０、パラメータ設定部１３０、特徴量計算部１４０および検索部１５０を有する。記憶部１１０は、ＲＡＭ１０２やＨＤＤ１０３に確保された記憶領域を用いて実現できる。グラフ化部１２０、パラメータ設定部１３０、特徴量計算部１４０および検索部１５０は、プロセッサ１０１によって実行されるプログラムのモジュールであってもよい。
【００６０】
記憶部１１０は、各部の処理に用いられる情報を記憶する。記憶部１１０が記憶する情報は、構造物データ、グラフデータおよび特徴ベクトルデータを含む。構造物データは、構造物の形状を示すＳＴＬ形式のデータである。構造物データは、作図された構造物毎に記憶部１１０に複数格納される。記憶部１１０に記憶された複数の構造物データ（構造物データ群）を指して、ライブラリと称することもある。
【００６１】
グラフデータは、構造物データから生成されたグラフの情報である。グラフは、ノードおよびエッジに所定の重みをもつ重み付けグラフである。特徴ベクトルデータは、グラフデータから計算された特徴ベクトルを構造物データ毎に管理するための情報である。ただし、ネットワーク１０を介して算出装置１００からアクセス可能な記憶装置がある場合、算出装置１００は、構造物データ、グラフデータおよび特徴ベクトルデータを当該記憶装置に格納してもよい。
【００６２】
グラフ化部１２０は、構造物データをグラフに変換し、記憶部１１０に格納する。具体的には、グラフ化部１２０は、構造物データで示される構造物の頂点をノード、構造物の頂点を結ぶ辺をエッジとしたグラフを生成する。グラフ化部１２０は、構造物の重心と頂点との距離を当該頂点に対応するノードの重みとする。グラフ化部１２０は、辺の長さを、当該辺に対応するエッジの重みとする。
【００６３】
パラメータ設定部１３０は、特徴量計算部１４０の演算に用いられるパラメータなどを決定する。後述するように、特徴量計算部１４０は、特徴量の計算に対称多項式（対称式と呼ばれることもある）を用いる。パラメータ設定部１３０は、記憶部１１０に記憶された各構造物のグラフデータがもつ重みの統計量に基づいて、対称多項式の演算に用いられる次数やパラメータを決定する。
【００６４】
特徴量計算部１４０は、パラメータ設定部１３０により決定された次数とパラメータと対称多項式とを用いて、グラフに含まれる重みやノードの接続関係の情報に応じた特徴量を計算する。特徴量計算部１４０は、複数の種類の特徴量を計算し、構造物の特徴ベクトルとする。
【００６５】
特徴量計算部１４０は、ライブラリに登録された構造物データ毎に、特徴ベクトルを予め算出しておく。特徴量計算部１４０は、算出した特徴ベクトルを、構造物データに対応付けて記憶部１１０に格納された特徴ベクトルデータに登録する。特徴量計算部１４０は、検索クエリで指定された構造物データに対して特徴ベクトルを計算することもある。
【００６６】
検索部１５０は、構造物の検索クエリを受け付ける。例えば、ユーザは、入力デバイス１２を操作して、所定の検索クエリを算出装置１００に入力できる。検索部１５０は、ネットワーク１０を介して接続された他の情報処理装置から検索クエリを受け付けてもよい。検索クエリは、構造物データまたは構造物データを指定する情報を含む。
【００６７】
検索部１５０は、グラフ化部１２０、パラメータ設定部１３０および特徴量計算部１４０を用いて検索クエリで指定された構造物データに対する特徴ベクトルを求める。検索部１５０は、検索クエリで指定された構造物データに対する特徴ベクトルを、記憶部１１０に記憶された特徴ベクトルデータに登録された特徴ベクトルと照合して、検索クエリで指定された形状に類似する形状を表す構造物データを検索する。例えば、検索では、検索クエリで指定された構造物データに対する特徴ベクトルと、ライブラリ内の構造物データに対する特徴ベクトルとを要素毎に比較し、差の合計が小さいものほど、一致度が高いと判断することが考えられる。検索部１５０は、ディスプレイ１１に検索結果を表示させるなどして、ユーザに提示する。
【００６８】
ここで、特徴量計算部１４０は特徴量の計算に種々の対称多項式を利用できる。対称多項式については、文献“Symmetric functions and Hall polynomials second edition (Oxford Mathematical Monographs)”（Ian Grant MacDonald, New York :Oxford University Press, 1995）が参考になる。例えば、次のような対称多項式が考えられる。
【００６９】
（１）基本対称多項式
０次から３次までの基本対称多項式ｅ0，ｅ1，ｅ2，ｅ3は式（８）で表される。ただし、ｊ，ｋ，ｌは正の整数である。ｎは変数の個数であり正の整数である。
【００７０】
【数８】
2015191617.tif 000010
【００７１】
（２）完全対称多項式
１次から３次までの完全対称多項式ｈ1，ｈ2，ｈ3は式（９）で表される。ただし、ｊ，ｋ，ｌは正の整数である。ｎは変数の個数であり正の整数である。
【００７２】
【数９】
2015191617.tif 000011
【００７３】
（３）モノミアル対称多項式
正の整数ｄが与えられたとき、非増加の非負整数列ｄ1，ｄ2，・・・，ｄnへ整数ｄを分解したときの非負整数列をｄの分割（partition）または整分割（integer partition）と呼び、λで表す。ｄとｄ1，ｄ2，・・・，ｄnとの関係は式（１０）で表される。
【００７４】
【数１０】
2015191617.tif 000012
【００７５】
分割λに対してモノミアル対称多項式を得ることができる。例えば、ｄ＝５の分割λ＝（３，１，１）の場合のモノミアル対称多項式は式（１１）で表される。
【００７６】
【数１１】
2015191617.tif 000013
【００７７】
また、例えば、ｄ＝６の分割λ＝（３，２，１）の場合のモノミアル対称多項式は式（１２）で表される。
【００７８】
【数１２】
2015191617.tif 000014
【００７９】
分割λに対する整数ｄは多項式の次数に相当する（下記の多項式についても同様）。
（４）冪和対称多項式
第１の実施の形態で例示したように、ｋ次の冪和対称多項式は式（１３）で表される。ただし、ｋは正の整数である。ｎは変数の個数であり正の整数である。
【００８０】
【数１３】
2015191617.tif 000015
【００８１】
（５）シューア多項式
まず、ファンデルモンド行列式（Vandermonde determinant）は、式（１４）で表される。ただし、ｊ，ｋは正の整数である。ｎは変数の個数であり正の整数である。
【００８２】
【数１４】
2015191617.tif 000016
【００８３】
分割λ＝（ｄ1，ｄ2，・・・，ｄn）に対するシューア多項式は、式（１４）を用いて式（１５）で表される。
【００８４】
【数１５】
2015191617.tif 000017
【００８５】
例えば、分割λ＝（２，１），λ＝（１，１，１）に対するシューア多項式は、それぞれ式（１６），（１７）で表される。
【００８６】
【数１６】
2015191617.tif 000018
【００８７】
【数１７】
2015191617.tif 000019
【００８８】
（６）ジャック対称多項式
分割λ、パラメータα、変数ｘ1，ｘ2，・・・，ｘmに対するジャック対称多項式Ｊλ(α)（ｘ1，ｘ2，・・・，ｘm）は、次の通りである。
【００８９】
ｍ＝１のとき、ジャック対称多項式Ｊλ(α)は式（１８）で表される。
【００９０】
【数１８】
2015191617.tif 000020
【００９１】
ｍ＞１のとき、ジャック対称多項式Ｊλ(α)は式（１９）で表される。
【００９２】
【数１９】
2015191617.tif 000021
【００９３】
ここで、式（１９）の和の記号Σにおけるμは、全ての分割μについて和をとることを示す。分割μは、skew partition λ／μ（skew Young図形で表される）がhorizontal stripであり、式（２０）の条件を満たすものである。
【００９４】
【数２０】
2015191617.tif 000022
【００９５】
なお、μn＝０である。そうでなければＪμ（ｘ1，・・・，ｘn-1）＝０である。ただし、分割λなどの記号の左下の添え字は、当該分割における整数要素を示している。また、式（１９）のβλμは、式（２１）、（２２）で表される。
【００９６】
【数２１】
2015191617.tif 000023
【００９７】
【数２２】
2015191617.tif 000024
【００９８】
Ｂに含まれる分割λ’，μ’は、それぞれ分割λ，μに共役な分割（conjugate partition）である。更に、式（２１）の積の記号Πにおける（ｉ，ｊ）∈λは、分割λのYoung図形に含まれる全ての箱の座標（ｉ，ｊ）（ｉ行ｊ列の位置を示す指標）に対する計算であることを示す。
【００９９】
ここで、μ⊂λであるようなYoung図形λ，μに対し、λ＼μ（Ｎ×Ｎの部分集合としての差集合。Ｎは自然数全体の集合）と表されるＮ×Ｎの部分集合をskew Young図形と呼び、λ／μと表す。｜λ／μ｜＝｜λ｜−｜μ｜とする。horizontal stripとは、skew Young図形のうち、１つの列に高々１つしか箱を含まないものを示す。一方、１つの行に高々１つしか箱を含まないものはvertical stripと呼ばれる。
【０１００】
図５は、skew Young図形の例である。図５（Ａ）は、horizontal stripおよびvertical stripの何れにも該当しないskew Young図形を例示している。図５（Ａ）では、λ＝（５，３，１）、μ＝（１，１）である。なお、図５では行（紙面横方向）および列（紙面縦方向）を識別しやすいように、行および列を示す番号を付している。
【０１０１】
図５（Ｂ）は、horizontal stripを例示している。図５（Ｂ）では、λ＝（５，３，１，１）、μ＝（３，１，１）である。図５（Ｃ）は、vertical stripを例示している。図５（Ｃ）では、λ＝（２，２，１，１，１）、μ＝（１，１，１）である。
【０１０２】
例えば、分割λ＝（２，１），λ＝（１，１，１）に対するジャック対称多項式は、それぞれ式（２３），（２４）で表される。
【０１０３】
【数２３】
2015191617.tif 000025
【０１０４】
【数２４】
2015191617.tif 000026
【０１０５】
（７）ホール−リトルウッド（Hall-Littlewood）対称多項式
分割λ、パラメータｔ、変数ｘ1，ｘ2，・・・，ｘnに対するホール−リトルウッド対称多項式は、式（２５）で表される。
【０１０６】
【数２５】
2015191617.tif 000027
【０１０７】
ただし、ｍ（ｉ）はｉに等しい要素である。Ｓｎは位数ｎ！の対称群である。例えば、分割λ＝（２，１），λ＝（１，１，１）に対するホール−リトルウッド対称多項式は、それぞれ式（２６），（２７）で表される。
【０１０８】
【数２６】
2015191617.tif 000028
【０１０９】
【数２７】
2015191617.tif 000029
【０１１０】
（８）マクドナルド（Macdonald）対称多項式
Ａn型のマクドナルド対称多項式（以下、単にマクドナルド対称多項式という）を用いる。マクドナルド対称多項式はパラメータｔ，ｑを含む。例えば、分割λ＝（２，１），λ＝（１，１，１）に対するマクドナルド対称多項式は、それぞれ式（２８），（２９）で表される。
【０１１１】
【数２８】
2015191617.tif 000030
【０１１２】
【数２９】
2015191617.tif 000031
【０１１３】
なお、上記の説明では、幾つかの次数で各対称多項式を例示したが他の次数としてもよい。また、幾つかの種類の対称多項式では単純な具体例として３変数の場合を例示したが、４変数以上に対応するものも利用可能である。更に、特徴量の計算に利用可能な幾つかの種類の対称多項式を例示したが、他の種類の対称多項式を利用することを妨げるものではない。
【０１１４】
図６は、構造物データの例を示す図である。構造物データ１１１は、次のようなフォーマットである。なお、構造物データ１１１の左側に付した番号は行番号である。“ｓｏｌｉｄ”の文字列の後には、構造物の識別情報（例えば、“構造物Ａ”）が設定される（１行目）。
【０１１５】
“ｆａｃｅｔ  ｎｏｒｍａｌ”の文字列の後には、法線ベクトルの成分が設定される（２行目）。“ｆａｃｅｔ  ｎｏｒｍａｌ”の行（２行目）から“ｅｎｄｆａｃｅｔ”の行（８行目）までが１つのポリゴンの情報に相当する。“ｖｅｒｔｅｘ”の文字列の後には、ポリゴンの頂点の座標が設定される。三角形のポリゴンを考えているから、１つのポリゴンに対し、“ｖｅｒｔｅｘ”の文字列を用いて３つの頂点の座標が設定されることになる。
【０１１６】
また、構造物データ１１１によれば、法線ベクトルでもポリゴンの表裏を区別できるし、ポリゴンの頂点の座標の設定順によってもポリゴンの表裏を区別できる。同様にして、９行目以降に他のポリゴンが順次定められる。構造物データ１１１の末尾行は“ｅｎｄｓｏｌｉｄ”の文字列が設定される（１５行目）。
【０１１７】
図７は、グラフデータの例を示す図である。ここでは、グラフデータ１１２のフォーマットとしてＧｒａｐｈＭＬ形式を想定する。ＧｒａｐｈＭＬでは、ＸＭＬ（eXtensible Markup Language）の記法を用いてノードおよびエッジを記述する。ただし、他の形式のフォーマットとしてもよい。また、無向グラフを想定するが、有向グラフでもよい。なお、グラフデータ１１２の左側に付した番号は行番号である。
【０１１８】
例えば、３行目の記述は、エッジに対するキー“ｋｅｙ０”を定義している。ｋｅｙ  ｉｄ“ｋｅｙ０”のタグにより、エッジの重み（“ｗｅｉｇｈｔ”）に相当する属性をエッジに付与する。エッジの重みは、エッジに対応する辺の長さである。
【０１１９】
４行目の記述は、ノードに対するキー“ｋｅｙ１”を定義している。ｋｅｙ  ｉｄ“ｋｅｙ１”のタグにより、ノードの重み（“ｗｅｉｇｈｔ”）に相当する属性をノードに付与する。ノードの重みは、ノードに対応する頂点と構造物の重心との間の距離である。
【０１２０】
例えば、グラフデータ１１２によれば、ノードＩＤ“ｎ０”のノード（７行目〜９行目）に対して、重み“３．３１６６”が設定されている。ノードＩＤ“ｎ１”のノード（１０行目〜１２行目）などの他のノードも同様に表される。
【０１２１】
また、グラフデータ１１２によれば、エッジＩＤ“ｅ０”のエッジは、ノードＩＤ“ｎ１”のノードとノードＩＤ“ｎ０”のノードとを結ぶエッジであり、重みは“１．４１４２”である（１５行目〜１７行目）。エッジＩＤ“ｅ１”のエッジ（１８行目〜２０行目）などの他のエッジも同様に表される。ここで、ノードおよびエッジの重みは、ベクトルや行列を用いて扱える。例えば、簡単な例として四面体を考える。
【０１２２】
図８は、四面体の例を示す図である。図８の四面体は、直交座標系（各軸をｘ軸，ｙ軸，ｚ軸とする）における頂点ｐ1，ｐ2，ｐ3，ｐ4をもつ。頂点ｐ1の座標は（１，０，０）である。頂点ｐ2の座標は（０，１，０）である。頂点ｐ3の座標は（０，０，１）である。頂点ｐ4の座標は原点Ｏである。この四面体は、例えば、４つのポリゴンにより形成される。４つのポリゴンとは、具体的には、三角形ｐ1ｐ2ｐ3、三角形ｐ2ｐ3ｐ4、三角形ｐ3ｐ4ｐ1および三角形ｐ4ｐ1ｐ2である。
【０１２３】
例えば、四面体の重心と頂点との距離を、各頂点（あるいは、頂点に対応するグラフのノード）の重みとするなら、頂点重みベクトルＸは式（３０）で表される。
【０１２４】
【数３０】
2015191617.tif 000032
【０１２５】
また、四面体の辺の長さを、各辺（あるいは、辺に対応するグラフのエッジ）の重みとするなら、辺重み行列Ｗは式（３１）で表される。
【０１２６】
【数３１】
2015191617.tif 000033
【０１２７】
ここで、ｉ行ｊ列目の要素は、頂点ｐiと頂点ｐjとを結ぶ辺の長さに対応する。１つの頂点では辺を作れないので対角要素は０である。
グラフにおけるノードやエッジの重みは上記のようにベクトルＸや行列Ｗで表せる。特徴量計算部１４０は、これらの重みを反映したベクトルを生成して、当該ベクトルの要素を対称多項式の変数にあてはめる。具体的には、式（３）で示される行列Ｄ（Ｘ）を生成する。式（３０）のベクトルＸに対する行列Ｄ（Ｘ）は、式（３２）で表される。
【０１２８】
【数３２】
2015191617.tif 000034
【０１２９】
そして、式（４）で示される行列Ｍlを生成する。例えば、ｌ＝１のときの行列Ｍ1＝Ｍ＝Ｄ（Ｘ）ＷＤ（Ｘ）は、式（３３）で表される。
【０１３０】
【数３３】
2015191617.tif 000035
【０１３１】
ここで、行列Ｍlのｉ行ｊ列の要素は、式（３４）のように表される。
【０１３２】
【数３４】
2015191617.tif 000036
【０１３３】
例えば、行列ＭlをＮ個（Ｎは頂点（ノード）数）の要素をもつベクトルに変換するには、次のようなｓｕｍR演算（式（３５））、ｓｕｍC演算（式（３６））およびｄｉａｇ演算（式（３７））が考えられる。
【０１３４】
【数３５】
2015191617.tif 000037
【０１３５】
【数３６】
2015191617.tif 000038
【０１３６】
【数３７】
2015191617.tif 000039
【０１３７】
ｓｕｍR演算では、行列Ｍlの列毎に和をとる。ｓｕｍC演算では、行列Ｍlの行毎に和をとる。ｄｉａｇ演算では、行列Ｍlの対角要素を抽出する。
更に、２階のテンソルから１階のテンソルを生成する方法には、上記のｓｕｍR演算、ｓｕｍC演算およびｄｉａｇ演算以外の方法も考えられる。例えば、ｎ変数の対称多項式ｆjは、式（３８）で表される。
【０１３８】
【数３８】
2015191617.tif 000040
【０１３９】
これは、行列Ｍlのｊ（列を示す）を固定し、ｉ（行を示す）を振ったものである。すると、対称多項式ｆjに対して、同じ種類の、または、異なる種類の対称多項式ｇを考えることができる。対称多項式ｇは、式（３９）で表される。
【０１４０】
【数３９】
2015191617.tif 000041
【０１４１】
対称多項式ｇの計算結果も対称群不変量である。すなわち、行列Ｍlおよび対称多項式ｆjに対して、ベクトル（ｆ1，ｆ2，・・・，ｆn）を生成してもよい。あるいは、行列Ｍlのｉ（行を示す）を固定し、ｊ（列を示す）振った対称多項式ｆi（ｉ＝１，２，・・・，ｎ）の値を要素にもつベクトルを生成することも考えられる。
【０１４２】
算出装置１００は、これらの演算を利用して、以下のように対称多項式を用いた特徴量の計算を行う。まず、対称多項式の計算で用いられる次数およびパラメータを決定する手順を例示する。
【０１４３】
図９は、次数およびパラメータの決定例を示すフローチャートである。以下、図９に示す処理をステップ番号に沿って説明する。
（Ｓ１）パラメータ設定部１３０は、記憶部１１０に記憶された全てのグラフデータに関して、ノードおよびエッジの重みの平均値μと、標準偏差σとを算出する。
【０１４４】
（Ｓ２）パラメータ設定部１３０は、パラメータＫ，Ｌを算出する。具体的には、パラメータＫ，Ｌは、式（４０）で表される。
【０１４５】
【数４０】
2015191617.tif 000042
【０１４６】
式（４０）の角括弧記号（“［］”）は、ガウス記号である（すなわち、小数点以下を切り捨てて整数化することを示す）。ただし、小数点以下を四捨五入または切り上げて、Ｋ，Ｌを整数化してもよい。式（４０）で示されるように、パラメータ設定部１３０は、相対誤差（σ／μ）が大きい程、Ｋ，Ｌを小さい値とする。なお、後述するように、パラメータＫは特徴量を算出する際の対称多項式の次数（特徴量の計算に用いる最大の次数）に相当する。
【０１４７】
（Ｓ３）パラメータ設定部１３０は、パラメータｔ，ｑ，αを算出する。具体的には、式（４１）によりパラメータｔ，αを求める。式（４２）によりパラメータｑを求める。
【０１４８】
【数４１】
2015191617.tif 000043
【０１４９】
【数４２】
2015191617.tif 000044
【０１５０】
（Ｓ４）パラメータ設定部１３０は、決定したパラメータＫ，Ｌ，ｔ，ｑ，αを記憶部１１０に格納する。
このように、算出装置１００は、グラフデータに含まれる重みの分布に基づいて、対称多項式の演算に用いられる次数およびパラメータを決定する。なお、ステップＳ１では、記憶部１１０に記憶された（ライブラリ内の）一部のグラフデータに関して、重みに関する平均値μおよび標準偏差σといった統計量を求めてもよい。例えば、所定数のグラフデータをサンプリングして統計量を求めることが考えられる。
【０１５１】
また、構造物データが、幾つかのカテゴリ（例えば、機械部品、電子部品など）に分類されているなら、カテゴリ毎に次数およびパラメータを算出してもよい。すると、算出装置１００は、構造物データが属するカテゴリ毎の次数およびパラメータを用いて、図１０以降に示す手順により当該構造物データに対する特徴量を計算し得る。
【０１５２】
あるいは、算出装置１００は、特徴量の算出対象の構造物データ毎（グラフデータ毎）に、当該構造物データに対応するグラフデータから各パラメータを決定してもよい。例えば、特徴量の算出対称の構造物データ毎に、当該構造物データに対応するグラフデータのみを用いて、構造物データ毎に専用の次数およびパラメータを決定してもよい。すると、算出装置１００は構造物データ毎の次数およびパラメータを用いて、図１０以降に示す手順により当該構造物データに対する特徴量を計算し得る。
【０１５３】
例えば、上記で挙げたライブラリ内のグラフデータ全体、カテゴリ、構造物データ（グラフデータ）の何れを単位としてパラメータ（次数も含む）を決定するかを、実際の運用（あるいは、運用テスト）に応じて選択することも考えられる。すると、構造物データの検索の精度をより向上できる方法を運用に応じて選択できるようになる。
【０１５４】
更に、ステップＳ１において、算出装置１００は、ノードおよびエッジの両方に着目して相対誤差を評価するものとしたが、ノードおよびエッジの何れかに着目して相対誤差を評価してもよい。また、算出装置１００は、特徴量の算出に用いる対称多項式のパラメータに限定して計算してもよい（例えば、ジャック対称多項式を用いないならパラメータαを求めなくてもよい）。そして、算出装置１００は、決定されたパラメータを用いて、下記の何れかの手順により特徴ベクトルを計算する。以降においてＮは、ノード数である。
【０１５５】
図１０は、特徴ベクトルの算出例（その１）を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。
（Ｓ１１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌとを取得する。
【０１５６】
（Ｓ１２）特徴量計算部１４０は、ｋ次の基本対称多項式ｅkを選択する。ここで、ｋは、１≦ｋ≦Ｋの整数である。ただし、ｋ＞Ｎのとき、ｅk＝０とする。
（Ｓ１３）特徴量計算部１４０は、行列Ｍlに対して、ｓｕｍC演算（式（３６））、ｓｕｍR演算（式（３５））、ｄｉａｇ演算（式（３７））それぞれにより取得されるベクトルＹ1jl，Ｙ2il，Ｙ3ilを計算する。ただし、ｌは、１≦ｌ≦Ｌの整数である。ベクトルＹ1jl，Ｙ2il，Ｙ3ilは、式（４３）、（４４）、（４５）で表される。
【０１５７】
【数４３】
2015191617.tif 000045
【０１５８】
【数４４】
2015191617.tif 000046
【０１５９】
【数４５】
2015191617.tif 000047
【０１６０】
（Ｓ１４）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ１５）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ１６〜Ｓ２１を実行する。
【０１６１】
（Ｓ１６）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ１７〜Ｓ２０を実行する。
（Ｓ１７）特徴量計算部１４０は、ｍ＝１，２，３と順番に代入して、ｍの代入値毎に、ステップＳ１８，Ｓ１９を実行する。
【０１６２】
（Ｓ１８）特徴量計算部１４０は、式（４６）で示されるＦ（ａ）＝ｅk,lの値を計算する。
【０１６３】
【数４６】
2015191617.tif 000048
【０１６４】
（Ｓ１９）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ２０）特徴量計算部１４０は、ｍ＝３までの計算が完了すると、処理をステップＳ２１に進める。それ以外の場合は、処理をステップＳ１７に進める。
【０１６５】
（Ｓ２１）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ２２に進める。それ以外の場合は、処理をステップＳ１６に進める。
（Ｓ２２）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ２３に進める。それ以外の場合は、処理をステップＳ１５に進める。
【０１６６】
（Ｓ２３）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・，Ｆ（３ＫＬ））を、ステップＳ１１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０１６７】
このように、算出装置１００は、基本対称多項式を用いて特徴量および特徴ベクトルを算出する。例えば、算出装置１００は、基本対称多項式の代わりに完全対称多項式や冪和対称多項式などを用いても、図１０に示した手順と同様の手順を実行できる。
【０１６８】
図１１は、特徴ベクトルの算出例（その２）を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。
（Ｓ３１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌとを取得する。
【０１６９】
（Ｓ３２）特徴量計算部１４０は、ｋ次の完全対称多項式ｈkを選択する。ここで、ｋは、１≦ｋ≦Ｋの整数である。ただし、ｋ＞Ｎのとき、ｈk＝０とする。
（Ｓ３３）特徴量計算部１４０は、式（４）により行列Ｍlを計算する。
【０１７０】
（Ｓ３４）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ３５）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ３６〜Ｓ４１を実行する。
【０１７１】
（Ｓ３６）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ３７〜Ｓ４０を実行する。
（Ｓ３７）特徴量計算部１４０は、ｋ’＝１からｋ’＝Ｋまで順番に代入して、ｋ’の代入値毎に、ステップＳ３８，Ｓ３９を実行する。
【０１７２】
（Ｓ３８）特徴量計算部１４０は、式（４７）で示されるＦ（ａ）＝ｈk（ｋ’，ｌ）の値を計算する。
【０１７３】
【数４７】
2015191617.tif 000049
【０１７４】
（Ｓ３９）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ４０）特徴量計算部１４０は、ｋ’＝Ｋまでの計算が完了すると、処理をステップＳ４１に進める。それ以外の場合は、処理をステップＳ３７に進める。
【０１７５】
（Ｓ４１）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ４２に進める。それ以外の場合は、処理をステップＳ３６に進める。
（Ｓ４２）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ４３に進める。それ以外の場合は、処理をステップＳ３５に進める。
【０１７６】
（Ｓ４３）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・，Ｆ（Ｋ2Ｌ））を、ステップＳ３１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０１７７】
このように、算出装置１００は２階のテンソル（行列に相当）を１階のテンソル（ベクトルに相当）に変換する際に対称多項式を利用し、当該１階のテンソルの各要素を同じ種類の対称多項式の各変数に代入して特徴量を計算してもよい。これにより、グラフに含まれる重みを適切に特徴量に反映させることができる。
【０１７８】
図１２は、特徴ベクトルの算出例（その３）を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。
（Ｓ５１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌとを取得する。
【０１７９】
（Ｓ５２）特徴量計算部１４０は、ｋ（１≦ｋ≦Ｋの整数）に対し、ｋの分割λを取得する。すなわち、特徴量計算部１４０は、ｋ＝１，２，・・・，Ｋの各整数に対し、複数の分割λを取得することになる。
【０１８０】
（Ｓ５３）特徴量計算部１４０は、ステップＳ５２で取得した分割λによって定まるモノミアル対称多項式ｍλを選択する。
（Ｓ５４）特徴量計算部１４０は、式（４）により行列Ｍlを計算する。
【０１８１】
（Ｓ５５）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ５６）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ５７〜Ｓ６４を実行する。
【０１８２】
（Ｓ５７）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ５８〜Ｓ６３を実行する。
（Ｓ５８）特徴量計算部１４０は、現在のｋに対する全ての分割λについて、分割λ毎に、ステップＳ５９〜Ｓ６２を実行する。
【０１８３】
（Ｓ５９）特徴量計算部１４０は、現在のｋに対する全ての分割λ’について、分割λ’毎に、ステップＳ６０，Ｓ６１を実行する。
（Ｓ６０）特徴量計算部１４０は、式（４８）で示されるＦ（ａ）＝ｍλ（λ’，ｌ）の値を計算する。
【０１８４】
【数４８】
2015191617.tif 000050
【０１８５】
（Ｓ６１）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ６２）特徴量計算部１４０は、現在のｋに対する全ての分割λ’について計算が完了すると、処理をステップＳ６３に進める。それ以外の場合は、処理をステップＳ５９に進める。
【０１８６】
（Ｓ６３）特徴量計算部１４０は、現在のｋに対する全ての分割λについて計算が完了すると、処理をステップＳ６４に進める。それ以外の場合は、処理をステップＳ５８に進める。
【０１８７】
（Ｓ６４）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ６５に進める。それ以外の場合は、処理をステップＳ５７に進める。
（Ｓ６５）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ６６に進める。それ以外の場合は、処理をステップＳ５６に進める。
【０１８８】
（Ｓ６６）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・）を、ステップＳ５１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０１８９】
図１３は、特徴ベクトルの算出例（その４）を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。
（Ｓ７１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌとを取得する。
【０１９０】
（Ｓ７２）特徴量計算部１４０は、ｋ次の冪和対称多項式ｐkを選択する。ここで、ｋは、１≦ｋ≦Ｋの整数である。
（Ｓ７３）特徴量計算部１４０は、式（４）により行列Ｍlを計算する。
【０１９１】
（Ｓ７４）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ７５）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ７６〜Ｓ８１を実行する。
【０１９２】
（Ｓ７６）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ３７〜Ｓ４０を実行する。
（Ｓ７７）特徴量計算部１４０は、ｋ’＝１からｋ’＝Ｋまで順番に代入して、ｋ’の代入値毎に、ステップＳ７８，Ｓ７９を実行する。
【０１９３】
（Ｓ７８）特徴量計算部１４０は、式（４９）で示されるＦ（ａ）＝ｐk（ｋ’，ｌ）の値を計算する。
【０１９４】
【数４９】
2015191617.tif 000051
【０１９５】
（Ｓ７９）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ８０）特徴量計算部１４０は、ｋ’＝Ｋまでの計算が完了すると、処理をステップＳ８１に進める。それ以外の場合は、処理をステップＳ７７に進める。
【０１９６】
（Ｓ８１）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ８２に進める。それ以外の場合は、処理をステップＳ７６に進める。
（Ｓ８２）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ８３に進める。それ以外の場合は、処理をステップＳ７５に進める。
【０１９７】
（Ｓ８３）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・，Ｆ（Ｋ2Ｌ））を、ステップＳ７１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０１９８】
図１４は、特徴ベクトルの算出例（その５）を示すフローチャートである。以下、図１４に示す処理をステップ番号に沿って説明する。
（Ｓ９１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌとを取得する。
【０１９９】
（Ｓ９２）特徴量計算部１４０は、ｋ（１≦ｋ≦Ｋの整数）に対し、ｋの分割λを取得する。すなわち、特徴量計算部１４０は、ｋ＝１，２，・・・，Ｋの各整数に対し、複数の分割λを取得することになる。
【０２００】
（Ｓ９３）特徴量計算部１４０は、ステップＳ９２で取得した分割λによって定まるシューア多項式ｓλおよびモノミアル対称多項式ｍλを選択する。
（Ｓ９４）特徴量計算部１４０は、式（４）により行列Ｍlを計算する。
【０２０１】
（Ｓ９５）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ９６）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ９７〜Ｓ１０４を実行する。
【０２０２】
（Ｓ９７）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ９８〜Ｓ１０３を実行する。
（Ｓ９８）特徴量計算部１４０は、現在のｋに対する全ての分割λについて、分割λ毎に、ステップＳ９９〜Ｓ１０２を実行する。
【０２０３】
（Ｓ９９）特徴量計算部１４０は、現在のｋに対する全ての分割λ’について、分割λ’毎に、ステップＳ１００，Ｓ１０１を実行する。
（Ｓ１００）特徴量計算部１４０は、式（５０）で示されるＦ（ａ）＝ｓλ（λ’，ｌ）の値を計算する。
【０２０４】
【数５０】
2015191617.tif 000052
【０２０５】
（Ｓ１０１）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ１０２）特徴量計算部１４０は、現在のｋに対する全ての分割λ’について計算が完了すると、処理をステップＳ１０３に進める。それ以外の場合は、処理をステップＳ９９に進める。
【０２０６】
（Ｓ１０３）特徴量計算部１４０は、現在のｋに対する全ての分割λについて計算が完了すると、処理をステップＳ１０４に進める。それ以外の場合は、処理をステップＳ９８に進める。
【０２０７】
（Ｓ１０４）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ１０５に進める。それ以外の場合は、処理をステップＳ９７に進める。
（Ｓ１０５）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ１０６に進める。それ以外の場合は、処理をステップＳ９６に進める。
【０２０８】
（Ｓ１０６）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・）を、ステップＳ９１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０２０９】
このように、算出装置１００は、２階のテンソルを１階のテンソルに変換する際に対称多項式（第１の種類の対称多項式）を利用し、その結果を他種類の対称多項式（第２の種類の対称多項式）に代入して特徴量を計算してもよい。これにより、グラフに含まれる重みを適切に特徴量に反映させることができる。
【０２１０】
図１５は、特徴ベクトルの算出例（その６）を示すフローチャートである。以下、図１５に示す処理をステップ番号に沿って説明する。
（Ｓ１１１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌ，αとを取得する。
【０２１１】
（Ｓ１１２）特徴量計算部１４０は、ｋ（１≦ｋ≦Ｋの整数）に対し、ｋの分割λを取得する。すなわち、特徴量計算部１４０は、ｋ＝１，２，・・・，Ｋの各整数に対し、複数の分割λを取得することになる。
【０２１２】
（Ｓ１１３）特徴量計算部１４０は、ステップＳ１１２で取得した分割λによって定まるジャック対称多項式Ｊλ(α)およびシューア多項式ｓλを選択する。
（Ｓ１１４）特徴量計算部１４０は、式（４）により行列Ｍlを計算する。
【０２１３】
（Ｓ１１５）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ１１６）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ１１７〜Ｓ１２４を実行する。
【０２１４】
（Ｓ１１７）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ１１８〜Ｓ１２３を実行する。
（Ｓ１１８）特徴量計算部１４０は、現在のｋに対する全ての分割λについて、分割λ毎に、ステップＳ１１９〜Ｓ１２２を実行する。
【０２１５】
（Ｓ１１９）特徴量計算部１４０は、現在のｋに対する全ての分割λ’について、分割λ’毎に、ステップＳ１２０，Ｓ１２１を実行する。
（Ｓ１２０）特徴量計算部１４０は、式（５１）で示されるＦ（ａ）＝Ｊλ(α)（λ’，ｌ）の値を計算する。
【０２１６】
【数５１】
2015191617.tif 000053
【０２１７】
（Ｓ１２１）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ１２２）特徴量計算部１４０は、現在のｋに対する全ての分割λ’について計算が完了すると、処理をステップＳ１２３に進める。それ以外の場合は、処理をステップＳ１１９に進める。
【０２１８】
（Ｓ１２３）特徴量計算部１４０は、現在のｋに対する全ての分割λについて計算が完了すると、処理をステップＳ１２４に進める。それ以外の場合は、処理をステップＳ１１８に進める。
【０２１９】
（Ｓ１２４）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ１２５に進める。それ以外の場合は、処理をステップＳ１１７に進める。
（Ｓ１２５）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ１２６に進める。それ以外の場合は、処理をステップＳ１１６に進める。
【０２２０】
（Ｓ１２６）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・）を、ステップＳ１１１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０２２１】
図１６は、特徴ベクトルの算出例（その７）を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。
（Ｓ１３１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌ，ｔとを取得する。
【０２２２】
（Ｓ１３２）特徴量計算部１４０は、ｋ（１≦ｋ≦Ｋの整数）に対し、ｋの分割λを取得する。すなわち、特徴量計算部１４０は、ｋ＝１，２，・・・，Ｋの各整数に対し、複数の分割λを取得することになる。
【０２２３】
（Ｓ１３３）特徴量計算部１４０は、ステップＳ１３２で取得した分割λによって定まるホール−リトルウッド対称多項式Ｐλ（；ｔ）を選択する。
（Ｓ１３４）特徴量計算部１４０は、行列Ｍlに対して、ｓｕｍC演算、ｓｕｍR演算、ｄｉａｇ演算それぞれにより取得されるベクトルＹ1jl，Ｙ2il，Ｙ3ilを計算する。ただし、ｌは、１≦ｌ≦Ｌの整数である。ベクトルＹ1jl，Ｙ2il，Ｙ3ilは、式（４３）、（４４）、（４５）で表される。
【０２２４】
（Ｓ１３５）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ１３６）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ１３７〜Ｓ１４４を実行する。
【０２２５】
（Ｓ１３７）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ１３８〜Ｓ１４３を実行する。
（Ｓ１３８）特徴量計算部１４０は、現在のｋに対する全ての分割λについて、分割λ毎に、ステップＳ１３９〜Ｓ１４２を実行する。
【０２２６】
（Ｓ１３９）特徴量計算部１４０は、ｍ＝１，２，３と順番に代入して、ｍの代入値毎に、ステップＳ１４０，Ｓ１４１を実行する。
（Ｓ１４０）特徴量計算部１４０は、式（５２）で示されるＦ（ａ）＝Ｐλ,l（；ｔ）の値を計算する。
【０２２７】
【数５２】
2015191617.tif 000054
【０２２８】
（Ｓ１４１）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ１４２）特徴量計算部１４０は、ｍ＝３までの計算が完了すると、処理をステップＳ１４３に進める。それ以外の場合は、処理をステップＳ１３９に進める。
【０２２９】
（Ｓ１４３）特徴量計算部１４０は、現在のｋに対する全ての分割λについて計算が完了すると、処理をステップＳ１４４に進める。それ以外の場合は、処理をステップＳ１３８に進める。
【０２３０】
（Ｓ１４４）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ１４５に進める。それ以外の場合は、処理をステップＳ１３７に進める。
（Ｓ１４５）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ１４６に進める。それ以外の場合は、処理をステップＳ１３６に進める。
【０２３１】
（Ｓ１４６）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・）を、ステップＳ１３１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０２３２】
図１７は、特徴ベクトルの算出例（その８）を示すフローチャートである。以下、図１７に示す処理をステップ番号に沿って説明する。
（Ｓ１５１）特徴量計算部１４０は、特徴ベクトルの計算対象とするグラフデータと、パラメータ設定部１３０が決定したパラメータＫ，Ｌ，ｔ，ｑとを取得する。
【０２３３】
（Ｓ１５２）特徴量計算部１４０は、ｋ（１≦ｋ≦Ｋの整数）に対し、ｋの分割λを取得する。すなわち、特徴量計算部１４０は、ｋ＝１，２，・・・，Ｋの各整数に対し、複数の分割λを取得することになる。
【０２３４】
（Ｓ１５３）特徴量計算部１４０は、ステップＳ１３２で取得した分割λによって定まるマクドナルド対称多項式Ｐλ（；ｔ，ｑ）を選択する。
（Ｓ１５４）特徴量計算部１４０は、行列Ｍlに対して、ｓｕｍC演算、ｓｕｍR演算、ｄｉａｇ演算それぞれにより取得されるベクトルＹ1jl，Ｙ2il，Ｙ3ilを計算する。ただし、ｌは、１≦ｌ≦Ｌの整数である。ベクトルＹ1jl，Ｙ2il，Ｙ3ilは、式（４３）、（４４）、（４５）で表される。
【０２３５】
（Ｓ１５５）特徴量計算部１４０は、変数ａに０を代入する。
（Ｓ１５６）特徴量計算部１４０は、ｌ＝１からｌ＝Ｌまで順番に代入して、ｌの代入値毎に、ステップＳ１５７〜Ｓ１６４を実行する。
【０２３６】
（Ｓ１５７）特徴量計算部１４０は、ｋ＝１からｋ＝Ｋまで順番に代入して、ｋの代入値毎に、ステップＳ１５８〜Ｓ１６３を実行する。
（Ｓ１５８）特徴量計算部１４０は、現在のｋに対する全ての分割λについて、分割λ毎に、ステップＳ１５９〜Ｓ１６２を実行する。
【０２３７】
（Ｓ１５９）特徴量計算部１４０は、ｍ＝１，２，３と順番に代入して、ｍの代入値毎に、ステップＳ１６０，Ｓ１６１を実行する。
（Ｓ１６０）特徴量計算部１４０は、式（５３）で示されるＦ（ａ）＝Ｐλ,l（；ｔ，ｑ）の値を計算する。
【０２３８】
【数５３】
2015191617.tif 000055
【０２３９】
（Ｓ１６１）特徴量計算部１４０は、ａにａ＋１を代入する。
（Ｓ１６２）特徴量計算部１４０は、ｍ＝３までの計算が完了すると、処理をステップＳ１６３に進める。それ以外の場合は、処理をステップＳ１５９に進める。
【０２４０】
（Ｓ１６３）特徴量計算部１４０は、現在のｋに対する全ての分割λについて計算が完了すると、処理をステップＳ１６４に進める。それ以外の場合は、処理をステップＳ１５８に進める。
【０２４１】
（Ｓ１６４）特徴量計算部１４０は、ｋ＝Ｋまでの計算が完了すると、処理をステップＳ１６５に進める。それ以外の場合は、処理をステップＳ１５７に進める。
（Ｓ１６５）特徴量計算部１４０は、ｌ＝Ｌまでの計算が完了すると、処理をステップＳ１６６に進める。それ以外の場合は、処理をステップＳ１５６に進める。
【０２４２】
（Ｓ１６６）特徴量計算部１４０は、Ｆ＝（Ｆ（０），Ｆ（１），・・・）を、ステップＳ１５１で取得したグラフデータに対する特徴ベクトルとする。特徴量計算部１４０は、グラフデータに対応する構造物データを特定する。特徴量計算部１４０は、特定した構造物データに対応付けて、算出した特徴ベクトルを記憶部１１０に格納する。
【０２４３】
このように、算出装置１００は、グラフデータから対称多項式の次数およびパラメータを決定し、対称多項式を用いて構造物データに対応する特徴量（あるいは、複数の種類の特徴量を含む特徴ベクトル）を計算する。これにより、構造物データの検索に適した特徴量を効率的に算出できる。具体的には次の通りである。
【０２４４】
形状検索用のグラフの特徴量には、ノードへの番号付けの順序に依存しないこと（対称群不変性。対称群をＳNと記してＳN不変性ということもある）が求められる。同じ形状でもノードへの番号付けの順序が違えば異なる特徴量となるようでは、構造物データの検索を適切に行えないからである。ここで、「ノードへの番号付け」とは便宜的な表現であり、グラフに含まれるノードおよびエッジの重みをどのような順番で取り扱うか（例えば、ノードの重みをベクトルで示すなら、あるノードの重みを何番目の要素とするか）を意味していると考えてもよい。
【０２４５】
図１８は、ノードへの番号付けの例を示す図である。図１８（Ａ）および図１８（Ｂ）は、ある構造物データに対するグラフに対して１〜８までの番号を付す２つのパターンを例示している。この例では、何れのグラフも同じ形状に対応するものだから、同じ特徴量を得ることが望まれる。
【０２４６】
ところが、対称群不変性をもたない量（グラフデータに含まれるノードやエッジの重み）を対称群不変な量に変換するとき、その計算コストが問題となる。例えば、グラフのノード数をＮとすると、対称群の位数はＮ！となり、それらを全て考慮にいれた対称群不変量（ＳN不変量ということもある）を、ノードやエッジの重みから計算するのは容易でない。第１の実施の形態で例示したように、Ｏ（Ｎ！）の計算複雑性をもつ演算を用いると、ノード数が増えるほど計算コストが極度に増大してしまう。このため、構造物の頂点数が増大するほど特徴量を算出するための計算コストが膨大になる（例えば、頂点数が比較的多い複雑な形状などの特徴量の計算には非効率である）。また、複数の種類の特徴量を作成して特徴ベクトルとする場合に、各特徴量に対してＯ（Ｎ！）の計算複雑性をもつ演算を行っていると計算コストの増加が一層深刻になる。他方、例えば、クリークの数を求めるなど、ＮＰ困難な問題を用いると、計算コストが膨大となり現実的でない。
【０２４７】
このように、計算コストがあまりにも大きい演算方法を採用すると検索の実用に耐え難くなるおそれがある。そこで、算出装置１００は、特徴量の計算に対称多項式を用いることで、特徴量を計算する際の計算コストを軽減する。第２の実施の形態の算出方法によれば、冪和対称多項式を用いて、特徴量の演算を高々Ｏ（Ｎ2）の計算複雑性に抑えることができる。また、第２の実施の形態で例示した冪和対称多項式以外の対称多項式を用いれば、特徴量の演算を高々Ｏ（ｅN）程度の計算複雑性に抑え得ることが期待される。
【０２４８】
このため、算出装置１００によれば、Ｏ（Ｎ！）の計算複雑性をもつ演算で特徴量を計算するよりも、計算コストを低減できる。特徴ベクトルを計算する場合に、Ｏ（Ｎ！）の計算複雑性をもつ演算で全ての特徴量を計算するよりも、計算コストを低減できる。特に、冪和対称多項式を選択すれば、他の種類の対称多項式に比べて、計算コストをより一層抑えられる。
【０２４９】
このとき、算出装置１００は、グラフデータ（グラフの情報）から次数ｋやパラメータｌを決定する。前述のように、ノードおよびエッジの重みは、構造物の形状を反映した情報であると考えられる。例えば、式（６）で示されるように、重みの乗算回数は次数ｋとパラメータｌとの積ｋｌで求められる。乗算は一般に値の違いを大きくする。重みの差異が特徴量に極端に大きく反映され過ぎると、比較的小さな形状の差異が比較的大きな特徴量の差異として表されてしまい、検索時の特徴量の照合において、類似の判定が困難になるおそれがある。一方、乗算回数が小さ過ぎると重みの差異が特徴量に十分に反映されないおそれもある。
【０２５０】
そこで、算出装置１００は、乗算で重みの違いが極端に大きくならないように（また、重みの差異が適度に特徴量に反映されるように）次数ｋおよびパラメータｌをグラフの重みの情報から動的に調整する（例えば、式（４０））。これにより、類似形状の検索用途に適した特徴量を算出できる。また、算出装置１によれば乗算回数ｋｌを所定の基準で制限できるので、グラフデータによらずに固定的にｋ，ｌを決定して無暗に乗算を重ねるよりも、検索に適した特徴量を比較的小さな計算コストで取得できる。
【０２５１】
また、第２の実施の形態の例では、次数ｋおよびパラメータｌが大きいほど、算出される特徴量の種類の数も増える。例えば、図１０の手順では、３ＫＬ個の特徴量が算出されることになる。図９で例示したようにＫ＝Ｌとすることで、重みの乗算回数や特徴量の種類の数を抑え、特徴ベクトルの計算に伴う計算コストが増大し過ぎないよう制限できる。
【０２５２】
なお、算出装置１００は、対称多項式の演算用の次数およびパラメータを、特徴量の算出対象とする構造物データ以外の他の構造物データに対応するグラフデータを用いて決定してもよい。例えば、算出装置１００は、検索クエリを受け付けた場合、当該検索クエリで指定された構造物データに対応するグラフデータから特徴量（特徴ベクトル）を計算し、ライブラリ内の構造物データの特徴量（特徴ベクトル）と照合することになる。その場合、算出装置１００は、ライブラリ内の構造物データに対して既に決定済みの次数およびパラメータを用いて、検索クエリで指定された構造物データに対応する特徴量（特徴ベクトル）を算出し得る。ただし、算出装置１００は、検索クエリで指定された構造物データに対応するグラフデータから、次数およびパラメータを決定してもよい。
【０２５３】
また、第１の実施の形態の情報処理は、演算部１ｂにプログラムを実行させることで実現できる。また、第２の実施の形態の情報処理は、プロセッサ１０１にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体１３に記録できる。
【０２５４】
例えば、プログラムを記録した記録媒体１３を配布することで、プログラムを流通させることができる。また、プログラムを他のコンピュータに格納しておき、ネットワーク経由でプログラムを配布してもよい。コンピュータは、例えば、記録媒体１３に記録されたプログラムまたは他のコンピュータから受信したプログラムを、ＲＡＭ１０２やＨＤＤ１０３などの記憶装置に格納し（インストールし）、当該記憶装置からプログラムを読み込んで実行してもよい。
【０２５５】
以上の第１，第２の実施の形態を含む実施形態に関し、更に以下の付記を開示する。
（付記１）  複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を取得し、
対称多項式の演算に用いられる次数およびパラメータを前記情報に基づいて決定し、
決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する、
処理をコンピュータに実行させる算出プログラム。
【０２５６】
（付記２）  前記決定では、グラフの情報に含まれる重みの分布に基づいて、次数およびパラメータを決定する、付記１記載の算出プログラム。
（付記３）  前記演算は、次数およびパラメータが大きいほど重みの乗算回数が増える演算であり、
前記決定では、重みの相対誤差が大きいほど次数およびパラメータを小さい値とする、付記２記載の算出プログラム。
【０２５７】
（付記４）  前記決定では、複数の構造物データに対応する複数のグラフの情報に基づいて、次数およびパラメータを決定する、付記１乃至３の何れか１つに記載の算出プログラム。
【０２５８】
（付記５）  前記決定では、特徴量の算出対象の構造物データ毎に、当該構造物データに対応するグラフの情報から次数およびパラメータを決定する、付記１乃至３の何れか１つに記載の算出プログラム。
【０２５９】
（付記６）  前記算出では、他の構造物データに対応するグラフの情報に基づいて決定された次数およびパラメータを用いる、付記１乃至４の何れか１つに記載の算出プログラム。
【０２６０】
（付記７）  前記算出では、グラフに含まれるノードおよびエッジの重みの情報を反映させた行列を生成し、第１の種類の対称多項式を用いて当該行列をベクトルに変換し、前記第１の種類の対称多項式または第２の種類の対称多項式の何れかに前記ベクトルの各要素を代入することで特徴量を算出する、付記１乃至６の何れか１つに記載の算出プログラム。
【０２６１】
（付記８）  前記算出では、冪和対称多項式、基本対称多項式、完全対称多項式、モノミアル対称多項式、シューア多項式、ジャック対称多項式、ホール−リトルウッド対称多項式またはマクドナルド対称多項式を用いる、付記１乃至７の何れか１つに記載の算出プログラム。
【０２６２】
（付記９）  複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を記憶する記憶部と、
対称多項式の演算に用いられる次数およびパラメータを前記情報に基づいて決定し、
決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する、演算部と、
を有する算出装置。
【０２６３】
（付記１０）  コンピュータが、
複数の多角形で３次元の構造物を表す構造物データに対応するグラフの情報を取得し、
対称多項式の演算に用いられる次数およびパラメータを前記情報に基づいて決定し、
決定した次数とパラメータと対称多項式とを用いて構造物データに対応するグラフの特徴量を算出する、
算出方法。
【符号の説明】
【０２６４】
１  算出装置
１ａ  記憶部
１ｂ  演算部
【図１】
2015191617.tif 000056
【図２】
2015191617.tif 000057
【図３】
2015191617.tif 000058
【図４】
2015191617.tif 000059
【図５】
2015191617.tif 000060
【図６】
2015191617.tif 000061
【図７】
2015191617.tif 000062
【図８】
2015191617.tif 000063
【図９】
2015191617.tif 000064
【図１０】
2015191617.tif 000065
【図１１】
2015191617.tif 000066
【図１２】
2015191617.tif 000067
【図１３】
2015191617.tif 000068
【図１４】
2015191617.tif 000069
【図１５】
2015191617.tif 000070
【図１６】
2015191617.tif 000071
【図１７】
2015191617.tif 000072
【図１８】
2015191617.tif 000073