画像信号の符号化方法および装置
【課題】演算の簡易化と圧縮効率の高効率化を同時に実現する画像信号の符号化方法および装置を提供することを目的とするものである。
【解決手段】
信号の列を３次元ブロック化して、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割して、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する画像信号の符号化方法において、 ３次元ブロックＨ１を、複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なさる前記ブロックを集めたものＩ１，Ｉ３，Ｊ１，Ｊ２，Ｊ３を前記塊とする。
【解決手段】
信号の列を３次元ブロック化して、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割して、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する画像信号の符号化方法において、 ３次元ブロックＨ１を、複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なさる前記ブロックを集めたものＩ１，Ｉ３，Ｊ１，Ｊ２，Ｊ３を前記塊とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像信号を符号化して、画像信号を圧縮する方法および装置に関するものである。
【背景技術】
【０００２】
例えば、無線テレビ電話や携帯情報端末（ＰＤＡ）のようなパーソナルビデオコミュニケーションシステムが急速に普及しつつある。パーソナルビデオコミュニケーションシステムにおいては、画像信号の符号化による信号圧縮は最も重要な技術のひとつである。現在、ＭＰＥＧ１，ＭＰＥＧ２，ＭＰＥＧ４，Ｈ．２６１あるいはＨ．２６３などの画像信号の符号化方式がよく知られている。しかし、これらの符号化方式は、符号化および復号化の計算が複雑で手間がかかるで、電池のエネルギー消費量が大きく、ＰＤＡによる通信には不都合である。
【０００３】
この問題を解決するために、３次元階層ツリー構造の一種である八分木法を用いて、３次元画像や動画の信号圧縮を行うことが提案されている（非特許文献１〜４）。
【０００４】
八分木法を用いる画像信号の圧縮方法は、概略、次のようなものである。
図１２は八分木法による階層ツリー構造の概念図である。上位の３次元ブロックＡ１は画像信号の列を４×４×４画素にブロック化したものであり、８個の中位の３次元ブロックＢ１〜Ｂ８に分割され、前記８個の中位の３次元ブロックＢ１〜Ｂ８のうち、２個の３次元ブロックＢ５およびＢ８はそれぞれ更に下位の３次元ブロックＣ１〜Ｃ８および３次元ブロックＣ９〜Ｃ１６に分割される。
【０００５】
３次元ブロックの分割を行うか否かの判断は、ある階層の３次元ブロックに含まれる画素が同一と見なせることを基準におこなわれる。つまり、同一と見なせない場合には、下位の３次元ブロックに分割し、同一と見なせる場合は分割を停止する。そして、分割された３次元ブロックのそれぞれに含まれる画素が同一と見なせるまで分割が続けられる。図１２の例では、３次元ブロックＡ１に含まれる４×４×４個の画素の輝度が同一と見なせないので、８個の３次元ブロックＢ１〜Ｂ８に分割されている。また、分割された前記８個の３次元ブロックのうち、３次元ブロックＢ５およびＢ８のそれぞれに含まれる画素は同一と見なせないので、さらにそれぞれ８個の下位の３次元ブロックに分割されている。一方、３次元ブロックＢ１〜Ｂ４，Ｂ６，Ｂ７のそれぞれに含まれる画素は同一と見なせるので、それ以上の分割は行われない。
【０００６】
なお、分割を行うか否か（同一と見なせるか否か）の具体的な判断基準は、種々の形式が提案されているが、下記の（数１）のような簡単な条件式で表現することもできる。
【０００７】
ｍａｘ（Ｘｉ）−ｍｉｎ（Ｘｉ）＜ ｔｈ （数１）
【０００８】
ここで、Ｘｉはブロックに含まれる画素のレベル（輝度あるいは濃度）であり、ｔｈは所定の閾値である。つまり、（数１）はブロックに含まれる全ての画素のレベルが閾値ｔｈの幅に収まっていれば、分割を中止し、収まっていなければ、更に分割を続けることを意味する。
【０００９】
このように、画像信号の３次元ブロックを、その３次元ブロックに含まれる画素のレベルが全て同一であると見なせるまで分割し、その分割されたブロックの構造データとそのブロックに含まれる画素のレベルを組にしたものを画像信号として記述すれば、全ての画素について画素情報を一つ一つ記述する場合に比べて信号量を小さくできる。つまり信号圧縮が行われる訳である。
【非特許文献１】C. L. Jackins and S. L. Tanimoto ”Oct-trees and their use in representing three dimensional objects”, CGIP, vol. 14, pp. 249-270, 1980.
【非特許文献２】M. Yau and S. N. Srihari ”Recursive generation of hierarchical data structures for multidimensional digital images”, Proc. PRIP'82, pp. 485-490, 1982
【非特許文献３】D. Meagher ”Geometric modeling using octree encoding”, CGIP, vol. 19, pp. 129-147, 1982
【非特許文献４】N. Ahuja and C. Nash ”Octree representation of moving objects” CVGIP, vol. 26, pp. 207-216, 1984
【発明の開示】
【発明が解決しようとする課題】
【００１０】
八分木法を用いる画像信号の圧縮方法は、加算、減算、比較あるいはビットシフトのような単純な演算で構成されているので、ＭＰＥＧ１等に比べて計算が簡単であった。しかしながら、この方式は３次元ブロックの一部に同一と見なせない部分があると、その３次元ブロック全体を８分割するので、必要以上の分割が行われ、圧縮効率が低くなるという問題があった。
【００１１】
例えば、図１２の上位の３次元ブロックＡ１を構成する６４個の画素の内、下位の３次元ブロックＣ１、Ｃ１６に相当する２個の画素の輝度が、他の６２個の画素と大きく異なり、他の６２個の画素の輝度は同一と見なせる場合を考えてみる。このような場合でも、八分木法では最上位の３次元ブロックＡ１を８分割して、８個の中位の３次元ブロックＢ１〜Ｂ８を作成し、中位の３次元ブロックＢ５およびＢ８をさらにそれぞれ、８分割して、１６個の下位の３次元ブロックＣ１〜Ｃ１６を作成しているから、上位の３次元ブロックＡ１を中位の３次元ブロック６個、下位の３次元ブロック１６個の合計２２個に分割することになる。結局、６４個の画素を２２個のブロックにまとめた訳であり、圧縮率は１／３程度に留まる。
【００１２】
このように、八分木法を用いる画像信号の圧縮は圧縮効率が低いので、実用性に難点があった。そこで、本発明は演算の簡易化と圧縮効率の高効率化を同時に実現する画像信号の符号化方法および装置を提供することを目的とするものである。
【課題を解決するための手段】
【００１３】
本発明の画像信号の符号化方法の第１の構成は、画像信号の列を３次元ブロック化して、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割して、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する画像信号の符号化方法において、前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを連結したものを前記塊とすることを特徴とする。
【００１４】
本発明の画像信号の符号化方法の第２の構成は前記第１の構成に加えて、前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする。
【００１５】
この構成により、そこに含まれる全ての画素の画素レベルが同一と見なされる任意形状の一連のサブブロックを塊として取り扱うから、不必要な分割を回避することができるので、画像信号の圧縮率が高くなる。
【００１６】
本発明の画像信号の符号化方法の第３の構成は前記第２の構成に加えて、そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割して、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする。
【００１７】
この構成により、前記サブブロックをさらにマイクロブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割するから、画質が向上する。
【００１８】
本発明の画像信号の符号化方法の第４の構成は、前記第２または第３の構成に加えて、四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正することを特徴とする。
【００１９】
この構成により、直接比較すればリンクされないサブブロックが、リンクの繰り返しにより同一の画素の塊として扱われること回避できるので、画質が向上する。
【００２０】
本発明の画像信号の符号化方法の第５の構成は、前記第２ないし第４の構成に加えて、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする。
【００２１】
この構成により、簡単な演算で「有効／無効」を判断するので、演算時間および消費電力を節約することができる。
【００２２】
本発明の画像信号の符号化方法の第６の構成は、前記第１ないし第５の構成に加えて、前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする。
【００２３】
この構成により、３次元ブロックの分割形式が単純なので、演算が簡単になり、演算時間および消費電力を更に節約することができる。
【００２４】
本発明の画像信号の符号化装置の第１の構成は、画像信号の列を３次元ブロック化する手段と、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割する手段と、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する手段を備えた画像信号の符号化装置において、前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを集めて、前記塊とする手段を備えたことを特徴とする。
【００２５】
本発明の画像信号の符号化装置の第２の構成は前記第１の構成に加えて、前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする。
【００２６】
本発明の画像信号の符号化装置の第３の構成は、前記第２の構成に加えて、そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割する手段と、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする。
【００２７】
本発明の画像信号の符号化装置の第４の構成は、前記第２または第３の構成に加えて、四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正する手段を有することを特徴とする。
【００２８】
本発明の画像信号の符号化装置の第５の構成は、前記第２ないし第４の構成に加えて、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする。
【００２９】
本発明の画像信号の符号化装置の第６の構成は、前記第１ないし第５の構成に加えて、前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする。
【発明の効果】
【００３０】
以上説明したように、本発明は、演算の簡易化と圧縮効率の高効率化および高画質化の要求に同時に答えることができる画像信号の符号化方法および装置を提供することができる。そして、本発明は無線テレビ電話や携帯情報端末（ＰＤＡ）のようなパーソナルビデオコミュニケーションシステムに適した方法および装置として実用性が高い。
【発明を実施するための最良の形態】
【００３１】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例】
【００３２】
図１は、本発明の実施例に係る適応階層ツリー構造の概念図である。上位の３次元ブロックＨ１は画像信号の列を４×４×４画素の立方体にブロック化したものであり、３個の任意形状のサブブロックＩ１〜Ｉ３に分割される。サブブロックＩ１およびＩ２は、２×２×２画素からなる単位立方体であり、サブブロックＩ３は、６個の前記単位立方体が連結されたものである。さらに、サブブロックＩ２は３個のマイクロブロックＪ１〜Ｊ３に分割されている。マイクロブロックＪ１およびＪ３はそれぞれ２個の画素から構成され、マイクロブロックＪ２は４個の画素から構成されている。そして、サブブロックＩ１に含まれる画素の画素レベルは全て同一と見なされる。同様にサブブロックＩ３およびマイクロブロックＪ１、Ｊ２、Ｊ３にそれぞれ含まれる画素の画素レベルは全て同一と見なされる。
【００３３】
このように、前記適応階層ツリー構造においては、上位の３次元ブロックは、そこに含まれる画素の画素レベルが全て同一と見なされるまで、分割を繰り返して、何個かの任意の形状の下位の３次元ブロックに分割される。この下位の３次元ブロックの構造データと前記下位の３次元ブロックに含まれる画素の画素レベルを量子化したデータを組み合わせることによって、画像データは圧縮される。
【００３４】
これから、前記適応階層ツリーを作成するために、８個（＝２×２×２）のサブブロックから構成される立方体ブロックを、任意形状の下位のブロックに分割する手順を説明する。
【００３５】
図２および図３は、立方体ブロックの分割手順を説明する図である。図２に示すように、立方体ブロックＮは８個のサブブロックＰ（１）〜Ｐ（８）から構成されている。ここで、サブブロックＰ（１）〜Ｐ（８）の互いの関係を表示する１２本のリンクＬ１２〜Ｌ７８を仮想する。
【００３６】
リンクＬ１２、Ｌ３４、Ｌ５６およびＬ７８は、それぞれリンクＰ（１）とＰ（２）とＰ（３）とＰ（４）、Ｐ（５）とＰ（６）およびＰ（７）とＰ（８）を結ぶリンクであり、横方向リンクと呼ぶことにする。
【００３７】
リンクＬ１３、Ｌ２４、Ｌ５７およびＬ６８は、それぞれリンクＰ（１）とＰ（３）とＰ（２）とＰ（４）、Ｐ（５）とＰ（７）およびＰ（６）とＰ（８）を結ぶリンクであり、縦方向リンクと呼ぶことにする。
【００３８】
リンクＬ１５、Ｌ２６、Ｌ３７およびＬ４８は、それぞれリンクＰ（１）とＰ（５）とＰ（２）とＰ（６）、Ｐ（３）とＰ（７）およびＰ（４）とＰ（８）を結ぶリンクであり、奥行き方向リンクと呼ぶことにする。
【００３９】
さて、図３(ａ）に示すように８個のサブブロックＰ（１）〜Ｐ（８）の画素レベルが大きく異なる場合は、隣接するサブブロックＰ（１）〜Ｐ（８）のどれを組み合わせても同一と見なせるものはないから、すべてのリンクＬ１２〜Ｌ７８は「無効」（図では点線で表示している）状態にあると考える。また、サブブロックＰ（１）とサブブロックＰ（５）に含まれる画素の画素レベルが同一と見なされ、他のサブブロックのレベルが異なる場合は、図３（ｂ）に示すように、リンクＬ１５が「有効」（図では太実線で表示している）状態にあると考え、サブブロックＰ（１）とサブブロックＰ（５）を併合して、１つのブロックとして取り扱い、他の６個のサブブロックはそれぞれを独立したブロックとして取り扱う。また、全てのサブブロックＰ（１）〜Ｐ（８）のレベルが同一と見なせる場合は、図３（ｃ）に示すように、すべてのリンクＬ１２〜Ｌ７８が「有効」状態にあると考え、８個のサブブロックＰ（１）〜Ｐ（８）を全て併合して、１つのブロックとして取り扱う。
【００４０】
このように、８個のサブブロックＰ（１）〜Ｐ（８）の中から併合可能な組み合わせ、すなわち、そこに含まれる全ての画素の画素レベルが同一とみなせるようなサブブロックＰ（１）〜Ｐ（８）の組み合わせを選び出して、サブブロックの塊を作成する問題は、１２個のリンクＬ１２〜Ｌ７８のそれぞれについて、「有効」または「無効」を決定する問題に帰着できる。なお、８個のサブブロックＰ（１）〜Ｐ（８）の併合のパターンは、２の１２乗通り、すなわち４０９６通りあることになるが、後述する「併合補正」の処理によって、不合理な組み合わせを排除すると、本発明の方法で選択可能な組み合わせは９８４通りになる。
【００４１】
そこで、１２個のリンクＬ１２〜Ｌ７８のそれぞれについて、「有効」または「無効」を決定する手順を、図４〜図８を参照しながら説明する。
【００４２】
図４は、８個のサブブロックＰ（１）〜Ｐ（８）の併合の可否を決定する概略手順を説明する図である。この概略手順は、横方向リンクの有効・無効を検討して横方向に並ぶサブブロック同士の併合の可能性を判断する第１ステップ、縦方向リンクの有効・無効を検討して縦方向に並ぶサブブロック同士の併合の可能性を判断する第２ステップ、前記第１ステップで判断した横方向のサブブロックの併合と前記第２ステップで判断した縦方向の併合の間に不合理が生じた場合に前記縦方向の併合の判断を取り消す第３ステップ、奥行き方向リンクの有効・無効を検討して奥行き方向に並ぶサブブロック同士の併合の可能性を判断する第４ステップ、および前記第１ステップないし前記第３ステップで判断したサブブロックの横方向および縦方向の併合と前記第４ステップで判断したサブブロックの奥行き方向の併合の間に不合理が生じた場合に前記奥行き方向の併合の判断を取り消す第５ステップに大きく分けられる。以下、第１ステップから順を追って、１２個のリンクＬ１２〜Ｌ７８の「有効／「無効」を決定する手順を説明する。
【００４３】
（第１ステップ）
符号化の対象となる画像信号の列はビデオメモリ１に記憶されている。このビデオメモリ１から画像信号の列を逐次読み出して、前記画像信号の列をサブブロックＰ（１）〜Ｐ（８）からなる３次元ブロックにして、パイプラインレジスタ２に記憶する。次に、サブブロックＰ（１）〜Ｐ（８）に属する画素の画素レベルをパイプラインレジスタ２から読み出し、領域併合判断モジュール３１〜３４に入力する。領域併合判断モジュール３１はサブブロックＰ（１）に属する画素の画素レベルとサブブロックＰ（２）に属する画素の画素レベルを比較してサブブロックＰ（１）とサブブロックＰ（２）の併合の可否を判断するモジュールである。同様に、領域併合判断モジュール３２はサブブロックＰ（３）とサブブロックＰ（４）の、領域併合判断モジュール３３はサブブロックＰ（５）とサブブロックＰ（６）の、領域併合判断モジュール３４はサブブロックＰ（７）とサブブロックＰ（８）の併合の可否をそれぞれ判断するモジュールである。
【００４４】
（領域併合判断モジュール）
図５は、領域併合判断モジュールの入出力を模式化した図である。なお、領域併合判断モジュール３１〜３４および後述する領域併合判断モジュール５１〜５４、領域併合判断モジュール８１〜８４の処理は全く同一である。
【００４５】
領域併合判断モジュールの入力は、Ｉａｍａｘ，Ｉａｍｉｎ，Ｉｂｍａｘ，ＩｂｍｉｎおよびＴｈの５種である。ここで、添え字ａ，ｂは併合判断の対象となるサブブロックＰ（１）〜Ｐ（８）の番号を示している。すなわち、Ｉａｍａｘ，Ｉａｍｉｎは領域併合判断の対象となる一方の領域（サブブロックＰ（ａ））に属する画素の画素レベルの最大値と最小値であり、Ｉｂｍａｘ，Ｉｂｍｉｎは他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの最大値と最小値である。また、Ｔｈは画素レベルを同一と見なすか否か（つまり、領域併合の可否）を判断するための閾値である。
【００４６】
領域併合判断モジュール２１の出力は、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，ＯｂｍｉｎおよびＬｉｎｋの５種である。Ｏａｍａｘ，Ｏａｍｉｎは前記一方の領域（サブブロックＰ（ａ））に属する画素の画素レベルの代表値であり、Ｏｂｍａｘ，Ｏｂｍｉｎは前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの代表値である。Ｌｉｎｋは領域併合の可否を表示するためのフラグである。
【００４７】
領域併合が成されない場合は、代表値Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎはそれぞれ最大値、最小値Ｉａｍａｘ，Ｉａｍｉｎ，Ｉｂｍａｘ，Ｉｂｍｉｎに等しい。
【００４８】
領域併合が成される場合は、ＯａｍａｘおよびＯｂｍａｘは、前記一方の領域（サブブロックＰ（ａ））または前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの最大値（つまり、ＩａｍａｘまたはＩｂｍａｘのいずれか大きい方の値）に等しくなり、ＯａｍｉｎおよびＯｂｍｉｎは前記一方の領域（サブブロックＰ（ａ））または前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの最小値（つまり、ＩａｍｉｎまたはＩｂｍｉｎのいずれか小さい方の値）に等しくなる。領域併合が成される場合は前記一方の領域（サブブロックＰ（ａ））および前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルが同一であると見なされるから、画素レベルの代表値も統一されるのである。
【００４９】
次に、領域併合の可否の判断の手順と、代表値Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎを決定する手順を詳述する。
【００５０】
まず、下記の（数２）に示すように、ＩａｍａｘとＩｂｍａｘの値を比較していずれか大きい値をＩｍａｘとする。つまりＩｍａｘはサブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルの最大値である。
【００５１】
Ｉｍａｘ＝ｍａｘ（Ｉａｍａｘ，Ｉｂｍａｘ） （数２）
【００５２】
つぎに、（数３）に示すように、ＩａｍｉｎとＩｂｍｉｎの値を比較していずれか小さい値をＩｍｉｎとする。つまりＩｍｉｎはサブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルの最小値である。
【００５３】
Ｉｍｉｎ＝ｍｉｎ（Ｉａｍｉｎ，Ｉｂｍｉｎ） （数３）
【００５４】
さらに、（数４）に示すように、ＩｍａｘとＩｍｉｎの差Ｄ、すなわち、サブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルの変動幅（ダイナミックレンジ）を求める。
【００５５】
Ｄ＝Ｉｍａｘ−Ｉｍｉｎ （数４）
【００５６】
次に、変動幅Ｄと閾値Ｔｈを比較する。変動幅Ｄが閾値Ｔｈより小さければ、サブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルは同一と見なせるから、「併合は可」と判断され、リンクＬａｂは「有効」とされる。この時、フラグＬｉｎｋに「１」を立てる。逆に変動幅Ｄが閾値Ｔｈｒｅｓｈｏｌｄと等しいか、より大きければ、サブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルは同一と見なせないから、「併合は不可」と判断され、リンクＬａｂは「無効」とされる。この時、フラグＬｉｎｋに「０」を立てる。
【００５７】
以後の説明では、リンクＬａｂのフラグＬｉｎｋの値を単にＬａｂと表記することにする。つまり、Ｌａｂ＝１ならば、リンクＬａｂは「有効」であり、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の「併合は可」とされていることを意味し、Ｌａｂ＝０ならば、リンクＬａｂは「無効」であり、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の「併合は不可」とされていることを意味する。
【００５８】
最後に、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎに（表１）に示す値を代入する。つまり、Ｌａｂ＝０の時は、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の併合は不可だから、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎの値は元のままであり、Ｉａｍａｘ，Ｉａｍｉｎ，Ｉｂｍａｘ，Ｉｂｍｉｎがそれぞれ代入される。Ｌａｂ＝１の時は、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の併合は可だから、ＯａｍａｘとＯｂｍａｘはＩｍａｘに統一され、ＯａｍｉｎとＯａｍｉｎはＩｍｉｎに統一される。これらの値を出力して、領域併合判断モジュールの処理は終わる。
【００５９】
【表１】
【００６０】
同様に、領域併合判断モジュール３２〜３４もそれぞれの判断対象のサブブロックに対して、同様の処理を行う。なお、領域併合判断モジュール３１〜３４の処理は互いに独立しているから、パラレルに処理することも出来るが、シリアルに処理しても良い。また、領域併合判断モジュール３１〜３４の出力はパイプラインレジスタ４に記憶される。
【００６１】
（第２ステップ）
パイプラインレジスタ４から前記第１ステップの処理後のサブブロックＰ（１）〜Ｐ（８）の画素レベルの最大値Ｉ１ｍａｘ〜Ｉ８ｍａｘおよび最小値Ｉ１ｍｉｎ〜Ｉ８ｍｉｎを読み出して、領域併合判断モジュール５１〜５４に入力する。領域併合判断モジュール５１はサブブロックＰ（１）とサブブロックＰ（３）の併合の可否を判断するモジュールである。同様に、領域併合判断モジュール５２はサブブロックＰ（２）とサブブロックＰ（４）の、領域併合判断モジュール５３はサブブロックＰ（５）とサブブロックＰ（７）の、領域併合判断モジュール５４はサブブロックＰ（６）とサブブロックＰ（８）の併合の可否をそれぞれ判断するモジュールである。
【００６２】
領域併合判断モジュール５１〜５４では、前述の領域併合判断モジュール３１〜３４と同様の処理が行われ、サブブロックＰ（１）〜Ｐ（８）の縦方向の併合の可否が判断される。領域併合判断モジュール４１〜４４の処理も互いに独立しているから、パラレルに処理することも出来るが、シリアルに処理しても良い。
【００６３】
（第３ステップ）
前記第２ステップの処理結果は、４併合補正モジュール６１、６２に入力されて処理される。４併合補正モジュール６１はサブブロックＰ（１）〜Ｐ（４）の横方向併合と縦方向併合の不合理を補正するモジュールであり、４併合補正モジュール６２はサブブロックＰ（５）〜Ｐ（８）の横方向併合と縦方向併合の不合理を補正するモジュールである。
【００６４】
４併合補正モジュール６１、６２の処理内容を説明する前に、「併合補正」の概念を説明する。
【００６５】
図６は、「併合補正」の概念を説明する図である。まず、サブブロックＰ（１）〜Ｐ（４）が与えられて（図６（ａ））、横方向併合を検討した結果、サブブロックＰ（１）とＰ（２）は併合可（リンクＬ１２は「有効」）であるが、サブブロックＰ（３）とＰ（４）は併合不可（リンクＬ３４は「無効」）となった（図６（ｂ））。次に縦方向併合を検討すると、サブブロックＰ（１）とＰ（３）は併合可（リンクＬ１３は「有効」）であり、サブブロックＰ（２）とＰ（４）も併合可（リンクＬ２４は「有効」）となった（図６（ｃ））。このように、四辺形を構成する４つのリンクのうち３つのリンクが「有効」となる場合がある。
【００６６】
この場合、サブブロックＰ（１）とＰ（２）が併合されるとともに、サブブロックＰ（１）とＰ（３）、サブブロックＰ（２）とＰ（４）が併合されるので、結局、サブブロックＰ（１）〜Ｐ（４）が全て併合され１つのブロックとして取り扱われることになる。前述したように、サブブロックＰ（３）とＰ（４）を直接比較すると、画素レベルの差が大きいので併合不可とされるにも関わらず、併合を繰り返した結果、同一の画素レベルに統一されてしまう訳である。このような不合理を放置すると、本来、その画面に存在する画素レベルの高低が消されてしまうので、画質が低下する場合がある。
【００６７】
そこで、４個のサブブロックを結ぶ４本のリンクの内、３本が「有効」で１本が「無効」とされた時に、「有効」とされた前記３本のリンクのいずれか１本を「無効」として、そのリンクで結合されるサブブロックの併合を行わないことにした。この処理を本明細書では「併合補正」と呼ぶことにする。
【００６８】
さて、３本のリンクの中から「無効」にする１本を選ぶ方法は各種考えられる。例えば、３本のリンクの変動幅（ダイナミックレンジ）を比較して、変動幅の一番大きいリンクを「無効」にするようにすれば、画素レベルの変化をより忠実に再現できる。しかし、本実施例では計算の簡易化のために、リンクの添え字の番号の古いものを「無効」にすることにしたので、リンクＬ２４を「無効」にした（図６（ｄ））。
【００６９】
（４併合補正モジュール）
図７は、４併合補正モジュール６１、６２の入出力を模式化した図である。なお、４併合補正モジュール６１および４併合補正モジュール６２の処理は全く同一である。
【００７０】
４併合補正モジュール６１，６２の入力は、Ｉａｍａｘ，Ｉａｍｉｎ，Jａｍａｘ，Jａｍｉｎ，Ｉｂｍａｘ，Ｉｂｍｉｎ，Jｂｍａｘ，Ｊｂｍｉｎ，Ｉｃｍａｘ，Ｉｃｍｉｎ，Ｊｃｍａｘ，Ｊｃｍｉｎ，Ｉｄｍａｘ，Ｉｄｍｉｎ，Ｊｄｍａｘ，Ｊｄｍｉｎ，およびＬａｂ，Ｌｃｄ，Ｌａｃ，Ｌｂｄの２０種である。添え字ａ，ｂ，ｃ，ｄは４併合補正の対象であるサブブロックＰ（１）〜Ｐ（８）の番号を示している。Ｉａｍａｘ，ＩａｍｉｎはサブブロックＰ（ａ）に属する画素の画素レベルの代表値であって、第２ステップ終了後つまり縦方向の領域併合判断モジュール５１〜５４の処理後の値である。また、Jａｍａｘ，JａｍｉｎはサブブロックＰ（ａ）に属する画素の画素レベルの代表値であって、第１ステップ終了後つまり横方向の領域併合判断モジュール３１〜３４の処理後の値である。同様に、Ｉｂｍａｘ〜ＩｄｍｉｎはサブブロックＰ（ｂ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値であって、第２ステップ終了後の値である。また、Jｂｍａｘ，JｄｍｉｎはサブブロックＰ（ｂ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値であって、第１ステップ終了後の値である。
【００７１】
４併合補正モジュールの６１，６２の出力は、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎ，Ｏｃｍａｘ，Ｏｃｍｉｎ，Ｏｄｍａｘ，ＯｄｍｉｎおよびＬ’ａｃ，Ｌ’ｂｄの１０種である。添え字ａ，ｂ，ｃ，ｄは４併合補正の対象であるサブブロックＰ（１）〜Ｐ（８）の番号を示している。Ｏａｍａｘ〜ＯｄｍｉｎはサブブロックＰ（ｂ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値である。また、Ｌ’ａｃ，Ｌ’ｂｄはサブブロックＰ（ａ），Ｐ（ｃ）間およびＰ（ｂ），Ｐ（ｄ）間の併合の可否を表示するフラグＬｉｎｋである。
【００７２】
図８は、４併合補正の規則を説明する図である。４併合補正モジュール６１、６２にフラグＬａｂ，Ｌｃｄ，Ｌａｃ，Ｌｂｄが入力されると、この規則にしたがって、縦方向リンクのフラグＬａｃおよびＬｂｄの値は、Ｌ’ａｃ，Ｌ’ｂｄに変更される。
【００７３】
図８に示すように、サブブロックＰ（a）〜Ｐ（b）について４併合補正が必要となる場合は下記のパターン１〜４の４通りの場合がある。
（パターン１)
横方向リンクＬａｂが「無効」、横方向リンクＬｃｄ、縦方向リンクＬａｃおよび縦方向リンクＬｂｄが「有効」（Ｌａｂ＝０、Ｌｃｄ＝Ｌａｃ＝Ｌｂｄ＝１）の場合は、縦方向リンクＬａｃをそのまま（Ｌ’ａｃ＝１）にして、縦方向リンクＬｂｄを補正して「無効」（Ｌ’ｂｄ＝０）にする。
（パターン２）
横方向リンクＬａｂが「有効」で、横方向リンクＬｃｄが「無効」、縦方向リンクＬａｃおよび縦方向リンクＬｂｄが「有効」（Ｌａｂ＝１、Ｌｃｄ＝０、Ｌａｃ＝Ｌｂｄ＝１）の場合は、縦方向リンクＬａｃをそのまま（Ｌ’ａｃ＝１）にして、縦方向リンクＬｂｄを補正して「無効」（Ｌ’ｂｄ＝０）にする。
（パターン３)
横方向リンクＬａｂ、Ｌｃｄが「有効」で、縦方向リンクＬａｃが「無効」、縦方向リンクＬｂｄが「有効」（Ｌａｂ＝Ｌｃｄ＝１、Ｌａｃ＝０、Ｌｂｄ＝１）の場合は、縦方向リンクＬａｃをそのまま（Ｌ’ａｃ＝０）にして、縦方向リンクＬｂｄを補正して「無効」（Ｌ’ｂｄ＝０）にする。
（パターン４)
横方向リンクＬａｂ、横方向リンクＬｃｄおよび縦方向リンクＬａｃが「有効」で、縦方向リンクＬｂｄが「無効」（Ｌａｂ＝Ｌｃｄ＝Ｌａｃ＝１、Ｌｂｄ＝０）の場合は、縦方向リンクＬａｃを補正（Ｌ’ａｃ＝０）して、縦方向リンクＬｂｄをそのまま（Ｌ’ｂｄ＝０）にする。
以上のパターン１〜４に当てはまらない場合は、補正は行わない。つまり、縦方向リンクＬａｃおよび縦方向リンクＬｂｄともにそのまま（Ｌ’ａｃ＝Ｌａｃ、Ｌ’ｂｄ＝Ｌｂｄ）にする。
【００７４】
以上説明した補正の規則を纏めると、表２のようになる。
【００７５】
【表２】
【００７６】
縦方向リンクＬａｃおよび縦方向リンクＬｂｄの補正が終わったら、各サブブロックＰ（ａ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎｂｍｉｎ，Ｏｃｍａｘ，Ｏｃｍｉｎ，Ｏｄｍａｘ，Ｏｄｍｉｎを、表３および表４に示す規則に従って決定する。
【００７７】
【表３】
【００７８】
【表４】
【００７９】
以下に、表３，表４の規則を簡単に説明する。
ＣＡＳＥ１：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンク、縦方向リンクの両方が「無効」だから、サブブロックＰ（ａ）、サブブロックＰ（ｂ）に属する画素の画素レベルの代表値は、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）についての横方向の領域併合判断後の値が採用される
【００８０】
ＣＡＳＥ２：サブブロックＰ（ａ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には横方向についての領域併合判断後の値が採用される。サブブロックＰ（ｂ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８１】
ＣＡＳＥ３：サブブロックＰ（ａ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合判断後の値が採用される。サブブロックＰ（ｂ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には横方向についての領域併合判断後の値が採用される。
【００８２】
ＣＡＳＥ４：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合判断後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８３】
ＣＡＳＥ５：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンクが「有効」であり、縦方向リンクが「無効」だから、画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｂ）についての横方向の領域併合判断後の値が採用される。
【００８４】
ＣＡＳＥ６：サブブロックＰ（ａ）については、横方向リンクが「有効」、縦方向リンクが「無効」であり、サブブロックＰ（ｂ）については、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ａ）、サブブロックＰ（ｂ）およびサブブロック（ｄ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の代表値はサブブロックＰ（ｂ）とサブブロックＰ（ｄ）についての縦方向の領域併合判断後の代表値が採用される。
【００８５】
ＣＡＳＥ７：サブブロックＰ（ａ）については、横方向リンクおよび縦方向リンクが「有効」であり、サブブロックＰ（ｂ）については、横方向リンクが「有効」、縦方向リンクが「無効」だから、サブブロックＰ（ａ）、サブブロックＰ（ｂ）およびサブブロック（ｃ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の代表値はサブブロックＰ（ａ）とサブブロックＰ（ｃ）についての縦方向の領域併合判断後の代表値が採用される。
【００８６】
ＣＡＳＥ８：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）ついての縦方向の領域併合後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８７】
ＣＡＳＥ９：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンク、縦方向リンクの両方が「無効」だから、サブブロックＰ（ｃ）、サブブロックＰ（ｄ）に属する画素の画素レベルの代表値は、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）についての横方向の領域併合判断後の値が採用される。
【００８８】
ＣＡＳＥ１０：サブブロックＰ（ｃ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には。サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）についての横方向の領域併合判断後の値が採用される。サブブロックＰ（ｄ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８９】
ＣＡＳＥ１１：サブブロックＰ（ｃ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合判断後の値が採用される。サブブロックＰ（ｄ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には、サブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００９０】
ＣＡＳＥ１２：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の画素レベルの代表値には、サブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００９１】
ＣＡＳＥ１３：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンクが「有効」であり、縦方向リンクが「無効」だから、画素レベルの代表値には、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）についての横方向の領域併合判断後の値が採用される。
【００９２】
ＣＡＳＥ１４：サブブロックＰ（ｃ）については、横方向リンクが「有効」、縦方向リンクが「無効」であり、サブブロックＰ（ｄ）については、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ｃ）、サブブロックＰ（ｄ）およびサブブロック（ｂ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の代表値はサブブロックＰ（ｂ）とサブブロックＰ（ｄ）についての縦方向の領域併合判断後の代表値が採用される。
【００９３】
ＣＡＳＥ１５：サブブロックＰ（ｃ）については、横方向リンクおよび縦方向リンクが「有効」であり、サブブロックＰ（ｄ）については、横方向リンクが「有効」、縦方向リンクが「無効」だから、サブブロックＰ（ｃ）、サブブロックＰ（ｄ）およびサブブロック（ａ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の代表値はサブブロックＰ（ａ）とサブブロックＰ（ｃ）についての縦方向の領域併合判断後の代表値が採用される。
【００９４】
ＣＡＳＥ１６：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の画素レベルの代表値には、サブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００９５】
４併合補正モジュール６１および６２の処理結果を、パイプラインレジスタ７に書き込んで、第３ステップは終了する。なお、４併合補正モジュール６１および６２は互いに独立しているから、パラレルに処理しても、シリアルに処理してもよい。
【００９６】
（第４ステップ）
第４ステップでは奥行き方向リンクについて、領域併合判断を行うため、パイプラインレジスタ７から第３ステップの処理結果を読み出して、領域併合判断モジュール８１〜８４に入力する。領域併合判断モジュール８１はサブブロックＰ（１）とサブブロックＰ（５）の併合の可否を判断するモジュールである。また、領域併合判断モジュール８２はサブブロックＰ（３）とサブブロックＰ（７）の、領域併合判断モジュール８３はサブブロックＰ（２）とサブブロックＰ（６）の、領域併合判断モジュール８４はサブブロックＰ（４）とサブブロックＰ（８）の併合の可否をそれぞれ判断するモジュールである。
【００９７】
領域併合判断モジュール８１〜８４では、領域併合判断モジュール３１〜３４および領域併合判断モジュール５１〜５４と同様に、各サブブロックＰ（１）〜Ｐ（８）に含まれる画素の画素レベルを比較して、併合の可否を判断する。
【００９８】
なお、領域併合判断モジュール８１〜８４は互いに独立しているので、パラレル処理、シリアル処理のいずれでもよい。
【００９９】
（第５ステップ）
前記第４ステップの処理結果は、８併合補正モジュール９１に入力されて処理される。８併合補正モジュール９１はサブブロックＰ（１）〜Ｐ（８）の横方向併合と奥行き縦方向併合の不合理および横方向併合と奥行き縦方向併合の不合理を補正するモジュールである。８併合補正モジュール９１は４併合補正モジュール６１，６２と同様に、４個のサブブロックを結ぶ４本のリンクの内、３本が「有効」で１本が「無効」とされた時に、「有効」とされた前記３本のリンクのいずれか１本を「無効」にする処理を行うモジュールであり、次の６組のサブブロックの組、（Ｐ（１）、Ｐ（２）、Ｐ（５）、Ｐ（６））、（Ｐ（１）、Ｐ（３）、Ｐ（５）、Ｐ（７））、（（Ｐ（２）、Ｐ（４）、Ｐ（６）、Ｐ（８））、（Ｐ（３）、Ｐ（４）、Ｐ（７）、Ｐ（８））、（Ｐ（１）、Ｐ（４）、Ｐ（５）、Ｐ（８））および（Ｐ（２）、Ｐ（３）、Ｐ（６）、Ｐ（７））について、奥行き方向のリンクの補正を検討し、その結果を重ね合わせて、前記奥行き方向のリンクの「有効／無効」を決定する。以下に、この補正の手順を詳述する。
【０１００】
サブブロックの組、（Ｐ（１）、Ｐ（２）、Ｐ（５）、Ｐ（６））については、リンクＬ１２，Ｌ５６，Ｌ１５，Ｌ２６の「有効／無効」を表示するフラグＬ１２，Ｌ５６，Ｌ１５，Ｌ２６の組み合わせを表５に示す規則に当てはめて、Ｌ（１）１５，Ｌ（１）２６の値を求める。
【０１０１】
【表５】
【０１０２】
サブブロックの組、（Ｐ（１）、Ｐ（３）、Ｐ（５）、Ｐ（７））については、フラグＬ１３，Ｌ５７，Ｌ１５，Ｌ３７の組み合わせを表６に示す規則に当てはめて、Ｌ（２）１５，Ｌ（１）３７の値を求める。
【０１０３】
【表６】
【０１０４】
サブブロックの組、（Ｐ（２）、Ｐ（４）、Ｐ（６）、Ｐ（８））については、フラグＬ２４，Ｌ６８，Ｌ２６，Ｌ４８の組み合わせを表７に示す規則に当てはめて、Ｌ（２）２６，Ｌ（１）４８の値を求める。
【０１０５】
【表７】
【０１０６】
サブブロックの組、（Ｐ（３）、Ｐ（４）、Ｐ（７）、Ｐ（８））については、フラグＬ３４，Ｌ７８，Ｌ３７，Ｌ４８の組み合わせを表８に示す規則に当てはめて、Ｌ（２）３７，Ｌ（２）４８の値を求める。
【０１０７】
【表８】
【０１０８】
サブブロックの組、（Ｐ（１）、Ｐ（４）、Ｐ（５）、Ｐ（８））については、フラグＬ１４，Ｌ５８，Ｌ１５，Ｌ４８の組み合わせを表９に示す規則に当てはめて、Ｌ（３）１５，Ｌ（３）４８の値を求める。
【０１０９】
【表９】
【０１１０】
なお、フラグＬ１４およびＬ５８は、サブブロックＰ（１）とＰ（４）およびＰ（５）とＰ（８）の併合の有無を表示するフラグであり、（数５）で与えられる。
【０１１１】
Ｌ１４＝（Ｌ１２ａｎｄＬ２４）ｏｒ（Ｌ１３ａｎｄＬ３４）
Ｌ５８＝（Ｌ５６ａｎｄＬ６８）ｏｒ（Ｌ５７ａｎｄＬ７８） （数５）
【０１１２】
サブブロックの組、（Ｐ（２）、Ｐ（３）、Ｐ（６）、Ｐ（７））については、フラグＬ２３，Ｌ６７，Ｌ２６，Ｌ３７の組み合わせを表９に示す規則に当てはめて、フラグＬ２６，Ｌ３７の値をＬ（３）２６，Ｌ（３）３７に変更する。
【０１１３】
【表９】
【０１１４】
なお、フラグＬ２３およびＬ６７は、サブブロックＰ（２）とＰ（３）およびＰ（６）とＰ（７）の併合の有無を表示するフラグであり、下記の（数６）で与えられる。
【０１１５】
Ｌ２３＝（Ｌ１２ａｎｄＬ１３）ｏｒ（Ｌ２４ａｎｄＬ３４）
Ｌ６７＝（Ｌ５６ａｎｄＬ５７）ｏｒ（Ｌ６８ａｎｄＬ７８） （数６）
【０１１６】
これで、サブブロックＰ（１）〜Ｐ（８）の６通りの組み合わせについてのフラグＬ１５、Ｌ２６、Ｌ３７、Ｌ４８の補正値Ｌ（１）１５〜Ｌ（３）４８が得られた。あるリンクについて、前記６通りの組み合わせの少なくとも１つで補正する必要があれば、そのリンクを補正する必要があるので、（数７）に示すように補正値Ｌ（１）１５〜Ｌ（３）４８の論理積をＬ’１５、Ｌ’２６、Ｌ’３７、Ｌ’４８とし、フラグＬ１５、Ｌ２６、Ｌ３７、Ｌ４８をこれらと置き換える。
【０１１７】
Ｌ’１５＝Ｌ（１）１５ａｎｄＬ（２）１５ａｎｄＬ（３）１５
Ｌ’２６＝Ｌ（１）２６ａｎｄＬ（２）２６ａｎｄＬ（３）２６
Ｌ’３７＝Ｌ（１）３７ａｎｄＬ（２）３７ａｎｄＬ（３）３７
Ｌ’４８＝Ｌ（１）４８ａｎｄＬ（２）４８ａｎｄＬ（３）４８ （数７）
【０１１８】
以上の演算結果をパイプラインレジスタ１０に書き込んで、第５ステップは終了する。
【０１１９】
以上、第１ステップから第５ステップの処理を行うことで、１２本のリンクＬ１２〜Ｌ７８の「有効／無効」が決定される。８個のサブブロックからなるブロックは、幾つかの「有効」なリンクで結合されたサブブロックの「塊」に分割される。また、サブブロックに含まれる画素の画素レベルは同一と見なせない場合は、そのサブブロックについて、第１ステップから第５ステップの処理を行って、「そこに含まれる全ての画素の画素レベルが同一と見なせる」マイクロブロックの「塊」に分割する。これを繰り返して、立体ブロックＮ全体を、「そこに含まれる全ての画素の画素レベルが同一と見なせる塊」に分割する。そして、この「塊」に含まれる画素の画素レベルを量子化して、量子化した画素データと「塊」の構造データを組にして、ハフマン符号の手法によって可変長符号に変換する。
【０１２０】
以上、本発明の実施例を、画像信号の符号化方法として説明してきたが、本発明の方法を実施する装置は、コンピュータに本発明の方法をプログラムの形で組み込むことにより簡単に構成できる。また、図４に示したような各モジュールに機能を分割して専用のハードウェアを用意すれば、演算をさらに高速化することができる。
【０１２１】
最後に、本発明の符号化方法の性能を従来の方法と比較して示す。なお、すべての比較は、ビデオフレームの輝度成分（Ｙ）について行っているが、圧縮率については、輝度成分（Ｙ）と２つの色差成分（Ｃｒ、Ｃｂ）を含んでいる。また、客観的比較を行うために、本発明の方法と八分木法については、同一の量子化のステップを使用した。量子化段階のハフマン符号とツリー構造情報は各符号化手法のそれぞれについて作成した。
【０１２２】
図９に、原画像と本発明の方法によって符号化した画像データによる画像、および従来の方法による画像を示す。図９（ａ）は、原画像であり、図９（ｂ）は、ＭＰＥＧ４ ＴＭ５による画像、図９（ｃ）は、本発明の方法による画像、図９（ｄ）は、八分木法による画像である、比較のために、圧縮率は同レベルに揃えている。図から解るように、本発明の方法による画像の画質は、ＭＰＥＧ４ ＴＭ５による画像に比べて遜色がなく、八分木法による画像に比べると遙かに優れている。
【０１２３】
表１０は、各方法による演算数の比較を示す表である。この表から、本発明の方法の操作数はＭＰＥＧ４の約６分の１であり、バッテリーの負担が小さいことが解る。
【０１２４】
【表１０】
【０１２５】
表１１は、各方法による符号化に要する時間を示している。本発明の符号化手法および八分木法による符号化時間は、ＭＰＥＧ４の１０分の１以下である。なお、ここに示した時間は、ペンティアム４（登録商標） ２．４ＧＨｚパーソナルコンピュータ上で動作させた場合であり、ＯＳはウィンドウズＸＰ（登録商標）である。
【０１２６】
【表１１】
【０１２７】
図１０は、各方法について、圧縮率と画質の関係を表示するグラフであり、画質はピーク信号−ノイズ比（ＰＳＮＲ）で表示している。図中で「ＡＤＡＰＴＩＶＥ」と表示した太い実線が本発明の実験結果を示し、「ＭＰＥＧ４」と表示した細い実線はＭＰＥＧ４ ＴＭ５による実験結果を、「ＯＣＴＲＥＥ」と表示した破線は八分木法による実験結果をそれぞれ示している。圧縮率０．５ｂｉｔ／ｐｅｌにおいて、本発明の符号化手法のＰＳＮＲはＭＰＥＧ４に対して約０．６ｄＢ小さいが、八分木法に対しては約１．２ｄＢ優れている。
【０１２８】
図１１は、各方法について、圧縮率０．５ｂｉｔ／ｐｅｌの条件の下で各フレームの画質を表示するグラフである。図中で「ＡＤＡＰＴＩＶＥ」と表示した太い実線が本発明の実験結果を示し、「ＭＰＥＧ４」と表示した細い実線はＭＰＥＧ４ ＴＭ５による実験結果を、「ＯＣＴＲＥＥ」と表示した破線は八分木法による実験結果をそれぞれ示している。ＰＳＮＲの傾向は図１０と同様に、ＭＰＥＧ４、本発明の方法、八分木法の順だが、ＰＳＮＲの分布は本発明の方法が３者の中で最も狭い。
【０１２９】
なお、本実施例では、３次元ブロック化された画像信号をサブブロックに分割するとともに、サブブロックを連結する仮想的な「リンク」という概念を導入して、「リンク」で連結されたサブブロックを、そこに含まれるすべての画素の画素レベルを同一と見なし得る画像信号の塊として取り扱うことにより、画像信号を符号化圧縮する方法および装置を示したが、本発明は「リンク」を用いるものに限られるものではない。３次元ブロック化された画像信号をそこに含まれるすべての画素の画素レベルを同一と見なし得る任意形状のサブブロックの塊に分割する画像信号の符号化方法は、本発明の技術的範囲に含まれる。
【図面の簡単な説明】
【０１３０】
【図１】本発明の実施例に係る適応階層ツリー構造の概念図である。
【図２】立方体ブロックの分割手順を説明する図である。
【図３】立方体ブロックの分割手順を説明する図である。
【図４】８個のサブブロックの併合の可否を決定する概略手順を説明する図である。
【図５】領域併合判断モジュールの入出力を模式化した図である。
【図６】併合補正の概念を説明する図である。
【図７】４併合補正モジュールの入出力を模式化した図である。
【図８】４併合補正の規則を説明する図である。
【図９】原画像、本発明の方法による画像、および従来の方法による画像の例である。
【図１０】圧縮率と画質の関係を表示するグラフである。
【図１１】各フレームの画質を表示するグラフである。
【図１２】八分木法による階層ツリー構造の概念図である。
【符号の説明】
【０１３１】
１ ビデオメモリ
２ パイプラインレジスタ
３１〜３４ 領域併合判断モジュール
４ パイプラインレジスタ
５１〜５４ 領域併合判断モジュール
６１，６２ ４併合補正モジュール
７ パイプラインレジスタ
８１〜８４ 領域併合判断モジュール
９１ ８併合補正モジュール
１０ パイプラインレジスタ
【技術分野】
【０００１】
本発明は、画像信号を符号化して、画像信号を圧縮する方法および装置に関するものである。
【背景技術】
【０００２】
例えば、無線テレビ電話や携帯情報端末（ＰＤＡ）のようなパーソナルビデオコミュニケーションシステムが急速に普及しつつある。パーソナルビデオコミュニケーションシステムにおいては、画像信号の符号化による信号圧縮は最も重要な技術のひとつである。現在、ＭＰＥＧ１，ＭＰＥＧ２，ＭＰＥＧ４，Ｈ．２６１あるいはＨ．２６３などの画像信号の符号化方式がよく知られている。しかし、これらの符号化方式は、符号化および復号化の計算が複雑で手間がかかるで、電池のエネルギー消費量が大きく、ＰＤＡによる通信には不都合である。
【０００３】
この問題を解決するために、３次元階層ツリー構造の一種である八分木法を用いて、３次元画像や動画の信号圧縮を行うことが提案されている（非特許文献１〜４）。
【０００４】
八分木法を用いる画像信号の圧縮方法は、概略、次のようなものである。
図１２は八分木法による階層ツリー構造の概念図である。上位の３次元ブロックＡ１は画像信号の列を４×４×４画素にブロック化したものであり、８個の中位の３次元ブロックＢ１〜Ｂ８に分割され、前記８個の中位の３次元ブロックＢ１〜Ｂ８のうち、２個の３次元ブロックＢ５およびＢ８はそれぞれ更に下位の３次元ブロックＣ１〜Ｃ８および３次元ブロックＣ９〜Ｃ１６に分割される。
【０００５】
３次元ブロックの分割を行うか否かの判断は、ある階層の３次元ブロックに含まれる画素が同一と見なせることを基準におこなわれる。つまり、同一と見なせない場合には、下位の３次元ブロックに分割し、同一と見なせる場合は分割を停止する。そして、分割された３次元ブロックのそれぞれに含まれる画素が同一と見なせるまで分割が続けられる。図１２の例では、３次元ブロックＡ１に含まれる４×４×４個の画素の輝度が同一と見なせないので、８個の３次元ブロックＢ１〜Ｂ８に分割されている。また、分割された前記８個の３次元ブロックのうち、３次元ブロックＢ５およびＢ８のそれぞれに含まれる画素は同一と見なせないので、さらにそれぞれ８個の下位の３次元ブロックに分割されている。一方、３次元ブロックＢ１〜Ｂ４，Ｂ６，Ｂ７のそれぞれに含まれる画素は同一と見なせるので、それ以上の分割は行われない。
【０００６】
なお、分割を行うか否か（同一と見なせるか否か）の具体的な判断基準は、種々の形式が提案されているが、下記の（数１）のような簡単な条件式で表現することもできる。
【０００７】
ｍａｘ（Ｘｉ）−ｍｉｎ（Ｘｉ）＜ ｔｈ （数１）
【０００８】
ここで、Ｘｉはブロックに含まれる画素のレベル（輝度あるいは濃度）であり、ｔｈは所定の閾値である。つまり、（数１）はブロックに含まれる全ての画素のレベルが閾値ｔｈの幅に収まっていれば、分割を中止し、収まっていなければ、更に分割を続けることを意味する。
【０００９】
このように、画像信号の３次元ブロックを、その３次元ブロックに含まれる画素のレベルが全て同一であると見なせるまで分割し、その分割されたブロックの構造データとそのブロックに含まれる画素のレベルを組にしたものを画像信号として記述すれば、全ての画素について画素情報を一つ一つ記述する場合に比べて信号量を小さくできる。つまり信号圧縮が行われる訳である。
【非特許文献１】C. L. Jackins and S. L. Tanimoto ”Oct-trees and their use in representing three dimensional objects”, CGIP, vol. 14, pp. 249-270, 1980.
【非特許文献２】M. Yau and S. N. Srihari ”Recursive generation of hierarchical data structures for multidimensional digital images”, Proc. PRIP'82, pp. 485-490, 1982
【非特許文献３】D. Meagher ”Geometric modeling using octree encoding”, CGIP, vol. 19, pp. 129-147, 1982
【非特許文献４】N. Ahuja and C. Nash ”Octree representation of moving objects” CVGIP, vol. 26, pp. 207-216, 1984
【発明の開示】
【発明が解決しようとする課題】
【００１０】
八分木法を用いる画像信号の圧縮方法は、加算、減算、比較あるいはビットシフトのような単純な演算で構成されているので、ＭＰＥＧ１等に比べて計算が簡単であった。しかしながら、この方式は３次元ブロックの一部に同一と見なせない部分があると、その３次元ブロック全体を８分割するので、必要以上の分割が行われ、圧縮効率が低くなるという問題があった。
【００１１】
例えば、図１２の上位の３次元ブロックＡ１を構成する６４個の画素の内、下位の３次元ブロックＣ１、Ｃ１６に相当する２個の画素の輝度が、他の６２個の画素と大きく異なり、他の６２個の画素の輝度は同一と見なせる場合を考えてみる。このような場合でも、八分木法では最上位の３次元ブロックＡ１を８分割して、８個の中位の３次元ブロックＢ１〜Ｂ８を作成し、中位の３次元ブロックＢ５およびＢ８をさらにそれぞれ、８分割して、１６個の下位の３次元ブロックＣ１〜Ｃ１６を作成しているから、上位の３次元ブロックＡ１を中位の３次元ブロック６個、下位の３次元ブロック１６個の合計２２個に分割することになる。結局、６４個の画素を２２個のブロックにまとめた訳であり、圧縮率は１／３程度に留まる。
【００１２】
このように、八分木法を用いる画像信号の圧縮は圧縮効率が低いので、実用性に難点があった。そこで、本発明は演算の簡易化と圧縮効率の高効率化を同時に実現する画像信号の符号化方法および装置を提供することを目的とするものである。
【課題を解決するための手段】
【００１３】
本発明の画像信号の符号化方法の第１の構成は、画像信号の列を３次元ブロック化して、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割して、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する画像信号の符号化方法において、前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを連結したものを前記塊とすることを特徴とする。
【００１４】
本発明の画像信号の符号化方法の第２の構成は前記第１の構成に加えて、前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする。
【００１５】
この構成により、そこに含まれる全ての画素の画素レベルが同一と見なされる任意形状の一連のサブブロックを塊として取り扱うから、不必要な分割を回避することができるので、画像信号の圧縮率が高くなる。
【００１６】
本発明の画像信号の符号化方法の第３の構成は前記第２の構成に加えて、そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割して、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする。
【００１７】
この構成により、前記サブブロックをさらにマイクロブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割するから、画質が向上する。
【００１８】
本発明の画像信号の符号化方法の第４の構成は、前記第２または第３の構成に加えて、四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正することを特徴とする。
【００１９】
この構成により、直接比較すればリンクされないサブブロックが、リンクの繰り返しにより同一の画素の塊として扱われること回避できるので、画質が向上する。
【００２０】
本発明の画像信号の符号化方法の第５の構成は、前記第２ないし第４の構成に加えて、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする。
【００２１】
この構成により、簡単な演算で「有効／無効」を判断するので、演算時間および消費電力を節約することができる。
【００２２】
本発明の画像信号の符号化方法の第６の構成は、前記第１ないし第５の構成に加えて、前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする。
【００２３】
この構成により、３次元ブロックの分割形式が単純なので、演算が簡単になり、演算時間および消費電力を更に節約することができる。
【００２４】
本発明の画像信号の符号化装置の第１の構成は、画像信号の列を３次元ブロック化する手段と、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割する手段と、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する手段を備えた画像信号の符号化装置において、前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを集めて、前記塊とする手段を備えたことを特徴とする。
【００２５】
本発明の画像信号の符号化装置の第２の構成は前記第１の構成に加えて、前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする。
【００２６】
本発明の画像信号の符号化装置の第３の構成は、前記第２の構成に加えて、そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割する手段と、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする。
【００２７】
本発明の画像信号の符号化装置の第４の構成は、前記第２または第３の構成に加えて、四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正する手段を有することを特徴とする。
【００２８】
本発明の画像信号の符号化装置の第５の構成は、前記第２ないし第４の構成に加えて、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする。
【００２９】
本発明の画像信号の符号化装置の第６の構成は、前記第１ないし第５の構成に加えて、前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする。
【発明の効果】
【００３０】
以上説明したように、本発明は、演算の簡易化と圧縮効率の高効率化および高画質化の要求に同時に答えることができる画像信号の符号化方法および装置を提供することができる。そして、本発明は無線テレビ電話や携帯情報端末（ＰＤＡ）のようなパーソナルビデオコミュニケーションシステムに適した方法および装置として実用性が高い。
【発明を実施するための最良の形態】
【００３１】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例】
【００３２】
図１は、本発明の実施例に係る適応階層ツリー構造の概念図である。上位の３次元ブロックＨ１は画像信号の列を４×４×４画素の立方体にブロック化したものであり、３個の任意形状のサブブロックＩ１〜Ｉ３に分割される。サブブロックＩ１およびＩ２は、２×２×２画素からなる単位立方体であり、サブブロックＩ３は、６個の前記単位立方体が連結されたものである。さらに、サブブロックＩ２は３個のマイクロブロックＪ１〜Ｊ３に分割されている。マイクロブロックＪ１およびＪ３はそれぞれ２個の画素から構成され、マイクロブロックＪ２は４個の画素から構成されている。そして、サブブロックＩ１に含まれる画素の画素レベルは全て同一と見なされる。同様にサブブロックＩ３およびマイクロブロックＪ１、Ｊ２、Ｊ３にそれぞれ含まれる画素の画素レベルは全て同一と見なされる。
【００３３】
このように、前記適応階層ツリー構造においては、上位の３次元ブロックは、そこに含まれる画素の画素レベルが全て同一と見なされるまで、分割を繰り返して、何個かの任意の形状の下位の３次元ブロックに分割される。この下位の３次元ブロックの構造データと前記下位の３次元ブロックに含まれる画素の画素レベルを量子化したデータを組み合わせることによって、画像データは圧縮される。
【００３４】
これから、前記適応階層ツリーを作成するために、８個（＝２×２×２）のサブブロックから構成される立方体ブロックを、任意形状の下位のブロックに分割する手順を説明する。
【００３５】
図２および図３は、立方体ブロックの分割手順を説明する図である。図２に示すように、立方体ブロックＮは８個のサブブロックＰ（１）〜Ｐ（８）から構成されている。ここで、サブブロックＰ（１）〜Ｐ（８）の互いの関係を表示する１２本のリンクＬ１２〜Ｌ７８を仮想する。
【００３６】
リンクＬ１２、Ｌ３４、Ｌ５６およびＬ７８は、それぞれリンクＰ（１）とＰ（２）とＰ（３）とＰ（４）、Ｐ（５）とＰ（６）およびＰ（７）とＰ（８）を結ぶリンクであり、横方向リンクと呼ぶことにする。
【００３７】
リンクＬ１３、Ｌ２４、Ｌ５７およびＬ６８は、それぞれリンクＰ（１）とＰ（３）とＰ（２）とＰ（４）、Ｐ（５）とＰ（７）およびＰ（６）とＰ（８）を結ぶリンクであり、縦方向リンクと呼ぶことにする。
【００３８】
リンクＬ１５、Ｌ２６、Ｌ３７およびＬ４８は、それぞれリンクＰ（１）とＰ（５）とＰ（２）とＰ（６）、Ｐ（３）とＰ（７）およびＰ（４）とＰ（８）を結ぶリンクであり、奥行き方向リンクと呼ぶことにする。
【００３９】
さて、図３(ａ）に示すように８個のサブブロックＰ（１）〜Ｐ（８）の画素レベルが大きく異なる場合は、隣接するサブブロックＰ（１）〜Ｐ（８）のどれを組み合わせても同一と見なせるものはないから、すべてのリンクＬ１２〜Ｌ７８は「無効」（図では点線で表示している）状態にあると考える。また、サブブロックＰ（１）とサブブロックＰ（５）に含まれる画素の画素レベルが同一と見なされ、他のサブブロックのレベルが異なる場合は、図３（ｂ）に示すように、リンクＬ１５が「有効」（図では太実線で表示している）状態にあると考え、サブブロックＰ（１）とサブブロックＰ（５）を併合して、１つのブロックとして取り扱い、他の６個のサブブロックはそれぞれを独立したブロックとして取り扱う。また、全てのサブブロックＰ（１）〜Ｐ（８）のレベルが同一と見なせる場合は、図３（ｃ）に示すように、すべてのリンクＬ１２〜Ｌ７８が「有効」状態にあると考え、８個のサブブロックＰ（１）〜Ｐ（８）を全て併合して、１つのブロックとして取り扱う。
【００４０】
このように、８個のサブブロックＰ（１）〜Ｐ（８）の中から併合可能な組み合わせ、すなわち、そこに含まれる全ての画素の画素レベルが同一とみなせるようなサブブロックＰ（１）〜Ｐ（８）の組み合わせを選び出して、サブブロックの塊を作成する問題は、１２個のリンクＬ１２〜Ｌ７８のそれぞれについて、「有効」または「無効」を決定する問題に帰着できる。なお、８個のサブブロックＰ（１）〜Ｐ（８）の併合のパターンは、２の１２乗通り、すなわち４０９６通りあることになるが、後述する「併合補正」の処理によって、不合理な組み合わせを排除すると、本発明の方法で選択可能な組み合わせは９８４通りになる。
【００４１】
そこで、１２個のリンクＬ１２〜Ｌ７８のそれぞれについて、「有効」または「無効」を決定する手順を、図４〜図８を参照しながら説明する。
【００４２】
図４は、８個のサブブロックＰ（１）〜Ｐ（８）の併合の可否を決定する概略手順を説明する図である。この概略手順は、横方向リンクの有効・無効を検討して横方向に並ぶサブブロック同士の併合の可能性を判断する第１ステップ、縦方向リンクの有効・無効を検討して縦方向に並ぶサブブロック同士の併合の可能性を判断する第２ステップ、前記第１ステップで判断した横方向のサブブロックの併合と前記第２ステップで判断した縦方向の併合の間に不合理が生じた場合に前記縦方向の併合の判断を取り消す第３ステップ、奥行き方向リンクの有効・無効を検討して奥行き方向に並ぶサブブロック同士の併合の可能性を判断する第４ステップ、および前記第１ステップないし前記第３ステップで判断したサブブロックの横方向および縦方向の併合と前記第４ステップで判断したサブブロックの奥行き方向の併合の間に不合理が生じた場合に前記奥行き方向の併合の判断を取り消す第５ステップに大きく分けられる。以下、第１ステップから順を追って、１２個のリンクＬ１２〜Ｌ７８の「有効／「無効」を決定する手順を説明する。
【００４３】
（第１ステップ）
符号化の対象となる画像信号の列はビデオメモリ１に記憶されている。このビデオメモリ１から画像信号の列を逐次読み出して、前記画像信号の列をサブブロックＰ（１）〜Ｐ（８）からなる３次元ブロックにして、パイプラインレジスタ２に記憶する。次に、サブブロックＰ（１）〜Ｐ（８）に属する画素の画素レベルをパイプラインレジスタ２から読み出し、領域併合判断モジュール３１〜３４に入力する。領域併合判断モジュール３１はサブブロックＰ（１）に属する画素の画素レベルとサブブロックＰ（２）に属する画素の画素レベルを比較してサブブロックＰ（１）とサブブロックＰ（２）の併合の可否を判断するモジュールである。同様に、領域併合判断モジュール３２はサブブロックＰ（３）とサブブロックＰ（４）の、領域併合判断モジュール３３はサブブロックＰ（５）とサブブロックＰ（６）の、領域併合判断モジュール３４はサブブロックＰ（７）とサブブロックＰ（８）の併合の可否をそれぞれ判断するモジュールである。
【００４４】
（領域併合判断モジュール）
図５は、領域併合判断モジュールの入出力を模式化した図である。なお、領域併合判断モジュール３１〜３４および後述する領域併合判断モジュール５１〜５４、領域併合判断モジュール８１〜８４の処理は全く同一である。
【００４５】
領域併合判断モジュールの入力は、Ｉａｍａｘ，Ｉａｍｉｎ，Ｉｂｍａｘ，ＩｂｍｉｎおよびＴｈの５種である。ここで、添え字ａ，ｂは併合判断の対象となるサブブロックＰ（１）〜Ｐ（８）の番号を示している。すなわち、Ｉａｍａｘ，Ｉａｍｉｎは領域併合判断の対象となる一方の領域（サブブロックＰ（ａ））に属する画素の画素レベルの最大値と最小値であり、Ｉｂｍａｘ，Ｉｂｍｉｎは他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの最大値と最小値である。また、Ｔｈは画素レベルを同一と見なすか否か（つまり、領域併合の可否）を判断するための閾値である。
【００４６】
領域併合判断モジュール２１の出力は、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，ＯｂｍｉｎおよびＬｉｎｋの５種である。Ｏａｍａｘ，Ｏａｍｉｎは前記一方の領域（サブブロックＰ（ａ））に属する画素の画素レベルの代表値であり、Ｏｂｍａｘ，Ｏｂｍｉｎは前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの代表値である。Ｌｉｎｋは領域併合の可否を表示するためのフラグである。
【００４７】
領域併合が成されない場合は、代表値Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎはそれぞれ最大値、最小値Ｉａｍａｘ，Ｉａｍｉｎ，Ｉｂｍａｘ，Ｉｂｍｉｎに等しい。
【００４８】
領域併合が成される場合は、ＯａｍａｘおよびＯｂｍａｘは、前記一方の領域（サブブロックＰ（ａ））または前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの最大値（つまり、ＩａｍａｘまたはＩｂｍａｘのいずれか大きい方の値）に等しくなり、ＯａｍｉｎおよびＯｂｍｉｎは前記一方の領域（サブブロックＰ（ａ））または前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルの最小値（つまり、ＩａｍｉｎまたはＩｂｍｉｎのいずれか小さい方の値）に等しくなる。領域併合が成される場合は前記一方の領域（サブブロックＰ（ａ））および前記他方の領域（サブブロックＰ（ｂ））に属する画素の画素レベルが同一であると見なされるから、画素レベルの代表値も統一されるのである。
【００４９】
次に、領域併合の可否の判断の手順と、代表値Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎを決定する手順を詳述する。
【００５０】
まず、下記の（数２）に示すように、ＩａｍａｘとＩｂｍａｘの値を比較していずれか大きい値をＩｍａｘとする。つまりＩｍａｘはサブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルの最大値である。
【００５１】
Ｉｍａｘ＝ｍａｘ（Ｉａｍａｘ，Ｉｂｍａｘ） （数２）
【００５２】
つぎに、（数３）に示すように、ＩａｍｉｎとＩｂｍｉｎの値を比較していずれか小さい値をＩｍｉｎとする。つまりＩｍｉｎはサブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルの最小値である。
【００５３】
Ｉｍｉｎ＝ｍｉｎ（Ｉａｍｉｎ，Ｉｂｍｉｎ） （数３）
【００５４】
さらに、（数４）に示すように、ＩｍａｘとＩｍｉｎの差Ｄ、すなわち、サブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルの変動幅（ダイナミックレンジ）を求める。
【００５５】
Ｄ＝Ｉｍａｘ−Ｉｍｉｎ （数４）
【００５６】
次に、変動幅Ｄと閾値Ｔｈを比較する。変動幅Ｄが閾値Ｔｈより小さければ、サブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルは同一と見なせるから、「併合は可」と判断され、リンクＬａｂは「有効」とされる。この時、フラグＬｉｎｋに「１」を立てる。逆に変動幅Ｄが閾値Ｔｈｒｅｓｈｏｌｄと等しいか、より大きければ、サブブロックＰ（ａ）とサブブロックＰ（ｂ）を併合した領域に属する画素の画素レベルは同一と見なせないから、「併合は不可」と判断され、リンクＬａｂは「無効」とされる。この時、フラグＬｉｎｋに「０」を立てる。
【００５７】
以後の説明では、リンクＬａｂのフラグＬｉｎｋの値を単にＬａｂと表記することにする。つまり、Ｌａｂ＝１ならば、リンクＬａｂは「有効」であり、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の「併合は可」とされていることを意味し、Ｌａｂ＝０ならば、リンクＬａｂは「無効」であり、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の「併合は不可」とされていることを意味する。
【００５８】
最後に、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎに（表１）に示す値を代入する。つまり、Ｌａｂ＝０の時は、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の併合は不可だから、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎの値は元のままであり、Ｉａｍａｘ，Ｉａｍｉｎ，Ｉｂｍａｘ，Ｉｂｍｉｎがそれぞれ代入される。Ｌａｂ＝１の時は、サブブロックＰ（ａ）とサブブロックＰ（ｂ）の併合は可だから、ＯａｍａｘとＯｂｍａｘはＩｍａｘに統一され、ＯａｍｉｎとＯａｍｉｎはＩｍｉｎに統一される。これらの値を出力して、領域併合判断モジュールの処理は終わる。
【００５９】
【表１】
【００６０】
同様に、領域併合判断モジュール３２〜３４もそれぞれの判断対象のサブブロックに対して、同様の処理を行う。なお、領域併合判断モジュール３１〜３４の処理は互いに独立しているから、パラレルに処理することも出来るが、シリアルに処理しても良い。また、領域併合判断モジュール３１〜３４の出力はパイプラインレジスタ４に記憶される。
【００６１】
（第２ステップ）
パイプラインレジスタ４から前記第１ステップの処理後のサブブロックＰ（１）〜Ｐ（８）の画素レベルの最大値Ｉ１ｍａｘ〜Ｉ８ｍａｘおよび最小値Ｉ１ｍｉｎ〜Ｉ８ｍｉｎを読み出して、領域併合判断モジュール５１〜５４に入力する。領域併合判断モジュール５１はサブブロックＰ（１）とサブブロックＰ（３）の併合の可否を判断するモジュールである。同様に、領域併合判断モジュール５２はサブブロックＰ（２）とサブブロックＰ（４）の、領域併合判断モジュール５３はサブブロックＰ（５）とサブブロックＰ（７）の、領域併合判断モジュール５４はサブブロックＰ（６）とサブブロックＰ（８）の併合の可否をそれぞれ判断するモジュールである。
【００６２】
領域併合判断モジュール５１〜５４では、前述の領域併合判断モジュール３１〜３４と同様の処理が行われ、サブブロックＰ（１）〜Ｐ（８）の縦方向の併合の可否が判断される。領域併合判断モジュール４１〜４４の処理も互いに独立しているから、パラレルに処理することも出来るが、シリアルに処理しても良い。
【００６３】
（第３ステップ）
前記第２ステップの処理結果は、４併合補正モジュール６１、６２に入力されて処理される。４併合補正モジュール６１はサブブロックＰ（１）〜Ｐ（４）の横方向併合と縦方向併合の不合理を補正するモジュールであり、４併合補正モジュール６２はサブブロックＰ（５）〜Ｐ（８）の横方向併合と縦方向併合の不合理を補正するモジュールである。
【００６４】
４併合補正モジュール６１、６２の処理内容を説明する前に、「併合補正」の概念を説明する。
【００６５】
図６は、「併合補正」の概念を説明する図である。まず、サブブロックＰ（１）〜Ｐ（４）が与えられて（図６（ａ））、横方向併合を検討した結果、サブブロックＰ（１）とＰ（２）は併合可（リンクＬ１２は「有効」）であるが、サブブロックＰ（３）とＰ（４）は併合不可（リンクＬ３４は「無効」）となった（図６（ｂ））。次に縦方向併合を検討すると、サブブロックＰ（１）とＰ（３）は併合可（リンクＬ１３は「有効」）であり、サブブロックＰ（２）とＰ（４）も併合可（リンクＬ２４は「有効」）となった（図６（ｃ））。このように、四辺形を構成する４つのリンクのうち３つのリンクが「有効」となる場合がある。
【００６６】
この場合、サブブロックＰ（１）とＰ（２）が併合されるとともに、サブブロックＰ（１）とＰ（３）、サブブロックＰ（２）とＰ（４）が併合されるので、結局、サブブロックＰ（１）〜Ｐ（４）が全て併合され１つのブロックとして取り扱われることになる。前述したように、サブブロックＰ（３）とＰ（４）を直接比較すると、画素レベルの差が大きいので併合不可とされるにも関わらず、併合を繰り返した結果、同一の画素レベルに統一されてしまう訳である。このような不合理を放置すると、本来、その画面に存在する画素レベルの高低が消されてしまうので、画質が低下する場合がある。
【００６７】
そこで、４個のサブブロックを結ぶ４本のリンクの内、３本が「有効」で１本が「無効」とされた時に、「有効」とされた前記３本のリンクのいずれか１本を「無効」として、そのリンクで結合されるサブブロックの併合を行わないことにした。この処理を本明細書では「併合補正」と呼ぶことにする。
【００６８】
さて、３本のリンクの中から「無効」にする１本を選ぶ方法は各種考えられる。例えば、３本のリンクの変動幅（ダイナミックレンジ）を比較して、変動幅の一番大きいリンクを「無効」にするようにすれば、画素レベルの変化をより忠実に再現できる。しかし、本実施例では計算の簡易化のために、リンクの添え字の番号の古いものを「無効」にすることにしたので、リンクＬ２４を「無効」にした（図６（ｄ））。
【００６９】
（４併合補正モジュール）
図７は、４併合補正モジュール６１、６２の入出力を模式化した図である。なお、４併合補正モジュール６１および４併合補正モジュール６２の処理は全く同一である。
【００７０】
４併合補正モジュール６１，６２の入力は、Ｉａｍａｘ，Ｉａｍｉｎ，Jａｍａｘ，Jａｍｉｎ，Ｉｂｍａｘ，Ｉｂｍｉｎ，Jｂｍａｘ，Ｊｂｍｉｎ，Ｉｃｍａｘ，Ｉｃｍｉｎ，Ｊｃｍａｘ，Ｊｃｍｉｎ，Ｉｄｍａｘ，Ｉｄｍｉｎ，Ｊｄｍａｘ，Ｊｄｍｉｎ，およびＬａｂ，Ｌｃｄ，Ｌａｃ，Ｌｂｄの２０種である。添え字ａ，ｂ，ｃ，ｄは４併合補正の対象であるサブブロックＰ（１）〜Ｐ（８）の番号を示している。Ｉａｍａｘ，ＩａｍｉｎはサブブロックＰ（ａ）に属する画素の画素レベルの代表値であって、第２ステップ終了後つまり縦方向の領域併合判断モジュール５１〜５４の処理後の値である。また、Jａｍａｘ，JａｍｉｎはサブブロックＰ（ａ）に属する画素の画素レベルの代表値であって、第１ステップ終了後つまり横方向の領域併合判断モジュール３１〜３４の処理後の値である。同様に、Ｉｂｍａｘ〜ＩｄｍｉｎはサブブロックＰ（ｂ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値であって、第２ステップ終了後の値である。また、Jｂｍａｘ，JｄｍｉｎはサブブロックＰ（ｂ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値であって、第１ステップ終了後の値である。
【００７１】
４併合補正モジュールの６１，６２の出力は、Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎ，Ｏｃｍａｘ，Ｏｃｍｉｎ，Ｏｄｍａｘ，ＯｄｍｉｎおよびＬ’ａｃ，Ｌ’ｂｄの１０種である。添え字ａ，ｂ，ｃ，ｄは４併合補正の対象であるサブブロックＰ（１）〜Ｐ（８）の番号を示している。Ｏａｍａｘ〜ＯｄｍｉｎはサブブロックＰ（ｂ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値である。また、Ｌ’ａｃ，Ｌ’ｂｄはサブブロックＰ（ａ），Ｐ（ｃ）間およびＰ（ｂ），Ｐ（ｄ）間の併合の可否を表示するフラグＬｉｎｋである。
【００７２】
図８は、４併合補正の規則を説明する図である。４併合補正モジュール６１、６２にフラグＬａｂ，Ｌｃｄ，Ｌａｃ，Ｌｂｄが入力されると、この規則にしたがって、縦方向リンクのフラグＬａｃおよびＬｂｄの値は、Ｌ’ａｃ，Ｌ’ｂｄに変更される。
【００７３】
図８に示すように、サブブロックＰ（a）〜Ｐ（b）について４併合補正が必要となる場合は下記のパターン１〜４の４通りの場合がある。
（パターン１)
横方向リンクＬａｂが「無効」、横方向リンクＬｃｄ、縦方向リンクＬａｃおよび縦方向リンクＬｂｄが「有効」（Ｌａｂ＝０、Ｌｃｄ＝Ｌａｃ＝Ｌｂｄ＝１）の場合は、縦方向リンクＬａｃをそのまま（Ｌ’ａｃ＝１）にして、縦方向リンクＬｂｄを補正して「無効」（Ｌ’ｂｄ＝０）にする。
（パターン２）
横方向リンクＬａｂが「有効」で、横方向リンクＬｃｄが「無効」、縦方向リンクＬａｃおよび縦方向リンクＬｂｄが「有効」（Ｌａｂ＝１、Ｌｃｄ＝０、Ｌａｃ＝Ｌｂｄ＝１）の場合は、縦方向リンクＬａｃをそのまま（Ｌ’ａｃ＝１）にして、縦方向リンクＬｂｄを補正して「無効」（Ｌ’ｂｄ＝０）にする。
（パターン３)
横方向リンクＬａｂ、Ｌｃｄが「有効」で、縦方向リンクＬａｃが「無効」、縦方向リンクＬｂｄが「有効」（Ｌａｂ＝Ｌｃｄ＝１、Ｌａｃ＝０、Ｌｂｄ＝１）の場合は、縦方向リンクＬａｃをそのまま（Ｌ’ａｃ＝０）にして、縦方向リンクＬｂｄを補正して「無効」（Ｌ’ｂｄ＝０）にする。
（パターン４)
横方向リンクＬａｂ、横方向リンクＬｃｄおよび縦方向リンクＬａｃが「有効」で、縦方向リンクＬｂｄが「無効」（Ｌａｂ＝Ｌｃｄ＝Ｌａｃ＝１、Ｌｂｄ＝０）の場合は、縦方向リンクＬａｃを補正（Ｌ’ａｃ＝０）して、縦方向リンクＬｂｄをそのまま（Ｌ’ｂｄ＝０）にする。
以上のパターン１〜４に当てはまらない場合は、補正は行わない。つまり、縦方向リンクＬａｃおよび縦方向リンクＬｂｄともにそのまま（Ｌ’ａｃ＝Ｌａｃ、Ｌ’ｂｄ＝Ｌｂｄ）にする。
【００７４】
以上説明した補正の規則を纏めると、表２のようになる。
【００７５】
【表２】
【００７６】
縦方向リンクＬａｃおよび縦方向リンクＬｂｄの補正が終わったら、各サブブロックＰ（ａ）〜Ｐ（ｄ）に属する画素の画素レベルの代表値Ｏａｍａｘ，Ｏａｍｉｎ，Ｏｂｍａｘ，Ｏｂｍｉｎｂｍｉｎ，Ｏｃｍａｘ，Ｏｃｍｉｎ，Ｏｄｍａｘ，Ｏｄｍｉｎを、表３および表４に示す規則に従って決定する。
【００７７】
【表３】
【００７８】
【表４】
【００７９】
以下に、表３，表４の規則を簡単に説明する。
ＣＡＳＥ１：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンク、縦方向リンクの両方が「無効」だから、サブブロックＰ（ａ）、サブブロックＰ（ｂ）に属する画素の画素レベルの代表値は、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）についての横方向の領域併合判断後の値が採用される
【００８０】
ＣＡＳＥ２：サブブロックＰ（ａ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には横方向についての領域併合判断後の値が採用される。サブブロックＰ（ｂ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８１】
ＣＡＳＥ３：サブブロックＰ（ａ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合判断後の値が採用される。サブブロックＰ（ｂ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には横方向についての領域併合判断後の値が採用される。
【００８２】
ＣＡＳＥ４：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合判断後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８３】
ＣＡＳＥ５：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンクが「有効」であり、縦方向リンクが「無効」だから、画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｂ）についての横方向の領域併合判断後の値が採用される。
【００８４】
ＣＡＳＥ６：サブブロックＰ（ａ）については、横方向リンクが「有効」、縦方向リンクが「無効」であり、サブブロックＰ（ｂ）については、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ａ）、サブブロックＰ（ｂ）およびサブブロック（ｄ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の代表値はサブブロックＰ（ｂ）とサブブロックＰ（ｄ）についての縦方向の領域併合判断後の代表値が採用される。
【００８５】
ＣＡＳＥ７：サブブロックＰ（ａ）については、横方向リンクおよび縦方向リンクが「有効」であり、サブブロックＰ（ｂ）については、横方向リンクが「有効」、縦方向リンクが「無効」だから、サブブロックＰ（ａ）、サブブロックＰ（ｂ）およびサブブロック（ｃ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の代表値はサブブロックＰ（ａ）とサブブロックＰ（ｃ）についての縦方向の領域併合判断後の代表値が採用される。
【００８６】
ＣＡＳＥ８：サブブロックＰ（ａ）、サブブロックＰ（ｂ）のいずれについても、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ａ）およびサブブロックＰ（ｂ）の画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）ついての縦方向の領域併合後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８７】
ＣＡＳＥ９：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンク、縦方向リンクの両方が「無効」だから、サブブロックＰ（ｃ）、サブブロックＰ（ｄ）に属する画素の画素レベルの代表値は、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）についての横方向の領域併合判断後の値が採用される。
【００８８】
ＣＡＳＥ１０：サブブロックＰ（ｃ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には。サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）についての横方向の領域併合判断後の値が採用される。サブブロックＰ（ｄ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００８９】
ＣＡＳＥ１１：サブブロックＰ（ｃ）については、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、画素レベルの代表値にはサブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合判断後の値が採用される。サブブロックＰ（ｄ）については、横方向リンク、縦方向リンクの両方が「無効」だから、画素レベルの代表値には、サブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００９０】
ＣＡＳＥ１２：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンクが「無効」であり、縦方向リンクが「有効」だから、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の画素レベルの代表値には、サブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００９１】
ＣＡＳＥ１３：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンクが「有効」であり、縦方向リンクが「無効」だから、画素レベルの代表値には、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）についての横方向の領域併合判断後の値が採用される。
【００９２】
ＣＡＳＥ１４：サブブロックＰ（ｃ）については、横方向リンクが「有効」、縦方向リンクが「無効」であり、サブブロックＰ（ｄ）については、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ｃ）、サブブロックＰ（ｄ）およびサブブロック（ｂ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の代表値はサブブロックＰ（ｂ）とサブブロックＰ（ｄ）についての縦方向の領域併合判断後の代表値が採用される。
【００９３】
ＣＡＳＥ１５：サブブロックＰ（ｃ）については、横方向リンクおよび縦方向リンクが「有効」であり、サブブロックＰ（ｄ）については、横方向リンクが「有効」、縦方向リンクが「無効」だから、サブブロックＰ（ｃ）、サブブロックＰ（ｄ）およびサブブロック（ａ）がリンクで結合され、画素レベルが同一と見なされていることになる。したがって、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の代表値はサブブロックＰ（ａ）とサブブロックＰ（ｃ）についての縦方向の領域併合判断後の代表値が採用される。
【００９４】
ＣＡＳＥ１６：サブブロックＰ（ｃ）、サブブロックＰ（ｄ）のいずれについても、横方向リンクおよび縦方向リンクが「有効」だから、サブブロックＰ（ｃ）およびサブブロックＰ（ｄ）の画素レベルの代表値には、サブブロックＰ（ａ）およびサブブロックＰ（ｃ）についての縦方向の領域併合後、およびサブブロックＰ（ｂ）およびサブブロックＰ（ｄ）についての縦方向の領域併合判断後の値が採用される。
【００９５】
４併合補正モジュール６１および６２の処理結果を、パイプラインレジスタ７に書き込んで、第３ステップは終了する。なお、４併合補正モジュール６１および６２は互いに独立しているから、パラレルに処理しても、シリアルに処理してもよい。
【００９６】
（第４ステップ）
第４ステップでは奥行き方向リンクについて、領域併合判断を行うため、パイプラインレジスタ７から第３ステップの処理結果を読み出して、領域併合判断モジュール８１〜８４に入力する。領域併合判断モジュール８１はサブブロックＰ（１）とサブブロックＰ（５）の併合の可否を判断するモジュールである。また、領域併合判断モジュール８２はサブブロックＰ（３）とサブブロックＰ（７）の、領域併合判断モジュール８３はサブブロックＰ（２）とサブブロックＰ（６）の、領域併合判断モジュール８４はサブブロックＰ（４）とサブブロックＰ（８）の併合の可否をそれぞれ判断するモジュールである。
【００９７】
領域併合判断モジュール８１〜８４では、領域併合判断モジュール３１〜３４および領域併合判断モジュール５１〜５４と同様に、各サブブロックＰ（１）〜Ｐ（８）に含まれる画素の画素レベルを比較して、併合の可否を判断する。
【００９８】
なお、領域併合判断モジュール８１〜８４は互いに独立しているので、パラレル処理、シリアル処理のいずれでもよい。
【００９９】
（第５ステップ）
前記第４ステップの処理結果は、８併合補正モジュール９１に入力されて処理される。８併合補正モジュール９１はサブブロックＰ（１）〜Ｐ（８）の横方向併合と奥行き縦方向併合の不合理および横方向併合と奥行き縦方向併合の不合理を補正するモジュールである。８併合補正モジュール９１は４併合補正モジュール６１，６２と同様に、４個のサブブロックを結ぶ４本のリンクの内、３本が「有効」で１本が「無効」とされた時に、「有効」とされた前記３本のリンクのいずれか１本を「無効」にする処理を行うモジュールであり、次の６組のサブブロックの組、（Ｐ（１）、Ｐ（２）、Ｐ（５）、Ｐ（６））、（Ｐ（１）、Ｐ（３）、Ｐ（５）、Ｐ（７））、（（Ｐ（２）、Ｐ（４）、Ｐ（６）、Ｐ（８））、（Ｐ（３）、Ｐ（４）、Ｐ（７）、Ｐ（８））、（Ｐ（１）、Ｐ（４）、Ｐ（５）、Ｐ（８））および（Ｐ（２）、Ｐ（３）、Ｐ（６）、Ｐ（７））について、奥行き方向のリンクの補正を検討し、その結果を重ね合わせて、前記奥行き方向のリンクの「有効／無効」を決定する。以下に、この補正の手順を詳述する。
【０１００】
サブブロックの組、（Ｐ（１）、Ｐ（２）、Ｐ（５）、Ｐ（６））については、リンクＬ１２，Ｌ５６，Ｌ１５，Ｌ２６の「有効／無効」を表示するフラグＬ１２，Ｌ５６，Ｌ１５，Ｌ２６の組み合わせを表５に示す規則に当てはめて、Ｌ（１）１５，Ｌ（１）２６の値を求める。
【０１０１】
【表５】
【０１０２】
サブブロックの組、（Ｐ（１）、Ｐ（３）、Ｐ（５）、Ｐ（７））については、フラグＬ１３，Ｌ５７，Ｌ１５，Ｌ３７の組み合わせを表６に示す規則に当てはめて、Ｌ（２）１５，Ｌ（１）３７の値を求める。
【０１０３】
【表６】
【０１０４】
サブブロックの組、（Ｐ（２）、Ｐ（４）、Ｐ（６）、Ｐ（８））については、フラグＬ２４，Ｌ６８，Ｌ２６，Ｌ４８の組み合わせを表７に示す規則に当てはめて、Ｌ（２）２６，Ｌ（１）４８の値を求める。
【０１０５】
【表７】
【０１０６】
サブブロックの組、（Ｐ（３）、Ｐ（４）、Ｐ（７）、Ｐ（８））については、フラグＬ３４，Ｌ７８，Ｌ３７，Ｌ４８の組み合わせを表８に示す規則に当てはめて、Ｌ（２）３７，Ｌ（２）４８の値を求める。
【０１０７】
【表８】
【０１０８】
サブブロックの組、（Ｐ（１）、Ｐ（４）、Ｐ（５）、Ｐ（８））については、フラグＬ１４，Ｌ５８，Ｌ１５，Ｌ４８の組み合わせを表９に示す規則に当てはめて、Ｌ（３）１５，Ｌ（３）４８の値を求める。
【０１０９】
【表９】
【０１１０】
なお、フラグＬ１４およびＬ５８は、サブブロックＰ（１）とＰ（４）およびＰ（５）とＰ（８）の併合の有無を表示するフラグであり、（数５）で与えられる。
【０１１１】
Ｌ１４＝（Ｌ１２ａｎｄＬ２４）ｏｒ（Ｌ１３ａｎｄＬ３４）
Ｌ５８＝（Ｌ５６ａｎｄＬ６８）ｏｒ（Ｌ５７ａｎｄＬ７８） （数５）
【０１１２】
サブブロックの組、（Ｐ（２）、Ｐ（３）、Ｐ（６）、Ｐ（７））については、フラグＬ２３，Ｌ６７，Ｌ２６，Ｌ３７の組み合わせを表９に示す規則に当てはめて、フラグＬ２６，Ｌ３７の値をＬ（３）２６，Ｌ（３）３７に変更する。
【０１１３】
【表９】
【０１１４】
なお、フラグＬ２３およびＬ６７は、サブブロックＰ（２）とＰ（３）およびＰ（６）とＰ（７）の併合の有無を表示するフラグであり、下記の（数６）で与えられる。
【０１１５】
Ｌ２３＝（Ｌ１２ａｎｄＬ１３）ｏｒ（Ｌ２４ａｎｄＬ３４）
Ｌ６７＝（Ｌ５６ａｎｄＬ５７）ｏｒ（Ｌ６８ａｎｄＬ７８） （数６）
【０１１６】
これで、サブブロックＰ（１）〜Ｐ（８）の６通りの組み合わせについてのフラグＬ１５、Ｌ２６、Ｌ３７、Ｌ４８の補正値Ｌ（１）１５〜Ｌ（３）４８が得られた。あるリンクについて、前記６通りの組み合わせの少なくとも１つで補正する必要があれば、そのリンクを補正する必要があるので、（数７）に示すように補正値Ｌ（１）１５〜Ｌ（３）４８の論理積をＬ’１５、Ｌ’２６、Ｌ’３７、Ｌ’４８とし、フラグＬ１５、Ｌ２６、Ｌ３７、Ｌ４８をこれらと置き換える。
【０１１７】
Ｌ’１５＝Ｌ（１）１５ａｎｄＬ（２）１５ａｎｄＬ（３）１５
Ｌ’２６＝Ｌ（１）２６ａｎｄＬ（２）２６ａｎｄＬ（３）２６
Ｌ’３７＝Ｌ（１）３７ａｎｄＬ（２）３７ａｎｄＬ（３）３７
Ｌ’４８＝Ｌ（１）４８ａｎｄＬ（２）４８ａｎｄＬ（３）４８ （数７）
【０１１８】
以上の演算結果をパイプラインレジスタ１０に書き込んで、第５ステップは終了する。
【０１１９】
以上、第１ステップから第５ステップの処理を行うことで、１２本のリンクＬ１２〜Ｌ７８の「有効／無効」が決定される。８個のサブブロックからなるブロックは、幾つかの「有効」なリンクで結合されたサブブロックの「塊」に分割される。また、サブブロックに含まれる画素の画素レベルは同一と見なせない場合は、そのサブブロックについて、第１ステップから第５ステップの処理を行って、「そこに含まれる全ての画素の画素レベルが同一と見なせる」マイクロブロックの「塊」に分割する。これを繰り返して、立体ブロックＮ全体を、「そこに含まれる全ての画素の画素レベルが同一と見なせる塊」に分割する。そして、この「塊」に含まれる画素の画素レベルを量子化して、量子化した画素データと「塊」の構造データを組にして、ハフマン符号の手法によって可変長符号に変換する。
【０１２０】
以上、本発明の実施例を、画像信号の符号化方法として説明してきたが、本発明の方法を実施する装置は、コンピュータに本発明の方法をプログラムの形で組み込むことにより簡単に構成できる。また、図４に示したような各モジュールに機能を分割して専用のハードウェアを用意すれば、演算をさらに高速化することができる。
【０１２１】
最後に、本発明の符号化方法の性能を従来の方法と比較して示す。なお、すべての比較は、ビデオフレームの輝度成分（Ｙ）について行っているが、圧縮率については、輝度成分（Ｙ）と２つの色差成分（Ｃｒ、Ｃｂ）を含んでいる。また、客観的比較を行うために、本発明の方法と八分木法については、同一の量子化のステップを使用した。量子化段階のハフマン符号とツリー構造情報は各符号化手法のそれぞれについて作成した。
【０１２２】
図９に、原画像と本発明の方法によって符号化した画像データによる画像、および従来の方法による画像を示す。図９（ａ）は、原画像であり、図９（ｂ）は、ＭＰＥＧ４ ＴＭ５による画像、図９（ｃ）は、本発明の方法による画像、図９（ｄ）は、八分木法による画像である、比較のために、圧縮率は同レベルに揃えている。図から解るように、本発明の方法による画像の画質は、ＭＰＥＧ４ ＴＭ５による画像に比べて遜色がなく、八分木法による画像に比べると遙かに優れている。
【０１２３】
表１０は、各方法による演算数の比較を示す表である。この表から、本発明の方法の操作数はＭＰＥＧ４の約６分の１であり、バッテリーの負担が小さいことが解る。
【０１２４】
【表１０】
【０１２５】
表１１は、各方法による符号化に要する時間を示している。本発明の符号化手法および八分木法による符号化時間は、ＭＰＥＧ４の１０分の１以下である。なお、ここに示した時間は、ペンティアム４（登録商標） ２．４ＧＨｚパーソナルコンピュータ上で動作させた場合であり、ＯＳはウィンドウズＸＰ（登録商標）である。
【０１２６】
【表１１】
【０１２７】
図１０は、各方法について、圧縮率と画質の関係を表示するグラフであり、画質はピーク信号−ノイズ比（ＰＳＮＲ）で表示している。図中で「ＡＤＡＰＴＩＶＥ」と表示した太い実線が本発明の実験結果を示し、「ＭＰＥＧ４」と表示した細い実線はＭＰＥＧ４ ＴＭ５による実験結果を、「ＯＣＴＲＥＥ」と表示した破線は八分木法による実験結果をそれぞれ示している。圧縮率０．５ｂｉｔ／ｐｅｌにおいて、本発明の符号化手法のＰＳＮＲはＭＰＥＧ４に対して約０．６ｄＢ小さいが、八分木法に対しては約１．２ｄＢ優れている。
【０１２８】
図１１は、各方法について、圧縮率０．５ｂｉｔ／ｐｅｌの条件の下で各フレームの画質を表示するグラフである。図中で「ＡＤＡＰＴＩＶＥ」と表示した太い実線が本発明の実験結果を示し、「ＭＰＥＧ４」と表示した細い実線はＭＰＥＧ４ ＴＭ５による実験結果を、「ＯＣＴＲＥＥ」と表示した破線は八分木法による実験結果をそれぞれ示している。ＰＳＮＲの傾向は図１０と同様に、ＭＰＥＧ４、本発明の方法、八分木法の順だが、ＰＳＮＲの分布は本発明の方法が３者の中で最も狭い。
【０１２９】
なお、本実施例では、３次元ブロック化された画像信号をサブブロックに分割するとともに、サブブロックを連結する仮想的な「リンク」という概念を導入して、「リンク」で連結されたサブブロックを、そこに含まれるすべての画素の画素レベルを同一と見なし得る画像信号の塊として取り扱うことにより、画像信号を符号化圧縮する方法および装置を示したが、本発明は「リンク」を用いるものに限られるものではない。３次元ブロック化された画像信号をそこに含まれるすべての画素の画素レベルを同一と見なし得る任意形状のサブブロックの塊に分割する画像信号の符号化方法は、本発明の技術的範囲に含まれる。
【図面の簡単な説明】
【０１３０】
【図１】本発明の実施例に係る適応階層ツリー構造の概念図である。
【図２】立方体ブロックの分割手順を説明する図である。
【図３】立方体ブロックの分割手順を説明する図である。
【図４】８個のサブブロックの併合の可否を決定する概略手順を説明する図である。
【図５】領域併合判断モジュールの入出力を模式化した図である。
【図６】併合補正の概念を説明する図である。
【図７】４併合補正モジュールの入出力を模式化した図である。
【図８】４併合補正の規則を説明する図である。
【図９】原画像、本発明の方法による画像、および従来の方法による画像の例である。
【図１０】圧縮率と画質の関係を表示するグラフである。
【図１１】各フレームの画質を表示するグラフである。
【図１２】八分木法による階層ツリー構造の概念図である。
【符号の説明】
【０１３１】
１ ビデオメモリ
２ パイプラインレジスタ
３１〜３４ 領域併合判断モジュール
４ パイプラインレジスタ
５１〜５４ 領域併合判断モジュール
６１，６２ ４併合補正モジュール
７ パイプラインレジスタ
８１〜８４ 領域併合判断モジュール
９１ ８併合補正モジュール
１０ パイプラインレジスタ
【特許請求の範囲】
【請求項１】
画像信号の列を３次元ブロック化して、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割して、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する画像信号の符号化方法において、
前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを集めて、前記塊とすることを特徴とする画像信号の符号化方法。
【請求項２】
前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする請求項１に記載の画像信号の符号化方法。
【請求項３】
そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割して、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする請求項２に記載の画像信号の符号化方法。
【請求項４】
四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正することを特徴とする請求項２または請求項３に記載の画像信号の符号化方法。
【請求項５】
前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする請求項２ないし請求項４の何れか１項に記載の画像信号の符号化方法。
【請求項６】
前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする請求項１ないし請求項５の何れか１項に記載の画像信号の符号化方法。
【請求項７】
画像信号の列を３次元ブロック化する手段と、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割する手段と、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する手段を備えた画像信号の符号化装置において、
前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを集めて、前記塊とする手段を備えたことを特徴とする画像信号の符号化装置。
【請求項８】
前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする画像データの符号装置。
【請求項９】
そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割する手段と、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする請求項８に記載の画像信号の符号化装置。
【請求項１０】
四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正する手段を有することを特徴とする請求項８または請求項９に記載の画像信号の符号化装置。
【請求項１１】
前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする請求項８ないし請求項１０の何れか１項に記載の画像信号の符号化装置。
【請求項１２】
前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする請求項７ないし請求項１１の何れか１項に記載の画像信号の符号化装置。
【請求項１】
画像信号の列を３次元ブロック化して、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割して、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する画像信号の符号化方法において、
前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを集めて、前記塊とすることを特徴とする画像信号の符号化方法。
【請求項２】
前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする請求項１に記載の画像信号の符号化方法。
【請求項３】
そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割して、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とし、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする請求項２に記載の画像信号の符号化方法。
【請求項４】
四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正することを特徴とする請求項２または請求項３に記載の画像信号の符号化方法。
【請求項５】
前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする請求項２ないし請求項４の何れか１項に記載の画像信号の符号化方法。
【請求項６】
前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする請求項１ないし請求項５の何れか１項に記載の画像信号の符号化方法。
【請求項７】
画像信号の列を３次元ブロック化する手段と、前記３次元ブロックをそこに含まれる全ての画素の画素レベルが同一と見なされる塊に分割する手段と、前記塊の構造データと前記塊に含まれる画素の画素レベルを量子化したデータを組にして記述する手段を備えた画像信号の符号化装置において、
前記３次元ブロックを複数のサブブロックに分割して、そこに含まれる全ての画素の画素レベルが同一と見なされる前記サブブロックを集めて、前記塊とする手段を備えたことを特徴とする画像信号の符号化装置。
【請求項８】
前記複数のサブブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記サブブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記サブブロックを前記塊とすることを特徴とする画像データの符号装置。
【請求項９】
そこに含まれる全ての画素の画素レベルが同一と見なされない前記サブブロックを、複数のマイクロブロックに分割する手段と、前記複数のマイクロブロックを相互に連結するリンクを仮想して、前記リンクで連結される２個の前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされる時には前記リンクを「有効」とし、前記マイクロブロックに含まれる全ての画素の画素レベルが同一と見なされない時には前記リンクを「無効」とする手段を備え、「有効」な前記リンクで連結された一連の前記マイクロブロックを前記塊とすることを特徴とする請求項８に記載の画像信号の符号化装置。
【請求項１０】
四辺形を形成する４本の前記リンクの内３本が「有効」とされた場合に、前記３本のリンクの何れか１本を「有効」から「無効」に補正する手段を有することを特徴とする請求項８または請求項９に記載の画像信号の符号化装置。
【請求項１１】
前記リンクで連結される２個の前記サブブロックに含まれる全ての画素の画素レベルの最大値と最小値の差が所定の閾値より小さい場合に、前記リンクを「有効」とすることを特徴とする請求項８ないし請求項１０の何れか１項に記載の画像信号の符号化装置。
【請求項１２】
前記３次元ブロックを、各軸方向に２分割して合計８個のサブブロックに分割することを特徴とする請求項７ないし請求項１１の何れか１項に記載の画像信号の符号化装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００６−１０８７９２（Ｐ２００６−１０８７９２Ａ）
【公開日】平成１８年４月２０日（２００６．４．２０）
【国際特許分類】
【出願番号】特願２００４−２８９０２０（Ｐ２００４−２８９０２０）
【出願日】平成１６年９月３０日（２００４．９．３０）
【出願人】（３９１０４３３３２）財団法人福岡県産業・科学技術振興財団 (53)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
【公開日】平成１８年４月２０日（２００６．４．２０）
【国際特許分類】
【出願日】平成１６年９月３０日（２００４．９．３０）
【出願人】（３９１０４３３３２）財団法人福岡県産業・科学技術振興財団 (53)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
[ Back to top ]