(57)【特許請求の範囲】
【請求項１】
ブロック単位の映像信号符号化システムに用いられ、映像信号からなる映像物体平面（ＶＯＰ）を各々がＮ×Ｎ個の画素（Ｎは正の整数）からなり同一の大きさを有する、複数のブロックに分ける最適のグリッドを決定する最適グリッド決定方法であって、
各々が隣接したグリッドから予め決められた間隙だけ相対的にシフトされる複数のグリッドを発生する第１工程と、
前記各グリッドに於いて、各々が物体の境界部分を有する、ブロックを表す複数のエッジブロックを該物体の形状情報に基づいて検出する第２工程と、
前記エッジブロックの個数及び前記エッジブロックにおける画素値に基づいてグリッドをえり抜けると共に、選択されたグリッドを前記最適グリッドとして発生する第３工程
とを含み、
前記第３工程が、
前記グリッドの中で、最小の数のエッジブロックを有するグリッドを選択する選択工程と、
複数のグリッドが同一の最小数のエッジブロックを有する場合、前記グリッドの各々に含まれた前記エッジブロックの画素値に基づいて、前記グリッドの各々に対して、前記エッジブロックの画素値間の分散度を表す平均活性値を計算する計算工程と、
前記複数のグリッドの中で、最小の平均活性値を有するグリッドを検出する検出工程と、
前記検出されたグリッドを前記最適グリッドとして決める決定工程とを有することを特徴とする最適グリッド決定方法。
【請求項２】
前記計算工程が、
Ｍがエッジブロック内のＮ×Ｎ個の画素数を、Ｈ（ｉ，ｊ）が該エッジブロックの画素位置（ｉ，ｊ）での画素値を、ｍが該エッジブロック内の画素値の平均値を各々表し、ｉ及びｊが各々Ｎ未満の正の整数であるとき、前記グリッドの各々に含まれた前記エッジブロックの画素値に基づいて、前記グリッドの各々に於ける各エッジブロックに対する活性度を次式
【数１】
0003903445.tif 000003
の通り計算する工程と、
前記グリッドにおける全てのエッジブロックに対する前記活性度全体を平均して、前記グリッドに対する平均活性度を求める工程とをさらに有することを特徴とする請求項１に記載の最適グリッド決定方法。
【請求項３】
前記グリッドの各々が、互いに画素単位でシフトされることを特徴とする請求項２に記載の最適グリッド決定方法。
【請求項４】
前記画素値が該当画素の輝度レベルを表すことを特徴とする請求項３に記載の最適グリッド決定方法。
【請求項５】
ブロック単位の映像信号符号化システムに用いられ、映像信号からなる映像物体平面（ＶＯＰ）を各々がＮ×Ｎ個の画素（Ｎは正の整数）からなり同一の大きさを有する、複数のブロックに分ける最適のグリッドを決定する最適グリッド決定装置であって、
各々が隣接したグリッドから予め決められた間隙だけ相対的にシフトされる複数のグリッドを発生するグリッド発生手段と、
前記各グリッドに於いて、各々が物体の境界部分を有する、ブロックを表す複数のエッジブロックを該物体の形状情報に基づいて検出するエッジブロック検出手段と、
前記エッジブロックの個数及び前記エッジブロックにおける画素値に基づいて、グリッドをえり抜けると共に、選択されたグリッドを前記最適グリッドとして発生する最適グリッド発生手段
とを含み、
前記最適グリッド発生手段が、
前記グリッドの中で、最小の数のエッジブロックを有するグリッドを選択する選択手段と、
複数のグリッドが同一の最小数のエッジブロックを有する場合、前記グリッドの各々に含まれた前記エッジブロックの画素値に基づいて、前記グリッドの各々に対して、前記エッジブロックの画素値間の分散度を表す平均活性度を計算する平均活性度計算手段と、
前記複数のグリッドの中で、最小の平均活性度を有するグリッドを検出する検出手段と、
前記検出されたグリッドを前記最適グリッドとして決める決定手段とを有することを特徴とする最適グリッド決定装置。
【請求項６】
前記平均活性度計算手段が、
Ｍがエッジブロック内のＮ×Ｎ個の画素数を、Ｈ（ｉ，ｊ）が該エッジブロックの画素位置（ｉ，ｊ）での画素値を、ｍが該エッジブロック内の画素値の平均値を各々表し、ｉ及びｊが各々Ｎ未満の正の整数であるとき、前記グリッドの各々に含まれた前記エッジブロックの画素値に基づいて、前記グリッドの各々に於ける各エッジブロックに対する活性度を次式
【数２】
0003903445.tif 000004
の通り計算する活性度計算手段と、
前記グリッドにおける全てのエッジブロックに対する前記活性度全体を平均して、前記グリッドに対する平均活性度を求める平均化手段とを更に有することを特徴とする請求項５に記載の最適グリッド決定装置。
【請求項７】
前記グリッドの各々が、互いに画素単位でシフトされることを特徴とする請求項６に記載の最適グリッド決定装置。
【請求項８】
前記画素値が、該当画素の輝度レベルを表すことを特徴とする請求項７に記載の最適グリッド決定装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ブロック単位の映像信号符号化システムに用いられる最適グリッド決定方法及びその装置に関し、特に、物体映像を表現する映像信号の符号化効率を向上させるための最適グリッド決定方法及びその装置に関する。
【０００２】
【従来の技術】
公知のように、ディジタル映像信号の伝送はアナログ信号よりも高画質の映像を得ることができる。一連のイメージ「フレーム」からなる映像信号が、画素値という一連のディジタル形態に表現される場合、とりわけ、テレビ電話、電子会議及び高精細度テレビのようなディジタルテレビジョンシステムにおいて、その伝送の際に大量のデータが必要となる。しかしながら、従来の伝送チャネル上の利用可能な周波数帯域幅が制限されているので、その制限されたチャネルを通じて大量のディジタルデータを伝送するためには、特に、テレビ電話または電子会議システムのような低ビットレートの映像信号符号化器の場合、伝送すべきデータの量を圧縮するか減らす必要がある。
このような多様な映像圧縮技法のうちの一つに、いわゆる、物体指向分析−合成(object-oriented analysis-synthesis)符号化技法がある。ここで入力映像信号は複数の物体（オブジェクト）に分けられ、各物体の動き、輪郭線及び画素データを定義する３セットからなるパラメータが異なる符号化チャネルを通じて処理される。
【０００３】
物体指向分析−合成符号化技法の一例に、いわゆる動映像専門家グループ４（ＭＰＥＧ−４）がある。ここで、ＭＰＥＧ−４によれば低ビットレートの通信方式、対話形マルチメディア（例えば、ゲーム、対話式ＴＶ等）及びエリア監視のような用途で内容単位の双方向性、改良された符号化効率及び／または汎用性を与えるようにオーディオ／ビデオ符号化標準案が提示されている（例えば、ＭＰＥＧ−４ Video Verification Model Version 2.0, International Organization for Standardization,  ＩＳＯ／ＩＥＣ  ＪＴＣ１／ＳＣ２９／ＷＧ１１  Ｎ１２６０，March １９９６  参照）
【０００４】
このＭＰＥＧ−４によると、入力映像は複数の映像物体平面（以下、ＶＯＰ（Video object plane）と称す）に分けられ、各ＶＯＰは使用者がアクセス可能且つ造作可能なビットストリームにおけるエンティティに対応する。ＶＯＰは物体としても呼ばれ、その幅及び高さが各物体を取り囲む１６画素（マクロブロックの大きさ）の最小倍数となる四角形で表現され得る。かくして、符号化器は入力映像信号をＶＯＰ単位、即ち、物体単位に処理できる。
即ち、ＶＯＰは四角境界線で表され、この四角境界線の輝度成分（Ｙ）と色成分（Ｕ、Ｖ）との間の位相差は４：２：０の比で正確に定まる。詳述すると、各色データが４：２：０の比で４（＝２×２）個の輝度データに関連されるので、四角形の左側座標は各物体を取り囲む最小四角形の左側上端座標（例えば、（２ｎ＋１、２ｍ＋１））より大きくなく、最も近くの偶数座標（例えば、（２ｎ、２ｍ））に定まるべきである。ここで、ｎ及びｍは正の整数である。この四角形の右側下端は該四角形の幅及び高さが１６画素の最小倍数になるよう拡張される。
ＭＰＥＧ−４で言及した境界四角形の情報は、形状情報と、輝度データ及び色データからなるカラ−情報とを有する。この形状情報は例えば２進マスクで表現され、輝度データと関連される。２進マスクにおいて、一方の２進値（例えば、０）は境界四角形における物体外部に位置する画素を、他方の２進値（例えば、１）は物体内部に位置する画素を各々表すに用いられる。従って、ＶＯＰでの輝度データは輝度形状情報という２進マスクにて処理されることによって、符号化の際に有用な輝度データとして選択されることになる。
【０００５】
境界四角形内部にある輝度データを取り扱うためには、この境界四角形は大体、グリッドにより区切られる同一大きさのブロックに分けられた後、各ブロックをブロック単位で多様なブロック単位の符号化技法（例えば、ＤＣＴ符号及び量子化）を用いて順に符号化されるべきである。
しかし、映像信号の符号化効率は物体の境界領域によって激しく左右されるので、伝送すべきデータの量をより一層減らすためには、物体の境界線を含むブロックの数をさらに減らすことが好ましい。
【０００６】
【発明が解決しようとする課題】
従って、本発明の目的は、ブロック単位の映像信号符号化システムに用いられ、ＶＯＰに対して、物体の境界線を取り囲むエッジブロック、即ち、ブロックの数を最小化して、映像信号の符号化効率を増大させ得る最適グリッド決定方法及びその装置を提供することにある。
本発明の他の目的は、ＶＯＰに対して最適のグリッドを決定して、最小平均活性度を有するエッジブロックを効率的に形成することによって、映像信号の符号化効率を増大させ得る最適グリッド決定方法及びその装置を提供することにある。
【０００７】
【課題を解決するための手段】
上記の目的を達成するために、本発明によれば、ブロック単位の映像信号符号化システムに用いられ、映像信号からなる映像物体平面（ＶＯＰ）を各々がＮ×Ｎ個の画素（Ｎは正の整数）からなり同一の大きさを有する、複数のブロックに分ける最適のグリッドを決定する最適グリッド決定方法であって、各々が隣接したグリッドから予め決められた間隙だけ相対的にシフトされる複数のグリッドを発生する第１工程と、前記各グリッドに於いて、各々が物体の境界部分を有する、ブロックを表す複数のエッジブロックを該物体の形状情報に基づいて検出する第２工程と、前記エッジブロックの個数及び前記エッジブロックにおける画素値に基づいてグリッドをえり抜けると共に、選択されたグリッドを前記最適グリッドとして発生する第３工程とを含み、前記第３工程が、前記グリッドの中で、最小の数のエッジブロックを有するグリッドを選択する選択工程と、複数のグリッドが同一の最小数のエッジブロックを有する場合、前記グリッドの各々に含まれた前記エッジブロックの画素値に基づいて、前記グリッドの各々に対して、前記エッジブロックの画素値間の分散度を表す平均活性値を計算する計算工程と、前記複数のグリッドの中で、最小の平均活性値を有するグリッドを検出する検出工程と、前記検出されたグリッドを前記最適グリッドとして決める決定工程とを有することを特徴とする最適グリッド決定方法が提供される。
【０００８】
【発明の実施の形態】
以下、本発明の好適実施例について図面を参照しながらより詳しく説明する。
図１を参照すれば、本発明の好適実施例に基づいて、ブロック単位の映像信号符号化システムに用いられるＶＯＰの最適グリッド決定装置（以下、最適サーチグリッド決定装置ともいう）１０のブロック図が示されている。この最適サーチグリッド決定装置１０は、サーチグリッド生成回路２０−１〜２０−Ｍ、エッジブロック検出回路４０−１〜４０−Ｍ、活性度計算回路７３−１〜７３−Ｍ、第１コンパレータ５０、第２コンパレータ７０及びマルチプレクサ７５を含む。
図示したように、物体の境界を表す形状情報は各エッジブロック検出回路４０−１〜４０−Ｍに供給される。この形状情報は殆ど２進マスク（即ち、「０」及び「１」）で表示されている。一方、輝度データ及び色データからなる映像フレーム信号は各活性度計算回路７３−１〜７３−Ｍに入力される。
【０００９】
グリッド生成回路（以下、サーチグリッド生成回路ともいう）２０−１〜２０−Ｍからは第１〜Ｍ番目のグリッド（以下、サーチグリッドともいう）が生成される。ここに、各サーチグリッドは隣接グリッドを予め定められた画素数だけシフトすることによって形成される。
各々のサーチグリッド生成回路は、サーチグリッド情報、即ち、対応するサーチグリッドに対するオフセット分情報を各エッジブロック検出回路４０−１〜４０−Ｍ、活性度計算回路７３−１〜７３−Ｍ及びマルチプレクサ７５に各々送り出す。
図２を参照すれば、一つのフレーム２１をカバーするサーチグリッド２２の一例が概略的に示されている。サーチグリッド２２は無限格子であり、このサーチグリッド２２により形成された同一の大きさのセルがブロック（以下、探索ブロックともいう）２３を形成することになる。探索ブロック２３はＮ×Ｎ個の画素からなり、Ｎは正の整数（例えば、８または１６）であり、ＭはＮ×Ｎと等しい。そして、探索ブロックの大きさＮは符号化信号の形態によって左右される。
【００１０】
サーチグリッド２２がシフト可能であるので、複数の異なるオフセット分に対応する複数の移動量が有り得る。ここで、オフセット分はフレーム２１の最左側上段の画素とサーチグリッド２２の最左側上段の探索ブロックとの間の変位を表す。
図３を参照すれば、最左側上段の探索ブロックの座標（１，１）の画素がフレームの座標（３，２）の画素に位置する場合、サーチグリッドはオフセット分（３，２）に対応する（３，２）サーチグリッドとして呼ばれる。同様に、オフセット分（２，３）に対応するサーチグリッドは（２，３）サーチグリッドとして名付けられる。
サーチグリッドがシフトされる場合に、不完全な探索ブロック２４が生じ得る。この不完全な検索ブロック２４は、図２に示したように、検索ブロック２３とは異なり、Ｎ×Ｎ個の画素を有しないことになる。サーチグリッドが画素単位でシフト可能であるので、一つの探索ブロックがＮ×Ｎ個の画素を有する場合、Ｍ（＝Ｎ×Ｎ）個のオフセット分に対応するＭ（＝Ｎ×Ｎ）個のシフトされたサーチグリッドが有り得る。しかし、必要によって、サーチグリッドは４：２：０の比で色レベルを符号化するために、二つの画素単位でシフトされ得る。ここで、各色レベルは隣接した四つの輝度レベルと関係がある。
たとえ、物体が一つの探索ブロックよりずっと大きいとしても、最小数の探索ブロックで該物体を取り囲むように複数のサーチグリッドが選択されることができる。
【００１１】
図１を再度参照すれば、形状情報と各サーチグリッド生成回路２０−１〜２０−Ｍから受け入れたサーチグリッド情報とに応じて、対応するエッジブロック検出回路４０−１〜４０−Ｍはエッジブロックを検出して、エッジブロックの位置を表すエッジブロック情報を生成する。図２に示したように、エッジブロック２５は、物体の境界線２６を少しでも含む探索ブロックを表し、各エッジブロック内では形状情報を表す各２進値が異なることになる。詳しくは、一つの探索ブロックにおいて各２進値が異なる場合、即ち、２進値が「０」と「１」の両方がある場合には、該探索ブロックはエッジブロックとして称され、内部にある全ての２進値が同じである（即ち、全ての２進値が「０」または「１」）場合は、該探索ブロックはエッジブロックでないと決まる。
本実施例では、物体の符号化効率が物体の境界で急に変化するので「エッジ」検出したが、必要によって、他の実施例で「エッジ」の代わりに物体を検出して符号化効率を高めることもよい。この場合、物体を表現する２進値「１」を有する探索ブロックが物体ブロックとなって、物体ブロックの位置を表す物体情報がエッジブロック情報の代わりに用いられ得る。
図１を再び参照すれば、各エッジブロック検出回路４０−１〜４０−Ｍは、対応するサーチグリッドに対するエッジブロック情報をラインＬ１１〜ＬＭ１を通じて対応する活性度計算回路７３−１〜７３−Ｍ及びマルチプレクサ７５に各々供給する。
【００１２】
また、各エッジブロック検出回路４０−１〜４０−Ｍは、対応するサーチグリッドに対するエッジブロックの数をカウントして、エッジブロック数を表す信号を発生する。もちろん、不完全な探索ブロックに対して通常の符号化技法を適用することが不可能であるので、ある不完全な探索ブロックが物体の一部境界線を含む場合には、対応するサーチグリッドに対するエッジブロック数の信号を最大値で割り当てて、次の符号化過程にてそのサーチグリッドを無視することが好ましい。エッジブロック検出回路４０−１〜４０−Ｍからの全てのエッジブロック数の信号は各ラインＬ１２〜ＬＭ２を通じて第１コンパレータ５０に供給される。
【００１３】
第１コンパレータ５０は、受け取った全てのエッジブロック数を比較すると共に、全てのエッジブロック数中で最小数を選択し、選択された第１選択信号を第２コンパレータ７０に供給する。この第１選択信号は最小数のエッジブロックを有するサーチグリッドを表す。複数のサーチグリッドが同一の最小数のエッジブロックを有する場合、対応するサーチグリッドが選択されると共に、第１選択信号として第２コンパレータ７０に伝送される。
一方、各エッジブロック検出回路４０−１〜４０−Ｍからのエッジブロック情報に基づいて、各活性度計算回路７３−１〜７３−Ｍは対応するサーチグリッドに含まれた各エッジブロックに対する活性度ＡＶを下記式、
【数３】
0003903445.tif 000002
ここで、Ｍ：エッジブロック内の画素数、Ｎ×Ｎと等しい
Ｈ（ｉ，ｊ）：該エッジブロックの画素位置（ｉ，ｊ）に置かれた画素値（例えば、輝度レベルまたは色レベル
ｍ：該エッジブロックの内部の全ての画素値に対する平均画素値
ｉ，ｊ：Ｎ以下の正の整数
のように計算する。その後、各活性度計算回路７３−１〜７３−Ｍは、対応するサーチグリッドに対する平均活性度を計算する。この平均活性度は、対応するサーチグリッド内の全てのエッジブロックの活性度に対する平均値である。
第１コンパレータ５０からの第１選択信号及び活性度計算回路７３−１〜７３−Ｍからの全ての平均活性度に応じて、第２コンパレータ７０は第１選択信号に当たる各サーチグリッドに対する全ての平均活性度をお互いに比較すると共に、該サーチグリッドに対する最小平均活性度を選択して、その値を第２選択信号としてマルチプレクサ７５に供給する。この第２選択信号は、各エッジブロックに対する各平均活性度の最小値を有するサーチグリッドを表す。
【００１４】
本発明による他の好適実施例において、第１コンパレータ５０によって複数のサーチグリッドが同数の最小エッジブロックを有するものとして選択される場合、最初、全てのサーチグリッドに対してでなく、選択されたサーチグリッドに対してのみ平均活性度を計算した後、選択されたサーチグリッドのうち最小の平均活性度を有する一つのサーチグリッドを選択してもよい。
第２選択信号と各サーチグリッド生成回路２０−１〜２０−Ｍからのサーチグリッド情報とに基づいて、マルチプレクサ７５は最小のエッジブロック数を有するサーチグリッドのうち最小の平均活性度を有する一つのサーチグリッドを選択する。また、マルチプレクサ７５は各エッジブロック検出回路４０−１〜４０−Ｍから入力されたエッジブロック情報に基づいて、選択されたサーチグリッドに対するサーチグリッド情報及びエッジブロック情報を現フレームに対する最適サーチグリッド情報として次のプロセッサへ伝送する。
即ち、最適サーチグリッド情報（例えば、Ｋ番目のサーチグリッド情報）は映像信号を符号化するための複数の符号化プロセッサ（例えば、ＤＣＴ及び量子化プロセッサ）（図示せず）に供給される。従って、この符号化プロセッサにて、最適サーチグリッドを用いて探索ブロック単位に映像信号の符号化処理が行われる。
上記において、本発明の好適な実施の形態について説明したが、本発明の請求範囲を逸脱することなく、当業者は種々の改変をなし得るであろう。
【００１５】
【発明の効果】
従って、本発明によれば、ＶＯＰに対して、物体の境界線を取り囲むエッジブロックの数を最小化することによって、映像信号の符号化効率をより一層増大させ得ることができる。
【図面の簡単な説明】
【図１】  本発明によるＶＯＰの最適グリッド決定装置のブロック図である。
【図２】  本発明による一つのグリッドによって形成されたブロックと物体の境界上に形成されたエッジブロックとを示した模式図である。
【図３】  本発明に基づいてグリッドのオフセットを説明するための例示フレームを示した模式図である。
【符号の説明】
１０  最適グリッド決定装置
２０−１〜２０−Ｍ  グリッド生成回路（サーチグリッド生成回路）
２１  フレーム
２２  グリッド（サーチグリッド）
２３  ブロック（探索ブロック）
２４  不完全なブロック（不完全な探索ブロック）
２５  エッジブロック
２６  物体境界線
４０−１〜４０−Ｍ  エッジブロック検出回路
５０  第１コンパレータ
７０  第２コンパレータ
７３−１〜７３−Ｍ  活性度計算回路
７５  マルチプレクサ
【図１】
0003903445.tif 000005
【図２】
0003903445.tif 000006
【図３】
0003903445.tif 000007