枠線認識方法および枠線認識装置
【課題】枠線によって囲まれた様々な形状の対象領域を確実に認識すること。
【解決手段】交点抽出部が、入力画像から抽出した罫線同士の交点を抽出し、記憶部が、交点に属する各罫線に沿ってこの交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、この腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶し、枠線抽出部が、所定の交点を始点として腕ベクトルの向きに従った経路探索を行うことによって閉じた経路が検出された場合に、この閉じた経路を枠線として抽出し、閉じた経路の検出に用いられた腕ベクトルに対応するフラグを使用済みへ更新し、すべてのフラグが使用済みへ更新された場合に、経路探索を終了させるように枠線認識装置を構成する。
【解決手段】交点抽出部が、入力画像から抽出した罫線同士の交点を抽出し、記憶部が、交点に属する各罫線に沿ってこの交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、この腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶し、枠線抽出部が、所定の交点を始点として腕ベクトルの向きに従った経路探索を行うことによって閉じた経路が検出された場合に、この閉じた経路を枠線として抽出し、閉じた経路の検出に用いられた腕ベクトルに対応するフラグを使用済みへ更新し、すべてのフラグが使用済みへ更新された場合に、経路探索を終了させるように枠線認識装置を構成する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、入力画像から枠線を認識する枠線認識方法および枠線認識装置に関する。
【背景技術】
【０００２】
従来、帳票に記入された手書き文字などを認識するＯＣＲ（Optical Character Reader）技術が広く知られている。また、ＯＣＲ技術では、枠線で囲まれた領域（以下、「対象領域」と記載する）に記入された手書き文字を認識することが一般的に行われており、かかる対象領域自体を認識する技術が併用されている。
【０００３】
ここで、対象領域を認識する技術としては、帳票のフォーマットごとに、枠線で囲まれた領域のピクセル座標（たとえば、入力画像の左上を原点とした座標系）を予め登録しておき、登録されたピクセル座標に基づいて対象領域を認識する手法がある。
【０００４】
しかし、フォーマットを予め登録しておく手法を用いると、読み取り対象となる帳票のフォーマットが多岐にわたる場合には、フォーマットを登録する作業が繁雑となる。また、フォーマット自体が定められていない場合には、そもそも対象領域を認識することができない。
【０００５】
このため、帳票のフォーマットの登録を必要としない枠線認識装置が提案されている。たとえば、特許文献１には、入力画像から抽出した枠線のエッジに対して方向コードを付与し、方向コードの変化を検出して枠線で囲まれた領域、すなわち、対象領域を認識する技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３５８６９１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１の技術では、対象領域が正方形や長方形といった矩形である場合には、対象領域の認識が可能であるものの、たとえば、凹型や凸型といった非矩形の形状をもつ対象領域については、認識することができないという問題があった。
【０００８】
特に、近年では、デザインや用途の多様性に応じて帳票のフォーマットも多岐にわたっており、また、１枚ごとにデザインが異なる帳票が用いられる場合もあることから、かかる問題が顕在化してきている。
【０００９】
これらのことから、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる枠線認識方法あるいは枠線認識装置をいかにして実現するかが大きな課題となっている。
【００１０】
本発明は、上述した従来技術による問題点を解消するためになされたものであって、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる枠線認識方法および枠線認識装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、本発明は、入力画像から枠線を認識する枠線認識方法であって、前記入力画像から抽出した罫線同士の交点を抽出する交点抽出工程と、前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶部へ記憶させる交点情報記憶工程と、所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出工程と、前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新工程と、前記更新工程によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出工程による前記経路探索を終了させる終了工程とを含んだことを特徴とする。
【００１２】
また、本発明は、上記の発明において、前記交点抽出工程は、前記入力画像から第１の方向の罫線を抽出して第１の識別子をそれぞれ付与するとともに、前記入力画像から前記第１の方向と垂直な第２の方向の罫線を抽出して第２の識別子をそれぞれ付与し、前記第１の識別子および前記第２の識別子の組み合わせで前記交点を特定することを特徴とする。
【００１３】
また、本発明は、上記の発明において、前記枠線抽出工程は、お互いにつながった前記罫線を１つのグループとし、前記グループごとに前記経路探索を行うことを特徴とする。
【００１４】
また、本発明は、上記の発明において、前記枠線抽出工程は、前記罫線で囲まれた閉領域における外周の前記経路探索の周回方向と、内周の前記経路探索の周回方向とを逆方向としたことを特徴とする。
【００１５】
また、本発明は、上記の発明において、前記枠線抽出工程は、前記経路探索において前記交点の前記腕ベクトルの向きが複数ある場合には、前記外周の前記経路探索であれば前記閉領域の外側へ向かう向きを優先して前記腕ベクトルを選択し、前記内周の前記経路探索であれば前記閉領域の内側へ向かう向きを優先して前記腕ベクトルを選択することを特徴とする。
【００１６】
また、本発明は、上記の発明において、前記枠線抽出工程は、抽出した前記枠線が同一の前記交点を複数回通過するものである場合に、当該枠線を当該交点で複数の前記枠線へ分割することを特徴とする。
【００１７】
また、本発明は、上記の発明において、前記交点抽出工程は、前記罫線における前記交点ではない先端を延長した延長線を生成し、当該延長線が他の罫線の延長線または前記他の罫線自体と最初に交わる点を仮交点としたうえで、前記先端を含んだ所定の領域内に当該先端と前記他の罫線をつなぐ経路が存在する場合に、当該仮交点を前記交点として抽出することを特徴とする。
【００１８】
また、本発明は、入力画像から枠線を認識する枠線認識装置であって、前記入力画像から抽出した罫線同士の交点を抽出する交点抽出手段と、前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶する交点情報記憶手段と、所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出手段と、前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新手段と、前記更新手段によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出手段による前記経路探索を終了させる終了手段とを備えたことを特徴とする。
【発明の効果】
【００１９】
本発明によれば、入力画像から抽出した罫線同士の交点を抽出し、交点に属する各罫線に沿ってこの交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、この腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶部へ記憶させ、所定の交点を始点として腕ベクトルの向きに従った経路探索を行うことによって閉じた経路が検出された場合に、この閉じた経路を枠線として抽出し、閉じた経路の検出に用いられた腕ベクトルに対応するフラグを使用済みへ更新し、すべてのフラグが使用済みへ更新された場合に、経路探索を終了させることとしたので、枠線によって囲まれた様々な形状の対象領域を確実に認識することができるという効果を奏する。
【００２０】
また、本発明によれば、入力画像から第１の方向の罫線を抽出して第１の識別子をそれぞれ付与するとともに、入力画像から第１の方向と垂直な第２の方向の罫線を抽出して第２の識別子をそれぞれ付与し、第１の識別子および第２の識別子の組み合わせで交点を特定することとしたので、簡便な処理で交点を特定することができるという効果を奏する。
【００２１】
また、本発明によれば、お互いにつながった罫線を１つのグループとし、グループごとに経路探索を行うこととしたので、入れ子や重なりといった複雑な形状を有する罫線であっても確実に認識することができるという効果を奏する。
【００２２】
また、本発明によれば、罫線で囲まれた閉領域における外周の経路探索の周回方向と、内周の経路探索の周回方向とを逆方向としたので、腕ベクトルに対応するフラグがすべて通過済みとなったことを探索終了の条件とすることができ、重複した経路探索を防止することができるという効果を奏する。
【００２３】
また、本発明によれば、経路探索において交点の腕ベクトルの向きが複数ある場合には、外周の経路探索であれば閉領域の外側へ向かう向きを優先して腕ベクトルを選択し、内周の経路探索であれば閉領域の内側へ向かう向きを優先して腕ベクトルを選択することとしたので、凹型や凸型といった複雑な形状の枠線を確実に認識することができるという効果を奏する。
【００２４】
また、本発明によれば、抽出した枠線が同一の交点を複数回通過するものである場合に、枠線をこの交点で複数の枠線へ分割することとしたので、表の構成としては不自然なつながりを有する枠線を分割することで、文字やノイズの影響による枠線の誤認識を防止することができるという効果を奏する。
【００２５】
また、本発明によれば、罫線における交点ではない先端を延長した延長線を生成し、この延長線が他の罫線の延長線または他の罫線自体と最初に交わる点を仮交点としたうえで、先端を含んだ所定の領域内にこの先端と他の罫線をつなぐ経路が存在する場合に、仮交点を交点として抽出することとしたので、角が丸い枠線を確実に認識することができるという効果を奏する。
【図面の簡単な説明】
【００２６】
【図１】図１は、本発明に係る枠線認識手法の概要を示す図である。
【図２】図２は、本実施例に係る枠線認識装置の構成を示すブロック図である。
【図３】図３は、罫線抽出処理の説明図である。
【図４】図４は、交点抽出処理の説明図である。
【図５】図５は、交点補正処理その１の説明図である。
【図６】図６は、交点補正処理その２の説明図である。
【図７】図７は、交点補正処理その３の説明図である。
【図８】図８は、交点グループ化処理の説明図である。
【図９】図９は、交点情報の一例を示す図である。
【図１０】図１０は、経路探索の優先順位を示す図である。
【図１１】図１１は、外周経路探索の一例を示す図である。
【図１２】図１２は、内周経路探索の一例を示す図である。
【図１３】図１３は、枠線情報の一例を示す図である。
【図１４】図１４は、枠線補正処理の説明図である。
【図１５】図１５は、枠線内画像抽出処理の説明図である。
【図１６】図１６は、破線検出処理の説明図である。
【図１７】図１７は、枠線認識装置が実行する処理手順を示すフローチャートである。
【図１８】図１８は、罫線抽出処理の処理手順を示すフローチャートである。
【図１９】図１９は、交点抽出処理の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００２７】
以下に、添付図面を参照して、本発明に係る枠線認識手法の好適な実施例を詳細に説明する。なお、以下では、本発明に係る枠線認識手法の概要について図１を用いて説明した後に、本発明に係る枠線認識手法を適用した枠線認識装置についての実施例を図２〜図１９を用いて説明する。
【００２８】
まず、本発明に係る枠線認識手法の概要について図１を用いて説明する。図１は、本発明に係る枠線認識手法の概要を示す図である。なお、同図では、手書き文字を含んだ帳票をスキャンした入力画像１から枠線を検出し、最終的に、枠線で囲まれた領域（以下、「枠線内領域」と記載する）を確定するまでの手順を示している。
【００２９】
なお、「罫線」という用語は、入力画像１から抽出された直線を指す場合に用い、「枠線」という用語は、後述する経路探索によって検出された閉じた経路を指す場合に用いることとする。また、入力画像は、あらかじめ２値化されているものとする。
【００３０】
図１に示すように、本発明に係る枠線認識手法は、入力画像１から検出した水平罫線および垂直罫線の各交点について、交点に属する罫線の向きを示す腕ベクトルを生成するとともに、生成した腕ベクトルに基づいて経路探索を行う。また、本発明に係る枠線認識手法は、経路探索で腕ベクトルが用いられたか否かを示すフラグである通過済フラグがすべて通過済みとなったことを条件として経路探索を終了する。
【００３１】
具体的には、本発明に係る枠線認識手法では、まず、入力画像１から「交点情報」を検出する（図１の（Ａ）参照）。ここで、交点情報は、各交点が、左、右、上および下のうちどの向きの腕ベクトルを有するかを示す「交点種別」と、各腕ベクトルが経路探索で用いられたこと、すなわち、通過済みとなったことを示す「通過済フラグ」とを含んだ情報である。
【００３２】
なお、以下では、「交点種別」および「通過済フラグ」をそれぞれ４ビットで表現する場合について説明する。また、「交点種別」は、腕ベクトルが存在する場合には「１」、存在しない場合には「０」とし、「通過済フラグ」は、通過済みである場合には「１」、未通過の場合には「０」として説明するが、他の表現方式をとっても構わない。
【００３３】
また、図１に示す、「左」、「右」、「上」および「下」は、「左向きの腕ベクトル」、「右向きの腕ベクトル」、「上向きの腕ベクトル」および「下向きの腕ベクトル」にそれぞれ対応している。なお、各交点に示した「黒矢印」は、該当する腕ベクトルが未通過である旨を、「白抜き矢印」は、該当する腕ベクトルが通過済みである旨を、それぞれ示している。
【００３４】
図１の（Ａ）に示したように、交点ｇは、水平罫線と垂直罫線とが接する右上のコーナーであるので、「交点種別」における「左」および「下」が「１」、「右」および「下」が「０」となる。また、「通過済みフラグ」は、初期値としてすべて「０」が設定されている。
【００３５】
ここで、本発明に係る枠線認識手法は、交点の腕ベクトルをすべて通過したことを、上記した「通過済フラグ」を介して検出した場合に、経路探索を終了する点に特徴がある。このため、本発明に係る枠線認識手法では、交点の集合によって構成される閉領域の外周を探索する「外周経路探索」と、内周を探索する「内周経路探索」との周回方向を逆方向としている。
【００３６】
たとえば、図１の（Ｂ）に示したように、外周経路探索を「時計回り」に行った場合には、図１の（Ｃ）に示したように、内周経路探索を「反時計回り」に行う。
【００３７】
そして、図１の（Ｂ）に示したように、交点ａ、ｄ、ｅ、ｇ、ｈ、ｃ、ｂおよびａという閉じた外周経路が検出された場合には、通過した腕ベクトルに対応する通過済みフラグが「１」へ更新される。たとえば、交点ｇの通過済みフラグの「下」は、「０」から「１」へ更新される。
【００３８】
また、図１の（Ｃ）に示したように、交点ａ、ｂ、ｆ、ｅ、ｄおよびａという閉じた内周経路、交点ｇ、ｅ、ｆ、ｂ、ｃ、ｈおよびｇという閉じた内周経路がそれぞれ検出されると、通過した腕ベクトルに対応する通過済みフラグが「１」へ更新される。たとえば、交点ｇの通過済みフラグの「左」は、「０」から「１」へ更新される。この段階で、交点ｇの交点種別「１００１」と、通過済みフラグ「１００１」とが一致した状態となる。
【００３９】
そして、図１の（Ｄ）に示したように、他のすべての交点についても同様に、交点種別と通過済みフラグとが一致した状態となった場合に、本発明に係る枠線認識手法は、経路探索を終了し、検出した枠線で囲まれた枠線内領域を確定する。
【００４０】
このように、本発明に係る枠線認識手法では、交点の腕ベクトルに従って経路探索を行うとともに、各腕ベクトルに対応したフラグがすべて通過済みとなった場合に、経路探索を終了して枠線内領域を確定する。したがって、本発明に係る枠線認識手法によれば、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる。
【００４１】
以下では、図１を用いて説明した枠線認識手法を適用した枠線認識装置についての実施例を説明する。なお、以下では、画像読取装置（たとえば、スキャナ装置）から入力画像を取得する枠線認識装置について説明するが、スキャナ装置を含んだ枠線認識装置を構成することとしてもよい。また、枠線認識装置にいわゆるＯＣＲ（Optical Character Reader）機能を持たせ、認識した枠線内領域に対応する画像の文字認識を行わせることとしてもよい。
【実施例】
【００４２】
図２は、本実施例に係る枠線認識装置１０の構成を示すブロック図である。同図に示すように、枠線認識装置１０は、画像読取装置２０と接続されており、画像読取装置２０が読み取った画像（たとえば、帳票をスキャンした画像）を取得する。なお、画像読取装置２０としては、たとえば、いわゆるスキャナ装置を用いることができる。
【００４３】
枠線認識装置１０は、制御部１１と、記憶部１２とを備えており、制御部１１は、画像取得部１１ａと、罫線抽出部１１ｂと、交点抽出部１１ｃと、グループ化部１１ｄと、枠線抽出部１１ｅと、枠線内画像抽出部１１ｆと、破線検出部１１ｇと、交点補正部１１ｈとをさらに備えている。また、記憶部１２は、入力画像１２ａと、交点情報１２ｂと、枠線情報１２ｃと、枠線内画像１２ｄとを記憶する。
【００４４】
制御部１１は、枠線認識装置１０の全体制御および枠線抽出処理を行う制御部である。また、画像取得部１１ａは、画像読取装置２０から、手書き文字を含んだ帳票をスキャンした入力画像１（図１参照）を取得し、２値化処理を行ったうえで、記憶部１２へ入力画像１２ａとして記憶させる処理を行う処理部である。なお、入力画像１が２値化画像である場合には、２値化処理を行う必要はない。
【００４５】
罫線抽出部１１ｂは、記憶部１２の入力画像１２ａから罫線を抽出する処理を行うとともに、抽出した罫線に関する情報を交点抽出部１１ｃへ渡す処理を行う処理部である。ここで、罫線抽出部１１ｂによって行われる罫線抽出処理の内容について図３を用いて説明しておく。
【００４６】
図３は、罫線抽出処理の説明図である。まず、図３の（Ａ）に示したのは、入力画像１２ａ（原画像）を、１／１６最小値圧縮した圧縮画像３１である。ここで、「１／１６最小値圧縮」とは、隣接する４画素×４画素の画素グループを１つの代表画素へ置き換える際に、画素グループに属する画素の画素値の最小値を、代表画素の画素値とする処理を指す。つまり、１６画素中に１つでも画素値０（黒に対応）の画素があれば、代表画素は画素値０となる。そして、罫線抽出部１１ｂは、かかる圧縮画像３１を罫線の抽出対象として用いる。
【００４７】
つづいて、図３の（Ｂ）に示したように、罫線抽出部１１ｂは、図３の（Ａ）に示した圧縮画像３１から、水平罫線３２および垂直罫線３３をそれぞれ抽出する。ここで、水平罫線３２としては、所定方向にそれぞれ連続する黒画素群（以下、「ランレン」と記載する）のうち、水平方向のもの、かつ、所定長以上のものが抽出される。
【００４８】
また、垂直罫線３３としては、垂直方向のランレンのうち、所定長以上のものが抽出される。なお、図３の（Ｂ）に示した場合では、水平罫線３２が４つ、垂直罫線３３が３つ、それぞれ抽出されている。
【００４９】
ここで、所定長以上のランレンを水平罫線３２あるいは垂直罫線３３として検出する処理を行う場合、平行する２本の罫線が近接していると、１本の罫線として誤検出してしまうおそれがある。このため、罫線抽出部１１ｂは、図３の（Ｃ）に示した「罫線方向圧縮」を行うことで、近接した２本の罫線を１本の罫線として誤検出してしまう問題を回避する。
【００５０】
水平罫線３２の場合を例にあげて説明すると、図３の（Ｃ）に示したように、検出された罫線のラベリングを行ったうえで、得られたラベルの外接矩形内で入力画像１２ａ（原画像）を切り出す。そして、切出画像３４を、罫線方向（この場合、水平方向）にのみ１／４最小値圧縮する（図３の（Ｃ−１）参照）。なお、垂直罫線３３の場合には、垂直方向にのみ１／４最小値圧縮すればよい。ここで、１／４最小値圧縮とは、一方向へ隣接する４画素の画素グループを１つの代表画素へ置き換える際に、画素グループに属する画素の画素値の最小値を代表画素値とする処理を指す。
【００５１】
つづいて、罫線方向圧縮画像３５でランレンを取得し、所定値以下のランレンを削除する（図３の（Ｃ−２）参照）。このようにすることで、入力画像１２ａ（原画像）の対応部分における罫線方向以外のランレンを効率的に削除することができる。そして、残ったランレンをラベリングすることで（図３の（Ｃ−３）参照）、近接した２本の罫線を、ラベル３６およびラベル３７として、すなわち、２本の罫線として検出することができる。
【００５２】
ところで、図３の（Ｃ）に示した「罫線方向圧縮」を用いた場合には、入力画像１２ａ（原画像）に「かすれ」や「ひずみ」がある場合に、１本の罫線を複数本の罫線として検出してしまう副作用が発生する可能性がある。このため、罫線抽出部１１ｂは、複数のラベルの結合処理をあわせて行う。
【００５３】
具体的には、図３の（Ｄ）に示したように、２つのラベル３８およびラベル３９の重なり長（ｌａｐ）および間隔（ｄｉｓｔ）を、それぞれ取得する。そして、ｌａｐが所定の閾値以下であり、かつ、ｄｉｓｔが所定の閾値以下である場合に、２つのラベルを結合する。なお、ｌａｐに関する閾値と、ｄｉｓｔに関する閾値としては、画像の解像度であるｄｐｉ（dot per inch）などに基づいて予め定められた最適な値がそれぞれ用いられるものとする。
【００５４】
このように、罫線抽出部１１ｂは、図３の（Ｃ）に示した罫線の分離処理および図３の（Ｄ）に示した罫線の結合処理をそれぞれ行い、最終的に残った罫線に対して識別番号を付与する。なお、以下では、罫線に対して付与された識別番号を、「罫線ＩＤ」と記載することとする。
【００５５】
たとえば、図３の（Ｅ）に示した場合では、水平罫線３２については、ｙ座標（図３の（Ａ）参照）が小さい方から順に、罫線ＩＤとして「０」、「１」、「２」および「３」を付与している。また、垂直罫線３３については、ｘ座標（図３の（Ａ）参照）が小さい方から順に、罫線ＩＤとして「０」、「１」および「２」を付与している。
【００５６】
なお、図３の（Ｅ）では、水平罫線３２および垂直罫線３３が、図３の（Ｂ）のものと同一の場合を例示したが、図３の（Ｃ）あるいは（Ｄ）で、罫線の追加や削除が行われた場合には、最終的に残った罫線に対して罫線ＩＤが付与されることはいうまでもない。
【００５７】
また、ｘ座標が同じ罫線が複数存在する場合には、ｙ座標が小さい方から昇順の罫線ＩＤを付与し、ｙ座標が同じ罫線が複数存在する場合には、ｘ座標が小さい方から昇順の罫線ＩＤを付与するものとする。なお、罫線ＩＤの付与を降順に行っても構わない。
【００５８】
図２の説明に戻り、制御部１１の説明をつづける。交点抽出部１１ｃは、罫線抽出部１１ｂから受け取った罫線に関する情報に基づいて交点情報１２ｂを生成する処理を行う処理部である。また、この交点抽出部１１ｃは、生成した交点情報１２ｂを記憶部１２へ記憶させる処理をあわせて行う。
【００５９】
ここで、交点抽出部１１ｃによって行われる交点抽出処理の内容について図４を用いて説明しておく。図４は、交点抽出処理の説明図である。なお、図４の（Ａ）および（Ｂ）では、図３の（Ｅ）に示した０〜３の４本の水平罫線３２および０〜２の３本の垂直罫線３３の交点を求める場合について説明する。
【００６０】
図４の（Ａ）に示すように、交点抽出部１１ｃは、罫線抽出部１１ｂから受け取った罫線に関する情報に基づいて交点を抽出し、抽出した交点に対して座標を付与する。ここで、交点抽出部１１ｃは、水平罫線３２の罫線ＩＤ（ｖ座標に相当）と、垂直罫線３３の罫線ＩＤ（ｕ座標に相当）とで、罫線の交点に対して罫線ＩＤを用いた座標（ｕ，ｖ）を付与する。
【００６１】
たとえば、図４の（Ａ）に示した交点（１，２）は、ｕ＝０の垂直罫線３３と、ｖ＝２の水平罫線３２との交点である。また、交点（２，３）は、ｕ＝２の垂直罫線３３と、ｖ＝３の水平罫線３２との交点である。
【００６２】
また、交点抽出部１１ｃは、図４の（Ｂ）に示したように、座標を付与した各交点の交点種別を特定する。すなわち、交点抽出部１１ｃは、所定の交点と、ｕ座標またはｖ座標が同一な直近の交点を検出する処理を行い、直近の交点を検出した場合に、直近の交点へ向かう「腕ベクトル」があると判定する。
【００６３】
たとえば、図４の（Ｂ）に示したように、交点（０，０）とｕ座標が同一で直近の交点は、交点（０，２）であるので、交点（０，０）には下向きの腕ベクトルがあると判定される。なお、交点（０，０）の上側、すなわち、ｖ座標の負方向には交点がないので、交点（０，０）には上向きの腕ベクトルはないと判定される。
【００６４】
また、図４の（Ｂ）に示したように、交点（０，０）とｖ座標が同一で直近の交点は、交点（１，０）であるので、交点（０，０）には右向きの腕ベクトルがあると判定される。なお、交点（０，０）の左側、すなわち、ｕ座標の負方向には交点がないので、交点（０，０）には左向きの腕ベクトルはないと判定される。
【００６５】
このように、交点抽出部１１ｃは、座標が付与されたすべての交点の交点種別、すなわち、４方向の腕ベクトルがそれぞれあるか否かの種別を特定する（図４の（Ｂ）で円に囲まれた領域を参照）。ここで、交点種別のパターンは、図４の（Ｃ）に示したように、パターンＡからパターンＩまでの９種類が存在する。
【００６６】
たとえば、図４の（Ｂ）に示した交点（０，０）の交点種別４１ａは、図４の（Ｃ）に示したパターンＡである。また、図４の（Ｂ）に示した交点（２，３）の交点種別４１ｂは、図４の（Ｃ）に示したパターンＩである。なお、本実施例では、各交点からそれぞれ遠ざかる向きの腕ベクトルを用いる場合について説明するが、各交点へそれぞれ近づく向きの腕ベクトルを用いることとしてもよい。
【００６７】
ここで、各交点種別は、左向きの腕ベクトル（左腕）、右向きの腕ベクトル（右腕）、上向きの腕ベクトル（上腕）および下向きの腕ベクトル（下腕）の各腕ベクトルがあるか否かを示す情報である。したがって、図４の（Ｄ）に示したように、各１ビットのフラグ×４方向の計４ビットの情報として表現することができる。
【００６８】
図４の（Ｄ）に示したように、パターンＥでは、４方向の腕ベクトルをすべて有しているので、４つのフラグをすべて立てた「１１１１」と表現することができる。また、パターンＩでは、左腕および上腕のみを有しているので、「１０１０」と表現することができる。
【００６９】
なお、交点抽出部１１ｃは、上記した「交点種別」と、交点種別に含まれる腕ベクトルが後述する経路探索で用いられたか否かを示す「通過済フラグ」とを含んだ交点情報１２ｂを生成するが、この交点情報１２ｂの詳細な内容については、図９を用いて後述する。
【００７０】
ところで、図４では、交点抽出部１１ｃによって行われる交点抽出処理のうち、最も基本的な処理、すなわち、水平罫線３２と垂直罫線３３との交点を、単に交点として抽出する処理について説明した。
【００７１】
しかしながら、角が丸い枠が存在する場合や、枠がかすれている場合、枠に文字が接していたりノイズの影響があったりする場合などには、検出すべき交点を検出できなかったり、本来は交点ではないのに交点として検出してしまったりといった交点の誤検出が発生する。
【００７２】
そこで、交点抽出部１１ｃは、交点の削除や追加といった交点の補正処理をあわせて行う。このため、以下では、交点抽出部１１ｃによって行われる交点補正処理について、図５〜図７を用いて説明する。なお、交点補正処理は、図４の（Ａ）に示した座標付与処理と、図４の（Ｂ）に示した交点種別特定処理との間に挿入される形で行われる。
【００７３】
図５は、交点補正処理その１の説明図である。なお、交点補正処理その１は、角が丸い枠を矩形枠と仮定した場合の仮交点を検出し、検出した仮交点をあらたな交点として追加する処理である。なお、交点は「●」で、交点ではない先端は「◇」で、それぞれ示している。
【００７４】
図５の（Ａ）に示したのは角が丸い枠をもつ入力画像１２ａの一例である。なお、図５の（Ａ）に示した場合では、右下の角のみが角が丸い状態、すなわち、Ｌ字部分のみが丸い状態である。
【００７５】
この場合、図３を用いて説明した罫線抽出処理で水平罫線３２および垂直罫線３３を抽出し、図４を用いて説明した交点抽出処理で交点を抽出すると、図５の（Ａ−１）に示したように、３つの交点（交点５１ａ、交点５１ｂおよび交点５１ｃ）のみが検出される。
【００７６】
ここで、図５の（Ａ−１）に示した矩形の上辺および左辺は、それぞれ２つの交点で挟まれた罫線であるが、同じく下辺および右辺は、１つの交点のみしか有しない罫線である。
【００７７】
そこで、交点抽出部１１ｃは、１つの交点のみしか有しない罫線の先端（すなわち、交点ではない先端）を延伸し、他の罫線もしくは他の罫線の先端を延伸した線との交点を求める処理を行う。
【００７８】
具体的には、図５の（Ａ−１）に示した場合、交点抽出部１１ｃは、１つの交点のみしか有しない罫線の先端５２ａおよび先端５２ｂをそれぞれ延伸し、先端５２ａおよび先端５２ｂを対角線とする矩形領域である検証領域５３を生成する。なお、有効な検証領域５３のサイズはあらかじめ定められているものとし、所定のサイズよりも大きい検証領域しか得られなかった場合には、図５の（Ａ−２）以降の処理は行われない。
【００７９】
つづいて、交点抽出部１１ｃは、図５の（Ａ−２）に示したように、検証領域５３において、先端５２ａと先端５２ｂとをつなぐ黒画素が、図５の（Ａ）に示した入力画像１２ａにあるか否かを検査する。
【００８０】
そして、図５の（Ａ−２）に示した場合には、先端５２ａと先端５２ｂとをつなぐ黒画素（連結線５２ｃ）が検出されたので、図５の（Ａ−３）に示したように、延伸した線同士が交わる点を交点５４とし、あらたな交点（交点種別：図４の（Ｃ）のパターンＩ）として追加する。
【００８１】
次に、枠線のＴ字部分が丸い場合について、図５の（Ｂ）および（Ｂ−１）〜（Ｂ−３）を用いて説明する。図５の（Ｂ）に示したのは角が丸い枠をもつ入力画像１２ａのその他の例である。なお、図５の（Ｂ）に示した場合では、逆Ｔ字部分が丸い状態である。
【００８２】
この場合、図３を用いて説明した罫線抽出処理で水平罫線３２および垂直罫線３３を抽出し、図４を用いて説明した交点抽出処理で交点を抽出すると、図５の（Ｂ−１）に示したように、５つの交点（交点５６ａ、交点５６ｂ、交点５６ｃ、交点５６ｄおよび交点５６ｅ）が検出される。
【００８３】
ここで、図５の（Ｂ−１）に示した垂直罫線３３の５５ａ、水平罫線３２の５５ｂおよび５５ｃは、１つの交点のみしか有しない罫線である。そこで、交点抽出部１１ｃは、１つの交点のみしか有しない罫線の先端（先端５７ａ、先端５７ｂおよび先端５７ｃ）を延伸し、他の罫線もしくは他の罫線の先端を延伸した線との交点を求める処理、すなわち、図５の（Ａ）と同様の処理を行う。このような処理を行うと、図５の（Ｂ−２）に示した連結線５７ｄおよび連結線５７ｅが検出され、図５の（Ｂ−３）に示したように、交点５９ａ（交点種別：図４の（Ｃ）のパターンＩ）と、交点５９ｂ（交点種別：図４の（Ｃ）のパターンＧ）とがあらたな交点候補として見つけられる。
【００８４】
ここで、あらたな交点候補が見つけられた罫線（５５ａ、５５ｂおよび５５ｃ）において、総当たりの各ペアで罫線幅方向に重なりがあるか否かが検証され、重なりがある場合には、該当するペア（図５の（Ｂ−３）では、罫線５５ｂおよび罫線５５ｃ）同士を結合する。
【００８５】
そして、図５の（Ｂ−４）に示したように、結合した罫線上の交点５９ａおよび交点５９ｂ（同図の（Ｂ−３）参照）を合成し、あらたな交点５９ｃ（交点種別：図４の（Ｃ）のパターンＨ）として確定し、追加する。この場合、あらたな交点５９ｃのｖ座標は、罫線５５ｂまたは罫線５５ｃのいずれかの罫線ＩＤを用いる。また、罫線５５ｂ上の交点および罫線５５ｃ上の交点についても、交点５９ｃのｖ座標に用いた罫線ＩＤへ共通化する。
【００８６】
つづいて、交点補正処理その２について説明する。図６は、交点補正処理その２の説明図である。なお、交点補正処理その２は、「かすれ」によって分断された罫線を結合し、先端に交点をもたない罫線に対してあらたな交点を追加する処理である。
【００８７】
なお、図６の（Ａ）には、最終的に結合する線分のペアと、結合しない線分とを模式的に示している。また、図５の場合と同様に、交点は「●」で、交点ではない先端は「◇」で、それぞれ示している。図６の（Ａ）に示したように、交点抽出部１１ｃは、交点ではない先端を有する線分（線分６１ａ〜線分６１ｅ）をそれぞれ抽出する。ここで、線分とは、罫線上において交点と交点とで挟まれた部分の直線、または、罫線の先端と先端から最も近い交点とで挟まれた部分の直線のことを指す。
【００８８】
つづいて、交点抽出部１１ｃは、図６の（Ｂ）に示したように、先端から所定距離以内に交点がない線分を抽出する（図６の（Ｂ−１）参照）。ここでは、線分６１ａ〜線分６１ｄが抽出されている。なお、線分６１ｅは、先端から所定距離以内に交点をもっているので候補から除外される。ここで、所定距離としては、あらかじめ定められた画素数や長さ（たとえば、ｍｍ）が用いられる。
【００８９】
また、図６の（Ｂ）に示したように、交点抽出部１１ｃは、先端から所定距離以内に交点がない線分（線分６１ａ〜線分６１ｄ）の先端を延伸し、延伸した線分の幅方向に重なる最も近い線分を抽出する（図６の（Ｂ−２）参照）。
【００９０】
なお、図６の（Ｂ）では、線分６１ａのペアとして線分６２ａが、線分６１ｂのペアとして線分６２ｂが、線分６１ｃのペアとして線分６２ｃが、それぞれ抽出されている。これに対し、線分６１ｄについては該当する線分がないため、候補から除外される。
【００９１】
つづいて、交点抽出部１１ｃは、図６の（Ｂ）で候補として残った線分について、図６（Ｃ）に示した結合条件（Ｃ−１）〜（Ｃ−３）を適用し、すべての結合条件を満たした線分を図６の（Ｂ）で抽出したペア線分と結合する。
【００９２】
ここで、結合条件（Ｃ−１）は、ペアとなる線分間の距離を結合後の線分長で除した値がα％よりも小さいという条件である。また、結合条件（Ｃ−２）は、ペアとなる線分間の距離がβよりも小さいという条件である。さらに、結合条件（Ｃ−３）は、結合後の線分から垂直方向に出っ張る黒画素長がγよりも小さいという条件である。
【００９３】
なお、α％は、たとえば、５％であり、βあるいはγについては、あらかじめ定められた画素数や長さ（たとえば、ｍｍ）が用いられる。
【００９４】
また、図６の（Ｂ）で候補として残った線分６１ａ、線分６１ｂおよび線分６１ｃのうち、線分６１ｃは、結合条件（Ｃ−１）あるいは結合条件（Ｃ−２）を満たさない例である。また、線分６１ｂは、結合条件（Ｃ−３）を満たさない例である。
【００９５】
このようにして、図６に例示した場合では、最終的には、線分６１ａが、線分６２ａと結合される。ここで、線分６１ａを有する罫線上の交点と、線分６２ａを有する罫線上の交点のｕ座標を、２つの罫線のうちいずれかの罫線の罫線ＩＤへ共通化する。なお、ここでは、垂直罫線を結合する場合について説明したが、水平罫線を結合する場合にはｖ座標を共通化することとすればよい。そして、図６に示した線分の結合処理の後、交点補正処理その３、すなわち、１つの交点のみしか有しない線分の削除処理が行われる。
【００９６】
つづいて、交点補正処理その３について説明する。図７は、交点補正処理その３の説明図である。なお、交点補正処理その３は、枠に文字が接した影響や、ノイズの影響で誤検出された交点を削除する処理である。
【００９７】
図７の（Ａ）に示したのは、文字が枠に接した入力画像１２ａの一例である。図７の（Ａ）に示した場合では、領域７１ａで、「市」という手書き文字が線分７１に接している。また、領域７１ｂで、「１」という手書き文字が線分７１に接している。
【００９８】
この場合、図３を用いて説明した罫線抽出処理で水平罫線３２および垂直罫線３３を抽出し、図４を用いて説明した交点抽出処理で交点を抽出すると、図７の（Ｂ）に示したように、線分７１と交点をもつ線分として線分７２ｂおよび線分７２ｃが、線分７２ｃと交点をもつ線分として線分７２ａが、それぞれ抽出される。なお、抽出された交点は、それぞれ「●」で示している。
【００９９】
ここで、交点抽出部１１ｃは、図７の（Ｃ）に示したように、交点を１つしか有しない線分である線分７２ａおよび線分７２ｂを削除する。そして、線分７２ａを削除した結果、１つの交点のみしか有しない線分となった線分７２ｃを、図７の（Ｄ）に示したように、削除する。このように、交点抽出部１１ｃは、１つの交点のみしか有しない線分の削除を、再帰的に行う。これにより、削除された線分が有していた交点は順次、削除されていくことになる。
【０１００】
なお、図７には、枠に文字が接した影響によって誤検出された交点を削除する場合について例示したが、ノイズの影響で誤検出された交点についても同様の手法で削除することができる。
【０１０１】
このように、交点抽出部１１ｃは、水平罫線３２と垂直罫線３３との交点を抽出した後、図５〜図７に示した交点の削除や追加といった交点補正処理を行う。そして、交点抽出部１１ｃは、交点補正処理後の交点について交点情報１２ｂを生成する。
【０１０２】
図２の説明に戻り、制御部１１の説明をつづける。グループ化部１１ｄは、交点抽出部１１ｃによって記憶部１２へ格納された交点情報１２ｂに基づき、交点のグループ分けを行う処理部である。
【０１０３】
ここで、グループ化部１１ｄによって行われる交点グループ化処理について図８を用いて説明しておく。図８は、交点グループ化処理の説明図である。なお、図８の（Ａ）には、グループ分けの対象となる交点の例を、図８の（Ｂ）には、グループ分けの結果を、それぞれ示している。
【０１０４】
グループ化部１１ｄは、座標が付与された交点について、罫線によってつながっているグループを検索する。たとえば、図８の（Ａ）に示した場合では、交点（０，０）、交点（０，４）、交点（３，４）および交点（３，０）が罫線によってつながれているので、これらの交点をグループＡとする。
【０１０５】
また、図８の（Ａ）に示した場合では、交点（１，１）、交点（１，２）、交点（１，３）、交点（２，３）、交点（２，２）および交点（２，１）が罫線によってつながれているので、これらの交点を１つのグループＢとする。
【０１０６】
このようにして、グループ化部１１ｄは、交点のグループ分けを行い、図８の（Ｂ）に示した結果を得る。なお、図８では、２つのグループを示したが、３つ以上のグループについても同様の手順でグループ分けを行うことができる。
【０１０７】
図２の説明に戻り、制御部１１の説明をつづける。枠線抽出部１１ｅは、グループ分け済みの交点情報１２ｂに基づき、経路探索を行うことで、閉じた経路である枠線を抽出する処理を行う処理部である。
【０１０８】
また、枠線抽出部１１ｅは、抽出した枠線に関する情報である枠線情報１２ｃを、記憶部１２へ記憶させる処理をあわせて行う。なお、枠線抽出部１１ｅによって行われる枠線抽出処理の詳細な内容については、図１０〜図１２を用いて後述する。また、枠線抽出処理につづいて行われる枠線補正処理の詳細な内容については、図１４を用いて後述する。
【０１０９】
枠線内画像抽出部１１ｆは、枠線抽出部１１ｅによって記憶部１２へ記憶させられた枠線情報１２ｃと、入力画像１２ａとに基づき、枠線によって囲まれた領域である枠線内画像１２ｄを抽出する処理を行う処理部である。また、この枠線内画像抽出部１１ｆは、抽出した枠線内画像１２ｄを記憶部１２へ記憶させる処理をあわせて行う。
【０１１０】
破線検出部１１ｇは、記憶部１２から読み出した枠線内画像１２ｄから、破線を検出する処理を行う処理部である。また、この破線検出部１１ｇは、検出した破線に関する情報を、交点補正部１１ｈへ渡す処理をあわせて行う。
【０１１１】
交点補正部１１ｈは、破線検出部１１ｇから受け取った破線に関する情報に基づき、交点情報１２ｂを更新する処理を行うとともに、更新後の交点情報１２ｂに基づいた交点の再グループ分けをグループ化部１１ｄに対して指示する処理を行う処理部である。
【０１１２】
すなわち、交点補正部１１ｈは、破線検出部１１ｇによって破線が検出され、検出された破線に基づく交点があらたに検出された場合に、あらたに検出された交点に関する情報で交点情報１２ｂを更新する。
【０１１３】
そして、グループ化部１１ｄは、更新後の交点情報１２ｂに含まれる交点を用いてグループ化処理を再度実行する。なお、破線検出部１１ｇによってあらたな破線が検出されなかった段階で、枠線情報１２ｃは確定されることになる。
【０１１４】
なお、枠線内画像抽出部１１ｆによる枠線内画像抽出処理の具体的な内容については図１５を用いて、破線検出部１１ｇによる破線検出処理および交点補正部１１ｈによる交点補正処理の具体的な内容については図１６を用いて、それぞれ後述することとする。
【０１１５】
記憶部１２は、不揮発性メモリやハードディスクドライブといった記憶デバイスで構成される記憶部であり、入力画像１２ａと、交点情報１２ｂと、枠線情報１２ｃとを記憶する。入力画像１２ａは、画像読取装置２０から画像取得部１１ａ経由で受け取った画像であり、たとえば、手書き文字を含んだ帳票をスキャンし、２値化した原画像である。
【０１１６】
また、交点情報１２ｂは、交点抽出部１１ｃによって生成された情報であり、交点ごとの腕ベクトルの有無を示す交点種別と、各腕ベクトルが枠線抽出部１１ｅによる経路探索で用いられたか否かを示す通過済フラグと、ピクセル座標（たとえば、入力画像の左上を原点とした座標系）を含んだ情報である。なお、交点種別、通過済みフラグおよびピクセル座標を別々の情報として記憶部１２へ記憶させることとしてもよい。
【０１１７】
ここで、この交点情報１２ｂの一例について図９を用いて説明する。図９は、交点情報１２ｂの一例を示す図である。ここで、図９の（Ａ）には、交点抽出部１１ｃによって生成された直後、すなわち、枠線抽出部１１ｅによる経路探索が行われる以前の交点情報１２ｂの例を示している。また、図９の（Ｂ）には、枠線抽出部１１ｅによる経路探索が完了した時点の交点情報１２ｂの例を示している。
【０１１８】
なお、図９に示した各交点は、図４の（Ａ）や（Ｂ）に示した８個の交点にそれぞれ対応している。なお、以降の説明では、図９に示したように、罫線ＩＤ座標（ｕ，ｖ）で特定された交点を、交点ａ（０，０）、あるいは、単に、交点ａのように記載することとする。
【０１１９】
図９の（Ａ）に示すように、交点情報１２ｂは、交点の罫線ＩＤ座標ごとに、「交点種別」項目、「通過済フラグ」項目およびピクセル座標を有する情報である。たとえば、交点ａ（０，０）は、左腕、右腕、上腕および下腕の各腕ベクトルのうち、右腕および下腕の腕ベクトルを有するので、有する腕ベクトルに対応するビットが「１」となり、交点種別は「０１０１」とあらわされる。なお、通過済フラグは「００００」であり、ピクセル座標は（ｘ１、ｙ１）である。
【０１２０】
また、交点ｅ（１，１）は、左腕、右腕、上腕および下腕のうち、右腕、上腕および下腕の腕ベクトルを有するので、交点種別は「０１１１」とあらわされる。なお、通過済フラグは「００００」であり、ピクセル座標は（ｘ５、ｙ５）である。また、その他の交点についても、図９の（Ａ）に示した状態では、通過済フラグはすべて「００００」である。
【０１２１】
ところで、枠線抽出部１１ｅによる経路探索が完了した状態では、すべての腕ベクトルがすべて通過済みとなる。したがって、図９の（Ｂ）に示した状態では、すべての交点について、交点種別のビット状態と、通過済フラグのビット状態とが一致する。すなわち、枠線抽出部１１ｅは、交点種別および通過済フラグが図９の（Ｂ）のように完全一致するまで、経路探索処理を継続する。
【０１２２】
このように、交点情報１２ｂは、交点の罫線ＩＤ座標ごとに、交点の腕ベクトルの有無を含んだ情報である。なお、交点情報１２ｂを様々な用途に用いることができる。たとえば、見かけ上は異なるフォーマット（たとえば、文字が入りきれずに枠を拡張した場合など）であっても、交点の個数と、交点の交点種別とが同一であることをもって同一のフォーマットとみなすことができる。また、枠内に空白が多い場合には、文字の読み取り後に、該当する枠を交点種別の関係を崩さない程度に縮小して保存することも可能となる。
【０１２３】
次に、枠線抽出部１１ｅによって行われる枠線抽出処理の詳細な内容について、図１０〜図１２を用いて説明する。図１０は、経路探索の優先順位を示す図である。なお、同図の（Ａ）には、外周の探索を時計回りで行う場合の優先順位を、同図の（Ｂ）には、外周の探索を反時計回りで行う場合の優先順位を、それぞれ示している。
【０１２４】
図１０の（Ａ）および（Ｂ）に示したように、枠線抽出部１１ｅは、外周探索の周回方向と、内周探索の周回方向とを逆方向に行う点に特徴がある。このように、外周探索の周回方向と、内周探索の周回方向とを逆にすることで、すべての腕ベクトルを１回ずつ通過したことをもって、経路探索が完了したことを検出することができる。なお、この点の詳細については、図１１および図１２を用いて後述する。
【０１２５】
図１０の（Ａ）に示したように、枠線抽出部１１ｅは、外周の探索を時計回りで行う場合には、内周の探索を反時計回りで行う。また、枠線抽出部１１ｅは、経路探索で通過しようとする交点に未通過の腕ベクトルが複数ある場合には、左折を最も優先し、直進を次に優先し、右折を最も優先しない。
【０１２６】
たとえば、通過しようとする交点における未通過の腕ベクトルが進路を左折する向きと、進路を直進する向きと、進路を右折する向きとの３つがある場合には、枠線抽出部１１ｅは、通過しようとする交点で左折する向きの腕ベクトルを選択する。
【０１２７】
また、通過しようとする交点における未通過の腕ベクトルが進路を左折する向きと、進路を右折する向きとの２つがある場合には、枠線抽出部１１ｅは、通過しようとする交点で左折する向きの腕ベクトルを選択する。なお、未通過の腕ベクトルが進路を直進する向きと、進路を右折する向きとの２つがある場合には、枠線抽出部１１ｅは、通過しようとする交点を直進する向きの腕ベクトルを選択する。
【０１２８】
これに対し、図１０の（Ｂ）に示したように、枠線抽出部１１ｅは、外周の探索を反時計回りで行う場合には、内周の探索を時計回りで行う。また、枠線抽出部１１ｅは、経路探索で通過しようとする交点に未通過の腕ベクトルが複数ある場合には、右折を最も優先し、直進を次に優先し、左折を最も優先しない。
【０１２９】
このように、枠線抽出部１１ｅは、外周を時計回りで探索する場合（図１０の（Ａ）の場合）であっても、外周を反時計回りで探索する場合（図１０の（Ｂ）の場合）であっても、外周探索の場合には、探索経路で囲まれる閉領域の面積がなるべく大きくなるように未通過の腕ベクトルを選択していく。逆に、内周探索の場合には、探索経路で囲まれる閉領域の面積がなるべく小さくなるように未通過の腕ベクトルを選択していく。
【０１３０】
次に、枠線抽出部１１ｅによる外周経路探索および内周経路探索の例について図１１および図１２を用いて説明する。図１１は、外周経路探索の一例であり、図１２は、内周経路探索の一例である。
【０１３１】
なお、図１１および図１２には、外周経路探索を時計回りで行った場合（図１１の矢印１１１参照）、すなわち、内周経路探索を反時計回りで行った場合（図１２の矢印１２１および矢印１２３参照）の例を示している。また、図１１および図１２では、未通過の腕ベクトルを「黒矢印」で、通過済みの腕ベクトルを「白抜き矢印」で、それぞれ示している。
【０１３２】
図１１の（Ａ）に示したように、外周経路の探索前には、交点ａ〜交点ｈの腕ベクトルはすべて「黒矢印」である。まず、枠線抽出部１１ｅは、交点ａ〜交点ｈの中から、経路探索の始点となる交点を選択する。たとえば、枠線抽出部１１ｅは、ｕ座標またはｖ座標が最も大きい交点あるいは最も小さい交点を選択する。
【０１３３】
図１１の（Ｂ−１）に示したのは、外周経路探索の始点として、ｕ座標およびｖ座標が最も小さい交点である交点ａを選択した場合である。この場合、外周経路探索は時計回りであるので、枠線抽出部１１ｅは、交点ａの腕ベクトルのうち右向きの腕ベクトルを選択する。ここで、ｕ座標またはｖ座標が最も大きい交点または小さい交点を選択した場合の外周探索の始点となりうる交点パターン（図４の（Ｃ）に対応）と、探索開始時に選択する腕ベクトルの向きとを図１１の（Ｃ）に示している。図１１の（Ｂ−１）に示した場合では、周回方向が時計回りであるので、交点パターンがパターンＡである交点ａから探索を開始する際に選択される腕ベクトルは右向きである。
【０１３４】
そして、交点ｄを通過する場合には、左折および直進ができないので、右折することになり、枠線抽出部１１ｅは、下向きの腕ベクトルを選択する。つづいて、交点ｅを通過する場合には、進行方向について、左折または直進の選択肢があるが、左折を優先するので、右向きの腕ベクトルを選択する。また、交点ｇを通過する場合には、選択肢が右折しかないので、下向きの腕ベクトルを選択する。以下、同様に、交点ｈでは左向きの腕ベクトルを選択し、交点ｃでは上向きの腕ベクトルを選択する。
【０１３５】
また、交点ｂでは、直進または右折の選択肢があるが、直進を優先するので、上向きの腕ベクトルを選択する。そして、外周経路探索の始点である交点ａに戻ったならば、枠線抽出部１１ｅは、交点ａを始点とし、交点ｄ、交点ｅ、交点ｇ、交点ｈ、交点ｃおよび交点ｂを通過して交点ａに戻る経路１１２を、確定した外周経路として枠線情報１２ｃへ記録する。
【０１３６】
なお、上記した外周経路探索で通過した交点については、図１１の（Ｂ−２）に示したように、選択した腕ベクトルに対応する通過済フラグを更新する。なお、仮に、始点に戻らなかった場合には、異なる腕ベクトルから出発するか、異なる始点から出発すればよい。なお、ｕ座標またはｖ座標が最も大きい交点、ｕ座標またはｖ座標が最も小さい交点を始点として選択し、図１１の（Ｃ）に示した向きで出発すれば必ず始点に戻るが、始点または出発向きを任意に選択すると、始点に戻れない場合がある。ただし、すべての始点またはすべての出発向きで総当たりの探索を行えば、外周経路を必ず見つけることができる。
【０１３７】
次に、図１１に示した外周経路探索につづいて行われる内周経路探索について図１２を用いて説明する。なお、図１２に示した内周経路探索では、図１１における外周経路探索で通過済みとなった各腕ベクトル（白抜き矢印）を引き継ぐ。なお、探索すべき内周経路が２つあるため、１つめの内周経路探索を図１２の（Ａ−１）および（Ａ−２）に、２つめの内周経路探索を図１２の（Ｂ−１）および（Ｂ−２）に、それぞれ示している。
【０１３８】
図１２の（Ａ−１）に示したように、１つめの内周経路探索では、たとえば、交点ａを始点として、矢印１２１に示すように反時計回りで経路探索が行われる。ここで、内周経路探索の始点とする交点は、外周経路探索後に未通過の腕ベクトルをもつ交点であればいずれの交点でもよく、出発時の腕ベクトルも未通過であれば、いずれの腕ベクトルから出発してもよい。なお、内周経路探索を反時計回りに行う場合には、図１１に示した外周経路探索と同様に、左折を最も優先し、直進を次に優先し、右折を最も優先しない（図１０の（Ａ）参照）。
【０１３９】
まず、図１２の（Ａ−１）に示したように、枠線抽出部１１ｅは、交点ａの未通過の腕ベクトルである下向きの腕ベクトルを選択する。そして、交点ｂを通過する場合には、進行方向について左折または直進の選択肢があるが、左折を優先するので、右向きの腕ベクトルを選択する。
【０１４０】
また、交点ｆでは、選択肢が左折しかないので、上向きの腕ベクトルを選択する。そして、交点ｅでは、左折の選択肢はないが、直進の選択肢はあるので、上向きの腕ベクトルを選択し、交点ｄでは、選択肢が左折しかないので、左向きの腕ベクトルを選択する。
【０１４１】
このようにして、始点である交点ａに戻ったならば、枠線抽出部１１ｅは、交点ａを始点とし、交点ｂ、交点ｆ、交点ｅおよび交点ｄを通過して交点ａに戻る経路１２２を、確定した内周経路として枠線情報１２ｃへ記録する。なお、経路探索時に通過した交点については、図１２の（Ａ−２）示したように、選択した腕ベクトルに対応する通過済フラグを更新する。ここで、外周経路探索後の内周探索においては、優先順位に従って選択した未通過の腕ベクトルの向きに進めば必ず始点に戻る。
【０１４２】
また、図１２の（Ｂ−１）に示したように、２つめの内周経路探索では、たとえば、交点ｇを始点として、矢印１２３に示すように反時計回りで経路探索が行われる。なお、左折を最も優先し、直進を次に優先し、右折を最も優先しない（図１０の（Ａ）参照）点については図１２の（Ａ−１）と同様である。
【０１４３】
まず、図１２の（Ｂ−１）に示したように、枠線抽出部１１ｅは、交点ｇの未通過の腕ベクトルである左向きの腕ベクトルを選択する。そして、交点ｅを通過する場合には、進行方向について未通過の腕ベクトルの向きは左折しかないので、下向きの腕ベクトルを選択する。
【０１４４】
また、交点ｆでは、選択肢が右折しかないので、左向きの腕ベクトルを選択し、交点ｂでは、選択肢が左折しかないので、下向きの腕ベクトルを選択する。また、交点ｃでは、選択肢が左折しかないので、右向きの腕ベクトルを選択し、交点ｈでは、選択肢が左折しかないので、上向きの腕ベクトルを選択する。
【０１４５】
このようにして、始点である交点ｇに戻ったならば、枠線抽出部１１ｅは、交点ｇを始点とし、交点ｅ、交点ｆ、交点ｂ、交点ｃおよび交点ｈを通過して交点ｇに戻る経路１２４を、確定した内周経路として枠線情報１２ｃへ記録する。なお、経路探索時に通過した交点については、図１２の（Ｂ−２）に示したように、選択した腕ベクトルに対応する通過済フラグを更新する。
【０１４６】
次に、枠線抽出部１１ｅによって更新される枠線情報１２ｃの例について図１３を用いて説明する。図１３は、枠線情報１２ｃの一例を示す図である。
【０１４７】
図１３に示したように、枠線情報１２ｃは、図８を用いて説明したグループを示す「グループ」項目と、外周経路探索か内周経路探索かの区別を示す「周回種別」項目とを含んでいる。また、枠線情報１２ｃは、確定された枠線の識別子に相当する「枠線番号」項目と、確定した経路を構成する交点を示す「経路」項目とを含んでいる。
【０１４８】
なお、図１３に示した「枠線番号」項目が「１」の経路は、図１１の（Ｂ−２）で確定した外周経路に対応している。また、図１３に示した「枠線番号」項目が「２」の経路および「３」の経路は、それぞれ、図１２の（Ａ−２）および（Ｂ−２）で確定した内周経路に対応している。
【０１４９】
このため、「枠線番号」項目が「１」の「周回種別」項目は「外周」であり、「枠線番号」項目が「２」および「３」の「周回種別」項目は「内周」である。なお、図１３に示した場合では、「グループ」項目はすべて「Ａ」となっているが、図８に示した場合のように、複数のグループが検出された場合には、各グループに対応する識別子がそれぞれ格納されることになる。
【０１５０】
次に、枠線抽出部１１ｅによって行われる枠線補正処理の詳細な内容について図１４を用いて説明する。ここで、枠線補正処理とは、検出された枠線のうち、「１つの線分でつながる枠線」および「１つの交点でつながる枠線」を、複数の枠線へ分離する処理のことを指す。
【０１５１】
図１４は、枠線補正処理の説明図である。図１４の（Ａ）に示した４つのパターンは、分離すべき枠線の代表的なパターンである。なお、図１４の（Ａ）では、罫線のパターンに対してアルファベットなしの符号（たとえば、１４１）を、検出された枠線に対して「ａ」付きの符号（たとえば、１４１ａ）を付している。
【０１５２】
また、図１４の（Ａ）では、枠線を接続する部分に対して「ｂ」付きの符号（たとえば、１４１ｂ）を、分離された枠線に対して「ｃ」または「ｄ」付きの符号（たとえば、１４１ｃおよび１４１ｄ）を、付している。
【０１５３】
ここで、図１４の（Ａ）に示したように、４つのパターンのうち、左側の２つが、「１つの線分でつながる枠線」に対応するパターンであり、右側の２つが、「１つの交点でつながる枠線」に対応するパターンである。枠線抽出部１１ｅは、図１４の（Ａ）に示したパターンを検出した場合に、枠線を分離する処理を行う。
【０１５４】
具体的には、枠線抽出部１１ｅは、枠線の中継点となる交点の中に複数回通過している交点がある場合に、分離すべき枠線であると判定する。そして、枠線抽出部１１ｅは、複数回通過している交点に内接する点が一致するか否かに基づき、「１つの線分でつながる枠線」であるか、「１つの交点でつながる枠線」であるかを判定する。
【０１５５】
たとえば、図１４の（Ｂ）に示したように、枠線抽出部１１ｅは、枠線の中継点の中で複数回通過している交点（同図では「交点ｃ」）、すなわち、一致点を検出する（図１４の（Ｂ−１）参照）。
【０１５６】
つづいて、枠線抽出部１１ｅは、一致点にそれぞれ内接する２つの点が一致しているか否かを判定する。ここで、図１４の（Ｂ）に示した場合では、一致点にそれぞれ内接する２つの点（同図では「交点ｆ」）が一致しているので（図１４の（Ｂ−２）参照）、枠線抽出部１１ｅは、「１つの線分でつながる枠線」、すなわち、「線分結合」と判定する。
【０１５７】
そして、枠線抽出部１１ｅは、枠線を、２つの一致点（同図では「交点ｃ」）の内側と外側との２つの枠線へ分離する。なお、「線分結合」の場合、片方の一致点は削除する（図１４の（Ｂ−３）参照）。このようにして、枠線抽出部１１ｅは、１つの経路を、「ａ、ｂ、ｃ、ｄおよびａ」という経路と、「ｆ、ｇ、ｈ、ｅおよびｆ」という経路とに分離する。
【０１５８】
また、図１４の（Ｃ）に示したように、枠線抽出部１１ｅは、枠線の中継点の中で複数回通過している交点（同図では「交点ｃ」）、すなわち、一致点を検出する（図１４の（Ｃ−１）参照）。
【０１５９】
つづいて、枠線抽出部１１ｅは、一致点にそれぞれ内接する２つの点が一致しているか否かを判定する。ここで、図１４の（Ｃ）に示した場合では、一致点にそれぞれ内接する２つの点（同図では「交点ｅ」および「交点ｇ」）が相違しているので（図１４の（Ｃ−２）参照）、枠線抽出部１１ｅは、「１つの交点でつながる枠線」、すなわち、「点結合」と判定する。
【０１６０】
そして、枠線抽出部１１ｅは、枠線を、２つの一致点（同図では「交点ｃ」）の内側と外側との２つの枠線へ分離する（図１４の（Ｃ−３）参照）。なお、「点結合」の場合、片方の一致点を分離後の枠線でそれぞれ用いる。このようにして、１つの経路を、枠線抽出部１１ｅは、「ａ、ｂ、ｃ、ｄおよびａ」という経路と、「ｃ、ｅ、ｆ、ｇおよびｃ」という経路とに分離する。
【０１６１】
次に、枠線内画像抽出部１１ｆによる枠線内画像抽出処理の具体的な内容について図１５を用いて説明する。図１５は、枠線内画像抽出処理の説明図である。なお、ここでは、図１５の（Ａ）に示すように、枠線抽出部１１ｅによって凹型の枠線が抽出された場合について説明する。
【０１６２】
図１５の（Ａ）に示したように、枠線内画像抽出部１１ｆは、枠線１５１をすべて含み、かつ、枠線よりも若干大きい領域１５２を、入力画像１２ａから切り出す。ここで、枠線を構成する経路の各交点に対応してピクセル座標（たとえば、入力画像の左上を原点とした座標系）が保持されており、かかるピクセル座標を用いて上記した切り出し処理および以降の処理が行われる。なお、同図では、領域１５２が矩形である場合を示しているが、枠線１５１の形状に合わせる（たとえば、枠線１５１が凹型であれば凹型の形状など）こととしてもよい。
【０１６３】
つづいて、図１５の（Ｂ）に示したように、枠線内画像抽出部１１ｆは、所定の傾きを有する直線１５３を同図に示す矢印の方向へ平行移動させることで、経路を構成する線分との交点を検出する。なお、検出された交点は「●」で示している。
【０１６４】
そして、枠線内画像抽出部１１ｆは、直線１５３上の最初の交点までは「外」、次の交点までは「内」、さらに次の交点までは「外」という判定を交互に繰り返すことで、直線１５３上の各画素が枠線の「外」に対応するか、「内」に対応するかを決定する。
【０１６５】
ここで、入力画像１２ａから切り出した領域１５２の各画素は、「黒」か「白」の２値画像であるので、枠線内画像抽出部１１ｆは、「内」の画素についてはそのまま、「外」の画素については「灰色」のような他の画素値へ変更する。このようにして、枠線内画像抽出部１１ｆは、図１５の（Ｃ）に入力画像として示した画像データを得る。
【０１６６】
そして、枠線内画像抽出部１１ｆは、連続する「黒画素」をラベル化するいわゆるラベリング処理を行う（図１５の（Ｃ−１）参照）。なお、同図に示した場合では、ラベル１５２ａと、ラベル１５２ｂと、ラベル１５２ｃと、ラベル１５２ｄとが得られている。
【０１６７】
また、枠線内画像抽出部１１ｆは、図１５の（Ｃ）に示した入力画像における「灰色」の領域を「黒」、入力画像における「白」または「黒」の領域を「白」とした２値画像である有効領域画像１５４を得る。ここで、有効領域画像１５４の「白」画素は、「有効エリア」に対応し、「黒」画素は、「無効エリア」に対応している。
【０１６８】
つづいて、枠線内画像抽出部１１ｆは、有効領域画像１５４の有効エリアを所定回数（ｎ回）収縮させる処理を行う（図１５の（Ｃ−２）参照）。これにより、有効領域が「痩せた」有効領域画像１５４ａが得られる。なお、このように、有効エリアの収縮処理を行うのは、有効エリアに対応する経路内画像を文字認識対象領域として取り扱うと、枠線自体が含まれる場合があり、枠線を文字と誤認識してしまうおそれがあるためである。
【０１６９】
このように、ラベリングが完了した領域１５２と、有効エリアを収縮させた有効領域画像１５４ａとが得られると、枠線内画像抽出部１１ｆは、両画像を重ね合わせる（図１５の（Ｃ−３）参照）。そして、有効領域画像１５４ａの無効領域に部分的に含まれるラベルは残し（図１５の（Ｃ−４）参照）、完全に無効領域に含まれるラベルはノイズとみなして削除する。
【０１７０】
具体的には、図１５の（Ｃ）に示した場合では、無効領域に完全に含まれるラベル１５２ａは削除されるが、その一部が無効領域に含まれるラベル１５２ｂ、ラベル１５２ｃおよびラベル１５２ｄは残されている。
【０１７１】
このように、枠線内画像抽出部１１ｆは、残存するラベルからなる画像を枠線内画像１２ｄとして、記憶部１２へ記憶させる。そして、破線検出部１１ｇは、記憶部１２から読み出した枠線内画像１２ｄに含まれるラベルの位置関係などに基づいて破線を検出する処理を行うことになる。
【０１７２】
次に、破線検出部１１ｇによって行われる破線検出処理の具体的な内容について図１６を用いて説明する。図１６は、破線検出処理の説明図である。なお、図１６の（Ａ）に示した画像１６１は、枠線内画像抽出部１１ｆから渡された枠線内画像１２ｄの一例であり、同図において破線で囲まれた領域は、各ラベルを示している。
【０１７３】
ここで、図１６の（Ａ）に示したように、破線検出部１１ｇは、各ラベルの高さおよび幅を検出する。なお、同図では、ラベル１６１ｂの高さｈ１および幅ｗ１のみを例示しているが、すべてのラベルについて高さおよび幅が検出される。
【０１７４】
そして、破線検出部１１ｇは、高さまたは幅のうちいずれかが所定値α以上の場合、または、高さまたは幅のいずれかがαよりも小さい所定値β以上でラベル内の黒画素占有率が所定値以下（たとえば、５０％以下）の場合に、該当するラベルを破線候補から削除する。
【０１７５】
このようにして、図１６の（Ｂ）に示したように、ラベル１６１ｂ、ラベル１６１ｃおよび１６１ｄは破線候補から削除される。一方、矩形状の９つのラベル１６１ａ（図１６の（Ａ）参照）は、削除されない。つづいて、破線検出部１１ｇは、図１６の（Ａ）に示したｘ座標が重なり合うラベル同士をグループ化する。ただし、対象となるラベルが２個以下の場合にはグループ化しない。このようにして、グループ１６２ａと、グループ１６２ｂとが得られる。
【０１７６】
なお、図１６の（Ｂ）では、垂直方向の破線を検出する場合について示しているが、水平方向の破線を検出する場合には、ｙ座標が重なり合うラベル同士をグループ化することとすればよい。
【０１７７】
つづいて、破線検出部１１ｇは、図１６の（Ｃ）に示したように、グループに含まれる各ラベルの高さ（同図ではｈ２）、グループ内に含まれる各ラベルの中心ピッチ（同図ではｐ１、ｐ２およびｐ３）を、それぞれ検出する。なお、同図では、記載を省略しているが、ラベルの高さおよびピッチの検出は、グループに含まれるすべてのラベルについて行われる。
【０１７８】
そして、破線検出部１１ｇは、グループ内の各ラベルの高さ（ｈ２）の総和を枠線内画像１６１の高さ（ｈ３）で除した値が、所定値以上（たとえば、５０％以上）であるグループを破線候補として残し、その他のグループを削除する。また、破線検出部１１ｇは、グループ内のラベルにおける中心ピッチの標準偏差を算出し、算出した標準偏差が所定値以下であるグループを破線候補として残し、その他のグループを削除する。
【０１７９】
つづいて、図１６の（Ｄ）に示したように、破線検出部１１ｇは、枠線内画像１６１の右辺または左辺から残存しているグループのｘ座標までの距離（Ｗ２）が所定値以下の場合に、該当するグループを削除する。
【０１８０】
ここで、枠線内画像１６１の右辺または左辺に近いグループを削除するのは、文字を入力するための枠として、たとえば、記入可能な大きさの文字よりも狭い枠は不自然であるためである。なお、水平方向の破線を検出する場合には、枠線内画像１６１の上辺または下辺からの距離を用いて同様の処理を行えばよい。
【０１８１】
このようにして、最終的に、図１６の（Ｃ）に示したグループ１６２ｂが、破線として確定される。そして、破線検出部１１ｇは、確定した破線に関する情報を交点補正部１１ｈへ渡し、交点補正部１１ｈは、グループ１６２ｂに相当する線分１６３が、枠線内画像の上辺と交わる点をあらたな交点１６４とするとともに、下辺と交わる点をあらたな交点１６５とし、交点情報１２ｂを更新する。また、交点補正部１１ｈは、グループ化部１１ｄへ更新後の交点情報１２ｂに基づいて再度のグループ化処理を行うように指示する。
【０１８２】
次に、枠線認識装置１０が実行する処理手順について図１７〜図１９を用いて説明する。図１７は、枠線認識装置１０が実行する処理手順を示すフローチャートである。図１７に示すように、罫線抽出部１１ｂが罫線抽出処理を行うと（ステップＳ１０１）、交点抽出部１１ｃは、交点抽出処理を行う（ステップＳ１０２）。
【０１８３】
なお、ステップＳ１０１の罫線抽出処理の詳細な処理手順については図１８を用いて、ステップＳ１０２の交点抽出処理の詳細な処理手順については図１９を用いて、それぞれ後述する。
【０１８４】
つづいて、グループ化部１１ｄが、交点のグルーピング（グループ分け）を行うと（ステップＳ１０３）、枠線抽出部１１ｅは、１つのグループを選択し（ステップＳ１０４）、外周経路探索を行うとともに（ステップＳ１０５）、内周経路探索を行う（ステップＳ１０６）。
【０１８５】
さらに、枠線抽出部１１ｅは、探索経路の分離を行い、分離後の経路を枠線情報１２ｃとして記憶部１２へ記憶させる（ステップＳ１０７）。そして、枠線抽出部１１ｅは、経路が分離されたか否かを判定し（ステップＳ１０８）、経路が分離されなかった場合には（ステップＳ１０８，Ｎｏ）、入力画像１２ａから枠線内画像１２ｄの抽出を行い（ステップＳ１０９）、破線検出部１１ｇは、破線の検出処理を行う（ステップＳ１１０）。なお、ステップＳ１０８にて、経路が分離されたと判定された場合には（ステップＳ１０８，Ｙｅｓ）、グループが変更されるため、ステップＳ１０３以降の処理を繰り返す。
【０１８６】
そして、全グループについての処理が完了したか否かを判定し（ステップＳ１１１）、全グループについての処理が終了した場合には（ステップＳ１１１，Ｙｅｓ）、ステップＳ１０９にて破線が検出されたグループがあるか否かを判定する（ステップＳ１１２）。なお、ステップＳ１１１の判定条件を満たさなかった場合には（ステップＳ１１１，Ｎｏ）、ステップＳ１０４以降の処理を繰り返す。
【０１８７】
そして、ステップＳ１１２にて、破線が検出されたと判定された場合には（ステップＳ１１２，Ｙｅｓ）、ステップＳ１０３以降の処理を繰り返し、破線の検出がないと判定された場合には（ステップＳ１１２，Ｎｏ）、処理を終了する。
【０１８８】
次に、図１７のステップＳ１０１に示した罫線抽出処理の詳細な処理手順について図１８を用いて説明する。図１８は、罫線抽出処理の処理手順を示すフローチャートである。図１８に示すように、罫線抽出部１１ｂは、入力画像１２ａに対して１／１６最小値圧縮を行い（ステップＳ２０１）、圧縮後の入力画像１２ａについて、水平方向および垂直方向のランレンを算出する（ステップＳ２０２）。
【０１８９】
つづいて、罫線抽出部１１ｂは、所定値以下のランレンを削除するとともに（ステップＳ２０３）、残ったランレンに対して罫線方向圧縮を行う（ステップＳ２０４）。そして、罫線方向圧縮によってあらたに検出された罫線を含んだすべての罫線を対象としたうえで、水平罫線および垂直罫線それぞれに罫線ＩＤを付与し（ステップＳ２０５）、処理を終了する。
【０１９０】
次に、図１７のステップＳ１０２に示した交点抽出処理の詳細な処理手順について図１９を用いて説明する。図１９は、交点抽出処理の処理手順を示すフローチャートである。図１９に示すように、交点抽出部１１ｃは、水平罫線と垂直罫線とが交わる部分を抽出する（ステップＳ３０１）。
【０１９１】
つづいて、交点抽出部１１ｃは、各交点について交点種別および罫線ＩＤ座標を付与し（ステップＳ３０２）、交点が１つの線分の結合および削除を行う（ステップＳ３０３）。そして、ステップＳ３０３の処理で結合および削除後の交点情報１２ｂを生成し（ステップＳ３０４）、記憶部１２へ記憶させたうえで、処理を終了する。
【０１９２】
上述してきたように、本実施例では、交点抽出部が、入力画像から抽出した罫線同士の交点を抽出し、記憶部が、交点に属する各罫線に沿ってこの交点からそれぞれ遠ざかる向きの腕ベクトルと、この腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶するように枠線認識装置を構成した。
【０１９３】
また、本実施例では、枠線抽出部が、所定の交点を始点として腕ベクトルの向きに従った経路探索を行うことによって閉じた経路が検出された場合に、この閉じた経路を枠線として抽出し、閉じた経路の検出に用いられた腕ベクトルに対応するフラグを使用済みへ更新し、すべてのフラグが使用済みへ更新された場合に、経路探索を終了させるように枠線認識装置を構成した。したがって、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる。
【０１９４】
なお、上述した実施例では、様々な形状の枠内領域を確実に認識することができるため、検出した枠内領域単位で、文字抽出に用いる閾値を変更するといった処理への応用が容易である。また、上述した実施例では、スキャナ装置（画像読取装置）とは独立した枠線認識装置について説明したが、スキャナ装置を含んだ枠線認識装置を構成することとしてもよい。また、枠線認識装置にいわゆるＯＣＲ（Optical Character Reader）機能を持たせ、認識した枠線内領域に対応する画像の文字認識を行わせることとしてもよい。
【産業上の利用可能性】
【０１９５】
以上のように、本発明に係る枠線認識装置および枠線認識方法は、枠線によって囲まれた様々な形状の対象領域を確実に認識したい場合に有用であり、特に、フリーフォーマットの帳票から、手書き文字等の文字を抽出したい場合に適している。
【符号の説明】
【０１９６】
１０ 枠線認識装置
１１ 制御部
１１ａ 画像取得部
１１ｂ 罫線抽出部
１１ｃ 交点抽出部
１１ｄ グループ化部
１１ｅ 枠線抽出部
１１ｆ 枠線内画像抽出部
１１ｇ 破線検出部
１１ｈ 交点補正部
１２ 記憶部
１２ａ 入力画像
１２ｂ 交点情報
１２ｃ 枠線情報
１２ｄ 枠線内画像
２０ 画像読取装置
【技術分野】
【０００１】
この発明は、入力画像から枠線を認識する枠線認識方法および枠線認識装置に関する。
【背景技術】
【０００２】
従来、帳票に記入された手書き文字などを認識するＯＣＲ（Optical Character Reader）技術が広く知られている。また、ＯＣＲ技術では、枠線で囲まれた領域（以下、「対象領域」と記載する）に記入された手書き文字を認識することが一般的に行われており、かかる対象領域自体を認識する技術が併用されている。
【０００３】
ここで、対象領域を認識する技術としては、帳票のフォーマットごとに、枠線で囲まれた領域のピクセル座標（たとえば、入力画像の左上を原点とした座標系）を予め登録しておき、登録されたピクセル座標に基づいて対象領域を認識する手法がある。
【０００４】
しかし、フォーマットを予め登録しておく手法を用いると、読み取り対象となる帳票のフォーマットが多岐にわたる場合には、フォーマットを登録する作業が繁雑となる。また、フォーマット自体が定められていない場合には、そもそも対象領域を認識することができない。
【０００５】
このため、帳票のフォーマットの登録を必要としない枠線認識装置が提案されている。たとえば、特許文献１には、入力画像から抽出した枠線のエッジに対して方向コードを付与し、方向コードの変化を検出して枠線で囲まれた領域、すなわち、対象領域を認識する技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３５８６９１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１の技術では、対象領域が正方形や長方形といった矩形である場合には、対象領域の認識が可能であるものの、たとえば、凹型や凸型といった非矩形の形状をもつ対象領域については、認識することができないという問題があった。
【０００８】
特に、近年では、デザインや用途の多様性に応じて帳票のフォーマットも多岐にわたっており、また、１枚ごとにデザインが異なる帳票が用いられる場合もあることから、かかる問題が顕在化してきている。
【０００９】
これらのことから、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる枠線認識方法あるいは枠線認識装置をいかにして実現するかが大きな課題となっている。
【００１０】
本発明は、上述した従来技術による問題点を解消するためになされたものであって、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる枠線認識方法および枠線認識装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、本発明は、入力画像から枠線を認識する枠線認識方法であって、前記入力画像から抽出した罫線同士の交点を抽出する交点抽出工程と、前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶部へ記憶させる交点情報記憶工程と、所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出工程と、前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新工程と、前記更新工程によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出工程による前記経路探索を終了させる終了工程とを含んだことを特徴とする。
【００１２】
また、本発明は、上記の発明において、前記交点抽出工程は、前記入力画像から第１の方向の罫線を抽出して第１の識別子をそれぞれ付与するとともに、前記入力画像から前記第１の方向と垂直な第２の方向の罫線を抽出して第２の識別子をそれぞれ付与し、前記第１の識別子および前記第２の識別子の組み合わせで前記交点を特定することを特徴とする。
【００１３】
また、本発明は、上記の発明において、前記枠線抽出工程は、お互いにつながった前記罫線を１つのグループとし、前記グループごとに前記経路探索を行うことを特徴とする。
【００１４】
また、本発明は、上記の発明において、前記枠線抽出工程は、前記罫線で囲まれた閉領域における外周の前記経路探索の周回方向と、内周の前記経路探索の周回方向とを逆方向としたことを特徴とする。
【００１５】
また、本発明は、上記の発明において、前記枠線抽出工程は、前記経路探索において前記交点の前記腕ベクトルの向きが複数ある場合には、前記外周の前記経路探索であれば前記閉領域の外側へ向かう向きを優先して前記腕ベクトルを選択し、前記内周の前記経路探索であれば前記閉領域の内側へ向かう向きを優先して前記腕ベクトルを選択することを特徴とする。
【００１６】
また、本発明は、上記の発明において、前記枠線抽出工程は、抽出した前記枠線が同一の前記交点を複数回通過するものである場合に、当該枠線を当該交点で複数の前記枠線へ分割することを特徴とする。
【００１７】
また、本発明は、上記の発明において、前記交点抽出工程は、前記罫線における前記交点ではない先端を延長した延長線を生成し、当該延長線が他の罫線の延長線または前記他の罫線自体と最初に交わる点を仮交点としたうえで、前記先端を含んだ所定の領域内に当該先端と前記他の罫線をつなぐ経路が存在する場合に、当該仮交点を前記交点として抽出することを特徴とする。
【００１８】
また、本発明は、入力画像から枠線を認識する枠線認識装置であって、前記入力画像から抽出した罫線同士の交点を抽出する交点抽出手段と、前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶する交点情報記憶手段と、所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出手段と、前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新手段と、前記更新手段によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出手段による前記経路探索を終了させる終了手段とを備えたことを特徴とする。
【発明の効果】
【００１９】
本発明によれば、入力画像から抽出した罫線同士の交点を抽出し、交点に属する各罫線に沿ってこの交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、この腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶部へ記憶させ、所定の交点を始点として腕ベクトルの向きに従った経路探索を行うことによって閉じた経路が検出された場合に、この閉じた経路を枠線として抽出し、閉じた経路の検出に用いられた腕ベクトルに対応するフラグを使用済みへ更新し、すべてのフラグが使用済みへ更新された場合に、経路探索を終了させることとしたので、枠線によって囲まれた様々な形状の対象領域を確実に認識することができるという効果を奏する。
【００２０】
また、本発明によれば、入力画像から第１の方向の罫線を抽出して第１の識別子をそれぞれ付与するとともに、入力画像から第１の方向と垂直な第２の方向の罫線を抽出して第２の識別子をそれぞれ付与し、第１の識別子および第２の識別子の組み合わせで交点を特定することとしたので、簡便な処理で交点を特定することができるという効果を奏する。
【００２１】
また、本発明によれば、お互いにつながった罫線を１つのグループとし、グループごとに経路探索を行うこととしたので、入れ子や重なりといった複雑な形状を有する罫線であっても確実に認識することができるという効果を奏する。
【００２２】
また、本発明によれば、罫線で囲まれた閉領域における外周の経路探索の周回方向と、内周の経路探索の周回方向とを逆方向としたので、腕ベクトルに対応するフラグがすべて通過済みとなったことを探索終了の条件とすることができ、重複した経路探索を防止することができるという効果を奏する。
【００２３】
また、本発明によれば、経路探索において交点の腕ベクトルの向きが複数ある場合には、外周の経路探索であれば閉領域の外側へ向かう向きを優先して腕ベクトルを選択し、内周の経路探索であれば閉領域の内側へ向かう向きを優先して腕ベクトルを選択することとしたので、凹型や凸型といった複雑な形状の枠線を確実に認識することができるという効果を奏する。
【００２４】
また、本発明によれば、抽出した枠線が同一の交点を複数回通過するものである場合に、枠線をこの交点で複数の枠線へ分割することとしたので、表の構成としては不自然なつながりを有する枠線を分割することで、文字やノイズの影響による枠線の誤認識を防止することができるという効果を奏する。
【００２５】
また、本発明によれば、罫線における交点ではない先端を延長した延長線を生成し、この延長線が他の罫線の延長線または他の罫線自体と最初に交わる点を仮交点としたうえで、先端を含んだ所定の領域内にこの先端と他の罫線をつなぐ経路が存在する場合に、仮交点を交点として抽出することとしたので、角が丸い枠線を確実に認識することができるという効果を奏する。
【図面の簡単な説明】
【００２６】
【図１】図１は、本発明に係る枠線認識手法の概要を示す図である。
【図２】図２は、本実施例に係る枠線認識装置の構成を示すブロック図である。
【図３】図３は、罫線抽出処理の説明図である。
【図４】図４は、交点抽出処理の説明図である。
【図５】図５は、交点補正処理その１の説明図である。
【図６】図６は、交点補正処理その２の説明図である。
【図７】図７は、交点補正処理その３の説明図である。
【図８】図８は、交点グループ化処理の説明図である。
【図９】図９は、交点情報の一例を示す図である。
【図１０】図１０は、経路探索の優先順位を示す図である。
【図１１】図１１は、外周経路探索の一例を示す図である。
【図１２】図１２は、内周経路探索の一例を示す図である。
【図１３】図１３は、枠線情報の一例を示す図である。
【図１４】図１４は、枠線補正処理の説明図である。
【図１５】図１５は、枠線内画像抽出処理の説明図である。
【図１６】図１６は、破線検出処理の説明図である。
【図１７】図１７は、枠線認識装置が実行する処理手順を示すフローチャートである。
【図１８】図１８は、罫線抽出処理の処理手順を示すフローチャートである。
【図１９】図１９は、交点抽出処理の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００２７】
以下に、添付図面を参照して、本発明に係る枠線認識手法の好適な実施例を詳細に説明する。なお、以下では、本発明に係る枠線認識手法の概要について図１を用いて説明した後に、本発明に係る枠線認識手法を適用した枠線認識装置についての実施例を図２〜図１９を用いて説明する。
【００２８】
まず、本発明に係る枠線認識手法の概要について図１を用いて説明する。図１は、本発明に係る枠線認識手法の概要を示す図である。なお、同図では、手書き文字を含んだ帳票をスキャンした入力画像１から枠線を検出し、最終的に、枠線で囲まれた領域（以下、「枠線内領域」と記載する）を確定するまでの手順を示している。
【００２９】
なお、「罫線」という用語は、入力画像１から抽出された直線を指す場合に用い、「枠線」という用語は、後述する経路探索によって検出された閉じた経路を指す場合に用いることとする。また、入力画像は、あらかじめ２値化されているものとする。
【００３０】
図１に示すように、本発明に係る枠線認識手法は、入力画像１から検出した水平罫線および垂直罫線の各交点について、交点に属する罫線の向きを示す腕ベクトルを生成するとともに、生成した腕ベクトルに基づいて経路探索を行う。また、本発明に係る枠線認識手法は、経路探索で腕ベクトルが用いられたか否かを示すフラグである通過済フラグがすべて通過済みとなったことを条件として経路探索を終了する。
【００３１】
具体的には、本発明に係る枠線認識手法では、まず、入力画像１から「交点情報」を検出する（図１の（Ａ）参照）。ここで、交点情報は、各交点が、左、右、上および下のうちどの向きの腕ベクトルを有するかを示す「交点種別」と、各腕ベクトルが経路探索で用いられたこと、すなわち、通過済みとなったことを示す「通過済フラグ」とを含んだ情報である。
【００３２】
なお、以下では、「交点種別」および「通過済フラグ」をそれぞれ４ビットで表現する場合について説明する。また、「交点種別」は、腕ベクトルが存在する場合には「１」、存在しない場合には「０」とし、「通過済フラグ」は、通過済みである場合には「１」、未通過の場合には「０」として説明するが、他の表現方式をとっても構わない。
【００３３】
また、図１に示す、「左」、「右」、「上」および「下」は、「左向きの腕ベクトル」、「右向きの腕ベクトル」、「上向きの腕ベクトル」および「下向きの腕ベクトル」にそれぞれ対応している。なお、各交点に示した「黒矢印」は、該当する腕ベクトルが未通過である旨を、「白抜き矢印」は、該当する腕ベクトルが通過済みである旨を、それぞれ示している。
【００３４】
図１の（Ａ）に示したように、交点ｇは、水平罫線と垂直罫線とが接する右上のコーナーであるので、「交点種別」における「左」および「下」が「１」、「右」および「下」が「０」となる。また、「通過済みフラグ」は、初期値としてすべて「０」が設定されている。
【００３５】
ここで、本発明に係る枠線認識手法は、交点の腕ベクトルをすべて通過したことを、上記した「通過済フラグ」を介して検出した場合に、経路探索を終了する点に特徴がある。このため、本発明に係る枠線認識手法では、交点の集合によって構成される閉領域の外周を探索する「外周経路探索」と、内周を探索する「内周経路探索」との周回方向を逆方向としている。
【００３６】
たとえば、図１の（Ｂ）に示したように、外周経路探索を「時計回り」に行った場合には、図１の（Ｃ）に示したように、内周経路探索を「反時計回り」に行う。
【００３７】
そして、図１の（Ｂ）に示したように、交点ａ、ｄ、ｅ、ｇ、ｈ、ｃ、ｂおよびａという閉じた外周経路が検出された場合には、通過した腕ベクトルに対応する通過済みフラグが「１」へ更新される。たとえば、交点ｇの通過済みフラグの「下」は、「０」から「１」へ更新される。
【００３８】
また、図１の（Ｃ）に示したように、交点ａ、ｂ、ｆ、ｅ、ｄおよびａという閉じた内周経路、交点ｇ、ｅ、ｆ、ｂ、ｃ、ｈおよびｇという閉じた内周経路がそれぞれ検出されると、通過した腕ベクトルに対応する通過済みフラグが「１」へ更新される。たとえば、交点ｇの通過済みフラグの「左」は、「０」から「１」へ更新される。この段階で、交点ｇの交点種別「１００１」と、通過済みフラグ「１００１」とが一致した状態となる。
【００３９】
そして、図１の（Ｄ）に示したように、他のすべての交点についても同様に、交点種別と通過済みフラグとが一致した状態となった場合に、本発明に係る枠線認識手法は、経路探索を終了し、検出した枠線で囲まれた枠線内領域を確定する。
【００４０】
このように、本発明に係る枠線認識手法では、交点の腕ベクトルに従って経路探索を行うとともに、各腕ベクトルに対応したフラグがすべて通過済みとなった場合に、経路探索を終了して枠線内領域を確定する。したがって、本発明に係る枠線認識手法によれば、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる。
【００４１】
以下では、図１を用いて説明した枠線認識手法を適用した枠線認識装置についての実施例を説明する。なお、以下では、画像読取装置（たとえば、スキャナ装置）から入力画像を取得する枠線認識装置について説明するが、スキャナ装置を含んだ枠線認識装置を構成することとしてもよい。また、枠線認識装置にいわゆるＯＣＲ（Optical Character Reader）機能を持たせ、認識した枠線内領域に対応する画像の文字認識を行わせることとしてもよい。
【実施例】
【００４２】
図２は、本実施例に係る枠線認識装置１０の構成を示すブロック図である。同図に示すように、枠線認識装置１０は、画像読取装置２０と接続されており、画像読取装置２０が読み取った画像（たとえば、帳票をスキャンした画像）を取得する。なお、画像読取装置２０としては、たとえば、いわゆるスキャナ装置を用いることができる。
【００４３】
枠線認識装置１０は、制御部１１と、記憶部１２とを備えており、制御部１１は、画像取得部１１ａと、罫線抽出部１１ｂと、交点抽出部１１ｃと、グループ化部１１ｄと、枠線抽出部１１ｅと、枠線内画像抽出部１１ｆと、破線検出部１１ｇと、交点補正部１１ｈとをさらに備えている。また、記憶部１２は、入力画像１２ａと、交点情報１２ｂと、枠線情報１２ｃと、枠線内画像１２ｄとを記憶する。
【００４４】
制御部１１は、枠線認識装置１０の全体制御および枠線抽出処理を行う制御部である。また、画像取得部１１ａは、画像読取装置２０から、手書き文字を含んだ帳票をスキャンした入力画像１（図１参照）を取得し、２値化処理を行ったうえで、記憶部１２へ入力画像１２ａとして記憶させる処理を行う処理部である。なお、入力画像１が２値化画像である場合には、２値化処理を行う必要はない。
【００４５】
罫線抽出部１１ｂは、記憶部１２の入力画像１２ａから罫線を抽出する処理を行うとともに、抽出した罫線に関する情報を交点抽出部１１ｃへ渡す処理を行う処理部である。ここで、罫線抽出部１１ｂによって行われる罫線抽出処理の内容について図３を用いて説明しておく。
【００４６】
図３は、罫線抽出処理の説明図である。まず、図３の（Ａ）に示したのは、入力画像１２ａ（原画像）を、１／１６最小値圧縮した圧縮画像３１である。ここで、「１／１６最小値圧縮」とは、隣接する４画素×４画素の画素グループを１つの代表画素へ置き換える際に、画素グループに属する画素の画素値の最小値を、代表画素の画素値とする処理を指す。つまり、１６画素中に１つでも画素値０（黒に対応）の画素があれば、代表画素は画素値０となる。そして、罫線抽出部１１ｂは、かかる圧縮画像３１を罫線の抽出対象として用いる。
【００４７】
つづいて、図３の（Ｂ）に示したように、罫線抽出部１１ｂは、図３の（Ａ）に示した圧縮画像３１から、水平罫線３２および垂直罫線３３をそれぞれ抽出する。ここで、水平罫線３２としては、所定方向にそれぞれ連続する黒画素群（以下、「ランレン」と記載する）のうち、水平方向のもの、かつ、所定長以上のものが抽出される。
【００４８】
また、垂直罫線３３としては、垂直方向のランレンのうち、所定長以上のものが抽出される。なお、図３の（Ｂ）に示した場合では、水平罫線３２が４つ、垂直罫線３３が３つ、それぞれ抽出されている。
【００４９】
ここで、所定長以上のランレンを水平罫線３２あるいは垂直罫線３３として検出する処理を行う場合、平行する２本の罫線が近接していると、１本の罫線として誤検出してしまうおそれがある。このため、罫線抽出部１１ｂは、図３の（Ｃ）に示した「罫線方向圧縮」を行うことで、近接した２本の罫線を１本の罫線として誤検出してしまう問題を回避する。
【００５０】
水平罫線３２の場合を例にあげて説明すると、図３の（Ｃ）に示したように、検出された罫線のラベリングを行ったうえで、得られたラベルの外接矩形内で入力画像１２ａ（原画像）を切り出す。そして、切出画像３４を、罫線方向（この場合、水平方向）にのみ１／４最小値圧縮する（図３の（Ｃ−１）参照）。なお、垂直罫線３３の場合には、垂直方向にのみ１／４最小値圧縮すればよい。ここで、１／４最小値圧縮とは、一方向へ隣接する４画素の画素グループを１つの代表画素へ置き換える際に、画素グループに属する画素の画素値の最小値を代表画素値とする処理を指す。
【００５１】
つづいて、罫線方向圧縮画像３５でランレンを取得し、所定値以下のランレンを削除する（図３の（Ｃ−２）参照）。このようにすることで、入力画像１２ａ（原画像）の対応部分における罫線方向以外のランレンを効率的に削除することができる。そして、残ったランレンをラベリングすることで（図３の（Ｃ−３）参照）、近接した２本の罫線を、ラベル３６およびラベル３７として、すなわち、２本の罫線として検出することができる。
【００５２】
ところで、図３の（Ｃ）に示した「罫線方向圧縮」を用いた場合には、入力画像１２ａ（原画像）に「かすれ」や「ひずみ」がある場合に、１本の罫線を複数本の罫線として検出してしまう副作用が発生する可能性がある。このため、罫線抽出部１１ｂは、複数のラベルの結合処理をあわせて行う。
【００５３】
具体的には、図３の（Ｄ）に示したように、２つのラベル３８およびラベル３９の重なり長（ｌａｐ）および間隔（ｄｉｓｔ）を、それぞれ取得する。そして、ｌａｐが所定の閾値以下であり、かつ、ｄｉｓｔが所定の閾値以下である場合に、２つのラベルを結合する。なお、ｌａｐに関する閾値と、ｄｉｓｔに関する閾値としては、画像の解像度であるｄｐｉ（dot per inch）などに基づいて予め定められた最適な値がそれぞれ用いられるものとする。
【００５４】
このように、罫線抽出部１１ｂは、図３の（Ｃ）に示した罫線の分離処理および図３の（Ｄ）に示した罫線の結合処理をそれぞれ行い、最終的に残った罫線に対して識別番号を付与する。なお、以下では、罫線に対して付与された識別番号を、「罫線ＩＤ」と記載することとする。
【００５５】
たとえば、図３の（Ｅ）に示した場合では、水平罫線３２については、ｙ座標（図３の（Ａ）参照）が小さい方から順に、罫線ＩＤとして「０」、「１」、「２」および「３」を付与している。また、垂直罫線３３については、ｘ座標（図３の（Ａ）参照）が小さい方から順に、罫線ＩＤとして「０」、「１」および「２」を付与している。
【００５６】
なお、図３の（Ｅ）では、水平罫線３２および垂直罫線３３が、図３の（Ｂ）のものと同一の場合を例示したが、図３の（Ｃ）あるいは（Ｄ）で、罫線の追加や削除が行われた場合には、最終的に残った罫線に対して罫線ＩＤが付与されることはいうまでもない。
【００５７】
また、ｘ座標が同じ罫線が複数存在する場合には、ｙ座標が小さい方から昇順の罫線ＩＤを付与し、ｙ座標が同じ罫線が複数存在する場合には、ｘ座標が小さい方から昇順の罫線ＩＤを付与するものとする。なお、罫線ＩＤの付与を降順に行っても構わない。
【００５８】
図２の説明に戻り、制御部１１の説明をつづける。交点抽出部１１ｃは、罫線抽出部１１ｂから受け取った罫線に関する情報に基づいて交点情報１２ｂを生成する処理を行う処理部である。また、この交点抽出部１１ｃは、生成した交点情報１２ｂを記憶部１２へ記憶させる処理をあわせて行う。
【００５９】
ここで、交点抽出部１１ｃによって行われる交点抽出処理の内容について図４を用いて説明しておく。図４は、交点抽出処理の説明図である。なお、図４の（Ａ）および（Ｂ）では、図３の（Ｅ）に示した０〜３の４本の水平罫線３２および０〜２の３本の垂直罫線３３の交点を求める場合について説明する。
【００６０】
図４の（Ａ）に示すように、交点抽出部１１ｃは、罫線抽出部１１ｂから受け取った罫線に関する情報に基づいて交点を抽出し、抽出した交点に対して座標を付与する。ここで、交点抽出部１１ｃは、水平罫線３２の罫線ＩＤ（ｖ座標に相当）と、垂直罫線３３の罫線ＩＤ（ｕ座標に相当）とで、罫線の交点に対して罫線ＩＤを用いた座標（ｕ，ｖ）を付与する。
【００６１】
たとえば、図４の（Ａ）に示した交点（１，２）は、ｕ＝０の垂直罫線３３と、ｖ＝２の水平罫線３２との交点である。また、交点（２，３）は、ｕ＝２の垂直罫線３３と、ｖ＝３の水平罫線３２との交点である。
【００６２】
また、交点抽出部１１ｃは、図４の（Ｂ）に示したように、座標を付与した各交点の交点種別を特定する。すなわち、交点抽出部１１ｃは、所定の交点と、ｕ座標またはｖ座標が同一な直近の交点を検出する処理を行い、直近の交点を検出した場合に、直近の交点へ向かう「腕ベクトル」があると判定する。
【００６３】
たとえば、図４の（Ｂ）に示したように、交点（０，０）とｕ座標が同一で直近の交点は、交点（０，２）であるので、交点（０，０）には下向きの腕ベクトルがあると判定される。なお、交点（０，０）の上側、すなわち、ｖ座標の負方向には交点がないので、交点（０，０）には上向きの腕ベクトルはないと判定される。
【００６４】
また、図４の（Ｂ）に示したように、交点（０，０）とｖ座標が同一で直近の交点は、交点（１，０）であるので、交点（０，０）には右向きの腕ベクトルがあると判定される。なお、交点（０，０）の左側、すなわち、ｕ座標の負方向には交点がないので、交点（０，０）には左向きの腕ベクトルはないと判定される。
【００６５】
このように、交点抽出部１１ｃは、座標が付与されたすべての交点の交点種別、すなわち、４方向の腕ベクトルがそれぞれあるか否かの種別を特定する（図４の（Ｂ）で円に囲まれた領域を参照）。ここで、交点種別のパターンは、図４の（Ｃ）に示したように、パターンＡからパターンＩまでの９種類が存在する。
【００６６】
たとえば、図４の（Ｂ）に示した交点（０，０）の交点種別４１ａは、図４の（Ｃ）に示したパターンＡである。また、図４の（Ｂ）に示した交点（２，３）の交点種別４１ｂは、図４の（Ｃ）に示したパターンＩである。なお、本実施例では、各交点からそれぞれ遠ざかる向きの腕ベクトルを用いる場合について説明するが、各交点へそれぞれ近づく向きの腕ベクトルを用いることとしてもよい。
【００６７】
ここで、各交点種別は、左向きの腕ベクトル（左腕）、右向きの腕ベクトル（右腕）、上向きの腕ベクトル（上腕）および下向きの腕ベクトル（下腕）の各腕ベクトルがあるか否かを示す情報である。したがって、図４の（Ｄ）に示したように、各１ビットのフラグ×４方向の計４ビットの情報として表現することができる。
【００６８】
図４の（Ｄ）に示したように、パターンＥでは、４方向の腕ベクトルをすべて有しているので、４つのフラグをすべて立てた「１１１１」と表現することができる。また、パターンＩでは、左腕および上腕のみを有しているので、「１０１０」と表現することができる。
【００６９】
なお、交点抽出部１１ｃは、上記した「交点種別」と、交点種別に含まれる腕ベクトルが後述する経路探索で用いられたか否かを示す「通過済フラグ」とを含んだ交点情報１２ｂを生成するが、この交点情報１２ｂの詳細な内容については、図９を用いて後述する。
【００７０】
ところで、図４では、交点抽出部１１ｃによって行われる交点抽出処理のうち、最も基本的な処理、すなわち、水平罫線３２と垂直罫線３３との交点を、単に交点として抽出する処理について説明した。
【００７１】
しかしながら、角が丸い枠が存在する場合や、枠がかすれている場合、枠に文字が接していたりノイズの影響があったりする場合などには、検出すべき交点を検出できなかったり、本来は交点ではないのに交点として検出してしまったりといった交点の誤検出が発生する。
【００７２】
そこで、交点抽出部１１ｃは、交点の削除や追加といった交点の補正処理をあわせて行う。このため、以下では、交点抽出部１１ｃによって行われる交点補正処理について、図５〜図７を用いて説明する。なお、交点補正処理は、図４の（Ａ）に示した座標付与処理と、図４の（Ｂ）に示した交点種別特定処理との間に挿入される形で行われる。
【００７３】
図５は、交点補正処理その１の説明図である。なお、交点補正処理その１は、角が丸い枠を矩形枠と仮定した場合の仮交点を検出し、検出した仮交点をあらたな交点として追加する処理である。なお、交点は「●」で、交点ではない先端は「◇」で、それぞれ示している。
【００７４】
図５の（Ａ）に示したのは角が丸い枠をもつ入力画像１２ａの一例である。なお、図５の（Ａ）に示した場合では、右下の角のみが角が丸い状態、すなわち、Ｌ字部分のみが丸い状態である。
【００７５】
この場合、図３を用いて説明した罫線抽出処理で水平罫線３２および垂直罫線３３を抽出し、図４を用いて説明した交点抽出処理で交点を抽出すると、図５の（Ａ−１）に示したように、３つの交点（交点５１ａ、交点５１ｂおよび交点５１ｃ）のみが検出される。
【００７６】
ここで、図５の（Ａ−１）に示した矩形の上辺および左辺は、それぞれ２つの交点で挟まれた罫線であるが、同じく下辺および右辺は、１つの交点のみしか有しない罫線である。
【００７７】
そこで、交点抽出部１１ｃは、１つの交点のみしか有しない罫線の先端（すなわち、交点ではない先端）を延伸し、他の罫線もしくは他の罫線の先端を延伸した線との交点を求める処理を行う。
【００７８】
具体的には、図５の（Ａ−１）に示した場合、交点抽出部１１ｃは、１つの交点のみしか有しない罫線の先端５２ａおよび先端５２ｂをそれぞれ延伸し、先端５２ａおよび先端５２ｂを対角線とする矩形領域である検証領域５３を生成する。なお、有効な検証領域５３のサイズはあらかじめ定められているものとし、所定のサイズよりも大きい検証領域しか得られなかった場合には、図５の（Ａ−２）以降の処理は行われない。
【００７９】
つづいて、交点抽出部１１ｃは、図５の（Ａ−２）に示したように、検証領域５３において、先端５２ａと先端５２ｂとをつなぐ黒画素が、図５の（Ａ）に示した入力画像１２ａにあるか否かを検査する。
【００８０】
そして、図５の（Ａ−２）に示した場合には、先端５２ａと先端５２ｂとをつなぐ黒画素（連結線５２ｃ）が検出されたので、図５の（Ａ−３）に示したように、延伸した線同士が交わる点を交点５４とし、あらたな交点（交点種別：図４の（Ｃ）のパターンＩ）として追加する。
【００８１】
次に、枠線のＴ字部分が丸い場合について、図５の（Ｂ）および（Ｂ−１）〜（Ｂ−３）を用いて説明する。図５の（Ｂ）に示したのは角が丸い枠をもつ入力画像１２ａのその他の例である。なお、図５の（Ｂ）に示した場合では、逆Ｔ字部分が丸い状態である。
【００８２】
この場合、図３を用いて説明した罫線抽出処理で水平罫線３２および垂直罫線３３を抽出し、図４を用いて説明した交点抽出処理で交点を抽出すると、図５の（Ｂ−１）に示したように、５つの交点（交点５６ａ、交点５６ｂ、交点５６ｃ、交点５６ｄおよび交点５６ｅ）が検出される。
【００８３】
ここで、図５の（Ｂ−１）に示した垂直罫線３３の５５ａ、水平罫線３２の５５ｂおよび５５ｃは、１つの交点のみしか有しない罫線である。そこで、交点抽出部１１ｃは、１つの交点のみしか有しない罫線の先端（先端５７ａ、先端５７ｂおよび先端５７ｃ）を延伸し、他の罫線もしくは他の罫線の先端を延伸した線との交点を求める処理、すなわち、図５の（Ａ）と同様の処理を行う。このような処理を行うと、図５の（Ｂ−２）に示した連結線５７ｄおよび連結線５７ｅが検出され、図５の（Ｂ−３）に示したように、交点５９ａ（交点種別：図４の（Ｃ）のパターンＩ）と、交点５９ｂ（交点種別：図４の（Ｃ）のパターンＧ）とがあらたな交点候補として見つけられる。
【００８４】
ここで、あらたな交点候補が見つけられた罫線（５５ａ、５５ｂおよび５５ｃ）において、総当たりの各ペアで罫線幅方向に重なりがあるか否かが検証され、重なりがある場合には、該当するペア（図５の（Ｂ−３）では、罫線５５ｂおよび罫線５５ｃ）同士を結合する。
【００８５】
そして、図５の（Ｂ−４）に示したように、結合した罫線上の交点５９ａおよび交点５９ｂ（同図の（Ｂ−３）参照）を合成し、あらたな交点５９ｃ（交点種別：図４の（Ｃ）のパターンＨ）として確定し、追加する。この場合、あらたな交点５９ｃのｖ座標は、罫線５５ｂまたは罫線５５ｃのいずれかの罫線ＩＤを用いる。また、罫線５５ｂ上の交点および罫線５５ｃ上の交点についても、交点５９ｃのｖ座標に用いた罫線ＩＤへ共通化する。
【００８６】
つづいて、交点補正処理その２について説明する。図６は、交点補正処理その２の説明図である。なお、交点補正処理その２は、「かすれ」によって分断された罫線を結合し、先端に交点をもたない罫線に対してあらたな交点を追加する処理である。
【００８７】
なお、図６の（Ａ）には、最終的に結合する線分のペアと、結合しない線分とを模式的に示している。また、図５の場合と同様に、交点は「●」で、交点ではない先端は「◇」で、それぞれ示している。図６の（Ａ）に示したように、交点抽出部１１ｃは、交点ではない先端を有する線分（線分６１ａ〜線分６１ｅ）をそれぞれ抽出する。ここで、線分とは、罫線上において交点と交点とで挟まれた部分の直線、または、罫線の先端と先端から最も近い交点とで挟まれた部分の直線のことを指す。
【００８８】
つづいて、交点抽出部１１ｃは、図６の（Ｂ）に示したように、先端から所定距離以内に交点がない線分を抽出する（図６の（Ｂ−１）参照）。ここでは、線分６１ａ〜線分６１ｄが抽出されている。なお、線分６１ｅは、先端から所定距離以内に交点をもっているので候補から除外される。ここで、所定距離としては、あらかじめ定められた画素数や長さ（たとえば、ｍｍ）が用いられる。
【００８９】
また、図６の（Ｂ）に示したように、交点抽出部１１ｃは、先端から所定距離以内に交点がない線分（線分６１ａ〜線分６１ｄ）の先端を延伸し、延伸した線分の幅方向に重なる最も近い線分を抽出する（図６の（Ｂ−２）参照）。
【００９０】
なお、図６の（Ｂ）では、線分６１ａのペアとして線分６２ａが、線分６１ｂのペアとして線分６２ｂが、線分６１ｃのペアとして線分６２ｃが、それぞれ抽出されている。これに対し、線分６１ｄについては該当する線分がないため、候補から除外される。
【００９１】
つづいて、交点抽出部１１ｃは、図６の（Ｂ）で候補として残った線分について、図６（Ｃ）に示した結合条件（Ｃ−１）〜（Ｃ−３）を適用し、すべての結合条件を満たした線分を図６の（Ｂ）で抽出したペア線分と結合する。
【００９２】
ここで、結合条件（Ｃ−１）は、ペアとなる線分間の距離を結合後の線分長で除した値がα％よりも小さいという条件である。また、結合条件（Ｃ−２）は、ペアとなる線分間の距離がβよりも小さいという条件である。さらに、結合条件（Ｃ−３）は、結合後の線分から垂直方向に出っ張る黒画素長がγよりも小さいという条件である。
【００９３】
なお、α％は、たとえば、５％であり、βあるいはγについては、あらかじめ定められた画素数や長さ（たとえば、ｍｍ）が用いられる。
【００９４】
また、図６の（Ｂ）で候補として残った線分６１ａ、線分６１ｂおよび線分６１ｃのうち、線分６１ｃは、結合条件（Ｃ−１）あるいは結合条件（Ｃ−２）を満たさない例である。また、線分６１ｂは、結合条件（Ｃ−３）を満たさない例である。
【００９５】
このようにして、図６に例示した場合では、最終的には、線分６１ａが、線分６２ａと結合される。ここで、線分６１ａを有する罫線上の交点と、線分６２ａを有する罫線上の交点のｕ座標を、２つの罫線のうちいずれかの罫線の罫線ＩＤへ共通化する。なお、ここでは、垂直罫線を結合する場合について説明したが、水平罫線を結合する場合にはｖ座標を共通化することとすればよい。そして、図６に示した線分の結合処理の後、交点補正処理その３、すなわち、１つの交点のみしか有しない線分の削除処理が行われる。
【００９６】
つづいて、交点補正処理その３について説明する。図７は、交点補正処理その３の説明図である。なお、交点補正処理その３は、枠に文字が接した影響や、ノイズの影響で誤検出された交点を削除する処理である。
【００９７】
図７の（Ａ）に示したのは、文字が枠に接した入力画像１２ａの一例である。図７の（Ａ）に示した場合では、領域７１ａで、「市」という手書き文字が線分７１に接している。また、領域７１ｂで、「１」という手書き文字が線分７１に接している。
【００９８】
この場合、図３を用いて説明した罫線抽出処理で水平罫線３２および垂直罫線３３を抽出し、図４を用いて説明した交点抽出処理で交点を抽出すると、図７の（Ｂ）に示したように、線分７１と交点をもつ線分として線分７２ｂおよび線分７２ｃが、線分７２ｃと交点をもつ線分として線分７２ａが、それぞれ抽出される。なお、抽出された交点は、それぞれ「●」で示している。
【００９９】
ここで、交点抽出部１１ｃは、図７の（Ｃ）に示したように、交点を１つしか有しない線分である線分７２ａおよび線分７２ｂを削除する。そして、線分７２ａを削除した結果、１つの交点のみしか有しない線分となった線分７２ｃを、図７の（Ｄ）に示したように、削除する。このように、交点抽出部１１ｃは、１つの交点のみしか有しない線分の削除を、再帰的に行う。これにより、削除された線分が有していた交点は順次、削除されていくことになる。
【０１００】
なお、図７には、枠に文字が接した影響によって誤検出された交点を削除する場合について例示したが、ノイズの影響で誤検出された交点についても同様の手法で削除することができる。
【０１０１】
このように、交点抽出部１１ｃは、水平罫線３２と垂直罫線３３との交点を抽出した後、図５〜図７に示した交点の削除や追加といった交点補正処理を行う。そして、交点抽出部１１ｃは、交点補正処理後の交点について交点情報１２ｂを生成する。
【０１０２】
図２の説明に戻り、制御部１１の説明をつづける。グループ化部１１ｄは、交点抽出部１１ｃによって記憶部１２へ格納された交点情報１２ｂに基づき、交点のグループ分けを行う処理部である。
【０１０３】
ここで、グループ化部１１ｄによって行われる交点グループ化処理について図８を用いて説明しておく。図８は、交点グループ化処理の説明図である。なお、図８の（Ａ）には、グループ分けの対象となる交点の例を、図８の（Ｂ）には、グループ分けの結果を、それぞれ示している。
【０１０４】
グループ化部１１ｄは、座標が付与された交点について、罫線によってつながっているグループを検索する。たとえば、図８の（Ａ）に示した場合では、交点（０，０）、交点（０，４）、交点（３，４）および交点（３，０）が罫線によってつながれているので、これらの交点をグループＡとする。
【０１０５】
また、図８の（Ａ）に示した場合では、交点（１，１）、交点（１，２）、交点（１，３）、交点（２，３）、交点（２，２）および交点（２，１）が罫線によってつながれているので、これらの交点を１つのグループＢとする。
【０１０６】
このようにして、グループ化部１１ｄは、交点のグループ分けを行い、図８の（Ｂ）に示した結果を得る。なお、図８では、２つのグループを示したが、３つ以上のグループについても同様の手順でグループ分けを行うことができる。
【０１０７】
図２の説明に戻り、制御部１１の説明をつづける。枠線抽出部１１ｅは、グループ分け済みの交点情報１２ｂに基づき、経路探索を行うことで、閉じた経路である枠線を抽出する処理を行う処理部である。
【０１０８】
また、枠線抽出部１１ｅは、抽出した枠線に関する情報である枠線情報１２ｃを、記憶部１２へ記憶させる処理をあわせて行う。なお、枠線抽出部１１ｅによって行われる枠線抽出処理の詳細な内容については、図１０〜図１２を用いて後述する。また、枠線抽出処理につづいて行われる枠線補正処理の詳細な内容については、図１４を用いて後述する。
【０１０９】
枠線内画像抽出部１１ｆは、枠線抽出部１１ｅによって記憶部１２へ記憶させられた枠線情報１２ｃと、入力画像１２ａとに基づき、枠線によって囲まれた領域である枠線内画像１２ｄを抽出する処理を行う処理部である。また、この枠線内画像抽出部１１ｆは、抽出した枠線内画像１２ｄを記憶部１２へ記憶させる処理をあわせて行う。
【０１１０】
破線検出部１１ｇは、記憶部１２から読み出した枠線内画像１２ｄから、破線を検出する処理を行う処理部である。また、この破線検出部１１ｇは、検出した破線に関する情報を、交点補正部１１ｈへ渡す処理をあわせて行う。
【０１１１】
交点補正部１１ｈは、破線検出部１１ｇから受け取った破線に関する情報に基づき、交点情報１２ｂを更新する処理を行うとともに、更新後の交点情報１２ｂに基づいた交点の再グループ分けをグループ化部１１ｄに対して指示する処理を行う処理部である。
【０１１２】
すなわち、交点補正部１１ｈは、破線検出部１１ｇによって破線が検出され、検出された破線に基づく交点があらたに検出された場合に、あらたに検出された交点に関する情報で交点情報１２ｂを更新する。
【０１１３】
そして、グループ化部１１ｄは、更新後の交点情報１２ｂに含まれる交点を用いてグループ化処理を再度実行する。なお、破線検出部１１ｇによってあらたな破線が検出されなかった段階で、枠線情報１２ｃは確定されることになる。
【０１１４】
なお、枠線内画像抽出部１１ｆによる枠線内画像抽出処理の具体的な内容については図１５を用いて、破線検出部１１ｇによる破線検出処理および交点補正部１１ｈによる交点補正処理の具体的な内容については図１６を用いて、それぞれ後述することとする。
【０１１５】
記憶部１２は、不揮発性メモリやハードディスクドライブといった記憶デバイスで構成される記憶部であり、入力画像１２ａと、交点情報１２ｂと、枠線情報１２ｃとを記憶する。入力画像１２ａは、画像読取装置２０から画像取得部１１ａ経由で受け取った画像であり、たとえば、手書き文字を含んだ帳票をスキャンし、２値化した原画像である。
【０１１６】
また、交点情報１２ｂは、交点抽出部１１ｃによって生成された情報であり、交点ごとの腕ベクトルの有無を示す交点種別と、各腕ベクトルが枠線抽出部１１ｅによる経路探索で用いられたか否かを示す通過済フラグと、ピクセル座標（たとえば、入力画像の左上を原点とした座標系）を含んだ情報である。なお、交点種別、通過済みフラグおよびピクセル座標を別々の情報として記憶部１２へ記憶させることとしてもよい。
【０１１７】
ここで、この交点情報１２ｂの一例について図９を用いて説明する。図９は、交点情報１２ｂの一例を示す図である。ここで、図９の（Ａ）には、交点抽出部１１ｃによって生成された直後、すなわち、枠線抽出部１１ｅによる経路探索が行われる以前の交点情報１２ｂの例を示している。また、図９の（Ｂ）には、枠線抽出部１１ｅによる経路探索が完了した時点の交点情報１２ｂの例を示している。
【０１１８】
なお、図９に示した各交点は、図４の（Ａ）や（Ｂ）に示した８個の交点にそれぞれ対応している。なお、以降の説明では、図９に示したように、罫線ＩＤ座標（ｕ，ｖ）で特定された交点を、交点ａ（０，０）、あるいは、単に、交点ａのように記載することとする。
【０１１９】
図９の（Ａ）に示すように、交点情報１２ｂは、交点の罫線ＩＤ座標ごとに、「交点種別」項目、「通過済フラグ」項目およびピクセル座標を有する情報である。たとえば、交点ａ（０，０）は、左腕、右腕、上腕および下腕の各腕ベクトルのうち、右腕および下腕の腕ベクトルを有するので、有する腕ベクトルに対応するビットが「１」となり、交点種別は「０１０１」とあらわされる。なお、通過済フラグは「００００」であり、ピクセル座標は（ｘ１、ｙ１）である。
【０１２０】
また、交点ｅ（１，１）は、左腕、右腕、上腕および下腕のうち、右腕、上腕および下腕の腕ベクトルを有するので、交点種別は「０１１１」とあらわされる。なお、通過済フラグは「００００」であり、ピクセル座標は（ｘ５、ｙ５）である。また、その他の交点についても、図９の（Ａ）に示した状態では、通過済フラグはすべて「００００」である。
【０１２１】
ところで、枠線抽出部１１ｅによる経路探索が完了した状態では、すべての腕ベクトルがすべて通過済みとなる。したがって、図９の（Ｂ）に示した状態では、すべての交点について、交点種別のビット状態と、通過済フラグのビット状態とが一致する。すなわち、枠線抽出部１１ｅは、交点種別および通過済フラグが図９の（Ｂ）のように完全一致するまで、経路探索処理を継続する。
【０１２２】
このように、交点情報１２ｂは、交点の罫線ＩＤ座標ごとに、交点の腕ベクトルの有無を含んだ情報である。なお、交点情報１２ｂを様々な用途に用いることができる。たとえば、見かけ上は異なるフォーマット（たとえば、文字が入りきれずに枠を拡張した場合など）であっても、交点の個数と、交点の交点種別とが同一であることをもって同一のフォーマットとみなすことができる。また、枠内に空白が多い場合には、文字の読み取り後に、該当する枠を交点種別の関係を崩さない程度に縮小して保存することも可能となる。
【０１２３】
次に、枠線抽出部１１ｅによって行われる枠線抽出処理の詳細な内容について、図１０〜図１２を用いて説明する。図１０は、経路探索の優先順位を示す図である。なお、同図の（Ａ）には、外周の探索を時計回りで行う場合の優先順位を、同図の（Ｂ）には、外周の探索を反時計回りで行う場合の優先順位を、それぞれ示している。
【０１２４】
図１０の（Ａ）および（Ｂ）に示したように、枠線抽出部１１ｅは、外周探索の周回方向と、内周探索の周回方向とを逆方向に行う点に特徴がある。このように、外周探索の周回方向と、内周探索の周回方向とを逆にすることで、すべての腕ベクトルを１回ずつ通過したことをもって、経路探索が完了したことを検出することができる。なお、この点の詳細については、図１１および図１２を用いて後述する。
【０１２５】
図１０の（Ａ）に示したように、枠線抽出部１１ｅは、外周の探索を時計回りで行う場合には、内周の探索を反時計回りで行う。また、枠線抽出部１１ｅは、経路探索で通過しようとする交点に未通過の腕ベクトルが複数ある場合には、左折を最も優先し、直進を次に優先し、右折を最も優先しない。
【０１２６】
たとえば、通過しようとする交点における未通過の腕ベクトルが進路を左折する向きと、進路を直進する向きと、進路を右折する向きとの３つがある場合には、枠線抽出部１１ｅは、通過しようとする交点で左折する向きの腕ベクトルを選択する。
【０１２７】
また、通過しようとする交点における未通過の腕ベクトルが進路を左折する向きと、進路を右折する向きとの２つがある場合には、枠線抽出部１１ｅは、通過しようとする交点で左折する向きの腕ベクトルを選択する。なお、未通過の腕ベクトルが進路を直進する向きと、進路を右折する向きとの２つがある場合には、枠線抽出部１１ｅは、通過しようとする交点を直進する向きの腕ベクトルを選択する。
【０１２８】
これに対し、図１０の（Ｂ）に示したように、枠線抽出部１１ｅは、外周の探索を反時計回りで行う場合には、内周の探索を時計回りで行う。また、枠線抽出部１１ｅは、経路探索で通過しようとする交点に未通過の腕ベクトルが複数ある場合には、右折を最も優先し、直進を次に優先し、左折を最も優先しない。
【０１２９】
このように、枠線抽出部１１ｅは、外周を時計回りで探索する場合（図１０の（Ａ）の場合）であっても、外周を反時計回りで探索する場合（図１０の（Ｂ）の場合）であっても、外周探索の場合には、探索経路で囲まれる閉領域の面積がなるべく大きくなるように未通過の腕ベクトルを選択していく。逆に、内周探索の場合には、探索経路で囲まれる閉領域の面積がなるべく小さくなるように未通過の腕ベクトルを選択していく。
【０１３０】
次に、枠線抽出部１１ｅによる外周経路探索および内周経路探索の例について図１１および図１２を用いて説明する。図１１は、外周経路探索の一例であり、図１２は、内周経路探索の一例である。
【０１３１】
なお、図１１および図１２には、外周経路探索を時計回りで行った場合（図１１の矢印１１１参照）、すなわち、内周経路探索を反時計回りで行った場合（図１２の矢印１２１および矢印１２３参照）の例を示している。また、図１１および図１２では、未通過の腕ベクトルを「黒矢印」で、通過済みの腕ベクトルを「白抜き矢印」で、それぞれ示している。
【０１３２】
図１１の（Ａ）に示したように、外周経路の探索前には、交点ａ〜交点ｈの腕ベクトルはすべて「黒矢印」である。まず、枠線抽出部１１ｅは、交点ａ〜交点ｈの中から、経路探索の始点となる交点を選択する。たとえば、枠線抽出部１１ｅは、ｕ座標またはｖ座標が最も大きい交点あるいは最も小さい交点を選択する。
【０１３３】
図１１の（Ｂ−１）に示したのは、外周経路探索の始点として、ｕ座標およびｖ座標が最も小さい交点である交点ａを選択した場合である。この場合、外周経路探索は時計回りであるので、枠線抽出部１１ｅは、交点ａの腕ベクトルのうち右向きの腕ベクトルを選択する。ここで、ｕ座標またはｖ座標が最も大きい交点または小さい交点を選択した場合の外周探索の始点となりうる交点パターン（図４の（Ｃ）に対応）と、探索開始時に選択する腕ベクトルの向きとを図１１の（Ｃ）に示している。図１１の（Ｂ−１）に示した場合では、周回方向が時計回りであるので、交点パターンがパターンＡである交点ａから探索を開始する際に選択される腕ベクトルは右向きである。
【０１３４】
そして、交点ｄを通過する場合には、左折および直進ができないので、右折することになり、枠線抽出部１１ｅは、下向きの腕ベクトルを選択する。つづいて、交点ｅを通過する場合には、進行方向について、左折または直進の選択肢があるが、左折を優先するので、右向きの腕ベクトルを選択する。また、交点ｇを通過する場合には、選択肢が右折しかないので、下向きの腕ベクトルを選択する。以下、同様に、交点ｈでは左向きの腕ベクトルを選択し、交点ｃでは上向きの腕ベクトルを選択する。
【０１３５】
また、交点ｂでは、直進または右折の選択肢があるが、直進を優先するので、上向きの腕ベクトルを選択する。そして、外周経路探索の始点である交点ａに戻ったならば、枠線抽出部１１ｅは、交点ａを始点とし、交点ｄ、交点ｅ、交点ｇ、交点ｈ、交点ｃおよび交点ｂを通過して交点ａに戻る経路１１２を、確定した外周経路として枠線情報１２ｃへ記録する。
【０１３６】
なお、上記した外周経路探索で通過した交点については、図１１の（Ｂ−２）に示したように、選択した腕ベクトルに対応する通過済フラグを更新する。なお、仮に、始点に戻らなかった場合には、異なる腕ベクトルから出発するか、異なる始点から出発すればよい。なお、ｕ座標またはｖ座標が最も大きい交点、ｕ座標またはｖ座標が最も小さい交点を始点として選択し、図１１の（Ｃ）に示した向きで出発すれば必ず始点に戻るが、始点または出発向きを任意に選択すると、始点に戻れない場合がある。ただし、すべての始点またはすべての出発向きで総当たりの探索を行えば、外周経路を必ず見つけることができる。
【０１３７】
次に、図１１に示した外周経路探索につづいて行われる内周経路探索について図１２を用いて説明する。なお、図１２に示した内周経路探索では、図１１における外周経路探索で通過済みとなった各腕ベクトル（白抜き矢印）を引き継ぐ。なお、探索すべき内周経路が２つあるため、１つめの内周経路探索を図１２の（Ａ−１）および（Ａ−２）に、２つめの内周経路探索を図１２の（Ｂ−１）および（Ｂ−２）に、それぞれ示している。
【０１３８】
図１２の（Ａ−１）に示したように、１つめの内周経路探索では、たとえば、交点ａを始点として、矢印１２１に示すように反時計回りで経路探索が行われる。ここで、内周経路探索の始点とする交点は、外周経路探索後に未通過の腕ベクトルをもつ交点であればいずれの交点でもよく、出発時の腕ベクトルも未通過であれば、いずれの腕ベクトルから出発してもよい。なお、内周経路探索を反時計回りに行う場合には、図１１に示した外周経路探索と同様に、左折を最も優先し、直進を次に優先し、右折を最も優先しない（図１０の（Ａ）参照）。
【０１３９】
まず、図１２の（Ａ−１）に示したように、枠線抽出部１１ｅは、交点ａの未通過の腕ベクトルである下向きの腕ベクトルを選択する。そして、交点ｂを通過する場合には、進行方向について左折または直進の選択肢があるが、左折を優先するので、右向きの腕ベクトルを選択する。
【０１４０】
また、交点ｆでは、選択肢が左折しかないので、上向きの腕ベクトルを選択する。そして、交点ｅでは、左折の選択肢はないが、直進の選択肢はあるので、上向きの腕ベクトルを選択し、交点ｄでは、選択肢が左折しかないので、左向きの腕ベクトルを選択する。
【０１４１】
このようにして、始点である交点ａに戻ったならば、枠線抽出部１１ｅは、交点ａを始点とし、交点ｂ、交点ｆ、交点ｅおよび交点ｄを通過して交点ａに戻る経路１２２を、確定した内周経路として枠線情報１２ｃへ記録する。なお、経路探索時に通過した交点については、図１２の（Ａ−２）示したように、選択した腕ベクトルに対応する通過済フラグを更新する。ここで、外周経路探索後の内周探索においては、優先順位に従って選択した未通過の腕ベクトルの向きに進めば必ず始点に戻る。
【０１４２】
また、図１２の（Ｂ−１）に示したように、２つめの内周経路探索では、たとえば、交点ｇを始点として、矢印１２３に示すように反時計回りで経路探索が行われる。なお、左折を最も優先し、直進を次に優先し、右折を最も優先しない（図１０の（Ａ）参照）点については図１２の（Ａ−１）と同様である。
【０１４３】
まず、図１２の（Ｂ−１）に示したように、枠線抽出部１１ｅは、交点ｇの未通過の腕ベクトルである左向きの腕ベクトルを選択する。そして、交点ｅを通過する場合には、進行方向について未通過の腕ベクトルの向きは左折しかないので、下向きの腕ベクトルを選択する。
【０１４４】
また、交点ｆでは、選択肢が右折しかないので、左向きの腕ベクトルを選択し、交点ｂでは、選択肢が左折しかないので、下向きの腕ベクトルを選択する。また、交点ｃでは、選択肢が左折しかないので、右向きの腕ベクトルを選択し、交点ｈでは、選択肢が左折しかないので、上向きの腕ベクトルを選択する。
【０１４５】
このようにして、始点である交点ｇに戻ったならば、枠線抽出部１１ｅは、交点ｇを始点とし、交点ｅ、交点ｆ、交点ｂ、交点ｃおよび交点ｈを通過して交点ｇに戻る経路１２４を、確定した内周経路として枠線情報１２ｃへ記録する。なお、経路探索時に通過した交点については、図１２の（Ｂ−２）に示したように、選択した腕ベクトルに対応する通過済フラグを更新する。
【０１４６】
次に、枠線抽出部１１ｅによって更新される枠線情報１２ｃの例について図１３を用いて説明する。図１３は、枠線情報１２ｃの一例を示す図である。
【０１４７】
図１３に示したように、枠線情報１２ｃは、図８を用いて説明したグループを示す「グループ」項目と、外周経路探索か内周経路探索かの区別を示す「周回種別」項目とを含んでいる。また、枠線情報１２ｃは、確定された枠線の識別子に相当する「枠線番号」項目と、確定した経路を構成する交点を示す「経路」項目とを含んでいる。
【０１４８】
なお、図１３に示した「枠線番号」項目が「１」の経路は、図１１の（Ｂ−２）で確定した外周経路に対応している。また、図１３に示した「枠線番号」項目が「２」の経路および「３」の経路は、それぞれ、図１２の（Ａ−２）および（Ｂ−２）で確定した内周経路に対応している。
【０１４９】
このため、「枠線番号」項目が「１」の「周回種別」項目は「外周」であり、「枠線番号」項目が「２」および「３」の「周回種別」項目は「内周」である。なお、図１３に示した場合では、「グループ」項目はすべて「Ａ」となっているが、図８に示した場合のように、複数のグループが検出された場合には、各グループに対応する識別子がそれぞれ格納されることになる。
【０１５０】
次に、枠線抽出部１１ｅによって行われる枠線補正処理の詳細な内容について図１４を用いて説明する。ここで、枠線補正処理とは、検出された枠線のうち、「１つの線分でつながる枠線」および「１つの交点でつながる枠線」を、複数の枠線へ分離する処理のことを指す。
【０１５１】
図１４は、枠線補正処理の説明図である。図１４の（Ａ）に示した４つのパターンは、分離すべき枠線の代表的なパターンである。なお、図１４の（Ａ）では、罫線のパターンに対してアルファベットなしの符号（たとえば、１４１）を、検出された枠線に対して「ａ」付きの符号（たとえば、１４１ａ）を付している。
【０１５２】
また、図１４の（Ａ）では、枠線を接続する部分に対して「ｂ」付きの符号（たとえば、１４１ｂ）を、分離された枠線に対して「ｃ」または「ｄ」付きの符号（たとえば、１４１ｃおよび１４１ｄ）を、付している。
【０１５３】
ここで、図１４の（Ａ）に示したように、４つのパターンのうち、左側の２つが、「１つの線分でつながる枠線」に対応するパターンであり、右側の２つが、「１つの交点でつながる枠線」に対応するパターンである。枠線抽出部１１ｅは、図１４の（Ａ）に示したパターンを検出した場合に、枠線を分離する処理を行う。
【０１５４】
具体的には、枠線抽出部１１ｅは、枠線の中継点となる交点の中に複数回通過している交点がある場合に、分離すべき枠線であると判定する。そして、枠線抽出部１１ｅは、複数回通過している交点に内接する点が一致するか否かに基づき、「１つの線分でつながる枠線」であるか、「１つの交点でつながる枠線」であるかを判定する。
【０１５５】
たとえば、図１４の（Ｂ）に示したように、枠線抽出部１１ｅは、枠線の中継点の中で複数回通過している交点（同図では「交点ｃ」）、すなわち、一致点を検出する（図１４の（Ｂ−１）参照）。
【０１５６】
つづいて、枠線抽出部１１ｅは、一致点にそれぞれ内接する２つの点が一致しているか否かを判定する。ここで、図１４の（Ｂ）に示した場合では、一致点にそれぞれ内接する２つの点（同図では「交点ｆ」）が一致しているので（図１４の（Ｂ−２）参照）、枠線抽出部１１ｅは、「１つの線分でつながる枠線」、すなわち、「線分結合」と判定する。
【０１５７】
そして、枠線抽出部１１ｅは、枠線を、２つの一致点（同図では「交点ｃ」）の内側と外側との２つの枠線へ分離する。なお、「線分結合」の場合、片方の一致点は削除する（図１４の（Ｂ−３）参照）。このようにして、枠線抽出部１１ｅは、１つの経路を、「ａ、ｂ、ｃ、ｄおよびａ」という経路と、「ｆ、ｇ、ｈ、ｅおよびｆ」という経路とに分離する。
【０１５８】
また、図１４の（Ｃ）に示したように、枠線抽出部１１ｅは、枠線の中継点の中で複数回通過している交点（同図では「交点ｃ」）、すなわち、一致点を検出する（図１４の（Ｃ−１）参照）。
【０１５９】
つづいて、枠線抽出部１１ｅは、一致点にそれぞれ内接する２つの点が一致しているか否かを判定する。ここで、図１４の（Ｃ）に示した場合では、一致点にそれぞれ内接する２つの点（同図では「交点ｅ」および「交点ｇ」）が相違しているので（図１４の（Ｃ−２）参照）、枠線抽出部１１ｅは、「１つの交点でつながる枠線」、すなわち、「点結合」と判定する。
【０１６０】
そして、枠線抽出部１１ｅは、枠線を、２つの一致点（同図では「交点ｃ」）の内側と外側との２つの枠線へ分離する（図１４の（Ｃ−３）参照）。なお、「点結合」の場合、片方の一致点を分離後の枠線でそれぞれ用いる。このようにして、１つの経路を、枠線抽出部１１ｅは、「ａ、ｂ、ｃ、ｄおよびａ」という経路と、「ｃ、ｅ、ｆ、ｇおよびｃ」という経路とに分離する。
【０１６１】
次に、枠線内画像抽出部１１ｆによる枠線内画像抽出処理の具体的な内容について図１５を用いて説明する。図１５は、枠線内画像抽出処理の説明図である。なお、ここでは、図１５の（Ａ）に示すように、枠線抽出部１１ｅによって凹型の枠線が抽出された場合について説明する。
【０１６２】
図１５の（Ａ）に示したように、枠線内画像抽出部１１ｆは、枠線１５１をすべて含み、かつ、枠線よりも若干大きい領域１５２を、入力画像１２ａから切り出す。ここで、枠線を構成する経路の各交点に対応してピクセル座標（たとえば、入力画像の左上を原点とした座標系）が保持されており、かかるピクセル座標を用いて上記した切り出し処理および以降の処理が行われる。なお、同図では、領域１５２が矩形である場合を示しているが、枠線１５１の形状に合わせる（たとえば、枠線１５１が凹型であれば凹型の形状など）こととしてもよい。
【０１６３】
つづいて、図１５の（Ｂ）に示したように、枠線内画像抽出部１１ｆは、所定の傾きを有する直線１５３を同図に示す矢印の方向へ平行移動させることで、経路を構成する線分との交点を検出する。なお、検出された交点は「●」で示している。
【０１６４】
そして、枠線内画像抽出部１１ｆは、直線１５３上の最初の交点までは「外」、次の交点までは「内」、さらに次の交点までは「外」という判定を交互に繰り返すことで、直線１５３上の各画素が枠線の「外」に対応するか、「内」に対応するかを決定する。
【０１６５】
ここで、入力画像１２ａから切り出した領域１５２の各画素は、「黒」か「白」の２値画像であるので、枠線内画像抽出部１１ｆは、「内」の画素についてはそのまま、「外」の画素については「灰色」のような他の画素値へ変更する。このようにして、枠線内画像抽出部１１ｆは、図１５の（Ｃ）に入力画像として示した画像データを得る。
【０１６６】
そして、枠線内画像抽出部１１ｆは、連続する「黒画素」をラベル化するいわゆるラベリング処理を行う（図１５の（Ｃ−１）参照）。なお、同図に示した場合では、ラベル１５２ａと、ラベル１５２ｂと、ラベル１５２ｃと、ラベル１５２ｄとが得られている。
【０１６７】
また、枠線内画像抽出部１１ｆは、図１５の（Ｃ）に示した入力画像における「灰色」の領域を「黒」、入力画像における「白」または「黒」の領域を「白」とした２値画像である有効領域画像１５４を得る。ここで、有効領域画像１５４の「白」画素は、「有効エリア」に対応し、「黒」画素は、「無効エリア」に対応している。
【０１６８】
つづいて、枠線内画像抽出部１１ｆは、有効領域画像１５４の有効エリアを所定回数（ｎ回）収縮させる処理を行う（図１５の（Ｃ−２）参照）。これにより、有効領域が「痩せた」有効領域画像１５４ａが得られる。なお、このように、有効エリアの収縮処理を行うのは、有効エリアに対応する経路内画像を文字認識対象領域として取り扱うと、枠線自体が含まれる場合があり、枠線を文字と誤認識してしまうおそれがあるためである。
【０１６９】
このように、ラベリングが完了した領域１５２と、有効エリアを収縮させた有効領域画像１５４ａとが得られると、枠線内画像抽出部１１ｆは、両画像を重ね合わせる（図１５の（Ｃ−３）参照）。そして、有効領域画像１５４ａの無効領域に部分的に含まれるラベルは残し（図１５の（Ｃ−４）参照）、完全に無効領域に含まれるラベルはノイズとみなして削除する。
【０１７０】
具体的には、図１５の（Ｃ）に示した場合では、無効領域に完全に含まれるラベル１５２ａは削除されるが、その一部が無効領域に含まれるラベル１５２ｂ、ラベル１５２ｃおよびラベル１５２ｄは残されている。
【０１７１】
このように、枠線内画像抽出部１１ｆは、残存するラベルからなる画像を枠線内画像１２ｄとして、記憶部１２へ記憶させる。そして、破線検出部１１ｇは、記憶部１２から読み出した枠線内画像１２ｄに含まれるラベルの位置関係などに基づいて破線を検出する処理を行うことになる。
【０１７２】
次に、破線検出部１１ｇによって行われる破線検出処理の具体的な内容について図１６を用いて説明する。図１６は、破線検出処理の説明図である。なお、図１６の（Ａ）に示した画像１６１は、枠線内画像抽出部１１ｆから渡された枠線内画像１２ｄの一例であり、同図において破線で囲まれた領域は、各ラベルを示している。
【０１７３】
ここで、図１６の（Ａ）に示したように、破線検出部１１ｇは、各ラベルの高さおよび幅を検出する。なお、同図では、ラベル１６１ｂの高さｈ１および幅ｗ１のみを例示しているが、すべてのラベルについて高さおよび幅が検出される。
【０１７４】
そして、破線検出部１１ｇは、高さまたは幅のうちいずれかが所定値α以上の場合、または、高さまたは幅のいずれかがαよりも小さい所定値β以上でラベル内の黒画素占有率が所定値以下（たとえば、５０％以下）の場合に、該当するラベルを破線候補から削除する。
【０１７５】
このようにして、図１６の（Ｂ）に示したように、ラベル１６１ｂ、ラベル１６１ｃおよび１６１ｄは破線候補から削除される。一方、矩形状の９つのラベル１６１ａ（図１６の（Ａ）参照）は、削除されない。つづいて、破線検出部１１ｇは、図１６の（Ａ）に示したｘ座標が重なり合うラベル同士をグループ化する。ただし、対象となるラベルが２個以下の場合にはグループ化しない。このようにして、グループ１６２ａと、グループ１６２ｂとが得られる。
【０１７６】
なお、図１６の（Ｂ）では、垂直方向の破線を検出する場合について示しているが、水平方向の破線を検出する場合には、ｙ座標が重なり合うラベル同士をグループ化することとすればよい。
【０１７７】
つづいて、破線検出部１１ｇは、図１６の（Ｃ）に示したように、グループに含まれる各ラベルの高さ（同図ではｈ２）、グループ内に含まれる各ラベルの中心ピッチ（同図ではｐ１、ｐ２およびｐ３）を、それぞれ検出する。なお、同図では、記載を省略しているが、ラベルの高さおよびピッチの検出は、グループに含まれるすべてのラベルについて行われる。
【０１７８】
そして、破線検出部１１ｇは、グループ内の各ラベルの高さ（ｈ２）の総和を枠線内画像１６１の高さ（ｈ３）で除した値が、所定値以上（たとえば、５０％以上）であるグループを破線候補として残し、その他のグループを削除する。また、破線検出部１１ｇは、グループ内のラベルにおける中心ピッチの標準偏差を算出し、算出した標準偏差が所定値以下であるグループを破線候補として残し、その他のグループを削除する。
【０１７９】
つづいて、図１６の（Ｄ）に示したように、破線検出部１１ｇは、枠線内画像１６１の右辺または左辺から残存しているグループのｘ座標までの距離（Ｗ２）が所定値以下の場合に、該当するグループを削除する。
【０１８０】
ここで、枠線内画像１６１の右辺または左辺に近いグループを削除するのは、文字を入力するための枠として、たとえば、記入可能な大きさの文字よりも狭い枠は不自然であるためである。なお、水平方向の破線を検出する場合には、枠線内画像１６１の上辺または下辺からの距離を用いて同様の処理を行えばよい。
【０１８１】
このようにして、最終的に、図１６の（Ｃ）に示したグループ１６２ｂが、破線として確定される。そして、破線検出部１１ｇは、確定した破線に関する情報を交点補正部１１ｈへ渡し、交点補正部１１ｈは、グループ１６２ｂに相当する線分１６３が、枠線内画像の上辺と交わる点をあらたな交点１６４とするとともに、下辺と交わる点をあらたな交点１６５とし、交点情報１２ｂを更新する。また、交点補正部１１ｈは、グループ化部１１ｄへ更新後の交点情報１２ｂに基づいて再度のグループ化処理を行うように指示する。
【０１８２】
次に、枠線認識装置１０が実行する処理手順について図１７〜図１９を用いて説明する。図１７は、枠線認識装置１０が実行する処理手順を示すフローチャートである。図１７に示すように、罫線抽出部１１ｂが罫線抽出処理を行うと（ステップＳ１０１）、交点抽出部１１ｃは、交点抽出処理を行う（ステップＳ１０２）。
【０１８３】
なお、ステップＳ１０１の罫線抽出処理の詳細な処理手順については図１８を用いて、ステップＳ１０２の交点抽出処理の詳細な処理手順については図１９を用いて、それぞれ後述する。
【０１８４】
つづいて、グループ化部１１ｄが、交点のグルーピング（グループ分け）を行うと（ステップＳ１０３）、枠線抽出部１１ｅは、１つのグループを選択し（ステップＳ１０４）、外周経路探索を行うとともに（ステップＳ１０５）、内周経路探索を行う（ステップＳ１０６）。
【０１８５】
さらに、枠線抽出部１１ｅは、探索経路の分離を行い、分離後の経路を枠線情報１２ｃとして記憶部１２へ記憶させる（ステップＳ１０７）。そして、枠線抽出部１１ｅは、経路が分離されたか否かを判定し（ステップＳ１０８）、経路が分離されなかった場合には（ステップＳ１０８，Ｎｏ）、入力画像１２ａから枠線内画像１２ｄの抽出を行い（ステップＳ１０９）、破線検出部１１ｇは、破線の検出処理を行う（ステップＳ１１０）。なお、ステップＳ１０８にて、経路が分離されたと判定された場合には（ステップＳ１０８，Ｙｅｓ）、グループが変更されるため、ステップＳ１０３以降の処理を繰り返す。
【０１８６】
そして、全グループについての処理が完了したか否かを判定し（ステップＳ１１１）、全グループについての処理が終了した場合には（ステップＳ１１１，Ｙｅｓ）、ステップＳ１０９にて破線が検出されたグループがあるか否かを判定する（ステップＳ１１２）。なお、ステップＳ１１１の判定条件を満たさなかった場合には（ステップＳ１１１，Ｎｏ）、ステップＳ１０４以降の処理を繰り返す。
【０１８７】
そして、ステップＳ１１２にて、破線が検出されたと判定された場合には（ステップＳ１１２，Ｙｅｓ）、ステップＳ１０３以降の処理を繰り返し、破線の検出がないと判定された場合には（ステップＳ１１２，Ｎｏ）、処理を終了する。
【０１８８】
次に、図１７のステップＳ１０１に示した罫線抽出処理の詳細な処理手順について図１８を用いて説明する。図１８は、罫線抽出処理の処理手順を示すフローチャートである。図１８に示すように、罫線抽出部１１ｂは、入力画像１２ａに対して１／１６最小値圧縮を行い（ステップＳ２０１）、圧縮後の入力画像１２ａについて、水平方向および垂直方向のランレンを算出する（ステップＳ２０２）。
【０１８９】
つづいて、罫線抽出部１１ｂは、所定値以下のランレンを削除するとともに（ステップＳ２０３）、残ったランレンに対して罫線方向圧縮を行う（ステップＳ２０４）。そして、罫線方向圧縮によってあらたに検出された罫線を含んだすべての罫線を対象としたうえで、水平罫線および垂直罫線それぞれに罫線ＩＤを付与し（ステップＳ２０５）、処理を終了する。
【０１９０】
次に、図１７のステップＳ１０２に示した交点抽出処理の詳細な処理手順について図１９を用いて説明する。図１９は、交点抽出処理の処理手順を示すフローチャートである。図１９に示すように、交点抽出部１１ｃは、水平罫線と垂直罫線とが交わる部分を抽出する（ステップＳ３０１）。
【０１９１】
つづいて、交点抽出部１１ｃは、各交点について交点種別および罫線ＩＤ座標を付与し（ステップＳ３０２）、交点が１つの線分の結合および削除を行う（ステップＳ３０３）。そして、ステップＳ３０３の処理で結合および削除後の交点情報１２ｂを生成し（ステップＳ３０４）、記憶部１２へ記憶させたうえで、処理を終了する。
【０１９２】
上述してきたように、本実施例では、交点抽出部が、入力画像から抽出した罫線同士の交点を抽出し、記憶部が、交点に属する各罫線に沿ってこの交点からそれぞれ遠ざかる向きの腕ベクトルと、この腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶するように枠線認識装置を構成した。
【０１９３】
また、本実施例では、枠線抽出部が、所定の交点を始点として腕ベクトルの向きに従った経路探索を行うことによって閉じた経路が検出された場合に、この閉じた経路を枠線として抽出し、閉じた経路の検出に用いられた腕ベクトルに対応するフラグを使用済みへ更新し、すべてのフラグが使用済みへ更新された場合に、経路探索を終了させるように枠線認識装置を構成した。したがって、枠線によって囲まれた様々な形状の対象領域を確実に認識することができる。
【０１９４】
なお、上述した実施例では、様々な形状の枠内領域を確実に認識することができるため、検出した枠内領域単位で、文字抽出に用いる閾値を変更するといった処理への応用が容易である。また、上述した実施例では、スキャナ装置（画像読取装置）とは独立した枠線認識装置について説明したが、スキャナ装置を含んだ枠線認識装置を構成することとしてもよい。また、枠線認識装置にいわゆるＯＣＲ（Optical Character Reader）機能を持たせ、認識した枠線内領域に対応する画像の文字認識を行わせることとしてもよい。
【産業上の利用可能性】
【０１９５】
以上のように、本発明に係る枠線認識装置および枠線認識方法は、枠線によって囲まれた様々な形状の対象領域を確実に認識したい場合に有用であり、特に、フリーフォーマットの帳票から、手書き文字等の文字を抽出したい場合に適している。
【符号の説明】
【０１９６】
１０ 枠線認識装置
１１ 制御部
１１ａ 画像取得部
１１ｂ 罫線抽出部
１１ｃ 交点抽出部
１１ｄ グループ化部
１１ｅ 枠線抽出部
１１ｆ 枠線内画像抽出部
１１ｇ 破線検出部
１１ｈ 交点補正部
１２ 記憶部
１２ａ 入力画像
１２ｂ 交点情報
１２ｃ 枠線情報
１２ｄ 枠線内画像
２０ 画像読取装置
【特許請求の範囲】
【請求項１】
入力画像から枠線を認識する枠線認識方法であって、
前記入力画像から抽出した罫線同士の交点を抽出する交点抽出工程と、
前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶部へ記憶させる交点情報記憶工程と、
所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出工程と、
前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新工程と、
前記更新工程によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出工程による前記経路探索を終了させる終了工程と
を含んだことを特徴とする枠線認識方法。
【請求項２】
前記交点抽出工程は、
前記入力画像から第１の方向の罫線を抽出して第１の識別子をそれぞれ付与するとともに、前記入力画像から前記第１の方向と垂直な第２の方向の罫線を抽出して第２の識別子をそれぞれ付与し、前記第１の識別子および前記第２の識別子の組み合わせで前記交点を特定することを特徴とする請求項１に記載の枠線認識方法。
【請求項３】
前記枠線抽出工程は、
お互いにつながった前記罫線を１つのグループとし、前記グループごとに前記経路探索を行うことを特徴とする請求項１または２に記載の枠線認識方法。
【請求項４】
前記枠線抽出工程は、
前記罫線で囲まれた閉領域における外周の前記経路探索の周回方向と、内周の前記経路探索の周回方向とを逆方向としたことを特徴とする請求項１、２または３に記載の枠線認識方法。
【請求項５】
前記枠線抽出工程は、
前記経路探索において前記交点の前記腕ベクトルの向きが複数ある場合には、前記外周の前記経路探索であれば前記閉領域の外側へ向かう向きを優先して前記腕ベクトルを選択し、前記内周の前記経路探索であれば前記閉領域の内側へ向かう向きを優先して前記腕ベクトルを選択することを特徴とする請求項４に記載の枠線認識方法。
【請求項６】
前記枠線抽出工程は、
抽出した前記枠線が同一の前記交点を複数回通過するものである場合に、当該枠線を当該交点で複数の前記枠線へ分割することを特徴とする請求項１〜５のいずれか一つに記載の枠線認識方法。
【請求項７】
前記交点抽出工程は、
前記罫線における前記交点ではない先端を延長した延長線を生成し、当該延長線が他の罫線の延長線または前記他の罫線自体と最初に交わる点を仮交点としたうえで、前記先端を含んだ所定の領域内に当該先端と前記他の罫線をつなぐ経路が存在する場合に、当該仮交点を前記交点として抽出することを特徴とする請求項１〜６のいずれか一つに記載の枠線認識方法。
【請求項８】
入力画像から枠線を認識する枠線認識装置であって、
前記入力画像から抽出した罫線同士の交点を抽出する交点抽出手段と、
前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶する交点情報記憶手段と、
所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出手段と、
前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新手段と、
前記更新手段によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出手段による前記経路探索を終了させる終了手段と
を備えたことを特徴とする枠線認識装置。
【請求項１】
入力画像から枠線を認識する枠線認識方法であって、
前記入力画像から抽出した罫線同士の交点を抽出する交点抽出工程と、
前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶部へ記憶させる交点情報記憶工程と、
所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出工程と、
前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新工程と、
前記更新工程によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出工程による前記経路探索を終了させる終了工程と
を含んだことを特徴とする枠線認識方法。
【請求項２】
前記交点抽出工程は、
前記入力画像から第１の方向の罫線を抽出して第１の識別子をそれぞれ付与するとともに、前記入力画像から前記第１の方向と垂直な第２の方向の罫線を抽出して第２の識別子をそれぞれ付与し、前記第１の識別子および前記第２の識別子の組み合わせで前記交点を特定することを特徴とする請求項１に記載の枠線認識方法。
【請求項３】
前記枠線抽出工程は、
お互いにつながった前記罫線を１つのグループとし、前記グループごとに前記経路探索を行うことを特徴とする請求項１または２に記載の枠線認識方法。
【請求項４】
前記枠線抽出工程は、
前記罫線で囲まれた閉領域における外周の前記経路探索の周回方向と、内周の前記経路探索の周回方向とを逆方向としたことを特徴とする請求項１、２または３に記載の枠線認識方法。
【請求項５】
前記枠線抽出工程は、
前記経路探索において前記交点の前記腕ベクトルの向きが複数ある場合には、前記外周の前記経路探索であれば前記閉領域の外側へ向かう向きを優先して前記腕ベクトルを選択し、前記内周の前記経路探索であれば前記閉領域の内側へ向かう向きを優先して前記腕ベクトルを選択することを特徴とする請求項４に記載の枠線認識方法。
【請求項６】
前記枠線抽出工程は、
抽出した前記枠線が同一の前記交点を複数回通過するものである場合に、当該枠線を当該交点で複数の前記枠線へ分割することを特徴とする請求項１〜５のいずれか一つに記載の枠線認識方法。
【請求項７】
前記交点抽出工程は、
前記罫線における前記交点ではない先端を延長した延長線を生成し、当該延長線が他の罫線の延長線または前記他の罫線自体と最初に交わる点を仮交点としたうえで、前記先端を含んだ所定の領域内に当該先端と前記他の罫線をつなぐ経路が存在する場合に、当該仮交点を前記交点として抽出することを特徴とする請求項１〜６のいずれか一つに記載の枠線認識方法。
【請求項８】
入力画像から枠線を認識する枠線認識装置であって、
前記入力画像から抽出した罫線同士の交点を抽出する交点抽出手段と、
前記交点に属する各罫線に沿って当該交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、当該腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶する交点情報記憶手段と、
所定の前記交点を始点として前記腕ベクトルの向きに従った前記経路探索を行うことによって閉じた経路が検出された場合に、当該閉じた経路を前記枠線として抽出する枠線抽出手段と、
前記閉じた経路の検出に用いられた前記腕ベクトルに対応する前記フラグを使用済みへ更新する更新手段と、
前記更新手段によってすべての前記フラグが使用済みへ更新された場合に、前記枠線抽出手段による前記経路探索を終了させる終了手段と
を備えたことを特徴とする枠線認識装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２０１２−６４０９８（Ｐ２０１２−６４０９８Ａ）
【公開日】平成２４年３月２９日（２０１２．３．２９）
【国際特許分類】
【出願番号】特願２０１０−２０９１２９（Ｐ２０１０−２０９１２９）
【出願日】平成２２年９月１７日（２０１０．９．１７）
【出願人】（０００００１４３２）グローリー株式会社 (1,344)
【Ｆターム（参考）】
【公開日】平成２４年３月２９日（２０１２．３．２９）
【国際特許分類】
【出願日】平成２２年９月１７日（２０１０．９．１７）
【出願人】（０００００１４３２）グローリー株式会社 (1,344)
【Ｆターム（参考）】
[ Back to top ]