文字認識用コンピュータプログラム、文字認識装置及び文字認識方法
【課題】画像上の文字列に含まれる文字の認識結果に誤りがある場合でも、その文字列を正確に認識しつつ、演算量を削減可能な文字認識用コンピュータプログラムを提供する。
【解決手段】文字認識用コンピュータプログラムは、文字列を撮影した画像上の文字区間を検出して文字区間に対応するパスの集合である候補文字ラティスを求め、パスごとに候補文字を少なくとも一つ求め、互いに排他的なパスが排他的でなくなるように修正した候補文字ラティスにおいて連続するパスに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検出してその単語の位置を表す単語パスを候補文字ラティスに追加し、検出された単語の評価値を求め、文字列全体に対応する一列に連続した単語パス及びパスの配列のうちで評価値の合計値が最も高い配列に含まれる単語と候補文字の組み合わせを画像上の文字列として推定することをコンピュータに実行させる。
【解決手段】文字認識用コンピュータプログラムは、文字列を撮影した画像上の文字区間を検出して文字区間に対応するパスの集合である候補文字ラティスを求め、パスごとに候補文字を少なくとも一つ求め、互いに排他的なパスが排他的でなくなるように修正した候補文字ラティスにおいて連続するパスに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検出してその単語の位置を表す単語パスを候補文字ラティスに追加し、検出された単語の評価値を求め、文字列全体に対応する一列に連続した単語パス及びパスの配列のうちで評価値の合計値が最も高い配列に含まれる単語と候補文字の組み合わせを画像上の文字列として推定することをコンピュータに実行させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、媒体に表された文字列を撮影した画像から、その文字列に含まれるそれぞれの文字を認識する文字認識用コンピュータプログラム、文字認識装置及び文字認識方法に関する。
【背景技術】
【０００２】
近年、光学文字認識（Optical Character Recognition, OCR）と呼ばれる、紙またはディスプレイなどの媒体上に表された文字列を撮影した画像を解析することによってその文字列を認識し、電子データ化する文字認識技術が利用されている。このような文字認識技術において、認識された個々の文字の組合せに対して、単語または文章としての整合性を検証することで、認識精度を向上することが検討されている（例えば、特許文献１〜３を参照）。
【０００３】
例えば、特許文献１に開示された文書認識装置は、画像上の各文字パターンに対して認識候補文字群を求め、各文字パターンの認識候補文字群と町域名辞書とを照合することにより町域名を認識する。
【０００４】
また、特許文献２に開示された文字認識装置は、個々の文字パターンを文字認識して複数の候補文字と各候補文字の確信度を求める。またこの文字認識装置は、候補文字の列の中から単語を検索し、検索された単語の生起確率を求める。そしてこの文字認識装置は、個々の文字の確信度と文字n-gram確率と単語の生起確率とを統合して最適な候補文字列を選択する。
【０００５】
また、特許文献３に開示された検索方法は、検索文字列に含まれる第１の文字とその第１の文字に対応する第２の文字に置き換えた派生文字列を生成し、検索対象文書から、検索文字列及び派生文字列を検索する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−１４８９０６号公報
【特許文献２】特開平１１−３２８３１６号公報
【特許文献３】特開２０１０−２２５１３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、文字認識技術では、文字列中の個々の文字を認識する際に、一つの文字を二つの文字として誤認識することで、本来存在しないはずの文字が挿入されてしまったり、あるいは、本来存在しているはずの文字が欠落してしまうことがある。例えば、「動」という一つの文字が、「重」と「力」という二つの文字として誤認識されてしまうことがある。このような場合、認識された個々の文字を連結した文字列の長さは、本来の文字列の長さと異なることになる。そのため、特許文献１または特許文献２に開示された技術では、検索対象となる辞書において、認識された文字列と一致する単語を見つけることができなくなるおそれがあった。
【０００８】
一方、特許文献３に開示された技術では、認識された一つの文字を予め登録された誤認識パターンに対応する複数の文字に置換したり、あるいは認識された複数の文字を一つの文字に置換することで派生文字列が生成される。そのため、この技術は、個々の文字を誤認識することで、認識された文字列の長さが本来の文字列の長さと異なる場合でも、正確に文字列を認識できる。
【０００９】
しかしながら、特許文献３に開示された技術では、認識対象となる文字列が長くなるほど、派生文字列の数も増えることになる。その結果、検索対象文書から、検索文字列及び派生文字列を検索するのに要する演算量が膨大となり、検索結果が得られるまでに要する時間も長くなってしまうおそれがあった。
【００１０】
そこで、本明細書は、画像上の文字列に含まれる個々の文字の認識結果に誤りがある場合でも、その文字列を正確に認識できるとともに、文字列の認識に要する演算量を削減可能な文字認識用コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
一つの実施形態によれば、文字認識用コンピュータプログラムが提供される。この文字認識用コンピュータプログラムは、媒体上に表された複数の文字を含む文字列を撮影した画像から、複数の文字のそれぞれごとに、その文字が写っていると推定される画像上の文字区間を検出し、複数の文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求め、複数のパスのそれぞれについて、そのパスに対応する文字区間に写っている文字の候補である候補文字を少なくとも一つ求め、候補文字ラティスに含まれる複数のパスのうち、第１のパスと、その第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、第１のパスの候補文字及び第２のパスの候補文字を含み、かつ、第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは第１のパスが上記の２以上の連続したパスの間に挿入されるように候補文字ラティスを修正し、単語辞書に登録された複数の単語のうち、修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を文字列に含まれる可能性のある単語として検出し、検出された単語の画像上の文字列中の位置を表す単語パスを候補文字ラティスに追加した候補文字及び単語ラティスを求め、候補文字及び単語ラティスにおいて、単語パスごとに、その単語パスに対応する単語が文字列に含まれる確からしさを表す評価値を求め、候補文字及び単語ラティスに含まれる単語パス及びパスの中から選択した文字列全体に対応する一列に連続した単語パス及びパスの配列ごとに評価値の合計値を求め、その合計値が最も高い配列に含まれる単語パス及びパスの順序に従って整列されたその単語パス及びパスに対応する単語と候補文字の組み合わせを画像上の文字列として推定することをコンピュータに実行させる命令を有する。
【００１２】
本発明の目的及び利点は、請求項において特に指摘されたエレメント及び組み合わせにより実現され、かつ達成される。
上記の一般的な記述及び下記の詳細な記述の何れも、例示的かつ説明的なものであり、請求項のように、本発明を制限するものではないことを理解されたい。
【発明の効果】
【００１３】
ここに開示される文字認識用コンピュータプログラムは、画像上の文字列に含まれる個々の文字の認識結果に誤りがある場合でも、その文字列を正確に認識できるとともに、文字列の認識に要する演算量を削減できる。
【図面の簡単な説明】
【００１４】
【図１】一つの実施形態による文字認識装置の概略構成図である。
【図２】処理部の機能を示すブロック図である。
【図３】画像に写った文字列及びその文字列に対して検出された文字区間の一例を示す図である。
【図４】図３に示した文字列に対応する候補文字ラティスの一例を示す図である。
【図５】他の文字列に対する候補文字ラティスの一例を示す図である。
【図６】候補文字ラティス修正処理の一例の動作フローチャートである。
【図７】候補文字ラティス修正処理の他の一例の動作フローチャートである。
【図８】DPマッチングを用いた、最適パスの探索手順の説明図である。
【図９】図３に示した文字列に対して、検出された単語のパスを追加した候補文字・単語ラティスの一例を示す図である。
【図１０】文字認識処理の動作フローチャートである。
【発明を実施するための形態】
【００１５】
以下、図を参照しつつ、一つの実施形態による、文字認識装置について説明する。この文字認識装置は、紙あるいはディスプレイの画面などの媒体上に表された複数の文字を含む文字列を撮影した画像から、その文字列を認識して電子データ化する。そのために、この文字認識装置は、個々の文字が写っている文字区間に対応する、その文字区間の相対的な位置関係を表すパスの集合である候補文字ラティスを生成する。この文字認識装置は、演算量の削減を図るために、候補文字ラティスに含まれる、一つのパスが他のパスに対して少なくとも一部が重複しているときに、その重複を無くすように何れかのパスを修正することで、単語を検索する際のパスの組み合わせの数を削減する。さらにこの文字認識装置は、単語を検索する際に、パスごとの文字の複数の候補の組合せに対するあいまい検索を行うことで、個々の文字の誤認識により文字列中に含まれる可能性の有る単語が検出されなくなることを防止して、文字列の認識精度の向上を図る。
【００１６】
図１は、一つの実施形態による文字認識装置の概略構成図である。文字認識装置１は、画像取得部１１と、出力部１２と、記憶部１３と、記憶媒体アクセス装置１４と、処理部１５とを有する。さらに文字認識装置１は、複数の操作ボタンといった入力装置と、電子データ化された文字列を表示する液晶ディスプレイなどの表示装置を有してもよい。処理部１５は、画像取得部１１、出力部１２、記憶部１３及び記憶媒体アクセス装置１４と、例えば、バスを介して接続される。
【００１７】
画像取得部１１は、例えば、媒体に表された文字列を撮影するデジタルカメラ、あるいはスキャナを有する。そして画像取得部１１は、その文字列が写った画像を生成し、その画像を処理部１５へ出力する。
【００１８】
あるいは、画像取得部１１は、文字認識装置１を、デジタルカメラまたはカメラ付き携帯電話などの画像入力装置（図示せず）と接続するための通信インターフェース及びその制御回路を有してもよい。そのような通信インターフェースは、例えば、Universal Serial Bus（ユニバーサル・シリアル・バス、USB）などの周辺機器接続用の通信規格に従ったインターフェースとすることができる。
あるいは画像取得部１１は、イーサネット（登録商標）などの通信規格に従った通信ネットワークに接続するための通信インターフェース及びその制御回路を有してもよい。
この場合には、画像取得部１１は、画像入力装置または通信ネットワークに接続された他の機器から、文字列が写った画像を取得し、その画像を処理部１５へ渡す。
【００１９】
出力部１２は、例えば、文字認識装置１を他の機器と接続するための通信インターフェース及びその制御回路を有する。そのような通信インターフェースは、USBなどの周辺機器接続用の通信規格、あるいはイーサネット（登録商標）などの通信規格に従ったインターフェースとすることができる。
出力部１２は、画像に写った文字列を処理部１５が認識することにより生成された、電子データ化された文字列を処理部１５から受け取り、その電子データ化された文字列を他の機器へ出力する。なお、画像取得部１１と出力部１２とは、一体化されていてもよい。
【００２０】
記憶部１３は、例えば、読み書き可能な半導体メモリと読み出し専用の半導体メモリとを有する。そして記憶部１３は、処理部１５上で実行されるコンピュータプログラム、及び画像上の文字列を認識するために用いられる各種の情報、例えば、検索対象となる複数の単語が登録された単語辞書、パスごとの候補文字及び候補文字ラティスを記憶する。また記憶部１３は、認識対象となる文字列が写った画像を記憶してもよい。
【００２１】
記憶媒体アクセス装置１４は、例えば、磁気ディスク、半導体メモリカード及び光記憶媒体といった記憶媒体１６にアクセスする装置である。記憶媒体アクセス装置１４は、例えば、記憶媒体１６に記憶された、処理部１５上で実行される文字認識用コンピュータプログラムを読み込み、処理部１５に渡すか、記憶部１３に記憶させる。また記憶媒体アクセス装置１４は、処理部１５により生成された、電子データ化された文字列を記憶媒体１６に書き込んでもよい。
【００２２】
処理部１５は、１個または複数個のプロセッサ及びその周辺回路を有する。そして処理部１５は、複数の文字を含む文字列が写った画像から、その文字列に含まれる各文字を認識し、各文字に対応する文字コードを文字列の先頭から順に並べることで電子データ化された文字列を生成する。
【００２３】
図２は、処理部１５の機能を示すブロック図である。処理部１５は、文字区間検出部２１と、候補文字ラティス生成部２２と、候補文字抽出部２３と、候補文字ラティス修正部２４と、単語検索部２５と、推定部２６とを有する。処理部１５が有するこれらの各部は、例えば、処理部１５が有するプロセッサ上で実行されるコンピュータプログラムによって実装される機能モジュールである。あるいは、処理部１５が有するこれらの各部は、それぞれの機能を実現する回路が集積された集積回路として文字認識装置１に実装されてもよい。
【００２４】
文字区間検出部２１は、画像上に写った文字列に含まれる複数の文字のそれぞれごとに、その文字が写っていると推定される区間である文字区間を検出する。
【００２５】
本実施形態では、紙などの媒体に印刷された文字列のように、白い背景上に文字が黒く表現されているものを撮影した画像において、各画素の値は0〜255の範囲内の値を持ち、濃度が濃いほど、画素値も高いとする。なお、ディスプレイの画面に表示された文字列のように、背景の輝度よりも文字の輝度の方が高い場合には、輝度が高いほど、画素値も高くなるように画像は生成されてもよい。また認識対象である文字列は、いわゆる横書きの文字列であり、画像上で水平方向に沿っているとする。なお、認識対象の文字列が、いわゆる縦書きの文字列である場合には、下記の説明における水平方向と垂直方向とを入れ替えればよい。
【００２６】
上記のように、本実施形態では、画像上で文字が写っている画素の値は、文字が写っていない画素の値よりも高い。そのため、文字間の区切りに相当する画素の値の平均値は、文字が写っている画素の値の平均値よりも低くなる。そこで、文字区間検出部２１は、画像中の一行の文字列に相当する領域に含まれる垂直方向のラインごとに、画素値の合計を求め、その合計値をその垂直ラインに対応する水平位置における画素値の投影値とする。そして文字区間検出部２１は、投影値が所定の閾値以下となる位置を、文字の区切りとする。なお、所定の閾値は、例えば、投影値の合計を水平方向の画素数で割ることにより求めた投影値の平均値に所定の係数を乗じた値に設定される。なお、所定の係数は、1以下の正の値、例えば、0.5である。なお、文字区間検出部２１は、特開平２−２１７９７８号公報に開示されている技術を用いて文字間の区切りを検出してもよい。また、文字区間検出部２１は、画像の各画素を、文字が写っている文字画素と文字が写っていない背景画素とに２値化し、垂直方向のラインごとに文字画素の数を集計し、その文字画素の数を投影値としてもよい。この場合、画素を２値化するための閾値は、例えば、画像全体の画素値の平均値、あるいは、画素値の分布に対して判別分析することにより設定されてもよい。
【００２７】
文字区間検出部２１は、画像を、水平方向に隣接する二つの文字間の区切りで挟まれた区間のそれぞれを、文字区間とする。文字区間検出部２１は、文字区間ごとに一意な識別番号を割り当て、その一意な識別番号とともに、文字区間の左端と右端の水平方向の座標を記憶部１３に記憶する。
【００２８】
なお、画像上の複数の行にわたって文字列が写っていることもある。そこで、画像上に複数の文字列が写っている可能性がある場合には、文字区間検出部２１は、上記の文字間の区切りを検出する前に、行間の区切りを検出してもよい。この場合には、文字区間検出部２１は、画像中の水平方向のラインごとに、画素値の合計を求め、その合計値をその水平ラインに対応する垂直位置における画素値の投影値とする。そして文字区間検出部２１は、投影値が極小値かつ行区切り検出用の閾値以下となる位置を、行の区切りとする。なお、行区切り検出用の閾値は、例えば、水平方向のラインごとの投影値の合計を垂直方向の画素数で割ることにより求めた投影値の平均値に所定の係数（例えば、0.5）を乗じた値に設定される。文字区間検出部２１は、画像を、垂直方向に隣接する二つの行の区切りで挟まれた領域ごとに分割し、その分割された画像を一つの文字列を表す画像とする。そして文字区間検出部２１は、個々の文字列を表す画像ごとに、上記のように文字間の区切りを検出することで文字区間を検出する。
【００２９】
また、文字列を撮影するカメラと、その文字列との位置関係によっては、文字列の行方向と、画像の水平方向とが一致しないことがある。そこで、文字区間検出部２１は、例えば、画像を、所定角度（例えば、5度）ずつ、アフィン変換によって回転し、回転した画像において水平方向のラインごとに投影値を求めてもよい。この場合、文字区間検出部２１は、投影値が極小値かつ、所定の閾値以下となるラインの数が最も多いときの回転角の画像を用いて各文字列を検出した後に、文字列ごとに文字区間を検出してもよい。
【００３０】
さらに、文字のなかには、偏と旁からなる漢字のように、水平方向に沿って複数の分離した構成要素を持つ文字が含まれる。このような文字が文字列中に含まれていると、文字区間が文字の個々の構成要素ごとに検出されるおそれがある。
【００３１】
図３は、画像に写った文字列及びその文字列に対して検出された文字区間の一例を示す図である。図３に示された「運動会の始まり」という文字列３００に対して各垂直ラインの投影値を表すグラフ３１０が、文字列３００の下方に示されている。また各点線３２０は、検出された文字間の区切りを表す。例えば、文字「動」に対して、二つの文字区間３３１、３３２が設定されていることが分かる。同様に、文字「の」、「始」及び「り」に対しても、それぞれ二つの文字区間が設定されている。
【００３２】
そこで、文字区間検出部２１は、検出された全ての文字区間のうち、一つの文字の一部に対応する可能性のある文字区間を抽出する。そのために、文字区間検出部２１は、検出された全ての文字区間の水平方向の幅の平均値または最頻値を基準文字幅として算出する。そして文字区間検出部２１は、連続する複数の文字区間の組のうち、その組に含まれる各文字区間の水平方向の幅の合計が基準文字幅未満となる組を連結したものも、一つの文字区間とする。
【００３３】
候補文字ラティス生成部２２は、複数の文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを生成する。そのために、候補文字ラティス生成部２２は、検出された全ての文字区間について、その文字区間の左端の座標及び右端の座標を比較して画像の左端側から順に並べることで候補文字ラティスを生成する。
【００３４】
図４は、図３に示された文字列３００に対応する候補文字ラティスの一例を示す図である。候補文字ラティス４００は、１６個のパスを有する。個々のパスは矢印で表されており、パスの上にそのパスの識別番号、すなわち、そのパスに対応する文字区間の識別番号が示されている。また、個々のパスに対応する文字及び文字の一部の構成要素が、パスの上方または下方に示されている。例えば、パス１は文字「運」に対応する。またパス２、パス３は、それぞれ、文字「動」の偏と旁に対応している。一方、パス２とパス３が統合されたパス２０は、文字「動」に対応している。
【００３５】
候補文字抽出部２３は、個々のパスに対応する文字区間に写っている文字の候補である候補文字を少なくとも一つ抽出する。例えば、候補文字抽出部２３は、画像から、個々の文字区間に相当する画像の一部をそれぞれ文字画像として切り出し、その文字画像を２値化する。なお、文字画像を２値化するための閾値は、例えば、その文字画像の平均画素値とすることができる。そして候補文字抽出部２３は、２値化された文字画像と、個々の文字の形を表すテンプレートとの間でテンプレートマッチングを実行することにより、文字画像とテンプレート間の認識距離を求める。なお、テンプレートは、例えば、対応する文字のストロークが写っている画素の値が'255'であり、その他の画素の値が'0'である２値画像とすることができる。そして各テンプレートは、予め記憶部１３に記憶される。また一つの文字に対して、書体またはサイズが異なる複数のテンプレートが準備されてもよい。認識距離は、例えば、２値化された文字画像とテンプレート間のハミング距離とすることができる。この場合、認識距離が小さいほど、テンプレートに表された文字がその文字画像に写っている可能性が高い。あるいは、候補文字抽出部２３は、認識距離の代わりに、文字画像とテンプレート間の相互相関値を求めてもよい。この場合には、総合相関値が高いほど、テンプレートに表された文字がその文字画像に写っている可能性が高い。
【００３６】
候補文字抽出部２３は、パスごとに、認識距離が小さい方から順に所定数のテンプレートを抽出し、抽出したテンプレートに対応する文字をそのパスの候補文字とする。そして候補文字抽出部２３は、抽出した各候補文字に対して、認識距離が短い方から順に順位を付す。なお、所定数は、例えば、１〜５のうちの何れかに設定される。あるいは、候補文字抽出部２３は、認識距離が所定距離以下となるテンプレートを全て抽出し、抽出したテンプレートに対応する文字をそのパスの候補文字としてもよい。所定距離は、例えば、テンプレート中に含まれる画素の7割〜8割が文字画像の画素と一致したときの認識距離とすることができる。この場合、候補文字抽出部２３は、認識距離が所定距離以下となるテンプレートがないパスについては、認識距離が最小となるテンプレートに対応する文字をそのパスの候補文字とすることが好ましい。
なお、候補文字抽出部２３は、画像上に写っている文字を認識する他の公知技術を用いて、パスごとの候補文字を求めてもよい。但しこの場合も、候補文字ごとに、そのパスに対応する文字区間に写っている可能性が高い方から順に順位が付されることが好ましい。
【００３７】
再度図４を参照すると、パスごとに、３個の候補文字が示されている。例えば、パス１に対して、'運'、'連'、'達'という３個の候補文字が示されている。
候補文字抽出部２３は、パスごとに抽出された候補文字を表すコードを、その候補文字に対応する順位とともに、そのパスと関連付けて記憶部１３に記憶する。
【００３８】
再度図４を参照すると、候補文字ラティス４００には、文字列３００全体に対応する一列に連続したパスの配列が複数存在する。そして、少なくとも一部が重なっているパス同士は排他的であり、同一のパスの配列には含まれない。例えば、パス２及びパス３が文字列３００全体に対応するパスの配列の一部として選択されると、パス２０はそのパスの配列には含まれない。逆に、パス２０が文字列３００全体に対応するパスの配列の一部として選択されると、パス２及びパス３はそのパスの配列には含まれない。
【００３９】
図５は、他の文字列に対する候補文字ラティスの一例を示す図である。図５に示す例では、「認知」という文字列５００に対して、x2〜x6という5点の文字間の区切りが検出されている。またx1、x7は、それぞれ、文字列５００の左端と右端に対応する。この例では、文字「認」、「知」それぞれの偏と旁の境界も文字間の区切りとして検出されている。そのため、文字列５００には二文字しか含まれていないにもかかわらず、文字列５００に対応する候補文字ラティス５１０は、8個のパスA1〜A8を含んでいる。したがって、排他的なパスの組（例えば、パスA1、A4とパスA6、パスA6とパスA7など）も多数存在する。その結果として、文字列５００全体に対応する、一列に連続したパスの配列も多数存在する。
【００４０】
図４及び図５に示されるように、排他的なパスの組が増えると、文字列全体に対応するパスの配列の数も増加する。そして、文字列に含まれる単語の検索に失敗することを防止するためには、パスの配列ごとに単語が検索されることになるので、パスの配列の数が増えるほど、単語検索に要する演算量も増大する。
【００４１】
そこで、候補文字ラティス修正部２４は、画像に写った文字列全体に対応する一列に連続するパスの配列の数を削減するよう、排他的なパスの組に含まれるパスを修正することにより、候補文字ラティスを修正する。本実施形態では、候補文字ラティス修正部２４は、以下の条件を満たすように候補文字ラティスを修正する。
（１）互いに排他的でない複数のパス、すなわち、文字列全体に対応する一列に連続するパスの同一の配列に含まれることが可能なパスの組については、候補文字ラティス修正部２４は、それら複数のパスの順序を維持し、かつ、排他的でない状態を保つ。
（２）互いに排他的な複数のパスについては、候補文字ラティス修正部２４は、長い方のパスを短い方のパスと一致させるよう修正した上で統合する。ただし、統合することによって（１）の条件が満たされなくなる場合には、候補文字ラティス修正部２４は、長い方のパスを、そのパスに対して排他的なパスに隣接するように修正する。
（３）候補文字ラティス修正部２４は、長い方のパスに対して排他的な相対的に短いパスが複数存在する場合には、長い方のパスをその複数の相対的に短いパスの何れと統合してもよい。あるいは、候補文字ラティス修正部２４は、長い方のパスを複製して、複数の相対的に短いパスのそれぞれと統合してもよい。
（４）候補文字ラティス修正部２４は、複数のパスを統合する際、各パスに対応する文字区間及び候補文字を、統合されたパスに対応付ける。
【００４２】
図６は、候補文字ラティス修正部２４により実行される、上記の各条件を満たしつつ、候補文字ラティスを修正するための候補文字ラティス修正処理の一例の動作フローチャートである。また以下の説明では、理解を容易にするために、適宜図５に示された候補文字ラティス５００を参照する。
【００４３】
候補文字ラティス修正部２４は、複数のパスのうち、自身に対応する文字区間よりも短い文字区間に対応する他のパスと重ならないパスを確定グループαに分類する（ステップＳ１０１）。候補文字ラティス修正部２４は、確定グループαに分類されなかったパスを未確定グループβに分類する（ステップＳ１０２）。
【００４４】
再度図５を参照すると、候補文字ラティス５００に含まれる各パスには、それぞれのパスに対応する文字区間が短い方から順に識別番号A1〜A8が付されている。そしてパスA1〜パスA4は、自身の文字区間よりも短い文字区間に対応する他のパスと重ならない。そのため、パスA1〜A4は確定グループαに分類される。一方、パスA5〜A8は、自身の文字区間よりも短い文字区間に対応する他のパスと少なくとも一部が重なっている。例えば、パスA5の文字区間は、パスA2及びA3の文字区間と重なっており、パスA6の文字区間は、パスA1及びA4の文字区間と重なっている。そのため、パスA5〜A8は未確定グループβに分類される。
【００４５】
次に、候補文字ラティス修正部２４は、確定グループα内のパスを、文字列の先頭から終端へ向かう座標順にソートして修正パス列P=｛p[1],p[2],....｝を生成する。さらに候補文字ラティス修正部２４は、修正パス列P内の各修正パスp[k]に対応する、すなわち、修正パスp[k]に対して排他的なパスの集合である他の候補パス群｛Qk｝を空集合として初期化する（ステップＳ１０３）。例えば、候補文字ラティス５００について、修正パス列Pは、下記の表１に示されるように、パスA1〜パスA4を、A1、A4、A3、A2の順に含む。
【表１】
なお、表１には、各修正パスp[k]について、元の候補文字ラティスにおけるパスの識別番号、パスに対応する文字区間（すなわち、その文字区間の左端及び右端の座標）、そのパスについて抽出された候補文字及び他の候補パス群が対応付けられる。例えば、修正パスp[1]には、識別番号A1、パスA1の文字区間[x1,x2]、候補文字「言」が対応付けられている。なお、候補文字が複数ある場合には、すべての候補文字が対応付けられる。例えば、パスA1に対して３個の候補文字「言」、「吉」、「忘」が抽出されている場合、これらの候補文字すべてが修正パスp[1]に対応付けられる。
また、この時点では、修正パス列Pに含まれる修正パスp[k]と未確定グループに属するパスとの位置関係は調べられていないので、各修正パスについての他の候補パス群は空集合となっている。
【００４６】
候補文字ラティス修正部２４は、未確定グループβに属するパスの何れかを注目パスAとして選択する（ステップＳ１０４）。なお、候補文字ラティス修正部２４は、例えば、未確定グループβに属するパスの中で対応する文字区間が最も短いパスから順に注目パスAとして選択する。あるいは、候補文字ラティス修正部２４は、例えば、未確定グループβに属するパスの中で最も文字列の先頭に近いパスから順に注目パスAとして選択してもよい。そして候補文字ラティス修正部２４は、修正パス列Pに含まれる修正パスp[k]のうち、注目パスAと少なくとも一部が重なる修正パスp[j]の何れかを選択する（ステップＳ１０５）。候補文字ラティス修正部２４は、修正パスp[j]に対応する他の候補パスのうちで注目パスAと重ならないパスがあるか否か判定する（ステップＳ１０６）。修正パスp[j]に対応する他の候補パスが無いか、または、他の候補パスのうちで注目パスAと重ならないパスがなければ（ステップＳ１０６−Ｎｏ）、候補文字ラティス修正部２４は、p[j]に対応する他の候補パス群｛Qk｝にパスAを追加する（ステップＳ１０７）。
【００４７】
例えば、注目パスAがパスA5であれば、修正パスp[3]、すなわちパスA3または修正パスp[4]、すなわちパスA2が選択されることになる。例えば、修正パスp[3]が選択されたとすると、この時点では、修正パスp[3]に対応する他の候補パスは存在しない。したがって、修正パスp[3]の他の候補パス群にパスA5が追加される。
【００４８】
ステップＳ１０７の後、あるいは、修正パスp[j]に対応する他の候補パスがあり、かつ、他の候補パスのうちで注目パスAと重ならないパスがある場合（ステップＳ１０６−Ｙｅｓ）、候補文字ラティス修正部２４は注目パスAと重なる他の修正パスが有るか否か判定する（ステップＳ１０８）。注目パスAと重なる他の修正パスが有れば（ステップＳ１０８−Ｙｅｓ）、候補文字ラティス修正部２４は、ステップＳ１０５以降の処理を繰り返す。
【００４９】
例えば、注目パスとしてのパスA5に対して最初に修正パスp[3]が選択されていると、候補文字ラティス修正部２４は、次に修正パスp[4]、すなわち、パスA2を選択する。この時点では、修正パスp[4]に対応する他の候補パスは存在しない。したがって、修正パスp[4]の他の候補パス群にパスA5が追加される。
【００５０】
一方、注目パスAと重なる他の修正パスがなければ（ステップＳ１０８−Ｎｏ）、候補文字ラティス修正部２４は、注目パスAは何れかの修正パスp[j]の他の候補パス群｛Qj｝に追加されたか否か判定する（ステップＳ１０９）。注目パスAが何れかの修正パスp[j]の他の候補パス群｛Qj｝に追加されていれば（ステップＳ１０９−Ｙｅｓ）、候補文字ラティス修正部２４は、未確定グループβ内に未注目のパスが残っているか否か判定する（ステップＳ１１１）。そして未注目のパスが残っていれば（ステップＳ１１１−Ｙｅｓ）、候補文字ラティス修正部２４は、ステップＳ１０４以降の処理を繰り返す。
【００５１】
例えば、パスA5の後、パスA6、A7が順次注目パスとして選択され、ステップＳ１０４〜Ｓ１１１の処理が行われたとする。この時点での修正パス列Pの対応表は以下のようになる。
【表２】
図５及び表２に示されるように、パスA6、パスA7は、修正パスp[1]、p[2]に対して、他の候補パスが無いか、あるいは他の候補パス群内にパスA6、A7と重ならないパスは無いので、修正パスp[1]、p[2]の他の候補群｛Q1｝、｛Q2｝にそれぞれ追加されている。
【００５２】
一方、ステップＳ１０９にて、注目パスAが何れの修正パスp[j]の他の候補パス群｛Qj｝にも追加されていなければ（ステップＳ１０９−Ｎｏ）、候補文字ラティス修正部２４は、修正パス列Pに対して、パスAと重なる複数の修正パスの間に、新たな修正パスとしてパスAを追加する（ステップＳ１１０）。
【００５３】
例えば、図５及び表２を参照すると、最後の未注目パスであるパスA8が注目パスに設定されたとすると、パスA8は修正パスp[2]、すなわちパスA4及び修正パスp[3]、すなわちパスA3と重なっている。しかし、修正パスp[2]の他の候補群｛Q2｝には、パスA8と重ならないパスA7が含まれている。同様に、修正パスp[3]の他の候補群｛Q3｝にも、パスA8と重ならないパスA5が含まれている。そのため、パスA8は、何れの修正パスp[j]の他の候補群にも追加されない。そして、パスA8の文字区間の途中に、修正パスp[2]に対応する文字区間と修正パスp[3]に対応する文字区間の境界が位置している。そのため、パスA8は、修正パスp[2]と修正パスp[3]の間に追加される。
【００５４】
ステップＳ１１０の後、候補文字ラティス修正部２４は、未確定グループβ内に未注目のパスが残っているか否か判定する（ステップＳ１１１）。そして未注目のパスが残っていれば（ステップＳ１１１−Ｙｅｓ）、候補文字ラティス修正部２４は、ステップＳ１０４以降の処理を繰り返す。
一方、未注目のパスが残っていなければ（ステップＳ１１１−Ｎｏ）、候補文字ラティス修正部２４は、他の候補パス群｛Qk｝についての候補文字を全て修正パスp[k]の候補文字として追加する（ステップＳ１１２）。そして修正パス列Pが、修正候補文字ラティスとなる。この場合、他の候補パス群｛Qk｝が空集合でない修正パスp[k]は、その修正パスp[k]に対応する確定グループα内のパス及び他の候補パス群｛Qk｝に含まれるパスを置換するものとなる。
その後、候補文字ラティス修正部２４は、候補文字ラティス修正処理を終了する。
【００５５】
表３は、最終的に作成された修正候補文字ラティスのパス及び候補文字の一覧である。
【表３】
修正候補文字ラティスの各パスには、そのパスに関連付けられた元の候補文字ラティスのパスの識別番号及びそのパスの候補文字がその順位とともに関連付けられる。表３に示されるように、修正候補文字ラティスに含まれる統合されたパスについての候補文字の数は元の個々のパスについての候補文字の数よりも増えるものの、修正候補文字ラティスは互いに排他的なパスの組を含んでいない。そのため、修正候補文字ラティスは、元の候補文字ラティスよりも簡単な構造を有している。
【００５６】
図７は、候補文字ラティス修正部２４により実行される、上記の各条件を満たしつつ、候補文字ラティスを修正するための候補文字ラティス修正処理の他の一例の動作フローチャートである。また以下の説明においても、理解を容易にするために、適宜図５に示された候補文字ラティス５００を参照する。
【００５７】
候補文字ラティス修正部２４は、候補文字ラティスに含まれるパスの境界を先頭から順に全て抽出する（ステップＳ２０１）。そして候補文字ラティス修正部２４は、（パスの境界の数-1）個の修正パスを含むパス記憶領域を記憶部１３に設定する（ステップＳ２０２）。
例えば、候補文字ラティス５００では、先頭から順にx1〜x7の7個の境界があるので、下記の表４のように、6個の修正パスを含むパス記憶領域が設定される。
【表４】
表４において、一番上の行は修正パスの先頭からの順序を表す。二番目の行は各修正パスに対応する区間の左端と右端の水平座標を表す。３番目の行は、修正パスに割り当てられた元の候補文字ラティスのパスの識別番号を表す。そして一番下の行は、修正パスに割り当てられたパスについての候補文字の集合を表す。この時点では、何れの修正パスにもパスは割り当てられていないので、下の２行は空欄となっている。
【００５８】
候補文字ラティス修正部２４は、各パスを、そのパスに対応する文字区間と修正パスの区間との重なり幅が最も大きい修正パスに割り当てる（ステップＳ２０３）。
例えば、x1=10、x2=25、x3=30、x4=40とする。この場合、パスA6は、修正パスM1[x1,x2]、M2[x2,x3]、M3[x3,x4]と重なっているが、このうち修正パスM1との重なり幅が最も大きい。そこで候補文字ラティス修正部２４は、パスA6を修正パスM1に割り当てる。
表５は、全てのパスを何れかの修正パスに割り当てたときのパス記憶領域を表す。
【表５】
なお、表５では、簡単化のために、各パスについて一つの候補文字だけが示されている。
【００５９】
候補文字ラティス修正部２４は、全てのパスが修正パスの何れかに割り当てられた後、１以上のパスが割り当てられた修正パスを先頭から順に抽出し、修正候補文字ラティスのパスとする（ステップＳ２０４）。そして候補文字ラティス修正部２４は、抽出された修正パスに割り当てられたパスの候補文字を、修正候補文字ラティスのパスの候補文字とする（ステップＳ２０５）。この例でも、複数のパスが割り当てられた修正パスは、それら複数のパスを統合し、かつそれら複数のパスを置換するものとなる。
その後、候補文字ラティス修正部２４は、候補文字ラティス修正処理を終了する。
【００６０】
例えば、表５に示されるように、修正パスM1、M3、M5、M6には１以上のパスが割り当てられている。そこで、修正パスM1、M3、M5、M6が修正候補文字ラティスのパスとして抽出される。表６は、最終的に得られる修正候補文字ラティスのパス及び候補文字の一覧である。
【表６】
【００６１】
なお、変形例によれば、ステップＳ２０３において、候補文字ラティス修正部２４は、各パスを、そのパスと少なくとも一部が重なる全ての修正パスに割り当ててもよい。この場合、例えば、パスA6は、修正パスM1〜M3にそれぞれ割り当てられる。表７は、この変形例により全てのパスが何れかの修正パスに割り当てられたときのパス記憶領域を表す。
【表７】
【００６２】
上記のように、何れの候補文字ラティス修正処理が実行されても、修正候補文字ラティスは、排他的なパスを含まないので、文字列全体に対応する一列に連続したパスの配列は一通りとなる。
【００６３】
単語検索部２５は、記憶部１３に記憶された単語辞書に登録された複数の単語のうち、修正候補文字ラティスの少なくとも一部のパスの配列に含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検出する。
本実施形態では、単語検索部２５は、単語辞書中に登録されている単語を検索するために、動的計画法（Dynamic Programming）によるマッチング手法（以下、DPマッチングと呼ぶ）を利用する。
【００６４】
図８は、本実施形態により利用されるDPマッチングを用いた、最適パスの探索手順の説明図である。図８において、検索対象単語に含まれる文字数に1加算した数を縦軸の格子数、修正候補文字ラティスの少なくとも一部に含まれるパスの数に1加算した数を横軸の格子数として、碁盤目状に格子点が配置されている。この例では、検索対象単語８１０は「運動会」であり、３個の文字を含む。そして各文字は、先頭から順に、上から順に一つの行の格子点に対応付けられている。一方、修正候補文字ラティスのパス数は４個であり、先頭のパスから終端のパスまで左側から順に一つの列の格子点に対応付けられている。また各パスには、１以上の候補文字８１１〜８１４が対応付けられている。例えば、先頭のパスには、３個の候補文字「運」、「連」、「達」が対応付けられている。各パスの候補文字の中から選択した一つの文字を先頭側のパスから順に連結して得られる文字列を、ここでは入力文字列と呼ぶ。
【００６５】
単語検索部２５は、左上端の格子点から右下端の格子点へ向かう経路のうち最適な経路を探索する。評価値として、例えば、検索対象単語と入力文字列間の編集距離、あるいは検索対象単語と入力文字列間で一致する文字の個数が用いられる。評価値として編集距離が用いられる場合、単語検索部２５は、評価値が最小となる経路を最短経路とする。この場合、左上端の格子点が最初の注目格子点となる。そして単語検索部２５は、注目格子点の右側、下側及び右下側に隣接する格子点の何れかを次の注目格子点とする。その際、現在の注目格子点から右下に隣接する注目格子点へ遷移した場合に、次の注目格子点が属する行に対応する検索対象単語の文字（例えば、上から３番目の行であれば、「動」）と、注目格子点が属する列に対応する候補文字の何れかが一致するか否か判定する。そして一致すれば、編集距離に加算されるポイントは'0'となる。しかし、一致しなければ、編集距離に加算されるポイントは'+2'となる。なお、両者が一致しないことは、検索対象単語の次の注目格子点に対応する文字が置換されたことに相当する。また、文字の置換に相当する加算ポイントは、'+1'に設定されてもよい。
【００６６】
また、現在の注目格子点に対して下側に隣接する格子点が次の注目格子点となる場合、編集距離に加算されるポイントは'+1'となる。なお、この下側への遷移は、検索対象単語中の文字の欠落に相当する。さらに、現在の注目格子点に対して右側に隣接する格子点が次の注目格子点となる場合も、編集距離に加算されるポイントは'+1'となる。なお、この右側への遷移は、検索対象単語に対する文字の挿入に相当する。
図８に示した例では、矢印で示される経路８２０が最短経路となり、検索対象単語に対応する入力文字列として「運動☆会」が選択される。なお、☆マークは、挿入された文字を表し、ここでは、右から２番目のパスに対応する候補文字「カ」、「力」、「刀」の何れかである。
【００６７】
単語検索部２５は、検索対象単語と入力文字列間の文字の再現率及び文字の適合率が所定の閾値を超えた場合、修正候補文字ラティスが表す文字列中のその入力文字列に対応する位置において検索対象単語が検出されたと判定する。
なお、文字の再現率及び文字の適合率は、例えば、次式で表される。
文字の再現率＝（入力文字列と検索対象単語間で一致する文字数）
／検索対象単語に含まれる文字数
文字の適合率＝（入力文字列と検索対象単語間で一致する文字数）
／入力文字列に含まれる文字数
また、所定の閾値は、例えば、0.6〜0.8の範囲内の何れかの値に設定される。
【００６８】
あるいは、単語検索部２５は、最短経路についての編集距離が所定の値以下である場合、その最短経路に対応する入力文字列に対応する位置において検索対象単語が抽出されたと判定してもよい。この場合、所定の値は、例えば、検索対象単語に含まれる文字数に、0.3〜0.4の範囲内の何れかの値を乗じた値とすることができる。
【００６９】
また、単語検索部２５は、他のあいまい検索手法を用いて、修正候補文字ラティスに含まれるパスの少なくとも一部の配列に含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検索してもよい。単語検索部２５は、このようなあいまい検索手法として、例えば、特開2010-225137号公報に開示されている方法を用いることができる。または、単語検索部２５は、喜田、「誤りを許したVLDCパタン照合アルゴリズム」、電子情報通信学会技術研究報告、COMP、コンピューテーション、103(622)、p61-68、2004年に記載された方法を用いることができる。
【００７０】
単語検索部２５は、単語辞書に登録された全ての単語に対して上述した処理を行って、文字列に含まれる単語を検索する。したがって、例えば、単語辞書に非常に多数の単語が登録されていると、例えば、10万個の単語が登録されていると、その全ての単語に対して上述した処理が行われることになる。
しかし、上記のように、単語検索部２５は、個々の単語について、排他的なパスを含まない修正候補文字ラティスに対してあいまい検索を行うので、パスの組み合わせが複数存在する元の候補文字ラティスに対してあいまい検索を行うよりも大幅に演算量を削減できる。そのため、単語辞書に登録されている単語の数が増えるほど、演算量の削減効果も大きくなる。また単語検索部２５は、文字の置換、挿入及び欠落の何れも許容して単語の検索を行うので、個々のパスに対する文字の誤認識が生じていたり、あるいは、検出された文字区間が誤っている場合でも、単語検索部２５は、文字列に含まれる単語を正しく検索できる。
【００７１】
単語検索部２５は、候補文字ラティスに対して、検出された単語に対応するパスである単語パスを追加する。そして得られたラティスを、以下では便宜上、候補文字・単語ラティスと呼ぶ。なお、単語検索部２５は、単語を検出する際に、DPマッチングの対象としたパスを知っているので、そのパスの位置に基づいて、単語パスを追加する位置を特定できる。さらに、単語検索部２５は、検出された単語パスのそれぞれについて、対応する単語に含まれる各文字と一致する候補文字の順位及びその候補文字に対応する元の候補文字ラティスのパスの識別番号をその単語パスと関連付ける。
【００７２】
図９は、図３に示した文字列「運動会の始まり」に対して、検出された単語のパスを追加した候補文字・単語ラティスの一例を示す図である。図９に示された候補文字・単語ラティス９００において、矢印で表されるパスのうち、パス１〜２３が文字ごとのパスであり、パス３１〜３７が追加された単語パスである。
【００７３】
推定部２６は、候補文字・単語ラティスに基づいて、画像上に写った文字列を推定する。そのために、推定部２６は、候補文字・単語ラティスに含まれる単語パスごとに、その単語パスに対応する単語の評価値を、例えば次式に従って算出する。
単語評価値＝｛Σ(1-α(Mi-1))｝n
ここで、Miは、単語検索部２５により検出された単語における先頭からi番目の文字と一致すると判定された候補文字の順位を表す。ただし、i番目の文字と一致すると判定された候補文字が無かった場合には、Miは候補文字抽出部２３が個々のパスについて抽出する候補文字の最大個数に1を加算した値に設定される。αは係数であり、Miの値が大きいほど(1-α(Mi-1))が0に近づくように、例えば、候補文字抽出部２３が個々のパスについて抽出する候補文字の最大個数の逆数以下の正の値、例えば、0.1に設定される。したがって、単語パスに対応する単語に含まれる個々の文字と一致する候補文字の順位の合計が小さいほど、単語評価値は高くなる。またnは補正係数であり、例えば、1以上の値に設定される。特に、単語に含まれる文字数が増えるほど単語評価値も高くなるようにするためには、補正係数nは、1よりも大きい値に設定されることが好ましく、例えば、2に設定される。このように補正係数を設定することで、文字数が多い単語ほど、文字列に含まれる単語であると推定され易くなる。
【００７４】
再度図９を参照すると、単語パス３１に対応する単語「運動会」について、M1=M2=1、M3=2である。そのため、α=0.1、n=2とすれば、単語評価値は8.41となる。なお、図９において、単語パス３１〜３７が表す単語と並んで表記された数値がその単語についての単語評価値である。
【００７５】
また、推定部２６は、単語パスでない、一つの文字を表すパスについての単語評価値を定数βに設定する。定数βは、例えば、0より大きく、２文字を含む単語についての単語評価値が取りうる最大値よりも小さい値、例えば、0.5に設定される。
【００７６】
推定部２６は、候補文字・単語ラティスにおいて、文字列全体に対応する、一列に連続した単語パス及びパスの配列のそれぞれについて、単語評価値の総和を、その配列に対する連結パス評価値として求める。そして推定部２６は、連結パス評価値が最大値となる配列に含まれる単語パス及びパスの順序に従って整列されたその単語パス及びパスに対応する単語と文字の列を、画像上に写っている文字列と推定する。なお、図９におけるパス５、６とパス２１のように、単語評価値の和が等しい排他的な複数のパスが存在する場合、推定部２６は、候補文字抽出部２３により求められた認識距離の和が小さい方のパスを配列に含めるように選択する。また、単語評価値が最大となる配列に含まれるパスに対して複数の候補文字が有る場合には、推定部２６は、順位が最も高い候補文字を選択する。
図９の例では、パス３１→パス２１→パス３４の順序に従って選択された配列の連結パス評価値が最大となるので、推定部２６は、それらのパスに対応する単語及び候補文字を並べた文字列「運動会の始まり」を、画像上に写っている文字列として推定する。
【００７７】
図１０は、文字認識処理の動作フローチャートである。処理部１５は、画像を受け取る度に、この文字認識処理を実行する。
文字区間検出部２１は、画像上に写った文字列から、個々の文字のそれぞれごとに、その文字が写っていると推定される文字区間を検出する（ステップＳ３０１）。さらに文字区間検出部２１は、１文字に対応する可能性の有る連続した２以上の文字区間を連結した区間も文字区間として検出する（ステップＳ３０２）。その後、候補文字ラティス生成部２２は複数の文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを生成する（ステップＳ３０３）。
また候補文字抽出部２３は、パスごとに候補文字を抽出する（ステップＳ３０４）。
【００７８】
その後、候補文字ラティス修正部２４は、互いに排他的なパスを統合するか、あるいは排他的なパスの一方の位置を修正することで修正候補文字ラティスを生成する（ステップＳ３０５）。具体的には、候補文字ラティス修正部２４は、第１のパスと、第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、第１及び第２のパスの候補文字を含み、かつ第２のパスと同一の文字区間に対応する第３のパスで置換する。あるいは、候補文字ラティス修正部２４は、第１のパスを、その連続したパスの間に挿入されるように修正する。
【００７９】
その後、単語検索部２５は、単語辞書に登録されている複数の単語のうち、修正候補文字ラティスにおいて連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検出する（ステップＳ３０６）。また、単語検索部２５は、検出された単語に相当する単語パスを候補文字ラティスに追加して候補文字・単語ラティスを生成する（ステップＳ３０７）。
推定部２６は、各パスについて求めた単語評価値の総和が最大となるパスの配列に相当する文字列を画像上に写っている文字列と推定する（ステップＳ３０８）。そして処理部１５は、推定された文字列に含まれる各文字のコードを、推定された文字列の順序に従って並べることにより、画像上に写った文字列を電子データ化する。処理部１５は、文字列を表す電子データを出力部１２を介して他の機器へ出力する。あるいは、処理部１５は、文字列を表す電子データを記憶部１３に記憶する。その後、処理部１５は、文字認識処理を終了する。なお、処理部１５は、ステップＳ３０３とステップＳ３０４の処理の順序を入れ替えてもよい。
【００８０】
以上に説明してきたように、この文字認識装置は、文字列中に含まれている単語を検索する前に、候補文字ラティスの構造を修正して互いに排他的なパスの組を無くすことで、その文字列を表すパスの配列の数を削減している。そのため、この文字認識装置は、単語検索の際の演算量を削減できるので、文字認識処理全体としての演算量も削減できる。さらにこの文字認識装置は、単語中の文字の置換、欠落または挿入を許容したあいまい検索手法により、文字列に含まれている可能性がある単語を検索する。そのため、この文字認識装置は、画像上の文字列に含まれる個々の文字の認識結果に誤りがあっても、文字列中に含まれる単語を検出できるので、その文字列を正確に認識できる。
【００８１】
なお、本発明は上記の実施形態に限られるものではない。例えば、推定部は、単語パスに対応する単語に含まれるそれぞれの文字と一致する候補文字についての認識距離の平均値が小さいほど、単語評価値を高くしてもよい。
また、文字区間検出部は、投影値に対する閾値を変更して文字の区切りを検出することによって、複数の文字区間を検出してもよい。例えば、文字区間検出部は、先ず、上記の実施形態と同様の閾値を用いて文字の区切りを検出することで、複数の文字区間を検出する。その後、文字区間検出部は、閾値をより低い値、例えば、元の閾値を1.2〜1.5で割った値に修正した後、再度各水平位置の投影値と修正後の閾値を比較して、修正後の閾値以下の投影値を持つ水平位置を文字の区切りとして再検出する。そして文字区間検出部は、再検出された文字の区切りで挟まれた区間を文字区間とする。これにより、文字の構成要素同士が近接する文字についても、その文字全体を含む文字区間が検出され易くなる。
【００８２】
ここに挙げられた全ての例及び特定の用語は、読者が、本発明及び当該技術の促進に対する本発明者により寄与された概念を理解することを助ける、教示的な目的において意図されたものであり、本発明の優位性及び劣等性を示すことに関する、本明細書の如何なる例の構成、そのような特定の挙げられた例及び条件に限定しないように解釈されるべきものである。本発明の実施形態は詳細に説明されているが、本発明の精神及び範囲から外れることなく、様々な変更、置換及び修正をこれに加えることが可能であることを理解されたい。
【符号の説明】
【００８３】
１ 文字認識装置
１１ 画像取得部
１２ 出力部
１３ 記憶部
１４ 記憶媒体アクセス装置
１５ 処理部
１６ 記憶媒体
２１ 文字区間検出部
２２ 候補文字ラティス生成部
２３ 候補文字抽出部
２４ 候補文字ラティス修正部
２５ 単語検索部
２６ 推定部
【技術分野】
【０００１】
本発明は、例えば、媒体に表された文字列を撮影した画像から、その文字列に含まれるそれぞれの文字を認識する文字認識用コンピュータプログラム、文字認識装置及び文字認識方法に関する。
【背景技術】
【０００２】
近年、光学文字認識（Optical Character Recognition, OCR）と呼ばれる、紙またはディスプレイなどの媒体上に表された文字列を撮影した画像を解析することによってその文字列を認識し、電子データ化する文字認識技術が利用されている。このような文字認識技術において、認識された個々の文字の組合せに対して、単語または文章としての整合性を検証することで、認識精度を向上することが検討されている（例えば、特許文献１〜３を参照）。
【０００３】
例えば、特許文献１に開示された文書認識装置は、画像上の各文字パターンに対して認識候補文字群を求め、各文字パターンの認識候補文字群と町域名辞書とを照合することにより町域名を認識する。
【０００４】
また、特許文献２に開示された文字認識装置は、個々の文字パターンを文字認識して複数の候補文字と各候補文字の確信度を求める。またこの文字認識装置は、候補文字の列の中から単語を検索し、検索された単語の生起確率を求める。そしてこの文字認識装置は、個々の文字の確信度と文字n-gram確率と単語の生起確率とを統合して最適な候補文字列を選択する。
【０００５】
また、特許文献３に開示された検索方法は、検索文字列に含まれる第１の文字とその第１の文字に対応する第２の文字に置き換えた派生文字列を生成し、検索対象文書から、検索文字列及び派生文字列を検索する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−１４８９０６号公報
【特許文献２】特開平１１−３２８３１６号公報
【特許文献３】特開２０１０−２２５１３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、文字認識技術では、文字列中の個々の文字を認識する際に、一つの文字を二つの文字として誤認識することで、本来存在しないはずの文字が挿入されてしまったり、あるいは、本来存在しているはずの文字が欠落してしまうことがある。例えば、「動」という一つの文字が、「重」と「力」という二つの文字として誤認識されてしまうことがある。このような場合、認識された個々の文字を連結した文字列の長さは、本来の文字列の長さと異なることになる。そのため、特許文献１または特許文献２に開示された技術では、検索対象となる辞書において、認識された文字列と一致する単語を見つけることができなくなるおそれがあった。
【０００８】
一方、特許文献３に開示された技術では、認識された一つの文字を予め登録された誤認識パターンに対応する複数の文字に置換したり、あるいは認識された複数の文字を一つの文字に置換することで派生文字列が生成される。そのため、この技術は、個々の文字を誤認識することで、認識された文字列の長さが本来の文字列の長さと異なる場合でも、正確に文字列を認識できる。
【０００９】
しかしながら、特許文献３に開示された技術では、認識対象となる文字列が長くなるほど、派生文字列の数も増えることになる。その結果、検索対象文書から、検索文字列及び派生文字列を検索するのに要する演算量が膨大となり、検索結果が得られるまでに要する時間も長くなってしまうおそれがあった。
【００１０】
そこで、本明細書は、画像上の文字列に含まれる個々の文字の認識結果に誤りがある場合でも、その文字列を正確に認識できるとともに、文字列の認識に要する演算量を削減可能な文字認識用コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
一つの実施形態によれば、文字認識用コンピュータプログラムが提供される。この文字認識用コンピュータプログラムは、媒体上に表された複数の文字を含む文字列を撮影した画像から、複数の文字のそれぞれごとに、その文字が写っていると推定される画像上の文字区間を検出し、複数の文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求め、複数のパスのそれぞれについて、そのパスに対応する文字区間に写っている文字の候補である候補文字を少なくとも一つ求め、候補文字ラティスに含まれる複数のパスのうち、第１のパスと、その第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、第１のパスの候補文字及び第２のパスの候補文字を含み、かつ、第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは第１のパスが上記の２以上の連続したパスの間に挿入されるように候補文字ラティスを修正し、単語辞書に登録された複数の単語のうち、修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を文字列に含まれる可能性のある単語として検出し、検出された単語の画像上の文字列中の位置を表す単語パスを候補文字ラティスに追加した候補文字及び単語ラティスを求め、候補文字及び単語ラティスにおいて、単語パスごとに、その単語パスに対応する単語が文字列に含まれる確からしさを表す評価値を求め、候補文字及び単語ラティスに含まれる単語パス及びパスの中から選択した文字列全体に対応する一列に連続した単語パス及びパスの配列ごとに評価値の合計値を求め、その合計値が最も高い配列に含まれる単語パス及びパスの順序に従って整列されたその単語パス及びパスに対応する単語と候補文字の組み合わせを画像上の文字列として推定することをコンピュータに実行させる命令を有する。
【００１２】
本発明の目的及び利点は、請求項において特に指摘されたエレメント及び組み合わせにより実現され、かつ達成される。
上記の一般的な記述及び下記の詳細な記述の何れも、例示的かつ説明的なものであり、請求項のように、本発明を制限するものではないことを理解されたい。
【発明の効果】
【００１３】
ここに開示される文字認識用コンピュータプログラムは、画像上の文字列に含まれる個々の文字の認識結果に誤りがある場合でも、その文字列を正確に認識できるとともに、文字列の認識に要する演算量を削減できる。
【図面の簡単な説明】
【００１４】
【図１】一つの実施形態による文字認識装置の概略構成図である。
【図２】処理部の機能を示すブロック図である。
【図３】画像に写った文字列及びその文字列に対して検出された文字区間の一例を示す図である。
【図４】図３に示した文字列に対応する候補文字ラティスの一例を示す図である。
【図５】他の文字列に対する候補文字ラティスの一例を示す図である。
【図６】候補文字ラティス修正処理の一例の動作フローチャートである。
【図７】候補文字ラティス修正処理の他の一例の動作フローチャートである。
【図８】DPマッチングを用いた、最適パスの探索手順の説明図である。
【図９】図３に示した文字列に対して、検出された単語のパスを追加した候補文字・単語ラティスの一例を示す図である。
【図１０】文字認識処理の動作フローチャートである。
【発明を実施するための形態】
【００１５】
以下、図を参照しつつ、一つの実施形態による、文字認識装置について説明する。この文字認識装置は、紙あるいはディスプレイの画面などの媒体上に表された複数の文字を含む文字列を撮影した画像から、その文字列を認識して電子データ化する。そのために、この文字認識装置は、個々の文字が写っている文字区間に対応する、その文字区間の相対的な位置関係を表すパスの集合である候補文字ラティスを生成する。この文字認識装置は、演算量の削減を図るために、候補文字ラティスに含まれる、一つのパスが他のパスに対して少なくとも一部が重複しているときに、その重複を無くすように何れかのパスを修正することで、単語を検索する際のパスの組み合わせの数を削減する。さらにこの文字認識装置は、単語を検索する際に、パスごとの文字の複数の候補の組合せに対するあいまい検索を行うことで、個々の文字の誤認識により文字列中に含まれる可能性の有る単語が検出されなくなることを防止して、文字列の認識精度の向上を図る。
【００１６】
図１は、一つの実施形態による文字認識装置の概略構成図である。文字認識装置１は、画像取得部１１と、出力部１２と、記憶部１３と、記憶媒体アクセス装置１４と、処理部１５とを有する。さらに文字認識装置１は、複数の操作ボタンといった入力装置と、電子データ化された文字列を表示する液晶ディスプレイなどの表示装置を有してもよい。処理部１５は、画像取得部１１、出力部１２、記憶部１３及び記憶媒体アクセス装置１４と、例えば、バスを介して接続される。
【００１７】
画像取得部１１は、例えば、媒体に表された文字列を撮影するデジタルカメラ、あるいはスキャナを有する。そして画像取得部１１は、その文字列が写った画像を生成し、その画像を処理部１５へ出力する。
【００１８】
あるいは、画像取得部１１は、文字認識装置１を、デジタルカメラまたはカメラ付き携帯電話などの画像入力装置（図示せず）と接続するための通信インターフェース及びその制御回路を有してもよい。そのような通信インターフェースは、例えば、Universal Serial Bus（ユニバーサル・シリアル・バス、USB）などの周辺機器接続用の通信規格に従ったインターフェースとすることができる。
あるいは画像取得部１１は、イーサネット（登録商標）などの通信規格に従った通信ネットワークに接続するための通信インターフェース及びその制御回路を有してもよい。
この場合には、画像取得部１１は、画像入力装置または通信ネットワークに接続された他の機器から、文字列が写った画像を取得し、その画像を処理部１５へ渡す。
【００１９】
出力部１２は、例えば、文字認識装置１を他の機器と接続するための通信インターフェース及びその制御回路を有する。そのような通信インターフェースは、USBなどの周辺機器接続用の通信規格、あるいはイーサネット（登録商標）などの通信規格に従ったインターフェースとすることができる。
出力部１２は、画像に写った文字列を処理部１５が認識することにより生成された、電子データ化された文字列を処理部１５から受け取り、その電子データ化された文字列を他の機器へ出力する。なお、画像取得部１１と出力部１２とは、一体化されていてもよい。
【００２０】
記憶部１３は、例えば、読み書き可能な半導体メモリと読み出し専用の半導体メモリとを有する。そして記憶部１３は、処理部１５上で実行されるコンピュータプログラム、及び画像上の文字列を認識するために用いられる各種の情報、例えば、検索対象となる複数の単語が登録された単語辞書、パスごとの候補文字及び候補文字ラティスを記憶する。また記憶部１３は、認識対象となる文字列が写った画像を記憶してもよい。
【００２１】
記憶媒体アクセス装置１４は、例えば、磁気ディスク、半導体メモリカード及び光記憶媒体といった記憶媒体１６にアクセスする装置である。記憶媒体アクセス装置１４は、例えば、記憶媒体１６に記憶された、処理部１５上で実行される文字認識用コンピュータプログラムを読み込み、処理部１５に渡すか、記憶部１３に記憶させる。また記憶媒体アクセス装置１４は、処理部１５により生成された、電子データ化された文字列を記憶媒体１６に書き込んでもよい。
【００２２】
処理部１５は、１個または複数個のプロセッサ及びその周辺回路を有する。そして処理部１５は、複数の文字を含む文字列が写った画像から、その文字列に含まれる各文字を認識し、各文字に対応する文字コードを文字列の先頭から順に並べることで電子データ化された文字列を生成する。
【００２３】
図２は、処理部１５の機能を示すブロック図である。処理部１５は、文字区間検出部２１と、候補文字ラティス生成部２２と、候補文字抽出部２３と、候補文字ラティス修正部２４と、単語検索部２５と、推定部２６とを有する。処理部１５が有するこれらの各部は、例えば、処理部１５が有するプロセッサ上で実行されるコンピュータプログラムによって実装される機能モジュールである。あるいは、処理部１５が有するこれらの各部は、それぞれの機能を実現する回路が集積された集積回路として文字認識装置１に実装されてもよい。
【００２４】
文字区間検出部２１は、画像上に写った文字列に含まれる複数の文字のそれぞれごとに、その文字が写っていると推定される区間である文字区間を検出する。
【００２５】
本実施形態では、紙などの媒体に印刷された文字列のように、白い背景上に文字が黒く表現されているものを撮影した画像において、各画素の値は0〜255の範囲内の値を持ち、濃度が濃いほど、画素値も高いとする。なお、ディスプレイの画面に表示された文字列のように、背景の輝度よりも文字の輝度の方が高い場合には、輝度が高いほど、画素値も高くなるように画像は生成されてもよい。また認識対象である文字列は、いわゆる横書きの文字列であり、画像上で水平方向に沿っているとする。なお、認識対象の文字列が、いわゆる縦書きの文字列である場合には、下記の説明における水平方向と垂直方向とを入れ替えればよい。
【００２６】
上記のように、本実施形態では、画像上で文字が写っている画素の値は、文字が写っていない画素の値よりも高い。そのため、文字間の区切りに相当する画素の値の平均値は、文字が写っている画素の値の平均値よりも低くなる。そこで、文字区間検出部２１は、画像中の一行の文字列に相当する領域に含まれる垂直方向のラインごとに、画素値の合計を求め、その合計値をその垂直ラインに対応する水平位置における画素値の投影値とする。そして文字区間検出部２１は、投影値が所定の閾値以下となる位置を、文字の区切りとする。なお、所定の閾値は、例えば、投影値の合計を水平方向の画素数で割ることにより求めた投影値の平均値に所定の係数を乗じた値に設定される。なお、所定の係数は、1以下の正の値、例えば、0.5である。なお、文字区間検出部２１は、特開平２−２１７９７８号公報に開示されている技術を用いて文字間の区切りを検出してもよい。また、文字区間検出部２１は、画像の各画素を、文字が写っている文字画素と文字が写っていない背景画素とに２値化し、垂直方向のラインごとに文字画素の数を集計し、その文字画素の数を投影値としてもよい。この場合、画素を２値化するための閾値は、例えば、画像全体の画素値の平均値、あるいは、画素値の分布に対して判別分析することにより設定されてもよい。
【００２７】
文字区間検出部２１は、画像を、水平方向に隣接する二つの文字間の区切りで挟まれた区間のそれぞれを、文字区間とする。文字区間検出部２１は、文字区間ごとに一意な識別番号を割り当て、その一意な識別番号とともに、文字区間の左端と右端の水平方向の座標を記憶部１３に記憶する。
【００２８】
なお、画像上の複数の行にわたって文字列が写っていることもある。そこで、画像上に複数の文字列が写っている可能性がある場合には、文字区間検出部２１は、上記の文字間の区切りを検出する前に、行間の区切りを検出してもよい。この場合には、文字区間検出部２１は、画像中の水平方向のラインごとに、画素値の合計を求め、その合計値をその水平ラインに対応する垂直位置における画素値の投影値とする。そして文字区間検出部２１は、投影値が極小値かつ行区切り検出用の閾値以下となる位置を、行の区切りとする。なお、行区切り検出用の閾値は、例えば、水平方向のラインごとの投影値の合計を垂直方向の画素数で割ることにより求めた投影値の平均値に所定の係数（例えば、0.5）を乗じた値に設定される。文字区間検出部２１は、画像を、垂直方向に隣接する二つの行の区切りで挟まれた領域ごとに分割し、その分割された画像を一つの文字列を表す画像とする。そして文字区間検出部２１は、個々の文字列を表す画像ごとに、上記のように文字間の区切りを検出することで文字区間を検出する。
【００２９】
また、文字列を撮影するカメラと、その文字列との位置関係によっては、文字列の行方向と、画像の水平方向とが一致しないことがある。そこで、文字区間検出部２１は、例えば、画像を、所定角度（例えば、5度）ずつ、アフィン変換によって回転し、回転した画像において水平方向のラインごとに投影値を求めてもよい。この場合、文字区間検出部２１は、投影値が極小値かつ、所定の閾値以下となるラインの数が最も多いときの回転角の画像を用いて各文字列を検出した後に、文字列ごとに文字区間を検出してもよい。
【００３０】
さらに、文字のなかには、偏と旁からなる漢字のように、水平方向に沿って複数の分離した構成要素を持つ文字が含まれる。このような文字が文字列中に含まれていると、文字区間が文字の個々の構成要素ごとに検出されるおそれがある。
【００３１】
図３は、画像に写った文字列及びその文字列に対して検出された文字区間の一例を示す図である。図３に示された「運動会の始まり」という文字列３００に対して各垂直ラインの投影値を表すグラフ３１０が、文字列３００の下方に示されている。また各点線３２０は、検出された文字間の区切りを表す。例えば、文字「動」に対して、二つの文字区間３３１、３３２が設定されていることが分かる。同様に、文字「の」、「始」及び「り」に対しても、それぞれ二つの文字区間が設定されている。
【００３２】
そこで、文字区間検出部２１は、検出された全ての文字区間のうち、一つの文字の一部に対応する可能性のある文字区間を抽出する。そのために、文字区間検出部２１は、検出された全ての文字区間の水平方向の幅の平均値または最頻値を基準文字幅として算出する。そして文字区間検出部２１は、連続する複数の文字区間の組のうち、その組に含まれる各文字区間の水平方向の幅の合計が基準文字幅未満となる組を連結したものも、一つの文字区間とする。
【００３３】
候補文字ラティス生成部２２は、複数の文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを生成する。そのために、候補文字ラティス生成部２２は、検出された全ての文字区間について、その文字区間の左端の座標及び右端の座標を比較して画像の左端側から順に並べることで候補文字ラティスを生成する。
【００３４】
図４は、図３に示された文字列３００に対応する候補文字ラティスの一例を示す図である。候補文字ラティス４００は、１６個のパスを有する。個々のパスは矢印で表されており、パスの上にそのパスの識別番号、すなわち、そのパスに対応する文字区間の識別番号が示されている。また、個々のパスに対応する文字及び文字の一部の構成要素が、パスの上方または下方に示されている。例えば、パス１は文字「運」に対応する。またパス２、パス３は、それぞれ、文字「動」の偏と旁に対応している。一方、パス２とパス３が統合されたパス２０は、文字「動」に対応している。
【００３５】
候補文字抽出部２３は、個々のパスに対応する文字区間に写っている文字の候補である候補文字を少なくとも一つ抽出する。例えば、候補文字抽出部２３は、画像から、個々の文字区間に相当する画像の一部をそれぞれ文字画像として切り出し、その文字画像を２値化する。なお、文字画像を２値化するための閾値は、例えば、その文字画像の平均画素値とすることができる。そして候補文字抽出部２３は、２値化された文字画像と、個々の文字の形を表すテンプレートとの間でテンプレートマッチングを実行することにより、文字画像とテンプレート間の認識距離を求める。なお、テンプレートは、例えば、対応する文字のストロークが写っている画素の値が'255'であり、その他の画素の値が'0'である２値画像とすることができる。そして各テンプレートは、予め記憶部１３に記憶される。また一つの文字に対して、書体またはサイズが異なる複数のテンプレートが準備されてもよい。認識距離は、例えば、２値化された文字画像とテンプレート間のハミング距離とすることができる。この場合、認識距離が小さいほど、テンプレートに表された文字がその文字画像に写っている可能性が高い。あるいは、候補文字抽出部２３は、認識距離の代わりに、文字画像とテンプレート間の相互相関値を求めてもよい。この場合には、総合相関値が高いほど、テンプレートに表された文字がその文字画像に写っている可能性が高い。
【００３６】
候補文字抽出部２３は、パスごとに、認識距離が小さい方から順に所定数のテンプレートを抽出し、抽出したテンプレートに対応する文字をそのパスの候補文字とする。そして候補文字抽出部２３は、抽出した各候補文字に対して、認識距離が短い方から順に順位を付す。なお、所定数は、例えば、１〜５のうちの何れかに設定される。あるいは、候補文字抽出部２３は、認識距離が所定距離以下となるテンプレートを全て抽出し、抽出したテンプレートに対応する文字をそのパスの候補文字としてもよい。所定距離は、例えば、テンプレート中に含まれる画素の7割〜8割が文字画像の画素と一致したときの認識距離とすることができる。この場合、候補文字抽出部２３は、認識距離が所定距離以下となるテンプレートがないパスについては、認識距離が最小となるテンプレートに対応する文字をそのパスの候補文字とすることが好ましい。
なお、候補文字抽出部２３は、画像上に写っている文字を認識する他の公知技術を用いて、パスごとの候補文字を求めてもよい。但しこの場合も、候補文字ごとに、そのパスに対応する文字区間に写っている可能性が高い方から順に順位が付されることが好ましい。
【００３７】
再度図４を参照すると、パスごとに、３個の候補文字が示されている。例えば、パス１に対して、'運'、'連'、'達'という３個の候補文字が示されている。
候補文字抽出部２３は、パスごとに抽出された候補文字を表すコードを、その候補文字に対応する順位とともに、そのパスと関連付けて記憶部１３に記憶する。
【００３８】
再度図４を参照すると、候補文字ラティス４００には、文字列３００全体に対応する一列に連続したパスの配列が複数存在する。そして、少なくとも一部が重なっているパス同士は排他的であり、同一のパスの配列には含まれない。例えば、パス２及びパス３が文字列３００全体に対応するパスの配列の一部として選択されると、パス２０はそのパスの配列には含まれない。逆に、パス２０が文字列３００全体に対応するパスの配列の一部として選択されると、パス２及びパス３はそのパスの配列には含まれない。
【００３９】
図５は、他の文字列に対する候補文字ラティスの一例を示す図である。図５に示す例では、「認知」という文字列５００に対して、x2〜x6という5点の文字間の区切りが検出されている。またx1、x7は、それぞれ、文字列５００の左端と右端に対応する。この例では、文字「認」、「知」それぞれの偏と旁の境界も文字間の区切りとして検出されている。そのため、文字列５００には二文字しか含まれていないにもかかわらず、文字列５００に対応する候補文字ラティス５１０は、8個のパスA1〜A8を含んでいる。したがって、排他的なパスの組（例えば、パスA1、A4とパスA6、パスA6とパスA7など）も多数存在する。その結果として、文字列５００全体に対応する、一列に連続したパスの配列も多数存在する。
【００４０】
図４及び図５に示されるように、排他的なパスの組が増えると、文字列全体に対応するパスの配列の数も増加する。そして、文字列に含まれる単語の検索に失敗することを防止するためには、パスの配列ごとに単語が検索されることになるので、パスの配列の数が増えるほど、単語検索に要する演算量も増大する。
【００４１】
そこで、候補文字ラティス修正部２４は、画像に写った文字列全体に対応する一列に連続するパスの配列の数を削減するよう、排他的なパスの組に含まれるパスを修正することにより、候補文字ラティスを修正する。本実施形態では、候補文字ラティス修正部２４は、以下の条件を満たすように候補文字ラティスを修正する。
（１）互いに排他的でない複数のパス、すなわち、文字列全体に対応する一列に連続するパスの同一の配列に含まれることが可能なパスの組については、候補文字ラティス修正部２４は、それら複数のパスの順序を維持し、かつ、排他的でない状態を保つ。
（２）互いに排他的な複数のパスについては、候補文字ラティス修正部２４は、長い方のパスを短い方のパスと一致させるよう修正した上で統合する。ただし、統合することによって（１）の条件が満たされなくなる場合には、候補文字ラティス修正部２４は、長い方のパスを、そのパスに対して排他的なパスに隣接するように修正する。
（３）候補文字ラティス修正部２４は、長い方のパスに対して排他的な相対的に短いパスが複数存在する場合には、長い方のパスをその複数の相対的に短いパスの何れと統合してもよい。あるいは、候補文字ラティス修正部２４は、長い方のパスを複製して、複数の相対的に短いパスのそれぞれと統合してもよい。
（４）候補文字ラティス修正部２４は、複数のパスを統合する際、各パスに対応する文字区間及び候補文字を、統合されたパスに対応付ける。
【００４２】
図６は、候補文字ラティス修正部２４により実行される、上記の各条件を満たしつつ、候補文字ラティスを修正するための候補文字ラティス修正処理の一例の動作フローチャートである。また以下の説明では、理解を容易にするために、適宜図５に示された候補文字ラティス５００を参照する。
【００４３】
候補文字ラティス修正部２４は、複数のパスのうち、自身に対応する文字区間よりも短い文字区間に対応する他のパスと重ならないパスを確定グループαに分類する（ステップＳ１０１）。候補文字ラティス修正部２４は、確定グループαに分類されなかったパスを未確定グループβに分類する（ステップＳ１０２）。
【００４４】
再度図５を参照すると、候補文字ラティス５００に含まれる各パスには、それぞれのパスに対応する文字区間が短い方から順に識別番号A1〜A8が付されている。そしてパスA1〜パスA4は、自身の文字区間よりも短い文字区間に対応する他のパスと重ならない。そのため、パスA1〜A4は確定グループαに分類される。一方、パスA5〜A8は、自身の文字区間よりも短い文字区間に対応する他のパスと少なくとも一部が重なっている。例えば、パスA5の文字区間は、パスA2及びA3の文字区間と重なっており、パスA6の文字区間は、パスA1及びA4の文字区間と重なっている。そのため、パスA5〜A8は未確定グループβに分類される。
【００４５】
次に、候補文字ラティス修正部２４は、確定グループα内のパスを、文字列の先頭から終端へ向かう座標順にソートして修正パス列P=｛p[1],p[2],....｝を生成する。さらに候補文字ラティス修正部２４は、修正パス列P内の各修正パスp[k]に対応する、すなわち、修正パスp[k]に対して排他的なパスの集合である他の候補パス群｛Qk｝を空集合として初期化する（ステップＳ１０３）。例えば、候補文字ラティス５００について、修正パス列Pは、下記の表１に示されるように、パスA1〜パスA4を、A1、A4、A3、A2の順に含む。
【表１】
なお、表１には、各修正パスp[k]について、元の候補文字ラティスにおけるパスの識別番号、パスに対応する文字区間（すなわち、その文字区間の左端及び右端の座標）、そのパスについて抽出された候補文字及び他の候補パス群が対応付けられる。例えば、修正パスp[1]には、識別番号A1、パスA1の文字区間[x1,x2]、候補文字「言」が対応付けられている。なお、候補文字が複数ある場合には、すべての候補文字が対応付けられる。例えば、パスA1に対して３個の候補文字「言」、「吉」、「忘」が抽出されている場合、これらの候補文字すべてが修正パスp[1]に対応付けられる。
また、この時点では、修正パス列Pに含まれる修正パスp[k]と未確定グループに属するパスとの位置関係は調べられていないので、各修正パスについての他の候補パス群は空集合となっている。
【００４６】
候補文字ラティス修正部２４は、未確定グループβに属するパスの何れかを注目パスAとして選択する（ステップＳ１０４）。なお、候補文字ラティス修正部２４は、例えば、未確定グループβに属するパスの中で対応する文字区間が最も短いパスから順に注目パスAとして選択する。あるいは、候補文字ラティス修正部２４は、例えば、未確定グループβに属するパスの中で最も文字列の先頭に近いパスから順に注目パスAとして選択してもよい。そして候補文字ラティス修正部２４は、修正パス列Pに含まれる修正パスp[k]のうち、注目パスAと少なくとも一部が重なる修正パスp[j]の何れかを選択する（ステップＳ１０５）。候補文字ラティス修正部２４は、修正パスp[j]に対応する他の候補パスのうちで注目パスAと重ならないパスがあるか否か判定する（ステップＳ１０６）。修正パスp[j]に対応する他の候補パスが無いか、または、他の候補パスのうちで注目パスAと重ならないパスがなければ（ステップＳ１０６−Ｎｏ）、候補文字ラティス修正部２４は、p[j]に対応する他の候補パス群｛Qk｝にパスAを追加する（ステップＳ１０７）。
【００４７】
例えば、注目パスAがパスA5であれば、修正パスp[3]、すなわちパスA3または修正パスp[4]、すなわちパスA2が選択されることになる。例えば、修正パスp[3]が選択されたとすると、この時点では、修正パスp[3]に対応する他の候補パスは存在しない。したがって、修正パスp[3]の他の候補パス群にパスA5が追加される。
【００４８】
ステップＳ１０７の後、あるいは、修正パスp[j]に対応する他の候補パスがあり、かつ、他の候補パスのうちで注目パスAと重ならないパスがある場合（ステップＳ１０６−Ｙｅｓ）、候補文字ラティス修正部２４は注目パスAと重なる他の修正パスが有るか否か判定する（ステップＳ１０８）。注目パスAと重なる他の修正パスが有れば（ステップＳ１０８−Ｙｅｓ）、候補文字ラティス修正部２４は、ステップＳ１０５以降の処理を繰り返す。
【００４９】
例えば、注目パスとしてのパスA5に対して最初に修正パスp[3]が選択されていると、候補文字ラティス修正部２４は、次に修正パスp[4]、すなわち、パスA2を選択する。この時点では、修正パスp[4]に対応する他の候補パスは存在しない。したがって、修正パスp[4]の他の候補パス群にパスA5が追加される。
【００５０】
一方、注目パスAと重なる他の修正パスがなければ（ステップＳ１０８−Ｎｏ）、候補文字ラティス修正部２４は、注目パスAは何れかの修正パスp[j]の他の候補パス群｛Qj｝に追加されたか否か判定する（ステップＳ１０９）。注目パスAが何れかの修正パスp[j]の他の候補パス群｛Qj｝に追加されていれば（ステップＳ１０９−Ｙｅｓ）、候補文字ラティス修正部２４は、未確定グループβ内に未注目のパスが残っているか否か判定する（ステップＳ１１１）。そして未注目のパスが残っていれば（ステップＳ１１１−Ｙｅｓ）、候補文字ラティス修正部２４は、ステップＳ１０４以降の処理を繰り返す。
【００５１】
例えば、パスA5の後、パスA6、A7が順次注目パスとして選択され、ステップＳ１０４〜Ｓ１１１の処理が行われたとする。この時点での修正パス列Pの対応表は以下のようになる。
【表２】
図５及び表２に示されるように、パスA6、パスA7は、修正パスp[1]、p[2]に対して、他の候補パスが無いか、あるいは他の候補パス群内にパスA6、A7と重ならないパスは無いので、修正パスp[1]、p[2]の他の候補群｛Q1｝、｛Q2｝にそれぞれ追加されている。
【００５２】
一方、ステップＳ１０９にて、注目パスAが何れの修正パスp[j]の他の候補パス群｛Qj｝にも追加されていなければ（ステップＳ１０９−Ｎｏ）、候補文字ラティス修正部２４は、修正パス列Pに対して、パスAと重なる複数の修正パスの間に、新たな修正パスとしてパスAを追加する（ステップＳ１１０）。
【００５３】
例えば、図５及び表２を参照すると、最後の未注目パスであるパスA8が注目パスに設定されたとすると、パスA8は修正パスp[2]、すなわちパスA4及び修正パスp[3]、すなわちパスA3と重なっている。しかし、修正パスp[2]の他の候補群｛Q2｝には、パスA8と重ならないパスA7が含まれている。同様に、修正パスp[3]の他の候補群｛Q3｝にも、パスA8と重ならないパスA5が含まれている。そのため、パスA8は、何れの修正パスp[j]の他の候補群にも追加されない。そして、パスA8の文字区間の途中に、修正パスp[2]に対応する文字区間と修正パスp[3]に対応する文字区間の境界が位置している。そのため、パスA8は、修正パスp[2]と修正パスp[3]の間に追加される。
【００５４】
ステップＳ１１０の後、候補文字ラティス修正部２４は、未確定グループβ内に未注目のパスが残っているか否か判定する（ステップＳ１１１）。そして未注目のパスが残っていれば（ステップＳ１１１−Ｙｅｓ）、候補文字ラティス修正部２４は、ステップＳ１０４以降の処理を繰り返す。
一方、未注目のパスが残っていなければ（ステップＳ１１１−Ｎｏ）、候補文字ラティス修正部２４は、他の候補パス群｛Qk｝についての候補文字を全て修正パスp[k]の候補文字として追加する（ステップＳ１１２）。そして修正パス列Pが、修正候補文字ラティスとなる。この場合、他の候補パス群｛Qk｝が空集合でない修正パスp[k]は、その修正パスp[k]に対応する確定グループα内のパス及び他の候補パス群｛Qk｝に含まれるパスを置換するものとなる。
その後、候補文字ラティス修正部２４は、候補文字ラティス修正処理を終了する。
【００５５】
表３は、最終的に作成された修正候補文字ラティスのパス及び候補文字の一覧である。
【表３】
修正候補文字ラティスの各パスには、そのパスに関連付けられた元の候補文字ラティスのパスの識別番号及びそのパスの候補文字がその順位とともに関連付けられる。表３に示されるように、修正候補文字ラティスに含まれる統合されたパスについての候補文字の数は元の個々のパスについての候補文字の数よりも増えるものの、修正候補文字ラティスは互いに排他的なパスの組を含んでいない。そのため、修正候補文字ラティスは、元の候補文字ラティスよりも簡単な構造を有している。
【００５６】
図７は、候補文字ラティス修正部２４により実行される、上記の各条件を満たしつつ、候補文字ラティスを修正するための候補文字ラティス修正処理の他の一例の動作フローチャートである。また以下の説明においても、理解を容易にするために、適宜図５に示された候補文字ラティス５００を参照する。
【００５７】
候補文字ラティス修正部２４は、候補文字ラティスに含まれるパスの境界を先頭から順に全て抽出する（ステップＳ２０１）。そして候補文字ラティス修正部２４は、（パスの境界の数-1）個の修正パスを含むパス記憶領域を記憶部１３に設定する（ステップＳ２０２）。
例えば、候補文字ラティス５００では、先頭から順にx1〜x7の7個の境界があるので、下記の表４のように、6個の修正パスを含むパス記憶領域が設定される。
【表４】
表４において、一番上の行は修正パスの先頭からの順序を表す。二番目の行は各修正パスに対応する区間の左端と右端の水平座標を表す。３番目の行は、修正パスに割り当てられた元の候補文字ラティスのパスの識別番号を表す。そして一番下の行は、修正パスに割り当てられたパスについての候補文字の集合を表す。この時点では、何れの修正パスにもパスは割り当てられていないので、下の２行は空欄となっている。
【００５８】
候補文字ラティス修正部２４は、各パスを、そのパスに対応する文字区間と修正パスの区間との重なり幅が最も大きい修正パスに割り当てる（ステップＳ２０３）。
例えば、x1=10、x2=25、x3=30、x4=40とする。この場合、パスA6は、修正パスM1[x1,x2]、M2[x2,x3]、M3[x3,x4]と重なっているが、このうち修正パスM1との重なり幅が最も大きい。そこで候補文字ラティス修正部２４は、パスA6を修正パスM1に割り当てる。
表５は、全てのパスを何れかの修正パスに割り当てたときのパス記憶領域を表す。
【表５】
なお、表５では、簡単化のために、各パスについて一つの候補文字だけが示されている。
【００５９】
候補文字ラティス修正部２４は、全てのパスが修正パスの何れかに割り当てられた後、１以上のパスが割り当てられた修正パスを先頭から順に抽出し、修正候補文字ラティスのパスとする（ステップＳ２０４）。そして候補文字ラティス修正部２４は、抽出された修正パスに割り当てられたパスの候補文字を、修正候補文字ラティスのパスの候補文字とする（ステップＳ２０５）。この例でも、複数のパスが割り当てられた修正パスは、それら複数のパスを統合し、かつそれら複数のパスを置換するものとなる。
その後、候補文字ラティス修正部２４は、候補文字ラティス修正処理を終了する。
【００６０】
例えば、表５に示されるように、修正パスM1、M3、M5、M6には１以上のパスが割り当てられている。そこで、修正パスM1、M3、M5、M6が修正候補文字ラティスのパスとして抽出される。表６は、最終的に得られる修正候補文字ラティスのパス及び候補文字の一覧である。
【表６】
【００６１】
なお、変形例によれば、ステップＳ２０３において、候補文字ラティス修正部２４は、各パスを、そのパスと少なくとも一部が重なる全ての修正パスに割り当ててもよい。この場合、例えば、パスA6は、修正パスM1〜M3にそれぞれ割り当てられる。表７は、この変形例により全てのパスが何れかの修正パスに割り当てられたときのパス記憶領域を表す。
【表７】
【００６２】
上記のように、何れの候補文字ラティス修正処理が実行されても、修正候補文字ラティスは、排他的なパスを含まないので、文字列全体に対応する一列に連続したパスの配列は一通りとなる。
【００６３】
単語検索部２５は、記憶部１３に記憶された単語辞書に登録された複数の単語のうち、修正候補文字ラティスの少なくとも一部のパスの配列に含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検出する。
本実施形態では、単語検索部２５は、単語辞書中に登録されている単語を検索するために、動的計画法（Dynamic Programming）によるマッチング手法（以下、DPマッチングと呼ぶ）を利用する。
【００６４】
図８は、本実施形態により利用されるDPマッチングを用いた、最適パスの探索手順の説明図である。図８において、検索対象単語に含まれる文字数に1加算した数を縦軸の格子数、修正候補文字ラティスの少なくとも一部に含まれるパスの数に1加算した数を横軸の格子数として、碁盤目状に格子点が配置されている。この例では、検索対象単語８１０は「運動会」であり、３個の文字を含む。そして各文字は、先頭から順に、上から順に一つの行の格子点に対応付けられている。一方、修正候補文字ラティスのパス数は４個であり、先頭のパスから終端のパスまで左側から順に一つの列の格子点に対応付けられている。また各パスには、１以上の候補文字８１１〜８１４が対応付けられている。例えば、先頭のパスには、３個の候補文字「運」、「連」、「達」が対応付けられている。各パスの候補文字の中から選択した一つの文字を先頭側のパスから順に連結して得られる文字列を、ここでは入力文字列と呼ぶ。
【００６５】
単語検索部２５は、左上端の格子点から右下端の格子点へ向かう経路のうち最適な経路を探索する。評価値として、例えば、検索対象単語と入力文字列間の編集距離、あるいは検索対象単語と入力文字列間で一致する文字の個数が用いられる。評価値として編集距離が用いられる場合、単語検索部２５は、評価値が最小となる経路を最短経路とする。この場合、左上端の格子点が最初の注目格子点となる。そして単語検索部２５は、注目格子点の右側、下側及び右下側に隣接する格子点の何れかを次の注目格子点とする。その際、現在の注目格子点から右下に隣接する注目格子点へ遷移した場合に、次の注目格子点が属する行に対応する検索対象単語の文字（例えば、上から３番目の行であれば、「動」）と、注目格子点が属する列に対応する候補文字の何れかが一致するか否か判定する。そして一致すれば、編集距離に加算されるポイントは'0'となる。しかし、一致しなければ、編集距離に加算されるポイントは'+2'となる。なお、両者が一致しないことは、検索対象単語の次の注目格子点に対応する文字が置換されたことに相当する。また、文字の置換に相当する加算ポイントは、'+1'に設定されてもよい。
【００６６】
また、現在の注目格子点に対して下側に隣接する格子点が次の注目格子点となる場合、編集距離に加算されるポイントは'+1'となる。なお、この下側への遷移は、検索対象単語中の文字の欠落に相当する。さらに、現在の注目格子点に対して右側に隣接する格子点が次の注目格子点となる場合も、編集距離に加算されるポイントは'+1'となる。なお、この右側への遷移は、検索対象単語に対する文字の挿入に相当する。
図８に示した例では、矢印で示される経路８２０が最短経路となり、検索対象単語に対応する入力文字列として「運動☆会」が選択される。なお、☆マークは、挿入された文字を表し、ここでは、右から２番目のパスに対応する候補文字「カ」、「力」、「刀」の何れかである。
【００６７】
単語検索部２５は、検索対象単語と入力文字列間の文字の再現率及び文字の適合率が所定の閾値を超えた場合、修正候補文字ラティスが表す文字列中のその入力文字列に対応する位置において検索対象単語が検出されたと判定する。
なお、文字の再現率及び文字の適合率は、例えば、次式で表される。
文字の再現率＝（入力文字列と検索対象単語間で一致する文字数）
／検索対象単語に含まれる文字数
文字の適合率＝（入力文字列と検索対象単語間で一致する文字数）
／入力文字列に含まれる文字数
また、所定の閾値は、例えば、0.6〜0.8の範囲内の何れかの値に設定される。
【００６８】
あるいは、単語検索部２５は、最短経路についての編集距離が所定の値以下である場合、その最短経路に対応する入力文字列に対応する位置において検索対象単語が抽出されたと判定してもよい。この場合、所定の値は、例えば、検索対象単語に含まれる文字数に、0.3〜0.4の範囲内の何れかの値を乗じた値とすることができる。
【００６９】
また、単語検索部２５は、他のあいまい検索手法を用いて、修正候補文字ラティスに含まれるパスの少なくとも一部の配列に含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検索してもよい。単語検索部２５は、このようなあいまい検索手法として、例えば、特開2010-225137号公報に開示されている方法を用いることができる。または、単語検索部２５は、喜田、「誤りを許したVLDCパタン照合アルゴリズム」、電子情報通信学会技術研究報告、COMP、コンピューテーション、103(622)、p61-68、2004年に記載された方法を用いることができる。
【００７０】
単語検索部２５は、単語辞書に登録された全ての単語に対して上述した処理を行って、文字列に含まれる単語を検索する。したがって、例えば、単語辞書に非常に多数の単語が登録されていると、例えば、10万個の単語が登録されていると、その全ての単語に対して上述した処理が行われることになる。
しかし、上記のように、単語検索部２５は、個々の単語について、排他的なパスを含まない修正候補文字ラティスに対してあいまい検索を行うので、パスの組み合わせが複数存在する元の候補文字ラティスに対してあいまい検索を行うよりも大幅に演算量を削減できる。そのため、単語辞書に登録されている単語の数が増えるほど、演算量の削減効果も大きくなる。また単語検索部２５は、文字の置換、挿入及び欠落の何れも許容して単語の検索を行うので、個々のパスに対する文字の誤認識が生じていたり、あるいは、検出された文字区間が誤っている場合でも、単語検索部２５は、文字列に含まれる単語を正しく検索できる。
【００７１】
単語検索部２５は、候補文字ラティスに対して、検出された単語に対応するパスである単語パスを追加する。そして得られたラティスを、以下では便宜上、候補文字・単語ラティスと呼ぶ。なお、単語検索部２５は、単語を検出する際に、DPマッチングの対象としたパスを知っているので、そのパスの位置に基づいて、単語パスを追加する位置を特定できる。さらに、単語検索部２５は、検出された単語パスのそれぞれについて、対応する単語に含まれる各文字と一致する候補文字の順位及びその候補文字に対応する元の候補文字ラティスのパスの識別番号をその単語パスと関連付ける。
【００７２】
図９は、図３に示した文字列「運動会の始まり」に対して、検出された単語のパスを追加した候補文字・単語ラティスの一例を示す図である。図９に示された候補文字・単語ラティス９００において、矢印で表されるパスのうち、パス１〜２３が文字ごとのパスであり、パス３１〜３７が追加された単語パスである。
【００７３】
推定部２６は、候補文字・単語ラティスに基づいて、画像上に写った文字列を推定する。そのために、推定部２６は、候補文字・単語ラティスに含まれる単語パスごとに、その単語パスに対応する単語の評価値を、例えば次式に従って算出する。
単語評価値＝｛Σ(1-α(Mi-1))｝n
ここで、Miは、単語検索部２５により検出された単語における先頭からi番目の文字と一致すると判定された候補文字の順位を表す。ただし、i番目の文字と一致すると判定された候補文字が無かった場合には、Miは候補文字抽出部２３が個々のパスについて抽出する候補文字の最大個数に1を加算した値に設定される。αは係数であり、Miの値が大きいほど(1-α(Mi-1))が0に近づくように、例えば、候補文字抽出部２３が個々のパスについて抽出する候補文字の最大個数の逆数以下の正の値、例えば、0.1に設定される。したがって、単語パスに対応する単語に含まれる個々の文字と一致する候補文字の順位の合計が小さいほど、単語評価値は高くなる。またnは補正係数であり、例えば、1以上の値に設定される。特に、単語に含まれる文字数が増えるほど単語評価値も高くなるようにするためには、補正係数nは、1よりも大きい値に設定されることが好ましく、例えば、2に設定される。このように補正係数を設定することで、文字数が多い単語ほど、文字列に含まれる単語であると推定され易くなる。
【００７４】
再度図９を参照すると、単語パス３１に対応する単語「運動会」について、M1=M2=1、M3=2である。そのため、α=0.1、n=2とすれば、単語評価値は8.41となる。なお、図９において、単語パス３１〜３７が表す単語と並んで表記された数値がその単語についての単語評価値である。
【００７５】
また、推定部２６は、単語パスでない、一つの文字を表すパスについての単語評価値を定数βに設定する。定数βは、例えば、0より大きく、２文字を含む単語についての単語評価値が取りうる最大値よりも小さい値、例えば、0.5に設定される。
【００７６】
推定部２６は、候補文字・単語ラティスにおいて、文字列全体に対応する、一列に連続した単語パス及びパスの配列のそれぞれについて、単語評価値の総和を、その配列に対する連結パス評価値として求める。そして推定部２６は、連結パス評価値が最大値となる配列に含まれる単語パス及びパスの順序に従って整列されたその単語パス及びパスに対応する単語と文字の列を、画像上に写っている文字列と推定する。なお、図９におけるパス５、６とパス２１のように、単語評価値の和が等しい排他的な複数のパスが存在する場合、推定部２６は、候補文字抽出部２３により求められた認識距離の和が小さい方のパスを配列に含めるように選択する。また、単語評価値が最大となる配列に含まれるパスに対して複数の候補文字が有る場合には、推定部２６は、順位が最も高い候補文字を選択する。
図９の例では、パス３１→パス２１→パス３４の順序に従って選択された配列の連結パス評価値が最大となるので、推定部２６は、それらのパスに対応する単語及び候補文字を並べた文字列「運動会の始まり」を、画像上に写っている文字列として推定する。
【００７７】
図１０は、文字認識処理の動作フローチャートである。処理部１５は、画像を受け取る度に、この文字認識処理を実行する。
文字区間検出部２１は、画像上に写った文字列から、個々の文字のそれぞれごとに、その文字が写っていると推定される文字区間を検出する（ステップＳ３０１）。さらに文字区間検出部２１は、１文字に対応する可能性の有る連続した２以上の文字区間を連結した区間も文字区間として検出する（ステップＳ３０２）。その後、候補文字ラティス生成部２２は複数の文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを生成する（ステップＳ３０３）。
また候補文字抽出部２３は、パスごとに候補文字を抽出する（ステップＳ３０４）。
【００７８】
その後、候補文字ラティス修正部２４は、互いに排他的なパスを統合するか、あるいは排他的なパスの一方の位置を修正することで修正候補文字ラティスを生成する（ステップＳ３０５）。具体的には、候補文字ラティス修正部２４は、第１のパスと、第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、第１及び第２のパスの候補文字を含み、かつ第２のパスと同一の文字区間に対応する第３のパスで置換する。あるいは、候補文字ラティス修正部２４は、第１のパスを、その連続したパスの間に挿入されるように修正する。
【００７９】
その後、単語検索部２５は、単語辞書に登録されている複数の単語のうち、修正候補文字ラティスにおいて連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を検出する（ステップＳ３０６）。また、単語検索部２５は、検出された単語に相当する単語パスを候補文字ラティスに追加して候補文字・単語ラティスを生成する（ステップＳ３０７）。
推定部２６は、各パスについて求めた単語評価値の総和が最大となるパスの配列に相当する文字列を画像上に写っている文字列と推定する（ステップＳ３０８）。そして処理部１５は、推定された文字列に含まれる各文字のコードを、推定された文字列の順序に従って並べることにより、画像上に写った文字列を電子データ化する。処理部１５は、文字列を表す電子データを出力部１２を介して他の機器へ出力する。あるいは、処理部１５は、文字列を表す電子データを記憶部１３に記憶する。その後、処理部１５は、文字認識処理を終了する。なお、処理部１５は、ステップＳ３０３とステップＳ３０４の処理の順序を入れ替えてもよい。
【００８０】
以上に説明してきたように、この文字認識装置は、文字列中に含まれている単語を検索する前に、候補文字ラティスの構造を修正して互いに排他的なパスの組を無くすことで、その文字列を表すパスの配列の数を削減している。そのため、この文字認識装置は、単語検索の際の演算量を削減できるので、文字認識処理全体としての演算量も削減できる。さらにこの文字認識装置は、単語中の文字の置換、欠落または挿入を許容したあいまい検索手法により、文字列に含まれている可能性がある単語を検索する。そのため、この文字認識装置は、画像上の文字列に含まれる個々の文字の認識結果に誤りがあっても、文字列中に含まれる単語を検出できるので、その文字列を正確に認識できる。
【００８１】
なお、本発明は上記の実施形態に限られるものではない。例えば、推定部は、単語パスに対応する単語に含まれるそれぞれの文字と一致する候補文字についての認識距離の平均値が小さいほど、単語評価値を高くしてもよい。
また、文字区間検出部は、投影値に対する閾値を変更して文字の区切りを検出することによって、複数の文字区間を検出してもよい。例えば、文字区間検出部は、先ず、上記の実施形態と同様の閾値を用いて文字の区切りを検出することで、複数の文字区間を検出する。その後、文字区間検出部は、閾値をより低い値、例えば、元の閾値を1.2〜1.5で割った値に修正した後、再度各水平位置の投影値と修正後の閾値を比較して、修正後の閾値以下の投影値を持つ水平位置を文字の区切りとして再検出する。そして文字区間検出部は、再検出された文字の区切りで挟まれた区間を文字区間とする。これにより、文字の構成要素同士が近接する文字についても、その文字全体を含む文字区間が検出され易くなる。
【００８２】
ここに挙げられた全ての例及び特定の用語は、読者が、本発明及び当該技術の促進に対する本発明者により寄与された概念を理解することを助ける、教示的な目的において意図されたものであり、本発明の優位性及び劣等性を示すことに関する、本明細書の如何なる例の構成、そのような特定の挙げられた例及び条件に限定しないように解釈されるべきものである。本発明の実施形態は詳細に説明されているが、本発明の精神及び範囲から外れることなく、様々な変更、置換及び修正をこれに加えることが可能であることを理解されたい。
【符号の説明】
【００８３】
１ 文字認識装置
１１ 画像取得部
１２ 出力部
１３ 記憶部
１４ 記憶媒体アクセス装置
１５ 処理部
１６ 記憶媒体
２１ 文字区間検出部
２２ 候補文字ラティス生成部
２３ 候補文字抽出部
２４ 候補文字ラティス修正部
２５ 単語検索部
２６ 推定部
【特許請求の範囲】
【請求項１】
媒体上に表された複数の文字を含む文字列を撮影した画像から、前記複数の文字のそれぞれごとに、当該文字が写っていると推定される前記画像上の文字区間を検出し、
複数の前記文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求め、
複数の前記パスのそれぞれについて、当該パスに対応する前記文字区間に写っている文字の候補である候補文字を少なくとも一つ求め、
前記候補文字ラティスに含まれる複数の前記パスのうち、第１のパスと、前記第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、当該第１のパスの候補文字及び当該第２のパスの候補文字を含み、かつ、当該第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは前記第１のパスが前記２以上の連続したパスの間に挿入されるように前記候補文字ラティスを修正し、
単語辞書に登録された複数の単語のうち、前記修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を前記文字列に含まれる可能性のある単語として検出し、当該検出された単語の前記文字列中の位置を表す単語パスを前記候補文字ラティスに追加した候補文字及び単語ラティスを求め、
前記候補文字及び単語ラティスにおいて、前記単語パスごとに、当該単語パスに対応する単語が前記文字列に含まれる確からしさを表す評価値を求め、
前記候補文字及び単語ラティスに含まれる前記単語パス及び前記パスの中から選択した前記文字列全体に対応する一列に連続した前記単語パス及び前記パスの配列ごとに、前記評価値の合計値を求め、当該合計値が最も高い配列に含まれる前記単語パス及び前記パスの順序に従って整列された当該単語パス及び当該パスに対応する単語と候補文字の組み合わせを前記文字列として推定する、
ことをコンピュータに実行させる文字認識用コンピュータプログラム。
【請求項２】
前記候補文字ラティスを修正することは、前記２以上の連続するパスのうち、前記第１のパスに対応する前記文字区間と重なる幅が最大となる文字区間に対応するパスを前記２のパスとする、請求項１に記載の文字認識用コンピュータプログラム。
【請求項３】
前記文字区間を求めることは、連続する２以上の前記文字区間のうち、当該２以上の文字区間を連結することにより得られる修正区間の幅が一つの文字の幅に相当する場合に、当該修正区間を文字区間として追加することを含む、請求項１または２に記載の文字認識用コンピュータプログラム。
【請求項４】
前記候補文字を求めることは、複数の前記パスの少なくとも一つについて複数の候補文字を求めるとともに、当該パスについて求められた複数の候補文字のそれぞれに対して、当該パスに対応する前記文字区間に写っている確からしさが高い方から順に順位を設定し、
前記評価値を求めることは、前記単語パスに対応する単語に含まれる文字と一致する前記候補文字の順位の合計が小さいほど前記評価値を高くする、請求項１〜３の何れか一項に記載の文字認識用コンピュータプログラム。
【請求項５】
前記評価値を求めることは、前記単語パスに対応する単語に含まれる文字の数が多いほど前記評価値を高くする、請求項１〜４の何れか一項に記載の文字認識用コンピュータプログラム。
【請求項６】
媒体上に表された複数の文字を含む文字列を撮影した画像を取得する画像取得部と、
複数の単語を登録した単語辞書を記憶する記憶部と、
前記画像から、前記複数の文字のそれぞれごとに、当該文字が写っていると推定される前記画像上の文字区間を検出する文字区間検出部と、
複数の前記文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求める候補文字ラティス生成部と、
複数の前記パスのそれぞれについて、当該パスに対応する前記文字区間に写っている文字の候補である候補文字を少なくとも一つ求める候補文字抽出部と、
前記候補文字ラティスに含まれる複数の前記パスのうち、第１のパスと、前記第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、当該第１のパスの候補文字及び当該第２のパスの候補文字を含み、かつ、当該第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは前記第１のパスが前記２以上の連続したパスの間に挿入されるように前記候補文字ラティスを修正する候補文字ラティス修正部と、
単語辞書に登録された複数の単語のうち、前記修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を前記文字列に含まれる可能性のある単語として検出し、当該検出された単語の前記文字列中の位置を表す単語パスを前記候補文字ラティスに追加した候補文字及び単語ラティスを求める単語検索部と、
前記候補文字及び単語ラティスにおいて、前記単語パスごとに、当該単語パスに対応する単語が前記文字列に含まれる確からしさを表す評価値を求め、前記候補文字及び単語ラティスに含まれる前記単語パス及び前記パスの中から選択した前記文字列全体に対応する一列に連続した前記単語パス及び前記パスの配列ごとに前記評価値の合計値を求め、当該合計値が最も高い配列に含まれる前記単語パス及び前記パスの順序に従って整列された当該単語パス及び当該パスに対応する単語と候補文字の組み合わせを前記文字列として推定する推定部と、
を有する文字認識装置。
【請求項７】
媒体上に表された複数の文字を含む文字列を撮影した画像を取得し、
前記画像から、前記複数の文字のそれぞれごとに、当該文字が写っていると推定される前記画像上の文字区間を検出し、
複数の前記文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求め、
複数の前記パスのそれぞれについて、当該パスに対応する前記文字区間に写っている文字の候補である候補文字を少なくとも一つ求め、
前記候補文字ラティスに含まれる複数の前記パスのうち、第１のパスと、前記第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、当該第１のパスの候補文字及び当該第２のパスの候補文字を含み、かつ、当該第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは前記第１のパスが前記２以上の連続したパスの間に挿入されるように前記候補文字ラティスを修正し、
単語辞書に登録された複数の単語のうち、前記修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を前記文字列に含まれる可能性のある単語として検出し、当該検出された単語の前記文字列中の位置を表す単語パスを前記候補文字ラティスに追加した候補文字及び単語ラティスを求め、
前記候補文字及び単語ラティスにおいて、前記単語パスごとに、当該単語パスに対応する単語が前記文字列に含まれる確からしさを表す評価値を求め、
前記候補文字及び単語ラティスに含まれる前記単語パス及び前記パスの中から選択した前記文字列全体に対応する一列に連続した前記単語パス及び前記パスの配列ごとに前記評価値の合計値を求め、当該合計値が最も高い配列に含まれる前記単語パス及び前記パスの順序に従って整列された当該単語パス及び当該パスに対応する単語と候補文字の組み合わせを前記文字列として推定する、
ことを含む方法。
【請求項１】
媒体上に表された複数の文字を含む文字列を撮影した画像から、前記複数の文字のそれぞれごとに、当該文字が写っていると推定される前記画像上の文字区間を検出し、
複数の前記文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求め、
複数の前記パスのそれぞれについて、当該パスに対応する前記文字区間に写っている文字の候補である候補文字を少なくとも一つ求め、
前記候補文字ラティスに含まれる複数の前記パスのうち、第１のパスと、前記第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、当該第１のパスの候補文字及び当該第２のパスの候補文字を含み、かつ、当該第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは前記第１のパスが前記２以上の連続したパスの間に挿入されるように前記候補文字ラティスを修正し、
単語辞書に登録された複数の単語のうち、前記修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を前記文字列に含まれる可能性のある単語として検出し、当該検出された単語の前記文字列中の位置を表す単語パスを前記候補文字ラティスに追加した候補文字及び単語ラティスを求め、
前記候補文字及び単語ラティスにおいて、前記単語パスごとに、当該単語パスに対応する単語が前記文字列に含まれる確からしさを表す評価値を求め、
前記候補文字及び単語ラティスに含まれる前記単語パス及び前記パスの中から選択した前記文字列全体に対応する一列に連続した前記単語パス及び前記パスの配列ごとに、前記評価値の合計値を求め、当該合計値が最も高い配列に含まれる前記単語パス及び前記パスの順序に従って整列された当該単語パス及び当該パスに対応する単語と候補文字の組み合わせを前記文字列として推定する、
ことをコンピュータに実行させる文字認識用コンピュータプログラム。
【請求項２】
前記候補文字ラティスを修正することは、前記２以上の連続するパスのうち、前記第１のパスに対応する前記文字区間と重なる幅が最大となる文字区間に対応するパスを前記２のパスとする、請求項１に記載の文字認識用コンピュータプログラム。
【請求項３】
前記文字区間を求めることは、連続する２以上の前記文字区間のうち、当該２以上の文字区間を連結することにより得られる修正区間の幅が一つの文字の幅に相当する場合に、当該修正区間を文字区間として追加することを含む、請求項１または２に記載の文字認識用コンピュータプログラム。
【請求項４】
前記候補文字を求めることは、複数の前記パスの少なくとも一つについて複数の候補文字を求めるとともに、当該パスについて求められた複数の候補文字のそれぞれに対して、当該パスに対応する前記文字区間に写っている確からしさが高い方から順に順位を設定し、
前記評価値を求めることは、前記単語パスに対応する単語に含まれる文字と一致する前記候補文字の順位の合計が小さいほど前記評価値を高くする、請求項１〜３の何れか一項に記載の文字認識用コンピュータプログラム。
【請求項５】
前記評価値を求めることは、前記単語パスに対応する単語に含まれる文字の数が多いほど前記評価値を高くする、請求項１〜４の何れか一項に記載の文字認識用コンピュータプログラム。
【請求項６】
媒体上に表された複数の文字を含む文字列を撮影した画像を取得する画像取得部と、
複数の単語を登録した単語辞書を記憶する記憶部と、
前記画像から、前記複数の文字のそれぞれごとに、当該文字が写っていると推定される前記画像上の文字区間を検出する文字区間検出部と、
複数の前記文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求める候補文字ラティス生成部と、
複数の前記パスのそれぞれについて、当該パスに対応する前記文字区間に写っている文字の候補である候補文字を少なくとも一つ求める候補文字抽出部と、
前記候補文字ラティスに含まれる複数の前記パスのうち、第１のパスと、前記第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、当該第１のパスの候補文字及び当該第２のパスの候補文字を含み、かつ、当該第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは前記第１のパスが前記２以上の連続したパスの間に挿入されるように前記候補文字ラティスを修正する候補文字ラティス修正部と、
単語辞書に登録された複数の単語のうち、前記修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を前記文字列に含まれる可能性のある単語として検出し、当該検出された単語の前記文字列中の位置を表す単語パスを前記候補文字ラティスに追加した候補文字及び単語ラティスを求める単語検索部と、
前記候補文字及び単語ラティスにおいて、前記単語パスごとに、当該単語パスに対応する単語が前記文字列に含まれる確からしさを表す評価値を求め、前記候補文字及び単語ラティスに含まれる前記単語パス及び前記パスの中から選択した前記文字列全体に対応する一列に連続した前記単語パス及び前記パスの配列ごとに前記評価値の合計値を求め、当該合計値が最も高い配列に含まれる前記単語パス及び前記パスの順序に従って整列された当該単語パス及び当該パスに対応する単語と候補文字の組み合わせを前記文字列として推定する推定部と、
を有する文字認識装置。
【請求項７】
媒体上に表された複数の文字を含む文字列を撮影した画像を取得し、
前記画像から、前記複数の文字のそれぞれごとに、当該文字が写っていると推定される前記画像上の文字区間を検出し、
複数の前記文字区間のそれぞれごとに設定された、他の文字区間との相対的な位置関係を表すパスの集合である候補文字ラティスを求め、
複数の前記パスのそれぞれについて、当該パスに対応する前記文字区間に写っている文字の候補である候補文字を少なくとも一つ求め、
前記候補文字ラティスに含まれる複数の前記パスのうち、第１のパスと、前記第１のパスと少なくとも一部が重なっている２以上の連続したパスのうちの第２のパスとを、当該第１のパスの候補文字及び当該第２のパスの候補文字を含み、かつ、当該第２のパスと同一の文字区間に対応する第３のパスで置換するか、あるいは前記第１のパスが前記２以上の連続したパスの間に挿入されるように前記候補文字ラティスを修正し、
単語辞書に登録された複数の単語のうち、前記修正された候補文字ラティスにおける連続する２以上のパスのそれぞれに含まれる候補文字の組み合わせと少なくとも一部が一致する単語を前記文字列に含まれる可能性のある単語として検出し、当該検出された単語の前記文字列中の位置を表す単語パスを前記候補文字ラティスに追加した候補文字及び単語ラティスを求め、
前記候補文字及び単語ラティスにおいて、前記単語パスごとに、当該単語パスに対応する単語が前記文字列に含まれる確からしさを表す評価値を求め、
前記候補文字及び単語ラティスに含まれる前記単語パス及び前記パスの中から選択した前記文字列全体に対応する一列に連続した前記単語パス及び前記パスの配列ごとに前記評価値の合計値を求め、当該合計値が最も高い配列に含まれる前記単語パス及び前記パスの順序に従って整列された当該単語パス及び当該パスに対応する単語と候補文字の組み合わせを前記文字列として推定する、
ことを含む方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１３−９７５９０（Ｐ２０１３−９７５９０Ａ）
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願番号】特願２０１１−２４００９３（Ｐ２０１１−２４００９３）
【出願日】平成２３年１１月１日（２０１１．１１．１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願日】平成２３年１１月１日（２０１１．１１．１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]