(57)【要約】【課題】年代順を回避し、最適化された圧縮度を得るように画像を符号化することを可能にする、ビデオドキュメントを圧縮するためのプロセス及び装置を提供することである。【解決手段】上記課題は、画像の各グループの符号化のコストを最小化する画像の各グループに対する最小スパニングツリーの計算のステップ、最小スパニングツリーにより与えられる順序で画像をブラウズすることによる画像の各グループの符号化のステップを有することによって解決され、さらに、最小スパニングツリーの計算の手段、画像の各グループの符号化の手段を有することによって解決される。【選択図】図２
2006020330.tif 000002
【特許請求の範囲】
【請求項１】
ビデオドキュメントを圧縮するためのプロセスであって、
ショットへのビデオドキュメントの分解（１）のステップを有し、
前記ショットを代表する画像の抽出（２）のステップを有し、
前記代表画像の間の距離の測定（３、４）のステップを有し、
画像のグループへの所定の閾値よりも小さい距離の画像のグループ化（５）のステップを有し、
画像のグループの他の画像に関して各画像の符号化の相対的コストの計算（６）のステップを有する、ビデオドキュメントを圧縮するためのプロセスにおいて、
該プロセスは、
画像の各グループの符号化のコストを最小化する、画像の各グループに対する最小スパニングツリーの計算（７）のステップを有し、
前記最小スパニングツリーにより与えられる順序で画像をブラウズすることによる画像の各グループの符号化（８）のステップを有する
ことを特徴とする、ビデオドキュメントを圧縮するためのプロセス。
【請求項２】
スパニングツリーの最初に符号化される画像はイントラモードで符号化されることを特徴とする、請求項１記載のプロセス。
【請求項３】
最初の画像以外の画像は最適スパニングツリーにおける前の画像に関して予測モードで符号化されることを特徴とする、請求項１又は２記載のプロセス。
【請求項４】
スパニングツリー内で離れて配置される幾つかの画像はイントラモードで符号化されることを特徴とする、請求項１記載のプロセス。
【請求項５】
ビデオドキュメントを圧縮するための装置であって、以下の手段（９）を有し、すなわち、
ショットへのビデオドキュメントの分解、
前記ショットを代表する画像の抽出、
前記代表画像の間の距離の測定、
画像のグループへの所定の閾値よりも小さい距離の画像のグループ化、
画像のグループの他の画像に関して各画像の符号化の相対的コストの計算（６）
の手段（９）を有する、ビデオドキュメントを圧縮するための装置において、
該装置は、
画像の各グループの符号化のコストを最小化する、画像の各グループに対する最小スパニングツリーの計算の手段（９）を有し、
前記最小スパニングツリーにより与えられる順序で画像をブラウズすることによる画像の各グループの符号化の手段（１２）を有する
ことを特徴とする、ビデオドキュメントを圧縮するための装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオドキュメントを圧縮するためのプロセスであって、ショットへのビデオドキュメントの分解のステップを有し、ショットを代表する画像の抽出のステップを有し、代表画像の間の距離の測定のステップを有し、画像のグループへの所定の閾値よりも小さい距離の画像のグループ化のステップを有し、画像のグループの他の画像に関して各画像の符号化の相対的コストの計算のステップを有する、ビデオドキュメントを圧縮するためのプロセスに関し、さらに本発明は、ビデオドキュメントを圧縮するための装置であって、以下の手段を有し、すなわち、ショットへのビデオドキュメントの分解、ショットを代表する画像の抽出、代表画像の間の距離の測定、画像のグループへの所定の閾値よりも小さい距離の画像のグループ化、画像のグループの他の画像に関して各画像の符号化の相対的コストの計算の手段を有する、ビデオドキュメントを圧縮するための装置に関する。とりわけ、本発明は、保存に適したビデオ圧縮に関するものである。
【背景技術】
【０００２】
ビデオドキュメントの圧縮制約条件は、伝送のためのビデオ圧縮に関する場合よりもビデオ保存に関する場合には有意ではない。
【０００３】
特に、リアルタイムで圧縮され、伝送され、伸長されるビデオは、例えばＭＰＥＧ−２のような符号化方法によって行われるように、年代順に次から次へと画像を取り出すことによって圧縮されなければならない。
【０００４】
画像が、例えばハードディスクのような長期間ストレージのための格納媒体に記録される場合、格納される情報量を最適化するためにはどんな順序でこれらの画像を圧縮することも可能であり、従って必要とされるストレージリソースを最小化することが可能である。それゆえ、圧縮制約条件はリアルタイム符号化／復号化の場合とは同じではない。
【０００５】
本発明は、それゆえ、圧縮度を増大するために符号化の前にビデオドキュメントの画像を配列することに関する。実際、データ圧縮の幾つかの方法はクラスタへのグループ化を使用する。しかし、一度クラスタが完成されると、符号化は画像に直接的にこれらの年代順に実施される。
【０００６】
公知技術として、ショットへビデオを分割する様々が方法が存在し、図２のステップ１により図示されている。このような方法は特にＴｈｏｍｓｏｎ  Ｌｉｃｅｎｓｉｎｇ  ＳＡ社の名の下に２００２年１０月２８日に提出されたフランス特許出願０２１３９７８に記述されている。この特許出願は各ショットにおけるキーとなる画像（key image）の抽出（図２のステップ２）も記述している。１つ又は複数のキー画像が各ショットから抽出され、これはショットの動きの量に依存し、考慮すべき動きを示すショットは１個より多くのキー画像によって特徴付けられうる。
【特許文献１】フランス特許出願０２１３９７８
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の課題は、年代順を回避し、最適化された圧縮度を得るように画像を符号化することを可能にする、ビデオドキュメントを圧縮するためのプロセス及び装置を提供することである。
【課題を解決するための手段】
【０００８】
上記課題は、ビデオドキュメントを圧縮するためのプロセスにおいて、
画像の各グループの符号化のコストを最小化する画像の各グループに対する最小スパニングツリーの計算のステップを有し、
最小スパニングツリーにより与えられる順序で画像をブラウズすることによる画像の各グループの符号化のステップを有する
ことによって解決され、
さらに、上記課題は、この方法を実施するための装置において
画像の各グループの符号化のコストを最小化する画像の各グループに対する最小スパニングツリーの計算の手段を有し、
最小スパニングツリーにより与えられる順序で画像をブラウズすることによる画像の各グループの符号化の手段を有する
ことによって解決される。
【発明を実施するための最良の形態】
【０００９】
本発明は、
ショットへのビデオドキュメントの分解のステップを有し、
ショットを代表する画像の抽出のステップを有し、
代表画像の間の距離の測定のステップを有し、
画像のグループへの所定の閾値よりも小さい距離の画像のグループ化のステップを有し、
画像のグループの他の画像に関して各画像の符号化の相対的コストの計算のステップを有する、ビデオドキュメントを圧縮するためのプロセスに関する。
【００１０】
本発明によれば、このプロセスは、
画像の各グループの符号化のコストを最小化する、画像の各グループに対する最小スパニングツリーの計算のステップを有し、
最小スパニングツリーにより与えられる順序で画像をブラウズすることによる画像の各グループの符号化のステップを有する。
【００１１】
最小スパニングツリー（minimum spanning tree）は画像の符号化の順序を変更し、これにより圧縮度を改善することを可能にする。これは、とりわけ符号化時間が重要ではなくかつ符号化の順序が重要ではない保存のための圧縮には適している。しかし、この最小スパニングツリーは独占的にこのような圧縮のためのものではない。
【００１２】
有利な実施形態によれば、スパニングツリーの最初に符号化される画像はイントラモードで符号化される。
【００１３】
有利な実施形態によれば、最初の画像以外の画像は最適スパニングツリーにおける前の画像に関して予測モードで符号化される。
【００１４】
有利な実施形態によれば、スパニングツリー内で離れている幾つかの画像はイントラモードで符号化される。
【実施例】
【００１５】
本発明は、添付した図面との関連において実施例及び実装の完全に無制限な有利なモードによってより良好に理解され図示されうる。本発明の実施例を以下において図面に基づいて記述する。
【００１６】
ビデオドキュメントは一連の画像から成り、これら自体はしばしばショットにグループ化されうるものであり、これらのショットはピクチャブレイクに相応する。
【００１７】
図１はショットＰ１、Ｐ２、Ｐ３、.....Ｐ１０へのビデオドキュメントの分割を表す。図１は図２とパラレルに記述され、この図２は図１に図示されたビデオドキュメントの分割を行うことを可能にするプロセスのステップを示している。
【００１８】
ショットへとビデオを分割する様々が方法が存在し、図２のステップ１により図示されている。このような方法は特にＴｈｏｍｓｏｎ  Ｌｉｃｅｎｓｉｎｇ  ＳＡ社の名の下に２００２年１０月２８日提出されたフランス特許出願０２１３９７８に記述されている。この特許出願は各ショットにおけるキーとなる画像（key image）の抽出（図２のステップ２）も記述している。１つ又は複数のキー画像が各ショットから抽出され、これはショットの動きの量に依存し、考慮すべき動きを示すショットは１個より多くのキー画像によって特徴付けられうる。
【００１９】
その後で、これらのキー画像はそれらの相似性の関数としてグループ化される（ステップ４、図２）。
【００２０】
相似性は画像間の距離の測定により計算される。画像間の距離の測定は属性Ｆの間の距離に基づいている。
【００２１】
Ｆは、無制限な実例としては、テクスチャ、色の中から選択される画像の特性量を表す。代替例としては、ウェーブレット変換の主要な係数（dominant coefficients）も属性と見なされうる。
【００２２】
属性を計算する様々な方法が存在し（ステップ３、図２）、当業者には周知である。
【００２３】
計算される距離Ｄは実例としてはユークリッドのタイプの距離でもよい。
【００２４】
距離Ｄが例えばビデオドキュメントのタイプの関数として決定される所定の閾値εより小さい場合、画像はグループ又は「クラスタ」にグループ化される、図２のステップ５。画像のこれらのグループはこの場合有意な視覚的相似性を示す。
【００２５】
幾つかのキー画像が全く同一のショットから抽出され、さらにクラスタへのグループ化のステップの間にこれらのキー画像が同じクラスタにおいて重要な役割を演じない場合には、これらのキー画像が所属するクラスタが併合される。
【００２６】
こうして得られるクラスタの数は、相似性の測定の所定の閾値ε及びクラスタへのグループ化のために使用される方法に依存する。
【００２７】
各クラスタは一定の個数のショットの全ての画像を含む。
【００２８】
その後で、各クラスタにおける画像の各々のペア毎に、符号化のコストが計算される。
【００２９】
各画像は１つずつセレクトされ、各画像に関する符号化コスト（ステップ６、図２）が他の画像に関して評価される。
【００３０】
その後で、これらの符号化コストに基づいて、最小スパニングツリーが各クラスタ毎に計算される（ステップ７、図２）。この最小スパニングツリーは、符号化コストを最小化する、クラスタの画像のセット全体をブラウズするためのパスを見つけ出すことを可能にする。
【００３１】
最小スパニングツリーを計算するためのアルゴリズムの中から、Ｋｒｕｓｋａｌアルゴリズムが使用される。
【００３２】
他の実施形態では、Ｐｒｉｍアルゴリズムも使用されうる。
【００３３】
このようなスパニングツリーの例は図３に示されており、この図３では点がクラスタの画像を表す。
【００３４】
クラスタＣｉはＩ１からＩ７までナンバリングされた７個の画像を含む。
【００３５】
クラスタ内の全く同一のショットの画像Ｉ１〜Ｉ７は連続している（consecutive）。
【００３６】
画像Ｉ１〜Ｉ７に適用されるＫｒｕｓｋａｌアルゴリズムは図３の右側に示されたスパニングツリーを与える。
【００３７】
このスパニングツリーは、最小符号化コスト、つまり、ビデオシーケンスの最大圧縮を可能にする符号化コストを得るために画像が符号化されなければならない順序を与える。
【００３８】
スパニングツリーが各クラスタ毎に計算される時、画像はスパニングツリーとコンパチブルな順序で符号化される（ステップ８、図２）。起点画像の選択は任意であるが、最も有利な選択は最も短いイントラ符号化を有する画像を取り出すことである。一度起点画像が選択されると、残りの画像はツリーにおける下降の順序で配列される。
【００３９】
この例によれば、Ｉ４が符号化される最初の画像である。この画像はそれゆえ符号化のイントラモードによって、つまり空間的にのみ符号化される。
【００４０】
後続の画像はツリーにおける前の画像に関して予測モードによって符号化される。画像Ｉ７は画像Ｉ７に関して符号化され、画像Ｉ６は画像Ｉ３ならびに画像Ｉ２に関して符号化される。画像Ｉ１は画像Ｉ２に関して符号化され、画像Ｉ５は画像Ｉ１に関して符号化される。
【００４１】
他の例では、幾つかの画像をイントラモードで符号化することが可能である。これはとりわけクラスタが相当数の画像を含む場合である。この場合には、一定の画像が選択され、スパニングツリーにおいて規則的に離れて配置され、イントラモードで符号化される。
【００４２】
予測符号化のための幾つかのスキームが想定されうる。とりわけ提案される実施形態では、画像はＭＰＥＧ−２又はＭＰＥＧ−４規格に従う符号化スキームによって符号化される。
【００４３】
一度符号化されると、画像ならびにクラスタの構造の記述及びビデオ全体を再構成することを可能にするツリーの構造の記述が、例えばハードディスクのような格納媒体に保存される。
【００４４】
各画像は、画像を配列して、復号化の間にビデオストリームを再構成することを可能にするタイムラベルによって識別される。
【００４５】
本発明は例えばとりわけショットが規則的にリターンするプログラムに適している。これは特に画像が伝送を送るジャーナリストのショットを規則的に含むテレビマガジン又はニュースの場合に当てはまる。
【００４６】
図４は本発明が実装されるシステムを表す。
【００４７】
このシステムはカメラ１１を含む。このカメラはイベントをキャプチャし、ビデオ情報が処理ユニット９に伝達される。
【００４８】
処理ユニット９は以下のことに適している、すなわち、
・  ショットへのビデオドキュメントの分解を行うこと、
・  前記ショットの代表画像を抽出すること、
・  前記代表画像の間の距離を測定すること、
・  画像のグループに所定の閾値よりも小さい距離の画像をグループ化すること、
・  画像のグループの他の画像に関して各画像の符号化の相対的コストを計算すること、
・  画像の各グループの符号化のコストを最小化する、画像の各グループに対する最小スパニングツリーを計算すること。
【００４９】
一度これが行われると、画像順序化情報が符号化装置１２に伝送される。この符号化装置１２は保存ユニット１０にビデオ画像を伝送する前にこれらのビデオ画像を符号化するのに適している。この保存ユニット１０はハードディスク、ＤＶＤ等々であればよい。
【図面の簡単な説明】
【００５０】
【図１】代表画像のグループへのビデオの分解を表す概略図である。
【図２】本発明によるプロセスのステップを示す線図である。
【図３】最小スパニングツリーを表す概略図である。
【図４】本発明による装置のブロック線図を表す。
【符号の説明】
【００５１】
１  ステップ１  ショット分割
２  ステップ２  キー画像抽出
３  ステップ３  属性抽出
４  ステップ４  相似性の測定
５  ステップ５  グループ化
６  ステップ６  符号化コスト計算
７  ステップ７  ツリー計算
８  ステップ８  符号化
９  処理ユニット
１０  保存ユニット
１１  カメラ
１２  符号化器
Ｉ１〜Ｉ７  画像
【図２】
2006020330.tif 000003
【図３】
2006020330.tif 000004
【図４】
2006020330.tif 000005
【図１】
2006020330.tif 000006