(57)【特許請求の範囲】
【請求項１】
画像から文字画像を切り出す位置を抽出する切出位置抽出手段と、
前記切出位置抽出手段によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する文字候補抽出手段と、
前記文字候補抽出手段によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、
前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、
前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段
を具備し、
前記限定手段は、前記予め定められた文字列パターンに合致するリンクに対応する文字列の画像としての長さが最も長いリンクを選択する
ことを特徴とする画像処理装置。
【請求項２】
前記限定手段によって限定されたリンクによって接続されたノードの文字候補間の関係による文字列らしさを表す値に基づいて、リンク値を生成するリンク値生成手段と、
前記リンク値生成手段によって生成されたリンク値に基づいて、前記ネットワーク生成手段によって生成されたネットワーク内のパスを選択するパス選択手段
を具備し、
前記出力手段は、前記パス選択手段によって選択されたパス内の文字候補列を文字認識結果として出力する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記リンク値生成手段は、前記リンクを構成しているノードに対する文字らしさを表す値に基づいて、前記リンク値を生成する
ことを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記切出位置抽出手段は、複数の切り出し位置を抽出し、
前記ネットワーク生成手段は、前記切出位置抽出手段によって抽出された複数の切り出し位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成する
ことを特徴とする請求項２又は３に記載の画像処理装置。
【請求項５】
前記限定手段は、最初のリンクから前記文字列パターンに合致していない場合、該合致していないリンクの次のリンクから該文字列パターンに合致するリンクに限定する
ことを特徴とする請求項１から４のいずれか一項に記載の画像処理装置。
【請求項６】
前記限定手段は、前記文字列パターンに合致するリンクがない場合は、該文字列パターン内の一部分の文字列パターンに合致するリンクに限定する
ことを特徴とする請求項１から５のいずれか一項に記載の画像処理装置。
【請求項７】
コンピュータを、
画像から文字画像を切り出す位置を抽出する切出位置抽出手段と、
前記切出位置抽出手段によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する文字候補抽出手段と、
前記文字候補抽出手段によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、
前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、
前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段
として機能させ、
前記限定手段は、前記予め定められた文字列パターンに合致するリンクに対応する文字列の画像としての長さが最も長いリンクを選択する
ことを特徴とする画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
文字認識結果を修正する技術がある。
これに関連する技術として、例えば、特許文献１では、書式制御情報の字種の指定に正規表現を使用することにより詳細な指定を可能にして、認識率を向上させることを目的とし、用紙に記録された文字等を読み取るために参照される書式制御情報を記憶するためのものであって、書式制御情報中の文字種を指定する情報が正規表現で表されているＦＣ部と、ＦＣ部に記憶された書式制御情報中の正規表現を解析する正規表現解析部と、正規表現解析部による解析結果に基づいて認識辞書中の使用する辞書を選択する字種制御部と、字種制御部によって選択された辞書を用いて用紙に記録された文字等のパターンと照合し読み取り結果を求める照合部を備えていることが開示されている。
【０００３】
また、例えば、特許文献２では、文字認識結果の修正に必要な修正規則の機能拡張や保守が容易で、修正誤りを起こすことがない文字認識結果の修正方式を提供することを課題とし、入力文字列に対する文字認識結果である候補文字列を第１位から第ｎ位まで配列して候補文字マトリックスを形成し、このマトリックスを正規表現マッチング部に渡し、マッチング部は、種々の文字列記述形式に適合した種々の修正規則を蓄積した修正規則ファイルをプログラム外に有しており、入力されたマトリックスに適合可能な修正規則をファイルから選択し、そして、選択した修正規則に最も適合する候補文字列をマトリックス内の文字を選んで作成し、続いて、選択された修正規則に従って、文字列置き換え部が、候補文字列内の文字列をより正しい文字列に置換し、次に、文字置き換え部が、文字列置換された候補文字列内の個々の文字をより正しい文字に置換することが開示されている。
【０００４】
画像から文字を切り出す技術がある。
これに関連する技術として、例えば、特許文献３では、文書に記入された文字列から文字パターンを切り出す文字パターン切り出し装置に関するものであって、用紙などに記入された文字列から１文字ずつ文字パターンを切り出す文字パターン切り出し装置において、用紙上の文字列を光学的に走査し光電変換する走査手段と、光電変換された上記文字列のパターンを記憶する文字列パターン記憶手段と、上記文字列の方向と直交する方向に上記文字列パターンを走査して求めた周辺分布値の連続性に基づいて文字列パターンを分割し、分割して得た基本パターンの左右端と上下端との座標より基本パターン領域を決める基本パターン領域検出手段と、単独の基本パターン領域の文字形状評価値と連続する複数個の基本パターン領域を結合した結合パターン領域の文字形状評価値とを上記基本パターン領域の左右端と上下端の座標から各々算出する文字形状評価値算出手段と、読み取り対象文字の基準パターンを格納した文字認識辞書記憶手段と、単独の基本パターンに対する文字認識評価値と連続する複数個の基本パターンを結合した結合パターンに対する文字認識評価値とを上記文字認識辞書記憶手段に記憶した基準パターンとの整合により求める文字認識評価値算出手段と、上記文字形状評価値算出手段で算出した文字形状評価値と上記文字認識評価値算出手段で算出した文字認識評価値とを加え合わせることにより、すべての基本パターンと結合パターンとに対応する文字評価値を算出する評価値加算手段と、上記基本パターン領域の位置情報に基づいて切り出し候補位置のあらゆる可能な組み合せを求め、各々の切り出し候補位置の組み合せについて、切り出し候補位置で切り出された基本パターンと結合パターンとに対応する上記評価値加算手段で求めた文字評価値に基づいて切り出し評価値を求め、この切り出し評価値に基づいて最適な文字切り出し位置の組み合せを決定する文字切り出し手段と、上記文字切り出し手段の結果に基づいて上記文字列パターン記憶手段に格納した１行の文字列パターンから１文字ずつ文字パターンを切り出して出力する出力手段とを具備することを特徴とする文字パターン切り出し装置が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０６−０３６０６９号公報
【特許文献２】特開平０９−１３８８３６号公報
【特許文献３】特開昭６２−１９０５７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、画像から文字を認識する場合にあって、本構成を有していない場合に比較して、精度が高い文字認識結果を出力するようにした画像処理装置及び画像処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００７】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の発明は、画像から文字画像を切り出す位置を抽出する切出位置抽出手段と、前記切出位置抽出手段によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する文字候補抽出手段と、前記文字候補抽出手段によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段を具備し、前記限定手段は、前記予め定められた文字列パターンに合致するリンクに対応する文字列の画像としての長さが最も長いリンクを選択することを特徴とする画像処理装置である。
【０００８】
請求項２の発明は、前記限定手段によって限定されたリンクによって接続されたノードの文字候補間の関係による文字列らしさを表す値に基づいて、リンク値を生成するリンク値生成手段と、前記リンク値生成手段によって生成されたリンク値に基づいて、前記ネットワーク生成手段によって生成されたネットワーク内のパスを選択するパス選択手段を具備し、前記出力手段は、前記パス選択手段によって選択されたパス内の文字候補列を文字認識結果として出力することを特徴とする請求項１に記載の画像処理装置である。
【０００９】
請求項３の発明は、前記リンク値生成手段は、前記リンクを構成しているノードに対する文字らしさを表す値に基づいて、前記リンク値を生成することを特徴とする請求項２に記載の画像処理装置である。
【００１０】
請求項４の発明は、前記切出位置抽出手段は、複数の切り出し位置を抽出し、前記ネットワーク生成手段は、前記切出位置抽出手段によって抽出された複数の切り出し位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成することを特徴とする請求項２又は３に記載の画像処理装置である。
【００１１】
請求項５の発明は、前記限定手段は、最初のリンクから前記文字列パターンに合致していない場合、該合致していないリンクの次のリンクから該文字列パターンに合致するリンクに限定することを特徴とする請求項１から４のいずれか一項に記載の画像処理装置である。
【００１２】
請求項６の発明は、前記限定手段は、前記文字列パターンに合致するリンクがない場合は、該文字列パターン内の一部分の文字列パターンに合致するリンクに限定することを特徴とする請求項１から５のいずれか一項に記載の画像処理装置である。
【００１３】
請求項７の発明は、コンピュータを、画像から文字画像を切り出す位置を抽出する切出位置抽出手段と、前記切出位置抽出手段によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する文字候補抽出手段と、前記文字候補抽出手段によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するネットワーク生成手段と、前記ネットワーク生成手段によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する限定手段と、前記限定手段によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する出力手段として機能させ、前記限定手段は、前記予め定められた文字列パターンに合致するリンクに対応する文字列の画像としての長さが最も長いリンクを選択することを特徴とする画像処理プログラムである。
【発明の効果】
【００１４】
請求項１の画像処理装置によれば、画像から文字を認識する場合にあって、本構成を有していない場合に比較して、精度が高い文字認識結果を出力することができる。
【００１５】
請求項２の画像処理装置によれば、各文字画像の１つだけの文字認識結果によって認識文字列を決定してしまうことを防止することができる。
【００１６】
請求項３の画像処理装置によれば、文字列らしさを表す値と文字らしさを表す値を用いてリンク値を生成することができる。
【００１７】
請求項４の画像処理装置によれば、複数の切り出し位置に対しても文字認識結果を出力することができる。
【００１８】
請求項５の画像処理装置によれば、最初に誤った文字認識結果がある場合であっても、文字列パターンに合致する文字認識結果を出力することができる。
【００１９】
請求項６の画像処理装置によれば、文字列パターン内の一部分の文字列パターンに合致する文字認識結果を出力することができる。
【００２０】
請求項７の画像処理プログラムによれば、画像から文字を認識する場合にあって、本構成を有していない場合に比較して、精度が高い文字認識結果を出力することができる。
【図面の簡単な説明】
【００２１】
【図１】本実施の形態の構成例についての概念的なモジュール構成図である。
【図２】対象とする帳票の例を示す説明図である。
【図３】正規表現表記規則の例を示す説明図である。
【図４】文字位置と文字候補の関係例を示す説明図である。
【図５】文字位置と文字候補の関係例を示す説明図である。
【図６】本実施の形態による処理例を示すフローチャートである。
【図７】記号例を示す説明図である。
【図８】記号例を示す説明図である。
【図９】記号例を示す説明図である。
【図１０】記号例を示す説明図である。
【図１１】記号例を示す説明図である。
【図１２】文字切り出し位置が複数ある場合の処理例を示す説明図である。
【図１３】記号例を示す説明図である。
【図１４】文字切り出し位置が複数ある場合の処理例を示す説明図である。
【図１５】パス限定処理モジュール内のモジュール構成例を示す説明図である。
【図１６】パス限定処理モジュールによる処理例を示すフローチャートである。
【図１７】文字位置と文字候補の関係例を示す説明図である。
【図１８】出力決定処理モジュール内のモジュール構成例を示す説明図である。
【図１９】リンク値生成モジュール内のモジュール構成例を示す説明図である。
【図２０】パス選択モジュール内のモジュール構成例を示す説明図である。
【図２１】出力決定処理モジュールによる処理例を示すフローチャートである。
【図２２】重み付けの例を示す説明図である。
【図２３】重み決定モジュール内のモジュール構成例を示す説明図である。
【図２４】重み付けの例を示す説明図である。
【図２５】重み付けの例を示す説明図である。
【図２６】重み付けの例を示す説明図である。
【図２７】重み決定モジュール内のモジュール構成例を示す説明図である。
【図２８】本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【図２９】文字列画像の例を示す説明図である。
【図３０】文字境界候補の例を示す説明図である。
【図３１】外接矩形の例を示す説明図である。
【図３２】文字切り出し結果の例を示す説明図である。
【図３３】文字切り出し位置を示すネットワーク表現の例を示す説明図である。
【図３４】ネットワーク表現内のパターンの例を示す説明図である。
【図３５】ネットワークの例を示す説明図である。
【図３６】複数の文字候補がある場合のネットワーク例を示す説明図である。
【発明を実施するための形態】
【００２２】
本実施の形態は、文字列が含まれている画像を対象として、その画像内の文字認識の結果を修正して出力するものである。
まず、本実施の形態を説明する前に、その前提又は本実施の形態を利用する画像処理装置について説明する。なお、この説明は、本実施の形態の理解を容易にすることを目的とするものである。
【００２３】
例えば、図２９の例に示すような文字列画像を対象とする。まず、この文字列画像を文字セグメントに分割する。文字セグメントとは、文字そのもの、あるいは文字の一部となる可能性がある文字部分である。ここでは、図２９の例に示すような横書きの文字列画像を例にとる。横書きの画像では、垂直な線（あるいは垂直に近い線）で分割を行うことにより、文字セグメントに分割する。例えば図３０に示した縦線（切れ目候補３０１０、切れ目候補３０２０）で、文字列画像を分割して、３つの文字セグメント「イ」、「ヒ」、及び、「学」を得ることができる。図３０の例に示した縦線を切れ目候補と呼ぶこととする。切れ目候補３０１０が「イ」と「ヒ」を分け、切れ目候補３０２０が「ヒ」と「学」を分けている。
【００２４】
次に、図３１の例に示すように、各文字セグメントに対し、その外接矩形（外接矩形３１１０、外接矩形３１２０、外接矩形３１３０）を抽出する。
以下、特許文献１に記載されている技術内容を例にして説明する。なお、以下の説明で用いる用語は、特許文献１で用いる用語とは異なっている場合がある。ただし、内容は特許文献１と同じである。
前述の文字セグメントを統合して、文字画像を決定する。複数の文字セグメントを統合して１つの文字画像を形成する場合もあれば、１つの文字セグメントが１つの文字となる場合もある。文字画像を決定するとは、文字の切り出し位置を決定することと同値であるから、以下では文字切り出し位置の決定という場合もある。
文字セグメントの統合のパターンは複数存在する。複数存在するパターンの中で、最も文字画像として評価の高いものを選択することによって、最終的な文字切り出し位置を決定する。
図３１の例に対しては、すべての文字切り出しパターンは、図３２に示す例のようになる。つまり、図３２（ａ）の例では、パターン１として３つの文字画像（外接矩形３１１０、外接矩形３１２０、外接矩形３１３０）、図３２（ｂ）の例では、パターン２として２つの文字画像（外接矩形３１１０と３１２０、外接矩形３１３０）、図３２（ｃ）の例では、パターン３として１つの文字画像（外接矩形３１１０と３１２０と３１３０）、図３２（ｄ）の例では、パターン４として２つの文字画像（外接矩形３１１０、外接矩形３１２０と３１３０）を示している。
【００２５】
文字切り出し位置を示すネットワーク表現（グラフ表現ともいわれる）として、図３２の例に示した複数の切り出しパターンを表すことができる。図３３の例において、ネットワークは、始点ノード３３００、終点ノード３３９０、中間ノード３３１０（ノード１）、中間ノード３３２０（ノード２）の４つのノードと、ノード間を接続するアークで構成されている（ノード間の接続線をアークと呼ぶこととする）。始点は、文字列画像の左端、終点は文字列画像の右端にあたる。中間ノード３３１０（ノード１）、中間ノード３３２０（ノード２）は、それぞれ、文字の切れ目候補位置（すなわち、図３０の例に示した切れ目候補３０１０、切れ目候補３０２０）を示す。中間ノード３３１０（ノード１）は、切れ目候補３０１０に対応している。また、中間ノード３３２０（ノード２）は、切れ目候補３０２０に対応している。
【００２６】
始点から、各ノードを通って、終点に至る経路を以下、「パス」と呼ぶ。パスは、１又は複数のアークから構成される。通常、複数のパスが存在する。図３２の例に示した文字切り出しパターンは、これらの複数のパスに対応している。例えば、図３２（ｂ）の例に示したパターン２は、図３４の太線で示したパス（文字切り出しパターン３３０４、文字切り出しパターン３３２２）と対応している。
ここで、どれか１つのアークには、１つの文字画像の候補が対応している。例えば、始点ノード３３００と中間ノード３３２０（ノード２）を結ぶアークには、「化」という文字画像（文字切り出しパターン３３０４）が対応している。１つのアークに対応する文字に対して、その文字の評価値を決定することができる。これを「アーク評価値」と呼ぶこととする。
アーク評価値は、文字の形状情報や、文字認識における認識確度などから算出する。アーク評価値の算出方法はさまざまある。例えば、（１）特開平９−１８５６８１号公報、（２）特開平８−１６１４３２号公報、（３）特開平１０−１５４２０７号公報、（４）特開昭６１−１７５８７８号公報、（５）特開平３−３７７８２号公報、（６）特開平１１−２０３４０６号公報等に記載の従来技術に示されている手法等がある。
【００２７】
１つのパスは、複数のアークから構成されている。複数のアーク評価値を用いて、そのアークから構成されるパスの評価値を計算することができる。これを「パス評価値」と呼ぶこととする。
文字切り出し位置を決定するため、複数のパスの中で、最もパス評価値の高いパスを選択する。パスが選択できれば、文字切り出し位置が確定して、文字を切り出すことができる。そして、切り出した文字（文字画像）を文字認識した結果も確定することになる。
例えば、図３４の例で、太線のパスが選択されたとする。この場合、文字切り出し位置は、始点３３００と、中間ノード３３２０（ノード２）と、終点３３９０の３点となる。そして、確定した文字認識結果は、「化」（文字切り出しパターン３３０４）、「学」（文字切り出しパターン３３２２）となる。
【００２８】
ここで、パス評価値の算出方法について説明する。基本的には、パス評価値は、アーク評価値の重み付け和が用いられる。ｉ番目のアークのアーク評価値をＶｉとし、ｉ番目のアーク評価値に対する重みをｗｉとし、アークの数をＮ、パス評価値をＰとすると、Ｐは次の（１）式で与えられる。
【数１】
0005942361.tif 000002
パスの数が複数存在すると前述したが、実際の文字列には、多くの文字セグメントが存在しているため、存在するパスの数は膨大となる。
そこで、特開平３−２２５５７９号公報に記載の技術では、図３３の例に示されたようなネットワーク内の複数のパスから最も評価値の高いパスを探索する方法として、ダイナミックプログラミング手法を用いることが述べられている。
ここでは、ダイナミックプログラミング手法の中で、このようなネットワークの最良パスを探索するのに適したビタビ法の説明を行う。
【００２９】
図３５に示す例において、始点ノード３５００から終点ノード３５９０までのネットワークを説明する。なお、ノード間のリンク（アークともいわれる）は、図３５に示したものに限らず、さまざまな場合がある。図３５のように対称の結線でなくてもかまわない。
このネットワークにおいて、途中に複数のノード（中間ノード３５１１、中間ノード３５１２、中間ノード３５１３等）を介して始点ノードから終点ノードに達するとする。途中のノードを中間ノードと呼ぶこととする。
各ノードとノードの間にはリンクが張られている。このリンクにはそのリンク固有の評価値（リンク値）が割り当てられている。始点ノード３５００から終点ノード３５９０に向かうパスは複数存在する。パスは、複数のリンクから成り立つことになる。パスが含む複数のリンクのリンク値の和が、パスの評価値となる。
例えば、リンク値は、ノード間の距離であるとする。この場合、パス評価値が最小のパスは、始点ノードから終点ノードに向かうパスの中で、最小距離のパスということになる。あるいは、パス評価値が最大のパスを求める問題とすることも可能である。
【００３０】
ここで、ビタビ法は、あるノードにある方向から入力されるリンクを１に限定することによって、最適ではないパスを削減する。これにより、演算処理量と所要メモリ量を削減する手法である。
例えば、今、ノードｘ（中間ノード３５２１）に左から入力されるリンクがすでに、１に限定されているとする。同様に、ノードｙ（中間ノード３５２２）、ノードｚ（中間ノード３５２３）に関しても１に限定されているとする。このとき、ノードＸ（中間ノード３５３１）に左から入力されるリンクを限定する。ノードＸ（中間ノード３５３１）には、ノードｘ（中間ノード３５２１）、ノードｙ（中間ノード３５２２）、ノードｚ（中間ノード３５２３）の３つのノードからリンクが張られている。このとき、ノードＸ（中間ノード３５３１）を通るパスとして、最適な可能性があるのは、ノードｘ（中間ノード３５２１）、ノードｙ（中間ノード３５２２）、ノードｚ（中間ノード３５２３）からノードＸ（中間ノード３５３１）に向かうリンクのいずれかである。この３つのうちで最適なものだけを残し、残りの２つを削除する。このようにして、ノードＸ（中間ノード３５３１）に左から入力されるパス（リンク）を１に限定する。ノードＹ（中間ノード３５３２）、ノードＺ（中間ノード３５３３）に関しても同様に左から入力されるパスを１に限定する。
このような手順を左のノードＡ（中間ノード３５１１）、ノードＢ（中間ノード３５１２）、ノードＣ（中間ノード３５１３）から順に右の方向に行う。最終的にノードＰ（中間ノード３５８１）、ノードＱ（中間ノード３５８２）、ノードＲ（中間ノード３５８３）に入る３つのパスに限定する。この３つのパスの中で最適なものを選択すればよい。
このようなビタビ法を用いた最適パス選定方法を、図３３に例示のネットワークにも同様に適用し得る。文字切り出し位置をノードとする。また、アーク評価値を前述のリンク値とすればよい。
【００３１】
従来技術が扱っていた図３３に例示するようなネットワークは、１つのアークに対し、１つの文字候補が存在しているものである。しかし、実際には１つのアークに対して、複数の文字候補が存在している。つまり、文字認識結果が複数ある場合である。例えば、図３６のように、複数の文字候補を割り当てることになる。図３６は、複数の文字候補がある場合のネットワーク例を示す説明図である。図３６の例では、「化学」（文字画像３６０２）という画像を１文字として認識したときの認識結果が、文字候補３６０２Ａの「梢」、文字候補３６０２Ｂの「際」、文字候補３６０２Ｃの「傾」の３種類ある。「化」（文字画像３６０４）という画像を１文字として認識したときの認識結果が、文字候補３６０４Ａの「化」、文字候補３６０４Ｂの「比」、文字候補３６０４Ｃの「任」の３種類ある。同様に、他の文字画像に対しても文字認識結果としての文字候補が複数ある。なお、図３６の例では、各文字画像に対して３種類の文字候補があるが、異なる数の文字候補を割り当ててもよい。例えば、認識確度が予め定められた値以上である文字を文字候補とした場合は、各文字画像に対して文字候補の数が異なる場合がある。
従来技術では、このような場合に、ビタビ法（又は、一般的にはダイナミックプログラミング手法）を適用して、文字認識結果を得ることはされていない。
【００３２】
以下、図面に基づき本発明を実現するにあたっての好適な一実施の形態の例を説明する。
図１は、本実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、それらのモジュールとして機能させるためのコンピュータ・プログラム（コンピュータにそれぞれの手順を実行させるためのプログラム、コンピュータをそれぞれの手段として機能させるためのプログラム、コンピュータにそれぞれの機能を実現させるためのプログラム）、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能に一対一に対応していてもよいが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）の場合にも用いる。「予め定められた」とは、対象としている処理の前に定まっていることをいい、本実施の形態による処理が始まる前はもちろんのこと、本実施の形態による処理が始まった後であっても、対象としている処理の前であれば、そのときの状況・状態に応じて、又はそれまでの状況・状態に応じて定まることの意を含めて用いる。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等が通信回線（一対一対応、一対多対応、多対一対応、多対多対応の通信接続を含む）で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。もちろんのことながら、「システム」には、人為的な取り決めである社会的な「仕組み」（社会システム）にすぎないものは含まない。
また、各モジュールによる処理毎に又はモジュール内で複数の処理を行う場合はその処理毎に、対象となる情報を記憶装置から読み込み、その処理を行った後に、処理結果を記憶装置に書き出すものである。したがって、処理前の記憶装置からの読み込み、処理後の記憶装置への書き出しについては、説明を省略する場合がある。なお、ここでの記憶装置としては、ハードディスク、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、外部記憶媒体、通信回線を介した記憶装置、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）内のレジスタ等を含んでいてもよい。
【００３３】
本実施の形態である画像処理装置は、画像から文字を認識するものであって、図１の例に示すように、画像受付モジュール１１０、文字列抽出モジュール１２０、切出位置抽出モジュール１３０、文字候補抽出モジュール１４０、パス限定処理モジュール１５０、出力モジュール１６０を有している。
【００３４】
画像受付モジュール１１０は、文字列抽出モジュール１２０と接続されている。画像受付モジュール１１０は、画像を受け付けて、その画像を文字列抽出モジュール１２０へ渡す。画像を受け付けるとは、例えば、スキャナ、カメラ等で画像を読み込むこと、ファックス等で通信回線を介して外部機器から画像を受信すること、ハードディスク（コンピュータに内蔵されているものの他に、通信回線を介して接続されているもの等を含む）等に記憶されている画像を読み出すこと等が含まれる。画像は、２値画像、多値画像（カラー画像を含む）であってもよい。受け付ける画像は、１枚であってもよいし、複数枚であってもよい。また、画像の内容として、文字列が含まれているのであれば、ビジネスに用いられる文書、広告宣伝用のパンフレット等であってもよい。
【００３５】
文字列抽出モジュール１２０は、画像受付モジュール１１０、切出位置抽出モジュール１３０と接続されている。文字列抽出モジュール１２０は、画像受付モジュール１１０が受け付けた画像から文字列を抽出する。
切出位置抽出モジュール１３０が対象とする画像は横書きあるいは縦書きの、１列のみの文字列画像を対象としている。なお、ここで、列とは、横書きの場合は横に並ぶ列であり、縦書きの場合は縦に並ぶ列である。
したがって、文字列抽出モジュール１２０は、画像受付モジュール１１０が受け付けた画像が１列のみの文字列画像であれば、そのまま用いればよい。画像受付モジュール１１０が受け付けた画像が、複数の文字列が存在するものがあり、このような複数文字列を単一の文字列になるように分離する手法としては、従来よりさまざまものが提案されているため、それらを用いればよい。単一の文字列となるように分離する例としてもさまざまな方式があるため、そのうちのいずれかを用いればよい。例えば、（１）特開平４−３１１２８３号公報、（２）特開平３−２３３７８９号公報、（３）特開平５−７３７１８号公報、（４）特開２０００−９０１９４号公報、等を用いればよい。これ以外の方法であってもよい。
【００３６】
切出位置抽出モジュール１３０は、文字列抽出モジュール１２０、文字候補抽出モジュール１４０と接続されている。切出位置抽出モジュール１３０は、文字列抽出モジュール１２０が抽出した文字列画像から文字画像を切り出す位置を抽出する。つまり、文字列画像を複数の文字セグメントに分割する。この文字切り出し位置の抽出方法としてもさまざまな方式があるため、そのうちのどれかを用いればよい。例えば、（１）特開平５−１１４０４７号公報、（２）特開平４−１００１８９号公報、（３）特開平４−９２９９２号公報、（４）特開平４−６８４８１号公報、（５）特開平９−５４８１４号公報、（６）特開平９−１８５６８１号公報の００２１段落に記載の文字の境界候補抽出方式、（７）特開平５−１２８３０８号公報の０００５段落に記載の文字切り出し位置決定方法等を用いればよい。これ以外の方法であってもよい。なお、ここでの文字画像とは、いわば文字候補画像であり、必ずしもその文字画像が１つの文字を表す画像でなくてもよい。
【００３７】
また、切出位置抽出モジュール１３０は、複数の切り出し位置を抽出してもよい。複数の切り出し位置を抽出することによって、１つの文字列画像に対して、文字切出位置群が複数ある。文字切出位置群とは、１つの文字列画像に対して、１つ以上の文字切り出し位置があることをいう。例えば、２つの文字切り出し位置があれば、３つの文字画像に分けられることになる。また、文字切出位置群が複数あるとは、１つの文字列画像に対して、文字切出位置で分けられた文字画像列が複数あることをいう。例えば、２つの文字切り出し位置で３つの文字画像からなる文字画像列と、３つの文字切り出し位置で４つの文字画像からなる文字画像列となる。具体例で説明すると、「化学」という文字列に対して、「イ」「ヒ」「学」からなる文字画像列と「化」「学」からなる文字画像列を生成することである。
【００３８】
文字候補抽出モジュール１４０は、切出位置抽出モジュール１３０、パス限定処理モジュール１５０と接続されている。文字候補抽出モジュール１４０は、切出位置抽出モジュール１３０によって抽出された位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補を抽出する。この抽出処理を行うために、文字認識処理を行ってもよい。そのために、文字候補抽出モジュール１４０内に文字認識モジュールを含んでいてもよい。文字認識処理による認識結果は、前述のように、１つの文字画像に対して複数の文字候補が対応する。つまり、その文字画像を文字認識して、第１位の認識確度を有している文字候補、第２位の認識確度を有している文字候補等のように、複数の文字候補を文字認識結果とする。そして、文字認識結果として、文字候補の他に、その文字候補の認識確度を有していてもよい。また、抽出するのに、１つの文字画像に対して予め定められた数の文字候補を抽出してもよいし、予め定められた値以上の認識確度を有している文字候補を抽出してもよい。なお、認識確度は、文字認識処理において、その認識結果としての信頼性を表す値であってもよいし、文字画像の外接矩形のサイズ、縦横比等によって定められる文字らしさを表す値であってもよい。
【００３９】
パス限定処理モジュール１５０は、文字候補抽出モジュール１４０、出力モジュール１６０と接続されている。パス限定処理モジュール１５０は、文字候補抽出モジュール１４０によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成する。隣接する文字画像のノード間とは、隣接する文字画像があり、その文字画像に対応するノード間ということである。
また、切出位置抽出モジュール１３０が複数の切り出し位置を抽出した場合は、パス限定処理モジュール１５０は、切出位置抽出モジュール１３０によって抽出された複数の切り出し位置によって分けられた文字画像に対して文字認識を行った結果である複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成するようにしてもよい。
そして、パス限定処理モジュール１５０は、生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する。
また、パス限定処理モジュール１５０は、限定されたリンクによって接続されたノードの文字候補間の関係による文字列らしさを表す値に基づいて、リンク値を生成してもよい。さらに、リンクを構成しているノードに対する文字らしさを表す値に基づいて、リンク値を生成するようにしてもよい。
そして、パス限定処理モジュール１５０は、生成されたリンク値に基づいて、ネットワーク内のパスを選択するようにしてもよい。
【００４０】
また、パス限定処理モジュール１５０は、最初のリンクから文字列パターンに合致していない場合、その合致していないリンクの次のリンクからその文字列パターンに合致するリンクに限定するようにしてもよい。
また、パス限定処理モジュール１５０は、文字列パターンに合致するリンクがない場合は、その文字列パターン内の一部分の文字列パターンに合致するリンクに限定するようにしてもよい。
【００４１】
出力モジュール１６０は、パス限定処理モジュール１５０と接続されている。出力モジュール１６０は、パス限定処理モジュール１５０によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する。また、出力モジュール１６０は、パス限定処理モジュール１５０によって選択されたパス内の文字候補列を文字認識結果として出力するようにしてもよい。文字認識結果を出力するとは、例えば、プリンタ等の印刷装置で印刷すること、ディスプレイ等の表示装置に表示すること、メモリーカード等の記憶媒体に記憶すること、他の情報処理装置へ渡すこと等が含まれる。
【００４２】
図２は、対象とする帳票２００の例を示す説明図である。この帳票２００には、名前枠２１０、住所枠（市前）２２０と住所枠（市後）２３０が設定されている。この帳票２００への記載者は、名前枠２１０には名前を記入する。また、住所枠（市前）２２０と住所枠（市後）２３０には住所を記載する。その結果、名前枠２１０内には、名前のみが記入されていると仮定することができる。又は、住所枠（市前）２２０、住所枠（市後）２３０内には住所のみが記入されていると仮定することができる。
このように、枠に記載されるはずの文字、又は単語が限定される場合には、自由に記載可能な場合よりも認識率を上げることができる。例えば、住所などの場合で、図２の例のように、住所枠（市前）２２０内に市の名前を書くように指定されている場合を考える。市の名前は限定されているので、それに限定すれば、より精度が上がる。ここで、例えば、住所枠（市前）２２０内に記載される可能性のある市名が、下記３つに限定されているとする。
（１）横浜
（２）川崎
（３）横須賀
ここで、住所枠（市前）２２０内に記載される文字列は、この３パターンに限定されているということができる。
【００４３】
このような、文字列パターンの限定を指定する手法の例として、正規表現がある。正規表現には種々の表記法があるが、一例として、正規表現の表記方法を図３に例示する。図３は、正規表現表記規則３００の例を示す説明図である。正規表現表記規則３００は、規則欄３１０内の表記を、意味欄３２０で説明している。
例えば、前記のように、「横浜」、あるいは、「川崎」、あるいは、「横須賀」のみを対象とする場合、正規表現としては、
「横浜｜川崎｜横須賀」
と記述すればよい。
【００４４】
特許文献１に記載の技術では、文字位置毎に、字種を限定させて、精度を上げる例が述べられている。
前述の市名の例では、
・１文字目には、「横」、「川」のみ
・２文字目には、「浜」、「崎」、「須」のみ
・３文字目には、「賀」のみ
しかあり得ない。この条件を利用する。例えば、１文字目には、「横」と、「川」しかあり得ないので、それのみを出力するように設定する。このようにすることによって、認識率の精度を上げることが可能となる。例えば、「横」は、「黄」と字が似ており、正解は「横」であるのに、「黄」と誤認識する可能性があるが、出力文字を、「横」と「川」に限定することで、「黄」の出力を禁ずることとなっている。
【００４５】
さらに、特許文献２に示すように、複数の文字候補を１文字目から見ていく方法もある。
１つの文字を認識する場合、複数の認識候補を得ることができる。複数の文字候補には、第１候補から、第ｎ候補までの、順位が付けられている。第１候補が最も確度の高い候補であり、数値が大きくなるに従って、認識の確度は低下する。特許文献２に記載の技術では、１文字目の第１候補から順に、正規表現にマッチするものを探索していく。ここで、決定するのは１文字目であるとする。１文字目の、第１候補が正規表現にマッチすれば、その候補を選択する。第１候補が正規表現にマッチしない場合、第２候補をチェックする。以降、正規表現にマッチするまで、第２、第３と、順に候補を探索する。正規表現にマッチする候補がない場合は、終了する。正規表現にマッチする候補がある場合その候補を選択する。候補を選択した後では、２文字目の選択を行う。ここではすでに１文字目の選択が行われているため、１文字目と合わせて、２文字の文字列が正規表現にマッチするような文字を選択する必要がある。ここで、１文字目と同様に、２文字目の第１候補から順に探索する。正規表現にマッチした段階で、その候補を選択する。
この方法であれば、複数の文字候補があっても、最終的に正規表現にマッチする文字列を選択することができる。
【００４６】
例えば、各文字と、その認識文字候補が、図４の例のようになっているとする。つまり、３つの各文字について、３つの文字認識候補がある例である。また、この場合の、正解は、「横須賀」であるとする。また、出力文字パターンとしての正規表現は、
「横浜｜川崎｜横須賀」
であるとする。
この例では、１文字目は第２候補、２文字目は第２候補、３文字目は第１候補を選択することで、正解出力を得ることができる。
特許文献１に記載の技術では、予め文字位置に応じて、出力される文字候補を決める。特許文献１に記載の技術での出力候補は、図５の例に示すハッチング部を除いた出力の中で、最も順位の高いもの（第１候補の方が第２候補よりも順位が高いとする）を出力することになる。結局、特許文献１に記載の技術では、「横浜賀」が出力されることとなる。
【００４７】
特許文献２に記載の技術では、１文字目では、正規表現に合致するのは「横」であるため、「横」が選択される。２文字目では、最も順位の高く、かつ正規表現に合致するのは、「浜」であるため、「浜」が出力される。３文字目では、正規表現に合致する文字はない。「横浜賀」という単語は、出力文字パターン「横浜｜川崎｜横須賀」の中にはないためである。そのため、特許文献２に記載の技術では、出力なしということになるか、あるいは、「横浜賀」の中で、最長一致の「横浜」が出力されることになる。
【００４８】
特許文献１、特許文献２に記載の技術では、文字列の１文字目、かつ、第１候補から、順に正規表現（あるいは、正規表現のような文字列パターン指示方法。以下、正規表現として示す）に合致する文字を選択している。
本実施の形態では、文字認識候補のあり得る文字列のうちから、正規表現に合致するパターンを探索するものである。そして、そのためにビタビ法を用いるようにしてもよい。
【００４９】
図６は、本実施の形態による処理例を示すフローチャートである。
ステップＳ６０２では、画像受付モジュール１１０が、対象となる画像を受け付ける。
ステップＳ６０４では、文字列抽出モジュール１２０が、画像から文字列画像を抽出する。
ステップＳ６０６では、切出位置抽出モジュール１３０が、文字列画像を対象として切り出し位置を抽出する。
ステップＳ６０８では、文字候補抽出モジュール１４０が、切り出された文字画像を文字認識する。
ステップＳ６１０では、文字候補抽出モジュール１４０が、複数の文字認識結果を文字画像の文字候補として抽出する。
ステップＳ６１２では、パス限定処理モジュール１５０が、ネットワークを生成し、その中のパスを限定する。
ステップＳ６１４では、出力モジュール１６０が、文字認識結果を出力する。
【００５０】
次に、図７から図２７を用いて、パス限定処理モジュール１５０による処理を説明する。
本実施の形態は、さらに、パス評価値の高いパスを出力することによって、文字切り出し位置の確定、又は文字認識を行うものである。また、パスの探索にダイナミックプログラミングの手法を用いてもよい。
本実施の形態のネットワークにおいては、始点ノード、終点ノード、複数の中間ノードがある。また、各ノード間のリンクには、リンク値を与える。始点ノードから１あるいは複数の中間ノードを介して、終点ノードに至るパスは、介するノードに依存したリンクを通ることになる。始点ノードから終点ノードに至るパスのパス評価値は、そのパスが通ったリンクのリンク値の重み付け和として表すことができる。
本実施の形態のパス限定処理モジュール１５０は、１つの文字画像に対して、複数の文字認識結果が存在しているときに、前述のノード、リンク、パスの構成（ネットワーク構造）を生成するものである。ネットワーク構造が与えられれば、パス限定処理モジュール１５０によってビタビ法などの手法を用いて、最適パスを探索することが可能となる。
【００５１】
＜Ａ１．文字切り出し位置が固定の場合＞
まず、切出位置抽出モジュール１３０の抽出する文字切り出し位置が固定（一種類）の場合について説明する。
図７は、記号例を示す説明図である。記号の種類として、長方形７１０、横棒である接続線７２０、７２２、７２４、７２７、７２８、円弧７３０、丸である文字候補７４２、７４４、７４６がある。
図７の例において、長方形７１０Ａ、７１０Ｂ、７１０Ｃ、７１０Ｄ（図８に例示する長方形７１０）は、それぞれ文字セグメントを表す。
また、横棒である接続線７２０、７２２、７２４、７２６、７２８は、文字切り出し位置を示す（図９に例示する接続線７２０、接続線７２２）。文字セグメントは文字切り出し位置を介して、隣接する文字セグメントにつながっている。
さらに、丸で表されている文字候補７４２Ａ、７４４Ａ等は、１つの文字セグメントを１文字として認識したときの、複数の文字候補を示す。円弧７３０Ａ、７３０Ｂ、７３０Ｃ、７３０Ｄは、下の１つの文字セグメントだけを対象に文字認識を行っていることを示している。
【００５２】
図１０の例では、文字候補７４２、７４４、７４６は、その下の長方形７１０が示す１文字の文字セグメントを認識したときの複数の文字候補であることを示している。また、円弧７３０は、その下の長方形７１０１つだけを対象に文字認識を行うことを示している。
本実施の形態では、文字セグメントの複数の文字候補をノードとして捉える。さらに、隣接する文字セグメントの文字候補と、リンクを接続する。図１１の例にリンクを太線で記入して示す。
ここでリンク値生成モジュール１８１０が生成するリンク値としては、リンク左右のノードの相互作用を示すものを使ってもよい。具体的には、リンクの左の文字候補とリンクの右の文字候補が連続して日本語の文章中に出現する確率（バイグラム）を用いる。
このようにノードとリンクを構成することによって、すべてのネットワーク構造が規定できる。ネットワーク構造が規定できれば、ビタビ法等により、最適パスを選択できる。
【００５３】
＜Ａ２．ノード内情報も用いる場合＞
前述では、リンク値として、ノード間の相互作用を示すもの（文章中に出現する確率）だけを用いたが、さらにノード単独の評価値を用いるようにしてもよい。ここでは、ビタビ法を用いて最適パスを探索するものとする。左から順にノードの左から入るリンクをノード毎に１つだけに限定していく処理を行う。
今、図１１の例で文字候補７４２Ｂ、７４４Ｂ、７４６Ｂのリンクを限定する段階であるとする。
ここで、文字候補７４２Ｂ、７４４Ｂ、７４６Ｂと、左側にある文字候補７４２Ａ、７４４Ａ、７４６Ａ間のリンク値を生成する。リンク値としては、各ノード間の相互作用を表すバイグラムなどの値と、各ノード内部の値の両方を用いる。ノード内部の値とは、例えば、文字候補７４２Ｂの文字の認識確度などがある。
【００５４】
ここで、リンクは、文字候補７４２Ｂ、７４４Ｂ、７４６Ｂと文字候補７４２Ａ、７４４Ａ、７４６Ａ間にあるため、リンク値としては、文字候補７４２Ｂ、７４４Ｂ、７４６Ｂと文字候補７４２Ａ、７４４Ａ、７４６Ａ間の評価値を算出するのが簡単である。しかし、ノード内部の値は、文字候補７４２Ｂ、７４４Ｂ、７４６Ｂと文字候補７４２Ａ、７４４Ａ、７４６Ａ間にあるのではなく、この場合、文字候補７４２Ｂ、７４４Ｂ、７４６Ｂに存在する。
つまり、ノード間情報はリンクの内部に存在していて、ノード内情報はリンクの端点に存在する。このような発生位置、又は概念が異なる値を一度に扱う。
【００５５】
従来では、図３３に示す始点ノード３３００、中間ノード３３１０（ノード１）、中間ノード３３２０（ノード２）、終点ノード３３９０など（つまり、文字切り出し位置）をノードとして、ノード間のアーク評価値を算出している。本実施の形態のように、複数の文字コードをノードとして、ノード間のリンク値を算出するわけではない。そのため、従来技術をそのまま用いることはできない。
本実施の形態では、リンクの評価値として、リンクの内部に存在する値（例えば、バイグラムの値）と、リンクの一方の端点のみに存在する値（例えば、文字候補７４２Ｂの文字認識確度）を用いる。他方の端点に存在する値（例えば、文字候補７４２Ａの文字認識確度）は用いない。このようにすることで、リンクの内部の値と、リンクの端点の値をともに用いる評価が可能となる。
最終的には、文字列の評価値（パス評価値）として、（１）式で、すべてのリンクの評価値を加算することになる。そのため、リンクの評価値の中に、リンクの内部の評価値と、リンクの一方の端点の評価値が含まれていれば、パス評価値の中にすべてのリンク内部の評価値とリンク端点の評価値が１つずつ含まれることになる。
【００５６】
後述するリンク値生成モジュール１８１０では、前述のリンク内部の値と、リンク端点の値のように、複数の値（バイグラムや認識確度）などを特徴量として、リンク値を算出すればよい。このように複数の値から、１つのリンク値を算出する方法としては、（１）特開平９−１８５６８１号公報、（２）特開昭６１−１７５８７８号公報、（３）特開平３−３７７８２号公報、（４）特開平１１−２０３４０６号公報等に記載の技術を用いればよい。これ以外の方法であってもよい。
なお、複数の値を特徴量ベクトルとして把握し、リンク値は、特徴量ベクトルを対象として、リンク評価値（スカラー値）を出力する関数で実現できる。
【００５７】
＜Ａ３．リンク情報として２以上のノードを用いる場合＞
前述では、リンク左右のノードの相互情報としてバイグラムを用いていた。この場合、リンク情報として２つのノード間の関係情報を用いていることになる。
ビタビ法を用いる場合、例えば、ノードである文字候補７４２Ａ、７４４Ａ、７４６Ａの左側のリンク数はすでに１個に限定されていることになる。この場合には、２以上のノードの情報を用いてリンク情報を構築することが可能となる。
例えば、２つの連続する文字の生起確率であるバイグラムではなく、３つの連続する文字の生起確率であるトライグラムを用いることも可能となる。
今、リンク値生成モジュール１８１０が、ノードである文字候補７４２Ｂ、７４４Ｂ、７４６Ｂの左側のリンク値を生成しようとする。
例えば、文字候補７４２Ａ−文字候補７４２Ｂ間のリンク値を算出する。バイグラムであれば、文字候補７４２Ａと文字候補７４２Ｂが連続する生起確率を求めればよい。ここで、トライグラムを求める場合を説明する。文字候補７４２Ａの左側のリンクは１つに限定されているため、実は、文字候補７４２Ａの左の文字も確定していることになる。この文字を保持するノードをＧとする。トライグラムとしては、ノードＧ−ノード（文字候補７４２Ａ）−ノード（文字候補７４２Ｂ）の３つの文字に関する生起確率を求めればよい。
以上のように求めたトライグラムをノード（文字候補７４２Ａ）−ノード（文字候補７４２Ｂ）間のリンク値として生成すればよい。同様に、Ｎｇｒａｍであっても、求めることが可能となる。
【００５８】
＜Ａ４．文字切り出し位置が確定していない場合＞
文字切り出し位置が確定していない場合（つまり、切出位置抽出モジュール１３０が複数の文字切り出し位置を抽出した場合であり、具体的には、「化」のように、「イ」と「ヒ」、あるいは、「化」のどちらになるか分からない場合）、文字候補の選択と、文字切り出し位置の選択を行うようにしてもよい。文字切り出し位置が確定していない場合、文字候補の選択は、文字切り出し位置の選択となる。
図１２は、文字切り出し位置が複数ある場合の処理例を示す説明図である。ここでは、円弧の記号の意味が追加されている。円弧が下にある複数の文字セグメント（長方形）を指し示す場合、その円弧はその複数の文字セグメントを統合した画像を１文字とみなして認識することを示す。円弧１２１０Ａは、長方形７１０Ａと長方形７１０Ｂを統合した画像を１文字とみなして文字認識結果として文字候補１２２２Ａ、１２２４Ａ、１２２６Ａを有している。また、円弧１２１０Ｃは、長方形７１０Ａ、７１０Ｂ、７１０Ｃ、７１０Ｄを統合した画像を１文字とみなして文字認識結果として文字候補１２２２Ｃ、１２２４Ｃ、１２２６Ｃを有している。
図１３の例に示すように、円弧７３０Ａと円弧７３０Ｂの下に２つの文字セグメント（長方形７１０Ａ、長方形７１０Ｂ）「イ」と「ヒ」がある場合に、その２つを含む円弧１２１０の上の文字候補（文字候補１２２２、１２２４、１２２６）は、「イ」と「ヒ」を統合した１つの文字セグメント「化」を認識したときの複数の文字候補に相当する。
【００５９】
文字切り出し位置が確定していない場合のリンクの接続は、図１４の例に示すようになる。図１４は、文字切り出し位置が複数ある場合の処理例を示す説明図である。
ここでは、文字切り出し位置に注目する。今、図１４の矢印で示す文字切り出し位置に関連するノードのリンクを対象とする。この文字切り出し位置でリンクされるノードには、
（１）左側ノード：矢印の文字切り出し位置に円弧の右側が存在するノード（斜線でハッチングしたノード、文字候補１４４２Ａ、文字候補１４４４Ａ、文字候補１４６２Ａ、文字候補１４６４Ａ、文字候補１４７２Ａ、文字候補１４７４Ａ等）と、
（２）右側ノード：矢印の文字切り出し位置に円弧の左側が存在するノード（内部が白のノード、文字候補１４４２Ｂ、文字候補１４４４Ｂ、文字候補１４６２Ｂ、文字候補１４６４Ｂ、文字候補１４７２Ｂ、文字候補１４７４Ｂ等）
の２種類がある。このとき、左側ノードと、右側ノード間にリンクを形成することによって、グラフ構造を構築することができる。
例えば、すべての左側ノードが、すべての右側ノードに直接接続できるようにリンクを形成すればよい。さらに、すべての文字切り出し位置において、前述のように、左側ノードと右側ノードのリンクを形成し、さらに、左側が文字列の端点の場合には始点ノードに接続し、また、右側が文字列の端点の場合には終端ノードに接続すれば、すべてのグラフ構造を構築することができる。
【００６０】
この場合においても、リンク値は、リンク左右のノードの相互作用を示すものを使ってもよいし、ノード内部の評価値を用いてもよい。
特に、この場合には、文字切り出し位置が確定していないため、ノード内部の評価値として、文字の形状情報を用いることができる。文字形状情報の例として、文字の縦横比や、文字左右の空白量、等を用いることができる。
【００６１】
このようにすることによって、文字列の左端から、文字列の右端に至るすべてのパスを書き出すことができる。各パスは、認識出力文字列に該当する。つまり、文字列を構成するネットワークにおいて、左端ノードから、右端ノードへ至るパスを決定することによって、文字列を決定できることになる。
【００６２】
パスの中で、正規表現にマッチするものだけを出力するようにすればよい。しかしながら、パスの数は膨大であるので、すべてのパスに対して正規表現にマッチしているかどうかをチェックすることは現実的ではない。
そこで、ビタビ法を用いて高速化する。
前述したように、あるノードに左から接続されるリンクの本数を１本に限定するようにしていく。もちろんのことながら、あるノードに右から接続されるリンクの本数を１本に限定するようにしてもよいが、以下の例では、左から接続されるリンクについて説明する。
ここで、あるノードに左から接続されるリンクを決定すれば、そのノードに至る出力文字列が確定できる。この出力文字列が正規表現に部分一致しているかどうかをチェックすればよい。
【００６３】
まず、あるノードに左から接続されるリンクが、Ｎ本あるとする。Ｎ本のリンクのうち、正規表現に部分一致しているものだけを抽出し、部分一致していないものを捨てる。
例えば、ノードＤ（文字候補「会」）に左から３本のリンクが接続されているとする。そして、そのリンクはそれぞれノードＡ（文字列候補「ヒ学」）、ノードＢ（文字列候補「化学」）、ノードＣ（文字列候補「ト学」）から接続されているとする。ここで、正規表現が、「化学会議」とされているとする。
ノードＡ、Ｂ、Ｃには、さらに左からノードが接続されているが、その部分は説明では省略している。ノードＡ、Ｂ、Ｃに関しては、すでに、左側のノードが１本に限定されているため、それらのノードに至るパスが確定している。そのため、それらのノードに至る文字列も確定している。ノードＡの文字列候補は「ヒ学」、ノードＢの文字列候補は「化学」、ノードＣの文字列候補は「ト学」となっている。
ここで、ノードＤに左から接続されるリンクを確定させる。ノードＡからのパスであれば、文字列は「ヒ学会」であり、ノードＢからのパスであれば、文字列は「化学会」であり、ノードＣからのパスであれば、文字列は「ト学会」となる。この中で、正規表現である文字列パターンに部分一致するものを選択する。
【００６４】
ここで、文字列が文字列パターンに部分一致するとは、文字列が、正規表現「化学会議」の先頭から連続する部分に一致すればよいというものである。例えば、「化学会」は、正規表現「化学会議」の最初から３文字目までは一致するので、部分一致しているとする。その他の、「ヒ学会」、「ト学会」は部分一致しない。
したがって、部分一致とは、文字列がＸであるとき、Ｘの後ろに任意の文字が続くとみなして、後ろに任意の文字が続く文字列が先頭から正規表現に一致しているかどうかを判断するとしてもよい。
【００６５】
ここで、部分一致しているものが複数ある場合には、正規表現を用いた方式とは別のやり方で最も評価値の高いものを選択すればよい。
さらに、部分一致しているものがない場合には、すべての候補の中から、正規表現とは別のやり方で最も評価値の高いものを選択すればよい。
以上のようにして、各ノードにおいて、左側のリンクを１つに絞る。最終的に、左端から右端に向かう複数のパスが残るので、その中から出力すべきパスを得ればよい。
【００６６】
＜パス限定処理モジュール１５０の例１＞
図１５は、パス限定処理モジュール１５０内のモジュール構成例を示す説明図である。パス限定処理モジュール１５０は、ネットワーク構築処理モジュール１５１０、ノード数限定処理モジュール１５２０、制御モジュール１５３０、出力決定処理モジュール１５４０を有している。
図１６は、パス限定処理モジュール１５０による処理例を示すフローチャートである。
ステップＳ１６０２では、ネットワーク構築処理モジュール１５１０が、ネットワークを構築する。
ステップＳ１６０４では、ノード数限定処理モジュール１５２０が、制御モジュール１５３０による制御によって、ネットワーク内のノードを限定する。
ステップＳ１６０６では、出力決定処理モジュール１５４０が、出力すべきパスを決定する。
【００６７】
ネットワーク構築処理モジュール１５１０は、ノード数限定処理モジュール１５２０と接続されている。ネットワーク構築処理モジュール１５１０は、文字候補抽出モジュール１４０によって抽出された複数の文字候補の各々をノードとし、隣接する文字画像のノード間にリンクを構築することによってネットワークを生成する。つまり、前述したように、文字列の一方の端（例えば、左端）から他方の端（例えば、右端）に至るネットワークを構築する。
ノード数限定処理モジュール１５２０は、ネットワーク構築処理モジュール１５１０、制御モジュール１５３０、出力決定処理モジュール１５４０と接続されている。ノード数限定処理モジュール１５２０は、ネットワーク構築処理モジュール１５１０によって生成されたネットワーク内のノードに先頭方向又は最後尾方向のいずれか一方向から接続するリンクに対して、予め定められた文字列パターンに合致するリンクに限定する。つまり、前述したように、各ノードにおいて、例えば左から接続されるノード数を限定する処理を行う。例えば、限定するノード数として１つである。
【００６８】
制御モジュール１５３０は、ノード数限定処理モジュール１５２０と接続されている。制御モジュール１５３０は、ノード数を限定するノード位置を左から順になるように制御するものである。
本実施の形態では、制御モジュール１５３０において、右端の終点ノードにおけるノード数を１本に限定する処理は行わない。すなわち、右端の終点ノードに入るリンク数（アーク数）が、Ｍ本であれば、最終的にＭ本のパスが残ることになる。Ｍ本のパスは、Ｍ個の文字列に相当している。
【００６９】
出力決定処理モジュール１５４０は、ノード数限定処理モジュール１５２０と接続されている。出力決定処理モジュール１５４０は、ノード数限定処理モジュール１５２０によって限定されたリンクによってつながれたパス内の文字候補列を文字認識結果として出力する。つまり、前述のＭ個の文字列の中から、出力すべき文字列を選択する。例えば、右端の終点ノードに３つのリンクが接続されている場合、３本の文字列候補が残ることになる。この３つの候補から出力すべき文字列を選択する。
このようにするのは、途中の部分一致では、文字列の後ろ側に一致していない文字数を評価することができないためである。文字列全体として、文字列の前側と後ろ側の不一致数を合わせて不一致数の最も少ないものを選択するため、Ｍ個の文字列に関して、評価を行う。
また、制御モジュール１５３０において、右端の終点ノードにおける入力ノード数を１本になるまで選択してもよい。出力決定処理モジュール１５４０では、その１本化した文字列の中から、正規表現にマッチする最も長い部分がある文字列を選択する。
【００７０】
「出力すべき文字列」を選択する評価尺度は、さまざまあって、下記のいずれか等を選択すればよい。
（１）評価尺度１
正規表現に最長一致するものを選ぶ。
最長一致するものが複数ある場合には、最もパス評価値の高い文字列を選ぶ。
変形例として、最長一致するものの文字数が所定の文字数未満である場合は、リジェクトとする。
（１．１）変形例（その１）
文字列の左端や右端が正規表現に一致しない場合、その一致しない左端や右端を除いた部分を抜き出して、その部分のみを正規表現に一致したとして、出力する。例えば、正規表現が「化学会議」で、文字列が「ＡＢ化学会議Ｃ」の場合、「ＡＢ」と「Ｃ」を取り除いた「化学会議」を出力する。このとき、取り除いた左端「ＡＢ」と右端「Ｃ」の文字数は計３文字となる。この取り除いた文字数が最も少ない文字列を選択する。
（１．２）変形例（その２）
前述の例で、「化学会議」となっている画像中の文字列の長さ（例えば、画像の画素数や、スキャン前の紙におけるセンチ数など）が最も長いものを選択してもよい。つまり、除去するノイズの量が画像中で最も小さいものを選択する。
【００７１】
（２）評価尺度２
正規表現に合致する文字列の長さは規定せず、正規表現に合致するものの中で、最もパス評価値の高い文字列を選ぶ。
出力文字列の中に、正規表現にマッチする部分があればよい。例えば、正規表現が「化学会議」であるとして、文字列が、「前化学会議Ａ」であって、最もパス評価値の高い文字列であるとき、１文字目と６文字目を省いて、「化学会議」という部分だけを出力することになる。
また、正規表現に完全に一致するときのみ採用するとしてもよい。
【００７２】
（３）評価尺度３
左端から右端までの全文字列が正規表現に一致すれば、その文字列を出力する。複数のパスが合致する場合は、最もパス評価値の高い文字列を選ぶ。ただし、左端から右端までの全文字列の中で、正規表現に一致するものがない場合は、出力がない（リジェクト）とする。
【００７３】
＜パス限定処理モジュール１５０の例２＞
前述のパス限定処理モジュール１５０の例１では、文字列の左端から、部分一致するノードを選択することになる。
ところが、部分一致では、文字列の先頭から、正規表現に一致する必要がある。
文字列の先頭部分には、ノイズが発生する場合が多い。ノイズが発生した場合には、文字列の最初から部分一致する文字列が存在しない場合がある。例えば、文字列の最初に縦棒のノイズが存在している場合、多くの出力文字列の１文字目に、「１」という文字が入ってしまう場合がある。
このような場合、ネットワーク構築処理で構築されたすべてのパスが部分一致しないことになってしまい、正規表現のマッチングが不可能となる。部分一致とは、文字列の先頭から一致することであるためである。
そこで、文字列の最初にノイズが混入した場合の不安定性を排除することを行う。
【００７４】
そのために、ノード数限定処理モジュール１５２０における処理において、各リンクに対して、下記の処理を行う。
（１）Ｉ＝１とする。
（２）文字列のＩ文字目から部分一致しているかどうかをチェックする。
（３）部分一致していれば終了。
（４）Ｉが文字列の最後であれば終了。
（５）部分一致していなければ、Ｉ＝Ｉ＋１として（２）に戻る。
そして、変数Ｉの値を用いて、各リンクに対して、何文字目から部分一致したかを計測する。その計測したＩを用いて、ノード数限定処理モジュール１５２０における処理では、下記の方法によって入力ノード数を限定する。
・部分一致しているパスの中で、Ｉの値が最も小さい入力ノードを選ぶ。
・部分一致しているパスの中で、最も小さいＩの値が複数ある場合、パス評価値が最も大きなノードを選ぶ。
・部分一致しているパスがない場合、パス評価値が最も大きなノードを選ぶ。
【００７５】
＜パス限定処理モジュール１５０の例３＞
また、パス限定処理モジュール１５０は、正規表現に完全に一致する文字列がない場合、部分一致文字列を出力するようにしてもよい。
前述のパス限定処理モジュール１５０の例１、２では、与えられた文字列パターン（正規表現）に一致するパス（文字列）を出力していた。ただし、一部でもよいから、一致するものを出力したいという場合もあり得る。例えば、前述の市名の例で、図１７の例のような認識結果が得られたとする。また、正解は「横浜」であるとする。
【００７６】
この場合、「横浜」となるパスは存在しないので、正規表現にマッチする文字列を出力することはできない。
文字認識後に、人間が認識結果を修正する場合がある。出力されない場合（リジェクトされる場合）、人間は「横浜」と２文字を入力する必要がある。ところが、「横」という文字は文字認識結果として存在している。「横」だけでも出力できれば、人間は、「浜」の１字だけを入力すればよいことになる。
パス限定処理モジュール１５０は以下の処理を行う。
（１）部分一致を検証するときに、部分一致する文字列の文字長が最長になる場合を記録しておく。文字列そのものか、パスの位置を記録しておけばよい。
（２）出力決定処理モジュール１５４０における処理において、正規表現にマッチする文字列があれば、それを出力する。
（３）出力決定処理モジュール１５４０における処理において、正規表現にマッチする文字列がない場合、部分一致文字長が最長となる文字列を出力する。
そして、文字認識結果を確認、修正する操作者には、部分一致でも出力するか否かの判断を表示装置に提示し、部分一致でも出力するが選択された場合は、（３）の処理を行うようにしてもよい。
【００７７】
出力決定処理モジュール１５４０がリンク値を用いてパスを選択する場合について説明する。
図１８は、出力決定処理モジュール１５４０内のモジュール構成例を示す説明図である。出力決定処理モジュール１５４０は、リンク値生成モジュール１８１０、パス選択モジュール１８２０を有している。
リンク値生成モジュール１８１０は、パス選択モジュール１８２０と接続されている。リンク値生成モジュール１８１０は、ノード数限定処理モジュール１５２０によって限定されたリンクによって接続されたノードの文字候補間の関係による文字列らしさを表す値に基づいて、リンク値を生成する。また、リンク値生成モジュール１８１０は、リンクを構成しているノードに対する文字らしさを表す値に基づいて、リンク値を生成するようにしてもよい。
パス選択モジュール１８２０は、リンク値生成モジュール１８１０と接続されている。パス選択モジュール１８２０は、リンク値生成モジュール１８１０によって生成されたリンク値に基づいて、ネットワーク構築処理モジュール１５１０によって生成されたネットワーク内のパスを選択する。パス選択モジュール１８２０は、ダイナミックプログラミング手法を用いて処理途中のパスを削減しながら、リンク値の和に基づいてパスを選択するようにしてもよい。
【００７８】
図１９は、リンク値生成モジュール１８１０内の構成例についての概念的なモジュール構成図である。リンク値生成モジュール１８１０は、Ｎグラム値算出モジュール１９１０、ノード値算出モジュール１９２０、リンク値算出モジュール１９３０を有している。
Ｎグラム値算出モジュール１９１０は、リンク値算出モジュール１９３０と接続されており、リンクによって接続されたノードの文字候補間の関係による文字列らしさを表す値に基づいて、リンク値を生成する。例えば、そのノードに対応する文字候補によって構成される文字列が、日本語の文章中に出現する確率をリンク値として用いる。例えば、リンクの左にあるノードと右にあるノードに対応する文字によって構成される文字列の確率は、バイグラムといわれる。また、２文字に限られず、リンクによってＮ文字以上の文字列の確率は、Ｎグラム（Ｎ＞２）といわれる。
ノード値算出モジュール１９２０は、リンク値算出モジュール１９３０と接続されており、文字候補抽出モジュール１４０からリンクの片方のノードに対応する文字候補の文字らしさを表す値である認識確度をノード値として抽出する。前述のように、ノードに対応する文字認識結果に含まれている認識確度を抽出すればよい。
リンク値算出モジュール１９３０は、Ｎグラム値算出モジュール１９１０、ノード値算出モジュール１９２０と接続されており、Ｎグラム値算出モジュール１９１０によって算出された文字列らしさを表す値をリンク値として算出してもよいし、Ｎグラム値算出モジュール１９１０によって算出された文字列らしさを表す値及びノード値算出モジュール１９２０によって算出された認識確度に基づいて（例えば、２つの値の加算等）リンク値として算出してもよい。
【００７９】
図２０は、パス選択モジュール１８２０内の構成例についての概念的なモジュール構成図である。パス選択モジュール１８２０は、重み決定モジュール２０１０、リンク重み量乗算モジュール２０２０、加算モジュール２０３０を有している。
重み決定モジュール２０１０は、リンク重み量乗算モジュール２０２０と接続されており、切出位置抽出モジュール１３０によって抽出された文字切り出し位置によって定められる距離に基づいて、重みを決定する。
また、重み決定モジュール２０１０は、切出位置抽出モジュール１３０によって抽出された文字切り出し位置の間にある画像の外接矩形の大きさに基づいて重みを決定するようにしてもよい。
また、重み決定モジュール２０１０は、切出位置抽出モジュール１３０によって抽出された文字切り出し位置の間に複数の画像がある場合は、その画像の外接矩形の大きさの和に基づいて重みを決定するようにしてもよい。なお、重み決定モジュール２０１０内のモジュール構成、処理については、図２２から図２７の例を用いて後述する。
【００８０】
リンク重み量乗算モジュール２０２０は、重み決定モジュール２０１０、加算モジュール２０３０と接続されており、リンク値生成モジュール１８１０によって生成されたリンク値に対して、重み決定モジュール２０１０によって決定された対応する重みを乗算する。
加算モジュール２０３０は、リンク重み量乗算モジュール２０２０と接続されており、リンク重み量乗算モジュール２０２０によって算出されたリンク値と重みの乗算結果を加算する。加算処理の結果は、対象としている文字列画像内の一連の文字切り出し位置毎（パス単位）となる。
したがって、リンク重み量乗算モジュール２０２０、加算モジュール２０３０の処理は、重み決定モジュール２０１０によって決定された重みに基づいて、リンク値生成モジュール１８１０によって生成されたリンク値の重み付き和を算出することとなる。
【００８１】
図２１は、出力決定処理モジュール１５４０による処理例を示すフローチャートである。
ステップＳ２１０２では、リンク値生成モジュール１８１０が、リンク値を生成する。
ステップＳ２１０４では、パス選択モジュール１８２０が、重みを決定する。
ステップＳ２１０６では、パス選択モジュール１８２０が、重み付け線形和を算出する。
ステップＳ２１０８では、パス選択モジュール１８２０が、ネットワーク内のパスを選択する。
【００８２】
次に、図２２から図２７を用いて、パス選択モジュール１８２０の重み決定モジュール２０１０による重み付け処理について説明する。
＜Ｂ１＞
図２２は、重み付けの例を示す説明図である。
ここでは、図２９に例示した「化学」という文字列画像を対象として説明する。なお、重みは画素数とする。図２２（ａ）、（ｂ）、（ｃ）に例示するように、「イ」の幅は１０画素、「ヒ」の幅は２０画素、「学」の幅は４０画素、「化」の幅は４０画素であるとする。また、文字セグメント間の空白の幅は１０画素であるとする。このとき、各パターンにおけるアーク評価値に対する重みは、図２２（ｄ）から（ｇ）の例のようになる。つまり、文字切り出し位置決定モジュール１１０によって設定された位置の候補（以下、「切り出し位置候補」ともいう）によって定められる距離が重みとなっている。なお、切り出し位置候補によって定められる距離とは、この例の場合、隣り合う切り出し位置候補の間には１つの文字画像があるとして、その文字画像の外接矩形の幅である。また、切り出し位置候補によって定められる距離を、隣り合う切り出し位置候補間の距離としてもよい。
なお、図２２（ｅ）の例に示す重みよりも、図２２（ｆ）の例に示す重みが大きくなっているが、アーク評価値（「化」、「学」のそれぞれを１つの文字とした場合の文字らしさ評価値と、「化学」を１つの文字とした場合の文字らしさ評価値）によって、図２２（ｅ）の例のパス評価値が高くなることが多い。
【００８３】
図２３は、重み決定モジュール２０１０内のモジュール構成例を示す説明図である。
重み決定モジュール２０１０は、文字切り出し間距離算出モジュール２３１０を有している。文字切り出し間距離算出モジュール２３１０は、隣り合う切り出し位置候補の間にある１つの文字画像の外接矩形の幅に基づいて、重みを決定する。また、隣り合う切り出し位置候補間の距離に基づいて、重みを決定するようにしてもよい。
【００８４】
＜Ｂ２＞
前述の＜Ｂ１＞では、文字画像の外接矩形の幅又は隣り合う切り出し位置候補間の距離をそのまま、重みとした。この場合には、内部で空白の大きな文字が必要以上に大きな重みを持つことになってしまう。
例えば、図２４に例示するように、文字切り出し間距離２４１０の内部に大きな空白を持つ文字を選択してしまうと、この重みが必要以上に大きな値となってしまう。図２４の例では、文字切り出し間距離２４１０内の画像「１      １」を文字認識した結果が「い」となる場合がある。この場合の重みの値は大きくなるので、「１      １」を１つの文字（つまり、文字認識結果が「い」）として選択されてしまうことがある。
又は、文字セグメントが重なっている場合には、必要以上に小さな重みになってしまう。図２５の例のように、文字セグメントの外接矩形が重なってしまっている場合、２つに分割した方が重みの値が大きくなってしまうため、「ＩＩ」（ローマ数字の２）ではなくて、「Ｉ」、「Ｉ」となってしまう可能性が高くなる。つまり、外接矩形幅２５１０と外接矩形幅２５２０の和は、文字切り出し間距離２５３０より大きくなってしまうので、各文字セグメントの切り出し位置が文字切り出し位置として採用されてしまうことになってしまう可能性が高いことになる。
【００８５】
そこで、文字内部（隣り合う切り出し位置候補の間にある画像）の文字セグメントの外接矩形の大きさ（横書きの文字列画像を対象としている場合は幅、縦書き文字列画像を対象としている場合は高さ）に基づいて重みを決定する。
そして、文字内部に複数の文字セグメントがある場合は、その文字セグメントの外接矩形の大きさの和に基づいて重みを決定するようにしてもよい。
図２６（ａ）、（ｂ）、（ｃ）に例示するように、「イ」の幅は１０画素、「ヒ」の幅は２０画素、「学」の幅は４０画素、「化」の幅は４０画素であるとする。また、文字セグメント間の空白の幅は１０画素であるとする。このとき、各パターンにおけるアーク評価値に対する重みは、図２６（ｄ）から（ｇ）の例のようになる。つまり、文字セグメントの外接矩形の幅（文字セグメントが複数ある場合は、その和）が重みとなっている。
【００８６】
図２７は、重み決定モジュール２０１０内のモジュール構成例を示す説明図である。
重み決定モジュール２０１０は、文字塊抽出モジュール２７１０、文字塊幅算出モジュール２７２０を有している。
文字塊抽出モジュール２７１０は、文字塊幅算出モジュール２７２０と接続されており、隣り合う切り出し位置候補の間にある文字セグメント（画素塊）を抽出する。例えば、４連結又は８連結の画素塊を文字セグメントとして抽出してもよい。また、横方向に文字のプロファイルをとるようにしてもよい。すなわち、横方向に黒画素数のヒストグラムを算出する。そして、その黒画素ヒストグラムを用いて、文字セグメントを抽出するようにしてもよい。
文字塊幅算出モジュール２７２０は、文字塊抽出モジュール２７１０と接続されており、文字塊抽出モジュール２７１０によって抽出された文字セグメントの外接矩形の大きさを算出して、重みを決定する。
【００８７】
図２８を参照して、本実施の形態の画像処理装置のハードウェア構成例について説明する。図２８に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成されるものであり、スキャナ等のデータ読み取り部２８１７と、プリンタなどのデータ出力部２８１８を備えたハードウェア構成例を示している。
【００８８】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２８０１は、前述の実施の形態において説明した各種のモジュール、すなわち、文字列抽出モジュール１２０、切出位置抽出モジュール１３０、文字候補抽出モジュール１４０、パス限定処理モジュール１５０、ネットワーク構築処理モジュール１５１０、ノード数限定処理モジュール１５２０、制御モジュール１５３０、出力決定処理モジュール１５４０、リンク値生成モジュール１８１０、パス選択モジュール１８２０、Ｎグラム値算出モジュール１９１０、ノード値算出モジュール１９２０、リンク値算出モジュール１９３０、重み決定モジュール２０１０、リンク重み量乗算モジュール２０２０、加算モジュール２０３０、文字切り出し間距離算出モジュール２３１０、文字塊抽出モジュール２７１０、文字塊幅算出モジュール２７２０等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムに従った処理を実行する制御部である。
【００８９】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）２８０２は、ＣＰＵ２８０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２８０３は、ＣＰＵ２８０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス２８０４により相互に接続されている。
【００９０】
ホストバス２８０４は、ブリッジ２８０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス２８０６に接続されている。
【００９１】
キーボード２８０８、マウス等のポインティングデバイス２８０９は、操作者により操作される入力デバイスである。ディスプレイ２８１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）などがあり、各種情報をテキストやイメージ情報として表示する。
【００９２】
ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）２８１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ２８０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクには、受け付けた画像、文字認識結果、文字列パターン、ネットワーク構造などが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。
【００９３】
ドライブ２８１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体２８１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース２８０７、外部バス２８０６、ブリッジ２８０５、及びホストバス２８０４を介して接続されているＲＡＭ２８０３に供給する。リムーバブル記録媒体２８１３も、ハードディスクと同様のデータ記録領域として利用可能である。
【００９４】
接続ポート２８１４は、外部接続機器２８１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート２８１４は、インタフェース２８０７、及び外部バス２８０６、ブリッジ２８０５、ホストバス２８０４等を介してＣＰＵ２８０１等に接続されている。通信部２８１６は、通信回線に接続され、外部とのデータ通信処理を実行する。データ読み取り部２８１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部２８１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。
【００９５】
なお、図２８に示す画像処理装置のハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図２８に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図２８に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００９６】
前述の実施の形態においては、対象として日本語の文字を示したが、中国語、英語等の文字を対象としてもよい。
前述の実施の形態においては、横書きの文字列を前提として、左が始点で右が終点であるような記述の仕方を行ってきた。しかし、前述の説明は、縦書きや、右から左に記述する文字列でも同様に成り立つ。例えば、縦書きの場合は、「左」を「上」、「右」を「下」とする変換を行えばよい。右から左に記述する文字列の場合は、「左」を「右」、「右」を「左」とする変換を行えばよい。
なお、数式を用いて説明したが、数式には、その数式と同等のものが含まれる。同等のものとは、その数式そのものの他に、最終的な結果に影響を及ぼさない程度の数式の変形、又は数式をアルゴリズミックな解法で解くこと等が含まれる。
【００９７】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、ブルーレイ・ディスク（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ（登録商標））、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ（登録商標））、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合せ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【符号の説明】
【００９８】
１１０…画像受付モジュール
１２０…文字列抽出モジュール
１３０…切出位置抽出モジュール
１４０…文字候補抽出モジュール
１５０…パス限定処理モジュール
１６０…出力モジュール
１５１０…ネットワーク構築処理モジュール
１５２０…ノード数限定処理モジュール
１５３０…制御モジュール
１５４０…出力決定処理モジュール
１８１０…リンク値生成モジュール
１８２０…パス選択モジュール
【図１】
0005942361.tif 000003
【図２】
0005942361.tif 000004
【図３】
0005942361.tif 000005
【図４】
0005942361.tif 000006
【図５】
0005942361.tif 000007
【図６】
0005942361.tif 000008
【図７】
0005942361.tif 000009
【図８】
0005942361.tif 000010
【図９】
0005942361.tif 000011
【図１０】
0005942361.tif 000012
【図１１】
0005942361.tif 000013
【図１２】
0005942361.tif 000014
【図１３】
0005942361.tif 000015
【図１４】
0005942361.tif 000016
【図１５】
0005942361.tif 000017
【図１６】
0005942361.tif 000018
【図１７】
0005942361.tif 000019
【図１８】
0005942361.tif 000020
【図１９】
0005942361.tif 000021
【図２０】
0005942361.tif 000022
【図２１】
0005942361.tif 000023
【図２２】
0005942361.tif 000024
【図２３】
0005942361.tif 000025
【図２４】
0005942361.tif 000026
【図２５】
0005942361.tif 000027
【図２６】
0005942361.tif 000028
【図２７】
0005942361.tif 000029
【図２８】
0005942361.tif 000030
【図２９】
0005942361.tif 000031
【図３０】
0005942361.tif 000032
【図３１】
0005942361.tif 000033
【図３２】
0005942361.tif 000034
【図３３】
0005942361.tif 000035
【図３４】
0005942361.tif 000036
【図３５】
0005942361.tif 000037
【図３６】
0005942361.tif 000038