JP6188005B2 - 濃淡画像符号化装置及び復号装置 - Google Patents

Description

本発明は、濃淡画像符号化装置及び復号装置に係り、特に、シャープな輪郭を有し輪郭内ではスムーズな分布を持つ奥行き画像、Ｘ線画像又はアニメーション画像等の濃淡画像（動画又は静止画）に好適な濃淡画像符号化装置及び復号装置に関する。

多視点３Ｄ動画データをサーバからクライアントへ送信するシステムでは、クライアント側で、指定した視点に応じて、多視点画像中の選択された２視点の画像が合成されて表示される。このため送信ビットレートが比較的高く、奥行き画像の符号化率を高める必要がある。

奥行き画像では一般に、背景と前景の輪郭を横切る線上で値が急変する。ＤＣＴ変換は、ブロックサイズで空間周波数成分に変換することと、高周波成分の量子化ステップが低周波のそれよりも大きいことから、シャープな輪郭が存在すると、高周波成分の誤差が大きくなって、ブロック全体に影響するノイズ（エイリアス）が発生し、画質が劣化する原因となる。

そこで、下記特許文献１では、背景マスクを用い、背景と前景の境界をまたがないように両領域に平滑フィルタを施して、エイリアスの発生を抑制している。

また、下記非特許文献１では、輪郭の位置を、画素間の位置で検出することにより、より正確に輪郭を検出し、ＤＣＴ（Discrete Cosine Transform）変換の替わりにＧＢＴ（Graph-Based Transform）変換を用いている。

特開２００７−５２６４４号公報

Godwin Shen, et. al., "EDGE-ADAPTIVE TRANSFORMS FOR EFFICIENT DEPTH MAP CODING," IEEE Picture Coding Symposium, Nagoya, Japan, December 2010

奥行き画像は一般に、シャープな輪郭を有し輪郭内ではスムーズに変化するという性質がある。本発明者は、この性質を利用して、エッジマップは解像度を落とさずに可逆圧縮し、輪郭内はダウンサンプリングして低解像度で圧縮することにより、奥行き画像全体として、画質に対する符号化率を高めることができるであろうということを知見した。この方法は、奥行き画像のみならず、この性質を有する画像、例えば、Ｘ線画像やアニメーション画像などの濃淡画像（ＲＧＢアニメーション画像の各成分画像は濃淡画像）にも適用可能である。

本発明の目的はしたがって、符号化率を向上させることが可能な濃淡画像符号化装置及び復号装置を提供することにある。

本発明の第１態様では、濃淡画像を符号化する濃淡画像符号化装置において、
濃淡画像の隣り合う画素間のエッジ点を検出し隣り合うエッジ点を連ねた輪郭を可逆的に符号化する輪郭符号化手段と、
この輪郭を跨がないように、輪郭の内側の濃淡画像を、ローパスフィルタリングした後、ダウンサンプリングすることにより低解像度濃淡画像を取得し、この低解像度濃淡画像をＧＢＴ直交変換し量子化した後にエントロピー符号化する低解像度画像符号化手段とを有し、符号化された輪郭とエントロピー符号化された低解像度濃淡画像との組を、マルチ解像度符号化濃淡画像として出力する。

本発明による濃淡画像符号化装置の第２態様では、第１態様において、濃淡画像は、Ｋｎ×Ｋｎ画素（Ｋは２以上の整数、ｎは２以上の整数）であり、
低解像度画像符号化手段は、着目画素の値を、着目画素を中心とする（２Ｋ−１）×（２Ｋ−１）画素のうち、着目画素から輪郭を跨がない範囲の画素の加重平均値に変換することにより、ローパスフィルタリングを行う。

本発明による濃淡画像符号化装置の第３態様では、第１態様において、濃淡画像は、Ｋｎ×Ｋｎ画素（Ｋは２以上の整数、ｎは２以上の整数）であり、この濃淡画像を（Ｋｎ）²次元ベクトルｘで表したとき、低解像度画像符号化手段は、
濃淡画像上の隣り合う画素を、その輪郭を跨がないように連結して得られるグラフの隣接行列Ａと、その次数行列Ｄと、で表されるラプラス行列Ｌ＝Ｄ−Ａを作成するラプラス行列作成手段と、
このラプラス行列Ｌの固有行ベクトルをその固有値の降順に対応して並べた直交変換行列Ｅを作成する直交変換行列作成手段と、
ベクトルｙ＝Ｅｘの上位ｎ²成分以外を０にしたベクトルｙ’を求め、これを行列Ｅ^tで変換したベクトルｘ’をダウンサンプリングの対象として求めるローパスフィルタリング手段とを有する。

本発明の濃淡画像復号装置の第１態様は、濃淡画像の隣り合う画素間のエッジ点を連ねた輪郭が可逆符号化された高解像度符号化データと、輪郭の内側の濃淡画像がダウンサンプリングされて符号化された低解像度符号化データとの組が、マルチ解像度符号化データとして供給され、このマルチ解像度符号化データを復号して元の解像度の濃淡画像を再構成する濃淡画像復号装置であって、
濃淡画像記憶部と、
エッジマップ記憶部と、
低解像度符号化データを復号し、復号された低解像度濃淡画像をアップサンプリングして濃淡画像記憶部に格納する低解像度濃淡画像復号手段と、
高解像度符号化データを復号して、エッジマップ記憶部内にエッジ点の集合であるエッジマップを再構成するエッジマップ復号手段と、
低解像度濃淡画像の中の画素をＬＲ画素としたとき、アップサンプリングにより挿入された挿入画素を、（１）エッジマップ上の隣り合うエッジ点を連ねた輪郭を跨がず且つ挿入画素に隣接するＬＲ画素の加重平均値で補間し、（２）補間されていない挿入画素が残っていればその挿入画素を、輪郭を跨がず且つ挿入画素に隣接する補間された画素の加重平均値で補間する挿入画素補間手段とを有する。

