(57)【特許請求の範囲】
【請求項１】
比較手段と判定手段と変更手段とを有する装置において画像を構成するための表現ツリーを最適化する方法であって、前記表現ツリーは少なくとも２つのノードを含み、各ノードは図形要素又は図形演算子のいずれかであり、前記ノードにより表わされる画像の１つの領域を有しており、その方法は、前記ツリーの少なくとも１つのノードについて、
前記比較手段が、前記ノードにより表わされる領域を、少なくとも１つの他のノードにより表わされる１つ又は複数の領域に対応する領域表現データ構造と比較する工程と、
前記判定手段が、前記ノードにより表わされる領域が、前記１つ又は複数の領域によって完全に又は部分的に陰に隠されるか否かを判定する工程と、
前記変更手段が、前記ノードにより表わされる領域が少なくとも一部又は完全に隠される場合に前記表現ツリーを変更する変更工程とを備える方法。
【請求項２】
前記変更工程は、前記ノードにより表わされる領域が一部隠される場合に前記ノードにクリッピング演算子を適用することを含む請求項１記載の方法。
【請求項３】
前記変更工程は、前記ノードが完全に隠される場合には、前記ノードが図形要素であれば、そのノードを除去する工程と、前記ノードが図形演算子であれば、前記図形演算子に従って所定の一連のノード置換え規則を適用する工程とを更に含む請求項１記載の方法。
【請求項４】
前記所定の一連のノード置換え規則は、
親ノードが「ｏｖｅｒ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノードを親ノードの右サブツリーと置換える工程と、
親ノードが「ｏｖｅｒ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｉｎ」図形演算子であるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｒａｔｏｐ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｒａｔｏｐ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｏｕｔ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｏｕｔ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＣ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき，親ノードを親ノードの右サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＣ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＷ」又は「Ｘｏｒ」図形演算子であり且つ現在 ノードが親ノードの左ブランチにあるとき、親ノードを親ノードの右サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＷ」又は「Ｘｏｒ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程とから構成されるグループから選択される少なくともひとつの工程を含む請求項３記載の方法。
【請求項５】
前記図形演算子は画像合成演算子である請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
前記領域表現は、階層データ構造の形態をとる請求項１記載の方法。
【請求項７】
前記階層データ構造はクアドツリー表現である請求項６記載の方法。
【請求項８】
トラバース手段と変更手段とを有する装置において画像を合成するための表現ツリーを最適化する方法であって、前記表現ツリーは複数のノードを含み、各ノードは図形要素又は図形演算子のいずれかであり且つ前記ノードにより表わされる画像の１つの領域を有しており、
前記トラバース手段が、ノードごとに表現ツリーをトラバースする工程と、
前記変更手段が、前記注目ノードにおいて表される画像の領域が、少なくとも１つの他のノードにより表わされる領域によって陰に隠されるか注目ノードにおいて判定し、注目ノードが一部又は完全に隠される場合には表現ツリーを変更する変更工程とを備える方法。
【請求項９】
前記変更工程は、前記注目ノードの除去、又は前記表現ツリーの他のノードによる前記注目ノードの置換を含む請求項８記載の方法。
【請求項１０】
前記変更工程は、前記注目ノードにより表わされる領域のクリッピング、又は後の段階でのクリッピングに備えたマーキングを更に含む請求項８記載の方法。
【請求項１１】
トラバース手段と受け取り手段と第１渡し手段と第１戻し手段と第２渡し手段と第２戻し手段と確定手段とを有する装置において画像を合成するための表現ツリーを最適化する方法であって、前記表現ツリーは複数のノードを含み、前記各ノードは図形要素又は図形演算子のいずれかを含み、且つ前記ノードにより表わされる画像の１つの領域を有しており、
前記トラバースする手段が、ノードごとに表現ツリーをトラバースする工程を含み、各注目ノードは、
（ｉ）前記受け取り手段が、親ノードから第１の領域表現を受け取る副工程と、
（ｉｉ）前記第１渡し手段が、前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す副工程と、
（ｉｉｉ）前記第１戻し手段が、前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す副工程と、
（ｉｖ）前記第２渡し手段が、前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す副工程と、
（ｖ）前記第２戻し手段が、前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す副工程と、
（ｖｉ）前記確定手段が、前記図形演算子の設定規則に従って、親ノードに戻すべき最終領域表現を確定する副工程とを適用する図形演算子を含む方法。
【請求項１２】
前記設定規則は、
（ａ）図形演算子が「ｏｖｅｒ」又は「ｐｌｕｓＣ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と前記第３の領域表現との和集合から確定されることと、
（ｂ）図形演算子が「ｉｎ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と前記第３の領域表現との共通部分から確定されることと、
（ｃ）図形演算子が「ｒａｔｏｐ」演算子である場合、親ノードに戻すべき最終領域表現は前記第２の領域表現であることと、
（ｄ）図形演算子が「ｏｕｔ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と、少なくとも注目ノードの右サブツリーのノードの境界規定ボックスにより表わされる領域を含む領域表現との差から確定されることと、
（ｅ）図形演算子が「Ｘｏｒ」又は「ｐｌｕｓＷ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現から、少なくとも注目ノードの右サブツリーのノードの境界規定ボックスにより表わされる領域を含む領域表現を減じたものと、前記第３の領域表現から、注目ノードの右サブツリーのノードの境界規定ボックスを含む領域表現を減じたものとの和集合から確定されることとから成るグループから選択される請求項１１記載の方法。
【請求項１３】
前記第１の所定の変更規則は、図形演算子が「ｏｖｅｒ」、「ｉｎ」、「ｒａｔｏｐ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」、「Ｘｏｒ」、「ｏｕｔ（左オペランドが先）」又はそれに類する演算子である場合に、変更された第１の領域表現として実質的に第１の領域表現を渡すことと、
図形演算子が「ｏｕｔ（右オペランドが先）」演算子である場合、変更された第１の領域表現として、第１の領域表現と第２の領域表現との和集合を渡すこととを含む請求項１１記載の方法。
【請求項１４】
前記第２の所定の変更規則は、図形演算子が「ｉｎ」、「ｒａｔｏｐ」、「ｏｕｔ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」、「Ｘｏｒ」又はそれに類する演算子である場合に、変更された第２の領域表現として実質的に第１の領域表現を渡すことと、図形演算子が「ｏｖｅｒ」演算子である場合、変更された第２の領域表現として、前記第１の領域表現と前記第２の領域表現との和集合を渡すこととを含む請求項１１記載の方法。
【請求項１５】
前記領域表現がその後に利用されないならば、ノードで領域表現は生成されないか、又は前記ノードの親ノードに領域表現が戻されない請求項１１乃至１４のいずれかに記載の方法。
【請求項１６】
ノードが、
「ｏｖｅｒ」演算子ノードがその親ノードに画像表現を戻す必要がないような「ｏｖｅｒ」演算子の右オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｉｎ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」又は「Ｘｏｒ」演算子の左オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｉｎ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」又は「Ｘｏｒ」演算子の右オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｏｕｔ」又は「ｒａｔｏｐ」演算子の左オペランドと、
「ｒａｔｏｐ」演算子の右オペランドと、
表現ツリーのルートと、
画像写像、アフィン変換又は畳み込み演算子と、
不透明度を維持しないか、あるいは変換ノードがその親ノードに画像表現を戻す必要がないような色変換のオペランドと
から構成されるグループから選択されるのであれば、画像表現はそのノードで生成されないか、あるいはそのノードの親ノードに戻されない請求項１５記載の方法。
【請求項１７】
画像を構成するための表現ツリーを最適化する装置であって、前記表現ツリーは少なくとも２つのノードを含み、各ノードは図形要素又は図形演算子のいずれかであり、前記ノードにより表わされる画像の１つの領域を有しており、その装置は、前記ツリーの少なくとも１つのノードについて、
前記ノードにより表わされる領域を、少なくとも１つの他のノードにより表わされる１つ又は複数の領域に対応する領域表現データ構造と比較する手段と、
前記ノードにより表わされる領域が、前記１つ又は複数の領域によって完全に又は部分的に陰に隠されるか否かを判定する手段と、
前記ノードにより表わされる領域が少なくとも一部又は完全に隠される場合に前記表現ツリーを変更する変更手段とを備える装置。
【請求項１８】
前記変更手段は、前記ノードにより表わされる領域が一部隠される場合に前記ノードにクリッピング演算子を適用することを含む請求項１７記載の装置。
【請求項１９】
前記変更手段は、
前記ノードが図形要素であり前記ノードが完全に隠されるならば、そのノードを除去する手段と、
前記ノードが図形演算子であり前記ノードが完全に隠されるならば、前記図形演算子に従って所定の一連のノード置換え規則を適用する手段とを更に含む請求項１７記載の装置。
【請求項２０】
前記所定の一連のノード置換え規則は、
親ノードが「ｏｖｅｒ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノードを親ノードの右サブツリーと置換える工程と、
親ノードが「ｏｖｅｒ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｉｎ」図形演算子であるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｒａｔｏｐ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｒａｔｏｐ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｏｕｔ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｏｕｔ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＣ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき，親ノードを親ノードの右サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＣ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＷ」又は「Ｘｏｒ」図形演算子であり且つ現在 ノードが親ノードの左ブランチにあるとき、親ノードを親ノードの右サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＷ」又は「Ｘｏｒ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程とから構成されるグループから選択される少なくともひとつの工程を含む請求項１９記載の装置。
【請求項２１】
前記図形演算子は画像合成演算子である請求項１７乃至２０のいずれかに記載の装置。
【請求項２２】
前記領域表現は、階層データ構造の形態をとる請求項１７記載の装置。
【請求項２３】
前記階層データ構造はクアドツリー表現である請求項２２記載の装置。
【請求項２４】
画像を合成するための表現ツリーを最適化する装置であって、前記表現ツリーは複数のノードを含み、各ノードは図形要素又は図形演算子のいずれかであり且つ前記ノードにより表わされる画像の１つの領域を有しており、
ノードごとに表現ツリーをトラバースする手段と、
前記注目ノードにおいて表される画像の領域が、少なくとも１つの他のノードにより表わされる領域によって陰に隠されるか注目ノードにおいて判定し、注目ノードが一部又は完全に隠される場合には表現ツリーを変更する変更手段とを備える装置。
【請求項２５】
前記変更手段は、前記注目ノードの除去、又は前記表現ツリーの他のノードによる前記注目ノードの置換を含む請求項２４記載の装置。
【請求項２６】
前記変更手段は、前記注目ノードにより表わされる領域のクリッピング、又は後の段階でのクリッピングに備えたマーキングを更に含む請求項２４記載の装置。
【請求項２７】
画像を合成するための表現ツリーを最適化する装置であって、前記表現ツリーは複数のノードを含み、前記各ノードは図形要素又は図形演算子のいずれかを含み、且つ前記ノードにより表わされる画像の１つの領域を有しており、
ノードごとに表現ツリーをトラバースするトラバース手段を備え、画像演算子を含む各注目ノードについて、前記トラバース手段は、
親ノードから第１の領域表現を受け取る手段と、
前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す手段と、
前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す手段と、
前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す手段と、
前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す手段と、
前記図形演算子の設定規則に従って、親ノードに戻すべき最終領域表現を確定する手段とを更に備える装置。
【請求項２８】
前記設定規則は、
（ａ）図形演算子が「ｏｖｅｒ」又は「ｐｌｕｓＣ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と前記第３の領域表現との和集合から確定されることと、
（ｂ）図形演算子が「ｉｎ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と前記第３の領域表現との共通部分から確定されることと、
（ｃ）図形演算子が「ｒａｔｏｐ」演算子である場合、親ノードに戻すべき最終領域表現は前記第２の領域表現であることと、
（ｄ）図形演算子が「ｏｕｔ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と、少なくとも注目ノードの右サブツリーのノードの境界規定ボックスにより表わされる領域を含む領域表現との差から確定されることと、
（ｅ）図形演算子が「Ｘｏｒ」又は「ｐｌｕｓＷ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現から、少なくとも注目ノードの右サブツリーのノードの境界規定ボックスにより表わされる領域を含む領域表現を減じたものと、前記第３の領域表現から、注目ノードの右サブツリーのノードの境界規定ボックスを含む領域表現を減じたものとの和集合から確定されることとから成るグループから選択される請求項２７記載の装置。
【請求項２９】
前記第１の所定の変更規則は、
図形演算子が「ｏｖｅｒ」、「ｉｎ」、「ｒａｔｏｐ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」、「Ｘｏｒ」、「ｏｕｔ（左オペランドが先）」又はそれに類する演算子である場合に、変更された第１の領域表現として実質的に第１の領域表現を渡すことと、
図形演算子が「ｏｕｔ（右オペランドが先）」演算子である場合、変更された第１の領域表現として、第１の領域表現と第２の領域表現との和集合を渡すこととを含む請求項２７記載の装置。
【請求項３０】
前記第２の所定の変更規則は、
図形演算子が「ｉｎ」、「ｒａｔｏｐ」、「ｏｕｔ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」、「Ｘｏｒ」又はそれに類する演算子である場合に、変更された第２の領域表現として実質的に第１の領域表現を渡すことと、
図形演算子が「ｏｖｅｒ」演算子である場合、変更された第２の領域表現として、前記第１の領域表現と前記第２の領域表現との和集合を渡すこととを含む請求項２７記載の装置。
【請求項３１】
前記領域表現がその後に利用されないならば、ノードで領域表現は生成されないか、又は前記ノードの親ノードに領域表現が戻されない請求項２７乃至３０のいずれかに記載の装置。
【請求項３２】
ノードが、
「ｏｖｅｒ」演算子ノードがその親ノードに画像表現を戻す必要がないような「ｏｖｅｒ」演算子の右オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｉｎ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」又は「Ｘｏｒ」演算子の左オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｉｎ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」又は「Ｘｏｒ」演算子の右オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｏｕｔ」又は「ｒａｔｏｐ」演算子の左オペランドと、
「ｒａｔｏｐ」演算子の右オペランドと、表現ツリーのルートと、画像写像、アフィン変換又は畳み込み演算子と、不透明度を維持しないか、あるいは変換ノードがその親ノードに画像表現を戻す必要がないような色変換のオペランドと
から構成されるグループから選択されるのであれば、画像表現はそのノードで生成されないか、あるいはそのノードの親ノードに戻されない請求項３１記載の装置。
【請求項３３】
画像を構成するための表現ツリーを最適化するプログラムを格納するコンピュータ可読の記憶媒体であって、前記表現ツリーは少なくとも２つのノードを含み、各ノードは図形要素又は図形演算子のいずれかであり、前記ノードにより表わされる画像の１つの領域を有しており、前記ツリーの少なくとも１つのノードについて、
前記ノードにより表わされる領域を、少なくとも１つの他のノードにより表わされる１つ又は複数の領域に対応する領域表現データ構造と比較する手段と、
前記ノードにより表わされる領域が、前記１つ又は複数の領域によって完全に又は部分的に陰に隠されるか否かを判定する手段と、
前記ノードにより表わされる領域が少なくとも一部又は完全に隠される場合に前記表現ツリーを変更する変更手段としてコンピュータを機能させるためのプログラムを記憶したことを特徴とする記憶媒体。
【請求項３４】
前記変更手段は、前記ノードにより表わされる領域が一部隠される場合に前記ノードにクリッピング演算子を適用することを含む請求項３３記載の記憶媒体。
【請求項３５】
前記変更手段は、前記ノードが完全に隠される場合には、前記ノードが図形要素であれば、そのノードを除去する手段と、前記ノードが図形演算子であれば、前記図形演算子に従って所定の一連のノード置換え規則を適用する手段とを更に含む請求項３３記載の記憶媒体。
【請求項３６】
前記所定の一連のノード置換え規則は、
親ノードが「ｏｖｅｒ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノードを親ノードの右サブツリーと置換える工程と、
親ノードが「ｏｖｅｒ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｉｎ」図形演算子であるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｒａｔｏｐ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｒａｔｏｐ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｏｕｔ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき、親ノード及び親ノードから枝分かれする全てのサブツリーを除去する工程と、
親ノードが「ｏｕｔ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＣ」図形演算子であり且つ注目ノードが親ノードの左ブランチにあるとき，親ノードを親ノードの右サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＣ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＷ」又は「Ｘｏｒ」図形演算子であり且つ現在 ノードが親ノードの左ブランチにあるとき、親ノードを親ノードの右サブツリーと置き換える工程と、
親ノードが「ｐｌｕｓＷ」又は「Ｘｏｒ」図形演算子であり且つ注目ノードが親ノードの右ブランチにあるとき、親ノードを親ノードの左サブツリーと置き換える工程とから構成されるグループから選択される少なくともひとつの工程を含む請求項３５記載の記憶媒体。
【請求項３７】
前記図形演算子は画像合成演算子である請求項３３乃至３６のいずれかに記載の記憶媒体。
【請求項３８】
前記領域表現は、階層データ構造の形態をとる請求項３３記載の記憶媒体。
【請求項３９】
前記階層データ構造はクアドツリー表現である請求項３８記載の記憶媒体。
【請求項４０】
画像を合成するための表現ツリーを最適化するプログラムを格納するコンピュータ可読の記憶媒体であって、前記表現ツリーは複数のノードを含み、各ノードは図形要素又は図形演算子のいずれかであり且つ前記ノードにより表わされる画像の１つの領域を有しており、
ノードごとに表現ツリーをトラバースする手段と、
前記注目ノードにおいて表される画像の領域が、少なくとも１つの他のノードにより表わされる領域によって陰に隠されるか注目ノードにおいて判定し、注目ノードが一部又は完全に隠される場合には表現ツリーを変更する変更手段としてコンピュータを機能させるためのプログラムを記憶したことを特徴とする記憶媒体。
【請求項４１】
前記変更手段は、前記注目ノードの除去、又は前記表現ツリーの他のノードによる前記注目ノードの置換を含む請求項４０記載の記憶媒体。
【請求項４２】
前記変更手段は、前記注目ノードにより表わされる領域のクリッピング、又は後の段階でのクリッピングに備えたマーキングを更に含む請求項４０記載の記憶媒体。
【請求項４３】
画像を合成するための表現ツリーを最適化するプログラムを格納するコンピュータ可読の記憶媒体であって、前記表現ツリーは複数のノードを含み、前記各ノードは図形要素又は図形演算子のいずれかを含み、且つ前記ノードにより表わされる画像の１つの領域を有しており、
ノードごとに表現ツリーをトラバースするトラバース手段としてコンピュータを機能させるプログラムを記憶した記憶媒体であって、前記各注目ノードは画像演算子を含み、前記トラバース手段は、
（ｉ）親ノードから第１の領域表現を受け取る手段と、
（ｉｉ）前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す手段と、
（ｉｉｉ）前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す手段と、
（ｉｖ）前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す手段と、
（ｖ）前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す手段と、
（ｖｉ）前記図形演算子の設定規則に従って、親ノードに戻すべき最終領域表現を確定する手段とを含む記憶媒体。
【請求項４４】
前記設定規則は、
（ａ）図形演算子が「ｏｖｅｒ」又は「ｐｌｕｓＣ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と前記第３の領域表現との和集合から確定されることと、
（ｂ）図形演算子が「ｉｎ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と前記第３の領域表現との共通部分から確定されることと、
（ｃ）図形演算子が「ｒａｔｏｐ」演算子である場合、親ノードに戻すべき最終領域表現は前記第２の領域表現であることと、
（ｄ）図形演算子が「ｏｕｔ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現と、少なくとも注目ノードの右サブツリーのノードの境界規定ボックスにより表わされる領域を含む領域表現との差から確定されることと、
（ｅ）図形演算子が「Ｘｏｒ」又は「ｐｌｕｓＷ」演算子である場合、親ノードに戻すべき最終領域表現は、前記第２の領域表現から、少なくとも注目ノードの右サブツリーのノードの境界規定ボックスにより表わされる領域を含む領域表現を減じたものと、前記第３の領域表現から、注目ノードの右サブツリーのノードの境界規定ボックスを含む領域表現を減じたものとの和集合から確定されることとから成るグループから選択される請求項４３記載の記憶媒体。
【請求項４５】
前記第１の所定の変更規則は、
図形演算子が「ｏｖｅｒ」、「ｉｎ」、「ｒａｔｏｐ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」、「Ｘｏｒ」、「ｏｕｔ（左オペランドが先）」又はそれに類する演算子である場合に、変更された第１の領域表現として実質的に第１の領域表現を渡すことと、
図形演算子が「ｏｕｔ（右オペランドが先）」演算子である場合、変更された第１の領域表現として、第１の領域表現と第２の領域表現との和集合を渡すこととを含む請求項４３記載の記憶媒体。
【請求項４６】
前記第２の所定の変更規則は、
図形演算子が「ｉｎ」、「ｒａｔｏｐ」、「ｏｕｔ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」、「Ｘｏｒ」又はそれに類する演算子である場合に、変更された第２の領域表現として実質的に第１の領域表現を渡すことと、
図形演算子が「ｏｖｅｒ」演算子である場合、変更された第２の領域表現として、前記第１の領域表現と前記第２の領域表現との和集合を渡すこととを含む請求項４３記載の記憶媒体。
【請求項４７】
前記領域表現がその後に利用されないならば、ノードで領域表現は生成されないか、又は前記ノードの親ノードに領域表現が戻されない請求項４３乃至４６のいずれかに記載の記憶媒体。
【請求項４８】
ノードが、
「ｏｖｅｒ」演算子ノードがその親ノードに画像表現を戻す必要がないような「ｏｖｅｒ」演算子の右オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｉｎ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」又は「Ｘｏｒ」演算子の左オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｉｎ」、「ｐｌｕｓＣ」、「ｐｌｕｓＷ」又は「Ｘｏｒ」演算子の右オペランドと、
演算子ノードがその親ノードに画像表現を戻す必要がないような「ｏｕｔ」又は「ｒａｔｏｐ」演算子の左オペランドと、
「ｒａｔｏｐ」演算子の右オペランドと、
表現ツリーのルートと、
画像写像、アフィン変換又は畳み込み演算子と、
不透明度を維持しないか、あるいは変換ノードがその親ノードに画像表現を戻す必要がないような色変換のオペランドと
から構成されるグループから選択されるのであれば、画像表現はそのノードで生成されないか、あるいはそのノードの親ノードに戻されない請求項４７記載の記憶媒体。
【請求項４９】
比較手段と判定手段と修正手段とを有する装置において画像を構成するための少なくとも２つの図形要素又は図形演算子のいずれかのノードを含む表現ツリーを最適化する方法であって、
前記比較手段が、前記ノードの第１の領域と表現ツリーの他のノードの少なくとも一つから得られる第２の領域とを比較するステップと、
前記判定手段が、前記第１領域が、前記第２の領域によって完全に又は部分的に陰に隠されるか否かを判定するステップと、
前記修正手段が、最適化された表現ツリーを形成するために、前記第２領域により少なくとも一部又は完全に隠される第１の領域を表す表現ツリーを修整するステップとを有し、
ツリーの最適化された部分は前記第１の領域の隠されない領域を表すことを特徴とする表現ツリーを最適化する方法。
【請求項５０】
画像を構成するための少なくとも２つの図形要素又は図形演算子のいずれかのノードを含む表現ツリーを最適化する装置であって、
前記ノードの第１の領域と表現ツリーの他のノードの少なくとも一つから得られる第２の領域とを比較する手段と、
前記第１領域が、前記第２の領域によって完全に又は部分的に陰に隠されるか否かを判定する手段と、
最適化された表現ツリーを形成するために、前記第２領域により少なくとも一部又は完全に隠される第１の領域を表す表現ツリーを修整する手段とを有し、
ツリーの最適化された部分は前記第１の領域の隠されない領域を表すことを特徴とする表現ツリーを最適化する装置。
【請求項５１】
トラバース手段と受け取り手段と第１渡し手段と第１戻し手段と第２渡し手段と第２戻し手段と確定手段とを有する装置において画像を合成するための図形要素又は図形演算子のいずれかを含む複数のノードを含む表現ツリーを最適化する方法であって、
前記トラバース手段が、ノードごとに表現ツリーをトラバースする工程を含み、
前記トラバースする工程は、
（ｉ）前記受け取り手段が、親ノードから第１の領域表現を受け取る工程と、
（ｉｉ）前記第１渡し手段が、前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す工程と、
（ｉｉｉ）前記第１戻し手段が、前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す工程と、
（ｉｖ）前記第２渡し手段が、前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す工程と、
（ｖ）前記第２戻し手段が、前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す工程と、
（ｖｉ）前記確定手段が、前記図形演算子の設定規則に従って、最適な表現ツリーを形成するため親ノードに戻すべき最終領域表現を確定する工程とを有し、
最終領域は実質的に現在のノードが表現木の他のノードを隠してしまうことができる領域であることを特徴とする表現ツリーを最適化する方法。
【請求項５２】
画像を合成するための複数の図形要素又は図形演算子のいずれかを含むノードを含む表現ツリーを最適化する装置であって、
ノードごとに表現ツリーをトラバースする手段を含み、
前記トラバースする手段は、
（ｉ）親ノードから第１の領域表現を受け取る手段と、
（ｉｉ）前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す手段と、
（ｉｉｉ）前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す手段と、
（ｉｖ）前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す手段と、
（ｖ）前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す手段と、
（ｖｉ）前記図形演算子の設定規則に従って、最適な表現ツリーを形成するため親ノードに戻すべき最終領域表現を確定する手段とを有し、
最終領域は実質的に現在のノードが表現木の他のノードを隠してしまうことができる領域であることを特徴とする表現ツリーを最適化する装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、静止画とビデオ映像双方の形態をとるコンピュータ生成画像の生成に関し、特に、複数の成分を合成することにより作成される画像の生成の方法及び装置およびコンピュータ可読のプログラムを格納する記憶媒体に関する。
【０００２】
【従来の技術】
通常、コンピュータ生成画像は、レンダリングされて最終的な画像を生成するためにひとつに合成された多数の異なる成分、すなわち、図形要素で構成されている。近年、「不透明度チャネル(opacity channel)」（「艶消し(matte)」、「アルファチャネル」、又は単純に「不透明度(opacity)」としても知られている）が一般に使用されている。不透明度チャネルは、各要素の透明性に関する情報を含む。不透明チャネルは各色の例と共に記憶されるので、たとえば、不透明度を伴った画素を基にした画像は、各画素の表現の一部として不透明度値を記憶する。明示された不透明度チャネル情報をもたない要素は、通常、その要素の定められた境界の中で全く不透明であるとされ、その境界の外では完全に透明であるとされる。
【０００３】
表現ツリーは、画像のオブジェクト、すなわち、要素をレンダリングするための系統的手段あるいは表現を提供する。表現ツリーはリーフノードと、内部ノードと、ひとつのルートノードを含む複数のノードから構成される。表現ツリーの最も外側にあるノードであるリーフノードはその下のノードをもたず、１つ又は複数の図形要素から構成される。内部ノードは、通常、左右のサブツリーに枝分かれし、各サブツリーそれ自体が少なくとも１つのリーフノードを含む表現ツリーになっている。表現ツリーの内部ノードは、左右のサブツリーを演算子のオペランドとして扱う合成演算子である。表現ツリーの第１のノードは一般にルートノードと呼ばれる。表現ツリーのルートノードは最終画像を表わし、ツリーの各ノードは最終画像の一部を表わす。
【０００４】
【発明が解決しようとする課題】
１つの図形要素自体はある大きさを有しているであろうが、その要素が最終画像の中で完全に見える必要はなく、要素のごく一部が最終画像に影響を及ぼす場合があってもよい。たとえば、ある大きさの画像を表示装置に表示するものとする。しかしながら、画像の左上角だけを表示装置により表示し、画像のその他の部分は表示しないように画像を位置決めした場合、表示装置に表示される最終画像はその画像の見える部分から成り、そのような場合には、見えない部分をレンダリングする必要はない。
【０００５】
要素のごく一部だけが影響を及ぼすもう１つの状況は、その部分が別の要素によって陰に隠されてしまうときである。たとえば、表示すべき（又はレンダリングすべき）最終画像が１つ又は複数の不透明な図形要素を含んでいる場合、そのうちいくつかの図形要素は他の図形要素を隠す。従って、陰に隠される要素は最終画像には影響を及ぼさない。
【０００６】
最終画像に影響を及ぼさない要素、又は要素の部分を識別できるのであれば、それらの要素（又は部分）をレンダリングする必要がないので、相当な時間とおそらくはメモリの節約になる。
【０００７】
従来の方法においては、少なくとも重なり合いが生じる画像について、透明な図形オブジェクトを容易に処理できず、また、あらゆる合成演算子を処理できないため問題が起こる。従って、少なくともそれらの問題の１つ又は複数を改善することが望ましい。
【０００８】
本発明はこの目的を達成するためになされたもので、オブジェクト間の重なり合いが生じる画像について、最終画像に影響を及ぼさない要素、又は要素の部分を識別できるため、それらの要素（又は部分）をレンダリングする必要がないので、処理な時間とメモリとを節約し、また、あらゆる合成演算子を処理するための表現ツリーの最適化方法および装置を提供することを目的とする。
【課題を解決するための手段】
上記目的を達成するために本発明は次のような構成から成る。すなわち、比較手段と判定手段と変更手段とを有する装置において画像を構成するための表現ツリーを最適化する方法であって、前記表現ツリーは少なくとも２つのノードを含み、各ノードは図形要素又は図形演算子のいずれかであり、前記ノードにより表わされる画像の１つの領域を有しており、その方法は、前記ツリーの少なくとも１つのノードについて、前記比較手段が、前記ノードにより表わされる領域を、少なくとも１つの他のノードにより表わされる１つ又は複数の領域に対応する領域表現データ構造と比較する工程と、前記判定手段が、前記ノードにより表わされる領域が、前記１つ又は複数の領域によって完全に又は部分的に陰に隠されるか否かを判定する工程と、前記変更手段が、前記ノードにより表わされる領域が少なくとも一部又は完全に隠される場合に前記表現ツリーを変更する変更工程とを備える。
【０００９】
あるいは、トラバース手段と変更手段とを有する装置において画像を合成するための表現ツリーを最適化する方法であって、前記表現ツリーは複数のノードを含み、各ノードは図形要素又は図形演算子のいずれかであり且つ前記ノードにより表わされる画像の１つの領域を有しており、前記トラバース手段が、ノードごとに表現ツリーをトラバースする工程と、前記変更手段が、前記注目ノードにおいて表される画像の領域が、少なくとも１つの他のノードにより表わされる領域によって陰に隠されるか注目ノードにおいて判定し、注目ノードが一部又は完全に隠される場合には表現ツリーを変更する変更工程とを備える。
【００１０】
あるいは、トラバース手段と受け取り手段と第１渡し手段と第１戻し手段と第２渡し手段と第２戻し手段と確定手段とを有する装置において画像を合成するための表現ツリーを最適化する方法であって、前記表現ツリーは複数のノードを含み、前記各ノードは図形要素又は図形演算子のいずれかを含み、且つ前記ノードにより表わされる画像の１つの領域を有しており、前記トラバースする手段が、ノードごとに表現ツリーをトラバースする工程を含み、各注目ノードは、（ｉ）前記受け取り手段が、親ノードから第１の領域表現を受け取る副工程と、（ｉｉ）前記第１渡し手段が、前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す副工程と、（ｉｉｉ）前記第１戻し手段が、前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す副工程と、（ｉｖ）前記第２渡し手段が、前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す副工程と、（ｖ）前記第２戻し手段が、前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す副工程と、（ｖｉ）前記確定手段が、前記図形演算子の設定規則に従って、親ノードに戻すべき最終領域表現を確定する副工程とを適用する図形演算子を含む。
【００１１】
あるいは
画像を構成するための表現ツリーを最適化する装置であって、前記表現ツリーは少なくとも２つのノードを含み、各ノードは図形要素又は図形演算子のいずれかであり、前記ノードにより表わされる画像の１つの領域を有しており、その装置は、前記ツリーの少なくとも１つのノードについて、
前記ノードにより表わされる領域を、少なくとも１つの他のノードにより表わされる１つ又は複数の領域に対応する領域表現データ構造と比較する手段と、
前記ノードにより表わされる領域が、前記１つ又は複数の領域によって完全に又は部分的に陰に隠されるか否かを判定する手段と、
前記ノードにより表わされる領域が少なくとも一部又は完全に隠される場合に前記表現ツリーを変更する変更手段とを備える。
【００１２】
あるいは、
画像を合成するための表現ツリーを最適化する装置であって、前記表現ツリーは複数のノードを含み、各ノードは図形要素又は図形演算子のいずれかであり且つ前記ノードにより表わされる画像の１つの領域を有しており、
ノードごとに表現ツリーをトラバースする手段と、
前記注目ノードにおいて表される画像の領域が、少なくとも１つの他のノードにより表わされる領域によって陰に隠されるか注目ノードにおいて判定し、注目ノードが一部又は完全に隠される場合には表現ツリーを変更する変更手段とを備える。
【００１３】
あるいは、
画像を合成するための表現ツリーを最適化する装置であって、前記表現ツリーは複数のノードを含み、前記各ノードは図形要素又は図形演算子のいずれかを含み、且つ前記ノードにより表わされる画像の１つの領域を有しており、
ノードごとに表現ツリーをトラバースする手段を備え、画像演算子を含む各注目ノードについて、前記トラバース手段は、
親ノードから第１の領域表現を受け取る手段と、
前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す手段と、
前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す手段と、
前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す手段と、
前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す手段と、
前記図形演算子の設定規則に従って、親ノードに戻すべき最終領域表現を確定する手段と
を更に備える。
【００１４】
あるいは、画像を構成するための表現ツリーを最適化するプログラムを格納するコンピュータ可読の記憶媒体であって、前記表現ツリーは少なくとも２つのノードを含み、各ノードは図形要素又は図形演算子のいずれかであり、前記ノードにより表わされる画像の１つの領域を有しており、前記ツリーの少なくとも１つのノードについて、前記ノードにより表わされる領域を、少なくとも１つの他のノードにより表わされる１つ又は複数の領域に対応する領域表現データ構造と比較する手段と、前記ノードにより表わされる領域が、前記１つ又は複数の領域によって完全に又は部分的に陰に隠されるか否かを判定する手段と、前記ノードにより表わされる領域が少なくとも一部又は完全に隠される場合に前記表現ツリーを変更する変更手段としてコンピュータを機能させるためのプログラムを記憶したことを特徴とする。
【００１５】
あるいは、画像を合成するための表現ツリーを最適化するプログラムを格納するコンピュータ可読の記憶媒体であって、前記表現ツリーは複数のノードを含み、各ノードは図形要素又は図形演算子のいずれかであり且つ前記ノードにより表わされる画像の１つの領域を有しており、ノードごとに表現ツリーをトラバースする手段と、前記注目ノードにおいて表される画像の領域が、少なくとも１つの他のノードにより表わされる領域によって陰に隠されるか注目ノードにおいて判定し、注目ノードが一部又は完全に隠される場合には表現ツリーを変更する変更手段としてコンピュータを機能させるためのプログラムを記憶したことを特徴とする。
【００１６】
あるいは、画像を合成するための表現ツリーを最適化するプログラムを格納するコンピュータ可読の記憶媒体であって、前記表現ツリーは複数のノードを含み、前記各ノードは図形要素又は図形演算子のいずれかを含み、且つ前記ノードにより表わされる画像の１つの領域を有しており、ノードごとに表現ツリーをトラバースするトラバース手段としてコンピュータを機能させるプログラムを記憶した記憶媒体であって、前記各注目ノードは画像演算子を含み、前記トラバース手段は、（ｉ）親ノードから第１の領域表現を受け取る手段と、（ｉｉ）前記図形演算子の第１のオペランドに、前記演算子に関する第１の所定の変更規則に従って変更された第１の領域表現を渡す手段と、（ｉｉｉ）前記第１のオペランドと関連するサブツリーによって隠される領域の第２の領域表現を図形演算子に戻す手段と、（ｉｖ）前記図形演算子の第２のオペランドに、前記演算子に関する第２の所定の変更規則に従って変更された第２の領域表現を渡す手段と、（ｖ）前記第２のオペランドと関連するサブツリーによって隠される領域の第３の領域表現を図形演算子に戻す手段と、（ｖｉ）前記図形演算子の設定規則に従って、親ノードに戻すべき最終領域表現を確定する手段とを含む。
【００１７】
【発明の実施の形態】
本発明の好ましい実施形態においては、ここで説明するような画像合成表現ツリーがレンダリングすべき画像に関して既に確定されているものとする。
【００１８】
好ましくは、画像領域の表現は、ひとつの画像の領域または部分を表現するのに適した、画像処理に用いられる階層的なデータ構造である。このような画像領域の表現のひとつが、本発明の技術分野において通常の技術知識を有する者により、「クアドツリー(quadtrees)」として知られている。画像領域の表現の他の形式でも同じ目的のために利用できる。簡単にするために、画像領域の表現はこれ以降クアドツリーであるものとする。
【００１９】
典型的には、画像領域を表すクアドツリーの生成には、その領域を複数のセルに細分することが必要である。各セルは、クアドツリーのひとつのノードによって表される。それゆえ、画像領域の細分の数が増えるにつれてクアドツリーのノード数も増え、それによってクアドツリーの深さと、クアドツリーにより表される領域の解像度が増していく。
＜合成演算＞
１つの画像の２つの部分を組み合わせるための主要な合成演算は、１３種類ある。それらの合成演算それぞれの機能を以下の表１に挙げる。表１の中で、Ｄｃは事前乗算済デスティネーション又は合成色であり、Ｄｏはデスティネーション又は合成αチャネル値であり、Ａｃは第１の画像源Ａの第１の部分の事前乗算済画素色であり、Ａｏは色がＡｃである画素に対応するα値であり、Ｂｃは第２の画像源Ｂの画像の一部の事前乗算済画素色値であり、Ｂｏは画像源ＢのＢｃに対応する画素のαチャネル値である。
【００２０】
【表１】
0003996975.tif 000002
【００２１】
表１は、２つの異なる画像を異なる演算子を利用して組み合わせる様々な合成方法を特に示している。別の不可的な演算子も可能である。それらの付加的な演算子は主に特殊効果を実現するために利用される。
【００２２】
「ｐｌｕｓＷ」演算子の性質である「包み込み(wrap around)」は、たとえば、Ａｃ＋Ｂｃの加算値が色成分の最大値より大きい場合に、その値を、色空間内の最小値に関して再びスタートさせるために「包み込む」ことを意味している。あるいは、「ｐｌｕｓＣ」により利用される「固定(clamping)」のプロセスは、たとえば、Ａｃ＋Ｂｃの加算値が色成分より大きいときに、その加算値をその色成分の最大値に固定すること(clamping)を含む。
【００２３】
図１は、表１に挙げたような様々な演算を利用して、２つの完全に不透明な円Ａ及びＢを合成するときに生成される最終画像の様々な例を示している。なお、演算子「ｒｏｖｅｒ」、「ｒｉｎ」、「ｒｏｕｔ」及び「ｒａｔｏｐ」は、オペランドを「ｒ」（逆）演算子にスワッピングして、それぞれ対応する演算子「ｏｖｅｒ」、「ｉｎ」、「ｏｕｔ」及び「ａｔｏｐ」を適用することと等価である。
【００２４】
本実施の形態では、表現ツリーは、２項合成演算子、単項演算子及びプリミティブを含む多様なノード型を含むことができる。単項演算子は、典型的には、色変換、画像畳み込み、アフィン変換及び画像の写像(warping)を含む。プリミティブは、典型的には、画素を基にした画像、スプラインを基にした径路、テキスト、「ａｌｌ」（「ａｌｌ」は生成中の画像全体のサイズにわたる図形要素である）、エッジブレンド、ボックスなどの図形要素を含む。
＜２項合成演算子＞
表２は、一連の２項合成演算子と、表現ツリーを単純化する場合にそれらの演算子を処理するときに実行されるべきアクションとのセットのリストである。
【００２５】
【表２】
0003996975.tif 000003
【００２６】
１つの演算子により表わされる表現ツリーのノードにおいては、通常、表現ツリーを単純化するプロセスの中で、クアドツリーなどの領域表現は各オペランドに渡される。演算子を比較するノードでは、ノードから枝分かれするサブツリーを消滅させるべきであるか否か（すなわち、枝を刈り込まねばならないか否か）、又は、図形要素の陰にならない部分に対応するクアドツリーをこのノードから戻すべきであるか否かに関して、他のノードでそれ以降の処理を可能にするために、アクションを実行すべきである。
【００２７】
表２においては、以下の表記を使用している。
【００２８】
ｑ0           ：ノードに渡されたクアドツリー
ｑL，ｑR      ：左右のサブツリーにより戻され、表２の演算子の左右のオペランドに対応するクアドツリー
ｑ1∩ｑ2
ｑ1∪ｑ2      ：クアドツリー設定演算
ｑ1−ｑ2
Ｂ（ｎｏｄｅ）：ノードの境界ボックスを完全に含むクアドツリー
表２の最後の２つの列の中で、代表的な置換規則が記述されている。そこでは「Ｌ」は注目ノードを注目ノードから枝分かれする左側のサブツリーと置換えることを意味し、「Ｒ」は注目ノードを注目ノードから枝分かれする右側のサブツリーと置換えることを意味し、「Ｖ」は注目ノードが消滅することを意味する。「消滅」すべきノードは、そのノードにより表わされる画像の領域が他の図形要素によって陰になることを意味する。そのため、そのノードは最終画像に全く影響を及ぼさない。双方のオペランドが消滅すれば、注目ノードも消滅する。
【００２９】
逆演算子を表２に説明されている演算子に置き換えることもできる。「Ａ ｏｖｅｒ Ｂ」として記載されている「ｏｖｅｒ」演算子は、画像要素Ａが画像要素Ｂを覆うことを意味する。例えば、これは、通常は「ｒｏｖｅｒ」（reverse over)と表される「ｏｖｅｒ」演算子の逆演算子により置き換えることができ、「Ｂ rover Ａ」は、画像要素「Ａ」及び「Ｂ」の合成において、「Ａ over Ｂ」と同じ結果をもたらす。
＜２項合成演算子の例＞
実例として、表２の一番上の「演算子」の行の第１の演算子（すなわち、「ｏｖｅｒ」演算子）を考える。「ｏｖｅｒ」演算子により表わされる表現ツリーの注目ノードにおいて、親ノードは注目ノードにクアドツリーｑ0を渡す。「左オペランドに渡す」の見出し（表２の列２）の下に示されるアクションに続いて、クアドツリーｑ0は、左オペランド、すなわち左サブツリーあるいは注目ノードにおける枝に渡される。
【００３０】
クアドツリーｑ0は左オペランドを処理するために使用され、クアドツリーｑLは左オペランドの陰領域として戻される。「右オペランドに渡す」（表２の列３）から、注目ノードで実行されるアクションは、右オペランドとして、親ノードであるクアドツリーｑ0と、その時点で戻された左オペランドのクアドツリーｑLとの和集合を渡すはずである。この和集合（ｑ0 ∪ ｑL）の結果として得られるクアドツリーは、右オペランドを処理するために使用される。クアドツリーｑRは右オペランドの陰領域として注目ノードに戻される。次に、注目ノードは表２の列４に「ｒｅｔｕｒｎ」によって説明されているように、左オペランドｑLと右オペランドｑRとの和集合（ｑL ∪ｑR ）を親ノードに戻す。
【００３１】
左オペランドにより表わされる領域が左オペランドに渡されたクアドツリーｑ0によって完全に隠されることがわかったならば、表２の列５の「左オペランドが消滅した場合」のアクションは、注目ノードを右サブツリー（「Ｒ」）すなわち、右オペランドと置換える。注目ノードをその右側のオペランドと置換えることによってツリーを変更しても、レンダリングされる画像(rendered image)は変わらないが、画像をレンダリングするために要する時間の点で改善が見られることから、これは望ましいことである。
【００３２】
同様に、右オペランドにより表わされる領域が右オペランドに渡されたクアドツリー（ｑ0 ∪ｑL ）によって完全に隠されることがわかったならば、表２の列６の「右オペランドが消滅した場合」のアクションは、注目ノードを左側のサブツリー（「Ｌ」）と置換える。
＜単項演算子＞
表現ツリーを簡略化するときの単項演算子の扱いは演算の種類に依存している。
【００３３】
（ａ）色変換においては、クアドツリーｑ0は色変換演算子のオペランドに渡される。変換が不透明さを維持するのであれば（すなわち、変換後も不透明画素が不透明のままであるならば）、オペランドから戻されるクアドツリーは単項演算子により戻される。言い換えれば、そのオペランドは、色変換の結果が陰に隠す領域を隠すということである。変換が不透明さを維持しない場合には、単項演算が陰にする領域を確定できないので、単項演算子は空のクアドツリーを戻す。オペランドが消滅すれば、不可視状態（不透明度がゼロ）が維持されない限り、単項演算子は消滅する。不可視状態が維持されないならば、その単項演算子をルートとするサブツリーは適切な「ａｌｌ」図形要素と置換えられる。
【００３４】
（ｂ）アフィン変換と画像の写像はクアドツリーとプリミティブとの間の幾何学的配置(geometry)を維持しない。単項演算子がクアドツリーｑ0によって隠される場合、演算子は消滅する。そうでなければ、陰領域として空クアドツリーを渡して、アフィン変換又は画像写像の演算のオペランドにおいてトラバースが再開される。オペランドにより戻されたクアドツリーが容易に変換可能でない限り、空クアドツリーは演算子によって戻される。
【００３５】
（ｃ）画像畳み込み：単項演算子がクアドツリーｑ0により陰に隠されるのであれば、演算子は消滅する。そうでなければ、陰領域として空クアドツリーを渡して、画像畳み込みのオペランドにおいてトラバースが再開される。演算子がぼやけ状態を起こさせるために、そのオペランドにより戻されるクアドツリーの使用が困難になるので、そのような演算子によって空クアドツリーを戻す。しかしながら、画像畳み込み演算子が不透明度を変えない場合には、その演算子のオペランドにより戻されたクアドツリーを、画像畳み込みの演算子により親ノードに順に戻すことが可能になる。
＜表現ツリーの最適化＞
本実施の形態においては、レンダリングされるべき画像の画像合成表現ツリー（以下、「表現ツリー」という）を、好ましくは、深さ優先方式でトラバースする。表現ツリーの各ノードは、その親ノードから、画像の１つ又は複数の領域の領域表現を受け取る。領域表現をそのノードで表わされている領域と比較して、そのノードにより表わされている領域を陰にするか否かを判定する。
【００３６】
ノードにより表わされる領域が完全に陰になるようなノードは、以下に説明する表現ツリーの適切な単純化によって表現ツリーから除去される。ノードにより表わされる領域の一部しか陰にならない場合には、そのノードで表わされる画像の領域を切り取って画像の陰になる部分を捨てるために、ノードにより表わされる領域にクリッピング演算子を適用する。たとえば、表現ツリーのある１つのノードにより表わされる領域が他のノードにより表わされる１つ又は複数の領域によって完全に隠されてしまう場合、状況に応じて、そのノードで図形演算を実行しないか、又は図形要素をレンダリングしなくても済むように、そのノードを表現ツリーから除去する。
【００３７】
ある１つのノードが表現ツリーの他のノードにより表わされる１つ又は複数の領域によって一部しか隠されない場合には、合成演算子を実行するときに、そのノードで表わされる画像の実質的に陰にならない領域がノードの領域の合成結果となるように、クリッピング演算子を適用する。クリッピング演算子により切り取られるノードから成る表現ツリーから画像を合成し、続いてレンダリングする場合、実質的に画像の他の図形要素によって陰に隠されない図形要素の部分が再生すなわち、レンダリングされることになる。
【００３８】
クリッピング演算子のノードへの適用は、最も単純な形では、その結果として、派生ノードで表わされる図形要素を、陰にならない図形要素の部分まで実質的に断ち落とすことができる。ところが、クリッピング演算子のノードへの適用はそれには限定されない。表現ツリーのあるノードが合成演算を有するとき、そのノードにクリッピング演算を適用すると、合成演算子は異なる形で組み合わされる結果となる場合があり、表わされる領域を陰にならない部分まで断ち落とすかのような効果をノードに及ぼす。
【００３９】
たとえば、図２（Ａ）から図２（Ｄ）を参照して、図２（Ａ）に示す表現ツリー１０１を合成する処理をを説明する。図２（Ｂ）に示すように、矢印１０２は３０°時計回り方向に回転され、不透明ボックス１０４と関連して「ｉｎ」演算子が実行されて、回転後の矢印１０５の一部はボックス１０４の中に入っている。これは、回転後の矢印をボックス１０４の境界まで断ち落とすために３０°時計回り方向に回転された矢印にクリッピング演算を適用することによって実現可能である。
【００４０】
あるいは、演算子を異なる形で組み合わせても、最終画像としてほぼ同じ結果１０５を得ることができる。図２（Ｃ）に示すように、ボックス１０４を３０°反時計回り方向に回転させ、矢印１０２をボックス１０４にクリッピングし、それにより得られた画像１０７を時計回り方向に３０°回転させて、最終画像結果１０５を得る。しかしながら、図２（Ｄ）に示すように、これは、矢印１０２をボックス１０４まで断ち落とし、次に、３０°の時計回り方向の回転を適用して、最終合成画像１０６を得る場合と同じではない。このように、ノードにクリッピング演算子を適用すると、合成演算子は異なる形で組み合わされることになる。
【００４１】
ノードにより表わされる画像の領域が隠されないか、又は一部しか隠されないと判定されたならば、領域表現は親ノードから受け取ったノードを派生ノードにそれぞれ渡す。派生ノードのそれぞれで同じプロセスが起こり、最終的には各派生ノードはその派生ノードで表わされる領域によって陰に隠される画像の領域の画像表現、あるいはその派生ノードが完全に陰になることの指示を親ノードに戻す。
【００４２】
ノードの派生を処理し終ったならば、それらの派生から戻された領域表現を利用して、そのノードにより陰に隠される画像の領域の領域表現を取り出す。この結果をノードの親に戻す。
【００４３】
本実施の形態では、表現ツリーを単純化するためのツリーのトラバースは、当業者には知られている「深さ優先方式」で、ツリーのルートで開始される。表現ツリーを「深さ優先方式」でトラバースする場合、どのノードにおいても、左のブランチを下降して行く経路に優先権を与え、ツリーに沿って派生ノードに至るこの経路を最初にたどるのが好ましい。注目ノードで利用できる左ブランチ経路がなくなったときには、先行するノードに戻り、このノードの右ブランチをたどる経路をとる。このようにして、表現ツリーの全てのノードをたどり終るまで表現ツリーをトラバースする。
＜表現ツリー最適化の流れ図＞
図９は、本実施の形態における画像合成に用いられる表現ツリー９０２の最適化処理の概要を示す高水準の流れ図である。表現ツリー９０２は少なくとも２つのノードを含み、各ノードは画像要素かあるいは画像演算子である。好ましくは、画像演算子は画像合成演算子である。更に、画像中の領域はノードにより表される。表現ツリー９０２はノード毎にトラバースできる。制御ブロック９０４は、入力として与えられる表現ツリー９０２の各ノードを処理するためにループ制御構造であることが望ましい。表現ツリー９０２全体が処理されると（「終了」と示されている）、ステップ９１４で処理は停止する。さもなければ、ステップ９０６で処理は続行される。
【００４４】
ステップ９０６において、残りのノードのひとつが注目ノードとして選択される。ステップ９０８においては、そのノードにより表される領域を、少なくともひとつの他のノードにより表されるひとつ以上の領域に対応する領域表現データ構造と比較する。その領域表現は、階層的データ構造の形式であることが望ましく、クアドツリー表現であればなおよい。判定ブロック９１０においては、注目ノードのより表される領域が、ひとつの領域によって全体的にあるいは部分的に隠されているか判定するためのチェックが行われる。判定ブロック９１０が偽（NO）を返したなら、処理はステップ９０４から続けられる。一方、判定ブロック９１０が真（YES）を返したなら、処理はステップ９１２から続行される。ステップ９１２においては、表現ツリーは変更される。その変更には、注目ノードの除去あるいは注目ノードの表現ツリーの他のノードによる置き換えが含まれている。また、注目ノードで表される領域のクリッピングや後でクリッピングするためのマーキングも含まれる。その後、制御ステップ９０４から処理は続行される。
【００４５】
図１０は、図９のステップ９１２に関して、表現ツリーを変更するための工程を説明する、より詳細な流れ図である。ステップ１００２で処理が開始され、ステップ１００４において注目ノードで表される領域が全体的あるいは部分的に隠されるか判定するためのチェックが行われる。判定ブロック１００４によりその領域は部分的に隠されると判定されると、処理はステップ１０１２に進む。ステップ１０１２においては、クリッピング演算子が注目ノードに適用され、処理はステップ１０１４に戻る。一方、判定ブロック１０１４において領域全体が隠されると判定されると、処理はブロック１００６に進む。
【００４６】
判定ブロック１００６において、注目ノードが画像要素かそれとも画像演算子か判定される。判定ブロック１００６により注目ノードが画像要素であると判定されると、ステップ１００８に処理は進む。ステップ１００８においては、注目ノードは表現ツリーから削除され、ステップ１０１４において、処理は呼び出した手続きに戻る。一方、判定ブロック１００６において注目ノードは画像演算子であると判定されると、処理はステップ１０１０に進む。ステップ１０１０においては、所定のノード置換規則群が画像演算子に応じて適用される。
【００４７】
所定のノード置換規則群（図９及び１０には不図示）は、下記の規則のうちひとつ以上を含む。
【００４８】
もし親ノードが「ｏｖｅｒ」画像演算子であり、しかも注目ノードが親ノードの左ブランチであれば、親ノードを親ノードの右サブツリーで置換する。
【００４９】
もし親ノードが「ｏｖｅｒ」画像演算子であり、しかも注目ノードが親ノードの右ブランチであれば、親ノードを親ノードの左サブツリーで置換する。
【００５０】
もし親ノードが「ｉｎ」画像演算子であれば、親ノード及び親ノードから枝分かれするサブツリーを削除する。
【００５１】
もし親ノードが「ｒａｔｏｐ」画像演算子であり、しかも注目ノードが親ノードの左ブランチであれば、親ノード及び親ノードから枝分かれするサブツリーを削除する。
【００５２】
もし親ノードが「ｒａｔｏｐ」画像演算子であり、しかも注目ノードが親ノードの右ブランチであれば、親ノードを親ノードの左サブツリーで置換する。
【００５３】
もし親ノードが「ｏｕｔ」画像演算子であり、しかも注目ノードが親ノードの左ブランチであれば、親ノード及び親ノードから枝分かれするサブツリーを削除する。
【００５４】
もし親ノードが「ｏｕｔ」画像演算子であり、しかも注目ノードが親ノードの右ブランチであれば、親ノードを親ノードの左サブツリーで置換する。
【００５５】
もし親ノードが「ｐｌｕｓＣ」画像演算子であり、しかも注目ノードが親ノードの左ブランチであれば、親ノードを親ノードの右サブツリーで置換する。
【００５６】
もし親ノードが「ｐｌｕｓＣ」画像演算子であり、しかも注目ノードが親ノードの右ブランチであれば、親ノードを親ノードの左サブツリーで置換する。
【００５７】
もし親ノードが「ｐｌｕｓＷ」あるいは「Ｘｏｒ」画像演算子であり、しかも注目ノードが親ノードの左ブランチであれば、親ノードを親ノードの右サブツリーで置換する。
【００５８】
もし親ノードが「ｐｌｕｓＷ」あるいは「Ｘｏｒ」画像演算子であり、しかも注目ノードが親ノードの右ブランチであれば、親ノードを親ノードの左サブツリーで置換する。
【００５９】
図１１はその他の実施例による表現ツリー１１０２の最適化処理の詳細流れ図を示す。この表現ツリーは多くのノードを有し、各ノードは画像要素あるいは画像演算子であり、画像の領域を表している。制御ブロック１１０４は、入力される表現ツリー１１０２の各ノードを処理するためのループ制御構造に備えたものであることが望ましい。表現ツリーはノード毎にトラバースされる。画像演算子を含む各注目ノードにおいては、ステップ１１０８から１１２０はこれから説明するように適用される。好ましくは深さ優先の手法で表現ツリー１１０２全体を処理し終えた場合（「終了」と示されている）、処理はステップ１１０６で停止する。そうでなければ、処理はステップ１１０８から続行される。
【００６０】
ステップ１１０８においては、残りのノードのひとつが注目ノードとして選択される。ステップ１１１０においては、第１の領域表現を親ノードから受け取る。ステップ１１１２においては、変更された第１の領域表現が、画像演算子の第１のオペランドに、その演算子の第１の所定の変更規則にしたがって渡される。ステップ１１１４においては、第１のオペランドのサブツリーによって隠される領域の第２の領域表現が決定され、画像演算子に返される。ステップ１１１６においては、変更された第２の領域表現が、画像演算子の第２のオペランドに、その演算子の第２の所定の変更規則にしたがって渡される。
【００６１】
ステップ１１１８においては、第２のオペランドに関連するサブツリーによって隠される領域の第３の領域表現が決定され、画像演算子に返される。ステップ１１２０では、最終的な領域表現が画像演算子の規則群に応じて決定され、注目ノードの親ノードに返される。好ましくは、その規則群は次の（Ａ）〜（Ｅ）を含むグループから選ばれる。
【００６２】
（Ａ）画像演算子が「ｏｖｅｒ」あるいは「ｐｌｕｓＣ」演算子の場合、最終的な領域表現は、第２の領域表現と第３の領域表現の和集合から決定される。
【００６３】
（Ｂ）画像演算子が「ｉｎ」演算子の場合、最終的な領域表現は、第２の領域表現と第３の領域表現の共通部分から決定される。
【００６４】
（Ｃ）画像演算子が「ｒａｔｏｐ」演算子の場合、最終的な領域表現は、第２の領域表現である。
【００６５】
（Ｄ）画像演算子が「ｏｕｔ」演算子の場合、最終的な領域表現は、第２の領域表現と、注目ノードの右サブツリーのノードの境界となるボックスにより表される少なくともひとつの領域を含む領域表現との差から決定される。
【００６６】
（Ｅ）画像演算子が「Ｘｏｒ」あるいは「ｐｌｕｓＷ」演算子の場合、最終的な領域表現は、注目ノードの右サブツリーのノードの境界となるボックスにより表される少なくともひとつの領域を含む領域表現を引いた第２の領域表現と、注目ノードの右サブツリーのノードの境界となるボックスを含む領域表現を引いた第３の領域表現との和集合から決定される。
【００６７】
好ましくは、画像演算子が「ｏｖｅｒ」「ｉｎ」「ｒａｔｏｐ」「ｐｌｕｓＣ」「ｐｌｕｓＷ」「Ｘｏｒ」「ｏｕｔ（左のオペランドが先）」等の演算子であるなら、第１の所定の変更規則は、実質的に第１の領域表現を、変更された第１の領域表現として渡す。もし画像演算子が「ｏｕｔ（左のオペランドが先）」演算子であれば、変更された第１の領域表現として第１の領域表現と第２の領域表現との和集合を渡すことを伴う。
【００６８】
また、画像演算子が「ｉｎ」「ｒａｔｏｐ」「ｏｕｔ」「ｐｌｕｓＣ」「ｐｌｕｓＷ」「Ｘｏｒ」等の演算子であるなら、第２の所定の変更規則は、実質的に第１の領域表現を、変更された第２の領域表現として渡す。模試画像演算子が「ｏｖｅｒ」であるなら、変更された第２の領域表現として第１の領域表現と第２の領域表現との和集合を渡すことを伴う。
【００６９】
好ましくは、画像表現が実質的に利用されないか、あるいはノードが「ｏｖｅｒ」演算子の右オペランドでしかもその「ｏｖｅｒ」演算子ノードが画像表現をその親ノードに返す必要がなければ、画像表現はそのノードで生成されないか、またはそのノードの親ノードに返されない。同様に、ノードが「ｉｎ」「ｐｌｕｓＣ」「ｐｌｕｓＷ」あるいは「Ｘｏｒ」演算子の左あるいは右オペランドでしかもその演算子が画像表現をその親ノードに返す必要がないならば、画像表現はそのノードで生成されないか、または返されない。更に、ノードが「ｏｕｔ」あるいは「ｒａｔｏｐ」演算子の左オペランドでしかも画像表現をその親ノードに返す必要がないならば、画像表現はそのノードで生成されないか、または親ノードに返されない。ノードが「ｒａｔｏｐ」演算子の右オペランドか、表現ツリーのルートか、画像写像のオペランドか、アフィン変換または畳み込みの演算子か、不透明性を保存しない色変換のオペランドであるか、あるいは変換ノードが画像表現をその親ノードに返す必要がないならば、画像表現はそのノードで生成されないか、または返されない。
【００７０】
本実施の形態の他の態様は、明細書の一部である付録に詳細が説明されている。特に、付録には、好適な実施の形態に従った方法を実現するための擬似コードリストが含まれている。この関連においては、本校的な実施の形態は、記録媒体に格納し得る、汎用コンピュータといった計算装置での処理の実行として遂行されるコンピュータソフトウエアとして実現されることが望ましい。
【００７１】
本発明にかかる実施の形態は、付録に含まれる擬似コードと同様、図９〜図１１の処理を含む処理を遂行するために、図１２に示したような従来の汎用コンピュータを用いて実現されることが望ましい。特に、表現ツリーを最適化する方法の工程は、コンピュータにより実行されるソフトウエア中の命令により達成される。コンピュータシステム１２００は、コンピュータ１２０２とビデオディスプレイ１２１６、入力装置１２１８，１２２０からなる。更に、コンピュータシステム１２００は、ラインプリンタやレーザプリンタ、プロッタ、その他のコンピュータ１２０２に接続された再生装置を含むその他多くの出力装置を有していてもよい。コンピュータ１２００は、モデムによる通信路やコンピュータネットワークなどの適当な通信チャネルで１つ以上の他のコンピュータに接続されていてもよい。
【００７２】
コンピュータ１２０２自身は、中央処理装置（単にプロセッサと呼ぶ）とランダムアクセスメモリ(ＲＡＭ)及びリードオンリメモリ(ＲＯＭ)を含むメモリ１２０６、入出力インターフェース１２０８、ビデオインターフェース１２１０、図１２のブロック１２１２で概括的に表されたひとつ以上の格納装置からなる。各装置１２１２は、ひとつ以上のフロッピーディスクやハードディスクドライブ、光磁気ディスクドライブ、ＣＤ−ＲＯＭ、あるいはその他多くの当業者によく知られた不揮発性の格納装置からなる。構成要素１２０４〜１２１２のそれぞれは、典型的には、順にデータ、アドレス、制御バスからなるバス１２１４によりひとつ以上の他の装置に接続されている。
【００７３】
ビデオインターフェース１２１０は、ビデオディスプレイ１２１６に接続され、コンピュータ１２０２からのビデオ信号をビデオディスプレイ１２１６への表示のために供給している。コンピュータ１２０２を操作するための利用者の入力者は、ひとつ以上の入力装置によりなされてもよい。例えば、操作者は、コンピュータ１２０２への入力をおこなうために、キーボード１２１８とマウス１２２０といった座標入力装置の何れか一方または両方を利用できる。本実施の形態が実現される代表的なコンピュータは、ＩＢＭ社のＩＢＭ−ＰＣ／ＡＴ及びその互換機と、ＳＵＮ社のSparcStationである。
［第１の実施例］
図３には、部分画像１１として表わされている不透明画像Ａと、この部分画像１１によって隠される円Ｂとして表わされている円１２と、任意にテキスト「Ｃ」として表わされているテキスト「ｈｅｌｌｏ」１３とを含む複数の図形要素から成る画像１０が示されている。点線１４は画像１０の広がり範囲を示し、画像１０を陰に隠すものが内部に何もない空の前景領域を表わす。
【００７４】
図４には、図３の画像の合成を表わす表現ツリー２０が示されている。ここで、図４を参照して、図４の表現ツリーを単純化する例を説明する。
【００７５】
表現ツリー２０のルート（第１のノード）２１で、コンピュータに備えられたプロセスは、画像１０を隠さないか、又はそれと同等に表現ツリー２０の第１のノード２１の上方に画像１０を陰に隠すノードが他にない空領域１４を表わす空クアドツリーを第１のノード２１に渡す。
【００７６】
第１のノード２１は、左右のオペランドを要求する合成演算子（この場合には「ｏｖｅｒ」演算子）である。左オペランドは図３の部分画像１１を表わすリーフノード２２であり、右オペランドはこの例においては「ｏｖｅｒ」合成演算子でもある表現ツリーの第２のノード２３により戻される。
【００７７】
第１のノード２１で空クアドツリーを受け取るのに続いて、プロセスは空クアドツリーをリーフノード２２に渡す。リーフノード２２では、通常、部分画像１１が陰になるか否かを判定するためにクアドツリーを部分画像１１と比較する。しかしながら、この例では、クアドツリーは空クアドツリーであるので、部分画像１１が空クアドツリーによって隠されない（隠されることはあり得ない）という結果を確定するために、直接の比較は必要ない。
【００７８】
クアドツリーと図形要素（この例では、部分画像１１）との比較には、画像の１つの領域が別の領域を陰に隠すか否かを判定するために、クアドツリーにより表わされる画像の領域を図形要素が占める画像の領域と比較するという比較が付随している。画像の１つの領域のクアドツリー表現と、画像の他の領域との比較は、画像のその領域と他の領域との直接比較、又は等価の表現などの比較のいずれかによってそれぞれの領域を比較することを含む。
【００７９】
リーフノード２２で表わされている部分画像１１は不透明であるので、画像１０の他の図形オブジェクトを隠してしまう可能性がある。従って、構成される部分画像１１の第１のクアドツリー表現は部分画像１１の境界を含んでおり、表現ツリー１０のリーフノード２２では左又は右のブランチはそれ以上利用できないので、第１のノード２１に戻される。第１のノード２１において、「ｏｖｅｒ」演算子は、そのノードに元来渡された、空クアドツリーであるクアドツリーと、左ノードから戻されるクアドツリー表現との和集合を、以下に説明する２項合成演算子の取扱いに関して表２に記載した規則に従って実行する。
【００８０】
空クアドツリーと、部分画像１１の第１のクアドツリー表現との和集合の結果、第１のクアドツリーと等価（又はほぼ同一）であり、以下では第１の左クアドツリーと呼ばれるクアドツリーが得られる。
【００８１】
第１の左クアドツリーは表現ツリー１０の第２のノード２３へ送り出され、先にノード２１に関連して説明したのと同じように、続いて第２のノードの左ブランチに渡されて、第２のノード２３から枝分かれするリーフノード２４に至る。リーフノード２４には円１２が表わされており、第１の左クアドツリーをリーフノード２４に送った後に、プロセスは第１の左クアドツリー（すなわち、第１の左クアドツリーにより表わされる画像領域）を円１２が占める画像の領域と比較し、その結果、少なくともこの例に関しては、円１２の領域は第１の左クアドツリーにより表わされる領域によって完全に隠されることがわかる。円１２の領域が完全に陰になるという結果は第２のノード２３に戻される。
【００８２】
通常、第２のノード２３は、リーフノード２４から部分画像１１及び円１２が占める画像の部分を表わすクアドツリー（部分画像１１と円の和集合により得られる領域）を受け取るが、この例においては、円１２は部分画像１１によって完全に隠されてしまうので、部分画像１１と円１２のクアドツリーの和集合を実行する必要はない。
【００８３】
部分画像１１を表わす第１の左クアドツリーと実質的に等価であるクアドツリーは第２のノード２３に戻され、このクアドツリーは第２のノード２３から枝わかれする右リーフノード２５に渡される。表現ツリーの右リーフノード２５はテキスト（テキスト「ｈｅｌｌｏ」１３）を形成する画像の領域を表わす。
【００８４】
テキストは、第２のノード２３から渡されるクアドツリー（そのクアドツリーにより表わされる画像領域）によって隠されない。通常、右リーフノード２５の図形要素によって陰に隠される画像の領域を表わすクアドツリーは第２のノード２３に戻されるであろうが、この場合、テキストは大きな領域（エリア）を隠さないので、第２のノード２３には空クアドツリーが戻される。以下に説明するように、実際の領域は処理の性能の点から定義されるのが好ましい。
【００８５】
第２のノード２３は右リーフノード２５から空クアドツリーを受け取る。左オペランドが隠されるとき、そのノードにおける「ｏｖｅｒ」演算子のアクション（表２に示す）に続いて、第２のノード２３自体を右リーフノード２５と置換え、この例では左リーフノード２４である左「ブランチ」を枝刈りする。第２のノード２３に戻されたクアドツリーは（空クアドツリーであっても）第１のノード２１に戻される。
【００８６】
第１のノード２１では、その派生ノードはいずれも枝刈りされず、「ｏｖｅｒ」演算子に対するアクションは、そこから「ｏｖｅｒ」演算子の左右のブランチに戻されるクアドツリーの和集合を形成することである。この和集合の結果は通常はノード２１の親ノードに戻される。ところが、第１のノード２１は表現ツリーの最上位置にあるノード（ルートノード）である。従って、和集合の結果は表現ツリーの最適化には利用されず、単純化された表現ツリーを図５に示す。図５では、第２のノード２３と左リーフノード２４が図４の表現ツリーから除かれている。そこで、図５の単純化された表現ツリーを使用して、ここでは円１２と呼ばれている図形要素は部分画像１１で隠されるためにこれをレンダリングする必要なく、図３の画像をレンダリングすることができる。
＜第２の実施例＞
図６から図８を参照して、表現ツリーを単純化（最適化）するもうひとつの例を説明する。図６には、ページ「Ｄ」４１と、不透明部分画像４２と、テキスト４３と、円４４という図形要素から構成される画像４０が示されている。図６の画像４０を合成又はレンダリングするための対応する表現ツリーを図７に示す。図７において、Ｓ０からＳ１４は、この実施例で表現ツリー５０を単純化あるいは最適化するために実行されるステップを表わす。
【００８７】
下記のステップＳ０−Ｓ１４は、図７の表現ツリー５０を単純化するときに、各ノードでコンピュータに備えられたプロセスによるアクションに対応している。
【００８８】
Ｓ０：画像４０全体を隠さない空の前景領域３９を表わす空クアドツリーｑ0を生成する。この空クアドツリーｑ0は表現ツリー５０の第１のノード５１（すなわちルートノード）に渡される。
【００８９】
Ｓ１：表現ツリー５０の第１のノード５１は「ｏｖｅｒ」演算子である。プロセスは先のステップＳ０から第１のノード５１に渡された空クアドツリーｑ0を受け取り、第１のノード５１により表わされる領域が陰に隠れるか否かを判定するために、クアドツリーｑ0により表わされる画像の領域を第１のノード５１により表わされる領域と比較する。ｑ0は空クアドツリーであり、第１のノード５１により表わされる領域を隠すことができないので、プロセスは派生ノードに対して実行し続ける。最初に、クアドツリーｑ0はノード５１の左ブランチに沿って第２のノード５２に渡される。
【００９０】
Ｓ２：この例では「ｉｎ」演算子である第２のノード５２は空クアドツリーｑ0を受け取る。第２のノード５２により表わされる領域がクアドツリーｑ0によって隠されるか否かを判定するために、クアドツリーｑ0を第２のノード５２の領域と比較する。クアドツリーｑ0は空であるので、第２のノード５２の領域はクアドツリーｑ0によって隠されない。その後もプロセスは深さ優先方式で実行を続け、クアドツリーｑ0を第２のノード５２の左ブランチに渡す。
【００９１】
Ｓ３：第３のノード５３は部分画像４２を表わしているリーフノードである。この第３のノード５３はＳ２ステップから渡されたクアドツリーｑ0を受け取り、ノード５３により表わされる領域がクアドツリーｑ0によって陰に隠されるか否かを判定するために、このノード５３の領域をクアドツリーｑ0により表わされる領域と比較する。この例では、クアドツリーｑ0は空であるので、ノード５３は隠されない。ところが、画像「Ａ」は他の図形要素を隠す可能性がある図形要素である。そのため、画像によって隠される領域を表わすクアドツリーｑ1を作成し、第３のノード５３では左ブランチをそれ以上利用できないので、クアドツリーｑ1を第２のノード５２に戻す。
【００９２】
Ｓ４：第２のノード５２は第３のノード５３からクアドツリーｑ1を戻される。第２のノード５２は「ｉｎ」演算子であるので、「ｉｎ」演算子の左オペランドの陰領域としてクアドツリーｑ1をメモリに記憶する。演算子の左オペランドの陰領域をここではｑLと表わす。すなわち、この例においては、ｑL ＝ｑ1 となる。表２に従えば、プロセスのアクションは、親ノード５１から渡されて、第２のノード５２で受け取られたクアドツリ−をノード５２の右派生ノード５４に渡すことである。この例では、第１のノード５１（親ノード）から第２のノード５２に渡されたクアドツリーｑ0を右ブランチに沿って右派生ノード５４へ送ることになる。
【００９３】
Ｓ５：右派生ノード５４（第５のノード）は再びリーフノードであり、円４４として指示される領域を表わしている。ステップＳ４に従ってクアドツリーｑ0は第２のノード５２に渡されているので、このクアドツリーｑ0により表わされる領域が円４４によって隠されるか否かを判定するために、クアドツリーｑ0を円４４が占める画像の領域と比較する。先の場合と同様に、クアドツリーｑ0は空であり、従って、ノード５４は隠されない。ところが、円４４はその下に位置する図形要素（オブジェクト）を陰に隠す可能性がある図形要素（オブジェクト）である。そのため、円が占める画像の領域を表わすクアドツリーｑ2を生成する。このノード５４ではそれ以上のブランチを利用できないので、クアドツリーｑ2を第２のノード５２に戻す。
【００９４】
Ｓ６：第２のノード５２は右派生ノード５４から戻されたクアドツリーｑ2受け取り、そのクアドツリーｑ2は「ｉｎ」演算子の右オペランドの陰領域として記憶される（すなわち、ｑR ＝ｑ2 ）。プロセスは「ｉｎ」演算子について表２に記載したアクションに従って進行し、その親ノード（すなわち第１のノード５１）に２つのオペランドにより表わされる領域（すなわち部分画像４２と円４４）との共通部分を渡す。その共通部分は、部分画像４２が、円４４と一致する部分（すなわちクアドツリーｑ2）により表わされる領域となる。この例では、この共通部分ｑL ∩ｑR ＝ｑ1 ∩ｑ2 ＝ ｑ2は、ノード５２が他の図形要素を隠すことがあり得る領域を表わしている。
【００９５】
Ｓ７：第１のノード５１は第２のノード５２から戻されたクアドツリーｑ2を受け取り、そのクアドツリーｑ2は「ｏｖｅｒ」演算子の左オペランドの陰(obscuring)領域として記憶される（ｑL ＝ｑ2 ）。「ｏｖｅｒ」演算子を有するノードの右ブランチを下降して行くときに表２に従って実行すべきアクションは、クアドツリーｑ0と、第２のノード５２から戻されたクアドツリーｑLとの和集合（すなわち、ｑ0 ∪ｑL ＝ｑ0 ∩ｑ2 ＝ ｑ2）を右ブランチに沿って渡すことである。この和集合の結果（ｑ0 ∪ｑL）はｑ2と実質的に同一のクアドツリーである。そのため、この和集合の結果（クアドツリーｑ2）は右ブランチに沿って、これも「ｏｖｅｒ」演算子を表わす第５のノード５５に渡される。
【００９６】
Ｓ８：第５のノード５５に渡されるクアドツリーｑ2により表わされる領域は、ノード５５の領域がクアドツリーｑ2（の領域）によって隠されるか否かを判定するために、第５のノード５５で表わされる領域と比較される。第５のノード５５で表わされる画像の領域はクアドツリーｑ2の領域によって隠されない。クアドツリーｑ2は第５のノード５５の左ブランチの派生に渡される。
【００９７】
Ｓ９：第５のノード５５の左側の派生は、テキスト４３を示している図６の画像の領域を表わすリーフノード５６である。リーフノード５６は第５のノード５５から渡されるクアドツリーｑ2を受け取り、クアドツリーｑ2により表わされる領域がリーフノード５６で表わされる領域を隠すか否かを判定するために、クアドツリーｑ2をリーフノード５６で表わされる領域と比較する（通常は、テキスト４３が占める図６の画像の領域は、テキストを含む境界規定ボックスである）。この例ではクアドツリーｑ2により表わされる領域（円４４が占める領域）はテキスト４３の一部を陰に隠す。そこで、テキスト４３をクリッピングするか、又は後の段階でのクリッピングに備えてタグ付けする。テキスト４３は、クリッピング演算子を適用することによってクリッピングされるが、このクリッピング演算はクアドツリーｑ2から出る「クリップ」経路を構成し、テキスト４３をこの経路に対してクリッピング、すなわちカットする。
【００９８】
この時点で、通常、テキストが占める画像の領域を表わす新たなクアドツリーが生成されて、第５のノード５５に戻される。しかしながら本実施例においては、図形要素は画像の他の図形要素の大部分を隠すには小さすぎるのなら（すなわち、図形要素であるテキスト４３「ｈｅｌｌｏ」が、テキスト４３の境界規定ボックスが十分な領域を表わしているとはいえ、他の図形要素を相当量覆い隠すことはないなら）、テキスト４３の領域のクアドツリー表現を実現するために処理時間を費やすより、むしろ、空クアドツリーを戻すほうが好ましい。従って、この実施例では、テキスト４３が占める画像の領域に関して新たなクアドツリーｑ3を空クアドツリーとして生成することを選択する。テキスト４３により表わされる領域に関して空クアドツリーを作成することを選択するのは、「性能の問題」という小見出しの下で以下に説明する、プロセスの性能の問題である。テキスト４３のクアドツリー表現を生成することは可能であるが、テキストをレンダリングするのに要する時間より、プロセスの実行速度の低下の方が上回ってしまう。従って、空クアドツリーｑ3を生成し、第５のノード５５に戻す。
【００９９】
Ｓ１０：第５のノード５５は、先のステップＳ９により戻された空クアドツリーｑ3を受け取り、このクアドツリーｑ3は第５のノード５５の「ｏｖｅｒ」演算子の左オペランドの陰領域(obscuring region)として記憶される（ｑL ＝ｑ3 ）。先の場合と同様に、「ｏｖｅｒ」演算子を有するノードの右ブランチを下降するときに表２に従って実行すべきアクションは、親ノード５１によりノード５５に渡されたクアドツリーｑ2と、左オペランドと関連するクアドツリーｑ3との和集合を右ブランチに沿って渡すことである（ｑL ∪ｑ2 ＝ｑ3 ∪ｑ2 ＝ｑ2 ）。クアドツリーｑ3はステップＳ９で説明した空クアドツリーであるので、クアドツリーｑ3とクアドツリーｑ2との和集合の結果は、クアドツリーｑ2と等価のクアドツリーが得られる。従って、クアドツリーｑ2が表現ツリーの右ブランチに沿って親ノード（第５のノード）５５の右リーフノード５７に渡される。
【０１００】
Ｓ１１：右リーフノード５７は図６の背景ページを表わす図形要素であるページ「Ｄ」４１により表わされている。クアドツリーｑ2により表わされる領域がページ「Ｄ」４１により表わされる領域を隠すか否かを判定するために、第５のノード５５により右リーフノード５７に渡されるクアドツリーｑ2をページ「Ｄ」４１の領域と比較する。この例では、この比較の結果、クアドツリーｑ2により表わされる領域（円４４）はページ「Ｄ」４１の一部または全部を隠すことがわかる。
【０１０１】
従って、図形要素ページ「Ｄ」を処理の後の段階、通常はレンダリングの前に円４４の境界にクリッピング（クリップ経路はクアドツリーｑ2から出る）されるようにタグ付けするか、あるいはクリッピング演算子を適用し、円４４により表わされる領域がページ「Ｄ」４１から切り取られるようにページ「Ｄ」４１をクリッピングする。ページ「Ｄ」４１を表わすためにクアドツリーを生成し、それを親ノードに戻すことも可能ではあろうが、この例においては、陰に隠れる可能性のある図形要素は他には存在しないことを推測できるので、親ノードに戻すべきページ「Ｄ」４１のクアドツリーを生成することは不必要である。
【０１０２】
Ｓ１２：プロセスは第５のノード５５に戻るが、そこで別のクアドツリーを生成する必要はない。
【０１０３】
Ｓ１３：プロセスは第１のノードに戻るが、そこで別のクアドツリーを生成する必要はない。
【０１０４】
Ｓ１４：プロセスは図７の表現ツリー５０を図８の表現ツリー６０へと最適化して終了する。図８において、菱形の記号５８及び５９は、テキスト４３とページ「Ｄ」４１をそれぞれクリッピングすべきであること（又は場合によっては既にクリッピングされていること）を指示している。
＜性能の問題＞
図１から図８を参照して説明した上記の例においては、画像全体と比較したときの図形要素（オブジェクト）の相対的な大きさとは関係なく、その図形要素が占める画像の一部領域を表わすクアドツリー表現を生成していた。しかし、この実施例で実行されるプロセスは下記の原理及び推論によって決定されるのが好ましい。
【０１０５】
（ａ）完璧な結果を得ようとするよりも、大半のケースに対応する最善のことを実行するほうが良い。
【０１０６】
（ｂ）少なくとも当初は、ノードで、画像の中に隠蔽が実際に存在するか否かはわからないので、効果があるかどうか不確実であるコストの高い試験を回避するほうが良い。これらの原理は次のように適用される。
【０１０７】
第１に、クアドツリーの深さ（ノードとブランチの数）が増すにつれて、クアドツリーの分解能は向上し、隠れる領域を検出する能力も高まる。ところが、所定の分解能を越えると、クアドツリーを生成し、組み合わせるための計算に要するコストは指数関係をもって増加し、クアドツリーの深さの増加によって表わされる消滅エリアを表現ツリーから除去しようとすることによって性能を埋め合わせようとしても、それを上回る不利益を生じる。
【０１０８】
第２に、不透明プリミティブごとに、それを陰形成可能要素（画像の他の図形要素を隠すかもしれない図形要素）として取り扱うのは、計算の面で負担が大きくなりすぎるであろう。プリミティブが小さくなればなるほど、そのプリミティブが別のプリミティブを隠す確率は低くなるので、所定の大きさ以上の陰形成可能要素にクアドツリーの生成を限定するのが好ましい。クアドツリーに変換するには負担が大きすぎるプリミティブでは、投資に対しての十分な見返りをもたらすことが保証されないので、そのようなプリミティブは通常は考慮されない。従って、「適切な陰形成可能要素」は次のような特徴を有するのが好ましいであろう。
【０１０９】
（ａ）完全に不透明である。
【０１１０】
（ｂ）所定の大きさより大きい（従って、画像の他のプリミティブを隠す可能性がある）。
【０１１１】
（ｃ）非常に迅速にクアドツリーに変換することが簡単である（たとえば、１つの単純な凸輪郭線から成る図形要素のみを選択する）。
【０１１２】
第３に、陰に隠すか否かの試験（すなわち、第１の図形要素が画像の１つ又は複数の図形要素を隠すか否かの判定）は、第１の図形要素により覆われる領域をクアドツリーとして表わし、そのクアドツリーのノードで表わされる領域の１つ又は複数のセルが画像の１つ又は複数の図形要素により覆われる領域を隠すか否かを試験することによって実行可能である。通常、１つ又は複数の領域についても、クアドツリーにより表わし、クアドツリーのセルを比較する。しかしながら、画像の任意の領域を所定の分解能でクアドツリー表現として表わすことは全く可能ではあるが、計算の面で非常に大きな負担となる可能性がある。そのため、表現ツリーのノードで表わされる領域の境界規定ボックスを構成するのが好ましい。ノードが図形要素であるか、又は領域が表現ツリーノードで表わした演算子であるかは申し分なく定義されている。
【０１１３】
表現ツリーのノードの境界規定ボックスはそのノードにより覆われる領域を厳密には表わせないであろうが、計算性能の向上は、通常、隠れを検出できないことによる性能の劣化を上回る。陰になる図形要素が占める画像の領域のクアドツリー表現を比較するより、図形要素それぞれの境界規定ボックスを比較することで図形要素を試験するほうが好ましい。これにより、所定の大きさ未満の隠れ図形要素のいくつかは欠落し、陰に隠れるとは考えられないかもしれないが、一般的なケースの多くで計算の面から投資に見合う見返りを正しく与えないような試験と比べれば、画像の図形要素が他の図形要素によって隠されるか否かを判定するという単純な試験のほうが好ましい。
【０１１４】
以下に、１つのノードの境界規定ボックスをクアドツリーセル（以下、「セル」という）と比較するルーチン「test」を呼び出すための擬似コードの一例を挙げる。
0003996975.tif 000004
【０１１５】
0003996975.tif 000005
によって呼び出される。
【０１１６】
クアドツリーは連続して生成、廃棄される。メモリ割り当てアクティビティが少なく、非常に単純且つ急速にコンピュータメモリを管理する方式が好ましい（たとえば、メモリのやや大きいブロックを、一度に１０００クアドツリーセル程度で割り当てる）。セルはそれらのブロックに割り当てられ、一度書き込んで読み出すのみ(write-once-read-only)として取り扱われ、表現ツリー全体のトラバースが終了するまで割り当ては解除されない。この方式によれば、セルはクアドツリーの間に割り当てられ、クアドツリー設定動作を実行するときのコピーは相当に減少する。
【０１１７】
性能の問題として、領域表現（クアドツリー）を生成する必要のないところでは、ノードで領域表現を生成しないのが好ましい。たとえば、親ノードは派生  ノードからその派生ノードと、その先の派生ノードが隠すと思われる領域のクアドツリーを要求するであろう。領域表現がその後の計算で全く利用されないのであれば、通常、その領域表現を生成する必要をなくすのが好ましい。
【０１１８】
以上、便宜上、再帰法を使用して、表現ツリーを最適化するプロセスを説明した。バックポインタを利用する非再帰的プロセスを使用してプロセスを実現することも可能である。これは関数呼び出しのオーバヘッドを少なくすると共に、実際にはほとんど均衡していることないような非常に大型のツリーを処理するためである。
【０１１９】
以上、本発明のいくつかの実施例のみを説明したが、本発明の範囲から逸脱することなく、当業者には自明な変形を実施することが可能である。
【０１２０】
尚、以下に付録として、好ましい実施例をコンピュータで実現するのに適する擬似コードを示す。ここに示す関数obscureは、クアドツリーｑ0 に対する隠蔽に関してノード（node）をテストする。この関数は、ノードの全ての可視部分が隠蔽されるか否かを戻す。need_resultが真であれば、ノードがどの領域を陰に隠すかを表わすクアドツリーも戻す。この関数obscureは、
obscure(ツリーのルートノード, false, 空のクアドツリー)
なる呼び出しによって呼び出される。
【０１２１】
【付録】
関数obscureは次の通りである
0003996975.tif 000006
0003996975.tif 000007
0003996975.tif 000008
0003996975.tif 000009
0003996975.tif 000010
0003996975.tif 000011
0003996975.tif 000012
【発明の効果】
以上説明したように、本発明によれば、オブジェクト間の重なり合いが生じる画像について、最終画像に影響を及ぼさない要素、又は要素の部分を識別できるため、それらの要素（又は部分）をレンダリングする必要がないので、処理な時間とメモリとを節約できる。また、あらゆる合成演算子を処理できるという効果を生ずる。
【０１２２】
【図面の簡単な説明】
【図１】  様々な合成演算を概略的に示す図である。
【図２】実施例に従ってクリッピング演算子を適用する例を示す図である。
【図３】単純な図形オブジェクトから合成されたレンダリング後の画像の例を示す図である。
【図４】図３の画像を合成又はレンダリングするための単純な図形オブジェクトの合成を表わす画像表現ツリーを示す図である。
【図５】実施例に従って図４の画像表現ツリーを単純化した画像表現ツリーを示す図である。
【図６】単純な図形オブジェクトから合成されるレンダリング後の画像の別の例を示す図である。
【図７】図６の画像を合成又はレンダリングするための図形オブジェクトの合成を表わす画像表現ツリーを示す図である。
【図８】実施例に従って図６の画像を合成するための単純化された表現ツ リーを示す図である。
【図９】本実施の形態における画像合成に用いられる表現ツリーの最適化処理の概要を示す流れ図である。
【図１０】図９のステップ９１２に関して、表現ツリーを変更するための工程の詳細な流れ図である。
【図１１】その他の実施例による表現ツリーの最適化処理の流れ図である。
【図１２】従来の汎用コンピュータのブロック図である。
【図１】
0003996975.tif 000013
【図２】
0003996975.tif 000014
【図３】
0003996975.tif 000015
【図４】
0003996975.tif 000016
【図５】
0003996975.tif 000017
【図６】
0003996975.tif 000018
【図７】
0003996975.tif 000019
【図８】
0003996975.tif 000020
【図９】
0003996975.tif 000021
【図１０】
0003996975.tif 000022
【図１１】
0003996975.tif 000023
【図１２】
0003996975.tif 000024