(57)【要約】【課題】文書画像データから、罫線を抽出して符号化する。【解決手段】２値化した文書の画像を取得し、この画像から連結画素を認識する。そして、連結画素の周囲長を求め、周囲長が所定のしきい値ＴＨＣより大きい連結画素を罫線と判断し、罫線のみを抽出する。しきい値ＴＨＣの設定にあたっては、文書画像中の連結画素を記憶し、記憶した各連結画素について、周囲長ごとに、その周囲長を有する連結画素の度数を数え、周囲長と度数の関係において、最も小さい周囲長の階級の点（ｘ１，ｙ１）と最も大きい周囲長の階級の点（ｘＮ，ｙＮ）を結ぶ直線から最も離れた点である極大点（ｘｍ’，ｙｍ’）を求め、この極大点の周囲長をしきい値ＴＨＣとして設定する。【選択図】      図  ８
2004334743.tif 000002
【特許請求の範囲】
【請求項１】
文字と罫線が混ざった文書画像から罫線を抽出する方法であって、
２値化した文書の画像を取得するステップと、
連結画素を認識するステップと、
連結画素の周囲長を求めるステップと、
周囲長がしきい値より大きい連結画素を罫線と判断するステップと
を含むことを特徴とする罫線の抽出方法。
【請求項２】
前記しきい値の決定に際し、
前記文書画像中の連結画素を記憶するステップと、
前記記憶した各連結画素について、前記周囲長を階級ごとに累積して度数を得るステップと、
前記周囲長と前記度数を座標軸とした直交座標上において、最も小さい周囲長の階級にある点と最も大きい周囲長の階級にある点を結ぶ直線から最も離れた連結画素の点である極大点を求めるステップと、
前記極大点の周囲長を前記しきい値として設定するステップとを含んで決定することを特徴とする請求項１に記載の罫線の抽出方法。
【請求項３】
請求項１又は請求項２に記載の罫線の抽出方法により抽出した罫線画像を符号化する方法であって、
前記罫線画像から、罫線が交差する節点位置を認識するステップと、
前記節点位置において、その節点が、表構造のうちの右上、左上、右下、または左下のそれぞれの角部になりうるかを判定するステップと、
前記右上、左上、右下、または左下のそれぞれの角部になりうるかの組合せに対し１対１に節点番号を対応させたテーブルを参照し、前記節点に節点番号を割り当てるステップとを含むことを特徴とする罫線の符号化方法。
【請求項４】
文字と罫線が混ざった文書画像から罫線を抽出するため、コンピュータを、
２値化した文書の画像を入力する手段、
連結画素を認識する手段、
連結画素の周囲長を求める手段、
周囲長がしきい値より大きい連結画素を罫線と判断する手段として機能させることを特徴とする罫線抽出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文書の画像データから罫線を抽出する方法に関する。
【０００２】
【従来の技術】
高度情報化社会の中、多くの文書が電子化され、各種メディアを通じて利用できるようになっている。一方、依然として、紙による文書も様々な状況において大量に用いられているが、情報の開示や作業の効率化のため、近年これら紙の文書に対する自動電子化の要求が急速に高まってきている。この「紙」から「電子データ」への変換の際に、大きな手助けとなるのがＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）である。文書画像処理技術の向上に伴い、ＯＣＲはより実用的なものとなり、イメージスキャナを含むコンピュータの普及や、高認識率ＯＣＲソフトウェアの低価格化が進んだことにより、社会の中で利用可能な環境が整いつつある。
【０００３】
しかしながら、図表、罫線などの文字以外の成分が含まれた文書画像に関しては、現状のＯＣＲでは対応しきれていないことが多い。各領域の属性を手作業で指定するＯＣＲソフトウェアもあるが、その場合、処理の完全な自動化を行うことはできない。また、処理の対象を表形式文書に限定し、表構造の認識に特化したＯＣＲソフトウェアもあるが、その出力においては、表構造にかなりの冗長性を持たせて表現しており、表構造を簡潔に表していない。すなわち、細かい格子に罫線をマッピングしたに過ぎず、システムが表構造を理解していることにはなっていない。
【０００４】
表は、社会全般において、使われる機会が非常に多い表現方法であり、文章などのような構造的に複雑なものではなく、内容を属性ごとに整列させ、意味をまとめて整理するために用いられるため、文章中では特に重要な要素である。したがって、表の表現には、構造を視覚的に再現するだけではなく、冗長性を無くした簡潔なものを用いなくては、表を理解したことにならない。ここ数年、電子商取引（ＥＣ：Ｅｌｅｃｔｒｏｎｉｃ  Ｃｏｍｍｅｒｃｅ）や電子データ交換（ＥＤＩ：Ｅｌｅｃｔｒｏｎｉｃ  Ｄａｔａ  Ｉｎｔｅｒｃｈａｎｇｅ）を進めるために、ＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）という技術が注目されているが、これは、各領域のデータに属性を与え、テキスト処理を容易にするためのものであり、領域の指定に冗長性が有る場合には、そのデータに属性を与えることが困難になる。
【０００５】
このような表構造の理解により、表構造を符号化する前提として、表構造（罫線）を電子データ化する技術が必要である。表構造を電子データ化する技術としては、入力された文書画像を２値化し、画像の縦方向と横方向について、それぞれ黒画素の画素数を各行、各列ごとに求め、この投影値に基づいて罫線を抽出する方法が知られている（例えば、特許文献１参照）。
【０００６】
【特許文献１】
特開２００１−１０９８８８号公報（段落００６４、図１８等）
【０００７】
【発明が解決しようとする課題】
しかしながら、前記した表が大きく傾いている場合や、同じ文字が連続して配置されている文書画像の場合には、正確に罫線を抽出することは困難であった。
そこで、本発明では、容易かつ正確に罫線を抽出する方法を提供することを課題とする。
【０００８】
【課題を解決するための手段】
前記した課題を解決するため、本発明の請求項１では、文字と罫線が混ざった文書画像から罫線を抽出する方法であって、２値化した文書の画像を取得するステップと、連結画素を認識するステップと、連結画素の周囲長を求めるステップと、周囲長がしきい値より大きい連結画素を罫線と判断するステップとを含むことを特徴とする。
【０００９】
このような方法によれば、２値化した画像における、連結画素、つまりひとかたまりと認識される部分の周囲長の長さがしきい値より大きいかどうかにより、罫線とそれ以外の要素を区別することができる。ここでの周囲長とは、連結画素の輪郭をたどる一周の長さであり、例えば輪郭を構成する画素の数で求められる。
【００１０】
また、請求項２の発明では、前記しきい値の決定に際し、前記文書画像中の連結画素を記憶するステップと、前記記憶した各連結画素について、前記周囲長を階級ごとに累積して度数を得るステップと、前記周囲長と前記度数を座標軸とした直交座標上において、最も小さい周囲長の階級にある点と最も大きい周囲長の階級にある点を結ぶ直線から最も離れた連結画素の点である極大点を求めるステップと、前記極大点の周囲長を前記しきい値として設定するステップとを含んで決定することを特徴とする。
【００１１】
このように、周囲長を階級ごとに累積して度数を数え、周囲長と度数の関係を直交座標上に作ると、文字等は、小さい周囲長で高い度数存在する一方で、罫線は、大きい周囲長で、低い度数しか存在しない。そのため、周囲長が小さい部分では高い度数があるが、ある周囲長から極端に度数が低くなり、前記関係のグラフを作ると、ある周囲長で急激に曲がる曲線となる。そして、この曲線が急激に曲がる点を求めるため、最も小さい周囲長の階級にある点と最も大きい周囲長の階級にある点を結ぶ直線から最も離れた点（本明細書において、これを「極大点」とする。）を求める。この極大点をしきい値として設定すれば、このしきい値より大きい周囲長を有する連結画素のみを選択して、罫線を抽出できることになる。
ここで、階級といっているのは、直交座標上にプロットできる点は、周囲長について連続しているものではなく、とびとびに存在しているためである。そして、前記した極大点の周囲長をしきい値とするということは、実際に罫線として選択される連結画素は、前記しきい値の次の階級の周囲長を有するものとなる。
【００１２】
また、請求項３に記載の発明では、請求項１又は請求項２に記載の罫線の抽出方法により抽出した罫線画像を符号化する方法であって、前記罫線画像から、罫線が交差する節点位置を認識するステップと、前記節点位置において、その節点が、表構造のうちの右上、左上、右下、または左下のそれぞれの角部になりうるかを判定するステップと、前記右上、左上、右下、または左下のそれぞれの角部になりうるかの組合せに対し１対１に節点番号を対応させたテーブルを参照し、前記節点に節点番号を割り当てるステップとを含むことを特徴とする。
このように、罫線を抽出した画像から罫線の節点位置を求めることで、罫線と文字が混ざっている状態から直接節点位置を求めるよりも、正確に節点位置を求めることができる。そして、各節点について、右上、左上、右下、または左下のそれぞれの角部になりうるかの組合せから、１対１に節点番号を対応させたテーブルを用いることで、この節点になりうるかの判断のみで、節点番号を割り振ることができる。なお、これらの発明では、コンピュータにより各ステップを実行する。
【００１３】
また、本発明の請求項４では、文字と罫線が混ざった文書画像から罫線を抽出するための罫線抽出プログラムであって、コンピュータを、２値化した文書の画像を入力する手段と、連結画素を認識する手段と、連結画素の周囲長を求める手段と、周囲長がしきい値より大きい連結画素を罫線と判断する手段として機能させることを特徴とする。
【００１４】
【発明の実施の形態】
次に、適宜図面を参照しながら本発明の実施形態について説明する。
参照する図面において、図１は、実施形態に係る罫線の抽出方法および符号化方法を実行するシステム（以下、「罫線抽出符号化装置」という）の構成図であり、図２は、実施形態に係る罫線の抽出方法および符号化方法の処理の概略を示すフローチャートであり、図３は、実施形態に係る罫線抽出符号化装置の機能ブロック図である。
【００１５】
図１に示すように、罫線抽出符号化装置１は、中央処理装置（ＣＰＵ）１１、入力装置としてのキーボード１３ならびにマウス１４、出力装置としてのディスプレイ１６、および記憶装置１５を備えた一般的なコンピュータに、罫線を含む文書Ｄをデジタル画像（以下、単に「画像」という）として読み込むスキャナ１２が接続されて構成されている。記憶装置１５には、後記する各機能を実現するコンピュータプログラムが記憶され、適宜ＣＰＵ１１にロードされて実行される。
【００１６】
図２を参照して、実施形態に係る罫線の抽出方法および符号化方法の概略を説明する。まず、スキャナ１２を使用して、文書Ｄを２値化した画像として取得する（Ｓ１）。そして、取得した画像中から一つにつながった連結画素を認識する（Ｓ２）。次に、各連結画素について周囲の長さ（周囲長）を計算する（Ｓ３）。次に、周囲長の長さから、その連結画素が罫線かどうかを判定する（Ｓ４）。罫線は、文字に比較して周囲長が長いことから、あるしきい値より大きい場合には、罫線であると判定すればよい。そして、罫線から節点を見つけ出した上で、節点を符号化することで、罫線を符号化する（Ｓ５）。この際、図１３に示したような節点符号化テーブル２９を参照することにより符号化を行う。
【００１７】
次に、図３を参照しながら、罫線抽出符号化装置の詳細について説明する。
図３に示すように、罫線抽出符号化装置１は、文書画像入力部２１と、連結画素認識部２２と、周囲長演算部２３と、しきい値演算部２４と、罫線判定部２５と、節点認識部２６と、節点符号化部２７と、節点符号化テーブル２９とを有して構成されている。
【００１８】
文書画像入力部２１は、前記したスキャナ１２を作動させるソフトウェアとして構成される。文書画像入力部２１は、スキャナ１２から、２値化画像として文書Ｄを取り込み、記憶装置１５に記憶させる。カラー画像、モノクロの多階調の画像として画像を入力する場合には、画像を入力した後、２値化するように構成すればよい。
文書画像入力部２１で入力される画像は、例えば、図４（ａ）の原画像や、図６（ａ）の原画像のようになる。
【００１９】
連結画素認識部２２は、文書画像入力部２１で入力された文書Ｄの２値化画像から、一つながりの黒画素（連結画素）を認識する部分である。なお、黒地に白で文字や罫線を標記した文書を入力する場合には、白画素を認識するように構成すればよい。
連結画素の認識方法は、種々の方法をとることができる。
例えば、各画素にラベルを付けていく方法である。これは、注目画素の周囲（上のラインと左）の画素を参照し、その周囲の画素が黒であれば、注目画素に周囲の画素と同じラベルを付す方法で、この処理を画像の左上の画素から順に画像全体にわたって行えば、各連結画素にユニークなラベルを付すことができる。
【００２０】
周囲長演算部２３は、連結画素認識部２２で認識した各連結画素の周囲長を演算する。周囲長とは、連結画素の輪郭の長さであり、例えば、輪郭を構成する画素（例えば、上下左右の画素のうち少なくとも一つが自己の連結画素でない画素）の総数をカウントすることで求められる。もちろん、この方法に限られず、他の方法により周囲長を求めても良い。また、周囲長は、罫線の内側のように黒画素の内側に囲まれた白画素がある場合、この内縁の黒画素を周囲長としてカウントしても、しなくても良いが、周囲長としてカウントした方が、文字と罫線をより正確に区別できるので望ましい。
【００２１】
しきい値演算部２４は、周囲長演算部２３で求めた各連結画素の周囲長と、その周囲長を有する連結画素の度数との関係を作り、この関係から、罫線と文字を判別するためのしきい値を演算する部分である。周囲長は、取得した文書画像の分解能に応じ、適度な幅で階級にしておくと良い。例えば、周囲長を、連結画素の周囲を形成する画素数でカウントする場合、１０画素ごとや、５０画素ごと、１００画素ごとなどで階級を作り、各連結画素を、それらの階級に割り当てる。そして、各階級ごとに、その階級に相当する連結画素の数を累積して度数を得る。
周囲長と、度数の関係は、例えば、図５や図７のようになる。ここで、図５は、図４（ａ）の文書（原画像）の文書の連結画素について、横軸に階級（周囲長）、縦軸に階級ごとの度数をとってプロットしたものであり、図７は、図６（ａ）の文書（原画像）の連結画素について、横軸に階級（周囲長）、縦軸に階級ごとの度数をとってプロットしたものである。これらを見て分かるように、度数の分布は、低い階級（短い周囲長）で高い度数を示し、階級が高く（周囲長が長く）なるにつれ急激に度数が低くなり、最高階級まで、低い度数で分布する。これは、一般に、文字と罫線が混ざった文書画像では、文字の数は周囲長が短く、度数が非常に多いのに対し、罫線は周囲長が長く、度数が非常に少ないからである。
【００２２】
図５または図７のような周囲長と度数の関係から、罫線か否かを判定する階級のしきい値を求める方法について、図８を参照しながら説明する。図８は、図７に対応する周囲長と度数の関係から、しきい値を求める方法を説明する図である。
図８に示すように、もとの周囲長の階級の軸（横軸）をｘ軸とし、度数の軸（縦軸）をｙ軸とする。そして、最も小さい周囲長の階級の点（ｘ１，ｙ１）と、最も大きい周囲長の階級の点（ｘＮ，ｙＮ）を結ぶ直線を作成し、これをｘ’軸とする。次に、ｘ’軸に直交する方向（図８では、（ｘ１，ｙ１）から左下向きを正に引いている）にｙ’軸をとる。ｘ’ｙ’の座標系をＳ’系と呼ぶことにする。
そして、Ｓ’系において、各点のｙ’軸への投影が最も大きい点を極大点（ｘｍ’，ｙｍ’）とし、この階級の周囲長をしきい値ＴＨＣとする。
極大点（ｘｍ’，ｙｍ’）は、図８の点の分布から明らかなように、ｘ’軸から最も遠い点である。
【００２３】
罫線判定部２５は、しきい値演算部２４で求めたしきい値ＴＨＣに基づき、各連結画素が罫線か否かを判定する部分である。すなわち、連結画素ごとに、その連結画素の周囲長と前記しきい値ＴＨＣの大小を比較し、周囲長がしきい値ＴＨＣよりも大きければ罫線であると判定し、小さければ罫線ではないと判断する。
また、罫線判定部２５は、文書画像から、罫線以外の部分（連結画素）を消去した画像を生成する。このようにして罫線が抽出された画像は、例えば図４（ｂ）、図６（ｂ）のようになる。
【００２４】
節点認識部２６は、文書画像中の罫線の位置を特定して、節点位置を求める部分である。例えば、節点認識部２６では、文書画像の縦（ｙ軸）方向に並んだ画素のラインについて、黒画素の数をカウントし、これをすべてのｘ座標について行う。このカウントした黒画素の数（累積値）を図示すると、図９（ａ）、（ｃ）のようになる。なお、図９は、ｘ座標、ｙ座標ごとの黒画素の累積値を図示したグラフであり、（ａ）が文字消去前のｘ方向、（ｂ）が文字消去前のｙ方向、（ｃ）が文字消去後のｘ方向、（ｄ）が文字消去後のｙ方向である。図９（ａ）、（ｃ）に示すように、累積値は、ｘ座標で間歇的に高い値を示す。その累積値が高いｘ座標が、罫線の縦線が位置する座標になる。
同様に、文書画像の横（ｘ軸）方向に並んだ画素のラインについて、黒画素の数をカウントし、これをすべてのｙ座標について行う。これを図示すると、図９（ｂ）、（ｄ）のようになる。ｙ座標についても、高い累積値を示すｙ座標が、罫線の横線が位置する座標になる。
【００２５】
（罫線位置の特定）
この縦線のｘ座標、及び横線のｙ座標の認識の仕方については、種々考えられる。
例えば、図１０に示すように、ｘ軸上に連続した３つの注目点（ｋ−１，ｋ，ｋ＋１）をとり、それらを移動させながら、累積値の分布（輪郭）を追跡する。図９（ｃ）、（ｄ）から分かるように、罫線抽出処理をして、罫線以外の部分（連結画素）を消去した上で黒画素の累積値の計算をすると、罫線がある箇所以外は平らになっており、平らな部分と罫線との境界が検知しやすくなっている。
ｈ（ｋ）を座標ｋにおける黒画素の累積値の値とし、罫線部分とそれ以外の部分との累積値の差をしきい値ＴＨＲとすると、次式（１）〜（３）の３式を共に満足する位置（ｋ＋１）を罫線が始まる位置とする（図１０（ａ）参照）。
ｈ（ｋ＋１）−ｈ（ｋ）  ＞  ＴＨＲ・・・・・（１）
ｈ（ｋ＋１）−ｈ（ｋ−１）  ＞  ＴＨＲ・・・・・（２）
｜ｈ（ｋ）−ｈ（ｋ−１）｜  ＜  ＴＨＲ・・・・・（３）
罫線が始まる位置を特定した後に、次式（４）〜（６）を共に満たす位置（ｋ−１）を罫線の終わりを示す位置とする（図１０（ｂ）参照）。
ｈ（ｋ−１）−ｈ（ｋ）  ＞  ＴＨＲ・・・・・（４）
ｈ（ｋ−１）−ｈ（ｋ＋１）  ＞  ＴＨＲ・・・・・（５）
｜ｈ（ｋ＋１）−ｈ（ｋ）｜  ＜  ＴＨＲ・・・・・（６）
そして、節点の座標を一つに決める必要があるときには、これらの判定により求められた罫線の始まりの位置と終わりの位置の中央の位置（座標）などを罫線の座標とすればよい。
【００２６】
また、図９（ｃ）、（ｄ）のように、罫線の位置の累積値とそれ以外の累積値に顕著な差がでるので、累積値のしきい値ＴＨＲを設定して、しきい値ＴＨＲより累積値が大きい場合には、罫線の部分であると判定し、小さい場合には、罫線が位置する座標ではないと判定してもよい。この場合、しきい値ＴＨＲの設定方法としては、例えば、累積値の平均値の定数倍をしきい値ＴＨＲとして設定する等があげられる。そして、節点の座標を決める必要があるときは、隣接して罫線と判定された部分を１本の罫線と考え、隣接する座標群のうちから適当な座標、例えば、最も小さい座標や、中央の座標を罫線の座標とすればよい。
【００２７】
（節点位置）
そして、縦線が位置するｘ座標と、横線が位置するｙ座標のすべての組合せを作り、組み合わせたｘ、ｙ座標が節点の座標となる。たとえば、ｘ座標が、１０，２０，５０に縦線があり、ｙ座標が１００，１２０に横線があると判定された場合には、ｘ座標、ｙ座標のすべての組合せ、すなわち（１０，１００）、（１０，１２０）、（２０，１００）、（２０，１２０）、（５０，１００）、（５０，１２０）が節点の座標となる。
このようにして、節点位置を求めて、罫線と重ねて図示した例が図１１である。図１１（ａ）においては、節点の位置を○印で示している。なお、Ｅ．Ｒ．（Ｅｌｅｍｅｎｔ  Ｒｅｇｉｏｎ）は文字などが配置される要素領域を示す。図１１に示す例では、罫線として、５本の縦線と、５本の横線が認識された結果、各縦線のｘ座標と各横線のｙ座標を組み合わせた２５個の節点が認識されている。なお、図１１（ａ）に示す節点Ｎ４４のように、縦線及び横線のいずれも存在しない点も、線がない節点として認識される。
【００２８】
節点符号化部２７は、各節点が、要素領域の右上、左上、右下、または左下の角部になりうるかを、形状から判定（これを、「角位置判定」とする。）した後、各節点のなりうる角位置の組合せから、各節点を符号化する部分である。
【００２９】
（角位置判定）
角位置の判定は、例えば次のようにして行う。図１２は、角位置の判定方法を説明する図である。図１２（ａ）において、各マスは画素を示しており、斜線で塗りつぶした画素は黒画素を示している。図１２（ａ）では、横の罫線Ｒ１と縦の罫線Ｒ２が交差している。横の罫線Ｒ１は、座標ｙｓが罫線の始まりであり、座標ｙｅが罫線の終わりである。縦の罫線Ｒ２は、座標ｘｓが罫線の始まりであり、座標ｘｅが罫線の終わりである。
前記した節点位置の特定により、座標ｙｓ，ｙｅ，ｘｓ，ｘｅは特定されており、一つの節点の角位置判定については、この座標の周辺のみで行えばよい。
角位置の判定には、角１つにつき、次の第１〜第３の３ステップの処理がある。基本的な処理については、４種類の角（右上、左上、右下、左下）のすべてに共通しているので、ここでは節点が左上の角になりうるかどうかを判定する処理を例にして説明する。
【００３０】
［第１ステップ］
図１２（ａ）に太線で囲んで示した領域Ｄを設定する。領域Ｄは、縦横の罫線の太さ分に限定された領域を、右下に１画素（ｘ方向に１画素、ｙ方向に１画素）移動した領域である。
そして、要素領域の左上になりうる点を、領域Ｄから探す。つまり、次式（７）〜（９）を共に満たす点を探す。なお、０は白画素、１は黒画素であることを示す。
ｂ（ｘ，ｙ）＝０・・・・・（７）
ｂ（ｘ，ｙ−１）＝１・・・・・（８）
ｂ（ｘ−１，ｙ）＝１・・・・・（９）
これらの条件式を満たす点が存在すれば、その点を注目点Ｔ（ｘｔ，ｙｔ）とする。また、存在しなければ、その時点でその節点が左上の角位置を構成しない（なりえない）と判定する。
【００３１】
［第２ステップ］
罫線を構成する黒画素に沿って、注目点Ｔを所定数の画素数、例えば２００画素（ｐｉｘｅｌ）移動させる。注目点Ｔの移動は、進行方向右側に黒画素があるように行う。つまり、図１２（ａ）の下方向の矢印２のように、進行方向右側に黒画素が位置した状態で図中下方向に移動する。すると、図１２（ｂ）に示したような、逆Ｔ字型の節点であって、左上の角を構成しない場合には、注目点Ｔはｘ座標が小さくなる方向に進み、ｘｓに達してしまう。逆に、その節点が図中左上の角位置になりうるなら、注目点Ｔはｘ座標が大きくはなる（ｘｓから離れる）が、小さくはならないはずである。そこで、注目点Ｔのｘ座標がｘｓに達した場合には、その節点は左上の角位置を構成し、ｘｓに達しない場合には、その節点は左上の角位置を構成すると判定する。
第１ステップのみでは、図１２（ｂ）のように、逆Ｔ字型の節点において縦の罫線が横の罫線を一部はみ出した場合でも、左上の角位置を構成するという条件を満たしてしまうが、本ステップにより、このような節点が左上の角位置を構成しないと正しく判定できる。
【００３２】
［第３ステップ］
注目点Ｔを初期の座標（ｘｔ，ｙｔ）に戻し、罫線を構成する黒画素に沿って、注目点を所定数の画素数、例えば２００画素移動させる。この場合は、進行方向左側に黒画素があるように行う。例えば図１２（ａ）では、図中右向きの矢印３のように、進行方向左側に黒画素が位置した状態で右方向へ進行する。前記した第２ステップと同様に、もし、その節点が左上の角位置になりうるなら、注目点Ｔはｙ座標が大きくはなる（ｙｓから離れる）が、小さくはならないはずである。そこで、この移動の際、注目点のｙ座標がｙｓに達した場合には、その節点が左上の角位置を構成しないと判定される。この移動を最後まで終了した場合には、その節点が左上の構成要素であると判定する。
【００３３】
以上の第１〜第３ステップの処理を、右上、右下、及び左下の角位置についても行い、角位置になりうるか否かの判定結果を記憶装置１５に記憶する。そして、以上の処理をすべての節点について行う。
【００３４】
（符号化）
角位置判定ができたならば、図１３の節点符号化テーブルを参照して、角位置になりうるかどうかの値（○又は×）から、各節点に節点番号を割り当てる。
図１３の節点符号化テーブル２９は、占有する要素領域の角位置（左上、右上、左下、右下）の組合せについて、それぞれ１つの節点番号が関係づけられている。例えば、図１３の２行目のように、左上の角位置のみ構成する節点は、節点番号ｎ１が関係づけられている。
この節点符号化テーブルにしたがって節点を節点番号に置き換えると、図１１（ｂ）のような行列（これを、「節点行列」という）とすることができる。図１１（ｂ）は、図１１（ａ）の表構造の各節点を図１３の節点符号化テーブルにしたがって符号化したものである。
図１３の節点番号はｎ０からｎ９の１０種類であるから、それぞれ０から９の１桁の数字であらわせば、図１１（ｃ）のように符号化することもできる。すなわち、１節点あたり１文字の数字でテキスト表現することができ、コンピュータプログラム言語内で、表を符合として取り扱うときに簡便である。
【００３５】
（符号化の後処理）
節点符号化部２７は、節点を符号化した後、冗長なデータ部分を削除して、表以外の部分を除いた圧縮されたデータとする。例えば、図１４（ａ）に示すような表Ｔ１と、下線Ｕ１が抽出された画像で節点行列を求めると、図１４（ｂ）のようになる。図１４（ｂ）では、下線Ｕ１の部分が、非節点（ｎ０）と認識されて、１行目がすべてｎ０（図では、強調するため大文字のＮ０で表現している）となる。このように、一行または一列の全体にわたって非節点（ｎ０）が連続している場合には、その行または列を削除することにより、データ量を低減することができる。行を削除した後のデータは、図１４（ｃ）のようになる。
なお、この後処理を行うかどうかは、本発明では任意である。
【００３６】
以上のような罫線抽出符号化装置１の動作について、図１５のフローチャートを参照しながら説明する。
まず、文書画像入力部２１が、文書Ｄをスキャナ１２で画像として取り込み、２値化する（Ｓ１１）。例えば、図４（ａ）、図６（ａ）のような画像を入力する。そして、連結画素認識部２２が、２値化画像中の連結画素を認識する（Ｓ１２）。次に、周囲長演算部２３は、各連結画素について周囲長を計算する（Ｓ１３）。この周囲長に基づいて、しきい値演算部２４は、周囲長と、その周囲長を有する連結画素の度数を、階級に分けて関係づける（Ｓ１４）。これを図示すると、例えば、図５や、図７のようなグラフになる。この関係（グラフ）において、最小階級と最大階級の点を直線で結び（Ｓ１５）、この直線から最も離れた点（階級）を探して、その周囲長をしきい値ＴＨＣとする（Ｓ１６）。
そして、罫線判定部２５は、各連結画素の周囲長と、しきい値ＴＨＣを比較して、それぞれの連結画素が罫線か否かを判定する（Ｓ１７）。さらに、罫線でないと判定された連結画素を、元の文書画像から消去して（Ｓ１８）、新たな画像を生成する（図４（ｂ）、図６（ｂ）参照）。
次に、節点認識部２６は、罫線判定部２５が生成した新たな画像について、ｘ座標、ｙ座標ごとに黒画素の累積値を求める（Ｓ１９）。例えば、図９（ｃ）、（ｄ）のような累積値の分布が得られる。そして、累積値の分布を追跡して節点の位置を求める。つまり、注目座標の累積値と、隣の座標の累積値とを比較して、しきい値ＴＨＲより大きいか否か（前記式（１）〜（６）参照）で、罫線の存在の有無及び位置を判断する（Ｓ２０）。
そして、節点符号化部２７は、各節点位置において、その節点が、要素領域（表構造）の右上、左上、右下、または左下の角位置を構成できるかを判定する（Ｓ２１）。この判定の際には、隣接画素との関係のみで、（［第１ステップ］）その角位置になれるかの判断と、罫線（黒画素）に沿って移動させていった場合にも、罫線があるｘ座標またはｙ座標を跨がないか（［第２ステップ］［第３ステップ］）により、要素座標の角位置を構成できるかどうかを判断する。
最後に、節点符号化部２７は、節点符号化テーブル２９を参照して、角位置の組合せから各節点を符合（ｎ０〜ｎ９）へ変換する（Ｓ２２）。
【００３７】
以上のような実施形態によれば、次のような効果がある。
まず、罫線の位置を認識するのに、連結画素と周囲長の関係を作り、この関係において、直線と点の距離を求め、この距離が最も遠い点をしきい値ＴＨＣとし、罫線の判定をするという、簡単な処理により罫線を判定できるので、処理速度を早くすることができる。
そして、罫線を抽出した後の画像から、罫線の位置（節点の位置）を求めるので、罫線の抽出ミスを少なくすることができる。
また、節点が、右上、左上、右下、または左下のいずれの角位置を構成しうるかの組合せに対し、１対１に対応させた節点符号化テーブルを参照して、前記組合せから節点番号を割り当てて符号化するので、極めて簡単に罫線を符号化することができる。さらに、後処理として、非節点の行または列を削除することで、不要なデータを捨てて、データ量を低減することができる。
また、本発明の節点符号化テーブルでは、１０通りの節点で整理してあるので、各節点モデルに０から９の数字を節点番号として割り当てることで、コンピュータプログラム上での表構造の取り扱いが簡便となる。
【００３８】
なお、本発明は、罫線の抽出・符号化方法及び罫線抽出プログラムであるので詳しくは説明しないが、符号化した罫線のデータは、前記した罫線符号化テーブルを利用して、節点番号から節点モデルを求め、節点モデルの直線を延長するように繋いでいくことで罫線（表構造）を再現することができる。
【００３９】
【発明の効果】
以上詳述した通り、本発明では、罫線を少ない処理、データ量で簡単に抽出し、符号化することができる。
【図面の簡単な説明】
【図１】実施形態に係る罫線抽出符号化装置の構成図である。
【図２】実施形態に係る罫線の抽出方法および符号化方法の処理の概略を示すフローチャートである。
【図３】実施形態に係る罫線抽出符号化装置の機能ブロック図である。
【図４】入力される画像の例であり、（ａ）が原画像、（ｂ）が罫線抽出後を示す。
【図５】図４の例における周囲長と度数の関係を示すグラフである。
【図６】入力される画像の例であり、（ａ）が原画像、（ｂ）が罫線抽出後を示す。
【図７】図６の例における周囲長と度数の関係を示すグラフである。
【図８】図７に対応する周囲長と度数の関係から、しきい値を求める方法を説明する図である。
【図９】ｘ座標、ｙ座標ごとの黒画素の累積値を図示したグラフであり、（ａ）が文字消去前のｘ方向、（ｂ）が文字消去前のｙ方向、（ｃ）が文字消去後のｘ方向、（ｄ）が文字消去後のｙ方向である。
【図１０】（ａ）は、罫線が始まる位置の探索、（ｂ）は、罫線が終わる位置の探索を説明する図である。
【図１１】（ａ）は、抽出された罫線と節点を重ねて示した図であり、（ｂ）は、（ａ）の罫線を符号化した行列、（ｃ）は、（ｂ）の添え字を使用して数値化した行列を示す。
【図１２】罫線の角位置の判定方法を説明する図であり、（ａ）が十字の節点の場合、（ｂ）が逆Ｔ字の節点の場合である。
【図１３】節点符号化テーブルである。
【図１４】符号化の後処理を説明する図であり、（ａ）が罫線抽出後の画像、（ｂ）が符号化後の行列、（ｃ）が後処理後の行列を示す。
【図１５】実施形態に係る罫線抽出符号化装置の動作を示すフローチャートである。
【符号の説明】
１１    ＣＰＵ
１２    スキャナ
１５    記憶装置
２１    文書画像入力手段
２２    連結画素認識部
２３    周囲長演算部
２４    しきい値演算部
２５    罫線判定部
２６    節点認識部
２７    節点符号化部
２９    節点符号化テーブル
【図１】
2004334743.tif 000003
【図２】
2004334743.tif 000004
【図３】
2004334743.tif 000005
【図４】
2004334743.tif 000006
【図５】
2004334743.tif 000007
【図６】
2004334743.tif 000008
【図７】
2004334743.tif 000009
【図８】
2004334743.tif 000010
【図９】
2004334743.tif 000011
【図１０】
2004334743.tif 000012
【図１１】
2004334743.tif 000013
【図１２】
2004334743.tif 000014
【図１３】
2004334743.tif 000015
【図１４】
2004334743.tif 000016
【図１５】
2004334743.tif 000017