本発明による濃淡画像復号装置の第２態様では、第１態様において、挿入画素補間手段は、
（３）補間されていない挿入画素のそれぞれについて処理（２）を行った後に、この処理（２）で補間された画素とし、
補間されていない挿入画素が無くなるまで処理（３）を繰り返す。

本発明による濃淡画像復号装置の第３態様では、第１態様において、アップサンプリングで１画素をＫ×Ｋ画素（Ｋは２以上の整数）にする場合、挿入画素補間手段の処理（１）及び（２）での隣接する画素は、挿入画素を中心とする（２Ｋ−１）×（２Ｋ−１）画素である。

上記濃淡画像符号化装置の第１態様の構成によれば、一方では濃淡画像の輪郭を可逆的に符号化し、他方では輪郭の内側の濃淡画像を、輪郭を跨がないようにローパスフィルタリングした後、ダウンサンプリングすることにより低解像度濃淡画像を取得し、この低解像度濃淡画像をＧＢＴ直交変換し量子化した後にエントロピー符号化するので、シャープな輪郭を有し輪郭内ではスムーズに変化するという性質を持った濃淡画像に対し、輪郭と輪郭内の画像の性質に適応した解像度で効率よく符号化することが可能となるという効果を奏する。

上記第２態様の構成によれば、低解像度画像符号化手段が、着目画素の値を、着目画素を中心とする（２Ｋ−１）×（２Ｋ−１）画素のうち、着目画素からその輪郭を跨がない範囲の画素の加重平均値に変換するので、輪郭に応じて比較的簡単にローパスフィルタリングすることができ、これによりエイリアスを低減することができるという効果を奏する。

上記第３態様の構成によれば、輪郭の内側の濃淡画像上の隣り合う画素を、その輪郭を跨がないように連結して得られるグラフに基づくＧＢＴ変換した後、その後のダウンサンプリングに対応した上位ｎ²成分以外を０にすることによりローパスフィルタリングするので、エイリアスを低減することができるという効果を奏する。

上記濃淡画像復号装置の第１態様の構成によれば、低解像度濃淡画像中の画素をＬＲ画素としたとき、アップサンプリングにより挿入された挿入画素を、（１）エッジマップ上の隣り合うエッジ点を連ねた輪郭を跨がず且つ挿入画素に隣接するＬＲ画素の加重平均値で補間し、（２）補間されていない挿入画素が残っていればこの挿入画素を、輪郭を跨がず且つ挿入画素に隣接する補間された画素の加重平均値で補間するので、輪郭の形状に応じてその影響を受けずに挿入画素を補間することができるという効果を奏する。

上記濃淡画像復号装置の第２態様の構成によれば、（３）補間されていない挿入画素のそれぞれについて処理（２）を行った後に、この処理（２）で補間された画素とし、補間されていない挿入画素が無くなるまで処理（３）を繰り返すので、例えば、図１２においてノード１と３に対応したＬＲ画素の値の平均でノード２に対応した挿入画素を補間した後、この値でノード６に対応した挿入画素を補間するということを避けることができ、すなわち、さらにノード１と９に対応したＬＲ画素の値の平均でノード５に対応した挿入画素を補間した後、ノード２とノード５の画素の値の平均でノード６に対応した挿入画素を補間することができ、これにより画素値の分布がスムーズになってノイズの発生を抑制できるという効果を奏する。

上記濃淡画像復号装置の第３態様の構成によれば、任意のアップサンプリング率Ｋ（Ｋは２以上の整数）について、挿入画素を効率よく補間することができるという効果を奏する。

本発明の他の目的、特徴的な構成及び効果は、以下の説明を特許請求の範囲及び図面の記載と関係づけて読むことにより明らかになる。

本発明の実施例１に係る、マルチ解像度の符号化データを生成する濃淡画像符号化装置の概略機能ブロック図である。 図１の装置に対応した濃淡画像復号装置の概略機能ブロック図である。 図１の濃淡画像符号化装置のハードウェア構成を示す概略機能ブロック図である。 （Ａ）は濃淡画像の説明図、（Ｂ）はエッジ検出前のエッジマップの説明図である。 エッジ検出後のエッジマップの説明図である。 図１中のローパスフィルタ部の、ＧＢＴ変換を用いた構成を示す概略機能ブロック図である。 （Ａ）は濃淡画像に対応したグラフのノードとエッジ点との関係を示す説明図であり、（Ｂ）はエッジ点を跨がないように４隣接ノード間を連結したグラフを示す図である。 （Ａ）及び（Ｂ）はそれぞれ、図７（Ｂ）のグラフに対応した隣接行列及びその次数行列の構成の一部を示す説明図である。 （Ａ）は図１中のＧＢＴ変換部の構成を示す概略機能ブロック図であり、（Ｂ）は図２中の逆ＧＢＴ変換部の構成を示す概略機能ブロック図である。 （Ａ）〜（Ｃ）は低解像度濃淡画像用ラプラス行列作成で用いられるグラフの作成方法説明図である。 図２中のＧＢ補間部による画素補間処理を示す概略フローチャートである。 （Ａ）及び（Ｂ）は、図１１のステップＳ１〜Ｓ９のループの１回目でのステップＳ５の補間処理説明図である。 （Ａ）及び（Ｂ）は、図１１のステップＳ１〜Ｓ９のループの２回目でのステップＳ５の補間処理説明図である。 （Ａ）及び（Ｂ）は、図１１のステップＳ１〜Ｓ９のループの３回目でのステップＳ５の補間処理説明図である。 （Ａ）〜（Ｃ）は、本発明の実施例２に係るエッジ適応型ローパスフィルタリングの説明図である。 図１５に示すエッジ適応型ローパスフィルタリングの変形例の説明図である。 （Ａ）及び（Ｂ）は、本発明の実施例２に係るＧＢ補間部による補間処理説明図である。 本発明の実施例２に係るＧＢ補間部による補間処理説明図である。 本発明の実施例２（ＭＲ−ＧＢＴ）と比較対象としての３つの従来法（高解像度（ＨＲ）ＤＣＴ、低解像度（ＬＲ）ＤＣＴ及び高解像度ＧＢＴ）との実験結果を示すＲＤ曲線図である。 本発明の実施例２について、ダウンサンプリング率を１／２、１／３及び１／４にした場合の実験結果を示すＲＤ曲線図である。 上記実験での奥行き画像を用いて２視点画像の２視点の中点から見た画像を合成したときの奥行き濃淡画像（左２つ）とＲＧＢ画像（右２つ）とを示し、上側は従来の低解像度（ＬＤ）ＤＣＴ、下側は高解像度と低解像度をミックスした本実施例２の場合の画像を示す図である。

