(57)【特許請求の範囲】
【請求項１】
任意サイズの画面における領域形状を符号化する形状情報符号化方法において、
前記領域形状の横線方向の境界線の有無を１ラインずつ検査するステップと、
該領域形状の横線方向の境界線の有無データに基づいて、該境界線の有無データの横線方向の線長を計算し整数値として出力するステップと、
該整数値をγ符号またはδ符号を用いて符号化するステップと、
前記領域形状の縦線方向の境界線の有無を１ラインずつ検査するステップと、
該領域形状の縦線方向の境界線の有無データに基づいて、該境界線の有無データの縦線方向の線長を計算し整数値として出力するステップと、
該整数値をγ符号またはδ符号を用いて符号化するステップと、
該符号化された横線方向の線長データと縦線方向の線長データの、それぞれに対応するデータを結合するステップとからなる形状情報符号化方法。
【請求項２】
請求項１に記載の形状情報符号化方法において、
前記領域形状の縦線方向の有無を１ラインずつ検査するステップは、
当該ラインの直前に符号化されたラインの境界線情報に基づき、
縦線方向の境界線の符号化を必要としない場合に、該領域形状の縦線方向の境界線の有無の検査を省略するスキップ処理を含むことを特徴とする形状情報符号化方法。
【請求項３】
請求項１または２に記載の形状情報符号化方法において、
さらに、
前記横線方向の境界線の有無データに基づいて符号化された符号の長さを、該境界に隣接する画素に均等に配分するステップと、
前記縦線方向の境界線の有無データに基づいて符号化された符号の長さを、該境界に隣接する画素に均等に配分するステップと、
前記２つのステップの処理により横線方向、縦線方向それぞれで配分された符号量を加算するステップとを備え、
当該画面における画素毎の形状情報符号量の分布を出力するようにしたことを特徴とする形状情報符号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は形状情報符号化方法に関し、特に映像信号の領域分割符号化方式に用いて好適な形状情報符号化方法に関する。
【０００２】
【従来の技術】
従来から、映像信号の領域分割処理と、動き推定処理とを互いに関連付けて、動画像の動き推定をすることにより、動き補償予測効率を向上させるようにする研究が進められており、従来例として、例えば特開平１０−２２４８０２号公報に記されているものがある。
【０００３】
この従来技術では、画像をＮ個の小ブロックに分割し、各小ブロックに対してＬ個の候補動ベクトルｖi （ｉ＝１，２，…，Ｌ）を想定する。次に、該Ｌ個の候補動ベクトルｖi に対して、動き補償予測誤差絶対値和または二乗和などの動き補償予測のマッチ度の規範（ＳＡＤ）の値を計算し、画面全体でのマッチ度規範テーブルであるＳＡＤテーブルを作成する。続いて、該ＳＡＤテーブルを用いいて有意の候補動ベクトルを抽出し、該有意の候補動ベクトルを用いて、小ブロックを一様な動きの部分毎に領域として統合することにより、該統合された領域を物体形状情報とするものである。
【０００４】
この従来技術によれば、前記領域に、動きのない部分と動きのある部分とが混在するのを低減あるいは除去することができるようになり、予測誤差を削減し、動き補償予測効率を向上することができるようになる。
【０００５】
【発明が解決しようとする課題】
前記の従来技術は、画面全体の形状が既知になってはじめて形状符号量を計算することができるようになるが、局所的に領域の符号量を見積もることには格別の配慮がされていなかった。このため、例えば画像の領域の形状をいろいろと変化させて、最適な領域形状を選択することができなかった。
【０００６】
本発明は、前記した従来技術に鑑みてなされたものであり、その目的は、画像中の物体や背景などの輪郭情報を高能率符号化し、効率よく蓄積あるいは伝送できる形状情報符号化方法を提供することにある。
【０００７】
【課題を解決するための手段】
前記した目的を達成するために、本発明は、任意サイズの画面における領域形状を符号化する形状情報符号化方法において、前記領域形状の横線方向の境界線の有無を１ラインずつ検査するステップと、該領域形状の横線方向の境界線の有無データに基づいて、該境界線の有無データの横線方向の線長を計算し整数値として出力するステップと、該整数値をγ符号またはδ符号を用いて符号化するステップと、前記領域形状の縦線方向の境界線の有無を１ラインずつ検査するステップと、該領域形状の縦線方向の境界線の有無データに基づいて、該境界線の有無データの縦線方向の線長を計算し整数値として出力するステップと、該整数値をγ符号またはδ符号を用いて符号化するステップと、該符号化された横線方向の線長データと縦線方向の線長データの、それぞれに対応するデータを結合するステップとを具備した点に特徴がある。
【０００８】
この特徴によれば、任意のサイズの局所画面の領域形状を、効率よく符号化できるようになる。
【０００９】
【発明の実施の形態】
以下に、図面を参照して、本発明を詳細に説明する。まず、本発明の一実施形態の形状情報符号化方法を具体的に説明する。
【００１０】
図１は画面１を示し、該画面１内の任意の局所画面２に着目する。該局所画面２は仮に４×４画素の大きさであるとし、各画素の値は図示されているａ〜ｅ値で構成されているとする。つまり、局所画面２内には、点線で表された領域形状が存在するものとする。
【００１１】
図２は、該局所画面２の形状情報符号化を説明する図であり、まず横線方向について説明する。いま、横線を図１に示されているように、ｙ，ｙ＋１，ｙ＋２，ｙ＋３とすると、横線ｙとｙ＋１との間に領域形状が存在するか否かを検査する。領域形状が存在しない時には０とし、存在する時には１とする。このため、図示の場合には、図２のように、領域識別データ１１は００１１となる。次に、横線ｙ＋１とｙ＋２との間、ｙ＋２とｙ＋３との間、に領域形状が存在するか否かを同様に検査する。図示の場合には、各々の領域識別データは１１００，１１１１となる。
【００１２】
次に、該領域識別データを線長データに変換する。該線長データは、以下の規則に従って作成する。(1) 各行のデータは、必ず０の個数から始める。(2) 先頭が１の場合は、０の個数が０であることを示す１ビットを加算する。(3) 先頭の０ランに対しては、該０ランに＋１する。(4) ＥＯＬは使用しない（全て、０ランか１ラン）。
【００１３】
図２の領域識別データ１１に前記の規則を適用して線長データを作成すると、次のようになる。なお、０、１各々の長さを表す関数を、ｆ(n) とする。ここに、ｎは０ランまたは１ランの個数である。
【００１４】
まず、第１行の「００１１」は、先頭の０ランが２個なのでｆ(2) となるが、先頭の０ランに対しては＋１するので（規則(3) ）、ｆ(2+1) となる。また、その後に１が２個続くので、ｆ(2) となる。次に、第２行の「１１００」は、先頭の１ランに対しては、先頭の０の個数が０であることを示す１ビットを加算するので（規則(2) ）、ｆ(2) ＋１となる。その後に続く０の２個は、ｆ(2) と表される。さらに、第３行の「１１１１」は、前記規則(2) を適用して、ｆ(4) ＋１と表される。以上のようにして、図２の線長データ１２が作成される。
【００１５】
次に、該線長データ１２を整数符号化する。この整数符号化は、図３に示されるγ方式またはδ方式で行うことができる。これらの整数符号化された結果が、出力される形状情報となる。なお、図３は、γ方式またはδ方式で符号化した場合のビット数を示している。
以下では、γ方式での整数符号化を適用して説明すると、図２の線長データ１２は、整数符号化データ１３に整数符号化される。すなわち、第１行の線長データは、「ｆ(2+1) ，ｆ(2) 」であるので、整数符号化データのビット数は「３，３」となる。以下、第２行の線長データのビット数は、「４，３」、第２行の線長データビット数は、「６」となる。
【００１６】
次に、該整数符号化データ１３を、単位横線長に分配する処理をして、単位横線長分配データ１４を作成する。図２の例では、第１行の「３，３」は、それぞれ２画素分に相当するデータであるので「３／２，３／２，３／２，３／２」となり、さらにこれらは２本の横線長に相当するデータであるので、該単位横線長分配データ１４は、さらに１／２倍されて「３／４，３／４，３／４，３／４」となる。すなわち、「０．７５，０．７５，０．７５，０．７５」となる。同様に、第２行は、「１，１，０．７５，０．７５」、第３行は、「６／８，６／８，６／８，６／８」、すなわち「０．７５，０．７５，０．７５，０．７５」となる。
【００１７】
次に、該単位横線長分配データ１４から、画素毎領域符号化データ１５を作成する処理をする。この処理は、単位横線長分配データ１４の各行は、２行の画素から作成されたものであるので、該単位横線長分配データ１４の各行のデータを該２行の各画素位置に配分する。図２を用いて具体的に説明すると、単位横線長分配データ１４の第１行のデータは、画素毎領域符号化データ１５の第１行と第２行に配分する。同様に、単位横線長分配データ１４の第２行のデータは、画素毎領域符号化データ１５の第２行と第３行に、また単位横線長分配データ１４の第３行のデータは、画素毎領域符号化データ１５の第３行と第４行に配分する。なお、前記第２行と第３行は、同じ画素位置に配分されたデータを加算する。以上のようにして、図２の画素毎領域符号化データ１５が作成される。
【００１８】
次に、縦線方向の領域符号化について説明する。縦線方向の領域符号化では、横線方向の領域符号化ではなかった処理、すなわち冗長な縦線はスキップ(skip)する処理を導入する。すなわち、画素データの分布が、図４(p) 〜(s) の４つの場合には、下方の縦線（点線で図示）の有無は、上方の縦線および横線（実線で図示）から推測できるので、下方の縦線の有無の表示をスキップするようにする。
【００１９】
図２に戻って説明すると、図１の局所画面２のｘ列〜ｘ＋３列に対して、前記横線方向の領域識別データ１１を求めたのと同様の方法で、第１列〜第３列の縦線方向領域識別データ２１を求める。この時、図４の条件に合致するものに対しては、スキップＳを導入する。次に、横線方向の線長データ１２を求めたのと同様の方法で、縦線方向の線長データ２２を求める。この時、前記スキップＳの線長データは、０と置く。
【００２０】
次に、横線方向の整数符号化データ１３を求めたのと同様の方法で、縦線方向の整数符号化データ２３を求める。次いで、横線方向の単位横線長分配データ１４を求めたのと同様の方法で、縦線方向の単位縦線長分配データ２４を求める。すなわち、図２の例では、第１行の「３，１，１」は、それぞれ２画素分の横線長に相当するデータであるので、該単位縦線長分配データは、「３／２，１／２，１／２」となる。すなわち、「１．５，０．５，０．５」となる。以下同様に、第２〜４行は、「０，１，０．５」、「１．５，０．５，０」、「０．８３，０．８３，０．８３」となる。
【００２１】
次に、該単位縦線長分配データ２４から、画素毎領域符号化データ２５を作成する処理をする。この処理は、単位縦線長分配データ２４の各行は、２列の画素から作成されたものであるので、該単位縦線長分配データ２４の各列のデータを該２列の各画素位置に配分する。図２を用いて具体的に説明すると、単位縦線長分配データ２４の第１列のデータは、画素毎領域符号化データ２５の第１列と第２列に配分する。同様に、単位縦線長分配データ２４の第２列のデータは、画素毎領域符号化データ２５の第２列と第３列に、また単位縦線長分配データ２４の第３列のデータは、画素毎領域符号化データ２５の第３列と第４列に配分する。なお、前記第２列と第３列は、同じ画素位置に配分されたデータを加算する。以上のようにして、図２の画素毎領域符号化データ２５が作成される。
【００２２】
以上のようにして、横線方向および縦線方向の画素毎領域符号化データ情報量の分布１５、２５が求められると、これらは同じ要素同士が互いに加算され、形状情報符号化データ情報量の分布２７が求められる。図示の例では、前記局所画面２の形状情報符号化に要する符号量は、３６ビットになる。
【００２３】
次に、前記具体例の処理を一般化したアルゴリズムを図５および図６を参照して説明する。図５は横線処理のフローチャート、図６は縦線処理のフローチャートである。なお、図中の下線部分はベクトル演算を表している。
【００２４】
図１の前記局所画面２を参照して、以下に図５の処理を説明する。ステップＳ１では、行を表すｙが０と置かれ、ステップＳ２では、長さｈのベクトルＶを用意し、最初はベクトルＶ＝０とする。ステップＳ３では、ｘ＝０とし、ステップＳ４に進む。ステップＳ４では、領域情報が入ったマトリックスをＭｍ［］［］とし、Ｍｍ［ｙ］［ｘ］＝Ｍｍ［ｙ＋１］［ｘ］が成立するか否かの判断をする。すなわち、ｙ＝ｘ＝０の位置の画素と、ｙ＝１，ｘ＝０の位置の画素との間に、領域があるか否かの判断がなされる。ステップＳ４の判断が肯定になれば、すなわち領域が存在しなければステップＳ５に進んでＶ[0] ＝０と置かれる。一方、否定であれば、すなわち領域が存在すれば、ステップＳ６に進んでＶ[0] ＝１と置かれる。次にステップＳ６に進んで、ｘ＜ｈが成立するか否かの判断がなされ、この判断が肯定になるとステップＳ７に進んで、ｘに１が加算される。なお、ｈは図１の前記局所画面２に示されているように、行方向の幅を表す。続いて、ステップＳ４に戻り、ｙ＝０，ｘ＝１の位置の画素と、ｙ＝１，ｘ＝１の画素との間に、領域があるか否かの判断がなされる。
【００２５】
以下、前記と同様の処理が行われ、ステップＳ６の判断が否定になると、図２の横線方向の領域識別データ１１の第１行が得られたことになる。ステップＳ７では、前記ベクトルＶを線長データｆに変換し、図２の線長データ１２の第１行を得る。ステップＳ８では、線長データｆを整数符号化により、単位横線毎のビット列Ｂに変換する。この処理により、図２の整数符号化データ１３の第１行が得られたことになる。ステップＳ９に進むと、該単位横線毎のビット列Ｂが１／２にされ、図２の横線方向の単位横線長分配データ１４の第１行が得られる。次いで、形状情報符号量のマトリクスをＭｓ［］［］とし、Ｍｓ[y] ＝Ｍｓ[y] ＋Ｂ、Ｍｓ[y+1] ＝Ｍｓ[y+1] ＋Ｂの処理をする。この処理により、横線方向の画素毎領域符号化データ１５の第１行と、第２行の一部のデータが得られる。ステップＳ１０では、ｙ＜ｖが成立するか否かの判断がなされる。ここに、ｖは図１の局所画面２に示されているように、列方向の幅である。ステップＳ１０の判断が肯定の時にはステップＳ１１に進んで、ｙに１が加算される。そして、再度前記ステップＳ３以下の処理が続行される。
【００２６】
以上の処理が行われ、前記ステップＳ１０の判断が否定になると、前記横線方向の画素毎領域符号化データ１５が得られることは明らかである。次に、図６の縦線処理に進む。
【００２７】
ステップＳ２１〜Ｓ２３は、図５のステップＳ１〜Ｓ３と同じ処理であるので説明を省略する。ステップＳ２４では、縦線は冗長であるか否かの判断がなされる。すなわち、図４で説明した４つのパターンに当てはまっているか否かの判断がなされる。この判断が肯定の場合にはステップＳ２５に進んで、Ｖ[x] ＝スキップと置かれる。一方、否定の場合には、ステップＳ２６に進んで、Ｍｍ[y][x]＝Ｍｍ[y][x+1]が成立するか否かの判断がなされる。例えば、Ｍｍ[0][0]＝Ｍｍ[0][1]が成立するか否かの判断がなされる。この判断が肯定の場合には、縦線の領域が存在しないので、ステップＳ２７に進んでＶ[x] ＝０と置かれ、否定の場合には、縦線の領域が存在するので、ステップＳ２８に進んでＶ[x] ＝１と置かれる。ステップＳ２９では、ｘ＜ｈ−１が成立するか否かの判断がなされ、この判断が肯定の場合には、ステップＳ３０に進んでｘに１が加算される。そして、ステップＳ２４〜Ｓ２９の処理が繰り返される。この処理の結果、ステップＳ２９の判断が否定になると、図２の縦線方向領域識別データ２１の第１列が得られたことになる。
【００２８】
ステップＳ３１では、ベクトルＶを線長データｆに変換する。これにより、図２の縦線方向の線長データ２２の第１行が求められる。ステップＳ３２では、線長データｆを整数符号化により、単位縦線毎のビット列Ｂに変換する。ただし、スキップ縦線部には、０ビットが入れられる。これにより、図２の縦線方向の整数符号化データ２３の第１行が得られる。次いで、ステップＳ２３に進み、Ｂ＝Ｂ／２とされる。これにより、図２の単位縦線長分配データ２４の第１行が得られる。続いて、Ｍｓ[y] ＝Ｍｓ[y] ＋Ｂ＋（右に１ビットシフトしたＢ）の処理がなされる。この処理により、形状情報符号化データ２７の第１行が求められたことになる。
【００２９】
ステップＳ３４では、ｙ＜ｖが成立するか否かの判断がなされ、この判断が肯定の時にはステップＳ３５に進んでｙに１が加算される。そして、ステップＳ２３に戻って、前記した処理が繰り返される。ステップＳ３４の判断が否定になった時には、形状情報符号化データ２７が得られることは明らかである。ステップＳ３４が否定になると、一連の処理は終了する。
【００３０】
前記した本実施形態によれば、画面全体の形状が既知でなくても、局所的に形状符号量を計算することができるようになり、画像の領域の形状をいろいろと変化させて、最適な形状を選択することができるようになる。
【００３１】
図７は、本発明を適用することができる装置の一例である動画像の領域分割符号化装置のブロック図を示す。入力画像３１は、例えば４×４画素のブロック毎に入力してくる。減算器３２は該入力画像３１と動き補償部３３から出力される動き補償された前画像との差、すなわち動き補償予測誤差を出力する。直交変換部３４ａ、量子化部３４ｂは、該動き補償予測誤差を符号化および量子化する。該量子化された動き補償予測誤差はバッファ３５に一時的に格納されると共に、逆量子化部３６ａ、逆直交変換部３６ｂに送られる。加算器３７は、該逆量子化部３６ａ、逆直交変換部３６ｂによって復号された動き補償予測誤差と前記動き補償部３３から出力された動き補償された前画像とを加算することにより現画像を復元し、フレームメモリ３８に格納する。ビットレート制御部３９は、バッファ３５に記憶されているデータ量に基づいて、前記量子化部３４ｂの量子化ステップサイズを決定する。動き推定部４０は、入力画像１とフレームメモリ８に格納されている画像とから、前記４×４画素のブロック毎に動き推定処理を行う。領域分割部４１は、該ブロック毎に領域形状の分割を行い、前記した本発明の形状情報符号化により、領域形状の符号量を計算する。該領域分割部４１に、本発明を適用することができる。
【００３２】
図７の領域分割符号化装置では、領域分割と動き推定は同時並行に行われなくてはならない。すなわち、画像中の各所における動きベクトルを符号量とＳＮＲの関係から最適なものにするためには、点線５０で囲まれた装置が全て同時に行われなくてはならない。このため、動きベクトルのための符号量と形状符号量とを同時に目標符号量に抑えなくてはならないことになり、領域分割部４１にて、領域の形状を色々と変化させて最適な領域形状を選択する。本発明では、局所的に領域の符号量を見積もることができるため、該領域分割部４１に適用すると好適である。
【００３３】
【発明の効果】
以上の説明から明らかなように、本発明によれば、物体形状や領域形状等の２値情報を、効率良く符号化できるようになる。また、形状符号量の見積りを、領域形状が完全に与えられなくても、逐次的に推定できるようになる。換言すれば、領域の符号量を局所的に見積もることができるようになる。また、このため、映像信号の領域分割符号化方式において、領域の形状を色々と変化させて最適な領域形状を選択することを目的とする場合に、局所的に最適な領域を決定することが可能になる。なお、従来方式では、画面全体の形状が既知になってはじめて符号量を計算することができた。
【図面の簡単な説明】
【図１】  本発明により領域符号化される局所画像の説明図である。
【図２】  局所画像の領域符号化の一具体例の説明図である。
【図３】  領域長さの整数符号化の一例を示す図である。
【図４】  縦方向領域の冗長な縦線をスキップする処理の説明図である。
【図５】  本発明の形状情報符号化処理の一実施形態を示すフローチャートである。
【図６】  図５の続きのフローチャートである。
【図７】  本発明を適用して好適な領域分割符号化装置の構成を示すブロック図である。
【符号の説明】
１…画面、２…局所画面、３４ａ…直交変換部、３４ｂ…量子化部、４０…動き推定部、４１…領域分割部。
【図１】
0003957123.tif 000002
【図２】
0003957123.tif 000003
【図３】
0003957123.tif 000004
【図４】
0003957123.tif 000005
【図５】
0003957123.tif 000006
【図６】
0003957123.tif 000007
【図７】
0003957123.tif 000008