(57)【特許請求の範囲】
【請求項１】
パターンの端点、交点、屈曲点からなる特徴点を検出する特徴点検出手段と、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するグラフ生成手段と、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺の除去を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、除去された辺の端点を接触文字の接触箇所と判断する接触箇所判別手段と、
を備えることを特徴とするパターン抽出装置。
【請求項２】
パターンの端点、交点、屈曲点からなる特徴点を検出する特徴点検出手段と、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するグラフ生成手段と、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺及びその辺の両端の特徴点の二重化を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、二重化された辺の位置を接触文字の接触箇所と判断して、切断箇所を検出する切断箇所検出手段と、
を備えることを特徴とするパターン抽出装置。
【請求項３】
パターンの端点、交点、屈曲点からなる特徴点を検出する特徴点検出手段と、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するグラフ生成手段と、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺の除去を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、除去された辺の端点を接触文字の接触箇所と判断して、切断箇所を検出する切断箇所検出手段と、
を備えることを特徴とする文字切り出し装置。
【請求項４】
更に、ある線分にもう一つの線分の端点が接触していて、該端点が前記切断箇所と検出された場合に前者を第１の線分、後者を第２の線分とし、該第１の線分方向の黒画素のランレングスが急激に減少する箇所でパターンを切断するパターン切断手段を備えることを特徴とする請求項３記載の文字切り出し装置。
【請求項５】
パターンの端点、交点、屈曲点からなる特徴点を検出する特徴点検出手段と、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するグラフ生成手段と、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺及びその辺の両端の特徴点の二重化を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、二重化された辺の位置を接触文字の接触箇所と判断して、切断箇所を検出する切断箇所検出手段と、
を備えることを特徴とする文字切り出し装置。
【請求項６】
更に、前記二重化された辺の位置が接触箇所と判断された場合に、該辺を垂直方向に二等分した位置でパターンを切断するパターン切断手段を備えることを特徴とする請求項５記載の文字切り出し装置。
【請求項７】
グラフの頂点間の辺の長さ、頂点間の水平方向の距離及び頂点間の垂直方向の距離に基づいて、グラフのサイズを算出するサイズ算出手段と、
分離後のグラフのサイズに基づいて、前記切断箇所検出手段により検出された切断箇所の候補の絞込みを行う絞込み手段とを備えることを特徴とする請求項３〜６のいずれか１項に記載の文字切り出し装置。
【請求項８】
前記切断箇所で切断されたパターンについての文字認識を行う文字認識手段と、
前記文字認識手段に実行される文字認識から、認識候補文字との相違度を求め、該相違度が所定値以下のパターンの切断箇所を前記パターンの接触箇所と判定する接触箇所判定手段と、
を備えることを特徴とする請求項３〜７のいずれか１項に記載の文字切り出し装置。
【請求項９】
切断されたパターンを他のパターンと組み合わせる組み合わせ手段を備え、
前記接触箇所判定手段は、組み合わせにより得られるパターンのうち、最も前記相違度の小さいパターンの組み合わせから得られる切断箇所を前記パターンの接触箇所と判定することを特徴とする請求項８に記載の文字切り出し装置。
【請求項１０】
パターンの端点、交点、屈曲点からなる特徴点を検出するステップと、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するステップと、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺の除去を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、除去された辺の端点を接触文字の接触箇所と判断して、切断箇所を検出するステップと、
を備えることを特徴とする文字切り出し方法。
【請求項１１】
更に、ある線分にもう一つの線分の端点が接触していて、該端点が前記切断箇所と検出された場合に前者を第１の線分、後者を第２の線分とし、該第１の線分方向の黒画素のランレングスが急激に減少する箇所でパターンを切断するステップを備えることを特徴とする請求項１０記載の文字切り出し方法。
【請求項１２】
パターンの端点、交点、屈曲点からなる特徴点を検出するステップと、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するステップと、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺及びその辺の両端の特徴点の二重化を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、二重化された辺の位置を接触文字の接触箇所と判断して、切断箇所を検出するステップと、
を備えることを特徴とする文字切り出し方法。
【請求項１３】
更に、前記二重化された辺の位置が接触箇所と判断された場合に、該辺を垂直方向に二等分した位置でパターンを切断するステップを備えることを特徴とする請求項１２記載の文字切り出し方法。
【請求項１４】
コンピュータに、パターンの端点、交点、屈曲点からなる特徴点を検出するステップと、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するステップと、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺の除去を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、除去された辺の端点を接触文字の接触箇所と判断して、切断箇所を検出するステップと、
を少なくとも実行させるためのプログラムを格納したコンピュータ読み出し可能な記憶媒体。
【請求項１５】
コンピュータに、パターンの端点、交点、屈曲点からなる特徴点を検出するステップと、
前記検出された特徴点を頂点とし、該特徴点で挟まれた線分を辺とするグラフを生成するステップと、
前記グラフ生成手段によって生成されたグラフの各頂点に対応する行成分及び列成分を有する第１の頂点隣接行列を生成し、前記グラフの辺及びその辺の両端の特徴点の二重化を行った場合のグラフに対応する第２の頂点隣接行列を生成し、該第１の頂点隣接行列と該第２の頂点隣接行列との間で対角化ブロック数が変化した場合、二重化された辺の位置を接触文字の接触箇所と判断して、切断箇所を検出するステップと、
を少なくとも実行させるためのプログラムを格納したコンピュータ読み出し可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパターン抽出装置及び文字切り出し装置に関し、特に、接触文字の接触箇所を検出する場合に適用して好適なものである。
【０００２】
【従来の技術】
従来の文字同士の接触位置の検出方法として、黒画素数ヒストグラムを用いる方法があった。この方法では、文字列の方向と垂直方向の黒画素数をカウントすることにより、黒画素数ヒストグラムを求め、その黒画素数ヒストグラムの極小点を文字同士の接触位置の候補とするものである。
【０００３】
図１８は、従来の文字同士の接触位置の検出方法を示す図である。
図１８（ａ）において、「印旛郡白井町」と手書きで書かれた文字パターンが入力され、「郡」という文字と「白」という文字とがＥ４の位置で接触しているものとする。
【０００４】
ここで、図１８（ａ）のパターンの接触位置を判定する場合、図１８（ｂ）に示すように、図１８（ａ）のパターンの黒画素数ヒストグラムを求める。そして、その黒画素数ヒストグラムの極小点Ｋ１〜Ｋ５を接触箇所の候補とするようにしていた。
【０００５】
【発明が解決しようとする課題】
しかしながら、従来の黒画素数ヒストグラムを用いる方法では、文字が傾いていたり、接触部分に別の文字線分が重なったり、横書きの場合の縦文字線分同士が接触したりしている場合、接触箇所に対応する黒画素数ヒストグラム値が極小とならない場合が発生し、接触箇所を検出することができないという問題があった。
【０００６】
例えば、図１８（ａ）の接触箇所Ｅ４に対応する黒画素数ヒストグラム値は、図１８（ｂ）のＥ４’の点に対応し、Ｅ４’の点は極小点ではないので、図１８（ａ）の接触箇所Ｅ４は接触箇所の候補から落とされる。この結果、図１８（ａ）のパターンを接触箇所Ｅ４の位置で切断することができなくなり、文字認識の精度が悪化する。
【０００７】
そこで、本発明の目的は、パターンの接触箇所の検出精度を向上させることが可能なパターン抽出装置及び文字切り出し装置を提供することである。
【０００８】
【課題を解決するための手段】
上述した課題を解決するために、本発明によれば、パターンから抽出された特徴点の接続関係に基づいて、パターンの接触箇所を判別するようにしている。
【０００９】
このことにより、文字同士が接触した時の連結状態を考慮して文字の接触箇所を判別することが可能となり、接触箇所を判別する際の文字の傾きの影響を除去することが可能となることから、パターンの接触箇所が黒画素数ヒストグラムの極小点に対応しない場合においても、パターンの接触箇所を効率よく見つけ出すことが可能となり、文字領域の切り出し精度を向上させることが可能となる。
【００１０】
また、本発明の一態様によれば、パターンの端点、交点、分岐点または屈曲点を検出し、これらの点から文字同士の接触点を見つけるようにしている。
このことにより、文字同士が接触した場合、その接触点は、通常、端点、交点、または屈曲点になるので、文字同士の接触点の候補を効率よく見つけることが可能となる。
【００１１】
また、本発明の一態様によれば、パターンの特徴点の位置でパターンを切断した場合、文字の配列方向にパターンが分離されないものを、文字同士の接触点の候補から除くようにしている。
【００１２】
このことにより、文字の接触方向とは異なる方向にパターンが切断される切断箇所を文字同士の接触点の候補から除くことが可能となり、文字同士の接触点とはならない切断箇所を文字同士の接触点の候補として考慮する必要がなくなることから、文字同士の接触点を効率よく見つけることが可能となる。
【００１３】
また、本発明の一態様によれば、パターンの接続関係を、パターンの特徴点を頂点とし、前記頂点で挟まれた線分を辺とするグラフで表現するようにしている。
【００１４】
このことにより、パターンの接続情報のみを画像データから抽出することが可能となり、パターンの接続関係を効率的に評価することが可能となることから、文字同士の接触点を効率よく見つけることが可能となる。
【００１５】
また、本発明の一態様によれば、パターンの接続関係を頂点隣接行列で表し、頂点隣接行列の対角化ブロック数をカウントすることにより、グラフの連結成分数を求めるようにしている。
【００１６】
このことにより、グラフの連結成分数を効率よく求めることが可能となり、パターンを特徴点で切断した際に、パターンが分離するかどうかを容易に調べることが可能となることから、文字同士の接触点を効率よく見つけることが可能となる。
【００１７】
また、本発明の一態様によれば、グラフの辺の除去を行った時の前記グラフの連結成分数の変化に基づいて、接触文字の切断箇所を検出するようにしている。
このことにより、パターンの連結成分数を求める場合に、情報量の多い画像データから直接求める必要がなくなり、画像データと比べて情報量の少ないグラフデータから連結成分数を求めることが可能となることから、点接触の場合の接触位置を高速に検出することが可能となる。
【００１８】
また、本発明の一態様によれば、第１の線分に接触している第２の線分の端点が検出された場合、前記第１の線分方向の黒画素ランレングスが急激に減少する箇所で、パターンを切断するようにしている。
【００１９】
このことにより、グラフ上の頂点で特定された接触箇所から実際のパターンの切断箇所を求めることが可能となり、点接触前のパターンの形状を再現可能な位置で、接触パターンを切断することが可能となる。
【００２０】
また、本発明の一態様によれば、グラフの辺及びその辺の両端の特徴点の二重化を行った時の前記グラフの連結成分数の変化に基づいて、接触文字の切断箇所を検出するようにしている。
【００２１】
このことにより、パターンの連結成分数を求める場合に、情報量の多い画像データから直接求める必要がなくなり、画像データと比べて情報量の少ないグラフデータから連結成分数を求めることが可能となることから、辺接触の場合の接触位置を高速に検出することが可能となる。
【００２２】
また、本発明の一態様によれば、辺同士の重なりが検出された場合、その辺を垂直方向に二等分した位置で、パターンを切断するようにしている。
このことにより、グラフ上の辺で特定された接触箇所から実際のパターンの切断箇所を求めることが可能となり、辺接触前のパターンの形状を再現可能な位置で、パターンを切断することが可能となる。
【００２３】
また、本発明の一態様によれば、１つの接触位置に対して、接触位置を示す候補点が複数得られた場合、それらの候補点で切断したパターンの文字認識結果に基づいて、それらの候補点が接触点かどうかを判別するようにしている。
【００２４】
ここで、接触位置でない点で文字パターンを切断した場合は、文字でないパターンが切り出され、そのパターンの文字との相違度は高くなり、接触位置で文字パターンを切断した場合は、文字パターンが切り出され、その文字パターンの文字との相違度は低くなる。このため、接触位置でない点が接触位置を示す候補点として検出された場合においても、その候補点を接触点から除外することが可能となり、文字の接触箇所を精度よく見つけ出すことが可能となる。
【００２５】
また、本発明の一態様によれば、切断されたパターンを他のパターンと組み合わせることにより複数の文字候補のパターンを切り出す。そして、それらのパターンと文字との相違度の合計が最も低くなる組み合わせに基づいて、パターンの接触箇所を判定する。
【００２６】
このことにより、相違度の低い文字の切り出し位置が検出された場合においても、それ以外の領域に残っているパターンの文字との相違度が高い場合には、その切り出し位置を文字同士の接触箇所でないと判断することが可能となり、文字列のパターンから相違度の低い文字の切り出し位置の候補が複数得られた場合においても、それらの候補を絞り込むことが可能となり、文字同士の接触箇所の検出精度を向上させることが可能となる。
【００２７】
【発明の実施の形態】
以下、本発明の一実施例に係わるパターン抽出装置について図面を参照しながら説明する。図１は、本発明の一実施例に係わるパターン抽出装置の構成を示すブロック図である。
【００２８】
図１において、特徴点検出手段１は、パターンの特徴点を検出する。ここで、特徴点は、パターンの端点、交点、または屈曲点とすることができる。接続関係判別手段２は、特徴点検出手段１により検出された特徴点の接続関係を判別する。接触箇所判別手段３は、接続関係判別手段２により判別された接続関係に基づいて、パターンの接触箇所を判別する。ここで、パターンを構成する線分の接続関係は、パターンが傾いてもそのまま保存される。また、文字同士が接触した場合、その接触箇所には、パターンの交点、分岐点または屈曲点が形成される。このため、パターンの特徴点の接続関係を調べることにより、パターンが傾いている場合においても、文字同士の接触箇所を精度よく検出することが可能となる。
パターンから抽出された特徴点が文字同士の接触箇所であるかどうか調べる場合、その特徴点の位置でパターンを切り離した時に、パターンが２つに分離するかどうかにより判断する。
【００２９】
ここで、画像データの情報量は膨大であり、画像データそのものを直接処理して、パターンの連結成分数を調べると、時間がかかる。そこで、接触箇所判別手段３は、特徴点の接続関係をグラフで表現するようにしてもよい。そして、グラフの辺や頂点を操作した時にグラフの連結成分数が変化するかどうかを調べることより、パターンの接触箇所を判別するようにしてもよい。このことにより、パターンの特徴点の接続関係を表すために必要な情報のみを画像データから抽出して、パターンの特徴点の接続関係を調べることが可能となり、処理時間を短縮することができる。
【００３０】
また、接触箇所判別手段３は、特徴点の接続関係を表すグラフを頂点隣接行列で表現するようにしてもよい。そして、グラフの辺や頂点の操作する前と後で頂点隣接行列の対角化ブロック数が変化するかどうかを調べることより、パターンの接触箇所を判別するようにしてもよい。
【００３１】
図２は、本発明の一実施例に係わる文字認識装置の構成を示すブロック図である。なお、以下の実施例では、文字が横書きで記入されている場合について説明するが、文字が縦書きで記入されている場合についても、行を列に置き換えることにより、同様に処理することができる。
【００３２】
図２において、ＯＣＲ（光学的文字認識装置）１１は、手書き文字が記入された帳票や文書を読み込み、手書き文字の認識結果を出力する。観測部１２は、ＣＣＤやスキャナなどによって手書き文字が記入された帳票や文書を取り込み、取り込んだ画像データを白黒の二値化データに変換する。文字列抽出部１３は、画像データのパターンを１行ごとに切り出し、文字列を抽出する。接触文字判定部１４は、各行画像中のパターンのラベリングを行うことにより、各行画像中のパターンの連結成分を抽出する。そして、連結成分の外接矩形のサイズや縦横比などを調べることにより、文字どうしが接触しているパターンかどうかを判定する。例えば、連結成分の外接矩形の横方向の長さが縦方向の長さよりも所定値以上長い場合、その連結成分は、文字どうしが接触しているパターンであると判定する。
【００３３】
接触候補箇所決定・切断部１５は、接触文字判定部１４で接触文字と判定されたパターンに対し、切断候補箇所を決定する。ここで、接触候補箇所決定・切断部１５は、切断候補箇所を決定する場合、文字列の黒画素数ヒストグラムの極小点を切断候補箇所に決定するのではなく、接触文字と判定されたパターンを構成する線分の接続関係を調べ、その線分の接続点を切断候補箇所に決定する。このことにより、文字が傾いていたり、接触部分に別の文字線分が重なったり、文字の線分同士が接触したりしているために、文字の接触箇所で黒画素数ヒストグラムが極小にならない場合においても、文字の接触箇所を精度よく識別することができる。ここで、パターンの接続点を効率よく見つけるため、パターンの接続関係をグラフで表現したり、頂点隣接行列を用いたりすることができる。
【００３４】
切断候補箇所が決まると、接触文字と判定されたパターンを切断候補箇所で切断することにより、部分パターンを生成する。候補文字ラティス生成部１６は、二端子有向グラフの最短経路問題におけるダイクストラの手法（以下、候補文字ラティス法と称す。）により、候補文字二端子有向グラフ（以下、候補文字ラティスと称す。）を生成する。すなわち、接触候補箇所決定・切断部１５により切断された部分パターンと行画像中の他のパターンの連結成分との可能な組み合せによる統合パターンを生成する。そして、その統合パターン、あるいは、統合前の単独パターンに対し、認識辞書部１７に登録されている文字種との比較を行い、第Ｎ位までの候補文字種及び相違度または類似度を求める。候補文字種及び相違度または類似度が求まると、候補文字ラティスを生成し、１文字領域と認識の第１次候補を決定する。
【００３５】
言語処理部１８は、知識辞書部１９を使って、認識の第１次候補をチェックし、第１次候補に文法的に間違いがあれば、第１次候補を下位の候補に置き換える。そして、文法的に間違いのない候補が得られると、その候補を文字認識結果として決定するとともに、その候補の位置を１文字領域と決定する。
【００３６】
図３は、図２の接触候補箇所決定・切断部１５の処理を示すフローチャートである。
図３において、接触候補箇所決定・切断部１５は、接触文字判定部１４により抽出された接触パターンの細線化を行う（ステップＳ１）。ここで、細線化は、接触パターンから端点、交点、または屈曲点を求める場合に、これらの点を求めやすくするために行う。従って、細線化は、元のパターンに含まれる端点、交点、または屈曲点が保存されるように行う。
【００３７】
図４は、本発明の一実施例に係わる細線化パターンの具体例を示す図である。図４（ａ）において、Ｅ１の点で接触している「静岡」というパターンを細線化することにより、Ｅ１’の点で接触している図４（ｂ）の細線化パターンを得ることができる。
【００３８】
細線化パターンが得られると、その細線化パターンから端点、交点、及び屈曲点を抽出し、これらの点をグラフの頂点とする（ステップＳ２）。すなわち、端点を１次の頂点、３本、４本の線分が交わる交点をそれぞれ、３次、４次の頂点とする。２次の頂点は、各辺における屈曲点とする。
【００３９】
図５は、次数２の頂点の決定方法を説明する図である。
図５において、２つの頂点に挟まれた辺上の着目点Ｐ０とその前後のサンプル点Ｐ１，Ｐ２を考え、Ｐ１を始点、Ｐ０を終点とするベクトルをｄ1 、Ｐ０を始点、Ｐ２を終点とするベクトルをｄ2 とした時、ベクトルｄ1 、ｄ2 の成す角θを以下の式で求める。
【００４０】
θ＝ｃｏｓ-1（ｄ1 ・ｄ2 ／｜ｄ1 ｜・｜ｄ2 ｜）
ここで、｜ｄ1 ｜、｜ｄ2 ｜はそれぞれ、ベクトルｄ1 、ｄ2 の大きさである。角度θが、しきい値θthより大きい場合、すなわち、θ＞θthの場合、Ｐ０を次数２の頂点とする。
【００４１】
グラフの頂点が求まると、輪郭追跡の手法で細線化パターンを探索することにより、細線化パターンから抽出された端点、交点、及び屈曲点の接続関係を求め、頂点間の隣接関係を求める（ステップＳ３）。そして、頂点の隣接関係が求まると、それらの頂点を辺で接続したグラフを生成する。
【００４２】
図６（ａ）は、点接触したパターンの具体例を示す図、図６（ｂ）は、図６（ａ）のパターンをグラフ化した例を示す図である。
図６（ａ）において、Ｅ２の位置で点接触している「上山」というパターンが接触文字判定部１４により抽出された場合、このパターンを細線化し、細線化パターンの探索を行いながら、細線化パターンの探索方向を調べる。そして、探索時に、探索方向が所定の角度以上変化した場合、その点をグラフの２次の頂点とし、探索時に、探索方向が２つに枝分かれした場合、その点をグラフの３次の頂点とし、探索時に、探索方向が３つに枝分かれした場合、その点をグラフの４次の頂点とする。
【００４３】
以上の処理により、図６（ａ）のパターンからＶ０〜Ｖ１１の頂点が検出され、これらの頂点を辺ｅ０〜ｅ１０で接続した図６（ｂ）のグラフＧ１を生成することができる。
【００４４】
接触候補箇所決定・切断部１５は、文字接触パターンに対応したグラフを生成すると、そのグラフに対応した頂点隣接行列を求める（ステップＳ４）。頂点隣接行列は、グラフの各頂点に対応する行成分及び列成分を有する。そして、頂点間が１辺で連結している場合、その２つの頂点で特定される行列成分は１の値をとり、頂点間が連結していない場合、その２つの頂点で特定される行列成分は０の値をとる性質を持つ。
【００４５】
図７（ａ）は、図６（ｂ）のグラフの頂点隣接行列を示す図である。
図７（ａ）において、行及び列の各成分は、グラフＧ１の頂点Ｖ０〜Ｖ１１にそれぞれ対応している。ここで、図６（ｂ）のグラフＧ１において、２つの頂点Ｖ０〜Ｖ１１を接続する辺ｅ０〜ｅ１０がある場合、その２つの頂点Ｖ０〜Ｖ１１で特定される行列成分は１、２つの頂点Ｖ０〜Ｖ１１を接続する辺ｅ０〜ｅ１０がない場合、その２つの頂点Ｖ０〜Ｖ１１で特定される行列成分は０となる。例えば、図６（ｂ）のグラフＧ１において、頂点Ｖ３、Ｖ４は辺ｅ３で接続されているので、頂点Ｖ３、Ｖ４で特定される行列成分（４行５列目の成分及び５行４列目の成分）は、１となっている。また、図６（ｂ）のグラフＧ１において、頂点Ｖ２、Ｖ５は辺ｅ０〜ｅ１０で接続されていないので、頂点Ｖ２、Ｖ５で特定される行列成分（３行６列目の成分及び６行３列目の成分）は、０となっている。
【００４６】
頂点隣接行列が求まると、頂点隣接行列の行または列を入れ替えることにより、頂点隣接行列のブロック対角化を行う。そして、ブロック対角化後の頂点隣接行列に含まれる対角化ブロック数をカウントする（ステップＳ５）。ブロック対角化後の頂点隣接行列に含まれる対角化ブロック数は、グラフの連結成分数に対応しており、ブロック対角化後の頂点隣接行列に含まれる対角化ブロック数をカウントすることにより、グラフの連結成分数を求めることができる。
【００４７】
次に、点接触箇所候補の導出を行う（ステップＳ６）。この点接触箇所候補の導出では、グラフの辺を１つずつ除去し、辺の除去によりグラフが２つに分離する場合、例えば、辺を除去する前のグラフの連結成分が１であるとすると、辺を除去した後のグラフの連結成分が２に増加する場合、その辺の両端の頂点を点接触の切断箇所の候補とする。
【００４８】
ここで、辺を除去した後のグラフに対応する頂点隣接行列を、辺を除去する前のグラフに対応する頂点隣接行列から求め、頂点隣接行列の行または列を入れ替えることにより、頂点隣接行列のブロック対角化を行う。そして、辺を除去する前のグラフに対応する頂点隣接行列の対角化ブロック数と、辺を除去した後のグラフに対応する頂点隣接行列の対角化ブロック数との差分が１となるかどうかを調べることにより、グラフが２つに分離するかどうかを判別することができる。
図６（ｃ）は、図６（ｂ）のグラフから辺を除去した場合にグラフの連結成分数が増加する例を示す図である。
【００４９】
図６（ｃ）において、図６（ｂ）のグラフＧ１から辺ｅ４を除去した場合、頂点Ｖ０〜Ｖ４からなるグラフＧ２と、頂点Ｖ５〜Ｖ１１からなるグラフＧ３とに分離する。この場合、辺ｅ４の両端の頂点Ｖ４、Ｖ６を点接触の切断箇所の候補とする。このことにより、図６（ａ）の接触パターンの接触点Ｅ２を切断箇所の候補として検出することが可能となる。
【００５０】
図６（ｂ）のグラフＧ１から辺ｅ０〜ｅ１０を１つずつ除去し、グラフＧ１が２つに分離するかどうかを調べることにより、点接触による切断箇所の候補として、６つの頂点Ｖ１、Ｖ４、Ｖ６、Ｖ７、Ｖ９、Ｖ１１が検出される。なお、この段階では、接触点Ｅ２に対応する頂点Ｖ６の他に、文字自体に含まれる交点や屈曲点に対応する頂点Ｖ１、Ｖ４、Ｖ７、Ｖ９、Ｖ１１も検出される。
【００５１】
図７（ｂ）は、図６（ｃ）のグラフＧ２、Ｇ３の頂点隣接行列を示す図である。
図７（ｂ）において、図７（ａ）の頂点隣接行列から図７（ｂ）の頂点隣接行列を求める場合、図６（ｂ）のグラフＧ１から除去された辺の両端の頂点に対応する行列成分を０にする。例えば、図６（ｂ）のグラフＧ１から辺ｅ４を除去することにより、図６（ｃ）のグラフＧ２、Ｇ３が生成されたものとする。この場合、辺ｅ４の両端の頂点はＶ４及びＶ６であるので、図７（ａ）の頂点隣接行列の頂点Ｖ４、Ｖ６で特定される成分、すなわち、（５、７）成分及び（７、５）成分を０にする。この結果、図７（ｂ）の頂点隣接行列が得られる。
【００５２】
図７（ｂ）の頂点隣接行列は、２つの正方行列Ａ１、Ａ２が対角斜め方向に配置されており、２つの正方行列Ａ１、Ａ２の直和の形で表現できる。ここで、頂点隣接行列のブロック対角化により得られる対角化ブロック数（対角斜め方向に配置される正方行列の個数）は、その頂点隣接行列に対応するグラフの連結成分数を表している。このため、頂点隣接行列を用いることにより、グラフから辺を除去した時に、グラフが２つに分離するかどうかを判定することができ、その時の辺の両端の頂点を点接触の切断箇所の候補とすることができる。
【００５３】
図８は、頂点隣接行列から接触点の候補を求める方法を示すフローチャートである。なお、図８のフローチャートでは、文字同士が複数の箇所で接触するのは、通常２点程度であるので、２点接触まで求める処理を示した。
【００５４】
図８において、グラフの頂点から２個選び、その頂点に対応する頂点隣接行列のｊ行ｋ列成分が１かどうかを判定する（ステップＳ２１）。そして、頂点隣接行列のｊ行ｋ列成分が１の場合、ｊ行ｋ列成分及びｋ行ｊ列成分を０にする（ステップＳ２２）。次に、ｊ行ｋ列成分及びｋ行ｊ列成分を０にした頂点隣接行列の行または列を入れ替えることにより、ｊ行ｋ列成分及びｋ行ｊ列成分を０にした頂点隣接行列のブロック対角化を行い、ブロック対角化後の対角化ブロック数をカウントする（ステップＳ２３）。
【００５５】
次に、ｊ行ｋ列成分及びｋ行ｊ列成分を０にする前の頂点隣接行列の対角化ブロック数と、ｊ行ｋ列成分及びｋ行ｊ列成分を０にした後の頂点隣接行列の対角化ブロック数とを比較し（ステップＳ２４）、ｊ行ｋ列成分及びｋ行ｊ列成分を０にした後の頂点隣接行列の対角化ブロック数が、ｊ行ｋ列成分及びｋ行ｊ列成分を０にする前の頂点隣接行列の対角化ブロック数より１だけ増加した場合、頂点ｊと頂点ｋとを１点接触の切断箇所の候補とする（ステップＳ２５）。以上の処理を頂点隣接行列のｊ行ｋ列の全ての成分について繰り返す。
【００５６】
次に、一点接触の切断箇所の候補を除いたグラフの頂点から４個選び、その頂点に対応する頂点隣接行列のｊ行ｋ列成分及びｍ行ｎ列成分が１かどうかを判定する（ステップＳ２６）。そして、頂点隣接行列のｊ行ｋ列成分及びｍ行ｎ列成分が１の場合、ｊ行ｋ列成分及びｋ行ｊ列成分を０にするとともに、ｍ行ｎ列成分及びｎ行ｍ列成分を０にする（ステップＳ２７）。次に、これらの４つの成分を０にした頂点隣接行列の行または列を入れ替えることにより、これらの４つの成分を０にした頂点隣接行列のブロック対角化を行い、ブロック対角化後の対角化ブロック数をカウントする（ステップＳ２８）。
【００５７】
次に、これらの４つの成分を０にする前の頂点隣接行列の対角化ブロック数と、これらの４つの成分を０にした後の頂点隣接行列の対角化ブロック数とを比較し（ステップＳ２９）、これらの４つの成分を０にした後の頂点隣接行列の対角化ブロック数が、これらの４つの成分を０にする前の頂点隣接行列の対角化ブロック数より１だけ増加した場合、頂点ｊ、頂点ｋ、頂点ｍ、頂点ｎを２点接触の切断箇所の候補とする（ステップＳ３０）。以上の処理を頂点隣接行列のｊ行ｋ列及びｍ行ｎ列の全ての成分の組み合わせについて繰り返す。
【００５８】
次に、辺接触候補箇所の導出を行う（ステップＳ７）。この辺接触候補箇所の導出では、グラフの１辺とその辺の両端に接続する２頂点を二重化し、二重化によりグラフが２つに分離する場合、例えば、二重化する前のグラフの連結成分が１であるとすると、二重化した後のグラフの連結成分が２に増加する場合、その辺を辺接触の切断箇所の候補とする。
【００５９】
ここで、辺及びその辺の両端に接続する２頂点を二重化した後のグラフに対応する頂点隣接行列を、辺及びその辺の両端に接続する２頂点を二重化する前のグラフに対応する頂点隣接行列から求め、頂点隣接行列の行または列を入れ替えることにより、頂点隣接行列のブロック対角化を行う。そして、二重化する前のグラフに対応する頂点隣接行列の対角化ブロック数と、二重化した後のグラフに対応する頂点隣接行列の対角化ブロック数との差分が１となるかどうかを調べることにより、グラフが２つに分離するかどうかを判別してもよい。
【００６０】
図９（ａ）は、辺接触したパターンの具体例を示す図、図９（ｂ）は、図９（ａ）のパターンをグラフ化した例を示す図、図９（ｃ）は、図９（ｂ）のグラフの辺及びその辺の端点の二重化を行った場合にグラフの連結成分数が増加する例を示す図である。
【００６１】
図９（ａ）において、Ｅ３の位置で辺接触している「山口」というパターンが接触文字判定部１４により抽出された場合、このパターンを細線化し、細線化パターンの探索を行いながら、細線化パターンの探索方向を調べる。そして、探索時に、探索方向が所定の角度以上変化した場合、その点をグラフの２次の頂点とし、探索時に、探索方向が２つに枝分かれした場合、その点をグラフの３次の頂点とし、探索時に、探索方向が３つに枝分かれした場合、その点をグラフの４次の頂点とする。
【００６２】
以上の処理により、図９（ａ）のパターンからＶ０〜Ｖ７の頂点が検出され、これらの頂点を辺ｅ０〜ｅ７で接続した図９（ｂ）のグラフＧ１１を生成することができる。
【００６３】
次に、図９（ｂ）のグラフＧ１１において、例えば、辺ｅ４及びその辺ｅ４の両端の頂点Ｖ４、Ｖ５を二重化することにより、辺ｅ４’及びその辺ｅ４’の両端に接続する頂点Ｖ４’、Ｖ５’を生成する。ここで、二重化を行う場合、頂点Ｖ４、Ｖ５と他の頂点Ｖ０〜Ｖ３、Ｖ６、Ｖ７との接続関係を調べる。そして、頂点Ｖ４、Ｖ５については、頂点Ｖ４、Ｖ５と左方向に隣接する頂点との接続関係のみを付与し、頂点Ｖ４’、Ｖ５’については、頂点Ｖ４、Ｖ５と右方向に隣接する頂点との接続関係のみを付与する。
【００６４】
例えば、頂点Ｖ４に隣接している頂点として、頂点Ｖ６が検出されると、頂点Ｖ６の頂点Ｖ４に対する隣接方向を調べる。この結果、頂点Ｖ６が頂点Ｖ４に対して右方向に隣接していると判別されると、グラフＧ１２の頂点Ｖ４から頂点Ｖ６を切り離し、その頂点Ｖ６をグラフＧ１３の頂点Ｖ４’に接続する。また、頂点Ｖ５に隣接している頂点として、頂点Ｖ３、Ｖ７が検出されると、頂点Ｖ３、Ｖ７の頂点Ｖ５に対する隣接方向を調べる。この結果、頂点Ｖ３は頂点Ｖ５に対して左方向に隣接していると判別されると、グラフＧ１３の頂点Ｖ５’から頂点Ｖ３を切り離し、その頂点Ｖ３をグラフＧ１２の頂点Ｖ５に接続する。また、頂点Ｖ７は頂点Ｖ５に対して右方向に隣接していると判別されると、グラフＧ１２の頂点Ｖ５から頂点Ｖ７を切り離し、その頂点Ｖ７をグラフＧ１３の頂点Ｖ５’に接続する。
【００６５】
この結果、図９（ｃ）に示すように、頂点Ｖ０〜Ｖ５からなるグラフＧ１２と、頂点Ｖ４’、Ｖ５’、Ｖ６、Ｖ７からなるグラフＧ１３とに分離する。この場合、辺ｅ４を辺点接触の切断箇所の候補とする。このことにより、図９（ａ）の接触パターンの接触辺Ｅ３を切断箇所の候補として検出することが可能となる。
図９（ｂ）のグラフにおいて、辺ｅ０〜ｅ７を１つずつ二重化し、グラフが２つに分離するかどうかを調べることにより、辺接触による切断箇所の候補として、２つの辺ｅ０、ｅ４を検出することができる。なお、この段階では、接触箇所Ｅ３に対応する辺ｅ４の他に、文字自体を構成する線分に対応する辺ｅ０も検出される。
【００６６】
図１０（ａ）は、図９（ｂ）のグラフの頂点隣接行列を示す図、図１０（ｂ）は、図９（ｃ）のグラフの頂点隣接行列を示す図である。
図１０（ａ）において、行及び列の各成分は、グラフの頂点Ｖ０〜Ｖ７にそれぞれ対応している。ここで、図９（ｂ）のグラフにおいて、２つの頂点Ｖ０〜Ｖ７を接続する辺ｅ０〜ｅ７がある場合、その２つの頂点Ｖ０〜Ｖ７で特定される行列成分は１、２つの頂点Ｖ０〜Ｖ７を接続する辺ｅ０〜ｅ７がない場合、その２つの頂点Ｖ０〜Ｖ７で特定される行列成分は０となる。
【００６７】
図１０（ａ）の頂点隣接行列から図１０（ｂ）の頂点隣接行列を求める場合、図９（ｂ）の二重化された辺の両端の頂点に対応する行及び列をコピーする。そして、コピー対象とされた行及び列の成分のうち、右方向に隣接する頂点の成分を０にするとともに、コピーにより新たに挿入された行及び列の成分のうち、左方向に隣接する頂点の成分を０にする。
【００６８】
例えば、図９（ｂ）のグラフの辺ｅ４及びその辺ｅ４の両端の頂点Ｖ４、Ｖ５を二重化することにより、辺ｅ４’及び辺ｅ４’の両端に接続する頂点Ｖ４’、Ｖ５’を生成し、図９（ｃ）のグラフが生成されたものとする。この場合、図１０（ａ）の頂点隣接行列の頂点Ｖ４に対応する行及び列をコピーすることにより、頂点Ｖ４’に対応する行及び列を新たに生成するとともに、頂点Ｖ５に対応する行及び列をコピーすることにより、頂点Ｖ４’に対応する行及び列を新たに生成する。ここで、頂点Ｖ４に対応する行及び列の成分のうち、頂点Ｖ４の右方向に隣接する頂点Ｖ６に対応する成分を０とし、頂点Ｖ５に対応する行及び列の成分のうち、頂点Ｖ５の右方向に隣接する頂点Ｖ７に対応する成分を０とし、頂点Ｖ５’に対応する行及び列の成分のうち、頂点Ｖ５の左方向に隣接する頂点Ｖ３に対応する成分を０とする。そして、行及び列を入れ替えてブロック対角化を行うことにより、図１０（ｂ）の頂点隣接行列が得られる。
【００６９】
図１０（ｂ）の頂点隣接行列は、２つの正方行列Ａ１、Ａ２が対角斜め方向に配置されており、２つの正方行列Ａ１、Ａ２の直和の形で表現できる。ここで、頂点隣接行列のブロック対角化により得られる対角化ブロック数（対角斜め方向に配置される正方行列の個数）は、その頂点隣接行列に対応するグラフの連結成分数を表している。このため、頂点隣接行列を用いることにより、グラフの辺を二重化した時に、グラフが２つに分離するかどうかを判定することができ、その時の辺を辺接触の切断箇所の候補とすることができる。
【００７０】
図１１は、頂点隣接行列から辺接触の候補を求める方法を示すフローチャートである。
図１１において、頂点隣接行列のｊ行ｋ列成分が１かどうかを判定する（ステップＳ４１）。ここで、頂点隣接行列のｊ行ｋ列成分が１の場合、ｊ行目に対応する頂点とｋ列目に対応する頂点との間に挟まれた辺に対応するパターンの文字線幅ｈが、以下の条件を満たすかどうかを調べる。
【００７１】
Ｈ×ａ＜ｈ  （１．０＜ａ）
ここで、Ｈは平均文字幅、ａは１より大きい値をとる定数で、実験により定めることができる。そして、この条件を満たさない辺は、二重化の候補から除外する（ステップＳ４２）。この処理により、二重化する辺の候補として、辺同士が接触したために線幅が他の辺よりも太くなっているものだけを選ぶことができ、辺接触していないような細い線幅の辺を、辺接触の候補から除去することができる。
【００７２】
また、横書きの場合は縦方向、縦書きの場合は横方向の辺のみを二重化するため、辺の傾きにも、しきい値を設けるようにする。すなわち、対象とする辺の傾きをＳ、傾きのしきい値をＳｔｈとすると、
Ｓ＞Ｓｔｈ（横書きの場合）
Ｓ＜Ｓｔｈ（縦書きの場合）
の条件を満たす候補のみについて、二重化を行うようにする（ステップＳ４２）。なお、しきい値Ｓｔｈは、実験により定めることができる。
【００７３】
次に、頂点隣接行列のｊ行目をｊ＋１行目にコピーし、頂点隣接行列のｊ＋１行目以降をシフトするとともに、頂点隣接行列のｊ列目をｊ＋１列目にコピーし、頂点隣接行列のｊ＋１列目以降をシフトする（ステップＳ４３）。
【００７４】
次に、横書きの場合、ｊ番目の頂点の右方向に隣接する頂点がある場合、ｊ行目及びｊ列目の成分のうち、右方向に隣接する頂点に対応する成分を０とし、ｊ番目の頂点の左方向に隣接する頂点がある場合、ｊ＋１行目及びｊ＋１列目の成分のうち、左方向に隣接する頂点に対応する成分を０とする（ステップＳ４４）。なお、縦書きの場合、ｊ番目の頂点の上方向に隣接する頂点がある場合、ｊ行目及びｊ列目の成分のうち、上方向に隣接する頂点に対応する成分を０とし、ｊ番目の頂点の下方向に隣接する頂点がある場合、ｊ＋１行目及びｊ＋１列目の成分のうち、下方向に隣接する頂点に対応する成分を０とする。
【００７５】
次に、頂点隣接行列のｋ行目をｋ＋１行目にコピーし、頂点隣接行列のｋ＋１行目以降をシフトするとともに、頂点隣接行列のｋ列目をｋ＋１列目にコピーし、頂点隣接行列のｋ＋１列目以降をシフトする（ステップＳ４５）。
【００７６】
次に、横書きの場合、ｋ番目の頂点の右方向に隣接する頂点がある場合、ｋ行目及びｋ列目の成分のうち、右方向に隣接する頂点に対応する成分を０とし、ｋ番目の頂点の左方向に隣接する頂点がある場合、ｋ＋１行目及びｋ＋１列目の成分のうち、左方向に隣接する頂点に対応する成分を０とする（ステップＳ４６）。なお、縦書きの場合、ｋ番目の頂点の上方向に隣接する頂点がある場合、ｋ行目及びｋ列目の成分のうち、上方向に隣接する頂点に対応する成分を０とし、ｋ番目の頂点の下方向に隣接する頂点がある場合、ｋ＋１行目及びｋ＋１列目の成分のうち、下方向に隣接する頂点に対応する成分を０とする。
【００７７】
次に、ｊ行ｋ列成分で特定される辺を二重化したグラフに対応する頂点隣接行列の行または列を入れ替えることにより、その頂点隣接行列のブロック対角化を行い、ブロック対角化後の対角化ブロック数をカウントする（ステップＳ４７）。次に、ｊ行ｋ列成分で特定される辺を二重化する前のグラフに対応する頂点隣接行列の対角化ブロック数と、ｊ行ｋ列成分で特定される辺を二重化した後のグラフに対応する頂点隣接行列の対角化ブロック数とを比較し（ステップＳ４８）、ｊ行ｋ列成分で特定される辺を二重化した後のグラフに対応する頂点隣接行列の対角化ブロック数が、ｊ行ｋ列成分で特定される辺を二重化する前のグラフに対応する頂点隣接行列の対角化ブロック数より１だけ増加した場合、頂点ｊと頂点ｋとの間に挟まれる辺を辺接触の切断箇所の候補とする（ステップＳ４９）。以上の処理を、ｊ＝１〜全頂点数、ｋ＝ｊ＋１〜全頂点数に対して繰り返す。
【００７８】
図３のステップＳ６、Ｓ７の処理により、点接触箇所候補及び辺接触箇所候補がグラフから抽出されると、接触箇所候補の絞り込みを行う（ステップＳ８〜Ｓ１０）。この接触箇所候補の絞り込みは、文字列方向と垂直方向にパターンが分割されることを防止するために行う。例えば、横書きの文字の場合、文字同士の接触は横方向に発生し、縦書きの文字の場合、文字同士の接触は縦方向に発生する。このため、横書きの文字の場合、パターンを横方向に分割する接触箇所候補のみを選別して、パターンを縦方向に分割する接触箇所候補を除去する。また、されないようにする。また、縦書きの文字の場合、パターンを縦方向に分割する接触箇所候補のみを選別して、パターンを横方向に分割する接触箇所候補を除去する。
【００７９】
ここでは、分離した各々のグラフの文字列方向のサイズをＷｊとし、元のグラフの文字列方向のサイズをＷとすると、
Ｗ×Ｃ１＜Ｗｊ＜Ｗ×Ｃ２
（０．０＜Ｃ１＜Ｃ２＜１．０、ｊ＝１，２）
となる切断候補のみを選択する。ここで、Ｃは、０と１の間の値をとる定数であり、実験により定めることができる。
【００８０】
接触箇所候補が決定すると、接触パターンの切断を行い、部分パターンを作成する（ステップＳ１１）。接触パターンの切断では、接触箇所候補として決定されたグラフ上の頂点または辺から実際のパターン上での切断位置を求め、その切断位置で接触パターンの切断する。
【００８１】
図１２は、点接触のパターンの切断方法を示す図である。
図１２（ａ）において、グラフ上で点接触箇所の候補が決定すると、点接触箇所の候補として決定されたグラフ上の頂点に対応する接触パターン２１上の切断候補点２２を求める。切断候補点２２が求まると、端点が接触している文字線２４を、切断候補点２２から細線化パターン２５の辺に沿って追跡し、もう一方の辺２６と平行方向の黒画素ランレングスを求める。この結果、黒画素ランレングスは、図１２（ｂ）に示すように、文字線２４の接触箇所２３の位置で急激に減少する。そこで、黒画素ランレングスが急激に減少する箇所Ｋに対応する位置で、接触パターン２１を切断する。この結果、図１２（ｃ）に示すように、接触パターン２１の文字線２４に対応した文字線２４’と接触パターン２１の文字線２６に対応した文字線２６’とを切り出すことができる。
【００８２】
図１３は、辺接触のパターンの切断方法を示す図である。
図１３（ａ）において、グラフ上で辺接触箇所の候補が決定すると、辺接触箇所の候補として決定されたグラフ上の辺に対応する接触パターン２１上の文字線３１を求める。文字線３１が求まると、その文字線３１を細線化パターン３２の辺で２分する。この結果、図１３（ｂ）に示すように、接触パターン３１の文字線３３に対応した文字線３３’と接触パターン３１の文字線３４に対応した文字線３４’とを切り出すことができる。
【００８３】
図１４は、図９（ａ）のパターンの切断例を示す図である。
図１４において、図９（ｂ）のグラフから点接触の候補となる頂点または辺接触の候補となる辺が求まると、これらの接触箇所の候補の位置で図９（ａ）のパターンを切断することにより、部分パターン４１〜４４を得ることができる。
【００８４】
部分パターンが求まると、単独パターン、あるいは、部分パターンと同一行の文字列に含まれる他のパターンとの可能な組み合わせにより得られる統合パターンに対し、文字認識を実行する。そして、認識候補文字種及び相違度（あるいは類似度）を求め、例えば、候補文字ラティス等の方法を用いることにより、一文字領域と文字認識候補を決定する。
【００８５】
図１５は、切断されたパターンの統合方法を示す図である。
図１５において、図１４の部分パターン４１〜４４が求まると、統合後の横方向の長さＷを算出し、統合後の横方向の長さＷがしきい値Ｗｔｈを越えた時に統合をストップする。例えば、図１５（ａ）において、図１４の部分パターン４１の横方向の長さＷ１がしきい値Ｗｔｈを越えているかどうか調べ、長さＷ１がしきい値Ｗｔｈを越えていない場合、図１５（ｂ）に示すように、図１４の部分パターン４１、４２を統合した統合パターン４５を生成する。
【００８６】
次に、統合パターン４５の横方向の長さＷ２がしきい値Ｗｔｈを越えているかどうか調べ、長さＷ２がしきい値Ｗｔｈを越えていない場合、図１５（ｃ）に示すように、図１５（ｂ）の統合パターン４５と図１４の部分パターン４３を統合した統合パターン４６を生成する。
【００８７】
次に、統合パターン４６の横方向の長さＷ３がしきい値Ｗｔｈを越えているかどうか調べ、長さＷ３がしきい値Ｗｔｈを越えていない場合、図１５（ｄ）に示すように、図１５（ｃ）の統合パターン４６と図１４の部分パターン４４を統合した統合パターン４７を生成する。
【００８８】
次に、統合パターン４７の横方向の長さＷ４がしきい値Ｗｔｈを越えているかどうか調べ、長さＷ４がしきい値Ｗｔｈを越えている場合、図１５（ｃ）の統合パターン４６と図１４の部分パターン４４との統合をストップする。
【００８９】
統合パターン４５、４６が求まると、統合パターン４５、４６及び部分パターン４１〜４４の文字認識を行い、文字との相違度の低いパターンを選別することにより、一文字ごとの切り出しを行うことができる。
【００９０】
図１６は、候補文字ラティス法による接触位置の決定方法を説明する図である。
図１６（ａ）において、「山口市」というパターンから部分パターン５１〜５５が切り出されたものとする。この場合、各パターンの横方向の長さを求めることにより、パターンの統合が可能かどうかを調べ、統合後のパターンの横方向の長さがしきい値Ｗｔｈ以下の場合、部分パターン５１〜５５を隣接パターンと統合する。この結果、部分パターン５１、５２を統合した統合パターン５６、部分パターン５２、５３を統合した統合パターン５７、部分パターン５１〜５３を統合した統合パターン５８、及び部分パターン５３、５４を統合した統合パターン５９が生成される。
【００９１】
部分パターン５１〜５５及び統合パターン５６〜５９が生成されると、これらのパターンの文字認識を実行し、「山口市」というパターンに対応するように、部分パターン５１〜５５及び統合パターン５６〜５９を組み合わせる。そして、これらの組み合わせの中から、最も相違度の低い組み合わせを選択する。
【００９２】
例えば、図１６（ｂ）において、部分パターンの組み合わせとして、Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５というパスを選択した場合、これらのパターンの相違度の合計は、２８４＋１８９＋１２６＋１７７＋２０３＝９７９となり、認識結果は「Ｕ−口市」となる。また、部分パターンの組み合わせとして、Ｐ６→Ｐ９→Ｐ５というパスを選択した場合、これらのパターンの相違度の合計は、４１９＋２０２＋２０３＝８２４となり、認識結果は「ル口市」となる。この処理を部分パターン５１〜５５及び統合パターン５６〜５９の全ての組み合わせについて行う。
【００９３】
この結果、最も相違度の低い組み合わせとして、Ｐ８→Ｐ４→Ｐ５というパスを選択することができ、統合パターン５８及び部分パターン５４，５５をそれぞれ一文字領域として切り出すことができる。ここで、統合パターン５８は「山口市」というパターンの中の「山」という文字に対応し、部分パターン５４は「山口市」というパターンの中の「口」という文字に対応し、部分パターン５５は「山口市」というパターンの中の「市」という文字に対応している。従って、「山口市」というパターンの中の「山」という文字と「口」という文字が辺接触している場合においても、１文字ごとに切り出すことができる。
【００９４】
図１７は、本発明の一実施例に係わるパターン抽出処理をソフトウエアを用いて実現した構成を示すブロック図である。
図１７において、６１は全体的な処理を行う中央演算処理ユニット（ＣＰＵ）、６２はリードオンリメモリ（ＲＯＭ）、６３はランダムアクセスメモリ（ＲＡＭ）、６４は通信インターフェイス、６５は通信ネットワーク、６６は入出力インターフェイス、６７は文字認識結果などを表示するディスプレイ、６８は文字認識結果などを印刷するプリンタ、６９はスキャナ７０により読み取られた画像データなどを一時的に格納するメモリ、７０は入力画像などを読み取るスキャナ、７１はキーボード、７２はマウスなどのポインティングデバイス、７３は記憶媒体を駆動するドライバ、７４はハードディスク、７５はＩＣメモリカード、７６は磁気テープ、７７はフロッピーディスク、７８はＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの光ディスク、７９はバスである。
【００９５】
パターン抽出処理や文字認識を行うプログラム、画像データなどは、ハードディスク７４、ＩＣメモリカード７５、磁気テープ７６、フロッピーディスク７７、光ディスク７８などの記憶媒体に格納される。そして、パターン抽出処理や文字認識を行うプログラム及び画像データを、これらの記憶媒体からＲＡＭ６３に読み出すことにより、文字領域の切り出しを行うことができる。また、パターン抽出処理や文字認識を行うプログラムを、ＲＯＭ６２に格納しておくこともできる。
【００９６】
さらに、パターン抽出処理や文字認識を行うプログラム、画像データ及び文字認識結果などを、通信ネットワーク６５を介して送受信したりすることもできる。通信インターフェイス６４に接続される通信ネットワーク６５として、例えば、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、アナログ電話網、デジタル電話網（ＩＳＤＮ：Ｉｎｔｅｇｒａｌ  Ｓｅｒｖｉｃｅ  Ｄｉｇｉｔａｌ  Ｎｅｔｗｏｒｋ）、ＰＨＳ（パーソナルハンディシステム）や衛星通信などの無線通信網を用いることができる。
【００９７】
ＣＰＵ６１は、パターン抽出処理を行うプログラムが起動されると、処理対象となる画像データのラベリングを行うことにより連結成分を抽出し、連結成分として抽出されたパターンの細線化を行う。細線化が終了すると、細線化パターンの探索を行うことにより、パターンの端点、交点、または屈曲点を抽出し、これらの端点、交点、または屈曲点の接続関係を調べる。接続関係が求まると、これらの接続関係をグラフで表現し、グラフの辺や頂点を操作した時にグラフの連結成分数が変化するかどうかを調べることより、パターンの切断箇所の候補を抽出する。
【００９８】
ここで、特徴点の接続関係を表すグラフを頂点隣接行列で表現することができる。そして、グラフの連結成分数の変化を頂点隣接行列を用いて調べることもできる。パターンの切断箇所の候補が抽出されると、これらの切断箇所の候補の位置でパターンを切断する。次に、文字認識を行うプログラムを起動し、切断された部分パターン及び部分パターを統合した統合パターンについて、文字認識を実行する。そして、相違度の最も小さいパターンの組み合わせをパターンの切断箇所に決定する。
【００９９】
【発明の効果】
以上説明したように、本発明によれば、パターンの特徴点の接続関係に基づいて、パターンの接触箇所を判別することにより、パターンが傾いている場合においても、パターンの特徴点の接続関係は変化しないため、パターンの接触箇所を効率よく見つけることが可能となり、文字領域の切り出し精度を向上させることが可能となる。
【０１００】
また、本発明の一態様によれば、パターンの端点、交点、分岐点または屈曲点を文字同士の接触点の候補とすることにより、文字同士の接触点を効率よく見つけることが可能となる。
【０１０１】
また、本発明の一態様によれば、パターンを切断した時のパターンの分離方向に基づいて、文字同士の接触点の候補を絞り込むことにより、文字の構成部分となる特徴点を文字同士の接触点の候補から除くことが可能となり、文字同士の接触点の検出を効率化することが可能となる。
【０１０２】
また、本発明の一態様によれば、パターンの接続関係をグラフで表現することにより、パターンの接続情報のみを残したまま、それ以外の画像情報を除去することが可能となり、パターンの接続関係を効率よく評価することが可能となる。
また、本発明の一態様によれば、パターンの接続関係を頂点隣接行列で表すことにより、グラフの連結成分数を効率よく求めることが可能となり、パターンを特徴点で切断した際に、パターンが分離するかどうかを効率よく調べることが可能となる。
【０１０３】
また、本発明の一態様によれば、グラフから辺を除去した時のグラフの連結成分数をカウントすることにより、パターンの特徴点でパターンが分離するかどうかを容易に判別することが可能となり、点接触の場合の接触位置を高速に検出することが可能となる。
【０１０４】
また、本発明の一態様によれば、パターンを接触方向に沿って探索した時に、急に細くなる箇所でパターンを切断することにより、点接触前のパターンの形状を保ちつつ、パターンを切断することが可能となる。
【０１０５】
また、本発明の一態様によれば、グラフの辺及びその辺の両端の特徴点の二重化を行った時のグラフの連結成分数をカウントすることにより、パターンの辺でパターンが分離するかどうかを容易に判別することが可能となり、辺接触の場合の接触位置を高速に検出することが可能となる。
【０１０６】
また、本発明の一態様によれば、パターンの辺を垂直方向に二等分した位置で、パターンを切断することにより、辺接触前のパターンの形状を保ちつつ、パターンを切断することが可能となる。
【０１０７】
また、本発明の一態様によれば、接触位置を示す候補点で切断したパターンの文字認識結果に基づいて、それらの候補点が接触点かどうかを判別することにより、１つの接触箇所に対して接触位置を示す候補点が複数検出された場合においても、接触位置でない候補点を接触点から除外することが可能となり、文字の接触箇所を精度よく見つけ出すことが可能となる。
【０１０８】
また、本発明の一態様によれば、相違度の小さい文字の切り出しに成功しても、それ以外の領域から１文字として切り出されたパターンの相違度が大きい場合には、その切り出し位置を文字同士の接触箇所でないと判断することにより、文字列のパターンから相違度の小さい文字の切り出し位置の候補が複数得られた場合においても、それらの候補を絞り込むことが可能となり、文字同士の接触箇所の検出精度を向上させることが可能となる。
【図面の簡単な説明】
【図１】本発明の一実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図２】本発明の一実施例に係わる文字認識装置の構成を示すブロック図である。
【図３】図２の接触候補箇所決定・切断部の処理を示すフローチャートである。
【図４】本発明の一実施例に係わる細線化パターンの具体例を示す図である。
【図５】次数２の頂点の決定方法を説明する図である。
【図６】（ａ）は、点接触したパターンの具体例を示す図、（ｂ）は、図６（ａ）のパターンをグラフ化した例を示す図、（ｃ）は、図６（ｂ）のグラフから辺を除去した場合にグラフの連結成分数が増加する例を示す図である。
【図７】（ａ）は、図６（ｂ）のグラフの頂点隣接行列を示す図、（ｂ）は、図６（ｃ）のグラフの頂点隣接行列を示す図である。
【図８】頂点隣接行列から接触点の候補を求める方法を示すフローチャートである。
【図９】（ａ）は、辺接触したパターンの具体例を示す図、（ｂ）は、図９（ａ）のパターンをグラフ化した例を示す図、（ｃ）は、図９（ｂ）のグラフの辺及びその辺の端点の二重化を行った場合にグラフの連結成分数が増加する例を示す図である。
【図１０】（ａ）は、図９（ｂ）のグラフの頂点隣接行列を示す図、（ｂ）は、図９（ｃ）のグラフの頂点隣接行列を示す図である。
【図１１】頂点隣接行列から辺接触の候補を求める方法を示すフローチャートである。
【図１２】点接触のパターンの切断方法を示す図である。
【図１３】辺接触のパターンの切断方法を示す図である。
【図１４】図１０（ａ）のパターンの切断例を示す図である。
【図１５】切断されたパターンの統合方法を示す図である。
【図１６】候補文字ラティス法による接触位置の決定方法を説明する図である。
【図１７】本発明の一実施例に係わるパターン抽出処理をソフトウエアを用いて実現した構成を示すブロック図である。
【図１８】従来の文字同士の接触位置の検出方法を示す図である。
【符号の説明】
１  特徴点検出手段
２  接続関係判別手段
３  接触箇所判別手段
１１  ＯＣＲ
１２  観測部
１３  文字列抽出部
１４  接触文字判定部
１５  接触候補箇所決定・切断部
１６  候補文字ラティス生成部
１７  認識辞書部
１８  言語処理部
１９  知識辞書部
６１  ＣＰＵ
６２  ＲＯＭ
６３  ＲＡＭ
６４  通信インターフェイス
６５  通信ネットワーク
６６  入出力インターフェイス
６７  ディスプレイ
６８  プリンタ
６９  メモリ
７０  スキャナ
７１  キーボード
７２  ポインティングデバイス
７３  ドライバ
７４  ハードディスク
７５  ＩＣメモリカード
７６  磁気テープ
７７  フロッピーディスク
７８  光ディスク
７９  バス
【図１】
0003798179.tif 000002
【図２】
0003798179.tif 000003
【図３】
0003798179.tif 000004
【図４】
0003798179.tif 000005
【図５】
0003798179.tif 000006
【図６】
0003798179.tif 000007
【図７】
0003798179.tif 000008
【図８】
0003798179.tif 000009
【図９】
0003798179.tif 000010
【図１０】
0003798179.tif 000011
【図１１】
0003798179.tif 000012
【図１２】
0003798179.tif 000013
【図１３】
0003798179.tif 000014
【図１４】
0003798179.tif 000015
【図１５】
0003798179.tif 000016
【図１６】
0003798179.tif 000017
【図１７】
0003798179.tif 000018
【図１８】
0003798179.tif 000019