図３は、本発明の実施例１に係る濃淡画像符号化装置のハードウェア構成を示す概略ブロック図である。

この装置では、ＭＰＵ（Micro Processing Unit）１０がインターフェイス１１を介してＰＲＯＭ（Programmable Read-Only Memory）１２、ＤＲＡＭ（Dynamic Random Access Memory）１３及びＤＭＡＣ（Direct Memory Access Controller）１４に結合されている。ＰＲＯＭ１２は、例えばフラッシュメモリであり、ＯＳ（Operating System）及び濃淡画像符号化のアプリケーションプログラムが格納されている。処理高速化のため、ＰＲＯＭ１２上のプログラムはＤＭＡＣ１４によりＤＲＡＭ１３上に転送されて実行される。ＤＲＡＭ１３は、ワークエリアとしても用いられる。ＤＭＡＣ１４は、ＤＲＡＭ１３内又はＤＲＡＭ１３と外部との間で濃淡画像、エッジマップ及び符号化されたデータを高速転送する。

図３のハードウェアは、ワンチップマイクロコンピュータで構成しても、パーソナルコンピュータやスマートフォンなどのコンピュータの一部で構成してもよい。

図１は、マルチ解像度の符号化データを生成する濃淡画像符号化装置の概略機能ブロック図である。

濃淡画像記憶部２０、エッジマップ記憶部２１、ＨＲ（高解像度）符号化データ記憶部２２、ＬＲ（低解像度）符号化データ記憶部２３及び量子化ベクトル２４はいずれも、ＤＲＡＭ１３内の領域であり、その他のブロックは何れも、ＭＰＵ１０が上記プログラムを実行することにより機能する。

濃淡画像記憶部２０には、図３の構成の内部（ＤＲＡＭ１３）から、又は、外部からインターフェイス１１を介して、濃淡画像が格納される。この濃淡画像は、例えばステレオビデオカメラで撮像された互いに接近した画像の対応点をステレオマッチングにより決定した後、幾何学的に奥行きを算出することにより生成される。

濃淡画像のサイズは、その輪郭データが映像のマクロブロックでの動き補償処理等で利用されることを考慮して、本実施例ではマクロブロックと同一、例えば、８Ｘ８画素となっている。しかし、以下の説明から明らかなように、本願発明は、原理的にはブロックサイズに依存せず、任意のブロックサイズ（フレームサイズを含む）に適用できる。

図１に戻って、本実施例１の第１の特徴は、奥行き画像のような濃淡画像の、シャープな輪郭を有し輪郭内ではスムーズに変化するという性質を利用し、ＨＲ輪郭符号化部３０でエッジマップを可逆符号化し、すなわち解像度を落とさずに符号化し、ＬＲ画像符号化部４０で濃淡画像をダウンサンプリングすることにより低解像度（ＬＲ）で符号化するというマルチ解像度符号化することにより、全体として、画質に対する符号化率を高める点である。

ＨＲ輪郭符号化部３０では、エッジ検出部３１で、濃淡画像２０１の隣り合う画素間のエッジ点を検出してエッジマップを生成し、これをエッジマップ記憶部２１に格納する。

図４（Ａ）は、濃淡画像記憶部２０内の濃淡画像２０１の説明図であり、簡単化の為に、１ブロックが４×４画素である場合を示している。この図中、画素ｄ（ｊ，ｋ）、ｊ＝０〜３、ｋ＝０〜３は、位置（ｊ，ｋ）での濃淡値である。

エッジ検出部３１は、左右上下に隣り合う４画素（４隣接画素）間のそれぞれについて、画素間の差分の絶対値が閾値以上であれば、その画素間にエッジ点が存在すると判定する。図４（Ａ）には、理解を容易にするため、画素間のエッジを太線で示している。例えば|画素ｄ（０，２）−ｄ（０，３）|≧Ｅthであり、ここにＥthは正の閾値である。

図４（Ｂ）は、濃淡画像２０１に対応したエッジマップ記憶部２１内のエッジマップ２１１を示す。

エッジマップ２１１は、画素数が濃淡画像２０１の２×２倍のビットマップである。この図中のハッチングを施した矩形は、濃淡画像２０１内の画素に対応したビットを表しており、×印を付した矩形（斜め隣接画素間）は、エッジ点判定対象外のビットであることを示している。すなわち、白抜きの矩形（ｊが偶数の場合にはｋが偶数のビットのみ、ｊが奇数の場合にはｋが偶数のビットのみ）に相当するエッジビットに、エッジ点有無の判定結果‘１’又は‘０’が格納される。

図５はエッジ判定結果が格納された状態を示す。この図中のドットは、エッジ点有り（ビットが‘１’）を示しており、それぞれ図４（Ａ）中の太線に対応している。

可逆符号化部３２は、このエッジマップを可逆的に圧縮し、すなわち例えば、エッジマップをランレングス符号化し、又は、エッジ点の連鎖を差分チェインコードで表した後にハフマン符号化若しくは算術符号化し、その結果をＨＲ符号化データ記憶部２２に格納する。

