(57)【特許請求の範囲】
【請求項１】
元曲線の形体を多角形近似により多角形に符号化し、該多角形の任意の一辺と、これに対応する元曲線の任意の一辺との誤差を求めるための誤差サンプリング方法において、
前記符号化した多角形の任意の一辺の傾斜度を求める過程と、
前記傾斜度が１より小さい場合には、水平軸から前記多角形および前記元曲線に投射し、前記傾斜度が１より大きくまたは等しい場合には、垂直軸から前記多角形および前記元曲線に投射する過程と、
前記傾斜度が１より小さい場合には、前記水平軸から前記元曲線上の点までの距離を距離Ｘとして、前記水平軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定し、前記傾斜度が１より大きくまたは等しい場合には、前記垂直軸から前記元曲線上の点までの距離を距離Ｘとして、前記垂直軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定する過程と、
前記距離Ｘから前記距離Ａを減算することにより、前記符号化した曲線と元曲線との誤差を決定する過程とを具備することを特徴とする符号化した２次元曲線に対する高速誤差サンプリング方法。
【請求項２】
入力元曲線の形体を多角形近似により多角形に符号化して、１次符号化した多角形を生成する過程と、
前記１次符号化した多角形の任意の一辺の傾斜度を求める過程と、
前記傾斜度が１より小さい場合には、水平軸から前記多角形および前記元曲線に投射し、前記傾斜度が１より大きくまたは等しい場合には、垂直軸から前記多角形および前記元曲線に投射する過程と、
前記傾斜度が１より小さい場合には、前記水平軸から前記元曲線上の点までの距離を距離Ｘとして、前記水平軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定し、前記傾斜度が１より大きくまたは等しい場合には、前記垂直軸から前記元曲線上の点までの距離を距離Ｘとして、前記垂直軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定する過程と、
前記距離Ｘから前記距離Ａを減算することにより、１次符号化した多角形と元曲線との誤差を生成する過程と、
前記１次符号化した多角形と元曲線との誤差を符号化する過程と、
前記誤差を復号化する過程と、
前記復号化した誤差を、前記１次符号化した多角形に加える過程と、
前記誤差が加えられた前記１次符号化した多角形を復号して、１次復号化した曲線を生成する過程とを具備することを特徴とする高能率の動画像符号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は動画像符号化装置に係り、特に符号化した２次元曲線に対する高速誤差サンプリング方法及びこれを用いた高能率の動画像符号化方法に関する。
【０００２】
【従来の技術】
最近、ビデオデータベース或いはビデオ伝送などがマルチメディアの核心技術として浮かび上がっている。人に認識される大部分の可視的な物体は究極的にその形体と内部テキスチャで示すことができ、今後のビデオ処理技術は一枚のフレーム単位でなく、人に知覚される物体や内容単位の処理を志向している。特に、現在進められているＭＰＥＧ−４のような国際映像符号化の標準は“内容−基盤”を重要目標としている。従って、物体の映像を描写することに２次元曲線の符号化方法は基本的な手段として用いられている。
【０００３】
一方、与えられた２次元曲線の形体は多角形近似により、多角形に符号化し得る。この際、より高い近似度のために多角形近似されてできた多角形はもう一度符号化し得るが、このために元曲線と該多角形との誤差を求めるべきである。元曲線と多角形近似された多角形との誤差を求めるための誤差サンプリング方法には多種がある。そのうち、コンピュータ上で容易な具現方法の一つとして、図１に示したように、元曲線を多角形近似してできた多角形１０２上の一点と該点に対応する元曲線１０１上の一点との距離を求める方法が挙げられる。図１に示した誤差の一部を図３の誤差３０２と仮定し得る。即ち、図３は多角形の一辺と関連した誤差と元曲線の一部を示したものである。
【０００４】
ここで、既存の方法は主に図４のような誤差サンプリング方法を用いている。即ち、元曲線上の一点３０１に対する誤差サンプリングのために点３０１と線分３０３との垂直距離を測定する。垂直距離３０５（ｄ）は点３０１を（ｘ１  ，ｙ１  ）とし、線分３０３を直線の方程式ａｘ＋ｂｙ＋ｃ＝０で示す時、次の式１のように示せる。
【０００５】
【数１】
0003623047.tif 000002
【０００６】
従って、曲線線分３０４上の各点（ｘｉ  ，ｙｉ  ）に対して前記式１を適用すべきである。即ち、図４のＸ０  ，Ｘ１  ，…，Ｘ７  ，Ｘ８  のような形態の（ｘｉ  ，ｙｉ  ）のそれぞれに対して前記式１を適用する。曲線線分３０４に対する誤差サンプリングを行う場合、直線線分３０３は固定されているので、前記式１の分母（ａ２  ＋ｂ２  ）１／２  が再び計算される必要はない。しかし、少なくとも２回の乗算（ａｘ１  、ｂｙ１  ）と２回の加算（ａｘ１  ＋ｂｙ１  、ｂｙ１  ＋ｃ）及び１回の除算（ｄ＝｜ａｘ１  ＋ｂｙ１  ＋ｃ｜／（ａ２  ＋ｂ２  ）１／２  ）が必要である。
【０００７】
さらに、符号化した誤差が元映像に復元される時、図４のＡ０  ，Ａ１  ，…，Ａ７  ，Ａ８  の位置が符号化時と同一であるべきである。これは、復元する時には曲線線分３０４のような元曲線情報がないため、直線線分３０３を基準にして符号化／復号化されなければならないからである。
【０００８】
したがって、誤差の符号化／復号化のためには曲線線分４０４上の点から直線線分４０３上に垂線を引いてはいけない。その代わり、直線線分４０３上に予め限定された点Ａ０  ，Ａ１  ，…，Ａ７  ，Ａ８  から曲線線分４０４までの垂直距離を測定すべきである。このためにＡ０  ，Ａ１  ，…，Ａ７  ，Ａ８  から引いた垂線と曲線線分４０４との交点を求めた後、それぞれＸ０  ，Ｘ１  ，…，Ｘ７  ，Ｘ８  と定めてＸ０  ，Ｘ１  ，…，Ｘ７  ，Ｘ８  とＡ０  ，Ａ１  ，…，Ａ７  ，Ａ８  との距離を求めると符号化／復号化に好適な誤差が得られる。しかし、このような方法は計算が複雑である。
【０００９】
【発明が解決しようとする課題】
従って、本発明の目的は符号化した２次元曲線に対して高速に誤差サンプリングを行うために、符号化した２次元曲線上の任意の点を条件に応じて水平軸又は垂直軸上に投射させた後、投射された点から元曲線までの距離を誤差の測定に用いる高速誤差サンプリング方法を提供することにある。
【００１０】
本発明の他の目的は符号化した２次元曲線に対する高速誤差サンプリング方法を用いる高能率の動画像符号化方法を提供することにある。
【００１１】
【課題を解決するための手段】
前記の目的を達成するために本発明は、元曲線の形体を多角形近似により多角形に符号化し、該多角形の任意の一辺と、これに対応する元曲線の任意の一辺との誤差を求めるための誤差サンプリング方法において、前記符号化した多角形の任意の一辺の傾斜度を求める過程と、前記傾斜度が１より小さい場合には、水平軸から前記多角形および前記元曲線に投射し、前記傾斜度が１より大きくまたは等しい場合には、垂直軸から前記多角形および前記元曲線に投射する過程と、前記傾斜度が１より小さい場合には、前記水平軸から前記元曲線上の点までの距離を距離Ｘとして、前記水平軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定し、前記傾斜度が１より大きくまたは等しい場合には、前記垂直軸から前記元曲線上の点までの距離を距離Ｘとして、前記垂直軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定する過程と、前記距離Ｘから前記距離Ａを減算することにより、前記符号化した曲線と元曲線との誤差を決定する過程とを具備することを特徴とする
【００１２】
前記他の目的を達成するために本発明による高能率の動画像符号化方法は、入力元曲線の形体を多角形近似により多角形に符号化して、１次符号化した多角形を生成する過程と、前記１次符号化した多角形の任意の一辺の傾斜度を求める過程と、前記傾斜度が１より小さい場合には、水平軸から前記多角形および前記元曲線に投射し、前記傾斜度が１より大きくまたは等しい場合には、垂直軸から前記多角形および前記元曲線に投射する過程と、前記傾斜度が１より小さい場合には、前記水平軸から前記元曲線上の点までの距離を距離Ｘとして、前記水平軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定し、前記傾斜度が１より大きくまたは等しい場合には、前記垂直軸から前記元曲線上の点までの距離を距離Ｘとして、前記垂直軸から投射された前記多角形上の点までの距離を距離Ａとしてそれぞれ測定する過程と、前記距離Ｘから前記距離Ａを減算することにより、１次符号化した多角形と元曲線との誤差を生成する過程と、前記１次符号化した多角形と元曲線との誤差を符号化する過程と、前記誤差を復号化する過程と、前記復号化した誤差を、前記１次符号化した多角形に加える過程と、前記誤差が加えられた前記１次符号化した多角形を復号して、１次復号化した曲線を生成する過程とを具備することを特徴とする。
【００１３】
【発明の実施の形態】
以下、添付した図面に基づき本発明の好ましい一実施例を詳細に説明する。
【００１４】
図２において、入力元曲線２０１の形体を多角形近似により多角形に符号化する。この際、多角形２０２又は２０４は元曲線を多角形に１次符号化した直線とし、１次符号化した直線２０２又は２０４と元曲線２０１との差を求めてこれを１次符号化した直線２０２又は２０４の誤差２０８とする。
【００１５】
一方、サンプリングされた誤差２０８は離散余弦変換（ＤＣＴ）などによりＤＣＴ係数に符号化し、ＤＣＴ係数に符号化した誤差は再び逆離散余弦変換されて復号化する。復号化した誤差２１０は１次符号化／復号化した多角形２１１に加えられて元曲線２０１により、近似した直線２１２に復号化する。
【００１６】
元曲線１０１と近似された多角形１０２との誤差サンプリングのために本発明では図４のような方法の代わりに図５Ａ及び図５Ｂのような方法を提案する。
【００１７】
図５Ａ及び図５Ｂにおいて、近似された多角形の一辺４０３の元曲線４０４に対する誤差を求める際、図４のＸ0 ，Ｘ1 ，…，Ｘ7 ，Ｘ8 から辺４０３に垂線を引いた時垂線と辺４０３との各接点Ａ0 ，Ａ1 ，…，Ａ7 ，Ａ8 までのそれぞれの距離を測定せず、水平軸に対する直線線分の傾斜度が１より小さいとＸ軸（水平軸）との距離５０１を、水平軸に対する直線線分の傾斜度が１より大きかったり等しいとＹ軸（垂直軸）との距離５０６を測定して誤差として用いる。この際、直線線分５０３又は５０８の傾斜度は前述したａｘ＋ｂｙ＋ｃ＝０から求められる。
【００１８】
測定された誤差は｜Ｘ０  −Ａ０  ｜，｜Ｘ１  −Ａ１  ｜，…，｜Ｘ７  −Ａ７  ｜，｜Ｘ８  −Ａ８  ｜で示せる。図５Ａ及び図５Ｂにおいて、Ａ０  ，Ａ１  ，…，Ａ７  ，Ａ８  は符号器と復号器の両方で一定した間隔を保つべきであり、一種のサンプリング区間とも言える。
【００１９】
図５Ａにおいて、近似された多角形の一辺５０３は符号化／復号化した直線線分の傾斜度が１より小さい場合であって、Ｘ軸（水平軸）から投射されたＡ０  ，Ａ１  ，…，Ａ７  ，Ａ８  から曲線線分５０４までの垂直距離５０１を測定してこれを誤差と定め符号化する。これに対して、図５Ｂにおいて、近似された多角形の一辺５０８は符号化／復号化した直線線分の傾斜度が１より大きかったり等しい場合であって、Ｙ軸（垂直軸）から投射されたＡ０  ，Ａ１  ，…，Ａ７  ，Ａ８  から曲線線分５０９までの垂直距離５０６を測定してこれを誤差と定め符号化する。
【００２０】
一方、復号化時には、水平軸又は垂直軸を基準にして足し算の演算のみで誤差補正を行うので計算量を減らし得る。即ち、多角形に１次符号化した曲線を復号化すると、多角形の一辺５０３又は５０８が得られ、ここで、Ａ０  ，Ａ１  ，…，Ａ７  ，Ａ８  は復号化から得られた直線線分５０３又は５０８上の点である。本発明により誤差サンプリングされた値｜Ｘ０  −Ａ０  ｜，｜Ｘ１  −Ａ１  ｜，…，｜Ｘ７  −Ａ７  ｜，｜Ｘ８  −Ａ８  ｜は符号化／復号化されて１次復号化した値Ａ０  ，Ａ１  ，…，Ａ７  ，Ａ８  に加えられれて元曲線５０４又は５０９に近似した曲線を生成する。サンプリングされた誤差が補償される過程は水平軸又は垂直軸の一方に限って行われる。
【００２１】
前述したように、本発明により符号化した２次元曲線に対する高速誤差サンプリング方法及びこれを用いた高能率の動画像符号化方法においては、１次符号化した多角形の任意の一辺の傾斜度によって、水平軸又は垂直軸に対して１次符号化した多角形の任意の一辺上の点から前記元曲線の任意の一辺上に投射させた後、投射された点から水平軸または垂直軸までの距離を測定して前記１次符号化した多角形と元曲線との誤差を生成することによって、従来より誤差サンプリングが簡便になり、よって２次元物体の形体を符号化／復号化する時高速処理し得る。
【００２２】
さらに、本発明の傾斜度の測定、投射、誤差測定による誤差サンプリング方法は３次元物体の形体を符号化する時３次元の曲面を２次元の平面により符号化した後、符号化した曲面の誤差をサンプリングすることによって、３次元にも容易に拡張できる。
【図面の簡単な説明】
【図１】元曲線と多角形近似により符号化した曲線を示した図である。
【図２】多角形近似及びＤＣＴを用いた外郭線の符号化方法を説明するための図である。
【図３】垂直距離の測定により誤差を求める方法を説明するための図である。
【図４】垂直距離の測定により誤差をサンプリングする方法を説明するための図である。
【図５】図５Ａは本発明による符号化した２次元曲線に対する高速誤差サンプリング方法の一実施例を示した図であり、図５Ｂは本発明による符号化した２次元曲線に対する高速誤差サンプリング方法の他の実施例を示した図である。
【図１】
0003623047.tif 000003
【図２】
0003623047.tif 000004
【図３】
0003623047.tif 000005
【図４】
0003623047.tif 000006
【図５】
0003623047.tif 000007