(57)【要約】  アナログビデオ情報をデジタル近似するために画素をグループ分けするための、形成された量子化ブロックの蜂の巣型セル配置の使用が開示される。フレームは、蜂の巣型に配置された六角形の量子化セルブロックか、または、れんが壁型に配置された矩形のセル量子化ブロックから構成され、各画素は１つの形の量子化ブロックにしか属さない。フレームが重なり合う量子化ブロックに仕切られる場合に用いられる、円形の量子化ブロックの蜂の巣型セル配置が説明される。
2005515653.tif 000002
【特許請求の範囲】
【請求項１】
アナログビデオ情報を、グループ分けされた画素の量子化ブロックに仕切られたフレームにデジタル近似するためのシステムにおいて、各画素は単一の量子化ブロックに属し、前記画素の量子化ブロックをグループに配置および形成するための最適化方法は、統計的な境界誤差がチェビシェフのオルタナンス定理に従って均一にされるための配置の決定を含み、これにより
（ａ）前記量子化ブロックは全て同一の形状を有し、
（ｂ）各量子化ブロックは接触する量子化ブロックと同じ環境を有し、
（ｃ）前記各量子化ブロックは最低限の数の接触する量子化ブロックを有し、
（ｄ）前記量子化ブロックの１つの中心から隣接する量子化ブロックの中心まで、測定される距離の偏差が最小限であり、
（ｅ）前記量子化ブロックの１つと接触する量子化ブロックとの間の、測定される共通する境界の長さの偏差が最小限である、最適化方法。
【請求項２】
当初は矩形の形状を有する量子化ブロックにチェビシェフのオルタナンス定理を適用することによって、前記量子化ブロックがれんが壁型配置に配置され、これにより前記量子化ブロックは各々、６つの接触する量子化ブロックしか持たない、請求項１に記載の最適化方法。
【請求項３】
チェビシェフのオルタナンス定理を適用することによって六角形状を有し蜂の巣型セル配置に配置される量子化ブロックを作成し、それによって前記量子化ブロックは各々、６つの接触する量子化ブロックしか持たない、請求項１に記載の最適化方法。
【請求項４】
アナログビデオ情報を、グループ分けされた画素の量子化ブロックに仕切られたフレームにデジタル近似するためのシステムにおいて、各画素は単一の量子化ブロックに属し、同等な矩形の量子化ブロックをれんが壁型配置へ組織することによって、各々、６つの接触する量子化ブロックを有する前記矩形の量子化ブロック。
【請求項５】
アナログビデオ情報を、グループ分けされた画素の量子化ブロックに仕切られたフレームにデジタル近似するためのシステムにおいて、各画素は単一の量子化ブロックに属し、同等な六角形状の量子化ブロックを蜂の巣型セル配置へ組織することによって、各々、６つの接触する量子化ブロックを有する前記六角形の量子化ブロック。
【請求項６】
アナログビデオ情報を、グループ分けされた画素の重なり合う量子化ブロックに仕切られたフレームにデジタル近似するためのシステムにおいて、少なくとも１つの画素は複数の量子化ブロックに属し、前記画素の重なり合う量子化ブロックをグループに配置および形成するための最適化方法は、統計的な境界誤差がチェビシェフのオルタナンス定理に従って等価されるための配置の決定を含み、これにより
（ａ）前記重なり合う量子化ブロックは同一の形状を有し、
（ｂ）各重なり合う量子化ブロックは接触する重なり合う量子化ブロックと同じ環境を有し、
（ｃ）前記各重なり合う量子化ブロックは最低限の数の前記接触する重なり合う量子化ブロックを有し、
（ｄ）前記重なり合う量子化ブロックの１つの中心から隣接する重なり合う量子化ブロックの中心まで、測定される距離の偏差が最小限であり、
（ｅ）前記重なり合う量子化ブロックの１つと接触する重なり合う量子化ブロックとの間の、測定される共通する境界の長さの偏差が最小限である、最適化方法。
【請求項７】
前記重なり合う量子化ブロックは円形で蜂の巣型セルと類似の配置で重なり合い、前記円形は前記蜂の巣型セルを包囲し、前記重なり合う円形の量子化ブロックは各々、６つの隣接する重なり合う円形の量子化ブロックのみを有し共通の画素を含む、請求項６に記載の最適化方法。
【請求項８】
前記円形の形状は前記蜂の巣型セルを包囲する多角形の円形の近似を含む、請求項７に記載の最適化方法。
【請求項９】
アナログビデオ情報を、グループ分けされた画素のブロックに仕切られたフレームにデジタル近似するためのシステムにおける、同等の円形形状の重なり合う量子化ブロックの蜂の巣型セル配置において、前記円形形状は前記蜂の巣型セルを包囲し、各々、６つの隣接する重なり合う円形形状の量子化ブロックのみを有し共通の画素を含む前記重なり合う円形形状の量子化ブロック。
【請求項１０】
前記円形形状は前記蜂の巣型セルを包囲する多角形によって近似される、請求項９に記載の蜂の巣型セル配置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してビデオ圧縮処理に関し、より詳細にはビデオ情報の量子化に関連する問題に関する。
【背景技術】
【０００２】
例えばＭＰＥＧ−Ｘシリーズ等のデジタルビデオ符号化アルゴリズムは、ビデオ情報のデジタル量子化のプロセスを用いる。量子化プロセスは、例えばアナログ画像等のアナログビデオ情報の、輝度および色彩の属性を有する多数の画素から成るフレームによる近似を含む。更に、ＭＰＥＧ−Ｘシリーズのアルゴリズムは、一定のビデオ情報が失われることを前提とした圧縮技術を用いる。これはつまり、符号化・復号化手順の後、デジタル化されたビデオ情報の画素がこれに対応するオリジナルの色彩および輝度を有する画素と異なることを意味する。このような技術はビデオ情報を大幅に圧縮でき、画像の品質は実際よりも溢れんばかりに感知されることが可能である一方、符号化・複合化手順を何回か続けて反復するとビデオ情報が著しく劣化する。ＭＰＥＧ−Ｘアルゴリズム技術は、画素を「量子化ブロック」にグループ分けすることに基づき、ある特定のブロックに属する画素は全て、個別にコード化される、つまり、ビデオ情報の一定の劣化をもたらす同一の輝度および色彩の量子化ルールを有する。通常、量子化ルールは、各量子化ブロック毎に別個に選択される量子化ステップによって定義される。このようなビデオ情報の近似により、ビデオ情報の解像度を低下させることによって情報のビットストリームが減少される。これらのブロックは、次のフレームのビデオ情報の近似のために転送ベクトルを用いるためにマクロブロックにグループ分けされ、これにより、情報のビットストリームに必要な帯域幅が更に減少される。動画の場合、ブロックに集成される画素に関するビデオ情報の損失の許容度は、ブロック毎に、また１つのフレームと次のフレームとで、異なる場合がある。この自由度は、１つのフレームから次のフレームへと画像エレメントを追跡するのを可能にし、これにより、原則的にはビット情報のストリームに必要な帯域幅が更に減少する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従って、既知のビデオ圧縮手順は、各ブロックごとに異なる種類の量子化ルールを用いて、解像度の増加と、ビデオ情報の伝送に必要な帯域幅の減少とを達成しようと試みている。ＭＰＥＧ−Ｘアルゴリズムで用いられる従来技術のブロックは、図１に示すように配置される矩形の形状を有する。この場合、矩形のブロックは各々、北、北西、西、南西、南、南東、東、北東の８つの隣接ブロックを有する。各ブロック内でのビデオ情報の劣化は量子化ルールによって制御されるが、検討されるブロックと隣接するブロックとの境界でのビデオ情報の劣化は、ある意味予測不能である。１つのフレームに関して定義されるブロックおよびマクロブロックが、次のフレームのビデオ情報を近似するために転送ベクトルによって転送される場合、次のフレームのイマジネーションにおける統計的誤差は、独立した色彩および輝度の属性の量子化ルールを有する隣接ブロックによって定義され、例えばＴｏｒｓｔｅｎ Ｓｅｅｍａｎｎ、Ｐｅｔｅｒ Ｔｉｓｃｈｅｒ、Ｔｅｔｒａ Ｌｉｎｄａｒｔｏによる論文”Ｇｅｎｅｒａｌｉｓｅｄ  Ｌｏｃａｌｌｙ  Ａｄａｐｔｉｖｅ  ＤＰＣＭ”−Ｐｒｏｃ．ｏｆ  ＩＥＥＥ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｃｏｎｆ．（ＩＥＥＥデータ圧縮会議、議事録）ｐｐ４７３、１９９７に記載されるように、ブロックの境界上に誤差が発生する。
【０００４】
Ｍｏｒｔｕｃｃｉらによる米国特許第５，７６４，８０５号には、量子化ブロックの境界に発生する統計的誤差を減少させるための、重なり合う多角形状のブロックの使用について開示されている。
【課題を解決するための手段】
【０００５】
従って、本発明の主たる目的は、既存のビデオ圧縮アルゴリズムの限界を克服し、蜂の巣型セルに類似する形状および配置を有する量子化ブロックの定義により、ビデオ圧縮のための改良されたアルゴリズムを提供することである。
【０００６】
量子化ブロックの蜂の巣型セルの形状および配置は、次の最適化基準に従って最適化となる。
【０００７】
第１の数理基準は、フレーム領域を完全に埋めるブロックのクラスを検討する場合、その領域に対する各ブロックのペリメータの最小限の比率を達成することである。これにより、圧縮ビデオの統計的な境界誤差は、量子化ブロックの境界の総数が減るのに伴って減少する。
【０００８】
第２の数理基準は、隣接するセルの数を減らすことにある。各セルが８つの隣接セルを有する従来技術の矩形の量子化ブロックの配置において１つのセルと境界を成す隣接セルの数と比較して、本発明は、各々が６つの隣接を有する蜂の巣型セルの形状および配置のブロックを使用する。
【０００９】
第３の数理基準は、次数Ｎの多項式関数による所望の関数の最適な近似のためのチェビシェフの基準である。この基準は、オルタナンスに関するチェビシェフの定理、つまり、所望する関数からの逸脱が最も少ない、与えられた次数Ｎ（我々の場合、Ｎは量子化ブロックの数）の近似多項式関数は、近似多項式関数が所望する関数と一致するN交点間において等しい逸脱を有するという定理が元になっている。
【００１０】
更に、統計的誤差を最小限にする上記第２の数理基準の適用は、ここに従来の矩形の量子化ブロックの、未知なる最適な配置をもたらす。この最適な配置、つまり「れんが壁」型配置は、ブロックの偶数の水平／垂直線を奇数の水平／垂直線へとそれぞれシフトさせることを含む。上記のチェビシェフの定理を適用することにより、「れんが壁」型配置の対称的な偏差がもたらされる。
【００１１】
本発明は、ブロックに配置される際に個々のセルが重なり合う場合にも適用できる。３つの数理最適化基準の適用を含む本発明の方法は、形成された量子化ブロックが重なり合うような配置が許容される場合にも適用できる。この場合、好ましい配置は蜂の巣型セル配置であり、量子化ブロックの好ましい形状は、蜂の巣型セルの六角形を包囲する円形である。
【発明を実施するための最良の形態】
【００１２】
本発明の実施形態に関して本発明がより良く理解されるために、添付の図面を参照する。該図面において、同じ符号は全体を通して対応する要素または部分を示す。
【００１３】
１．従来技術の矩形ブロック
ＭＰＥＧ−Xアルゴリズムで用いられる従来技術の量子化ブロックは矩形の形状を有し、図１に示す方法で配置される。この場合、各矩形のブロック１０は、北１１、北西１２、西１３、南西１４、南１５、南東１６、東１７、北東１８の８つの隣接ブロックを有する。何らかのフレームのために定義された量子化ブロックおよび量子化ブロックのグループであるマクロブロックが、次のフレームのビデオ情報を近似するために移送ベクトルによって移送されると、次の画像の統計的誤差は、独自の色彩および輝度の量子化ルールを有する隣接ブロックによって定義され、ブロックの境界上に誤差が発生する。
【００１４】
２．成形されたブロックの蜂の巣型セル配置
本発明の１つの実施形態である、図２に示す蜂の巣型セル２０タイプの量子化、つまり画素を蜂の巣型セルの形状および配置を有するブロック２０にグループ分けすることは、従来の、画素を図１に示すように配置される矩形の量子化ブロック１０、１１、１２等にグループ分けする場合と比較して、幾つかの利点がある。これらの利点には次のようにものがある。
【００１５】
静止圧縮画像形成の品質改善
静止圧縮画像形成は約７．５％改善される。圧縮量子化ブロックによって近似された静止状態の所望画像は、領域に対するブロックの境界線比率に直接的に依存する近似誤差を有する。等しい領域を有するセル、従来技術の矩形セル１０、および本発明で示される蜂の巣型セル２０の境界線を比較すると、次のP4／P6が得られ、これは次の式に等しい。
【００１６】
【数１】
2005515653.tif 000003
ここで、Ｐ4は領域Ｓ4＝（Ｐ4／４）＾２を有する矩形の境界線であり、
Ｐ6は領域S6＝S4を有する蜂のセルの境界線である。
【００１７】
量子化ブロックビデオ情報を１つのフレームから次のフレームへと移送するための動作ベクトルプロセスにおける品質損失の削減
本発明により、約３３％のオーダーで品質損失の削減が達成される。この効果は、六角形の量子化ブロックの特定の蜂の巣型セル配置によって説明される。いくつかのフレームのために定義されたあるブロックが、次のフレームのビデオ情報を近似するために移送ベクトルによって移送される場合、次の圧縮画像の統計的誤差は、圧縮ブロックに接触する圧縮された隣接ブロックの数に直接的に依存する。各ブロックが、北、北西、西、南西、南、南東、東、北東の８つ接触する隣接ブロックを有するよう配置される矩形のセルを有するブロック１０、１１、１２等を用いる従来技術とは異なり、本発明によれば、蜂の巣型セルの形状に配置される六角形のブロック２０を用いることにより、各ブロックは６つの接触する隣接ブロックを有し、従って連続する画像における統計誤差の値が低くなる。
【００１８】
多項式関数による所望の関数近似のチェビシェフ基準による最適量子化
オルタナンスに関するチェビシェフの定理によると、所望する関数からの逸脱が最も少ない、与えられた次数Ｎの近似多項式関数は、近似多項式関数が所望する関数と一致するＮ交点間に等しい逸脱があるとしている。本発明において、所望する関数は当初の完全な（つまり圧縮されていない）ビデオ情報であり、近似多項式関数は圧縮したビデオ情報を有する量子化ブロックから構築されるフレームであり、与えられた次数Ｎは、量子化ブロックの数である。従って、従来技術では、異なる統計上の誤差、つまり近似多項式関数の異なる逸脱をもたらすブロック１０、１１、１２等を使用するのに対して、本発明では、蜂の巣型セルを形成する形状および配置のブロック２０の使用することにより、６つの等しい隣接ブロックをもたらし、これによって同等の統計的誤差、つまり隣接ブロックの対照的な統計的影響による近似多項式関数の等しい逸脱をもたらす。
【００１９】
３つの数理基準を併せて適用することにより、画素を矩形の量子化ブロックにグループ分けするという既知の方法を用いた場合よりも、動画の圧縮が著しく優れるという効果が得られる。
【００２０】
図４を参照すると、本発明の数理基準を用いて重なり合う量子化ブロックを配置および形成することによる最適化は、円形の形状の重なり合う量子化ブロック４０の蜂の巣型セル配置をもたらす。円形のブロックは蜂の巣型セルの六角形を包囲する。本実施形態の些細な変形は、蜂の巣型セルを覆う多角形によって円形が近似される場合を含む（図示せず）。
【００２１】
３．矩形ブロックのれんが壁型配置
ここで図３を参照すると、図１に示す従来技術の配置に対して、本発明のもう１つの実施形態として、矩形の量子化ブロックの「れんが壁」型配置を用いることによって、任意に選択された量子化ブロック３０の６つの隣接ブロック３１、３２、３３、３４、３５、３６をもたらすことが示されている。この事実はまた、量子化ブロックのビデオ情報を前のフレームから次のフレームへと移送するベクトルのプロセスにおいて、品質の損失が極めて減少される。この効果は、いくつかのフレームのために定義されるブロックが次のフレームのビデオ情報を近似するために移送ベクトルによって移送される場合に、次の画像の統計的誤差は、最も近い隣接ブロックの数に直接的に依存するという事実によって説明される。オルタナンスに関するチェビシェフの定理を考慮に入れると、図３に示すように、れんが壁型配置の対照的な偏差は最適である。さらに、該定理を参照すると、図１に示す従来技術の矩形の量子化ブロックの配置は、極めて最適でない。
【００２２】
上記の実施形態は単に説明的な性質のものであることを認識されるべきである。当業者であれは、本発明の精神を逸脱することなく、例示的な実施形態に様々な変更または修正を加えることが可能であると予想され、また本発明の真の範囲は、本明細書の教示を最も広く解釈して従う本請求項を参照することによってのみ決定されるべきである。
【図面の簡単な説明】
【００２３】
【図１】従来技術における矩形の量子化ブロックの配置を示す概略図である。
【図２】本発明の１つの実施形態を示す概略図であり、画素を、蜂の巣型セルに類似する形状および配置のブロックにする最適なグループ分けを示す。
【図３】本発明の１つの実施形態を示す概略図であり、矩形の量子化ブロックのれんが壁型配置を示す。
【図４】本発明の１つの実施形態を示す概略図であり、重なり合う円形の量子化ブロックの蜂の巣型配置を示す。
【図１】
2005515653.tif 000004
【図２】
2005515653.tif 000005
【図３】
2005515653.tif 000006
【図４】
2005515653.tif 000007
【国際調査報告】
2005515653.tif 000008