(57)【特許請求の範囲】
【請求項１】
枠線を含む２値画像を入力する入力手段と、前記２値画像のエッジに方向コードを付与し、方向コードが変化する点を枠線のコーナーとして方向コードの変化を示す特徴コードとその座標をコーナー特徴点として抽出するコーナー検出手段と、近傍の前記コーナー特徴点の組合せから枠の構成要素を抽出する構成要素抽出手段と、前記構成要素を連結し最小矩形の矩形情報を出力する最小矩形認識手段と、前記最小矩形認識手段からの矩形情報に基づいて枠線の構造を認識する構造認識手段と、前記構造認識手段からの枠線の構造から文字領域を切り出す文字切り出し手段とを具備する枠線認識装置。
【請求項２】
コーナー検出手段のコーナー特徴点は、前記方向コードの変化を示す特徴コードを組み合わせて８種類のコーナー形状に分類することを特徴とする請求項１記載の枠線認識装置。
【請求項３】
前記構成要素は、Ｌ字、Ｔ字または十字の構成要素であることを特徴とする請求項１記載の枠線認識装置。
【請求項４】
前記構成要素抽出手段は、前記コーナー特徴点の座標を中心として、コーナー特徴点の特徴コードに対応した領域を探索することを特徴とする請求項３記載の枠線認識装置。
【請求項５】
前記最小矩形認識手段は、前記抽出された構成要素の内任意の構成要素を始点として、始点の構成要素の接手の方向に仮のリンク線をたどり、時計回りまたは反時計回りに連結する接手を持つ構成要素の探索を繰り返し、一巡する事によって連結された構成要素の組合せを最小矩形とすることを特徴とする請求項１記載の枠線認識装置。
【請求項６】
前記最小矩形認識手段は、前記構成要素を始点として、前記構成要素の接手の方向を任意の範囲で検索し、連結する接手を持つ構成要素を検出すれば、最小矩形を構成する構成要素として登録し、その構成要素を基準にして90度毎に接手の方向を時計回りまたは反時計回りに探索することを繰り返し、始点に戻ることによって、最小矩形を構成すること特徴とする請求項５記載の枠線認識装置。
【請求項７】
前記最小矩形認識手段は、基準とした構成要素において90度方向の回転した接手の有無を検査して、接手が存在すれば、その接手の方向を任意の範囲で検索して、次に基準となる構成要素を検出する処理を始点の構成要素に戻るまで繰り返すことを特徴とする請求項５記載の枠線認識装置。
【請求項８】
前記最小矩形認識手段は、基準とした構成要素において90度方向の回転
した接手の有無を検査して、接手が存在しないか、あるいは、その接手の方向を任意の範囲で検索しても、連結する接手を持つ構成要素が検出できない場合には、前記構成要素の９０度逆方向の接手の有無を検査し、前記９０度逆方向の接手が存在すれば、その接手の方向で任意の範囲に構成要素を探索し、存在しない場合には前記構成要素を最小矩形と登録しないことを特徴とする請求項５記載の枠線認識装置。
【請求項９】
前記最小矩形認識手段は、構成要素の接手の方向を任意の範囲で検索した場合、連結する接手を持つ構成要素が検出できなく、かつ前記構成要素が反時計回りまたは時計回りの方向に接手を持っていない場合には、それらの構成要素を最小矩形として登録しないこと特徴とする請求項５記載の枠線認識装置。
【請求項１０】
前記最小矩形認識手段は、探索領域として構成要素の接手の方向に予め設定した傾きと長さを持つ三角形領域であることを特徴とする請求項５乃至８のいずれかに記載の枠線認識装置。
【請求項１１】
構造認識手段は、前記最小矩形認識手段からの矩形情報に基づいて、予め帳票の矩形情報を登録した基準フォーマットと照合し、枠線の構造を認識することを特徴とする請求項１記載の枠線認識装置。
【請求項１２】
前記文字切り出し手段は、枠線の角の４点で囲まれた長方形領域から一定のオフセット分内側の領域を文字領域として切り出すことを特徴とする請求項１記載の枠線認識装置。
【請求項１３】
枠線を含む２値画像を入力し、前記２値画像のエッジに方向コードを付与し、方向コードが変化する点を枠線のコーナーとして方向コードの変化を示す特徴コードとその座標をコーナー特徴点として抽出し、近傍の前記コーナー特徴点の組合せから枠の構成要素を抽出して、前記構成要素から最小矩形を認識して矩形情報を出力し、前記矩形情報から文字領域を切り出す文字切り出すことを特徴とする枠線認識方法。
【請求項１４】
コーナー特徴点の検出は、前記方向コードの変化を示す特徴コードを組み合わせて８種類のコーナー形状に分類することを特徴とすることを特徴とする請求項１３記載の枠線認識方法。
【請求項１５】
前記構成要素は、Ｌ字、Ｔ字または十字の構成要素であることを特徴とする請求項１３記載の枠線認識方法。
【請求項１６】
前記最小矩形の認識は、前記抽出された構成要素の内任意の構成要素を始点として、始点の構成要素の接手の方向に仮のリンク線をたどり、時計回りまたは反時計回りに連結する接手を持つ構成要素の探索を繰り返し、一巡する事によって連結された構成要素の組合せを最小矩形とすることを特徴とする請求項１３乃至１５のいずれかに記載の枠線認識方法。
【請求項１７】
構造認識は、前記矩形情報に基づいて、予め帳票の矩形情報を登録した基準フォーマットと照合し、枠線の構造を認識することを特徴とする請求項１３記載の枠線認識方法。
【請求項１８】
前記文字切り出しは、枠線の角の４点で囲まれた長方形領域から一定のオフセット分内側の領域を文字領域として切り出すことを特徴とする請求項１３記載の枠線認識方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、帳票のような枠線と文字を含む画像の枠線の構造を自動的に認識し、帳票内に記入されている文字領域を切り出し、文字を自動認識するための前処理装置である枠線認識装置に関するものである。
【０００２】
【従来の技術】
近年、文書情報の電子化に伴い、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）を初めとする文字認識技術や文書画像処理に対する要望が高まっており、帳票の枠線構造の認識もそのひとつである。
【０００３】
帳票の枠線認識として、枠線のラン長で線分を検出する方法が良く知られており例えば特開平０１−２１７５８３号公報であり、その実施例を第２２図を基に説明する。画像入力部１００１は認識対象罫線を含む画像を走査し２値信号で画像メモリ１００２に格納する。縦方向ラン抽出部１００３は画像メモリ１００２に格納されている画像を縦方向に走査して縦方向ランを抽出する。抽出された縦方向のランの連結性が縦方向線分抽出部１００４で調べられ縦方向線分が抽出される。同様の処理により横方向ラン抽出部１００５で横方向ランが抽出され、横方向線分抽出部１００６で横方向線が分抽出される。文字領域抽出部１００７は縦方向線分抽出部１００４で抽出された縦方向線分と横方向線分抽出部１００６で抽出された横方向線分を用いて文字領域および文字記入領域を抽出する。
【０００４】
また、切り出された文字認識については、各種方式が提案されており例えば、ニューラルネットを用いた文字認識法（森：”ＰＤＰモデルによる手書き漢字認識”、電子情報通信学会論文誌、Ｖｏｌ．Ｊ７３−Ｄ−ＩＩ，  Ｎｏ．８  ｐｐ．１２６８−１２７４  １９９０）があり、認識率も実用的なところまできているが、今回は帳票の枠線認識装置ということで文字認識の前処理に限定しているので文字認識に関しては省略するものとする。
【０００５】
【発明が解決しようとする課題】
しかしながら前記の従来の構成では、枠線（罫線を以後枠線と呼ぶ）が細い場合や帳票が傾いて画像として読み取られた場合は、ラン長で枠線を認識することが難しく、検出するラン長を短く設定すると枠線以外の線分が抽出され誤検出するという課題がある。
【０００６】
本願発明は、前記従来技術の課題を解決するもので、特に枠線が細い場合や帳票が傾いて読み取られた場合に対して正確で信頼性の高い枠線認識装置を提供することを目的とする。
【０００７】
【課題を解決するための手段】
この目的を達成するために本発明は、例えば帳票から自動的に枠線を認識し文字領域を切り出す際に、帳票を読み取り２値画像を出力するイメージスキャナーと、前記イメージスキャナーからの２値画像（文字、枠線を”０”、その他を”１”）から帳票の枠線のエッジに方向コードを付与し、その方向コードの変化する点を画像のコーナーとし、その特徴コードと座標をコーナー特徴点として抽出するコーナー検出手段と、近傍の前記コーナー特徴点の組合せから（Ｔ字、十字およびＬ字等の）枠線の構成要素を抽出する構成要素抽出手段と、前記構成要素抽出手段からの構成要素をもとに、注目構成要素を基準に右回り（あるいは左）に周辺の構成要素を検索し相手となる構成要素を連結し元に戻るまで繰り返し最小矩形を認識し矩形情報を出力する最小矩形認識手段と、前記最小矩形認識手段からの矩形情報の任意の角を基準とした連結する最小矩形を認識する構造認識手段と、前記構造認識手段からの枠線の構造から文字領域を切り出す文字切り出し手段とを設けたものである。
【０００８】
【作用】
本発明は前記構成によって、帳票の２値画像から枠のコーナー点を抽出し、コーナー点から枠線の構成要素を抽出し、相互に連結された構成要素から帳票の最小矩形を認識することにより、帳票の枠線が細い場合や帳票が傾いて読み取られた場合においても信頼性の高い枠線認識装置を実現できる。
【０００９】
【実施例】
以下、本発明の一実施例について、図面を参照しながら説明する。
【００１０】
図１は本発明の一実施例における枠線認識装置のブロック構成図である。１０１は帳票を読み取り２値画像を出力するイメージスキャナー、１０２は枠線の輪郭に方向コードを付与しその変化点をコーナー特徴点として出力するコーナー検出手段、１０３は注目コーナー特徴点とその周辺コーナー特徴点から枠線の構成要素を抽出する構成要素抽出手段、１０４は枠線の構成要素から最小矩形を構成するように構成要素を連結して最小矩形を認識する最小矩形認識手段、１０５は各最小矩形から木構造を生成し枠線の構造を認識する構造認識手段、１０６は枠線の構造から文字領域を切り出す文字切り出し手段である。
【００１１】
以上のように構成された枠線認識装置について、その動作を説明する。
イメージスキャナー１０１により、帳票を読み取り２値画像に変換し、その２値画像からコーナー検出手段１０２により、帳票の枠線の輪郭に方向コードを付与してその変化点をコーナー特徴点として出力し、構成要素抽出手段１０３により、注目コーナー特徴点とその周辺コーナー特徴点から枠線の構成要素を抽出し、その構成要素から最小矩形認識手段１０４により、最小矩形を認識して出力し、各最小矩形から構造認識手段１０５により、連結する矩形の木構造を生成して枠線の構造を認識し、その枠線の構造から文字切り出し手段１０６により、文字領域を切り出して、枠線を認識するものである。
【００１２】
次に各構成要素の動作を詳細に説明する。帳票を読み取り２値画像を出力するイメージスキャナー１０１は、線密度を約４００ｄｐｉ程度とし、原稿である帳票にＬＥＤ（発光ダイオード）等で照明しその反射光を一次元のＣＣＤカメラで読み取り、任意の閾値で２値化して２値画像を出力するものである。また、照明は原稿である帳票の枠線や記入された文字の色によって異なるが、例えば青・黒および赤等の枠線に対して、黒や青等で数字や記号および文字が記入された場合、緑あるいは黄緑の波長（５５０〜５７０ｎｍ付近）のＬＥＤを用いることが多い。２値化処理においては、固定閾値法や浮動閾値法（森、大津：”認識問題としての二値化と各種方法の検討”、情報処理学会、イメージプロセッシング１５−１，  Ｎｏｖ．  １９７７）が良く知られている２値化処理法であり、原稿に合わせて任意の２値化処理法を選択すればよい。
【００１３】
次に、コーナー検出手段１０２について説明する。コーナー検出手段１０２は、枠線の輪郭に方向コードを付与しその変化点をコーナー特徴点として出力するもので、図２に詳細ブロック図を示し説明する。
【００１４】
図２において、２０１はスキャナー１０１からの２値画像１１０に８方向の方向コードを付与する方向コード付与手段、２０２は方向コードの変化する特徴点を検出し、方向コードの変化を表すコードおよび特徴点の座標をコーナー特徴点として抽出する特徴抽出手段を示す。本実施例においては、コーナー特徴点の検出方法として帳票の枠線の輪郭画素に方向コードを付与しその方向コードの変化点を検出することで、帳票の枠線のコーナーを検出するものである。方向コードを付与する方式は、フリーマンのチェインコード（Ｈ．Ｆｒｅｅｍａｎ：”Ｏｎｔｈｅ  ｅｎｃｏｄｉｎｇ  ｏｆ  ａｒｂｉｔｒａｒｙ  ｇｅｏｍｅｔｒｉｃｃｏｎｆｉｇｕｒａｔｉｏｎｓ”、ＩＲＥ  Ｔｒａｎｓ．Ｅｌｅｃｔｒｏｎ．Ｃｏｍｐｕｔ．ＥＣ−１０、１９６１、ｐｐ２６０−２６８）がよく知られている。
【００１５】
まず、方向コード付与手段２０１について、図３を用いて説明する。図３（ａ）は、方向コード付与手段２０１の回路構成図である。図３（ａ）において、２１１はラインメモリ、２１２は３×３の走査窓、２１３は走査窓２１２のビットパターンによって４ビットの方向コード画像２１４を出力するＬＵＴ（ルック・アップ・テーブル）を示す。方向コードは、図３（ｂ）に示す様に、注目画素２０３から周辺の輪郭画素に向かう８方向を、方向コードとしてそれぞれ”１”〜”８”の値で表すものである。方向コード付与手段２０１は、２値画像１０１に対し３×３走査窓２１２で走査し、走査窓内からのビットパターンでＬＵＴ２１３を用いて４ビットの方向コードを出力する。またここでは、方向コードは、”１”から”８”としたが、”０”から”７”の値でもかまわない。
【００１６】
ＬＵＴ２１３は、予め計算によってデータを作成しておくもので、条件（数１）を満たすパターンに対して条件（数２）を満たす方向コードｉを算出するもので、本実施例では右回り方向に方向コードを付与するものとする。ただし、条件（数３）を満たす例えば一画素幅の特殊なパターンに対しては値”ａ”を付与し、文字領域内部には値”ｆ”、枠線部には値”０”をそれぞれ割り当てるものとする。
【００１７】
【数１】
0003586911.tif 000002
【００１８】
【数２】
0003586911.tif 000003
【００１９】
【数３】
0003586911.tif 000004
【００２０】
ここで、走査窓内の画素ｄ１〜ｄ８は、図３（ａ）の定義に従うものとする。なお、Ｎｃ（８）は８連結数、Ｎｃ（４）は４連結数と呼ばれ、パターンの連結性を示すパラメータとしてよく知られている。前記処理によって得られる方向コード画像の例を図４に示す。図４において、枠線２１５は”０”が割り当てられ、文字領域２１８のエッジに対して右回りに方向コード２１６が付与される。同様に、中央の文字２１７にも方向コードが付与される。
【００２１】
次に、特徴抽出手段２０２について図５を用いて説明する。図５は、特徴抽出手段の回路構成図である。図５において、２２０はラインメモリ、２２１は多値の３×３走査窓、２２２は走査窓２２１からのＤ０信号２３１に従って、Ｄ１〜Ｄ８の信号２３０の出力を選択するＭＰＸ（マルチプレクサ）、２２３はＭＰＸ２２２からの出力２２８およびＤ０信号２３１を参照し、帳票の枠線を示すためのコーナー特徴点を出力するＬＵＴを示す。本実施例においては、方向コードの変化する点を特徴点として抽出し、コーナーの形状を表す特徴コードとその座標をコーナー特徴点として通知するものである。以下に、特徴抽出手段２０２の動作について説明する。
【００２２】
まず、方向コード付与手段２０１からの方向コード画像２１４を、走査窓２２１に入力し一画素づつ走査する。
【００２３】
特徴抽出手段２０２は、走査窓２２１からのＤ１〜Ｄ８の方向コード信号２３０をそれぞれＭＰＸ２２２に入力し、注目画素位置Ｄ０の方向コード２３１が示す周辺の画素位置Ｄ１〜Ｄ８が選択される。注目画素Ｄ０の方向コード２３１と選択された周辺画素の方向コード２２８から、ＬＵＴ２２３により特徴コードＣｆと同期信号２２７からＸＹ座標発生器２２５で発生したＸＹ座標とからなるコーナー特徴点２２９が出力される。また、特殊コード判定部２２４では、周辺画素の方向コード２２８の値が特殊コードである”ａ”が付与されているかを判定し、判定された結果はＬＵＴ２２３に通知し特徴コードＣｆとして値”ａ”を通知するものとする。特徴コードＣｆは、予め（数４）で演算した結果をＬＵＴ２２３に登録しておくものである。
【００２４】
【数４】
0003586911.tif 000005
【００２５】
ただし、Ｄｉは、方向コードＤ０が示す方向に隣接している画素の方向コードである。図６に特徴コードの例を示す。図６（ａ）は特徴コード値が”３１”の例、同図（ｂ）は特徴コード値が”１７”の例、同図（ｃ）は特徴コード値が”７５”の例、同図（ｄ）は特徴コード値が”５３”の例、同図（ｅ）は特徴コード値が”５６”の例、同図（ｆ）は特徴コード値が”６１”の例をそれぞれ示すものである。なお本実施例では、右回り方向に方向コードを付与したが、左回りに付与してもよい。
【００２６】
次に、構成要素抽出手段１０３、最小矩形認識手段１０４、構造認識手段１０５および文字切り出し手段１０６について説明するが、これらの具体的な処理は基本的にはソフトウエア処理が主体となるために共通な回路構成を図７に示し以下に説明する。図７において、１１１はコーナー検出手段１０２からのコーナー特徴点を入力するＦＩＦＯ（ファースト・イン・ファースト・アウト）メモリ、１１２および１１３は各ソフトウエア処理を行うためのＣＰＵとワークメモリ、１０７はスキャナー１０１からのデータを記憶するイメージメモリ、１１４はＦＩＦＯ１１１及びイメージメモリ１０７のデータをＣＰＵ１１２とワークメモリ１１３に送るＩ／Ｆ回路である。１１５および１１６は今回は詳しくは触れないが文字部を切り出した後に文字認識部にデータを送るＩ／Ｆ回路および文字認識装置を示す。
まず、コーナー検出手段１０２で検出されたコーナー特徴点はＦＩＦＯメモリ１１１に入力され、逐次ＣＰＵ１１２に読み込まれ一旦ワークメモリ１１３に記憶される。また、イメージメモリ１０７に記憶されたデータは、最後に文字の切り出し位置が確定した時点で文字領域が切り出されＩ／Ｆ１１５を介して今回は説明を省略した文字認識装置に送られ文字の認識が行われる。
【００２７】
次に、構成要素抽出手段１０３について説明する。構成要素抽出手段１０３の処理の概念図を図８に示し説明する。図８において、２４５〜２４６はコーナー検出手段１０２からコーナー特徴点をＦＩＦＯメモリ１１１を介して得られたコーナー特徴点、２４４はコーナー特徴点の探索領域、２４１〜２４３は得られた構成要素を示す。まず発生順に得られたコーナー特徴点２４５を注目特徴点とした場合、コーナー特徴点２４５を中心に探索領域２４４内に対応するコーナー特徴点があるかどうかを探索する。例えば、Ｌ字の構成要素は図９（ａ）〜（ｄ）に示す４種類、Ｔ字の構成要素は図９（ｅ）〜（ｈ）の４種類、十字の構成要素は１種類の組み合わせが存在する。このように枠線は、Ｌ字・Ｔ字および十字が組合わさって構成されており構成要素と構成要素とを接続することで枠線の骨格が構成できる。
構成要素抽出手段１０３の具体的な処理手順を図１０に参照しながら説明する。
（１）コーナー特徴点をワークメモリ１１３から入力する。
（２）対象のコーナー特徴点が９０゜のコーナー特徴点かどうかをチェックし、９０゜コーナー特徴点ならそのまま（４）のステップへ、それ以外なら（３）のステップに進む。
（３）注目のコーナー特徴点の上位桁を始点として、任意の連結許容範囲Ｓｒ内で、かつ、図１１（ａ）に示す探索範囲内に存在して、さらにコーナー特徴点が図１１（ｂ）に示す終点コーナー特徴点であれば、その特徴点を終点として連結して９０゜コーナー特徴点とする。
（４）連結した９０゜コーナー特徴点を図１１（ｂ）に示す参照コードに変換してワークメモリに記憶する。
（５）ワークメモリの全てのコーナー特徴点について、前記の処理が終了すれば（６）に進み、そうでない場合は（１）に進む。
（６）ワークメモリの中の９０゜コーナー特徴点を対象点とする。対象点の参照コードＣｒを入力する。
（７）（数５）の式を満たす参照コードＣｐを持つ相手が、（数６）で表現される探索範囲に存在すれば、対象点はＬ字構成要素にグルーピングされるものとして（１０）に進み、存在しなければ（８）に進む。ここで、例として、対象点２５５の参照コードＣｒ＝２の場合の探索範囲２５６を図１２（ａ）に示す。
【００２８】
【数５】
0003586911.tif 000006
【００２９】
【数６】
0003586911.tif 000007
【００３０】
ただし、グルーピング許容範囲：Ｇｒ、対象点座標：ｘｒ，ｙｒ、相手座標：ｘｐ，ｙｐ、対象点の参照コードＣｒとする。
（８）図１２（ｂ）のように、対象点２５７を中心にして水平または垂直方向に伸びたＧｒ×２ｗの長方形探索領域２５８の中に存在する相手の参照コードが、（数７）また（数８）の条件を満たすかどうか調べる。
【００３１】
【数７】
0003586911.tif 000008
【００３２】
ただし、対象点の参照コードＣｒ＝４のときは、相手の参照コードＣｐ＝１とする。
【００３３】
【数８】
0003586911.tif 000009
【００３４】
ただし、対象点の参照コードＣｒ＝１のときは、相手の参照コードＣｐ＝４とする。
（９）（数７）かまたは（数８）のどちらかを満たす場合には、Ｔ字構成要素と判断し、また、（数７）と（数８）のどちらをも満たす場合には、十字構成要素と判断して（１０）に進む。何れの条件も満たさない場合は（１１）に進む。
（１０）Ｌ字、Ｔ字および十字構成要素として認識された参照コードをグルーピングし図１２（ｃ）に示す要素コードデータに変換すると共に参照コードとグルーピングされた相手との平均座標を演算しワークメモリに記憶する。ただし、図１２（ｃ）における、Ｅ方向、Ｎ方向、Ｗ方向及びＳ方向はそれぞれ図１２（ｄ）に示す方向を表す。
（１１）（９）の処理で何れの条件にも満たない参照コードは消去する。
（１２）コーナー特徴点が全てグルーピングされた場合は処理を終了し、そうでない場合は（６）に進む。
以上の処理を行うことにより、図１３に示す枠線のＬ、Ｔ、十字の各構成要素が抽出される。ただし、図１３は、抽出された各構成要素（要素コード＋平均座標データ）を枠線上に展開したものを示している。
【００３５】
次に最小矩形認識手段１０４について説明する。最小矩形認識手段１０４は、枠線の構成要素を連結して最小矩形を認識するするもので、処理の概念を図１４を用いて説明する。図１４（ａ）は、最小矩形認識手段１０４の処理の概念を示すもので、各構成要素同士の手を連結させリンク線２６４（破線で示す）を仮想的に張り、最小矩形の始点２６５を矩形の左上として右回りにリンク線２６４をたどって元の始点に戻れば最小矩形２６７と認識したものとする。
最小矩形認識手段１０４の処理を、図１５および図１６に示した処理フローに従って詳細に説明する。最小矩形認識手段１０４の処理は大きく２つの処理から構成されており、各構成要素を連結する処理と連結したリンク線をたどって矩形を認識する処理である。図１５に各構成要素を連結する処理フローを示し以下に説明する。
（１）構成要素データをワークメモリに読み込む。
（２）構成要素データの中から連結されていない対象点を順次選択する。
（３）対象点にまだ連結していない”手”がある場合、その手の伸びている方向を探索範囲として、図１４（ｂ）に示すような帳票の読み取り時の傾きと位置ずれを考慮した三角形探索領域２６９内で連結する相手を探す。この時、図１４（ｃ）に示すように対象点２７１の手２７３に対して逆方向の手２７４を持つ最短距離の相手２７２を探索する。
（４）前記条件を満たす相手が存在するかどうか判定し、ある場合は（５）へ進み、ない場合は（２）へ進む。
（５）対象点の手と相手の手を仮想的に連結し、記憶する。
（６）構成要素データに未連結の構成要素の有無をチェックし、Ｙの場合は（２）      へＮの場合は（７）に進む。
（７）次の矩形認識処理に進む。
図１６に矩形認識処理の処理フローを示し、以下に説明する。基本的には、始点からＥ→Ｓ→Ｗ→Ｎと右回りにリンク線をたどり、行き止まりになれば前の要素に戻り新しい候補を選択して探索を繰り返し、最後に始点に戻ることのできる構成要素の集まりを最小矩形と認識するものである。
（８）連結された構成要素からＥ方向とＳ方向の手を持つ構成要素を探索し始点とする。まずその始点を対象点とする。
（９）対象点のＥ方向にリンク線で構成要素が連結しているがどうか調べ、Ｎなら（８）へＹなら（１０）に進む。
（１０）連結しているＥ方向の構成要素を対象点にする。
（１１）対象点のＳ方向にリンク線で構成要素が連結しているがどうか調べ、Ｎなら（９）へＹなら（１２）に進む。
（１２）連結しているＳ方向の構成要素を対象点にする。
（１３）対象点のＷ方向にリンク線で構成要素が連結しているがどうか調べ、Ｎなら（１１）へＹなら（１４）に進む。
（１４）連結しているＷ方向の構成要素を対象点にする。
（１５）対象点のＮ方向にリンク線で構成要素が連結しているがどうか調べ、Ｎなら（１３）へＹなら（１６）に進む。
（１６）連結しているＮ方向の構成要素を対象点にする。
（１７）この対象点が始点であるかどうか調べ、Ｎなら（１５）へＹなら（１８）に進む。
（１８）最小矩形として認識し、４角の座標を登録する。
（１９）始点となる構成要素があれば（８）に戻り、なければ処理を終了する。
以上が矩形認識処理の処理フローである。
【００３６】
次に、矩形認識処理を図１７（ａ）（ｂ）を用いて具体的に説明する。
まず、図１７（ａ）において、ＥおよびＳ方向の手を持つ構成要素を始点２８０とする。始点２８０からみて右回りにリンク線２８４をたどり一周して始点２８０に戻れば最小矩形として認識する。始点２８０のＥ方向の手からリンク線２８４をたどり候補点ａ２８１を探索する。この時、候補点ａ２８１の手の方向をチェックすればＳ方向の手を持っていることがわかるので連結し、候補点ａ２８１を新たな対象点としてＳ方向にリンク線をたどり候補点ｂ２８２を探索し、持っている手の方向をチェックする。この候補点ｂ２８２は、Ｗ方向の手を持っていないので次に進むことができない。そこで、対象点（現在は候補点ａ）がＥ方向の手を持っているので、更にＥ方向を探索し候補点ｃ２８３を探索し、手の方向をチェックする。候補点ｃ２８３は、Ｓ方向の手を持っているので候補点ｃ２８３を新たな対象点とする。次に、対象点（候補点ｃ２８３）のＳ方向に連結している候補点ｄ２８５がＷ方向の手を持っている事が分かり、さらに候補点ｄ２８５のＷ方向に連結している候補点ｅ２８６がＮ方向の手を持っているかどうかをチェックする。ここで、Ｎ方向に連結している候補点ｆ２８７が始点かどうかをチェックするが、始点ではない。そこで、さらにＮ方向にリンク線をたどれば始点２８０に戻る事ができる。これで図１７（ｂ）のように、始点２８０、候補点ｃ２８３、候補点ｄ２８５および候補点ｅ２８６の４点がリンクした最小矩形２８８を認識することができた。最後に、この４点の座標を通知する。
【００３７】
次に、構造認識手段１０５について説明する。構造認識手段１０５は、矩形情報から枠の木構造を生成し、その枠の木構造と予め記憶しておいた基準の木構造とを比較して枠構造を認識するもので、処理の概念を図１８を用いて説明する。
【００３８】
図１８は、構造認識手段１０５の処理の枠の木構造の概念を示すもので、矩形２９０の任意の角を矩形の頂点２８９として、各矩形の頂点を水平・垂直方向に仮想的なリンク線２９１で連結したものである。この図では、矩形と矩形の間が離れているが、実際にはリンク線で連結されている矩形同士は接しているものとする。
【００３９】
このような木構造を（表１）のようなフォーマットで記述する。ここで、”番号”はその矩形のレコード番号、”水平方向連結ポインタ”はこの矩形の水平方向に連結している矩形のレコード番号、同じように”垂直方向連結ポインタ”は垂直方向に連結している矩形のレコード番号を示す。また、”欄フラグ”は文字切りだし手段に通知するべき欄かそうでないかを判別するためにある。そして、この矩形の物理情報として、幅と高さをそれぞれ”矩形幅”と”矩形高さ”に記述する。
【００４０】
入力された木構造データと予め用意された基準の木構造データとの連結関係と物理情報を比較して、全ての矩形が基準の木構造データと対応している木構造データを帳票の枠構造として認識する。帳票の枠を木構造として認識する手法は、例えば（成瀬ら：”帳票における枠罫線構造の記述と認識”、ＰＲＵ９０−１５０）があり、よく知られている手法である。
【００４１】
【表１】
0003586911.tif 000010
【００４２】
構造認識手段１０５の処理を、図１９および図２０に示した処理フローに従って詳細に説明する。構造認識手段１０５の処理は大きく分けて２つの処理から構成されおり、木構造を生成する処理とその木構造を基準のデータと比較する処理である。図１９に木構造を生成する処理フローを示し以下に説明する。
（１）矩形データをワークメモリに読み込む。
（２）前記の最小矩形認識手段において認識された矩形の左上の点を探索して矩形の頂点としてフラグを立てる。
（３）（表１）のフォーマットで”番号”、”矩形幅”と”矩形高さ”をワークメモリに書き込む。
（４）全ての矩形データに対して（１）から繰り返す。
（５）フラグの立っているデータを頂点として読み込む。
（６）ある頂点の水平・垂直方向にリンク線で別の矩形の頂点が連結しているかどうか調べる。
（７）連結している場合には、”垂直”または”水平方向連結ポインタ”に連結している矩形のレコード番号を書き込む。
（８）ワークメモリに頂点データがあれば、（５）に戻って繰り返す。
【００４３】
図２０に木構造データを比較する処理フローを示し、以下に説明する。
（９）基準フォーマットに記述されている最初のデータを”基準の始点”として取り出す。
（１０）矩形データテーブルから矩形を選択して候補とする。
（１１）基準の始点の幅と候補の幅との”差”が許容範囲内であるかどうか調べる。
（１２）範囲外の場合には、（１０）に戻り、範囲内の場合には（１３）に進む。
（１３）基準の始点の高さと候補の高さとの”差”が許容範囲内であるか調べる。
（１４）範囲外の場合には、（１０）に戻り、範囲内の場合には（１５）に進む。
（１５）”基準”に連結している枠と、”候補”に連結している枠が対応するかどうか調べる。
（１６）対応すれば、連結しているデータを新しい”基準”と”候補”として（１５）に戻って繰り返す。
（１７）対応しなければ（９）に戻る。
（１８）基準フォーマットが終われば、対応のついた矩形の４角の点の座標の内で”欄フラグ”の立っているデータだけをデータテーブルに登録して終了する。
以上が構造認識処理の処理フローである。（表２）と（表３）に木構造データの一例を示し処理について具体的に説明する。
【００４４】
（表２）が基準データを、（表３）が実際の入力データをそれぞれ（表１）のフォーマットで木構造で記述したものである。まず、（表２）の番号”１”のデータが基準の始点となるので、これに対応する矩形を（表３）から探す。ここで、（表３）の番号”２”の矩形の幅と高さが許容範囲内であるが、”２”に連結している矩形が水平方向だけなので対応しない。しかし、（表３）の番号”３”から”７”までの矩形に関しては、（表２）の基準フォーマットと完全に対応している。そして、対応する矩形の欄フラグの立っている矩形の４角の点をワークメモリに記憶する。
【００４５】
【表２】
0003586911.tif 000011
【００４６】
【表３】
0003586911.tif 000012
【００４７】
次に、文字切り出し手段１０６について説明する。文字切り出し手段１０６は、イメージメモリから実際の文字の２値イメージを切り出して文字認識装置１１４に送るもので、その処理について図２１を用いて詳細に説明する。
【００４８】
図２１は、ある帳票の枠の中に文字が描かれている２値イメージの一部を示す。ここで、３０１〜３０４は構造認識手段から通知された枠の４角の点、３０５は枠の４角の点３０１〜３０４で構成される領域ａ、３０６は領域ａ３０５よりも枠線の幅分小さくした領域ｂ、３０７は枠内に描かれている文字、３０８は文字枠である。
【００４９】
文字切り出しの処理の時には、領域ａ３０５で２値イメージを切り出した場合、文字枠３０８の一部分まで切り出してしまい、余分なイメージを含んでいるために文字認識率が低下する事がある。それを防ぐために、領域ａ３０５よりも枠線の幅分小さくした領域ｂ３０６で２値イメージから切り出すことによって、文字枠３０８を除いたイメージを後の文字認識装置に転送し、高い精度で文字３０７を認識する事ができる。
【００５０】
以上ように、本実施例によればイメージスキャナーからの帳票の２値画像に対して、帳票の枠線部分を矩形の連結した木構造として取り扱う事によって枠線を認識するものである。
【００５１】
【発明の効果】
以上のように一本発明の効果は、帳票の２値画像から枠のコーナー点を抽出し、コーナー点から枠線の構成要素を抽出し、相互に連結された構成要素から帳票の最小矩形を認識することにより、帳票の枠線が細い場合や帳票が傾いて読み取られた場合においても信頼性の高い枠線認識装置を実現できる。
【図面の簡単な説明】
【図１】本発明の実施例における枠線認識装置のブロック結線図
【図２】同実施例の枠線認識装置におけるコーナー検出手段についての詳細ブロック結線図
【図３】同実施例の枠線認識装置における方向コード付与手段についての詳細ブロック結線及びその概念図
【図４】同実施例の枠線認識装置における方向コード付与手段の処理例を示す概念図
【図５】同実施例の枠線認識装置における特徴抽出手段についての詳細ブロック結線図
【図６】同実施例の枠線認識装置における特徴抽出手段についての方向コードの変化点の検出例を示す概念図
【図７】同実施例の枠線認識装置における構成要素抽出手段、最小矩形認識手段、構造認識手段および文字切りだし手段についてのソフトウェア処理の詳細ブロック結線図
【図８】同実施例の枠線認識装置における構成要素抽出手段の処理の概念図
【図９】同実施例の枠線認識装置における構成要素抽出手段からの構成要素の種類を示す概念図
【図１０】同実施例の枠線認識装置における構成要素抽出手段の具体的な処理の手順を示すフローチャート
【図１１】同実施例の枠線認識装置における構成要素抽出手段でのコーナー特徴点を連結する探索範囲およびそのコーナー形状を示す概念図
【図１２】同実施例の枠線認識装置における構成要素抽出手段での構成要素生成を示す図
【図１３】同実施例の枠線認識装置における構成要素抽出手段から生成された構成要素を示す概念図
【図１４】同実施例の枠線認識装置における最小矩形認識手段の処理の概念図
【図１５】同実施例の枠線認識装置における最小矩形認識手段の構成要素を連結する処理の手順を示すフローチャート
【図１６】同実施例の枠線認識装置における最小矩形認識手段の矩形認識処理の処理手順を示すフローチャート
【図１７】同実施例の枠線認識装置における最小矩形認識手段の矩形認識処理の具体的な例を示す概念図
【図１８】同実施例の枠線認識装置における構造認識手段の処理の概念図
【図１９】同実施例の枠線認識装置における構造認識手段の木構造を生成する処理の手順を示すフローチャート
【図２０】同実施例の枠線認識装置における構造認識手段の木構造データを比較する処理の手順を示すフローチャート
【図２１】同実施例の枠線認識装置における文字切り出し手段の処理を示す図
【図２２】従来の枠線認識装置のブロック結線図
【符号の説明】
１０１  イメージスキャナー
１０２  コーナー検出手段
１０３  構成要素抽出手段
１０４  最小矩形認識手段
１０５  構造認識手段
１０６  文字切り出し手段
１０７  イメージメモリ
１１０  ２値画像
１１１  ＦＩＦＯメモリ
１１２  ＣＰＵ
１１３  ワークメモリ
１１４  Ｉ／Ｆ回路
１１５  Ｉ／Ｆ回路
１１６  文字認識装置
２０１  方向コード付与手段
２０２  特徴抽出手段
２０３  注目画素
２１１  ラインメモリ
２１２  ３×３の走査窓
２１３  ＬＵＴ
２１４  方向コード画像
２１６  方向コード
２１７  文字２１７
２１８  文字領域
２２０  ラインメモリ
２２１  多値の３×３走査窓
２２２  ＭＰＸ
２３１  Ｄ０信号
２３０  Ｄ１〜Ｄ８の信号
２２３  ＬＵＴ
２２４  特殊コード判定部
２２５  ＸＹ座標発生器
２２７  同期信号
２２８  ＭＰＸからの出力
２２９  コーナー特徴点
２４１〜２４３  構成要素
２４４  コーナー特徴点の探索領域
２４５〜２４６  コーナー特徴点、
２５５  対象点
２５６  探索範囲
２５７  対象点
２５８  長方形探索領域
２６４  リンク線
２６５  最小矩形の始点
２６７  最小矩形
２６９  三角形探索領域
２７１  対象点
２７２  相手
２７３  手
２７４  逆方向の手
２８０  始点
２８１  候補点ａ
２８２  候補点ｂ
２８３  候補点ｃ
２８４  リンク線
２８５  候補点ｄ
２８６  候補点ｅ
２８７  候補点ｆ
２８８  最小矩形
２８９  矩形の頂点
２９０  矩形
２９１  リンク線
３０１〜３０４  枠の４角の点
３０５  領域ａ
３０６  領域ｂ
３０７  文字
３０８  文字枠
【図１】
0003586911.tif 000013
【図２】
0003586911.tif 000014
【図３】
0003586911.tif 000015
【図４】
0003586911.tif 000016
【図５】
0003586911.tif 000017
【図６】
0003586911.tif 000018
【図７】
0003586911.tif 000019
【図８】
0003586911.tif 000020
【図９】
0003586911.tif 000021
【図１０】
0003586911.tif 000022
【図１１】
0003586911.tif 000023
【図１２】
0003586911.tif 000024
【図１３】
0003586911.tif 000025
【図１４】
0003586911.tif 000026
【図１５】
0003586911.tif 000027
【図１６】
0003586911.tif 000028
【図１７】
0003586911.tif 000029
【図１８】
0003586911.tif 000030
【図１９】
0003586911.tif 000031
【図２０】
0003586911.tif 000032
【図２１】
0003586911.tif 000033
【図２２】
0003586911.tif 000034