(57)【特許請求の範囲】
【請求項１】
画像発生方法であって、
（ａ）複数の点からなる境界を有する構造化オブジェクトを定義するステップと、
（ｂ）前記境界に沿った各点に対してエッジ特性関数を割り当てるステップであって、少なくとも２つの点の前記エッジ特性関数は互いに異なっており、前記エッジ特性関数の各々は前記境界の付近の画像値を定めるエッジ特性を定義する、前記のステップと、
（ｃ）前記画像内の各ピクチャ・エレメントに対して、前記境界上のアンカーおよび該アンカーまでの符号付き距離を決定するステップであって、前記アンカーは前記ピクチャ・エレメントが最も近い前記境界上の点である、前記のステップと、
（ｄ）前記画像内の各ピクチャ・エレメントに対して、前記ピクチャ・エレメントに対し決定した前記アンカーに割り当てる前記エッジ特性関数を選択するステップと、
（ｅ）前記画像内の各ピクチャ・エレメントに対して、当該ピクチャ・エレメントから前記アンカーまでの前記符号付き距離に、前記選択したエッジ特性関数を適用して、前記ピクチャ・エレメントに対して画像値を決定するステップと、から成る画像発生方法。
【請求項２】
請求項１記載の方法において、前記割り当てるステップ（ｂ）が、
前記画像内において境界を定義するステップと、
前記境界上の複数の点を選択するステップと、
選択した各点にエッジ特性関数を割り当てるステップと、
前記選択した点の各々の前記エッジ特性関数を補間して、前記境界上の他の点のエッジ特性関数を得るステップと、
から成ること、を特徴とする画像発生方法。
【請求項３】
請求項１記載の方法において、前記の関数を適用するステップが、各点について、前記アンカーおよび前記距離に応じてファクタαを算出するステップを含み、当該点に対する前記画像データはαＡ＋（１−α）Ｂであり、ここでＡは第１画像における対応する点からのデータであり、Ｂは第２画像における対応する点からの画像データであること、を特徴とする画像発生方法。
【請求項４】
コンピュータが読み取り可能な形態で、座標空間内の対象とする領域の表現を格納したコンピュータ読取可能媒体であって、前記表現が、
前記領域内の複数の点によって定義した境界の指示と、
前記境界の少なくとも２つの点に対する、エッジ特性関数の指示と、
から成り、前記境界上の第１の点の前記エッジ特性関数と前記境界上の第２の点の前記エッジ特性関数が異なること、
を特徴とするコンピュータ読取可能媒体。
【請求項５】
請求項４記載のコンピュータ読取可能媒体であって、更に、
前記座標空間における各点に対して、当該点に最も近い前記境界上の点と、前記境界上の前記点までの符号付き距離との指示を含むこと、
を特徴とするコンピュータ読取可能媒体。
【請求項６】
コンピュータが読み取り可能な形態で、座標空間内の対象とする領域の表現を格納したコンピュータ読取可能媒体であって、前記表現が、
前記領域内の複数の点によって定義した境界の指示と、
前記座標空間における各点に対して、当該点に最も近い前記境界上の点と、前記境界上の前記点までの符号付き距離との指示と、
から成ること、を特徴とするコンピュータ読取可能媒体。
【請求項７】
座標空間における対象とする領域の表現を発生するためのコンピュータ実装プロセスであって、
（ａ）ユーザ入力に応答して、境界を定義するステップと、
（ｂ）前記境界上の少なくとも２つの点に対して、ユーザ入力を受け取り、該ユーザ入力に応じてエッジ特性関数を割り当て、前記境界上の第１の点の前記エッジ特性関数を前記境界上の第２の点の前記エッジ特性関数とは異なるものとする、前記のステップと、
から成るコンピュータ実装プロセス。
【請求項８】
有限座標空間における対象とする領域の表現を発生するコンピュータ・システムであって、
（ａ）境界を定義する手段と、
（ｂ）前記境界上の少なくとも２つの点に対して、エッジ特性関数を割り当てる手段であって、前記境界上の第１の点の前記エッジ特性関数が前記境界上の第２の点の前記エッジ特性関数とは異なるようにした、前記の手段と、
から成るコンピュータ・システム。
【請求項９】
座標空間における対象とする領域の定義を操作するためのコンピュータ実装プロセスであって、コンピュータ読取可能信号を用いて前記定義をコンピュータ読取可能媒体上に格納し、前記定義が、前記領域内の複数の点によって定義した境界の指示と、前記座標空間における各点に対して当該点に最も近い境界上の点と、前記境界上の前記点までの符号付き距離の指示とを含み、前記プロセスが、
アンカーと当該アンカーまでの符号付き距離とを有する前記座標空間内の各点に対して、前記アンカーに割り当てた前記エッジ特性関数を、前記格納した符号付き距離に適用して、値を得るステップと、
該得た値に応じて、前記座標空間における前記点を表示するステップと、
から成ること、を特徴とするコンピュータ実装プロセス。
【請求項１０】
請求項１記載の方法であって、更に、
前記定義したエッジ特性関数を補間して、前記境界上の各点に対してエッジ特性関数を決定するステップ、
を含むこと、を特徴とする画像発生方法。
【請求項１１】
請求項１記載の方法において、アンカー点は、識別したピクチャ・エレメントに最も近い前記境界の点であり、前記アンカー点を決定するステップが、更に、
前記境界上の点の座標を初期化するステップと、
最小距離値を選択するステップと、
前記境界上のアンカー点を選択するステップと、
前記識別したピクチャ・エレメントと前記初期アンカー点との間の符号付き距離を決定するステップと、
前記符号付き距離を前記最小距離値と比較するステップと、
を含むこと、を特徴とする画像発生方法。
【請求項１２】
請求項１１記載の方法において、前記比較するステップが、更に、
前記最小距離値を前記符号付き距離に設定するステップと、
前記最小距離値に対応する前記ピクチャ・エレメントにアンカーを選択するステップと、
を含むこと、を特徴とする画像発生方法。
【請求項１３】
請求項１１記載の方法において、前記比較するステップが、更に、
ピクチャ・エレメントと前記境界上の各点との間の符号付き距離を決定するステップと、
前記符号付き距離を、前記境界上の各点の前記最小距離と比較するステップと、
前記ピクチャ・エレメントに対する前記最小距離を定め、そして対応するアンカーを選択するステップと、
を含むこと、を特徴とする画像発生方法。
【請求項１４】
請求項１記載の方法において、前記アンカーを決定する前記ステップが、更に、
各走査線内の各点に対して、
当該点に対して、前記境界までの現在の最小距離を含む距離テーブルである第１のアレイを発生するステップと、
前記点に対して、前記境界上の現在最も近い点を含むアンカー・テーブルである第２のアレイを発生するステップと、
前記点についての前記距離テーブルおよび前記アンカー・テーブルにしたがって、前記走査線に沿った各点に色を選択するステップと、
を含むこと、を特徴とする画像発生方法。
【請求項１５】
請求項１４記載の方法において、第１のアレイおよび第２のアレイを発生する各前記ステップが、
前記境界および関連するエッジ特性によって影響を受ける画像の領域を定める境界枠内に、現走査線が入っているか否かについて判定を行なうステップと、
前記境界のパラメータ値を初期化するステップと、
現パラメータに対応する点の画素座標を得るステップと、
前記点と前記現走査線との間のｙ軸に沿った距離を最大距離と比較するステップであって、該最大距離が、前記境界の前記エッジ特性によって画素が影響を受ける前記境界からの距離を表す、前記のステップと、
前記点のｘ軸に沿った最大距離内にある点についてのみ、前記点からの半径方向距離を用いて、前記第１および第２のアレイ内の前記距離テーブルおよび前記アンカー・テーブルを更新するステップと、
前記境界上の全ての点を評価し終えるまで、前記パラメータ値を増分するステップと、
を含むこと、を特徴とする画像発生方法。
【請求項１６】
請求項１５記載の方法であって、更に、
前記パラメータ値を再初期化するステップと、
現パラメータに対応する点の座標、および直前のパラメータに対応する前記画像内の点の座標を得るステップと、
前記現パラメータを表す点および前記画像内の前記点によって定義する線分上への、前記走査線の直交投影を決定するステップと、
前記走査線から前記点までの直交距離を決定するステップと、
前記直交距離を前記最大距離と比較するステップと、
前記点によって定義した前記線分への前記走査線の直交投影に対応する、前記走査線上の最小点と前記走査線上の最大点との間で、前記第１および第２のアレイ内の前記距離テーブルおよびアンカー・テーブルを更新するステップと、
を含むこと、を特徴とする画像発生方法。
【請求項１７】
請求項１５記載の方法において、前記現走査線が境界枠内に入っているか否かを判定する前記ステップが、前記走査線が前記境界枠の外側にある場合、アンカー値および距離値をデフォルト値にセットするステップを含むこと、を特徴とする画像発生方法。
【請求項１８】
請求項２記載の方法において、前記エッジ特性関数が、２つの引数、即ち、前記アンカーおよび前記距離を受け取る手順であること、を特徴とする画像発生方法。
【請求項１９】
請求項２記載の方法において、前記領域内の各点に対して、前記所与の点に最も近い前記境界上のアンカー点、および当該アンカー点までの距離を決定することによって、前記エッジ特性関数を適用すること、を特徴とする画像発生方法。
【請求項２０】
請求項４記載のコンピュータ読取可能媒体において、前記エッジ特性関数が、前記境界付近の画像値を定義すること、を特徴とするコンピュータ読取可能媒体。
【請求項２１】
請求項２０記載のコンピュータ読取可能媒体において、前記エッジ特性関数が、前記境界付近の各点の画像への寄与を、前記境界からの前記点の距離の関数として定義すること、を特徴とするコンピュータ読取可能媒体。
【請求項２２】
請求項７記載のコンピュータ実装プロセスであって、更に、
前記境界上の前記点の各々の前記エッジ特性関数を補間して、前記境界上の他の点のエッジ特性関数を得るステップ、
を含むこと、を特徴とするコンピュータ実装プロセス。
【請求項２３】
請求項７記載のコンピュータ実装プロセスであって、更に、
前記座標空間内の各点に対して、当該点に最も近い前記境界上の点と、前記境界上の前記点までの符号付き距離とを決定するステップと、
前記符号付き距離に適用する前記エッジ特性関数に基づいて、前記座標空間内の各点に対して値を決定するステップと、
を含むこと、を特徴とするコンピュータ実装プロセス。
【請求項２４】
請求項７記載のコンピュータ実装プロセスにおいて、前記エッジ特性関数が、前記境界付近の画像値を定義すること、を特徴とするコンピュータ実装プロセス。
【請求項２５】
請求項８記載のコンピュータ・システムであって、更に、
前記座標空間内の各点に対して、当該点に最も近い前記境界上の点と、前記境界上の前記点までの符号付き距離とを示す手段と、
前記エッジ特性関数に基づいて、前記座標空間内の各点に対して値を割り当てる手段と、
を含むこと、を特徴とするコンピュータ・システム。
【請求項２６】
請求項８記載のコンピュータ・システムにおいて、前記エッジ特性関数が、前記境界付近の画像値を定義すること、を特徴とするコンピュータ・システム。
【請求項２７】
請求項９記載のコンピュータ実装プロセスにおいて、前記エッジ特性関数が、前記境界付近の画像値を定義すること、を特徴とするコンピュータ実装プロセス。
【発明の詳細な説明】
発明の分野
本発明は、コンピュータを用いて二次元空間または三次元空間における構造化オブジェクトを定義するというような、座標空間において対象領域を定義し操作するためのコンピュータ・システムおよびコンピュータ実装プロセスに関するものである。特に、本発明は、画像を合成する際に使用する制御画像の発生に有用である。
発明の背景
コンピュータ・システムには、通常２つのカテゴリの一方に該当する静止画像データを表現する多くの方法がある。ビット・マップと呼ばれる画像表現の第１カテゴリでは、画像の個々のピクチャ・エレメント即ち画素の各値を格納する。画像表現は、圧縮または伸長をしてもよい。ビット・マップ状画像表現は、通常、表示のためにはコンピュータによる計算を多く必要としないが、大量のメモリ空間を占有する場合がある。また、このような画像表現は、通常、柔軟性がなく、かなりの視覚的なアーチファクトを発生せずに、スケールまたはその他の変更を行うことは困難である。画像表現の第２カテゴリは、構造化オブジェクトである。構造化オブジェクトは、画像内に含まれるオブジェクトの構造にしたがって、典型的に数式で画像を定義する。例えば、立方体の画像は、ある基準点に関する、当該立方体の頂点の位置で表すことができる。このような構造化オブジェクトは、三次元モデリング・システム、デスクトップ・パブリッシング・システム等内において日常的に見られるものである。
画像表現が重要な分野の１つに、画像合成(image compositing)がある。アルファ合成(alpha compositing)と呼ばれる、画像合成の一形式は、２つの画像を組み合わせて第３の画像を発生することを伴い、第３の画像における組み合わせ画像の各々の寄与の程度を、制御画像によって定義する。アルファ合成システムの一例が、ポール・ケラー(Pall Kellar)の米国特許第４，６０２，２８６号に見られる。
ケラー特許に記載されているように、制御画像は、ビット・マップ・ピクチャとして定義し、各画素がある値を有する。各画素の値は、ゼロ（０）ないし１の目盛り上におけるアルファ値（α）を表す。制御画像内の各画素（ｘ，ｙ）に対するアルファ値（αｘ，ｙ）を、ここでは制御値と呼ぶが、これを標準的なマッピング関数において用いて、入力画像を組み合わせる。例えば、第１の入力画像（Ａ）における各画像Ａｘ，ｙおよび、第２の入力画像（Ｂ）における画像Ｂｘ，ｙについて、出力画像Ｃにおける画素Ｃｘ，ｙを、次の式で与える。尚、ＡおよびＢは、ｘ×ｙ個の画素から成る画像である。
Ｃｘ，ｙ＝αｘ，ｙＡｘ，ｙ＋（１−αｘ，ｙ）Ｂｘ，ｙ          （１）
このような合成は、ビデオ・プログラムにおいて、ワイプ、フェード等の特殊効果および遷移として現れる。ビット・マップ状画像を制御画像として用いる場合の難問の１つに、アルファ合成が、動画ビデオ・シーケンス(motion video sequence)におけるカット間の遷移におけるような、時間的な補間を伴う場合が多いことがあげられる。即ち、１対のフレームを組み合わせて動画ビデオ・シーケンスにおける１フレームを生成するために用いる制御画像が、当該シーケンス内の他のフレームを生成するために用いる制御画像とは異なる場合が多い。加えて、低解像度で作成したビット・マップ状制御画像を、後により高い解像度に調整する場合、低解像度の画像において見られる電子化が、解像度を高めた画像においてアーチファクトが発生する原因となる。
制御画像を定義する別の方法に、構造化オブジェクトを用いることによるものがある。構造化オブジェクトは、画像内のオブジェクトの構造によって、典型的に数式で、制御画像を定義する。この定義は、曲線を表す等式のような数式、または点の座標や方向および大きさを表すベクトルのような幾何学とすることができる。この構造化オブジェクト定義を解釈することにより、最終画像において発生すべき各画素に対し制御値を得る。これらを一緒に取り入れると、制御値は、ビット・マップ状画像を用いて得られる制御値の集合と同様となる。
構造化定義の利点の１つに、これらは、ビット・マップ状画像のような静的定義よりも容易に、スケール、動画化(aminate)、または時間的な補間が可能なことがあげられる。構造化オブジェクトを用いることの別の利点は、画像のある部分がオブジェクトの境界の内側または外側のどちらにあるのかについての計算上の判定が比較的容易なことである。構造化オブジェクト定義は、また、スケーリングや回転のような単純な操作がしやすいので、効果によっては、それを作成するプロセスを簡単にする。しかしながら、今日まで構造化オブジェクトは、通常、単純なオブジェクトに対する単純な処理に用いられているに過ぎない。
画像合成では、通常、ビット・マップ状画像および構造化オブジェクト定義双方を用いて、制御画像を発生する。制御画像は、典型的に、０または１のいずれかの制御値を有し、画像内の画素間の変化がエッジを定義する。通例では、エッジ即ち境界を処理してブレンド特性(blending characteristic)を与え、得られる画像内におけるソース・コンテンツ(source content)間の変化が１つの画素上で分離して発生しないようにする。むしろ、制御画像は、全てのエッジが漸進的な変化、典型的には、単純なグレースケール傾斜を有するように処理する。ケラーの特許では、ペンおよびタブレット入力デバイスからの入力を処理する際のアーチファクトのため、このグレースケール傾斜を与える。構造化オブジェクトを用いる場合、殆どの従来技術のシステムは、走査線内のあるエッジの前後の値を単純に調節するだけである。
本発明の一般的な目的は、複雑度の高い画像を表すことができ、しかも容易に操作可能な、コンピュータ用の画像表現を与えることである。
発明の概要
構造化オブジェクトを用いた画像表現は、コンピュータによって容易に操作することができる。この画像表現は、より複雑な画像を表現することができ、構造化オブジェクトは境界を定義し、ある領域内のこの境界に近い画像値は、エッジ特性関数(edge characteristic function)と呼ぶ関数によって定義する。エッジ特性関数を適用するには、当該領域内の各点について、所与の点に最も近い境界上の点（ここではアンカーと呼ぶ）およびその点までの距離を決定する。
境界に沿った異なる点に、異なるエッジ特性関数を割り当てることができる。一実施形態では、エッジ特性関数は、境界上で選択した特性点に対して割り当てる。これらのエッジ特性関数を補間し、境界に沿った残りの点に対するエッジ特性関数を与えることができる。境界上にない各点は、それに最も近い当該境界上の点のエッジ特性関数にしたがって、および当該点までの距離にしたがって処理を行う。エッジ特性関数は、他のファクタの関数としてもよい。
この画像表現は、多くの利点を与え、その中には、一層複雑な画像を発生し、次にそれを一層容易に操作するか、あるいは異なる画像フォーマットから変換することができる機能を含む。操作形態の１つは、時間に対する補間である。画像合成では、この画像表現は、いくつもの領域にわたる種々の効果を、制御しつつ容易に減衰することも可能とする。この方法は、画像合成、および多数のパラメータにわたって様々に変化するデータをモデリングするためには、特に有用である。
したがって、本発明の一形態は、画像発生方法である。この方法は、画像内の曲線を複数の点として定義することを含む。曲線内の少なくとも２点に対して、ある関数を割り当てる。これらの点の一方の関数は、これらの点の他方の関数とは異なる。画像内の各ピクチャ・エレメント毎に、曲線上のアンカーおよび当該アンカーまでの符号付き距離を決定する。各ピクチャ・エレメント毎に、点のアンカーに割り当てる関数を選択する。画像内の各ピクチャ・エレメント毎に、選択した関数を当該ピクチャ・エレメントからアンカーまでの符号付き距離に適用し、当該ピクチャ・エレメントに対する画像データを決定する。符号付き距離とは、絶対値ではなく、負または正の距離寸法であり、例えば、方向を示す場合に有用である。
この方法の一実施形態では、点に関数を割り当てるステップが、境界上の複数の点を選択することを含む。選択した各点に、エッジ特性を割り当てる。選択した点の各々のエッジ特性を補間し、境界上の他の点のエッジ特性を得る。
この方法の別の実施形態では、関数を適用するステップが、各点毎に、アンカーおよび距離に応じてファクタαを計算することを含む。当該点に対する画像データは、αＡ＋（１−α）Ｂであり、ここで、Ａは第１画像内の対応する点からの画像データであり、Ｂは第２画像の対応する点からの画像データである。
本発明の別の形態は、コンピュータが読み取り可能な形態で、座標空間内の対象領域の表現を格納したコンピュータ読取可能媒体である。この表現は、当該領域内の複数の点で定義した境界の指示と、境界上の少なくとも２点に対するエッジ特性の指示とを含み、第１点のエッジ特性および第２点のエッジ特性は異なる。一実施形態では、この表現は、座標空間内の各点毎に、当該点に最も近い境界上の点の指示と、境界上の当該点までの符号付き距離とを含む。
本発明の別の形態は、コンピュータが読み取り可能な形態で、座標空間内の対象領域の表現を格納したコンピュータ読取可能媒体である。この表現は、領域内の複数の点で定義した境界の指示と、座標空間内の各点毎に、当該点に最も近い境界上の点の指示と、境界上の当該点までの符号付き距離とを含む。
本発明の別の形態は、座標空間内の対象領域の表現を発生する、コンピュータ実装プロセスである。このプロセスは、ユーザ入力に応答して境界を定義することを含む。また、境界上の少なくとも２点についてもユーザ入力を受け取り、このユーザ入力に応じて、エッジ特性を割り当てる。第１点のエッジ特性と第２点のエッジ特性は異なる。
本発明の別の形態は、有限座標空間内の対象領域の表現を発生するコンピュータ・システムである。このコンピュータ・システムは、境界を定義する機構を有する。境界上の少なくとも２点についてエッジ特性を割り当てるために別の機構を用い、第１点のエッジ特性は、第２点のエッジ特性とは異なる。
本発明の別の形態は、座標空間内の対象領域の定義を操作する、コンピュータ実装プロセスであり、コンピュータ読取可能信号を用いて、この定義をコンピュータ読取可能媒体上に格納し、該定義は、当該領域内の複数の点で規定した境界の指示と、座標空間内の各点毎に、当該点に最も近い境界上の点の指示と、境界上の当該点までの符号付き距離とを含む。このプロセスは、アンカーおよび当該アンカーまでの符号付き距離を有する座標空間内の各点毎に、アンカーに割り当てたエッジ特性関数を、格納してある符号付き距離に適用して、値を得ることを含む。得られた値に応じて、座標空間内の点を表示する。
【図面の簡単な説明】
図面において、
図１Ａおよび図１Ｂは、従来技術のシステムにおけるα合成に用いるための制御画像のビット・マップ状画像定義、および関連するブレンド特性を示す。
図２Ａおよび図２Ｂは、従来技術の方法論による構造化オブジェクトを用いて定義した制御画像、および関連するブレンド特性を示す。
図３Ａないし図３Ｅは、本発明による構造化オブジェクト表現を用いて定義した制御画像、および関連するエッジ特性関数を示す。
図４は、本発明による構造化オブジェクト定義の表現の概略図である。
図５は、本発明を使用可能なコンピュータ・システムのブロック図である。
図６は、図３に示したメモリ・システムの更に詳細な構成図である。
図７は、本発明による構造化オブジェクト定義を処理するシステムのブロック図である。
図８Ａおよび図８Ｂは、エッジ特性定義の例を表す擬似コードである。
図９Ａは、図７におけるアンカー／距離計算部が実行する、アンカー値および距離値を決定するプロセスを記述するフローチャートである。
図９Ｂは、座標空間におけるある領域を輪郭描写する構造化オブジェクトの概略図である。
図９Ｃおよび図９Ｄは、アンカー／距離の寸法を決定する別のプロセスを記述するフローチャートである。
図９Ｅは、いかにして半径方向距離および直交距離を定義するかを示す図である。
図１０は、図７に示す構造化オブジェクト定義、可変エッジ特性ならびにアンカー値および距離値を用いた、画像処理を記述するフローチャートである。
図１１は、図７に示す画像処理モジュールによって発生した出力例の図である。
図１２は、本発明を用いて発生した制御画像を使用可能な、α合成システムのブロック図である。
詳細な説明
本発明は、添付図面に関連付けて以下の詳細な説明を読むことによって、一層深い理解が得られよう。図面では、同様の参照番号は、同様の構造を示すものとする。
本発明は、座標空間内の対象領域の輪郭描写(delineation)に関するものである。対象領域とは、空間内のより大きな領域のサブセットのことである。対象領域の輪郭描写の一種に、画像のサブセットを選択し、これに画像の残り部分とは異なる処置を施すというものがある。処置とは、複数の画像処理機能のいずれかを意味し、色つけ、合成、遷移および特殊効果を含むが、これらに限定される訳ではない。対象領域の輪郭描写の別の種類に、画像処理には無関係に、何らかの人口学的特性(demographic characteristic)を適用する地理的領域の輪郭描写がある。三次元空間における一例として、彗星のような、本体と彗星の尾を含む、移動中の火の玉のアニメーションの記述をあげておく。
これより図１Ａを参照すると、従来技術の画像処理システムにおいて、ビット・マップ状画像を用いてある領域が輪郭描写してある。これは、ユーザがペンおよびタブレット入力デバイス（図示せず）を用いて発生したものである。この入力デバイスは、ユーザが、図１Ａの画像２２内において、２０に示すような線を定義することを可能にする。次に図１Ｂを参照すると、ペンの先端の傾斜形状によって、２４に示すような数学的特性を有するエッジを与える。目で見たときに、線２０によって定義したエッジは、短いグレースケールの傾斜を有するように現れる。２４で示すグラフは、境界からの距離に対するグレースケール値を示す。
次に図２Ａを参照すると、構造化オブジェクトを用いた従来のシステムにおいて、画像２６は、Ａで定義した円のようなオブジェクトを含む。円は、その半径、例えば、２、およびその中心、例えば、画像の座標空間内の座標（０，０）によって定義することができる。次の図２Ｂを参照すると、２８に示すような関数が、構造化オブジェクトＡによって定義した境界を横切るｘ方向のグレースケール傾斜を定義し、所望のエッジ・スムージング(edge smoothing)を与えることができる。処理するとき、画像２６内の点には、構造化オブジェクトＡによって定義した境界からそれがどれだけ離れているかに応じたグレースケール値を割り当てることができる。実際には、構造化オブジェクトによって定義した境界上にある点をが与えられた場合、この関数２８を用いて、境界上のこの点に近い他の点を識別し、これら識別した点にグレースケール値を割り当てる。
構造化オブジェクト定義の利点の１つに、構造化オブジェクトの時間に対する補間、例えば、その形状の変化を容易に実行できることがあげられる。例えば、拡大した半径、例えば、３、および同じ中心座標を有する拡大した円を、画像２６内のＢに示す。この円のサイズは、半径値を増分または減分することによって、容易に変更可能であることは、明らかに理解できよう。その位置は、中心座標を移動させることによって、容易に変化させることができる。
画像処理の用途からのこれらの解決策(solution)は、構造化オブジェクトによって定義した境界におけるブレンド特性の決定において、間接的にのみ、「近接度(proximity)」という概念(notion)を必要とする。ある点の境界に対する近接度の直接的な尺度およびその使用によって、更に複雑なオブジェクトの表現も可能になることがわかっている。
近接度とは、構造化オブジェクトによって定義した領域のエッジから、ある点がどれだけ離れているかについての符号付き寸法である。例えば、点が当該領域の内側にある場合、寸法は正とすることができ、点が領域の外側にある場合負とすることができる。黒色（白色）をエッジ付近にない外側（内側）の点全てに割り当て、グレースケールの傾斜をエッジ付近の点に割り当てた場合、領域は、黒い背景上の白い区域として表示され、領域のエッジ上に、白から黒への傾斜した遷移が生じる。グレースケール傾斜の形状がエッジ付近のシェードを制御し、これを当該領域のエッジ特性と呼ぶ。グレースケール傾斜が異なれば、異なるエッジ特性が得られ、したがって、その領域の異なる輪郭描写が得られる。図１Ａおよび図１Ｂに示す画像表現では、エッジ特性を明示的に定義していない。エッジ付近のブレンド特性は、実際には、入力デバイスの所望の副作用である。図２Ａおよび図２Ｂに示す画像表現では、１つのブレンド特性のみを領域毎に割り当てている。加えて、このブレンド特性は、領域の境界上のある点に関して処理して、当該境界点に近接した座標空間内の点を識別する。対照的に、本発明では、近接度は、領域内の点に対して定義して、その所与の点に最も近い境界上の点を識別するようにしている。
次に図３Ａないし図３Ｅを参照すると、本発明は、構造化オブジェクトによって定義した曲線に沿った異なる点において、異なるエッジ特性関数を可能にする。例えば、円領域Ｃは、構造化オブジェクト定義によって輪郭描写することができる。円のエッジ周囲に割り当てた可変エッジ特性関数は、各方向毎に異なる外観のグレースケール傾斜を有する円形ディスクを表す。例えば、図３Ａにおける円のエッジ上の点Ｅには、図３Ｂの３２に示すような、第１のエッジ特性関数ｆ１（Ｅ）を割り当てることができる。図３Ａにおける円のエッジの対向側にある第２の点Ｆには、図３Ｃの３４に示すような異なるエッジ特性関数ｆ２（Ｆ）を割り当てることができる。このエッジ特性の組み合わせにより、卵黄(egg yolk)を有する卵のように見える形状が得られる。
このような画像表現は、時間に対して容易に補間することができる。例えば、半径を変化させ、図３ＡのＤで示すような曲線を生成することができる。あるいは、曲線上の点ＥおよびＦに割り当てたエッジ特性を、例えば、３６および３８に示すような新しい関数ｆ１（Ｅ）およびｆ２（Ｆ）に変更することも可能である。
次に図４を参照し、二次元画像のような座標空間内の対象領域の輪郭描写の表現を示す。このような表現は、全体として、４０に示すような境界を与える構造化オブジェクトの定義の指示を含む。図示の例では、円の境界は、中心点および半径によって定義する。また、この画像表現は、４２に示すような１つまたは２つ以上のエッジ特性関数の指示を含み、これらを、それぞれ、境界上の各特性点に割り当てる。
この対象領域の輪郭描写の表現は、例えば、図５に示すようなコンピュータ・システム５０で用いる。コンピュータ・システム５０は、相互接続機構５６を介してメモリ５４に接続したプロセッサ５２を含む。入力デバイス５８および表示装置６０も、相互接続機構５６を介して、プロセッサおよびメモリに接続してある。コンピュータは、「Ｃ」のような高級プログラミング言語、またはその他のプログラミング言語を用いてプログラムして、アプリケーション・プログラムを作成することができる。このアプリケーション・プログラムは、高級プログラミング言語によるプログラムを収容するコンピュータ・ファイルをコンパイルすることによって作成する機械実行可能コードである。オペレーティング・システム（図示せず）は、このアプリケーション・プログラムの実行を制御し、そしてスケジューリング、デバッギング、入出力、メモリ管理、データ管理、およびコンピュータに関連するサービスを提供する。
コンピュータ・システム５０は、多くの商業的に入力可能な汎用計算機システムの任意のもの、例えば、カリフォルニア州マウンテン・ビュー(Mountain View)のシリコン・グラフィクス社(Silicon Graphics, Inc.)のIndigoコンピュータのような、アップル・コンピュータから入手可能なＩＲＩＸオペレーティング・システム類似のコンピュータ、あるいはその他の特注の画像処理用ワークステーションおよび他のプログラミング・システムでよい。このようなコンピュータ・システムは、例えば、インテルのペンティアム(Pentium)またはシリーズｘ８６プロセッサ、あるいはモトローラのシリーズ６８０ｘ０プロセッサのような、商業的に入手可能なプロセッサを採用している。その他の適切にプログラムされたマイクロプロセッサを用いることもできる。相互接続機構５６は、単純なバスとしたり、あるいはより複雑なスイッチング構成を含み、コンピュータ・システムの種々のエレメントと並列に通信できるようにしたりできる。また、本発明は単一プロセッサ・システムに限定されないことは理解されよう。並列処理コンピュータを含むマルチプロセッサ・システムも、本発明では使用可能である。
本発明と共に使用可能な入力デバイスに例には、マウス、トラック・ボール、ペンおよびタブレット、またはその他のポインティング・デバイス、更にはキーボード、キーパッド、スキャナおよび汎用コンピュータのために一般的に用いられている他の入力デバイスが含まれる。表示装置６０は、陰極線管（ＣＲＴ）ディスプレイ、多数の種類がある液晶ディスプレイ（ＬＣＤ），およびプリンタのようなその他の表示装置とすることができる。本発明を用いて動画ピクチャ・シーケンスを発生する場合、表示装置１０は、光印刷装置、またはビデオ・テープ・レコーダとすることができる。
図６は、図５のメモリ・システム５４について更に詳細に示す。このメモリ・システムは、磁気ディスクまたは光磁気ディスクのような、コンピュータ読取可能および書込可能な、ランダム・アクセス不揮発性記録媒体７０を含む。ディスクは、フロッピ・ディスクまたはコンパクト・ディスクとして公知の着脱自在のもの、またはハード・ドライブとして公知の固定式のものでもよい。このようなディスクは、７２で示すような、多数のトラックを有し、この中に、典型的に、二進形態、即ち、７６に示すように１および０のシーケンスとして解釈する形態で信号を格納する。このような１および０のシーケンスが、図４に示したような、境界定義、特性点、および関連するエッジ特性関数の指示を与える。この情報は、ディスク７０上に格納する。典型的には、動作中、プロセッサはデータをディスク７０から、７８で示すような集積回路メモリ・エレメントに読み出させる。集積回路メモリ７８は、情報に対しディスク７０よりも高速のアクセスを可能にする。通常、プロセッサは集積回路メモリ内のデータを操作し、次いで処理が完了したときに、データをディスク７０にコピーする。ディスク７０と集積回路メモリ７８との間のデータ移動を管理するための機構は、種々のものが公知であり、本発明はそれに限定されるものではない。また、本発明は、特定のプロセッサ、入力デバイス、出力デバイス、または相互接続機構にも限定されるものではない。
本発明によるシステムの一実施形態について、図７に関連付けて説明する。このようなシステムは、図５および図６に関連付けて先に述べたような、コンピュータ・システム上で高級コンピュータ・プログラミング言語を用いることによって実施することができる。このシステムのモジュールの１つは、モデル発生器１００であり、典型的に、グラフィカル・ユーザ・インターフェースを通じてユーザ入力１０１を受け取り、それに応答して構造化オブジェクトを発生し、これを用いて座標空間内に境界を定義する。モデル発生器１００は、例えば、イングランド、ロンドンの、元パララックス社(Parallax)であるアヴィッド・テクノロジー・ヨーロッパ社(Avid Technology Europe Ltd.)のマタドール(Matador)、ウィスコンシン州マディソンの、元エラスティック・リアリティ社(Elastic Reality)である、アヴィッド・テクノロジー(Avid Technology)のエラスティック・リアリティ(Elastic Reality)、およびカリフォルニア州マウンテン・ビューのアドビ・システムズ社(Adobe Systems, Inc.)のフォトショップ(Photoshop)のような、マット発生ソフトウェア(matte generation software)とすればよい。このようなシステムは、ユーザが入力デバイスを用いてマット(matte)を発生できるようにするものである。マットは、境界の表現として、ファイルに出力することができる。１０２に示すように、こうして発生した境界は、コンピュータのメモリ５４に格納することができる。
別のモジュールにエッジ特性定義モジュール１０４がある。これは、ユーザ入力１０３を受け取り、１０６に示すようなエッジ特性関数をユーザが定義することを可能にする。エッジ特性関数は、構造化オブジェクトによって定義した境界上の１つ以上の特性点に関連付けることができる。補間を行うか、あるいはエッジ特性を定義することにより、単一の定義を与えて、これを、境界上の位置の関数としてオブジェクト全体に適用することができる。また、エッジ特性関数の定義は、コンピュータ・メモリ５４に格納することも可能である。エッジ特性関数１０６と境界１０２との組み合わせは、構造化オブジェクトを定義した座標空間における１つの対象領域の輪郭描写を記述するには十分である。
図９Ａないし図９Ｄに関連付けて以下に更に詳細に説明するように、アンカー／距離計算モジュール１０８が、座標空間内の各点毎に、それに最も近い境界上の点（ここではアンカーと呼ぶ）を、当該境界までの距離の寸法と共に決定する。１１０で示すような各点に対するアンカーおよび距離は、コンピュータのメモリ５４に格納する。距離の寸法は、例えば、符号付き距離とすればよい。符号付き距離とは、絶対値ではなく、負または正の距離寸法であり、例えば、方向を示すために有用である。
本発明では、構造化オブジェクト定義の一群(collection)を与えることが可能である。用途によっては、所与の構造化オブジェクトにアンカー値および距離値を予め計算しておくことが好ましい場合もある。このような場合、境界定義１０２とアンカー値／距離値１１０との組み合わせは、後に使用するために、一緒にメモリ５４に格納しておく。エッジ特性関数１０６は、後で定義することができる。加えて、１組の構造化オブジェクトおよび対応するエッジ特性１０６を組み合わせて、例えば、視覚的効果のライブラリを用意することも可能である。
画像プロセッサ１１２は、境界定義または構造化オブジェクト定義１０２と、アンカー値／距離値１１０と、ならびにエッジ特性関数１０６とを受け取り、そして画像１１４を生成する。画像プロセッサが実行するプロセスについては、図１０に関連付けて以下で更に詳しく説明する。アンカー／距離計算部１０８と画像プロセッサ１１２双方の機能を組み合わせて１つのモジュールとし、双方の処理を画像毎、走査線毎に行うようにすることが可能である。画像１１４は、表示するデータを表すものとしたり、あるいはα合成システム１１６における制御画像として使用したりすることができる。この画像の他の用途および使用法については、以下で更に詳細に説明する。
図８Ａおよび図８Ｂは、エッジ特性定義の例を更に詳細に示すものであり、以下これについて説明する。これらの定義は、ＥＭＡＣＳのようなプログラム・エディタを用いて作り、２つの引数、即ち、アンカーおよび距離を受け取る手順としてエッジ特性を定義するコンピュータ・コードを発生することができる。
この実施形態では、「Ｃ」擬似コードで示しており、領域のエッジ特性は、関数Color PickColor (double dist, double anch)によって決定する。ここで、distは領域のエッジＣからの現在点Ｐの符号付き距離であり、anchはＰのＣからのアンカーである。anchは、境界Ｃ上の所定の点に関する、０と１の間の正規化値である。したがって、anchの値０および１は、Ｃが閉じている場合、双方ともＣ上の同一点を表す。同様に、distは−１および１の間の値であり、Ｐが領域の外側にある場合distは負であり、Ｃによって定義した領域の内側にＰがある場合正であるという規則を設ける。エッジ特性に最大フットプリント(MAXDIST)を用い、dist*MAXDISTが実際のＣからのＰの距離を与えるようにする。
単純なエッジ特性関数を図８Ａに示す。この関数はanchとは独立している。このエッジ特性関数が返す色は、半径方向に対称である（即ち、この関数は、一定のアンカーのいずれの半径に沿っても同一関数である）。一定のアンカーのいずれのパス上においても、返される色は、colorA（dist=1における色）とcolorB（dist=1における色）との間の直線傾斜上にある。２箇所の端部の色、および恐らくそれらの間の傾斜を慎重に選択することにより、ソフトエッジ等のような、領域の良質の輪郭描写(quality delineation)を生成することができる。
この画像表現のパワーおよび柔軟性を、図８Ｂに示すようなエッジ特性関数の定義によって例証する。このエッジ特性関数では、MixColor()は単純なブレンド関数であり、colorAを、colorBおよびcolorCを混合することによって得られる別の色と混合する。Ramp()はスムーズ関数であり、［−１，１］を関数MixColor()のドメインである［０，１］にマップする。Ramp()は、区間［WHITEOUT, 1］上のー１，１において、０を返し、区間［−１,WHITEOUT］上においてスムーズ立方傾斜（smooth cubic ramp）であり、ここでWHITEOUTは定数、例えば、０．５である。
PickColor()の定義において、MixColor()関数の適用により、２つの慎重に選択した引数を用いて、色を選択する。第１引数Ramp(dist)は、当該領域内における色の半径方向のスムーズな遷移を確保する。［WHITEOUT, 1］上の平坦部分によって、領域の中心に、均一な色（colorA）を割り当てる。中心から遠ざかるように移動するに連れて、色は他の色に変化する。これは、第２引数
(anch<0.5)? anch*2: (1-anch)*2
で制御する。これが意味するのは、anchが０．５未満の場合、値はanch*2となり、その他の場合値は(1-anch)*2となるということである。この引数は、帽子状関数(hat-shaped function)を定義し、anch=０または１においてゼロとなり、anch=0.5において１に上昇する。この関数は、輪郭描写領域の最外縁における色を、colorB (anch=0)からcolorC (anch=0.5)に変化させ、次いでcolorB(anch==1.0)に戻す。アンカー値anchが周期的であるという事実は、PickColor()も、anchに関して周期的でなければならないことを意味する。
構造化オブジェクトの定義が与えられたとして、座標空間における各ピクチャ・エレメント毎に、構造化オブジェクトによって定義した曲線上において符号付き距離およびアンカーを決定するプロセスについて、これより図９Ａないし図９Ｄとの関連において説明する。図９Ａは、構造化オブジェクト定義１０２を用いてどのようにアンカー値および距離値を計算することができるのかを記述するフローチャートである。図９Ｂは、構造化オブジェクトを用いて輪郭描写した領域をもつ座標空間Ｒの概略図である。
このプロセスでは、曲線をパラメータ化(parametrize)し、領域のエッジを定義する各点に値ｉを割り当てるようにする。曲線をパラメータ化するには多くの方法がある。ここに記載する実施形態では、曲線上の初期点にパラメータｉ＝０を割り当て、曲線上の最終点にパラメータｉ＝１を割り当てる。図９Ａに定めたプロセスの目的は、座標空間Ｒ内の各点Ｐ毎に、１）点Ｐに最も近いエッジ上の点である、領域を定義するエッジ上の点Ｑ、および２）点Ｐと点Ｑとの間の符号付き距離、を決定することである。
このプロセスにおける最初のステップは、ステップ２００であり、走査する曲線における点の画素座標を表すｘ値およびｙ値、ならびに曲線のパラメータ値ｉを初期化する。典型的には、この初期化は、それら対応する変数をゼロに設定する。勿論、他の初期値を用いてもよい。次に、ステップ２０２において、最小距離値および初期アンカーを初期値に選択する。例えば、最小距離値は、所与の座標空間を用いて予測され得る最大値に設定することもでき、アンカーは、最低のパラメータ値、例えば、ゼロを示すように設定する。
初期化値を与えた後、ステップ２０４において、現在点(x，y)と曲線上の現在点ｉとの間の符号付き距離δを決定する。このように計算した距離δが現在格納してある最小距離以下であるとステップ２０６において判定された場合、ステップ２０８において現在点に対する最小距離を、この計算した距離δに設定し、この点(x，y)に対するアンカー値を現パラメータ値ｉに設定する。次に、ステップ２１０において、値Ｎだけ増分することによりパラメータ値ｉを更新する。Ｎは１／（Ｍ−１）であり、Ｍは曲線上の点の数である。ステップ２１２において、曲線上の点の全ての分析を完了していないと判定した場合、ステップ２０４，２０６，２０８および２１０のループを繰り返す。
曲線上の点の全てを分析し終えた場合、この時点で、現在点(x，y)に対する最小距離およびそのアンカーを定義したことになる。次に、ステップ２１４においてｘ値を増分することにより、ｘ方向の次の点を選択し、パラメータ値ｉをその初期値、例えば、ゼロにリセットする。次に、ステップ２１６によって走査線の終端に到達したことを判定するまで、ステップ２０２ないし２１４を実行し続けることにより、走査線内の全ての点を辿る。走査線の終端に到達した場合、ステップ２１８においてｙ値を増分し、ｘ値を例えばゼロに初期化する。ステップ２２０によって、全ての走査線を処理したと判定するまで、ステップ２０２ないし２１８にしたがって、各走査線を処理する。ステップ２２０が完了した時には、各点に対する最小距離およびそのアンカーが決定済みとなる。
図９Ａに関連して説明したプロセスは、二次元のみについて例示したものである。このプロセスの三次元への拡張は、比較的単純であり、処理すべき第３次元のためにステップ２１８ないし２２０と同様のステップを有する追加のループ、およびステップ２０２に戻るリンクを付加すればよい。
ステップ２０４において、距離メトリック（distance metric)を用いて、座標空間内の一点と曲線上の複数の点との間の距離を測定する。使用する単純な距離メトリックは、ユークリッド距離、即ち、二乗ユークリッド距離であり、二乗根演算の実行を回避する。座標空間内のある点(x1，y1)から他の点(x2，y2)までのユークリッド距離Δは、以下の式で表す。
二次元区間において、‖Δ‖=√{(x1-x2)2+(y1-y2)2}
三次元区間において、‖Δ‖=√｛(x1-x2)2+(y1-y2)2+(z1-z2)2｝
２点間の差または類似度を測定するための他の多くの距離メトリックも公知である。ユークリッド距離は、使用する距離メトリックの一例に過ぎない。この距離は、ユークリッド距離を、領域における最大可能距離を示すファクタMAXDISTで除算することにより、［-1，1］の範囲に正規化することができる。計算した距離は、符号付き距離としてもよい。距離に対する符号を選択する１つの方法は、曲線を、座標空間を２つの領域に分割するものとみなすことである。これを行うには、曲線を、パラメータ値ｉが増大するに連れて、座標空間内を前進するものとしてみなす。ある平面において、この曲線は当該平面を２つの領域に分割する。即ち、面の右側に１つの領域と面の左側に別の領域とである。このような場合、座標空間内の点Ｐと曲線との間の符号付き距離は、点Ｐが曲線Ｃの右側にある場合正と定義し、点Ｐが曲線Ｃの左側にある場合負と定義する。
アンカー、即ち、座標空間上の所与の点に最も近い曲線上の点の識別に関して、曲線上の２箇所以上の点が、座標空間内のいずれか所与の点まで同一距離を有する場合があるということがあり得る。このような状況では、一方の点を選択しなければならない。この点を選択するプロセスは、図９Ａにおけるステップ２０６および２０８の比較および選択ステップにおいて実行することができる。図９Ａに示す実施形態では、最も大きなパラメータ値ｉを有する曲線上の点を、アンカーとして選択する。ステップ２０６の比較において「未満」比較(less than comparison)のみを行うことによって、パラメータ値ｉが最も小さい曲線上の点を選択することも可能である。パラメータ化の方位(orientation)を変更することによって、または初期化および更新ステップ２００および２１０をそれぞれ変更することによっても、同一効果を得ることができる。
図９Ａのプロセスの結果は、以下の２つの固有のスカラを表す、座標空間内の各点Ｐについての情報であり、これらをメモリに格納する。
τ  Ｐのアンカーと呼ぶ
δ  その符号付き距離
この点Ｐの順序付けた対（τ，δ）へのマッピングを、曲線Ｃの輪郭描写マップと呼ぶ。曲線Ｃの輪郭描写マップは、色のような種々の媒体によって表すことができる。例えば、曲線に関するアンカーおよび符号付き距離に基づいて色を割り当てる、カラー・マップを定義するとよい。このように、領域は、輪郭描写マップによって輪郭描写する。
図９Ａにおける、アンカーおよび符号付き距離の計算に対する力尽くの手法は、オーダーＯ（Mxy）の計算時間を必要とする。ここで、Ｍは曲線を表すパラメータの数であり、x・yは画像内の画素数である。一層効率的な計算が望ましい。
次に図９Ｃおよび図９Ｄに関連付けて、このようなプロセスについて説明する。図９Ａの実施形態と同様、この実施形態においても、二次元において、１対の座標(x，y)を表すパラメータ値ｉによって、曲線Ｃのパラメータ化を行う。コンピュータは個別の画素を処理するので、本質的に、曲線Ｃを部分線形曲線で近似し、各部分をパラメータｉで表し、２つの交点、即ち、パラメータｉに対応する点(x，y)と、パラメータｉ-1に対応する点(x，y)とを有するものとする。連続する交点間の曲線Ｃは、２つの交点間の直線上にある全ての点であるとみなす。
点Ｐから曲線Ｃまでの距離を計算するには、曲線上の無限に多い点を用いて計算する必要があるが、Ｐからその部分線形近似までの距離を計算するには、図９Ａのプロセスによって例証したように、交点の数のオーダーだけ作業を行えばよい。ＰからＣへの距離は、即ち、ＰからＣ上の任意の点までの最短距離と定義する。２種類の距離、半径方向距離と直交距離がある。半径方向距離とは、ユークリッド・メトリックのような何らかの予め定義してあるメトリックを用いた、ＰとＣの任意の交点との間の距離のことである。半径方向距離は、交点が中心にある円形ディスクを定義するものとして視覚化することができる。直交距離とは、半径方向距離を計算する際に用いるメトリックを用いた、Ｐと部分線形曲線の２つの隣接する交点間の各直線の線分との間の距離のことである。直交距離は、Ｐを通り、線分に直交する方向に引いた無限の線によって視覚化することができる。この無限の線が、線分を定める２つの交点間のある点Ｑにおいて、線分と交差する場合、直交距離を定義し、ＰとＱとの間の距離と等しいとする。一方、点Ｑが、線分を定める２つの交点の間にない場合、Ｐと線分との間の直交距離は未定義とする。
図９Ｄとの関連において以下で説明するが、このプロセスは、実際には逆を決定する。即ち、走査線(*，y)が与えられた場合、このプロセスは、曲線Ｃの２つの交点によって定義される線分によって明確に定義された直交距離を有する走査線上のｘ値を決定する。ここで、*は画像の左右の極限間の任意のｘ値を表す。加えて、これら有効なｘ値が生成する最小直交距離も決定する。
この実施形態のプロセスでは、各走査線毎の各画素について距離およびアンカーを計算する代わりに、各走査線間で更新が必要となった場合にのみ、交点毎に曲線を横切り、走査線を表すアレイ内の距離およびアンカーを更新することにより、より良い性能が得られる。このプロセスは、値MAXDISTが定義するエッジ特性によって画素が影響を受ける曲線からの最大距離に距離値およびアンカー値が左右され、曲線上の所与の点による影響を受ける可能性があるのは、１走査線内ではわずか数画素に過ぎないという事実を利用する。したがって、必要な場合にのみ各走査線について距離値およびアンカー値を更新するプロセスは、二段階で行う。ここで図９Ｅを参照する。最初に、交点からの半径方向距離では、最大距離MAXDIST内にある画素のみに、更新を行う必要がある。例えば、曲線上の点Ｐｉから半径方向距離MAXDIST以内にある走査線上の点（ｘ０とｘ２との間）のみ、更新する必要がある。第２に、各線分の端点（例えば、ＰｉおよびＰi+1によって定義される）を通過し、かつ当該線分に垂直な２本の線の現走査線上のｘ切片(x-intercept)は、計算が容易である。走査線および線分上の点間の直交距離も、計算が容易である。直交距離が最大距離MAXDISTよりも小さい場合、２つの切片（例えば、ｘ１およびｘ３）間にある画素のみを更新すればよい。
次に、図９Ｃを参照すると、この実施形態では、画像を一度に１走査線ずつ処理する。したがって、最初のステップは、ステップ２３０においてｙ値をゼロに設定することである。次に、ステップ２３２において、走査線に対して２つのアレイを発生する。第１アレイを距離テーブルと呼び、走査線に沿った各点ｘについて、曲線までの現最小距離を保持する。第２アレイをアンカー・テーブルと呼び、走査線に沿った各点ｘについて、曲線上の現在最も近い点を保持する。このように、距離テーブルおよびアンカー・テーブルは、ｘ−エントリ・アレイであり、ｘは走査線内の画素番号である。これらのアレイを発生するプロセスについては、図９Ｄに関連付けて以下で説明する。走査線上の各画素について、ステップ２３４ないしステップ２４０によって色を選択する。即ち、ステップ２３４においてｘをゼロに初期化する。現ｘ値および現走査線によって定義した画素に対する色は、現ｘ値に対する距離テーブルおよびアンカー・テーブルにおける距離値およびアンカー値にしたがって決定する（ステップ２３６）。ステップ２３８においてｘを増分し、ステップ２４０において、走査線の終端に到達したと判定するまで、これらのステップを実行する。これらのステップ２３４ないし２４０は、距離テーブルおよびアンカー・テーブルを各走査線毎に格納する場合には、図１０に関連付けて以下で説明する画像処理モジュールの一部として、別個に実行してもよい。次に、ステップ２４２においてｙ値を増分し、ステップ２４４において最終走査線を処理したと判定されるまで、後続の走査線を処理する。
ここで図９Ｄを参照し、距離テーブルおよびアンカー・テーブルを発生するプロセスについてこれより説明する。このプロセスの最初のステップは、現走査線が、曲線およびそれに関連するエッジ特性による影響を受ける画像の領域を規定する境界枠(bounding box)の範囲内にあるか否かについて判定することである（ステップ２４６）。ステップ２４６において、走査線値ｙを、境界枠を規定する最大および最小のｙ値と比較する。走査線が境界枠の外側にある場合、ステップ２４８において、アンカー値および距離値を、無限大のようなデフォルト値に設定する。
走査線が境界枠内にある場合、ステップ２５０においてパラメータ値、例えばｉを初期値、例えば、ゼロに初期化する。次に、ステップ２５２において、現パラメータｉに対応する点Ｐの画素座標(x，y)を得る。次に、ステップ２５４において、この点と現走査線との間のｙ軸に沿った距離を、値MAXDISTと比較し、この点が現走査線の距離値およびアンカー値に影響を与え得るか否かについて判定を行う。このようにして、距離がMAXDIST未満である場合、ステップ２５６において、点Ｐのｘ軸に沿ったMAXDIST内の点のみについて、点Ｐからの半径方向距離によって、距離テーブル・アレイおよびアンカー・テーブル・アレイを更新する。このように、点Ｐと、ｘ−MAXDISTとｘ＋MAXDISTとの間の走査線内の各点との間の、ユークリッド距離のような距離を計算する。ここで、ｘは点Ｐのｘ座標である。図９Ａにおけるステップ２０６および２０８と同様のステップを用いて、この距離を当該点に対する距離テーブル内の現距離と比較して、距離テーブルおよびアンカー・テーブルを更新する。ステップ２６０において曲線上の全ての点を評価し終わったと判定されるまで、ｉを増分する（ステップ２５８）ことにより、各パラメータｉ即ち曲線に沿った各点について、ステップ２５２ないし２５６を繰り返す。
ステップ２６２において、パラメータ値、例えば、ｉを初期値、例えば、ゼロに再度初期化する。次に、ステップ２６４において、現パラメータｉに対応する点Ｑの画素座標(x，y)、および直前のパラメータ（ｉ-1）に対応する点Ｐの画素座標(x，y)を得る。次に、ステップ２６６において、点ＰおよびＱによって定義した線分上への走査線の直交投影を決定し、走査線から点ＰおよびＱまでの直交距離を計算する。ステップ２６８において、直交距離を値MAXDISTと比較する。これらの長さが双方ともMAXDISTよりも長い場合、これらの点は走査線の距離値およびアンカー値に影響を与えない。そうでない場合、ステップ２７０において、点ＰおよびＱによって定義した線分上の走査線の直交投影に対応して、走査線上の最小ｘ点と走査線上の最大ｘ点との間で、距離テーブルおよびアンカー・テーブルを更新する。即ち、最小ｘ点および最大ｘ点間の走査線に沿った各点について、点ＰおよびＱによって定義した線分までの直交距離を算出する。図９Ａにおけるステップ２０６および２０８と同様のステップを用いることにより、この距離を当該点に対する距離テーブル内の現距離と比較して、距離テーブルおよびアンカー・テーブルを更新する。ステップ２７４において曲線上の全ての点を評価し終えたと判定されるまで、ｉを増分する（ステップ２７２）ことによって、各パラメータｉ即ち曲線に沿った各点について、ステップ２６４ないし２７０を繰り返す。
以上、ある領域における点についてどのようにしてアンカー値および距離値を決定するのかについて説明したので、次に、図１０との関連において、画像１１４を生成するための画像プロセッサ１１２による境界定義、エッジ特性ならびにアンカー値および距離値の使用について説明する。境界上で選択した点に対してエッジ特性関数が予め規定されていると仮定すると、画像処理の第１ステップは、これらのエッジ特性関数を補間し（ステップ３００）、境界上の各点についてエッジ特性関数を決定することである。このステップは、図８Ａにおけるように、エッジ特性関数がアンカーに独立している場合、またはオブジェクト全体に対して、アンカーの関数として定義する場合には不要である。曲線のパラメータ化を行う場合、パラメータの各値に対して、エッジ特性関数がなければならない。次に、ｘ値およびｙ値を、例えば、それぞれゼロおよびゼロに初期化し、画像の走査線処理に対処する。各点(x，y)について、当該点のアンカーに割り当てたエッジ特性関数を、ステップ３０４において選択する。ステップ３０６において、当該点に対する符号付き距離にこの関数を適用して、ここではαと呼ぶ値を得る。尚、画像内の境界は、エッジ特性によって影響を受ける区域を制限する場合があることは理解されよう。したがって、距離が何らかの最大距離よりも大きい場合、黒のようなデフォルト色を発生すべきである。各点(x，y)についてのこれらの値α全てを組み合わせて、画像１１４を定義する。次に、ステップ３０８においてｘ値を増分して、走査線を更に処理する。ステップ３１０において走査線の終端に到達したと判定されるまで、ステップ３０４ないし３０８の走査線を繰り返す。走査線の終端において、ステップ３１２でｙ値を増分し、ｘ値をその初期値、例えば、ゼロにリセットする。ステップ３１４において全ての走査線を処理し終えたと判定されるまで、ステップ３０４ないし３１２を繰り返すことにより、各走査線を処理する。こうして、ステップ３１４の完了時に、画像１１４が完成する。
先に説明したように、この画像処理機能をアンカーおよび距離の算出と組み合わせてもよい。処理機能のこの組み合わせは、例えば、図９Ａにおけるステップ２１２と２１４との間にステップ３０４および３０６を挿入することによって、実施することができる。
図１１は、発生可能な画像の一例を示す。この画像は、オブジェクト即ち曲線３２０によって定義したものである。線３２２で示す方向に定義したエッジ特性は、例えば３２４で示したものよりも長いグレースケール傾斜である。この図は、曲線上の点の関数である可変エッジ特性を使用することにより、図示の効果が作成可能であることを例示している。これは、従来技術の方法では容易に行うことはできない。
次に図１２を参照し、本発明の応用について述べる。図１２は、画像のα合成用システムのブロック図である。このようなシステムは、それぞれのフレーム記憶部８２および８４からＡｘ，ｙおよびＢｘ，ｙのような画素データを受け取るブレンダ(blender)８０を含む。フレーム記憶部８６からは、制御画像を受け取る。制御画像は、α値αｘ，ｙをブレンダ８０に供給し、ブレンダ８０は先に提示した式（１）の関数を実行して、画素Ｃｘ，ｙを出力し、そしてこの得られた画像はフレーム記憶部８８に入力する。
図１２の合成システムは、ケラー特許のような連続する同期ビデオ信号を処理するため、またはアヴィッド・テクノロジー社から入手可能であり、更にＰＣＴ公報第９４／２４８１５号に記載されているようなシステムにおけるように、間欠的でありフロー制御が行われるデジタル・ビデオ情報のストリームを処理するために、実施することができる。
画像およびデータの表現において、本発明の用途は他にもある。一般的に、このような用途は、座標空間内の値を、当該空間の境界上の最も近い点までの距離の関数として表すことを伴う。一例として、陸地のある点が水面下になる確率は、所与の点に最も近い水の現境界における点までの距離を参照することによって定義することができる。例えば、境界に沿った種々の点には、異なる確率関数を割り当てることができる。追加例として、彗星のような火の玉の動きは、その尾を定義する長いエッジ特性関数および不規則に修正されるエッジ特性を有する円として表し、その中核から出射する炎を示すことも可能である。このような表現によって発生する画像は、α合成を用いて、他の画像にブレンドすることも可能である。
構造化オブジェクト上の最も近い点までの距離の関数として、画像の画素の特性を定義するエッジ特性関数を有する構造化オブジェクトを用いることによって、更に複雑な画像も定義することができる。このような画像表現も容易に操作し、画像合成、特殊効果、アニメーションおよびモデリングを含む種々の画像処理の応用を可能にする。加えて、本発明における構造化オブジェクトは、構造化オブジェクトの利点全て、およびビット・マップの利点の多くを、特にエッジの定義において有するものである。
以上、本発明の実施形態をいくつか説明したが、これまでに述べたことは単なる例示であって限定ではなく、一例として提示したに過ぎないことは、当業者には明白であろう。多数の変更およびその他の実施形態は、当業者の範囲内であり、添付した請求の範囲に定めた本発明の範囲に該当するものとみなす。
【図１Ａ】
0003862759.tif 000002
【図１Ｂ】
0003862759.tif 000003
【図２Ａ】
0003862759.tif 000004
【図２Ｂ】
0003862759.tif 000005
【図３Ａ】
0003862759.tif 000006
【図３Ｂ】
0003862759.tif 000007
【図３Ｃ】
0003862759.tif 000008
【図３Ｄ】
0003862759.tif 000009
【図３Ｅ】
0003862759.tif 000010
【図４】
0003862759.tif 000011
【図５】
0003862759.tif 000012
【図６】
0003862759.tif 000013
【図７】
0003862759.tif 000014
【図８】
0003862759.tif 000015
【図９Ａ】
0003862759.tif 000016
【図９Ｂ】
0003862759.tif 000017
【図９Ｃ】
0003862759.tif 000018
【図９Ｄ】
0003862759.tif 000019
【図９Ｅ】
0003862759.tif 000020
【図１０】
0003862759.tif 000021
【図１１】
0003862759.tif 000022
【図１２】
0003862759.tif 000023