JPH0290366A - 対話式図形探索置換方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、一般には、コンピュータ支援設計（Ｃｏｍｐ
ｕｔｅｒ　ａｉｄｅｄ　ｇｅｏｍｅｔｒｉｃ　Ｄｅｓｉ
ｇｎ、　ＣＡＤと略す）装置のほか、コンピュータ内蔵
イラスト装置や製図装置のような対話型ディジタル合成
画像編集装置、より詳細には、上記の合成画像編集装置
の性能を向上させる優れた機能を備えた対話式図形探索
置換ユーティリティを具体化する方法及び手段に関する
ものである。

従来の技術 合成画像は、繰り返される幾何学的形状や繰り返される
図形的性質を含んでいることが多い。例えば、ディジタ
ルイラストの場合は、一定の色、字形又は線幅を有して
いることが多い。同様に、ディジタルイラストには、一
定の形状が繰り返して現れることがあり、才な一定の形
状の場合でも、その平行移動、回転、及び拡大縮小は、
さまざまである。理解されるように、繰り返される形状
又は性質のすべての事例を、矛盾なく修正するには、デ
ィジタルイラストを゛論理的に″変化させることが必要
であり、また望ましい。

従来のディジタル図形編集プログラムは、ユーザーがイ
ラストを論理的に変化させたいとき、それを手助けする
クラスタ化機能と例示化機能を備えている。ユーザーは
、クラスタ化機能により、対象を、一般に”クラスタ″
と呼ばれるグループに分類し、一定のクラスタの対象を
一単位として選択したり、操作したりすることが可能で
ある。

クラスタ化された対象の性質、例えば、色、線の幅、線
のスタイルは、容易に、迅速に、論理的に変更すること
が可能であるが、クラスタ化は、クラスタ化した対象の
形状の変更を容易するものではない。他方、ユーザーは
、例示化機能により、選択した対象がライブラリ対象の
“例示′″であることを宣言することができ、その宣言
により、ライブラリ対象の形状や性質に対して行われた
すべての変更が、自動的にその対象のすべての“例示″
に反映される。しかし、クラスタ化機能と例示化機能は
、用途が限られている。それらの欠点の１つは、クラス
タ化したり、又は例示化するようにイラストを構成しな
ければならないので、イラストのどの対象が論理的編集
を必要とするかを前もって決める必要があることである
。もう１つの欠点は、どの対象を変更すべきか、又は変
更すべきでないかをユーザーが一件一件決める自由がな
いことがである。

したがって、図形探索置換ユーティリティが要望されて
いることは明らかである。ここで用語“図形探索”″と
は、直線や曲線で形成された、又は直線や曲線で囲われ
た領域で定義される対象から成る任意に作られた合成画
像から指定された図形パターンのすべての場合を見付け
る手法を言う。

″図形置換°°とは、一致した対象（すなわち、ユーザ
ー指定探索要求に一致する対象）の選択された特徴（例
えば、形状、色、線の幅、線のスタイル、テキストの字
形）を、ユーザー指定置換パターンで表した新しい特徴
で置き換える手法をいう。

上記の定義は、図形探索置換ユーティリティのさらに別
の利用を示唆している。例えば、図形対象をデータベー
スの中に記述し、伝統的なデータベース間合せ言語又は
図形対象の問合せを明確な形で表すため特（こ設計した
新しい言語で表現した間合せによって、それらを容易に
取り出すことができる。図形探索置換は、図形データベ
ースに対するインタフェースとして使用することができ
る。

図形探索置換は、曲線や曲線のグループを能率よく見付
は出すアルゴリズムを提供するばかりでなく、図面によ
り、さもなくば問合せの目的対象の例を定義することに
より、図形問合せを簡単に表現することができる。同様
に、図形探索置換は、繰り返し形状を生成する図形文法
を具体的に述べるために使用することができる。また、
別に、形状文法（図形文法のサブセット）が研究され、
特に写実的な像の生成に利用されている。これらの形状
文法は、既存の形状を新しい形状で置換する規則を記述
する。図形探索置換は、置換パターンの形状のほかに、
その図形的パラメータ（例えば、色、線の幅、線のスタ
イル、テキストの字形）を定義するのに使用でき、した
がって形状文法の機能を拡張する。このように、図形探
索置換技術は、繰り返し形状、型板の形状や図形的マク
ロの生成を手助けする使いやすい手法であることが理解
されるであろう。

発明が解決しようとする課題 また、ディジタル画像内のユーザー指定幾何学的形状の
出現を発見するために使用できるパターン認識アルゴリ
ズムが開発されている。それらのアルゴリズムの一部は
、図形探索置換操作の探索フェーズを実行するのに適し
ている。しかし、ディジタル図形編集プログラムによっ
て生成された画像内のパターンの一致を発見できるよう
に最適化したアルゴリズムがより好ましい。例えば、２
つの曲線が同じ順序の線分セットで構成されているか否
かを判断することによって、それらの曲線が同じ形状を
有するか否かを迅速に判定できるように、アルゴリズム
を最適化することが好ましい。

また、あらかじめ定義した合成画面、ファイル、又はデ
ータベース内で一定の図形探索パターンの出現をすべて
見付は出すための単一経路決定手続きが得られるように
、アルゴリズムを最適化することが望ましい。

課題を解決するための手段 上記の課題を解決するため、本発明に従って、図形探索
手続きは、図形パターン突合せを使用して、合成ディジ
タル画像内のユーザー指定対象形状やその他の図形的性
質の出現を見付は出す。対話型ディジタル図形編集装置
、例えばコンピュータ内蔵イラスト装置や製図装置ある
いはＣＡＤ装置は、探索手続きと置換手続きを組み合わ
せて図形探索置換機能を具体化することができる。探索
のとき見付は出されたパターンの一致の全部又は一部は
、ユーザー指定探索パターンと空間的に整合するユーザ
ー指定置換パターンの形状やく又は）図形性質に従って
修正することかできる。単一画面、単一ファイル、又は
多数ファイル図形データベースの中に存在する図形パタ
ーンの一致を見付は出す単一経路指向性探索を実行する
アルゴリズムと、データベース内の既存対象と置換のと
き付加された対象とを弁別して、置換対象が、突き合わ
され、置換されることを防止するアルゴリズムが得られ
る。このように、これらのアルゴリズムは、決定論的で
、常に終結するので、例えば、定の探索パターンと一致
するすべての対象を見付は出して置換するＣＨＡＮＧＥ
ＡＬＬ操作をサポートする。

本発明のその他の特徴や利点は、添付図面を参照し、以
下の詳細な説明を読まれれば、明らかになるであろう。

実施例 以下、特定の実施例について発明の詳細な説明するが、
発明をその実施例に限定するつもりのないことは理解さ
れるであろう。むしろ、特許請求の範囲に記載した本発
明の精神及び発明の範囲に入るすべての修正態様、代替
態様及び均等態様は本発明に包含されるものと考える。

■、概説 ■、＾、使用環境 本発明が提供する図形探索置換ユーティリティの実施例
は、突合せツール（ＭａｔｃｈＴｏｏ　Ｉ　）として知
られる探索ソフトウェア応用プログラムの中に具体化さ
れている。ＭａｔｃｈＴｏｏｌは、Ｘｅｒｏｘ　Ｄｏｒ
ａｄ。

高性能パーソナルワークステーション（Ｋ八、Ｐｉｅｒ
。

“八　Ｒｅｔｒｏｓｐｅｃｔｉｖｅ　　ｏｎ　　ｔｈｅ
　　Ｄｏｒａｄｏ、ａ　　ｔｌｉｇｈ　　Ｐｅｒｆ。

ｒｍａｎｃｅ　Ｐｅｒｓｏｎａｌ　Ｃｏｍｐｕｔｅｒ、
　”Ｐｒｏｃｅｅｄｉｎｇｓｏｆ　ｔｈｅｌｏｔｈ　Ｓ
ｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ａｒｃｈ
ｉｔｅｃｔｕｒｅ。

５ＩＧＡＲＣＨ／ＩＥＥＥ、　Ｓｔｏｃｋｈｏｌｍ、　
Ｓｕ＋ｅｄｅｎ、　Ｊｕｎｅ　１９８３゜ｐｐ、２５２
〜２６９参照）を含む多数のプロセッサを稼働させため
、Ｃｅｄａｒのプログラミング環境（Ｄ。

５ｗ１ｎｅｈａｒｔ　　ｅｔ　　ａｌ、、　　“八　　
５ｔｒｕｃｔｕｒａｌ　　Ｖｉｅｕ＋　　ｏｆ　　ｔｈ
ｅＣｅｄａｒ　ｐｒｏｇｒａｍｍｉｎｇ　Ｅｎ−ｖｉｒ
ｏｎｍｅｎｔ”、　ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ
　ｏｎ　ＰｒｏｇｒａｍｍｉｎｇＬａｎｇｕａｇｅｓ　
ａｎｄ　Ｓｙｓｔｅｍｓ。

Ｖｏｌ、８．　Ｎｏ、４．０ｃｔｏｂｅｒ　１９８６．
　ｐｐ、４１９〜４９０参照）を使用するＣｅｄａｒプ
ログラミング言語で書かれたものである。

１、Ｂ、　　ユーザーインタフェース、典型的応用とオ
プション １、Ｂ、１．　　ｍ何字的形状の探索と置換最初に、図
形探索置換操作を使用して既存のイラストを変更するこ
とを説明する。第２図を参照すると、モニター１３には
、２個の窓２１．２２が開いている。第１の窓２１には
、編集されるイラストが表示される。第２の窓２２は、
ユーザー指定探索パターンと置換パターンをそれぞれ表
示するため、一対の窓枠２３．２４に分割されている。

探索パターンと置換パターンは、所定の場所に描くこと
もできるし、又は適当なソースから複写することもでき
る。

第２図に示すように、編集するイラストは、ハイウェイ
記号の枠をアーチ形や直線区分やパラメトリック曲線で
表し、道路をパラメトリック曲線で表した地図である。

テキストは、一定のフォント名とアフィン変換を有する
＾ＳＣｎストリングで表しである。最近、カルフォルニ
ヤ州、サンジョセの近くのハイウェイ１７の区間が州連
絡道路８８０と名称変更された。このような地図の改訂
には、探索置換操作が適している。

地図の改訂を実行するなめ、ハイウェイ１７の記号を、
編集する地図から複写するなどして、探索１〇− 窓枠２３に入れる。さらに、州連絡道路８８０記号を、
所定の場所に描くか、他の既存のイラストから複写する
かして、置換窓枠２４に入れる。置換を実行するとき、
ずれが生じないように、２つの記号の中心が、確実にそ
れぞれの窓枠の同一座標にあるように注意する。例えば
、２つの記号の中心を探索窓枠２３内で整合し、次に座
標を保存する゛移動″操作を用いて州連絡道路２８０記
号を置換窓枠２４の中に動かすことにより、２つの記号
の中心を容易に整合させることができる。

基本的な探索置換動作を制御する主ユーザーインタフェ
ースとして比較的簡単なメニュー２５（ＳＥＡＲＣＨ，
ＹＥＳ、　Ｎｏ、　ＣＮ八へＧＥＡＬＬ）を使用するこ
とができる。５ＥＡＲＴＨオプシヨンを選択すると、編
集するイラストが所定方向の順序（例えば、上から下、
左から右の順序）で探索され、同時にハイウェイ　１７
記号探索パターンに一致する対象が探索される。一致が
発見されると、それを強調表示するために、突合せパタ
ーンが選ばれる。ＹＥＳオプションを選択すると、存在
するハイウェイ１７が抹消され、州連絡道路２８０記号
がそれに置き換えられ、そして探索が再開される。ハイ
ウェイ１７は、州連絡道路２８０の北側だけが、州連絡
道路８８０と名称変更されたので、２回の探索置換操作
でこの地図を改訂することができる。３回目の探索フェ
ーズは、ハイウェイ１７の記号を発見するが、この記号
は州連絡道路２８０の南側であるので、３回目の置換フ
ェーズをオーバーライドするためにＮＯオプションが選
択される。探索は最後まで続行するが、それ以上、一致
は発見されないので、ユーザーはそれ以上一致が発見さ
れなかったことに気が付き、処理は終了する。第２Ｂ図
は、改訂された地図を示す。もちろん、もしハイウェイ
１７の全記号を州連絡道路２８０の記号へ変更したけれ
ば、ＣＩ（ＡＮＧＥＡＬＬオプションを選択することが
できよう。

以上の説明は、サイズ、形状及び向きが既知の対象の集
まりに適用した場合の探索と置換の実例である。しかし
、６個の探索パラメータ、すなわち細分度（Ｇｒａｎｕ
ｌａｒｉｔｙ）、回転不変性（Ｒｏｔａｔｉｏｎ　Ｉｎ
ｖａｒｉａｎｃｅ）、スケール不変性（Ｓｃａｌｅ　Ｉ
ｎｖａｒｉａｎｃｅ）、極性（Ｐｏｌａｒｉｔｙ）、文
脈依存性（ｃｏｎｔｅｘｔＳｅｎｓｉｔｉｖｉｔｙ）、
及び許容誤差（Ｔｏｌｅｒａｎｃｅ）のうち１つ以上を
変化させることで、より制約の少ない探索が実行できる
ことを理解されたい。第３図に、これらの特徴のユーザ
ーインタフェースを示す。

最初の４つのパラメータは、本節で論じるが、後の２つ
は、拡張探索置換操作についての節で論じることにする
。

細分度（ｇｒａｎｕｌａｒｉｔｙ）は、値「クラスタｊ
、値「曲線」、又は値「線分」を取ることができる。

細分度は、探索置換ユーティリティに、突合せを実行す
るとき、イラストの構造のどのくらいを無視できるかを
伝える。もし細分度が「クラスタ」にセットされれば、
編集中のイラスト内のクラスタ化された一群の曲線は、
探索パターン内の同様な完全クラスタとだけ一致するで
あろう。すなわち、クラスタ内の個々の曲線は独立に一
致することはできない。細分度が「曲線」にセットされ
た場合には、イラスト内の曲線＾は、たとえ曲線へがク
ラスタの一部分であっても、探索パターン内の同様な曲
線Ｂと一致するであろう。この細分度では、曲線へが完
全に一致しなければならないので、曲線への一部分のサ
ブセットだけを含むパターンは一致しないであろう。「
線分」の場合は、もし曲線Ｂの一部分のすべてが曲線へ
の対応する一部分に一致すれば、曲線＾の一部分は、パ
ターン曲線Ｂによって突き合わせることができる。この
細分度の場合は、探索窓枠２３（第２八図）内の曲線が
そのまま、編集する画面内の単一曲線の一部分と一致す
ることができる。

「線分」の突合せでは、最小レベルの画面要素（線分）
が原子として取り扱われるので、それらの部分に対して
突き合わせることはできない。このことは、性能上の利
点があり、かつ特定の対象クラスの一部分を置換する場
合に付随する別の問題が避けられる。例えば、非局部ス
プラインのような、ある種の線分の部分は、線分全体に
変化を生じさせずに、置換することができない。

［回転不変性Ｊ　（Ｒｏｔａｔｉｏｎ　Ｉｎｖａｒｉａ
ｎｃｅ）をオンにした場合は、もし平行移動と回転のあ
る組合せによって、探索パターンと画面対象の構成が一
致すれば、パターンは、画面対象の構成と一致するであ
ろう。もし一回転以上が可能であれば、探索ユーティリ
ティは、最小回転を選んで作業するであろう。「スケー
ル不変性Ｊ　（Ｓｃａ！ｅ　Ｉｎｖａｒｉａｎｃｅ）を
オンにした場合は、もし平行移動と拡大縮小のある組合
せによって、パターンと画面対象の構成が一致すれば、
パターンは画面対象の構成と一致するであろう。同様に
、「回転不変性」と「スケール不変性」を共にオンにし
た場合は、探索ユーティリティは平行移動、回転及び拡
大縮小の組合せを用いて、探索パターンを画面対象に一
致させようと試みるであろう。

