文字の読み順を決定するための読み順決定装置、方法及びプログラム
【課題】認識されていなかった文字領域の追加による文字領域の修正に対して適用可能なコンピュータの演算処理により文字の読み順を決定する技術を提供する。
【解決手段】画像データから文字認識処理により抽出された文字情報が文字の読み順に並んだ文字情報のリストと、画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを用意する。そして、文字情報のリストへの文字情報の追加要求に応答して、行情報のリストから、追加される文字の文字領域を包含する行枠を取り出し、該行枠に包含される文字領域を有する文字情報を文字情報のリストから全て求め、上記行枠に対応する文字の並び方向に対する位置に従って並び替えて、新たな文字の読み順を決定する。
【解決手段】画像データから文字認識処理により抽出された文字情報が文字の読み順に並んだ文字情報のリストと、画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを用意する。そして、文字情報のリストへの文字情報の追加要求に応答して、行情報のリストから、追加される文字の文字領域を包含する行枠を取り出し、該行枠に包含される文字領域を有する文字情報を文字情報のリストから全て求め、上記行枠に対応する文字の並び方向に対する位置に従って並び替えて、新たな文字の読み順を決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、画像データから文字認識処理により抽出された文字の集合に対して文字の読み順をコンピュータの演算処理により決定する技術に関する。特に本願発明は、文字認識誤りを正すための修正がなされた後においても正しく文字の読み順を決定する技術に関する。
【背景技術】
【０００２】
光学式文字読取装置（Optical Character Reader :OCR)によって取得されたテキスト・データに文字認識誤りがある場合、文字領域の修正に合わせて文字の読み順を編集する必要がある。ここで、文字認識の誤りが文字単位の認識ミスであり、文字領域の統合や分離によって修正される場合、新たな文字の読み順は修正前の文字領域に付与されている順番を利用してコンピュータの演算処理により決定できる。
【０００３】
例えば特許文献１は、ＯＣＲの前処理として、処理対象の領域を所定の識別条件に従い分け、画像領域を設定、各領域に読み順の設定を行い、ユーザが領域を統合する修正を指示すると、新規作成領域と重なる修正前の複数の領域を探索し、検出される複数の領域の重なり面積の最も大きい領域に付与されていた読み順を新規統合領域の読み順として引き継ぐ技術を開示する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２２５９６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１が開示する読み順の自動修正技術は、新規に作成される領域が修正前の領域と重なることを前提としている。そのため、上記自動修正技術をＯＣＲによる文字認識の誤りの修正時における文字の読み順の修正に適用しても、文字抜けのように全く認識されていなかった領域を新たに追加するような修正が行われる場合には、手作業でテキスト順序を編集しなければならない。
【０００６】
この発明は、上記の問題点を解決するためになされたものであって、認識されていなかった文字領域の追加による文字領域の修正に対して適用可能な、コンピュータの演算処理により文字の読み順を決定する技術を提供することを目的とする。また、本願発明は、文字領域の統合、分割、新規挿入の全ての修正に適用可能な、コンピュータの演算処理により文字の読み順を決定する技術を提供することを他の目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成する本願発明は、次のような、文字の読み順を決定するための読み順決定装置によって実現される。そのような読み順決定装置は、画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報が文字の読み順に並んだリストである文字情報のリストを格納する文字情報格納部と、前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、前記文字情報のリストへの文字情報の追加要求に応答して、前記行情報のリストから、追加された前記文字情報の文字領域データが示す領域を包含する行枠を有する行情報を検出する検出手段と、前記検出手段より検出された前記行情報の前記行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、前記部分集合内の各文字領域データを、検出された前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、前記部分集合内の文字領域データの並び順に基づいて前記文字情報のリストを更新することにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段とを含む。
【０００８】
前記読み順決定装置は更に、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、該文字の並び方向に前記現在の文字領域が存在しなくなるまで、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張する行枠候補生成手段と、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを含んでよい。ここで、前記行枠候補生成手段は、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、前記現在の文字領域を前記文字情報のリストの先頭として一連の処理を繰り返す。
【０００９】
更に前記読み順決定装置は、現在の前記行枠候補又は前記行情報のリストに登録された過去の前記行枠候補のいずれかに前記現在の文字領域が包含されることを条件に、前記行枠候補生成手段により現在の前記行枠候補を拡張する代わりに、前記現在の文字領域を包含する前記行枠候補を対応する文字の並び方向に対して垂直かつ前記現在の文字領域の中心点を基準に分割し、分割した行枠候補を該行枠候補に包含される文字領域データに基づいて修正し、分割により包含されなくなった各文字領域に対し該文字領域を行枠とする行情報を生成する行枠候補修正手段を含んでもよい。
【００１０】
あるいは前記読み順決定装置は、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、前記行枠候補を前記現在の文字領域を更に含む最小の行枠に拡張する拡張処理を一定の条件の下に実行する行枠候補生成手段と、前記行枠候補生成手段による前記拡張処理の実行前に、拡張によって生成されることになる行枠候補と前記文字並び方向とを基に文字の読み順が正しく決定されることを確認する確認部と、前記確認部による確認の失敗に応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを更に含んでもよい。ここで、前記行枠候補生成手段は、前記確認部による確認の成功を条件として前記拡張処理を実行し、前記確認が失敗した場合は、前記現在の文字領域を前記文字情報のリストの先頭として処理を繰り返す。
【００１１】
上記目的を達成する本願発明はまた、次のような文字の読み順を決定するための読み順決定装置によっても実現される。そのような読み順決定装置は、文字の読み順を決定するための読み順決定装置であって、画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報のリストである文字情報のリストを格納する文字情報格納部と、前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、前記行情報のリストから行情報を読み出して、読み出した前記行情報の行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、前記部分集合内の各文字領域データを、対応する前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、行情報ごとの並び替えられた前記文字領域データの部分集合を前記行の並びに順に繋ぎ合わせることにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段とを含む。
【００１２】
以上、文字の読み順を決定するための読み順決定装置として本願発明を説明した。しかし本願発明は、そのような読み順決定装置によって実施される文字の読み順を決定するための読み順決定方法、及びそのような読み順決定装置としてのコンピュータによってインストールして実行される文字の読み順を決定するための読み順決定プログラムとして把握することもできる。
【発明の効果】
【００１３】
本願発明では、画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを予め用意しておき、行枠内における文字の並び方向に従って行枠に包含される文字領域の文字の読み順を決定する。従って本願発明によれば、文字領域の統合、分割、新規挿入のいずれの修正が行われても、修正箇所を包含する行枠の文字並び方向に基づいて修正後の文字の読み順を決定できる。本願発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００１４】
【図１】本願発明の実施の形態に係る読み順決定装置１００（第１実施例）の機能構成の一例を示す。
【図２】（ａ）は、文字領域のフォーマットを説明する説明図を示す。（ｂ）は、行情報のフォーマットを説明する説明図を示す。
【図３】文字画像データの一例を示す。
【図４】（ａ）乃至（ｄ）はそれぞれ、圧縮プロセス（第１実施例）の各段階の説明図を示す。
【図５】（ａ）乃至（ｆ）はそれぞれ、文字領域が新規追加された場合における解凍プロセス（第１実施例）の各段階の説明図を示す。
【図６】圧縮処理部１２０による処理（第１実施例）の全体の流れの一例を示す。
【図７】解凍処理部１４０による処理（第１実施例）の全体の流れの一例を示す。
【図８】本願発明の実施の形態に係る読み順決定装置８００（第２実施例）の機能構成の一例を示す。
【図９】（ａ）は、文字画像データの他の一例を示す。（ｂ）は、図９（ａ）に示す文字画像データに対応する行枠を示す。
【図１０】解凍処理部８４０による処理（第２実施例）の全体の流れの一例を示す。
【図１１】（ａ）乃至（ｃ）はそれぞれ、処理対象の文字領域が既存の行枠に包含される場合における圧縮プロセスの各段階の説明図を示す。
【図１２】本願発明の実施の形態に係る読み順決定装置１２００（第３実施例）の機能構成の一例を示す。
【図１３】（ａ）乃至（ｃ）はそれぞれ、処理対象の文字領域が既存の行枠に包含される場合における改良された圧縮プロセス（第３実施例）の各段階の説明図を示す。
【図１４】圧縮処理部１２２０による処理（第３実施例）の全体の流れの一例を示す。
【図１５】図１４に示すステップ１４１４の修正処理の流れの一例を示すフローチャートである。
【図１６】本願発明の実施の形態に係る読み順決定装置１６００（第４実施例）の機能構成の一例を示す。
【図１７】（ａ）乃至（ｅ）はそれぞれ、圧縮プロセス（第４実施例）の各段階の説明をする説明図を示す。
【図１８】圧縮処理部１６２０による処理（第４実施例）の全体の流れの一例を示す。
【図１９】本願発明の実施の形態に係る読み順決定装置を実現するのに好適な情報処理装置のハードウェア構成の一例を示す。
【発明を実施するための形態】
【００１５】
以下、本願発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００１６】
（第１実施例） 図１は、本願発明の第１実施例に係る読み順決定装置１００の機能構成の一例を示す。読み順決定装置１００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部１１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部１１５と、文字情報のリストから行情報を生成する圧縮処理部１２０と、生成された行情報を格納する行情報格納部１３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部１０５と、行情報を用いて文字情報格納部１１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部１４０とを含む。なお、画像データ格納部１１０と修正部１０５は読み順決定装置１００の外に設け、読み順決定装置１００は修正部１０５から修正結果を受け取るように構成してもよい。そして読み順決定装置１００は、受け取った修正結果に基づいて文字情報格納部１１５に格納される文字情報のリストを更新するように構成してもよい。
【００１７】
画像データ格納部１１０が格納する画像データは、文字を含む画像データである。その格納単位は、任意の文書の１頁分ごとの画像データであっても、或いは任意の文書の１頁内のまとまりある領域ごとの画像データであってもよい。以下では、画像データは文書の１頁ごとの画像データであるとして説明する。
【００１８】
文字情報格納部１１５が格納する各文字情報は、画像データに含まれる各文字のテキスト・データ及び文字領域データを含む。ここで図２（ａ）を参照して文字領域データのフォーマットを説明する。まず文字Ｔ２０８が含まれる頁２００の左上隅を原点２０２とし、頁２００の上端をＸ軸２０４（水平軸）、左端をＹ軸２０６（垂直軸）として定める。するとほとんど全ての文字はＸ軸２０４又はＹ軸２０６に沿って並んでいると考えることができるので、上記のように定義した座標内において、文字Ｔ２０８を囲む矩形の文字領域２１０は、左上隅の座標（ｘ、ｙ）と、文字領域２１０の幅ｗと、文字領域２１０の高さｈとによって表すことができる。当然ながら文字領域データのフォーマットはこれに限定されず、矩形の全頂点の座標など等価な情報を含む他のフォーマットを利用してもよい。なお、本願の図面に示される全ての文字Ｔは、任意の言語の文字を示すことに留意されたい。また、本願の図に表された全ての座標は、上記説明した座標と同様にして定義されたものとする。
【００１９】
文字情報格納部１１５は、上記のように表される文字情報が文字の読み順にリストされた文字情報のリストを格納する。上述したようにこのような文字情報のリストは、ＯＣＲによる文字認識処理の結果として取得できる。以下に、一例として文字情報のデータ構造Symbolと文字情報のリストのデータ構造Pageとを示す。
calss Symbol {
char character;
int x, y, width, height;
}
class Page{
Symbol[] symbols;
}
【００２０】
圧縮処理部１２０は、文字情報格納部１１５から文字情報のリストを読み出して行情報のリストを生成し、行情報格納部１３５に格納する。ここで行情報とは、画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる情報をいう。本発明ではこのような行情報を導入し、行の並び順にリストされた行情報のリストを予め用意しておくことで、後に文字情報のリストが修正された場合でも正しく文字の読み順を決定することを可能とする。
【００２１】
ここで図２（ｂ）を参照して行情報のフォーマットを説明する。図２（ｂ）では簡単のため、同一方向に連続して並ぶ文字をＴ１２２２とＴ２２２６の２つとしている。これら２つの文字を囲む行枠２２８は、文字Ｔ１２２２の文字領域２２０と文字Ｔ２２２６の文字領域２２４とを囲む最小の矩形として定義される。従って行枠２２８は、図２（ｂ）に示す座標内において、行枠の左上隅の座標（ｘ、ｙ）と、行枠の幅ｗと、行枠の高さｈとによって表すことができる。また行枠内における文字の並び方向ｄは、Ｘ軸２１６又はＹ軸２１８のいずれか一方の方向を示す。なお、２以上の文字が同一方向に連続して並ばない場合、１つの文字の文字領域をそのまま行枠とし、文字の並び方向に関する情報のない行情報を生成する。以下では、このように1文字領域からなる行枠を単文字行枠と呼ぶ。当然ながら行枠のフォーマットはこれに限定されず、矩形の全頂点の座標など等価な情報を含む他のフォーマットを利用してもよい。なお本願発明では、ある文字領域に他の文字領域が完全に含まれることはないものとする。
【００２２】
行情報格納部１３５は、上記のように表される行情報が行の並び順にリストされた行情報のリストを格納する。以下に、一例として行情報のデータ構造Lineと行情報のリストのデータ構造Orderとを示す。
calss Line {
int x, y, width, height;
int dx, dy
}
class Order{
Line[] lines;
}
【００２３】
圧縮処理部１２０は、より具体的には、行枠候補生成部１２５と行情報登録部１３０とを含む。行枠候補生成部１２５は、文字情報格納部１１５に格納される文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化する。行枠候補生成部１２５はまた、最初の２つの文字領域データによって行枠候補における文字の並び方向を決定する。そして行枠候補生成部１２５は、決定した文字の並び方向に現在の文字領域が存在しなくなるまで、行枠候補を現在の文字領域を更に包含する最小の行枠に拡張する。文字の並び方向に現在の文字領域が存在しなくなると、行枠候補生成部１２５は、現在の文字領域を文字情報のリストの先頭の文字領域データとして、上記一連の処理を繰り返す。
【００２４】
行情報登録部１３０は、圧縮処理の開始時に行情報のリストを用意し、これをｎｕｌｌで初期化する。行情報登録部１３０はまた、行枠候補生成部１２５による上記処理において、文字の並び方向に現在の文字領域が存在しないことが検知されるたびに、現在の行枠候補を対応する文字の並び方向と共に行情報として行情報のリストの最後尾に登録し、行情報格納１３５に格納する。
【００２５】
ここで図３乃至図４を参照して、行枠候補生成部１２５及び行情報登録部１３０による圧縮処理の概要を説明する。図３は、２行からなる文字集合の画像データ３００を示す。図４は、圧縮プロセスの各段階を示す。処理の開始時において、文字情報格納部１１５には画像データ３００から抽出された文字情報のリストが格納されており、行情報格納部１３５には空の行情報のリストが格納されているものとする。なお、上述したように図３においてＴｍ（ｍは１から１８までの任意の整数）は任意の言語の文字を示す。また、図３においてＴｍを囲む矩形はＴｍの文字領域を示し、Ｔｍの真上又は真下にある数字はＴｍに付与された文字の読み順（文字情報のリストのリスト順）を示す。
【００２６】
まず、行枠候補生成部１２５は、文字情報のリストから最初に読み出したＴ１の文字情報の文字領域データで行枠候補４００を初期化する（図４（ａ）を参照）。続いて行枠候補生成部１２５は、現在の行枠候補４００を、次に読み出した２番目のＴ２の文字情報の文字領域データを更に含む最小の矩形に拡張し、現在の行枠候補４０２とする（図４（ｂ）を参照）。このとき行枠候補生成部１２５は、１番目と２番目に読み出したＴ１とＴ２の文字情報の文字領域データに基づき、行枠候補４０２内における文字の並び方向４０３を決定する（図４（ｂ）を参照）。
【００２７】
続いて行枠候補生成部１２５は、決定した文字の並び方向４０３に現在の文字領域が存在しなくなるまで、行枠候補４０３を現在の文字領域を更に包含する最小の行枠に順次拡張し、行枠候補４０４を得る（図４（ｃ）を参照）。続いて行枠候補生成部１２５は、次の文字情報、即ちＴ１０の文字領域データを現在の文字領域として読み出し、Ｔ１０の文字領域データが文字の並び方向４０３の方向とは異なる方向４０６にあることを検出する（図４（ｃ）の矢印４０６を参照）。
【００２８】
上記検出は行枠候補生成部１２５から行情報登録部１３０へ伝えられ、行情報登録部１３０は、現在の行枠候補４０４と対応する文字の並び方向４０３を行情報として、行情報格納部１３５の行情報のリストに登録する。行枠候補生成部１２５また、Ｔ１０の文字領域データを文字情報のリストの先頭の文字領域データとみなして、文字情報のリストに文字情報がなくなるまで図４（ａ）乃至図４（ｄ）までの処理と同様の処理を繰り返す（図４（ｄ）を参照）。処理の終わりと同時に行情報のリストが完成する。
【００２９】
修正部１０５は、画像データ格納部１１０と文字情報格納部１１５から、それぞれ文字情報と対応する画像データとを読み出して図示しないディスプレイ等の出力部に出力し、ユーザがオリジナルの画像とＯＣＲによる文字認識結果との比較により文字認識の誤りの有無を確認することを可能とする。修正部１０５はまた、ユーザが文字認識の誤りを見つけた場合に、ユーザから図示しないキーボード等の入力部を介して文字情報の修正の指示を受け取る。
【００３０】
ここで文字認識の誤りの修正は、文字領域の統合、分割、及び挿入のうちのいずれかであってよい。修正が文字領域の統合及び分割の場合、修正の指示は、既存の文字情報の削除と、削除する文字情報に代わる文字情報の追加である。一方、修正が文字領域の挿入の場合、修正の指示は文字情報の追加である。
【００３１】
従って文字情報の修正の指示が文字領域の統合、分割、挿入のいずれであっても、修正部１０５は、入力部を介してユーザから追加するべき文字のテキスト・データ及び対応する文字領域データを受け取る。修正部１０５は、受け取った文字情報を文字情報のリストの先頭又は最後尾に追加する。このため文字情報のリストに対し修正がなされた後は、後述する解凍処理部１４０によって文字の読み順を再度決定する必要がある。修正部１０５は、ユーザから受け取った追加すべき文字情報を文字情報のリストに追加することなく解凍処理部１４０に直接渡してもよい。
【００３２】
なお、文字情報の修正の指示が文字領域の統合及び分割の場合は、追加すべき文字情報を統合又は分割のために文字情報のリストから削除すべき文字情報の位置に挿入すれば、文字の読み順の修正は不要である。一方、追加位置を常に文字情報のリストの先頭又は最後尾とすれば、或いは常に解凍処理部１４０へ直接渡すようにすれば、修正内容に応じて処理を変える必要がない。どちらの構成を採用するにしても、文字領域の挿入による修正に対しては、文字の読み順の修正が必要である。
【００３３】
解凍処理部１４０は、文字情報のリストに対する修正要求に応答して、行情報のリストを用いて文字情報格納部１１５に格納される文字情報のリストの文字の読み順を決定する。上述したように、解凍処理部１４０は、修正部１０５から文字情報のリストの先頭又は最後尾への文字情報の追加の通知を受けてもよく、或いは修正部１０５から追加すべき文字情報そのものを受け取ってもよい。
【００３４】
解凍処理部１４０は、より具体的には、検出部１４５と、部分集合決定部１５０と、並び替え部１５５と、順序決定部１６０とを含む。検出部１４５は、文字情報のリストへの文字情報の追加要求に応答して、行情報格納部１３５に格納される行情報のリストから、追加する文字情報の文字領域データが示す領域を包含する行枠を検出する。
【００３５】
部分集合決定部１５０は、文字情報格納部１１５に格納される文字情報のリストから、検出部１４５により検出された行枠に包含される領域を示す全ての文字領域データからなる文字領域データの部分集合を求める。なお、追加する文字情報が解凍処理部１４０に直接渡される場合には、部分集合決定部１５０は追加する文字情報の文字領域データを、求めた文字領域データの部分集合に含める。
【００３６】
並び替え部１５５は、部分集合決定部１５０により求められた部分集合内の各文字領域データを、検出された行枠に対応する文字の並び方向に対する位置に従って並び替える。より具体的には、並び替え部１５５は、部分集合内の各文字領域データを、検出された行枠に対応する文字の並び方向に対する各文字領域データの示す領域の中心点座標の位置に従って並び替える。
【００３７】
順序決定部１６０は、並び替え部１５５により決定された部分集合についての文字領域データの並び順に従って、文字情報格納部１１５に格納される文字情報のリストを更新する。より具体的には、順序決定部１６０は、並び替え部１５５により決定された部分集合についての文字領域データの並び順により追加する文字情報の挿入位置を決定し、決定した挿入位置に追加する文字情報を挿入して文字情報のリストを更新する。結果、文字情報のリストにおける新たらしい文字の読み順が決定される。
【００３８】
ここで図５を参照して、解凍処理部１４０の上記各構成要素による解凍処理の概要を説明する。図５は、解凍プロセスの各段階を示す。処理の開始において、文字情報格納部１１５には画像データ５００から抽出されたＴ１、Ｔ２、Ｔ３、Ｔ４の文字情報を含む文字情報のリストが格納されているものとする（図５（ａ）参照）。また行情報格納部１３５には、Ｔ１、Ｔ２、Ｔ３、Ｔ４の文字領域を囲む最小の矩形である行枠５０２と、行枠５０２内における文字の並び方向５０３とからなる行情報を含む行情報のリストが格納されているものとする（図５（ａ）参照）。なお、図５（ａ）に示す画像データ５００において各文字の真上に記載されている数字は、各文字に付与された文字の読み順（文字情報のリストのリスト順）を示す。
【００３９】
このような状況で、文字認識の誤りを正すためにユーザが文字Ｔ３とＴ４の間に新たに文字ＴＸ５０４を挿入する修正を指示したとする（図５（ｂ）参照）。上述したように、修正の指示としてユーザから入力される情報は、文字ＴＸ５０４のテキスト・データとその文字領域データのみである。そのため、文字情報のリストのどの位置に文字ＴＸ５０４を挿入すべきか不明であり、文字の読み順を改めて決定する必要がある。そこで検出部１４５はまず行情報のリストを検索して、追加された文字ＴＸ５０４の文字領域を包含する行枠５０２と対応する文字並び方向５０３とを取得する（図５（ｃ）参照）。
【００４０】
続いて部分集合決定部１５０は、検出部１４５により検出された行枠５０２に包含される領域を示す文字領域データを文字情報のリストから全て読み出す（図５（ｄ）参照）。続いて並び替え部１５５は、部分集合決定部１５０により読み出された全文字領域データを、検出部１４５により検出された文字並び方向５０３に対する各文字領域データの中心座標の位置に従って並び替える（図５（ｅ））。すると文字領域データの部分集合に対し文字の読み順が正しく決定され（図５（ｆ））、結果として、文字ＴＸ５０４の文字情報を文字情報のリストに挿入する位置（文字Ｔ３とＴ４の間であり、リストの４番目の位置）が分かる。このように、追加文字の文字領域を含む行枠に関して文字の並び順を決定することによって、文字情報のリスト全体についての正しい文字の読み順を決定できる。
【００４１】
次に図６及び図７を参照して、本願発明の第１実施例に係る読み順決定装置１００による処理の流れを説明する。図６は、圧縮処理部１２０による圧縮処理の流れの一例を示すフローチャートである。図７は、解凍処理部１４０による解凍処理の流れの一例を示すフローチャートである。まず、図６を参照して、圧縮処理部１２０による圧縮処理の流れを説明する。
【００４２】
図６において、圧縮処理はステップ６００から開始し、行情報登録部１３０は、行情報を行の並び順に登録すべき行情報のリストＬＩＳＴ１を用意し、これにｎｕｌｌを設定して初期化する。また、行枠候補生成部１２５は、文字情報格納部１１５に格納される文字情報のリストから先頭の1文字目の文字領域Ｃを読み出してこれを行枠候補Ｌ１に設定すると共に、行枠候補Ｌ１に対応する文字の並び方向Ｌ２にｎｕｌｌを設定して、行情報の候補Ｌを初期化する（ステップ６０３）。
【００４３】
続いて行枠候補生成部１２５は、文字情報格納部１１５に次の文字領域が存在するか否かを判定する（ステップ６０６）。文字情報のリストにリストされる全ての文字情報が読み出されている場合（ステップ６０６：ＮＯ）、制御は行枠候補生成部１２５から行情報登録部１３０へ移り、行情報登録部１３０は、現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１に登録し、ＬＩＳＴ１を出力する（ステップ６０９）。そして処理は終了する。
【００４４】
一方、ステップ６０６において次の文字領域が存在する場合（ステップ６０６：ＹＥＳ）、行枠候補生成部１２５は、次の文字領域をＮとする（ステップ６１２）。続いて行枠候補生成部１２５は、行枠候補Ｌ１と次の文字領域ＮとをそれぞれＸ軸及びＹ軸に射影し、Ｘ軸及びＹ軸のどちらに射影した場合も射影区間が重ならないか否かを判定する（ステップ６１５）。これは、隣の行の文字などＸ軸又はＹ軸に沿って並んでいない文字を同一の行枠に含むことを避けるためである。
【００４５】
射影区間が重なる場合（ステップ６１５：ＮＯ）、行枠候補生成部１２５は、行枠候補Ｌ１の中心点（ｘ１、ｙ１）と次の文字領域Ｎの中心点（ｘ２、ｙ２）との座標の差（ｘ１−ｘ２、ｙ１−ｙ２）を求め、差の絶対値が大きな軸（ｍａｘ（｜ｘ１−ｘ２｜、｜ｙ１−ｙ２｜））の方向を指す単位ベクトルＤ（（０，１）又は（１，０））を求める（ステップ６１８）。ここで次の文字領域Ｎが現在の1文字目の文字領域Ｃに続く2文字目の文字領域である場合、文字の並び方向Ｌ２にＤを設定する。続いて行枠候補生成部１２５は、文字の並び方向Ｌ２と単位ベクトルＤが等しいか否かを判定する（ステップ６２１）。
【００４６】
文字の並び方向Ｌ２と単位ベクトルＤが等しい場合（ステップ６２１：ＹＥＳ）、行枠候補生成部１２５は、行枠候補Ｌ１を行枠候補Ｌ１と次の文字領域Ｎを含む最小の矩形で置換する（ステップ６２４）。そして処理はステップ６０６に戻り、行枠候補生成部１２５は一連の処理を繰り返す。一方、文字の並び方向Ｌ２と単位ベクトルＤが等しくない場合（ステップ６２１：ＮＯ）、制御は行枠候補生成部１２５から行情報登録部１３０へ移り、行情報登録部１３０は現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１の最後尾に追加し、また、現在の次の文字領域Ｎを文字情報のリストの一文字目とみなすため、現在の１文字目の文字領域Ｃに設定する（ステップ６２７）。そして処理はステップ６０３へ戻り、行枠候補生成部１２５は一連の処理を繰り返す。
【００４７】
次に、図７を参照して、解凍処理部１４０による解凍処理の流れを説明する。図７において、解凍処理はステップ７００から開始し、検出部１４５は、文字情報のリストへの文字情報の追加に応答して、行情報格納１３５に格納される行情報のリストから、追加された文字情報の文字領域データが示す領域を包含する行枠と対応する文字の並び方向からなる行情報を検出する。続いて、部分集合決定部１５０は、検出部１４５から行情報を受け取り、該行情報の行枠に包含される領域を示す文字領域データの部分集合Ｍを、文字情報格納部１１５に格納される文字情報のリストから求める（ステップ７０２）。
【００４８】
続いて並び替え部１５５は、部分集合決定部１５０から文字領域データの部分集合Ｍと行情報とを受け取り、部分集合Ｍを構成する各文字領域データを、受け取った行情報の文字の並び方向に対する各文字領域データの領域の位置に従って並び替える（ステップ７０４）。最後に順序決定部１６０は、文字領域データの部分集合Ｍについて決定された文字の並び順に基づいて、文字情報格納部１１５に格納される文字情報のリストを更新し、新たに文字の読み順を決定する（ステップ７０６）。そして処理は終了する。
【００４９】
（第２実施例）上述した第１実施例では、解凍処理部１４０は、文字情報のリストに対する修正要求に応答して解凍処理を行い文字の読み順を決定する。しかしながら解凍処理部１４０による解凍処理は、文字情報のリストを文字情報格納部１１５から読み出すタイミングで行うようにしてもよい。そこで該構成を採用する場合を第２実施例として以下に説明する。
【００５０】
図８は、本願発明の第２実施例に係る読み順決定装置８００の機能構成の一例を示す。読み順決定装置８００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部８１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部８１５と、文字情報のリストから行情報を生成する圧縮処理部８２０と、生成された行情報を格納する行情報格納部８３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部８０５と、行情報を用いて文字情報格納部８１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部８４０を含む。
【００５１】
第２実施例に係る読み順決定装置８００の上記各構成要素は、解凍処理部８４０を除いて第１実施例に係る読み順決定装置１００の対応する構成要素と変わらないので、以下では解凍処理部８４０についてのみ説明をする。但し、第２実施例では、文字情報格納部８１５から文字情報のリストが読み出されるたびに解凍処理部８４０による解凍処理が行われ文字の読み順が決定されるので、文字情報格納部８１５に格納される文字情報のリストは必ずしも文字の読み順に並んでいなくてよい。第２実施例に係る解凍処理部８４０は、部分集合決定部８４５と、並び替え部８５０と、順序決定部８５５とを含む。
【００５２】
部分集合決定部８４５は、文字情報格納部１１５からの文字情報のリストの読み出しに応答して、行情報格納８３５に格納される行情報のリストの先頭から順に行情報を読み出し、読み出した行情報の行枠に包含される領域を示す全ての文字領域データの部分集合を、文字情報格納部８１０に格納される文字情報のリストから求める。このとき部分集合決定部８４５は、求めた文字領域データの部分集合の中に、現在処理する行枠よりも先に読み出した行枠に対して求めた文字領域データの部分集合に含まれる文字領域データがあるか否かを確認する。そのような文字領域データがあった場合、部分集合決定部８４５は、現在の文字領域データの部分集合からその共通して含まれる文字領域データを削除する。かかる処理は、１つの文字領域が２つの行枠に含まれる場合における文字の読み順決定処理の不具合を解消するためである。
【００５３】
ここで、図９を参照して、１つの文字領域が２つの行枠に含まれるケースを具体的に説明する。図９（ａ）は、文字Ｔ１からＴ６までの文字の集合９００の画像データを示し、図９（ｂ）は、文字の集合９００に対応する行枠を示す。文字の添え字は文字の読み順を表している。図９（ａ）に示すように、２番目の文字Ｔ２の文字領域がＹ軸方向にずれてＹ軸に射影した場合に文字Ｔ１、Ｔ３のいずれの文字領域とも重ならないため、文字Ｔ１からＴ３に対応する行枠は、図９（ｂ）に示すようにそれぞれ単文字行枠Ｌ１、Ｔ２、Ｌ３となっている。一方、文字Ｔ４からＴ６はＸ軸方向に連続して並んでいるため、対応する行枠は、文字Ｔ４からＴ６の文字領域を含む１つの行枠Ｌ４となっている。そして、その文字領域のずれにより、文字Ｔ２の文字領域は、本来含まれるべき行枠Ｌ2のみならず行枠Ｌ4にも含まれてしまっている。
【００５４】
このような状況において行情報を用いて文字の読み順を決定すると、文字Ｔ２が2度登場する文字情報のリストが作成される。これを解決するには、行枠Ｌ4を用いて文字を並び替える際に、行枠Ｌ4に含まれる文字領域の集合から、先に処理した行枠Ｌ２にも共通して含まれる文字Ｔ２の文字領域を削除すればよい。そこで第２実施例に係る部分集合決定部８４５では、現在の処理対象である文字領域データの部分集合と先に求めた文字領域データの部分集合とに共通して含まれる文字領域データがあるか否かを判定し、共通して含まれる文字領域データがある場合はこれを現在の処理対象である文字領域データの部分集合から削除するようにした。部分集合決定部８４５により最終的に求められた行情報ごとの文字領域データの部分集合は、対応する行情報と共に後述する並び替え部８５０に渡される。
【００５５】
並び替え部８５０は、行情報のリストにおける行の並び順で、部分集合決定部８４５から行情報と対応する文字領域データの部分集合とのペアを受け取る。そして並び替え８５０は、行情報ごと、対応する部分集合の各文字領域データを対応する文字の並び方向に対する位置に従って並び替える。より具体的には、並び替え部８５０は、部分集合内の各文字領域データを、対応する文字の並び方向に対する各文字領域データの示す領域の中心点座標の位置に従って並び替える。
【００５６】
順序決定部８５５は、行情報のリストにおける行の並び順で、並び替え部８５０から行情報と対応する部分集合の並び替えられた文字領域データとを受け取る。そして順序決定部８５５は、行情報ごとの並び替えられた文字領域データの部分集合を行の並びに順に繋ぎ合わせて文字領域データのリストを作成し、該リストのリスト順を文字情報のリストについての文字の読み順として決定する。
【００５７】
次に図１０を参照して、解凍処理部８４０による解凍処理の流れを説明する。図１０において、解凍処理はステップ１０００から開始し、順序決定部８５５は、文字領域データを文字の読み順に登録するリストＬＩＳＴ２を用意し、これにｎｕｌｌを設定して初期化する。続いて制御は順序決定部８５５から部分集合決定部８４５へ移り、部分集合決定部８４５は、行情報格納８３５に格納されている行情報のリストからリスト順に行情報を読み出し、読み出すべき次の行情報が行情報のリストに存在するか否かを判定する（ステップ１００２）。読み出すべき次の行情報が行情報のリストに存在しない場合（ステップ１００２：ＮＯ）、制御は順序決定部８５５に戻り、順序決定部８５５は現在のリストＬＩＳＴ２を出力する。その後処理は終了する。
【００５８】
一方、読み出すべき次の行情報が行情報のリストに存在する場合（ステップ１００２：ＹＥＳ）、部分集合決定部８４５は、読み出した次の行情報の行枠に包含される領域を示す全ての文字領域データの部分集合Ｍを、文字情報格納部８１０に格納される文字情報のリストから求める（ステップ１００６）。続いて部分集合決定部８４５は、求めた文字領域データの部分集合Ｍの中に、現在のリストＬＩＳＴ２に登録されている文字領域データが含まれているか否かを確認し、含まれている場合にはその共通して含まれる文字領域データを部分集合Ｍから削除する（ステップ１００８）。上述したようにかかる処理は、１つの文字領域が２つの行枠に含まれる場合における文字の読み順決定処理の不具合を解消するためである。
【００５９】
ステップ１００８の処理の後、文字領域データの部分集合Ｍは対応する行情報と共に並び替え部８５０へ渡され、並び替え部８５０は、部分集合Ｍを構成する各文字領域データを、文字の並び方向に対する各文字領域データの領域の位置に従って並び替える（ステップ１０１０）。続いて順序決定部８５５は、並び替え部８５０によって並び替えられた文字領域データの部分集合ＭをリストＬＩＳＴ２の最後尾に追加する（ステップ１０１２）。その後処理はステップ１００２へ戻り、一連の処理が繰り返される。
【００６０】
（第３実施例）第２実施例に係る解凍処理に関連して説明した、１つの文字領域が２つの行枠に含まれるという問題は、任意の言語において起こり得るものである。これとは別に、ある文字領域が先に決定した行枠又は現在の行枠候補に含まれるという問題があり、これは日本語に特有の問題である。そこでこのような問題に対応した構成を第３実施例として以下に説明する。
【００６１】
まず図１１を参照して、その生成後に処理対象となった文字領域を含むこととなった行枠を使用して文字の読み順を決定した場合の不具合を説明する。図１１（ａ）は、２桁の数字を含む縦書きの文字列「平成２３年」の画像データ１１００を示す。この画像データ１１００から抽出された文字情報のリスト（リスト順は、「平」、「成」、「２」、「３」、「年」の順）に対し、第１実施例として説明した圧縮方法により行枠を作成することを考える。なお、数字「２３」は、ＯＣＲによる文字認識処理において「２」と「３」の２文字として認識されることに留意されたい。また「３」の文字領域は「２」の文字領域よりも「成」の文字領域に近いことに留意されたい。すると文字情報のリストから「２」が読み出された時点で図１１（ｂ）に示す行枠候補１１０２が現在の行枠候補として決定される。続いて数字「３」が読み出され行枠候補の拡張が検討される。しかし図１１（ｃ）に示すように数字「３」は現在の行枠候補１１０２に既に包含されている。
【００６２】
ここで仮に現在の行枠候補１１０２をこのまま行枠として採用するとする。すると解凍時において、行枠候補１１０２及び対応する文字の並び方向１１０４に基づいて文字の並び順を決定しようとすると、上述したように「３」の文字領域は「２」の文字領域よりも「成」の文字領域に近いため、「平」、「成」、「３」、「２」という順序で文字列が作成されてしまう。そこで第３実施例では、第１実施例に係る圧縮処理部１２０を改良して、ある文字領域が先に決定した行枠又は現在の行枠候補に含まれる場合に、当該ある文字を含まないよう先に決定した行枠又は現在の行枠候補を修正するようにした。以下、図１２を参照して第３実施例に係る読み順決定装置１２００を説明する。
【００６３】
図１２は、本願発明の第３実施例に係る読み順決定装置１２００の機能構成の一例を示す。読み順決定装置１２００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部１２１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部１２１５と、文字情報のリストから行情報を生成する圧縮処理部１２２０と、生成された行情報を格納する行情報格納部１２３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部１２０５と、行情報を用いて文字情報格納部１２１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部１２４０を含む。
【００６４】
第３実施例に係る読み順決定装置１２００の上記各構成要素は、圧縮処理部１２２０を除いて第１実施例に係る読み順決定装置１００の対応する構成要素と変わらないので、以下では圧縮処理部１２２０についてのみ説明をする。なお、第３実施例において、解凍処理部１２４０の代わりに第２実施例に係る解凍処理部８４０を採用してもよいことは言うまでもない。第３実施例に係る圧縮処理部１２２０は、行枠候補生成１２２５と、行枠候補修正部１２２７と、行情報登録部１２３０とを含む。
【００６５】
行枠候補生成１２２５は、文字情報格納部１２１５に格納される文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化する。行枠候補生成部１２２５はまた、最初の２つの文字領域データによって行枠候補における文字の並び方向を決定する。そして行枠候補生成部１２２５は、決定した文字の並び方向に現在の文字領域が存在しなくなるまで、行枠候補を現在の文字領域を更に包含する最小の行枠に拡張する。
【００６６】
但し第３実施例では、行枠候補生成１２２５は、現在の文字領域が現在の行枠候補又は過去に行枠として決定された行枠候補のいずれかに包含される場合には、拡張処理を行うことなく後述する行枠候補修正部１２２７を呼び出してその修正処理の結果の一部を取得する。行枠候補修正部１２２７から修正結果の一部を受け取った場合、行枠候補生成部１２２５は、受け取った一部の修正結果で行枠候補を初期化して上記一連の処理を繰り返す。行枠候補生成部１２２５はまた、文字の並び方向に現在の文字領域が存在しなくなった場合、現在の文字領域を文字情報のリストの先頭の文字領域データとみなして、上記一連の処理を繰り返す。
【００６７】
行枠候補修正部１２２７は、行枠候補生成部１２２５からの呼び出しに応答して、現在の文字領域を包含する行枠候補（現在の行枠候補又は過去に行枠として決定された行枠候補）に対して以下の修正処理１〜３を行う。即ち、行枠候補修正部１２２７は、修正対象の行枠候補を、対応する文字の並び方向に対して垂直かつ現在の文字領域の中心点を基準に分割する（修正処理１）。続いて行枠候補修正部１２２７は、分割により生成された２つの行枠候補のうち少なくとも１つの文字領域を包含する行枠候補を、包含する全ての文字領域を囲む最小の矩形に修正する（修正処理２）。続いて行枠候補修正部１２２７は、分割により分割後の２つの行枠候補のいずれにも包含されなくなった文字領域、および、現在の文字領域の各々に対して単文字行枠を生成する（修正処理３）。
【００６８】
上記修正処理２または修正処理３において得られた１以上の行枠候補は、現在の文字領域を包含する修正対象の行枠候補が現在の行枠候補である場合、行枠候補修正部１２２７により、行情報格納部１２３５に格納される行情報のリストの最後尾に登録される。一方、現在の文字領域を包含する修正対象の行枠候補が過去に行枠として決定された行枠候補である場合、修正処理２または修正処理３において得られた１以上の行枠候補は、行枠候補修正部１２２７により、行情報格納部１２３５に格納される行情報のリスト上の上記過去に行枠として決定された行枠候補と置換される。
【００６９】
また、上記行情報格納部１２３５への登録または置換において、修正処理２または修正処理３において得られた１以上の行枠候補の順序は、以下のとおりとする。現在の文字領域からなる単文字行枠を最後尾とする。その他の行枠候補については、分割前の行枠によって得られる文字の順序に矛盾しない順序とする。
【００７０】
ここで図１３を参照して、行枠候補修正部１２２７による上記修正処理１〜３を具体的に説明する。なお、行枠候補修正部１２２７は、図１１を参照して説明した文字列「平成２３年」の画像データ１１００から抽出された文字情報のリストを基に行情報を作成する行枠候補生成部１２２５により呼び出されて処理を開始するものとする。また、呼び出し時点において行枠候補生成部１２２５は、図１１（ｂ）に示す行枠１１０２を現在の行枠候補として生成しており、図１１（ｃ）に示すように現在の文字領域１１０６が、現在の行枠候補である行枠１１０２に包含されることを検出しているとする。
【００７１】
図１３（ａ）は、行枠候補修正部１２２７による修正処理１を示す。図１１（ｃ）に示す修正対象の行枠１１０２は、対応する文字の並び方向１１０４に対して垂直かつ現在の文字領域１１０６の中心点を基準に分割され、図１３（ａ）に示すように２つの行枠１３００と１３０２とが生成される。図１３（ｂ）は、行枠候補修正部１２２７による修正処理２を示す。図１３（ｂ）では、分割により生成された２つの行枠１３００と１３０２のうち、「平」と「成」の２つの文字領域を包含する行枠１３００が、包含する「平」と「成」の２つの文字領域を囲む最小の矩形である行枠１３０４に修正される。図１３（ｃ）は、行枠候補修正部１２２７による修正処理３を示す。図１３（ｃ）では、分割により分割後のいずれの行枠１３００と１３０２にも包含されなくなった「２」と「３」の２つの文字領域（図１３（ａ）参照）の各々に対し、単文字行枠１３０６、１３０８が生成されている。
【００７２】
図１２に戻って、行情報登録部１２３０は、圧縮処理の開始時に行情報のリストを行情報格納部１２３５に用意し、これをｎｕｌｌで初期化する。行情報登録部１２３０はまた、行枠候補生成部１２２５による拡張処理において、文字の並び方向に現在の文字領域が存在しないことが検知されるたびに、現在の行枠候補を対応する文字の並び方向と共に行情報として行情報格納部１２３５に格納される行情報のリストの最後尾に登録する。
【００７３】
次に図１４及び図１５を参照して、第３実施例に係る圧縮処理部１２２０による圧縮処理の流れを説明する。図１４は、第３実施例に係る圧縮処理部１２２０による圧縮処理の流れの一例を示すフローチャートである。図１５は、図１４に示すステップ１４１４の修正処理の流れの一例を示すフローチャートである。なお図１５に示すフローチャートは、四角１４５０で囲んだ部分の処理が新たに追加されたことを除いては、図６に示す第１実施例に係る圧縮処理部１２０による圧縮処理のフローチャートと同じである。そこで以下では、四角１４５０で囲んだ新たに追加されたステップについてのみ説明する。
【００７４】
ステップ１４１３の処理は、図６に示すフローチャートのステップ６１２に対応するステップ１４１２の直後に行われ、行枠候補生成部１２２５は、文字情報のリストから読み出した次の文字領域Ｎが、現在の行枠候補Ｌ１又は現在の行情報のリストＬＩＳＴ１に行枠として登録されている過去の行枠候補のいずれかに包含されるか否かを判定する。次の文字領域Ｎがいずれの行枠候補にも包含されない場合（ステップ１４１３：ＮＯ）、処理は図６に示すフローチャートのステップ６１５に対応するステップ１４１５へ進む。一方、次の文字領域Ｎがいずれかの行枠候補に包含される場合（ステップ１４１３：ＹＥＳ）、処理はステップ１４１４へ進み、行枠候補修正部１２２７は、次の文字領域Ｎを包含する現在の行枠候補Ｌ１又は過去の行枠候補を修正する修正処理を行う。修正処理の詳細は図１５を参照して説明する。修正処理の後処理はステップ１４０６へ戻る。
【００７５】
図１５に示す行枠候補修正部１２２７による修正処理は、ステップ１５００から開始し、行枠候補修正部１２２７は、文字領域Ｎの中心点を基準に、文字領域Ｎを包含する既存の行枠候補を該行枠候補に対応する文字の並び方向に対して垂直に分割する。続いて、行枠候補修正部１２２７は、分割後の２つの行枠候補のうち、１以上の文字領域を包含する行枠候補を該１以上の文字領域を囲む最小の行枠に修正する（ステップ１５０２）。行枠候補修正部１２２７はまた、分割によって分割後の２つの行枠候補のいずれにも包含されなくなった各文字領域に対し、該文字領域を行枠とする単文字行枠を生成する（ステップ１５０４）。
【００７６】
続いて行枠候補修正部１２２７は、ステップ１５０２において修正した分割後の行枠候補と、あれば、ステップ１５０４において生成した単文字行枠（文字領域Ｎから生成した単文字行枠を除く）とで、行情報のリストＬＩＳＴ１を更新する（ステップ１５０６）。続いて行枠候補修正部１２２７は、ステップ１５０４において文字領域Ｎから生成した単文字行枠で行枠候補Ｌ１を更新する（ステップ１５０８）。そして処理は終了する。
【００７７】
（第４実施例）第３実施例に関して説明した、ある文字領域が先に決定した行枠又は現在の行枠候補に包含されるという問題は、第３実施例の構成とは異なるもう１つの構成を採用することによっても解決される。そこで以下ではそのようなもう１つの構成を第４実施例として説明する。
【００７８】
第４実施例では、第１実施例に係る圧縮処理部１２０を改良して、行枠候補を現在の文字領域を更に含む最小の行枠に拡張する拡張処理を、拡張によって生成されることになる行枠候補と文字並び方向とを基に文字の読み順が正しく決定されることを条件として行うようにした。以下、図１６を参照して、第４実施例に係る読み順決定装置１６００を説明する。
【００７９】
図１６は、本願発明の第４実施例に係る読み順決定装置１６００の機能構成の一例を示す。読み順決定装置１６００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部１６１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部１６１５と、文字情報のリストから行情報を生成する圧縮処理部１６２０と、生成された行情報を格納する行情報格納部１６３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部１６０５と、行情報を用いて文字情報格納部１６１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部１６４０を含む。
【００８０】
第４実施例に係る読み順決定装置１６００の上記各構成要素は、圧縮処理部１６２０を除いて第１実施例に係る読み順決定装置１００の対応する構成要素と変わらないので、以下では圧縮処理部１６２０についてのみ説明をする。なお、第４実施例において、解凍処理部１６４０の代わりに第２実施例に係る解凍処理部８４０を採用してもよいことは言うまでもない。第４実施例に係る圧縮処理部１６２０は、行枠候補生成１６２５と、確認部１６２７と、行情報登録部１６３０とを含む。
【００８１】
行枠候補生成１６２５は、文字情報格納部１６１５に格納される文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化する。行枠候補生成部１６２５はまた、最初の２つの文字領域データによって行枠候補における文字の並び方向を決定する。そして行枠候補生成部１６２５は、行枠候補を現在の文字領域を更に包含する最小の行枠に拡張する拡張処理を一定の条件の下に実行する。ここで一定の条件とは、後述する確認部１６２７による確認が成功することをいい、行枠候補生成１６２５は、拡張処理前に確認部１６２７を呼び出して確認結果を受け取る。確認部１６２７による確認が成功した場合は、行枠候補生成１６２５は拡張処理を実行し、拡張後の行枠候補と次に読み出した現在の文字領域に対して確認結果が失敗となるまで繰り返し拡張処理を試みる。確認部１６２７による確認が失敗した場合は、行枠候補生成１６２５は、現在の文字領域を文字情報のリストの先頭とみなして上記一連の処理を繰り返す。
【００８２】
確認部１６２７は、行枠候補生成部１６２５からの呼び出しに応答して、拡張によって生成されることになる行枠候補と対応する文字の並び方向とを基に文字の読み順が正しく決定されることを確認する。該確認は次のように行ってよい。確認部１６２７はまず、実際に拡張処理を実行して行枠候補を生成し、これを現在の文字の並び方向とともに仮の行情報の候補とする。続いて確認部１６２７は、仮の行情報の候補を用いて文字領域の並び替えを行い文字の読み順を決定する。最後に確認部１６２７は、決定した文字の読み順と文字情報のリストにおけるリスト順とを比較し、一致するか否かを判定する。一致する場合、確認部１６２７は確認の成功を行枠候補生成１６２５へ返し、一致しない場合、確認部１６２７は確認の失敗を行枠候補生成１６２５へ返す。
【００８３】
行情報登録部１６３０は、圧縮処理の開始時に行情報のリストを行情報格納部１２３５に用意し、これをｎｕｌｌで初期化する。行情報登録部１６３０はまた、確認部１６２７による確認の失敗に応答して、現在の行枠候補を対応する文字の並び方向と共に行情報として行情報のリストの最後尾に登録する。
【００８４】
ここで図１７を参照して、確認部１６２７による確認処理の結果に基づく圧縮プロセスの各段階を説明する。処理の開始において、文字情報格納部１６１５には、図１７（ａ）に示す文字列「平成２３年」の画像データ１７００から抽出された文字情報のリストが格納されているものとする。なお、図１７（ａ）乃至（ｅ）に示す画像データ１７００は、図１１（ａ）に示す画像データ１１００と同じものである。まず、確認部１６２７により、仮の行情報の候補として行枠候補１７０２と文字の並び方向１７０４が検討されるところから開始するとする（図１７（ａ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「平」、「成」の順）と文字情報のリストにおけるリスト順（「平」、「成」の順）が一致するため、行枠候補生成１６２５による拡張処理が実行され、仮の行情報が現在の行情報の候補として確定する。
【００８５】
続いて確認部１６２７により、現在の行情報の候補が「２」の文字領域を含むように拡張され、仮の行情報の候補として行枠候補１７０６と文字の並び方向１７０４が検討される（図１７（ｂ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「平」、「成」、「３」、２」の順）と文字情報のリストにおけるリスト順（「平」、「成」、「２」、（「３」）の順）は一致しないため、行枠候補生成１６２５による拡張処理は実行されず、現在の行情報の候補が行情報として行情報のリストの最後尾に登録される（図１７（ｃ）の行枠１７０８と文字の並び方向１７１０を参照）。また、現在の行情報の候補が「２」の文字領域で初期化される。
【００８６】
続いて確認部１６２７により、上記「２」の文字領域で初期化された現在の行情報の候補が「３」の文字領域を含むように拡張され、仮の行情報の候補として行枠候補１７１２と文字の並び方向１７１４が検討される（図１７（ｃ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「２」、「３」の順）と文字情報のリストにおけるリスト順（「２」、「３」の順）が一致するため、行枠候補生成１６２５による拡張処理が実行され、仮の行情報が現在の行情報の候補として確定する。
【００８７】
続いて確認部１６２７により、現在の行情報の候補が「年」の文字領域を含むように拡張され、仮の行情報の候補として行枠候補１７１６と文字の並び方向１７１４が検討される（図１７（ｄ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「２」、「年」、「３」の順）と文字情報のリストにおけるリスト順（「２」、「３」、年」の順）は一致しないため、行枠候補生成１６２５による拡張処理は実行されず、現在の行情報の候補が行情報として行情報のリストの最後尾に登録される（図１７（ｅ）の行枠１７２０と文字の並び方向１７１８を参照）。また、現在の行情報の候補が「年」の文字領域で初期化される。このように第４実施例では、正しい文字の読み順が決定されることを条件に拡張処理が行われる。
【００８８】
次に図１８を参照して、第４実施例に係る圧縮処理部１６２０による圧縮処理の流れを説明する。図１８は、第４実施例に係る圧縮処理部１６２０による圧縮処理の流れの一例を示すフローチャートである。
【００８９】
図１８に示す圧縮処理はステップ１８００から開始し、行情報登録部１６３０は、行情報を行の並び順に登録すべき行情報のリストＬＩＳＴ１を用意し、これにｎｕｌｌを設定して初期化する。また、行枠候補生成部１６２５は、文字情報格納部１６１５に格納される文字情報のリストから先頭の1文字目の文字領域Ｃを読み出してこれを行枠候補Ｌ１に設定すると共に、行枠候補Ｌ１に対応する文字の並び方向Ｌ２にｎｕｌｌを設定して、行情報の候補Ｌを初期化する（ステップ１８０２）。
【００９０】
続いて行枠候補生成部１６２５は、文字情報格納部１６１５に次の文字領域が存在するか否かを判定する（ステップ１８０４）。文字情報のリストに次の文字領域が存在する場合（ステップ１８０４：ＹＥＳ）、次の文字領域をＮとし、行枠候補Ｌ１の中心点（ｘ１、ｙ１）と次の文字領域Ｎの中心点（ｘ２、ｙ２）との差の絶対値が大きな軸（ｍａｘ（｜ｘ１−ｘ２｜、｜ｙ１−ｙ２｜））の方向を指す単位ベクトル（（０，１）又は（１，０））を文字の並び方向Ｄとして決定して、文字の並び方向Ｌ２に設定する（ステップ１８０６）。
【００９１】
ステップ１８０６の後行枠候補生成部１６２５は確認部１６２７を呼び出し、確認部１６２７は、行枠候補Ｌ１と次の文字領域Ｎを含む最小の矩形を仮の行枠候補Ｌ‘１、及び文字の並び方向Ｌ２を仮の文字の並び方向Ｌ‘２として仮の行情報の候補Ｌ’を生成する（ステップ１８０８）。そして確認部１６２７は、仮の行情報の候補Ｌ’を次の行枠として、図１０に示すフローチャートの四角１０５０で囲んだサブルーチンを実行し、実行結果の文字領域の並びが、現在の１文字目の文字領域Ｃから次の文字領域Ｎまでの文字情報のリストにおけるリスト順に一致するか否かを判定する（ステップ１８０８）。
【００９２】
実行結果の文字領域の並びが文字情報のリストにおけるリスト順に一致しない場合（ステップ１８０８：ＮＯ）、処理はステップ１８１８へ進み、行情報登録部１６３０は現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１の最後尾に追加する。また、行情報登録部１６３０は現在の次の文字領域Ｎを、文字情報のリストの一文字目とみなすために、現在の１文字目の文字領域Ｃに設定する。そして処理はステップ１８０２へ戻り、行枠候補生成部１６２５は一連の処理を繰り返す。
【００９３】
一方、実行結果の文字領域の並びが文字情報のリストにおけるリスト順に一致する場合（ステップ１８０８：ＹＥＳ）、行枠候補生成部１６２５は文字情報のリストに次の文字領域が存在するか否かを判定し（ステップ１８１０）、次の文字領域が存在する場合（ステップ１８１０：ＹＥＳ）、該次の文字領域を現在の次の文字領域Ｎとすると共に、仮の行情報の候補Ｌ’を現在の行情報の候補Ｌとして確定する（ステップ１８１２）。そして処理はステップ１８０８へ戻り、確認部１６２７と行枠候補生成部１６２５は一連の処理を繰り返す。
【００９４】
一方、ステップ１８１０において次の文字領域が存在しない場合、行枠候補生成部１６２５は仮の行情報の候補Ｌ’を現在の行情報の候補Ｌとして確定する（ステップ１８１４）。ステップ１８１４から、又は、ステップ１８０４において文字情報のリストにリストされる全ての文字情報が読み出されている場合、処理はステップ１８１６へ進み、行情報登録部１６３０は、現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１の最後尾に登録し、ＬＩＳＴ１を出力する。そして処理は終了する。
【００９５】
図１９は、本願発明の任意の実施例に係る読み順決定装置としてのコンピュータ５０のハードウェア構成の一例を示した図である。コンピュータ５０は、バス２に接続されたメインＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、及びＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【００９６】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ１に命令を与え、本願発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ５０にインストールされ、コンピュータ５０を本願発明の任意の実施例に係る読み順決定装置として機能させる読み順決定プログラムや、行情報のリスト、文字情報のリストといったデータを記録することができる。
【００９７】
上記読み順決定プログラムは、圧縮モジュールと、修正モジュールと、解凍モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、圧縮処理部１２０、８２０、１２２０、又は１６２０、修正部１０５、８０５、１２０５、又は１６０５、解凍処理部１４０、８４０、１２４０、１６４０としてそれぞれ機能させる。圧縮モジュールは、行枠候補生成モジュール、行枠情報登録モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、行枠候補生成部１２５、８２５、行情報登録部１３０、８３０としてそれぞれ機能させる。これに代えて、圧縮モジュールは、行枠候補生成モジュール、行枠候補修正モジュール、行枠情報登録モジュールとを含んでもよい。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、行枠候補生成部１２２５、行枠候補修正部１２２７、行情報登録部１２３０としてそれぞれ機能させる。或いは、圧縮モジュールは、行枠候補生成モジュール、確認モジュール、行枠情報登録モジュールとを含んでもよい。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、行枠候補生成部１６２５、確認部１６２７、行情報登録部１６３０としてそれぞれ機能させる。解凍モジュールは、検出モジュール、部分集合決定モジュール、並び替えモジュール、順序決定モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、検出部１４５、１２４５、１６４５、部分集合決定部１５０、１２５０、１６５０、並び替え部１５５、１２５５、１６５５、順序決定部１６０、１２６０、１６６０としてそれぞれ機能させる。これに代えて解凍モジュールは、部分集合決定モジュール、並び替えモジュール、順序決定モジュールとを含んでもよい。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、部分集合決定部８４５、並び替え部８５０、順序決定部８５５としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【００９８】
コンピュータ５０は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータ５０は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータ５０は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータ５０は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【００９９】
以上の説明により、コンピュータ５０は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本願発明の必須構成要素となるわけではない。
【０１００】
以上、実施形態を用いて本願発明の説明をしたが、本願発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本願発明の技術的範囲に含まれる。
【０１０１】
なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。
【技術分野】
【０００１】
本願発明は、画像データから文字認識処理により抽出された文字の集合に対して文字の読み順をコンピュータの演算処理により決定する技術に関する。特に本願発明は、文字認識誤りを正すための修正がなされた後においても正しく文字の読み順を決定する技術に関する。
【背景技術】
【０００２】
光学式文字読取装置（Optical Character Reader :OCR)によって取得されたテキスト・データに文字認識誤りがある場合、文字領域の修正に合わせて文字の読み順を編集する必要がある。ここで、文字認識の誤りが文字単位の認識ミスであり、文字領域の統合や分離によって修正される場合、新たな文字の読み順は修正前の文字領域に付与されている順番を利用してコンピュータの演算処理により決定できる。
【０００３】
例えば特許文献１は、ＯＣＲの前処理として、処理対象の領域を所定の識別条件に従い分け、画像領域を設定、各領域に読み順の設定を行い、ユーザが領域を統合する修正を指示すると、新規作成領域と重なる修正前の複数の領域を探索し、検出される複数の領域の重なり面積の最も大きい領域に付与されていた読み順を新規統合領域の読み順として引き継ぐ技術を開示する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２２５９６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１が開示する読み順の自動修正技術は、新規に作成される領域が修正前の領域と重なることを前提としている。そのため、上記自動修正技術をＯＣＲによる文字認識の誤りの修正時における文字の読み順の修正に適用しても、文字抜けのように全く認識されていなかった領域を新たに追加するような修正が行われる場合には、手作業でテキスト順序を編集しなければならない。
【０００６】
この発明は、上記の問題点を解決するためになされたものであって、認識されていなかった文字領域の追加による文字領域の修正に対して適用可能な、コンピュータの演算処理により文字の読み順を決定する技術を提供することを目的とする。また、本願発明は、文字領域の統合、分割、新規挿入の全ての修正に適用可能な、コンピュータの演算処理により文字の読み順を決定する技術を提供することを他の目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成する本願発明は、次のような、文字の読み順を決定するための読み順決定装置によって実現される。そのような読み順決定装置は、画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報が文字の読み順に並んだリストである文字情報のリストを格納する文字情報格納部と、前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、前記文字情報のリストへの文字情報の追加要求に応答して、前記行情報のリストから、追加された前記文字情報の文字領域データが示す領域を包含する行枠を有する行情報を検出する検出手段と、前記検出手段より検出された前記行情報の前記行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、前記部分集合内の各文字領域データを、検出された前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、前記部分集合内の文字領域データの並び順に基づいて前記文字情報のリストを更新することにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段とを含む。
【０００８】
前記読み順決定装置は更に、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、該文字の並び方向に前記現在の文字領域が存在しなくなるまで、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張する行枠候補生成手段と、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを含んでよい。ここで、前記行枠候補生成手段は、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、前記現在の文字領域を前記文字情報のリストの先頭として一連の処理を繰り返す。
【０００９】
更に前記読み順決定装置は、現在の前記行枠候補又は前記行情報のリストに登録された過去の前記行枠候補のいずれかに前記現在の文字領域が包含されることを条件に、前記行枠候補生成手段により現在の前記行枠候補を拡張する代わりに、前記現在の文字領域を包含する前記行枠候補を対応する文字の並び方向に対して垂直かつ前記現在の文字領域の中心点を基準に分割し、分割した行枠候補を該行枠候補に包含される文字領域データに基づいて修正し、分割により包含されなくなった各文字領域に対し該文字領域を行枠とする行情報を生成する行枠候補修正手段を含んでもよい。
【００１０】
あるいは前記読み順決定装置は、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、前記行枠候補を前記現在の文字領域を更に含む最小の行枠に拡張する拡張処理を一定の条件の下に実行する行枠候補生成手段と、前記行枠候補生成手段による前記拡張処理の実行前に、拡張によって生成されることになる行枠候補と前記文字並び方向とを基に文字の読み順が正しく決定されることを確認する確認部と、前記確認部による確認の失敗に応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを更に含んでもよい。ここで、前記行枠候補生成手段は、前記確認部による確認の成功を条件として前記拡張処理を実行し、前記確認が失敗した場合は、前記現在の文字領域を前記文字情報のリストの先頭として処理を繰り返す。
【００１１】
上記目的を達成する本願発明はまた、次のような文字の読み順を決定するための読み順決定装置によっても実現される。そのような読み順決定装置は、文字の読み順を決定するための読み順決定装置であって、画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報のリストである文字情報のリストを格納する文字情報格納部と、前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、前記行情報のリストから行情報を読み出して、読み出した前記行情報の行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、前記部分集合内の各文字領域データを、対応する前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、行情報ごとの並び替えられた前記文字領域データの部分集合を前記行の並びに順に繋ぎ合わせることにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段とを含む。
【００１２】
以上、文字の読み順を決定するための読み順決定装置として本願発明を説明した。しかし本願発明は、そのような読み順決定装置によって実施される文字の読み順を決定するための読み順決定方法、及びそのような読み順決定装置としてのコンピュータによってインストールして実行される文字の読み順を決定するための読み順決定プログラムとして把握することもできる。
【発明の効果】
【００１３】
本願発明では、画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを予め用意しておき、行枠内における文字の並び方向に従って行枠に包含される文字領域の文字の読み順を決定する。従って本願発明によれば、文字領域の統合、分割、新規挿入のいずれの修正が行われても、修正箇所を包含する行枠の文字並び方向に基づいて修正後の文字の読み順を決定できる。本願発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００１４】
【図１】本願発明の実施の形態に係る読み順決定装置１００（第１実施例）の機能構成の一例を示す。
【図２】（ａ）は、文字領域のフォーマットを説明する説明図を示す。（ｂ）は、行情報のフォーマットを説明する説明図を示す。
【図３】文字画像データの一例を示す。
【図４】（ａ）乃至（ｄ）はそれぞれ、圧縮プロセス（第１実施例）の各段階の説明図を示す。
【図５】（ａ）乃至（ｆ）はそれぞれ、文字領域が新規追加された場合における解凍プロセス（第１実施例）の各段階の説明図を示す。
【図６】圧縮処理部１２０による処理（第１実施例）の全体の流れの一例を示す。
【図７】解凍処理部１４０による処理（第１実施例）の全体の流れの一例を示す。
【図８】本願発明の実施の形態に係る読み順決定装置８００（第２実施例）の機能構成の一例を示す。
【図９】（ａ）は、文字画像データの他の一例を示す。（ｂ）は、図９（ａ）に示す文字画像データに対応する行枠を示す。
【図１０】解凍処理部８４０による処理（第２実施例）の全体の流れの一例を示す。
【図１１】（ａ）乃至（ｃ）はそれぞれ、処理対象の文字領域が既存の行枠に包含される場合における圧縮プロセスの各段階の説明図を示す。
【図１２】本願発明の実施の形態に係る読み順決定装置１２００（第３実施例）の機能構成の一例を示す。
【図１３】（ａ）乃至（ｃ）はそれぞれ、処理対象の文字領域が既存の行枠に包含される場合における改良された圧縮プロセス（第３実施例）の各段階の説明図を示す。
【図１４】圧縮処理部１２２０による処理（第３実施例）の全体の流れの一例を示す。
【図１５】図１４に示すステップ１４１４の修正処理の流れの一例を示すフローチャートである。
【図１６】本願発明の実施の形態に係る読み順決定装置１６００（第４実施例）の機能構成の一例を示す。
【図１７】（ａ）乃至（ｅ）はそれぞれ、圧縮プロセス（第４実施例）の各段階の説明をする説明図を示す。
【図１８】圧縮処理部１６２０による処理（第４実施例）の全体の流れの一例を示す。
【図１９】本願発明の実施の形態に係る読み順決定装置を実現するのに好適な情報処理装置のハードウェア構成の一例を示す。
【発明を実施するための形態】
【００１５】
以下、本願発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００１６】
（第１実施例） 図１は、本願発明の第１実施例に係る読み順決定装置１００の機能構成の一例を示す。読み順決定装置１００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部１１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部１１５と、文字情報のリストから行情報を生成する圧縮処理部１２０と、生成された行情報を格納する行情報格納部１３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部１０５と、行情報を用いて文字情報格納部１１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部１４０とを含む。なお、画像データ格納部１１０と修正部１０５は読み順決定装置１００の外に設け、読み順決定装置１００は修正部１０５から修正結果を受け取るように構成してもよい。そして読み順決定装置１００は、受け取った修正結果に基づいて文字情報格納部１１５に格納される文字情報のリストを更新するように構成してもよい。
【００１７】
画像データ格納部１１０が格納する画像データは、文字を含む画像データである。その格納単位は、任意の文書の１頁分ごとの画像データであっても、或いは任意の文書の１頁内のまとまりある領域ごとの画像データであってもよい。以下では、画像データは文書の１頁ごとの画像データであるとして説明する。
【００１８】
文字情報格納部１１５が格納する各文字情報は、画像データに含まれる各文字のテキスト・データ及び文字領域データを含む。ここで図２（ａ）を参照して文字領域データのフォーマットを説明する。まず文字Ｔ２０８が含まれる頁２００の左上隅を原点２０２とし、頁２００の上端をＸ軸２０４（水平軸）、左端をＹ軸２０６（垂直軸）として定める。するとほとんど全ての文字はＸ軸２０４又はＹ軸２０６に沿って並んでいると考えることができるので、上記のように定義した座標内において、文字Ｔ２０８を囲む矩形の文字領域２１０は、左上隅の座標（ｘ、ｙ）と、文字領域２１０の幅ｗと、文字領域２１０の高さｈとによって表すことができる。当然ながら文字領域データのフォーマットはこれに限定されず、矩形の全頂点の座標など等価な情報を含む他のフォーマットを利用してもよい。なお、本願の図面に示される全ての文字Ｔは、任意の言語の文字を示すことに留意されたい。また、本願の図に表された全ての座標は、上記説明した座標と同様にして定義されたものとする。
【００１９】
文字情報格納部１１５は、上記のように表される文字情報が文字の読み順にリストされた文字情報のリストを格納する。上述したようにこのような文字情報のリストは、ＯＣＲによる文字認識処理の結果として取得できる。以下に、一例として文字情報のデータ構造Symbolと文字情報のリストのデータ構造Pageとを示す。
calss Symbol {
char character;
int x, y, width, height;
}
class Page{
Symbol[] symbols;
}
【００２０】
圧縮処理部１２０は、文字情報格納部１１５から文字情報のリストを読み出して行情報のリストを生成し、行情報格納部１３５に格納する。ここで行情報とは、画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる情報をいう。本発明ではこのような行情報を導入し、行の並び順にリストされた行情報のリストを予め用意しておくことで、後に文字情報のリストが修正された場合でも正しく文字の読み順を決定することを可能とする。
【００２１】
ここで図２（ｂ）を参照して行情報のフォーマットを説明する。図２（ｂ）では簡単のため、同一方向に連続して並ぶ文字をＴ１２２２とＴ２２２６の２つとしている。これら２つの文字を囲む行枠２２８は、文字Ｔ１２２２の文字領域２２０と文字Ｔ２２２６の文字領域２２４とを囲む最小の矩形として定義される。従って行枠２２８は、図２（ｂ）に示す座標内において、行枠の左上隅の座標（ｘ、ｙ）と、行枠の幅ｗと、行枠の高さｈとによって表すことができる。また行枠内における文字の並び方向ｄは、Ｘ軸２１６又はＹ軸２１８のいずれか一方の方向を示す。なお、２以上の文字が同一方向に連続して並ばない場合、１つの文字の文字領域をそのまま行枠とし、文字の並び方向に関する情報のない行情報を生成する。以下では、このように1文字領域からなる行枠を単文字行枠と呼ぶ。当然ながら行枠のフォーマットはこれに限定されず、矩形の全頂点の座標など等価な情報を含む他のフォーマットを利用してもよい。なお本願発明では、ある文字領域に他の文字領域が完全に含まれることはないものとする。
【００２２】
行情報格納部１３５は、上記のように表される行情報が行の並び順にリストされた行情報のリストを格納する。以下に、一例として行情報のデータ構造Lineと行情報のリストのデータ構造Orderとを示す。
calss Line {
int x, y, width, height;
int dx, dy
}
class Order{
Line[] lines;
}
【００２３】
圧縮処理部１２０は、より具体的には、行枠候補生成部１２５と行情報登録部１３０とを含む。行枠候補生成部１２５は、文字情報格納部１１５に格納される文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化する。行枠候補生成部１２５はまた、最初の２つの文字領域データによって行枠候補における文字の並び方向を決定する。そして行枠候補生成部１２５は、決定した文字の並び方向に現在の文字領域が存在しなくなるまで、行枠候補を現在の文字領域を更に包含する最小の行枠に拡張する。文字の並び方向に現在の文字領域が存在しなくなると、行枠候補生成部１２５は、現在の文字領域を文字情報のリストの先頭の文字領域データとして、上記一連の処理を繰り返す。
【００２４】
行情報登録部１３０は、圧縮処理の開始時に行情報のリストを用意し、これをｎｕｌｌで初期化する。行情報登録部１３０はまた、行枠候補生成部１２５による上記処理において、文字の並び方向に現在の文字領域が存在しないことが検知されるたびに、現在の行枠候補を対応する文字の並び方向と共に行情報として行情報のリストの最後尾に登録し、行情報格納１３５に格納する。
【００２５】
ここで図３乃至図４を参照して、行枠候補生成部１２５及び行情報登録部１３０による圧縮処理の概要を説明する。図３は、２行からなる文字集合の画像データ３００を示す。図４は、圧縮プロセスの各段階を示す。処理の開始時において、文字情報格納部１１５には画像データ３００から抽出された文字情報のリストが格納されており、行情報格納部１３５には空の行情報のリストが格納されているものとする。なお、上述したように図３においてＴｍ（ｍは１から１８までの任意の整数）は任意の言語の文字を示す。また、図３においてＴｍを囲む矩形はＴｍの文字領域を示し、Ｔｍの真上又は真下にある数字はＴｍに付与された文字の読み順（文字情報のリストのリスト順）を示す。
【００２６】
まず、行枠候補生成部１２５は、文字情報のリストから最初に読み出したＴ１の文字情報の文字領域データで行枠候補４００を初期化する（図４（ａ）を参照）。続いて行枠候補生成部１２５は、現在の行枠候補４００を、次に読み出した２番目のＴ２の文字情報の文字領域データを更に含む最小の矩形に拡張し、現在の行枠候補４０２とする（図４（ｂ）を参照）。このとき行枠候補生成部１２５は、１番目と２番目に読み出したＴ１とＴ２の文字情報の文字領域データに基づき、行枠候補４０２内における文字の並び方向４０３を決定する（図４（ｂ）を参照）。
【００２７】
続いて行枠候補生成部１２５は、決定した文字の並び方向４０３に現在の文字領域が存在しなくなるまで、行枠候補４０３を現在の文字領域を更に包含する最小の行枠に順次拡張し、行枠候補４０４を得る（図４（ｃ）を参照）。続いて行枠候補生成部１２５は、次の文字情報、即ちＴ１０の文字領域データを現在の文字領域として読み出し、Ｔ１０の文字領域データが文字の並び方向４０３の方向とは異なる方向４０６にあることを検出する（図４（ｃ）の矢印４０６を参照）。
【００２８】
上記検出は行枠候補生成部１２５から行情報登録部１３０へ伝えられ、行情報登録部１３０は、現在の行枠候補４０４と対応する文字の並び方向４０３を行情報として、行情報格納部１３５の行情報のリストに登録する。行枠候補生成部１２５また、Ｔ１０の文字領域データを文字情報のリストの先頭の文字領域データとみなして、文字情報のリストに文字情報がなくなるまで図４（ａ）乃至図４（ｄ）までの処理と同様の処理を繰り返す（図４（ｄ）を参照）。処理の終わりと同時に行情報のリストが完成する。
【００２９】
修正部１０５は、画像データ格納部１１０と文字情報格納部１１５から、それぞれ文字情報と対応する画像データとを読み出して図示しないディスプレイ等の出力部に出力し、ユーザがオリジナルの画像とＯＣＲによる文字認識結果との比較により文字認識の誤りの有無を確認することを可能とする。修正部１０５はまた、ユーザが文字認識の誤りを見つけた場合に、ユーザから図示しないキーボード等の入力部を介して文字情報の修正の指示を受け取る。
【００３０】
ここで文字認識の誤りの修正は、文字領域の統合、分割、及び挿入のうちのいずれかであってよい。修正が文字領域の統合及び分割の場合、修正の指示は、既存の文字情報の削除と、削除する文字情報に代わる文字情報の追加である。一方、修正が文字領域の挿入の場合、修正の指示は文字情報の追加である。
【００３１】
従って文字情報の修正の指示が文字領域の統合、分割、挿入のいずれであっても、修正部１０５は、入力部を介してユーザから追加するべき文字のテキスト・データ及び対応する文字領域データを受け取る。修正部１０５は、受け取った文字情報を文字情報のリストの先頭又は最後尾に追加する。このため文字情報のリストに対し修正がなされた後は、後述する解凍処理部１４０によって文字の読み順を再度決定する必要がある。修正部１０５は、ユーザから受け取った追加すべき文字情報を文字情報のリストに追加することなく解凍処理部１４０に直接渡してもよい。
【００３２】
なお、文字情報の修正の指示が文字領域の統合及び分割の場合は、追加すべき文字情報を統合又は分割のために文字情報のリストから削除すべき文字情報の位置に挿入すれば、文字の読み順の修正は不要である。一方、追加位置を常に文字情報のリストの先頭又は最後尾とすれば、或いは常に解凍処理部１４０へ直接渡すようにすれば、修正内容に応じて処理を変える必要がない。どちらの構成を採用するにしても、文字領域の挿入による修正に対しては、文字の読み順の修正が必要である。
【００３３】
解凍処理部１４０は、文字情報のリストに対する修正要求に応答して、行情報のリストを用いて文字情報格納部１１５に格納される文字情報のリストの文字の読み順を決定する。上述したように、解凍処理部１４０は、修正部１０５から文字情報のリストの先頭又は最後尾への文字情報の追加の通知を受けてもよく、或いは修正部１０５から追加すべき文字情報そのものを受け取ってもよい。
【００３４】
解凍処理部１４０は、より具体的には、検出部１４５と、部分集合決定部１５０と、並び替え部１５５と、順序決定部１６０とを含む。検出部１４５は、文字情報のリストへの文字情報の追加要求に応答して、行情報格納部１３５に格納される行情報のリストから、追加する文字情報の文字領域データが示す領域を包含する行枠を検出する。
【００３５】
部分集合決定部１５０は、文字情報格納部１１５に格納される文字情報のリストから、検出部１４５により検出された行枠に包含される領域を示す全ての文字領域データからなる文字領域データの部分集合を求める。なお、追加する文字情報が解凍処理部１４０に直接渡される場合には、部分集合決定部１５０は追加する文字情報の文字領域データを、求めた文字領域データの部分集合に含める。
【００３６】
並び替え部１５５は、部分集合決定部１５０により求められた部分集合内の各文字領域データを、検出された行枠に対応する文字の並び方向に対する位置に従って並び替える。より具体的には、並び替え部１５５は、部分集合内の各文字領域データを、検出された行枠に対応する文字の並び方向に対する各文字領域データの示す領域の中心点座標の位置に従って並び替える。
【００３７】
順序決定部１６０は、並び替え部１５５により決定された部分集合についての文字領域データの並び順に従って、文字情報格納部１１５に格納される文字情報のリストを更新する。より具体的には、順序決定部１６０は、並び替え部１５５により決定された部分集合についての文字領域データの並び順により追加する文字情報の挿入位置を決定し、決定した挿入位置に追加する文字情報を挿入して文字情報のリストを更新する。結果、文字情報のリストにおける新たらしい文字の読み順が決定される。
【００３８】
ここで図５を参照して、解凍処理部１４０の上記各構成要素による解凍処理の概要を説明する。図５は、解凍プロセスの各段階を示す。処理の開始において、文字情報格納部１１５には画像データ５００から抽出されたＴ１、Ｔ２、Ｔ３、Ｔ４の文字情報を含む文字情報のリストが格納されているものとする（図５（ａ）参照）。また行情報格納部１３５には、Ｔ１、Ｔ２、Ｔ３、Ｔ４の文字領域を囲む最小の矩形である行枠５０２と、行枠５０２内における文字の並び方向５０３とからなる行情報を含む行情報のリストが格納されているものとする（図５（ａ）参照）。なお、図５（ａ）に示す画像データ５００において各文字の真上に記載されている数字は、各文字に付与された文字の読み順（文字情報のリストのリスト順）を示す。
【００３９】
このような状況で、文字認識の誤りを正すためにユーザが文字Ｔ３とＴ４の間に新たに文字ＴＸ５０４を挿入する修正を指示したとする（図５（ｂ）参照）。上述したように、修正の指示としてユーザから入力される情報は、文字ＴＸ５０４のテキスト・データとその文字領域データのみである。そのため、文字情報のリストのどの位置に文字ＴＸ５０４を挿入すべきか不明であり、文字の読み順を改めて決定する必要がある。そこで検出部１４５はまず行情報のリストを検索して、追加された文字ＴＸ５０４の文字領域を包含する行枠５０２と対応する文字並び方向５０３とを取得する（図５（ｃ）参照）。
【００４０】
続いて部分集合決定部１５０は、検出部１４５により検出された行枠５０２に包含される領域を示す文字領域データを文字情報のリストから全て読み出す（図５（ｄ）参照）。続いて並び替え部１５５は、部分集合決定部１５０により読み出された全文字領域データを、検出部１４５により検出された文字並び方向５０３に対する各文字領域データの中心座標の位置に従って並び替える（図５（ｅ））。すると文字領域データの部分集合に対し文字の読み順が正しく決定され（図５（ｆ））、結果として、文字ＴＸ５０４の文字情報を文字情報のリストに挿入する位置（文字Ｔ３とＴ４の間であり、リストの４番目の位置）が分かる。このように、追加文字の文字領域を含む行枠に関して文字の並び順を決定することによって、文字情報のリスト全体についての正しい文字の読み順を決定できる。
【００４１】
次に図６及び図７を参照して、本願発明の第１実施例に係る読み順決定装置１００による処理の流れを説明する。図６は、圧縮処理部１２０による圧縮処理の流れの一例を示すフローチャートである。図７は、解凍処理部１４０による解凍処理の流れの一例を示すフローチャートである。まず、図６を参照して、圧縮処理部１２０による圧縮処理の流れを説明する。
【００４２】
図６において、圧縮処理はステップ６００から開始し、行情報登録部１３０は、行情報を行の並び順に登録すべき行情報のリストＬＩＳＴ１を用意し、これにｎｕｌｌを設定して初期化する。また、行枠候補生成部１２５は、文字情報格納部１１５に格納される文字情報のリストから先頭の1文字目の文字領域Ｃを読み出してこれを行枠候補Ｌ１に設定すると共に、行枠候補Ｌ１に対応する文字の並び方向Ｌ２にｎｕｌｌを設定して、行情報の候補Ｌを初期化する（ステップ６０３）。
【００４３】
続いて行枠候補生成部１２５は、文字情報格納部１１５に次の文字領域が存在するか否かを判定する（ステップ６０６）。文字情報のリストにリストされる全ての文字情報が読み出されている場合（ステップ６０６：ＮＯ）、制御は行枠候補生成部１２５から行情報登録部１３０へ移り、行情報登録部１３０は、現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１に登録し、ＬＩＳＴ１を出力する（ステップ６０９）。そして処理は終了する。
【００４４】
一方、ステップ６０６において次の文字領域が存在する場合（ステップ６０６：ＹＥＳ）、行枠候補生成部１２５は、次の文字領域をＮとする（ステップ６１２）。続いて行枠候補生成部１２５は、行枠候補Ｌ１と次の文字領域ＮとをそれぞれＸ軸及びＹ軸に射影し、Ｘ軸及びＹ軸のどちらに射影した場合も射影区間が重ならないか否かを判定する（ステップ６１５）。これは、隣の行の文字などＸ軸又はＹ軸に沿って並んでいない文字を同一の行枠に含むことを避けるためである。
【００４５】
射影区間が重なる場合（ステップ６１５：ＮＯ）、行枠候補生成部１２５は、行枠候補Ｌ１の中心点（ｘ１、ｙ１）と次の文字領域Ｎの中心点（ｘ２、ｙ２）との座標の差（ｘ１−ｘ２、ｙ１−ｙ２）を求め、差の絶対値が大きな軸（ｍａｘ（｜ｘ１−ｘ２｜、｜ｙ１−ｙ２｜））の方向を指す単位ベクトルＤ（（０，１）又は（１，０））を求める（ステップ６１８）。ここで次の文字領域Ｎが現在の1文字目の文字領域Ｃに続く2文字目の文字領域である場合、文字の並び方向Ｌ２にＤを設定する。続いて行枠候補生成部１２５は、文字の並び方向Ｌ２と単位ベクトルＤが等しいか否かを判定する（ステップ６２１）。
【００４６】
文字の並び方向Ｌ２と単位ベクトルＤが等しい場合（ステップ６２１：ＹＥＳ）、行枠候補生成部１２５は、行枠候補Ｌ１を行枠候補Ｌ１と次の文字領域Ｎを含む最小の矩形で置換する（ステップ６２４）。そして処理はステップ６０６に戻り、行枠候補生成部１２５は一連の処理を繰り返す。一方、文字の並び方向Ｌ２と単位ベクトルＤが等しくない場合（ステップ６２１：ＮＯ）、制御は行枠候補生成部１２５から行情報登録部１３０へ移り、行情報登録部１３０は現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１の最後尾に追加し、また、現在の次の文字領域Ｎを文字情報のリストの一文字目とみなすため、現在の１文字目の文字領域Ｃに設定する（ステップ６２７）。そして処理はステップ６０３へ戻り、行枠候補生成部１２５は一連の処理を繰り返す。
【００４７】
次に、図７を参照して、解凍処理部１４０による解凍処理の流れを説明する。図７において、解凍処理はステップ７００から開始し、検出部１４５は、文字情報のリストへの文字情報の追加に応答して、行情報格納１３５に格納される行情報のリストから、追加された文字情報の文字領域データが示す領域を包含する行枠と対応する文字の並び方向からなる行情報を検出する。続いて、部分集合決定部１５０は、検出部１４５から行情報を受け取り、該行情報の行枠に包含される領域を示す文字領域データの部分集合Ｍを、文字情報格納部１１５に格納される文字情報のリストから求める（ステップ７０２）。
【００４８】
続いて並び替え部１５５は、部分集合決定部１５０から文字領域データの部分集合Ｍと行情報とを受け取り、部分集合Ｍを構成する各文字領域データを、受け取った行情報の文字の並び方向に対する各文字領域データの領域の位置に従って並び替える（ステップ７０４）。最後に順序決定部１６０は、文字領域データの部分集合Ｍについて決定された文字の並び順に基づいて、文字情報格納部１１５に格納される文字情報のリストを更新し、新たに文字の読み順を決定する（ステップ７０６）。そして処理は終了する。
【００４９】
（第２実施例）上述した第１実施例では、解凍処理部１４０は、文字情報のリストに対する修正要求に応答して解凍処理を行い文字の読み順を決定する。しかしながら解凍処理部１４０による解凍処理は、文字情報のリストを文字情報格納部１１５から読み出すタイミングで行うようにしてもよい。そこで該構成を採用する場合を第２実施例として以下に説明する。
【００５０】
図８は、本願発明の第２実施例に係る読み順決定装置８００の機能構成の一例を示す。読み順決定装置８００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部８１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部８１５と、文字情報のリストから行情報を生成する圧縮処理部８２０と、生成された行情報を格納する行情報格納部８３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部８０５と、行情報を用いて文字情報格納部８１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部８４０を含む。
【００５１】
第２実施例に係る読み順決定装置８００の上記各構成要素は、解凍処理部８４０を除いて第１実施例に係る読み順決定装置１００の対応する構成要素と変わらないので、以下では解凍処理部８４０についてのみ説明をする。但し、第２実施例では、文字情報格納部８１５から文字情報のリストが読み出されるたびに解凍処理部８４０による解凍処理が行われ文字の読み順が決定されるので、文字情報格納部８１５に格納される文字情報のリストは必ずしも文字の読み順に並んでいなくてよい。第２実施例に係る解凍処理部８４０は、部分集合決定部８４５と、並び替え部８５０と、順序決定部８５５とを含む。
【００５２】
部分集合決定部８４５は、文字情報格納部１１５からの文字情報のリストの読み出しに応答して、行情報格納８３５に格納される行情報のリストの先頭から順に行情報を読み出し、読み出した行情報の行枠に包含される領域を示す全ての文字領域データの部分集合を、文字情報格納部８１０に格納される文字情報のリストから求める。このとき部分集合決定部８４５は、求めた文字領域データの部分集合の中に、現在処理する行枠よりも先に読み出した行枠に対して求めた文字領域データの部分集合に含まれる文字領域データがあるか否かを確認する。そのような文字領域データがあった場合、部分集合決定部８４５は、現在の文字領域データの部分集合からその共通して含まれる文字領域データを削除する。かかる処理は、１つの文字領域が２つの行枠に含まれる場合における文字の読み順決定処理の不具合を解消するためである。
【００５３】
ここで、図９を参照して、１つの文字領域が２つの行枠に含まれるケースを具体的に説明する。図９（ａ）は、文字Ｔ１からＴ６までの文字の集合９００の画像データを示し、図９（ｂ）は、文字の集合９００に対応する行枠を示す。文字の添え字は文字の読み順を表している。図９（ａ）に示すように、２番目の文字Ｔ２の文字領域がＹ軸方向にずれてＹ軸に射影した場合に文字Ｔ１、Ｔ３のいずれの文字領域とも重ならないため、文字Ｔ１からＴ３に対応する行枠は、図９（ｂ）に示すようにそれぞれ単文字行枠Ｌ１、Ｔ２、Ｌ３となっている。一方、文字Ｔ４からＴ６はＸ軸方向に連続して並んでいるため、対応する行枠は、文字Ｔ４からＴ６の文字領域を含む１つの行枠Ｌ４となっている。そして、その文字領域のずれにより、文字Ｔ２の文字領域は、本来含まれるべき行枠Ｌ2のみならず行枠Ｌ4にも含まれてしまっている。
【００５４】
このような状況において行情報を用いて文字の読み順を決定すると、文字Ｔ２が2度登場する文字情報のリストが作成される。これを解決するには、行枠Ｌ4を用いて文字を並び替える際に、行枠Ｌ4に含まれる文字領域の集合から、先に処理した行枠Ｌ２にも共通して含まれる文字Ｔ２の文字領域を削除すればよい。そこで第２実施例に係る部分集合決定部８４５では、現在の処理対象である文字領域データの部分集合と先に求めた文字領域データの部分集合とに共通して含まれる文字領域データがあるか否かを判定し、共通して含まれる文字領域データがある場合はこれを現在の処理対象である文字領域データの部分集合から削除するようにした。部分集合決定部８４５により最終的に求められた行情報ごとの文字領域データの部分集合は、対応する行情報と共に後述する並び替え部８５０に渡される。
【００５５】
並び替え部８５０は、行情報のリストにおける行の並び順で、部分集合決定部８４５から行情報と対応する文字領域データの部分集合とのペアを受け取る。そして並び替え８５０は、行情報ごと、対応する部分集合の各文字領域データを対応する文字の並び方向に対する位置に従って並び替える。より具体的には、並び替え部８５０は、部分集合内の各文字領域データを、対応する文字の並び方向に対する各文字領域データの示す領域の中心点座標の位置に従って並び替える。
【００５６】
順序決定部８５５は、行情報のリストにおける行の並び順で、並び替え部８５０から行情報と対応する部分集合の並び替えられた文字領域データとを受け取る。そして順序決定部８５５は、行情報ごとの並び替えられた文字領域データの部分集合を行の並びに順に繋ぎ合わせて文字領域データのリストを作成し、該リストのリスト順を文字情報のリストについての文字の読み順として決定する。
【００５７】
次に図１０を参照して、解凍処理部８４０による解凍処理の流れを説明する。図１０において、解凍処理はステップ１０００から開始し、順序決定部８５５は、文字領域データを文字の読み順に登録するリストＬＩＳＴ２を用意し、これにｎｕｌｌを設定して初期化する。続いて制御は順序決定部８５５から部分集合決定部８４５へ移り、部分集合決定部８４５は、行情報格納８３５に格納されている行情報のリストからリスト順に行情報を読み出し、読み出すべき次の行情報が行情報のリストに存在するか否かを判定する（ステップ１００２）。読み出すべき次の行情報が行情報のリストに存在しない場合（ステップ１００２：ＮＯ）、制御は順序決定部８５５に戻り、順序決定部８５５は現在のリストＬＩＳＴ２を出力する。その後処理は終了する。
【００５８】
一方、読み出すべき次の行情報が行情報のリストに存在する場合（ステップ１００２：ＹＥＳ）、部分集合決定部８４５は、読み出した次の行情報の行枠に包含される領域を示す全ての文字領域データの部分集合Ｍを、文字情報格納部８１０に格納される文字情報のリストから求める（ステップ１００６）。続いて部分集合決定部８４５は、求めた文字領域データの部分集合Ｍの中に、現在のリストＬＩＳＴ２に登録されている文字領域データが含まれているか否かを確認し、含まれている場合にはその共通して含まれる文字領域データを部分集合Ｍから削除する（ステップ１００８）。上述したようにかかる処理は、１つの文字領域が２つの行枠に含まれる場合における文字の読み順決定処理の不具合を解消するためである。
【００５９】
ステップ１００８の処理の後、文字領域データの部分集合Ｍは対応する行情報と共に並び替え部８５０へ渡され、並び替え部８５０は、部分集合Ｍを構成する各文字領域データを、文字の並び方向に対する各文字領域データの領域の位置に従って並び替える（ステップ１０１０）。続いて順序決定部８５５は、並び替え部８５０によって並び替えられた文字領域データの部分集合ＭをリストＬＩＳＴ２の最後尾に追加する（ステップ１０１２）。その後処理はステップ１００２へ戻り、一連の処理が繰り返される。
【００６０】
（第３実施例）第２実施例に係る解凍処理に関連して説明した、１つの文字領域が２つの行枠に含まれるという問題は、任意の言語において起こり得るものである。これとは別に、ある文字領域が先に決定した行枠又は現在の行枠候補に含まれるという問題があり、これは日本語に特有の問題である。そこでこのような問題に対応した構成を第３実施例として以下に説明する。
【００６１】
まず図１１を参照して、その生成後に処理対象となった文字領域を含むこととなった行枠を使用して文字の読み順を決定した場合の不具合を説明する。図１１（ａ）は、２桁の数字を含む縦書きの文字列「平成２３年」の画像データ１１００を示す。この画像データ１１００から抽出された文字情報のリスト（リスト順は、「平」、「成」、「２」、「３」、「年」の順）に対し、第１実施例として説明した圧縮方法により行枠を作成することを考える。なお、数字「２３」は、ＯＣＲによる文字認識処理において「２」と「３」の２文字として認識されることに留意されたい。また「３」の文字領域は「２」の文字領域よりも「成」の文字領域に近いことに留意されたい。すると文字情報のリストから「２」が読み出された時点で図１１（ｂ）に示す行枠候補１１０２が現在の行枠候補として決定される。続いて数字「３」が読み出され行枠候補の拡張が検討される。しかし図１１（ｃ）に示すように数字「３」は現在の行枠候補１１０２に既に包含されている。
【００６２】
ここで仮に現在の行枠候補１１０２をこのまま行枠として採用するとする。すると解凍時において、行枠候補１１０２及び対応する文字の並び方向１１０４に基づいて文字の並び順を決定しようとすると、上述したように「３」の文字領域は「２」の文字領域よりも「成」の文字領域に近いため、「平」、「成」、「３」、「２」という順序で文字列が作成されてしまう。そこで第３実施例では、第１実施例に係る圧縮処理部１２０を改良して、ある文字領域が先に決定した行枠又は現在の行枠候補に含まれる場合に、当該ある文字を含まないよう先に決定した行枠又は現在の行枠候補を修正するようにした。以下、図１２を参照して第３実施例に係る読み順決定装置１２００を説明する。
【００６３】
図１２は、本願発明の第３実施例に係る読み順決定装置１２００の機能構成の一例を示す。読み順決定装置１２００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部１２１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部１２１５と、文字情報のリストから行情報を生成する圧縮処理部１２２０と、生成された行情報を格納する行情報格納部１２３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部１２０５と、行情報を用いて文字情報格納部１２１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部１２４０を含む。
【００６４】
第３実施例に係る読み順決定装置１２００の上記各構成要素は、圧縮処理部１２２０を除いて第１実施例に係る読み順決定装置１００の対応する構成要素と変わらないので、以下では圧縮処理部１２２０についてのみ説明をする。なお、第３実施例において、解凍処理部１２４０の代わりに第２実施例に係る解凍処理部８４０を採用してもよいことは言うまでもない。第３実施例に係る圧縮処理部１２２０は、行枠候補生成１２２５と、行枠候補修正部１２２７と、行情報登録部１２３０とを含む。
【００６５】
行枠候補生成１２２５は、文字情報格納部１２１５に格納される文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化する。行枠候補生成部１２２５はまた、最初の２つの文字領域データによって行枠候補における文字の並び方向を決定する。そして行枠候補生成部１２２５は、決定した文字の並び方向に現在の文字領域が存在しなくなるまで、行枠候補を現在の文字領域を更に包含する最小の行枠に拡張する。
【００６６】
但し第３実施例では、行枠候補生成１２２５は、現在の文字領域が現在の行枠候補又は過去に行枠として決定された行枠候補のいずれかに包含される場合には、拡張処理を行うことなく後述する行枠候補修正部１２２７を呼び出してその修正処理の結果の一部を取得する。行枠候補修正部１２２７から修正結果の一部を受け取った場合、行枠候補生成部１２２５は、受け取った一部の修正結果で行枠候補を初期化して上記一連の処理を繰り返す。行枠候補生成部１２２５はまた、文字の並び方向に現在の文字領域が存在しなくなった場合、現在の文字領域を文字情報のリストの先頭の文字領域データとみなして、上記一連の処理を繰り返す。
【００６７】
行枠候補修正部１２２７は、行枠候補生成部１２２５からの呼び出しに応答して、現在の文字領域を包含する行枠候補（現在の行枠候補又は過去に行枠として決定された行枠候補）に対して以下の修正処理１〜３を行う。即ち、行枠候補修正部１２２７は、修正対象の行枠候補を、対応する文字の並び方向に対して垂直かつ現在の文字領域の中心点を基準に分割する（修正処理１）。続いて行枠候補修正部１２２７は、分割により生成された２つの行枠候補のうち少なくとも１つの文字領域を包含する行枠候補を、包含する全ての文字領域を囲む最小の矩形に修正する（修正処理２）。続いて行枠候補修正部１２２７は、分割により分割後の２つの行枠候補のいずれにも包含されなくなった文字領域、および、現在の文字領域の各々に対して単文字行枠を生成する（修正処理３）。
【００６８】
上記修正処理２または修正処理３において得られた１以上の行枠候補は、現在の文字領域を包含する修正対象の行枠候補が現在の行枠候補である場合、行枠候補修正部１２２７により、行情報格納部１２３５に格納される行情報のリストの最後尾に登録される。一方、現在の文字領域を包含する修正対象の行枠候補が過去に行枠として決定された行枠候補である場合、修正処理２または修正処理３において得られた１以上の行枠候補は、行枠候補修正部１２２７により、行情報格納部１２３５に格納される行情報のリスト上の上記過去に行枠として決定された行枠候補と置換される。
【００６９】
また、上記行情報格納部１２３５への登録または置換において、修正処理２または修正処理３において得られた１以上の行枠候補の順序は、以下のとおりとする。現在の文字領域からなる単文字行枠を最後尾とする。その他の行枠候補については、分割前の行枠によって得られる文字の順序に矛盾しない順序とする。
【００７０】
ここで図１３を参照して、行枠候補修正部１２２７による上記修正処理１〜３を具体的に説明する。なお、行枠候補修正部１２２７は、図１１を参照して説明した文字列「平成２３年」の画像データ１１００から抽出された文字情報のリストを基に行情報を作成する行枠候補生成部１２２５により呼び出されて処理を開始するものとする。また、呼び出し時点において行枠候補生成部１２２５は、図１１（ｂ）に示す行枠１１０２を現在の行枠候補として生成しており、図１１（ｃ）に示すように現在の文字領域１１０６が、現在の行枠候補である行枠１１０２に包含されることを検出しているとする。
【００７１】
図１３（ａ）は、行枠候補修正部１２２７による修正処理１を示す。図１１（ｃ）に示す修正対象の行枠１１０２は、対応する文字の並び方向１１０４に対して垂直かつ現在の文字領域１１０６の中心点を基準に分割され、図１３（ａ）に示すように２つの行枠１３００と１３０２とが生成される。図１３（ｂ）は、行枠候補修正部１２２７による修正処理２を示す。図１３（ｂ）では、分割により生成された２つの行枠１３００と１３０２のうち、「平」と「成」の２つの文字領域を包含する行枠１３００が、包含する「平」と「成」の２つの文字領域を囲む最小の矩形である行枠１３０４に修正される。図１３（ｃ）は、行枠候補修正部１２２７による修正処理３を示す。図１３（ｃ）では、分割により分割後のいずれの行枠１３００と１３０２にも包含されなくなった「２」と「３」の２つの文字領域（図１３（ａ）参照）の各々に対し、単文字行枠１３０６、１３０８が生成されている。
【００７２】
図１２に戻って、行情報登録部１２３０は、圧縮処理の開始時に行情報のリストを行情報格納部１２３５に用意し、これをｎｕｌｌで初期化する。行情報登録部１２３０はまた、行枠候補生成部１２２５による拡張処理において、文字の並び方向に現在の文字領域が存在しないことが検知されるたびに、現在の行枠候補を対応する文字の並び方向と共に行情報として行情報格納部１２３５に格納される行情報のリストの最後尾に登録する。
【００７３】
次に図１４及び図１５を参照して、第３実施例に係る圧縮処理部１２２０による圧縮処理の流れを説明する。図１４は、第３実施例に係る圧縮処理部１２２０による圧縮処理の流れの一例を示すフローチャートである。図１５は、図１４に示すステップ１４１４の修正処理の流れの一例を示すフローチャートである。なお図１５に示すフローチャートは、四角１４５０で囲んだ部分の処理が新たに追加されたことを除いては、図６に示す第１実施例に係る圧縮処理部１２０による圧縮処理のフローチャートと同じである。そこで以下では、四角１４５０で囲んだ新たに追加されたステップについてのみ説明する。
【００７４】
ステップ１４１３の処理は、図６に示すフローチャートのステップ６１２に対応するステップ１４１２の直後に行われ、行枠候補生成部１２２５は、文字情報のリストから読み出した次の文字領域Ｎが、現在の行枠候補Ｌ１又は現在の行情報のリストＬＩＳＴ１に行枠として登録されている過去の行枠候補のいずれかに包含されるか否かを判定する。次の文字領域Ｎがいずれの行枠候補にも包含されない場合（ステップ１４１３：ＮＯ）、処理は図６に示すフローチャートのステップ６１５に対応するステップ１４１５へ進む。一方、次の文字領域Ｎがいずれかの行枠候補に包含される場合（ステップ１４１３：ＹＥＳ）、処理はステップ１４１４へ進み、行枠候補修正部１２２７は、次の文字領域Ｎを包含する現在の行枠候補Ｌ１又は過去の行枠候補を修正する修正処理を行う。修正処理の詳細は図１５を参照して説明する。修正処理の後処理はステップ１４０６へ戻る。
【００７５】
図１５に示す行枠候補修正部１２２７による修正処理は、ステップ１５００から開始し、行枠候補修正部１２２７は、文字領域Ｎの中心点を基準に、文字領域Ｎを包含する既存の行枠候補を該行枠候補に対応する文字の並び方向に対して垂直に分割する。続いて、行枠候補修正部１２２７は、分割後の２つの行枠候補のうち、１以上の文字領域を包含する行枠候補を該１以上の文字領域を囲む最小の行枠に修正する（ステップ１５０２）。行枠候補修正部１２２７はまた、分割によって分割後の２つの行枠候補のいずれにも包含されなくなった各文字領域に対し、該文字領域を行枠とする単文字行枠を生成する（ステップ１５０４）。
【００７６】
続いて行枠候補修正部１２２７は、ステップ１５０２において修正した分割後の行枠候補と、あれば、ステップ１５０４において生成した単文字行枠（文字領域Ｎから生成した単文字行枠を除く）とで、行情報のリストＬＩＳＴ１を更新する（ステップ１５０６）。続いて行枠候補修正部１２２７は、ステップ１５０４において文字領域Ｎから生成した単文字行枠で行枠候補Ｌ１を更新する（ステップ１５０８）。そして処理は終了する。
【００７７】
（第４実施例）第３実施例に関して説明した、ある文字領域が先に決定した行枠又は現在の行枠候補に包含されるという問題は、第３実施例の構成とは異なるもう１つの構成を採用することによっても解決される。そこで以下ではそのようなもう１つの構成を第４実施例として説明する。
【００７８】
第４実施例では、第１実施例に係る圧縮処理部１２０を改良して、行枠候補を現在の文字領域を更に含む最小の行枠に拡張する拡張処理を、拡張によって生成されることになる行枠候補と文字並び方向とを基に文字の読み順が正しく決定されることを条件として行うようにした。以下、図１６を参照して、第４実施例に係る読み順決定装置１６００を説明する。
【００７９】
図１６は、本願発明の第４実施例に係る読み順決定装置１６００の機能構成の一例を示す。読み順決定装置１６００は、スキャナにより電子データに変換された画像データを格納する画像データ格納部１６１０と、画像データからＯＣＲによって抽出された文字情報のリストを格納する文字情報格納部１６１５と、文字情報のリストから行情報を生成する圧縮処理部１６２０と、生成された行情報を格納する行情報格納部１６３５と、画像データと文字情報とを対比可能に表示し、ＯＣＲによる文字認識処理の結果をユーザに修正させる修正部１６０５と、行情報を用いて文字情報格納部１６１５に格納される文字情報の集合の文字の読み順を決定する解凍処理部１６４０を含む。
【００８０】
第４実施例に係る読み順決定装置１６００の上記各構成要素は、圧縮処理部１６２０を除いて第１実施例に係る読み順決定装置１００の対応する構成要素と変わらないので、以下では圧縮処理部１６２０についてのみ説明をする。なお、第４実施例において、解凍処理部１６４０の代わりに第２実施例に係る解凍処理部８４０を採用してもよいことは言うまでもない。第４実施例に係る圧縮処理部１６２０は、行枠候補生成１６２５と、確認部１６２７と、行情報登録部１６３０とを含む。
【００８１】
行枠候補生成１６２５は、文字情報格納部１６１５に格納される文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化する。行枠候補生成部１６２５はまた、最初の２つの文字領域データによって行枠候補における文字の並び方向を決定する。そして行枠候補生成部１６２５は、行枠候補を現在の文字領域を更に包含する最小の行枠に拡張する拡張処理を一定の条件の下に実行する。ここで一定の条件とは、後述する確認部１６２７による確認が成功することをいい、行枠候補生成１６２５は、拡張処理前に確認部１６２７を呼び出して確認結果を受け取る。確認部１６２７による確認が成功した場合は、行枠候補生成１６２５は拡張処理を実行し、拡張後の行枠候補と次に読み出した現在の文字領域に対して確認結果が失敗となるまで繰り返し拡張処理を試みる。確認部１６２７による確認が失敗した場合は、行枠候補生成１６２５は、現在の文字領域を文字情報のリストの先頭とみなして上記一連の処理を繰り返す。
【００８２】
確認部１６２７は、行枠候補生成部１６２５からの呼び出しに応答して、拡張によって生成されることになる行枠候補と対応する文字の並び方向とを基に文字の読み順が正しく決定されることを確認する。該確認は次のように行ってよい。確認部１６２７はまず、実際に拡張処理を実行して行枠候補を生成し、これを現在の文字の並び方向とともに仮の行情報の候補とする。続いて確認部１６２７は、仮の行情報の候補を用いて文字領域の並び替えを行い文字の読み順を決定する。最後に確認部１６２７は、決定した文字の読み順と文字情報のリストにおけるリスト順とを比較し、一致するか否かを判定する。一致する場合、確認部１６２７は確認の成功を行枠候補生成１６２５へ返し、一致しない場合、確認部１６２７は確認の失敗を行枠候補生成１６２５へ返す。
【００８３】
行情報登録部１６３０は、圧縮処理の開始時に行情報のリストを行情報格納部１２３５に用意し、これをｎｕｌｌで初期化する。行情報登録部１６３０はまた、確認部１６２７による確認の失敗に応答して、現在の行枠候補を対応する文字の並び方向と共に行情報として行情報のリストの最後尾に登録する。
【００８４】
ここで図１７を参照して、確認部１６２７による確認処理の結果に基づく圧縮プロセスの各段階を説明する。処理の開始において、文字情報格納部１６１５には、図１７（ａ）に示す文字列「平成２３年」の画像データ１７００から抽出された文字情報のリストが格納されているものとする。なお、図１７（ａ）乃至（ｅ）に示す画像データ１７００は、図１１（ａ）に示す画像データ１１００と同じものである。まず、確認部１６２７により、仮の行情報の候補として行枠候補１７０２と文字の並び方向１７０４が検討されるところから開始するとする（図１７（ａ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「平」、「成」の順）と文字情報のリストにおけるリスト順（「平」、「成」の順）が一致するため、行枠候補生成１６２５による拡張処理が実行され、仮の行情報が現在の行情報の候補として確定する。
【００８５】
続いて確認部１６２７により、現在の行情報の候補が「２」の文字領域を含むように拡張され、仮の行情報の候補として行枠候補１７０６と文字の並び方向１７０４が検討される（図１７（ｂ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「平」、「成」、「３」、２」の順）と文字情報のリストにおけるリスト順（「平」、「成」、「２」、（「３」）の順）は一致しないため、行枠候補生成１６２５による拡張処理は実行されず、現在の行情報の候補が行情報として行情報のリストの最後尾に登録される（図１７（ｃ）の行枠１７０８と文字の並び方向１７１０を参照）。また、現在の行情報の候補が「２」の文字領域で初期化される。
【００８６】
続いて確認部１６２７により、上記「２」の文字領域で初期化された現在の行情報の候補が「３」の文字領域を含むように拡張され、仮の行情報の候補として行枠候補１７１２と文字の並び方向１７１４が検討される（図１７（ｃ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「２」、「３」の順）と文字情報のリストにおけるリスト順（「２」、「３」の順）が一致するため、行枠候補生成１６２５による拡張処理が実行され、仮の行情報が現在の行情報の候補として確定する。
【００８７】
続いて確認部１６２７により、現在の行情報の候補が「年」の文字領域を含むように拡張され、仮の行情報の候補として行枠候補１７１６と文字の並び方向１７１４が検討される（図１７（ｄ）参照）。すると、仮の行情報の候補を使用して得られる文字の読み順（「２」、「年」、「３」の順）と文字情報のリストにおけるリスト順（「２」、「３」、年」の順）は一致しないため、行枠候補生成１６２５による拡張処理は実行されず、現在の行情報の候補が行情報として行情報のリストの最後尾に登録される（図１７（ｅ）の行枠１７２０と文字の並び方向１７１８を参照）。また、現在の行情報の候補が「年」の文字領域で初期化される。このように第４実施例では、正しい文字の読み順が決定されることを条件に拡張処理が行われる。
【００８８】
次に図１８を参照して、第４実施例に係る圧縮処理部１６２０による圧縮処理の流れを説明する。図１８は、第４実施例に係る圧縮処理部１６２０による圧縮処理の流れの一例を示すフローチャートである。
【００８９】
図１８に示す圧縮処理はステップ１８００から開始し、行情報登録部１６３０は、行情報を行の並び順に登録すべき行情報のリストＬＩＳＴ１を用意し、これにｎｕｌｌを設定して初期化する。また、行枠候補生成部１６２５は、文字情報格納部１６１５に格納される文字情報のリストから先頭の1文字目の文字領域Ｃを読み出してこれを行枠候補Ｌ１に設定すると共に、行枠候補Ｌ１に対応する文字の並び方向Ｌ２にｎｕｌｌを設定して、行情報の候補Ｌを初期化する（ステップ１８０２）。
【００９０】
続いて行枠候補生成部１６２５は、文字情報格納部１６１５に次の文字領域が存在するか否かを判定する（ステップ１８０４）。文字情報のリストに次の文字領域が存在する場合（ステップ１８０４：ＹＥＳ）、次の文字領域をＮとし、行枠候補Ｌ１の中心点（ｘ１、ｙ１）と次の文字領域Ｎの中心点（ｘ２、ｙ２）との差の絶対値が大きな軸（ｍａｘ（｜ｘ１−ｘ２｜、｜ｙ１−ｙ２｜））の方向を指す単位ベクトル（（０，１）又は（１，０））を文字の並び方向Ｄとして決定して、文字の並び方向Ｌ２に設定する（ステップ１８０６）。
【００９１】
ステップ１８０６の後行枠候補生成部１６２５は確認部１６２７を呼び出し、確認部１６２７は、行枠候補Ｌ１と次の文字領域Ｎを含む最小の矩形を仮の行枠候補Ｌ‘１、及び文字の並び方向Ｌ２を仮の文字の並び方向Ｌ‘２として仮の行情報の候補Ｌ’を生成する（ステップ１８０８）。そして確認部１６２７は、仮の行情報の候補Ｌ’を次の行枠として、図１０に示すフローチャートの四角１０５０で囲んだサブルーチンを実行し、実行結果の文字領域の並びが、現在の１文字目の文字領域Ｃから次の文字領域Ｎまでの文字情報のリストにおけるリスト順に一致するか否かを判定する（ステップ１８０８）。
【００９２】
実行結果の文字領域の並びが文字情報のリストにおけるリスト順に一致しない場合（ステップ１８０８：ＮＯ）、処理はステップ１８１８へ進み、行情報登録部１６３０は現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１の最後尾に追加する。また、行情報登録部１６３０は現在の次の文字領域Ｎを、文字情報のリストの一文字目とみなすために、現在の１文字目の文字領域Ｃに設定する。そして処理はステップ１８０２へ戻り、行枠候補生成部１６２５は一連の処理を繰り返す。
【００９３】
一方、実行結果の文字領域の並びが文字情報のリストにおけるリスト順に一致する場合（ステップ１８０８：ＹＥＳ）、行枠候補生成部１６２５は文字情報のリストに次の文字領域が存在するか否かを判定し（ステップ１８１０）、次の文字領域が存在する場合（ステップ１８１０：ＹＥＳ）、該次の文字領域を現在の次の文字領域Ｎとすると共に、仮の行情報の候補Ｌ’を現在の行情報の候補Ｌとして確定する（ステップ１８１２）。そして処理はステップ１８０８へ戻り、確認部１６２７と行枠候補生成部１６２５は一連の処理を繰り返す。
【００９４】
一方、ステップ１８１０において次の文字領域が存在しない場合、行枠候補生成部１６２５は仮の行情報の候補Ｌ’を現在の行情報の候補Ｌとして確定する（ステップ１８１４）。ステップ１８１４から、又は、ステップ１８０４において文字情報のリストにリストされる全ての文字情報が読み出されている場合、処理はステップ１８１６へ進み、行情報登録部１６３０は、現在の行情報の候補Ｌを行情報のリストＬＩＳＴ１の最後尾に登録し、ＬＩＳＴ１を出力する。そして処理は終了する。
【００９５】
図１９は、本願発明の任意の実施例に係る読み順決定装置としてのコンピュータ５０のハードウェア構成の一例を示した図である。コンピュータ５０は、バス２に接続されたメインＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、及びＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【００９６】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ１に命令を与え、本願発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ５０にインストールされ、コンピュータ５０を本願発明の任意の実施例に係る読み順決定装置として機能させる読み順決定プログラムや、行情報のリスト、文字情報のリストといったデータを記録することができる。
【００９７】
上記読み順決定プログラムは、圧縮モジュールと、修正モジュールと、解凍モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、圧縮処理部１２０、８２０、１２２０、又は１６２０、修正部１０５、８０５、１２０５、又は１６０５、解凍処理部１４０、８４０、１２４０、１６４０としてそれぞれ機能させる。圧縮モジュールは、行枠候補生成モジュール、行枠情報登録モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、行枠候補生成部１２５、８２５、行情報登録部１３０、８３０としてそれぞれ機能させる。これに代えて、圧縮モジュールは、行枠候補生成モジュール、行枠候補修正モジュール、行枠情報登録モジュールとを含んでもよい。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、行枠候補生成部１２２５、行枠候補修正部１２２７、行情報登録部１２３０としてそれぞれ機能させる。或いは、圧縮モジュールは、行枠候補生成モジュール、確認モジュール、行枠情報登録モジュールとを含んでもよい。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、行枠候補生成部１６２５、確認部１６２７、行情報登録部１６３０としてそれぞれ機能させる。解凍モジュールは、検出モジュール、部分集合決定モジュール、並び替えモジュール、順序決定モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、検出部１４５、１２４５、１６４５、部分集合決定部１５０、１２５０、１６５０、並び替え部１５５、１２５５、１６５５、順序決定部１６０、１２６０、１６６０としてそれぞれ機能させる。これに代えて解凍モジュールは、部分集合決定モジュール、並び替えモジュール、順序決定モジュールとを含んでもよい。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、部分集合決定部８４５、並び替え部８５０、順序決定部８５５としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【００９８】
コンピュータ５０は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータ５０は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータ５０は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータ５０は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【００９９】
以上の説明により、コンピュータ５０は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本願発明の必須構成要素となるわけではない。
【０１００】
以上、実施形態を用いて本願発明の説明をしたが、本願発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本願発明の技術的範囲に含まれる。
【０１０１】
なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。
【特許請求の範囲】
【請求項１】
文字の読み順を決定するための読み順決定装置であって、
画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報が文字の読み順に並んだリストである文字情報のリストを格納する文字情報格納部と、
前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、
前記文字情報のリストに対する文字情報の追加要求に応答して、前記行情報のリストから、追加された前記文字情報の文字領域データが示す領域を包含する行枠を有する行情報を検出する検出手段と、
前記検出手段より検出された前記行情報の前記行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、
前記部分集合内の各文字領域データを、検出された前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、
前記部分集合内の文字領域データの並び順に基づいて前記文字情報のリストを更新することにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段と、
を含む読み順決定装置。
【請求項２】
前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、該文字の並び方向に前記現在の文字領域が存在しなくなるまで、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張する行枠候補生成手段と、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを更に含み、前記行枠候補生成手段は、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、前記現在の文字領域を前記文字情報のリストの先頭として一連の処理を繰り返す、請求項１に記載の読み順決定装置。
【請求項３】
現在の前記行枠候補又は前記行情報のリストに登録された過去の前記行枠候補のいずれかに前記現在の文字領域が包含されることを条件に、前記行枠候補生成手段により現在の前記行枠候補を拡張する代わりに前記現在の文字領域を包含する前記行枠候補を、対応する文字の並び方向に対して垂直かつ前記現在の文字領域の中心点を基準に分割し、分割した行枠候補を該行枠候補に包含される文字領域データに基づいて修正し、分割により包含されなくなった各文字領域に対し該文字領域を行枠とする行情報を生成する行枠候補修正手段を更に含む、請求項２に記載の読み順決定装置。
【請求項４】
前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、前記行枠候補を前記現在の文字領域を更に含む最小の行枠に拡張する拡張処理を一定の条件の下に実行する行枠候補生成手段と、前記行枠候補生成手段による前記拡張処理の実行前に、拡張によって生成されることになる行枠候補と前記文字の並び方向とを基に文字の読み順が正しく決定されることを確認する確認部と、前記確認部による確認の失敗に応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを更に含み、前記行枠候補生成手段は、前記確認部による確認の成功を条件として前記拡張処理を実行し、前記確認が失敗した場合は、前記現在の文字領域を前記文字情報のリストの先頭として処理を繰り返す、請求項１に記載の読み順決定装置。
【請求項５】
前記画像データは、文書の１頁分の画像データ又は文書の１頁内のまとまりある領域の画像データである、請求項１に記載の読み順決定装置。
【請求項６】
ユーザから、前記文字情報のリストへの文字情報の追加指示と共に、テキスト・データ及び対応する文字領域データを文字情報として受け取り、該文字情報を前記文字情報のリストの先頭又は最後尾に追加する修正手段を更に含む、請求項１に記載の読み順決定装置。
【請求項７】
文字の読み順を決定するための読み順決定装置であって、
画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報のリストである文字情報のリストを格納する文字情報格納部と、
前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、
前記行情報のリストから行情報を読み出して、読み出した前記行情報の行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、
前記部分集合内の各文字領域データを、対応する前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、
行情報ごとの並び替えられた前記文字領域データの部分集合を前記行の並びに順に繋ぎ合わせることにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段と、
を含む読み順決定装置。
【請求項８】
コンピュータの演算処理により、文字の読み順を決定する読み順決定方法であって、前記コンピュータは、画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報が文字の読み順に並んだリストである文字情報のリストを格納する文字情報格納部と、前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部にアクセス可能であり、
（ａ）前記コンピュータが、前記文字情報のリストに対する文字情報の追加要求に応答して、前記行情報のリストから、追加された前記文字情報の文字領域データが示す領域を包含する行枠を有する行情報を検出するステップと、
（ｂ）前記コンピュータが、前記検出手段より検出された前記行情報の前記行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求めるステップと、
（ｃ）前記コンピュータが、前記部分集合内の各文字領域データを、検出された前記行情報の前記文字の並び方向に対する位置に従って並び替えるステップと、
（ｄ）前記コンピュータが、前記部分集合内の文字領域データの並び順に基づいて前記文字情報のリストを更新することにより、前記文字情報のリストにおける文字の読み順を決定するステップと、
を含む読み順決定方法。
【請求項９】
ステップ（ａ）乃至（ｄ）の処理の前に、前記文字情報のリストに基づいて前記行情報のリストを作成するために、（ｅ）前記コンピュータが、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、該文字の並び方向に前記現在の文字領域が存在しなくなるまで、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張するステップと、（ｄ）前記コンピュータが、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録するとともに、前記現在の文字領域を前記文字情報のリストの先頭としてステップ（ｅ）及び（ｄ）の処理を繰り返すステップとをさらに含む、請求項８に記載の読み順決定方法。
【請求項１０】
ステップ（ｅ）は、前記コンピュータが、現在の前記行枠候補又は前記行情報のリストに登録された既存の前記行枠候補のいずれかに前記現在の文字領域が含まれることを条件に、現在の前記行枠候補を拡張する代わりに前記現在の文字領域を包含する前記行枠候補を、対応する文字の並び方向に対して垂直かつ前記現在の文字領域の中心点を基準に分割し、分割した行枠候補を該行枠候補に包含される文字領域データに基づいて修正し、分割により包含されなくなった各文字領域に対し該文字領域を行枠とする行情報を生成するステップを含む、請求項９に記載の読み順決定方法。
【請求項１１】
ステップ（ａ）乃至（ｄ）の処理の前に、前記文字情報のリストに基づいて前記行情報のリストを作成するために、（ｅ）前記コンピュータが、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張する拡張処理を、拡張によって生成される行枠候補と前記文字の並び方向とを基に文字の読み順が正しく決定されることを条件に実行するステップと、（ｄ）前記コンピュータが、前記拡張処理の不実行に応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録するとともに、前記現在の文字領域を前記文字情報のリストの先頭としてステップ（ｅ）の処理を繰り返すステップとをさらに含む、請求項８に記載の読み順決定方法。
【請求項１２】
請求項８乃至１１に記載の読み順決定方法をコンピュータに実行させる、文字の読み順を決定する読み順決定プログラム。
【請求項１】
文字の読み順を決定するための読み順決定装置であって、
画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報が文字の読み順に並んだリストである文字情報のリストを格納する文字情報格納部と、
前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、
前記文字情報のリストに対する文字情報の追加要求に応答して、前記行情報のリストから、追加された前記文字情報の文字領域データが示す領域を包含する行枠を有する行情報を検出する検出手段と、
前記検出手段より検出された前記行情報の前記行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、
前記部分集合内の各文字領域データを、検出された前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、
前記部分集合内の文字領域データの並び順に基づいて前記文字情報のリストを更新することにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段と、
を含む読み順決定装置。
【請求項２】
前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、該文字の並び方向に前記現在の文字領域が存在しなくなるまで、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張する行枠候補生成手段と、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを更に含み、前記行枠候補生成手段は、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、前記現在の文字領域を前記文字情報のリストの先頭として一連の処理を繰り返す、請求項１に記載の読み順決定装置。
【請求項３】
現在の前記行枠候補又は前記行情報のリストに登録された過去の前記行枠候補のいずれかに前記現在の文字領域が包含されることを条件に、前記行枠候補生成手段により現在の前記行枠候補を拡張する代わりに前記現在の文字領域を包含する前記行枠候補を、対応する文字の並び方向に対して垂直かつ前記現在の文字領域の中心点を基準に分割し、分割した行枠候補を該行枠候補に包含される文字領域データに基づいて修正し、分割により包含されなくなった各文字領域に対し該文字領域を行枠とする行情報を生成する行枠候補修正手段を更に含む、請求項２に記載の読み順決定装置。
【請求項４】
前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、前記行枠候補を前記現在の文字領域を更に含む最小の行枠に拡張する拡張処理を一定の条件の下に実行する行枠候補生成手段と、前記行枠候補生成手段による前記拡張処理の実行前に、拡張によって生成されることになる行枠候補と前記文字の並び方向とを基に文字の読み順が正しく決定されることを確認する確認部と、前記確認部による確認の失敗に応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録する行情報登録手段とを更に含み、前記行枠候補生成手段は、前記確認部による確認の成功を条件として前記拡張処理を実行し、前記確認が失敗した場合は、前記現在の文字領域を前記文字情報のリストの先頭として処理を繰り返す、請求項１に記載の読み順決定装置。
【請求項５】
前記画像データは、文書の１頁分の画像データ又は文書の１頁内のまとまりある領域の画像データである、請求項１に記載の読み順決定装置。
【請求項６】
ユーザから、前記文字情報のリストへの文字情報の追加指示と共に、テキスト・データ及び対応する文字領域データを文字情報として受け取り、該文字情報を前記文字情報のリストの先頭又は最後尾に追加する修正手段を更に含む、請求項１に記載の読み順決定装置。
【請求項７】
文字の読み順を決定するための読み順決定装置であって、
画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報のリストである文字情報のリストを格納する文字情報格納部と、
前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部と、
前記行情報のリストから行情報を読み出して、読み出した前記行情報の行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求める部分集合決定手段と、
前記部分集合内の各文字領域データを、対応する前記行情報の前記文字の並び方向に対する位置に従って並び替える並び替え手段と、
行情報ごとの並び替えられた前記文字領域データの部分集合を前記行の並びに順に繋ぎ合わせることにより、前記文字情報のリストにおける文字の読み順を決定する順序決定手段と、
を含む読み順決定装置。
【請求項８】
コンピュータの演算処理により、文字の読み順を決定する読み順決定方法であって、前記コンピュータは、画像データから文字認識処理により抽出された各文字のテキスト・データ及び文字領域データからなる文字情報が文字の読み順に並んだリストである文字情報のリストを格納する文字情報格納部と、前記画像データにおいて同一方向に連続して並んでいる文字の集合を囲む行枠及び該行枠内における文字の並び方向からなる行情報が行の並び順にリストされた行情報のリストを格納する行情報格納部にアクセス可能であり、
（ａ）前記コンピュータが、前記文字情報のリストに対する文字情報の追加要求に応答して、前記行情報のリストから、追加された前記文字情報の文字領域データが示す領域を包含する行枠を有する行情報を検出するステップと、
（ｂ）前記コンピュータが、前記検出手段より検出された前記行情報の前記行枠に包含される領域を示す文字領域データの部分集合を、前記文字情報のリストから求めるステップと、
（ｃ）前記コンピュータが、前記部分集合内の各文字領域データを、検出された前記行情報の前記文字の並び方向に対する位置に従って並び替えるステップと、
（ｄ）前記コンピュータが、前記部分集合内の文字領域データの並び順に基づいて前記文字情報のリストを更新することにより、前記文字情報のリストにおける文字の読み順を決定するステップと、
を含む読み順決定方法。
【請求項９】
ステップ（ａ）乃至（ｄ）の処理の前に、前記文字情報のリストに基づいて前記行情報のリストを作成するために、（ｅ）前記コンピュータが、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、該文字の並び方向に前記現在の文字領域が存在しなくなるまで、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張するステップと、（ｄ）前記コンピュータが、前記文字の並び方向に前記現在の文字領域が存在しなくなったことに応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録するとともに、前記現在の文字領域を前記文字情報のリストの先頭としてステップ（ｅ）及び（ｄ）の処理を繰り返すステップとをさらに含む、請求項８に記載の読み順決定方法。
【請求項１０】
ステップ（ｅ）は、前記コンピュータが、現在の前記行枠候補又は前記行情報のリストに登録された既存の前記行枠候補のいずれかに前記現在の文字領域が含まれることを条件に、現在の前記行枠候補を拡張する代わりに前記現在の文字領域を包含する前記行枠候補を、対応する文字の並び方向に対して垂直かつ前記現在の文字領域の中心点を基準に分割し、分割した行枠候補を該行枠候補に包含される文字領域データに基づいて修正し、分割により包含されなくなった各文字領域に対し該文字領域を行枠とする行情報を生成するステップを含む、請求項９に記載の読み順決定方法。
【請求項１１】
ステップ（ａ）乃至（ｄ）の処理の前に、前記文字情報のリストに基づいて前記行情報のリストを作成するために、（ｅ）前記コンピュータが、前記文字情報のリストの先頭から順に文字領域データを読み出して現在の文字領域とし、最初の文字領域データで行枠候補を初期化すると共に最初の２つの文字領域データによって前記行枠候補における文字の並び方向を決定し、前記行枠候補を前記現在の文字領域を更に包含する最小の行枠に拡張する拡張処理を、拡張によって生成される行枠候補と前記文字の並び方向とを基に文字の読み順が正しく決定されることを条件に実行するステップと、（ｄ）前記コンピュータが、前記拡張処理の不実行に応答して、現在の前記行枠候補を対応する前記文字の並び方向と共に行情報として前記行情報のリストに登録するとともに、前記現在の文字領域を前記文字情報のリストの先頭としてステップ（ｅ）の処理を繰り返すステップとをさらに含む、請求項８に記載の読み順決定方法。
【請求項１２】
請求項８乃至１１に記載の読み順決定方法をコンピュータに実行させる、文字の読み順を決定する読み順決定プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図１１】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図１１】
【図１３】
【公開番号】特開２０１２−２５６１６０（Ｐ２０１２−２５６１６０Ａ）
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願番号】特願２０１１−１２８２１３（Ｐ２０１１−１２８２１３）
【出願日】平成２３年６月８日（２０１１．６．８）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願日】平成２３年６月８日（２０１１．６．８）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]