(57)【特許請求の範囲】
【請求項１】
文書画像の認識結果の情報を用いて、該文書画像内の情報を検索する検索装置であって、
キーワードを入力する入力手段と、
前記文書画像から、前記キーワードを構成する任意の文字を探索し、探索された文字をキー文字として、該キー文字の位置情報を抽出する抽出手段と、
前記キー文字の位置情報を基準として、前記キーワードを構成する文字のうち該キー文字より先頭側にある文字の数と、前記文書画像内の文字の代表的なサイズを示す文字サイズ情報および代表的な文字間隔を示す文字間隔情報のうち少なくとも一方とを用いて、該文書画像内の該キーワードに対応する領域の先端位置を計算し、前記キーワードを構成する文字のうち該キー文字より末尾側にある文字の数と、該文字サイズ情報および文字間隔情報のうち少なくとも一方とを用いて、該キーワードに対応する領域の末端位置を計算し、得られた先端位置と末端位置の間の範囲を該キーワードに対応する領域と推定する推定手段と、
推定された領域のうち、前記キーワードに対応する文字列を含む領域の情報を、検索結果として出力する出力手段と
を備えることを特徴とする検索装置。
【請求項２】
前記推定された領域内の文字パターンに基づいて、該推定された領域内の文字列が前記キーワードであるか否かを検証する検証手段をさらに備え、前記出力手段は、該キーワードであることが検証された文字列を含む領域の情報を、前記検索結果として出力することを特徴とする請求項１記載の検索装置。
【請求項３】
文書画像の認識結果の情報を用いて、該文書画像内の情報を検索するコンピュータのためのプログラムを記録した記録媒体であって、
前記プログラムは、
前記文書画像から、キーワードを構成する任意の文字を探索し、探索された文字をキー文字として、該キー文字の位置情報を抽出し、
前記キー文字の位置情報を基準として、前記キーワードを構成する文字のうち該キー文字より先頭側にある文字の数と、前記文書画像内の文字の代表的なサイズを示す文字サイズ情報および代表的な文字間隔を示す文字間隔情報のうち少なくとも一方とを用いて、該文書画像内の該キーワードに対応する領域の先端位置を計算し、前記キーワードを構成する文字のうち該キー文字より末尾側にある文字の数と、該文字サイズ情報および文字間隔情報のうち少なくとも一方とを用いて、該キーワードに対応する領域の末端位置を計算し、得られた先端位置と末端位置の間の範囲を該キーワードに対応する領域と推定し、
推定された領域のうち、前記キーワードに対応する文字列を含む領域の情報を、検索結果として出力する
処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項４】
文書画像の認識結果の情報を用いて、該文書画像内の情報を検索する検索方法であって、
入力手段が、キーワードを入力し、
抽出手段が、前記文書画像から、前記キーワードを構成する任意の文字を探索し、探索された文字をキー文字として、該キー文字の位置情報を抽出し、
推定手段が、前記キー文字の位置情報を基準として、前記キーワードを構成する文字のうち該キー文字より先頭側にある文字の数と、前記文書画像内の文字の代表的なサイズを示す文字サイズ情報および代表的な文字間隔を示す文字間隔情報のうち少なくとも一方とを用いて、該文書画像内の該キーワードに対応する領域の先端位置を計算し、前記キーワードを構成する文字のうち該キー文字より末尾側にある文字の数と、該文字サイズ情報および文字間隔情報のうち少なくとも一方とを用いて、該キーワードに対応する領域の末端位置を計算し、得られた先端位置と末端位置の間の範囲を該キーワードに対応する領域と推定し、
出力手段が、推定された領域のうち、前記キーワードに対応する文字列を含む領域の情報を、検索結果として出力する
ことを特徴とする検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像情報に対する文字認識処理の結果を利用して、画像内の情報を検索する検索装置およびその方法に関する。
【０００２】
【従来の技術】
近年、企業等の組織内では、情報の共有化および迅速な情報利用の観点から、文書を電子化して共有する文書管理システムが使用されている。電子化文書としては、作成時から電子化されているワードプロセッサ文書やプレゼンテーション文書等のテキスト検索可能な文書がよく使用されるが、その他にも、そのままではテキスト検索ができない画像情報も使用される。
【０００３】
画像を文書管理システムに登録する方法としては、後の検索処理のために、画像を文字認識して検索可能なテキスト情報を抽出し、その情報を画像とともに保存する方法が一般的である。
【０００４】
しかし、文字認識処理の認識率は１００％ではなく、認識結果には誤認識も含まれる。また、通常の検索方法では、誤認識を検出することができない。このため、文書中にキーワードの文字列があるにもかかわらず、その文字列が誤認識のためにキーワードと一致せず、検索できない場合がある。
【０００５】
これを防ぐために、文字認識の特性を利用した検索用データ作成方法と、文字認識後のデータに対する検索方法の開発が必要とされている。文字認識後の情報を検索する従来の検索技術としては、例えば、以下のような文献が挙げられる。
（＃１）丸川（Marukawa）、藤澤（Fujisawa）、嶋（Shima ）「認識機能の出力あいまい性を許容した情報検索手法の一検討  認識誤り特性に着目した検索手法の分析評価」電子情報通信学会論文誌vol.J79-D-II, no.5, pp785-794, 1996
（＃２）太田（Ohta）、高須（Takasu）、安達（Adachi）「認識誤りを含む和文テキストにおける全文検索手法」情処学会論文誌vol.39, no.3, pp625-635, 1998
（＃３）糸乗（Itonori ）、尾崎（Ozaki ）「類似文字による日本語単語抽出」信学技報（Technical Report of IEICE）PRMU98-87, pp25-32, 1998
（＃４）今川（Imagawa ）、松川（Matsukawa ）、近藤（Kondo ）、目片（Mekata）「文字毎に認識信頼度を付与した誤認識を含むテキストからの検索手法」信学技報PRMU99-72, pp63-75, 1999
（＃５）近藤、松川、今川、目片「文字認識誤りを含むテキストからのあいまい検索に関する一検討」信学技報PRMU99-73, pp69-75, 1999
（＃６）遊佐（Yusa）、田中（Tanaka）「日本語文書画像に対する文字列検索機能の実現」情報処理、情報メディア研究報告19-1, pp1-8, 1995
（＃７）中西（Nakanishi ）、大町（Omachi）、阿曽（Aso ）「低品位文書画像に対応した高精度なキーワード検索システム」信学技報PRMU98-232, pp97-104, 1999
（＃８）松川、今川、近藤、目片「形状特徴検索併用による文書画像検索の性能向上」信学技報PRMU99-74, pp77-83, 1999
これらの従来技術は、以下のように分類できる。
ａ）文字認識候補とキーワードとの照合を行う方法
文字認識時に認識候補を生成し、検索時に候補を用いて、複数の可能性を考慮しながら検索する。
文献（＃１）
認識候補の数は固定数ではなく、文字毎に類似度のしきい値処理を行い、認識候補を絞り込んでいる（しきい値：４種類）。
ｂ）類似文字によるキーワードの展開方法
ｂ−１）類似文字テーブルによるキーワード文字列展開
１つのキーワードを類似文字情報により複数個に展開して検索する。
文献（＃１）
あらかじめ作っておいたコンフュージョンマトリクスで、単純にキーワードを展開する。１文字に対する類似文字数は固定数ではなく、あらかじめ文字毎に類似度のしきい値処理を行い、類似文字を絞り込んでいる（しきい値：４種類）。
文献（＃２）
誤認識、誤欠落、誤挿入、誤結合、および誤分割を確率的に表した誤り易さに基づく確率を格納したテーブルをあらかじめ作っておき、そのテーブルを用いて、確率が０以外のすべての組み合わせでキーワードを展開する。次に、展開されたキーワードを使って全文検索を行う。そして、検索で抽出された文字列毎に、確率的に求めた文字列の確信度を計算し、しきい値を用いて適否を決める。
ｂ−２）類似文字テーブルによる検索
文字認識された文字列に対して、類似文字テーブルを用いて、検索毎の複数の対応関係の可能性を考慮して検索する。
文献（＃３）
形状の似た複数の文字を１つのカテゴリとして扱い、言語処理で１つに絞り込んで検索する。
【０００６】
辞書作成）
まず、階層的クラスタリングで類似文字のカテゴリ（クラスタ）を作成する。次に、類似文字クラスタを分割し、分割クラスタを再統合する。
【０００７】
識別）
画像に対して、類似文字識別、形態素解析、および詳細識別の順で処理を行い、単語列を生成する。類似文字識別では、１０００個または２０００個のカテゴリが用いられる。
【０００８】
まず、再統合クラスタ→分割クラスタ→類似文字クラスタの階層的識別で、入力文字に最も近い類似文字カテゴリを求め、類似文字カテゴリでできた文字列を作成する。次に、類似文字カテゴリ用の形態素解析で、類似文字カテゴリ内の文字を使った単語を生成する。このとき、形態素解析で１単語に絞り込めなかった文字だけ、詳細識別で決定する。
文献（＃４）
認識結果の確信度（信頼度）に応じて、類似文字テーブルの展開文字数を文字毎に可変にしている。あらかじめ、正しい文字と認識結果、およびその確信度からなる類似文字テーブルを作り、認識時に文字認識結果とその確信度を出力しておく。検索時には、キーワードの文字と認識結果の文字、およびその確信度から、類似文字テーブルを使って検索文字との照合確率を求める。そして、その値が正である場合に認識結果が照合されたものとみなして、検索を行う。この方法は、照合確率が正になる類似文字に限定した検索と同じである。
文献（＃５）
文字毎に付与された文字認識の信頼度と文字数別特定可能確率を用いる文献（＃４）の検索方法に加えて、ｎ文字の単語のうちｋ文字が一致した場合にその単語が一意に特定できる確率を使って検索する。文字数別特定可能確率とは、比較的長い文字列長をもった単語の一部をワイルドカード扱いにして検索を行っても、別の単語が検索されない確率のことである。
ｃ）画像検索方法
画像照合により、文書画像からキーワード画像を直接検索する。
文献（＃６）
まず、文字矩形を正方形とみなして１６等分し、隣り合った部分同士を縦または横に２つ組み合わせてできる長方形を１単位とする。そして、隣同士の２つの長方形の組み合わせのうち、正方形を作るような組み合わせを抽出する。１文字からは、１８セットの組み合わせができる。次に、１単位の中の黒画素密度を求め、隣同士の単位間における黒画素密度の比を００〜１１の２ビットでコード化したものを特徴量とする。１文字当たり３６ビットの特徴量が得られ、照合時には、８ビットの誤りまで許容される。
文献（＃７）
複数の切り出し候補を出力し、切り出し候補毎に特徴ベクトルを登録する。検索時には、キーワード文字の最初の文字から１文字毎にマッチングを行い、距離値が固定しきい値以下である場合に、マッチしたものとする。このとき、前の文字がマッチしたら次の文字は切り出し候補を絞ることで、処理を高速化する。そして、すべての文字の距離値がしきい値以下で、かつ、距離値の和が別の固定しきい値以下の場合に、キーワードを検出する。
ｄ）類似文字検索と画像検索を組み合わせた方法
文献：（＃８）
認識結果の確信度（信頼度）に応じて、類似文字検索と画像検索を切り替える。ｂ−２）における文献（＃４）の類似文字検索を行い、照合条件に合う文字を抽出する。そして、類似文字検索で検出されず、かつ、信頼度が固定しきい値より低い文字が連続する場合に、形状特徴検索を行う。形状特徴検索では、キーワードの文字から推定した幅になるように、隣接する低信頼度の文字を統合して切り出す。次に、文字の特徴量を求め、それとキーワードの文字の特徴量との間のユークリッド距離を求める。そして、距離値が固定しきい値以下であれば、照合されたものとする。
【０００９】
【発明が解決しようとする課題】
しかしながら、上述した従来の検索技術には、次のような問題がある。
ａ）文字認識候補とキーワードとの照合を行う方法
文献（＃１）
検索対象文書画像のフォントによっては、候補文字の中に正解が入らない場合がある。特に、類似文字が多数ある場合には、正解が候補文字の下位になってしまうと、候補文字数の制限から足切りされて、候補文字の中に正解が入らない。
ｂ）類似文字によるキーワードの展開方法
ｂ−１）
文献（＃１）
展開したキーワードの数が、類似文字テーブルの大きさによって指数関数的に増え、計算量が膨大になる。
文献（＃２）
処理対象が広がると、展開したキーワードの数が爆発的に増える。
ｂ−２）
文献（＃３）
言語処理が入るので、複合語や文字数が少ない単語では精度が悪くなる。
文献（＃４）
あらかじめ用意される類似文字テーブルの作り方によっては、精度が期待できない。実際に、低解像度文字では精度が悪いことが、この文献の著者らによって報告されている。
文献（＃５）
複合語や文字数が少ない単語に弱い。また、文献（＃４）の方法と同様に、あらかじめ用意される類似文字テーブルの作り方によっては、精度が期待できない。
ｃ）画像検索方法
文献（＃６）
この方法で使用されている特徴量では、高精度が期待できない。また、テキストのみを使う検索に比べて、計算量が多い。さらに、辞書作成フォント以外では、高精度にならない。
文献（＃７）
テキストのみを使う検索に比べて、計算量が多い。また、キーワードの最初の文字が検出できないと、対応する文字列を検索できない。さらに、辞書作成フォント以外では、高精度にならない。
ｄ）類似文字検索と画像検索を組み合わせた方法
文献（＃８）
文献（＃４）の方法と同様に、あらかじめ用意される類似文字テーブルの作り方によっては、精度が期待できない。
【００１０】
本発明の課題は、文字認識後の情報の検索処理において、上述した検索技術の良い部分を残し、不完全な部分を改良して、より高精度な検索を行う検索装置およびその方法を提供することである。
【００１１】
【課題を解決するための手段】
図１は、本発明の検索装置の原理図である。図１の検索装置は、入力手段１０１、抽出手段１０２、推定手段１０３、および出力手段１０４を備え、文書画像の認識結果の情報を用いて、その文書画像内の情報を検索する。
【００１２】
入力手段１０１は、キーワードを入力し、抽出手段１０２は、文書画像から、キーワードを構成する任意の文字を探索し、探索された文字をキー文字として、そのキー文字の位置情報を抽出する。推定手段１０３は、抽出されたキー文字の位置情報を基準として、そのキーワードを構成する文字のうちキー文字より先頭側にある文字の数と、文書画像内の文字の代表的なサイズを示す文字サイズ情報および代表的な文字間隔を示す文字間隔情報のうち少なくとも一方とを用いて、文書画像内のキーワードに対応する領域の先端位置を計算し、キーワードを構成する文字のうちキー文字より末尾側にある文字の数と、文字サイズ情報および文字間隔情報のうち少なくとも一方とを用いて、キーワードに対応する領域の末端位置を計算し、得られた先端位置と末端位置の間の範囲をキーワードに対応する領域と推定する。出力手段１０４は、推定された領域のうち、キーワードに対応する文字列を含む領域の情報を、検索結果として出力する。
【００１３】
入力手段１０１は、例えば、ユーザにより指定されたキーワードを検索装置に入力し、抽出手段１０２は、入力されたキーワードに含まれる任意の文字を、文書画像から抽出し、それをキー文字として推定手段１０３に渡す。推定手段１０３は、受け取ったキー文字の位置から、そのキー文字を含み、かつ、キーワードを構成する文字の数に対応するような領域を推定する。そして、出力手段１０４は、推定された領域のうち、キーワードに対応する文字列を含む領域の位置および範囲の情報を出力する。
【００１４】
このような検索装置によれば、文書画像に含まれる文字パターンのうち、キーワードを構成する任意の文字に対応するパターンの位置を基準として、自動的にキーワード領域を推定することができる。したがって、キーワードの最初の文字が検出されなくても、他の文字がキー文字として抽出されれば、キーワードに対応する領域の情報が出力される。これにより、検索処理の精度が向上する。
【００１５】
例えば、図１の入力手段１０１は、後述する図１４の入力装置１１３に対応し、図１の抽出手段１０２および推定手段１０３は、図１４のＣＰＵ１１１とメモリ１１２の組み合わせに対応し、図１の出力手段１０４は、図１４の出力装置１１４に対応する。
【００１６】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本実施形態の検索装置は、まず、入力された画像情報の領域識別と文字認識を行い、検索に必要な認識結果を含む検索用情報を生成する。次に、検索用情報を用いて、キーワードを構成する文字を入力画像内で探索し、その文字の位置からキーワードが存在する領域の範囲を推定する。そして、その領域内の画像情報を用いて文字列を検証し、キーワードが抽出されれば、その位置を検索結果として出力する。
【００１７】
図２は、検索用情報生成処理のフローチャートである。検索装置は、まず、検索対象の文書画像を入力する（ステップＳ１）。このとき、ユーザは、紙文書をスキャナ等の画像入力装置で光学的に読み取って、検索装置に入力する。これにより、文書画像が検索装置に登録される。文書画像としては、基本的に白黒の２値画像を想定しているが、カラー画像であっても、前処理として２値化を行うことで、２値画像と同様に扱うことができる。
【００１８】
次に、検索装置は、文書画像を走査し、公知の技術で領域識別を行って、文字領域を抽出する（ステップＳ２）。ここでは、例えば、画像全体をラベリングして黒画素連結領域の外接矩形を抽出し、一定サイズ以上の矩形を図形・表領域候補として抽出する。次に、図・表領域候補の各矩形の内部を対象として罫線抽出を行い、縦横の罫線が抽出されれば、その矩形を表領域と識別する。また、罫線が抽出されなければ、その矩形を図領域と識別する。そして、図・表領域以外の領域を文字領域として抽出する。
【００１９】
次に、文字領域から行（文字列）を抽出し、各行を対象として文字認識を行い、認識結果を含む検索用情報を生成して出力する（ステップＳ３）。このとき、黒画素連結領域の外接矩形を元にして１文字の領域が決められ、画像情報から文字パターンが切り出される。
【００２０】
ただし、文字同士が接触している場合もあるので、接触文字切り出し技術を用いて接触文字を分割し、文字あるいは文字の部分パターンを単位（基本矩形）として、検索用情報を出力する。接触文字切り出し技術としては、例えば、特開平１１−３３８９７５（「文字切り出し処理方式および文字切り出し処理プログラムを記録した記録媒体」）の技術が用いられる。
【００２１】
また、“川”のような分離文字を正確に抽出するため、隣接する基本矩形を統合して文字候補の統合矩形を作り、その矩形についても同様の検索用情報を出力する。
【００２２】
以下では、検索用情報の出力単位となる基本矩形と統合矩形を合わせて、文字矩形と呼ぶことにする。検索用情報の出力は行単位で行われ、１つの行内で各文字矩形の情報をソートして出力する。各文字矩形の検索用情報には、以下のようなものが含まれる。
ａ）文字認識結果情報
この情報は、文字認識により得られた第１位から第ｎ位までの認識候補の情報である（ｎ≧１）。各候補の情報の内容は、文字コード、距離値、評価値、または確信度である。文字コードは、検索するときのために、すべて全角コードに変換しておく。距離値は、認識対象の文字パターンと認識辞書の文字パターンの間の類似度を表し、評価値は、認識候補に対する評価を表す。また、確信度は、認識候補の確からしさを表し、例えば、その候補の距離値と他の候補の距離値を用いて算出される。
ｂ）文字図形特徴情報
この情報は、複数の文字の図形的な特徴を表す情報で、以下の情報を含む。
・文字パターンそのもの
・文字パターンを画像処理した情報（画像特徴）
文字の識別能力がはっきりしている情報が望ましく、具体的には、特徴ベクトル等が用いられる。キーワードの中の１文字の文字コードをキーとして、認識辞書中の特徴ベクトルとこの特徴ベクトルを整合させたときに、同じ文字同士では確実に整合でき、異なる文字同士では整合できないような性質が要求される。例えば、以下のような特徴ベクトルが挙げられる。
１）文字パターンから求めた詳細分類用特徴ベクトル（２８８次元）
文字パターンから多元圧縮法という公知技術を用いて、２８８次元の特徴ベクトルを抽出する（Hai, Kabuyama, Yamamoto「手書き漢字認識の一手法  多元圧縮法と部分パターン法による認識」電子情報通信学会論文誌vol.J68-D no.4, pp773-780, 1985 ）。この方法では、まず、文字パターンの輪郭点毎に、４方向の属性を持たせて方向線素を求め、文字パターンを非線形正規化した後に、方向毎に異なる数の領域に分割する。そして、各領域毎に方向線素の画素数をカウントして、カウント値を規定の順序で並べ、ベクトル化する。これにより、詳細分類用特徴ベクトルが得られる。
２）文字パターンから求めた大分類用特徴ベクトル（１６次元）
上述の詳細分類用特徴ベクトルを元にして、カテゴリ毎に固有値と固有ベクトルを求め、固有値の大きい方から１６本の軸（固有ベクトル）を求める。そして、各軸上にカテゴリの代表ベクトルを投影した値を要素とする１６次元のベクトルを生成する。これにより、大分類用特徴ベクトルが得られる。
【００２３】
これらの特徴ベクトルを用いれば、キーワードの中の１文字の文字コードに相当する認識辞書中の特徴ベクトルと、検索対象文書中の文字の特徴ベクトルを整合させたときに、同じ文字同士では、距離のしきい値を用いることでそれらが同じ文字であると判別できる。また、異なる文字同士では、同じ距離のしきい値を用いて、それらが異なっていると判別できる。
ｃ）文字情報
・文字の位置
例えば、文字の黒画素連結領域の外接矩形の左上および右下の頂点の座標値が用いられる。
・サイズ情報
この情報は、文字が属する行内に含まれる代表的な文字矩形のサイズを表す。例えば、文字が属する行内に含まれる文字矩形の高さと幅の最頻値が用いられる。
・行内の文字間隔距離の代表値
例えば、行内の文字の外接矩形間の距離の平均値が用いられる。
・行内の文字矩形の並びと、文字矩形の順序を表す情報
例えば、横書き行であれば、図３に示すように、基本矩形の間隙部に、左側から順に、０，１，２，．．．のような通し番号を付ける。そして、１つの文字矩形の開始番号として、その矩形の左側の間隙番号を設定し、終了番号として右側の間隙番号を設定して、文字矩形の順序情報を生成する。
【００２４】
図３の文字矩形のうち、矩形１〜矩形９は基本矩形に対応し、矩形１０〜矩形１５は、複数の基本矩形を統合した統合矩形に対応する。例えば、矩形１０は、矩形１と矩形２を統合して生成され、矩形１４は、矩形１、矩形２、および矩形３を統合して生成される。これらの矩形は、１つの行に対する複数の異なる切り出し結果を表している。また、これらの矩形の順序情報は、図４のようになる。
ｄ）行情報
・行番号
行番号は、ページ内の各行に付けられたユニークな番号を表す。
・行方向
行方向は、縦または横を表す。
【００２５】
図５は、出力された検索用情報に基づく全文検索処理のフローチャートである。まず、ユーザは、検索したいキーワードを入力する（ステップＳ１１）。次に、検索装置は、検索用情報を格納した検索対象ファイルから、キーワードを構成する文字（キー文字）を抽出し（ステップＳ１２）、キー文字に基づいて、キーワードに対応する文字列が存在する領域を推定する（ステップＳ１３）。
【００２６】
次に、その領域内の画像情報を認識辞書の情報と比較して、領域内にキーワードが含まれているか否かを検証し、キーワードと整合する文字列を抽出する（ステップＳ１４）。そして、抽出された文字列の位置情報を検索結果として出力し（ステップＳ１５）、処理を終了する。
【００２７】
次に、図６から図１３までを参照しながら、全文検索処理の具体例について説明する。
図６および図７は、図５のステップＳ１２で行われるキー文字抽出処理のフローチャートである。この処理では、認識候補の確信度に基づくキー文字探索が行われる。そして、入力されたキーワードの中の１文字の文字コードと検索対象ファイルの中の文字（第２位以下の認識候補も含む）の文字コードが一致し、かつ、確信度が一定しきい値を越える場合に、その文字をキー文字として抽出する。
【００２８】
検索装置は、まず、キーワードの中の各文字を保持する配列ｋｅｙｃｏｄｅを作成し（図６のステップＳ２１）、キーワードの文字数を変数ｋｅｙｗｏｒｄ＿ｎｕｍに入れる（ステップＳ２２）。次に、                                抽出されたキー文字の数を表す変数ｅｘｔｒａｃｔ＿ｎｕｍに０を入れ（ステップＳ２３）、                                                            検索対象ファイルから認識結果の１文字を抽出する（ステップＳ２４）。
【００２９】
次に、認識候補の順位を表す変数ｉに１を入れ（ステップＳ２５）、配列ｋｅｙｃｏｄｅのインデックスを表す変数ｊに１を入れて（ステップＳ２６）、    ｉ番目の候補の文字コードを、ｋｅｙｃｏｄｅのｊ番目の文字の文字コードと比較する（ステップＳ２７）。
【００３０】
２つの文字コードが一致すれば、次に、ｉ番目の候補の確信度を一定しきい値と比較する（ステップＳ２８）。確信度がしきい値を越えていれば、ステップＳ２４で抽出された文字をキー文字とみなし、ｋｅｙｃｏｄｅのｊ番目の文字コードと、抽出された文字の位置を記録する（ステップＳ２９）。そして、ｅｘｔｒａｃｔ＿ｎｕｍ＝ｅｘｔｒａｃｔ＿ｎｕｍ＋１とおく（ステップＳ３０）。
【００３１】
次に、ｊ＝ｊ＋１とおき（図７のステップＳ３１）、ｊをｋｅｙｗｏｒｄ＿ｎｕｍと比較する（ステップＳ３２）。そして、ｊがｋｅｙｗｏｒｄ＿ｎｕｍ以下であれば、ステップＳ２７以降の処理を繰り返す。
【００３２】
また、ステップＳ２７において２つの文字コードが一致しない場合、および、ステップＳ２８において確信度がしきい値以下である場合は、ステップＳ２４で抽出された文字はキー文字ではないと判断して、ステップＳ３１以降の処理を行う。
【００３３】
ステップＳ３２においてｊがｋｅｙｗｏｒｄ＿ｎｕｍを越えると、次に、ｉ＝ｉ＋１とおき（ステップＳ３３）、ｉを認識候補の数と比較する（ステップＳ３４）。そして、ｉが認識候補の数以下であれば、ステップＳ２６以降の処理を繰り返す。
【００３４】
ｉが認識候補の数を越えると、次に、検索対象ファイルの中の文字が終了したか否かをチェックする（ステップＳ３５）。未処理の文字が残っていれば、次の文字についてステップＳ２４以降の処理を繰り返す。そして、すべての文字が処理されると、処理を終了する。
【００３５】
この処理では、認識候補の確信度の代わりに、評価値や距離値を用いることもできる。評価値を用いた場合は、ステップＳ２８において認識候補の評価値を一定しきい値と比較し、評価値がしきい値を越えていれば、検索対象ファイルの文字をキー文字とみなす。また、距離値を用いた場合は、ステップＳ２８において認識候補の距離値を一定しきい値と比較し、距離値がしきい値を下回れば、検索対象ファイルの文字をキー文字とみなす。
【００３６】
上述したキー文字抽出処理によれば、検索対象ファイルの中の各文字について、複数の認識候補とキーワードを構成する文字とが照合されるので、文書画像中のキー文字が検出され易くなる。また、認識候補の確信度、評価値、または距離値に基づいてキー文字が抽出されるので、キー文字の抽出精度が向上する。
【００３７】
図８および図９は、図５のステップＳ１３で行われるキーワード領域推定処理のフローチャートである。この処理では、抽出されたキー文字の文字情報から、キーワード内におけるその文字の位置を獲得する。そして、キーワード内の位置と、キーワードの文字数や文字幅等の文字範囲情報から、キー文字を囲む推定キーワード領域を求める。例えば、横書きの場合は、キー文字から左右に伸びるキーワード領域が生成され、縦書きの場合は、キー文字から上下に伸びるキーワード領域が生成される。
【００３８】
検索装置は、まず、抽出されたキー文字の１つを指す変数ｉに１を入れ（図８のステップＳ４１）、既抽出キーワード領域の数を表す変数ｋｗｎｕｍに０を入れて（ステップＳ４２）、ｉ番目のキー文字の文字コードと検索対象ファイル内の位置の情報を取得する（ステップＳ４３）。
【００３９】
次に、キー文字の位置、サイズ（キー文字が属する行の文字の幅または高さ）、文字間隔距離等の文字情報と、そのキー文字のキーワード内における位置から、文書画像内におけるキーワード領域を推定する（ステップＳ４４）。
【００４０】
例えば、キーワードとして“富士通研究所”が入力され、キー文字として“通”が抽出された場合を考える。この例では、図１０に示すように、文書画像内にｘｙ座標系が設定され、抽出された文字“通”の文字情報には、文字矩形の左上頂点の座標（ｘ，ｙ）＝（２００，５００）と右下頂点の座標（２５０，５５０）が、位置として記録されている。また、代表的な文字幅は５０ドットであり、文字間隔距離は１０ドットであることが記録されている。
【００４１】
この場合、推定キーワード領域の上端および下端の座標値としては、それぞれ、左上頂点のｙ座標５００および右下頂点のｙ座標５５０が採用され、左端および右端の座標値は、次式により計算される。
左座標：
左上頂点のｘ座標−（文字幅＋文字間隔距離）×（キー文字の左側の文字数）
＝２００−（５０＋１０）×２
＝８０
右座標：
右下頂点のｘ座標＋（文字幅＋文字間隔距離）×（キー文字の右側の文字数）
＝２５０＋（５０＋１０）×３
＝４３０
したがって、推定キーワード領域の範囲を左上および右下頂点の座標を用いて表すと、（８０，５００）−（４３０，５５０）となる。
【００４２】
次に、検索装置は、既に登録されたキーワード領域の１つを指す変数ｊに１を入れ、既抽出キーワード領域との重複フラグ変数ｋｗｎｕｍ２に０を入れて（ステップＳ４５）、推定キーワード領域がｊ番目の既登録キーワード領域        と重複するか否かをチェックする（ステップＳ４６）。
【００４３】
２つのキーワード領域が重複すれば、それらのキーワード領域を囲む矩形領域を新たなキーワード領域として求め、ｊ番目の既登録キーワード領域の座標を更新する（ステップＳ４７）。これにより、ｊ番目の既登録キーワード領域の範囲が新たなキーワード領域の範囲に置き換えられる。そして、ｋｗｎｕｍ２＝１とおく。
【００４４】
次に、ｊ＝ｊ＋１とおき（ステップＳ４８）、ｊとｋｗｎｕｍを比較する（図９のステップＳ４９）。そして、ｊがｋｗｎｕｍ以下であれば、ステップＳ４６以降の処理を繰り返し、ｊがｋｗｎｕｍを越えれば、次に、ｋｗｎｕｍ２の値をチェックする。
【００４５】
ｋｗｎｕｍ２＝０であれば、推定キーワード領域を新規に登録し、ｋｗｎｕｍ＝ｋｗｎｕｍ＋１とおく（ステップＳ５１）。次に、ｉ＝ｉ＋１とおいて（ステップＳ５２）、ｉ番目の抽出キー文字の情報があるか否かをチェックする（ステップＳ５３）。そして、ｉ番目の抽出キー文字があれば、ステップＳ４３以降の処理を繰り返し、抽出キー文字の情報が終了すれば、処理を終了する。
【００４６】
ステップＳ４６において、２つのキーワード領域が重複しなければ、そのままステップＳ４８以降の処理を行い、ステップＳ５０において、ｋｗｎｕｍ２＞０であれば、ステップＳ５２以降の処理を行う。
【００４７】
このようなキーワード領域推定処理によれば、抽出されたキー文字の位置に基づいて、その文字を含むキーワード領域の範囲を精度良く推定することができる。また、キーワードの最初の文字がキー文字として抽出されなくても、他の文字がキー文字として抽出されれば、その文字の位置から対応するキーワード領域を推定することができる。さらに、複数のキー文字が１つのキーワード領域を構成する場合に、そのキーワード領域を正しく抽出することができる。
【００４８】
図１１は、図５のステップＳ１４で行われるキーワード抽出処理のフローチャートである。この処理では、得られた推定キーワード領域の範囲の文字矩形を対象として、文字パターンの画像を認識辞書の対応する文字と整合させ、領域内の文字列が本当にキーワードであるか否かを検証する。
【００４９】
例えば、キーワード領域内の重複しない矩形の組み合わせをすべて求め、得られた組み合わせの各々について、各矩形内の文字パターンから求めた画像特徴と、辞書から求めたキーワード構成文字の画像特徴を整合させる。これらの組み合わせは、それぞれ異なる文字切り出し結果に対応する。そして、整合度が一定しきい値以上（例えば、距離値の合計が一定しきい値以下）の組み合わせが存在する場合に、キーワードが検出されたものとみなす。
【００５０】
例えば、キーワード領域内に図３の文字矩形が含まれる場合、以下のような矩形の組み合わせが考えられる。
・矩形１〜矩形９
・矩形１０、および矩形３〜矩形９
・矩形１０、矩形１３、および矩形４〜矩形９
・矩形１０、矩形１１、および矩形５〜矩形９
・矩形１０〜矩形１２、および矩形７〜矩形９
・矩形１、矩形２、矩形１１、および矩形５〜矩形９
・矩形１、矩形２、矩形１１、矩形１２、および矩形７〜矩形９
・矩形１〜矩形４、矩形１２、および矩形７〜矩形９
・矩形１、矩形１３、および矩形４〜矩形９
・矩形１、矩形１３、矩形４、矩形１２、および矩形７〜矩形９
・矩形１４、および矩形４〜矩形９
・矩形１４、矩形４、矩形１２、および矩形７〜矩形９
・矩形１４、矩形１５、および矩形６〜矩形９
・矩形１０、矩形３、矩形１５、および矩形６〜矩形９
・矩形１、矩形１３、矩形１５、および矩形６〜矩形９
図１１では、１つの推定キーワード領域についての検証処理が示されているが、検索装置は、同様の処理をすべての推定キーワード領域について行い、キーワードが検出された領域だけを、検索結果として出力する。推定キーワード領域内の各組み合わせに含まれる矩形は、あらかじめ、対応する行の先頭に近いものから順にソートされているものとする。
【００５１】
検索装置は、まず、キーワード領域内の矩形の組み合わせの１つに注目し、その組み合わせの最初の矩形をカレント矩形として選択する（ステップＳ６１）。次に、キーワードの中の文字と一致した領域内の文字の数を表す変数ｎｕｍに０を入れ、キーワードの中の文字を指す変数ｋに１を入れて（ステップＳ６２）、再帰的整合処理を呼び出す（ステップＳ６３）。再帰的整合処理では、画像特徴を用いて領域内の各文字パターンとキーワードの文字パターンとを照合し、一致した文字数を復帰値としてｎｕｍに設定する。
【００５２】
次に、復帰値ｎｕｍとキーワードの文字数を比較し（ステップＳ６４）、両者が一致しなければ、同じキーワード領域内に他の組み合わせがあるか否かをチェックする（ステップＳ６５）。他の組み合わせがあれば、その組み合わせについてステップＳ６１以降の処理を繰り返す。
【００５３】
ステップＳ６４において、ｎｕｍとキーワード文字数が一致すれば、キーワードが検出された領域の数をインクリメントして（ステップＳ６６）、ステップＳ６５の処理を行う。そして、ステップＳ６５において、キーワード領域内のすべての組み合わせの検証が終了すれば、処理を終了する。
【００５４】
ステップＳ６３の再帰的整合処理では、まず、キーワード領域内の矩形の文字パターンと文字情報を取得する。その後の処理で用いられる検証方法には、以下のような方法がある。
ａ）すべての矩形の文字パターンについて検証を行う方法
領域内のすべての矩形について、画像情報を用いた整合処理としきい値処理を行い、対象矩形がキーワードを構成する文字か否かを検証する。
【００５５】
具体的には、領域内のすべての矩形について画像情報によるマッチングを行い、しきい値以下の距離の矩形をキーワードの文字と整合したものとみなす。そして、キーワードの文字がすべて領域内の矩形と整合した場合に、キーワードが抽出されたとみなす。この方法によれば、すべての矩形が画像情報を用いて検証されるため、キーワードの抽出精度が向上する。
ｂ）確信度の低い矩形の文字パターンのみについて検証を行う方法
領域内の矩形から、確信度が所定の条件を満たすようなものを除き、残りの矩形を対象として、画像特徴情報を用いた整合処理としきい値処理を行う。
【００５６】
具体的には、領域内の矩形のうち、確信度がしきい値より高い矩形は、既にキーワードの文字と整合がとれているとみなし、確信度がしきい値以下の矩形について、画像情報によるマッチングを行う。そして、しきい値以下の距離の矩形をキーワードの文字と整合したものとみなし、キーワードの文字がすべて領域内の矩形と整合した場合に、キーワードが抽出されたとみなす。この方法によれば、キーワードの抽出精度を損なうことなく、処理時間を削減することができる。
【００５７】
図１２および図１３は、ａ）の検証方法を用いた再帰的整合処理のフローチャートである。検索装置は、まず、カレント矩形の開始番号とその前の矩形の終了番号を比較する（図１２のステップＳ７１）。両者が一致しなければ、次に、カレント矩形の開始番号が０であるか否かをチェックする（ステップＳ７２）。カレント矩形の開始番号が０であれば、次に、カレント矩形の行番号が前の行の行番号＋１であるか否かをチェックする（ステップＳ７３）。
【００５８】
カレント矩形の行番号が前の行の行番号＋１であれば、次に、カレント矩形内の文字の画像特徴（特徴ベクトル等）と、キーワードのｋ番目の文字の画像特徴を比較する（ステップＳ７４）。そして、画像特徴間の距離がしきい値以下であれば、カレント矩形の文字とキーワードのｋ番目の文字が一致したものとみなし、ｎｕｍ＝ｎｕｍ＋１とおく（ステップＳ７５）。
【００５９】
次に、ｋ＋１をキーワードの文字数と比較する（図１３のステップＳ７６）。そして、ｋ＋１がキーワード文字数以下であれば、ｋ＝ｋ＋１とおき（ステップＳ７７）、カレント矩形の次の矩形を新たなカレント矩形に設定する（ステップＳ７８）。次の矩形としては、カレント矩形の終了番号を開始番号として持つ矩形が選択される。そして、再帰的整合処理を呼び出して復帰値ｎｕｍを取得し（ステップＳ７９）、呼び出し元にｎｕｍを返して（ステップＳ８０）、処理を終了する。
【００６０】
ステップＳ７１において、カレント矩形の開始番号と前の矩形の終了番号が一致すれば、ステップＳ７４以降の処理を行う。また、ステップＳ７２において開始番号が０でない場合と、ステップＳ７３において行番号が前の行の行番号＋１でない場合と、ステップＳ７４においてカレント矩形の文字とキーワードのｋ番目の文字が一致しない場合は、そのままステップＳ８０の処理を行う。また、ステップＳ７６において、ｋ＋１がキーワード文字数を越えた場合も、ステップＳ８０の処理を行う。
【００６１】
ｂ）の検証方法を用いた場合は、領域内のすべての矩形ではなく、確信度が高い矩形の間にある矩形を対象にして、図１２および図１３と同様の処理を行う。この場合、図１１のステップＳ６４では、キーワードの中の文字のうち、確信度が高い文字を除いた残りの文字（部分的な文字列）の数がキーワード文字数として用いられる。
【００６２】
また、ｂ）の検証方法において、確信度の代わりに、評価値や距離値を用いて同様の処理を行うこともできる。この場合、キーワード領域内の矩形から、評価値または距離値が所定の条件を満たすようなものを除き、残りの矩形を対象として、整合処理としきい値処理を行う。
【００６３】
本実施形態のパターン抽出装置は、例えば、図１４に示すような情報処理装置（コンピュータ）を用いて構成することができる。図１４の情報処理装置は、ＣＰＵ（中央処理装置）１１１、メモリ１１２、入力装置１１３、出力装置１１４、外部記憶装置１１５、媒体駆動装置１１６、ネットワーク接続装置１１７、および画像入力装置１１８を備え、それらはバス１１９により互いに接続されている。
【００６４】
メモリ１１２は、例えば、ＲＯＭ（read only memory）、ＲＡＭ（random access memory）等を含み、処理に用いられるプログラムとデータを格納する。ＣＰＵ１１１は、メモリ１１２を利用してプログラムを実行することにより、必要な処理を行う。
【００６５】
入力装置１１３は、例えば、キーボード、ポインティングデバイス、タッチパネル等であり、ユーザからの指示や情報の入力に用いられる。出力装置１１４は、例えば、ディスプレイ、プリンタ、スピーカ等であり、ユーザへの問い合わせや処理結果の出力に用いられる。
【００６６】
外部記憶装置１１５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク（magneto-optical disk）装置等である。情報処理装置は、この外部記憶装置１１５に、上述のプログラムとデータを保存しておき、必要に応じて、それらをメモリ１１２にロードして使用することができる。また、外部記憶装置１１５は、検索対象ファイルを格納するデータベースとしても用いられる。
【００６７】
媒体駆動装置１１６は、可搬記録媒体１２０を駆動し、その記録内容にアクセスする。可搬記録媒体１２０としては、メモリカード、フロッピーディスク、ＣＤ−ＲＯＭ（compact disk read only memory ）、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。ユーザは、この可搬記録媒体１２０に上述のプログラムとデータを格納しておき、必要に応じて、それらをメモリ１１２にロードして使用することができる。
【００６８】
ネットワーク接続装置１１７は、ＬＡＮ（local area network）等の任意の通信ネットワークへの接続に用いられ、通信に伴うデータ変換を行う。情報処理装置は、上述のプログラムとデータをネットワーク接続装置１１７を介して外部の装置から受け取り、それらをメモリ１１２にロードして使用することができる。
【００６９】
画像入力装置１１８は、例えば、ＣＣＤカメラやスキャナ等の撮像装置であり、カラー画像を含む文書画像の入力に用いられる。
図１５は、図１４の情報処理装置にプログラムとデータを供給することのできるコンピュータ読み取り可能な記録媒体を示している。可搬記録媒体１２０や外部のデータベース１２１に保存されたプログラムとデータは、メモリ１１２にロードされる。そして、ＣＰＵ１１１は、そのデータを用いてそのプログラムを実行し、必要な処理を行う。
【００７０】
以上説明した実施形態では、文字位置の情報として矩形の座標を用いているが、本発明では、その他の任意の形状の座標を用いることができる。また、推定キーワード領域として、矩形以外の形状を用いてもよい。
（付記１）  文書画像の認識結果の情報を用いて、該文書画像内の情報を検索する検索装置であって、
キーワードを入力する入力手段と、
前記文書画像から、前記キーワードを構成する任意の文字をキー文字として抽出する抽出手段と、
前記キー文字の位置情報に基づいて、前記文書画像内の前記キーワードに対応する領域を推定する推定手段と、
推定された領域の情報に基づいて、検索結果を出力する出力手段と
を備えることを特徴とする検索装置。
（付記２）  前記抽出手段は、前記文書画像内の文字の複数の認識候補と前記キーワードを構成する任意の文字を比較して、前記キー文字を抽出することを特徴とする付記１記載の検索装置。
（付記３）  前記抽出手段は、前記文書画像内の文字の認識候補の確信度、評価値、および距離値のうちの１つを用いて、前記キー文字を抽出することを特徴とする付記１記載の検索装置。
（付記４）  前記推定手段は、前記文書画像内の文字のサイズ情報および文字間隔の情報のうち少なくとも一方と、前記キー文字の位置情報とを用いて、前記キーワードに対応する領域の範囲を計算することを特徴とする付記１記載の検索装置。
（付記５）  前記推定された領域内の文字パターンに基づいて、該推定された領域内の文字列が前記キーワードであるか否かを検証する検証手段をさらに備え、前記出力手段は、該キーワードであることが検証された文字列を含む領域の情報を、前記検索結果として出力することを特徴とする付記１記載の検索装置。
（付記６）  前記検証手段は、前記推定された領域内のすべての文字パターンを対象として、画像特徴情報を用いた整合処理としきい値処理を行い、対象文字パターンがキーワードを構成する文字か否かを検証することを特徴とする付記５記載の検索装置。
（付記７）  前記検証手段は、前記推定された領域内の文字パターンから、確信度、評価値、および距離値のうちの１つが所定の条件を満たすような文字パターンを除き、残りの文字パターンを対象として、画像特徴情報を用いた整合処理としきい値処理を行い、対象文字パターンがキーワードを構成する文字か否かを検証することを特徴とする付記５記載の検索装置。
（付記８）  前記検証手段は、複数の文字切り出し結果に対応する、文字パターンの複数の組み合わせの各々について、画像特徴情報を用いた整合処理としきい値処理を行い、各組み合わせが前記キーワードに対応するか否かを検証することを特徴とする付記５記載の検索装置。
（付記９）  あらかじめ前記文書画像を文字認識して、認識結果を含む検索用情報を生成する生成手段と、該検索用情報を検索対象ファイルとして格納する格納手段をさらに備え、前記抽出手段と推定手段は、該格納手段に格納された該検索用情報を用いて処理を行うことを特徴とする付記１記載の検索装置。
（付記１０）  文書画像の認識結果の情報を用いて、該文書画像内の情報を検索するコンピュータのためのプログラムを記録した記録媒体であって、
前記プログラムは、
前記文書画像から、キーワードを構成する任意の文字をキー文字として抽出し、
前記キー文字の位置情報に基づいて、前記文書画像内の前記キーワードに対応する領域を推定し、
推定された領域の情報に基づいて、検索結果を出力する
処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
（付記１１）  文書画像の認識結果の情報を用いて、該文書画像内の情報を検索する検索方法であって、
キーワードを指定し、
前記文書画像から、前記キーワードを構成する任意の文字をキー文字として抽出し、
前記キー文字の位置情報に基づいて、前記文書画像内の前記キーワードに対応する領域を推定し、
推定された領域の情報に基づいて、検索結果を提示する
ことを特徴とする検索方法。
【００７１】
【発明の効果】
本発明によれば、画像内の情報の検索処理において、文字認識結果が有効に利用され、高精度な検索を行うことができる。これにより、従来では誤認識のために検索できなかった文書画像中の単語についても、キーワードによる全文検索が可能になる。
【図面の簡単な説明】
【図１】本発明の検索装置の原理図である。
【図２】検索用情報生成処理のフローチャートである。
【図３】文字矩形を示す図である。
【図４】文字矩形の順序情報を示す図である。
【図５】全文検索処理のフローチャートである。
【図６】キー文字抽出処理のフローチャート（その１）である。
【図７】キー文字抽出処理のフローチャート（その２）である。
【図８】キーワード領域推定処理のフローチャート（その１）である。
【図９】キーワード領域推定処理のフローチャート（その２）である。
【図１０】キーワード領域を示す図である。
【図１１】キーワード抽出処理のフローチャートである。
【図１２】再帰的整合処理のフローチャート（その１）である。
【図１３】再帰的整合処理のフローチャート（その２）である。
【図１４】情報処理装置の構成図である。
【図１５】記録媒体を示す図である。
【符号の説明】
１０１  入力手段
１０２  抽出手段
１０３  推定手段
１０４  出力手段
１１１  ＣＰＵ
１１２  メモリ
１１３  入力装置
１１４  出力装置
１１５  外部記憶装置
１１６  媒体駆動装置
１１７  ネットワーク接続装置
１１８  画像入力装置
１１９  バス
１２０  可搬記録媒体
１２１  データベース
【図１】
0003917349.tif 000002
【図２】
0003917349.tif 000003
【図３】
0003917349.tif 000004
【図４】
0003917349.tif 000005
【図５】
0003917349.tif 000006
【図６】
0003917349.tif 000007
【図７】
0003917349.tif 000008
【図８】
0003917349.tif 000009
【図９】
0003917349.tif 000010
【図１０】
0003917349.tif 000011
【図１１】
0003917349.tif 000012
【図１２】
0003917349.tif 000013
【図１３】
0003917349.tif 000014
【図１４】
0003917349.tif 000015
【図１５】
0003917349.tif 000016