(57)【要約】本発明は、接続されるコンポーネントの少なくとも１つの方位ベクトルの符号化及び復号化の分野においてなされる。符号化のためにベクトル成分を量子化する場合に、符号化されるベクトル成分の許容可能な量子化偏差は時々、計算されるベクトル成分の許容不可能な偏差をもたらす。従って、ベクトルの第１及び第２の成分を量子化及び逆量子化し、量子化をされた第１及び第２の成分並びにベクトルの第３の成分の符号をシグナリングするビットを符号化するステップと、ベクトルの所定の長さ並びに逆量子化をされた第１及び第２の成分を用いて、第３の成分の近似の計算される絶対値が第１の閾値よりも小さいかどうかを決定するステップと、計算される絶対値が第１の閾値よりも小さい場合は、第３の成分の計算される絶対値と第３の成分の絶対値との間の剰余を決定し、量子化及び符号化するステップとを有する方法が提案される。
2014527736.tif 000002
【特許請求の範囲】
【請求項１】
接続されるコンポーネントの方位ベクトルを符号化する方法であって、該ベクトルが所定の長さを有し且つ３つの成分を含む方法において、
前記ベクトルの第１及び第２の成分を量子化及び逆量子化し、該量子化をされた第１及び第２の成分と、前記ベクトルの第３の成分の符号をシグナリングするビットとを符号化するステップと、
前記所定の長さと、前記逆量子化をされた第１及び第２の成分とを用いて、前記ベクトルの前記第３の成分の近似の計算される絶対値が第１の閾値よりも小さいかどうかを決定するステップと、
前記計算される絶対値が前記第１の閾値よりも小さい場合は、前記第３の成分の前記計算される絶対値と前記第３の成分の絶対値との間の剰余を決定し、量子化及び符号化するステップと
を有する方法。
【請求項２】
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な前記接続されるコンポーネントの更なる方位ベクトルを、
請求項１に従って符号化されたデータを用いて、再構成される第３の成分を決定し、
前記再構成される第３の成分が第２の閾値よりも小さいことを決定し、
前記逆量子化をされた第１及び第２の成分の絶対値を比較し、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きい場合は、前記更なる成分の中の第１の更なる成分の符号をシグナリングするビットが符号化され、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きくない場合は、前記更なる成分の中の第２の更なる成分の符号をシグナリングするビットが符号化され、
第３の更なる成分を量子化及び符号化する
ことによって、符号化するステップ
を更に有する請求項１に記載の方法。
【請求項３】
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な更なるベクトルを、
請求項１に従って符号化されたデータを用いて、再構成される第３の成分を決定し、
前記再構成される第３の成分が、前記第１の閾値よりも小さい第２の閾値よりも小さくないことを決定し、
前記逆量子化をされた第１及び第２の成分の絶対値を用いて、前記更なる成分の中の第１及び第２の更なる成分のうち選択された１つを量子化及び逆量子化し、
前記ベクトルの再構成と、前記所定の長さと、前記逆量子化をされた、第１及び第２の更なる成分のうち選択された１つとを用いて、前記更なる成分の中の前記第１及び第２の更なる成分のうち選択されていない１つの２つのとり得る値を計算し、
前記計算をされた２つのとり得る値のどちらが前記選択されてない更なる成分により良く近似するかに依存してフラグを設定し、
前記量子化をされた選択された更なる成分及び前記フラグを符号化する
ことによって、符号化するステップ
を更に有する請求項１に記載の方法。
【請求項４】
前記所定の長さと、前記フラグと、前記逆量子化をされた選択された更なる成分とを用いて、前記更なるベクトルの中の第３の更なる成分の近似の計算される更なる絶対値が前記第１の閾値よりも小さいかどうかを決定するステップと、
前記計算される更なる絶対値が前記第１の閾値よりも小さい場合は、前記計算される更なる絶対値と前記更なるベクトルの前記第３の更なる成分の絶対値との間の更なる剰余を決定し、量子化及び符号化するステップと
を更に有する請求項３に記載の方法。
【請求項５】
非一時的な記憶媒体において符号化された全てのデータを記憶するステップ
を更に有する請求項１乃至４のうちいずれか一項に記載の方法。
【請求項６】
請求項５に記載の方法に従って記憶されたデータを担持する記憶媒体。
【請求項７】
接続されるコンポーネントの方位ベクトルを再構成する方法であって、該ベクトルが所定の長さを有し且つ３つの成分を含む方法において、
前記ベクトルの第３の成分の符号をシグナリングするビットと、前記ベクトルの第１及び第２の成分とを復号し且つ前記第１及び第２の成分を逆量子化するステップと、
前記所定の長さと、前記逆量子化をされた第１及び第２の成分とを用いて、前記ベクトルの前記第３の成分の近似の計算される絶対値が第１の閾値よりも小さいかどうかを決定するステップと、
前記計算される絶対値が前記第１の閾値よりも小さい場合は、前記第３の成分の前記計算される絶対値と前記第３の成分の絶対値との間の剰余を決定し、復号及び逆量子化するステップと、
前記復号されたデータを用いて、前記ベクトルの前記第３の成分を再構成するステップと
を有する方法。
【請求項８】
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な前記接続されるコンポーネントの更なる方位ベクトルを、
前記再構成をされた第３の成分が前記第１の閾値よりも小さい第２の閾値よりも小さいことを決定し、
前記逆量子化をされた第１及び第２の成分の絶対値を比較し、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きい場合は、前記更なる成分の中の第１の更なる成分の符号をシグナリングするビットが符号化され、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きくない場合は、前記更なる成分の中の第２の更なる成分の符号をシグナリングするビットが符号化され、
前記更なるベクトルの第３の更なる成分を復号及び逆量子化する
ことによって、再構成するステップ
を更に有する請求項７に記載の方法。
【請求項９】
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な前記接続されるコンポーネントの更なる方位ベクトルを、
前記再構成をされた第３の成分が、第２の閾値よりも小さくないことを決定し、
フラグと前記更なる成分の中の１つとを復号し、前記更なる成分の中の１つを逆量子化するステップと、
前記逆量子化をされた第１及び第２の成分の絶対値を用いて、前記更なる成分の中の前記１つが前記更なるベクトルの第１又は第２の更なる成分のいずれであるか決定し、
前記ベクトルの再構成と、前記所定の長さと、前記フラグと、前記更なる成分の中の前記逆量子化をされた１つとを用いて、前記更なる成分の中の前記１つがそうではないと決定される前記更なるベクトルの別の更なる成分を計算し、
前記所定の長さと、前記逆量子化をされた１つの更なる成分と、前記計算をされた別の更なる成分とを用いて、第３の更なる成分の近似を決定する
ことによって、再構成するステップ
を更に有する請求項７に記載の方法。
【請求項１０】
前記第３の更なる成分の前記決定された近似の絶対値が前記第１の閾値よりも小さいことを決定するステップと、
更なる剰余を復号及び逆量子化するステップと、
前記逆量子化をされた更なる剰余を用いて前記決定された近似を更新するステップと
を更に有する請求項９に記載の方法。
【請求項１１】
請求項１乃至５のうちいずれか一項に記載の方法又は請求項７乃至１０のうちいずれか一項に記載の方法を実行するプロセッサを有する装置。
【請求項１２】
接続されるコンポーネントに関連する方位ベクトルを決定する反復構造発見モジュールと、前記方位ベクトルを符号化するよう請求項１乃至５のうちいずれか一項に記載の方法を実行するエンコーダとを有し、
前記接続されるコンポーネントは、パターンのインスタンスに対応し、
前記パターンは、３Ｄモデルにおいて起こる反復構造に対応する、
装置。
【請求項１３】
請求項７乃至１０のうちいずれか一項に記載の方法に従って符号化された方位ベクトルを復号するデコーダと、前記接続されるコンポーネントを含む３Ｄモデルを生成するモデル再構成モジュールとを有し、
前記接続されるコンポーネントは、パターンのインスタンスに対応し、
前記パターンは、前記３Ｄモデルにおいて起こる反復構造に対応する、
装置。
【請求項１４】
前記接続されるコンポーネントは、パターンのインスタンスに対応し、
前記パターンは、３Ｄモデルにおいて起こる反復構造に対応し、
当該方法は、前記接続されるコンポーネントに関連する前記方位ベクトルを決定するステップを更に有する、
請求項１乃至５のうちいずれか一項に記載の方法。
【請求項１５】
前記接続されるコンポーネントは、パターンのインスタンスに対応し、
前記パターンは、３Ｄモデルにおいて起こる反復構造に対応し、
当該方法は、前記接続されるコンポーネントを含む前記３Ｄモデルを生成するステップを更に有する、
請求項７乃至１０のうちいずれか一項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトルの成分の符号化の分野においてなされる。特に、本発明は、所定の長さを有し且つ３つの成分を含む、接続されるコンポーネントの方位ベクトルの符号化に関する。
【背景技術】
【０００２】
接続されるコンポーネントの方位ベクトルは、コンポーネントのインスタンスへの該コンポーネントのテンプレートの回転変換に役立ち、オーディオビジュアルコンテンツの処理において多種多様な方法で使用される。例えば、聴覚に関連するオブジェクトをモデリングする場合に、オブジェクトは音源に相当してよい。視覚に関連するオブジェクトをモデリングする場合に、オブジェクトは剛体に相当してよい。
【０００３】
特に、例えば、２〜３例を挙げると、ＣＡＤシステム、三次元（３Ｄ）ゲーム、３Ｄテレビ、又は３Ｄ映画において使用される３Ｄにおいて、視覚に関連するオブジェクトをモデリングする場合に、しばしば反復構造が見られる。そのような反復構造は、例えば、複数回起こるオブジェクト又はオブジェクト部分であり、一度構造のテンプレートを符号化して、構造のインスタンスごとに、当該インスタンスへのテンプレートの変換を可能にするデータを符号化することによって、圧縮符号化され得る。テンプレートはパターンとも呼ばれ、クラスタリングにより得られる。
【０００４】
最も一般的に言えば、そのような変換は、回転、スケーリング、剪断、及び／又は移動に分けることができるアフィン変換である。回転、スケーリング、剪断は、交換可能である線形変換である。すなわち、それらの適用の順序は全体の変換結果に影響を及ぼさず、線形変換のそれぞれを可能にするデータは独立に符号化され得る。
【０００５】
線形変換の中で、三次元空間における回転は、３つの異なる軸の周りの回転に更に分けることができる。すなわち、３Ｄにおける回転の回転データは、一般的に、３自由度を有する。
【０００６】
すなわち、アフィン変換の回転変換部分は、互いに直行する正規化された方位ベクトルの対を特定するパラメータによって表され得る。垂直制約及び正規化制約により、この方位ベクトルの対は３自由度を有する。すなわち、３つのパラメータは、他のパラメータが符号化されたパラメータ及びそれらの制約を用いて計算され得るので、２つのベクトルの確かな決定を可能にするために決定される必要がある。
【０００７】
回転のうちの特定の１つが零又はπ（１８０度に対応）である所謂ジンバルロックの場合に、歳差回転（precession  rotation）及び固有回転（intrinsic  rotation）が同じ軸の周りに、すなわち同じ面において、起こる。歳差回転及び固有回転は相互的であり、累積回転によって表され得る。よって、そのような場合に、自由度は失われ、回転は２つのパラメータによって一意的に特定される。
【０００８】
M.  Deering：“Geometry  Compression”、Proceeding  of  ACM  SIGGRAPH、１９９５年、pp.13-20（非特許文献１）は、法線ベクトルの符号化に関し、単位法線の終点が位置し且つ８つの八分円に分けられる法線球面であって、各八分円が６つの六分円に更に分けられる法線球面を提案している。
【０００９】
接続されるコンポーネントの方位軸が幾つかの主方位を有する場合について、Deok-Soo  Kim、Youngsong  Cho及びHyun  Kim：“Normal  Compression  Based  on  Clustering  and  Relative  Indexing”、Pacific  Conference  on  Computer  Graphics  and  Applications  IEEE、２００２年（非特許文献２）は、固定数のクラスタによるｋ平均法クラスタリングに基づくアプローチを提案している。
【００１０】
圧縮のために繰り返しパターンを利用することへの他の取り組みは、Kangying  Cai、Wencheng  Wang、Zhibo  Chen、Quqing  Chen、Jun  Teng：“Exploiting  repeated  patterns  for  efficient  compression  of  massive  models”、Proceeding  of  the  8th  International  Conference  on  Virtual  Reality  Continuum  and  its  Applications  in  Industry(VRCAI  2009)：145-150、２００９年（非特許文献３）において記載されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】M.  Deering：“Geometry  Compression”、Proceeding  of  ACM  SIGGRAPH、１９９５年、pp.13-20
【非特許文献２】Deok-Soo  Kim、Youngsong  Cho及びHyun  Kim：“Normal  Compression  Based  on  Clustering  and  Relative  Indexing”、Pacific  Conference  on  Computer  Graphics  and  Applications  IEEE、２００２年
【非特許文献３】Kangying  Cai、Wencheng  Wang、Zhibo  Chen、Quqing  Chen、Jun  Teng：“Exploiting  repeated  patterns  for  efficient  compression  of  massive  models”、Proceeding  of  the  8th  International  Conference  on  Virtual  Reality  Continuum  and  its  Applications  in  Industry(VRCAI  2009)：145-150、２００９年
【発明の概要】
【発明が解決しようとする課題】
【００１２】
符号化のためにベクトル成分を量子化する場合に、発明者は、符号化される成分の量子化によって導入される許容可能な偏差が時々、計算される成分の許容不可能な偏差をもたらすことに気づいた。発明者は、これが、零に近い除数の場合に該除数に存在する誤差の許容不可能な伝播をもたらす計算において含まれる除算ステップに起因すると分かった。
【課題を解決するための手段】
【００１３】
従って、請求項１に係る方法は、所定の長さを有し且つ３つの成分を含む、接続されるコンポーネントの方位ベクトルを符号化するために提案される。
【００１４】
本発明に従う方法は有利に、３Ｄモデルにおいて起こる繰り返しパターンのインスタンスに対応する接続されるコンポーネントの符号化／復号化において使用される。
【００１５】
当該方法は、
前記ベクトルの第１及び第２の成分を量子化及び逆量子化し、該量子化をされた第１及び第２の成分と、前記ベクトルの第３の成分の符号をシグナリングするビットとを符号化するステップと、
前記所定の長さと、前記逆量子化をされた第１及び第２の成分とを用いて、前記ベクトルの前記第３の成分の近似の計算される絶対値が第１の閾値よりも小さいかどうかを決定するステップと、
前記計算される絶対値が前記第１の閾値よりも小さい場合は、前記第３の成分の前記計算される絶対値と前記第３の成分の絶対値との間の剰余を決定し、量子化及び符号化するステップ
とを有する。
【００１６】
実施例において、当該方法は、
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な前記接続されるコンポーネントの更なる方位ベクトルを、
請求項１に従って符号化されたデータを用いて、再構成される第３の成分を決定し、
前記再構成される第３の成分が第２の閾値よりも小さいことを決定し、
前記逆量子化をされた第１及び第２の成分の絶対値を比較し、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きい場合は、前記更なる成分の中の第１の更なる成分の符号をシグナリングするビットが符号化され、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きくない場合は、前記更なる成分の中の第２の更なる成分の符号をシグナリングするビットが符号化され、
第３の更なる成分を量子化及び符号化する
ことによって、符号化するステップ
を更に有する。
【００１７】
異なる実施例において、当該方法は、
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な更なるベクトルを、
請求項１に従って符号化されたデータを用いて、再構成される第３の成分を決定し、
前記再構成される第３の成分が、前記第１の閾値よりも小さい第２の閾値よりも小さくないことを決定し、
前記逆量子化をされた第１及び第２の成分の絶対値を用いて、前記更なる成分の中の第１及び第２の更なる成分のうち選択された１つを量子化及び逆量子化し、
前記ベクトルの再構成と、前記所定の長さと、前記逆量子化をされた、第１及び第２の更なる成分のうち選択された１つとを用いて、前記更なる成分の中の前記第１及び第２の更なる成分のうち選択されていない１つの２つのとり得る値を計算し、
前記計算をされた２つのとり得る値のどちらが前記選択されてない更なる成分により良く近似するかに依存してフラグを設定し、
前記量子化をされた選択された更なる成分及び前記フラグを符号化する
ことによって、符号化するステップ
を更に有する。
【００１８】
前述の異なる実施例において、当該方法は、
前記所定の長さと、前記フラグと、前記逆量子化をされた選択された更なる成分とを用いて、前記更なるベクトルの中の第３の更なる成分の近似の計算される更なる絶対値が前記第１の閾値よりも小さいかどうかを決定するステップと、
前記計算される更なる絶対値が前記第１の閾値よりも小さい場合は、前記計算される更なる絶対値と前記更なるベクトルの前記第３の更なる成分の絶対値との間の更なる剰余を決定し、量子化及び符号化するステップと
を更に有する。
【００１９】
当該方法は、非一時的な記憶媒体において符号化された全てのデータを記憶するステップを有することができるが必ずしも必要ではない。
【００２０】
更に、提案される方法又は該方法の実施例の１つに従って記憶されたデータを担持する記憶媒体が提案される。
【００２１】
そして、所定の長さを有し且つ３つの成分を含む、接続されるコンポーネントの方位ベクトルを再構成する請求項７に係る方法が提案される。
【００２２】
当該再構成方法は、
前記ベクトルの第３の成分の符号をシグナリングするビットと、前記ベクトルの第１及び第２の成分とを復号し且つ前記第１及び第２の成分を逆量子化するステップと、
前記所定の長さと、前記逆量子化をされた第１及び第２の成分とを用いて、前記ベクトルの前記第３の成分の近似の計算される絶対値が第１の閾値よりも小さいかどうかを決定するステップと、
前記計算される絶対値が前記第１の閾値よりも小さい場合は、前記第３の成分の前記計算される絶対値と前記第３の成分の絶対値との間の剰余を決定し、復号及び逆量子化するステップと、
前記復号されたデータを用いて、前記ベクトルの前記第３の成分を再構成するステップと
を有する。
【００２３】
実施例において、当該再構成方法は、
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な前記接続されるコンポーネントの更なる方位ベクトルを、
前記再構成をされた第３の成分が前記第１の閾値よりも小さい第２の閾値よりも小さいことを決定し、
前記逆量子化をされた第１及び第２の成分の絶対値を比較し、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きい場合は、前記更なる成分の中の第１の更なる成分の符号をシグナリングするビットが符号化され、
前記逆量子化をされた第１の成分の絶対値が前記逆量子化をされた第２の成分の絶対値よりも大きくない場合は、前記更なる成分の中の第２の更なる成分の符号をシグナリングするビットが符号化され、
前記更なるベクトルの第３の更なる成分を復号及び逆量子化する
ことによって、再構成するステップ
を更に有する。
【００２４】
異なる実施例において、当該再構成方法は、
前記所定の長さを有し且つ３つの更なる成分を含む、前記ベクトルに垂直な前記接続されるコンポーネントの更なる方位ベクトルを、
前記再構成をされた第３の成分が、第２の閾値よりも小さくないことを決定し、
フラグと前記更なる成分の中の１つとを復号し、前記更なる成分の中の１つを逆量子化するステップと、
前記逆量子化をされた第１及び第２の成分の絶対値を用いて、前記更なる成分の中の前記１つが前記更なるベクトルの第１又は第２の更なる成分のいずれであるか決定し、
前記ベクトルの再構成と、前記所定の長さと、前記フラグと、前記更なる成分の中の前記逆量子化をされた１つとを用いて、前記更なる成分の中の前記１つがそうではないと決定される前記更なるベクトルの別の更なる成分を計算し、
前記所定の長さと、前記逆量子化をされた１つの更なる成分と、前記計算をされた別の更なる成分とを用いて、第３の更なる成分の近似を決定する
ことによって、再構成するステップ
を更に有する。
【００２５】
前述の異なる実施例において、当該再構成方法は、
前記第３の更なる成分の前記決定された近似の絶対値が前記第１の閾値よりも小さいことを決定するステップと、
更なる剰余を復号及び逆量子化するステップと、
前記逆量子化をされた更なる剰余を用いて前記決定された近似を更新するステップと
を更に有することができる。
【００２６】
更に、提案される方法の１つを実行するプロセッサを有する装置が提案される。更に、本発明は、３Ｄモデルにおける繰り返しパターンのインスタンスに対応する接続されるコンポーネントの方位ベクトルを符号化／復号化するエンコーダ又はデコーダを有する装置を提供する。
【００２７】
更なる有利な実施形態の特徴は、従属請求項において特定される。
【図面の簡単な説明】
【００２８】
【図１】符号化方法の実施形態のフローチャートを例示する。
【図２】復号化方法の実施形態のフローチャートを例示する。
【図３】本原理に従う３Ｄモデルのエンコーダの例を示す。
【図４】本原理に従う３Ｄモデルのデコーダの例を示す。
【発明を実施するための形態】
【００２９】
本発明の例となる実施形態は、図面において表され、以下の記載においてより詳細に説明される。例となる実施形態は、特許請求の範囲において定義される本発明の開示又は適用範囲を制限するためではなく、本発明を明らかにするためにのみ説明される。
【００３０】
本発明は、相応に適合された処理装置を有する如何なる電子機器においても実現されてよい。本発明が実現され得る例となる装置の非包括的なリストには、テレビ受像器、携帯電話機、パーソナルコンピュータ、デジタル静止カメラ、デジタルビデオカメラ、ＭＰ３プレーヤ、ナビゲーションシステム又はカーオーディオシステムが含まれる。
【００３１】
本発明は、符号化されるベクトルが使用される如何なる目的からも独立して所定の長さのベクトルを符号化するために使用され得る。
【００３２】
以下で記載される例となる実施形態は、符号化されたベクトルが方位ベクトルである視覚的オブジェクトのモデリングに関するが、これに制限されない。
【００３３】
表１において、ビットストリームフォーマットの例が提示される。これにより、本発明の実施形態に従って符号化される垂直な正規化ベクトルの対が与えられ得る：
【００３４】
【表１】
2014527736.tif 000003
デカルトモードにおけるｉ番目のインスタンスの方位は、２つの直交する軸（x0，y0，z0）及び（x1，y1，z1）によって表される。
【００３５】
compr_ith_insta_orient_x0：ｉ番目のインスタンスの方位の圧縮されたx0を有する。
【００３６】
compr_ith_insta_orient_y0：ｉ番目のインスタンスの方位の圧縮されたy0を有する。
【００３７】
compr_ith_insta_orient_z0_sgn：x0及びy0を用いてz0を計算するために必要とされるz0の符号を示す１ビットの符号なし整数。“−”については０且つ“＋”については１。
【００３８】
compr_ith_insta_orient_z0_res：（z0−compute_z0()）によって計算されるz0の圧縮された剰余を有する。
【００３９】
compr_ith_insta_orient_z1：ｉ番目のインスタンスの方位の圧縮されたz1を有する。
【００４０】
ith_insta_orient_x1_sgn：x0及びy0を用いてx1を計算するために必要とされるx1の符号を示す１ビットの符号なし整数。“−”については０且つ“＋”については１。
【００４１】
ith_insta_orient_y1_sgn：x0及びy0を用いてy1を計算するために必要とされるy1の符号を示す１ビットの符号なし整数。“−”については０且つ“＋”については１。
【００４２】
compr_ith_insta_orient_x1：ｉ番目のインスタンスの方位の圧縮されたx1を有する。
【００４３】
compr_ith_insta_orient_y1：ｉ番目のインスタンスの方位の圧縮されたy1を有する。
【００４４】
ith_insta_orient_delta_sgn：x0、y0、z0及びy1又はx1を用いてx1又はy1を計算するために必要とされる符号を示す１ビットの符号なし整数。“−”については０且つ“＋”については１。
【００４５】
compr_ith_insta_orient_z1_res：（z1−compute_z1()）によって計算されるz1の圧縮された剰余を有する。
【００４６】
threshold：圧縮分野において広く受け入れられている閾値。
【００４７】
compute_z0()：x0、y0、及びz0の符号を用いてｉ番目のインスタンスのz0を計算する。
【００４８】
bit_num_orient_cartesian()：ＱＰに基づきデカルト座標系において各方位値ごとにビットの数を計算する。
【００４９】
bit_num_orient_res_cartesian()：ＱＰに基づきデカルト座標系において各方位剰余値ごとにビットの数を計算する。
【００５０】
compute_z1()：x0、y0、z0、x1及びy1を用いてｉ番目のインスタンスのz1を計算する。
【００５１】
表２において、ビットストリームフォーマットの他の例が与えられる：
【００５２】
【表２】
2014527736.tif 000004
球形モードにおけるｉ番目のインスタンスの方位は、３つの角度アルファ、ベータ及びガンマによって表される。
【００５３】
compr_ith_insta_orient_alpha：ｉ番目のインスタンスの方位の圧縮されたアルファを有する。
【００５４】
compr_ith_insta_orient_beta：ｉ番目のインスタンスの方位の圧縮されたベータを有する。
【００５５】
compr_ith_insta_orient_gamma：ｉ番目のインスタンスの方位の圧縮されたガンマを有する。
【００５６】
compr_ith_insta_orient_res：ｉ番目のインスタンスの方位のデカルト座標系における圧縮された剰余を有する。
【００５７】
bit_num_orient_alpha()：ＱＰに基づき各アルファ値ごとにビットの数を計算する。
【００５８】
bit_num_orient_beta()：ＱＰに基づき各ベータ値ごとにビットの数を計算する。
【００５９】
bit_num_orient_gamma()：ＱＰに基づき各ガンマ値ごとにビットの数を計算する。
【００６０】
need_correction()：方位を確認し、大きな誤差を生じさせるかもしれない周辺条件にある場合は真（true）を返し、そうでない場合は偽（false）を返す。
【００６１】
正規化ベクトルの符号化の必要性が起こる例は、３Ｄ接続コンポーネントの方位の表現である。通常、方向は、デカルト座標又は球座標のいずれかにおいて、接続されるコンポーネントの方位軸のうち２つについて符号化される。３Ｄ接続コンポーネントの３つの方位軸は互いに直交するので、第３の軸は、最初の２つの軸の外積を計算することによって求められ得る。
【００６２】
３つの軸をd0（x0，y0，z0）、d1（x1，y1，z1）及びd2（x2，y2，z2）によって表すとすれば、d0・d1＝0且つd2＝d0×d1が得られる。その場合に、方位軸の符号化方法は：
１）x0及びy0を計算するステップと、
２）z0の符号を符号化するステップと、
３）x1を圧縮するステップと
を有してよい。
【００６３】
次いで、y1、z0及びz1が：
z0＝sqrt（1−x02−y02）、
z1＝sqrt（1−x12−y12）、及び
0＝x0×x1＋y0×y1＋z0×z1
を用いて計算され得る。
【００６４】
方位軸d2は、d2＝d0×d1を用いて決定可能である。
【００６５】
しかし、x0、y0およびx1のfloat値は符号化の前に量子化されるので、偏差が導入され、これは、計算における誤差伝播により、計算された成分においてなおさら大きい誤差をもたらす。
【００６６】
例えば、１２ビット量子化により次の方位：
d0（-0.984644，-0.174418，-0.00737644）及び
d1（-0.121407，0.714518，-0.689003）
を圧縮した後、再構成により
d0（-0.984462，-0.174202，-0.0220894）及び
d1（-0.121595，0.767049，-0.629961）
が得られる。
【００６７】
x0、y0及びx1の量子化誤差は許容可能であり、すなわち、0.000182、0.000216及び0.000188。しかし、計算される値z0、y1及びz1の誤差は0.01471296、0.052531及び0.059042であり、これは全体として受け入れられない。
【００６８】
上記の主な原因は、z0の計算誤差である。1−x02−y02が小さく、従ってz0が小さい場合は、x又はyにおける極小さな誤差は、z0が1−x02−y02の平方根であるために、z0のより大きな誤差になる。従って、本発明は、z0が小さい場合、すなわち、その絶対値が第１の閾値を下回る場合において、補正を更に符号化することを提案する。
【００６９】
更に、z1を再構成することは、z0による除算を含む。この除算はまた、z0が零に近い場合において許容不可能な誤差伝播をもたらす。同様に、x1が符号化される場合において、y1を再構成することは、（1−x02）による除算を含む。代替的に、y1が符号化される場合において、x1は、（1−y02）による除算を用いて再構成され得る。
【００７０】
本発明の圧縮方法は、ベクトルの再構成が最大偏差を超えて当該ベクトルから外れないようにすることを確かにする。
【００７１】
先に述べたように、方位表現における幾つかの値は、符号化されるよりむしろ計算され得る。あいにく、これは、計算のために用いられる符号化される値自体が量子化により不正確であるために、許容不可能な誤差を生じさせることがある。本発明はこの問題に対処し、相当に小さいそれらの計算された値についての剰余データを符号化することを有する、計算誤差を最小限とする圧縮方法を提案する。
【００７２】
直交するベクトルの対が符号化される実施例において、本発明の符号化方法は、前記ベクトルの対の一方のベクトルの第１及び第２の量子化されたfloat成分と、前記ベクトルの対の他方のベクトルの第１又は第２のいずれか一方の量子化されたfloat成分とを符号化することを有する。この実施例において、２つの符号ビット又はフラグビット、すなわち、２つの単一ビットが、３Ｄコンポーネントの方位を表すよう更に符号化される。再構成誤差を最小限とするよう、この実施例の符号化スキームは、次の点に基づき設計される：
１．計算における分母を可能な限り大きくする。
２．分母が極めて小さいか又は零である場合は特別の処理を行う。
３．許容不可能な誤差を生じさせるかもしれない場合を自動的に特定し、そのような場合に剰余データを送信する。
【００７３】
図１は、前述の実施例に従う符号化プロセスを例示する。
【００７４】
前記一方のベクトルの第１の成分x0は常に量子化及び符号化される。少なくとも、第1の量子化されたベクトル成分の逆量子化値x0rが１に等しくない限り、符号ビットが更に符号化される。符号ビットは、前記一方のベクトルの第３の成分z0の符号をシグナリングする。前記一方のベクトルの第２の成分y0が更に量子化及び符号化される。
【００７５】
z0微分モジュールは、前記一方のベクトルの所定の長さと、符号化されたデータの再構成とを用いて、前記一方のベクトルの第３の成分の近似z0aを計算する。すなわち、少なくとも、第１の量子化されたベクトル成分の逆量子化値x0rの絶対値が１に等しくない限り、符号ビット並びに第１及び第２の量子化されたベクトル成分の逆量子化値x0r、y0rはz0aを決定するために使用される。第１の量子化されたベクトル成分の逆量子化値x0rの絶対値が１に等しい場合は、z0aは零と決定され得る。
【００７６】
誤差補正モジュールは、z0aについて計算された値が極めて小さい、すなわち、第１の閾値よりも小さく、よって不正確である可能性が高い場合に、有効にされる。そのような場合に、エンコーダは更に、原値と近似z0aとの間の量子化された剰余を符号化する。すなわち、z0の再構成z0rは、z0aに等しいか、又は逆量子化された剰余の分だけz0aと相違する。
【００７７】
前記他方のベクトルの第１のベクトルが符号化される場合に、y1微分モジュールは、前記一方のベクトルの逆量子化された第１及び第２の量子化されたfloat成分値x0r、y0rと、前記他方のベクトルの逆量子化された第１の量子化されたfloat成分値x1rとを用いて、前記他方のベクトルの第２の成分について２つのとり得る解を計算する。すなわち：
y1r＝（x0r×y0r×x1r＋√Δ）／（1−x0r2）又は
y1r＝（x0r×y0r×x1r−√Δ）／（1−x0r2）。
【００７８】
これらの式において、Δはz0r2×（1−x0r2−y0r2）に等しく、このときz0rは、場合により剰余により補正された再構成である。
【００７９】
同様に、前記他方のベクトルの第２の成分が符号化される場合に、x1微分モジュールは、前記一方のベクトルの逆量子化された第１及び第２の量子化されたfloat成分値x0r、y0rと、前記他方のベクトルの逆量子化された第２の量子化されたfloat成分値y1rとを用いて、前記他方のベクトルの第１の成分について２つのとり得る解を計算する。すなわち：
x1r＝（x0r×y0r×y1r＋√Δ）／（1−y0r2）又は
x1r＝（x0r×y0r×y1r−√Δ）／（1−y0r2）。
【００８０】
これらの式において、Δはz0r2×（1−x0r2−y0r2）に等しく、このときz0rは、場合により剰余により補正された再構成である。
【００８１】
z0rの絶対値が極めて小さい、すなわち、第１の閾値よりも更に小さい第２の閾値よりも小さい場合に、x1微分モジュールもy1微分モジュールも作動しない。代わり、z1が量子化及び符号化される。加えて、更なる符号ビットが符号化される。この更なる符号ビットは、より小さい絶対値を有する前記他方のベクトルの再構成された第１及び第２の成分のその１つの符号を示す。
【００８２】
z0rの絶対値が第２の閾値よりも小さくない場合においてx1微分モジュール又はy1微分モジュールのいずれが作動するかどうかは、前記一方のベクトルの再構成された第１及び第２の成分x0r及びy0rの絶対値の関係に依存する。abs（x0r）＞abs（y0r）の場合には、x1が量子化及び符号化され、y1微分モジュールが作動される。abs（x0r）＜abs（y0r）の場合には、y1が量子化及び符号化され、x1微分モジュールが作動される。x1微分モジュール及びy1微分モジュールのそれぞれが２つのとり得る解を提供するので、フラグビットが更に、使用される解をデコーダに示すよう符号化される。
【００８３】
z1微分モジュールは、z0が第１の閾値を下回る場合に、平方根関数sqrt（・）と、前記一方のベクトルの所定の長さと、前記一方のベクトルの逆量子化された第１及び第２の量子化されたfloat成分値とを用いて、z1の絶対値を計算する。すなわち：
z1＝sqrt（1−x1r2−y1r2）。
【００８４】
z0が第１の閾値を下回らない場合に、z1の絶対は、絶対値関数abs（・）を用いて次のように計算される。すなわち：
z1＝abs（（−x0r×x1r−y0r×y1r）／z0）。
【００８５】
z1について計算された値が小さく、従って不正確である可能性が高い場合は、誤差補正モジュールがまた有効にされ得る。z1について計算された値が小さい場合に誤差補正モジュールがまた有効にされるならば、エンコーダは更に、z1の原値と計算された値との間の更なる量子化された剰余を符号化する。
【００８６】
図２は、前述の実施例に従う復号化プロセスを例示する。
【００８７】
前記一方のベクトルの第１のfloat成分x0rは常に復号及び逆量子化される。更に、フラグビットが常に復号される。少なくとも、第１の量子化されたベクトル成分の逆量子化値x0rが１に等しくない限り、符号ビットが更に復号される。符号ビットは、前記一方のベクトルの第３の成分z0rの符号をシグナリングする。前記一方のベクトルの第２の成分y0が更に復号及び逆量子化される。
【００８８】
z0微分モジュールは、前記一方のベクトルの所定の長さと、復号及び逆量子化されたデータとを用いて、前記一方のベクトルの第３の成分の近似z0aを計算する。すなわち、少なくとも、第１の量子化されたベクトル成分の逆量子化値x0rの絶対値が１に等しくない限り、符号ビット並びに第１及び第２の量子化されたベクトル成分の逆量子化値x0r、y0rが、z0aを決定するために使用される。第１の量子化されたベクトル成分の逆量子化値x0rの絶対値が１に等しい場合は、y0r及びz0aは両方とも零と決定され得る。
【００８９】
誤差補正モジュールは、z0aについて計算された値が極めて小さい、すなわち、第１の閾値よりも小さく、よって不正確である可能性が高い場合に、有効にされる。そのような場合に、デコーダは更に、原値と近似z0aとの間の量子化された剰余を復号及び逆量子化する。すなわち、z0の再構成z0rは、z0aに等しいか、又は逆量子化された剰余の分だけz0aと相違する。
【００９０】
z0rが第１の閾値よりも小さい第２の閾値よりも小さくなく、x0rの絶対値がy0rの絶対値よりも小さい場合に、前記他方のベクトルの第２の量子化された成分が、y1rを求めるために復号及び逆量子化される。フラグビットは、前記他方のベクトルの第１の成分を計算するために使用される２つのとり得る解のいずれか一方を示す。次いで、x1r及びz1rが計算される。
【００９１】
z0rが第１の閾値よりも小さい第２の閾値よりも小さくなく、x0rの絶対値がy0rの絶対値よりも小さい場合に、y1微分モジュールは、フラグビットを用いて、前記他方のベクトルの第２の成分を計算するための２つのとり得る解のうち一方を選択する。すなわち：
y1r＝（x0r×y0r×x1r＋√Δ）／（1−x0r2）又は
y1r＝（x0r×y0r×x1r−√Δ）／（1−x0r2）。
【００９２】
これらの式において、Δはz0r2×（1−x0r2−y0r2）に等しく、このときz0rは、場合により剰余により補正された再構成である。
【００９３】
z0rが第１の閾値よりも小さい第２の閾値よりも小さくなく、x0rの絶対値がy0rの絶対値よりも小さくない場合に、前記他方のベクトルの第１の量子化された成分が、x1rを求めるために復号及び逆量子化される。フラグビットは、前記他方のベクトルの第２の成分を計算するために使用される２つのとり得る解のいずれか一方を示す。次いで、y1r及びz1rが計算される。
【００９４】
z0rが第１の閾値よりも小さい第２の閾値よりも小さくなく、x0rの絶対値がy0rの絶対値よりも小さくない場合に、x1微分モジュールは、フラグビットを用いて、前記他方のベクトルの第１の成分を計算するための２つのとり得る解のうち一方を選択する。すなわち：
x1r＝（x0r×y0r×y1r＋√Δ）／（1−y0r2）又は
x1r＝（x0r×y0r×y1r−√Δ）／（1−y0r2）。
【００９５】
これらの式において、Δはz0r2×（1−x0r2−y0r2）に等しく、このときz0rは、場合により剰余により補正された再構成である。
【００９６】
z0rが第１の閾値よりも小さい第２の閾値よりも小さく、y0rの絶対値がx0rの絶対値よりも小さい場合に、前記他方のベクトルの第３の量子化された成分が、z1rを求めるために復号及び逆量子化される。フラグビットは、y1rのsign（y1r）を決定するために使用され、x1r及びy1rが計算される。すなわち：
y1r＝sign（y1r）×abs（x0r）√（1−z1r2）
x1r＝−x0r×x1r／y0r。
【００９７】
z0rが第１の閾値よりも小さい第２の閾値よりも小さく、y0rの絶対値がx0rの絶対値よりも小さくない場合に、前記他方のベクトルの第３の量子化された成分が、z1rを求めるために復号及び逆量子化される。フラグビットは、x1rのsign（x1r）を決定するために使用され、x1r及びy1rが計算される。すなわち：
x1r＝sign（x1r）×abs（x0r）√（1−z1r2）
y1r＝−x0r×x1r／y0r。
【００９８】
z1rが復号及び逆量子化ではなく計算により得られ、第１の閾値を下回る絶対値を有する場合に、誤差補正モジュールが有効にされ得る。そのような場合に、デコーダは更に、原値とz1rとの間の更なる量子化された剰余を復号及び逆量子化し、逆量子化された更なる剰余に従ってz1rを補正する。
【００９９】
実施例はデカルト座標に関して本発明を記載するが、本発明はそれに制限されない。球座標において、同様の問題が、π／２（すなわち、９０度）に近い角度に関して起こる。すなわち、計算される角度の絶対値が閾値だけπ／２と異ならない場合に、正規化ベクトルの前記計算される角度の剰余を符号化することが提案される。
【０１００】
先に論じられたように、本原理は、３Ｄモデルの反復構造を符号化することに関連して有利に適用されてよい。有効に３Ｄモデルを符号化するよう、反復構造は、パターン及びインスタンスに分けられてよい。インスタンスは、例えば、対応するパターンのパターンＩＤと、平行移動、回転及びスケーリングに関する情報を含む変換行列とを用いて、対応するパターンの変形として表される。
【０１０１】
インスタンスがパターンＩＤ及び変換行列によって表される場合に、パターンＩＤ及び変換行列は、インスタンスの圧縮時に圧縮されるべきである。結果として、インスタンスは、パターンＩＤ及び変換行列により再構成されてよい。すなわち、インスタンスは、パターンＩＤによって示される復号化されたパターンの（復号化された変換行列からの）変形として再構成されてよい。
【０１０２】
図３は、例となる３Ｄモデルエンコーダ３００のブロック図を表す。装置３００の入力は、３Ｄモデルと、３Ｄモデルを符号化するための品質パラメータと、他のメタデータとを含む。３Ｄモデルは最初に、反復構造発見モジュール３１０を通る。反復構造発見モジュール３１０は、パターン、インスタンス及び固有コンポーネントに関して３Ｄモデルを出力する。パターンエンコーダ３２０は、パターンを圧縮するために用いられ、固有コンポーネントエンコーダ３５０は、固有コンポーネントを符号化するために用いられる。インスタンスに関し、インスタンスコンポーネント情報は、ユーザにより選択されたモードに基づき符号化される。インスタンス情報グループモードが選択される場合は、インスタンス情報は、集合インスタンス情報エンコーダ３４０を用いて符号化される。そうでない場合は、インスタンス情報は、素インスタンス情報エンコーダ３３０を用いて符号化される。符号化されたコンポーネントは更に、反復構造検証部３６０において検証される。符号化されたコンポーネントがその品質要件を満足しない場合は、それは、固有コンポーネントエンコーダ３５０を用いて符号化される。パターン、インスタンス及び固有コンポーネントのためのビットストリームがビットストリーム組立部３７０でアセンブルされる。
【０１０３】
図４は、例となる３Ｄモデルデコーダ４００のブロック図を表す。装置４００の入力は、３Ｄモデルのビットストリーム、例えば、エンコーダ３００によって生成されたビットストリームを有してよい。圧縮されたビットストリームにおけるパターンに関する情報は、パターンデコーダ４２０によって復号される。固有コンポーネントに関する情報は、固有コンポーネントデコーダ４５０によって復号される。インスタンス情報の復号化はまた、ユーザにより選択されたモードに依存する。インスタンス情報グループモードが選択される場合は、インスタンス情報は、集合インスタンス情報デコーダ４４０を用いて復号される。そうでない場合は、インスタンス情報は、素インスタンス情報デコーダ４３０を用いて復号される。復号されたパターン、インスタンス情報及び固有コンポーネントは、モデル再構成モジュール４６０で出力３Ｄモデルを生成するよう再構成される。
【０１０４】
ここで記載される実施は、例えば、方法若しくはプロセス、装置、ソフトウェアプログラム、データストリーム、又は信号において、実施されてよい。たとえ単一の実施形態に関してしか論じられない（例えば、方法としてしか論じられない）としても、論じられる特徴の実施は他の形態においても実施されてよい（例えば、装置又はプログラム）。装置は、例えば、適切なハードウェア、ソフトウェア、及びファームウェアにおいて、実施されてよい。方法は、例えば、コンピュータ、マイクロプロセッサ、集積回路、又はプログラム可能な論理装置を含むプロセッサ（概して処理装置をさす。）等の装置において、実施されてよい。プロセッサはまた、例えば、コンピュータ、携帯電話機、ポータブル／パーソナルデジタルアシスタント（ＰＤＡ）、及びエンドユーザ間の情報の通信を助ける他の装置等の通信装置を含む。
【０１０５】
本原理の“実施形態”若しくは“実施例”又は“実施”の言及並びにそれらの他の言い換えは、実施形態に関連して記載される特定の特徴、構造、特性等が本原理の少なくとも１つの実施形態に含まれることを意味する。よって、明細書の様々な箇所で見られる“実施形態において”若しくは“実施例において”又は“実施において”との表現及びそれらの他の言い換えの出現は、必ずしも全て同じ実施形態に言及しているわけではない。
【０１０６】
当業者には明らかなように、実施は、例えば、記憶又は伝送される情報を搬送するようフォーマットされた様々な信号を生成してよい。情報には、例えば、方法を実行するための命令、又は記載される実施の１つにより生成されるデータが含まれてよい。例えば、信号は、記載される実施形態のビットストリームを搬送するようフォーマットされてよい。そのような信号は、例えば、（例えば、スペクトラムの無線周波数部分を用いて）電磁波として、又はベースバンド信号としてフォーマットされてよい。フォーマッティングは、例えば、データストリームを符号化し、符号化されたデータストリームによりキャリアを変調することを含んでよい。信号が搬送する情報は、例えば、アナログ又はデジタル情報であってよい。信号は、知られているように、多種多様な有線又は無線リンクを介して送信されてよい。信号は、プロセッサにより読み取り可能な媒体において記憶されてよい。
【０１０７】
原理上、開示される発明は、他のデータ圧縮エリアにも適用可能である。本発明は、独自のビットストリームフォーマットをもたらす。
【０１０８】
ビットストリームは変換データを全て埋め込み、一方、それは効率的であり且つ複数の用途に対処することができる。時々、ビットストリームサイズ又は復号化効率は、最も誤りの起こりにくい事項である。従って、２つのモードオプションが、１つのインスタンスの変換データ、すなわち、その位置、方位及びスケーリング係数を如何にしてビットストリームに置くかに関して開示される。第１のモード（オプションＡ）では、１つのインスタンスの位置、方位及びとり得るスケーリング係数が、ビットストリームにおいてまとめて圧縮される。第２のモード（オプションＢ）では、全てのインスタンスの位置、法又はとり得るスケーリング係数が、ビットストリームにおいてまとめて圧縮される。
【０１０９】
本発明は、単に一例として記載されていることが理解され、詳細の変形は、本発明の適用範囲から逸脱することなく行われ得る。
【０１１０】
明細書並びに（必要に応じて）特許請求の範囲及び図面において開示されているそれぞれの特徴は、独立して、又は何らかの適切な組み合わせにおいて、提供されてよい。特徴は、必要に応じて、ハードウェア、ソフトウェア、又はそれらの組み合わせにおいて実施されてよい。接続は、必要に応じて、無線接続又は有線（必ずしも直接又は専用でなくてもよい。）接続として実施されてよい。
特許請求の範囲における参照符号は、単なる一例であり、特許請求の範囲の適用範囲を制限する効果を有さない。
【図１】
2014527736.tif 000005
【図２】
2014527736.tif 000006
【図３】
2014527736.tif 000007
【図４】
2014527736.tif 000008
【国際調査報告】
2014527736.tif 000009
2014527736.tif 000010