ｒｉ性Ｊ　（Ｐｏｌａｒｉｔｙ）がオンの場合は、２つ
の曲線は、同じ向きに描かれている場合だけ、一致する
であろう。例えば、パターンが直線線分の場合、もし　
「回転不変性」突合せを実行すれば、パターンは、同じ
長さを有するあらゆる直線線分と一致するであろう。「
極性」″がオフのとき、１８０°だけ異なる２つの回転
を用いて、各突合せを行うことができる。「極性」がオ
ンのとき、探索ユーティリティは、各直線線分が描かれ
た方向を考慮し、そして探索パターンの線分と画面の線
分が合わさるような回転を選択するであろう。

実例として、３組のコツホ（Ｋｏｃｈ）雪片を作るため
に、第３図のユーザー制御可能探索パラメータを用いる
ことができる。最初に、第４八図に示すように、時計回
りに正三角形３１の直線線分を描いて、三角形３１を構
成する。次に、三角形３１の一辺を選んで、探索窓枠２
３に複写する。置換窓枠２４に、三角形３１を作るとき
用いた直線線分の１７３の長さの４本の直線線分を描く
。これらの直線線分を三角形３１の直線線分と同じ方向
（左下から右上へ）に描く。画面対象を置換したとき、
「ずれ」が生じないように、置換形状３２が探索線分３
３と同じ座標で始まり、同じ座標で終わるように十分に
注意する。第４Δ図は、得られた探索窓枠２３と置換窓
枠２４を示す。

ここで、上記の雪片を繰り返して構成するため、「細分
度」を゛線分°′にセットして、探索が元の三角形３１
の個々の線分を見付けることができるようにする。次に
「回転不変性」と「極性」をオンにする。次に、”ＣＨ
ＡＮＧＥＡＬＬ”を選択すると、元の三角形３１のすべ
ての直線線分が、第４Ｂ図に示すように、４線分経路で
置換される。もし“’ＣＨＡＮＧＥＡＬＬ′°を再び選
択しても、画面には探索ターンの線分と同じ長さの線分
がないので、何も起こらない。

しかし、「スケール不変性」をオンにして、ＣＨＡＮＧ
ＥＡＬＬ”を再び選択すれば、第４Ｂ図のすべての線分
が、４線分経路で置換され、第４Ｃ図が生じる。

１、Ｂ、２．　　図形スタイルの探索と置換図形対象の
形状以外の性質（すなわち、図形的性質）、例えば対象
類別（長方形、円、又は多角形）、曲線の種類（直線、
Ｂｅｚｉｅｒ、　Ｂスプライン、円錐曲線、又は弧）、
領域の色、線の性質（線の色）、ストローク幅、ダッシ
ュパターン、接続の融合、又はストローク端の形状）、
又はテキストの性質（＾ＳＣＩ［ストリング、フォント
ファミリ、又はフォント変換〉を探索したい場合がしば
しば起きる。同様に、ユーザーは、一致した対象の図形
的性質を置換することに興味を有するかも知れない。第
５図は、「探索」欄及び「置換」欄と呼ばれるユーザー
インタフェースの一部を示す。「探索」欄の黒色の正方
形は、画面の対象と一致し、突合せが成功しなければな
らない探索窓枠２３（第２八図）内の対象の性質を示す
。この場合、他の性質は無視することができる。「置換
」欄の黒色正方形は、置換を行ったとき、一致した対象
に付加される置換窓枠２４内の対象の図形的性質を示す
。

その他の性質は、特定の性質が間接的にそれらを変更さ
せない限り（例えば、形状を変えると、曲線のスタイル
が変わる）、そのままである。ユーザーは、マウス１４
（第１図）を用い、選択ボックス上でカチッと合わせる
ことによって、各図形的性質を選択したり、選択を解除
したりできる。

探索及び置換の図形的性質が適切に指定されると、本発
明の探索置換ユーティリティを使用し、色はそのままに
して、対象の形状を変更することができる。例えば、多
色雪片を作るため、第品図に示すように、前と同様な三
角形３１ａで開始し、その３つの辺に異なる色を付ける
ことができよう。もし「探索」欄の「線の色Ｊ　　（Ｌ
ｉｎｅ　Ｃｏ１ｏｒ）をオフすれば、３つのすべての辺
はなお探索パターンと一致するであろう。また、「置換
」欄の「線の色」をオフすれば、各辺が置換されるとき
、その色が、置換形状に付けられる。もし同じ探索窓枠
と置換窓枠を前と同様に使用すれば、２回の　”ＣＨＡ
ＮＧＥΔ１、Ｌ′の後、第６Ｂ図の絵が得られる。

探索置換ユーティリティは、形状をそのままにして、対
象の色を変更することが可能である。

１、Ｂ、３．　　拡張型探索機能と置換機能第３図に戻
ると、ユーザーは、文脈依存探索により、別の１組の形
状Ｂが存在としている状態で、１組の形状への出現を探
索することができる。八に一致する形状のみが選択され
、置換される資格を有する。文脈依存探索を行うため、
ユーザーは、あらゆるパターン形状Ａ、　Ｂを探索窓枠
２３（第２八図）に入れ、それらを選択することで、へ
の中にどの形状があるかを指示し、「文脈依存性Ｊ　（
Ｃｏｎｔｅｘｔ　５ｅｎｓｉｔｉｖｉｔｙ）をオンして
、探索を開始する。

文脈依存性探索は、置換される資格を有する形状セット
を減らすことで、一定のパターン指定に存在する「あい
まいさ」を除くことができる。例えば、「置換」欄の「
形状」がオンで、「線の色」がオフであれば、探索置換
プロセスは、一致した形状を置換形状で置き換えて、一
致した形状の線の色を置換形状へ複写しなければならな
い。もし探索パターンが幾つかの異なる線の色を有する
１組の形状と一致すれは、置換パターンのどの対象が探
索パターンの１組の形状からどの線の色を受は取るべき
かはっきりしないので、問題が生じる。

この問題を解決するため、ユーザーは、各文脈依存探索
が１つの「線の色」の対象のみを選ぶことができるよう
に、探索を幾つかの文脈性探索に分割することができる
。

第７八図〜第７Ｄ図は、文脈依存性探索の別の使用例を
示す。ユーザーはソフトボールを含むゴム製ボールマシ
ンの絵から出発して（第７八図）、ソフトボールをフッ
トボールで置き換える（第７Ｂ図）。

各フットボールは、ソフトボールの縫い目の方向からそ
の向きを引用し、同様に、ソフトボールからその面の色
とその縫い目の線の色を引用するであろう。縫い目の線
の色と外円の線の色は、１個１個ののソフトボールで違
っているから、この置換のすべてを一度に実行すること
ができない。代わりに、ユーザーは、第７Ｂ図に示すよ
うな所望の結果が得られるように、第７Ｃ図に示す文脈
依存探索置換操作と、第７Ｄ図に示す通常の探索置換操
作を行う。最初の操作（第７Ｃ図）は、円（ソフトボー
ルの縫い目が存在する状態で）を適当な向き、領域の色
及び線の色のフットボールで置換する。

第２の操作（第７Ｄ図）は、ソフトボールの縫い目を適
当な線の色のフットボールの縫い目で置換する。

いろいろな許容誤差（Ｔｏｌｅｒａｎｃｅ）　（第３図
）を用いて、ユーザーは、探索パターンに、厳密ではな
いが、近似的に一致する形状を見付けることができる。

一致が識別されたとき、ユーザーは、ソフトウェアスラ
イダ又は同等なもの（図示せず）を調節することにより
、突合せアルゴリズムが許容する誤差量を増減できる。

例えば、適当な許容誤差と探索パターンを用いて、円に
近いすべての形状、あるいは直線に近いすべての形状を
突き合わすことができる。適当な許容誤差は、一般に、
試行錯誤によって決められるので、この機能をうまく利
用するため、ユーザーは形状突合せのメカニズムをある
程度詳しく理解しなければならない。

１、Ｂ、４．　　図形探索と図形マクロ図形探索を用い
て図形の形状を見付けたら、次の３つのアクション′を
取ることができる。詳細には、１）一致した形状を新し
い形状で置換することができる。２）一致した形状を編
集するため、制御をユーザーへ引き渡すことができる。

３）探索を始める前に、ユーザーが指定した１組の編集
操作を実行することができる。この最後のアクションに
は、いわゆる“図形マクロ″′が必要である。

ユーザーは、置換窓枠２４（第２八図）内で描画操作を
行って、マクロを記録する。同時にすべてのマウスの座
標とボタン操作音が記録される。次に、ユーザーは探索
置換ユーティリティに、置換の代わりに、マクロを実行
することを命令し、置換操作の１．っ、例えば、ＣＨ＾
ＮＧＥＡＬＬを呼び出す。マクロの実行中に一致が見付
かったときは、探索置換ユーティリティは記録された動
作をプレイバックし、そしてもし置換が実行されていた
ならば、置換対象へ適用されたであろう同じ変換を用い
てマウス座標を変換する。期待しない結果を防止するた
め、マクロ命令は、一致した対象についてのみ作用する
ように限定される。

簡単な置換では困難な論理的変更を実行するため、図形
マクロを使用することができる。例えば、一致した対象
を複写し、コピーグレーを着色し、一致した対象からコ
ピーをオフセットし、元の一致した対象の下にコピーを
移動させるマクロを記録することによって、１組の対象
に、゛′ドロップシャドウ″を与えることができる。

■、探索と置換の基礎 この節は、図形合成画面が何を意味するかをより明確に
説明し、探索をどのように実行するかを説明し、適当に
修正した上から下、左から右の探索順序を説明し、曲線
の数学的表現とそれらが探索プロセスにどのように作用
するかを説明し、曲線形状の厳密な突合せと、厳密でな
い突合せとの相違を説明し、形状の置換と図形的性質の
置換との相違を説明する。

■、＾９合成図形画面 以下に説明する図形探索置換アルゴリズムは、合成図形
画面内の図形対象を探索するためのものである。詳しく
述べると、画面は、１組の合成図形対象で構成すること
ができる。合成図形対象は１組のばらばらの曲線で構成
され、曲線は１組の順序付き線分で構成される。

例えば、第８八図は、輪郭と呼ばれる一種の図形対象を
示す。輪郭は、フェンスと呼ばれる外側の曲線４１と、
ゼロ又は１個以上の穴と呼ばれる内側の曲線４２で構成
されている。もしフェンス４１がそれ自体閉じていなけ
れば（すなわち、２つの区別できる端を有していれば）
、輪郭は穴４２を持たないであろう。図かられかるよう
に、第８八図の輪郭は２つの曲線、すなわち１個のフェ
ンス４１と１個の穴４２から成っている１曲線は接続さ
れた１つの曲がった線である。直観的には、曲線は、ペ
ンを紙から持ち上げずに描くことができる種類の曲がっ
た線である。多くのディジタルピクチャ装置では、曲線
は、数学的に「線分」と呼ばれる一連の順序付き小部分
で表される。各小部分は、普通の数学的形式を有する。

例えば、第８Ａ図の輪郭のフェンス４１は３つの線分、
すなわち第８Ｂ図のように、弧４３、直線４４及びパラ
メトリック三次曲線４５から成っている。同様に、穴４
２は、第８Ｃ図のように、２つの弧４６，４７で表され
る。

輪郭は、図形探索置換を用いて、見付けることができる
種類の図形対象の一例に過ぎない。一般に、開示の目的
で、図形対象は、それらがフェンスや穴と思われるか否
かに関係なく、あらゆる曲線の集まりであってもよい。

ここでは、曲線の集まりと考える場合は、図形対象を、
クラスタ又は単に対象と呼ぶ。

Ｉ［、Ｂ、　　細分度（Ｇｒａｎｕｌａｒｉｔｙ）ユー
ザーは、探索パターン内で対象を見付は出すために、探
索プロセスに、図形画面をどの程度に分けてもよいかか
を指定できる。詳細には、ユーザーは、クラスタレベル
、曲線レベル、又は線分レベルで探索することができる
。

クラスタレベルで探索する場合は、画面内のクラスタを
、そっくりそのまま突き合わすことができるだけである
。例えば、もし第８Ａ図の輪郭がシ画面内に存在し、「
回転不変性」と「スケール不変性」をオンにして、探索
を実行した場合には、第８Ｄ図の探索パターンは画面の
輪郭と一致するであろう、しかし、第８Ｅ図と第８Ｆ図
の探索パターンは、第８Ａ図の輪郭の一部を含むだけで
あるから、一致しない。

しかし、曲線レベルで探索する場合は、画面内の曲線を
そっくりそのまま突き合わすことができるだけである。

しかし、この場合の探索は、各回６一 線が属するクラスタに注意を払わない。このレベルでは
、第８Ｄ図の探索パターンは、第８八図の輪郭の２つの
曲線と一致する。同様に、第８Ｅ図は、第８八図の輪郭
の外側曲線と一致する。しかし、第８Ｆ図の探索パター
ンは、第８′八図の曲線の１つの一部分を表しているだ
けであるから、依然として突合せに失敗するであろう。

最後に、線分レベルでは、第８Ｄ図〜第８Ｆ図のすべて
の探索パターンが第８八図の輪郭（全部又は−部）と一
致するであろう。詳しく述べると、第８Ｄ図の探索パタ
ーンは第８Δ図の輪郭全体と一致し、第８Ｅ図の探索パ
ターンは輪郭の外側曲線と一致し、第８Ｆ図の探索パタ
ーンは輪郭の外側曲線の２つの線分と一致する。

ユーザーが探索のため３つの粒状度のどれを選択したか
に応じて、探索置換ユーティリティは、形状を比較する
ためのさまざまなデータ構造を作る。一般に、データ構
造は、曲線レベル探索の場合よりもクラスタレベル探索
の場合のほうが簡単・であり、線分レベル探索の場合よ
りも曲線レベル探索の場合のほうが簡単である。もちろ
ん、簡単なデータ構造を用いたほうが、探索が速・く行
われる。次に、これらのデータ構造と、その・構１成に
ついてさ、らに検討する。

便宜上、ここで使用する表記式“細分度・クラスタ′″
は、ユーザーがクラスタレベルで探索していることを示
し、゛′細分度−・曲線レベル′°は、ユーザ、−が曲
線レベルで探索していることを示し、゛細分度・線分°
゛は、ユーザーが線分レベルで探索し、ていることを示
す。

［、Ｃ，境界ボックス（ＢｏｕｎｄｉｎｇＢｏｘ）探索
開始前に、探索ツールは、画面内の各曲線又は各曲線グ
ループについで、（１）水平の辺と垂直の辺を有し、（
２）特定の画面曲線または曲線グループを完全に含み、
（３）前記条件（１）と（２）を満たす最小長方形であ
る長方形を計算する。

これらの長方形は、境界ポック・スと呼ばれ、曲線を探
索する順序を決定し、かつあらかじめ定義した変換の下
で与えられた探索曲線と一致する可能性のない曲線を迅
速に除外するために使用される。

ＩＩ　、Ｄ、　　探索順序 通常、ユーザーが順方向探索を要求したときは、画面は
上から下、左から右へ探索され、逆゛方向探索を要求し
たときは、下から上、右から左へ探索される。しかし、
この規則には、２つの重要な例外がある。

ｎ　、Ｄ、１．　　例外１：　先導対象以下に詳しく説
明するように、探索プロセスは、探索パターンのクラス
タ又は曲線の１つを先導対象に選ぶ・。探索の・とき、
先導対象は、Ｍ密に上がら下、左から右の順序で、画面
対−象と比較され°る。

しかし、もし探索パターンが先導対象のほかに、１つ又
はそれ以上の対象を含んでおり、そして探索操作を繰“
り返して実行すれば、前の探索操作′の゛とき一致した
１組の画面対象よりも蝋の上部□の近くにその境界ボッ
クスがある１組の画面対象は、１線゛索操作で突き合わ
せることができる。言い換えると、たとえ傾向が全体と
して上から下であっても、一連の一致は、ある時には下
から上の方向に動くように見えることがある。

第９＾図〜第９Ｃ図は、そのような１つの事例を示す。

