(57)【特許請求の範囲】
【請求項１】
複数の単語が手書きされた手書き文書中の単語を特定する方法であって、
単語が手書きされた文書が走査されて得られた画像内の単語において、該単語に属する単語内の区切れによって分離された単語の構成部分の境界を表す曲線を境界曲線と、
前記境界曲線上において、予め定められたしきい値により求められる角度を有するコーナーの位置を特徴点と、
前記境界曲線上の非同一直線上の３つの前記特徴点を第１の特徴点〜第３の特徴点と、
前記第１の特徴点から前記第２の特徴点及び前記第３の特徴点各々への２つのベクトルを用いて、該第１の特徴点から前記境界曲線上の複数の特徴点各々の位置までのベクトルを表すことにより求められる情報をアフィン座標という場合に、
ａ）コンピュータが、前記手書き文書が走査されて得られた文書画像内の各単語において前記境界曲線を抽出するステップと、
ｂ）前記コンピュータが、前記抽出された複数の境界曲線を、前記文書画像内の１つの単語に属する境界曲線の曲線グループにグループ化するステップと、
ｃ）前記コンピュータが、各曲線グループ内の各境界曲線上において、前記第１の特徴点〜前記第３の特徴点の組を複数組選択すると共に各組の該第１の特徴点〜該第３の特徴点を用いて各境界曲線上の複数の前記特徴点の前記アフィン座標を求め、各曲線グループの各境界曲線上の各特徴点における各組のアフィン座標の情報と、該各特徴点の前記文書画像上の位置の情報と、を対応させて構成される画像ハッシュテーブルを生成するステップと、
ｄ）前記コンピュータが、前記文書画像内の複数の単語からなる照会単語について前記ステップａ）及び前記ステップｂ）を行なうと共に、該ステップｂ）によって得られた各曲線グループ内の各境界曲線上において、前記第１の特徴点〜前記第３の特徴点の組を複数組選択すると共に各組の該第１の特徴点〜該第３の特徴点を用いて各境界曲線上の複数の前記特徴点の前記アフィン座標を求めることにより、各曲線グループの各境界曲線上の各特徴点における各組のアフィン座標の情報を求め、該照会単語について求められたアフィン座標の情報と、前記画像ハッシュテーブルと、に基づいて、前記画像ハッシュテーブルにおける各曲線グループの各境界曲線の各特徴点について、前記照会単語の各曲線グループの各境界曲線の各特徴点との各組のアフィン座標の一致度を表すヒストグラムを生成し、生成したヒストグラムのピークに基づいて、前記照会単語の候補の位置を見出し、
ｅ）前記コンピュータが、前記見出された前記候補の位置に前記照会単語を位置させて該照会単語の前記複数の特徴点の前記文書画像上の位置の近辺に、前記ステップｃ）における各曲線グループ内の各境界曲線上の各特徴点が位置するかどうかを検証して、前記照会単語と前記文書画像上の前記見出された前記候補の位置における単語との適合を調べるステップと、
を含む手書き文書中の単語を特定する方法。
【請求項２】
複数の単語が手書きされた手書き文書中の単語を特定する装置であって、
単語が手書きされた文書が走査されて得られた画像内の単語において、該単語に属する単語内の区切れによって分離された単語の構成部分の境界を表す曲線を境界曲線と、
前記境界曲線上において、予め定められたしきい値により求められる角度を有するコーナーの位置を特徴点と、
前記境界曲線上の非同一直線上の３つの前記特徴点を第１の特徴点〜第３の特徴点と、
前記第１の特徴点から前記第２の特徴点及び前記第３の特徴点各々への２つのベクトルを用いて、該第１の特徴点から前記境界曲線上の複数の特徴点各々の位置までのベクトルを表すことにより求められる情報をアフィン座標という場合に、
前記手書き文書が走査されて得られた文書画像の画像データを入力する入力手段と、
前記入力された画像データに基づいて、前記文書画像内の各単語において前記境界曲線を抽出する第１の抽出手段と、
前記第１の抽出手段により抽出された複数の境界曲線を、前記文書画像内の１つの単語に属する境界曲線の曲線グループにグループ化する第１のグループ化手段と、
前記第１のグループ化手段によりグループ化された各曲線グループ内の各境界曲線上において、前記第１の特徴点〜前記第３の特徴点の組を複数組選択すると共に各組の該第１の特徴点〜該第３の特徴点を用いて各境界曲線上の複数の前記特徴点の前記アフィン座標を求め、各曲線グループの各境界曲線上の各特徴点における各組のアフィン座標の情報と、該各特徴点の前記文書画像上の位置の情報と、を対応させて構成される画像ハッシュテーブルを生成する生成手段と、
前記文書画像内の複数の単語からなる照会単語おいて前記境界曲線を複数抽出する第２の抽出手段と、
前記第２の抽出手段により抽出された複数の境界曲線を、１つの単語に属する境界曲線の曲線グループにグループ化する第２のグループ化手段と、
前記第２のグループ化手段によりグループ化された各曲線グループ内の各境界曲線上において、前記第１の特徴点〜前記第３の特徴点の組を複数組選択すると共に各組の該第１の特徴点〜該第３の特徴点を用いて各境界曲線上の複数の前記特徴点の前記アフィン座標を求めることにより、各曲線グループの各境界曲線上の各特徴点における各組のアフィン座標の情報を求め、該照会単語について求められたアフィン座標の情報と、前記画像ハッシュテーブルと、に基づいて、前記画像ハッシュテーブルにおける各曲線グループの各境界曲線の各特徴点について、前記照会単語の各曲線グループの各境界曲線の各特徴点との各組のアフィン座標の一致度を表すヒストグラムを生成し、生成したヒストグラムのピークに基づいて、前記照会単語の候補の位置を見出す見出手段と、
前記見出された前記候補の位置に前記照会単語を位置させて該照会単語の前記複数の特徴点の前記文書画像上の位置の近辺に、前記生成手段により生成された各曲線グループ内の各境界曲線上の各特徴点が位置するかどうかを検証して、前記照会単語と前記文書画像上の前記見出された前記候補の位置における単語との適合を調べる検証調査手段と、
を備えた手書き文書中の単語を特定する装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、手書き文字の認識及び索引付けに関し、より詳細には、画像ハッシュテーブルを用いて手書きの単語を索引付けする手書き文字の局限（localization) 方法に関する。
【０００２】
【従来の技術】
手書き文書中の手書きの単語を検出し、認識する能力は、いくつかの用途にとって重要である。目下市販されている手書き認識製品がこのような能力を有することが商業戦略的に重要であることは明らかであり、デジタルライブラリー及びデジタル文書管理などの用途においては、上記能力の活用は無視することはできない。上記能力は、例えばデジタルライブラリーの場合、歴史的に価値のある書類を保存したり、該書類に記録された内容をデジタルデータに変換したりする業界に非常に関心が持たれている。図１に示す、系譜学の研究に使用される教会の記録の見本にみられるように、これらの文書は手書きで、装飾書体であることが多い。このような書類の内容のデジタルデータへの変換の重要な態様は、単語の照会（質問）に基づいたアクセスである。手書きキーワードの抽出及び索引付けは、手書きの注釈、工学図面上のマーク、メモ及び遺贈文書などの多様な不規則の紙文書の寄せ集めを処理する場合に、文書管理を行うための貴重な能力にもなりうる。
【０００３】
走査及びプリントされたテキスト文書の索引の生成の際に、テキストキーワードを抽出するためにＯＣＲアルゴリズムを使用することができるが、このような方法は、ロバストな手書き認識アルゴリズムがないため、まだ手書き文書のためのオプションにはならない。このような状況において代わりとなる方法は、ビットマップの特徴を抜粋したいくつかのフォームを記憶し、手書き単語の照会パターンを用いてこのような表現の内容を直接「索引付けする」ことによって、全体的な索引生成を防ぐ方法である。この方法でさえ、手書き単語の索引付けは、少なくとも２つの理由によってプリントされたテキストの索引付けよりもかなり複雑な問題となっている。第１に、文書が１人の著者によって書かれていても、同一の照会単語が文書の異なる位置で異なって書かれている場合がある。カーシブ（続け書き）書体の場合、これは、単語が、その著者に特徴的である単語内の区切れによって分離される単語セグメントの集まりとして書かれていることを意味することが多い。図２（Ａ）〜図２（Ｃ）はこの状況を示している。ここで "database" という単語は、この単語が書かれた様々な例において、図２（Ａ）〜図２（Ｃ）において点線で囲んで示したように、同一の著者であっても異なるように書かれている。更に、手書きテキストのラインはプリントテキストほど水平でないことが多いため、様々な例において様々な程度の全体的なスキュー（傾斜）が示される場合がある。第２に、照会単語と適合しそうな各単語の位置を細かく調べると計算が高価になり、このような文書の迅速な検索を妨げてしまう。
【０００４】
手書き単語を位置づける本発明の方法は、家系をたどるために古い装飾書体の手書きの教会記録文書の画像索引付けを必要とする用途が動機となった。図１に示すように、これらの文書は表状の（tabular)背景に対して書かれた。人物の名前に関する照会が与えられて、関連記録を位置づけることがタスクであった。これらの文書のための照会単語パターンの公式化は興味深い問題であるが、この開示のために、手書き単語がユーザによって公式化された後に手書き単語を整合する問題に焦点があてられる。これはおそらく、実際にタイプされたテキスト照会からこのようなパターン照会を生成するトレーニングプロセスによって得られるか、又はこのような照会は手書き文書そのものから得られる。
【０００５】
文書中の手書き単語パターンを局限する本発明の方法は、次のようなデータ構造を開発する。このデータ構造は、前処理ステップで生成される画像ハッシュテーブルと呼ばれ、文書を細かく探索せずに任意の単語を局限するのに必要な特徴情報を簡潔に表すためのものである。オブジェクト（目的とする単語）を局限するための画像ハッシュテーブルの使用は、幾何学ハッシングの次のような概念に成り立つ。即ち、この概念は、予めセグメント化された画像領域内でオブジェクトを識別するためのものであり、ラムダン（Y. Lamdan)及びウルフソン（H.J. Wolfson) の "Geometric hashing: A general and efficient model-based recognition scheme"(Proceeding of the International Conference on Computer Vision 、第238-249 頁、1988年）及び "Transformation invariant indexing"（Geometric Invariants in Computer Vision 、MIT プレス、第334-352 頁、1992年）という論説において述べられている。ツァイ（F.C.D. Tsai)の "Geometric hashing with line features"(Pattern Recognition 、第27巻、第３号、第377-389 頁、1994年）に述べられるように、ラインの特徴と共に使用するための基本的な幾何学ハッシングスキーム（理論大系）の拡張に更に多くの研究が行われている。幾何学ハッシングスキームの大規模な分析が、グリムソン（W.E.L. Grimson) 及びフッテンロッヒャー（D. Huttenlocher)の "Learning geometric hashingfunctions for model-based object recognition"(Proceedings International Conference on Computer Vision 、第543-548 頁、1995年）という論説において行われている。優れた幾何学ハッシュ関数の探究は、ビービス（G. Bebis) 、ジョージオポラス（M. Georgiopolous) 及びロボ（N. Lobo)の "Learning geometric hashing functions for model-based object recognition"(Proceedings International Conference on Computer Vision、第543-548 頁、1995年）という論説においても行われており、ハッシュテーブルを再ハッシングする概念を用いた拡張された幾何学ハッシングは、リグストス（I. Rigoustos) 及びハメル（R. Hummel)の "Massively parallel model matching: Geometric hashing on the connection machine"(IEEE Computer 、第33-41 頁、1992年２月）という論説において述べられている。従来の研究は全て、オブジェクト認識においてモデルの索引付けをするために幾何学ハッシング技術を用いており、ここでタスクは、モデルのライブラリーの中のどのモデルが画像内の示される領域に存在するかを決定することである。セグメント化されていない手書き文書中の手書き単語の局限は（モデルの索引付けではなく）画像の索引付けの一例であり、これに対して幾何学ハッシングを用いた従来の研究は存在しない。これに最も近い研究は、マンマサ（R. Manmatha)、ハン（C. Han) 及びライズマン（E. Riseman) の "Word spotting: A new approach to indexing handwriting"(Proceedings IEEE Computer Vision and Pattern Recognition Conference、第631-637 頁、1996年）という論説に述べられるように、手書き単語を局限するために画像の逐次探索を用いたものである。
【０００６】
【発明が解決しようとする課題】
本発明は、手書き文書中の手書き単語照会を位置づけし認識する方法である。手書き単語の索引付けを行う能力は、プリントテキスト文書と同様に手書き文書を処理可能にすることによって現行の文書管理システムの能力を拡張するだけでなく、手書き単語のトークン化によってこのような文書を圧縮する基礎となることが可能である。
【０００７】
【課題を解決するための手段】
手書き文書中の単語の局限には、文書中の任意の単語を位置づけするのに必要である必須情報を記録する、画像ハッシュテーブルと呼ばれるデータ構造を用いる。テーブル中の顕著なヒットが文書中の単語の位置の候補となるものを直接示し、よって細かい探索を避けるような方法で、文書中の特定の単語の局限又は索引付けは、その単語から得られる情報を用いてハッシュテーブルに索引付けをすることによって行われる。この方法は、１人の著者が異なる例（場所）において同一の単語を書く態様を表す、向き、スキュー及び単語内の区切れによる手書き単語の外観の変化を解決する。より具体的には、画像ハッシュテーブルにおける任意の単語の局限は、単語のパターンから計算された特徴を用いてハッシュテーブルに索引付けすることによって行われる。テーブル内の上部ヒットは、その単語を最も含みそうな位置の候補である。このような索引付けによってポーズ（pose) 情報を自動的に生じ、次にこれを用いて単語を示される位置に射影し（project)、検証する。検証には、その下にある単語と射影された単語との間の適合の程度を判断することが含まれる。画像ハッシュテーブルの生成及び索引付けには、２Ｄアフィン変換による単語の外観の変化、テキストのラインの向きの変化、文書全体のスキュー、閉塞（occlusion)、ノイズ又は１人の著者によって生じる単語内の筆跡の変化による単語の外観の変化が考慮される。
【０００８】
本発明の手書き単語の局限及び検出方法の詳細は、下記の発明の実施の形態において説明される。概して、この方法は次の４つの段階を含む：（１）単語を局限するための特徴を抽出する前処理段階；（２）画像ハッシュテーブルの構築段階；（３）照会単語の特徴を使用してハッシュテーブルを調べ、候補の位置を探索する索引付け段階；（４）照会単語を射影し、候補の位置においてその下にある単語と整合する検証段階。より具体的には、本発明は手書き文書中の単語を索引付けする方法であって、ａ）手書き文字を含む文書を前処理するステップを含み、ここで該文書に含まれる手書き単語から単語を局限（特定）するための特徴を抽出し、ｂ）幾何学情報を用いて該文書の該手書き単語を索引付けするための画像ハッシュテーブルを生成するステップを含み、ｃ）該ハッシュテーブルにおいて該手書き単語を索引付けするステップを含み、ここで照会単語から得られる上記特徴を使用して該ハッシュテーブル内で該照会単語に対応する手書き単語を探索して候補の位置を見出し、ｄ）前記見出された候補の位置に位置する単語に前記照会単語を重ね合わせかつ適合を調べることによって該ハッシュテーブル内の前記照会単語に対応する単語が登録されているか否かを検証するステップを含む。
【０００９】
開示される本発明の方法は、以下の利点を有する：１）テキストを細かくセグメント化せずに、手書き文書中の手書き単語のパターンを局限する迅速な方法である；２）１人の著者の筆跡の変化に対処する能力が、現行の筆跡認識研究よりも優れている；３）手書き文書よりもずっと広範囲の画像における任意の２Ｄ（リジッド）オブジェクトを局限し、検出する手段を提供する；４）速い探索及び検索が可能なデータベースにおいて文書（及び他の画像）を編成する手段を提供する。
【００１０】
【発明の実施の形態】
図３を参照すると、本発明のハッシュテーブル構築方法を行うための構成要素が示されている。本発明の前処理ステップでは、手書きページを高解像度（２００ｄｐｉ又はそれより多く）で走査することによって得られた原稿（文書画像１（ビットマップ上の））を使用する。特徴抽出モジュール２において、走査された文書画像１の連結成分領域が形成される。連結成分を見出す方法はいくつかあるが、下記のアルゴリズムを用いてビットマップ内の連結成分を決定する。即ち、描かれた単語部分に相当する連続領域（例えば、黒色部分）を決定する。
１．ランレングス（同じ文字列）のスタートポイント（開始点）及びエンドポイント（終了点）を保持するロー［ｉ］、ハイ［ｉ］アレイ（配列）を用いて、画像ピクセル１列当たりの「オン」ピクセル（背景が白であると仮定したときの黒色のピクセル）のランレングスを記録する。即ち、「オン」ピクセルの連続領域を抽出、記録する。
２．まず、全てのランレングスを、ランレングスｉに対してＣ＿｛ｉ｝で示される別個のグループに配置する。即ち、全てのランレングスを、各ランレングスを識別する度数Ｃ＿｛ｉ｝で識別する。
３．ロー［ｉ］及びハイ［ｉ］アレイの全てのエンドポイントピクセル（ｋ、ｌ）に対し、下記のステップを行う。
ステップＡ：「オン」のピクセルに隣接するピクセル（ｋ’、ｌ’）の数及びそれらに関連するランレングスを見出す。
ステップＢ：上で識別した隣接するランレングスと所与のランレングスをマージ（比較）する。これは、同一のグループ識別情報を有する全てのマージされた全てのランレングスを有することによって記録される。
【００１１】
上記アルゴリズムは、コーメン（Cormen) 、ライザーセン（Leisersen)及びリヴェスト（Rivest) による "Introduction to algorithms"(MIT プレス、1994) というタイトルの本で説明されたユニオン−ファインドデータ構造と呼ばれるデータ構造を用いて有効に実施でき、画像のランレングスの数の時間線形で実行することができる。
【００１２】
境界位置（ポイント）が、少なくとも１つの「オフ」隣接ピクセルを有するポイントとして、連結成分領域上で決定される。即ち、上記連続領域において隣接ピクセル位置を境界位置に決定する。このような境界ピクセルを巡回トレースして、連結成分領域の境界を表す曲線を得る。従来のライン−セグメント近似アルゴリズムを用いて、曲線を平滑にする。最後に、重大な湾曲偏差が生じるポイントであるコーナー特徴を上記曲線から抽出する。即ち、上記偏差が生じるコーナー特徴は、２本の付随するライン間の角度が特定のしきい値よりも大きい場合に生じる。本発明の特許請求の範囲に著しく影響を及ぼすものでなければ、他の曲線トレース方法及びコーナー特徴検出方法を使用してもよい。画像は高解像度で走査されるものと仮定されるため、ラインは十分太く、このような画像においてライン連結部分もコーナーとして示されることに注意する。特に閉塞及びノイズの存在下では全ての曲線が単一の単語からのものという訳ではないが、画像を横切ってランダムに選択された任意の３つの特徴よりも１本の曲線から生じる特徴は単一の画像の位置を示す可能性が高いという論理的根拠を用いて、１本の曲線上のコーナー特徴が局限の基本単位として選択される。
【００１３】
曲線抽出及び特徴生成の前処理ステップを、文書画像又は画像パターンとして表される照会単語に対して均一に行い、画像サイズの時間線形を行うことができる。
【００１４】
曲線グループの生成
異なる単語内間隔（単語の中にある異なる領域（例えば、白部))によって単語の外観が変化した筆跡（手書き文字）の局限を可能にするために、単語内の区切れ（単語の中にある異なる領域（例えば、白部))によって分離された曲線を曲線グループ生成モジュール３においてグループ化する。このようにグループ化された各グループは、同一単語に属する曲線の切片を有する。
【００１５】
手書きのページ画像のテキストのラインを検出することには、個々の単語領域のうちのどれが優勢的にテキストの認識可能なラインに沿って位置するかを決定することを含む。プリントされたテキストとは異なり、手書き文書のテキストのラインを推定することは難しい。何故なら、手書きのテキスト単語は直線で書かれていないことが多いからである。更に、テキストの連続的なラインはプリントされたテキストのように平行でない場合がある。最後に、著者は書いている間に単語内及び隣接する単語間の間隔を変える場合があり、そのために同一の単語でも異なる例（場所）によって書き方が違う場合がある。これにより、どの単語セグメントがグループに属するかを決定する処理が困難になる。
【００１６】
本明細書に開示されるテキストラインの検出方法は、ページの向きとは無関係に行われ、手書きテキストの個々のラインが平行であるとして行われない。更に、本方法を行う際は、全ての単語領域（単語の並ぶ方向）とテキストラインの向きとが一致するように調整されている必要もない。手書き文書のビットマップ画像に対して行う最初の操作は、図３の特徴抽出モジュール２を用いて画像の前処理を行い、暗領域（「オン」ピクセル）の連結成分（連続領域）を生成することである。暗領域は、単語セグメントと、このような連結領域の境界を示す曲線（境界線）とから構成される。また、この前処理段階は暗領域の重心を記録する。単語セグメント領域の向きは、暗領域の慣性モーメント軸の方向として決定する。慣性モーメント軸を見つけるための式は、ホーン（B.K.P. Horn)の "Robot Vision"(MIT プレス、1986）というタイトルの本の第３章に記されている。向きのヒストグラム（度数分布）を生成し、そのピークを自動的に選択して画像の主な単語の向きを表す。選択された優勢な向きの各々に対して、各領域の重心を通るように特定の向きのラインを引く。これらのラインのクラスタリングを行い、このようなラインのグループを決定する。バラード（D. Ballard) 及びブラウン（C. Brown) の "Computer Vision"(Prentice-Hall、第４章、第123-124 頁、1982年) というタイトルの本に述べられるハフ変換を使用して、この情報を記録した。ハフ変換テーブルと呼ばれる得られたデータ構造は、特定の向き及び位置のラインに沿って又はこれに近接して位置するポイント（ここでは領域の重心）の数を記録する２次元アレイである。このテーブルで値が最も高いエントリーは、テキストの候補のラインに一致すると考えられる。重心がピークのテーブルエントリーに貢献する領域に注釈を付ける。従って、これらの単語セグメント領域は、手書き文書画像のテキストのラインを形成するものと考えられる。
【００１７】
曲線グループは、同一単語の部分を形成する単語セグメントを有する。グルーピングにおいて、テキストのライン、従ってテキストのラインに沿って位置する単語セグメントが決定されると、距離によって分離され、単語内の区切れを特徴付ける全てのこのような単語セグメントがアセンブルされる。単語内の区切れは、以下のように判断される：上記に決定したテキストの各ライン毎に、ライン上に位置する単語セグメント領域の境界を使用して１つの領域当たり２つの極値ポイントを決定する；即ち、領域の全ての境界ポイントをラインの上に射影し、スタートポイント及びエンドポイントに注釈を付ける。所与のポイントをラインの上に射影することは、所与のラインを有する所与のポイントを通る垂直ラインの交差ポイントである。このような射影は全て、従来の分類アルゴリズムを用いて、ラインに沿って昇順に分類される。ある領域のエンドポイントと別の領域のスタートポイントとの間の距離には、単語セグメント間の区切れを表すように注釈が付けられる。これらの距離を、テキストの全てのラインに関して記録する。このような距離のヒストグラムを生成する。殆どの手書き文書の場合、このようなヒストグラムは少なくとも２つの顕著なピークを示す。最も小さな区切れの距離のピークには、単語内の区切れとして注釈を付ける。単語内の区切れを用いて、上記のように決定された単語内の区切れの一定の境界の距離だけテキストのラインの向きに沿って分離される単語セグメント領域をグルーピングすることにより、曲線グループを形成する。単語内の区切れ（+/- 選択されたしきい値）によって分離された曲線のグルーピングは、前述のユニオン−ファインドデータ構造を用いて行われる。
【００１８】
画像ハッシュテーブル
上記で得た特徴を用いて、画像ハッシュテーブルと呼ばれるデータ構造をハッシュテーブル構築モジュール４において展開し、これを用いて、手書きの照会単語の位置づけを促すように曲線グループ内の曲線の特徴の位置に関する情報を簡潔に表す。即ち、画像ハッシュテーブルは、上記曲線グループ内の曲線の特徴情報及び対応する画像上の位置情報を示すことが可能なものである。画像ハッシュテーブルの概念を理解するために、単純にするため各曲線グループが単一の曲線からなるものと想像する。タスクが、他の中でもこの曲線からなる画像に所与の照会曲線を位置づけることであると想像する。所与の照会曲線上には３つの連続する非同一直線上の特徴ポイント（Ｏ、Ｐ1 、Ｐ2 ）があると考える。これにより、曲線のあらゆる他のポイントＰの座標を、ポイント（Ｏ、Ｐ1 、Ｐ2 )(ベーストリプル（基礎となる３つのポイント）と呼ばれる）の座標によって下記のように表現できることが既知である。
ＯＰ＝αＯＰ1 ＋βＯＰ2 
【００１９】
座標（α、β）はアフィン座標と呼ばれ、これはアフィン変換に対して不変である。従って、スキューされた又は回転された画像に所与の曲線が表れた場合、変換された画像曲線上の対応ポイントは、変換された画像曲線内の変換されたベーストリプルと同一の座標を有する。よって、画像のある位置における曲線が所与の曲線に適合するか否かを調べる１つの方法は、画像曲線上の十分な特徴ポイントが画像曲線の画像ベーストリプルと同一のアフィン変換を有するかどうかを調べることである。この場合、画像曲線上のベーストリプル及び所与の（照会）曲線が一致すると言うこともできる。このような一致から、ポーズ情報をアフィン変換として下記のように得ることができる。
【００２０】
【数１】
0004308342.tif 000002
【００２１】
これは、下記のような連立方程式の集合を解決することによって得られる。
【数２】
0004308342.tif 000003
【００２２】
式中、（Ｏx 、Ｏy ) ＝０であり、ｘ及びｙは点Ｏのｘ座標及びｙ座標を示している。
【００２３】
画像ハッシュテーブルの構築
閉塞、ノイズ及び他の変化によって、所与の曲線上の３つのベースポイントが対応する画像曲線において可視でなくなる場合があるため、３つのベースポイントのより多くのセットに対する全てのポイントのアフィン座標を記録しなくてはならない。得られた画像ハッシュテーブル５は、この計算情報を表すのに便利なデータ構造であり、エントリーはアフィン座標の範囲を画定するベーストリプルである。画像ハッシュテーブルはハッシュテーブル構築モジュール４において構築される。このとき、アフィン座標の適切な量子化を用い、各々のアフィン座標を生じるベースポイントを記録する。即ち、下記の式を用いる。
Ｈ（α１＜＝α＜α２、β１＜＝β＜β２）
＝｛＜Ｏ′、Ｐ′1 、Ｐ′2 ＞... ｝
これにより、１つのポイントの任意の所与のアフィン座標（アフィン変換後の座標)(α、β）に対し、この座標を生じることができたベースポイントは、ハッシュテーブルのエントリーα＿｛１｝＜＝α＜α＿｛２｝、β＿｛１｝＜＝β＜β＿｛２｝を調べることによって見出すことができる。曲線グループ内により多くの曲線がある場合は、画像ハッシュテーブルを下記のように構築する。１つの曲線における連続的な特徴を３つ毎にベーストリプルとして使用し、曲線グループの全ての特徴のアフィン座標を計算する。従って、ベースポイントは単一曲線から得られるが、アフィン座標は曲線グループの全ての曲線上の全ての特徴に関して計算される。
【００２４】
連続的な３つの特徴はベースポイントに使用されるため、単刀直入な幾何学ハッシングにおけるＯ（Ｎ3 ）とは異なり、ベースポイントの線形数のみを記録すればよい。また、ハッシュテーブルのサイズは、通常の幾何学ハッシングがＯ（Ｎ4 ）であるのに対し、Ｏ（Ｎ2 ）である。このスキームの計算の実現可能性は、オブジェクトを局限する能力と共に、幾何学ハッシングの既存の変形物を改良する。
【００２５】
索引付け又は単語の局限
ここで、図４のブロック図を参照する。索引付けの際、照会単語６をシステムに与え、前処理ステップ及び図３に説明された特徴の生成に必要なモジュール（７及び８）を用いて照会単語６から曲線グループを生成する。単語の局限（照会単語に対応する単語の特定）はまず、より長い平均曲線長の曲線グループを用いて行われる。このような各曲線グループ毎に、アフィン座標の集合を索引付けモジュール９において計算し、これらを使用して画像ハッシュテーブル１２を索引付けする。ベースポイントの数は線形であるため、ロバストにするために曲線グループの全てのベースポイントに対してこの操作を繰り返してもよい。アフィン座標を用いて索引付けした各ベーストリプル毎に、索引付けした回数（ヒットと呼ばれる）及び対応する照会トリプルを記録する。ヒット数、対応する照会単語及び文書画像内の整合ベースポイントのヒストグラムをヒストグラムランク付けモジュール１０に記録する。次に、ヒストグラムのピークを照会の候補の位置とみなす。
【００２６】
ハッシュテーブルの索引付けにおいて、下記のようにアフィン座標の集合を生成することにより、画像内の単語を単語セグメント（又は照会単語）に分割する。
１．単語内の区切れをＴ＝（ｔ1 、ｔ2 ）とする。
２．各ベーストリプル＜Ｏ、Ｐ１、Ｐ２＞及び所与の特徴ポイントＰに対し、アフィン座標（α、β）及び（α′k 、β′k ）を計算する。ここで、（α′k 、β′k ）は下記のように計算する。
【数３】
0004308342.tif 000004
式中、ｋは曲線グループ内の曲線の数を表す。値ｋは、著者の書体（即ち、著者が単語を特徴的なスタイルで書く態様）に合わせられる。
３．各アフィン座標を用いてハッシュテーブルを索引付けし、前述のヒットのヒストグラムのピークを記録する。
【００２７】
検証
単語の局限の最後のステップでは、索引付けステップで与えられた候補の位置において単語の検証を行う。これは、ポーズ検証モジュール１１によって行われる。このステップは、有意なヒットに対応する整合ベースポイントの連立方程式の集合を解いてを求めることにより、ポーズパラメータ（Ａ、Ｔ）を見出す（recover)ことを含む。
【００２８】
ポーズパラメータを用いて、照会単語の曲線上の全ての点（ｉ、ｊ)(コーナー特徴を含む）を文書画像の位置（ｉ′、ｊ′）に射影する。位置（ｉ′、ｊ′）は、下記のように求められる。
【数４】
0004308342.tif 000005
次に、画像の各曲線上のポイント特徴が射影されたポイントの近辺に位置するかどうかを検証する。適合した射影ポイントと照会単語の全ての曲線上のポイントの総数との比率により、検証スコアが構成される。このスコアが適切に選択されたしきい値を上回っている場合、この検証は成功したと言える。適合するベースポイントが検証されない場合、次に最も有意な照会曲線グループを試し、有意なグループが残らなくなるまでこれを続ける。しかし、実際には、最も強い照会曲線を用いて、索引付け操作の際早くに正確な照会局限が達成される。
【００２９】
具体例
図１は走査された手書き文書を示し、図５（Ａ）はこの画像に対して前処理及び特徴抽出を行った結果を示している。ハッシュテーブルの構築に使用される曲線毎のコーナー特徴は、図５（Ａ）に丸で示される。全ての曲線を合わせて曲線は１７９あり、コーナーは２０８４ある。これらによって、ハッシュテーブルのためのベースポイントが３４９４になる。図５（Ｂ）は、単一曲線からなる照会パターンを示している。図６は、アフィン座標に基づいたハッシングのヒストグラムを示している。ここでは、画像のベースポイントを、照会パターンのアフィン座標から得られたヒットの数に対してプロットしている。図７は、ハッシングの結果を示している。ヒストグラムの最も有意な３つのピークに対応するハッシングされた画像のベースポイントを各照会ベーストリプルと整合し、候補のポーズを計算する。次に、ポーズパラメータを用いて照会曲線を画像に射影する。これは、図７で太線で示すように元の画像の上に重ねられて示される。図からわかるように、上の２つの整合は、整合が生じる２つの位置において照会パターンを正確に局限している。しかし、３つめの整合は誤実証であり、これはポーズ検証の際に取り除くことができる。この場合、誤実証が生じたのは、画像の前景のテキストパターンが表状の（画像が描かれた物の）背景のラインと合ったためである。
【００３０】
再び図２を参照すると、ハッシングによる別の照会局限の図が示されており、ここでは曲線グループを用いている。図２（Ａ）は、"database"という単語が２回生じる見本の文書を示している。この "database" という照会単語は図２（Ｂ）に示される。この単語の文字間の間隔は、２つの例において均一ではない。索引付けに使用した照会パターンが図２（Ｃ）に示される。ここでもまた、上の３つの整合が（ポーズ解決後に）元の画像の上に重ねられ、照会の局限を示している。この単語を構成する文字が、この単語が生じる画像の２つの例において異なる間隔で書かれているときでさえも、この索引付けスキームを使用してこの単語が局限されたことに注意する。ここに示される誤実証整合は、コーナー特徴に基づき下層の単語と類似していたため、ポーズ検証の後でも残った。
【００３１】
筆跡のトークン化への拡張
画像そのものにおける曲線グループのうちの１つである照会手書き単語を選択することにより、他のトークン化スキームによって行われるように文書中の単一の単語を１つずつしっかりと整合したりせずに、上記方法を使用して文書中に単語が複数表れていることを識別することができる。また、曲線グループ内のアフィン不変特性を用いることで、このようなトークン化スキームは、向き、スキューの変化及び単一著者の筆跡の変化に対してロバストになる。
【００３２】
風景画像内の任意の２Ｄオブジェクトの位置づけの一般化
（おそらくエッジ検出及び曲線トレースによって）自然の画像を処理して曲線を生成することにより、上記方法を一般化し、セグメント化されていない自然の風景画像における任意の２Ｄオブジェクトの形状を処理することができる。曲線グループを生成するためのグルーピングの制約は、手書き文書の場合ほど定義が容易ではない場合がある（単語はライン上に書かれる）。最後に、上記の方法は、曲線上のコーナー特徴のほかに他の特徴単位も許容する。しかし、グルーピング特性は、オブジェクトの局限に使用される任意の特徴と共に保たれなくてはならない。
【図面の簡単な説明】
【図１】見本の手書き文書の走査画像を示している。
【図２】（Ａ）は見本の手書き文書画像を示し、（Ｂ）は手書きの照会単語を示し、（Ｃ）は候補の位置に射影された対象照会単語を示している。
【図３】ハッシュテーブルの構築に関する本発明のモジュールのブロック図を示している。
【図４】ハッシュテーブルの画像索引付けによる照会の局限に関連する本発明のモジュールのブロック図を示している。
【図５】（Ａ）は図１の見本の手書き文書中の曲線を示しており、曲線のコーナー特徴を丸で示している。（Ｂ）は単一曲線からなる照会パターンを示しており、この曲線のコーナー特徴をハッシュテーブルの索引付けに使用している。
【図６】図５（Ａ）の画像の全てのベースポイントのヒットのヒストグラムを示している。
【図７】図５（Ａ）のハッシングの結果を示している。
【符号の説明】
１    文書画像
２、７    特徴抽出モジュール
３、８    曲線グループ生成モジュール
４    ハッシュテーブル構築モジュール
５、１２    画像ハッシュテーブル
６    照会単語
９    ハッシュテーブル索引付けモジュール
１０    ヒストグラムランク付けモジュール
１１    ポーズ検証モジュール
【図１】
0004308342.tif 000006
【図２】
0004308342.tif 000007
【図３】
0004308342.tif 000008
【図４】
0004308342.tif 000009
【図５】
0004308342.tif 000010
【図６】
0004308342.tif 000011
【図７】
0004308342.tif 000012