(57)【特許請求の範囲】
【請求項１】
複数の線図形を有する画像データを取り込んで表示画面上に表示し、
入力手段を介して上記複数の線図形と交わる補助線の入力を受け、
上記補助線と上記複数の線図形それぞれとの交点を探索基準点として設定し、
上記複数の設定された探索基準点の順序から該探索基準点の設定される線図形の隣接関係を認識し、
上記探索基準点を設定した線図形それぞれに認識エージェントを割り当てて、上記隣接関係を用いて該認識エージェントの割り当てられた複数の線図形を並列的に探索することを特徴とする線図形の認識方法。
【請求項２】
上記画像データは等高線図形の画像データであって、上記線図形は等高線であることを特徴とする請求項１に記載の線図形の認識方法。
【請求項３】
上記線画像の接合部または分断部において、上記隣接関係と既に確定している線図形の経路情報を用いて経路を予測することで上記探索を行うことを特徴とする請求項２に記載の線図形の認識方法。
【請求項４】
上記画像データから線経路を抽出し、
上記線経路の始終点間距離と経路長の比の値、上記線経路の経路長、上記線経路のベクトル長の総和と経路長の比の値を算出し、
上記それぞれの値を所定値と比較して選択された上記線経路について、上記探索基準点の設定を行うことを特徴とする請求項１乃至３の何れかに記載の線図形の認識方法。
【請求項５】
複数の線図形を有する画像データを表示する表示装置と、
上記表示された複数の線図形と交わる補助線の入力を受ける入力装置と、
上記補助線と上記複数の線図形それぞれとの交点を探索基準点として設定し、該複数の設定された探索基準点の順序から該探索基準点の設定される線図形の隣接関係を認識し、
上記探索基準点を設定した線図形それぞれに認識エージェントを割り当てて、上記隣接関係を用いて該該認識エージェントの割り当てられた複数の線図形を並列的に探索する制御部とを有することを特徴とする線図形の認識装置。
【請求項６】
上記画像データは等高線図形の画像データであって、上記線図形は等高線であることを特徴とする請求項５に記載の線図形の認識装置。
【請求項７】
上記制御部は、上記線画像の接合部または分断部において、上記隣接関係と既に確定している線図形の経路情報を用いて経路を予測することで上記探索を行うことを特徴とする請求項５又は６に記載の線図形の認識装置。
【請求項８】
上記制御部は、上記画像データから線経路を抽出し、
上記線経路の始終点間距離と経路長の比の値、上記線経路の経路長、上記線経路のベクトル長の総和と経路長の比の値を算出し、
上記それぞれの値を所定値と比較して選択された上記線経路について、上記探索基準点の設定を行うことを特徴とする請求項５乃至７の何れかに記載の線図形の認識装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、スキャナ・ＴＶカメラ等の光電変換装置により読み込んだ地図や図面に含まれた図形をデータベースに登録する図形の登録方法に関わり、特に等高線のように複数の似通った線の集合によって表される図形を認識して登録する場合に有効な線図形の認識方法に関する。
【０００２】
【従来の技術】
従来の線図形の認識方法として、等高線情報の自動入力に関する先行的な研究が数多く報告されている。例えば、文献1:安居院他2、「山岳地図情報に関する研究」(電子情報通信学会報告、PRL81-37,1981)では、入力対象となる山岳地図画像に細線化処理を加えた後、長いベクトル成分をなすかどうかの判定から等高線候補を抽出し、文字や記号により分断された等高線候補間をベクトルの角度に基づいて相互に接続する方法が提案されている。しかし、この方法では、ベクトルの角度の判定が局所的になるために、接続誤りが多く発生する問題があった。
【０００３】
一方、文献2:水谷他3、「ボロノイ線図による隣接関係を用いた等高線の抽出」(電子情報通信学会論文誌D-II、Vo1.J74-D-II,No.11,1991)では、線分の大域的な隣接関係を把握するためにボロノイ線図を作成し、これから線分間の隣接グラフを求め、分断された等高線成分の接続を正確に行う方法が提案されている。この方法では、隣接グラフの判定から接続誤りを減少させることが可能になっている。しかし、等高線が狭い領域に密集して図面として接合している部分や標高値・崖記号等によって線が分断する部分では、等高線を完全に認識することは不可能であり、多くの認識誤りを生じる。このため上記のようなバッチ処理型の入力方法を利用した自動認識を行った場合は、集中的な誤りチェックを操作者に要求することが多かった。この集中的な誤りチェックは膨大な労力を必要とするため、システムへの入力から出力に至る全体の工数は減少しないという問題があった。
【０００４】
そこで、文献3:山川他1、「会話型図面入カシステム」(日経コンピュータグラフィックス、1987年4月号、pp.120-130)に示されているように、ベクトル化初期の段階から積極的に操作者の判断が反映されるような対話誘導型の認識方式が注目されるようになってきている。この対話誘導型の認識方式では、ベクトル化の方向が自動的に決定されない場合には、システムから操作者への問い合わせによってベクトル化の方向を決定するため、誤りチェックに要する無駄な作業を削減することができる。しかし、等高線の接合部や分断部のように探索方向が自動的に決定しない箇所にさしかかる度に、探索をする方向すなわちベクトル化方向を問い合わせるようなシステム構成のため、操作者（ユーザ）の負担が大きい。
【０００５】
一方このような流れとは別に、対象となる図形を部分と全体の関係によって構造的に記述し、逐次的に探索した部分間の整合性を確認することによって全体の認識を行う研究も数多く報告されている。例えば、文献4:中村他1、「並列探索による画像特徴抽出」(人工知能学会誌、Vo1.8,No.1,PP.65-78,1993)では、このような構造記述に基づく特徴抽出をマルチエージエントの協調的な動作によって実現することを提案している。この方法によると、処理の流れに関する詳細な記述がなくとも、実行時に動的に処理を決定していくことが可能であり、自己整合的な問題解決による高精度な画像認識が期待されている。しかしこの方法は、組み合わせの爆発により膨大な計算時間を要する可能性がある。また、等高線のような複雑な形状をもつ図形では、構造記述自体も明確ではない。
【０００６】
そこで本発明では、マルチエージェント理論の線図形認識への適用として、操作者が指定した複数の隣接する線の一本一本に対応して経路認識を行う認識エージェントと全体の管理を行う管理エージェントによってシステムを構成する方法を提案する。この方法では各エージェントの自律的な挙動とエージェント間の協調動作を記述することによって高精度な認識が可能となる。しかし、エージェントの割り当てが間違っていて、一本の等高線に対応して二つのエージェントが設定されたりすると、エージェント間の協調動作が正しく行われないため、認識結果も間違ってしまうという問題がある。マルチエージェントの協調動作によって高精度な認識を実現するためには、エージェントが正しく設定されるようにエージェントの割り当てを自動的に変更する技術が重要である。
【０００７】
エージェントの割り当ての変更が実現している例として、文献５：行天他３、「文書画像からの文字切り出しのためのマルチエージェントシステム（...）がある。この文献では、マルチエージェント理論における空間分散方式を文書画像中の文字切り出し問題に適用し、文書画像中の一つの文字列に対応して一つのエージェントを設定している。しかし、文字切り出しと線図形の認識では認識対象が異なるため、文字認識に用いたエージェントの割り当てと割り当ての誤り検出方法をそのまま線図形に用いることはできない。
【０００８】
【発明が解決しようとする課題】
本発明の目的は、地図または図面上の図形をベクトル化データとして登録する際に図の表記上の制約（解像度、注釈等）によって、本来連続している線が不連続となっている部分や、本来独立した複数の線が結合してしまっている部分（以下問題箇所）を自動的に補間して、１つの図形を１つの連続するベクトル化データとして認識する際に、すでに認識が完了した確実な認識結果に基づいて、誤りなく線認識処理を行い、その結果をデータベースに自動的に登録することが可能な図形の登録方法及び装置を提供することにある。
【０００９】
本発明の他の目的は、経路補間前の図形に認識エージェントを割り当て、対象経路の認識を行う認識エージェント間で誤った割り当てを解消して、線図形の自動認識及び登録をすることが可能な線図形の登録方法及び装置を提供することにある。
【００１０】
【課題を解決するための手段】
上記目的を達成するために、紙図面上の線で表現されている図形を２値の画像データとして計算機に入力し、細線化ベクトル化処理等によって第１のベクトル化データを作成し、該第１のベクトル化データの構成要素に対してエージェントを割り当てる。該エージェントが対応するベクトル化データを認識するときに問題箇所に遭遇した場合、隣接するベクトル化データを参照して問題箇所のベクトル化データを補間して、得られた一連のベクトル化データを一つの図形データとして認識し、第２のベクトル化データとして登録する。更に、第一のベクトル化データに割り当てたエージェントが認識する図形データと一対一に対応するように、隣接関係のような線図形の基本特性に基づいてエージェントの割り当てが正しいかどうかを判断し、間違っている場合には線図形の基本特性に対応する矛盾が解消されるようにエージェントを統合したり分割したりしてエージェントの割り当てを変更する。また、エージェントの初期割り当て時には、局所的な連結性に基づいて図面全体の線経路を認識し、認識した線経路の一本一本に対応してエージェントを割り当ててもよい。なお、認識対象とする線図形は、画像から抽出された輪郭線でもよい。
【００１１】
【発明の実施の形態】
以下、本発明の一実施例を、地形図中の等高線を認識する例を用いて説明する。
【００１２】
（１）全体システム
図１は本発明による線図形の認識を行うためのシステム構成を示す図である。1は線の認識・ベクトル化等システムの制御を行う中央処理装置である。2は地図・図面を２値画像データとして取り込む画像入力装置である。例えば、スキャナを挙げられる。3はスキャナにて得られた２値画像データを格納するための第１のファイル装置である。4は第１のファイル装置に格納されている２値画像データに前処理を施して得られたベクトル化データを格納するための第２のファイル装置である。ここで行われる前処理は２値画像データを代表する特徴点（屈曲点と端点）を２つ以上抽出し、それらの点の位置座表を求め、順番にベクトル化する処理を指す。5はスキャナで取り込まれた２値画像データ、前処理により得られたベクトルデータ及び認識処理後のベクトルデータにより線画像、線図形等を表示する表示装置である。6は本システムの操作に対する指示を入力する入力装置である。７は、中央処理装置１で実行される前処理、認識処理等を記述したプログラム、及び処理の際に用いられる記憶領域を有するメモリである。ファイル装置（１）（２）やメモリ７はシステム内部に設けられているか、外部に備えるかを問わない。また、ファイル装置（１）（２）とメモリ７は、１つの大きなメモリと統合し、使用領域の分割によって区別されても良い。
【００１３】
図１のシステム全体の処理動作の概要を図２を用いて説明する。図２は、本システム全体の処理概略を示すPAD図である。
【００１４】
はじめに、スキャナ２により、処理すべき地形図が読み込まれ、２値画像データとして、ファイル装置(1)３に記憶される(ステップ401)。
【００１５】
ファイル装置(1)３に記憶された地形図の原画像データに対して、まず前処理としてベクトル化処理（前処理プログラム；ステップ402）を施して認識対象を含む入力された地形図そのもののベクトル化データを得る。本実施例においては、等高線のベクトル化データが得られる。得られた等高線の連続する一本に対して１つの認識エージェントを割り当て（初期割り当てプログラム；ステップ404）、等高線の認識を行う。割り当てられた認識エージェントの処理が全て終わるまで、認識エージェント間の競合解消処理及び協調認識処理を繰り返す（認識プログラム；ステップ405〜407）。等高線の認識処理が終わると、その結果を最終結果としてファイル装置(2)４等の記憶装置に蓄積する（登録プログラム）。必要有れば、表示装置へ表示する。次に個々の処理について説明する。
【００１６】
（２）ベクトル化処理（前処理プログラム；ステップ402）
図３は、本実施例の処理を説明するための画面表示例である。画面表示300は、ファイル装置(1)3から読み込んだ地形図の原画像データに対してベクトル化処理を施した後のベクトル化データを表示した図である。
【００１７】
本発明では、折れ線近似による間引き処理やヒゲ除去といった図形処理をベクトル化処理の後に実施してもよい。また、ベクトル化処理に伴う図形の変形等をさけるために、ノイズや文字・記号等の分離といった画像処理をベクトル化処理の前に実施してもよい。
【００１８】
（３）認識対称図形へのエージェントの割り当て（初期割り当てプログラム；ステップ403,404）
（3-1）認識対象領域（等高線成分）の抽出
画面表示300は、一般の地形図を読み込んだ２値画像データの表示である。そのような地形図は、等高線301だけでなく、家枠102、道路103、標高値や文字104等の様々な成分を含んでいる。画面表示300から処理対象図形である線図形を抽出するには、入力装置６によって、対象とする領域を直接指定する（310）。311はユーザがマウスを利用して指定した領域である。また、家枠102、道路103、標高値や文字104等、線図形以外の成分を指示装置６から指定して削除し、残りの表示を認識対象領域として指定してもよい（320）。
【００１９】
もちろん、読み込まれた画像が、認識対象とする図形のみにより構成されている場合や、上記の(2)で説明した文字・記号等を分離する画像処理がすでに実施されている場合は、単に処理対象領域の指定を行えばよい。
【００２０】
上記の方法のように、ユーザが外部より認識対象を指定してもよいが、以下に示すように認識対象図形を自動的に抽出する方法を用いることができる。図４〜図９を用いて説明する。
【００２１】
図４は等高線成分の自動抽出処理の流れを示すPAD図であり、図５は本方法において用いるテーブル構造を表す図である。500は図面全体に対応するベクトルデータテーブルであり、このテーブルには細線化ベクトル化処理（ステップ402）によって得られたベクトルの始点及び終点の座標に関する情報が格納されている。まず、500に対応するリストラベルテーブルを作成し、ラベルを０に初期化する（ステップ400）。510はリストラベルテーブルであり、リスト番号は500に格納されているベクトルの番号を、ラベルは対応するベクトルの認識が終了したかどうかのフラグ情報を表す。そこで、図面に対応する総てのベクトルについて（ステップ410）、対応するリストのラベルが０かどうかを判定する（ステップ420）。ラベルが０ならば、そのベクトルを出発点として線経路を認識し、対応するリストにラベルを付与する（ステップ430）。例えば、認識した線経路の番号をラベルとして付与する。520は認識した線経路データテーブルであり、このテーブルには線経路の構成点数及び構成点座標に関する情報が格納されている。これより、認識した線経路の特徴量を求めて、特徴空間におけるクラスタリングによって線経路を分類し、線経路情報テーブルに格納する（ステップ440）。530は線経路情報テーブルであり、ラベルは520に格納されている線経路の番号を、線経路情報は特徴量空間における分類を表す。例えば、その線経路が認識対象に対応していないならば０、対応しているならば１を付与することにする。
【００２２】
次に、等高線成分の抽出方法における線経路の認識方法を図６及び図７にて説明する。図６は線経路認識処理の流れを示すPAD図であり、図７は本方法における探索領域の設定方法とベクトルの決定方法に関する説明図である。まず、探索領域として円領域を設定し（ステップ611）、探索基点（確定経路の終点）の近傍領域を探索する。700はこの円領域の設定に関する説明図である。ここでは、探索基点を中心とした円領域を設定し、この領域内に端点を持つベクトルを探索する。但し、すでに認識の終了したベクトルは探索対象から除外する。ここで、円の半径は隣接する等高線間の距離に比べて十分に小さい値を設定する。ベクトルがこの円領域内に端点を持つかどうかの条件は701の条件式によって表される。ベクトルが円領域内に存在しないならば（ステップ612）、探索領域として楕円領域を設定し（ステップ613）、探索領域を拡大して再度探索する。710はこの楕円領域の設定方法に関する説明図である。ここでは、探索基点（確定経路の終点）と確定経路の延長線上の点を二つの焦点とする楕円領域を設定し、この領域内に端点を持つベクトルを探索する。ベクトルがこの領域内に端点を持つかどうかの条件は711によって表される。ベクトルが楕円領域内に存在しないならば（ステップ614）、線経路の認識を終了する（ステップ615）。ベクトルが存在する場合は、ベクトルを接続した場合の線の滑らかさを評価関数としてベクトルを決定する（ステップ616）。720は線の滑らかさに基づくベクトルの決定方法に関する説明図である。721は評価関数の定義とベクトルの決定条件を表す。二つ以上のベクトルが候補として存在する場合、どちらのベクトルでも滑らかに接続するならば、次のベクトルを決定することはできない。そこで、評価関数が指定範囲以下であって、評価関数の差が指定範囲以上ならば、次のベクトルとして決定する。ベクトルが決定しない場合は（ステップ617）、線経路の認識を終了する（618）。このような探索領域の設定からベクトルの決定までを、線経路の認識が終了するまで繰り返す（ステップ610）。730は線経路の認識において用いるパラメータの一覧である。
【００２３】
次に、等高線成分の抽出方法における線経路の分類方法を図８にて説明する。800は認識した線経路の例を表示した図である。認識した線経路は、ベクトル化データが存在するベクトル部分と、ベクトル化データが存在しないギャップ部分によって構成されている。ところで、等高線図形は、１）曲がりくねっている、２）実線で表示されている。３）ある程度以上の長さである、といった特徴を持つ。従って、特徴空間におけるクラスタリング処理を利用すれば、等高線図形に対応する線経路を抽出することが可能である。810は曲がりくねっているという基本特性に対応する特徴量とこの基本特性が満足されるための特徴量の条件を表す。この基本特性の特徴量は始終点間の距離／経路長によって表され、この特徴量が指定範囲以下ならば曲がりくねっていると判断される。820は実線で表示されているという基本特性に対応する特徴量とこの基本特性が満足されるための特徴量の条件を表す。この基本特性の特徴量はベクトル長の総和／経路長によって表され、この特徴量が指定範囲以上ならば実線で表示されていると判断される。830はある程度以上の長さであるという基本特性に対応する特徴量とこの基本特性が満足されるための特徴量の条件を表す。この基本特性の特徴量は経路長によって表される。
【００２４】
次に、等高線成分の抽出におけるパラメータ設定方法を図９にて説明する。等高線成分の抽出方法として特徴量に基づく線経路の分類方法を用いると、特徴量の範囲をパラメータとして設定する必要がある。図９はこのようなパラメータを設定するためのインタフェースを表示した図である。900はパラメータ設定画面を表し、910は操作者が指示した特徴量の範囲に対応する線経路を色分けして表示するためのウインドウ、920は線経路の特徴量の範囲を操作者によって設定するためのウインドウである。920におけるパラメータ設定は、特徴量の範囲を表すバーをマウス操作によって伸縮したり、特徴量の範囲をキーボードから入力したりすることによって実施される。このようにしてパラメータが設定されたならば、910のウインドウに特徴量の範囲に対応する線経路を表示する。パラメータが更新された場合は、対応する線経路を再表示する。
【００２５】
（3-2）認識対象図形へのエージェントの割り当て（ステップ404）
次に、領域の設定により認識対称図形にエージェントを割り当てる。
【００２６】
図３の330は並列探索の初期値設定の様子を示す。初期値は次のように指定される。操作者は入力装置6を用いて隣接する複数の等高線をよぎるように探索補助線331を引く。この探索補助線331と認識対象となる複数の等高線の交点を探索基準点332とする。指定された複数の探索基準点352をB1,B2,・・,BNとする。探索補助線331上の探索基準点332の順序は対応する等高線の隣接関係を表す。それから、各探索基準点332を初期特徴点として並列的に等高線の経路探索を開始する。
【００２７】
等高線の一本一本に適当にエージェントを割り当てて、エージェント間の隣接関係を自動的に把握する方法を説明する。
【００２８】
次に、本発明による線図形の認識方法における認識エージェントの初期割り当て方法を図10にて説明する。すでに等高線成分の抽出は終了し、その等高線成分は局所的な判断基準によって線経路として認識・登録されているとする。図10は認識エージェントの初期割り当てを示す図である。1000は局所的な判断基準によって認識した線経路と認識エージェントの対応関係を表した図である。ここで、線経路は切断点や分岐点で分断されている。このような線経路の一本一本に対応して一つずつ認識エージェントを割り当てる。1010は認識エージェントのデータとメソッドを表す。この認識エージェントは線経路データ（構成点数と構成点座標）をデータとして持ち、認識エージェントを生成したり、消滅したりする操作、線経路データに構成点を追加したり、線経路データから構成点を削除したりする操作、他の認識エージェントに線経路データを要求したり、この要求に対して線経路データを応答したりする操作等をメソッドとして持つ。
【００２９】
次に、本発明による線図形の認識方法において認識エージェントが問題発生時に環境を認識する方法を図11、図12及び図13にて説明する。切断部や接合部における線経路間の連結関係を求める問題を複数の認識エージェントの協力によって解決するためには、認識エージェントが置かれている環境として認識エージェント間の隣接関係を把握する必要がある。図11は隣接関係の認識方法における処理の流れを示すPAD図、図12は隣接関係を把握するために用いるボロノイ線図を示した図であり、図13は認識エージェントを制御する管理エージェントの設定方法を示す図である。例えば、文献２と同様の方法にボロノイ線図を用いて認識エージェント間の隣接関係を求める。まず、線経路間の二等分線によって構成されるボロノイ線図を作成し（ステップ1100）、これより隣接関係のネットワークを表す隣接グラフを作成する（ステップ1110）。1200はボロノイ線図を表し、1310は対応する隣接グラフを表わす。ここで、実線は隣接する線経路間の境界線（ボロノイ線図）の長さが対応する線経路の長さに比べて長い場合を表し、破線は短い場合を表す。実線は等高線同士の隣接関係を表している可能性が高いので強い隣接関係と呼び、破線はその可能性が低いので弱い隣接関係と呼ぶことにする。また、それ自体で閉ループをなすかあるいは端点がページ境界線上に存在する、という等高線図形の基本特性に基づき、この特性が満足される場合は認識終了、満足されない場合は問題発生とし認識エージェントを区別して表示している。ページとは、処理単位となる領域のことである。総ての認識エージェントについて（ステップ1120）、その認識エージェントが問題発生であって（ステップ1130）、どの管理エージェントにも登録されていないならば（ステップ1140）、管理エージェントを生成して（ステップ1150）、これに属する認識エージェントとその隣接関係を登録する（ステップ1160）。1320は管理エージェントとこれに対応する認識エージェントの関係を表示した図である。
【００３０】
（４）等高線の認識処理（認識プログラム；ステップ405〜407）
等高線の一本一本に割り当てられたエージェントの隣接関係が明らかになったら、次に、その隣接関係を手がかりとして、意味のある等高線としての認識処理を行う。図３の330の様にユーザが補助線を用いて、エージェントの隣接関係を初期設定した場合でも、誤って一本の等高線に重複して補助線を引いたり、ノイズ除去で分離できなかった道路などの認識対象外の図形に補助線を引いてしまうこともある。また、自動的にエージェントを設定した場合には、等高線の切断、分岐、結合等のため、一本の等高線に複数のエージェントが割り当てられたり、複数の等高線に１のエージェントしか割り当てられなかったりすることがある。
【００３１】
等高線の認識処理は、特定の高さの等高線とエージェントとを１対１に対応させるためにエージェントを統合したり分割する競合解消処理と、既に確定済みの他の等高線に割当てられたエージェントと協調して当該等高線の認識を行う協調認識処理とからなる。
【００３２】
（4-1）競合解消処理
本発明における認識エージェント間の競合解消方法を図14、図15及び図16にて説明する。本実施例では、認識エージェントを統合したり分割したりすることによって認識エージェント間の競合を解消する。
【００３３】
図14は切断部のような問題箇所における認識エージェントの統合方法を示す図である。1400は切断部における認識エージェントの初期割り当てを表す。ここでは、一本の等高線に対応して二つの認識エージェント（2と4）が割り当てられている。1410は切断部に対応する管理エージェントと認識エージェントを表す。この場合に、認識エージェント（2と4）の間には弱い隣接関係が存在している。そこで、このような隣接関係が存在する場合、管理エージェントはこれら二つの認識エージェントを統合して、新たな認識エージェントを生成する。1420は管理エージェントによる認識エージェントの統合を表し、1430は新規エージェントの隣接関係を表す。
【００３４】
図15は接合部のような問題箇所における認識エージェントの統合方法を表示した図である。1500は接合部における認識エージェントの初期割り当てを表す。ここでは、一本の等高線に対応して三つの認識エージェント（2, 5, 6 または 3, 5, 7）が割り当てられている。1510は接合部に対応する管理エージェントと認識エージェントを表す。この場合に、認識エージェント（2と5、3と5、5と6、5と7の）の間には弱い隣接関係が存在している。そこで、このような隣接関係が存在する場合、管理エージェントはこれら二つの認識エージェントを統合してゆき、新たな認識エージェントを生成する。1520は管理エージェントによる認識エージェントの統合を表し、1530は新規エージェントの隣接関係を表す。
【００３５】
図16は接合部のような問題箇所における認識エージェントの分割方法を表示した図である。1600は接合部における認識エージェントの初期割り当てを表す。ここでは、一つの認識エージェント（3）が三本の等高線に割り当てられている。1610は接合部に対応する管理エージェントと認識エージェントを表す。この場合、1と2と3の間あるいは3と4と5の間で矛盾（隣の隣＝隣）が発生している。このような協調ネットワークが存在する場合には、両者に共通する3の認識エージェントが間違っている可能性が高い。そこで、1620に示したように、管理エージェントはこの認識エージェントを三つに分割する。そして新たに三つの認識エージェントを生成する。1630は新たに生成した認識エージェントの割り当てを表し、1640は新規エージェントの隣接関係を表す。
【００３６】
（4-2）経路補間のための協調認識処理
図17は本方法による認識エージェント間のメッセージの流れを示す図であり、図18は本方法に基づく経路補間方法を示す図である。図17は図12の切断部に対応する管理エージェントと認識エージェントの間のメッセージの流れを表す。図18はこのような切断部における経路補間方法の概略図を表す。すでに認識エージェント間の隣接関係は解っている。この隣接関係を利用し、認識対象の経路を補間する。
【００３７】
本発明において、経路補間の際には、102の接合部や103の分断部のような問題箇所にさしかかった場合には既に確定した隣接する等高線を規範として探索方向を決定する。
【００３８】
以下では、図３の330に示すように、補助線331の設定により、等高線にエージェントを割り当てたとして協調処理を説明する。図３の330の場合は、エージェントの探索基準点が補助線の入力された位置により設定される。一方、図10のように、自動的にエージェントを等高線成分に割り当てた場合は、各エージェントが任意の位置を探索基準点として設定すればよい。
【００３９】
340は330を初期値とした経路探索を終了した後のベクトル化データを表示した図である。341は経路探索によって認識された等高線を表し、342は周回点、343は周囲点である。周回点は等高線がそれ自体で閉ループをなす場合にエージェントが探索基準点に戻ってきた点を表し、探索の終了点となる。ー方、周囲点はぺージ境界上に位置し、探索がこの点に到達した場合には探索基準点に戻って逆方向の探索を行う。逆方向の探索が再び周囲点に到達したら、この点を探索の終了点とする。以上のような探索基準点の設定から特徴点探索までの処理を等高線図形全体についてくり返しおこない、広範囲の等高線の認識結果を得る。
【００４０】
次に、認識処理を行うエージェントとエージェントが参照するデータの関係を図19を用いて説明する。本発明では、マルチエージェントによってシステムを構成し、各エージエントの自律的な挙動とエージェント間の協調動作を記述することによって処理の定式化を行っている。従来の手続き指向によるアプローチでは全ての処理の流れを漏れなく記述する必要があったのに対し、エージェント指向によるアプローチではエージェント間の協調動作はプログラムの実行時に動的に決定するため、処理の流れについての詳細な記述を必要としない。
【００４１】
1900は等高線に割り当てられたエージェント全体の管理を行う管理エージェント、1910は各等高線の経路認識を制御する認識エージェントを表し、1920は共有データ部を表す。共有データ部には等高線画像データや認識処理前のベクトル化データ等の入力情報、ベクトル探索を高速に行うための索引情報、探索が終了したベクトルに付けられるラベル情報、それから等高線の特徴点位置座標によって表される認識結果が格納されている。1930はエージェント間のメッセージ通信、1940はデータの参照を表している。これらエージェントの自律的な挙動についての機能定義と前提条件を図20に、エージェント間の協調動作についての具体的な処理内容を図21にまとめる。2001と2002は線図形を認識するエージェント（認識エージェント）の機能定義と前提条件をそれぞれ表し、2003と2004は管理エージエントの機能定義と前提条件をそれぞれ表す。また、図21の2101と2102はそれぞれ接合部と分断部における管理エージェントや認識エージェントの間の協調動作を表す。
【００４２】
次に、認識エージェントの自律的な挙動における経路探索の方法を図22にて説明する。今、i番目の等高線の探索を行っているとする。2200は探索領域近傍のベクトル化データを表す。2210はすでに探索が終了した確定済ベクトル、2220,2230,2240はまた探索の終了していない未確定ベクトルを表す。ベクトル2210の端点2211は経路探索の現在点を表し、探索がこの点まで終了していることを表している。2221,2231,2241はそれぞれ2220,2230,2240の端点を表す。また、2250は次の経路候補を探索するための探索領域を表す。この図では、2220と2230が経路候補として選ばれる。この探索領域内に隣接する等高線の確定済ベクトルが存在する場合には、隣接する経路との交差といった矛盾が生じないように経路候補を選ぶ。
【００４３】
複数の経路候補が存在する場合には、図２３及び図２４に示すように隣接情報に基づいて最適な経路候補を選ぶ。まず、経路候補を決定するための基準線を隣接情報に基づいて構成する手順を図２３に示す。２３００はi番目の等高線の探索領域に経路候補となる複数のベクトルが存在していることを表す。ここで、i+1番目の等高線の経路探索はすでに終了しているとする。２３１０に示したようにすでに確定したi+1番目の等高線について、現在点からの最短距離dを求める。それから、２３２０に示したようにi+1番目の等高線の構成ベクトルを距離dだけ平行移動し、これを基準線とする。次に、この基準線に基づいて最適な経路候補を選択する方法を図２４に示す。2400は基準線2410とベクトル2430の位置関係を表す。経路候補としては、この基準線に距離や方向が最も近いベクトルを選ぶべきである。そこで、2420のように評価関数を定義し、この評価関数を最小にするベクトルを次の経路候補として選ぶ。ここで、d1とd2はベクトル2430の両端点から基準線までの最短距離をそれぞれ表す。尚、選択した経路候補ベクトルを経路として確定するかどうかは、図25に示した判定方法を用いて行う。
【００４４】
接合部または分断部において隣接する等高線の経路情報に基づいて経路を予測する方法を図26にて説明する。図26は分断部における予測方法を表すが、接合部においても同様の処理によって経路予測が可能である。2600は探索領域内に経路候補となるベクトルが存在しないことを表す。ここで、i+1番目の等高線の経路探索はすでに終了しているとする。2610に示したようにすでに確定したi+1番目の等高線について、現在点からの最短距離dを求める。それから、2620に示したようにi+1番目の等高線の構成ベクトルを距離dだけ次々と平行移動していき、これを予測経路とする。予測経路の長さが指定範囲以内ならば、経路候補ベクトルがみつかるまで予測を続ける。
【００４５】
（５）記憶装置への登録（登録プログラム）
以上の処理により得られたデータは、スキャナ２で入力した図面を示す連続するベクトル化データとして、記録装置へ登録される。記録装置は、図１のシステム構成図で示したファイル装置（１）（２）、メモリ７でも良いし、それ以外の図示しない外部記憶媒体でもよい。
【００４６】
【発明の効果】
本発明によれば、入力された図形データをベクトル化データとして登録する際に、認識対象とする図形に割り当てられたエージェントの隣接関係を利用して、エージェントどうしの競合・協調処理を行うことにより、本来、連続すべき線が不連続であったり、独立である線が他の線と接合（図形が他の図形と接合）するような問題箇所において、過度の対話操作が減少し、不確定部分の自動処理能力が向上する。これにより線により表される図形のデータベース化における入カコストを大幅に低減することが可能となる。
【００４７】
更に、認識エージェントの初期割り当てが間違っていた場合にも、認識エージェントが正しく設定されるようにエージェントの割り当てを自動的に変更することが可能となり、不必要な対話操作を抑制し、ユーザにとって使いやすいシステムを提供することができる。
【図面の簡単な説明】
【図１】本発明のシステム構成を示す図である。
【図２】本発明の処理全体の流れを示すPAD図である。
【図３】本発明の処理の表示画面を示す図である。
【図４】等高線成分の自動抽出処理を示すPAD図である。
【図５】等高線成分の自動抽出処理で用いるテーブルの構造を示す図である。
【図６】線経路の認識処理を示すPAD図である。
【図７】探索領域の設定方法とベクトルの決定方法を説明する図である。
【図８】線経路の分類方法を説明する図である。
【図９】等高線成分の自動抽出処理におけるパラメータ設定時の画面表示である。
【図１０】認識エージェントの初期割り当て方法を示す図である。
【図１１】認識エージェントの隣接関係を認識する処理のPAD図である。
【図１２】隣接関係を把握するために用いるボロノイ線図である。
【図１３】管理エージェントの設定方法を説明する図である。
【図１４】切断部における認識エージェントの統合処理を説明する図である。
【図１５】接合部における認識エージェントの統合処理を説明する図である。
【図１６】接合部における認識エージェントの分割処理を説明する図である。
【図１７】協調認識における認識エージェント間のメッセージの授受関係を説明する図である。
【図１８】協調認識における切断部の経路補間処理を説明する図である。
【図１９】認識エージェントと管理エージェントとデータの関係を示す図である。
【図２０】エージェントの自律的な挙動についての機能定義と前提条件を示す図。
【図２１】エージェント間の協調動作についての具体的な処理内容を示す図である。
【図２２】エージェントの自律的な挙動における経路探索処理を説明する図である。
【図２３】経路候補を決定するための基準線を隣接情報に基づいて構成する手順を説明する図である。
【図２４】基準線に基づいて最適な経路候補を選択する処理を説明する図である。
【図２５】選択した経路候補ベクトルを経路の判定処理を説明する図である。
【図２６】分断部において隣接する等高線の経路情報に基づいて経路を予測する方法を説明する図である。
【符号の説明】
1…ｂ中央処理装置2…画像入力装置、3…第１のファイル装置、4…第２のファイル装置、5…表示装置、6…入力装置、７…メモリ。
【図１】
0003668560.tif 000002
【図２】
0003668560.tif 000003
【図３】
0003668560.tif 000004
【図４】
0003668560.tif 000005
【図５】
0003668560.tif 000006
【図６】
0003668560.tif 000007
【図７】
0003668560.tif 000008
【図８】
0003668560.tif 000009
【図９】
0003668560.tif 000010
【図１０】
0003668560.tif 000011
【図１１】
0003668560.tif 000012
【図１２】
0003668560.tif 000013
【図１３】
0003668560.tif 000014
【図１４】
0003668560.tif 000015
【図１５】
0003668560.tif 000016
【図１６】
0003668560.tif 000017
【図１７】
0003668560.tif 000018
【図１８】
0003668560.tif 000019
【図１９】
0003668560.tif 000020
【図２０】
0003668560.tif 000021
【図２１】
0003668560.tif 000022
【図２２】
0003668560.tif 000023
【図２３】
0003668560.tif 000024
【図２４】
0003668560.tif 000025
【図２５】
0003668560.tif 000026
【図２６】
0003668560.tif 000027