詳しく述べると、第９＾図は「回転不変性」探索におい
て使用される探索パターンを示す。第９Ｂ図は最初の一
致が見付かった図形画面を示す。−致した対象は、それ
らの隅に黒色正方形を付けて目立つよ６うにしである。

第９Ｃ図は第２の一致が見付、かった同じ図・彩画面を
示す。探索パターンの先導対象、すなわち第９Ａ図の３
線分曲線４８は、第９Ｂ図の対象より低い第９Ｃ，図の
対象と一致す□るが・、全体と・して見ると、第９Ｃ図
の一致がより高いことに留意されたい。通常の上から下
、左から右の探索順序に対するこの例外は、比較的簡単
な探索戦略を可能にするので、許゛容される。

ｎ　、Ｄ、２．　　例外２：　曲線内の順序付は曲線内
の線分は、もしペンを紙から持ち上げずに措かれたなら
°ば有するであろう時間的な順序で決まる自然の順序を
有゛している。したがっで、探索パターンの先導対象め
線分を画面曲線の線分と比較す−ると、画面曲線の線分
は、厳密な上から下パの順序でなくミこの自然の順序で
検討される。

第１０八図〜第１０Ｂ図は、上がら下の探索規則に対す
るこの例外を設けた１つの動機を示す。第１０＾図は、
１２０°の角度をなしている２つの線分４９゜５０から
成る探索パターンを示す。第１０Ｂ図は、すべての線分
が１２０°の角度で結合している２個の曲線を示す。し
たがって、□第１０八図の探索パターンは、「回転不変
性」がオンであれば、第１０Ｂ図の隣り合う□任意の一
対の線分と一致するであろう。しかし、探索規則は、与
えられた線分を一度だけ一致することができると規定し
ているので、探索順序は、実際に、どの隣り合う線分対
が一致するかを判断する。もし厳密な上から下の規則に
従ったな−らば、第１０Ｂ図の線分対５１．５２が、最
初に一致し、次に線分対５３．５４が一致し、次に線分
対５６．５７が一致したであろう。言い換えると、プロ
セスは、右側の曲線に関しては２回一致するが、左側の
曲線に関しては１回一致するだけである。

対照的に、もし線分が自然の順序で一致すれば、プロセ
スは、線分対５１，５２、次に線分対５６．５７、次に
線分対５８，５３、次に線分対５４．５９と一致するで
あろう。

自然の線分順序を用いる動機はもう１つある。

もし各置換を行った後に、・モニター１３（第１図）を
更新すれば、一般に、各置換が行われる領域が見えるよ
うに、モニターの図形画面の位置を変える必要があろう
。もし位置を変えるならば゛、自然の線分順序を使用す
れば、・図形画面全体の位置を変えなければならない回
数を減らすことができる。

これにより、ユーザーの目の負担が減り、計算時間も短
かくなる。

ユーザーが、成功した順方向（上から下）探索のすぐ後
に逆方向（下から上〉探索を要求し、そして前の探索が
先頭曲線と画面曲線の中間の線分とを突き合わせたなら
ば、探索プロセスは、順方向探索において最も新しく突
き合わせした画面曲線の線分から逆方向探索を開始し、
後向きに進行するであろう。例えば、第１０Ｂ図におい
て、もしプロセスが線分５４．５９を突き合わせたばか
りであれば、プロセスは逆に進行して、線分５８．５３
を突き合わせるであろう。この結果、第２の逆方向探索
は、線分５６．５７を見付は出すであろう。以下同様で
ある。

上から下の規則に対するこの自然順序例外は、探索アル
ゴリズムを複雑にする、が、直観的に予想される結果が
得られる。

Ｉ［、、Ｅ、　　キャリラド記号による部分画面探索前
に言及したガーゴイル（Ｇａｒｇｏｙ　Ｉ　ｅ　）イラ
スト装置のソフトウェアカーソル（キャリラドと呼ばれ
る）をユーザーが手で挿入し、次に順方向探索操作を開
始すると、キャリラドの下に境界ボッダスが完全に入る
クラスタ（又は、探索の細分度によっては、曲Ｍ）だけ
が、突合せのため選ばれる資格を有する。対、照的に、
キャリラドを挿入し、次に逆方向探索を開始すれば、キ
ャリラドの上に境界ボックスの上部があるクラスタ又は
曲線だけが、・突合せのため選ばれる資格を有する。こ
の規則のわずかな不対称によ、って、もしキャリラドを
決められた位置（ｘｏ、ｙｏ）に挿入ル、一致が、それ
以上発見されなくなるまで順方向探索を実行し、次にキ
・ヤリットを同じ位１ｆ（ｘｏ、ｙｏ）に挿入し、一致
がそれ以上発見されなくなるまで逆方向探索を実行すれ
ば、画面内のすべての一致が確実に発見されるであろう
。

各々の一致が発見された後、キャリラドは、探索パター
ンの先導対象と一致した画面対象の境界ボックスの左上
隅へ動かされる。したがって、探室操作が行われるたび
に発見される一致は、常に、探索方向にキャリラドの向
こう側での最初の一致である（上に述べた探索順序規則
の例外を前提として）。

Ｉ［、、Ｆ、　　曲線タイプ すべての合成図・形編集装置は、・曲線を内部では数学
的に表現する。通常、数学的記述では、単一曲線は、そ
れぞれが数学的に簡単な一連の湾曲線分（小部分）で表
される。例えば、第１１Ａ図と第１１Ｂ図は、円弧、直
線線分及びＢｅｚｉｅｒ三次曲眸の三次曲率部分で表わ
した曲線を示す。しかし、この表現は、必ずしも唯一で
はない。例え、ば、第１１Ｃ図は、第１１八図の曲線の
別の表現である。この第２の表現は、３個の円弧、縮退
Ｂｅｚｉｅｒ三次曲線と、三次Ｂスプライン曲線から成
っている。

第１１八図と第１１Ｃ図の曲線は、厳密に同じ形状を有
するが、表現は非常に異なる。

ユーザーが［曲線タイプＪ探索パラメータ（第５図）を
活動化すると、探索プロセスは、同じ数学的表現を持つ
曲線同士の突合せのみを許す。例えば、「スケール不変
性」、「回転不変性」及び「曲線タイプ」のすべてを活
動化して実行した探索では、第１１八図の曲線は、第１
１Ｂ図の曲線と一致するが、第１１．Ｃ図とは一致しな
い。実際には、もし「曲線タイプ」探索パラメータがオ
ンで、「形状」探索パラメータがオフであれば、小部分
の実際の形状に関係なく、第１１八図の曲線は、円弧、
直線、及び三次曲線から成るすべての曲線と一致するで
あろう。

対照的に、１曲線タイプ」探索パラメータがオフで、「
形状」探索パラメータがオンであれば、第１１八図の探
索パターンは、第１１Ｂ図の曲線とも、第１１Ｃ図の曲
線とも一致するであろう。次に、２つの曲線が、それら
の数学的表現に関係なく、同一形状を有するか否かを判
断するアルゴリズムについて述べる。

＋１．に、　　厳密でない突合せ 探索プロセスは、通常、探索パターン内の対象と正確に
同一形状を有する図形対象を見付は出すために使用され
る（浮動小数点計算の誤差を見込んで、形状の多少の差
は許される）。ユーザーは、この種の突合せを要求する
ため、「厳密」（Ｅｘａｃｔ）オプション（第３図）を
活動化する。しかし、時には、探索パターンとほとんど
同一形状の対象を探索することが有用なことがある。例
えば、ユーザーは、第１２八図の円のような円を見付は
出すために、第１２Ｂ図の円のような近似的に円の形状
をスケッチし、そのスケッチと近似的には同一であるが
、厳密には同一でない形状を探索することができるであ
ろう。これは、「厳密」オプションをオフにし、そして
許容誤差値（ゼロがら無限大までの実数）を選択するこ
とで行われる。許容誤差値を大きくすればするほど、探
索プロセスにおいて、探索パターンと画面内の決められ
た対象とが一致することが多くなるであろう。許容誤差
値が大き過ぎると、画面内のすべての対象が一致するこ
とは言うまでもない。以下説明する曲線突合せアルゴリ
ズムの１つは、厳密でない突合せを考慮している。

ＩＩ　、Ｈ，図形の形状及び性質の置換前に指摘したよ
うに、探索置換操作を使用して、対象の色のみ、対象の
形状のみ、又は対象の幾何学的特徴と図形的性質の組合
せを変更することができる。これは、置換操作の終った
後図形画面に現れる最終の形状を作るために、置換アル
ゴリズムが一致した対象の形状及び性質と、置換パター
ンとを組み合わせることができなければならないことを
意味する。例えば、第１３八図は、探索パターン（図示
せず）が画面内の三角形６０＾と一致した場合を示す。

置換パターン６０Ｂとして、ユーザーは厚い境界線を有
する灰色の正方形を描いた。

「置換Ｊ　＠６ｏｃは、形状を置換すべきこと、しかし
領域の色と線の幅を置換すべきでないことを指示してい
る。したがって、合成された対象６００を作るためには
、置換アルゴリズムは、置換パターン６０Ｂから形状を
取り（矢印で強調しである）、その形状に、一致した対
象（三角形）６０＾の領域の色と線の幅を組み合わせな
ければならない。別の例である第１３Ｂ図を参照すると
、合成された形状は非常に異なるやり方で作られること
がわかるであろう。同様に、探索により三角形６０＾が
一致した。置換パターン６０Ｂは、厚い境界線を有する
灰色の正方形である。しかし、「置換」欄６０Ｅは、形
状をそのままにし、領域の色と線の幅を置換すべきこと
を指示している。したがって、合成された対象６０Ｆを
作るために、置換アルゴリズムは、一致した対象６〇八
から形状を取り（矢印で強調しである）、この形状に、
置換パターン６０Ｂの領域の色と線の幅を付ける。さら
に別の組合せも可能であることは理解されよう。例えば
、「置換」欄内の形状、領域の色、及び線の幅はオンに
するのが通例である。この場合には、形状とその他の図
形的性質は、置換パターンから引き継がれる。

都合の悪いことに、同じ性質に複数の値を有する対象か
ら図形的性質を移す場合は、置換操作はいく通りにも解
釈できる。例えば、第１４図は、第１３Ｂ図に類似した
場合を示す。同様に、探索により、三角形６０Δが一致
した。「置換」欄６０Ｅは、形状を保持し、しかし領域
の色と線の幅を置換パターン６０Ｇから取るべきことを
指示している。都合の悪いことに、置換パターン８０Ｇ
はいくつかの線幅を有しているので、三角形６０Δのど
の辺がどの線幅を受は取るべきかがあいまいである。こ
の状況が起きると、三角形６０Ｈて示すように、置換操
作はいく通りにも解釈されるので、置換は行われず、エ
ラー発生がユーザーに告げられる。

■１曲線の突合せ、 本発明の図形探索プロセスの最小レベルのルーチンは、
２つの曲線を比較して、同じ形状であるか否かを判断す
るルーチンである。２つの曲線の比較は、曲線の突合せ
と呼ばれる。本節では、この曲線の突合せのアルゴリズ
ムについて述べる。

図形パターンは、一般に、多くの曲線を有しており、ま
た形状以外の図形性質、例えば色や、線の幅を記述して
いるので、サブルーチンとして曲線突合せに基礎をおく
他目的の探索プロセスが具体化されている。このより包
括的な機能については、次節で説明する。

好ましい曲線突合せアルゴリズムは、２つの手法に基づ
いてその能率を高めている。すなわち（１）迅速除外チ
エツク、、、、、２つの曲線の詳しく比較する前に、幾
つかの迅速テストを行って、曲線が明らかに同一形状で
ないかどうかを判断する。これらの迅速テストをパスし
た場合だけ、２つの形状が詳しく比較される。

（２）基準形０００１１画面内の各曲線及び探索パター
ン内の各曲線の形状は、“基準形″と呼ばれる標準形式
で表わされる。もし「回転不変性」探索を行えば、最初
に形状をどのように回転したかに関係なく、この基準形
は同じである。また「スケール不変性」探索を行えば、
最初に形状をどのように拡大縮小したかに関係なく、こ
の基準形は同じである。基準形さえ計算すれば、曲線同
士を比較することが可能であり、曲線を回転させたり、
拡大縮小したりする計算は不要である。たとえ特定の変
換が探索曲線を画面曲線にマツプするかどうかを判断す
る必要があるときでも、探索曲線の２点について変換を
適用して、その変換で一致が生じるかどうかを判断する
だけで済み、探索曲線全体を変換する必要がない。また
、探索プロセスの開始時に、曲線全体の基準形を一回計
算するだけでよい。

曲線突合せ問題には、２つの手法を採用した。

「構造ベース曲線突合せ」と呼ばれる第１の手法におい
ては、２つの曲線を、同しタイプの同じ数の線分で作っ
て突き合わせなければならない。

これに対して、「折れ線ペース曲線突合せ」と呼ばれる
第２の手法は、たとえ２つの曲線が異なる数の線分、異
なるタイプの線分、又はこの両方で表現されていても、
２つの曲線が同一形状を有することを見付けることが可
能である。この制約のない突合せ能力を得るために、各
曲線を、それらの表現形式によらずに、形状のみによっ
て決まる「折れ線」と呼ばれる表現に変換する。その後
、２つの曲線の折れ線を比較して、一致が生じるかどう
を判断する。

■、＾２曲線突合せ それぞれが一連の線分で表された２つの曲線が与えられ
たとして、突合せの目標は、２つの曲線を比較して同一
表現かどうか、又は同一形状かどうか、又は同一表現か
つ同一形状かどうかを判断することである。２つの表現
を突き合わせなければならない場合は、構造ベース曲線
突合せが好ましい。もしそうでなければ、折れ線ベース
突合せがより好ましい。本節は、最初に、構造ベース曲
線突合せと折れ線ベース曲線突合せをどのように行うか
を説明し、次に探索パターン曲線から突合せ用画面曲線
への変換をどのように見付けるかを説明する。最後に、
特定のアフィン変換（すなわち、平行移動、回転、及び
拡大縮小の操作を組み合わせて、２つの曲線を一致させ
ることが目的の場合に、曲線突合せアルゴリズムをどの
ように修正するかについて説明する。

■、＾、１．構造ベース曲線突合せ 一般に、曲線の数学的表現は、各曲線線分の形状を、２
以上の点の位置で表す。第１５図は、第１１八図の曲線
を示し、各線分の制御点を黒色正方形で示しである。図
かられかるように、弧は、制御点６１，６２．６３を通
過し、点６１と６３で終わる唯一の円弧として定義され
る。直線線分は、制御点６３゜６４を通過する唯一の直
線線分である。Ｂｅｚ’ｉ　ｅｒ三次曲線は制御点６４
と６５で終わり、制御点６４〜６７によって決まる形状
を有する。

２つの曲線の構造ベース比較を実行する場合は、最初に
、２つの曲線が同じ数の線分を含んでいるかどうかを判
断する。もし含んでいなければ、突合せは、その場で失
敗する。もし曲線が同じ数ｎの線分を含んでいれば、プ
ロセスは、第１の曲線のｉ番目の線分のタイプと第２の
曲線のｉ番目の線分のタイプを比較する。ここで、ｉは
１〜ｎである。もしそれらの比較のどれかで、線分のタ
イプが異なることが発見されれば、曲線の比較はその場
で失敗する。もし線分のタイプが同一であれば、次に、
２つの曲線の形状を比較する必要がある。

「平行移動」と「回転」又は「拡大縮小」によって、形
状の異なる曲線を発見できることが望ましいので、回転
と拡大縮小の効果を分析できる必要がある。それには、
各曲線について、その位置、向き、及び相対サイズが異
なる第２の表現を計算する必要がある。この新しい表現
を計算するため、曲線の元の数学的表現を以下のように
修正する。

