(57)【要約】【課題】画像の空間的形状に柔軟に追随することが可能であり、予測精度が高く情報圧縮効率の高い画像符号化技術を提供する。【解決手段】被処理画像を複数のラインに分割し、各ラインのうち隣接する２つのラインのうち、一方のライン上の画素の画素値を、他方のライン上の画素の画素値を参照して予測することにより予測符号化を行う画像符号化装置１において、一方のライン上の各画素と、それに対応する他方のライン上の画素の画素間相違尺度の総和が最小となるように、一方のライン上の各画素を他方のライン上の画素に対応づけ、対応づけられた両ライン上の画素の画素値の差である予測残差を求め、画素の対応付け情報、予測残差情報を符号化画像として出力する。【選択図】          図５
2004208252.tif 000002
【特許請求の範囲】
【請求項１】
被処理画像を複数のラインに分割し、前記各ラインのうち隣接する２つのラインのうち、一方のライン上の画素の画素値を、他方のライン上の画素の画素値から予測することにより前記被処理画像の予測符号化を行う画像符号化装置において、
前記一方のライン上の各画素と、前記一方のライン上の各画素に対応する前記他方のライン上の画素との画素間相違尺度の総和が最小となるように、前記一方のライン上の各画素と前記他方のライン上の画素との対応づけを行う画素対応最適化手段と、
前記画素対応最適化手段により対応づけられる、前記一方のライン上の画素と前記他方のライン上の画素との画素値の差である予測残差を、前記一方のライン上の各画素について求める予測残差計算手段と、
前記画素対応最適化手段による画素の対応付けに関する情報と、前記予測残差の情報とを符号化画像として出力する符号化画像出力手段と、
を備えていることを特徴とする画像符号化装置。
【請求項２】
前記画素対応最適化手段は、前記画素間の対応づけを行う際に、前記一方のライン上の各画素に対して対応づけられる前記他方のライン上の画素の位置について、単調連続性の条件を課すこと
を特徴とする請求項１記載の画像符号化装置。
【請求項３】
前記画素対応最適化手段は、動的計画法により前記画素間の対応づけを行うこと
を特徴とする請求項１又は２記載の画像符号化装置。
【請求項４】
前記符号化画像出力手段は、前記画素対応最適化手段が求めた前記両ライン上の画素間の対応づけに関する情報を、前記両ライン上の画素間の対応付けによる画素の位置変化の差分情報として出力することを特徴とする請求項１乃至３の何れか一に記載の画像符号化装置。
【請求項５】
前記被処理画像内の隣接する２つのラインは、２次元の前記被処理画像内における空間的に隣接した２つのラインであることを特徴とする請求項１乃至４の何れか一に記載の画像符号化装置。
【請求項６】
前記被処理画像内の隣接する２つのラインは、３次元の前記被処理画像内における時間的に隣接したラインであることを特徴とする請求項１乃至４の何れか一に記載の画像符号化装置。
【請求項７】
被処理画像を複数のラインに分割し、前記各ラインのうち隣接する２つのラインのうち、一方のライン上の画素の画素値を、他方のライン上の画素の画素値を参照して予測することにより前記被処理画像の予測符号化を行う画像符号化方法において、
前記一方のライン上の各画素と、前記一方のライン上の各画素に対応する前記他方のライン上の画素の画素間相違尺度の総和が最小となるように、前記一方のライン上の各画素を前記他方のライン上の画素に対応づけ、
それにより対応づけられる、前記一方のライン上の画素と前記他方のライン上の画素との画素値の差である予測残差を求め、
前記画素の対応付けに関する情報と、前記予測残差の情報とを符号化画像として出力すること
を特徴とする画像符号化方法。
【請求項８】
前記一方のライン上の画素と前記他方のライン上の画素との対応づけを行う場合において、
前記一方のライン上の各画素に対して対応づけられる前記他方のライン上の画素の位置については、単調連続性の条件を課すこと
を特徴とする請求項７記載の画像符号化方法。
【請求項９】
前記一方のライン上の画素と前記他方のライン上の画素との対応づけを動的計画法により行うこと
を特徴とする請求項７又は８記載の画像符号化方法。
【請求項１０】
前記符号化画像は、
前記予測残差の情報と、
前記両ライン上の画素間の対応付けによる画素の位置変化の差分情報と、
を含むこと
を特徴とする請求項７乃至９の何れか一に記載の画像符号化方法。
【請求項１１】
前記被処理画像内の隣接する２つのラインは、２次元の前記被処理画像内における空間的に隣接した２つのラインであることを特徴とする請求項７乃至１０の何れか一に記載の画像符号化方法。
【請求項１２】
前記被処理画像内の隣接する２つのラインは、３次元の前記被処理画像内における時間的に隣接したラインであることを特徴とする請求項７乃至１０の何れか一に記載の画像符号化方法。
【請求項１３】
コンピュータで実行することにより、請求項１乃至６の何れか一に記載の画像符号化装置が実現されることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は静止画像や動画像の圧縮符号化を行う画像符号化技術に関し、特に、簡単な処理で、高効率な圧縮を可能とする符号化技術に関する。
【０００２】
【従来の技術】
従来より、画像通信等の分野においては、画像伝送等の際に画像を高効率に圧縮するための一手段として、予測符号化技術が知られている（例えば、非特許文献１）。
【０００３】
以下、一例として、画像通信における画像の送信という目的を想定して説明する。
【０００４】
画像の予測符号化は、画像中の画素値が、その近傍の画素値との間に強い相関を有することを利用して行われる。静止画を対象とする場合には、各画素の空間的近傍の画素値を参照して各画素の予測を行い、予測した画素値と現実の画素値との差分である予測残差を送信データとする。動画像の場合にはあるフレームの各画素に対して時間的空間的近傍関係にある画素値を用いる（非特許文献１参照）。
【０００５】
図１６に最も簡単な圧縮法である予測符号化方式の原理を示す。
図１６においては、ラスター走査を想定しており、上半が送信側で、送信すべき信号値（画素値）が２ライン分示されている。下半が受信側で、再生された信号値（画素値）が２ライン分示されている。現第ｌライン上の画素値をａｉで、前第ｌ−１ライン上の画素値をｂｉで示す。受信側でも同様の表示を用いる。
【０００６】
送信側で第ｌラインの画素値ａｉが符号化される様子は以下のとおりである。現第ｌライン上の画素値ａｉを、第ｌ−１ラインでａｉと同一位置にある参照画素値ｂｉにより近似予測する。これと実際の画素値ａｉとの差
【数１】
2004208252.tif 000003
を予測残差情報として送信する。もとの画素値ａｉに比して、予測残差（以下、「単純予測残差」という。）δａｉ’の信号としてのダイナミックレンジは、画像全体での平均的意味で、相当小さくなり、結果として送信情報量の低減効果が得られる。
【０００７】
受信側での復号は以下のように行われる。いま、ラスター走査順に従って第ｌ−１ラインまでの復号が終了しているとする。このとき画素値ａｉは、第ｌ−１ラインでａｉと同一位置にある参照画素ｂｉと、受信された単純予測残差δａｉ’とにより、
【数２】
2004208252.tif 000004
と復元される。（１）式を代入するとにより  ａｉ（受信側）＝ａｉ（送信側）となることが容易に確認される。
【０００８】
【非特許文献１】
黒田英夫，「ディジタル信号処理シリーズ（第１５巻）画像符号化技術」，初版，株式会社昭光堂，１９９６年１２月，ｐ．４６−５７
【非特許文献２】
迫江，「音声認識における動的計画法の応用」，ｂｉｔ，共立出版，１９８３年７月，第１５巻，第８号，ｐ．１３５−１４２
【非特許文献３】
迫江，藤井，吉田，亘理，「フレーム同期化，ビームサーチ，ベクトル量子化の統合によるＤＰマッチングの高速化」，電子情報通信学会論文誌Ｄ，電子情報通信学会，１９８８年９月，第Ｊ７１巻，第９号，ｐ．１６５０−１６５９
【０００９】
【発明が解決しようとする課題】
上記従来の予測符号化方式は、基本的に、画像をラスター走査線間の画素値の変化パターンとしてとらえ、隣接画素値を参照して予測残差を抽出・送信することにより圧縮を行っている。しかし、画像には輝度や色といった性質の他に、形状に関する情報が含まれている。端的な例を挙げると、ラインの進行に伴って、ライン上の１次元パターンが変化していくというとらえ方である。
【００１０】
図１７（ａ），（ｂ）はこのことを説明するための図である。
図１７（ａ）の数字は画像の画素輝度値を示している。図１７（ｂ）には図１７（ａ）に破線を施した２ライン分を拡大表示している。これに、第ｌ−１ラインに比して第ｌラインは空間的に少し左寄りに歪んだ関係にあることが見て取れる。（１）式をそのまま適用して予測残差を計算する従来方式では第ｌ−１ライン上のｉ番目の画素の画素値ｂｉ（＝２）を参照して、第ｌライン上のｉ番目の画素の画素値ａｉ（＝４）を予測するとδａｉ’＝２が発生する。上記の空間的な歪みを考えて、第ｌ−１ライン上のｉ番目の画素の代わりに、第ｌ−１ラインの少し右よりのｉ＋２番目の画素の値ｂｊ（＝４）を参照するとδａｉ’＝０と予測残差は発生しない。このように、従来方式では、予測される画素に対する参照画素の位置関係が固定されていてライン間の空間的形状変化に追従できない点が、圧縮効果の限界を与える欠点となっていた。
【００１１】
そこで、本発明の解決すべき課題は、画像の空間的形状に柔軟に追随することが可能であり、予測精度が高く情報圧縮効率の高い画像符号化技術を提供することにある。
【００１２】
【課題を解決するための手段】
以下、上述の課題を解決するための手段について説明するが、まず最初に、動的計画法の一利用形態であるＤＰマッチング法による２ライン上の画素間の対応付けの手法について説明し、次に、本発明の構成及び作用について説明する。
【００１３】
〔１〕ＤＰマッチング法による２ライン上の画素間の対応付けの手法
【００１４】
まず最初に、以下の説明で用いる記号法について整理しておく。
符号化処理の対象となる被処理画像は、行列形式で、
【数３】
2004208252.tif 000005
と表現する。ここで、ａｌ，ｉは第ｌ行，第ｉ列の画素値を示す。また、第ｌラインと第ｌ−１ラインとの関係を論じるときには、第ｌ−１ラインを、
【数４】
2004208252.tif 000006
と略式表記し、第ｌラインを、
【数５】
2004208252.tif 000007
と略式表記する。この表記は、送信側でも受信側でも共通である。伝送エラーのない可逆符号化・復号の場合を想定して記法の簡単化を図ったものである。
【００１５】
図１は本発明の原理を説明するための図である。
図１においては、第ｌラインと第ｌ−１ラインとが示されている。この２ライン間には、「従来の技術」の項目で述べたように、ラインの進行（ｌ−１→ｌ）に伴う形状への追従による１次元パターンとしての変化が含まれている。これを、時系列パターンａとｂとの間の非線形伸縮変化とみなして、第ｌ−１ライン上の画素位置ｊを、歪み関数ｊ（ｉ）により近似する。
【数６】
2004208252.tif 000008
ここで、歪み関数ｊ（ｉ）は、第ｌライン上の画素位置ｉと第ｌ−１ライン上の画素位置ｊとを対応づける関数である。
【００１６】
また、第ｌラインと第ｌ−１ラインとの間の予測残差Ｄ（ｌ，ｌ−１）を
【数７】
2004208252.tif 000009
により定義する。ここで、‖ａｉ−ｂｊ（ｉ）‖は、画素ａｉと画素ｂｊ（ｉ）との間の相違の尺度量であり、例えば、モノクロ画像の場合には、画素の絶対値差｜ａｉ−ｂｊ（ｉ）｜や２乗差（ａｉ−ｂｊ（ｉ））２、カラー画像の場合には、画素ベクトル間の距離やそれに準じる尺度等が用いられる。
【００１７】
そして、予測残差Ｄ（ｌ，ｌ−１）が最小となるように歪み関数ｊ（ｉ）を定める。そうすれば、歪み関数ｊ＝ｊ（ｉ）によって画素ａｉに対応づけられた画素ｂｊの画素値は、画素ａｉの画素値に近い値をとり、画素ｂｊを参照画素とした予測残差の絶対値｜ａｉ−ｂｊ｜の値は平均的に圧縮される。すなわち、ラインｌ上の位置ｉの画素ａｉで対応する画素ｂｉを参照していた従来方式と比べて、伝送すべき情報量の低減を図ることができる。
【００１８】
次に、予測残差Ｄ（ｌ，ｌ−１）を最小化するための歪み関数ｊ（ｉ）の決定方法について説明する。
【００１９】
まず、画素間相違尺度ｄ（ｉ，ｊ）を
【数８】
2004208252.tif 000010
により定義する。
【００２０】
次に、画素間のトポロジーは保存されると考えられることから、歪み関数ｊ（ｉ）に対して、境界条件
【数９】
2004208252.tif 000011
【数１０】
2004208252.tif 000012
及び、単調連続性条件
【数１１】
2004208252.tif 000013
を課する。尚、ここでは、計算量を少なくするために、一例として、ｐの範囲は０，１，２としているが、一般的な単調連続性条件ではｐ∈｛０，１，…，ｎ｝（ｎはＮに対して十分小さい自然数）と表される。
単調連続性条件の意味に関して、更に具体的に図２を用いて説明する。
図２（ａ）は、単調連続性条件を満たす画素間の対応づけの例を示し、図２（ｂ）は、単調連続性条件を満たさない画素間の対応づけの例を示す。単調連続性条件を満たす場合には、第ｌラインの各画素に対応づけられる第ｌ−１ラインの画素の間隔は、伸縮し又は０となることはあるが、常にｊ（ｉ）≧ｊ（ｉ−１）の条件を満たす。すなわち、両ライン上の画素の対応づけを表す矢印が交差することはない。それに対して、単調連続性条件を満たさない場合には、必ずしもｊ（ｉ）≧ｊ（ｉ−１）の条件が成立しない。すなわち、両ライン上の画素の対応づけを表す矢印が交差する場合が生じる。
【００２１】
以上のような拘束条件のもとで、動的計画法の一利用形態であるＤＰマッチング法を適用して歪み関数ｊ（ｉ）の決定をする。尚、ＤＰマッチング法については、主に音声認識の分野において用いられており、例えば、非特許文献２等の文献に記載されている。
【００２２】
具体的に歪み関数ｊ（ｉ）の決定を行うには、初期条件を、
【数１２】
2004208252.tif 000014
として、ｉ＝１，２，…，Ｍ；ｉ−ｒ≦ｊ≦ｉ＋ｒの領域において、漸化式
【数１３】
2004208252.tif 000015
を計算すると同時に、その最適パラメータを
【数１４】
2004208252.tif 000016
として配列ｐ（ｉ，ｊ）に保存する。ここで、演算子
【数１５】
2004208252.tif 000017
は、ｘｐの値が最小であるｐを選択することを意味する演算子である。また、ｐ（ｉ，ｊ）は、最小化におけるパラメータｐの最適値を保存する配列であり、バックポインタと呼ばれる。また、ｒはｉとｊの対応のズレを規制するためのパラメータである。
【００２３】
以上に説明した方法は、次のようなアルゴリズムにより簡潔に表される。
【数１６】
2004208252.tif 000018
【００２４】
図３はＤＰマッチングを説明する図である。
図３においては、横軸をラインｌ上の座標ｉ、縦軸をラインｌ−１上の座標ｊにとった（ｉ，ｊ）平面を表している。この平面上の点（ｉ，ｊ）では、ａｉとｂｊとの間の画素間相違度ｄ（ｉ，ｊ）が計算される。そして、経路ｊ＝ｊ（ｉ）上のｄ（ｉ，ｊ）の総和が最小となるように歪み関数ｊ（ｉ）を最適化する。
【００２５】
ここで、（８）式の境界条件ｊ（１）＝１は、初期条件（１１）式により実現されている。また、（９）式の境界条件ｊ（Ｍ）＝Ｍは、（１２）式及び（１３）式の計算点を点（ｉ，ｊ）＝（Ｍ，Ｍ）で終了することにより実現されている。また、単調連続性条件（１０）式は、（１２）式及び（１３）式の最小化の付帯条件（ｐ＝０，１，２）として実現されている。この単調連続性条件（１０）式の制約により、ｉの進行に伴うｊの変化は、図４のように制限される。
【００２６】
（１２）式及び（１３）式の計算点が点（ｉ，ｊ）＝（Ｍ，Ｍ）まで終了した時点で、（６）式の最小値は、
【数１７】
2004208252.tif 000019
と定まる。更に、以下のようなバックトラック処理で、歪み関数｛ｊ（ｉ）；ｉ＝１，２，…，Ｍ｝と、これらの差分である差分歪み関数｛δｊ（ｉ）＝ｊ（ｉ＋１）−ｊ（ｉ）；ｉ＝１，２，…，Ｍ−１｝が降順に定まる。
【数１８】
2004208252.tif 000020
【００２７】
なお、このバックトラック処理において、同時に予測残差｛δａｉ＝ａｉ−ｂｊ（ｉ）；ｉ＝１，２，…，Ｍ｝も計算される。すなわち、バックトラック処理は以下のようなアルゴリズムとして簡潔に表される。
【数１９】
2004208252.tif 000021
ここで、上記（数１９）のアルゴリズムにおいて、ｊ（ｉ）の値を保存していないのは、ｊ（ｉ）かδｊ（ｉ）かの何れか一方が分かれば、他方を復元することができるため、δｊ（ｉ）の値のみを保存すれば十分だからである。
【００２８】
尚、ここでは一例として、画像通信における画像の送信という目的を想定して説明したが、本発明の適用範囲は、画像記録を目的とする場合等も包含する。また、送信画像が完全な形に復号される可逆符号化の範囲で説明したが、本発明の予測符号化処理により生成される信号に何らかの他の可逆圧縮処理を追加するもの、さらには非可逆圧縮処理を追加して構成される非可逆圧縮系において利用される形態であってもよい。
【００２９】
また、上記ＤＰマッチングにおいては、（１２）式，（１３）式は｛（ｉ，ｊ）；ｉ＝１，２，…，Ｍ，ｉ−ｒ≦ｊ≦ｉ＋ｒ｝の総ての点について計算することとしたが、高速化が要求されるような場合においては、ＤＰマッチングにビームサーチ法やベスト・ファースト・サーチ法等を適用し、一部の（ｉ，ｊ）について（１２）式，（１３）式を計算するようにしてもよい。尚、ビームサーチ法の適用によるＤＰマッチングの高速化の方法については、音声認識の分野において行われた例が知られており（非特許文献３参照）、既に公知事項であるため、ここでは説明は省略する。
【００３０】
〔２〕本発明の構成及び作用
【００３１】
本発明に係る画像符号化装置の第１の構成は、被処理画像を複数のラインに分割し、前記各ラインのうち隣接する２つのラインのうち、一方のライン上の画素の画素値を、他方のライン上の画素の画素値から予測することにより前記被処理画像の予測符号化を行う画像符号化装置において、前記一方のライン上の各画素と、前記一方のライン上の各画素に対応する前記他方のライン上の画素の画素間相違尺度の総和が最小となるように、前記一方のライン上の各画素と前記他方のライン上の画素との対応づけを行う画素対応最適化手段と、前記画素対応最適化手段により対応づけられる、前記一方のライン上の画素と前記他方のライン上の画素との画素値の差である予測残差を求める予測残差計算手段と、前記画素対応最適化手段による画素の対応付けに関する情報と、前記予測残差の情報とを符号化画像として出力する符号化画像出力手段と、を備えていることを特徴とする。
【００３２】
このように、隣接するライン間で画素単位の対応を予測残差の総和が最小となるように最適に定めることにより、画像の空間的形状に柔軟に追随して画素間の対応がつけられ、一般的な画像においては、上記従来よりも予測精度が高く情報圧縮効率を向上させることが可能となる。また、ライン上の画素対ライン上の画素の対応付けであるため、１次元の対応付処理ですむために計算量が少なく、高速化が可能である。
【００３３】
また、一方のライン上の画素に対応づける画素を他の“ライン”上の画素に制約することにより、対応付情報についての符号量の低減が図られる。すなわち、予測符号化後に圧縮された画像の符号量は、予測誤差の符号量と対応付情報の符号量の和で決まる。従って、実際の圧縮率は、予測誤差のエントロピーと対応付情報のエントロピーのバランスを最適化することが必要である。本発明では、一方のライン上の各画素に対して他の“ライン”上の画素の対応付け（すなわち、０次元（一方のライン上の画素）対１次元（他方のライン上の何れかの画素）の対応付け）とすることで、少なくとも対応付情報のエントロピーは抑えられる。そして、対応付けをする他のラインを、同一画像内の隣接ライン又は隣接フレーム内の同一座標のライン等の「隣接するライン」にとれば、通常の画像の場合は予測誤差のエントロピーも小さくなる。従って、予測誤差と対応付情報とのエントロピーのバランスは最適値に近くなる。すなわち、圧縮された画像の符号量が減少する。
【００３４】
ここで、画素対応最適化手段による画素間の対応付けの方法としては、動的計画法や整数計画法等を使用することが可能である。
【００３５】
本発明に係る画像符号化装置の第２の構成は、上記第１の構成において、前記画素対応最適化手段は、前記画素間の対応づけを行う際に、前記一方のライン上の各画素に対して対応づけられる前記他方のライン上の画素の位置について、単調連続性の条件を課すことを特徴とする。
【００３６】
このように、単調性の条件を課すことにより、画素間のトポロジーが保存される。十分に解像度の高い画像情報において、画素間のトポロジー保存の制約条件は妥当なものである。単調性は、ライン上で隣接する２画素が対応するライン上の画素の順番に対して入れ替わることがない条件であり、トポロジー保存のための必要条件である。従って、単調性を課すことによって予測残差を大きくすることなく、２ライン上の画素間の対応づけの範囲を縮小することが可能となる。これにより、画素の対応付けに関する情報量が減少するため、符号化効率がさらに向上する。
【００３７】
また、連続性の条件を課すことによって、画素の対応付けに関する情報量の上限が決まる。すなわち、連続性の条件により、一方のライン上の各画素に対応づけられる他方のライン上の画素の移動範囲が極端に大きくなることはなく、移動範囲は決められた範囲内となるため、移動量を表すための符号長が決まる。従って、これをエントロピー符号化した場合、画素の対応付けに関する情報量の上限は定まることになる。従って、被写体のエッジ部分のように画像の性質によって画素間対応が付けにくい場合であっても、符号化効率が低減することが防止される。
【００３８】
尚、「単調連続性の条件」とは、上述のとおり、一方のライン上の各画素に対応づけられる他方のライン上の画素の順番が、それに対応する一方のライン上の画素の順番に対して入れ替わることがなく（単調性）、且つ、対応する２画素の座標が互いに近傍にある（連続性）とする条件をいい、一般的には下式により表される。
【数２０】
2004208252.tif 000022
ここで、ｎは任意の自然数を表し、計算速度の点から、通常は、２又は３程度の値とされる。
【００３９】
本発明に係る画像符号化装置の第３の構成は、上記第１又は２の構成において、前記画素対応最適化手段は、動的計画法により前記画素間の対応づけを行うことを特徴とする。
【００４０】
動的計画法により、隣接する２ライン上の画素間の対応づけを効率よく行うことができる。従って、画素間の対応づけの計算処理を高速で行うことができる。
【００４１】
本発明に係る画像符号化装置の第４の構成は、上記第１乃至３の何れか一の構成において、前記符号化画像出力手段は、前記画素対応最適化手段が求めた前記両ライン上の画素間の対応づけに関する情報を、前記両ライン上の画素間の対応付けによる画素の位置変化の差分情報として出力することを特徴とする。
【００４２】
このように、符号化画像に含まれる、対応づけによる各画素の位置変化の情報を、上記画素の位置変化の差分情報により構成することで、各画素の位置変化の情報を効率よく圧縮することができる。
【００４３】
特に、上記連続単調性の条件を課した場合には、画素の位置変化の差分情報のダイナミックレンジは所定の範囲に決定される。そのため、各画素の位置変化の情報の圧縮効率が向上する。
【００４４】
本発明に係る画像符号化装置の第５の構成は、上記第１乃至４の何れか一の構成において、前記被処理画像内の隣接する２つのラインは、２次元の前記被処理画像内における空間的に隣接した２つのラインであることを特徴とする。
【００４５】
これにより、２次元の被処理画像を高い圧縮効率で符号化することができる。
【００４６】
本発明に係る画像符号化装置の第６の構成は、上記第１乃至４の何れか一の構成において、前記被処理画像内の隣接する２つのラインは、３次元の前記被処理画像内における時間的に隣接したラインであることを特徴とする。
【００４７】
これにより、３次元の被処理画像を高い圧縮効率で符号化することができる。
【００４８】
本発明に係る画像符号化方法の第１の構成は、被処理画像を複数のラインに分割し、前記各ラインのうち隣接する２つのラインのうち、一方のライン上の画素の画素値を、他方のライン上の画素の画素値を参照して予測することにより前記被処理画像の予測符号化を行う画像符号化方法において、前記一方のライン上の各画素と、前記一方のライン上の各画素に対応する前記他方のライン上の画素の画素間相違尺度の総和が最小となるように、前記一方のライン上の各画素を前記他方のライン上の画素に対応づけ、それにより対応づけられる、前記一方のライン上の画素と前記他方のライン上の画素との画素値の差である予測残差を求め、前記画素の対応付けに関する情報と、前記予測残差の情報とを符号化画像として出力することを特徴とする。
【００４９】
本発明に係る画像符号化方法の第２の構成は、上記第１の構成において、前記一方のライン上の画素と前記他方のライン上の画素との対応づけを行う場合において、前記一方のライン上の各画素に対して対応づけられる前記他方のライン上の画素の位置については、単調連続性の条件を課すことを特徴とする。
【００５０】
本発明に係る画像符号化方法の第３の構成は、上記第１又は２の構成において、前記一方のライン上の画素と前記他方のライン上の画素との対応づけを動的計画法により行うことを特徴とする。
【００５１】
本発明に係る画像符号化方法の第４の構成は、上記第１乃至３の何れか一の構成において、前記符号化画像は、前記予測残差の情報と、前記両ライン上の画素間の対応付けによる画素の位置変化の差分情報と、
を含むことを特徴とする。
【００５２】
本発明に係る画像符号化方法の第５の構成は、上記第１乃至４の何れか一の構成において、前記被処理画像内の隣接する２つのラインは、２次元の前記被処理画像内における空間的に隣接した２つのラインであることを特徴とする。
【００５３】
本発明に係る画像符号化方法の第６の構成は、上記第１乃至４の何れか一の構成において、前記被処理画像内の隣接する２つのラインは、３次元の前記被処理画像内における時間的に隣接したラインであることを特徴とする。
【００５４】
本発明に係るプログラムは、コンピュータで実行することにより、請求項１乃至６の何れか一に記載の画像符号化装置が実現されることを特徴とする。
【００５５】
【発明の実施の形態】
以下、本発明に係る一実施の形態について、図面を参照しながら説明する。
【００５６】
（実施の形態１）
図５は本発明の実施の形態１に係る画像符号化装置のブロック図である。
図５において、本実施の形態に係る画像符号化装置１は、ラインバッファ２，３、ＤＰマッチング処理部４、バックポインタテーブル５、バックトラック処理部６、差分歪み関数テーブル７、最適予測残差テーブル８、単純予測残差計算部９、単純予測残差テーブル１０、符号化部１１、比較出力部１３、及び送信バッファ１４，１５を有している。また、本実施の形態においては、被処理画像は、被処理画像記憶手段２０に記憶されている。
【００５７】
ラインバッファ２は、被処理画像を記憶する被処理画像記憶手段２０に記憶された被処理画像を、１ライン分ずつ読み出し記憶する（以下、ラインバッファ２に記憶された１ライン分の被処理画像を「ラインａ」という。）。また、ラインバッファ３は、ラインバッファ２に読み込まれたラインａを、所定の処理が終了した後にそのまま読み込んで記憶する（以下、ラインバッファ３に記憶された１ライン分の被処理画像を「ラインｂ」という。）。
【００５８】
ＤＰマッチング処理部４は、ラインバッファ２，３に記憶されたラインａ，ｂの各画素間の対応づけを、ＤＰマッチング法により行い、バックポインタテーブル５にバックポインタｐ（ｉ，ｊ）を出力する。
【００５９】
バックトラック処理部６は、バックポインタテーブル５に記憶されたバックポインタｐ（ｉ，ｊ）と、ラインバッファ２，３に記憶されたラインａ，ｂとに基づいて、予測残差δａ（ｉ）及び差分歪み関数δｊ（ｉ）を計算するとともに、予測残差δａ（ｉ）を最適予測残差テーブル８に出力し、差分歪み関数δｊ（ｉ）を差分歪み関数テーブル７に出力する。
【００６０】
単純予測残差計算部９は、ラインバッファ２，３に記憶されたラインａ，ｂより、（１）式に基づいて単純予測残差δａ’を計算し、単純予測残差テーブル１０に出力する。
【００６１】
符号化部１１は、符号表を参照して、予測残差δａ及び差分歪み関数δｊ（ｉ）をハフマン符号化して符号化画像Ｇを送信バッファ１４に出力するとともに、単純予測残差δａ’をハフマン符号化して符号化画像Ｇ’を送信バッファ１５に出力する。
【００６２】
比較出力部１３は、符号化画像Ｇ，Ｇ’の符号量を比較し、何れか符号量の小さい方を送信用の符号化画像として出力する。
【００６３】
以上のように構成された本実施の形態に係る画像符号化装置１において、以下、それによる画像符号化方法について説明する。
【００６４】
図６は本発明の実施の形態１に係る画像符号化方法を表すフローチャートである。
【００６５】
まず、ラインバッファ２は、被処理画像記憶手段２０より、１ライン分の被処理画像を読み込んで保持する（Ｓ１）。
【００６６】
そして、まず第１ラインの符号化処理を行う（Ｓ２）。
【００６７】
なお、第１ラインの符号化においては、実在しない第０ラインを参照することになる。従って、第１ラインの符号化処理では、第０ラインの画素値は総て０であるとして、ラインバッファ３のデータを０でクリアして、後述のステップＳ７，Ｓ８及びＳ１１の処理を行う。これらの処理が終了した時点で、ラインバッファ３には、第１ラインの各画素の画素値が格納された状態となっている。
【００６８】
次に、ラインバッファ３は、ラインバッファ２に記憶されたラインａを読み込んで、ラインｂとして保持する（Ｓ３）。そして、ラインバッファ２は、被処理画像記憶手段２０より、次のライン（ｌ行目のライン）を読み込んで、ラインａとして保持する（Ｓ４）。
【００６９】
次いで、ＤＰマッチング処理部４は、上述の（数１６）に示したアルゴリズムより、ラインバッファ２に記憶されたラインａの各画素について、ラインバッファ３に記憶されたラインｂの画素への対応づけを行う（Ｓ５）。そして、ＤＰマッチング処理部４は、（１３）式で表されるバックポインタｐ（ｉ，ｊ）をバックポインタテーブル５に出力する。
【００７０】
図７はＤＰマッチング処理を表すフローチャートである。
【００７１】
ＤＰマッチング処理において、ＤＰマッチング処理部４は、まず、最初の画素同士の画素間相違度ｄ（１，１）を（７）式により計算し、評価パラメータであるｇ（１，１）に代入し、次に処理を行う画素の位置を表すポインタｉを２に設定する（Ｓ２０）。
【００７２】
次に、対応づけを行う前のラインの画素の位置を表すポインタｊをｉ−ｒに設定する（Ｓ２１）。ここで、ポインタｊは区間［１，Ｍ］内になければならないので、ｊ＜０の場合には（Ｓ２２）、ｊ＝１に設定する（Ｓ２３）。また、ｊ＞Ｍの場合には（Ｓ２４）、ｉ番目の画素についての処理を終了し、後述のステップＳ３０に移行する。
【００７３】
次に、（７）式より画素間相違度ｄ（ｉ，ｊ）を計算する。尚、ｒはポインタｉとポインタｊとの対応のズレを規制するためのパラメータであり、一定の値（例えば２）に設定されているものとする。そして、評価パラメータｇ（ｉ，ｊ）、バックポインタｐ（ｉ，ｊ）を（１２）式及び（１３）式により計算し（Ｓ２３）、バックポインタｐ（ｉ，ｊ）をバックポインタテーブル５に保存する（Ｓ２４）。
【００７４】
そして、ｊ＜ｉ＋ｒかつｊ＜Ｍの場合には（Ｓ２８）、ポインタｊをインクリメントして（Ｓ２９）、上記ステップＳ２５〜Ｓ２８のｉ番目の画素についてのＤＰマッチング処理を繰り返す。
【００７５】
ステップＳ２８において、ｊ＝ｉ＋ｒ又はｊ＝Ｍの場合には、ｉ番目の画素についてのバックポインタ計算処理を終了する。そして、ｉ＜Ｍの場合には（Ｓ３０）、ポインタｉをインクリメントした後に（Ｓ３１）、再び上記ステップＳ２１〜Ｓ２９の動作を繰り返す。ステップＳ３０において、ｉ＝Ｍの場合には、現ライン上の総ての画素についてのＤＰマッチング処理が終了したので、ＤＰマッチング処理を終了する。このＤＰマッチング処理が終了した時点で、バックポインタ｛ｐ（ｉ，ｊ）｝が総て求まり、ａとｂとの最適な画素間の対応づけを確定することが可能な状態となる。
【００７６】
以上のＤＰマッチング処理が終わると、次に、バックトラック処理部６は、バックポインタテーブル５に記憶されたバックポインタｐ（ｉ，ｊ）を参照して、（数１９）に示すアルゴリズムに従ってバックトラック処理を行う（図６のＳ６）。
【００７７】
図８はバックトラック処理を表すフローチャートである。
【００７８】
バックトラック処理において、バックトラック処理部６は、まず、初期値として、ポインタｉ，ｊの値をｉ＝Ｍ，ｊ＝Ｍに設定する（Ｓ４０）。
【００７９】
次に、δａｉ＝ａｉ−ｂｊにより予測残差δａｉを計算し、最適予測残差テーブル８に保存する（Ｓ４２）。
【００８０】
次に、δｊ（ｉ−１）＝ｐ（ｉ，ｊ）とし（Ｓ４３）、δｊ（ｉ−１）を差分歪み関数テーブル７に保存する（Ｓ４４）。
【００８１】
次に、ｊ−δｊ（ｉ−１）の値を計算して歪み関数ｊ（ｉ−１）の値を求め、その値をポインタｊに代入する。すなわち、ポインタｊは、ｉ−１番目の画素の対応づけを行うための歪み関数ｊ（ｉ−１）の値に更新される。また、ｉの値をデクリメントする（Ｓ４５）。すなわち、ポインタｉは、ライン上を右から左に向かって走査される。
【００８２】
そして、ｉ＞１ならば（Ｓ４６）、ステップＳ４１〜Ｓ４６を繰り返す。一方、ステップＳ４６で、ｉ＝１である場合、δａ１＝ａ１−ｂ１として（Ｓ４７）、δａ１を最適予測残差テーブル８に保存してから（Ｓ４８）、バックトラック処理を終了する。このバックトラック処理により、第ｌ行目のライン上の画素と第ｌ−１行目のライン上の画素との対応づけが決まり、その対応づけに関する情報である差分歪み関数｛δｊ（ｉ）；ｉ＝１，２，…，Ｍ−１｝が差分歪み関数テーブル７に格納される。また、同時に、その対応づけによる予測残差｛δａｉ；ｉ＝１，２，…，Ｍ｝が最適予測残差テーブル８に格納されることになる。
【００８３】
一方、上記ＤＰマッチング処理及びバックトラック処理と並行して、単純予測残差計算部９は、（１）式に基づき単純予測残差を計算し、単純予測残差テーブル１０に出力する（図６のＳ７）。
【００８４】
以上のような最適予測残差計算（Ｓ５，Ｓ６）及び単純予測残差計算（Ｓ７）の終了後、符号化部１１による符号化処理が行われる（Ｓ８）。
【００８５】
図９は符号化処理を表すフローチャートである。
符号化処理において、符号化部１１は、まず、差分歪み関数テーブル７に保存された差分歪み関数δｊ（ｉ）のうち、その値ｐが、それぞれ０，１，２であるものの個数ｎ（ｐ）を計数する（Ｓ５０）。次に、個数｛ｎ（ｐ）；ｐ＝０，１，２｝のうちで最大のものに対応するｐの値によって、（表１）に示すように、適応的な符号表を選択する（Ｓ５１）。
【表１】
2004208252.tif 000023
【００８６】
すなわち、個数の最も多かったものに長さ１の符号０を、そのほかに長さ２の符号１０又は１１を対応させるように、符号表を選択する。尚、（表１）の符号表は一例であり、これ以外の符号表を使用することもできるが、差分歪み関数の符号化に使用する符号表は、瞬時符号となっていることを要する。また、このようにラインごとに符号表を切り替えているのは、各ラインの差分歪み関数について、最適なハフマン符号化を行うためである。
【００８７】
そして、この符号化を、差分歪み関数テーブル７に記憶された差分歪み関数｛δｊ（ｉ）；ｉ＝１，２，…，Ｍ−１｝の総てについて行い、符号化された差分歪み関数｛Δｊ（ｉ）；ｉ＝１，２，…，Ｍ−１｝を生成し、送信バッファ１４に記憶させる（Ｓ５２〜Ｓ５５）。
【００８８】
次に、符号化部１１は、送信バッファ１４にフラグｆを与える（Ｓ５６）。送信バッファ１４には、２ビットのフラグｆを記憶する領域が用意されている。この領域には、（表１）のどの符号表が使用されたかにより、２進数で（００）２，（０１）２，（１０）２の値が記憶される。このフラグｆを参照することによって、受信側では、復号に使用すべき符号表を知ることができる。尚、送信バッファ１５にもフラグｆを記憶する領域が用意されているが、この領域には、２進数（１１）２が固定的に記憶されている。
【００８９】
続いて、符号化部１１は、予測残差情報の符号化を行った後に（Ｓ５７）、符号化処理を終了する。
【００９０】
図１０は予測残差情報の符号化処理を表すフローチャートである。
【００９１】
予測残差情報の符号化処理では、符号化部１１は、ポインタｉ，ｊを１に初期化して、各ライン（第ｌ行，第ｌ−１行目のライン）の左端に合わせる（Ｓ７０）。
【００９２】
次に、符号化部１１は、最適予測残差テーブル８に記憶された予測残差δａ（ｉ）をハフマン符号化し、予測残差情報Δａとして送信バッファ１４に保存する（Ｓ７１）。また、符号化部１１は、単純予測残差テーブル１０に記憶された予測残差δａ（ｉ）’をハフマン符号化し、予測残差情報Δａ’として送信バッファ１５に保存する（Ｓ７２）。そして、ポインタｊの値をｊ＋δｊ（ｉ）の値に更新するとともに（Ｓ７３）、ポインタｉの値をインクリメントする（Ｓ７４）。
【００９３】
このとき、ｉ≦Ｍの場合には（Ｓ７５）、再びステップＳ７１〜Ｓ７５の動作を繰り返す。そして、ステップＳ７５において、ｉ＞Ｍとなった場合に、予測残差情報の符号化処理を終了する。
【００９４】
以上のような予測残差情報の符号化処理が終了すると、比較出力部１３は、送信バッファ１４に格納されたデータの符号量Ｃ１と、送信バッファ１５に格納されたデータの符号量Ｃ２とを比較する（Ｓ９）。その結果、前者が小さいときには、比較出力部１３は、送信バッファ１４内のデータを送信し（Ｓ１０）、そうでない場合は送信バッファ１５内のデータを送信する（Ｓ１１）。
【００９５】
このように、送信バッファを２個用いて、一方にはライン間対応を伴う予測残差情報Δａと差分歪み情報｛Δｊ（ｉ）｝を、他方には、画素位置を固定した対応に伴う単純予測残差情報Δａ’を用意し、何れか符号量の少ない方を送信することとしたのは、次のような理由による。
【００９６】
一般には、予測残差Δａの符号量は、単純予測残差情報Δａ’の符号量に比べ大幅に削減される。
【００９７】
しかし、特別な場合として、現ライン（第ｌ行目のライン）の画素値配列と、前ライン（第ｌ−１行目のライン）の画素値配列とが極めて類似している場合、ライン間の画素対応ｊ（ｉ）を最適化しても、予測残差Δａと単純予測残差情報Δａ’とが殆ど変わらないことがある。このような場合、差分歪み情報｛Δｊ（ｉ）｝を含めて送信すると、かえって送信情報量の増加を招くことになる。
【００９８】
そこで、このような特別な場合には、単に固定の画素対応に基づいた単純予測残差Δａ’を送信することとして、送信符号量の増加を抑制することとしたものである。
【００９９】
以上の一連の処理が終了した後、被処理画像の総ての行について符号化が終了していない場合には（Ｓ１２）、ステップＳ３の処理に戻る。被処理画像の総ての行について符号化が終了した場合には（Ｓ１２）、画像符号化装置１は画像符号化処理を終了する。
【０１００】
尚、本実施の形態において、各ラインの符号化処理は、１行づつ順次行う構成としたが、処理の高速化が要求される場合には、複数のラインの符号化処理を、上記と同様の方法で並列に行うようにすることもできる。ｎ本のラインの符号化処理を並列で行うことにより、処理速度は理論上ｎ倍とすることが可能である。
【０１０１】
次に、受信側の画像復号装置について説明する。
【０１０２】
図１１は本発明の実施の形態１に係る画像複号化装置のブロック図である。
図１１において、本実施の形態の画像複号化装置２０は、受信バッファ２１、復号部２２、最適予測残差テーブル２３、差分歪み関数テーブル２４、単純予測残差テーブル２５、最適予測復号部２６、単純予測復号部２７、及び２つのラインバッファ２８，２９を具備する。
【０１０３】
受信バッファ２１は、上記画像符号化装置１より送信されてくるデータを受信して格納する。復号部２２は、受信バッファ２１に格納された受信データの先頭の２ビットからなるフラグｆを参照して、受信データの符号化方法を判別するとともに、判別された符号化方法に従って、ハフマン符号化された上記受信データを復号し、最適予測複号化部２６に予測残差δａｉ及び差分歪み関数δｊ（ｉ）を出力し、又は単純予測複号化部２７に単純予測残差δａｉ’を出力する。最適予測復号部２６は、上記予測残差δａ（ｉ）と差分歪み関数δｊ（ｉ）、及びラインバッファ２９に格納されている複号化された被処理画像の第ｌ−１行目のラインｂのデータとに基づいて、被処理画像の第ｌ番目のラインａのデータを復元して、ラインバッファａに出力する。ラインバッファ２８は、第ｌ行目の総ての画素が復元された時点で、格納されたデータを被処理画像記憶手段３０及びラインバッファ２９に出力する。
【０１０４】
以上のように構成された本実施の形態に係る画像複号化装置において、以下その画像複号化方法について説明する。
【０１０５】
図１２は実施の形態１に係る画像複号化方法を示すフローチャートである。
【０１０６】
画像複号化装置２０は、まず、画像符号化装置１から送信される最初の１ライン分のデータを受信すると、受信バッファ２１に格納する（Ｓ１００）。このとき、初期状態では、ラインバッファ２９内のデータは０クリアされている。そして、復号部２２は受信バッファ２１内のデータを復号し、第１ラインの画素値列を復元する（Ｓ１０１）。単純予測復号部２７は、復号部２２の復号結果に、ラインバッファ２９内のデータを加えてラインバッファ２８に出力する（Ｓ１０２）。すなわち、この時点で、ラインバッファ２８には第１ラインの画素値列が順次格納される。ラインバッファａに第１ラインの画素値列が総て格納された時点で、ラインバッファ２８は、そのデータは被処理画像記憶手段３０にも出力するとともに、ラインバッファ２９にデータを移す。従って、この時点で、ラインバッファ２８には第１ラインの画素値列が格納された状態となる。
【０１０７】
次に、画像複号化装置２０は、画像符号化装置１から送信される次の１ライン分のデータを受信し、受信バッファ２１に格納する（Ｓ１０３）。
【０１０８】
復号部２２は、受信バッファ２１に格納されたデータの先頭２ビットのフラグｆを参照し、フラグｆが（１１）２であるか否かを調べる（Ｓ１０４）。フラグｆが（１１）２である場合は、後述のステップＳ１１３〜Ｓ１１６の単純予測復号処理を行う。尚、このとき、受信バッファ内には、フラグｆに続いて、差分歪み情報｛Δｊ（ｉ）｝と予測残差情報｛Δａｉ｝とが格納されている。
【０１０９】
一方、ステップＳ１０４においてｆ≠（１１）２の場合、最適予測復号部２６は、以下のような画素間の対応づけを考慮した予測復号処理を行う。
フラグｆの値が（００）２，（０１）２，（１０）２の何れであるかによって、（表１）に従って符号表を選択する（Ｓ１０５）。次いで、ポインタｉ，ｊを１に初期化して、ラインの左端に合わせる（Ｓ１０６）。
【０１１０】
次に、受信バッファ２１より予測残差情報Δａｉを読み出して、復号し、予測残差δａｉを求める（Ｓ１０７）。そして、ラインバッファ２９より前のライン上の画素値ｂｊを読み出して、これに予測残差δａｉを加えて、現ライン上の画素値ａｉを求め、ラインバッファ２８に出力する（Ｓ１０８）。
【０１１１】
図１３は送信側のライン間の画素対応と受信側の処理との関係を示す図である。
現ライン（第ｌライン）上の位置ｉにある画素の画素値ａｉは、既に復元済みの前のライン（第ｌ−１ライン）の位置ｊにある画素の画素値ｂｊと予測残差δａｉを加えることにより復元される。ここで、ポインタｊには歪み関数ｊ（ｉ）の値が設定されている。
【０１１２】
次に、受信バッファ２１より、差分歪み情報Δｊ（ｉ）を読み出して、先に選択した符号表に従って復号し、差分歪み関数δｊ（ｉ）を求める（Ｓ１０９）。そして、ポインタｊの値に差分歪み関数δｊ（ｉ）を加えた値を、新たなポインタｊの値とする（Ｓ１１０）。これによって、歪み関数ｊ（ｉ＋１）が復元されて、ポインタｊが更新される。一方、ポインタｉの値については、インクリメントする（Ｓ１１１）。これによって、現ライン上の予測複号化処理を行う画素位置ｉが、ラインの右端から左端に向かって走査される。
【０１１３】
そして、ポインタｉの値が１ラインの画素数Ｍ以下の場合には（Ｓ１１２）、上記ステップＳ１０７〜Ｓ１１２の動作を繰り返し、ポインタｉの値がＭを超えた時点で（Ｓ１１２）、画素間の対応づけを考慮した予測復号処理を終了して、後述のステップＳ１１７の動作に移る。
【０１１４】
一方、ステップＳ１０４において、フラグｆが（１１）２である場合、単純予測復号部２７は、以下のような単純予測復号処理を行う。尚、このとき、受信バッファ内には、フラグｆに続いて、単純予測残差情報｛Δａｉ’｝が格納されている。
【０１１５】
まず、ポインタｉの値を１に初期化して、ラインの左端に合わせる（Ｓ１１３）。そして、受信バッファ２１から単純予測残差情報Δａｉ’を読み出して、複号し、単純予測残差δａｉ’を求める。次いで、ラインバッファ２９から前のライン上の画素値ｂｉを読み出して、これに単純予測残差δａｉ’を加えて、現ライン上の画素値ａｉを求め、ラインバッファ２８に出力する（Ｓ１１５）。そして、ポインタｉの値が１ラインの画素数Ｍ以下の場合には（Ｓ１１６）、上記ステップＳ１１４〜Ｓ１１６の動作を繰り返し、ポインタｉの値がＭを超えた時点で（Ｓ１１６）、単純予測復号処理を終了し、次のステップＳ１１７の動作に移る。
【０１１６】
以上の処理により、現ライン上の総ての画素の画素値｛ａｉ｝が復号された時点で、ラインバッファ２８に格納された１ライン分の画素値｛ａｉ｝をラインバッファ２９にコピーする（Ｓ１１７）。また、ラインバッファ２８に格納された１ライン分の画素値｛ａｉ｝を被処理画像記憶手段３０に格納する。
【０１１７】
画像複号化装置２０は、被処理画像の総てのラインについて復号がされるまで、上記ステップＳ１０３〜Ｓ１１８の動作を繰り返す（Ｓ１１９）。そして、被処理画像の総てのラインについて復号がされると（Ｓ１１９）、画像複号化処理を終了する。
【０１１８】
（実施の形態２）
実施の形態１では、最も簡単な例として、参照画像として前ライン上の１画素を用いて予測符号化を行うこととしたが、本実施の形態においては、符号化する画素の近傍の複数の画素を用いて、フィールド予測による予測符号化を行う。
【０１１９】
図１４には、一例として、現ライン（第ｌライン）上のｉ番目の画素の画素値ａｉを予測符号化する場合において、上述のような動的計画法により対応づけられた前ライン（第ｌ−１ライン）上のｊ（ｉ）番目の画素の画素値ｂｊ（ｉ）と、現ライン上のｉ−１番目の画素の画素値ａｉ−１とを用いてフィールド予測による予測符号化を行う例を示した。
【０１２０】
この場合、予測残差δａｉを求める式は、以下の（１６）式のように変更される。
【数２１】
2004208252.tif 000024
【０１２１】
ここで、ｗ１，ｗ２は重みづけを表す重み定数であり、ｗ１＋ｗ２＝１に規格化される。図１４では、ｗ１＝ｗ２＝１／２としてあるが、これに限る必要はない。
【０１２２】
この場合、復号時には、ｂｊ（ｉ），δａｉ、及び復元済みの画素値ａｉ−１から、ａｉは、
【数２２】
2004208252.tif 000025
のように復元される。
【０１２３】
尚、本実施の形態においては、符号化する画素の近傍の２画素を用いたフィールド予測の例を示したが、更に多くの画素を用いたフィールド予測を行うように構成してもよい。例えば、ａｉ−１，ｂｊ（ｉ）に加えて、ｂｊ（ｉ）近傍の画素を用いることもできる。
【０１２４】
尚、これらの場合には、ＤＰマッチングの（７）式等で用いる画素間相違度ｄ（ｉ，ｊ）として、単に画素間の距離｜ａｉ−ｂｊ（ｉ）｜を用いるのではなく、予測残差の絶対値を用いること、すなわち、画素間相違尺度を、
【数２３】
2004208252.tif 000026
とすることもできる。
【０１２５】
（実施の形態３）
本実施の形態においては、動画像や断層画像のような３次元画像におけるフレーム間予測符号化に、上述の動的計画法を適用するものである。
【０１２６】
図１５は動画像における時刻ｔにおけるフレームと、１フレーム前の時刻ｔ−１における画像フレームを示した図である。
【０１２７】
このように、時間的に隣接するフレーム間において、空間的に同位置にあるラインを考え、その上での対応づけｊ＝ｊ（ｉ）を行うことにより、フレーム間予測型の予測符号化が実現される。尚、対応づけの方法や予測残差の算出方法等については、実施の形態１と同様であるため、詳細な説明は省略する。実施の形態１の画像符号化方法において、ｌ→ｔ，ｌ−１→ｔ−１なる読替を行えばよい。また、ｔ＝１の先頭のフレーム（第１フレーム）の符号化においては、第０フレームの画素値が総て０であるとして処理を開始すればよい。
【０１２８】
尚、上記実施の形態１，２，３においては、画像符号化装置及び画像復号装置をハードウェア的に実現する例について説明したが、画像符号化装置及び画像復号装置をコンピュータにより構成し、両実施の形態の画像処理装置及び画像複合装置を実現するためのプログラムをコンピュータに読み込ませて実行させることにより、画像符号化装置及び画像復号装置として動作させるようにしてもよい。
【０１２９】
【発明の効果】
以上のように、本発明によれば、隣接するライン間で画素単位の対応を予測残差の総和が最小となるように最適に定めることにより、画像の空間的形状に柔軟に追随して画素間の対応がつけられ、一般的な画像においては、上記従来よりも予測精度が高く情報圧縮効率を向上させることが可能となる。従って、画像送信における画像転送時間の短縮や画像の記憶のための記憶容量の減少等を図ることができる。
【０１３０】
また、一方のライン上の画素に対応づける画素を他の“ライン”上の画素に制約することにより、対応付情報についての符号量の低減が図られる。また、一方のライン上の画素の対応づけの対象となるラインを「隣接するライン」にとることで、通常の画像の場合であれば、予測誤差のエントロピーも小さくできる。従って、予測誤差と対応付情報とのエントロピーのバランスが最適に近くなるので、圧縮された画像の符号量が減少する。
【０１３１】
また、画素間の対応づけの処理において、単調連続性を課すことにより、予測残差を大きくすることなく、２ライン上の画素間の対応づけの範囲を縮小することが可能となる。これにより、画素の対応付けに関する情報量が減少するため、符号化効率が向上する。また、符号化処理に要する時間の短縮も図られる。
【０１３２】
また、画素間の対応づけを動的計画法により行うことで、画素間の対応づけの計算処理の高速化が図られる。従って、画素単位の対応づけに基づく予測符号化処理を実用的な時間内で行うことが可能となる。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】単調連続性条件を具体的に説明する図である。
【図３】ＤＰマッチングを説明する図である。
【図４】ｉの進行に伴うｊの変化の制限を説明する図である。
【図５】本発明の実施の形態１に係る画像符号化装置のブロック図である。
【図６】本発明の実施の形態１に係る画像符号化方法を表すフローチャートである。
【図７】ＤＰマッチング処理を表すフローチャートである。
【図８】バックトラック処理を表すフローチャートである。
【図９】符号化処理を表すフローチャートである。
【図１０】予測残差情報の符号化処理を表すフローチャートである。
【図１１】本発明の実施の形態１に係る画像複号化装置のブロック図である。
【図１２】実施の形態１に係る画像複号化方法を示すフローチャートである。
【図１３】送信側のライン間の画素対応と受信側の処理との関係を示す図である。
【図１４】フィールド予測による予測符号化を行う場合の例を示す図である。
【図１５】動画像における時刻ｔにおけるフレームと、１フレーム前の時刻ｔ−１における画像フレームを示した図である。
【図１６】最も簡単な圧縮法である予測符号化方式の原理を示す図である。
【図１７】ラインの進行に伴ってライン上の１次元パターンが変化していく様子を表す図である。
【符号の説明】
１  画像符号化装置
２，３  ラインバッファ
４  ＤＰマッチング処理部
５  バックポインタテーブル
６  バックトラック処理部
７  差分歪み関数テーブル
８  最適予測残差テーブル
９  単純予測残差計算部
１０  単純予測残差テーブル
１１  符号化部
１３  比較出力部
１４，１５  送信バッファ
２０  画像複号化装置
２１  受信バッファ
２２  復号部
２６  最適予測復号部
２７  単純予測復号部
２８，２９  ラインバッファ
３０  被処理画像記憶手段
【図１】
2004208252.tif 000027
【図２】
2004208252.tif 000028
【図３】
2004208252.tif 000029
【図４】
2004208252.tif 000030
【図５】
2004208252.tif 000031
【図６】
2004208252.tif 000032
【図７】
2004208252.tif 000033
【図８】
2004208252.tif 000034
【図９】
2004208252.tif 000035
【図１０】
2004208252.tif 000036
【図１１】
2004208252.tif 000037
【図１２】
2004208252.tif 000038
【図１３】
2004208252.tif 000039
【図１４】
2004208252.tif 000040
【図１５】
2004208252.tif 000041
【図１６】
2004208252.tif 000042
【図１７】
2004208252.tif 000043