(57)【特許請求の範囲】
【請求項１】
文字列画像の特徴量を前記文字列の配列方向の成分系列として抽出する特徴量抽出手段と、
カテゴリの特徴量を前記カテゴリの配列方向の成分系列として設定する特徴量設定手段と、
前記文字画像中の全ての成分に対して、前記カテゴリの成分系列の最後の成分を前記文字列画像の各成分と対応付け、前記対応付けに対し、前記カテゴリの残りの成分系列を前記文字列画像の成分と対応付けることにより、前記カテゴリの成分系列の最初の成分と対応する前記文字列画像の成分を探索する探索手段と、
前記成分系列の対応付けが行われた前記文字列画像と前記カテゴリとの間の相違度を算出する相違度算出手段と、
前記相違度に基づいて、前記文字列画像からの文字の切り出し位置を判別する判別手段と、
前記文字列画像の配列方向の全ての成分に対し、カテゴリの成分系列の最初の成分と対応する前記文字列画像の成分及びその時の相違度を組として、認識対象となる各カテゴリごとに登録する登録手段と、
前記文字列画像の切り出し位置に対応する成分で特定される相違度のうち、所定値以下の相違度を前記登録手段から検索する検索手段と、
前記検索手段で検索された相違度と組となる前記文字列画像の成分を前記登録手段から取得する取得手段と、
前記登録手段から取得された前記文字列画像の成分に基づいて、前記文字列画像の次の切り出し位置を算出する算出手段と、
前記文字列画像の切り出し位置と、前記算出手段により算出された前記文字列画像の次の切り出し位置とを結ぶパスを生成するパス生成手段と、
前記切り出し位置に対応する座標値、前記検索手段で検索された相違度及び前記相違度に対応するカテゴリを、前記パスの属性として付与する属性付与手段と、
前記文字列画像を前記パスで辿ることにより、前記パスの組み合わせを生成する組み合わせ生成手段と、
前記パスに付与された相違度の累積結果に基づいて、前記パスの組み合わせを評価する評価手段と、
前記評価結果に基づいて、前記パスの組み合わせの選別を行う選別手段と、
前記選別手段で選別されたパスに付与されている座標値を前記文字列画像の切断点として決定する切断点決定手段と、
を備えることを特徴とする文字切り出し装置。
【請求項２】
前記相違度は、前記カテゴリの成分系列の最初の成分から最後の成分までについての各成分間の距離の累積結果から求められ、
前記探索手段は、過去の成分の対応付けのうち、各成分間の距離の累積値の最も小さな対応付けに基づいて、現在の成分の対応付けを行う、
ことを特徴とする請求項１記載の文字切り出し装置。
【請求項３】
前記選別手段で選別されたパスに付与されているカテゴリを、前記切断点で切断されたパターンの認識結果とする認識結果出力手段をさらに備えることを特徴とする請求項１に記載の文字切り出し装置。
【請求項４】
文字切り出し装置を、
文字列画像の特徴量を前記文字列の配列方向の成分系列として抽出する特徴量抽出手段と、
カテゴリの特徴量を前記カテゴリの配列方向の成分系列として設定する特徴量設定手段と、
前記文字画像中の全ての成分に対して、前記カテゴリの成分系列の最後の成分を前記文字列画像の各成分と対応付け、前記対応付けに対し、前記カテゴリの残りの成分系列を前記文字列画像の成分と対応付けることにより、前記カテゴリの成分系列の最初の成分と対応する前記文字列画像の成分を探索する探索手段と、
前記成分系列の対応付けが行われた前記文字列画像と前記カテゴリとの間の相違度を算出する相違度算出手段と、
前記相違度に基づいて、前記文字列画像からの文字の切り出し位置を判別する判別手段と、
前記文字列画像の配列方向の全ての成分に対し、カテゴリの成分系列の最初の成分と対応する前記文字列画像の成分及びその時の相違度を組として、認識対象となる各カテゴリごとに登録する登録手段と、
前記文字列画像の切り出し位置に対応する成分で特定される相違度のうち、所定値以下の相違度を前記登録手段から検索する検索手段と、
前記検索手段で検索された相違度と組となる前記文字列画像の成分を前記登録手段から取得する取得手段と、
前記登録手段から取得された前記文字列画像の成分に基づいて、前記文字列画像の次の切り出し位置を算出する算出手段と、
前記文字列画像の切り出し位置と、前記算出手段により算出された前記文字列画像の次の切り出し位置とを結ぶパスを生成するパス生成手段と、
前記切り出し位置に対応する座標値、前記検索手段で検索された相違度及び前記相違度に対応するカテゴリを、前記パスの属性として付与する属性付与手段と、
前記文字列画像を前記パスで辿ることにより、前記パスの組み合わせを生成する組み合わせ生成手段と、
前記パスに付与された相違度の累積結果に基づいて、前記パスの組み合わせを評価する評価手段と、
前記評価結果に基づいて、前記パスの組み合わせの選別を行う選別手段と、
前記選別手段で選別されたパスに付与されている座標値を前記文字列画像の切断点として決定する切断点決定手段と、
として機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項５】
文字切り出し装置が、
文字列画像の特徴量を前記文字列の配列方向の成分系列として抽出する特徴量抽出ステップと、
カテゴリの特徴量を前記カテゴリの配列方向の成分系列として設定する特徴量設定ステップと、
前記文字画像中の全ての成分に対して、前記カテゴリの成分系列の最後の成分を前記文字列画像の各成分と対応付け、前記対応付けに対し、前記カテゴリの残りの成分系列を前記文字列画像の成分と対応付けることにより、前記カテゴリの成分系列の最初の成分と対応する前記文字列画像の成分を探索する探索ステップと、
前記成分系列の対応付けが行われた前記文字列画像と前記カテゴリとの間の相違度を算出する相違度算出ステップと、
前記相違度に基づいて、前記文字列画像からの文字の切り出し位置を判別する判別ステップと、
前記文字列画像の配列方向の全ての成分に対し、カテゴリの成分系列の最初の成分と対応する前記文字列画像の成分及びその時の相違度を組として、認識対象となる各カテゴリごとに登録する登録ステップと、
前記文字列画像の切り出し位置に対応する成分で特定される相違度のうち、所定値以下の相違度を前記登録ステップから検索する検索ステップと、
前記検索ステップで検索された相違度と組となる前記文字列画像の成分を前記登録ステップから取得する取得ステップと、
前記登録ステップから取得された前記文字列画像の成分に基づいて、前記文字列画像の次の切り出し位置を算出する算出ステップと、
前記文字列画像の切り出し位置と、前記算出ステップにより算出された前記文字列画像の次の切り出し位置とを結ぶパスを生成するパス生成ステップと、
前記切り出し位置に対応する座標値、前記検索ステップで検索された相違度及び前記相違度に対応するカテゴリを、前記パスの属性として付与する属性付与ステップと、
前記文字列画像を前記パスで辿ることにより、前記パスの組み合わせを生成する組み合わせ生成ステップと、
前記パスに付与された相違度の累積結果に基づいて、前記パスの組み合わせを評価する評価ステップと、
前記評価結果に基づいて、前記パスの組み合わせの選別を行う選別ステップと、
前記選別ステップで選別されたパスに付与されている座標値を前記文字列画像の切断点として決定する切断点決定ステップと、
を有することを特徴とする文字切り出し方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパターン切り出し装置及びパターン認識装置に関し、特に、１文字領域を文字列画像から切り出す場合に適用して好適なものである。
【０００２】
【従来の技術】
従来の文字認識では、文字認識を行う前に、文字列画像から１文字に相当するパターンを切り出す必要がある。この切り出し処理では、主に、ラベリング処理、重なり統合処理、上下統合処理（横書きの場合）または左右統合処理（縦書きの場合）の３つの処理が行われる。ただし、これらの処理を用いただけでは、２つ以上の文字が接触している場合、あるいは、２つ以上の文字が入り組んで並置している場合、それらの文字を正しく切り出すことができない。このため、従来の切り出し処理では、このような接触文字を正しく切り出すために、以下の方法が用いられていた。
【０００３】
（１）文字列方向への黒画素射影ヒストグラム（周辺分布）を作成し、その極小値を与える点を切断点とする。
（２）文字列の上部及び下部について輪郭追跡を行い、その極小値を与える点を切断点とする。
【０００４】
【発明が解決しようとする課題】
しかしながら、文字の形状あるいは文字間の接触部の形状によっては、接触点の周辺分布あるいは輪郭が必ずしも極小になっているとは限らない。このため、従来の方法では、文字同士の接触点で正しく切断されない場合があるという問題があった。
【０００５】
また、画像の状態が悪く、パターンの凹凸が頻繁に発生している場合は、切断点が多数生成されるため、仮説検証を行っても、過分割の悪影響を避けることが難しいという問題があった。
【０００６】
そこで、本発明の目的は、文字接触パターンの切り出し精度を向上させることが可能なパターン切り出し装置及びパターン認識装置を提供することである。
【０００７】
【課題を解決するための手段】
上述した課題を解決するために、本発明によれば、カテゴリの特徴量と画像の特徴量とを比較し、カテゴリの特徴量と対応する部分を画像から切り出すようにしている。
【０００８】
このことにより、カテゴリの特徴量と対応しているパターンの存在位置でそのパターンを切り出すことが可能となり、パターン同士の接触位置が黒画素射影ヒストグラムの極小点に対応しない場合においても、パターン同士の切れ目の位置でパターンを切り出すことが可能となる。また、カテゴリの特徴量に対応する部分を画像から一体的に切り出すことが可能となり、切り出し対象のパターンに凹凸が頻繁に発生している場合においても、１つのパターンがそのパターンの極小点で多数の領域に分断されることを防止することが可能となり、切り出し精度を向上させることが可能となる。
【０００９】
また、本発明の一態様によれば、カテゴリの配列方向の成分系列として設定された特徴量の最初の成分及び最後の成分を、文字列画像の配列方向に独立に移動させながら、カテゴリの特徴量と文字列画像の特徴量との対応付けを行うようにしている。
【００１０】
このことにより、文字列画像に歪みや変形が発生した場合においても、カテゴリの特徴量と文字列画像の文字パターンの特徴量との照合精度を維持することが可能となり、様々の文字列画像が入力された場合においても、カテゴリの特徴量との照合がとれなくなることを防止することが可能となる。
【００１１】
また、本発明の一態様によれば、文字列画像の配列方向の成分に対応するカテゴリの最初の点を登録しておき、カテゴリの最初の点に対応する文字列画像の成分から次の切り出し位置を求めるようにしている。
【００１２】
このことにより、カテゴリに対応する別個の領域が文字列画像内で連なるようにして、別個の文字領域を文字列画像から抽出することが可能となり、文字列画像からの複数の文字領域の抽出を効率よく行うことが可能となる。
【００１３】
また、本発明の一態様によれば、画像からの切り出し領域が複数得られた場合、認識対象となるいずれのカテゴリにも対応しない領域が画像内に存在しないようにして、切り出し領域の組み合わせを生成するようにしている。
【００１４】
このことにより、切り出し対象となる画像内の全ての領域を認識対象となるいずれかのカテゴリに対応させることが可能となり、カテゴリのいずれにもに対応しないパターンが余る場合には、その切り出し位置を棄却することが可能となり、画像からの切り出し領域が複数得られた場合においても、その中から最適な切り出し位置を求めることが可能となる。例えば、文字列だけからなる画像には、文字以外のパターンは存在しない。このため、文字列だけからなる画像から、いずれの文字にも対応しないパターンが１つでも切り出された場合、その切り出し位置は間違っていると判断することができる。従って、切り出し対象となる文字列からの全ての切り出し結果が、いずれかの文字カテゴリに対応するように切り出し位置を決定することにより、間違った位置で切り出しが行われることを防止して、切り出し精度を向上させることが可能となる。
【００１５】
また、本発明の一態様によれば、カテゴリの切り出し用の特徴量と、カテゴリの認識用の特徴量とを別個に設定し、カテゴリの切り出し用の特徴量を用いて切り出されたパターンを、カテゴリの認識用の特徴量を用いて認識するようにしている。
【００１６】
このことにより、あるカテゴリに対応する領域として切り出されたパターンが、そのカテゴリに一致するかどうかを検証することが可能となり、文字の切り出し精度を向上させることが可能となる。
【００１７】
また、本発明の一態様によれば、カテゴリの切り出し用の特徴量を用いてパターンが切り出された場合、そのカテゴリをそのままそのパターンの認識結果として出力するようにしている。
【００１８】
このことにより、画像からの切り出し処理を行うだけで、パターンの認識結果を得ることが可能となり、パターンの切り出し処理とは別個にパターンの認識処理を行う必要がなくなることから、パターンの認識結果を得るまでにかかる時間を短縮することが可能となる。
【００１９】
【発明の実施の形態】
以下、本発明の一実施例に係わるパターン切り出し装置及びパターン認識方法について図面を参照しながら説明する。
【００２０】
図１は、本発明の一実施例に係わるパターン切り出し装置の構成を示すブロック図である。図１において、特徴量抽出手段１は、画像の特徴量を抽出する。特徴量設定手段２は、カテゴリの特徴量を設定する。特徴量比較手段３は、カテゴリの特徴量と画像の特徴量とを、処理対象となる画像全体について比較する。切り出し手段４は、特徴量比較手段３による比較結果に基づいて、カテゴリの特徴量に対応する部分を画像から切り出す。ここで、カテゴリの特徴量及び画像の特徴量とは、元のパターンを再現可能な特徴量またはその特徴量の一部のことを意味する。例えば、カテゴリの特徴量及び画像の特徴量として、ｎ次までのペリフェラル特徴を用いることができる。
【００２１】
このことにより、カテゴリの特徴量に対応するパターンのみを画像から一体的に切り出すことが可能となり、文字以外のパターンが切り出されたり、１つの文字が多数の点で分断された状態で切り出されたりすることを防止することが可能となり、文字の切り出し精度を向上させることが可能となる。また、文字の特徴量に対応する部分が画像内に存在する場合は、文字同士が接触している場合においても、文字に対応する部分の位置を特定することが可能となり、文字同士の接触位置が黒画素射影ヒストグラムの極小点に対応しない場合においても、文字の境界の位置で文字を切り出すことが可能となる。
【００２２】
また、カテゴリの特徴量及び画像の特徴量を文字列の配列方向に対して設定する。そして、カテゴリの特徴量の配列の最後の部分及び最初の部分を文字列の配列方向に対して独立に走査し、その走査により得られるカテゴリの特徴量と画像の特徴量との対応のうち、最適な対応を与える位置を求める。例えば、カテゴリの特徴量の配列の最後の部分の各対応に対し、カテゴリの特徴量と画像の特徴量との最適の対応が得られるように、カテゴリの特徴量の配列の最初の部分の対応を求める。
【００２３】
このことにより、カテゴリの特徴量に対応する部分を入力画像から抽出する際に、カテゴリを伸縮させながらカテゴリを入力画像内で走査させることが可能となり、入力画像に手書き文字が存在する場合などにおいても、カテゴリの特徴量に対応する部分を入力画像から精度良く抽出することが可能となる。
【００２４】
図２は、本発明の一実施例に係わるパターン切り出し方法を説明する図である。なお、以下の実施例では、カテゴリ“５”の特徴量を入力画像の特徴量と照合する場合を例にとって説明するが、他のカテゴリについても同様である。図２（ａ）において、カテゴリ“５”の特徴量がｙ軸方向に設定され、カテゴリ“５”の左端Ｌｋの特徴量がｙ＝０、カテゴリ“５”の右端Ｒｋの特徴量がｙ＝ｙ１に対応しているものとする。一方、切り出し対象の画像として、図２（ｂ）の接触文字「２５７」が入力されたものとする。接触文字「２５７」が入力されると、文字列方向に対してｘ軸を設定し、接触文字「２５７」の左端ＬＩの特徴量をｘ＝０、接触文字「２５７」の右端ＲＩの特徴量をｘ＝ｘ１に対応させる。そして、カテゴリ“５”の右端Ｒｋ及び左端Ｌｋをｘ軸の０〜ｘ１の範囲内で別々に走査し、その走査により得られるカテゴリ“５”の特徴量と接触文字「２５７」の特徴量との対応のうち、最適な対応を与える位置を求める。この結果、カテゴリ“５”の右端Ｒｋをｘ軸のｘＲに対応させ、カテゴリ“５”の左端Ｌｋをｘ軸のｘＬに対応させた場合に、カテゴリ“５”の特徴量と接触文字「２５７」の特徴量との最適な対応関係が得られるものとすると、座標値ｘＬ及びｘＲを接触文字「２５７」の切り出し位置の候補とする。ここで、カテゴリ“５”の横方向の画素数がｄｙ、接触文字「２５７」のカテゴリ“５”に対応する部分の画素数がｄｙ’であるものとすると、カテゴリ“５”の右端Ｒｋ及び左端Ｌｋをｘ軸の０〜ｘ１の範囲内で別々に走査することにより、カテゴリ“５”の横方向の画素数ｄｙと接触文字「２５７」のカテゴリ“５”に対応する部分の画素数ｄｙ’とが異なる場合においても、カテゴリ“５”に対応する部分を接触文字「２５７」から精度良く切り出すことが可能となる。
【００２５】
なお、特徴量の照合は、連続ＤＰ（ｄｙｎａｍｉｃ  ｐｒｏｇｒａｍｍｉｎｇ：動的計画法）という名の非線形伸縮マッチングを用いることができる。なお、連続ＤＰについては、例えば、（岡、“連続ＤＰを用いた連続単語認識”、日本音響学会音声研究会、Ｓ７８−２０，ｐｐ．１４５−１５２、１９７８）に記載されている。
【００２６】
このように、画像中のあるカテゴリに相当する部分（そのカテゴリの文字として切り出されるべき部分）の特徴量が、そのカテゴリの特徴量に類似していることに着目する。すなわち、画像に対し、ある特徴量を定義し、入力された画像全体に対し、各カテゴリの特徴量と類似するところを探索する。このために、まず、各カテゴリの特徴量を辞書に登録しておく。そして、入力画像全体に対し、特徴量を求め、各カテゴリの特徴量との照合を行う。この結果、各カテゴリに関し、入力画像とどの程度一致したか、また最も一致したのは入力画像のどこからどこまでか、等の情報が得られる。具体的には、各カテゴリについて、各座標における相違度と、その相違度を与える座標間の対応関係がわかる。特に、各座標を終点としたときの相違度と、その対応の開始点が明らかになる。この相違度を、画像をその開始点から終点までの部分で切り出し、その部分をそのカテゴリと仮定した時のコストと考えれば、切り出し方の各々について、その妥当性が比較できる。そして、最も妥当性の高い切り出し方の組み合わせを探索することにより、切り出し位置とその認識結果を確定することができる。
【００２７】
図３は、本発明の第１実施例に係わるパターン認識方法を示すフローチャートである。この第１実施例では、カテゴリの特徴量との照合により画像内の切り出し位置が得られた場合、そのカテゴリをそのままその切り出し位置のパターンの認識結果とするものである。図３において、まず、入力画像に対し（ステップＳ１）、正規化処理を施す（ステップＳ２）。この正規化処理では、画像を縦の長さがある一定の長さになるように拡縮し、さらに、それに対しスムージングを施す。次に、正規化後の入力画像の特徴量を計算する（ステップＳ３）。特徴量は、正規化画像の横画素数と同じ個数の整数（またはベクトル）の系列からなり、各整数は、例えば、０から１００までの値をとることができる。
【００２８】
次に、辞書に登録されている各カテゴリの特徴量を用い、画像全体に対し、連続ＤＰによる照合を行う（ステップＳ４）。この結果、各カテゴリと各座標に関する最適対応の相違度と、その最適対応の開始点の座標情報が得られる。次に、これらの情報を基に、切断点の算出を行う（ステップＳ５）。具体的には、各最適対応を、その開始点と終点を結び、かつ、その相違度を重みとするパスとする。そして、それらのパスの系列で、最もコストのかからないものを探索する。この結果得られるパスの系列、すなわち、それらのパスの始点及び終点の系列を切断点として出力する。この場合、それらのパスを与えるカテゴリが認識結果となる。
【００２９】
図４は、本発明の第２実施例に係わるパターン認識方法を示すフローチャートである。この第２実施例では、切り出し用のカテゴリの特徴量とは別個に、認識用のカテゴリの特徴量を辞書に格納しておく。そして、切り出し用のカテゴリの特徴量との照合により画像内の切り出し位置が得られた場合、認識用のカテゴリの特徴量を用いて、その切り出し位置のパターンの認識を行う。図４において、図３のステップＳ１〜Ｓ５と同様の処理を行うことにより、切断点の算出を行う（ステップＳ１１〜Ｓ１５）。次に、切断点で画像を切り出し（ステップＳ１６）、切り出されたパターンの１文字認識を行い（ステップＳ１７）、その認識結果に基づいて、カテゴリの確定を行う（ステップＳ１８）。さらに、パスの組み合わせをコストの低い順に複数出力し、同じく、１文字認識させ、認識結果から最も妥当のものを認識結果とするようにしてもよい。
【００３０】
上述した実施例において、特徴量には、横書きの場合、上下２方向からのｎ次までのペリフェラル特徴を用いることができる。また、ｎ次までのペリフェラル特徴のうちの一部の特徴を用いることもできる。以下の例では、上下２方向からの１次、及び２次のペリフェラル特徴を用いた場合について説明する。
【００３１】
図５は、本発明の一実施例に係わるカテゴリのペリフェラル特徴の算出方法を示す図である。なお、図５の例では、カテゴリ“５”を例にとって説明するが、他のカテゴリについても同様の方法で求めることができる。図５において、まず、カテゴリ“５”の外接矩形の下辺のことを下限Ｄｋと呼ぶ。そして、この下限Ｄｋに対応してｙ軸を設定し、ｙ軸と垂直にｚ軸を設定する。また、カテゴリ“５”を構成する横方向の各画素をｙ座標に対応させ、カテゴリ“５”を構成する縦方向の各画素をｚ座標に対応させる。この下限Ｄｋの座標ｙから垂直に走査線を延ばした時、カテゴリ“５”の黒画素に最初にぶつかるまでの距離をｚ１とする。カテゴリ“５”の外接矩形の高さをｄｚとすれば、カテゴリ“５”の座標ｙにおける下限Ｄｋからの第１次ペリフェラル特徴は、以下の式で求めることができる。
【００３２】
（ｚ１／ｄｚ×１００）の整数部分
同様に、次に白画素から黒画素に変化する点までの距離をｚ２とすると、カテゴリ“５”の座標ｙにおける下限Ｄｋからの第２次ペリフェラル特徴は、以下の式で求めることができる。
【００３３】
（ｚ２／ｄｚ×１００）の整数部分
また、カテゴリ“５”の外接矩形の上辺のことを上限と呼ぶことにすると、カテゴリ“５”の座標ｙにおける上限からの第１次、第２次ペリフェラル特徴も同様にして求めることができる。
【００３４】
カテゴリ“５”の座標ｙにおける上限及び下限の１次及び２次ペリフェラル特徴が得られると、これらの４つの値を１組としてｙ軸上の各点に対応させる。ここで、カテゴリ“５”の左端の画素をｙ＝０に対応させ、カテゴリ“５”の右端の画素をｙ＝ｙ１に対応させる。そして、ｙ＝０〜ｙ１について、上限及び下限の１次及び２次のペリフェラル特徴の４つの値の組をｙ軸方向にそのまま並べて得られる成分系列を、カテゴリ“５”のペリフェラル特徴とすることができる。
【００３５】
図６は、本発明の一実施例に係わるカテゴリ“５”のペリフェラル特徴の算出結果を示す図である。図６（ａ）は、上限Ｕｋからの第１次ペリフェラル特徴を示し、図６（ｂ）は、上限Ｕｋからの第２次ペリフェラル特徴を示し、図６（ｃ）は、下限Ｄｋからの第１次ペリフェラル特徴を示し、図６（ｄ）は、下限Ｄｋからの第２次ペリフェラル特徴を示している。
【００３６】
なお、学習サンプルを用いてカテゴリの特徴量を求める場合、各カテゴリについて横画素数を予め決めておく。次に、各学習サンプルに対し、上述した方法で特徴量を算出する。そして、特徴量の４つの整数の組の個数が、各カテゴリに対し決められた横画素数と一致するように、一様に拡縮し、それぞれの座標で整数値の平均化を行う。
【００３７】
入力画像についても、入力画像の上限及び下限を設定し、上限及び下限からの１次及び２次ペリフェラル特徴を求めることにより、入力画像のペリフェラル特徴を求めることができる。
【００３８】
なお、縦書きの場合、左右２方向からのｎ次までのペリフェラル特徴を用いるようにする。例えば、画像の右限及び左限からの１次及び２次ペリフェラル特徴を用いることにより、カテゴリと入力画像との照合を行うことができる。
【００３９】
図７は、本発明の一実施例に係わる連続ＤＰによる相違度の算出方法を説明する図である。図７において、入力画像として、接触文字「２５７」からなるパターンが入力されたものとすると、辞書に登録されている各カテゴリの特徴量を、接触文字「２５７」からなるパターン全体の特徴量と照合する。
【００４０】
以下、辞書に登録されている各カテゴリの特徴量のうち、カテゴリ“５”の特徴量と接触文字「２５７」からなるパターン全体の特徴量とを照合する場合を例にとって説明する。まず、カテゴリ“５”の横方向の画素数ｄｙ＝３０であり、カテゴリ“５”のペリフェラル特徴Ｆｋが４つの整数の組の３０個の系列として辞書に登録されているものとすると、これら３０個の４つの整数の組（ｋ０、ｋ０’、ｋ０’’、ｋ０’’’）、（ｋ１、ｋ１’、ｋ１’’、ｋ１’’’）・・・（ｋ２９、ｋ２９’、ｋ２９’’、ｋ２９’’’）をｙ軸のｙ＝０からｙ＝ｙ１＝２９までの座標に対応させる。ここで、ｋ０、ｋ１・・・ｋ２９は、カテゴリ“５”の上限からの第１次ペリフェラル特徴（図６（ａ）に対応）、ｋ０’、ｋ１’・・・ｋ２９’は、カテゴリ“５”の上限からの第２次ペリフェラル特徴（図６（ｂ）に対応）、ｋ０’’、ｋ１’’・・・ｋ２９’’は、カテゴリ“５”の下限からの第１次ペリフェラル特徴（図６（ｃ）に対応）、ｋ０’’’、ｋ１’’’・・・ｋ２９’’’は、カテゴリ“５”の下限からの第２次ペリフェラル特徴（図６（ｄ）に対応）である。
【００４１】
また、接触文字「２５７」からなるパターンの横方向の画素数ｄｘ＝８６であるものとすると、接触文字「２５７」からなるパターンの左端ＬＩをｘ軸のｘ＝０に対応させ、接触文字「２５７」からなるパターンの右端ＲＩをｘ軸のｘ＝８５に対応させる。そして、接触文字「２５７」からなるパターンのペリフェラル特徴ＦＩを４つの整数の組の８６個の系列として抽出し、これら８６個の４つの整数の組（Ｉ０、Ｉ０’、Ｉ０’’、Ｉ０’’’）、（Ｉ１、Ｉ１’、Ｉ１’’、Ｉ１’’’）・・・（Ｉ８５、Ｉ８５’、Ｉ８５’’、Ｉ８５’’’）をｘ軸のｘ＝０からｘ＝ｘ１＝８５までの座標に対応させる。ここで、Ｉ０、Ｉ１・・・Ｉ８５は、接触文字「２５７」からなるパターンの上限からの第１次ペリフェラル特徴、Ｉ０’、Ｉ１’・・・Ｉ８５’は、接触文字「２５７」からなるパターンの上限からの第２次ペリフェラル特徴、Ｉ０’’、Ｉ１’’・・・Ｉ８５’’は、接触文字「２５７」からなるパターンの下限からの第１次ペリフェラル特徴、Ｉ０’’’、Ｉ１’’’・・・Ｉ８５’’’は、接触文字「２５７」からなるパターンの下限からの第２次ペリフェラル特徴である。
【００４２】
次に、ｘ軸上での接触文字「２５７」からなるパターンのペリフェラル特徴ＦＩ及びｙ軸上でのカテゴリ“５”のペリフェラル特徴Ｆｋが求まると、カテゴリ“５”のペリフェラル特徴Ｆｋの３０個の成分を接触文字「２５７」のペリフェラル特徴ＦＩの成分に対応付ける。そして、それらの対応付けのうち、最適な対応付けを求め、その最適な対応付けでのｘ軸上での成分の位置を接触文字「２５７」の切り出し位置の候補とすることができる。ここで、各対応付けに対する各成分間の距離の累積値を求め、その累積値を重みで正規化する。そして、正規化後の値の最も小さい対応付けを、最適な対応付けとすることができる。
【００４３】
以下、入力パターンの成分とカテゴリの成分との間の対応付けを経路と呼ぶことにすると、現在の点（ｘ、ｙ）に至るまでの過去の経路のうち、相違度の最も小さくなる経路を選択することにより、現在の点（ｘ、ｙ）に至るまでの最適な経路を求めることができる。ここで、カテゴリと入力パターンとの対応づけについて、各成分系列の順序の逆転はなく、系列をなす成分の採用に飛びは生じないものとすると、現在の点（ｘ、ｙ）に至る経路は、図８に示すように、３つの経路に限られる。
【００４４】
従って、現在の点（ｘ、ｙ）に至るまでの最適な経路を求める場合、過去の点に至るまでの最適な経路を求めておき、過去の点から現在の点（ｘ、ｙ）に至るまでの３つの経路のうち、相違度の最も小さくなる経路を選択することにより、現在の点（ｘ、ｙ）に至るまでの最適な経路を求めることができる。
【００４５】
具体的には、０≦ｘ≦ｘ１、０≦ｙ≦ｙ１の範囲内について、点（ｘ、ｙ）に至るまでの最適な経路に対する相違度の累積値ｑ（ｘ，ｙ）は、式（１）〜（８）の累積値の漸化式より求めることができる。
累積値の漸化式
０≦ｘ≦ｘ１、０≦ｙ≦ｙ１
ｑ（−１、ｙ）＝ｑ（０、ｙ）＝Ｍ（Ｍは、十分大きな値）    ・・・（１）
ｑ（ｘ、０）＝２ｄ（ｘ、０）                              ・・・（２）
ｑ（ｘ、１）＝ｍｉｎ
｛ｑ（ｘ−２、０）＋２ｄ（ｘ−１、０）＋ｄ（ｘ、１）    ・・・（３）
ｑ（ｘ−１、０）＋２ｄ（ｘ、０）   ・・・（４）
ｑ（ｘ、０）＋ｄ（ｘ、１）｝       ・・・（５）
ｑ（ｘ、ｙ）＝ｍｉｎ
｛ｑ（ｘ−２、ｙ−１）＋２ｄ（ｘ−１、ｙ）＋ｄ（ｘ、ｙ）・・（６）
ｑ（ｘ−１、ｙ−１）＋２ｄ（ｘ、ｙ） ・・・（７）
ｑ（ｘ−１、ｙ−２）＋２ｄ（ｘ、ｙ−１）＋ｄ（ｘ、ｙ）｝・（８）
ここで、距離ｄ（ｘ，ｙ）は、例えば、以下のシティブロック距離で定義することができる。
【００４６】
ｄ（ｘ，ｙ）＝Σn=1,2,｜ＩＰｎ，ｕｐ（ｘ）−Ｋｎ，ｕｐ（ｙ）｜
＋｜ＩＰｎ，ｄｏｗｎ（ｘ）−Ｋｎ，ｄｏｗｎ（ｙ）｜  ・・・（１７）
ただし、ＩＰｎ，ｕｐ（ｘ）は、点ｘにおける入力画像の上限からのｎ次ペリフェラル特徴、
ＩＰｎ，ｄｏｗｎ（ｘ）は、点ｘにおける入力画像の下限からのｎ次ペリフェラル特徴、
Ｋｎ，ｕｐ（ｙ）は、点ｙにおけるカテゴリの上限からのｎ次ペリフェラル特徴、
Ｋｎ，ｄｏｗｎ（ｙ）は、点ｙにおけるカテゴリの下限からのｎ次ペリフェラル特徴である。
【００４７】
なお、距離ｄ（ｘ，ｙ）は、シティブロック距離以外にも、ユークリッド距離などで定義してもよい。
ここで、図８において、点Ｐ１に至る相違度の累積値をｑ（ｘ−２，ｙ−１）、点Ｐ２に至る相違度の累積値をｑ（ｘ−１，ｙ−２）、点Ｐ３に至る相違度の累積値をｑ（ｘ−１，ｙ−１）、点Ｐ４における入力画像とカテゴリとの間の距離をｄ（ｘ−１，ｙ）、点Ｐ５における入力画像とカテゴリとの間の距離をｄ（ｘ，ｙ−１）、点Ｐ６における入力画像とカテゴリとの間の距離をｄ（ｘ，ｙ）とすると、（６）式は、図８のＰ１→Ｐ４→Ｐ６の経路で、点Ｐ６に至る相違度の累積値ｑ（ｘ，ｙ）を求めることに相当し、（７）式は、図８のＰ３→Ｐ６の経路で、点Ｐ６に至る相違度の累積値ｑ（ｘ，ｙ）を求めることに相当し、（８）式は、図８のＰ２→Ｐ５→Ｐ６の経路で、点Ｐ６に至る相違度の累積値ｑ（ｘ，ｙ）を求めることに相当している。
【００４８】
また、累積値ｑ（ｘ，ｙ）に対応する重みｇ（ｘ、ｙ）は、式（９）〜（１６）の重みの漸化式により求めることができる。
重みの漸化式
0004053188.tif 000002
ここで、重みの漸化式（９）〜（１６）式は、累積値の漸化式（１）〜（８）式にそれぞれ対応している。
【００４９】
（１）〜（１６）式により、相違度の累積値ｑ（ｘ，ｙ）及び重みｇ（ｘ、ｙ）が求まると、点（ｘ，ｙ）に至るまでの最適な経路に対する入力画像とカテゴリとの相違度Ｄ（ｘ，ｙ）は、（１７）式により求めることができる。
【００５０】
Ｄ（ｘ，ｙ）＝ｑ（ｘ，ｙ）／ｇ（ｘ，ｙ）              ・・・（１８）
以上の式を用いることにより、図７の各点（ｘ，ｙ）について、点（ｘ，ｙ）に至るまでの最適な経路に対する入力画像とカテゴリとの相違度Ｄ（ｘ，ｙ）を求めることができる。ここで、現在の点（ｘ，ｙ）の相違度Ｄ（ｘ，ｙ）を求めるためには、過去の点の相違度が求まっている必要がある。このため、まず、ｘ＝−１及びｘ＝０の点に対応する相違度として、（１）式によりＭの値を設定する。そして、Ｄ１→Ｄ２→・・・→Ｄ６→・・・→Ｄ７→Ｄ８→・・・→Ｄ１２→・・・→Ｄ３７→Ｄ３８→・・・→Ｄ４２という順番で相違度Ｄ（ｘ，ｙ）を求めていく。
【００５１】
また、例えば、現在の点（ｘ，ｙ）の相違度Ｄ２８を求める場合、現在の点（ｘ，ｙ）に至る経路はＲ１〜Ｒ３の３つの経路がある。ここで、（６）式の累積値ｑ（ｘ、ｙ）及び（１４）式の重みｇ（ｘ、ｙ）を（１８）式に代入することにより、経路Ｒ１から現在の点（ｘ，ｙ）に至る時の相違度Ｄ（ｘ，ｙ）を求めることができる。また、（７）式の累積値ｑ（ｘ、ｙ）及び（１５）式の重みｇ（ｘ、ｙ）を（１８）式に代入することにより、経路Ｒ２から現在の点（ｘ，ｙ）に至る時の相違度Ｄ（ｘ，ｙ）を求めることができる。また、（８）式の累積値ｑ（ｘ、ｙ）及び（１６）式の重みｇ（ｘ、ｙ）を（１８）式に代入することにより、経路Ｒ３から現在の点（ｘ，ｙ）に至った時の相違度Ｄ（ｘ，ｙ）を求めることができる。このため、これらの３つの経路Ｒ１〜Ｒ３のうち、相違度が最小となる経路を選択することにより、現在の点（ｘ，ｙ）の相違度Ｄ２８を求めることができる。また、現在の点（ｘ，ｙ）に至る３つの経路Ｒ１〜Ｒ３のうちのいずれか１つが選択されると、その選択された経路を登録しておく。
【００５２】
図９は、本発明の一実施例に係わる連続ＤＰによる相違度の算出方法を示すフローチャートである。図９において、まず、初期化処理を行う（ステップＳ２１）。この初期化処理では、０≦ｙ≦ｙ１の範囲について、ｑ（−１、ｙ）＝ｑ（０、ｙ）＝Mに設定するとともに、ｇ（−１、ｙ）＝ｇ（０、ｙ）＝０に設定する。次に、Ｘ＝１に設定し（ステップＳ２２）、ｑ（ｘ、０）＝２ｄ（ｘ、０）、ｇ（ｘ、０）＝２に設定する（ステップＳ２３）。次に、ｙ＝１について、式（３）〜（５）より累積値ｑ（ｘ，ｙ）を求めるとともに、式（１１）〜（１３）よりその累積値ｑ（ｘ，ｙ）に対応する重みｇ（ｘ、ｙ）を求める。また、２≦ｙ≦ｙ１の範囲について、式（６）〜（８）より累積値ｑ（ｘ，ｙ）を求めるとともに、式（１４）〜（１６）よりその累積値ｑ（ｘ，ｙ）に対応する重みｇ（ｘ、ｙ）を求める（ステップＳ２４）。以上の処理を、ｘを１づつ増やしながら（ステップＳ２５）、ｘ＝ｘ１になるまで繰り返す（ステップＳ２６）。
【００５３】
以上の処理により、０≦ｘ≦ｘ１、０≦ｙ≦ｙ１の範囲について、点（ｘ，ｙ）に至るまでの最適な経路及びその時の相違度を求めることができる。点（ｘ，ｙ）に至るまでの最適な経路が求まると、その経路を逆に辿っていくことにより、点（ｘ，ｙ）に対応する始点（ｘ０，ｙ０）を求めることができる。この対応を、
ｘ０＝Ｓｔｘ（ｘ，ｙ）
ｙ０＝Ｓｔｙ（ｘ，ｙ）
と表現する。
【００５４】
また、図１０に示すように、カテゴリ“５”の右端Ｒｋに対応する点（ｘ、ｙ１）に至る最適な経路を逆に探索することにより、カテゴリ“５”の左端Ｌｋに対応する点（ｓｔ、０）を探索する。そして、カテゴリ“５”の左端Ｌｋに対応する点（ｓｔ、０）が求まると、その時のｘ軸上の値ｓｔを、座標ｘにおけるカテゴリ“５”の開始点とする。
【００５５】
以上より、カテゴリＫと座標ｘに対する照合結果は、相違度をＳｃ（ｘ，Ｋ）、開始点をＳｔ（ｘ，Ｋ）として、
Ｓｃ（ｘ，Ｋ）＝Ｄ（ｘ，ｄｙ−１）
Ｓｔ（ｘ，Ｋ）＝Ｓｔｘ（ｘ，ｄｙ−１）
とすることができる。
【００５６】
以上の処理により、カテゴリ“５”の右端Ｒｋを接触文字「２５７」の横方向の点ｘに対応させた時に、相違度の最も低くなるようにして、カテゴリ“５”の左端Ｌｋが対応する接触文字「２５７」の横方向の点ｓｔ及びその時の相違度を求めることができる。
【００５７】
以上の処理を、接触文字「２５７」からなるパターンに対し、認識対象となる全てのカテゴリＫについて行う。例えば、認識対象となるカテゴリＫが“０”〜“９”までとすると、カテゴリ“０”〜“９”の全てについて、以上の処理を行う。そして、０≦ｘ≦ｘ１の範囲について、開始点Ｓｔ（ｘ，Ｋ）及びその時の相違度Ｓｃ（ｘ，Ｋ）を各カテゴリＫごとに求める。
【００５８】
図１１は、本発明の一実施例に係わる開始点及びその時の相違度を各カテゴリごとに算出した結果の一部を示す図である。ここで、図１１の例では、４７≦ｘ≦７２の範囲についてのみ示し、それ以外のｘの範囲について省略している。また、相違度ｓｃがあるしきい値以上の場合、ｘｘで表している。図１１において、例えば、ｘ＝６０の点についてみると、カテゴリ“０”、“１”、“４”の場合は、開始点ｓｔをｘ軸上のどの点に設定しても、相違度ｓｃがあるしきい値より小さくならないことを示している。一方、カテゴリ“２”の場合は、開始点ｓｔ＝４０に設定することにより（この場合、カテゴリ“２”の左端をｘ＝４０の点に設定することに相当する）、カテゴリ“２”の右端をｘ＝６０の点に設定した時の相違度ｓｃが最も小さくなり、その時の相違度ｓｃ＝６７であることを示している。また、例えば、カテゴリ“５”の場合は、開始点ｓｔ＝３３に設定することにより（この場合、カテゴリ“５”の左端をｘ＝３３の点に設定することに相当する）、カテゴリ“５”の右端をｘ＝６０の点に設定した時の相違度ｓｃが最も小さくなり、その時の相違度ｓｃ＝３０であることを示している。
【００５９】
図１２は、図１１の算出結果から切り出し位置の経路を探索する方法を示す図である。図１２において、認識対象となるカテゴリＫが“０”〜“９”であり、切り出し対象となる接触文字「２５７」のパターンの横方向の画素数ｗ１＝８６であるものとすると、全てのカテゴリ“０”〜“９”に対し、０≦ｘ≦ｘ１＝８５の範囲について、開始点ｓｔ及びその時の相違度ｓｃが求められる。ここで、例えば、接触文字「２５７」のパターンの右端のｘ＝８５の点に着目する（以下、この点のことを初期基点という）。そして、ｘ＝８５の点に対応する相違度ｓｃのうち、しきい値ＴＨ以下の相違度ｓｃがあるかどうかを調べる。ここで、例えば、しきい値ＴＨ＝３５に設定されているものとすると、カテゴリ“７”の相違度ｓｃが２５であるので、しきい値ＴＨ＝３５以下の相違度ｓｃのカテゴリ“７”が見つかる。ｘ＝８５の点においてカテゴリ“７”が見つかると、ｘ＝８５の点でのカテゴリ“７”に対応する開始点ｓｔを調べる。この結果、ｘ＝８５の点でのカテゴリ“７”の開始点ｓｔは６２と判るので、接触文字「２５７」のパターンの次の切り出し位置をこの開始点ｓｔ＝６２から求める。ここで、開始点ｓｔ＝６２は、カテゴリ“７”に対応するパターンの右端の切り出し位置をｘ＝８５に設定した場合、カテゴリ“７”に対応するパターンの左端の切り出し位置をｘ＝６２に設定すると、相違度ｓｃが最も小さくなることを示している。また、その時の相違度ｓｃが２５であることも判る。従って、接触文字「２５７」のパターンの次の切り出し位置を、ｘ＝ｓｔ＝６２から所定値ｔｈだけ溯った範囲とする。例えば、所定値ｔｈ＝２であるものとすると、次の切り出し位置の探索範囲をｘ＝６０〜６２の間に設定し、ｘ＝６０〜６２の間の点に対応する相違度ｓｃのうち、しきい値ＴＨ以下の相違度ｓｃがあるかどうかを調べる。ここで、ｘ＝６０の点においてカテゴリ“５”の相違度ｓｃが３０であるので、しきい値ＴＨ＝３５以下の相違度ｓｃのカテゴリ“５”が見つかる。ｘ＝６０の点でのカテゴリ“５”が見つかると、その座標ｘ＝６０を接触文字「２５７」のパターンの次の切り出し位置とする（以下、この点のことを基点という）。また、最初の切り出し位置ｘ＝８５の点と次の切り出し位置ｘ＝６０の点とを結ぶパスＰ１を生成する。
【００６０】
次に、パスＰ１が生成されると、ｘ＝６０の点でのカテゴリ“５”に対応する開始点ｓｔを調べる。この結果、ｘ＝６０の点でのカテゴリ“５”の開始点ｓｔは３３と判るので、接触文字「２５７」のパターンの次の切り出し位置をこの開始点ｓｔ＝３３から求める。この結果、次の切り出し位置の探索範囲はｘ＝３１〜３３となり、ｘ＝３１〜３３の間の点に対応する相違度ｓｃのうち、しきい値ＴＨ以下の相違度ｓｃがあるかどうかを調べる。ここで、ｘ＝３１の点においてカテゴリ“２”の相違度ｓｃが３５であるので、しきい値ＴＨ＝３５以下の相違度ｓｃのカテゴリ“２”が見つかる。ｘ＝３１の点でのカテゴリ“２”が見つかると、その座標ｘ＝３１を接触文字「２５７」のパターンの次の切り出し位置とする。また、切り出し位置ｘ＝６０の点とその次の切り出し位置ｘ＝３１の点とを結ぶパスＰ２を生成する。
【００６１】
次に、パスＰ２が生成されると、ｘ＝３１の点でのカテゴリ“２”に対応する開始点ｓｔを調べる。この結果、ｘ＝３１の点でのカテゴリ“２”の開始点ｓｔは７と判るので、接触文字「２５７」のパターンの次の切り出し位置をこの開始点ｓｔ＝７から求める。ここで、ｘ＝７以前の範囲にはカテゴリ“０”〜“９”に対応するパターンが存在しないものとすると、接触文字「２５７」のパターンの切り出し位置をｘ＝７の点とする（以下、この点のことを原始点という）。そして、切り出し位置ｘ＝３１の点とその次の切り出し位置ｘ＝７の点とを結ぶパスＰ３を生成し、切り出し処理を終了する。
【００６２】
以上の処理により、接触文字「２５７」のパターンを「２」と「５」との境界の位置及び「５」と「７」との境界の位置で切断することができる。なお、接触文字「２５７」のパターンに対し、パスＰ１〜Ｐ３が求まると、パスＰ１〜Ｐ３に対して重みを与えることにより、Ｐ１→Ｐ２→Ｐ３という経路を辿って切り出しを行った場合の切り出し位置の評価を行うことができる。ここで、パスＰ１〜Ｐ３の重みとして、各パスＰ１〜Ｐ３に対応して切り出されるパターンとそのパターンに対応するカテゴリとの間の相違度ｓｃを用いることができる。例えば、パスＰ１の重みは、ｘ＝８５の点でのカテゴリ“７”の相違度ｓｃから２５と求め、パスＰ２の重みは、ｘ＝６０の点でのカテゴリ“５”の相違度ｓｃから３０と求め、パスＰ３の重みは、ｘ＝３１の点でのカテゴリ“２”の相違度ｓｃから３５と求めることができる。パスＰ１〜Ｐ３の重みが求まると、パスＰ１〜Ｐ３の重みの合計値ｑ＝２５＋３０＋３５＝９０をパスＰ１〜Ｐ３の本数ｂ＝３で割った値ｖ＝９０／３＝３０を切り出し位置の評価値とすることができる。
【００６３】
図１３は、本発明の一実施例に係わる切り出し位置の算出方法を示すフローチャートである。図１３において、まず、初期基点の選出処理を行う（ステップＳ３１）。この初期基点の選出処理では、入力パターンの右端の座標ｘ＝ｄｘ−１に対応して登録されている相違度Ｓｃ（ｄｘ−１、Ｋ）に着目する。カテゴリＫを相違度Ｓｃ（ｄｘ−１、Ｋ）の小さい順番で並べ、カテゴリＫの集合の中から、相違度Ｓｃ（ｄｘ−１、Ｋ）の小さい上位ｍ個を選出する。そして、上位ｍ個のカテゴリが、Ｋ１，Ｋ２，．．．，Ｋｍであるとすれば、初期基点を、（ｄｘ−１，Ｋ１），（ｄｘ−１，Ｋ２），．．．，（ｄｘ−１，Ｋｍ）とする。なお、ｄｘは入力パターンの横方向の画素数である。
【００６４】
次に、パスの生成処理を行う（ステップＳ３２）。このパスの生成処理では、各初期基点に関し、入力画像と各カテゴリの対応を、その開始点と終点を結ぶパスと考え、その対応の相違度をパスの重みとする。さらに、そのパスにカテゴリの値を付加する。
【００６５】
図１４は、本発明の一実施例に係わるパスの生成処理を示すフローチャートである。図１４において、まず、座標ｘ、カテゴリＫに対応する初期基点（ｘ，Ｋ）に対し（ステップＳ４１）、相違度ｓｃ＝Ｓｃ（ｘ，Ｋ）、開始点ｓｔ＝Ｓｔ（ｘ，Ｋ）を調べる（ステップＳ４２）。次に、ｘ＝ｓｔについて、基点を探索する（ステップＳ４３）。ここで、基点とは、ｓｔ−ｔｈ≦ｘ≦ｓｔの範囲で、全てのカテゴリＫｉに関し、（ｘ，Ｋｉ）の中でＳｃ（ｘ，Ｋｉ）＜ＴＨであり、Ｓｔ（ｘ，Ｋｉ）の値が同じものの中で、Ｓｃ（ｘ，Ｋｉ）が最小の点である。そして、もし、基点の個数が０であれば（ステップＳ４４）、開始点ｓｔ、終点ｘ、重みｓｃ、カテゴリＫなるパスを登録し（ステップＳ４５）、処理を終了（リターン）する。一方、基点の個数がａで、基点が（ｘｉ，ｋｉ）（ｉ＝１，・・・，ａ）ならば（ステップＳ４４）、開始点ｘｉ、終点ｘ、重みｓｃ、カテゴリＫなるパスを登録する（ステップＳ４６）。そして、ステップＳ４１に戻り、各基点に関し、同様に処理する。
【００６６】
図１５は、本発明の一実施例に係わる基点の探索処理を示すフローチャートである。図１５において、まず、ＢＰｃｈｅｃｋ，ＢＰｓｃｏｒｅ，ＢＰｅｎｄ、及びａの初期化を行う（ステップＳ５１）。ここで、ＢＰｃｈｅｃｋ，ＢＰｓｃｏｒｅ，ＢＰｅｎｄはいずれもｄｘ個の配列である。ＢＰｃｈｅｃｋは、座標ｘがチェックされたか否かを示すもので、初期値は全て０である。ＢＰｓｃｏｒｅには、相違度ｓｃの値が入り、初期値は全て−１である。ＢＰｅｎｄには、座標値が入り、初期値は全てｓｔである。整数ａは、発見された基点の個数を表し、初期値は０である。
【００６７】
次に、Ｋ＝０に設定し（ステップＳ５２）、Ｋ＜ｍａｘの場合（ステップＳ５３）、ｘ＝ｓｔに設定する（ステップＳ５４）。ここで、ｍａｘは、認識対象となるカテゴリＫの個数である。次に、ｘ≧ｓｔ−ｔｈ、かつ、ｘ≧０でない場合（ステップＳ５５）、Ｋの値を１だけ増やし（ステップＳ６２）、ステップＳ５３に戻る。一方、ｘ≧ｓｔ−ｔｈ、かつ、ｘ≧０の場合（ステップＳ５５）、ｓｃ（ｘ）＝Ｓｃ（ｘ、Ｋ）、ｓｔ（ｘ）＝Ｓｔ（ｘ、Ｋ）とし、ｓｃ（ｘ）＜ＴＨかどうかを判定する（ステップＳ５６）。そして、ｓｃ（ｘ）＜ＴＨでない場合、ｘを１だけ減らし（ステップＳ６１）、ステップＳ５５に戻る。一方、ｓｃ（ｘ）＜ＴＨの場合、ＢＰｃｈｅｃｋ（ｓｔ（ｘ））＞０かどうかを判定し（ステップＳ５７）、ＢＰｃｈｅｃｋ（ｓｔ（ｘ））＞０でない場合、ＢＰｃｈｅｃｋ（ｓｔ（ｘ））＝１とし、ａの値を１だけ増やし（ステップＳ５８）、ステップＳ６０に進む。一方、ＢＰｃｈｅｃｋ（ｓｔ（ｘ））＞０の場合、ｓｃ（ｘ）＜ＢＰｓｃｏｒｅ（ｓｔ（ｘ））、あるいはｓｃ（ｘ）＝ＢＰｓｃｏｒｅ（ｓｔ（ｘ））かつｘ＜ＢＰｅｎｄ（ｓｔ（ｘ））を満たすかどうかを判定し（ステップＳ５９）、ステップＳ５９の条件を満たさない場合、ステップＳ６１に進む。一方、ステップＳ５９の条件を満たす場合、ＢＰｓｃｏｒｅ（ｓｔ（ｘ））＝ｓｃ（ｘ）、ＢＰｅｎｄ（ｓｔ（ｘ））＝ｘとする（ステップＳ６０）。以上の処理を、ｘ≧ｓｔ−ｔｈ、かつ、ｘ≧０の条件を満たす座標ｘについて、認識対象となる全てのカテゴリＫについて行う。
【００６８】
図１６は、本発明の一実施例に係わるパスの生成例を示す図である。図１６において、例えば、ｘ１＝ｄｘ−１の点で４つの初期基点Ｂ１〜Ｂ４が選出されたものとする。そして、初期基点Ｂ１に対し、基点Ｂ５、Ｂ１１が探索された結果、Ｐ１９→Ｐ２０の２つのパスからなる経路が得られる。また、初期基点Ｂ２に対し、基点Ｂ６、Ｂ９、Ｂ１３が探索された結果、Ｐ１７→Ｐ１８→Ｐ１３の３つのパスからなる経路が得られる。また、初期基点Ｂ３に対し、基点Ｂ７、Ｂ９、Ｂ１３が探索された結果、Ｐ１１→Ｐ１２→Ｐ１３の３つのパスからなる経路が得られる。また、初期基点Ｂ４に対し、基点Ｂ８、Ｂ１０、Ｂ１２が探索された結果、Ｐ１４→Ｐ１５→Ｐ１６の３つのパスからなる経路が得られる。
【００６９】
ここで、各パスＰ１１〜Ｐ２０には、開始点、終点、重み及びカテゴリからなる属性が付与されている。例えば、開始点ｘｆ、終点ｘ１、初期基点Ｂ１に対応するカテゴリの相違度ｓｃ、初期基点Ｂ１に対応するカテゴリが、パスＰ１１の属性として付与される。また、開始点ｘｄ、終点ｘｆ、基点Ｂ７に対応するカテゴリの相違度ｓｃ、基点Ｂ７に対応するカテゴリが、パスＰ１２の属性として付与される。
【００７０】
次に、最適経路の探索を行う（ステップＳ３３）。この最適経路の探索では、以上の処理で生成されたパスの集合の中で、最適の経路を探索する。まず、各座標ｘについて、その座標ｘが開始点になっているパスＰｉを列挙する。この時、これらのパスＰｉに関し、開始点、終点、重み、カテゴリを対応させる関数をそれぞれ、ｓｔ（Ｐｉ），ｅｄ（Ｐｉ）、ｓｃ（Ｐｉ），ｃａ（Ｐｉ）とする。また、それまでの座標ｔ（＞ｘ）における重みの累積値をｑ（ｔ）、また、それまで何本のパスを経たものかを表す数値をｂ（ｔ）とすると、
（ｑ（ｅｄ（Ｐｉ））＋ｓｃ（Ｐｉ））／（ｂ（ｅｄ（Ｐｉ）＋１）・・・（１９）
の最小値を与えるパスＰｉを選び、そのパスＰｉをＰｉ＝ａｒｇ（ｘ）とする。そして、
ｑ（ｘ）＝ｑ（ｅｄ（Ｐｉ＝ａｒｇ（ｘ））＋ｓｃ（Ｐｉ＝ａｒｇ（ｘ））
・・・（２０）
ｂ（ｘ）＝ｂ（ｅｄ（Ｐｉ＝ａｒｇ（ｘ））＋１          ・・・（２１）
とする。
【００７１】
全ての座標に関し、上記の計算を行った後、各座標のうち、原始点になっているものについて、以下の評価値ｖ（ｘ）の計算を行う。
ｖ（ｘ）＝ｑ（ｘ）／ｂ（ｘ）                          ・・・（２２）
ここで、原始点とは、少なくともその座標ｘを開始点とするパスが１個以上存在し、かつ、その座標ｘを終点とするパスが存在しないものをいう。この評価値ｖ（ｘ）の値で原始点を順序づけ、最も小さい評価値ｖ（ｘ）を与える座標をｘ＝Ｏｒｉｇｉｎとする。Ｏｒｉｇｉｎが得られると、Ｏｒｉｇｉｎから逆にパスを辿ることで、最短経路を与えるパスの系列を得ることができる。そして、それらのパスに付与されている終点及びカテゴリをそれぞれ切断点及び認識結果とすることができる。
【００７２】
例えば、図１６において、基点Ｂ９には、Ｐ１１→Ｐ１２という経路とＰ１７→Ｐ１８という経路との２通りの経路で到達できる。この場合、ｔ＝ｘｄまでについて、（１９）式の値を計算し、その値の小さい方を選択する。ここで、Ｐ１１→Ｐ１２という経路が選択されたものとすると、原始点Ｂ１１に至る経路として、Ｐ１９→Ｐ２０という経路が得られ、原始点Ｂ１２に至る経路として、Ｐ１４→Ｐ１５→Ｐ１６という経路が得られ、原始点Ｂ１３に至る経路として、Ｐ１１→Ｐ１２→Ｐ１３という経路が得られる。原始点Ｂ１１〜Ｂ１３得られると、（２２）式の評価値ｖ（ｘ）が最も小さいものを選択する。ここで、原始点Ｂ１２が選択されたものとすると、原始点Ｂ１２に対応する座標ｘａをＯｒｉｇｉｎとする。そして、ＯｒｉｇｉｎからパスＰ１４〜Ｐ１６を逆に辿ることで、切断点ｘｃ、ｘｅを決定することができる。また、パスＰ１４〜Ｐ１６に付与されているカテゴリを各切り出し位置における認識結果とすることができる。
【００７３】
以上説明したように、本実施例によれば、画像特徴からでは切れ目がはっきりしない文字の接触パターンに対しても、画像全体と各カテゴリとを照合し、得られる照合結果においてカテゴリ及び切り出し位置に関する整合をとって、最も照合する切り出し位置とカテゴリの組み合わせを得ることができるので、文字を正しく切り出し、かつ認識できる。また、カテゴリとの照合による切り出し処理と１文字認識処理とを併用することで、より高精度に認識できる。
【００７４】
図１７は、本発明の一実施例に係わるパターン切り出し及びパターン認識をソフトウェアにより実現する構成を示すブロック図である。図１７おいて、１１は全体的な処理を行う中央演算処理ユニット（ＣＰＵ）、１２はリードオンリメモリ（ＲＯＭ）、１３はランダムアクセスメモリ（ＲＡＭ）、１４は通信インターフェイス、１５は通信ネットワーク、１６は入出力インターフェイス、１７は文書データなどを表示するディスプレイ、１８は文書データなどを印刷するプリンタ、１９はスキャナ２０により読み取られた文書データなどを一時的に格納するメモリ、２０は入力画像などを読み取るスキャナ、２１はキーボード、２２はマウスなどのポインティングデバイス、２３は記憶媒体を駆動するドライバ、２４はハードディスク、２５はＩＣメモリカード、２６は磁気テープ、２７はフロッピーディスク、２８はＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの光ディスク、２９はバスである。
【００７５】
パターン切り出しやパターン認識を行うプログラム、カテゴリの特徴量などは、ハードディスク２４、ＩＣメモリカード２５、磁気テープ２６、フロッピーディスク２７、光ディスク２８などの記憶媒体に格納される。そして、パターン切り出しやパターン認識を行うプログラム及びカテゴリの特徴量を、これらの記憶媒体からＲＡＭ１３に読み出すことにより、パターン切り出しやパターン認識を行うことができる。また、パターン切り出しやパターン認識を行うプログラムをＲＯＭ１２に格納しておくこともできる。
【００７６】
さらに、パターン切り出しやパターン認識を行うプログラム、カテゴリの特徴量や入力画像の特徴量などを、通信インターフェイス１４を介して通信ネットワーク１５から取り出すこともできる。通信インターフェイス１４に接続される通信ネットワーク１５として、例えば、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、アナログ電話網、デジタル電話網（ＩＳＤＮ：Ｉｎｔｅｇｒａｌ  Ｓｅｒｖｉｃｅ  Ｄｉｇｉｔａｌ  Ｎｅｔｗｏｒｋ）、ＰＨＳ（パーソナルハンディシステム）や衛星通信などの無線通信網を用いることができる。
【００７７】
ＣＰＵ１１は、パターン切り出しを行うプログラムまたはパターン認識を行うプログラムが起動されると、ハードディスク２４などの記憶媒体、または通信ネットワーク１５などからカテゴリの特徴量を取得する。また、スキャナ２０により読み取られた入力画像、または通信ネットワーク１５から送られた入力画像などから、入力画像の特徴量を抽出する。そして、カテゴリの特徴量に対し、入力画像の特徴量を対応させる部分を変えながら、カテゴリの特徴量と入力画像の特徴量との照合を行う。その照合の結果、カテゴリの特徴量に対応する部分が入力画像から得られると、カテゴリの特徴量に対応する部分を入力画像の切り出し位置とする。入力画像の切り出し位置が得られると、照合に用いたカテゴリを入力画像から切り出されたパターンの認識結果とすることができる。また、認識結果を得るために、入力画像から切り出されたパターンの認識を行うようにしてもよい。認識結果が得られると、その認識結果をディスプレイ１７やプリンタ１８に出力したり、通信ネットワーク１５を介して送信したりすることができる。
【００７８】
【発明の効果】
以上説明したように、本発明によれば、カテゴリの特徴量と画像の特徴量の比較結果に基づいてパターンの切り出しを行うことにより、パターンの輪郭や凹凸だけでなく、カテゴリの全体的な形状や構造を考慮して、画像からの切り出し処理を行うことが可能となり、パターンの切り出し精度を向上させることが可能となる。また、カテゴリの特徴量に対応するパターンを画像から一体的に切り出すことが可能となり、１つのカテゴリに対応するパターンが多数の点で切断されることを防止することが可能となる。
【００７９】
また、本発明の一態様によれば、カテゴリの両端を文字列画像の両端に固定することなく、カテゴリの両端を文字列画像の様々の点に対応させて、カテゴリと文字列画像との照合を行うことにより、文字列画像に歪みや変形が発生した場合においても、カテゴリの特徴量と文字列画像の文字パターンの特徴量との照合精度を維持することが可能となる。
【００８０】
また、本発明の一態様によれば、カテゴリの一端を文字列画像の成分の座標に対応させた時のカテゴリの他端が対応する文字列画像の成分の座標をテーブルに登録しておくことにより、文字列画像の切り出し位置が求まると、その文字列画像の次の切り出し位置をそのテーブルから容易に求めることが可能となり、文字列画像からの別個の文字領域の抽出を効率よく行うことが可能となる。
【００８１】
また、本発明の一態様によれば、認識対象となるいずれのカテゴリにも対応しない領域が切り出されたかどうかを調べることにより、その切り出し位置が正しい切り出し位置かどうかを判別することが可能となり、画像からの切り出し領域が複数得られた場合においても、その中から最適な切り出し位置を求めることが可能となる。
【００８２】
また、本発明の一態様によれば、カテゴリの切り出し用の特徴量と、カテゴリの認識用の特徴量とを別個に設定することにより、カテゴリの切り出し用の特徴量を用いてパターンの切り出しを行うとともに、カテゴリの認識用の特徴量を用いて切り出されたパターンの認識を行うことが可能となる。このため、パターンの認識結果が正しいかどうかを異なる特徴量を用いて検証することが可能となる。また、切り出し処理を行う場合には、切り出しに適した特徴量を用いることが可能となるとともに、認識処理を行う場合には、認識に適した特徴量を用いることが可能となり、切り出し精度及び認識精度を向上させることが可能となる。
【００８３】
また、本発明の一態様によれば、カテゴリの切り出し用の特徴量を用いてパターンが切り出された場合、そのカテゴリをそのままそのパターンの認識結果とすることにより、画像からの切り出し処理を行うだけで、パターンの認識結果を得ることが可能となり、パターンの認識結果を得るまでにかかる時間を短縮することが可能となる。
【図面の簡単な説明】
【図１】本発明の一実施例に係わるパターン切り出し装置の構成を示すブロック図である。
【図２】本発明の一実施例に係わるパターン切り出し方法を説明する図である。
【図３】本発明の第１実施例に係わるパターン認識方法を示すフローチャートである。
【図４】本発明の第２実施例に係わるパターン認識方法を示すフローチャートである。
【図５】本発明の一実施例に係わるカテゴリのペリフェラル特徴の算出方法を示す図である。
【図６】本発明の一実施例に係わるカテゴリのペリフェラル特徴の算出結果を示す図である。
【図７】本発明の一実施例に係わる連続ＤＰによる相違度の算出方法を説明する図である。
【図８】本発明の一実施例に係わる連続ＤＰにおける現在の点への到達経路を示す図である。
【図９】本発明の一実施例に係わる連続ＤＰによる相違度の算出方法を示すフローチャートである。
【図１０】本発明の一実施例に係わる開始点の探索方法を説明する図である。
【図１１】本発明の一実施例に係わる開始点及びその時の相違度を各カテゴリごとに算出した結果の一部を示す図である。
【図１２】図１１の算出結果から切り出し位置の経路を探索する方法を示す図である。
【図１３】本発明の一実施例に係わる切り出し位置の算出方法を示すフローチャートである。
【図１４】本発明の一実施例に係わるパスの生成処理を示すフローチャートである。
【図１５】本発明の一実施例に係わる基点の探索処理を示すフローチャートである。
【図１６】本発明の一実施例に係わるパスの生成例を示す図である。
【図１７】本発明の一実施例に係わるパターン切り出し及びパターン認識をソフトウェアにより実現する構成を示すブロック図である。
【符号の説明】
１  特徴量抽出手段
２  特徴量設定手段
３  特徴量比較手段
４  切り出し手段
１１  ＣＰＵ
１２  ＲＯＭ
１３  ＲＡＭ
１４  通信インターフェイス
１５  通信ネットワーク
１６  入出力インターフェイス
１７  ディスプレイ
１８  プリンタ
１９  メモリ
２０  スキャナ
２１  キーボード
２２  ポインティングデバイス
２３  ドライバ
２４  ハードディスク
２５  ＩＣメモリカード
２６  磁気テープ
２７  フロッピーディスク
２８  光ディスク
２９  バス
【図１】
0004053188.tif 000003
【図２】
0004053188.tif 000004
【図３】
0004053188.tif 000005
【図４】
0004053188.tif 000006
【図５】
0004053188.tif 000007
【図６】
0004053188.tif 000008
【図７】
0004053188.tif 000009
【図８】
0004053188.tif 000010
【図９】
0004053188.tif 000011
【図１０】
0004053188.tif 000012
【図１１】
0004053188.tif 000013
【図１２】
0004053188.tif 000014
【図１３】
0004053188.tif 000015
【図１４】
0004053188.tif 000016
【図１５】
0004053188.tif 000017
【図１６】
0004053188.tif 000018
【図１７】
0004053188.tif 000019