最初に、曲線の最小番号の制御点く例えば、第１６八図
の始点６１）を見付ける。次に、第１６８図に示すよう
に、この点が原点（ｘ＝Ｏ９ｙ・０）にくるように、曲
線を平行移動する。また、「回転不変性」探索を行う場
合は、最小番号の制御点から最も離れた遠点と呼ばれる
制御点６７を見付ける。次に、遠点６７が正のＸ軸（第
１６Ｃ図に示すように、原点を通る水平線の右側）上に
くるまで、曲線を原点のまわりに回転する。あるいは、
「スケール不変性」探索を行う場合は、最初に、第１６
Ｂ図のように、曲線を平行移動し、次に、第１６０図の
ように、遠点６７が原点から１．０単位の距離にくるま
で、原点のまわりに曲線を拡大又は縮小する。探索が「
スケール不変性」と「回転不変性」の両方の場合は、第
１６Ｅ図に示すように、第１６ｄ図の回転操作と第１６
０図の拡大縮小操作を実行する。

上記のプロセスで計算した曲線は、元の曲線の゛構造ベ
ース基準形″と呼ばれる。２つの曲線のそれぞれについ
て、構造ベース基準形を計算したら、それらの基準形を
比較することにより、２つの曲線を比較することができ
る。基準形の比較を行う場合は、最初に、２つの基準形
が同じ数ｐの制御点を有するかどうかを判断する。もし
同じでなければ、比較はその時点で失敗する。もし同じ
であれば、第１の基準形のｉ番目の制御点の位置と第２
の基準形のｉ番目の制御点を比較する。

ここで、ｉは、１〜ｐである。もし各対の制御点が同じ
位置く数値の不正確さを見越して）を有すれば、曲線は
一致すると言える。もし同じ位置を有しなければ、比較
は失敗する。

■、＾、２．折れ線ベース曲線突合せ ２つの曲線の折れ線ベース゛比較は、各曲線を「折れ線
」と呼ばれる不連続直線経路で近似する必要がある。折
れ線近似形は、曲線に応じて構成され、高い曲率の領域
は平らな領域よりも多くの直線線分で表現される。しか
し、折れ線の線分の数が多過ぎないように、折れ線の線
分を、少なくとも所定の最小長さに制限することが好ま
しい。

この種のベクトル化は、曲線をコンピュータデイスプレ
ィに表示する普通の操作であるから、既に多くの図形処
理装置で行われている。第１７図に示すように、曲線を
異なるスケールでコピーした場合の折れ線は、相互の縮
尺でないことがある。画質テストは、後で詳しく説明す
るように、この誤差を考慮しなければならない。

第１８八図に示した折れ線は、迅速に比較できるように
基準形に変換されている。その基準形の性質は、第１８
Ｂ図〜第１８０図にそれぞれ示すように、突合せが「回
転不変性」、「スケール不変性」、そのいずれでもない
、又はその両方かどうかによって決まる。折れ線のある
点を始点に選ぶ。開曲線の場合には、最初の端点を用い
る。閉曲線の場合は、曲線に沿って延びている−様な密
度／単位長さの「等価電線」の質量中心から最も遠い距
離にある点を用いる（第１８八図）。もちろん、閉曲線
は質量中心から最も遠い点を幾つか有することがあるが
、その場合には、曲線は幾つかの基準位置を有するであ
ろう。折れ線（第１８Ａ図）を、その始点が原点にくる
ように変換する（第１８Ｂ図）。もし「回転不変性」突
合せを選べば、質量中心が正のＸ軸上にくるように、折
れ線を回転する（第１８Ｃ図）。

もし「スケール不変性」突合せを選べば、曲線の折れ線
を、単位弧長を有するように正規化する（第１８Ｄ図）
。もし探索が「回転不変性」と「スケール不変性」の両
方であれば、最後の２つの操作を組み合わせる（図示せ
ず）。

ここて、明白に一致しない対の曲線については、それ以
上の計算を避けるために、折れ線について、１組の迅速
除外テストを適用することができる。

弧長、曲線からその質量中心までの最大距離、始点に対
する質量中心の位置を含む、幾つかの量を迅速に比較す
ることによって、上記の判断を行うことができる。もし
２つの折れ線の上記の値が最小値以上に相違すれば（計
算の不正確さ又は量子化の差のせいである）、それ以上
の計算をせず、曲線は一致しないと結論する。

もし迅速除外テストにより、２つの与えられた折れ線へ
とＢが同等な形状を表すことができると認められたなら
ば、さらに広範な比較をする必要がある。このため、折
れ線＾の各頂点Ｖがその始点からどれくらい遠いがを、
折れ線へに沿って測定する。この測定した距、離をＷと
する。

次に、折れ線Ｂの始点がら始めて、折れ線Ｂに沿って距
離Ｗだけ進んだ点ｐを一意的に識別する（点ｐは、、折
れ線Ｂの直線線分の中間にあることもある）。次に、頂
点Ｖがら点ｐまでの距離を計算する。もし折れ線＾上の
どれかの頂点について、上記の距離が一定のしきい値を
越えれば、突合せは失敗である。ユーザー指定突合せ誤
差を反映させるため、迅速除外テストに用いた諸量のほ
かに、このしきい値を調整することができる。次に、折
れ線へと折れ線Ｂの役割を替えて、上記の比較的厳密な
比較プロセスを繰り返す。この結果、もし折れ線、への
すべての頂点が、許容基準で決められた範囲内で折れ線
Ｂの近くにあり、かつ折れ線Ｂの頂点が、同じ基準で、
折れ線への近くにあれば、突合せは成功する。もし近く
になければ、突合せは失、敗する。第１９図は、上の述
べた比較プロセスを示す。図かられかるように、折れ線
への各頂点は、折れ線Ｂに沿って同じ弧長の点まで短い
線分で結んで可視化することができる。同様に、折れ線
Ｂの各頂点は、折れ線＾に沿って同じ、弧長の点まで短
い線分で結んで可視化することができる。距離ｄｌ’＋
４２＋１１．（Ｌは、折れ線ベース比較アルゴリズムで
計算する。次に各距離ｄｉを調べて、ユーザー指定許容
しきい値以下であることを確かめる。

上記の距離比較テストは、迅速除外テストと共に、厳密
な突合せ基準を定めていることに留意されたい。厳密で
ない突合せの場合は、距離比較テストで等しいとしてパ
スした曲線が、最初の迅速除外テストの少なくとも１つ
に失敗して、等しくないとみなされる可能性もある。

２つの閉曲線を距離比較テストで比較する場合には、弧
長テスト又は質量中心までの最大吐離テストが下記の比
較をする必要がない旨を指示しない限り、不一致を宣言
する前に、一方の曲線のすべての基準向きと他方の曲線
の１つの基準向きと比較しなければならない。折れ線ベ
ース突合せアルゴリズムは、すべての開曲線や一部の閉
曲線に対する折れ線のサンプル数ｎに複雑さが比例する
が、Ｏ（ｎ　２）にスローダウンするある、種の形状が
存在する。曲線突合せアルゴリズムの複雑さに基づくこ
の上限を改善するため、曲線の図心からの距離のサンプ
リング（Ｈ，Ｆｒｅｅｍａｎ、５ｈａｐｅ　Ｄｅｓｃｒ
ｉｐｔｉｏｎ　Ｖｉａ　ｔｈｅ　Ｕｓｅ　ｏｆ　Ｉｎ１
ｔｉａｌ　、Ｐｏ１ｎｔｓ、”Ｐａｔ−ｔｅｒｎ　Ｒｅ
ｃｏｇｎｉｔｉｏｎ、Ｖｏｌ、１０．　Ｎｏ、３．１９
７８．　ｐｐ、１５９〜１６６参照）、又は曲率のサン
プリング（Ｈ，１ｌｌｏｌｆ　ｓｏｎ　ｔ“Ｏｎ　Ｃｕ
ｒｖｅ　Ｍａｔｃｈ、ｉｎｇ、”Ｔｅｃｈｎｉｃａｌ　
Ｒｅｐｏｒｔ　Ｎｏ。

５〇− ２５６　　Ｃｏｕｒａｎｔ　　Ｔｎｓｔｉｔｕｔｅ　ｏ
ｆ　Ｍａｔｈｅｍａｔｉｃａｌ　　５ｃｉｅｎｃｅｓ、
　Ｎ、Ｙ’、、’Ｎｏｖｅｍｂｅｒ　１９８’６参照）
など、別の表現を用いることができる。

第２０八図と第２０−８図は、たとえ曲線の表現が相違
していても、折れ線ベース突合せアルゴリズムが一致す
る曲線をどのようにして見付けるかを示す。

第２０八図の左側にある曲線は、第２０Ｂ図の左側にあ
る曲線とは表現が相違する。しかし、両図の右側に示す
ように、左側の曲線から作られた折れ線は、はとんど同
じ点を通過する。したがって、距離比較テス１〜は、形
状の一致を見付けるであろう。

■、＾、３．突合せ変換の計算 この時点で、構造ベース突合せアルゴリズム又は折れ線
ベース突合せアルゴリズムを使用する場合、アフィン変
換、例えば平行移動（始点を原点に合わせるため）、回
転（曲線をその基準向きの１つに置くため）、及び拡大
縮小（曲線を基準サイズへ拡大又は縮小するため）を使
用して、各曲線の１以上の基準形が導かれることは理解
されたであろう。元の曲線をその基準形の上にマツプす
るアフィン変換を計算するとき使用するため、これらの
変換及び実行する順序はすべて記録される。

このアフィン変換は、後で使用する基準形を用いて保存
される。

２つの曲線ＧとＨが実際に一致すると判断したら、曲線
Ｈを曲線Ｇにする変換を次のように計算することができ
る。もし曲線Ｈが曲ｉＧに一致すれば、曲線Ｈのある基
準形（Ｂと呼ぶ）は、曲線Ｇのある基準形（八と呼ぶ）
と一致する。■をＢにする変換及びＧを八にする変換は
知られているから、これら２つの変換を用いて、曲線Ｈ
を曲線Ｇにする変換を計算することができる。ＨからＧ
への変換計算には、ＨからＢへの変換の順方向の適用と
、Ｇから八への変換の逆方向の適用が必要であることは
理解されよう。

■、八へ４９条件付き探索 次に詳しく説明するように、探索パターン内の対象の１
つ（先導対象）について、一致を発見したら、探索プロ
セスは、先導探索対象を、それに一致する画面対象にす
る変換Ｔを計算する。この変換Ｔは、節■、Δ、３．で
述べた方法で求める。

次に、探索プロセスは、同じ変換Ｔを使用して、探索パ
ターン内の他のすべての曲線を画面曲線に一致させるこ
とができるかを知ろうと試みる。言い換えると、探索パ
ターン内の他の曲線の１つ、■と一致させるために、変
換ＴがＨをＧにするような画面曲線Ｇを見付ける必要が
ある。

変換Ｔで特定の探索曲線Ｈを特定の画面曲線Ｇの上にマ
ツプできるかどうかを判断するために、まず、上記の曲
線突合せアルゴリズムを用いることが好ましい。もしこ
れらの曲線突合せアルゴリズムを用いて、ＧとＨが一致
しないと結論されたならば、曲線Ｇと■は、変換Ｔの下
で一致せず、突合せは失敗する。しかし、これらのアル
ゴリズムに基づいて、Ｇと■が一致すれば、以下の追加
テストを行う。

各曲線Ｈ上の異なる２点、例えば始点とその始点から最
も遠い点を選ぶ。次にこれらの２点に対して、変換Ｔを
適用する。続いて、変換されたＨの始点と６の始点を比
較し、そしてＨの変換された最遠点とＧの最遠点を比較
する。

もし比較した点が各ケースについてほぼ同じであれば、
突合せは成功する。もしそうでなければ、突合せは失敗
する。探索パターンの形状と傾斜したそれ自身の変形と
を比較することができるように、探索プロセスを拡張す
る場合には、上記の２点の代わりに、■の異なる３点を
変換して、比較する必要があることは理解されるであろ
う。

ｔ、Ｂ、　　曲線突合せの流れ図と疑似コードＩ［、Ｂ
、１．　　曲線突合せの流れ国策２１図は、折れ線ベー
ス突合せにおいて、曲線突合せアルゴリズムを実行する
基本的ステップを示す。ステップ７１に指示するように
、画面曲線Ｇと探索パターン曲１ｉ１１とを比較する。

最初に、弧長や質量中心から最遠点までの距離のような
、曲線Ｈの基準向きに左右されない２つの曲線の性質を
比較する（ステップ７２．７３）。もしこれらの性質が
非常に相違すれば、直ちに、曲線が一致しない旨がユー
ザーへ報告され、プロセスは終了する。もし相違しなけ
れば、曲線ＩＩの特定の基準形（Ｂと呼ぶ）を選び（ス
テップ７４）、曲線Ｇの基準形（八と呼ぶ）と比較する
（ステップ７５．７６）。

詳しく述べると、最初に、ステップ７５で、への質量中
心からへの始点までのベクトルと、Ｂの質量中心からＢ
の始点までのベクトルとを比較する。もしこれらのベク
トルが非常に相違すれば、Ｂは八に一致しないことは明
白である。そこで、ステップ７７で、もし試みるべき基
準形がそのほかに残っていれば、への形状とＢの形状を
厳密に比較せずに、プロセスはＨの別の基準形へ転じる
。他方、もし八とＢが予備テストのすべてをパスすれは
、ステップ７６で、前に述べた距離比較を用いて、への
形状とＢの形状を比較する。もし、折れ線が一致すれば
、曲線ＧとＨは一致する（ステップ７８）。もし一致し
なければ、プロセスは、ステップ７７へ戻り、Ｈの別の
基準形に基ついて続行する。もし試みるべきＨの基準形
がそれ以上存在しなければ、曲線ＧとＨは一致しない（
ステップ８０）。

構造ベース曲線突合せアルゴリズムを実行する必要なス
テップは、構造ベース突合せの場合では、（１）質量中
心の代わりに、始点からの最も遠い制御点を使用するこ
と、（２）距離比較（ステップ７３）が、八とＢが同数
の線分と同数の制御点を有するか否かを判断するテスト
で置換されていること、及び（３）弧長比較（ステップ
７２）が、曲線の制御点を次々に相互に連結する必要な
直線線分の累積長さを各曲線について比較するステップ
で置換されていることを除いて、折れ線ベース突合せの
場合と同じである。

Ｉ［１、Ｂ、２．　　曲線突合せの疑似コード記述以下
の疑似コードは、３つのルーチンを使用して曲線突合せ
アルゴリズムを記述する。「曲線形状比較」ルーチンは
、もし「曲線タイプ」探索パラメータがアクティブであ
れば、「構造ベース比較」ルーチンを呼び出し、さもな
ければ、「折れ線ベース比較コル−チンを呼び出す。疑
似コードは、ＩＩＸ−Ｙ１１２を用いて、点Ｘと点７間
のユークリッド距離を表し、ボンド記号＃を用いて「等
しくない」ことを表し、用語「手続き」の後に、（Ｇ：
画面曲線、Ｈ：探索パターン曲線）を用いて、手続きか
２つのパラメータＧ　（画面曲線）と■　（探索パター
ン曲線）を有することを表す。

ここでは、全体を通じて、左矢印（←）を代入演算子と
して使用する。また、括弧０．０内の文は、注釈である
。

疑似コードに移る前に、変数「位置記述子」は、以下説
明する探索アルゴリズムにとって重要であることを理解
されたい。この変数は、構造ベース比較ルーチン又は折
れ線ベース比較ルーチンで設定されるが、どちらにも使
用されない。変数「位置記述子」にリストされた変換は
、前に述べた節ＩＩＩ　、八、３．に説明したやり方で
計算する。

