(57)【特許請求の範囲】
【請求項１】
コンピュータが、
２値化された文書画像の黒画素の連結成分に関する外接矩形を記憶手段から読み出し、  読み出した外接矩形の大きさからテキストサイズを推定して前記記憶手段に記憶し、
読み出したテキストサイズに基づきテキスト候補を推定して前記記憶手段に記憶し、
読み出したテキスト候補を中心とした一定の大きさの領域内に含まれるテキスト候補の個数を密集度として求め、密集度がしきい値以下のものをテキストと判定し、判定されたテキスト候補を前記記憶手段に記憶する、
ことを特徴とする文書画像レイアウト識別方法。
【請求項２】
２値化された文書画像の黒画素の連結成分に関する外接矩形の集合からテキストを抽出する文書画像レイアウト識別装置であって、
上記外接矩形の大きさからテキストサイズを推定する手段と、
上記推定されたテキストサイズに基づきテキスト候補を推定する手段と、
テキスト候補を中心とした一定の大きさの領域内に含まれるテキスト候補の個数を密集度として求め、密集度がしきい値以下のものをテキストと判定する手段とを備えた
ことを特徴する文書画像レイアウト識別装置。
【請求項３】
コンピュータを、
２値化された文書画像の黒画素の連結成分に関する外接矩形を記憶手段から読み出す手段、
読み出した外接矩形の大きさからテキストサイズを推定して前記記憶手段に記憶する手段、
読み出したテキストサイズ基づきテキスト候補を推定して前記記憶手段に記憶する手段、
読み出したテキスト候補を中心とした一定の大きさの領域内に含まれるテキスト候補の個数を密集度として求め、密集度がしきい値以下のものをテキストと判定し、判定されたテキスト候補を前記記憶手段に記憶する手段、
として機能させるための文書画像レイアウト識別プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文書画像を認識するための方法および装置に関し、さらに詳細には、文書画像のレイアウト識別処理におけるテキスト抽出処理を正確かつ高速に行うことができる文書レイアウト識別方法および装置に関するものである。
【０００２】
【従来の技術】
従来、レイアウト識別処理は次のように行われていた。
まず、２値の文書画像をラベリングし、連結成分の外接矩形を抽出した後、外接矩形の相対的な大きさに基づいて、テキスト、図、セパレータ等の属性を推定する。その後、テキスト候補の外接矩形を対象として、それらの相対的な大きさ、位置関係、または、周期性等を考慮することにより、テキストが構成する行及び段の抽出処理を行う。
【０００３】
【発明が解決しようとする課題】
しかしながら、テキストの外接矩形を推定するときに、図１０に示すように、文書に写真や新聞の見出しによく使われるような背景模様が含まれる場合、従来の方法では、写真や背景模様を構成する要素の一部が、誤ってテキストと判定されてしまうといった問題があった。
さらに、写真や背景模様は、図１１（ａ）（ｂ）の拡大図に示すように網点から構成されており、テキストと誤判定される要素の個数が、実際のテキストの個数と比べ、はるかに多い。そのため、テキストと誤判定された要素の影響によって、行または段抽出処理が正しく行われなかったり、行または段抽出処理の処理時間が膨大になってしまっていた。
【０００４】
本発明は上記問題点を解決するためになされたものであって、その目的とするところは、文書画像に写真の一部や背景模様等、小さな構成要素が多数配置されていても、テキストの行及び段抽出処理に無駄な時間をかけることなく、正確なレイアウト識別が可能な文書レイアウト識別方法および装置を提供することである。
【０００５】
【課題を解決するための手段】
図１は本発明の概要を説明する図である。
同図に示すように２値化された文書画像データはラベリング手段１でラベリング処理を施され、連結成分の外接矩形が求められる。テキストサイズ推定手段２は、各外接矩形の大きさの最頻値からテキストサイズを推定する。テキスト候補推定手段３は上記推定されたテキストサイズと各外接矩形の大きさからテキスト候補を推定する。
密集度に基づくテキスト候補判定手段４は、テキスト候補を中心とした一定の大きさの領域内に含まれるテキスト候補の個数を密集度として求め、密集度がしきい値以下のものをテキストと判定する。
すなわち、相対的な大きさに基づいてテキストと推定されたテキスト候補が、本当にテキストかどうかを、テキスト候補の周辺における矩形の密集度から再度判定し、誤判定されたテキスト候補が行及び段抽出処理に回されることを防ぐ。
具体的には、テキスト候補を中心としたある一定の大きさの領域を想定し、その内部に含まれるテキスト候補の個数を密集度として計算し、密集度があるしきい値以下であればテキストと判定し、しきい値以上ならば非テキストと判定する。また、テキスト候補の矩形集合から、新たな矩形集合を生成し、その２つの集合間で矩形の重複チェックを例えば平面走査法によって行うことにより、処理の高速化を図ることができる。
【０００６】
【発明の実施の形態】
図２は本発明の処理を行うためのシステムの構成例を示す図である。本発明は、同図に示すように、ＣＰＵ１１、ＲＡＭ１２、ＲＯＭ１３、外部記憶装置１４、プリンタ、ディスプレイ、キーボード等から構成される入出力装置１５、記録媒体読み取り装置１６、画像読み取りを行うカラー入力装置、ＣＣＤカメラ、スキャナ等の画像入力装置１７、図示しない通信インタフェース等から構成されるシステムで実現することができる。
そして、上記スキャナ１７等の画像入力装置から読み込んだ例えば前記図１０に示す文書画像からテキスト部分を識別する。
【０００７】
次に本発明の実施例を図３に示すフローチャートにより説明する。
図３に示すフローチャートにおいて処理対象となるデータは、上記スキャナ等の画像入力装置から入力された２値化された前記図１０に示したような写真、背景模様に含む文書画像である。また、処理結果として得られる出力は、テキスト候補の外接矩形の集合である。
（１）ラベリング
入力された２値文書画像に対し、ラベリング処理を施す。すなわち、画像全体をラベリングして、図４に示すように黒画素連結領域を抽出する。
その結果、連結成分の個数と、各連結成分の外接矩形の座標が得られる。
【０００８】
（２）テキストサイズ推定
上記各外接矩形に関し、次のようにヒストグラムを生成し、ヒストグラムからテキストサイズを推定する。
まず、図５（ａ）に示すように外接矩形の左上点を（Ｘ1 ，Ｙ1 ）、右下点を（Ｘ2 ，Ｙ2 ）とし、ｄｘ＝Ｘ2 −Ｘ1 ＋１，ｄｙ＝Ｙ2 −Ｙ1 ＋１とおく。なお、＋１するのは、両端点の画素をｄｘ，ｄｙに含ませるためである。
次に、ｔ＝ｍａｘ（ｄｘ，ｄｙ）とし、ヒストグラムＨ1 （ｔ）に、ｄｘ×ｄｙすなわち外接矩形の面積を加算し、ヒストグラムＨ2 （ｔ）に１を加算する。その結果、例えば図５（ｂ）に示すようなヒストグラムＨ1 （ｔ）、Ｈ2 （ｔ）が作成される。
そして最終的に、Ｈ（ｔ）＝Ｈ1 （ｔ）×Ｈ2 （ｔ）により、図５（ｂ）に示すようにヒストグラムＨ（ｔ）を得る。このヒストグラムＨの最大を与えるｔが、テキストサイズＴであると推定する。
上記のように外接矩形の面積のヒストグラムＨ1 （ｔ）と外接矩形の個数のヒストグラムＨ2 （ｔ）を作成し、それらを掛け合わせたヒストグラムＨ（ｔ）によりテキストサイズＴを推定することにより、文書画像中に、数は少なく面積の大きな矩形、数が多く面積が小さい矩形が存在しても、それらに大きく影響されることなくなくテキストサイズＴを推定することができる。
【０００９】
（３）矩形の大きさに基づくテキスト候補推定
前記文書画像中の各矩形に対し、ｔ＝ｍａｘ（ｄｘ，ｄｙ）を求め、ある数ｋを用いた条件式：ｔ≦Ｔ×ｋを満たすものをテキスト候補と推定する。例えば、ｋは５などである。
【００１０】
（４）密集度に基づくテキスト候補の推定
まず、密集度の定義を示す。ある領域内の矩形集合において、点Ａにおける矩形の密集度とは、図６に示すように、点Ａを中心とし１辺がある定められた長さの正方形の中に含まれる矩形の個数のことである。
密集度に基づくテキスト候補の推定処理においては、以下に説明するように、上記テキスト候補の矩形集合とテキストサイズＴから近傍集合を生成して密集度を求め、密集度がしきい値以上のものをテキスト候補として出力する。
【００１１】
▲１▼  近傍集合生成
矩形に対し、矩形の中心点を中心とし１辺が〔テキストサイズＴ〕×Ｌの正方形を、近傍と呼ぶことにする。ここで、Ｌはあらかじめ定められた数で、例えば０．６などである。各矩形に対し、このような近傍を求める。
▲２▼  重複チェックによる密集度の計算
各近傍に対し、近傍領域に含まれる矩形を後述する平面走査法により効率的に調べ上げ、各矩形に対しその近傍に含まれる矩形の個数を求める。そして、近傍に含まれる矩形の個数をその矩形の密集度ωとする。
そして、各矩形について、上記密集度ωと予め定められたしきい値ｔｈを比較し、ω≦ｔｈであれば、その矩形はテキスト候補として判定する。また、それ以外は非テキストと判定する。ここで、上記しきい値ｔｈは例えば１０などである。
【００１２】
以下、上記平面走査法による近傍領域に含まれる矩形の個数の求め方について説明する。平面走査法は、図７に示すように文書画像を走査線により走査して、各テキスト候補の矩形Ｒｔ〔ｉ〕（ｉ＝１…Ｎ）の近傍Ｒｎ〔ｉ〕（ｉ＝１…Ｎ）に含まれる矩形の個数を求める方法である。
まず、以下で使用する記述について説明する。
・矩形情報
ｉ番目の矩形情報Ｒ〔ｉ〕は以下のような形式を持つ。
ｘ１：左上ｘ座標
ｙ１：左上ｙ座標
ｘ２：右下ｘ座標
ｙ２：右下ｙ座標
【００１３】
・カレント情報
カレント情報とは上記した走査線の役割を果たすものであり、ｉ番目のカレントＣ〔ｉ〕は以下の形式で表現される。
ｘ    ：ｘ座標
label ：ラベル番号
flag1 ：ＩＮまたはＯＵＴの属性
flag2 ：ＴＥＸＴ（テキスト候補）またはＮＥＩＧＨＢＯＲ（近傍）の属性
【００１４】
・スキャン集合
スキャンテキスト集合とは、上記走査線上に乗っているテキスト集合である。また、スキャン近傍集合とは上記走査線上に乗っている近傍の集合である。
・密集度の情報
ｉ番目のテキスト候補の密集度ω〔ｉ〕は、ｉ番目のテキスト候補の近傍に重複するテキスト候補の個数で表され、以下の形式で表現される。
num ：重複しているテキスト矩形の個数
label ：重複しているテキスト矩形のラベル番号
【００１５】
次に平面走査法による密集度の計算について説明する。
(1) テキスト候補をＲｔ〔ｉ〕（ｉ＝１，…，Ｎ）によって表し、Ｒｔ〔ｉ〕（ｉ＝１，…，Ｎ）にテキスト候補の外接矩形座標とラベル番号を代入する。
(2) 近傍をＲｎ〔ｉ〕（ｉ＝１，…，Ｎ）によって表し、Ｒｎ〔ｉ〕（ｉ＝１，…，Ｎ）に、テキスト候補Ｒｔ〔ｉ〕の近傍の座標と、Ｒｔ〔ｉ〕のラベル番号を代入する。
【００１６】
(3) カレントをＣ〔ｉ〕（ｉ＝１，…，４Ｎ）によって表す。まず、Ｃ〔２ｉ−１〕（ｉ＝ｉ，…，Ｎ）についてｘにはテキスト候補Ｒｔ〔ｉ〕のｘ１を、label にはＲｔ〔ｉ〕のlabel を、flag1 にはＩＮを、flag2 にはＴＥＸＴを代入する。また、Ｃ〔２ｉ〕（ｉ＝ｉ，…，Ｎ）について、ｘにはテキスト候補Ｒｔ〔ｉ〕のｘ２を、label にはＲｔ〔ｉ〕のlabel を、flag1 にはＯＵＴを、flag2 にはＴＥＸＴを代入する。
次に、Ｃ〔２ｉ−１＋２Ｎ〕（（ｉ＝１，…，４Ｎ）について、ｘには近傍Ｒｎ〔ｉ〕のlabel を、flag1 にはＩＮを、flag2 にはＮＥＩＧＨＢＯＲを代入する。また、Ｃ〔２ｉ＋２Ｎ〕（ｉ＝ｉ，…，Ｎ）について、ｘには近傍Ｒｎ〔ｉ〕のｘ２を、label にはＲｎ〔ｉ〕のlabel を、flag1 にはＯＵＴを、flag2 にはＮＥＩＧＨＢＯＲを代入する。
すなわち、テキストＲｔ〔ｉ〕のＩＮ（ｘ＝ｘ１）について、カレントＣ〔２ｉ−１〕が、テキストＲｔ〔ｉ〕のＯＵＴ（ｘ＝ｘ２）について、カレントＣ〔２ｉ〕が、その近傍Ｒｎ〔ｉ〕のＩＮ（ｘ＝ｘ１）について、カレントＣ〔２ｉ−１＋Ｎ〕が、Ｒｎ〔ｉ〕のＯＵＴ（ｘ＝ｘ２）について、カレントＣ〔２ｉ＋Ｎ〕が定められる。
(4) Ｃ〔ｉ〕（ｉ＝ｉ，…，４Ｎ）をｘに関しソートする。
【００１７】
(5) Ｃ〔ｉ〕（ｉ＝ｉ，…，４Ｎ）について以下の処理を行う。
(i) flag1 ＝ＩＮ、flag2 ＝ＴＥＸＴの場合
図８（ａ）に示すようにＣ〔ｉ〕のlabel 番号をＬとするとき、テキスト候補Ｒｔ〔Ｌ〕をスキャンテキスト集合に登録する。
【００１８】
(ii) flag1＝ＯＵＴ、flag2 ＝ＴＥＸＴの場合
Ｃ〔ｉ〕のlabel 番号をＬとするとき、テキスト候補Ｒｔ〔Ｌ〕が、スキャン近傍集合（走査線上に乗っている近傍）に属する近傍で、その近傍のｘ１が上記テキスト候補Ｒｔ〔Ｌ〕のｘ１より小さいもの、と重なっているかをチェックする。重なっていれば、重なっている近傍のラベル番号をＬ１，…Ｌｋとするとき、ω〔Ｌ１〕，ω〔Ｌ２〕，…，ω〔Ｌｋ〕について、個数を一つ増加させ、ω〔Ｌ１〕，ω〔Ｌ２〕，…，ω〔Ｌｋ〕のラベル番号に上記Ｌを記録する。上記処理によりω〔Ｌ１〕，ω〔Ｌ２〕，…，ω〔Ｌｋ〕にＲｔ〔Ｌ〕が登録されたので、Ｒｔ〔Ｌ〕をスキャンテキスト集合から抹消する。
例えば、図８（ｂ）に示すように近傍Ｒｎ〔Ｌ１〕、Ｒｎ〔Ｌ２〕がＲｔ〔Ｌ〕と重なっており、そのｘ１がＲｔ〔Ｌ〕のｘ１より小さい場合には、ω（Ｌ１），ω〔Ｌ２〕の個数を１増加させ、Ｒｔ〔Ｌ〕をスキャン近傍集合から抹消する。
なお、Ｒｔ〔Ｌ〕がスキャン近傍集合に属する近傍で、そのｘ１がＲｔ〔Ｌ〕のｘ１より大きいもの（図８ではＲｎ〔Ｌ３〕）と重なっているかは、次の(iii) でチェックされるので、ここではチェックする必要はない。
【００１９】
(iii) flag1 ＝ＩＮ、flag2 ＝ＮＥＩＧＨＢＯＲの場合
Ｃ〔ｉ〕のlabel 番号をＬとするとき、Ｒｎ〔Ｌ〕をスキャン近傍集合に登録する。そして、Ｒｎ〔Ｌ〕がスキャンテキスト集合（走査線上に乗っているテキスト候補の集合）に属するテキスト矩形と重なっているかをチェックする。そして重なっていれば、その個数とラベル番号をω〔Ｌ〕に記録する。
例えば図９（ａ）に示すように、Ｒｎ〔Ｌ〕がＲｔ〔Ｌｍ〕、Ｒｔ〔Ｌｎ〕と重なっている場合、ω（Ｌ）に個数２を加え、ラベル番号Ｌｍ，Ｌｎを登録する。
【００２０】
(iv)flag1 ＝ＯＵＴ、flag2 ＝ＮＥＩＧＨＢＯＲの場合
Ｃ〔ｉ〕のlabel 番号をＬとするとき、Ｒｎ〔Ｌ〕がスキャンテキスト集合（走査線上に乗っているテキスト候補の集合）に属するテキスト矩形と重なっているかをチェックし、ω〔Ｌ〕に含まれていない分だけ、その個数とラベル番号をω〔Ｌ〕に追加する。そしてＲｎ〔Ｌ〕をスキャン近傍集合から抹消する。
例えば、図９（ｂ）に示すようにＲｎ〔Ｌ〕がＲｔ〔Ｌｋ〕と重なっている場合には、ω〔Ｌ〕に個数１を追加し、ラベル番号Ｌｋを追加する。なお、Ｒｔ〔Ｌｉ〕は、Ｒｎ〔Ｌ〕がスキャン近傍集合に登録されるとき、すなわち(iii) でチェックしており、すでに登録済である。
【００２１】
【発明の効果】
以上説明したように、本発明においては、テキスト候補を中心とした一定の大きさの領域内に含まれるテキスト候補の個数を密集度として求め、密集度がしきい値以下のものをテキストと判定しているので、文書画像において写真の一部や背景模様等、小さな構成要素が多数配置されていても、それらをテキストと誤判定することがない。このため、テキストの行及び段抽出処理に無駄な時間をかけることなく、正確なレイアウト識別が可能となる。
【図面の簡単な説明】
【図１】本発明の概要を説明する図である。
【図２】本発明を実現するためのシステムの構成例を示す図である。
【図３】本発明の実施例の処理を示すフローチャートである。
【図４】黒画素連結領域と外接矩形を説明する図である。
【図５】テキストサイズの推定方法を説明する図である。
【図６】本発明における密集度の定義を示す図である。
【図７】平面走査法を説明する図（１）である。
【図８】平面走査法を説明する図（２）である。
【図９】平面走査法を説明する図（３）である。
【図１０】本発明が対象とする文書画像の一例を示す図である。
【図１１】文書画像中に含まれる写真、背景模様の１例を示す図である。
【符号の説明】
１  ラベリング手段
２  テキストサイズ推定手段
３  テキスト候補推定手段
４  密集度によるテキスト候補判定手段
【図１】
0003960756.tif 000002
【図２】
0003960756.tif 000003
【図３】
0003960756.tif 000004
【図４】
0003960756.tif 000005
【図５】
0003960756.tif 000006
【図６】
0003960756.tif 000007
【図７】
0003960756.tif 000008
【図８】
0003960756.tif 000009
【図９】
0003960756.tif 000010
【図１０】
0003960756.tif 000011
【図１１】
0003960756.tif 000012