ＬＲ濃淡画像符号化部４０では、エッジ適応型ローパスフィルタ部４１が、濃淡画像記憶部２０内の濃淡画像２０１を、エッジ点を跨がないようにローパスフィルタリングする。例えば、エッジ点を跨がないように１画素ずつ走査しながらガウスフィルタなどの平滑フィルタを施してローパスフィルタリングし、又は、図６に示すようなＧＢＴ変換を用いてローパスフィルタリングする。これは、次にダウンサンプリングしたときに、エイリアスの発生を抑制するためである。

次に、本実施例１の第２の特徴である図６の構成を、図７及び図８を参照して説明する。

グラフは、ノードの集合と、ノード間の連結を示すエッジの集合とで表される。図７（Ａ）は、図５中のハッチングを施した画素に対応するノードを○印で示し、図５中のエッジ点であるドットをそのまま転記したものである。４隣接ノード間を、エッジ点を跨がないように連結し、ドットを省略すると、図７（Ｂ）に示す如くなる。この図では、ノードを左上からのラスタスキャン順に、シリアル番号１〜１６をノードにラベル付けしている。

図８（Ａ）は、図７（Ｂ）の隣接行列Ａの一部を示す。

隣接行列Ａは、次数がノード数に等しく、１６Ｘ１６行列である。隣接行列Ａの第ｉ行第ｊ列の要素Ａijの値は、図７（Ｂ）のグラフ上でノードｉとノードｊが連結されていれば１、そうでなければ０となり、隣接行列Ａは対象行列である。ｉ、ｊはいずれも上記ラベルである。

図８（Ｂ）は、この隣接行列Ａの次数行列Ｄの一部を示す。

次数行列Ｄは、隣接行列Ａと同じく１６Ｘ１６行列であり、対角行列であって、対角要素Ｄiiの値は、隣接行列Ａの第ｉ行の要素の値の総和に等しい。

ラプラス行列Ｌ＝Ｄ−Ａは、Ｄ−Ａの内容を直接作成することもできる。また、図７（Ｂ）のグラフは、図５のエッジマップ２１１に対応しているので、グラフを作成せずにエッジマップ２１１に基づいてラプラス行列Ｌを作成することもできる。

図６に戻って、ラプラス行列作成部４１０は、エッジマップ記憶部２１内のエッジマップ２１１に基づいてラプラス行列Ｌを作成する。

変換行列作成部４１１は、ラプラス行列Ｌの固有行ベクトルをその固有値の降順に対応して並べた直交変換行列Ｅ及びその逆行列に等しい転置行列Ｅ^tを作成する。

ここで、濃淡画像２０１上の画素ｄ（ｊ，ｋ）、ｊ＝０〜３、ｋ＝０〜３を、図７（Ｂ）中のノードのラベル順に並べた列ベクトルをベクトルｘとする。

変換部４１２は、ベクトルｘを変換行列Ｅでベクトルｙ＝Ｅｘに変換（ＧＢＴ変換）する。この変換を行う理由は、次にローパスフィルタ４１３で、ベクトルｙの上位８成分以外（第９行以降）を０にしたベクトルｙ’を求めることにより、ローパスフィルタリングするためである。換言すれば、変換行列Ｅはこのような性質をもっている。逆変換部４１４は、ベクトルｙ’を変換行列Ｅの逆行列であるＥ^tで変換したベクトルｘ’を出力する。

このような処理により、ベクトルｘ’は、ベクトルｘに対しエッジ点を跨がずに、ローパスフィルタリングを施した画像となる。

図１に戻って、ダウンサンプリング部４２は、ベクトルｘ’の成分を、図７（Ｂ）の行及び列に関し１行おき及び１列おきに（２Ｘ２画素に１画素の割合で）ダウンサンプリングして、すなわちラベルが１、３、９及びインターフェイス１１の成分のみ取り出して、４行の列ベクトルｕで表される低解像度濃淡画像にする。

ＧＢＴ変換部４３は、列ベクトルｕをＧＢＴ変換してベクトルｖにする。

図９（Ａ）は、ＧＢＴ変換部４３の構成を示す。機能ブロック４３０〜４３２はそれぞれ、図６の機能ブロック４１０〜４１２に対応している。但し、ラプラス行列Ｌ’は４Ｘ４である。ラプラス行列作成部４３０でグラフを作成する場合、図１０（Ａ）に網掛け表示した、ラベルが上記１、３、９及び１１のノードを取り出して、図１０（Ｂ）に示すように連結関係を維持し、図１０（Ｃ）に示すようラベルを付け替えればよい。

図１に戻って、量子化部４４は、ベクトルｖを量子化する。すなわち、ベクトルｖに対応した量子化ベクトル２４が予め設定されており、ＤＣＴ変換の場合と同様に、ｖの各成分を量子化ベクトル２４の対応する成分（量子化ステップ）で量子化する。エントロピー符号化部４５は、ベクトルｖの成分を順次、出現確率に基づき符号化する。

ＧＢＴ変換部４３は、量子化部４４での処理により値が０になる成分を多くして（出現確率を大きくして）、エントロピー符号化部４５での符号化率を高めるためのものであり、この点は、同じ直交変換であるＤＣＴの場合と同様である。

次に、濃淡画像符号化装置に対応した濃淡画像復号装置について説明する。

濃淡画像復号装置のハードウェア構成は、図３と同じであるので、その説明を省略する。

図２は、濃淡画像復号装置の概略機能ブロック図である。

濃淡画像記憶部５０、エッジマップ記憶部５１、ＨＲ符号化データ記憶部５２及びＬＲ符号化データ記憶部５３はいずれも、ＤＲＡＭ１３内の領域であり、その他のブロックは何れも、ＭＰＵ１０が上記プログラムを実行することにより機能する。

ＨＲ符号化データ記憶部５２、ＬＲ符号化データ記憶部５３及び量子化ベクトル５４にはそれぞれ、図３の構成の内部（ＤＲＡＭ１３）から、又は、外部からインターフェイス１１を介して、図１のＨＲ符号化データ記憶部２２、ＬＲ符号化データ記憶部２３及び量子化ベクトル２４の内容が格納される。