「画１肚析ルＬｔｖ二九に＝手続き（Ｇ：画面曲線、Ｈ
：探索パターン曲線）・ もし探索窓枠で「曲線タイプＪがアクティブであれば、
〔構造ベース突合せを使用する〕［構造ベース比較コル
−チンを呼び出す：［構造ベース比較」ルーチンが見付
けた一致（もしあれば）をリターンする； さもなければ、〔折れ線ベース突合せを使用する〕 「折れ線ベース比較コル−チンを呼び出す；「折れ線ベ
ース比較」ルーチンが見付けた一致（もしあれば）をリ
ターンする； 「構造ベース比較」ルーチン二手続き（Ｇ：画面曲線、
■＝探探索パター的曲線 もしＧが曲線全体でなければ、 Ｇの構造ベース基準形を計算する； その基準形を八に保存する： さもなければ、＾←初期化のとき計算したＨの基準形； Ｂセット←初期化の際計算したＨの基準形：ＢＧ−Ｂセ
ットの最初の要素。

もしへの弧長＃Ｂの弧長であれば、失敗をリターンする
； もしへの線分の数＃Ｂの線分の数であれば、失敗をリタ
ーンする； もし＾の制御点の数＃Ｂの制御点の数であれば、失敗を
リターンする； ＳＡ←＾の始点； ｆＡ←ＳＡから最も遠いへの制御点； ＳＢ←Ｂの始点； ｆ、←ＳＢから最も遠いＢの制御点； 「テストＢ」ルーチン： もしベクトルｆＡ−６ＡがｆＢ−３１１と著しく相違す
れば、「次のＢ試行」ルーチンへ飛ぶ；１から＾の制御
点の数までのすべての整数について、 へのｉ番目の制御点からＢのｉ番目の制御点までの距離
を求める： もし距離がゼロから著しく相違すれば、「次のＢ試行」
ルーチンへ飛ぶ； ｉのループ終了； もし「位置記述子」が空であれば（変換は現在提案され
ていない）、 位置記述子←基準形Ｂ、へを介して■をＧにする変換と
、＾及び除外してきたＨのすべての基準形を介してＨを
Ｇにする変換を加えたものから成る変換リスト； 成功をリターンする；（一致を見付けた）「次のＢ試行
」ルーチン： もし試みなかったＢセットの要素がまだ存在すれば、 Ｂ←Ｂセットの次の要素； ３Ｒ←Ｂの始点； ｆ、←ｓ８から最も遠いＢの制御点； 「テストＢ」ルーチンへ飛ぶ； さもなければ、失敗をリターンする：（一致はない） 「　れ　ベース　　　ルー　ン：手続き（Ｇ：画面曲線
、旧探索パターン曲線）・ もしＧが曲線全体でなければ、 Ｇの折れ線ベース基準形を計算する； その基準形を＾に保存する； さもなければ、＾←初期化のとき計算したＧの基準形； Ｂセット←初期化の際計算したＨの基準形；Ｂ←Ｂセッ
トの最初の要素； もしへの弧長＃Ｂの弧長であれば、失敗をリターンする
； Ｓ＾←＾の始点； ｍＡ←＾の質量中心； ｆＡＩ−８Ａから最も遠いへの制御点；８ｓ←Ｂの始点
； ｆ８←ＳＢから最も遠いＢの制御点； 「テストＢ」ルーチン： もしベクトルｆＡ−８ＡがｆＢ−３Ｂと著しく相違すれ
ば、１次のＢ試行」ルーチンへ飛ぶ；もし距離１１１Ｉ
ＩＡ−８Ａ１１２がｌ　ｍ−５ＢＩｆ　２と著しく相違
すれば、「次のＢ試行」ルーチンへ飛ぶ；１から＾の頂
点の数までのすべての整数について、 ＳＡから＾のｉ番目の頂点までの「渡し距離」Ｗを求め
る； ＳＡから「渡し距離」Ｗにある＾上の点ｐを求める； もしｐからＢのｉ番目の頂点までの距離が許容値より大
きければ、「次のＢ試行」ルーチンへ飛ぶ； ｉのループ終了； １からＢの頂点の数までのすべての整数について、 ８ＢからＢのｉ番目の頂点までの「渡し距離」Ｗを求め
る； ８Ｂから「渡し距離」ＷのＢ上の点ｐを求める； もしｐからＢのｉ番目の頂点までの距離が許容値より大
きければ、「次の８試行」ルーチンへ飛ぶ； ｉのループ終了； もし「位置記述子」が空であれば（変換が現在提案され
ていない）、 位置記述子←基準形Ｂ、＾を介してＨをＧにする変換と
、＾及び除外してきたＨのすべての基準形を介してＨを
Ｇにする変換を加えたものから成る変換リスト； 成功をリターンする：（一致を見付けた）「次のＢ試行
」ルーチン： もし試みなかったＢセットの要素がまだ存在すれば、 Ｂ←Ｂセットの次の要素； ｓＢ←Ｂの始点； ｍＢ←Ｂの質量中心； ｆ、←Ｓ、から最も遠いＢの制御点； 「テストＢ」ルーチンへ飛ぶ； さもなければ、失敗をリターンする：〔一致は存在しな
い〕 ■１図形の形状及び性質の能率的探索 本発明の図形探索置換法は、すべての曲線が塗りつぶし
の色、線の色、線の幅、ダッシュパターンなどの図形ス
タイルが相違する曲線の集りを見付けることができる。

また、もし１以上の形状の集りが探索パターンと一致す
れば、本方法は、原則として、それらの一致を上から下
、左から右の順序で報告する。本節は、図形画面内の次
の図形パターンの出現を見付けるアルゴリズムについて
説明する。ここで、「次の」の図形パターンの出現は、
上から下、左から右の順序において最も新しく一致した
図形パターンの出現の後に続く。このアルゴリズムは、
優れた成果を得るため次の戦略を用いている。

１）問合せの最適化、　探索パターンのすべての情報を
分類して、それらの特徴のうち、（ｉ）画面内の形状と
比較する計算費用が少ない特徴、又はにｉ）探索パター
ンと一致する可能性のある画面対象の数を迅速に限定す
ると思われる特徴を識別する。これらの識別された性質
を最初に比較する。

この最適化を続ける場合、探索パターン内の１つの曲線
をいわゆる先導曲線に選ぶ。探索パターン内の他の形状
に対する突合せを実行する前に、まず、この先導曲線に
ついて画面を検査する。

２）条件付き探索、　先導曲線をシーン曲線にマツプす
る変換Ｔを求めたら、その変換Ｔをそれらに適用し、得
られた対象の位置に注目し、それらの対象の位置から遠
い画面対象を除外することによって、探索パターンの残
りの対象が、その特定の変換Ｔで一致するかどうかを迅
速に判断する。

■、＾、探索置換アルゴリズム ユーザーがユーザーインタフェース（第２八図）の“Ｙ
ＥＳ　”オプションを選択して、探索置換手続きをいっ
たん開始すると、３つの計算フェーズが、初期化、探索
、及び置換の順序で実行される。しかし、ユーザーが割
込み操作を用いずに、繰り返して“ＹＥＳ　”オプショ
ンを選択すると、初期化フェーズは一度実行されるだけ
であるが、探索フェーズと置換フェーズは、交互に実行
される。すなわち、計算フェーズは、初期化、探索、置
換、探索、置換、等の順序で実行される。同様に、゛Ｃ
Ｈ八ＮへＥ八Ｌへ”オプションを選択すると、装置は、
初期化を最初に、その後は探索と置換を交互に、３つの
計算フェーズを自動的に実行する。

幾つかの探索と置換を、この交互のやり方で実行する場
合、プロセスは、最も新しい初期化以来すべての探索フ
ェーズで発見されたすべての対象を追跡し続け、それら
のどれもが再度突き合わされることがないようにする。

また、置換フェーズで加えられたすべての対象は、ユー
ザーが新しい初期化を要求するまで、探索フェーズによ
って発見される資格を有しない。これにより、Ｃ■＾Ｎ
ＧＥＡＬＬ”オプションは確実に予測される結果を有し
、常に終了する。

探索置換プロセスの３つのフェーズで実行される操作は
次の通りである。

１）初期化、　このフェーズは探索パターンと図形画面
の分析をする。初期化は、探索に関係のある画面の性質
及び探索パターン対象を表すデータ構造を作る。これら
のデータ構造は、以後の計算能率を向上させため分類さ
れる。

２〉　探索、　このフェーズは、探索パターンのデータ
構造と画面を表すデータ構造とを比較し、上から下、左
から右の順序で、その探索パターンの次の一致を見付け
る。

３）置換、　もし一致が見付かれば、このプロ６一 セスは、探索パターンに一致した画面対象を選ぶ。

次に、置換すべき場合には、一致した画面対象の指定し
た性質を、置換パターンに記述された対応する性質で置
換する。ユーザーが新規に初期化を行うまでは、元の画
面対象のみがその以後の探索フェーズにおいて突き合わ
される資格を有するので、プロセスは、この置換フェー
ズの間に画面に加えられた形状と元の画面対象とを区別
する。

次節は、（１）先導探索対象をどのように選ぶか、（２
）探索及び置換において用いた主データ構造、（３）初
期化、探索、及び置換、（４）これらのフェーズにおい
てデータ構造をどのように最新に保つか、をさらに細分
して説明する。

■、八へ１．先導曲線と先導対象 初期化フェーズの最重要な結果の１つは、単に「先導対
象ｊとも呼ばれる先導探索対象の選択である。もし細分
度・クラスタであれば、先導探索対象はクラスタである
。もし細分度・曲線又は線分てあれば、先導対象は曲線
である。探索フェーズにおいて、プロセスは、探索パタ
ーン内の他のどれかの対象との一致を見付は出す試行に
先立って、常に先導対象との一致を見付は出す試行をす
る。探索パターンのどの対象を先導対象に用いてもよい
。

先導対象の曲線の１つを「先導曲線」に選ぶ。

先導対象と画面クラスタ又は曲線とを比較するプロセス
において、この先導曲線は、先導対象のすべての曲線の
中で、画面曲線と比較される最初の曲線である。先導対
象として、探索パターン内のどの対象を用いてもよいし
、また先導曲線として探索パターン内のどの曲線を用い
てもよい。

しかし、もし先導曲線を注意深く選べば、探索は、そう
しないより迅速に進行するであろう。例えば、それは、
考えられる最小の向きでそれ自身に一致する先導曲線を
選択することである。より詳細に説明すると、第２２八
図〜第２２Ｄ図は、先導曲線として好ましい順序で示し
た４つの曲線である。第２２八図に示した閉曲線が最良
である。その理由は、唯一の向きで、同一形状の他の曲
線に一致させることができるからである。一般に、閉曲
線は、多くても２つの向きで他の曲線と一致することが
できる。次に良い曲線は、第２２Ｂ図に示す非対称の閉
曲線である。その理由は、唯一の向きで、それ自身に一
致させることができるからである。第２２Ｃ図に示した
正方形のような有限回転対称の形状が、その次に好まし
い。その理由は、幾つかの向きで、それ自身に一致させ
ることができるからである。最後に、第２２Ｄ図に示し
た円は、それ自身に一致させることができる向きが無数
にあるから、先行曲線として考えられる最悪の選択であ
る。

探索フェーズにおいては、探索パターン全体について完
全な一致が見付かるまで、先導対象が画面内の各対象と
比較される。先導曲線の第１の基準形が画面曲線と一致
したら、探索曲線の残部を対応する画面曲線に一致させ
る変換を見付けるため、先導曲線の他の基準形を画面曲
線と比較する必要のあることが多い。したがって、対称
性の少ない（つまり、基準形の少ない）先導曲線を選べ
ば、比較回数を減らせることは明白である。

■、Ａ、２．　　主データ構造 探索フェーズ及び置換フェーズにおいて、プロセスは、
以下述べる、互いに相いれない異なる３セツトの曲線線
分について情報を得なければならない。すなわち、 １）適格セット、　適格セットは、まだ突き合わせる資
格を有する画面内のすべての線分を含む。

このセットは、初期化後、探索される資格を有する画面
の部分を識別するため使用したキャリットその他の指示
記号に先行するすべての線分を含む。

探索フェーズが１以上の線分との一致に成功すると、こ
れらの一致した線分は、適格セットから除かれる。

２）　仮セット、仮セットは、探索フェーズの間だけ空
でない。仮セットには、提案された変換の下で探索パタ
ーンの対応線分と突き合わされる画面の線分が含まれる
。これらの線分は、一致する画面線分が見付からなかっ
た探索パターンの線分が１以上あるとき、−時的に突き
合わされるだけである。提案された変換を用いて、探索
窓枠２３（第２Δ図）内のすべての線分が一致する画面
線分を見付けたとき、あるいはそのような一致する線分
を見付けることができないとプロセスが判断したとき、
仮セッＩ−は再び空になる。仮セッ１へ内のすべての線
分は、適格セットにも含まれていなければならない。

３）順序付きセット、順序付きセットは、探索パターン
の先導対象とまだ余すことなく比較されていない適格セ
ット内の線分を含む。定義によれは、（ｉ）前の探索フ
ェーズにおいて、これらの線分は一致していない。（ｉ
ｉ）現在の探索フェースにおいて、先導対象をそれらの
線分の上にマツプするかも知れない未試行の先導対象の
向きがまた１゜以上ある。

順序付きセット内の線分について完全な順序付けがある
。この順序付けは、曲線についての順序付けから導かれ
る。詳細に述べると、細分度クラスタであれば、クラス
タは、それらの境界ボックスの上左隅によって、上から
下、左から右に順序付けされる。したがって、もしこの
順序付けにおいて、クラスタ＾がクラスタＢに先行ずれ
ば、クラスタΔのすべての曲線は、クラスタＢのすべて
の曲線に先行する。もちろん、クラスタ内では、曲線は
、クラスタを作ったときユーザーが与えた順序を有する
。最後に、曲線内では、線分は前に述べた自然順序を使
用する。細分度・曲線又は線分であれば、曲線は、それ
らの境界ボックスの上左隅によって順序付けられ、曲線
内の線分は自然順序を使用する。理解されるように、上
記の規則は線分に関する完全な順序付けを定めている。

しかし、ユーザーが逆方向の順序（下から上、右から左
）で探索する場合は、この線分の順序が逆になる。次に
、以上具なる３つのセットの具体化について説明する。

順序付きセラ１へ、順序付きセットは、一般に、１組の
ビットとクラスタ又は曲線のリストで表現される。各画
面線分について、「アヘッドビット（ａｈｅａｄ　ｂｉ
ｔ）」と呼ばれるビットが記憶される。線分のアヘッド
ビットが１　（ＴＲＵＥ）であれば、その線分は、探索
パターンの先導対象とまだ余すとろこなく比較されてい
ない。アヘッドビットが０（ＦＡＬＳＥ）であれば、線
分は余すとろこなく比較されている。また、すべての線
分が　ＴＲＵＥのアヘッドビットを有するクラスタのす
べて（細分度クラスタの場合）、又はすべての線分がＴ
ＲＵＥのアヘッドビットを有する曲線のすべて（細分度
・曲線の場合）、又はどれがの線分がＴＲＵＥのアヘッ
ドビットを有する曲線のすべて（細分度・線分の場合）
が、［アヘッドリスト（ａｈｅａｄ　ｌ１ｓｔ）」と呼
ばれるリストに記載される。このアヘッドリストは、線
分の境界ボックスの上左隅によって分類される。

適格セット、　適格セットは、１組のビットとクラスタ
又は曲線のリストによって適当に表現される。各画面線
分について、［突合せビット（ｍａｔｃｈ　ｂｉｔ）　
Ｊと呼ばれるビットが記憶される。

線分の一致ビットが１　（ＴＲＵＥ）であれば、その線
分は最後の初期化フェーズ以来まだ突き合わされていな
い。突合せビットが０　（ＦＡＬＳＥ）であれば、その
線分は最後の初期化フェーズ以来既に突き合わされてい
るので、突き合わされる資格を持たない。

また、すべての線分が　ＴＲＵＥの「突合せビット」を
有するクラスタのすべて（細分度・クラスタの場合）、
又はすべての線分がＴＲＵＥの突合せビットを有する曲
線のすべて（細分度・曲線の場合）、又はどれかの線分
がＴＲＵＥの突合せビットを有する曲線のすべて（細分
度・線分の場合）が、「画面リスト（ｓｃｅｎｅ　１ｉ
ｓｔ）　」と呼ばれるリストに記載される。画面リスト
は、２つの部分に記憶される。第１の部分は、「アヘッ
ドリスト」である。これは順序付きセットを表現する場
合にも使用されており、前述のように順序付けされる。

