(57)【要約】【課題】少容量のメモリを使用して高速かつ高圧縮率で三次元画像を符号化する画像符号化技術を提供する。【解決手段】終端のフレーム画像を除くフレーム画像に対して走査することにより一次元化フレーム画像を生成し、各一次元化フレーム画像内に対して区間線型近似処理を行い符号化フレーム画像を生成し、Ｎｚ−１枚の符号化フレーム画像と終端フレーム画像とからなる近似カット画像に対し、三次元充填曲線に沿って走査して一次元化近似カット画像を生成し、一次元化近似カット画像内に対して区間線型近似処理を行って符号化カット画像を生成する。【選択図】          図１
2004350136.tif 000002
【特許請求の範囲】
【請求項１】
Ｎｚ枚（Ｎｚ≧２）のフレームからなる三次元の原カット画像を構成するフレーム画像のうち、終端のフレーム画像を除くＮｚ−１枚のフレーム画像のそれぞれに対して、所定の平面充填曲線に沿って走査することによりＮｚ−１個の一次元化フレーム画像を生成する一次元化フレーム画像生成手段と、
前記各一次元化フレーム画像内において、一の区間内における各画素の画素値と当該区間内における総ての画素の画素値の平均値との差の二乗和が所定の閾値以下となるように、前記一次元化フレーム画像を区間分割し、各区間の区間長及び平均値の情報からなる符号化フレーム画像を生成する第一区分線型近似手段と、
Ｎｚ−１枚の前記符号化フレーム画像と前記終端のフレーム画像とからなる近似カット画像に対して、所定の三次元充填曲線に沿って走査して一次元化近似カット画像を生成する一次元化近似カット画像生成手段と、
前記一次元化近似カット画像内において、一の区間内における各画素の画素値と当該区間内における総ての画素の画素値の平均値との差の二乗和が所定の閾値以下となるように、前記一次元化近似カット画像を区間分割し、各区間の区間長及び平均値の情報からなる符号化カット画像を生成する第二区分線型近似手段と、
を備えていることを特徴とする画像符号化装置。
【請求項２】
前記一次元化近似カット画像の各画素の画素値と前記符号化カット画像の各画素の画素値との差である一次元化残差カット画像を生成する一次元化残差カット画像生成手段と、
前記一次元化残差カット画像を変換符号化することにより符号化残差カット画像を生成する変換符号化手段と、
を有していることを特徴とする請求項１記載の画像符号化装置。
【請求項３】
一次元化フレーム画像生成手段が、Ｎｚ枚（Ｎｚ≧２）のフレームからなる三次元の原カット画像を構成するフレーム画像のうち、終端のフレーム画像を除くＮｚ−１枚のフレーム画像について、１枚ずつ順次、所定の平面充填曲線に沿って走査しながら、それに並行して、第一区分線型近似手段が、上記走査により逐次得られる一次元化フレーム画像に対して、
ａ．区間内における各画素の画素値と、当該区間内における画素の平均値との差を二乗した値を当該区間内の総ての画素について合計した値を求め、
ｂ．その合計値が所定の閾値を超えたときに、当該閾値を超える前の点の画素を当該区間の終点と確定し、当該閾値を超えた点の画素を新たな区間の始点とする、
という操作を行うことにより、当該一次元化フレーム画像を区間分割して各区間の区間長及び平均値の情報からなる符号化フレーム画像を生成し、これを符号化フレーム画像記憶手段に格納する第１ステップ、
及び、一次元化近似カット画像生成手段が、前記符号化フレーム画像記憶手段に記憶されたＮｚ−１枚の符号化フレーム画像と、前記終端のフレーム画像とから、所定の三次元充填曲線に沿った走査点に対応する画素を抽出して一次元化近似カット画像を生成しながら、それに並行して、第二区分線型近似手段が、前記一次元化近似カット画像に対して、
ａ．区間内における各画素の画素値と、当該区間内における画素の平均値との差を二乗した値を当該区間内の総ての画素について合計した値を求め、
ｂ．その合計値が所定の閾値を超えたときに、当該閾値を超える前の点の画素を当該区間の終点と確定し、当該閾値を超えた点の画素を新たな区間の始点とする、
という操作を行うことにより、当該一次元化近似カット画像を区間分割して各区間の区間長及び平均値の情報からなる符号化カット画像を生成する第２ステップ、
を有することを特徴とする画像符号化方法。
【請求項４】
前記第２ステップにおいては、第二区分線型近似手段が前記一次元化近似カット画像に対して一つの区間の終点を確定したときに、一次元化残差カット画像生成手段が、当該区間内の前記一次元化近似カット画像の各画素に対して、その画素値と当該区間内の各画素の画素値の平均値との残差を演算して残差カット画像記憶手段に格納し、
前記第２ステップの終了後、変換符号化手段が、Ｎｚ枚の各フレームの各々に対応する位置の前記残差を前記残差カット画像記憶手段から抽出するとともに、各フレームにおいて前記残差を変換符号化する第３ステップ
を有することを特徴とする請求項３記載の画像符号化方法。
【請求項５】
コンピュータに読み込ませて実行することにより、コンピュータに請求項３又は４記載の画像符号化方法を実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動画像や立体画像等の三次元画像を符号化する画像符号化技術に関し、特に符号化に際して小容量のメモリを使用して高速に符号化処理を行うことが可能な画像符号化技術に関する。
【０００２】
【従来の技術】
近年、携帯電話やモバイル・コンピュータによるデータ通信等において、電子カメラ等で撮像した動画像や立体画像のような三次元画像の通信が行われるようになってきている。そこで、ＭＰＥＧに代表されるように、三次元画像に対する種々の画像符号化技術が研究・開発されている。
【０００３】
このような画像符号化技術の一つとして、本発明者は、先にリアルタイム動画像転送方法を考案している（特許文献１参照）。特許文献１に記載では、三次元画像を符号化する方法として、以下のような方法を用いている。
【０００４】
ここで、三次元画像はＮｚ枚のフレーム画像から構成されているとし、各フレーム画像のｘｙ方向の画像サイズをＮｘ×Ｎｙとする。ここで、フレームとは、三次元画像を構成する１枚の単位画像をいう。また、以下、三次元画像のような、連続するフレーム画像の集合を「カット」という。
【０００５】
そして、まず、ルックアップテーブルから取得した三次元空間での走査順番に従って三次元画像を走査して原一次元データ｛ｑ０，  ｑ１，  …，  ｑＮｘＮｙ−１｝へ変換する。この三次元空間での走査順番は、ｘｙ方向の長方形の領域を充填する曲線に沿った二次元平面における走査順番を、二次元平面における走査順番が偶数番の場合にはｚ方向に０からＮｚまで走査し、二次元平面における走査順番が奇数番の場合には−ｚ方向にＮｚから０まで走査することにより、三次元空間を充填する走査順番に拡張することによって生成されている。
【０００６】
次に、生成された原一次元データ｛ｑ０，  ｑ１，  …，  ｑＮｘＮｙ−１｝を区分線型近似処理によって近似一次元データ｛（ａ０，  ｌ０），  …，  （ａＭ−１，  ｌＭ−１）｝を生成し、これを三次元画像の符号化データとする。
【０００７】
ここで、区分線型近似処理とは、原一次元データ｛ｑ０，  ｑ１，  …，  ｑＮｘＮｙ−１｝について、あるｉ番目の画素からｉ＋Ｎ番目の画素までの累積二乗誤差が予め与えられた閾値を超えた場合に、ｉ番目からｉ＋Ｎ−１番目を一つの区間とし、当該区間にあるすべての画素の画素値を当該区間にある画素の画素値の平均値で近似するという操作を、原一次元データの先頭から順に逐次行い、原一次元データ｛ｑ０，  ｑ１，  …，  ｑＮｘＮｙ−１｝を各区間の平均値と各区間の長さとの系列｛（ａ０，  ｌ０），  …，  （ａＭ−１，  ｌＭ−１）｝で置き換えることにより原一次元データを符号化する操作をいう。具体的には、以下のような操作を行う。
【０００８】
まず、ｉ＝０，  ｋ＝０，  Ｎ＝２としておいて、
（１）原一次元データ｛ｑ０，  ｑ１，  …，  ｑＮｘＮｙ−１｝内のｉ番目の画素ｑｉ−１からｉ＋Ｎ−１番目の画素ｑｉ＋Ｎ−１までのＮ個の画素の画素値の平均値を（数１）により計算する。
【数１】
2004350136.tif 000003
【０００９】
（２）次に、求められた平均値と原一次元データとの累積二乗誤差ｅｉ（Ｎ）を（数２）により計算する。
【数２】
2004350136.tif 000004
【００１０】
（３）そして、累積二乗誤差ｅｉ（Ｎ）が所定の閾値Γ以下であれば、Ｎを１だけ繰り上げて、上記（１）、（２）の処理を繰り返す。一方、累積二乗誤差ｅｉ（Ｎ）が閾値Γを超えたときには、Ｎ−１番目の画素までをｋ番目の区間とし、ｋ番目の区間の画素を区間内の画素の画素値の平均値と区間長との組（ａｋ，  ｌｋ）で符号化する。ここで、
【数３】
2004350136.tif 000005
とおいた。
【００１１】
そして、ｉをＮ−１だけ繰り上げた後、Ｎを２に設定し、再び、上記（１）〜（３）の動作を繰り返す。
【００１２】
このように、三次元画像の走査にルックアップテーブルを使用し、また、区分線型近似処理を使用して三次元画像の符号化を行うことにより、高速に符号化処理を行うことができる。更に、ｚ方向の走査順序を直線的にすることによって、動画像のようにｚ方向の相関が極めて強い三次元画像を効率的に圧縮することが可能となる。
【００１３】
【特許文献１】
特許第３３４７６８４号公報
【００１４】
【発明が解決しようとする課題】
上記特許文献１に示された画像符号化方法は、高速に高圧縮率で符号化処理を行うことが可能であるため、テレビ電話などのようにリアルタイム性と高速性が要求されるような分野において適用すると、優れた効果が発揮される。
【００１５】
しかしながら、その一方で、符号化処理を行うためには、符号化処理を行う三次元画像を、一旦フレームメモリに総て格納した後に符号化処理を行う必要がある。従って、画像サイズが大きい場合には、大容量のフレームメモリが必要とされる。
【００１６】
一方、近年著しく普及してきた携帯電話等の携帯電子機器のように、小型化・省電力化の要求から装置自体のメモリ容量が制限される装置においては、少容量のフレームメモリを用いて三次元画像を高速かつ高圧縮率で符号化する技術が望まれる。
【００１７】
そこで、本発明の目的は、少容量のメモリを使用して高速かつ高圧縮率で三次元画像を符号化する画像符号化技術を提供することにある。
【００１８】
【課題を解決するための手段】
本発明に係る画像符号化装置の第１の構成は、Ｎｚ枚（Ｎｚ≧２）のフレームからなる三次元の原カット画像を構成するフレーム画像のうち、終端のフレーム画像を除くＮｚ−１枚のフレーム画像のそれぞれに対して、所定の平面充填曲線に沿って走査することによりＮｚ−１個の一次元化フレーム画像を生成する一次元化フレーム画像生成手段と、前記各一次元化フレーム画像内において、一の区間内における各画素の画素値と当該区間内における総ての画素の画素値の平均値との差の二乗和が所定の閾値以下となるように、前記一次元化フレーム画像を区間分割し、各区間の区間長及び平均値の情報からなる符号化フレーム画像を生成する第一区分線型近似手段と、Ｎｚ−１枚の前記符号化フレーム画像と前記終端のフレーム画像とからなる近似カット画像に対して、所定の三次元充填曲線に沿って走査して一次元化近似カット画像を生成する一次元化近似カット画像生成手段と、前記一次元化近似カット画像内において、一の区間内における各画素の画素値と当該区間内における総ての画素の画素値の平均値との差の二乗和が所定の閾値以下となるように、前記一次元化近似カット画像を区間分割し、各区間の区間長及び平均値の情報からなる符号化カット画像を生成する第二区分線型近似手段とを備えていることを特徴とする。
【００１９】
この構成によれば、第一区分線型近似手段により、終端のフレーム画像を除くＮｚ−１枚のフレーム画像は、各区間の区間長及び平均値の情報からなる符号化フレーム画像に変換される。そのため、Ｎｚ−１枚のフレーム画像のデータ量は圧縮され、符号化フレーム画像を格納するためのメモリを小さくできる。
【００２０】
また、一次元化近似カット画像生成手段が、圧縮された符号化フレーム画像を復元することなく、Ｎｚ−１枚の符号化フレーム画像と終端のフレーム画像とから直接一次元化近似カット画像を生成し、この一次元化近似カット画像を第２区分線型近似手段が符号化カット画像に変換して圧縮する。この一次元化近似カット画像生成手段及び第２区分線型近似手段の処理は、同時並行的に行うことができる。すなわち、一次元化近似カット画像生成手段がＮｚ−１枚の符号化フレーム画像と終端のフレーム画像とから一次元化近似カット画像を１画素ずつ生成しながら、同時に、生成された一次元化近似カット画像の画素データを用いて、第２区分線型近似手段が符号化カット画像を生成することができる。従って、圧縮された一次元化近似カット画像を復元した画像を別途に記憶するメモリは不要である。従って、少容量のメモリを用いてカット画像の符号化を行うことが可能となる。
【００２１】
更に、三次元空間での走査線に沿って区分線型近似処理を行うことにより、符号化カット画像においては三次元画像の空間的な冗長性が除去される。従って、高圧縮率で符号化することができる。
【００２２】
ここで、「平面充填曲線」とは、平面内の各格子点を１回だけ通過して平面内を隙間なく充填する曲線をいう。例えば、ラスタ・スキャン、ジグザグ・スキャン、ヒルベルト・スキャン等の走査パターンである。「三次元充填曲線」とは、３次元空間内の各格子点を１回だけ通過して３次元空間内を隙間なく充填する曲線をいう。
【００２３】
また、本発明において、前記一次元化フレーム画像生成手段は、ルックアップテーブルに格納された前記所定の平面充填曲線を参照して、前記各フレーム画像の走査を行うことができる。また、一次元化近似カット画像生成手段は、ルックアップテーブルに格納された前記所定の三次元充填曲線を参照して、前記近似カット画像の走査を行うことができる。このように、メモリに余裕がある場合には、ルックアップテーブルを使用すれば、走査処理が高速化される。
【００２４】
また、本発明において、三次元充填曲線は、フレーム内の領域を充填する曲線に沿った、順序づけられた格子点の集合からなる走査順番を、当該走査順番が偶数番の場合には一端のフレームから他端のフレームに向かう方向に０からＮｚ−１まで走査し、当該走査順番が奇数番の場合には他端のフレームから一端のフレームに向かう方向にＮｚ−１から０まで走査することにより、三次元空間を充填する走査順番に拡張することによって生成されたものを用いることができる。このように、三次元充填曲線は、フレームと垂直な方向に直線的に走査するようにすれば、動画像のようにフレーム間の相関が非常に大きい三次元画像に対しては、符号化による圧縮効率を高めることができる。
【００２５】
本発明に係る画像符号化装置の第２の構成は、前記第１の構成において、前記一次元化近似カット画像の各画素の画素値と前記符号化カット画像の各画素の画素値との差である一次元化残差カット画像を生成する一次元化残差カット画像生成手段と、前記一次元化残差カット画像を変換符号化することにより符号化残差カット画像を生成する変換符号化手段とを有していることを特徴とする。
【００２６】
この構成によれば、一次元化残差カット画像を変換符号化することにより、原カット画像は、一次元化近似カット画像と符号化残差カット画像とに符号化される。そして、復号の際には、一次元化残差カット画像から一次元化残差カット画像を復号し、符号化残差カット画像の各画素に復号された一次元化残差カット画像を重畳して原カット画像を復号する。従って、一次元化残差カット画像の情報により、より高画質の画像を再生することができる。
【００２７】
ここで、「変換符号化」とは、ＤＣＴ、ＫＬ変換等の座標系の変換を用いた符号化をいう。
【００２８】
また、変換符号化手段は、一次元化残差カット画像を変換符号化を行う際には、一次元化残差カット画像から各フレーム内の画素に対応する残差を抽出して、それぞれのフレーム内において変換符号化を行うようにすることができる。フレーム内において変換符号化を行うことにより、画像の二次元的な相関による冗長性を除去し、変換符号化による圧縮効率を上げることができる。
【００２９】
本発明に係る画像符号化方法の第１の構成は、一次元化フレーム画像生成手段が、Ｎｚ枚（Ｎｚ≧２）のフレームからなる三次元の原カット画像を構成するフレーム画像のうち、終端のフレーム画像を除くＮｚ−１枚のフレーム画像について、１枚ずつ順次、所定の平面充填曲線に沿って走査しながら、それに並行して、第一区分線型近似手段が、上記走査により逐次得られる一次元化フレーム画像に対して、
ａ．区間内における各画素の画素値と、当該区間内における画素の平均値との差を二乗した値を当該区間内の総ての画素について合計した値を求め、
ｂ．その合計値が所定の閾値を超えたときに、当該閾値を超える前の点の画素を当該区間の終点と確定し、当該閾値を超えた点の画素を新たな区間の始点とする、
という操作を行うことにより、当該一次元化フレーム画像を区間分割して各区間の区間長及び平均値の情報からなる符号化フレーム画像を生成し、これを符号化フレーム画像記憶手段に格納する第１ステップ、
及び、一次元化近似カット画像生成手段が、前記符号化フレーム画像記憶手段に記憶されたＮｚ−１枚の符号化フレーム画像と、前記終端のフレーム画像とから、所定の三次元充填曲線に沿った走査点に対応する画素を抽出して一次元化近似カット画像を生成しながら、それに並行して、第二区分線型近似手段が、前記一次元化近似カット画像に対して、
ａ．区間内における各画素の画素値と、当該区間内における画素の平均値との差を二乗した値を当該区間内の総ての画素について合計した値を求め、
ｂ．その合計値が所定の閾値を超えたときに、当該閾値を超える前の点の画素を当該区間の終点と確定し、当該閾値を超えた点の画素を新たな区間の始点とする、
という操作を行うことにより、当該一次元化近似カット画像を区間分割して各区間の区間長及び平均値の情報からなる符号化カット画像を生成する第２ステップを有することを特徴とする。
【００３０】
これにより、一次元化フレーム画像生成手段が読み込まれるフレームごとに走査して一次元化するのと並行して、第一区分線型近似手段がこの一次元化フレーム画像を区分線型近似処理により圧縮された符号化フレーム画像に変換し、これを符号化フレーム画像記憶手段に格納する。従って、区分線型近似処理による圧縮効率がｐ、フレーム１枚あたりのデータ容量がＤとすれば、符号化フレーム画像記憶手段のメモリ容量は、（１＋（Ｎｚ  −１）ｐ）Ｄとなる。従って、総てのフレームをフレームメモリに格納する場合に比べると、メモリ容量は（１＋（Ｎｚ  −１）ｐ）／  Ｎｚに削減される。例えば、Ｎｚ  ＝１０，  ｐ＝０．５とすると、必要なメモリ容量は、総てのフレームをフレームメモリに格納する場合に比べ５５％に削減される。
【００３１】
また、第２ステップにおいては、符号化フレーム画像記憶手段に格納された符号化フレーム画像からもとの画像を復元することなく、一次元化近似カット画像生成手段が必要なデータを符号化フレーム画像記憶手段から抽出しながら一次元化近似カット画像を生成し、それに並行して、第二区分線型近似手段が区分線型近似処理により符号化カット画像を生成する。従って、符号化に際して大きな容量のメモリは必要がない。
【００３２】
従って、少容量のメモリを使用して高速かつ高圧縮率で三次元画像を符号化することができる。
【００３３】
本発明に係る画像符号化方法の第２の構成は、前記第１の構成において、前記第２ステップにおいては、第二区分線型近似手段が前記一次元化近似カット画像に対して一つの区間の終点を確定したときに、一次元化残差カット画像生成手段が、当該区間内の前記一次元化近似カット画像の各画素に対して、その画素値と当該区間内の各画素の画素値の平均値との残差を演算して残差カット画像記憶手段に格納し、前記第２ステップの終了後、変換符号化手段が、Ｎｚ枚の各フレームの各々に対応する位置の前記残差を前記残差カット画像記憶手段から抽出するとともに、各フレームにおいて前記残差を変換符号化する第３ステップを有することを特徴とする。
【００３４】
また、本発明に係るプログラムは、コンピュータに読み込ませて実行することにより、コンピュータに上記第１又は第２の構成に係る画像符号化方法を実行させるものであることを特徴とする。
【００３５】
【発明の実施の形態】
以下、本発明の一実施形態について図面を参照しながら説明する。
【００３６】
（実施形態１）
図１は本発明の実施形態１に係る画像符号化装置の構成を表すブロック図である。
【００３７】
図１において、本実施形態に係る画像符号化装置１は、画像入力手段２、フレームメモリ３、一次元化フレーム画像生成手段４、第一ルックアップテーブル４ａ、第一区分線型近似手段５、符号化フレーム画像記憶手段６、一次元化カット画像生成手段７、第二ルックアップテーブル７ａ、第二区分線型近似手段８、符号化カット画像記憶手段９、一次元化残差カット画像生成手段１０、残差カット画像記憶手段１１、変換符号化手段１２、符号化残差カット画像記憶手段１３、及び出力手段１４を備えている。
【００３８】
画像入力手段２は、動画像や立体画像などの三次元の原カット画像Ｇを入力するための装置である。具体的には、画像入力手段２は、例えば、ＣＣＤ（Ｃｈａｒｇｅ  Ｃｏｕｐｌｅｄ  Ｄｅｖｉｃｅ；  電荷結合素子）などの撮像素子やＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどの外部記憶装置、モデム等の通信ネットワーク・インタフェースにより構成される。ここで、原カット画像はＮｚ枚（Ｎｚ≧２）のフレーム画像｛Ｆ０，…，Ｆ  Ｎｚ −１｝によって構成されているものとする。
【００３９】
フレームメモリ３は、画像入力手段２から入力されるフレーム画像Ｆｚ（ｚ∈｛０，…，  Ｎｚ  −１｝）を一時的に記憶するメモリである。本実施形態においては、フレームメモリ３はフレーム画像１枚分のメモリ容量を有するものとする。
【００４０】
一次元化フレーム画像生成手段４は、原カット画像Ｇを構成するＮｚ枚のフレーム画像のうち、終端のフレーム画像Ｆ  Ｎｚ −１を除くＮｚ−１枚のフレーム画像｛Ｆ０，…，Ｆ  Ｎｚ −２｝のそれぞれに対して、一次元化フレーム画像｛ＦＬ０，…，ＦＬ  Ｎｚ −１｝を生成する。ここで、一次元化フレーム画像ＦＬｚ（ｚ∈｛０，…，  Ｎｚ  −２｝）とは、フレーム画像Ｆｚを所定の平面充填曲線に沿って走査することにより生成される一次元の画素データ列をいう。平面充填曲線に関する情報は、第一ルックアップテーブル４ａに記憶されている。一次元化フレーム画像生成手段４は、走査順番についてはこの第一ルックアップテーブル４ａを参照しながら走査を行う。なお、平面充填曲線としては、ラスタ走査曲線、ジグザグ走査曲線、ヒルベルト曲線等を使用することができる。
【００４１】
第一区分線型近似手段５は、一次元化フレーム画像ＦＬｚ（ｚ∈｛０，…，  Ｎｚ  −２｝）に対して、区分線型近似処理を行うことによって、符号化フレーム画像ＦＣｚ＝｛（ａｚ，０，ｌ  ｚ，０），…，（ａ  ｚ，Ｍｚ−１，ｌ  ｚ，Ｍｚ−１）｝（Ｍｚはフレーム内の区間数）を生成する。なお、区分線型近似処理については、〔従来の技術〕の欄で既に説明しているため、ここでは説明は省略する。符号化フレーム画像記憶手段６は、第一区分線型近似手段５により生成された符号化フレーム画像｛ＦＣｚ；  ｚ＝０，…，  Ｎｚ  −２｝が格納される。
【００４２】
一次元化近似カット画像生成手段７は、符号化フレーム画像記憶手段６に格納された符号化フレーム画像｛ＦＣｚ；  ｚ＝０，…，  Ｎｚ  −２｝及びフレームメモリ３に格納された終端のフレーム画像Ｆ  Ｎｚ −１からなる近似カット画像Ｇ’に対して、所定の三次元充填曲線に沿って走査をして一次元化近似カット画像ＧＬ’を生成する。三次元充填曲線に関する情報は、第二ルックアップテーブル７ａに記憶されている。一次元化近似カット画像生成手段７は、走査順番についてはこの第二ルックアップテーブル７ａを参照しながら走査を行う。
【００４３】
なお、三次元充填曲線としては、第一ルックアップテーブル４ａに記憶された平面充填曲線に沿った、順序づけられた格子点の集合からなる走査順番を、当該走査順番が偶数番の場合には一端のフレームから他端のフレームに向かう方向に０からＮｚ  −１まで走査し、当該走査順番が奇数番の場合には他端のフレームから一端のフレームに向かう方向にＮｚ  −１から０まで走査することにより、三次元空間を充填する走査順番に拡張することによって生成されたものが用いられる。このように、第一ルックアップテーブル４ａに記憶された平面充填曲線に沿った、順序づけられた格子点の集合からなる走査順番を、フレームに対して垂直方向に直線的に引き延ばしたものを使用することで、符号化フレーム画像記憶手段６に記憶された符号化フレーム画像｛ＦＣｚ；  ｚ＝０，…，  Ｎｚ  −２｝から三次元充填曲線に沿った画素データを抽出することが容易となる。
【００４４】
第二区分線型近似手段８は、一次元化近似カット画像生成手段７が生成する一次元化近似カット画像ＧＬ’に対して区分線型近似処理を行うことにより、符号化カット画像ＧＣを生成する。なお、ここでの区分線型近似処理も、上記〔従来の技術〕の欄で説明したものと同様である。そして、生成された符号化カット画像ＧＣは、符号化カット画像記憶手段９に格納される。
【００４５】
一次元化残差カット画像生成手段１０は、一次元化近似カット画像ＧＬ’の各画素の画素値と、符号化カット画像ＧＣの各画素の画素値との差である一次元化残差カット画像ＧＲＬを生成し、残差カット画像記憶手段１１に格納する。変換符号化手段１２は、残差カット画像記憶手段１１に格納された一次元化残差カット画像ＧＲＬを変換符号化することにより、符号化残差カット画像ＧＲＣを生成し、符号化残差カット画像記憶手段１３に格納する。
【００４６】
そして、符号化カット画像記憶手段９に格納された符号化カット画像ＧＣ及び符号化残差カット画像記憶手段１３に格納された符号化残差カット画像ＧＲＣは、出力手段１４により出力される。出力手段１４としては、例えば、ディスプレイ、送信インタフェース等が用いられる。
【００４７】
以上のように構成された本実施形態に係る画像符号化装置において、以下、その画像符号化方法について説明する。
【００４８】
図２は本発明の実施形態１に係る画像符号化方法の全体の流れを表すフローチャートである。
【００４９】
まず、フレームの番号を表すパラメータｚを０として（Ｓ１）、画像入力手段２からｚ番目のフレーム画像Ｆｚ＝｛ｑｘ，ｙ，ｚ；  ｘ＝０，…，Ｎｘ−１，  ｙ＝０，…，Ｎｙ−１｝が入力され、フレームメモリ３に格納される（Ｓ２）。ここで、フレーム平面をｘｙ平面で表すものとし、Ｎｘはフレームのｘ方向のサイズ、Ｎｙはフレームのｙ方向のサイズを表す。
【００５０】
次に、一次元フレーム画像生成手段４は、まず、フレーム画像Ｆｚを適当なサイズの部分画像｛ＦＢｚ（Ｘ，Ｙ）；  Ｘ＝０，…，ＮＢｘ−１，  Ｙ＝０，…，ＮＢｙ−１｝に分割する（Ｓ３）。以下、この部分画像ＦＢｚ（Ｘ，Ｙ）のことをブロックという。このブロックへの分割は、以下の処理時において必要とされる計算量やメモリ容量をできるだけ少なくするために行われるものである。なお、ＮＢｘはフレーム内におけるブロックのｘ方向の数、ＮＢｙはフレーム内におけるブロックのｙ方向の数を表す。従って、各ブロックのサイズは（Ｎｘ／ＮＢｘ）×（Ｎｙ／ＮＢｙ）画素からなる。
【００５１】
次に、一次元フレーム画像生成手段４は、第一ルックアップテーブル４ａに格納された走査順番に従って、フレーム画像Ｆｚを走査し、一次元化フレーム画像ＦＬｚを生成する。また、それと並行して、第一区分線型近似手段５は、走査によって逐次得られる一次元化フレーム画像ＦＬｚに対して、区分線型近似処理を行い、符号化フレーム画像ＦＣｚを生成する（Ｓ４）。ここで生成された符号化フレーム画像ＦＣｚは、符号化フレーム画像記憶手段６に格納される（Ｓ５）。そして、変数ｚの値を１だけ繰り上げられて（Ｓ６）、変数ｚの値がＮｚ−２に達するまで、ステップＳ２〜Ｓ５の処理が繰り返される。
【００５２】
ここで、ステップＳ４〜Ｓ５の動作について補足説明する。本実施の形態においては、走査順番の一例として、ブロックのサイズを８×８画素として、第一ルックアップテーブル４ａには図３に示したようなヒルベルト曲線に従った走査順番が格納されているものとする。
【００５３】
まず、第一区分線型近似手段５は、現在の区間番号を表す変数ｉを０に設定するとともに、区間の長さを表す変数Ｎを２に設定する。
【００５４】
一方、一次元フレーム画像生成手段４は、フレーム画像Ｆｚの各ブロックＦＢｚ（Ｘ，Ｙ）（Ｘ＝０，…，ＮＢｘ−１，  Ｙ＝０，…，ＮＢｙ−１）に対して、順次第一ルックアップテーブル４ａの走査順番に従って走査していく。その結果、一次元化フレーム画像ＦＬｚ＝｛ｑｚ，０，ｑ  ｚ，１，…｝が逐次得られる。
【００５５】
これと並行して、第一区分線型近似手段５は、（数１）、（数２）に示した漸化式により画素値の平均値と累積二乗誤差ｅｉ（Ｎ）を求める。そして、累積二乗誤差ｅｉ（Ｎ）が所定の閾値Γ以下であれば、Ｎを１だけ繰り上げて、（数１）、（数２）に示した漸化式の演算処理を繰り返す。一方、累積二乗誤差ｅｉ（Ｎ）が閾値Γを超えたときには、Ｎ−１番目の画素までをｋ番目の区間とし、ｋ番目の区間の画素を区間内の画素の画素値の平均値と区間長との組（ａ  ｚ，ｋ，  ｌ  ｚ，ｋ）で符号化する。（ａ  ｚ，ｋ，  ｌ  ｚ，ｋ）は（数３）に示した通りである。そして、この符号化されたデータ（符号化フレーム画像ＦＣｚ）を符号化フレーム画像記憶手段６に格納する。そして、第一区分線型近似手段５は、変数ｉをＮ−１だけ繰り上げた後、Ｎを２に初期化し、再び、上記動作を繰り返す。
【００５６】
図４は符号化フレーム画像記憶手段６に格納された符号化フレーム画像ＦＣｚ（ｚ∈｛０，…，  Ｎｚ  −２｝）のデータ構造を表す図である。図４に示したように、先頭のアドレスには、フレームアドレス情報ａｄｒ０〜ａｄｒ  Ｎｚ −２が格納されている。このフレームアドレス情報ａｄｒ０〜ａｄｒ  Ｎｚ −２は、各フレームの符号化フレーム画像ＦＣ０〜ＦＣ  Ｎｚ −２が格納されているアドレスの先頭アドレスを表す。フレームアドレス情報ａｄｒ０〜ａｄｒ  Ｎｚ −２に続いて、符号化フレーム画像ＦＣ０〜ＦＣ  Ｎｚ −２の情報｛（ａｚ，ｉ，  ｌｚ，ｉ）；  ｚ＝０，…，  Ｎｚ  −２，  ｉ＝０，…，Ｍｚ−２−１｝が格納されている。従って、先頭のフレームアドレス情報ａｄｒ０〜ａｄｒ  Ｎｚ −２を参照することにより、符号化フレーム画像ＦＣ０〜ＦＣ  Ｎｚ −２の情報に自由にアクセスすることができる。
【００５７】
以上のように、一次元フレーム画像生成手段４による一次元化フレーム画像ＦＬｚの生成と、第一区分線型近似手段５による符号化フレーム画像ＦＣｚの生成とが同時並行的に行われる。そして、得られた符号化フレーム画像ＦＣｚが符号化フレーム画像記憶手段６に蓄積される。符号化フレーム画像ＦＣｚの圧縮率は、区分線型近似処理における累積二乗誤差ｅｉ（Ｎ）の閾値Γの大きさによって決まる。個々では、圧縮率が１／１０〜１／３程度の値となるように閾値Γの大きさが設定される。
【００５８】
このように、入力されるフレーム画像Ｆｉは逐次１／１０〜１／３程度のデータ量に圧縮され、符号化フレーム画像記憶手段６に蓄積されるため、フレーム画像Ｆｉを格納するメモリ容量を少なくすることが可能である。
【００５９】
なお、本実施形態では第一ルックアップテーブル４ａに格納する走査順番として図３の平面充填曲線を使用することとしたが、第一ルックアップテーブル４ａに格納する走査順番としては、他にも、例えば図５（ａ）〜（ｈ）に示したような平面充填曲線に沿った走査順番などを使用することもできる。
【００６０】
図２に戻って、０〜Ｎｚ−２番目までのフレーム画像Ｆ０〜Ｆ  Ｎｚ −２に対して、区分線型近似処理により符号化フレーム画像ＦＣ０〜ＦＣ  Ｎｚ −２の生成が終わると、次に、画像入力手段２は、終端のフレーム画像Ｆ  Ｎｚ −１を読み込んで、フレームメモリ３に格納する（Ｓ７）。
【００６１】
次いで、一次元化近似カット画像生成手段７は、第二ルックアップテーブル７ａに格納された走査順番に従って、符号化フレーム画像記憶手段６に格納された符号化フレーム画像ＦＣ０〜ＦＣ  Ｎｚ −２とフレームメモリ３に格納された終端のフレーム画像Ｆ  Ｎｚ −１とから仮想的に構成される三次元の近似カット画像Ｇ’を走査し、一次元化近似カット画像ＧＬ’を生成する。この三次元の近似カット画像Ｇ’の走査もブロック単位で行われる。また、それと並行して、第二区分線型近似手段８は、この走査によって逐次得られる一次元化近似カット画像ＧＬ’に対して、区分線型近似処理を行い、符号化カット画像ＧＣを生成する。また、同時に一次元化残差カット画像生成手段１０が、一次元化残差カット画像ＧＲＬを生成して残差カット画像記憶手段１１に格納する（Ｓ８）。
【００６２】
ここで、ステップＳ８の処理について補足説明する。本実施の形態においては、第二ルックアップテーブル７ａに格納された走査順番は、第一ルックアップテーブル４ａに格納された走査順番（図３参照）に対応させて、図６のような三次元充填曲線に沿った走査順番とされている。図６に示す走査順番は、フレーム内の領域を充填する図３の曲線に沿った、順序づけられた格子点の集合からなる走査順番（ｘ０，ｙ０），（ｘ１，ｙ１），…，（ｘＮｘＮｙ−１，ｙＮｘＮｙ−１）を、当該走査順番が偶数番の場合にはｚ方向に０からＮｚ−１まで走査し、当該走査順番が奇数番の場合には−ｚ方向にＮｚ−１から０まで走査することにより、三次元空間を充填する走査順番
【数４】
2004350136.tif 000006
に拡張することによって生成されたものが用いられている。このように、三次元充填曲線は、フレームと垂直なｚ方向に直線的に走査するようにすれば、動画像のようにフレーム間の相関が非常に大きい三次元画像に対しては、符号化による圧縮効率を高めることができる。
【００６３】
一次元化近似カット画像生成手段７は、まず、内部変数ｉ，ｚを０に設定した後、以下のような動作により一次元化近似カット画像を生成する。
【００６４】
（１）  第二ルックアップテーブル７ａから走査座標（ｘｉ，ｙｉ，ｚ）を取得する。
【００６５】
（２）  ｚ≠ｎ−１の場合、一次元化近似カット画像生成手段７は、符号化フレーム画像記憶手段６から、走査座標（ｘｉ，ｙｉ，ｚ）に対応する位置の画素値ｑｉ，ｚを抽出する。この場合、一次元化近似カット画像生成手段７は、まずｚの値から、フレームアドレス情報ａｄｒｚを取得し、第ｚフレームの符号化フレーム画像ＦＣｚの先頭アドレスにアクセスする。そして、第ｚフレームの符号化フレーム画像ＦＣｚの区間長ｌｚ，ｊ（ｊ＝０，…，Ｍｚ−１）を順次累算していき、累算値がｉ以上になったときの番号ｊに対応する画素値ａｚ，ｊを取得して、これを走査座標（ｘｉ，ｙｉ，ｚ）に対応する位置の画素値ｑｉ，ｚとすればよい。
一方、ｚ＝ｎ−１の場合、一次元化近似カット画像生成手段７は、フレームメモリ３から、走査座標（ｘｉ，ｙｉ，ｚ）に対応する位置（ｘｉ，ｙｉ）の画素値ｑｉ，ｚを抽出する。
【００６６】
（３）ｚの値を１だけ増加させる。
【００６７】
（４）  （１）〜（３）の動作をｚ＝ｎ−１となるまで繰り返す。
【００６８】
（５）  次に、ｉを１だけ増加させ、（１）〜（３）の動作をｚ＝０となるまで繰り返す。このとき、（３）においてはｚの値を１だけ減少させる。
【００６９】
（６）  （１）〜（５）の動作を、ｉの値がＮｘＮｙ−１になるまで行う。
【００７０】
そして、一次元化近似カット画像生成手段７の符号化処理と並行して、第二区分線型近似手段８は、順次得られる一次元化近似カット画像ＧＬ’に基づいて、区分線型近似処理を行い、その結果生成される符号化カット画像ＧＣを、符号化カット画像記憶手段９に格納する。
【００７１】
このようにして、一次元化近似カット画像生成手段７は、符号化フレーム画像記憶手段６に格納された符号化フレーム画像｛ＦＣｚ；  ｚ＝０，…，Ｎｚ−２｝を復号することなく、一次元化近似カット画像ＧＬ’＝｛ｑ０，０，…ｑ０，Ｎｚ−１，ｑ１，Ｎｚ−１，…，ｑ１，０，…，  ｑＮｘＮｙ−１，０｝を生成するため、符号化処理に要するメモリ容量を大幅に抑えることが可能となる。また、一次元化近似カット画像ＧＬ’は、逐次生成されるごとに第二区分線型近似手段８によって符号化処理され、データ量が圧縮される。そして、この符号化処理で得られる符号化カット画像ＧＣを、符号化カット画像記憶手段９に格納することで、符号化処理に要するメモリ容量が更に抑えられる。
【００７２】
一次元化残差カット画像生成手段１０は、区分線型近似処理において、一つの区間が確定するごとに、その区間内にある一次元化近似カット画像ＧＬ’の各画素の画素値と符号化カット画像ＧＣの画素値との差である一次元化残差カット画像ＧＲＬを生成し、これを残差カット画像記憶手段１２に格納する。
【００７３】
上記ステップＳ８の処理が１ブロック分の終わるたびに、変換符号化手段１２は、残差カット画像記憶手段１２に格納されたＮｚフレームの１ブロック分の一次元化残差カット画像ＧＲＬに対して、１フレームごとに変換符号化を行い、符号化残差カット画像記憶手段１３に格納する（Ｓ９）。ここで、変換符号化は、一般に広く用いられているＤＣＴ（離散コサイン変換）やＫＬ変換等の手法を用いて行われる。このように、変換符号化手段１２がブロック単位で逐次変換符号化を行うことで、残差カット画像記憶手段１２の記憶容量はＮＢｘ×ＮＢｙ×Ｎｚ画素分あればよいこととなる。変換符号化された符号化残差カット画像ＧＣは、フレーム内相関による冗長性が除去されるため、データ量は少ない。従って、符号化残差カット画像記憶手段１３の容量も小さくてすむ。
【００７４】
以上の処理が総て終了すると、出力手段１４は、符号化カット画像ＧＣ及び符号化残差カット画像ＧＲＣを符号化された三次元画像として出力し（Ｓ１０）、処理を終了する。
【００７５】
以上のように、本実施形態に係る画像符号化装置によれば、少ないメモリ容量で三次元画像の符号化を行うことが可能となる。また、画像の符号化において区分線型近似処理を用いることで、画像が読み込まれる順に逐次的に符号化されていくため、後段の処理を並行して行うことができる。従って、処理が高速化される。
【００７６】
【発明の効果】
以上のように、本発明によれば、少容量のメモリを使用して高速かつ高圧縮率で三次元画像を符号化することが可能となる。従って、携帯電話、デジタルカメラ等の携帯電子機器のようにメモリ容量が制限される機器において、動画像などの三次元画像を符号化するのに適した画像符号化技術を提供することができる。
【図面の簡単な説明】
【図１】本発明の実施形態１に係る画像符号化装置の構成を表すブロック図である。
【図２】本発明の実施形態１に係る画像符号化方法の全体の流れを表すフローチャートである。
【図３】第一ルックアップテーブル４ａに格納された走査順番を表す図である。
【図４】符号化フレーム画像記憶手段６に格納された符号化フレーム画像ＦＣｚ（ｚ∈｛０，…，  Ｎｚ  −２｝）のデータ構造を表す図である。
【図５】第一ルックアップテーブル４ａに格納することのできる走査順番の他の例を表す図である。
【図６】第二ルックアップテーブル７ａに格納された走査順番を表す図である。
【符号の説明】
１  画像符号化装置
２  画像入力手段
３  フレームメモリ
４  一次元フレーム画像生成手段
４ａ  第一ルックアップテーブル
５  第一区分線型近似手段
６  符号化フレーム画像記憶手段
７  一次元化近似カット画像生成手段
７ａ  第二ルックアップテーブル
８  第二区分線型近似手段
９  符号化カット画像記憶手段
１０  一次元化残差カット画像生成手段
１１  残差カット画像記憶手段
１２  変換符号化手段
１３  符号化残差カット画像記憶手段
１４  出力手段
【図１】
2004350136.tif 000007
【図２】
2004350136.tif 000008
【図３】
2004350136.tif 000009
【図４】
2004350136.tif 000010
【図５】
2004350136.tif 000011
【図６】
2004350136.tif 000012