(57)【特許請求の範囲】
【請求項１】
形状情報を有する対象物の映像にグリッドを形成して所定の大ききのブロックに区画し前記グリッドを移動させる段階と、
全ての画素を探索せず選択的に画素を探索し最初に対象物体が存在する画素発見時に探索を中断し現在探索しているブロックを対象物体が存在するブロックとして決定する過程を全体ブロックに対して遂行して、前記対象物体が存在するブロックの個数をカウントする探索およびカウント段階と、
前記カウント結果により最も最小個数のブロックをもつようになる新たなグリッドスタート点を決定する段階と
からなることを特徴とする選択的な画素探索を利用したグリッド移動方法。
【請求項２】
前記ブロック内に物体が存在するか選択的に画素を探索する過程で、ブロックの端部境界の画素全体を探索することを特徴とする請求項１記載の選択的な画素探索を利用したグリッド移動方法。
【請求項３】
前記ブロック内に物体が存在するか選択的に画素を探索する過程で、ブロックの端部境界の画素を探索しＮ個の画素ずつ飛び越しながら物体が存在するか探すことを特徴とする請求項１記載の選択的な画素探索を利用したグリッド移動方法。
【請求項４】
前記ブロック内に物体が存在するか選択的に画素を探索する過程で、対角線方向の画素を探索してブロック内に物体が存在するかを探すことを特徴とする請求項１記載の選択的な画素探索を利用したグリッド移動方法。
【請求項５】
前記グリッド移動段階の以後、符号化しようとする物体映像を所定の方法によって４等分して上方の左側部分を第１四分面、上方の右側部分を第２四分面、下方の左側部分を第３四分面、下方の右側部分を第４四分面とし、前記ブロック内に物体が存在するか選択的に画素を探索する過程で、どの四分面に属するブロックであるかにより選択的に探索する方法を異ならせることを特徴とする請求項１記載の選択的な画素探索を利用したグリッド移動方法。
【請求項６】
前記第１四分面の場合、右側の下方端部の画素から端部境界の画素に対してブロック内に物体が存在するかをジグザグ式に探すことを特徴とする請求項５記載の選択的な画素探索を利用したグリッド移動方法。
【請求項７】
前記第２四分面の場合、左側の下方端部からブロック内に物体が存在するかをジグザグ式に探すことを特徴とする請求項５記載の選択的な画素探索を利用したグリッド移動方法。
【請求項８】
前記第３四分面の場合、右側の上方端部からブロック内に物体が存在するかをジグザグ式に探すことを特徴とする請求項５記載の選択的な画素探索を利用したグリッド移動方法。
【請求項９】
前記第４四分面の場合、左側の上方端部からブロック内に物体が存在するかをジグザグ式に探すことを特徴とする請求項５記載の選択的な画素探索を利用したグリッド移動方法。
【請求項１０】
アドレスを発生するスタート位置を単位領域の大きさ以内で一定間隔ずつ移動させて出力するアドレス発生制御手段と、
前記アドレス発生制御手段が出力するアドレススタート位置により対象物の映像を単位領域に区分して出力するようにアドレスを発生するアドレス発生手段と、
入力される形状情報を有する対象物の映像を貯蔵し、この貯蔵された映像をアドレス発生器からのアドレスによって出力するメモリ手段と、
前記メモリ手段から入力される映像データを一次元から二次元に構成した後、Ｎ×Ｍブロック単位に区分してブロックの端部画素のみ物体が存在するかを確認する端部画素の探索手段と、
前記端部画素の探索手段から物体が存在するブロックの個数を計数するブロック個数カウント手段と、
前記ブロック個数カウント手段によって計数されたデータから最小ブロックに構成することができるスタート点を決定する最小ブロックグリッド選択手段と
を包含して構成されていることを特徴とする選択的な画素探索を利用したグリッド移動装置。
【請求項１１】
前記アドレス発生手段は、入力される対象物映像の大きさ情報により単位領域の横の大ききおよび単位領域の縦の大きさをそれぞれ決定する横軸の大きさの決定手段および縦軸の大きさの決定手段と、前記アドレス発生制御手段から出力されるアドレススタート位置から前記横軸の大きさの決定手段および縦軸の大きさの決定手段が決定した単位領域の横軸および維軸の大きさを区分し区分した単位領域の横軸および縦軸の大きさによるアドレスを順次発生する領域アドレス発生手段とから構成されることを特徴とする請求項１０記載の選択的な画素探索を利用したグリッド移動装置。
【請求項１２】
前記単位領域の横軸および縦軸の大きさが同一の場合に一つの大きさの決定手段によって単位領域の横軸および縦軸の大きさを決定することを特徴とする請求項１０記載の選択的な画素探索を利用したグリッド移動装置。
【請求項１３】
前記ブロック個数カウント手段は、クロック信号をカウントして単位領域を区分するブロックカウント手段と、前記メモリ手段から出力される映像の単位領域を前記ブロックカウント手段の出力信号により区分し対象物の形状情報が存在するかの可否を判断する形状情報の存在判断手段と、前記形状情報の存在判断手段の判断信号をカウントして対象物の映像が存在する単位領域の数を出力する領域数加算手段とから構成されることを特徴とする請求項１０記載の選択的な画素探索を利用したグリッド移動装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、形状情報および／または映像情報を有する所定の物体や領域等を始めとした各種対象物の映像にグリッドを形成して単位領域に区画し、形成したグリッドを移動させたのち、映像グリッドを再構成して符号化しなければならない対象物体が占有するブロック個数を減少させてやる形状適応の領域分割から個々のブロック毎に物体が存在するかを迅速な速度に把握することができるようにすることによって計算量を大幅に減少させて演算速度を増加させることができるようにした選択的な画素探索を利用したグリッド移動方法および装置に関するものである。
【０００２】
【従来の技術】
一般的に、物体の信号情報を符号化するにはブロック離散コサイン変換（Discrete Cosine Transfom：以下、“ＤＣＴ”と略称する）およびベクトル量子化器等が使用されており、最近では形状適用形ＤＣＴ（Shape Adaptive ＤＣＴ：以下、“ＳＡＤＣＴ”と略称する）が物体の形状情報を利用する物体中心符号化方法で非常に効果的なものとして提案されている。
【０００３】
このようなＳＡＤＣＴは任意の形態を有する所定物体の信号情報を効率的に符号化することを目的とするものであり、映像フレームを所定の大きさのブロックに細分化した後にブロック内に入る物体の信号情報のみを符号化するものである。すなわち、ＳＡＤＣＴは、ブロックが符号化する情報によってすべて満たされると、前記二次元ブロックＤＣＴと符号化の効率が同一になり、すべて満たさない場合には物体の領域に該当する信号のみ横軸に一次元ＤＣＴを遂行し、前記一次元ＤＣＴを遂行した結果を再び縦軸に一次元ＤＣＴして最終結果の値を得るものである。
【０００４】
また、ＳＡＤＣＴは、ＤＣＴ符号化利得を考慮する場合に物体の映像がいろんなブロックに分離されて符号化されることより、可能ならばブロック内部に物体の映像がたくさん満たされることが変換係数の圧縮効率が向上される。
そのため、前記ＳＡＤＣＴを遂行する場合に、ブロックの内部に符号化する物体の映像を効果的に満たして映像が位置するブロックの数を減少させたのち、符号化することが望ましい。
【０００５】
また、他の一般的なＤＣＴやブロックの量子化を遂行する場合にもそのままに符号化を遂行することによってフレーム当たりのビット率が高く、物体の映像が占有するブロックの数が多数であるので、信号情報のデータ量を減少させるのに限界があった。
したがって、前記のような間題点を解決するために、本出願人によって提案されたものとして、対象物体の位置によりグリッドのブロック位置を調節し、符号化を遂行して符号化の効率を向上させることができるようにしたものがある。
【０００６】
このようにグリッドを移動させて映像を再構成したのち、動き推定、テクスチャー情報の符号化等を遂行することによって符号化の効率を向上させることができ、ブロックグリッドを移動させてスタート点の位置を変換させることによって物体が包含されるブロック個数が最小になるようにする過程を、形状適応の領域分割という。
このような形状適応の領域分割は、現在国際標準化の作業中であるＭＰＥＧ−４の応用分野である画像電話、画像会議、ＰＣＳ、モービル用電話および今後の符号化の技術に有用に利用しうる。
【０００７】
もし、映像画面から符号化しようとする物体がある場合、形状情報を有するある物体やある領域を一つの画面でブロック単位に符号化する。
ここで、ブロックの単位はＮ×Ｍであり、画面全体を規則的に構成しうる多角形（例えば、三角形、六角形）も一つのブロックの概念に包含させることができる。通常、映像画面から符号化しようとする物体がある場合、形状情報を有するある物体やある領域を対象に形状適応領域分割を適用する。
例えば、現在標準化が進行中であるＭＰＥＧ−４ではＶＯＰを映像画面の物体として考えることができる。
ここで、言及しているＶＯＰは、映像画面からある物体が存在するとき、その物体を別に分離してそれぞれの物体を別々に符号化することを基本骨格としている。
【０００８】
このとき、物体を包含している最小映像の大きさの横と縦の値と物体情報を伝送することになる。
形状適応の領域分割を遂行すれば、ブロック基盤の符号化において、物体はそのままに位置させた状態でグリッドを移動させて、物体の形状が最も少ない数のブロックが構成されるようにする新たなグリッドスタート点を探して符号化することによって符号化の効率を向上させることができる。
【０００９】
図１７は一般的なＶＭ（Verification Model）エンコーダのＶＯＰ符号化部で、前記ＶＯＰ形成部１０で形成されたそれぞれの物体映像に対するＶＯＰが動き推定部（Motion Estimation）１１に入力されてマクロブロックの単位に動きが推定される。
前記動き推定部１１で推定された動き情報は動き補償部（Motion Compensation） １２に入力されて動きが補償される。
また、前記動き補償部１２で動きが補償されたＶＯＰはこのＶＯＰ形成部１０で形成されたＶＯＰとともに減算器３に入力されて差の値が検出され、前記減算器１３で検出された差の値は物体内部の情報符号化部１４に入力されてマクロブロックのサブブロック単位に物体内部の情報が符号化される。
【００１０】
前記動き補償部１２で動きが補償されたＶＯＰと物体内部の符号化部１４で符号化された物体の内部情報が加算器１５に入力されて加算され、前記加算器１５の出力信号は以前のＶＯＰ検出部（Previous Reconstructed ＶＯＰ）１６に入力されて以前画面のＶＯＰが検出される。
前記以前のＶＯＰ検出部１６で検出された前記以前画面のＶＯＰは動き推定部１１および動き補償部１２に入力されて動き推定および動き補償に使用される。
【００１１】
一方、前記ＶＯＰ形成部１０で形成されたＶＯＰは形状情報の符号化部１７に入力されて形状情報が符号化される。
ここで、形状情報の符号化部１７の出力信号はＶＯＰ符号化部が適用される分野により使用可否が決定されるもので、形状情報の符号化部１７の出力信号を点線によって表示するように動き推定部１１、動き補償部１２および物体の内部情報の符号化部１４に入力させて動き推定、動き補償および物体の内部情報を符号化するのに使用することができる。
【００１２】
前記動き推定部１１で推定された動き情報、物体の内部情報の符号化部１４で符号化された物体の内部情報および形状情報の符号化部１７で符号化された形状情報はマルチプレクサ１８で多重化され、バッファ１９を通じてビットストリームに伝送される。
【００１３】
前記形状適応領域分割に適用することができる一例として、図１８は前述した定義のとおりに符号化しようとする物体を包含する最小の四角形の大きさを示す。
図１９は図１８で符号化しようとする物体をマクロブロック大ききの単位に右側と下側に拡大した図面であって、ブロックグリッド（点線部分）を移動させてスタート点位置を変換させることによって物体が包含されるブロックの個数が最小になるようにする。
【００１４】
図２０は図１９の物体境界のブロック中の一つであるＡブロックを拡大して示した図面であって、ブロックの大きさは１６×１６に示されているが、これに限定されず８×８であってもよく、ここでは大きさをＮ×Ｍに定義する。
このとき、従来では図２１に図示のようにブロック内に物体が包含されるかを決定するためにブロックの全ての画素を探した。
例えば、ブロックの大きさが１６×１６である場合、前記ブロック内に物体が存在するか探す画素の数は最大総２５６個になった。
したがって、２５６個の画素を継続して探す途中で一つでも物体が存在する画素が探せれば、そのブロックは物体が存在していると判断し次のブロックに移る。
【００１５】
【発明が解決しようとする課題】
しかしながら、従来ではブロック内に物体が存在するかを探すためにブロック全体をチェックしなければならなかった。
したがって、従来ではブロックグリッドのスタート点を変化しながら全体ＶＯＰのそれぞれのブロック毎に物体の包含可否を確認しなければならなく、計算量が多量となるので、演算速度が遅延することになる。
即ち、上述のような従来技術においては、ブロック内に物体が包含されたかを探すためにブロック内の画素を全部確認しなければならないので、演算速度が遅延するという問題点があった。
【００１６】
本発明はこのような従来の問題点を解決するためのもので、本発明の目的は、形状適応領域分割をする場合、物体はそのままに位置させた状態で物体の形状に合うようにグリッドを移動させることによって物体が存在するブロック個数が最も小さいグリッドのスタート点を探し、一つのブロック毎に物体が存在するかを確認するためにブロック内の全ての画素を探さないで探す始点の個数を減少させて形状適応領域分割の演算速度を迅速にすることができる選択的な画素探索を利用したグリッド移動方法および装置を提供することにある。
【００１７】
【課題を解決するための手段】
このような目的を達成するために、本発明の選択的な画素探索を利用したグリッド移動方法は、形状情報を有する対象物の映像にグリッドを形成して所定の大ききのブロックに区画し前記グリッドを移動させる段階と、全ての画素を探索せず選択的に画素を探索し最初に対象物体が存在する画素発見時に探索を中断し現在探索しているブロックを対象物体が存在するブロックとして決定する過程を全体ブロックに対して遂行して、前記対象物体が存在するブロックの個数をカウントする探索およびカウント段階と、前記カウント結果により最も最小個数のブロックをもつようになる新たなグリッドスタート点を決定する段階とからなることを特徴とするものである。
【００１８】
また、前記ブロック内に物体が存在するか選択的に画素を探索する過程で、ブロックの端部境界の画素全体を探索することを特徴とするものである。
【００１９】
また、前記ブロック内に物体が存在するか選択的に画素を探索する過程で、ブロックの端部境界の画素を探索しＮ個の画素ずつ飛び越しながら物体が存在するか探すことを特徴とするものである。
【００２０】
また、前記ブロック内に物体が存在するか選択的に画素を探索する過程で、対角線方向の画素を探索してブロック内に物体が存在するかを探すことを特徴とするものである。
【００２１】
また、前記グリッド移動段階の以後、符号化しようとする物体映像を所定の方法によって４等分して上方の左側部分を第１四分面、上方の右側部分を第２四分面、下方の左側部分を第３四分面、下方の右側部分を第４四分面とし、前記ブロック内に物体が存在するか選択的に画素を探索する過程から、どの四分面に属するブロックであるかにより選択的に探索する方法を異ならせることを特徴とするものである。
【００２２】
また、前記第１四分面の場合、右側の下方端部の画素から端部境界の画素に対してブロック内に物体が存在するかをジグザグ式に探すことを特徴とするものである。
【００２３】
また、前記第２四分面の場合、左側の下方端部からブロック内に物体が存在するかをジグザグ式に探すことを特徴とするものである。
【００２４】
また、前記第３四分面の場合、右側の上方端部からブロック内に物体が存在するかをジグザグ式に探すことを特徴とするものである。
【００２５】
また、前記第４四分面の場合、左側の上方端部からブロック内に物体が存在するかをジグザグ式に探すことを特徴とするものである。
【００２６】
また、本発明に係る選択的な画素探索を利用したグリッド移動装置は、アドレスを発生するスタート位置を単位領域の大きさ以内で一定間隔ずつ移動させて出力するアドレス発生制御手段と、前記アドレス発生制御手段が出力するアドレススタート位置により対象物の映像を単位領域に区分して出力するようにアドレスを発生するアドレス発生手段と、入力される形状情報を有する対象物の映像を貯蔵し、この貯蔵された映像をアドレス発生器からのアドレスによって出力するメモリ手段と、前記メモリ手段から入力される映像データを一次元から二次元に構成した後、Ｎ×Ｍブロック単位に区分してブロックの端部画素のみ物体が存在するかを確認する端部画素の探索手段と、前記端部画素の探索手段から物体が存在するブロックの個数を計数するブロック個数カウント手段と、前記ブロック個数カウント手段によって計数されたデータから最小ブロックに構成することができるスタート点を決定する最小ブロックグリッド選択手段とを包含して構成されていることを特徴とするものである。
【００２７】
また、前記アドレス発生手段は、入力される対象物映像の大きさ情報により単位領域の横の大ききおよび単位領域の縦の大きさをそれぞれ決定する横軸の大きさの決定手段および縦軸の大きさの決定手段と、前記アドレス発生制御手段から出力されるアドレススタート位置から前記横軸の大きさの決定手段および縦軸の大きさの決定手段が決定した単位領域の横軸および維軸の大きさを区分し区分した単位領域の横軸および縦軸の大きさによるアドレスを順次発生する領域アドレス発生手段とから構成されることを特徴とするものである。
【００２８】
また、前記単位領域の横軸および縦軸の大きさが同一の場合に一つの大きさの決定手段によって単位領域の横軸および縦軸の大きさを決定することを特徴とするものである。
【００２９】
また、前記ブロック個数カウント手段は、クロック信号をカウントして単位領域を区分するブロックカウント手段と、前記メモリ手段から出力される映像の単位領域を前記ブロックカウント手段の出力信号により区分し対象物の形状情報が存在するかの可否を判断する形状情報の存在判断手段と、前記形状情報の存在判断手段の判断信号をカウントして対象物の映像が存在する単位領域の数を出力する領域数加算手段とから構成されることを特徴とするものである。
【００３０】
【発明の実施の形態】
本発明に係る選択的な画素探索を利用したグリッド移動方法は、ブロック内に物体が存在するか探す支点をブロックの端部においてのみ確認するとかまたは端部においても所定のブロックＮずつ飛び越しながら確認するとかまたは対角線の方向の画素のみを確認する方法によって行なわれる。
また、本発明の選択的な画素探索を利用したグリッド移動方法は、符号化しようとするある物体映像を４等分して上方の左側部分を第１四分面、上方の右側部分を第２四分面、下方の左側部分を第３四分面、下方の右側部分を第４四分面であるとするとき、この物体映像の一番中央の角部からそれぞれのブロック内に物体が存在するかをそれぞれ４個の四分面を異ならせて探す方法によって達成される。
【００３１】
また、本発明の選択的な画素探索を利用したグリッド移動装置は、貯蔵された映像を入力されるアドレスによって次のブロックに送るメモリ手段と、物体をブロック単位に分類したとき、一番初めに該当する、即ち一番左側、一番上方のアドレススタート点から順に発生させて前記メモリ手段に送るアドレス発生手段と、前記メモリ手段から入力される映像データを一次元から二次元に構成した後、Ｎ×Ｍブロック単位に区分してブロックの端部画素のみ物体が存在するかを確認する端部画素の探索手段と、前記端部画素の探索手段から物体が存在するブロックの個数を計数するブロック個数カウンタと、前記ブロック個数カウンタによって計数されたデータから最小ブロックに構成することができるスタート点を決定する最小ブロックグリッド選択手段と、一番左側、一番上方のスタート部分をＮ×Ｎ回移動してスタート点の情報を前記アドレス発生器に送るアドレス発生制御手段を包含して構成する。
【００３２】
以下、本発明の選択的な画素探索を利用したグリッド移動方法および装置の望ましい実施の形態を添附図面を参考にして詳細に説明すると次のとおりである。まず、図１は国際標準傘下機構から一次的に確定したＶＭエンコーダのＶＯＰ符号化部に本発明の形状適応領域分割部２１を構成した実施の形態を示したブロック図である。
図示のように、本発明は、ＶＯＰ形成部１０内に形状適応領域分割部２１を具備して、マクロブロックの横軸および縦軸グリッドスタート点を移動させながらＶＯＰの対象物映像の輪郭線が存在する位置による情報量の減少位置を決定する。前記情報量の減少位置に、対象物映像の輪郭線が存在するマクロブロックの数が最小となる位置を最適の横軸および縦軸グリッドスタート点に決定し、決定した最適の横軸および縦軸グリッドスタート点を出力して形状情報の符号化部１７に入力させる。
したがって、前記形状情報の符号化部１７においては前記形状適応領域分割部２１から出力される最適の横軸および縦軸グリッドスタート点によりマクロブロックを再形成し、対象物の形状情報を符号化してマルチプレクサ１８に送る。
【００３３】
図２は前記図１の形状適応領域分割部２１の一実施の形態を示したブロック図であって、貯臓された映像を入力されるアドレスによって次のブロックに送るフレームメモリ５と、物体をブロック単位に分類したとき一番初めに該当する、すなわち一番左側、一番上方のアドレススタート点から順に発生させて前記フレームメモリ５に送るアドレス発生器２０と、前記フレームメモリ５から入力される映像データを一次元から二次元に構成した後、Ｎ×Ｍブロック単位に区分してブロックの端部画素のみ物体が存在するかを確認する端部画素の探索器３０と、前記端部画素の探索器３０から物体が存在するブロックの個数を計数するブロック個数カウンタ４０と、前記ブロック個数カウンタ４０によって計数されたデータから最小ブロックに構成することができるスタート点を決定する最小ブロックグリッド選択器５０と、一番左側、一番上方のスタート部分をＮ×Ｎ回移動してスタート点情報を前記アドレス発生器２０に送るアドレス発生制御器６０とから構成される。
【００３４】
ここで、前記フレームメモリ５の大きさは映像の大きさよりは大きくなければならないが、例えばＮ×Ｍブロックの大きさが境界外を覆う程度に大きくなければならない。
また、前記アドレス発生器２０は、入力される対象物映像の大きさの情報により横軸の大きさの決定部がマクロブロックの横軸の大きさを決定し、縦軸の大ききの決定部がマクロブロックの縦軸の大ききを決定する。
【００３５】
また、前記ブロック個数カウンタ４０は、クロック信号をカウントして単位領域を区分するブロックカウント手段と、フレームメモリ５から出力される映像の単位領域を前記ブロックカウント手段の出力信号により区分し対象物の形状情報が存在するかの可否を判断する形状情報の存在判断手段と、前記形状情報の存在判断手段の判断信号をカウントして対象物の映像が存在する単位領域の数を出力する領域数の加算手段とから構成される。
ここで、マクロブロックの横軸および縦軸の大きさが同一の場合には一つの大き決定部のみを使用してマクロブロックの大きさを決定しうる。
【００３６】
このような構成を有する本発明は、図３に図示のように、形状や領域情報（Ｓ１の段階）からグリッド位置をＮ×Ｎ回移動し（Ｓ２段階）、スタート点を基準としてＮ×Ｍブロック分割し（Ｓ３段階）、物体が包含されたブロックを探すとき、ブロックの端部画素のみ確認するとかまたは端部においても所定の画素（間）ずつ飛び越しながら画素を確認するとかまたは対角線に画素を確認した後（Ｓ４段階）、ブロック内に物体が存在する最小のブロック数を有するスタート点を決定する（Ｓ５段階）。
【００３７】
前記図３の段階Ｓ１−Ｓ５において、Ｓ２段階はグリッド移動方法に関する段階で、これに対する詳細な内容は本出願人によってＰＣＴ出願（ＰＣＴ／ＫＲ９６／００１０６）および米国出願（０８／６７９，７５８、０８／６７９，３６５、０８／６７９．７６０、０８／６７９，３６６）されている。
このようなグリッド移動方法は、図４乃至図８に詳細に図示されており、図４はグリッド移動方法により情報量の減少位置を探す一実施の形態の過程を示した信号流れ図であって、ここで、Ｓ１６−Ｓ１９の段階がグリッド移動方法に関する内容である。
【００３８】
図５はグリッド移動方法により情報量の減少位置を探す他の実施の形態を示したもので、ここでは、Ｓ３４−Ｓ３６の段階がグリッド移動方法に関する内容である。
図６はグリッド移動方法により情報量の減少位置を探すまた他の実施の形態を示した信号流れ図であって、ここで、Ｓ４４，Ｓ４５の段階がグリッド移動方法に関する内容である。
図７はグリッド移動方法により情報量の減少位置を探すさらに他の実施の形態を示した信号流れ図であって、ここで、Ｓ５４，Ｓ５５の段階とＳ６０，Ｓ６１の段階がグリッド移動方法に関する内容である。
図８はグリッド移動方法により情報量の減少位置を探すさらに他の実施の形態を示した信号流れ図であって、ここで、Ｓ７４，Ｓ７８，Ｓ８０の段階がグリッド移動方法に関する内容である。
【００３９】
本発明において、前記グリッドを移動しながらスタート点を探し、さらにＶＯＰ形成過程で形状適応領域分割をするとき、一つのブロック毎に物体が存在するかを探すための端部の探索方法は前記図３からＳ４段階に該当するもので、図９でみるとき、ブロック内に物体が存在するか探す支点をブロックの端部からのみ確認する。
ここで、上記図９の易合、ブロックの大きさが１６×１６であるとき、ブロック内に物体が存在するか探す支点は最大総６０個になる。
ブロック内に物体が存在すれば、ブロック境界のどこかに連結されているので、演算速度を減少しながら既存の形状適応領域分割で得ることができる符号化の利得を一様に得ることができ、演算時間が実際に約１／４に減少されることが分る。但し、例外的な場合として、ブロックの一番中心に物体があって実際に物体はブロック内に存在するが、ブロックの四角境界に掛からない場合もあるが、この場合は実際に符号化の利得に別の利得を付与できないので無視しても関係ない。
【００４０】
図１０は図９に図示している図面のようにブロック内に物体が存在するかを探すためにブロックの端部をすべて探さないでブロックの端部においても一つの間ずつ飛び越しながらブロック内に物体が存在するかを探す方法を説明するためのもので、例えばブロックの大きさが１６×１６である場合、ブロック内に物体が存在するか探す支点は総３０個になる。
この場合、上記図２１からブロック内に物体を探す場合より演算速度が２倍に迅速になって演算時問が１／８に減少される。
【００４１】
図１１はブロック内に物体が存在するかを探すためにブロックの対角線の方向に一つの間ずつ探す方法を示した図面であって、このときにもブロックの対角線の方向にＮ個の画素（間）ずつ（例えば、一つの画素（間）ずつまたは二つの画素（間）ずつ）飛び越しながら探すことができることは勿論である。
図１２は符号化しようとする所定の対象映像を４等分して個々の四分面に属するブロック毎に他の順に物体が存在するかを探す方法を示したもので、上方の左側部分を第１四分面、上方の右側部分を第２四分面、下方の左側部分を第３四分面、下方の右側部分を第４四分面であると定義したものである。
【００４２】
図１３は図１２の第１四分面に属するブロック内に物体が存在するか探す支点の順序を示したものであって、中央点から一番近い角部からブロック内に物体が存在するかをブロックの端部のみ確認する。すなわち、中央点から最も近い角部である下方の右側部分から図面の番号のようにジグザグ式に物体が存在するかを探していく。
図１４乃至図１６は図１２からそれぞれ第２四分面乃至第４四分面のブロック内に物体が存在するか探すスタート位置と順序を表示したもので、図１３の場合と同様に中央点から一番近い角部分からジグザグ式に物体が存在するかを探していく。
これは映像画面やどの物体からブロック内に物体が存在する確率が高い部分から探すことによって形状適応の領域分割の演算速度を迅速にするためのものである。すなわち、符号化しようとする物体を４等分したとき、一番中心の方に物体が存在する確率が高いので、演算速度を迅速にすることができる。
【００４３】
本発明において、ブロックＮ×Ｍの大きさが大変大きな場合には、別途にブロックを対角線に分類してその境界内に物体が存在するかを探すことができ、またブロックを４等分してその境界からブロック内に物体が存在するか探すことができる。
そして、ブロックの端部を中心としてブロック内に物体が存在するかを探すとき、図１０の実施の形態においては一つの間ずつ飛び越したが、演算速度をなお一層迅速にする必要のある場合には符号化の効率は少し低下しても二つの間以上ずつ飛び越しながらブロック内に物体が存在するかを探すことができる。
また、上述のように本発明は四角形ブロックのみに限定されるものではなく、三角形、六角形の各種の多角形においても適用することができることは勿論である。
【００４４】
【発明の効果】
以上説明したように、本発明は、形状適応領域分割をするに際し、ブロック内の全ての画素を探さないでブロックの端部を中心としてＮブロックずつ飛び越しながらブロック内に物体が存在するかを探すことによって演算速度を迅速にすることができる効果がある。
【図面の簡単な説明】
【図１】  国際標準準傘下器構から一次的に確定したＶＯＰ符号化部に本発明の形状適応の領域分割部を構成した実施の形態を示したブロック図である。
【図２】  前記図１の形状適応の領域分割部の実施の形態を示したブロック図である。
【図３】  本発明の形状適応の領域分割加速装置の動作流れ図である。
【図４】  グリッド移動方法に対する実施の形態を示した動作流れ図である。
【図５】  図４と同様にグリッド移動方法に対する実施の形態を示した動作流れ図である。
【図６】  図４と同様にグリッド移動方法に対する実施の形態を示した動作流れ図である。
【図７】  図４と同様にグリッド移動方法に対する実施の形態を示した動作流れ図である。
【図８】  図４と同様にグリッド移動方法に対する実施の形態を示した動作流れ図である。
【図９】  本発明のブロック内の物体確認時にブロックの端部のみ探すことを示した図面である。
【図１０】  本発明のブロック内の物体確認時にブロックの端部から一つの間ずつ飛び越して探すことを示した図面である。
【図１１】  本発明のブロック内に物体確認時にブロックの対角線によって探すことを示した図面である。
【図１２】  本発明の符号化しようとする物体映像を４等分してそれぞれ１，２，３，４分面によって区分した図面である。
【図１３】  前記図１２からブロックが第１四分面である場合、ブロック内に物体が存在する確率が最も高い順序から探していく過程を説明するための図面である。
【図１４】  前記図１２からブロックが第２四分面である場合、ブロック内に物体が存在する確率が一番高い順序から探していく過程を説明するための図面である。
【図１５】  前記図１２からブロックが第３四分面である場合、ブロック内に物体が存在する確率が一番高い順序から探していく過程を説明するための図面である。
【図１６】  前記図１２からブロックが第４四分面である場合、ブロック内に物体が存在する確率が一番高い順序から探していく過程を説明するための図面である。
【図１７】  一般的なＶＭエンコーダのＶＯＰ符号化部の構成図である。
【図１８】  符号化しようとする対象物体を示した図面である。
【図１９】  前記図１８の物体をマクロブロック単位に拡張した図面である。
【図２０】  前記図１９のＡブロック拡大図である。
【図２１】  従来図２０からブロック内に物体が存在するか全ての画素を探す過程を説明するための図面である。
【符号の説明】
５  フレームメモリ、２１  形状適応の領域分割部、４０  ブロック個数カウンタ、６０  アドレス発生制御器、２０  アドレス発生器、３０  端部画素の探索器、５０  最小ブロックグリッド選択器。
【図１】
0003676550.tif 000002
【図２】
0003676550.tif 000003
【図３】
0003676550.tif 000004
【図４】
0003676550.tif 000005
【図５】
0003676550.tif 000006
【図６】
0003676550.tif 000007
【図７】
0003676550.tif 000008
【図８】
0003676550.tif 000009
【図９】
0003676550.tif 000010
【図１０】
0003676550.tif 000011
【図１１】
0003676550.tif 000012
【図１２】
0003676550.tif 000013
【図１３】
0003676550.tif 000014
【図１４】
0003676550.tif 000015
【図１５】
0003676550.tif 000016
【図１６】
0003676550.tif 000017
【図１７】
0003676550.tif 000018
【図１８】
0003676550.tif 000019
【図１９】
0003676550.tif 000020
【図２０】
0003676550.tif 000021
【図２１】
0003676550.tif 000022