第２の部分は、「ビハインドリスト（ｂｅｈｉｎｄ　１
ｉｓｔ）」と呼ばれ、特定の順序なしに記憶される。こ
の部分は、アヘッドリストに記載されていない適格線分
を有するすべてのクラスタ又は曲線を含む。

仮セット、　各画面線分について、「仮ビット（ｔｅｎ
ｔａｔｉｖｅ　ｂｉｔ）　Ｊと呼ばれるビットが記憶さ
れる。線分の仮ビットが１　、（ＴＲＵＥ）であれば、
その線分は探索パターン内の対応する線分と一時的に一
致している。仮ビットがＯ（ＦＡＬＳＥ）であれば、そ
の線分は、これまで−時的な一致の部分をなしたことが
ない。

■、八へ３．初期化 初期化の際、プロセスは、上から下、左から右の順序で
、キャリット記号に先行するすべての画面形状のリスト
を作る。その場合、対象の境界ボックスの上左隅を使用
して、リストの順序付けの位置を決定する。これらの画
面形状は、次の初期化までに探索された形状のみである
。リストに載っている各対象について、対象のすべての
線分が順序付きセットと適格セット内にあり、そして線
分のどれもが仮セツト内にないことを示す適当なビット
を設定する。最後に、探索フェーズにおいて容易にアク
セスできるように、探索パターン内の各対象について、
ユーザーが探索に興味を示した対象の性質（例えば、各
線分の色又は輪郭の領域の色）の値を選び出す。

初期化を実行すべき場合が幾つかある。第１に、もし特
定の画面が全く探索されなかったならば、曲線の基準形
を含む必要なデータ構造を構成するために、初期化が必
要である。第２に、探索方向を逆にする場合には、上か
ら下の順序の代わりに下から上の順序で（又はその逆）
画面対象を探索することができるように、画面対象を逆
にしなければならない。第３に、もしユーザーが手で画
面を編集したり、キャリット記号を新しい位置へ動かし
たならば、キャリット記号に先行する最初の対象から探
索が確実に始まるように、初期化が必要である。第４に
、もし最後の探索後、探索パターンを変更したならば、
編集した画面を忠実に表現するために、新しいデータ構
造を構成しなければならない。もちろん、画面を表現す
るデータ構造は、探索の細分度や、探索が回転不変性か
スケール不変性かによって異なる。したがって、これら
の探索パラメータを変更したときも、画面を表現するデ
ータ構造を再計算する必要がある。

■、八へ４．探索 前に触れたように、探索フェーズにおいては、探索パタ
ーンの先導曲線と画面内の曲線は、基本的に上から下の
順序で比較される。この比較を計算するため、先導曲線
の基準形と各画面曲線の基準形の１つを使用する。特定
のアフィン変換Ｔを使用し先導曲線を対応する画面曲線
に合わせることによって、先導曲線について一致が見付
かったら直ちに、プロセスは、その同じ変換Ｔを使用し
て、探索パターン内の曲線の残りと対応する画面曲線と
を比較する。変換Ｔを使用して探索曲線のすべての突合
せに成功すれば、プロセスは終了する。成功しなければ
、プロセスは、先導曲線を、与えられた同じ画面対象に
一致させる別の変換を見付ける試行をする。しかし、も
つともらしく思われるすべての変換を検討し尽くしたら
、プロセスは、先導曲線を現在の画面曲線に一致させる
試行を中止して、先導曲線を順序内の次の画面曲線と一
致させる試行へ進む。

幾つかの探索パターン曲線を同一画面曲線に突き合わせ
ることがないように、前に述べた仮ビットを使用して、
提案した変換Ｔの下で、どの画面曲線が探索パターン内
の対応する線分と既に一致しなかの情報を得る。もしあ
る変換Ｔの下で、すべての探索曲線を一致させることが
不可能であるとわかったら、すべての仮ビットをクリヤ
して、新しい変換を提案する。したがって、探索パター
ン内の全部の曲線について、一致が見付かった場合、又
は探索パターンの先導曲線と比較する画面曲線がそれ以
上存在しない場合には、探索フェーズが終了することは
理解されよう。前者の場合は、一致が確実に存在するの
に対し、後者の場合は、探索は失敗する。

形状に関する突合せのとき、能率を向上させるために、
条件付き探索を用いてもよい。先導対象について一致が
見付かったとき、その一致の場所は、探索リストの残部
の形状を探す画面内の場所を少なくともおおざっばに指
示する。したがって、境界ボックスを用いて、探索リス
トに残っている多数の対象を迅速に除外することが可能
である。

また、特定の変換Ｔを探索対象に適用したとき、与えら
れた探索パターン対象の一点がマツプする場所を計算す
ることによって、変換した点が境界＝７７ ボックスに含まれていない探索リスト上のすべての対象
を除外することが可能である。実際には、探索が厳密で
ない場合は、その点が含まれているかについてテストす
る前に、許容誤差に比例する量だけ境界ボックスを拡大
する。さらに別の迅速化手段は、探索リストが境界ボッ
クスの左上隅によって順序付けられるので、探索リスト
のセクション全体を迅速に除外することができるという
事実を利用している。

細分度・線分の場合の探索のメカニズムは、上記よりい
くらか複雑であり、パターンリスト内の対象と探索リス
ト内の対象の全部又は一部とを比較する。したがって、
一致を見付したときは常に、探索が終了した場所を正確
に指示する情報が保存される。もし探索リストのどれか
の部分がそれまでに検査されなかったならば、同じ探索
リストの別の部分について、次の探索を続けることがで
きる。また、一致を発見された後、将来同じ対象を突き
合わすことがないように、探索リストが更新される。探
索によって見付けた編集用窓２２（第２八図）内の突合
せ対象が選択され、他のすべての対象が除かれる。これ
は、２つの機能を果たす。

第１に、この選択のフィードバックにより、対象のどの
セットが一致したかがユーザーに指示される。第２に、
この選択のフィードバックにより、抹消、色の変更、変
換を含む、選択した対象に作用する編集繰作のどれかで
、一致した対象を修正する準備が完了する。ガーゴイル
（Ｇａｒｇｏｙｌｅ）編集プログラムでは、一致の位置
にソフトウェアのキャリット記号を置き直す。もしＹＥ
ＳまたはＣＨＡＮＧＥＡＬＬが実行中であれば、この時
点で、置換又はマクロ操作を実行する。

■、＾、５．置換 一致が見付かりさえすれば、探索パターン曲線の全部を
図形画面内の対応する曲線にマツプする既知の変換Ｔが
存在する。また探索プロセスは探索パターン内の曲線線
分と画面内の対応する曲線線分との一致も同時に立証し
た。したがって、この時点で、置換を行う場合には、ユ
ーザーインタフェース（第５図）の「置換」欄を吟味す
る。

形状以外の性質（すなわち、図形的スタイル）だけを置
換する場合には、置換窓枠２４（第２八図）内の形状か
らそれらの性質の値を選び出して、一致した対象に適用
する。形状を置換する場合には、一致した対象を抹消し
、置換窓枠２４内の対象を画面に複写する。そのとき新
しい画面対象は、前述のように、一致した形状から、「
置換」欄（第５図）に指定されていない性質を受は継ぐ
。

探索プロセスが形状の突合せをしているか否かによって
、置換フェーズにおいて、新しい画面対象を画面に位置
決めする。形状の突合せをしている場合は、変換Ｔが、
置換窓枠の形状に適用される。さもなければ、置換対象
の境界ボックスの中心と、一致した対象の境界ボックス
の中心とが合わさるように、置換対象を位置決めする。

ディジタル合成図形画面には、すべての対象（例えば、
輪郭やクラスタ）が特定の順序で描かれる。

後に描かれた対象は、先に描かれた対象を不明りように
することがある（その上に置かれることがある）。した
がって、形状を置換する置換操作においては、可能なと
きはいつでも、置換する形状などの対象の描き順序で、
新しい形状を同じ位置に置くことが望ましい。しかし、
一致した対象は、この順序付けの幾つかの異なる位置に
見付かることがあるので、それらに対する置換対象は、
どれかの一致した対象０が描かれたであろう描き順すな
わち層の最先の場所に、すべてが描かれるように置く。

置換対象は、それ自体内では、置換窓枠２４（第２八図
）内にあったとき有していた描き順すなわち層を保って
いる。

画面を更新したときは、探索のために画面を表すデータ
構造を更新する必要がある。そのため、置換された線分
に対するすべての引用をデータ構造から除去する。また
、最も新しく先導曲線と比較された線分は識別されるの
で、次の探索操作は、線分の順序における次の線分から
取り掛かることができる。

Ｎ　、Ｂ、　　探索置換操作の簡単な流れ図と疑似コー
ド ＩＶ　、Ｂ、１、探索置換操作の流れ図の概略ユーザー
がＣＨＡＮＧＥＡＬＬオプションく第２八図）を選択す
ると、全部で３つの図形探索置換フェーズが実行される
。最初に、初期化フェーズにおいてデータ構造か作られ
る。次に画面の全領域が探索されるまで、探索フェース
と置換フェーズが交互に実行される。第２２図の流れ図
は、ＣＨＡＮＧＥＡＬＬオプションを選択した場合の探
索置換アルゴリズムの概略を示す。

■、Ｂ、２．　　初期化の疑似コード記述下の疑似コー
ドは、探索データ構造をどのようにして構成するかを詳
細に記述する。前に指摘したように、データ構造の書式
は、実行する探索のタイプによって異なる。初期化フェ
ースの際の主要な変数を下に挙げる。

１）　方向（ｄｉｒｅｃｔｉｏｎ） 方向・順方向であれば、プロセスは、次の一致を上から
下、左から右の順序で探索し、方向・逆方向であれば、
次の一致を下から上、右から左の順序て探索する。

２）最終方向（ＩａｓｔＤｉｒｅｃｔｉｏｎ）「最終方
向」　は、変数「方向」が、すぐ前の探索のときに有し
ていた値である。

３）細分度（ｇｒａｎｕｌａｒｉｔｙ）思い出されるで
あろうが、「細分度」は、値「クラスタ」、「曲線」、
「線分」を取ることができる。

４）　アヘッドリスト（ａｈｅａｄＬｉｓｔ）構造が、
変数「対象情報」の記述中に記載されている記録のリス
トである。「アヘッドリスト」は、既に余すところなく
先行対象と比較された線分を除いた、順序付きセット内
の線分を含むすべてのクラスタ又は曲線を指す。

５）　ビハインドリスト（ｂｅｈｉｎｄＬｉｓｔ）「ビ
ハインドリストｊは、同様に変数「画面情報」のリスト
であり、まだ突合せ適格を有する線分を含むが、順序付
きセット内の線分を含まないすべてのクラスタ又は曲線
を指す。言い換えると、これらのクラスタ又は曲線のす
べての線分は、既に余すところなく先行対象と比較され
ている。

６）対象情報（ｏｂｊｅｃｔｌｎｆｏ）細分度・クラス
タであれば、変数「対象情報」は、探索パターン内の１
クラスタを表し、細分変曲線又は線分であれば、探索パ
ターン内の１曲線を表す。

ア）探索リスト（ｓｅａｒｃｈＬｉｓｔ）構造か、変数
「対象ルックス」の記述中に記載されている記録のリス
トである。「探索リスト」は、探索パターン内の各対象
０について１個のリス１へ要素を有する。

８）対象ルックス（ｏｂｊｅｃｔＬｏｏｋｓ）細分度・
クラスタであれば、「対象ルックス」は探索パターン内
の１クラスタを表し、細分度・曲線又は線分であれば、
探索パターン内の１曲線を表す。「対象ルックス」は、
関連する対象内の各曲線Ｃについて１個の要素を有する
リストである（細分度・曲線又は線分の場合、そのよう
な曲線は１つだけがある）。各曲線に対応する要素は、
それ自身、曲線内の各線分について１個の要素を有する
リストである。各線分の要素は、１つの線分Ｓの図形的
性質を記述する。これらの図形的性質には、線分Ｓの形
状、関連する対象０のクラス、線分Ｓの曲線タイプ、線
分Ｓの線の色、関連曲線Ｃのオストワルト純色、線分Ｓ
のダッシュパターン、曲線Ｃのストローク接合のスタイ
ル、曲線Ｃのストローク端のスタイル、及び線分Ｓのス
トローク幅が含まれる。また「対象ルックス」は、最小
の対称性を有する曲線の２つの性質を記述する２つのフ
ィールド、ｒ向きカウント」と「折れ線カウント」を有
する。詳しく述べると、「向きカウント」は、特定の曲
線の基準向きの個数であり、「折れ線カウント」は、曲
線の折れ線近似形の直線線分の個数である。

９）最終キャリット位置（ｌａｓｔｃａｒｅｔＰｏｓ）
この変数は、最後の一致を見付けたとき、プロセスがキ
ャリット記号を置いた場所の情報を得るため使用する点
（ｘ−ｙ座標対）である。

１０）キャリット位置（ｃａｒｅｔＰｏ）この変数は、
キャリット記号が現在置かれている場所を示す別の点（
別のｘ−ｙ座標対）である。

ユーザーはキャリット記号を動かすことができるので、
「キャリット位置」は「最終キャリット位置」と同じの
ことも、異なることもある。

１１）突合せビット（ｍａｔｃｈ　ｂｉｔｓ）画面内の
各曲線線分は、「突合せビット」と呼ばれる関連するプ
ール変数を有する。「突合せビット」は、その曲線線分
がそれまで突き合わされていなければ、ＴＲ１ｌＥであ
り、突き合わされていれば、ＦＡＬＳＥである。

次に説明する４つのルーチンが初期化を実行する。主ル
ーチンは、「探索初期化」ルーチンである。このルーチ
ンは、「アヘッドリスト作成」ルーチンと、「探索パタ
ーン分析」ルーチンを呼び出す。そして、「アヘッドリ
スト作成」ルーチンは　「探索探索記述」ルーチンを呼
び出す。

ルー　ン：手続き・ アヘッドリスト←ＮＩＬ、ビハインドリスト←ＮＩＬ、
　（両リストを空リストへ初期化する）もしキャリット
位置＃最終キャリット位置又は”５ＥＡＲＣＨ”オプシ
ョンの押しが最初であれば、［アヘッドリスト作成」ル
ーチンを呼び出す；（スクラッチからアヘッドリストを
作成する）もし方向＃最終方向であれば、（探索方向が
変わった） ［アヘッドリスト作成」ルーチンを呼び出す；（スクラ
ッチからアヘッドリストを作成する）線分の一部が前の
探索操作によって一致した各曲線Ｃについて、 一致したばかりのそれらの線分のアヘッドビットをＦＡ
ＬＳＥにセットする；（その結果、探索方向を逆にした
とき、同じ線分が再び一致することはない） もし曲線ＣのすべてのアヘッドビットがこのときＦＡＬ
ＳＥならば、 曲線Ｃをアヘッドリストから除き、ビハインドリストに
入れる； 一致した曲線のループを終了； さもなくば、もし”５ＥＡＲＣＨ″″オプシヨンの押し
が最初であるか、又は前の探索以来探索パターンを編集
した最初であれば、 「探索パターン分析」ルーチンを呼び出す；（スクラッ
チから探索リストを作成する）「アヘッドリスト　　　
ルーチン；手続き・画面内のすべての線分の突合せビッ
トをＰＡＬＳＥにセットする； 画面内のすべての線分のアヘッドビットをＦＡＬＳＥに
セットする； キャリット記号に先行する各画面対象０について、 「探索対象記述」ルーチン（０，アヘッドリスト）を呼
び出す；（曲線０の記述をアヘッドリストに加える） 曲線０のすべての線分のアヘッドビットをＴＲＵＥにセ
ットする； 曲線０のすべての線分の突合せビットをＴＲＵＥにセッ
トする； 画面対象のループを終了； もし方向・順方向であれば、各曲線の境界ボックスの上
左隅のｙ座標を減らすで、アヘッドリストを分類する； さもなくば、各曲線の境界ボックスの上左隅のｙ座標を
増すことで、アヘッドリストを分類する； ［索対象言述　ルー　ン；手続き（ｏ：画面対象。