復号部６０は、ＨＲ符号化データ記憶部５２内のデータを復号して、エッジマップ記憶部５１内にエッジマップを再構成する。

ＬＲ濃淡画像復号部７０において、エントロピー復号部７１は、ＬＲ符号化データ記憶部５３内のデータを復号し、逆量子化部７２はその結果を、量子化ベクトル５４で逆量子化して、ベクトルｖを再構成する。

図９（Ｂ）は、このベクトルｖを変換する逆ＧＢＴ変換部７３の構成を示す概略機能ブロック図である。

逆ＧＢＴ変換部７３は、ＧＢＴ変換部４３のラプラス行列作成部４３０と同一構成のラプラス行列作成部７３０を備え、エッジマップ記憶部５１内のエッジマップに基づいてラプラス行列Ｌ'を作成する。逆変換行列作成部７３１は、変換行列作成部４３１と同様にして、変換行列Ｅ'を転置した変換行列Ｅ'^-1を作成する。逆変換部７３２は、この変換行列Ｅ'^-1でベクトルｖをベクトルｕに変換する。

図２に戻って、アップサンプリング部７４は、ベクトルｕをアップサンプリングして濃淡画像記憶部５０に格納する。これにより、濃淡画像記憶部５０には、挿入され画素値が欠落している画素（挿入画素）を含むＬＲ濃淡画像が得られる。

ＧＢ補間部７５は、前記格納の完了に応答して、エッジマップ記憶部５１内のエッジマップに基づき、上記図７（Ｂ）と同一の図１０（Ｃ）に示すグラフを作成し、網掛けが表示されていない挿入画素を、直接連結された（エッジ点を跨がず隣接する）ノードの値又は平均値で補間する。すなわち、輪郭の形に応じて補間を行う。この点が、本実施例１の第３の特徴である。

ノードのラベルｉは、画素ｄ（ｊ，ｋ）と、
ｊ＝［（ｉ−１）／４］、ｋ＝（ｉ−１） ｍｏｄ ４
の関係にある。ここに、［］は小数点以下を切り捨てて整数化する演算子であり、ｍｏｄは剰余演算子である。

以下の処理で用いるため、各ノードに、挿入画素であるか否か（低解像度（ＬＲ）画素でないかＬＲ画素か）を示すフラグ及び挿入画素については補間されたか否かを示すフラグを対応付けておく。

図１１は、ＧＢ補間部７５による処理を示す概略フローチャートである。以下、括弧内は図１１中のステップ識別符号である。

（Ｓ０）ブロック内の全挿入画素数１２をダウンカウンタＣに代入する。

（Ｓ１）走査ラベルｉに、初期値２を代入する。

（Ｓ２）ラベルｉのノードへ移動する。

（Ｓ３）このノードが挿入画素のノードであればステップＳ４へ進み、そうでなければステップＳ７へ進む。

（Ｓ４）このノードに直接連結された、挿入画素でないノード（ノードｒ）が１以上存在すれば、ステップＳ５へ進み、そうでなければステップＳ７へ進む。

（Ｓ５）このノードｉに対応する画素ｄ（ｊ，ｋ）を、ノードｒが複数の場合にはそれぞれに対応した画素ｄ（ｐ，ｑ）の平均値で補間し、ノードｒが１個の場合にはこれに対応した画素ｄ（ｐ，ｑ）の値で補間する。ｉの値を記憶しておく。

（Ｓ６）ダウンカウンタＣを１だけデクリメントし、ｉを１だけインクリメントする。

（Ｓ７）ｉ＞１６であればステップＳ８へ進み、そうでなければステップＳ２へ戻る。

（Ｓ８）Ｃ＝０であれば補間処理を終了し、そうでなければステップＳ９へ進む。

（Ｓ９）ステップＳ５で記憶した各ｉのノードを、挿入画素でないノードとし（上記フラグをセットし）、ステップＳ１へ戻る。

図１２（Ａ）は、図１１のステップＳ１〜Ｓ９のループの１回目でのステップＳ５の補間処理を示しており、矢印の始点の画素で、矢印の終点の画素が補間されることを示している。図１２（Ｂ）はステップＳ９の処理が行われた後の状態を示す。

図１３（Ａ）は、上記ループの２回目でのステップＳ５の補間処理を示している。２回目以降は、補間された画素による補間となる。図１３（Ｂ）は、ステップＳ９の処理が行われた後の状態を示す。

図１４（Ａ）は、上記ループの３回目でのステップＳ５の補間処理を示している。図１４（Ｂ）は、ステップＳ９の処理が行われた後の状態を示す。

以上において、ダウンサンプリング部４２によるダウンサンプリング率が１／２である場合を説明したが、これを１／Ｋ、すなわち、Ｋｎ×Ｋｎ濃淡画像（Ｋは２以上の整数、ｎは２以上の整数）をＫｘＫ画素に１画素の割合でダウンサンプリングにする場合の構成は、ローパスフィルタ４１３において、ベクトルｙの上位ｎ²成分以外を０にしたベクトルｙ’を求めることにより、ローパスフィルタリングすること以外は、以上の説明から明らかであるので、その説明を省略する。

なお、ラプラス行列作成の場合と同様に、グラフを作成せずにエッジマップに基づいて図１１の処理を行うこともできる。

また、図１の符号化部３０及び図２の復号部６０はそれぞれ、フレーム単位でエッジマップの符号化及び復号を行い、ＧＢ補間部７５においてもフレーム単位で補間処理を行ってもよい。この場合、フレーム全体としてより適切に補間することができる。

本実施例１の濃淡画像符号化装置によれば、一方ではエッジ検出部３１で濃淡画像のエッジマップを生成し、これを可逆符号化部３２で符号化し、他方では濃淡画像を、エッジマップ２１１上の輪郭を跨がないようにローパスフィル部４１でフィルタリングした後、ダウンサンプリング部４２でダウンサンプリングすることにより低解像度濃淡画像を取得し、該低解像度濃淡画像をＧＢＴ直交変換部４３で変換し量子化した後にエントロピー符号化部４５で符号化するので、シャープな輪郭を有し輪郭内ではスムーズに変化するという性質を持った濃淡画像に対し、輪郭と輪郭内の画像の性質に適応した解像度で効率よく符号化することが可能となるという効果を奏する。

