(57)【要約】      （修正有）【課題】処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替え、処理を低減するＤＭＭ（Ｄｅｐｔｈ  Ｍｏｄｅｌｉｎｇ  Ｍｏｄｅ）予測装置、画像復号装置及び画像符号化装置を提供する。【解決手段】ウェッジレットパターン生成手段によって導出されたウェッジパターンと、ウェッジパターンで分割される領域毎の予測値を導出するＤＣ（平均）予測値導出手段を備えるＤＭＭ予測装置において、ウェッジレットパターン生成手段は、基本パターンを生成する基本パターン生成部と、回転パターンを導出する回転パターン生成部を備える。【選択図】図１
2017216487.tif 000002
【特許請求の範囲】
【請求項１】
ウェッジレットパターン生成手段によって導出されたウェッジパターンと、前記ウェッジパターンで分割される領域毎の予測値を導出するＤＣ予測値導出手段を備えるＤＭＭ予測装置において、前記ウェッジレットパターン生成手段は、基本パターンを生成する基本パターン生成部と、回転パターンを導出する回転パターン生成部を備えることを特徴とするＤＭＭ予測装置。
【請求項２】
前記基本パターン生成部は、線分描画部と領域フィル部から構成されることを特徴とする請求項１に記載のＤＭＭ予測装置。
【請求項３】
前記回転パターン生成部は、入力された参照ウェッジレットパターンから対象ウェッジレットパターンを生成し、座標(x, y)上の対象ウェッジレットパターンの値を、(x, y)を回転行列で座標変換して得られる座標(i, j)上の参照ウェッジレットパターンの値を用いて導出することを特徴とする請求項１〜請求項２に記載のＤＭＭ予測装置。
【請求項４】
前記回転パターン生成部は、前記対象ウェッジレットパターンの値として、前記参照ウェッジレットパターンの座標(i, j)の値を反転させた値を用いることを特徴とする請求項３に記載のＤＭＭ予測装置。
【請求項５】
前記基本パターン生成部で生成される第１基本パターン、第２基本パターンと、前記回転パターン生成部により、第１基本パターンから生成される第１基本パターン第１回転パターン、第１基本パターン第２回転パターン、第１基本パターン第３回転パターンと、前記回転パターン生成部により、第２基本パターンから生成される第２基本パターン第１回転パターンからウェッジレットパターンを生成することを特徴とする請求項４に記載のＤＭＭ予測装置。
【請求項６】
前記回転パターン生成部は、基本パターン設定部で設定される開始点と終了点の間のウェッジレットパターンを入力として、回転パターンを導出することを特徴とする請求項５に記載のＤＭＭ予測装置。
【請求項７】
前記線分描画部は、ウェッジレットパターンサイズpatternSizeを、refShiftだけ左シフトして得られるサイズpatternSize<< refShiftの仮想ブロック上の座標(xPos, yPos)を、refShiftだけ右シフトして得られる座標(xPos>> refShift, yPos>> refShift)に１を設定することを特徴とする請求項２に記載のＤＭＭ予測装置。
【請求項８】
前記領域フィル部は、パターンが１である画素を探索し、パターンが１である画素があれば継続する画素を１に設定することを特徴とする請求項２に記載のＤＭＭ予測装置。
【請求項９】
前記基本パターンについてのみ、一致判定を行い、前記回転パターンについては、一致判定を行わずに格納するパターン格納部をさらに備えることを特徴とする請求項３に記載のＤＭＭ予測装置。
【請求項１０】
前記基本パターン生成部により第１基本パターン、第２基本パターンを生成し、前記回転パターン生成部により、第１回転パターン、第２回転パターン、第３回転パターン、第４回転パターンの回転パターンを生成し、さらに、前記回転パターン生成部は直前に生成したパターンに基づいて、回転パターンを生成することを特徴とする請求項１に記載のＤＭＭ予測装置。
【請求項１１】
前記ＤＭＭ予測装置は、あるグループのパターンを生成する前のパターン数をスタート開始位置posStart、回転パターンを生成する前のパターン数−１を終了位置posEndとし、開始位置から終了位置にある各位置posのパターンを参照して、前記回転パターン生成部により回転させることにより回転パターンを生成することを特徴とする請求項１０に記載のＤＭＭ予測装置。
【請求項１２】
前記回転パターン生成部は、90度回転を用いることを特徴とする請求項１０から請求項１１に記載のＤＭＭ予測装置。
【請求項１３】
前記回転パターン生成部の90度回転は、(x, y)を座標変換した位置(x+y, wBlkSize - 1 - x + y)の参照パターンrefPatternの値refPattern[x+y][wBlkSize - 1 - x + y]を参照して、(x, y)の位置の回転パターンの値Pattern[x][y]を導出することを特徴とする請求項１２に記載のＤＭＭ予測装置。
【請求項１４】
前記回転パターン生成部は、270度回転を用いることを特徴とする請求項１０から請求項１１に記載のＤＭＭ予測装置。
【請求項１５】
前記請求項１から請求項１４に記載のＤＭＭ予測装置を備える画像復号装置。
【請求項１６】
前記請求項１から請求項１４に記載のＤＭＭ予測装置を備える画像符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を表す符号化データを復号する画像復号装置、および画像を符号化することによって符号化データを生成する画像符号化装置に関する。
【背景技術】
【０００２】
複数視点の画像符号化技術には、複数の視点の画像を符号化する際に画像間の視差を予測することによって情報量を低減する視差予測符号化や、その符号化方法に対応した復号方法が提案されている。視点画像間の視差を表すベクトルを変位ベクトルと呼ぶ。変位ベクトルは、水平方向の要素（ｘ成分）と垂直方向の要素（ｙ成分）を有する２次元のベクトルであり、１つの画像を分割した領域であるブロック毎に算出される。また、複数視点の画像を取得するには、それぞれの視点に配置されたカメラを用いることが一般的である。複数視点の符号化では、各視点画像は、複数のレイヤにおいてそれぞれ異なるレイヤとして符号化される。複数のレイヤから構成される動画像の符号化方法は、一般に、スケーラブル符号化又は階層符号化と呼ばれる。スケーラブル符号化では、レイヤ間で予測を行うことで、高い符号化効率を実現する。レイヤ間で予測を行わずに基準となるレイヤは、ベースレイヤ、それ以外のレイヤは拡張レイヤと呼ばれる。レイヤが視点画像から構成される場合のスケーラブル符号化を、ビュースケーラブル符号化と呼ぶ。このとき、ベースレイヤはベースビュー、拡張レイヤは非ベースビューとも呼ばれる。さらに、ビュースケーラブルに加え、テクスチャ（画像）からなるテクスチャレイヤ（画像レイヤ）と、デプスマップ（距離画像）からなるデプスレイヤ（距離画像レイヤ）から構成される場合のスケーラブル符号化は、３次元スケーラブル符号化と呼ばれる。
【０００３】
例えば、非特許文献１のHEVCベースの３次元スケーラブル符号化技術がある。非特許文献１では、効率良くデプスマップを符号化するために、DMM予測（Depth Modeling Mode；デプスイントラ予測もという)や、領域別DC符号化(SDC; Segment-wise DC Coding)というデプス符号化ツールがある。
【０００４】
領域別DC符号化は、デプスマップ上の対象ブロックにおいて、１又は複数の領域毎に、予測残差を、周波数変換・逆量子化をせずに、予測残差の平均(DC)値を表わす予測残差ＤＣ情報を符号化する技術である。
【０００５】
DMM予測は、基本的に、デプスマップ上の対象ブロック（デプスブロックとも称する）は、２つの非矩形の平坦領域から構成され、各平坦領域のデプス値は固定値で表現されるというデプスモデルに基づいている。また、デプスモデルは、各画素が属する領域を表わすパーティション情報、及び各領域のデプス値情報から構成される。
【０００６】
DMM予測では、ウェッジレット分割 (Wedgelet Partition)、及び輪郭分割(Contour Partition)がある。非特許文献１では、DMM1予測において、ウェッジレット分割の分割パターン（ウェッジパターン、ウェッジレットパターン）を、ブロックサイズ毎に予め定義したルックアップテーブルに保持し、分割パターンを指定する識別子（ウェッジパターンインデックスwedge_full_tab_idx）により指定されるウェッジパターンが選択される。選択されたウェッジパターンに基づいてデプスブロックを２つの領域へ分割し、分割された領域毎に周辺画素から予測されるデプス予測値と、デプス予測値を補正するデプス値情報に基づいて、各領域のデプス値を復元する予測値を予測する技術である。
【０００７】
なお、DMM予測における領域毎のデプス値情報、及び領域別DC符号化における領域毎の予測残差DC情報を総称して、DCオフセット情報と称し、非特許文献１では、共通のシンタックス(depth_dc_flag, depth_dc_abs, depth_dc_sign_flag)を利用して符号化される。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】G. Tech, K. Wegner, Y. Chen, S. Yea, “3D-HEVC Draft Text 5”, JCT3V-I1001_v3, JCT-3V 9th Meeting: Sapporo, JP, 3 - 9 July 2014（2014年8月13日公開）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献１のウェッジパターン生成では、全てのパターンを線分描画処理、及び、領域フィル処理によって生成しているため、処理量が大きいという課題がある。また、仮想的にブロックサイズを縦横２倍にしてウェッジパターンを生成する場合にメモリサイズが大きいという課題がある。また、全てのウェッジパターンにおいて格納する場合に、ウェッジパターンの一致比較を行うため格納の処理量が大きいという課題がある。
【課題を解決するための手段】
【００１０】
本発明の１つの形態は、ウェッジレットパターン生成手段によって導出されたウェッジパターンと、前記ウェッジパターンで分割される領域毎の予測値を導出するＤＣ予測値導出手段を備えるＤＭＭ予測装置において、前記ウェッジレットパターン生成手段は、基本パターンを生成する基本パターン生成部と、回転パターンを導出する回転パターン生成部を備えることを特徴とする。
【００１１】
本発明の１つの形態は、前記基本パターン生成部は、線分描画部と領域フィル部から構成されることを特徴とする。
【００１２】
本発明の１つの形態は、前記回転パターン生成部は、入力された参照ウェッジレットパターンから対象ウェッジレットパターンを生成し、座標(x, y)上の対象ウェッジレットパターンの値を、(x, y)を回転行列で座標変換して得られる座標(i, j)上の参照ウェッジレットパターンの値を用いて導出することを特徴とする。
【００１３】
本発明の１つの形態は、前記回転パターン生成部は、前記対象ウェッジレットパターンの値として、前記参照ウェッジレットパターンの座標(i, j)の値を反転させた値を用いることを特徴とする。
【００１４】
本発明の１つの形態は、前記基本パターン生成部で生成される第１基本パターン、第２基本パターンと、前記回転パターン生成部により、第１基本パターンから生成される第１基本パターン第１回転パターン、第１基本パターン第２回転パターン、第１基本パターン第３回転パターンと、前記回転パターン生成部により、第２基本パターンから生成される第２基本パターン第１回転パターンからウェッジレットパターンを生成することを特徴とする。
【００１５】
本発明の１つの形態は、前記回転パターン生成部は、基本パターン設定部で設定される開始点と終了点の間のウェッジレットパターンを入力として、回転パターンを導出することを特徴とする。
【００１６】
本発明の１つの形態は、前記線分描画部は、ウェッジレットパターンサイズpatternSizeを、refShiftだけ左シフトして得られるサイズpatternSize<< refShiftの仮想ブロック上の座標(xPos, yPos)を、refShiftだけ右シフトして得られる座標(xPos>> refShift, yPos>> refShift)に１を設定することを特徴とする。
【００１７】
本発明の１つの形態は、前記領域フィル部は、パターンが１である画素を探索し、パターンが１である画素があれば継続する画素を１に設定することを特徴とする。
【００１８】
本発明の１つの形態は、前記基本パターンについてのみ、一致判定を行い、前記回転パターンについては、一致判定を行わずに格納するパターン格納部をさらに備えることを特徴とする。
【００１９】
本発明の１つの形態は、前記基本パターン生成部により第１基本パターン、第２基本パターンを生成し、前記回転パターン生成部により、第１回転パターン、第２回転パターン、第３回転パターン、第４回転パターンの回転パターンを生成し、さらに、前記回転パターン生成部は直前に生成したパターンに基づいて、回転パターンを生成することを特徴とする。
【００２０】
本発明の１つの形態は、前記ＤＭＭ予測装置は、あるグループのパターンを生成する前のパターン数をスタート開始位置posStart、回転パターンを生成する前のパターン数−１を終了位置posEndとし、開始位置から終了位置にある各位置posのパターンを参照して、前記回転パターン生成部により回転させることにより回転パターンを生成することを特徴とする。
【００２１】
本発明の１つの形態は、前記回転パターン生成部は、90度回転を用いることを特徴とする。
【００２２】
本発明の１つの形態は、前記回転パターン生成部の90度回転は、(x, y)を座標変換した位置(x+y, wBlkSize - 1 - x + y)の参照パターンrefPatternの値refPattern[x+y][wBlkSize - 1 - x + y]を参照して、(x, y)の位置の回転パターンの値Pattern[x][y]を導出することを特徴とする。
【００２３】
本発明の１つの形態は、前記回転パターン生成部は、270度回転を用いることを特徴とする。
【００２４】
本発明の画像復号装置の１つの形態は、上述したＤＭＭ予測装置を備える。
【００２５】
本発明の画像符号化装置の１つの形態は、上述したＤＭＭ予測装置を備える。
【発明の効果】
【００２６】
本実施形態のウェッジレットパターン生成部１４５Ｔ４は、全てのウェッジパターンを線分描画部１４６２、領域フィル部１４６３を用いた線分描画処理、領域フィル処理により生成するのではなく、一部のウェッジパターンは回転パターン生成部１５６５を用いた回転処理により生成する。処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替えることができるため、処理を低減する効果を奏する。
【図面の簡単な説明】
【００２７】
【図１】本実施例に係るＤＭＭ予測部の詳細構成を示すブロック図である。
【図２】本発明の実施形態に係る画像伝送システムの構成を示す概略図である。
【図３】本実施例に係る動画像復号装置の概略的構成について示した機能ブロック図である。
【図４】本発明の一実施形態に係る動画像符号化装置によって生成され、上記動画像復号装置によって復号される符号化データのデータ構成を示す図であって、（ａ）は、シーケンスSEQを既定するシーケンスレイヤ、（ｂ）は、ピクチャPICTを規定するピクチャレイヤ、（ｃ）は、スライスSを規定するスライスレイヤ、（ｄ）は、スライスデータに含まれるツリーブロックを規定するツリーブロックレイヤ、（ｅ）は、符号化ツリーに含まれる符号化単位（Coding Unit; CU）を規定するＣＵレイヤ（符号化ユニットレイヤ）を示す図である。
【図５】ＣＵレイヤに含まれるシンタックスの例を示す図である。（ａ）は、イントラＣＵに係るシンタックステーブルの一例を示し、（ｂ）は、イントラ予測モード拡張に係るシンタックステーブルの一例である。
【図６】ＣＵレイヤに含まれるＤＣオフセット情報に係るシンタックスの一例である。
【図７】上記動画像復号装置で利用されるイントラ予測方式の分類と対応する予測モード番号の例を示す図である。
【図８】方向予測に属する３３種類の予測モードについて、予測モードの識別子に対応する予測方向を示す図である。
【図９】上記動画像復号装置が備える予測画像生成部の構成例について示す機能ブロック図である。
【図１０】上記予測画像生成部におけるＣＵ単位の予測画像生成処理の概略を示すフローチャートである。
【図１１】ＤＭＭ予測の概略について説明する図である。（ａ）はブロック上のオブジェクトのエッジ境界を示す例であり、（ｂ）は該ブロックを、オブジェクトのエッジ境界に沿って２つの領域（Ｐ１、Ｐ２）へ分割することを示す分割パターンであるウェッジレットパターン（wedgePattern）の一例を示し、（ｃ）上記各分割された領域へ予測値を割り当てた一例である。
【図１２】ＤＭＭ予測において、ウェッジレット分割（ＤＭＭ１）に基づくウェッジレットパターンの生成方法を説明する図である。（ａ）はブロック上の始点Ｓ、及び終点Ｅの一例であり、（ｂ）は、始点Ｓと終点Ｅを結ぶ線分の一例を示し、（ｃ）線分で分割された領域のフィルの一例を示し、（ｄ）はウェッジレートパターンの一例を示す。。
【図１３】ＤＭＭ１予測において、ウェッジレットパターン生成部１４５Ｔ４において生成されるウェッジ方向wedgeOri(wedgeOri=0..5)別のウェッジレットパターンの一例を説明するための図である。（ａ）は、wedgeOri=０のウェッジレットパターンの例を示し、（ｂ）は、wedgeOri=１のウェッジレットパターンの例を示し、（ｃ）は、wedgeOri＝２のウェッジレットパターンをの例を示し、（ｄ）は、wedgeOri＝３のウェッジレットパターンの例を示し、（ｅ）は、wedgeOri=４のウェッジレットパターンの例を示し、（ｆ）はwedgeOri=５のウェッジレットパターンの例である。
【図１４】ウェッジレットパターン生成部１４５Ｔ４の構成を示すブロック図である。
【図１５】ウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理を示すフローチャートである。
【図１６】ウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理を示す図である。
【図１７】ウェッジレットパターン生成部１４５Ｔ４の動作を示すフローチャートである。
【図１８】パターン格納部１４６４の動作を示すフローチャートである。
【図１９】基本パターン生成および回転パターン生成に用いるパラメータを示すテーブルである
【図２０】本実施形態の仮想座標（posX、posY）と、パターンとの関係を示す図である。
【図２１】本実施形態の領域フィル部１４６３の動作を説明する図である。第１基本パターンにおける処理を示す。
【図２２】ウェッジレットパターン生成部１４５Ｔ４´の構成を説明する図である。
【図２３】ウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理を示す図である。
【図２４】本実施形態の回転パターン生成部１４６５´の動作を説明する図である。
【図２５】本実施形態の回転パターン生成部１４６５´の動作を説明する図である。
【図２６】ウェッジレットパターン生成部１４５Ｔ４´の備えるパターン格納部１４６４´の動作を示すフローチャートである。
【図２７】ウェッジレットパターン生成部１４５Ｔ４´´の備えるパターン格納部１４６４´´の動作を示すフローチャートである。
【図２８】本実施形態のウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理を示すフローチャートの別の例である。第２基本パターンの次に第１基本パターンを生成する場合を示す。
【図２９】本発明の一実施形態に係る動画像符号化装置の構成について示す機能ブロック図である。
【図３０】本実施形態のウェッジレットパターン生成部１４５Ｔ４Ｂの構成を示すブロック図である。
【図３１】本実施形態のウェッジレットパターン生成部１４５Ｔ４Ｂにおけるウェッジレットパターン生成処理を示す図である。
【図３２】本実施形態のウェッジレットパターン生成部１４５Ｔ４Ｂの動作を示すフローチャートである。
【発明を実施するための形態】
【００２８】
〔概要〕
以下、図面を参照しながら本発明の実施形態について説明する。
【００２９】
図２は、本実施形態に係る画像伝送システム５の構成を示す概略図である。
【００３０】
画像伝送システム５は、複数のレイヤ画像を符号化した符号を伝送し、伝送された符号を復号した画像を表示するシステムである。画像伝送システム５は、画像符号化装置２、ネットワーク３、画像復号装置２及び画像表示装置４を含んで構成される。
【００３１】
画像符号化装置２には、複数のレイヤ画像（テクスチャ画像ともいう）を示す信号Ｔが入力される。レイヤ画像とは、ある解像度及びある視点で視認もしくは撮影される画像である。複数のレイヤ画像を用いて３次元画像を符号化するビュースケーラブル符号化を行う場合、複数のレイヤ画像のそれぞれは、視点画像と呼ばれる。ここで、視点は撮影装置の位置又は観測点に相当する。例えば、複数の視点画像は、被写体に向かって左右の撮影装置のそれぞれが撮影した画像である。画像符号化装置２は、この信号のそれぞれを符号化して符号化データ＃１を生成する。符号化データ＃１の詳細については、後述する。視点画像とは、ある視点において観測される２次元画像（平面画像）である。視点画像は、例えば２次元平面内に配置された画素毎の輝度値、又は色信号値で示される。
【００３２】
以下では、１枚の視点画像又は、その視点画像を示す信号をピクチャ（picture）と呼ぶ。本実施形態では、複数のレイヤ画像として、少なくともベースレイヤ画像と、ベースレイヤ画像以外の画像（拡張レイヤ画像）を含む画像の符号化および復号を扱う。複数のレイヤのうち、画像もしくは符号化パラメータにおいて参照関係（依存関係）にある２つのレイヤについて、参照される側の画像を、第１レイヤ画像、参照する側の画像を第２レイヤ画像と呼ぶ。例えば、ベースレイヤを参照して符号化される（ベースレイヤ以外の）エンハンスレイヤ画像がある場合、ベースレイヤ画像を第１レイヤ画像、エンハンスレイヤ画像を第２レイヤ画像として扱う。なお、エンハンスレイヤ画像の例としては、ベースビュー以外の視点の画像やデプス画像などがある。
【００３３】
視点画像は、例えば２次元平面内に配置された画素毎の輝度値、又は色信号値で示される。また、デプスマップ（depth map、「デプス画像」、「深度画像」、「距離画像」とも言う）とは、被写空間に含まれる被写体や背景の、視点（撮影装置等）からの距離に対応する信号値（「デプス値」、「深度値」、「デプス」等と呼ぶ）であって、二次元平面に配置された画素毎の信号値（画素値）からなる画像信号である。デプスマップを構成する画素は、視点画像を構成する画素と対応する。従って、デプスマップは、被写空間を二次元平面に射影した基準となる画像信号である視点画像を用いて、三次元の被写空間を表すための手がかりとなる。
【００３４】
ネットワーク３は、画像符号化装置２が生成した符号化データ＃１を画像復号装置１に伝送する。ネットワーク３は、インターネット（internet）、広域ネットワーク（WAN:Wide Area Network）、小規模ネットワーク（LAN:Local Area Network）又はこれらの組み合わせである。ネットワーク３は、必ずしも双方向の通信網に限らず、地上波ディジタル放送、衛星放送等の放送波を伝送する一方向又は双方向の通信網であっても良い。また、ネットワーク３は、ＤＶＤ（Digital Versatile Disc）、ＢＤ（Blue-ray Disc）等の符号化データ＃１を記録した記憶媒体で代替されても良い。
【００３５】
画像復号装置１は、ネットワーク３が伝送した符号化データ＃１のそれぞれを復号し、それぞれ復号した複数の復号レイヤ画像Ｔｄ（復号視点画像TexturePic、及び復号デプスマップDepthPic）を生成して出力する。
【００３６】
画像表示装置４は、画像復号装置１が生成した複数の復号レイヤ画像Ｔｄの全部又は一部を表示する。例えば、ビュースケーラブル符号化においては、全部の場合、３次元画像（立体画像）や自由視点画像が表示され、一部の場合、２次元画像が表示される。画像表示装置４は、例えば、液晶ディスプレイ、有機ＥＬ（Electro-luminescence）ディスプレイ等の表示デバイスを備える。また、空間スケーラブル符号化、ＳＮＲスケーラブル符号化では、画像復号装置１、画像表示装置４が高い処理能力を有する場合には、画質の高い拡張レイヤ画像を表示し、より低い処理能力しか有しない場合には、拡張レイヤほど高い処理能力、表示能力を必要としないベースレイヤ画像を表示する。
【００３７】
視点画像は、例えば２次元平面内に配置された画素毎の輝度値、又は色信号値で示される。また、デプスマップ（depth map、「デプス画像」、「深度画像」、「距離画像」とも言う）とは、被写空間に含まれる被写体や背景の、視点（撮影装置等）からの距離に対応する信号値（「デプス値」、「深度値」、「デプス」等と呼ぶ）であって、二次元平面に配置された画素毎の信号値（画素値）からなる画像信号である。デプスマップを構成する画素は、視点画像を構成する画素と対応する。従って、デプスマップは、被写空間を二次元平面に射影した基準となる画像信号である視点画像を用いて、三次元の被写空間を表すための手がかりとなる。
【００３８】
以下では、図１〜図３２を参照しながら、本発明の一実施形態に係る画像復号装置１および画像符号化装置２について説明する。図３は、画像復号装置１の概略的構成を示す機能ブロック図である。
【００３９】
動画像復号装置１には、動画像符号化装置２がレイヤ画像（1又は複数の視点画像TexturePic、及び視点画像TexturePicに対応する同時刻のデプスマップDepthPic）を符号化した符号化データ＃１が入力される。動画像復号装置１は、入力された符号化データ＃１を復号して、レイヤ画像＃２（1又は複数の視点画像TexturePic、及び視点画像TexturePicに対応する同時刻のデプスマップDepthPic）を外部に出力する。動画像復号装置１の詳細な説明に先立ち、符号化データ＃１の構成を以下に説明する。
〔符号化データの構成〕
図４を用いて、動画像符号化装置２によって生成され、動画像復号装置１によって復号される符号化データ＃１の構成例について説明する。符号化データ＃１は、例示的に、シーケンス、およびシーケンスを構成する複数のピクチャを含む。
【００４０】
符号化データ＃１におけるシーケンスレイヤ以下の階層の構造を図４に示す。図４の（ａ）〜（ｅ）は、それぞれ、シーケンスＳＥＱを規定するシーケンスレイヤ、ピクチャＰＩＣＴを規定するピクチャレイヤ、スライスＳを規定するスライスレイヤ、スライスデータを規定するスライスデータレイヤ、符号化ツリーに含まれる符号化単位（Coding Unit; CU）を規定する符号化ユニットレイヤを示す図である。
【００４１】
（シーケンスレイヤ）
シーケンスレイヤでは、処理対象のシーケンスＳＥＱ（以下、対象シーケンスとも称する）を復号するために動画像復号装置１が参照するデータの集合が規定されている。シーケンスＳＥＱは、図４の（ａ）に示すように、ビデオパラメータセット（Video Parameter Set）シーケンスパラメータセットＳＰＳ（Sequence Parameter Set）、ピクチャパラメータセットＰＰＳ（Picture Parameter Set）、ピクチャＰＩＣＴ、及び、付加拡張情報ＳＥＩ（Supplemental Enhancement Information）を含んでいる。ここで＃の後に示される値はレイヤＩＤを示す。図４では、＃０と＃１、すなわちレイヤ０とレイヤ１の符号化データが存在する例を示すが、レイヤの種類およびレイヤの数はこれによらない。
【００４２】
ビデオパラメータセットＶＰＳは、複数のレイヤから構成されている動画像において、複数の動画像に共通する符号化パラメータの集合および動画像に含まれる複数のレイヤおよび個々のレイヤに関連する符号化パラメータの集合が規定されている。
【００４３】
シーケンスパラメータセットＳＰＳでは、対象シーケンスを復号するために動画像復号装置１が参照する符号化パラメータの集合が規定されている。例えば、ピクチャの幅や高さが規定される。
【００４４】
ピクチャパラメータセットＰＰＳでは、対象シーケンス内の各ピクチャを復号するために動画像復号装置１が参照する符号化パラメータの集合が規定されている。例えば、ピクチャの復号に用いられる量子化幅の基準値（pic_init_qp_minus26）や重み付き予測の適用を示すフラグ（weighted_pred_flag）が含まれる。なお、ＰＰＳは複数存在してもよい。その場合、対象シーケンス内の各ピクチャから複数のＰＰＳの何れかを選択する。
【００４５】
（ピクチャレイヤ）
ピクチャレイヤでは、処理対象のピクチャＰＩＣＴ（以下、対象ピクチャとも称する）を復号するために動画像復号装置１が参照するデータの集合が規定されている。ピクチャＰＩＣＴは、図４の（ｂ）に示すように、スライスＳ1〜ＳNSを含んでいる（NSはピクチャＰＩＣＴに含まれるスライスの総数）。
【００４６】
なお、以下、スライスＳ1〜ＳNSのそれぞれを区別する必要が無い場合、符号の添え字を省略して記述することがある。また、以下に説明する符号化データ＃１に含まれるデータであって、添え字を付している他のデータについても同様である。
【００４７】
（スライスレイヤ）
スライスレイヤでは、処理対象のスライスＳ（対象スライスとも称する、スライスセグメント）を復号するために動画像復号装置１が参照するデータの集合が規定されている。スライスＳは、図４の（ｃ）に示すように、スライスヘッダＳＨ、及び、スライスデータＳＤＡＴＡを含んでいる。
【００４８】
スライスヘッダＳＨには、対象スライスの復号方法を決定するために動画像復号装置１が参照する符号化パラメータ群が含まれる。スライスタイプを指定するスライスタイプ指定情報（slice_type）は、スライスヘッダＳＨに含まれる符号化パラメータの一例である。
【００４９】
スライスタイプ指定情報により指定可能なスライスタイプとしては、（１）符号化の際にイントラ予測のみを用いるＩスライス、（２）符号化の際に単方向予測、又は、イントラ予測を用いるＰスライス、（３）符号化の際に単方向予測、双方向予測、又は、イントラ予測を用いるＢスライスなどが挙げられる。
【００５０】
スライスデータＳＤＡＴＡには、１又は複数のツリーブロックＴＢＬＫ１〜ＴＢＬＫＮＣ（ＮＣは、スライスデータＳＤＡＴＡに含まれるツリーブロックの総数）が含まれる。
【００５１】
（ツリーブロックレイヤ）
ツリーブロックレイヤでは、処理対象のツリーブロックＴＢＬＫ（以下、対象ツリーブロックとも称する）を復号するために動画像復号装置１が参照するデータの集合が規定されている。
【００５２】
ツリーブロックＴＢＬＫは、ツリーブロックヘッダＴＢＬＫＨと、符号化単位情報ＣＵ１〜ＣＵＮＬ（ＮＬはツリーブロックＴＢＬＫに含まれる符号化単位情報の総数）とを含む。ここで、まず、ツリーブロックＴＢＬＫと、符号化単位情報ＣＵとの関係について説明すると次のとおりである。
【００５３】
ツリーブロックＴＢＬＫは、イントラ予測またはインター予測、および、変換の各処理ためのブロックサイズを特定するためのユニットに分割される。
【００５４】
ツリーブロックＴＢＬＫの上記ユニットは、再帰的な４分木分割により分割されている。この再帰的な４分木分割により得られる木構造のことを以下、符号化ツリー（coding tree）と称する。
【００５５】
以下、符号化ツリーの末端のノードであるリーフ（leaf）に対応するユニットを、符号化ノード（coding node）として参照する。また、符号化ノードは、符号化処理の基本的な単位となるため、以下、符号化ノードのことを、符号化単位（ＣＵ）とも称する。
【００５６】
つまり、符号化単位情報（以下、ＣＵ情報と称する）ＣＵ１〜ＣＵＮＬは、ツリーブロックＴＢＬＫを再帰的に４分木分割して得られる各符号化ノード（符号化単位）に対応する情報である。
【００５７】
また、符号化ツリーのルート（root）は、ツリーブロックＴＢＬＫに対応付けられる。換言すれば、ツリーブロックＴＢＬＫは、複数の符号化ノードを再帰的に含む４分木分割の木構造の最上位ノードに対応付けられる。
【００５８】
なお、各符号化ノードのサイズは、当該符号化ノードが直接に属する符号化ノード（すなわち、当該符号化ノードの１階層上位のノードのユニット）のサイズの縦横とも半分である。
【００５９】
（ツリーブロックヘッダ）
ツリーブロックヘッダＴＢＬＫＨには、対象ツリーブロックの復号方法を決定するために動画像復号装置１が参照する符号化パラメータが含まれる。具体的には、図４の（ｄ）に示すように、対象ツリーブロックの各ＣＵへの分割パターンを指定するツリーブロック分割情報ＳＰ＿ＴＢＬＫ、および、量子化ステップの大きさを指定する量子化パラメータ差分Δｑｐ（qp_delta）が含まれる。
【００６０】
ツリーブロック分割情報ＳＰ＿ＴＢＬＫは、ツリーブロックを分割するための符号化ツリーを表す情報であり、具体的には、対象ツリーブロックに含まれる各ＣＵの形状、サイズ、および、対象ツリーブロック内での位置を指定する情報である。
【００６１】
また、量子化パラメータ差分Δｑｐは、対象ツリーブロックにおける量子化パラメータｑｐと、当該対象ツリーブロックの直前に符号化されたツリーブロックにおける量子化パラメータｑｐ’との差分ｑｐ−ｑｐ’である。
【００６２】
（ＣＵレイヤ）
ＣＵレイヤでは、処理対象のＣＵ（以下、対象ＣＵとも称する）を復号するために動画像復号装置１が参照するデータの集合が規定されている。
【００６３】
ここで、ＣＵ情報ＣＵに含まれるデータの具体的な内容の説明をする前に、ＣＵに含まれるデータの木構造について説明する。符号化ノードは、予測ツリー（prediction tree；ＰＴ）および変換ツリー（transform tree；ＴＴ）のルートのノードとなる。予測ツリーおよび変換ツリーについて説明すると次のとおりである。
【００６４】
予測ツリーにおいては、符号化ノードが１または複数の予測ブロックに分割され、各予測ブロックの位置とサイズとが規定される。
【００６５】
予測処理は、この予測ブロックごとに行われる。以下、予測の単位である予測ブロックのことを、予測単位（prediction unit；ＰＵ）とも称する。
【００６６】
予測ツリーにおける分割の種類は、イントラ予測と、インター予測との２つがある。イントラ予測の場合、分割方法は、２Ｎ×２Ｎ（符号化ノードと同一サイズ）と、Ｎ×Ｎとがある。インター予測の場合、分割方法は、２Ｎ×２Ｎ（符号化ノードと同一サイズ）、２Ｎ×Ｎ、Ｎ×２Ｎ、および、Ｎ×Ｎがある。
【００６７】
また、変換ツリーにおいては、符号化ノードが１または複数の変換ブロックに分割され、各変換ブロックの位置とサイズとが規定される。
【００６８】
変換処理は、この変換ブロックごとに行われる。以下、変換の単位である変換ブロックのことを、変換単位（transform unit；ＴＵ）とも称する。
【００６９】
（ＣＵ情報のデータ構造）
続いて、図４の（ｅ）を参照しながらＣＵ情報ＣＵに含まれるデータの具体的な内容について説明する。図４の（ｅ）に示すように、ＣＵ情報ＣＵは、具体的には、スキップフラグＳＫＩＰ、ＰＴ情報ＰＴＩ、および、ＴＴ情報ＴＴＩを含む。
【００７０】
スキップフラグＳＫＩＰは、対象のＰＵについて、スキップモードが適用されているか否かを示すフラグであり、スキップフラグＳＫＩＰの値が１の場合、すなわち、対象ＣＵにスキップモードが適用されている場合、そのＣＵ情報ＣＵにおけるＰＴ情報ＰＴＩ、および、ＴＴ情報ＴＴＩは省略される。
【００７１】
ＰＴ情報ＰＴＩは、ＣＵに含まれるＰＴに関する情報である。ＰＴ情報ＰＴＩは、図４の（ｄ）に示すように、予測タイプ情報ＰＴｙｐｅ、および、予測情報ＰＩｎｆｏを含んでいる。
【００７２】
予測タイプ情報ＰＴｙｐｅ（又は、CuPredMode）は、イントラ予測を用いるのか、または、インター予測を用いるのかを指定する情報である。例えば、イントラ予測を用いる場合には、予測タイプ情報CuPredModeは、イントラ予測を示すMODE_INTRAに設定され、インター予測を用いる場合には、インター予測を示すMODE_INTERに設定される。イントラ予測を適用するＣＵをイントラＣＵと呼び、インターＣＵを適用するＣＵをインターＣＵとも呼ぶ。
【００７３】
予測情報ＰＩｎｆｏは、予測タイプ情報ＰＴｙｐｅが何れの予測方法を指定するのかに応じて、イントラ予測情報、または、インター予測情報より構成される。以下では、イントラ予測が適用されるＰＵをイントラＰＵとも呼称し、インター予測が適用されるＰＵをインターＰＵとも呼称する。
【００７４】
また、予測情報ＰＩｎｆｏは、対象ＰＵの形状、サイズ、および、位置を指定する情報が含まれる。上述のとおり予測画像の生成は、ＰＵを単位として行われる。予測情報ＰＩｎｆｏの詳細については後述する。
【００７５】
ＴＴ情報ＴＴＩは、ＣＵに含まれるＴＴに関する情報である。言い換えれば、ＴＴ情報ＴＴＩは、ＴＴに含まれる１または複数のＴＵそれぞれに関する情報の集合であり、動画像復号装置１により残差データを復号する際に参照される。なお、以下、ＴＵのことを変換ブロックと称することもある。
【００７６】
ＴＴ情報ＴＴＩは、図４の（ｄ）に示すように、対象ＣＵの各変換ブロックへの分割パターンを指定するＴＴ分割情報ＳＰ＿ＴＵ、および、ＴＵ情報ＴＵＩ1〜ＴＵＩNT（ＮＴは、対象ＣＵに含まれる変換ブロックの総数）を含んでいる。
【００７７】
ＴＴ分割情報ＳＰ＿ＴＵは、具体的には、対象ＣＵに含まれる各ＴＵの形状、サイズ、および、対象ＣＵ内での位置を決定するための情報である。例えば、ＴＴ分割情報ＳＰ＿ＴＵは、対象となるノードの分割を行うのか否かを示す情報（split_transform_unit_flag）と、その分割の深度を示す情報（trafoDepth）とから実現することができる。
【００７８】
また、ＴＵ分割情報ＳＰ＿ＴＵには、各ＴＵに非ゼロの変換係数が存在するか否かの情報が含まれる。例えば、個々のＴＵに対する非ゼロ係数の存否情報（CBF；Coded Block Flag）がり、色空間毎に、輝度lumaに関するCBFをcbf_luma、色差Cbに関するCBFをcbf_cb、色差Crに関するCBFをcbf_crと称する。また、複数のＴＵに対する非ゼロ係数の存否情報（rqt_root_flag, 又はno_residual_data_flagとも称する）がＴＵ分割情報ＳＰ＿ＴＵに含まれる。また、各ＴＵに対する非ゼロの変換係数を符号化する代わりに、ＴＵにおいて、１又は複数の領域毎に、予測残差の平均(DC)値を表わす予測残差ＤＣ情報（ＤＣオフセット情報）を符号化する(領域別DC符号化を行う)か否かを示すSDCフラグsdc_flagが含まれる。なお、領域別DC符号化は、Segment-wise DC Coding (SDC)とも呼ばれる。特に、イントラ予測における領域別ＤＣ符号化を、イントラＳＤＣと呼び、インター予測における領域別ＤＣ符号化をインターＳＤＣと呼ぶ。なお、領域別ＤＣ符号化が適用される場合、ＣＵサイズ、ＰＵサイズ、及びＴＵサイズは等しくてもよい。
【００７９】
ＴＵ情報ＴＵＩ1〜ＴＵＩNTは、ＴＴに含まれる１または複数のＴＵそれぞれに関する個別の情報である。例えば、ＴＵ情報ＴＵＩは、量子化予測残差を含んでいる。
【００８０】
各量子化予測残差は、動画像符号化装置２が以下の処理Ａ、又は処理Ｂを、処理対象のブロックである対象ブロックに施すことによって生成した符号化データである。
【００８１】
（処理Ａ：周波数変換・量子化を実施する場合）
処理Ａ−１：符号化対象画像から予測画像を減算した予測残差をＤＣＴ変換（Discrete Cosine Transform）する；
処理Ａ−２：処理Ａ−１にて得られた変換係数を量子化する；
処理Ａ−３：処理Ａ−２にて量子化された変換係数を可変長符号化する；
なお、上述した量子化パラメータｑｐは、動画像符号化装置２が変換係数を量子化する際に用いた量子化ステップＱＰの大きさを表す（ＱＰ＝２qp/6）。
【００８２】
（処理Ｂ：領域別DC符号化の場合（SDC; Segment-wise DC Coding））
処理Ｂ−１：符号化対象画像から予測画像を減算した予測残差の平均値（ＤＣ値）を算出する。
【００８３】
処理Ｂ−２：処理Ｂ−１にて得られたＤＣ値を可変長符号化する。
【００８４】
特に、領域別にＤＣ値を符号化することを、領域別ＤＣ符号化（SDC; Segment-Wise DC Coding）と呼び、平坦な領域の予測残差の符号化に有効である。例えば、デプスマップの符号化において、各デプスブロックにおいて、１又は複数に分割された領域の予測残差の符号化に利用される。
【００８５】
（予測情報ＰＩｎｆｏ）
上述のとおり、予測情報ＰＩｎｆｏには、インター予測情報およびイントラ予測情報の２種類がある。
【００８６】
インター予測情報には、動画像復号装置１が、インター予測によってインター予測画像を生成する際に参照される符号化パラメータが含まれる。より具体的には、インター予測情報には、対象ＣＵの各インターＰＵへの分割パターンを指定するインターＰＵ分割情報、および、各インターＰＵについてのインター予測パラメータが含まれる。
【００８７】
インター予測パラメータには、参照画像インデックスと、推定動きベクトルインデックスと、動きベクトル残差とが含まれる。
【００８８】
一方、イントラ予測情報には、動画像復号装置１が、イントラ予測によってイントラ予測画像を生成する際に参照される符号化パラメータが含まれる。より具体的には、イントラ予測情報には、対象ＣＵの各イントラＰＵへの分割パターンを指定するイントラＰＵ分割情報、および、各イントラＰＵについてのイントラ予測パラメータが含まれる。イントラ予測パラメータは、各イントラＰＵについてのイントラ予測（予測モード）を復元するためのパラメータである。
【００８９】
デプスマップDepthPic、及びテクスチャTexturePicの符号化で共通に利用されるイントラ予測（DC予測、Planar予測、Angular予測）に関するパラメータ（イントラ予測パラメータ）には、ＭＰＭ（Most Probable Mode、以下同様）に関するフラグであるmpm_flag、ＭＰＭを選択するためのインデックスであるmpm_idx、および、ＭＰＭ以外の予測モードを指定するためのインデックス（残余予測モードインデックス）であるrem_idxが含まれる。なお、mpm_flagおよびrem_idxは、それぞれ、非特許文献１における“prev_intra_luma_pred_flag”(図５(a)のSYN02)および“rem_intra_luma_pred_mode”(図５(a)のSYN03)に対応している。また、chroma_modeは、“intra_chroma_pred_mode”(不図示)に対応している。
【００９０】
デプスマップの符号化に利用されるデプスイントラ予測(DMM予測)に関する予測モード（イントラ拡張モード(図５(a)のSYN01)）を復元するためのパラメータ（デプスイントラ予測パラメータ, ＤＭＭ予測モード情報）には、デプスイントラ予測の有無を示すフラグ（デプスイントラ予測有無フラグ）dim_not_present_flag（図５(b)のSYN01A）、及びDMM1予測において、PU内の分割パターンを表わすウェッジパターンを指定するインデックス(ウェッジパターンインデックス)wedge_full_tab_idex(図５(b)のSYN01C)がある。
【００９１】
また、イントラＳＤＣや、インターＳＤＣ、及びデプスイントラ予測に関する予測パラメータには、さらに、ＰＵ内の分割された１又は２つの領域のデプス予測値を補正するためのＤＣオフセット情報、すなわち、ＤＣオフセット有無フラグdepth_dc_flag(図６のSYND1)、ＤＣオフセット値の絶対値を示すdepth_dc_abs(図６のSYND02)、及びＤＣオフセット値の符号を示すdepth_dc_sign_flag(図６のSYND03)がある。
〔動画像復号装置〕
以下では、本実施形態に係る動画像復号装置１の構成について、図１〜図２８を参照して説明する。
【００９２】
（動画像復号装置の概要）
動画像復号装置１は、ＰＵ毎に予測画像を生成し、生成された予測画像と、符号化データ＃１から復号された予測残差とを加算することによって復号画像＃２を生成し、生成された復号画像＃２を外部に出力する。
【００９３】
ここで、予測画像の生成は、符号化データ＃１を復号することによって得られる符号化パラメータを参照して行われる。符号化パラメータとは、予測画像を生成するために参照されるパラメータのことである。符号化パラメータには、インター予測において参照される動きベクトルやイントラ予測において参照される予測モードなどの予測パラメータに加えて、ＰＵのサイズや形状、ブロックのサイズや形状、および、原画像と予測画像との残差データなどが含まれる。以下では、符号化パラメータに含まれる情報のうち、上記残差データを除く全ての情報の集合を、サイド情報と呼ぶ。
【００９４】
また、以下では、復号の対象となるピクチャ（フレーム）、スライス、ツリーブロック、ＣＵ、ブロック、および、ＰＵをそれぞれ、対象ピクチャ、対象スライス、対象ツリーブロック、対象ＣＵ、対象ブロック、および、対象ＰＵと呼ぶことにする。
【００９５】
なお、ツリーブロックのサイズは、例えば６４×６４画素であり、ＣＵのサイズは、例えば、６４×６４画素、３２×３２画素、１６×１６画素、８×８画素であり、ＰＵのサイズは、例えば、６４×６４画素、３２×３２画素、１６×１６画素、８×８画素や４×４画素などである。しかしながら、これらのサイズは、単なる例示であり、ツリーブロック、ＣＵ、および、ＰＵのサイズは以上に示したサイズ以外のサイズであってもよい。
【００９６】
（動画像復号装置の構成）
再び、図３を参照して、動画像復号装置１の概略的構成について説明すると次のとおりである。図３は、動画像復号装置１の概略的構成について示した機能ブロック図である。
【００９７】
図３に示すように動画像復号装置１は、可変長復号部１１、逆量子化・逆変換部１３、予測画像生成部１４、加算器１５およびフレームメモリ１６を備えている。
【００９８】
［可変長復号部］
可変長復号部１１は、動画像復号装置１から入力された符号化データ＃１に含まれる各種のパラメータを復号する。以下の説明では、可変長復号部１１が、ＣＡＢＡＣ等のエントロピー符号化方式により符号化されているパラメータの復号を適宜行うものとする。可変長復号部１１は、具体的には、以下の手順により、１フレーム分の符号化データ＃１を復号する。
【００９９】
まず、可変長復号部１１は、１フレーム分の符号化データ＃１を、逆多重化することで、図４に示した階層構造に含まれる各種情報に分離する。例えば、可変長復号部１１は、各種ヘッダに含まれる情報を参照して、符号化データ＃１を、スライス、ツリーブロックに順次分離する。
【０１００】
ここで、各種ヘッダには、（１）対象ピクチャのスライスへの分割方法についての情報、および（２）対象スライスに属するツリーブロックのサイズ、形状および対象スライス内での位置についての情報が含まれる。
【０１０１】
そして、可変長復号部１１は、ツリーブロックヘッダＴＢＬＫＨに含まれるツリーブロック分割情報ＳＰ＿ＴＢＬＫを参照して、対象ツリーブロックを、ＣＵに分割する。また、可変長復号部１１は、対象ＣＵについて得られる変換ツリーに関するＴＴ情報ＴＴＩ、および、対象ＣＵについて得られる予測ツリーに関するＰＴ情報ＰＴＩを復号する。
【０１０２】
可変長復号部１１は、対象ＣＵについて得られたＴＴ情報ＴＴＩをＴＵ情報復号部１２に供給する。また、可変長復号部１１は、対象ＣＵについて得られたＰＴ情報ＰＴＩを予測画像生成部１４に供給する。なお、ＴＴ情報ＴＴＩには、上述のとおり、変換ツリーに含まれるＴＵに対応するＴＵ情報ＴＵＩが含まれる。また、ＰＴ情報ＰＴＩには、上述のとおり、対象予測ツリーに含まれる各ＰＵに対応するＰＵ情報ＰＵＩ（各ＰＵの予測情報Ｐｉｎfｏ）が含まれる。
【０１０３】
以下では、本発明に関連の深いイントラＰＵの予測情報Ｐｉｎｆｏに含まれるイントラ予測パラメータ、及び領域別ＤＣ符号化(イントラＳＤＣ、インターＳＤＣ)やデプスイントラ予測に利用されるＤＣオフセット情報の復号処理の概略について説明する。
【０１０４】
（イントラ予測パラメータ）
可変長復号部１１は、図５のSYN01に示すイントラ予測モード拡張intra_mode_ext()のシンタックステーブルに従って、符号化データ＃１より各シンタックスを復号する。なお、復号対象レイヤにおいて、デプス符号化ツールにおいてＤＭＭ１予測の可否を示すフラグ（DMM1予測モード可否フラグ）intra_sdc_dmm_wfull_flagが１、の場合、イントラ予測モード拡張intra_mode_ext()が復号される。なお、DMM1予測モード可否フラグintra_sdc_dmm_wfull_flagは、１の場合、デプス符号化ツールであるDMM1予測モードが復号対象レイヤにおいて適用されうることを示し、０の場合は、適用されないことを示す。また、ＤＭＭ１予測モード可否フラグは、パラメータセット（ビデオパラメータセットVPS、シーケンスパラメータセットSPS、ピクチャパラメータセットPPS、スライスヘッダSH）等から復号される。
【０１０５】
まず、可変長復号部１１は、対象ＰＵサイズが３２×３２以下の場合（logPbSize<6）、デプスイントラ予測有無フラグdim_not_present_flag(図５(b)のSYN01A)を復号する。対象ＰＵサイズが３２×３２より大きい場合には、該フラグの値を１と推定する。該フラグは、デプスイントラ予測の有無を示すフラグであり、該フラグの値が１の場合、対象ＰＵに関するデプスイントラ予測モードフラグdepth_intra_mode_flagが符号化データ中になく、イントラ予測モード番号‘０’〜‘３４’（DC予測、Planar予測、Angular予測）のいずれかのイントラ予測方式が対象ＰＵに利用されることを示す。また、該フラグが０の場合は、デプスイントラ予測モードdepth_intra_mode_flagが符号化データ中にあることを示す。
【０１０６】
また、可変長復号部１１は、復号したデプスイントラ予測有無フラグdim_not_present_flagに基づいて、対象ＰＵのＤＭＭフラグDmmFlagを下記式により導出する。
【０１０７】
DmmFlag = !dim_not_present_flag
すなわち、ＤＭＭフラグには、デプスイントラ予測有無フラグの論理否定の値が設定される。ＤＭＭフラグは１の場合、デプスイントラ予測が利用されることを示し、ＤＭＭフラグが０の場合、デプスイントラ予測が利用されないことを示す。
【０１０８】
（デプスイントラ予測有無フラグが１の場合）
可変長復号部１１は、デプスイントラモードフラグdepth_intra_mode_flagが０の場合、すなわち、デプスイントラ予測がＤＭＭ１予測である場合、予測モードpredModeIntraへ、ＤＭＭ１予測を示す予測モード番号を設定する。さらに、ＰＵ内の分割パターンを示すウェッジパターンを指定するウェッジパターンインデックスwedge_full_tab_idxを復号する。
【０１０９】
（デプスイントラ予測有無フラグが０の場合）
可変長復号部１１は、デプスイントラ予測有無フラグdim_not_present_flagが０場合、対象ＰＵのイントラ予測モードが推定予測モードＭＰＭと一致するか否かを示すＭＰＭフラグmpm_flagを復号する。該フラグが１の場合、対象ＰＵのイントラ予測モードが推定予測モードＭＰＭと一致することを示し、該フラグが０の場合、予測モード番号‘０’〜‘３４’（DC予測、Planar予測、Angular予測のいずれか）の中で、推定予測モードＭＰＭを除くいずれかの予測モードであることを示す。
【０１１０】
可変長復号部１１は、ＭＰＭフラグが１の場合、さらに、推定予測モードＭＰＭを指定するＭＰＭインデックスmpm_idxを復号して、該mpm_idxが示す推定予測モードを、予測モードpredModeIntraへ設定する。
【０１１１】
可変長復号部１１は、ＭＰＭフラグが０の場合、さらに、ＭＰＭ以外の予測モードを指定するためのインデックスrem_idxを復号して、該rem_idxから特定される、推定予測モードＭＰＭを除く予測モード番号‘０’〜‘３４’（DC予測、Planar予測、Angular予測のいずれか）の中でいずれかの予測モード番号を、予測モードpredModeIntraへ設定する。
【０１１２】
（ＤＣオフセット情報）
可変長復号部１１は、さらに、図示しないＤＣオフセット情報復号部１１１を備え、該ＤＣオフセット情報復号部１１１によって、対象ＣＵ内に含まれるＤＣオフセット情報の復号を行う。
【０１１３】
より具体的には、ＤＣオフセット情報復号部１１１は、対象ＣＵ内にＤＣオフセット情報の有無を示すＣＵ内ＤＣオフセット情報有無フラグcuDepthDcPresentFlagを下記式により導出する。
【０１１４】
cuDepthDcPresentFlag = ( sdc_flag || (CuPredMode ==  MODE_INTRA ) )
すなわち、SDCフラグsdc_flagが１、又は、予測タイプ情報CuPredModeがイントラ予測である場合に、該ＣＵ内ＤＣオフセット情報有無フラグは１（真）に設定され、それ以外の場合(SDCフラグが０（偽）、かつ、インター予測の場合)は、０（偽）に設定される。該ＣＵ内ＤＣオフセット情報有無フラグが１の場合、対象ＣＵ内にＤＣオフセット情報が存在しうることを示し、該フラグが０の場合、対象ＣＵ内にＤＣオフセット情報が存在しないことを示す。
【０１１５】
続いて、ＤＣオフセット情報復号部１１１は、ＣＵ内ＤＣオフセット情報有無フラグが１の場合、対象ＣＵ内の各ＰＵ毎に、該ＰＵ内の１又は複数に分割された領域のデプス予測値を補正するためのＤＣオフセット情報を復号する。
【０１１６】
より具体的には、まず、ＤＣオフセット情報復号部１１１は、対象ＰＵに関するＤＣオフセット情報が存在しうるか否かを示すＰＵ内ＤＣオフセット情報有無フラグpuDepthDcPresentFlagを下記式により導出する。
【０１１７】
puDepthDcPresentFlag = ( DmmFlag || sdc_flag )
すなわち、対象ＰＵのＤＭＭフラグが１、又はＳＤＣフラグが１の場合、該ＰＵ内ＤＣオフセット情報有無フラグが１（真）に設定され、それ以外の場合（DmmFlag==0 && sdc_flag==0）は、０（偽）に設定される。該ＰＵ内ＤＣオフセット情報フラグが１の場合、対象ＰＵ内にＤＣオフセット情報が存在しうることを示し、該フラグが０の場合、対象ＰＵ内にＤＣオフセット情報が存在しないことを示す。
【０１１８】
ＤＣオフセット情報復号部１１１は、対象ＰＵの分割領域数dcNumSegを、対象ＰＵのＤＭＭフラグに基づいて、下記式により導出する。
【０１１９】
dcNumSeg = DmmFlag ? 2 : 1
すなわち、ＤＭＭフラグが１の場合には、対象ＰＵの分割領域数dcNumSegを２に設定し、該ＤＭＭフラグが０の場合には、dcNumSegを１に設定する。なお、X ? Y: Zは、Xが真（０以外）の場合Y、偽（０）の場合Zを選択する３項演算子である。
【０１２０】
ＤＣオフセット情報復号部１１１は、ＤＣオフセット情報（ＤＣオフセット情報有無フラグdepth_dc_flag, ＤＣオフセット絶対値depth_dc_abs[i]、ＤＣオフセット符号depth_dc_sign_flag[i]）、及び分割領域数dcNumSegに基づいて、各ＰＵ内の分割領域Ri(i=0..dcNumSeg-1)に対応するＤＣオフセット値DcOffset[i]を下記式により導出する。
【０１２１】
DcOffset[i] = !depth_dc_offset_flag ? 0 : 
( 1 - 2*depth_dc_sign_flag[i] ) * ( depth_dc_abs[i] + dcNumSeg - 2 )
すなわち、ＤＣオフセット情報有無フラグが０の場合、分割領域RiのDCオフセット値DcOffset[i]を０へ設定し、ＤＣオフセット情報有無フラグが１の場合には、depth_dc_sign_flag[i]、depth_dc_abs[i]、分割領域数dcNumSegに基づいて、分割領域RiのDCオフセット値DcOffset[i]を設定する。
【０１２２】
なお、ＤＣオフセット値の導出式は、上記に限定されず、実施可能な範囲で変更可能である。例えば、ＤＣオフセット値は、下記式によって導出してもよい。
【０１２３】
DcOffset[i] = 
( 1 - 2*depth_dc_sign_flag[i] ) * ( depth_dc_abs[i] + dcNumSeg - 2 )
【０１２４】
［逆量子化・逆変換部］
逆量子化・逆変換部１３は、対象ＣＵに含まれる各ブロックについて、ＴＴ情報ＴＴＩに基づいて逆量子化・逆変換処理を実行する。具体的には、逆量子化・逆変換部１３は、各対象ＴＵについて、対象ＴＵに対応するＴＵ情報ＴＵＩに含まれる量子化予測残差を逆量子化および逆直交変換することによって、対象ＴＵに対応する画素毎の予測残差Ｄ（又はresSamples[x][y]）を復元する。なお、ここで直交変換とは、画素領域から周波数領域への直交変換のことを指す。したがって、逆直交変換は、周波数領域から画素領域への変換である。また、逆直交変換の例としては、逆ＤＣＴ変換（Inverse Discrete Cosine Transform）、および逆ＤＳＴ変換（Inverse Discrete Sine Transform）等が挙げられる。逆量子化・逆変換部１３は、復元した予測残差Ｄを加算器１５に供給する。なお、逆量子化・逆変換部１３は、ＳＤＣフラグが１の場合、逆量子化・逆変換処理を省略し、対象ＴＵの画素毎の予測残差Ｄ（又はresSamples[x][y]）を０へ設定し、加算器１５に供給する。
【０１２５】
［予測画像生成部］
予測画像生成部１４は、対象ＣＵに含まれる各ＰＵについて、ＰＴ情報ＰＴＩに基づいて予測画像を生成する。具体的には、予測画像生成部１４は、各対象ＰＵについて、対象ＰＵに対応するＰＵ情報ＰＵＩ（予測情報Ｐｉｎｆｏ）に含まれるパラメータに従ってイントラ予測またはインター予測を行うことにより、復号済み画像である局所復号画像Ｐ’から予測画像Ｐｒｅｄを生成する。予測画像生成部１４は、生成した予測画像Ｐｒｅｄを加算器１５に供給する。なお、予測画像生成部１４の構成については、後ほど、より詳しく説明する。
【０１２６】
［加算器］
加算器１５は、予測画像生成部１４より供給される予測画像Ｐｒｅｄと、逆量子化・逆変換部１３より供給される予測残差Ｄとを加算することによって、対象ＣＵについての復号画像Ｐを生成する。
【０１２７】
［フレームメモリ］
フレームメモリ１６には、復号された復号画像Ｐが順次記録される。フレームメモリ１６には、対象ツリーブロックを復号する時点において、当該対象ツリーブロックよりも先に復号された全てのツリーブロック（例えば、ラスタスキャン順で先行する全てのツリーブロック）に対応する復号画像が記録されている。
【０１２８】
また、対象ＣＵを復号する時点において、当該対象ＣＵよりも先に復号された全てのＣＵに対応する復号画像が記録されている。
【０１２９】
なお、動画像復号装置１において、画像内の全てのツリーブロックに対して、ツリーブロック単位の復号画像生成処理が終わった時点で、動画像復号装置１に入力された１フレーム分の符号化データ＃１に対応する復号画像＃２が外部に出力される。
【０１３０】
（予測モードの定義）
前述の通り、予測画像生成部１４は、ＰＴ情報ＰＴＩに基づいて予測画像を生成して出力する。対象ＣＵがインターＣＵの場合、予測画像生成部１４に入力されるＰＵ情報ＰＴＩは、例えば、動きベクトルmvLX(X=0,1)、及びフレームメモリ１６に格納された復号済画像を参照画像として指定するための、参照画像インデックスrefIdxLX(X=0,1)、単予測（Ｌ０予測、Ｌ１予測）又は、双方向予測等のインター予測方式を指定するインター予測識別子inter_pred_idxを含む。
【０１３１】
対象ＣＵがイントラＣＵの場合、予測画像生成部１４に入力されるＰＵ情報ＰＴＩは、予測モード（IntraPredMode）と、色差予測モード（IntraPredModeC）を含む。以下、予測モード（輝度・色差）の定義について、図７を参照して説明する。
【０１３２】
（概要）
図７は、動画像復号装置１で利用されるイントラ予測方式の分類と対応する予測モード番号の例を示している。Planar予測（INTRA_PLANAR）に‘０’、ＤＣ予測（INTRA_DC）に‘１’、Angular予測（INTRA_ANGULAR）に‘２’〜 ‘３４’、DMM1予測(INTRA_DMM_WFULL)に‘３５’、DMM4予測（INTRA_DMM_CREDTEX）に‘３６’の予測モード番号がそれぞれ割り当てられている。DMM1予測、及びDMM4予測を総称して、デプスイントラ予測とも呼ぶ。デプスイントラ予測とは、デプスマップ上の対象ブロック（デプスブロックとも称する）が２つの非矩形の平坦領域から構成され、各平坦領域のデプス値は固定値で表現されるというデプスモデルに基づいている。デプスブロックの分割方法として、DMM1と呼ばれる、ウェッジレット分割 (Wedgelet Partition)、及びDMM4とも呼ばれる輪郭分割(Contour Partition)がある。本明細書では、ウェッジレット分割を用いる方法を説明する。
【０１３３】
次に、図８を用いて、Angular予測に含まれる各予測モードの識別子を説明する。図８には方向予測に属する３３種類の予測モードについて、予測モードの識別子と対応する予測方向が図示されている。
【０１３４】
（予測画像生成部の詳細）
次に、図９を用いて予測画像生成部１４の構成についてさらに詳しく説明する。図９は予測画像生成部１４の構成例について示す機能ブロック図である。なお、本構成例は、予測画像生成部１４の機能のうち、イントラＣＵの予測画像生成に係る機能ブロックを図示している。
【０１３５】
図９に示すように、予測画像生成部１４は、予測単位設定部１４１、参照画素設定部１４２、スイッチ１４３、参照画素フィルタ部１４４、および予測画像導出部１４５を備える。
【０１３６】
予測単位設定部１４１は、対象ＣＵに含まれるＰＵを規定の設定順序で対象ＰＵに設定し、対象ＰＵに関する情報（対象ＰＵ情報）を出力する。対象ＰＵ情報には、対象ＰＵのサイズｎＳ、対象ＰＵのＣＵ内の位置、対象ＰＵの輝度または色差プレーンを示すインデックス（輝度色差インデックスcIdx）が少なくとも含まれる。
【０１３７】
スイッチ１４３は、入力される対象ＰＵ情報のうち、輝度色差インデックスcIdx、および予測モードpredModeIntraとに基づいて、参照画素を対応する出力先へ出力する。より具体的には、輝度色差インデックスcIdxが０であり（処理対象の画素が輝度である）、かつ、予測モードpredModeIntraが、０〜３４である（予測モードが、Planar予測、又は、DC予測、又は、Angular予測である（predModeIntra<35））とき、スイッチ１４３は、入力される参照画素を、参照画素フィルタ部１４４へ出力する。それ以外の場合、すなわち、輝度色差インデックスcIdxが１である（処理対象の画素が色差である）、又は、予測モードpredModeIntraが、予測モード番号‘３５’に割り当てられたデプスイントラ予測である(predModeIntra>=35)とき、スイッチ１４３は、入力される参照画素を、予測画像導出部１４５へ出力する。
【０１３８】
参照画素フィルタ部１４４は、入力される参照画素値にフィルタを適用して、フィルタ適用後の参照画素値を出力する。具体的には、参照画素フィルタ部１４４は、フィルタの適用有無を、対象ＰＵサイズと予測モードpredModeIntraとに応じて決定する。
【０１３９】
予測画像導出部１４５は、入力されるＰＵ情報（予測モードpredModeIntra、輝度色差インデックスcIdx、ＰＵサイズｎＳ）と参照画素ｐ[x][y]に基づいて対象ＰＵの予測画像predSamplesを生成して出力する。予測画像導出部１４５の詳細な説明は後述する。
【０１４０】
（予測画像生成処理の流れ）
次に、予測画像生成部１４におけるＣＵ単位の予測画像生成処理の概略を図１０のフローチャートを用いて説明する。ＣＵ単位の予測画像生成処理が始まると、まず、予測単位設定部１４１がＣＵ内に含まれるＰＵの一つを既定の順序に従って対象ＰＵに設定して対象ＰＵ情報を参照画素設定部１４２およびスイッチ１４３に出力する（Ｓ１１）。次に、参照画素設定部１４２は対象ＰＵの参照画素を、外部のフレームメモリから読み出した復号画素値を用いて設定する（Ｓ１２）。次に、スイッチ１４３が、入力された対象ＰＵ情報に基づいて対象ＰＵが輝度か色差か、又は予測モードpredModeIntraがＤＭＭ予測であるか否かを判定し、当該判定結果に応じて出力を切り替える（Ｓ１３）。
【０１４１】
対象ＰＵが輝度であり、かつ、予測モードpredModeIntraがデプスイントラ予測でない場合（cIdx==0 && predModeIntra<35）（Ｓ１３でＹＥＳ）、スイッチ１４３の出力は参照画素フィルタ部１４４に接続される。続いて、参照画素フィルタ部１４４に対し参照画素が入力され、別途入力された予測モードに応じて参照画素フィルタが適用され、フィルタ適用後の参照画素が予測画像導出部１４５に出力される（Ｓ１４）。
【０１４２】
一方、対象ＰＵが色差である、又は、予測モードpredModeIntraがデプスイントラ予測である場合(cIdx==1 || predModeIntra>=35)（Ｓ１３でＮＯ）、スイッチ１４３の出力は予測画像導出部１４５に接続される。
【０１４３】
次に、予測画像導出部１４５は、入力されるＰＵ情報（予測モードpredModeIntra、輝度色差インデックスcIdx、ＰＵサイズｎＳ）と参照画素p[x][y]に基づいて対象ＰＵにおける予測画像predSamplesを生成して出力する（Ｓ１５）。
【０１４４】
対象ＰＵの輝度または色差の予測画像の生成が終わると、予測単位設定部１４１が、対象ＣＵ内の全てのＰＵの予測画像が生成されたかを判定する（Ｓ１６）。対象ＣＵ内の一部のＰＵの予測画像が生成されていない場合（Ｓ１６でＮＯ）、上記Ｓ１に戻り、対象ＣＵ内の次のＰＵの予測画像生成処理を実行する。対象ＣＵ内の全てのＰＵの予測画像が生成されている場合（Ｓ１６でＹＥＳ）、対象ＣＵ内の各ＰＵの輝度および色差の予測画像を合わせて対象ＣＵの予測画像として出力し、処理を終了する。
【０１４５】
（予測画像導出部１４５の詳細）
続いて、予測画像導出部１４５の詳細について説明する。図９に示すように、予測画像導出部１４５は、さらに、DC予測部１４５Ｄ、Planar予測部１４５Ｐ、Angular予測部１４５Ａ、及びDMM予測部１４５Ｔを備える。
【０１４６】
予測画像導出部１４５は、入力される予測モードpredModeIntraに基づいて予測画像生成に用いる予測方式を選択する。予測方式の選択は、前述の図７の定義に基づいて、入力される予測モードpredModeIntraの予測モード番号に対応する予測方式を選択することで実現される。
【０１４７】
さらに、予測画像導出部１４５は、予測方式の選択結果に応じた予測画像を導出する。より具体的には、予測画像導出部１４５は、予測方式が、Planar予測、DC予測、Angular予測、及びDMM予測の場合、それぞれ、Planar予測部１４５Ｐ、DC予測部１４５Ｄ、Angular予測部１４５Ａ、及びDMM予測部１４５Ｔにより予測画像を導出する。
【０１４８】
DC予測部１４５Ｄは、入力される参照画素の画素値の平均値に相当するDC予測値を導出し、導出されたDC予測値を画素値とする予測画像を出力する。
【０１４９】
Planar予測部１４５Ｐは、予測対象画素との距離に応じて複数の参照画素を線形加算することで導出した画素値により予測画像を生成して出力する。
【０１５０】
[Angular予測部１４５Ａ]
Angular予測部１４５Ａは、入力される予測モードpredModeIntraに対応する予測方向（参照方向）の参照画素を用いて対象ＰＵ内に対応する予測画像を生成して出力する。Angular予測による予測画像の生成処理では、予測モードpredModeIntraの値に応じて主参照画素を設定し、予測画像をＰＵ内のラインまたはコラムの単位で主参照画素を参照して生成する。
【０１５１】
[DMM予測部１４５Ｔ]
DMM予測部１４５Ｔは、入力される予測モードpredModeIntraに対応するDMM予測(Depth Modeling Mode,デプスイントラ予測ともいう)に基づいて、対象ＰＵ内に対応する予測画像を生成して出力する。
【０１５２】
DMM予測部１４５Ｔの詳細な説明に先だって、図１１を参照しながら、DMM予測の概略について説明する。図１１は、DMM予測部１４５Ｔにおいて実行されるDMM予測の概念図である。デプスマップは、主に、図１１(a)に示すように、オブジェクト境界を表わすエッジ領域、及びオブジェクトエリアを表わす平坦領域（ほぼデプス値が一定）を有するという特徴がある。まず、DMM予測では、基本的に、デプスマップの画像的特徴を利用し、対象ブロックを、オブジェクトのエッジに沿った２つの領域Ｐ１、Ｐ２に分割し、図１１ (b)に示すように、各画素が属する領域を表わすパターン情報であるウェッジパターンWedgePattern[x][y]を導出する。
【０１５３】
ウェッジパターン（ウェッジレットパターン）WedgePattern[x][y]は、対象ブロック（対象ＰＵ）の幅×高さ分の大きさがあるマトリックスであり、要素(x,y)毎に０、又は１が設定され、対象ブロックの各画素が２つの領域P1、P2のどちらに属するかを示す。図１１ (b)の例では、要素の値が０であれば、領域Ｐ１に属し、１であれば、領域Ｐ２に属すこととなる。次に、図１１ (c)に示すように、各領域Ｐ１、及びＰ２を各々のデプス予測値を埋めることによって予測画像を生成する。
【０１５４】
以下、ウェッジレットと呼ばれる線分により分割されたウェッジパターンを便宜的にウェッジレットパターンと呼ぶが、ウェッジパターン、ウェッジレットパターンも同じもの（２つの領域に分割された２次元パターン）であるため、特に区別しなくても良い。なお、ウェッジパターン（ウェッジレットパターン）を単にパターンとも呼ぶ。
【０１５５】
以下では、図１を参照しがら、DMM予測部１４５Ｔの構成について説明する。図１は、DMM予測部１４５Ｔの構成例のついて示す機能ブロック図である。
【０１５６】
図１に示すように、DMM予測部１４５Ｔは、ウェッジパターン導出部１４５Ｔ２、及びＤＣ予測値導出部１４５Ｔ３を備える。
【０１５７】
DMM予測部１４５Ｔは、入力される予測モードpredModeIntraに対応するウェッジパターン生成手段を起動させ、対象ＰＵの分割パターンを示すウェッジパターンwedgePattern[x][y]を生成する。より具体的には、予測モードpredModeIntraが、予測モード番号‘３５’である場合、すなわち、INTRA_DMM_WEDGEFULLモードでは、ウェッジパターン導出部１４５Ｔ２を起動する。一方、予測モードpredModeIntraが、予測モード番号‘３６’である場合、すなわち、INTRA_DMM_CPCREDTEXモードでは、を起動する。
【０１５８】
[ウェッジパターン導出部１４５Ｔ２]
ウェッジパターン導出部１４５Ｔ２は、入力される対象ＰＵサイズｎＳ、ウェッジパターンインデックスwedge_full_tab_idx、予め設定された参照ウェッジパターンサイズｎＢＳ、及び参照ウェッジパターン数NumWedgePattern[log2(nS)]に基づいて、ウェッジパターンテーブル１４５Ｔ５に格納されたウェッジパターンテーブルの配列WedgePatternTable[][x][y]から、対象ＰＵへ適用するウェッジパターンwedgePattern[x][y]を導出し、ＤＣ予測値導出部１４５Ｔ３へ出力する。
【０１５９】
wedgePattern[x][y] = WedgePatternTable[log2(nS)][wedge_full_tab_idx][x][y],
with x = 0..nS-1, y = 0..nS-1
ここで、log2(nS)は、対象ＰＵサイズ(nS)の２を底とする対数値でありlog2BlkSize（=log2(nS)）とも表現する。nS=4、8、16、32、64に対して、log2(nS)は2,3,4,5,6となる。
【０１６０】
[DC予測値導出部１４５Ｔ３]
DC予測値導出部１４５Ｔ３は、対象ＰＵの分割パターンを示すウェッジパターンwedgePattern[x][y]に基づいて、対象ＰＵを2つの領域に分割し(例えば、図１ (c)に示す領域P1、P2)、入力されたＰＴ情報、及び参照画素p[x][y]に基づいて領域P1に関する予測値、及び領域P2に関する予測値を導出し、各領域に導出した予測値を予測画像predSamples[x][y]に設定して導出する。
【０１６１】
[ウェッジレットパターン生成部１４５Ｔ４]
ウェッジパターン導出部１４５Ｔ２は、初回起動時のみ、ウェッジレットパターン生成部１４５Ｔ４を起動させ、ブロックサイズnS毎の複数のウェッジパターンを生成する。次に、生成したウェッジパターンをウェッジパターンテーブル１４５Ｔ５に格納する。
【０１６２】
ウェッジレットパターン生成部１４５Ｔ４におけるウェッジパターンテーブルの生成方法の説明に先だって、ウェッジレットパターンの生成方法の概要について、図１２を参照して説明する。まず、全要素が０のウェッジレットパターンを生成する。次に、ウェッジレットパターン内に、始点S(xS,yS)と終点E(xE,yE)を設定する。始点と終点は、パターンを構成する四角形の辺上に設定される。図１２の（ａ）の例では、始点S(xS,yS)=(3,patternSize -1)、終点E(xE,yE)=(patternSize -1,2)である。次に、始点Sと終点Eの間をBresenhamのアルゴリズムを用いて線分を引く（図１２ (b)の斜線の要素）。図１２ (c)の例では、続いて、図１２（ｄ）に示すように、例えば、その線分上及び線分より左側の座標に対応する要素を１に設定することで、ウェッジレットパターンwedgePattern[x][y]が生成される。ここで、patternSize は、ウェッジレットパターンを生成するブロックのサイズ（縦幅、横幅）である。
【０１６３】
以下では、ウェッジレットパターン生成部１４５Ｔ４におけるウェッジパターンテーブルの生成方法について説明する。ウェッジレットパターン生成部１４５Ｔ４では、図１３に示すように、主に、６種類のウェッジ方向wedgeOri(wedgeOri=0..5)のウェッジレットパターンをブロックサイズnS別に生成する。一つのウェッジ方向wedgeOri(wedgeOri=0..5)において、始点と終点の位置をずらしながら複数のウェッジパターン（ウェッジパターンのセット）を生成する。
【０１６４】
図１３(a)は、始点がブロックの上辺の線分Ｓ上の点、終点がブロックの左辺の線分Ｅ上の点を選択して得られる２点を結ぶ線分で分割される２つの領域から構成されるウェッジ方向wedgeOri=0のウェッジレットパターンである。
【０１６５】
図１３(ｂ)は、始点がブロックの右辺の線分Ｓ上の点、終点がブロックの上辺の線分Ｅ上の点を選択して得られる２点を結ぶ線分で分割される２つの領域から構成されるウェッジ方向wedgeOri=1のウェッジレットパターンである。
【０１６６】
図１３(ｃ)は、始点がブロックの下辺の線分Ｓ上の点、終点がブロックの右辺の線分Ｅ上の点を選択して得られる２点を結ぶ線分で分割される２つの領域から構成されるウェッジ方向wedgeOri=2のウェッジレットパターンである。
【０１６７】
図１３(ｄ)は、始点がブロックの左辺の線分Ｓ上の点、終点がブロックの下辺の線分Ｅ上の点を選択して得られる２点を結ぶ線分で分割される２つの領域から構成されるウェッジ方向wedgeOri=3のウェッジレットパターンである。
【０１６８】
図１３(ｅ)は、始点がブロックの上辺の線分Ｓ上の点、終点がブロックの下辺の線分Ｅ上の点を選択して得られる２点を結ぶ線分で分割される２つの領域から構成されるウェッジ方向wedgeOri=4のウェッジレットパターンである。
【０１６９】
図１３(ｆ)は、始点がブロックの左辺の線分Ｓ上の点、終点がブロックの右辺の線分Ｅ上の点を選択して得られる２点を結ぶ線分で分割される２つの領域から構成されるウェッジ方向wedgeOri=5のウェッジレットパターンである。
【０１７０】
本実施形態では、図１３(a)に示すウェッジ方向wedgeOri=0のウェッジレットパターンを第１の基本パターンと呼び、図１３(ｂ)に示すウェッジ方向wedgeOri=1〜3のウェッジレットパターンを、ウェッジ方向wedgeOri=0のウェッジレットパターンの回転により生成する。さらに、図１３(ｅ)に示すウェッジ方向wedgeOri=4のウェッジレットパターンを第２の基本パターンと呼び、図１３(ｆ)に示すウェッジ方向wedgeOri=5のウェッジレットパターンを、ウェッジ方向wedgeOri=4のウェッジレットパターンの回転により生成する。
【０１７１】
図１４は、ウェッジレットパターン生成部１４５Ｔ４の構成を示すブロック図である。ウェッジレットパターン生成部１４５Ｔ４は、基本パターン生成部１４６１、パターン格納部１４６４、回転パターン生成部１５６５から構成され、基本パターン生成部１４６１は、線分描画部１４６２、領域フィル部１４６３から構成される。
【０１７２】
本実施形態のウェッジレットパターン生成部１４５Ｔ４は、全てのウェッジレットパターンを線分描画部１４６２、領域フィル部１４６３を用いた線分描画処理、領域フィル処理により生成するのではなく、一部のウェッジレットパターンは回転パターン生成部１５６５を用いた回転処理により生成する。処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替えることができるため、処理を低減する効果を奏する。
【０１７３】
図１６は、ウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理を示す図である。図に示すように、本実施形態のウェッジレットパターン生成部１４５Ｔ４は、図１６(a)に示す基本パターン生成部１４６１で生成されるウェッジレットパターンのセットである第１基本パターンに含まれるウェッジレットパターンを一つ一つ参照し、図１６（ｂ）、（ｃ）、（ｄ）に示す回転パターン生成部１５６５による回転により、ウェッジレットパターンのセットである第１基本パターン第１回転パターン、第１基本パターン第２回転パターン、第１基本パターン第３回転パターンを生成し、図１６(ｅ)に示す基本パターン生成部１４６１で生成されるウェッジレットパターンのセットである第２基本パターンに含まれるウェッジレットパターンを一つ一つ参照し、図１６（ｆ）に示す回転パターン生成部１５６５による回転によりウェッジレットパターンのセットである第２基本パターン第１回転パターンを生成する。本実施形態では、第１回転パターン、第２回転パターン、第３回転パターンの例として、各々時計回りに90度、180度、270度の例を説明するが、90度単位の回転であればこの順によらず、270度、180度、90度などの順でも良い。また、180度、90度、270度の順等でも良い。
【０１７４】
図１７は、ウェッジレットパターン生成部１４５Ｔ４の動作を示すフローチャートである。
【０１７５】
（Ｓ０００１）変数posWedgePatternに０を設定する。
【０１７６】
（Ｓ０００２）ウェッジ方向wedgeOriに関するループの開始。ウェッジ方向wedgeOriに0,1,2,3,4,5を順に設定しＳ０００３からＳ００１４の処理を行う。これにより、ウェッジ方向wedgeOriのウェッジレットパターンのセットを導出する。
【０１７７】
（Ｓ０００３）ウェッジ方向wedgeOriが基本パターンを示す値（ここでは、wedgeOri=0, 4）の場合には、Ｓ０００４に遷移し、線分描画処理と領域フィル処理により、ウェッジ方向wedgeOriの各ウェッジレットパターンを生成する。ウェッジ方向wedgeOriが基本パターンを示す値以外（ここではwedgeOri=1,2,3,5）の場合には、Ｓ００１０に遷移し、回転処理によりウェッジレットパターンを生成する。
【０１７８】
（Ｓ０００４）変数posStartに、基本パターン生成前のウェッジパターン数であるposWedgePatternを設定する。posStart＝posWedgePattern
（Ｓ０００５）始点位置と終点位置を制御する変数m, nに関するループの開始。ループ変数はm, n。以下、m=0.. wBlkSize - 1、n=0.. wBlkSize - 1のm, nに対して、Ｓ０００６からＳ０００８の処理を行う。これにより、ウェッジ方向wedgeOriに対して、始点、終点を変化させながらウェッジレットパターンを生成する。なおwBlkSizeはブロックサイズ（仮想ブロックサイズ）である。
【０１７９】
（Ｓ０００６）線分描画部１４６２が線分を引き、領域フィル部１４６３が領域をフィルすることで、ウェッジ方向wedgeOri、変数m, nで示される始点と終点のウェッジレットパターンを生成する。
【０１８０】
（Ｓ０００７）パターン格納部１４６４は、生成されたウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。より具体的にはパターン格納部１４６４に示す一致判定の条件に合う場合に格納し、格納した場合には、ウェッジパターン数NumWedgePatternを１だけインクリメントする。格納した時点でのウェッジパターン数NumWedgePatternをposWedgePatternに設定する。
【０１８１】
（Ｓ０００８）始点位置と終点位置を制御する変数m, nに関するループの終了。
【０１８２】
（Ｓ０００９）posEndに、基本パターン生成後のウェッジパターン数であるposWedgePattern−１を設定する。posEnd＝posWedgePattern−１
【０１８３】
（Ｓ００１０）参照パターンのインデックスposに関するループの開始。posの範囲はposStartからposEnd。
【０１８４】
（Ｓ００１１）回転パターン生成部１４６５を用いて、posを参照ウェッジレットパターンとして、回転パターンであるウェッジレットパターンを生成する。
【０１８５】
（Ｓ００１２）生成されたウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。より具体的にはパターン格納部１４６４に示す一致判定の条件に合う場合に格納し、格納した場合には、ウェッジパターン数NumWedgePatternを１だけインクリメントする。格納した時点でのウェッジパターン数NumWedgePatternをposWedgePatternに設定する。
【０１８６】
（Ｓ００１３）参照パターンのインデックスposに関するループの終了。
【０１８７】
（Ｓ００１４）ウェッジ方向wedgeOriに関するループの終了。
【０１８８】
以下、ウェッジレットパターン生成部１４５Ｔ４を構成する各手段の動作を説明する。
【０１８９】
（ウェッジレットパターン生成部１４５Ｔ４）
ウェッジレットパターン生成部１４５Ｔ４は、ブロックサイズ（パターンのサイズ）をpatternSize（=nS）として、patternSize×patternSizeのパターンを生成する。本発明では、patternSize×patternSizeのパターンを生成する際に、内部的に、ブロックサイズの１倍もしくは２倍の仮想ブロックサイズwBlkSize を用いてwBlkSize ×wBlkSize のパターンを生成することを仮定する。これにより、より細かい単位でのパターンが生成可能である。ここで、wBlkSize =patternSize<<resShiftを満たす。仮想拡大シフト値resShiftは0もしくは1とする。ここで、パターンサイズは対象パターンの２の対数log2BlkSizeを用いれば、patternSize＝( 1  << log2BlkSize )である。
【０１９０】
ウェッジレットパターン生成部１４５Ｔ４は、ウェッジレートパターンのサイズの対数をlog2BlkSizeに2, 3, 4を設定し、各サイズ(4、8、16)のウェッジレットパターンを生成する。パターンサイズpatternSizeと仮想拡大シフト値resShift、仮想ブロックサイズwBlkSizeを以下の式で導入する。
【０１９１】
resShift = ( log2BlkSize  = =  4 ) ? 0 : 1
patternSize＝( 1  << log2BlkSize ) 
wBlkSize = (patternSize << resShift) = ( 1  << (log2BlkSize + resShift)  )
【０１９２】
ウェッジレットパターン生成部１４５Ｔ４は、変数posWedgePatternに０を設定する（Ｓ０００１）。
【０１９３】
ウェッジレットパターン生成部１４５Ｔ４は、ウェッジ方向wedgeOriを設定（Ｓ０００２）し、各ウェッジ方向wedgeOriに対応する複数のウェッジレットパターン（ウェッジレットパターンのセット）を生成する。具体的には、各ウェッジ方向wedgeOriに0,1,2,3,4,5を用いる。
【０１９４】
ウェッジレットパターン生成部１４５Ｔ４は、ウェッジ方向wedgeOriが0、4の場合に、基本パターン生成部１４６１により、ウェッジレットパターンを生成する（Ｓ０００４〜Ｓ０００９）。ウェッジ方向wedgeOriが1,2,3,5の場合には、回転パターン生成部１４６５により、ウェッジパターンテーブル１４５Ｔに格納されたウェッジレットパターンを読み出し、回転させることにより、ウェッジレットパターンを生成する。生成されたウェッジレットパターンは、パターン格納部１４６４により、ウェッジパターンテーブル１４５Ｔに格納される。サイズlog2BlkSize別のウェッジテーブルの数は配列NumWedgePattern[]に記録される。変数posWedgePatternには、NumWedgePattern[log2BlkSize]が設定される。
【０１９５】
ウェッジレットパターン生成部１４５Ｔ４は、基本パターン導出前に、変数posStartに、その時点のウェッジパターンテーブル１４５Ｔに格納されたウェッジテーブルの数NumWedgePattern[log2BlkSize]であるposWedgePatternを設定する（Ｓ０００４）。
【０１９６】
ウェッジレットパターン生成部１４５Ｔ４は、基本パターン導出後に、変数posEndに、その時点のウェッジパターンテーブル１４５Ｔに格納されたウェッジテーブルの数NumWedgePattern[log2BlkSize]であるposWedgePattern-1を設定する（Ｓ０００９）。
【０１９７】
（基本パターン生成部）
基本パターン生成部１４６１は、第１基本パターン（ここではウェッジ方向wedgeOri=0のウェッジレットパターンのセット）と第２基本パターン（ここではウェッジ方向wedgeOri=4のウェッジレットパターンのセット）を導出する。具体的には、各基本パターンに属する各ウェッジレットパターンの始点と終点を設定し、線分描画部１４６２を用いて線分をウェッジレットパターンに設定し、線分により分割された２つの領域の一方を領域フィル部１４６３により１に設定する（Ｓ０００６）。
【０１９８】
基本パターン生成部１４６１は、ウェッジ方向wedgeOriがwedgeOri=0（第１基本パターンに対応するウェッジ方向）もしくはwedgeOri=4（第２基本パターンに対応するウェッジ方向）の場合に、以下の処理により基本パターン（基本を構成するウェッジレートパターン）を実行する。
【０１９９】
0からwBlkSize - 1の範囲の各値をとる変数m、0からwBlkSize - 1の範囲の各値をとる変数nに設定し、始点(xS, yS、xE、yE)を以下の式により導出する。
【０２００】
xS = m
yS = 0
xE = (wedgeOri==0) ? 0 : n
yE = (wedgeOri==0) ? n : wBlkSize - 1
【０２０１】
基本パターン生成部１４６１は、始点(xS, yS)と終点(xE, yE)を線分描画部１４６２に入力し、線分パターンをcurPatternに生成する。
【０２０２】
基本パターン生成部１４６１は、始点(xS, yS)と終点(xE, yE)を領域フィル部１４６３に入力し、curPatternの領域の一方に１を設定する。
【０２０３】
基本パターン生成部１４６１は、パターン格納部１４６４に生成されたパターンcurPatternを入力する。
【０２０４】
（線分描画部１４６２）
線分描画部１４６２は、ウェッジレットパターンサイズpatternSizeを、refShiftだけ左シフトして得られるサイズpatternSize<< refShiftの拡大ブロック上の始点(xS、yS)と終点(xE、yE)から得られる線分座標(xPos, yPos)を、refShiftだけ右シフトして得られる座標(xPos>> refShift, yPos>> refShift)に１を設定する。線分描画部１４６２は、始点（xS、yS）と終点を（xE、yE）結ぶ線分を以下の擬似コードで示す処理により導出し、パターンcurPattern[][](wedgePattern[][])に出力する。
【０２０５】
x0 = xS
y0 = yS
x1 = xE
y1 = yE
if( abs( yE - yS ) > abs( xE - xS ) ) {
( x0, y0 ) = Swap( x0, y0 )
( x1, y1 ) = Swap( x1, y1 )
}
if( x0 > x1 ) {
( x0, x1 ) = Swap( x0, x1 )
( y0, y1 ) = Swap( y0, y1 )
}
sumErr = 0
posY = y0
for( posX = x0; posX  <=  x1; posX ++ ) {
if( abs( yE - yS ) > abs( xE - xS ) )  
curPattern[ posY>>resShift ][ posX>>resShift ] = 1 
else 
curPattern[ posX>>resShift ][ posY>>resShift ] = 1 
sumErr  +=  ( abs( y1 - y0 )  <<  1 )
if( sumErr  >=  ( x1 - x0 ) ) {
posY  +=  ( y0 < y1 ) ? 1 : --1
sumErr  --=  ( x1 - x0 )  <<  1
}
}
なお、x0、y0、x1、y1は、変換後の始点と終点を示す変数であり、sumErrは増分、posX、posYは、始点(xS, yS)と終点(xE, yE)を結ぶ線上の点を示す座標、Swap(x, y)はxとyを入れ替える処理を示す。curPatternは処理の対象となるウェッジパターンwedgePattern[][]である。
【０２０６】
図２０は、本実施形態の仮想座標（posX、posY）と、パターンとの関係を示す。線分描画部１４６２は始点(xS, yS)と終点(xE, yE)を結ぶ線上の点として仮想座標（posX、posY）を、wBlkSize×wBlkSizeの仮想ブロック上に設定する。線分描画部１４６２は、メモリ上に仮想ブロックを確保し、仮想座標（posX、posY）に１を書きこむのではなく、patternSize×patternSizeのパターンに相当するメモリに、仮想座標を仮想拡大シフト値resShiftだけ右シフトした座標（posY>>resShift 、posX>>resShift ）に１を書きこむ。
【０２０７】
すなわち、線分描画部１４６２では仮想ブロックサイズwBlkSize 上で始点(xS, yS)と終点(xE, yE)を移動させ、仮想座標（posX、posY）の画素を１とする処理を実行することにより、線分描画処理を動作させる特徴を有する。さらに、線分描画部１４６２では、パターンcurPattern[][]に１を代入する際に、仮想座標を仮想拡大シフト値resShiftだけ右シフトすることにより座標（posY>>resShift 、posX>>resShift ）を導出する。このように、仮想拡大シフト値resShiftだけ拡大した座標系で描画処理を行いながら実際に格納する際には、仮想拡大シフト値resShiftだけ右シフトして元の座標に戻すことにより、線分描画処理に用いるメモリサイズを増大させることを防ぐ効果を奏する。すなわち、拡大座標を用いながら、wBlkSize ×wBlkSizeのメモリを必要とせず、patternSize ×patternSizeのメモリで良い。
【０２０８】
（領域フィル部１４６３）
領域フィル部１４６３は、線分描画部１４６２で導出されたパターンcurPatternにおいて、線分で分けられた２つの領域の内、一方の領域を１でフィルする。他方の領域は０のままとする。以下のフィル処理では、左上座標の値を常に１とするように領域のフィルを行う。なお、ウェッジレットパターン生成部１４５Ｔ４の別の構成では、左上座標の値を常に０とするように領域のフィルを行っても良い。
【０２０９】
領域フィル部１４６３は、以下の擬似コードで示す処理によりパターンcurPattern[][]の値を１とすることで領域のフィルを行う。
【０２１０】
for( iY = 0; iY <= yE>> resShift; iY++ ) {
for( iX = 0; iX <= curSize - 1 || curPattern[ iX ][ iY ]  = =  0 ; iX++) 
curPattern[ iX ][ iY ] = 1
}
すなわち、領域フィル部１４６３は、０から終点座標yE>>resShiftにおける垂直成分iYに対して以下の処理を行う。なお、yE>>resShiftは、仮想ブロックでの終点座標yEを、仮想拡大シフト値resShiftで右シフトすることにより導出されるウェッジレットパターン上の座標である。なお、curPatternは処理の対象となるウェッジパターンwedgePattern[][]である。
【０２１１】
領域フィル部１４６３は、0からcurSize - 1の水平成分iXに対して、パターンの値curPattern[ iX ][ iY ]が０である位置を探索しながら、パターンの値curPattern[ iX ][ iY ]が０でない点に対して、curPattern[ iX ][ iY ] = 1により１を設定する。
【０２１２】
上記の領域フィル部１４６３では、終了点yEに関する情報を必要としたが、それらの情報が不要な別の動作を行っても良い。図２１は、領域フィル部１４６３の別の動作を説明する図である。具体的には以下の擬似コードで示す処理によりパターンcurPattern[][]の値を１とすることで領域のフィルを行う。
【０２１３】
for( iY = 0; iY < curSize; iY++ ) {//ループＢ０
// 処理Ｂ１
for( iX = curSize -- 1; iX >= 0 || curPattern[ iX ][ iY ]  = =  0 ; iX- -) {
}
// 処理Ｂ２
for( ; iX >= 0; iX- -) {
curPattern[ iX ][ iY ] = 1
}
}
ここで、curSize＝patternSize。
【０２１４】
領域フィル部１４６３は、０からcurSize-1の垂直成分iYに対して以下の処理を行う（ループＢ０）。領域フィル部１４６３は、curSize - 1から開始する水平成分iXに対して、パターンの値curPattern[ iX ][ iY ]が１である位置を探索する（処理Ｂ１）。すなわち、パターンの値curPattern[ iX ][ iY ]が０である限り、iXの値をひとつずつ減じる。図２１（ａ）では、iX1という点が見つかる。
【０２１５】
続いて、領域フィル部１４６３は、curPattern[ iX ][ iY ]が１である位置が見つかると、iXの値を０になるまで１つずつ減じながら、curPattern[ iX ][ iY ] = 1としてパターンに１を設定する（処理Ｂ２）。図２１（ｂ）では、iX1より０に近い値に対してフィルが行われる。領域フィル部１４６３は、Ｂ０のループで同じ処理を繰り返し、図２１（ｃ）に示す処理Ｂ１を行い、図２１（ｄ）に示す処理Ｂ２を行う。図２１（ｅ）のように処理Ｂ１において、iX1がcurSize−１から０の間で見つからないと処理Ｂ１ではiX=-1となる。この場合、処理Ｂ２では、処理が行われず図２１（ｆ）のように、この列ではフィルは行われない。上記アルゴリズムでは、垂直成分iYがある値である各行において、パターンcurPattern[ iX ][ iY ]が１である画素があってもなくても処理が可能であるという効果を奏する。具体的には、各行においてパターンcurPattern[ iX ][ iY ]が１である画素があれば、その１の画素よりも左の画素を全て１にフィルし、curPattern[ iX ][ iY ]が１である画素がなければ処理を行わない。
【０２１６】
左上座標の値を常に０とするように領域のフィルでは、領域フィル部１４６３は例えば、以下の擬似コードの処理を行う。
【０２１７】
for (y = 0; y < curSize; y++)
{
for (x = curSize - 1; x >= 0 ; x--)
{
if (curPattern [(y * curSize) + x])
break;
curPattern [(y * curSize) + x] = 1;
}
for (; x >= 0 ; x--)
{
curPattern [(y * curSize) + x] = 0;
}
}
【０２１８】
（回転パターン生成部１４６５）
回転パターン生成部１４６５は、ウェッジパターンテーブル１４５Ｔに格納された、基本パターンを１つ１つ読み出し、回転させることで、基本パターンの回転パターンを生成する（図１６（ｂ）に相当）（Ｓ００１０〜Ｓ００１３）。ここでは、図１３(ｂ)に示すウェッジ方向wedgeOri=1のウェッジレットパターンを生成する。具体的には、startPos（ここでは０）からendPosまでのposで指定されるウェッジパターンテーブル１４５Ｔの各WedgePatternTable[ log2BlkSize ][ pos ]を参照パターンrefPattern[][]として、以下の処理により、回転後のパターンwedgePattern[][]を導出する。
【０２１９】
cInc = wedgeOri == 2 ? - 1 : 0; 
sInc = (wedgeOri == 1 ? - 1 : 1) * (1 + cInc) 
iOffset = cInc + sInc < 0 ? patternSize - 1 ? 0
jOffset = -sInc + cInc < 0 ? patternSize - 1 ? 0
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
i = iOffset + cInc * x + sInc * y
j = jOffset - sInc * x + cInc * y
wedgePattern[ x ][ y ] = refPattern [ i ][ j ]       式Ｒ１
}
なお、回転パターン生成部１４６５は、参照パターンrefPattern[][]から対象パターンwedgePattern[][]を生成する場合に、対象パターン上の座標(x, y)を参照パターン上の座標(i, j)に座標変換し、式Ｒ１のように、参照パターン上の座標(i, j)上の画素refPattern [ i ][ j ]を、対象パターン上の座標(x, y)上の画素wedgePattern[ x ][ y ]として用いることで導出する。
【０２２０】
wedgePattern[ x ][ y ] = refPattern [ i ][ j ]      式Ｒ１
なお、i, jは、各々0..patternSizeの範囲の値である。ここで、対象パターン上の座標 (x, y)と参照パターン上の座標(i, j)は、回転行列で座標変換されることとする。すなわち、x = (cosθ)i - (sinθ)j + offsetX、y = (sinθ)i + (cosθ)j + offsetYの関係を満たす。offsetX、offsetYは座標変換後の座標(x, y)が０以上をpatternSize−１以下を満たすように設定されるオフセットである。上記の式では、cIncがcosθ、sIncがsinθに対応し、cInc2+ sInc2= 1を満たす。
【０２２１】
なお、本実施形態の第１回転パターンから第３回転パターンでは、特にθ＝90度（PI /2 rad）、180度（PI rad）、270度（3 PI /2 rad）のいずれかの場合を用いる。ここでPIは、円周率であり、3.141592...の値を有する。よって、回転パターン生成部１４６５は、cIncに0もしくは-1、sIncに1, -1(cIncが0のとき)、0(cInxが-1のとき)のいずれかを設定する。
【０２２２】
なお、回転パターン生成部１４６５は、参照パターンrefPattern[][]から対象パターンwedgePattern[][]を生成する場合に、参照パターン上の座標(i, j)を対象パターン上の座標(x, y)に座標変換し、参照パターン上の座標(i, j)上の画素refPattern [ i ][ j ]を、対象パターン上の座標(x, y)上の画素wedgePattern[ x ][ y ]として用いてもよい。
xOffset = cIncS - sIncS < 0 ? patternSize - 1 ? 0
yOffset = sIncS + cIncS < 0 ? patternSize - 1 ? 0
for( j = 0; j < patternSize; j++ )
for( i = 0; i < patternSize; i++ )  {
x = xOffset+ cInc * i - sInc* j
y = yOffset+ sInc * i + cInc * j
wedgePattern[ x ][ y ] = refPattern[ i ][ j ]
}
【０２２３】
（パターン格納部１４６４）
パターン格納部１４６４は、基本パターン生成部１４６１および回転パターン生成部１４６５で生成されるウェッジレットパターンについて、ウェッジパターンテーブル中に一致する（重複する）ウェッジレットパターンが存在しなければ、wBlksize×wBlksizeのウェッジパターンテーブルWedgePatternTable[log2BlkSize][NumWedgePattern[log2BlkSize]]へ追加する。より具体的には、生成したウェッジレットパターンwedgePattern[x][y]を、下記式によりウェッジパターンテーブルWedgePatternTableの対応する要素へ、値を設定する。
【０２２４】
WedgePatternTable[log2BlkSize][NumWedgePattern[log2BlkSize][x][y] = 
wedgePattern[x][y], with x = 0..wBlkSize-1, y = 0..wBlkSize-1
なお、重複するウェッジレットパターンとは、生成されたウェッジレットパターンと同一の分割パターン、又は、生成されたウェッジレットパターンの各要素値を反転させたウェッジレットパターン(例えば、図１１(b)において、０を１へ、１を０へ置換した分割パターン)と同一の分割パターンである。ここで、wBlksizeとは、ウェッジレットパターンを生成するブロックの幅及び高さのサイズを示し、配列NumWedgePattern[]は、ブロックサイズの対数値(log2BlkSize)を引数とする、ブロックサイズ別のウェッジパターンテーブルに追加されたウェッジレットパターンの個数(ウェッジパターン数)を表わす。ウェッジパターンテーブルへウェッジレットパターンが追加される度に、ウェッジパターン数NumWedgePattern[log2BlkSize]は１加算される。なお、NumWedgePatternの初期値は０である。ウェッジパターンテーブル１４５Ｔ５に格納されたサイズlog2BlkSizeのウェッジレットパターンのパターン数がNumWedgePattern[ log2BlkSize ]とする。
【０２２５】
図１８は、パターン格納部１４６４の動作を示すフローチャートである。
【０２２６】
（Ｓ２００１）パターン格納部１４６４は、一致判定Ｃ１を行い一致すると判定された場合には、格納せずに処理を終了し、一致しないと判定された場合にはＳ２００２に遷移する。パターン格納部１４６４は、インデックスk(0..NumWedgePattern[ log2BlkSize ] - 1)のウェッジパターンテーブル１４５Ｔ５に格納されたパターンWedgePatternTable[ log2BlkSize ][ k ][ x ][ y ]と、対象のパターンwedgePattern[ x ][ y ]を比較し１つでも等しくなければ、一致フラグを０とする（一致判定処理Ｃ１）。
【０２２７】
// 一致判定処理Ｃ１
for k = 0..NumWedgePattern[ log2BlkSize ] - 1
patIdenticalFlag = 1
for x, y =0..( 1  <<  log2BlkSize ) - 1,
if (wedgePattern[ x ][ y ] != WedgePatternTable[ log2BlkSize ][ k ][ x ][ y ])
patIdenticalFlag = 0
【０２２８】
（Ｓ２００２）パターン格納部１４６４は、反転一致判定Ｃ２を行い一致すると判定された場合には、格納せずに処理を終了し、それ以外の場合には、Ｓ２００３に遷移する。パターン格納部１４６４は、インデックスk(0..NumWedgePattern[ log2BlkSize ] - 1)のウェッジパターンテーブル１４５Ｔ５に格納されたパターンWedgePatternTable[ log2BlkSize ][ k ][ x ][ y ]と、対象のパターンwedgePattern[ x ][ y ]を比較しひとつでも等しければ（反転したパターンと一つでも異なれば）一致フラグを０とする（反転一致判定処理Ｃ２）。
【０２２９】
// 反転一致判定処理Ｃ２
for k = 0..NumWedgePattern[ log2BlkSize ] - 1
patIdenticalFlag = 1
for x, y =0..( 1  <<  log2BlkSize ) - 1,
if (wedgePattern[ x ][ y ] == WedgePatternTable[ log2BlkSize ][ k ][ x ][ y ])
patIdenticalFlag = 0
【０２３０】
（Ｓ２００３）パターン格納部１４６４は、生成されるウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。格納されるのは、一致判定Ｃ１と反転一致判定Ｃ２でどちらでも一致しないと判定され、patIdenticalFlagが０となる場合のみである。格納時にウェッジパターン数NumWedgePattern[ log2BlkSize ] を１だけインクリメントする。
【０２３１】
（ウェッジレットパターン生成部１４５Ｔ４の動作手順）
図１５は、ウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理のうち、各基本パターン生成、各回転パターン生成に注目した処理を示すフローチャートである。以下、図１５を参照して、ウェッジレットパターン生成部１４５Ｔ４の詳細動作を説明する。図１９は、基本パターン生成および回転パターン生成に用いる生成パラメータを示すテーブルである。パラメータを用いることにより、各パターンの生成が共通の処理で実行可能である。また共通の処理（プログラム、回路）を用いず、図の生成パラメータを展開して得られる個別の処理（プログラム、回路）を用いて各基本パターン生成、各回転パターン生成を行っても良い。
【０２３２】
（Ｓ１００１）第１基本パターン生成
ウェッジレットパターン生成部１４５Ｔ４は、基本パターン生成部１４６１において第１基本パターン生成を生成する（図１６（ａ）に相当）。ここでは、第１基本パターン生成は、図１３(a)に示すウェッジ方向wedgeOri=0のウェッジレットパターンとするが、ウェッジ方向wedgeOri=0〜3のウェッジレットパターンの何れか１つのウェッジレットパターンでも構わない。基本パターン生成は、始点、終点設定、線分描画、領域フィルから構成される。
【０２３３】
基本パターン生成部１４６１は、始点（xS、yS）と終点（xE、yE）を設定する。具体的には、第１のループ変数m（m= 0..wBlkSize - 1）、第２のループ変数n（n= 0..wBlkSize - 1）に対して、以下の式により、xS、yS、xE、yEを設定する。
【０２３４】
xS = m 
yS =  0 
xE = (wedgeOri==0) ? 0 : n
yE = (wedgeOri==0) ? n : wBlkSize - 1
wedgeOri==0なので、以下が設定される。
【０２３５】
xS = m  
yS = 0 
xE = 0 
yE = n  
ここでは、図１３(a)で説明したように、始点がブロックの上辺の線分Ｓ上の点、終点がブロックの左辺の線分Ｅ上の点となる。
【０２３６】
なお、xPosS、yPosS、xPosE、yPosEは初期値、xIncS、yIncS、xIncE、yIncEは増分として以下のように始点と終点を設定しても良い。
【０２３７】
xS = ( xPosS + m * xIncS )
yS = ( yPosS + m * yIncS )
xE = ( xPosE + n * xIncE )
yE = ( yPosE + n * yIncE )
【０２３８】
ウェッジ方向wedgeOri=0を基本パターンとする場合には、図１９（ａ）に示すあたい、xPosS=0、yPosS=0、xPosE=0、yPosE=0、xIncS=1、yIncS=0、xIncE=0、yIncE=1を設定する。これにより上記値が設定される。
【０２３９】
領域フィル部１４６３は、パターンが１である画素を探索し、パターンが１である画素があれば継続する画素を１に設定する。
【０２４０】
なお、第２のループ変数nは１からスタートしても良い（n= 1..wBlkSize - 1）。これにより冗長なパターンが生成されることを防ぐことができる。
【０２４１】
この領域フィルは、第１基本パターンと第２基本パターンで共通の処理を用いることができる。本実施形態の線分描画部１４６２では、導出するウェッジレットパターン毎に異なる領域フィル処理を用いることなく、一つの領域フィル処理を共通で用いることができるという効果を奏する。
【０２４２】
パターン格納部１４６４は、領域フィル部１４６３でフィルされたパターンをウェッジパターンテーブル１４５Ｔに格納する。基本パターン導出では、基本パターン導出前のウェッジパターンテーブル１４５Ｔに格納されたテーブルの数NumWedgePattern[log2BlkSize]を変数startPos、基本パターン導出後のウェッジパターンテーブル１４５Ｔに格納されたテーブルの数NumWedgePattern[log2BlkSize]−１を変数endPosに設定する。ここでは、変数startPosは０、変数endPosを第１基本パターンを導出した後のウェッジパターンテーブル１４５Ｔの数となる。
【０２４３】
（Ｓ１００２）第１基本パターン第１回転パターン生成
回転パターン生成部１４６５は、ウェッジパターンテーブル１４５Ｔに格納された、基本パターンを１つ１つ読み出し、回転させることで、基本パターンの回転パターンを生成する（図１６（ｂ）に相当）。ここでは、図１３(ｂ)に示すウェッジ方向wedgeOri=1のウェッジレットパターンを生成する。具体的には、startPos（ここでは０）からendPos（ここでは第１基本パターン導出後のウェッジテーブル数―１）までのposで指定されるウェッジパターンテーブル１４５Ｔの各WedgePatternTable[ log2BlkSize ][ pos ]を参照パターンrefPattern[][]として、以下の処理により、回転後のパターンwedgePattern[][]を導出する。
【０２４４】
cInc = 0
sInc = -1
iOffset = patternSize - 1
jOffset = 0
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
i = iOffset + cInc * x + sInc * y = patternSize - 1 - y 
j = jOffset - sInc * x + cInc * y = 0 
wedgePattern[ x ][ y ] = refPattern [ i ][ j ]
}
【０２４５】
本実施形態の回転パターン生成部１４６５は、入力された参照ウェッジレットパターンrefPattern [ i ][ j ]から対象ウェッジレットパターンwedgePattern[ x ][ y ]を生成し、参照ウェッジレットパターン上の座標(i, j)を回転行列で座標変換して得られる座標(x, y)上の対象ウェッジレットパターンの値wedgePattern[ x ][ y ]として、参照ウェッジレットパターンの座標(i, j)の値refPattern [ i ][ j ]を用いる。処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替えることができるため、処理を低減する効果を奏する。
【０２４６】
前記回転パターン生成部１４６５は、基本パターン設定部１４６１で設定される開始点と終了点の間のウェッジレットパターンを入力refPattern[][]として、回転パターンであるウェッジレットパターンwedgePattern[][]を導出する。
【０２４７】
なお、上の座標(i, j)を対象パターン上の座標(x, y)に座標変換するのではなく、対象パターン上の座標（x, y）を参照パターン上の座標(i, j)に座標変換し、対象パターン上の座標(x, y)上の画素wedgePattern[ x ][ y ]として、参照パターン上の座標(i, j)上の画素refPattern [ i ][ j ]を代入してもよい。この場合も、(i,j)と(x,y)は、回転行列で座標変換されるものとする。すなわち、i = (cosθ)x + (sinθ)y、j = -(sinθ)x + (cosθ)yの関係を満たす。
【０２４８】
上記第１基本パターン第１回転パターン生成の例では、
for( y = 0; y < patternSize; y++ )  
for( x = 0; x < patternSize; x++ )  {
i = 0 * x + 1 * y
j = -1 * x + 0 * y
wedgePattern[ x ][ y ] = refPattern [ i ][ j ]
}
としても良い。
【０２４９】
生成されたパターンwedgePattern[][]はパターン格納部１４６４に格納される。
【０２５０】
（Ｓ１００３）第１基本パターン第２回転パターン生成
回転パターン生成部１４６５は、ウェッジパターンテーブル１４５Ｔに格納された、基本パターンを１つ１つ読み出し、回転させることで、基本パターンの回転パターンを生成する（図１６（ｃ）に相当）。ここでは、図１３(ｃ)に示すウェッジ方向wedgeOri=2のウェッジレットパターンを生成する。具体的には、startPos（ここでは０）からendPosまでのposで指定されるウェッジパターンテーブル１４５Ｔの各WedgePatternTable[ log2BlkSize ][ pos ]を参照パターンrefPattern[][]として、回転後のパターンwedgePattern[][]を導出する。
【０２５１】
cInc = -1
sInc = 0
iOffset = patternSize - 1
jOffset = patternSize - 1
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
i = iOffset + cInc * x + sInc * y = patternSize - 1 - x
j = jOffset - sInc * x + cInc * y = patternSize - 1 - y
wedgePattern[ x ][ y ] = refPattern [ i ][ j ]
}
生成されたパターンwedgePattern[][]はパターン格納部１４６４で格納される。
【０２５２】
（Ｓ１００４）第１基本パターン第３回転パターン生成
回転パターン生成部１４６５は、ウェッジパターンテーブル１４５Ｔに格納された、基本パターンを１つ１つ読み出し、回転させることで、基本パターンの回転パターンを生成する（図１６（ｄ）に相当）。ここでは、図１３(ｄ)に示すウェッジ方向wedgeOri=3のウェッジレットパターンを生成する。具体的には、startPos（ここでは０）からendPosまでのposで指定されるウェッジパターンテーブル１４５Ｔの各WedgePatternTable[ log2BlkSize ][ pos ]を参照パターンrefPattern[][]として、回転後のパターンwedgePattern[][]を導出する。
【０２５３】
cInc = 0
sInc = 1
iOffset = 0
jOffset = patternSize - 1
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
i = iOffset + cInc * x + sInc * y = y
j = jOffset - sInc * x + cInc * y = patternSize - 1 - x
wedgePattern[ x ][ y ] = refPattern [ i ][ j ]
}
生成されたパターンwedgePattern[][]はパターン格納部１４６４で格納される。
【０２５４】
（Ｓ１００５）第２基本パターン生成
ウェッジレットパターン生成部１４５Ｔ４は、基本パターン生成部１４６１において第２基本パターン生成を生成する（図１６（ａ）に相当）。
【０２５５】
基本パターン生成部１４６１は、始点（xS、yS）と終点（xE、yE）を設定する。具体的には、第１のループ変数m（m= 0..wBlkSize - 1）、第２のループ変数n（n= 0..wBlkSize - 1）に対して、以下の式により、xS、yS、xE、yEを設定する
xS = m 
yS =  0 
xE = (wedgeOri==0) ? 0 : n
yE = (wedgeOri==0) ? n : wBlkSize - 1
すなわち、以下が設定される
xS = m * 1 
yS = 0 
xE =  n 
yE = wBlkSize - 1 
なお、xPosS、yPosS、xPosE、yPosEは初期値、xIncS、yIncS、xIncE、yIncEは増分とし、図１９（ｅ）に示す値であるxPosS=0、yPosS=0、xPosE=0、yPosE=  wBlkSize - 1 、xIncS=1、yIncS=0、xIncE=1、yIncE=0を用いて以下のように導出してもよい
xS = ( xPosS + m * xIncS )
yS = ( yPosS + m * yIncS )
xE = ( xPosE + n * xIncE )
yE = ( yPosE + n * yIncE )
【０２５６】
第２基本パターンは、始点もしくは終点の移動方向が互いに並行であるパターンである。すなわち、始点の移動方向が水平方向（xIncS=1、yIncS=0）である場合、終点の移動方向も水平方向（xIncE=1、yIncE=0）であるパターンを指す。なお、移動方向に垂直な方向、ここでは垂直方向の成分は固定値となる。なお、移動方向が互いに並行であれば、（xIncS=1、yIncS=0）、（xIncE=-1、yIncE=0）のように方向が反転していても良い。
【０２５７】
ここで説明した第２基本パターンは、ウェッジ方向wedgeOri=4のパターンであり、図１３(ｅ)で説明したように、始点がブロックの上辺の線分Ｓ上の点、終点がブロックの下辺の線分Ｅ上の点となる。
【０２５８】
なお、第２基本パターンを、ウェッジ方向wedgeOri=5のパターンとすることもできる。図１３(ｆ)で説明したように、始点がブロックの左辺の線分Ｓ上の点、終点がブロックの右辺の線分Ｅ上の点となる。第２基本パターンをウェッジ方向wedgeOri=5のパターンとする場合には、xPosS=0、yPosS=0、xPosE=patternSize-1、yPosE=0、xIncS=0、yIncS=1、xIncE=0、yIncE=1を設定する。すなわち、以下が設定される
xS = 0 
yS =  m * 1 
xE = patternSize-1 
yE = n * 1 
【０２５９】
この場合も、第２基本パターンは、始点もしくは終点の移動方向が互いに並行であるパターンとなる。すなわち、始点の移動方向が垂直方向（xIncS=0、yIncS=1）である場合、終点の移動方向も垂直方向（xIncE=0、yIncE=1）であるパターンを指す。なお、移動方向に垂直な方向、ここでは水平方向の成分は固定値となる。なお、移動方向が互いに並行であれば、（xIncS=0、yIncS=1）、（xIncE=0、yIncE=-1）のように方向が反転していても良い。
【０２６０】
領域フィル部１４６３は、線分描画部１４６２で導出された線分で分けられた２つの領域の内、一方の領域を１でフィルする。他方の領域は０のままとする。具体的には以下の擬似コードで示す処理によりフィルを行う。
【０２６１】
生成されたパターンwedgePattern[][]はパターン格納部１４６４に格納される。基本パターン導出では、基本パターン導出前のウェッジパターンテーブル１４５Ｔに格納されたテーブルの数NumWedgePattern[log2BlkSize]を変数startPos、基本パターン導出後のウェッジパターンテーブル１４５Ｔに格納されたテーブルの数NumWedgePattern[log2BlkSize]−１を変数endPosに設定する。
【０２６２】
（Ｓ１００６）第２基本パターン第１回転パターン生成
回転パターン生成部１４６５は、ウェッジパターンテーブル１４５Ｔに格納された、第２基本パターンを１つ１つ読み出し、回転させることで、第２基本パターンの回転パターンを生成する。ここでは、図１３(ｆ)に示すウェッジ方向wedgeOri=5のウェッジレットパターンを生成する。具体的には、startPosからendPosまでのposで指定されるウェッジパターンテーブル１４５Ｔの各WedgePatternTable[ log2BlkSize ][ pos ]を参照パターンrefPattern[][]として、回転後のパターンwedgePattern[][]を導出する。
【０２６３】
cInc = 0
sInc = 1
iOffset = 0
jOffset = patternSize - 1
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
i = iOffset + cInc * x + sInc * y = y
j = jOffset - sInc * x + cInc * y = patternSize - 1 - x
wedgePattern[ x ][ y ] = refPattern [ i ][ j ]
}
生成されたパターンwedgePattern[][]は、パターン格納部１４６４に格納される。
【０２６４】
（ウェッジレットパターン生成部１４５Ｔ４の実施形態）
以下、ウェッジレットパターン生成部１４５Ｔ４の変形例であるウェッジレットパターン生成部１４５Ｔ４´を説明する。図２２は、ウェッジレットパターン生成部１４５Ｔ４´の構成を説明する図である。ウェッジレットパターン生成部１４５Ｔ４´は、基本パターン生成部１４６１、パターン格納部１４６４´、回転パターン生成部１５６５´から構成される。
【０２６５】
（回転パターン生成部１４６５´）
回転パターン生成部１４６５´は、参照パターンrefPatternに基づいて対象パターンに設定する際に、一部の場合に反転を行う。具体的には、回転パターン生成部１４６５´は、以下の擬似コードの処理を行う。
【０２６６】
cInc = wedgeOri == 2 ? - 1 : 0;
sInc = (wedgeOri == 1 ? - 1 : 1) * (1 + cInc);
iOffset = cInc + sInc < 0 ? patternSize - 1 ? 0
jOffset = -sInc + cInc < 0 ? patternSize - 1 ? 0
for( y = 0; y < patternSize; y++ ) {
for( x = 0; x < patternSize; x++ )  {
i = iOffset + cInc * x + sInc  * y
j = jOffset - sInc * x + cInc  * y
wedgePattern[ x ][ y ] = refPattern [ iOffset ][ jOffset ] ? refPattern [ i ][ j ] : 1 -refPattern [ i ][ j ]       式Ｒ２
}
}
【０２６７】
式Ｒ２は、対象パターンの左上座標(0, 0)のウェッジレットパターンの値が１となるように回転に加え、条件に応じて反転を行う場合の式である。
【０２６８】
図２４は、本実施形態の回転パターン生成部１４６５´の動作を説明する図である。領域フィル部１４６３は左上座標の値が１となるウェッジレットパターンを生成する。式Ｒ２の処理を行う回転パターン生成部１４６５´は、図２４（ａ）に示すように、回転後の左上座標が１となる場合、、反転せずrefPattern [ i ][ j ]を、対象パターンwedgePattern[ x ][ y ]に設定し、図２４（ｂ）に示すように回転後の左上座標が０の場合には回転および反転して、1-refPattern [ i ][ j ]（= !refPattern [ i ][ j ]）を対象パターンwedgePattern[ x ][ y ]に設定する。ここで反転とは１と０を入れ替える操作を指す。
【０２６９】
参照パターン上の座標(i0 , j0)の参照パターンの値refPattern [ i0 ][ j0 ]が、回転後に対象パターンの左上座標(0, 0)の値として設定されるとすると、回転パターン生成部１４６５´は、回転後の左上座標の対象パターンの値refPattern [ i0 ][ j0 ]が１の場合には、反転せずrefPattern [ i ][ j ]を設定し、refPattern [ i0 ][ j0 ]が０の場合には反転して、1-refPattern [ i ][ j ]を設定する。
【０２７０】
回転後に 座標(x, y)が(0,0)となる、回転前の座標(i0, j0)は以下により求められる。
【０２７１】
i0 = iOffset + cInc * 0 + sInc  * 0 = iOffset
j0 = jOffset - sInc * 0 + cInc  * 0 = jOffset
すなわち、(i0, j0)= (iOffset, jOffset)であり、回転後の左上座標の対象パターンの値はrefPattern [ iOffset ][ jOffset ]である。よって、refPattern [ iOffset ][ jOffset ]が１の場合に、反転せずrefPattern [ i ][ j ]を設定し、refPattern [ iOffset ][ jOffset ]が０の場合には反転して、1-refPattern [ i ][ j ]を設定する。
【０２７２】
このように、ウェッジレットパターン生成部１４５Ｔ４´の備える領域フィル部１４６３がウェッジレットパターンの左上が常に１となるようなウェッジレットパターンを生成する場合において、ウェッジレットパターン生成部１４５Ｔ４´の備える回転パターン生成部１４６５´は、ウェッジレットパターンの左上が常に１（もしくは常に０）であるパターンを容易に生成することができるという効果を奏する。
【０２７３】
図２３は、ウェッジレットパターン生成部１４５Ｔ４´におけるウェッジレットパターン生成処理を示す図である。図１６では、ウェッジレットパターンの左上座標の画素値が回転前と回転後で反転していたが、図２３では、ウェッジレットパターンの左上座標の画素値が反転することはない。図２３では、式Ｒ２のように回転パターン生成のときに、条件に応じて反転させることにより、左上座標のウェッジレットパターンの値の変化をなくすことができる。左上座標のウェッジレットパターンの値を固定にする場合、ウェッジレットパターンの１と０が反転したパターンが、基本パターン生成部１４６１および回転パターン生成部１５６５´から生成されることがないため、パターン格納部１４６４´における一致判定処理がウェッジレットパターン生成部１４５Ｔ４に比べ簡略化できる。
【０２７４】
図２５は、本実施形態の別の形態のウェッジレットパターン生成部１４５Ｔ４´を説明する図である。ウェッジレットパターン生成部１４５Ｔ４´は、領域フィル部１４６３、回転パターン生成部１４６５の代わりに、領域フィル部１４６３´、回転パターン生成部１４６５´´を備える。領域フィル部１４６３´は、左上が常に０となるように領域のフィルを行う。回転パターン生成部１４６５´´は、式Ｒ２の代わりに以下の式Ｒ２´を用いる。
【０２７５】
wedgePattern[ x ][ y ] = refPattern [ iOffset ][ jOffset ] == 0 ? refPattern [ i ][ j ] : 1 -refPattern [ i ][ j ]       式Ｒ２´
なお、refPattern [ iOffset ][ jOffset ] == 0は、論理否定！を用いて、!refPattern [ iOffset ][ jOffset ]でも処理ができる。
【０２７６】
ウェッジレットパターン生成部１４５Ｔ４´の備える領域フィル部１４６３がウェッジレットパターンの左上が常に０となる場合、上記構成の回転パターン生成部１４６５´´は、回転前と回転後でウェッジレットパターンの左上座標の値を変更させないという効果を奏する。
【０２７７】
図２６は、ウェッジレットパターン生成部１４５Ｔ４´の備えるパターン格納部１４６４´の動作を示すフローチャートである。
【０２７８】
（Ｓ２０１１）パターン格納部１４６４´は、一致判定Ｃ１で一致すると判定された場合には、格納せずに処理を終了し、一致しないと判定された場合にはＳ２０１３に遷移する。パターン格納部１４６４は、インデックスk(0..NumWedgePattern[ log2BlkSize ] - 1)のウェッジパターンテーブル１４５Ｔ５に格納されたパターンWedgePatternTable[ log2BlkSize ][ k ][ x ][ y ]と、対象のパターンwedgePattern[ x ][ y ]を比較し１つでも等しくなければ、一致フラグを０とする（一致判定処理Ｃ１）。
【０２７９】
// 一致判定処理Ｃ１
for k = 0..NumWedgePattern[ log2BlkSize ] - 1
patIdenticalFlag = 1
for x, y =0..( 1  <<  log2BlkSize ) - 1,
if (wedgePattern[ x ][ y ] != WedgePatternTable[ log2BlkSize ][ k ][ x ][ y ])
patIdenticalFlag = 0
【０２８０】
（Ｓ２０１３）パターン格納部１４６４´は、一致判定Ｃ１で一致しない場合、つまり、patIdenticalFlagが０の場合のみ、生成されるウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。格納時にウェッジパターン数NumWedgePattern[ log2BlkSize ] を１だけインクリメントする。
【０２８１】
ウェッジレットパターン生成部１４５Ｔ４´によれば、領域フィル部１４６３および回転パターン生成部１４６５´（もしくは回転パターン生成部１４６５´´）で、常にウェッジレットパターンの左上画素を１（もしくは０）とする規則に応じてウェッジレットパターンが生成するため、パターン格納部１４６４´において、反転一致判定Ｃ２を行う必要がない。そのため、ウェッジレットパターン生成部１４５Ｔ４´によれば、一致判定Ｃ１のみを行えば良いため、既にウェッジパターンテーブル１４５Ｔ５に格納したウェッジレットパターンと生成したパターンが一致しているがどうかの判定処理を低減させる効果を奏する。
【０２８２】
（回転パターン生成部１４６５´の別の構成）
なお、ウェッジレットパターン生成部１４５Ｔ４´は、回転パターン生成部１４６５´として、以下の式Ｒ２、式Ｒ２´よりも簡単な式Ｒ３を用いても良い。
【０２８３】
cInc = wedgeOri == 2 ? - 1 : 0;
sInc = (wedgeOri == 1 ? - 1 : 1) * (1 + cInc);
iOffset = cInc + sInc < 0 ? patternSize - 1 ? 0
jOffset = -sInc + cInc < 0 ? patternSize - 1 ? 0
for( y = 0; y < patternSize; y++ ) {
for( x = 0; x < patternSize; x++ )  {
i = iOffset + cInc * x + sInc  * y
j = jOffset - sInc * x + cInc  * y
wedgePattern[ x ][ y ] = 1 -refPattern [ i ][ j ]       式Ｒ３
}
}
【０２８４】
式Ｒ３を用いる回転パターン生成部１４６５´では、回転パターンとして導出されるウェッジレットパターンの左上画素が常に１（もしくは０）となることは保障されないが、参照パターンの左上画素が１（もしくは０）となるように生成されている場合、多くの場合に、ウェッジレットパターンの左上画素を１（もしくは０）となる。これにより、パターン格納部１４６４´において、反転一致判定Ｃ２を行う必要がない。そのため、ウェッジレットパターン生成部１４５Ｔ４´によれば、一致判定Ｃ１のみを行えば良いため、既にウェッジパターンテーブル１４５Ｔ５に格納したウェッジレットパターンと生成したパターンが一致しているがどうかの判定処理を低減させる効果を奏する。なお、反転して一致するパターンが一部ウェッジパターンテーブル１４５Ｔ５に格納されても問題は生じない。
【０２８５】
（ウェッジレットパターン生成部１４５Ｔ４´´）
回転パターン生成部１４６５、１４６５´から生成される回転パターンのウェッジパターン（ウェッジレットパターン）は、多くの場合、既に生成され、ウェッジパターンテーブル１４５Ｔ５に格納されたウェッジパターン（ウェッジレットパターン）と一致することがない。そのため、回転パターンでは一致判定を省略するようにパターン格納部の動作を簡略化することが適当である。以下、このような構成のパターン格納部１４６４´´を備えるウェッジレットパターン生成部１４５Ｔ４´´を説明する。
【０２８６】
ウェッジレットパターン生成部１４５Ｔ４´´は、ウェッジレットパターン生成部１４５Ｔ４、ウェッジレットパターン生成部１４５Ｔ４´と同様の構成であるが、パターン格納部１４６４、パターン格納部１４６４´の代わりに、パターン格納部１４６４´´を用いる。
【０２８７】
図２７は、ウェッジレットパターン生成部１４５Ｔ４´´の備えるパターン格納部１４６４´´の動作を示すフローチャートである。
【０２８８】
（Ｓ２０２０）パターン格納部１４６４´´は、ウェッジ方向wedgeOriが所定の値、ここでは基本パターン（第１基本パターン、第２基本パターン）を示すwedgeOri=0、4である場合、Ｓ２０２１に遷移し、条件に応じてウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。それ以外の場合（ここでは回転パターンを示すwedgeOri=1,2,3,5の場合）、Ｓ２０２３に遷移し条件によらずウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。
【０２８９】
（Ｓ２０２１）パターン格納部１４６４´´は、既にウェッジパターンテーブル１４５Ｔ５に格納したウェッジレットパターンと一致する場合には、格納せずにＳ２０２５に遷移する。一致しない場合にはＳ２０２３に遷移する。なお、一致判定には、既に説明した一致判定Ｃ１および反転一致判定Ｃ２を用いることができる。なお、回転パターン生成部１４６５´で、ウェッジレットパターンの左上画素を１（もしくは０）とするような、式Ｒ２、Ｒ２´もしくは、式Ｒ３を利用して、ウェッジレットパターンを生成する場合には、パターン格納部１４６４´´は、パターン格納部１４６４´と同様、反転一致判定Ｃ２を行わず、一致判定Ｃ１のみを行うことが適当である。
【０２９０】
（Ｓ２０２３）パターン格納部１４６４´´は、生成されるウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。格納される場合は、基本パターンの場合、かつ、既にウェッジパターンテーブル１４５Ｔ５に格納したウェッジレットパターンと一致しない場合、もしくは、回転パターンの場合である。格納時にウェッジパターン数NumWedgePattern[ log2BlkSize ] を１だけインクリメントする。
【０２９１】
上記構成のパターン格納部１４６４´´を備えるウェッジレットパターン生成部１４５Ｔ４´´によれば、基本パターンのさらにウェッジ方向wedgeOriの一致したパターン間のパターンのみで一致判定を行うので、一致判定に用いる処理量が少ないという効果を奏する。
【０２９２】
（第２基本パターンを先に導出する例）
以上説明したウェッジレットパターン生成部１４５Ｔ４、ウェッジレットパターン生成部１４５Ｔ４´、ウェッジレットパターン生成部１４５Ｔ４´´では、始点と終点の位置する辺が互いに直交する関係を有する始点と終点から生成される第１基本パターンの次に、始点と終点の位置する辺が互いに並行する関係を有する始点と終点から生成される第２基本パターンを生成しているが、第２基本パターンを第１基本パターンの先に生成しても良い。図２８は、ウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理を示すフローチャートの別の例であり、第２基本パターンを第１基本パターンの先に生成する。
【０２９３】
（Ｓ１０１１）第２基本パターン生成
図１６（ｅ）、図２３（ｅ）を用いて、既に説明したＳ１００５と同じ動作により第２基本パターンを生成する。
【０２９４】
（Ｓ１０１２）第２基本パターン生成第１回転パターン生成
図１６（ｆ）、図２３（ｆ）を用いて、既に説明したＳ１００６と同じ動作により第２基本パターン第１回転パターンを生成する。
【０２９５】
（Ｓ１０１３）第１基本パターン生成
図１６（ａ）、図２３（ａ）を用いて、既に説明したＳ１００１と同じ動作により第１基本パターンを生成する。
【０２９６】
（Ｓ１０１４）第２基本パターン生成第１回転パターン生成
図１６（ｂ）、図２３（ｂ）を用いて、既に説明したＳ１００２と同じ動作により第１基本パターン第１回転パターンを生成する。
【０２９７】
（Ｓ１０１５）第２基本パターン生成第１回転パターン生成
図１６（ｃ）、図２３（ｃ）を用いて、既に説明したＳ１００３と同じ動作により第１基本パターン第２回転パターンを生成する。
【０２９８】
（Ｓ１０１６）第２基本パターン生成第１回転パターン生成
図１６（ｄ）、図２３（ｄ）を用いて、既に説明したＳ１００４と同じ動作により第１基本パターン第３回転パターンを生成する。
【０２９９】
第２基本パターンを先に生成する場合も、ウェッジレットパターン生成部１４５Ｔ４の効果は、第１基本パターンを先に生成する場合と等しい。すなわち、本実施形態のウェッジレットパターン生成部１４５Ｔ４は、全てのウェッジレットパターンを線分描画部１４６２、領域フィル部１４６３を用いた線分描画処理、領域フィル処理により生成するのではなく、一部のウェッジレットパターンは回転パターン生成部１５６５を用いた回転処理により生成する。処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替えることができるため、処理を低減する効果を奏する。
【０３００】
[ウェッジパターンテーブル１４５Ｔ５]
ウェッジパターンテーブル１４５Ｔ５は、ウェッジレットパターン生成部１４５Ｔ４より供給されるブロックサイズ別のウェッジパターンテーブルWedgePatternTableを記録する。
【０３０１】
（作用・効果）
以上説明した本実施形態に係る動画像復号装置１の備えるウェッジレットパターン生成部１４５Ｔ４は、全てのウェッジレットパターンを線分描画部１４６２、領域フィル部１４６３を用いた線分描画処理、領域フィル処理により生成するのではなく、一部のウェッジレットパターンは回転パターン生成部１５６５を用いた回転処理により生成する。処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替えることができるため、処理を低減する効果を奏する。
【０３０２】
以上説明した本実施形態に係る動画像復号装置１の備える線分描画部１４６２は、ウェッジレットパターンサイズpatternSizeを、refShiftだけ左シフトして得られるサイズpatternSize<< refShiftの拡大ブロック上の始点(xS、yS)と終点(xE、yE)から得られる線分座標(xPos, yPos)を、refShiftだけ右シフトして得られる座標(xPos>> refShift, yPos>> refShift)に１を設定することにより、線分描画処理に用いるメモリサイズを増大させることを防ぐ効果を奏する。
【０３０３】
以上説明した本実施形態に係る動画像復号装置１の備えるウェッジレットパターン生成部１４５Ｔ４´は、回転とともに反転を回転パターン生成部１４６５´を用いることにより、ウェッジレットパターンの左上が常に１（もしくは常に０）であるパターンを容易に生成することができる（式Ｒ２の場合）、という効果を奏する。もしくは、回転とともに反転を回転パターン生成部１４６５´を用いることにより、ウェッジレットパターンの左上が多くの場合に１（もしくは常に０）であるパターンを容易に生成することができる（式Ｒ３の場合）。
【０３０４】
以上説明した本実施形態に係る動画像復号装置１の備える領域フィル部１４６３は、パターンが１である画素を探索し、パターンが１である画素があれば継続する画素を１に設定する。これにより、導出するウェッジレットパターン毎に異なる領域フィル処理を用いることなく、一つの領域フィル処理を共通で用いることができるという効果を奏する。
【０３０５】
以上説明した本実施形態に係る動画像復号装置１の備えるウェッジレットパターン生成部１４５Ｔ４´´のパターン格納部１４６４´´は、基本パターンについてのみ、一致判定を行い、回転パターンについては、一致判定を行わずに格納するため処理量が少ないという効果を奏する。
【０３０６】
（ウェッジレットパターン生成部１４５Ｔ４の変形例）
以下、ウェッジレットパターン生成部１４５Ｔ４の変形例のウェッジレットパターン生成部１４５Ｔ４Ｂを説明する。
【０３０７】
図３０に示すとおり、ウェッジレットパターン生成部１４５Ｔ４Ｂは、ウェッジレットパターン生成部１４５Ｔ４と同様に、基本パターン生成部１４６１、パターン格納部１４６４、回転パターン生成部１５６５Ｂから構成され、基本パターン生成部１４６１は、線分描画部１４６２、領域フィル部１４６３から構成される。
【０３０８】
図３１は、ウェッジレットパターン生成部１４５Ｔ４におけるウェッジレットパターン生成処理を示す図である。図３１（a)に示すように、本実施形態のウェッジレットパターン生成部１４５Ｔ４Ｂは、基本パターン生成部１４６１で第１基本パターンを構成するウェッジレットパターンのセットを生成する。次に、（ｂ）に示すように、回転パターン生成部１４６５Ｂで、直前に生成したウェッジレットパターンのセットである第１基本パターンに含まれる個々のウェッジレットパターンを回転させ、ウェッジレットパターンのセットである第１基本パターン第１回転パターン（第１回転パターン）を生成する。次に、（ｃ）に示すように、回転パターン生成部１４６５Ｂで、直前に生成したウェッジレットパターンのセットである第１基本パターン第１回転パターンに含まれる個々のウェッジレットパターンを回転させ、ウェッジレットパターンのセットである第１基本パターン第２回転パターン（第２回転パターン）を生成する。次に、（ｄ）に示すように、回転パターン生成部１４６５Ｂで、直前に生成したウェッジレットパターンのセットである第１基本パターン第２回転パターンに含まれる個々のウェッジレットパターンを回転させ、第１基本パターン第３回転パターン（第３回転パターン）を生成する。さらに、図３１(ｅ)に示すように、本実施形態のウェッジレットパターン生成部１４５Ｔ４Ｂは、基本パターン生成部１４６１で第２基本パターンを構成するウェッジレットパターンのセットを生成する。（ｆ）に示すように、回転パターン生成部１４６５Ｂで、直前に生成したウェッジレットパターンのセットである第２基本パターンに含まれる個々のウェッジレットパターンを回転させ、ウェッジレットパターンのセットである第２基本パターン第１回転パターン（第４回転パターン）を生成する。本実施形態では、第１回転パターン、第２回転パターン、第３回転パターン、第４回転パターンを生成するために回転パターン生成部１４６５Ｂは各々時計回りに90度の例を説明するが、90度ではなく270度の回転でも良い。
【０３０９】
図３２は、ウェッジレットパターン生成部１４５Ｔ４Ｂの動作を示すフローチャートである。
【０３１０】
（Ｓ０１０１）変数posStartに０を設定する。
【０３１１】
（Ｓ０１０２）ウェッジ方向wedgeOriに関するループの開始。ウェッジ方向wedgeOriに0,1,2,3,4,5を順に設定しＳ０１０３からＳ０１１４の処理を行う。
【０３１２】
（Ｓ０１０３）現時点でのウェッジパターン数NumWedgePatternを変数posStart (posWedgePatternとも呼ぶ)に設定する。
【０３１３】
（Ｓ０１０４）ウェッジ方向wedgeOriが基本パターンの場合には、すなわち、wedgeOri=0, 又はwedgeOri＝４の場合に、Ｓ０１０５に遷移し、線分描画処理と領域フィル処理により、ウェッジ方向wedgeOriの各ウェッジレットパターンを生成する。ウェッジ方向wedgeOriが基本パターン以外の場合（wedgeOri=1,2,3,5の場合）には、Ｓ０１０９に遷移し、回転処理によりウェッジレットパターンを生成する。
【０３１４】
（Ｓ０１０５）始点位置と終点位置を制御する変数m, nに関するループの開始。ループ変数はm, n。以下、m=0.. wBlkSize - 1、n=0.. wBlkSize - 1のm, nに対して、Ｓ０１０６からＳ０１０８の処理を行う。これにより、ウェッジ方向wedgeOriに対して、始点、終点を変化させながらウェッジレットパターンを生成する。なおwBlkSizeはブロックサイズ（仮想ブロックサイズ）である。なお、後述するように基本パターン生成部１４６１の変形例で後述するように、m=0.. (wBlkSize / sizeScaleS) - 1、n=0.. (wBlkSize / sizeScaleE) - 1のm, nに対して、Ｓ０１０６からＳ０１０８の処理を行っても良い。
【０３１５】
（Ｓ０１０６）線分描画部１４６２が線分を引き、領域フィル部１４６３が領域をフィルすることで、ウェッジ方向wedgeOri、変数m, nで示される始点、終点の基本パターンであるウェッジレットパターンを生成する。具体的には、基本パターン生成部１４６１は、視点(xS, yS)、終点(xE, yE)を以下の式で導出する。
【０３１６】
xS = m
yS = 0
xE = (wedgeOri==0) ? 0 : n
yE = (wedgeOri==0) ? n : wBlkSize - １
【０３１７】
また、基本パターン生成部１４６１は、変形例として後述するように視点(xS, yS)、終点(xE, yE)を以下の式で導出しても良い。
【０３１８】
xS = m* sizeScaleS
yS = 0
xE = (wedgeOri==0) ? 0 : n * sizeScaleE
yE = (wedgeOri==0) ? n * sizeScaleE : wBlkSize - 1
なお、sizeScaleS、sizeScaleEは、始点と終点を各々sizeScaleS、sizeScaleE間隔で変化させるための変数であり、以下の式により導出される。
【０３１９】
sizeScaleS = ( log2BlkSize > 3 ) ? 2 : 1
sizeScaleE = ( wedgeOri < 4  &&  log2BlkSize > 3 ) ? : 2 : 1
ここで、log2BlkSizeは、ブロックサイズの２を底とする対数である。
【０３２０】
（Ｓ０１０７）生成されたウェッジレットパターンが所定条件を満たせば、該ウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。格納する場合、ウェッジパターン数NumWedgePatternを１だけインクリメントする。
【０３２１】
（Ｓ０１０８）始点位置と終点位置を制御する変数m, nに関するループの終了。
【０３２２】
（Ｓ０１０９）posEndに、現時点のウェッジパターン数NumWedgePattern-１を設定する。
【０３２３】
（Ｓ０１１０）参照パターンのインデックスposに関するループの開始。posの範囲はposStartからposEnd。
【０３２４】
（Ｓ０１１１）回転パターン生成部１４６５Ｂを用いて、posを参照ウェッジレットパターンとして、回転パターンであるウェッジレットパターンを生成する。
【０３２５】
（Ｓ０１１２）生成されたウェッジレットパターンが所定条件を満たせば、該ウェッジレットパターンをウェッジパターンテーブル１４５Ｔ５に格納する。格納する場合、ウェッジパターン数NumWedgePatternを１だけインクリメントする。
【０３２６】
（Ｓ０１１３）参照パターンのインデックスposに関するループの終了。
【０３２７】
（Ｓ０１１４）ウェッジ方向wedgeOriに関するループの終了。
【０３２８】
ここで、所定条件とは、パターン格納部１６４における一致判定Ｃ１やＣ２を行い、その結果、格納済ウェッジレットパターンと生成ウェッジレットパターンが重複しないことである。
【０３２９】
基本パターン生成部１４６１の動作は、既に説明した通り、wedgeOri=0（第１基本パターン）とwedgeOri=4（第２基本パターン）において、0からwBlkSize - 1の範囲の各値をとる変数m、0からwBlkSize - 1の範囲の各値をとる変数nについて、始点(xS, yS)と終点（xE、yE)を設定し、線分描画部１４６２、領域フィル部１４６３により、各パターンを導出する。線分描画部１４６２、領域フィル部１４６３は既に説明済みであるので説明を省略する。
【０３３０】
（基本パターン生成部の変形例）
基本パターン生成部１４６１は既に説明した方法の他、変形例として、ウェッジレートテーブルを生成する単位を変更しても良い。具体的には0から(wBlkSize / sizeScaleS) - 1の範囲の各値をとる変数m、0から(wBlkSize / sizeScaleE) - 1の範囲の各値をとる変数nに設定し、始点(xS, yS)と終点（xE、yE)を以下の式により導出しても良い。
【０３３１】
xS = m* sizeScaleS
yS = 0
xE = (wedgeOri==0) ? 0 : n * sizeScaleE
yE = (wedgeOri==0) ? n * sizeScaleE : wBlkSize - 1
このとき、sizeScaleS 、sizeScaleEは、生成する単位（間引き）を処理するための変数であり、sizeScaleS単位で変化する始点、sizeScaleE単位で変化する終点を用いて線分描画部１４６２、領域フィル部１４６３により、線分を描画、領域をフィルしてウェッジレットパターンを導出する。
【０３３２】
（回転パターン生成部１４６５Ｂ）
回転パターン生成部１４６５Ｂは、図３１に示すようにウェッジパターンテーブル１４５Ｔに格納されたウェッジレットパターンを１つ１つ読み出し、回転させることで、回転パターンを生成する（図３２のＳ０１１０〜Ｓ０１１３に相当）。具体的には、startPosからendPosまでのposで指定されるウェッジパターンテーブル１４５Ｔの各WedgePatternTable[ log2BlkSize ][ pos ]を参照パターンrefPattern[][]として回転後のパターンwedgePattern[][]を導出する。
【０３３３】
ウェッジレットパターン生成部１４５Ｔ４Ｂの備える回転パターン生成部１４６５Ｂについて説明する。既に説明した回転パターン生成部１４６５は90度、180度、270度の回転を備えていたが、本実施形態の回転パターン生成部１４６５Ｂは一つの回転方向（具体的には90度もしくは270度）のみを備える。
【０３３４】
本実施形態の回転パターン生成部１４６５Ｂは、以下の処理で示す90度回転処理を行う。これは回転パターン生成部１４６５で説明した処理にcInc = 0、sInc = 1を設定した場合に相当する。
【０３３５】
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
i = x + y
j = patternSize - 1- x + y
wedgePattern[ x ][ y ] = -refPattern [ i ][ j ]       式Ｒ２
}
なお、参照パターンrefPattern= wedgePatternTable[log2BlkSize][pos]であるから、ウェッジパターンテーブルに含まれる参照パターンrefPatternの参照処理と回転処理を同時に表現すると以下となる。
【０３３６】
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
WedgePattern [ x ][ y ] = 1 - WedgePatternTable[ log2BlkSize ][ pos ][ x + y][ wBlkSize - 1 - x + y ]
}
なお、式Ｒ２の代わりに既に説明した式Ｒ２´を用いても良い。この場合、cInc = 0、sInc = 1では、iOffset = 0、jOffset = patternSize - 1であるから、式Ｒ２´にこのiOffset, jOffsetを代入して得られる以下の式Ｒ２Ｂ´を用いる。
【０３３７】
wedgePattern[ x ][ y ] = refPattern [ 0 ][ patternSize - 1 ] == 0 ? refPattern [ i ][ j ] : 1 -refPattern [ i ][ j ]       式Ｒ２Ｂ´
なお、上記処理の代わりに回転パターン生成部１４６５Ｂは、以下の処理で示す270度回転処理を行っても良い（回転パターン生成部１４６５Ｃ）。これは回転パターン生成部１４６５で説明した処理にcInc = 0、sInc = -1を設定した場合に相当する。
【０３３８】
for( y = 0; y < patternSize; y++ )
for( x = 0; x < patternSize; x++ )  {
i = patternSize - 1 + x - y
j = x + y
wedgePattern[ x ][ y ] = -refPattern [ i ][ j ]       式Ｒ２Ｃ
}
なお、式Ｒ２の代わりに既に説明した式Ｒ２´Ｃを用いても良い。この場合、cInc = 0、sInc = -1では、iOffset = patternSize - 1、jOffset = 0であるから、式Ｒ２´にこのiOffset, jOffsetを代入して得られる以下のは式Ｒ２Ｃ´を用いる。
【０３３９】
wedgePattern[ x ][ y ] = refPattern [ patternSize - 1 ][ 0 ] == 0 ? refPattern [ i ][ j ] : 1 -refPattern [ i ][ j ]       式Ｒ２Ｃ´
【０３４０】
本実施形態のウェッジレットパターン生成部１４５Ｔ４Ｂは、全てのウェッジレットパターンを線分描画部１４６２、領域フィル部１４６３を用いた線分描画処理、領域フィル処理により生成するのではなく、一部のウェッジレットパターンは回転パターン生成部１５６５Ｂを用いた回転処理により生成する。処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替えることができるため、処理を低減する効果を奏する。さらに、回転パターン生成部１５６５Ｂは単一角度の回転（ここでは90度もしくは270度）のみの処理であるため、必要となる回転処理が容易であるという効果を奏する。
【０３４１】
〔動画像符号化装置〕
以下において、本実施形態に係る動画像符号化装置２について、図２９を参照して説明する。
【０３４２】
（動画像符号化装置の概要）
動画像符号化装置２は、概略的に言えば、入力画像＃１０を符号化することによって符号化データ＃１を生成し、出力する装置である。ここで、入力画像＃１０は、1又は複数の視点画像TexturePic、及び視点画像TexturePicに対応する同時刻のデプスマップDepthPicからなるレイヤ画像である。
【０３４３】
（動画像符号化装置の構成）
まず、図２９を用いて、動画像符号化装置２の構成例について説明する。図２９は、動画像符号化装置２の構成について示す機能ブロック図である。図２９に示すように、動画像符号化装置２は、符号化設定部２１、逆量子化・逆変換部２２、予測画像生成部２３、加算器２４、フレームメモリ２５、減算器２６、変換・量子化部２７、および符号化データ生成部２９を備えている。
【０３４４】
符号化設定部２１は、入力画像＃１０に基づいて、符号化に関する画像データおよび各種の設定情報を生成する。
【０３４５】
具体的には、符号化設定部２１は、次の画像データおよび設定情報を生成する。
【０３４６】
まず、符号化設定部２１は、入力画像＃１０を、スライス単位、ツリーブロック単位、ＣＵ単位に順次分割することにより、対象ＣＵについてのＣＵ画像＃１００を生成する。
【０３４７】
また、符号化設定部２１は、分割処理の結果に基づいて、ヘッダ情報Ｈ’を生成する。ヘッダ情報Ｈ’は、（１）対象スライスに属するツリーブロックのサイズ、形状および対象スライス内での位置についての情報、並びに、（２）各ツリーブロックに属するＣＵのサイズ、形状および対象ツリーブロック内での位置についてのＣＵ情報ＣＵ’を含んでいる。
【０３４８】
さらに、符号化設定部２１は、ＣＵ画像＃１００、および、ＣＵ情報ＣＵ’を参照して、ＰＴ設定情報ＰＴＩ’を生成する。ＰＴ設定情報ＰＴＩ’には、（１）対象ＣＵの各ＰＵへの可能な分割パターン、および、（２）各ＰＵに割り付ける可能な予測モード、の全ての組み合わせに関する情報が含まれる。
【０３４９】
符号化設定部２１は、ＣＵ画像＃１００を減算器２６に供給する。また、符号化設定部２１は、ヘッダ情報Ｈ’を符号化データ生成部２９に供給する。また、符号化設定部２１は、ＰＴ設定情報ＰＴＩ’を予測画像生成部２３に供給する。
【０３５０】
逆量子化・逆変換部２２は、変換・量子化部２７より供給される、ブロック毎の量子化予測残差を、逆量子化、および、逆直交変換することによって、ブロック毎の予測残差を復元する。逆直交変換については、図３に示す逆量子化・逆変換部１３について、既に説明したとおりであるので、ここではその説明を省略する。
【０３５１】
また、逆量子化・逆変換部２２は、ブロック毎の予測残差を、ＴＴ分割情報（後述）により指定される分割パターンに従って統合し、対象ＣＵについての予測残差Ｄを生成する。逆量子化・逆変換部２２は、生成した対象ＣＵについての予測残差Ｄを、加算器２４に供給する。
【０３５２】
予測画像生成部２３は、フレームメモリ２５に記録されている局所復号画像Ｐ’、および、ＰＴ設定情報ＰＴＩ’を参照して、対象ＣＵについての予測画像Ｐｒｅｄを生成する。予測画像生成部２３は、予測画像生成処理により得られた予測パラメータを、ＰＴ設定情報ＰＴＩ’に設定し、設定後のＰＴ設定情報ＰＴＩ’を符号化データ生成部２９に転送する。なお、予測画像生成部２３による予測画像生成処理は、動画像復号装置１の備える予測画像生成部１４と同様であるので、ここでは説明を省略する。すなわち、予測画像生成部１４は、ウェッジパターン導出部１４５Ｔ２、及びＤＣ予測値導出部１４５Ｔ３から構成されるDMM予測部１４５Ｔを備える。DMM予測部１４５Ｔは、ウェッジレットパターン生成部１４５Ｔ４を備える。ウェッジレットパターン生成部１４５Ｔ４は、基本パターン生成部１４６１、パターン格納部１４６４、回転パターン生成部１５６５から構成され、基本パターン生成部１４６１は、線分描画部１４６２、領域フィル部１４６３から構成される。ウェッジレットパターン生成部１４５Ｔ４の代わりに既に説明したウェッジレットパターン生成部１４５Ｔ４´、ウェッジレットパターン生成部１４５Ｔ４´を用いても良い。また、ウェッジレットパターン生成部１４５Ｔ４の代わりに既に説明した回転パターン生成部１４６５Ｂを備えるウェッジレットパターン生成部１４５Ｔ４Ｂを用いても良い。
【０３５３】
加算器２４は、予測画像生成部２３より供給される予測画像Ｐｒｅｄと、逆量子化・逆変換部２２より供給される予測残差Ｄとを加算することによって、対象ＣＵについての復号画像Ｐを生成する。
【０３５４】
フレームメモリ２５には、復号された復号画像Ｐが順次記録される。フレームメモリ２５には、対象ツリーブロックを復号する時点において、当該対象ツリーブロックよりも先に復号された全てのツリーブロック（例えば、ラスタスキャン順で先行する全てのツリーブロック）に対応する復号画像が記録されている。
【０３５５】
減算器２６は、ＣＵ画像＃１００から予測画像Ｐｒｅｄを減算することによって、対象ＣＵについての予測残差Ｄを生成する。減算器２６は、生成した予測残差Ｄを、変換・量子化部２７に供給する。
【０３５６】
変換・量子化部２７は、予測残差Ｄに対して、直交変換および量子化を行うことで量子化予測残差を生成する。なお、ここで直交変換とは、画素領域から周波数領域への変換のことをさす。また、逆直交変換の例としては、ＤＣＴ変換（Discrete Cosine Transform）、およびＤＳＴ変換（Discrete Sine Transform）等が挙げられる。
【０３５７】
具体的には、変換・量子化部２７は、ＣＵ画像＃１００、および、ＣＵ情報ＣＵ’を参照し、対象ＣＵの１または複数のブロックへの分割パターンを決定する。また、決定された分割パターンに従って、予測残差Ｄを、各ブロックについての予測残差に分割する。
【０３５８】
また、変換・量子化部２７は、各ブロックについての予測残差を直交変換することによって周波数領域における予測残差を生成した後、当該周波数領域における予測残差を量子化することによってブロック毎の量子化予測残差を生成する。なお、変換部・量子化部２７は、ＳＤＣフラグが１の場合、周波数変換・量子化を省略し、対象ＴＵの画素毎の予測残差Ｄ（又はresSamples[x][y]）を０とする。
【０３５９】
また、変換・量子化部２７は、生成したブロック毎の量子化予測残差と、対象ＣＵの分割パターンを指定するＴＴ分割情報と、対象ＣＵの各ブロックへの可能な全分割パターンに関する情報とを含むＴＴ設定情報ＴＴＩ’を生成する。変換・量子化部２７は、生成したＴＴ設定情報ＴＴＩ’を逆量子化・逆変換部２２および符号化データ生成部２９に供給する。
【０３６０】
符号化データ生成部２９は、ヘッダ情報Ｈ’、ＴＴ設定情報ＴＴＩ’、およびＰＴ設定情報ＰＴＩ’を符号化し、符号化したヘッダ情報Ｈ、ＴＴ設定情報ＴＴＩ、およびＰＴ設定情報ＰＴＩを多重化して符号化データ＃１を生成し、出力する。
【０３６１】
（作用・効果）
以上説明した本実施形態に係る動画像符号化装置２の備えるウェッジレットパターン生成部１４５Ｔ４は、全てのウェッジレットパターンを線分描画部１４６２、領域フィル部１４６３を用いた線分描画処理、領域フィル処理により生成するのではなく、一部のウェッジレットパターンは回転パターン生成部１５６５を用いた回転処理により生成する。処理量の大きい線分描画処理、領域フィル処理を、処理量の少ない回転処理に置き替えることができるため、処理を低減する効果を奏する。
【０３６２】
以上説明した本実施形態に係る動画像符号化装置２の備える線分描画部１４６２は、ウェッジレットパターンサイズpatternSizeを、refShiftだけ左シフトして得られるサイズpatternSize<< refShiftの拡大ブロック上の始点(xS、yS)と終点(xE、yE)から得られる線分座標(xPos, yPos)を、refShiftだけ右シフトして得られる座標(xPos>> refShift, yPos>> refShift)に１を設定することにより、線分描画処理に用いるメモリサイズを増大させることを防ぐ効果を奏する。
【０３６３】
以上説明した本実施形態に係る動画像符号化装置２の備えるウェッジレットパターン生成部１４５Ｔ４´は、線分描画部１４６２および回転パターン生成部１４６５´は、さらに、回転とともに反転を用いることにより、ウェッジレットパターンの左上が常に１（もしくは常に０）であるパターンを容易に生成することができる（式Ｒ２の場合）、もしくはウェッジレットパターンの左上が多くの場合に１（もしくは常に０）であるパターンを容易に生成することができる（式Ｒ３の場合）、という効果を奏する。
【０３６４】
以上説明した本実施形態に係る動画像符号化装置２の備える領域フィル部１４６３は、パターンが１である画素を探索し、パターンが１である画素があれば継続する画素を１に設定する。これにより、導出するウェッジレットパターン毎に異なる領域フィル処理を用いることなく、一つの領域フィル処理を共通で用いることができるという効果を奏する。
【０３６５】
以上説明した本実施形態に係る動画像符号化装置２の備えるウェッジレットパターン生成部１４５Ｔ４´´のパターン格納部１４６４´´は、基本パターンについてのみ、一致判定を行い、回転パターンについては、一致判定を行わずに格納するため処理量が少ないという効果を奏する。
【０３６６】
以上説明した本実施形態に係る動画像符号化装置２の備えるウェッジレットパターン生成部１４５Ｔ４Ｂは、基本パターンについてのみ、一致判定を行い、回転パターンについては、一致判定を行わずに格納するため処理量が少ないという効果を奏する。
【０３６７】
なお、上述した実施形態における動画像復号装置１、動画像符号化装置２の一部をコンピュータで実現するようにしても良い。その場合、この制御機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、動画像復号装置１、動画像符号化装置２のいずれかに内蔵されたコンピュータシステムであって、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０３６８】
また、上述した実施形態における動画像復号装置１、動画像符号化装置２の一部、または全部を、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等の集積回路として実現しても良い。動画像復号装置１、動画像符号化装置２の各機能ブロックは個別にプロセッサ化しても良いし、一部、または全部を集積してプロセッサ化しても良い。また、集積回路化の手法はＬＳＩに限らず専用回路、または汎用プロセッサで実現しても良い。また、半導体技術の進歩によりＬＳＩに代替する集積回路化の技術が出現した場合、当該技術による集積回路を用いても良い。
【０３６９】
以上、図面を参照してこの発明の一実施形態について詳しく説明してきたが、具体的な構成は上述のものに限られることはなく、この発明の要旨を逸脱しない範囲内において様々な設計変更等をすることが可能である。
【産業上の利用可能性】
【０３７０】
本発明は、画像データが符号化された符号化データを復号する画像復号装置、および、画像データが符号化された符号化データを生成する画像符号化装置に好適に適用することができる。また、画像符号化装置によって生成され、画像復号装置によって参照される符号化データのデータ構造に好適に適用することができる。
【符号の説明】
【０３７１】
１          動画像復号装置（画像復号装置）
１１        可変長復号部
１１１      ＤＣオフセット情報復号部
１３        逆量子化・逆変換部
１４        予測画像生成部
１４１      予測単位設定部
１４２      参照画素設定部
１４３      スイッチ
１４４      参照画素フィルタ部
１４５      予測画像導出部
１４５Ｄ    ＤＣ予測部
１４５Ｐ    Planar予測部
１４５Ａ    Angular予測部
１４５Ｔ    ＤＭＭ予測部（ＤＭＭ予測装置）
１４５Ｔ２  ウェッジパターン導出部
１４５Ｔ３  ＤＣ予測値導出部
１４５Ｔ４、１４５Ｔ４Ｂ  ウェッジレットパターン生成部
１４５Ｔ５  ウェッジパターンテーブル（バッファ）
１４６１    基本パターン生成部
１４６２    線分描画部
１４６３    領域フィル部
１４６４、１４６４´、１４６４´´    パターン格納部
１４６５、１４６５´、１４６５´´、１４６５Ｂ    回転パターン生成部
１５        加算器
１６        フレームメモリ
２          動画像符号化装置（画像符号化装置）
２１        符号化設定部
２２        逆量子化・逆変換部
２３        予測画像生成部
２４        加算器
２５        フレームメモリ
２６        減算器
２７        変換・量子化部
２９        符号化データ生成部
【図１】
2017216487.tif 000003
【図２】
2017216487.tif 000004
【図３】
2017216487.tif 000005
【図４】
2017216487.tif 000006
【図５】
2017216487.tif 000007
【図６】
2017216487.tif 000008
【図７】
2017216487.tif 000009
【図８】
2017216487.tif 000010
【図９】
2017216487.tif 000011
【図１０】
2017216487.tif 000012
【図１１】
2017216487.tif 000013
【図１２】
2017216487.tif 000014
【図１３】
2017216487.tif 000015
【図１４】
2017216487.tif 000016
【図１５】
2017216487.tif 000017
【図１６】
2017216487.tif 000018
【図１７】
2017216487.tif 000019
【図１８】
2017216487.tif 000020
【図１９】
2017216487.tif 000021
【図２０】
2017216487.tif 000022
【図２１】
2017216487.tif 000023
【図２２】
2017216487.tif 000024
【図２３】
2017216487.tif 000025
【図２４】
2017216487.tif 000026
【図２５】
2017216487.tif 000027
【図２６】
2017216487.tif 000028
【図２７】
2017216487.tif 000029
【図２８】
2017216487.tif 000030
【図２９】
2017216487.tif 000031
【図３０】
2017216487.tif 000032
【図３１】
2017216487.tif 000033
【図３２】
2017216487.tif 000034