(57)【要約】画像コンテンツベースの検索及びランキングによるビデオ圧縮のための効率的な参照データ符号化方法及び装置が提供される。この装置は、複数の候補参照ブロックの各々のコンテキスト特徴に対する符号化されるべき現在のブロックのコンテキスト特徴に基づいて、前記符号化されるべき現在のブロックに関連する前記複数の候補参照ブロックの各々について参照データをランク番号に変換するランク変換部（２１０）を含む。前記装置はさらに、前記現在のブロックに関連する前記複数の候補参照ブロックの各々について前記参照データの代わりに且つ当該参照データを表すように、前記現在のブロックに関連する前記複数の候補参照ブロックの各々についてのランク番号をエントロピー符号化するエントロピーエンコーダ（２２０）を含む。
2013539935.tif 000002
【特許請求の範囲】
【請求項１】
符号化されるべき現在のブロックに関連する複数の候補参照ブロックの各々について参照データを前記複数の候補参照ブロックの各々のコンテキスト特徴に対する前記現在のブロックのコンテキスト特徴に基づいてランク番号に変換するため、及び、ランク番号を決定するためのランク変換部（２１０）であって、該ランク番号は前記現在のブロックを符号化するために参照ブロックとして実際に使用される前記複数の候補参照ブロックの１つに対応する、ランク変換部、及び、
前記現在のブロックについて前記決定されたランク番号をエントロピー符号化するエントロピーエンコーダ（２２０）
を備える、装置。
【請求項２】
前記参照データは、動きベクトル、空間変位ベクトル及び視差値の少なくとも１つを含む、請求項１記載の装置。
【請求項３】
前記現在のブロックに関連する前記複数の候補参照ブロックの各々についての前記参照データは、前記複数の候補参照ブロックのそれぞれの候補参照ブロックの前記コンテキスト特徴に対する前記現在のブロックの前記コンテキスト特徴に基づいて、前記複数の候補参照ブロックのそれぞれの候補参照ブロックと前記現在のブロックの間の距離を計算すること、前記複数の候補参照ブロックの残りの参照ブロックのそれぞれについて前記距離の前記計算を繰り返して複数の距離を得ること、及び当該複数の距離に基づいて前記複数の候補参照ブロックをソートして前記複数のランク番号を有するランクリストを得ることによって、前記ランク番号にそれぞれ変換される、請求項１記載の装置。
【請求項４】
前記現在のブロックを符号化するために前記参照ブロックとして実際に使用される前記複数の候補参照ブロックのうちの特定の１つが対応する前記複数のランク番号のそれぞれに基づいて特定され、これが、前記複数の距離のうちの最も短い距離に基づいて前記現在のブロックと前記複数の候補参照ブロックのうちの前記１つの参照ブロックとの間の最も近いマッチングを示す、請求項１記載の装置。
【請求項５】
前記現在のブロックの前記コンテキスト特徴は前記現在のブロックを囲む画素からなり、前記複数の候補参照ブロックの各々についての前記コンテキスト特徴は当該候補参照ブロックを囲む画素からなる、請求項１記載の装置。
【請求項６】
前記複数の候補参照ブロックの各々の前記コンテキスト特徴は、前記現在のブロックの前記コンテキスト特徴と比較される検索可能なコンテキスト特徴の集合を形成する、請求項１記載の装置。
【請求項７】
前記現在のブロックの前記コンテキスト特徴は、前記現在のブロックと前記複数の候補参照ブロックの各々との間の距離に基づいて、前記複数の候補参照ブロックの各々のコンテキスト特徴にマッチングされる、請求項１記載の装置。
【請求項８】
符号化されるべき現在のブロックに関連する複数の候補参照ブロックの各々について参照データを前記複数の候補参照ブロックの各々のコンテキスト特徴に対する前記現在のブロックのコンテキスト特徴に基づいてランク番号に変換するステップ（３１５）、
前記現在のブロックについてランク番号を決定するステップ（３２０）であって、該ランク番号は前記現在のブロックを符号化するために参照ブロックとして実際に使用される前記複数の候補参照ブロックの１つに対応する、ステップ、及び、
前記現在のブロックについて前記決定されたランク番号をエントロピー符号化するステップ（３２５）
を含む、方法。
【請求項９】
前記参照データは、動きベクトル、空間変位ベクトル及び視差値の少なくとも１つを含む、請求項８記載の方法。
【請求項１０】
前記現在のブロックに関連する前記複数の候補参照ブロックの各々についての前記参照データは、前記複数の候補参照ブロックのそれぞれの候補参照ブロックの前記コンテキスト特徴に対する前記現在のブロックの前記コンテキスト特徴に基づいて、前記複数の候補参照ブロックのそれぞれの候補参照ブロックと前記現在のブロックの間の距離を計算すること、前記複数の候補参照ブロックの残りの参照ブロックのそれぞれについて前記距離の前記計算を繰り返して複数の距離を得ること、及び当該複数の距離に基づいて前記複数の候補参照ブロックをソートして前記複数のランク番号を有するランクリストを得ることによって、前記ランク番号にそれぞれ変換される、請求項８記載の方法。
【請求項１１】
前記現在のブロックを符号化するために参照ブロックとして実際に使用される前記複数の候補参照ブロックのうちの特定の１つが対応する前記複数のランク番号のそれぞれに基づいて特定され、これが前記複数の距離のうちの最も短い距離に基づいて前記現在のブロックと前記複数の候補参照ブロックのうちの前記１つの参照ブロックとの間の最も近いマッチングを示す、請求項１０記載の方法。
【請求項１２】
前記現在のブロックの前記コンテキスト特徴は前記現在のブロックを囲む画素からなり、前記複数の候補参照ブロックの各々についての前記コンテキスト特徴は当該候補参照ブロックを囲む画素からなる、請求項８記載の方法。
【請求項１３】
前記複数の候補参照ブロックの各々の前記コンテキスト特徴は、前記現在のブロックの前記コンテキスト特徴と比較される検索可能なコンテキスト特徴の集合を形成する、請求項８記載の方法。
【請求項１４】
前記現在のブロックの前記コンテキスト特徴は、当該現在のブロックと前記複数の候補参照ブロックの各々との間の距離に基づいて、前記複数の候補参照ブロックの各々のコンテキスト特徴にマッチングされる、請求項８記載の方法。
【請求項１５】
符号化されるべき現在のブロックに関連する複数の候補参照ブロックの各々について参照データを前記複数の候補参照ブロックの各々のコンテキスト特徴に対する前記現在のブロックのコンテキスト特徴に基づいてランク番号に変換する手段（２１０）であって前記現在のブロックについてランク番号を決定する手段（２１０）であって、該ランク番号は前記現在のブロックを符号化するために参照ブロックとして実際に使用される前記複数の候補参照ブロックの１つに対応する、手段、及び、
前記現在のブロックについて前記決定されたランク番号をエントロピー符号化する手段（２２０）
を備える、装置。
【請求項１６】
前記参照データは、動きベクトル、空間変位ベクトル及び視差値の少なくとも１つを含む、請求項１５記載の装置。
【請求項１７】
前記現在のブロックに関連する前記複数の候補参照ブロックの各々についての前記参照データは、前記複数の候補参照ブロックのそれぞれの候補参照ブロックの前記コンテキスト特徴に対する前記現在のブロックの前記コンテキスト特徴に基づいて、前記複数の候補参照ブロックのそれぞれの候補参照ブロックと前記現在のブロックの間の距離を計算すること、前記複数の候補参照ブロックの残りの参照ブロックのそれぞれについて前記距離の前記計算を繰り返して複数の距離を得ること、及び当該複数の距離に基づいて前記複数の候補参照ブロックをソートして前記複数のランク番号を有するランクリストを得ることによって、前記ランク番号にそれぞれ変換される、請求項１５記載の装置。
【請求項１８】
前記現在のブロックを符号化するために前記参照ブロックとして実際に使用される前記複数の候補参照ブロックのうちの特定の１つが対応する前記複数のランク番号のそれぞれに基づいて特定され、これが前記複数の距離のうちの最も短い距離に基づいて前記現在のブロックと前記複数の候補参照ブロックのうちの前記１つの参照ブロックとの間の最も近いマッチングを示す、請求項１６記載の装置。
【請求項１９】
前記現在のブロックの前記コンテキスト特徴は前記現在のブロックを囲む画素からなり、前記複数の候補参照ブロックの各々についての前記コンテキスト特徴は当該候補参照ブロックを囲む画素からなる、請求項１５記載の装置。
【請求項２０】
前記複数の候補参照ブロックの各々の前記コンテキスト特徴は、前記現在のブロックの前記コンテキスト特徴と比較される検索可能なコンテキスト特徴の集合を形成する、請求項１５記載の装置。
【請求項２１】
前記現在のブロックの前記コンテキスト特徴は、前記現在のブロックと前記複数の候補参照ブロックの各々との間の距離に基づいて、前記複数の候補参照ブロックの各々のコンテキスト特徴にマッチングされる、請求項１５記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願］
本出願は、２０１０年９月１０日（代理人整理番号ＰＵ１００１９５）に出願された米国仮特許出願第６１／４０３１３８号（発明の名称：画像コンテンツベースの検索及びランキングによるビデオ圧縮のための効率的な参照データ符号化）の優先権を主張する。
【０００２】
本出願は、以下の米国特許庁に同時係属中の特許出願（出願人も共通）に関連する。
【０００３】
（１）国際特許出願ＰＣＴ／ＵＳ１１／０００１０７、発明の名称「効率的なビデオ圧縮のためのサンプリングベースの超解像アプローチ」、出願日２０１１年１月２０日（代理人整理番号ＰＵ１００００４）。
【０００４】
（２）国際特許出願番号ＰＣＴ／ＵＳ１１／０００１１７、発明の名称「事例ベースの超解像を用いたビデオ圧縮のためのデータプルーニング」、出願日２０１１年１月２１日（代理人整理番号ＰＵ１０００１４）。
【０００５】
（３）国際特許出願番号ＸＸＸＸ、発明の名称「ビデオ圧縮のための動き補償された事例ベースの超解像を用いたビデオ信号符号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００１９０）。
【０００６】
（４）国際特許出願番号ＸＸＸＸ、発明の名称「ビデオ圧縮のための動き補償された事例ベースの超解像を用いたビデオ信号復号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００２６６）。
【０００７】
（５）国際特許出願番号ＸＸＸＸ、発明の名称「より優れたビデオ圧縮効率のための事例ベースのデータプルーニングを使用するビデオ信号符号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００１９３）。
【０００８】
（６）国際特許出願番号ＸＸＸＸ、発明の名称「より優れたビデオ圧縮効率のための事例ベースのデータプルーニングを用いたビデオ信号復号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００２６７）。
【０００９】
（７）国際特許出願番号ＸＸＸＸ、発明の名称「ブロックベースの混合解像度のデータプルーニングのためのビデオ信号符号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００１９４）。
【００１０】
（８）国際特許出願番号ＸＸＸＸ、発明の名称「ブロックベースの混合解像度のデータプルーニングのためのビデオ信号復号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００２６８）。
【００１１】
（９）国際特許出願番号ＸＸＸＸ、発明の名称「画像コンテンツベースの検索およびランキングによるビデオ圧縮のための効率的な参照データ復号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１１０１０６）。
【００１２】
（１０）国際特許出願番号ＸＸＸＸ、発明の名称「フレーム内のパッチ類似度を用いた事例ベースのデータプルーニングのためのビデオ信号符号化方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００１９６）。
【００１３】
（１１）国際特許出願番号ＸＸＸＸ、発明の名称「フレーム内のパッチ類似度を用いた事例ベースのデータプルーニングによりビデオ信号を復号化する方法及び装置」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１００２６９）。
【００１４】
（１２）国際特許出願番号ＸＸＸＸ、発明の名称「事例ベースのデータプルーニング圧縮におけるプルーニング決定最適化」、出願日２０１１年９月ＸＸ日（代理人整理番号ＰＵ１０１９７）。
【００１５】
本発明はビデオの符号化及び復号化に関し、特に画像コンテンツベースの検索及びランキングによる、ビデオ圧縮のための効率的な参照データ符号化方法及び装置に関する。 
【背景技術】
【００１６】
国際標準化機構/国際電気標準会議（ＩＳＯ／ＩＥＣ）のＭＰＥＧ４（Moving Picture Experts Group-4）パート１０の高度ビデオ符号化（ＡＶＣ：Advanced Video Coding）規格／国際電気通信連合電気通信標準化部門（ＩＴＵ−Ｔ）Ｈ２６４勧告（以下、「ＭＰＥＧ−４ＡＶＣ規格」と称する）のようなブロックベースのビデオ符号化方式では、画像ブロックの符号化及び／または復号化はしばしば、別の同様なブロック（以下、「参照ブロック」と称する）からの予測により容易に行うことができる。従って、参照ブロックの位置を示すサイド情報を、デコーダ側に送信しなければならない。一般化するために、このような参照情報は「参照データ」と称される。参照データの例としては、ＭＰＥＧ−４ＡＶＣ規格及び他のＭＰＥＧベースの符号化方式における動きベクトル、マルチビュー符号化方式における視差値、並びに空間ブロック予測を用いたビデオ圧縮方式における空間変位ベクトルがある。
【００１７】
従来のビデオ符号化方式では、動きベクトルなどの参照データは、エントロピー符号化を使用して符号化される。一般的に、動きベクトルの符号化は画像コンテンツとは無関係である。
【００１８】
最近では、ビデオ符号化効率を向上すべく、テンプレートマッチング法と呼ばれる方法が提案されている。テンプレートマッチング法はイントラ符号化方式の一種であり、現在の符号化ブロックを予測するためにビデオフレーム内のどこかに位置している参照ブロックを使用する。現在の符号化ブロックを予測するために隣接ブロックのコンテンツのみを使用する従来のＭＰＥＧ−４ＡＶＣ規格のイントラ符号化方式とは異なり、テンプレートマッチング法における参照ブロックは現在の符号化ブロックに対して非隣接であってよい。このことにより、テンプレートマッチング法は、符号化に関して、より柔軟かつ効率的になる。テンプレートマッチング法のもう一つの特徴は、空間変位ベクトル（参照ブロックと現在のブロックの間の相対座標）を符号化する必要がないということである。テンプレートマッチング法は、参照ブロックとしてベストマッチブロックを見つけるために、符号化ブロックのコンテキストを使用する。ブロックのコンテキストは通常、ブロックの周囲の画素の集合である。図１を参照すると、コンテキストマッチングとこれに対応する空間変位ベクトルの例が符号１００で示されている。符号化／復号化されるべき現在のブロックは符号１１０で示されている。参照ブロックは符号１２０で示されている。参照ブロック１２０から現在のブロック１１０への空間変位ベクトルは符号１３０で示されている。コンテキストは符号１４０で示されている。このように、テンプレートマッチング方法は、参照ブロックを見つけるためにコンテキストのみを利用している。しかしながら、２つのブロックが同じようなコンテキストを有するが大きく異なる外観を有することもあり、それ故に、コンテキストを使用して参照ブロックを見つけることは、多くの場合、信頼できないかもしれない。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
従来技術の上記した欠点・課題及びその他の欠点・課題は、画像コンテンツベースの検索及びランキングによるビデオ圧縮のための効率的な参照データ符号化方法及び装置を開示する本発明によって解決される。 
【課題を解決するための手段】
【００２０】
本発明の一つの態様によれば、装置が提供される。該装置は、複数の候補参照ブロックの各々のコンテキスト特徴（context feature）に対する符号化されるべき現在のブロックのコンテキスト特徴に基づいて、上記符号化されるべき現在のブロックに関連する上記複数の候補参照ブロックの各々について参照データをランク番号に変換するランク変換部を含む。該装置はさらに、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記参照データの代わりに且つ当該参照データを表すように、上記現在のブロックに関連する上記複数の候補参照ブロックの各々についてのランク番号をエントロピー符号化するエントロピーエンコーダを含む。
【００２１】
本発明の別の態様によれば、方法が提供される。該方法は、複数の候補参照ブロックの各々のコンテキスト特徴に対する符号化されるべき現在のブロックのコンテキスト特徴に基づいて、上記符号化されるべき現在のブロックに関連する上記複数の候補参照ブロックの各々について参照データをランク番号に変換するステップを含む。この方法はさらに、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記参照データの代わりに且つ当該参照データを表すように、上記現在のブロックに関連する上記複数の候補参照ブロックの各々についてのランク番号をエントロピー符号化するステップを含む。
【００２２】
本発明のさらに別の態様によれば、装置が提供される。該装置は、復号化されるべき現在のブロックに関連する複数の候補参照ブロックの各々について、符号化されたランク番号をエントロピー復号化することにより、復号化されたランク番号を得るエントロピーデコーダを含む。上記符号化されたランク番号は、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記参照データの代わりになり且つ当該参照データを表す。該装置はさらに、上記複数の候補参照ブロックの各々のコンテキスト特徴に対する上記現在のブロックのコンテキスト特徴に基づいて、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記復号化されたランク番号を参照データに変換する逆ランク変換部を含む。
【００２３】
本発明のさらに別の態様によれば、方法が提供される。該方法は、復号化されるべき現在のブロックに関連する複数の候補参照ブロックの各々について、符号化されたランク番号をエントロピー復号化することにより、復号化されたランク番号を得るステップを含む。上記符号化されたランク番号は、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記参照データの代わりになり且つ当該参照データを表す。該方法はさらに、上記複数の候補参照ブロックの各々のコンテキスト特徴に対する上記現在のブロックのコンテキスト特徴に基づいて、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記復号化されたランク番号を参照データに変換するステップを含む。
【００２４】
本発明のさらなる態様によれば、装置が提供される。該装置は、複数の候補参照ブロックの各々のコンテキスト特徴に対する符号化されるべき現在のブロックのコンテキスト特徴に基づいて、上記符号化されるべき現在のブロックに関連する上記複数の候補参照ブロックの各々について参照データをランク番号に変換する手段を含む。該装置はさらに、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記参照データの代わりに且つ当該参照データを表すように、上記現在のブロックに関連する上記複数の候補参照ブロックの各々についてランク番号をエントロピー符号化する手段を含む。
【００２５】
本発明のさらなる態様によれば、装置が提供される。該装置は、復号化されるべき現在のブロックに関連する複数の候補参照ブロックの各々について、符号化されたランク番号をエントロピー復号化することにより、復号化されたランク番号を得る手段を含む。上記符号化されたランク番号は、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記参照データの代わりになり且つ当該参照データを表す。該装置はさらに、上記複数の候補参照ブロックの各々のコンテキスト特徴に対する上記現在のブロックのコンテキスト特徴に基づいて、上記現在のブロックに関連する上記複数の候補参照ブロックの各々について上記復号化されたランク番号を参照データに変換する手段を含む。
【００２６】
本発明の上記の態様、特徴及び利点並びに他の態様、特徴及び利点は、添付図面を参照して読まれるべき例示的実施形態の以下の詳細な説明から明らかになるであろう。 
本発明は、以下の例示的な図面に基づいて、より良く理解される。
【図面の簡単な説明】
【００２７】
【図１】図１は、従来技術によるコンテキストマッチングとこれに対応する空間変位ベクトルの例を示す図である。
【図２】図２は、本発明の実施形態による参照データを符号化するための例示的な装置を示すブロック図である。
【図３】図３は、本発明の実施形態による参照データを符号化するための例示的な方法を示すフロー図である。
【図４】図４は、本発明の実施形態による参照データを復号化するための例示的な装置を示すブロック図である。
【図５】図５は、本発明の実施形態による参照データを復号化するための例示的な方法を示すフロー図である。
【図６】図６は、本発明の実施形態による参照データをランク番号に変換するための例示的なランク変換を示す図である。
【図７】図７は、本発明の実施形態による参照データをランク番号に変換するための例示的な方法を示すフロー図である。
【発明を実施するための形態】
【００２８】
本発明は、画像コンテンツベースの検索とランキングによる、ビデオ圧縮のための効率的な参照データ符号化方法及び装置に関している。 
本明細書は本発明の技術思想を説明している。したがって、当業者は、本発明の技術思想を具現化する様々な構成を、明示的に本明細書に記載または図示されていないが、考案することができ、当該構成は本発明の精神及び範囲内に含まれる。
【００２９】
本明細書に記載されたすべての例と条件を示す表現・記載とは、当該技術を発展・促進するために本発明者によって成された本発明の技術思想を本明細書の読者が理解する際に役立つであろういう意図をもって提示されたものであり、そのような特定の例及び条件に限定されないと解釈されるべきである。
【００３０】
また、本明細書中における本発明の技術思想、態様、実施形態及び特定の例の記載・説明は、構成とその機能的均等物とを包含する。さらに、当該均等物は、現在知られている均等物と将来開発される均等物（つまり、構成にかかわらず、同じ機能を発揮するように開発された全ての要素）の双方を含む。
【００３１】
したがって、例えば、本明細書に示されたブロック図が、本発明を具現化する例示的な回路の概念図を表していることは、当業者であれば理解できるであろう。同様に、すべてのフローチャート、フロー図、状態遷移図、擬似コード等が実質的にコンピュータ可読媒体内に表現され、コンピュータもしくはプロセッサによって実行される種々のプロセスを表していることも、当該コンピュータもしくはプロセッサが明示されているか否かにかかわらず理解できよう。
【００３２】
図示された様々な要素の機能は、専用ハードウェアを使用するだけでなく、適切なソフトウェアと連動するソフトウェアを実行することができるハードウェアを使用することにより、提供されてもよい。前記機能がプロセッサによって提供される場合、当該機能は１つの専用プロセッサによって、１つの共有プロセッサによって、または、複数の独立したプロセッサ（その内の幾つかのプロセッサは共有プロセッサであってもよい）によって提供され得る。さらに、「プロセッサ」または「コントローラ」という用語の明示的な使用は、ソフトウェアを実行可能なハードウェアだけを意味すると解釈されるべきではなく、黙示的に、デジタル信号プロセッサ（ＤＳＰ：digital signal processor）ハードウェア、ソフトウェアを記憶するリードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、及び不揮発性記憶装置も含むが、これらに限定されるものではない。
【００３３】
他のハードウェア、従来のハードウェア及び/またはカスタムハードウェアも含まれ得る。同様に、図示されたすべてのスイッチは、概念的なものに過ぎない。それらの機能は、プログラムロジックの操作・実行により、専用ロジックにより、プログラム制御と専用ロジックのインタラクションにより実施することができるし、手動で実施することさえ可能であり、どの特定の技術を選択するかは、実施者がコンテキストに応じて決めることができる。
【００３４】
本出願の特許請求の範囲において、特定の機能を実行する手段として表現された要素のすべては、当該機能の実行する任意のものを包含し、例えば、（ａ）当該機能の実行する複数の回路要素の組み合わせ、または（ｂ）当該機能を実行するソフトウェアを実行する適切な回路と組み合わされる任意の形（形式）のソフトウェア（例えば、ファームウェア、マイクロコード等）を含む。このような請求項によって規定される本発明の技術思想は、様々な記載された手段によって提供される機能が組み合わされて、請求項が意図している形で一体化される中に見出される。したがって、前記機能を提供することができる任意の手段は、本明細書に示されるものと均等であるとみなされる。
【００３５】
本明細書において「１つの実施形態」、「本発明の実施形態」または当該実施形態の変形例として説明されているものは、当該実施形態との関連で記載されている特定の特徴・機能、構造、特性等が本発明の少なくとも１つの実施形態に含まれていることを意味している。よって、本明細書の複数の箇所において記載されている「１つの実施形態では（においては）」という表現、「実施形態では（においては）」という表現、及び同様な表現は、すべて同じ実施形態を指すとは限らない。
【００３６】
「／」、 「及び／または」、及び 「の少なくとも１つ」という表現は、例えば「Ａ／Ｂ」、「Ａ及び／またはＢ」、「ＡとＢのうちの少なくとも１つ」であれば、最初に記載されたもの（Ａ）のみを選択する場合と、２番目に記載されたもの（Ｂ）のみを選択する場合と、両方とも選択する場合（ＡとＢ）とを包含することを意図している。別の例として、「Ａ、Ｂ及び/またはＣ」と「Ａ、Ｂ及びＣの少なくとも１つ」という表現は、最初に記載されたもの（Ａ）のみを選択する場合と、２番目に記載されたもの（Ｂ）のみを選択する場合と、３番目に記載されたもの（Ｃ）のみを選択する場合と、１番目と２番目に記載されたもの（ＡとＢ）のみを選択する場合と、１番目と３番目に記載されもの（Ａ及びＣ）のみを選択する場合と、２番目と３番目に記載されたもの（ＢとＣ）のみを選択する場合と、または３つのものすべて（ＡとＢとＣ）を選択する場合とを包含することを意図している。このような解釈は、本発明の技術分野及び関連技術分野における当業者であれば容易に理解できるであろうが、より多くの項目が記載されている場合にも適用され得る。
【００３７】
また、本明細書で使用される用語「ピクチャ」と「画像（image）」は、同じ意味で使用され、ビデオシーケンスから得られる静止画像またはピクチャを意味している。公知のように、ピクチャはフレームまたはフィールドであることもある。
【００３８】
上述したように、本発明は、画像コンテンツベースの検索とランキングによって、ビデオ圧縮のための効率的な参照データの符号化を行う方法及び装置に関している。例えば、１つの実施形態では、これに限定されないが例えば動きベクトルの参照データを符号化する新規なスキームが開示されている。参照データは、例えば、コンテンツベースの検索、ランキング及びランク番号エンコーディングを使用して符号化される。
【００３９】
図２を参照すると、参照データを符号化するための例示的な装置が符号２００で示されている。装置２００は、ランク変換部２１０及びエントロピー符号化部２２０を含む。ランク変換部２１０の出力は、エントロピー符号化部２２０の入力と信号通信可能に接続されている。ランク変換部２１０の入力は、コンテキスト特徴（図示せず）及び参照データを受信するために、装置２００への入力として使用可能である。エントロピー符号化部２２０の出力は、符号化された参照データを出力するために、装置２００の出力として利用可能である。
【００４０】
要するに、参照データはまず、後述するランク変換処理を使用してランク変換部２１０によってランク番号に変換される。その後、エントロピー符号化処理が、ランク番号を符号化するためにエントロピー符号化部２２０によって使用される。エントロピー符号化処理は、例えば、ゴロム符号または他の符号を利用する。
【００４１】
図３を参照すると、参照データを符号化するための例示的な方法が符号３００で示されている。ステップ３０５において、コンテキスト特徴と参照データが入力される。ステップ３１０において、すべての候補ブロックまでの距離が、コンテキスト特徴を使用して計算される。ステップ３１５において、候補ブロックが前記距離（ステップ３１０で算出）に基づいてソートされてランクリストが取得される。ステップ３２０において、ランクリスト内の参照データのランク番号が取得される。ステップ３２５において、ランク番号はエントロピー符号化される。ステップ３３０において、符号化された参照データ、即ち、エントロピー符号化されたランク番号が出力される。
【００４２】
図４を参照すると、参照データを復号化する例示的な装置が符号４００で示されている。この装置４００は、エントロピーデコーダ４１０と逆ランク変換部４２０を含む。エントロピーデコーダ４１０の出力は、逆ランク変換部４２０の入力と信号通信可能に接続されている。エントロピーデコーダ４１０の入力は、符号化された参照データを受信するために、装置４００への入力として使用可能である。逆ランク変換部４２０の出力は、（復号化された）参照データを出力するために、装置４００の出力として利用可能である。
【００４３】
受信された符号化されたデータはまず、エントロピーデコーダ４１０によって復号化され、ランク番号になる。逆ランク変換部４２０はランク番号を取得し、対応する参照ブロックを出力する。逆ランク変換処理は、後述するランク変換に似ている。復号化ブロックのコンテキスト特徴Ｆｅは、距離計算により、コンテキスト特徴集合Ｆ＝｛Ｆ１、Ｆ２、... 、ＦＮ｝内の特徴にマッチングさせられる。コンテキスト特徴集合内の各特徴は、参照ブロックに対応している。次に、コンテキスト特徴集合はソートされ、検索ランクリストになる。復号化されたランク数Ｒは、その後、ランクリスト中のＲ番目のエントリに位置されている「正しい」参照ブロックを取り出すために用いられる。
【００４４】
図５を参照すると、参照データを復号化する例示的な方法が符号５００で示されている。ステップ５０５において、コンテキスト特徴と符号化された参照データが入力される。ステップ５１０において、すべての候補ブロックまでの距離が、コンテキスト特徴を用いて計算される。ステップ５１５において、候補ブロックが前記距離（ステップ５１０で算出）に基づいてソートされてランクリストを取得する。ステップ５２０において、符号化された参照データがエントロピー復号化されてランク番号を取得する。ステップ５２５において、ランクリスト内の参照データがランク番号を用いて見つけられる。ステップ５３０において、復号化された参照データが出力される。
【００４５】
本明細書において提案される複数の方法のうちの少なくとも１つの方法は、テンプレートマッチング法により着想を得ている。このような方法（複数可）もブロックのコンテキスト情報を使用するが、コンテキストは、動きベクトルまたは変位ベクトルなどの参照データを符号化するために使用される。上記の問題は、本発明者が提案する手法・手段によれば、まず、より正確な参照ブロックを見つけるためにコンテキストを使用するのではなく画像ブロックコンテンツを使用すること、次に、空間変位ベクトル（spatial displacement vector）または動きベクトル（motion vector）を符号化するために前記見つけられた参照ブロックのコンテキスト情報を使用することにより解決される。これにより、本明細書で開示された方法はテンプレートマッチング法よりも正確なものになり、且つ、変位ベクトルや動きベクトルを直接使用するよりも、符号化効率を高めることができる。
【００４６】
したがって、本発明は、ビデオ符号化処理中に生成される動きベクトル及び/または空間変位ベクトルなどの参照データをより効率的に符号化するための方法及び装置を提供する。本発明は、元の参照データの確率分布をより低いエントロピーを持つ変換されたデータの新たな確率分布に変換するというアイデアに基づいている。エントロピーが低いと、シャノンの情報源符号化定理に従って、変換された参照データを符号化するために必要なビット数が少なくなる。このような変換は画像ブロックコンテキスト特徴をマッチングさせることによって生成された検索ランクリストを使用することにより実現できることが示されている。また、ランクリスト中の参照ブロックのランク番号は、低いエントロピーを持つ変換された参照データである。ブロックベースの圧縮技術があり、画像またはビデオのフレームがオーバーラップしないブロックに分割されていると仮定する。各ブロックごとに、動きベクトルなどの参照データがデコーダ側に送信される必要がある。本発明に従い、参照データは離散的で且つ有限であると仮定し、それは動きベクトルまたは変位ベクトルについても言えるとする。
【００４７】
伝統的に、参照データは、データの確率分布に関する１つの仮定の下でエントロピー符号化法を使用して符号化される。ここで、ブロックに関連付けられた参照データをＭとする。Ｍは、参考データ集合ΣＭから得られる値を取る乱数である。Ｍの確率分布はｐ（Ｍ）であるので、ＭのエントロピーはＨ（Ｍ）である。シャノンの情報源符号化によれば、参照データのロスレス符号化のための最小ビット数はエントロピーＨ（Ｍ）によって制約されている。より正式には、参照データＭが最適なエンコーダを使用してビット数Ｓの２進数として、ロスレス符号化されていると仮定する。次に、シャノンの情報源符号化定理によると、以下のようになる。
Ｈ（Ｍ）＜Ｅ（Ｓ）＜Ｈ（Ｍ）＋１
【００４８】
ここで、Ｅ（Ｓ）はＳの期待値である。つまり、Ｓは最適なエンコーダでＭを符号化するのに用いられるビット数を示している。
【００４９】
さらにシャノンの情報源符号化定理によれば、もしエンコーダが最適ならば、符号化効率を向上させる唯一の方法は、エントロピーＨ（Ｍ）を減ずることである。エントロピーＨ（Ｍ）を減ずる他の方法があるかもしれない。１つの方法は、低いエントロピーを持つ別の確率変数にＭを変換するための変換手段・手法を見つけることである。その一例は、予測による符号化である。例えば、動きベクトルの場合、隣接するブロックの動きベクトルを用いて、現在の符号化ブロックの動きベクトルを予測することができる。隣接するブロックの動きベクトルがＭＮと表わされ、メタデータＭの変換がＭ'＝Ｍ−ＭＮにより得られる場合、ＭとＭＮが相関しているならばＭ 'は低いエントロピーを有する。また、この場合において、ＭＮはＭを予測するサイド情報（side information）である。
【００５０】
したがって、本発明によれば、それはサイド情報としてブロックに関連付けられた画像コンテンツを使用して参照データＭを変換する変換手段を見つけることが可能である。具体的には、Ｍがブロックの参照データであるとすると、Ｍは有限なメタデータ集合ΣＭから値を取る。また、各ブロックは、あるコンテキスト特徴Ｆに関連付けられる。コンテキスト特徴の一例は、図１に示されているようなブロックを囲む画素の集合である。ここで、符号化ブロックのために特定の参照ブロックを選択する候補として、Ｎ個のブロックがあるとする。したがって、参照データの集合は１からＮまでの自然数の集合である、すなわち、ΣＭ＝｛１，２，．．．，Ｎ｝である。参照データの集合は離散的で且つ有限であるので、参照データは常に有限な自然数の集合にマッピングすることができる。ｉ番目の候補ブロックについては、コンテキスト特徴Ｆｉがあり、すべての候補参照ブロックＦ＝｛Ｆ１，Ｆ２，．．．，ＦＮ｝については対応するコンテキスト特徴集合がある。符号化ブロックについては、コンテキスト特徴Ｆｅも関連付けられている。
【００５１】
本発明者が提案する変換手段は、コンテキスト特徴集合Ｆ内のすべて特徴とコンテキスト特徴Ｆｅの間の距離を計算することによって参照データ集合内の最適マッチング（best-match）参照ブロックを検索し、前記距離に基づいて当該参照データ集合を昇順にソートして、検索ランクリストを得る。その結果、前記特徴Ｆｅに最も近いコンテキスト特徴を有するΣＭ内の参照データが、検索ランクリストの一番上になる。直接的なブロックマッチングのような信頼性の高い方法を用いて得られる「正しい」参照ブロックが実際に検索ランクリストのＲ番目のエントリであると仮定すると、ランク番号Ｒは、符号化された参照データとして保存される。要するに、本発明において提案されているプロセスは、元の参照データをランクリストのランク番号に変換するという変換である。ランク番号も自然数の集合｛１，２，... ，Ｎ}から値を取る。本明細書で用いられる「直接的なブロックマッチング（direct block match）」は単に、これに限定されないが例えばＭＰＥＧ−４ＡＶＣ規格等のブロックベースのビデオ圧縮法で実行される一般的な動き推定法に用いられるブロックマッチング法を意味している。ダイレクトブロックマッチング法または直接的なブロックマッチング法は、現在のブロックと複数の候補ブロックとの差を算出し、最適なマッチングとして、差が最も小さい候補参照ブロックを選択する。
【００５２】
図６を参照すると、参照データをランク番号に変換するための例示的なランク変換法が符号６００で示されている。ランク変換法６００は、符号化ブロック６１０（すなわち、符号化されるべきブロック）、当該符号化ブロック６１０のコンテキスト特徴６１５、候補参照ブロックの集合６２０及びソートされた参照ブロックの集合６３０（すなわち、ランクリスト）を含む。候補参照集合６２０内の候補参照ブロックは、コンテキスト特徴（図中で明示的に符号を付していない）も含む。
【００５３】
図７を参照すると、参照データをランク番号に変換するための例示的な方法が符号７００で示されている。ステップ７０５において、コンテキスト特徴と参照データが入力される。ステップ７１０において、すべての候補ブロックまでの距離が、コンテキスト特徴を使用して計算される。ステップ７１５において、候補ブロックは前記距離に応じてソートされ、ランクリストを取得する。ステップ７２０において、ランクリスト中の参照データのランク番号が得られる。ステップ７２５において、ランク番号が出力される。
【００５４】
変換されたランク番号Ｒのエントロピーはコンテキスト特徴Ｆの精度及び関連性（妥当性）に依存する。例えば、もしコンテキスト特徴が非常に正確で関連性（妥当性）が高く、「正しい」参照ブロックのコンテキスト特徴が常に符号化ブロックのコンテキスト特徴と同一であるなら（よって、距離は０である）、当該「正しい」参照ブロックは検索ランクリストの一番上に常になければならない。結果として、ランク番号Ｒは常に１になる。したがって、Ｒのエントロピーは０であり、参照データを符号化するために０ビットが必要とされる。即ち、参照データはコンテキスト特徴から推論されるので、参照データを送信する必要はない。これはまた、ビデオエンコーダはコンテキスト特徴のみに基づいて参照ブロックを見つけることができ、参照データは必要ないということを示している。別のシナリオでは、コンテキスト特徴は完全に関連が無いと仮定し、よって、「正しい」参照ブロックは、検索ランクリスト内の任意の位置に配置できるとする。従って、Ｒの数は完全にランダムになり、ΣＭにおいて一様な分布を有する。結果として、Ｒを符号化するためにはｌｏｇＮビットが必要となり、これは上記した変換をすることなく元の参照データを符号化するのと等しいかそれより悪いかもしれない。一般的なシナリオは、これら２つの極端な状況の間にある。つまり、Ｒのエントロピーは一般に０より大きいが、ｌｏｇＮよりも小さい。結果として、変換されたデータの符号化は、元の参照データを直接符号化するよりも効率的でなければならないし、テンプレートマッチング法よりも信頼性が高くなければならない。番号Ｒの確率分布は、コンテキスト特徴の関連性と精度に関連している。番号Ｒの確率分布が公知であると仮定すると、数Ｒは、その確率分布に従って特定のエントロピー符号化法を使用して符号化することができる。一般的にＲの確率分布は幾何分布または指数分布に近いことが実験で確認されている。Ｒが幾何分布に従うならば、最適なプレフィックスコードはゴロム符号（Golomb Code）であることが、データ符号化分野では知られている。エントロピー符号化コンポーネントは、ランク番号の異なる確率分布に応じて変えられてもよい。
【００５５】
例：空間変位ベクトルの符号化
空間変位ベクトルは、符号化ブロックとその参照ブロックの間の相対的な空間座標を指す。インターフレーム予測または動き補償符号化法の場合には、空間変位ベクトルは実際には動きベクトルであり、このことにより、エンコーダは参照フレーム（例えば、ＩＳＯ／ＩＥＣのＭＰＥＧ−４パート１０ＡＶＣ規格、ＩＴＵ−Ｔ、Ｈ２６４勧告（以下、「ＭＰＥＧ−４ＡＶＣ規格」と称する）におけるイントラフレームまたはＩフレーム）内において対応する参照ブロックを見つけやすい。イントラフレームブロック予測の場合（現在のＭＰＥＧ−４ＡＶＣ規格で採用されていないが、Ｈ．２６５またはそれ以降のものでは採用されている可能性がある）、空間変位ベクトルがあると、エンコーダは、現在の符号化フレーム内に対応参照ブロックを見つけやすい（図１）。両方の場合において、変位ベクトルは相対座標である２Ｄベクトル（δｘ、δｙ）として表される。一般的に、変位ベクトルは、ブロックマッチングによって計算される。例えば、空間予測方式では、符号化ブロックは符号化ブロックと候補ブロックの間の距離を計算し、最小距離を有する参照ブロックを見つけることによって、復号化されたエリア内（図１）のすべての可能性のあるブロックにマッチングさせることができる。符号化ブロックと参照ブロックの間の相対的な座標は、空間変位ベクトルである。デコーダが復号化処理中に正しい参照ブロックを見つけることができるように、空間変位ベクトルをデコーダに送信しなければならない。
【００５６】
本発明が提案する方式では、変位ベクトルは、上記のプロセスにより符号化することができる。まず、ブロックの周囲画素がコンテキスト特徴として使用される。しかしながら、現在のブロックの下部右側はまだ復号化プロセスにおいて復号化されていないので、空間予測では、ブロックの上部左側のみがコンテキスト特徴として使用される。その後、現在のブロックのコンテキスト特徴を用いて、すべての候補参照ブロックのコンテキスト特徴をマッチングさせる。結果は昇順でソートされ、ソートされたリスト内の参照ブロックの位置（つまり、ランク）が、変換された変位ベクトルとして扱われる。最後に、エントロピー符号化が適用されてランク番号を符号化する。復号化処理は、これと逆の処理である。デコーダは、対応するブロック（本明細書では、これと同じ意味で「復号化ブロック」という用語が用いられている）が復号化されるべき時間までに、ランク番号を受け取る。復号化ブロックのコンテキスト特徴が抽出され、復号化されたエリア内のすべての許容参照ブロックのコンテキスト特徴にマッチングされる。その結果は昇順にソートされ、受信したランク番号を使用してランクリストから参照ブロックを取得する。
【００５７】
本発明の上記の特徴及び利点並びに他の特徴及び利点は、本明細書の教示内容に基づいて当業者であれば容易に確認・認識することができるであろう。本発明の教示内容は、様々な形式のハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、またはこれらの組み合わせにより実装・実現することができる。
【００５８】
最も好ましくは、本発明の教示内容は、ハードウェアとソフトウェアの組み合わせとして実装される。さらに、ソフトウェアは、プログラム記憶装置に具現化されたアプリケーションプログラムとして実装することができる。当該アプリケーションプログラムは、任意の適切なアーキテクチャを有するマシンにアップロードされて当該マシンにより実行され得る。好ましくは、当該マシンは、１つまたは複数の中央処理装置（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）及び入力／出力（Ｉ／Ｏ）インタフェースなどのハードウェアを備えるコンピュータプラットフォームに実装される。当該コンピュータプラットフォームは、オペレーティングシステム及びマイクロ命令コードを含んでもよい。本明細書に記載された様々なプロセス及び機能は、マイクロ命令コードの一部もしくはアプリケーションプログラムの一部、またはこれらの組み合わせであってよく、ＣＰＵによって実行することができる。加えて、様々な他の周辺装置、例えば、データ記憶装置及び印刷装置を、コンピュータプラットフォームに接続してもよい。
【００５９】
また、添付図面に示された基本的なシステムコンポーネント及び方法のいくつかは、好ましくはソフトウェアで実装されるので、システムコンポーネント間またはプロセス機能ブロック間の実際の接続は、本発明がどのようにプログラムされるかによって異なる可能性がある。本明細書の教示内容を理解した当業者であれば、本発明の方法・実装もしくは装置・構成と同一もしくは類似のものを考えつくであろう。
【００６０】
例示的な実施形態が添付図面を参照して本明細書に説明されたが、本発明は当該実施形態そのものに限定されず、当該実施形態に対する様々な変更及び修正が本発明の範囲及び精神から逸脱することなく当業者によってなされ得る。そのような変更及び修正のすべては、特許請求の範囲に記載された本発明の技術的範囲内に含まれる。
【図１】
2013539935.tif 000003
【図２】
2013539935.tif 000004
【図３】
2013539935.tif 000005
【図４】
2013539935.tif 000006
【図５】
2013539935.tif 000007
【図６】
2013539935.tif 000008
【図７】
2013539935.tif 000009
【国際調査報告】
2013539935.tif 000010
2013539935.tif 000011
2013539935.tif 000012