また、ＧＢＴ直交変換部４３で濃淡画像に対し、輪郭を跨がないように隣り合う点を連結したグラフに基づく直交変換をした後、その後のダウンサンプリングに対応した上位ｎ²成分以外を０にすることによりローパスフィルタリングするので、エイリアスを低減することができるという効果を奏する。

さらに、低解像度濃淡画像中の画素をＬＲ画素としたとき、アップサンプリングにより挿入された挿入画素を、図１１のステップＳ１〜Ｓ９のループの１回目で、エッジマップ上のエッジ点を跨がず且つ挿入画素に隣接するＬＲ画素の値又は平均値で補間し、このループの２回目以降で、補間されていない挿入画素を、エッジマップ上のエッジ点を跨がず且つ挿入画素に隣接する補間された画素の値又は平均値で補間するので、輪郭の形状に応じてその影響を受けずに挿入画素を補間することができるという効果を奏する。

また、図のステップＳ９の処理により、例えば、図１２においてノード１と３に対応したＬＲ画素の値の平均でノード２に対応した挿入画素を補間した後、この値でノード６に対応した挿入画素を補間するということを避けることができ、すなわち、さらにノード１と９に対応したＬＲ画素の値の平均でノード５に対応した挿入画素を補間した後、ノード２とノード５の画素の値の平均でノード６に対応した挿入画素を補間することができ、これにより画素値の分布がスムーズになって、ノイズの発生を抑制できるという効果を奏する。

図１５（Ａ）〜（Ｃ）は、本発明の実施例２に係るエッジ適応型ローパスフィルタリング部による処理の説明図である。

このローパスフィルタリング部は、図６のエッジ適応型ローパスフィルタ部４１の替わりに用いられ、空間フィルタの一種である平滑化フィルタとして、矩形で示すサイズ３×３の平均値フィルタを用いている。図１５（Ａ）は、着目画素ｄ（１、３）に平均値フィルタを施している状態を示しており、フィルタ領域内に含まれる画素のうち、着目画素から輪郭を跨がない範囲の画素をフィルタリングの対象とする。すなわち、この例では画素値ｄ（１，３）をｄ’（１，３）＝｛ｗ・ｄ（１，３）＋ｄ（０，３）＋ｄ（２，３）＋ｄ（２，２）＋ｄ（１，２）｝／（４＋ｗ）に変換し（ｄ（１，３）は書き換えない）、変換後の記憶部にこれを書き込む。ｗは１であってもよい。着目画素から見た斜め方向の画素については、エッジ点を図４のような線分に置き換えたときの輪郭を、該着目画素から該斜め方向の画素への直線が跨ぐか否か判定し、跨がないとき、平均化の対象画素とする。

同様に図１５（Ｂ）では、画素値ｄ（１，１）をｄ’（１，１）＝｛ｗ・ｄ（１，１）＋ｄ（０，１）＋ｄ（０，２）＋ｄ（２，０）＋ｄ（１，０）＋ｄ（０，０）｝／（５＋ｗ）に変換し、該変換後の記憶部にこれを書き込む。図１５（Ｃ）は、輪郭が図１５（Ｂ）のそれと異なる場合を示しており、この場合、画素値ｄ（１，１）をｄ’（１，１）＝｛ｗ・ｄ（１，１）＋ｄ（０，１）＋ｄ（０，２）＋ｄ（１，０）＋ｄ（０，０）｝／（４＋ｗ）に変換する。

以上のようにして、該変換後の記憶部に、ローパスフィルタリングされたブロック画像が得られ、これに対し、図１のダウンサンプリング部４２がダウンサンプリングし、上記ベクトルｕに変換する。

図１６は、図１５のローパスフィルタリングの変形例の説明図である。

この変形例では、図７（Ｂ）のグラフに含まれる２つの部分グラフの各ノードに、部分グラフ識別番号をラベルとして付与している。画像に対応してグラフにも図示のように平均値フィルタを対応させ、着目画素に対応したノードのラベルと同一の部分グラフ識別番号を有するノードに対応した画素を、平均値フィルタによる平均化対象画素（輪郭を股がない画素）とする。他の点は、上記の処理と同一である。

ここで、本実施例２では、図１の符号化部３０及び図２の復号部６０はそれぞれ、フレーム単位でエッジマップの符号化及び復号を行う。

図１７（Ａ）、（Ｂ）及び図１８は、本発明の実施例２に係るＧＢ補間部による補間処理の説明図である。

この補間処理も、フレーム単位で行うが、説明の簡単化のため、図１７（Ａ）、（Ｂ）及び図１８では、１ブロックに対する補間処理を示している。

図１１と同様にアップサンプリングされた濃淡画像上の挿入画素及びこれに対応するグラフ上のノードを走査しながら、サイズ３×３の平均値補間フィルタを施して、着目している挿入画素の補間値を求める。図１７（Ａ）は、ラベルが２のノード（着目ノード２）に平均値補間フィルタを対応させた状態を示す。以下ではラベル値ｉのノードに対応した画素値をｄ（<ｉ>）と表記する。ｄ（<ｉ>）を、このフィルタ内の、挿入画素でないノードに対応した画素値の加重平均値として求める。重みｗは、着目画素からの距離に反比例した値とする。

図１７（Ａ）では、着目ノード２に対応した画素値ｄ（<２>）を、ｄ（<２>）＝｛ｄ（<１>）＋ｄ（<３>）｝／２と決定し、図１７（Ｂ）では、着目ノード６に対応した画素値ｄ（<６>）を、ｄ（<６>）＝｛ｄ（<１>）＋ｄ（<３>）＋ｄ（<９>）｝／３と決定する。

