(57)【要約】  エンコーダ及びデコーダ、ならびに符号化及び復号化方法が、３Ｄ画像をレンダリングするために提供される。３Ｄ画像は、３Ｄ画像の要素を分析することにより分解され、３Ｄ画像内のパターンの鏡映に一致させ、３Ｄ画像をさらにレンダリングするために要素を復元する。エンコーダ及びデコーダは鏡映の原理を利用し、効果的に画像内の対称点を一致させることにより、対称点が、回転及び変換マトリックスにより特徴付けられ、これにより、３Ｄ画像内のすべての点を符号化及び復号化する要件を減少させ、計算効率を向上させる。
2015504559.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄ画像を復号化する方法であって、
画像の３Ｄ要素を含む受信されたビットストリームの要素を復号化して、前記３Ｄ画像のパターンの組を取得するステップと、
前記要素を、パターンの移動、回転及び鏡映情報に分解するステップと、
パラメータを検査して前記パターンが前記要素に一致するか否かを判定するステップと、
前記パターンの復号化された回転マトリックスを伴う前記要素及び前記パターンの組を使用して前記画像を再構成するステップと、
を含む、前記方法。
【請求項２】
前記パターンが前記要素に一致しないように前記パラメータが設定されている場合に、前記パターンの鏡映を使用して、前記３Ｄモデルを再構成するステップをさらに含み、前記分解するステップは、前記画像のパターン内の複数の鏡映された点を生成し、一致した要素を特徴付けるステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記パターンが前記要素に一致する場合、又は前記鏡映が前記要素に一致する場合、回転マトリックスを導出するステップをさらに含む、請求項２に記載の方法。
【請求項４】
前記復号化するステップは前記要素のエントロピー復号化を行うステップを含む、請求項３に記載の方法。
【請求項５】
すべての要素が一致するまで、さらなるパターンマッチングのための要素をインクリメントするステップをさらに含む、請求項４に記載の方法。
【請求項６】
前記鏡映情報は、鏡映フラグを含む、請求項５に記載の方法。
【請求項７】
前記鏡映フラグを検査して、前記パターンが前記要素に一致するか、前記パターンの鏡映が前記要素に一致するかを判定するステップをさらに含む、請求項６に記載の方法。
【請求項８】
３Ｄ画像を復号化するデコーダであって、前記３Ｄ画像内のパターンの鏡映を一致させることにより前記３Ｄ画像の要素を分析し、及び前記３Ｄ画像をさらにレンダリングするために前記要素を復元する回路を含む、前記デコーダ。
【請求項９】
前記回路は、一致した前記要素を移動、変換、スケーリング及び鏡映要素に分解するための回路をさらに含む、請求項８に記載のデコーダ。
【請求項１０】
前記回路は、前記パターンが前記要素に一致するか、又は前記パターンの前記鏡映が前記要素に一致するかを判定する回路をさらに含む、請求項９に記載のデコーダ。
【請求項１１】
前記分解する回路は、回転マトリックスを分解して、変換、回転、スケーリング及び対称要素を取得する回路をさらに含む、請求項１０に記載のデコーダ。
【請求項１２】
前記対象要素は、鏡映フラグを含む、請求項１１に記載のデコーダ。
【請求項１３】
３Ｄ画像を符号化する方法であって、
前記３Ｄ画像を符号化して、前記３Ｄ画像の要素を表す少なくとも一つのパターンを取得するステップと、
前記３Ｄ画像のおのおのの要素に対して、前記要素を前記パターンと比較して前記要素が前記パターンに一致するか否かを判定するステップと、
前記要素が前記パターンと一致する場合、前記要素に関係するパラメータを符号化して、符号化された表示される要素を取得するステップと、
鏡映フラグを、前記パターンが前記要素に一致することを示す値に設定するステップと、
を含む、前記方法。
【請求項１４】
前記パラメータを符号化するステップは、変換マトリックスを生成して、前記パターンに関連する移動、回転及び倍率を取得する、請求項１３に記載の方法。
【請求項１５】
前記パターンが前記要素に一致する場合、前記鏡映フラグを０に設定するステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記パターンの前記鏡映が前記要素に一致する場合、前記鏡映フラグを１に設定するステップをさらに含む、請求項１５に記載の方法。
【請求項１７】
前記符号化するステップは、前記３Ｄ画像のエントロピー符号化を行うことを含む、請求項１６に記載の方法。
【請求項１８】
３Ｄ画像を符号化するエンコーダであって、
前記３Ｄ画像の要素を表す少なくとも一つのパターンを取得するエントロピーエンコーダと、
前記要素を前記パターンと比較し、前記要素が前記パターンに一致するか否かを判定する回路と、
前記要素に関連するパラメータを符号化して、符号化された表される要素を取得し、鏡映フラグを前記パターンが前記要素に一致することを示す値に設定する回路と、
を含む、前記エンコーダ。
【請求項１９】
パラメータを符号化する前記回路は、変換マトリックスを生成して、前記パターンに関連する移動、回転及び倍率を取得する回路をさらに含む、請求項１８に記載のエンコーダ。
【請求項２０】
前記パターンが前記要素に一致する場合、前記鏡映フラグを０に設定し、前記パターンの鏡映が前記要素に一致する場合、前記鏡映フラグを１に設定する回路をさらに含む、請求項１９に記載のエンコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元（３Ｄ）モデルに関し、より詳細には、３Ｄ画像をレンダリングするための回転マトリックスおよび変換マトリックスを構成する鏡映技法を用いた３Ｄプログラムにおける３Ｄモデルの送信に関する。
【背景技術】
【０００２】
建築デザイン、化学プラント及び機械のＣＡＤデザインのような大きな３Ｄ工学モデルは、ＳＥＣＯＮＤ  ＬＩＦＥ及びＧＯＯＧＬＥ  ＥＡＲＴＨ等の様々な仮想世界のアプリケーションにおいてますます開発されている。多くの工学モデルにおいて、それぞれ平均で数百程度のポリゴンを有する小サイズから中サイズの結合された要素が多数存在する。さらに、これらのモデルのタイプは、図１に示すミーティングルームのように、様々な位置、大きさ及び方向が反復される多くの幾何学的特徴を有する。このモデルは、表示されることが意図される画像の正確で効果的なレンダリングを生成するために、通常、符号化され、圧縮され、３Ｄに復号化されなければならない。この画像のモデルは、高度に相互接続され、しばしば非常に複雑な幾何学パターンを含む、画像の３Ｄメッシュを生成する。用語「３Ｄモデル」は、本明細書で用いられるとき、表示されることが意図される画像だけでなく、モデル自体のことも言う。そのため、用語「３Ｄモデル」及び「３Ｄ画像」は、本明細書を通して、交互に使用される。
【０００３】
１９９０年代前半から、３Ｄメッシュを効果的に圧縮するために、多くのアルゴリズムが提案されてきた。例えば、非特許文献１を参照されたい。非特許文献１に示すように、ほとんどの既存の３Ｄメッシュ圧縮アルゴリズムは、小さな三角形の高密度なメッシュを有する滑らかな表面に対して最もよく機能する。しかし、大きな３Ｄモデル、特に工学図面及びデザインにおいて使用する３Ｄモデルは、通常少数の大きな三角形をもち、しばしば任意に連続した、多くの結合された要素を有する。建築及び機械のＣＡＤモデルは、通常、３Ｄの圧縮及びレンダリングに最適でない非特許文献１の方法により作製した多くの滑らかでない表面を有する。
【０００４】
さらに、初期の３Ｄメッシュ圧縮技術のほとんどは、結合された要素を各々分離して扱う。実際、エンコーダの能力は、幾何学的な特徴パターンの繰り返しの表現において冗長を取り除くことにより大きく発展できる。大きな３Ｄ工学モデルにおいてこの幾何学的な特徴の繰り返しを自動的に発見する方法が提案されてきた。非特許文献２を参照されたい。しかし、非特許文献２は、３Ｄ工学モデルの完全な圧縮技術を提供していない。例えば、非特許文献２は、結合された要素を対応する幾何学的パターンから復元するのに必要な情報の圧縮に対する解決を提供していなかった。３Ｄ工学モデルがたいてい含む結合された要素の大きなサイズを考慮に入れると、この種の情報が大量の記憶領域及び分解及び最終的なレンダリングのための多大なコンピュータ処理時間を消費するという回避できない結論を導く。加えて、非特許文献２は、要素の方向の正規化のみ開示しており、そのため、様々な大きさの特徴の繰り返しを発見するのに適切ではない。
【０００５】
本発明の所有者は、K.Cai、Q.Chen及びJ.Tengの、発明の名称が“Efficient Compression Scheme for Large 3D Engineering Modeles”である特許文献１の国際出願の所有者でもあり、特許文献１は、多くの小から中サイズの結合された要素から構成される３Ｄメッシュの圧縮方法を開示しており、様々な位置、大きさ及び方向を繰り返す幾何学的特徴を有しており、この開示は明確に本明細書に参照により組み込まれている。しかし、本発明は、正しく厳格に適合した基準を使用することを要求し、強い相関関係の要件を有し、それゆえ同様の幾何学的特徴を有する多くの要素は、この解決により無視される。
【０００６】
したがって、既存の技術は、パターンと、パターンの鏡像対称である要素との相関関係を無視する。「鏡像対称」は、本明細書で用いられるとき、そのパターンの鏡映と十分に一致できるパターンの要素のことを言う。本技術分野のこれらの問題を克服するために、鏡像対称の一致の基準を拡張することが有用であり、鏡像対称の変換により取得できる要素を効果的に表すことができる。これは、本技術分野において、今まで達成されていなかった。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】国際公開番号ＷＯ２０１０／１４９４９２号公報パンフレット
【特許文献２】欧州特許出願公開ＥＰ２２６１８５９号公報
【非特許文献】
【０００８】
【非特許文献１】J.L.Peng,C.S.Kim and C.C.Jay Kuo, Technologies for 3D Mash Compression: A survey; ELSEVIER Journal of Visual Communication and Image Representation, 16(6), 688-733, 2005.
【非特許文献２】D.Shikhare, S.Bhakar and S.P.Mudur, Compression of Large 3D Engineering Models using Automatic Discovery of Repeating Geometric Features; 6th International Fall Workshop on Vision, Modeling and Visualization (VMV2001), November 21-23, 2001, Stuttgart, Germany
【非特許文献３】Rossignac & Szymczak “Computational Geometry: Theory and Applications”, May 2, 1999
【発明の概要】
【０００９】
本技術分野におけるこれら及び他の問題は、本発明に従って提供される方法及び装置により解決される。本発明は、エンコーダ及びデコーダ、ならびに符号化及び復号化方法を提供し、３Ｄ画像内のパターンの鏡映に一致させることにより３Ｄ画像の要素を分析し、３Ｄ画像のさらなるレンダリングのために、要素を復元する。
【図面の簡単な説明】
【００１０】
【図１】多くの反復する特徴を有する、例示的な３Ｄのモデル（ミーティングルーム）を示す図である。
【図２】本発明のＣＯＤＥＣにおいて使用されるべき好ましいエンコーダの例を示す図である。
【図３】本発明のＣＯＤＥＣにおいて使用される好ましいデコーダの例を示す図である。
【図４Ａ】本発明に従う３Ｄ画像を符号化する好ましい方法をしめすフローチャートである。
【図４Ｂ】本発明に従う３Ｄ画像を復号化する好ましい方法をしめすフローチャートである。
【図５】図５Ａは、パターンを描写した図であり、図５Ｂは、パターンの回転を描写した図であり、図５Ｃは、パターンの鏡映を描写した図である。
【発明を実施するための形態】
【００１１】
好ましい実施形態において、本発明を実装するエンコーダ及びデコーダ（ＣＯＤＥＣ）は、それぞれ図２及び３において示される。これらのＣＯＤＥＣは、簡易化された移動による鏡映を含む変換マトリックス、３つのオイラー角及び鏡映フラグを効果的に表す反復構造（回転及び鏡映）のアルゴリズムを実装する。これは、以下に詳細に示されるように、効果的な画像の３Ｄ符号化及び復号化を提供するために、パターン及びパターンの連続が簡易化されるようにすることができる。
【００１２】
一般的に、３Ｄ符号化／復号化は、回転、鏡映、移動及びスケーリングの量子化を伴う反復構造について対処することが必要で、「反復構造（回転、鏡映、移動及びスケーリング）」と表される。従来は、本技術分野では、鏡映の特性に対処する能力なしに反復構造（回転、移動及びスケーリング）の分析を適用することにより３Ｄ符号化／復号化に対処していた。本発明は、集中的な反復構造（回転及び鏡映）を適用することによりその問題に対処し、符号化・復号化処理の反復構造（移動及び回転）の分析を減少することを可能にする対称の特性を利用する。当業者は、本発明のＣＯＤＥＣが、このような３Ｄレンダリングが要求される様々な環境に対する柔軟性を提供するために、ハードウェア、ソフトウェア及びファームウェア又はこれらの種類の組み合わせに実装できることが理解できるであろう。特定用途向け集積回路（ＡＳＩＣ）、プログラム可能アレイ論理回路、ディスクリート半導体回路、プログラム可能デジタル信号処理回路、コンピュータ可読媒体（一時的又は非一時的）は、とりわけ、本発明を実装するのにすべて利用できる。これらはすべて、本発明を実装可能な非限定的な例であり、当業者は、他の実施形態も適用可能であることが理解できるであろう。
【００１３】
図２は、本発明の一実施形態に従う、３Ｄメッシュモデルを符号化するエンコーダを示す。結合された要素は、通常結合された要素の認識を提供する三角横断ブロック１００により区別される。正規化ブロック１０１は、各々の結合された要素を正規化する。一実施形態において、正規化は、一又はそれより多くの要素を備える３Ｄメッシュモデルを符号化する方法を開示する共同出願である欧州特許出願ＥＰ０９１３０５５２７（特許文献２として公開）に記載された技術に基づく。参照により本明細書に明確に組み込まれた非特許文献２に記載された正規化技術は、要素を３Ｄ空間の正規直行基底と決定するステップであって、要素の頂点の各々は、頂点の座標データ及び同じ三角形に属する他の頂点の座標データから決定される重みが割り当てられる、ステップと、要素の物体座標系情報を符号化するステップと、ワールド座標系に対して要素の方向を正規化するステップと、頂点の位置を量子化するステップと、量子化された頂点位置を符号化するステップとを含む。当業者には、他の正規化技術が使用できることが理解できるであろう。本明細書に記載されたＣＯＤＥＣの従来の使用は、各々の結合された要素の方向及びスケーリング両方の正規化を提供していた。
【００１４】
図２のブロック１０２は、反復される幾何学的パターンを発見するための正規化された要素を一致させ、Ｓｈｉｋｈａｒｅ等の一致方法を使用できる。入力モデルにおける各々の結合された要素は、対応する幾何学的パターンの識別子（ＩＤ）１３０、及び幾何学的パターン１２０から要素を再構成するための変換情報により表される。変換情報１２２は、対応する結合された要素の、クラスタを表現する幾何学的パターン、３つの方向軸１２６および倍率１２８を含む。平均１２４（すなわち幾何学的パターンの中心）は、送信されないが、デコーダにおいて再計算される。エッジブレーカーエンコーダ１０３は、符号化のために幾何学的パターン１２０を受信する。エッジブレーカー符号化／復号化は、三角表面の圧縮及び伸張に対する効果的なスキームを提供する周知の技術である。エッジブレーカーアルゴリズムは、参照により本明細書に明確に組み込まれている非特許文献３により記述される。ｋｄ木ベースのエンコーダ１０は、結合された要素の各々の平均（すなわち中央）を提供し、一方でクラスタリングがブロック１０５において具体的に行われ、エントロピーエンコーダ１０６による変換情報及び平均情報による最終的な符号化のために、方向軸情報１３２及び倍率情報１３８が生成される。
【００１５】
同様に、図３においてデコーダは、エンコーダから符号化されたビットストリームを受信し、第１のエントロピー復号化２００であり、異なる部分のデータが取得される。データの１つの部分は、幾何学的パターン２３２を取得するためにエッジブレーカーデコーダ２０１に入力される。データの他の部分は、幾何学的パターンのクラスタの表現を含み、ｋｄ木ベースのデコーダ２０２に入力され、おのおのの結合された要素の平均（すなわち中央）２３４を提供する。エントロピーデコーダ２００はまた、方向軸情報２４４及び倍率情報２４６を出力する。ｋｄ木ベースのデコーダ２０２は平均２３４を計算し、他の要素の情報（パターンＩＤ２３６、方向軸２３８及び倍率２４０）と共に回復ブロック２４２に配信される。回復ブロック２４２は、反復要素を正規化された結合された要素を復元するための第１のブロック２０３、結合された要素（反復しない結合された要素を含む）を復元するための第２のブロック２０４、及び結合された要素を組み立てるための第３のブロックにおいて回復する。一実施形態において、デコーダは、そのインスタンスを復元する前に、おのおのの反復パターンの平均を計算する。さらなるブロック（図３において図示しない）において、結合された要素から完全な要素が組み立てられる。
【００１６】
本発明にしたがって、本発明の反復構造（回転及び鏡映）技術を、エンコーダのブロック１０２及びデコーダのブロック２０４に実装できる。これは、本明細書に記載のように、本発明のＣＯＤＥＣが本発明の鏡像対称の性質を、さらなるレンダリングのための効果的な３Ｄメッシュの符号化／復号化画像に利用することができるようにする。ブロック１０２及び２０４は、３Ｄ画像におけるパターンの鏡映を一致させることにより３Ｄ画像の要素を分析し、及びさらに以下で述べる鏡像対称技術により画像の結合された要素を復元する機能を提供する。
【００１７】
本発明のＣＯＤＥＣは、鏡像対称の新しいコンセプトに基づいて、３Ｄモデルを効果的に圧縮するよう設計されている。発明者が発見した鏡像対称の技術において、ＣＯＤＥＣは画像の要素が画像内のパターンの鏡映と一致しているか否か検査する。したがって、符号化の冗長性が取り除かれ、複雑な計算が少なくなることにより、大きな圧縮が達成される。本発明のＣＯＤＥＣは要素の画像内のパターン、又は画像内のパターンの鏡映に対する完全な一致を必要としない。
【００１８】
本発明に従う鏡像対称は、３Ｄエントロピー符号化／復号化の３つの広義の限定されない方法を提案する。第１に、ＣＯＤＥＣは、３Ｄモデルの要素を、パターン自体と同様、パターンの鏡映にも一致させることを試みる。第２に、一致した要素へのパターンからの変換は、移動、回転及び対称／反復のフラグに分解され、ここで回転はオイラー角により現される。第３に、全てのパターンの対象は、鏡像対称の検出を実装する必要があるかどうかを判定する前に、すべてのパターンの対象が検査される。パターンが対称それ自体である場合、鏡像対称検出の複雑さのコスト及び対称／反復フラグの若干のコストが節約される。
【００１９】
図４Ａを参照して、より詳細に説明するように、本発明に従う３Ｄ画像を符号化する方法は、ステップ２０６において開始する。任意のパターンの要素へのマッチングがステップ２０８において開始される。ステップ２１０において、任意のパターンが画像内の任意のパターンに一致するかどうかの第１の判定が行われる。任意のパターンが画像内の任意のパターンに一致する場合、ステップ２１２において、回転マトリックスが生成され、鏡映フラグが「０」に設定され、ステップ２１４においてパターンが要素に一致すると判定され、ステップ２１６において方法は停止する。
【００２０】
ステップ２１０において、要素がどのパターンにも一致しないと判定されると、ステップ２１８において、要素の鏡映が生成され、ステップ２２０において再び本発明に従うマッチングが行われる。ステップ２２２において、任意のパターンが要素の鏡映に一致するかどうか判定される。任意のパターンが要素の鏡映に一致しない場合、ステップ２２６においてマッチング不可能となり、ステップ２１６において方法が停止する。任意のパターンが要素の鏡映に一致する場合、ステップ２２４において回転マトリックスが生成され、鏡映フラグが「１」に設定される。ステップ２１４において鏡映が判定され、ステップ２１６において方法が停止する。この処理は、複雑な３Ｄ画像の符号化に必要なので、複数の要素に対して行うことができることが理解できるであろう。
【００２１】
この時点において３Ｄ画像のパラメータを伴うビットストリームが符号化され、図４Ｂのデコーダに送信される。パターンデータを伴うビットストリームがステップ２３０において受信され、ステップ２３２においてデータがエントロピー復号化され、ステップ２３４においてメモリに格納されるデータのパターンセットが生成される。エントロピー復号化ステップ２３２はまた、ステップ２３６において、回転データ、変換データ、スケーリングデータ、パターンＩＤ及び「０」又は「１」に設定される鏡映フラグを含む変換情報を分解する。
【００２２】
次いで、ステップ２３８において、鏡映フラグが１に設定されているか否かが判定される。鏡映フラグが１に設定されていない場合、鏡映フラグは０であり、ステップ２４２において要素により再構成される。ステップ２４４において、一致し、再構成されるべき他の要素があるか否かが判定される。一致し、再構成されるべき他の要素がない場合、ステップ２４８において方法は停止する。一致し、再構成されるべき他の要素がある場合、ステップ２４６において次の要素が使用され、ステップ２３６から処理が繰り返される。
【００２３】
ステップ２３８において、鏡映フラグが１であり、ステップ２４０においてパターンの鏡映が要素により再構成されると、方法はステップ２４４に移動する。すでに述べたようにステップ２４４において他の要素があるかどうかが判定され、他の要素がない場合、方法はステップ２４８において停止する。さもなければ、ステップ２４６において、次の要素が使用され、ステップ２３６から方法が繰り返される。この時点で、３Ｄ画像は本発明にしたがって鏡像対称により完全に再構成され、これは本技術分野において従来達成されていなかった。
【００２４】
図４Ａ及び図４Ｂのフローチャートの方法に関して説明したように本発明の鏡像対称の発見を実装するために、図５Ｃを参照して、反復構造がパターンの回転及び移動により取得できる要素として定義される。例えば上記の特許文献１において、及び図２のエンコーダ及び図３のデコーダにより以前に達成されたものとして、この要素が検出されると、この要素は、実際の幾何学情報よりもむしろ、並進ベクトル、回転マトリックス及びパターンＩＤにより表される。残念なことに、これは反復構造がパターンに正確に一致することを必要とし、これは、図５Ｂに示されるように、鏡映パターンの要素を表すことができないことを意味する。しかし、図５Ｂの要素が図５Ａのパターンと酷似しているので、図５Ｂの再符号化は計算が重複し、それゆえ付随的に費用がかかる。
【００２５】
この、必要のない計算上の複雑さ及び費用を緩和するために、発明者は、要素を、パターンの回転及び／又は変換のみによるよりもむしろパターンの鏡映により取得できることを発見した。これは、パターンの頂点又は候補の要素をｎ×３のマトリックスにより表示することにより達成される。マトリックスは列の各々が頂点を表し、ｎは頂点の数である。要素の並進ベクトルは、簡単にするために考慮されない。すなわち、以下で検討されるすべての要素が基点に移動されるが、当業者は参照フレームの基点以外を使用することができ、このような場合に点の移動が必要になるであろうことが理解できるであろう。これらの可能性は共に本発明の範囲内である。
【００２６】
パターンを
【００２７】
【数１】
2015504559.tif 000003
【００２８】
であると仮定する一方で、候補の要素は、
【００２９】
【数２】
2015504559.tif 000004
【００３０】
であると仮定する。要素がパターンの回転により取得できる場合、以下の条件
【００３１】
【数３】
2015504559.tif 000005
【００３２】
を満足する３×３の回転マトリックス
【００３３】
【数４】
2015504559.tif 000006
【００３４】
が存在しなければならない。
【００３５】
本発明において、パターンの８つの鏡像対称は、第１に鏡映により生成される。
【００３６】
【数５】
2015504559.tif 000007
【００３７】
原型のパターンはＰ０００である。これは、ｉ＝１のときにｘ軸に関して変換された鏡像対称である。同様に、ｊ（ｋ）＝１のときには、ｙ（ｚ）軸に関する鏡映となる。
【００３８】
候補の要素が、パターンの任意の８つの鏡映の回転により取得できる限り（すなわちＣ＝ＲＰｉｊｋ）、候補の要素は、並進ベクトル、回転マトリックス、パターンＩＤ及び鏡像対称インデックスにより表すことができる。したがって、図５Ｂにおいて表されるような要素を、効果的に圧縮できる。
【００３９】
各成分は独立したものではないため、回転マトリックスを表すためにすべての要素が符号化される必要はない。好ましい実施形態において、オイラー角の表現が利用される。すなわち、回転マトリックスＲが３つのオイラー角θ、Φ及びΨ
【００４０】
【数６】
2015504559.tif 000008
【００４１】
により表される。
【００４２】
【数７】
2015504559.tif 000009
【００４３】
θ、Φ、Ψは、回転マトリックスの９つの成分の代わりに量子化され、符号化される。
【００４４】
回転マトリックスＲを回復するために、
【００４５】
【数８】
2015504559.tif 000010
【００４６】
この方法は、マトリックスが［数３］の式（１）〜（３）を満足する場合にのみ機能する。このため、回転マトリックスと鏡映マトリックスの積、ＲＳｉｊｋの直接圧縮を達成できない。
【００４７】
候補の要素がＣ＝ＲＰｉｊｋを満足する場合、候補の要素はパターンの反復構造又は鏡像対称とみなされ、パターンの鏡映が要素に一致する仕様を導き出すことが必要となる。好ましい実施形態において、３−ｂｉｔフラグは、ｉ、ｊ及びｋの８つの組み合わせを示すのに使用される。しかし、各々の場合を特定する必要はない。
【００４８】
２つの鏡像対称変換は、ある回転と同等である。したがって、ｍｏｄ（ｉ＋ｊ＋ｋ，２）＝０である場合、Ｓｉｊｋを回転マトリックス自体とみなすことができる。さもなくば、ｍｏｄ（ｉ＋ｊ＋ｋ，２）＝１である場合、Ｓｉｊｋを１つの回転マトリックスＨ及び１つの鏡映マトリックスＧに分解できる。つまり、Ｓｉｊｋ＝ＨＧとなる。
【００４９】
Ｇを
【００５０】
【数９】
2015504559.tif 000011
【００５１】
と特定することがさらに好ましい。そうすると、Ｓｉｊｋは、
【００５２】
【数１０】
2015504559.tif 000012
【００５３】
と書き換えることができる。
【００５４】
例１：ｉ＝１、ｊ＝１、ｋ＝０の場合、
【００５５】
【数１１】
2015504559.tif 000013
【００５６】
したがって、
【００５７】
【数１２】
2015504559.tif 000014
【００５８】
例２：ｉ＝０、ｊ＝１、ｋ＝０の場合、
【００５９】
【数１３】
2015504559.tif 000015
【００６０】
したがって、
【００６１】
【数１４】
2015504559.tif 000016
【００６２】
例１及び２のマトリックスＨは、式（１）〜（３）を満足するとみることができる。
【００６３】
したがって、Ｈは回転を示し、回転マトリックスＲと結合でき、マトリックスＲＳを取得できる。
【００６４】
【数１５】
2015504559.tif 000017
【００６５】
鏡像対称の検出を簡略化するために、候補の要素を、パターンの８つの鏡映全てと比較する必要がないことを認識することは有効である。式（４）に示すとおり、
【００６６】
【数１６】
2015504559.tif 000018
【００６７】
であり、これは８つの鏡映のいずれも、パターンの回転Ｈ、又はｚ軸に関する鏡映の回転により表すことができることを意味する。より詳細には、パターンが対称性をもつそれ自体である場合、８つの鏡映のいずれも、回転により取得できる。
【００６８】
したがって、本発明の好ましい実施形態において、反復構造及び鏡像対称の検出は以下のように実装される。候補の要素をパターンと比較する。要素とパターンとがよく一致する場合、回転マトリックスを導き出す。それ以外の場合は、ｚ軸に関するパターンの鏡映を生成し、
【００６９】
【数１７】
2015504559.tif 000019
【００７０】
を取得する。候補の要素を鏡映Ｐ００１と比較する。要素とパターンとがよく一致する場合、回転マトリックスを導き出す。それ以外の場合は、候補の要素は、反復構造又は鏡像対称とすることができない。
【００７１】
符号化／復号化方法は、３Ｄモデルの要素を表現する既存のパターンに利用できる。各々の要素に対して、ＣＯＤＥＣはその要素をすべてのパターンと比較する。要素が、パターンの１つと一致する場合、並進ベクトル、回転マトリックス、パターンＩＤ及び対称／反復に対するフラグは、要素を表すために符号化される。式（４）において実際に対称／反復フラグはｋであり、回転マトリックスはＲＳである。以下は要素の圧縮に焦点を当てる。
【００７２】
すべてのパターンの対称は、鏡映を生成する必要があるかどうかを決定するために検査される。各々のパターンは要素と比較される（必要であれば、パターンの鏡映も要素と比較される）。パターン（又はパターンの鏡映）の１つが要素と一致する場合、対称／反復フラグは０に設定される。さもなければ、パターンの鏡映の１つが要素に一致する場合、フラグは１に設定される。並進ベクトル、パターンＩＤ及び対称／反復フラグは既存の技術で符号化され、回転マトリックスは上述したように圧縮される。
【００７３】
このような方法において、３Ｄメッシュ画像を、鏡像対称の性質により、画像から効果的にコスト効率よく生成できる。これは、パターンの鏡映の組を伴う複雑な画像を、回転および移動を使用して符号化及び復号化することを可能にし、周知のパラメータの組に対する符号化及び復号化の問題を大きく減少させる。このような結果は本技術分野において従来達成されていなかった。
【図２】
2015504559.tif 000020
【図３】
2015504559.tif 000021
【図４Ａ】
2015504559.tif 000022
【図４Ｂ】
2015504559.tif 000023
【図５】
2015504559.tif 000024
【図１】
2015504559.tif 000025
【手続補正書】
【提出日】平成26年11月25日(2014.11.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
３Ｄ画像を復号化する方法であって、
画像の３Ｄ要素を含む受信されたビットストリームの要素を復号化して、前記３Ｄ画像のパターンの組を取得するステップと、
前記要素を、パターンの移動、回転及び鏡映情報に分解するステップと、
パラメータを検査して前記パターンが前記要素に一致するか否かを判定するステップと、
前記要素及び前記パターンの組を前記パターンの復号化された回転マトリックスと共に使用して前記画像を再構成するステップと、
を含む、前記方法。
【請求項２】
前記パターンが前記要素に一致しないように前記パラメータが設定されている場合に、前記パターンの鏡映を使用して、前記３Ｄモデルを再構成するステップをさらに含み、前記分解するステップは、前記画像のパターン内の複数の鏡映された点を生成し、一致した要素を特徴付けるステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記パターンが前記要素に一致する場合、又は前記鏡映が前記要素に一致する場合、回転マトリックスを導出するステップをさらに含む、請求項２に記載の方法。
【請求項４】
前記復号化するステップは前記要素のエントロピー復号化を行うステップを含む、請求項３に記載の方法。
【請求項５】
すべての要素が一致するまで、さらなるパターンマッチングのための要素をインクリメントするステップをさらに含む、請求項４に記載の方法。
【請求項６】
前記鏡映情報は、鏡映フラグを含む、請求項５に記載の方法。
【請求項７】
前記鏡映フラグを検査して、前記パターンが前記要素に一致するか、又は前記パターンの鏡映が前記要素に一致するかを判定するステップをさらに含む、請求項６に記載の方法。
【請求項８】
３Ｄ画像を復号化するデコーダであって、前記３Ｄ画像内のパターンの鏡映を一致させることにより前記３Ｄ画像の要素を分析し、及び前記３Ｄ画像をさらにレンダリングするために前記要素を復元する回路を含む、前記デコーダ。
【請求項９】
前記回路は、一致した前記要素を移動、変換、スケーリング及び鏡映要素に分解する回路をさらに含む、請求項８に記載のデコーダ。
【請求項１０】
前記回路は、前記パターンが前記要素に一致するか、又は前記パターンの前記鏡映が前記要素に一致するかを判定する回路をさらに含む、請求項９に記載のデコーダ。
【請求項１１】
前記分解する回路は、回転マトリックスを分解して、変換、回転、スケーリング及び対称要素を取得する回路をさらに含む、請求項１０に記載のデコーダ。
【請求項１２】
前記対象要素は、鏡映フラグを含む、請求項１１に記載のデコーダ。
【請求項１３】
３Ｄ画像を符号化する方法であって、
前記３Ｄ画像を符号化して、前記３Ｄ画像の要素を表す少なくとも一つのパターンを取得するステップと、
前記３Ｄ画像のおのおのの要素に対して、前記要素を前記パターンと比較して前記要素が前記パターンに一致するか否かを判定するステップと、
前記要素が前記パターンと一致する場合、符号化された表示される要素を取得するために前記要素に関係するパラメータを符号化するステップと、
鏡映フラグを、前記パターンが前記要素に一致することを示す値に設定するステップと、
を含む、前記方法。
【請求項１４】
前記パラメータを符号化するステップは、変換マトリックスを生成して、前記パターンに関連する移動、回転及び倍率を取得することを含む、請求項１３に記載の方法。
【請求項１５】
前記パターンが前記要素に一致する場合、前記鏡映フラグを０に設定するステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記パターンの前記鏡映が前記要素に一致する場合、前記鏡映フラグを１に設定するステップをさらに含む、請求項１５に記載の方法。
【請求項１７】
前記符号化するステップは、前記３Ｄ画像のエントロピー符号化を行うことを含む、請求項１６に記載の方法。
【請求項１８】
３Ｄ画像を符号化するエンコーダであって、
前記３Ｄ画像の要素を表す少なくとも一つのパターンを取得するエントロピーエンコーダと、
前記要素を前記パターンと比較し、前記要素が前記パターンに一致するか否かを判定する回路と、
前記要素に関連するパラメータを符号化する回路であって、符号化された表される要素を取得し、鏡映フラグを前記パターンが前記要素に一致することを示す値に設定する、前記回路と、
を含む、前記エンコーダ。
【請求項１９】
パラメータを符号化する前記回路は、変換マトリックスを生成して、前記パターンに関連する移動、回転及び倍率を取得する回路をさらに含む、請求項１８に記載のエンコーダ。
【請求項２０】
前記パターンが前記要素に一致する場合、前記鏡映フラグを０に設定し、前記パターンの鏡映が前記要素に一致する場合、前記鏡映フラグを１に設定する回路をさらに含む、請求項１９に記載のエンコーダ。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
【図１】多くの反復する特徴を有する、例示的な３Ｄのモデル（ミーティングルーム）を示す図である。
【図２】本発明のＣＯＤＥＣにおいて使用されるべき好ましいエンコーダの例を示す図である。
【図３】本発明のＣＯＤＥＣにおいて使用される好ましいデコーダの例を示す図である。
【図４Ａ】本発明に従う３Ｄ画像を符号化する好ましい方法をしめすフローチャートである。
【図４Ｂ】本発明に従う３Ｄ画像を復号化する好ましい方法をしめすフローチャートである。
【図５】図５Ａは、パターンを描写した図であり、図５Ｂは、パターンの鏡映を描写した図であり、図５Ｃは、パターンの回転を描写した図である。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
図２のブロック１０２は、反復される幾何学的パターンを発見するための正規化された要素を一致させ、Ｓｈｉｋｈａｒｅ等の一致方法を使用できる。入力モデルにおける各々の結合された要素は、対応する幾何学的パターンの識別子（ＩＤ）１３０、及び幾何学的パターン１２０から要素を再構成するための変換情報により表される。変換情報１２２は、対応する結合された要素の、クラスタを表現する幾何学的パターン、３つの方向軸１２６および倍率１２８を含む。平均１２４（すなわち幾何学的パターンの中心）は、送信されないが、デコーダにおいて再計算される。エッジブレーカーエンコーダ１０３は、符号化のために幾何学的パターン１２０を受信する。エッジブレーカー符号化／復号化は、三角表面の圧縮及び伸張に対する効果的なスキームを提供する周知の技術である。エッジブレーカーアルゴリズムは、参照により本明細書に明確に組み込まれている非特許文献３により記述される。ｋｄ木ベースのエンコーダ１０４は、結合された要素の各々の平均（すなわち中央）を提供し、一方でクラスタリングがブロック１０５において具体的に行われ、エントロピーエンコーダ１０６による変換情報及び平均情報による最終的な符号化のために、方向軸情報１３２及び倍率情報１３８が生成される。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
同様に、図３においてデコーダは、エンコーダから符号化されたビットストリームを受信し、第１のエントロピーデコーダ２００であり、異なる部分のデータが取得される。データの１つの部分は、幾何学的パターン２３２を取得するためにエッジブレーカーデコーダ２０１に入力される。データの他の部分は、幾何学的パターンのクラスタの表現を含み、ｋｄ木ベースのデコーダ２０２に入力され、おのおのの結合された要素の平均（すなわち中央）２３４を提供する。エントロピーデコーダ２００はまた、方向軸情報２４４及び倍率情報２４６を出力する。ｋｄ木ベースのデコーダ２０２は平均２３４を計算し、他の要素の情報（パターンＩＤ２３６、方向軸２３８及び倍率２４０）と共に回復ブロック２４２に配信される。回復ブロック２４２は、反復要素を正規化された結合された要素を復元するための第１のブロック２０３、結合された要素（反復しない結合された要素を含む）を復元するための第２のブロック２０４、及び結合された要素を組み立てるための第３のブロックにおいて回復する。一実施形態において、デコーダは、そのインスタンスを復元する前に、おのおのの反復パターンの平均を計算する。さらなるブロック（図３において図示しない）において、結合された要素から完全な要素が組み立てられる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
このような方法において、３Ｄメッシュ画像を、鏡像対称の性質により、画像から効果的にコスト効率よく生成できる。これは、パターンの鏡映の組を伴う複雑な画像を、回転および移動を使用して符号化及び復号化することを可能にし、周知のパラメータの組に対する符号化及び復号化の問題を大きく減少させる。このような結果は本技術分野において従来達成されていなかった。
本発明の好ましい実施形態を以下に示す。
付記１．３Ｄ画像を復号化する方法であって、
画像の３Ｄ要素を含む受信されたビットストリームの要素を復号化して、前記３Ｄ画像のパターンの組を取得するステップと、
前記要素を、パターンの移動、回転及び鏡映情報に分解するステップと、
パラメータを検査して前記パターンが前記要素に一致するか否かを判定するステップと、
前記要素及び前記パターンの組を前記パターンの復号化された回転マトリックスと共に使用して前記画像を再構成するステップと、
を含む、前記方法。
付記２．前記パターンが前記要素に一致しないように前記パラメータが設定されている場合に、前記パターンの鏡映を使用して、前記３Ｄモデルを再構成するステップをさらに含み、前記分解するステップは、前記画像のパターン内の複数の鏡映された点を生成し、一致した要素を特徴付けるステップをさらに含む、付記１に記載の方法。
付記３．前記パターンが前記要素に一致する場合、又は前記鏡映が前記要素に一致する場合、回転マトリックスを導出するステップをさらに含む、付記２に記載の方法。
付記４．前記復号化するステップは前記要素のエントロピー復号化を行うステップを含む、付記３に記載の方法。
付記５．すべての要素が一致するまで、さらなるパターンマッチングのための要素をインクリメントするステップをさらに含む、付記４に記載の方法。
付記６．前記鏡映情報は、鏡映フラグを含む、付記５に記載の方法。
付記７．前記鏡映フラグを検査して、前記パターンが前記要素に一致するか、又は前記パターンの鏡映が前記要素に一致するかを判定するステップをさらに含む、付記６に記載の方法。
付記８．３Ｄ画像を復号化するデコーダであって、前記３Ｄ画像内のパターンの鏡映を一致させることにより前記３Ｄ画像の要素を分析し、及び前記３Ｄ画像をさらにレンダリングするために前記要素を復元する回路を含む、前記デコーダ。
付記９．前記回路は、一致した前記要素を移動、変換、スケーリング及び鏡映要素に分解する回路をさらに含む、付記８に記載のデコーダ。
付記１０．前記回路は、前記パターンが前記要素に一致するか、又は前記パターンの前記鏡映が前記要素に一致するかを判定する回路をさらに含む、付記９に記載のデコーダ。
付記１１．前記分解する回路は、回転マトリックスを分解して、変換、回転、スケーリング及び対称要素を取得する回路をさらに含む、付記１０に記載のデコーダ。
付記１２．前記対象要素は、鏡映フラグを含む、付記１１に記載のデコーダ。
付記１３．３Ｄ画像を符号化する方法であって、
前記３Ｄ画像を符号化して、前記３Ｄ画像の要素を表す少なくとも一つのパターンを取得するステップと、
前記３Ｄ画像のおのおのの要素に対して、前記要素を前記パターンと比較して前記要素が前記パターンに一致するか否かを判定するステップと、
前記要素が前記パターンと一致する場合、符号化された表示される要素を取得するために前記要素に関係するパラメータを符号化するステップと、
鏡映フラグを、前記パターンが前記要素に一致することを示す値に設定するステップと、
を含む、前記方法。
付記１４．前記パラメータを符号化するステップは、変換マトリックスを生成して、前記パターンに関連する移動、回転及び倍率を取得することを含む、付記１３に記載の方法。
付記１５．前記パターンが前記要素に一致する場合、前記鏡映フラグを０に設定するステップをさらに含む、付記１４に記載の方法。
付記１６．前記パターンの前記鏡映が前記要素に一致する場合、前記鏡映フラグを１に設定するステップをさらに含む、付記１５に記載の方法。
付記１７．前記符号化するステップは、前記３Ｄ画像のエントロピー符号化を行うことを含む、付記１６に記載の方法。
付記１８．３Ｄ画像を符号化するエンコーダであって、
前記３Ｄ画像の要素を表す少なくとも一つのパターンを取得するエントロピーエンコーダと、
前記要素を前記パターンと比較し、前記要素が前記パターンに一致するか否かを判定する回路と、
前記要素に関連するパラメータを符号化する回路であって、符号化された表される要素を取得し、鏡映フラグを前記パターンが前記要素に一致することを示す値に設定する、前記回路と、
を含む、前記エンコーダ。
付記１９．パラメータを符号化する前記回路は、変換マトリックスを生成して、前記パターンに関連する移動、回転及び倍率を取得する回路をさらに含む、付記１８に記載のエンコーダ。
付記２０．前記パターンが前記要素に一致する場合、前記鏡映フラグを０に設定し、前記パターンの鏡映が前記要素に一致する場合、前記鏡映フラグを１に設定する回路をさらに含む、付記１９に記載のエンコーダ。
【国際調査報告】
2015504559.tif 000026
2015504559.tif 000027