(57)【特許請求の範囲】
【請求項１】
ビデオ信号エンコーダに用いられ、オブジェクトの輪郭映像を表すための輪郭近似方法であって、
前記輪郭映像上の複数の頂点を特定する第１過程と、
前記輪郭映像に、各々が２つの隣接する頂点を結ぶ複数のラインセグメントを当てはめて、多角形近似を求める第２過程と、
前記ラインセグメント上の前記２つの頂点の位置をセグメントデータとして求める第３過程と、
前記ラインセグメントに対して複数のサンプル点を特定すると共に、各ラインセグメントを同一の長さのより小さいセグメントに分割する、前記サンプル点の位置を表すサンプル点の情報を求める第４過程と、
前記ラインセグメント上の各サンプル点及び頂点において、２つの頂点を結ぶラインセグメントとそれらの頂点の間の輪郭セグメントとの間の距離を表す、第１エラーを計算する第５過程と、
前記サンプル点及び前記頂点に対する第１エラーを、一組の離散的正弦変換係数に変換する第６過程と、
前記一組の離散的正弦変換係数の各々を量子化された一組の変換係数に変換する第７過程と、
前記量子化された一組の変換係数を再構成された一組の第１エラーに変換する第８過程と、
前記ラインセグメントの各々に対するセグメントデータ、サンプル点情報及び一組の第１エラーに基づいて、再構成された輪郭セグメントを求める第９過程と、
前記再構成された輪郭セグメントとそれに対応する元の輪郭セグメントとの間の不一致の画素数である第２エラーを計算する第１０過程と、
予め定めた閾値と前記第２エラーとを比較する第１１過程と、
前記第２エラーが前記予め定めた閾値以下である場合、前記輪郭セグメントのセグメントデータと量子化された一組の変換係数を符号化するか、あるいは前記第２エラーが前記予め定めた閾値以上である場合、前記輪郭セグメント上に付加頂点を加えることによって、前記輪郭セグメントを新たに分割された輪郭セグメントに分割すると共に、新たに分割された輪郭セグメントの各々に対応するラインセグメントに対して前記第３過程乃至第１２過程を繰り返す第１２過程と、
前記第１過程で特定された頂点により形成された全ラインセグメントに対して、前記第１過程乃至前記第１２過程を繰り返す第１３過程と
を含むことを特徴とする輪郭近似方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はビデオ信号エンコーダに用いるための輪郭近似方法に関し、特に、オブジェクトの輪郭を正確に再構成するための輪郭近似方法に関するものである。
【０００２】
【従来の技術】
従来のビデオ電話、電子会議システム及び高精細度テレビジョンシステムのようなディジタルテレビジョンシステムにおいては、ビデオフレーム信号におけるビデオライン信号が画素値と称されるディジタルデータのシーケンスを含むので、各ビデオフレーム信号を規定するのに大量のディジタルデータが必要である。しかし、通常の伝送チャネル上の利用可能な周波数帯域幅は制限されているので、そのチャネルを経て相当な量のディジタルデータを伝送するためには、様々なデータ圧縮技法を用いてデータ量を圧縮するか、或いは減らすことが不可避である。特に、ビデオ電話或いは電子会議システムのような低ビットレートのビデオ信号エンコーダの場合、そのようなデータ圧縮技法が必要となる。
【０００３】
低ビットレート符号化システムのビデオ信号を符号化するための符号化方法の一つに、いわゆるオブジェクト指向分析−合成符号化技法(Object-oriented analysis coding technique (Michael Hotterの論文，「Object-Oriented Analysis-Senthesis Coding Based on Moving Two-Dimensional Objects 」,Signal Processing:Image communication 2,409-428頁 (1990年12月) 参照) がある。
【０００４】
このオブジェクト指向分析−合成符号化技法によれば、入力ビデオ映像を複数のオブジェクトに分け、また、各オブジェクトの動き、輪郭及び画素データを規定する３組のパラメータを異なる符号化チャネルを介して処理する。
【０００５】
とりわけ、オブジェクトの輪郭映像の処理において、輪郭情報はオブジェクトの形状の分析及び合成に重要である。この輪郭情報を表すための通常の符号化方法にチェーン符号化 (chain coding) 法がある。しかし、このチェーン符号化法は、輪郭情報の損失はないが、相当な量のビットが必要である。
【０００６】
この点に関しては、多角形近似或いはＢ−スプライン近似（Ｂ−Spline approximation) のような輪郭を近似させるための幾つかの方法が提案されてきた。多角形近似における欠点の一つは、輪郭映像が粗く表現されることにある。一方、Ｂ−スプライン近似は輪郭映像をより正確に表現しうるが、近似エラーを減らすのに高次の多項式が必要になって、ビデオエンコーダにおける総体的な計算の複雑さを増すことになる。そのような総体的な計算の複雑さの欠点を回避するために提案された方法の一つに、多角形近似法及び離散的サイン変換（ＤＳＴ）法を採用する輪郭近似法がある。この方法は１９９５年４月１７日に出願された、本願発明と出願人を同じくする係属中の米国特許第０８／４２３，６０４号明細書、「A CONTOUR APPROXIMATION APPARATUS FOR REPRESENTING A CONTOUR OF AN OBJECT 」に記載されている。しかし、複雑な輪郭映像を扱う場合、多角形近似法及びＤＳＴ法を用いた上記の方法は、元の輪郭映像に比べて非常に異なる再構成された輪郭映像をもたらすという問題点がある。
【０００７】
【発明が解決しようとする課題】
従って、本発明の主目的は、多角形近似と離散的正弦変換（ＤＳＴ）を用いることによって、輪郭映像を表現する際の正確さを高め、かつ総体的な計算量を減少させた改善された輪郭近似方法を提供することにある。
【０００８】
【課題を解決するための手段】
上記の目的を達成するために、本発明によれば、ビデオ信号エンコーダに用いられ、オブジェクトの輪郭映像を表すための輪郭近似方法であって、前記輪郭映像上の複数の頂点を特定する第１過程と、前記輪郭映像に、各々が２つの隣接する頂点を結ぶ複数のラインセグメンを当てはめて、多角形近似を求める第２過程と、前記ラインセグメント上の前記２つの頂点の位置をセグメントデータとして求める第３過程と、前記ラインセグメントに対して複数のサンプル点を特定すると共に、各ラインセグメントを同一の長さのより小さいセグメントに分割する、前記サンプル点の位置を表すサンプル点の情報を求める第４過程と、前記ラインセグメント上の各サンプル点及び頂点において、２つの頂点を結ぶラインセグメントとそれらの頂点の間の輪郭セグメントとの間の距離を表す、第１エラーを計算する第５過程と、前記サンプル点及び前記頂点に対する第１エラーを、一組の離散的正弦変換係数に変換する第６過程と、前記一組の離散的正弦変換係数の各々を量子化された一組の変換係数に変換する第７過程と、前記量子化された一組の変換係数を再構成された一組の第１エラーに変換する第８過程と、前記ラインセグメントの各々に対するセグメントデータ、サンプル点情報及び一組の第１エラーに基づいて、再構成された輪郭セグメントを求める第９過程と、前記再構成された輪郭セグメントとそれに対応する輪郭セグメントとの間の不一致の画素数である第２エラーを計算する第１０過程と、予め定めた閾値と前記第２エラーとを比較する第１１過程と、前記第２エラーが前記予め定めた閾値以下である場合、前記輪郭セグメントのセグメントデータと量子化された一組の変換係数を符号化するか、あるいは前記第２エラーが前記予め定めた閾値以上である場合、前記輪郭セグメント上に付加頂点を加えることによって、前記輪郭セグメントを新たに分割された輪郭セグメントに分割すると共に、新たに分割された輪郭セグメントの各々に対応するラインセグメントに対して前記第３過程乃至第１２過程を繰り返す第１２過程と、前記第１過程で特定された頂点により形成された全ラインセグメントに対して、前記第１過程乃至前記第１２過程を繰り返す第１３過程とを含むことを特徴とする輪郭近似方法にある。
【０００９】
【発明の実施の形態】
以下、本発明の輪郭近似法について図面を参照して詳細に説明する。
図１には、ビデオ信号で表わされるオブジェクトの輪郭映像を表すための、本発明による輪郭近似装置のブロック図を示してある。
【００１０】
オブジェクトの輪郭を表す輪郭映像データは多角形近似ブロック１００、第１及び第２エラー検知ブロック１２０、１５０及び曲率計算ブロック１６０へ入力される。多角形近似ブロック１００では、輪郭映像が多角形近似技法により近似化される。輪郭映像の多角形近似は、輪郭映像に複数のラインセグメントを当てはめる通常の近似アルゴリズムを用いて行われる。
【００１１】
図２のａ乃至ｃには、多角形近似技法による輪郭映像１０に対すセグメンテーション過程の一例を説明するための説明図を示してある。
【００１２】
最初に、２つの開始点が選択される。輪郭映像が開ループ形である場合には、２つの終点、例えば、図２ａに示したようなＡ及びＢが開始点として選択される。一方、輪郭映像が閉ループ形(closed loop) である場合には、輪郭上で最も遠く離れている２つの点が開始点として選択される。次で、ラインセグメントＡＢから最も遠く離れている輪郭上の点が特定される。最も遠い点、例えば、ＣとラインセグメントＡＢとの間の距離ＤMAX が予め定めた閾値より大きい場合には、点Ｃが新しい頂点になる。この処理手順は図２ｃに示したように、各セグメントからの距離ＤMAX が予め定めた閾値ＴＨ１より小さくなるまで繰り返される。
【００１３】
与えられた輪郭の頂点の個数は、予め定めた閾値ＴＨ１に応じて変化する。図２ｃから分かるように、予め定める閾値を符号効率を犠牲にして小さな値に設定すれば、ラインセグメントにより表現される輪郭映像がより一層正確になる。
【００１４】
図１を再び参照するに、図２ｃに示したような、輪郭映像１０の特定した頂点、例えば、Ａ，Ｂ，Ｃ，Ｄ，及びＥの位置を表す頂点情報は、多角形近似ブロック１００からバッファ１１０へ供給される。
【００１５】
バッファ１１０は、多角形近似ブロック１００から頂点情報を受取ると共に、この情報を頂点データとして格納する。多角形近似ブロック１００にて特定された全ての頂点に対する頂点情報がバッファ１１０に格納された後、本発明による輪郭近似化が、例えば、プロセスコントローラ（図示せず）により図２ｃに示したセグメントＡＤから始まる。即ち、プロセスコントローラからの開始信号に応答して、バッファ１１０は、例えば、ラインセグメントＡＤの２つの頂点の位置を表すセグメントデータをサンプリング回路１１５へ供給する。
【００１６】
このサンプリング回路１１５は、各ラインセグメントに対して予め定めた個数（例えば、４つ）のサンプル点を特定するが、ここでサンプル点はラインセグメントを同一の長さのサブセグメントに分割し、サンプリング回路１１５は特定したサンプル点の位置を表すサンプル点情報をセグメントデータと共にラインＬ１１を経て、第１エラー検知ブロック１２０及び輪郭再構成ブロック１４５へ供給する。
【００１７】
サンプリング回路１１５からのセグメントデータ、サンプル点情報及びラインＬ１０上の輪郭映像データに基づいて、第１エラー検知ブロック１２０は、ラインセグメント上の頂点及びサンプル点の各々に対する第１エラーを計算する。ここで、「第１エラー」とは、２つの頂点を結ぶラインセグメントと、これら２つの頂点の間の輪郭セグメントとの間の距離を表す。
【００１８】
図３のａ及びｂには、ラインセグメントとそれに対応する輪郭セグメントとの間の第１エラーを例示的に図解した図を示してある。図３ａはラインセグメントＡＤとそれに対応する輪郭セグメントとの間の第１エラーを図解したものであり、図３ｂには、ラインセグメントＤＣとそれに対応する輪郭セグメントとの間の第１エラーを示してある。エラーｄ１乃至ｄ４、またはエラーｄ１′乃至ｄ４′の各々は、ラインセグメントＡＤ上のサンプル点ｓ１乃至ｓ４、またはラインセグメントＤＣ上のサンプル点ｓ１′乃至ｓ４′の各々から対応する輪郭セグメントまでの距離を表す。図３ａ及び図３ｂから分かるように、あらゆる頂点は輪郭線上に存在するため、それらの頂点に対する近似エラーは、全てゼロとなる。
【００１９】
第１エラー検知ブロック１２０により計算された第１エラーは、離散的正弦変換（ＤＳＴ）ブロック１２５へ供給される。このＤＳＴブロック１２５は、ラインセグメントに対する一組の第１エラーに対して一次元的なＤＳＴ演算を行って一組のＤＳＴ係数を発生する。この一組のＤＳＴ係数は量子化（Ｑ）ブロック１３０へ入力される。このＱブロック１３０は一組のＤＳＴ係数を量子化して、ラインセグメントに対応する一組の量子化されたＤＳＴ係数を、ラインＬ１２を経て逆量子化（ＩＱ）ブロック１３５及びモード選択ブロック１５５へ供給し、引き続き処理する。
【００２０】
ＩＱブロック１３５では、一組の量子化されたＤＳＴ係数が一組の再構成されたＤＳＴ係数に再度変換される。次いで、この再構成された一組のＤＳＴ係数は、逆ＤＳＴブロック１４０にて再構成された一組の第１エラーに逆変換される。しかる後に、再構成された一組の第１エラーが輪郭再構成ブロック１４５へ供給される。
【００２１】
ＩＤＳＴブロック１４０からの再構成された一組の第１エラーとサンプリング回路１１５からのセグメントデータ及びサンプル点情報とに基づいて、輪郭再構成ブロック１４５は、再構成された輪郭セグメントを生成して、それに関連する再構成輪セグメントデータを第２エラー検知ブロック１５０へ供給する。
【００２２】
第２エラー検知ブロック１５０は、輪郭再構成ブロック１４５からの再構成された輪郭セグメントとそれに対応する元の輪郭セグメント（ラインＬ１０上の輪郭映像データから提供される）との間の不一致の画素数である第２エラーを計算すると共に、ラインＬ１３に第２エラーを、ライン１４にセグメントデータ（即ち、再構成された輪郭セグメントの２つの頂点の位置データ）を各々供給する。図４のａには、ラインセグメントＡＤに対する元の輪郭セグメント１００及び例示的な再構成された輪郭セグメント２００を図解してある。この場合、第２エラーは、輪郭セグメント１００と２００により包囲される領域３００内に含まれている画素数に対応する。
【００２３】
モード選択ブロック１５５では、第２エラーが予め定めた閾値ＴＨ２と比較される。この第２エラーが予め定めた閾値ＴＨ２以下の場合に、モード選択ブロック１５５はＱブロック１３０からの量子化された一組のＤＳＴ係数及び第２エラー検知ブロック１５０からの対応する輪郭セグメントのセグメントデータを、各々ラインＬ１６及びＬ１７を経て輪郭符号化器１６５へ各々供給し、同時に第１イネーブル信号をバッファ１１０へも供給する。この際、処理すべき次のセグメントの一対の頂点（例えば、Ｄ及びＣ）に対するセグメントデータはバッファ１１０からサンプリング回路１１５へ供給され、上記の過程はセグメントの第２エラーが予め定めた閾値ＴＨ２以下となるまで、輪郭映像の全セグメントに対して繰り返し処理される。
【００２４】
一方、再構成された輪郭セグメントに対する第２エラーが予め定めた閾値ＴＨ２に等しいか、またはそれ以上の場合には、再構成された輪郭セグメントの各々に対応する元の輪郭セグメントを、本発明に従ってそのセグメントに付加頂点を加えることによってさらに分割する。即ち、再構成された輪郭セグメントに対する第２エラーが予め定めた閾値ＴＨ２に等しいか、またはそれ以上であれば、モード選択ブロック１５５は、その頂点に対するセグメントデータ及び第２イネーブル信号をそれぞれ曲率計算ブロック１６０及びバッファ１１０へ供給する。この曲率計算ブロック１６０では、モード選択ブロック１５５からのセグメントデータに対応する元の輪郭セグメント上の選択された画素の各々に対する曲率を計算する。
【００２５】
図５には、本発明による曲率計算ブロック１６０にて行われる曲率計算過程を図解した説明図を示してある。まず、同図に示したように、輪郭セグメント上のＮ個（例えば、６つ）の画素を目標画素（例えば、Ｔ１，Ｔ２またはＴ３）として選択する。次いで、２つの隣接する一対の目標画素（例えば、Ｔ１及びＴ２）を通る直線を引く。所定の目的画素を通る２つの直線が成す角度変化量θをその目標画素の曲率として特定する。その後、曲率計算ブロック１６０は、各目標画素に対する位置及び曲率度を表す目標画素情報を付加頂点選択ブロック１７０へ供給する。
【００２６】
この付加頂点選択ブロック１７０は、曲率計算ブロック１６０からの目標画素に対する曲率度を計算し、最も大きい曲率度を有する目標画素（例えば、図４のａに示されているＦ）を付加頂点として選択すると共に、その付加頂点の位置を表す付加頂点の情報をバッファ１１０へ供給する。この付加頂点の情報はバッファ１１０に頂点データとして格納される。従って、第２エラー値が大きい複雑な輪郭セグメント（例えば、図４のａに示した輪郭セグメント１００）は、図４のｂ及びｃに示したような多少簡素化した２つの輪郭セグメントに分割されるが、この輪郭セグメントは、２つの頂点（例えば、Ａ及びＤ）の間に付加頂点Ｆを加えることによって、ＤＳＴによってより一層正確に近似化することができる。
【００２７】
その後、第２イネーブル信号に応答して、バッファ１１０が頂点Ａ及びＦに対するセグメントデータをサンプリング回路１１５へ供給し、前述した輪郭近似過程がセグメントＡＦに対して繰り返し行われる。
【００２８】
一方、輪郭符号化器１６５においては、ラインＬ１６上の量子化された各組のＤＳＴ係数を、例えば、ＪＰＥＧ (Joint Photographic Experts Group) の２進算術コードを用いて符号化すると共に、モード選択ブロック１５５からのラインＬ１７上のセグメントデータを、頂点間の相関性が少ないため、例えば、圧縮のない固定長さの符号を用いて符号化する。しかる後、符号化した量子化ＤＳＴ係数とセグメントデータとからなる符号化ディジタル信号が、受信機への伝送のために送信機（図示せず）へ伝送される。
【００２９】
上記において、本発明の好適な実施例について説明したが、本発明は請求範囲を逸脱することなく、種々の変更を加え得ること勿論である。
【００３０】
【発明の効果】
従って、本発明によれば、オブジェクトの輪郭を表す際、付加頂点を加えることによってより近似化された輪郭の正確度を増大させることができる。
【図面の簡単な説明】
【図１】輪郭映像を表すための本発明の輪郭近似装置の一実施例を示すブロック図である。
【図２】ａ，ｂ及びｃからなり、ａはオブジェクト映像の多角形近似過程を例示的に説明するための説明図で、過程の初めの部分である開始点Ａ，Ｂが選択されるところを示したものであり、ｂはオブジェクト映像の多角形近似過程を例示的に説明するための説明図で、開始点Ａ，Ｂから新しい頂点が決定されたところを示したものであり、Ｃはオブジェクト映像の多角形近似過程を例示的に説明するための説明図で、頂点Ａ，Ｂ，Ｃから新しい頂点Ｄ，Ｅが決定されるところを示したものである。
【図３】ａ及びｂからなり、ａは２つの頂点Ａ，Ｄを結ぶラインセグメントＡＤと、それに対応する輪郭映像との間のエラーを例示的に説明する説明図であり、ｂは２つの頂点Ｃ，Ｄを結ぶラインセグメントＣＤとそれに対応する輪郭映像との間のエラーを例示的に説明する説明図である。
【図４】ａ，ｂ及びｃからなり、ａは元の輪郭セグメント１００において付加頂点が加えられ規定される再構成された輪郭セグメント２００を例示的に示した図であり、ｂ及びｃは輪郭セグメント１００をラインセグメントＡＦ，ＦＤによって多少簡素化した形態を示した図である。
【図５】本発明による曲率計算法を説明するための図である。
【符号の説明】
１００  多角形近似ブロック
１１０  バッファ
１１５  サンプリング回路
１２０  第１エラー検知ブロック
１２５  離散的正弦変換（ＤＳＴ）ブロック
１３０  量子化（Ｑ）ブロック
１３５  逆量子化（ＩＱ）ブロック
１４０  逆離散的正弦変換（ＩＤＳＴ）ブロック
１４５  輪郭再構成ブロック
１５０  第２エラー検知ブロック
１５５  モード選択ブロック
１６０  曲率計算ブロック
１６５  輪郭符号化器
１７０  付加頂点選択ブロック
【図１】
0003759980.tif 000002
【図２】
0003759980.tif 000003
【図３】
0003759980.tif 000004
【図４】
0003759980.tif 000005
【図５】
0003759980.tif 000006