(57)【特許請求の範囲】
【請求項１】
２次元図形パタン上の曲線を編集する装置において、
予め入力された図形の形状と、位置入力手段によって入力された複数の座標データからなる座標列に基づいて、曲線の追加・削除のどちらを実行するかを自動的に判定する手段と、
その判定結果に基づいて曲線追加と曲線削除を選択的に実行する手段と
を備えることを特徴とする図形編集装置。
【請求項２】
前記位置入力手段による入力位置の移動の度に入力位置座標に応じて動作判定し、追加曲線または削除曲線を異った色で、曲線追加または曲線削除の実行前に、リアルタイムで表示することを特徴とする請求項１記載の図形編集装置。
【請求項３】
前記位置入力手段で指定した２個の座標から始点・終点を定め、その始点・終点がトレース可能な経路上にあるかどうかを削除判定基準として利用し、削除動作と判定された場合は始点から終点に至るトレース経路を削除曲線として選択することを特徴とする請求項１又は２記載の図形編集装置。
【請求項４】
前記トレース経路が複数ある場合には、最短経路を削除曲線として選択することを特徴とする請求項３記載の図形編集装置。
【請求項５】
始点・終点が図形の交点にあたるかどうかを検査し、交点の場合はその点を削除曲線から除外することを特徴とする請求項３記載の図形編集装置。
【請求項６】
前記位置入力手段による入力座標の近傍の座標点の中で、一番近い端点・交点を探索し、存在しない場合は一番近い他の図形点を探索し、みつかった場合はこれらの点を始点や終点として定めることを特徴とする請求項３〜５のいずれか一項に記載の図形編集装置。
【請求項７】
２次元図形パタン上の曲線を編集する方法において、
予め入力された図形の形状と、位置入力手段によって入力された複数の座標データからなる座標列に基づいて、曲線の追加・削除のどちらを実行するかを自動的に判定し、
その判定結果に基づいて曲線追加と曲線削除を選択的に実行する
ことを特徴とする図形編集方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２次元図形パタン上の曲線を編集するための図形編集装置及び方法に関する。
【０００２】
【従来の技術】
犯罪者の指紋照合を行う自動指紋照合装置（ＡＦＩＳ）では、スキャナに等により図４のような指紋画像を読み込み、これから指紋の盛り上がった部分に対応する図５のような芯線と呼ばれる曲線を抽出し、この芯線の端点・交点情報等を用いて照合を行う方式が広く用いられている。通常、図４から図５への芯線化処理はＡＦＩＳ内で自動的に行われるが、現場から採取した遺留指紋は画像品質が低いために芯線を自動抽出出来ない場合も多く、人間がコンピュータ上で対話的に芯線の追加・削除等を行うための芯線修正システムが開発・利用されていた。
【０００３】
芯線修正操作では、指紋が不明瞭な部分の芯線を新たに追加したり、文字等の指紋以外の部分で誤抽出した曲線を削除する操作が多く行われる。また、指紋の芯線が他の芯線と微妙に接している部分は正しく自動抽出出来ない場合もあり、図６の交点６０１を持つ芯線を図７の端点７０１を持つ芯線に修正したり、逆に図７の端点７０１を持つ芯線を図６の分岐点６０１を持つ芯線に修正するための芯線の削除・追加操作も頻繁に繰り返す必要があった。ここで、図６および図７は、芯線化処理後の２値図形データの配列を示す図である。
【０００４】
【発明が解決しようとする課題】
従来の芯線修正システムなどの対話的図形編集装置では、曲線の追加・削除のどちらの操作を行うかは、動作モード指定ボタンやメニュー、キーボード等によりオペレータが明示的に指定するのが一般的であったが、削除・追加を頻繁に繰り返す場合は動作指定操作も頻繁に行う必要があり、使い勝手が悪いという問題点があった。例えば、メニュー選択による動作モード切替えは、通常メニューを開くためのマウスクリック、項目選択のためのマウス移動、項目実行のためのマウスクリックと、３つの操作を行う必要がある。また、動作モード指定ボタンを使用する場合は、マウスのクリック操作は１回ですむ利点があるが、編集中の図形領域から動作モード指定ボタン領域までマウスを移動させてクリックし、さらにまた編集中の図形領域までマウスを戻す操作が必要となる。また、キーボードを使用する場合、例えば特定キーを押すことにより動作モードを切替える方法はキーボード操作に慣れたオペレータにとっては他の２方式より操作性が向上する利点があるが、キー操作に慣れる必要がある点や、他の目的でのキーボード使用が制限される点などの欠点があった。
【０００５】
また、図形削除を行う一般的な手法としては、矩形領域などの領域指定により領域内の図形を削除する方法、マウスによりブラシを動かしてその近くの図形を削除する方法、１曲線全体を選択して削除する方法などがあるが、これらの方法では、図５のような曲線が密集する場合に特定の曲線部分を削除する操作が面倒になる欠点があった。
【０００６】
曲線の追加、削除を繰り返して図形編集を行うアプローチの他に、描画済みの曲線を変形する方法もいくつか提案されているが、汎用的な曲線編集には不向きだったり、操作性が悪いという問題があった。例えば、特開昭６２−１２８３６７号公報の曲線の構成編集方式があるが、この方式はスプライン曲線で描画された曲線の通過点を修正することにより曲線の変形を行うため、図５のような画像処理により検出された曲線や、オペレータがフリーハンドで描いた曲線など、任意の形状の曲線編集には向いていない。特開平１０−１１５９８号公報では、入力済みの第一の線図形に対し、新たに第二の線図形を入力し、両線図形の座標から途中区間修正、延長修正、頂点移動修正の３種類のどの修正手段を行うかを自動判定し、第一の線図形の変形を行う図形編集装置が提案されている。しかし、本図形編集装置は入力済みの線図形の形状や位置の修正には適しているものの、線図形の途中を削除して二つの線図形に分割したり第二の線図形自身を追加する操作は同時には行えず、このような動作を行う場合はオペレータが動作切替えの指定を行う必要がある欠点があった。
【０００７】
また、特開平１１−３２８４３１号公報では、スケッチ曲線を新たに入力し、このスケッチ曲線に近接する図形内の曲線を見つけ出し、この曲線をスケッチ曲線に近付けるよう曲線変形する方法が提案されているが、本技術も特開平１０−１１５９８号公報の途中区間修正の編集方法の変形であり、同様の欠点があった。
【０００８】
芯線修正処理のように自然画像から自動生成した曲線を編集する場合は曲線の移動や拡大・縮小操等の変形を行いたい場合はあまり無く、自動抽出出来なかった曲線を追加したり、誤抽出した曲線を削除するなどの操作を効率的に行えることが望まれていた。本発明は、図形編集の際に曲線の追加や削除を効率的に行うことができる図形編集装置及び方法を提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記課題を解決するため、請求項１記載の発明は、２次元図形パタン上の曲線を編集する装置において、予め入力された図形の形状と、位置入力手段によって入力された複数の座標データからなる座標列に基づいて、曲線の追加・削除のどちらを実行するかを自動的に判定する手段と、その判定結果に基づいて曲線追加と曲線削除を選択的に実行する手段を備えることを特徴とする。請求項２記載の発明は、前記位置入力手段による入力位置の移動の度に入力位置座標に応じて動作判定し、追加曲線または削除曲線を異った色で、曲線追加または曲線削除の実行前に、リアルタイムで表示することを特徴とする。請求項３記載の発明は、前記位置入力手段で指定した２個の座標から始点・終点を定め、その始点・終点がトレース可能な経路上にあるかどうかを削除判定基準として利用し、削除動作と判定された場合は始点から終点に至るトレース経路を削除曲線として選択することを特徴とする。
【００１０】
請求項４記載の発明は、前記トレース経路が複数ある場合には、最短経路を削除曲線として選択することを特徴とする。請求項５記載の発明は、始点・終点が図形の交点にあたるかどうかを検査し、交点の場合はその点を削除曲線から除外することを特徴とする。請求項６記載の発明は、前記位置入力手段による入力座標の近傍の座標点の中で、一番近い端点・交点を探索し、存在しない場合は一番近い他の図形点を探索し、みつかった場合はこれらの点を始点や終点として定めることを特徴とする。請求項７記載の発明は、２次元図形パタン上の曲線を編集する方法において、予め入力された図形の形状と、位置入力手段によって入力された複数の座標データからなる座標列に基づいて、曲線の追加・削除のどちらを実行するかを自動的に判定し、その判定結果に基づいて曲線追加と曲線削除を選択的に実行することを特徴とする。
【００１１】
より具体的に発明の特徴を説明すると、本発明は、複数の曲線などから構成される図形の対話的編集装置において、オペレータが位置入力手段としてのマウスにより曲線の経路座標を入力するだけで、曲線の追加と削除の両方の動作を選択的に行うことを特徴とする装置である。曲線の追加・削除のどちらを行うかの動作判定は、マウスにより指定した座標と図形の形状から自動的に行われるため、オペレータがどちらの動作を行いたいかを別途メニュー、キーボード、動作モード指定ボタン等で指定する必要が無く、効率的に曲線の追加と削除を繰り返し行うことが出来る。
【００１２】
また、マウス移動に応じて追加曲線または削除曲線が別々の色で画面上に表示・更新されるため、オペレータは修正確定操作前に編集結果となる図形の形状をリアルタイムに知ることが出来、後戻り作業の無い効率的な曲線編集が可能となる。
【００１３】
【発明の実施の形態】
以下、本発明による図形編集装置の実施の形態について説明する。
［実施形態の構成］
本発明の第一の実施形態で示す図形編集装置は、コンピュータと周辺装置とコンピュータで実行されるプログラムによって実現される図１の構成図の手段１０１〜１０９より構成される。図形表示手段１０１は、編集中の図形を表示装置（ＣＲＴ）上に表示するための手段である。白い背景画面の上に図形記憶手段１０３で格納している図形を黒く表示し、その上に動作判定手段１０５で曲線削除動作と判定された場合は削除曲線生成手段１０６で生成した削除曲線を赤い線で合成表示し、曲線追加操作と判定された場合は追加曲線生成手段１０７で生成した追加曲線を緑の線で合成表示する。
【００１４】
座標入力手段１０２は、追加・削除を行う曲線の座標位置をオペレータが指定するためのポインティング装置（マウス）である。マウスボタンのクリック、ダブルクリック、マウス移動があった場合、これらの操作の種類とその時のマウスが指し示す図形上の座標位置を獲得する。
【００１５】
図形記憶手段１０３は、編集を行う図形を２次元の数値パタンｇ（ｘ，ｙ）として格納するメモリ装置である。ｇ（ｘ，ｙ）は、座標（ｘ，ｙ）が図形上の点（図形点）の場合に１を、背景上の点の場合に０を格納する。
【００１６】
座標記憶手段１０４は、座標入力手段１０２で入力したマウス位置のｘ座標、ｙ座標を、入力個数分だけ記憶する１次元のメモリ装置ｐｘ（ｉ）、ｐｙ（ｉ）である。ここで記憶された最初の座標点が曲線の始点、最後の座標が曲線の終点となる。
【００１７】
動作判定手段１０５は、図形記憶手段１０３で記憶した図形情報と、座標記憶手段１０４で記憶した入力座標列を元に、曲線の追加を行うか削除を行うかの動作判定を行う。本実施形態では、座標記憶手段１０４で記憶した入力座標数が２個で、共に図形上の点の場合、すなわちｇ（ｐｘ（１），ｐｙ（１））＝１かつｇ（ｐｘ（２），ｐｙ（２））＝１の場合で、始点（ｐｘ（１），ｐｙ（１））からトレース可能な曲線経路上に終点（ｐｘ（２），ｐｙ（２））が存在する場合は曲線削除動作と判定し、それ以外の場合は曲線追加動作と判定する。曲線のトレースとは、パタン上の曲線を構成する点列を順番にたどっていく公知の処理のことであり、注目点に隣接する右上左下斜め方向の近傍８画素の中から未トレースの図形上の点を探し出し、次々に注目点を移動していくことにより行われる。トレース中に曲線の端点（トレース方向が１方向の図形点）、交点（トレース方向が３〜４方向の図形点）、非曲線点（面積を持つ図形点などのトレース不可能な図形点）に到達した場合や始点座標に戻った場合（ループ曲線の場合）、その曲線のトレースを終了して再度始点から残りの曲線のトレースを行う。図形上の点が端点、交点、非曲線点、曲線経路点（トレース方向が２方向の図形点）かどうかは近傍８画素の図形パタンから判定可能で、近傍パタン全種類（２の８乗＝２５６個）に対してトレース続行不能かどうか（端点、交点、非曲線点かどうか）の判定値やトレース方向をあらかじめメモリ上に記憶しておくことにより、トレース中止判定やトレース処理を高速に行えることが知られている。
【００１８】
削除曲線生成手段１０６は、始点から終点に至る削除曲線の座標列を生成する。本実施形態では、動作判定手段１０５でトレースした始点から終点に至る経路の座標列を、そのまま削除曲線の座標列としてメモリに記憶する。ただし、経路の始点または終点が曲線の交点に当たる場合、残りの曲線が切断されないようにするため、交点の座標を削除曲線の座標列から取り除く。
【００１９】
追加曲線生成手段１０７は、座標記憶手段１０４で記憶した入力座標列を元に、始点から終点に至る追加曲線の座標列を生成する。本実施形態では、単に入力座標列を順番に経由する折れ線経路上の座標列を生成し、メモリに記憶しておくこととする。
【００２０】
図形修正手段１０８は、編集終了時に図形記憶手段１０３で記憶した図形パタンの修正を行う。すなわち、動作判定手段１０５で削除動作と判定された場合、削除曲線生成手段１０６で生成された削除曲線を図形上から削除（曲線上の座標点のｇ（ｘ，ｙ）に０を設定）し、追加動作と判定された場合、追加曲線生成手段１０７で生成された追加曲線を図形上に追加（曲線上の座標点のｇ（ｘ，ｙ）に１を設定）する。
【００２１】
制御手段１０９は、あらかじめ所定の記憶装置に記憶されているプログラムに従って動作し、上述した各手段１０１〜１０８を制御する。
【００２２】
［実施形態の動作の説明］
次に、図１の構成図及び図２のフローチャートを参照して本実施形態の全体の動作について詳細に説明する。最初に、図形表示手段１０１により編集中の図形を表示する（図２のステップＳ１）。開始直後は図形記憶手段１０３で記憶した図形のみが表示されるが、ステップＳ５を実行後に繰り返しステップＳ１が行われる場合、削除曲線または追加曲線が合成表示されることになる。次のステップＳ２では、座標入力手段１０２によりオペレータがＣＲＴ上の図形を見ながらマウス操作を行い、削除・追加したい曲線の座標を指定する。マウスの移動、マウスボタンのクリック、ダブルクリック操作を行う度に、その情報を獲得し、ステップＳ３以降に制御を移す。次のステップＳ３では、座標記憶手段１０４により、ステップＳ２で獲得した座標（ｘ座標、ｙ座標）を一次元のメモリｐｘ（ｉ）、ｐｙ（ｉ）に記憶する。上記のｉは、ｉ個目に記憶された座標であることを表している。次のステップＳ４では、ステップＳ３で記憶された入力座標数が２以上かどうかを検査し、２以上であればステップＳ５へ、２未満であればステップＳ９へ制御を移す。次のステップＳ５では、動作判定手段１０５より、曲線の削除を行うか追加を行うかの判定を行う。ステップＳ５で削除動作と判定された場合、削除曲線生成手段１０６により、削除する曲線座標列を生成する（ステップＳ６）。ステップＳ５で追加動作と判定された場合、追加曲線生成手段１０７により追加する曲線座標列を生成する（ステップＳ７）。ステップＳ８では、１つの曲線の編集処理を終了するかどうかの判定を行う。本実施形態では、ステップＳ２でのマウス操作がダブルクリックの場合、または最後に入力した座標が図形上の点でマウス操作がクリックの場合に編集処理を終了するものと判定し、ステップＳ１１に制御を移す。それ以外の場合はステップＳ９に制御を移す。ステップＳ９では、ステップＳ２での操作が座標確定操作だったかどうかの判定を行う。マウスクリック、ダブルクリックによる座標確定操作以外の場合、すなわちマウス移動操作だった場合、ステップＳ３で座標記憶手段１０４に記憶した座標１つを削除する（ステップＳ１０）。この後、ステップＳ１に再び制御を移し、編集処理を続行する。ステップＳ８で編集処理終了と判定された場合、図形修正手段１０８によって図形記憶手段１０３に記憶した図形パタンの修正を行い、１曲線の編集を終了する（ステップＳ１１）。複数の曲線編集を行う場合は、座標記憶手段１０４で記憶した全ての入力座標列と動作判定手段１０５での判定結果をクリアした上で、再び最初から同じ処理を繰り返せば良い。
【００２３】
次に、図３の具体例をあげて説明する。図３中のグレー（斜線付き）表示の格子点は図形上の点を、白色の格子点は背景上の点を表している。例えば座標点３０１、３０４は交点、３１２は端点、３０８は非曲線点、３０２、３０３、３０５、３０６、３０７、３０９、３１０、３１１は曲線経路点である。ここでは、オペレータは３０１から３１２に至る曲線の削除を行いたいものとする。まず、ステップＳ１で図３の図形を表示する。ステップＳ５の動作モード判定はまだ行われていないため、削除曲線、追加曲線ともに表示されない。次にステップＳ２でオペレータが曲線の始点として３０１をクリックし、ステップＳ３でこの３０１の座標を記憶する。入力座標はこの時点で１つしか指定していないため、ステップＳ４ではステップＳ９へ分岐する。また、入力座標はマウスクリックによるため、ステップＳ９ではステップＳ１に分岐し、画面が再表示される。（この時点で表示の変更部分は無い。）さらに、ステップＳ２でオペレータはマウスを３１２まで移動させる。ステップＳ３では新たに３１２の座標を記憶する。これで３０１、３１２の座標が座標は記憶手段により記憶され、ステップＳ４ではステップＳ５に分岐する。
【００２４】
ステップＳ５では、３０１を始点とする曲線のトレースを順番に行っていく。最初に３０１、３０２、３０３、３０４の座標列からなる曲線をトレースしていき、３０４が交点のため、この曲線のトレースを終了する。次に３０１、３０５、３０６、３０７、３０８の曲線をトレースしていき、３０８が非曲線点のため、この曲線のトレースを終了する。さらに３０１、３０９、３１０、３１１、３１２の曲線をトレースし、３１２が終点座標と一致するため、曲線削除を行うことと判定し、ステップＳ５を終了する。なお、以上の処理の中で３０５から次の点にトレースする際、斜めの点３０７へではなく縦横に隣接する点３０６を優先してトレースすることに注意する必要がある。これにより、縦横斜めに連結する曲線をうまくトレースすることが可能になる。ステップＳ５で削除動作と判定されたため、次にステップＳ６で削除曲線の生成を行う。すなわち、ステップＳ５でトレースした経路座標列３０１、３０９、３１０、３１１、３１２を取りだし、経路の両端点３０１及び３１２が曲線の交点かどうか判定する。端点３０１は図形上の３つの曲線の交点となっているため、３０１を削除曲線座標列から取り除き、３０９、３１０、３１１、３１２を削除曲線座標列としてメモリに記憶する。入力座標はマウス移動によるもののため、ステップＳ８でステップＳ９に分岐し、さらにステップＳ９からステップＳ１０に分岐することになる。ここで最後にステップＳ３で記憶した座標３１２が削除され、座標記憶手段１０３には３０１の座標１個のみが残る。
【００２５】
次にステップＳ１まで戻り、元の図形上にステップＳ６で生成した削除曲線３０９、３１０、３１１、３１２を赤く表示する。この時点ではまだ図形記憶手段１０３で記憶している図形の更新は行われていないことに注意する必要がある。オペレータは画面上で上記削除曲線を確認し、削除したい場合はステップＳ２で座標３１２上でマウスボタンのクリックを行う。これにより再びステップＳ３、Ｓ４、Ｓ５、Ｓ６の処理を前回と同様に繰り返すが、図形点３１２上のマウスクリックは編集終了動作のため、ステップＳ８ではステップＳ１１へ分岐する。最後に、ステップＳ１１で座標列３０９、３１０、３１１、３１２の図形データの書き換え、すなわち図形からの削除が行われる。以上により座標３０１と３１２をマウスでクリックすることにより、３０９、３１０、３１１、３１２を経路とする曲線が削除出来ることを示したが、逆に３０１から３１２に至る曲線の追加を行いたい場合は、既に存在する図形上の点以外の座標（例えば３１３）を中間点として指定し、３０１、３１３、３１２の順序にマウスでクリックすれば良い。
【００２６】
［本実施形態による効果］
本実施形態の第一の効果は、オペレータが曲線追加・曲線削除等の動作モードを別途指定すること無く、効率的に曲線の追加と削除を繰り返し行うことが出来ることにある。例えば、図６の図形を図７のように修正する場合は座標６０１と６０２をクリックするだけで良く、また図７の図形を図６のように修正する場合は座標７０１と７０２をクリックするだけで良い。このように、１本の曲線の追加・削除のどちらの操作もほぼ必要最低限の座標指定のみで実行可能となることに本発明の効果がある。
【００２７】
必要最低限の座標指定ですまない例外として、トレース可能な曲線上の２点間を結ぶ直線を描画したい場合がある。例えば図８の８０１から８０２を結ぶ直線を追加したい場合にあたる。このような場合は曲線削除動作にならないように余分な中間点８０３を指定する必要があるが、このような中間点指定の煩雑さは従来手法でのメニュー、キーボード、動作モード指定ボタン等による動作指定と比べても全く遜色が無く、指紋の芯線描画の場合等では元々中間点指定が必要な図５のような曲線を描画する場合が多いことなどを考えると、本発明の優位性は明らかである。
【００２８】
もう一つの例外として交点を持たない完全なループ曲線の削除を行う場合であるが、これについては第二の実施形態で説明する。
【００２９】
本実施形態の第二の効果は、オペレータが修正確定前にマウス移動のみで編集結果となる図形の形状を知ることが出来、後戻りの無い効率的な曲線編集が可能となることである。その理由は、マウス移動の度に削除・追加の動作モード判定が行なわれ、それによって削除曲線または追加曲線が異った色でリアルタイムに描画更新されるため、オペレータの意図と異る動作だった場合はマウス移動や中間点指定により動作モード等を柔軟に変更しながら編集出来ることにある。削除判定時の曲線トレース処理の計算量はトレースを行う曲線の長さに比例しており、直線描画と同じオーダ時間での計算が可能である。
【００３０】
マウス移動の度にマウス位置に応じて描画曲線をリアルタイムに更新する手法は従来技術として広く知られており、例えば特表平９−５０６９９１号公報の請求項８に記された装置がある。本発明では、この装置を改良して入力座標以外にも図形データを用いて動作判定を行い、これに応じて追加曲線または削除曲線を自動的に切替え、異る色で表示させる機能を新たに追加させることにより、単なる１種類の曲線の形状だけではなく、動作モード、追加曲線形状、削除曲線形状の３種類の情報をオペレータにリアルタイムに知らせることを可能にしている。
【００３１】
［発明の他の実施形態］
第一の実施形態の課題として、交点を持たない完全なループ曲線の特定区間を削除したい場合、曲線状の２点を経由するループ右回りと左回りの２つのトレース可能な経路が存在し、どちらが削除されるかは曲線のトレース順序に依存してオペレータが指定出来ないことがある。この課題を解決する第二の実施形態としては、第一の実施形態の削除曲線生成手段１０６を変形して始点から終点に至る全てのトレース経路で距離を計算しながら探索し、始点から終点に至る経路が複数見つかった場合はその中の最小距離となる経路を削除曲線として選択するようにすればよい。トレース経路の距離の計算は、縦方向にトレースした場合には距離１を、斜め方向にトレースした場合は２の平方根を加算していくことにより簡易的に計算可能である。ループの長い経路側やループ全体を削除したい場合は一旦短い距離で曲線を削除してループを解消した後に残りの曲線を削除するようにするか、あるいは矩形領域削除等の他の一般的な曲線削除手段を併用すれば良い。
【００３２】
第一の実施形態の課題として、他の曲線に隣接する曲線を追加した場合、トレース不可能な非曲線点や短いループ曲線が発生してしまい、実施形態の手段だけではこの部分の図形削除が面倒になってしまうことがあげられる。例えば図８において、８１１から８１２までの線を引くつもりでオペレータが座標指定位置を誤り８１１から８１８までの直線を追加した場合、８１７を経由するループが発生し、さらに８１５、８１６が非曲線点になる。このような場合、編集のやり直しや矩形領域削除・ブラシ削除等の従来手法による別の図形削除手段を併用することも考えられるが、第一の実施形態を改良することも可能である。
【００３３】
非曲線点の削除機能を付加するよう改良した第三の実施形態は、第一の実施形態の削除判定手段１０５及び削除曲線生成手段１０６を変形し、始点・終点が同一の非曲線点の連結領域に含まれる場合は削除動作と判定し、この非曲線点の連結領域を削除図形として生成するする機能を追加した装置である。これにより、曲線追加・曲線削除・非曲線点領域削除の３つの動作を選択実行させることが可能になる。画像中の連結領域の検出は一般的な画像処理として既知のものであり、始点指定時にあらかじめ始点を含む非曲線点連結領域を検出しておくことにより、終点指定時に高速に削除動作が可能になる。
【００３４】
非曲線点を自動的に除去するよう改良した第四の実施形態として、第一の実施形態の図形修正手段１０８を変形し、曲線追加後に図形の細線化を行う処理を追加した装置があげられる。細線化処理とは太さを持つ図形を段々細めていく一般的な画像処理で、繰り返し行うことにより非曲線点を無くすことが出来る。この処理を曲線追加の度に自動的に行うことにより、本実施形態による曲線削除編集が容易となる利点がある。
【００３５】
短いループ曲線を自動的に除去するよう改良した第五の実施形態として、第一の実施形態の追加曲線生成手段１０７を変形し、生成した追加曲線を描画済みの図形に接する部分で区間分割し、一定以下の長さの区間を追加曲線から除去する装置があげられる。ただし、始点・終点間が短い曲線を描画出来るようにするため、始点隣の座標点を含む区間と終点隣の座標点を含む区間が同一または隣接する場合、区間削除を行わないこととする。
【００３６】
本実施形態の動作を先の図８の例で説明すると、８１３から８１７までの直線は、８１３〜８１４、８１５、８１６、８１７という４区間に分割される。始点隣の８１３〜８１４の区間と終点隣の８１７の区間が隣接しないため、距離が短い８１５、８１６、８１７の３区間を追加曲線から削除することが出来る。なお、区間８１３〜８１４の長さがしきい値以下であればこの区間も追加曲線から削除されてしまうが、この場合は終点を８１２に移動することにより、始点隣を含む区間と終点隣を含む区間が同一となり直線描画が可能となる。
【００３７】
座標点指定を容易にする改良を行った第六の実施形態として、第一の実施形態の動作判定手段１０５、削除曲線生成手段１０６、追加曲線生成手段１０７で使用する座標点として、マウス位置そのものである入力座標点をそのまま使用せずに、入力座標の近傍から曲線上の点を探索し、見つかった場合はその中で最も距離が近い点の座標を入力座標の代わりに使用する装置が考えられる。この方法は図形選択時に座標点を厳密に指定する必要が無いという利点があり、従来の図形編集装置などでも図形選択に使われているが、本実施形態へ適用する場合、端点・交点のみを最初に探索し、存在しない場合は他の曲線経路点を探索するという２段階探索を行うことにより、端点・交点からの曲線削除・追加操作と、曲線経路点からの曲線削除・追加操作の両方の座標指定が容易になる利点がある。
【００３８】
削除曲線生成手段１０６は、始点や終点として曲線の交点が指定された場合には交点の削除を行わない機能を持っており、これは上記探索により交点が削除端点になった場合でも、交点に接続する他の曲線が分断されることを防ぐ効果がある。
【００３９】
また、上記座標修正の際、終点が始点と一致するような座標修正を制限するような改良を行ったり、曲線の交点として３分岐までしか許さない制約条件を持つ図形の編集を行う場合は曲線追加手段１０７で使用する座標のみ交点の優先探索を行わないようにすることも考えられる。
【００４０】
以上、本発明の具体的実施形態について説明したが、本発明はこの具体例にのみ制限するべきものではなく、本発明の技術的範囲を逸脱することなしに種々の変形や他の図形編集方法との組み合わせが可能であることは勿論である。例えば、図形表示手段１０１の変形として曲線の色を変えるかわりに模様（実線、点線等）や点滅のさせ方等を変える方法、座標入力手段１０２の変形としてトラックボールやキーボードのカーソルキー等のマウス以外の入力手段を使用する方法、動作判定手段１０５で終点から曲線のトレースを行う方法などが考えられるが、これらは上記実施形態と全く同じ効果をもつ。
【００４１】
また、高速化のために、例えば動作判定手段１０５での曲線トレース範囲を制限したり、制御手段１０９を簡略化することも容易である。  逆に、動作判定手段１０５を変形して曲線トレース時に交点があった場合にトレースを終了せず、交点の先の個々の曲線を繰り返しトレースすることにより、複数の交点を経由する複雑な曲線を削除出来るようにすることも可能である。この改良は計算時間の増加を伴うが、曲線のトレース処理は始点確定時に１回だけ行い、図形上の各画素に対して始点からのトレース方向を記憶しておくことにより、終点の移動による削除判定処理、削除曲線生成処理の高速化が可能となる。
【００４２】
また、他の図形編集方法と組み合わせて操作性や図形編集能力を向上させることも容易である。例えばマウスドラッグ（ボタンを押しながらのマウス移動）により曲線の始点・終点を指定する機能、マウスの別のボタンクリックで入力済みの座標をキャンセルする機能、キーボードの特定キーを押しながらマウス操作した場合に矩形削除やトレース可能な全曲線削除等の別の編集を行う機能、追加曲線生成手段１０７を変形して多項式補間やスプライン補間による自由曲線等の他の曲線描画を行う方法などがある。
【００４３】
また、図形表示手段１０１で、曲線の端点・交点を別の色で表示したり円等の他の図形を重ねて表示することにより端点・交点の位置をわかりやすくする等、図形編集に有効な表示情報を追加することも容易である。
【００４４】
なお、本発明による図形編集装置は、１または複数のコンピュータを含むハードウェア資源と、そこで実行されるプログラムとの組み合わせから構成することができ、そのコンピュータで実行されるプログラムは、コンピュータ読みとり可能な記録媒体または通信回線を介して頒布することが可能である。
【００４５】
【発明の効果】
以上説明したように、本発明によれば、図形編集の際に、曲線の追加や削除を行う操作の効率を従来よりも高めることができるという効果を得られる。
【図面の簡単な説明】
【図１】本発明による図形編集装置の一実施形態の構成を示すブロック図。
【図２】図１の図形編集装置の動作を説明するためのフローチャート。
【図３】本発明の図形編集装置の実施形態の動作を説明するためのパタン図。
【図４】指紋画像の一例を示す図。
【図５】図４の指紋画像から抽出されたを芯線の一例を示す図。
【図６】本発明および背景技術を説明するためのパタン図。
【図７】本発明および背景技術を説明するためのパタン図。
【図８】本発明を説明するためのパタン図。
【符号の説明】
１０１  図形表示手段
１０２  座標入力手段
１０３  図形記憶手段
１０４  座標記憶手段
１０５  動作判定手段
１０６  削除曲線生成手段
１０７  追加曲線生成手段
１０８  図形修正手段
１０９  制御手段
【図１】
0003564371.tif 000002
【図２】
0003564371.tif 000003
【図３】
0003564371.tif 000004
【図４】
0003564371.tif 000005
【図５】
0003564371.tif 000006
【図６】
0003564371.tif 000007
【図７】
0003564371.tif 000008
【図８】
0003564371.tif 000009