閉図形抽出装置
【課題】任意の線図形に対して正確に抽出可能で、不要な接続点の認識を排除することができる閉図形抽出装置を提供する。
【解決手段】複数のベクトルによって構成される線図形の中から、空間的に閉塞した領域としての閉図形を抽出する閉図形抽出装置１０である。閉図形抽出装置１０は、前記線図形を構成する各ベクトルについて、互いの接続関係を対応づけ、各ベクトルを開始ベクトルとして、追跡方向を記録しながら連続的に追跡して追跡リストを作成し、抽出された閉図形のうち、任意の２つの閉図形を構成する追跡リストに共通する任意の一つのベクトルが、連続かつ互いに異なる追跡方向を有するように前記追跡リストを再配置して、当該２つの追跡リストを合成する。
【解決手段】複数のベクトルによって構成される線図形の中から、空間的に閉塞した領域としての閉図形を抽出する閉図形抽出装置１０である。閉図形抽出装置１０は、前記線図形を構成する各ベクトルについて、互いの接続関係を対応づけ、各ベクトルを開始ベクトルとして、追跡方向を記録しながら連続的に追跡して追跡リストを作成し、抽出された閉図形のうち、任意の２つの閉図形を構成する追跡リストに共通する任意の一つのベクトルが、連続かつ互いに異なる追跡方向を有するように前記追跡リストを再配置して、当該２つの追跡リストを合成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、閉図形抽出装置に関し、より具体的には、複数の線によって構成される線図形の中から、空間的に閉塞した領域として閉図形を抽出する閉図形抽出装置に関する。
【背景技術】
【０００２】
従来、パーソナルコンピュータやＣＡＤ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ）装置等の図形処理装置によって、地図、回路パターン図、設計図等の線図形を処理する場合、しばしば当該線図形の中から空間的に閉塞した領域としての閉図形を抽出することが要求される。
【０００３】
従来、線図形から閉図形を抽出する技術の一例として、特開平３−１７１３７８号公報（特許文献１）に開示された「閉領域自動認識装置」がある。また、線図形から閉図形を抽出する他の従来技術として、特開平２−２４５９８７号公報（特許文献２）に開示された「線図形認識装置の閉ループ抽出方法」がある。
【０００４】
しかし、上記特許文献１の技術では、線図形の中に、一方の閉図形がその内部に他方の閉図形を包含し、かつ他方の閉図形が一方の閉図形と１点で接しているような閉図形群が存在している場合、閉図形を正しく抽出できないという問題点があった。
【０００５】
さらに、上記特許文献２の技術は、アークの追跡時に、追跡中ノードに接続するアークのすべてについて、その反対側ノード（追跡中ノードと反対側のノード）の接続状況を調べるという複雑な条件判断を行っているため、追跡に時間がかかるという問題点を有していた。
【０００６】
かかる問題を解消すべく、特開平６−１１９４４６号公報（特許文献３）に開示の「閉図形抽出装置」が公知となっている。追跡中のアークが閉図形以外の図形部分に到達しても、再び追跡開始アークの追跡開始方向に戻るまでアークの追跡が中断することなく続行されるため、閉図形以外の図形部分に分岐点ノードが存在する場合であっても、アークの追跡が途中で中断することがなくなり、閉図形を正しく抽出できる。
【特許文献１】特開平３−１７１３７８号公報
【特許文献２】特開平２−２４５９８７号公報
【特許文献３】特開平６−１１９４４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、特許文献３にかかる閉図形抽出装置は、例えば、図２７に示すような、Ｖ１０１〜Ｖ１０４で構成された１つの閉図形を貫通する線分Ｖ１０５が存在する場合、当該成分で区画された２つの閉図形Ｌ１０１，Ｌ１０３としての抽出が可能であるが、Ｖ１０５〜Ｖ１０８で構成された１つの閉図形（すなわちＬ１０２＋Ｌ１０３の閉図形）を抽出することは不可能であった。
【０００８】
すなわち、特許文献３にかかる閉図形抽出装置は、追跡中ノードに接続する３以上のアークが存在する場合、現在追跡中のアークを除き、当該アークから見て最も右側（左側でも同様である）に折れるアークを次の追跡中アークとすることから、Ｖ１０５の追跡過程において、ノードＣ１０１でＶ１０５を直進して追跡することができない。よって、Ｖ１０５の全線分を構成要素とする閉図形Ｌ１０３の抽出を行うことができないという問題があった。
【０００９】
さらに、特許文献３にかかる閉図形抽出装置は、１つの閉図形がその一部に他方の閉図形を包含し、かつ他方の閉図形が一方の閉図形と一点で接しているような閉図形群が存在している場合（図２８）、他方の閉図形と一点で接している１の閉図形の当該接点Ｓを新たなノード（接続点）として判断することとなる。そして、このように１つの閉図形の１つの線分の途中にノード（接続点）が認識されると、当該閉図形において各ノード毎に変形式を持つような特殊な拡大縮小変形処理を行う場合に、自動追加されたノードには適切な変形式が未設定であることから、意図した変形結果を得ることが困難となる。例えば、閉図形抽出装置が服飾型作成の編集作業装置に組み込まれて使用される場合、規準サイズからのサイズアップ及びサイズダウンの処理に問題となる。
【００１０】
したがって、本発明が解決しようとする技術的課題は、上記問題を解消し、１つの閉図形を貫通する線分が存在する場合などの図形を含む任意の線図形に対して正確に抽出可能で、不要な接続点の認識を排除することができる閉図形抽出装置を提供することである。
【課題を解決するための手段】
【００１１】
本発明は、上記技術的課題を解決するために、以下の構成の閉図形抽出装置を提供する。
【００１２】
本発明の第１態様によれば、複数のベクトルによって構成される線図形の中から、空間的に閉塞した領域としての閉図形を抽出する閉図形抽出装置であって、
前記線図形を構成する各ベクトルを格納するベクトルリストと、
前記ベクトルリストに格納されているベクトルについて、他のベクトルとの交点を抽出し、前記交点が存在する場合は当該ベクトルを分割して作成された新たなベクトルを互いの接続関係を対応づけて前記ベクトルリストに登録する、交点抽出手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして、追跡方向を記録しながら連続的に追跡して追跡リストを作成し、追跡リストに含まれる連続するベクトルが同一で互いに異なる追跡方向を有している場合は当該ベクトルを除外しつつ閉図形を抽出する追跡手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして
前記追跡手段で抽出された閉図形のうち、任意の２つの閉図形を構成する追跡リストに共通する任意の一つのベクトルが、連続かつ互いに異なる追跡方向を有するように前記追跡リストを再配置して、当該２つの追跡リストを合成する共有ベクトル合成手段と、
前記抽出図形を構成するベクトルが、交点抽出手段により分割されたベクトルを含む場合、前記ベクトルリストの接続関係に基づいて、統合したベクトルに置き換える、ベクトル統合手段とを備えることを特徴とする、閉図形抽出装置を提供する。
【００１３】
本発明の第２態様によれば、前記追跡手段は、
右回りに追跡処理して追跡リストを作成する第１追跡手段と、
左回りに追跡処理して追跡リストを作成する第２追跡手段とを備える、ことを特徴とする、第１態様の閉図形抽出装置を提供する。
【００１４】
本発明の第３態様によれば、前記共有ベクトル合成手段は、前記追跡リスト変換手段により変換された前記共通ベクトルが連続するように前記追跡リストを合成することを特徴とする、第１又は第２態様の閉図形抽出装置を提供する。
【００１５】
本発明の第４態様によれば、前記共有ベクトル合成手段は、合成された追跡リストのうち、連続する同一かつ互いに異なる追跡方向ベクトル及び前記抽出された他の閉図形と同配列のベクトルを削除することを特徴とする、第３態様の閉図形抽出装置を提供する。
【発明の効果】
【００１６】
本発明によれば、線図形を構成するベクトルを交点で分割し、分割された全てのベクトルを追跡開始ベクトルとして追跡を行い、追跡により得られた閉図形に共通するベクトルを統合して他の閉図形を構築することができるため、追跡において抽出できなかった閉図形を新たに抽出することができる。また、分割されたベクトルを含む閉図形には、ベクトルリストに含まれる接続関係に基づいて統合を行うため、線分の途中に接続点をなくすことができる。
【００１７】
また、本発明によれば、追跡処理として、右回りと左回りの双方を行うことにより、追跡処理での閉図形の抽出をより正確に行うことができる。
【００１８】
また、本発明の第３及び第４態様によれば、合成処理において共通するベクトルを除外し、合成処理において閉図形を容易に抽出することができる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の一実施形態に係る閉図形抽出装置について、図面を参照しながら説明する。
【００２０】
（装置の概略構成）
図１は、本発明の一実施形態にかかる閉図形抽出装置の概略構成を示すブロック図である。図１において、この閉図形抽出装置は、ＣＰＵ１，ＲＯＭ２，ＲＡＭ３，ベクトル演算用プロセッサ４，画像入力ポート５および端末制御部６を含むデータ処理ユニット１０と、原稿上の画像をラスタデータとして読み込むイメージスキャナ８と、画像処理の指示や処理結果の表示を行う端末機９とを備えている。
【００２１】
ＣＰＵ１は、システムバス７を介して、ＲＯＭ２およびＲＡＭ３とデータ伝送可能に接続されている。ＣＰＵ１は、ＲＯＭ２に格納されたプログラムに従ってデータ処理を行う。ＲＡＭ３は、ＣＰＵ１のデータ処理に必要なデータを適宜記憶する。さらに、ＣＰＵ１は、システムバス７を介して、ベクトル演算用プロセッサ４，画像入力ポート５および端末制御部６と接続されている。画像入力ポート５および端末制御部６には、それぞれ、イメージスキャナ８および端末機９が接続されている。
【００２２】
イメージスキャナ８は、セットされた原稿を光学的にスキャンし、白黒の２値情報として画像データ（ラスタデータ）を読み取るものである。ＣＰＵ１は、端末機９からの指示により、イメージスキャナ８が読み取ったラスタデータを画像入力ポート５に内蔵された画像バッファの所定の領域に展開する。端末機９は、こうした一連の画像処理の作業をデータ処理ユニット１０に指示するとともに、画像処理の過程や処理結果をその表示部に表示する。
【００２３】
データ処理ユニット１０に内蔵されたベクトル演算用プロセッサ４は、画像入力ポート５の画像バッファに展開されたラスタデータに対してベクトル演算を行って、原画像に対する線分のベクトルデータを抽出するプロセッサである。ベクトルデータとしては、始点の座標と方向と長さ、あるいは始点と終点の座標といった形式が考えられる。
【００２４】
次に、データ処理ユニット１０が実行する閉図形抽出処理について説明する。図２は、データ処理ユニットの機能ブロック図であり、図３は、データ処理ユニットが実行する処理のフローチャートである。
【００２５】
（線図形画像入力）
本実施形態の画像処理装置は、閉図形抽出処理を開始すると、まず画像の入力処理を行う（＃１）。入力処理は、例えば、イメージスキャナ８によって読み取られたラスタデータをデータ処理ユニット１０が画像入力ポート５の画像バッファに展開することにより行われる。なお、画像入力処理としては、イメージスキャナ８により読み取る他に、図示しない任意の画像作成装置によって作成された線図又はラスタデータとして認識されている情報を読み出すように構成してもよい。
【００２６】
（ベクトルデータ抽出処理）
次に、データ処理ユニット１０は、画像入力ポート５の画像バッファに展開されたラスタデータから線図形を構成する各線分のベクトルデータを抽出する処理を行う（＃２）。このベクトルデータの抽出は、ラスタデータに対してベクトル演算用プロセッサ４により行われ、ＲＡＭ３の所定の領域であるベクトルデータ記憶部１１に格納される。
【００２７】
図４は、画像の入力処理により入力された画像データをベクトルデータとして抽出した状態を示す例である。図４に示す例では、ベクトルデータはベクトルＶ１〜ベクトルＶ９までのベクトルの集合として認識されている。ベクトルデータの例を図５に示す。図５に示すように、ベクトルデータは、各ベクトルＶ１〜ベクトルＶ９の始点・終点の座標、有効フラグ、接続フラグなどの情報を有する。各ベクトルの始点・終点を示す方向性は任意に決定すればよく、例えば、右から左方向、上から下方向などというように必ずしも一義的に決定されていなくてもよい。有効フラグは、後述する閉図形抽出の追跡工程において、追跡の対象となるか否かをしめすフラグである。また、接続フラグは、あるベクトルが接続する他のベクトルを示すフラグである。
【００２８】
また、各ベクトルは、曲線で構成されていてもよい。図４では、例えば、ベクトルＶ２は曲線で構成されており、この場合は、始点・終点の端点の他、自由曲線の中間点の座標を任意に有する。
【００２９】
（交点抽出処理）
次に、データ処理ユニット１０は、交点抽出処理を行う（＃３）。交点抽出処理は、交点抽出手段１２が処理を司る。図６は、交点抽出処理のフローチャートである。図７は、交点抽出処理によって更新されたベクトルデータのデータ構造を示す図である。図８は、交点抽出処理後のベクトル及び交点の状態を示す図である。図９は、交点抽出処理によって抽出された交点リストのデータ構造を示す図である。交点抽出処理は、まず、ベクトルデータ記憶部１１に格納されているそれぞれのベクトルＶ１〜ベクトルＶ９について、それぞれに交点が存在しているかを確認する（＃３２）。ベクトルの交点が存在している場合は、対象ベクトルを当該交点で分割して新たなベクトルデータとし、ベクトルデータに登録する（＃３３）。分割された対象ベクトルは、有効フラグが無効に書き換えられ、接続フラグに分割の対象となった他のベクトルを登録する（＃３４）。また、存在が確認された交点については、交点リストに記録され（＃３５）、交点リスト記憶部１３に格納される。
【００３０】
図７及び図８を用いて交点抽出処理の具体的処理について説明する。以下では、対象ベクトルを、ベクトルＶ１からベクトルＶ９へと順次切り替えて交点抽出を行う場合を例にとって説明する。ベクトルＶ１を対象ベクトルとした場合、ベクトルＶ１については、図８に示すように他のベクトルＶ２及びベクトルＶ３と交差する点（交点Ｃ１，Ｃ２）が存在している。ここで、交点Ｃ１は、ベクトルＶ１と他のベクトルＶ３が交差する交点であり、交点Ｃ１を挟んで両側にベクトルＶ１を構成する一部の線分が存在する。一方、交点Ｃ２は、ベクトルＶ１の終点座標とベクトルＶ２の始点座標が一致しており、交点を挟んで一方側にのみベクトルＶ１を構成する線分が存在する。
【００３１】
ベクトルＶ１を対象ベクトルとした場合、抽出される交点はＣ１，Ｃ２であり、ベクトルＶ１を分割して新たに登録されたベクトルはベクトルＶ１０とベクトルＶ１１となる。ベクトルＶ１は分割されたため、図７に示すように無効のフラグが付される。また、新たに登録されたベクトルＶ１０，ベクトルＶ１１は、有効のフラグが立てられ接続フラグに互いのベクトルが付される。
【００３２】
ベクトルＶ１を対象とした場合に抽出された交点Ｃ１及びＣ２は、交点リストに登録される。交点リストに登録される交点は、ベクトルの始点又は終点の座標が交点座標と一致しているベクトルを接続ベクトルとして登録する。よって、たとえば、交点Ｃ１の接続ベクトルは、この段階では、ベクトルＶ１０及びベクトルＶ１１のみとなる。この段階で、ベクトルＶ１を対象ベクトルとする交点抽出処理は終了し、対象ベクトルをインクリメントしつつ、同様の処理が繰り返し行われる。
【００３３】
上記交点抽出処理において、ベクトルＶ３を対象とする場合、抽出された交点は、すでに登録された交点Ｃ１である。ベクトルＶ３は交点Ｃ１で分割され、新たにベクトルＶ１２，ベクトルＶ１３が登録される。また、交点Ｃ１の交点リストには、その交点を始点又は終点とするベクトルＶ１２，ベクトルＶ１３が接続ベクトルとして登録される。
【００３４】
ベクトルＶ６を対象ベクトルとする場合、ベクトルＶ６は、ベクトルＶ８とベクトルＶ９に交差することなく連結しているため、分割の処理が行われない。したがって、ベクトルＶ６は依然として有効であり、ベクトルデータの更新は行われない。また、交点Ｃ６及び交点Ｃ９では、接続ベクトルとしてＶ６が登録される。
【００３５】
以上の処理を全てのベクトルについて実行する。全てのベクトルについての処理が終了すると、延長処理（＃３８）を実行する。
【００３６】
延長処理（＃３８）は、延長処理手段１７によって実行され、ベクトルの両端から一定の距離だけ線分を延長する処理である。延長処理によって、わずかな隙間を空けて配置されている２つの線分を接続させ新たに交点を抽出することができる。
【００３７】
図１０は延長処理後のベクトル及び交点の状態を示す図である。図１１は、延長処理によって抽出された交点リストのデータ構造を示す図である。延長処理は、上記交点抽出において有効のフラグが付されているベクトルであって、交点リストの接続ベクトルとして登録されている数が１つ以下のベクトルが対象となる。図８の例では、ベクトルＶ１１，ベクトルＶ１２，ベクトルＶ１３，ベクトルＶ１５，ベクトルＶ１６，ベクトルＶ１７，ベクトルＶ１８，ベクトルＶ２０，ベクトルＶ２３，ベクトルＶ２４，ベクトルＶ２６，ベクトルＶ２７が対象となる。
【００３８】
これらの延長処理の対象となるベクトルについて、交点として登録されていない側の端点から所定量線分を延長する。延長量は任意に設定することができ、たとえば、ベクトルの長さに関係なく一定量を延長してもよいし、例えば、ベクトル長さの２０％を延長するというようにベクトルの長さに応じて設定してもよい。
【００３９】
延長する側の端点を中心として所定距離内に他のベクトルが存在する場合については、その交点を新たな交点として交点リストに追加する。図１０の例では、破線で示したベクトルＶ１１とベクトルＶ２０が延長されて新たな交点Ｃ１２が登録され、ベクトルＶ１８が延長されて新たな交点Ｃ１１が登録され、ベクトルＶ１２が延長されて新たな交点Ｃ１０が登録されている。
【００４０】
延長処理によって新たに登録された交点を規準として、ベクトルをさらに分割する。図１０の例では、ベクトルＶ１７は、新たに登録された交点Ｃ１０，交点Ｃ１１によってベクトルＶ３０，ベクトルＶ３１，ベクトルＶ３２に分割される。ベクトルの分割に伴い、ベクトルＶ１７は有効フラグが無効に更新され、図１１に示すように、交点リストの交点Ｃ１０，交点Ｃ１１，交点Ｃ１２が追加され、接続ベクトル番号が更新される。
【００４１】
延長処理が終了すると交点抽出処理（＃３）は終了し、閉図形抽出処理（＃４）が実行される。
【００４２】
（閉図形抽出処理）
図１２は閉図形抽出処理のサブフローチャートである。閉図形抽出処理（＃４）は、図１２に示す通り、右回り追跡処理（＃４１）、左回り追跡処理（＃４２）、共有ベクトル処理（＃４３）、ベクトル統合処理（＃４４）の４つのサブルーチンを備える。右回り追跡処理（＃４１）は、第１追跡手段１８が実行し左回り追跡処理（＃４２）は第２追跡手段１９が実行する。共有ベクトル処理（＃４３）は共有ベクトル処理手段２０が実行する。ベクトル統合処理（＃４４）はベクトル統合処理手段２１が実行する。
【００４３】
（右回り追跡処理）
図１６は、右回り追跡処理のサブフローチャートである。右回り追跡処理では、適当なベクトルから追跡をスタート（＃４１１）し、連続する要素を辿っていく。このとき、任意の追跡開始のベクトルごとに追跡リストを作成し、追跡したベクトルと追跡方向を記録しておく（＃４１２）。右回り追跡処理では、交点又は開放端において、追跡方向から見て最も右側に存在するベクトルを連続して追跡する。追跡は、追跡をスタートしたベクトルに対して追跡方向が同じとなった時点で終了する（＃４１３）。
【００４４】
図１３Ａは、ベクトルＶ１０をスタートとして右回り追跡を行う場合の処理を説明する図であり、図１３Ｂは、図１３Ａの追跡処理が行われる場合の追跡リストのデータ構成例を示す図である。図１３Ａに示すように、ベクトルＶ１０からベクトルの追跡が行われる場合、ベクトルＶ１０の追跡方向は、ベクトルの方向と逆向きであるため、図１３Ｂに示される追跡リストにベクトルＶ１０が逆向きに追跡されたことが記録される。交点Ｃ１では、ベクトルＶ１１，ベクトルＶ１２，ベクトルＶ１３が接続されているが、右回り追跡処理では、追跡方向から見て最も右側に存在するベクトル（ベクトルＶ１２）を選択して追跡する。同様に追跡を繰り返して追跡したベクトル及び交点を記録し、追跡をスタートしたベクトル（ベクトルＶ１０）に対して追跡方向が同じとなった時点で、当該追跡を終了する。
【００４５】
なお、本実施例では、追跡するベクトルについて、接続された他のベクトルが存在しなければ、現在追跡しているベクトルの端点から同じベクトルを逆向きに追跡する。具体的には、図１４Ａに示す、ベクトルＶ１１を追跡スタートのベクトルとして追跡を開始した場合、図１４Ｂに示すように、ベクトルＶ１１（逆），ベクトルＶ２０（逆），ベクトルＶ２２（順），ベクトルＶ２４（順）と追跡が進むが、ベクトルＶ２４（順）の終点では、交点が存在しないため、再度ベクトルＶ２４を逆向きに追跡する。また、ベクトルＶ２４（逆）を行い、交点Ｃ４では、ベクトルＶ２３（順）、ベクトルＶ２３（逆）、ベクトルＶ２５（逆）・・・と追跡が行われ、最後に、ベクトルＶ１１（逆）となった時点で当該追跡を終了する。
【００４６】
このときの追跡リストは、図１４Ｂに示す通りとなるが、右回り処理手段は、追跡リストの追跡結果であって、同じベクトルで追跡方向が互いに異なる追跡結果を有する連続するベクトルは端ベクトルと判断し、これを追跡結果から削除する処理を行う（＃４１４）。具体的には、図１４Ｂでは、Ｎｏ４，Ｎｏ５のベクトルＶ２４，Ｎｏ６，Ｎｏ７のベクトルＶ２３，Ｎｏ９，Ｎｏ１０のベクトルＶ２７は、それぞれ連続しかつ追跡方向が互いに異なるので、これらを端ベクトルとして追跡リストから削除する。図１４Ｃは、端ベクトル削除が行われた図１４Ｂの追跡リストの結果を示す図である。
【００４７】
なお、端ベクトルの削除は多段階で行われる。多段階に削除処理を行うことで、複数のベクトルによって１つの開放端を構成するような場合であっても、閉図形の抽出要素から除外することができる。たとえば、図４に示す本実施形態の例には含まれていないが、例えば、図１５Ａに示すように、３つのベクトルＶ５０、ベクトルＶ５１、ベクトルＶ５２で端ベクトルを構成しているような場合の追跡処理の例を説明する。
【００４８】
ベクトルＶ５０を追跡スタートとして追跡処理がスタートした場合、図１５Ｂに示すように、追跡結果は、ベクトルＶ５０（順），ベクトルＶ５１（順），ベクトルＶ５２（逆），ベクトルＶ５２（逆），ベクトルＶ５１（順），ベクトルＶ５０（逆）となり、スタートであるベクトルＶ５０（順）が追跡される時点で当該追跡処理が終了する。そして削除処理では、第１段階として、Ｎｏ３，Ｎｏ４のベクトルＶ５２及び、Ｎｏ６，Ｎｏ７のベクトルＶ５０が削除される。第１段階の削除の結果、次にＮｏ２，Ｎｏ５が隣り合う追跡結果となり、ベクトルが共通で追跡方向が反対であるため、ベクトル５１についても端ベクトルであると判断され、これが削除される。
【００４９】
なお、図１５Ａにおいて、追跡スタートのベクトルが例えばベクトルＶ５１であったとしても、図１５Ｃに示すように、削除処理を行えば、同じ結果となる。
【００５０】
次に、一図形内の複数閉図形の分割処理を行う。追跡リストの各ベクトルの端点で、重複の有無を検査し、重複があればその重複端点の前後で、追跡リストを分割する。この処理は、図１５Ｄのような一つの追跡リスト内に２つの閉図形Ｆ１，Ｆ２が存在するような場合に、それぞれの閉図形を検出するための処理である。具体的には、連続する交点（Ｃ３０，Ｃ３１）が２以上追跡リスト内に存在し、かつ当該交点に挟まれるベクトルＶ５０が正逆方向反対である場合に、複数の閉図形が連結している図形であると判断する。
【００５１】
なお、追跡リストを分割と端ベクトルの削除の順序はどちらを先にしてもよい。例えば、追跡リストの分割を行って、複数の閉図形を検出した後、それぞれの追跡リストにおいて上記の端ベクトルの削除に関する処理を行い、端ベクトルがあればそれを削除するようにしてもよい。
【００５２】
削除処理（＃４１４）を行った結果、追跡リストを構成するベクトルが２以下の場合は、当該追跡リストを削除する（＃４１７）。一方、追跡リストを構成するベクトルが２以上である場合は、閉図形であると判断し、閉図形リストに当該追跡リストを登録する（＃４１６）。閉図形リストは、ＲＯＭ２又はＲＡＭ３の一部領域で構成される閉図形リスト記憶部１４に格納される。
【００５３】
なお、このとき、閉図形リストに格納される追跡結果は、同じ閉図形が多数回認識される。例えば、ベクトルＶ１０をスタートベクトルとして抽出される閉図形と、ベクトルＶ１２，ベクトルＶ１４，ベクトルＶ３０をスタートベクトルとした場合に抽出されるそれぞれの閉図形は同じ閉図形であり、構成ベクトルを全て共通にする図形である。このような構成ベクトルを全て共通する閉図形は、２回目以降閉図形リストに登録しない。以上の処理を繰り返し行い、全てのベクトルを追跡スタートベクトルとした場合について追跡を行い、全てのベクトルについての追跡が終了すると右回り追跡処理を終了する。
【００５４】
（左回り追跡処理）
右回り追跡処理が終了すると、左回り追跡処理が実行される。左回り追跡処理は右回り追跡処理とほぼ同じ処理が行われ、適当なベクトルから追跡をスタートし、連続する要素を辿っていく。左回り追跡処理では、交点又は開放端において、追跡方向から見て最も左側に存在するベクトルを連続して追跡する点において、右回り追跡処理と異なる。
【００５５】
右回り追跡処理に加えて左回り追跡処理を行うことで、右回り追跡処理では抽出できなかった新たな閉図形を抽出することができる。図１７に示す例に基づいて、ベクトルＶ１０をスタートベクトルとして左回り追跡処理を行う場合を説明する。図１７に示すように、ベクトルＶ１０からベクトルの追跡が行われる場合、ベクトルＶ１０の追跡方向は、ベクトルの方向と逆向きであるため、追跡リストにベクトルＶ１０が逆向きに追跡されたことが記録される。交点Ｃ１では、ベクトルＶ１１，ベクトルＶ１２，ベクトルＶ１３が接続されているが、左回り追跡処理では、追跡方向から見て最も左側に存在するベクトルＶ１３を選択して追跡する。ベクトルＶ１３の終端は開放端であるため、追跡はベクトルＶ１３を逆向きに追跡し、次にベクトルＶ１１（逆）を追跡する。同様に追跡をベクトルＶ２０（逆），ベクトルＶ２１（順），ベクトルＶ６（順），ベクトルＶ２９（順），ベクトルＶ１８（逆），ベクトルＶ３２（逆），ベクトルＶ３２（順），ベクトルＶ３１（順），ベクトルＶ３０（順），ベクトルＶ１５（順），ベクトルＶ１５（逆），ベクトルＶ１６（順），ベクトルＶ１６（逆），ベクトルＶ１４（逆）と繰り返し、追跡をスタートしたベクトルＶ１０（逆）に対して追跡方向が同じとなった時点で、当該追跡を終了する。
【００５６】
端ベクトルの削除処理を行い、ベクトルＶ１３，ベクトルＶ３２を削除し、残ったベクトル（ベクトルＶ１０，ベクトルＶ１１，ベクトルＶ２０，ベクトルＶ２１，ベクトルＶ６，ベクトルＶ２９，ベクトルＶ１８，ベクトルＶ３１，ベクトルＶ３０，ベクトルＶ１４）を構成要素として閉図形が抽出される。
【００５７】
図１８は、閉図形リストのデータ構成例である。閉図形リストは、構成ベクトル列として登録される。
【００５８】
図１９は、図４のベクトルデータにもとづいて、右回り追跡処理と左回り追跡処理が終了した結果、抽出される閉図形の例を示す図である。右回り追跡処理と左回り追跡処理が終了した時点で、図１９に示すＡ〜Ｅまでの５つの閉図形が抽出されている。これらの抽出された閉図形を用いて新しい閉図形を構築する共有ベクトル処理を行う（＃４３）。
【００５９】
（共有ベクトル処理）
共有ベクトル処理は、それぞれの閉図形の共有する辺（ベクトル）に注目し、辺を共有するベクトルを除いて新たな閉図形を構築する処理である。以下、図を用いながら具体的に説明する。
【００６０】
共有ベクトル処理では、まず閉図形リストに格納されている全図形のうち全ての組み合わせについて下記の処理を行う。
【００６１】
図２０は共有ベクトル処理のサブフローチャートである。対象となる選択された２つの閉図形を構成するベクトルとして、双方に共通するベクトルを有しているか否かを判断する（＃４３０）。共有するベクトルが存在しない場合は、当該組み合わせについての共有ベクトル処理を行わない。
【００６２】
共有するベクトルが存在している場合は、当該共有ベクトルに着目し、閉図形リストに格納されている構成ベクトルの順逆が異なるように反転処理を行う。例えば、図２１Ａに示すように閉図形Ａと閉図形Ｂが選択された場合、共にベクトルＶ１２を共通にする。反転処理では、まず、閉図形Ａと閉図形Ｂの共有ベクトルに着目し、それぞれの閉図形において、共通するベクトルを、閉図形リストの最終ベクトルと先頭ベクトルに移動させる配置変換を行う（＃４３１）。
【００６３】
配置変換が行われたそれぞれの閉図形について、共有ベクトルの追跡方向が同じか異なるかを判断し（＃４３２）、追跡方向が同じである場合は、いずれか一方の閉図形について、全ての構成ベクトルの追跡方向を反転させる（＃４３２）。図２１Ｂは、反転処理が終了した閉図形Ａの閉図形リストであり、図２１Ｃは、反転処理が終了した閉図形Ｂの閉図形リストである。
【００６４】
次いで、２つの閉図形リストの共有ベクトルが連続するように、２つの図形リストを合成し（＃４３４）、新たな閉図形リストＦを作成する。図２２Ａに合成処理によって新たに作成された閉図形リストの例を示す。合成処理によって新たに作成された閉図形リストについて、削除処理を行う（＃４３５）。共有ベクトル処理における削除処理は、右回り追跡処理及び左回り追跡処理における削除処理において削除の対象となった連続配置されかつ追跡方向が互いに異なるベクトルに加え、すでに既登録の閉図形リストを構成するベクトルの配列が共通する場合はこれも削除する。
【００６５】
図２２Ａの例では、新たに合成された閉図形リストＦは、ベクトルＶ１２が連続配置されかつ追跡方向が互いに異なるため、これを削除する。削除後の閉図形リストは図２２Ｂのように構成される。
【００６６】
図２２Ｃに閉図形Ａと閉図形Ｂとの共有ベクトル処理で新たに構築された閉図形の構成を示す。閉図形Ａと閉図形Ｂとの共有ベクトル処理で新たに構築された閉図形Ｆは、図示のような多数のベクトルで構成される。また、反転処理を行うことによって接続ベクトルの追跡方向を同方向にすることができる。例えば、ベクトルＶ１０とベクトルＶ１１とでは、共に逆向きとなるように構成されており、ベクトルの接続の処理をスムーズに行うことができる。
【００６７】
なお、共有ベクトル処理において対象となる２つの閉図形が、共有するベクトルを２以上有しているときは、いずれか１つのベクトルに注目して上記配置変換、反転、合成の各処理を行い、合成リストについて削除処理を行う。
【００６８】
例えば、図２３Ａに示すように閉図形Ｂと閉図形Ｅの共有ベクトル処理では、図２３Ｂにおいて破線で示すベクトルＶ１１，ベクトルＶ１８，ベクトルＶ２０，ベクトルＶ３１が共有する。この場合、いずれか１つのベクトル（例えば、ベクトルＶ３１）を共有ベクトルとして上記処理（＃４３１〜＃４３５）を行う。
【００６９】
以下、閉図形リストを示して具体的に説明する。図２４は、閉図形Ｅと閉図形Ｂの閉図形リストである。図２４においては、すでに配置変換（＃４３１）及び反転処理（＃４３３）は終了している状態を示している。図２４では、ベクトルＶ３１を共有ベクトルとし２つの閉図形リストをベクトル合成する（＃４３４）。ベクトル合成された２つのリストは、次の通り削除処理（＃４３５）がなされる。まず、ベクトルＶ３１は、連続しかつ追跡方向が互いに異なるので、削除処理される。ベクトルＶ３１が削除されると、ベクトルＶ１８が連続しかつ追跡方向が互いに異なるのでベクトル１８を削除する。
【００７０】
次に、残った閉図形追跡リストの内で、複数閉図形の分割処理と同様の処理を行い、ベクトル端点で重複する交点（ここではＣ１・Ｃ５・Ｃ１２）に注目し、そのいずれかで、追跡リストを分割する。
【００７１】
ここで交点Ｃ１で分割したとすると、既登録の閉図形の構成ベクトルの削除後残った閉図形リストの内で、連続しかつ追跡方向が逆のベクトルを削除する。具体的には、ベクトルＶ１１は、リストの先頭と最後に位置し、連続しておりかつ追跡方向が逆であるので、これを削除する。また、ベクトルＶ１１を削除すると、ベクトルＶ２０が連続かつ追跡方向が逆となるのでこれを削除する。以上のベクトルの削除が終了すると、図２５に示す新たな閉図形リストが残ることとなる。生成された閉図形リストで、ベクトルＶ１２・ベクトルＶ３０・ベクトルＶ１４・ベクトルＶ１０の組み合わせは、閉図形Ａと共通するため、この組み合わせを削除する。
【００７２】
このように削除処理がなされた後の閉図形リストが既存の閉図形リストに登録されている閉図形であるかを確認し（＃４３７）、共通でない場合は、新たな閉図形として登録する（＃４３８）。
【００７３】
以上の処理について、全ての閉図形の組み合わせについて共有ベクトル処理が終了すると、全ての可能性のある閉図形が抽出される。具体的には、図２２Ｃに示した閉図形Ｆ（閉図形Ａと閉図形Ｂの組み合わせ）、や閉図形Ｇ（閉図形Ｅと閉図形Ｂの組み合わせ）、さらには、閉図形Ｂと閉図形Ｃの組み合わせが抽出される。
【００７４】
なお、たとえば、閉図形Ｇは閉図形Ｃと閉図形Ｄの組み合わせでも抽出可能であるが、上記のように既存の閉図形リストには重複して登録されないため、いずれかの組み合わせの共有ベクトル処理においてのみ登録されることとなる。
【００７５】
さらに、共有ベクトル処理は、共有ベクトル処理によって新たに追加された閉図形についての組み合わせも処理を行う。例えば、閉図形Ｂと閉図形Ｇ（閉図形Ｃと閉図形Ｄとを組み合わせ図形）の供給ベクトル処理も行われ、新たな閉図形を抽出することができる。
【００７６】
（ベクトル統合処理）
以上、共有ベクトル処理が終了し、閉図形が抽出された後、それぞれの閉図形リストにおいて、閉図形を構成するベクトルの接続フラグを確認し、接続フラグが互いに付されており、かつ追跡方向が共通のベクトルを統合処理し、新たなベクトルとしてベクトルデータに追加する。
【００７７】
図２６は、閉図形Ｅを構成する閉図形リストを構成するベクトルを示す図である。閉図形Ｅは、ベクトルＶ１０とベクトルＶ１１及びベクトルＶ３０とベクトルＶ３１が互いに接続フラグで付されており、かつ追跡方向が共通する。ベクトル統合処理では、これらを統合し、新たにベクトルＶ３３とベクトルＶ３４を作成するとともに、閉図形リストに構成されるベクトルを新たに統合されたベクトルに置き換える。
【００７８】
なお、ベクトル統合処理で新たに作成されたベクトルは、当該対象となる閉図形においてのみ用いられるものである。たとえば、閉図形Ｂにおいては、依然としてベクトルＶ１１もベクトルＶ３１も有効に存在している。よって、閉図形Ｂと閉図形Ｅでは、共通する線分を有しているが、これら共通する線分を構成するベクトルは異なるベクトルとして認識される。
【００７９】
ベクトル統合処理により、１つの線分中に存在する接続点を削除することができ、閉図形を相似形に拡大縮小する場合などに変形などの影響が及ぶことがない。
【００８０】
以上説明したように、本実施形態にかかる閉図形抽出装置によれば、線図形を構成するベクトルを交点で分割し、分割された全てのベクトルを追跡スタートベクトルとして、回転方向が異なる複数回の追跡を行い、追跡により得られた閉図形に共通するベクトルを統合して他の閉図形を構築することができる。これにより、ほぼ漏れなく閉図形の抽出を行うことができる。また、閉図形の抽出のために分割したベクトルは、分割された接続するベクトルの情報を格納しておくことにより、閉図形を構成するベクトルの統合が容易であり、１つの線分中に存在する接続点を除去することができる。
【００８１】
よって、正確に抽出された閉図形の相似形に拡大・縮小を行う場合に変形などの問題を起こすことがなく、例えば、服飾用の型紙の作成などにおいて好適に用いることができる。
【００８２】
なお、本発明は上記実施形態に限定されるものではなく、その他種々の態様で実施可能である。
【図面の簡単な説明】
【００８３】
【図１】本発明の一実施形態にかかる閉図形抽出装置の概略構成を示すブロック図である。
【図２】データ処理ユニットの機能ブロック図である。
【図３】データ処理ユニットが実行する処理のフローチャートである。
【図４】画像の入力処理により入力された画像データをベクトルデータとして抽出した状態を示す例である。
【図５】ベクトルデータ記憶部に格納されているベクトルデータのデータ構成例である。
【図６】交点抽出処理のフローチャートである。
【図７】交点抽出処理によって更新されたベクトルデータのデータ構造を示す図である。
【図８】交点抽出処理後のベクトル及び交点の状態を示す図である。
【図９】交点抽出処理によって抽出された交点リストのデータ構造を示す図である。
【図１０】延長処理後のベクトル及び交点の状態を示す図である。
【図１１】延長処理によって抽出された交点リストのデータ構造を示す図である。
【図１２】閉図形抽出処理のサブフローチャートである。
【図１３Ａ】ベクトルＶ１０をスタートとして右回り追跡を行う場合の処理を説明する図である。
【図１３Ｂ】図１３Ａの追跡処理が行われる場合の追跡リストのデータ構成例を示す図である。
【図１４Ａ】追跡しているベクトルの端点から同じベクトルを逆向きに追跡する追跡例を示す図である。
【図１４Ｂ】図１４Ａの追跡リストの構成を示す図である。
【図１４Ｃ】削除処理を行った後の図１４Ｂの追跡リストの構成を示す図である。
【図１５Ａ】複数のベクトルによって１つの開放端を構成するような場合のベクトル追跡の状態を説明する図である。
【図１５Ｂ】図１５Ａの線図形においてベクトルＶ５０を追跡スタートとして追跡処理がスタートした場合の追跡リストを示す図である。
【図１５Ｃ】図１５Ａの線図形においてベクトルＶ５１を追跡スタートとして追跡処理がスタートした場合の追跡リストを示す図である。
【図１５Ｄ】一追跡リスト中に複数の閉図形が存在している場合の分割処理を説明する図である。
【図１６】右回り追跡処理のサブフローチャートである。
【図１７】ベクトルＶ１０をスタートベクトルとして行われる左回り追跡処理を説明する図である。
【図１８】閉図形リストのデータ構成例である。
【図１９】図４のベクトルデータにもとづいて、右回り追跡処理と左回り追跡処理が終了した結果、抽出される閉図形の例を示す図である。
【図２０】共有ベクトル処理のサブフローチャートである。
【図２１Ａ】閉図形Ａと閉図形Ｂが選択された場合の共有ベクトル処理の説明図である。
【図２１Ｂ】反転処理が終了した閉図形Ａの閉図形リストである。
【図２１Ｃ】反転処理が終了した閉図形Ｂの閉図形リストである。
【図２２Ａ】合成処理によって新たに作成された閉図形リストの例を示す図である。
【図２２Ｂ】削除処理後の図２２Ａの閉図形リストの例を示す図である。
【図２２Ｃ】閉図形Ａと閉図形Ｂとの共有ベクトル処理で新たに構築された閉図形の構成図である。
【図２３Ａ】閉図形Ｂと閉図形Ｅが選択された場合の共有ベクトル処理の説明図である。
【図２３Ｂ】２３Ａの共有ベクトル処理において共有するベクトルを示す図である。
【図２４】閉図形Ｅと閉図形Ｂの閉図形リストである。
【図２５】閉図形Ｂと閉図形Ｅの共有ベクトル処理において新たに作成された閉図形リストの構成を示す図である。
【図２６】閉図形Ｅを構成する閉図形リストを構成するベクトルを示す図である。
【図２７】従来の閉図形抽出装置で抽出不可能な閉図形の例を示す図である。
【図２８】従来の閉図形抽出装置で抽出不可能な閉図形の例を示す図である。
【符号の説明】
【００８４】
１ ＣＰＵ
２ ＲＯＭ
３ ＲＡＭ
４ ベクトル演算用プロセッサ
５ 画像入力ポート
６ 端末制御部
７ システムバス
８ イメージスキャナ
９ 端末機
１０ データ処理ユニット
１１ ベクトルデータ記憶部
１２ 交点抽出手段
１３ 交点リスト記憶部
１４ 閉図形リスト記憶部
１５ 閉図形抽出手段
１６ 交点検出手段
１７ 延長処理手段
１８ 第１追跡手段
１９ 第２追跡手段
２０ 共有ベクトル処理手段
２１ ベクトル統合手段
【技術分野】
【０００１】
本発明は、閉図形抽出装置に関し、より具体的には、複数の線によって構成される線図形の中から、空間的に閉塞した領域として閉図形を抽出する閉図形抽出装置に関する。
【背景技術】
【０００２】
従来、パーソナルコンピュータやＣＡＤ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ）装置等の図形処理装置によって、地図、回路パターン図、設計図等の線図形を処理する場合、しばしば当該線図形の中から空間的に閉塞した領域としての閉図形を抽出することが要求される。
【０００３】
従来、線図形から閉図形を抽出する技術の一例として、特開平３−１７１３７８号公報（特許文献１）に開示された「閉領域自動認識装置」がある。また、線図形から閉図形を抽出する他の従来技術として、特開平２−２４５９８７号公報（特許文献２）に開示された「線図形認識装置の閉ループ抽出方法」がある。
【０００４】
しかし、上記特許文献１の技術では、線図形の中に、一方の閉図形がその内部に他方の閉図形を包含し、かつ他方の閉図形が一方の閉図形と１点で接しているような閉図形群が存在している場合、閉図形を正しく抽出できないという問題点があった。
【０００５】
さらに、上記特許文献２の技術は、アークの追跡時に、追跡中ノードに接続するアークのすべてについて、その反対側ノード（追跡中ノードと反対側のノード）の接続状況を調べるという複雑な条件判断を行っているため、追跡に時間がかかるという問題点を有していた。
【０００６】
かかる問題を解消すべく、特開平６−１１９４４６号公報（特許文献３）に開示の「閉図形抽出装置」が公知となっている。追跡中のアークが閉図形以外の図形部分に到達しても、再び追跡開始アークの追跡開始方向に戻るまでアークの追跡が中断することなく続行されるため、閉図形以外の図形部分に分岐点ノードが存在する場合であっても、アークの追跡が途中で中断することがなくなり、閉図形を正しく抽出できる。
【特許文献１】特開平３−１７１３７８号公報
【特許文献２】特開平２−２４５９８７号公報
【特許文献３】特開平６−１１９４４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、特許文献３にかかる閉図形抽出装置は、例えば、図２７に示すような、Ｖ１０１〜Ｖ１０４で構成された１つの閉図形を貫通する線分Ｖ１０５が存在する場合、当該成分で区画された２つの閉図形Ｌ１０１，Ｌ１０３としての抽出が可能であるが、Ｖ１０５〜Ｖ１０８で構成された１つの閉図形（すなわちＬ１０２＋Ｌ１０３の閉図形）を抽出することは不可能であった。
【０００８】
すなわち、特許文献３にかかる閉図形抽出装置は、追跡中ノードに接続する３以上のアークが存在する場合、現在追跡中のアークを除き、当該アークから見て最も右側（左側でも同様である）に折れるアークを次の追跡中アークとすることから、Ｖ１０５の追跡過程において、ノードＣ１０１でＶ１０５を直進して追跡することができない。よって、Ｖ１０５の全線分を構成要素とする閉図形Ｌ１０３の抽出を行うことができないという問題があった。
【０００９】
さらに、特許文献３にかかる閉図形抽出装置は、１つの閉図形がその一部に他方の閉図形を包含し、かつ他方の閉図形が一方の閉図形と一点で接しているような閉図形群が存在している場合（図２８）、他方の閉図形と一点で接している１の閉図形の当該接点Ｓを新たなノード（接続点）として判断することとなる。そして、このように１つの閉図形の１つの線分の途中にノード（接続点）が認識されると、当該閉図形において各ノード毎に変形式を持つような特殊な拡大縮小変形処理を行う場合に、自動追加されたノードには適切な変形式が未設定であることから、意図した変形結果を得ることが困難となる。例えば、閉図形抽出装置が服飾型作成の編集作業装置に組み込まれて使用される場合、規準サイズからのサイズアップ及びサイズダウンの処理に問題となる。
【００１０】
したがって、本発明が解決しようとする技術的課題は、上記問題を解消し、１つの閉図形を貫通する線分が存在する場合などの図形を含む任意の線図形に対して正確に抽出可能で、不要な接続点の認識を排除することができる閉図形抽出装置を提供することである。
【課題を解決するための手段】
【００１１】
本発明は、上記技術的課題を解決するために、以下の構成の閉図形抽出装置を提供する。
【００１２】
本発明の第１態様によれば、複数のベクトルによって構成される線図形の中から、空間的に閉塞した領域としての閉図形を抽出する閉図形抽出装置であって、
前記線図形を構成する各ベクトルを格納するベクトルリストと、
前記ベクトルリストに格納されているベクトルについて、他のベクトルとの交点を抽出し、前記交点が存在する場合は当該ベクトルを分割して作成された新たなベクトルを互いの接続関係を対応づけて前記ベクトルリストに登録する、交点抽出手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして、追跡方向を記録しながら連続的に追跡して追跡リストを作成し、追跡リストに含まれる連続するベクトルが同一で互いに異なる追跡方向を有している場合は当該ベクトルを除外しつつ閉図形を抽出する追跡手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして
前記追跡手段で抽出された閉図形のうち、任意の２つの閉図形を構成する追跡リストに共通する任意の一つのベクトルが、連続かつ互いに異なる追跡方向を有するように前記追跡リストを再配置して、当該２つの追跡リストを合成する共有ベクトル合成手段と、
前記抽出図形を構成するベクトルが、交点抽出手段により分割されたベクトルを含む場合、前記ベクトルリストの接続関係に基づいて、統合したベクトルに置き換える、ベクトル統合手段とを備えることを特徴とする、閉図形抽出装置を提供する。
【００１３】
本発明の第２態様によれば、前記追跡手段は、
右回りに追跡処理して追跡リストを作成する第１追跡手段と、
左回りに追跡処理して追跡リストを作成する第２追跡手段とを備える、ことを特徴とする、第１態様の閉図形抽出装置を提供する。
【００１４】
本発明の第３態様によれば、前記共有ベクトル合成手段は、前記追跡リスト変換手段により変換された前記共通ベクトルが連続するように前記追跡リストを合成することを特徴とする、第１又は第２態様の閉図形抽出装置を提供する。
【００１５】
本発明の第４態様によれば、前記共有ベクトル合成手段は、合成された追跡リストのうち、連続する同一かつ互いに異なる追跡方向ベクトル及び前記抽出された他の閉図形と同配列のベクトルを削除することを特徴とする、第３態様の閉図形抽出装置を提供する。
【発明の効果】
【００１６】
本発明によれば、線図形を構成するベクトルを交点で分割し、分割された全てのベクトルを追跡開始ベクトルとして追跡を行い、追跡により得られた閉図形に共通するベクトルを統合して他の閉図形を構築することができるため、追跡において抽出できなかった閉図形を新たに抽出することができる。また、分割されたベクトルを含む閉図形には、ベクトルリストに含まれる接続関係に基づいて統合を行うため、線分の途中に接続点をなくすことができる。
【００１７】
また、本発明によれば、追跡処理として、右回りと左回りの双方を行うことにより、追跡処理での閉図形の抽出をより正確に行うことができる。
【００１８】
また、本発明の第３及び第４態様によれば、合成処理において共通するベクトルを除外し、合成処理において閉図形を容易に抽出することができる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の一実施形態に係る閉図形抽出装置について、図面を参照しながら説明する。
【００２０】
（装置の概略構成）
図１は、本発明の一実施形態にかかる閉図形抽出装置の概略構成を示すブロック図である。図１において、この閉図形抽出装置は、ＣＰＵ１，ＲＯＭ２，ＲＡＭ３，ベクトル演算用プロセッサ４，画像入力ポート５および端末制御部６を含むデータ処理ユニット１０と、原稿上の画像をラスタデータとして読み込むイメージスキャナ８と、画像処理の指示や処理結果の表示を行う端末機９とを備えている。
【００２１】
ＣＰＵ１は、システムバス７を介して、ＲＯＭ２およびＲＡＭ３とデータ伝送可能に接続されている。ＣＰＵ１は、ＲＯＭ２に格納されたプログラムに従ってデータ処理を行う。ＲＡＭ３は、ＣＰＵ１のデータ処理に必要なデータを適宜記憶する。さらに、ＣＰＵ１は、システムバス７を介して、ベクトル演算用プロセッサ４，画像入力ポート５および端末制御部６と接続されている。画像入力ポート５および端末制御部６には、それぞれ、イメージスキャナ８および端末機９が接続されている。
【００２２】
イメージスキャナ８は、セットされた原稿を光学的にスキャンし、白黒の２値情報として画像データ（ラスタデータ）を読み取るものである。ＣＰＵ１は、端末機９からの指示により、イメージスキャナ８が読み取ったラスタデータを画像入力ポート５に内蔵された画像バッファの所定の領域に展開する。端末機９は、こうした一連の画像処理の作業をデータ処理ユニット１０に指示するとともに、画像処理の過程や処理結果をその表示部に表示する。
【００２３】
データ処理ユニット１０に内蔵されたベクトル演算用プロセッサ４は、画像入力ポート５の画像バッファに展開されたラスタデータに対してベクトル演算を行って、原画像に対する線分のベクトルデータを抽出するプロセッサである。ベクトルデータとしては、始点の座標と方向と長さ、あるいは始点と終点の座標といった形式が考えられる。
【００２４】
次に、データ処理ユニット１０が実行する閉図形抽出処理について説明する。図２は、データ処理ユニットの機能ブロック図であり、図３は、データ処理ユニットが実行する処理のフローチャートである。
【００２５】
（線図形画像入力）
本実施形態の画像処理装置は、閉図形抽出処理を開始すると、まず画像の入力処理を行う（＃１）。入力処理は、例えば、イメージスキャナ８によって読み取られたラスタデータをデータ処理ユニット１０が画像入力ポート５の画像バッファに展開することにより行われる。なお、画像入力処理としては、イメージスキャナ８により読み取る他に、図示しない任意の画像作成装置によって作成された線図又はラスタデータとして認識されている情報を読み出すように構成してもよい。
【００２６】
（ベクトルデータ抽出処理）
次に、データ処理ユニット１０は、画像入力ポート５の画像バッファに展開されたラスタデータから線図形を構成する各線分のベクトルデータを抽出する処理を行う（＃２）。このベクトルデータの抽出は、ラスタデータに対してベクトル演算用プロセッサ４により行われ、ＲＡＭ３の所定の領域であるベクトルデータ記憶部１１に格納される。
【００２７】
図４は、画像の入力処理により入力された画像データをベクトルデータとして抽出した状態を示す例である。図４に示す例では、ベクトルデータはベクトルＶ１〜ベクトルＶ９までのベクトルの集合として認識されている。ベクトルデータの例を図５に示す。図５に示すように、ベクトルデータは、各ベクトルＶ１〜ベクトルＶ９の始点・終点の座標、有効フラグ、接続フラグなどの情報を有する。各ベクトルの始点・終点を示す方向性は任意に決定すればよく、例えば、右から左方向、上から下方向などというように必ずしも一義的に決定されていなくてもよい。有効フラグは、後述する閉図形抽出の追跡工程において、追跡の対象となるか否かをしめすフラグである。また、接続フラグは、あるベクトルが接続する他のベクトルを示すフラグである。
【００２８】
また、各ベクトルは、曲線で構成されていてもよい。図４では、例えば、ベクトルＶ２は曲線で構成されており、この場合は、始点・終点の端点の他、自由曲線の中間点の座標を任意に有する。
【００２９】
（交点抽出処理）
次に、データ処理ユニット１０は、交点抽出処理を行う（＃３）。交点抽出処理は、交点抽出手段１２が処理を司る。図６は、交点抽出処理のフローチャートである。図７は、交点抽出処理によって更新されたベクトルデータのデータ構造を示す図である。図８は、交点抽出処理後のベクトル及び交点の状態を示す図である。図９は、交点抽出処理によって抽出された交点リストのデータ構造を示す図である。交点抽出処理は、まず、ベクトルデータ記憶部１１に格納されているそれぞれのベクトルＶ１〜ベクトルＶ９について、それぞれに交点が存在しているかを確認する（＃３２）。ベクトルの交点が存在している場合は、対象ベクトルを当該交点で分割して新たなベクトルデータとし、ベクトルデータに登録する（＃３３）。分割された対象ベクトルは、有効フラグが無効に書き換えられ、接続フラグに分割の対象となった他のベクトルを登録する（＃３４）。また、存在が確認された交点については、交点リストに記録され（＃３５）、交点リスト記憶部１３に格納される。
【００３０】
図７及び図８を用いて交点抽出処理の具体的処理について説明する。以下では、対象ベクトルを、ベクトルＶ１からベクトルＶ９へと順次切り替えて交点抽出を行う場合を例にとって説明する。ベクトルＶ１を対象ベクトルとした場合、ベクトルＶ１については、図８に示すように他のベクトルＶ２及びベクトルＶ３と交差する点（交点Ｃ１，Ｃ２）が存在している。ここで、交点Ｃ１は、ベクトルＶ１と他のベクトルＶ３が交差する交点であり、交点Ｃ１を挟んで両側にベクトルＶ１を構成する一部の線分が存在する。一方、交点Ｃ２は、ベクトルＶ１の終点座標とベクトルＶ２の始点座標が一致しており、交点を挟んで一方側にのみベクトルＶ１を構成する線分が存在する。
【００３１】
ベクトルＶ１を対象ベクトルとした場合、抽出される交点はＣ１，Ｃ２であり、ベクトルＶ１を分割して新たに登録されたベクトルはベクトルＶ１０とベクトルＶ１１となる。ベクトルＶ１は分割されたため、図７に示すように無効のフラグが付される。また、新たに登録されたベクトルＶ１０，ベクトルＶ１１は、有効のフラグが立てられ接続フラグに互いのベクトルが付される。
【００３２】
ベクトルＶ１を対象とした場合に抽出された交点Ｃ１及びＣ２は、交点リストに登録される。交点リストに登録される交点は、ベクトルの始点又は終点の座標が交点座標と一致しているベクトルを接続ベクトルとして登録する。よって、たとえば、交点Ｃ１の接続ベクトルは、この段階では、ベクトルＶ１０及びベクトルＶ１１のみとなる。この段階で、ベクトルＶ１を対象ベクトルとする交点抽出処理は終了し、対象ベクトルをインクリメントしつつ、同様の処理が繰り返し行われる。
【００３３】
上記交点抽出処理において、ベクトルＶ３を対象とする場合、抽出された交点は、すでに登録された交点Ｃ１である。ベクトルＶ３は交点Ｃ１で分割され、新たにベクトルＶ１２，ベクトルＶ１３が登録される。また、交点Ｃ１の交点リストには、その交点を始点又は終点とするベクトルＶ１２，ベクトルＶ１３が接続ベクトルとして登録される。
【００３４】
ベクトルＶ６を対象ベクトルとする場合、ベクトルＶ６は、ベクトルＶ８とベクトルＶ９に交差することなく連結しているため、分割の処理が行われない。したがって、ベクトルＶ６は依然として有効であり、ベクトルデータの更新は行われない。また、交点Ｃ６及び交点Ｃ９では、接続ベクトルとしてＶ６が登録される。
【００３５】
以上の処理を全てのベクトルについて実行する。全てのベクトルについての処理が終了すると、延長処理（＃３８）を実行する。
【００３６】
延長処理（＃３８）は、延長処理手段１７によって実行され、ベクトルの両端から一定の距離だけ線分を延長する処理である。延長処理によって、わずかな隙間を空けて配置されている２つの線分を接続させ新たに交点を抽出することができる。
【００３７】
図１０は延長処理後のベクトル及び交点の状態を示す図である。図１１は、延長処理によって抽出された交点リストのデータ構造を示す図である。延長処理は、上記交点抽出において有効のフラグが付されているベクトルであって、交点リストの接続ベクトルとして登録されている数が１つ以下のベクトルが対象となる。図８の例では、ベクトルＶ１１，ベクトルＶ１２，ベクトルＶ１３，ベクトルＶ１５，ベクトルＶ１６，ベクトルＶ１７，ベクトルＶ１８，ベクトルＶ２０，ベクトルＶ２３，ベクトルＶ２４，ベクトルＶ２６，ベクトルＶ２７が対象となる。
【００３８】
これらの延長処理の対象となるベクトルについて、交点として登録されていない側の端点から所定量線分を延長する。延長量は任意に設定することができ、たとえば、ベクトルの長さに関係なく一定量を延長してもよいし、例えば、ベクトル長さの２０％を延長するというようにベクトルの長さに応じて設定してもよい。
【００３９】
延長する側の端点を中心として所定距離内に他のベクトルが存在する場合については、その交点を新たな交点として交点リストに追加する。図１０の例では、破線で示したベクトルＶ１１とベクトルＶ２０が延長されて新たな交点Ｃ１２が登録され、ベクトルＶ１８が延長されて新たな交点Ｃ１１が登録され、ベクトルＶ１２が延長されて新たな交点Ｃ１０が登録されている。
【００４０】
延長処理によって新たに登録された交点を規準として、ベクトルをさらに分割する。図１０の例では、ベクトルＶ１７は、新たに登録された交点Ｃ１０，交点Ｃ１１によってベクトルＶ３０，ベクトルＶ３１，ベクトルＶ３２に分割される。ベクトルの分割に伴い、ベクトルＶ１７は有効フラグが無効に更新され、図１１に示すように、交点リストの交点Ｃ１０，交点Ｃ１１，交点Ｃ１２が追加され、接続ベクトル番号が更新される。
【００４１】
延長処理が終了すると交点抽出処理（＃３）は終了し、閉図形抽出処理（＃４）が実行される。
【００４２】
（閉図形抽出処理）
図１２は閉図形抽出処理のサブフローチャートである。閉図形抽出処理（＃４）は、図１２に示す通り、右回り追跡処理（＃４１）、左回り追跡処理（＃４２）、共有ベクトル処理（＃４３）、ベクトル統合処理（＃４４）の４つのサブルーチンを備える。右回り追跡処理（＃４１）は、第１追跡手段１８が実行し左回り追跡処理（＃４２）は第２追跡手段１９が実行する。共有ベクトル処理（＃４３）は共有ベクトル処理手段２０が実行する。ベクトル統合処理（＃４４）はベクトル統合処理手段２１が実行する。
【００４３】
（右回り追跡処理）
図１６は、右回り追跡処理のサブフローチャートである。右回り追跡処理では、適当なベクトルから追跡をスタート（＃４１１）し、連続する要素を辿っていく。このとき、任意の追跡開始のベクトルごとに追跡リストを作成し、追跡したベクトルと追跡方向を記録しておく（＃４１２）。右回り追跡処理では、交点又は開放端において、追跡方向から見て最も右側に存在するベクトルを連続して追跡する。追跡は、追跡をスタートしたベクトルに対して追跡方向が同じとなった時点で終了する（＃４１３）。
【００４４】
図１３Ａは、ベクトルＶ１０をスタートとして右回り追跡を行う場合の処理を説明する図であり、図１３Ｂは、図１３Ａの追跡処理が行われる場合の追跡リストのデータ構成例を示す図である。図１３Ａに示すように、ベクトルＶ１０からベクトルの追跡が行われる場合、ベクトルＶ１０の追跡方向は、ベクトルの方向と逆向きであるため、図１３Ｂに示される追跡リストにベクトルＶ１０が逆向きに追跡されたことが記録される。交点Ｃ１では、ベクトルＶ１１，ベクトルＶ１２，ベクトルＶ１３が接続されているが、右回り追跡処理では、追跡方向から見て最も右側に存在するベクトル（ベクトルＶ１２）を選択して追跡する。同様に追跡を繰り返して追跡したベクトル及び交点を記録し、追跡をスタートしたベクトル（ベクトルＶ１０）に対して追跡方向が同じとなった時点で、当該追跡を終了する。
【００４５】
なお、本実施例では、追跡するベクトルについて、接続された他のベクトルが存在しなければ、現在追跡しているベクトルの端点から同じベクトルを逆向きに追跡する。具体的には、図１４Ａに示す、ベクトルＶ１１を追跡スタートのベクトルとして追跡を開始した場合、図１４Ｂに示すように、ベクトルＶ１１（逆），ベクトルＶ２０（逆），ベクトルＶ２２（順），ベクトルＶ２４（順）と追跡が進むが、ベクトルＶ２４（順）の終点では、交点が存在しないため、再度ベクトルＶ２４を逆向きに追跡する。また、ベクトルＶ２４（逆）を行い、交点Ｃ４では、ベクトルＶ２３（順）、ベクトルＶ２３（逆）、ベクトルＶ２５（逆）・・・と追跡が行われ、最後に、ベクトルＶ１１（逆）となった時点で当該追跡を終了する。
【００４６】
このときの追跡リストは、図１４Ｂに示す通りとなるが、右回り処理手段は、追跡リストの追跡結果であって、同じベクトルで追跡方向が互いに異なる追跡結果を有する連続するベクトルは端ベクトルと判断し、これを追跡結果から削除する処理を行う（＃４１４）。具体的には、図１４Ｂでは、Ｎｏ４，Ｎｏ５のベクトルＶ２４，Ｎｏ６，Ｎｏ７のベクトルＶ２３，Ｎｏ９，Ｎｏ１０のベクトルＶ２７は、それぞれ連続しかつ追跡方向が互いに異なるので、これらを端ベクトルとして追跡リストから削除する。図１４Ｃは、端ベクトル削除が行われた図１４Ｂの追跡リストの結果を示す図である。
【００４７】
なお、端ベクトルの削除は多段階で行われる。多段階に削除処理を行うことで、複数のベクトルによって１つの開放端を構成するような場合であっても、閉図形の抽出要素から除外することができる。たとえば、図４に示す本実施形態の例には含まれていないが、例えば、図１５Ａに示すように、３つのベクトルＶ５０、ベクトルＶ５１、ベクトルＶ５２で端ベクトルを構成しているような場合の追跡処理の例を説明する。
【００４８】
ベクトルＶ５０を追跡スタートとして追跡処理がスタートした場合、図１５Ｂに示すように、追跡結果は、ベクトルＶ５０（順），ベクトルＶ５１（順），ベクトルＶ５２（逆），ベクトルＶ５２（逆），ベクトルＶ５１（順），ベクトルＶ５０（逆）となり、スタートであるベクトルＶ５０（順）が追跡される時点で当該追跡処理が終了する。そして削除処理では、第１段階として、Ｎｏ３，Ｎｏ４のベクトルＶ５２及び、Ｎｏ６，Ｎｏ７のベクトルＶ５０が削除される。第１段階の削除の結果、次にＮｏ２，Ｎｏ５が隣り合う追跡結果となり、ベクトルが共通で追跡方向が反対であるため、ベクトル５１についても端ベクトルであると判断され、これが削除される。
【００４９】
なお、図１５Ａにおいて、追跡スタートのベクトルが例えばベクトルＶ５１であったとしても、図１５Ｃに示すように、削除処理を行えば、同じ結果となる。
【００５０】
次に、一図形内の複数閉図形の分割処理を行う。追跡リストの各ベクトルの端点で、重複の有無を検査し、重複があればその重複端点の前後で、追跡リストを分割する。この処理は、図１５Ｄのような一つの追跡リスト内に２つの閉図形Ｆ１，Ｆ２が存在するような場合に、それぞれの閉図形を検出するための処理である。具体的には、連続する交点（Ｃ３０，Ｃ３１）が２以上追跡リスト内に存在し、かつ当該交点に挟まれるベクトルＶ５０が正逆方向反対である場合に、複数の閉図形が連結している図形であると判断する。
【００５１】
なお、追跡リストを分割と端ベクトルの削除の順序はどちらを先にしてもよい。例えば、追跡リストの分割を行って、複数の閉図形を検出した後、それぞれの追跡リストにおいて上記の端ベクトルの削除に関する処理を行い、端ベクトルがあればそれを削除するようにしてもよい。
【００５２】
削除処理（＃４１４）を行った結果、追跡リストを構成するベクトルが２以下の場合は、当該追跡リストを削除する（＃４１７）。一方、追跡リストを構成するベクトルが２以上である場合は、閉図形であると判断し、閉図形リストに当該追跡リストを登録する（＃４１６）。閉図形リストは、ＲＯＭ２又はＲＡＭ３の一部領域で構成される閉図形リスト記憶部１４に格納される。
【００５３】
なお、このとき、閉図形リストに格納される追跡結果は、同じ閉図形が多数回認識される。例えば、ベクトルＶ１０をスタートベクトルとして抽出される閉図形と、ベクトルＶ１２，ベクトルＶ１４，ベクトルＶ３０をスタートベクトルとした場合に抽出されるそれぞれの閉図形は同じ閉図形であり、構成ベクトルを全て共通にする図形である。このような構成ベクトルを全て共通する閉図形は、２回目以降閉図形リストに登録しない。以上の処理を繰り返し行い、全てのベクトルを追跡スタートベクトルとした場合について追跡を行い、全てのベクトルについての追跡が終了すると右回り追跡処理を終了する。
【００５４】
（左回り追跡処理）
右回り追跡処理が終了すると、左回り追跡処理が実行される。左回り追跡処理は右回り追跡処理とほぼ同じ処理が行われ、適当なベクトルから追跡をスタートし、連続する要素を辿っていく。左回り追跡処理では、交点又は開放端において、追跡方向から見て最も左側に存在するベクトルを連続して追跡する点において、右回り追跡処理と異なる。
【００５５】
右回り追跡処理に加えて左回り追跡処理を行うことで、右回り追跡処理では抽出できなかった新たな閉図形を抽出することができる。図１７に示す例に基づいて、ベクトルＶ１０をスタートベクトルとして左回り追跡処理を行う場合を説明する。図１７に示すように、ベクトルＶ１０からベクトルの追跡が行われる場合、ベクトルＶ１０の追跡方向は、ベクトルの方向と逆向きであるため、追跡リストにベクトルＶ１０が逆向きに追跡されたことが記録される。交点Ｃ１では、ベクトルＶ１１，ベクトルＶ１２，ベクトルＶ１３が接続されているが、左回り追跡処理では、追跡方向から見て最も左側に存在するベクトルＶ１３を選択して追跡する。ベクトルＶ１３の終端は開放端であるため、追跡はベクトルＶ１３を逆向きに追跡し、次にベクトルＶ１１（逆）を追跡する。同様に追跡をベクトルＶ２０（逆），ベクトルＶ２１（順），ベクトルＶ６（順），ベクトルＶ２９（順），ベクトルＶ１８（逆），ベクトルＶ３２（逆），ベクトルＶ３２（順），ベクトルＶ３１（順），ベクトルＶ３０（順），ベクトルＶ１５（順），ベクトルＶ１５（逆），ベクトルＶ１６（順），ベクトルＶ１６（逆），ベクトルＶ１４（逆）と繰り返し、追跡をスタートしたベクトルＶ１０（逆）に対して追跡方向が同じとなった時点で、当該追跡を終了する。
【００５６】
端ベクトルの削除処理を行い、ベクトルＶ１３，ベクトルＶ３２を削除し、残ったベクトル（ベクトルＶ１０，ベクトルＶ１１，ベクトルＶ２０，ベクトルＶ２１，ベクトルＶ６，ベクトルＶ２９，ベクトルＶ１８，ベクトルＶ３１，ベクトルＶ３０，ベクトルＶ１４）を構成要素として閉図形が抽出される。
【００５７】
図１８は、閉図形リストのデータ構成例である。閉図形リストは、構成ベクトル列として登録される。
【００５８】
図１９は、図４のベクトルデータにもとづいて、右回り追跡処理と左回り追跡処理が終了した結果、抽出される閉図形の例を示す図である。右回り追跡処理と左回り追跡処理が終了した時点で、図１９に示すＡ〜Ｅまでの５つの閉図形が抽出されている。これらの抽出された閉図形を用いて新しい閉図形を構築する共有ベクトル処理を行う（＃４３）。
【００５９】
（共有ベクトル処理）
共有ベクトル処理は、それぞれの閉図形の共有する辺（ベクトル）に注目し、辺を共有するベクトルを除いて新たな閉図形を構築する処理である。以下、図を用いながら具体的に説明する。
【００６０】
共有ベクトル処理では、まず閉図形リストに格納されている全図形のうち全ての組み合わせについて下記の処理を行う。
【００６１】
図２０は共有ベクトル処理のサブフローチャートである。対象となる選択された２つの閉図形を構成するベクトルとして、双方に共通するベクトルを有しているか否かを判断する（＃４３０）。共有するベクトルが存在しない場合は、当該組み合わせについての共有ベクトル処理を行わない。
【００６２】
共有するベクトルが存在している場合は、当該共有ベクトルに着目し、閉図形リストに格納されている構成ベクトルの順逆が異なるように反転処理を行う。例えば、図２１Ａに示すように閉図形Ａと閉図形Ｂが選択された場合、共にベクトルＶ１２を共通にする。反転処理では、まず、閉図形Ａと閉図形Ｂの共有ベクトルに着目し、それぞれの閉図形において、共通するベクトルを、閉図形リストの最終ベクトルと先頭ベクトルに移動させる配置変換を行う（＃４３１）。
【００６３】
配置変換が行われたそれぞれの閉図形について、共有ベクトルの追跡方向が同じか異なるかを判断し（＃４３２）、追跡方向が同じである場合は、いずれか一方の閉図形について、全ての構成ベクトルの追跡方向を反転させる（＃４３２）。図２１Ｂは、反転処理が終了した閉図形Ａの閉図形リストであり、図２１Ｃは、反転処理が終了した閉図形Ｂの閉図形リストである。
【００６４】
次いで、２つの閉図形リストの共有ベクトルが連続するように、２つの図形リストを合成し（＃４３４）、新たな閉図形リストＦを作成する。図２２Ａに合成処理によって新たに作成された閉図形リストの例を示す。合成処理によって新たに作成された閉図形リストについて、削除処理を行う（＃４３５）。共有ベクトル処理における削除処理は、右回り追跡処理及び左回り追跡処理における削除処理において削除の対象となった連続配置されかつ追跡方向が互いに異なるベクトルに加え、すでに既登録の閉図形リストを構成するベクトルの配列が共通する場合はこれも削除する。
【００６５】
図２２Ａの例では、新たに合成された閉図形リストＦは、ベクトルＶ１２が連続配置されかつ追跡方向が互いに異なるため、これを削除する。削除後の閉図形リストは図２２Ｂのように構成される。
【００６６】
図２２Ｃに閉図形Ａと閉図形Ｂとの共有ベクトル処理で新たに構築された閉図形の構成を示す。閉図形Ａと閉図形Ｂとの共有ベクトル処理で新たに構築された閉図形Ｆは、図示のような多数のベクトルで構成される。また、反転処理を行うことによって接続ベクトルの追跡方向を同方向にすることができる。例えば、ベクトルＶ１０とベクトルＶ１１とでは、共に逆向きとなるように構成されており、ベクトルの接続の処理をスムーズに行うことができる。
【００６７】
なお、共有ベクトル処理において対象となる２つの閉図形が、共有するベクトルを２以上有しているときは、いずれか１つのベクトルに注目して上記配置変換、反転、合成の各処理を行い、合成リストについて削除処理を行う。
【００６８】
例えば、図２３Ａに示すように閉図形Ｂと閉図形Ｅの共有ベクトル処理では、図２３Ｂにおいて破線で示すベクトルＶ１１，ベクトルＶ１８，ベクトルＶ２０，ベクトルＶ３１が共有する。この場合、いずれか１つのベクトル（例えば、ベクトルＶ３１）を共有ベクトルとして上記処理（＃４３１〜＃４３５）を行う。
【００６９】
以下、閉図形リストを示して具体的に説明する。図２４は、閉図形Ｅと閉図形Ｂの閉図形リストである。図２４においては、すでに配置変換（＃４３１）及び反転処理（＃４３３）は終了している状態を示している。図２４では、ベクトルＶ３１を共有ベクトルとし２つの閉図形リストをベクトル合成する（＃４３４）。ベクトル合成された２つのリストは、次の通り削除処理（＃４３５）がなされる。まず、ベクトルＶ３１は、連続しかつ追跡方向が互いに異なるので、削除処理される。ベクトルＶ３１が削除されると、ベクトルＶ１８が連続しかつ追跡方向が互いに異なるのでベクトル１８を削除する。
【００７０】
次に、残った閉図形追跡リストの内で、複数閉図形の分割処理と同様の処理を行い、ベクトル端点で重複する交点（ここではＣ１・Ｃ５・Ｃ１２）に注目し、そのいずれかで、追跡リストを分割する。
【００７１】
ここで交点Ｃ１で分割したとすると、既登録の閉図形の構成ベクトルの削除後残った閉図形リストの内で、連続しかつ追跡方向が逆のベクトルを削除する。具体的には、ベクトルＶ１１は、リストの先頭と最後に位置し、連続しておりかつ追跡方向が逆であるので、これを削除する。また、ベクトルＶ１１を削除すると、ベクトルＶ２０が連続かつ追跡方向が逆となるのでこれを削除する。以上のベクトルの削除が終了すると、図２５に示す新たな閉図形リストが残ることとなる。生成された閉図形リストで、ベクトルＶ１２・ベクトルＶ３０・ベクトルＶ１４・ベクトルＶ１０の組み合わせは、閉図形Ａと共通するため、この組み合わせを削除する。
【００７２】
このように削除処理がなされた後の閉図形リストが既存の閉図形リストに登録されている閉図形であるかを確認し（＃４３７）、共通でない場合は、新たな閉図形として登録する（＃４３８）。
【００７３】
以上の処理について、全ての閉図形の組み合わせについて共有ベクトル処理が終了すると、全ての可能性のある閉図形が抽出される。具体的には、図２２Ｃに示した閉図形Ｆ（閉図形Ａと閉図形Ｂの組み合わせ）、や閉図形Ｇ（閉図形Ｅと閉図形Ｂの組み合わせ）、さらには、閉図形Ｂと閉図形Ｃの組み合わせが抽出される。
【００７４】
なお、たとえば、閉図形Ｇは閉図形Ｃと閉図形Ｄの組み合わせでも抽出可能であるが、上記のように既存の閉図形リストには重複して登録されないため、いずれかの組み合わせの共有ベクトル処理においてのみ登録されることとなる。
【００７５】
さらに、共有ベクトル処理は、共有ベクトル処理によって新たに追加された閉図形についての組み合わせも処理を行う。例えば、閉図形Ｂと閉図形Ｇ（閉図形Ｃと閉図形Ｄとを組み合わせ図形）の供給ベクトル処理も行われ、新たな閉図形を抽出することができる。
【００７６】
（ベクトル統合処理）
以上、共有ベクトル処理が終了し、閉図形が抽出された後、それぞれの閉図形リストにおいて、閉図形を構成するベクトルの接続フラグを確認し、接続フラグが互いに付されており、かつ追跡方向が共通のベクトルを統合処理し、新たなベクトルとしてベクトルデータに追加する。
【００７７】
図２６は、閉図形Ｅを構成する閉図形リストを構成するベクトルを示す図である。閉図形Ｅは、ベクトルＶ１０とベクトルＶ１１及びベクトルＶ３０とベクトルＶ３１が互いに接続フラグで付されており、かつ追跡方向が共通する。ベクトル統合処理では、これらを統合し、新たにベクトルＶ３３とベクトルＶ３４を作成するとともに、閉図形リストに構成されるベクトルを新たに統合されたベクトルに置き換える。
【００７８】
なお、ベクトル統合処理で新たに作成されたベクトルは、当該対象となる閉図形においてのみ用いられるものである。たとえば、閉図形Ｂにおいては、依然としてベクトルＶ１１もベクトルＶ３１も有効に存在している。よって、閉図形Ｂと閉図形Ｅでは、共通する線分を有しているが、これら共通する線分を構成するベクトルは異なるベクトルとして認識される。
【００７９】
ベクトル統合処理により、１つの線分中に存在する接続点を削除することができ、閉図形を相似形に拡大縮小する場合などに変形などの影響が及ぶことがない。
【００８０】
以上説明したように、本実施形態にかかる閉図形抽出装置によれば、線図形を構成するベクトルを交点で分割し、分割された全てのベクトルを追跡スタートベクトルとして、回転方向が異なる複数回の追跡を行い、追跡により得られた閉図形に共通するベクトルを統合して他の閉図形を構築することができる。これにより、ほぼ漏れなく閉図形の抽出を行うことができる。また、閉図形の抽出のために分割したベクトルは、分割された接続するベクトルの情報を格納しておくことにより、閉図形を構成するベクトルの統合が容易であり、１つの線分中に存在する接続点を除去することができる。
【００８１】
よって、正確に抽出された閉図形の相似形に拡大・縮小を行う場合に変形などの問題を起こすことがなく、例えば、服飾用の型紙の作成などにおいて好適に用いることができる。
【００８２】
なお、本発明は上記実施形態に限定されるものではなく、その他種々の態様で実施可能である。
【図面の簡単な説明】
【００８３】
【図１】本発明の一実施形態にかかる閉図形抽出装置の概略構成を示すブロック図である。
【図２】データ処理ユニットの機能ブロック図である。
【図３】データ処理ユニットが実行する処理のフローチャートである。
【図４】画像の入力処理により入力された画像データをベクトルデータとして抽出した状態を示す例である。
【図５】ベクトルデータ記憶部に格納されているベクトルデータのデータ構成例である。
【図６】交点抽出処理のフローチャートである。
【図７】交点抽出処理によって更新されたベクトルデータのデータ構造を示す図である。
【図８】交点抽出処理後のベクトル及び交点の状態を示す図である。
【図９】交点抽出処理によって抽出された交点リストのデータ構造を示す図である。
【図１０】延長処理後のベクトル及び交点の状態を示す図である。
【図１１】延長処理によって抽出された交点リストのデータ構造を示す図である。
【図１２】閉図形抽出処理のサブフローチャートである。
【図１３Ａ】ベクトルＶ１０をスタートとして右回り追跡を行う場合の処理を説明する図である。
【図１３Ｂ】図１３Ａの追跡処理が行われる場合の追跡リストのデータ構成例を示す図である。
【図１４Ａ】追跡しているベクトルの端点から同じベクトルを逆向きに追跡する追跡例を示す図である。
【図１４Ｂ】図１４Ａの追跡リストの構成を示す図である。
【図１４Ｃ】削除処理を行った後の図１４Ｂの追跡リストの構成を示す図である。
【図１５Ａ】複数のベクトルによって１つの開放端を構成するような場合のベクトル追跡の状態を説明する図である。
【図１５Ｂ】図１５Ａの線図形においてベクトルＶ５０を追跡スタートとして追跡処理がスタートした場合の追跡リストを示す図である。
【図１５Ｃ】図１５Ａの線図形においてベクトルＶ５１を追跡スタートとして追跡処理がスタートした場合の追跡リストを示す図である。
【図１５Ｄ】一追跡リスト中に複数の閉図形が存在している場合の分割処理を説明する図である。
【図１６】右回り追跡処理のサブフローチャートである。
【図１７】ベクトルＶ１０をスタートベクトルとして行われる左回り追跡処理を説明する図である。
【図１８】閉図形リストのデータ構成例である。
【図１９】図４のベクトルデータにもとづいて、右回り追跡処理と左回り追跡処理が終了した結果、抽出される閉図形の例を示す図である。
【図２０】共有ベクトル処理のサブフローチャートである。
【図２１Ａ】閉図形Ａと閉図形Ｂが選択された場合の共有ベクトル処理の説明図である。
【図２１Ｂ】反転処理が終了した閉図形Ａの閉図形リストである。
【図２１Ｃ】反転処理が終了した閉図形Ｂの閉図形リストである。
【図２２Ａ】合成処理によって新たに作成された閉図形リストの例を示す図である。
【図２２Ｂ】削除処理後の図２２Ａの閉図形リストの例を示す図である。
【図２２Ｃ】閉図形Ａと閉図形Ｂとの共有ベクトル処理で新たに構築された閉図形の構成図である。
【図２３Ａ】閉図形Ｂと閉図形Ｅが選択された場合の共有ベクトル処理の説明図である。
【図２３Ｂ】２３Ａの共有ベクトル処理において共有するベクトルを示す図である。
【図２４】閉図形Ｅと閉図形Ｂの閉図形リストである。
【図２５】閉図形Ｂと閉図形Ｅの共有ベクトル処理において新たに作成された閉図形リストの構成を示す図である。
【図２６】閉図形Ｅを構成する閉図形リストを構成するベクトルを示す図である。
【図２７】従来の閉図形抽出装置で抽出不可能な閉図形の例を示す図である。
【図２８】従来の閉図形抽出装置で抽出不可能な閉図形の例を示す図である。
【符号の説明】
【００８４】
１ ＣＰＵ
２ ＲＯＭ
３ ＲＡＭ
４ ベクトル演算用プロセッサ
５ 画像入力ポート
６ 端末制御部
７ システムバス
８ イメージスキャナ
９ 端末機
１０ データ処理ユニット
１１ ベクトルデータ記憶部
１２ 交点抽出手段
１３ 交点リスト記憶部
１４ 閉図形リスト記憶部
１５ 閉図形抽出手段
１６ 交点検出手段
１７ 延長処理手段
１８ 第１追跡手段
１９ 第２追跡手段
２０ 共有ベクトル処理手段
２１ ベクトル統合手段
【特許請求の範囲】
【請求項１】
複数のベクトルによって構成される線図形の中から、空間的に閉塞した領域としての閉図形を抽出する閉図形抽出装置であって、
前記線図形を構成する各ベクトルを格納するベクトルリストと、
前記ベクトルリストに格納されているベクトルについて、他のベクトルとの交点を抽出し、前記交点が存在する場合は当該ベクトルを分割して作成された新たなベクトルを互いの接続関係を対応づけて前記ベクトルリストに登録する、交点抽出手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして、追跡方向を記録しながら連続的に追跡して追跡リストを作成し、追跡リストに含まれる連続するベクトルが同一で互いに異なる追跡方向を有している場合は当該ベクトルを除外しつつ閉図形を抽出する追跡手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして
前記追跡手段で抽出された閉図形のうち、任意の２つの閉図形を構成する追跡リストに共通する任意の一つのベクトルが、連続かつ互いに異なる追跡方向を有するように前記追跡リストを再配置して、当該２つの追跡リストを合成する共有ベクトル合成手段と、
前記抽出図形を構成するベクトルが、交点抽出手段により分割されたベクトルを含む場合、前記ベクトルリストの接続関係に基づいて、統合したベクトルに置き換える、ベクトル統合手段とを備えることを特徴とする、閉図形抽出装置。
【請求項２】
前記追跡手段は、
右回りに追跡処理して追跡リストを作成する第１追跡手段と、
左回りに追跡処理して追跡リストを作成する第２追跡手段とを備える、ことを特徴とする、請求項１に記載の閉図形抽出装置。
【請求項３】
前記共有ベクトル合成手段は、前記追跡リスト変換手段により変換された前記共通ベクトルが連続するように前記追跡リストを合成することを特徴とする、請求項１又は２に記載の閉図形抽出装置。
【請求項４】
前記共有ベクトル合成手段は、合成された追跡リストのうち、連続する同一かつ互いに異なる追跡方向ベクトル及び前記抽出された他の閉図形と同配列のベクトルを削除することを特徴とする、請求項３に記載の閉図形抽出装置。
【請求項１】
複数のベクトルによって構成される線図形の中から、空間的に閉塞した領域としての閉図形を抽出する閉図形抽出装置であって、
前記線図形を構成する各ベクトルを格納するベクトルリストと、
前記ベクトルリストに格納されているベクトルについて、他のベクトルとの交点を抽出し、前記交点が存在する場合は当該ベクトルを分割して作成された新たなベクトルを互いの接続関係を対応づけて前記ベクトルリストに登録する、交点抽出手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして、追跡方向を記録しながら連続的に追跡して追跡リストを作成し、追跡リストに含まれる連続するベクトルが同一で互いに異なる追跡方向を有している場合は当該ベクトルを除外しつつ閉図形を抽出する追跡手段と、
前記ベクトルリストに登録されたベクトルについて、各ベクトルを開始ベクトルとして
前記追跡手段で抽出された閉図形のうち、任意の２つの閉図形を構成する追跡リストに共通する任意の一つのベクトルが、連続かつ互いに異なる追跡方向を有するように前記追跡リストを再配置して、当該２つの追跡リストを合成する共有ベクトル合成手段と、
前記抽出図形を構成するベクトルが、交点抽出手段により分割されたベクトルを含む場合、前記ベクトルリストの接続関係に基づいて、統合したベクトルに置き換える、ベクトル統合手段とを備えることを特徴とする、閉図形抽出装置。
【請求項２】
前記追跡手段は、
右回りに追跡処理して追跡リストを作成する第１追跡手段と、
左回りに追跡処理して追跡リストを作成する第２追跡手段とを備える、ことを特徴とする、請求項１に記載の閉図形抽出装置。
【請求項３】
前記共有ベクトル合成手段は、前記追跡リスト変換手段により変換された前記共通ベクトルが連続するように前記追跡リストを合成することを特徴とする、請求項１又は２に記載の閉図形抽出装置。
【請求項４】
前記共有ベクトル合成手段は、合成された追跡リストのうち、連続する同一かつ互いに異なる追跡方向ベクトル及び前記抽出された他の閉図形と同配列のベクトルを削除することを特徴とする、請求項３に記載の閉図形抽出装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１４Ｃ】
【図１５Ａ】
【図１５Ｂ】
【図１５Ｃ】
【図１５Ｄ】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１Ａ】
【図２１Ｂ】
【図２１Ｃ】
【図２２Ａ】
【図２２Ｂ】
【図２２Ｃ】
【図２３Ａ】
【図２３Ｂ】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１４Ｃ】
【図１５Ａ】
【図１５Ｂ】
【図１５Ｃ】
【図１５Ｄ】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１Ａ】
【図２１Ｂ】
【図２１Ｃ】
【図２２Ａ】
【図２２Ｂ】
【図２２Ｃ】
【図２３Ａ】
【図２３Ｂ】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【公開番号】特開２００９−２２３７７４（Ｐ２００９−２２３７７４Ａ）
【公開日】平成２１年１０月１日（２００９．１０．１）
【国際特許分類】
【出願番号】特願２００８−６９６４８（Ｐ２００８−６９６４８）
【出願日】平成２０年３月１８日（２００８．３．１８）
【出願人】（０００００１０９６）倉敷紡績株式会社 (296)
【Ｆターム（参考）】
【公開日】平成２１年１０月１日（２００９．１０．１）
【国際特許分類】
【出願日】平成２０年３月１８日（２００８．３．１８）
【出願人】（０００００１０９６）倉敷紡績株式会社 (296)
【Ｆターム（参考）】
[ Back to top ]