ビッグリスト：対象情報のりスト） 対象情報←ＮＩＬ。

０の構成要素である各曲線について（方向順方向ならば
正順で、方向・逆方向ならば逆順て、曲線を検討する）
、 曲線情報←ＮＩＬ。

Ｃに含まれる各線分Ｓについて（方向・順方向ならば正
順で、方向・逆方向ならば逆順て、線分を検討する）、 ユーザーがオンしたｓ、ｐの各性質について、 もしｐが形状性質であり、折れ線突合せアルゴリズムを
使用する場合には、 Ｓを折れ線に変換し、折れ線を形状と して使用する； レコード「情報」に、Ｓに関するｐの値を記録する； 線分のループ終了； もし細分層・線分又は曲線ならば、 「曲線情報」をリスト「ビッグリスト」に加える； さもなくば、「曲線情報」をリスト「対象情報」に加え
る；く細分層・クラスタ）曲線のループ終了； もし細分層・クラスタであれば、「対象情報」をリスト
「ビッグリストＪに加える； 「　　パターン　　　ルー　ン；手続き・探索リスト←
ＮＩＬ。

探索パターン内の各対象Ｏについて、 対象ルックス←ＮＩＬ。

０の構成要素である各曲線Ｃについて、対象ルックス→
ＮＩＬ。

Ｃに含まれている各線分Ｓについて、 ユーザーがオンしたｓ＋ｐの各性質に ついて、 ｐが形状性質であり、折れ線突合せ アルゴリズムを使用するのであれば、 Ｓを折れ線へ変換し、折れ線を形状 として使用する； レコード「ルックス（Ｌｏｏｋｓ）　ＪにＳに関するｐ
の値を記録する； 性質のループ終了； 「ルックス」をリスト「曲線ルックス」に加える； 線分のループ終了； もし細分層・線分又は曲線であれば、 「曲線ルックス」をリスト「探索リ スト」に加える； さもなければ、「曲線ルックス」をリスト「対象ルック
ス」に加える；（細分層・クラスタ） 曲線のループ終了； もし細分層・クラスタであれば、 「対象ルックス」をリスト「探索リスト」に加える； 別− 対象のループ終了； 探索の能率を高めるため、得られたリスト「探索リスト
」に基づき「探索形状分類」ルーチンを呼び出す；（「
探索形状分類」ルーチンをリターンするとき、探索リス
トの最初の要素が先行対象である。） 「　　ノ゛　　　ルー　ン：手続き・ 「形状」性質を探索しない場合は、 探索リストはそのままにしておく さもなければ、 探索リスト内の各要素ｅについて、 最良曲線←最小対称性を有する要素ｅの曲線； 向きカウント←最良曲線の基準向きの数；折れ線カウン
ト←最良の折れ線近似形の直線線分の数； ループ終了； 向きカウントが増加する順序で、探索リストを分類する
。関連がある場合、折れ線カウントが増加する順序で探
索リストを分類する；■、Ｂ、３．　　探索の疑似コー
ド記述下の疑似コードは、探索をどのように実行するか
を記述する。簡単に言うと、上に説明した初期化フェー
ズのとき作成した「探索リスト」、「アヘッドリスト」
、「ビハインドリスト」を相互に比較して、「アヘッド
リスト」と「ビハインドリスト」内の対応する対象に一
致する「探索リスト」内の対象を見付は出す。探索のと
き、画面対象と、探索パターンの先導対象とを余すとこ
ろなく比較したら、画面対象を「アヘッドリスト」から
「ビハインドリスト」へ移す。

探索フェーズにおいては、初期化フェーズにおいて導入
した変数に加えて、以下の変数を使用する。

１）現比較対象（ｔｈｉｓＡｈｅａｄ）　、この変数は
、探索パターンの先導対象と現在比較している画面対象
を表す。変数「現比較対象」は、「アヘッドリスト」の
最初の要素である。

２）位置記述子（ｐｏｓｉｔｉｏｎＤ　：　ｐｏｓｉｔ
ｉｏｎ　ｄｅｓｃｒｉｐｔｏｒの略）、この変数は、現
在の先導曲線を「現−９３＝ 比較対象」の対応する線分にする変換のすべてのリスト
である。

３）マツピング（ｍａｐｐｉｎｇ）　、この変数は、対
のリストであり、第１要素は探索パターン内の対象、曲
線、又は線分であり、第２要素は画面内の突合せ用の対
象、曲線、又は線分である。

４）画面リスト（ｓｃｅｎｅＬｉｓｔ）　、この変数は
、「アヘッドリストＪの全要素と「ビハインドリスト」
の全要素を含むリストであり、「アヘッドリスト」のす
べての順序付き要素は、特定の順序を有しない「ビハイ
ンドリスト」の要素に先行する。この「画面リスト」は
、適格セット内のすべての画面線分を含んでいる。

５）　仮ビット（ｔｅｎｔａｔｉｖｅ　ｂｉｔｓ）、　
　画面内の各線分は、仮ビットを有する。このビットは
、線分が探索パターン内の対応する線分と仮に一致した
場合だけ、ＴＲＵＥである。

６）　現比較対象の一致部分（ｔｈｉｓＡｈｅａｄＰａ
ｒｔｓ）　−この変数は、「先導対象突合せ」ルーチン
の最も新しい呼出しにおいて、先導対象と一致した［現
在比較対象」の部分を表す。

７）　現比較対象の未突合せ部分（ｎｅｘｔＡｈｅａｄ
Ｐａｒｔｓ）　、　　この変数は、先導対象とまだ余す
ところなく比較されていない「現比較対象」の部分を表
し、比較される資格を有する。

８）極性オン（ｐｏｌａｒｉｔｙＯｎ）　、　　この変
数は、「極性」探索パラメータ（第３図参照）がアクテ
ィブであれば、ＴＲＵＥであり、さもなければ、ＦＡＬ
ＳＥである。

９）　形状オン（ｓｈａｐｅｏｎ）　、　　この変数は
、「探索」欄（第５図参照）の「形状」パラメータがオ
ンであれば、ＴＲＵＥであり、さもなければ、ＦＡＬＳ
Ｅである。

「　の−ルー　ン；手続き・ 「探索パターン突合せ」ルーチンを呼び出す；もし「探
索パターン突合せ」が成功すれば、すべての画面対象を
選択から外す； 文脈依存性探索の場合は、 探索窓枠内の選択した対象に対応する一致した画面対象
を選ぶ； さもなくば、 一致したすべての画面対象を選ぶ； 最終キャリット位置←キャリット位置；キャリット位置
←先導対象と一致した画面対象の境界ボックスの上左隅
； さもなくば、 すべての画面対象を選択から外す； これ以上の一致がないことをユーザーに知らせる； ［パターン　ムせ　ルー　ン；手続き・画面リストのす
べての線分の仮ビットをＦＡＬＳＥにセットする； もし画面リスト・ＮＩＬ又はアヘッドリスト・ＮＩＬで
あれば、失敗をリターンする：（探索パターンがない、
又は探索すべき画面対象が残っていない） 先導対象←探索リストの最初の要素； 他の対象←探索リストの残りの要素； 現比較対象←アヘッドリストの最初の要素；アヘッドリ
ストが空になるまで、又は一致が見付かるまで、 位置記述子←無； マツピング←ＮＩＬ。

もし「現比較対象」の１以上の要素がＴＲＵＥであれば
、 「先導対象突合せ」ルーチン（現比較対象。

先導対象）を呼び出す； もし「先導対象突合せ」ルーチンが一致の発見に成功す
れば、 〔現比較対象一致部分、現比較対象未突合せ部分、及び
位置記述子は新しい値を有する〕 「現比較対象一致部分」にリストされたすべての線分の
仮ビットをＴＲＩＩＥにセットする； 「他対象突合せ」ルーチン（他対象）を呼び出す； もし「他対象突合せ」ルーチンが一致の発見に成功すれ
ば、「一致発見」ルーチア− ンヘ飛ぶ； 「位置記述子」内の未試行の各向きについて、 「先導対象突合せ」ルーチン（現比較 対象、先導対象）を呼び出す； もし「先導対象突合せ」ルーチンが一 致の発見に成功すれば、 「他対象突合せ」ルーチン（他対象） を呼び出す； もし「他対象突合せ」ルーチンが成 功すれば、「一致発見」ルーチンへ 飛ぶ； 向きのループ終了； さもなくば、「突合せ失敗」ルーチンへ飛ぶ： さもなくば、「突合せ失敗」ルーチンへ飛ぶ： 「一致発見」ルーチン： ［現比較対象未突合せ部分Ｊの線分を除き、「現比較対
象」のすべての線分のアヘ・ンドビ・ントをＦＡＬＳＥ
にセ・ン卜する；もし「現比較対象」のすべてのアヘッ
ドビットがＦＡＬＳＥであれば、 アヘッドリストから「現比較対象Ｊを 除く： 「現比較対象」をビハインドリストに 加える； 「マツピング」のすべての線分の突合せビットをＦＡＬ
ＳＥにセットする； 成功をリターンする； 「突合せ失敗」ルーチン： ［現比較対象一致部分Ｊ内のすべての線分のアヘッドビ
ットをＦＡＬＳＥにセットする； 「現比較対象」　←　「現比較対象未突合せ部分」； さもなくば、（現比較対象にそれ以上未突合せの部分が
残っていないので、次の現比較対象へ進む） アヘッドリストから「現比較対象」を除く；「現比較対
象」をビハインドリストへ加える・ もしアヘッドリストが空であれば、失敗をリターンする
； 現比較対象←アヘッドリストの最初の要素； アヘッドリストのループ終了； ［ムせ　ルー　ン：手続きく画面部分、探索対象） もし細分度・線分ならば、 Ｃ１画面部分で表した曲線； ｔ←探索対象で表した曲線； 「最大ラン突合せ」ルーチン（ｃ、ｔ）を呼び出す；「
「最大ラン突合せ」ルーチンはｔ（のすべで）と一致す
る曲線Ｃの線分の最大ラン、「一致した部分」を見付け
る］ もし線分のランが探索対象（一致した部分ＮＩＬ）と一
致しなければ、 ［現比較対象未突合せ部分」　←ＮＩＬ。

失敗をリターンする； さもなくば、 「現比較対象未突合せ部分」　←（画面部分）［（一致
した部分のすべての線分）＋（−致した部分の線分の前
にくるＣのすべての線分（一致した部分が探索対象と正
順で一致した場合）又は一致した部分の後にくるＣのす
べての線分（一致した部分が探索対象と逆順て一致した
場合）］； 成功をリターンする； もし細分度・曲線であれば、 Ｃ１画面部分で表した曲！！： ｔ←探索対象で表した曲線； ｒ２曲線（ｃ、ｔ）突合せ」ルーチンを呼び出す；「現
比較対象未突合せ部分」←ＮＩＬ。

もし「２曲線突合せ」ルーチンが、Ｃとｔが一致するこ
とを発見すれば、 「一致した部分」　←Ｃ； 成功をリターンする； 「一致した部分」　←ＮＩＬ： 失敗をリターンする； もし細分度・クラスタであれば、 「全曲線突合せ」ルーチン（画面部分、探索対象）を呼
び出す； もし「全曲線突合せ」ルーチンが画面部分と探索対象の
突合せに成功すれば、 ［クラスタ一致発見Ｊルーチンへ飛ぶ；さもなくば、［
クラスタ突合せ失敗」ルーチンへ飛ぶ； 「クラスタ一致発見」ルーチン： 「一致した部分」←画面部分； ［現比較対象未突合せ部分」←ＮＩＬ。

成功をリターンする； Ｆクラスタ突合せ失敗」ルーチン： 「一致した部分」←　ＮＩＬ； 「現比較対象未突合せ部分」　←ＮＩＬ。

失敗をリターンする； 「１対象　きムわせ」ルーチン二手続きく画面部分、探
索対象） このルーチンは、「現比較対象未突合せ部分」を修正す
るコードのすべての行が削除されていることを除き、「
先導対象突合せ」ルーチンと同じである。

「　・　　ムせ　ルー　ン：手続き（他対象二対象ルッ
クスのリスト） もし他対象・ＮＩＬならば、 成功をリターンする；（未突合せのものは残っていなく
、全部を突き合わせた。） １本対象」　←　「他対象」の最初の要素；もし「形状
オン」がＴＲＵＥであれば、位置記述子を使用して「本
対象」の始点を画面のどこに置くべきかを見付ける。こ
の位置を「サンプル点」と呼ぶ； 画面リストの各対象０について、 もし「サンプル点」が境界ボックスの中になければ、「
次対象」ルーチンへ飛ぶ； 画面部分を、仮ビットがＦＡＬＳＥである対象０の線分
にする； もし画面部分が１以上の線分を含んでいれば、「１対象
突合せ」ルーチン（画面部分、本対象）を呼び出す： もし「１対象突合せ」ルーチンが、すべての０、すなわ
ち本対象を画面部分の一部の線分（まとめて「一致した
部分」と呼ぶ）に一致させれば、 「一致した部分」内のすべての線分の仮ビットをＴＲＵ
Ｅにセットする； 「他対象突合せ」ルーチン（他対象から本対象を除いた
もの）を呼び出す； もし「他対象突合せ」が成功すれば、成功をリターンす
る； さもなくば、 「一致した部分ｊ内のすべての線分の 仮ビットをＦＡＬＳＥにセットする； 「マツピング」を、「他対象突合せ」 ルーチンの呼出しをしたとき保持して いた値にリセットする； 「次対象」ルーチン： 画面リスト内の対象のループ終了； 〔この行に達すれば、現在提案している変換で、本対象
と一致する対象が画面内に存在しない〕失敗をリターン
する； ラン　４せ　ルー　ン；手続き（Ｃ：曲線、ｔ：曲線） セット内にあって、「置換」欄でアクティブである各性
質（領域の色、対象のクラス、ストローク接合）につい
て、 もしＣのｐの値と、ｔのｐの値が相違すれば、失敗をリ
ターンする； 性質のループ終了； ｎを、Ｃの線分の数とする； ｍを、ｔの線分の数とする； １からｎ−ｍ＋１の各整数ｉについて、１からｍの各整
数ｊについて、 本画面線分←Ｃの線分の数（ｉ＋ｊ−１）；本探索線分
←ｔの線分の数ｊ； 「線分性質比較」ルーチン（本画面線分。

本探索線分）を呼び出す； もし「線分性質比較」ルーチンが失敗すれば、「道順試
行」ルーチンへ飛ぶ； ｊのループ終了； 「 「性質一致」ルーチンへ飛ぶ； 「道順試行」ルーチン： もし「極性オン」がＦＡＬＳＥであれば、ｍから１まで
の各整数について、 本画面線分←Ｃの線分の数（ｉ＋ｊ−１）；本探索線分
←ｔの線分の数ｊ； ［線分性質比較Ｊルーチン（本画面線 分１本探索線分）を呼び出す； もし「線分性質比較」ルーチンが失敗 すれば、「次の１を試行」ルーチンへ 飛ぶ； ｊのループ終了； 「性質一致」ルーチンへ飛ぶ； さもなくば、「次の■を試行」ルーチンへ飛ぶ； 「性質一致」ルーチンニ 一致した部分←ｉからｉ＋ｍ−１までのＣの線分； もし「形状オン」がＦＡＬＳＥであれば、「−致発見」
ルーチンへ飛ぶ； 「曲線形状比較」ルーチン（一致した部分。

ｔ）を呼び出す； 〔もし位置記述子が変換を持たず、「曲線形状比較」ル
ーチンが一致を発見すれば、その時には、位置記述子は
、ｔを「一致した部分」にする変換のリストを有する。

