(57)【要約】【課題】符号化に要する計算量が比較的少なく高速化が可能で、フレーム間で画像内の被写体自体の変形を伴う場合等においても圧縮率を大きくすることが可能な画像符号化技術を提供する。【解決手段】第ｔフレームに隣接する第ｔ−１フレーム内の画素の画素値を参照して第ｔフレーム内の各画素の画素値を予測することにより第ｔフレームの予測符号化を行う画像符号化装置１において、符号化画像情報量評価値が最小となるように、第ｔフレーム内の各画素と第ｔ−１フレーム内の画素との対応づけを行い、それにより対応づけられる、第ｔフレーム内の画素と第ｔ−１フレーム内の画素との差である予測残差を第ｔフレーム内の各画素について求め、画素の対応づけに関する情報と、予測残差の情報とを符号化する。【選択図】          図４
2004208253.tif 000002
【特許請求の範囲】
【請求項１】
複数枚のフレームから構成される３次元画像について、符号化処理を行うべき第ｔフレームに隣接する第ｔ−１フレーム内の画素の画素値を参照して前記第ｔフレーム内の各画素の画素値を予測することにより前記第ｔフレームの予測符号化を行う画像符号化装置において、
符号化画像情報量評価値が最小となるように、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけを行う画素対応最適化手段と、
前記画素対応最適化手段により対応づけられる、前記第ｔフレーム内の画素と前記第ｔ−１フレーム内の画素との差である予測残差を前記第ｔフレーム内の各画素について求める予測残差計算手段と、
前記画素対応最適化手段による画素の対応づけに関する情報、及び前記予測残差の情報を符号化する符号化画像出力手段と、
を備え、
前記画素対応最適化手段は、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけを、少なくとも拘束条件
０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
のもとで行うこと
を特徴とする画像符号化装置。
ここで、（ｉ，ｊ）は前記第ｔフレーム内の画素の座標を表し、（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））は、前記第ｔフレーム内の画素（ｉ，ｊ）に対応づけられる前記第ｔ−１フレーム内の画素の座標を与える対応付関数を表し、ε１，ε１’は連続性条件による動きの制約を決める自然数を表す。
【請求項２】
前記画素対応最適化手段は、前記画素間の対応づけを行う際に、前記第ｔフレーム内の画素に対応づけられる前記第ｔ−１フレーム内の画素の位置について、更に少なくとも以下の拘束条件
｜ｌ（ｉ，ｊ）−ｌ（ｉ，ｊ−１）｜≦ε２
｜ｍ（ｉ，ｊ）−ｍ（ｉ−１，ｊ）｜≦ε２’
を課すこと
を特徴とする請求項１記載の画像符号化装置。
ここで、ε２，ε２’は２次元的な連続性条件による動きの制約を決める自然数を表す。
【請求項３】
前記画素対応最適化手段は、
動的計画法により、前記第ｔフレーム内の行ｉ又は列ｊ上の各画素を、前記第ｔ−１フレーム内の行ｉ又は列ｊ上の画素に対応づけることにより、行又は列を固定した条件のもとで最適化された対応付関数ｍ（ｊ）又はｌ（ｉ）を求める第１の画素対応最適化手段と、
前記第１の画素対応最適化手段により求められた対応付関数ｍ（ｊ）又はｌ（ｉ）を固定した条件のもとで、動的計画法により、前記第ｔフレーム内の列ｊ又は行ｉ上の各画素を、前記第ｔ−１フレーム内の列ｍ（ｊ）又は行ｌ（ｉ）上の画素と、対応づける第２の画素対応最適化手段と、
を有することを特徴とする請求項１又は２記載の画像符号化装置。
【請求項４】
前記画素対応最適化手段は、２次元的に動的計画法を適用することにより前記両フレーム内の画素間の対応づけを行うこと
を特徴とする請求項１又は２記載の画像符号化装置。
【請求項５】
前記画素対応最適化手段は、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけに関する情報を、前記両フレーム内の画素間の対応づけによる画素の位置変化の差分情報として求めること
を特徴とする請求項１乃至４の何れか一に記載の画像符号化装置。
【請求項６】
前記符号化画像情報量評価値は、前記予測残差の情報量と、前記画素の対応づけに関する情報の情報量との和であることを特徴とする請求項１乃至５の何れか一に記載の画像符号化装置。
【請求項７】
前記符号化画像情報量評価値は、前記予測残差の情報量であることを特徴とする請求項１乃至５の何れか一に記載の画像符号化装置。
【請求項８】
前記符号化画像情報量評価値は、前記第ｔフレーム内の各画素と、前記第ｔフレーム内の各画素に対応する前記第ｔ−１フレーム内の画素との画素間相違尺度の総和であることを特徴とする請求項１乃至５の何れか一に記載の画像符号化装置。
【請求項９】
複数枚のフレームから構成される３次元画像について、符号化処理を行うべき第ｔフレームに隣接する第ｔ−１フレーム内の画素の画素値を参照して前記第ｔフレーム内の各画素の画素値を予測することにより前記第ｔフレームの予測符号化を行う画像符号化方法において、
少なくとも拘束条件
０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
のもとで、符号化画像情報量評価値が最小となるように、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけを行い、
それにより対応づけられる、前記第ｔフレーム内の画素と前記第ｔ−１フレーム内の画素との差である予測残差を前記第ｔフレーム内の各画素について求め、前記画素の対応づけに関する情報と、前記予測残差の情報とを符号化することを特徴とする画像符号化方法。
ここで、（ｉ，ｊ）は前記第ｔフレーム内の画素の座標を表し、（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））は、前記第ｔフレーム内の画素（ｉ，ｊ）に対応づけられる前記第ｔ−１フレーム内の画素の座標を与える対応付関数を表し、ε１，ε１’は連続性条件による動きの制約を決める自然数を表す。
【請求項１０】
前記両フレーム内の画素間の対応づけを行う際に、前記第ｔフレーム内の画素に対応づけられる前記第ｔ−１フレーム内の画素の位置について、更に少なくとも以下の拘束条件
｜ｌ（ｉ，ｊ）−ｌ（ｉ，ｊ−１）｜≦ε２
｜ｍ（ｉ，ｊ）−ｍ（ｉ−１，ｊ）｜≦ε２’
を課すこと
を特徴とする請求項９記載の画像符号化方法。
ここで、ε２，ε２’は２次元的な連続性条件による動きの制約を決める自然数を表す。
【請求項１１】
前記両フレーム内の画素間の対応づけを行う場合において、
まず、動的計画法により、前記第ｔフレーム内の行ｉ又は列ｊ上の各画素を、前記第ｔ−１フレーム内の行ｉ又は列ｊ上の画素に対応づけることにより、行又は列を固定した条件のもとで最適化された対応付関数ｍ（ｊ）又はｌ（ｉ）を求め、
次に、前記対応付関数ｍ（ｊ）又はｌ（ｉ）を固定した条件のもとで、動的計画法により、前記第ｔフレーム内の列ｊ又は行ｉ上の各画素を、前記第ｔ−１フレーム内の列ｍ（ｊ）又は行ｌ（ｉ）上の画素と、対応づけを行うこと
を特徴とする請求項９又は１０記載の画像符号化方法。
【請求項１２】
前記両フレーム内の画素間の対応付けは、２次元的に動的計画法を適用することにより行うこと
を特徴とする請求項９又は１０記載の画像符号化方法。
【請求項１３】
前記両フレーム内の画素間の対応づけを行う際に、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけに関する情報を、前記両フレーム内の画素間の対応づけによる画素の位置変化の差分情報として求めること
を特徴とする請求項９乃至１２の何れか一に記載の画像符号化方法。
【請求項１４】
前記符号化画像情報量評価値は、前記予測残差の情報量と、前記画素の対応づけに関する情報の情報量との和であることを特徴とする請求項９乃至１３の何れか一に記載の画像符号化方法。
【請求項１５】
前記符号化画像情報量評価値は、前記予測残差の情報量であることを特徴とする請求項９乃至１３の何れか一に記載の画像符号化方法。
【請求項１６】
前記符号化画像情報量評価値は、前記第ｔフレーム内の各画素と、前記第ｔフレーム内の各画素に対応する前記第ｔ−１フレーム内の画素との画素間相違尺度の総和であることを特徴とする請求項９乃至１３の何れか一に記載の画像符号化方法。
【請求項１７】
コンピュータで実行することにより、請求項１乃至８の何れか一に記載の画像処理装置が実現されることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、予測符号化により動画像や立体画像等の３次元画像を符号化する画像符号化技術に関し、特に、フレーム間で画像内の被写体自体の変形を伴う場合等においても高圧縮率の得られる画像符号化技術に関する。
【０００２】
【従来の技術】
動画像や立体画像等の複数枚のフレームから構成される３次元画像の符号化には、フレーム間の相関の除去が有効とされている。すなわち、符号化すべき対象フレームの画像と、それに隣接する隣接フレームの画像との間で、画素ごとの差分を計算し、この差分値を送信するというものである。この方式は、フレーム間予測符号化と呼ばれる。通常、画素値そのものよりも差分値のほうが発生頻度の偏り（エネルギーの集中度）が大きく、エントロピーが小さいため、高能率で符号化が可能である。さらに、フレーム間の変化が大きな画像でも高圧縮率を実現するためには、動き補償予測符号化技術が用いられる（例えば、非特許文献１参照）。
【０００３】
以下、３次元画像として動画像を例にとって、従来のフレーム間予測符号化について説明する。
【０００４】
図１２はフレーム間予測符号化方式の原理を説明するためのブロック図である。
図１２において、左半が送信側、右半が受信側を表す。送信側は、フレームメモリ１１０，１２０、及び符号化器１３０を有する構成とされる。また、受信側は、フレームメモリ１４０，１５０、及び復号器１６０を有する構成とされる。
【０００５】
フレームメモリ１１０には、隣接フレーム（以下、「第ｔ−１フレーム」という。）の画像信号ａ（ｉ，ｊ，ｔ−１）が記憶され、フレームメモリ１２０には、対象フレーム（以下、「第ｔフレーム」という。）の画像信号ａ（ｉ，ｊ，ｔ）が記憶される。ここで、ｉは行番号、ｊは列番号、ｔ，ｔ−１はフレーム番号である。ｔは、原時刻における画像であることを示している。また、ｔ−１は、現時刻ｔより前に既に符号化処理がされた過去のフレームの画像であることを示している。同様に、受信側のフレームメモリ１４０には、復号された第ｔ−１フレームの画像信号ａ（ｉ，ｊ，ｔ−１）が記憶され、フレームメモリ１５０には、復号により得られる第ｔフレームの画像信号ａ（ｉ，ｊ，ｔ）が記憶される。
【０００６】
最も単純なフレーム間予測による符号化と復号は、以下のようにして行われる。
【０００７】
送信側の符号化器１３０は、フレームメモリ１２０に記憶された第ｔフレームの走査と同期して、フレームメモリ１１０に記憶された第ｔ−１フレームの画像内の画素指定アドレス（ｉ，ｊ）の画素を読み出す。画像の走査は、例えば、ラスタスキャン方式に行われる。それぞれのフレームメモリ１１０，１２０から読み出された画素の画素指定アドレスを（ｉ，ｊ）で表す。また、フレームメモリ１１０から読み出された第ｔ−１フレーム内の画素の画素値をａ（ｉ，ｊ，ｔ−１）、フレームメモリ１２０から読み出された第ｔフレーム内の画素の画素値をａ（ｉ，ｊ，ｔ）で表す。符号化器１３０は、両画素値間の差分
【数１】
2004208253.tif 000003
を計算する。そして、この差分δａ（ｉ，ｊ，ｔ）’の情報が受信側に送信される。
【０００８】
一方、受信側では、復号器１６０は、この差分δａ（ｉ，ｊ，ｔ）’及びフレームメモリ１４０から読み出される第ｔ−１フレームの画素値ａ（ｉ，ｊ，ｔ−１）を用いて、
【数２】
2004208253.tif 000004
により、第ｔフレーム内の画素の画素値ａ（ｉ，ｊ，ｔ）を復元する。
【０００９】
（１）式は、第ｔフレームの画素値ａ（ｉ，ｊ，ｔ）を第ｔ−１フレームの画素値ａ（ｉ，ｊ，ｔ−１）によって予測し、その差分δａ（ｉ，ｊ，ｔ）’を送信している。差分δａ（ｉ，ｊ，ｔ）’は、予測しきれなかった誤差分であり、「予測残差」と呼ばれる。一般に、空間的位置（ｉ，ｊ）が同一である画素の画素値は、第ｔ−１フレーム間で類似している場合が多い。従って、予測残差δａ（ｉ，ｊ，ｔ）’の分布は０の近傍に集中したものとなり、その実効値（エネルギー）は元の信号ａ（ｉ，ｊ，ｔ）の実効値よりも大幅に小さくなる。そのため、前者のエントロピーは後者のエントロピーに比して格段に小さくなる。すなわち、送信情報量を大幅に低減させることが可能となり、高効率な動画通信が実現される。
【００１０】
なお、実際に高効率な動画通信を行うためには、予測残差δａ（ｉ，ｊ，ｔ）’をそのまま（例えば、２進数のまま）送信するのではなく、ハフマン符号、ブロック符号などの情報源符号化処理又は復号処理を、符号化器１３０又は復号器１６０に組み込む必要がある。
【００１１】
以上に述べたフレーム間予測符号化技術は、第ｔ−１フレーム間の画像の動きが小さいことを前提としている。すなわち、画素の空間的位置（ｉ，ｊ）が同一であれば、第ｔフレームでの画素値ａ（ｉ，ｊ，ｔ）は、第ｔ−１フレームでの画素値ａ（ｉ，ｊ，ｔ−１）で良好に近似することができるという仮定のもとで、送信情報量の圧縮効果を期待したものである。従って、隣接するフレーム間の画像の変化が大きい場合には、当然、予測残差δａ（ｉ，ｊ，ｔ）’が大きくなり、そのエントロピーが増大するために圧縮率は低下する。
【００１２】
そこで、このようなフレーム間の画像の変化による圧縮率低下の対策として用いられるのが、動き補償予測符号化技術である（例えば、非特許文献１，２参照）。
【００１３】
図１３は動き補償を含むフレーム間予測符号化の原理を説明する図である。
図１３には、第ｔ−１フレームの画像２１０と第ｔフレームの画像２２０とが示されている。画像中で斜線を付した部分は、動きがある被写体領域２１２，２２２を表す。このように動きがある被写体が含まれると、上述の単純なフレーム間予測符号化では、両被写体領域２１２，２２２の排他論理和部分での予測残差δａ（ｉ，ｊ，ｔ）’が大きくなり、伝送情報の圧縮率は低下する。
【００１４】
そこで、以下のような動き予測が行われる。
まず、第ｔフレームの画像２２０を８×８画素程度のブロックに分割する。各ブロックの位置座標はｋ＝（ｕ，ｖ）により指定される。そして、各ブロックを平行移動して、それぞれのブロック内の画像に最も類似する同サイズの領域を、第ｔ−１フレームの画像２１０内で探索する。この探索によって定まる第ｔ−１フレーム内の画像領域を、ここでは「一致ブロック」と呼ぶ。また、第ｔフレームの画像２２０内のあるブロックを終点とし、そのブロックに対応する第ｔ−１フレームの画像２１０内の一致ブロックを始点とするベクトルｍｖ（ｋ）を「動きベクトル」という。
【００１５】
各ブロック対して定まる動きベクトルｍｖ（ｋ）によりフレーム間のブロックの動きを予測し、このブロックの動きによる画素値変化分を削除して情報量の圧縮を行うのが動き補償である。
【００１６】
再び図１２を参照して、以下、符号化器１３０で行われる動き補償予測符号化方法について説明する。
【００１７】
フレームメモリ１２０には、図１３に示した第ｔフレームの画像２２０が格納されており、フレームメモリ１１０には、図１３に示した第ｔ−１フレームの画像２１０が格納されているものとする。そこで、第ｔフレームの画像２２０のｋ番目のブロック２２２に注目して、動き補償予測符号化の原理を説明する。
【００１８】
いま第ｔフレーム及び第ｔ−１フレームの画像が２５６×２５６画素のサイズであるとし、各画素の位置は｛（ｉ，ｊ）；ｉ＝０，１，…，２５５，ｊ＝０，１，…，２５５｝で番地指定されるものとする。また、ブロックのサイズは８×８であるとする。この場合、１フレームの画像は３２×３２個のブロックからなる。各ブロックは｛ｋ＝（ｕ，ｖ）；ｕ＝０，１，…，３１，ｖ＝０，１，…，３１｝で２次元的に番号づけられる。
【００１９】
ｋ＝（ｕ，ｖ）で指定されるブロックの各画素の位置は、
【数３】
2004208253.tif 000005
により表される。
【００２０】
この第ｋブロックの動きベクトルは、ｍｖ（ｋ）＝（Δｉ，Δｊ）で表されるものとする。この動きベクトルｍｖ（ｋ）は、第ｔ−１フレームから第ｔフレームにかけてのブロックｋの左上隅の点（８ｕ，８ｖ）の動きを示している。このとき、（３）式の画素（８ｕ＋δｕ，８ｖ＋δｖ）に対応する第ｔ−１フレームの画素の位置は、（８ｕ＋δｕ−Δｉ，８ｖ＋δｖ−Δｊ）と定まる。動き補償予測符号化においては、これらの画素間の差分である
【数４】
2004208253.tif 000006
の値を予測残差として送信する。実際には、この予測残差に加えて、各ブロックの動きベクトル｛ｍｖ（ｋ）＝（Δｉ，Δｊ）｝も送信する必要がある。
【００２１】
次に、受信側における復号処理について説明する。
受信側の復号器１６０は、上記各ブロックごとに、１個の動きベクトル｛ｍｖ（ｋ）＝（Δｉ，Δｊ）｝と、８×８個の予測残差ｄ（８ｕ＋δｕ，８ｖ＋δｖ）を受信する。復元する第ｔフレームの画像内の第ｋブロックの各画素（８ｕ＋δｕ，８ｖ＋δｖ）に対応する隣接ブロックの画素位置は、（８ｕ＋δｕ−Δｉ，８ｖ＋δｖ−Δｊ）と定まるので、
【数５】
2004208253.tif 000007
によって元の画素値が完全に復元される。これをブロック内の総ての画素に対して行うことにより第ｋブロックが復元される。同様の処理をフレーム内の総てのブロックに対して行うことにより、１フレームの画素が完全に復元される。
【００２２】
【非特許文献１】
黒田英夫，「デジタル信号処理シリーズ  第１５巻  画像符号化技術初版」，株式会社昭光堂，１９９６年１２月，ｐ．５７−６５
【非特許文献２】
電子情報通信学会編，「エンサイクロペディア電子情報通信ハンドブック  第１版」，株式会社オーム社，１９９８年１１月，ｐ．２１２
【非特許文献３】
内田誠一，迫江博昭，”動的計画法に基づく単調連続２次元ワープ法の検討”，電子情報通信学会論文誌  Ｄ−ＩＩ，社団法人電子情報通信学会，１９９８年６月，第Ｊ８１−Ｄ−ＩＩ巻，第６号，ｐ．１２５１−１２５８
【非特許文献４】
磯道義典，小川辰男，”動的計画法によるパターンマッチング”，情報処理，社団法人情報処理学会，１９７５年１月，第１６巻，第１号，ｐ．１５−２２
【非特許文献５】
迫江博昭，”音声認識における動的計画法の応用”，ｂｉｔ，共立出版株式会社，１９８３年７月，第１５巻，第８号，ｐ．１３５−１４２
【００２３】
【発明が解決しようとする課題】
しかしながら、上記従来の動き補償予測符号化技術においては、ブロック探索の計算量が多くなるという欠点がある。すなわち、１ブロック内の画素数をＮｐ、１フレーム内のブロック数をＮｂとする。このとき、１フレーム内の画素数は、Ｎ２＝Ｎｐ×Ｎｂである。１つのブロックについて、第ｔ−１フレーム内での一致ブロックを探索する範囲をＷ×Ｗとすると、この探索に要する計算量は、
【数６】
2004208253.tif 000008
のオーダーとなる。
【００２４】
また、フレーム間で画像内の被写体自体の変形を伴う場合や被写体が回転する場合等には、圧縮率が低くなるという欠点がある。すなわち、上述の図１３に示したように、フレーム間で画像内の被写体が平行移動するような場合に限っては高い圧縮効果が得られるが、図１４に示したように、被写体自体が変形を伴う場合には、ブロックの平行移動による探索・補償では予測残差の圧縮に限界がある。
【００２５】
そこで、本発明の解決すべき課題は、符号化に要する計算量が比較的少なく高速化が可能で、フレーム間で画像内の被写体自体の変形を伴う場合等においても圧縮率を大きくすることが可能な画像符号化技術を提供することにある。
【００２６】
【課題を解決するための手段】
以下、上述の課題を解決するための手段について説明するが、まず最初に、動的計画法の一利用形態であるＤＰマッチング法による２フレーム内の画素間の対応づけの手法について説明し、続いて、本発明の構成及び作用について説明する。
【００２７】
〔１〕ＤＰマッチング法による２フレーム内の画素間の対応づけの手法
【００２８】
本発明は、複数のフレームからなる動画像や立体画像等の３次元画像一般について適用可能なものであるが、ここでは、説明上、一例として動画像を符号化する場合について、本発明の画像符号化技術の原理について説明する。
【００２９】
まず最初に、以下の説明で用いる記号法について整理する。
各フレーム内の画素値については、第ｔ−１フレームの画素値を｛ｂｌ，ｍ＝ａ（ｌ，ｍ，ｔ−１）；ｌ＝１，２，…，Ｎ，ｍ＝１，２，…，Ｎ｝、第ｔフレームの画素値を｛ａｉ，ｊ＝ａ（ｉ，ｊ，ｔ）；ｉ＝１，２，…，Ｎ，ｊ＝１，２，…，Ｎ｝で略式表記する。ここで、ｌ，ｉは行番号、ｍ，ｊは列番号である。
【００３０】
本発明では、第ｔフレームの各画素ａｉ，ｊに対応する第ｔ−１フレームの画素ｂｌ，ｍを最適に定め、予測残差ａｉ，ｊ−ｂｌ，ｍにより第ｔフレームの画像の予測符号化を行う。フレームの進行（ｔ−１→ｔ）に伴う被写体形状の変形に伴い、第ｔフレーム内の各画素の第ｔ−１フレーム内の画素への対応づけも画素ごとに変化する。そこで、第ｔフレーム内の画素の位置（ｉ，ｊ）に対応づけられる第ｔ−１フレームの画素の位置（ｌ，ｍ）を、対応付関数（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））により近似する。
【数７】
2004208253.tif 000009
【００３１】
また、上記対応づけの最適化を図るための評価関数を、
【数８】
2004208253.tif 000010
により定義する。ここで、ｄ（ｉ，ｊ，ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））は画素間相違度といい、
【数９】
2004208253.tif 000011
により定義される。‖ａｉ，ｊ−ｂｌ（ｉ，ｊ），ｍ（ｉ，ｊ）‖は、画素ａｉ，ｊと画素ｂｌ（ｉ，ｊ），ｍ（ｉ，ｊ）との間の相違の尺度量であり、例えば、モノクロ画像の場合には、画素の絶対値差｜ａｉ，ｊ−ｂｌ（ｉ，ｊ），ｍ（ｉ，ｊ）｜や２乗差（ａｉ，ｊ−ｂｌ（ｉ，ｊ），ｍ（ｉ，ｊ））２、カラー画像の場合には、画素ベクトル間の距離やそれに準じる尺度等が用いられる。
【００３２】
そして、評価関数Ｄ（ｔ，ｔ−１）を最小化するように対応付関数（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））を定める。これにより、対応付関数（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））によって画素ａｉ，ｊに対応づけられた画素ｂｌ，ｍの画素値は、画素ａｉ，ｊの画素値に近い値をとり、画素ｂｌ，ｍを参照画素とした予測残差の絶対値｜ａｉ，ｊ−ｂｌ，ｍ｜の値は平均的に圧縮される。すなわち、予測残差のエントロピーを低減され、符号化による圧縮率の向上を図ることができる。
【００３３】
本発明においては、評価関数Ｄ（ｔ，ｔ−１）の最小化を動的計画法を用いて行うことを特徴とする。非特許文献３では、パターンマッチングの分野において、２つの対応付関数を有する評価関数の最適化を、２次元最適化問題として厳密に行う方法が記載されている。
【００３４】
本発明においては、このような２次元的な動的計画法を用いて評価関数Ｄ（ｔ，ｔ−１）を最小化する最適な対応付関数ｌ（ｉ，ｊ），ｍ（ｉ，ｊ）を決定することができる。
【００３５】
尚、２次元的な動的計画法を用いる場合には、両フレーム間で被写体のトポロジーは保存されると考えられることから、境界条件
【数１０】
2004208253.tif 000012
【数１１】
2004208253.tif 000013
及び、２次元的な単調連続性条件を課する。
【００３６】
ここで、「単調性」とは、第ｔフレーム内の任意の２つの画素と、それらの画素に対応づけられた第ｔ−１フレーム内の２つの画素の上下左右関係が、対応づけの前後で保存されることをいう。すなわち、
【数１２】
2004208253.tif 000014
である。また、「連続性」とは、第ｔフレーム内の互いに隣接する任意の２つの画素に対応づけられた第ｔ−１フレーム内の２つの画素が、互いに近傍に存在することをいう。すなわち、
【数１３】
2004208253.tif 000015
である。ここで、ε１，ε２は１又は１近傍の任意の小さい自然数（だいたい、７以下の自然数）であるが、計算量を減らすため、通常は、ε１＝２，ε２＝１に設定される。
【００３７】
従って、２次元的な単調連続性条件は以下のように表される。
【数１４】
2004208253.tif 000016
【数１５】
2004208253.tif 000017
【数１６】
2004208253.tif 000018
【数１７】
2004208253.tif 000019
【００３８】
更に、必要に応じて以下のような整合窓条件（窓幅ｗ＞０）を用いることもできる。
【数１８】
2004208253.tif 000020
【００３９】
ところで、非特許文献３に記載の方法を用いた場合、画像サイズＮに関して指数オーダーという膨大な計算量が必要とされることが知られている。
【００４０】
そこで、本発明の高速化手法としては、非特許文献４を参考として、第ｔフレームの行方向の画素の対応づけと列方向の画素の対応づけとを２段階に分割して近似的に行う。すなわち、まず、行番号ｉを固定して、行方向のライン上における１次元対応付関数ｍ＝ｍ（ｊ｜ｉ）を、評価関数
【数１９】
2004208253.tif 000021
を用いて、この評価関数Ｄ（ｔ，ｔ−１｜ｉ）が最小となる対応付関数ｍ＝ｍ（ｊ｜ｉ）として定める。そしてその後、今度は列番号ｊ及び対応付関数ｍ（ｊ）を固定して、列方向の１次元対応付関数ｌ＝ｌ（ｉ｜ｊ，ｍ）を、評価関数
【数２０】
2004208253.tif 000022
を用いて、この評価関数Ｄ（ｔ，ｔ−１｜ｊ，ｍ）が最小となる対応付関数ｌ（ｉ｜ｊ，ｍ）として定め、対応付関数ｌ（ｉ，ｊ），ｍ（ｉ，ｊ）を近似的に最適化するという手法をとる。
【００４１】
そこで、次にｉ行目のライン上において評価関数Ｄ（ｔ，ｔ−１｜ｉ）を最小化するための１次元対応付関数ｍ＝ｍ（ｊ｜ｉ）の決定方法について説明する。
【００４２】
まず、画素間のトポロジーは保存されると考えられることから、１次元対応付関数ｍ＝ｍ（ｊ｜ｉ）に対して、境界条件
【数２１】
2004208253.tif 000023
【数２２】
2004208253.tif 000024
及び、１次元的な単調連続性条件
【数２３】
2004208253.tif 000025
を課する。尚、ここでは、計算量を少なくするために、一例として、ｐの範囲は｛０，１，２｝としているが、一般的な１次元的な単調連続性条件では、
【数２４】
2004208253.tif 000026
と表される。すなわち、１次元的な単調連続性条件とは、第ｔフレーム内のライン上の各画素に対応づけられる第ｔ−１フレーム内のライン上の画素の順番が、それに対応する第ｔフレーム内のライン上の画素の順番に対して入れ替わることがなく（ｍ（ｊ｜ｉ）≧ｍ（ｊ−１｜ｉ）；単調性）、且つ、対応する２画素の座標が互いに近傍にある（｜ｍ（ｊ｜ｉ）−ｍ（ｊ−１｜ｉ）｜≦ε；連続性）とする条件をいう。
【００４３】
以上のような拘束条件のもとで、動的計画法の一利用形態であるＤＰマッチング法を適用して対応付関数ｍ（ｊ｜ｉ）の決定を行う。尚、ＤＰマッチング法については、主に音声認識の分野において用いられており、例えば、非特許文献５等の文献に記載されている。
【００４４】
具体的に、対応付関数ｍ（ｊ｜ｉ）の決定を行うには、初期条件を、
【数２５】
2004208253.tif 000027
として、ｊ＝０，１，…，Ｎ；ｊ−ｒ≦ｍ≦ｊ＋ｒの領域において、漸化式
【数２６】
2004208253.tif 000028
を計算すると同時に、その最適パラメータを
【数２７】
2004208253.tif 000029
として、配列ｐ（ｊ，ｍ｜ｉ）に保存する。ここで、演算子
【数２８】
2004208253.tif 000030
は、ｘｐの値が最小であるｐを選択することを意味する演算子である。また、ｐ（ｌ，ｍ｜ｉ）は、最小化におけるパラメータｐの最適値を保存する配列であり、バックポインタと呼ばれる。また、ｒはｌとｍとの対応のズレを規制するためのパラメータである。
【００４５】
以上に説明した方法は、次のようなアルゴリズムにより簡潔に表される。
【数２９】
2004208253.tif 000031
【００４６】
図１はＤＰマッチングを説明する図である。
図１においては、横軸を第ｔフレーム内の第ｉ行目のライン上の座標ｊ、縦軸を第ｔ−１フレームの第ｉ行目のライン上の座標ｍにとった（ｊ，ｍ）平面を表している。この平面上の点（ｊ，ｍ）では、ａｉ，ｊとｂｉ，ｍとの間の画素間相違度ｄ（ｉ，ｊ，ｉ，ｍ）が計算される。そして、経路ｍ＝ｍ（ｊ｜ｉ）上の総和が最小となるように、対応付関数ｍ（ｊ）を最適化する。
【００４７】
ここで、（１９）式の境界条件ｍ（１｜ｉ）＝１は、初期条件（２２）式により実現される。また、（２０）式の境界条件ｍ（Ｎ｜ｉ）＝Ｎは、（２３）式及び（２４）式の計算点を、点（ｊ，ｍ）＝（Ｎ，Ｎ）で終了することにより実現されている。また、１次元的な単調連続性条件（２１）式は、（２３）式及び（２４）式の最小化付帯条件（ｐ＝０，１，２）として実現されている。この１次元的な単調連続性条件（２１）式の制約により、ｊの進行に伴うｍの変化は、図２のように制限される。
【００４８】
（２３）式及び（２４）式の計算が、（ｊ，ｍ）＝（Ｎ，Ｎ）点まで終了した時点で、（１７）式の最小値は、
【数３０】
2004208253.tif 000032
と定まる。更に、以下のようなバックトラック処理で、対応付関数｛ｍ（ｊ｜ｉ）；ｊ＝１，２，…，Ｎ｝と、これらの差分である差分対応付関数｛δｍ（ｊ｜ｉ）；ｊ＝１，２，…，Ｎ−１｝が降順に定まる。
【数３１】
2004208253.tif 000033
【００４９】
ここで、δｍ（ｊ｜ｉ）は、対応付関数ｍ（ｊ｜ｉ）の差分δｍ（ｊ｜ｉ）＝ｍ（ｊ｜ｉ）−ｍ（ｊ−１｜ｉ）を表す。このバックトラック処理は、以下のようなアルゴリズムとして簡潔に表される。
【数３２】
2004208253.tif 000034
【００５０】
以上の計算を、第ｔフレーム内の総ての行ｉについて行うことで、行方向について近似的に最適化された対応付関数｛ｍ（ｊ）＝ｍ（ｊ｜ｉ）；ｉ，ｊ＝１，２，…Ｎ｝及び｛δｍ（ｊ）＝δｍ（ｊ｜ｉ）；ｉ，ｊ＝１，２，…Ｎ｝が定まる。
【００５１】
次に、以上の行方向の対応付けの結果を踏まえて、同様の方法により、今度は列番号ｊ，ｍ（ｊ）を固定して、列方向のフレーム間の画素の対応付けを行う。この場合、第ｔフレームの第ｊ列と第ｔ−１フレームの対応付けられた列方向のラインｍ（ｊ）を固定して、列方向のライン上における１次元対応付関数ｌ＝ｌ（ｉ｜ｊ，ｍ）を、（１８）式に示した評価関数が最小となるように定める。
また、境界条件は、
【数３３】
2004208253.tif 000035
【数３４】
2004208253.tif 000036
単調連続性条件は、
【数３５】
2004208253.tif 000037
となる。
【００５２】
対応付関数ｌ（ｉ）＝ｌ（ｉ｜ｊ，ｍ）の最適化は、初期条件を
【数３６】
2004208253.tif 000038
として、ｉ＝０，１，…，Ｎ；ｉ−ｒ≦ｌ≦ｉ＋ｒの領域において、漸化式
【数３７】
2004208253.tif 000039
を計算すると同時に、バックポインタ
【数３８】
2004208253.tif 000040
を計算することにより行う。
【００５３】
また、バックトラック処理は、
【数３９】
2004208253.tif 000041
のようになる。ここで、δｌ（ｉ｜ｊ，ｍ）は、対応付関数ｌ（ｉ｜ｊ，ｍ）の差分δｌ（ｉ｜ｊ，ｍ）＝ｌ（ｉ｜ｊ，ｍ）−ｌ（ｉ−１｜ｊ，ｍ）を表す。
【００５４】
尚、このバックトラック処理において、同時に予測残差｛δａｉ，ｊ  ＝  ａｉ，ｊ−ｂｌ（ｉ），ｍ（ｊ）；ｉ，ｊ＝１，２，…，Ｎ｝も計算される。すなわち、以下のようなアルゴリズムとして表される。
【数４０】
2004208253.tif 000042
【００５５】
以上の処理によって、第ｌフレームの画像は、予測残差｛δａｉ，ｊ｝及び動き差分｛ｑ（ｉ，ｊ）＝（δｌ（ｉ，ｊ），δｍ（ｉ，ｊ））｝により予測符号化される。
【００５６】
図３は行方向の動き探索と列方向の動き探索との関係を示す図である。
図３（ａ）は、第ｔフレームの画像の画素配列を模式的に表現したものである。各格子点には画素ａｉ，ｊが対応する。図３（ｂ）は行方向の動き探索結果を模式的に示したものである。縦方向の折れ線は、各行ｉで対応付関数ｍ（ｊ｜ｉ）で指定される列を結んだものである。図３（ｃ）は、図３（ｂ）に加えて列方向探索を行った例である。図３（ｂ）の折れ線に沿って動き探索を行っている。
【００５７】
尚、ここでは一例として動画像の予測符号化という目的を想定して説明したが、本発明の適用範囲は、立体画像等の一般的な３次元画像の符号化についても適用可能である。また、３次元画像が完全な形に復号される可逆符号化の範囲で説明したが、本発明の予測符号化により生成される信号に何らかの他の可逆圧縮処理を追加するもの、さらには非可逆圧縮処理を追加して構成される非可逆圧縮形において利用される形態であってもよい。
【００５８】
また、上記ＤＰマッチングにおいては、（２２）式，（２３）式及び（３１）式，（３２）式は｛（ｊ，ｍ）；ｊ＝１，２，…，Ｎ，ｊ−ｒ≦ｍ≦ｊ＋ｒ｝及び｛（ｉ，ｌ）；ｉ＝１，２，…，Ｎ，ｉ−ｒ≦ｌ≦ｉ＋ｒ｝の総ての点について計算することとしたが、高速化が要求されるような場合においては、ＤＰマッチングにビームサーチ法等を適用し、一部の（ｊ，ｍ）又は（ｉ，ｌ）について（２２）式，（２３）式又は（３１）式，（３２）式を計算するようにしてもよい。尚、ビームサーチ法の適用によるＤＰマッチングの高速化の方法については、音声認識の分野において行われた例が知られており（非特許文献３参照）、既に公知事項であるため、ここでは説明は省略する。
【００５９】
〔２〕本発明の構成及び作用
【００６０】
本発明の画像符号化装置の第１の構成は、複数枚のフレームから構成される３次元画像について、符号化処理を行うべき第ｔフレームに隣接する第ｔ−１フレーム内の画素の画素値を参照して前記第ｔフレーム内の各画素の画素値を予測することにより前記第ｔフレームの予測符号化を行う画像符号化装置において、符号化画像情報量評価値が最小となるように、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけを行う画素対応最適化手段と、前記画素対応最適化手段により対応づけられる、前記第ｔフレーム内の画素と前記第ｔ−１フレーム内の画素との差である予測残差を前記第ｔフレーム内の各画素について求める予測残差計算手段と、前記画素対応最適化手段による画素の対応づけに関する情報、及び前記予測残差の情報を符号化する符号化画像出力手段と、を備え、前記画素対応最適化手段は、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけを、少なくとも拘束条件
０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
のもとで行うことを特徴とする。ここで、（ｉ，ｊ）は前記第ｔフレーム内の画素の座標を表し、（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））は、前記第ｔフレーム内の画素（ｉ，ｊ）に対応づけられる前記第ｔ−１フレーム内の画素の座標を与える対応付関数を表し、ε１，ε１’は連続性条件による動きの制約を決める自然数を表す。
【００６１】
このように、第ｔフレーム内の各画素と第ｔ−１フレーム内の画素との画素同士の対応づけを行い、この画素単位の対応付に基づく予測符号化を行うことにより、フレーム間でフレーム内の被写体画像が変形や回転等を伴う場合においても、柔軟に非線形伸縮を伴った精度の高い対応付が可能となる。従って、上記従来の動き補償予測符号化の場合に比べて、予測残差計算手段が求める予測残差を小さくすることができる。すなわち、第ｔフレームの予測残差のエントロピーを小さくすることができるため、符号化画像出力手段による符号化時の圧縮率を大きくすることができる。
【００６２】
また、第１又は第２の画素対応最適化手段が動的計画法による両フレームの画素間の対応付を行う際に、画像の縦横２方向について１次元的な単調連続性条件０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
を課すことで、画像の縦横２方向に対して被写体画像のトポロジーを保存するという妥当な条件の下で、最適化される対応付関数の変化範囲に条件を課し、対応付情報の符号長を一定の長さ以下に抑えることができる。すなわち、例えば、ε１＝ε１’＝２とすれば、δｌ（ｉ，ｊ）＝ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）及びδｍ＝ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）のとり得る値は０，１，２の何れかの値であるため、対応付情報は、高々２ビットの符号長で表すことが可能であり、それ以上の符号長となることはない。従って、対応付情報を符号化した場合の情報量の上限を一定の値以下に抑えることができる。また、画像の縦横２方向に対して被写体画像のトポロジーが保存されるという条件は、通常の画像においては妥当な条件であるため、上記１次元的な単調連続性条件を課すことによる、予測残差の増加は少ないと考えられる。従って、予測残差情報の情報量も抑えられる。予測符号化の場合、最終的な符号化画像の情報量は、予測残差情報の情報量と対応付情報の情報量の和によって決まるが、上記１次元的な単調連続性条件を課して対応付を行うことで、両者のバランスを最適に近い状態とすることが可能となり、最終的な符号化画像の情報量を低減させ、圧縮率を高めることが可能となる。
【００６３】
ここで、符号化画像情報量評価値とは、符号化画像出力手段が出力する、符号化された第ｔフレームの画像の情報量を評価するための基準となる値をいい、両フレーム内の対応づけられた画素の画素値から所定の評価関数によって求められる値である。
【００６４】
また、連続性条件による動きの制約を決める自然数ε１，ε１’としては、１又は１近傍の小さい自然数とされ、対応付情報の符号量を抑えるという意味から、好ましくは７以下の自然数（上限３ビット）、より好ましくは３以下の自然数（上限２ビット）とするのがよい。
【００６５】
尚、符号化画像出力手段は、公知の各種情報源符号化の手法、例えば、ハフマン符号化、ランレングス符号化、算術符号化等によって画素の対応づけに関する情報及び予測残差の情報を符号化することができる。
【００６６】
本発明の画像符号化装置の第２の構成は、前記第１の構成において、前記画素対応最適化手段は、前記画素間の対応づけを行う際に、前記第ｔフレーム内の画素に対応づけられる前記第ｔ−１フレーム内の画素の位置について、更に少なくとも以下の拘束条件
｜ｌ（ｉ，ｊ）−ｌ（ｉ，ｊ−１）｜≦ε２
｜ｍ（ｉ，ｊ）−ｍ（ｉ−１，ｊ）｜≦ε２’
を課すことを特徴とする。
【００６７】
このように、２次元的な単調連続性条件
０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
｜ｌ（ｉ，ｊ）−ｌ（ｉ，ｊ−１）｜≦ε２
｜ｍ（ｉ，ｊ）−ｍ（ｉ−１，ｊ）｜≦ε２’
を課すことによって、対応付による画素の動き距離を、所定の距離以内に抑えることができる。そのため、対応付関数を符号化する際に、更に符号量を減少させることが可能となり、その結果、画像の圧縮率を更に大きくすることができる。
【００６８】
ここで、連続性条件による動きの制約を決める自然数ε２，ε２’としては、１又は１近傍の小さい自然数とされ、対応付情報の符号量を抑えるという意味から、好ましくは７以下の自然数（上限３ビット）、より好ましくは３以下の自然数（上限２ビット）とするのがよい。
【００６９】
本発明の画像符号化装置の第３の構成は、前記第１又は２の構成において、前記画素対応最適化手段は、動的計画法により、前記第ｔフレーム内の行ｉ又は列ｊ上の各画素を、前記第ｔ−１フレーム内の行ｉ又は列ｊ上の画素に対応づけることにより、行又は列を固定した条件のもとで最適化された対応付関数ｍ（ｊ）又はｌ（ｉ）を求める第１の画素対応最適化手段と、前記第１の画素対応最適化手段により求められた対応付関数ｍ（ｊ）又はｌ（ｉ）を固定した条件のもとで、動的計画法により、前記第ｔフレーム内の列ｊ又は行ｉ上の各画素を、前記第ｔ−１フレーム内の列ｍ（ｊ）又は行ｌ（ｉ）上の画素と、対応づける第２の画素対応最適化手段と、を有することを特徴とする。
【００７０】
このように、１次元的な動的計画法を、直交する２方向に対して順次適用して両フレームの画素間の対応付を行うことにより、対応付けに要する計算量を少なくすることができ、符号化処理の高速化を図ることが可能となる。
【００７１】
本発明の画像符号化装置の第４の構成は、前記第１又は２の構成において、前記画素対応最適化手段は、２次元的に動的計画法を適用することにより前記両フレーム内の画素間の対応づけを行うことを特徴とする。
【００７２】
この構成により、画素対応最適化手段は、比較的少ない計算回数により、両フレーム内の画素間の対応づけを行うことが可能となる。従って、画像符号化処理の高速化を図ることができる。また、２次元的な動的計画法を用いるため、フレーム内の被写体画像がフレーム間で斜め方向に移動した場合や、２つの被写体画像がフレーム間ですれ違いを起こした場合等においても、精度よく両フレーム内の画素間の対応づけを行うことが可能である。そのため、かかる場合でも高い圧縮率を得ることができる。
【００７３】
ここで、「２次元的に動的計画法を適用する」とは、２次元平面からなる一方のフレーム内の画素（ｉ，ｊ）を、２次元平面からなる他方のフレーム内の画素（ｌ，ｍ）に対応づける、対応付関数（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））を、動的計画法により、画素間相違尺度の総和が最小となるように最適化することをいう。
【００７４】
本発明の画像符号化装置の第５の構成は、前記第１乃至４の何れか一の構成において、前記画素対応最適化手段は、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけに関する情報を、前記両フレーム内の画素間の対応づけによる画素の位置変化の差分情報として求めることを特徴とする。
【００７５】
このように、符号化画像に含まれる、対応づけによる画素の位置変化の情報を、上記画素の位置変化の差分情報とすることで、各画素の位置変化の情報を効率よく圧縮することが可能となる。特に、上記２次元的又は１次元的な単調連続性条件を課した場合には、画素間の位置変化の差分情報のダイナミックレンジが所定の範囲に限定される。そのため、符号化画像出力手段による、各画素の一辺か情報の圧縮効率が向上する。
【００７６】
本発明の画像符号化装置の第６の構成は、前記第１乃至５の何れか一の構成において、前記符号化画像情報量評価値は、前記予測残差の情報量と、前記画素の対応づけに関する情報の情報量との和であることを特徴とする。
【００７７】
このように、符号化画像情報量評価値として、予測残差の情報量と画素の対応づけに関する情報の情報量との和を用いることで、画素対応最適化手段は、最終的に符号化画像出力手段が符号化する情報の情報量が最小となるように、両フレーム内の画素間の対応付けを最適化する。その結果、符号化画像出力手段による画像の圧縮率を最大化することができる。
【００７８】
本発明の画像符号化装置の第７の構成は、前記第１乃至５の何れか一の構成において、前記符号化画像情報量評価値は、前記予測残差の情報量であることを特徴とする。
【００７９】
このように、符号化画像情報量評価値として、画素の対応づけに関する情報の情報量を省略して、予測残差の情報量のみを用いることも可能である。一般に、３次元画像では被写体画像のフレーム間相関が大きいため、画素の対応づけに関する情報の情報量は、予測残差の情報量に比べて小さくなると考えられるからである。従って、予測残差の情報量のみを最小化するように、両フレーム内の画素間の対応付けを最適化すれば、符号化画像出力手段による画像の圧縮率を近似的に最大化することができる。また、このように符号化画像情報量評価値を簡単化することにより画素対応最適化手段による最適化処理時間を短縮し、画像符号化処理の高速化を図ることができる。
【００８０】
本発明の画像符号化装置の第８の構成は、前記第１乃至５の何れか一の構成において、前記符号化画像情報量評価値は、前記第ｔフレーム内の各画素と、前記第ｔフレーム内の各画素に対応する前記第ｔ−１フレーム内の画素との画素間相違尺度の総和であることを特徴とする。
【００８１】
このように、符号化画像情報量評価値として、画素間相違尺度の総和を用いることで、符号化画像情報量評価値の計算が簡単化され、画像符号化処理の高速化を図ることができる。また、画素間相違尺度の総和を最小化することで、結果的に、予測残差の情報量を最小化することができる。
【００８２】
ここで、「画素間相違尺度」とは、上述のように、画素間の相違の尺度量のことをいい、予測残差や２乗差、画素ベクトル間の距離等が用いられる。
【００８３】
本発明の画像符号化方法の第１の構成は、複数枚のフレームから構成される３次元画像について、符号化処理を行うべき第ｔフレームに隣接する第ｔ−１フレーム内の画素の画素値を参照して前記第ｔフレーム内の各画素の画素値を予測することにより前記第ｔフレームの予測符号化を行う画像符号化方法において、少なくとも拘束条件
０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
のもとで、符号化画像情報量評価値が最小となるように、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけを行い、それにより対応づけられる、前記第ｔフレーム内の画素と前記第ｔ−１フレーム内の画素との差である予測残差を前記第ｔフレーム内の各画素について求め、前記画素の対応づけに関する情報と、前記予測残差の情報とを符号化することを特徴とする。
【００８４】
本発明の画像符号化方法の第２の構成は、前記第１の構成において、前記両フレーム内の画素間の対応づけを行う際に、前記第ｔフレーム内の画素に対応づけられる前記第ｔ−１フレーム内の画素の位置について、更に少なくとも以下の拘束条件
｜ｌ（ｉ，ｊ）−ｌ（ｉ，ｊ−１）｜≦ε２
｜ｍ（ｉ，ｊ）−ｍ（ｉ−１，ｊ）｜≦ε２’
を課すことを特徴とする。
【００８５】
本発明の画像符号化方法の第３の構成は、前記第１又は２の構成において、前記両フレーム内の画素間の対応づけを行う場合において、まず、動的計画法により、前記第ｔフレーム内の行ｉ又は列ｊ上の各画素を、前記第ｔ−１フレーム内の行ｉ又は列ｊ上の画素に対応づけることにより、行又は列を固定した条件のもとで最適化された対応付関数ｍ（ｊ）又はｌ（ｉ）を求め、次に、前記対応付関数ｍ（ｊ）又はｌ（ｉ）を固定した条件のもとで、動的計画法により、前記第ｔフレーム内の列ｊ又は行ｉ上の各画素を、前記第ｔ−１フレーム内の列ｍ（ｊ）又は行ｌ（ｉ）上の画素と、対応づけを行うことを特徴とする。
【００８６】
本発明の画像符号化方法の第４の構成は、前記第１又は２の構成において、前記両フレーム内の画素間の対応付けは、２次元的に動的計画法を適用することにより行うことを特徴とする。
【００８７】
本発明の画像符号化方法の第５の構成は、前記第１乃至４の何れか一の構成において、前記両フレーム内の画素間の対応づけを行う際に、前記第ｔフレーム内の各画素と前記第ｔ−１フレーム内の画素との対応づけに関する情報を、前記両フレーム内の画素間の対応づけによる画素の位置変化の差分情報として求めることを特徴とする。
【００８８】
本発明の画像符号化方法の第６の構成は、前記第１乃至５の何れか一の構成において、前記符号化画像情報量評価値は、前記予測残差の情報量と、前記画素の対応づけに関する情報の情報量との和であることを特徴とする。
【００８９】
本発明の画像符号化方法の第７の構成は、前記第１乃至５の何れか一の構成において、前記符号化画像情報量評価値は、前記予測残差の情報量であることを特徴とする。
【００９０】
本発明の画像符号化方法の第８の構成は、前記第１乃至５の何れか一の構成において、前記符号化画像情報量評価値は、前記第ｔフレーム内の各画素と、前記第ｔフレーム内の各画素に対応する前記第ｔ−１フレーム内の画素との画素間相違尺度の総和であることを特徴とする。
【００９１】
本発明のプログラムは、コンピュータで実行することにより、請求項１乃至８の何れか一に記載の画像処理装置が実現されることを特徴とする。
【００９２】
【発明の実施の形態】
以下、本発明の一実施形態について、図面を参照しながら説明する。
【００９３】
図４は本発明の実施の形態に係る画像符号化装置のブロック図である。
図４において、本実施の形態に係る画像符号化装置１は、フレームメモリ２，３、ＤＰマッチング処理部４，９、バックポインタテーブル５，１０、バックトラック処理部６，１１、対応付関数テーブル７、差分対応付関数テーブル８，１３、予測残差テーブル１２、符号化部１５、及び送信バッファ１６を有している。また、本実施の形態においては、被処理画像は、被処理画像記憶部１７に記憶されているものとする。
【００９４】
フレームメモリ２は、被処理画像記憶部１７に記憶されている３次元の被処理画像を、１フレームづつ読み出して記憶する。また、フレームメモリ３は、フレームメモリ２に読み込まれたフレームを、所定の処理が終了した後にそのまま読み込んで記憶する。
【００９５】
ＤＰマッチング処理部４は、フレームメモリ２に記憶された第ｔフレーム内の画像の各行ｉについて、行ｉ上の各画素を、フレームメモリ３に記憶された第ｔ−１フレーム内の行ｉ上の画素に対応づけることにより、行を固定した条件のもとでのＤＰマッチング処理を行い、バックポインタテーブル５にバックポインタｐ（ｊ，ｍ｜ｉ）を出力する。
【００９６】
バックトラック処理部６は、バックポインタテーブル５に記憶されたバックポインタｐ（ｊ，ｍ｜ｉ）と、フレームメモリ２，３に記憶された第ｔフレーム及び第ｔ−１フレームとに基づいて、対応付関数ｍ（ｊ）及び差分対応付関数δｍ（ｊ）を計算すると共に、対応付関数ｍ（ｊ）を対応付関数テーブル７に出力し、差分対応付関数δｍ（ｊ）を差分対応付関数テーブル８に出力する。
【００９７】
ＤＰマッチング処理部９は、対応付関数テーブル７内の対応付関数ｍ（ｊ）を参照しながら、フレームメモリ２に記憶された第ｔフレーム内の画像の各列ｊについて、列ｊ上の各画素を、フレームメモリ３に記憶された第ｔ−１フレーム内の列ｍ（ｊ）上の画素に対応づけることにより、対応付関数ｍ（ｊ）を固定した条件のもとで、第ｔフレーム内の画像の各列ｊ上の画素及び第ｔ−１フレーム内の画像の各列ｍ（ｊ）上の画素に対してＤＰマッチング処理を行い、バックポインタテーブル１０にバックポインタｐ（ｉ，ｌ｜ｊ，ｍ）を出力する。
【００９８】
バックトラック処理部１１は、バックポインタテーブル１０に記憶されたバックポインタｐ（ｉ，ｌ｜ｊ，ｍ）と、フレームメモリ２，３に記憶された第ｔフレーム及び第ｔ−１フレームとに基づいて、差分対応付関数δｌ（ｉ）及び予測残差δａｉ，ｊを計算すると共に、差分対応付関数δｌ（ｉ）を差分対応付関数テーブル１３に出力し、予測残差δａｉ，ｊを予測残差テーブル１２に出力する。
【００９９】
符号化部１５は、予測残差δａｉ，ｊ及び差分対応付関数δｌ（ｉ），δｍ（ｊ）をハフマン符号化して、符号化された第ｔフレームＧを送信バッファ１６に出力する。送信バッファ１６は、符号化部１５から符号化された第ｔフレームＧが入力された後に、当該符号化された第ｔフレームＧを送信する。
【０１００】
本実施の形態においては、フレームメモリ２，３、ＤＰマッチング処理部４，９、バックポインタテーブル５，１０、バックトラック処理部６，１１、対応付関数テーブル７、差分対応付関数テーブル８，１３、及び予測残差テーブル１２により、画素対応最適化手段及び予測残差計算手段が実現されている。また、符号化部１５により符号化画像出力手段が実現されている。
【０１０１】
以上のように構成された本実施形態に係る画像符号化装置１において、以下その画像符号化方法について説明する。
【０１０２】
図５は本発明の実施の形態に係る画像符号化方法の全体の流れを表すフローチャート、図６は行方向の動き探索処理を表すフローチャート、図７は列方向の動き探索処理を表すフローチャート、図８は２次元動き補償符号化処理を表すフローチャートである。
【０１０３】
本実施の形態においては、第ｌフレームの画像の予測符号化を行う場合、まず、行方向の動き探索をＤＰマッチング処理により行い（Ｓ１）、次に、列方向の動き探索をＤＰマッチング処理により行う（Ｓ２）。そして、第ｌフレームと、既に符号化が終わっている第ｌ−１フレームとの対応づけの情報に基づき、両フレーム内の対応する画素間の予測残差を求めることにより、２次元動き補償符号化を行う（Ｓ３）。そして、符号化された画像は、送信バッファ１６より送信される。
【０１０４】
ステップＳ１における行方向の動き探索は、図６のフローチャートに沿って行われる。
【０１０５】
最初に、行を指定するポインタｉが１にリセットされる（Ｓ１０）。このポインタｉに設定された行について、以下の処理において、行固定条件においての両フレーム内の画素間の対応付け（行方向の動き探索）が動的計画法により行われる。
【０１０６】
そしてまず、ＤＰマッチング処理部４は、ポインタｉにより指定される行について、ＤＰマッチング処理が実行する（Ｓ１１）。すなわち、上記（数２９）で示したアルゴリズムによって、境界条件（１９）式、（２０）式、及び１次元的な単調連続性条件（２１）式の条件の下で、第ｔフレームのｉ行目の各画素に対して、第ｌ−１行目の画素を対応づけるためのバックポインタ（２４）式を求める。そして、算出したバックポインタ｛ｐ（ｊ，ｍ｜ｉ）；ｊ＝１，２，…，Ｎ｝を、バックポインタテーブル５に格納する。
【０１０７】
次に、ｉ行，Ｎ列目の画素までの処理が終わった時点で、バックトラック処理部６は、バックポインタテーブル５に格納されたバックポインタ｛ｐ（ｊ，ｍ｜ｉ）｝を参照して、（数３２）に示したバックトラック処理により、行ｉを固定した条件のもとでの最適化された対応付関数｛ｍ（ｊ｜ｉ）；ｊ＝１，２，…，Ｎ｝及び差分対応付関数｛δｍ（ｊ｜ｉ）；ｊ＝１，２，…，Ｎ｝を決定する（Ｓ１３）。この対応付関数｛ｍ（ｊ｜ｉ）；ｊ＝１，２，…，Ｎ｝は、対応付関数テーブル７に格納され、差分対応付関数｛δｍ（ｊ｜ｉ）；ｊ＝１，２，…，Ｎ｝は、差分対応付関数テーブル８に格納される。
【０１０８】
最後に、ポインタｉをインクリメントして、処理行を次の行に設定した後に、ｉがＮ以下であれば（Ｓ１５）、Ｓ１１〜Ｓ１５の処理を繰り返す。ステップＳ１５において、ｉがＮを超えた場合、総ての行について行固定条件においての両フレーム内の画素間の対応付け（行方向の動き探索）の処理を終了する。
【０１０９】
これらの処理によって、行固定条件における対応付関数｛ｍ（ｊ）＝ｍ（ｊ｜ｉ）；ｉ，ｊ＝１，２，…，Ｎ｝の最適化が、第ｔフレームの総ての行について終了したことになる。また、差分対応付関数｛δｍ（ｊ）＝δｍ（ｊ｜ｉ）；ｉ，ｊ＝１，２，…，Ｎ｝が、第ｔフレームの総ての行について終了したことになる。
【０１１０】
ステップＳ２における列方向の動き探索は、図７のフローチャートに沿って行われる。
【０１１１】
最初に、列を指定するポインタｊが１にリセットされる（Ｓ２０）。このポインタｊに設定された第ｔフレーム内の列ｊと、それに対応する第ｔ−１フレーム内の列ｍｉ（ｊ）について、以下の処理において、列固定条件においての両フレーム内の画素間の対応付け（列方向の動き探索）が動的計画法により行われる。
【０１１２】
そしてまず、ＤＰマッチング処理部９は、対応付関数テーブル７に格納された対応付関数｛ｍｉ（ｊ）；ｉ＝１，２，…，Ｎ｝を参照して、第ｔフレーム内の列ｊ及び第ｔ−１フレーム内の列ｍｉ（ｊ）について、ＤＰマッチング処理を実行する（Ｓ２１）。すなわち、上記（３０）式〜（３２）式によって、境界条件（２７）式、（２８）式、及び１次元的な単調連続性条件（２９）式の制限下で、第ｔフレームのｊ列目の各画素に対して、第ｌ−１行目のｍｉ（ｊ）列内の画素を対応づけるためのバックポインタ（３２）式を求める。そして、算出したバックポインタ｛ｐ（ｉ，ｌ；ｊ，ｍ）；ｉ＝１，２，…，Ｎ｝を、バックポインタテーブル１０に格納する。
【０１１３】
次に、第ｔフレームのｊ列，Ｎ行目の画素までの処理が終わった時点で、バックトラック処理部１１は、バックポインタテーブル１０に格納されたバックポインタ｛ｐ（ｉ，ｌ｜ｊ，ｍ）；ｉ＝１，２，…，Ｎ｝を参照して、（数４０）に示したバックトラック処理により、列ｊ及び対応付関数ｍ（ｊ）を固定した条件のもとでの最適化された差分対応付関数｛δｌ（ｉ｜ｊ，ｍ）；ｉ＝１，２，…，Ｎ｝及び予測残差｛δａｉ，ｊ＝ａｉ，ｊ−ｂｌ（ｉ），ｍ（ｊ）；ｉ＝１，２，…，Ｎ｝を決定する（Ｓ２２）。この差分対応付関数｛δｌ（ｉ｜ｊ，ｍ）；ｉ＝１，２，…，Ｎ｝は、差分対応付関数テーブル８に格納され、予測残差｛δａｉ，ｊ；ｉ＝１，２，…，Ｎ｝は、予測残差テーブル１２に格納される。
【０１１４】
最後に、ポインタｊをインクリメントして、処理列を次の列に設定した後に、ｊがＮ以下であれば（Ｓ２４）、Ｓ２１〜Ｓ２３の処理を繰り返す。ステップＳ２４において、ｊがＮを超えた場合、総ての列について列固定条件においての両フレーム内の画素間の対応付け（列方向の動き探索）の処理を終了する。
【０１１５】
これらの処理によって、列固定条件における差分対応付関数｛δｌ（ｉ）＝δｌ（ｉ｜ｊ）；ｉ，ｊ＝１，２，…，Ｎ｝が、第ｔフレームの総ての行について終了したことになる。また、予測残差｛ａｉ，ｊ＝ａｉ，ｊ−ｂｌ（ｉ），ｍ（ｊ）；ｉ＝１，２，…，Ｎ｝の最適化が、第ｔフレームの総ての行について終了したことになる。
【０１１６】
ステップＳ３における２次元動き補償符号化処理は、図８のフローチャートに沿って行われる。
【０１１７】
まず、符号化部１５は、第ｔフレーム内の処理行の行番号を表すポインタｉを１に設定し（Ｓ３０）、第ｔフレーム内の処理列の列番号を表すポインタｊを１に設定する（Ｓ３１）。次に、符号化部１５は、差分対応付関数テーブル８，１３から差分対応付関数｛δｍ（ｊ）；ｉ，ｊ＝１，２，…，Ｎ｝，｛δｌ（ｉ）；ｉ，ｊ＝１，２，…，Ｎ｝を読み出し、予測残差テーブルδａ（ｉ）から予測残差｛δａ（ｉ，ｊ）；ｉ，ｊ＝１，２，…，Ｎ｝を読み出す。そして、これらをハフマン符号によるエントロピー符号化によって符号化する。符号化された｛δｍ（ｊ）｝，｛δｌ（ｉ）｝及び｛δａ｝は、送信バッファ１６に格納され、送信バッファ１６よりデータ送信される。
【０１１８】
尚、本実施の形態において、対応付関数ｌ（ｉ，ｊ），ｍ（ｉ，ｊ）を送信せずに、動き差分関数ｑ（ｉ，ｊ）＝（δｌ（ｉ，ｊ），δｍ（ｉ，ｊ））を送信することとしたのは、次のような理由による。
（イ）（数３２），（数４０）から分かるように、ｌ（ｉ）＝ｌ（ｉ−１）＋δｌ（ｉ），ｍ（ｊ）＝ｍ（ｊ−１）＋δｍ（ｊ）であり、対応付関数ｌ（ｉ），ｍ（ｊ）は、その動き差分関数から復元することができる。
（ロ）動き差分関数は、もともと（２４）式、（３２）式のバックポインタｐであり、その値は｛０，１，２｝の３値であるため、送信に当たって符号化効率がよい。
【０１１９】
次に、受信側の画像復号装置について説明する。
【０１２０】
図９は本発明の実施に形態に係る画像復号装置のブロック図である。
図９において、本実施の形態に係る画像復号装置２０は、受信バッファ２１、復号部２２、予測復号部２３、及びフレームメモリ２４，２５を具備する。
【０１２１】
受信バッファ２１は、上記画像符号化装置１より送信されてくるデータを受信して格納する。復号部２２は、受信バッファ２１に格納された受信データを復号し、予測残差｛δａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝、及び対応付関数｛δｍ（ｊ）；ｉ，ｊ＝１，２，…，Ｎ｝，｛δｌ（ｉ）；ｉ，ｊ＝１，２，…，Ｎ｝を復元する。予測復号部２３は、上記予測残差｛δａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝及び対応付関数｛δｍ（ｊ）；ｉ，ｊ＝１，２，…，Ｎ｝，｛δｌ（ｉ）；ｉ，ｊ＝１，２，…，Ｎ｝、並びに、フレームメモリ２５に格納された第ｔ−１フレームの画素｛ｂｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝から、第ｔフレームの画素｛ａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝を復元し、フレームメモリ２４に出力する。フレームメモリ２４は、予測復号部２３から出力される復元された第ｔフレームの画素｛ａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝を総て格納した時点で、当該第ｔフレームの画素｛ａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝を被処理画像記憶手段２６に出力するとともに、当該第ｔフレームの画素｛ａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝をフレームメモリ２６にコピーする。
【０１２２】
以上のように構成された本実施の形態に係る画像復号化装置において、以下その画像復号化方法について説明する。
【０１２３】
図１０は本発明の実施の形態に係る画像復号化方法のフローチャートである。図１０は、第ｔフレームの画像｛ａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝を復元する処理を表したものであり、第ｔ−１フレームの画像｛ｂｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝については、既に復元されてフレームメモリ２５に格納されているものとする。
【０１２４】
最も単純な復号方法は、まず最初に対応付関数（ｌ（ｉ，ｊ），ｍ（ｉ，ｊ））を第ｔフレーム全体について完全に復元した後に、第ｔフレームの各画素値を順次復号する方式である。
【０１２５】
この場合、まず最初に、画像符号化装置２０は、画像符号化装置１から送信された符号化された予測残差及び対応付関数を受信し、受信バッファ２１に格納する（Ｓ４０）。復号部２２は、受信バッファ２１内の符号化された予測残差及び対応付関数を復号し、予測残差｛δａｉ，ｊ；ｉ，ｊ＝１，２，…，Ｎ｝及び対応付関数｛δｍ（ｊ）；ｉ，ｊ＝１，２，…，Ｎ｝，｛δｌ（ｉ）；ｉ，ｊ＝１，２，…，Ｎ｝を復元する（Ｓ４１）。
【０１２６】
次に、予測復号部２３は、これから復号処理を行う行及び列を表すポインタｉ，ｊを１に設定する（Ｓ４２，Ｓ４３）。
【０１２７】
次に、対応付関数ｍ（ｉ，ｊ）をｍ（ｉ，ｊ）＝ｍ（ｉ，ｊ−１）＋δｍ（ｉ，ｊ）により求め（Ｓ４４）、対応付関数ｌ（ｉ，ｊ）をｌ（ｉ，ｊ）＝ｌ（ｉ−１，ｊ）＋δｌ（ｉ，ｊ）により求める（Ｓ４５）。
【０１２８】
そして、ｊの値をインクリメントして（Ｓ４６）、ｊ≦Ｎの間は（Ｓ４７）、ステップＳ４４〜Ｓ４７を繰り返す。ステップＳ４７において、ｊ＞Ｎとなった場合には、第ｉ行の対応付関数ｌ（ｉ，ｊ）、ｍ（ｉ，ｊ）の復号が終わったので、次にｉをインクリメントして（Ｓ４８）、ｉ≦Ｎの間は（Ｓ４９）、ステップＳ４３〜Ｓ４９を繰り返す。ステップＳ４９において、ｉ＞Ｎとなった場合には、第ｔフレームの対応付関数ｌ（ｉ，ｊ）、ｍ（ｉ，ｊ）の復号が終了したので、次の画素値ａ（ｉ，ｊ）の復号ステップに移る。
【０１２９】
画素値ａ（ｉ，ｊ）の復号ステップでは、まず、これから復号処理を行う行及び列を表すポインタｉ，ｊを１に設定する（Ｓ５０，Ｓ５１）。
【０１３０】
次に、フレームメモリ２５より、第ｔ−１フレームの画素ｂｌ（ｉ，ｊ），ｍ（ｌ（ｉ，ｊ），ｊ）を読み出して、ａｉ，ｊ＝ｂｌ（ｉ，ｊ），ｍ（ｌ（ｉ，ｊ），ｊ）＋δａｉ，ｊにより、第ｔフレームの画素ａｉ，ｊを復元し（Ｓ５２）、復元した画素ａｉ，ｊは、フレームメモリ２４に格納する。
【０１３１】
そして、ポインタｊの値を、インクリメントし（Ｓ５３）、更新されたポインタｊの値がＮ以下であれば（Ｓ５４）、再び、ステップＳ５２〜Ｓ５４までの処理を繰り返す。ステップＳ５４において、ポインタｊの値がＮを超えた場合には、第ｉ行目の処理を終了する。そして、ポインタｉの値をインクリメントする（Ｓ５５）。
【０１３２】
更新されたポインタｉの値がＮ以下であれば（Ｓ５６）、再び、ステップＳ５１〜Ｓ５６までの処理を繰り返す。ステップＳ５６において、ポインタｉの値がＮを超えた場合には、第ｔフレームの復号処理を終了する。
【０１３３】
以上の処理が終了した時点で、フレームメモリ２４には、第ｔフレームの復元画像が総て格納される。そして、フレームメモリ２４は、この復元された第ｔフレームの画像を被処理画像記憶手段２６に格納すると共に、第ｔフレームの画像をフレームメモリ２５にコピーする。このようにして、順次、３次元画像のフレームが復元されていく。
【０１３４】
尚、復号処理に関しては、他の高速化手法を採用することも可能である。図１１は、高速化した復号処理の流れを表すフローチャートである。
【０１３５】
この場合、ステップＳ６０，Ｓ６１は、図１０のステップＳ４０，Ｓ４１と同様なので省略する。
【０１３６】
次に、予測復号部２３は、これから復号処理を行う列を表すポインタｊを１に設定する（Ｓ６２）。そして、これから復号処理を行う行を表すポインタｉを１に設定する（Ｓ６３）。
【０１３７】
そして、ｉの値を１からＮまでインクリメントつつ、ｍ（ｉ，ｊ）＝ｍ（ｉ，ｊ−１）＋δｍ（ｉ，ｊ）により、第ｊ列の対応付関数｛ｍ（ｉ，ｊ）；ｊ＝１，２，…，Ｎ｝を先に復号する（ＳＳ６４〜Ｓ６６）。
【０１３８】
次に、再び、ポインタｉを１に設定した後、ｉの値を１からＮまでインクリメントつつ、ｌ（ｉ，ｊ）＝ｌ（ｉ，ｊ−１）＋δｌ（ｉ，ｊ）により、第ｊ列の対応付関数｛ｌ（ｉ，ｊ）；ｊ＝１，２，…，Ｎ｝を復号するとともに、フレームメモリ２５より、第ｔ−１フレームの画素ｂｌ（ｉ，ｊ），ｍ（ｌ（ｉ，ｊ），ｍ（ｌ（ｉ，ｊ），ｊ））を読み出して、ａｉ，ｊ＝ｂｌ（ｉ，ｊ），ｍ（ｌ（ｉ，ｊ），ｍ（ｌ（ｉ，ｊ），ｊ））＋δａｉ，ｊにより、第ｔフレームの画素ａｉ，ｊを復号し、フレームメモリ２４に格納する（Ｓ６８〜Ｓ７１）。
【０１３９】
そして、ｊの値をインクリメントして（Ｓ７２）、第Ｎ列までステップＳ６３〜Ｓ７３の動作を繰り返す（Ｓ７３）。ステップＳ７３において、ポインタｊの値がＮを超えた場合には、第ｔフレームの復号処理を終了する。
【０１４０】
このアルゴリズムによれば、列の復号処理についてのループを１回のみ回せばよいので、図１０のアルゴリズムよりも復号処理が高速となる。
【０１４１】
尚、上記実施の形態においては、画像符号化装置及び画像復号装置をハードウェア的に実現する例について説明したが、画像符号化装置及び画像復号装置をコンピュータにより構成し、両実施の形態の画像処理装置及び画像複合装置を実現するためのプログラムをコンピュータに読み込ませて実行させることにより、画像符号化装置及び画像復号装置として動作させるようにしてもよい。
【０１４２】
【発明の効果】
以上のように、本発明によれば、第ｔフレーム内の各画素と、第ｔ−１フレーム内の画素との２次元的な画素同士の対応付けを行い、画素単位の対応付けに基づく予測符号化を行うことにより、フレーム間でフレーム内の被写体画像が変形や回転等の非線形変化を伴う場合においても、柔軟な対応付が可能となる。従って、予測残差を小さくすることができ、その結果、フレーム画像の圧縮率を向上させることが可能となる。
【０１４３】
また、第ｔフレーム内の各画素と、第ｔ−１フレーム内の画素との対応付けにあたって、１次元的な単調連続性条件
０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
を課すことで、対応付情報の情報量と予測残差情報の情報量とをバランスよく低減させ、フレーム画像の圧縮率を更に向上させることができる。
【０１４４】
更に、第ｔフレーム内の各画素と、第ｔ−１フレーム内の画素との対応付けにあたって、２次元的な単調連続性条件
０≦ｌ（ｉ，ｊ）−ｌ（ｉ−１，ｊ）≦ε１
０≦ｍ（ｉ，ｊ）−ｍ（ｉ，ｊ−１）≦ε１’
｜ｌ（ｉ，ｊ）−ｌ（ｉ，ｊ−１）｜≦ε２
｜ｍ（ｉ，ｊ）−ｍ（ｉ−１，ｊ）｜≦ε２’
を課すことにより、１次元的な単調連続性条件を課した場合よりも、フレーム画像の圧縮率を更に向上させることができる。
【０１４５】
そして、この対応付において、動的計画法の手法を用いることによって、少ない計算回数で最適な対応付を行うことができる。従って、画像符号化の高速化を図ることが可能となり、動画像通信のようなリアルタイムの画像転送に適用することも可能となる。
【０１４６】
実際に、本発明の実施の形態に係る画像符号化方法による計算量を、（６）式に準じて見積もると、そのオーダーは、１回の行方向の計算量がＷ×Ｎ（Ｗ＝２ｒ＋１）のオーダーであることから、そのＮ行分、かつ列方向まで総合すると、２×Ｗ×Ｎ２となる。すなわち、動き探索範囲Ｗに関して、従来は２乗のオーダーであったものが、本発明によって線形オーダーまで低減される。
【図面の簡単な説明】
【図１】ＤＰマッチングを説明する図である。
【図２】ｊの進行に伴うｍの変化の制限を説明する図である。
【図３】行方向の動き探索と列方向の動き探索との関係を示す図である。
【図４】本発明の実施の形態に係る画像符号化装置のブロック図である。
【図５】本発明の実施の形態に係る画像符号化方法の全体の流れを表すフローチャートである。
【図６】行方向の動き探索処理を表すフローチャートである。
【図７】列方向の動き探索処理を表すフローチャートである。
【図８】２次元動き補償符号化処理を表すフローチャートである。
【図９】本発明の実施に形態に係る画像復号装置のブロック図である。
【図１０】本発明の実施の形態に係る画像復号化方法のフローチャートである。
【図１１】高速化した復号処理の流れを表すフローチャートである。
【図１２】フレーム間予測符号化方式の原理を説明するためのブロック図である。
【図１３】動き補償を含むフレーム間予測符号化の原理を説明する図である。
【図１４】被写体自体が変形を伴う場合の一例を示す図である。
【符号の説明】
１  画像符号化装置
２，３  フレームメモリ
４，９  ＤＰマッチング処理部
５，１０  バックポインタテーブル
６，１１  バックトラック処理部
７  対応付関数テーブル
８，１３  差分対応付関数テーブル
１２  予測残差テーブル
１５  符号化部
１６  送信バッファ
２０  画像復号装置
２１  受信バッファ
２２  復号部
２３  予測復号部
２４，２５  フレームメモリ
２６  被処理画像記憶手段
【図１】
2004208253.tif 000043
【図２】
2004208253.tif 000044
【図３】
2004208253.tif 000045
【図４】
2004208253.tif 000046
【図５】
2004208253.tif 000047
【図６】
2004208253.tif 000048
【図７】
2004208253.tif 000049
【図８】
2004208253.tif 000050
【図９】
2004208253.tif 000051
【図１０】
2004208253.tif 000052
【図１１】
2004208253.tif 000053
【図１２】
2004208253.tif 000054
【図１３】
2004208253.tif 000055
【図１４】
2004208253.tif 000056