(57)【要約】【課題】比較的簡単な処理で、重なりがある図形から個々の図形を分離すること。【解決手段】交点抽出手段２は、処理対象画像１から交点を抽出し、Ｔ型、Ｘ型、Ｌ型等の交点種情報と、交点に接続される線の接続情報を抽出し、交点情報テーブル３を生成する。また、交点数が０のパターン、接続先が自分自身である閉曲線は重なりを持たない図形と判断し分離する。分離点抽出手段４は、交点情報テーブル３の交点種情報と、接続情報等に基づき、各交点について、分離可能か分離せずに交点情報から削除するかを判定し、分離可能な交点を分離点として抽出する。図形分離手段５は上記分離点情報を元に、処理対象画像の線図形を分離する。分離された個々の図形は、例えば図形毎にベクトル化し、電子データとして復元したり再利用などに用いられる。【選択図】          図１
2004326223.tif 000002
【特許請求の範囲】
【請求項１】
図形画像から個々の線図形を分離する図形分離方法であって、
線３本以上が集まっている交点を抽出して、交点種情報および交点間の接続関係を抽出し、
上記交点について、上記交点種情報、および接続関係に基づき、分離可能とするか、分離せず交点情報から削除するかを判断して、分離可能な交点を分離点とし、
上記分離点の情報を元に図形の分離を行う
ことを特徴とする図形分離方法。
【請求項２】
交点を分離可能とするか、分離せず交点情報から削除するかを判断するに際し、上記交点を以下の（ａ）  〜（ｄ）  に分類し、
（ａ）  互いに線が交差して交点を構成している状態（Ｘ型）、
（ｂ）  ある線に対して、他の線が突き当たっている状態（Ｔ型）、
（ｃ）  交点を構成する線が互いに交点において他の線の端点に突き当たっている状態（Ｌ型）、
（ｄ）  線の端点、
上記（ａ），（ｂ）  において交点を構成している線のうち傾きが同一または交点をはさんで同じ曲率を持つ線を、交点を構成する線から除外し、残った交点を分離点とする
ことを特徴とする請求項１の図形分離方法。
【請求項３】
上記分離点の情報を元に図形の分離するに際し、以下の（ｉ）  〜（ｉｖ）の処理を繰り返すことにより、図形を分離する、
（ｉ）  交点数が０のパターン、または接続先が自分自身である閉曲線を持つパターンは重なりを持たない図形であると判断し分離する、
（ｉｉ）ＴおよびＸ型交点を構成している線のうち傾きが同一または交点をはさんで同じ曲率を持つ線を接続関係にあるとし、交点情報から除き、Ｔ型の交点に接続される線の内、同一の傾きを持たない線が上記交点に接続している点を終点とし、
（ｉｉｉ）  上記Ｔ型終点、Ｌ型、および、線分の端点を、分離可能な点である分離候補点とする、
（ｉｖ）分離候補点にはさまれた部分に交点がない場合には、その部分を分離する、
ことを特徴とする請求項１または請求項２の図形分離方法。
【請求項４】
図形画像から個々の線図形を分離する機能を備えた画像処理装置であって、
線３本以上が集まっている交点を抽出し、交点種情報および交点間の接続関係を抽出する交点抽出手段と、
上記交点について、上記交点種情報、および接続関係に基づき、分離可能とするか、分離せず交点情報から削除するかを判断して、分離可能な交点を分離点とする分離点抽出手段と、
上記分離点の情報を元に図形の分離を行う図形分離手段を備えた
ことを特徴とする図形分離機能を備えた画像処理装置。
【請求項５】
図形画像から個々の線図形を分離する図形分離プログラムであって、
上記プログラムは、図形どうし互いに重なりを持つ場合を含む図形画像に対して、線３本以上が集まっている交点を抽出して、交点種情報、交点間の接続関係を抽出する処理と、
上記交点について、上記交点種情報、および接続関係に基づき、分離可能とするか、分離せず交点情報から削除するかを判断して、分離可能な交点を分離点とする処理と、
上記分離点の情報を元に図形の分離を行う処理をコンピュータに実行させる
ことを特徴とする図形分離プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
近年、スキャナ等の入力機器の普及に伴って、画像を取り扱う機会が増加しており、それに伴って、文書を読み取るＯＣＲ（文字認識装置またはソフト）や、紙の情報を電子データとして復元する文書復元の需要が増加している。
本発明は、文書復元、再利用などを目的として、図形を多用している文書（例えばプレゼンテーション用の資料）等に含まれる重なりのある図形を、交点情報およびその接続関係を元に個々の線図形に分離する図形分離方法および図形分離機能を備えた画像処理装置に関し、このようにして分離・抽出された線図形は、例えば、部分毎にベクトル化したり、何の図形であるかを認識するために使用される。
【０００２】
【従来の技術】
図形画像から個々の図形を分離して抽出し、例えばベクトルデータに変換したり図形認識をすることにより、紙の情報を電子データとして復元することが行われている。
上記のように画像中の線図形を復元するには、図形どうしが重なりがなく孤立している場合だけでなく、図形どうし重なりがある場合も対象とする必要がある。図形どうし重なりのある状態を対象とする従来技術に関しては、例えば特許文献１に記載のものが知られている。
上記特許文献１に記載のものは、重なり線図形について非常に数多く存在する解釈候補の中から、少数の解釈候補を識別する。交点間の補完を行う毎に交点と線分の接続関係を示す接続行列を縮退させることにより判断している。
また、特許文献２には、複数の閉図形に対して図形の重なり態様を示す重合度を指定することにより、前記重合度による図形を認識する方式が開示されている。
【０００３】
【特許文献１】
特開平７−３３４６７４号公報
【特許文献２】
特開平２−１３２５６９号公報
【０００４】
【発明が解決しようとする課題】
上記のように従来から画像中の線図形を復元する方法が種々提案されているが、上記特許文献１に記載されるものは、判断する対象として、全ての補完パターンに対して、その中から正確な接続候補を選択する方式であり、処理に時間がかかり、また、線の補完まで一括して処理するため間違えた判断を行った場合に修正に手間が掛かるといった問題があった。
また、前記特許文献２に記載のものは、閉図形（四角形や６角形等）に対する方式であり、閉図形に加えて、直線など閉図形でない図形が存在する場合には処理対象にはならないといった問題があった。
本発明は上記従来技術の問題点を解決するためになされたものであって、本発明の目的は、比較的簡単な処理で、重なりがある図形から線図形を分離することができ、また、直線等の閉図形でない図形も分離することが可能な図形分離方法および図形分離機能を備えた画像処理装置を提供することである。
【０００５】
【課題を解決するための手段】
本発明においては、線図形どうしが重なりを持ち、また、閉図形および閉図形でないものが共に存在する場合に対応するために、交点種を形状により分類し、その接続関係を抽出し、それらの情報を用いて分離を行う。
まず、交点を次のように分類しそれぞれの接続関係を抽出する。交点情報としては、交点位置、交点種、構成する線、それぞれの線がどの交点に接続するかという情報である。すなわち、交点を（１）  Ｔ型、（２）  Ｘ型、（３）  Ｌ型、（３）  線の端点に分類する。
次に上記で作成した交点情報を元に分離を行う。その際、下記の一連のステップを繰り返すことで分離を実現する。
（ａ）  交点数が０のパターン、または接続先が自分自身である閉曲線は重なりを持たない図形と判断し分離する。
（ｂ）  Ｔ型およびＸ型交点を構成している線のうち、傾きが同一の線を接続関係にあるとし、交点情報から除く。
（ｃ）  交点情報から除かれたＴ型交点を構成している接続関係のない線の端点をＴ型終点とし、このＴ型終点、Ｌ型交点、線分の端点を分離可能な分離候補点とする。なお、Ｘ型交点は、接続関係のある線で構成されているので、交点情報を削除し、それぞれ分離可能な線として扱われる。
（ｄ）  分離候補点にはさまれた部分に交点がない場合には、その部分を分離する。
（ｅ）  上記（ａ）  から繰り返す。
本発明においては、上記のようにして図形を分離しているので、比較的簡単な処理で、重なりがある図形から線図形を分離することができ、また、直線等の閉図形でない図形も分離することが可能となる。
【０００６】
【発明の実施の形態】
以下、本発明の実施の形態について説明する。
図１は本発明の実施例の機能構成を示すブロック図である。
同図において、１は処理対象画像であり、この画像は、ここでは２値画像であるとし、また、書かれている図形は線図形であるとする。
２は交点抽出手段であり、上記処理対象画像１から交点を抽出し、交点種情報と、接続情報を抽出し、交点情報テーブル３を生成する。
４は分離点抽出手段であり、上記交点情報テーブル３の交点種情報と、接続情報等に基づき、各交点について、分離可能か分離せずに交点情報から削除するかを判定し、分離可能な交点を分離点として抽出する。
５は図形分離手段であり、上記分離点情報を元に、処理対象画像の線図形を分離する。
上記処理対象画像１は、例えば、プレゼンテーション用の資料等、図形を多用している文書に含まれる図形等であり、図２に示すように処理対象画像を本実施例により線図形に分離した後、分離された個々の図形について、図形認識を行ったり、あるいは分離された図形毎にベクトル化し、電子データとして復元したり、再利用などに用いられる。
【０００７】
以下、図３の処理対象画像を例として、本実施例について説明する。
まず、図１の交点抽出手段２で処理対象画像パターン中の交点を抽出する。ここで交点とは、３本以上の線が一箇所に集まっている個所であり、交点候補の位置が検出できればいかなる方式でも構わないが、一例として細線化画像を作成し、それをもとに交点を抽出する方法を以下に述べる。
１ドット幅に細線化した画像を対象として、それぞれの画素ごとに連結されている画素数を求める。注目画素に連結している画素が３以上であれば交点であるとみなして検出する。
例えば、図４では真ん中の斜線が付された画素には３画素が連結しているが、それ以外は１または２画素しか連結しておらず、この場合、交点は上記斜線が付された画素のみである。
【０００８】
次に交点の種類を抽出する。また、交点に接続している線の方向を調査し、交点をはさんで同一の方向を持つ線を組みとする。線の方向は例えば画素探索により検出する。
図５に交点種を示す。同図に示すように、３線により構成されている交点の２線が同一方向である場合にはＴ型交点とし、Ｘのように互いに交差している状態である場合をＸ型交点、同一方向を持つ線が他にない場合には、Ｌ型交点とする。なお、同図に示すように線分の端点も交点の一種であるとして抽出する。
以上の処理により、図３の例では、交点種として同図に示すようにＴ型交点Ｔ、Ｘ型交点Ｘ、線の端点Ｅが抽出される。
そして、これら交点種と、交点に接続される線がそれぞれ組み合わさった状態であるかを判断する。すなわち、交点を構成する線が同じ傾き／曲率を持つ場合には、組になっていると判断する。例えば、図５のＴ型交点における線分Ａ，Ｂは同一方向であるので、組と判断する。また、同一方向の線のみでなく、同図のＡ’，Ｂ’に示すように、同一の曲率を持ち、滑らかに接続している場合にも組とする。
【０００９】
上記のように交点が検出され、交点種と交点に接続される線の組が判断されたら、さらに、それぞれの交点情報に、どういう交点種であるかという情報に加えて、交点位置、交点を構成している線がどの交点に接続しているかの情報を作成する。交点と交点の連結状態は、画素を一つ一つ探索していき、その結果どの交点に接続するかを見つけることで判断することができる。
上記交点情報は、図１に示した交点情報テーブルに格納される。この交点情報テーブルには、上記交点種、交点に接続される線の組の情報、交点を構成している線がどの交点に接続しているかの情報が格納され、画素の連結成分毎に交点数、交点情報も分かるようにしておく。
図６に交点情報テーブルに格納される情報の１例を示す。
例えば、同図（ａ）に示す図形の交点Ｐ１，Ｐ２について、交点情報テーブルには、同図（ｂ）に示すような情報が格納される。すなわち、各交点番号に対応付けて、交点種、交点位置の座標、組となる線の情報、交点に接続される線の接続情報が格納される。
【００１０】
次に、作成した交点情報をもとに、図１の分離点抽出手段４で分離点を抽出し、図形分離手段５で図形の分離を行う。
図７は、本実施例の図形分離処理を示すフローチャートであり、図形の分離処理は以下に示すステップを繰り返すことにより実現する。
（ａ）  まず、交点数が０の連結成分（１）  または、接続先が自分自身である閉図形（２）  があるかを調べる（図７のステップＳ１）。
そして、交点数が０の連結成分（１）  、または接続先が自分自身である閉曲線（２）  は重なりを持たない図形と判断して分離し（ステップＳ２）、前記交点情報テーブル３の交点情報を更新する（ステップＳ３）。
例えば、図８（ａ）に示す線分や閉曲線、図８（ｂ）に示すように交点を持つが、接続先が自分自身である閉曲線は分離される。
【００１１】
ここで、接続先が自分自身であるとは以下のような場合を言う。
図３の三角形Ｄ１は一点で四角形と接触しているが、この交点情報は、四角を構成する横線が交点を挟んで同じ傾きを持ち、互いに組になっているため、それぞれの線が接続しているという交点情報をもつ。
一方、三角形Ｄ１を構成している斜めの２本の線は、傾きが一致していないため組にはなっていない。しかし、接続している交点情報が注目している交点であるため、線をたどると元に戻ってくることがわかる。このような閉曲線は、接続先が自分自身とであるとして分離する。
そして、上記三角形Ｄ１を分離することにより、線３本以上が一点に集まっている個所はなくなるため、この交点情報は前記交点情報テーブルから削除する。また、接続先としてこの交点を示していた他の交点があった場合、その交点情報の更新を行う。
以上の処理を行うことにより、例えば、図３の例において、図形Ｄ１，Ｄ２は図９（ａ）の点線に示すように分離され、三角形Ｄ１が接していた交点の情報は削除され、交点情報の更新が行われる。
【００１２】
（ｂ）  Ｔ型交点、Ｘ型交点を選択し（図７のステップＳ４）、ＴおよびＸ型交点を構成している線の中で、傾きが同一の線を接続関係にあるとして、交点を構成する線から除き（ステップＳ５）、交点情報を削除する（ステップＳ６）。
例えば、図９（ａ）の中のＸ型交点は、４本の線がそれぞれ交差している状態である。このように、傾きが同じで組になった線で構成される交点は、交点情報から除かれる。
この場合にも、接続先としてこの交点を示していた他の交点があった場合には、前記交点情報テーブルの情報の更新を行う。この情報の更新の際、交点の無くなる閉曲線であると判定された線は閉曲線として記憶しておく。
上記処理により、図９（ａ）のＸ型交点は、同図（ｂ）（ｃ）に示すように交点情報から除かれる。
【００１３】
（ｃ）  Ｔ型終点、Ｌ型、線分の端点を、分離可能な点である分離候補点とする（図７のステップＳ７）。
例えば、図１０（ａ）に示すようなＴ型交点について、傾きが同じで組になった線で構成される交点を交点情報から除くと、同図（ｂ）に示すように交点情報なしとなる。この場合、この交点に接続されていた線分Ｌ１の端点を、Ｔ型終点とし、分離可能な点であるとして分離候補点とする。
これにより、図９（ｂ）（ｃ）に示すようにＴ型交点は、分離候補点Ｃとなる。
（ｄ）  分離候補点にはされまれた部分に交点がないかを調べ（ステップＳ８）、あれば分離候補点間を分離し、交点情報を更新する。例えば、上記分離候補点Ｃで、図９（ｄ）に示すように各図形を分離し、分離図形を得る。
ｅ）分離候補点がなければ、（ａ）  に戻り（図７のステップＳ１に戻り）、上記処理を繰り返す。
なお、上記（ｂ）  において、Ｔ型交点を構成している線のうち接続関係をもつ線をたどっていくと注目交点に戻ってくる場合には、閉曲線としてあらかじめ分離しておいてもよい。
【００１４】
【発明の効果】
以上説明したように、本発明においては、図形どうし互いに重なりを持つ図形画像に対して、交点種情報および交点間の接続関係を用いて、交点を分離可能とする分離点候補を求め、この分離点情報を元に図形の分離を行っているので、比較的簡単な処理で、重なりのある図形を分離することができ、また、閉曲線や直線等の閉曲線でない図形が存在する場合でも処理対象とすることができる。
【図面の簡単な説明】
【図１】本発明の実施例の機能構成を示すブロック図である。
【図２】本発明の図形分離から図形認識までの処理の流れを示す図である。
【図３】本発明の実施例を説明するための使用する処理対象画像の例を示す図である。
【図４】交点の検出を説明する図である。
【図５】交点種を示す図である。
【図６】交点情報テーブルに格納される情報の１例を示す図である。
【図７】本発明の実施例の図形分離処理を示すフローチャートである。
【図８】交点数が０の連結成分、接続先が自分自身である閉図形の例を示す図である。
【図９】図形の分離手順を説明する図である。
【図１０】Ｔ型終点を説明する図である。
【符号の説明】
１    処理対象画像
２    交点抽出手段
３    交点情報テーブル
４    分離点抽出手段
５    図形分離手段
【図１】
2004326223.tif 000003
【図２】
2004326223.tif 000004
【図３】
2004326223.tif 000005
【図４】
2004326223.tif 000006
【図５】
2004326223.tif 000007
【図６】
2004326223.tif 000008
【図７】
2004326223.tif 000009
【図８】
2004326223.tif 000010
【図９】
2004326223.tif 000011
【図１０】
2004326223.tif 000012