(57)【要約】あるビデオ処理アプリケーション、とりわけ電子透かし検出（４０）では、一つのフレームを作る二つのインターレース・フィールドを（部分的に）加算する、又は平均することが必要になる。この演算は、フレーム符号化されたＤＣＴブロックの存在のためにＭＰＥＧ領域では通常ではない。本発明は、フレームメモリ又はオン・ザ・フライ逆ＤＣＴ変換を必要としない、フィールドの加算方法と装置を供給する。このために、数学的に必要とされる、逆垂直ＤＣＴ変換（３２１）及び加算（３２２）の演算は、基底変換（３２３）とともに結合される。この基底変換は、結合された演算がスパース行列（３２）との乗算に物理的に取って代わられるように選択される。前記のスパース行列の乗算は容易にオン・ザ・フライで実行される。逆基底変換（３５）は、要望される加算（３３，３４）が完了されるまで延期される。
2005501490.tif 000002
【特許請求の範囲】
【請求項１】
画像変換（ＤＣＴ）により得られた、フレーム符号化された変換ブロックの形式で受信されたインターレース・ビデオ・フレーム画像のフィールド画像の加算方法であって、
前記変換ブロックに、前記画像変換の逆変換とフィールドの加算とあらかじめ決定された基底変換とを表すスパース行列を乗算するステップと、
乗算された変換ブロックに前記のあらかじめ決定された基底変換の逆変換を行うステップとを有する方法。
【請求項２】
前記インターレース・ビデオ・フレーム画像がＭＰＥＧ符号化されたフレームで受信され、前記スパース行列が実質上
【数１】
2005501490.tif 000012
と同等であり、前記基底変換が４点離散コサイン変換である、請求項１に記載の方法。
【請求項３】
前記インターレース・ビデオ・フレームがフレーム符号化された変換ブロック及びフィールド符号化された変換ブロックの混合として受信される方法であり、さらに、前記フィールド符号化された変換ブロックに他の行列を乗算するステップと、乗算されたフィールド符号化された変換ブロックに乗算されたフレーム符号化された変換ブロックを加算するステップとを有する、請求項１に記載の方法。
【請求項４】
前記他の行列が
【数２】
2005501490.tif 000013
となり、ここでＤ４及びＤ８はそれぞれ４点及び８点離散コサイン変換である、請求項３に記載の方法。
【請求項５】
前記他の行列が実質的に
【数３】
2005501490.tif 000014
と同等である、請求項３に記載の方法。
【請求項６】
画像変換（ＤＣＴ）により得られたフレーム符号化された変換ブロックの形式で受信されたインターレース・ビデオ・フレーム画像のフィールド画像を加算する装置であり、
前記変換ブロックに、前記画像変換の逆変換、フィールドの加算及びあらかじめ決定された基底変換を表すスパース行列を乗算する手段と、
乗算された変換ブロックに前記のあらかじめ決定された基底変換の逆変換を行う手段とを有する装置。
【請求項７】
前記インターレース・ビデオ・フレーム画像が、フレーム符号化された変換ブロック及びフィールド符号化された変換ブロックの混合として受信され、さらに、前記フィールド符号化された変換ブロックに他の行列を乗算する手段と、乗算されたフィールド符号化された変換ブロックに乗算されたフレーム符号化された変換ブロックを加算する手段とを有する請求項６に記載の装置。
【請求項８】
画像変換（ＤＣＴ）により得られた、フレーム符号化された変換ブロックの形式で受信された、複数のインターレース・ビデオ・フレームのフィールドに埋め込まれた電子透かしを検出する方法であり、
前記変換ブロックに、前記画像変換の逆変換、フィールドの加算及びあらかじめ決定された基底変換を表すスパース行列を乗算するステップと、
前記の乗算された変換ブロックの、空間的に対応するものをバッファに蓄積するステップと、
蓄積された乗算された変換ブロックに前記のあらかじめ決定された基底変換の逆変換を行うステップと、
前記バッファ内の前記電子透かしを検出するステップとを有する方法。
【請求項９】
前記インターレース・ビデオ・フレーム画像が、フレーム符号化された変換ブロック及びフィールド符号化された変換ブロックの混合として受信され、さらに、前記フィールド符号化された変換ブロックに他の行列を乗算するステップと、前記の乗算されたフィールド符号化された変換ブロックの空間的に対応するものを前記バッファに蓄積するステップとを有する、請求項８に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像変換により得られたフレーム符号化変換ブロックの形式で受信されたインターレース・ビデオ・フレーム画像のフィールド画像を加算する方法及び装置に関する。
【従来の技術】
【０００２】
本発明は複数のインターレース・ビデオ・フレームのフィールドに埋め込まれた電子透かしを検出する方法及び装置に関する。
【０００３】
あるビデオ処理アプリケーションは、インターレース・ビデオ・フレームの二つのフィールドが加算されるか、平均されることが必要とされる。そのようなアプリケーションの一例として電子透かしの検出がある。国際特許出願公報ＷＯ−Ａ−９９／４５７０５は、同じ電子透かしがビデオ信号の連続したフィールドに埋め込まれている、ビデオ電子透かしシステムを開示している。このシステムの電子透かし検出器は、ビデオ信号の平均はゼロになるが、電子透かしは建設的に増すように、複数のフレームにわたってフィールドを蓄積する。
【０００４】
インターレース・ビデオ・フレームの二つのフィールドを加算する（平均する）ことはピクセル領域では通常だが、デジタル（ＭＰＥＧ）領域では通常とはかけ離れている。その理由は、ＭＰＥＧエンコーダが符号化する前に一つのフレームのフィールドを結合し、奇数フィールド及び偶数フィールド両方からの情報を含んだＤＣＴブロックからなる、いわゆるフレーム・ピクチャーを作ってもよいからである。
【０００５】
図１及び図２はこの発明の基になっている問題を描いた図を表している。図１は画像を符号化するＭＰＥＧのモードの一つを表している。フレーム符号化されたマクロブロックを含むフレーム・ピクチャーとして知られる、この符号化モードでは、二つのフィールド１１及び１２が、二つのフィールドからのラインをインターリーブすることにより、フレーム１３に結合される。両方のフィールドには同じ電子透かしＷが埋め込まれている。そのフレームは、８×８ピクセルのブロックを８×８係数のブロックに変換する、離散コサイン変換（ＤＣＴ）の対象となる。四つのＤＣＴブロックは集合的にマクロブロック１４を構成する。各ＤＣＴブロックはピクセルの半数を第一フィールド１１から及びピクセルの半数を第二フィールド１２から表す。
【０００６】
ＤＣＴ変換は線形変換なので、ＤＣＴ係数を加算する効果は対応するピクセルを加算することと同様である。それに応じ、電子透かし検出器により実行されたフレームの加算はＤＣＴ領域で行われてもよい。逆ＤＣＴ変換は蓄積が完了する後まで延期されてもよい。しかし、蓄積にはフレームメモリが必要になる。それに応じて、ＷＯ−Ａ−９９／４５７０５で開示されている、１２８×１２８の電子透かしパターンがそれぞれのフィールド上にタイル張りにされているシステムの電子透かし検出器は２５６×１２８のバッファを必要とする。
【０００７】
二つのフィールドを加算するもう一つの通常の態様はブロック毎に、それが到着したときに、逆ＤＣＴ変換を行い、そして奇数ライン及び偶数ラインを加算し、結果をメモリに蓄えることである。このオプションにはフィールドメモリ（すなわち電子透かし検出器に１２８×１２８のバッファ）のみが必要となるが、全てのＤＣＴブロックにオン・ザ・フライ（ｏｎ−ｔｈｅ−ｆｌｙ）逆ＤＣＴ変換が必要となり、実施する観点からは魅力的ではない。
【０００８】
図２は画像を符号化するもう一つのＭＰＥＧモードを表している。フィールド符号化されたマクロブロックを含むフレーム・ピクチャーとして知られる、この符号化モードでは、二つのフィールド１１及び１２が、第一のフィールド１１から８つの連続したラインを、続いて第二のフィールド１２から同じく８つのラインを取りだし、フレーム１５に結合する。このフレームはＤＣＴ変換されている。四つのＤＣＴブロックは集合的にマクロブロック１６を構成する。この符号化モードではマクロブロックはあるフィールドのブロックと別のフィールドのブロックを含む。しかし一つのＤＣＴブロックに相当する全てのピクセルは同じフィールドにある。ＤＣＴは線形変換なので、ＤＣＴ係数を加算する効果は対応するピクセルを加算することと同様である。それに応じて、各マクロブロック１６と縦に隣接した二つのＤＣＴブロックはＤＣＴ領域でともに加算されてもよい。この演算にはフィールドメモリを必要とする。逆ＤＣＴ変換は全てのフレームの蓄積が完了するまで延期されてもよい。しかし、この直接的な解決策は上述のフレーム符号化されたマクロブロックのフィールドを加算する解決策と、簡単に結合することはできない。
【０００９】
実際面では、ＭＰＥＧフレーム・ピクチャーはフレーム符号化されたマクロブロック及びフィールド符号化されたマクロブロックの混合を含んでいる。大部分（７０．．８５％）のマクロブロックはフレーム符号化されている。技術的にもっとも難しい状況はもっともありふれた状況でもある。
【００１０】
【発明が解決しようとする課題】
上述の問題を軽減する、インターレース・ビデオ画像フレームのフィールドを加算する方法と装置を供給することが本発明の目的である。
【００１１】
【課題を解決するための手段】
これらとその他の目的を達成するために、本発明に従った方法は、フレーム符号化したブロックに、逆画像変換とフィールドの加算とあらかじめ決定された基底変換とを表す、スパース行列を乗算するステップ及び前記の乗算の結果に前記のあらかじめ決定された基本変換の逆変換を行うステップから成る。
【００１２】
本発明は逆ＤＣＴ変換及びフィールドの加算の実行が、前記の基底変換の逆変換が後で行われないような基底変換により後続されてもよい。構成された演算（逆ＤＣＴ変換、フィールドの加算及び基底変換）は一つの行列の積に物理的に取って代わる。基底変換は前記の行列の乗算がスパース行列、すなわち非ゼロ要素がほとんどない行列との乗算になるように選ばれている。スパース行列の乗算はオン・ザ・フライで実行されるが、オン・ザ・フライ逆ＤＣＴ変換より実行するのは非常に容易である。この方法はフィールドメモリのみが必要となる。本発明の更なる重要な利点は、逆基底変換の実行が、すべてのフレーム（電子透かし検出に対して２０くらい）がフィールドメモリに蓄積されるまで延期させることができることである。
【００１３】
【発明の実施の形態】
図３は本発明の方法に従って、複数のフレーム符号化されたマクロブロックを蓄積する装置の概要図を示す。この装置は８×８のフレーム符号化したＤＣＴブロック３１（すなわち図１の１４と表示されているマクロブロックからのブロックの一つ）を受信する。このＤＣＴブロックは８×４のスパース行列Ｖ２との積３２をとる。この乗算は、二つのフィールドの和を示す中間値の８×４のブロックを生じる。加算器３３及びメモリ３４は、当該アプリケーション（例えば電子透かし検出）に必要なだけ多数の中間ブロックを蓄積する。この蓄積の完了と同時に、蓄積されたブロックには、行列Ｕ０との乗算３５により、逆基底変換が続いて行われる。最後に、実際のアプリケーション（ここでは電子透かし検出４０）が実行される。
【００１４】
ここで留意すべきは、図３の蓄積メモリ３４は８×４のメモリ（図では、各要素は実際の行列サイズ、例えば８×８、８×４又は４×４の比で描かれている）であることである。実際問題として、一つはマクロブロックのＤＣＴブロック上部から派生する四つのラインを蓄積するため、及び、一つはそれに相当するＤＣＴブロック下部から派生する四つのラインを蓄積するため、二つのメモリ３４が必要となる。集合的に前記メモリはフィールドメモリ（すなわち電子透かし検出の場合１２８×１２８のバッファ）の構成要素となる。
【００１５】
図３の中で点線で示すことを試みたように、行列Ｖ２は三つの数学的演算の組み合わせを表している。第一及び第二の演算はそれぞれ逆ＤＣＴ変換３２１及び二つのフィールドの加算３２２である。導入の段落で記述したように、受信した各ＤＣＴブロックに逆ＤＣＴ変換を物理的に実行することは魅力的ではない。この装置は数学的に二つの演算３２１及び３２２の結果を基本変換３２３にすることにより、これを避ける。この基底変換は図３においてＵ０−１と表示されている。この慣習的でない表記Ｕ０−１をこの特許明細書においては前記の基底変換そのものとして使用するのに対し、表記Ｕ０を逆基底変換として使用する。その理由は、基底変換３２３はただの数学的観念であるが、逆基底変換３５は前記の装置により物理的に実行されるからである。
【００１６】
本発明はまた、逆ＤＣＴ変換３２１は垂直方向のみに実行される必要があるという洞察を有利に開拓する。逆水平ＤＣＴ変換は（もしアプリケーション４０が、ピクセル領域において蓄積されたフィールドを処理する必要があると、必然的に）、逆基底変換３５の完了後まで延期されることが可能である。それに応じて、逆ＤＣＴ演算３２１はＤＣＴブロック３１に行列Ｄ８−１を乗ずることにより実行される。後者の行列は周知の８点ＤＣＴ変換の逆変換である。
【数４】
2005501490.tif 000003
図３における行列Ｓは奇数及び偶数ラインの和の行列表示である。
【数５】
2005501490.tif 000004
三つの行列Ｄ８−１、Ｓ及びＵ０−１を物理的に取って代わる行列Ｖ２は、数学的に以下のように表現できる。
Ｖ２＝Ｕ０−１・Ｓ・Ｄ８−１
基底変換Ｕ０−１は、逆基底変換Ｕ０が存在することを条件に、任意に選ぶことができる。本発明は、行列Ｖ２がスパース、すなわち多数のゼロを持つように、基底変換を選択することに帰する。本発明者は基底変換
Ｕ０−１＝Ｄ４
が巧妙な選択であることを発見した。ここでＤ４は４点ＤＣＴ変換である（式１を参照）。この選択は以下の行列が結果となる。
【数６】
2005501490.tif 000005
行列Ｖ２はきわめてスパースである。ＤＣＴブロック３１との乗算はＤＣＴ係数ごとに一つだけ、オン・ザ・フライで容易に行うことができる乗算を必要とする。これより非ゼロ成分が少ない行列は存在しないことを示すことが可能である。
【００１７】
導入の段落で既に言及したように、ＭＰＥＧのフレーム符号化ピクチャーは一般的にフレーム符号化されたマクロブロック（図１）及びフィールド符号化マクロブロック（図２）の混合により構成されている。メモリ３４に蓄積された、Ｖ２により変換されたフレーム符号化されたブロックにフィールド符号化されたブロックを直接加算することは可能ではない。なぜならそれらのブロックは異なる基底にあるからである。これは同一フレームの異なるブロックがともに加算される必要があるとき、又は複数のフレームがともに加算される必要があるとき（どちらの状況も導入の段落において言及されている電子透かし検出器において発生する）、問題を引き起こす。
【００１８】
図４は本発明に従ってフレーム符合されたブロック及びフィールド符号化されたブロックの混合を蓄積するように手配された処理の実施形態の概要図を示している。この実施形態において、フィールド符号化されたＤＣＴブロック３６は他の行列Ｖ１で乗算３７することにより、Ｖ２で変換されたフレーム符号化されたＤＣＴブロック３１と同じ基底に変換される。一貫性のため、行列Ｖ１は
【数７】
2005501490.tif 000006
でなければならない。ここでＤ４は４点ＤＣＴ変換であり（式１を参照）、Ｏ４は４×４の０行列である。あいにく、行列Ｖ１は相当にスパースではない。しかし、ＤＣＴ係数ごとに一つの乗算（全ての乗算は符号に至るまで同様）を必要とするという点でスパースである、
【数８】
2005501490.tif 000007
により、近似することが可能である。
【００１９】
ＤＣＴ係数が一様分布していると仮定すると、式（３）の厳密な定義の代わりに式（４）のＶ１を使うことにより、フィールド符号化されたマクロブロックのエネルギーの８５％を捕らえる。
【００２０】
本発明者は、より多くのフィールド符号化されたエネルギーを捕らえられるように、基底変換Ｕ０をわずかに修正することにより、結果としてそのいくらかのフレーム符号化されたエネルギーが失われるにも関わらず、これより改善することが可能であることを発見した。フィールド符号化されたマクロブロックに比べ、フレーム符号化されたマクロブロックに著しく多くのエネルギーがあると仮定すると、対応する行列Ｖ２及びＶ１は
【数９】
2005501490.tif 000008
【数１０】
2005501490.tif 000009
ここでαｋは式（２）と同様、並びにａｉ及びｂｉはビデオ画像統計に従って選ばれる。以下に述べる式とともに、ａｉ及びｂｉはフレーム符号化されたＤＣＴブロックの列のｉ番目のＤＣＴ係数の分散σｉ２及びフィールド符号化されたＤＣＴブロックの列のｉ番目のＤＣＴ係数の分散τｉ２を持つビデオシークエンスについて計算することができる。
【数１１】
2005501490.tif 000010
ここで
【数１２】
2005501490.tif 000011
【００２１】
一般的に、ａｉ及びｂｉは１に近く、前記の行列は式（２）及び（４）で定義されたものと実質上似ている。
【００２２】
本発明は以下のように要約することができる。あるビデオ処理アプリケーション、とりわけ電子透かし検出（４０）では、一つのフレームを構成する二つのインターレース・フィールドを（部分的に）加算又は平均することが必要である。この演算は、フレーム符号化されたＤＣＴブロックの存在のため、ＭＰＥＧ領域では通常ではない。本発明は、フレームメモリ又はオン・ザ・フライ逆ＤＣＴを必要としない、フィールドを加算する方法と装置を供給する。このために、数学的に要求される、垂直ＤＣＴの逆変換（３２１）及び加算（３２２）の演算は基底変換（３２３）に結合される。この基底変換は結合された演算がスパース行列（３２）の乗算により物理的に代えられるように選ばれる。前記のスパース行列の乗算は容易にオン・ザ・フライで実行される。逆基底変換（３５）は、要望される加算（３３，３４）が完了されるまで延期される。
【図面の簡単な説明】
【図１】本発明の基になる問題を説明する図を示す。
【図２】本発明の基になる問題を説明する図を示す。
【図３】本発明に従い、フレーム符号化されたマクロブロックを蓄積するための装置の概要図を示す。
【図４】本発明に従い、フレーム符号化されたブロックとフィールド符号化されたブロックとの混合を蓄積する装置の実施形態の概要図を示す。
【国際公開パンフレット】
2005501490.tif 000015
2005501490.tif 000016
2005501490.tif 000017
2005501490.tif 000018
2005501490.tif 000019
2005501490.tif 000020
2005501490.tif 000021
2005501490.tif 000022
2005501490.tif 000023
2005501490.tif 000024
2005501490.tif 000025
2005501490.tif 000026
2005501490.tif 000027
2005501490.tif 000028
【国際公開パンフレット（コレクトバージョン）】
2005501490.tif 000029
【国際調査報告】
2005501490.tif 000030
2005501490.tif 000031
2005501490.tif 000032