(57)【特許請求の範囲】
【請求項１】
文書画像と該文書画像について予め生成されたビット分布及び該文書画像の記述子の集合とを対応付けて格納するデータベースを検索して照会文書画像とマッチング処理を行うデータ処理方法であって、
前記照会文書画像のビット分布を生成し、前記生成した照会文書画像のビット分布と前記データベースに格納される各々の文書画像のビット分布とに基づいて、前記データベースに格納される少なくとも一つ以上の文書画像を候補集合として選出する粗マッチング処理ステップと、
前記照会文書画像中の各テキスト行の上部に存在する上端点の集合と下部に存在する下端点の集合とを抽出し、前記抽出した上端点の集合及び下端点の集合に基づいて前記照会文書画像中のテキスト行を検出し、前記検出されたテキスト行内の選択された上端点の集合間の距離及び選択された下端点の集合間の距離に基づいて記述子の集合を生成し、前記照会文書画像の前記生成した記述子の集合と前記候補集合を構成する文書画像のそれぞれが有する記述子の集合とに基づいて、前記候補集合から前記照会文書画像に一致する文書画像を選出する詳細マッチング処理ステップと、
からなることを特徴とするデータ処理方法。
【請求項２】
前記粗マッチング処理ステップは、
前記照会文書画像のビット分布に対してスペクトル解析を行って前記照会文書画像の大局的統計量を求め、
前記照会文書画像の大局的統計量と前記データベースに格納される各文書画像の大局的統計量とに基づいて前記データベースに格納される少なくとも一つ以上の文書画像を初期候補の集合として選出し、
前記照会文書画像のビット分布と前記選出された初期候補の集合に含まれる各文書画像のビット分布とに基づいて、前記データベースに格納される少なくとも一つ以上の文書画像を前記候補集合として選出することを特徴とする請求項１に記載のデータ処理方法。
【請求項３】
前記粗マッチング処理ステップは、
前記照会文書画像のビット分布を生成し、前記生成した照会文書画像のビット分布と前記データベースに格納される各々の文書画像のビット分布との相互相関をとり、
該相互相関に基づいて前記データベースに格納される少なくとも一つ以上の文書画像を前記候補集合として選出することを特徴とする請求項１に記載のデータ処理方法。
【請求項４】
前記大局的統計量は、前記照会文書中の支配的な行間隔の推定値、前記照会文書のテキスト量に関する推定値、前記照会文書中のテキスト位置に関する推定値、前記照会文書画像におけるテキスト密度の推定値、のいずれかであることを特徴とする請求項２に記載のデータ処理方法。
【請求項５】
前記相互相関は、前記照会文書画像のビット分布と前記データベースに格納される各々の文書画像のビット分布との各々のベクトル積を生成することによってとられることを特徴とする請求項３に記載のデータ処理方法。
【請求項６】
前記候補集合は、前記各々のベクトル積が閾値を超えた前記データベースに格納される文書画像の集合であることを特徴とする請求項５に記載のデータ処理方法。
【請求項７】
前記選択された上端点は各テキスト行のアセンダ領域内の上端点であり、前記選択された下端点は各テキスト行のデセンダ領域内の下端点であることを特徴とする請求項１乃至６のいずれか１に記載のデータ処理方法。
【請求項８】
前記アセンダ領域及びデセンダ領域は、前記テキスト行中の第１のテキスト行のｘ−高さラインより上の領域を前記第１のテキスト行の前記アセンダ領域と定め、前記第１のテキスト行のベースラインより下の領域を前記第１のテキスト行の前記デセンダ領域と定めることを特徴とする請求項７に記載のデータ処理方法。
【請求項９】
前記ビット分布は、前記文書画像中の複数の画素行のそれぞれを符号化するために必要なビット数に基づいて生成されることを特徴とする請求項１乃至８のいずれか１に記載のデータ処理方法。
【請求項１０】
前記照会文書画像及び前記文書画像は所定の圧縮形式で圧縮されていることを特徴とする請求項１乃至９のいずれか１に記載のデータ処理方法。
【請求項１１】
前記所定の圧縮形式は、各画素ランが複数の符号化モード中の１つの符号モードによって符号化される方法で圧縮されていることを特徴とする請求項１０記載のデータ処理方法。
【請求項１２】
前記詳細マッチング処理ステップによって選出された文書画像を表示装置に表示するステップをさらに含むことを特徴とする請求項１乃至１１のいずれか１に記載のデータ処理方法。
【請求項１３】
文書画像と該文書画像について予め生成されたビット分布及び該文書画像の記述子の集合とを対応付けて格納するデータベースと、
照会文書画像のビット分布を生成し、前記生成した照会文書画像のビット分布と前記データベースに格納される各々の文書画像のビット分布とに基づいて、前記データベースに格納される少なくとも一つ以上の文書画像を候補集合として選出する粗マッチング処理手段と、
前記照会文書画像中の各テキスト行の上部に存在する上端点の集合と下部に存在する下端点の集合とを抽出し、前記抽出した上端点の集合及び下端点の集合に基づいて前記照会文書画像中のテキスト行を検出し、前記検出されたテキスト行内の選択された上端点の集合間の距離及び選択された下端点の集合間の距離に基づいて記述子の集合を生成し、前記照会文書画像の前記生成した記述子の集合と前記候補集合を構成する文書画像のそれぞれが有する記述子の集合とに基づいて、前記候補集合から前記照会文書画像に一致する文書画像を選出する詳細マッチング処理手段と、
を備えることを特徴とするデータ処理装置。
【請求項１４】
前記粗マッチング処理手段は、
前記照会文書画像のビット分布に対してスペクトル解析を行って前記照会文書画像の大局的統計量を求め、
前記照会文書画像の大局的統計量と前記データベースに格納される各文書画像の大局的統計量とに基づいて前記データベースに格納される少なくとも一つ以上の文書画像を初期候補の集合として選出し、
前記照会文書画像のビット分布と前記選出された初期候補の集合に含まれる各文書画像のビット分布とに基づいて、前記データベースに格納される少なくとも一つ以上の文書画像を前記候補集合として選出することを特徴とする請求項１３に記載のデータ処理装置。
【請求項１５】
前記粗マッチング処理手段は、
前記照会文書画像のビット分布を生成し、前記生成した照会文書画像のビット分布と前記データベースに格納される各々の文書画像のビット分布との相互相関をとり、
該相互相関に基づいて前記データベースに格納される少なくとも一つ以上の文書画像を前記候補集合として選出することを特徴とする請求項１３に記載のデータ処理装置。
【請求項１６】
前記大局的統計量は、前記照会文書中の支配的な行間隔の推定値、前記照会文書のテキスト量に関する推定値、前記照会文書中のテキスト位置に関する推定値、前記照会文書画像におけるテキスト密度の推定値、のいずれかであることを特徴とする請求項１４に記載のデータ処理装置。
【請求項１７】
前記相互相関は、前記照会文書画像のビット分布と前記データベースに格納される各々の文書画像のビット分布との各々のベクトル積を生成することによってとられることを特徴とする請求項１５に記載のデータ処理装置。
【請求項１８】
前記候補集合は、前記各々のベクトル積が閾値を超えた前記データベースに格納される文書画像の集合であることを特徴とする請求項１７に記載のデータ処理装置。
【請求項１９】
前記選択された上端点は各テキスト行のアセンダ領域内の上端点であり、前記選択された下端点は各テキスト行のデセンダ領域内の下端点であることを特徴とする請求項１３乃至１８のいずれか１に記載のデータ処理装置。
【請求項２０】
前記アセンダ領域及びデセンダ領域は、前記テキスト行中の第１のテキスト行のｘ−高さラインより上の領域を前記第１のテキスト行の前記アセンダ領域と定め、前記第１のテキスト行のベースラインより下の領域を前記第１のテキスト行の前記デセンダ領域と定めることを特徴とする請求項１９に記載のデータ処理装置。
【請求項２１】
前記ビット分布は、前記文書画像中の複数の画素行のそれぞれを符号化するために必要なビット数に基づいて生成されることを特徴とする請求項１３乃至２０のいずれか１に記載のデータ処理装置。
【請求項２２】
前記照会文書画像及び前記文書画像は所定の圧縮形式で圧縮されていることを特徴とする請求項１３乃至２１のいずれか１に記載のデータ処理装置。
【請求項２３】
前記所定の圧縮形式は、各画素ランが複数の符号化モード中の１つの符号モードによって符号化される方法で圧縮されていることを特徴とする請求項２２記載のデータ処理装置。
【請求項２４】
前記詳細マッチング手段によって選出された文書画像を表示する表示手段をさらに備えることを特徴とする請求項１３乃至２３のいずれか１に記載のデータ処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文書管理の分野に係り、特に、文書マッチングの分野に関する。
【０００２】
【従来の技術】
電子文書画像の生成及び伝送が容易になったため、文書を自動的に追加したり検索したりする機能を持つデータベースに文書画像が保存されるのが一般的になってきた。その結果、追加しようとする文書と同じものがデータベース内に既に存在しているか否かを効率よく確実に判定できるようにすることが、ますます重要になっている。さもないと、同じ文書が重複してデータベースに格納され貴重な記憶スペースを浪費することになる。データベース内に、ある文書と同じものが入っているか否かを判定することを文書マッチングと言う。
【０００３】
現在利用できる画像内容をベースにした検索システムでは、色、テクスチャ、形態の特徴が文書マッチングに利用されることが多い。大部分が２階調（bitonal）で形態及びテクスチャが似ている文書画像のマッチングをしようとすると、
様々な問題が起こる。
【０００４】
一般的な文書マッチング手法の１つは、光学的文字認識（ＯＣＲ）を行ったのち、テキスト・ベースの探索を行う方法である。もう１つの方法は、文書のレイアウトを解析し、構造的に類似した文書をデータベースから探す方法である。残念ながら、この２つの方法はいずれも計算量の多いページ解析を必要とする。計算による解析を減らすための一方法は、文書を確実に識別できるように特別に設計されたマーカーを文書に埋め込む方法である。
【０００５】
最近、テキスト・ベースの方法に代わるものとして、画像から特徴量を直接抽出することによりＯＣＲよりも優れた効率性及び頑健性を得ようとする方法が開発された。そのような特徴量の１例はワード長である。文書中のワード長の系列をインデックスとして利用し、照会によって生成された各画像でのヒット数を比較することにより一致文書を識別し得る。もう１つの方法は、ＡＳＣＩＩテキスト検索のための探索キーのコンパイルに利用できる文字形状コード（ＣＳＣ）の小集合へ、アルファベット文字をマッピングする方法である。ＣＳＣは、テキスト画像から、ベースライン及びｘ−高さラインに対する連結成分の相対的位置に基づいて得ることもできる。このように、ＣＳＣは文書画像中のワード検出のために利用できる。十分な長さの先頭のテキスト行から抽出したＣＳＣの短系列を用いて多重インデックスを作ることにより、文書重複検出にもＣＳＣが適用されている。
【０００６】
以上に述べた方法の大きな欠点は、本質的にテキスト行ベースの方法であることである。通常、行切り出し、ワード切り出し、あるいは、文字切り出しさえも行う必要がある。テキスト・ベースでないある方法では、水平射影に基づいて重複検出がなされる。水平射影のウェーブレット係数ベクトル間の距離で、文書の類似度を表す。この方法は、低品質の文書やテキスト量が少ない文書に対し、テキスト・ベースの方法より高性能である。
【０００７】
データベース内の文書画像の大部分は圧縮された形で格納されているので、圧縮ファイルに対して文書マッチングを行うのが有利である。圧縮ファイルに対し文書マッチングを行うのであれば、伸長と再圧縮の必要がなくなり、必要メモリ量の削減により商用化も容易になる。当然のことながら、圧縮ファイルのマッチングをしようとすると、また別の問題が生じる。ＣＣＩＴＴグループ４圧縮ファイルについては、パスコードが類似文書の識別に役立つ情報を含んでいることが分かっている。ある従来技術の方法によれば、小テキスト領域からパスコードを抽出してハウスドルフ（Hausdorff）距離と共に利用することにより、同じ文書を高い割合で正確に識別する。しかしながら、ハウスドルフ距離の計算は計算量が多く、また、距離計算の回数がデータベースの大きさに比例して増加する。
【０００８】
【発明が解決しようとする課題】
よって、本発明の主要な目的は次の通りである。
（１）少ない計算量で高精度の文書マッチングが可能な、テキスト・ベースでもテキスト行ベースでもない方法及び装置を提供すること。
（２）文書画像が圧縮されている場合においても、文書画像の伸長を行うことなく、少ない計算量で高精度の文書マッチングが可能な方法及び装置を提供すること。
（３）文書画像のノイズ、変形に対して頑健な文書マッチングが可能な方法及び装置を提供すること。
以上の目的のより具体的な内容並びにその他の目的は、以下の説明から明瞭になろう。
【０００９】
【課題を解決するための手段】
上記目的を達成するため、本発明の一態様によれば、照会文書がデータベース内の複数の文書中の１つ以上と一致するか判定するため、照会文書中の複数の画素行の各行を符号化するために必要とされるビット数に基づいて、照会文書のビット分布(bit  profile)が生成される。そして、このビット分布とデータベース内の複数の文書に関するビット分布との比較により、１つ以上の候補文書が割り出される。この１つ以上の候補文書に対しさらに詳細なマッチングを行うために、照会文書の端点特徴が検出され、この端点特徴の位置に基づき照会文書に関する記述子の集合が生成される。この生成された記述子の集合と、１つ以上の候補文書に関する記述子の集合との比較により、１つ以上の候補文書の少なくとも１つと照会文書が一致するか判定される。
【００１０】
以上に述べた本発明の特徴及びその他の特徴は、添付図面及び以下の詳細な説明によって明らかになろう。
【００１１】
【発明の実施の形態】
以下、本発明の実施の形態について様々な実施例によって説明する。また、以下においては、主にＣＣＩＴＴグループ４圧縮文書を対象として説明するが、本発明はそれに限定されるものではなく、他の形式の文書、例えばＣＣＩＴＴグループ３の圧縮文書やＴＩＦＦ形式のファイルにも適用し得るものである。
【００１２】
また、次のような語句又は略語を用いるが、別の意味が前後関係から明白である場合を除いて、以下の定義が適用される。
・検索率(recall  rate)：データベースから適切な一致文書が選び出される割合
・ＭＭＲ：Modified  Modified  Relative  Element  Address  Designateの略語
・テキスト密度：単位領域あたりのテキスト行数（例えば５行／インチ）
・ＣＣＩＴＴ：国際電信電話諮問委員会
・ＴＩＦＦ：Tagged  Image  File  Formatの略語
・Ｇ３圧縮又はグループ３圧縮：ＣＣＩＴＴ勧告Ｔ．４に記載の文書画像圧縮方式
・Ｇ４圧縮又はグループ４圧縮：ＣＣＩＴＴ勧告Ｔ．６に記載の文書画像圧縮方式
・文書画像：１枚の紙又は同様の媒体のデジタル画像
・走査線：文書画像中の１つの画素行
・ハーフトーン：分離した黒と白のドットによるグレースケール画像の模擬画像
・ダウンサンプル：平均化することによって、又は、他の方法で複数画素を１画  素に統合することによって、解像度を下げる手法
・ハフマン・コード：画素ラン符号化用ビット・コード
【００１３】
図１は、一実施例による２段階文書マッチングの概要を示す。粗マッチング段階１５において、圧縮された照会文書１２が走査されビット分布(bit  profile)が生成される。このビット分布から、行間隔や文字高さなどの大局的統計量が計算され、これを用いることによって画像データベース１４内の探索すべき文書の範囲が絞られる。次に、前記ビット分布が、探索範囲内の文書に関して予め計算されているビット分布と比較されることにより、詳細マッチング段階２０のための候補１７が選び出される。粗マッチング段階１５で複数の候補１７が得られた場合、詳細マッチング段階２０において、詳細マッチングのための端点特徴の集合が照会文書から抽出される。端点特徴は、ページのスキュー推定や向き推定など、様々なレベルの処理に必要な情報を含んでいる。さらに、端点特徴は、安定であり、対称的であり、また、グループ４圧縮ファイルなどの（これに限定されない）一般的に用いられる圧縮ファイルから容易に計算可能である。詳細マッチング段階２０において、抽出された端点特徴を用いることにより、高い確率で一致文書２１が正確に識別される。
【００１４】
《１．粗マッチング段階》
粗マッチング段階１５の主目的は、候補集合を高い検索率で得ることである。したがって、使用される特徴量は、計算が簡単であって、一般的な画像変形に強いものである必要がある。伸長を行うことなく得られる、最もわかりやすい特徴量はファイル・サイズである。しかし残念ながら、オリジナル画像と写真複写画像とではハーフトーン品質が一致しないため、あるいは、文書の周縁近傍でのハーフトーン効果により、圧縮ファイルのサイズは一致すべき文書間でも大きく異なることがある。同じように利用しやすく、情報量がずっと多いのは、各走査線の圧縮後のサイズである。
【００１５】
図２は、一実施例による粗マッチング段階の説明図である。まず、Ｇ４又は他の圧縮方法により圧縮された照会文書１２を１回走査することにより、圧縮ビット分布２５を生成する。次に、このビット分布２５に対しスペクトル解析手法を適用することにより頑健な大局的統計量を生成する。この照会文書１２の大局的統計量を、データベース内の文書画像に関し予め計算された大局的統計量２７と比較することにより、初期候補の集合を生成する。これら初期候補に関して予め計算されたビット分布２９と照会文書１２のビット分布２５との相互相関をとることにより、順位付けされた候補１７の集合を含む仮説を生成する。相互相関によって高い確信度で一致するものが得られた場合には、これ以降の処理を省いてもよい。
【００１６】
《１．１  ビット分布(bit  profile)の抽出》
グループ４圧縮規格は、各走査線が上の走査線を基準にして符号化される２次元のランレングス・ベースの符号化方式（ＭＭＲ）を規定している。この２つの走査線上の連続したランのパターンに応じて、適切なハフマン・コードが生成される。ＭＭＲ符号化は決定論的であるため、同じ画像パターンであれば、それが文書中のどこに位置していようと、同様の圧縮比が得られる。したがって、各画素行の符号化に要するビット数は、計算するのに都合のよい特徴量である。一般的に、ハーフトーンは符号化するのに最も多くのビットを必要とし、テキストはそれより少ないビット数しか必要とせず、背景はさらに少ないビット数しか必要としない。殆どがテキストで横向きの画像の場合、そのビット分布にテキスト行に対応したピークと谷が現れる。テキスト行によって生じるピークと谷の例が図３に示すビット分布２５の領域４１に見られる。このビット分布２５は、文書画像４０の圧縮データから生成されたものである。
【００１７】
インク濃度の水平射影（例えば、各走査線上の黒画素の平均個数）とは異なり、ビット分布(bit  profile)からどこに情報が実際にあるかわかる。例えば、写真複写された文書の周縁部にしばしば出現する大きな黒領域（例えば、図３の領域４３）は、ビット分布２５には殆ど影響を及ぼさないが、これに対し、インク濃度分布には大きなピークができるだろう。実際、ページを反転表示しても、ビット分布２５はそれほど変わらないであろう。また、ビット分布２５は、インク濃度分布よりも、走査線上のインク分布に関する多くの構造情報を伝える。文書で普通に使用されるポイント・サイズの範囲では、全ページ幅の各テキスト行の（正規化単位の）圧縮率はほぼ均一であり、したがって、テキストとハーフトーンが同様のインク濃度を持つことがあったとしても、テキスト行をハーフトーン部分と区別することが可能になる。
【００１８】
《１．２  仮説の生成》
多くの場合、ビット分布(bit  profile)が有する情報量はただ１つの文書を一意に同定するには少なすぎる。しかし、そっくりな文書は同様のビット分布を持つのが普通である。距離計算に基づいてビット分布を直接的に比較する方法では、ビット分布が相対的に垂直方向に少し平行移動するだけでも失敗する可能性がある。そこで、少なくとも一実施例にあっては、相互相関が用いられる。ビット分布ベクトルの相互相関は、それら分布のフーリエ変換の積として効率的に計算することができる。また、相互相関によって垂直方向のレジストレーションが求まり、これは局所的特徴を抽出するための２つの画像の対応部分を割り出すのに利用できるであろう。計算コストをさらに削減するため、文書の大局的統計量が計算されて探索範囲の絞り込みに利用される。
【００１９】
ビット分布から、いくつかの大局的統計量を抽出できる。ビット分布の周期性は、スペクトル特性が統計的モーメントより有用であることを示唆する。支配的な行間隔、テキスト行数及びテキストの位置は良好な第１段階の特徴付けを与えるが、これら統計量はスペクトル領域においてビット分布から容易に求めることができる。一実施例によれば、ビット分布の周波数成分の解析のためにパワースペクトル密度（ＰＳＤ）が用いられる。
【００２０】
図３に、ビット分布２５から計算されたＰＳＤ４５を示す。照会文書４０（又はその圧縮データ）の支配的な行間隔は、ＰＳＤ４５の最も高いピーク４７から直接計算できる。照会文書４０のテキスト行数の定量的な目安はスペクトル解析では与えられないが、ＰＳＤ４５におけるピーク周波数でのエネルギー（矢線４９で示す）はページ上のテキスト量の良好な目安である。一実施例によれば、支配的な行間隔の周波数を中心にした帯域フィルタをビット分布２５に適用することにより、照会文書中のテキスト行の位置が推定される。フィルタ処理後の信号はテキスト位置で振幅が大きくなることは、テキスト・エネルギー分布５１に示す通りである。位相群遅延グラフ５３（ラジアン単位でプロット）において一定した値の小さな領域５５で示すように、位相がリニアなビット分布の区間は、テキスト・ブロックとよく一致する。一実施例によれば、テキスト・エネルギー分布５１の重心５９と、９０％エネルギー区間の幅６０が、テキストの位置と密度の推定値として用いられる。一実施例によれば、テキストの位置及び密度が、ピーク周波数及び全テキストエネルギーとともに、データベース画像空間内に探索ウインドウを定めるための大局的統計量として用いられる。他の実施例では、これ以外の大局的統計量又は大局的統計量の別の組合せが用いらることもある。
【００２１】
《１．３  特徴解析》
ここで、ビット分布特徴と大局的統計量の、様々な変形に対する頑健性は検討に値する。図４は、２つの一致すべき文書画像間によく見られる変形のいくつかを示す。これらの問題の解析において重要な着目点は次のとおりである。２つのページの間に相対的なスキューがなければ、ノイズの多いほうの画像のビット分布は、ノイズの少ないほうの画像のビット分布に、ノイズの多いほうの画像上のその他全てのもののビット分布が付加された、すなわち加算されたものである。前述のように、ページの上部と側部にある大きな一様に黒い領域６１，６３は、ビット分布にはほとんど影響を及ぼさない。しかし、ハーフトーンにディザ化されたグレー領域（例えば領域６５）によって、ビット分布は大きく変化する可能性がある。ページの上部又は下部のハーフトーン部分は、孤立したピークとしてビット分布に現れるが、それらの局所的平均はテキスト行にしては高すぎるので検出して除去することができる。ページの長手方向に沿うハーフトーン部分は、ビット分布にランダムなノイズを加える。しかし、このようなランダムなノイズは、通常、密度が極めて均一であるため、ＰＳＤにはそれほど影響を及ぼさない。他方、ページの片側にある関係のないテキスト６６はもっと大きな影響をＰＳＤに及ぼすことがある。このページの片側にある無関係なテキスト６６のテキストエネルギーは、その行間隔と本体テキストの行間隔とが同じ場合には本体テキストのテキスト・エネルギーに吸収されるが、それらの行間隔が異なる場合には、別の、通常はもっと小さなピークを作る。
【００２２】
最も重大な欠陥の１つは、ページ上の画像の回転によって生じるスキューである。回転６７は、ビット分布において水平射影を局所的に平均化させる作用をし、ピークを低くし谷を浅くする。スキューが大きくなればなるほど、平滑化作用も強くなる。ビット分布の平滑化は、支配的な周波数を変化させないが、エネルギー分布を変化させ、ピーク周波数でのエネルギーをスペクトルの低い側へ押しやり、検出をずっと難しくさせる。これが図４のＰＳＤ６９に例示されている。図４において、パワー密度７２と同７４はそれぞれスキューのない画像７１とスキューのある画像７３についてプロットしたものである。一実施例によれば、スペクトル評価の前に、ビット分布に対し低周波エネルギーを除去するための前処理が施される。大局的統計量は、概して、画像の歪みに対し頑健である。しかし、ビット分布の相互相関は画像の歪みに対する耐性が弱い。
【００２３】
これ以外にも、解像度や符号化形式などビット分布の変動をもたらす関連要因がある。グループ４圧縮では２次元符号化と固定ハフマン符号化テーブルが用いられる結果、圧縮に必要とされるビット数はランの長さに比例しては増減しない。（例えば拡大によって生じる）水平解像度の変化はビット分布全体に一定のスケーリング効果を及ぼすことはないとはいえ、残留誤差は無視できることが多い。ビット分布をダウンサンプルし、様々な垂直解像度に合わせることも、局所的変動を減らすのに役立つ。
【００２４】
ここまでＧ４圧縮画像を中心に説明してきたが、Ｇ３圧縮方式に関連したことも言及する意味がある。同じ画像のＧ３符号化ファイルとＧ４符号化ファイルのビット分布の差異は、１次元（１Ｄ）符号化走査線と２次元（２Ｄ）符号化走査線にある。２Ｄ符号化は、通常、１Ｄ符号化より効率がよいため、Ｇ３符号化ビット分布は、Ｇ４符号化ビット分布に、周波数がｋの周期的波形を加えたものである。ここで、ｋは１Ｄ符号化走査線の周波数である。Ｇ３において、ｋの推奨設定は、２００ドット／インチ（ｄｐｉ）で２走査線おきであり、それ以上に高い解像度の場合には４走査線おきである。実際には、差異はピーク高さについては小さいことが多く、これらの周波数は通常は非常に高いため本来の行間隔と混同されることはない。ＴＩＦＦ形式のファイルにおいては、この種の周期的ノイズが符号化方式とは関係なく発生することがある。ＴＩＦＦ形式のファイルでは、処理を容易にするため画像が固定サイズのストリップとして符号化されることが多い。そのため、各ストリップの最初の行は事実上、１Ｄ符号化される。１ストリップ当たり行数(RowsPerStrip)のパラメータの設定を変えると、それに対応した変化がＰＳＤに生じる。Ｇ３における周波数ｋの周期的波形の場合と同様に、ＴＩＦＦ形式ファイルにおける事実上の１Ｄ符号化によって生じるノイズは、テキスト行によって作られるピークに比べかなり小さいので無視し得る。
【００２５】
《２．詳細マッチング》
視覚的に異なる文書が同じ様な圧縮ビット分布を持つことがあり得るので、粗マッチングにより得られた候補リスト中の不確実なものを取り除くために２段目の処理が必要であろう。一実施例によれば、それ以上の情報を得るため、Ｇ４圧縮照会画像又はそれ以外の方法で圧縮された照会画像から端点特徴の集合を抽出する。解析により、これら端点特徴の部分集合がマーカーとして認定される。文書の索引付けのため、これらマーカーの位置に基づいた記述子が生成される。粗マッチング処理で文書候補集合が得られたときには、クロス確認が実行される。以下の部分で、端点特徴の抽出及び記述子の生成について詳述する。
【００２６】
《２．１  端点抽出》
端点特徴抽出の理解を容易にするためには、グループ４圧縮方式について簡単に検討するのが有益である。グループ４圧縮方式では、各走査線は上の走査線を基準として符号化される。図５の（Ａ）及び（Ｂ）を参照すれば、現在符号化点ａ０を基準にして、両走査線上の２つの連続した画素ランの起点（変化要素と言う）が随時検出される。これらの変化要素間の相対位置に基づいて、可能な３つのモードの中の１つのモード、すなわち水平モード、垂直モード又はパスモードが符号化のために選択される。符号化後、ａ０が先へ移動させられ、処理が繰り返される。これが図５に矢線８１及び８３で示されている。復号化時には、復号化されたモードが既に分かっている変化要素（ａ０，ｂ１，ｂ２）と併用されることによりａ１及び／又はａ２の位置が決定される。そして、要素ａ０が符号化の場合と同様に先へ移動させられる。したがって、モード情報が最初に復号化される。変化要素の位置も常に保存される。
【００２７】
パスコードは、ストロークの最下部（白パス）又はホールの最下部（黒パス）に対応した位置で発生する。ローマ字の場合、これらの特徴点は、下向きの縦ストロークの端又は曲線ストロークの最下部に見出されることは、図６のパスコード・ダイアグラム８７によって示す通りである（各正方形ドット８８がパスコードの位置を示す）。パスコードがベースラインの近くに整列しているため、また、パスコードが構造情報を持っているため、パスコードはスキュー推定、テキスト・マッチングのような様々な処理に有用である。パスコードがグループ４圧縮ファイルから容易に抽出できることも同様に重要である。
【００２８】
パスコードは有用ではあるが、限界もある。第１に、白パスコードは全てストロークの最下部に対応するが、ストロークの最下部の全てがパスコードによって表現されるわけではない、という意味でバスコードは不安定である。グループ４の符号化モードはコンテキスト依存性があるため、同じ変化要素局所パターンであっても異なった符号化がなされる可能性がある。
【００２９】
例えば、図５（Ａ）のｂ１から始まる黒ラン８４はパスコードを発生させる。一方、図５（Ｂ）のｂ２から始まる黒ラン８５はパスコードを発生させない（もしａ１が１画素右にシフトしたならば発生させるだろうが）。それどころか、ｂ２にあるストロークの最下部８６は、ａ０からａ２まで及ぶ水平モード符号化によって完全に隠蔽される。
【００３０】
パスコードのもう１つの限界は、パスコードが非対称であることである。ストローク又はホールの最下部をパスコードで表現し得るとしても、パスコードは、そのストローク又はホールの最上部の情報は全く与えない。例えば、図６のパスコード・ダイヤグラム８７に見られるように、”ｄ”の最下部は２つのパスコード、すなわち白パスコード８９Ａと黒パスコード８９Ｂを含むことが多いが、その文字の最上部の特徴点は全く捕捉されない。
【００３１】
パスコードには前記の限界があるため、少なくとも詳細マッチング段階の一実施例によれば、圧縮照会文書の変化要素から直接的に端点特徴が抽出される。２種類の端点、すなわち上端点と下端点が抽出される。下端点は、白パスコードで捕捉されるものと同様の、ストロークの最下部である。しかし、下端点とパスコードとの重要な相違は、下端点が変化要素ａ１，ｂ２の位置を直接比較することによって抽出され、水平符号化によって不明瞭になる可能性がなくなることである。このように、パスコードと違い、ストロークの最下部は全て下端点であり、かつ、下端点は全てストロークの最下部である。ストロークの最上部は、変化要素ａ２，ｂ１を用いて同様に上端点として抽出される。
【００３２】
図６の端点ダイヤグラム９４は、上端点及び下端点によって捕捉される特徴量を表すもので、パスコードによって捕捉される特徴量と端点によって捕捉される特徴量との差異を明らかにするためパスコード・ダイヤグラム８７の直ぐ下に置かれている。端点ダイヤグラム９４は、下端点９６はおおむねテキスト行のベースライン９８の位置に整列するが、上端点９５はおおむねｘ−高さライン９７の位置に整列することも示している（ｘ−高さラインは、小文字”ｘ”の最上部で決まるラインである）。
【００３３】
図７の（Ａ）及び（Ｂ）並びに以下の擬似コードは、上端点と下端点の検出方法を説明するために用意された。
if  ((pixel(a0)  ==  WHITE)  and  (al>b2))
{
down  endpoint  at  (b1+(b2-bl+l)/2，r-l)
move  a0  to  b2
}
if  ((pixel(a0)  ==  WHITE)  and  (bl>a2)  and  (b0<al))
up  endpoint  at  (al+(a2-al+l)/2，r)
move  aO  to  a2
}
【００３４】
図７（Ａ）において、ａ０は白でａ１はｂ２の後に現れる。よって、上記擬似コードリスト中の最初の条件文の条件が満たされるので、走査線ｒ−１上のｂ２からｂ１までのランのほぼ中間点に下端点９６が設定される。要素ａ０は、矢線１０１で示されるように、走査線ｒ上のｂ２の真下位置へ進められる。
【００３５】
図７（Ｂ）において、ａ０は白であり、ｂ１はａ２の後に現れ、ｂ０はａ１の前に現れる。よって、前記擬似コードリスト中の２番目の条件文の条件が待たされるため、走査線ｒ上のａ１からａ２までのランのほぼ中間点に上端点９５が設定される。要素ａ０は、矢線１０３で示されるように、ａ２まで進められる。
【００３６】
端点にはパスコードに比べ有利な点がいくつかある。まず、端点のほうが安定である。すなわち、同じ特徴点が符号化モードの違いによって不明確になることがない。また、端点は、テキスト行のｘ−高さラインとベースラインの両方に関する情報を与える。これによって、文字高さ、ページ向き、アセンダなどの情報の抽出が可能になる。上端点及び下端点の対称性は、上下逆さまのページを処理する場合に好都合である。ページが上下逆さまであるときには、上端点と下端点とを入れ替えて簡単な座標再配置をすることによって正しい向きのページに関する端点を得ることができる。圧縮文書を再度走査する必要がない。これに対し、パスコードは、非対称であるため、対応した特徴点を得るためには、通常、画像を上下逆さまにして改めて圧縮する必要がある。さらに、端点は変化要素の相対的位置に基づいて検出されるため、それらの位置はパスコードと同程度に計算が容易である。
【００３７】
《２．２  文書の索引付け》
特徴抽出の次に、２次元の端点情報は、効率的な索引付けのための１次元表現に変換される。この変換には、いくつかの操作が必要とされる。まず、ページのスキューが推定され、端点に基づいて修正される。スキュー補正後の上端点と下端点についての平滑化した水平射影（Ｕ分布とＤ分布と呼ぶ）を用いて、テキスト行の位置が検出される。ｘ−高さラインは対応したベースラインより上にあるはずであるから、Ｄ分布はＵ分布より後にあるはずである。ビット分布のスペクトル解析により求められた支配的行間隔によって制限されたオフセットの範囲内で、Ｕ分布とＤ分布間の最大相関が計算される。相関分布において、Ｕ分布の極大値が、文字高さに相当する距離だけ離れたＤ分布の極大値と一致する場所ではテキスト行が検出される可能性が高い。Ｕ分布とＤ分布の相関を向上させるため、行間隔の２倍未満の範囲内にあるＵ分布及びＤ分布の極大値以外は全て０にされる。これは、Ｕ分布からｘ−高さライン以外のものを全て除去し、かつ、Ｄ分布からベースライン以外のものを全て除去しようとするものである。それから、極大値の分布について相関がとられる。図８は、照会画像から抽出されてスキュー補正された端点集合１０９と、上端点及び下端点の水平射影１１２（下端点はＤ分布を作る負の射影値１１４である）と、Ｕ分布及びＤ分布の極大値の射影１１５と、一致するＵ分布とＤ分布の極大値１１７を示す。
【００３８】
テキスト行位置の集合が与えられたならば、各テキスト行領域内の端点が抽出される。テキスト行内の端点を用いて、そのｘ−高さラインとベースラインの位置を知ることができるから、そのテキスト行内のアセンダ領域及びデセンダ領域と呼ばれる領域を定めることができる。図９は、２つのテキスト行領域１２７，１２９を含む画像領域１２５と、各テキスト行領域内に含まれる上端点及び下端点を表している。対応した端点マップ１３１には、実線で表されたテキスト行の境界１３３Ａ−１３３Ｃと、破線で区切られたアセンダ領域１３５Ａ，１３５Ｂ及びデセンダ領域１３７Ａ，１３７Ｂが含まれている。この端点マップ１３１において、上端点と下端点はそれぞれ上向きの三角形と下向きの三角形で示されている。
【００３９】
図９に示された例から、いくつかのことが分かる。まず、上端点と下端点の相対的位置から重要な情報を導き出すことができる。例えば、点などの符号や、”ｉ”，”ｊ”は、（例えば矢線１４５で示すように）アセンダ領域１３５Ａ，１３５Ｂ内の同じｘ位置に上端点と下端点の両方が存在することから容易に分かる。また、中間領域１４７Ａ，１４７Ｂ内の上端点は、通常、”ｅ”，”ｓ”，”ｔ”のような文字の上向き曲線を表す。文字”ｃ”は、（例えば矢線１４６によって示すように）中間領域内の２組の対向した上端点と下端点によって表される。
【００４０】
一実施例によれば、比較的小さい領域から抽出された端点の系列を用いて文書マッチングのための索引が作られる。基準線がうまく決まれば、端点を系列にエンコードする方法はいくつか可能である。観察すると、ｘ−高さ領域の内側に生じる端点は、接触、分離、セリフ、フォント種類の変動によるノイズの影響を受けやすいことが分かる。そのため、一実施例によれば、中間領域内の端点は無視され、Ｘ−高さラインより上にある（すなわちアセンダ領域内にある）上端点とベースラインより下にある（すなわちデセンダ領域内にある）下端点だけがマーカーとして用いられる。他の実施例では、テキスト行の他の領域から抽出された端点がマーカーとして用いられることもあろう。
【００４１】
一実施例によれば、連続したマーカー間の量子化距離の系列が記述子として用いられる。連続マーカー間距離の量子化を図１０に例示する。上端点マーカー（すなわち”アセンダ”）間距離を表すために正値が用いられており、下端点マーカー（すなわち”デセンダ”）間距離を表すために負値が用いられている。各テキスト行領域の左端の端点は基準点１４９Ａ，１４９Ｂとして用いられる。これに代わる実施例では、別の基準点と距離形式が用いられることもあろう。２次元構造を保存するため、テキスト行間にまたがる距離インジケータが、間に０をはさんで連結される。したがって、与えられたテキスト行について、正値と負値のストリングが生成されることになる。例えば、図１０に示すテキスト行については、距離インジケータのストリングは
1，11，13，4，2，2，2，4，0，-39
O,
5，7，7，4，8，6，0，-11
となる。
【００４２】
他の実施例では、これとは異なるマーカー距離形式が用いられることもあろう。例えば、アセンダ領域とデセンダ領域のマーカー距離を厳密に左から右へ向かう順に交互に並べてもよい。
【００４３】
一実施例によれば、Ｎ個の連続した距離からなる各系列により作成された記述子で、データベース内の各文書が逆索引付けされる。同様に、Ｎ個の連続した距離からなるＫ個の系列が照会時に生成される。一案によれば、各記述子の重みは、索引付けする文書数に逆比例する。例えば、図１０の例においてＮ＝５とすれば、下記の通り、Ｋ＝（距離インジケータ数−Ｎ）＋１＝（１９−１）＋１＝１５個の系列Ｓ１〜Ｓ１５が生成される。
S1=(1，11，13，4，2)
S2=(11，13，4，2，2)
S3=(13，4，2，2，2)
・
・
S15=(4，8，6，0，-11)
【００４４】
索引付けする文書数に逆比例して各系列に重み付けをすることにより、Ｋ個の系列中の各系列Ｓｉは、それで索引付けするＭｉ個の文書の１つ１つに１／（Ｋ＊Ｍｉ）なるスコアを与える。ある閾値より大きなスコアを与えられた文書が、詳細マッチング段階で選出される。Ｎの値が大きいほど、より少ない、よりユニークな記述子が生成されるが、長い系列ほどノイズによって分断されやすい。本発明の範囲から逸脱しない限り、記述子の重み付け及び記述子の選択のために他の方法を用いてもよい。
【００４５】
《３．実験結果》
９７９の文書画像からなるデータベースについて実験を行った。９７９の画像中、２９２（１４６組）の画像は一致する相手がある。これら２９２の画像中の各画像が、それと一致する画像を残りの９７８の画像から検索するための照会画像として用いられる。粗マッチング手順と詳細マッチング手順の個別実験と組み合わせ実験が行われた。それぞれの実験の結果を以下に示す。
【００４６】
《３．１  粗マッチングの実験結果》
粗マッチング・アルゴリズムの一具体化例では、特定の垂直画像解像度で得られた原ビット分布が、平均化によって３６ｄｐｉにダウンサンプルされる。これは、検出可能な最小行間隔が４ポイントであることを意味する。このような解像度であれば、ビット分布は十分滑らかであるが、それでも、その詳しさは索引の計算及び分布の修正に必要十分である。スペクトル解析中に、８ポイントから３６ポイントまでの周波数範囲に限定して支配的な行間隔が調べられる。分布値は、３００ｄｐｉ（水平）の１インチあたりビット数に正規化されてから８ビットに量子化される。この８ビットという深さは、様々なフォント種類において３００ｄｐｉで圧縮するために８ポイント文字が必要とするのは２００ビット／インチ未満であるのが普通であるという知見に基づき実験的に見出された。平均２５５ビット／インチを越える走査線は、通常、ハーフトーンを含んでいる。他の画像解像度で得られた分布は（３６ｄｐｉで垂直方向に再サンプリングされた後）、まず比例変倍され、次に量子化される。グループ３／グループ４符号化ファイルやＴＩＦＦ形式のストリップ・サイズに対する特別な調整は行われない。したがって、典型的な８．５×１１インチのサイズの１ページにつき、３９６バイト（１１インチ×３６ｄｐｉ×８ビット）のデータが生成される。
【００４７】
上位Ｎ個の選択結果についての検索率（recall  rate）を図１１にまとめて示す。ビット分布の相互相関によって、最上位の選択結果で８６％の正解が得られ、また上位３つの選択結果で９１％の正解が得られた。大局的統計量を索引付けに利用すると、相互相関計算のための平均候補数は、検索率を悪化させることなく、９０％減少する。データベース内文書のビット分布の離散フーリエ変換が予め計算され格納されているので、相互相関をベクトル積で計算できる。したがって、各画像照会には、ビット分布の抽出、大局的統計量によるフィルタ処理、その後の約１００回の３９６次元ベクトル積演算が必要である。
【００４８】
正しく一致がとれた文書と間違って一致がとれた文書の例を図１２及び図１３にそれぞれ示されている。正しく一致がとれたケースを見れば、前述した変形に対処できる情報頑健性があることは明白である。殆どの誤りは、画像にスキューがあるか画像にハーフトーン部分が含まれているために起こった。ハーフトーン部分の品質は、索引付けには影響を及ぼさないけれども、分布相関に大きな影響を及ぼす。また、多段組のページ、特に、ある段がハーフトーンで別の段がテキストである多段組ページによって問題が起こることがある。非共線的な段があると、エイリアシングが生じて行間隔推定が不正確になることがある。２組の画像は倍率が異なっている。
【００４９】
行間隔指標及びテキスト・エネルギー指標のほうが、テキストの位置指標及び大きさ指標より、探索空間を絞り込むのにずっと有効であることが分かった。このことは、フーリエ変換の空間局在性の悪さから予想されるものである。しかし、密に配されたポイント・サイズ９から１２までの行間を識別するためには、周波数分離が良好であることが重要である。テキスト位置検出の改善のため、ウェーブレット変換を用いてもよい。
【００５０】
《３．２  詳細マッチングの実験結果》
詳細マッチングの実験においては、既知の正しい情報（ground  truth  information）を利用して、画像中の最初のテキスト部分の１．５×１インチの領域から端点が抽出された。そして、アセンダ領域及びデセンダ領域の端点を検出するためテキスト行位置検出アルゴリズムが適用された。これら領域のいくつかには画像の非テキスト部が含まれていたが、この行位置検出手法によってテキスト行に属さない特徴点を全て除去できた。アセンダ領域とデセンダ領域の境界が定まってから、各領域毎に端点マーカー間距離の系列が生成された。連続したＮ個の距離をそれぞれ索引として選び、データベース照会のための複数の記述子が作成された。前述の重み付け方法を用いて、最も高いスコアを与えられた画像が選択された。
【００５１】
２９２の画像の１つ１つを用いて９７９の画像全体に対して照会した。これらの画像自体は、すべてのケースで検索された。この２９２のケースのうち２９０のケースでは、その画像だけが第１位の選択結果として検索された。２つのケースでは、別の画像が１つ同じスコアで検索された。重複検出の場合、あるケースが正しいとみなされるのは、一方のスコアが残りの画像中で最高であって同じスコアがないときである。異なるＮ値の場合の結果が図１４にまとめて示されている。
【００５２】
３つの距離からなる系列、４つの距離からなる系列、及び、５つの距離からなる系列を用いることにより、９２．５％の重複が正しく検出される。この性能は、もっと計算量の多い手法によって達成される結果に匹敵する。しかも、この索引付け方法は、距離ベースの方法に比べ拡張性が非常に優れている。誤りの大部分は特徴点のノイズによるものである。
【００５３】
射影ベースのテキスト行位置検出手法は、ページの幅方向にテキスト行が共線的であることを前提にしているため、その性能は整列していない多段組文書では悪化する。この問題に対する解決策の１つは、垂直射影を用いて段分割をすることである。もう１つの解決策は、文書の縦方向断片内でテキスト行位置検出を行い、信頼性の高い結果だけを利用することにより段境界を避けることである。
【００５４】
テキスト行境界の外側に出現する擬似特徴点によって、誤った記述子が生成されることがある。テキスト行の水平方向の大きさを検出するための方策をいくつか講じてもよい。特徴点はスキューを補正済みであり、かつ、ｘ−高さラインとベースラインは分かっているから、前記端点分布に基づいて行領域の端を見つけることができる。さらに、記述子生成のための領域は自動的に決定できる。実験においては、既知の正しい情報（ground  truth  information）が、文書画像中の対応テキスト領域を検出するために用いられた。このレジストレーション・プロセスは、自動領域選択方法で置き換えてもよい。検出された各テキスト行毎に記述子を生成すると、データベースのサイズが増加して検索精度が悪化するであろう。候補領域を特定するための可能な１つの方法は、局所的な特徴点密度に基づいて選択する方法である。本発明の範囲を逸脱しない限り、他の手法を用いてもよい。
【００５５】
《３．３  組合せ実験結果》
粗マッチング段階と詳細マッチング段階を組合せた実験においては、第１位選択結果の相関スコアが０．５より大きく、かつ、第１位選択結果のスコアと第２位選択結果のスコアとの差が０．０３より大きい場合に、粗マッチング段階の結果が選ばれる。それ以外の場合には、上位２０個の選択結果が詳細マッチングに回される。その結果、７０％の画像が粗マッチングによって確定され、３０％の画像だけが詳細マッチングを必要とする。システム全体の正解率は９３．８％である。このように、分布相関による粗マッチングは、実行効率を向上させるだけでなく、それがないと詳細マッチング単独では間違いやすい候補を排除することが分かる。判定ルールを修正すれば、結果は違ったものになろう。殆どの場合、検出の信頼性を向上させるために詳細マッチング段階を行うべきである。
【００５６】
《４．データ処理システムの概要》
図１５は、本発明の実施例に従った処理を実行するためのデータ処理システム１５０の一例を示すブロック図である。このデータ処理システム１５０は、処理装置１５１、メモリ１５３、表示装置１５５、カーソル制御装置１５７、キーパッド１５８、通信装置１５９をそれぞれバス構造１６１に接続してなる。データ処理システム１５０は、デスクトップコンピュータであっても、ワークステーションであっても、もっと大型のコンピュータであってもよい。あるいはまた、データ処理システム１５０は、圧縮文書画像を処理するのが望ましい、コピー装置、ファクシミリ装置、その他任意の電子装置であってもよい。カーソル制御装置１５７は、表示装置１５５に表示されている要素を操作するための、マウス、トラックボール、その他任意の装置でよい。キーパッド１５８は、ユーザが英数字データを入力可能な、キーボードやその他の任意の装置でよい。データ処理システム１５０で遂行される機能に応じて、他の入出力装置１６３が設けられてもよい。
【００５７】
処理装置１５１は、命令シーケンスを実行可能な、１つ以上の汎用プロセッサ、１つ以上のデジタル信号プロセッサ、その他任意の装置でよい。処理装置１５１は、データ処理システム１５０の複数のコンピュータ間に分散配置されてもよい。ネイティブマシン言語又は仮想マシン言語を用いてプログラムすることによって、処理ユニット１５１を前述した粗マッチング段階と詳細マッチング段階の処理を実行するために利用できる。
【００５８】
通信装置１５９は、データ処理システム１５０を電子装置のネットワーク（例えばインターネットのようなコンピュータネットワーク）に接続するためのモデム、ネットワークカード、その他任意の装置でよい。通信装置１５９は、有線又は無線媒体を介して伝送される信号の送信又は受信のために利用できる。この伝送信号は、例えば、ワールドワイドウェブ（又は他の任意のコンピュータネットワーク）のサイトと交信して、文書画像や、本発明の実施例を遂行するための処理装置１５１によって実行可能な更新プログラムコード又は機能拡張用プログラムコードを受信するために用いることができる。
【００５９】
一実施例によれば、メモリ１５３はシステムメモリ１６６、不揮発性大容量記憶装置１６７及びリムーバブル記憶媒体１６８からなる。リムーバブル記憶媒体１６８は、例えば、コンパクトディスク読み出し専用メモリ（ＣＤＲＯＭ）、フロッピーディスク、その他のリムーバブル記憶装置である。前述の粗マッチング段階と詳細マッチング段階の処理を行うための命令シーケンスなどのプログラムコードを、データ処理システム１５０によって読み取り可能なリムーバブル記憶媒体１６８に格納しておき、それを用いて以上に説明した実施例に従ってデータ処理システム１５０を動作させることができる。不揮発性大容量記憶装置１６７は、磁気テープ、磁気ディスク、光ディスク、電気的消去可能書き込み可能読み出し専用メモリ（ＥＥＰＲＯＭ）、その他任意のコンピュータ読み取り可能媒体などの不揮発性記憶媒体に情報を格納するための装置でよい。以上に述べた実施例に従ってデータ処理システム１５０を動作させるためのデータとプログラムコードは、インストールプログラムの制御によって、リムーバブル記憶媒体１６８から不揮発性大容量記憶装置１６７へ転送してもよい。文書データベースも不揮発性大容量記憶装置１６７に保存してもよい。
【００６０】
一実施例によれば、データ処理システム１５０の電源が投入されると、処理装置１５１又はダイレクト・メモリアクセス・コントローラ（不図示）のような他の装置によって、オペレーティングシステムのプログラムコードが不揮発性大容量記憶装置１６７からシステムメモリ１６６にロードされる。そうすると、オペレーティングシステムに含まれる命令シーケンスを処理装置１５１が実行して、前述の粗マッチング段階と詳細マッチング段階を遂行するためのプログラムコードなどの命令シーケンスを不揮発性大容量記憶装置１６７からシステムメモリ１６６にロードする。かくして、コンピュータ読み取り可能媒体から命令シーケンスを取得し、それを処理装置１５１で実行することにより、本発明の実施例を実施できる。
【００６１】
本発明の実施例を実施するためのデータ処理システムについて説明したが、個々の処理操作を、それを実行するための布線ロジックを含む専用ハードウェア要素、又は、プログラムされた処理要素と布線ロジックの組合せによって遂行してもよい。以上に述べたことを、前述の操作がハードウェア要素の特定の組合せによって行われる実施例にのみ本発明を限定するものと理解すべきではない。
【００６２】
以上、本発明を特定の実施例に関して説明した。しかし、特許請求の範囲に記載された本発明の範囲から逸脱しない限り、前記特定の実施例を様々に修正変更してよいことは明らかであろう。よって、本明細書及び図面は、説明のためのものと理解すべきであって、限定的にとらえるべきでない。
【００６３】
【発明の効果】
以上に詳細に説明したように、本発明によれば、テキスト・ベースでもなく、またテキスト行ベースでもない、文書画像の特徴を利用した高精度な文書マッチングが可能になる。少ない計算量で高精度な文書マッチングが可能になる。文書画像が圧縮している場合においても、文書画像の伸長、再圧縮を必要とせずに高精度な文書マッチングが可能になる。文書画像のノイズや変形に頑健な高精度な文書マッチングが可能になる。
【図面の簡単な説明】
【図１】  本発明による２段階文書マッチングの概要説明図である。
【図２】  一実施例による粗マッチング段階の説明図である。
【図３】  照会文書と、それに対応したビット分布、バンドパスフィルタ処理後の分布、位相群遅延密度グラフ及びパワースペクトル密度を示す図である。
【図４】  一致すべき２文書画像間によく見られる変形と、それら文書画像に対応したパワースペクトル密度を示す図である。
【図５】  （Ａ）ＣＣＩＴＴグループ４符号化でパスモード符号化に用いられる参照点の例を示す図である。
（Ｂ）ＣＣＩＴＴグループ４符号化で水平モード符号化に用いられる参照点の例を示す図である。
【図６】  パスコードと端点の差異の説明図である。
【図７】  （Ａ）下端点抽出の説明図である。
（Ｂ）上端点抽出の説明図である。
【図８】  スキュー修正後の端点集合と、対応した水平射影、水平射影の極大値及び一致する極大値を示す図である。
【図９】  １対のテキスト行領域内に位置する端点集合の例を示す図である。
【図１０】  連続した端点マーカー間距離の量子化の説明図である。
【図１１】  異なるＮ値に対する粗マッチング検索率をまとめて示す図である。
【図１２】  正しく一致がとれた画像の例を示す図である。
【図１３】  間違って一致がとれた画像の例を示す図である。
【図１４】  異なる１記述子あたり連続距離数によるデータベースの詳細マッチング結果をまとめて示す図である。
【図１５】  本発明によるデータ処理システムの一例を示すブロック図である。
【符号の説明】
１２  照会文書
１４  画像データベース
１５  粗マッチング段階
２０  詳細マッチング段階
２５  ビット分布
２７  大局的統計量
２９  ビット分布
４０  文書画像
８７  パスコード・ダイアグラム
９４  端点ダイヤグラム
９５  上端点
９６  下端点
９７  ｘ−高さライン
９８  ベースライン
１２７，１２９  テキスト行領域
１３１  端点マップ
１３５Ａ，１３５Ｂ  アセンダ領域
１３７Ａ，１３７Ｂ  デセンダ領域
１４９Ａ，１４９Ｂ  基準点
１５０  データ処理システム
１５１  処理装置
１５３  メモリ
１５５  表示装置
１５７  カーソル制御装置
１５８  キーパッド
１５９  通信装置
１６１  バス構造
１６６  システムメモリ
１６７  不揮発性大容量記憶装置
１６８  リムーバブル記憶媒体
【図１】
0004023706.tif 000002
【図２】
0004023706.tif 000003
【図３】
0004023706.tif 000004
【図４】
0004023706.tif 000005
【図５】
0004023706.tif 000006
【図６】
0004023706.tif 000007
【図７】
0004023706.tif 000008
【図８】
0004023706.tif 000009
【図９】
0004023706.tif 000010
【図１０】
0004023706.tif 000011
【図１１】
0004023706.tif 000012
【図１２】
0004023706.tif 000013
【図１３】
0004023706.tif 000014
【図１４】
0004023706.tif 000015
【図１５】
0004023706.tif 000016