(57)【特許請求の範囲】
【請求項１】
文書画像中のテキストブロックの行分割を実行する方法であって、
前記テキストブロックを分割して少なくとも１つの画素領域を含む第１の画素領域を取得する第１の分割ステップと、
前記第１の画素領域の各画素領域中の各々の画素行におけるすべての連続白画素シーケンスをその長さに従って順序付けするステップと、
最長の連続白画素シーケンスから開始して、次に続く連続白画素シーケンスの各々を順次重ね合わせることにより、所定の数の前記連続白画素シーケンスが共通して占める空白部分により判定される共通重複部分を空白領域として検出し、前記第１の画素領域の前記画素領域から前記空白領域を除去して第２の画素領域を取得する空白領域除去ステップと、
前記第１の画素領域の各画素領域の各画素行に関して、前記第２の画素領域中の画素行の黒画素カウントと前記第２の画素領域の幅との比を利用することにより、その画素行が文字画素行であるか又はスペース画素行であるかを検出するステップと、
前記第２の画素領域中の１つ以上の検出済みスペース画素行の前の隣接する１つ以上の隣接文字画素行を利用することにより、前記１つ以上の検出済みスペース画素行から１つ以上の最終スペース画素行を判定するステップと、
前記判定された１つ以上の最終スペース画素行に基づいてテキスト行分割を実行するテキスト行分割ステップと、
を有することを特徴とする方法。
【請求項２】
前記テキスト行分割ステップは、
前記第１の画素領域の各画素領域の各画素行に関して、その画素行の連続白画素シーケンス長さ統計値と前記第２の画素領域の幅との比を利用することにより、その画素行が文字画素行であるか又はスペース画素行であるかを検出するステップを更に有し、
前記連続白画素シーケンス長さ統計値は、前記第２の画素領域中の画素行の最長の連続白画素シーケンスの長さであるか、あるいは前記第２の画素領域の画素行の前記最長の連続白画素シーケンスの長さと２番目に長い連続白画素シーケンスの長さとの和であることを特徴とする請求項１に記載の方法。
【請求項３】
前記テキスト行分割ステップは、
検出されるべき画素行の前の隣接するすべての検出済み文字画素行を１つの文字行領域にマージするステップと、
前記文字行領域における文字ストローク幅を推定するステップと、
前記検出されるべき画素行をいくつかの小部分に分割し、前記いくつかの小部分の中から最大の黒画素カウントを有する小部分を検索するステップと、
前記最大黒画素カウントと前記文字ストローク幅とを比較することにより、前記検出されるべき画素行がスペース画素行であるか否かを検出するステップと、
を更に有することを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記文字ストローク幅を推定するステップは、
前記文字行領域の高さの１０分の１を前記文字ストローク幅の第１の推定値として取得するステップと、
次式を使用することにより前記文字ストローク幅の第２の推定値を取得するステップと、
式： 第２の推定値＝文字行領域中の黒画素カウント／（文字行領域の幅×平均ストローク量）
前記第１の推定値と前記第２の推定値のうち小さいほうの値を前記文字ストローク幅として使用するステップと、
を更に有し、前記平均ストローク幅は、前記文書中で使用される言語によって異なる値であることを特徴とする請求項３に記載の方法。
【請求項５】
前記判定するステップは、
前記１つ以上の隣接文字画素行を第２の文字行領域としてマージするステップと、
前記第２の文字行領域から第３の文字行領域を取得し且つ前記第３の文字行領域を利用することにより、前記１つ以上の検出済みスペース画素行の各スペース画素行が第２のスペース画素行であるか否かを判定する第１の判定ステップと、
前記第１の判定ステップで判定された前記第２のスペース画素行が前記最終スペース画素行であるか否かを判定する第２の判定ステップと、
を有することを特徴とする請求項４記載の方法。
【請求項６】
前記第２の文字行領域から第３の文字行領域を取得するステップは、
前記第２の文字行領域中の空白領域を検出し且つ前記第２の文字行領域から前記空白領域を除去して前記第３の文字行領域を取得するステップを有することを特徴とする請求項５記載の方法。
【請求項７】
前記第１の判定ステップは、
前記第３の文字行領域に対応する部分における前記スペース画素行中の黒画素カウントと前記第３の文字行領域の幅との比を利用することにより、前記スペース画素行が第２のスペース画素行であるか否かを判定するステップとを更に有することを特徴とする請求項６に記載の方法。
【請求項８】
前記第１の判定ステップは、
前記スペース画素行における連続白画素シーケンス長さ統計値と前記第３の文字行領域の幅との比を利用することにより、前記スペース画素行が第２のスペース画素行であるか否かを判定するステップとを更に有し、
前記連続白画素シーケンス長さ統計値は、前記第３の文字行領域に対応する部分における前記スペース画素行の最長の連続白画素シーケンスの長さ、あるいは前記第３の文字行領域に対応する部分における最長の連続白画素シーケンスと２番目に長い連続白画素シーケンスの長さとの和であることを特徴とする請求項６又は７に記載の方法。
【請求項９】
前記第２の判定ステップは、
前記第３の文字行領域をいくつかの部分領域に分割し且つそれに対応して前記第２のスペース画素行をいくつかの小部分に分割するステップと、
前記第２のスペース画素行の前記いくつかの小部分の中から最大の黒画素カウントを有する小部分を選択するステップと、
前記最大の黒画素カウントと前記小部分に対応する前記第３の文字行領域の部分領域から取得された上限とを比較することにより、前記第２のスペース画素行が最終スペース画素行であるか否かを判定するステップとを有し、
前記最大の黒画素カウントが前記上限より小さい場合、第２のスペース画素行は最終スペース画素行として判定されることを特徴とする請求項５に記載の方法。
【請求項１０】
前記上限は、次式によって計算される、
上限＝部分領域の文字量×平均ストローク量×文字ストローク幅
ここで、式中、部分領域の文字量は、部分領域の幅と部分領域の高さとの比を表し、
平均ストローク量は、文書中で使用される言語に基づく所定の値であり、
文字ストローク幅は、前記第３の文字行領域の幅の１０分の１である
ことを特徴とする請求項９に記載の方法。
【請求項１１】
前記所定の数は、前記画素領域中の画素行の数の少なくとも７０％であることを特徴とする請求項１に記載の方法。
【請求項１２】
前記第１の分割ステップは、画像に基づく分割方法を利用することにより実行されることを特徴とする請求項１に記載の方法。
【請求項１３】
文書画像中のテキストブロックの行分割を実行するシステムであって、
前記テキストブロックを分割して少なくとも１つの画素領域を含む第１の画素領域を取得する第１の分割ユニットと、
前記第１の画素領域の各画素領域中の各々の画素行におけるすべての連続白画素シーケンスをその長さに従って順序付けするユニットと、
最長の連続白画素シーケンスから開始して、次に続く連続白画素シーケンスの各々を順次重ね合わせることにより、所定の数の前記連続白画素シーケンスが共通して占める空白部分により判定される共通重複部分を空白領域として検出し、前記第１の画素領域の前記画素領域から前記空白領域を除去して第２の画素領域を取得する空白領域除去ユニットと、
前記第１の画素領域の各画素領域の各画素行に関して、前記第２の画素領域中の画素行の黒画素カウントと前記第２の画素領域の幅との比を利用することにより、その画素行が文字画素行であるか又はスペース画素行であるかを検出するユニットと、
前記第２の画素領域中の１つ以上の検出済みスペース画素行の前の隣接する１つ以上の隣接文字画素行を利用することにより、前記１つ以上の検出済みスペース画素行から１つ以上の最終スペース画素行を判定するユニットと、
前記判定された１つ以上の最終スペース画素行に基づいてテキスト行分割を実行するテキスト行分割ユニットと、
を有することを特徴とするシステム。
【請求項１４】
前記テキスト行分割ユニットは、
前記第１の画素領域の各画素領域の各画素行に関して、その画素行の連続白画素シーケンス長さ統計値と前記第２の画素領域の幅との比を利用することにより、その画素行が文字画素行であるか又はスペース画素行であるかを検出するように構成された白画素シーケンス検出ユニットを更に有し、
前記連続白画素シーケンス長さ統計値は、前記第２の画素領域中の画素行の最長の連続白画素シーケンスの長さ、あるいは前記第２の画素領域中の画素行の最長の連続白画素シーケンスの長さと２番目に長い連続白画素シーケンスの長さとの和であることを特徴とする請求項１３に記載のシステム。
【請求項１５】
前記テキスト行分割ユニットは、先に検出されていた文字画素行に関連する文字ストローク幅を利用することにより、画素行がスペース画素行であるか否かを検出するように構成された文字ストローク幅検出ユニットを更に有し、当該文字ストローク幅検出ユニットは、
検出されるべき画素行の前の隣接するすべての検出済み文字画素行を１つの文字行領域としてマージするように構成されたマージユニットと、
前記文字行領域における文字ストローク幅を推定するように構成された推定ユニットと、
前記検出されるべき画素行をいくつかの小部分に分割し且つ前記いくつかの小部分の中から最大の黒画素カウントを有する小部分を検索するように構成された検索ユニットと、
前記最大黒画素カウントと前記文字ストローク幅とを比較することにより、前記検出されるべき画素行がスペース画素行であるか否かを検出するように構成された比較ユニットと、
を有することを特徴とする請求項１３又は１４に記載のシステム。
【請求項１６】
前記推定ユニットは、
前記文字行領域の高さの１０分の１を前記文字ストローク幅の第１の推定値として取得し、
次式を使用することにより前記文字ストローク幅の第２の推定値を取得し、
式：第２の推定値＝文字行領域中の黒画素カウント／（文字行領域の幅×平均ストローク量）
前記第１の推定値及び前記第２の推定値のうち小さいほうの値を前記文字ストローク幅として使用することにより、
前記文字ストローク幅を推定し、
前記平均ストローク量は、前記文書中で使用される言語によって異なる値であることを特徴とする請求項１５に記載のシステム。
【請求項１７】
前記判定ユニットは、
前記１つ以上の隣接文字画素行を第２の文字行領域としてマージするように構成されたマージユニットと、
前記第２の文字行領域から第３の文字行領域を取得し且つ前記第３の文字行領域を利用することにより、前記１つ以上の検出済みスペース画素行の各スペース画素行が第２のスペース画素行であるか否かを判定するように構成された第１の判定ユニットと、
前記第１の判定ステップで判定された前記第２のスペース画素行が前記最終スペース画素行であるか否かを判定するように構成された第２の判定ユニットと、
を有することを特徴とする請求項１３に記載のシステム。
【請求項１８】
前記第１の判定ユニットは、前記第２の文字行領域中の空白領域を検出し且つ前記第２の文字行領域から前記空白領域を除去して前記第３の文字行領域を取得するように構成された文字行領域取得ユニットを有することを特徴とする請求項１７に記載のシステム。
【請求項１９】
前記第１の判定ユニットは、
前記第３の文字行領域に対応する部分における前記スペース画素行中の黒画素カウントと前記第３の文字行領域の幅との比を利用することにより、前記スペース画素行が第２のスペース画素行であるか否かを判定するように構成された黒画素カウント判定ユニット
を更に有することを特徴とする請求項１８に記載のシステム。
【請求項２０】
前記第１の判定ユニットは、
前記スペース画素行における連続白画素シーケンス長さ統計値と前記第３の文字行領域の幅との比を利用することにより、前記スペース画素行が第２のスペース画素行であるか否かを判定するように構成された白画素シーケンス判定ユニットを更に有し、
前記連続白画素シーケンス長さ統計値は、前記第３の文字行領域に対応する部分におけるスペース画素行の最長の連続白画素シーケンスの長さ、あるいは前記第３の文字行領域に対応する部分におけるスペース画素行の最長の連続白画素シーケンスの長さと２番目に長い連続白画素シーケンスの長さとの和であることを特徴とする請求項１８又は１９に記載のシステム。
【請求項２１】
前記第２の判定ユニットは、
前記第３の文字行領域をいくつかの部分領域に分割し且つそれに対応して前記第２のスペース画素行をいくつかの小部分に分割するように構成された分割ユニットと、
前記第２のスペース画素行の前記いくつかの小部分の中から最大の黒画素カウントを有する小部分を選択するように構成された選択ユニットと、
前記小部分に対応する前記第３の文字行領域中の部分領域から上限を計算するように構成された上限計算ユニットと、
前記最大の黒画素カウントと前記上限とを比較することにより、前記第２のスペース画素行が最終スペース画素行であるか否かを判定するように構成された比較ユニットとを有し、
前記最大の黒画素カウントが前記上限より小さい場合、第２のスペース画素行は最終スペース画素行として判定されることを特徴とする請求項１７に記載のシステム。
【請求項２２】
前記上限計算ユニットは、次式に従って前記上限を計算する、
上限＝部分領域中の文字量×平均ストローク量×文字ストローク幅
ここで、式中、部分領域中の文字量は、部分領域の幅と部分領域の高さとの比を表し、
平均ストローク量は、前記文書中で使用される言語に基づく所定の値であり、
文字ストローク幅は、前記第３の文字行領域の幅の１０分の１である
ことを特徴とする請求項２１に記載のシステム。
【請求項２３】
前記所定の数は、前記画素領域中の前記画素行の数の少なくとも７０％であることを特徴とする請求項１３に記載のシステム。
【請求項２４】
前記第１の分割ユニットは、画像に基づく分割方法を利用することにより分割することを特徴とする請求項１３に記載のシステム。
【請求項２５】
請求項１３乃至２４のいずれか１項に記載のシステムの各ユニットとしてコンピュータを機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書画像の行分割方法及び行分割システムに関し、特に、複雑なレイアウトを有する文書画像又はノイズが含まれる文書画像の行分割方法及び行分割システムに関する。
【背景技術】
【０００２】
光学式文字認識（ＯＣＲ）の分野には、元の文書から得られた文書画像に含まれるテキストコンテンツを取得するために文書画像を認識する技術が複数存在する。それら複数の技術のうち１つの技術は、文書画像中のテキストブロックをテキスト行に分割する方法であり、以下の説明中、この方法は行分割方法と呼ばれる。
【０００３】
文書画像の行分割技術の１つは、画像に基づく技術、特に画素投影に基づく技術であり、この種の一般的な方法は、各画素行の黒画素投影のみによって行分割を実行する。更に詳細には、図１に示されるように、主に方法は、文書画像の１つのテキストブロックに含まれる各画素行の黒画素投影値を計算することと、すべてのスペース画素行をその黒画素投影値に従って検出することと、スペース画素行に沿ってテキストブロックを分割することにより行分割結果を取得することとから成る。
【０００４】
１つの画素行の黒画素投影値は複数の形態をとるが、一般的な形態の１つは、１つの画素行の黒画素カウントとその画素行の面積との比である。画素行の面積は、画素行の幅を画素行の高さと乗算することにより計算される。更に詳細には、１つの画素行の高さは常に１であるので、１つの画素行の黒画素投影値は、その画素行における黒画素カウントとその画素行の幅との比である。この技術において、１つの画素行の黒画素カウントとその画素行の面積との比が、通常は０であるか又は０に近い閾値より小さい場合、その画素行は、文字に関連するコンテンツを含まない画素行であると通常は考えられるスペース画素行とみなされ、テキストブロックの行分割に使用されるだろう。
【０００５】
しかし、特に文書画像中にノイズが存在する場合又は文書画像が複雑なレイアウトを有する場合、この方法では、適切な行分割結果は通常得られない。
【０００６】
このような行分割の問題に対処するための方法はいくつか提案されているが、それらの方法は、ノイズを含む文書画像又は複雑なレイアウトの画像のいずれか一方のみを処理することを意図している。
【０００７】
１つの方法は、行分割に先立ってノイズを削除する。方法は、ノイズを含む文書画像を対象とするが、長い時間を必要とし、「点ノイズ」のようなものを処理可能なだけである。特に、この方法は、複雑なレイアウトの文書画像の行分割の問題を解決できない。
【０００８】
もう１つの方法は、画素行における連続白画素シーケンスの長さである白画素連続長に基づく。この方法では、各画素行の白画素連続長が計算され、長い白画素連続長を有する画素行は、行分割可能な位置、すなわちスペース画素行とみなされる。この方法は、レイアウトがそれほど複雑ではない文書画像にはある程度は有用であり、場合によっては、２つのテキスト行の間のノイズ画素行の一部をこの方法により検出可能であるので、特定のノイズを含む文書画像にも有用である。しかし、この方法は次のような３つの欠点を有する。
【０００９】
第１に、テキスト行が短い場合、特にタイトル行のように隣接する文字の間に広いスペースがある場合、テキスト行中の画素行は長い白画素連続長を有するので、図２Ａに示されるように、テキスト行はいくつかのテキスト行に誤って分割されてしまう。
【００１０】
第２に、投影に基づく方法では分離できない２つのテキスト行を分割するために上記の方法が適用される場合、それら２つのテキスト行のうち一方の行が短く他方が長いと、短いテキスト行の中の画素行では、空白領域は画素行の白画素連続長さの一部とみなされ、いくつかの文字画素行は、誤ってスペース画素行とみなされる。そのため、図２Ｂに示されるように、ノイズ画素行である確率が最も高い画素行に沿ってテキスト行を分割すると、短いテキスト行は誤っていくつかのテキスト行に分割されることになる。
【００１１】
あるいは、図２Ｃに示されるように、すべてのノイズ画素行を直接削除することによりテキスト行を分割する場合、短いテキスト行はテキスト行の間のスペース領域の一部とみなされることもある。
【００１２】
第３に、ノイズを含む文書画像では、画素行中のノイズが点在していない場合に限り、上記の方法によってノイズ画素行を発見できる。文書画像中にノイズが点在している場合にはノイズ画素行を発見できず、図２Ｄに示されるように、上記の方法によりテキスト行を分離することは不可能である。
【００１３】
更に図２Ｅに示されるように、従来の技術では、複雑なレイアウトを有するのに加えてノイズが存在し、点在している文書画像を正確に分割できない。
【００１４】
以上のことから、複雑なレイアウトを有する文書画像又はノイズが存在し、点在している文書画像に効率よく且つ正確に対処できる方法がないことは明らかである。
【００１５】
更に、複雑なレイアウトを有するのに加えてノイズが存在し、点在している文書画像に効果的且つ正確に対処できる方法もない。
【００１６】
従って、上述の従来技術における技術的な問題点を考慮して、従来技術によって発生する欠陥を克服し、行分割により文書画像から正確にテキスト行を取得する技術が必要とされる。
【発明の概要】
【発明が解決しようとする課題】
【００１７】
本発明の１つの目的は、複雑なレイアウトの文書画像の行分割を正確に実現することである。
【００１８】
本発明の別の目的は、ノイズを含む文書画像、特にノイズが点在している文書画像の行分割を正確に実現することである。
【００１９】
本発明の更なる目的は、複雑なレイアウトを有するのに加えてノイズが存在し、点在している文書画像の行分割を正確に実現することである。
【課題を解決するための手段】
【００２０】
本発明の１つの態様では、文書画像中のテキストブロックの行分割を実行する方法であって、
前記テキストブロックを分割して少なくとも１つの画素領域を含む第１の画素領域を取得する第１の分割ステップと、
前記第１の画素領域の各画素領域中の各々の画素行におけるすべての連続白画素シーケンスをその長さに従って順序付けするステップと、
最長の連続白画素シーケンスから開始して、次に続く連続白画素シーケンスの各々を順次重ね合わせることにより、所定の数の前記連続白画素シーケンスが共通して占める空白部分により判定される共通重複部分を空白領域として検出し、前記第１の画素領域の前記画素領域から前記空白領域を除去して第２の画素領域を取得する空白領域除去ステップと、
前記第１の画素領域の各画素領域の各画素行に関して、前記第２の画素領域中の画素行の黒画素カウントと前記第２の画素領域の幅との比を利用することにより、その画素行が文字画素行であるか又はスペース画素行であるかを検出するステップと、
前記第２の画素領域中の１つ以上の検出済みスペース画素行の前の隣接する１つ以上の隣接文字画素行を利用することにより、前記１つ以上の検出済みスペース画素行から１つ以上の最終スペース画素行を判定するステップと、
前記判定された１つ以上の最終スペース画素行に基づいてテキスト行分割を実行するテキスト行分割ステップとを有する方法が提供される。
【００２１】
本発明の別の態様では、文書画像中のテキストブロックの行分割を実行するシステムであって、
前記テキストブロックを分割して少なくとも１つの画素領域を含む第１の画素領域を取得する第１の分割ユニットと、
前記第１の画素領域の各画素領域中の各々の画素行におけるすべての連続白画素シーケンスをその長さに従って順序付けするユニットと、
最長の連続白画素シーケンスから開始して、次に続く連続白画素シーケンスの各々を順次重ね合わせることにより、所定の数の前記連続白画素シーケンスが共通して占める空白部分により判定される共通重複部分を空白領域として検出し、前記第１の画素領域の前記画素領域から前記空白領域を除去して第２の画素領域を取得する空白領域除去ユニットと、
前記第１の画素領域の各画素領域の各画素行に関して、前記第２の画素領域中の画素行の黒画素カウントと前記第２の画素領域の幅との比を利用することにより、その画素行が文字画素行であるか又はスペース画素行であるかを検出するユニットと、
前記第２の画素領域中の１つ以上の検出済みスペース画素行の前の隣接する１つ以上の隣接文字画素行を利用することにより、前記１つ以上の検出済みスペース画素行から１つ以上の最終スペース画素行を判定するユニットと、
前記判定された１つ以上の最終スペース画素行に基づいてテキスト行分割を実行するテキスト行分割ユニットとを有するシステムが提供される。
【００２２】
本発明の更なる特徴と利点は、添付の図面を参照して以下の説明を読むことにより明らかになるだろう。
【００２３】
本明細書に組み込まれ且つ本明細書の一部を構成する添付の図面は、本発明の実施形態を例示し、以下の説明と共に本発明の原理を説明する。
【図面の簡単な説明】
【００２４】
【図１】図１は、従来の技術における黒画素投影に基づく行分割の方法を概略的に示す図である。
【図２Ａ】、
【図２Ｂ】、
【図２Ｃ】、
【図２Ｄ】、
【図２Ｅ】図２Ａ〜図２Ｅは、従来の方法により正確に分割できない種々の文書画像を概略的に示す図であり、図２Ａ〜図２Ｃは、誤って分割された複雑なレイアウトを有する文書画像を概略的に示す図であり、図２Ｄは、ノイズが点在しているために分割できない文書画像を概略的に示す図であり、図２Ｅは、複雑なレイアウトを有し且つノイズが点在しているために正確に分割できない文書画像を概略的に示す図である。
【図３】図３は、画素行の幅及び高さの意味を概略的に説明する図である。
【図４】図４は、本発明に係る行分割システムを実現する計算デバイスの構成を示すブロック図である。
【図５】図５は、本発明に係る行分割方法の第１の実施形態を示すフローチャートである。
【図６】図６は、図５の方法により実現される画素領域の行分割の結果の一例を概略的に示す図である。
【図７】図７は、空白領域が含まれる画素領域を概略的に示す図である。
【図８】図８は、画素領域における空白領域の判定及び画素領域からの第２の画素領域の取得を示すフローチャートである。
【図９】図９は、画素領域中の各々の画素行における連続白画素シーケンス間の共通重複部分の一例を概略的に示す図である。
【図１０Ａ】、
【図１０Ｂ】図１０Ａ及び図１０Ｂは、画素領域における空白領域の検出の別の例を概略的に示す図である。
【図１１】図１１は、空白領域が検出され且つ除去されている場合の画素領域中の画素行のパラメータを概略的に示す図である。
【図１２Ａ】、
【図１２Ｂ】、
【図１２Ｃ】図１２Ａ〜図１２Ｃは、行分割方法の第１の実施形態のステップＳ３００において実行される例示的なステップを示すフローチャートである。
【図１３Ａ】、
【図１３Ｂ】図１３Ａ及び図１３Ｂは、従来の技術と本発明の第１の実施形態とによりそれぞれ実現された複雑なレイアウトを有する文書画像の行分割の結果の比較を概略的に示す図である。
【図１４】図１４は、本発明に係る行分割方法の第２の実施形態のステップＳ３００における処理を示すフローチャートである。
【図１５Ａ】、
【図１５Ｂ】、
【図１５Ｃ】図１５Ａ〜図１５Ｃは、従来の技術と本発明の第２の実施形態とによりそれぞれ実現されたノイズが存在し、点在している文書画像の行分割の結果の比較を概略的に示す図である。
【図１６Ａ】、
【図１６Ｂ】図１６Ａ及び図１６Ｂは、２つの隣接テキスト行が相当に異なる長さを有する２つの場合を概略的に示す図である。
【図１７】図１７は、本発明に係る行分割方法の第３の実施形態のテキスト行分割ステップにおける処理を示すフローチャートである。
【図１８】図１８は、第３の実施形態のテキスト行分割ステップの第１の判定ステップにおける処理を示すフローチャートである。
【図１９】図１９は、第３の文字行領域と判定されるべきスペース画素行との対応を概略的に示す図である。
【図２０】図２０は、第３の実施形態の行分割方法の第２の判定ステップにおける処理を示すフローチャートである。
【図２１Ａ】、
【図２１Ｂ】、
【図２１Ｃ】図２１Ａ〜図２１Ｃは、テキストブロック中の２つの隣接テキスト行が相当に異なる長さを有する文書画像に関して、従来の技術の方法と第３の実施形態の方法とによりそれぞれ実現された行分割の結果の比較を概略的に示す図である。
【図２２Ａ】、
【図２２Ｂ】、
【図２２Ｃ】、
【図２２Ｄ】、
【図２２Ｅ】図２２Ａ〜図２２Ｅは、複雑なレイアウトを有し且つノイズが存在し、点在している文書画像の行分割の一例を概略的に示す図である。
【図２３】図２３は、行分割システムの一般的な構成を示すブロック図である。
【発明を実施するための形態】
【００２５】
添付の図面を参照して、本発明の実施形態を以下に詳細に説明する。
【００２６】
本発明を完全に且つ適切に理解しやすくするために、まず、本明細書及び特許請求の範囲で使用される用語を説明する。
【００２７】
本明細書及び特許請求の範囲において、特に文書画像で使用される場合の用語「テキストブロック」は、文書画像中の１つ以上の行に１つ以上の語を含み且つ１つ以上の画素領域に分割できるブロックを表す。画素領域は、１つ以上のテキスト行から構成され且つ各テキスト行を取得するように分割可能である。テキスト行は、１行分のテキスト、更に詳細には１行分の語に対応し、１つ以上の画素行を含む。画素行は、画素領域中の語に関連する情報を含む文字画素行であるか、又は語に関連する情報を実質的には含まず且つ画素領域の行分割に際して分割位置としてみなすことができるスペース画素行である。１つ以上の文字画素行を１つの文字行領域としてマージできる。
【００２８】
画素行又はテキスト行の方向に関して、「水平」という用語はほぼ水平方向であることを意味し、「垂直」という用語はほぼ垂直方向であることを意味する。特に、文書画像で使用される場合の用語「水平」は、文書画像又は元の文書におけるテキスト行とほぼ平行な方向であることを表す。同様に、文書画像で使用される場合の用語「垂直」は、文書画像又は元の文書におけるテキスト行に対してほぼ垂直な方向であることを表す。
【００２９】
本明細書及び特許請求の範囲において、通常は水平方向の行である文書画像中のテキスト行に関して、「高さ」（Ｈで示される）及び「幅」（Ｗで示される）という用語は、それぞれ、垂直方向のテキスト行の長さ及び水平方向のテキスト行の長さを示す。
【００３０】
テキスト行が水平方向の行に限定されず、垂直方向の行（テキスト列とも呼ばれる）であってもよいことは言うまでもない。この場合、「水平」という用語は、文書画像又は元の文書におけるテキスト列に対してほぼ垂直な方向であることを意味し、「垂直」という用語は、文書画像又は元の文書におけるテキスト列とほぼ平行な方向であることを意味し、「高さ」（Ｈで示される）という用語は、水平方向のテキスト列の長さを示し、「幅」（Ｗで示される）という用語は、垂直方向のテキスト列の長さを示す。
【００３１】
図３は、上記の２つの場合を概略的に示す。テキストブロック及び画素領域は１つ以上のテキスト行を含み且つ１つのテキスト行は１つ以上の画素行から構成されるので、「高さ」及び「幅」の意味は、テキストブロック、画素領域及びその部分領域、並びに画素行及びその小部分のいずれの「高さ」及び「幅」にも同等に適用される。この点を考慮して、テキストブロック又は画素領域の分割（すなわち、行分割）は、その高さ方向に実行されるといえるだろう。
【００３２】
以下の説明を簡単にするために、特に指示のない限り、「高さ」は垂直方向の長さを意味し、「幅」は水平方向の長さを意味し、分割は垂直方向の分割を意味する。
【００３３】
本明細書において、特に指示のない限り、すべての大きさ（長さ又は幅など）は「画素」の単位で表される。
【００３４】
図４は、本発明に係る行分割システムを実現する計算デバイスの構成を示すブロック図である。簡潔にするため、システムは、１つの計算デバイスに組み込まれるものとして示される。しかし、システムが１つの計算デバイスに組み込まれるか又はネットワークシステムとして複数の計算デバイスに配置されるかにかかわらず、システムは有効である。
【００３５】
図４に示されるように、計算デバイス１００は、行分割の処理を実現するために使用される。計算デバイス１００は、ＣＰＵ１０１と、チップセット１０２と、ＲＡＭ１０３と、ストレージコントローラ１０４と、ディスプレイコントローラ１０５と、ハードディスクドライブ１０６と、ＣＤ−ＲＯＭドライブ１０７と、ディスプレイ１０８とを備える。計算デバイス１００は、ＣＰＵ１０１とチップセット１０２との間に接続された信号線１１１、チップセット１０２とＲＡＭ１０３との間に接続された信号線１１２、チップセット１０２と種々の周辺装置との間に接続された周辺装置バス１１３、ストレージコントローラ１０４とハードディスクドライブ１０６との間に接続された信号線１１４、ストレージコントローラ１０４とＣＤ−ＲＯＭドライブ１０７との間に接続された信号線１１５、並びにディスプレイコントローラ１０５とディスプレイ１０８との間に接続された信号線１１６を更に備える。
【００３６】
クライアント１２０は、計算デバイス１００に直接接続されるか又はネットワーク１３０を介して接続される。クライアント１２０は、例えば行分割の処理により要求される命令及び／又はパラメータを計算デバイス１００へ送出し、計算デバイス１００は、クライアント１２０へ情報を返送するか又はディスプレイ１０８に情報を表示する。
【００３７】
［第１の実施形態］
図５を参照して、本発明に係る行分割方法の第１の実施形態を以下に説明する。図５は、行分割方法の第１の実施形態を示すフローチャートである。
【００３８】
行分割方法のステップＳ１００（以下、第１の分割ステップと呼ばれる）において、少なくとも１つの画素領域を含む粗い画素領域（以下、第１の画素領域と呼ばれる）を取得するために、文書画像のテキストブロックが分割される。ステップＳ１００の処理中、先に説明した投影に基づく方法などの従来の何らかの種類の行分割方法を使用可能であるので、ここでは説明を省略する。
【００３９】
ステップＳ２００（以下、空白領域除去ステップと呼ばれる）において、第１の画素領域の各画素領域中の各画素行における連続白画素シーケンス間の共通重複部分が第１の画素領域の対応する画素領域における空白領域として検出され且つ空白領域が除去された画素領域（以下、第２の画素領域と呼ばれる）を取得するために第１の画素領域の対応する画素領域から空白領域が除去される。通常、第１の画素領域の各画素領域は、１つの第２の画素領域に対応する。ステップＳ２００の処理については以下に詳細に説明する。
【００４０】
ステップＳ３００（以下、テキスト行分割ステップと呼ばれる）において、テキスト行分割に第２の画素領域が使用される。例えば、第１の画素領域中の各画素領域に関して、対応する第２の画素領域を利用することにより、その画素領域における行分割位置が判定され、その後、行分割結果を取得するために、画素領域は行分割位置に従って分割される。従来の技術では周知のように、通常、行分割位置は１つ以上のスペース画素行に対応する。
【００４１】
図６は、図５に示される方法により実現されたテキストブロック中の１つの画素領域の行分割結果の一例を概略的に示す。図６に示されるように、第１の画素領域に含まれる各画素領域は、１つ以上のスペース画素行に従って少なくとも２つの部分に分割可能である。詳細には、例えば画素領域中に２つ以上の一連の隣接するスペース画素行が存在する場合、それらのスペース画素行は１つのスペース画素行領域にマージされ、そのスペース行領域を削除することにより、スペース画素行は、画素領域を少なくとも２つのより小さな画素領域（テキスト行領域とも呼ばれる）に分割するために使用されるだろう。
【００４２】
場合によっては、行分割結果として取得された画素領域（すなわち、テキスト行領域）を更に分割しなければならないこともある。例えば、文書画像の状態と個人的な経験とに従って設定される１つの閾値ＴＨ１、例えば３００ｄｐｉ画像の場合に３４である閾値をテキスト行領域の高さが超える場合、そのテキスト行領域を更に分割する必要がある。
【００４３】
行分割方法において、行分割されるべき画素領域の幅などの多くの種類のパラメータを考慮し、正確に取得する必要がある。詳細には図７に示されるように、画素領域がいくつかの空白領域を含む場合、画素領域中の空白領域を検出し且つ削除しなければならない。特にテキスト行が短い場合、空白領域を削除しないと行分割誤差が発生する。
【００４４】
図８及び図９を参照して、ステップＳ２００の処理を以下に詳細に説明する。図８は、画素領域中の空白領域の判定及び画素領域からの第２の画素領域の取得とを示すフローチャートである。図９は、画素領域中の画素行の中の共通重複部分の一例を概略的に示す。
【００４５】
図８のステップＳ２０１において、画素領域中の各画素行におけるすべての連続白画素シーケンスがその長さに従って順序付けされる。
【００４６】
ステップＳ２０２において、画素領域中の各画素行における連続白画素シーケンス間の共通重複部分（空白領域に対応する）を生成するために、最長の連続白画素シーケンスから開始して、次に続く連続白画素シーケンスの各々が順次重ね合わされる。ステップＳ２０２の処理については以下に詳細に説明する。
【００４７】
ステップＳ２０３において、画素領域から空白領域が除去され、残った文字領域は第２の画素領域にグループ化される。
【００４８】
ステップＳ２０２の処理では、１つの共通空白部分を生成するために、共通して重ね合わされたシーケンスのカウント、すなわち、重ね合わされた画素行の数が所定の数に達するまで、第１の連続白画素シーケンス、すなわち１つの画素行の中で最長の連続白画素シーケンスから開始して、他の画素行の次に続く白画素シーケンスの各々が前の１つ以上の連続白画素シーケンスと順序通りに重ね合わされる。この所定の数は、所期の精度、画像の解像度などの多くの種類の条件に従って操作者により設定可能である。一般に、所定の数は、画素領域中の画素行の数の少なくとも７０％になるように設定される。
【００４９】
重ね合わせ処理中、重ね合わされるべき連続白画素シーケンスが前の連続白画素シーケンスを組み合わせることにより生成された空白領域と重なり合わない場合、重ね合わされるべき連続白画素シーケンスは放棄され、次の連続白画素シーケンスの重ね合わせが試みられる。
【００５０】
最後に、取得された共通空白部分の範囲に対応する画素領域の部分が、その画素領域の共通重複部分、すなわちその画素領域の空白領域とみなされる。空白領域は除去され、画素領域中に残った文字領域（第２の画素領域としてグループ化可能である）は、続く行分割の間に利用される。
【００５１】
あるいは、共通重複部分を検出する上記の方法は、空白領域を検出するために黒画素カウントにより空白領域を検出する別の方法と組み合わせ可能である。
【００５２】
更に詳細に説明すると、図１０Ａに示されるように、まず、画素領域はいくつかの部分領域に分割され、大きな空白領域を検出するために、各部分領域の黒画素カウントとその部分領域の面積との比が計算され、比が１つの閾値ＹＨ４（例えば、０．０１）より小さい場合、その部分領域は空白領域とみなされる。比が閾値ＴＨ４（例えば、０．０１）より大きい場合、その部分領域は文字部分領域である可能性が高い。以後、説明を簡単にするために、特に指示のない限り、分割は幅方向の分割を指す。
【００５３】
続いて、図１０Ｂに示されるように、文字部分領域に関して、文字部分領域中に出現しうる小さな空白部分領域を検出するために、上述の共通重複部分を検出する方法が使用される。
【００５４】
図１１及び図１２Ａ〜図１２Ｃを参照して、ステップＳ３００の処理を以下に詳細に説明する。図１１は、空白領域が既に検出され且つ除去されている場合の画素領域中の１つの画素行の黒画素カウント及び連続白画素シーケンスの長さなどのパラメータを概略的に示す。図１２Ａ〜図１２Ｃは、行分割方法の第１の実施形態のステップＳ３００において実行される例示的なステップを示すフローチャートである。
【００５５】
ステップＳ３００において、先に説明したように、行分割に第２の画素領域が使用されるだろう。更に詳細には、検出されるべき画素行が文字画素行であるか又はスペース画素行であるかを検出するために、第２の画素領域のパラメータ、並びに検出されるべき画素行の対応するパラメータを使用できる。
【００５６】
第２の画素領域のパラメータは、例えば第２の画素領域の幅を含む。この幅は、第２の画素領域中の文字領域の幅の和を計算することにより取得できる。
【００５７】
画素行の対応するパラメータは、例えば第２の画素領域中の画素行の黒画素カウント及び画素行の連続白画素シーケンス長さ統計値を含む。連続白画素シーケンス長さ統計値は、図１１に示されるように、第２の画素領域中の画素行の最長の連続白画素シーケンスの長さ又は第２の画素領域中の画素行の最長の連続白画素シーケンスの長さと２番目に長い連続白画素シーケンスの長さとの和である。
【００５８】
第２の画素領域のパラメータ及び検出されるべき画素行のパラメータを使用して、スペース画素行を検出するために、ステップＳ３００の処理を種々の方法で実行可能である。
【００５９】
図１２Ａは、第２の画素領域中の画素行における黒画素カウントと第２の画素領域の幅との比を利用することによりスペース画素行が検出されるステップＳ３００の処理を示す。
【００６０】
この処理の一般的な方法の１つは、画素行がスペース画素行であるか否かを検出するように、上記の比が閾値と比較されることである。比が閾値ＴＨ２、例えば０．０１より小さい場合、その画素行は１つのスペース画素行とみなされる。そうでない場合、画素行は１つの文字画素行とみなされる。
【００６１】
図１２Ｂは、画素行における連続白画素シーケンス長さ統計値と第２の画素領域の幅との比、すなわち第２の画素領域中の画素行の最長連続白画素シーケンスの長さと第２の画素領域の幅との比、あるいは第２の画素領域中の画素行の最長連続白画素シーケンスの長さ及び２番目に長い連続白画素シーケンスの長さの和と第２の画素領域の幅との比を利用することにより、スペース画素行が検出されるステップＳ３００の処理を示す。
【００６２】
この処理の一般的な方法の１つは、画素行がスペース画素行であるか否かを検出するように、それら２つの比を閾値と比較する。それら２つの比のいずれか一方が１つの閾値ＴＨ３（例えば０．７）より大きい場合、その画素行は１つのスペース画素行とみなされる。そうでない場合、画素行は１つの文字画素行とみなされる。
【００６３】
図１２Ｃは、図１２Ａに示される方法と図１２Ｂに示される方法とを組み合わせたステップＳ３００の処理を示す。例えば、図１２Ａに示される方法及び図１２Ｂに示される方法を順次実行することが可能である。尚、図１２Ｃの処理の順序は単なる例であり、他の順序も利用できる。例えば、図１２Ｂに示される処理の次に図１２Ａに示される処理が実行されてもよい。
【００６４】
上述の処理方法は、第２の画素領域を利用することによりスペース画素行の検出を実現する好適な処理方法の例であるが、他の方法も使用可能である。
【００６５】
スペース画素行の検出は、水平のレイアウトでは、第１の画素領域に含まれる画素領域のすべての画素行に関して上から下に向かって実行可能であるが、これに限定されない。例えば、検出精度をほとんど低下させずに計算速度を改善するために、１つの画素領域の中央にある画素行に関してスペース画素行の検出を実行可能であり、この中央部分の範囲は、操作者が任意に設定可能である。一般的な選択肢の１つは、画素領域が上限「ｒｅｇｉｏｎ＿ｔｏｐ」及び下限「ｒｅｇｉｏｎ＿ｂｏｔｔｏｍ」を有し、「ｍｉｄｄｌｅ」は「ｒｅｇｉｏｎ＿ｔｏｐ」＋０．２×ｓｔｄ＿ｌｉｎｅ＿ｈｅｉｇｈｔと「ｒｅｇｉｏｎ＿ｂｏｔｔｏｍ」−０．２×ｓｔｄ＿ｌｉｎｅ＿ｈｅｉｇｈｔとの間の領域であると仮定するものである。ｓｔｄ＿ｌｉｎｅ＿ｈｅｉｇｈｔは、文書画像の解像度により推定される。
【００６６】
１つの画素領域において、すべてのスペース画素行を一度に検出可能であるが、本発明はこれに限定されない。例えば、水平のレイアウトでは、上から下に向かって各画素行を走査し、検出することができる。１つのスペース画素行が発見された後、それに続く別の画素行が文字画素行であるか否かが判断され、処理は終了する。
【００６７】
［有利な効果］
第１の実施形態の方法は、少なくとも、複雑なレイアウトを有する文書画像、特にタイトル行を含む文書画像に有効且つ正確に適用可能であり、それによりそのような文書画像の行分割の性能を向上できる。
【００６８】
図１３Ａ及び図１３Ｂは、従来の技術と本発明の第１の実施形態とによりそれぞれ実現された複雑なレイアウトを有する文書画像の行分割の結果の比較を概略的に示す。文書画像は、例えば文書中のタイトル行である。図１３Ａに示されるように、従来の方法によりタイトル行は誤って分割されていることがわかる。これに対し本発明に係る第１の実施形態の方法によれば、図１３Ｂに示されるように、タイトル行ではスペース画素行は検出されず、従ってタイトル行は誤って分割されていないことがわかるだろう。
【００６９】
［第２の実施形態］
図１４〜図１５Ｃを参照して、本発明の第２の実施形態を詳細に説明する。第２の実施形態は、テキスト行分割ステップを除いて第１の実施形態とほぼ同一である。第２の実施形態のテキスト行分割ステップは、画素領域中の検出されるべき画素行の前の文字画素行を利用することにより、特に検出されるべき画素行の前の文字画素行から導出された文字ストローク幅を利用することにより、画素行がスペース画素行であるか否かを更に検出する。第１の実施形態のステップと同様である第２の実施形態のステップは省略し、詳細には説明しない。
【００７０】
このスペース画素行検出処理は、１つのテキスト行が３つ以上の文字を含む場合、テキスト行領域内の画素行ごとに、文字の少なくとも１つの文字ストロークがその画素行を通過するという１つの妥当な推論に基づく。文字ストローク幅は、多数の文字画素行から構成される領域内の語の少なくとも１つの文字ストロークの平均幅である。上記の推論及び定義は、画素行及び画素領域が共に水平方向である場合と画素行及び画素領域が共に垂直方向である場合との双方に適用可能である。水平方向である場合、文字ストロークは垂直文字ストロークになり、文字ストローク幅は垂直の文字ストロークの文字ストローク幅に対応する。垂直方向である場合、文字ストロークは水平文字ストロークになり、文字ストローク幅は水平の文字ストロークの文字ストローク幅に対応する。
【００７１】
第２の実施形態のスペース画素行検出処理と第１の実施形態のスペース画素行検出処理とを種々の方法で組み合わせることができる。一例において、第２の実施形態のテキスト行分割ステップを第１の実施形態の図１２Ａ〜図１２Ｃのいずれかに示される処理に続けて実行し、それらの処理を組み合わせてもよい。
【００７２】
図１４は、本発明に係る行分割方法の第２の実施形態におけるスペース画素行検出処理を示すフローチャートである。
【００７３】
ステップＳ４０１において、第２の画素領域が少なくとも２つの文字を含むか否かが検査される。一般的な検査方法の１つは、第２の画素領域の幅と高さとの比を計算する方法である。この比が２より大きい場合、第２の画素領域は少なくとも２つの文字を含むとみなされ、ステップＳ４０２へ進む。そうでない場合、処理は終了し、次の第２の画素領域を待つ。
【００７４】
ステップＳ４０２において、検出されるべき画素行の前の隣接するすべての検出済み文字画素行が１つの文字行領域にマージされる。
【００７５】
ステップＳ４０３において、この文字行領域の文字ストローク幅が推定される。ステップＳ４０３の処理については以下に詳細に説明する。
【００７６】
ステップＳ４０４において、検出されるべき画素行はいくつかの小部分に分割され、それらいくつかの小部分の中から最大の黒画素カウントを有する小部分が検索される。
【００７７】
ステップＳ４０５において、最大の黒画素カウントと文字ストローク幅とを比較することにより、検出されるべき画素行がスペース画素行であるか否かが検出される。例えば、最大の黒画素カウントが文字ストローク幅未満であるか否かを検査し、文字ストローク幅未満であれば、検出されるべき画素行は１つのスペース画素行である。文字ストローク幅未満ではない場合、少なくとも１つの文字ストロークが画素行を通過していると考えられるので、画素行は文字画素行になる。
【００７８】
これにより、第２の実施形態のスペース画素行検出方法によりスペース画素行を検出でき、その後、スペース画素行は画素領域の行分割に使用される。
【００７９】
次に、文字ストローク幅の推定方法を詳細に説明する。
【００８０】
文字ストローク幅は２つの方法により推定可能である。第１の方法は、マージ後の文字行領域の高さと文字ストローク幅との関係に基づき、文字ストローク幅の第１の推定値を取得する。第２の方法は、隣接するマージ済み文字行領域における黒画素分布を解析することにより文字ストローク幅を動的に取得するために使用され、文字ストローク幅の第２の推定値を取得する。この２つの方法に基づき、第１の推定値及び第２の推定値のうち小さいほうの値が文字ストローク幅とみなされる。
【００８１】
第１の推定方法において、マージ後の文字行領域中の文字の文字ストローク幅の第１の推定値は、マージ後の文字行領域の高さのみに従って推定される。第１の推定方法は、文字ストローク幅は文字高さの１０分の１を超え且つ文字高さと文字行領域の高さとの差は小さいという仮定に基づく。
【００８２】
第１の推定値は、以下の式（１）により得られる。
0005523537.tif 000002
式中、ＳｔｒｏｋｅＷｉｄｔｈ１は文字ストローク幅の第１の推定値であり、ＨｅｉｇｈｔCharacterLineRegionはマージ後の文字行領域の高さである。
【００８３】
第２の推定方法において、マージ後の文字行領域中の文字の文字ストローク幅の第２の推定値は、文字行領域の黒画素分布に従って推定される。
【００８４】
第２の推定値は、以下の式（２）により得られる。
0005523537.tif 000003
式中、ＳｔｒｏｋｅＷｉｄｔｈ２は文字ストローク幅の第２の推定値であり、ＢｌａｃｋＰｉｘｅｌＣｏｕｎｔCharacterLineRegionはマージ後の文字行領域における黒画素カウントであり、ＷｉｄｔｈCharacterLineRegionはマージ後の文字行領域の幅である。
【００８５】
式（２）は、以下の演繹から得られる。
【００８６】
文字行領域の黒画素カウントは、以下の式（３）により計算できる。
0005523537.tif 000004
式中、ＣｈａｒａｃｔｅｒＡｍｏｕｎｔCharacterLineRegionはマージ後の文字行領域中の文字量を表し、ＳｔｒｏｋｅＷｉｄｔｈは文字ストローク幅を表す。
式中、ＡｖｅｒａｇｅＳｔｒｏｋｅＡｍｏｕｎｔCharacterは１文字中の平均ストローク量であり、これは、文字行領域が水平方向である場合は１文字中の平均垂直ストローク量に対応し、文字行領域が垂直方向である場合は１文字中の平均水平ストローク量に対応する。ＡｖｅｒａｇｅＳｔｒｏｋｅＡｍｏｕｎｔCharacterは、文書の言語に従って操作者により設定可能である。
【００８７】
文字行領域中の文字量は、以下の式により得られると考える。
0005523537.tif 000005
また、１文字中の平均ストローク量は、例えば以下の通りである。
0005523537.tif 000006
そこで、文字行領域の黒画素カウント計算式は次の通りとなる。
0005523537.tif 000007
そして、式（６）から式（２）を導出できる。
【００８８】
以上の説明では、第２の実施形態の処理は、第２の画素領域、すなわち空白領域が除去された画素領域に基づいてスペース画素行の検出を実行するが、本発明はそれに限定されない。言い換えると、空白領域の除去は、第２の実施形態の処理に不可欠ではなく、従って、第２の実施形態の処理により実現される効果に大きな影響を与えない。第１の画素領域中の画素領域から空白領域が除去されず、空白領域が除去されていない画素領域に基づいて第２の実施形態の処理で検出を実行したとしても、第２の実施形態の処理は、画素領域を相対的に正確に検出し、それにより画素領域を分割することができる。
【００８９】
［有利な効果］
第２の実施形態の方法は、先に説明したタイトル行のような文書画像に加えて、少なくとも、ノイズが含まれる文書画像、特に、ノイズが存在し、点在しているような文書画像にも有効且つ正確に適用可能であり、それにより、そのような文書画像の行分割の性能を向上できる。
【００９０】
図１５Ａ〜図１５Ｃは、従来の技術と本発明の第２の実施形態とによりそれぞれ実現されたノイズが存在し、点在している文書画像の行分割の結果の比較を概略的に示す。これらの図において、確認済みノイズ画素行は、第２の実施形態の処理により検出されたスペース画素行である。
【００９１】
図１５Ａに示されるように、文書画像は少なくとも２つのテキスト行を含み、分割されるべきであるが、従来の方法では、この文書画像を分割できないことがわかる。これに対し、本発明の方法によれば、図１５Ｂ及び図１５Ｃに示されるように、文書画像中のスペース画素行、すなわち確認済みノイズ画素行を正確に検出可能であり、文書画像は、文書画像中のノイズにより影響を受けることなくスペース画素行に沿って適切に分割される。
【００９２】
［第３の実施形態］
図１６Ａ〜図２１Ｃを参照して、本発明に係る行分割方法の第３の実施形態を以下に詳細に説明する。第３の実施形態は、テキスト行分割ステップを除いて第１の実施形態及び第２の実施形態のいずれともほぼ同一である。テキスト行分割ステップには、先に検出された文字画素行を利用して、検出済みスペース画素行が最終スペース画素行であるか否かを判定する判定ステップが更に含まれる。第３の実施形態のステップのうち、第１の実施形態及び第２の実施形態のステップと同様のステップは省略し、詳細には説明しない。
【００９３】
判定ステップは、テキストブロック中の２つの隣接テキスト行が相当に異なる長さを有する場合、すなわち一方のテキスト行の長さが隣接する別のテキスト行の長さと相当に異なる場合の従来の方法の欠陥に対処することを目的とする。
【００９４】
ここで、２つの場合が考えられる。一つ（第１のケース）は、上から下に向かって１つの画素領域中の第１のテキスト行が短く、第２のテキスト行は長い場合である。画素領域中の空白領域を検出するのが困難であり且つテキスト行幅、画素行の黒画素カウント並びに連続白画素シーケンス長さは誤って計算されるので、図１６Ａに示されるように、第１のテキスト行中の下部のいくつかの画素行が誤ってスペース画素行とみなされてしまい、その結果、画素領域は誤って分割されることになる。もう１つ（第２のケース）は、上から下に向かって１つの画素領域中の第１のテキスト行が長く、第２のテキスト行は短い場合である。空白領域を検出するのが困難であり且つテキスト行幅、画素行の黒画素カウント並びに連続白画素シーケンス長さは誤って計算されるので、図１６Ｂに示されるように、第２のテキスト行中の上部のいくつかの画素行が誤ってスペース画素行とみなされてしまい、その結果、画素領域は誤って分割されることになる。
【００９５】
第３の実施形態の判定ステップは、第２の画素領域中の１つ以上の検出済みスペース画素行の前の隣接する１つ以上の隣接文字画素行を利用することにより、１つ以上の検出済みスペース画素行から１つ以上の最終スペース画素行を判定することから成り、その後、判定された１つ以上の最終スペース画素行に基づいてテキスト行分割が実行される。一例において、判定ステップは、検出済みスペース画素行の黒画素分布並びに連続白画素分布と、すべての隣接文字画素行との関係を解析することにより実現される。このステップについては以下に説明する。
【００９６】
第３の実施形態の判定処理を、第１の実施形態又は第２の実施形態のいずれかの処理と多様な方法で組み合わせることができる。一例において、第３の実施形態の判定ステップは、第１の実施形態及び第２の実施形態のそれぞれのテキスト行分割ステップの処理のいずれか、すなわち図１２Ａ〜図１２Ｃの処理又は図１４の処理のいずれかの後に組み合わされてもよい。
【００９７】
図１７を参照して、第３の実施形態の判定ステップを以下に詳細に説明する。
【００９８】
ステップＳ７０１（以下、マージステップと呼ばれる）において、１つ以上の隣接する検出済み文字画素行は、１つの文字行領域（以下、第２の文字行領域と呼ばれる）にマージされる。
【００９９】
ステップＳ７０２（以下、第１の判定ステップと呼ばれる）において、空白領域が除去された文字行領域（以下、第３の文字行領域と呼ばれる）が第２の文字行領域から取得され、第３の文字行領域は、１つ以上の検出済みスペース画素行の各スペース画素行が第２のスペース画素行であるか否かを判定するために利用される。
【０１００】
ステップＳ７０３（以下、第２の判定ステップと呼ばれる）において、第１の判定ステップで判定された第２のスペース画素行が最終スペース画素行であるか否かが判定される。
【０１０１】
図１８は、第３の実施形態の第１の判定ステップの処理を示すフローチャートである。第１の判定ステップは、上記の２つのケースに適用可能であるが、第１のケースに適用されるのが好ましい。
【０１０２】
ステップＳ８０１において、第２の文字行領域中の空白領域を検出し且つ第２の文字行領域から空白領域を除去することにより、第３の文字行領域が取得される。残った文字行領域は、第３の文字行領域を構成すると考えられる。
【０１０３】
第２の文字行領域をいくつかの部分領域に分割し且つ各部分領域の黒画素カウントとその面積との比を計算することにより空白領域を検出する方法、図８に示される方法と同様に、文字行領域中の連続白画素シーケンス間の共通重複部分を利用することにより空白領域を検出する方法、図１０Ａ及び図１０Ｂに対応する方法と同様に、それら２つの方法の組み合わせを使用することにより空白領域を検出する方法などの多様な方法で、空白領域の検出を実現可能である。従って、文字行領域における空白領域の検出は詳細に説明されない。
【０１０４】
ステップＳ８０２において、第２のスペース画素行を判定するために、第３の文字行領域が利用される。第２のスペース画素行の判定は、多様な方法で実現可能である。
【０１０５】
一例において、スペース画素行が第２の画素行であるか否かを判定するために、第３の文字行領域のパラメータ並びに判定されるべきスペース画素行の対応するパラメータを使用できる。
【０１０６】
第３の文字行領域のパラメータは、例えば第３の文字行領域の幅を含む。第３の文字行領域の幅は、その領域に含まれる文字部分領域の幅の和を計算することにより取得される。
【０１０７】
スペース画素行の対応するパラメータは、第３の文字行領域に対応する一部分におけるスペース画素行のパラメータであり、例えばその部分のスペース画素行の黒画素カウント及びその部分のスペース画素行の連続白画素シーケンス長さ統計値を含む。図１９に示されるように、連続白画素シーケンス長さ統計値は、その部分のスペース画素行の最長の連続白画素シーケンスの長さ、あるいはその部分のスペース画素行の最長の連続白画素シーケンスの長さと２番目に長い連続白画素シーケンス長さとの和である。
【０１０８】
スペース画素行の一部と第３の文字行領域との対応は、通常、テキスト行に対して垂直な方向の対応を意味する。更に詳細には、第３の文字行領域に対応するスペース画素行の部分は、第３の文字行領域と等しい幅を有し且つ水平方向の縁部が水平方向に第３の文字行領域の縁部と整列しているスペース画素行の一部分を表す。特に、第３の行領域がいくつかの文字部分領域から構成される場合、スペース画素行のその部分は、テキスト行に対して垂直な方向に第３の文字行領域のいくつかの文字部分領域の各々とそれぞれ対応するいくつかの小部分を含む。
【０１０９】
第３の文字行領域のパラメータ及び判定されるべきスペース画素行のパラメータを使用して、図１２Ａ〜図１２Ｃに示される処理と同様に、第２のスペース画素行を多様な方法で判定できる。そのため、ここではステップＳ８０２の処理を省略し、詳細には説明しない。
【０１１０】
図２０を参照して、第２の判定ステップの処理を以下に説明する。第２の判定ステップも上記の２つのケースに適用可能であるが、第２のケースに適用されるのが好ましい。
【０１１１】
第２の判定ステップにおいて、第２のスペース画素行は、いくつかの小部分に分割され、それらの小部分における黒画素カウントを１つの推定黒画素カウント上限と比較することにより、第２のスペース画素行が最終スペース画素行（確認済みスペース画素行とも呼ばれる）であるか否かが判定される。推定黒画素カウント上限は、第３の文字行領域中の対応する部分領域における黒画素カウントの平均値である。第２の判定ステップは、１つの妥当な推論に基づく。すなわち、現在の第２のスペース画素行が文字画素行である場合、画素行の小部分の黒画素カウントのうち少なくとも１つの黒画素カウントは、文字画素行領域中の対応する部分領域における平均黒画素カウントより大きくなるという推論である。
【０１１２】
図２０は、第３の実施形態の第２の判定ステップの処理を示すフローチャートである。
【０１１３】
ステップＳ１００１において、第３の文字行領域はいくつかの部分領域に分割され、それに対応して、判定されるべき第２のスペース画素行はいくつかの小部分に分割される。
【０１１４】
ステップＳ１００２において、判定されるべき第２のスペース画素行のいくつかの小部分の黒画素カウントの中で最大の黒画素カウントを有する１つの小部分が選択される。
【０１１５】
ステップＳ１００３において、選択された最大黒画素カウントと選択された小部分に対応する第３の文字行領域中の部分領域から導出できる上限（黒画素カウント上限とも呼ばれる）とを比較することにより、第２のスペース画素行が最終スペース画素行であるか否かが判定される。この部分領域は、小部分と同一の幅を有する。最大黒画素カウントが黒画素カウント上限より小さい場合、第２のスペース画素行は最終スペース画素行である。
【０１１６】
小部分の黒画素カウント上限は、次の式（７）により計算できる。
0005523537.tif 000008
式中、ＷｉｄｔｈSubRegionは、その小部分に対応する第３の文字行領域中の部分領域の幅である。
【０１１７】
式（７）は、以下の演繹から得られる。
【０１１８】
第２のスペース画素行が最終スペース画素行である場合、小部分の黒画素カウントは、以下より小さくなるべきである。
0005523537.tif 000009
式中、ＣｈａｒａｃｔｅｒＡｍｏｕｎｔSubRegionは第３の文字行領域中の部分領域における文字量を表す。
式中、ＡｖｅｒａｇｅＳｔｒｏｋｅＡｍｏｕｎｔCharacterは１文字中の平均ストローク量であり、これは、第３の文字行領域が水平方向である場合は１文字中の平均垂直ストローク量に対応し、第３の文字行領域が垂直方向である場合は１文字中の平均水平ストローク量に対応する。ＡｖｅｒａｇｅＳｔｒｏｋｅＡｍｏｕｎｔCharacterは、文書の言語に従って操作者が設定可能である。
【０１１９】
部分領域中の文字量が、式（９）により得られ、１文字中の平均ストローク量が式（１０）により得られることを考慮する。
0005523537.tif 000010
0005523537.tif 000011
その文字のストローク幅は、以下により推定できる。
0005523537.tif 000012
このように、小部分の黒画素カウント上限の計算式を上記の式のように簡単にすることができる。
【０１２０】
あるいは、現在の第２のスペース画素行が最終スペース画素行であるか否かを判定するために、現在の第２のスペース画素行に加えて、現在の第２のスペース画素行の直前の第２のスペース画素行及び次の第２のスペース画素行も使用できる。更に詳細には、直前の第２のスペース画素行及び次の第２のスペース画素行の小部分における最大黒画素カウントが対応する上限より共に小さいか否かが判定される。共に小さければ、現在の第２のスペース画素行は、テキスト行間のスペース領域に属しているはずであるので、最終スペース画素行とラベル付けされる。
【０１２１】
以上の説明の中で、第３の実施形態の処理は、空白領域が除去された第２の画素領域及び第３の文字行領域に基づいて最終スペース画素行の判定を実行していたが、本発明は、これに限定されない。言い換えると、空白領域の除去は、第３の実施形態の処理には不可欠ではなく、従って第３の実施形態の処理により実現される効果に大きな影響を与えない。第２の画素領域及び第３の文字行領域に空白領域がまだ残っていたとしても、第３の実施形態の処理は、画素領域を相対的に正確に検出し且つ分割することができる。
【０１２２】
更に、第３の実施形態における処理の順序は単なる例であり、他の順序も利用可能である。例えば、第１の判定ステップと第２の判定ステップの順序を入れ替えてもよく、第１の判定ステップの前に第２の判定ステップを実行することも可能である。この場合、検出済みスペース画素行が第２のスペース画素行であるか否かを判定するために、検出済みスペース画素行は、まず、図２０に示される処理のように第２の判定ステップにより処理される。次に、最終スペース画素行を判定するために、図１７及び図１８に示される処理のように、第２のスペース画素行は、第１の判定ステップにより処理されることになるだろう。この処理は、実行可能な空白領域の除去を含まなくてもよい。
【０１２３】
［有利な効果］
以上説明したタイトル行のような文書画像又はノイズが点在している文書画像のような文書画像の他にも、第３の実施形態の方法は、複雑なレイアウトを有する文書画像、特にテキストブロック中の２つの隣接テキスト行が相当に異なる長さを有する文書画像に有効且つ正確に適用可能であり、それによりそのような文書画像の行分割の性能を向上できる。
【０１２４】
図２１Ａ〜図２１Ｃは、テキストブロック中の２つの隣接テキスト行が相当に異なる長さを有する文書画像に関して、従来の技術と、第３の実施形態の方法とによりそれぞれ実現された行分割の結果の比較を概略的に示す。これらの図において、確認済みノイズ画素行は、第３の実施形態の方法により判定された最終スペース画素行に対応する。
【０１２５】
このような文書画像では、従来の方法を使用した場合、図２１Ａ及び図２１Ｂに示されるように、短いテキスト行は誤って分割されてしまうことがわかる。これに対し、第３の実施形態の処理を利用することにより、図２１Ｃに示されるように、文書画像から３つのテキスト行が正確に分割される。
【０１２６】
更に、先に説明した第１の実施形態から第３の実施形態により実現される有利な効果を考慮すると、複雑なレイアウトを有するのに加えてノイズが存在し、点在している文書画像も、第３の実施形態の方法を利用することにより有効且つ正確に分割できる。
【０１２７】
［実施例１］
本発明の方法を理解しやすくするために、図２２Ａ〜図２２Ｅを参照して実施例１を説明する。実施例１において、第１の実施形態から第３の実施形態の方法を利用することにより、複雑なレイアウトを有し且つノイズが点在している文書画像が行分割される。
【０１２８】
図２２Ａに示されるように、元の文書画像は、第１のテキスト行が第２のテキスト行より相当に短いという複雑なレイアウトを有し且つノイズが点在している画像である。
【０１２９】
図２２Ｂに示されるように、まず元の文書画像中のスペース画素行を発見するために、第１の実施形態及び第２の実施形態の方法を利用することにより文書画像が検出される。図２２Ｂのノイズ画素行仮定は、検出済みスペース画素行に対応する。
【０１３０】
図２２Ｃに示されるように、文書画像中の検出済みスペース画素行は、第３の実施形態の第１の判定ステップを利用することにより判定される。図２２Ｃのノイズ画素行仮定は、判定された第２のスペース画素行に対応する。
【０１３１】
図２２Ｄに示されるように、第３の実施形態の第２の判定ステップを利用することにより、最終スペース画素行が発見される。図２２Ｄの確認済みノイズ画素行仮定は、判定された最終スペース画素行に対応する。
【０１３２】
図２２Ｅに示されるように、判定された最終スペース画素行に沿って、文書画像を２つのテキスト行に正確に分割できる。
【０１３３】
図２３は、各モジュール手段から構成された文書画像の行分割システムの一般的な構成を示すブロック図である。
【０１３４】
図２３に示されるように、行分割システム２００は、少なくとも１つの画素領域を含む第１の画素領域を取得するためにテキストブロックを分割する第１の分割ユニット２０１と、第１の画素領域中の各画素領域から空白領域を検出し且つ空白領域を除去することにより対応する第２の画素領域を取得する空白領域除去ユニット２０２と、第１の画素領域中の画素領域ごとに、対応する第２の画素領域を利用することによりテキスト行の分割を実行するテキスト行分割ユニット２０３とを備える。
【０１３５】
空白領域除去ユニット２０２は、第１の領域の各画素領域中の各々の画素行における連続白画素シーケンス間の共通重複部分を画素領域中の空白領域として検出する空白領域検出ユニット２０２−１と、画素領域から空白領域を除去することにより対応する第２の画素領域を取得する除去ユニット２０２−２とを備えるのが好ましい。
【０１３６】
テキスト行分割ユニット２０３は、第２の画素領域中の画素行における黒画素カウントと第２の画素領域の幅との比を利用することにより、画素行が文字画素行であるか又はスペース画素行であるかを検出する黒画素カウント検出ユニット２０３−１を備えるのが好ましく、テキスト行分割ユニット２０３は、画素行における連続白画素シーケンス長さ統計値と第２の画素領域の幅との比を利用することにより、画素行が文字画素行であるか又はスペース画素行であるかを検出する白画素シーケンス検出ユニット２０３−２を更に備えるのが好ましい。
【０１３７】
テキスト行分割ユニット２０３は、直前の検出済み文字画素行に関連する文字ストローク幅を利用することにより、画素行がスペース画素行であるか否かを検出する文字ストローク幅検出ユニット２０３−３を更に備えるのが好ましい。文字ストローク幅検出ユニット２０３−３は、検出されるべき画素行の前の隣接するすべての検出済み文字画素行を１つの文字行領域としてマージするマージユニット２０３−３１と、文字行領域の文字ストローク幅を推定する推定ユニット２０３−３２と、検出されるべき画素行をいくつかの小部分に分割し且ついくつかの小部分の中から最大の黒画素カウントを有する小部分を検索する検索ユニット２０３−３３と、スペース画素行を検出するために、最大の黒画素カウントと文字ストローク幅とを比較する比較ユニット２０３−３４とを備えるのが好ましい。
【０１３８】
テキスト行分割ユニット２０３は、第２の画素領域中の１つ以上の検出済みスペース画素行の前の隣接する１つ以上の隣接文字画素行を利用することにより、１つ以上の検出済みスペース画素行から１つ以上の最終スペース画素行を判定する判定ユニット２０３−４を更に備えるのが好ましい。判定ユニット２０３−４は、１つ以上の隣接文字画素行を第２の文字行領域としてマージするマージユニット２０３−４１と、１つ以上の検出済みスペース画素行の各スペース画素行が第２のスペース画素行であるか否かを判定する第１の判定ユニット２０３−４２と、第２のスペース画素行から最終スペース画素行を判定する第２の判定ユニット２０３−４３とを備えるのが好ましい。
【０１３９】
第１の判定ユニット２０３−４２は、空白領域を検出し且つ第２の文字行領域から空白領域を除去することにより、第２の文字行領域から第３の文字行領域を取得する文字行領域取得ユニット２０３−４２１と、第３の文字行領域に対応する部分におけるスペース画素行の黒画素カウントと第３の文字行領域の幅との比を利用することにより、スペース画素行が第２のスペース画素行であるか否かを判定する黒画素カウント判定ユニット２０３−４２２とを備えるのが好ましく、第１の判定ユニット２０３−４２は、第３の文字行領域に対応する部分におけるスペース画素行の連続白画素シーケンス長さ統計値と第３の文字行領域の幅との比を利用することにより、スペース画素行が第２のスペース画素行であるか否かを判定する白画素シーケンス判定ユニット２０３−４２３を更に備えるのが好ましい。
【０１４０】
第２の判定ユニット２０３−４３は、第３の文字行領域をいくつかの部分領域に分割し且つそれに対応して第２のスペース画素行をいくつかの小部分に分割する分割ユニット２０３−４３１と、第２のスペース画素行中のいくつかの小部分の中から最大の黒画素カウントを有する小部分を選択する選択ユニット２０３−４３２と、最大の黒画素カウントを有する小部分に関して上限（黒画素カウント上限とも呼ばれる）を計算する上限計算ユニット２０３−４３３と、最終スペース画素行を判定するために最大の黒画素カウントと上限とを比較する比較ユニット２０３−４３４とを備えるのが好ましい。
【０１４１】
上記の各手段は、先に説明した処理を実現するための好適なモジュールの例である。種々のステップを実現するモジュールのすべてがここに挙げられているわけではない。しかし、ある特定の処理を実行するステップがある場合、それと同一の処理を実現するための対応する機能モジュール又は手段が存在する。
【０１４２】
本発明の方法及びシステムを多様な方法で実現可能である。例えば、本発明の方法及びシステムをソフトウェア、ハードウェア、ファームウェア又はそれらの何らかの組み合わせによって実現可能である。方法のステップに関して先に説明された実行の順序は単なる例であり、特に指示のない限り、本発明の方法のステップは、先に特定して説明した順序に限定されない。更に、いくつかの実施形態において、本発明は、本発明に係る方法を実現するための機械可読命令を含めて、記録媒体に記録されたプログラムとして実現されてもよい。従って、本発明は、本発明に係る方法を実現するためのプログラムを記憶する記録媒体を更に含む。
【０１４３】
本発明のいくつかの特定の実施形態を例によって詳細に説明したが、上記の例は単に例示を目的としており、本発明の範囲を限定することを意図しないことは当業者には理解されるべきである。本発明の趣旨の範囲から逸脱することなく上述の実施形態を変形できることは当業者には理解されるべきである。本発明の範囲は、添付の特許請求の範囲により定義される。
【図１】
0005523537.tif 000013
【図２Ａ】
0005523537.tif 000014
【図２Ｂ】
0005523537.tif 000015
【図２Ｃ】
0005523537.tif 000016
【図２Ｄ】
0005523537.tif 000017
【図２Ｅ】
0005523537.tif 000018
【図３】
0005523537.tif 000019
【図４】
0005523537.tif 000020
【図５】
0005523537.tif 000021
【図６】
0005523537.tif 000022
【図７】
0005523537.tif 000023
【図８】
0005523537.tif 000024
【図９】
0005523537.tif 000025
【図１０Ａ】
0005523537.tif 000026
【図１０Ｂ】
0005523537.tif 000027
【図１１】
0005523537.tif 000028
【図１２Ａ】
0005523537.tif 000029
【図１２Ｂ】
0005523537.tif 000030
【図１２Ｃ】
0005523537.tif 000031
【図１３Ａ】
0005523537.tif 000032
【図１３Ｂ】
0005523537.tif 000033
【図１４】
0005523537.tif 000034
【図１５Ａ】
0005523537.tif 000035
【図１５Ｂ】
0005523537.tif 000036
【図１５Ｃ】
0005523537.tif 000037
【図１６Ａ】
0005523537.tif 000038
【図１６Ｂ】
0005523537.tif 000039
【図１７】
0005523537.tif 000040
【図１８】
0005523537.tif 000041
【図１９】
0005523537.tif 000042
【図２０】
0005523537.tif 000043
【図２１Ａ】
0005523537.tif 000044
【図２１Ｂ】
0005523537.tif 000045
【図２１Ｃ】
0005523537.tif 000046
【図２２Ａ】
0005523537.tif 000047
【図２２Ｂ】
0005523537.tif 000048
【図２２Ｃ】
0005523537.tif 000049
【図２２Ｄ】
0005523537.tif 000050
【図２２Ｅ】
0005523537.tif 000051
【図２３】
0005523537.tif 000052