このようにして濃淡画像を１回走査すると、図１８に示すようにノード４に対応した画素値ｄ（<４>）のみが未定となる。２回目の走査で、ｄ（<４>）をｄ（<４>）＝｛ｄ（<８>）＋ｄ（<７>）／√２｝／（１＋√２）と決定する。

他の点は、実施例１と同一である。

本実施例２において、アップサンプリング部によるアップサンプリング率が２である場合を説明したが、これをＫ、すなわち１画素をＫｘＫ画素にアップサンプリングにする場合、上記平均値フィルタ及び平均値補間フィルタのサイズをいずれも（２Ｋ−１）×（２Ｋ−１）とする。

次に、本実施例２の実験結果を説明する。

Ｈ．２６４／ＡＶＣ規格の下で奥行き画像を符号化し、復号した。量子化ベクトル５４の各成分の値を互いに同一にし、その値が２４、２８、３２及び３６の場合についてＲＤ（Rate-Distortion）曲線を求めた結果を図１９及び図２０に示す。

図１９は、本実施例２（ＭＲ−ＧＢＴ）と比較対象としての３つの従来法ＨＲ−ＤＣＴ、ＬＲ−ＤＣＴ及びＨＲ−ＧＢＴとの実験結果を示す。ここにＨＲは、ダウンサンプリングを行わなかったことを示し、ＬＲは、エンコーダ側で、ガウスフィルタによりローパスフィルタリングした後、ダウンサンプリングを行い、デコーダ側で、アップサンプリングし、全変動正則化補間を行ったことを示す。本実施例２（ＭＲ−ＧＢＴ）と従来のＬＲ−ＤＣＴのダウンサンプリング率はいずれも１／２にした。

本実施例２の符号化方法は、従来のＨＲ−ＤＣＴと同一のＰＳＮＲ値で比較して、ビットレートを６８％低減（実施例１の場合、６７％低減）することができた。また、従来のＨＲ−ＧＢＴと同一のＰＳＮＲ値で比較して、ビットレートを５５％低減（実施例１の場合、５４％低減）することができた。

図２１は、上記実験での奥行き画像を用いて２視点画像の２視点の中点から見た画像を合成したときの奥行き濃淡画像（左２つ）とＲＧＢ画像（右２つ）であり、上側はＬＤ−ＤＣＴ、下側はＭＲ−ＧＢＴの場合の画像を示す。ＬＲ−ＤＣＴ法は本実施例１のＭＲ−ＧＢＴよりもブロックノイズが多く、また、本実施例２の方がＬＲ−ＤＣＴ法よりも映像がより明瞭である。

図２０は、本実施例２について、ダウンサンプリング率を１／２、１／３及び１／４にした場合の実験結果を示す。ダウンサンプリング率の値が小さくなるほど高圧縮となり画質が低下するが、ダウンサンプリング率をどこまで小さくすべきかは、奥行き画像の輪郭内スムーズさにより異なる。

以上において、本発明の好適な実施例を説明したが、本発明には他にも種々の変形例が含まれ、上記実施例で述べた各構成要素の機能を実現する他の構成を用いたもの、当業者であればこれらの構成又は機能から想到するであろう他の構成も、本発明に含まれる。

例えば、上記実施例１、２ではＧＢＴ変換のグラフにおいて、最大４隣接エッジ点を連結する場合を説明したが、図５中のＸ印を付したビットを有効にして、すなわち図５で斜め方向に隣接する画素間についてもエッジを検出し、グラフ上で最大８隣接エッジ点を連結したもののラプラス行列を用い、図１１の補間処理においてもこのグラフを用いる構成であってもよい。

１０ ＭＰＵ
１１ インターフェイス
１２ ＰＲＯＭ
１３ ＤＲＡＭ
１４ ＤＭＡＣ
２０、５０ 濃淡画像記憶部
２０１ 濃淡画像
２１、５１ エッジマップ記憶部
２１１ エッジマップ
２２、５２ ＨＲ符号化データ記憶部
２３、５３ ＬＲ符号化データ記憶部
２４、５４ 量子化ベクトル
３０ ＨＲ輪郭符号化部
３１ エッジ検出部
３２ 可逆符号化部
４０ ＬＲ濃淡画像符号化部
４１ ローパスフィルタ部
４１０、４３０、７３０ ラプラス行列作成部
４１１、４３１ 変換行列作成部
４１２、４３２ 変換部
４１３ ローパスフィルタ
４１４ 逆変換部
４２ ダウンサンプリング部
４３ ＧＢＴ変換部
４４ 量子化部
４５ エントロピー符号化部
６０ 復号部
７０ ＬＲ濃淡画像復号部
７１ エントロピー復号部
７２ 逆量子化部
７３ 逆ＧＢＴ変換部
７３１ 逆変換行列作成部
７３２ 逆変換部
７４ アップサンプリング部
７５ ＧＢ補間部
Ａ 隣接行列
Ｌ、Ｌ' ラプラス行列
Ｅ、Ｅ' 変換行列
ｘ、ｘ'、ｙ、ｙ' ベクトル

Claims (8)

1. 濃淡画像を符号化する濃淡画像符号化装置において、
   前記濃淡画像の隣り合う画素間のエッジ点を検出し、隣り合うエッジ点を連ねた輪郭を可逆的に符号化する輪郭符号化手段と、
   前記輪郭を跨がないように前記輪郭の内側の濃淡画像をローパスフィルタリングした後、ダウンサンプリングすることにより低解像度濃淡画像を取得し、前記低解像度濃淡画像をＧＢＴ直交変換して量子化した後にエントロピー符号化する低解像度画像符号化手段と、を有し、
   前記符号化された輪郭と前記エントロピー符号化された低解像度濃淡画像との組を、マルチ解像度符号化濃淡画像として出力する
   ことを特徴とする濃淡画像符号化装置。