〕もし「曲線形状比較」ルーチンが成功すれば、　「一
致発見」ルーチンへ飛ぶ； さもなくば、 一致した部分←ＮＩＬ、　（次のＩを試行する、すなわ
ち曲線Ｃの線分の次のランを試行する） ｒ次の■を試行）ルーチンへ飛ぶ； 「一致発見」ルーチン： Ｃのｉからｉ＋ｍ−１までの線分が、ｔの１からｍまで
の線分と一致したことを示すため「マツピング」を更新
する； 成功をリターンする； 「次のＩを試行Ｊルーチン： ｉのループ終了； 失敗をリターンする； ［２ムせ　ルー　ン：手続き（ｃ：曲線。

ｔ：曲線）・ ｎを、Ｃの線分の数とする； ｍを、ｔの線分の数とする； もしｍａｎであれば、失敗をリターンする；「最大ラン
突合せ」ルーチン（ｃ、ｔ）を呼び出す；「最大ラン突
合せ」ルーチンの結果をリターンする； ［全　　　ムせ　ルー　ン：手続き（画面部分、探索対
象）・ ｎを、画面部分内の曲線の数とする； ｍを、探索対象内の曲線の数とする； もしｎ＃ｍであれば、〔画面部分と探索対象は明らかに
一致しない〕 失敗をリターンする； ０１画面部分の最初の曲線； ｔ←探索対象の最初の曲線； 「２曲線突合せ」ルーチン（ｃ、ｔ）を呼び出す；〔も
し位置記述子が変換を持たず、「２曲線突合せ」ルーチ
ン一致を発見し、「形状オン」がＦＡＬＳＥであれば、
この時には、位置記述子はｔをＣにする変換のリストを
有する。〕もし「２曲線突合せ」ルーチンが失敗すれば
、失敗をリターンする； 位置記述子内の各変換について（「形状オン」がＦＡＬ
ＳＥであれば一度だけ）、 ０１画面部分内のｉ番目の曲線； ｔ←探索対象内のｉ番目の曲線； 「２曲線突合せ」ルーチン（ｃ、ｔ）を呼び出す； もし「２曲線突合せ）ルーチンが失敗すれば、「次の変
換」ルーチンへ飛ぶ； 画面部分のループ終了； 成功をリターンする； 「次の変換」ルーチン： 変換のループ終了： 「線分性　比　　ルー　ン：手続き（本画面線分。

本探索線分）・ セット内にあって、置換窓枠内でアクティブの各性質ｐ
（曲線のタイプ、線の色、ラインダッシュ、線の端、線
の幅）について、 もし本画面線分のｐの値＃木探索線分のｐの値であれば
、失敗をリターンする； 性質のループ終了； 成功をリターンする； 以上の疑似コードかられかるように、ユーザーは°“５
ＥＡＲＣ）ｌ”オプション（第２八図）を選択すると、
「次の一致発見・選択」ルーチンが呼び出される。

このルーチンは、「探索パターン突合せ」ルーチンを呼
び出す。この「探索パターン突合せ」ルーチンは、「先
導探索突合せ」ルーチンと　「他対象突合せ」ルーチン
を呼び出す。「他対象突合せ」ルーチンは、自身を再帰
的に呼び出し、再入可能なことに留意されたい。また「
先導対象突合せ」ルーチンと「他対象突合せ」ルーチン
は、次の３つのルーチン、「最大ラン突合せ」ルーチン
、「２曲線突合せ」ルーチン、及び「全曲線突合せ」ル
ーチンに依存していることに留意されたい。［最大ラン
突合せ」ルーチンは、細分度・線分の場合に使用され、
「２曲線突合せ」ルーチンは、細分度・曲線の場合に使
用され、ｒ全曲線突合せ」ルーチンは、細分度・クラス
タの場合に使用される。

以上３つのルーチンは、それぞれ、（ｉ）「線分性質比
較」ルーチンを呼び出して、２つの線分を比較し、色、
ストローク幅、ダッシュパターン、ストローク端の形状
が同一であるかどうかを判定し、そして（ｉｉ）ｒ曲線
形状比較」ルーチンを呼び出して、前に述べた曲線突合
せアルゴリズムを使用し、２の曲線の形状を比較する。

■、Ｂ、４．　　置換フェーズの簡単な流れ図形２３図
に、探索置換プロセスの置換フェーズの概略を示す。ス
テップ９１で、ユーザーが各探索後１組のマクロ操作を
実行することを命令したと判断したら、記録した動作を
再生する（ステップ９２）。

代わりに、形状及び性質を置換すべきと判断することも
ある（ステップ９１）。この場合には、もしユーザーイ
ンタフェース（第５図）の「置換」欄の「形状」パラメ
ータがアクティブであると判断したら（ステップ９３）
、一致した形状を抹消し、置換窓枠２４（第２八図）の
形状で置換する（ステップ９４）。これらの置換形状は
、ユーザーが行った図形的性質の選択（第５図）によっ
て、一致した形状から、その性質が修正される。置換し
ない場合には、形状はそのまま残され、置換窓枠２４か
ら一致した対象へ性質が付加される（ステップ９５）。

最後に、「アヘッドリスト」が更新され、次の探索フェ
ーズの準備が完了する（ステップ９６）。

ＩＶ　、Ｂ、５．　　置換フェーズの疑似コード提案す
る置換アルゴリズムの主な変数は、次の通りである。

１）転移する性質１合成された対象は、前に述べたよう
に、置換形状（一致した対象又は置換パターンから）と
図形的性質（一致した対象又は置換パターンから）とを
組み合わせて作られる。形状をあるソースから取り、幾
つかの図形的性質を別のソースから取る場合には、図形
的性質をそれらのソースから形状へ移さなければならな
い。変数「転移する性質」は、転移する図形的性質のリ
ストである。

２）　形状置換、この変数は、「置換」欄（第５図）の
「形状」パラメータがアクティブであれば、ＴＲＵＥで
あり、さもなければ、ＦＡＬＳＥである。

３）　形状ソースは、変数「形状置換」がＴＲＵＥであ
れば、置換パターンであり、ＦＡＬＳＥであれば、一致
した形状である。

４）性質ソースは、変数「形状置換」がＴＲＵＥであれ
ば、一致した形状であり、ＰＡＬＳＥであれば置換パタ
ーンである。

置換操作の疑似コードは３つのルーチンから成る。主ル
ーチンは　「置換」ルーチンである。

「置換Ｊルーチンは、置換が一義的であることを確認す
る［線分は同じに見えるか」ルーチンと、一致した対象
又は置換パターンのどちらかから図形的性質を付加して
、新しい画面対象を作り出す「性質転移」ルーチンを呼
び出す。さらに、「置換」ルーチンは、「アヘッドリス
ト」を増分的に更新して、次の探索操作のために「アヘ
ッドリストｊの準備を完了する「）＠序付きセット更新
」ルーチンを呼び出す。

一監直１し一ルニーｙンー二手続き もしユーザーが各探索後置換を実行することを要求すれ
ば、 もし「置換形状」がＴＲｔｌＥであれば、「転移する性
質」←「置換」欄のアクティブでない図形的性質； 線分ソースト一致した対象のすべての線分；［線分は同
じに見えるか」ルーチン（転移する性質、線分ソース）
を呼び出す； 「線分は同じに見えるか」ルーチンが成功すれば、 一致した形状を抹消する； 置換形状を複写し、探索対象を突き合わせた対象にマツ
ピングさせるのに成功した変換を用いてコピーを変換す
る； コピーを画面に加える； 形状ソース←置換形状のコピー； 性質ソース←一致した形状； 「性質転移」ルーチン（転移する性質、形状ソース、性
質ソース）を呼び出す； さもなくば、失敗をリターンする；（置換ができない） さもなくば、（一致した対象の形状をそのまま残す） 転移する性質←　「置換」欄のアクティブである図形的
性質； 線分ソース←置換パターンのすべての 線分； 「線分は同じに見えるか」ルーチン（転移する性質、線
分ソース）を呼び出す；もし「線分は同じに見えるか」
ルーチンが成功すれば、 形状ソースト一致した形状； 性質ソース←置換パターン： 「性質転移」ルーチン（転移する性質。

線分ソース）を呼び出す； さもなくば、失敗をリターンする；（置換ができない） さもなくば、（ユーザーは各探索後マクロ操作を実行す
ることを要求した） マクロ操作を再生し、探索対象を突き合わせた画面対象
に現在マツピングするのに成功した変換を用いてカーソ
ル座標を変換する；〔注記：　マクロ操作は次の探索フ
ェーズの前にキャリット記号位置を動かし、固定するこ
とができる〕 キャリット位置←最終キャリット位置；「順序付きセッ
ト更新コル−チンを呼び出す：「　　は同じに　えるか
　ルー　ン：手続きく転移する性質二図形的性質、線分
ソース二線分のりスト）・ 置換リストの最初の線分をＳ。とする；線分ソース内の
各線分Ｓについて、 「転移する性質」の各性質ｐについて、もしＳ。のｐの
値が、Ｓのｐの値と等しくなければ、失敗をリターンす
る； 性質のループ終了； 線分のループ終了； 成功をリターンする； ［ルー　ン：　手続き（転移する性質二図形的性質、性
質ソース二図形パターン、形状ソース：線分のリスト）
・ 「転移する性質Ｊ内の各性質ｐについて、もし性質が図
形対象全体く例えば、塗りつぶしなど）に適用されれば
、 形状ソース内の各対象０について、 ０の性質ｐを、ｐが性質ソース内に 有する値にセットする； 対象のループ終了； さもなくば、（性質は線分に適用する）形状ソース内の
各線分Ｓについて、 Ｓの性質ｐを、ｐが性質ソース内に有 する値にセットする； 線分のループ終了； 性質のループ終了； 曲線： もし「現比較対象の曲線」の一部（全部でない）が抹消
されたか（マクロ操作によって）、置換されなければ、
（現比較対象の曲線は幾つかの小部分に分けることがで
きる） アヘッドリスト、現比較対象の曲線を表すデータ構造を
除く； 新曲線リスト←ＮＩＬ、（新曲線リストは空のリストで
始まる） 残っている「現比較対象曲線」の各曲線Ｃについて、 Ｃの記述を新曲線リストに加えるため、「探索対象記述
」ルーチン（ｃ、新曲線リスト）を呼び出す； ループを終了； 順序を保っている新曲線リストのすべての要素をアヘッ
ドリストの頭に加える； 発明の効果 第２４図は、初期化フェーズ１０１で始まり、次に探索
フェーズ１０２が続き、置換フェーズ１０３で終わるＣ
ｈａｎｇｅ＾１１操作の場合の本発明の探索置換方法を
要約して示す。既に探索フェーズ１０２と置換フェーズ
１０３に主要ステップについてかなり詳しく説明したが
、この流れ図はＣｈａｆｅ＾１１操作を実行している場
合の異なるフェーズ間の相関関係を示す。前に述べたよ
うに、ユーザーが探索を続行すると決定したときはいつ
でも、置換フェーズ１０２は初期化フェーズ１０１へ戻
るけれども、ユーザーがパターンの一致を１つづつ見付
けることを選んだ場合にも、同様な相関関係がある。

以上の説明から、本発明により、ディジタル合成図形デ
ータを探索して、ユーザー指定の図形探索パターンと一
致するパターンを見付は出す能率のよい有効な方法及び
手段、並びに（１）あらかじめ記録したマクロ操作を見
付かった一致の全部又は一部に実施し、又は（１１）見
付かつ一致パターンの幾何学的特徴と図形的性質の全部
又は一部をユーザー指定のもので置き換える能率の良い
有効な方法及び手段が得られたことがわかるであろつ。

【図面の簡単な説明】

第１図は、本発明の図形探索置換ユーティリティを使用
して合成図形編集プログラムを実行するパーソナルワー
クステーションの略図、 第２Ａ図は、第１図のワークステーションによって開か
れた、典型的な探索置換操作を実行するための表示窓と
、前記操作を制御するための適当な主ユーザーインタフ
ェースを示す図、 第２Ｂ図は、第２Ａ図に示した探索置換操作を実行して
得られた編集画面、 第３図は、探索のとき幾何学的パラメータをセットする
ためのユーザーインタフェースを示す図、第４Ａ図〜第
４Ｃ図は、再帰的図形探索置換機能を使用して、繰返し
幾何図形を作る説明図、第５図は、探索置換プロセスの
探索のとき図形的性質をセットするためのユーザーイン
タフェースを示す図、 第６Ａ図と第６Ｂ図は、文脈依存図形探索置換操作の典
型的な利用を説明する図、 第７Ａ図〜第７Ｄ図は、文脈依存探索置換操作の別の利
用を説明する図、 第８Ａ図〜第８Ｆ図は、探索プロセスのいろいろな細分
度を示す図、 第９Ａ図〜第９Ｃ図は、ユーザー指定探索順序の例外を
示す図、 第１０Ａ図と第１０Ｂ図は、ユーザー指定探索順序の別
の例外を示す図、 第１１Ａ図〜第１１Ｃ図は、曲線タイプと形状探索パラ
メータの作用を示す図、 第１２Ａ図〜第１２Ｂ図は、精密探索パラメータと探索
許容誤差の作用を示す図、 第１３Ａ図〜第１３Ｂ図は、図形探索パターンと置換パ
ターンの幾何学的特徴及び図形的性質をどのように組み
合わせて合成した対象を作成するかを示す事例、 第１４図は、あいまいさのために失敗する置換操作の事
例、 第１５図は、第１１Ａ図に示した曲線の制御点を示す図
、 第１６Ａ図〜第１６Ｅ図は、曲線の基準形に基づく構造
計算に必要なステップを示す図、 第１７図は、２つの異なる曲線が同様な折れ線近似形を
作ることができる場合を示す図、第１８Ａ図〜第１８Ｄ
図は、折れ線を基準形に変換するやり方を示す図、 第１９図は、２つの折れ線を比較するときの距離比較曲
線突合せテストを示す図、 第２０Ａ図と第２０Ｂ図は、折れ線曲線突合せの表現上
の独立性を示す図、 第２１図は、本発明による図形探索操作の簡単な流れ図
、 第２２Ａ図〜第２２Ｄ図は、図形探索における考えられ
る各種の先導曲線の図、 第２３図は、本発明による図形マクロ操作／置換操作の
簡単な流れ図、 第２４図は、本発明に従ってユーザー指定Ｃ■＾Ｎ−Ｇ
ＥＡＬＬ操作を実行する図形探索置換プロセスの包括的
流れ図である。 符号の説明 １１・・・プロセッサ、１２・・・キーボード、１３・
・・モニタ、１４・・・カーソルコントローラ、２１．
２２・・・窓、２３・・・探索窓枠、２４・・・置換窓
枠、２５・・・メニュー、３１．３１ａ・・・正三角形
、３２・・・置換形状、３３・・・探索線分、４１・・
・外側曲線、４２−・・内側曲線、４３・・・弧、４４
・・・直線、４５・・・パラメトリック３次曲線、４６
．４７・・・弧、４８・・・３線分の曲線、４９．５０
．５２．５３．５４，５６．５７．５８．５９・・・線
分、６０＾・・・三角形、６０Ｂ・・・置換パターン、
６０Ｃ，６０Ｅ、６０Ｇ・・・「置換」欄、６００．６
０Ｆ、６０Ｈ・・・合成された対象、６１〜６７・・・
制御点、７１〜１０３・・・流れ図の各ステップ。 ＦＩＧ、２２Ａ ＦＩＧ、２２（ ＦＩＧ、２２Ｂ ＦＩＧ、２２Ｄ

Claims (1)

【特許請求の範囲】
1. （１）ディジタル合成図形データを編集するためのコン
   ピュータ化した図形探索置換方法であって、 ユーザー指定図形探索パターンの幾何学的特徴及び図形
   的性質と一致する図形パターンのデータを、方向付けら
   れた順序で探索するステップ、 前記データの探索において見付かった探索パターンに一
   致するすべての図形パターンを次々に選択するステップ
   、及び 前記選択した図形パターンの少なくとも一部を、ユーザ
   ー指定の編集命令に従って一件一件編集するステップ、 から成ることを特徴とする図形探索置換方法。