(57)【特許請求の範囲】
【請求項１】
入力された２値画像データから、画素の繋がった連結領域の外接矩形を算出し、各外接矩形にラベルを付して記憶する外接矩形算出手段と、
前記外接矩形算出手段により算出された各外接矩形について、他の外接矩形との重なりの有無を判定する重なり判定手段と、
前記重なり判定手段の判定で重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を、内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める細分割手段と、
前記入力された２値画像データ、前記重なり判定手段の判定で重なり無しと判定された外接矩形の座標、及び、前記細分割手段によって求められた親及び各々の子の外接矩形とからなるデータを出力する出力手段を備えた連結領域抽出装置において、
前記重なり判定手段の判定で重なり有りと判定された外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する単一ラベル判定手段を備えると共に、
前記判定結果が単一ラベルであれば、その外接矩形の座標データを前記出力手段へ送り、単一ラベルでなければ、その外接矩形の座標データを前記細分割手段へ送る機能を備えている、
ことを特徴とする連結領域抽出装置。
【請求項２】
前記細分割手段は、
前記外接矩形の細分割処理を行う過程で算出した外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する単一ラベル判定手段を備えると共に、
前記単一ラベル判定手段の判定結果が単一ラベルであれば、その外接矩形についての細分割処理を終了させ、単一ラベルでなければ、その外接矩形についての細分割処理を行わせる機能を備えている、
ことを特徴とする請求項１記載の連結領域抽出装置。
【請求項３】
入力された２値画像データから画素の繋がった連結領域の外接矩形を算出し、各外接矩形にラベルを付して記憶する外接矩形算出手段と、
前記外接矩形算出手段により算出された各外接矩形について、他の外接矩形との重なりの有無を判定する重なり判定手段と、
前記重なり判定手段の判定で重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める細分割手段と、
前記入力された２値画像データ、前記重なり判定手段の判定で重なり無しと判定された外接矩形の座標、及び、前記細分割手段によって求められた親及び各々の子の外接矩形とからなるデータを出力する出力手段を備えた連結領域抽出装置に、
前記重なり判定で、重なり有りと判定された外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する手順と、
前記判定結果が単一ラベルであれば、その外接矩形の座標データを前記出力手段へ送り、単一ラベルでなければ、その外接矩形の座標データを前記細分割手段へ送る手順と、
を実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
近年、金融文書、ビジネス文書等の入力周辺機器として、文字認識装置ＯＣＲ（以下、単に「ＯＣＲ」という）の需要が増加している。本願発明は、このようなＯＣＲ等に利用されるものであり、例えば、ＯＣＲにおける文字切り出し処理に適用して有効な連結領域抽出装置及び記録媒体に関するものである。
【０００２】
前記ＯＣＲにおける文字切り出し処理において、個々の文字の高い認識率を実現するためには、認識の前段階である「切り出し処理」が、その正確さの点で重要である。従来は、記帳等の文字記入位置を予め指定した文書（ドロップアウトカラーではなく、黒枠罫線と文字が同じような色、または濃度で書かれたもの）に対して、指定した範囲内に文字が綺麗に書かれてあれば、かなりの率で文字を自動認識できたが、少しでも指定した範囲を越えて、指定範囲を示す枠や罫線に接触したり、或いは、指定範囲を示す枠や罫線からはみ出しが生じると、著しく認識率が低下する、という問題が生じていた。
【０００３】
そこで、このような問題に対して、罫線、枠に触れている文字から、文字だけを正確に切り出す技術の開発が要望されていた。なお、本願発明は、ＯＣＲだけでなく、印刷文字認識装置、図面認識における文字、記号の切り出し、画像中の罫線と物体、図形、文字の接触部分の分離等のように、直線と広い意味での図形が重なったパターンから、その図だけを抽出する技術にも利用可能である。
【０００４】
【従来の技術】
以下、従来例を説明する。
【０００５】
§１：従来例の一般的な説明
従来、２値画像データから画素が１つに繋がった連結領域（連結成分）を抽出し、その連結領域に基づいてラベル画像情報を作成する連結領域抽出装置が知られていた（例えば、特開平８−５５２１９号公報、特開平７−３２５９２１号公報参照）。
【０００６】
近年、２値画像データから画素の繋がった連結領域を抽出するラベリング手法は、画像を解析して画像中から文字や図形等を抽出する手段として重要になってきている。例えば、手書き文字認識装置（ＯＣＲ）においては、複数文字から個々の文字を切り出す手段として、その前処理部にラベリング手法が使用されている。更に、検査や監視を目的とした画像処理の応用システムに幅広く実現されている。前記ラベリング手法については、例えば、特願平３−２０６５７４号公報、特願平５−２３７５５２号の明細書及び図面に記載されているようによく知られた技術なので説明は省略する。以下、特開平８−５５２１９号公報に記載された発明の概要を従来例として説明する。
【０００７】
§２：連結領域抽出装置の概要
前記連結領域抽出装置は、入力された２値画像データから画素の繋がった連結領域（連結成分）の外接矩形を算出し、各外接矩形にラベルを付してメモリに記憶する外接矩形算出手段と、前記外接矩形算出手段によって算出された各外接矩形について他の外接矩形との重なりの有無を判定する重なり判定手段と、前記重なり判定手段で重なり有りの判定がなされた場合、その外接矩形に再びラベリング処理を行って、そのラベル画像を作成し、そのラベル画像の外接矩形を親として、その内部に含まれるラベルを元に、子の外接矩形に細分割し、更にその子の外接矩形を内部に含まれるラベルの数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める細分割手段と、前記入力された２値画像、重なり無しと判定された外接矩形の座標と、及び細分割手段によって求められた親及び各々の子の外接矩形とからなるデータを出力する出力手段等を含んで構成される。
【０００８】
前記連結領域抽出装置の処理概要は次の通りである。外接矩形算出手段は、入力された２値画像データから連結領域の外接矩形を算出し、各外接矩形にラベルを付して記憶する。次に、重なり判定手段は、外接矩形算出手段によって算出された各外接矩形について他の外接矩形との重なりの有無を判定し、重なり有りと判定された場合、更に細分割手段により再度のラベリング処理を行い、再分割処理を行う。
【０００９】
この場合、細分割手段は、再度ラベリングされたラベル画像の外接矩形を親として、その内部に含まれるラベルを元に、子の外接矩形に細分割し（再度、外接矩形を算出し）、更に、子の外接矩形を内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める。出力手段は、入力された２値画像データと、重なり判定手段によって重なり無しと判定された外接矩形の座標と、細分割手段によって求められた親及び各々の子の外接矩形とからなるデータを出力する。
【００１０】
§３：連結領域抽出処理の概要説明
図８は従来例の説明図（その１）である。以下、図８の具体例に基づき、前記連結領域抽出装置における連結領域抽出処理の概要を説明する。
【００１１】
連結成分抽出部１は、入力した２値画像データから、画素の繋がった成分である連結成分（或いは連結領域）を抽出する。この時、抽出された連結成分に対しラベリング処理を行う。例えば、図示の例ではラベル１の連結成分とラベル２の連結成分が存在している。次に、連結成分細分割部２は、前記抽出された連結成分内に更に他の連結成分が含まれる時は、前記抽出された連結成分（２−１）を、その内部に含まれる各連結成分（２−２，２−３）の領域に細分割する。
【００１２】
そして、細分割領域判定部３は、前記ラベルに基づいて細分割された各領域がどの連結成分のものか判定する。この例の場合、細分割領域（２−１）はラベル２の連結成分に属し、（２−２）はラベル１の連結成分に属し、（２−３）はラベル２の連結成分に属する、というように判定を行なう。
【００１３】
そして、細分割領域記憶部４は、前記抽出された連結成分を細分割した各領域（細分割領域）の和、差等の算術式で表現し、記憶部（バッファメモリ等）に記憶する。例えば、ラベル２の領域＝＋（２−１）の領域−（２−２）の領域＋（２−３）の領域、というようにしてこのデータを記憶部に記憶する。
【００１４】
以上のように、一画面全体のラベル、又は他の連結成分と重なり部を有する連結成分のラベル画像を記憶した方式と違って、連結成分が細分割された領域の和、差等で表現することによって、記憶するラベル画像その数を減少、又は皆無にすることができる。
【００１５】
§４：フローチャートによる処理の説明
図９は従来例の説明図（その２）である。以下、図９のフローチャートに基づいて詳細な処理を説明する。なお、図の(1) 〜(8) は各処理を示す。
【００１６】
(1) ：先ず、入力された２値画像データにラベリング処理（例えば、特願平３−２０６５７４号公報、特願平５−２３７５５２号の明細書及び図面参照）を施して、連結したパターン（連結成分）毎に、それらを区別するためのラベルが付いた、その連結パターンの外接矩形を算出する。この場合、外接矩形の意味は、画面上の座標及びラベルをその属性として含むことがある。
【００１７】
(2) ：次に、各ラベルの外接矩形がお互いに重なっているかどうかを判定する。すなわち、外接矩形の重なりを判定する。
【００１８】
(3) ：前記(2) の重なり判定の結果に基づいて、重なっていないラベル（非重なりラベル）に対しては、重なっていないラベル（番号）と、その外接矩形の対応関係を記憶部に記憶する。
【００１９】
(4) ：また、(2) の重なり判定の結果に基づいて、重なっているラベルについては、注目するラベル内の画像に対して再び連結パターン毎の外接矩形を算出する（重なり注目ラベル内再外接矩形算出処理を行う）。
【００２０】
(5) ：次に、注目ラベルの外接矩形は、再外接矩形算出のための画像サイズと一致することから、重なり注目ラベル以外のラベルの外接矩形（以下、この外接矩形のことを「雑音外接矩形」、又は「他の外接矩形」という）を算出する。
【００２１】
(6) ：雑音外接矩形内に含まれる複数個の連結パターンが１つであるか否かを確認する。具体的には、各雑音外接矩形を対象として、再び連結パターンの外接矩形を算出し、その外接矩形の数から単一ラベルか否かを確認する。
【００２２】
(7) ：複数個の外接矩形が全て単一ラベルの場合には、それらの雑音外接矩形を重なり注目ラベル内の雑音矩形として記憶部に記憶しておく。こうして、ラベル画像を復元する時には、重なり注目ラベルの外接矩形から雑音外接矩形を除いた領域が重なり注目ラベルの領域となる。
【００２３】
(8) ：複数個の雑音外接矩形が一つでも単一ラベル（即ち、注目ラベルと同一ラベル）でない場合、重なり注目ラベル内のラベル画像を記憶部に記憶する。このラベル画像は、重なり注目ラベルの矩形内画像に対してラベリング処理を行って算出するが、前記(4) の外接矩形算出の際に、ラベル画像の記憶を同時に行っても良い。
【００２４】
このように、連結パターンを外接矩形だけでなく、ラベル画像と共に表現して出力する。このようにして出力された外接矩形及びラベル画像に基づいて、画像処理装置は画像解析、文書画像処理等を行う。
【００２５】
§５：細分割処理例の説明
図１０は従来例の説明図（その３）である。以下、図１０に基づいて、細分割処理例を説明する。
【００２６】
前記例では、重なり部で注目ラベル以外の外接矩形が単一である場合にのみ、注目ラベルの外接矩形を外接矩形の演算式で表現し、重なり部で注目ラベル以外の外接矩形が複数存在した場合には、ラベル画像を記憶した。しかし、この例では、ラベル画像の記憶に要するデータ量を削減するために、注目ラベル以外の外接矩形（雑音外接矩形）の内部に含まれるラベルが単一になるまで、細分割を繰り返す。
【００２７】
この細分割処理では、先ず、注目ラベルの外接矩形内に存在する各外接矩形（雑音外接矩形）内のラベルが単一になるまで、雑音外接矩形を細分割する処理を繰り返す。この場合、注目ラベルの外接矩形を親（この例では、ラベル９）とすると、子１、子２・・・というように、注目ラベルの外接矩形は階層的に表現できる。
【００２８】
この例では、左上の座標（Ｘ１９，Ｙ１９）と、右下の座標（Ｘ２９，Ｙ２９）で表された外接矩形がラベル９の親であり、左上の座標（Ｘ１９２，Ｙ１９２）と、右下の座標（Ｘ２９２，Ｙ２９２）で表された外接矩形が、ラベル１の子１であり、左上の座標（Ｘ１９３，Ｙ１９３）と、右下の座標（Ｘ２９３，Ｙ２９３）で表された外接矩形が、ラベル１−１の子２である。
【００２９】
このようにして、注目ラベルの外接矩形内に存在する各外接矩形内のラベルが単一になるまで、雑音外接矩形を細分割する処理を繰り返す。そして、細分割した各領域（細分割領域）の和、差等の算術式で表現し、記憶部（バッファメモリ等）に記憶する。例えば、ラベル９の領域＝＋（９−１）の領域−（９−２）の領域＋（９−３）の領域、というようにしてこのデータを記憶部に記憶する。
【００３０】
【発明が解決しようとする課題】
前記のような従来のものにおいては、次のような課題があった。
【００３１】
(1) ：従来の細分割処理では、重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を、内部に含まれるラベル数が単一になるまで細分割する操作を繰り返して行っていた。
【００３２】
このため、重なり合った外接矩形内で、雑音以外の小さいラベルがあった場合に、部分ラベリング回数が増加し、細分割処理の時間が長くなっていた。
【００３３】
(2) ：従来の連結領域抽出処理でかすれた画像を扱う場合、かすれた画像は細かいラベルが多く存在するため、細分割処理においてラベリング処理や外接矩形の算出処理等を何度も処理を繰り返して行う必要があった。このため、処理時間が長くなっていた。
【００３４】
本発明は、このような従来の課題を解決し、連結領域抽出処理全体の処理量を少なくして、処理の高速化を達成することを目的とする。
【００３５】
【課題を解決するための手段】
図１は本発明の原理説明図である。本発明は前記の目的を達成するため、次のように構成した。
【００３６】
(1) ：入力された２値画像データから画素の繋がった連結領域の外接矩形を算出し、各外接矩形にラベルを付して記憶する外接矩形算出手段１２Ａと、前記外接矩形算出手段１２Ａにより算出された各外接矩形について、他の外接矩形との重なりの有無を判定する重なり判定手段１３Ａと、前記重なり判定手段１３Ａの判定で重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を、内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める細分割手段１５Ａと、前記入力された２値画像データ、前記重なり判定手段の判定で重なり無しと判定された外接矩形の座標、及び、前記細分割手段によって求められた親及び各々の子の外接矩形とからなるデータを出力する出力手段１６Ａを備えた連結領域抽出装置において、前記重なり判定手段の判定で重なり有りと判定された外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する単一ラベル判定手段１４Ａを備えると共に、前記判定結果が単一ラベルであれば、その外接矩形の座標データを前記出力手段へ送り、単一ラベルでなければ、その外接矩形の座標データを前記細分割手段１５Ａへ送る機能を備えている。
【００３７】
(2) ：前記(1) の連結領域抽出装置において、前記細分割手段１５Ａは、前記外接矩形の細分割処理を行う過程で算出した外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する単一ラベル判定手段１７Ａを備えると共に、前記単一ラベル判定手段１７Ａの判定結果が単一ラベルであれば、その外接矩形についての細分割処理を終了させ、単一ラベルでなければ、その外接矩形についての細分割処理を行わせる機能を備えている。
【００３８】
(3) ：入力された２値画像データから画素の繋がった連結領域の外接矩形を算出し、各外接矩形にラベルを付して記憶する外接矩形算出手段１２Ａと、前記外接矩形算出手段１２Ａにより算出された各外接矩形について、他の外接矩形との重なりの有無を判定する重なり判定手段１３Ａと、前記重なり判定手段１３Ａの判定で重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める細分割手段１５Ａと、前記入力された２値画像データ、前記重なり判定手段の判定で重なり無しと判定された外接矩形の座標、及び、前記細分割手段によって求められた親及び各々の子の外接矩形とからなるデータを出力する出力手段１６Ａを備えた連結領域抽出装置に、前記重なり判定で、重なり有りと判定された外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する手順と、前記判定結果が単一ラベルであれば、その外接矩形の座標データを前記出力手段へ送り、単一ラベルでなければ、その外接矩形の座標データを前記細分割手段へ送る手順とを実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【００３９】
（作用）
前記構成に基づく本発明の作用を、図１に基づいて説明する。
【００４０】
(a) ：前記(1) では、外接矩形算出手段１２Ａは、入力された２値画像データから画素の繋がった連結領域（画素の連結成分）の外接矩形を算出し、各外接矩形にラベルを付して記憶する（例えば、図示しないワークメモリに記憶する）。次に、重なり判定手段１３Ａは、前記外接矩形算出手段１２Ａにより算出された各外接矩形について、他の外接矩形との重なりの有無を判定する。
【００４１】
その結果、重なり無しであれば、外接矩形の座標を出力手段１６Ａへ送り、重なり有りであれば、その重なり有りと判定された外接矩形に対し、単一ラベル判定手段１４Ａが単一ラベルか否かを判定する。この場合、単一ラベル判定手段１４Ａは、前記外接矩形の縦方向、又は横方向のサイズを算出し、前記サイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する。
【００４２】
そして、単一ラベルであると判定した場合には、その外接矩形の座標データを前記出力手段１６Ａへ送り、単一ラベルでないと判定した場合は、その外接矩形の座標データを細分割手段１５Ａへ送る。
【００４３】
その後、細分割手段１５Ａは、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求め、そのデータを出力手段へ送る。
【００４４】
このように、重なり判定手段１３Ａで重なり有りと判定された外接矩形について、細分割手段１５Ａにより細分割処理を行う前に、単一ラベル判定手段１４Ａにより単一ラベルか否かの判定を行ない、単一ラベルと判定された場合は、細分割処理を行うことなく、該当する外接矩形の座標データを出力手段１６Ａへ出力する。
【００４５】
このため、単一ラベルと判定された外接矩形についての余分な細分割処理を行う必要がなくなり、その分、処理量を少なくして処理の高速化を達成できる。すなわち、従来の細分割手段１５Ａでは、重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を、内部に含まれるラベル数が単一になるまで細分割する操作を繰り返して行うが、この細分割処理において行う単一ラベルの判定を行う際のラベリング処理時間等を削減することができる。
【００４６】
これは、前記単一ラベル判定手段１４Ａにより、ラベル内部に、他のラベルが明らかに無いと判明しているケースを外接矩形サイズから算出することで、内部のラベル数をラベリング等の処理をすることなく判別できるからである。従って、前記のように、処理量を少なくして処理の高速化を達成することができる。
【００４７】
(b) ：前記(2) では、前記単一ラベル判定手段１４Ａにより、単一ラベルでないと判定された場合、細分割手段１５Ａは、対象とする外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し（外接矩形を算出し）、更に、その子の外接矩形を内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める処理を行う。
【００４８】
この場合、単一ラベル判定手段１７Ａが、細分割処理の過程で算出した外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する。そして、前記判定結果が単一ラベルであれば、その外接矩形についての細分割処理を終了させ、単一ラベルでなければ、その外接矩形について更に細分割処理を行わせる。このようにすれば、繰り返し行う細分割処理の処理量が少なくなり、細分割処理の高速化が達成できる。
【００４９】
(3) ：連結領域抽出装置の制御部（例えば、ＣＰＵ）が、前記記録媒体のプログラムを読み出して実行することにより、連結領域抽出処理における重なり判定で、重なり有りと判定された外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する手順と、前記判定結果が単一ラベルであれば、その外接矩形の座標データを出力手段へ送り、単一ラベルでなければ、その外接矩形の座標データを細分割手段１５Ａへ送る手順とを実行する。
【００５０】
このように、重なり判定処理で重なり有りと判定された外接矩形について、細分割処理を行う前に、単一ラベル判定処理により単一ラベルか否かの判定を行ない、単一ラベルと判定された場合は、細分割処理を行うことなく、該当する外接矩形の座標データを出力手段１６Ａへ出力する。
【００５１】
このため、余分な細分割処理を行う必要がなくなり、処理量を少なくして処理の高速化を達成できる。すなわち、従来は、重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を、内部に含まれるラベル数が単一になるまで細分割する操作を繰り返して行うが、この細分割処理において行う単一ラベルの判定を行う際のラベリング処理時間を削減することができる。
【００５２】
これは、前記単一ラベル判定処理により、ラベル内部に、他のラベルが明らかに無いと判明しているケースを外接矩形サイズから算出することで、内部のラベル数をラベリング等の処理をすることなく判別できるからである。従って、前記のように、処理量を少なくして処理の高速化を達成することができる。
【００５３】
【発明の実施の形態】
以下、発明の実施の形態を図面に基づいて詳細に説明する。
【００５４】
§１：連結領域抽出装置の説明
図２は連結領域抽出装置のブロック図である。以下、図２に基づいて、連結領域抽出装置を説明する。連結領域抽出装置は、入力された２値画像データから画素の連結成分（連結領域）を抽出し、その情報を一画面のラベル画像情報として出力する装置であり、出力されたラベル画像情報は、例えば、画像処理装置へ送り画像処理を行う。
【００５５】
この連結領域抽出装置は、入力した２値画像データを一時格納する２値画像記憶部１１（例えば、バッファメモリ）と、２値画像記憶部１１に格納された２値画像データから、画素の繋がった成分である連結成分（或いは連結領域）を抽出し、その連結成分の外接矩形を算出して、各外接矩形にラベルを付してラベル画像とし、このラベル画像をワークメモリに格納する外接矩形算出部１２と、前記算出された各外接矩形について他の外接矩形との重なりの有無を判定する重なり判定部１３と、前記重なり判定部１３の判定で、重なり有りと判定された場合、単一ラベルか否かを判定する単一ラベル判定部１４と、前記単一ラベル判定部１４で単一ラベルでないと判定された場合、更に細分割を行う細分割部１５と、前記各部で処理された後のデータを出力する出力部１６を設け、更に、前記細分割部１５内に単一ラベル判定部１７を設ける。
【００５６】
この場合、前記細分割部１５は、外接矩形算出部１２により作成されたラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に子の外接矩形を内部に含まれるラベル数が各々の子の外接矩形の座標を求める処理を行うが、このような細分割処理を行う際、単一ラベル判定部１４により、単一ラベルか否かの判定を行い、単一ラベルと判定した場合は、細分割処理を終了して出力部１６へ出力する。
【００５７】
なお、前記単一ラベル判定部１４、１７を除く他の構成、すなわち、２値画像記憶部１１、外接矩形算出部１２、重なり判定部１３、細分割部１５、出力部１６の構成は、前記従来例（特開平８−５５２１９号公報参照）と同じである。
【００５８】
§２：連結領域抽出処理の説明
図３は連結領域抽出処理フローチャートである。以下、図２を参照しながら図３に基づいて、２値画像データの連結領域抽出処理を説明する。なお、Ｓ１〜Ｓ８は各処理ステップを示す。
【００５９】
先ず、入力された２値画像データを２値画像記憶部１１に記憶する（Ｓ１）。その後、外接矩形算出部１２は、前記２値画像記憶部１１に記憶された２値画像データを取り出し、画素が繋がった連結成分（連結領域）の外接矩形を算出する（Ｓ２）。
【００６０】
この場合、前記２値画像データにラベリング処理（例えば、特願平３−２０６５７４号、特願平５−２３７５５２号の明細書及び図面参照）を施して、連結したパターン（連結成分）毎に、それらを区別するラベルが付いた、その連結したパターンの外接矩形を求めワークメモリに格納する。
【００６１】
次に、重なり判定部１３は、外接矩形算出部１２が算出した外接矩形に対し、各ラベルの外接矩形がお互いに重なっているかどうかを判定する（Ｓ３）。その結果、重なりが有ると判定された場合には（Ｓ４）、単一ラベル判定部１４により単一ラベルか否かの判定を行う（Ｓ５）。しかし、前記Ｓ４の処理で重なり無しと判定された場合には、判定対象の外接矩形を出力部１６へ出力する。
【００６２】
そして、前記Ｓ６の処理で単一ラベルか否かの判定を行ない、単一ラベルであると判定された場合には、その外接矩形のデータを出力装置１６へ出力する。しかし、前記Ｓ５の単一ラベル判定処理で単一ラベルでないと判定された場合は、外接矩形の細分割処理（細分割処理の詳細は後述する）を行い（Ｓ７）、細分割後のデータを出力部１６へ出力へ送る（Ｓ８）。以上のようにして、２値画像データの連結領域抽出処理を行う。
【００６３】
§３：細分割処理の説明
図４は細分割処理フローチャートである。以下、図４に基づいて前記細分割処理を説明する。なお、Ｓ１１〜Ｓ１７は各処理ステップを示す。この処理は、前記図２に示した細分割部１５が行う処理であり、単一ラベル判定部１７による単一ラベル判定処理を含む処理である。
【００６４】
前記単一ラベル判定部１４により単一ラベルでないと判定された外接矩形データに対し、細分割部１５が細分割処理を行うが、この処理では先ず、単一ラベル判定部１７により単一ラベルか否かの判定を行う。すなわち、注目ラベル以外の他ラベル（雑音ラベル）が単一ラベルかどうかの判定処理を行う（Ｓ１１）。
【００６５】
その結果、単一ラベルであれば（Ｓ１２）、細分割処理を終了するが、単一ラベルでなければ、細分割部１５が再び、外接矩形の算出処理（再外接矩形算出処理）を行う（Ｓ１３）。そして、前記算出した外接矩形は注目ラベルか否かの判定処理を行なう（Ｓ１４）。その結果、前記算出した外接矩形が注目ラベルでなければ（Ｓ１５）、細分割処理を終了するが、注目ラベルであれば、算出した外接矩形について再び単一ラベルか否かの判定処理を行う（Ｓ１６）。
【００６６】
その結果、単一ラベルであると判定した場合（Ｓ１７）は、細分割処理を終了するが、単一ラベルでないと判定した場合は前記Ｓ１１の処理から繰り返して行う。以上のようにして、注目ラベル以外の他外接矩形（雑音外接矩形）の内部に含まれるラベルが単一になるまで、細分割処理（Ｓ１１〜Ｓ１７）を繰り返して行う。
【００６７】
§４：単一ラベル判定処理の説明
図５は単一ラベル判定処理フローチャートである。また、図６は単一ラベル判定処理説明図であり、Ａ図は重なり外接矩形、Ｂ図はラベル内部に他の重なりラベルが存在しない図の例１、Ｃ図はラベル内部に他の重なりラベルが存在しない図の例２、Ｄ図は内部にラベルが存在する図の例１、Ｅ図は内部にラベルが存在する図の例２である。なお、図６の「０」、「１」は２値画像データの「白」、「黒」画素を示す。
【００６８】
以下、図６を参照しながら図５のフローチャートに基づいて単一ラベル判定処理を説明する。この処理は、単一ラベル判定部１４、１７が行う処理であり、Ｓ２１〜Ｓ２７は各処理ステップを示す。また、重なり外接矩形のデータ等は、図示しないワークメモリに格納されているとする。
【００６９】
例えば、図６のＡ図に示したように、重なり外接矩形の左上の座標点がＰ１、右下の座標点がＰ２とし、Ｐ１＝（ｘ１，ｙ１）、Ｐ２＝（ｘ２，ｙ２）であるとする。単一ラベル判定部１４、１７は、先ず、重なり外接矩形の左上の座標Ｐ１＝（ｘ１，ｙ１）と、右下の座標Ｐ２＝（ｘ２，ｙ２）をワークメモリから取得する（Ｓ２１）。
【００７０】
そして、重なり外接矩形の横幅（横方向の画素数）Ｗ＝（ｘ２−ｘ１＋１）と、高さ（縦方向の画素数）Ｈ＝（ｙ２−ｙ１＋１）を算出する（Ｓ２２）。なお、前記Ｗ、Ｈの式において、＋１があるのは、画素に幅があるためである。そして、最小単一ラベルのサイズＳ（予め設定した値Ｓ＝２）を取得し（Ｓ２３）、Ｗ≦Ｓの条件を満たしているかどうかを判定する（Ｓ２４）。
【００７１】
その結果、Ｗ≦Ｓの条件を満たしていれば、単一ラベルと判定し（Ｓ２６）、処理を終了するが、Ｗ≦Ｓの条件を満たしていなければ、Ｈ≦Ｓ（Ｓ＝２）の条件を満たしているか否かを判定する（Ｓ２５）。その結果、Ｈ≦Ｓの条件を満たしていれば、単一ラベルと判定し（Ｓ２６）、処理を終了するが、Ｈ≦Ｓの条件を満たしていなければ、従来の処理を行う（Ｓ２７）。
【００７２】
前記処理において、Ｓ＝２（２画素）とし、図６のＢ図に示したように、Ｗ＝２（横幅＝２画素）であれば、Ｗ≦Ｓの条件を満たしており、ラベル内に他の重なりラベルが存在しない。また、図６のＣ図に示したように、Ｗ＝２（横幅＝２画素）でない場合でも、Ｈ≦Ｓの条件を満たしていれば、ラベル内に他の重なりラベルが存在しないと判定する。更に、図６のＤ図のように、Ｗ＝３（横幅＝３）の場合、或いは、Ｅ図のように、Ｈ＝３（高さ＝３）の場合、内部にラベルが存在すると判定する。
【００７３】
すなわち、Ｗ＝２以下、又はＨ＝２以下なら、Ｗ又はＨは２画素か１画素なので、このような幅の画素からなるラベルの内部に、他の重なりラベルが存在することはない。しかし、Ｗ＝３以上、又はＨ＝３以上なら、前記ラベルの内部に、他の重なりラベルが存在する可能性があるので、前記のように判定する。
【００７４】
以上のように、単一ラベル判定部１４、１７では、判定対象の外接矩形の横方向のサイズ（横幅＝Ｗ）、又は縦方向のサイズ（高さ＝Ｈ）を算出し、前記いずれかのサイズが２画素以下（Ｗ≦２、又はＨ≦２）であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する。
【００７５】
このように、ラベル内部に、他のラベルが明らかに無いと判明しているケースを、外接矩形サイズ（Ｗ、Ｈ）から算出することで、従来のように、内部のラベル数を算出したり、ラベリング処理を行ったりすることなく、簡単、かつ短時間で単一ラベル判定処理を行うことができ、処理の高速化を達成できる。
【００７６】
§５：連結領域抽出装置の具体的な装置例と記録媒体の説明
図７は具体的な装置例である。前記連結領域抽出装置は、パーソナルコンピュータ、ワークステーション等の任意のコンピュータにより実現することができる。この装置は、コンピュータ本体２１と、該コンピュータ本体２１に接続されたディスプレイ装置２２、入力装置（キーボード／マウス等）２３、リムーバブルディスクドライブ（「ＲＤＤ」という）２４、磁気ディスク装置（「ＭＤＤ」という）２５等で構成されている。
【００７７】
そして、前記コンピュータ本体２１には、内部の各種制御や処理を行うＣＰＵ２６と、プログラムや各種データを格納しておくためのＲＯＭ２７と、メモリ２８（ワークメモリ）と、インタフェース制御部（「Ｉ／Ｆ制御部」という）２９と、通信制御部３０等が設けてある。なお、前記ＲＤＤ２４には、フレキシブルディスクドライブや光ディスクドライブ等が含まれる。
【００７８】
前記構成の装置において、例えば、前記ＲＯＭ２７、或いはＭＤＤ２５の磁気ディスク（記録媒体）に、前記連結領域抽出処理を実現するためのプログラムを格納しておき、このプログラムをＣＰＵ２６が読み出して実行することにより、前記連結領域抽出処理を実行する。
【００７９】
しかし、本願発明は、このような例に限らず、例えば、ＭＤＤ２５の磁気ディスクに、次のようにしてプログラムを格納し、このプログラムをＣＰＵ２６が実行することで前記連結領域抽出処理を行うことも可能である。
【００８０】
▲１▼：他の装置で作成されたリムーバブルディスクに格納されているプログラム（他の装置で作成したプログラムデータ）を、ＲＤＤ２４により読み取り、ＭＤＤ２５の記録媒体に格納する。
【００８１】
▲２▼：ＬＡＮ等の通信回線を介して他の装置から伝送されたプログラム等のデータを、通信制御部３０を介して受信し、そのデータをＭＤＤ２５の記録媒体（磁気ディスク）に格納する。
【００８２】
【発明の効果】
以上説明したように、本発明によれば次のような効果がある。
【００８３】
(1) ：連結領域抽出装置に単一ラベル判定手段を設け、単一ラベルと判定した外接矩形について、以降の処理を省略するので、連結領域抽出処理全体の処理量を少なくして、処理の高速化を達成できる。
【００８４】
(2) ：単一ラベル判定手段では、ラベル内部に、他のラベルが無いと判明しているケースを外接矩形サイズから算出することで、従来行っていたラベリング処理等を省略できる。その結果、連結領域抽出処理の処理量を少なくして、処理の高速化を達成できる。特に、かすれた画像は細かいラベルが多いため、前記効果が顕著に現れる。
【００８５】
(3) ：外接矩形算出手段により算出された各外接矩形について、重なり判定手段は他の外接矩形との重なりの有無を判定し、重なり無しであれば外接矩形の座標を出力手段へ送り、重なり有りであればその重なり有りと判定された外接矩形に対し、単一ラベル判定手段が単一ラベルか否かを判定する。
【００８６】
この場合、単一ラベル判定手段は、外接矩形の縦方向、又は横方向のサイズを算出し、前記サイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する。そして、単一ラベルであると判定した場合には、その外接矩形の座標データを前記出力手段へ送り、単一ラベルでないと判定した場合は、その外接矩形の座標データを細分割手段へ送る。
【００８７】
このように、重なり判定手段で重なり有りと判定された外接矩形について、細分割手段により細分割処理を行う前に、単一ラベル判定処理により単一ラベルか否かの判定を行ない、単一ラベルと判定された場合は、細分割処理を行うことなく、該当する外接矩形の座標データを出力手段へ出力する。
【００８８】
このため、単一ラベルと判定された外接矩形についての細分割処理を行う必要がなくなり、その分、処理量を少なくして処理の高速化を達成できる。すなわち、従来の細分割手段では、重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を、内部に含まれるラベル数が単一になるまで細分割する操作を繰り返して行うが、単一ラベルと判定された外接矩形については、この細分割処理を削減することができる。
【００８９】
また、ラベル内部に、他のラベルが無いと判明しているケースを外接矩形サイズから算出することで、従来行っていたラベリング処理等を省略できる。その結果、連結領域抽出処理の処理量を少なくして、処理の高速化を達成できる。特に、かすれた画像は細かいラベルが多いため、前記効果が顕著に現れる。従って、連結領域抽出処理の処理量を少なくして、処理の高速化を達成することができる。
【００９０】
(4) ：重なり判定手段により他の外接矩形との重なり有りと判定された外接矩形について単一ラベルか否かの判定を行い、単一ラベルでないと判定された外接矩形に対して細分割処理を行う。この細分割処理において、細分割手段は、該当する外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を内部に含まれるラベル数が単一になるまで細分割する操作を繰り返し、ラベル数が単一になったときの各々の子の外接矩形の座標を求める処理を行う。
【００９１】
この場合、細分割手段内部の単一ラベル判定手段が、細分割処理の過程で算出した外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する。そして、前記判定結果が単一ラベルであれば、その外接矩形についての細分割処理を終了させる。
【００９２】
このようにすれば、細分割処理を行う場合、単一ラベルと判定された外接矩形については、以降の処理を省略できる。従って、繰り返し行う細分割処理の処理量が少なくなり、細分割処理の高速化が達成できる。この場合、特に、ラベル内部に、他のラベルが無いと判明しているケースを外接矩形サイズから算出することで、ラベリング処理等を省略できる。
【００９３】
その結果、特に、細分割処理の処理量を少なくして、処理の高速化を達成できる。特に、かすれた画像は細かいラベルが多いため、かすれた画像を扱う場合には、前記効果が顕著に現れる。
【００９４】
(5) ：連結領域抽出装置の制御部（例えば、ＣＰＵ）が、前記記録媒体のプログラムを読み出して実行することにより、連結領域抽出処理における重なり判定で、重なり有りと判定された外接矩形に対し、その外接矩形の縦方向、又は横方向のサイズを算出し、前記いずれかのサイズが２画素以下であった場合に、そのラベル内部に他の重なりラベルが無い単一ラベルであると判定する手順と、前記判定結果が単一ラベルであれば、その外接矩形の座標データを出力手段へ送り、単一ラベルでなければ、その外接矩形の座標データを細分割手段へ送る手順とを実行する。
【００９５】
このように、重なり判定処理で重なり有りと判定された外接矩形について、細分割処理を行う前に、単一ラベル判定処理により単一ラベルか否かの判定を行ない、単一ラベルと判定された場合は、細分割処理を行うことなく、該当する外接矩形の座標データを出力手段へ出力する。
【００９６】
このため、余分な細分割処理を行う必要がなくなり、処理量を少なくして処理の高速化を達成できる。すなわち、従来は、重なり有りと判定された外接矩形に対し、再度ラベリング処理を行なってラベル画像を作成し、該ラベル画像の外接矩形を親として、その内部に含まれるラベルを基に、子の外接矩形に細分割し、更に、その子の外接矩形を、内部に含まれるラベル数が単一になるまで細分割する操作を繰り返して行うが、この細分割処理を削減することができる。
【００９７】
また、ラベル内部に、他のラベルが無いと判明しているケースを外接矩形サイズから算出することで、従来行っていたラベリング処理等を省略できる。その結果、連結領域抽出処理の処理量を少なくして、処理の高速化を達成できる。特に、かすれた画像は細かいラベルが多いため、前記効果が顕著に現れる。従って、連結領域抽出処理の処理量を少なくして、処理の高速化を達成することができる。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】本発明の実施の形態における連結領域抽出装置のブロック図である。
【図３】本発明の実施の形態における連結領域抽出処理フローチャートである。
【図４】本発明の実施の形態における細分割処理フローチャートである。
【図５】本発明の実施の形態における単一ラベル判定処理フローチャートである。
【図６】本発明の実施の形態における単一ラベル判定処理説明図である。
【図７】本発明の実施の形態における具体的な装置例である。
【図８】従来例の説明図（その１）である。
【図９】従来例の説明図（その２）である。
【図１０】従来例の説明図（その３）である。
【符号の説明】
１  連結成分抽出部
２  連結成分細分割部
３  細分割領域判定部
４  細分割領域記憶部
１１  ２値画像記憶部
１２  外接矩形算出部
１３  重なり判定部
１４  単一ラベル判定部
１５  細分割部
１６  出力部
１７  単一ラベル判定部
２１  コンピュータ本体
２２  ディスプレイ装置
２３  入力装置
２４  リムーバブルディスクドライブ
２５  磁気ディスク装置
２６  ＣＰＵ（中央処理装置）
２７  ＲＯＭ（リードオンリメモリ）
２８  メモリ
２９  インタフェース制御部（Ｉ／Ｆ制御部）
３０  通信制御部
【図１】
0004322999.tif 000002
【図２】
0004322999.tif 000003
【図３】
0004322999.tif 000004
【図４】
0004322999.tif 000005
【図５】
0004322999.tif 000006
【図６】
0004322999.tif 000007
【図７】
0004322999.tif 000008
【図８】
0004322999.tif 000009
【図９】
0004322999.tif 000010
【図１０】
0004322999.tif 000011