2. 前記濃淡画像は、Ｋｎ×Ｋｎ画素（Ｋは２以上の整数、ｎは２以上の整数）であり、
   前記低解像度画像符号化手段は、着目画素の値を、前記着目画素を中心とする（２Ｋ−１）×（２Ｋ−１）画素のうち、前記着目画素から前記輪郭を跨がない範囲の画素の加重平均値に変換することにより、前記ローパスフィルタリングを行う、
   ことを特徴とする請求項１に記載の濃淡画像符号化装置。
3. 前記濃淡画像は、Ｋｎ×Ｋｎ画素（Ｋは２以上の整数、ｎは２以上の整数）であり、
   前記濃淡画像を（Ｋｎ）²次元ベクトルｘで表したとき、
   前記低解像度画像符号化手段は、
   前記濃淡画像上の隣り合う画素を、前記輪郭を跨がないように連結して得られるグラフの隣接行列Ａと、その次数行列Ｄと、で表されるラプラス行列Ｌ＝Ｄ−Ａを作成するラプラス行列作成手段と、
   前記ラプラス行列Ｌの固有行ベクトルをその固有値の降順に対応して並べた直交変換行列Ｅを作成する直交変換行列作成手段と、
   ベクトルｙ＝Ｅｘの上位ｎ²成分以外を０にしたベクトルｙ’を求め、これを行列Ｅ^tで変換したベクトルｘ’を前記ダウンサンプリングの対象として求めるローパスフィルタリング手段と、
   を有することを特徴とする請求項１に記載の濃淡画像符号化装置。
4. 前記濃淡画像は、Ｋｎ×Ｋｎ画素（Ｋは２以上の整数、ｎは２以上の整数）であり、
   前記低解像度濃淡画像は、ｎ×ｎ画素であり、
   前記低解像度濃淡画像をｎ²次元ベクトルｕで表したとき、
   前記低解像度画像符号化手段は、
   前記ダウンサンプリングされた濃淡画像上の隣り合う画素を、前記濃淡画像の隣り合う画素間のエッジ点を１／Ｋの率でダウンサンプリングしたときのエッジ点を連ねた縮小輪郭を跨がないように連結して得られるグラフの隣接行列Ａ'と、その次数行列Ｄ'と、で表されるラプラス行列Ｌ'＝Ｄ'−Ａ'を作成するラプラス行列作成手段と、
   前記ラプラス行列Ｌ'の固有行ベクトルをその固有値の降順に対応して並べた直交変換行列Ｅ'を作成する直交変換行列作成手段と、
   前記ベクトルｕを、ｖ＝Ｅ’ｕなるベクトルｖに直交変換する直交変換手段と、を有して、
   前記低解像度濃淡画像を前記ＧＢＴ直交変換することを特徴とする請求項１〜３のいずれか１項に記載の濃淡画像符号化装置。
5. 濃淡画像の隣り合う画素間のエッジ点を連ねた輪郭が可逆符号化された高解像度符号化データと、前記輪郭を跨がないように前記輪郭の内側の前記濃淡画像がダウンサンプリングされて符号化された低解像度符号化データとの組が、マルチ解像度符号化データとして供給され、前記マルチ解像度符号化データを復号して元の解像度の濃淡画像を再構成する濃淡画像復号装置であって、
   濃淡画像記憶部と、
   エッジマップ記憶部と、 前記低解像度符号化データを復号し、復号された低解像度濃淡画像をアップサンプリングして前記濃淡画像記憶部に格納する低解像度濃淡画像復号手段と、
   前記高解像度符号化データを復号して、前記エッジマップ記憶部内に前記エッジ点の集合であるエッジマップを再構成するエッジマップ復号手段と、
   前記低解像度濃淡画像の中の画素をＬＲ画素としたとき、前記アップサンプリングにより挿入された挿入画素を、（１）前記輪郭を跨がず且つ前記挿入画素に隣接するＬＲ画素の加重平均値で補間し、（２）補間されていない挿入画素が残っていれば前記挿入画素を、前記輪郭を跨がず且つ前記挿入画素に隣接する補間された画素の加重平均値で補間する挿入画素補間手段と、
   を有することを特徴とする濃淡画像復号装置。
6. 前記挿入画素補間手段は、
   （３）補間されていない挿入画素のそれぞれについて処理（２）を行った後に、この処理（２）で補間された画素とし、
   補間されていない挿入画素が無くなるまで、処理（３）を繰り返す、
   ことを特徴とする請求項５に記載の濃淡画像復号装置。
7. 前記アップサンプリングで１画素をＫ×Ｋ画素（Ｋは２以上の整数）にする場合、前記挿入画素補間手段における、の処理（１）及び（２）での前記隣接する画素は、前記挿入画素を中心とする（２Ｋ−１）×（２Ｋ−１）画素である、
   ことを特徴とする請求項５に記載の濃淡画像復号装置。
8. 前記元の解像度の濃淡画像は、Ｋｎ×Ｋｎ画素（Ｋは２以上の整数、ｎは２以上の整数）であり、
   前記低解像度濃淡画像は、ｎ×ｎ画素であり、
   前記低解像度濃淡画像をｎ²次元ベクトルｖで表したとき、
   前記低解像度濃淡画像復号手段は、
   前記アップサンプリングされた濃淡画像中の挿入画素を除く画素に対応する点の集合のうち隣り合う点を、前記エッジマップ上の隣り合うエッジ点を連ねた輪郭を跨がないように連結したエッジの隣接行列Ａ'とその次数行列Ｄ'とで表されるラプラス行列Ｌ'＝Ｄ'−Ａ'を作成するラプラス行列作成手段と、
   前記ラプラス行列Ｌ'の固有列ベクトルをその固有値の降順に対応して並べた直交逆変換行列Ｅ'を作成する直交変換行列作成手段と、
   前記低解像度濃淡画像のベクトルｖを、ｕ＝Ｅ’ｖなるベクトルｕに直交逆変換する直交逆変換手段と、
   を有し前記ベクトルｕは前記アップサンプリングの対象であることを特徴とする請求項５乃至７のいずれか１項に記載の濃淡画像復号装置。