(57)【要約】【課題】デジアニメーション計算仕事量を低減することができるデジアニメーション計算仕事量の圧縮方法を提供する。【解決手段】デジアニメーションの画面を１６Ｘ１６画素行列よりも小さいマイクロ・ブロックに分割して計算し、ＲＡＭにより計算結果を一旦に記憶し、前記計算結果を重複に利用する。【選択図】図３
2006060522.tif 000002
【特許請求の範囲】
【請求項１】
一般のデジアニメーションの連続する二枚の画面における同様な映像は運動概算によってその運動関係を決めるが、通常に画面が１６Ｘ１６の２５６個の画素行列を一マクロ・ブロックとして、画面を複数のマクロ・ブロックに分割すると共に、１６Ｘ１６画素行列よりも大きくて適当な捜索範囲がマクロ・ブロックに定義されることにより、各マクロ・ブロックが付近の適当な捜索範囲内に、次の画面と関連する最高な運動ベクトルを見出し、
計算仕事量を低減するために、デジアニメーションの画面を１６Ｘ１６よりも小さい画素行列に分割してマイクロ・ブロックになり、各マイクロ・ブロックの総和を別々に計算して記憶した後、二マクロ・ブロックの対応する画素値の絶対相違値の和（ＭＡＤ計算値と称し）は、二マクロ・ブロックのそれぞれの画素値の和の絶対相違値（概略計算値と称し）よりも大きい又は同様であり、まず、マクロ・ブロックの適当な捜索範囲内に何れか一点のＭＡＤ計算値を算出して暫定最小参考値として記憶し、次に、記憶したマイクロ・ブロックの画素の総和を取出して、マクロ・ブロックの適当な捜索範囲内の他の点の概略計算値を算出し、概略計算値が暫定最小参考値よりも大きい又は同様である場合には、前記暫定最小参考値を保留し、概略計算値が暫定最小参考値よりも小さい場合には、他点のＭＡＤ計算値を計算し、また、前記他点のＭＡＤ計算値が暫定最小参考値よりも大きい又は同様である場合には、前記暫定最小参考値を保留し、前記他点のＭＡＤ計算値が暫定最小参考値よりも小さい場合には、前記他点のＭＡＤ計算値が暫定最小参考値を取って代わることを特徴とする、デジアニメーション計算仕事量の圧縮方法。
【請求項２】
前記マイクロ・ブロックは２Ｘ２画素行列であることを特徴とする、請求項１に記載のデジアニメーション計算仕事量の圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジアニメーション計算仕事量の圧縮方法に係り、特にデジアニメーションの画面を１６Ｘ１６画素行列よりも小さいマイクロ・ブロックに分割して計算し、ＲＡＭにより計算結果を一旦に記憶し、前記計算結果を重複に利用することにより、デジアニメーション計算仕事量を低減するデジアニメーション計算仕事量の圧縮方法に関する方法である。
【背景技術】
【０００２】
目下、一般のパソコンと、テレビと、携帯電話となどのディスプレーのデジアニメーション処理は、メモリ容量を低減し、又はデータ伝送の速度を上げるために、デジアニメーション圧縮技術が使用される。デジアニメーション圧縮技術において、よく使用される規格は、ＭＰＥＧ−２と、ＭＰＥＧ−４と、ＡＶＳと、Ｈ.２６４となどであり、これらは全て運動概算（motion estimation）方法によりデータを圧縮する。一般の連続アニメーションは、画面の流れを順調にするために、一秒ごと２０〜３０枚の画面を提供することが必要であり、連続の二枚の画面における同様な映像が運動概算方法によりその運動関係を決めることが必要である。
【０００３】
運動概算方法の一つは、画面を１６Ｘ１６の２５６個の画素行列を一マクロ・ブロック（Macro-Block,MB）として分割して、各マクロ・ブロックと前の画面との関連する最高運動ベクトル（motion
vector）を見出す。図１を参照する。図１（ａ）と図１（ｂ）は連続の二枚の画面である。しかしながら、図１（ｂ）の画面を伝送（又は記憶）するときに、汽車の運動ベクトル（破線矢印に示すように）を伝送するだけでよく、図１（ａ）において汽車に隠された背景画面を補足し、本来の汽車と背景画面データとを合せば、図１（ｂ）になる。この方法によれば、伝送速度が大幅に向上するが（又は、メモリ容量を低減し）、計算の複雑度が著しく増加する。
【０００４】
図１（ａ）におけるあるマクロ・ブロックの運動ベクトルを計算するときには、マクロ・ブロックにおける各画素を図１（ｂ）におけるあるマクロ・ブロックの各対応する画素から引いて（Full Search,全捜索）、２５６個の絶対相違値を加算して一「総合絶対相違値」になる。それで、図１（ｂ）における全ての比較点の周囲のマクロ・ブロックを順序に計算して多数の総合絶対相違値が得られ、総合絶対相違値が最小である比較点の位置は求められるものであり、それと比較点の位置との相違は運動ベクトルである。計算仕事量を低減するために、より小さい画面の捜索範囲（Searching
Range）を設定することが一般のやり方であり、前記捜索範囲において捜索した総合絶対相違値が予定設定値よりも小さいであれば、当該比較点の位置はいわゆる運動ベクトルである。
【０００５】
図２を参照する。従来の全捜索方法の運動概算は、捜索範囲が３２Ｘ３２画素であり、マクロ・ブロックが１６Ｘ１６画素であれば、各マクロ・ブロックに対いて運動ベクトルを求める場合には、マクロ・ブロック自身と他の全てのマクロ・ブロックと計算することが必要であるので、全部１７Ｘ１７＝２８９回のマクロ・ブロック比較（マクロ・ブロックが捜索範囲内に移動すると、１７Ｘ１７の範囲だけあり、マクロ・ブロックが捜索範囲を超えることが許さなく）がする。毎回の比較は「最小総和絶対相違値」（ＭＡＤ）の方法により計算し、一マクロ・ブロックの画素値が関連するマクロ・ブロックの画素値から引いて絶対値を取って加算し、全部に７６７回の計算が必要である（引算２５６回、絶対値取り２５６回、加算２５５回、全部に２５６＋２５６＋２５５＝７６７回）。マクロ・ブロック比較は２８９回あり、毎回の比較は７６７回計算が必要なので、２８９Ｘ７６７＝２２１６６３回の計算で一マクロ・ブロックの同一捜索範囲に対する捜索が始めて完成でき、運動ベクトルを見出す。隣接のマクロ・ブロックも２２１６６３回の計算が必要である。
【０００６】
一画面は７２０Ｘ４８０の映像である場合には、その画面が１３５０個のマクロ・ブロックに分割することができる。各マクロ・ブロックは緊密に連接するが、重なる部分がなく、捜索範囲が隣接する捜索範囲と大量に重なるが、各マクロ・ブロックが全て新たに計算することが必要である。このような画面の運動ベクトルを概算すれば、総和計算仕事量は２．９９Ｘ１０８回（１３５０Ｘ２２１６６３）である。一般の連続アニメーションは一秒ごと２２枚の画面を提供することが必要なので、一秒ごとの総和計算仕事量は６．５８Ｘ１０９回（２２Ｘ２．９９Ｘ１０８）である。
【０００７】
だから、全捜索方法の計算の複雑度が高すぎるので、システムがより高いタイミングとより大きいデジ信号プロセッサーとを採用し、結果として電力消耗が極めて大きい。携帯式電子製品の電池が耐えられなく、且つコストも低減できない。だから、多数の新方法は開発され、それらの新方法は、比較点数低減法と、計算回数低減法との二種類に分けられる。計算仕事量を低減するために、上記二種類の方法は同時に使用することができる。
【０００８】
比較点数低減法は、色々あり、よく採用されるのは三ステップ捜索（Three
Step Search, TSS）と四ステップ捜索（Four Step Search, FSS）などである。その概要は設定する捜索範囲において複数点を見出して、最小のＭＡＤ値を選び、この最小のＭＡＤ値の付近に、更に区域化計算をする。
【０００９】
計算回数低減法はより少なく、よく使用される公式は、
SUM（ABS（-b））≧ABS（SUM（a）-SUM（b））であって、
【００１０】
aとbとはそれぞれ二マクロ・ブロックの各点の画素値を代表する。上記公式の意義は、二マクロ・ブロックの対応する画素値の絶対相違値の和（ＭＡＤ計算値と称し）は、二マクロ・ブロックのそれぞれの画素値の和の絶対相違値（概略計算値と称し）よりも大きい又は同様である。
【００１１】
上記公式の性質により、捜索範囲の中から何れかの比較点を取り出して、ＭＡＤ計算をして（上記公式の左側の計算）、暫定最小参考値とした後、第二の比較点を選択して上記公式の右側の計算をする（概略計算と称し）。前記暫定最小参考値は捜索範囲の中の最小値であれば、第二比較点のＭＡＤ計算値が前記暫定最小参考値よりも大きいはずである。しかしながら、第二比較点の概略計算値は前記暫定最小参考値よりも大きいであれば、上記公式により、第二比較点のＭＡＤ計算値は、第二比較点の概略計算値よりも大きい又は同様であるので、きっと前記暫定最小参考値よりも大きいので、前記暫定最小参考値を継続に保留する。第二比較点の概略計算値は前記暫定最小参考値よりも小さいであれば、第二比較点のＭＡＤ計算値がきっと前記暫定最小参考値よりも小さいとは言えずので、第二比較点に対してＭＡＤ計算をして（上記公式の左側の計算）、暫定最小参考値と比較し、第二比較点のＭＡＤ計算値が暫定最小参考値よりも小さいであれば、第二比較点のＭＡＤ計算値を今後の暫定最小参考値とする。
【００１２】
捜索範囲内の２８９個の点が比較を完成するまでに、上記ステップを重複し、毎回の比較は暫定最小参考値をメモリに記憶する。
【００１３】
図２を参照する。上記公式の性質により、捜索範囲が３２Ｘ３２画素であり、マクロ・ブロックが１６Ｘ１６画素であれば、左上の角部の第一捜索点のＭＡＤ計算値が丁度最小値と仮定する。捜索範囲において２８９個（１７Ｘ１７）の比較点があり、第一比較点のＭＡＤ計算方法は、従来の全捜索と同様であり、７６７回の計算が必要である。その後の２８８個の比較点は上記公式の右側の概略計算を採用し、毎回の比較が２５５回の加算が必要でありSUM（b）を取って、SUM（a）と引算をして絶対値を取り、全部に２５７回の計算が必要である。SUM（a）は、第一比較点を計算した後（２５５回の加算が必要）、その後の２８８個の比較点に使用である。だから、第一捜索点のＭＡＤ計算値が最小値であれば、一マクロ・ブロックの全捜索範囲の比較を完成すると、全部に７５３２６回の計算が必要であり（第一比較点７６７回、SUM（a）が第一比較点で２５５回の加算が必要、その他の２８８個の比較点がそれぞれ２５７回が必要、暫定最小値との比較が２８８回、全部に７６７＋２５５＋２５７Ｘ２８８＋２８８＝７５３２６）、上記の２２１６６３回の計算よりも大幅に低くなる。
【００１４】
だから、上記公式により計算仕事量が大幅に低減できることが分かった。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の目的は、デジアニメーションの画面を１６Ｘ１６画素行列よりも小さいマイクロ・ブロックに分割して計算し、ＲＡＭにより計算結果を一旦に記憶し、前記計算結果を重複に利用することにより、デジアニメーション計算仕事量を低減するデジアニメーション計算仕事量の圧縮方法を提供する。
【課題を解決するための手段】
【００１６】
上記目的を達成するためになされた本願の発明は、一般のデジアニメーションの連続する二枚の画面における同様な映像は運動概算によってその運動関係を決めるが、通常に画面が１６Ｘ１６の２５６個の画素行列を一マクロ・ブロックとして、画面を複数のマクロ・ブロックに分割すると共に、１６Ｘ１６画素行列よりも大きくて適当な捜索範囲がマクロ・ブロックに定義されることにより、各マクロ・ブロックが付近の適当な捜索範囲内に、次の画面と関連する最高な運動ベクトルを見出し、計算仕事量を低減するために、デジアニメーションの画面を１６Ｘ１６よりも小さい画素行列に分割してマイクロ・ブロックになり、各マイクロ・ブロックの総和を別々に計算して記憶した後、二マクロ・ブロックの対応する画素値の絶対相違値の和（ＭＡＤ計算値と称し）は、二マクロ・ブロックのそれぞれの画素値の和の絶対相違値（概略計算値と称し）よりも大きい又は同様であり、まず、マクロ・ブロックの適当な捜索範囲内に何れか一点のＭＡＤ計算値を算出して暫定最小参考値として記憶し、次に、記憶したマイクロ・ブロックの画素の総和を取出して、マクロ・ブロックの適当な捜索範囲内の他の点の概略計算値を算出し、概略計算値が暫定最小参考値よりも大きい又は同様である場合には、前記暫定最小参考値を保留し、概略計算値が暫定最小参考値よりも小さい場合には、他点のＭＡＤ計算値を計算し、また、前記他点のＭＡＤ計算値が暫定最小参考値よりも大きい又は同様である場合には、前記暫定最小参考値を保留し、前記他点のＭＡＤ計算値が暫定最小参考値よりも小さい場合には、前記他点のＭＡＤ計算値が暫定最小参考値を取って代わることを特徴とするデジアニメーション計算仕事量の圧縮方法であることを要旨としている。
【００１７】
本願の発明では、前記マイクロ・ブロックは２Ｘ２画素行列であることを特徴とする請求項１に記載のデジアニメーション計算仕事量の圧縮方法であることを要旨としている。
【発明の効果】
【００１８】
本発明によれば、デジアニメーションの画面を１６Ｘ１６画素行列よりも小さいマイクロ・ブロックに分割して計算し、ＲＡＭにより計算結果を一旦に記憶し、前記計算結果を重複に利用することにより、デジアニメーション計算仕事量を低減できる。
【発明を実施するための最良の形態】
【００１９】
以下、添付図面を参照して本発明の好適な実施の形態を詳細に説明する。
【００２０】
まず、図３を参照する。図３は本発明に係るデジ信号処理ユニット（ＤＳＰ/ＡＬＵ）の概略図である。図面におけるＲＡＭは、ＤＲＡＭ又はＳＲＡＭであり、それらは成熟したデジタル集積回路なので、製造上には問題ない。
【００２１】
従来の全捜索方法による運動概算は、捜索範囲が３２Ｘ３２画素であり、マクロ・ブロックが１６Ｘ１６画素であれば、各マクロ・ブロックに対いて運動ベクトルを求める場合には、２２１６６３回の計算が必要である。計算回数低減法の上記公式によれば、７５３２６回の計算が必要である。
【００２２】
本発明の計算方法は、図４に示すように、全ての条件が上記と同様であり、捜索範囲が３２Ｘ３２画素であり、マクロ・ブロックが１６Ｘ１６画素であるが、本発明は３２Ｘ３２画素をもっと２Ｘ２のマイクロ・ブロックに分割し、全部に２５６個のマイクロ・ブロックがある。
【００２３】
左上の角部の第一比較点Ｐ1,1での比較値が最小値と仮定し、第一比較点Ｐ1,1と自身の比較がＭＡＤ計算を使用して、この捜索範囲の「暫定最小参考値」を取るために、７６７回の計算が必要である（引算２５６＝１６Ｘ１６回、絶対値取り２５６回、加算２５５回、７６７＝２５６＋２５６＋２５５であり、上記全捜索法と同様）。
【００２４】
Ｐ1,1点と全ての各点との比較は、上記公式の右側により概略計算をする。だが、本発明の概略計算は２Ｘ２画素のマイクロ・ブロックをユニットとして計算し、各マイクロ・ブロックが４個の画素を有し、まず、この４個の画素値を加算し、三回の計算が必要であり、且つ各マイクロ・ブロックの計算結果を図３のＤＳＰ/ＡＬＵのData Memory（ＲＡＭ）に記憶して、マクロ・ブロックの１６Ｘ１６画素からの６４個のマイクロ・ブロックの数値を（６３回に）加算し、全部２５５回（加算３Ｘ６４＋６３回）に計算して６４個のマイクロ・ブロックの総和を取る。Ｐ1,1点は概略計算法により自身の６４個のマイクロ・ブロックの総和を取るために２５５回の計算が必要であり、且つ計算が一回だけでよく、その計算結果を記憶して今後の使用に提供する。他の点の６４個のマイクロ・ブロックの総和を取るために、それぞれ２５５回（加算３Ｘ６４＋６３回）の計算が必要であり、そしてＰ1,1点自身の６４個のマイクロ・ブロックの総和と引算をして絶対値を取ることにより、上記公式の右側の概略計算値が得られる。
【００２５】
メモリ処理のロード（load）と記憶（store）とは、一般の計算命令と平行に処理されるので、下記の計算式では一旦に省略される。
【００２６】
第一比較点Ｐ1,1は自身の６４個のマイクロ・ブロックの総和を取るために２５５回（加算３Ｘ６４＋６３回）の計算が必要であり、第二比較点Ｐ1,2は自身の６４個のマイクロ・ブロックの総和を取るためにも２５５回の計算が必要である。だが、一列目の第３，４〜１７個の比較点Ｐ1,3〜Ｐ1,17は８７回（３Ｘ８＋６３）の計算だけが必要であり、その原因は、８個だけのマイクロ・ブロックが新たに計算することが必要であり、その他の５６個のマイクロ・ブロックはＰ1,1での計算中にメモリに記憶した。二列目の比較点（Ｐ2,3〜Ｐ2,17）が６４個のマイクロ・ブロックの総和を取るための計算が一列目と同様であり、図５を参照する。三列目の第一、二比較点Ｐ3,1，Ｐ3,2（図６を参照）では８７回（３Ｘ８＋６３）の計算だけが必要であり、その原因は、８個だけのマイクロ・ブロックが新たに計算することが必要であり、その他の５６個のマイクロ・ブロックはＰ1,1，Ｐ1,2での計算中にメモリに記憶した。三列目の第３，４〜１７個の比較点Ｐ3,3〜Ｐ3,17は６６回の計算だけが必要であり、その原因は、１個だけのマイクロ・ブロックが新たに計算することが必要である（加算３回、６４個のマイクロ・ブロックの計算結果の加算が６３回、全部に６６回）。４〜１７列目の比較点（Ｐ4,X〜Ｐ17,X）の計算仕事量は三列目と同様であり、図６を参照する。
【００２７】
概略計算結果が記憶した「暫定最小参考値」よりも小さい場合だけには、当該点の微細ＭＡＤ計算をし、微細ＭＡＤ計算結果は「暫定最小参考値」よりも小さい場合には、微細ＭＡＤ計算結果が本来の「暫定最小参考値」を取り代わってメモリに記憶する。概略計算結果が記憶した「暫定最小参考値」よりも大きい場合には、この比較点が目標ではないので、次の比較点の概略計算を実施する。２８９個の比較点の計算が全て完成するまでに、これらのステップを重複する。（第一比較点が最高値と仮定するので、上記計算が必要なＭＡＤ計算仕事量を省略する可能性があるが、現実中に第一捜索点は最高値になる確率が極めて高い方法がある。その討論がここで省略する。）
【００２８】
上記方法を纏めれば、捜索範囲が３２Ｘ３２画素であり、マクロ・ブロックが１６Ｘ１６画素であれば、各マクロ・ブロックに対いて運動ベクトルを求める場合には、２２７２１回の計算が必要である。それは、
【００２９】
Ｐ1,1自身のＭＡＤ計算は７６７回であり、
Ｐ1,1が自身の６４個のマイクロ・ブロックの総和を取るために、２５５回の計算が必要であり、
Ｐ1,1とＰ1,2との比較が２５５＋１＋１＋１回の計算（引算して絶対値を取って比較し）が必要であり、
Ｐ1,1とＰ2,1との比較が２５５＋１＋１＋１回の計算が必要であり、
Ｐ1,1とＰ2,2との比較が２５５＋１＋１＋１回の計算が必要であり、
Ｐ1,1とＰ1,3〜Ｐ1,17との比較がそれぞれ８７＋１＋１＋１回の計算が必要であり、
Ｐ1,1とＰ2,3〜Ｐ2,17との比較がそれぞれ８７＋１＋１＋１回の計算が必要であり、
Ｐ1,1とＰ3,1〜Ｐ17,1との比較がそれぞれ８７＋１＋１＋１回の計算が必要であり、
Ｐ1,1とＰ3,2〜Ｐ17,2との比較がそれぞれ８７＋１＋１＋１回の計算が必要であり、
Ｐ1,1とその他の各点との比較がそれぞれ６６＋１＋１＋１回の計算が必要であり、
全部に、７６７＋２５５Ｘ４＋９＋（９０Ｘ１５）Ｘ４＋（６９Ｘ１５Ｘ１５）＝２２７２１回である。
【００３０】
７２０Ｘ４８０画素を有する画面は、１３５０個のマクロ・ブロックに分割することができる。各マクロ・ブロックは緊密に連接するが、重ならなく、しかしながら、捜索範囲３２Ｘ３２の中のマクロ・ブロックの大きさは１６Ｘ１６であり、各マクロ・ブロックが隣接するマクロ・ブロックの捜索範囲と大量に重なるので、マイクロ・ブロックの計算結果は各マクロ・ブロックに重複に使用できる。一画面の運動概算を完成すれば、総計算仕事量は３．０７Ｘ１０７回（１３５０Ｘ２２７２１）よりも少ないである。一秒ごとに２２枚の画面を提供すれば、一秒ごとの計算仕事量は６．７５Ｘ１０８回（３．０７Ｘ１０７Ｘ２２回）よりも少ないである。総計算仕事量は上記計算回数低減法公式による計算仕事量の３０．２％だけである。
【００３１】
ＭＰＥＧ−２と、ＭＰＥＧ−４と、ＡＶＳと、Ｈ.２６４となどの規格によれば、全てのマクロ・ブロックが緊密に連接するので、その捜索範囲が全て重なる。この特性を利用すれば、分解度が増加するときには、各映像の最上端縁ともっとも左側とだけでの計算仕事量がより大きく、その他の各マクロ・ブロックは２万回だけの計算が必要である。だから、本発明の新方法によれば、計算仕事量を更に圧縮することができる。
【００３２】
本発明の精神と範囲とは、特許請求範囲に限定され、上記の実施例に限定されることではない。
【図面の簡単な説明】
【００３３】
【図１】運動ベクトルの概略図である。
【図２】従来の全捜索運動概算の概略図である。
【図３】本発明に係るデジ信号処理ユニット（ＤＳＰ/ＡＬＵ）の概略図である。
【図４】本発明に係る全捜索運動概算の一行目の複雑度を示す概略図である。
【図５】本発明に係る全捜索運動概算の二行目の複雑度を示す概略図である。
【図６】本発明に係る全捜索運動概算の三行目及びその後の複雑度を示す概略図である。
【図１】
2006060522.tif 000003
【図２】
2006060522.tif 000004
【図３】
2006060522.tif 000005
【図４】
2006060522.tif 000006
【図５】
2006060522.tif 000007
【図６】
2006060522.tif 000008