(57)【特許請求の範囲】
【請求項１】
映像信号のビデオフレームに含まれた物体の輪郭を符号化する方法であって、前記輪郭は前記輪郭上に位置する画素である複数の輪郭画素によって表され、
前記ビデオフレームを、各々Ｋ×Ｌ画素（Ｋ及びＬは各々正の整数）である複数のブロックに分割する第１過程と、
内部に前記輪郭画素を１つ以上含むブロック（輪郭ブロック）を検出する第２過程と、
前記輪郭を輪郭ブロック単位に符号化する第３過程とを含み、
前記第３過程は、
各輪郭ブロック内に含まれた連続的な輪郭画素の組である各輪郭セグメント上に於いて複数の頂点を決定する第３（Ａ）過程と、
各輪郭セグメント上の前記頂点に基づいて前記輪郭を符号化する第３（Ｂ）過程とを含み、
前記第３（Ａ）過程は、
各輪郭セグメントがオープンループである場合、輪郭セグメントの両終点を選択し、前記輪郭セグメントがクローズループである場合、輪郭セグメント上に最も遠くはなれて存在する２つの点を選択して２つの頂点を決定する第３（Ａ１）過程と、
各輪郭セグメント上の隣接する２つの頂点を連結する各直線セグメントと対応する輪郭セグメント上に存在する点の中で前記直線セグメントとの距離が最大となる点を新しい頂点として追加し、前記距離が予め定められた閾値より小さくなるまで新たな頂点の追加を繰り返す第３（Ａ２）過程とを含み、
前記第３（Ｂ）過程は、
各輪郭セグメント上の隣接する２つの頂点を連結する各直線セグメント上に於いて予め定められた個数のサンプルポイントを決定する第３（Ｂ１）過程と、
各直線セグメント上の各サンプルポイントから対応する輪郭セグメントまでの距離を求めこれをエラーとして定義し、前記エラーによって前記直線セグメントと対応する輪郭セグメントとの間の距離を表すようにする第３（Ｂ２）過程と、
エラーの組を変換係数の組に変換する第３（Ｂ３）過程と、
前記変換係数の組を量子化された変換係数の組に変換する第３（Ｂ４）過程と、
前記量子化された変換係数の組を符号化する第３（Ｂ５）過程とを含むことを特徴とする輪郭符号化方法。
【請求項２】
前記エラーの組が、各直線セグメント上の前記サンプルポイントにおけるエラーを含むことを特徴とする請求項１に記載の輪郭符号化方法。
【請求項３】
前記エラーの組が、各直線セグメント上の前記サンプルポイントと前記頂点とにおいて、エラーを含むことを特徴とする請求項１に記載の輪郭符号化方法。
【請求項４】
映像信号のビデオフレームに含まれた物体の輪郭を符号化する装置であって、前記輪郭は前記輪郭上に位置する画素である複数の輪郭画素によって表され、
前記ビデオフレームを、各々Ｋ×Ｌ画素（Ｋ及びＬは各々正の整数）である複数のブロックに分割する手段と、
内部に前記輪郭画素を１つ以上含むブロック（輪郭ブロック）を検出する手段と、
前記輪郭を輪郭ブロック単位に符号化する手段とを含み、
前記符号化手段は、
各輪郭ブロック内に含まれた連続的な輪郭画素の組である各輪郭セグメント上に於いて複数の頂点を決定する手段と、
各輪郭セグメント上の前記頂点に基づいて前記輪郭を符号化する手段とを含み、
前記頂点決定手段は、
各輪郭セグメントがオープンループである場合、輪郭セグメントの両終点を選択し、前記輪郭セグメントがクローズループである場合、輪郭セグメント上に最も遠くはなれて存在する２つの点を選択して２つの頂点を決定する手段と、
各輪郭セグメント上の隣接する２つの頂点を連結する各直線セグメントと対応する輪郭セグメント上に存在する点の中で前記直線セグメントとの距離が最大となる点を新しい頂点として追加し、前記距離が予め定められた閾値より小さくなるまで新たな頂点の追加を繰り返す手段とを含み、
前記輪郭符号化手段は、
各輪郭セグメント上の隣接する２つの頂点を連結する各直線セグメント上に於いて予め定められた個数のサンプルポイントを決定する手段と、
各直線セグメント上の各サンプルポイントから対応する輪郭セグメントまでの距離を求めこれをエラーとして定義し、前記エラーによって前記直線セグメントと対応する輪郭セグメントとの間の距離を表すようにする手段と、
エラーの組を変換係数の組に変換する手段と、
前記変換係数の組を量子化された変換係数の組に変換する手段と、
前記量子化された変換係数の組を符号化する手段とを含むことを特徴とする輪郭符号化装置。
【請求項５】
前記エラーの組が、各直線セグメント上の前記サンプルポイントにおけるエラーを含むことを特徴とする請求項４に記載の輪郭符号化装置。
【請求項６】
前記エラーの組が、各直線セグメント上の前記サンプルポイントと前記頂点とにおけるエラーを含むことを特徴とする請求項４に記載の輪郭符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、映像信号に含まれた物体（オブジェクト）の輪郭を符号化するための方法及び装置に関し、特に、輪郭近似の複雑な計算過程をより簡単化させ得る輪郭符号化方法及び装置に関する。
【０００２】
【従来の技術】
テレビ電話、電子会議及び高精細度テレビシステムのようなディジタルビデオシステムでは、ビデオフレーム信号のビデオライン信号は画素値と呼ばれる一連のディジタルデータからなり、各ビデオフレーム信号を表現するには大量のディジタルデータが必要である。しかし、通常の伝送チャンネルの利用可能な周波数帯域幅は制限されているため、特にテレビ電話のような低ビットレートの映像信号符号化システムでは多様なデータ圧縮技法を用いて相当量のデータを圧縮するか、或いは減らすことが不可避である。
【０００３】
低ビットレートの符号化システムで映像信号を符号化するための符号化方法の一つに、いわゆる物体指向分析合成符号化法（Michael Hotterの“「Object-Oriented Analysis-Synthesis Coding Based on Moving Two-Dimensional Objects」,Signal Processing:Image Communication,2,No.4,pp.409-428(December,1990)”参照）がある。
【０００４】
物体指向解析合成符号化法によると、入力映像信号は複数の物体（オブジェクト）に分けられ、各物体の動き、輪郭、画素データを規定する３セットのパラメータは異なる符号化チャンネルを通じて処理される。
【０００５】
特に、物体の輪郭を処理する際、輪郭情報は物体形状の分析及び合成に重要である。輪郭情報を表すための通常の符号化方法に、チェーン符号化法（chain coding technique）がある。チェーン符号化法は輪郭情報の損失はないが、輪郭情報を表すのに多量のビットが必要であるという不都合がある。
【０００６】
この点に関して、多角形近似及びＢ−スプライン近似のような輪郭近似法が幾つか提案されてきた。多角形近似の短所の１つは輪郭の表現が粗くなるということである。Ｂ−スプライン近似は輪郭をより正確に表すことができるが、近似誤差（エラー）を減らすのに高次多項式を必要とし、ビデオ符号化の全体的な計算量を増大させる。
【０００７】
上記のような粗い輪郭表現及び全体的な計算量の増加の問題点を解消するために提示された方法の１つが多角形近似と離散サイン変換（ＤＳＴ）を共に用いた輪郭近似法である。この技法は１９９５年４月１７日に出願された本出願人による係属中の米国特許第出願08/423,604号明細書「A CONTOUR APPROXIMATION APPARATUS FOR REPRESENTING A CONTOUR OF AN OBJECT」に開示されている。しかし、この技術はフレーム全体に対し輪郭の多角形近似及びＤＳＴを行うために、複雑な輪郭を扱う場合、輪郭近似の複雑な計算過程をより簡単にする必要がある。
【０００８】
【発明が解決しようとする課題】
従って、本発明の主な目的は、輪郭近似の複雑な計算過程をより簡単にし得る輪郭符号化方法及び装置を提供することである。
【０００９】
【課題を解決するための手段】
上記の目的を達成するために、本発明によれば、映像信号のビデオフレームに含まれた物体の輪郭を符号化する方法であって、前記輪郭は前記輪郭上に位置する画素である複数の輪郭画素によって表され、前記ビデオフレームを、各々Ｋ×Ｌ画素（Ｋ及びＬは各々正の整数）である複数のブロックに分割する第１過程と、内部に前記輪郭画素を１つ以上含むブロック（輪郭ブロック）を検出する第２過程と、前記輪郭を輪郭ブロック単位に符号化する第３過程とを含むことを特徴とする輪郭符号化方法が提供される。
【００１０】
【発明の実施の形態】
以下、本発明の好適実施について図面を参照しながらより詳しく説明する。
【００１１】
図１には、映像信号のビデオフレームに含まれた物体の輪郭を符号化するための本発明による輪郭符号化装置１０のブロック図が示されている。
【００１２】
輪郭符号化装置１０は、輪郭ブロック検出器１００、開始頂点決定ブロック１１０、多角形近似ブロック１２０、サンプリング及びエラー検出ブロック１３０、変換及び量子化ブロック１４０、輪郭符号化器１５０を含む。
【００１３】
ビデオフレームに含まれた物体の輪郭データは輪郭ブロック検出器１００へ入力される。ここで、輪郭データは輪郭画素の位置情報を表し、輪郭画素は物体の輪郭上にある画素である。
【００１４】
輪郭ブロック検出器１００で、ビデオフレームはまず複数のＫ×Ｌ画素ブロック（ここで、Ｋ及びＬは各々正の整数）に分割され、それから輪郭ブロックが検出される。ここで、輪郭ブロックとは輪郭画素を１つ以上有するブロックである。例えば、図２に例示されているように、斜線領域２０内に位置する各ブロックはビデオフレーム４０での輪郭３０の一部を含んでおり、従って輪郭ブロックである。各輪郭ブロック内に含まれる輪郭画素の位置情報は開始頂点決定ブロック１１０へ送られる。
【００１５】
開始頂点決定ブロック１１０は各輪郭ブロック内で各輪郭セグメントの終点を探し、終点が検出された場合、検出された２つの終点をその輪郭セグメントの開始頂点として選択する。ここで、輪郭セグメントとは輪郭ブロック内に存在する連続的な輪郭画素の組である。
【００１６】
図３に、開始頂点決定ブロック１１０で行われる開始頂点の決定過程の一例を示す。図３に示したように、輪郭ブロックＭ内にオープンループ形の輪郭セグメント３３及び３５が存在している場合、２つの終点Ａ及びＢが輪郭セグメント３３の開始頂点として決定され、２つの終点Ｃ及びＤが輪郭セグメント３５の開始頂点として選択される。輪郭ブロック内に存在する輪郭セグメントがクローズループ形である場合は、通常の多角形近似法の場合と同じように、輪郭セグメント上に存在する最も離れた２つの画素が開始頂点として選択される。輪郭セグメントが１つの輪郭画素のみからなる場合、その輪郭セグメントに対しては開始頂点は決定されない。２以上の輪郭画素を含む各輪郭セグメントの開始頂点を決定した後、輪郭セグメントの開始頂点の位置情報を表す開始頂点データと、輪郭セグメントを構成する輪郭画素の位置データを表す輪郭セグメントデータとを多角形近似ブロック１２０へ伝送する。
【００１７】
各輪郭セグメントの開始頂点データ及び輪郭セグメントデータを用いて、多角形近似ブロック１２０は、直線セグメントで輪郭セグメントを近似する通常の近似アルゴリズムによって各輪郭セグメントを近似する。
【００１８】
図４に、多角形近似法による輪郭セグメント３３のセグメンテーション過程を例として示す。
【００１９】
まず、輪郭セグメント３３の開始頂点ＡとＢを結ぶ直線セグメントＡＢを引き、直線ＡＢとこれから最も遠くはなれて存在する輪郭セグメント３３上の輪郭画素（Ｅ）との距離ＤＭＡＸを求める。
【００２０】
直線ＡＢと点Ｅとの間の距離ＤＭＡＸが予め定められた値より大きい場合、点Ｅは頂点として追加され、ＡとＥ、ＢとＥを連結する直線セグメントＡＥ、ＥＢを引くことができる。同様の過程を各直線セグメントに対するＤＭＡＸが予め定められた閾値より小さくなるまで繰り返す。
【００２１】
追加される頂点の個数は、予め定められた閾値によって変化する。予め定められた閾値が小さい程、直線セグメントによる輪郭セグメントの近似はより精密になるが、符号化効率は低下する。
【００２２】
図１を再度参照されたい。多角形近似ブロック１２０は、各輪郭セグメントに対する開始頂点及び追加された頂点、例えば、Ａ、Ｂ及びＥの位置を表す頂点情報をラインＬ１０を通じてサンプリング及びエラー検出ブロック１３０へ送るとともに、各輪郭セグメントに対する輪郭セグメントデータをラインＬ２０を通じてサンプリング及びエラー検出ブロック１３０へ供給する。
【００２３】
サンプリング及びエラー検出ブロック１３０は、輪郭セグメント上の隣接する２つの頂点間を結ぶ各直線セグメントに対してＮ個のサンプルポイントを選択する。ここで、Ｎ個のサンプルポイントは等間隔に並び、Ｎは正の整数である。そして、頂点情報及び輪郭セグメントデータを用いてＮ個のサンプルポイント各々での近似エラーを計算する。ここで、各サンプルポイントでの近似エラーは、そのサンプルポイントにおける直線セグメントと輪郭セグメントとの間の距離を表す。
【００２４】
図５は、直線セグメントＡＥとこれに対応する輪郭セグメントとの間の近似エラーを表す例示図である。各近似エラーｄ１〜ｄ４は直線セグメントＡＥ上に存在するサンプルポイントｓ１〜ｓ４の各々から対応する輪郭セグメントまでの距離を表す。ここで、頂点Ａ及びＥでの近似エラーはゼロである。本発明による好適実施例では、各近似エラーは予め定められた方法によって決定される符号を含む。これによって、受信側の復号化器では、各近似エラーによって表された前記輪郭セグメントの部分、即ち、輪郭画素が直線セグメントの上下どちらの側にあるか判断することができる。各直線セグメントに対する近似エラーの組は変換及び量子化ブロック１４０へ送られる。
【００２５】
変換及び量子化ブロック１４０は、まず、例えば離散サイン変換（ＤＳＴ）を用いて、近似エラーの組を変換係数の組に変換する。ここで、近似エラーの各組は各直線セグメントの２つの頂点及びＮ個のサンプルポイントに対する近似エラーを含むか、或いはＮ個のサンプルポイントの近似エラーだけを含む。続いて、前記変換係数の組は公知の量子化法によって量子化される。各直線セグメントに対応する量子化された変換係数の組は次の過程のために輪郭符号化器１５０へ送られる。
【００２６】
輪郭符号化器１５０に於いて、量子化された変換係数の各組は、例えばＪＰＥＣの２進算術符号を用いて符号化される。一方、頂点情報は、頂点間の相関が低いので、例えば非圧縮の固定長符号を用いて符号化される。符号化された量子化された変換係数及び頂点情報を含む符号化されたディジタル信号は、送信器へ送られ伝送される。
【００２７】
上記において、本発明の特定の実施例について説明したが、本明細書に記載した特許請求の範囲を逸脱することなく、当業者は種々の変更を加え得ることは勿論である。また、本方法はコンピュータをプログラムに従って動作させることで実行可能であり、本装置はプログラムに従って動作するコンピュータによって実現可能である。そのようなプログラムは所定の媒体に記憶させることが可能である。
【００２８】
【発明の効果】
従って、本発明による輪郭符号化方法及び装置は、映像信号に含まれた物体の輪郭を輪郭ブロック単位で符号化することによって、輪郭近似の複雑な計算過程をより簡単にすることができる。
【図面の簡単な説明】
【図１】本発明による輪郭符号化装置のブロック図である。
【図２】輪郭ブロックを説明するための図面である。
【図３】本発明による開始頂点決定過程を説明するための図面である。
【図４】輪郭セグメントの近似過程を例示的に示した図面である。
【図５】２つの頂点間に於いて対応する輪郭セグメントを近似する直線セグメントのサンプルポイントにおけるエラーを例示した図面である。
【符号の説明】
１０  輪郭符号化装置
１００  輪郭ブロック検出器
１１０  開始頂点決定ブロック
１２０  多角形近似ブロック
１３０  サンプリング及びエラー検出ブロック
１４０  変換及び量子化ブロック
１５０  輪郭符号化器
【図１】
0003917691.tif 000002
【図２】
0003917691.tif 000003
【図３】
0003917691.tif 000004
【図４】
0003917691.tif 000005
【図５】
0003917691.tif 000006