(57)【特許請求の範囲】
【請求項１】
複数の物体画素及び複数の背景画素よりなる映像信号において、物体の輪郭線をトレーシングする輪郭線トレーシング方法であって、
互いに隣接した背景画素が同一の背景インデックスを有するように、前記背景画素の各々をインデクシングする第１過程と、
隣接画素の中に１以上の背景画素を有する物体画素である輪郭線画素を検出する第２過程と、
同じグループの輪郭線画素は同一の背景インデックスを有する１または複数の背景画素に隣接するように、前記輪郭線画素をグループ分けして１または複数の輪郭線画素グループを生成する第３過程と、
前記輪郭線画素をグループ単位にトレーシングする第４過程とを含むことを特徴とする輪郭線トレーシング方法。
【請求項２】
ある輪郭線画素がその隣接画素の中に異なる背景インデックスを有する背景画素を含んでいる場合、その輪郭線画素は前記異なる背景インデックスに対応する各グループに含まれることを特徴とする請求項１に記載の輪郭線トレーシング方法。
【請求項３】
前記第４過程が、異なる背景インデックスを有する背景画素に隣接する前記輪郭線画素から始められことを特徴とする請求項２に記載の輪郭線トレーシング方法。
【請求項４】
上下左右に４個の第１隣接画素を有し、対角線方向に４個の第２隣接画素を有する正方形パターンの物体画素及び背景画素よりなる映像信号における物体の輪郭線をトレーシングする輪郭線トレーシング方法であって、
前記背景画素を複数の組に分ける第１過程と、
前記背景画素の各組に相異なる背景インデックスを割り当てる第２過程と、
各物体画素に対し、各々の第１隣接画素中に１または複数の背景画素が含まれるか否かをチェックする第３過程と、
前記第１隣接画素中に１または複数の背景画素が含まれている場合、その物体画素を輪郭線画素として定める第４過程と、
各輪郭線画素に対し、前記１または複数の背景画素に対応するインデックスを割り当てる第５過程と、
前記輪郭線画素をグループ分けして、同じグループの輪郭線画素は同一のインデックスを有するようにする第６過程と、
前記第１及び第２隣接画素に基づいて、前記輪郭線画素をグループ単位にトレーシングする第７過程とを含むことを特徴とする輪郭線トレーシング方法。
【請求項５】
前記第５過程において複数のインデックスが割り当てられた輪郭線画素は複数のインデックスに対応する輪郭線画素の各グループに含まれることを特徴とする請求項４に記載の輪郭線トレーシング方法。
【請求項６】
前記第７過程が、
第１インデックスを有する輪郭線画素グループを選択する第７−１過程と、
前記選択された輪郭線画素グループに属する輪郭線画素の一つを追跡画素として選択する第７−２過程と、
前記選択された画素の前記第１及び第２隣接画素の中で、前記第１インデックスを有する未追跡の隣接輪郭線画素の数をカウントし、カウント値が１以上のときは選択されている画素を追跡済み画素としてマーキングする第７−３過程と、第７−３過程でカウントされた隣接輪郭線画素の数が１より大きい場合、前記選択されている画素を分岐画素としてマークし、前記第７−３過程でカウントされた前記隣接輪郭線画素の１つを次の追跡画素として選択し、前記カウント数が１である場合は、前記第７−３過程でカウントされた前記隣接輪郭線画素を次の追跡画素として選択する第７−４過程と、
選択された次の追跡画素に対して前記第７−３過程及び前記第７−４過程を繰り返す第７−５過程とを有することを特徴とする請求項５に記載の輪郭線トレーシング方法。
【請求項７】
前記第７過程が、前記第７−５過程の後に、
前記第７−３過程でカウントされた隣接輪郭線画素の数が０である場合、隣接輪郭線画素が存在しているのであれば、該隣接輪郭線画素の中の何れか１つを次の追跡画素として選択する第７−６過程と、
選択されている輪郭線画素グループに属する全輪郭線画素の追跡が完了するまで、前記第７−５過程及び第７−６過程を繰り返す第７−７過程とを、更に有することを特徴とする請求項６に記載の輪郭線トレーシング方法。
【請求項８】
前記第７過程が、前記第７−７過程の後に
存在するのであれば、次のインデックスを有する輪郭線画素グループを選択する第７−８過程と、
前記物体の全輪郭線画素に対する追跡が完了するまで、前記第７−８過程で選択された前記輪郭線画素グループに対して、前記第７−２過程から前記第７−８過程を繰り返す第７−９過程とを、更に有することを特徴とする請求項７に記載の輪郭線トレーシング方法。
【請求項９】
前記第１インデックスと前記次のインデックスの両方を有する輪郭線画素は、前記第７−２過程で前記次のインデックスに対しても前記追跡画素として選択されることを特徴とする請求項８に記載の輪郭線トレーシング方法。
【発明の詳細な説明】
【０００１】
【０００２】
【発明の属する技術分野】
本発明は、映像信号で表現された物体の輪郭線を抽出し、トレーシング（追跡）する輪郭線トレーシング方法に関する。特に、物体の背景情報に基づいて、物体に対応する輪郭線を正確にかつ効果的にトレーシングし得る輪郭線トレーシング方法に関する。
【０００３】
【従来の技術】
テレビ電話、電子会議及び高精細度テレビジョンシステムのようなディジタル映像システムでは、映像フレーム信号の映像ライン信号が「画素値」と呼ばれる一連のディジタルデータからなっているので、各映像フレーム信号を規定するのには大量のディジタルデータが必要である。しかし、通常の伝送チャネル上の利用可能な周波数帯域幅は制限されているため、特に、テレビ電話及び電子会議システムのような低ビットレートの映像信号符号化の場合、その制限されたチャネルを通じて大量のデータを伝送するためには、多様なデータ圧縮技法を用いて伝送すべきデータの量を減らすか圧縮する必要がある。
【０００４】
低ビットレートの符号化システム用のそのような多様なデータ圧縮技法の中で、いわゆる、物体指向分析−合成符号化技法（ｏｂｊｅｃｔ−ｏｒｉｅｎｔｅｄａｎａｌｙｓｉｓ−ｓｙｎｔｈｅｓｉｓ  ｃｏｄｉｎｇ  ｔｅｃｈｎｉｑｕｅ）が最も効率的なものとして知られている。それによると、入力映像信号は複数の物体（オブジェクト）に分けられ、各物体の動き、輪郭線、画素データを定める３組のパラメータが相異なる符号化チャネルを通じて処理される。
【０００５】
物体の輪郭線を処理する際、物体の形状を分析し合成するためには輪郭線データが非常に重要である。この輪郭線データは通常、輪郭線検出器によって隣接する画素値の変化を検出することによって求められる。
【０００６】
しかし、従来の輪郭線トレーシング（追跡）方法によって求められた単一の輪郭線の輪郭線データは、輪郭線データ間の相関関係を適切に考慮しない符号化法を用いて符号化されているため、特に輪郭線の形状が複雑である場合、符号化効率が低くなるという問題がある。
【０００７】
【発明が解決しようとする課題】
従って、本発明の主な目的は、物体の背景情報に基づいて、物体の輪郭線を正確にかつ効果的にトレーシング（追跡）して、輪郭線データストリーム中の全輪郭線画素間の相関関係を適切に利用することによって、符号化効率を向上させ得る輪郭線トレーシング方法を提供することである。
【０００８】
【課題を解決するための手段】
上記の目的を達成するために、本発明の好適実施例によれば、複数の物体画素及び複数の背景画素よりなる映像信号において、物体の輪郭線をトレーシングする輪郭線トレーシング方法であって、互いに隣接した背景画素が同一の背景インデックスを有するように、前記背景画素の各々をインデクシングする第１過程と、隣接画素の中に１以上の背景画素を有する物体画素である輪郭線画素を検出する第２過程と、同じグループの輪郭線画素は同一の背景インデックスを有する１または複数の背景画素に隣接するように、前記輪郭線画素をグループ分けして１または複数の輪郭線画素グループを生成する第３過程と、前記輪郭線画素をグループ単位にトレーシングする第４過程とを含むことを特徴とする輪郭線トレーシング方法が提供される。
【０００９】
【発明の実施の形態】
以下、本発明の好適実施例について図面を参照しながらより詳しく説明する。
【００１０】
図１には、本発明による輪郭線トレーシング装置１０の概略的なブロック図が示されている。入力映像信号は、輪郭線画素抽出ブロック１２及び背景インデクシングブロック１４の各々へ入力される。この入力映像は、１または複数の物体と背景からなり、例えば、ビットマップの形態で表現される。ここで、物体画素は例えば「１」で、背景画素は例えば「０」で各々表現される。別の例として、背景画素を「０」で表し、物体画素をある「０」でない値で表すようにしてビットマップを構成してもよい。この場合、背景画素と物体画素は、予め定められた閾値（例えば、０．５）と比較することによって容易に区別される。
【００１１】
背景インデクシングブロック１４では、互いに隣接する背景画素には同じ背景インデックスが割り当てられるように、各背景画素にインデックスが割り当てられる。図２に、２個の物体ＯＢ１及びＯＢ２を有する入力映像の例を示す。本発明によれば、両物体ＯＢ１及びＯＢ２の外側に存在する背景画素は互いに繋がっているため、それらには同じインデックスＢＫ１が割り当てられる。同様に、物体ＯＢ１の内側にある背景画素には、インデックスＢＫ２が割り当てられる。各背景画素に対するインデックスを表す背景画素情報は輪郭線画素抽出ブロック１２へ供給される。図２中で、「Ｏ」または「Ｘ」で表示された画素（例えば、２２、２４、２６、２８、３０、３１、３２、３３、３４及び３５）は輪郭線画素を表す。これらの輪郭線画素に対しては、後に図３を参照して詳しく説明する。
【００１２】
輪郭線画素抽出ブロック１２においては、入力映像と背景インデクシングブロック１４からの背景画素情報とに応じて、複数の輪郭線画素及びそれらの各々に対応するインデックスが決定され、決定された輪郭線画素のインデックス及び位置を表す輪郭線画素情報が輪郭線画素トレーシングブロック１６へ送られる。輪郭線画素の選択とそれらに対応するインデックスの決定とは、図３に示した過程に従って行われる。
【００１３】
図３に示したように、本発明の輪郭線トレーシング方法によれば、ステップＳ３２において、例えば図２の例に示した物体ＯＢ１及びＯＢ２を構成する物体画素の中の１つが走査物体画素として選択される。ステップＳ３３において、選択された物体画素が輪郭線画素であるか否かがチェックされる。本発明の好適実施例では、入力映像の画素は正方形パターンと仮定する。詳述すると、１つの画素はその上下左右に４個の第１隣接画素を有し、その対角線方向に４個の第２隣接画素を有するものとする。輪郭線画素の決定では、まず、走査物体画素の回りの４個の第１隣接画素の中に背景画素がないかどうかがチェックされる。走査物体画素が非輪郭線画素と判断された場合（即ち、４個の第１隣接画素が全て物体画素である場合）は、プロセスはステップＳ３７に進む。一方、走査物体画素が輪郭線画素と判断された場合（即ち、４個の第１隣接画素の中に１以上背景画素がある場合）は、プロセスはステップＳ３４に進む。
【００１４】
このステップＳ３４においては、走査物体画素が１つの背景のみに隣接するか否かがチェックされる。言い替えれば、ステップＳ３４にて、走査物体画素に対する４個の第１隣接画素に属する１または複数の背景画素が全て同じインデックスを有する場合、プロセスはステップＳ３５に進み、ここで、輪郭線画素に単一のインデックスが割り当てられる。例えば、図２に示した輪郭線画素２２、２８、２９、３０、３１、３２、３３、３４及び３５は、第１隣接画素内にインデックスＢＫ１の背景画素のみを有しているため、それら輪郭線画素には例えば、ＣＰ−１のインデックスが割り当てられる。輪郭線画素２４はインデックスＢＫ２の背景画素と隣接しているため、ＣＰ−２のインデックスが割り当てられる。ステップＳ３４において輪郭線画素が４個の第１隣接画素の中にインデックスの相異なる背景画素を有する場合は、それに対応した複数のインデックスが割り当てられる（多重インデックスという）。例えば図２に示した例では、輪郭線画素２６は背景インデックスＢＫ１の背景画素と背景インデックスＢＫ−２の背景画素の両方に隣接しているため、ＣＰ−１とＣＰ−２の２つのインデックスが割り当てられる。その後、ステップＳ３７において、未走査物体画素が存在するかどうかがチェックされる。未走査物体画素が存在する場合は、プロセスはステップＳ３２に戻り、全ての物体画素が走査されるまで上記した過程が繰り返して行われる。
【００１５】
図１を再度参照されたい。輪郭線画素抽出ブロック１２からの輪郭線画素情報に応じて、輪郭線画素トレーシングブロック１６は、図４及び図５に詳しく示された本発明のトレーシング方法に従って、輪郭線をトレーシングし、得られた輪郭線映像を次のプロセッサ、例えば輪郭線符号化器（図示せず）へ送る。
【００１６】
図４及び図５のフロー図を参照して、本発明による輪郭線トレーシング方法を説明する。ステップＳ４１では、図１に示した輪郭線抽出ブロック１２で決定された輪郭線画素のうちの何れか１つが「追跡画素」として選択される。ステップＳ４２では、選択された画素のインデックスのうちの何れか１つが選択される（追跡インデックス）。例えば、図２に示された輪郭線画素２２が選択されれば、そのインデックスＣＰ−１が追跡インデックスとして選択され、多重インデックスの輪郭線画素２６が選択された場合は、そのインデックスＣＰ−１とＣＰ−２のうちの何れか１つが追跡インデックスとして選択される。
【００１７】
続いてステップＳ４３では、追跡画素の追跡インデックスと同一のインデックスを有する未追跡の隣接輪郭線画素の個数がカウントされる。ここで、隣接輪郭線画素は選択されている画素を取り囲む第１及び第２隣接画素（８個）に含まれる輪郭線画素を表す。また、未追跡とは対象としている追跡インデックスに関してまだ追跡画素として選択されていないということを表す。選択された追跡インデックスと同じインデックスを有する未追跡の隣接輪郭線画素の個数Ｎが１より大きい場合はステップＳ４４に進み、ここで、選択されている画素（追跡画素）は分岐画素としてマークされ、その後プロセスはステップＳ４５へ進む。カウントされた隣接輪郭線画素の個数Ｎが１の場合は直ちにステップＳ４５に進み、個数Ｎが０の場合はステップＳ４８に進む。
【００１８】
ステップＳ４５においては、選択されている画素が「追跡済み画素」としてマークされる。ステップＳ４６では、追跡済み画素の位置を表す追跡済み画素データが、前述した例えば輪郭線符号化器（図示せず）へ伝送される。ここで、追跡済み画素データは、図１に示した輪郭線画素トレーシングブロック１６から生成される輪郭線画像データを構成する。その後、ステップＳ４７において、Ｎ＞１の場合はステップＳ４３でカウントされた隣接輪郭線画素のうちの何れか１つを、Ｎ＝１の場合はステップＳ４３でカウントされた唯一つの隣接輪郭線画素を次のトレーシング過程のための「候補画素（次の追跡画素）」として選択し、ステップＳ４３へ進む。この候補画素として選択された画素の追跡インデックスは、前の追跡済み画素のインデックスと同じである。上述したように、追跡済み画素は、所定の条件を満たす隣接輪郭線画素の数をカウントするステップＳ４３及び次のトレーシングのための候補画素を選択するステップＳ４７において除外されることに注意されたい。
【００１９】
例として、図２に示された輪郭線画素２２がまず選択されて上記の輪郭線トレーシング過程が始まるとする。この輪郭線画素２２はステップＳ４４で分岐画素としてマーキングされる。ステップＳ４７にて、輪郭線画素３０が次のトレーシングのための候補画素として選択される場合、輪郭線トレーシングは物体ＯＢ１の下部周りに沿って反時計方向へ行われ、輪郭線画素２８はステップＳ４４にて分岐画素としてマーキングされる。更に、ステップＳ４７において、分岐画素２８に隣接する２つの輪郭線画素３１及び３４のうちで輪郭線画素３４が選択されれば、物体ＯＢ１の外側周りの上部に沿って輪郭線トレーシング過程が続けられ、物体ＯＢ１の外側周りの最後の輪郭線画素３５に到達する。このとき、輪郭線画素３１〜３３はまだトレーシングされていない。
【００２０】
図４〜図５を再度参照されたい。ステップＳ４３にて最後の輪郭線画素３５と同じインデックスを有する未追跡の隣接輪郭線画素の数がカウントされるが、カウントされる隣接輪郭線画素の数Ｎは０であるため、プロセスはステップＳ４８へ進む。ステップＳ４８においては、追跡済み画素の中に分岐画素が存在するか否かがチェックされる。図２に示した例の場合には、ステップＳ４８にて、２つの輪郭線画素２２及び２８が分岐画素として検出され、ステップＳ４９にて、それらのうちの１つが選択される。ステップＳ５０では、ステップＳ４９で選択された分岐画素の隣接輪郭線画素の中にステップＳ４２で選択された追跡インデックスを有し且つ未追跡の輪郭線画素があるか否かがチェックされる。もし、ステップＳ５０で条件を満たす輪郭線画素の数Ｎが２以上である場合は、ステップＳ４７にてそのような画素の中の何れか１つが候補画素として新たに選択され、プロセスは再びステップＳ４３へ進む。もし、ステップＳ５０にてＮ＝１の場合は、ステップＳ５２にてＳ５０でチェックした画素がそれ以上分岐画素として考慮されないようにその画素から分岐画素としてのマーキングを外し、ステップＳ４７に進んで、ステップＳ５０にてカウントされた輪郭線画素が次のトレーシングのための新たな候補画素として選択される。ステップＳ５０にてＮ＝０の場合は、ステップＳ４９で選択された分岐画素はステップＳ５１で分岐画素のマーキングを外され、プロセスはステップＳ４８に戻る。上述した輪郭線トレーシング過程に従って、未追跡の残余輪郭線画素（例えば、図２に示された輪郭線画素３１〜３３）はトレーシングされ、ステップＳ４４で定義された全ての分岐画素は分岐画素としてのマーキングを解除される。従って、ステップＳ４８での判定結果が「いいえ」となり、プロセスは図５のステップＳ５３へ進む。
【００２１】
図５を参照すると、ステップＳ５３において、追跡済み輪郭線画素の中で多重インデックスの輪郭線画素が存在するか否かがチェックされる。もし、多重インデックスの輪郭線画素が存在する場合、ステップＳ５４でそれらの輪郭線画素のうちの何れか１つが選択される。次のステップＳ５５において、選択された多重インデックスの輪郭線画素のインデックスの中でまだ選択されていないインデックスのうちの何れか１つが選択される。その後、ステップＳ５６において、選択された多重インデックスの輪郭線画素のインデックスの中に、選択されていないインデックスがまだ存在するか否かがチェックされる。もし、選択されていないインデックスが存在しない場合、即ち、ステップＳ５５で選択されたインデックスがステップＳ５４で選択された多重インデックスの輪郭線画素のインデックスのうちで最後の未選択インデックスであった場合、ステップＳ５７にて選択された輪郭線画素の多重インデックスとしてのマーキングは外され、それ以上ステップＳ５３で多重インデックスの輪郭線画素として選択されないようにされる。そうしてプロセスはステップＳ４３に戻り、新たに選択されたインデックスを有する輪郭線画素に対して輪郭線トレーシングが行われる。ステップＳ５６において、まだ未選択インデックスが存在すると判定された場合、プロセスは直接ステップＳ４３に進む。上述したプロセスに従って、図２に示されたインデックスＢＫ２の背景画素に隣接する輪郭線画素がトレーシングされる。例えば、多重インデックスの輪郭線画素２６がステップＳ５４で選択されるとすると、ステップＳ５５でインデックスＣＰ−２が選択される。インデックスＣＰ−１及びＣＰ−２がステップＳ４２及びＳ５５で選択されたため、ステップＳ５７にて輪郭線画素２６に対する多重インデックスのマーキングは解除され、インデックスＣＰ−２の輪郭線画素に対する輪郭線トレーシングがステップＳ４３から行われる。新たに選択されたインデックスに対する輪郭線画素のトレーシングでは、前に選択されたインデックスに対する輪郭線トレーシングの際に、ステップＳ４５で行われた追跡済み画素としてのマーキングは無視される。従って、図２で「○」で表示されたインデックスＣＰ−２を有する輪郭線画素は全てトレーシングされ、輪郭線画素２６のような多重インデックスの輪郭線画素は再度トレーシングされることとなる。新たに選択されたインデックスの全ての輪郭線画素がトレーシングされ、多重インデックスの輪郭線画素の多重インデックスのマーキングが全て外されると、ステップＳ５３で追跡済み輪郭線画素の中にもはや多重インデックスの輪郭線画素が存在しないと判断される。その場合、ステップＳ５８に進み、未追跡輪郭線画素が存在するか否かが判断される。未追跡画素がある場合はプロセスは図４のステップＳ４１に進む。図２に示された入力映像の場合、物体ＯＢ２の輪郭線画素が未追跡であるため、プロセスはステップＳ４１に戻り、上述した方式で物体ＯＢ２の輪郭線画素のトレーシングがなされる。物体ＯＢ２の輪郭線画素のトレーシングが完了されると、追跡すべき輪郭線画素がもはや存在しなくなるため、輪郭線トレーシング過程は終了される。
【００２２】
上記において、本発明の特定の実施例について説明したが、本発明に記載した特許請求の範囲を逸脱することなく、当業者は種々の変更を加え得ることは勿論である。尚、本方法はコンピュータをプログラムに従って動作させることで実行可能であり、そのようなプログラムは所定の媒体に記憶させることが可能である。
【００２３】
【発明の効果】
従って、本発明によれば、物体の背景情報に基づいて、該物体の輪郭線を正確にかつ効果的にトレーシングして、輪郭線データのストリームで全ての輪郭線画素間の相関関係を用いることによって、符号化の効率を増大させ得ることができる。
【図面の簡単な説明】
【図１】本発明による輪郭線トレーシング装置の概略的なブロック図である。
【図２】２個の物体ＯＢ１及びＯＢ２を有する入力映像の例を示した模式図である。
【図３】本発明の輪郭線トレーシング方法を説明するためのフロー図である。
【図４】本発明の輪郭線トレーシング方法を説明するためのフロー図である。
【図５】本発明の輪郭線トレーシング方法を説明するためのフロー図である。
【符号の説明】
１２  輪郭線画素抽出ブロック
１４  背景インデクシングブロック
１６  輪郭線画素トレーシングブロック
ＢＫ１、ＢＫ２  背景インデックス
ＯＢ１、ＯＢ２  物体
【図１】
0003853450.tif 000002
【図２】
0003853450.tif 000003
【図３】
0003853450.tif 000004
【図４】
0003853450.tif 000005
【図５】
0003853450.tif 000006