(57)【特許請求の範囲】
【請求項１】
入力画像から複数の文字領域とセパレータ領域と図領域とを抽出する領域抽出ステップと、
前記領域抽出ステップで抽出されたセパレータ領域と図領域とを長い順に取り出す取り出しステップと、
前記取り出しステップで取り出された順に前記セパレータ領域と図領域とを分割位置として用いて前記入力画像を順次分割していくことによって、前記入力画像を複数の記事に分ける記事分離ステップと、
前記記事分離ステップで分けられた複数の記事それぞれにおいて、該記事内に含まれる前記文字領域を各文字領域間の位置関係に基づいてグループ化することによって複数のグループを生成するグループ生成ステップと、
前記記事分離ステップで分けられた複数の記事の順序と前記グループ生成ステップで生成された複数のグループの順序とを決定する順序決定ステップと、
前記順序決定ステップで決定された各記事の順序と各グループの順序とに基づいて、前記入力画像全体における前記文字領域の順序を決定する文字領域順序決定ステップと
を有することを特徴とする順序付け方法。
【請求項２】
前記セパレータ領域は、該セパレータ領域の外接矩形の高さ又は幅が、前記入力画像の高さ又は幅に対して所定の閾値以上の割合を有するセパレータ領域であることを特徴とする請求項１に記載の順序付け方法。
【請求項３】
前記図領域は、該図領域の外接矩形の高さ又は幅が、前記入力画像の高さ又は幅に対して所定の閾値以上の割合を有する図領域であることを特徴とする請求項１に記載の順序付け方法。
【請求項４】
前記所定の閾値は、前記入力画像の幅又は高さ又は面積に応じて変化することを特徴とする請求項２又は３のいずれかに記載の順序付け方法。
【請求項５】
前記グループ生成ステップでは、複数階層からなるグループを生成することを特徴とする請求項１に記載の順序付け方法。
【請求項６】
前記順序決定ステップでは、組方向に従って前記記事の順序と前記グループの順序とを決定することを特徴とする請求項１に記載の順序付け方法。
【請求項７】
入力画像から複数の文字領域とセパレータ領域と図領域とを抽出する領域抽出手段と、
前記領域抽出手段で抽出されたセパレータ領域と図領域とを長い順に取り出す取り出し手段と、
前記取り出し手段で取り出された順に前記セパレータ領域と図領域とを分割位置として用いて前記入力画像を順次分割していくことによって、前記入力画像を複数の記事に分ける記事分離手段と、
前記記事分離手段で分けられた複数の記事それぞれにおいて、該記事内に含まれる前記文字領域を各文字領域間の位置関係に基づいてグループ化することによって複数のグループを生成するグループ生成手段と、
前記記事分離手段で分けられた複数の記事の順序と前記グループ生成手段で生成された複数のグループの順序とを決定する順序決定手段と、
前記順序決定手段で決定された各記事の順序と各グループの順序とに基づいて、前記入力画像全体における前記文字領域の順序を決定する文字領域順序決定手段と
を有することを特徴とする順序付け装置。
【請求項８】
前記セパレータ領域は、該セパレータ領域の外接矩形の高さ又は幅が、前記入力画像の高さ又は幅に対して所定の閾値以上の割合を有するセパレータ領域であることを特徴とする請求項７に記載の順序付け装置。
【請求項９】
前記図領域は、該図領域の外接矩形の高さ又は幅が、前記入力画像の高さ又は幅に対して所定の閾値以上の割合を有する図領域であることを特徴とする請求項７に記載の順序付け装置。
【請求項１０】
前記所定の閾値は、前記入力画像の幅又は高さ又は面積に応じて変化することを特徴とする請求項８又は９のいずれかに記載の順序付け装置。
【請求項１１】
前記グループ生成手段は、複数階層からなるグループに分けることを特徴とする請求項７に記載の順序付け装置。
【請求項１２】
前記順序決定手段は、該各グループの組方向に従って該文字領域の順序を決定することを特徴とする請求項１０に記載の順序付け装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ＯＣＲ（光学的文字認識）装置、複写機、ファクシミリ等の電子装置において、特に入力画像に対して抽出された文字領域に読み順を付ける文字の順序付け方法に関するものである。
【０００２】
【従来の技術】
従来の順序付けの方法として、複数に分割された文書領域の位置から縦書きの場合は右から左方向に順序を付け、上下方向に関しては、上から下方向に順序を付けていくもの等がある。
【０００３】
【発明が解決しようとしている課題】
しかしながら、上述の従来技術では新聞記事等、原稿の中に複数の記事が様々な大きさかつ複雑な配置で存在する場合に、複数の記事の本文が入り組んでしまい正しく読み順を付けることができず、オペレータの手による修正等が必要となるという問題点があった。
【０００４】
【課題を解決するための手段】
上記課題を解決するために、本発明の順序付け方法は、入力画像から複数の文字領域とセパレータ領域と図領域とを抽出する領域抽出ステップと、前記領域抽出ステップで抽出されたセパレータ領域と図領域とを長い順に取り出す取り出しステップと、前記取り出しステップで取り出された順に前記セパレータ領域と図領域とを分割位置として用いて前記入力画像を順次分割していくことによって、前記入力画像を複数の記事に分ける記事分離ステップと、前記記事分離ステップで分けられた複数の記事それぞれにおいて、該記事内に含まれる前記文字領域を各文字領域間の位置関係に基づいてグループ化することによって複数のグループを生成するグループ生成ステップと、前記記事分離ステップで分けられた複数の記事の順序と前記グループ生成ステップで生成された複数のグループの順序とを決定する順序決定ステップと、前記順序決定ステップで決定された各記事の順序と各グループの順序とに基づいて、前記入力画像全体における前記文字領域の順序を決定する文字領域順序決定ステップとを有する。
また、上記課題を解決するために、本発明の順序付け装置は、入力画像から複数の文字領域とセパレータ領域と図領域とを抽出する領域抽出手段と、前記領域抽出手段で抽出されたセパレータ領域と図領域とを長い順に取り出す取り出し手段と、前記取り出し手段で取り出された順に前記セパレータ領域と図領域とを分割位置として用いて前記入力画像を順次分割していくことによって、前記入力画像を複数の記事に分ける記事分離手段と、前記記事分離手段で分けられた複数の記事それぞれにおいて、該記事内に含まれる前記文字領域を各文字領域間の位置関係に基づいてグループ化することによって複数のグループを生成するグループ生成手段と、前記記事分離手段で分けられた複数の記事の順序と前記グループ生成手段で生成された複数のグループの順序とを決定する順序決定手段と、前記順序決定手段で決定された各記事の順序と各グループの順序とに基づいて、前記入力画像全体における前記文字領域の順序を決定する文字領域順序決定手段とを有する。
【０００５】
【作用】
以上の構成において、新聞記事等、原稿の中に複数の記事が入り組んでいる場合でも、正しく読み順を付けることができ、修正等の手間を削減できる。
【０００６】
【実施例】
図２５は本実施例における装置の構成を表わすブロック図である。１００１は本装置全体の処理を実行するＣＰＵであって、ＲＯＭ１００２に格納されている制御プログラムに従って判断及び処理を制御する。１００２はＲＯＭであり、本実施例において説明するフローチャートの制御プログラム、或いは処理に用いる予め定まっているパラメータ等のデータを記憶している。１００３はＲＡＭであり、ＣＰＵ１００１での処理中のデータを記憶するワーキングメモリエリアを備える。１００４はスキャナであり、原稿画像を光学的に読み込む。読み込まれた画像データはＲＡＭ１００３に記憶できる。１００５はキーボードであり、各種コードの入力、オペレータの指示が入力できる。１００６はポインティングデバイスであり、表示器１００７の表示画面上の所望の位置を指示でき、また、ボタンをクリックすることにより選択、取消の指示を入力することもできる。１００７は表示器であり、ＣＲＴ或いは液晶表示器からなる。１００８は例えばＬＢＰ、インクジェット式等のプリンタ、１００９は例えばＦＤなどの外部記憶装置、１０１０はこれら各構成間でのデータの授受を行う為のデータバスである。
【０００７】
（第１の実施例）
図１は、本実施例の順序付け方法を表すフローチャートである。
同図において、
▲１▼ステップＳ１０１
スキャナー１００４等から画像を入力する。
【０００８】
▲２▼ステップＳ１０２
次にステップＳ１０１で入力した画像の領域分割を行い、文字、セパレータ、図等の領域を画像から抽出する。このステップでの領域分割方法は、例えば特願平４−２４３２５２号公報等で示される方法がある。
ここで分割された領域情報は全てＲＡＭ１００３に格納する。
【０００９】
▲３▼ステップＳ１０３
次に画像から抽出された文字、セパレータ、図等の領域を階層的なグループに分ける。以下このステップＳ１０３でのグループ化について詳細に説明する。図２は、画像から抽出された領域を画像全体（ＲＯＯＴ）、記事、段組、同一段グループ、段落（同一行グループ）、行という６階層にグループ分けしたところを示した図である。２０１は階層０即ち画像全体である。２０２は記事１である。２０３は同じ階層内において更に幾つかあることを示している。階層内のグループの個数は、階層０は１個のみ、階層１〜４は１個以上、階層５は０個以上存在する。２０４は段組１であり、記事１（２０２）に属している。２０５は同一段グループであり、段組１（２０４）に属している。２０６は段落１であり、同一段グループ１（２０５）に属している。段落１は行からなるグループ階層５を持っていない。２０７は段落２すなわち行１、行２からなる同一行グループであり、同一段グループ１（２０５）に属している。２０８は行１であり、段落２（２０７）に属している。
【００１０】
図３はステップＳ１０３について更に詳細なフローチャートである。
【００１１】
図４は、領域分割によって抽出された文字領域、セパレータ領域、図領域、グループ化によってできた記事、段組、同一段グループ、同一行グループの一部を示している。図４において、４０１はスキャナー等から入力した縦書きの原稿画像である。４１３、４４３は抽出した文字領域、特に見出し領域かつ記事、同一段グループ、段落でもある。４２６、４２７は抽出した文字領域、特に見出し領域かつ行である。４１４、４１６、４３０、４４４は抽出した文字領域かつ同一段グループである。４２８、４２９は、抽出した文字領域かつ段落である。４１５、４４５、４４６は抽出したセパレータ領域である。４２５は抽出した図領域である。４１１、４２１、４４１はセパレータ４４６及び図領域４２５によって分割した記事領域である。４１２、４２２、４４２は段組である。４２３は同一段グループである。
【００１２】
図５は、ステップＳ３０１についての詳細なフローチャートである。図６はステップＳ３０４についての詳細なフローチャートである。図７はステップＳ３０２についての詳細なフローチャートである。図８は図４の画像から抽出された領域を画像全体、記事、段組、同一段グループ、段落（同一行グループ）、行という６階層にグループ分けしたところを示した図である。図９はステップＳ１０４についての詳細なフローチャートである。図１０はステップＳ９０１についての詳細なフローチャートである。図１１はステップＳ９０２についての詳細なフローチャートである。図１２はステップＳ９０３についての詳細なフローチャートである。図１３はステップＳ９０４についての詳細なフローチャートである。図１４はステップＳ９０５についての詳細なフローチャートである。図１５はステップＳ３０５についての詳細なフローチャートである。図１６は図４の画像から抽出された文章領域４２６である。図１６において、１６０１は文字領域４２６の黒画素のＹ方向（縦方向）のヒストグラムである。１６０２はヒストグラム１６０１から求めた黒画素の幅である。
【００１３】
図３のフローチャートに従って、ステップＳ１０３を説明する。
【００１４】
◎ステップＳ３０１
画像全体に対してある一定割合以上の長さを持つセパレータ、図によって画像を１個以上の領域に分け、記事とする。図４及びフローチャート図５に従って詳細に説明する。まず、ステップＳ５０１では、図１の領域分割Ｓ１０２によって抽出されたセパレータまたは図を一つ取り出す。次に、取り出したセパレータまたは図の外接矩形の高さと幅のどちらが大きいか比較する。幅のほうが大きい場合には、ステップＳ５０３で画像全体の幅をＬａｌｌ、セパレータまたは図の幅をＬｓｅｐとする。また、高さの方が大きい場合には、ステップＳ５１２で画像全体の高さをＬａｌｌ、セパレータまたは図の高さをＬｓｅｐとする。ステップＳ５０４で、
Ｌｓｅｐ÷Ｌａｌｌ≧α…（１）
を充たすか否か判断する。ここで、αは閾値でここでは０．４とする。式（１）を充たすセパレータまたは図をステップＳ５０５で配列ＬＯＮＧＳＥＰに格納する。充たさない場合はステップＳ５０６に進む。図４の例では、セパレータ４１５、４４５は式（１）を充たしていない。セパレータ４４６及び図領域４２５は式（１）を充たしているので配列ＬＯＮＧＳＥＰに格納する。
【００１５】
ステップＳ５０６では、すべてのセパレータまたは図を処理したか判断する。すべて処理した場合は、ステップＳ５０７に進む。また、処理していないセパレータまたは図が残っている場合は、ステップＳ５０１に戻って処理を継続する。
【００１６】
ステップＳ５０７では、配列ＬＯＮＧＳＥＰに格納したセパレータ、図を幅または高さの長い方を比較して長い順に並べる。
【００１７】
ステップＳ５０８で、配列ＬＯＮＧＳＥＰに格納したセパレータまたは図を長い順にひとつ取り出す。ステップＳ５０９で、取り出したセパレータ、図により領域を二分する。図４では、まず初めに一番長いセパレータ４４６によって画像４０１を左右に二分する。分割した領域の左側の領域が記事４４１である。
【００１８】
次にステップＳ５１０で、配列ＬＯＮＧＳＥＰに格納されたすべてのセパレータ、図に関して処理したか判断する。すべて処理した場合は、ステップＳ５１１に進む。図４の例では、図領域４２５に関して未処理なのでステップＳ５０８に戻る。図領域４２５によって先程分割してできた右側の領域を上下に分割する。そうしてできたのが記事４１１、４２１である。
【００１９】
配列ＬＯＮＧＳＥＰに格納されたすべてのセパレータ、図に関して処理したのでステップＳ５１１に進む。
【００２０】
ステップＳ５１１では、枠や表の領域も別領域として分離する。例えば、新聞のコラムの文字や表の中の文やデータ等は、他の本文と混在することはない。よってこれらも、別の記事として扱う必要があるため、別領域として分離する。次にステップＳ５１３に進む。
【００２１】
ステップＳ５１３では、分割した領域を各々記事としてＩＤ番号をつける。図４では、それぞれ記事４１１を記事１、記事４２１を記事２、記事４４１を記事３とし、階層０の原稿画像４０１から階層１の記事１、２、３が分割できる。
【００２２】
◎ステップＳ３０２
領域分割で取り出した文字領域の中で一行のみからなる領域が並んでいる場合には、それらを合わせて同一行グループとし、各々の領域を行とする。図４及びフローチャート図７に従って詳細に説明する。まずステップＳ７０１で、ステップＳ３０１で分割できたうちの一つの記事を取り出す。図４及び図１６の例では、記事ＩＤ２の記事４２１を取り出して説明する。
【００２３】
次にステップＳ７０２で、記事内の文字領域の領域情報を一つＲＡＭ１００３から取り出す。ステップＳ７０３で、取り出した領域のヒストグラムをとり、一行のみからなる文字領域か判定する。一行のみからなる文字領域であれば、ステップＳ７０４に進む。一行のみからなる文字領域ではない場合は、ステップＳ７０５に進む。
【００２４】
取り出した文字領域が何行からなるかを調べるＳ７０３の詳細な方法を図１６に従って示す。文字領域４２６の組方向が縦書きであることは、ステップＳ１０２の領域分割の結果から分かっている。縦書きの時は、文字領域４２６の黒画素の縦方向のヒストグラムを取る。横書きの時は同様に横方向のヒストグラムを取る。図１６の例では、縦方向のヒストグラムを取った結果がヒストグラム１６０１である。ヒストグラム１６０１を横方向に見ることによって、黒画素の存在が連続する箇所が何か所あるか数え、それが求める行数となる。ヒストグラム１６０１の例では黒画素の存在が連続する箇所が１か所なので、文字領域４２６の行数は１行である。１行なので、ステップＳ７０４へ進む。
【００２５】
ステップＳ７０４では、文字領域の組方向と同じ方向に隣り合って一行のみからなる文字領域があり、かつ間にセパレータや図がなく、文字の大きさがほぼ同じ、かつ組方向が同じで、隙間も大きくないならば同一行グループとする。図４の記事４２１の文字領域４２６の例では、ステップＳ７０３で文字領域４２６が一行のみからなると判定され、縦書きなので縦方向に１行のみからなる文字領域がないか捜す。文字領域４２７が文字領域４２６と縦方向に並んでいて、しかも１行のみからなっていることが分かる。また、文字領域４２６と文字領域４２７の間にセパレータや図がないことは明白である。詳しく述べると２つの文字領域が縦方向に並んでいるので、並んでいる上の領域、この場合は文字領域４２６の下底と、並んでいる下の領域、この場合は文字領域４２７の上底から構成される平行四辺形の中にセパレータまたは図の一部または全部が含まれているか調べる。横並びの時は、同様に右辺と左辺により構成される平行四辺形内にセパレータまたは図が含まれるか調べる。次に文字の大きさを調べる。図１６の例で説明すると、ヒストグラム１６０１の幅１６０２を簡易的に文字の大きさとする。つまり、おおよその文字幅を文字大きさとする。ヒストグラムを取った時に黒画素の連続する領域が数カ所に分かれている時、つまり文字領域内に複数行が存在する時は、それらの幅の平均を取って文字大きさとする。本文字領域４２６と文字領域４２７の文字大きさを比較して、大きい方をＣｂｉｇ、小さい方をＣｓｍａｌｌとする。
【００２６】
Ｃｓｍａｌｌ÷Ｃｂｉｇ≧α２…（２）
を充たせば、文字大きさが同じとする。ただし、α２は閾値でここでは０．９とする。文字領域４２６と文字領域４２７の場合は、式（２）を充たすので文字大きさが同じと判定する。次に組方向が同じか調べる。
【００２７】
前述した様に文字領域４２６は縦書きであり、文字領域４２７も縦書きであるので、組方向は共に同じと判定する。
【００２８】
次に隙間が大きくないか調べる。文字領域４２６と文字領域４２７の間の隙間をＧ、文字大きさの小さい方をＣｓｍａｌｌとすると、
Ｇ÷Ｃｓｍａｌｌ≦α３…（３）
を充たせば、文字領域４２６と文字領域４２７の隙間は大きくないと判定する。ただし、α３は閾値でここでは１０とする。従って、文字領域４２６と文字領域４２７を、あわせて同一行グループ４２４とする。また、文字領域４２６と文字領域４２７を、行と判定する。
【００２９】
ステップＳ７０５では、すべての文字領域に関して処理したか判定する。すべてを処理したのであれば、ステップＳ７０６に進む。処理していない文字領域があればステップＳ７０２に戻って、同一行グループの判定を行う。文字領域４２８、４２９、４３０は複数行からなるので行にはならない。ステップＳ７０６では、行に各々ＩＤ番号を付ける。
【００３０】
ステップＳ７０７では、すべての記事に関して処理したか判定する。すべてを処理したのであれば、ステップＳ３０２を終了してステップＳ３０３に進む。処理していない記事があればステップＳ７０１に戻って、同一行グループの判定を行う。
【００３１】
◎ステップＳ３０３
ここでは、ステップＳ１０２の領域分割の結果をそのまま段落としてＩＤ番号を付ける。ただし、ステップＳ３０２で生成された同一行グループが存在すれば同様に段落とし、ＩＤ番号をつける。ステップＳ３０２で行となった領域は段落とはしない。図４の例では、文字領域４２６と文字領域４２７から生成した同一行グループ４２４も段落として扱う。
【００３２】
◎ステップＳ３０４
ここでは、段組の一つの段となる段落を、階層３の「同一段グループ」とする。図４の例では、段落４１３、段落４１４、段落４１６、段落（同一行グループ）４２４、段落４３０、段落４４３、段落４４４はそれぞれ一つの領域のみで同一段グループを形成する。段落４２８、段落４２９は共に同じ同一段グループに属する。
【００３３】
図６のフローチャートに従って記事２に関して説明する。ステップＳ６０１で、一つの記事を取り出す。ここでは、記事２を取り出す例を示す。ステップＳ６０２で、記事の組方向を判定する。図４の記事２の例では、記事２に属する文字領域の全てが縦書きであることはステップＳ１０２の領域分割の結果で分かっているので、記事２の組方向は縦書きであると分かる。仮に縦書きと横書きの文字領域が混在していた場合は、各々の面積を求めて大きい方の組方向とする。または、各々の個数の大きい方の組方向とする。縦書きなのでステップＳ６０３に進む。横書きの場合はステップＳ６０９に進む。
【００３４】
ステップＳ６０３で、記事内の段落を高さの大きい順に並べる。ステップＳ６０４で、どの同一段グループにも属していない一つの段落を並べた順に取り出し基本同一段グループとする。ステップＳ６０５で、どの同一段グループにも属していない他の段落を並べた順に取り出し比較段落とすると共に、基本同一段グループと比較して、文字の大きさがほぼ等しく、あいだに記事の組方向と逆方向のセパレータや他の同一段グループに属する段落がなく、領域が記事の組方向と逆方向に重なっていて、隙間も余り大きく開いてないなら、比較段落を基本同一段グループと同じ同一段グループとして結合する。どの同一段グループにも属していない他の段落を比較として繰り返す。
【００３５】
図４の記事２の例では、まず段落（同一行グループ）４２４が基本同一段グループ４２４となるが、文字の大きさが他の段落と違うため、単独で同一段グループを形成する。次に段落４２８が基本段落となる。比較段落４２９とのあいだで、式（２）を充たし、文字の大きさが等しいと判定する。また、間に記事の組方向と逆方向（つまり横方向）のセパレータや他の同一段グループに属する段落もない。判定の仕方は、ステップＳ７０４で述べた方法と同じである。次に基本同一段グループと比較段落の記事の組方向と逆方向（つまり横方向）の重なり具合を判定する。基本段落と比較段落の高さ（横書きの時は幅）の小さい方をＨｓｍａｌｌ、横方向に重なっている長さをＫとすると、
Ｋ÷Ｈｓｍａｌｌ≧α４…（４）
を充たせば、重なっていると判定する。ただし、α４は閾値でここでは０．８とする。基本同一段グループ４２８と比較段落４２９は式（４）を充たす。次に隙間を調べる。基本同一段グループ４２８と比較段落４２９の間の隙間は式（３）を充たすので隙間は大きくないと判定する。よって比較段落４２９を基本同一段グループ４２８と同じ同一段グループとし結合して一つの基本同一段グループとする。同様に、段落４３０を比較段落として調べる。領域が横方向に式（４）を充たさないので同一段グループとはしない。故に、段落４２８と段落４２９のみが同一段落となり、合わせて階層３の同一段グループ４２３を作る。
【００３６】
ステップＳ６０６で全ての段落がいずれかの同一段グループに属したか調べる。図４の記事２の例では、まだ段落４３０が残っているので、ステップＳ６０４に進む。段落４３０は基本同一段グループとなるが、ステップＳ６０５で比較段落がないので、段落４３０単独で同一段グループを形成する。全ての段落が同一段グループに属したので、ステップＳ６０７に進む。
【００３７】
ステップＳ６０７では、同一段グループに各々ＩＤ番号を付ける。段落４２４を同一段グループ１、同一段グループ４２３を同一段グループ２に、段落４３０を同一段グループ３とする。
【００３８】
ステップＳ６０８で、全ての記事を処理したか判定する。全ての記事を処理したらステップＳ３０４を終了し、ステップＳ３０５に進む。処理していない記事が残っていればステップＳ６０１に戻って処理を続ける。
【００３９】
◎ステップＳ３０５
ここでは、同じ段組となる同一段グループをまとめて階層２の「段組」とする。図４の記事４１１、記事４２１の例では、同一段グループ４１３、４２４、４４３はそれぞれ一つの同一段グループのみで段組を形成する。同一段グループ４１４、４１６は段組４１２を形成する。同様に記事２では、同一段グループ４２３、４３０は段組４２２を形成する。
【００４０】
図１５のフローチャートに従って記事４２１に関して説明する。ステップＳ１５０１で、一つの記事を取り出す。ここでは、記事４２１を取り出すことにする。ステップＳ１５０２で、記事の組方向を判定する。これは、ステップＳ６０２と同様である。ここでは記事の組方向は縦書きである。縦書きなのでステップＳ１５０３に進む。同様に横書きの場合はステップＳ１５０９に進む。
【００４１】
ステップＳ１５０３で、記事内の同一段グループを右から順に並べる。ステップＳ１５０４で、どの段組にも属していない一つの同一段グループを並べた順に取り出し基本段組とする。ステップＳ１５０５で、どの段組にも属していない他の同一段グループを並べた順に取り出し比較同一段グループとすると共に、基本段組と比較して、文字の大きさがほぼ等しく、隣り合って領域が組方向と同じ方向に重なっていて、隙間も余り大きく開いてないなら、比較同一段グループを基本段組と同じ段組として結合する。どの段組にも属していない他の同一段グループを比較同一段グループとして繰り返す。
【００４２】
図４の記事４２１の例では、まず同一段グループ４２４が基本段組４２４となるが、文字の大きさが他の段組と違うため、単独で基本段組を形成する。次に同一段グループ４２３が基本段組４２３となる。比較同一段グループ４３０とのあいだで、式（２）を充たし、文字の大きさが等しいと判定する。
【００４３】
次に基本段組と比較同一段グループの記事の組方向と逆方向（つまり横方向）の重なり具合を判定する。基本段落と比較同一段グループの高さ（横書きの時は幅）の小さい方をＨｓｍａｌｌ、横方向に重なっている長さをＫとすると、式（４）を充たしているので、重なっていると判定する。また隣り合っていることは明白である。調べ方は、ステップＳ７０４で述べたのと同様に、間に他の同一段グループがないか調べる。
【００４４】
次に隙間を調べる。基本段組４２３と比較同一段グループ４３０の間の隙間は式（３）を充たすので隙間は大きくないと判定する。よって比較同一段グループ４３０を基本段組４２３と同じ段組として、基本段組に結合して、段組４２２を形成する。他に比較同一段グループとすべき同一段グループはないのでステップＳ１５０５を終了し、ステップＳ１５０６に進む。ステップＳ１５０６で全ての同一段グループがいずれかの段組に属したか調べる。全ての同一段グループが段組に属したら、ステップＳ１５０７に進む。
【００４５】
ステップＳ１５０７では、段組に各々ＩＤ番号を付ける。段組４２４を段組１、段組４２２を段組２とする。
【００４６】
ステップＳ１５０８で、全ての記事を処理したか判定する。全ての記事を処理したらステップＳ３０５を終了し、グループ化が完了する。処理していない記事が残っていればステップＳ１５０１に戻って処理を続ける。
【００４７】
以上でステップＳ１０３を終了する。図４の例で、ステップＳ１０３でグループ化した結果を階層的に示した図が図８である。図８で、各番号は図４の番号に対応している。異なる階層で同じ番号がついているものがあるが、それは単独で一つの段落や同一段グループを構成しているためである。例えば、記事１の段組１は単独の同一段グループ１から構成されており、更に単独の段落１、即ち文字領域４１３から構成されているので、全て同じ番号の４１３となる。
【００４８】
▲４▼ステップＳ１０４
グループ別に順序付けを行い、最後に画像全体に関する順序を付ける。
【００４９】
以下、グループ別順序付けについて詳細に説明する。
【００５０】
図９はステップＳ１０４についての詳細なフローチャートである。図１０はステップＳ９０１についての詳細なフローチャートである。図１１はステップＳ９０２についての詳細なフローチャートである。図１２はステップＳ９０３についての詳細なフローチャートである。図１３はステップＳ９０４についての詳細なフローチャートである。図１４はステップＳ９０５についての詳細なフローチャートである。図１７はステップＳ９０６についての詳細なフローチャートである。図９のフローチャートに従って、ステップＳ１０４を説明する。
【００５１】
◎ステップＳ９０１
全て同一行グループ内の行にそれぞれ順序付けをする。図４及びフローチャート図１０に従って詳細に説明する。
【００５２】
ステップＳ１００１で階層４の一つの同一行グループを取り出す。図４の例では、同一行グループは同一行グループ４２４のみである。
【００５３】
ステップＳ１００２で同一行グループの組方向は横書きか判定する。横書きならステップＳ１００３へ進む。縦書きならステップＳ１００４に進む。組方向の判定方法は、ステップＳ６０２と同様である。同一行グループ４２４は、縦書きの行４２６、行４２７からなるので、縦書きと判定し、ステップＳ１００４に進む。
【００５４】
ステップＳ１００４では、同一行グループの中に含まれる階層５の行に上から順に番号をつける。行４２６と行４２７では、行４２６が上なので、行４２６、行４２７の順に順番を付ける。
【００５５】
ステップＳ１００５で、すべての同一行グループを処理したか判定する。全て処理していればステップＳ９０１を終了してステップＳ９０２に進む。残っていれば、ステップＳ１００１に戻って処理を続ける。図４の例では、全て処理したのでステップＳ９０１を終了して、ステップＳ９０２に進む。
【００５６】
◎ステップＳ９０２
全て同一段グループ内の段落及び同一行グループにそれぞれ順序付けをする。図４及びフローチャート図１１に従って詳細に説明する。
【００５７】
ステップＳ１１０１で一つの同一段グループを取り出す。図４の例では、複数の段落から構成する同一段グループは同一段グループ４２３のみであるので、同一段グループ４２３を中心に説明する。
【００５８】
ステップＳ１１０２で同一段グループの組方向は横書きか判定する。横書きならステップＳ１１０３へ進む。縦書きならステップＳ１１０４に進む。組方向の判定方法は、ステップＳ６０２と同様である。同一段グループ４２３は、縦書きの段落４２８、段落４２９からなるので、縦書きと判定し、ステップＳ１１０４に進む。
【００５９】
ステップＳ１１０４では、同一段グループの中に含まれる段落及び同一行グループに右から順に番号をつける。段落４２８と段落４２９では、段落４２８が右なので、段落４２８、段落４２９の順に順番を付ける。
【００６０】
ステップＳ１１０５で、すべての同一段グループを処理したか判定する。全て処理していればステップＳ９０２を終了してステップＳ９０３に進む。残っていれば、ステップＳ１１０１に戻って処理を続ける。
【００６１】
◎ステップＳ９０３
全ての記事内の同一段グループにそれぞれ順序付けをする。図４及びフローチャート図１２に従って詳細に説明する。
【００６２】
ステップＳ１２０１で一つの段組を取り出す。図４の例では、段組４２２に関して説明する。
【００６３】
ステップＳ１２０２で段組の組方向は横書きか判定する。横書きならステップＳ１２０３へ進む。縦書きならステップＳ１２０４に進む。組方向の判定方法は、ステップＳ６０２と同様である。段組４２２は、縦書きの同一段グループ４２３、同一段グループ４３０からなるので、縦書きと判定し、ステップＳ１２０４に進む。
【００６４】
ステップＳ１２０４では、段組の中に含まれる同一段グループを上から順に番号をつける。同一段グループ４２３と同一段グループ４３０では、同一段グループ４２３が上なので、同一段グループ４２３、同一段グループ４３０の順に番号を付ける。
【００６５】
ステップＳ１２０５で、すべての段組を処理したか判定する。全て処理していればステップＳ９０３を終了してステップＳ９０４に進む。残っていれば、ステップＳ１２０１に戻って処理を続ける。
【００６６】
◎ステップＳ９０４
全ての記事内の段組にそれぞれ順序付けをする。
【００６７】
図４及びフローチャート図１３に従って詳細に説明する。ステップＳ１３０１で一つの記事を取り出す。図４の例では、記事４２１に関して説明する。
【００６８】
ステップＳ１３０２で記事の組方向は横書きか判定する。横書きならステップＳ１３０３へ進む。縦書きならステップＳ１３０４に進む。組方向の判定方法は、ステップＳ６０２と同様である。記事４２１は、縦書きの段組４２４、段組４２２からなるので、縦書きと判定し、ステップＳ１３０４に進む。
【００６９】
ステップＳ１３０４では、記事の中に含まれる段組に右から順に番号をつける。段組４２４と段組４２２では、段組４２４が右なので、段組４２４、段組４２２の順に番号を付ける。
【００７０】
ステップＳ１３０５で、すべての記事を処理したか判定する。全て処理していればステップＳ９０４を終了してステップＳ９０５に進む。残っていれば、ステップＳ１３０１に戻って処理を続ける。
【００７１】
◎ステップＳ９０５
記事にそれぞれ順序付けをする。図４及びフローチャート図１４に従って詳細に説明する。
【００７２】
ステップＳ１４０１で画像全体の組方向は横書きか判定する。横書きならステップＳ１４０２へ進む。縦書きならステップＳ１４０３に進む。組方向の判定方法は、ステップＳ６０２と同様である。画像４０１は、縦書きの記事４１１、記事４２１、記事４４１からなるので、縦書きと判定し、ステップＳ１４０３に進む。
【００７３】
ステップＳ１４０３では、画像全体の中に含まれる記事に右から順に番号をつけて、ステップＳ９０５を終了して、ステップＳ９０６に進む。記事４１１、記事４２１、記事４４１の順に順番を付ける。
【００７４】
◎ステップＳ９０６
画像全体に関して全ての文字領域に全体としての順序付けをする。
【００７５】
図４及びフローチャート図１７に従って詳細に説明する。ステップＳ１７０１で、変数ＯＲＤＥＲに１を代入する（初期化）。この変数値が文字領域の画像全体に関する順番となる。ステップＳ１７０２で、記事を番号の小さい順に一つ取り出す。ここで番号とは、ステップＳ９０１からステップＳ９０５で付けた各々のＩＤ番号をさす。ステップＳ１７０３で、ステップＳ１７０２で取り出した記事内の段組を番号の小さい順に一つ取り出す。ステップＳ１７０４で、ステップＳ１７０３で取り出した段組内の同一段グループを番号の小さい順に一つ取り出す。ステップＳ１７０５で、ステップＳ１７０４で取り出した同一段グループ内の段落を番号の小さい順に一つ取り出す。ステップＳ１７０６で、ステップＳ１７０５で取り出した段落は同一行グループか判定する。同一行グループであれば、ステップＳ１７０７に進む。同一行グループでなければ、ステップＳ１７０８に進む。ステップＳ１７０７で、ステップＳ１７０５で取り出した段落内の行を番号の小さい順に一つ取り出す。ステップＳ１７０９で、行に変数ＯＲＤＥＲの順番を付け、ＯＲＤＥＲに１加える。ステップＳ１７１０では、全ての行を処理したか判定する。全ての行を処理していればステップＳ１７１１に進む。残っていれば、ステップＳ１７０７に戻って処理を続ける。また、ステップＳ１７０８では、段落に変数ＯＲＤＥＲの順番を付け、ＯＲＤＥＲに１加える。ステップＳ１７１１では、すべての段落を処理したか判定する。全ての段落を処理していればステップＳ１７１２に進む。残っていれば、ステップＳ１７０５に戻って処理を続ける。ステップＳ１７１２では、全ての同一段グループを処理したか判定する。全ての同一段グループを処理していればステップＳ１７１３に進む。残っていれば、ステップＳ１７０４に戻って処理を続ける。ステップＳ１７１３では、全ての段組を処理したか判定する。全ての段組を処理していればステップＳ１７１４に進む。残っていれば、ステップＳ１７０３に戻って処理を続ける。ステップＳ１７１４では、全ての記事を処理したか判定する。全ての記事を処理していればステップＳ９０６を終了する。残っていれば、ステップＳ１７０２に戻って処理を続ける。以上でステップＳ１０４を終了する。
【００７６】
（第２の実施例）
第１の実施例では、画像から抽出された領域を画像全体（ＲＯＯＴ）、記事、段組、同一段グループ、段落（同一行グループ）、行という６階層にグループ分けした場合について説明したが、３階層のみのグループで、内容毎に分かれる複数のグループに分割してもよい。その場合の３階層を示したのが、図１８である。ここでは内容毎に分かれる複数のグループとは、図１８の階層１の記事をさしている。例えば、同じ紙面内で、ある政治関係の記事が記事１となり、社説が記事２、コラムが記事３となる等である。また、段落は、図１のステップＳ１０２の領域分割の結果として画像から抽出されたすべての領域である。
【００７７】
本実施例の順序付け方法を表すフローチャートは図１に示す第一の実施例と同様である。以上の説明により、前述の第一の実施例と同様の作用、効果が得られる。
【００７８】
（第３の実施例）
図３のフローチャートで示す通り、図１のステップＳ１０３のグループ化に関する処理において、第１の実施例では、記事、行と同一行グループ、段落、同一段グループの順にグループ化した場合について説明したが、異なる順にグループ化してもよい。例えば、記事、同一段グループ、段組、行と同一行グループ、段落の順にグループ化してもよい。
【００７９】
本実施例の順序付け方法を表すフローチャートは図１に示す第一の実施例と同様である。以上の説明により、前述の第一の実施例と同様の作用、効果が得られる。
【００８０】
（第４の実施例）
図５のフローチャートで示す通り、図３のステップＳ３０１の記事のグループ化に関する処理において、第１の実施例では、ステップＳ５０４の閾値αを一定値にしていたが、図１９のステップＳ１９０１に示す様に画像の幅や高さまたは面積に応じて変化させてもかまわない。例えば、画像の面積が大きな場合は閾値は小さめにするが、画像が小さくなるに従って閾値を大きくしていく等である。これによって、実際の長さは小さいが画像も小さかったことによって、分離しなくてもよいところを分離してしまうようなミスを少なくし、順序付けの精度を上げることができる。同様に式（２）〜（４）で使われている閾値も画像の大きさや階層等によって変化させてもよい。
【００８１】
本実施例の順序付け方法を表すフローチャートは図１に示す第一の実施例と同様である。以上の説明により、前述の第一の実施例と同様の作用、効果が得られる。
【００８２】
（第５の実施例）
図５のフローチャートで示す通り、図３のステップＳ３０１の記事のグループ化に関する処理において、第１の実施例では、画像の幅や高さまたは面積に対してある割合以上のセパレータや図等に関して領域を分離して記事を抽出していたが、短いセパレータや図であっても、セパレータまたは図と見出しの組み合わせによって領域を分離してもかまわない。
【００８３】
図２１のステップＳ２１０１がその処理である。図２２はステップＳ２１０１を詳細に示すフローチャートである。図２０は、第５の実施例説明のための図で、２００１は、画像全体である。２００２、２００３は、記事である。２００４は、セパレータである。２００５は、文字領域特に見出し領域である。
【００８４】
図２２、図２０に従って説明する。ステップＳ２２０１で、一つのセパレータまたは図を取り出す。ステップＳ２２０２で、画像全体の組方向が横書きか判定する。組方向判定の仕方は、第１の実施例で述べた通りである。横書きであれば、ステップＳ２２０３に進む。縦書きであれば、ステップＳ２２０４に進む。図２０の例では、横書きであるので、ステップＳ２２０３に進む、ステップＳ２２０３では、セパレータまたは図のすぐ下に見出しがあるか判定する。見出しがあれば、ステップＳ２２０５に進む。なければステップＳ２２０６に進む。図２０の例では、セパレータ２００４の下に見出し２００５が存在するので、ステップ２２０５に進む。また、同様にステップＳ２２０４では、セパレータまたは図のすぐ左に見出しがあるか判定する。見出しがあれば、ステップＳ２２０５に進む。なければステップＳ２２０６に進む。ステップＳ２２０５では、取り出したセパレータ、図により領域を二分する。図２０の例では、セパレータ２００４によって領域を二分し、記事２００２と記事２００３を生成した。ステップＳ２２０６では、全てのセパレータ、図に関して処理したか判定する。全て処理していれば、ステップＳ２１０１を終了する。残っていれば、ステップ２２０１に戻って処理を続ける。この処理によって、短いセパレータ等でも精度高く順序付けを行うことができる。
【００８５】
本実施例の順序付け方法を表すフローチャートは図１に示す第一の実施例と同様である。以上の説明により、前述の第一の実施例と同様の作用、効果が得られる。
【００８６】
（第６の実施例）
第１の実施例では、ステップＳ７０４で領域間にセパレータや図があるか調べる時に、平行四辺形を形作って、その中にセパレータや図が入るか調べたが、例えば縦方向に並んだ領域間を調べる場合に、上の領域の下底と、下の領域の上底を全部または一部含むような長方形を形作って、その中にセパレータや図が入るか調べてもよい。同様に横方向に並んだ領域間を調べる場合には、右の領域の左辺と、左の領域の右辺を全部または一部含むような長方形を形作って、その中にセパレータや図が入るか調べてもよい。図２３は、縦方向に並んだ領域間を調べる場合に、上の領域の下底と、下の領域の上底を全部含むような長方形を形作った例である。図２３において、２３０１は、上の領域である。２３０２は、下の領域である。２３０３は、上の領域の下底と、下の領域の上底を全部含むような長方形である。
【００８７】
同様に図２４は、縦方向に並んだ領域間を調べる場合に、上の領域の下底と、下の領域の上底を一部含むような長方形を形作った例である。図２４において、２３０１は、上の領域である。２３０２は、下の領域である。２４０１は、上の領域の下底と、下の領域の上底を一部含むような長方形である。
【００８８】
【発明の効果】
以上説明したように、本実施例によれば、新聞記事等、原稿の中に複数の記事が存在する場合でも、正しく読み順をつけることができ、修正等の手間を削減できる効果がある。
【図面の簡単な説明】
【図１】本実施例の順序付け方法を表すフローチャート。
【図２】画像を６階層にグループ分けしたところを示した図。
【図３】ステップＳ１０３についての詳細なフローチャート。
【図４】領域分割によって抽出された各領域を表す図。
【図５】ステップＳ３０１についての詳細なフローチャート。
【図６】ステップＳ３０４についての詳細なフローチャート。
【図７】ステップＳ３０２についての詳細なフローチャート。
【図８】図４の画像を６階層にグループ分けしたところを示した図。
【図９】ステップＳ１０４についての詳細なフローチャート。
【図１０】ステップＳ９０１についての詳細なフローチャート。
【図１１】ステップＳ９０２についての詳細なフローチャート。
【図１２】ステップＳ９０３についての詳細なフローチャート。
【図１３】ステップＳ９０４についての詳細なフローチャート。
【図１４】ステップＳ９０５についての詳細なフローチャート。
【図１５】ステップＳ３０５についての詳細なフローチャート。
【図１６】図４の画像から抽出された文字領域４２６を表す図。
【図１７】ステップＳ９０６についての詳細なフローチャート。
【図１８】図４の画像を３階層にグループ分けしたところを示した図。
【図１９】ステップＳ３０１についての詳細なフローチャート。
【図２０】領域分割によって抽出された文字領域、セパレータ領域、グループ化によってできた記事を示す図。
【図２１】ステップＳ３０１の詳細なフローチャート。
【図２２】ステップＳ３０１を詳細に示すフローチャート。
【図２３】上下領域を含む長方形の例示図１。
【図２４】上下領域を含む長方形の例示図２。
【図２５】実施例における装置の構成ブロック図。
【図１】
0003683923.tif 000002
【図２】
0003683923.tif 000003
【図３】
0003683923.tif 000004
【図４】
0003683923.tif 000005
【図５】
0003683923.tif 000006
【図６】
0003683923.tif 000007
【図７】
0003683923.tif 000008
【図８】
0003683923.tif 000009
【図９】
0003683923.tif 000010
【図１０】
0003683923.tif 000011
【図１１】
0003683923.tif 000012
【図１２】
0003683923.tif 000013
【図１３】
0003683923.tif 000014
【図１４】
0003683923.tif 000015
【図１５】
0003683923.tif 000016
【図１６】
0003683923.tif 000017
【図１７】
0003683923.tif 000018
【図１８】
0003683923.tif 000019
【図１９】
0003683923.tif 000020
【図２０】
0003683923.tif 000021
【図２１】
0003683923.tif 000022
【図２２】
0003683923.tif 000023
【図２３】
0003683923.tif 000024
【図２４】
0003683923.tif 000025
【図２５】
0003683923.tif 000026