【手続補正書】
【提出日】平成20年8月26日(2008.8.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
少なくとも１つのエンティティを含む少なくとも１つの入力を受け取る受信コンポーネントと、
同時セグメンテーション・認識プロセスを利用して前記入力中の前記エンティティを認識する認識コンポーネントと、
を備え、前記認識コンポーネントは、
前記受信コンポーネントからの入力を受信し、前記入力内で見つかったエンティティの近似グラフを構成する近傍グラフ生成器と、
前記近傍グラフ生成器から受信した近似グラフを接続された部分グラフに区分けする部分集合グループ化コンポーネントと、
各部分グラフの少なくとも１つのレンダリングされた画像を生成する画像レンダリングコンポーネントと、
前記レンダリングされた画像を処理することにより前記部分グラフを認識する分類器と
を含むことを特徴とする空間認識システム。
【請求項２】
請求項１に記載のシステムであって、前記入力は、Ｐ次元空間において存在する幾何学構造を含むことを特徴とするシステム。
【請求項３】
請求項２に記載のシステムであって、前記Ｐ次元空間は、１次元空間、２次元空間、および３次元空間からなるグループから選択される少なくとも１つを含むことを特徴とするシステム。
【請求項４】
請求項１に記載のシステムであって、前記認識コンポーネントは、ダイナミックプログラミングを用いて同時セグメンテーション・認識プロセスを容易にすることを特徴とするシステム。
【請求項５】
請求項１に記載のシステムであって、前記認識コンポーネントは、前後関係の情報を使って、同時セグメンテーション・認識プロセスを容易にすることを特徴とするシステム。
【請求項６】
請求項１に記載のシステムであって、前記認識コンポーネントは、ストローク特徴情報を利用して、同時セグメンテーション・認識プロセスを容易にすることを特徴とするシステム。
【請求項７】
請求項１に記載のシステムであって、前記エンティティは、テキストのエンティティとグラフィクスのエンティティとで構成されるグループから選択される少なくとも１つを含むことを特徴とするシステム。
【請求項８】
請求項１に記載のシステムであって、前記エンティティは、ストロークの集合および画素の集合からなるグループから選択される少なくとも１つを含むことを特徴とするシステム。
【請求項９】
請求項１に記載のシステムであって、前記入力は、時間における非線形シーケンスと空間における非線形シーケンスとで構成されるグループから選択される少なくとも１つを含むことを特徴とするシステム。
【請求項１０】
請求項１に記載のシステムであって、前記認識コンポーネントは、前記エンティティを認識するために、前記入力から得られる空間的キューを利用することを特徴とするシステム。
【請求項１１】
請求項１に記載のシステムであって、
入力からエンティティを特定するように前記認識コンポーネントを自動的にトレーニングするトレーニングコンポーネントをさらに備えることを特徴とするシステム。
【請求項１２】
請求項１１に記載のシステムであって、前記トレーニングコンポーネントは、機械学習を用いてセグメンテーションパラメータを解くことを特徴とするシステム。
【請求項１３】
請求項１に記載のシステムであって、前記エンティティは、等式に関する文字を含むことを特徴とするシステム。
【請求項１４】
請求項１３に記載のシステムであって、前記認識コンポーネントは、それが認識する前記文字に基づいて、前記等式の副次式を判断することを特徴とするシステム。
【請求項１５】
請求項１４に記載のシステムであって、前記認識コンポーネントは、前記判断された副次式に基づいて、前記等式を導き出すことを特徴とするシステム。
【請求項１６】
請求項１に記載のシステムであって、前記分類器は、不正確なセグメンテーションにペナルティを与える機能を学習する、トレーニング可能な分類器を含むことを特徴とするシステム。
【請求項１７】
請求項１に記載のシステムであって、
最適なセグメンテーションと認識を決定する最適化によって、前記セグメンテーション・認識プロセスを容易にする最適化コンポーネントをさらに備えることを特徴とするシステム。
【請求項１８】
請求項１７に記載のシステムであって、前記最適化は、コスト指向型検索方法を含むことを特徴とするシステム。
【請求項１９】
請求項１８に記載のシステムであって、前記コスト指向型検索方法は、Ａ−スター検索方法、最善優先検索方法、および分岐限定検索方法で構成されるグループから選択される少なくとも１つを含むことを特徴とするシステム。
【請求項２０】
請求項１７に記載のシステムであって、前記最適化は、ダイナミックプログラミングプロセスを利用する最適化を含むことを特徴とするシステム。
【請求項２１】
請求項１に記載のシステムであって、前記認識コンポーネントは、セグメンテーションにおける曖昧さを利用して認識を容易にすることを特徴とするシステム。
【請求項２２】
請求項１に記載のシステムであって、前記認識コンポーネントは、認識における曖昧さを利用してセグメンテーションを容易にすることを特徴とするシステム。
【請求項２３】
空間認識を容易にする方法であって、
少なくとも１つのＰ次元入力を受け取るステップと、
同時セグメンテーション・認識プロセスを使って前記入力中のエンティティを認識するステップと、
を備え、前記同時セグメンテーション・認識プロセスは、
近似グラフ内の前記入力のストロークを連結して、接続された部分グラフを形成するステップと、
前記近似グラフの前記接続されたサブグラフに亘って検索方法を適用して、最適な分解を決定するステップと、
少なくとも一部をレンダリングされたストロークの画像、ストロークの特徴および前後関係に基づいて、分類器の使用を通じて前記最適な分解を認識するステップと
を含むことを特徴とする方法。
【請求項２４】
請求項２３に記載の方法であって、前記Ｐ次元入力は、１次元入力、２次元入力、および３次元入力で構成されるグループから選択される少なくとも１つを含むことを特徴とする方法。
【請求項２５】
請求項２３に記載の方法であって、前記入力は、テキストの入力とグラフィクスの入力とで構成されるグループから選択される少なくとも１つを含むことを特徴とする方法。
【請求項２６】
請求項２３に記載の方法であって、前記入力は、光学的に認識可能なマークの集合と画素の集合とで構成されるグループから選択される少なくとも１つを含むことを特徴とする方法。
【請求項２７】
請求項２３に記載の方法であって、前記入力は、時間の非線形シーケンスと空間の非線形シーケンスとで構成されるグループから選択される少なくとも１つを含むことを特徴とする方法。
【請求項２８】
請求項２３に記載の方法であって、前記同時セグメンテーション・認識プロセスは、縮尺および回転不変空間認識プロセスを含むことを特徴とする方法。
【請求項２９】
請求項２３に記載の方法であって、前記ストロークを連結して部分グラフを作成するステップは、
近傍グラフＧ＝（Ｖ，Ｅ）（ただし、頂点Ｖはストロークに対応し、辺Ｅはストローク間の隣接関係に対応する）を構成するステップと、
幾何学的関係に基づいて頂点を連結するステップと、
接続された部分集合Ｖi（ただし、｜Ｖi｜≦Κ、Κは部分グラフの大きさを限定する閾値）を列挙するステップと、
を含むことを特徴とする方法。
【請求項３０】
請求項２３に記載の方法であって、
部分グラフの前後関係を判断するステップと、
前記接続された部分グラフの分類を容易にするために前記前後関係を利用するステップと、
をさらに備えることを特徴とする方法。
【請求項３１】
請求項２３に記載の方法であって、前記同時セグメンテーション・認識プロセスは、
トレーニング例の集合から前記分類器および／または分類パラメータを自動的に学習するステップをさらに含むことを特徴とする方法。
【請求項３２】
請求項２３に記載の方法であって、前記検索方法はコスト指向型検索方法を含むことを特徴とする方法。
【請求項３３】
請求項３２に記載の方法であって、前記コスト指向型検索方法は、Ａ−スター検索方法、最善優先検索方法、分岐限定検索方法で構成されるグループから選択される少なくとも１つを含むことを特徴とする方法。
【請求項３４】
請求項２３に記載の方法であって、前記検索方法は、
コスト最適化関数を利用してセグメンテーションおよび認識を容易にし、式（１）
Ｃ（｛Ｖi｝）＝Φ（Ｒ（Ｖ1），Ｒ（Ｖ2），…，Ｒ（Ｖn））            （式１）
（ただし、Ｖiは入力の分解を形成する頂点の部分集合、Ｒは前記頂点の集合についての最良の認識結果、関数Φは組み合わせコスト、Ｃは特定のグループ｛Ｖi｝を表す）
に従って最適なグループ化およびラベリングを判断するステップを含む最適化方法を用いることを特徴とする方法。
【請求項３５】
請求項２３に記載の方法であって、前記ストロークの特徴は、ストロークの曲率、ストロークの向き、ストロークの少なくとも１つの終点で構成されるグループから選択される少なくとも１つを含むことを特徴とする方法。
【請求項３６】
請求項２３に記載の方法であって、
前記接続された部分グラフを所定の固定サイズに限定するステップをさらに含むことを特徴とする方法。
【請求項３７】
請求項２３に記載の方法であって、前記最適な部分グラフを認識するステップは、
機械学習に基づく分析器を利用して有効および無効な部分グラフを区別するステップをさらに含むことを特徴とする方法。
【請求項３８】
請求項３７に記載の方法であって、前記機械学習に基づく分析器は、アダブースト、ニューラルネットワーク、サポートベクトルマシン、ベイズ式分類法で構成されるグループから選択される少なくとも１つを含むことを特徴とする方法。
【請求項３９】
請求項３７に記載の方法であって、
限定された深さの決定木を利用して、アダブーストに基づく認識方法を容易にするステップをさらに備えることを特徴とする方法。
【請求項４０】
請求項２３に記載の方法であって、前記最適な分解を認識するステップは、
有効な部分グラフの各々について、分解とラベルの有効性を提供するステップをさらに含むことを特徴とする方法。
【請求項４１】
請求項１に記載のシステムのコンピュータ実行可能なコンポーネントが記憶されたことを特徴とするコンピュータ読取可能記録媒体。
【請求項４２】
プロセッサにより実行されたときに、請求項２３に記載の方法を実施するコンピュータ実行可能命令を記憶したことを特徴とするコンピュータ読取可能記録媒体。