(57)【特許請求の範囲】
【請求項１】
輪郭線画素よりなる物体の輪郭線を符号化する輪郭線符号化装置であって、
第１制御信号に応じて、前記輪郭線を多角近似化して当該輪郭線上に複数の頂点を特定した後、一対の隣接する前記頂点を直線的に結んだ線分と、当該一対の隣接する前記頂点の前記輪郭線の部分として与えられる輪郭線分との間の最大垂直距離Ｄmaxが予め定められた閾値より小さくなるまで他の輪郭線画素を頂点として選択し続け、選択された頂点を主頂点として決定する多角近似化手段と、
前記各主頂点の位置情報を符号化して、符号化輪郭線データを生成する第１符号化手段と、
第２制御信号に応じて、前記輪郭線画素のうちの何れか１つを副頂点として特定した後、前記特定した副頂点を中心とする所定範囲の探索領域の境界画素における前記輪郭線と一致する画素を次の副頂点として決定し、前記一致する画素が複数個存在する場合は予め設定された優先順位に従って選択された画素を副頂点として決定し、かつ新たに決定された副頂点について更に次の副頂点を決定する処理を繰り返して副頂点を順次決定する副頂点決定手段と、
前記各副頂点の位置情報を符号化して、符号化輪郭線データを生成する第２符号化手段と、
前記最大垂直距離Ｄmaxと閾値ＴＨとを比較して、前記Ｄmaxが前記ＴＨより大きい場合には第１制御信号を生成し、前記Ｄmaxが前記ＴＨ以下である場合には第２制御信号を生成する比較手段と、
を含むことを特徴とする輪郭線符号化装置。
【請求項２】
前記副頂点決定手段が、
前記第１副頂点の位置情報及び前記次の副頂点の方向インデックスを、前記第２符号化手段に供給する位置情報供給手段をさらに備えることを特徴とする請求項１に記載の輪郭線符号化装置。
【請求項３】
前記第２符号化手段が、
決定された順番が隣り合う一対の副頂点における方向インデックスの差分値を計算する差分値計算手段と、
前記第１副頂点の位置、前記第１副頂点の方向インデックス、及び前記差分値を符号化して、前記符号化輪郭線データを生成する符号化手段とを備えることを特徴とする請求項２に記載の輪郭線符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、映像信号で表現された物体の輪郭線を符号化する輪郭線符号化装置に関し、特に、輪郭線を符号化し得る輪郭線符号化装置に関する。
【０００２】
【従来の技術】
テレビ電話、電子会議及び高精細度テレビジョンシステムのようなディジタルテレビジョンシステムにおいて、映像フレーム信号のビデオライン信号が「画素値」と呼ばれる一連のディジタルデータよりなっているため、各映像フレーム信号を定義するには大量のディジタルデータが必要となる。しかしながら、従来の伝送チャネル上の利用可能な周波数帯域幅は制限されているため、特に、テレビ電話及び電子会議のシステムのような低ビットレートの映像信号符号化器の場合、そのような伝送チャネルを通じて多量のディジタルデータを伝送するためには、多様なデータ圧縮技法を用いて伝送すべきデータの量を圧縮するか減らす必要がある。
【０００３】
低ビットレートの符号化システムに於いて、映像信号の符号化方法のうちの１つに、いわゆる、物体指向分析−合成符号化方法がある。ここで、入力映像は複数の物体に分けられ、各物体の動き、輪郭線、画素データを定義するための３つの組よりなるパラメータが異なる符号化チャネルを通じて処理される。
【０００４】
物体の輪郭線の処理の際、物体の形状を分析及び合成するには、輪郭線情報が重要である。この輪郭線情報を表す通常の符号化方法に、チェーン符号化方法（ｃｈａｉｎ  ｃｏｄｉｎｇ  ｍｅｔｈｏｄ）がある。しかし、このチェーン符号化方法は、たとえ輪郭線情報を損失なく符号化しても、輪郭線情報を表現のために大量のデータビットが必要となるという短所を有する。
【０００５】
これに関連して、多角近似化、Ｂ−スプライン近似化及び多角近似化技法に組み合わせられたＤＳＴ（離散的サイン変換）のような輪郭線情報符号化法が幾つか提案されてきた。このような近似化方法において、輪郭線は該輪郭線上で一対の隣接頂点間を結んだ線分（例えば、複数の直線または曲線）によって近似され、各頂点は、例えば、いわゆる局部適応的オクタントベース頂点符号化技法（locally-adaptive octant-based vertex coding technique）に基づいて符号化される（例えば、International Organization for Standardization, Coding of Moving Pictures and Audio Information, ISO/IEC JTCI/SC29/WG11, Shape Coding AHG, July30, 1996の、K.O'Connell,P.Gerken 及びJ.H.Kimの論文、「Revised Description of S4a：Geometrical Representation Method」参照）。
【０００６】
図１を参照すれば、オクタントベース頂点符号化技法を用いて、映像信号で表現された物体の輪郭線上の各頂点を符号化する、従来の輪郭線符号化装置の概略的なブロック図が示されている。
【０００７】
図中で、２進マスクは輪郭線取出し部１０に入力される。この２進マスクにおいて、各画素は、該画素が物体領域または背景領域のうちの何れかの１つに位置することによって、２進値（即ち、０または１）のうちの１つに表現される。
【０００８】
輪郭線取出し部１０は、２進マスクから物体の輪郭線映像を取出し、該輪郭線映像を頂点選択部２０に供給する。この輪郭線は、各々が物体の境界線上に位置する物体画素である複数の輪郭線画素からなる。
【０００９】
頂点選択部２０は従来の反復的近似度改選法（iterated refinement technique)（例えば、多角近似化技法）を用いて複数の頂点を選択する。最初、最大距離だけ隔たっている一対の輪郭線画素を開始頂点として決定し、一対の隣接頂点を結ぶ線分から該一対の隣接頂点によって定義された輪郭線分までの最大垂直距離が予め定められた閾値Ｄmaxより大きくなくなるまで、他の輪郭線画素を１つずつ他の頂点として選択し続ける。ここで、一対の隣接頂点は輪郭線に沿って互いに隣接している。従って、そのような多角近似化技法の場合、近似度の正確さは予め決められた閾値Ｄmaxによって左右される。
【００１０】
頂点符号化部３０は、頂点選択部２０からの各頂点を例えば、オクタントベース頂点符号化方法を用いて符号化する。
【００１１】
このオクタントベース頂点符号化において、隣接する頂点の各対間の変位Ｒに対するｘ成分Ｘ及びｙ成分Ｙ、それらの大きさｘ＿ｍａｇ及びｙ＿ｍａｇが計算される。その後、全ての成分Ｘ及びＹの大きさｘ＿ｍａｇ及びｙ＿ｍａｇのうち、最大の大きさに対応する２つの頂点が輪郭線の開始頂点及び終了頂点として選択される。その後、図２に示したように、Ｎ個（例えば、８個）の頂点が開始頂点から終了頂点の方へ輪郭線を沿って順番に指標（インデックス）が付けられる。図２において、一対の頂点Ｖ1及びＶ8に対応するｘ成分の大きさｘ＿ｍａｇが、頂点Ｖ1〜Ｖ8で計算された８対の両成分Ｘ及びＹの大きさｘ＿ｍａｇ及びｙ＿ｍａｇのうちの最大値として求められる。
【００１２】
開始頂点及び終了頂点を決定した後、変位Ｒiの両大きさｘ＿ｍａｇ及びｙ＿ｍａｇのうち各最大値、ｘ＿ｍａｘ−ｍａｇ及びｙ＿ｍａｘ−ｍａｇが各々輪郭線に対するｘ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ及びｙ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅとして決定される。ここで、変位ＲiはＶi+1−Ｖi（ｉ＝１、２、…、Ｎ−１）であり、Ｖiは頂点Ｖiに対応する位置ベクトルである。その後、開始頂点Ｖ1のｘ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ、ｙ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ及び絶対位置が符号化され、残余の頂点（即ち、Ｖi+1、ｉ＝１、２、…、Ｎ−１の時）の各々が前頂点Ｖiからの変位Ｒiに基づいて符号化される。
【００１３】
詳述すると、図３に示したように、頂点Ｖi+1が属するオクタントが変位Ｒiのｘ成分Ｒi（ｘ）及びｙ成分Ｒi（ｙ）に基づいて、オクタント０〜７から決定され、原点を基準とする８個の近傍の点（図中、黒点に表示）が８個のオクタントの開始点を表す。
【００１４】
各頂点Ｖi+1のオクタントを決定した後、各オクタントに付けられたインデックスが通常の微分チェーン符号化技法によって符号化され、前頂点Ｖiに対する頂点Ｖi+1の相対的位置を表す両変位成分の大きさＲｉ（ｘ）及びＲｉ（ｙ）は、各々ｘ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ及びｙ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅに基づいて決定されたビットを用いて符号化される。
【００１５】
オクタントベース頂点符号化技法の他の例として、オクタントインデックス及びＲiは、いわゆる、シンタクス適応的算術符号化（syntax-adaptive arithmetic coding；SAAC)を用いて選択的に符号化される。このＳＡＡＣにおいて可能なシンボルの数はダイナミックレンジの最大値（即ち、ｍａｘ（ｘ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ、ｙ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ））に応じて変化する。このオクタントベース頂点符号化技法の詳細は上記したK.O'Connellらの論文を参照されたい。
【００１６】
前述したような頂点の順序付け過程において、開始頂点を除いた全頂点が自分が属するオクタント、大きさＲｉ（ｘ）及びＲｉ（ｙ）によって表現され、また、各大きさの符号化に必要なビット数が両ダイナミックレンジｘ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ及びｙ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅに直接依存しているので、各頂点を表すデータの量をオクタントベース頂点符号化技法を用いて、効果的に減らし得る。
【００１７】
しかし、そのような従来の輪郭線符号化技法においては、とりわけ、両大きさｘ＿ｍａｇ及びｙ＿ｍａｇが各々ｘ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅ及びｙ＿ｄｙｎａｍｉｃ＿ｒａｎｇｅより相当に小さいか、または近接頂点が大量に存在する場合、更に、閾値Ｄｍａｘが小さい場合に、頂点表現のために大量の不必要なデータを依然として要するという不都合がある。
【００１８】
【発明が解決しようとする課題】
従って、本発明の主な目的は、輪郭線を効果的に符号化する、改善された輪郭線符号化装置を提供することにある。
【００１９】
【課題を解決するための手段】
上記の目的を達成するために、本発明によれば、輪郭線画素よりなる物体の輪郭線を符号化する輪郭線符号化装置であって、
第１制御信号に応じて、複数の主頂点を用いて前記輪郭線を多角近似化する多角近似化手段であって、前記輪郭線が、各々両端に２つの主頂点を有し、前記２つの主頂点間を結ぶ線分によって表現される複数の第１輪郭線分に分けられ、前記各第１輪郭線分と前記線分との間の最大の垂直距離が閾値Ｄmaxより小さい、前記多角近似化手段と、
前記各主頂点の位置情報を符号化して、符号化輪郭線データとして発生する第１符号化手段と、
第２制御信号に応じて、各々が既に決定された副頂点から予め定められた位置のうちの何れか１つに１つまたは複数の画素だけ隔たって位置する、複数の副頂点を前記輪郭線上に順番に決定すると共に、前記副頂点の位置情報を発生する副頂点決定手段と、
前記各副頂点の位置情報を符号化して、符号化輪郭線情報として発生する第２符号化手段と、
前記Ｄmaxと前記ＴＨとを比較して、前記Ｄmaxが前記ＴＨより大きい場合は、第１制御信号を発生し、前記Ｄmaxが前記ＴＨ以下である場合には第２制御信号を発生する比較手段とを含むことを特徴とする輪郭線符号化装置が提供される。
【００２０】
【発明の実施の形態】
以下、本発明の好適実施例について図面を参照しながらより詳しく説明する。
【００２１】
図４を参照すると、本発明の好適実施例による輪郭線符号化装置１００の概略的なブロック図が示されている。
【００２２】
物体の輪郭線映像は、２進マスクの形態で輪郭線取出し部４０に入力される。この輪郭線取出し部４０は、物体の境界に位置する輪郭線画素よりなる輪郭線を取出して、第１頂点選択部５０及び等距離位置頂点符号化部９０に各々供給する。
【００２３】
第１頂点選択部５０は従来の多角近似化技法を用いて、輪郭線上で複数の主頂点を選択し、各頂点位置情報を表す主頂点データをラインＬ２０を通じて、主頂点符号化部８０に供給する。輪郭線上に主頂点を決定する際、最大距離だけ隔たっている一対の輪郭線画素が開始頂点として決定される。その後、対になった各隣接頂点を結ぶ線分から頂点の対によって定義された輪郭線分までの最大垂直距離が、予め定められた閾値Ｄmaxより大きくなくなるまで、他の輪郭線画素を１つずつ他の頂点として選択し続ける。このようにして決定された各頂点は、主頂点として定められる。
【００２４】
また、第１頂点選択部５０は主頂点を決定した後、輪郭線に沿って隣接する２つの主頂点を結ぶ線分からそれに対応する輪郭線分までの最大垂直距離を計算して、ラインＬ１０を通じてエラー検出部６０に供給する。
【００２５】
このエラー検出部６０は第１頂点選択部５０からの各線分に対する最大距離を受け取ると共に、そのうち最大値を選択してこの値を近似化エラーとして比較部７０に出力する。
【００２６】
比較部７０は、近似化エラーと予め定められた閾値ＴＨ１とを比較して、近似化エラーが閾値ＴＨ１より大きい場合は第１選択信号を、そうでない場合には第２選択信号を選択部９５に各々供給する。
【００２７】
一方、主頂点符号化部８０は例えば、図１を参照して説明した従来のオクタントベース頂点符号化技法を用いて、第１頂点選択部５０からの主頂点データを符号化して、符号化主頂点データは選択部９５に供給する。
【００２８】
等距離位置頂点符号化部９０は、輪郭線取出し部４０から受け取った輪郭線に応じて、輪郭線上に複数の副頂点を決定すると共に、各副頂点を符号化して符号化副頂点データを選択部９５に供給する。
【００２９】
図６には、等距離位置頂点符号化部９０の詳細なブロック図が示されている。この等距離位置頂点符号化部９０は第２頂点選択部１１０及び差分チェーン符号化部１２０から構成される。
【００３０】
第２頂点選択部１１０は、輪郭線取出し部４０から受け取った輪郭線上に複数の副頂点を決定する。ここで、各副頂点は、隣接する副頂点から予め定められた位置だけ隔たっている頂点の組のうちの何れか１つに位置する輪郭線画素である。輪郭線上に各副頂点の決定の際、輪郭線の最長の直線が検出され、該直線上の両端に位置する輪郭線画素のうちの何れか１つが第１副頂点として決定される。しかる後、第１副頂点を求めるための探索ウィンドウが形成される。この探索ウィンドウは中心に既に決定された副頂点を有し、（２Ｍ＋１）×（２Ｎ＋１）個の画素からなる大きさに形成される。ここで、Ｍ及びＮは各々多角近似化における閾値Ｄmaxに基づいて決定された値より大きい正の整数である。その後、探索ウィンドウ上のある境界画素が、まだ副頂点として決定されていない輪郭線画素と一致するか否かを判断する。一致する輪郭線画素が１つあれば、該輪郭線画素は新たな副頂点として選択される。しかし、境界画素の位置に一致する輪郭線画素が１つまたは複数個あれば、その輪郭線画素のうちの何れか１つが、各境界位置に割り当てられた優先順位によって追加の副頂点として選択される。
【００３１】
図７（Ａ）に示したように、もし、太線で取り囲まれた画素ＲＶが輪郭線上の第２副頂点である場合、５×５画素からなる探索ウィンドウ６５上の１６個の境界画素（即ち、斜線部分）各々が輪郭線画素であるか否かを判断する。図中、境界画素の位置に付けられた例示的な方向インデックス１〜１５は、頂点選択の優先順位を表す。例えば、境界画素の位置（例えば、インデックス２〜５）で１つまたは複数の輪郭線画素が存在する場合、インデックス２の輪郭線画素が次の副頂点として決定される。上述した副頂点決定のプロセスは、初期決定された各頂点（即ち、第１及び第２副頂点）が２つの後続の探索ウィンドウ内で各々順次検出されるまで、新たに選択された副頂点を基準として繰り返して行われる。
【００３２】
図７（Ｂ）には、５×５画素からなる探索ウィンドウによって決定された副頂点ＳＶ１〜ＳＶ４を含んでいる、例示的な輪郭線６７の一部分が示されている。輪郭線上に副頂点を決定した後、第１副頂点の位置情報はラインＬ３２を通じて、残余副頂点の方向インデックスはラインＬ３０を通じて差分チェーン符号化部１２０に各々供給される。この差分チェーン符号化部１２０は図８に示したように、量子化部２２０と、量子化パラメータ（ＱＰ）決定部２２２と、差分決定部２３０と、差分値符号化部２４０とから構成されている。
【００３３】
ＱＰ決定部２２２は、図４及び図５中の伝送バッファ９６からラインＬ４０を通じて入力されたバッファの充満度または占有度をモニターすると共に、従来の量子化パラメータ決定方法と類似な方法にてＱＰを決定して、量子化部２２０に供給する。
【００３４】
量子化部２２０はＱＰ決定部２２２からのＱＰに基づいて、第２頂点選択部１１０からラインＬ３０を通じて受け取った方向インデックスを量子化する。
【００３５】
図９（Ａ）は５×５画素からなる探索ウィンドウの場合に、図９（Ｂ）は７×７画素からなる探索ウィンドウの場合に、方向インデックスの量子化過程を説明するための模式図が各々示されている。各図中で、斜線部分は代表的な境界画素を表し、各境界画素は各探索ウィンドウ上の各コーナ及び予め定められた縁部分に位置する。量子化のプロセスの際、点で表示された非代表的な境界画素の位置に存在する各副頂点の方向インデックス（即ち、ｂ及びｆ）は、隣接する代表的な境界画素の方向インデックス（即ち、ｃ及びｇ）に各々表示される。しかる後、代表的な境界画素の方向インデックスは、代表的なインデックスを割り当てるため再びインデックスが付けされる。図９（Ａ）及び図９（Ｂ）に示したように、このような方法にて各方向インデックスを量子化することによって、全体で１６個及び全体で２４個の方向インデックスは、各々、８個の代表的な方向インデックスに減らされる。
【００３６】
代表的な境界画素の個数または代表的なインデックスの個数は、ＱＰによって変更される。即ち、ＱＰがバッファの充満度が一杯、または占有度が高いという指示する場合、代表的な境界画素の個数は減らすか、または増加することになる。本発明の好適実施例において、代表的な境界画素の個数の上限線はその探索ウィンドウ内の全ての境界画素の個数によって設定され、下限線は８に決まっている。そのような場合、図９に示したように、任意の副頂点が探索ウィンドウの大きさに係わらず、該当探索ウィンドウの４つのコーナ及び４つの縁部上の中央に位置する、８つの代表的な境界画素のうちの何れか１つによって表示される。
【００３７】
差分決定部２３０は量子化部２２０から受け取った代表的なインデックスに基づいて、差分インデックスを決定して差分値符号化部２４０に供給する。この差分インデックスは、２つの連続する代表的なインデックスの大きさの間の差分を表す。
【００３８】
差分値符号化部２４０は従来の可変長符号化法またはシンタクスベースの算術符号化法を用いて、ラインＬ３２を通じて受け取った第１副頂点の位置情報と差分決定部２３０からの差分インデックスとを符号化して、符号化副頂点データを選択部９５または第２選択部９５Ｂに供給する。
【００３９】
選択部９５は、第１選択信号に応じて符号化主頂点データを選択し、第２選択信号に応じて符号化副頂点データを選択して、該選択データを符号化輪郭線データとして伝送バッファ９６に送り出す。この符号化輪郭線データは、伝送バッファ９６を通じてその伝送のため伝送器（図示せず）に送られる。
【００４０】
図５を参照すると、本発明の他の好適実施例による輪郭線符号化装置１００の概略的なブロック図が示されている。
【００４１】
好適実施例による近似化エラーの変わりに、比較部７５は閾値Ｄmaxと閾値ＴＨ１とを比較する。もし、ＤmaxがＴＨ１より大きい場合は第１選択信号を、そうでない場合には第２選択信号をラインＬ２５上に出力する。これらの選択信号に応じて、第１選択部９５Ａ及び第２選択部９５Ｂはその動作を行う。詳述すると、第１選択部９５Ａは、輪郭線取出し部４０から取り出された輪郭線を、第１選択信号に応じて第１頂点選択部５０に供給し、第２選択信号に応じて等距離位置頂点符号化部９０に供給する。一方、第２選択部９５Ｂの選択動作は、図４中の選択部９５と同じく行われる。図４及び図５において、同一の参照符号で表示した各要部は同一の動作を行い、その説明は省略する。
【００４２】
上記において、本発明の好適な実施の形態について説明したが、本発明の請求範囲を逸脱することなく、当業者は種々の改変をなし得るであろう。
【００４３】
【発明の効果】
従って、本発明によれば、オクタントベースの適応的符号化法及び等距離位置頂点符号化法に基づいて、複数の画素よりなる探索ウィンドウを通じ輪郭線画素を効果的に符号化して、伝送すべき映像データをより一層減らすことができる。
【図面の簡単な説明】
【図１】従来の輪郭線符号化装置の概略的なブロック図。
【図２】輪郭線を沿って各頂点に優先順位を順に割り当てる過程を説明する模式図。
【図３】オクタントベース頂点符号化方法を説明する模式図。
【図４】本発明の一実施例による輪郭線符号化装置の概略的なブロック図。
【図５】本発明の他の好適実施例による輪郭線符号化装置の概略的なブロック図。
【図６】図４中の等距離位置頂点符号化部の詳細なブロック図。
【図７】Ａ及びＢからなり、Ａ及びＢは、各々、等距離位置頂点符号化部による副頂点の選択過程を説明するための模式図。
【図８】図６の差分チェーン符号化部の詳細なブロック図。
【図９】Ａ及びＢからなり、Ａ及びＢは、各々、図８の量子化部による量子化過程を説明するための模式図。
【符号の説明】
１０  輪郭線取出し部
２０  頂点選択部
３０  頂点符号化部
４０  輪郭線取出し部
５０  第１頂点選択部
６０  エラー検出部
７０  比較部
８０  主頂点符号化部
９０  等距離位置頂点符号化部
９５  選択部
９５Ａ  第１選択部
９５Ｂ  第２選択部
９６  伝送バッファ
１１０  第２頂点選択部
１２０  差分チェーン符号化部
２２０  量子化部
２２２  量子化パラメータ（ＱＰ）決定部
２３０  差分決定部
２４０  差分値符号化部
【図１】
0004136031.tif 000002
【図２】
0004136031.tif 000003
【図３】
0004136031.tif 000004
【図４】
0004136031.tif 000005
【図５】
0004136031.tif 000006
【図６】
0004136031.tif 000007
【図７】
0004136031.tif 000008
【図８】
0004136031.tif 000009
【図９】
0004136031.tif 000010