(57)【特許請求の範囲】
【請求項１】
画像をラスタ走査して得られた画像情報を格納した画像データ格納部の画像情報の各画素について仮ラベルを割り付けて，実ラベルに変換を行う処理を行う高速ラベリング方式において，
前記画像データ格納部の画像データについて背景ではない画素である黒画素を検出すると該検出位置を黒画素検出位置格納部に格納する全白ライン抽出部と，
前記検出された黒画素を含む複数画素からなるラインをラベル付けラインとし，該ラベル付けラインの上の行の複数画素からなるラインを参照ラインとし，前記各ラインの左端の画素を含む複数画素については，それぞれの最初の画素の前に仮の前画素を設定し，前記各ラインの同じ位置同士の画素を先頭画素から順に照合して不一致が検出されると，それまでの一致が検出された参照ラインの複数の画素と前記ラベル付けラインの前記前画素とを近傍画素とし，前記ラベル付けラインの一致が検出された前記前画素を除く複数の画素を注目画素として抽出し，前記左端の画素を含む複数画素に続くラベル付けラインとその上の行の参照ラインについては，当該各ラインに関する直前の前記抽出処理により得られた各ラインの最終画素のそれぞれを次の前画素として設定して，前記各ラインの同じ位置同士の画素を照合して不一致が検出されると，それまでの一致が検出された参照ラインの複数の画素と前記ラベル付けラインの前記前画素とを近傍画素とし，前記ラベル付けラインの一致が検出された前記前画素を除く複数の画素を注目画素として抽出し，それぞれを注目画素と近傍画素格納部に格納する注目画素と近傍画素抽出部と，
予め参照ラインとラベル付けラインの各パターンに対応したラベル付けラインへの仮ラベル割付方法が規定された割付知識格納部と，
前記注目画素と近傍画素格納部に格納された注目画素と近傍画素のパターンと前記割付知識格納部のパターンを照合して適合するパターンに対応する仮ラベル割付方法を獲得する割付知識照合部と，
前記割付知識照合部により獲得した仮ラベル割付方法に従って前記ラベル付けラインに対し仮ラベルを割り付ける仮ラベル構成部と
を備えることを特徴とする高速ラベリング方式。
【請求項２】
請求項１において，
前記割付知識格納部において適用される知識情報は，使用頻度が高いものについて降順に適用順番を更新することを特徴とする高速ラベリング方式。
【請求項３】
請求項１または２の何れかにおいて，
先頭のラベル付けのラインの参照ラインを全白画素のラインに設定することで，先頭以外のラインと同様な処理を行えることを特徴とする高速ラベリング方式。
【請求項４】
請求項１乃至３の何れかにおいて，
前記全白ライン抽出部は，任意のラインの黒画素の有無を調査し，全白画素ラインを検出すると，仮ラベルを真ラベルに更新することで仮ラベルの領域を可能な限り縮小することを特徴とする高速ラベリング方式。
【請求項５】
請求項４において，
前記全白画素ラインが２ライン以上継続した場合には，前記仮ラベルの更新処理を行わないことを特徴とする高速ラベリング方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像中の複数の領域を分離区別するための高速ラベリング方式に関する。
【０００２】
近年，金融文書，ビジネス文書等を情報処理システムへ入力するための周辺機器として，文字認識装置（ＯＣＲという：Optical Charactor Reader) の需要が増大している。
【０００３】
ＯＣＲでは，文字切り出して，個々の文字の認識率を高めるには，認識の前段階である切り出し処理を正確に行うことが重要である。これまでは，帳票等の文字記入位置を予め指定した文書（ドロップアウトカラーではなく，黒枠や罫線等と文字が同じ色，または濃度で書かれたもの）に対し，指定した範囲内に文字が正しく書かれてあれば，かなりの率で文字を自動認識できたが，少しでも指定した範囲を超えて指定範囲を示す枠や罫線に接触，またははみ出しが生じると，著しく認識率が低下していた。
【０００４】
このように，罫線，枠に触れている文字から，文字だけを正確に切り出すための前処理を行うためにラベリング処理が用いられており，その高速化が望まれている。なお，ラベリング処理の技術は，ＯＣＲだけでなく，印刷文字認識装置，図面認識における文字，記号の切り出し，画像中の罫線と物体，図形，文字の接触部分の分離等のように直線と広い意味での図形が重なったパターンからその図だけ抽出する場合にも使用される。
【０００５】
【従来の技術】
図１１は従来例の説明図である。
【０００６】
従来のラスタ走査型ラベリング処理の方法を説明する。最初に，1 回目のラスタ走査で，背景でない画像部分に仮ラベルを割り付けると共に，仮ラベル間の接続関係を検出し，次にこの接続関係を整理することで，仮ラベルから実ラベルへの変換テーブルを作成し，続いて２回目のラスタ走査で変換テーブルを参照しながら，仮ラベル画像を実ラベル画像に変換する処理を行う。
【０００７】
ラスタ走査のラベリング処理を実行する場合，図１１のＡ．に示すようなウインドウを設定して，このウインドウを水平方向／垂直方向に１画素ずつずらしながら，このウインドウに含まれる画素のラベルを見ながら注目画素に対し仮ラベルを割り付けるものである。すなわち，図１１のＡに示すように，注目画素（仮ラベルが付与される対象となる画素）が“１”（文字等の画像を表す画素の値）の場合に，これに隣接する４つの画素（注目画素の左上画素，真上の画素，右上画素及び左画素）のラベルを識別して，４画素中に０でないラベルのものがあれば図１１のＢ．に示すようにそのラベル値を注目画素の仮ラベル値として設定し，４画素の何れも０のラベルであれば図１１のＣ．に示すように新規ラベル値を注目画素の仮ラベル値として設定する。
【０００８】
図１２〜図１４は従来のラベリング処理の説明図（その１）〜（その３）である。
【０００９】
図１２の(a) に示す２値化画像を処理対象とする場合，１回目のラスタ走査で，背景でない画像部分について注目画素が仮ラベルの割り付けられた画素に接続する場合には，その仮ラベルを注目画素に割り付けていくと共に，仮ラベルの割り付けられた画素に割り付けていくことで，図１２の(b) に示すような仮ラベルを割り付けると共に，仮ラベル１は仮ラベル２，３と接続するという，図１３の(a) に示すような接続関係を検出する。次に，この接続関係を整理することで，仮ラベル１はどの仮ラベルとも接続せず，仮ラベル２は仮ラベル１と接続し，仮ラベル３は仮ラベル１と接続し，仮ラベル４はどの仮ラベルとも接続せずといった，図１３の(b) に示す接続テーブルを作成して，この接続テーブルを更に整理することで，仮ラベル１には実ラベル１，仮ラベル２には実ラベル１，仮ラベル３には実ラベル１，仮ラベル４には実ラベル２を割り付けるという図１３の(c) に示す変換テーブルを作成する。なお，背景には実ラベル０が割り付けられる。続いて２回目のラスタ走査で，この変換テーブルを参照しながら仮ラベル画像を実ラベル画像に変換することで，図１４に示すような実ラベルが割り付けられる。
【００１０】
上記仮ラベルの割り付けを図１１のようなウインドウを用いて１画素ずつずらして仮ラベルを割り付ける従来の方法によると，仮ラベルの割り付けに時間がかかるという問題があった。
【００１１】
これを改良するために本発明と同じ出願人により先に「仮ラベル割付処理方式と実ラベル割付処理方式」（特願平５−２３７５５２号：特開平７−９３５３９号公報）が提案された。この提案された方式の概要を説明すると，予め２×Ｘ画素の大きさを持つウインドウを水平方向には重複することなく移動させ，垂直方向に１画素ずつずらして移動させる制御を行い，上段列を参照ラインとしウインドウの下段列を注目ラインとして，下段列の各画素に割りつける仮ラベルの割付方法を記述する複数のラベル割付ルールを，ウインドウ内画素の示す２値化パターンと対応付けて管理する手段を備え，ウインドウが新たな位置に移動するとウインドウ内画素の２値化パターンを特定し，特定された２値化パターンに従って対応するラベル割付ルールを検索し，検索されたラベル割り付けルールに従って，ウインドウの下段列の各画素に仮ラベルを割り付けるものである。
【００１２】
図１５は提案された方式によるラベル付けの１例を示す。
【００１３】
図１５にはａ〜ｈで表す各行にウインドウのパターンが設定され，ａ，ｂは２行×４画像（上段の４画素と下段の４画素）のパターン，ｃ〜ｈは２×２（上段の２画素と下段の２画素）のパターンであり，各パターンを構成する画素は白が背景を表し，黒が画像（文字や図形の線）を表し，それぞれ上段の画素が参照ラインで，下段の各画素が注目画素（下段の全て画像）である。
【００１４】
図１５において，ａのパターンは上段と下段の各４画素が全て背景の画素である例で，この場合は，下段の４画素に対してラベルは付与されず，背景を表す０が割り付けられる。ｂのパターン上段と下段の各４画素が全て画像の画素である例で，この場合は，下段の４画素に対してラベルは上段の参照ラインに割り付けられているラベル（Ｘで表す）と同一のＸのラベルが付与される。ｃ，ｄの場合は，注目画素が何れも背景の画素（０の値）であり，この場合はラベルは割り付けられない。ｅの場合は，下段の注目画素の中の右側の画素に対しＹ（新規仮ラベル番号）が割り付けられ，左側は割り付けられない（０のまま）。ｆの場合は，上段と下段の２つの画素が「０１」の場合であり，下段の右側の注目画素に対し上段の右側の画素に割り付けられたラベルと同じラベル（Ｘで表す）が割り付けられる。またはｇのパターンの場合，注目画素の下段の左側の画素に対しラベルＺを付与する。但し，Ｚは直前画素が黒画素の場合，それと同一ラベルを付けて，直前の２画素が白画素の場合，Ｚは新規仮ラベル番号となる。ｈのパターンでは，注目画素の下段の右側に画素に対しラベルＺを割付方法に示すようにして割り付けられる。
【００１５】
図１６は上記提案された方式による実ラベル割付処理方式の説明図であり，▲１▼はある画像の外接矩形（画像を表す図形に外接する矩形）であり，▲２▼は▲１▼の図形に接する画像の外接矩形を表す。仮ラベルの初期値として実ラベルの初期値を用いる従来の方法では正確に実ラベルが割り付けられなくなるので，これを防止するために，図１６の方式では，外接矩形単位で仮ラベルを実ラベルに割り付けるが，予め仮ラベルの初期値を実ラベルの初期値と異ならせて割り付け，図１６の(a) に示す例では▲１▼の外接矩形内については仮ラベルＬ，Ｌ＋１，Ｌ＋２というように割り付け，▲２▼の外接矩形内については仮ラベルＬ，Ｌ＋２が割り付けられている。
【００１６】
この(a) に示す各外接矩形▲１▼, ▲２▼の仮ラベルを実ラベルに変換する場合, 仮ラベル１を実ラベル１に，仮ラベル（Ｌ＋１）を実ラベル１に，仮ラベル（Ｌ＋２）を実ラベル２に，Ｌ以下の実ラベルはそのままとするように変換される。これにより，図１６の(b) に示すように▲１▼の外接矩形内の仮ラベルＬ／（Ｌ＋１）は実ラベル１に変換され，仮ラベル（Ｌ＋２）は実ラベル２に変換される。続いて▲２▼の外接矩形内について変換処理が行われることで，図１６の(c) に示すように，外接矩形▲１▼の仮ラベル（Ｌ＋２）は実ラベル２に変換され，仮ラベルとして扱われる実ラベル２はそのままの値を維持し，正確な実ラベルの割り付けが実現される。
【００１７】
【発明が解決しようとする課題】
上記提案されたウインドウパターンのラベル割付方法では，全てのウインドウパターンを作成することが困難であり，また，全パターン作成した場合には，どのパターンに対応するかを検索するのに時間を要するという問題があった。
【００１８】
本発明は全ウインドウパターンについてラベル割付を管理することなく，検索時間も全パターンを検索するより短縮してラベル値の割付を行うことができる高速ラベリング方式を提供することを目的とする。
【００１９】
【課題を解決するための手段】
図１は本発明の原理構成を示す図である。図中，１は全白ライン抽出部，２は注目画素と近傍画素抽出部，３は割付知識照合部，４は割付知識格納部，５は仮ラベル構成部，６は真ラベル構成部，７は記憶部であり，７ａはラスタ走査により得られた画像データ格納部，７ｂは黒画素検出位置格納部，７ｃは注目画素と近傍画素格納部，７ｄは割付知識照合結果格納部，７ｅは仮ラベルデータ格納部，７ｆは真ラベルデータ格納部である。
【００２０】
本発明は注目画素の近辺の画素に対し，予め設定されたルールに従い，集団の注目画素に一度にラベル付けを行うものである。
【００２１】
最初に，ラスタ走査により得られた画像データについて，全白ライン抽出部１はラスタ走査により画像データが得られるとこれを記憶部７の画像データ格納部７ａに格納する。この画像データについて各画素が行方向（または列方向）に画像の画素（線または黒を表すビット値を持つ画素）が全く無いラインの抽出を行う。この時，全白ラインが抽出されると，続くラインについても抽出を行って白ラインの連続を検出し，それらの全白ラインについては真ラベル構成部６が駆動されて，真ラベル（実ラベルと同じ）の割当てを行う。全白ライン抽出部１の抽出動作中に黒画素を検出すると，その黒画素位置を記憶部７の黒画素検出位置格納部７ｂに格納する。黒画素が検出されたラインに対して注目画素と近傍画素抽出部２による抽出動作が行われ，黒画素を含む画像の矩形領域に垂直方向の最上位のラインから順番にラベル付けラインとその上の参照ラインの対応する画素を照合して一致する画素の個数を検出して注目画素と近傍画素を抽出し，記憶部７の注目画素と近傍画素格納部７ｃに格納する。続いて，割付知識照合部３の動作により予め注目画素状態のパターンに対応する仮ラベルの割付方法が規定された割付知識格納部４の内容と照合し，仮ラベル割付方法を獲得すると照合結果を記憶部７の割付知識照合結果格納部７ｄに格納し，仮ラベル構成部５において仮ラベル割付方法に従ってラベル付けラインに対し仮ラベルを割り付けて記憶部７の仮ラベルデータ格納部７ｅに格納する。続いて，真ラベル構成部６により従来技術を用いて仮ラベルの接続関係の存在に応じて，真ラベル（実ラベル）を割り付けて記憶部７の真ラベルデータ格納部７ｆに格納する。この真ラベルデータ格納部７ｆの内容は印刷または表示として出力することができる。
【００２２】
【発明の実施の形態】
本発明はプログラムによりデータ処理する情報処理装置において実施することができ，上記図１に示す各部の処理フローと各部の関係及び具体例と共に以下に説明する。
【００２３】
図２は全白ライン抽出の処理フローであり，上記図１の全白ライン抽出部１の機能を実現するフローである。最初に２値画像のデータ（図１のエリア７ａに格納）を読込み（図２のＳ１），まずラインの属性（全白ライン，黒画素を含むラインの何れか）を表す変数ｙを０に設定する（同Ｓ２）。先頭（最上行）の横ラインの黒画素を探索し（図２のＳ３），黒画素があるか判別し（同Ｓ４），黒画素がない場合は全白ラインと決定する（同Ｓ５）。この場合，前ラインも全白ラインか判別し（図２のＳ６），前ラインが全白ラインでない場合は，新たな全白ラインでありこれに対し真ラベル構成部による真ラベル（実ラベル）の割り付けを実行する（同Ｓ７）。この場合，ｙ＝ｙ２に設定する。また，前ラインも全白ラインである場合は，ｙ＝ｙ３に設定して次の縦ライン（次の行）に移行する（図２のＳ１２）。続いて全ライン終了か判別し（同Ｓ１３），終了しない場合はＳ３に移行して同様の処理が繰り返され，終了した場合は真ラベル構成部の処理が実行される。
【００２４】
上記Ｓ４において黒画素が検出された場合，ｙ＝ｙ１に設定し，その黒画素位置を記憶部に格納する（図２のＳ８）。この黒画素位置は，次の注目画素と近傍画素抽出部の処理（同Ｓ９）における処理の開始位置として利用される。注目画素と近傍画素抽出部の処理の内容は後述する図４に示す。
【００２５】
この注目画素と近傍画素抽出部の処理に続いて，後述する割付知識照合部の処理（同Ｓ１０）及び仮ラベル構成部の処理（同Ｓ１１）が順に実行される。
【００２６】
図３は全白ライン抽出処理の具体例を示す。図３の(1) はラスタ走査により得られた２値画像であり，これに対し上記図２の全白ライン抽出の処理により，図３の(2) のような結果が得られる。すなわち, 黒画素を含むラインｙ１の下側に全白ラインのｙ２，ｙ３が存在し，その下にｙ１のラインが存在する。また，網掛け部分は白ライン内領域を表す。
【００２７】
図４は注目画素と近傍画素抽出の処理フローであり，上記図１の注目画素と近傍画素抽出部２の機能を実現する処理フローである。最初に処理の対象となる画像データとして予め水平方向サイズ（ｘｘ）と垂直方向サイズ（ｙｙ）が既知の値としてファイルにより与えられ，処理の開始時にこれらのサイズを設定する（図４のＳ１）。次に先頭の行から処理を行うため垂直方向（ｙ方向）を表す変数ｙを０に設定し（図４のＳ２），この行をラベル付けラインとし，これに対する参照ラインも設定する（同Ｓ３）。この参照ラインは，最初にラベルを割り付ける対象となる最上段のラベル付けライン（ｙ＝０のライン）の上のラインであるが，この最上段の画像は存在しないので，仮想的にラインが全て背景（０）と同じ値を持つ００〜０に設定される（横方向のｘｘ画素分）。
【００２８】
次に黒画素先頭位置（上記図２のＳ８で記憶）を横方向の位置を表すｘの初期値に設定し（図４のＳ４），続いて前画素初期値を０（背景）に設定する（同Ｓ５）。この場合の，前画素は，水平方向（ｘ方向）の参照ライン及びラベル付ラインの両方のラインの先頭画素に対しその直前に仮想的に初期値を０とする画素を設定するものである。ここで，画像の各画素のデータ構造に応じて次の２つの何れかが実行される。すなわち，１つの画素が８ビット以上（多値）で構成されている場合は，１画素（８ビットで構成）を注目画素に設定し（図４のＳ６），１画素が１ビットで構成されている場合は，８画素（８ビットで構成）を注目画素に設定する（同Ｓ７）。
【００２９】
Ｓ６またはＳ７に続いて，同じ参照／ラベル付けラインのパターンを獲得する（図４のＳ８）。これは，上，下に並んだ参照ラインとラベル付けラインの同じ位置（ｘ方向）の画素同士を照合して，同じ値をとるパターンを獲得するものである。これにより，例えば，先頭画素からｍ個の画素までが一致して，ｍ＋１画素目で不一致になると，その参照ラインのｍ個の画素と，ラベル付けラインの先頭画素が近傍画素となり，ラベル付けラインの先頭画素（前画素）を除いた（ｍ−１）個の画素が注目画素となる。
【００３０】
これに続いて，後述する割付知識照合部の処理が行われる（図４のＳ９）。その割付知識照合処理において，参照ラインとラベル付けラインの画素の対応付けによる一致数が増大する場合があり，その数をｎ個（ｎ≧ｍ）とする。次いで，ｘの値を上記により処理が行われた画素の隣の画素に更新し（図４のＳ１０），そのｘの値に対応した位置に画素があるか判別し（同Ｓ１１），ある場合は上記Ｓ８の処理における照合一致した最終画素を次の前画素に設定し（同Ｓ１２），上記Ｓ６またはＳ７の処理に戻り，新たなラインについて注目画素と近傍画素抽出の処理を行う。
【００３１】
上記Ｓ１１の処理において更新されたｘに対応する画素が無い場合にはそのラインの処理の対象となる画素が終了したことになり，このラベル付ラインに対して仮ラベル構成部（後述する）による仮ラベルを割り付ける処理が行われる（図４のＳ１３）。この後，次の参照ラインにラベル付けラインを設定し（図４のＳ１４），ｙの値を＋１して更新する（同Ｓ１５）。次にｙの値がｙ方向の最終ライン（サイズｙｙに対応）以下であるか判別し（図４のＳ１６），以下の場合は，次ラベル付けラインについて上記Ｓ４の処理が行われ，以下同様の処理が繰り返される。当該画像のｙ方向の最終ラインに達した場合には，真ラベル構成部による真ラベル（実ラベルと同じ）の割り付けが従来と同じ方法で行われる（同Ｓ１７）。
【００３２】
図５はライン毎の先頭画素を初期化した近傍画素と注目画素抽出の具体例である。
【００３３】
ライン毎に左端からラベル付けを行う場合，上記図４のＳ５の処理により最左端の画素の更に左側に仮の前画素を０に設定して付加する。図５の例では，Ａ．に示すように画像の中の一つの参照ラインに仮ラベルが，「００１０００２２０３３３０４４４４０」と割り付けられ，このラインに続くラベル付けラインの画素が図のように「０００１１１００００１０１１１１０」のパターンを備えている。この場合，参照ラインの先頭画素のラベルが０で，ラベル付けラインの先頭画素が０であるが，上記図４のＳ５の処理により，初期値が０（背景）である架空の前画素が先頭画素の前に付加され，図４のＳ８の処理により図５のＢ．に示すような注目画素（３つの□で表す画素）と近傍画素（参照ラインの０００１とラベル付けラインの先頭の０）が一致したパターンとして得られる。
【００３４】
このように前画素を設定することで，以降のラインの中間部分（ｘの値が０でない位置）の近傍画素と注目画素抽出の処理でも最左端かどうかの識別を要することなく，同様の流れでラベル付けを行うことができる。
【００３５】
図６は最初のラインに対する注目画素と近傍画素抽出の具体例である。
【００３６】
図６の例では，Ｂ．に示すように画像領域を構成する各ラインの画素が先頭ラインから順番に配列されている。この画像領域の先頭ライン（ｙ＝０）をラベル付けラインとする場合に，注目画素と近傍画素の抽出を行う場合，上記図４のＳ３の処理により全て背景（０）を持つＡ．に示すような仮想領域（水平方向のサイズは画像領域のサイズと同じ）を設定する。この先頭ラインに対する注目画素と近傍画素を抽出すると，上記図５に示した先頭画素を前に設定する処理を含めた処理により，Ｃ．に示すように注目画素（３個の□の画素）と近傍画素（参照ラインが４個の０の画素とラベル付けラインの先頭の０の画素）が抽出される。
【００３７】
このように，最初の１ライン目が全白ラインでない場合に，仮に全白ラインを参照ラインに設定することで，最初の１ラインかどうかを判定する必要がなく，２ライン以降と同様にラベル付けを行うことが可能となる。
【００３８】
図７，図８は割付知識の実施例（その１），（その２）を示す。この割付知識には，割付知識照合部（図１の３）において上記図４に示す処理により得られた注目画素と近傍画素のパターンと照合される多数のパターンが用意されている。
【００３９】
図７，図８には先頭の欄に注目画素状態が設定され，その後に対象となるパターン例，ラベル付け結果及びラベル割付方法の各欄が設けられている。最初の(a) には参照ライン及びラベル付けラインが共に全部白画素である場合で，「００００」，「００」「０００００００」のパターンについてラベル付け結果が図に示すように０ラベルのパターンが付けられる。(b) は参照ライン及びラベル付けラインの共に全部黒画素である場合で, この場合は参照ラインのラベルと同一のラベル（Ｘ）を図に示すように付けられる。(c) は, 参照ラインが白画素（全部），ラベル付けラインが黒画素で右端が白画素である場合で，直前画素に黒画素が存在すれば，Ｙ０となる（ただしＹは、直前画素のラベルと同一、そうでなければＹは新規ラベルを割り付ける）。(d) の場合ラベル付けラインが連続する白画素（参照ラインは不問）であり，ラベル割付は全部０となる。
【００４０】
図８に示す(e) は参照ラインが白画素（全部）で，ラベル付けラインの左側が白画素，右側が黒画素の場合であり，ラベル付けは０Ｙ，００Ｙ，０００ＹＹＹＹである。但しＹは新規仮ラベル番号である。(f) はラベル付けラインが参照ラインと同一パターンで，左端が白画素の場合であり，図のラベル付け結果に示すような仮ラベルが割り付けられる。(g) はラベル付けラインが参照ラインと同一パターンで，左端が黒画素の場合であり，図のラベル付け結果に示すような仮ラベルが割り付けられる。(h) は参照ラインの左側が白画素で右側が黒画素の時，ラベル付けラインの左側が黒画素右側は不問であり，ラベル割付方法は，直前画素が黒画素の場合，Ｚはそれと同一ラベル直前の２画素が白画素の場合，Ｚは参照ラインと同一ラベルとなる。
【００４１】
上記図７，図８に示す割付知識については，各パターンの順は使用頻度に応じて適用順番を更新するようにして，効率的な照合を可能にする。
【００４２】
上記図４の注目画素と近傍画素抽出の処理フローにより得られた注目画素と近傍画素を上記図７，図８に示す割付知識の各パターンとの照合が割付知識照合部（図１の３）において行われる。この処理は単純にパターンを照合する処理であり，従来の技術により実現することができる。
【００４３】
図９は仮ラベル付けの処理フローであり，割付知識照合部（図１の３）による割付の後実行され，上記図１の仮ラベル構成部５の機能を実現するものである。最初に，上記の注目画素と近傍画素抽出の処理において検出された注目画素数（Ｎｃとする）を設定する（図９のＳ１）。次に注目画素の全画素に０であるか判別し（図９のＳ２），全画素が０である場合は上記図７の(a) の注目画素の状態に対応し，これに対してはＮｃ個にラベルとして値０を設定する（同Ｓ３）。上記Ｓ２において，全画素が０でないことが分かると，全部同一のＬ（ラベル番号）であるかの判別を行い（図９のＳ４），同一である場合は上図７の(b) の注目画素の状態に対応し，その注目画素のＮｃ個の仮ラベルはＬ（番号）に設定する（同Ｓ５）。続いて，ラベルＬの矩形情報を更新し（同Ｓ６），ｙ＝ｙ＋１する。これは，同じラベルの値が上のラインから当該対象とするラインへと継続するので，そのラベルのサイズを表す矩形情報の行方向の値を＋１する。Ｓ６の次は後述するＳ１０へ移行する。
【００４４】
図９において，Ｓ２，Ｓ４の何れにも該当しない場合，次に参照ラインの同位置と同一のラベルであるかの判別を行う（図９のＳ７）。同一である場合は，上記図８の(f) または(g) を変形した場合に該当し, Ｎｃ個の参照ラインのラベルを注目画素に対するラベルとしてコピーし（図９のＳ８），コピーした全ラベルの矩形情報を更新する（同Ｓ９）。続いて，他のラベルと接続関係を見てラベルを統合する必要があるか判別し（図９のＳ１０），必要があれば左画素と左端上画素のラベルを統合し（同Ｓ１１），必要がなければ終了する。また，上記Ｓ７の判別でＮＯである場合は，黒画素にラベルＫ（番号）を設定し（同Ｓ１２），ラベルＫの矩形情報を更新し（同Ｓ１３），上記Ｓ１０に移行する。
【００４５】
図１０は仮ラベル付けの具体的な動作手順を示す。
【００４６】
注目画素は参照ラインとラベル付けラインがそれぞれ８画素分が図に示すようなパターンを持つものとする（図１０の丸１ )。このパターンについて上記図７，図８に示すような割付知識と照合を行うと（図１０の丸２），図８の(f) に規定する状態（参照ラインと同一パターンで左端が白画素）であることが分かる（図１０の丸３）。これにより，(f) を適用する間の注目画素の探索を行う（図１０の丸４）。すなわち，注目画素として上記(1))に示すような８画素が設定されているが，この(f) を適用することで, 更に後続の参照ラインとラベル付けラインのパターンについても探索を行い, 結局２５画素まで一致することが分かる。次に，前画素を含む近傍ラベル（参照ラインのラベル）を抽出する（図１０の丸５）。図の例では，前画素のラベルがＺで，その後の各画素に対し０（背景）のラベルを挟んでＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆの各ラベルが付けられる。続いて上記(f) に規定されたラベル割付方法により仮ラベルを構成することで（図１０の丸６），ラベル付けラインのラベルが参照ラインからのコピーにより割り付けられる。この後，ラベルＡ〜Ｆの各矩形情報（矩形の左上の座標ｘ１，ｙ１と右下の座標ｘ２，ｙ２で表す）の更新が行われる（図１０の丸７）。この例では，仮ラベルＡ〜Ｆのそれぞれについて，それぞれ矩形情報のｙ２の値を＋１（下の行に増加させる）する。
【００４７】
このようにして，各ラベル付けラインに対して仮ラベルを割り付けられた後は，従来と同様の技術を用いた図１の真ラベル構成部６により真ラベル（実ラベル）の割り付けが行われる。
【００４８】
【発明の効果】
本発明によれば，全てのウインドウパターンについてラベル割付を管理することなく，また検索時間も全パターンを検索するより短縮することができるため，ラベル値の割り付けを効果的に行うことができる。また，ラベル矩形の小容量化及び高速化を促進できる。特に，帳票等を含んだビジネス文書を扱う場合に有効である。
【００４９】
出願人による実際の試験での測定結果によれば，従来のラベリングと比較して処理時間が４０％〜６０％減少した。
【図面の簡単な説明】
【図１】本発明の原理構成を示す図である。
【図２】全白ライン抽出の処理フローを示す図である。
【図３】全白ライン抽出処理の具体例を示す図である。
【図４】注目画素と近傍画素抽出の処理フローを示す図である。
【図５】ライン毎の先頭画素を初期化した近傍画素と注目画素抽出の具体例を示す図である。
【図６】最初のラインに対する注目画素と近傍画素抽出の具体例を示す図である。
【図７】割付知識の実施例（その１）を示す図である。
【図８】割付知識の実施例（その２）を示す図である。
【図９】仮ラベル付けの処理フローを示す図である。
【図１０】仮ラベル付けの具体的な動作手順を示す図である。
【図１１】従来例の説明図である。
【図１２】従来のラベリング処理の説明図（その１）である。
【図１３】従来のラベリング処理の説明図（その２）である。
【図１４】従来のラベリング処理の説明図（その３）である。
【図１５】提案された方式によるラベル付けの１例を示す図である。
【図１６】提案された方式による実ラベル割付処理方式の説明図である。
【符号の説明】
１      全白ライン抽出部
２      注目画素と近傍画素抽出部
３      割付知識照合部
４      割付知識格納部
５      仮ラベル構成部
６      真ラベル構成部
７      記憶部
７ａ    画像データ格納部
７ｂ    黒画素検出位置格納部
７ｃ    注目画素と近傍画素格納部
７ｄ    割付知識照合結果格納部
７ｅ    仮ラベルデータ格納部
７ｆ    真ラベルデータ格納部
【図１】
0004763113.tif 000002
【図２】
0004763113.tif 000003
【図３】
0004763113.tif 000004
【図４】
0004763113.tif 000005
【図５】
0004763113.tif 000006
【図６】
0004763113.tif 000007
【図７】
0004763113.tif 000008
【図８】
0004763113.tif 000009
【図９】
0004763113.tif 000010
【図１０】
0004763113.tif 000011
【図１１】
0004763113.tif 000012
【図１２】
0004763113.tif 000013
【図１３】
0004763113.tif 000014
【図１４】
0004763113.tif 000015
【図１５】
0004763113.tif 000016
【図１６】
0004763113.tif 000017