【手続補正書】
【提出日】平成18年2月8日(2006.2.8)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】  明細書
【発明の名称】  画像符号化方法とその装置、画像復号化方法とその装置、コンピュータに画像符号化方法および画像復号化方法を実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体
【特許請求の範囲】
【請求項１】  全方位画像を予測符号化する方法であって、フレーム内符号化を行う参照画像符号化ステップと、符号化された参照画像から類似の全方位画像を予測する際、参照画像の端が他方の端に連続していることを仮定し、継ぎ目なく予測全方位画像を生成する予測ステップと、予測ステップにより生成された予測全方位画像と入力全方位画像との差分を符号化する残差符号化ステップを有することを特徴とする画像符号化方法。
【請求項２】  全方位画像を予測復号化する方法であって、フレーム内復号化を行う参照画像復号化ステップと、復号化された参照画像から類似の全方位画像を予測する際、参照画像の端が他方の端に連続していることを仮定し、継ぎ目なく予測全方位画像を生成する予測ステップと、予測ステップにより生成された予測全方位画像と入力全方位画像との差分を復号化する残差復号化ステップを有することを特徴とする画像復号化方法。
【請求項３】  全方位画像を予測符号化する装置であって、フレーム内符号化を行う参照画像符号化手段と、符号化された参照画像から類似の全方位画像を予測する際、参照画像の端が他方の端に連続していることを仮定し、継ぎ目なく予測全方位画像を生成する予測手段と、予測手段により生成された予測全方位画像と入力全方位画像との差分を符号化する残差符号化手段を有することを特徴とする画像符号化装置。
【請求項４】  全方位画像を予測復号化する装置であって、フレーム内復号化を行う参照画像復号化手段と、復号化された参照画像から類似の全方位画像を予測する際、参照画像の端が他方の端に連続していることを仮定し、継ぎ目なく予測全方位画像を生成する予測手段と、予測手段により生成された予測全方位画像と入力全方位画像との差分を復号化する残差復号化手段を有することを特徴とする画像復号化装置。
【請求項５】  コンピュータに請求項１に記載の画像符号化方法を実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項６】  コンピュータに請求項２に記載の画像復号化方法を実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元環境システムを実現することを目的とした画像符号化方法とその装置、画像復号化方法とその装置、コンピュータに画像符号化方法および画像復号化方法を実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
コンピュータグラフィックス（Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ，ＣＧ）とは、「コンピュータによりデータを処理し、生成された画像」または、「コンピュータによりデータを処理し、画像を生成する技術」という意味で用いられる。
【０００３】
広く解釈すれば、コンピュータで図形を描くアルゴリズムを開発することも、コンピュータを利用して図形を描くこともＣＧに含まれる。
【０００４】
ＣＧが表現可能な対象は、人間が見ることができる物体、場所や背景のみならず、実際に見ることができないものを表現することも可能である。
【０００５】
そのため、ＣＧは仮想現実感（Ｖｉｒｔｕａｌ  Ｒｅａｌｉｔｙ，  ＶＲ）や人工現実感（Ａｒｔｉｆｉｃｉａｌ Ｒｅａｌｉｔｙ，ＡＲ）と呼ばれる技術に用いられ、重要な基礎となっている。これらの技術では、コンピュータ内に構築された世界をＣＧによって可視化し、あたかもその世界にいるかのような感覚を起こす。より現実味のある緻密な画像生成が必要である。
【０００６】
現在そのＣＧの多くは、ポリゴンベースドレンダリング（Ｐｏｌｙｇｏｎ−Ｂａｓｅｄ Ｒｅｎｄｅｒｉｎｇ，ＰＢＲ）という手法によって生成されている。光学的計算を行うレンダリング（Ｒｅｎｄｅｒｉｎｇ）行程は、実環境のような複雑なシーンである場合は計算コストが大きくなる。そのために、計算機の能力が飛躍的に発展した現在でも、実時間でシーンの変更が必要な場合には幾何計算専用のプロセッサが必要になることがある。
【０００７】
一方、撮影・蓄積された実写画像を基に画像を生成するイメージベースドレンダリング（Ｉｍａｇｅ−Ｂａｓｅｄ  Ｒｅｎｄｅｒｉｎｇ，  ＩＢＲ）と呼ばれる手法が提案されている。
【０００８】
蓄積画像数が莫大になるために大きな記憶領域を必要とする欠点があるが、実写画像を用いることにより写実的な再生画像を得ることができる。
【０００９】
しかし、撮影した画像しか再生できないために、架空の環境は表現することができない。ＩＢＲは実写画像を用いるために写実性に優れている。さらに、蓄積画像を出力するために計算コストは極めて小さく、人工現実感のように写実的な画像が求められ、かつ視点の変更とともに実時間でシーンの変更が求められるような応用には、後者のＩＢＲが適している。
【００１０】
本発明はＩＢＲを用いた３次元環境再現システムに関する。
【００１１】
ＩＢＲを用いた３次元環境再現システムを図１に示す。
【００１２】
図１では全方位画像（パノラマ画像）を撮影できるロボットを自走させ、多地点で撮像することにより、任意位置の任意視点の見え方を再現する。ＩＢＲの課題は、蓄積すべき情報量が多い点である。
【００１３】
これについては特開平１０−２７１５１１号公報記載の画像符号化装置と画像復号化装置がある。
【００１４】
これを符号化に関する従来例（従来例１）とする。従来例１では、図２に示すように物体周囲をカメラが移動し可能な限り多くの位置から物体を撮像し、異なる視点画像間の相関を利用して高能率符号化を行う。
【００１５】
この高能率符号化には、動き補償離散コサイン変換（Ｍｏｔｉｏｎ−Ｃｏｍｐｅｎｓａｔｅｄ  Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ）符号化方式（ＭＣ−ＤＣＴ符号化と以後略す）が多視点間の予測符号化に拡張されて用いられている。
【００１６】
ＭＣ−ＤＣＴ符号化方式はＩＴＵ−Ｔ（国際電気通信連合  電気通信標準化部門）で国際標準化されたＨ．２６１規格やＨ．２６３規格やＭＰＥＧ規格に採用された共通動画圧縮技術として良く知られている。
【００１７】
ここでＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）とは、世界標準化機構（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ  ｆｏｒ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ，  ＩＳＯ）の音声・動画符号化の標準化を進めてきた作業グループ（ＩＳＯ／ＩＥＣ  ＪＴＣ１／ＳＣ２９／ＷＧ１１）を指すが、同時にこのグループが定めたデータ圧縮の国際規格をも意味する。
【００１８】
ＭＣ−ＤＣＴ符号化方式では画像を１６×１６画素からなるマクロブロックと呼ばれるブロックに分割し、連続する画像（フレーム）間でマクロブロックの差分が最小となる移動量（動きベクトル）を計算し、その差分を離散コサイン変換（ＤＣＴ）符号化を行う。フレーム間差分最小となるよう動きベクトルを求め冗長性を除いた差分画像を得る作業は動き補償と呼ばれる。ＤＣＴは動き補償された画像（差分画像）に残る空間的冗長性を除くために用いられる。なお、最初のフレームは、他のフレームとの差分符号化が行えないため、ＤＣＴのみを用いて符号化される。これをＩピクチャとよぶ。ＭＣ−ＤＣＴ符号化される一般フレームをＰピクチャとよぶ。従来例１はこの構造を多視点画像間に拡張したものである。
【００１９】
３次元環境再現システムでは自走ロボットを所定の位置を走査するよう制御する。
【００２０】
この制御は角度センサーの情報から移動距離、回転を得て行われるが、角度センサーの精度不足や車輪のスリップが避けられず、正しく所定の位置を走行する保証はない。そのために得られた画像から実際に走行した視点位置を補正する必要がある。
【００２１】
画像中の特徴点から、カメラの動きを推定する手法として６特徴点照合による推定方法がある。例えば、文献Ｊｕｙａｎｇ  Ｗｅｎｇ，  Ｎａｒｅｎｄｒａ  Ａｈｕｊａ，  ａｎｄ  Ｔｈｏｍａｓ  Ｓ．Ｈｕａｎｇ：“Ｏｐｔｉｍａｌ  ｍｏｔｉｏｎ  ａｎｄ  ｓｔｒｕｃｔｕｒｅ  ｅｓｔｉｍａｔｉｏｎ”，  ＩＥＥＥ  Ｔｒａｎｓ，  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，１５（９），ｐｐ８６４−８８４（１９９３）に記載されている。
【００２２】
これを撮像装置の校正に関する従来例（従来例２）とする。この概念を図３に示す。画像中で
【００２３】
【数１】
2000261808.tif 000001
【００２４】
が未知数であるとする。
【００２５】
ここで、ｄ０からｄ５まではカメラから物体（この場合、筐体の頂点）までの距離、Ｔｘ、Ｔｙ、Ｔｚはカメラと物体間の相対的並進成分、ωｘ、ωｙ、ωｚは回転成分である。基準位置で観測された６特徴点の座標を数２として定める。
【００２６】
【数２】
2000261808.tif 000002
【００２７】
３次元空間中の特徴点の位置が（数１）と（数２）を既知とすると、任意の視点位置の特徴点投影座標が（数３）として計算できる。
【００２８】
【数３】
2000261808.tif 000003
【００２９】
（数３）が実際には（数４）として観測されたとする。
【００３０】
【数４】
2000261808.tif 000004
【００３１】
（数３）と（数４）は量子化誤差やレンズ系の収差のため、必ずしも一致しない。
【００３２】
（数３）と（数４）のずれを２乗誤差として（数５）に表現し、これを最小化する枠組みで物体−カメラ間の動きΨを決定する。
【００３３】
【数５】
2000261808.tif 000005
【００３４】
この最小化は、（数３）の関数ｆが非線形関数であることから、反復による最小化手法が使われる。（数６）は非線形最小２乗化の手法として広く用いられているＬｅｖｅｎｂｅｒｇ−Ｍａｒｑｕａｒｔ法による最小化ステップを表している。
【００３５】
【数６】
2000261808.tif 000006
【００３６】
Ｈは近似ヘッセ行列で、Ｉは単位行列∇ｅは勾配ｔは反復数である。λは非負の制御変数で、λが大きな時、最急降下法（収束は遅いが安定）に、λが小さな時、ニュートン法（不安定だが収束は速い）に近づく。
【００３７】
Ｌｅｖｅｎｂｅｒｇ−Ｍａｒｑｕａｒｔ法では、λを制御することにより最急降下法とニュートン法の長所が生かせる。なお、Ｌｅｖｅｎｂｅｒｇ−Ｍａｒｑｕａｒｔ法では、近似ヘッセ行列を以下のように計算する。
【００３８】
【数７】
2000261808.tif 000007
【００３９】
【数８】
2000261808.tif 000008
【００４０】
数８は、数５が２次形式をとっていることから、可能になった近似である。
【００４１】
反復が安定収束であるためには、数６において、勾配∇ｅに係る逆行列は正定
値（ｐｏｓｉｔｉｖｅ−ｄｅｆｉｎｉｔｅ）である必要がある。
【００４２】
一般にヘッセ行列は正定値である保証はないが、数７が数８の近似により実対称行列となることから、この場合正定置であることが保証されている。以上２視点間の６特徴点照合により、カメラの並進・回転が求まる。ただし、並進については絶対値ではなく、特徴点までの距離も含めて比として得られる。
【００４３】
なお、６特徴点の照合が必要な理由は、以下のように説明できる。特徴点一つの観測につき水平・垂直の座標が得られることから２つの方程式が立つ。
【００４４】
カメラの動きパラメータ（未知パラメータ）は６個である。特徴点照合が１つにつき、基準座標における特徴点までの距離が１個未知パラメータとして増える。特徴点照合が６のとき、方程式数が未知パラメータ１２と等しくなり、数５の最小化として画像から動きパラメータが求まる。
【００４５】
【発明が解決しようとする課題】
従来例１は、図２に示したように内向き多視点画像の符号化を行っており、図１に示すようなＩＢＲを用いた３次元環境再現システム符号化には、改善の余地がある。異なる視点画像間の相関を用いた上で、符号化対象は全方位画像であることの性質を利用した符号化が必要である。また、３次元環境再現システムを実現するためには、符号化した全方位画像の復号化が必要である。
【００４６】
本発明は、かかる点に鑑み、全方位画像多視点符号化に適した符号化方法とその装置、全方位画像多視点複合化に適した復号化方法とその装置、およびコンピュータに全方位画像多視点符号化に適した符号化方法および全方位画像多視点複合化に適した復号化方法を実現させるプログラムを記録した記録媒体を提供することを目的とする。
【００４７】
【課題を解決するための手段】
この課題を解決するために、第１の発明は、全方位画像を予測符号化する方法であって、フレーム内符号化を行う参照画像符号化ステップと、符号化された参照画像から類似の全方位画像を予測する際、参照画像の端が他方の端に連続していることを仮定し、継ぎ目なく予測全方位画像を生成する予測ステップと、予測ステップにより生成された予測全方位画像と入力全方位画像との差分を符号化する残差符号化ステップを有することを特徴とする画像符号化方法である。
【００４８】
第２の発明は、全方位画像を予測復号化する方法であって、フレーム内復号化を行う参照画像復号化ステップと、復号化された参照画像から類似の全方位画像を予測する際、参照画像の端が他方の端に連続していることを仮定し、継ぎ目なく予測全方位画像を生成する予測ステップと、予測ステップにより生成された予測全方位画像と入力全方位画像との差分を復号化する残差復号化ステップを有することを特徴とする画像復号化方法である。
【００４９】
【発明の実施の形態】
（実施例１）
実施例１を図４、図５、図６、図７、図８を用いて説明する。図１に示した撮像系は、床面上を格子状にくまなく移動するように移動する。図４は、床面を上から俯瞰した、撮影点を表しており、円は全方位画像を表している。
【００５０】
全方位画像の中で、網かけされた円はテンプレート符号化画像であり、そうでない画像はテンプレート符号化画像を参照して予測符号化されるテンプレート予測符号化画像である。全方位画像は円筒状にシームレスな画像であるが、これを矩形に展開し、ＭＰＥＧ１とほぼ同じイントラフレーム符号化により符号化される（ＭＣ−ＤＣＴ符号化方式のＩピクチャに相当）。
【００５１】
ＭＰＥＧ１と異なるのは画像サイズで横３５２０×縦５７６画素であることである。
【００５２】
この処理ステップを図５に示す。従来の技術で説明したように、通常のＭＣ−ＤＣＴ符号化方式と同じように画像を１６×１６画素からなるマクロブロックと呼ばれるブロックに分割し、それをさらに分割した８×８画素単位で２次元ＤＣＴを行う。
【００５３】
これを量子化し、主観画質を落とさない範囲で情報を落とす（情報の欠落は量子化誤差に相当する）。量子化データは可変長符号化されてハフマン符号として出力される。
【００５４】
テンプレート予測符号化画像の符号化ステップを図６に示す。
【００５５】
視点位置の近いテンプレートを一度復号して参照画像とする。
【００５６】
この復号済みテンプレートとの間で当該画像のマクロブロックの差分が最小となる移動量（動きベクトル）を計算し、その差分を離散コサイン変換（ＤＣＴ）符号化を行う。
【００５７】
この処理を図７に示す。量子化以降はテンプレート符号化と同じステップをとる。上記動き補償で、従来のＭＣ−ＤＣＴ方式の動き補償と異なるのは、図８に示すように領域外参照となる動きベクトルを認めることである。
【００５８】
全方位画像はシームレスな円筒画像と考えることができるから、右方（左方）への突出分を画像左端（右端）からみたオフセットとして予測画像生成を行う。
【００５９】
この“シームレス（継ぎ目なし）”動き補償に対応して、動きベクトル予測も“シームレス”に行う。
【００６０】
以上特許請求の範囲の請求項１に該当する実施例１を説明した。
（実施例２）
次に実施例１で生成された符号データを復号する実施例２を示す。
【００６１】
図９は図５の逆過程であり、テンプレート符号化画像を再構成する。
【００６２】
横３５２０×縦５７６画素が扱えるＭＰＥＧ１のイントラ復号化ステップを実行する。
【００６３】
図１０は、図６の逆過程であり、テンプレート予測画像を再構成する。
【００６４】
再生しようとする視点位置がテンプレート符号化画像であれば、図９の処理ステップにしたがって復号化する。テンプレート予測符号化画像であれば、参照している近傍のテンプレート符号化画像を一度復号した後（あるいは、一度復号した画像は、消去せずに蓄積しておくとすると、メモリから読み出して）、図１０の処理ステップに従って復号化する。さらに再構成された画像から図１１に示すように任意視線方向を切り取れば、３次元環境再現が行える。
【００６５】
このように、膨大なデータ量となる全方位画像を異なる視点間の相関を利用した上で、全方位画像の特徴に注目して“シームレス”動き補償することにより、少ない符号量で符号化することができる。
（参考例１、２）
参考例１、２は３次元環境再現システムにおける観測系の動き推定方法に関するものである。
【００６６】
はじめに、参考例１、２の課題を示す。従来技術に示した従来例２は６特徴点照合により、カメラの並進・回転が求まる。図１のように一般に床面上を移動する撮像系では、自由度が水平移動に拘束され、また回転についても鉛直線を軸に１自由度の回転である。
【００６７】
したがって、２自由度の並進運動と１自由度の回転運動合計３自由度のパラメータ推定では、３特徴点照合により、カメラ移動パラメータが画像より推定できる。しかし、カメラ移動に際して、特徴点座標の垂直方向成分が変化しないことが多い。したがって、２自由度の並進運動と１自由度の回転運動合計３自由度のパラメータ推定では、３特徴点照合により、カメラ移動パラメータが画像より推定できる。しかし、カメラ移動に際して、特徴点座標の垂直方向成分が変化しないことが多い。
【００６８】
言い換えれば、画面上、垂直方向の特徴点座標の僅かな観測誤差が、カメラの運動パラメータを大きく左右する。
【００６９】
参考例１、２では、かかる点に鑑み、床面上を移動する観測系の動きパラメータを安定して推定する方法と装置を提供する実施例を示す。
（参考例１）
参考例１に示す発明は、走行する観測系の水平移動、回転角度を推定する方法であって、基準位置における観測系周囲に存在するＮ個所（Ｎ≧６）の方向角を観測するステップ１と、上記Ｎ個所について異なる位置１で再度方向角を観測するステップ２と、上記Ｎ個所についてさらに異なる位置２で再度方向角を観測するステップ３と、以上の３Ｎの方向角を用いて、基準位置に対する位置１および位置２とその位置における鉛直線周りの観測系の回転を求めるステップからなることを特徴とする観測系動き推定方法である。
【００７０】
観測系動き推定方法を図１２、図１３、図１４を用いて説明する。参考の実施例では床面上を移動する撮像系の動きパラメータを安定して推定する方法を示す。
【００７１】
はじめに動きパラメータの推定原理を説明する。図１２に示すように、カメラが自走することにより、異なる観測位置で、見え方の異なる画像が撮像される。ここで求めたいのは、カメラの並行移動成分（床面上の２自由度）と鉛直方向周りの回転成分（１自由度）の計３自由度のパラメータである。
【００７２】
床面上の移動に対して、最も見え方変化の大きな特徴は、情景中の垂直エッジである（原理的には、垂直エッジだけではなく、特徴点を含む。後述の方向角に変換できる特徴であれば良い）。
【００７３】
本実施例では水平方向の見え方の変化だけを頼りにカメラの動きパラメータを推定する。図１３は、撮像装置の位置を真上から俯瞰した図であるが、このように３視点位置でＡの位置を基準とし、新たに位置Ｂおよび位置Ｃで同じ垂直エッ
ジを観測するとする。
【００７４】
各位置における十字は、撮像装置中心で定まる局座標である。
【００７５】
基準位置Ａにおいて定めた座標系に対して、Ｂに移動した際のカメラ動きパラ
メータは（ＴｘＢ、ＴｙＢ、ωＢ）、Ｃに移動した際のカメラ動きパラメータは（ＴｘＣ、ＴｙＣ、ωＣ）とする。
【００７６】
未知数は６である。これを求めるために、各位置における垂直エッジの方位角を求める。観測１つに付き数９が１つ成り立つ。
【００７７】
数９においてｐは位置の識別子でこの場合［Ｂ、Ｃ］のいずれかである。ｉは垂直エッジの識別子であり、０≦ｉ＜Ｎ、Ｎ≧６であることは後述する。
【００７８】
【数９】
2000261808.tif 000009
【００７９】
数９は垂直エッジｉの基準座標Ａからみた距離ｄｉＡと位置ｐまでのカメラ動きパラメータが分かれば視点Ａにおける方位角が計算できることを意味する拘束式である。
【００８０】
さて、ここで２つの視点（例えば、基準点Ａと移動点Ｂ）で、垂直エッジを照合して基準座標から移動点Ｂまでのカメラ動きパラメータを求めようとすると、観測１つにつき拘束式が増えるが、新たに未知パラメータｄｉＡが増える。
【００８１】
そこで、観測位置を３点（この場合に相当し、基準点Ａと移動点ＢとＣ）とすると、観測１に対して拘束式が２つ得られ、６特徴の観測で１２の拘束式、１２の未知パラメータとなり、未知パラメータが定まる。
【００８２】
より一般的には６特徴以上の観測であれば、未知パラメータは全て求まる。
【００８３】
数９を書き換えて数１０とする。
【００８４】
【数１０】
2000261808.tif 000010
【００８５】
ただし、
【００８６】
【数１１】
2000261808.tif 000011
【００８７】
【数１２】
2000261808.tif 000012
【００８８】
【数１３】
2000261808.tif 000013
【００８９】
である。
【００９０】
ここで求めるべきパラメータを数１４とする。
【００９１】
【数１４】
2000261808.tif 000014
【００９２】
これまでの関係式から、Ψが求まれば視点位置Ａ、Ｂ、Ｃ間のカメラ移動が分かることになる。
【００９３】
基準位置Ａにおける観測角を数１５とすると、Ψと数１５から、視点位置Ｂに
おける観測角と視点位置Ｃにおける観測角が数１６として導かれる。
【００９４】
【数１５】
2000261808.tif 000015
【００９５】
【数１６】
2000261808.tif 000016
【００９６】
以上は、移動パラメータと視点位置から計算された値であるが、実際に観測された角度を数１７であるとする。
【００９７】
【数１７】
2000261808.tif 000017
【００９８】
ただし、
【００９９】
【数１８】
2000261808.tif 000018
【０１００】
【数１９】
2000261808.tif 000019
【０１０１】
である。
【０１０２】
ここで、Ψと数１５から得られる数１６を以後の微分処理を容易にするため（数１０参照）、数２０に表現を書き換える。数２０は明示しないまでもΨと基準点Ａにおける観測角（数１５）の関数である。
【０１０３】
【数２０】
2000261808.tif 000020
【０１０４】
以上に対応して、観測位置Ｂ、Ｃにおける観測角の表現を数１７から数２１に表現を変える。
【０１０５】
【数２１】
2000261808.tif 000021
【０１０６】
そして、計算により予測されるＢ地点、Ｃ地点の観測角と実測との２乗誤差を数２２で表す。
【０１０７】
【数２２】
2000261808.tif 000022
【０１０８】
数２２を最小化するΨとしてパラメータが求まる。これは、従来技術で示したＬｅｖｅｎｂｅｒｇ−Ｍａｒｑｕａｒｔ法の枠組みで数２３の反復として求めることができる。
【０１０９】
【数２３】
2000261808.tif 000023
【０１１０】
数２３中、Ｈは近似ヘッセ行列（数７、数８と同形）で、Ｉは単位行列∇ｅは勾配である。
【０１１１】
ヘッセ行列と勾配を求める微分処理は数１４の未知パラメータについて行われる。
【０１１２】
以上の処理ステップをまとめると、図１４となる。これを参考例１とする。
（参考例２）
参考例２の発明は、走行する観測系の水平移動、回転角度を推定する装置であって、観測系周囲に存在するＮ個所（Ｎ≧６）の方向角を観測する手段と、上記手段を異なる観測位置（基準位置、位置１、位置２）について３回動作させた結果を保持するメモリと、記憶された３観測位置における３Ｎの方向角を用いて、基準位置に対する位置１および位置２とその位置における鉛直線周りの観測系の回転を求める手段からなることを特徴とする観測系動き推定装置である。
【０１１３】
観測系動き推定装置の参考例２について、図１５を用いて説明する。図１５はブロック図であり、１０１は全方位画像から垂直エッジを抽出する特徴抽出部、１０２は垂直エッジの対応関係を求める特徴追跡部、１０３はエッジから図１３に示す観測角に変換する６方向抽出部、１０４〜１０５は基準点Ａ、移動点Ｂ、Ｃの角度を記憶するメモリ、１０７は以上の観測から数２３に示した反復演算を行い、数１４のパラメータを求めるカメラ動き計算部である。
【０１１４】
この装置によれば、自走しながら３地点で画像上に現れる６本の線分の見える方位角を記憶することにより、その線分（例えば、テーブルや本棚の稜線）までの距離と移動成分の比、および鉛直線周りの回転角を計算することができる。実際に観測した例を図１６、図１７に示す。
【０１１５】
未知パラメータのうち、距離に関する成分（言い換えれば回転以外の成分）は全て比として求まる。
【０１１６】
この例では、移動カメラの車輪から得られた距離から数１４のＴｘＢの絶対値を定め、比例演算で絶対距離を求めている。
【０１１７】
なお、本参考例では、全方位画像に写る垂直線分を特徴として用いたが、原理的には、図１３に示すように３次元中の物体の存在（エッジや角など）を観測位置からの水平面上の方位角に置き換えることができれば、数１４のパラメータを求めることができる。
【０１１８】
したがって、撮像対象が全方位画像である必要はなく、また用いる画像特徴も線分に限定する必要はない。
【０１１９】
例えば、通常のカメラを用いてその投影面上でレンズ中心に平行な線を仮定し、その線上の特徴移動を追跡することによりカメラ動きパラメータを推定することができる。
【０１２０】
さらに、観測手段は画像である必要も無い。方位角の観測であるからレーザー光の照射によってもこの方法および装置は適用できる。
【０１２１】
最後に６線分を観測したが、７以上の線分を観測しても、増える未知パラメータ（線分までの距離）の数よりも拘束式が増えるため、数２０の最小化により求めることができる。
【０１２２】
なお、本発明をソフトウエアプログラムによって実現し、そのプラグラムをメモリ上に記憶することにより、実行することができる。その場合、そのプログラムをＣＤ−ＲＯＭ等の記録媒体を用いて、あるいはインターネット等の通信回線を用いてプログラムを配信して、本発明を実行することも可能である。
【０１２３】
【発明の効果】
以上のように本発明（請求項１）に係る画像符号化方法によれば、図１に例示される全方位画像を予測符号化する際、右端と左端が連結した動き補償を行うことにより、ＭＰＥＧ１などの通常の予測符号化を用いた方法よりも高能率に符号化することができる。
【０１２４】
また本発明（請求項２）に係る画像復号化方法によれば、図１に例示される全方位画像を予測符号化したデータを複号化する際、右端と左端が連結した動き補償を行うことにより、ＭＰＥＧ１などの通常の予測復号化を用いた方法よりも高能率に復号化することができる。
【図面の簡単な説明】
【図１】
３次元環境再現システム概念図
【図２】
多視点画像符号化の従来例を示す図
【図３】
画像上の６特徴点照合によるカメラ動きパラメータ推定図
【図４】
テンプレート符号化画像とテンプレート予測符号化画像の配置説明図
【図５】
テンプレート符号化処理手順を示す図
【図６】
テンプレート予測符号化処理手順を示す図
【図７】
全方位画像の動き補償概念図
【図８】
全方位画像の境界外動き補償の概念図
【図９】
テンプレート復号化処理手順を示す図
【図１０】
テンプレート予測復号化処理手順を示す図
【図１１】
全方位画像と任意方向画像の関係説明図
【図１２】
６垂直線による自走ロボット位置推定概念図
【図１３】
方向角と自走ロボットの座標系説明図
【図１４】
観測系動き推定方法の一実施例処理手順を示す図
【図１５】
観測系動き推定装置の一実施例ブロック図
【図１６】
観測系動き推定装置の一実施例による処理結果例１を示す図
【図１７】
観測系動き推定装置の一実施例による処理結果例２を示す図
【符号の説明】
１０１  特徴抽出部
１０２  特徴追跡部
１０３  ６方向抽出部
１０４  角度メモリ１
１０５  角度メモリ２
１０６  角度メモリ３
１０７  カメラ動き計算部