物体の形状に関する情報を表す特徴データを確定するための装置およびプログラム
【課題】幾何学特徴データを確定するための、正確さ、および／又は効力、および／又は性能、および／又は有用性が改善された技術を提供する。
【解決手段】本発明の第一の態様によると、複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合い、本発明の第二の態様によると、複数の区域（ｒ）に含まれる物体の対応する部分が所定の測定基準に関して互いにほぼ等しいように、セル（ｐ）の少なくともいくつかの境界が物体が位置する空間内の該複数の区域（ｒ）を区切る。
【解決手段】本発明の第一の態様によると、複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合い、本発明の第二の態様によると、複数の区域（ｒ）に含まれる物体の対応する部分が所定の測定基準に関して互いにほぼ等しいように、セル（ｐ）の少なくともいくつかの境界が物体が位置する空間内の該複数の区域（ｒ）を区切る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、異なった形状と異なった幾何学的特徴の物体のコンピューターベース処理（ｃｏｍｐｕｔｅｒ−ｂａｓｅｄ ｐｒｏｃｅｓｓｉｎｇ）を行う技術分野に関する。更に詳しくは、本発明は物体形状に関する情報を示す特徴データを確定し使用する分野に関する。本発明が教示することは、たんぱく質、CAD、ウェブデータの類似探索と類似分類などの様々なアプリケーションに用いることができるが、アプリケーションはこれらに限られてはいない。
【０００２】
過去１０年間、類似探索のための効率的かつ効果的なサポートを必須条件としたデータベースアプリケーションが益々多数出現している。マルチメディア、医療関係のイメージング、分子生物学、コンピューター援用エンジニアリング、マーケティング、購買、管理などのアプリケーション分野では類似探索（ｓｉｍｉｌａｒｉｔｙ ｓｅａｒｃｈ）と類似分類（ｓｉｍｉｌａｒｉｔｙ ｃｌａｓｓｉｆｉｃａｔｉｏｎ）がより重要視されている。特に、類似した二次元、三次元の形状を見つけ出す作業が益々重要視されている。幾何学的物体の形状に基づいて、類似した物体を読み出し（類似探索）、類似した物体のクラスタを検出（分類）しなければならない。
【０００３】
【０００４】
【０００５】
研究論文「Ｒｏｔａｔｉｏｎ Ｉｎｖａｒｉａｎｔ Ｓｐｈｅｒｉｃａｌ Ｈａｒｍｏｎｉｃ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ３Ｄ Ｓｈａｐｅ Ｄｅｓｃｒｉｐｔｏｒｓ（三次元形状記述子の回転不変球面調和関数表現）」Ｋａｚｈｄａｎ Ｍ．，Ｆｕｎｋｈｏｕｓｅｒ Ｔ．，Ｒｕｓｉｎｋｉｅｗｅｃｚ Ｓ著、Ｐｒｏｃ．１ｓｔ Ｅｕｒｏｇｒａｐｈｉｃｓ Ｓｙｍｐｓｉｕｍ ｏｎ Ｇｅｏｍｅｔｒｙ Ｐｒｏｃｅｓｓｉｎｇ（ＳＧＰ），Ａａｃｈｅｎ，２００３，ｐｐ．１６７−１７５には、形状の類似性を評価する際の問題点についての様々な公知の取り組みの概説が含まれている。
【０００６】
本発明の目的は、幾何学特徴データを確定する先行技術の方法の正確さ、および／又は効力、および／又は性能、および／又は有用性を改善する技術を提供することである。好まれる実施の形態では、特徴データが次の類似探索か類似分類の正確さを改善するプロパティー（ｐｒｏｐｅｒｔｙ）を持っており、それにより全体的な正確さの改善を達成したり、および／又は要求される正確さの水準に達する為に必要な計算量と記憶量を削減することができる。
【０００７】
本発明によると、上記の目的は、独立請求項記載の装置およびコンピュータプログラムによって、少なくとも部分的には達成される。従属請求項は本発明の好まれる実施の形態を定義している。
【０００８】
発明の第一の態様は、少なくとも二つのセル（ｃｅｌｌ）が少なくとも部分的に重なり合うように複数のセルを定義する分割スキーム（ｐａｒｔｉｔｉｏｎｉｎｇ ｓｃｈｅｍｅ）を使うアイディアに基づいている。そのような分割スキームはまた、本願では「重複する分割スキーム」と呼ぶ。この重複性そのものにも計算量の追加が必要になる。しかしながら実験の結果によると、この影響を補うに余るほど、入手した特徴データの正確さが向上するので、先行技術で必要なものに比べより粗い分割スキームを使うことが可能になる、という驚くべきことが発見された。全体的に見て、総計算量と総記憶量は一見無駄と思われる重複する分割スキームによって大きく削減される。
【０００９】
本発明の第二の態様によると、複数のセルを定義する分割スキームが使われており、これらのセルの少なくともいくつかの境界は物体の位置する空間内にある複数の区域を区切り、この複数の区域に含まれる物体のそれぞれの部分が、所定の測定基準に関してはほとんど等しくなる。本願では、そのような区域にグループ分けすることができるセルを定義する分割スキームを「比例分割スキーム」と呼ぶ。先と同様に、実験によると、比例分割スキームを使うことにより全体的な正確さの向上が達成され、および／又は従来必要とされるよりも粗い分割スキームを選ぶことが可能になる。
【００１０】
本発明の好ましい実施例では、分割スキームが重なりあう多数のセルを定義することができる。例えば、分割スキームにより定義された全てのセルの少なくとも５０％又は少なくとも９０％は他のセルと部分的もしくは全体的に重なり合うこともある。実施例によっては、複数のセルが、物体が存在する空間内の同一の区域を異なって分割するセルの二つ以上のグループを含んでいるものもある。言い換えると、これらのセルの各グループ内にある全てのセルの各ユニオンは同一空間にあり、一つのグループ内の各セルは、他の各グループの少なくとも一つのセルと少なくとも部分的に重なり合っている。
【００１１】
本発明の実施例によっては、分割スキームによって定義されるセルはネストされたセル（ｎｅｓｔｅｄ ｃｅｌｌｓ）のグループから成る。このグループでは、重なり合っているセルはそれぞれ全体的に重なり合っている。分割スキームは、このネストされたセルのグループに属さない追加のセルを定義してもしなくても良い。ネストされたセルのグループのセルは、好ましくは、ネストされたセルのグループのセル内に含まれる物体の各部分のｋ次元の体積が、ほぼ規則的に、又はきちんと規則的に増加するシーケンスを形成する。言い換えると、ネストされたセルのグループ内の第一のセルは物体の一体積ユニットを含み、第二のセルはおおよそもう一体積ユニットを含み、第三のセルは更にもう一体積ユニットを含むということである。他の実施例では、セルの全体的な重なり合い、つまりセルのネスティングを指定せず、部分的な重なり合いのみを指定する分割スキームを用いる。
【００１２】
重複するか比例する分割スキームの使用によってすでに相当な効果があるが、重複しかつ比例する分割スキームの使用が特に好まれる。実験によると、この組み合わせにより、重複する分割スキームのみの利益と比例分割スキームのみの利益を単に合計した利益を超える、予期せぬ相乗的な利益が達成される。実施例によっては、重複する態様および比例する態様は、少なくとも比例区域の一つが、少なくとも二つの部分的に重なり合うセル又は完全に重なり合うセルを含むように組み合わされる。
【００１３】
実施例によっては、比例区域は互いにばらばらであり、他の実施例によっては、これらの区域は少なくとも部分的に重なり合っている。区域は、必ずしも物体が位置する全空間に及ぶ必要はない。実施例によっては、どの比例区域の部分でもない追加のセルがあり、他の実施例によっては、分割スキームよって定義される全てのセルが少なくとも区域の一つに属する。
【００１４】
測定基準によって区域内に含まれる物体の各部分がほぼ等しいことが必要とされるが、この測定基準は物体の各部分のｋ次元の体積であることが好ましい。三次元の場合、体積は各物体部分の「通常の」空間体積であり、二次元の体積は、各物体部分によって占められる実際の面積である。他の実施例では、例えば三次元の物体の部分の表面積といった他の基準が使用される。
【００１５】
本発明の第二の態様によると、比例区域は分割スキームによって定義されるセルの境界によって区切られる。好ましい実施例では、各区域が少なくとも二つのセルのユニオンおよび／又は差異および／又は交差部分に相当するか、一つのセルにぴったり相当することを意味する。好ましくは、各区域は単一のセル、セルのグループ、あるいは第一のセル又はセルのグループから第二のセル又はセルのグループを引いた差異に相当する。
【００１６】
一般的に、セルおよび／又は区域はどんな適切な形状でもよいが、標準的な形状がたいていは効果的である。セルおよび／又は区域の少なくともいくつか、あるいはセルおよび／又は区域の全てが以下の形状の内の一つであることが好ましい。物体が位置する空間において、ｋ次元の球体、ｋ次元のシェル形、ｋ次元の球体のセクタ、ｋ次元のシェル形のセクタである。
【００１７】
本発明は、分割スキームのセル内に含まれる物体のそれぞれの部分の少なくとも一つのプロパティーに基づいて、物体の特徴データを確定するステップから成る。このステップを遂行するいくつかの方法自体は周知であり、本発明の実施に関連しても使用してもよい。例えば、複数のセルの各セル内に含まれる物体のそれぞれの部分のｋ次元の体積に基づいて、および／又は複数のセルの各セル内に含まれる物体のそれぞれの部分のｋ主軸を定義するデータに基づいて、物体の特徴データを確定してもよい。
【００１８】
実施例によっては、本発明によって得られる特徴データは特徴ベクトルである。この特徴データは様々な方法で使用できるが、それ自体も周知である。例えば、特徴データは複数の物体の類似探索や類似分類を実行するために使用される。
【００１９】
本発明のコンピュータープログラム製品は、本発明の方法を実行するプログラムのインストラクションから成る。コンピュータープログラム製品は、例えば半導体メモリ、コンピューターディスク、ＣＤ−ＲＯＭといった有形のデータキャリアである。しかしながら、コンピュータープログラム製品は、例えばコンピューターネットワーク内で送信された信号といった無形のデータキャリアでもよい。本発明の装置は、本発明の方法を実行するようにプログラムされた一般的なパーソナルコンピューター、ワークステーション、メインフレームコンピューター、コンピューターネットワークである。コンピューター製品、および／又は装置の好ましい実施例は、上述した特徴、および／又は従属の方法の請求項の特徴に対応する特徴から成る。
【図面の簡単な説明】
【００２０】
【図１】物体と、それに対応する最小の境界となる球面の一例である。
【図２】先行技術によるばらばらで等距離にある分割スキームの一例である。
【図３】本発明の第一の実施例による、ばらばらな比例分割スキームの一例である。
【図４】本発明の第二の実施例による、重複し、等距離にある分割スキームの第一の例である。
【図５】本発明の第三の実施例による、重複し、等距離にある分割スキームの第二の例である。
【図６】本発明の第四の実施例による、重複する比例分割スキームの第一の例である。
【図７】本発明の第五の実施例による、重複する比例分割スキームの第二の例である。
【図８】図２の先行技術の分割スキームと図６の分割スキームとを比較し、精度と再現率の関係をプロットしたものである。
【図９】たんぱく質データについて、図２の先行技術による分割スキームを使用する分類にかかる総ランタイム（ｔｏｔａｌ ｒｕｎｔｉｍｅ）と、図６の分割スキームを使用する分類にかかる総ランタイムとを比較した図である。
【発明を実施するための形態】
【００２１】
【００２２】
【００２３】
【００２４】
【００２５】
【００２６】
【００２７】
図２は、先行技術で公知の分割スキームを三つのセル（ｄ＝３）で示したものである。この分割スキームは、（１）全てのセルｐｉはばらばらである、（２）セルｐｉの境界は等距離である、というプロパティを有する。第一のセルｐ１はｋ次元の球体（すなわち、ｋ＝２の場合は円、ｋ＝３の場合は空間にある球体）の形状であり、第二および第三のセルｐ２、ｐ３はそれぞれ最小の境界となる球体ｂｓ（ｏ）の中心ｃの周りにｋ次元のシェルの形状を有する。図２の分割スキームはばらばらで等距離であることからＤＥと呼ぶ。
【００２８】
図３は、本発明の第一のサンプルの実施例による分割スキームを三つのセル（ｄ＝３）で図示したものである。一般的に、本発明の全ての分割スキームは特に異種の物体のデーターベースに適している。図３の分割スキームはいわゆる比例分割スキームである。ここに記述するサンプルの実施例の比例分割スキームでは、セルの境界やこれらの境界のいくつかは、各区域内に占める物体の体積が少なくともほぼ一定であるように、空間内において多数の区域を区切る。したがって、セルおよび区域の境界は各物体の個々の形状に適合する。
【００２９】
【００３０】
図３の比例分割スキームは、ばらばらで比例することからＤＰと呼ばれる。図２の先行技術による分割スキームを形状ヒストグラムと称するならば、図３のアプローチは形状分位と呼ぶことができ、分位は分割スキームによって定義される分割セルの数ｄによって確定される。
【００３１】
【００３２】
図４のサンプルの実施例では、セルｐiはネストされたセルの単一のグループｇｎを形成する。言い換えると、最小のセルｐ１はセルｐ２に完全に含まれ、順を追ってセルｐ２は最大のセルｐ３に完全に含まれる。それゆえ、セルｐ１からｐ３は「内に含まれている」関係について、完全な順序シーケンスを構成している。更に、セルｐｉの境界は等距離である。
【００３３】
図５は、重複し等距離にある分割スキームの更なるサンプルの実施例を１７個のセル（ｄ＝１７）で示したものである。このスキームは、図２のセルｐ２とセルｐ３を更に分けることによって、図２の先行技術の分割スキームから得られる。より具体的には、図２の第二のセルｐ２は、内セルｐ２からｐ５の第一のグループｇｉ１と、内セルｐ６からｐ９の第二のグループｇｉ２とに更に分けられている。これらのグループｇｉ１、ｇｉ２のそれぞれに含まれるセルは、それぞれのグループｇｉ１、ｇｉ２内においてばらばらである。しかしながら、グループｇｉ１、ｇｉ２は、一方のグループある各セルが他方のグループの二つのセルに重なり合うように、互いに対してシフトしている。同様に、図２の第三のセルｐ３は外セルｐ１０からｐ１３の第一のグループｇｏ１と、外セルｐ１４からｐ１７の第二のグループｇｏ２とに更に分けられている。セルｐ２からｐ１７のそれぞれは、最小の境界となる球体ｂｓ（ｏ）内のｋ次元のシェルのセクタの形状をしている。
【００３４】
図４および図５の重複し等距離にある分割スキームの例は、それぞれＲＥ１（ｏ）、ＲＥ２（ｏ）と呼ぶ。
【００３５】
実験によると、比例する分割と重複する分割とが組み合わさっている場合、特に利益が大きい。重複と比例を組み合わせた分割スキームはＲＰと呼ぶ。図６および図７は、ＲＰ分割のサンプルの実施例を二つ示している。
【００３６】
【００３７】
更に注目すべき点として、図６の例では、セルｐ１からセルｐ３にある物体ｏの各部分の体積は、規則的に、すなわち各セルとも物体ｏの総体積の１／ｄづつ増加する。したがって、三つのセルの本例では、第一のセルｐ１は物体ｏの総体積の約１／３、第二のセルｐ２は約２／３、第三のセルｐ３は総体積を含む。
【００３８】
【００３９】
【００４０】
上述したサンプルの実施例では、所与の物体ｏの特徴ベクトルΦ（ｏ）は、対応する分割スキームによって定義される全てのセルｐに、集約αを当てはめることによって得られる全ての結果を、単に連結したものである。他の実施例では、更なる標準化、又は他の追加の処理ステップを実行してもよい。
【００４１】
全体として見ると、結果としてもたらされた類似性の指標を使用して、物体の幾何学的特徴によって物体の大きな集まりを分類したり、類似した物体のデータベース探索を行ったり、物体の幾何学的類似性を評価しなければならない他の作業を行ったりすることができる。
【００４２】
本発明の長所を評価するために、ここに提案した分割のアプローチの効力を先行技術による最も優れたテクニックの一つと比較する。先行技術による最も優れたテクニックとは、先に引用した研究論文「三次元形状記述子の回転不変球面調和関数表現」で提案しているような、球面の調和値の集約関数を用いたＤＥ分割に基づいている。非常に有望な結果が得られている。例えば、図８は、たんぱく質データベースに関する先行技術のＤＥ分割および本ＲＰ１分割の結果を示したものである。再現率５０％では、ＤＥに基づく方法では精度が２６％であるのに対して、ＲＰ１に基づく方法では４２％の精度を示している。再現率８０％では、ＲＰ１はＤＥよりもほぼ二倍の精度をもたらす。ＣＡＤおよびウェブデータに関しても同様の結果が得られている。
【００４３】
図９は、上記と同じ構成で得られる性能の結果を示している。ＲＰ１がＤＥよりも約十倍早く実行されることが明らかである。したがって、ＲＰ１はＤＥよりも非常に高い効力をもたらすだけではなく、ランタイムで見たコストが格段に低くなる。ＤＥの性能が遅いのは、よい結果を出すために、はるかにきめの細かい分割スキームを必要とするという事実のためである。したがって、作り出されたＤＥの特徴ベクトルは、距離関数によって評価すると、はるかにより長くて高価である。
【００４４】
類似性に基づいた探索および／又は分類の方法の正確さおよび効力を改善するために、本発明が利用できるということが明らかである。上述したサンプルの実施例の記述に含まれる詳細は、本発明の範囲を制限するように解釈されるべきではなく、むしろ本発明の好まれる実施例の例示として解釈されるべきである。他の多くのバリエーションが可能であり、当業者には容易に明らかである。それゆえ、本発明の範囲は、説明した実施例によって確定されるのではなく、添付の請求項およびそれらと法的に等価であるものによって確定される。
【００４５】
更なる特徴や、本発明の目的および効果は、以下に詳細に記述するいくつかのサンプルの実施例から明らかになる。図を参照とされたい。
【技術分野】
【０００１】
本発明は、一般的に、異なった形状と異なった幾何学的特徴の物体のコンピューターベース処理（ｃｏｍｐｕｔｅｒ−ｂａｓｅｄ ｐｒｏｃｅｓｓｉｎｇ）を行う技術分野に関する。更に詳しくは、本発明は物体形状に関する情報を示す特徴データを確定し使用する分野に関する。本発明が教示することは、たんぱく質、CAD、ウェブデータの類似探索と類似分類などの様々なアプリケーションに用いることができるが、アプリケーションはこれらに限られてはいない。
【０００２】
過去１０年間、類似探索のための効率的かつ効果的なサポートを必須条件としたデータベースアプリケーションが益々多数出現している。マルチメディア、医療関係のイメージング、分子生物学、コンピューター援用エンジニアリング、マーケティング、購買、管理などのアプリケーション分野では類似探索（ｓｉｍｉｌａｒｉｔｙ ｓｅａｒｃｈ）と類似分類（ｓｉｍｉｌａｒｉｔｙ ｃｌａｓｓｉｆｉｃａｔｉｏｎ）がより重要視されている。特に、類似した二次元、三次元の形状を見つけ出す作業が益々重要視されている。幾何学的物体の形状に基づいて、類似した物体を読み出し（類似探索）、類似した物体のクラスタを検出（分類）しなければならない。
【０００３】
【０００４】
【０００５】
研究論文「Ｒｏｔａｔｉｏｎ Ｉｎｖａｒｉａｎｔ Ｓｐｈｅｒｉｃａｌ Ｈａｒｍｏｎｉｃ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ３Ｄ Ｓｈａｐｅ Ｄｅｓｃｒｉｐｔｏｒｓ（三次元形状記述子の回転不変球面調和関数表現）」Ｋａｚｈｄａｎ Ｍ．，Ｆｕｎｋｈｏｕｓｅｒ Ｔ．，Ｒｕｓｉｎｋｉｅｗｅｃｚ Ｓ著、Ｐｒｏｃ．１ｓｔ Ｅｕｒｏｇｒａｐｈｉｃｓ Ｓｙｍｐｓｉｕｍ ｏｎ Ｇｅｏｍｅｔｒｙ Ｐｒｏｃｅｓｓｉｎｇ（ＳＧＰ），Ａａｃｈｅｎ，２００３，ｐｐ．１６７−１７５には、形状の類似性を評価する際の問題点についての様々な公知の取り組みの概説が含まれている。
【０００６】
本発明の目的は、幾何学特徴データを確定する先行技術の方法の正確さ、および／又は効力、および／又は性能、および／又は有用性を改善する技術を提供することである。好まれる実施の形態では、特徴データが次の類似探索か類似分類の正確さを改善するプロパティー（ｐｒｏｐｅｒｔｙ）を持っており、それにより全体的な正確さの改善を達成したり、および／又は要求される正確さの水準に達する為に必要な計算量と記憶量を削減することができる。
【０００７】
本発明によると、上記の目的は、独立請求項記載の装置およびコンピュータプログラムによって、少なくとも部分的には達成される。従属請求項は本発明の好まれる実施の形態を定義している。
【０００８】
発明の第一の態様は、少なくとも二つのセル（ｃｅｌｌ）が少なくとも部分的に重なり合うように複数のセルを定義する分割スキーム（ｐａｒｔｉｔｉｏｎｉｎｇ ｓｃｈｅｍｅ）を使うアイディアに基づいている。そのような分割スキームはまた、本願では「重複する分割スキーム」と呼ぶ。この重複性そのものにも計算量の追加が必要になる。しかしながら実験の結果によると、この影響を補うに余るほど、入手した特徴データの正確さが向上するので、先行技術で必要なものに比べより粗い分割スキームを使うことが可能になる、という驚くべきことが発見された。全体的に見て、総計算量と総記憶量は一見無駄と思われる重複する分割スキームによって大きく削減される。
【０００９】
本発明の第二の態様によると、複数のセルを定義する分割スキームが使われており、これらのセルの少なくともいくつかの境界は物体の位置する空間内にある複数の区域を区切り、この複数の区域に含まれる物体のそれぞれの部分が、所定の測定基準に関してはほとんど等しくなる。本願では、そのような区域にグループ分けすることができるセルを定義する分割スキームを「比例分割スキーム」と呼ぶ。先と同様に、実験によると、比例分割スキームを使うことにより全体的な正確さの向上が達成され、および／又は従来必要とされるよりも粗い分割スキームを選ぶことが可能になる。
【００１０】
本発明の好ましい実施例では、分割スキームが重なりあう多数のセルを定義することができる。例えば、分割スキームにより定義された全てのセルの少なくとも５０％又は少なくとも９０％は他のセルと部分的もしくは全体的に重なり合うこともある。実施例によっては、複数のセルが、物体が存在する空間内の同一の区域を異なって分割するセルの二つ以上のグループを含んでいるものもある。言い換えると、これらのセルの各グループ内にある全てのセルの各ユニオンは同一空間にあり、一つのグループ内の各セルは、他の各グループの少なくとも一つのセルと少なくとも部分的に重なり合っている。
【００１１】
本発明の実施例によっては、分割スキームによって定義されるセルはネストされたセル（ｎｅｓｔｅｄ ｃｅｌｌｓ）のグループから成る。このグループでは、重なり合っているセルはそれぞれ全体的に重なり合っている。分割スキームは、このネストされたセルのグループに属さない追加のセルを定義してもしなくても良い。ネストされたセルのグループのセルは、好ましくは、ネストされたセルのグループのセル内に含まれる物体の各部分のｋ次元の体積が、ほぼ規則的に、又はきちんと規則的に増加するシーケンスを形成する。言い換えると、ネストされたセルのグループ内の第一のセルは物体の一体積ユニットを含み、第二のセルはおおよそもう一体積ユニットを含み、第三のセルは更にもう一体積ユニットを含むということである。他の実施例では、セルの全体的な重なり合い、つまりセルのネスティングを指定せず、部分的な重なり合いのみを指定する分割スキームを用いる。
【００１２】
重複するか比例する分割スキームの使用によってすでに相当な効果があるが、重複しかつ比例する分割スキームの使用が特に好まれる。実験によると、この組み合わせにより、重複する分割スキームのみの利益と比例分割スキームのみの利益を単に合計した利益を超える、予期せぬ相乗的な利益が達成される。実施例によっては、重複する態様および比例する態様は、少なくとも比例区域の一つが、少なくとも二つの部分的に重なり合うセル又は完全に重なり合うセルを含むように組み合わされる。
【００１３】
実施例によっては、比例区域は互いにばらばらであり、他の実施例によっては、これらの区域は少なくとも部分的に重なり合っている。区域は、必ずしも物体が位置する全空間に及ぶ必要はない。実施例によっては、どの比例区域の部分でもない追加のセルがあり、他の実施例によっては、分割スキームよって定義される全てのセルが少なくとも区域の一つに属する。
【００１４】
測定基準によって区域内に含まれる物体の各部分がほぼ等しいことが必要とされるが、この測定基準は物体の各部分のｋ次元の体積であることが好ましい。三次元の場合、体積は各物体部分の「通常の」空間体積であり、二次元の体積は、各物体部分によって占められる実際の面積である。他の実施例では、例えば三次元の物体の部分の表面積といった他の基準が使用される。
【００１５】
本発明の第二の態様によると、比例区域は分割スキームによって定義されるセルの境界によって区切られる。好ましい実施例では、各区域が少なくとも二つのセルのユニオンおよび／又は差異および／又は交差部分に相当するか、一つのセルにぴったり相当することを意味する。好ましくは、各区域は単一のセル、セルのグループ、あるいは第一のセル又はセルのグループから第二のセル又はセルのグループを引いた差異に相当する。
【００１６】
一般的に、セルおよび／又は区域はどんな適切な形状でもよいが、標準的な形状がたいていは効果的である。セルおよび／又は区域の少なくともいくつか、あるいはセルおよび／又は区域の全てが以下の形状の内の一つであることが好ましい。物体が位置する空間において、ｋ次元の球体、ｋ次元のシェル形、ｋ次元の球体のセクタ、ｋ次元のシェル形のセクタである。
【００１７】
本発明は、分割スキームのセル内に含まれる物体のそれぞれの部分の少なくとも一つのプロパティーに基づいて、物体の特徴データを確定するステップから成る。このステップを遂行するいくつかの方法自体は周知であり、本発明の実施に関連しても使用してもよい。例えば、複数のセルの各セル内に含まれる物体のそれぞれの部分のｋ次元の体積に基づいて、および／又は複数のセルの各セル内に含まれる物体のそれぞれの部分のｋ主軸を定義するデータに基づいて、物体の特徴データを確定してもよい。
【００１８】
実施例によっては、本発明によって得られる特徴データは特徴ベクトルである。この特徴データは様々な方法で使用できるが、それ自体も周知である。例えば、特徴データは複数の物体の類似探索や類似分類を実行するために使用される。
【００１９】
本発明のコンピュータープログラム製品は、本発明の方法を実行するプログラムのインストラクションから成る。コンピュータープログラム製品は、例えば半導体メモリ、コンピューターディスク、ＣＤ−ＲＯＭといった有形のデータキャリアである。しかしながら、コンピュータープログラム製品は、例えばコンピューターネットワーク内で送信された信号といった無形のデータキャリアでもよい。本発明の装置は、本発明の方法を実行するようにプログラムされた一般的なパーソナルコンピューター、ワークステーション、メインフレームコンピューター、コンピューターネットワークである。コンピューター製品、および／又は装置の好ましい実施例は、上述した特徴、および／又は従属の方法の請求項の特徴に対応する特徴から成る。
【図面の簡単な説明】
【００２０】
【図１】物体と、それに対応する最小の境界となる球面の一例である。
【図２】先行技術によるばらばらで等距離にある分割スキームの一例である。
【図３】本発明の第一の実施例による、ばらばらな比例分割スキームの一例である。
【図４】本発明の第二の実施例による、重複し、等距離にある分割スキームの第一の例である。
【図５】本発明の第三の実施例による、重複し、等距離にある分割スキームの第二の例である。
【図６】本発明の第四の実施例による、重複する比例分割スキームの第一の例である。
【図７】本発明の第五の実施例による、重複する比例分割スキームの第二の例である。
【図８】図２の先行技術の分割スキームと図６の分割スキームとを比較し、精度と再現率の関係をプロットしたものである。
【図９】たんぱく質データについて、図２の先行技術による分割スキームを使用する分類にかかる総ランタイム（ｔｏｔａｌ ｒｕｎｔｉｍｅ）と、図６の分割スキームを使用する分類にかかる総ランタイムとを比較した図である。
【発明を実施するための形態】
【００２１】
【００２２】
【００２３】
【００２４】
【００２５】
【００２６】
【００２７】
図２は、先行技術で公知の分割スキームを三つのセル（ｄ＝３）で示したものである。この分割スキームは、（１）全てのセルｐｉはばらばらである、（２）セルｐｉの境界は等距離である、というプロパティを有する。第一のセルｐ１はｋ次元の球体（すなわち、ｋ＝２の場合は円、ｋ＝３の場合は空間にある球体）の形状であり、第二および第三のセルｐ２、ｐ３はそれぞれ最小の境界となる球体ｂｓ（ｏ）の中心ｃの周りにｋ次元のシェルの形状を有する。図２の分割スキームはばらばらで等距離であることからＤＥと呼ぶ。
【００２８】
図３は、本発明の第一のサンプルの実施例による分割スキームを三つのセル（ｄ＝３）で図示したものである。一般的に、本発明の全ての分割スキームは特に異種の物体のデーターベースに適している。図３の分割スキームはいわゆる比例分割スキームである。ここに記述するサンプルの実施例の比例分割スキームでは、セルの境界やこれらの境界のいくつかは、各区域内に占める物体の体積が少なくともほぼ一定であるように、空間内において多数の区域を区切る。したがって、セルおよび区域の境界は各物体の個々の形状に適合する。
【００２９】
【００３０】
図３の比例分割スキームは、ばらばらで比例することからＤＰと呼ばれる。図２の先行技術による分割スキームを形状ヒストグラムと称するならば、図３のアプローチは形状分位と呼ぶことができ、分位は分割スキームによって定義される分割セルの数ｄによって確定される。
【００３１】
【００３２】
図４のサンプルの実施例では、セルｐiはネストされたセルの単一のグループｇｎを形成する。言い換えると、最小のセルｐ１はセルｐ２に完全に含まれ、順を追ってセルｐ２は最大のセルｐ３に完全に含まれる。それゆえ、セルｐ１からｐ３は「内に含まれている」関係について、完全な順序シーケンスを構成している。更に、セルｐｉの境界は等距離である。
【００３３】
図５は、重複し等距離にある分割スキームの更なるサンプルの実施例を１７個のセル（ｄ＝１７）で示したものである。このスキームは、図２のセルｐ２とセルｐ３を更に分けることによって、図２の先行技術の分割スキームから得られる。より具体的には、図２の第二のセルｐ２は、内セルｐ２からｐ５の第一のグループｇｉ１と、内セルｐ６からｐ９の第二のグループｇｉ２とに更に分けられている。これらのグループｇｉ１、ｇｉ２のそれぞれに含まれるセルは、それぞれのグループｇｉ１、ｇｉ２内においてばらばらである。しかしながら、グループｇｉ１、ｇｉ２は、一方のグループある各セルが他方のグループの二つのセルに重なり合うように、互いに対してシフトしている。同様に、図２の第三のセルｐ３は外セルｐ１０からｐ１３の第一のグループｇｏ１と、外セルｐ１４からｐ１７の第二のグループｇｏ２とに更に分けられている。セルｐ２からｐ１７のそれぞれは、最小の境界となる球体ｂｓ（ｏ）内のｋ次元のシェルのセクタの形状をしている。
【００３４】
図４および図５の重複し等距離にある分割スキームの例は、それぞれＲＥ１（ｏ）、ＲＥ２（ｏ）と呼ぶ。
【００３５】
実験によると、比例する分割と重複する分割とが組み合わさっている場合、特に利益が大きい。重複と比例を組み合わせた分割スキームはＲＰと呼ぶ。図６および図７は、ＲＰ分割のサンプルの実施例を二つ示している。
【００３６】
【００３７】
更に注目すべき点として、図６の例では、セルｐ１からセルｐ３にある物体ｏの各部分の体積は、規則的に、すなわち各セルとも物体ｏの総体積の１／ｄづつ増加する。したがって、三つのセルの本例では、第一のセルｐ１は物体ｏの総体積の約１／３、第二のセルｐ２は約２／３、第三のセルｐ３は総体積を含む。
【００３８】
【００３９】
【００４０】
上述したサンプルの実施例では、所与の物体ｏの特徴ベクトルΦ（ｏ）は、対応する分割スキームによって定義される全てのセルｐに、集約αを当てはめることによって得られる全ての結果を、単に連結したものである。他の実施例では、更なる標準化、又は他の追加の処理ステップを実行してもよい。
【００４１】
全体として見ると、結果としてもたらされた類似性の指標を使用して、物体の幾何学的特徴によって物体の大きな集まりを分類したり、類似した物体のデータベース探索を行ったり、物体の幾何学的類似性を評価しなければならない他の作業を行ったりすることができる。
【００４２】
本発明の長所を評価するために、ここに提案した分割のアプローチの効力を先行技術による最も優れたテクニックの一つと比較する。先行技術による最も優れたテクニックとは、先に引用した研究論文「三次元形状記述子の回転不変球面調和関数表現」で提案しているような、球面の調和値の集約関数を用いたＤＥ分割に基づいている。非常に有望な結果が得られている。例えば、図８は、たんぱく質データベースに関する先行技術のＤＥ分割および本ＲＰ１分割の結果を示したものである。再現率５０％では、ＤＥに基づく方法では精度が２６％であるのに対して、ＲＰ１に基づく方法では４２％の精度を示している。再現率８０％では、ＲＰ１はＤＥよりもほぼ二倍の精度をもたらす。ＣＡＤおよびウェブデータに関しても同様の結果が得られている。
【００４３】
図９は、上記と同じ構成で得られる性能の結果を示している。ＲＰ１がＤＥよりも約十倍早く実行されることが明らかである。したがって、ＲＰ１はＤＥよりも非常に高い効力をもたらすだけではなく、ランタイムで見たコストが格段に低くなる。ＤＥの性能が遅いのは、よい結果を出すために、はるかにきめの細かい分割スキームを必要とするという事実のためである。したがって、作り出されたＤＥの特徴ベクトルは、距離関数によって評価すると、はるかにより長くて高価である。
【００４４】
類似性に基づいた探索および／又は分類の方法の正確さおよび効力を改善するために、本発明が利用できるということが明らかである。上述したサンプルの実施例の記述に含まれる詳細は、本発明の範囲を制限するように解釈されるべきではなく、むしろ本発明の好まれる実施例の例示として解釈されるべきである。他の多くのバリエーションが可能であり、当業者には容易に明らかである。それゆえ、本発明の範囲は、説明した実施例によって確定されるのではなく、添付の請求項およびそれらと法的に等価であるものによって確定される。
【００４５】
更なる特徴や、本発明の目的および効果は、以下に詳細に記述するいくつかのサンプルの実施例から明らかになる。図を参照とされたい。
【特許請求の範囲】
【請求項１】
物体（ｏ）の形状に関する情報を表す特徴データを確定するためのコンピュータを備えた装置であって、該物体（ｏ）はｋ次元の空間に位置し、
前記コンピュータが
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＲＥ、ＲＰ）を確定し、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するものであり、
前記分割スキーム（ＲＥ、ＲＰ）の確定では、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように分割スキーム（ＲＥ、ＲＰ）を確定する、
ことを特徴とする装置。
【請求項２】
該複数のセル（ｐ）が、セルの第一のグループ（ｇｉ１；ｇｏ１）にある該セルのユニオンがセルの第二のグループ（ｇｉ２；ｇｏ２）の該セルのユニオンと同一空間にあるようなセルの該第一のグループおよびセルの該第二のグループ（ｇｉ１、ｇｉ２；ｇｏ１、ｇｏ２）を少なくとも備え、ここで、
セルの該第一のグループ（ｇｉ１；ｇｏ１）の各セルがセルの該第二のグループ（ｇｉ２；ｇｏ２）の対応する少なくとも一つのセルに少なくとも部分的に重なり合うこと、を特徴とする請求項１の装置。
【請求項３】
該複数のセル（ｐ）が少なくとも一つのネストされたセルのグループ（ｇｎ）を備え、ネストされたセルの該グループ（ｇｎ）の全てのセルが互いにネストしていること、を特徴とする請求項１又は請求項２の装置。
【請求項４】
ネストされたセルの該グループ（ｇｎ）の該セルが、ネストされたセルの該グループ（ｇｎ）の該セルに含まれる該物体（ｏ）の該対応する部分のｋ次元の体積が少なくとも規則的に増加するようなシーケンスを形成すること、を特徴とする請求項３の装置。
【請求項５】
物体（ｏ）の形状に関する情報を表す特徴データを確定するためのコンピュータを備えた装置であって、該物体（ｏ）はｋ次元の空間に位置し、
前記コンピュータは
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＤＰ、ＲＰ）を確定し、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するものであり、
前記分割スキーム（ＲＥ、ＲＰ）の確定では、該分割スキーム（ＤＰ、ＲＰ）によって定義される該セル（ｐ）の境界の少なくともいくつかを該物体（ｏ）の個々の形状に当てはめ、複数の区域（ｒ）に含まれる該物体（ｏ）の対応する部分が所定の測定基準に関して互いに等しいように該物体（ｏ）が位置する空間内の該複数の区域（ｒ）を区切るように、該分割スキーム（ＤＰ、ＲＰ）を確定する
ことを特徴とする装置。
【請求項６】
該複数の区域（ｒ）の少なくとも一つの区域（ｒ）が、少なくとも部分的に互いに重なり合う、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）を含むこと、を特徴とする請求項５の装置。
【請求項７】
該複数の区域（ｒ）の全ての区域（ｒ）が互いに対してばらばらであること、を特徴とする請求項５又は請求項６の装置。
【請求項８】
該複数の区域（ｒ）の各区域（ｒ）の該測定基準が、該区域（ｒ）に含まれる該物体（ｏ）の対応する部分のｋ次元の体積であること、を特徴とする請求項５乃至請求項７のいずれか一つの装置。
【請求項９】
該複数の区域（ｒ）の各区域（ｒ）が、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）のユニオンおよび／又は差異および／又は交差部分に相当するか、該複数のセル（ｐ）の一つのセル（ｐ）にぴったりと相当すること、を特徴とする請求項５乃至請求項８のいずれか一つの装置。
【請求項１０】
該複数の区域（ｒ）の少なくともいくつかの区域（ｒ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項５乃至請求項９のいずれか一つの装置。
【請求項１１】
該分割スキーム（ＤＰ，ＲＥ，ＲＰ）によって定義される少なくともいくつかの該セル（ｐ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項１乃至請求項１０のいずれか一つの装置。
【請求項１２】
該複数のセル（ｐ）の各セル（ｐ）内に含まれる該物体（ｏ）の各対応する部分のｋ次元の体積に基づいて、および／又は該複数のセル（ｐ）の該各セル（ｐ）に含まれる該物体（ｏ）の各対応する部分のｋ主軸を定義するデータに基づいて、該物体（ｏ）の該特徴データを確定すること、を特徴とする請求項１乃至請求項１１のいずれか一つの装置。
【請求項１３】
第一の物体と、第二の物体のセットとの間の類似探索を実行するため、該第一の物体の特徴データおよび該第二の物体のセットのそれぞれの特徴データを確定し、該確定した特徴データの比較に基づいて該類似探索を実行する、ことを特徴とする請求項１乃至請求項１２のいずれか一つの装置。
【請求項１４】
物体のセットの類似分類を実行するため、物体の該セットの各物体の特徴データを確定し、該確定した特徴データの分類に基づいた対応する類似性に従って、物体の該セットの該物体をグループ化する、ことを特徴とする請求項１乃至請求項１２のいずれか一つの装置。
【請求項１５】
請求項１乃至請求項１４のいずれか一つの装置が、たんぱく質、CAD又はウェブデータの類似探索および／または類似分類のために用いられる、ことを特徴とする装置。
【請求項１６】
コンピュータに、物体（ｏ）の形状に関する情報を表す特徴データを確定する処理を実行させるためのプログラムであって、該物体（ｏ）はｋ次元の空間に位置し、
前記プログラムは
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＲＥ、ＲＰ）を確定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するステップと、
を前記コンピュータに実行させるものであり、
前記分割スキーム（ＲＥ、ＲＰ）を確定するステップでは、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように分割スキーム（ＲＥ、ＲＰ）を確定する、
ことを特徴とするプログラム。
【請求項１７】
該複数のセル（ｐ）が、セルの第一のグループ（ｇｉ１；ｇｏ１）にある該セルのユニオンがセルの第二のグループ（ｇｉ２；ｇｏ２）の該セルのユニオンと同一空間にあるようなセルの該第一のグループおよびセルの該第二のグループ（ｇｉ１、ｇｉ２；ｇｏ１、ｇｏ２）を少なくとも備え、ここで、
セルの該第一のグループ（ｇｉ１；ｇｏ１）の各セルがセルの該第二のグループ（ｇｉ２；ｇｏ２）の対応する少なくとも一つのセルに少なくとも部分的に重なり合うこと、を特徴とする請求項１６のプログラム。
【請求項１８】
該複数のセル（ｐ）が少なくとも一つのネストされたセルのグループ（ｇｎ）を備え、ネストされたセルの該グループ（ｇｎ）の全てのセルが互いにネストしていること、を特徴とする請求項１６又は請求項１７のプログラム。
【請求項１９】
ネストされたセルの該グループ（ｇｎ）の該セルが、ネストされたセルの該グループ（ｇｎ）の該セルに含まれる該物体（ｏ）の該対応する部分のｋ次元の体積が少なくとも規則的に増加するようなシーケンスを形成すること、を特徴とする請求項１８のプログラム。
【請求項２０】
コンピュータに、物体（ｏ）の形状に関する情報を表す特徴データを確定する処理を実行させるためのプログラムであって、該物体（ｏ）はｋ次元の空間に位置し、
前記プログラムは
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＤＰ、ＲＰ）を確定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するステップと、
を前記コンピュータに実行させるものであり、
前記分割スキーム（ＲＥ、ＲＰ）を確定するステップでは、該分割スキーム（ＤＰ、ＲＰ）によって定義される該セル（ｐ）の境界の少なくともいくつかを該物体（ｏ）の個々の形状に当てはめ、複数の区域（ｒ）に含まれる該物体（ｏ）の対応する部分が所定の測定基準に関して互いに等しいように該物体（ｏ）が位置する空間内の該複数の区域（ｒ）を区切るように、該分割スキーム（ＤＰ、ＲＰ）を確定させる、
ことを特徴とするプログラム。
【請求項２１】
該複数の区域（ｒ）の少なくとも一つの区域（ｒ）が、少なくとも部分的に互いに重なり合う、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）を含むこと、を特徴とする請求項２０のプログラム。
【請求項２２】
該複数の区域（ｒ）の全ての区域（ｒ）が互いに対してばらばらであること、を特徴とする請求項２０又は請求項２１のプログラム。
【請求項２３】
該複数の区域（ｒ）の各区域（ｒ）の該測定基準が、該区域（ｒ）に含まれる該物体（ｏ）の対応する部分のｋ次元の体積であること、を特徴とする請求項２０乃至請求項２２のいずれか一つのプログラム。
【請求項２４】
該複数の区域（ｒ）の各区域（ｒ）が、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）のユニオンおよび／又は差異および／又は交差部分に相当するか、該複数のセル（ｐ）の一つのセル（ｐ）にぴったりと相当すること、を特徴とする請求項２０乃至請求項２３のいずれか一つのプログラム。
【請求項２５】
該複数の区域（ｒ）の少なくともいくつかの区域（ｒ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項２０乃至請求項２４いずれか一つのプログラム。
【請求項２６】
該分割スキーム（ＤＰ，ＲＥ，ＲＰ）によって定義される少なくともいくつかの該セル（ｐ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項１６乃至請求項２５のいずれか一つのプログラム。
【請求項２７】
該複数のセル（ｐ）の各セル（ｐ）内に含まれる該物体（ｏ）の各対応する部分のｋ次元の体積に基づいて、および／又は該複数のセル（ｐ）の該各セル（ｐ）に含まれる該物体（ｏ）の各対応する部分のｋ主軸を定義するデータに基づいて、該物体（ｏ）の該特徴データが確定されること、を特徴とする請求項１６乃至請求項２６のいずれか一つのプログラム。
【請求項２８】
前記コンピュータに、第一の物体と、第二の物体のセットとの間の類似探索を実行させるため、該第一の物体の特徴データおよび該第二の物体のセットのそれぞれの特徴データを確定するステップと、該確定した特徴データの比較に基づいて該類似探索を実行するステップと、をさらに実行させる、ことを特徴とする請求項１６乃至請求項２７のいずれか一つのプログラム。
【請求項２９】
前記コンピュータに、物体のセットの類似分類を実行させるため、物体の該セットの各物体の特徴データを確定するステップと、該確定した特徴データの分類に基づいた対応する類似性に従って、物体の該セットの該物体をグループ化するステップと、をさらに実行させることを特徴とする請求項１６乃至請求項２７のいずれか一つのプログラム。
【請求項３０】
請求項１６乃至請求項２９のいずれか一つのプログラムが、たんぱく質、CAD又はウェブデータの類似探索および／または類似分類のために用いられる、ことを特徴とするプログラム。
【請求項１】
物体（ｏ）の形状に関する情報を表す特徴データを確定するためのコンピュータを備えた装置であって、該物体（ｏ）はｋ次元の空間に位置し、
前記コンピュータが
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＲＥ、ＲＰ）を確定し、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するものであり、
前記分割スキーム（ＲＥ、ＲＰ）の確定では、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように分割スキーム（ＲＥ、ＲＰ）を確定する、
ことを特徴とする装置。
【請求項２】
該複数のセル（ｐ）が、セルの第一のグループ（ｇｉ１；ｇｏ１）にある該セルのユニオンがセルの第二のグループ（ｇｉ２；ｇｏ２）の該セルのユニオンと同一空間にあるようなセルの該第一のグループおよびセルの該第二のグループ（ｇｉ１、ｇｉ２；ｇｏ１、ｇｏ２）を少なくとも備え、ここで、
セルの該第一のグループ（ｇｉ１；ｇｏ１）の各セルがセルの該第二のグループ（ｇｉ２；ｇｏ２）の対応する少なくとも一つのセルに少なくとも部分的に重なり合うこと、を特徴とする請求項１の装置。
【請求項３】
該複数のセル（ｐ）が少なくとも一つのネストされたセルのグループ（ｇｎ）を備え、ネストされたセルの該グループ（ｇｎ）の全てのセルが互いにネストしていること、を特徴とする請求項１又は請求項２の装置。
【請求項４】
ネストされたセルの該グループ（ｇｎ）の該セルが、ネストされたセルの該グループ（ｇｎ）の該セルに含まれる該物体（ｏ）の該対応する部分のｋ次元の体積が少なくとも規則的に増加するようなシーケンスを形成すること、を特徴とする請求項３の装置。
【請求項５】
物体（ｏ）の形状に関する情報を表す特徴データを確定するためのコンピュータを備えた装置であって、該物体（ｏ）はｋ次元の空間に位置し、
前記コンピュータは
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＤＰ、ＲＰ）を確定し、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するものであり、
前記分割スキーム（ＲＥ、ＲＰ）の確定では、該分割スキーム（ＤＰ、ＲＰ）によって定義される該セル（ｐ）の境界の少なくともいくつかを該物体（ｏ）の個々の形状に当てはめ、複数の区域（ｒ）に含まれる該物体（ｏ）の対応する部分が所定の測定基準に関して互いに等しいように該物体（ｏ）が位置する空間内の該複数の区域（ｒ）を区切るように、該分割スキーム（ＤＰ、ＲＰ）を確定する
ことを特徴とする装置。
【請求項６】
該複数の区域（ｒ）の少なくとも一つの区域（ｒ）が、少なくとも部分的に互いに重なり合う、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）を含むこと、を特徴とする請求項５の装置。
【請求項７】
該複数の区域（ｒ）の全ての区域（ｒ）が互いに対してばらばらであること、を特徴とする請求項５又は請求項６の装置。
【請求項８】
該複数の区域（ｒ）の各区域（ｒ）の該測定基準が、該区域（ｒ）に含まれる該物体（ｏ）の対応する部分のｋ次元の体積であること、を特徴とする請求項５乃至請求項７のいずれか一つの装置。
【請求項９】
該複数の区域（ｒ）の各区域（ｒ）が、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）のユニオンおよび／又は差異および／又は交差部分に相当するか、該複数のセル（ｐ）の一つのセル（ｐ）にぴったりと相当すること、を特徴とする請求項５乃至請求項８のいずれか一つの装置。
【請求項１０】
該複数の区域（ｒ）の少なくともいくつかの区域（ｒ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項５乃至請求項９のいずれか一つの装置。
【請求項１１】
該分割スキーム（ＤＰ，ＲＥ，ＲＰ）によって定義される少なくともいくつかの該セル（ｐ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項１乃至請求項１０のいずれか一つの装置。
【請求項１２】
該複数のセル（ｐ）の各セル（ｐ）内に含まれる該物体（ｏ）の各対応する部分のｋ次元の体積に基づいて、および／又は該複数のセル（ｐ）の該各セル（ｐ）に含まれる該物体（ｏ）の各対応する部分のｋ主軸を定義するデータに基づいて、該物体（ｏ）の該特徴データを確定すること、を特徴とする請求項１乃至請求項１１のいずれか一つの装置。
【請求項１３】
第一の物体と、第二の物体のセットとの間の類似探索を実行するため、該第一の物体の特徴データおよび該第二の物体のセットのそれぞれの特徴データを確定し、該確定した特徴データの比較に基づいて該類似探索を実行する、ことを特徴とする請求項１乃至請求項１２のいずれか一つの装置。
【請求項１４】
物体のセットの類似分類を実行するため、物体の該セットの各物体の特徴データを確定し、該確定した特徴データの分類に基づいた対応する類似性に従って、物体の該セットの該物体をグループ化する、ことを特徴とする請求項１乃至請求項１２のいずれか一つの装置。
【請求項１５】
請求項１乃至請求項１４のいずれか一つの装置が、たんぱく質、CAD又はウェブデータの類似探索および／または類似分類のために用いられる、ことを特徴とする装置。
【請求項１６】
コンピュータに、物体（ｏ）の形状に関する情報を表す特徴データを確定する処理を実行させるためのプログラムであって、該物体（ｏ）はｋ次元の空間に位置し、
前記プログラムは
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＲＥ、ＲＰ）を確定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するステップと、
を前記コンピュータに実行させるものであり、
前記分割スキーム（ＲＥ、ＲＰ）を確定するステップでは、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように分割スキーム（ＲＥ、ＲＰ）を確定する、
ことを特徴とするプログラム。
【請求項１７】
該複数のセル（ｐ）が、セルの第一のグループ（ｇｉ１；ｇｏ１）にある該セルのユニオンがセルの第二のグループ（ｇｉ２；ｇｏ２）の該セルのユニオンと同一空間にあるようなセルの該第一のグループおよびセルの該第二のグループ（ｇｉ１、ｇｉ２；ｇｏ１、ｇｏ２）を少なくとも備え、ここで、
セルの該第一のグループ（ｇｉ１；ｇｏ１）の各セルがセルの該第二のグループ（ｇｉ２；ｇｏ２）の対応する少なくとも一つのセルに少なくとも部分的に重なり合うこと、を特徴とする請求項１６のプログラム。
【請求項１８】
該複数のセル（ｐ）が少なくとも一つのネストされたセルのグループ（ｇｎ）を備え、ネストされたセルの該グループ（ｇｎ）の全てのセルが互いにネストしていること、を特徴とする請求項１６又は請求項１７のプログラム。
【請求項１９】
ネストされたセルの該グループ（ｇｎ）の該セルが、ネストされたセルの該グループ（ｇｎ）の該セルに含まれる該物体（ｏ）の該対応する部分のｋ次元の体積が少なくとも規則的に増加するようなシーケンスを形成すること、を特徴とする請求項１８のプログラム。
【請求項２０】
コンピュータに、物体（ｏ）の形状に関する情報を表す特徴データを確定する処理を実行させるためのプログラムであって、該物体（ｏ）はｋ次元の空間に位置し、
前記プログラムは
セル（ｐ）のうちの少なくともいくつかがそれぞれ該物体（ｏ）の対応する部分を含むように、該物体（ｏ）が位置する空間内の複数の該セル（ｐ）を定義する分割スキーム（ＤＰ、ＲＰ）を確定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該対応する部分の少なくとも一つのプロパティに基づいて該物体（ｏ）の該特徴データを確定するステップと、
を前記コンピュータに実行させるものであり、
前記分割スキーム（ＲＥ、ＲＰ）を確定するステップでは、該分割スキーム（ＤＰ、ＲＰ）によって定義される該セル（ｐ）の境界の少なくともいくつかを該物体（ｏ）の個々の形状に当てはめ、複数の区域（ｒ）に含まれる該物体（ｏ）の対応する部分が所定の測定基準に関して互いに等しいように該物体（ｏ）が位置する空間内の該複数の区域（ｒ）を区切るように、該分割スキーム（ＤＰ、ＲＰ）を確定させる、
ことを特徴とするプログラム。
【請求項２１】
該複数の区域（ｒ）の少なくとも一つの区域（ｒ）が、少なくとも部分的に互いに重なり合う、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）を含むこと、を特徴とする請求項２０のプログラム。
【請求項２２】
該複数の区域（ｒ）の全ての区域（ｒ）が互いに対してばらばらであること、を特徴とする請求項２０又は請求項２１のプログラム。
【請求項２３】
該複数の区域（ｒ）の各区域（ｒ）の該測定基準が、該区域（ｒ）に含まれる該物体（ｏ）の対応する部分のｋ次元の体積であること、を特徴とする請求項２０乃至請求項２２のいずれか一つのプログラム。
【請求項２４】
該複数の区域（ｒ）の各区域（ｒ）が、該複数のセル（ｐ）の少なくとも二つのセル（ｐ）のユニオンおよび／又は差異および／又は交差部分に相当するか、該複数のセル（ｐ）の一つのセル（ｐ）にぴったりと相当すること、を特徴とする請求項２０乃至請求項２３のいずれか一つのプログラム。
【請求項２５】
該複数の区域（ｒ）の少なくともいくつかの区域（ｒ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項２０乃至請求項２４いずれか一つのプログラム。
【請求項２６】
該分割スキーム（ＤＰ，ＲＥ，ＲＰ）によって定義される少なくともいくつかの該セル（ｐ）が、該物体（ｏ）が位置する空間において、ｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項１６乃至請求項２５のいずれか一つのプログラム。
【請求項２７】
該複数のセル（ｐ）の各セル（ｐ）内に含まれる該物体（ｏ）の各対応する部分のｋ次元の体積に基づいて、および／又は該複数のセル（ｐ）の該各セル（ｐ）に含まれる該物体（ｏ）の各対応する部分のｋ主軸を定義するデータに基づいて、該物体（ｏ）の該特徴データが確定されること、を特徴とする請求項１６乃至請求項２６のいずれか一つのプログラム。
【請求項２８】
前記コンピュータに、第一の物体と、第二の物体のセットとの間の類似探索を実行させるため、該第一の物体の特徴データおよび該第二の物体のセットのそれぞれの特徴データを確定するステップと、該確定した特徴データの比較に基づいて該類似探索を実行するステップと、をさらに実行させる、ことを特徴とする請求項１６乃至請求項２７のいずれか一つのプログラム。
【請求項２９】
前記コンピュータに、物体のセットの類似分類を実行させるため、物体の該セットの各物体の特徴データを確定するステップと、該確定した特徴データの分類に基づいた対応する類似性に従って、物体の該セットの該物体をグループ化するステップと、をさらに実行させることを特徴とする請求項１６乃至請求項２７のいずれか一つのプログラム。
【請求項３０】
請求項１６乃至請求項２９のいずれか一つのプログラムが、たんぱく質、CAD又はウェブデータの類似探索および／または類似分類のために用いられる、ことを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１１−１８７０６６（Ｐ２０１１−１８７０６６Ａ）
【公開日】平成２３年９月２２日（２０１１．９．２２）
【国際特許分類】
【出願番号】特願２０１１−７１００８（Ｐ２０１１−７１００８）
【出願日】平成２３年３月２８日（２０１１．３．２８）
【分割の表示】特願２００７−５０２２４８（Ｐ２００７−５０２２４８）の分割
【原出願日】平成１７年３月４日（２００５．３．４）
【出願人】（５０４４３８２８８）シーメンス、プラダクツ、ライフサイクル、マニジマント、ソフトウエア、インク (13)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｐｒｏｄｕｃｔ Ｌｉｆｅｃｙｃｌｅ Ｍａｎａｇｅｍｅｎｔ Ｓｏｆｔｗａｒｅ Ｉｎｃ．
【住所又は居所原語表記】５８００ Ｇｒａｎｉｔｅ Ｐａｒｋｗａｙ， Ｓｕｉｔｅ ６００ Ｐｌａｎｏ， Ｔｅｘａｓ ７５０２４， ＵＳＡ
【Ｆターム（参考）】
【公開日】平成２３年９月２２日（２０１１．９．２２）
【国際特許分類】
【出願日】平成２３年３月２８日（２０１１．３．２８）
【分割の表示】特願２００７−５０２２４８（Ｐ２００７−５０２２４８）の分割
【原出願日】平成１７年３月４日（２００５．３．４）
【出願人】（５０４４３８２８８）シーメンス、プラダクツ、ライフサイクル、マニジマント、ソフトウエア、インク (13)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｐｒｏｄｕｃｔ Ｌｉｆｅｃｙｃｌｅ Ｍａｎａｇｅｍｅｎｔ Ｓｏｆｔｗａｒｅ Ｉｎｃ．
【住所又は居所原語表記】５８００ Ｇｒａｎｉｔｅ Ｐａｒｋｗａｙ， Ｓｕｉｔｅ ６００ Ｐｌａｎｏ， Ｔｅｘａｓ ７５０２４， ＵＳＡ
【Ｆターム（参考）】
[ Back to top ]