"原始要素および関係を含む複数のデータグラフをクラスタ化する方法であって、制御演算装置により、関連するサブグラフのグラフを含むグラフラティスを生成することを含み、次数1のサブグラフは前記原始要素であり、次数i>1の各サブグラフは次数i-1のサブグラフおよび前記原始要素のうちの1つを含み、制御演算装置により、前記複数のデータグラフに対する特徴ベクトルを生成するために前記グラフラティスを使用することを含み、制御演算装置により、前記生成された特徴ベクトルの間の類似性に従って前記複数のデータグラフをクラスタ化することを含む、複数のデータグラフをクラスタ化する方法。前記特徴ベクトルが接合点規格化マッピングカウントを用いて決定される、請求項1に記載の方法。接合点規格化マッピングカウントが、接合点マッピングカウントにより再重み付けされたサブグラフマッチングカウントである、請求項1に記載の方法。前記生成された特徴ベクトルの間の前記類似性が共通マイナス差尺度を用いて決定される、請求項1に記載の方法。前記共通マイナス差尺度が絶対的な大きさを要素ごとに比較する、請求項1に記載の方法。前記クラスタ化することが、前記特徴ベクトルを用いて前記複数のデータグラフのそれぞれに対する最良適合クラスタを見つけることと、前記複数のデータグラフの前記それぞれに対する類似性スコアを前記データグラフの前記最良適合クラスタに基づいて決定することと、前記データグラフの前記類似性スコアが第1のしきい値を超えているとき、前記複数のデータグラフの前記それぞれを前記データグラフの前記最良適合クラスタを用いて分類することと、前記データグラフの前記類似性スコアが第2のしきい値よりも小さいとき、前記複数のデータグラフの前記それぞれを新しいクラスタ内に分類することと、前記データグラフの前記類似性スコアが前記第1のしきい値と前記第2のしきい値の間にあるとき、前記複数のデータグラフの前記それぞれを未確定クラスタ内に分類することと、を含む、請求項1に記載の方法。原始要素および関係を含むデータグラフを分類する方法であって、制御演算装置により、関連するサブグラフのグラフを含むグラフラティスを生成することを含み、次数1のサブグラフは前記原始要素であり、次数i>1の各サブグラフは次数i-1のサブグラフおよび前記原始要素のうちの1つを含み、制御演算装置により、前記データグラフと第1のカテゴリの見本とに対する特徴ベクトルを生成するために前記グラフラティスを使用することを含み、制御演算装置により、前記データグラフと前記第1のカテゴリの前記見本とに対する前記生成された特徴ベクトルを比較することを含み、画像と前記見本との前記特徴ベクトルの間の類似性がしきい値を超えているとき、制御演算装置により、前記データグラフを前記第1のカテゴリの要素として分類することを含む、データグラフを分類する方法。前記特徴ベクトルが接合点規格化マッピングカウントを用いて決定される、請求項7に記載の方法。接合点規格化マッピングカウントが、接合点マッピングカウントにより再重み付けされたサブグラフマッチングカウントである、請求項8に記載の方法。前記特徴ベクトルの間の前記類似性が共通マイナス差尺度を用いて決定される、請求項7に記載の方法。空間関係をコード化する一つの方法はグラフである。オブジェクトやシーンは、部分ノードや関係リンクとしてモデル化される。観察された画像は、観察された部分およびかかる部分と他の部分との関係についてのグラフを生成し、認識はサブグラフマッチングによって行われる。サブグラフマッチングにはいくつかの困難が伴う。第一に指数関数的に高価である。この問題は属性グラフの使用によりある程度緩和される。しかし、サブグラフマッチングは、第二の困難な点により比較的小さいサブグラフに限定されている。この第二の困難な点というのは、ノイズと変動性によって、観察されたグラフが理想のモデルから逸脱してしまうことである。その結果、不正確なグラフマッチング技法を使用することになり、ひいては、マッチングコストが急増し、属性グラフマッチングの利点は大半失われる。つまり、画像のノイズおよび変動性は、必要なマッチングを迅速かつ効果的に行うのを困難にしている。かかる問題に対処する方法および/またはシステムの開発が求められている。以下の開示は、かかる方法および/またはシステムについて考察するものである。本開示のプロセスは、原始要素および関係を含む複数のデータグラフをクラスタ化する方法であって、制御演算装置により、関連するサブグラフのグラフを含むグラフラティスを生成することを含み、次数1のサブグラフは前記原始要素であり、次数i>1の各サブグラフは次数i-1のサブグラフおよび前記原始要素のうちの1つを含み、制御演算装置により、前記複数のデータグラフに対する特徴ベクトルを生成するために前記グラフラティスを使用することを含み、制御演算装置により、前記生成された特徴ベクトルの間の類似性に従って前記複数のデータグラフをクラスタ化することを含む、複数のデータグラフをクラスタ化する方法を含む。また、本開示のプロセスは、前記クラスタ化することが、前記特徴ベクトルを用いて前記複数のデータグラフのそれぞれに対する最良適合クラスタを見つけることと、前記複数のデータグラフの前記それぞれに対する類似性スコアを前記データグラフの前記最良適合クラスタに基づいて決定することと、前記データグラフの前記類似性スコアが第1のしきい値を超えているとき、前記複数のデータグラフの前記それぞれを前記データグラフの前記最良適合クラスタを用いて分類することと、前記データグラフの前記類似性スコアが第2のしきい値よりも小さいとき、前記複数のデータグラフの前記それぞれを新しいクラスタ内に分類することと、前記データグラフの前記類似性スコアが前記第1のしきい値と前記第2のしきい値の間にあるとき、前記複数のデータグラフの前記それぞれを未確定クラスタ内に分類することと、を含む方法を含む。また、本開示のプロセスは、原始要素および関係を含むデータグラフを分類する方法であって、制御演算装置により、関連するサブグラフのグラフを含むグラフラティスを生成することを含み、次数1のサブグラフは前記原始要素であり、次数i>1の各サブグラフは次数i-1のサブグラフおよび前記原始要素のうちの1つを含み、制御演算装置により、前記データグラフと第1のカテゴリの見本とに対する特徴ベクトルを生成するために前記グラフラティスを使用することを含み、制御演算装置により、前記データグラフと前記第1のカテゴリの前記見本とに対する前記生成された特徴ベクトルを比較することを含み、画像と前記見本との前記特徴ベクトルの間の類似性がしきい値を超えているとき、制御演算装置により、前記データグラフを前記第1のカテゴリの要素として分類することを含む、データグラフを分類する方法を含む。サブグラフの形の複雑な画像特徴の大きな族を、グラフラティスの構造すなわち、ラティスで結ばれた関連するサブグラフの階層を通じて、より単純な画像特徴から作ることができる。多数のこれらの特徴サブグラフを支持することにより、正確なグラフマッチングを通じて画像構造を捕捉できる。後で分かるように、グラフラティスは画像雑音およびばらつきがある場合でも効率的なグラフマッチングを促進し、効率的な画像クラスタリング、分類、検索、反復構造発見、および新規性検出を促進することが有利である。下記のシステムおよび方法は、特に文書形状認識の実際的問題に対処するために直線的線画の領域で説明されている。しかしながら、概念は直線的線画以外の、原始要素の集合に分解できる画像に適用できることを理解すべきである。グラフラティスと呼ばれる基本的枠組みはノードのラティスであり、各ノードは画像原始要素および関係を示すサブグラフに対応している。グラフラティスノードは、それらの各サブグラフから原始要素を付加上方におよび除去下方にすることによりラティス内で互いに関連している。例えば、原始要素が次数1を定義するとき、ラティスが次数1から次数Nまで広がっていると仮定すれば、次数i>1のすべてのサブグラフは次数i-1のサブグラフに原始要素を加えたものを含む。アイデアは少なくとも2つの理由から直線的線画の領域で説明されている。第1に、直線的線画の領域の基準線は明確な形で交差して接合点および自由端ターミネータを形成するので、直線的線画はグラフとして容易に表すことができる。これらの接合点はグラフのノードとして使用するのによく適しているとともに、接合点を結び付ける基準線部分はグラフの連結棒として使用するのによく適している。第2に、直線的線画は文書において一般的であり、上述のように、本明細書に開示する発明の要旨は、文書といっしょに一般に使用される画像分類、検索、重複検出に関連して特定用途を有している。図1は直線的線画、およびこれらの実施例の中に見られる反復構造の一部を示す。第1の画像102および第2の画像104は、それぞれ棒グラフの直線的線画画像を含んでいる。さらに、これらの画像の中には部分構造106のような反復部分構造がある。部分構造106が示すように、部分構造は単一画像の中で、および/または複数画像にわたって繰り返すことができる。グラフラティス表現は部分構造をサブグラフとして発見して使用することを可能にする。図2は直線的線画の領域における13種類の接合点を規定している。これらはグラフラティスの原始要素または第1レベルのサブグラフである。13個の原始的接合点種別は、原子を組み合わせて分子を形成するのとほぼ同じ方法でそれらの適合する連結方向に従って分類できる。図3はこれらの原始要素の98個の可能な組み合わせがある、言い換えれば、次数2の98個のサブグラフがあることを示している。これらの組み合わせのうちの2つは、中ぶらりんの線分を有していないサブグラフである図形例えば、単一の水平なおよび垂直な線分を形成している。しかしながら、残りは中ぶらりんの線分を有しており、そのために、それらは図形のサブグラフとしてのみ使用できる。原始要素とサブグラフの間の親子関係は、ラティスを形成する。より小さいサブグラフは親ノードと呼ばれ、接合点を付加することにより、より小さいサブグラフから生成されたより大きなサブグラフは子ノードと呼ばれる。図4は上述した概念を示している。そのとき、原始要素の例外はあるが、次数iの各サブグラフは次数i-1のサブグラフおよび原始要素を含む。例えば、次数3のサブグラフ402は、次数2のサブグラフ404および原始要素406次数1のサブグラフでもあるを含む。本明細書の議論では子グラフラティスノードの次数は常にそれらの親の次数よりも1だけ大きいことを仮定しているが、特定の実施形態では、任意の大きさの2つのサブグラフを結合して、より大きなサブグラフを生成してもよい。次数Nの完全に母集団化されたグラフラティスを作るために、次数のサブグラフのすべての連結適合位置に13個のすべての原始要素を付加して次数i1のすべてのサブグラフを定義し、ここで、iは1からN-1まで広がっている。ラティスの各レベルは次の層のための基礎の役割を果たす。さらに、次数の全グラフラティスを作ることは、各図形の接合点およびすべてのサブグラフを含むすべての可能な図形の空間に対する抽象的表現を提供する。しかしながら、予想通りに、グラフラティスを完全に母集団化すると、次数は3を超えて桁はずれに大きくなる。この問題は下記の段落で検討されるであろう。ここでは、N個の接合点を含む単一の図形だけを表すグラフラティス、およびそのサブグラフのすべてについて検討する。この図形は次数Nのグラフラティス内の単一ノードを定義することになる。その結果、次数N-1では、図形はN-1ノードを有し、このN-1ノードのそれぞれは、その接合点のうちの1つがなくなった状態のサブグラフということになる。次数N-2のノード数は、図形のトポロジーに依存するであろう。したがって、グラフラティスは平らな基礎を有するひし形を形成し、ここで、基礎は原始要素を表す13のノードを含む。ひし形はN/2の周囲の層で通常最も広くなり、ここで、存在する接合点およびなくなった接合点のほとんどの組み合わせが生じる傾向があることになる。単一の図形に対するグラフラティス内のノード総数は約2N個である。グラフラティスの概念は直線的線画との関連で導入されたが、他の定式化も同様に受け入れられることを理解されたい。すなわち、グラフラティスの概念は画像特徴が原始要素の集合に分解できる他の領域にも適用できる。グラフラティスの生成と関連するいくつかの基本概念を導入した後に、グラフラティスを作るためのアルゴリズムを導入する。アルゴリズムは理論的グラフラティス全体の一部分だけを作ることによりグラフラティスの複雑さを管理し、このアルゴリズムは所与のデータコーパスおよび用途の集合に対して意味があり有用である。データコーパスはデータグラフの集合であり、各データグラフは画像に対応している。画像は、例えば、文書画像であり得る。上述のように、データグラフは原始要素を用いて画像を表し、データグラフ内のノードは原始要素に対応し、データグラフ内の縁端部は接合点の間の連結棒に対応している。直線的線画の場合、画像のデータグラフは、基準線を抽出して、それにより形成される接合点を決定することにより構成される。その後、これらの接合点はデータグラフのノードを定義し、これらのノードは、基準線により相互接続される。図5はグラフラティスを作るのに使用される概念を説明する例を示している。図5の2つの画像502、504のデータグラフに対してグラフラティスを作ることが好ましいことと、各画像のデータグラフがN個の接合点を含むこととを仮定する。上述のように、N>3のとき、完全に母集団化されたグラフラティスを作るのは一般に非現実的である。この問題に対処するために、グラフラティスは画像502、504の両方のデータグラフ内に見つけられるサブグラフ506、508のようなサブグラフとともに母集団化されるだけである。より低いレベル次数のグラフラティスノードは、より高いレベルのグラフラティスノードのサブグラフであってもよい。複雑さを限定するために、グラフラティスノード3個の間の親子関係だけが保持される。これらの3個はレベルN親のノードと、原始要素技術的には第2の親と、親グラフラティスノードのサブグラフに、その周辺子に結び付けられた原始要素を加えたもので構成されるサブグラフであるレベルN1のノードと、で構成される。この三方向の関係が、ストラットと呼ばれるデータ構造内で保持される。ストラットの目的は2つである。第1に、ストラットは親グラフラティスノードと子グラフラティスノードの間の接合点インデックスマッピングを保持する。一般に、任意のグラフラティスノードは、その構成要素接合点に順序不同にインデックスを付けるであろう。ストラットは、それらを親グラフラティスノードと子グラフラティスノードの間で系統的に整理された状態に保持する。第2に、ストラットはプリミティブ型、親の配置、および親から子を作る接合点に対する連結棒を示す。図6はストラットの概念を示している。ストラットは、その構成グラフラティスノードへのポインタを保持し、これらのノードは、それらを接続するすべてのストラットへの連結棒を保持する。ストラットは、S{A,p,i,B,M,L}と表され、ここで、Aは親グラフラティスノードであり、pは子を生成するために親に付加された原始要素の種類であり、iはこの原始要素の子サブグラフ内でのインデックスであり、Bは子サブグラフグラフラティスノードであり、Mは親接合点インデックスと子接合点インデックスの間のマッピングであり、Lは子サブグラフを生成するための原始要素の親との連関である。Lは、付加された原始要素に関する方向インデックスから、子のノードインデックスへマッピングする。グラフラティスノードは、それらが関与するストラットのリストを保持する。しかしながら、特定の実施形態では、原始要素は節約のためにこれらのリストを保持していない。このような実施形態では、原始要素はストラットのリストだけを保持しており、ここで、両方の親は原始要素であり、子は次数2のグラフラティスノードである。各グラフラティスノードはそれ自体がサブグラフである。したがって、ノードは、グラフラティスノードのサブグラフ接合点を、対応するデータグラフ接合点にマッピングすることにより、観察されるデータグラフと照合できる。原始要素は分類されるため、この照合は属性サブグラフマッチングのための任意の公知アルゴリズムを用いて実行できる。図7は実施例データグラフとグラフラティスノードのサブグラフの間の、結果として生じるマッピングを示している。一般に、このようなマッピングは一対多数になるであろうすなわち、グラフラティスノードで表される単一のサブグラフは、観察されるデータグラフの複数の部分にマッピングしてもよい。マッピングは本明細書でマッピングセットMappingSetと呼ぶデータ構造内に保持される。マッピングセットは{グラフラティスノード、データグラフIDDataGraphID、マッピングリストlist-of-Mappings}の3要素で構成されている。データグラフIDは、データグラフおよびデータグラフの関連する原画像例えば、ファイル名などへのポインタである。マッピングリストはマッピングのリストであり、このリストのそれぞれは{順マッピング配列、逆マッピング配列}の対である。順マッピング配列はグラフラティスノードの次数に等しい大きさを有する配列である。この配列はグラフラティスノードのサブグラフのノードインデックスから、データグラフ内のノードのインデックス上にマッピングする。逆マッピング配列は、データグラフのノードインデックスから、グラフラティスノードにおいて表されるサブグラフのノードインデックスへマッピングする配列またはハッシュ表である。データグラフは非常に大きくなると予想されるため、データグラフの大きさに等しい長さを有する配列の代わりに、ハッシュ表衝突検出を備えたとして逆マッピングを保存することの方が、より空間効率が良い。各グラフラティスノードはマッピングセットと呼ばれるリストを保持する。これらのマッピングセットは、グラフラティスノードのサブグラフがマッピングされているデータグラフ上に身元および位置を記録する。したがって、各グラフラティスノードは、そのグラフラティスノードのサブグラフがマッピングされている各データグラフに対するマッピングセットを含んでいる。常に、承認済みグラフラティスノードのリスト、および候補グラフラティスノードのリストが保持されている。これらのリストの目的についてはさらに詳細に後述するが、簡潔に述べると、承認済みグラフラティスノードはグラフラティスに付加されたノードであり、候補グラフラティスノードはグラフラティスノードへの付加を現在検討しているノードである。開始状態として、原始要素のリストが承認済みグラフラティスノードに使用され、空集合が最初の候補グラフラティスノードに使用される。さらに、候補および承認済みグラフラティスノードの集合は、次数原始要素の個数によりインデックスを付けられた配列で構成されるデータ構造内にそれぞれ保持されている。この配列の各要素は、原始要素の個数の組み合わせによりインデックスを付けられたハッシュ表で構成されている。例えば、ハッシュインデックスは、各原始要素とデータグラフとが一致した回数を数える数字から連結された文字列に関してJavaハッシング関数を用いて計算してもよい。このデータ構造の目的は、重複したグラフラティスノードを効率的に検出できるようにすることである。特定の実施形態では、それぞれの承認済みおよび候補グラフラティスノードは、それが作られた原始要素の個数のカウントを保持して、次数によるインデックス付けをより効率的に促進するようにしている。グラフラティスノードの原始要素のカウントは、グラフラティスノードの次数またはレベルに対応している。グラフラティスを生成するためのアルゴリズムを図8に示している。アルゴリズムは入力としてデータ見本の集合を取り込み、これらのデータ見本のそれぞれは原始要素と原始要素の間の関係を示す連結棒とを示すノードで構成されるデータグラフである。これらの見本により、データ見本にマッピングできるサブグラフを単に生成するだけで、グラフラティスを手元で使用する形にすることが辛うじて可能になる。アルゴリズムは、候補グラフラティスノードを生成すること動作802、候補グラフラティスノードを選択すること動作804、選択されたグラフラティスノードを昇格させること動作806、および終了条件が満たされるまで繰り返すこと動作808を含んでいる。候補グラフラティスノードは、承認済みグラフラティスノードおよび観察されるデータグラフからラティス生成されるアクション802。概要の方法では、承認済みグラフラティスノードの、観察されるデータグラフ上へのマッピングは調査され、新しい候補グラフラティスノードを生み出すために使用される。観察されるデータグラフは、以前に見られたデータグラフ、および/または新しく、新規で、以前には観察されていないデータグラフを含んでいてもよい。上述のように、承認済みグラフラティスノードは、最初は原始要素のリストを含む。候補グラフラティスノードを生成する第1のステップは、次数Nの承認済みグラフラティスノードの拡張を生成することである。レベルNのグラフラティスノードの、観察されるデータグラフ上へのあらゆるマッピングは、新しいレベルN1のグラフラティスノードを生み出すための種としての役割を果たすことができ、この新しいレベルN1のグラフラティスノードは、そのレベルNのグラフラティスノードで表されるサブグラフのスーパーグラフである。サブグラフの周辺に結び付けられた各原始要素は、それ自体がサブグラフの大きさをノード1つだけ大きくし、したがって、グラフラティスにおいて次数レベル1だけ高くすることができ、これ以降はグラフラティスノードの拡張と呼ばれる。図9を参照すると、この概念を示している。そのとき、種グラフラティスノード902が使用され4種類の拡張904a~904dを生み出される。この実施例では、各拡張の次数は6であり、種グラフラティスノードの次数よりも1だけ高い。さらに、各拡張は観察されるデータグラフ906の中に見られる。あらゆるレベルNの承認済みグラフラティスノードにより生成された各拡張は、新しいレベルN1の候補グラフラティスノードとして追加される前に、レベルN1の既存のグラフラティスと比較されて、各拡張が既存の承認済みまたは候補グラフラティスノードと重複していないことが確認される。この重複検査は、上述したグラフラティスノードのハッシュ表インデックス付けにより促進される。実際のグラフマッチングにより比較されなければならない、同じ可能性のあるレベルN1のグラフラティスノードの集合は、ハッシュ表を通じて、ほんの少数の候補グラフラティスノードに絞られる。拡張が重複していないことが分かったとき、拡張はレベルN1の候補グラフラティスノードのリストおよびハッシュ表に追加される。その後、それぞれの新しい候補グラフラティスノードは、また、それがマッピングするデータグラフに、ストラットを通じて結び付けられる。この新しい候補グラフラティスノードを、そのレベルの親および関連する原始要素と結び付けるストラットは明らかである。しかしながら、グラフラティスのラティス特徴のために、他のレベルのグラフラティスノードもまた、新しい拡張のサブグラフであってもよい。これらの関係に対するストラットもまた、形成されなければならない。候補グラフラティスノードが生成されると動作802、承認済みグラフラティスノードに昇格させるために候補グラフラティスノードの一部を選択する動作804。一般に、目標は、付加されたノードがクラスタリング、分類、反復構造検出、またはグラフラティスの他の応用の目的を果たすようにグラフラティスを大きく育てることである。候補グラフラティスノードを選択するための1つの方法は、最大ノード種別多様性基準である。この方法のランクは、すべての候補グラフラティスノードを、ノードnに対する原始的ノード種別iのエントロピーHnとして測定されるプリミティブ型の多様性に従って順序付ける。ここで、ciはグラフラティスノードnで使用される種類iの原始要素の個数のカウントである。ノード種別多様性基準は多くの異なる種類の接合点を含むノードを含むグラフラティスを大きく育てることに通じ、これらのグラフラティスはクラスタリングおよび分類の観点から見てデータグラフの中で多くの場合最も特徴的なサブグラフである。また、他の選択基準も可能である。次に、以前に選択された候補グラフラティスノード動作804を承認済みグラフラティスノードに昇格させる動作806。承認されたステータスを獲得することにより、グラフラティスノードは新しい候補グラフラティスノードの種としての役割を果たす資格がある。候補グラフラティスノードを昇格させた動作806後、アルゴリズムは終了条件が満たされるまで繰り返される動作808。次数Nの新しく昇格したグラフラティスノードは観察されるデータグラフに対するマッピングを既に参照しているため、繰り返しはわずかである。その後、これらのマッピングは昇格したグラフラティスノードの子を捜すために容易に追跡調査され、これらの子は、まだレベルN1のグラフラティスノードで表されていないデータサンプル内で観察されるサブグラフを表している。可能な終了条件は下記の5項目を含むが、これらに限らない。i.所与のレベルにおける承認済みグラフラティスノードのしきい値個数を含むグラフラティス。ii.すべての承認済みグラフラティスノードのしきい値個数を含むグラフラティス。iii.使い尽くされている候補グラフラティスノードのリスト。iv.候補グラフラティスノードに対する品質測定がしきい値を下回る。v.決定された時間を超える実行時間。特定の実施形態では、終了条件は動作804で検討される採用戦略に依存している。データグラフを作るための上述のアルゴリズムにかかわらず、他のアルゴリズムも同様に受け入れられることを理解されたい。例えば、1つのアイデアは、ノード種別多様性のエントロピーに基づく尺度を用いて、強く示唆される候補グラフラティスノードを選択することである。グラフラティスを用いて実行する演算は、1つ以上の画像から導出される観察されたデータグラフに対するマッピングを計算することである。グラフラティスは非常に大きくなる可能性がある数千または数十万のノードを含んでいるため、この計算を効率的に行うことは重要である。単純素朴な方法は、観察されるデータグラフと、各グラフラティスノードのサブグラフの間で別々にサブグラフマッチングを実行することである。しかしながら、グラフラティスノードの間の関係におけるラティス構造を利用する、より効率的なアルゴリズムについて後述する。図10は、入力としてデータグラフを取り込み、グラフラティスノードで表されるサブグラフから、データグラフ上へのすべてのマッピングを記述するマッピングセットの編集物を出力するマッピングを計算するためのアルゴリズムを示している。アルゴリズムは、原始要素とデータグラフのノードとの一致を計算すること動作1002と、次数2のサブグラフとデータグラフとの一致を計算すること動作1004と、次数3およびより高次のサブグラフの一致を繰り返して計算すること動作1006とを含んでいる。まず、次数1のサブグラフはデータグラフと照合される動作1002。サブグラフは、グラフラティスノードのサブグラフ接合点を、対応するデータグラフ接合点にマッピングすることにより、観察されるデータグラフと照合され得る。次数1のサブグラフは照合された動作1002後に、次数2のサブグラフがデータグラフにマッピングされる動作1004。原始要素AおよびBの各対に対して、それらがレベル2のグラフラティスノードc1,c2,...,cNに対する1つ以上のストラットの親であるかどうかを判断する。それらがc1,c2,...,cNに対する1つ以上のストラットの親であると判断された場合、アルゴリズムはAの、データグラフ上へのすべてのマッピングを繰り返し適用して、ciが有効なマッピングであるかどうかを判断する。ciが有効なマッピングであるかどうかの判断は、そのマッピングに対するAの適正な近さにおける原始要素Bへの連結棒の存在についてデータグラフを試験することにより実行される。次数2のサブグラフをデータグラフにマッピングした動作1004が、レベル3およびより高レベルのマッピングは、レベル3のグラフラティスノードから始めて繰り返し計算される。レベルNの各グラフラティスノードRN=3から始まるに対して、アルゴリズムは前のレベルの親ノードAに対する1つのストラットSを選択する。レベルNのマッピングを見つけるためには、ノードのレベルN-1のサブグラフのすべてをマッピングすることになるため、1つのストラットを考慮することだけが必要である。その後、ストラットSに関連するレベルN-1の親ノードAに対して、アルゴリズムは、その親ノードAの、データグラフ上へのマッピングのそれぞれを繰り返すとともに、それぞれのこのようなマッピングに対して、アルゴリズムは、ストラットSにより示される原始要素pもまたデータグラフ上に存在しているかどうか、およびストラットSにより示される原始要素pが、ストラットの連関パラメータLで示されるように結び付けられているかどうかを調べる。この原始要素が存在しており、適切に結び付けられている場合には、Bへのマッピングが確立され得る。この手順の複雑さはグラフラティス内の親子ストラットの個数の増加とともに直線的に増大し、グラフラティスノードとデータグラフの間のマッピングの個数の増加とともに直線的に増大する。重要な点は、各レベルにおいて、すべてのマッピングが前のレベルで見つかるマッピングに対する漸進的拡張であるため、マッピングを計算するには少しの仕事だけが必要であるという点である。図11を参照すると、照合アルゴリズムの基礎となる概念を示している。すなわち、レベルN1のグラフラティスノードBの、データグラフへのマッピングは、そのグラフラティスノードBのレベルNの親グラフラティスノードの、データグラフへのマッピングから、ほとんどの場合引き継がれる。その後、AからBへのストラットは、原始要素pB上のインデックス5の存在についてデータグラフ上のどこで試験すればよいのかを示している。したがって、照合アルゴリズムは漸進的マッピングを経験する。グラフラティスの枠組みは、文書認識におけるいくつかの重要な用途、およびコンピュータビジョンの他の態様を支持する。しかしながら、これらについて説明する前に、グラフラティスマッピングに基づく特徴ベクトル、および妥当な特徴ベクトル類似性尺度について説明する。グラフラティス表現のいくつかの使用は、グラフラティスから、観察されるデータグラフへのマッピングに基づく特徴ベクトルを計算することを含んでいる。各グラフラティスノードはベクトルの1つの要素を含んでおり、その要素に対するベクトル入力は、そのグラフラティスノードのサブグラフの、データグラフ上へのマッピングの個数から導出される。試験は、純粋なまたはきちんとしたマッピングカウントをその要素にもつ特徴ベクトルは、線画クラスタリングおよび分類に対してうまく機能しないことを示している。その理由は、より大きなサブグラフが多過ぎることと関係している。より大きなサブグラフ特徴に対しては、非常に重複の多いサブグラフを非常に多く照合する。データグラフ内の任意のノード線画接合点は、低次のサブグラフよりもはるかに多くの高次のサブグラフに関与するであろう。このことは、原始的接合点を検出する際のエラーがたとえ少数であったとしても、結果として多数のマッチカウントの不安定性を引き起こす。図12では、丸を付けた接合点1202が、図示のサブグラフ1204に、より多くの図示していないサブグラフを加えたものを用いてマッピングすることにより重ね合わせる方法で覆われている。上述のように、このような重ね合わせにより、接合点または領域がマッピングカウント特徴ベクトルにおいて不規則に表されるようになる。これを解決するために、接合点規格化マッピングカウントJNMCに基づく特徴ベクトルを使用する。接合点規格化マッピングカウントはレベル当たりで計算される。言い換えれば、ある特定のレベルのノードに対するグラフラティスノードマッピングmiのすべてを計算し、これらを使用して、そのレベルのすべてのノードに対するマッピングカウントが規格化される。各レベルのマッピングに対するマッピングカウントが互いに別々に規格化される。レベルLに対して、観察されるデータグラフ内の各接合点jに対して重み付けWjを計算する。ここで、Njは、接合点jを含むレベルLのすべてのノードからのマッピングの個数である。その後、グラフラティスノードiに対する接合点規格化マッピングカウント要素Ciは下記の式で表される。ここで、miはグラフラティスノードiによる、観察されるデータグラフ上へのマッピングの集合である。言い換えれば、所与のグラフラティスノードに対応する接合点規格化カウントベクトル要素は、そのグラフラティスノードによりマッピングされ、そのグラフラティスノードの、観察されるデータグラフ上へのすべてのマッピングにわたって合計される、すべての接合点に対する接合点重みの合計とみなされる。接合点規格化マッピングカウントは、グラフラティスノードで表されるサブグラフのマッピングのカウントの特徴ベクトルの構築に向けて、観察されるデータグラフ内の各接合点に均等な重みを与える働きをする。上述の式を通じて、これらの重みは各接合点を含むマッピングの間に分配される。接合点が1回または数回だけマッピングされる場合、接合点はカウントに対して強く寄与する。他方、接合点が多くの重複マッピングにより覆われている場合、これらのマッピングは、その接合点の寄与重みをすべて共有しなければならない。接合点規格化式は、いくつかのグラフラティスノードがたまたま多くの重複マッピングを有するときに、それらが特徴ベクトルを支配するのを防止するが、このような状況は反復構造がある場合に起こる可能性がある。クラスタリングおよび分類を行うためにデータに対する特徴ベクトル表現を比較することは標準的技法である。類似性/相違点スコアを出すために異なる式が使用されてもよい。当然の選択としてはユークリッド距離およびコサイン距離などがある。これらの選択のどちらも、有効に働くかどうか分かっていない。例えば、コサイン距離は、サブグラフの、観察されるデータグラフ上へのマッピングのカウントから導出された特徴ベクトルを比較する場合には有効に働かない。したがって、共通マイナス差CMDと呼ばれる下記の類似性尺度が使用される。ここで、Gkはデータグラフkの大きさ接合点の個数であり、Nは接合点規格化特徴ベクトル内で考慮されるサブグラフサイズの個数である。よく知られているコサイン距離は、ベクトル要素の分布または相対値を比較するように設計されており、他方、CMD距離はまた、絶対的な大きさを要素ごとに比較する。コサイン距離は特徴要素の、ともに正のカウントを有する任意の対にクレジットを与え、他方、CMDの挙動は、より正確である。カウントが似ている限り、正のクレジットが与えられ、カウントが異なる限り、負のクレジットが与えられる。現在比較しているデータグラフの大きさに基づく規格化条件により、CMD類似性尺度の範囲は-2最小、最低の類似性~1最大、最高の類似性である。上述の議論で開示した発明の要旨の有用な応用は画像クラスタリングである。画像クラスタリングは、文書画像に対する良好な画像クラスタリングを実現するために、グラフラティス表現、サブグラフマッピング、接合点規格化マッピングカウントベクトル、および共通マイナス差の類似性尺度を使用する。接合点規格化マッピングカウントおよびCMDの下で、試験は、より高次のサブグラフ特徴は判別の向上をもたらすことを示している。画像をクラスタ化するために、単純欲張りクラスタ化アルゴリズムを使用できる。欲張りクラスタ化アルゴリズムの下で、明確に同一のクラスタのしきい値および明確に異なるクラスタのしきい値の2つのしきい値を設定する。これらのしきい値は手動で設定してもよく、画像の代表的サンプリングに対する、対をなすCMD距離のヒストグラムから自動的に推定してもよい。アルゴリズムは入力としてクラスタ化される予定の画像のコーパスを取り込む。コーパス内の各画像に対して、アルゴリズムは最良適合クラスタを見つける。その画像と、既にクラスタの要素である画像との間の最良スコアが、画像に対する最良適合クラスタを決定する。これは、最近傍に基づいて、または要素をカテゴリにサンプリングする最良スコアに基づいて、画像をカテゴリに割り当てる画像分類プロセスに相当する。最良スコアは、接合点規格化マッピングカウントを用いて決定される特徴ベクトルに関するCMDを用いて決定される。画像に対する最良適合クラスタを見つけた後に、画像を分類する。最良適合クラスタと画像との類似性が、明確に同一のクラスタのしきい値よりも大きいとき、画像は最良適合クラスタに加えられる。最良適合クラスタと画像との類似性が、明確に異なるクラスタのしきい値よりも小さいとき、画像は唯一の要素としてその画像を有する新しいクラスタに加えられる。最良適合クラスタの類似性が、明確に同一のクラスタのしきい値と、明確に異なるクラスタのしきい値の間にあるとき、画像は未確定のカテゴリに入れられて、すべての画像を検討し終わるまで棚上げにされる。コーパス内のすべての画像が分類されると、それぞれの未確定画像が再び取り上げられる。特定の実施形態では、未確定画像は、それらの最良適合クラスタに割り当てられる。他の実施形態では、上述のように未確定画像を既存のクラスタに加えることを試みる。このような実施形態の下で、明確に同一のクラスタのしきい値を超えることができない任意の画像は余りと呼ばれる新しいクラスタに加えられる。欲張りクラスタ化アルゴリズムは、スキャナで取り込まれた手書きのおよびタイプされた米国納税申告書を代表する、大きさ2560x3300画素の11,185枚の画像で構成された米国標準技術局NIST納税申告書のデータコーパスで試験された。大きさ1~3または1~4のサブグラフを含む特徴ベクトルを用いて、クラスタ化アルゴリズムは、1つのカテゴリを2つに分けながら、すべての11,185枚のNIST画像を、それらのそれぞれの20のカテゴリに正確に分類した。図13はサブグラフサイズが最大4までの特徴ベクトルを用いて200のNIST文書の、対をなす類似性ヒストグラムを示している。NISTデータに対して、サブグラフ特徴サイズが2を超えると、異なる画像カテゴリが明確に分離される。最終的に、クラスタリング結果を図14に示している。クラスタリングの品質は、画像をカテゴリにグラウンドトルースに正しく割り当てるまでの編集距離として記録される。間違って分類されたそれぞれの文書に対して1つの編集操作が記録され、同じグラウンドトルースにカテゴリを表す任意の2つのクラスタを1つにまとめるために1つの編集操作が記録される。唯一のエラーはグラウンドトルースにカテゴリのうちの1つを複製する付加的なクラスタであるため、帳票クラスタリングおよび分類は、大きさ3以上のサブグラフに対してほぼ100正確である。欲張りクラスタ化アルゴリズムについて上述したが、本明細書に開示する概念を基礎とする他のクラスタ化アルゴリズムも同様に受け入れられる。上述の議論で開示した発明の要旨の他の有用な応用は画像分類である。画像分類は、グラフラティス表現、サブグラフマッピング、接合点規格化マッピングカウントベクトル、および共通マイナス差を使用する。画像分類は、分類に対する各カテゴリの1つ以上の見本の使用を通じてクラスタリングと同じように実行できる。すなわち、分類する予定の各画像に対して、アルゴリズムは見本の最良適合群を見つけ、画像と見本の間の最良スコアが最良適合群を決定する。上述のように、最良スコアは、接合点規格化マッピングカウントを用いて決定される特徴ベクトルに関するCMDを用いて決定される。グラフラティスは高速画像蓄積および検索の基礎としての役割を果たすことができる。グラフラティスの、観察されるデータグラフ上への照合は、グラフラティスノードのサブグラフの、データグラフのサブグラフ上へのマッピングのマッピングセットを作ることを含む。これらのマッピングはマッピングの身元および配置を記録する。新しい画像が観察されると、各グラフラティスノードによりマッピングされた、したがって、一般的構造を共有する他の画像は、これらのマッピングから取り出される。雑音およびサンプル変化に起因するような不完全なデータグラフの条件下で、目標と共通して多くのサブグラフを共有する観察されるサンプルから画像を選択するために公知の投票方法を使用できる。グラフラティスは画像の中の反復構造を検出する基盤としての役割を果たすことができる。グラフラティスの、観察されるデータグラフ上への照合は、グラフラティスノードのサブグラフの、データグラフのサブグラフ上へのマッピングのマッピングセットを作ることを含む。同じ画像の異なる領域への複数のマッピングは、その画像内の反復構造を示している。多くの重複サブグラフは、単に反復部分についての人間の直観に対応するサブグラフではなく、繰り返されることが分かっている。図15では、反復構造は、1周期的反復構造、および2孤立反復構造の2つの大きなカテゴリで生じる。周期的反復構造図15のaは、反復構造領域がそれ自体とともに境界を共有するときに生じる。これは、反復パターンの境界を定義する際に、エイリアシングまたは位相アンビギュイティの問題を引き起こす。孤立反復構造図15のbは、反復領域を囲む材料が、反復領域の1つの例とその隣の例とで全般的に異なっているときに生じる。重複のない目標ノードで表されるサブグラフに正確にR回マッピングするレベルL/Rのグラフラティスノードが存在するときには、レベルLのグラフラティスノードはR回反復される構造を表している。このような反復ノードは各レベルLで各ノードを順々に試験することにより検出できる。目標ノードで表されるサブグラフが形成され、その後、サブグラフマッチング用の単純アルゴリズムを使用してレベルL/Rの候補ノードを一度に1つずつ照合する。候補ノードが正確にRマッピングを有しているとき、目標サブグラフの各接合点がRマッピングにより正確に1回マッピングされるかどうかを判断する。目標サブグラフの各接合点がRマッピングにより正確に1回マッピングされると判断された場合、目標レベルノードは反復構造ノードであり、それが含む反復構造は候補レベルL/Rノードで表される。この方法は、棒グラフで大きさが最大6の接合点までの反復構造を検出することが試験され示されている。図16では、グラフラティスシステム1600を示している。記憶装置と、マイクロプロセッサ、マイクロコントローラ、映像処理装置GPUなどのデジタル/電子プロセッサと、を含むコンピュータ1602または他のデジタル/電子制御演算装置がシステム1600を具現化することがふさわしい。他の実施形態では、システム1600はデジタルプロセッサを含み、デジタルデータ記憶装置を含むか、もしくはデジタルデータ記憶装置にアクセスできるサーバにより具現化され、このようなサーバはインターネットもしくはローカルエリアネットワークを介してアクセスされることがふさわしく、またはシステム1600はデジタルプロセッサおよびデジタルデータ記憶装置などを含む携帯情報端末PDAにより具現化される。コンピュータ1602または他のデジタル制御演算装置は、制御システム1600へのユーザ入力を受信するキーボード1604のような1つ以上のユーザ入力装置を含み、またはこのような1つ以上のユーザ入力装置と動作的に接続されていることがふさわしく、コンピュータ1602または他のデジタル処理装置は、システム1600の出力に基づいて生成された出力を表示する表示部1606のような1つ以上の表示装置をさらに含み、またはこのような1つ以上のユーザ入力装置と動作的に接続されていることがふさわしい。他の実施形態では、制御システム1600に対する入力は、コンピュータ1602上のシステム1600に先立って起動している、もしくはシステム1600と同時に起動している他のプログラムから受信し、またはネットワーク接続などから受信する。同様に、他の実施形態では、出力はコンピュータ上のシステム1600の後で起動している、もしくはシステム1600と同時に起動している他のプログラムへの入力としての役割を果たしてもよく、またはネットワーク接続などを介して伝達されてもよい。システム1600は、本願のグラフラティスの1つ以上の態様を実現するグラフラティスモジュール1608と、グラフラティスを用いる方法および/またはアルゴリズムとを含んでいる。特定の実施形態では、グラフラティスモジュール1608はモジュール1608の外部のソースから1つ以上の画像のコーパスを受信し、コーパスからグラフラティスを生成する。このような実施形態の一部では、グラフラティスモジュール1608は目標画像をさらに受信し、この目標画像はグラフラティスモジュール1608がコーパスから類似画像を取り出すために使用する。このような実施形態のその他では、グラフラティスモジュールは画像のコーパス上でクラスタ化を実行し、および/またはコーパスの中の反復サブグラフを特定する。いくつかの実施形態では、グラフラティスモジュール1608は、実行可能命令を保存する記憶媒体により、例えば、デジタルプロセッサにより具現される。記憶媒体は、例えば、磁気ディスクもしくは他の磁気記憶媒体か、光ディスクもしくは他の光記憶媒体か、ランダムアクセスメモリRAM、読み出し専用メモリROM、もしくは他の電子メモリ素子もしくはチップもしくは動作的に相互接続したチップセットか、保存された命令をそこからインターネットもしくはローカルエリアネットワークを介して取り出してもよいインターネットサーバなどを含んでいてもよい。図17では、図16のグラフラティスシステム1600を用いるコンピュータビジョンシステム1700を示している。コンピュータビジョンシステム1700は、撮像装置1702と、図16のグラフラティスシステム1704と、を含んでいる。特定の実施形態では、コンピュータビジョンシステム1700は、例えば、通信ネットワークを経由してコンピュータビジョンシステム1704に動作的に接続された文書データベース1706をさらに含んでいる。文書データベース1706は文書画像のデータベースであり、文書画像は撮像装置1702のような装置を介して生成される。撮像装置1702は1つ以上の文書1708を受け取り、それらを文書画像1710に変換する。撮像装置はカメラ、スキャナ、または他の類似装置であってもよい。さらに、撮像装置1702は給紙トレイから延びるコンベヤ経路を介して文書を受け取ってもよい。その後、グラフラティスシステム1704は文書画像1710を受信し、それらを用いて1つ以上の作業を実行する。グラフラティスシステム1704は通信ネットワークを介して電子的に文書画像1710を受信してもよい。さらに、1つ以上の作業は、クラスタ化された文書画像1712を生成するために1つ以上のクラスタ化する文書画像1710を含み、文書データベース1706の中の類似文書画像1714を見つけ、文書画像1710の中の反復構造1716を見つけてもよい。図示の作業にかかわらず、グラフラティスシステム1704は、図示していない付加的な作業例えば、文書分類を実行できる。グラフラティスシステム1704を使用して、クラスタ化された文書画像1712を生成するシナリオの下で、第4.3項画像分類およびクラスタリングに関連して説明するように文書画像1710をクラスタ化して、クラスタ化された文書画像1712を定義する。すなわち、文書画像1710を比較するCMD類似性スコアが、文書画像1710のグラフラティスを用いて生成され、文書画像1710をクラスタ化するために使用される。グラフラティスシステム1704が文書画像1710をクラスタ化すると、必要に応じて文書1708および/または文書画像1710が処理される。例えば、文書1708は、それらのクラスタに基づいて目的地までコンベヤ経路を介して送ってもよい。あるいは、または加えて、文書画像1710は、それらのクラスタに従ってデータベース内に保存してもよく、および/またはファイルシステムの中に保存してもよい。グラフラティスシステム1704を使用して類似文書画像1714を見つけるシナリオの下で、文書画像1710を使用して文書データベース1706から類似文書画像1714を取り出す。これは画像インデキシング、記憶装置、および検索に関連して説明するように実行される。すなわち、文書データベース1706内の文書画像のグラフラティスを文書画像1710にマッピングする。その後、単純投票方法を使用して、文書画像1710と共通して最も多くの構造を有する、文書データベース1706内の文書画像を見つける。グラフラティスシステム1704が類似文書画像1714を見つけると、必要に応じてそれらの類似文書画像1714を処理してもよい。例えば、類似文書画像1714はデータベース内に保存してもよく、および/またはファイルシステムの中に保存してもよい。あるいは、または加えて、類似文書画像1714は表示部および/またはプリンタを介してコンピュータビジョンシステム1700のオペレータに提供してもよい。グラフラティスシステム1704を使用して反復構造1716を見つけるシナリオの下で、反復構造を探して文書画像1710を検索する。これは共通構造および反復構造の検出に関連して説明するように実行される。文書画像1710を使用してグラフラティスを生成し、その後、重複のない目標ノードで表されるサブグラフに正確にR回マッピングするレベルL/Rのグラフラティスノードが存在するときには、レベルLのグラフラティスノードはR回反復される構造を表しているという了解の下で、各レベルLで各ノードを順々に試験することにより反復ノードを検出する。グラフラティスシステム1704が反復構造1716を見つけると、必要に応じて反復構造を処理してもよい。例えば、反復構造は表示部および/またはプリンタを介してコンピュータビジョンシステム1700のオペレータに提供してもよい。グラフラティスおよびグラフラティスに適用するアルゴリズムは、画像クラスタリングの効率、精度、およびスケーラビリティと、分類と、類似の、および重複した画像インデキシングおよび検索と、反復構造検出とを促進する。効率は、グラフラティスの単純なパターンから、より複雑なパターンまでを作るサブグラフへのマッピングを計算するアルゴリズムから導出する。精度は、グラフラティス内のサブグラフの非常に大きな集合の保存によるグラフラティスの冗長性から導出する。スケーラビリティは、観察されるデータに合わせた大きなグラフラティスこのグラフラティスは、すべてのサブグラフの空間に比べれば、まだはるかに小さいを育てるように我々が開示するアルゴリズムから導出する。下記の変形は予測できると考えられる。vi.観察されるデータからグラフラティスを適応的に大きく育てる方法。特に重要な問題はグラフラティスの中に経路を深く延ばすことであり、その結果、より小さいサブグラフの急増にノードをささげることなく、大きなサブグラフを示す。これは、さらに耐雑音性を獲得するほど十分な冗長性を備えた上で、高レベルノードまで経路を選択的に延ばすことを意味している。vii.作業またはデータに依存する偶然性に従って、グラフラティスの、データ上へのマッピングを選択的に計算する方法。viii.クラスタ、反復構造、および例外的パターンを発見するためにデータサンプル上のグラフラティスのマッピングカウントを分析する方法。ix.埋め込み、カーネル法、および他の統計的パターン認識法に対して特徴ベクトルに関与するためにグラフラティスノードを選択する方法。"