(57)【特許請求の範囲】
【請求項１】
（ｉ）少なくとも一つの線画セグメントを規定する複数の点から形成した第１線画と、（ii）空間座標系において離散位置を有する少なくとも一つの点から形成した第２線画とを記憶するための作業メモリを有するコンピュータシステムにおける、第１線画の第１線画セグメントを規定する点の非空の第１点セットの各点の位置を第２線画の第２線画セグメントを規定する点の非空の第２点セットの整合点にマッチングさせるための装置において、
第１点セットから所定数の第１作業点と第２点セットから同一数の第２作業点を使用者が選択することができる初期選択手段であり、各作業点は対応選択点の座標位置を表現する初期選択手段と、
各第１作業点をそれぞれの第２作業点と関連付けるために初期選択手段に結合された初期関連手段と、
第１線画セグメントの第１点セットからの非選択点と第２線画セグメントの第２点セットからの第２点セットの非選択点との間の対応を決定し、第１点セットからの各非選択点の座標位置と第２点セットからの整合点の座標位置とをマッチングさせるための初期関連手段に結合されたマッチャーであり、第１点セットの各非選択点から第２点セットの整合点へのベクトル変換を行い、上記ベクトル変換は、初期関連手段により関連付けされる如く作業点によって規定されるマッチャーとを具備し、
該マッチャーが、（１）各整合点に数値を割り当て、（２）該数値に従って第１点セットの点と第２セットの点との間のマッチングの正確さを判定する機能を有する
ことを特徴とする装置。
【請求項２】
（ｉ）少なくとも一つの線画セグメントを規定する第１複数の点から形成した第１線画と、（ii）２次元空間座標系において離散位置を有する第２複数の点から形成した第２線画とを記憶する作業メモリを有するコンピュータシステムにおける、第１線画の各点の座標位置を第２線画の整合点にマッチングさせる方法において、
第１線画の少なくとも一つの第１線画セグメントを識別する段階であり、各第１線画セグメントは、連続点の非空の第１点セットによって規定される段階と、
第２線画の少なくとも一つの第２線画セグメントを識別する段階であり、各第２線画セグメントは、連続点の非空の第２点セットによって規定される段階と、
各第１線画セグメントに対して、第１点セットを一つの第２点セットにマッチングさせる段階であり、マッチングさせる段階は、
ａ）第１点セットの４つの第１作業点の位置と第２点セットの４つの第２作業点の位置を使用者が選択する工程であり、各作業点は、対応選択点の座標位置を表現する段階と、
ｂ）各第１作業点をそれぞれの第２作業点と関連付ける工程と、
ｃ）第１作業点の座標位置が第１作業点の特定の一つの座標位置に関して表現され、そして第２作業点の座標位置が第２作業点の特定の一つの座標位置に関して表現される如く２次元座標系を特定する工程と、
ｄ）関連第１及び第２作業点の座標位置からの変換ベクトルを規定する工程であり、変換ベクトルは、第１点セットにおける点の座標位置と第２点セットにおける点の座標位置との間の数学的関係を提供する工程と、
ｅ）第１線画セグメントの第１点セットの各残余点と第２線画セグメントの第２点セットの各残余点との対応を決定し、変換ベクトルを第１点セットにおける各非選択点に適用することにより、第１点セットの各残余点の座標位置と第２点セットの整合点の座標位置にマッチングさせる工程とを含み、
該マッチングさせる工程が、（１）各整合点に数値を割り当てること、（２）該数値に従って第１点セットの点と第２点セットの点との間のマッチングの正確さを判定することを含む
ことを特徴とする方法。
【発明の詳細な説明】
発明の背景
動画化シーケンスにおいて、対象位置／姿勢、及び／又は背景、前景又は他の特徴における変化を示す一連と画像がある。各画像に対して、多重の線画フレームがある。コンピュータアニメーションの補助なしで、所与の画像の各フレームは、再描写されなければならない。各フレームを再描写するプロセスは、長たらしくて時間を消費する。
コンピュータが、動画化線画のフレームを発生させるために使用される。動画化シーケンスにおける各フレームを描写する代わりに、少数のキーフレームが、実際に、手又は他の手段により描写される。それから、コンピュータは、動画シーケンスを形成するために初期キーフレーム対の間に必要な中間フレームを発生させる。これは、「インビテゥイーン化」として周知である。
一般に、コンピュータは、初期キーフレーム線画と最終キーフレーム線画において点データにおける補間技術を使用して、インビテゥイーン線画を発生させる。補間法を使用するインビテゥイーン化の方法は、米国特許出願第０７／８１９、７６７号においてＰｏｇｇｉとＢｒｕｎｅｌｌｉによって記載される。成功するためには、初期線画における各点は、最終線画における対応点と整合されなければならない。コンピュータアニメーションにおいて、初期及び最終キーフレーム線画の制御点を対応付けることが必要であり、そのため、コンピュータはキーフレーム間を補間することができる。
手により２つの線画の間の点毎に整合させることは、少数の制御点しかない時には実現可能である。制御点の数が増大する時、タスクは、より複雑になり誤差を生じやすい。線画が不正に整合されるとき、発生されたインビテゥイーン線画は、不正になる。
従って、動画シーケンスの各フレームを発生させる際に、特に「インビテゥイーン」において、すなわち、所与のキーフレーム間のインビテゥイーン／中間線画を発生させる際に改良の必要性がある。
発明の要約
本発明は、先行技術からの必要性を扱う。特に、本発明は、２つの形状（又は線画）の間の対応を決定するためのコンピュータ装置及び方法を設ける。それ自体として、本発明は、物体が類似の形状を有するか、あるいは一方の物体が他方の物体の変形であるか、あるいは２つの物体が多様な幾何形状特徴において異なる（例えば、各線画における総点数が異なる）かを、第１物体（例えば、線画）と目標物体（例えば、線画）の間の点対点の整合／対応を決定するためのコンピュータマッチャーを設ける。
好ましい実施態様（例えば、動画シーケンスの発生において使用される）において、本発明は、第１線画における点を第２線画における点に変換するためのコンピュータ装置を設ける。発明の装置は、初期関連手段と、初期関連手段に結合されたマッチャーとを含む。初期関連手段は、第１線画におけるある数の作業点を選択し、第２線画における同数の作業点に関連付ける。それ自体として、第２線画における作業点は、第１線画における作業点に対してそれぞれの整合点として役立つ。
マッチャーは、第１線画における残余点と第２線画におけるそれぞれの残余点との対応を決定し、こうして整合させる。これは、マッチャーが、第１線画における各残余点から第２線画におけるそれぞれの点へのベクトル変換を行うことにより達成される。ベクトル変換は、第１線画における作業点と初期関連手段によって形成された第２線画の作業点の間の関連によって規定される。
一つの実施態様において、初期関連手段は、第１及び第２線画の少なくとも４つの作業点と第１及び第２線画の間のそれぞれの関連とを使用者が指定することを可能にするユーザーインターフェースを含む。
本発明の一つの見地により、マッチャーは、さらに、ランキング関数を実行することにより、第１線画における残余点の各々と第２線画におけるそれぞれの残余点との（例えば、可能な多重整合の中の）単一整合を設ける。特に、ランキング関数は、各整合に数値を割り当てる。しきい値に最も近い合成ランキング関数値との整合は、最高ランキング又は優先度を与えられ、及び／又は整合が正確さにおいて初期的に問題にされた場合に確立される。
【図面の簡単な説明】
発明の前述及び他の目的、特徴及び利点は、図面の好ましい実施態様の次の詳細な説明から明らかになるであろう。この場合、同様の参照文字は、種々の図面を通じて同一部分を参照する。図面は、必ずしも等尺ではなく、代わりに、発明の原理を示すことが強調される。
第１ａ〜１ｂ図は、２つの類似形状の間の整合／対応点の例を示す。
第２図は、発明の好ましい実施態様のブロック図である。
第３図は、発明の好ましい実施態様を使用する線画マッチングの例を示す。
第４図は、第２図の本発明の好ましい実施態様において使用されたマッチングルーチンの流れ図である。
発明の好ましい実施態様の詳細な説明
第１ａ〜１ｂ図は、２つの例示の線画の間の整合点を示す。第１ａ図は、文字「Ｊ」の線画１を示す。説明の簡単化と明確性のために、第１ａ図における線画は、９つの点（Ｐ1、Ｐ2、．．．Ｐ9）で示される。線画における実点数は、多かれ少なかれ９である。第１ｂ図は、第１ａ図からの対象文字「Ｊ」の変換を示す。線画は回転及び変形されているが、第１ａ図に示された点に対応する９つの点の配置を近似することができる。これらの９つの対応点（Ｐ'1、Ｐ'2、．．．Ｐ'3）は、第１ｂ図において示される。
さらに詳細には、形状は、一般に、多様な副形状又はセグメントから成る。例えば、第１ａ図における線画１は、２つの離散副形状に分割される。一方の副形状は、Ｐ1とＰ3によって境界付けられた直線セグメントである。他方の副形状は、Ｐ2とＰ9によって境界付けられた鉤形状セグメントである。変換された直線セグメントは、その時、第１ｂ図の線画２に位置し、対応点（Ｐ'1、Ｐ'2、Ｐ'3）は、相応して同様にラベル付けされる。同様に、回転及び変形された鉤形状セグメントは、第１ｂ図の線画２に見いだされる。その時、第１ａ図の線画における点Ｐ2〜Ｐ9の間の空間関係は、第１ｂ図の線画における対応点（Ｐ'2〜Ｐ'9）を配置／近似する際に使用される。第１ａ図の初期線画１における点に対応する第１ｂ図における変換線画２における点が生ずる。
こうして、発明の好ましい実施態様において、各画像又は対象は、副形状又はセグメントに分割され、そして各セグメントは個別に処置（処理）される。
第２図は、発明の実施態様の概略ブロック図である。マッチャー１０は、コンピュータ（デジタルプロセッサー）２０内で機能する。コンピュータ２０の作業メモリに記憶され又は他の方法で設けられて、マッチャー１０への入力として役立つ線画３０、４０の２つのキーフレームがある。原始キーフレーム３０は、原始線画３を含む。目標キーフレーム４０は、目標線画４を含む。使用者６０は、ユーザーインターフェース５０（例えば、ワークステーションと会話形又は他の構成プログラム）を通して、マッチャー１０に原始線画３における制御点毎を目標線画４における対応制御点に整合させる。マッチャー１０は、原始線画３の制御点を目標線画４に変換する。これは、次の如く達成される。
第３図は、発明を記載するために使用される原始及び目標線画３、４を示す。説明の簡単化と明確性のために、各線画は、唯一のセグメントを有する。原始線画３は、初期キーフレーム３０の線画である。目標線画４は、最終キーフレーム４０の線画である。実際に、原始線画３と目標線画４は、手書きか、コンピュータ発生されるか、又はコンピュータ２０のメモリに入力及び記憶された走査画像である。使用者６０の目的は、原始線画３と目標線画４の間のインビテゥイーン（すなわち、中間）形状又は線画をこれらの所与の線画３、４から発生させることである。
インビテゥイーン線画が発生される前に、原始線画３における点は、目標線画４に整合される。原始線画３と目標線画４は、各々、任意の数の制御点３１、４１を有する。これらの任意の数の制御点から、使用者は、原始線画３と目標線画４の間の少なくとも４対の整合又は対応点を識別しマークする。２つの線画３、４の間の対応の決定は、一般に、使用者６０によって迅速かつ容易に行われる。好ましくは、使用者は、原始線画３と目標線画４の両方において視覚的に区別される点位置３１を選択する。セグメントの端点は、そのような２つの点である。曲線遷移点は、他のそのような点である。以下に説明された如く、セグメントの端点のマーク付けは、点が非整合にされる機会を縮小する。加えて、セグメントの端点のマーク付けは、多重交差の機会を縮小する。
制限ではなく例示の目的のために、例えば、ユーザーインターフェース５０を通して、使用者は、原始線画３の端点３１ａと３１ｄを、目標線画４のそれぞれ端点４１ａと４１ｄへの整合／対応点としてマーク付けする。同様に、例えば、使用者６０は、（インターフェース５０を通して）、原始線画３の曲線遷移点３１ｂと３１ｃを、目標線画４のそれぞれ曲線遷移点４１ｂと４１ｃへの整合／対応点としてマーク付けする。これは、第３図に示された如く、４つの制御点対３１ａ、４１ａ；３１ｂ、４１ｂ；３１ｃ、４１ｃ；及び３１ｄ、４１ｄを生成する。
本発明の一つの実施態様において、コンピュータ２０は、線画３と４の間の４対の整合点をマーク付けすることにより使用者６０を補助する。原始線画の端点３１ａ、３１ｄは、目標線画の端点４１ａ、４１ｄに整合される。直線補間又は同様の技術が、残りの２対の点を整合させるために使用される。使用者６０は、使用者のより良い判断を満たすためにコンピュータによってマークされた点を変更することを許容される。点のコンピュータ選択は、常に使用者６０によって見られる如く正確な整合につながるわけではないが、使用者６０は、労力を節約される。
次に、全体として、本発明、特にマッチャー１０は、次の如く動作する。２つの線画と線画における４対の整合／対応制御点を与えられると、マッチャー１０は、２つの線画の間の整合（すなわち、対応点）を決定する直線の傾斜とｙ切片を表現するベクトルを構成する。具体的には、第１線画の各点に対して、ベクトルは、第２線画における点と交差する直線を設ける。第２線画における交差点は、第１線画における対象点への整合又は対応点である。こうして、ベクトルは、変換ベクトルと呼ばれる。
特有の表現において、第３図の例示において使用者６０によってマークされた４対の制御点の中で、１対の点３１ａ、４１ａは、線画３、４のために使用された基準フレームのそれぞれの原点を識別するために使用される。そして使用者６０によってマークされた他の３対の点は、変換ベクトルを生成するために使用される。すなわち、原始線画３における一つのマーク点３１ａは、原始線画の原点であるように選択される。原点３１ａは、原始線画３においてどこかに位置するマーク点でも良い。発明の好ましい実施態様において、使用者６０によってマークされた第１点は、原点として選択される。発明の代替態様において、原点は、マーク点の集合からランダムに選択される。第３図に示された如く、原始線画３の基準フレームの原点は、位置（ｘ0、ｙ0）にある。
原始線画３の原点３１ａが選択された後、目標線画４の対応点４１ａは、線画４の基準フレームの原点になる。第３図において、目標線画４の基準フレームの原点は、位置（ｘ'0、ｙ'0）にある。その時、２つの原点は、原始原点が目標原点に変換される如く互いに関連される。関連に応答して、コンピュータ２０は、（マッチャー１０を介して）、２つの原点（第３図に示される）を連結する直線３４ａを規定する。インビテゥイーン線画の原点は、直結直線３４上に位置する。
３つの残りのマーク点の対の各々に対して同様にして、使用者は、マッチャー１０に、対の各点のそれぞれの線画における位置を指定する。すなわち、線画３と４における原点を決定すると、使用者６０は、マッチャー１０に、線画３の（ｘ1、ｙ1）において点３１ｂの位置を指定する。その時、目標線画４における対応点４１ｂは、線画３の点３１ｂが線画４における点４１ｂに変換される如く線画４の（ｘ'1、ｙ'1）に位置する。使用者６０は、マッチャー１０に、線画３の（ｘ2、ｙ2）において点３１ｃの位置を指定する。その時、目標線画４における対応点４１ｃは、点３１ｃが点４１ｃに変換される如く線画４の（ｘ'2、ｙ'2）に位置する。最後に、使用者６０は、マッチャー１０に、原始線画３における（ｘ3、ｙ3）において点３１ｄの位置を指定する。その時、目標線画４における対応点４１ｄは、点３１ｄが点４１ｄに変換される如く線画４における（ｘ'3、ｙ'3)に位置する。
さらに、これらの関連の各々に応答して、マッチャー１０は、第３図に示された如く、関連点の間のそれぞれの連結直線を規定する。具体的には、マッチャー１０は、
（ｉ）原始線画３の関連点３１ｂと目標線画４の点４１ｂの間の連結直線３４ｂと、
（ii）原始線画３の関連点３１ｃと目標線画４の点４１ｃの間の連結直線３４ｃと、
（iii）原始線画３の関連点３１ｄと目標線画４の点４１ｄの間の連結直線３４ｄと
を計算する。インビテゥイーン線画の曲線遷移及び端点は、それぞれ、連結直線３４ｂ、３４ｃと３４ｄに位置する。
上記のほかに、マッチャー１０は、変換ベクトルを究極的に規定する変換マトリックスを計算するために、前述の３対の使用者のマーク点（３１ｂ、４１ｂ）、（３１ｃ、４１ｃ）、（３１ｄ、４１ｄ）を使用する。さらに具体的には、マッチャー１０は、３つの非原点の使用者のマーク点の座標から変換ベクトル［ａ、ｂ、ｃ］を生成する。目標線画４におけるベクトルのｙ'切片は、方程式
ｙ'＝ａｘ＋ｂｙ＋ｃｘ'                  方程式１
から計算される。ここで、ａ、ｂとｃは、未知数であり、ｘとｙは、原始線画３における既知（ｘ、ｙ）位置のベクトルであり、ｘ'とｙ'は、目標線画４における既知（ｘ'、ｙ'）位置のベクトルである。
３対の対象マーク点に対して方程式１を展開すると、
0003727061.tif 000002
を生ずる。ａ、ｂとｃに対して解くと、
0003727061.tif 000003
を生ずる。
ａ、ｂとｃに対して値が計算された後、原始線画３における各点３１に対して、方程式は、原始フレーム３０における点を目標線画４の任意の整合対応点４１がその線上になければならない目標フレーム４０における点に連結する直線に対して書き出される。そのような直線に対する方程式は、方程式１から、次の如くである。
ｙ’＝ｃｘ’＋(ａｘ＋ｂｙ)                  方程式４
ここで項（ａｘ＋ｂｙ）は、既知であり、目標フレーム４０におけるｙ’切片になり、そしてｃは、直線の勾配である。
従って、マッチャー１０は、新しく計算された変換ベクトル［ａ、ｂ、ｃ］を、原始線画３におけるすべてのマークのない（すなわち、使用者６０によって以前にマークされていない）点３１に適用する。結果として、各そのような原始線画点に対して、作業直線が規定される。それから、マッチャー１０は、各合成作業直線を目標フレーム４０に（すなわち、目標線画４において）プロットし、そして直線と目標線画４の間の交差点が、可能な整合位置（すなわち、対象原始線画点への対応点）になる。
原始線画３と目標線画４が正確なアフィン変換であるならば、変換ベクトルは、完全な結果につながることを保証される。不幸にも、雑音データ又は手書きを取り扱う時、原始及び目標線画は、めったに正確なアフィン変換とはならない。こうして、実際に、一般に目標線画４が原始線画３の正確なアフィン変換ではない場合に、前述のマッチャー１０の計算を行う時、３つのエラーが発生することがある。３つのエラーの場合は、
１．合成作業直線が、目標線画４に交差しない、
２．合成作業直線が、二度以上目標線画４に交差する、
３．合成作業直線が、ただ一度目標線画４に交差するが、交差は不正と「判断」される、
である。
３つのエラーの場合を取り扱うために、本発明は、次の如く付加処理を設ける。二以上の交差点（ケース２）がある場合に、最良の交差点が計算される。これは、所与の作業直線のすべての交差点に数値を割り当てるランキング関数を使用して達成される。割り当て数値又はランクが０（又は適切な所定値）に接近するほど、交差点は正しい選択になりやすい。単一交差点（ケース３）の場合に、ランキング関数は、交差の正確さを判定するために使用される。
交差点のランキングを決定するために、対象線画点３１、４１の間の距離及び角度、及び原始線画３と目標線画４におけるそれぞれの前整合点３１ａ、３１ｂ、４１ａ、４１ｂが、決定される。説明の簡単化と明確性のために、前整合点はまた、マーク点である。しかし、一般に、前整合点は、存立可能な最良交差点を有した前対象点になる。
新整合のランク「Ｒ」を決定するために、原始線画３における前整合点３１ａ、３１ｂに関する対象原始線画点３１の距離及び角度は、方程式、
Ｒ＝｜θt−θs｜＋Ｃ｜δt−δs｜              方程式５
を使用して、目標線画４における交差（新整合）点４１と目標線画４における前整合点４１ａ、４１ｂの間の距離及び角度と比較される。ランキング方程式５において、θtは、対象目標線画交差点４１から２つの前整合目標線画点４１ａ、４１ｂの各々へのベクトルの間の角度である。θsは、対象原始線画点３１と２つの前マッチ原始線画点３１ａ、３１ｂからのベクトルの間の角度である。δtは、対象目標線画交差点４１と前整合目標線画点４１ｂの間の距離である。δsは、対処原始線画点３１と前整合原始線画点３１ｂの間の距離である。Ｃは、角度又は距離を所望に応じて重み付けするスカラー重みである。Ｃが高値であるほど、距離測定値により大きな重み付けをし、そしてＣの分数値は、角度測定値をより重要にする。発明の好ましい実施態様において、Ｃは、値１．０を割り当てられ、距離及び角度測定値を等しく重要にする。
スケール付き合計、パーセント等は、θt、θs、δtとδsに対して使用され、その結果、単位のない計算が方程式５において行われることが理解される。
既知の交差点が存在しない（ケース１と３）の場合に、対象原始線画３の点は、目標線画４における任意の点に適正に整合されない。対処原始線画３の点は、より多くの情報が利用可能になるまで、一時的に無視されなければならない。その点は、待ちキュー、すなわち、処理されるために待機する点のリストに置かれる。点が待ちキューに置かれた後、次の原始線画点を処理する試みが為される。いったん妥当整合が決定されると、待ちキューにおけるすべての点は、前に良好に処理された原始線画点（目標線画４における適正に規定された整合又は対応点を有する）と現在の良好に処理された原始線画点（目標線画４における適正に規定された整合点を有する）の間で直線補間される。
第４図は、マッチャー１０（第２図）を実現するコンピュータマッチングルーチン１００の流れ図である。マッチングルーチン１００は、コンピュータ２０によって実行され、原始及び目標線画の個別セグメントに作用する。マッチングルーチン１００への入力により、使用者は、（第３図に記載された如く）線画セグメント当たり少なくとも４対の整合制御点を提供／指定し、一対は、原始及び目標線画セグメントの原点を識別する。
コンピュータ２０（ルーチン１００）は、まず、第４におけるステップ１０５においてすべてのデータを初期化する。初期化は、マトリックスサイズを規定することを含み、使用者の指定したマトリックス点の値（すなわち、非原点の整合点の対）にマトリックス値を初期化する。好ましい実施態様において、マトリックスは、４対以上の使用者の所定のマトリックス点を収容する大きさである（このため、使用者は、第３図に示されたマッチャー１０の初期ステップにおける５対以上の整合点を指定する）。そのような好ましい実施態様において、選択マトリックスサイズを超える付加的な使用者のマーク（指定）の点の対は、曲線のあてはめ中間点における補助として使用される。
同様に、マトリックスサイズは、２対以下の使用者指定マトリックス点を収容するために下方に調整されることが理解される。その場合に、使用者は、２対以下の初期的に整合した点を指定すればよく、一対は、原始及び目標線画における原点を識別し、残りの対はマトリックスを規定するために使用される。しかし、出願者は、４対の使用者指定点（一対は原始及び目標線画の原点を識別し、３対は、方程式３のマトリックスを規定する）による処理が、使用者の入力を最小にし、非常に良好な整合結果を可能にすることを見いだした。
データが初期化された後、ルーチン１００は、方程式３により、ステップ１１０において変換ベクトル［ａ、ｂ、ｃ］を計算する。マッチングルーチン１００は、続いてａ、ｂとｃの値を使用して、原始線画における各制御点の目標線画における点への変換を計算する。
特に、ルーチン１００は、次に、原始線画におけるすべての制御点を通ったステップ１６５においてループする。好ましくは、原始線画における制御点は、所与（使用者指定）の原点から順次に探索される。原始線画を通したループにおける第１ステップ１１５は、原始線画における続く対象点（すなわち、原点又は最終処理点に続く）の（ｘ、ｙ）位置を獲得することである。
（ｘ、ｙ）位置が計算された後、点は、ステップ１２０においてチェックされ、点が初期的に与えられた（すなわち、使用者指定又はマーク）入力点の一つであるかを判定する。点が与えられる（すなわち、使用者によって初期的にマークされた）ならば、目標線画における対応点は、また、（使用者により）予選択され入力においてマークされている。原始線画における対象点は、第４図におけるステップ１２５において目標線画の予指定された対応マーク点と対にされる。点が使用者によって初期的にマークされた（入力において与えられた）ならば、目標線画におけるｙ'切片が、方程式４により、ステップ１３０において計算される。
ｙ'切片が計算された後、ルーチン１００は、目標線画に合成直線を載せ、そしてステップ１３５において目標線画との切片数（すなわち、直線が交差する回数）を決定する。この時、３つの可能なケースが生ずる。交差点がない、一つの交差点がある、又は目標線画と２つ以上の交差点がある、である。
目標線画と交差点がないならば、対象原始線画点は、ステップ１６０において待ちキューに入れられる。待ちキューは、いったん存立可能な交差点が続いて処理される原始線画点に対して見いだされたならば処理される。原始線画点を通したループは、第４図におけるステップ１６５において判定される如く、処理する点がさらにあるならば継続する。ループは、ステップ１７０において原始線画における次の点に増分した後、再び始まる。
目標線画と２つ以上の交差点がある（すなわち、計算作業直線による多重交差点の場合）ならば、可能な交差点の配列が、第４図における副部分Ｅにおいて生成される。ルーチン１００は、ステップ１４０において、方程式５による交差点配列における最良の交差点を決定する。具体的には、ルーチン１００は、方程式５からランキングＲを各交差点に対して計算する。ルーチン１００は、最低計算ランキング値Ｒを有する交差点を最良交差点であると選択する。
いったん単一交差点（すなわち、一つの現存交差点又は最良交差点）が選択されたならば、ルーチン１００は、ステップ１４５において、選択交差点のランク値Ｒをチェックし、対応目標線画点（すなわち、選択交差点が目標線画と交差する点）の存立可能性を判定する。唯一の交差点の場合に、ルーチン１００は、ステップ１４５において、その交差点に対して計算されたランク値Ｒに基づいて存立可能性チェックを行う。発明の好ましい実施態様において、交差点のランキング値Ｒは、対応交差点（目標線画）点が存立可能な整合点であると見なされるために、所定の最大許容値以下でなければならない。発明の好ましい実施態様において、ランクに対する最大許容値は、目標及び原始線画の相対サイズに基づいて使用者６０により対話式に決定される。
選択最良又は対象交差の目標線画交差点が存立可能点でないならば、対象原始線画点が、ステップ１６０において待ちキューに入れられる。原始線画を通したループは、ステップ１６５において処理する点がさらにあるならば上記の如く継続する。ループは、ステップ１７０において、原始線画における次の点に増分した後、再び始まる。
対象交差点が存立可能点にあるならば、ルーチン１００は、第４図におけるステップ１５０において、対象原始線画点を目標線画における確認存立可能交差点と対にする。存立可能な整合が見いだされたために、ルーチン１００は、ステップ１５５において待ちキューを処理する。好ましい実施態様において、最も最近に対にされた整合点からのデータは、待ちキューにおける原始線画点に対する目標線画点への整合／対応を決定するために使用される。特に、待ちキューにおける各原始線画点に対して、目標線画における整合点（すなわち、位置）は、前決定された整合点の対（すなわち、原始線画点と対応目標線画点）と新しく決定された整合点の対の間の直線補間することにより計算される。原始線画を通したループは、ステップ１６５において、処理する原始線画点がさらにあるならば継続する。ループは、ステップ１７０において、原始線画における次の点へ増分した後、再び始まる。
ルーチン１００が原始線画におけるすべての点を初期的に処理した（すなわち、通過した）後、ステップ１７５において、待ちキューに残りの点があるかもしれない。最終原始線画点が目標線画における存立可能な整合を有しなかったならば、待ちキューにおいて少なくとも一つの点がある。原始線画点を非整合させるのを防止するために、ルーチン１００は、コンピュータ２０の主／呼出しルーチンに制御を返す１８０前に、（前処理された整合点の対の間の直線補間により）ステップ１７５において待ちキューを処理する。
発明が好ましい実施態様を参照して詳細に示され記載されたが、次の変形は、添付の請求の範囲によって記載された如く発明に準拠するとして技術における当業者には理解される。
例えば、コンピュータ２０は、ミニコンピュータ、ＰＣ、又は同等物である。ユーザーインターフェース５０は、使用者が選択を入力する表示モニターとキーボード又はマウスの如くコンピュータ２０に結合されたＩ／Ｏ装置を含む。応答して、コンピュータ２０は、使用者選択を実施するためのコマンドを発生させ、実行する。代替的に、使用者コマンドにおいて実行されたプログラム／ルーチンが、使用者選択を行うために使用される。ここで使用された用語「使用者選択」は、コンピュータ２０の作業メモリに保持された線画における使用者仕様及び／又は所望の点のマーキングを含む。
ユーザーインターフェース５０はまた、使用者入力を促進／獲得するために会話形又は他の作業プログラムを含む。受信使用者入力に応答して、作業プログラムはデータをフォーマットし、マッチャー１０へデータを設け、マッチャー１０（すなわち、マッチングルーチン１００）の実行を開始させる。
使用者６０とユーザーインターフェース５０の間及びユーザーインターフェース５０とマッチャー１０の間のそのような通信は、コンピュータプログラミングの技術における共通技術によりサポートされる。例えば、メニュー駆動主プログラムは、制御点対の選択と要求に対して使用者６０に所望の入力（すなわち、所与の原始及び目標線画と使用者指定制御点対）によりマッチャー１０をラン／実行させることを促す。
原始及び目標線画から所望数の作業制御点対を初期的に選択し関連付けるために他の手段（例えば、ソフトウェアルーチン及び同等物）も適切である。そのような手段は、所望の入力をマッチャー１０に設ける。
【図１ａ】
0003727061.tif 000004
【図１ｂ】
0003727061.tif 000005
【図２】
0003727061.tif 000006
【図３】
0003727061.tif 000007
【図４】
0003727061.tif 000008
0003727061.tif 000009