(57)【要約】本発明は、Ｎ次元オブジェクトのボクセル表現を特定の形状のグラフであるセルラー空間を含むコンピュータモデルに変換する方法に関する。セルラー空間のそれぞれのエッジに付されるインジケータは、ある境界があるオブジェクトに属しているかを示している。これは、ビデオ系列の三次元圧縮及びインターネットでのビデオ系列のサーチにとって有効である。
2005531862.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ次元の第一のオブジェクトのコンピュータ表現を該第一のオブジェクトのコンピュータモデルに変換する方法であって、
該コンピュータモデルへの変換は、Ｎに等しい次元を有する第一のマニフォルドに属する第一のセルと、該第一のマニフォルドの境界に位置され、Ｎ−１に等しい低い次元を有する第二のマニフォルドに属する第二のセルと、該第一のマニフォルドの境界の一部を該第二のマニフォルドが形成しているかを示すインジケータが割り当てられる該第一のセルと該第二のセルとの間のエッジとを有するセルラー空間モデルを生成するステップを有する、
ことを特徴とする変換方法。
【請求項２】
第三のマニフォルドに属する第三のセルは、第二のオブジェクトのコンピュータ表現のために該セルラー空間モデルに追加される、
ことを特徴とする請求項１記載の変換方法。
【請求項３】
連続する瞬間と関連される二次元画像から構成され、一列に配置される三次元のビデオキューブは、第一のオブジェクトと第二のオブジェクトに分割され、該変換は、第一のセルと第二のセルを生成し、該第一のマニフォルドと該第三のマニフォルドの次元は、多くとも３である、
ことを特徴とする請求項２記載の変換方法。
【請求項４】
該変換は、該コンピュータ表現の値から導出される少なくとも１つの幾何学的特性の計算に基づいて、ある値をインジケータに割り当てる、
ことを特徴とする請求項３記載の変換方法。
【請求項５】
該変換は、ある瞬間でのビデオキューブにおける二次元画像の平面による該第一のオブジェクトの断面の表面の、時間に関する変化の計算に基づいて、ある値を該インジケータに割り当てる、
ことを特徴とする請求項３記載の変換方法。
【請求項６】
Ｎ次元オブジェクトのコンピュータ表現を該オブジェクトの圧縮モデルに変換する圧縮方法であって、該変換はセルラー空間モデルを利用する、
ことを特徴とする圧縮方法。
【請求項７】
圧縮されたビデオ信号をＮ次元オブジェクトのコンピュータ表現に伸張する方法であって、該伸張はセルラー空間モデルを利用する、
ことを特徴とする伸張方法。
【請求項８】
第一の複数のセルを有する第一のセルラー空間モデルを第二の複数のセルを有する第二のセルラー空間モデルに変換する方法であって、該第一の複数のセルは該第二の複数のセルとは異なる、
ことを特徴とする変換方法。
【請求項９】
Ｎ次元の第一のオブジェクトのコンピュータ表現を該第一のオブジェクトのコンピュータモデルに変換する方法を実行するためのコンピュータプログラムであって、
該コンピュータモデルへの変換は、Ｎに等しい次元を有する第一のマニフォルドに属する第一のセルと、該第一のマニフォルドの境界に位置され、Ｎ−１に等しい低い次元を有する第二のマニフォルドに属する第二のセルと、該第一のマニフォルドの境界の一部を該第二のマニフォルドが形成しているかを示すインジケータが割り当てられる該第一のセルと該第二のセルとの間のエッジとを有するセルラー空間モデルを生成するステップを有する、
ことを特徴とするコンピュータプログラム。
【請求項１０】
Ｎ次元のオブジェクトのコンピュータ表現を該オブジェクトの圧縮モデルに変換する圧縮方法を実行するためのコンピュータプログラムであって、該変換はセルラー空間モデルを利用する、
ことを特徴とするコンピュータプログラム。
【請求項１１】
圧縮されたビデオ信号をＮ次元のオブジェクトのコンピュータ表現に伸張する方法を実行するためのコンピュータプログラムであって、該伸張はセルラー空間モデルを利用する、
ことを特徴とするコンピュータプログラム。
【請求項１２】
Ｎ次元の第一のオブジェクトのコンピュータ表現を該第一のオブジェクトのコンピュータモデルに変換するための装置であって、
該第一のオブジェクトのコンピュータ表現を取得するための取得手段と、
該第一のオブジェクトのコンピュータ表現を変換するための処理手段と、
該コンピュータモデルを出力するための出力手段とを有し、
該処理手段は、Ｎに等しい次元を有する第一のマニフォルドに属する第一のセルと、該第一のマニフォルドの境界に位置され、Ｎ−１に等しい低い次元を有する第二のマニフォルドに属する第二のセルと、該第一のセルと該第二のセルとの間のエッジとを有するセルラー空間モデルを生成可能であって、該第一のマニフォルドの境界の一部を該第二のマニフォルドが形成しているかを示すインジケータを該エッジに割り当て可能である、
ことを特徴とする装置。
【請求項１３】
圧縮されたビデオ信号をＮ次元オブジェクトのコンピュータ表現に伸張するためのビデオ伸張装置であって、
該圧縮されたビデオ信号を取得するための取得手段と、
該圧縮されたビデオ信号に基づいて該コンピュータ表現を生成するための処理手段と、
該コンピュータ表現を出力するための出力手段とを有し、
該処理手段は、セルラー空間モデルへのアクセスを有する、
ことを特徴とするビデオ伸張装置。
【請求項１４】
デジタル化されたＮ次元オブジェクトを表すためのセルラー空間を有するデータ表現であって、
該セルラー空間の第一のセルと第二のセルとの間のエッジにインジケータが割り当てられ、該インジケータは、低い次元を有する第二のマニフォルドが高い次元を有する第一のマニフォルドの一部を形成しているかを示し、該第一及び第二のマニフォルドは、該第一及び第二のセルによりそれぞれ表される、
ことを特徴とするデータ表現。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｎ次元の第一のオブジェクトのコンピュータ表現を該第一のオブジェクトのコンピュータモデルに変換する方法に関する。
また、本発明は、Ｎ次元のオブジェクトのコンピュータ表現を該オブジェクトの圧縮モデルに変換する圧縮モデルに関する。
また、本発明は、圧縮されたビデオ信号をＮ次元オブジェクトのコンピュータ表現に伸張する方法に関する。
また、本発明は、第一の複数のセルを有する第一のセルラー空間モデルを第二の複数のセルを有する第二のセルラー空間に変換する方法に関する。
【０００２】
また、本発明は、Ｎ次元の第一のオブジェクトのコンピュータ表現を第一のオブジェクトのコンピュータモデルに変換する方法を実行するコンピュータプログラムに関する。
また、本発明は、Ｎ次元オブジェクトのコンピュータ表現を該オブジェクトの圧縮モデルに変換する圧縮方法を実行するコンピュータプログラムに関する。
また、本発明は、圧縮されたビデオ信号をＮ次元オブジェクトのコンピュータ表現に伸張する方法を実行するコンピュータプログラムに関する。
【０００３】
また、本発明は、Ｎ次元の第一のオブジェクトのコンピュータ表現を第一のオブジェクトのコンピュータモデルに変換する装置に関するものであって、本装置は、該第一のオブジェクトのコンピュータ表現を取得する取得手段、該第一のオブジェクトのコンピュータ表現を変換する処理手段、及び該コンピュータモデルを出力する出力手段を有している。
【０００４】
また、本発明は、圧縮されたビデオ信号をＮ次元オブジェクトのコンピュータ表現に伸張するビデオ伸張装置に関するものであって、本ビデオ伸張装置は、該圧縮されたビデオ信号を取得する取得手段、該圧縮されたビデオ信号に基づいてコンピュータ表現を生成する処理手段、及び該コンピュータ表現を出力する出力手段を有している。
また、本発明は、デジタル化されたＮ次元オブジェクトを表現するセルラー空間を有するデータ表現に関する。
【背景技術】
【０００５】
上記方法の態様は、M  Ghanbariによる書籍“Video  Coding,  an  introduction  to  standard  codes”  The  Institution  of  Electrical  Engineers,  1999,  ISBN  0  85296  762  4,  pp.  46-48から知られている。
【０００６】
この態様では、コンピュータ表現は、連続的な瞬間でカメラのイメージプレーンにおける投射により記録される空間における三次元オブジェクトの記録を表す二次元画像の組に関するデジタル化された表現である。画像は、グレイ値が割り当てられる画素の位置のマトリクスから構成される。
【０００７】
ＤＶＤディスクへのデジタルテレビジョンの送信又は記録のような、公知の方法の大部分の応用では、固定された画素のブロックは、僅かに適応パターンに従ってコンピュータモデルに送信される。応用の例は、ＭＰＥＧ２規格を利用するＤＶＤディスクへの記録であり、ここでは、コンピュータモデルが特に経験的に固定された画素のブロックについて計算された離散コサイン変換（ＤＣＴ）係数を有している。公知のシステムの別の応用は、より適応性を可能にするＭＰＥＧ４規格に従うビデオ応用である。たとえば、二次元オブジェクトは、ＭＰＥＧ４ではオブジェクトベースの方式で符号化することができる。ＭＰＥＧ４規格は、ビデオ系列における人間の顔の圧縮モデルとして、時間に関して動画化される人間の顔の３次元モデルを可能にする。ビデオキューブにおける３次元オブジェクトのボクセル表現を自動的にモデリングする満足のいく方法が存在しないことが、現在のＭＰＥＧ４圧縮システムに問題点である。ボクセル表現は、ボクセルと呼ばれる基本次元からなるキューブの組として３次元オブジェクトを表している。ボクセルは、たとえば、ビデオ画像におけるある画素のグレイ値を示すある数に関連される３次元の幾何学的な位置として定義される場合がある。ビデオキューブは、一列に時間に関して互いに連続する、複数のビデオ画像を配置することで形成されるボクセルからなるキューブである。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の第一の目的は、特に、ユーザフレンドリーなコンピュータモデルによりＮ次元オブジェクトをモデル化するための変換方法を提供することにある。
本発明の第二の目的は、特に、Ｎ次元オブジェクトを圧縮する効率的な方法を提供することにある。
本発明の第三の目的は、特に、効率的に圧縮されたビデオ信号を伸張する方法を提供することにある。
本発明の第四の目的は、特に、関連されるＮ次元オブジェクトの変換が効率的にモデル化できるように、第一のセルラー空間モデルを第二のセルラー空間モデルに変換する方法を提供することにある。
【０００９】
本発明の第五の目的は、特に、変換方法を実行するためのコンピュータプログラムを提供することにある。
本発明の第六の目的は、特に、圧縮方法を実行するためのコンピュータプログラムを提供することにある。
本発明の第七の目的は、特に、伸張方法を実行するためのコンピュータプログラムを提供することにある。
【００１０】
本発明の第八の目的は、特に、変換方法を実行するための装置を提供することにある。
本発明の第九の目的は、特に、伸張方法を実行するための装置を提供することにある。
本発明の第十の目的は、特に、Ｎ次元オブジェクトを表現するための、容易に処理可能なデータ表現を提供することにある。
【課題を解決するための手段】
【００１１】
第一の目的は、コンピュータモデル変換が、Ｎに等しい次元を有する第一のマニフォルドに属する第一のセル、及び該第一のマニフォルドの境界に位置されてＮ−１に等しいより低い次元を有する第二のマニフォルドに属する第二のセル、並びに該第二のマニフォルドが該第一のマニフォルドの境界の一部を形成しているかを示すインジケータが割り当てられる、第一のセルと第二のセルとの間のエッジを有するセルラー空間モデルを生成するステップを有することで実現される。
【００１２】
マニフォルド（manifold）は、次元Ｄを有するポイントの集合体についての算術的な名称である。マニフォルドの例は、プレーン（面）である。ビデオキューブにおけるプレーンの例は、たとえばスクエアオブジェクトの上側からカメラにより受けたときの、連続的なビデオ画像における投射から構築されるプレーンである。それぞれの個々のビデオ画像では、この投射は、あるラインを形成し、全てのラインは、ある面を共同で形成する。オブジェクトの上側により形成される面は、勿論、湾曲される場合がある。ビデオ画像と関連される２つの空間的な次元と時間的な次元以外に、第三の空間的な次元が三次元のテレビジョンの応用において存在する場合がある。スケール次元も追加されるとき、次元数Ｎは５に等しい。たとえば、オブジェクトのテクスチャに基づいて計算された他のパラメータを表現するため、更なる次元を追加することができる。
【００１３】
セルラー空間は、グラフという特別の例である。グラフは、数学的な概念であり、セルとエッジとから構成される。セルラー空間は、あるセルがＮ次元オブジェクトのそれぞれのマニフォルドに対応し、オブジェクトの内部を形成しているＮ次元のマニフォルドから始め、ゼロ次元までの境界の全ての低い次元のマニフォルドにわたり進み、ポイントであるゼロ次元をもつ境界にあるマニフォルドを含むようなやり方で、一般に構築される。セルラー空間の特定の特性は、第二のマニフォルドが第一のマニフォルドの境界に位置されるとき、次元Ｄを有する第一のマニフォルドに対応する第一のセルと、１次元低い次元Ｄ−１を有する第二のマニフォルドに対応する第二のセルとの間のエッジが追加されることである。マザーオブジェクトの境界にある全てのより低い次元のマニフォルドは、セルラー空間モデルにおけるセル及びエッジにより明示的にモデル化される。セルラーグラフを構築する例は、図３及び図４を参照して例示される。本発明に係る変換方法では、インジケータがエッジに追加され、このインジケータは、次元Ｄをもつ第一のマニフォルドの境界にある次元Ｄ−１の第二のマニフォルドが第一のマニフォルドのオブジェクトの一部を形成するかを示している。「一部を形成すること」により意味される点が図２を参照して説明される。
【００１４】
コンピュータグラフィック技術におけるＮ次元オブジェクトをモデル化する多くの方法が存在している。しかし、これらの方法は、基準的な特性を有している。ある例は、Octree分割法（８分木法）であり、この方法では、三次元オブジェクトは、最小のキューブが所与の精度をもつ不規則な外側面に近づくまで異なる次元のキューブに分割される。他のモデルは、たとえば、三角メッシュ又はガウスバンプモデルのようなＮ次元オブジェクトの表面をモデル化する。しかし、セルラー空間は、Ｎ次元オブジェクトのトポロジー表現であり、このトポロジー表現により、必要であれば、メトリックモデルによりどのコンポーネントを補助的にモデル化することができるか、からなるオブジェクトのコンポーネントに関する指示が可能である。
【００１５】
第二のオブジェクトのコンピュータオブジェクトについて、第三のマニフォルドに属する第三のセルがセルラー空間モデルに追加されるときに有利である。両方のオブジェクトの全てのマニフォルドが１つの単一のセルラー空間で表現されるとき、それらのトポロジーの関係は、便利であって、容易に処理することができる。第一のセルと第二のセルとに属する２つの隣接するマニフォルドは、第三のセルに属しているより低い次元の共通の境界のマニフォルドを有する。セルラー空間は、境界のマニフォルドの境界の関係をモデル化する、第三のセルと第一のセルとの間の第一のエッジ、及び第三のセルと第二のセルとの間の第二のセルを有している。境界マニフォルドは、唯一のマニフォルドの一部を一般に形成しているので、エッジのうちの一方のインジケータは、「一部を形成する」値を有し、他方のエッジのインジケータは、「一部を形成していない」値を有している。セルラー空間を有している全てのオブジェクトの情報により、たとえば、オブジェクトの時間的な進化を予測すること、又はコンピュータグラフィックアプリケーションでそれを変化することが容易である。インジケータは、カメラによりビデオ系列で取得された三次元空間における２つのオブジェクトのどちらが最も後方に位置されるかに関する情報を供給する。
【００１６】
１実施の形態では、連続する瞬間に関連され、一列に配置される二次元画像からなる三次元ビデオキューブは、第一のオブジェクトと第二のオブジェクトとに分割され、変換により、第一のセルと第三のセルとが生成され、第一のマニフォルドと第三のマニフォルドの次元は、多くとも３である。
【００１７】
この実施の形態は、たとえば、二次元のテレビジョン応用で起こる。本発明に係る方法の利点は、オブジェクトの幾何学的な変換がセルラー空間モデルにより時間に関してより容易にモデル化することができる点である。ビデオキューブにおける全てのボクセルは、あるオブジェクトに割り当てられ、たとえば、第一の三次元の空間−時間オブジェクトは、歩いている人物を表し、第二のオブジェクトは、全ての他のボクセルを含んでいる人物の環境である。ビデオキューブがビデオ系列から選択されたＰ個の画像を有するとき、人物は、たとえば、多数のＰ−Ｋ画像にのみ生じることができ、代替的に、該人物は、選択されたビデオキューブの外側の更なる画像にも生じる場合がある。ビデオキューブにおけるそれぞれのオブジェクトは、同じセルラー空間モデルでモデル化される。
【００１８】
また、コンピュータ表現の値から導出される、少なくとも１つの幾何学的な特性の計算に基づいて、変換によりある値がインジケータに割り当てられるときに関心がある。セルラー空間モデルは、実際のビデオ系列に基づいて自動的に生成される。ビデオ系列における全ての種類のオブジェクトの特性を測定することができ、１以上のこれらの特性により、高い確かさをもつ正しい値がインジケータに与えられる。
【００１９】
インジケータのロバストな計算を使用する１実施の形態では、変換により、ある瞬間でのビデオキューブにおけるあるオブジェクトの二次元の断面の平面による第一のオブジェクトの断面の、表面の時間に関する変化の計算に基づいて、インジケータにある値が割り当てられる。実際に、ビデオ系列におけるあるオブジェクトの二次元の断面が現れるか、又は別のオブジェクトの断面の背後に消えるとき、オブジェクトの幾つかの画素が見えなくなるために断面に関連される画素数が変化する。
【００２０】
第二の目的は、変換がセルラー空間モデルを利用する点で実現される。セルラー空間モデルに加えて、圧縮モデルも生成される。圧縮モデルは、基準情報、たとえば、第一のオブジェクトの内部の正確な形に関する情報を含んでいる。本発明に係る方法の利点は、ビデオキューブにおけるオブジェクトは、三次元モデルにより圧縮され、従来のＭＰＥＧ４におけるオブジェクトは、異なるテレビジョン画像における二次元断面のみをモデル化及び圧縮することで二次元に圧縮される。三次元の圧縮モデルを使用することで、同じ画質で達成される圧縮要素は、二次元圧縮におけるよりも高い。代替的に、固定された圧縮要素で、三次元圧縮における画質は、二次元圧縮におけるよりも高い。ある画像を１６×１６画素ブロックに分割するその固定されたパターン及び画像の時間的な予測のため、ＭＰＥＧ２は、ビデオキューブにおける三次元オブジェクトのキャラクタを完全に利用しない。効率的な圧縮について、オブジェクトが吸収される要素が明示的に考慮される場合がある。第一のオブジェクトが三次元空間で先行する第二のオブジェクトの背後に動くとき、又は第一のオブジェクトが第二のオブジェクトの背後から現れるときに吸収が起こる。
【００２１】
国際特許出願WO-A-00/64148号は、二次元セグメントのマッチングに基づいた圧縮方法を記載している。この出願に記載される幾つかの技法は、本発明に係る方法のために要求される、ビデオキューブからＮ次元オブジェクトを得るために有効である場合がある。しかし、この特許出願は、Ｎ次元オブジェクトを明示的に使用していないが、その二次元の投射のみを使用している。
【００２２】
第三の目的は、伸張方法がセルラー空間モデルを利用することで実現される。セルラー空間モデルにおけるオブジェクトの明示的な符号化により、進歩された圧縮及び伸張が可能となる。実際に、Ｎ次元オブジェクトの再生成の間、オブジェクトの画素が目に見えるセルラー空間モデルにより計算される。
【００２３】
第四の目的は、第一の複数のセルが第二の複数のセルとは異なる点で実現される。たとえば、インターネットでの画像マテリアルのサーチのため、たとえば、第一のＮ次元オブジェクトが第二のＮ次元オブジェクトと比較されるとき、それらの関連されるセルラー空間モデルを比較することは容易である。両方のセルラー空間モデルのセル及びエッジを互いに関連付けする前に、セルラー空間モデルの一方をはじめに変換することが容易な場合がある。たとえば、照会で特定され、インターネットでの画像における第二の家について指摘された家をモデル化しているセルラー空間モデルについて、家を表しているオブジェクトの屋根はフラットである。たとえば、フラットな屋根を表しているセルは、指摘された屋根の第一の傾斜した側について再使用され、第二の傾斜した側について余分のセルを追加する場合がある。同じ種類の技法は、コンピュータグラフィックの応用について有効である。
【００２４】
第五の目的は、変換方法のためのコンピュータプログラムを含むコードを提供することで実現される。
第六の目的は、圧縮方法のためのコンピュータプログラムを含むコードを提供することで実現される。
第七の目的は、伸張方法のためのコンピュータプログラムを含むコードを提供することで実現される。
【００２５】
第八の目的は、処理手段が、Ｎに等しいより高い次元を有する第一のマニフォルドに属する第一のセルと、第一のマニフォルドの境界に位置されるＮ−１に等しいより低い次元を有する第二のマニフォルドに属する第二のセル、及び第一のセルと第二のセルとの間のエッジとを有するセルラー空間モデルを生成可能であり、第二のマニフォルドが第一のマニフォルドの境界の一部を形成しているかを示すインジケータをエッジに割り当て可能であることで実現される。
【００２６】
第九の目的は、処理手段がセルラー空間モデルへのアクセスを有することで実現される。
第十の目的は、セルラー空間の第一のセルと第二のセルとの間のエッジにインジケータが割り当てられることで実現され、このインジケータは、より低い次元を有する第二のマニフォルドが、より高い次元を有する第一のマニフォルドの一部を形成するかを示し、該第一及び第二のマニフォルドは、第一及び第二のセルのそれぞれにより表現される。
【００２７】
本発明に係る変換方法、圧縮方法、伸張方法、装置、ビデオ伸張装置及びデータ表現は、添付図面を参照して例示を通して明らかにされるであろう。
【発明を実施するための最良の形態】
【００２８】
以下の図では、既に説明された図の部材に対応する部材は、同じ参照符号により示される。あるオブジェクト及び関連されるセルラー空間モデルの対応する部材の参照符号は、１００だけ異なっている。破線で示されている部材は、任意である。本方法及び装置は、考えをより明確に理解するため、三次元又は二次元のオブジェクトを参照して説明される。記載される処理は、高次の次元について明らかな方式で算術的に規定される場合がある。
【００２９】
図１の変換方法の第二のステップは、たとえば、Ｎ次元オブジェクトのボクセル表現といった、コンピュータ表現を取得するステップ（ＡＣＱ）１である。取得するステップの前に、分割するステップ（ＰＡＲＴ）３を実行することもでき、この分割するステップでは、オブジェクトがビデオキューブから分割される。分割は、ビデオキューブにおけるそれぞれの画素を１つだけのオブジェクトに割り当てることである。三次元のビデオキューブを分割するためのアルゴリズムは、二次元画像のセグメント化に関する文献で説明されているアルゴリズムから簡単な方式で導出することができる。可能性のあるアルゴリズムは、たとえば、８×８×８ボクセルからなるキューブを、該キューブが選択された特性に関して同じ種類であることを基準が示すとき、同一のセグメントに割り当てる。特性の例は、あるボクセルに関連されたグレイ値である。ある基準の例は、２つのボクセルのキューブに関連されるヒストグラムの絶対差である。
【００３０】
【数１】
2005531862.tif 000003
式［１］では、ｉはヒストグラムのビンのインデックスであり、あるビデオキューブにおける全てのグレイ値は、Ｍ個のビンに分割される。Ｃは、キューブＫ１及びＫ２におけるビンｉに関連されるグレイ値の数である。あるキューブのボリュームＶは、正規化定数として使用される。差Ｇが小さいとき、両方のキューブは、セグメンテーションアルゴリズムに従って同一のセグメントに属する。異なる基準が文献に説明されており、それぞれの基準は、ボクセルグレイ値、ボクセルカラーのような異なる特性、Gaborフィルタリングにより得られた値又は同時生起確率行列からの値のようなテクスチャ・ディメンジョンを利用することができる。文献では、たとえば、小さなセグメントをより大きなセグメントに、逆に、大きなセグメントをより小さなセグメントに分割するグループ化するための異なるセグメンテーションアルゴリズムが存在する。
【００３１】
オブジェクトは、たとえば８分木といった、所与のモデルに従って既にモデル化されている場合がある。望まれる場合、８分木モデルは、取得ステップの間に、あるボクセル表現に変換される場合がある。代替的に、セルラー空間モデルは、たとえば、三角メッシュ表現に基づいて生成することができる。
【００３２】
図１の生成するステップ５の間、セルラー空間は、ボクセル表現から構築される。このことは、図３及び図４を参照して例示されている。
【００３３】
図３は、一次元の円の境界５１３、及び３つの直線の境界５１４，５１５及び５１６、により境界付けされるプレーン５１１を有するシンプルな二次元のフィギュア５１０を示している。直線の境界は２点により境界が設定され、たとえば、第一の直線の境界５１４は、第一のポイント５２０及び第二のポイント５２１により境界が設定されている。
【００３４】
図４は、図３に示されるフィギュアに属しているセルラー空間モデル６０９を図解的に示している。プレーン５１１に属している、セルの次元２をもつ１つのセル６１１が存在している。その次元が２よりも低い１であるプレーン５１１の境界にある全ての境界のマニフォルドについて、セル６１１と境界のマニフォルドに対応するセルとの間のセルラー空間モデル６０９にはエッジが追加されており、たとえば、セル６１１と円の境界５１３に関連されるセル６１３との間のエッジ６１２である。次元に関して１以上異なるマニフォルドに関連されるセルの間にはエッジが追加されておらず、たとえば、セル６１１と第一のポイント５２０に関連するセル６２０との間にはエッジが追加されない。図の明確さのためにインジケータ６２５のみが示されているが、インジケータは、全てのエッジに割り当てられている。このインジケータは、円の境界５１３がプレーン５１１の一部を形成しているか、言い換えれば、二次元フィギュア５１０の一部を形成しているかを示しており、その場合、たとえば、値１がインジケータに割り当てられる。円の境界５１３がプレーン５１１の一部を形成していない場合、たとえば、値０がインジケータに割り当てられる。
【００３５】
図２は、「一部を形成する」が意味することを説明する図であって、たとえば、カメラで撮影されたとき、又はコンピュータ描画プログラムで描かれたとき、ある空間における三次元シーンの二次元画像を示している。オブジェクト１３は、オブジェクト１５の前の空間に位置している。オブジェクト１５のプレーン１６は、４つの直線の境界、特に、第一の直線の境界１７及び第二の直線の境界１８により境界設定されている。プレーン１６に属するセルと第一の直線の境界１７との間のエッジに関連される正しい値をインジケータに与えるため、第一の直線の境界１７がプレーン１６の一部を形成しているか、又は等価的に、オブジェクト１５の一部を形成しているかに関する問題が問われる。このオブジェクトが、たとえば、壁におけるドアの開口を表すとき、第一の直線の境界１７は、ドアの開口と関連される。したがって、基準は、たとえば、パン機構を持つカメラにより撮影された一連のビデオ画像においてドアの開口が動くとき、第一の直線の境界１７がドアの開口に沿って動くことである。たとえばCannyエッジ検出器といったエッジ検出器により発見される境界１７のポイントでの、たとえばHough変換を利用することによる直線のフィットは、たとえば所与のグレイレベル値を超える画素のセグメントであるドアの開口のテクスチャと共に同じ速さ及び方向で動く。ドアが十分なテクスチャ情報を有している場合、たとえば特許出願WO-A-0188852に記載される予測器のような、ドアの動きを決定するために動き予測が使用される場合がある。第二の直線の境界１８もプレーン１６の境界をつけている。第二の直線の境界１８がオブジェクト１３の上側の境界を形成しており、オブジェクト１５の実際の境界はたとえばオブジェクト１３の背後に隠れていると仮定する。このとき、第二の直線の境界１８は、たとえばオブジェクト１３が左に歩いている人であるときに、オブジェクト１３に沿ってたとえば左に動き、たとえばカメラの動きの影響下では、たとえば右に動くオブジェクト１５と共に移動しない。したがって、第二の直線の境界１８は、プレーン１６の境界をつくるものの、プレーン１６の一部を形成せず、オブジェクト１３の一部を形成する。ある境界のマニフォルドがどのオブジェクトと関連されているかを定義するため、生起分析により異なるヒューリスティックを使用することもできる。第一のヒューリスティックは、たとえば、一連の画像における第一のオブジェクトの断面が減少又は増加するときを定義し、第二の隣接するオブジェクトの断面を一定に維持しつつ、第二のオブジェクトは、第一のオブジェクトをカバーし、境界のマニフォルドは、第二のオブジェクトの一部を形成する。
【００３６】
図１１を参照して、第二のヒューリスティックが例示されている。境界３０１と境界３０３０のＴ型ジャンクションでは、連続する境界３０１と関連されるオブジェクト３０５は、オブジェクト３０７及び３０９の前に位置されており、境界３０１は、オブジェクト３０５の一部を形成している。
【００３７】
第三のヒューリスティックは、ある境界がどの隣接するテクスチャと動くかを分析する。これは、動き予測により行われる場合がある。はじめに、テクスチャ分析は、たとえば、Lawsパラメータ又はウェーブレットを計算することで実行することができるか、若しくはテクスチャのフラクタル分析又はテクスチャユニットの分析を実行することもできる。さらに、同じタイプのテクスチャを有するセグメントを画像から分離して、セグメントベースの動き予測を適用することも可能である。
【００３８】
たとえば、図７のビデオキューブ２０１における第一のオブジェクト２０３と一緒の第二のオブジェクト２０４といった、第二のオブジェクトが存在する場合、第二のオブジェクトのセルラー空間にセルが追加される。たとえば、図６において、図５の第一のリング２１の内部２５及び第二のリング２３の内部２７のそれぞれについて、セル１２５及び１２７が追加されている。図６では、破線で示されているインジケータは、「一部を形成していない」ことの意味を有する値と関連される。図６の明確さのため、２つのポイントのみの関連されるセルが示されている。
【００３９】
図１における生成ステップ５でボクセル表現のセルラー空間モデル２２３が生成されるときだけでなく、モデリングステップ６でメトリックモデル２２２が生成されたときに関心がある。たとえば、三次元オブジェクトの二次元のエンベロープは、三角メッシュモデル又はコンピュータグラフィック技法から公知の別のモデルにより、メトリックにモデル化される場合がある。境界のマニフォルドを生成するためにメトリックなアルゴリズムを使用することは関心のあることである。あるオブジェクトの二次元の境界の表面を定義するため、はじめに、オブジェクトのたとえば重心が計算され、続いて、重心から遠くに最も離れているオブジェクトと関連されるポイントが重心からの半径上の境界のポイントとして考慮される場合がある。マニフォルドを識別するための他のアルゴリズムは、構成的立体幾何（CSG:  Constructive  Solid  Geometry）の技術分野で公知である。全ての境界のポイントの集合体として得られる、オブジェクトの湾曲された二次元の境界表面は、たとえば、二次元の境界表面との整合により計算されるフラットなだけであってプレーンではないマニフォルドでモデル化される場合があり、フラットなだけであってプレーンではないマニフォルドのポイントは、所定の距離よりも二次元の境界表面のポイントから更に離れることはない。別の例は、図３を参照して与えられる。たとえば境界５１６といった１つの直線の境界のみによる境界の直線部分を説明することは明らかであるが、直線の境界５１６は、セルラー空間６０９における２つのセルに属する２つのより小さい直線の境界に分割される場合もある。さらに、テクスチャ関数がメトリックモデルにも割り当てられるべきである。可能性は、１つのマニフォルドの全てのボクセルに同一の色を与えることである。別の可能性は、たとえば、ある多項式のテクスチャモデルを三角メッシュ表現におけるある三角形に追加することである。多項式のパラメータは、その後、圧縮モデルに追加される。圧縮モデル及びセルラー空間は、オブジェクトを効率的に再構成するために必要な全ての情報を与える。
【００４０】
出力するステップ７の間、セルラー空間モデル、及びもし使えるのであればメトリックモデル２２２は、たとえばメモリ２１９に出力されるか、又はデータコネクションを介してメモリ２１９に出力される。メトリックモデル及びセルラー空間のデータが圧縮モデル２２８、好ましくはオブジェクトベースの圧縮モデルを生成するために使用されるときに関心がある。たとえば、オブジェクトの三次元ウェーブレットモデルは、ハフマンビジョンの特性、及びたとえばハフマン符号化の特性を考慮しつつ、ウェーブレット係数の量子化のような圧縮技術から知られている技術を使用して、圧縮モデルとして使用することができる。
【００４１】
セルラー空間モデルを使用する利点は、圧縮及び伸張がメトリックモデルのみによるよりも更に効率的に実行することができることである。このことは、図１２及び図１３を参照して例示されている。ビデオ系列では、２つのオブジェクトが互いに吸収することが通常である。正方形７１３は、第一の画像７０１、第二の画像７０３及び第三の画像７０５の三者において同じ位置のままである。しかし、円は、正方形の背後に移動し、第三の画像にフレームを超えて進んでいる。図１３は、三次元オブジェクト７３０として異なる画像における円の動きを表している。円の一部が吸収されている、すなわち円の一部がある画像において見えないので、三次元オブジェクト７３０の形状は不規則である。たとえば、円の第三の位置７１４に対応する断面７２５は、円の一部が画像を越えているために円ではない。しかし、動きが起こっている三次元空間では、円は常に円のままである。したがって、吸収をモデル化することができる場合、円についての円筒状のモデルを使用することが可能である。このことは、セルラー空間モデルにおけるインジケータにより本方法で行われる。伸張の間、ビデオキューブの画像は圧縮モデルから生成されるとき、吸収が考慮される。たとえば、画像を再生成するとき、画像の外側にある全てのものがクリップされる。境界は、特別のケースである吸収オブジェクトである。画像の再生成は、図８の説明で更に明らかにされる。二次元画像におけるオブジェクトの変化は、シンプルな三次元オブジェクトが関連される平行移動、回転及びズームからなる場合がある。より複雑な変換モデルは、非線形にワープする。
【００４２】
たとえば、サッカーボールは、画像を通して転がり、テクスチャのモデル化は、フットボールの回転するテクスチャ関数、又は線形に平行移動するスタティックな関数を任意にモデル化する場合があり、ボールは、受け手のエンドで回転するボールの代わりにスライディングとして観察される。たとえば、イルミネーションの変化により、テクスチャ関数が時間と共に変動する場合、第一のオプションは、たとえば、４フレームを通してあるオブジェクトの軌道の微小部分のみをモデル化する、非常に短い三次元オブジェクトを利用することである。代替的なオプションは、オブジェクトに結合される基準軸のシステムにおける画素のグレイ値に関する多項式の変化といった、時間変動するテクスチャ関数の使用である。
【００４３】
圧縮は、多くの応用にとって重要である。圧縮の応用としてのデータ転送は、たとえば、インターネットビデオ、第三及び第四世代のモバイルコミュニケーション、デジタル加入者ライン（ＤＳＬ）を通したビデオオンデマンド及びデジタルテレビジョンを意味することが理解される。ストレージは、低品質であるが全ての種類のシステムで所有権を主張できる圧縮をもつ、ＤＶＤのようなデジタルディスクでのたとえばＨＤＴＶ、プロフェッショナルビデオサーバ、たとえば多くのプログラムが記録されるハードディスクに基づいたパーソナルビデオレコーダのような、たとえば高密度の記録キャリアを意味することが理解される。低密度のストレージについて、ビデオＣＤ、スモールディスク及び固体メモリのようなキャリアに関心がある。ビデオ信号は、サテライトテレビジョンからインターネットビデオまでの範囲の全ての種類のソースから生じる場合がある。本方法は、リビングルームと同様に、たとえばテレビジョンスタジオといったプロバイダのエンド、たとえばケーブルネットワーク会社といった中間体のエンドで使用される場合がある。
【００４４】
たとえばそれぞれのフレームについていわゆるスケール空間を構築することで、３次元を超える次元を得ることができる。たとえば、フレームは、フィルタの標準偏差σが連続的に増加されるガウスフィルタでフィルタリングされる場合がある。次いで、標準偏差は、余分の次元を形成する。同様に、図７に示されるように時間に関して一列にフレームを配置することでビデオキューブを形成することができるとき、異なるスケールでのフレームと呼ばれるフィルタリングされたフレームも一列に配置することができる。
【００４５】
セルラー空間モデルの別の応用は、コンピュータビジョンである。たとえば、ロボットがカメラにより撮影された画像を参照して三次元空間における動きの軌道を計画する必要があるとき、該ロボットが三次元構造及び三次元空間におけるオブジェクトの配置を良好に計算することができるように、フレームにおいてどのマニフォルドが互いに属するかを定義するように、該ロボットはセルラー空間モデルを利用することができる。さらに、特別の効果を形成するときにセルラー空間モデルは関心がある。別の応用は、たとえばインターネットでの画像の構造的な分解である。所与のオブジェクトを有する画像が発見される必要があるとき、これらのオブジェクトは、セルラー空間モデルにより説明することができる。たとえば画像サーチプログラムのユーザにより行われたサーチされたオブジェクトのスケッチ、及びインターネット上のデータベースにおける画像の両者について、セルラー空間モデルが生成される。セルラー空間モデルの使用は、医療画像処理の応用でも関心がある。
【００４６】
図８は、圧縮されたビデオ信号を伸張する方法に関するフローチャートである。はじめに、圧縮された信号が取得され（ＡＣＱ）１０１、たとえば、信号は、テレビジョン伝送ケーブルを介して到来するか、又はパーソナルビデオレコーダから到来する。必要であれば、使用可能なメトリックモデルを達成するように変換が実行される。たとえば、圧縮されたモデルにおける情報の一部は、たとえば差別的に記憶される場合があり、そのケースでは、モデルパラメータの絶対値がはじめに計算され、メトリックモデルに記憶される。好適な実施の形態では、セルラー空間モデルは、圧縮モデルと共に供給され、別の実施の形態では、セルラー空間モデルは受け手のエンドで計算される。
【００４７】
続いて、メトリックモデル及びセルラー空間モデルを利用して、たとえばビデオキューブといったコンピュータ表現が生成される（図８におけるＧＥＮステップ）。第一の実施の形態では、Ｐ個のフレームを含む三次元ビデオキューブを直接生成することができる。たとえば、三次元オブジェクトの境界がはじめに生成され、続いて、たとえばテクスチャモデルより内部が生成される。代替的に、それぞれのフレームは、第二の実施の形態では個々に生成される場合がある。第二の実施の形態は、図１２及び図５を参照して例示される。
【００４８】
たとえば第二の画像７０３が生成されているとき、円７１２及び正方形７１３の両方の境界は、たとえば第二の画像７０３のプレーンにあるそれら関連される三次元オブジェクトの投射によりはじめに計算される。続いて、円及び正方形の色を色付けするように、それぞれのテクスチャ関数が適用される。円又は正方形のいずれが前にあるかが計算されるべきである。境界のマニフォルドが正方形の一部を形成しているので、正方形が前にある。結果として、その第二の位置７１２にある円のテクスチャ関数がはじめに描かれ、正方形７１３のテクスチャ関数により上書きされる。
【００４９】
図５は、空間において相互接続される第一のリング２１と第二のリング２３の更に異なるケースを示している。たとえば境界２９及び３１のようなリングの一次元の境界は、投射アルゴリズムにより生成される。続いて、リングの画素を色付けするように、テクスチャ関数が適用される。このため、たとえばペインターアルゴリズムが使用される。これは、正しい値をオブジェクトの境界内の全ての画素に割り当てる。選択されたアルゴリズムは、第一のリング２１の画素を始めに描き、次いで、第二のリング２３の画素を描く。交線５５とデリミタ５６との間のエリアでは、第一のリング２１の画素は、選択されたアルゴリズムが使用された場合に、第二のリングの画素により不正に上書きされる。また、別の選択されたアルゴリズムが第二のリングをはじめに描いたとき、間違いの画素が存在する。これは、第一のリング２１及び第二のリング２３のいずれもが前にないためである。この問題は、セルラー空間モデルにサイクル検出アルゴリズムを提供することで解決することができる。あるサイクルが検出されたとき、たとえば交線５５といった、交線と呼ばれる余分の境界のマニフォルドが追加される必要がある。交線５５と境界５１との間の第一のリング２１の一部は、第二のリングにわたり第三の描画フェーズにおいて描かれる。交線を入力して余分の描画フェーズを実行するアルゴリズムを利用することで、全ての画素が正しい値を有する。
【００５０】
出力ステップ１０５の間、ビデオキューブは、たとえばメモリ２７１に書き込まれるか、又は一連の画像は、たとえば画像表示装置に送出される。
【００５１】
図９は、たとえば、Ｎ次元の第一のオブジェクト２０３のボクセル表現２２１といったコンピュータ表現をオブジェクト２０３のコンピュータモデルに変換するための装置２１１を示している。このため、装置２１１は、たとえば、第一のオブジェクト２０３のボクセル表現２２１を取得するためのデータコネクションである取得手段２１５を有している。好適な実施の形態では、ボクセル表現２２１は、メモリ２１９にある。さらに、装置２１１は、ボクセル表現２２１に基づいてコンピュータモデルを生成するための処理手段２１３を有している。好適な実施の形態では、処理手段２１３はプロセッサである。コンピュータモデルを出力するための出力手段２１７は、たとえば、セルラー空間モデル２２３及びメトリックモデル２２２が書き込まれるメモリ２１９とのデータコネクションである。装置２１１がビデオ処理装置２４１に組み込まれるときに関心がある。１実施の形態では、ビデオ処理装置２４１は、受信されたビデオ信号２２９のための入力２３３、及び受信されたビデオ信号を処理し、たとえばＰＡＬ信号をビデオキューブに変換することができるコンディショニングユニット２２５を有している。さらに、実施の形態では、出力のビデオ信号２３１のための出力２３５が設けられ、ビデオ信号は、出力処理ユニット２２７により形成される。出力処理ユニット２２７が圧縮モデル２２８を生成するときに特に関心がある。
【００５２】
図１０は、圧縮モデルを含む圧縮されたビデオ信号２６１を、たとえば三次元ビデオキューブ２０１といったコンピュータ表現に伸張するためのビデオ伸張装置２５１を示している。ビデオ伸張装置２５１は、圧縮されたビデオ信号２６１のための入力２５５、及びたとえばビデオキューブ２０１といった伸張されたビデオ信号２６３を出力するための出力２５７を有している。任意に、出力処理ユニット２６５は、たとえばビデオキューブをＰＡＬ又はＮＴＳＣ信号に変換するために設けられている。ビデオ伸張装置２５１の好適な実施の形態では、コンピュータ表現２６２を生成するための処理ユニット２５３は、セルラー空間モデル２７３が記憶されるメモリ２７１に接続される。
【図面の簡単な説明】
【００５３】
【図１】オブジェクトのコンピュータ表現をコンピュータモデルに変換する方法に関するブロック図である。
【図２】三次元シーンの二次元画像である。
【図３】セルラー空間モデルの構築を明らかにするための簡単な二次元オブジェクトである。
【図４】図３のオブジェクトに関連されるセルラー空間モデルである。
【図５】２つのメッシュの環状のオブジェクトを示す図である。
【図６】図５の環状のオブジェクトと関連されるセルラー空間モデルの簡略化された表現を示す図である。
【図７】２つのオブジェクトをもつビデオキューブである。
【図８】伸張方法に関するブロック図である。
【図９】Ｎ次元オブジェクトのセルラー空間モデルを作成するための装置を示す図である。
【図１０】ビデオ伸張装置を示す図である。
【図１１】３つのオブジェクトの２つの境界に関するＴ型ジャンクションを示す図である。
【図１２】時間的に連続な互いに連続する画像のシンボル表現を示す図である。
【図１３】図１２の円に関連される三次元の空間−時間オブジェクトを示す図である。
【図１】
2005531862.tif 000004
【図２】
2005531862.tif 000005
【図３】
2005531862.tif 000006
【図４】
2005531862.tif 000007
【図５】
2005531862.tif 000008
【図６】
2005531862.tif 000009
【図７】
2005531862.tif 000010
【図８】
2005531862.tif 000011
【図１０】
2005531862.tif 000012
【図９】
2005531862.tif 000013
【図１１】
2005531862.tif 000014
【図１３】
2005531862.tif 000015
【図１２】
2005531862.tif 000016
【国際調査報告】
2005531862.tif 000017
2005531862.tif 000018
2005531862.tif 000019