(57)【要約】【課題】画像データの輪郭の符号化率を向上させる。【解決手段】追跡した直近のＫ個（≧３）のエッジ点の回帰直線Ｌと平行で向きが追跡方向である基準ベクトルＲＶと各次エッジ候補ベクトルＮＶｓ、ＮＶｒ及びＮＶｌとのなす角度αが小さいほど値が大きくなる関数ｐ（α，κ）の値を次エッジ候補ベクトルの出現確率として求める。パラメータκは、次エッジ候補のそれぞれについての角度αの最小値が小さいほど関数の半値幅が狭くなるように定められている。【選択図】図７
2014072720.tif 000002
【特許請求の範囲】
【請求項１】
画像データ内の輪郭データが供給され、該輪郭のエッジ点を追跡しながら、現エッジ点からこれに隣接する第１所定数の次エッジ候補点へのそれぞれのベクトルである次エッジ候補ベクトルの出現確率に基づき該輪郭データを符号化する算術符号化手段を備えた適応型算術輪郭符号化装置において、
追跡した直近の第２所定数（≧３）のエッジ点の回帰直線と平行で向きが追跡方向である基準ベクトルを決定する基準ベクトル決定手段と、
該基準ベクトルと各次エッジ候補ベクトルとのなす角度αが小さいほど値が大きくなる関数ｐ（α）の値を該次エッジ候補ベクトルの該出現確率として求める出現確率算出手段と、
をさらに有することを特徴とする適応型算術輪郭符号化装置。
【請求項２】
該関数ｐ（α）は、該第１所定数の次エッジ候補のそれぞれについての該角度αの最小値が小さいほど該関数の半値幅が狭くなるパラメータを有することを特徴とする請求項１に記載の適応型算術輪郭符号化装置。
【請求項３】
該関数ｐ（α）は、フォン・ミーゼス確率密度関数ｐ（α）＝ＥＸＰ（κｃｏｓ（α−μ））／｛２πＩ0（κ）｝であり、ここにＩ0（κ）は ０次の第一種変形ベッセル関数であり、μ＝０としたものであり、該パラメータはκであることを特徴とする請求項２に記載の適応型算術輪郭符号化装置。
【請求項４】
該輪郭の各エッジ点は、画素間のエッジ点であり、
該輪郭の追跡開始エッジ点から、このエッジ点に最も近いエッジ点へのベクトルを追跡開始エッジベクトルとして決定する追跡開始エッジベクトル決定手段をさらに備え、
該符号化データはさらに、該追跡開始エッジベクトルのデータを含むことを特徴とする請求項１乃至３のいずれか１つに記載の適応型算術輪郭符号化装置。
【請求項５】
該基準ベクトル決定手段は、該回帰直線に対する該直近の第２所定数のエッジの分散が閾値以上である場合に該第２所定数の値を、該分散が該閾値未満であるときの値よりも小さい値にすることを特徴とする請求項１乃至４のいずれか１つに記載の適応型算術輪郭符号化装置。
【請求項６】
該算術符号化手段は、数直線上の半開区間を、該第１所定数の次エッジ候補ベクトルの出現確率に比例して分割し、分割された半開区間のうち、次エッジ候補ベクトル先端が次エッジ点と一致するものに対応する半開区間で該数直線上の半開区間を更新するとともに、該現エッジ点を該次エッジ点で更新する処理を繰り返して、該輪郭データを、最終的な半開区間又はこれに含まれる値と繰り返し回数とを含む符号化データに一意的に変換する、
ことを特徴とする請求項１乃至５のいずれか１つに記載の適応型算術輪郭符号化装置。
【請求項７】
画像データ内の輪郭を算術符号化した輪郭符号化データが供給され、輪郭符号化データを
復号しながら該輪郭を構成するエッジ点を追跡再生する適応型算術輪郭復号装置において、
復号された直近の第２所定数（≧３）のエッジ点の回帰直線と平行で向きが追跡方向である基準ベクトルを決定する基準ベクトル決定手段と、
該基準ベクトルと現エッジ点からこれに隣接する第１所定数の次エッジ点候補へのそれぞれの次エッジ候補ベクトルとのなす角度αで定まる、それぞれの次エッジ候補ベクトルの出現確率を、角度αが小さいほど値が大きくなる関数ｐ（α）の値として求める出現確率算出手段と、
該第１所定数の次エッジ候補ベクトルのそれぞれの出現確率に基づき次エッジ点を決定し、該現エッジ点を該次エッジ点で更新する処理を繰り返すことにより該輪郭符号化データを復号する算術復号手段と、
を有することを特徴とする適応型算術輪郭復号装置。
【請求項８】
該輪郭符号化データは、数直線上の半開区間、又は該半開区間内の点と繰り返し回数とを含み、
該算術復号手段は、該第１所定数の次エッジ候補ベクトルのそれぞれの出現確率で、数直線上の半開区間を比例分割し、該半開区間、又は該半開区間内の点が属する、該比例分割した半開区間の１つに対応した次エッジ候補ベクトルの先端を次エッジ点と決定し、該現エッジ点を該次エッジ点で更新するとともに、該数直線上の半開区間を該１つの分割半開区間で更新する処理を、該分割半開区間に該数直線上の半開区間が含まれる最大回数又は該繰り返し回数だけ繰り返す、
ことを特徴とする請求項７に記載の適応型算術輪郭復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像上の輪郭を追跡しながら適応的に算術符号化する適応型算術輪郭符号化装置及びこれに対応した復号装置に関する。
【背景技術】
【０００２】
多視点３Ｄ動画データをサーバからクライアントへ送信するシステムでは、クライアント側で、指定した視点に応じて、多視点画像中の選択された２視点の画像が合成されて表示される。このため送信ビットレートが比較的高く、奥行き画像の符号化率を高める必要がある。
【０００３】
奥行き画像に含まれる輪郭を適応算術符号化する場合、従来では、輪郭を追跡しながら、
現エッジ点からこれに隣接する複数の次エッジ候補点へのそれぞれのベクトルである次エッジ候補ベクトルの出現率を、統計的に更新し、これに基づいて、輪郭を算術符号化していた。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−５２６４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、輪郭を追跡しながら局所的かつ幾何学的に見ると、前記統計的な出現率は出現確率として信頼性が低く、結果として、効率よく符号化することができず、このような観点から改善の余地があることを本願発明者は知見した。
【０００６】
本発明の目的はしたがって、画像データの輪郭の符号化率を向上させることが可能な適応型算術輪郭符号化装置及びこれに対応した復号装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明の第１態様では、画像データ内の輪郭データが供給され、該輪郭のエッジ点を追跡しながら、現エッジ点からこれに隣接する第１所定数の次エッジ候補点へのそれぞれのベクトルである次エッジ候補ベクトルの出現確率に基づき該輪郭データを符号化する算術符号化手段を備えた適応型算術輪郭符号化装置において、
追跡した直近の第２所定数（≧３）のエッジ点の回帰直線と平行で向きが追跡方向である基準ベクトルを決定する基準ベクトル決定手段と、
該基準ベクトルと各次エッジ候補ベクトルとのなす角度αが小さいほど値が大きくなる関数ｐ（α）の値を該次エッジ候補ベクトルの該出現確率として求める出現確率算出手段とをさらに有する。エッジ点は、実施例３のみなしエッジ点であってもよい。
【０００８】
本発明による適応型算術輪郭符号化装置の第２態様では、第１態様において、該関数ｐ（α）は、該第１所定数の次エッジ候補のそれぞれについての該角度αの最小値が小さいほど該関数の半値幅が狭くなるパラメータを有する。
【０００９】
本発明による適応型算術輪郭符号化装置の第３態様では、第１又は２態様において、該基準ベクトル決定手段は、該回帰直線に対する該直近の第２所定数のエッジの分散が閾値以上である場合に該第２所定数の値を、該分散が該閾値未満であるときの値よりも小さい値にする。
【発明の効果】
【００１０】
上記第１態様の構成によれば、追跡した直近の第２所定数（≧３）のエッジ点の回帰直線と平行で向きが追跡方向である基準ベクトルと各次エッジ候補ベクトルとのなす角度αが小さいほど値が大きくなる関数ｐ（α）の値を次エッジ候補ベクトルの出現確率として求めるので、エッジ点追跡途中の局所的な幾何学的特徴が出現確率に反映され、これにより、輪郭データを効率よく符号化することが可能になるという効果を奏する。
【００１１】
上記第２態様の構成によれば、関数ｐ（α）は、次エッジ候補のそれぞれについての該角度αの最小値が小さいほど該関数の半値幅が狭くなるパラメータを有するので、確率分布をエッジ点追跡途中の局所的な幾何学的状況に応じてパラメータκが自動的にかつ適切に決定され、出現確率の信頼性がより高くなり、これにより、輪郭データをさらに効率よく符号化することが可能になるという効果を奏する。
【００１２】
上記第３態様の構成によれば、該回帰直線に対する該直近の第２所定数のエッジの分散が閾値以上である場合に該第２所定数の値を、該分散が該閾値未満であるときの値よりも小さい値にするので、輪郭の屈曲部分において出現確率の信頼性がより高くなり、これにより、輪郭データをさらに効率よく符号化することが可能になるという効果を奏する。
【００１３】
本発明の他の目的、特徴的な構成及び効果は、以下の説明を特許請求の範囲及び図面の記載と関係づけて読むことにより明らかになる。 
【図面の簡単な説明】
【００１４】
【図１】本発明の実施例１に係る適応型算術輪郭符号化装置の概略機能ブロック図である。
【図２】図１の装置の１ブロックに対する処理手順を示す概略フローチャートである。
【図３】本発明の実施例１に係る適応型算術輪郭符号化装置のハードウェア構成を示す概略ブロック図である。
【図４】１フレーム内の奥行きマップの濃淡画像を、輪郭が検出されたブロックの矩形とともに示す説明図である。
【図５】（Ａ）は１ブロックが４×４画素の奥行きマップ説明図、（Ｂ）はこのマップに対応したエッジマップの説明図である。
【図６】（Ａ）は画素間エッジ点が格納されたエッジマップの説明図、（Ｂ）はエッジ点追跡開始エッジベクトル決定説明図である。
【図７】（Ａ）は４隣接チェインコード説明図、（Ｂ）はブロック内の１つの輪郭の最初の３エッジ点Ｐ０〜Ｐ２追跡後の次エッジ点符号化説明図、（Ｃ）は６エッジ点Ｐ０〜Ｐ５追跡後の次エッジ点符号化説明である。
【図８】（Ａ）〜（Ｃ）はそれぞれαmがαm１、αm2、αm3（αm１＞αm2＞αm3＝π／２）である場合の出現確率ｐ（α，κ）を示す図である。
【図９】（Ａ）〜（Ｃ）は、３つの次エッジ候補ベクトル及びαmが互いに同一で基準ベクトルＲＭが互いに異なる場合を示す説明図、（Ｄ）はエッジ点Ｐ１からＰ３までの算術符号化説明図である。
【図１０】本発明の実施例１に係る適応型算術輪郭符号化装置の概略機能ブロック図である。
【図１１】図１０の装置の１ブロックに対する処理手順を示す概略フローチャートである。
【図１２】本発明の実施例２に係る奥行きマップ上のエッジ点追跡説明図である。
【図１３】本発明の実施例３に係る奥行きマップ上のみなしエッジ点追跡説明図である。
【図１４】本発明の実施例３に係るみなしエッジ点符号化説明である。
【図１５】実施例１による符号化の効果を２つの従来の符号化と対比して示す実験結果説明図であって、（Ａ）はビデオカメラの撮影対象がバレーとブレイクダンサーズである場合のそれぞれの１エッジ点当たりの平均符号化ビット数のテーブルを示す図、（Ｂ）及び（Ｃ）はそれぞれ該バレーと該ブレイクダンサーズの深さデータを符号化したときのビットレートに対するＰＳＮＲのグラフを示す図である。
【実施例１】
【００１５】
図３は、本発明の実施例１に係る適応型算術輪郭符号化装置のハードウェア構成を示す概略ブロック図である。
【００１６】
この装置では、ＭＰＵ（Micro Processing Unit）１０がインターフェイス１１を介してＰＲＯＭ（Programmable Read-Only Memory）１２、ＤＲＡＭ（Dynamic Random Access Memory）１３及びＤＭＡＣ（Direct Memory Access Controller）１４に結合されている。ＰＲＯＭ１２は、例えばフラッシュメモリであり、ＯＳ（Operating System）及び輪郭適応算術符号化のアプリケーションプログラムが格納されている。処理高速化のため、ＰＲＯＭ１２上のプログラムはＤＭＡＣ１４によりＤＲＡＭ１３上に転送されて実行される。ＤＲＡＭ１３は、ワークエリアとしても用いられる。ＤＭＡＣ１４はＤＲＡＭ１３内又はＤＲＡＭ１３と外部との間で奥行きマップ、エッジマップ及び符号化エッジマップのデータを高速転送する。
【００１７】
図３のハードウエアは、ワンチップマイクロコンピュータで構成しても、パーソナルコンピュータやスマートフォンなどのコンピュータの一部で構成してもよい。
【００１８】
図１は、適応型算術輪郭符号化装置の概略機能ブロック図である。
【００１９】
奥行きマップ記憶部２０、符号化エッジマップ記憶部２１及びエッジマップ記憶部２２はいずれも、ＤＲＡＭ１３内の領域であり、その他のブロックは何れも、ＭＰＵ１０が上記プログラムを実行することにより機能する。制御部２３はメインルーチンであり、機能ブロック２４〜２９はそのサブルーチンである。
【００２０】
奥行きマップ記憶部２０には、図３の構成の内部（ＤＲＡＭ１３）から、又は、外部からインターフェイス１１を介して、奥行きマップが格納される。この奥行きマップは、例えばステレオビデオカメラによる互いに接近した画像について、ステレオマッチングにより対応点を決定して幾何学的に奥行きを算出することにより生成される。
【００２１】
奥行きマップのサイズは、その輪郭データが映像のマクロブロックでの動き補償処理等で利用されることを考慮して、本実施例ではマクロブロックと同一、例えば、１６Ｘ１６画素となっている。しかし、以下の説明から明らかなように、本願発明は、原理的にはブロックサイズに依存せず、任意のブロックサイズに適用できる。
【００２２】
図４は、１フレーム内の奥行きマップの具体例を示すものであり、図中の各矩形領域は、画素間の差分の絶対値が閾値以上であるエッジが検出されたマクロブロックを示す。
【００２３】
奥行きマップは、１画素が８ビットの濃淡画像であり、図４では奥行きが小さいほど明るく表現されている。奥行きマップ上の一般的な性質として、輪郭がシャープで、輪郭で分割される各領域内の画素値がほぼ一様になるという特徴がある。
【００２４】
図１に戻って、奥行きマップ記憶部２０への１ブロック分の奥行きマップの格納が完了すると、奥行きマップ格納完了のイベントが制御部２３に通知される。制御部２３はこれに応答して、この奥行きマップに関し、直接又は他の機能ブロックを介し処理を行うことにより、符号化エッジマップ記憶部２１内に、符号化されたエッジマップ（輪郭のみを符号化したもの）を生成する。
【００２５】
図２は、１ブロックに対する制御部２３（図１の装置）の処理手順を示す概略フローチャートである。以下、括弧内は図２中のステップ識別符号である。なお、記憶部２１及び２２は、初期化されている。
【００２６】
（Ｓ０）制御部２３はまず、画素間エッジ点検出部２４を呼び出す。画素間エッジ点検出部２４はこれに応答して、エッジカウンタＥＣをゼロクリアしておき、奥行きマップ記憶部２０内の奥行きマップに対し、画素間の差分処理を行ってエッジ点の存否を判定し、その結果をエッジマップ記憶部２２に格納するとともに、エッジ点が存在すると判定する毎に、エッジカウンタＥＣを１だけインクリメントする。
【００２７】
図５（Ａ）は、奥行きマップ記憶部２０内の奥行きマップ２０１の説明図であり、簡単化の為に、１ブロックが４×４画素である場合を示している。この図中、画素ｄ（ｊ，ｋ）、ｊ＝０〜３、ｋ＝０〜３は、位置（ｊ，ｋ）での奥行き値である。画素間エッジ点検出部２４は、左右上下に隣り合う４画素（４隣接画素）間のそれぞれについて、画素間の差分の絶対値が閾値以上であれば、その画素間にエッジ点が存在すると判定する。図５（Ａ）には、理解を容易にするため、画素間のエッジを太線で示している。例えば|ｄ（２，０）−ｄ（３，０）|≧Ｅthであり、ここにＥthは正の閾値である。
【００２８】
図５（Ｂ）は、奥行きマップ２０１に対応したエッジマップ記憶部２２内のエッジマップ２２１を示す。
【００２９】
エッジマップ２２１は、画素数が奥行きマップ２０１の２×２倍のビットマップである。この図中のハッチングを施した矩形は、奥行きマップ２０１内の画素に対応したビットを表しており、×印を付した矩形（斜め隣接画素間）は、エッジ点判定対象外のビットであることを示している。すなわち、白抜きの矩形（ｊが偶数の場合にはｋが偶数のビットのみ、ｊが奇数の場合にはｋが偶数のビットのみ）に相当する有効ビットに、エッジ点有無の判定結果‘１’又は‘０’が格納される。図６（Ａ）はエッジ判定結果が格納された状態を示す。この図中のドットは、エッジ点有り（有効ビットが‘１’）を示しており、それぞれ図５（Ａ）中の太線に対応している。以下、位置（ｊ，ｋ）の有効ビットをｅ（ｊ，ｋ）と表記する。
【００３０】
（Ｓ１）制御部２３は、半開区間［ｓ，ｔ）を［０，１）に初期化する。この半開区間は、ブロック内の隣接するエッジ点を追跡して得られる１つの輪郭と対応付けられ、半開区間［０，１）は、輪郭が存在しないことを示している。また、チェインコードカウンタＣＣＣをゼロクリアする。
【００３１】
（Ｓ２）制御部２３は次いで、追跡開始エッジベクトル決定部２５を呼び出す。追跡開始エッジベクトル決定部２５はこれに応答して、図６（Ｂ）に示すように、エッジマップ記憶部２２内をラスタースキャンして、値が‘１’である最初のエッジ点Ｐ（０）、すなわちｅ（ｊ0，ｋ0）＝‘１’を検出するとともに、エッジカウンタＥＣを１だけデクリメントする。なお、エッジマップを作成せずに、濃淡画像をラスタースキャンしながらエッジ点を検出してもよい。
【００３２】
次に、このエッジ点Ｐ（０）の左下に隣接するｅ（ｊ0−１，ｋ0−１）が‘１’であればこれをエッジ点Ｐ（１）とし、‘０’のとき、エッジ点Ｐ（０）の右下に隣接するｅ（ｊ0＋１，ｋ0＋１）が‘１’であればこれをエッジ点Ｐ（１）とする。そして、エッジカウンタＥＣを１だけデクリメントするとともに、エッジ点Ｐ（０）からＰ（１）へのエッジベクトルＥＶ（Ｐ（０），Ｐ（１））を、追跡開始エッジベクトルと決定する。
【００３３】
このベクトルを、この方向の、図７（Ａ）に示すチェインコード０〜３のうちの対応するものＣＣ０と、エッジ点Ｐ０の座標（ｊ0，ｋ0）との組に変換して、符号化エッジマップ記憶部２１に格納する。また、現エッジ点Ｐ（ｉ）のインデックスｉに、１を代入する。
【００３４】
エッジ点Ｐ（０）の左下及び右下に隣接するいずれのエッジ点も‘０’であれば、エッジ点Ｐ（０）をノイズとみなし、その値ｅ（ｊ0，ｋ0）を‘０’にするととともに、エッジカウンタＥＣを１だけデクリメントする。
【００３５】
（Ｓ３）ステップＳ２で追跡開始エッジベクトルＥＶ（Ｐ（０），Ｐ（１））が存在したとき（このとき、ＥＣ≧２）であればステップＳ４へ進み、そうでなければステップＳ１４へ進む。
【００３６】
（Ｓ４）制御部２３は、現エッジベクトルＥＶ（Ｐ（ｉ−１），Ｐ（ｉ））を指定して次エッジ点決定部２６を呼び出す。次エッジ点決定部２６はこの呼び出しに応答して、まず、現エッジ点Ｐ（ｉ）が追跡途中のビット（その輪郭自身への戻りであって、通常はエッジ点追跡開始点への戻り）であれば、制御部２３に−１を返す。そうでなければ、現エッジ点Ｐ（ｉ）とエッジベクトルＥＶ（Ｐ（ｉ−１），Ｐ（ｉ））の方向及びこの方向と直角な方向（この方向から見て左右方向）に隣接する有効ビットｅ、例えば図７（Ｂ）の次エッジ候補ベクトルＮＶs、ＮＶl及びＮＶrの終端に相当するビットのいずれが‘１’であるかを判定して、この‘１’である次エッジ点Ｐ（ｉ＋１）を決定し、これを制御部２３に返す。
【００３７】
次エッジ点Ｐ（ｉ＋１）が存在しなければ（途切れであって、通常は図４に示すようにブロック境界上からの途切れ）、ｎｕｌｌを制御部２３に返す。
【００３８】
（Ｓ５）制御部２３は、返り値が−１又はｎｕｌｌであればステップＳ１６へ進み、そうでなければステップＳ６へ進む。
【００３９】
（Ｓ６）ｉ＜Ｋ−１であればステップＳ１５へ進み、そうでなければステップＳ７へ進む。Ｋの意味は、以下の説明から明らかになる。Ｋは定数であり、符号化率の平均値ができるだけ高くなるように、実験的に定められる。
【００４０】
（Ｓ７）制御部２３は、ｉ＝Ｋ−１のときはＫ個のエッジ点Ｐ（０）〜Ｐ（Ｋ−１）を指定して、ｉ＞Ｋ−１のときは、基準ベクトル決定部２７で前回の計算結果（Ｋ個のエッジ点、その平均値及び分散）を保持していてこれら用いることができるので、現エッジ点Ｐ（ｉ）のみ指定して、基準ベクトル決定部２７を呼び出す。
【００４１】
以下のステップＳ８〜Ｓ１２での処理は、次エッジベクトル候補毎出現確率算出部２８により行われる。
【００４２】
（Ｓ８）基準ベクトル決定部２７はこの呼び出しに応答して、最小二乗法により、直近のＫ個のエッジ点Ｐ（０）〜Ｐ（Ｋ−１）の回帰直線を決定し、この回帰直線と平行でエッジ点追跡方向である基準ベクトルＲＶを決定し、これを制御部２３に返す。
【００４３】
図７（Ｂ）は、Ｋ＝３、ｉ＝２である場合を示し、この場合の回帰直線Ｌは、エッジ点Ｐ（０）〜Ｐ（２）を通る直線と一致する。基準ベクトルＲＶの向きはエッジ点Ｐ（０）からＰ（２）の方向である。図７（Ｃ）、Ｋ＝３、ｉ＝５である場合を示す。
【００４４】
（Ｓ９）制御部２３は、基準ベクトルＲＶと現エッジ点Ｐ（ｉ）と前エッジ点Ｐ（ｉ−１）とを指定して、次エッジベクトル候補毎出現確率算出部２８を呼び出す。
【００４５】
次エッジベクトル候補毎出現確率算出部２８はこれに応答して、基準ベクトルＲＶと３つの次エッジ候補ベクトルＮＶs、ＮＶl及びＮＶrのそれぞれとの間の角度αs、αl及びαrを算出する。ここに次エッジ候補ベクトルＮＶs、ＮＶl及びＮＶrはそれぞれ、図７（Ｂ）に示すように、現エッジ点Ｐ（ｉ）を始点とし、エッジベクトルＥＶ（Ｐ（ｉ−１），Ｐ（ｉ））の方向及びその左右の方向に隣接する、有効ビットｅに対応する点を終点とするベクトルであり、現エッジ点Ｐ（ｉ）から前エッジ点Ｐ（ｉ−１）へのベクトルは含まれない。
【００４６】
ここで、追跡方向を予測する基準ベクトルＲＶの性質から、角度αが小さいほど出現確率が高いと推定できる。そのような出現確率ｐ（α）の好ましい１例として、フォン・ミーゼス確率密度関数
出現確率ｐ（α，κ）＝ＥＸＰ（κｃｏｓ（α−μ））／｛２πＩ0（κ）｝  ・・・（１）
を用いる。ここにＩ0（κ）は ０次の第一種変形ベッセル関数であり、μ＝０とする。
【００４７】
上記３つの角度の最小値を、
αm＝ＭＩＮ（αs，αr，αl）                               ・・・（２）
としたとき、αm≦π／4となる。αm＝π／4のとき、すなわちαs＝π/4のとき、基準ベクトルＲＶの両側の次エッジ候補ベクトルの角度αがいずれもπ／4となる。また、κ＝０のとき、出現確率ｐ（α，κ）が一様になる。そこで、
κ＝ρ・ｃｏｓ（Q・αm）                                    ・・・（３）
と定める。ここにQは、Q＜２なる定数であって、２に近い値である。また、Q及びρは、平均符号化効率が高くなるように実験的に定められる定数である。このようにすることで確率分布をエッジ点追跡途中の局所的な幾何学的状況に応じてパラメータκが自動的にかつ適切に決定される。
【００４８】
図８（Ａ）〜（Ｃ）はそれぞれ、αmがαm１、αm2、αm3（αm１＞αm2＞αm3＝π）である場合の出現確率ｐ（α，κ）を示す。図中のＨＷ１及びＨＷ２は半値幅を示しており、αmがπに近づくほど大きくなる。αm＝πのときの半値幅は、存在しないが、連続性から、πとみなすことができる。
【００４９】
図９（Ａ）〜（Ｃ）は、αmが互いに同一で基準ベクトルＲＶが互いに異なる３つの場合を示しており、パラメータを含めた確率関数は互いに同一になる。図９（Ａ）及び（Ｂ）の場合のチェインコード１と図９（Ｃ）の場合のチェインコード２の出現確率は互いに同一になり、図９（Ａ）〜（Ｃ）のそれぞれのチェインコード０、２、１の出現確率は互いに同一になり、図９（Ａ）〜（Ｃ）のそれぞれのチェインコード２、０、０の出現確率は互いに同一になる。
【００５０】
（Ｓ１０）上式（２）のαmの値を求める。
【００５１】
（Ｓ１１）上式（３）のκの値を求める。
【００５２】
（Ｓ１２）現エッジ点Ｐ（ｉ）を始点とする次エッジ候補ベクトルＮＶs、ＮＶr及びＮＶlのそれぞれの出現確率ｐｓ（ｉ）＝ｐ（κ，αs）、ｐｒ（ｉ）＝ｐ（κ，αr）及びｐｌ（ｉ）＝ｐ（κ，αl）を算出し、これらの値を制御部２３に返す。
【００５３】
（Ｓ１３）制御部２３は、これら出現確率を指定して、算術符号化部２９を呼び出す。算術符号化部２９はこれに応答して、半開区間［ｓ，ｔ）を出現確率ｐｓ（ｉ）、ｐｒ（ｉ）、ｐｌ（ｉ）で比例分割（ｐｓ：ｐｒ：ｐｌで分割）する。分割された半開区間のうち、先端がステップＳ４で求めた次エッジ点Ｐ（ｉ＋１）と一致するものに対応する半開区間［ｓｉ，ｔｉ）で半開区間［ｓ，ｔ）を更新し、制御部２３に制御を移す。
【００５４】
半開区間［ｓ，ｔ）は例えば図９（Ｄ）に示すように順次更新される。この図は、エッジ点Ｐ（１）を算術符号化開始点とするエッジ点Ｐ（４）までの算術符号化シーケンスを表している。
【００５５】
（Ｓ１４）制御部２３は、ｉを１だけインクリメントし、エッジカウンタＥＣを１だけデクリメントし、チェインコードカウンタＣＣＣを１だけインクリメントし、ステップＳ５へ戻る。
【００５６】
（Ｓ１５）サンプル数が少なくて基準ベクトルを定めることができないので、ｐｓ（ｉ）＝ｐｒ（ｉ）＝ｐｌ（ｉ）＝１／３と出現確率を均一化し、ステップＳ１４へ進む。
【００５７】
（Ｓ１６）最終的な半開区間［ｓ，ｔ）内の値で、桁数を最大限削減できる値をｕとして求める。ｕ及びチェインコードカウンタＣＣＣの値を、ステップＳ２で格納した追跡開始点（ｊ0，ｋ0）及びこの点からのチェインコードＣＣ０と対応付けて１組とし、符号化エッジマップ記憶部２１に格納する。この組が、１つの輪郭に対応しており、適応型算術輪郭復号装置で後述のように復号される。次に、ステップＳ１へ戻る。その後のステップＳ２においては、符号化した輪郭を除いた未スキャン領域をスキャンして、値が‘１’である最初のエッジ点Ｐ（０）を検出する。
【００５８】
なお、ステップステップＳ０において生成したエッジマップを、ステップＳ２でのスキャン用としてコピーしておき、ステップスＳ２では、このエッジマップをスキャンし、エッジ点Ｐ（０）及びＰ（１）のそれぞれに対応するビットを‘０’にし、ステップＳ１４でｉを更新する前の現エッジ点Ｐ（ｉ）に対応するビットを‘０’にするようにしてもよい。
【００５９】
（Ｓ１７）制御部２３は、エッジ符号化完了信号を内部（同じＤＲＡＭ１３内）、又は、インターフェイス１１を介して外部に出力し、これに応答があったとき、符号化エッジマップ記憶部２１の内容を出力し、１ブロック符号化処理を終了する。
【００６０】
本実施例１の適応型算術輪郭符号化装置によれば、追跡した直近のＫ個（≧３）のエッジ点の回帰直線Ｌと平行で向きが追跡方向である基準ベクトルＲＶと各次エッジ候補ベクトルＮＶｓ、ＮＶｒ及びＮＶｌとのなす角度αが小さいほど値が大きくなる関数ｐ（α，κ）の値を次エッジ候補ベクトルの出現確率として求めるので、復号途中の局所的な幾何学的特徴が出現確率に反映され、これにより、輪郭データを効率よく符号化することが可能になるという効果を奏する。
【００６１】
また、関数ｐ（α，κ）は、次エッジ候補のそれぞれについての該角度αの最小値が小さいほど該関数の半値幅が狭くなるパラメータκを有するので、確率分布をエッジ点追跡途中の局所的な幾何学的状況に応じてパラメータκが自動的にかつ適切に決定され、出現確率の信頼性がより高くなり、これにより、輪郭データをさらに効率よく符号化することが可能になるという効果を奏する。
【００６２】
なお、回帰直線Ｌに対する直近のＫ個のエッジの分散が閾値以上である場合に、Ｋの値を、該分散が該閾値未満であるときの値よりも小さい値（但しＫ≧３）にしてもよい。
【００６３】
この場合、輪郭の屈曲部分において出現確率の信頼性がより高くなり、これにより、輪郭データをさらに効率よく符号化することが可能になるという効果を奏する。
【００６４】
次に、適応型算術輪郭復号装置について説明する。
【００６５】
適応型算術輪郭復号装置のハードウェア構成は、図３と同じであるのでその説明を省略する。
【００６６】
図１０は、適応型算術輪郭復号装置の概略機能ブロック図である。
【００６７】
符号化エッジマップ記憶部３０及び３１は、ＤＲＡＭ１３内の領域である。ブロック３２〜３５は何れも、ＭＰＵ１０がプログラムを実行することにより機能する。制御部３２はメインルーチンであり、機能ブロック３３〜３５はそのサブルーチンである。
【００６８】
符号化エッジマップ記憶部３０には、図３のＤＲＡＭ１３内の他の領域又は外部から１ブロックの符号化エッジマップが格納される。１ブロック分の符号化エッジマップの格納が完了すると、符号化エッジマップ格納完了のイベントが制御部３２に通知される。制御部３２はこれに応答して、この符号化エッジマップに関し、直接又は他の機能ブロックを介し処理を行うことにより、エッジマップ記憶部３１内に、復号されたエッジマップを生成する。以下、エッジマップのデータを上記同様にｅ（ｊ，ｋ）と表記する。
【００６９】
図１１は、１ブロックに対する制御部３２（図１１の装置）の処理手順を示す概略フローチャートである。この処理は、上記イベントの通知に応答して開始される。
【００７０】
（Ｓ２０）制御部３２は、符号化エッジマップ記憶部３０から１つの輪郭に対応した上記１組のデータである半開区間内の値ｕ、チェインコードカウンタＣＣＣ、エッジ点追跡開始点（ｊ0，ｋ0）及びこの点からのチェインコードＣＣ０を読み出す。
【００７１】
（Ｓ２１）この組が存在すればステップＳ２２へ進み、そうでなければステップＳ２８へ進む。
【００７２】
（Ｓ２２）エッジマップ記憶部３１内のｅ（ｊ0，ｋ0）を‘１’とし、この点から、チェインコードＣＣ０に対応したベクトルの先端に相当するビットを‘１’にする。すなわち、エッジ点Ｐ（０）及びＰ（１）を再生する。また、現エッジ点のインデックスｉに１を代入する。
【００７３】
（Ｓ２３）制御部３２は、半開区間［ｓ，ｔ）を［０，１）に初期化する。
【００７４】
（Ｓ２４）ＣＣＣ＝０であれば、ステップＳ２０へ戻り、そうでなければ、ステップＳ６へ進む。ステップ６以下の、ステップＳ６、Ｓ８〜１２及びステップＳ１５での処理は、図１のそれらと同一である。但し、ステップＳ１５からステップＳ２５へ進む。
【００７５】
基準ベクトル決定部３３及び次エッジベクトル候補毎出現確率算出部３４での処理は、それぞれ図１の基準ベクトル決定部２７及び次エッジベクトル候補毎出現確率算出部２８での処理と同一であり、制御部３２は算術復号部３５から出現確率ｐｓ（ｉ）、ｐｒ（ｉ）及びｐｌ（ｉ）を受け取る。
【００７６】
（Ｓ２５）制御部３２は、これら出現確率ｐｓ、ｐｒ及びｐｌを指定して、算術復号部３５を呼び出す。算術復号部３５はこれに応答して、半開区間［ｓ，ｔ）を出現確率ｐｓ、ｐｒ、ｐｌで比例分割する。
【００７７】
（Ｓ２６）算術復号部３５は、分割された半開区間のうち、ｕが含まれる半開区間［ｓ'，ｔ'）に対応するエッジベクトルをエッジマップ上の現エッジ点Ｐ（ｉ）からの次エッジベクトルと決定し、その終端に相当するビットｅを‘１’にする。
【００７８】
（Ｓ２７）算術復号部３５は、半開区間［ｓ，ｔ）を半開区間［ｓ'，ｔ'）で更新し、制御を制御部３２に戻す。制御部３２は、ｉを１だけインクリメントし、チェインコードカウンタＣＣＣを１だけデクリメントし、ステップＳ２４へ戻る。
【００７９】
（Ｓ２８）制御部３２は、エッジマップ復号完了信号を内部又は外部へ出力し、これに応答があったとき、エッジマップ記憶部３１の内容を内部又は外部へ出力する。
【００８０】
なお、チェインコードの替わりに、差分チェインコードを用いてもよい。
【実施例２】
【００８１】
次に、エッジマップを作成せずに輪郭を追跡する場合を、実施例２として説明する。
【００８２】
図１２は、図５（Ａ）の奥行きマップ２０１上に、左上頂点を原点とするＸ−Ｙ直交座標系を配置し、Ｘ軸及びＹ軸の単位をそれぞれ半画素幅として、エッジ点Ｐ（ｉ）の座標を表している。
【００８３】
一般に、画素ｄ（ｊ，ｋ）とｄ（ｊ＋１，ｋ）の間のエッジ点座標は、（２ｊ＋２，２ｋ＋１）であり、画素ｄ（ｊ，ｋ）とｄ（ｊ，ｋ＋１）の間のエッジ点座標は、（２ｊ＋１，２ｋ＋２）である。
【００８４】
すなわち、エッジ点座標（Ｘ，Ｙ）のＸとＹの一方が偶数であれば、他方が奇数である。また、エッジ点座標のＸ座標値が偶数であれば、図１２中の縦のエッジラインであり、奇数であれば、図１２中の横のエッジラインである。隣合う画素の位置座標と、エッジ点座標（Ｘ，Ｙ）との一方が分かれば、上記の関係から、他方が分かる。
【００８５】
エッジ点座標（Ｘ，Ｙ）は、図６（Ａ）中のエッジ点座標と同一である。
【００８６】
以上のことから、エッジマップを作成せずに、実施例１と同様にして、エッジ点の符号化及び復号を行うことができることが分かる。
【実施例３】
【００８７】
次に、図１２のエッジ点の替わりに、図１３に示すように画素のエッジラインの端点をエッジ点とみなして追跡する場合を説明する。
【００８８】
Ｘ軸及びＹ軸の単位をそれぞれ１画素幅とする。
【００８９】
一般に、画素ｄ（ｊ，ｋ）と画素ｄ（ｊ＋１，ｋ）の間の縦エッジラインは、その端点座標の組［（ｊ＋１，ｋ），（ｊ＋１，ｋ＋１）］で表され、画素ｄ（ｊ，ｋ）と  画素ｄ（ｊ，ｋ＋１）の間の横エッジラインは、その端点座標の組［（ｊ，ｋ＋１），（ｊ＋１，ｋ＋１）］で表される。
【００９０】
すなわち、端点座標の組のＸ座標が同一であれば縦エッジラインであり、Ｙ座標が同一であれば横エッジラインであることが分かる。また、隣合う画素の位置座標と、エッジラインの端点座標の組との一方が分かれば、上記の関係から、他方が分かる。
【００９１】
図１２において、最初のエッジラインの端点座標の組［（３，０），（３，１）］を見つけた後、エッジ点Ｐ２〜Ｐ７を順次追跡する。すなわち、チェインコード又は差分チェインコードを順次決定する。
【００９２】
図１４に示すように、みなしエッジ点の回帰直線Ｌを最小二乗法により決定する。例えば、
現エッジ点がＰ３である場合、点Ｐ０〜Ｐ３の回帰直線Ｌを最小二乗法により決定し、この回帰直線Ｌと平行でエッジ点追跡方向である基準ベクトルＲＶを決定する。次に、実施例１と同様に、基準ベクトルＲＶと３つの次エッジ候補ベクトルＮＶs、ＮＶl及びＮＶrのそれぞれとの間の角度αs、αl及びαrを算出する。実施例１と異なるのは、次エッジ候補ベクトルＮＶs、ＮＶl及びＮＶrが、縦方向又は横方向である点である。
【００９３】
他の点は、実施例１と同一である。
【００９４】
本実施例３によれば、実施例１、２の場合よりも、輪郭を容易に表現できるという効果を奏する。
【００９５】
次に本実施例３の実験結果を説明する。
【００９６】
図１５（Ａ）は、撮影対象がバレー（図４はその１フレーム）とブレイクダンサーズのそれぞれの多視点深さデータ（１フレームが１０２４×７６８画素）を、２つの従来法（ｚモード＋ＭＰＥＧ−４ＤＣＣ及びｉｉｄＡＥＣ−Ｈ２６４／ＡＶＣ）と本実施例３の符号化方法（ｚモード＋ｎｏｎ−ｉｉｄＡＥＣ）とで、それぞれ１００フレーム以上符号化した場合の、１エッジ点当たりの平均符号化ビット数（エッジ率）を示す。ＤＣＣ（differential chain coding）は差分チェイン符号化であり、ＡＥＣ（arithmetic edge coding）はエッジを算術符号化したことを意味し、ｉｉｄ（independent and identically distributed）は出現確率ｐｓ、ｐｒ、ｐｌをそれぞれ１／３に固定した場合である。本実施例３の符号化方法では、回帰直線を求める直近のエッジ点数Ｋの値を３とし、また、上式（３）中のρの値を８とした。
【００９７】
本実施例３の符号化方法は、従来のＭＰＥＧ−４ＤＣＣのそれよりも、符号化率を６７％高めることができた。
【００９８】
図１５（Ｂ）及び（Ｃ）はそれぞれ上記バレーとブレイクダンサーズの多視点深さデータ深さデータを符号化したときのビットレートに対するＰＳＮＲ（Peak Signal-to-Noise Ratio）を上記３つの方式のそれぞれについて示す。各グラフ上の４点はそれぞれ、量子化行列の各成分の値を互いに同一にし、その値を27、32、 37及び 42としたものに対応している。この結果は、図１５（Ａ）のように従来法より本実施例３の方が、符号化率が向上したため、従来のＨ２６４／ＡＶＣ方式よりも本実施例３の方が、同一ビットレートにして比較すると情報量を多く転送することができ、その結果、ＰＳＮＲが約３デシベル向上していることを示している。
【００９９】
以上において、本発明の好適な実施例を説明したが、本発明には他にも種々の変形例が含まれ、上記実施例で述べた各構成要素の機能を実現する他の構成を用いたもの、当業者であればこれらの構成又は機能から想到するであろう他の構成も、本発明に含まれる。
【０１００】
例えば、エッジ点追跡初期でｉ≧３のときＫ−１＞ｉであっても回帰直線及び基準ベクトルを求める構成であってもよい。
【０１０１】
上記実施例１では４隣接エッジ点を連結する場合を説明したが、図６（Ａ）中のＸ印を付したビットを有効にして、すなわち図５（Ａ）で斜め方向に隣接する画素間についてもエッジを検出して、図６（Ａ）で８隣接エッジ点を連結する場合に本発明を適用してもよい。この場合、次エッジ候補ベクトル数は８−１＝７となる。
【０１０２】
また、回帰直線を求める直近のエッジ点数は、少な過ぎても多すぎても確率の信頼性が低くなり、ｎＸｎ画素ブロックの場合、好ましくは３以上ｎ／２以下であればよい。
【０１０３】
さらに、出現確率を与える関数は、４隣接及び８隣接のいずれの場合も、基準ベクトルＲＶと次エッジ候補ベクトルとのなす角度αが小さいほど値が大きくなるものであればよい。
【０１０４】
また、輪郭符号化したものにチェインコードカウンタＣＣＣと半開区間内の値とを含める替わりに、半開区間を含める構成であってもよい。
【０１０５】
また、本発明の装置の処理対象は奥行き画像のエッジマップに限定されず、輝度画像や単色画像のエッジマップであってもよい。
【符号の説明】
【０１０６】
１０  ＭＰＵ
１１  インターフェイス
１２  ＰＲＯＭ
１３  ＤＲＡＭ
１４  ＤＭＡＣ
２０  奥行きマップ記憶部
２１  符号化エッジマップ記憶部
２２  エッジマップ記憶部
２３、３２  制御部
２４  画素間エッジ点検出部
２５  追跡開始エッジベクトル決定部
２６  次エッジ点決定部
２７、３３  基準ベクトル決定部
２８、３４  次エッジベクトル候補毎出現確率算出部
２９  算術符号化部
２０１  奥行きマップ
２２１  エッジマップ
３０  符号化エッジマップ記憶部
３１  エッジマップ記憶部
３２  制御部
３５  算術復号部
ＥＣ  エッジカウンタ
ＣＣ０  チェインコード
ＣＣＣ  チェインコードカウンタ
ＥＶ  エッジベクトル
ＮＶs、ＮＶr、ＮＶl  次エッジ候補ベクトル
ＲＶ  基準ベクトル
α、αs、αr、αl  角度
ｐ、ｐｓ、ｐｒ、ｐｌ  出現確率
【図１】
2014072720.tif 000003
【図２】
2014072720.tif 000004
【図３】
2014072720.tif 000005
【図５】
2014072720.tif 000006
【図７】
2014072720.tif 000007
【図８】
2014072720.tif 000008
【図９】
2014072720.tif 000009
【図１０】
2014072720.tif 000010
【図１１】
2014072720.tif 000011
【図１２】
2014072720.tif 000012
【図１３】
2014072720.tif 000013
【図１４】
2014072720.tif 000014
【図１５】
2014072720.tif 000015
【図４】
2014072720.tif 000016
【図６】
2014072720.tif 000017