(57)【要約】      （修正有）【課題】第１のクラスの文書と他のクラスの文書とを弁別するための１つまたは複数の画像アンカテンプレートを生成する方法と、対応するシステムとを提供する。【解決手段】１つまたは複数の画像アンカテンプレート候補を生成することと、コンピュータプロセッサを用いて上記１つまたは複数の画像アンカテンプレート候補毎に品質スコアを決定することと、上記１つまたは複数の画像アンカテンプレート候補の品質スコアに従って、上記１つまたは複数の画像アンカテンプレート候補に等級を付けることと、最も高い等級の上記画像アンカテンプレートのうちの１つまたはそれ以上を選択することを含む。【選択図】図２
2011243199.tif 000002
【特許請求の範囲】
【請求項１】
第１のクラスの文書と他のクラスの文書とを弁別するための１つまたは複数の画像アンカテンプレートを生成する方法であって、
ａ）１つまたは複数のシード画像アンカテンプレート及び／または前記第１のクラスの１つまたは複数の手本のうちの少なくとも１つを用いて、１つまたは複数の画像アンカテンプレート候補を生成することと、
ｂ）コンピュータプロセッサ及び前記第１のクラスの前記１つまたは複数の手本を用いて、前記１つまたは複数の画像アンカテンプレート候補毎に品質スコアを決定することと、
ｃ）品質スコアに従って、前記１つまたは複数の画像アンカテンプレート候補に等級を付けることと、
ｄ）最も高い等級の前記画像アンカテンプレートのうちの１つまたはそれ以上を選択することを含む方法。
【請求項２】
前記１つまたは複数の画像アンカテンプレート候補毎の前記品質スコアは、前記１つまたは複数の画像アンカテンプレート候補の各々と前記第１のクラスの前記１つまたは複数の手本との一致の質を基礎とする、請求項１に記載の方法。
【請求項３】
第１のクラスの文書と他のクラスの文書とを弁別するための１つまたは複数の画像アンカテンプレートを生成するためのシステムであって、
１つまたは複数のシード画像アンカテンプレート及び／または前記第１のクラスの１つまたは複数の手本のうちの少なくとも１つを用いて、１つまたは複数の画像アンカテンプレート候補を生成する生成器モジュールと、
コンピュータプロセッサ及び前記第１のクラスの前記１つまたは複数の手本を用いて、前記１つまたは複数の画像アンカテンプレート候補毎に品質スコアを決定するテンプレートスコアリングモジュールと、
品質に従って、前記１つまたは複数の画像アンカテンプレート候補に等級を付けるランキングモジュールと、
最も高い等級の前記画像アンカテンプレートのうちの１つまたはそれ以上を選択する選択モジュールとを備えるシステム。
【請求項４】
文書が第１のクラスのメンバであるか、他のクラスのメンバであるかを決定するための方法であって、
ａ）１つまたは複数のシード画像アンカテンプレート及び／または前記第１のクラスの１つまたは複数の手本のうちの少なくとも１つを用いて、１つまたは複数の画像アンカテンプレート候補を生成することと、
ｂ）コンピュータプロセッサ及び前記第１のクラスの前記１つまたは複数の手本を用いて、前記１つまたは複数の画像アンカテンプレート候補毎に品質スコアを決定することと、
ｃ）品質スコアに従って、前記１つまたは複数の画像アンカテンプレート候補に等級を付けることと、
ｄ）最も高い等級の前記画像アンカテンプレートのうちの１つまたはそれ以上を選択することと、
ｅ）前記最も高い等級の画像アンカテンプレートのうちの前記１つまたはそれ以上が前記文書を前記第１のクラスのメンバとして識別するかどうかを決定することを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に開示する本発明の例示的な実施形態は、概して文書の分類に関する。その具体的なアプリケーションは、文書の類別に使用される画像アンカテンプレートの生成と連動して見出され、本明細書では特にこれに関連して説明する。しかしながら、本発明の例示的な実施形態が他の類似するアプリケーションにも適することは認識されるべきである。
【背景技術】
【０００２】
多数の文書を処理するに当たっては、これらの文書を迅速に分類することが望ましい場合が多い。典型的なソリューションは、手動で生成された１つまたは複数の画像アンカテンプレートを文書に対応するターゲット画像にマッチングさせることによって動作する。画像アンカテンプレートがターゲット画像に十分に一致すれば、対応する文書の分類が分かる。
【０００３】
このようなソリューションの１つの重要な側面は、これらが異なるクラスの文書間を弁別する画像アンカテンプレートの能力に依存していることにある。必然的に、画像アンカテンプレートはその弁別力によって選ばれる。換言すれば、画像アンカテンプレートは、異なるクラスの文書間を区別化するその能力によって選ばれる。
【０００４】
画像アンカテンプレートの選定に際して、典型的なソリューションは、オペレータが特定のクラスのターゲット画像と他のクラスのターゲット画像とを弁別するための画像アンカテンプレートを手動で選択することに依存する。言い換えれば、これらのソリューションは、画像アンカテンプレートを生成するオペレータの技量及び直観に依存する。しかしながら、オペレータへのこの依存性は、画像アンカテンプレートを選択する困難さに起因して標準以下の画像アンカテンプレート及び／または時間及び資源の浪費に繋がる場合がある。
【０００５】
即ち、オペレータにとって、ある特定の画像アンカテンプレートが異なるターゲット画像にどのようにマッチするかを予測することは困難である。まして、オペレータにとって、異なるクラスのターゲット画像に一致するとは思われない画像アンカテンプレートを見つけることはさらに困難である。この傾向は、考察されるべき文書が固定部分及び可変部分及び／または他のクラスの文書と共有する部分を有していれば特に顕著である。このような事例としては、機関書式、レターヘッド、伝票、他がある。これらの困難さの結果として、オペレータは概して、時間及び資源を要する試行錯誤過程を経ることを余儀なくされる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述の欠点に鑑みて、画像アンカテンプレートを生成する改良されたシステム及び／または方法が必要とされている。本出願は、上述の問題点及び他の問題点を緩和するために使用される場合のある、このような新規かつ改良されたシステム及び／または方法を企図するものである。
【課題を解決するための手段】
【０００７】
本出願の一態様によれば、第１のクラスの文書と他のクラスの文書とを弁別する１つまたは複数の画像アンカテンプレートを生成するための方法が提供される。本方法は、１つまたは複数のシード画像アンカテンプレート及び／または第１のクラスの１つまたは複数の手本のうちの少なくとも１つを使用して１つまたは複数の画像アンカテンプレート候補を生成することにより開始される。次に、コンピュータプロセッサ及び第１のクラスの手本を用いて、画像アンカテンプレート候補毎の品質スコアが決定される。これらの品質スコアを基礎として、画像アンカテンプレート候補に等級が付けられ、等級の高い画像アンカテンプレートのうちの１つまたはそれ以上が選択される。
【０００８】
本出願の別の態様によれば、第１のクラスの文書と他のクラスの文書とを弁別する１つまたは複数の画像アンカテンプレートを生成するためのシステムが提供される。本システムは、生成器モジュールと、テンプレートスコアリングモジュールと、ランキングモジュールと、選択モジュールとを含む。生成器モジュールは、１つまたは複数のシード画像アンカテンプレート及び／または第１のクラスの１つまたは複数の手本のうちの少なくとも１つを用いて１つまたは複数の画像アンカテンプレート候補を生成する。テンプレートスコアリングモジュールは、コンピュータプロセッサ及び第１のクラスの手本を用いて画像アンカテンプレート候補毎に品質スコアを決定する。ランキングモジュールは、品質スコアに従って画像アンカテンプレート候補に等級を付ける。選択モジュールは、最も高い等級の画像アンカテンプレートのうちの１つまたはそれ以上を選択する。
【０００９】
本出願の別の態様によれば、ある文書が第１のクラスのメンバであるか、他のクラスのメンバであるかを決定するための方法が提供される。本方法は、１つまたは複数のシード画像アンカテンプレート及び／または第１のクラスの１つまたは複数の手本のうちの少なくとも１つを用いて１つまたは複数の画像アンカテンプレート候補を生成することにより開始される。次に、コンピュータプロセッサ及び第１のクラスの手本を用いて、画像アンカテンプレート候補毎の品質スコアが決定される。これらの品質スコアを基礎として、画像アンカテンプレート候補に等級が付けられ、等級の高い画像アンカテンプレートのうちの１つまたはそれ以上が選択される。最も高い等級の画像アンカテンプレートが選択されると、これらの最も高い等級の画像アンカテンプレートのうちの１つまたはそれ以上を用いて、その文書が第１のクラスのメンバであるかどうかが決定される。
【図面の簡単な説明】
【００１０】
【図１Ａ】テンプレートソースを示す。
【図１Ｂ】テンプレートソースを示す。
【図２】第１のクラスの文書と他のクラスの文書とを弁別する画像アンカテンプレートを生成するための方法を示す。
【図３】幾つかの異なる画像アンカテンプレート候補生成器を使用する画像アンカテンプレート候補の生成を示す。
【図４】ＲＯＣ曲線を示す。
【図５】図２の方法の一実施形態による画像アンカテンプレートの生成を示す。
【図６】図２の方法の一実施形態による画像アンカテンプレートの生成を示す。
【図７】図２の方法を使用する画像アンカテンプレート生成器を示す。
【図８】図７の画像アンカテンプレート生成器を有する文書分類システムの使用法を示す。
【発明を実施するための形態】
【００１１】
後に詳しく論じるシステム及び方法は、第１のクラスの文書と他のクラスの文書とを弁別するための画像アンカテンプレートの自動生成に関する。第１のクラスの少なくとも手本（即ち、例）を所与として、画像アンカテンプレートは、画像アンカテンプレート候補を生成し、これらの画像アンカテンプレート候補の品質スコアを決定し、品質スコアに従ってこれらの画像アンカテンプレート候補に等級を付けかつ最も高い等級の画像アンカテンプレート候補を選択することによって生成されることが可能である。しかしながら、これらのシステム及び方法を詳しく論じる前に、幾つかの基本的な構成ブロックについて論じる。
【００１２】
画像アンカテンプレートｔは、画像ｔ．ｉｍと、関心領域ｔ．ｒｏｉとを含む。テンプレートの画像ｔ．ｉｍはテンプレートソースＴのサブ画像Ｔａである。
ｔ．ｉｍ＝Ｔａ
ここで、ａはテンプレートソースＴのサブ領域を示す。サブ領域ａは、テンプレートソースＴの座標に関して指定され、かつ典型的には、サブ領域ａは軸平行の長方形領域になる。これに対して、関心領域ｔ．ｒｏｉは、ターゲット画像Ｉの座標に関して指定される。ターゲット画像Ｉは、画像アンカテンプレートｔに対してマッチングされる画像である。
【００１３】
図１ａ及び図１ｂを参照すると、テンプレートソース１００が示されている。テンプレートソース１００は、図示されているように未記入の書式であり、画像アンカテンプレート１０２を含んでいる。画像アンカテンプレートは、関心領域１０４と画像１０６とで構成される。
【００１４】
テンプレートマッチング関数ｍ（ｔ，Ｉ）は画像アンカテンプレートｔ及びターゲット画像Ｉを取り込み、ターゲット画像Ｉ内でテンプレート画像ｔ．ｉｍに最もよく類似するものを発見するためにテンプレート画像ｔ．ｉｍの有効変換セットを探索する。有効変換はテンプレート関心領域ｔ．ｒｏｉに限定され、かつテンプレート画像ｔ．ｉｍの平行移動、テンプレート画像ｔ．ｉｍの回転、ｔ．ｉｍのスケーリング及びｔ．ｉｍのアフィン変換のうちの少なくとも１つを含んでもよい。しかしながら、テンプレート画像ｔ．ｉｍの他の変換も等しく適合することは認識されるべきである。
【００１５】
ターゲット画像Ｉ内のよく類似するものを位置決めした後、テンプレートマッチング関数は概して［０，１］の範囲内のスコアを返す。但し、ゼロは一致なし、を示し、１は完全一致を示す。完全一致は、ターゲット画像Ｉの何らかのサブ領域が有効変換下でテンプレート画像ｔ．ｉｍに精確にピクセル単位で一致する場合にのみ存在する。さらに、画像アンカテンプレートｔが複数のロケーションに一致すれば、スコアは一致の数と共に増大する係数で割り引かれる。従って、テンプレートマッチング関数ｍ（ｔ，Ｉ）によって返されるスコアは、典型的には発見された最良一致の「優良度」を表すスコアであるが、この限りではない。所定の実施形態では、マッチング関数はターゲット画像Ｉの最良一致または最良一致のサブ画像に対応する有効変換も返してもよい。
【００１６】
マッチング関数は上述の制限を受ける任意のものが使用されてもよいが、所定の実施形態では、マッチング関数は、種々の正規化を行った、または行わない基本的な相関測度、確率的尤度または尤度比（文書画像復号化のためのマルチレベルテンプレート等）、ハウスドルフ距離及び局所的測定ヒストグラム（アースムーバーズ距離等）を基礎とする比較のうちの少なくとも１つを基礎としている。
【００１７】
２値文書を取り扱う場合は、ハウスドルフ距離を基礎とするマッチング関数が特に興味深いが、これは、このマッチング関数が２値画像の取扱いにおいて高速かつ効率的であることが知られているためである。２画像（例えば、テンプレート画像及びターゲット画像のサブ画像）間のハウスドルフ距離は、最良一致シナリオを得るためにテンプレートが最も好適な有効変換によって変換された後の対応する２つのフォアグラウンドの点間の最大距離として定義される。
【００１８】
Ｒｕｃｋｌｉｄｇｅ、らは、テンプレート画像の点集合とサブ画像の点集合とのハウスドルフ距離を最小化することによって、より大きい画像内にテンプレートを位置決めするための分枝限定を基礎とする有効な技術を開発した。詳細情報については、Ｄａｎｉｅｌ  Ｐ．Ｈｕｔｔｅｎｌｏｃｈｅｒ、Ｗｉｌｌｉａｍ  Ｊ．Ｒｕｃｋｌｉｄｇｅ共著「ハウスドルフ距離を用いる多分解能画像比較技術」Ｔｅｃｈｎｉｃａｌ  ＲｅｐｏｒｔＴＲ  ９２−１３２１、コーネル大学、１９９２年、及びＷｉｌｌｉａｍ  Ｒｕｃｋｌｉｄｇｅ著「ハウスドルフ距離を用いる効率的な視覚認識」（Ｓｐｒｉｎｇｌｅｒ−Ｖｅｒｌａｇ  Ｎｅｗ  Ｙｏｒｋ，Ｉｎｃ．、米国、ニュージャージー州、セコーカス、１９９６年）を注目されたい。
【００１９】
テンプレート検出関数ｄ（ｔ，Ｉ）は、良い一致が発見されたかどうかを示すために１またはゼロを返すブール関数である。但し、ゼロは一致が発見されなかったことを意味する。テンプレート検出関数は、テンプレートマッチング関数の一致スコアを受容しきい値ｑと比較することによって構築されてもよい。
ｍ（ｔ，Ｉ）＞ｑであれば、ｄ（ｔ，Ｉ；ｍ，ｑ）＝１
そうでなければ、０
【００２０】
複合画像アンカテンプレートＣは、画像アンカテンプレート（ｔ１，ｔ２，．．．，ｔｋ）の集合体である。先に述べたテンプレートマッチング関数と同様に、複合テンプレートマッチング関数ｍ（ｃ，Ｉ）も概して［０，１］の範囲内のスコアを返す。但し、このスコアはマッチングの「優良度」を表す。しかしながら、先に述べたテンプレートマッチング関数とは対照的に、複合テンプレートマッチング関数は画像アンカテンプレートの各々がターゲット画像Ｉとどのようにマッチングするかについて考慮する。ある典型的な複合マッチング関数は、個々のテンプレートマッチング関数に渡る関数を画定することによって取得される。
【数１】
2011243199.tif 000003
このような関数は、例えば個々のテンプレート一致スコアの最大値、最小値、平均値または中央値を考慮する可能性もある。より高度な複合マッチング関数は、個々の一致スコアだけでなく、対応する変換についても考慮することがある。
【００２１】
先に述べたテンプレート検出関数に類似する複合テンプレート検出関数ｄ（Ｃ，Ｉ）は、ゼロまたは１（一致または一致なし）を返す。典型的には、複合テンプレート検出関数は個々のテンプレート検出関数のブール組合せである。しかしながら、他の方法も等しく適合する。例えば、投票方式を用いること、または複合検出器として２値文書分類器関数を適用することも可能である。
【００２２】
２値または多カテゴリ文書分類器関数は、ターゲット画像、及び異なるクラスのターゲット画像間を弁別することができる画像アンカテンプレートの集合を取り込み、分類を返す。２値文書分類器関数は単に、ターゲット画像が所定の分類のものであるかどうかを示す。多カテゴリ文書分類器関数は、複数の既知の分類のうちの１つからターゲット画像の分類を返す。所定の実施形態では、文書分類器関数は、テンプレートマッチング関数及び／またはテンプレート検出関数の結果を分類器への入力ベクトルとして処理することによってテンプレートマッチング関数及び／またはテンプレート検出関数を積み上げる。
【００２３】
例えば、第１のクラスの一致文書のみに知られる（かつ他のクラスの文書には知られていない）画像アンカテンプレートを有していれば、その画像アンカテンプレートが文書画像に一致するかどうかを基礎として文書分類器関数を容易に構築することができる。より複雑な事例では、これは、異なるクラスの文書間を弁別するために画像アンカテンプレートの組合せを取り込んでもよい。このような事例では、文書分類器関数は単に、テンプレートマッチング関数及び／またはテンプレート検出関数からの結果のベクトルからこれらの組合せを認識できるだけでよい。ブール代数は、検出結果のベクトルを処理するための有益なツールを提示する。
【００２４】
図２を参照すると、第１のクラスの文書と他のクラスの文書とを弁別するための１つまたは複数の画像アンカテンプレートを決定する方法２００が示されている。方法２００は、画像アンカテンプレート候補を生成すること（アクション２０２）と、画像アンカテンプレート候補毎に品質スコアを決定すること（アクション２０４）と、品質スコアに従って画像アンカテンプレート候補に等級を付けること（アクション２０６）と、最も高い等級の画像アンカテンプレートのうちの１つまたはそれ以上を選択すること（アクション２０８）を含む。所定の実施形態では、方法２００はさらに、終了条件が満たされるまでアクション２０２から２０８までを反復することを含む。
【００２５】
まず始めに、画像アンカテンプレート候補生成器を用いて画像アンカテンプレート候補が生成される（アクション２０２）。画像アンカテンプレート候補生成器は、概して、入力として画像及び／または画像アンカテンプレートを取り込む。所定の実施形態では、画像は第１のクラスの手本画像であり、または他のクラスの手本画像である。手本画像は、方法２００をトレーニングするために使用される、あるクラス（例えば、第１のクラス）からの文書例の画像である。典型的には、方法２００を実行するオペレータが手本画像を画定する。所定の実施形態では、画像アンカテンプレートは、入力として画像または画像アンカテンプレートを取り込むことに加えて、第１のクラスの手本及び／または他のクラスの手本も取り込む。
【００２６】
この入力を基礎として、画像アンカテンプレート候補生成器は画像アンカテンプレート候補を生成する。所定の実施形態では、画像アンカテンプレート候補を生成することは、必然的に、入力からサブ画像を抽出すること、及び／または入力に対して任意数の有効変換を実行することを伴う。有効変換には、平行移動、回転、アフィン変換、他が含まれるが、この限りではない。画像アンカテンプレート候補生成器の例には、粗グリッドサンプリング生成器、シードコレクション生成器及び推移エクスプローラ生成器が含まれるが、この限りではない。
【００２７】
粗グリッドサンプリング生成器は入力画像を取り込み、入力画像から画像アンカテンプレートの粗いサンプリングを生成する。言い替えれば、粗グリッドサンプリング生成器は入力画像をサブ領域に分割し、これらのサブ領域を画像アンカテンプレートに抽出する。所定の実施形態では、そのピクセルがほぼ全て白またはほぼ全て黒である画像アンカテンプレートは放棄されるが、これは、これらが元来低い弁別力を有するものと理解されているためである。粗グリッドサンプリング生成器により生成される画像アンカテンプレート候補の数を制御するために、入力画像から抽出されるべき画像アンカテンプレートのサイズは変えられることが可能である。当然ながら、サイズが小さいほど、画像アンカテンプレートの数は多くなる。
【００２８】
図３ａを参照すると、粗グリッドサンプリング生成器３０２を用いる画像アンカテンプレート候補の生成が示されている。図から分かるように、粗グリッドサンプリング生成器３０２は入力として画像３０４を受信し、画像アンカテンプレート候補３０６を出力する。
【００２９】
シードコレクション生成器（摂動生成器とも称される）は入力として画像アンカテンプレートを取り込み、入力された画像アンカテンプレートに対して有効変換を実行することにより新しい画像アンカテンプレートを生成する。有効変換には、平行移動、回転、アフィン変換、他が含まれるが、この限りではない。従って、シードコレクション生成器は、入力された画像アンカテンプレートの僅かな変動を探ることによって画像アンカテンプレートを生成する。所定の実施形態では、シードコレクション生成器は、入力された画像アンカテンプレートの関心領域の変動を探ってもよい。
【００３０】
図３ｂを参照すると、シードコレクション生成器３０８を用いる画像アンカテンプレート候補の生成が示されている。図から分かるように、シードコレクション生成器３０８は入力として画像アンカテンプレート３１０を受信し、画像アンカテンプレート候補３１２を出力する。
【００３１】
推移エクスプローラ生成器はシードコレクション生成器の特別な一種であり、入力として画像アンカテンプレート及び手本を取り込んで、画像アンカテンプレートを手本にマッチングさせる。この場合、手本内に一致を作り出すことによって新しい画像アンカテンプレートが構築される。所定の実施形態では、推移エクスプローラ生成器もまた、シードコレクション生成器と同様に、入力された画像アンカテンプレート上で有効変換を探る。さらに、所定の実施形態では、推移エクスプローラ生成器は、手本内の全ての一致を結合することによって画像アンカテンプレートを生成する。これらの実施形態の中には、これが、全ての一致するロケーションが互いの上にオーバーレイされる際に最も一致したピクセルを識別することによって決定されるものがある。
【００３２】
図３ｃを参照すると、推移エクスプローラ生成器３１４を用いる画像アンカテンプレート候補の生成が示されている。図から分かるように、推移エクスプローラ生成器３１４は入力として画像アンカテンプレート３１６及び手本３１８を受信する。この入力を受信した後、推移エクスプローラ生成器は画像アンカテンプレート候補３２０を出力する。
【００３３】
列挙された画像アンカテンプレート生成器に関わらず、他の種類の画像アンカテンプレート生成器も等しく適する。さらに、画像アンカテンプレート生成器は、新しい複合生成器を取得するために様々な構成でネスト化されることも可能である。例えば、典型的には、シードコレクション生成器及び／または推移エクスプローラ生成器は粗グリッドサンプリング生成器と共に使用され、この場合、粗グリッドサンプリング生成器により生成される画像アンカテンプレートはシードコレクション生成器及び／または推移エクスプローラ生成器への入力として使用される。
【００３４】
図２を再度参照すると、画像アンカテンプレート候補がどのようにして生成されるか（アクション２０２）に関わらず、品質スコアは、テンプレートスコアリング関数を用いて画像アンカテンプレート候補毎に決定される（アクション２０４）。画像アンカテンプレートの品質スコアは、その弁別力の測度である。本方法のコンテキストにおいて、画像アンカテンプレートの弁別力は、第１のクラスの文書と他のクラスの文書とを弁別する画像アンカテンプレートの能力に相当する。
【００３５】
品質スコアの決定を容易にするために、テンプレートスコアリング関数は、概して、第１のクラスの１つまたは複数の手本（即ち、陽性手本）を入力として取り込む。所定の実施形態では、テンプレートスコアリング関数はさらに、他のクラスの手本（即ち、陰性手本）を入力として取り込んでもよい。手本は、本方法が、第１のクラスの文書と他のクラスの文書とを弁別する画像アンカテンプレートの能力を経験的に決定することを可能にする。
【００３６】
手本を入力として用いることにより、品質スコアは、固有の画像アンカテンプレート特性及び／または手本のサンプルコレクションに対する画像アンカテンプレート応答を使用して決定されてもよいが、必ずしもそうでなくてもよい。画像アンカテンプレート応答は、例えば、品質の監視された経験的推定、品質の監視されない経験的推定及び品質の経験的片側推定を含んでもよい。
【００３７】
固有のテンプレート特性を用いるテンプレートスコアリング関数は、少なくとも１つの画像アンカテンプレートを入力として取り込む。次にこれは、略既知の弁別力に相当する画像アンカテンプレートの特性を探す。例えば、全て白または全て黒の画像アンカテンプレートは有益でないように思われ、よって、これらの画像アンカテンプレートには低い品質スコアが適切に割り当てられてもよい。当然ながら、このようなテンプレートスコアリング関数の分解能レベルは限定的である。しかしながら、これは、画像アンカテンプレートを効率的に放棄する迅速な方法を提供する。
【００３８】
品質の監視された経験的推定を用いるテンプレートスコアリング関数は、少なくとも１つの画像アンカテンプレート、陽性手本画像及び陰性手本を入力として取り込む。これは次に、手本に対する画像アンカテンプレート応答に注目する。即ち、画像アンカテンプレートｔ及びマッチング関数ｍ（ｔ，Ｉ）について、全ての手本（陽性及び陰性）の一致スコアが生成され、かつテンプレート検出関数ｄ（ｔ，Ｉ）における受容しきい値ｑを変えて受信者動作特性（ＲＯＣ）曲線を生成するために使用される。
【００３９】
ＲＯＣ曲線は、受容しきい値ｑの変更に伴う誤警報率（即ち、偽陽性率）に対するヒット率（即ち、真陽性率）をプロットすることによって得られる。所定の受容しきい値ｑに対するヒット率は、単に、テンプレート検出関数ｄ（ｔ，Ｉ）が手本を正しく分類する率である。陽性及び陰性手本の集合は既知であることから、テンプレート検出関数ｄ（ｔ，Ｉ）の検証は容易に達成される。同様にして、誤警報率も容易に得られる。図４を参照して、ＲＯＣ曲線を例示する。
【００４０】
ＲＯＣ曲線が生成されると、画像アンカテンプレートの品質スコアｓを次のように計算することができる。
【数２】
2011243199.tif 000004
ａｒｅａＲＯＣ（ｔ，ｍ，α）は、単にＲＯＣ曲線から下の面積（即ち、図４の曲線から下の領域）であり、ｍａｒｇｉｎ（ｔ，ｍ）は陽性手本の最小一致スコアと陰性手本の最大一致スコアとの差である。さらに、ｂｅｓｔＲＯＣ（ｔ，ｍ，α）は、
【数３】
2011243199.tif 000005
と定義される。但し、ｈｉｔＲａｔｅ（ｑ）及びｆａｌｓｅＡｌａｒｍＲａｔｅ（ｑ）は実質的に先に述べた通りのものであり、αは誤警報のペナルティである。αが高いほど、誤警報のペナルティは大きくなる。
【００４１】
品質の監視されない経験的推定を用いるテンプレートスコアリング関数は、手本のサンプルコレクションに対する画像アンカテンプレート応答に注目する。この品質推定は、複数のターゲットカテゴリが存在する状況を標的とし、かつ手本コレクションのカテゴリラベルは既知であるが、カテゴリをどのように分割するかに関する決定は行われていない。このような事例では、テンプレートの品質スコアは、マッチング／検出結果と画像カテゴリラベルとの間の相互的情報である。
【００４２】
品質の経験的片側推定を用いるテンプレートスコアリング関数は、少なくとも１つの画像アンカテンプレート及び陽性手本を入力として取り込む。次にこれは、陽性手本のみのサンプルコレクションに対する画像アンカテンプレート応答に注目する。即ち、片側計量ｏ（ｔ，ｍ）は、
【数４】
2011243199.tif 000006
と定義することができる。但し、右辺の各確率は、ベイズ規則を用いて、下記の公式から始まる等しい先験的確率によって計算されることが可能である。
【数５】
2011243199.tif 000007
当然認識されるように、変数λはトレーニングされることが可能である。しかしながら、スペースに配慮して、所定の実施形態ではλｐｏｓ及びλｎｅｇは１に設定され、よって陰性カテゴリにはより平らな分布が与えられる。
【００４３】
列挙されたテンプレートスコアリング関数に関わらず、他のテンプレートスコアリング関数も等しく適することは認識されるべきである。例えば、先に列挙したテンプレートスコアリング関数上に構築される複合テンプレートスコアリング関数及び／または他のテンプレートスコアリング関数が使用されてもよい。さらに、先に論じたテンプレートスコアリング関数は単一の画像アンカテンプレートに関して定義されたが、テンプレートスコアリング関数が複合テンプレートに使用されてもよいことは認識されるべきである。
【００４４】
画像アンカテンプレート候補の品質スコアが生成されると（アクション２０４）、画像アンカテンプレート候補にはこれらの品質スコアに従って等級が付けられ（アクション２０６）、最も高い等級の画像アンカテンプレート候補のうちの１つまたはそれ以上が選択される（アクション２０８）。所定の実施形態では、選択されるべき画像アンカテンプレートの数をオペレータが手動で画定する。他の実施形態では、選択されるべき画像アンカテンプレートの数は、第１のクラスの全手本（即ち、陽性手本）のフルカバーを達成するレベルへ動的に設定される。フルカバーは、第１のクラスの全手本と他のクラスの手本とを弁別する能力を指す。
【００４５】
所定の実施形態では、この時点で方法２００は完了する。このような実施形態では、選択された画像アンカテンプレートは、第１のクラスの文書と他のクラスの文書とを弁別するために見出された最良の画像アンカテンプレートである。この線に沿って、図５を参照すると、図２の方法の特有の実施形態による画像アンカテンプレートの生成が示されている。画像アンカテンプレート候補５０２は、陽性手本５０６及び陰性手本５０８を要する品質の監視された経験的推定を用いて等級付けされる５０４。この後、予め画定された数の最も高い等級の画像アンカテンプレートが選択される５１０。但し、選択されるこれらの画像アンカテンプレートは、生成された最良の画像アンカテンプレート５１２を提示する。
【００４６】
しかしながら、他の実施形態では、方法２００は続いていく場合がある。即ち、先に述べたように、最も高い等級の画像アンカテンプレートが選択された後、後に述べる条件に従って、方法２００は、終了条件が満たされるまでアクション２０２から２０８までを任意選択として反復してもよい（アクション２１０）。これらの実施形態の下では、反復は、反復毎に変わってもよい。例えば、画像アンカテンプレート関数及び／またはテンプレートスコアリング関数は変わってもよい。
【００４７】
終了条件に関連して、所定の実施形態では、終了条件は経過した実行時間であり、及び／または予め画定された反復数で実行される。例えば、方法２００は５秒間実行された後に終了されてもよい。他の実施形態では、終了条件は、選択された画像アンカテンプレートが第１のクラスの全手本をカバーしているかどうかである。言い替えれば、選択された画像アンカテンプレートが第１のクラスの全手本と他のクラスの手本とを弁別することができるかどうかである。
【００４８】
後者の終了条件の下では、選択された画像アンカテンプレートによってカバーされていない第１のクラスの手本が存在すれば、これらの手本は次の反復において画像アンカテンプレートを生成するために使用されてもよい。例えば、カバーされていない手本は、粗グリッドサンプリング生成器への入力として使用されてもよい。さらに、もしくは代替として、カバーされていない第１のクラスの手本から導出される画像アンカテンプレートは、シードコレクション生成器及び／または推移エクスプローラ生成器への入力として使用されてもよく、これにより、これらの画像アンカテンプレートはシード画像アンカテンプレートとして作用する。
【００４９】
上述の例示的な終了条件に関わらず、他の終了条件も等しく適し、かつ終了条件が個々の終了条件の複合体であってもよいことは認識されるべきである。例えば、終了条件は、経過時間及び選択された画像アンカテンプレートが第１のクラスの全手本と他のクラスの手本とを弁別できるかどうかの双方を使用してもよい。
【００５０】
反復に関して、アクション２０２から２０８までは、実質的に先に述べたようにして反復される。しかしながら、これについての１つの顕著な例外は、新しい画像アンカテンプレート候補が先に選択された画像アンカテンプレートと共に等級付けされることである。言い替えれば、先の反復からの最良の画像アンカテンプレートは、現行の反復から新たに生成される画像アンカテンプレート候補と共に等級付けされる。さらに、先に示唆したように、先の反復からの最も高い等級の画像アンカテンプレート候補のうちの１つまたはそれ以上は、アクション２０２において新しい画像アンカテンプレート候補を生成するための入力として使用されてもよい。
【００５１】
例示として、本方法の反復例を次に示す。粗グリッドサンプリング生成器を用いて、第１のカテゴリの手本から画像アンカテンプレート候補の初期集合が生成される。次に、これらの画像アンカテンプレート候補の品質スコアが決定され、かつ画像アンカテンプレート候補に等級が付けられる。この等級付けから、上位２００個の画像アンカテンプレートが選択される。終了条件が満たされていない（例えば、経過時間が経過していない）ものとして、選択された画像アンカテンプレートは、シードコレクション生成器及び／または推移エクスプローラ生成器によって追加の画像アンカテンプレートを生成するために使用される。次に、これらの新たに生成された画像アンカテンプレートには品質スコアが生成され、かつ新たに生成された画像アンカテンプレートは先に選択された画像アンカテンプレートと共に等級を付けられる。この等級付けから、上位２００個の画像アンカテンプレートが選択される。終了条件は満たされているものとすれば、これらの上位２００個の画像アンカテンプレートは本方法の最終結果を表す。
【００５２】
上述の方法２００のパフォーマンスを向上させるために、幾つかのオプションが利用可能である。例としては、グリッドサンプリング発生器の粗さを調整すること、２倍でサブサンプリングされた画像に取り組むこと、陰性手本に照らして検査される最大数の画像アンカテンプレートをキャッピングすること、画像アンカテンプレートの探索領域を縮小すること、検査される手本（陽性及び／または陰性）の数を減らすこと、マッチング関数（例えば、ハウスドルフマッチング）の変数を変えること、が含まれるが、この限りではない。
【００５３】
画像アンカテンプレートの探索領域の縮小に関連して、少なくとも２つの方法論は、固有のテンプレート特性を基礎とする方法及びヒストグラムベースの方法を含む。元来、第１のクラスの手本から、有益な画像アンカテンプレートを産出する可能性があるのは手本の所定のエリアのみであることは明らかであると思われる。従って、画像アンカテンプレートの探索は、例えば画像アンカテンプレートの探索を手本の上半分及び／または下半分に限定することによって限定されることが可能である。さらに、もしくは代替として、画像アンカテンプレートの探索領域を限定するためのより高度な方法は、ヒストグラムベースのアプローチを使用することである。
【００５４】
ヒストグラムベースのアプローチによれば、１つのターゲット画像上で最初の数百個のテンプレート一致を調べた後は、他のテンプレート一致が発見される変位の可能性を推測するに足る手掛かりが存在している。例えば、陽性手本画像に一致する数千個もの画像アンカテンプレートが存在するものとする。まず、変位の可能性のある大スペースで画像アンカテンプレートの一致を探索し、かつ一致が発見されている変位に渡ってヒストグラムをポピュレートし続ければ、幾つか（例えば、１００個）の一致の後に、それまでの一致の９５％以上を含む最小の外接矩形を識別することができる。次に、残りのテンプレートは、相対変位のこのより密な矩形内でのみマッチングされることが可能である。
【００５５】
どの最適化が使用されるかに関わらず、方法２００が完了すると、先に述べたように、方法２００を用いて生成された画像アンカテンプレートを、第１のカテゴリの２値または多カテゴリ文書分類器関数を構築するために容易に使用することができる。即ち、方法２００が実行されると、第１のクラスの画像アンカテンプレートと他のクラスの画像アンカテンプレートとを弁別するに足る画像アンカテンプレートのコレクションが得られる。従って、ある文書が第１のクラスに包含されるかどうかの決定は、単に、その文書が決定された画像アンカテンプレートに十分に一致するかどうかを決定するという問題になる。
【００５６】
方法２００を論じたこの時点では、所定の実施形態において、方法２００が複合画像アンカテンプレートを用いて使用されてもよいことは認識されるべきである。さらに、オペレータ入力は、上述のどのアクションにおいて使用されてもよい。例えば、方法２００の反復変形例の実行に際して、オペレータは、各反復について、画像アンカテンプレート候補が生成される方法を制御するために入力を行ってもよい。
【００５７】
例えば、図６を参照すると、図２の方法の反復実施形態に従った画像アンカテンプレートの生成が示されている。画像アンカテンプレート候補６０２は、陽性手本６０６を要する品質の経験的片側推定を用いて等級を付けられる６０４。この後、予め画定された数の最も高い等級の画像アンカテンプレートが選択され６０８、推移エクスプローラ生成器を用いて拡張される６１０。画像アンカテンプレートのこの拡張された集合は、選択された画像アンカテンプレート及び推移エクスプローラ生成器によって生成された画像アンカテンプレートを含む。次に、画像アンカテンプレートのこの拡張された集合には品質の経験的片側推定を用いて等級が付けられ６１２、予め画定された数の最も高い等級の画像アンカテンプレートが選択される６１４。この場合、これらの画像アンカテンプレートは、生成された最良の画像アンカテンプレート６１６に相当する。
【００５８】
先に述べたように、図６は、図２の方法２００の反復変形例として特徴づけられることが可能である。即ち、上述の拡張は、先の反復から選択された画像アンカテンプレートを用いる画像アンカテンプレートの生成として特徴づけられることが可能であり、よって選択された画像アンカテンプレートは推移エクスプローラ生成器のシードとして作用する。さらに、対応されない陽性手本６１８は単に、最良の画像アンカテンプレート６１６によってカバーされない第１のクラスの手本であるに過ぎない。先に述べたように、これらの手本は、後続の反復において追加的な画像アンカテンプレートを生成するために使用されてもよい。
【００５９】
図７を参照すると、図２の方法を用いる画像アンカテンプレート（ＩＡＴ）生成器７００が示されている。コンピュータ７０２または、記憶装置と、マイクロプロセッサ、マイクロコントローラ、グラフィック処理装置（ＧＰＵ）、他等のデジタルプロセッサとを含む他のデジタル処理デバイスは、ＩＡＴ生成器７００を適切に具現する。他の実施形態では、ＩＡＴ生成器７００は、デジタルプロセッサを含みかつデジタルデータ記憶装置を含む、またはデジタルデータ記憶装置へのアクセスを有するサーバによって具現され、このようなサーバは、インターネットまたはローカルエリアネットワークを介して、またはデジタルプロセッサ及びデジタルデータ記憶装置を含むパーソナルデータアシスタント（ＰＤＡ）、等々によって適切にアクセスされている。
【００６０】
コンピュータまたは他のデジタル処理デバイスは、適切には、ＩＡＴ生成器７００を制御するために、ユーザ入力を受信するための図示されているキーボード７０４等の１つまたは複数のユーザ入力デバイスを含むかこれらと動作可能式に接続され、かつさらに、ＩＡＴ生成器７００の出力を基礎として生成された出力を表示するために、図示されているディスプレイ７０６等の１つまたは複数のディスプレイデバイスを含むか、これらと動作可能式に接続される。他の実施形態では、ＩＡＴ生成器７００を制御するための入力は、コンピュータ７０２上でＩＡＴ生成器７００に先行して、またはＩＡＴ生成器７００と同時的に実行される別のプログラムから、またはネットワーク接続、等々から受信される。同様に、他の実施形態では、出力は、コンピュータ上でＩＡＴ生成器７００に続いて、またはＩＡＴ生成器７００と同時的に実行される別のプログラムへの入力として働いてもよく、またはネットワーク接続、等々を介して送信されてもよい。
【００６１】
ＩＡＴ生成器７００は、生成器モジュール７０８と、テンプレートスコアリングモジュール７１０と、ランキングモジュール７１２と、選択モジュール７１４とを含む。システムが図２の方法の反復変形例をサポートする所定の実施形態では、システムはさらに終了モジュール７１６を含む。
【００６２】
生成器モジュール７０８は、画像または画像アンカテンプレートを入力として受信し、これから画像アンカテンプレート候補を生成する。所定の実施形態では、生成器モジュール７０８は、入力をＩＡＴ生成器７００より外部のソースから受信する。ソースは、例えば、データベース、別のプログラム、オペレータ、他であってもよい。このような実施形態の下では、生成器モジュール７０８は、概して第１のクラスの１つまたは複数の手本を受信し、これらは粗グリッドサンプリング生成器によって画像アンカテンプレートを生成するために使用される。他の実施形態では、生成器モジュール７０８は入力を終了モジュール７１６から受信する。このような実施形態の下では、生成器モジュール７０８は、概して１つまたは複数の画像アンカテンプレートを受信し、これらはシードコレクション生成器及び／または推移エクスプローラ生成器によって使用される。生成器モジュール７０８は、好適には、図２のアクション２０２に関して述べたように画像アンカテンプレート候補を生成する。
【００６３】
テンプレートスコアリングモジュール７１０は、生成器モジュール７０８から画像アンカテンプレート候補を受信し、これらの画像アンカテンプレート候補の各々について品質スコアを決定する。所定の実施形態では、テンプレートスコアリングモジュール７１０はさらに、ＩＡＴ生成器７００及び／または生成器モジュール７０８より外部のソースから、第１のクラスの手本画像及び／または他のクラスの手本画像を受信する。例えば、テンプレートスコアリングモジュール７１０が品質の経験的片側推定を用いていれば、これは第１のクラスの陽性手本を受信する。生成器モジュール７０８と同様に、テンプレートスコアリングモジュールは、好適には、図２のアクション２０４に関して述べたように品質スコアを生成する。
【００６４】
次に、ランキングモジュール７１２は画像アンカテンプレート候補及び対応する品質スコアを受信し、品質スコアに従って画像アンカテンプレート候補に等級を付ける。後述するように、所定の実施形態において、ランキングモジュール７１２は先の反復からの画像アンカテンプレートも受信し、これらの画像アンカテンプレートをテンプレートスコアリングモジュール７１０から受信される画像アンカテンプレートと共に等級付けする。好適には、ランキングモジュール７１２は、図２のアクション２０６に関して述べたように作動する。
【００６５】
次に、選択モジュール７１４は、等級を付けられたこれらの画像アンカテンプレート候補を用いて、最も高い等級の画像アンカテンプレートのうちの１つまたはそれ以上を選択する。例えば、選択モジュール７１４は、最も高い等級の画像アンカテンプレートを２００個選択してもよい。好適には、選択モジュール７１４は図２のアクション２０８に関して述べたように作動する。
【００６６】
実施形態によっては、ＩＡＴ生成器７００は、先に述べたように終了モジュール７１６をさらに含み、これにより、ＩＡＴ生成器７００は反復的に作動して画像アンカテンプレートを生成する。このような実施形態では、終了モジュール７１６は終了条件が満たされているかどうかを決定する。終了条件が満たされていなければ、終了モジュール７１６は生成器モジュール７０８と調和して画像アンカテンプレートの新しい集合を生成し、次にこれらはテンプレートスコアリングモジュール７１０によってスコアを与えられ、かつ先に選択された画像アンカテンプレートと共にランキングモジュール７１２によって等級を付けられる。次に、画像アンカテンプレートの新しい集合が選択モジュール７１４によって選択され、かつ終了モジュール７１６は終了するかどうかを再度決定する。終了モジュール７１６は、好適には、図２のアクション２１０に関して述べたように作動する。
【００６７】
終了条件が満たされているか、ＩＡＴ生成器７００に終了モジュール７１６が存在しなければ、選択モジュール７１４からの選択された画像アンカテンプレートは次に表示用に出力され、プリントされ及び／または文書分類等の追加的な意志決定機構に実装される。文書分類に関連して、画像アンカテンプレートは、先に述べたように、文書分類器関数を生成するために使用されてもよい。この後、文書は、文書画像を文書分類器へ通すことによって迅速に分類されることが可能である。
【００６８】
図８を参照すると、文書分類システム８００の用途が示されている。システム８００は、画像デバイス８０２と、画像アンカテンプレート生成器８０４と、文書分類器８０６とを含む。画像デバイス８０２は、書式等の文書をターゲット画像に変換し、かつカメラ、スキャナまたは他の類似デバイスであってもよい。画像アンカテンプレート生成器８０４は、別段の記述のない限り、図７に記述されている通りである。文書分類器８０６は、画像アンカテンプレートを用いて文書のターゲット画像を分類する。
【００６９】
文書の分類は、画像アンカテンプレート生成器８０４へ手本８０８が供給された後に開始可能となる。画像アンカテンプレート生成器８０４へは、少なくとも陽性手本が供給される。しかしながら、使用される画像アンカテンプレートスコアリング関数に依存して、画像アンカテンプレート生成器へは陰性手本が供給されてもよい。所定の実施形態では、システム８００のオペレータは手本８０８を手動で分類する。この後、画像アンカテンプレート生成器８０４は手本８０８を取り込み、図７に関して論じたように画像アンカテンプレートを生成する８１０。
【００７０】
画像アンカテンプレートが生成された後８１０、システム８００は文書の分類を開始する。即ち、スキャンデバイス８０２は１つまたは複数の文書８１２を受信し、これらをターゲット画像８１４に変換する。所定の実施形態では、文書８１２は印刷デバイスの給紙トレイへ装填され、コンベヤ経路を介して画像デバイス８０２を通過される。
【００７１】
次に、ターゲット画像８１４は文書分類器８０６へ送られ、文書分類器８０６は画像アンカテンプレート生成器８０４からの画像アンカテンプレート８１０を用いてターゲット画像８１４を分類する。ターゲット画像８１４は文書分類器８０６へ文書８１２の変換と同時的に、または全文書８１２の変換後に送られてもよい。所定の実施形態では、先に述べたように、文書分類器８０６は画像アンカテンプレート８１０を２値または多カテゴリ文書分類器関数への入力として使用する。
【００７２】
文書分類器８０６が文書８１２を分類すると、文書８１２及び／またはターゲット画像８１４が必要に応じて処理される。例えば、文書８１２は、その分類を基礎として、コンベヤ経路を介して目的地へルーティングされてもよい。さらに、もしくは代替として、ターゲット画像８１２は、その分類に従ってデータベースに格納されてもよく、かつ／またはファイルシステム内に格納されてもよい。
【００７３】
これまでに行った論考に鑑みれば、実施形態によっては、本発明の例示的な方法、本方法を用いるＩＡＴ生成器、等々は、画像アンカテンプレートの決定を実装するために（例えば、デジタルプロセッサによって）実行可能な命令を格納する記憶媒体によって具現される。記憶媒体としては、例えば、磁気ディスクまたは他の磁気記憶媒体、光ディスクまたは他の光記憶媒体、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）または他の電子メモリデバイスまたはチップまたは動作可能式に相互接続されたチップセット、格納されている命令をインターネットまたはローカルエリアネットワークを介してそこから検索できるインターネットサーバ、等々が含まれてもよい。
【００７４】
さらに、様々な上述の、及び他の特徴及び機能またはその代替物が、望ましくは他の多くの異なるシステムまたはアプリケーションに組み合わされてもよいことは認識されるであろう。例えば、これまでに述べたシステム及び方法は画像アンカテンプレートの生成に関連していたが、これまでに述べた方法及びシステムが、画像アンカテンプレートではなくマッチング関数、検出関数、テンプレートスコアリング関数、他を決定するように容易に拡張され得ることは認識されるべきである。また、同じく添付の請求の範囲に包含されることが意図される、現時点では不測である、または予期されていないその様々な代替物、修正、変形または改良が当業者によって続いて行われ得ることも認識されるべきである。
【図１Ａ】
2011243199.tif 000008
【図１Ｂ】
2011243199.tif 000009
【図２】
2011243199.tif 000010
【図３】
2011243199.tif 000011
【図４】
2011243199.tif 000012
【図５】
2011243199.tif 000013
【図６】
2011243199.tif 000014
【図７】
2011243199.tif 000015
【図８】
2011243199.tif 000016