(57)【要約】映像圧縮処理は、コンフィギュレーション空間におけるパス最適化問題として最適化問題を設定し、コンフィギュレーション空間の中で最小コストパスを見つけることにより、データストリームを圧縮するための量子化方式の最適な選択を高速化する。この処理は、開始ノード（又は「状態」）から始まり、パスが完成するまで空間に最小コスト波を伝搬させる。この処理は、コストが最終状態よりも小さい間、最小コスト未完成パスから始めて、改良パスが見つけられるまで、未完成パスを使用し続ける。この処理は、更に、時間制約付き処理の場合、時間がなくなるか、又は、すべての有用な可能性が尽きるまで、継続される。
2004532558.tif 000002
【特許請求の範囲】
【請求項１】
映像又は画像を圧縮する方法であって、
データ圧縮処理の最適ビット割り当て問題をモデル化するコンフィギュレーション空間を定義する手順が設けられ、
コンフィギュレーション空間は、ノード及びノード間の遷移を定義し、
ノードは、データストリームの個々の特徴に対して選択された量子化方式に対応し、
パスは遷移の組によって定義され、
各遷移は、該ノードの中の対応したノードで該組の中の別の遷移に接続され、
該パスは開始ノードと終了ノードをつなぎ、
該パスは該組の該遷移のコストの合計に対応する総コストをもち、
最小コストであることが検出された第１のパスが該開始ノードを該終了ノードへつなぐ該コンフィギュレーション空間内で特定されるように、空間的に変化するメトリックに応じて、バディングによって該コンフィギュレーション空間に最小コスト波を伝搬させる手順が設けられ、
該データ圧縮処理によって圧縮されるべき第１のデータの組に、該第１のパス上にある該ノードに対応した量子化方式を適用する手順が設けられている、
方法。
【請求項２】
最小コストであることが検出された第２のパスが特定されるように最小コスト波を伝搬させる手順を繰り返し、該データ圧縮処理によって圧縮されるべき第２のデータの組を圧縮する際に量子化方式を適用する手順を繰り返す手順が更に設けられている、請求項１記載の方法。
【請求項３】
映像又は画像を圧縮する方法であって、
データ圧縮処理の最適ビット割り当て問題をモデル化するコンフィギュレーション空間を定義する手順が設けられ、
コンフィギュレーション空間は、ノード及びノード間の遷移を定義し、
ノードは、データストリームの個々の特徴に対して選択された量子化方式に対応し、
パスは遷移の組によって定義され、
各遷移は、該ノードの中の対応したノードで該組の中の別の遷移に接続され、
該パスは開始ノードと終了ノードをつなぎ、
該パスは該組の該遷移のコストの合計に対応する総コストをもち、
最小コストであることが検出された第１のパスが該開始ノードを該終了ノードへつなぐ該コンフィギュレーション空間内で特定されるように、空間的に変化するメトリックに応じて、バディングによって該コンフィギュレーション空間に最小コスト波を伝搬させる手順が設けられ、
最小コストであることが検出された第２のパスが特定されるように最小コスト波を伝搬させる手順を繰り返す手順と、
該第１のパスのコストと該第２のパスのコストを比較し、該データ圧縮処理によって圧縮されるべき入力データを圧縮する際に、該第１のパスと該第２のパスのうちでコストが小さい方のパス上にある該ノードに対応した量子化方式を適用する手順が設けられている、
方法。
【請求項４】
繰り返す手順と、量子化方式を適用する手順は、最適最小コストパスを検出するために許容された時間間隔に基づいて条件付きで実行される、請求項３記載の方法。
【請求項５】
該入力データは映像データを含み、
該コストは、該映像データの画像の歪みと、量子化方式を適用する手順から得られたデータストリームのビットレートのうちの一方である、
請求項３記載の方法。
【請求項６】
未加工データストリームを受信し、圧縮データストリームを出力するため接続されたプロセッサを含むデータ圧縮装置であって、
該プロセッサは、データ圧縮処理の最適ビット割り当て問題をモデル化するコンフィギュレーション空間のノードをバディングすることにより最適量子化方式を決定するようにプログラミングされ、
ノードは、データストリームの個々の特徴に対して選択された量子化方式に対応し、
パスは遷移の組によって定義され、
各遷移は、該ノードの中の対応したノードで該組の中の別の遷移に接続され、
該パスは開始ノードと終了ノードをつなぎ、
該パスは該組の該遷移のコストの合計に対応する総コストをもち、
バディングによって、最小コストであることが検出されたパスが該開始ノードを該終了ノードへつなぐ該コンフィギュレーション空間内で特定されるように、空間的に変化するメトリックに応じて、該コンフィギュレーション空間に最小コスト波を伝搬させ、
該プロセッサは、該未加工データを圧縮する際に、最小コストのパス上にあるノードに対応した量子化方式を適用するようにプログラミングされている、
データ圧縮装置。
【請求項７】
未加工データストリームを受信し、圧縮データストリームを出力するため接続されたプロセッサを含むデータ圧縮装置であって、
該プロセッサは、データ圧縮処理の最適ビット割り当て問題をモデル化するコンフィギュレーション空間のノードをバディングすることにより最適量子化方式を決定するようにプログラミングされ、
ノードは、データストリームの個々の特徴に対して選択された量子化方式に対応し、
パスは遷移の組によって定義され、
各遷移は、該ノードの中の対応したノードで該組の中の別の遷移に接続され、
該パスは開始ノードと終了ノードをつなぎ、
該パスは該組の該遷移のコストの合計に対応する総コストをもち、
バディングによって、最小コストであることが検出された第１のパスが該開始ノードを該終了ノードへつなぐ該コンフィギュレーション空間内で特定されるように、空間的に変化するメトリックに応じて、該コンフィギュレーション空間に最小コスト波を伝搬させ、
該プロセッサは、
最小コストであることが検出された第２のパスを特定するため更なるコスト波を更に伝搬させ、
該第１のパスのコストと該第２のパスのコストを比較し、
該未加工データを圧縮する際に、該第１のパスと該第２のパスのうちでコストが小さい方のパス上にある該ノードに対応した量子化方式を適用する
ようにプログラミングされている、
データ圧縮装置。
【請求項８】
デジタルデータ圧縮における最適レート／歪み性能のためのビット割り当て方法であって、
該デジタルデータ圧縮に応じてデータストリームの部分の組の各部分に対し選択された相互接続された量子化方式の組を決定する手順と、
該選択された量子化方式の中の最初の量子化方式を定義し、該最初の量子化方式から始めて、必要なすべての量子化方式を定めるパスが見つかるまで、最小コスト波を伝搬させる手順と、
該パスによって定められた該選択された量子化方式の少なくとも一部に基づいて、データ圧縮を実施する手順と、
を有するビット割り当て方法。
【請求項９】
量子化方式の組を決定する手順は、映像データストリームの部分の組の各部分に対して相互接続された量子化方式の組を決定する手順を含む、請求項８記載のビット割り当て方法。
【請求項１０】
該量子化方式はビデオ画像の四分木分割を含む、請求項９記載のビット割り当て方法。
【請求項１１】
該量子化方式は動きベクトルフィールドを表現する量子化方式を含む、請求項９記載のビット割り当て方法。
【請求項１２】
該量子化方式は該データストリームの値の間の差を量子化する量子化方式を含む、請求項８記載のビット割り当て方法。
【請求項１３】
デジタルデータ圧縮における最適レート／歪み性能のためのビットを割り当てる装置であって、
データストリームが供給され、該デジタルデータ圧縮に応じてデータストリームの部分の組の各部分に対し選択された相互接続された量子化方式の組を決定するようにプログラミングされたプロセッサを有し、
該プロセッサは、該選択された量子化方式の中の最初の量子化方式を定義し、該最初の量子化方式から始めて、必要なすべての量子化方式を定めるパスが見つかるまで、最小コスト波を伝搬させるように更にプログラミングされ、
該プロセッサは、該パスによって定められた該選択された量子化方式の少なくとも一部に基づいて、データ圧縮を実施するように更にプログラミングされている、
装置。
【請求項１４】
該データストリームは映像データストリームである、請求項１３記載の装置。
【請求項１５】
該量子化方式はビデオ画像の四分木分割を含む、請求項１４記載の装置。
【請求項１６】
該量子化方式は動きベクトルフィールドを表現する量子化方式を含む、請求項１４記載の装置。
【請求項１７】
該量子化方式は該データストリームの値の間の差を量子化する量子化方式を含む、請求項１３記載の装置。
【請求項１８】
デジタルデータ圧縮における最適レート／歪み性能のためのビットを割り当てる装置であって、
データストリームが供給され、該デジタルデータ圧縮に応じてデータストリームの部分の組の各部分に対し選択された相互接続された量子化方式の組を決定するようにプログラミングされたプロセッサを有し、
該プロセッサは、該選択された量子化方式の中の最初の量子化方式を定義し、該最初の量子化方式から始めて、必要なすべての量子化方式を定める第１のパスが見つかるまで、最小コスト波を伝搬させるように更にプログラミングされ、
該プロセッサは、不完全な最小コストパスから始めて、必要なすべての量子化方式を定める第２のパスが見つかるまで、最小コスト波を伝搬させるように更にプログラミングされ、
該プロセッサは、該第１のパスと該第２のパスのうちの最小コストのパスによって定められた該選択された量子化方式の少なくとも一部に基づいて、データ圧縮を実施するように更にプログラミングされている、
装置。
【請求項１９】
該データストリームは映像データストリームである、請求項１８記載の装置。
【請求項２０】
該量子化方式はビデオ画像の四分木分割を含む、請求項１９記載の装置。
【請求項２１】
該量子化方式は動きベクトルフィールドを表現する量子化方式を含む、請求項１９記載の装置。
【請求項２２】
該量子化方式は該データストリームの値の間の差を量子化する量子化方式を含む、請求項１３記載の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
（技術分野）
本発明は、データ圧縮に係り、特に、最適な量子化方式を選択しようとする圧縮処理をより効率的にすることを目的とする圧縮体系に関する。
【０００２】
大量のデータを蓄積し伝送することは永遠の課題である。例えば、デジタル化された映像のデータ量は極めて大量であり、冗長で重要ではない情報を捨てる実際的な方法がない場合、殆どの装置の記憶容量及び伝送容量を詰まらせることになるであろう。これはデータ圧縮の問題であり、かなり正確に予測され得るデータストリームに関する情報を蓄積するか、又は、伝送するかについて悩む必要がない。予測の精度が１００％であるならば、圧縮方式は「無損失」と呼ばれる。１００％未満の精度であるならば、その圧縮方式は「損失のある」と呼ばれる。
【０００３】
データストリームの圧縮は他の環境でも使用される。例えば、画像は損失のある方法で圧縮され得る。ある周知のタイプの画像圧縮であるＪＰＥＧ（ジョイント・フォトグラフィック・エキスパート・グループ）は、画素の値を予測し、所定の品質レベルで蓄積若しくは伝送されるべきデータ量を削減するため、近隣画素の間の相関を有利に利用する。この他にも多数の損失のある圧縮方式がある。
【０００４】
損失のある方式は、その名の示す通り、原物の完全な無損失表現を生成し得ない。殆どの圧縮方式では、許容最大歪みレベルを予め選択し、その許容最大歪みレベルを達成するために要求されるデータの最小量（ビットレート）を蓄積若しくは伝送することができる。或いは、ビットレートは、予め選択し、歪みは、指定されたビット予算に対して最小限に抑えられる。
【０００５】
歪みは、データ圧縮のタイプに依存する概念であり、主観的な規準を含み得る。例えば、所与の圧縮／伸長サイクルで生じる歪みの程度は、一方で、人の視覚系に依存する。例えば、人は、ルミナンス（画像の部分の相対的な明るさ及び暗さ）と同じディテールでカラーを見分けない。その結果として、知覚された品質に殆ど寄与しないデータが知覚された品質により大きく寄与するデータよりも先に捨てられるようにデータストリームを歪ませることは、圧縮のための最適な解決法である。（明らかに、画質に影響を与えないデータ、即ち、冗長なデータは、このリストの先頭にくるであろう。）この圧縮アプローチは、「レート歪み圧縮」に対する「最適ビット割り当て」と呼ばれる「最適化問題」を規定する。最適性を定義するものについての主観的な考え方に加えて、最適性にはより具体的な局面もある。例えば、全体的な最適化を達成するため、データストリームの一部分を犠牲にし、その他の部分を強調することにより、平均歪みを最小限に抑えることを選択することができる。或いは、データストリームの中の指定されたすべての部分の最大歪みを最小限に抑えることができる。最適性の規準は、このように複雑な進化中の概念であり、本明細書では、任意の具体的なメトリック（規準）を表すことが意図されている。
【０００６】
かなり以前から、映像データは、少ない知覚歪みによる圧縮のための優れた候補であることが知られている。技術的に説明すると、未加工の生データはエントロピーが非常に低く、時空間の所与の位置は、時空間の他の部分から高い確率で予測可能である。例えば、最初のフレームは、高速ペースの映像シーケンスの場合でも、次のフレームと非常に類似しているように見える。
【０００７】
非常に様々な方式が映像を簡潔に定義するため提案された。例えば、映像フレームは、前のフレームから移動した画像の各セグメントの場所と、動きデータだけからフレームを再生することにより失われたディテールだけを含む差フレームという形で定義することができる。この技術を使用する圧縮方式は、動き補償映像符号器（ＭＣＶＣ）と呼ばれる。合成データストリームは、非常に簡潔である。なぜならば、映像の順次フレームにおける変化の殆どは、カラーとルミナンスのフィールドを徐々にシフトすることによって特徴付けることができるからである。
【０００８】
映像データを圧縮する様々な方式のうちの殆どは、合わせて使用される。オーディオ、静止画像、及び、その他の種類のデータを圧縮する多数の方法がある。最適化問題は、情報が時間的若しくは空間的に隣接している信号の部分から収集されるこれらのいわゆる予測型方式の場合には複雑化する。未加工データをそのデータを表現するある種のシンボルで置き換えることは、圧縮方式に内在する事項である。例えば、単一のデータがデジタルデータに変換されるとき、送信機（又は記憶装置）は、精度と消費の間のトレードオフを解決しなければならない。精度が高くなると、要求されるデータが増加する。これは、「量子化方式」の間における簡単な選択の例である。最新データ圧縮問題には、より複雑な選択の問題が含まれる。例えば、映像フレームの一部分の動きを伝送することによって映像ストリームを表現するＭＣＶＣにおいて、量子化方式の選択は、動きベクトルによって効率的に表現できる部分のサイズを選択する問題を含む。一つのフレームを移動する部分に分割する方法の選択は、次に続くフレームの予測値に影響を与える。その結果として、未加工データをシンボルへ翻訳する方法の時間的又は空間的な選択の系列において歪みの量が増加し、データストリームのある部分に対する量子化方式の選択がデータストリームの他の部分の歪み（若しくはビットレート）に影響を与える複雑な計画問題が生じる。
【０００９】
（発明の開示）
一部の映像圧縮方式では、動的プログラミング（ＤＰ）と呼ばれるツールの使用が、このような圧縮方式によってもたらされる最適化問題を解決するために提案されている。ＤＰはロバスト性を備えているが（即ち、いつも正常に動作するが）、計算集約的である。それ故に、最適化の質が損なわれるか、又は、最適化を計算するためのコストが高くなる。かくして、従来の技術では、レート歪み圧縮方式によって課された最適化問題を少ない計算負荷で解決する方法が求められている。
【００１０】
要約すると、映像圧縮処理は、有向グラフにおけるパス最適化問題として最適化問題を設定し、有向グラフ内で最小コストパスを検出することにより、データストリームを圧縮する量子化方式の選択を最適化する。有向グラフは、コンフィギュレーション空間とみなすこともできる。この処理は、開始ノード（若しくは「状態」）から始まり、パスが最終的に完成するまで空間内に最小コスト波を伝搬させる。よりコストの小さい部分、若しくは、未完成パスは、比較され、最良のものが使用される。この処理は、時間的制約のある処理の場合には、時間が切れるか、又は、最適パスに寄与するすべての可能性が尽くされるまで、継続する。
【００１１】
圧縮方式は、量子化方式がデータストリームの損失のある圧縮中にレート若しくは歪みを最適化するため選択される場合に生じる制約付き最適化問題から始める。従来技術の場合と同様に、この方式は、所与の最大歪みに対する最小ビットレートを選択するか、又は、所与の最大ビットレートに対する最小歪みを選択することにより、レート−歪みを圧縮しようとする。しかし、本発明によれば、この最適化問題は、A*パスプランニングとして知られているパス最適化を使用して解決され、これにより、幾つかの利益が得られる。第一に、動的プログラミングに対して、このパスプランニングは、時間制約付き環境において獲得されるべき準最適パスの継続的な改善を行うことができる。なぜならば、このパスプランニングは、大域的な最適パスへ導くため、許容可能な発見的手法（楽観的予想）を使用するからである。第二に、このパスプランニングは、網羅的な膨張を伴うことなく、考えられるすべてのパスを最適化することができるので、動的プログラミングよりも計算の効率が高くなる。
【００１２】
一般的に、本発明によれば、量子化方式の最適化は、パス最適化問題に翻訳され、パス最適化問題は、A*パスプランニングを使用して解決される。A*パスプランニングは、参考のため全体がここに引用されている以下の文献：
米国特許第５，２２０，４９７号  "Method  and  apparatus  for  controlling  high  speed  vehicles"
米国特許第５，０８３，２５６号  "Path−planning  with  transition  changes"
米国特許第４，９４９，２７７号  "Differential  budding:  method  and  apparatus  for  path−planning  with  moving  obstacles  and  goals"
米国特許第５，８７０，３０３号  "Method  and  apparatus  for  controlling  maneuvers  of  a  vehicles"
米国特許第５，８０８，８８７号  "Animation  of  path−planning"
米国特許第５，６９６，６７４号  "Computer  animation  of  planned  path  in  changing  space"
米国特許第５，５３９，６４５号  "Traffic  monitoring  system  with  reduce  communications  requirements"
を含む多数の刊行物に記載されている。
【００１３】
これらの特許には、空間変形メトリックを使用して、バディング(budding)によってコンフィギュレーション空間内にコスト波を伝搬させることにより最適パスが決定されるパスプランニングの処理が記載されている。バディングは、コンフィギュレーション空間内の所定のノードの各近傍から（或いは、所与のノードの近傍へのスタートから）ゴールへ到達するための総コストを計算する処理を意味する。バディングは、そのポイントまでに検出された最小コストパス上に存在するノードの近傍に対して常に実行される。かくして、バディングの処理は、コンフィギュレーション空間内に最小コストの波形を伝搬させることとして記載されている。この処理は、本例に適用される。なぜならば、最適ビット割り当て問題は、上記の文献に記載されているように、コンフィギュレーション空間におけるパスプランニング問題を定義するからである。
【００１４】
圧縮の環境における量子化方式を最適化がパスプランニング問題を引き起こす理由を理解するため、簡単な画像圧縮問題を考える。画像は、ある任意の圧縮プロトコルに応じて、左側半分と右側半分の二つに分割される。ある任意の要求によれば、この問題は、画像が画像の歪みを最小限に抑えたままである所定のビット数Ｎに圧縮されるように、量子化方式を選択することである。片側ずつには一つの選択肢、即ち、量子化方式があり、一つの選択肢は、１ビットで画素のルミナンスを表現し、別の選択肢は、２ビットで画素のルミナンスを表現する。１ビット量子化方式の場合、画像歪みは大きくなるが、要求されるデータ量は少なくなる。２ビット量子化方式の場合、歪みは小さくなるが、要求されるデータ量は増える。
【００１５】
上記の例における最適化問題は、画像の片側毎に、ビットの総数がＮよりも少なくなり、歪みを最小限に抑える量子化方式を見つける問題に過ぎない。歪みは、公知の技術によって計算される。これらの技術は、全体画像（若しくは映像）歪みを計算する際に、観察者にはっきり見えるタイプの歪みよりも重くない重みが観察者にとって見えやすくないタイプの歪みに重み付けされるように、人の知覚的バイアスを考慮するように発展している。平均２乗誤差のようなその他の数値的技術を利用してもよい。画像の歪みを計算する論点は、本明細書ではこれ以上展開されない。なぜならば、この話題は、成熟した技術的テーマであり、本発明と直接的な関係がないからである。
【００１６】
明かりが灯っていない部屋の方へ開かれた扉の画像のように、画像の左側の大部分が非常に暗い場合、画素のルミナンスを黒又は白として表現する単一ビットを使用して画像の左側が符号化されるならば、殆ど損失は生じない。右側では、扉の特徴は、２ビットのルミナンス表現によって実現可能である４段階のルミナンスを使用することによって表現する方が有利である。左側画素のため１ビットを使用し、右側画素のため２ビットを使用する方が、反対のビット数を使用するよりも歪みが小さくなることは明らかである。パスプランニング問題は、ノードの割り当て（マップ）によって表現され、各ノードは、画像の領域への量子化方式の割り当てを表現する。パスは、画像の左側に対応した唯一のノードを通り、画像の右側に対応した唯一のノードを通る必要がある。パスをどのようにプロットするかについての選択は、画像領域の画素を記憶するために要するビット数に関して、並びに、圧縮画像の歪みに関して、ある程度のコストを生じる。本例の場合、パス最適化問題は、許容された最大ビット数Ｎ以下を維持したまま、最小歪みが得られるパスを選択することである。
【００１７】
A*パスプランニングは、開始ポイント及び終了ポイントを格納するトポロジーを用いて、アルゴリズムの初期化から始まるこのパス最適化問題を解決する。本例の場合、これは、上述のノード以外の２個の補助的なノードである。ノードは、許容されたパスと相互接続される。簡単な画像圧縮の例題では、画像の左側用の１及び２ビット量子化方式を表現するノードは接続されないが、左側用の１ビット量子化方式を表現するノードは、右側の量子化方式を表現する両方のノードに接続される。A*アルゴリズムは、比喩的に説明すると、各ノードからすべての隣接ノードへ１ステップを取り出し、そこまでのステップから要求された総歪みと総ビットを計算する。これは、近接ノードの拡張、又は、最小（歪み）コストの波の伝搬と呼ばれる。総ひずみ値は、ヒープとして知られているコンピュータ・ソフトウェア要素によって管理される。ヒープは、最小歪みが常にヒープの最上部にくるように総ひずみ値を分類する。すべての近接ノードが拡張された後、要求されたビット総数が問題によって与えられた限界よりも小さい場合、アルゴリズムは、ヒープの最上部の値に対応するノード（即ち、最小歪みを生ずる最下位ノード）へ進む。このアルゴリズムは、次に、すべての新しい近傍を拡張し、現在ノードによって定められた量子化値に対応した累積的な歪みをヒープに格納する。このアルゴリズムは、次に、ヒープの最上部にあるノードを選択し、その近傍を拡張する。これは、現在ノードが以前に拡張されたノードであることを意味するか、又は、現在ノードが１回目の拡張のため選択されたノードに沿ってパスを更に推し進めることを意味する。この処理は、処理の完了が宣言されるポイントである最終ノードへ到達するまで継続する。この暫定的な最終結果は、典型的に準最適パスであり、時間制約付き問題において新しいパスを拡張するために十分な時間がない場合には最終結果として使用することができる。さもなければ、この準最適解は採用されず、できる限り、現在の最適パスの歪みよりも小さい歪みをもつ別のパスが見つけられるまで、補助的なパスが拡張される。ヒープの最上部の歪み値が目標の準最適歪みと一致した場合、パスはそれ以上改良されない。かくして、網羅的な探索は不要であると共に、最適パスの検出が保証される。
【００１８】
上記の普通の画像圧縮問題において、ノードに対応する歪みは、他のノードがパス上のポイントとして選択されたかどうかによって影響されない（依存性がない）ことに注意する必要がある。より現実的なレート歪み圧縮問題の場合、通常、依存性が生じる。このような量子化方式は依存型量子化方式と呼ばれる。例えば、この依存性は、ある領域の量子化方式が隣接領域における所与の量子化方式で獲得された歪み結果に影響を与えるように、画素値が差動的に符号化された場合に現れる。相互関係又は依存性は、グラフ構造によって与えられる。また、用語「量子化方式」は、本願明細書では、単に等級スケールの量子化を意味するだけではなく、画像若しくは映像シーケンスのデータを符号化する処理の際に画像若しくは映像シーケンスをモデリングするため使用されるすべての方法を表すために使用される用語であることに注意する必要がある。したがって、例えば、「量子化方式」は、動き補償モデリングのための画像若しくは映像フレームの四分木分割の選択を表す。勿論、本発明は、画像及び映像シーケンスの様々なモデリング方法を予期しているが、但し、パスプランニング問題を定義する最適化問題はある種の特性をもつことが想定されている。その特性には、パス空間がノードにより構成された有向グラフによって定義され、ノードはノード間で遷移することが許容されること、遷移に対するコストが計算可能であること、コストは、遷移と遷移の間で単調（単調増加若しくは単調減少）に累積するか、若しくは、零を維持し、コストは評価済みの先行ノードの関数であること、が含まれる。これらの要件が満たされる場合、A*アルゴリズムを実施することが可能であり、上述の結果が自動的に獲得される。
【００１９】
以下、本発明は、添付図面を参照して、ある種の好ましい実施例と共に説明されるので、十分に理解されるであろう。添付図面に関して注意すべきことは、詳細な記載は、一例として用いられているものであり、本発明の好ましい実施例の説明することだけを目的とするものであること、並びに、詳細な記述は、本発明の原理及び概念的な局面の最も有用で、かつ、容易に理解できる説明であると考えられる記述を与えるために提示されていること、である。この点に関して、本発明の構造的な詳細については、本発明の基本的な理解のために必要以上に詳しく提示することは試みられていない。図面と共に説明を読むことによって、当業者は、本発明の幾つかの形態が実際に具現化される態様がわかるであろう。
【００２０】
図１には、本発明の開示の欄で説明した簡単な例によって得られたグラフ９０が示されている。ブロック１０、２０、３０及び４０は、ノードを表している。ノード１０は、左側でビットを符号化するため使用される１ビット量子化方式の選択を表し、ノード２０は、右側でビットを符号化するため使用される１ビット量子化方式の選択を表す。ノード３０は、左側でビットを符号化するため使用される２ビット量子化方式の選択を表し、ノード４０は、右側でビットを符号化するため使用される２ビット量子化方式の選択を表す。開始ノードＳ及び終了ノードＥは、それぞれ、最適化問題の開始ノード及び終了ノードを表すように定められている。ノード１０乃至４０とノードＳ及びＥを含む各ノードは、従来技術では「遷移」とも呼ばれる有向線分によって別のノードと連結される。遷移４５、５０、５５、６０、６５、７０、７５及び８０を示す線分は、矢印によって示されるように左から右へ向かう進行方向だけが許可される。各ノード１０乃至４０は、歪みコストと関連付けられる。発明の開示の欄で説明したように、各ノード１０乃至４０は、対応した画像部分（Ｌ，Ｒ）を符号化するためのビット所要量とも関連付けられる。現時点までに要求された総ビットはノード内に保持される。
【００２１】
グラフ９０とヒープ（図示しない）の初期化後（開始ノードＳは、零歪み（コスト）と零ビット所要量をもつ）、A*アルゴリズムは、近接ノード１０及び３０の各々について、歪み及びビット所要量（即ち、ノードＳから当該ノードまでの歪みの合計）を計算することから始まる。ノードに対する総ビット所要量が規定された上限に満たない場合、総歪み（及び当該ノードへのポインタ）がヒープに設定され、より小さい総歪みに対応するノードが最上部に現れる。歪みが小さい方のノードがノード１０であるならば、次に、近傍ノード２０及び４０が拡張される。即ち、各近傍ノードに対応した歪み及びビットレートが計算され、ノード１０に対する基本歪み及びビットレートに加算される。このように、ノード２０の歪みは、ノード１０とノード２０とノードＳの歪みの総量と一致し、ノード４０の場合も同様である。ビットレートに対する総量も同じように計算される。両方がビットレート予算に満たない場合、総歪みの値がヒープに設定される。さもなければ、ビット予算の範囲に収まるパスに対応した歪み値だけがヒープに設定される。各ノード内では、最良の「親」ノードへのポインタが保持される。親ノードは、最小コストを与えたノードである。本例の場合、親ノードは、各ノードの左側のノードであり、矢印８１乃至８５によって示されている。最終パスは、ノードＥからノードＳまで追跡され、最適パスを与えるために反転される。両方のパスがビット予算内に収まる場合、二つの最終結果のうちの小さい方が暫定的な最適化されたパスである。
【００２２】
最適化問題は、圧縮演算に対し制限時間を付けることがある。制限時間までに時間が残っている場合、ノード３０の近傍ノードは、総歪みが終了ノードＥにおける歪みよりも小さいならば、拡張される。仮想的な例では、遷移７０及び８０に対応するレートと歪みは、遷移５０及び７５に対するレートと歪みに一致するが、一般的には、このような条件は成り立たず、圧縮問題に依存する。この処理は、ノード１０に関して継続し、その結果として、ノード２０及び４０における値は改善されないので、これらはヒープに追加されない。総歪みの小さい方のノード（本例では、ノード４０の方が小さいノードである。）は次に拡張される。遷移６０の遷移コストは零であるため、ノードＥまで達する。これは、探索の終了を知らせる。ヒープ内に、ノード４０の値よりも小さい他の値が存在する場合、探索を更に進めることが可能である。本例の場合、終了ノードは代役であり、遷移５５及び６０は、増分的なレート若しくは歪みと関連付けられることがなく、探索は、ノード２０とノード４０のいずれにも達しないとき、そのままノードＥへ進む。できるだけ多数の探索が行われた後、本例では、二つの考えられる遷移の各々に対して唯一の拡張を実施可能であり、最小総歪みコストを与える親ノードが選択される。
【００２３】
図２は、発明の名称が"Method  and  device  for  optimal  bit  allocation  between  different  sources  of  information  in  digital  video  compression"であり、参考のため全体がここに引用される米国特許第５，７７８，１９２号からの図面であり、映像圧縮によって特定された最小コストパス探索問題が説明されている。図２のグラフは、３２画素×３２画素の画像ブロックに対する許容された量子化方式の選択を表す多重レベルトレリスを表現する。ブロックは、レベル３まで展開することが許可された四分木構造を用いて分割されている。四分木構造は、白抜きの長円形１１５、１２０及び１２５に対応し、各白抜きの長円形はノードの組、例えば、黒い丸で示されたノード１１０、１３０及び１４０を指定する。尚、図面が過度に混み合うことを避けるため、代表的な長円形とノードだけに参照番号のラベルが付けられている。各組には、２個のノード１１０、１１１、１１２、１３０及び１４０だけが示されているが、ノードの個数は幾つでもよく、ノードの個数は、様々なレベルにおける個別のブロックの許容状態値の個数に対応する。即ち、各ノードは、映像ストリームの特定の局面に対する量子化方式の選択に対応する。上述の特許文献に記載された体系は、動き補償体系である。そのような体系の場合、補助ノードである開始ノードＳ及び終端ノードＺは、動きベクトルの差動パルス符号変調（ＤＰＣＭ）を初期化し、レート／歪みの観点から最小総コストをもつパスを選択するため使用される。
【００２４】
上述の特許文献に記載されているように、目標は、トレリスの中で、最小総レート／歪みコストに対応するパスを特定することである。このパスは、許容された遷移、例えば、遷移１００、１０１及び１０２から形成される。これは、有効ビット予算を多種多様なデータの間で割り当てる問題に帰着する。上記の特許文献からの例の場合、特定の種類の圧縮体系には、セグメンテーションと、動きベクトルと、予測誤差の三つの重要なタイプのデータが含まれている。本発明を理解する目的のために圧縮体系の詳細は重要ではない。なぜならば、多数の圧縮体系は、トレリスとして表現できないとしても、このようなグラフ探索問題を生じるからである。あらゆるケースにおいて複雑な最適化問題が生じる。なぜならば、特定のタイプのデータのあるビットを捨てることにより影響を受ける歪みの量は、別のタイプのデータを表現する別のビットを捨てることにより影響を受ける歪みの量と一致しないからである。基本的な目的は、所与のフレーム若しくは映像シーケンスをレート−歪みの意味で最適的に符号化することである。即ち、所定の符号化体系のビット予算の条件で、ビットを最適割り当てすることにより、考えられる最小歪みが実現され、逆もまた同様である。本発明のために、符号化体系の詳細、及び、符号化体系から得られるグラフ探索問題の詳細は、グラフ検索問題が以下の特性を備えている限り重要ではない。
【００２５】
パス空間のトポロジーは、ノード間にある種の遷移が許容されるノードの組からなる有向グラフを規定する。一部のノードは、他のノードから到達不可能であり、循環的な接続が許可される。
【００２６】
最適化されるべきコストは遷移毎に定義してもよい。コストは非負で無ければならない。
【００２７】
コストは単調増加するか、又は、単調減少しなければならない。
【００２８】
開始条件と、少なくとも一つの目標若しくは終端条件とが必要である。しかし、これらの条件は、上述の簡単な例と同様に任意に定義することが可能である。
【００２９】
次に、図３を参照すると、開始ノードＳの近傍が最初に拡張されている。これは、最小コスト波の段階的伝搬における第１のステップである。ビットレート及び歪みは、開始ノードＳの近傍を取り囲む各遷移１４７、１４８、１４５、１４６、１４９及び１５１に対して計算される。レートが計算され、各ノードに格納される。各ノードから開始ノードへのポインタも付加される。ノード１３０への遷移１４５がビットレート上限よりも下を維持している最小歪みコストに対応していると仮定すると、ノード１３０は、ヒープの最上部に上昇し、ノード１３０の近傍が図４に示されるように拡張され、コスト及びレートが新しい遷移の組１７３毎に計算される。更に、最良パスの親ノードも特定される。同図において、親ノードの矢印は図面を簡単化するために省略されている。この処理は、図５に示されるように、終了ノードＺに達する最終的な最適化されたパス２１０が見つかるまで継続する。再度、この処理は、残りの最小総コストノードから始めて、
総コストが終了ノードＺの総コスト以上になるという他の制約によって阻止されている状況に至らない限り、より大域的な最適解を探し続けることができる。
【００３０】
図６には、データストリームに上記処理を実施する装置が例示されている。データソース３１０は、データストリームをプロセッサ３００へ供給する。プロセッサ３００は、本発明に従って量子化方式を最適化する圧縮アルゴリズムを実施するようにプログラミングされている。プロセッサは、圧縮ビデオデータストリーム３２０を出力する。
【００３１】
図７は、圧縮処理に制限時間若しくは処理リソース制限を加える環境でデータストリームが圧縮される処理を説明するフローチャートである。新しいデータの組がステップ１０で受け取られる。例えば、ビデオフレームは、ステップ１０における処理のため受け取られる。タイマーは、ステップ１５で初期化される（又は、処理リソース量子化方式）。タイマーは、ステップ２０で満了したかどうかを検査され、時間（又は、処理リソース）が残っている場合、新しい最適パスがステップ２５で説明された最適パスアルゴリズムに従って伝搬される。処理フローは、新しいデータの組を入力するためステップ１０へ戻る。ステップ２０において、タイマーが時間切れになった場合、ステップ２５の反復毎に検出されたパス候補の中から、ステップ３０において、最良（最小コスト）パスが特定される。次に、ステップ３５において、データは、ステップ３０で特定された量子化方式に従って圧縮され、圧縮されたデータが出力され、処理フローはステップ１０へ戻る。
【００３２】
当業者に明らかであるように、本発明は、上記の説明のための実施例の細部に限定されるものではなく、本発明は、本発明の精神若しくは不可欠な属性から逸脱することなく、その他の具体的な態様で具現化できる。本発明の実施例は、あらゆる観点から見て、例示のためのものであり、限定のためのものではなく、本発明の範囲は、実施例の説明ではなく、特許請求の範囲に記載された事項によって示されるものであり、請求項に記載された事項と均等な意味及び範囲に含まれるすべての変更は、請求項に記載された事項に含まれることが意図されている。
【図面の簡単な説明】
【００３３】
【図１】本発明を説明するための仮想的な画像圧縮方式のパス最適化問題の説明図である。
【図２】本発明を説明するための典型的なパスプランニング問題を解決する第１ステージの説明図である。
【図３】図１のパスプランニング問題を解決する第２ステージの説明図である。
【図４】図１のパスプランニング問題を解決する第３ステージの説明図である。
【図５】図１のパスプランニング問題を解決する最終ステージの説明図である。
【図６】本発明の一実施例によるデータ圧縮装置のブロック図である。
【図７】本発明の一実施例による圧縮方法のフローチャートである。
【図１】
2004532558.tif 000003
【図６】
2004532558.tif 000004
【図７】
2004532558.tif 000005
【国際公開パンフレット】
2004532558.tif 000006
2004532558.tif 000007
2004532558.tif 000008
2004532558.tif 000009
2004532558.tif 000010
2004532558.tif 000011
2004532558.tif 000012
2004532558.tif 000013
2004532558.tif 000014
2004532558.tif 000015
2004532558.tif 000016
2004532558.tif 000017
2004532558.tif 000018
2004532558.tif 000019
2004532558.tif 000020
2004532558.tif 000021
2004532558.tif 000022
2004532558.tif 000023
2004532558.tif 000024
2004532558.tif 000025
2004532558.tif 000026
【国際公開パンフレット（コレクトバージョン）】
2004532558.tif 000027
【国際調査報告】
2004532558.tif 000028
2004532558.tif 000029
2004532558.tif 000030