【誤訳訂正書】
【提出日】平成24年11月28日(2012.11.28)
【誤訳訂正１】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【発明の詳細な説明】
【発明の名称】幾何学的特徴データを決定すること、および使用すること
【技術分野】
【０００１】
本発明は、一般的に、異なった形状と異なった幾何学的特徴を有する物体のコンピューターベース処理（ｃｏｍｐｕｔｅｒ−ｂａｓｅｄ  ｐｒｏｃｅｓｓｉｎｇ）を行う技術分野に関する。更に詳しくは、本発明は物体形状に関する情報を示す特徴データを決定し使用する分野に関する。本発明が教示することは、たんぱく質、ＣＡＤ、ウェブデータの類似性探索や類似性分類などの様々なアプリケーションに用いることができるが、アプリケーションはこれらに限られてはいない。
【０００２】
過去１０年間、類似性探索のための効率的かつ効果的なサポートを必須条件としたデータベースアプリケーションが益々多数出現している。マルチメディア、医用イメージング、分子生物学、コンピューター援用エンジニアリング、マーケティング、購買、管理などのアプリケーション分野では類似性探索（ｓｉｍｉｌａｒｉｔｙ  ｓｅａｒｃｈ）と類似性分類（ｓｉｍｉｌａｒｉｔｙ  ｃｌａｓｓｉｆｉｃａｔｉｏｎ）の重要性が増している。特に、類似した二次元、三次元の形状を見つけ出す作業が益々重要視されている。幾何学的物体の形状に基づいて、類似した物体を読み出し（類似性探索）、類似した物体のクラスタを検出（分類）しなければならない。
【０００３】
広く使われている類の類似性モデルは特徴ベクトルのパラダイムに基づいている。このパラダイムの一例は以下のように記述することができる。すなわち、三次元物体の形状は、正則グリッドに配列された三次元の点の集合で記述される。すなわち、物体ｏはべき集合
2007528068.tif 000001
の要素とみなされ、ｏの体積又は表面積（物体の種類による）は濃度
2007528068.tif 000002
により測られる。特徴変換を使い、どの物体ｏも適切な多次元特徴空間内の特徴ベクトルに写像される。そうすると二つの物体の類似性は、特徴空間内でのこれら二つの物体の特徴ベクトルの近さとして定められる。すなわち、それぞれの特徴ベクトルの位置が近いほど二つの物体はより類似すると考えられる。
【０００４】
研究論文「Ｅｆｆｅｃｔｉｖｅ  Ｓｉｍｉｌａｒｉｔｙ  Ｓｅａｒｃｈ  ｏｎ  Ｎｏｘｅｌｉｚｅｄ  ＣＡＤ  Ｏｂｊｅｃｔｓ（ボクセル状のＣＡＤ物体の効果的な類似性検索）」Ｋｒｉｅｇｅｌ  Ｈ．−Ｐ．，  Ｋｒｏｅｇｅｒ  Ｐ．，  Ｍａｓｈａｅｌ  Ｚ．，  Ｐｆｅｉｆｌｅ  Ｍ．，  Ｐｏｅｔｋｅ  Ｍ．，  Ｓｅｉｄｌ  Ｔ．著、Ｐｒｏｃ．８ｔｈ  Ｉｎｔ．  Ｃｏｎｆ．  ｏｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ａｄｖａｎｃｅｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  （ＤＡＳＦＡＡ），Ｋｙｏｔｏ，２００３，ｐｐ．  ２７−３８には、特徴に基づく類似性モデルを利用した数々の公知の取り組みが要約されている。特に、この論文では物体が位置する空間内に複数のセルを定める分割スキームを決定してその物体の特徴データを決定する方法と、複数のセルに含まれる物体の各部分の例えば体積といった少なくとも一つのプロパティーに基づいて物体の特徴データを決定する方法が開示されている。等距離シェル、等辺セクタ、またはその組み合わせに基づいた分割スキームも開示されている。本願明細書には、上記の研究論文の全体が含まれる。
【０００５】
研究論文「Ｒｏｔａｔｉｏｎ  Ｉｎｖａｒｉａｎｔ  Ｓｐｈｅｒｉｃａｌ  Ｈａｒｍｏｎｉｃ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｏｆ  ３Ｄ  Ｓｈａｐｅ  Ｄｅｓｃｒｉｐｔｏｒｓ（三次元形状記述子の回転不変球調和関数表現）」Ｋａｚｈｄａｎ  Ｍ．，Ｆｕｎｋｈｏｕｓｅｒ  Ｔ．，Ｒｕｓｉｎｋｉｅｗｅｃｚ  Ｓ著、Ｐｒｏｃ．１ｓｔ  Ｅｕｒｏｇｒａｐｈｉｃｓ  Ｓｙｍｐｓｉｕｍ  ｏｎ  Ｇｅｏｍｅｔｒｙ  Ｐｒｏｃｅｓｓｉｎｇ（ＳＧＰ），Ａａｃｈｅｎ，２００３，ｐｐ．１６７−１７５には、形状の類似性を評価する際の問題点についての様々な公知の取り組みの概説が含まれている。
【０００６】
本発明の目的は、幾何学的特徴データを決定するための先行技術における方法の正確さ、および／又は効力、および／又は性能、および／又は有用性を改善する技術を提供することである。好ましい実施の形態では、特徴データが後続の類似性探索または類似性分類の正確さを改善する性質を有しており、それにより全体的な正確さの改善を達成したり、および／又は要求される正確さの水準に達する為に必要な計算量と記憶量を削減することができる。
【０００７】
本発明によると、上記の目的は、請求項１による方法、請求項５による方法、請求項１４による使用、請求項１５による使用、請求項１６によるコンピュータープログラム製品、請求項１７による装置によって、少なくとも部分的には達成される。従属請求項は本発明の好まれる実施の形態を定めている。
【０００８】
発明の第一の態様は、少なくとも二つのセルが少なくとも部分的に互いに重なり合うように、これらの複数のセルを定める分割スキーム（ｐａｒｔｉｔｉｏｎｉｎｇ  ｓｃｈｅｍｅ）を使うというアイディアに基づいている。このような分割スキームはまた、本願では「重複（ｒｅｄｕｎｄａｎｔ）分割スキーム」と呼ぶ。この重複性自体には計算量の追加が必要になる。しかしながら実験の結果によると、この影響を補うに余るほど得られる特徴データの正確さが向上するので、先行技術で必要なものに比べてはるかに粗い分割スキームを使うことが可能になる、という驚くべきことが発見された。全体的に見て、総計算量と総記憶量は一見無駄と思われる重複分割スキームによって大きく削減される。
【０００９】
本発明の第二の態様によると、複数のセルを定める分割スキームが使われており、これらのセルの少なくともいくつかの境界は物体の位置する空間内の複数の区域を定める。それもこの複数の区域に含まれる物体のそれぞれの部分が、所定の計量基準からして互いにほとんど等しくなるように範囲を定める。本願では、そのような区域にグループ分け可能な複数のセルを定める分割スキームを「比例（ｐｒｏｐｏｒｔｉｏｎａｌ）分割スキーム」と呼ぶ。先と同様に、実験によると、比例分割スキームを使うことにより全体的な正確さの向上が達成され、および／又はさもなければ必要とされるよりも粗い分割スキームを選ぶことが可能になる。
【００１０】
本発明の好ましい実施例では、分割スキームによって、重なりあう多数のセルが定められる。例えば、分割スキームにより定められた全てのセルの少なくとも５０％又が少なくとも９０％は他のセルと部分的もしくは全体的に重なり合う。実施例によっては、複数のセルは、物体が異なって位置する空間内の１つの区域とこれと同一の区域とを分割するセルの二つ以上のグループを含んでいる。言い換えると、セルのこれらの各グループ内にある全てのセルの和はそれぞれ同一空間を占め、一つのグループ内の各セルは、他の各グループの少なくとも一つのセルと少なくとも部分的に重なり合っている。
【００１１】
本発明の実施例によっては、分割スキームによって定められるセルは入れ子構造の（ｎｅｓｔｅｄ）セルのグループを含む。このグループ内のセルの重なり合いはそれぞれ完全な重なり合いである。分割スキームは、この入れ子構造のセルのグループに属さない付加的なセルを定めても定めなくても良い。入れ子構造のセルのグループのセルは、好ましくは、入れ子構造のセルのグループのセル内に含まれる物体の各部分のｋ次元の体積が、ほぼ規則的に、又は正確に規則的に増加する列を形成する。言い換えると、入れ子構造のセルのグループ内の第一のセルは物体の一つの体積単位を含み、第二のセルはおおよそもう一つの体積単位を含み、第三のセルは更にもう一つの体積単位を含むということである。他の実施例では、セルの完全な重なり合い（つまり入れ子構造）を何ら特定せず、部分的な重なり合いを特定する分割スキームを用いる。
【００１２】
重複分割スキームまたは比例分割スキームのいずれか一方の使用によってすでに相当な効果があるが、重複分割スキームおよび比例分割スキームの両方の使用が特に好ましい。実験によると、この組み合わせにより、重複分割スキームのみのメリットと比例分割スキームのみのメリットを単純に合計したメリットを超える、予期せぬ相乗的なメリットが実現されることが示されている。実施例によっては、重複の態様および比例の態様が、比例区域の少なくとも一つが、少なくとも二つの部分的に重なり合うセル又は完全に重なり合うセルを含むように組み合わされる。
【００１３】
実施例によっては、比例区域は互いに素であり、他の実施例によっては、これらの区域は少なくとも部分的に重なり合っている。区域は、必ずしも物体が位置する全空間をカバーする必要はない。実施例によっては、比例区域のどの部分でもない付加的なセルがあり、他の実施例によっては、分割スキームよって定められる全てのセルは区域の少なくとも一つに属する。
【００１４】
用いられる計量基準では区域内に含まれる物体の各部分がほぼ等しいことが要求されるが、この計量は物体の各部分のｋ次元の体積であることが好ましい。三次元の場合、この体積は各物体部分の「通常の」空間体積であり、二次元の体積は、実際には各物体部分によって占められる面積である。他の実施例では、例えば三次元の物体の部分の表面積といった他の基準が使用される。
【００１５】
本発明の第二の態様によると、比例区域は分割スキームによって定められるセルの境界によって範囲が定められる。好ましい実施例では、各区域が少なくとも二つのセルの和および／又は差および／又は共通部分に一致するか、あるいは、一つのセルに正確に一致することをこれは意味する。好ましくは、各区域は単一のセル又はセルのグループに一致し、あるいは第一のセル又はセルのグループから第二のセル又はセルのグループを引いた差に一致する。
【００１６】
一般的に、セルおよび／又は区域はどんな適切な形状でもよいが、正則形状がたいていは効果的である。セルおよび／又は区域の少なくともいくつか、あるいはセルおよび／又は区域の全てが以下の形状の内の一つであることが好ましい。すなわち、物体が位置する空間における、ｋ次元の球、ｋ次元のシェル、ｋ次元の球のセクタ、ｋ次元のシェルのセクタである。
【００１７】
本発明は、分割スキームのセル内に含まれる物体のそれぞれの部分の少なくとも一つのプロパティーに基づいて、物体の特徴データを決定するステップを含む。このステップを遂行するいくつかの方法自体は既知であり、本発明の実施に関連しても使用することができる。例えば、複数のセルの各セル内に含まれる物体のそれぞれの部分のｋ次元の体積に基づいて、および／又は複数のセルの各セル内に含まれる物体のそれぞれの部分のｋ本の主軸を定めるデータに基づいて、物体の特徴データを決定することができる。
【００１８】
実施例によっては、本発明によって得られる特徴データは特徴ベクトルである。この特徴データは様々な方法で使用できるが、それ自体も既知である。例えば、特徴データは複数の物体の類似性探索や類似性分類を実行するために使用される。
【００１９】
本発明のコンピュータープログラム製品は、本発明の方法を実行するプログラム命令を含む。コンピュータープログラム製品は、例えば半導体メモリ、コンピューターディスク、ＣＤ−ＲＯＭといった有形のデータ媒体である。しかしながら、コンピュータープログラム製品は、例えばコンピューターネットワーク内で送信された信号といった無形のデータ媒体でもよい。本発明の装置は、本発明の方法を実行するようにプログラムされた一般的なパーソナルコンピューター、ワークステーション、メインフレームコンピューター、コンピューターネットワークである。コンピューター製品、および／又は装置の好ましい実施例は、上述した特徴、および／又は方法の従属請求項の特徴に対応する特徴を含む。
【００２０】
本発明は一般的に、ｋ次元の空間内に位置する物体の形状に関する情報を表す特徴データを得るために使用される。以下に記述するサンプルの実施例では、物体ｏは、正則グリッドに配列されたｋ次元の点の集合によって特定される。したがって、物体ｏはべき集合
2007528068.tif 000003
の要素と見なされる。所定の集合
2007528068.tif 000004
、すなわちｋ次元の物体のドメインは定義されていると仮定する。ｏの体積又は表面積（物体の種類による）はその濃度
2007528068.tif 000005
により測られる。
【００２１】
本サンプルの実施例において得られる特徴データは「特徴ベクトル」と呼ばれる。形式的には、本サンプルの実施例はいわゆる特徴変換または特徴抽出
2007528068.tif 000006
を実行し、特徴変換または特徴抽出により物体ドメインＯの任意の物体ｏは、適切なｈ次元の特徴空間内の対応する特徴ベクトル上に写像される。
【００２２】
特徴データの目的とする用途は類似性探索や類似性分類を実行することである。二つの物体の類似性は特徴空間内の特徴ベクトルの近さで定義可能である。すなわち、それぞれの特徴ベクトルの位置が近いほど二つの物体はより類似すると考えられる。より形式的には、
2007528068.tif 000007
を二つのｈ次元の特徴ベクトル間の「距離関数」とする。距離関数δは、例えばマンハッタン距離やユークリッド距離である。したがって、二つの物体
2007528068.tif 000008
の特徴に基づく物体の類似性
2007528068.tif 000009
は、
2007528068.tif 000010
によって定められる。代替の実施例では、物体の回転、対称移動、平行移動の可能性を考慮した物体の類似性の他の基準が利用できる。この点に関しては、すでに引用した研究論文「ボクセル状ＣＡＤ物体の効果的な類似性探索」のセクション３．３を参照のこと。
【００２３】
本サンプルの実施例では、物体ｏの特徴ベクトルの計算は、物体ｏが位置するｋ次元の空間内にある複数のセルを定める分割スキームに基づく。この分割スキームに関して、様々なドメインを選択することができる。本サンプルの実施例では、物体ｏの最小包囲球ｂｓ（ｏ）が分割スキームのドメインとして使用される。このことは図１に示されている。より形式的には、物体ｏ∈Ｏの「最小包囲球」
2007528068.tif 000011
は、ｏの質量中心ｃを中心とする最小のｋ次元の球であり、ｏはｂｓ（ｏ）に完全に含まれている。分割スキームについての他のドメインを本発明の代替の実施例で使用してもよい。
【００２４】
本サンプルの実施例によると、物体ｏの複数の空間セルｐｉの和が分割スキームについてのドメイン（すなわち本ケースでは最小包囲球ｂｓ（ｏ））を完全に満たすように、分割スキームはセルｐｉを定める。より形式的には、
2007528068.tif 000012
をｋ次元の物体のドメインとし、
2007528068.tif 000013
をｋ次元のセルのドメインとする。そうすると、「分割スキーム」
2007528068.tif 000014
は、所与の物体ｏ∈Ｏおよびその最小包囲球ｂｓ（ｏ）に対して、ｄ個の空間セルの列
2007528068.tif 000015
を定める。ここで、
2007528068.tif 000016
である。なお、分割スキームπによって定められるセルｐｉは必ずしも互いに素でなくてもよい。
【００２５】
物体ｏの特徴データ又は特徴ベクトルは、分割スキームπによってセルｐｉのそれぞれに含まれる物体ｏの各部分の少なくとも一つのプロパティーに基づいて定められる。この概念を数式化するため、「集約（ａｇｇｒｅｇａｔｉｏｎ）」
2007528068.tif 000017
を導入し、これは所与のセルｐ∈Ｐに含まれるｏ∈Ｏの全ての点をａ次元のベクトルα（ｏ，ｐ）上に写像するものである。したがって、本サンプルの実施例の特徴抽出（ｅｘｔｒａｃｔｏｒ）
2007528068.tif 000018
は、物体ｏと分割スキームの個々のセルｐｉとに適用された集約関数αの結果の連結として表現できるという性質を有する。より形式的には、本サンプルの実施例の特徴抽出
2007528068.tif 000019
は、φが
2007528068.tif 000020
と表現できるように、分割πと集約αが存在するという性質を有する。ここで、
2007528068.tif 000021
であり、ｈ＝ｄ・ａである。そのような特徴抽出φを「分割スキームに基づく特徴抽出」と呼ぶ。
【００２６】
図２は、先行技術で既知の分割スキームを三つのセル（ｄ＝３）で示したものである。この分割スキームは、（１）全てのセルｐｉは「互いに素」である、（２）セルｐｉの境界は「等距離」である、という性質を有する。第一のセルｐ１はｋ次元の球（すなわち、ｋ＝２の場合は円、ｋ＝３の場合は空間球）の形状であり、第二および第三のセルｐ２、ｐ３はそれぞれ最小包囲球ｂｓ（ｏ）の中心ｃを中心とするｋ次元のシェルの形状を有する。図２の分割スキームは互いに素（ｄｉｓｊｏｉｎｔ）で等距離（ｅｑｕｉｄｉｓｔａｎｔ）であることから「ＤＥ」と呼ぶ。
【００２７】
図３は、本発明の第一のサンプルの実施例による分割スキームを三つのセル（ｄ＝３）で図示したものである。一般的に、本発明の全ての分割スキームは特に異種の物体のデータベースに適している。図３の分割スキームはいわゆる「比例分割スキーム」である。ここに記述するサンプルの実施例の比例分割スキームでは、セルの境界やこれらの境界のいくつかは、各区域内に含まれる物体の体積が少なくともほぼ一定であるように、空間内において多数の区域を定める。したがって、セルおよび区域の境界は各物体の個々の形状に適合する。
【００２８】
図３のサンプルの実施例では、各セルｐｌ、ｐ２、ｐ３がこれらの比例区域（ｒ１、ｒ２、ｒ３で示される）の一つに正確に一致している。より形式的には、区域ｒｉ（ｉは１≦ｉ≦３）のそれぞれは、区域ｒｉに含まれる物体ｏの一部分が一定の体積を有する、すなわち、ｄ’＝ｄ＝３およびｒｉ＝ｐｉについて
2007528068.tif 000022
であるという性質を有する。
【００２９】
図３の比例分割スキームは、互いに素（ｄｉｓｊｏｉｎｔ）で比例する（ｐｒｏｐｏｒｔｉｏｎａｌ）ことから「ＤＰ」と呼ばれる。図２の先行技術による分割スキームを形状ヒストグラム（ｓｈａｐｅ ｈｉｓｔｏｇｒａｍ）と称するならば、図３のアプローチは「形状分位（ｓｈａｐｅ ｑｕａｎｔｉｌｅ）」と呼ぶことができ、「分位」は分割スキームによって定められる分割セルの数ｄによって決定される。
【００３０】
図４は本発明の更なるサンプルの実施例を示したものであり、すなわち三つのセル（ｄ＝３）のいわゆる重複分割スキームである。実験によると、重複性の使用、すなわちセルを重なり合わせることによって、類似データ、特に複雑な物体の類似データの質および有用性がしばしば向上することが示されている。物体を互いに素なセルに分割しないことによって、物体の形状全体がはるかによい状態で維持されると考えられる。本サンプルの実施例では、重複分割スキーム
2007528068.tif 000023
、
2007528068.tif 000024
の概念は、非空の空間区域を共有するセルｐｉ、ｐｊがｉ≠ｊおよび１≦ｉ、ｊ≦ｄについて存在する、すなわち
2007528068.tif 000025
であるという性質によって形式的に表現できる。
【００３１】
図４のサンプルの実施例では、セルｐｉは入れ子構造のセルの単一のグループｇｎを形成する。言い換えると、最小のセルｐ１はセルｐ２に十分に含まれ、一方でセルｐ２は最大のセルｐ３に十分に含まれる。それゆえ、セルｐ１〜ｐ３は、「包含」関係によって十分に順序づけられた列を構成している。更に、セルｐｉの境界は等距離である。
【００３２】
図５は、重複かつ等距離分割スキームの更なるサンプルの実施例を１７個のセル（ｄ＝１７）で示したものである。このスキームは、図２のセルｐ２とセルｐ３を更に分けることによって、図２の先行技術の分割スキームから得られる。より具体的には、図２の第二のセルｐ２は、内側セルｐ２〜ｐ５の第一のグループｇｉ１と、内側セルｐ６〜ｐ９の第二のグループｇｉ２とに更に分けられている。これらのグループｇｉ１、ｇｉ２のそれぞれに含まれるセルは、それぞれのグループｇｉ１、ｇｉ２内において互いに素である。しかしながら、グループｇｉ１、ｇｉ２は、一方のグループのある各セルが他方のグループの二つのセルに重なり合うように、互いに対してずれている。同様に、図２の第三のセルｐ３は外側セルｐ１０〜ｐ１３の第一のグループｇｏ１と、外側セルｐ１４〜ｐ１７の第二のグループｇｏ２とに更に分けられている。セルｐ２〜ｐ１７のそれぞれは、最小包囲球ｂｓ（ｏ）内のｋ次元のシェルのセクタの形状をしている。
【００３３】
図４および図５の重複かつ等距離分割スキームの例は、それぞれＲＥ１（ｏ）、ＲＥ２（ｏ）と呼ぶ。
【００３４】
実験によると、比例分割と重複分割とを組み合わせた場合、特にメリットが大きいことが示された。重複と比例とを組み合わせた分割スキームは「ＲＰ」と呼ぶ。図６および図７は、ＲＰ分割のサンプルの実施例を二つ示している。
【００３５】
図６のスキームＲＰ１（ｏ）は、三つのセル（ｄ＝３）を定める。このスキームは、三つの入れ子構造のセルｐｌ、ｐ２、ｐ３のグループｇｎを定めるという点で、図４のスキームＲＥ１（ｏ）に類似している。しかしながら、図４のスキームＲＥ１（ｏ）とは異なり、セルｐｌ、ｐ２、ｐ３の境界は、更に、ｄ’＝３について
2007528068.tif 000026
を維持するように、三つの比例区域ｒ１、ｒ２、ｒ３を定める。第一の区域ｒｌは第一のセルｐｌと同一である。第二の区域ｒ２は、第一のセルｐｌと第二のセルｐ２の境界によって範囲が定められる。第三の区域ｒ３は、第二のセルｐ２と第三のセルｐ３の境界によって範囲が定められる。言い換えると、第二の区域ｒ２はｐ２からｐｌを引いた差であり、第三の区域ｒ３はｐ３からｐ２を引いた差である。
【００３６】
更に注目すべき点として、図６の例では、セルｐ１〜セルｐ３にある物体ｏの各部分の体積は、規則的に、すなわち各セルについて物体ｏの総体積の１／ｄづつ増加する。したがって、三つのセルの本例では、第一のセルｐ１は物体ｏの総体積の約１／３、第二のセルｐ２は約２／３、第三のセルｐ３は総体積を含む。
【００３７】
図７のスキームＲＰ２（ｏ）は１７個のセル（ｄ＝１７）を定める。このスキームは、内側セルの二つの重複するグループｇｉ１とｇｉ２と、外側セルの二つの重複するグループｇｏ１とｇｏ２とを定めるという点で、図５のスキームＲＥ２（ｏ）に類似している。しかしながら、図５のスキームＲＥ２（ｏ）とは異なり、ＲＰ２（ｏ）のセルの境界は更に、ｄ’＝３について
2007528068.tif 000027
（ｄ’は区域の数）を維持するように、三つの比例区域ｒｌ、ｒ２、ｒ３を定める。第一の区域ｒｌは第一のセルｐｌと同一である。第二の区域ｒ２は、セルｐ２〜セルｐ９の曲線状の境界によって範囲が定められる。第三の区域ｒ３は、セルｐ１０〜セルｐ１７の曲線状の境界によって範囲が定められる。言い換えると、第二の区域ｒ２はｐ２〜ｐ９の和であり、第三の区域ｒ３はｐ１０〜ｐ１７の和である。
【００３８】
上述したように、本サンプルの実施例の方法は、集約
2007528068.tif 000028
に基づいて物体ｏの特徴ベクトルを決定するために、図３〜図７の一つに示された分割スキームを使用する。適切な集約関数はそれ自体既知である。例えば、それぞれのセルｐ内に含まれる物体ｏの部分の正規化体積を計算する集約
2007528068.tif 000029
を使用することができる。代替的に、それぞれのセルｐ内に含まれる物体ｏの部分のｋ本の主軸に沿った分散を定める集約
2007528068.tif 000030
を使用してもよい。物体ｏおよびセルｐの集約α２の計算には、セルｐ内に含まれる物体ｏの部分の境界を示す最小の楕円にわたるｋ個の固有ベクトルに対応するｋ個の固有値を決定し、それからｋ個の固有値を分類し、最後に結果α２（ｏ，ｐ）として分類されたｋ個の固有値を出力することが含まれる。集約α１およびα２を実行するために必要な計算は、先に引用した研究論文「ボクセル状ＣＡＤ物体の効果的な類似性探索」のセクション３．４．１および３．４．３により詳しく記述されている。これらのセクションは本願明細書に参照により含まれる。
【００３９】
上述したサンプルの実施例では、所与の物体ｏの特徴ベクトルφ（ｏ）は、対応する分割スキームによって定められる全てのセルｐに、集約αを適用することによって得られる全ての結果を、単に連結したものである。他の実施例では、更なる正規化、又は他の追加の処理ステップを実行してもよい。
【００４０】
全体として見ると、結果としてもたらされた類似性の基準を使用して、物体の大きな集まりをその幾何学的特徴によって分類したり、類似した物体のデータベース探索を行ったり、物体の幾何学的類似性を評価しなければならない他の作業を行ったりすることができる。
【００４１】
本発明の長所を評価するために、ここに提案した分割のアプローチの効力を先行技術による最も優れた技術の一つと比較した。先行技術による最も優れた技術とは、先に引用した研究論文「三次元形状記述子の回転不変球調和関数表現」で提案しているような、球の調和値の集約関数を用いたＤＥ分割に基づいている。非常に有望な結果が得られている。例えば、図８は、たんぱく質データベースに関する先行技術のＤＥ分割および本ＲＰ１分割の結果を示したものである。再現率５０％では、ＤＥに基づく方法では精度が２６％であるのに対して、ＲＰ１に基づく方法では４２％の精度を示している。再現率８０％では、ＲＰ１はＤＥよりもほぼ二倍の精度をもたらす。ＣＡＤおよびウェブデータに関しても同様の結果が得られている。
【００４２】
図９は、上記と同じ構成で得られる性能の結果を示している。ＲＰ１がＤＥよりも約十倍早く実行されることが明らかである。したがって、ＲＰ１はＤＥよりも非常に高い効力をもたらすだけではなく、ランタイムで見たコストが格段に低くなる。ＤＥの性能が遅いのは、よい結果を出すために、はるかにきめの細かい分割スキームを必要とするという事実のためである。したがって、作り出されたＤＥの特徴ベクトルは、距離関数によって評価するためには、はるかにより長くて高価である。
【００４３】
類似性に基づいた探索および／又は分類の方法の正確さおよび効力を改善するために、本発明が利用できるということが明らかである。上述したサンプルの実施例の記述に含まれる詳細は、本発明の範囲を制限するように解釈されるべきではなく、むしろ本発明の好まれる実施例の例示として解釈されるべきである。他の多くの変形が可能であり、当業者には容易に明らかである。それゆえ、本発明の範囲は、説明した実施例によって定められるのではなく、添付の請求項およびそれらと法的に等価であるものによって定められる。
【００４４】
更なる特徴や、本発明の目的および効果は、以下に詳細に記述するいくつかのサンプルの実施例から明らかになる。図を参照とされたい。
【図面の簡単な説明】
【００４５】
【図１】物体と、それに対応する最小包囲球の一例である。
【図２】先行技術による互いに素かつ等距離分割スキームの一例である。
【図３】本発明の第一の実施例による、互いに素かつ比例分割スキームの一例である。
【図４】本発明の第二の実施例による、重複かつ等距離分割スキームの第一の例である。
【図５】本発明の第三の実施例による、重複かつ等距離分割スキームの第二の例である。
【図６】本発明の第四の実施例による、重複かつ比例分割スキームの第一の例である。
【図７】本発明の第五の実施例による、重複かつ比例分割スキームの第二の例である。
【図８】図２の先行技術の分割スキームと図６の分割スキームとを比較し、精度と再現率の関係をプロットしたものである。
【図９】たんぱく質データについて、図２の先行技術による分割スキームを使用する分類にかかる総ランタイム（ｔｏｔａｌ  ｒｕｎｔｉｍｅ）と、図６の分割スキームを使用する分類にかかる総ランタイムとを比較した図である。
【誤訳訂正２】
【訂正対象書類名】図面
【訂正対象項目名】図１
【訂正方法】変更
【訂正の内容】
【図１】
2007528068.tif 000031
【誤訳訂正３】
【訂正対象書類名】図面
【訂正対象項目名】図２
【訂正方法】変更
【訂正の内容】
【図２】
2007528068.tif 000032
【誤訳訂正４】
【訂正対象書類名】図面
【訂正対象項目名】図３
【訂正方法】変更
【訂正の内容】
【図３】
2007528068.tif 000033
【誤訳訂正５】
【訂正対象書類名】図面
【訂正対象項目名】図４
【訂正方法】変更
【訂正の内容】
【図４】
2007528068.tif 000034
【誤訳訂正６】
【訂正対象書類名】図面
【訂正対象項目名】図５
【訂正方法】変更
【訂正の内容】
【図５】
2007528068.tif 000035
【誤訳訂正７】
【訂正対象書類名】図面
【訂正対象項目名】図６
【訂正方法】変更
【訂正の内容】
【図６】
2007528068.tif 000036
【誤訳訂正８】
【訂正対象書類名】図面
【訂正対象項目名】図７
【訂正方法】変更
【訂正の内容】
【図７】
2007528068.tif 000037
【誤訳訂正９】
【訂正対象書類名】特許請求の範囲
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【特許請求の範囲】
【請求項１】
コンピュータにより、ｋ次元、但しｋ＝２または３、の空間に位置する物体（ｏ）の形状に関する情報を表す特徴ベクトルを決定する方法であって、
該方法は、前記コンピュータが
物体（ｏ）が位置する空間に複数のセル（ｐ）を定め、この際、該複数のセル（ｐ）の二つ以上によって該物体（ｏ）が完全に含まれ、かつ、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように定める分割スキームを決定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の該各部分の少なくとも一つのプロパティーに基づいて該物体（ｏ）の特徴ベクトルを決定するステップと、
前記決定された特徴ベクトルに基づいて、前記物体（ｏ）に関する類似性探索または類似性分類を行うステップと、
を実行するものであり、
該複数のセル（ｐ）が互いに素なセルの第一のグループ（ｇｉ１；ｇｏ１）および互いに素なセルの第二のグループ（ｇｉ２；ｇｏ２）を含んでおり、該セルの第一のグループ（ｇｉ１；ｇｏ１）のセルの和は該セルの第二のグループ（ｇｉ２；ｇｏ２）のセルの和と同一空間を占め、かつ、
該セルの第一のグループ（ｇｉ１；ｇｏ１）の各セルが該セルの第二のグループ（ｇｉ２；ｇｏ２）の各少なくとも一つのセルと少なくとも部分的に重なり合うこと、
を特徴とする方法。
【請求項２】
前記セルの第一のグループ（ｇｉ１；ｇｏ１）および前記セルの第二のグループ（ｇｉ２；ｇｏ２）は、それぞれ、物体（ｏ）の最小包囲球ｂｓ（ｏ）内のｋ次元の第一のシェル内にあること、を特徴とする請求項１記載の方法。
【請求項３】
前記複数のセル（ｐ）が互いに素なセルの第三のグループ（ｇｉ１；ｇｏ１）および互いに素なセルの第四のグループ（ｇｉ２；ｇｏ２）を含んでおり、該セルの第三のグループ（ｇｉ１；ｇｏ１）のセルの和は該セルの第四のグループ（ｇｉ２；ｇｏ２）のセルの和と同一空間を占め、かつ、
該セルの第三のグループ（ｇｉ１；ｇｏ１）の各セルが該セルの第四のグループ（ｇｉ２；ｇｏ２）の各少なくとも一つのセルと少なくとも部分的に重なり合い、
前記セルの第三のグループ（ｇｉ１；ｇｏ１）および前記セルの第四のグループ（ｇｉ２；ｇｏ２）は、それぞれ、物体（ｏ）の最小包囲球ｂｓ（ｏ）内のｋ次元の第二のシェル内にあり、
前記第一のシェル内のセルと前記第二のシェル内のセルとは互いに素であること、
を特徴とする請求項２記載の方法。
【請求項４】
前記第１のシェルおよび前記第２のシェルの半径方向の幅が互いに等しいこと、を特徴とする請求項３記載の方法。
【請求項５】
前記第１のシェル内のセルおよび前記第２のシェル内のセルに含まれる物体（ｏ）のｋ次元の体積が互いに等しいこと、を特徴とする請求項３記載の方法。
【請求項６】
コンピュータにより、ｋ次元、但しｋ＝２または３、の空間に位置する物体（ｏ）の形状に関する情報を表す特徴ベクトルを決定する方法であって、
該方法は、前記コンピュータが
物体（ｏ）が位置する空間に複数のセル（ｐ）を定め、この際、該複数のセル（ｐ）の二つ以上によって該物体（ｏ）が完全に含まれ、かつ、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように定める分割スキームを決定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の各部分の少なくとも一つのプロパティーに基づいて該物体（ｏ）の特徴ベクトルを決定するステップと、
前記決定された特徴ベクトルに基づいて、前記物体（ｏ）に関する類似性探索または類似性分類を行うステップと、
を実行するものであり、
該複数のセル（ｐ）が少なくとも一つの入れ子構造のセルのグループ（ｇｎ）を含んでおり、該入れ子構造のセルのグループ（ｇｎ）の全てのセルが互いに入れ子関係にあること、
を特徴とする方法。
【請求項７】
前記セル（ｐ）それぞれに含まれる該物体（ｏ）の各部分のｋ次元の体積が少なくとも規則的に変化すること、を特徴とする請求項６記載の方法。
【請求項８】
前記複数のセル（ｐ）はそれぞれ、物体（ｏ）の最小包囲球（ｂｓ（ｏ））内の互いに半径の異なるｋ次元の球を構成すること、を特徴とする請求項６または７記載の方法。
【請求項９】
前記複数のセル（ｐ）の各境界間の距離は互いに等しいこと、を特徴とする請求項６を引用する請求項８記載の方法。
【請求項１０】
前記複数のセル（ｐ）が、それぞれ、該物体（ｏ）が位置する空間のｋ次元の球体および／又はｋ次元のシェルおよび／又はｋ次元の球体のセクタおよび／またはｋ次元のシェルのセクタであること、を特徴とする請求項１乃至９のいずれか一つの方法。
【請求項１１】
該複数のセル（ｐ）の各セル（ｐ）内に含まれる該物体（ｏ）の各部分のｋ次元の体積に基づいて、および／又は、前記複数のセル（ｐ）の各セル（ｐ）に含まれる該物体（ｏ）の各部分のｋ本の主軸を定めるベクトルに基づいて、該物体（ｏ）の特徴ベクトルが決定されること、を特徴とする請求項１乃至１０のいずれか１項記載の方法。
【請求項１２】
少なくとも２つの物体（ｏ）について決定された特徴ベクトル同士を比較して、該物体間の類似性を決定する、請求項１乃至１１のいずれか１項記載の方法。
【請求項１３】
決定された類似性に基づいて、該物体の分類を行う、請求項１２記載の方法。
【請求項１４】
たんぱく質、ＣＡＤ又はウェブデータについて類似性探索および／または類似性分類を行う、請求項１乃至１３のいずれか１項記載の装置。
【請求項１５】
ｋ次元、但しｋ＝２または３、の空間に位置する物体（ｏ）の形状に関する情報を表す特徴ベクトルを決定するためのコンピュータを備えた装置であって、
前記コンピュータは、
物体（ｏ）が位置する空間に複数のセル（ｐ）を定め、この際、該複数のセル（ｐ）の二つ以上によって該物体（ｏ）が完全に含まれ、かつ、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように定める分割スキームを決定し、
該複数のセル（ｐ）に含まれる該物体（ｏ）の各部分の少なくとも一つのプロパティーに基づいて該物体（ｏ）の特徴ベクトルを決定し、
前記決定された特徴ベクトルに基づいて、前記物体（ｏ）に関する類似性探索または類似性分類を行うものであり、
該複数のセル（ｐ）が互いに素なセルの第一のグループ（ｇｉ１；ｇｏ１）および互いに素なセルの第二のグループ（ｇｉ２；ｇｏ２）を含んでおり、該セルの第一のグループ（ｇｉ１；ｇｏ１）のセルの和は該セルの第二のグループ（ｇｉ２；ｇｏ２）のセルの和と同一空間を占め、かつ、
該セルの第一のグループ（ｇｉ１；ｇｏ１）の各セルが該セルの第二のグループ（ｇｉ２；ｇｏ２）の各少なくとも一つのセルと少なくとも部分的に重なり合うこと、
ことを特徴とする装置。
【請求項１６】
ｋ次元、但しｋ＝２または３、の空間に位置する物体（ｏ）の形状に関する情報を表す特徴ベクトルを決定するためのコンピュータを備えた装置であって、
前記コンピュータは、
物体（ｏ）が位置する空間に複数のセル（ｐ）を定め、この際、該複数のセル（ｐ）の二つ以上によって該物体（ｏ）が完全に含まれ、かつ、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように定める分割スキームを決定し、
該複数のセル（ｐ）に含まれる該物体（ｏ）の各部分の少なくとも一つのプロパティーに基づいて該物体（ｏ）の特徴ベクトルを決定し、
前記決定された特徴ベクトルに基づいて、前記物体（ｏ）に関する類似性探索または類似性分類を行い、
該複数のセル（ｐ）が少なくとも一つの入れ子構造のセルのグループ（ｇｎ）を含んでおり、該入れ子構造のセルのグループ（ｇｎ）の全てのセルが互いに入れ子関係にあること、
ことを特徴とする装置。
【請求項１７】
コンピュータに、ｋ次元、但しｋ＝２または３、の空間に位置する物体（ｏ）の形状に関する情報を表す特徴ベクトルを決定する処理を実行させるためのプログラムであって、
該プログラムは、
物体（ｏ）が位置する空間に複数のセル（ｐ）を定め、この際、該複数のセル（ｐ）の二つ以上によって該物体（ｏ）が完全に含まれ、かつ、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように定める分割スキームを決定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の各部分の少なくとも一つのプロパティーに基づいて該物体（ｏ）の特徴ベクトルを決定するステップと、
前記決定された特徴ベクトルに基づいて、前記物体（ｏ）に関する類似性探索または類似性分類を行うステップと、
を前記コンピュータに実行させるものであり、
該複数のセル（ｐ）が互いに素なセルの第一のグループ（ｇｉ１；ｇｏ１）および互いに素なセルの第二のグループ（ｇｉ２；ｇｏ２）を含んでおり、該セルの第一のグループ（ｇｉ１；ｇｏ１）のセルの和は該セルの第二のグループ（ｇｉ２；ｇｏ２）のセルの和と同一空間を占め、かつ、
該セルの第一のグループ（ｇｉ１；ｇｏ１）の各セルが該セルの第二のグループ（ｇｉ２；ｇｏ２）の各少なくとも一つのセルと少なくとも部分的に重なり合うこと、
ことを特徴とするプログラム。
【請求項１８】
コンピュータに、ｋ次元、但しｋ＝２または３、の空間に位置する物体（ｏ）の形状に関する情報を表す特徴ベクトルを決定する処理を実行させるためのプログラムであって、
該プログラムは、
物体（ｏ）が位置する空間に複数のセル（ｐ）を定め、この際、該複数のセル（ｐ）の二つ以上によって該物体（ｏ）が完全に含まれ、かつ、該複数のセル（ｐ）の少なくとも二つが少なくとも部分的に互いに重なり合うように定める分割スキームを決定するステップと、
該複数のセル（ｐ）に含まれる該物体（ｏ）の各部分の少なくとも一つのプロパティーに基づいて該物体（ｏ）の特徴ベクトルを決定するステップと、
前記決定された特徴ベクトルに基づいて、前記物体（ｏ）に関する類似性探索または類似性分類を行うステップと、
を前記コンピュータに実行させるものであり、
該複数のセル（ｐ）が少なくとも一つの入れ子構造のセルのグループ（ｇｎ）を含んでおり、該入れ子構造のセルのグループ（ｇｎ）の全てのセルが互いに入れ子関係にあること、
ことを特徴とするプログラム。