(57)【特許請求の範囲】
【請求項１】
輪郭線で表現された画像を走査線プロセスによって処理する画像処理方法であって、
各オブジェクトの有向境界線を確定する工程と、
前記有向境界線と注目走査線との交点を確定する工程と、
前記注目走査線の中の画素ごとに、上方向の有向境界線との交差に対してはカウントを増分し、下方向の前記有向境界線との交差に対しては前記カウントを減分する工程と、
前記オブジェクトの各画素を前記カウントの絶対値に等しい回数のレンダリングを行うレンダリング工程と
を備えることを特徴とする画像処理方法。
【請求項２】
前記オブジェクトは自己重複したオブジェクトであることを特徴とする請求項１記載の画像処理方法。
【請求項３】
前記有向境界線を規定している複数のエッジの各々に関わる方向をテーブルに記憶する工程をさらに含むことを特徴とする請求項１乃至２のいずれか１項に記載の画像処理方法。
【請求項４】
ひとつの画像の中で複数のオブジェクトを合成する画像処理方法であって、
少なくとも２つのスプラインから構成されているオブジェクトの各々の輪郭線を変換して、複数のエッジから構成される境界線を生成する工程と、
前記オブジェクトの各々について、前記複数のエッジの各々の方向を記憶して有向境界線を規定する工程と、
１本の走査線上の画素ごとに、前記画素が上方向を有するエッジに含まれる場合はカウントを増分し、前記画素が下方向を有するエッジに含まれる場合には前記カウントを減分する工程と、
前記カウントの絶対値に応じて走査線ごとの画素を色情報でレンダリングする工程とを実行して、前記画像をレンダリングする工程と
を備えることを特徴とする画像処理方法。
【請求項５】
輪郭線で表現された画像を走査線プロセスによって処理する画像処理装置であって、
各オブジェクトの有向境界線を確定する手段と、
前記有向境界線と注目走査線との交点を確定する手段と、
前記注目走査線の中の画素ごとに、上方向の有向境界線との交差に対しては前記カウントを増分し、下方向の前記有向境界線との交差に対しては前記カウントを減分する手段と、
前記オブジェクトの各画素を前記カウントの絶対値に等しい回数のレンダリングを行うレンダリング手段と
を備えることを特徴とする画像処理装置。
【請求項６】
メモリ媒体から所定のプログラムを読み込んでコンピュータを制御するコンピュータ制御装置であって、
前記メモリ媒体は、
輪郭線で表現されたオブジェクトの有向境界線を確定する工程の手順と、
前記有向境界線と注目走査線との交点を確定する工程の手順と、
前記注目走査線の中の画素ごとに、上方向の有向境界線との交差に対しては前記カウントを増分し、下方向の前記有向境界線との交差に対しては前記カウントを減分する工程の手順と、
前記オブジェクトの各画素を前記カウントの絶対値に等しい回数のレンダリングを行うレンダリング工程の手順と
を備えることを特徴とするコンピュータ制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンピュータグラフィック画像の合成に関し、特に重複するアスペクト、すなわち、「２と２分の１次元」のアスペクトを示すオブジェクトの合成に関する。
【０００２】
【従来の技術】
透明性を含むオブジェクトを合成して最終画像を作成する技法は良く知られている。「ペインタのアルゴリズム」から派生した従来の第１の方法では、各オブジェクトを通常通りに「レンダリング」して、対応する画素表現を作成する。その画素表現を他のオブジェクトの表現と組み合わせることによって、画素表現を通常通りに利用して、オブジェクトの最終画像を構成して行く。透明性を実現するためには、オブジェクトの画素ごとに、別の「アルファ」チャネル値を記憶しておく場合が多い。複数の透明性の程度を有するオブジェクトの組み合わせに関する詳細な説明については、本明細書の中にも取り入れられているPorterとDuffによる論文“Compositing Digital Images”(SIGGRAPF 84）の２５３ページから２５９ページを参照すればよい。
【０００３】
図１には、コンピュータグラフィックス画像処理システムにおいてオブジェクト２の上に重ねてレンダリングすべきオブジェクト１を示す。オブジェクト１は第１の色を有し、レンダリングの後、オブジェクト２がオブジェクト１を通して部分的に見えるという意味で部分透明であるものと定義されている。２つのオブジェクト１及び２の境界、すなわち、輪郭線は、そのようなオブジェクトを定義するために従来使用されていた技法に従って、スプラインによって規定されている。
【０００４】
次に、図２から図４を参照して、従来のアルファチャネル方法を使用した図１の画像の作成を説明する。図２では、その時点で作成されている画像は、先にレンダリングされていたオブジェクト２から構成されている。このオブジェクト２は、スプライン輪郭線とオブジェクト２の内部色の表現とから構成されている図１のフォーマットではなく、画素のアレイから構成されるように「走査変換」されている、すなわち、レンダリングされているという点で、図１のオブジェクト２とは異なっている。図３に示すオブジェクト１を（図２により定義されるような）現在状態の画像の上に合成して、オブジェクト１とオブジェクト２を共に含む図４に示す所望の画像を形成するためには、PorterとDuffのモデルに従って、オブジェクト１をそれぞれの画素が色と透明性の情報を含むような対応する画素表現へと抽象的にレンダリングし、図３の対応する画素画像を図２の画素画像と組み合わせて、図４に示すような最終画像を形成できるようにしなければならない。
【０００５】
先に述べたようにスプライン輪郭線により規定されているオブジェクト１又は２をレンダリングするためには、通常、スプライン輪郭線を、スプラインではなく線分から構成されるスプライン輪郭線の近似形に変換することが必要である。この変換プロセスは一般には「ベクトル化」として知られている。ベクトル化のプロセスは当業者には良く知られている。たとえば、Foley他が著述し、１９９０年にAddison - Wesley Publishing Companyから刊行された、本明細書の中にも取り入れられている“Computer Graphics : Principles and Practice”の４８７ページから４８８ページ及び５１１ページから５１４ページには、２つの方法が詳細に説明されている。
【０００６】
次に図５を参照すると、オブジェクト１を直線線分から構成される五つの辺６（６Ａ〜６Ｅ）を有する対応する多角形にベクトル化した結果が示されている。オブジェクト１はそれ自身の上へ「折り返され」る（doubles back）ような輪郭線を有し、オブジェクト１はそれ自身に重なり合っているので、重なり部分５にはオブジェクト１の２つの部分が存在している。
【０００７】
【発明が解決しようとする課題】
オブジェクト１が部分透明であれば、作成すべき最終画像を観察したときにその重なりがより明確になるように、重なり部分５の中に「２と２分の１」次元効果を示すことが望ましい。ところが、前述の従来の走査線方法ではこの効果を実現することが不可能である。従来の方法は、現在オブジェクトが重なり合っているか否かを判定できないという欠点を有する。
【０００８】
本発明は上記従来の技術に鑑みてなされたもので、その目的は、自己重複オブジェクトをレンダリングする効率の良い画像処理方法及び装置を提供することである。
【０００９】
【課題を解決するための手段】
上記目的を達成するために本発明の画像処理方法は次のような構成からなる。すなわち、  輪郭線で表現された画像を走査線プロセスによって処理する画像処理方法であって、各オブジェクトの有向境界線を確定する工程と、前記有向境界線と注目走査線との交点を確定する工程と、前記注目走査線の中の画素ごとに、上方向の有向境界線との交差に対してはカウントを増分し、下方向の前記有向境界線との交差に対しては前記カウントを減分する工程と、前記オブジェクトの各画素を前記カウントの絶対値に等しい回数のレンダリングを行うレンダリング工程とを備える。
【００１０】
あるいは、ひとつの画像の中で複数のオブジェクトを合成する画像処理方法であって、少なくとも２つのスプラインから構成されているオブジェクトの各々の輪郭線を変換して、複数のエッジから構成される境界線を生成する工程と、前記オブジェクトの各々について、前記複数のエッジの各々の方向を記憶して有向境界線を規定する工程と、１本の走査線上の画素ごとに、前記画素が上方向を有するエッジに含まれる場合はカウントを増分し、前記画素が下方向を有するエッジに含まれる場合には前記カウントを減分する工程と、前記カウントの絶対値に応じて走査線ごとの画素を色情報でレンダリングする工程とを実行して、前記画像をレンダリングする工程とを備える。
【００１１】
また、本発明の画像処理装置は次のような構成からなる。すなわち、輪郭線で表現された画像を走査線プロセスによって処理する画像処理装置であって、各オブジェクトの有向境界線を確定する手段と、前記有向境界線と注目走査線との交点を確定する手段と、前記注目走査線の中の画素ごとに、上方向の有向境界線との交差に対しては前記カウントを増分し、下方向の前記有向境界線との交差に対しては前記カウントを減分する手段と、前記オブジェクトの各画素を前記カウントの絶対値に等しい回数のレンダリングを行うレンダリング手段とを備える。
【００１２】
また、本発明のコンピュータ制御方法は次のような構成からなる。すなわち、メモリ媒体から所定のプログラムを読み込んでコンピュータを制御するコンピュータ制御装置であって、前記メモリ媒体は、輪郭線で表現されたオブジェクトの有向境界線を確定する工程の手順と、前記有向境界線と注目走査線との交点を確定する工程の手順と、前記注目走査線の中の画素ごとに、上方向の有向境界線との交差に対しては前記カウントを増分し、下方向の前記有向境界線との交差に対しては前記カウントを減分する工程の手順と、前記オブジェクトの各画素を前記カウントの絶対値に等しい回数のレンダリングを行うレンダリング工程の手順とを備える。
【００１３】
【発明の実施の形態】
添付の図面を参照して本発明の実施形態を説明する。
【００１４】
本実施形態においては、図５におけるベクトル化された各辺６の方向を確定する。この方向は１つの辺６から始めて、１つの閉路が完成するまで多角形の辺を巡って行くことにより確定される。多角形の辺の全てを通過したならば、各辺について、対応する走査線に対する方向が確定する。
【００１５】
次に、多角形を通常の方式を適応することで画素フォーマットに走査変換することができる。Foley他の論文の第３章に詳細に記載されている通り、従来の走査変換プロセスは、走査されている現在「走査線」７と交差するエッジの実行中エッジリスト（running edge list）を保持する（特に、Foleyの９７ページから９９ページを参照）。本実施形態においては、各エッジの方向（ｙ方向に見て上向き又は下向き）をさらに記憶するように、エッジテーブルと活動エッジリスト（active edge list）とを変形して用いる。
【００１６】
複数のオブジェクトから構成されるコンピュータ画像を作成するシステムにおいて、自己重複オブジェクトを走査線プロセスによって処理する方法のプロセスの流れ図を図７に示す。この方法は、重なり合うオブジェクトの各々について実行される次のステップから構成されている。
【００１７】
ステップ７０２では、オブジェクトの有向境界線を確定する。ステップ７０４ではその有向境界線と現在走査線との交点を確定する。ステップ７０６では、１本の走査線の中の画素ごとに、先行する交点の数のカウントを確定する。そのカウントは第１の方向の有向境界線との交差に対しては増分され、第２の方向の有向境界線との交差に対しては減分される。ステップ７０８では、オブジェクトの各画素をカウントに等しい回数だけレンダリングする。
【００１８】
自己重複オブジェクトは部分透明であっても良く、関連する透明性と色の情報を有し、レンダリングするステップは関連する透明性情報に従って色情報をカウントに等しい回数だけレンダリングするのが好ましい。
【００１９】
次に、図６を参照してこの方法を説明する。オブジェクト１は点線で示されており、図５の現在走査線７と交差するエッジはその方向を指示する矢印で示されている。走査線７の各画素をレンダリングするとき、交差するエッジ８から１１の各々についてカウントを保持する。上向き方向のエッジ８及び９が現われると、カウントは増分する。下向き方向のエッジ１０及び１１が現われたときには、カウントは減分する。走査線７上のオブジェクトの各画素はカウントの現在値の絶対値により指示される回数だけレンダリングされる。
【００２０】
図６のエッジ８に至る走査線の部分については、カウントは０であり、オブジェクト１はそれらの画素の一部を形成していない。「上向き」のエッジ８が現われると、カウントは１に増分し、PorterとDuffの方法のような従来の技法に従ってオブジェクトの色を関連する透明性と共に一度レンダリングすることができる。「上向き」のエッジ９が現われると、カウントは再び増分して２となり、オブジェクトの色は従来のPorterとDuffの方法に従って二度レンダリングされる。「下向き」のエッジ１０は逆方向であり、その結果、カウントは減分されて１となり、オブジェクト１は、エッジ１０から「下向き」のエッジ１１まで一度レンダリングされることになる。そこでまた、逆方向のエッジ１１が現われ、カウントは０まで減分し、残る走査線部分についてはゼロのままである。したがってその部分についてはレンダリングは行われない。
【００２１】
続いて、レンダリング処理は、画像のレンダリングが完了するまで従来の方式により次の走査線へと進むことができる。オブジェクト１をレンダリングする回数を確定する際に有向エッジの絶対値を利用することによって、スプラインのベクトル化で得られる有向エッジ８から１１の方向を数え上げるために最初に選択した方向は重要ではなくなる。
【００２２】
以上説明したプロセスを、たとえば、図８に示すパーソナルコンピュータ８０６を使用するコンピュータ実施方法として実現することが可能である。当該技術分野では良く知られている通り、そのようなコンピュータ８０６は、典型的には、メモリ装置に結合する中央処理装置８１０を含む。メモリ装置は中央処理装置を動作させるためのデータと命令を記憶している。たとえば、パーソナルコンピュータは一般にはデータと命令を一時的に記憶するランダムアクセスメモリ（ＲＡＭ）と、データと命令を一時的に、もしくは永久に記憶する二次記憶装置（ハードドライブ及びフロッピーディスクなど）とを含む。
【００２３】
図８に示すように、中央処理装置８１０は当該技術では良く知られているバス８２２に結合している。そのようなバスは典型的にはアドレスバス、データバス、制御信号線などを含む。このバス８２２にはランダムアクセスメモリ８１２と、読み取り専用メモリ８１４と、ハードディスクドライブ／フロッピーディスクドライブ８１６と、ビデオインタフェース８１８と、入出力インタフェース８２０とが結合している。ビデオインタフェース８１８は表示装置／モニタ８００に出力を供給する。同様に、入出力インタフェース８２０は再生装置８０２に結合している。再生装置８０２はレーザービームプリンタ、プロッタ、ドットマトリクスプリンタなどを含んでいても良い。従って、複数のオブジェクトから構成されるコンピュータ画像を走査線プロセスによって作成するシステムにおいて自己重複オブジェクトを処理する装置をこのようなパーソナルコンピュータを使用して実現できる。
【００２４】
１つの画像中で複数のオブジェクトを合成する装置９２０を図９に示す。装置９２０は１つ又は複数のオブジェクトから構成される入力９０２を受信する。装置９２０は複数のオブジェクトから構成されるコンピュータ画像を走査線プロセスを使用して作成する。入力９０２は、オブジェクトの有向境界線を確定する有向境界線確定手段９０４に供給される。有向境界線確定手段９０４の出力は、有向オブジェクトと現在走査線との交点を確定する交点確定手段９０６に供給される。有向境界線は有向境界線確定手段から受信される。交点確定手段９０６の出力は交点カウント手段９０８に供給される。交点カウント手段９０８は、１本の走査線の中の画素ごとに先行する交点の数のカウントを確定し、そのカウントは第１の方向の有向境界線交差に対しては増分し、第２の方向の有向境界線交差に対しては減分する。たとえば、「上向き」交差に対してはカウントを増分し、「下向き」交差に対してはカウントを減分する。交点カウント手段９０８の出力は画素レンダリング手段９１０に供給される。画素レンダリング手段はオブジェクトの各画素をカウントに等しい回数だけレンダリングする。これを走査線の画素ごとに、画像の全ての走査線について実行する。出力画像９１２は画素レンダリング手段９１０の出力端子で供給される。
【００２５】
さらに、本発明の実施例による方法及び／又は装置により生成されたレンダリング画像をビデオ端末表示装置（又はモニタ）８００、レーザービームプリンタ、プロッタ及びドットマトリクスプリンタを含む再生装置８０２などに出力として供給することもできる。以上、いくつかの再生装置について論じたが、本発明の範囲から逸脱せずに他の再生装置も使用可能であることは当業者には明白であろう。
【００２６】
以上、本発明の実施形態を説明したが、ここで説明した例に対して、本発明の範囲から逸脱することなく当業者には自明な変形を実施することは可能である。たとえば、上記のシステムが複数のオブジェクトを同時にレンダリングすることもできることは当業者には明らかであろう。
【００２７】
【発明の効果】
以上説明したように、本発明に係る画像処理方法及び装置は、自己重複オブジェクトを効率よくレンダリングできるという効果を奏する。
【００２８】
【図面の簡単な説明】
【図１】レンダリングすべき２つのオブジェクトを示す図である。
【図２】２つのオブジェクトのレンダリングを示す図である。
【図３】２つのオブジェクトのレンダリングを示す図である。
【図４】２つのオブジェクトのレンダリングを示す図である。
【図５】好ましい実施例に従ったベクトル化及び走査線レンダリングのプロセスを示す図である。
【図６】好ましい実施例に従って１本の走査線をレンダリングするプロセスを示す図である。
【図７】本発明の別の実施例による方法を示す流れ図である。
【図８】汎用コンピュータを示すブロック線図である。
【図９】本発明の別の実施例による装置のブロック線図である。
【符号の説明】
１，２  オブジェクト、
５  重なり部分、
６，６Ａ−６Ｅ  辺、
７  現在走査線、
８，９  上向きのエッジ、
１０，１１  下向きのエッジ、
９０２  入力、
９０４  有向境界線確定手段、
９０６  交点確定手段、
９０８  交点カウント手段、
９１０  画素レンダリング手段、
９１２  出力画像、
９２０  オブジェクト合成装置
【図１】
0003740193.tif 000002
【図２】
0003740193.tif 000003
【図３】
0003740193.tif 000004
【図４】
0003740193.tif 000005
【図５】
0003740193.tif 000006
【図６】
0003740193.tif 000007
【図７】
0003740193.tif 000008
【図８】
0003740193.tif 000009
【図９】
0003740193.tif 000010