(57)【要約】【課題】精度の高い文字認識を行うことが可能な文字認識装置、文字認識方法およびプログラムを提供する。【解決手段】実施形態の文字認識装置１０は、文字列画像を取得する文字列画像取得部１１と、文字列画像に対して文字認識処理を行い、１つの文字とみなされる文字領域ごとの認識結果を表す文字候補情報であって各々が１以上の候補文字を含む複数の文字候補情報を、文字列画像における各文字領域の並び順に従って接続した結合グラフを生成する結合グラフ生成部１２と、同一文字列を含む複数の文字列画像から生成された複数の結合グラフ、または、１つの文字列画像に対して複数の異なる文字認識処理を行うことで生成された複数の結合グラフを統合する結合グラフ統合部１３と、統合された結合グラフ、または、統合された結合グラフに基づいて得られる認識文字列を出力する出力部１５と、を備える。【選択図】図２
2017049911.tif 000002
【特許請求の範囲】
【請求項１】
文字列画像を取得する文字列画像取得部と、
前記文字列画像に対して文字認識処理を行い、１つの文字とみなされる文字領域ごとの認識結果を表す文字候補情報であって各々が１以上の候補文字を含む複数の前記文字候補情報を、前記文字列画像における各文字領域の並び順に従って接続した結合グラフを生成する結合グラフ生成部と、
同一文字列を含む複数の前記文字列画像から生成された複数の前記結合グラフ、または、１つの前記文字列画像に対して複数の異なる文字認識処理を行うことで生成された複数の前記結合グラフを統合する結合グラフ統合部と、
統合された前記結合グラフ、または、統合された前記結合グラフに基づいて得られる認識文字列を出力する出力部と、を備える文字認識装置。
【請求項２】
前記結合グラフ統合部は、統合する複数の前記結合グラフを第１の結合グラフおよび第２の結合グラフとしたときに、前記第１の結合グラフに含まれる前記文字候補情報と前記第２の結合グラフに含まれる前記文字候補情報との対応関係を特定し、前記第１の結合グラフと前記第２の結合グラフとで対応する前記文字候補情報同士を１つの前記文字候補情報に併合するとともに、前記第２の結合グラフに含まれる前記文字候補情報であって、前記第１の結合グラフに含まれるいずれの前記文字候補情報にも対応しない前記文字候補情報を前記第１の結合グラフに追加することにより、前記第１の結合グラフと前記第２の結合グラフとを統合する、請求項１に記載の文字認識装置。
【請求項３】
前記文字候補情報は、前記文字列画像における文字領域の位置を表す位置情報を含み、
前記結合グラフ統合部は、前記位置情報に基づいて、前記第１の結合グラフに含まれる前記文字候補情報と前記第２の結合グラフに含まれる前記文字候補情報との対応関係を特定する、請求項２に記載の文字認識装置。
【請求項４】
前記結合グラフ統合部は、同一文字列を含む複数の前記文字列画像から生成された複数の前記結合グラフを統合する場合に、複数の前記文字列画像の位置合わせを行って、当該位置合わせの結果に応じて変換した前記位置情報に基づいて、前記第１の結合グラフに含まれる前記文字候補情報と前記第２の結合グラフに含まれる前記文字候補情報との対応関係を特定する、請求項３に記載の文字認識装置。
【請求項５】
前記結合グラフ統合部は、前記第１の結合グラフに含まれる前記文字候補情報と前記第２の結合グラフに含まれる前記文字候補情報との対応関係を緩和法により特定する、請求項２に記載の文字認識装置。
【請求項６】
前記結合グラフは、前記文字列画像における文字領域の区切りが異なる複数のパターンに対応して、各パターンにおける前記文字候補情報の繋がりを表す接続パスを複数含み、
前記結合グラフ統合部は、前記第１の結合グラフと前記第２の結合グラフをそれぞれ単一の前記接続パスに分離した後、前記第１の結合グラフの前記接続パスと前記第２の結合グラフの前記接続パスとの対応関係を特定し、前記第１の結合グラフと前記第２の結合グラフとで対応する前記接続パスに含まれる前記文字候補情報同士を１つの前記文字候補情報に併合するとともに、前記第２の結合グラフの前記接続パスであって、前記第１の結合グラフのいずれの前記接続パスにも対応しない前記接続パスに含まれる前記文字候補情報を、前記第１の結合グラフのいずれかの前記接続パスに追加した上で、前記第１の結合グラフの複数の前記接続パスを結合することにより、前記第１の結合グラフと前記第２の結合グラフとを統合する、請求項２に記載の文字認識装置。
【請求項７】
前記結合グラフは、隣り合う前記文字候補情報同士の接続関係を表す接続情報を含み、
前記結合グラフ統合部は、前記第１の結合グラフに含まれる前記接続情報に対し、前記第２の結合グラフに含まれる前記文字候補情報との接続関係を追加することにより、前記第２の結合グラフに含まれる前記文字候補情報を前記第１の結合グラフに追加する、請求項２乃至６のいずれか一項に記載の文字認識装置。
【請求項８】
文字列画像を取得するステップと、
前記文字列画像に対して文字認識処理を行い、１つの文字とみなされる文字領域ごとの認識結果を表す文字候補情報であって各々が１以上の候補文字を含む複数の前記文字候補情報を、前記文字列画像における各文字領域の並び順に従って接続した結合グラフを生成するステップと、
同一文字列を含む複数の前記文字列画像から生成された複数の前記結合グラフ、または、１つの前記文字列画像に対して複数の異なる文字認識処理を行うことで生成された複数の前記結合グラフを統合するステップと、
統合された前記結合グラフ、または、統合された前記結合グラフに基づいて得られる認識文字列を出力するステップと、を含む文字認識方法。
【請求項９】
コンピュータに、
文字列画像を取得する機能と、
前記文字列画像に対して文字認識処理を行い、１つの文字とみなされる文字領域ごとの認識結果を表す文字候補情報であって各々が１以上の候補文字を含む複数の前記文字候補情報を、前記文字列画像における各文字領域の並び順に従って接続した結合グラフを生成する機能と、
同一文字列を含む複数の前記文字列画像から生成された複数の前記結合グラフ、または、１つの前記文字列画像に対して複数の異なる文字認識処理を行うことで生成された複数の前記結合グラフを統合する機能と、
統合された前記結合グラフ、または、統合された前記結合グラフに基づいて得られる認識文字列を出力する機能と、を実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、文字認識装置、文字認識方法およびプログラムに関する。
【背景技術】
【０００２】
ＯＣＲ（Optical  Character  Recognition/Reader）に代表される文字認識の分野では、認識精度の向上を図るための様々な取り組みがなされている。例えば、同一の文字列を含む複数の文字列画像に対してそれぞれ文字認識処理を行い、対応する文字について信頼度の高い認識結果を選択して最終的な認識文字列を得るといった技術が知られている。
【０００３】
しかし、信頼度の高い認識結果を選択する従来の方法では、例えば、信頼度の高い認識結果が必ずしも正解ではないこと、また、文字列画像における文字の区切りが正しくない場合もあることから、正しい認識文字列が得られない場合も多く、さらなる改善が求められている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−３３１２１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明が解決しようとする課題は、高精度な文字認識を行うことが可能な文字認識装置、文字認識方法およびプログラムを提供することである。
【課題を解決するための手段】
【０００６】
実施形態の文字認識装置は、文字列画像取得部と、結合グラフ生成部と、結合グラフ統合部と、出力部と、を備える。文字列画像取得部は、文字列画像を取得する。結合グラフ生成部は、前記文字列画像に対して文字認識処理を行い、１つの文字とみなされる文字領域ごとの認識結果を表す文字候補情報であって各々が１以上の候補文字を含む複数の前記文字候補情報を、前記文字列画像における各文字領域の並び順に従って接続した結合グラフを生成する。結合グラフ統合部は、同一文字列を含む複数の前記文字列画像から生成された複数の前記結合グラフ、または、１つの前記文字列画像に対して複数の異なる文字認識処理を行うことで生成された複数の前記結合グラフを統合する。出力部は、統合された前記結合グラフ、または、統合された前記結合グラフに基づいて得られる認識文字列を出力する。
【図面の簡単な説明】
【０００７】
【図１】図１は、文字認識装置のハードウェア構成例を示すブロック図である。
【図２】図２は、文字認識装置の機能的な構成例を示すブロック図である。
【図３】図３は、結合グラフの一例を示す図である。
【図４】図４は、結合グラフのデータ構造の一例を説明する図である。
【図５】図５は、累積結合グラフおよび新規結合グラフの一例を示す図である。
【図６】図６は、図５に示す新規結合グラフを累積結合グラフに統合することによって得られる新たな累積結合グラフを示す図である。
【図７】図７は、文字認識装置による処理手順の一例を示すフローチャートである。
【図８】図８は、図７のステップＳ１０５の統合処理の概要を説明するフローチャートである。
【図９】図９は、図８のステップＳ２０５の処理手順を示すフローチャートである。
【図１０】図１０は、図５に例示した累積結合グラフおよび新規結合グラフの一部の文字候補情報を抜き出して示す図である。
【図１１】図１１は、結合グラフを単一の接続パスに分離する様子を示す図である。
【発明を実施するための形態】
【０００８】
以下、実施形態の文字認識装置、文字認識方法およびプログラムを、図面を参照して詳細に説明する。
【０００９】
図１は、実施形態の文字認識装置１０のハードウェア構成例を示すブロック図である。文字認識装置１０は、例えば一般的なコンピュータとしてのハードウェア構成を採用することができる。この場合、文字認識装置１０は、図１に示すように、ＣＰＵ（Central  Processing  Unit）１０１、ＲＯＭ（Read  Only  Memory）１０２、ＲＡＭ（Random  Access  Memory）１０３、ＨＤＤ（Hard  Disk  Drive）１０４、デバイスＩ／Ｆ１０５、ネットワークＩ／Ｆ１０６、これらを接続するバス１０７などを備える。そして、文字認識装置１０は、例えば、ＣＰＵ１０１がＲＡＭ１０３をワークエリアとして利用し、ＲＯＭ１０２やＨＤＤ１０４などに格納されたプログラムを実行することによって、文字認識に関わる様々な機能を実現することができる。
【００１０】
デバイスＩ／Ｆ１０５は、液晶ディスプレイなどの表示装置１０８、キーボードやマウスなどの操作入力装置１０９、カメラやスキャナなどの画像入力装置１１０といった周辺機器を文字認識装置１０に接続するためのインタフェースである。ネットワークＩ／Ｆ１０６は、文字認識装置１０をインターネットやＬＡＮ（Local  Area  Network）などのネットワークに接続するための通信インタフェースである。
【００１１】
図２は、実施形態の文字認識装置１０の機能的な構成例を示すブロック図である。文字認識装置１０は、例えば、上記のハードウェアとソフトウェア（プログラム）との協働により実現される機能的な構成要素として、図２に示すように、文字列画像取得部１１と、結合グラフ生成部１２と、結合グラフ統合部１３と、認識文字列生成部１４と、出力部１５とを備える。
【００１２】
文字列画像取得部１１は、文字認識処理の対象となる文字列画像を取得する。文字列画像取得部１１は、例えば、カメラやスキャナなどの画像入力装置１１０から入力される文字列画像をデバイスＩ／Ｆ１０５を介して取得する構成であってもよいし、ネットワークに接続された外部装置から送信される文字列画像をネットワークＩ／Ｆ１０６を介して取得する構成であってもよい。また、文字列画像取得部１１は、予め取得した文字列画像をＨＤＤ１０４などに格納しておき、文字認識処理を実行する際にＨＤＤ１０４などから文字列画像を読み出す構成であってもよい。
【００１３】
文字列画像取得部１１は、取得した文字列画像に対して例えば二値化処理などの文字認識処理を行う上で必要な前処理を施し、前処理を施した文字列画像を結合グラフ生成部１２に渡す。なお、文字認識処理を行う上で必要な前処理は既存技術をそのまま利用できるため、詳細な説明は省略する。
【００１４】
結合グラフ生成部１２は、文字列画像取得部１１から受け取った文字列画像に対して文字認識処理を行い、この文字列画像に対する文字認識処理の結果を纏めたグラフである結合グラフを生成する。文字認識処理は、例えば、文字列画像から１つの文字とみなされる文字領域をすべて抽出し、それぞれの文字領域から特徴量を求めて、その特徴量に基づいて文字領域ごとに１以上の候補文字とその確からしさを表す認識スコアを取得する処理である。また、文字認識処理は、文字列画像に対する文字領域の区切りと文字領域に対する文字認識とを同時に行うものであってもよい。結合グラフ生成部１２は、文字列画像取得部１１から受け取った文字列画像に対し、以上のような文字認識処理を行って、個々の文字領域の文字列画像ＩＳにおける位置やサイズ、個々の文字領域から各々取得された候補文字や認識スコアなどを纏めることにより、結合グラフを生成する。なお、文字列画像ＩＳに対する具体的な文字認識処理の手法、例えば文字領域の抽出方法や文字認識に用いる特徴量などは既存技術をそのまま利用できるため、詳細な説明は省略する。
【００１５】
図３は、結合グラフ生成部１２により生成される結合グラフＧの一例を示す図である。結合グラフＧは、図３に示すように、文字列画像ＩＳにおいて１つの文字とみなされる文字領域ごとの認識結果を表す文字候補情報２１０を、文字列画像ＩＳにおける各文字領域の並び順に従って接続したグラフである。結合グラフＧは、文字列画像ＩＳにおける文字領域の区切りが異なる複数のパターンに対応して、複数の接続パスを含みうる。接続パスは、文字列画像ＩＳにおける文字候補情報２１０の繋がりを表す。図３の例では、「糸」と「色」が２つの文字とみなされる場合と、１つの「絶」という文字とみなされる場合とで、接続パスが異なる。また、「女」と「子」が２つの文字とみなされる場合と、１つの「好」という文字とみなされる場合とで、接続パスが異なる。このため、図３に示す結合グラフＧには、「糸」→「色」→「女」→「子」と繋がる接続パスと、「糸」→「色」→「好」と繋がる接続パスと、「絶」→「女」→「子」と繋がる接続パスと、「絶」→「好」と繋がる接続パスとの４種類の接続パスが含まれる。なお、文字列画像ＩＳにおける文字領域の区切りが一意に特定される場合は、結合グラフＧに含まれる接続パスは１つである。
【００１６】
結合グラフＧでは、隣り合う文字候補情報２１０同士の接続関係が接続情報２２０によって表される。ここでの接続とは、２つの文字候補情報２１０に各々対応する２つの文字が隣り合っていることを意味する。結合グラフＧを図３のようにグラフィカルに表すと、接続情報２２０は、隣り合う２つの文字候補情報２１０の間に配置される。なお、特殊な接続情報２２０として、文字列の先頭には開始位置２２１が配置され、文字列の末尾には終了位置２２２が配置される。
【００１７】
図３は、横方向に文字が並ぶ横文字列を含む文字列画像ＩＳを文字認識処理の対象とした場合に生成される結合グラフＧをグラフィカルに表した例であり、横方向に並ぶ文字候補情報２１０の各々が、文字列画像ＩＳにおいて１つの文字とみなされる文字領域ごとの認識結果を表している。なお、図３に示す各文字候補情報２１０の文字は、対応する文字領域に対する文字認識により取得される候補文字のうち、認識スコアが最も高い候補文字を示している。以下では、このような横文字列を含む文字列画像ＩＳを文字認識処理の対象とする場合について説明するが、縦方向に文字が並ぶ縦文字列を含む文字列画像ＩＳを文字認識処理の対象とする場合も、文字候補情報２１０の並びが横方向から縦方向に変わるだけで、結合グラフＧの基本的な構成は同様である。
【００１８】
ここで、結合グラフＧのデータ構造の具体例について説明する。図４は、結合グラフＧのデータ構造の一例を説明する図である。図４では、結合グラフＧの中から１つの接続情報２２０および当該接続情報２２０に関連する複数の文字候補情報２１０を部分的に抜き出したものを模式的に示している。
【００１９】
文字候補情報２１０は、上述したように、１つの文字とみなされる文字領域に対する文字認識により得られる情報であり、例えば、フラッグ、候補数、文字コード、スコア、サイズ、位置、右ポインタ、左ポインタなどを含む。フラッグは、当該文字候補情報２１０の属性などを表す。候補数は、当該文字候補情報２１０に含まれる文字候補の数を表す。文字コードは、当該文字認識情報２１０に含まれる１以上の候補文字それぞれの文字コードである。スコアは、それぞれの候補文字に対応する認識スコアである。サイズは、当該文字候補情報２１０に対応する文字領域（文字の外接矩形）のサイズである。位置は、当該文字候補情報２１０に対応する文字領域の文字列画像ＩＳにおける位置（本実施形態では文字領域の左端位置や右端位置）を表す位置情報である。右ポインタは、当該文字候補情報２１０の右端位置に対応する接続情報２２０を指し示すポインタである。左ポインタは、当該文字候補領域２１０の左端位置に対応する接続情報２２０を指し示すポインタである。なお、ポインタは対象となる情報が格納されたメモリ上の領域を特定できればよく、例えばメモリ上のアドレスやインデックスなどを用いることができる。
【００２０】
接続情報２２０は、隣り合う文字候補情報２１０を接続するための情報であり、フラッグ、複数の左ポインタ、複数の左接続位置、複数の右ポインタ、複数の右接続位置を含む。フラッグは、当該接続情報２２０の属性などを表す。左ポインタは、当該接続情報２２０を介して隣り合う文字候補情報２１０のうちの左側の文字候補情報２１０を指し示すポインタである。左接続位置は、左ポインタが指し示す文字候補情報２１０の位置を知るための情報であり、例えば当該文字候補情報２１０の位置情報である右端位置が登録される。右ポインタは、当該接続情報２２０を介して隣り合う文字候補情報２１０のうちの右側の文字候補情報２１０を指し示すポインタである。右接続位置は、右ポインタが指し示す文字候補情報２１０の位置を知るための情報であり、例えば当該文字候補情報２１０の位置情報である左端位置が登録される。
【００２１】
上述したように結合グラフＧは複数の接続パスを含む場合があるので、文字候補情報２１０同士の接続関係は複数通り存在する。このため、接続情報２２０には、複数の左ポインタおよび左接続位置と、複数の右ポインタおよび右接続位置とが設けられている。各ポインタは有効／無効を切り替えられるようになっており、それぞれのポインタが有効であるか無効であるかは、例えばフラッグに記載される。
【００２２】
なお、図３に示す例のように、隣り合う文字候補情報２１０同士の接続関係を２つの接続情報２２０で表すことも可能である。この場合、２つの接続情報２２０のうちの左側の接続情報２２０は、右ポインタの１つで右側の接続情報２２０を指し示し、その右ポインタに対応する右接続位置に、右側の接続情報２２０の右接続位置と同じ位置が登録される。また、２つの接続情報２２０のうちの右側の接続情報２２０は、左ポインタの１つで左側の接続情報２２０を指し示し、その左ポインタに対応する左接続位置に、左側の接続情報２２０の左接続位置と同じ位置が登録される。
【００２３】
図３に示す開始位置２２１は、右ポインタおよび右接続位置のみ登録された特殊な接続情報２２０であり、図３に示す終了位置２２２は、左ポインタおよび左接続位置のみ登録された特殊な接続情報２２０である。このような接続情報２２０の属性は、上述したフラッグに記載されている。なお、１つの結合グラフＧには開始位置２２１と終了位置２２２が通常１つずつ設けられるが、結合グラフＧ内に開始位置２２１や終了位置２２２が複数存在していてもよい。
【００２４】
本実施形態では、隣り合う文字候補情報２１０同士の接続関係を接続情報２２０によって表す構成の結合グラフＧを例示するが、これに限らない。例えば文字候補情報２１０が隣り合う他の文字候補情報２１０を直接指し示すように設定し、接続情報２２０を含まない構成の結合グラフＧとしてもよい。この場合、文字候補情報２１０には１つの接続情報２２０を指し示す左ポインタや右ポインタの代わりに、隣り合う他の文字候補情報２１０を指し示す複数の左ポインタや複数の右ポインタを設定すればよい。
【００２５】
結合グラフ生成部１２は、文字列画像取得部１１から文字列画像ＩＳを受け取るたびに、以上のような結合グラフＧを生成して結合グラフ統合部１３に渡す。特に本実施形態では、結合グラフ生成部１２が１つの文字列に対して複数の結合グラフＧを生成して結合グラフ統合部１３に渡す。例えば、結合グラフ生成部１２は、同一文字列を含む複数の文字列画像ＩＳに対してそれぞれ文字認識処理を行うことで複数の結合グラフＧを生成し、これら複数の結合グラフＧを結合グラフ統合部１３に渡す。また、結合グラフ生成部１２は、１つの文字列画像ＩＳに対して複数の異なる文字認識処理を行うことで複数の結合グラフＧを生成し、これら複数の結合グラフＧを結合グラフ統合部１３に渡すようにしてもよい。なお、同一文字列を含む複数の文字列画像ＩＳは、例えば画像ファイルのファイル名などで識別可能な構成とすることができる。
【００２６】
結合グラフ統合部１３は、１つの文字列に対して結合グラフ生成部１２により生成された複数の結合グラフＧ、すなわち、同一文字列を含む複数の文字列画像ＩＳから生成された複数の結合グラフＧ、または、１つの文字列画像ＩＳに対して複数の異なる文字認識処理を行うことで生成された複数の結合グラフＧを統合する。本実施形態では、結合グラフＧを１つずつ順次統合していく方法を採用する。以下では、それまでに統合された結合グラフＧを累積結合グラフＧ＿ａｃｃ（第１の結合グラフ）と呼び、新たに統合する結合グラフＧを新規結合グラフＧ＿ｎｅｗ（第２の結合グラフ）と呼ぶ。
【００２７】
結合グラフ統合部１３は、１つの文字列に対して結合グラフ生成部１２により生成された複数の結合グラフＧのうちの最初の結合グラフＧを受け取ると、これを初期の累積結合グラフＧ＿ａｃｃとして保存する。そして、結合グラフ統合部１３は、２番目の結合グラフＧを受け取るとこれを新規結合グラフＧ＿ｎｅｗとし、この新規結合グラフＧ＿ｎｅｗを累積結合グラフＧ＿ａｃｃに統合して、統合された結合グラフＧを新たな累積結合グラフＧ＿ａｃｃとして保存する。結合グラフ統合部１３は、３番目以降の結合グラフＧに対しても同様の処理を繰り返し、１つの文字列に対して結合グラフ生成部１２により生成されたすべての結合グラフＧの統合が終了すると、最終的に得られた累積結合グラフＧ＿ａｃｃを認識文字列生成部１４または出力部１５に渡す。
【００２８】
累積結合グラフＧ＿ａｃｃに対する新規結合グラフＧ＿ｎｅｗの統合は、以下のように行われる。すなわち、結合グラフ統合部１３は、累積結合グラフＧ＿ａｃｃに含まれる各文字候補情報２１０と新規結合グラフＧ＿ｎｅｗに含まれる各文字候補情報２１０との対応関係を特定し、対応する文字候補情報２１０同士をマージ（１つに併合）するとともに、累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０のいずれにも対応しない新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０を累積結合グラフＧ＿ａｃｃに追加することで、新規結合グラフＧ＿ｎｅｗを累積結合グラフＧ＿ａｃｃに統合する。
【００２９】
以下では、このような統合処理の具体例について、図５および図６を参照しながら説明する。図５（ａ）は累積結合グラフＧ＿ａｃｃの一例、図５（ｂ）は新規結合グラフＧ＿ｎｅｗの一例をそれぞれ示し、図６は、図５（ｂ）の新規結合グラフＧ＿ｎｅｗを図５（ａ）の累積結合グラフＧ＿ａｃｃに統合することによって得られる新たな累積結合グラフＧ＿ａｃｃを示している。図５では、累積結合グラフＧ＿ａｃｃや新規結合グラフＧ＿ｎｅｗに含まれる各文字候補情報２１０を区別するために、累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０にＡ１，Ａ２，Ａ３，Ａ４，Ａ５，Ａ６の符号を付し、新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０にＢ１，Ｂ２，Ｂ３，Ｂ４，Ｂ５の符号を付している。
【００３０】
本実施形態では、文字候補情報２１０に含まれる位置情報（文字列画像ＩＳにおける文字領域の左端位置や右端位置）を手掛かりとして、累積結合グラフＧ＿ａｃｃに含まれる各文字候補情報２１０と新規結合グラフＧ＿ｎｅｗに含まれる各文字候補情報２１０との対応関係を特定する。
【００３１】
結合グラフ統合部１３は、新規結合グラフＧ＿ｎｅｗに含まれる文字候補情報２１０のそれぞれについて、位置情報として登録されている文字領域の左端位置にほぼ一致する右接続位置を有する接続情報２２０と、位置情報として登録されている文字領域の右端位置にほぼ一致する左接続位置を有する接続情報２２０との組を、累積結合グラフＧ＿ａｃｃの中から検索する。ほぼ一致するとは、双方の位置の違いが予め定めた誤差範囲内にあることをいう。これにより、新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０の左右の接続情報２２０に対応する累積結合グラフＧ＿ａｃｃ側の２つの接続情報２２０が特定される。
【００３２】
次に、結合グラフ統合部１３は、特定した累積結合グラフＧ＿ａｃｃ側の２つの接続情報２２０に挟まれる１つの文字候補情報２１０が累積結合グラフＧ＿ａｃｃ内に存在するか否かを判断し、そのような文字候補情報２１０が累積結合グラフＧ＿ａｃｃ内にあれば、その文字候補情報２１０が新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０に対応するものと判断する。このとき、結合グラフ統合部１３は、累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０と新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０とが対応しているか否かを、さらに、双方の文字候補情報２１０に含まれる文字候補の一致度などを考慮して判断することが望ましい。例えば、双方の文字候補情報２１０に同じ文字候補が所定数以上含まれている場合に、双方の文字候補情報２１０が対応していると判断する。
【００３３】
結合グラフ統合部１３は、新規結合グラフＧ＿ｎｅｗに含まれる文字候補情報２１０のうち、累積結合グラフＧ＿ａｃｃ内で対応する文字候補情報２１０が見つかった文字候補情報２１０については、その新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０を、対応する累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０にマージ（１つに併合）する。具体的には、文字認識により得られた候補文字の文字コードと認識スコアをマージする。文字候補情報２１０をマージする際、候補文字の文字コードを認識スコア順にソートするが、同じ文字コードで認識スコアが異なる場合には、認識スコアが高い方を採用する。また、マージによって候補文字の数が予め定めた上限値を超える場合は、認識スコアが低い文字コードは登録しないようにする。
【００３４】
図５に示す例では、新規結合グラフＧ＿ｎｅｗ側のＢ１，Ｂ２，Ｂ３，Ｂ４が、累積結合グラフＧ＿ａｃｃ側のＡ１，Ａ２，Ａ３，Ａ４に各々対応するので、Ｂ１がＡ１、Ｂ２がＡ２、Ｂ３がＡ３、Ｂ４がＡ４にそれぞれマージされる。
【００３５】
また、結合グラフ統合部１３は、新規結合グラフＧ＿ｎｅｗに含まれる文字候補情報２１０のうち、累積結合グラフＧ＿ａｃｃ内で対応する文字候補情報２１０が見つからない文字候補情報２１０については、その新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０を、累積結合グラフＧ＿ａｃｃに新たな文字候補情報２１０として追加する。具体的には、結合グラフ統合部１３は、追加すべき文字候補情報２１０の右ポインタが、その文字候補情報２１０の右側の接続情報２２０に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０を指し示し、追加すべき文字候補情報２１０の左ポインタが、その文字候補情報２１０の左側の接続情報２２０に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０を指し示すように、これらのポインタを変更する。また、結合グラフ統合部１３は、追加すべき文字候補情報２１０の右側の接続情報２２０に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０に、その文字候補情報２１０を指し示す左ポインタおよび左接続位置を追加登録するとともに、追加すべき文字候補情報２１０の左側の接続情報２２０に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０に、その文字候補情報２１０を指し示す右ポインタおよび右接続位置を追加登録する。これにより、累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０のいずれにも対応しない新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０が、累積結合グラフＧ＿ａｃｃに追加される。
【００３６】
図５に示す例では、新規結合グラフＧ＿ｎｅｗ側のＢ５の累積結合グラフＧ＿ａｃｃ側の接続位置の間にＡ２およびＡ３の２つの文字候補情報２１０があり、新規結合グラフＧ＿ｎｅｗ側のＢ５に対応する累積結合グラフＧ＿ａｃｃ側の１つの文字候補情報２１０が見つからないため、新規結合グラフＧ＿ｎｅｗ側のＢ５が、累積結合グラフＧ＿ａｃｃ側のＡ１とＡ４の間に、新たな文字候補情報２１０として追加される。
【００３７】
結合グラフ統合部１３は、新規結合グラフＧ＿ｎｅｗ内のすべての文字候補情報２１０について、左からの接続順に以上のような統合処理を順次行っていく。また、新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０の左右に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０の組が複数見つかる場合があるが、その場合には、それぞれに対して上述した文字候補情報２１０のマージあるいは追加を行う。この統合によって、図５に示す累積結合グラフＧ＿ａｃｃおよび新規結合グラフＧ＿ｎｅｗから、図６に示す新たな累積結合グラフＧ＿ａｃｃが生成される。
【００３８】
次に、例外的な処理について説明する。新規結合グラフＧ＿ｎｅｗの文字候補情報２１０の左右に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０が１つも見つからない場合は、その文字候補情報２１０は誤読である可能性が高いため、累積結合グラフＧ＿ａｃｃへのマージや追加は行わない。
【００３９】
また、新規結合グラフＧ＿ｎｅｗの文字候補情報２１０の左側に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０が見つかったが、右側に対応する接続情報２２０が見つからない場合は、その文字候補情報２１０を累積結合グラフＧ＿ａｃｃに追加するとともに、その文字候補情報２１０の右側の接続情報２２０を、新たな終了位置２２２として累積結合グラフＧ＿ａｃｃに追加する。このとき、新たな終了位置２２２として追加する接続情報２２０が右ポインタと右接続位置を有する場合は、これらを削除する。また、新たな終了位置２２２として追加する接続情報２２０が、追加する文字候補情報２１０以外の文字候補情報２１０を指し示す左ポインタと左接続位置を有する場合は、これらも削除する。
【００４０】
また、新規結合グラフＧ＿ｎｅｗの文字候補情報２１０の右側に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０が見つかったが、左側に対応する接続情報２２０が見つからない場合は、その文字候補情報２１０を累積結合グラフＧ＿ａｃｃに追加するとともに、その文字候補情報２１０の左側の接続情報２２０を、新たな開始位置２２１として累積結合グラフＧ＿ａｃｃに追加する。このとき、新たな開始位置２２１として追加する接続情報２２０が左ポインタと左接続位置を有する場合は、これらを削除する。また、新たな開始位置２２１として追加する接続情報２２０が、追加する文字候補情報２１０以外の文字候補情報２１０を指し示す右ポインタと右接続位置を有する場合は、これらも削除する。
【００４１】
また、新規結合グラフＧ＿ｎｅｗの文字候補情報２１０の右側に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０が開始位置２２１である場合、その文字候補情報２１０を開始位置２２１の左に接続される文字候補情報２１０として累積結合グラフＧ＿ａｃｃに追加するとともに、累積結合グラフＧ＿ａｃｃ側の開始位置２２１にその文字候補情報２１０を指し示す左ポインタおよび左接続位置を追加し、フラッグの属性を書き換えることによって、開始位置２２１を通常の接続情報２２０に変更する。また、その文字候補情報２１０の左側の接続情報２２０を、新たな開始位置２２１として累積結合グラフＧ＿ａｃｃに追加する。このとき、新たな開始位置２２１として追加する接続情報２２０が左ポインタと左接続位置を有する場合は、これらを削除する。また、新たな開始位置２２１として追加する接続情報２２０が、追加する文字候補情報２１０以外の文字候補情報２１０を指し示す右ポインタと右接続位置を有する場合は、これらも削除する。
【００４２】
また、新規結合グラフＧ＿ｎｅｗの文字候補情報２１０の左側に対応する累積結合グラフＧ＿ａｃｃ側の接続情報２２０が終了位置２２２である場合、その文字候補情報２１０を終了位置２２２の右に接続される文字候補情報２１０として累積結合グラフＧ＿ａｃｃに追加するとともに、累積結合グラフＧ＿ａｃｃ側の終了位置２２２にその文字候補情報２１０を指し示す右ポインタおよび右接続位置を追加し、フラッグの属性を書き換えることによって、終了位置２２２を通常の接続情報２２０に変更する。また、その文字候補情報２１０の右側の接続情報２２０を、新たな終了位置２２２として累積結合グラフＧ＿ａｃｃに追加する。このとき、新たな終了位置２２２として追加する接続情報２２０が右ポインタと右接続位置を有する場合は、これらを削除する。また、新たな終了位置２２２として追加する接続情報２２０が、追加する文字候補情報２１０以外の文字候補情報２１０を指し示す左ポインタと左接続位置を有する場合は、これらも削除する。
【００４３】
累積結合グラフＧ＿ａｃｃは、複数の開始位置２２１や複数の終了位置２２２を持つ構成であってもよいが、これら開始位置２２１や終了位置２２２を１つに絞り込む必要がある場合は、以下のようにして絞り込みを行う。すなわち、複数の開始位置２２１のうち、最左端以外の開始位置２２１の右ポインタをすべて無効化する。同様に、複数の終了位置２２２のうち、最右端以外の終了位置２２２の左ポインタをすべて無効化する。文字候補情報２１０の右ポインタや左ポインタが指し示す接続情報２２０の対応するポインタが無効となっている場合には、その文字候補情報２１０の右ポインタや左ポインタも無効化する。この処理を無効化されるポインタがなくなるまで繰り返し実施する。そして、最後にポインタがすべて無効な接続情報２２０および文字候補情報２１０を削除する。
【００４４】
なお、以上は、隣り合う文字候補情報２１０同士の接続関係を接続情報２２０によって表す構成の結合グラフＧの統合処理について説明したが、文字候補情報２１０が隣り合う他の文字候補情報２１０を直接指し示す構成、つまり、文字候補情報２１０に接続情報２２０の機能も持たせた構成の結合グラフＧを用いる場合であっても、同様の統合処理を適用できる。この場合、上述の説明において、文字候補情報２１０の左右の接続情報２２０を、文字候補情報２１０内の接続情報に置き換えればよい。
【００４５】
結合グラフ統合部１３は、統合すべきすべての結合グラフＧについて、以上説明したような統合処理を繰り返し、すべての結合グラフＧの統合が終了すると、統合された結合グラフＧを認識文字列生成部１４または出力部１５に渡す。
【００４６】
認識文字列生成部１４は、結合グラフ統合部１３から統合された結合グラフＧを受け取り、この統合された結合グラフＧに対して、例えば知識処理などの所定の処理を施すことにより、最終的な文字認識結果である認識文字列を生成する。そして、認識文字列生成部１４は、生成した認識文字列を出力部１５に渡す。なお、最終的な文字認識結果である認識文字列を生成するための知識処理などの処理は既存技術をそのまま利用できるため、詳細な説明は省略する。
【００４７】
出力部１５は、認識文字列生成部１４により生成された認識文字列を出力する。また、出力部１５は、認識文字列生成部１４により生成された認識文字列に代えて、あるいは認識文字列とともに、結合グラフ統合部１３によって統合された結合グラフＧを出力する構成としてもよい。出力部１５が統合された結合グラフＧのみを出力する構成の場合、実施形態の文字認識装置１０は、上述した認識文字列生成部１４を備えない構成とすることができる。
【００４８】
出力部１５による認識文字列や統合された結合グラフＧの出力形態は、認識文字列や統合された結合グラフＧを表示装置１０８に表示する形態であってもよいし、ネットワークに接続された外部装置に、ネットワークＩ／Ｆ１０６を介して認識文字列や統合された結合グラフＧを送信する形態であってもよい。
【００４９】
次に、実施形態の文字認識装置１０の動作を説明する。図７は、文字認識装置１０による処理手順の一例を示すフローチャートである。文字認識装置１０は、例えば、図７のフローチャートで示す一連の処理手順に従って動作する。
【００５０】
文字認識装置１０が動作を開始すると、まず、文字列画像取得部１１が、文字認識処理の対象となる文字列画像ＩＳを取得し（ステップＳ１０１）、取得した文字列画像ＩＳに対して前処理を施して（ステップＳ１０２）、結合グラフ生成部１２に渡す。
【００５１】
次に、結合グラフ生成部１２が、文字列画像取得部１１から受け取った文字列画像ＩＳに対する文字認識処理を実行し（ステップＳ１０３）、文字列に対応する結合グラフＧを生成する（ステップＳ１０４）。本実施形態では、結合グラフ生成部１２が、同一文字列を含む複数の文字列画像ＩＳに対してそれぞれ文字認識処理を行う、あるいは、１つの文字列画像ＩＳに対して複数の異なる文字認識処理を行うことで、１つの文字列に対応する複数の結合グラフＧを生成する。結合グラフ生成部１２により生成された複数の結合グラフＧは、結合グラフ統合部１３に順次渡される。
【００５２】
次に、結合グラフ統合部１３が、結合グラフ生成部１２から受け取った複数の結合グラフＧ、つまり、１つの文字列に対応する複数の結合グラフＧの統合処理を実行し（ステップＳ１０５）、統合した結合グラフＧを認識文字列生成部１４に渡す。なお、上述したように、出力部１５が統合された結合グラフＧを出力する構成の場合は、結合グラフ統合部１３は、統合した結合グラフＧを出力部１５に渡す。
【００５３】
次に、認識文字列生成部１４が、結合グラフ統合部１３から受け取った統合された結合グラフＧに基づいて、最終的な文字認識結果である認識文字列を生成し（ステップＳ１０６）、この認識文字列を出力部１５に渡す。なお、出力部１５が統合された結合グラフＧのみを出力する構成の場合は、このステップＳ１０６の処理は省略される。
【００５４】
最後に、出力部１５が、認識文字列生成部１４から受け取った認識文字列を出力する（ステップＳ１０７）。なお、出力部１５は、認識文字列に代えて、あるいは認識文字列とともに、結合グラフ生成部１２から受け取った統合された結合グラフＧを出力してもよい。
【００５５】
図８は、図７のステップＳ１０５の統合処理の概要を説明するフローチャートであり、新規結合グラフＧ＿ｎｅｗを累積結合グラフＧ＿ａｃｃに順次統合する統合処理の手順を示している。なお、図中のｉはカウンタ値を示し、ｎは統合すべき結合グラフＧの数を示している。
【００５６】
統合処理が開始されると、結合グラフ統合部１３は、まずカウンタ値ｉを初期化（ｉ＝０）する（ステップＳ２０１）。その後、結合グラフ生成部１２により結合グラフＧが生成されると、結合グラフ統合部１３は、結合グラフ生成部１２から結合グラフＧを受け取り（ステップＳ２０２）、カウンタ値ｉをインクリメント（ｉ＝ｉ＋１）する（ステップＳ２０３）。
【００５７】
次に、結合グラフ統合部１３は、カウンタ値ｉが１であるかどうかを確認することにより、ステップＳ２０２で受け取った結合グラフＧが、統合すべき複数の結合グラフＧのうちの最初の結合グラフＧかどうかを判定する（ステップＳ２０４）。
【００５８】
ここで、ステップＳ２０２で受け取った結合グラフＧが最初の結合グラフＧである場合（ステップＳ２０４：Ｙｅｓ）、結合グラフ統合部１３は、その結合グラフＧをそのまま累積結合グラフＧ＿ａｃｃとして保存する（ステップＳ２０６）。一方、ステップＳ２０２で受け取った結合グラフＧが最初の結合グラフＧではない場合（ステップＳ２０４：Ｎｏ）、結合グラフ統合部１３は、その結合グラフＧを新規結合グラフＧ＿ｎｅｗとして、保存している累積結合グラフＧ＿ａｃｃに統合する（ステップＳ２０５）。そして、統合した結合グラフＧを、新たな累積結合グラフＧ＿ａｃｃとして保存する（ステップＳ２０６）。
【００５９】
その後、結合グラフ統合部１３は、カウンタ値ｉがｎに達したか否かを判断することにより、統合すべきすべての結合グラフＧを統合したか否かを判定する（ステップＳ２０７）。そして、統合していない結合グラフＧがあれば（ステップＳ２０７：Ｎｏ）、ステップＳ２０２に戻って以降の処理を繰り返し、すべての結合グラフＧを統合すると（ステップＳ２０７：Ｙｅｓ）、保存している累積結合グラフＧ＿ａｃｃを認識文字列生成部１４や出力部１５に渡して、一連の処理を終了する。
【００６０】
図９は、図８のステップＳ２０５の処理手順を示すフローチャートである。なお、図中のｊはカウンタ値を示し、ｍは新規結合グラフＧ＿ｎｅｗに含まれる文字候補情報２１０の数を示している。
【００６１】
結合グラフ統合部１３は、まずカウンタ値ｊを初期化（ｊ＝０）する（ステップＳ３０１）。その後、結合グラフ統合部１３は、新規結合グラフＧ＿ｎｅｗの左から順に文字候補情報２１０を１つ取り出し（ステップＳ３０２）、カウンタ値ｊをインクリメント（ｊ＝ｊ＋１）する（ステップＳ３０３）。
【００６２】
次に、結合グラフ統合部１３は、ステップＳ３０２で取り出した文字候補情報２１０、すなわち新規結合グラフＧ＿ｎｅｗ側の左からｊ番目の文字候補情報２１０の左右に対応する累積結合グラフＧ＿ａｃｃ側の２つの接続情報２２０を特定する（ステップＳ３０４）。そして、結合グラフ統合部１３は、ステップＳ３０４で特定した２つの接続情報２２０に挟まれる１つの文字候補情報２１０が、累積結合グラフＧ＿ａｃｃ側に存在するか否かを判定する（ステップＳ３０５）。
【００６３】
ここで、累積結合グラフＧ＿ａｃｃ側にそのような文字候補情報２１０があれば（ステップＳ３０５：Ｙｅｓ）、結合グラフ統合部１３は、その文字候補情報２１０を新規結合グラフＧ＿ｎｅｗ側の左からｊ番目の文字候補情報２１０に対応する累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０とみなし、新規結合グラフＧ＿ｎｅｗ側の左からｊ番目の文字候補情報２１０を、その累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０にマージする（ステップＳ３０６）。一方、累積結合グラフＧ＿ａｃｃ側にそのような文字候補情報２１０がなければ（ステップＳ３０５：Ｎｏ）、結合グラフ統合部１３は、新規結合グラフＧ＿ｎｅｗ側の左からｊ番目の文字候補情報２１０に対応する文字候補情報２１０が累積結合グラフＧ＿ａｃｃにはないと判断し、新規結合グラフＧ＿ｎｅｗ側の左からｊ番目の文字候補情報２１０を累積結合グラフＧ＿ａｃｃに追加する（ステップＳ３０７）。
【００６４】
その後、結合グラフ統合部１３は、カウンタ値ｊがｍに達したか否かを判断することにより、新規結合グラフＧ＿ｎｅｗに含まれるすべての文字候補情報２１０に対する処理が終了したか否かを判定する（ステップＳ３０８）。そして、処理が終了していない文字候補情報２１０があれば（ステップＳ３０８：Ｎｏ）、ステップＳ３０２に戻って以降の処理を繰り返し、すべての文字候補情報２１０に対する処理が終了すると（ステップＳ３０８：Ｙｅｓ）、一連の処理を終了する。
【００６５】
以上、具体的な例を挙げながら詳細に説明したように、実施形態の文字認識装置１０は、文字列画像ＩＳに対する文字認識処理により各々が１以上の候補文字を含む文字候補情報２１０を接続した結合グラフＧを生成し、１つの文字列に対して生成した複数の結合グラフＧを統合して、統合した結合グラフＧ、または、統合した結合グラフＧに基づいて生成した認識文字列を出力する。したがって、複数の文字認識結果から対応する文字について信頼度の高い認識結果を選択して最終的な認識文字列を得る従来の方法に比べて、誤読や文字の区切りの誤りに対して頑強な認識結果を出力することができ、高精度な文字認識を行うことが可能となる。
【００６６】
以下では、上述した実施形態の変形例について説明する。
＜変形例１＞
上述した実施形態では、複数の結合グラフＧにおける文字候補情報２１０の対応付けを文字候補情報２１０に含まれる位置情報に基づいて行っているが、複数の結合グラフＧが異なる文字列画像ＩＳから生成されたものである場合、対応する文字候補情報２１０の位置情報が必ずしも一致しているとは限らない。上述した実施形態では、位置情報の一致判定に誤差範囲を設けているが、同一の文字列を含む複数の文字列画像ＩＳにおいて、同じ文字が存在する位置が大きく異なることも想定される。
【００６７】
そこで、同一の文字列を含む複数の文字列画像ＩＳから生成された複数の結合グラフＧを統合する場合には、複数の文字列画像ＩＳの位置合わせ（レジストレーション）を行い、位置合わせの結果に応じて変換した位置情報に基づいて、複数の結合グラフＧにおける文字候補情報２１０同士の対応付けを行うようにしてもよい。
【００６８】
この場合、結合グラフ統合部１３は、結合グラフ生成部１２から結合グラフＧを受け取る際に、その結合グラフＧの生成に用いた文字列画像ＩＳも受け取る。そして、結合グラフＧの統合を行う際には、まず、文字列画像ＩＳの位置合わせを行い、その位置合わせの結果に応じて、統合する結合グラフＧに含まれる各文字候補情報２１０の位置情報を変換する。そして、変換した位置情報を用いて、上述した実施形態と同様の方法により文字候補情報２１０の対応付けを行う。なお、画像の位置合わせ（レジストレーション）は既存技術をそのまま適用できるため、詳細な説明は省略する。
【００６９】
本変形例では、文字列画像ＩＳの位置合わせの結果に応じて変換した位置情報に基づいて、複数の結合グラフＧにおける文字候補情報２１０の対応付けを行うことにより、複数の文字列画像ＩＳにおいて同じ文字が存在する位置が大きく異なる場合であっても、文字候補情報２１０の対応付けを適切に行って、高精度な文字認識を行うことが可能となる。
【００７０】
＜変形例２＞
複数の結合グラフＧにおける文字候補情報２１０の対応付けは、文字候補情報２１０の位置情報だけでなく、隣り合う文字候補情報２１０の連接性を手掛かりとして行うこともできる。以下では、隣り合う文字候補情報２１０の連接性を手掛かりとして文字候補情報２１０の対応付けの方法の一例について説明する。
【００７１】
図１０は、図５に例示した累積結合グラフＧ＿ａｃｃおよび新規結合グラフＧ＿ｎｅｗの一部の文字候補情報２１０を抜き出して示す図である。この図１０において、累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０（Ａ１，Ａ２，Ａ５）と新規結合グラフＧ＿ｎｅｗの側の文字候補情報２１０（Ｂ１，Ｂ２，Ｂ５）とを結ぶ線が、それぞれの文字候補情報２１０の対応付けの候補を表している。図１０に示すように、１つの文字候補情報２１０が複数の対応付けの候補を有する。
【００７２】
本変形例では、このような対応付けの候補の１つ１つにそれぞれスコアを準備する。スコアの初期値としては、文字列における各文字の相対的な位置関係から求まる位置ずれ量や認識結果の近さなどからスコアを設定する。例えば、文字列内の座標値を左上が０、右下が１となるように正規化して表現し、その正規化座標値に基づいてスコアを計算する。具体的には、累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０の正規化座標値と新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０の正規化座標値との差の絶対値の二乗を計算し、それら全部の和を取るなどの方法がある。また、累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０と新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０とで同じ文字コードがある場合に、それに対応する認識スコアの和を取り、最もよい認識スコアとなる文字コードを見つけ、その文字コードの認識スコアに基づいて、ここでの対応付け候補のスコアを決めるようにしてもよい。また、以上のような２つのスコアを合成することで、ここでの対応付け候補のスコアを決めるようにしてもよい。
【００７３】
次に、新規結合グラフＧ＿ｎｅｗにおいて隣り合う２つの文字候補情報２１０について、これらの文字候補情報２１０の対応付け候補となっている累積結合グラフＧ＿ａｃｃ側の隣り合う２つの文字候補情報２１０の組を探し出す。一般には、このような文字候補情報２１０の組は複数見つかる。
【００７４】
次に、新規結合グラフＧ＿ｎｅｗ側の２つの文字候補情報２１０と累積結合グラフＧ＿ａｃｃ側の２つの文字候補情報２１０との対応付け候補のスコアに基づいて、それぞれのスコアを更新する。例えば、双方の対応付け候補のスコアが平均スコアを上回れば、それぞれのスコアに対して所定の定数を加算し、双方の対応付け候補のスコアが平均スコアを下回れば、それぞれのスコアから所定の定数を減算し、それ以外はスコアの加減算を行わない。この処理を繰り返すことによって、尤もらしい対応付け候補のスコアが上昇し、尤もらしくない対応付け候補のスコアが下降することになる。以上の処理を一定回数、あるいはスコアの変動が閾値以下になるまで行う。
【００７５】
次に、対応付け候補のスコアが大きい順から、新規結合グラフＧ＿ｎｅｗ側の文字候補情報２１０と累積結合グラフＧ＿ａｃｃ側の文字候補情報２１０との対応付けを決定していくが、その過程では、すでに対応付けが決まった文字候補情報２１０を含む対応付けは採用しないようにする。また、対応付け候補のスコアが閾値を下回る場合は、その文字候補情報２１０同士の対応付けを採用しないようにする。これにより、最終的に妥当な文字候補情報２１０同士の対応付けを得ることができる。なお、ここでの対応付けは、新規結合グラフＧ＿ｎｅｗ側と累積結合グラフＧ＿ａｃｃ側のすべての文字候補情報２１０を１対１に対応付けるものではなく、１対１に対応しない文字候補情報２１０、つまり１対０や０対１の対応付けを含むものである。
【００７６】
以上のような対応付けの方法は、緩和法として知られている方法である。上述した実施形態の文字認識装置１０は、結合グラフ統合部１３における結合グラフＧの統合処理において、以上のような緩和法により文字候補情報２１０の対応付けを行うようにしてもよい。これにより、位置情報に基づく文字候補情報２１０の対応付けが困難な場合であっても、文字候補情報２１０の対応付けを適切に行って、高精度な文字認識を行うことが可能となる。
【００７７】
＜変形例３＞
次に、複数の結合グラフＧの統合方法の他の例を説明する。本例の統合方法は、複数の接続パスを有する累積結合グラフＧ＿ａｃｃと、複数の接続パスを有する新規結合グラフＧ＿ｎｅｗのそれぞれを単一の接続パスに分離する。そして、累積結合グラフＧ＿ａｃｃ側と新規結合グラフＧ＿ｎｅｗ側との接続パスの対応関係を特定し、対応する接続パスに含まれる文字候補情報２１０同士をマージする。また、累積結合グラフＧ＿ａｃｃ側のいずれの接続パスにも対応しない新規結合グラフＧ＿ｎｅｗ側の接続パスについては、その接続パスに含まれる文字候補情報２１０を、累積結合グラフＧ＿ａｃｃ側のいずれかの接続パスに追加する。その後、累積結合グラフＧ＿ａｃｃ側のすべての接続パスを結合して、新たな累積結合グラフＧ＿ａｃｃとする。
【００７８】
図１１は、結合グラフＧを単一の接続パスに分離する様子を示す図である。結合グラフＧから分離された単一の接続パスの集合を、以下では多重単線パスＭＰという。多重単線パスＭＰは、結合グラフＧに含まれる文字候補情報２１０を左から順に辿り、分岐があるごとに個別の接続パスを生成することで構築することができる。また、このとき、生成した各接続パスに含まれる各文字候補情報２１０が元の結合グラフＧ内のどの文字候補情報２１０に由来するかのデータを付属させておく。また、例えば文字候補情報２１０に含まれる認識スコアなどから接続パスのスコアを計算し、上位ｎ個の接続パスのみを残す、あるいは、スコアが閾値以上の接続パスのみを残すようにして、多重単線パスＭＰに含まれる接続パスの数に制限を設けるようにしてもよい。
【００７９】
本例では、以上のような接続パスの分離を、累積結合グラフＧ＿ａｃｃと新規結合グラフＧ＿ｎｅｗの双方に対して行う。そして、累積結合グラフＧ＿ａｃｃ側の接続パスと新規結合グラフＧ＿ｎｅｗ側の接続パスとの対応関係を、それぞれの接続パスに含まれる文字候補情報２１０同士のマッチングスコアを用いて特定する。具体的には、以下の方法により、累積結合グラフＧ＿ａｃｃ側の接続パスと新規結合グラフＧ＿ｎｅｗ側の接続パスとの対応関係を特定する。
【００８０】
累積結合グラフＧ＿ａｃｃ側の接続パスにおいて連続する文字候補情報２１０をＡ０，Ａ１，・・・，Ａｎ−１とし、新規結合グラフＧ＿ｎｅｗ側の接続パスにおいて連続する文字候補情報２１０をＢ０，Ｂ１，・・・，Ｂｍ−１とする。文字候補情報２１０同士のマッチングスコアは、それぞれの文字候補情報２１０に含まれる認識スコア、文字領域の位置やサイズなどを用いて計算する。このような文字候補情報２１０同士のマッチングスコアを接続パスの先頭から所定数の文字候補情報２１０の組み合わせについて計算し、その中で最良のマッチングスコアが得られた文字候補情報２１０同士を特定する。そして、累積結合グラフＧ＿ａｃｃ側の接続パスと新規結合グラフＧ＿ｎｅｗ側の接続パスのそれぞれで、最良のマッチングスコアが得られた文字候補情報２１０の次の文字候補情報２１０から所定数の文字候補情報２１０の組み合わせについて、文字候補情報２１０同士のマッチングスコアを同様に計算する。そして、得られた最良のマッチングスコアをそれまでのマッチングスコアに加算していく。
【００８１】
今、Ａｋ−１とＢｈ−１のマッチングスコアが最良であったとする。この場合、次のステップでは、Ａｋ〜Ａｋ＋ｄ−１のｄ個の文字候補情報２１０と、Ｂｈ〜Ｂｈ＋ｄ−１のｄ個の文字候補情報２１０との間で、合計２ｄ−１組の文字候補情報２１０の組み合わせについて各々マッチングスコアを計算する。そして、得られたマッチングスコアのうちの最良のマッチングスコアを、Ａｋ−１とＢｈ−１までの処理で得られているマッチングスコアに加算する。このとき、累積結合グラフＧ＿ａｃｃ側の接続パスと新規結合グラフＧ＿ｎｅｗ側の接続パスにおいて、最良のマッチングスコアが得られた文字候補情報２１０同士が連続しない場合、その間の文字候補情報２１０の数に応じて、マッチングスコアが低くなるように調整する。この処理を累積結合グラフＧ＿ａｃｃ側の接続パスの最後の文字候補情報２１０と新規結合グラフＧ＿ｎｅｗ側の接続パスの最後の文字候補情報２１０との組み合わせまで行い、累積結合グラフＧ＿ａｃｃ側の接続パスと新規結合グラフＧ＿ｎｅｗ側の接続パスとの最終的なマッチングスコアを得る。ここで使うスコア計算法はレーベンシュタイン距離と呼ばれるものの一種であり、マッチング方式はダイナミックプログラミング（ＤＰ）と呼ばれるものである。ただし、スコア計算の方法やマッチング方式は、以上の例に限定されるものではない。
【００８２】
以上の説明では、２ｄ−１組の文字候補情報２１０の組み合わせのうち、最良のマッチングスコアが得られた文字候補情報２１０の組み合わせをマッチングがとれた文字候補情報２１０の組み合わせとみなして処理を進めているが、マッチングスコアが高い順から上位Ｔ個の組み合わせを候補として残し、それぞれの組み合わせに対して上述と同様の処理を行うようにしてもよい。このような上位Ｔ個の組み合わせを残す手法はビームサーチと呼ばれる。
【００８３】
本例では、累積結合グラフＧ＿ａｃｃ側のすべての接続パスと、新規結合グラフＧ＿ｎｅｗ側のすべての接続パスとの組み合わせについて、以上の処理により接続パス同士のマッチングスコアを計算する。そして、マッチングスコアが最大となる累積結合グラフＧ＿ａｃｃ側の接続パスと新規結合グラフＧ＿ｎｅｗ側の接続パスとの組みを特定し、そのマッチングスコアが所定の閾値を超える場合に、これらの接続パスが対応しているものとして、これらの接続パスに含まれる文字候補情報２１０同士を上述した実施形態と同様の方法によりマージする。一方、マッチングスコアが閾値以下の接続パスの組については、新規結合グラフＧ＿ｎｅｗ側の接続パスに含まれる文字候補情報２１０を、上述した実施形態と同様の方法により、累積結合グラフＧ＿ａｃｃ側の接続パスに追加する。そして最後に、累積結合グラフＧ＿ａｃｃ側のすべての接続パスを結合して、新たな累積結合グラフＧ＿ａｃｃとする。
【００８４】
上述した実施形態の文字認識装置１０は、結合グラフ統合部１３における結合グラフＧの統合処理を、以上説明した本例の方法により行うようにしてもよい。これにより、累積結合グラフＧ＿ａｃｃや新規結合グラフＧ＿ｎｅｗの接続パスの数が多い場合であっても、結合グラフＧの統合処理を適切に行って、高精度な文字認識を行うことが可能となる。
【００８５】
＜補足説明＞
以上説明した実施形態の文字認識装置１０における各機能は、例えば、文字認識装置１０のハードウェア構成としてコンピュータを用いる場合、このコンピュータで所定のプログラムを実行することにより実現できる。文字認識装置１０として用いるコンピュータで実行されるプログラムは、例えば、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact  Disk  Read  Only  Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact  Disk  Recordable）、ＤＶＤ（Digital  Versatile  Disc）などのコンピュータで読み取り可能な記録媒体に記録されてコンピュータプログラムプロダクトとして提供される。
【００８６】
また、文字認識装置１０として用いるコンピュータで実行されるプログラムを、インターネットなどのネットワークに接続された他のコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、文字認識装置１０として用いるコンピュータで実行されるプログラムをインターネットなどのネットワーク経由で提供または配布するように構成してもよい。また、文字認識装置１０として用いるコンピュータで実行されるプログラムを、コンピュータ内部のＲＯＭ１０２などに予め組み込んで提供するように構成してもよい。
【００８７】
文字認識装置１０として用いるコンピュータで実行されるプログラムは、文字認識装置１０の上述した機能的な構成要素（文字列画像取得部１１、結合グラフ生成部１２、結合グラフ統合部１３、認識文字列生成部１４、および出力部１５）を含むモジュール構成となっており、実際のハードウェアとしては、例えば、ＣＰＵ１０１が上記記録媒体からプログラムを読み出して実行することにより、上記の各構成要素がＲＡＭ１０３などの主記憶部上にロードされ、上記の各構成要素が主記憶部上に生成されるようになっている。なお、文字認識装置１０の機能的な構成要素は、その一部または全部を、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field-Programmable  Gate  Array）などの専用のハードウェアを用いて実現することも可能である。
【００８８】
以上、本発明の実施形態を説明したが、この実施形態は例として提示したものであり、発明の範囲を限定することは意図していない。この新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００８９】
１０  文字認識装置
１１  文字列画像取得部
１２  結合グラフ生成部
１３  結合グラフ統合部
１４  認識文字列生成部
１５  出力部
２１０  文字候補情報
２２０  接続情報
Ｇ  結合グラフ
Ｇ＿ａｃｃ  累積結合グラフ
Ｇ＿ｎｅｗ  新規結合グラフ
ＩＳ  文字列画像
【図１】
2017049911.tif 000003
【図２】
2017049911.tif 000004
【図３】
2017049911.tif 000005
【図４】
2017049911.tif 000006
【図５】
2017049911.tif 000007
【図６】
2017049911.tif 000008
【図７】
2017049911.tif 000009
【図８】
2017049911.tif 000010
【図９】
2017049911.tif 000011
【図１０】
2017049911.tif 000012
【図１１】
2017049911.tif 000013