(57)【特許請求の範囲】
【請求項１】
特定の文書画像と複数の対照対象の文書画像とを対照する文書画像対照方法であって、
前記文書画像中の個々の文字の位置を特徴付ける点であるアンカーポイントの集合を取得する取得ステップと、
前記特定の文書画像について取得されたアンカーポイントの集合と前記対照対象の各文書画像について取得されたアンカーポイントの集合との対照により、前記複数の対照対象の文書画像の中から前記特定の文書画像と最もよく合致する文書画像を識別する識別ステップと、
から構成されることを特徴とする文書画像対照方法。
【請求項２】
請求項１に記載の文書画像対照方法において、
前記取得ステップは、
文書画像の、ライン上の連続した黒又は白画素のランが次ライン上に対応したランを持たないことを示すパス符号を含む圧縮表現を入力として受け取るためのステップと、
前記圧縮表現よりパス符号の位置をアンカーポイントとして抽出するステップと
から構成されることを特徴とする文書画像対照方法。
【請求項３】
特定の文書画像と複数の対照対象の文書画像とを対照する文書画像対照方法であって、
前記特定の文書画像の、ライン上の連続した黒又は白画素のランが次ライン上に対応したランを持たないことを示すパス符号を含む圧縮表現を受け付けるステップと、
前記特定の文書画像中の個々の文字の位置を特徴付ける点であるアンカーポイントの集合として、前記圧縮表現よりパス符号の位置の集合を取得するステップと、
前記特定の文書画像について取得されたアンカーポイントの集合と前記対照対象の各文書画像について予め取得されたアンカーポイントの集合との対照により、前記複数の対照対象の文書画像の中から前記特定の文書画像と最もよく合致する文書画像を識別する識別ステップと
から構成されることを特徴とする文書画像対照方法。
【請求項４】
請求項２又は３に記載の文書画像対照方法において、
前記圧縮表現はＣＣＩＴＴグループ３のファクシミリ符号化標準又はＣＣＩＴＴグループ４のファクシミリ符号化標準の圧縮表現であることを特徴とする文書画像対照方法。
【請求項５】
請求項１又は３に記載の文書画像対照方法において、
前記識別ステップは、
前記特定の文書画像についてのアンカーポイントの集合と前記対照対象の各文書画像についてのアンカーポイントの集合との間のハウスドルフ距離を求めるステップと、
前記複数の対照対象の文書画像中で前記ハウスドルフ距離が最小となる文書画像を最もよく合致する文書画像と同定するステップとから構成されることを特徴とする文書画像対照方法。
【請求項６】
特定の文書画像と複数の対照対象の文書画像とを対照するための文書画像対照プログラムが記録されたコンピュータ読み取り可能記録媒体であって、
前記文書画像対照プログラムは、
前記文書画像中の個々の文字の位置を特徴付ける点であるアンカーポイントの集合を取得する取得ステップと、
前記特定の文書画像について取得されたアンカーポイントの集合と前記対照対象の各文書画像について取得されたアンカーポイントの集合との対照により、前記複数の対照対象の文書画像の中から前記特定の文書画像と最もよく合致する文書画像を識別する識別ステップと
をコンピュータに実行させるプログラムであることを特徴とするコンピュータ読み取り可能記録媒体。
【請求項７】
請求項６に記載のコンピュータ読み取り可能記録媒体において、
前記取得ステップは、
文書画像の、ライン上の連続した黒又は白画素のランが次ライン上に対応したランを持たないことを示すパス符号を含む圧縮表現を入力として受け取るためのステップと、
前記圧縮表現よりパス符号の位置をアンカーポイントとして抽出するステップと
から構成されることを特徴とするコンピュータ読み取り可能記録媒体。
【請求項８】
特定の文書画像と複数の対照対象の文書画像とを対照するための文書画像対照プログラムが記録されたコンピュータ読み取り可能記録媒体であって、
前記文書画像対照プログラムは、
前記特定の文書画像の、ライン上の連続した黒又は白画素のランが次ライン上に対応したランを持たないことを示すパス符号を含む圧縮表現を受け付けるステップと、
前記特定の文書画像中の個々の文字の位置を特徴付ける点であるアンカーポイントの集合として、前記圧縮表現よりパス符号の位置の集合を取得するステップと、
前記特定の文書画像について取得されたアンカーポイントの集合と前記対照対象の各文書画像について予め取得されたアンカーポイントの集合との対照により、前記複数の対照対象の文書画像の中から前記特定の文書画像と最もよく合致する文書画像を識別する識別ステップと
をコンピュータに実行させるプログラムであることを特徴とするコンピュータ読み取り可能記録媒体。
【請求項９】
請求項７又は８に記載のコンピュータ読み取り可能記録媒体において、
前記圧縮表現はＣＣＩＴＴグループ３のファクシミリ符号化標準又はＣＣＩＴＴグループ４のファクシミリ符号化標準の圧縮表現であることを特徴とするコンピュータ読み取り可能記録媒体。
【請求項１０】
請求項６又は８に記載のコンピュータ読み取り可能記録媒体において、
前記識別ステップは、
前記特定の文書画像についてのアンカーポイントの集合と前記対照対象の各文書画像についてのアンカーポイントの集合との間のハウスドルフ距離を求めるステップと、
前記複数の対照対象の文書画像中で前記ハウスドルフ距離が最小となる文書画像を最もよく合致する文書画像と同定するステップと
から構成されることを特徴とするコンピュータ読み取り可能記録媒体。
【請求項１１】
特定の文書画像と複数の対照対象の文書画像とを対照する文書画像対照装置であって、
前記文書画像中の個々の文字の位置を特徴付ける点であるアンカーポイントの集合を取得する取得手段と、
前記特定の文書画像について取得されたアンカーポイントの集合と前記対照対象の各文書画像について取得されたアンカーポイントの集合との対照により、前記複数の対照対象の文書画像の中から前記特定の文書画像と最もよく合致する文書画像を識別する識別手段と
から構成されることを特徴とする文書画像対照装置。
【請求項１２】
特定の文書画像と複数の対照対象の文書画像とを対照する文書画像対照装置であって、
前記特定の文書画像の、ライン上の連続した黒又は白画素のランが次ライン上に対応したランを持たないことを示すパス符号を含む圧縮表現を受け付ける手段と、
前記特定の文書画像中の個々の文字の位置を特徴付ける点であるアンカーポイントの集合として、前記圧縮表現よりパス符号の位置の集合を取得する手段と、
前記特定の文書画像について取得されたアンカーポイントの集合と前記対照対象の各文書画像について予め取得されたアンカーポイントの集合との対照により、前記複数の対照対象の文書画像の中から前記特定の文書画像と最もよく合致する文書画像を識別する識別手段と
から構成されることを特徴とする文書画像対照装置。
【請求項１３】
請求項１１又は１２に記載の文書画像対照装置において、
前記識別手段は、前記特定の文書画像についてのアンカーポイントの集合と前記対照対象の各文書画像についてのアンカーポイントの集合との間のハウスドルフ距離を求め、前記複数の対照対象の文書画像中で前記ハウスドルフ距離が最小となる文書画像を最もよく合致する文書画像と同定する手段である
ことを特徴とする文書画像対照装置。
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明は、電子的に表現された文書画像間のマッチング技術に関する。
【０００２】
【従来の技術】
電子的に表現されたある画像と画像のマッチング（対照）は多くのアプリケーションで有用である。例えば、文書画像が”類似”文書の入っているディレクトリに格納され、その類似性が２つの画像が共通の有意領域をどの程度持っているかによって定義される自動ファイリングのアプリケーションを考えられたい。
【０００３】
文書画像のマッチングに利用できるいくつかの方法がある。ほとんどの方法は、特徴を抽出し、抽出した特徴をデータベース内の文書画像とマッチングするという２ステップからなる。入力画像はデータベース画像と有意個数の特徴を共有するかマッチングされる。
【０００４】
どのような特徴抽出の手法を用いるかによって、マッチングシステムの性能が決定的に左右される。理想を言えば、特徴抽出は、高速であって、メモリ効率がよく、かつ、入力画像に対し一意の表現を得られるものでなければならない。この表現の一意性によって、ある文書画像はそれ自身とは高い確率でよくマッチする（合致する）が他の文書とはマッチしないことが保証される。
【０００５】
文書画像マッチングに用いられる従来の特徴抽出手法の例は、例えば、文字変化確率、連続した語の長さのシーケンス、文書のグラフィック要素間の不変関係１、連結画素群を囲む枠の間隔などを基にして動作する。従来手法よりも速度、メモリ効率及び表現の一意性が向上する特徴抽出に基づいた文書マッチングシステムの実現が望まれる。
【０００６】
【発明が解決しようとする課題】
よって、本発明の目的は、高速でメモリ効率がよく高精度な文書画像マッチングのための手段を提供することにある。
【０００７】
【課題を解決するための手段】
上記課題を解決するための本発明の骨子は、特定の文書画像中の文字のアンカー位置を示す情報を獲得し、獲得したアンカー位置に基づいて、複数のマッチング対象文書画像の中から最もよくマッチする文書画像を識別することである。
【０００８】
【発明の実施の形態】
本発明によれば、高速でメモリ効率がよく高精度な文書画像マッチングシステムが提供される。
【０００９】
ある実施例においては、文書画像のマッチングの基本は、文書中の文字のアンカーポイント（anchor point）を検出することである。文書マッチングプロセスは、アンカーポイント、例えば文字の近似位置を表す点がマッチング用特徴とみなれさる特徴抽出ステップを含む。
【００１０】
格別に効率のよい実施態様では、アンカーポイントは文書画像の１ライン単位の圧縮表現における”パス符号”である。あるラインの圧縮表現におけるパス符号は、直前ライン上の当該パス符号のほぼ上に存在する白又は黒のランが現在ライン上に見つからないことを示す。ＣＣＩＴＴのグループ３及びグループ４のファクシミリ符号化標準方式は、本発明に利用可能なパス符号を用いる圧縮方式の例である。
【００１１】
本発明の効果的な実施態様によれば、入力文書画像中に見つかったアンカーポイントの集合と、マッチング対象文書画像について予め求められたアンカーポイントの集合との比較に、修正されたハウスドルフ（Ｈausdorff）距離が用いられる。この距離は、計算の効率がよく、また写真複写することによる画像劣化に強いことが分かった。
【００１２】
パス符号に基づく実施態様は、画像の１平方インチの断片しかマッチングに利用できない場合でも、高速かつ高精度のマッチングが可能であることが分かった。このタイプのマッチングシステムは、適切な圧縮表現が予め得られるファクシミリ受信機において容易に実施し得る。
【００１３】
以下、図面を参照し、本発明の実施例を詳しく説明する。
【００１４】
図１は、本発明に利用するのに適したコンピュータシステムの基本的なサブシステムを示す。図１において、コンピュータシステム１０はバス１２を含み、このバス１２は主要なサブシステム、例えば中央処理装置１４、システムメモリ１６、入出力（Ｉ／Ｏ）コントローラ１８を相互接続し、また、外部デバイス、例えばプリンタ２０をパラレルポート２２を介し、ディスプレイスクリーン２４をディスプレイアダプター２６を介して、シリアルポート２８、キーボード３０、ハードディスク３２、及びフロッピーディスク３３Ａを受け入れ可能なフロッピーディスクドライブ３３を相互接続する。ほかにも多くのデバイスが接続されてもよく、例えば読み取り装置３４が外部インターフェース３６を介して、マウス３８がシリアルポート２８を介して、またタッチスクリーン４０が直接的に接続される。このほかに、（図示しないが）多くのデバイス又はサブシステムが同じような方法で接続されてもよい。また、後述のように、本発明を実施するうえで、図１に示したデバイスの全部が必ずしも用意されなくともよい。それらデバイス及びサブシステムは、図１に示した方法とは異なった方法で相互接続されてもよい。
【００１５】
図１に示したようなコンピュータシステムの動作は、当該技術分野において容易に理解されるので、ここでは詳しく述べない。
【００１６】
本発明を実施するためのソースコード（プログラム）は、システムメモリ１６に動作可能に格納されてもよいし、あるいは、ハードディスク３２又はフロッピーディスク３３Ａのような記憶媒体に格納されてもよい。本発明は、デジタルコピア又はファクシミリ装置に関連して実施されてもよい。
【００１７】
図２は、本発明の一実施例による文書マッチングのステップを表すトップレベルのフローチャートを示す。ステップ２０２において、読み取り装置３４はマッチングしようとする文書画像を読み込む。その画像の電子的表現が、それ以前に読み取られ、あるいは電子的に伝送されて既に得られているなら、それでもよいことは当然である。ステップ２０４において、コンピュータシステム１０は、文書画像中の文字の位置を特徴付ける点であるアンカーポイントの位置を推定し、アンカーポイントの集合を生成する。
【００１８】
好適な実施例においては、これらのアンカーポイントは固有の性質を有する圧縮表現より得られる”パス符号”である。図３に関連して詳しく述べるように、あるラインの圧縮表現中のパス符号は、前ライン上の該パス符号のほぼ上に存在する白又は黒のランが現在ライン上に見つからないことを意味する。なお、アンカーポイントの検出方法はこれに限定されるものではない。例えば、文書画像中の文字の重心をアンカーポイントとして検出してもよい。
【００１９】
ステップ２０６において、コンピュータシステム１０は、ステップ２０４で生成されたアンカーポイントの集合に基づいて、入力文書画像とマッチするものを見つける。一実施例では、例えばハードディスク３２に格納されているデータベース内の文書画像についてアンカーポイントの集合が予め生成される。この場合、マッチするものの識別には、その文書画像について生成されたアンカーポイントの集合と、データベースに予め格納されている文書について生成されたアンカーポイントの集合との比較が含まれる。一実施例では、この比較は後に詳述するハウスドルフ距離を用いて行われる。そして、マッチした文書画像はディスプレイスクリーン２４に表示されるか、その他の方法によってユーザに提示される。
【００２０】
文書画像の特定圧縮画像からのパス符号抽出としてステップ２０４を実施することが、非常に高速であり、かつ、文書画像の非常に独特な表現を得られることに発明者は気づいた。この表現の一意性はマッチング性能を向上させる。
【００２１】
パス符号は、画像のいわゆる２次元符号化表現中に見つかる。画像の１次元符号化表現では、各ラインは、前ラインを参照することなく独立に符号化される。連続した白又は黒画素ランのランレングスを符号語アルファベットを用いて符号化することによって、圧縮がなされる。２次元符号化表現では、ラインは参照ラインとの比較として符号化される。
【００２２】
ＣＣＩＴＴグループ３ファクシミリ伝送標準方式は、ｋライン（ｋ＝４が代表的）毎に適用される１次元符号化方式と２次元符号化方式の組合せを用いる。
【００２３】
ＣＣＩＴＴグループ４標準方式においては、全てのラインが２次元的に符号化され、画像の最初のラインは全白の参照ラインに対して符号化される。グループ３標準方式もグループ４標準方式も共に同じ２次元符号化方式を使う。この符号化標準方式の完全な解説はＨunter  ＆  Ｒobinson，”Ｉnternational  Ｄigital  Ｆacsimile  Ｃoding  Ｓtandards”，Ｐroceedings  of  the  ＩＥＥＥ，（Ｊuly  １９８０）に見られるが、その内容は引用によって全面的に本明細書に組み入れられる。
【００２４】
ここで、ＣＣＩＴＴの２次元符号化方式の一般原則を図３を参照して説明する。図３は、符号化しようとする符号化ライン３０２の画素、及び、符号化ライン３０２が符号化過程において比較される参照ライン３０４の画素を表している。符号化は１ラインずつ行われる。各変化要素すなわち直前の画素と異なった画素値を持つ各画素、例えば黒画素が後に続く白画素又は白画素が後に続く黒画素に、１つの符号語が割り当てられる。
【００２５】
図３は、そのような５つの変化要素を表している。起点変化要素ａ0は符号化ライン上の符号化すべき変化要素の前の変化要素である。次の変化要素ａ1は次に符号化すべき変化要素である。ａ1の後の変化要素がａ2である。参照ラインにおいて、ｂ1はａ0より右にあってａ1と同じ色を持つ最初の変化要素である。変化要素ｂ2はｂ1の右の参照ライン上の変化要素である。
【００２６】
パス符号”０００１”は、ｂ2の位置がａ1の左側にある時に変化要素ａ1で始まるランを表す。これは、図３に示された状態であって、参照ライン上の白又は黒ランが符号化ライン上の対応した白又は黒ランと隣接していないことを示す。
【００２７】
多くの文字は、そのホールに白のパス符号が付けられ、そのストロークに黒のパス符号が付けられる。構成要素の配列や符号化プロセスの作用によっては、すべての構成要素に必ずしもパス符号が付けられるわけではない。しかしながら、構成要素のほぼ８０％乃至９０％にパス符号が付けられることが分かっている。
【００２８】
図４（Ａ）は、文書の写真複写を読み取った画像におけるパス符号を表している。図４（Ｂ）は、図４（Ａ）の文書の原稿を読み取った画像におけるパス符号を表している。両図はいずれも説明用に作成された図であって、淡く表した文字画像や（・）印で表したパス符号の位置は、必ずしも正確なものではない。各文字について、一般的にその最も低い位置の画素にパス符号が位置し、フラットな底部を持つ文字では一般的にその左下隅にパス符号が位置する。画像劣化があるにもかかわらず、これら文書間でパス符号の位置は非常に類似している。
【００２９】
図５は、本発明の一実施例により文書画像の圧縮表現よりパス符号を抽出するステップを表すフローチャートである。ステップ５０２において、コンピュータシステム１０はパス符号を用いる２次元画像符号化方式によって文書画像の２値表現を圧縮する。一実施例では、このステップはグループ３又はグループ４符号化システムの助けをかりて行われる。ファクシミリ受信機に関連して受信ファクスのマッチングのために本発明が実施される場合であれば、その圧縮表現は既に作られているから、ステップ５０２は必要ない。
【００３０】
ステップ５０４において、コンピュータシステム１０は、圧縮表現中のパス符号の位置を求める。ステップ５０２で画像が局所的に圧縮される場合には、圧縮と同時にパス符号の位置を求めてもよいことは言うまでもない。圧縮表現が局所的に生成されない場合には、コンピュータシステム１０は圧縮表現を初めから終わりまで１回走査し、非圧縮画像に付けられたところの各パス符号の垂直方向及び水平方向の位置を求める。各パス符号の垂直方向位置の決定は、走査中に圧縮表現中のＥＯＬ（end  of  line）符号語をカウントすることによって行われる。
各パス符号の水平方向位置を求めるため、コンピュータシステム１０は現在ライン上のパス符号の前にある各符号語によって表された画素数の累計をとる。ステップ５０４の結果は、文書画像中のパス符号位置の集合である。
【００３１】
なお、パス符号の位置を求めるステップのために、コンピュータシステム１０は伸長された画素値を実際に生成、格納又は出力する必要がないことに留意されたい。また、圧縮表現は小さいので、それを１回走査することは非圧縮表現を走査する場合より高速である。よって、パス符号の位置を検出することは、文字のアンカーポイントを見つける非常に高速なメモリ効率のよい方法である。結合成分特性又は光学文字認識に依存した特徴抽出手法は遥かに大きな非圧縮画像表現を何度も走査する必要があるため、そのような手法に比べて速度の優位性は非常に大きい。
【００３２】
特徴抽出が終わると、そのアンカーポイントの集合は、マッチング対象の文書画像について予め求められているアンカーポイントの集合とマッチングされる。一実施例では、予め求められているアンカーポイントの集合を見つけるためにハウスドルフ距離が用いられる。
【００３３】
原型のハウスドルフ距離は２つの集合Ａ＝ａ1，...，ａm，Ｂ＝ｂ1，...，ｂn相違を評価するのに効果的である。ここで、この２集合間の原型ハウスドルフ距離は次のとおりである。
【００３４】
【数１】
0003766186.tif 000002
【００３５】
関数ｈ（Ａ，Ｂ）は、ａから、そのＢ中の最近傍までの距離を評価する。したがって、ハウスドルフ距離Ｈ（ａ，ｂ）は、Ｂのどのポイントからも最も遠いＡのポイントと、Ａのどのポイントからも最も遠いＢのポイントとの距離を評価する。だから直感的に、ハウスドルフ距離がｄのときには、ＡのすべてのポイントはＢのどのポイントからも距離ｄの範囲内にあるはずであり、またＢのすべてのポイントはＡのどのポイントからも距離ｄの範囲内にあるはずである。
【００３６】
原型ハウスドルフ距離の弱点は”アウトライアー（outlier）”に敏感であることである。これらのアウトライアーは、原型ハウスドルフ距離によれば２つのポイント集合間のマッチを反映しない大きな値が返るポイントである。例えば、集合Ｂ中の最も近いポイントから１０画素離れた集合Ａ中の単一ポイントは、原型ハウスドルフ距離をして１０なる値を返させることになろう。このことは、Ａ中の他のすべてのポイントがＢ中の他のすべてのポイントから１画素以内にあったとしても起こる。
【００３７】
他の実施例では、シーン解析（scene analysis）向けに最適化された修正ハウスドルフ距離を利用する。この修正ハウスドルフ距離は、Ｈuttenlocher，Ｋlanderman，and  Ｒucklidge，”Ｃomparing  Ｉmages  Ｕsing  the  Ｈausdorff  Ｄistance”，ＩＥＥＥ  Ｔransactions  on  Ｐattern  Ａnalysis  and  Ｍachine  Ｉntelligence（Ｓeptember１９９３），pp．８５０−８６３に述べられており、その内容は引用により全面的に本明細書に組み込まれる。この修正ハウスドルフ距離は、アウトライナーの問題を解決し、２値画像より求められたポイント集合間の距離の確実な評価を与える。
【００３８】
この修正ハウスドルフ距離は次のように要約できる。
【００３９】
【数２】
0003766186.tif 000003
【００４０】
ここでは第ｋランクの値を返す”ｋｔｈ”関数が一般的なハウスドルフ距離のｍａｘ関数に置き換わっている。ｈk（Ａ，Ｂ）≦δの時、Ｂ中のポイントからδ画素以内にあるポイントを含む集合Ａkが得られる。Ａk中のポイントの数をＡ中のポイントに対する割合で表してもよい。
【００４１】
修正ハウスドルフ距離を計算する一つの方法は、周知の膨張プロセス及び相関プロセスを用いる方法である。半径δの円盤によるポイントの膨張により、当該ポイントをそれを中心とした半径δの円盤で置き換える。かかる膨張が集合Ｂに適用される。Ａの膨張後のＢとの相関をとることにより、Ｂ中のどれかのポイントからδ画素以内にあるＡ中のポイントの数ｐが得られる。ｐ≧ｋならば、ＡはＢ内に見つかる。すなわち、ｈk（Ａ，Ｂ）≦δである。
【００４２】
逆ハウスドルフ距離ｈk（Ｂ，Ａ）も同じ手法で計算される。ｈk（Ａ，Ｂ）及びｈk（Ｂ，Ａ）の値が許容できる値であれば（すなわち、それぞれが予め指定されたδ1及びδ2と等しいか、それより小さい値であれば）、ＡのインスタンスがＢ中に見つかり、それらが視覚的に非常に似ていることが保証される。すなわち、Ａは黒ベタの断片とマッチしない。さらに修正されたハウスドルフ距離は、修正ハウスドルフ距離を計算する前に、単純にＡをある一定量ｔだけ平行移動させることによってＡのｘ，ｙ移動を補償する。マッチングプロセスでは、ある範囲のｔ値を試して最小のハウスドルフ距離を見つける。
【００４３】
上記のさらに修正されたハウスドルフ距離の効率的な実例は、Ｒucklidge，”Ｅfficient  Ｃomputation  of  the  Ｍinimum  Ｈausdorff  Ｄistance  for  Ｖisial  Ｒecognition”，ＴＲ９４−１４５４，Ｃornell  Ｕniversity，Ｄepartment  of  ＣomputerＳcience，Ｓeptember，１９８４に述べられており、その内容は引用により全面的に本明細書に組み入れられる。
【００４４】
なお、特徴抽出及びマッチングは、画像の一部分だけを基にしてもよい（その部分が矛盾なく選ばれる限りにおいて）。パス符号抽出及び上記のさらに修正されたハウスドルフ距離を用いて、周知のワシントン大学のＣＤ−ＲＯＭから取り出した８００個の文書画像に対して本発明の一実施例が試された。これら画像中の初めの５２６個の画像は、１インチ四方の画像断片を用いて、８００個の画像からなるデータベースとマッチングされた。この５２６個の画像中の１５２個は、別途読み込まれた複製がデータベース内の別の場所にあった。１１４個の画像は第１世代の写真複写から読み取られた（そのオリジナルの読み取り画像もデータベース中にある）。１９個の画像は第１世代の写真複写であり、第３世代又はそれ以降の写真複写とマッチングされた。１９個の第３世代又はそれ以降の写真複写が第１世代写真複写とマッチングされた。
【００４５】
本発明の手法によれば、各画像断片とそれ自体とのマッチングにおいて１００％の精度を得られ、また、データベース中の写真複写の同定において９２．５％の精度を得られた。Ｓun  Ｍicrosystems社（カリフォルニア州マウンテンビュー）の７０ＭＨz  Ｓparkstation  ２０上で実施したところ、ある画像断片と８００画像断片のデータベースとのマッチングに約１０分を要した。
【００４６】
【発明の効果】
以上に詳細に述べたように、本発明によれば、文書画像の小さな断片しか利用出来ない場合も含め高い精度のマッチングが可能である。写真複写等により劣化した文書画像についても精度のよいマッチングが可能である。マッチング用特徴抽出及びマッチングのための処理の速度及びメモリ効率を大幅に向上させることができる。ファクシミリ受信機の受信ファクスのような予め圧縮表現が得られている文書画像に対し極めて高速なマッチングが可能になる、等々の効果を得られる。
【図面の簡単な説明】
【図１】  本発明の実施に適する典型的なコンピュータシステムを示すブロック図である。
【図２】  本発明の一実施例による文書マッチングのステップを表すフローチャートである。
【図３】  ＣＣＩＴＴグループ３ファクシミリ符号化標準方式による画像ラインの符号化の説明のための図である。
【図４】  （Ａ）文書の写真複写を読み取った画像中のパス符号を表す図である。
（Ｂ）同文書の原稿を読み取った画像中のパス符号を表す図である。
【図５】  本発明の一実施例により文書画像の圧縮表現からパス符号を抽出するステップを表すフローチャートである。
【符号の説明】
１０  コンピュータシステム
１２  システムバス
１４  中央処理装置
１６  システムメモリ
１８  入出力（Ｉ／Ｏ）コントローラ
２０  外部デバイス
２２  パラレルポート
２４  ディスプレイスクリーン
２６  ディスプレイアダプター
２８  シリアルポート
３０  キーボード
３２  ハードディスク
３４  読み取り装置
２６  外部インターフェイス
３３  フロッピーディスクドライブ
３３Ａ  フロッピーディスク
３０２  符号化ライン
３０４  参照ライン
【図１】
0003766186.tif 000004
【図２】
0003766186.tif 000005
【図３】
0003766186.tif 000006
【図４】
0003766186.tif 000007
【図５】
0003766186.tif 000008