(57)【特許請求の範囲】
【請求項１】
画像の画素にインデックスが割り当てられた符号化対象データにおいて、隣接する前記インデックスの境界の長さをインデックス同士の接続の強さを接続強度値として算出する接続強度算出部と、
前記インデックスの境界の長さが大きいインデックスの組ほど、インデックスに割り当てられる画素値の差が小さくなるように画素値を割り当てる画素値割当部と、
を備える非可逆符号化装置。
【請求項２】
画像の画素にインデックスが割り当てられた符号化対象データにおいて、割り当てられたインデックス同士の接続の強さを示す接続強度値を算出する接続強度算出部と、
前記接続強度値に基づいて、前記インデックスの各々に対して画素値を割り当てる画素値割当部と、
を備え
符号化が、非可逆符号化である場合、
前記画素値割当部は、前記接続強度値によって示される接続強度に応じて、前記非可逆符号化を行った後に残りやすい画素値を前記インデックスに対して割り当て、
前記画素値割当部は、
前記インデックスに対する前記画素値の割り当てパターンの全てを生成して出力する割り当てパターン発生部と、
前記全ての前記画素値の割り当てパターンごとに、前記インデックス間の前記画素値の差を算出し、前記接続強度算出部が算出する前記接続強度値と、当該接続強度値に対応する前記インデックス間の前記画素値の差とに基づいて接続コストを算出するコスト算出部と、
前記接続コストが最小となる前記画素値の割り当てパターンを最適な前記画素値の割り当てパターンとして選択する最適パターン選択部と、
を備える非可逆符号化装置。
【請求項３】
前記コスト算出部は、
前記接続強度値と、当該接続強度値に対応する前記インデックス間の前記画素値の差とに基づいて、前記接続コストを求める際に、前記画素値のマンハッタン距離、または、ユークリッド距離を前記接続コストとして算出する、請求項２に記載の非可逆符号化装置。
【請求項４】
前記画像とみなされる前記符号化対象データは、マップ情報であり、
前記マップ情報に基づいて、前記画像を生成して出力する画像生成部を備え、
前記接続強度算出部は、
前記マップ情報に含まれる前記インデックス同士の接続の強さを示す接続強度値を算出し、
前記最適パターン選択部は、
選択する最適な前記画素値の割り当てパターンを外部と前記画像生成部に出力し、
前記画像生成部は、
前記マップ情報と、最適な前記画素値の割り当てパターンとに基づいて、前記画像を生成して出力する、請求項２又は３に記載の非可逆符号化装置。
【請求項５】
画像の画素にインデックスが割り当てられた符号化対象データにおいて、隣接する前記インデックスの境界の長さをインデックス同士の接続の強さを接続強度値として算出する接続強度算出ステップと、
前記インデックスの境界の長さが大きいインデックスの組ほど、インデックスに割り当てられる画素値の差が小さくなるように画素値を割り当てる画素値割当ステップと、
を有する非可逆符号化方法。
【請求項６】
請求項１から４のいずれか一項に記載の非可逆符号化装置としてコンピュータを動作させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、非可逆符号化装置、非可逆符号化方法、及びコンピュータプログラムに関する。
【背景技術】
【０００２】
画像符号化技術や映像符号化技術は、通常の自然画以外の情報を圧縮することに適用することができる。例えば、テクスチャ合成を利用した符号化においては、テクスチャ合成を行う場所を指定するマップ情報をあわせて送る構成となっているが、このマップ情報の圧縮に対して従来の画像符号化技術を利用できる。例えば、非特許文献１に示す例では、１枚の画像を５種類のテクスチャ領域に分割している。なお、５種類のテクスチャ領域の１領域は、テクスチャ合成を行わない領域となっている。この分割の状態を示すマップ情報を画像とみなして従来の画像符号化法を利用して高い圧縮率で情報圧縮を行っている。
【０００３】
このような従来の画像符号化や映像符号化の手法により圧縮されるマップ情報とは、前述の通り、画像とみなして扱うことができる情報であり、かつ画素値そのものには直接の意味はなく、その画素値に紐付けられた別の物理量に意味がある情報である。別の物理量とは、例えば、上記のように５種類のテクスチャ領域に分割する場合においては、テクスチャの種別となる。また、画像とみなされるマップ情報では、その画素値の取り得る範囲が自然画より大幅に少ない点も特徴である。例えば、８ｂｉｔＲＧＢの自然画では画素値の取り得る範囲は約１，６７７万パターンもあるのに対し、上記の５種類のテクスチャ領域に分割したマップ情報を画像とみなした場合、画素値は５パターンあればよい。
【０００４】
従来の画像符号化を用いて上記のようなマップ情報を符号化する場合、マップ情報を画像に変換する作業が必要となる。以下の説明では、マップ情報のインデックスを画素値へと変換するこの作業を「画像化」、この画像をマップ情報のインデックスに戻す作業を「マップ化」と記載する。ここで、図６を参照しつつ、マップ情報をモノクロ画像に画像化する場合について説明する。図６に示すマップ情報は、インデックスとして“ａ”、“ｂ”、“ｃ”及び“ｄ”の記号が付与される４つの領域から構成されており、画像化とはこの“ａ”〜“ｄ”の領域それぞれに具体的な画素値を与えることをいう。
【０００５】
画素値を与える手法としては、例えば、マップ情報を左上からラスタ順にスキャンし、検出した領域から順に画素値を“０”、“１０”、“２０”等のように与えてもよいし、各領域の面積を求めて、面積が大きい領域から順に画素値を“０”、“１０”、“２０”等のように与えるようにしてもよい。図６の例の場合、どちらの手法で画素値を与えたとしても、領域ａ＝画素値“０”、領域ｂ＝画素値“１０”、領域ｃ＝画素値“２０”、領域ｄ＝画素値“３０”という形で画像化される。
【０００６】
画像化されたマップ情報は、従来の画像符号化方式、例えばＪＰＥＧ（Joint Photographic Experts Group）やＰＮＧ（Portable Network Graphics）等の符号化方式により簡単に圧縮することができる。ＰＮＧ等の可逆圧縮方式で符号化した場合、マップ情報への復号は単純に上記の逆の手順を行うことになる。すなわち、ＰＮＧのデコーダを用いて圧縮データを画像に復号後、各画素値について、その画素値に紐付けられた領域種別に置き換えていくことでマップ情報に戻すことができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】佐々木崇元、谷田隆一、清水淳、"Texture合成符号化における非合成領域決定法の検討",  PCSJ P-2-11, 2015, p48-p49
【非特許文献２】Emmy-Charlotte Forster, Thomas Lowe, Stephan Wenger, Marcus Magnor, “RGB-Guided Depth Map Compression via Compressed Sensing and Sparse Coding”, (4) Picture Coding Symposium, 2015 May.31.2015-June.3.2015,Page.1〜4
【非特許文献３】Wenjing Zhu, Oscar C. Au, Wei Dai, Haitao Yang, Rui Ma, Luheng Jia, Jin Zeng, Pengfei Wan, “PALETTE-BASED COMPOUND IMAGE COMPRESSION IN HEVC BY EXPLOITING NON-LOCAL SPATIAL CORRELATION”, 2014 IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP), 2014, p7398-p7402
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ＪＰＥＧ等の非可逆な圧縮を行う画像符号化方式では、急峻なエッジの再現性が良くないことが知られている。例えば、図６のマップ情報を、上記の通り、領域ａ＝画素値“０”、領域ｂ＝画素値“１０”、領域ｃ＝画素値“２０”、領域ｄ＝画素値“３０”として画像化し、ＪＰＥＧ等の非可逆圧縮を行うとする。この非可逆圧縮により、領域ｂ＝画素値１０と領域ｄ＝画素値“３０”の間のエッジが急峻であるため、このエッジがなまってしまい画素値“２０”に近い画素が符号化の結果として出現してしまうことがある。
【０００９】
このように、ＪＰＥＧ等の非可逆圧縮方式で符号化した場合、復号画像には画像の劣化が生じるため、画素値として“０”、“１０”、“２０”、“３０”以外の値が発生することからマップ化の処理において、復号画像の画素値を一度、“０”、“１０”、“２０”、“３０”の中で最も近い値に丸めてから領域“ａ”〜“ｄ”にマッピングすることが行われる。
【００１０】
図６に示す例に、この丸める処理が適用されると、マップ情報へ戻すマップ化の過程で、領域ｂ＝画素値“１０”と領域ｄ＝画素値“３０”に現れた画素値“２０”に近い画素は、画素値“２０”に丸められる。そのため、図７に示すように、復号されたマップ情報において、領域“ｄ”の周囲に領域“ｃ”が現れてしまう可能性がある。このマップ情報が、上記した非特許文献１で示したテクスチャ種別を示していた場合、領域“ｄ”の周囲に意図しない領域“ｃ”に対応するテクスチャが貼り付けられ、視覚的に大きく劣化した画像となる。
【００１１】
以上のように、画像圧縮にＪＰＥＧ等の非可逆圧縮で符号化する方式を適用した場合、符号化に起因する画質劣化によって、復号したマップ情報から必要な情報が失われてしまう等の大きなダメージを与えてしまうという問題がある。
【００１２】
上記事情に鑑み、本発明は、マップ情報等の画素ごとにインデックスが割り当てられて画像とみされる符号化対象データを符号化する場合に、復号したマップ情報から必要な情報が失われることを低減する非可逆符号化装置、非可逆符号化方法、及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１３】
本発明の一態様は、画像の画素にインデックスが割り当てられた符号化対象データにおいて、隣接する前記インデックスの境界の長さをインデックス同士の接続の強さを接続強度値として算出する接続強度算出部と、前記インデックスの境界の長さが大きいインデックスの組ほど、インデックスに割り当てられる画素値の差が小さくなるように画素値を割り当てる画素値割当部と、
を備える非可逆符号化装置である。
【００１５】
本発明の一態様は、画像の画素にインデックスが割り当てられた符号化対象データにおいて、割り当てられたインデックス同士の接続の強さを示す接続強度値を算出する接続強度算出部と、前記接続強度値に基づいて、前記インデックスの各々に対して画素値を割り当てる画素値割当部と、を備え符号化が、非可逆符号化である場合、前記画素値割当部は、前記接続強度値によって示される接続強度に応じて、前記非可逆符号化を行った後に残りやすい画素値を前記インデックスに対して割り当て、前記画素値割当部は、前記インデックスに対する前記画素値の割り当てパターンの全てを生成して出力する割り当てパターン発生部と、前記全ての前記画素値の割り当てパターンごとに、前記インデックス間の前記画素値の差を算出し、前記接続強度算出部が算出する前記接続強度値と、当該接続強度値に対応する前記インデックス間の前記画素値の差とに基づいて接続コストを算出するコスト算出部と、前記接続コストが最小となる前記画素値の割り当てパターンを最適な前記画素値の割り当てパターンとして選択する最適パターン選択部と、を備える非可逆符号化装置である。
【００１７】
本発明の一態様は、上記の非可逆符号化装置であって、前記コスト算出部は、前記接続強度値と、当該接続強度値に対応する前記インデックス間の前記画素値の差とに基づいて、前記接続コストを求める際に、前記画素値のマンハッタン距離、または、ユークリッド距離を前記接続コストとして算出する。
【００１８】
本発明の一態様は、上記の非可逆符号化装置であって、前記画像とみなされる前記符号化対象データは、マップ情報であり、前記マップ情報に基づいて、前記画像を生成して出力する画像生成部を備え、前記接続強度算出部は、前記マップ情報に含まれる前記インデックス同士の接続の強さを示す接続強度値を算出し、前記最適パターン選択部は、選択する最適な前記画素値の割り当てパターンを外部と前記画像生成部に出力し、前記画像生成部は、前記マップ情報と、最適な前記画素値の割り当てパターンとに基づいて、前記画像を生成して出力する。
【００１９】
本発明の一態様は、画像の画素にインデックスが割り当てられた符号化対象データにおいて、隣接する前記インデックスの境界の長さをインデックス同士の接続の強さを接続強度値として算出する接続強度算出ステップと、前記インデックスの境界の長さが大きいインデックスの組ほど、インデックスに割り当てられる画素値の差が小さくなるように画素値を割り当てる画素値割当ステップと、を有する非可逆符号化方法である。
【００２０】
本発明の一態様は、上記の非可逆符号化装置としてコンピュータを動作させるためのコンピュータプログラムである。
【発明の効果】
【００２１】
この発明によれば、マップ情報等の画素ごとにインデックスが割り当てられて画像とみされる符号化対象データを非可逆で符号化する場合に、復号したマップ情報から必要な情報が失われることを低減することが可能となる。
【図面の簡単な説明】
【００２２】
【図１】本発明における符号化システム１００の構成を示すブロック図である。
【図２】画像化部の内部構成を示すブロック図である。
【図３】画像化部の処理の流れを示すフローチャートである。
【図４】接続強度値の算出結果の一例を示す図である。
【図５】画素値の割り当てパターンの一例を示す図である。
【図６】マップ情報の一例を示す図である。
【図７】マップ情報に対して非可逆圧縮を施した場合の一例を示す図である。
【発明を実施するための形態】
【００２３】
以下、本発明の実施形態について図面を参照して説明する。図１は、本発明における符号化システム１００の構成を示すブロック図である。符号化システム１００は、符号化装置１と、復号装置２とを備える。符号化装置１は、画像化部１０とＪＰＥＧ圧縮部２０とを備える。画像化部１０は、外部から供給される符号化対象データであるマップ情報に対して、マップ情報に含まれる各インデックスに対してユニークな画素値を割り当てることにより画像化を行って画像データを出力する。また、画像化部１０は、インデックスと画素値の対応情報を出力する。ＪＰＥＧ圧縮部２０は、画像化部１０が出力する画像データをＪＰＥＧにより圧縮してＪＰＥＧ圧縮データを生成して出力する。ここで、外部から供給されるマップ情報とは、例えば、インデックスが２次元状に並べられたマップ情報であり、図６の例では、領域“ａ”、“ｂ”、“ｃ”及び“ｄ”に含まれる各々の画素には“ａ”、“ｂ”、“ｃ”及び“ｄ”の記号で示されるインデックスが付与されているものとする。
【００２４】
復号装置２は、ＪＰＥＧ復号部３０とマップ化部４０とを備える。ＪＰＥＧ復号部３０は、符号化装置１が出力するＪＰＥＧ圧縮データが与えられると復号を行う。そして、ＪＰＥＧ復号部３０は、復号した画像データをマップ化部４０に出力する。マップ化部４０は、ＪＰＥＧ復号部３０が出力する画像データと、符号化装置１が出力する対応情報とに基づいて、画像データに含まれる画素値を対応するインデックスに逆変換してマップ情報を復号する。また、マップ化部４０は、逆変化の際に、各々の画素値を、インデックスと対応づけられている画素値の中で一番近い画素値に丸めてからインデックスに逆変換する。
【００２５】
図２は、符号化装置１が備える画像化部１０の内部構成を示すブロック図である。画像化部１０は、画像生成部１１、接続強度算出部１２、接続強度記憶部１３及び画素値割当部１４を備える。画素値割当部１４は、割り当てパターン発生部１４１、コスト算出部１４２、最適パターン選択部１４３、最適パターン記憶部１４４及び制御部１４５を備える。接続強度算出部１２は、外部から供給されるマップ情報に基づいて、マップ情報に含まれるインデックス間の全ての接続強度値を算出する。ここで、接続強度値とは、インデックス間の接続関係の強さを示す値である。インデックス間の接続関係としては、例えば、各インデックスが隣接しているか否かの情報を適用することができ、接続関係の強さとしては、例えば、隣接する各インデックス間の境界の長さを適用することができる。また、接続強度算出部１２は、算出した接続強度値を接続強度記憶部１３に書き込む。接続強度記憶部１３は、接続強度算出部１２が書き込む接続強度値を記憶する。
【００２６】
割り当てパターン発生部１４１は、制御部１４５からの開始信号を受けて、インデックスの各々に対する画素値の割り当てパターンを１つずつ生成してコスト算出部１４２と最適パターン選択部１４３とに出力する。また、割り当てパターン発生部１４１は、全ての画素値の割り当てパターンを生成して出力すると終了信号を制御部１４５に出力する。コスト算出部１４２は、接続強度記憶部１３から接続強度値を読み出す。また、コスト算出部１４２は、割り当てパターン発生部１４１が生成して出力する画素値の割り当てパターンと、読み出した接続強度値とに基づいて、画素値の割り当てパターンごとの接続コストを算出する。また、コスト算出部１４２は、算出した割り当てパターンに対応する接続コストを最適パターン選択部１４３に出力する。
【００２７】
最適パターン選択部１４３は、制御部１４５から開始を示す制御信号を受けると、内部変数Ｃｍｉｎを十分大きな値で初期化する。また、最適パターン選択部１４３は、コスト算出部１４２が出力する接続コストの値と、Ｃｍｉｎとを比較する。また、最適パターン選択部１４３は、比較の結果、接続コストがＣｍｉｎより小さい場合、当該接続コストをＣｍｉｎとし、当該接続コストに対応する画素値の割り当てパターンを画素値の割り当てパターンとして最適パターン記憶部１４４に書き込む。なお、最適パターン選択部１４３は、最適パターン記憶部１４４が既に他の画素値の割り当てパターンを記憶している場合、当該他の画素値の割り当てパターンを削除してから新たな画素値の割り当てパターンを書き込む。また、最適パターン選択部１４３は、制御部１４５から終了を示す制御信号を受けた場合であって、かつ、全ての接続コストに対する比較の処理が終了している場合、最適パターン記憶部１４４が記憶する画素値の割り当てパターンを最適な画素値の割り当てパターンとして読み出す。また、最適パターン選択部１４３は、最適パターン記憶部１４４から読み出した最適な画素値の割り当てパターンをインデックスと画素値の対応情報として画像生成部１１と外部に出力する。最適パターン記憶部１４４は、処理が開始される際に、制御部１４５によって初期化される。また、最適パターン記憶部１４４は、最適パターン選択部１４３が書き込む画素値の割り当てパターンを記憶する。
【００２８】
制御部１４５は、処理が開始されると、開始信号を割り当てパターン発生部１４１に出力する。また、制御部１４５は、処理が開始されると、最適パターン選択部１４３に開始を示す制御信号を出力する。また、制御部１４５は、処理が開始されると、最適パターン記憶部１４４を初期化、すなわち最適パターン記憶部１４４が画素値の割り当てパターンを記憶している場合、当該画素値の割り当てパターンを削除する。また、制御部１４５は、割り当てパターン発生部１４１から終了信号を受けると、最適パターン選択部１４３に終了を示す制御信号を出力する。
【００２９】
画像生成部１１は、外部から供給されるマップ情報と、最適パターン選択部１４３が出力する最適な画素値の割り当てパターン、すなわちインデックスと画素値の対応情報とに基づいて、マップ情報のインデックスを対応する画素値に置き換えて画像を生成して外部に出力する。
【００３０】
（画像化部による処理）
次に、図３から図５を参照しつつ、画像化部１０による処理について説明する。図３は、画像化部１０の処理の流れを示すフローチャートである。処理が開始されると、画素値割当部１４の制御部１４５は、開始信号を割り当てパターン発生部１４１に出力し、また、最適パターン選択部１４３に開始を示す制御信号を出力する。また、制御部１４５は、最適パターン記憶部１４４を初期化する。最適パターン選択部１４３は、制御部１４５から開始を示す制御信号を受けると内部変数Ｃｍｉｎを十分大きな値で初期化する（Ｓ１）。
【００３１】
接続強度算出部１２は、外部から供給されるマップ情報を受けて、マップ情報の全インデックス間の接続強度値を算出する。上述したように、接続強度値として、隣接するインデックス間の境界の長さが適用される場合、マップ情報として、図６に示すマップ情報が与えられるとき、接続強度算出部１２は、図６のマップ情報の左上から順にマップ情報の各要素をスキャンする。接続強度算出部１２は、マップ情報の要素となる各画素をスキャンしつつ、異なるインデックスと隣接する画素の数をカウントしていくことで、各インデックス間の境界の長さを算出することができる。
【００３２】
図４は、接続強度算出部１２が算出した接続強度値を示す図である。隣接していないインデックス間の接続強度値は「０」となる。図４に示すように、“ａ”のインデックスと“ｂ”のインデックスの接続強度値は「１００」であり、“ａ”のインデックスと“ｃ”のインデックスの接続強度値は、「３０」であり、“ｂ”と“ｄ”の接続強度値は、「５」となる。それ以外のインデックス間は隣接していないため、接続強度値は「０」となる。すなわち、インデックス“ａ”とインデックス“ｂ”の間の境界の長さが最も長いため、インデックス“ａ”とインデックス“ｂ”の接続が最も強い接続であることを示している。また、インデックス“ａ”とインデックス“ｃ”との接続強度値が２番目に強く、インデックス“ｂ”とインデックス“ｄ”との接続強度値が３番目に強い接続であることを示している。接続強度算出部１２は、全ての接続強度値を算出する（Ｓ２）。接続強度算出部１２は、算出した接続強度値をインデックス間を示す情報に関連付けて接続強度記憶部１３に書き込んで記憶させる。
【００３３】
割り当てパターン発生部１４１は、制御部１４５から開始信号を受けると、画素値の割り当てパターンを生成する（Ｓ３）。例えば、図６に示すマップ情報の場合、４つのインデックス“ａ”〜“ｄ”に対して４種類の画素値の割り当てを行うことから、生成する画素値の割り当てパターン数は全部で４Ｐ４＝２４通りとなる。ここで、割り当てる画素値を｛１，２，３，４｝とした場合、割り当てパターン発生部１４１は、図５に示すような画素値の割り当てパターンを、パターン番号が「１」のパターンから順にパターン番号が「２４」までのパターンを生成して出力する。なお、割り当てパターン発生部１４１による画素値の割り当てパターンの生成は、パターン番号が「１」のパターンからでなくてもよく、ランダムに生成して出力するようにしてもよい。また、以下の説明では、図５に示すパターン番号の任意の番号を示す場合、パターン番号「ｉ」として示し、具体的な、パターン番号、例えば、１番のパターン番号を示す場合、パターン番号「ｉ＝１」として示す。
【００３４】
コスト算出部１４２と最適パターン選択部１４３は、割り当てパターン発生部１４１が生成して出力する全ての画素値の割り当てパターンについて、パターン番号「ｉ＝１」から順に「ｉ」を１ずつ増やして、以下のステップＳ４、Ｓ５、Ｓ６の処理を繰り返す（ループＬ１−１〜Ｌ１−２）。割り当てパターン発生部１４１から、パターン番号が「ｉ」の画素値の割り当てパターンが供給されると、コスト算出部１４２は、パターン番号が「ｉ」の画素値の割り当てパターンと、接続強度記憶部１３に記憶されているインデックス間ごとの接続強度値とに基づいて、全接続コストを算出する（Ｓ４）。
【００３５】
例えば、パターン番号「ｉ＝１」の場合、図５に示すように、ａ＝１、ｂ＝２、ｃ＝３、ｄ＝４が、各インデックスの画素値として割り当てられる画素値の割り当てパターンとなる。コスト算出部１４２が算出する接続コストとして、ここでは、例えば、マンハッタン距離を適用し、インデックス間ごとに、画素値の差と接続強度値との積を算出し、算出した積の和を接続コストとして算出する。また、以下の説明において、パターン番号が「ｉ」の画素値の割り当てパターンに対する全接続コストをＣ（ｉ）で表す。このとき、コスト算出部１４２が算出するパターン番号「ｉ＝１」に対応する全接続コストＣ（１）は、Ｃ（１）＝「ａとｂ間の接続コスト」＋「ａとｃ間の接続コスト」＋「ａとｄ間の接続コスト」＋「ｂとｃ間の接続コスト」＋「ｂとｄ間の接続コスト」＋「ｃとｄ間の接続コスト」となる。数値を代入して計算すると、Ｃ（１）＝ａｂｓ（１−２）×１００＋ａｂｓ（１−３）×３０＋ａｂｓ（１−４）×０＋ａｂｓ（２−３）×０＋ａｂｓ（２−４）×５＋ａｂｓ（３−４）×０＝１７０となる。コスト算出部１４２は、パターン番号「ｉ＝１」の画素値の割り当てパターンの情報、すなわち｛１，２，３，４｝と、算出したパターン番号「ｉ＝１」に対応する全接続コストの値とを最適パターン選択部１４３に出力する。
【００３６】
最適パターン選択部１４３は、コスト算出部１４２が出力する画素値の割り当てパターンの情報と、全接続コストの値とを受けると、全接続コストの値と、内部変数Ｃｍｉｎとを比較し、ＣｍｉｎがＣ（ｉ）より大きいか否かを判定する（Ｓ５）。最適パターン選択部１４３は、ＣｍｉｎがＣ（ｉ）よりも大きいと判定した場合（Ｓ５：ＹＥＳ）、ＣｍｉｎにＣ（ｉ）の値を代入し、パターン番号「ｉ」の画素値の割り当てパターンを最適パターン記憶部１４４に書き込んで記憶させる（ステップＳ６）。その後、全ての画素値の割り当てパターンの処理が終わるまで、ループＬ１−１〜Ｌ１−２の間のステップＳ４〜Ｓ６の処理を繰り返す。一方、ステップＳ５において、最適パターン選択部１４３が、ＣｍｉｎがＣ（ｉ）以下であると判定した場合（ステップＳ５：ＮＯ）、全ての画素値の割り当てパターンの処理が終わるまで、ループＬ１−１〜Ｌ１−２の間のステップＳ４〜Ｓ６の処理を繰り返す。
【００３７】
ここで、パターン番号「ｉ＝１」と「ｉ＝２」の場合についてみると、上述した通り、パターン番号「ｉ＝１」についての全接続コストは、１７０となる。Ｃｍｉｎの初期値は十分に大きな値とされているため、ステップＳ５の処理において、最適パターン選択部１４３は、Ｃｍｉｎ＞Ｃ（１）であると判定し、Ｃｍｉｎに１７０を代入し、パターン番号「ｉ＝１」の画素値の割り当てパターンを最適パターン記憶部１４４に書き込んで記憶させる。ステップＳ４に戻り、割り当てパターン発生部１４１からパターン番号「ｉ＝２」についての画素値の割り当てパターンが出力されると、コスト算出部１４２は、Ｃ（２）を算出する。パターン番号「ｉ＝２」は、図５に示すようにａ＝１、ｂ＝２、ｃ＝４、ｄ＝３であるから、コスト算出部１４２は、全接続コストを、Ｃ（２）＝ａｂｓ（１−２）×１００＋ａｂｓ（１−４）×３０＋ａｂｓ（２−３）×５＝１９５として算出する。ステップＳ５の判定処理において、最適パターン選択部１４３は、Ｃｍｉｎ＝１７０と、Ｃ（２）＝１９５とを比較し、Ｃｍｉｎの値は、Ｃ（２）の値以下であるため、最適パターン選択部１４３は、ステップＳ６には進まず、ステップＳ４からの処理が繰り返される。図５に示すパターン番号が「２４」の画素値の割り当てパターンまでの処理が終了した時点で、最適パターン選択部１４３の内部変数Ｃｍｉｎは、パターン番号「ｉ＝９」の全接続コストである１３５となり、最適パターン記憶部１４４には、パターン番号「ｉ＝９」のａ＝２、ｂ＝３、ｃ＝１、ｄ＝４が記憶されることになる。
【００３８】
割り当てパターン発生部１４１は、全ての画素値の割り当てパターンの出力が終了すると、終了信号を制御部１４５に出力する。制御部１４５は、割り当てパターン発生部１４１から終了信号を受けると、終了を示す制御信号を最適パターン選択部１４３に出力する。最適パターン選択部１４３は、最後の画素値の割り当てパターンに対してコスト算出部１４２が出力する全接続コストの処理が終了しており、かつ制御部１４５から終了を示す制御信号を受けていると、その時点で最適パターン記憶部１４４が記憶している画素値の割り当てパターンを読み出す。最適パターン選択部１４３は、最適パターン記憶部１４４から読み出した画素値の割り当てパターンを最適な画素値の割り当てパターンとして、インデックスと画素値の対応情報とし、画像生成部１１と外部とに出力する。画像生成部１１は、外部から供給されるマップ情報と、最適パターン選択部１４３が出力するインデックスと画素値の対応情報とに基づいて、マップ情報を画像化し、画像として外部に出力する（ステップＳ６）
【００３９】
上記の実施形態の構成により、画素の各々にインデックスが割り当てられているマップ情報を画像とみなし、接続強度算出部１２が、マップ情報に含まれるインデックスの接続強度値を算出して接続強度記憶部１３に書き込んで記憶させる。画素値割当部１４において、割り当てパターン発生部１４１は、インデックスの数と同じ個数の画素値を選択し、インデックスに割り当てる画素値の割り当てパターンの全てを生成して出力する。コスト算出部１４２は、接続強度記憶部１３に記憶されているインデックス間の接続強度値と、割り当てパターン発生部１４１が出力する画素値の割り当てパターンとに基づいて、画素値の割り当てパターンごとの接続コストを算出する。最適パターン選択部１４３は、コスト算出部１４２が算出する接続コストの中で値の小さい接続コストに対応する画素値の割り当てパターンを選択して最適パターン記憶部１４４に書き込んで記憶させる。最適パターン選択部１４３は、最後に、最適パターン記憶部１４４に記憶されている接続コストが最小の画素値の割り当てパターンを最適な画素値の割り当てパターンとして読み出し、読み出した画素値の割り当てパターンをインデックスと画素値の対応情報として出力する。以上のように、画素値割当部１４は、接続強度値によって示される接続強度に応じて、非可逆符号化を行った後に残りやすい画素値をインデックスに対して割り当てる。ここで、非可逆符号化を行った後にその画素が残るかどうかは割り当てた画素値の隣接関係に基づく。例えば、画素値の差が小さいほどそのまま画素値が残りやすい。画像生成部１１は、マップ情報と、最適パターン選択部１４３が出力するインデックスと画素値の対応情報とに基づいて画像を生成して出力する。ＪＰＥＧ圧縮部２０は、画像生成部１１が出力する画像に対してＪＰＥＧ圧縮を行って外部に出力する。
【００４０】
これにより、マップ情報等の画素ごとにインデックスが割り当てられて画像とみされる符号化対象データを符号化する際に、符号化に起因する画質劣化によって、復号したマップ情報から必要な情報が失われる可能性を低減することが可能となる。
上記の図６のマップ情報に基づく具体例では、パターン番号「ｉ＝９」が最適なインデックスと画素値の対応情報として選択されている。パターン番号「ｉ＝９」の画素値の割り当てパターン、すなわちａ＝２、ｂ＝３、ｃ＝１、ｄ＝４を適用して、図６のマップ情報を画像化すると、隣接するインデックス間の画素値差が全て１となる。したがって、この画像化されたデータに対して非可逆圧縮を行い、領域の境界がなまったとしても、図７に示す領域ｄの周りに領域ｃが現れる可能性が低い対応情報が得られていることが分かる。
【００４１】
換言すると、本実施形態では、インデックス同士の隣接境界が長いところほど、画素値差が小さくなるように各インデックスに対して画素値の割り当てが行われる構成となっている。そのため、符号化により画質の劣化が生じたとしてもマップ化の過程で、図７のように無関係なインデックスが飛び地のように生じる可能性が大きく低減される。
また、本実施形態の構成を適用することで、マップ情報におけるインデックスが複雑な隣接関係になっていたとしても、最適な画素値の配分を機械的に求めることが可能となる。
【００４２】
なお、上記の実施形態では、コスト算出部１４２が、接続コストを算出する手段として、２つのインデックスに割り当てられた画素値間のマンハッタン距離と、当該２つのインデックスの接続強度値との積を求めて算出するようにしているが、本発明の構成は、当該実施の形態に限られない。例えば、マンハッタン距離の代わりにユークリッド距離を適用するようにしてもよい。
【００４３】
また、上記の実施形態では、図６に示すマップ情報を例として、４つのインデックスａ〜ｄに対して、４種類の画素値の割り当てを行うため、画素値の割り当てパターン数が、４Ｐ４＝２４通りの構成について説明したが、本発明の構成は、当該実施の形態に限られない。例えば、マップ情報に５つのインデックスが含まれており、５種類の画素値の割り当てを行う場合、割り当てパターン発生部１４１は、５Ｐ５＝１２０通りの画素値の割り当てパターンを生成して出力することになる。
【００４４】
また、上記の実施形態では、最適パターン選択部１４３は、コスト算出部１４２が算出する接続コストが、Ｃｍｉｎより小さい場合、当該接続コストに対応する画素値の割り当てパターンを選択して最適パターン記憶部１４４に書き込んで記憶させるようにしているが、本発明の構成は、当該実施の形態に限られない。例えば、画素値の割り当てパターンそのものを最適パターン記憶部１４４に書き込んで記憶させるのではなく、当該接続コストに対応するパターン番号「ｉ」を記憶させるようにしてもよい。この場合、割り当てパターン発生部１４１が生成して出力する図５のパターン番号ごとの画素値の割り当てパターンのテーブルを他の記憶部に記憶させておく等の構成が必要となる。そして、最適パターン選択部１４３が、処理の最後で、最適パターン記憶部１４４が記憶しているパターン番号を読み出し、読み出したパターン番号に基づいて、当該他の記憶部を参照して、画素値の割り当てパターンを読み出し、インデックスと画素値の対応情報として出力することになる。
【００４５】
また、上記の実施形態では、図３のステップ１０５の処理において、Ｃｍｉｎの値がＣ（ｉ）の値を超過しているか否かの判定を行っているが、超過しているか否かの判定は、一例であり、例えば、Ｃｍｉｎの値がＣ（ｉ）の値以上であるか否かの判定を行うようにしてもよい。
【００４６】
また、上記の実施形態では、インデックスとして、“ａ”、“ｂ”、“ｃ”及び“ｄ”という記号が画素ごとに付与されている構成としているが、本発明の構成は、当該実施の形態に限られず、“１”、“２”、“３”及び“４”等の番号で示されるインデックスであってもよい。
【００４７】
また、上記の実施形態では、接続強度算出部１２は、インデックスに対応する領域ごとの境界の長さを接続強度値として算出しているが、本発明の構成は、当該実施の形態に限られず、インデックスに優先度がある場合、当該優先度に応じて境界の長さによって決定される接続強度値をインデックスの優先度によって補正するようにしてもよい。
【００４８】
また、上記の実施形態の構成では、テクスチャ合成を利用した符号化、すなわちマップ情報に画素値を割り当てて画像化を行って符号化を行うようにしているが、本発明の構成は、当該実施の形態に限られない。例えば、デプスマップやＳＣＣ（Screen Content Coding）スクリーンコンテンツ符号化のパレットモードに適用するようにしてもよい。
【００４９】
ここで、デプスマップとは、奥行き情報を有する画像や映像に関して、その奥行きを数値化したデータのことであり、デプスマップは、画像・映像と共に保存される。デプスマップは、基本的に、その画素の奥行きを数値化したものであり、画像や映像によっては数値がかなり離散的になる。この場合、離散値をそのまま圧縮するより、一旦、インデックスに置き換えて離散値を連続的な数値とすることで、符号化難度が下がり、圧縮効率が高まる可能性がある。デプスマップの例として、例えば、非特許文献２のＦｉｇ．２（ｂ）等がある。
【００５０】
また、ＳＣＣのパレットモードとは、ＨＥＶＣ（High Efficiency Video Coding）に導入されている符号化ツールの中の技術の１つである。例えば、ゲーム画面やパソコンの画面を動画にするＳＣＣに関しては、通常の自然画と異なる性質が多く存在する。そのため映像符号化標準規格ＨＥＶＣでは、別途、ＳＣＣ向けのプロファイルを定義して専用の符号化ツールをいくつか導入している。ＳＣＣのパレットモードとは、前述したようにその符号化ツールの中の技術である。例えば、ＳＣＣの対象となるパソコンの画面では自然画と違い、かなり色数がかなり限定されている場合が多い。そのため、ＳＣＣのパレットモードでは、その限定された色にインデックスを割り当てて、画素値をインデックスの並びで表現し、このインデックスの並びと、当該インデックスに対応する色の情報を符号化して送信する（例えば、このインデックスと色の分離は、非特許文献３のＦｉｇ．１を参照）。ＨＥＶＣ規格のＳＣＣ向けに採用されているパレットモードでは、色情報に関しては非可逆圧縮を行うため劣化を伴うが、インデックスの並びは可逆圧縮のため非劣化である。したがって、本実施形態による手法を用いることで、劣化の発生を小さく抑えることができるため、インデックスの並び対しても非可逆圧縮を適用することができる。
【００５１】
また、上記のデプスマップやＳＣＣのパレットモード以外に、レイヤ画像に適用するようにしてもよく、これら以外に、画素値がインデックスを表すような画像であればどのようなものであっても幅広く適用することが可能である。
【００５２】
上述した実施形態における符号化装置１をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【００５３】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００５４】
１…符号化装置，２…復号装置，１０…画像化部，１１…画像生成部，１２…接続強度算出部，１３…接続強度記憶部，１４…画素値割当部，１４１…割り当てパターン発生部，１４２…コスト算出部，１４３…最適パターン選択部，１４４…最適パターン記憶部，１４５…制御部，３０…ＪＰＥＧ圧縮部，３０…ＪＰＥＧ復号部，４０…マップ化部，１００…符号化システム
【図１】
0006591933.tif 000002
【図２】
0006591933.tif 000003
【図３】
0006591933.tif 000004
【図４】
0006591933.tif 000005
【図５】
0006591933.tif 000006
【図６】
0006591933.tif 000007
【図７】
0006591933.tif 000008