(57)【特許請求の範囲】
【請求項１】
MPEGを用いて画像データを圧縮する情報処理装置において、
前記画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出手段と、
前記第１のブロックの各画素の画素値の和と、前記抽出手段により抽出された前記第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算手段と、
前記第１の演算手段により演算された前記第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定手段と、
前記第１の演算手段により演算された前記第１の値と、前記第２の値とを比較する第１の比較手段と、
前記第１の比較手段により、前記第１の値が、前記第２の値より小さいと判断された場合、前記第１のブロックの各画素と、前記第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算手段と、
前記第２の値と、前記第２の演算手段により演算された前記第３の値を比較し、前記第３の値の方が小さかった場合、前記第２の値として、前記第３の値を再設定する第２の設定手段と
を備え、
前記抽出手段は、予め定められた探索範囲内の全ての前記第２のブロックを順次抽出する
ことを特徴とする情報処理装置。
【請求項２】
前記抽出手段は、前記探索範囲内において、前記第１のブロックを中心としたらせん状に、前記第２のブロックを抽出する位置を移動する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記抽出手段により抽出された全ての前記第２のブロックに対する処理の終了後の前記第２の値を用いて、前記第１のブロックのブロックタイプを判定するか、もしくは、前記第１のブロックの符号化を実行するために用いる動きベクトルを演算して、その結果を出力する出力手段
を更に備えることを特徴とする請求項１に記載の情報処理装置。
【請求項４】
MPEGを用いて画像データを圧縮する情報処理装置の情報処理方法において、
前記画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出ステップと、
前記第１のブロックの各画素の画素値の和と、前記抽出ステップの処理により抽出された前記第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算ステップと、
前記第１の演算ステップの処理により演算された前記第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定ステップと、
前記第１の演算ステップの処理により演算された前記第１の値と、前記第２の値とを比較する第１の比較ステップと、
前記第１の比較ステップの処理により、前記第１の値が、前記第２の値より小さいと判断された場合、前記第１のブロックの各画素と、前記第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算ステップと、
前記第２の値と、前記第２の演算ステップの処理により演算された前記第３の値を比較し、前記第３の値の方が小さかった場合、前記第２の値として、前記第３の値を再設定する第２の設定ステップと
を含み、
前記抽出ステップの処理では、予め定められた探索範囲内の全ての前記第２のブロックを順次抽出する
ことを特徴とする情報処理方法。
【請求項５】
MPEGを用いて画像データを圧縮する情報処理装置用のプログラムであって、
前記画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出ステップと、
前記第１のブロックの各画素の画素値の和と、前記抽出ステップの処理により抽出された前記第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算ステップと、
前記第１の演算ステップの処理により演算された前記第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定ステップと、
前記第１の演算ステップの処理により演算された前記第１の値と、前記第２の値とを比較する第１の比較ステップと、
前記第１の比較ステップの処理により、前記第１の値が、前記第２の値より小さいと判断された場合、前記第１のブロックの各画素と、前記第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算ステップと、
前記第２の値と、前記第２の演算ステップの処理により演算された前記第３の値を比較し、前記第３の値の方が小さかった場合、前記第２の値として、前記第３の値を再設定する第２の設定ステップと
を含み、
前記抽出ステップの処理では、予め定められた探索範囲内の全ての前記第２のブロックを順次抽出する
ことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項６】
MPEGを用いて画像データを圧縮する情報処理装置を制御するコンピュータが実行可能なプログラムであって、
前記画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出ステップと、
前記第１のブロックの各画素の画素値の和と、前記抽出ステップの処理により抽出された前記第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算ステップと、
前記第１の演算ステップの処理により演算された前記第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定ステップと、
前記第１の演算ステップの処理により演算された前記第１の値と、前記第２の値とを比較する第１の比較ステップと、
前記第１の比較ステップの処理により、前記第１の値が、前記第２の値より小さいと判断された場合、前記第１のブロックの各画素と、前記第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算ステップと、
前記第２の値と、前記第２の演算ステップの処理により演算された前記第３の値を比較し、前記第３の値の方が小さかった場合、前記第２の値として、前記第３の値を再設定する第２の設定ステップと
を含み、
前記抽出ステップの処理では、予め定められた探索範囲内の全ての前記第２のブロックを順次抽出する
ことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報処理装置および情報処理方法、記録媒体、並びにプログラムに関し、特に、MPEGによって動画像データを圧縮する場合に用いて好適な情報処理装置および情報処理方法、記録媒体、並びにプログラムに関する。
【０００２】
【従来の技術】
デジタル動画像データを圧縮する技術として、MPEG（Moving Picture Experts Group）が広く用いられている。なお、MPEGには動画像データ圧縮とともに、音声データの圧縮も含まれる。MPEGは、離散コサイン変換（DCT：Discrete Cosine Transform）、動き予測、および圧縮効率を高めるためのインターフレーム符号化を圧縮方法として利用している。すなわち、MPEGを用いてデジタル動画像データを圧縮する場合、基本的には、動画像の１コマ目のデータをもとに、２コマ目はそれと違う部分だけ、３コマ目は２コマ目と違う部分だけと、コマ（フレーム）の間の差分を記録することで圧縮を実現する。
【０００３】
Video−CDなどに使われているMPEG1は、H.261（電気通信サービス事業者が中心となって定めた動画圧縮技術）をベースに標準化されている。MPEG1においては、画像内での物体の動く方向を予測し、そのベクトルだけを保存するなどの処理により、データを圧縮している。MPEG1は、CD−ROMなどの蓄積メディアにおける保存、もしくは再生処理を考慮したものであり、その再生品質はVTR再生並みである。更に、放送メディアでの使用を考慮し、HDTVなみの再生品質をもつ、MPEG2も制定されている。
【０００４】
MPEG4は、10kbps乃至2Mbpsでの動画符号化技術である。MPEG4は、MPEG1およびMPEG2と同じ基礎技術を圧縮方法として利用している。しかしながら、MPEG1およびMPEG2が、キーフレーム画像で変化した部分のみを分解していくのに対して、MPEG4では、フレームの画像をオブジェクトに分解（すなわち、MPEG4では、映像を構成する要素を、例えば、背景、人物、建物などに分解）し、それぞれのオブジェクトに応じて差分を記録する。
【０００５】
MPEG4では、符号化すべきVOP（Video Object Plane）を含むようなｎ×ｎ画素からなる画素ブロックを設定し、探索範囲内の参照画像にマッチングして、その画素の差分の絶対値和ＡＤ（absolute difference ）を求め、ＡＤが最小となるときの移動量を動きベクトルMV（Motion Vector）として検出する動き探索によって符号化を行っている。そして、マクロブロック毎に動き補償が行われると同時に、各マクロブロックのモード情報（VOPの内側であるか否か、動き補償の適用が可であるか否かなど）が決定される。そして、その後に、マクロブロックのサイズ変換が行なわれる。また、形状情報の動き補償においては、形状情報そのものから得られるMVと、テクスチャ情報から得られる通常のMVの双方が考慮される。
【０００６】
【発明が解決しようとする課題】
上述した動き探索処理は、MPEG4のみならず、MPEG全体の処理において、最も時間の掛かる処理である。従って、動き探索の高速化あるいは処理量の削減は、例えば、MPEG4において、実時間における動画の符号化を可能とするための、非常に重要な課題である。
【０００７】
本発明はこのような状況に鑑みてなされたものであり、MPEGによる動画圧縮時の計算量を削減することができるようにするものである。
【０００８】
【課題を解決するための手段】
本発明の情報処理装置は、画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出手段と、第１のブロックの各画素の画素値の和と、抽出手段により抽出された第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算手段と、第１の演算手段により演算された第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定手段と、第１の演算手段により演算された第１の値と、第２の値とを比較する第１の比較手段と、第１の比較手段により、第１の値が、第２の値より小さいと判断された場合、第１のブロックの各画素と、第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算手段と、第２の値と、第２の演算手段により演算された第３の値を比較し、第３の値の方が小さかった場合、第２の値として、第３の値を再設定する第２の設定手段とを備え、抽出手段は、予め定められた探索範囲内の全ての第２のブロックを順次抽出することを特徴とする。
【０００９】
抽出手段には、探索範囲内において、第１のブロックを中心としたらせん状に、第２のブロックを抽出する位置を移動させるようにすることができる。
【００１１】
抽出手段により抽出された全ての第２のブロックに対する処理の終了後の第２の値を用いて、第１のブロックのブロックタイプを判定するか、もしくは、第１のブロックの符号化を実行するために用いる動きベクトルを演算して、その結果を出力する出力手段を更に備えさせるようにすることができる。
【００１２】
本発明の情報処理方法は、画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出ステップと、第１のブロックの各画素の画素値の和と、抽出ステップの処理により抽出された第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算ステップと、第１の演算ステップの処理により演算された第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定ステップと、第１の演算ステップの処理により演算された第１の値と、第２の値とを比較する第１の比較ステップと、第１の比較ステップの処理により、第１の値が、第２の値より小さいと判断された場合、第１のブロックの各画素と、第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算ステップと、第２の値と、第２の演算ステップの処理により演算された第３の値を比較し、第３の値の方が小さかった場合、第２の値として、第３の値を再設定する第２の設定ステップとを含み、抽出ステップの処理では、予め定められた探索範囲内の全ての第２のブロックを順次抽出することを特徴とする。
【００１３】
本発明の記録媒体に記録されているプログラムは、画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出ステップと、第１のブロックの各画素の画素値の和と、抽出ステップの処理により抽出された第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算ステップと、第１の演算ステップの処理により演算された第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定ステップと、第１の演算ステップの処理により演算された第１の値と、第２の値とを比較する第１の比較ステップと、第１の比較ステップの処理により、第１の値が、第２の値より小さいと判断された場合、第１のブロックの各画素と、第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算ステップと、第２の値と、第２の演算ステップの処理により演算された第３の値を比較し、第３の値の方が小さかった場合、第２の値として、第３の値を再設定する第２の設定ステップとを含み、抽出ステップの処理では、予め定められた探索範囲内の全ての第２のブロックを順次抽出することを特徴とする。
【００１４】
本発明のプログラムは、画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックを抽出する抽出ステップと、第１のブロックの各画素の画素値の和と、抽出ステップの処理により抽出された第２のブロックの各画素の画素値の和との差の絶対値である第１の値を演算する第１の演算ステップと、第１の演算ステップの処理により演算された第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、小さいものを設定する第１の設定ステップと、第１の演算ステップの処理により演算された第１の値と、第２の値とを比較する第１の比較ステップと、第１の比較ステップの処理により、第１の値が、第２の値より小さいと判断された場合、第１のブロックの各画素と、第２のブロックの各画素の差分の絶対値和である第３の値を演算する第２の演算ステップと、第２の値と、第２の演算ステップの処理により演算された第３の値を比較し、第３の値の方が小さかった場合、第２の値として、第３の値を再設定する第２の設定ステップとを含み、抽出ステップの処理では、予め定められた探索範囲内の全ての第２のブロックを順次抽出することを特徴とする。
【００１５】
本発明の情報処理装置および情報処理方法、並びにプログラムにおいては、画像データのうちの所定の数の画素からなる第１のブロックに対する参照ブロックである第２のブロックが抽出され、第１のブロックの各画素の画素値の和と、第２のブロックの各画素の画素値の和との差の絶対値である第１の値が演算され、第１の値と比較する第２の値の初期値として、動き補償の有無を判断するための第１の閾値と、前記第１のブロックが参照ブロックを用いて符号化するブロックであるか否かを判断するための第２の閾値とのうち、いずれか小さいものが設定され、第１の値と、第２の値とが比較され、第１の値が、第２の値より小さいと判断された場合、第１のブロックの各画素と、第２のブロックの各画素の差分の絶対値和である第３の値が演算され、第２の値と、第３の値が比較されて、第３の値の方が小さかった場合、第２の値として、第３の値が再設定され、予め定められた探索範囲内の全ての第２のブロックが順次抽出される。
【００１６】
【発明の実施の形態】
以下、図を参照して、本発明の実施の形態について説明する。
【００１７】
例えば、インターネットや電話回線網などを介して、情報を送受信することが可能なパーソナルコンピュータは、その内部に保存されている動画像データを、MPEG4を用いて圧縮し、例えば、携帯型電話機や、ＰＤＡ、あるいは、他のパーソナルコンピュータなどに送信することができる。
【００１８】
図1は、パーソナルコンピュータ1の構成を示すブロック図である。
【００１９】
ＣＰＵ（Central Processing Unit）１１は、入出力インターフェース１２および内部バス１３を介して、ユーザが、入力部１４を用いて入力した各種指令に対応する信号や、ネットワークインターフェース２０を介して、他の装置から入力された信号を受け、入力された信号に基づいた各種処理を実行する。ＲＯＭ（Read Only Memory）１５は、ＣＰＵ１１が使用するプログラムや演算用のパラメータのうちの基本的に固定のデータを格納する。ＲＡＭ（Random Access Memory）１６は、ＣＰＵ１１の実行において使用するプログラムや、その実行において適宜変化するパラメータを格納する。ＣＰＵ１１、ＲＯＭ１５、およびＲＡＭ１６は、内部バス１３により相互に接続されている。
【００２０】
内部バス１３は、入出力インターフェース１２とも接続されている。入力部１４は、例えば、キーボード、タッチパッド、ジョグダイヤル、あるいはマウスなどからなり、ユーザがＣＰＵ１１に各種の指令を入力するとき操作される。表示部１７は、例えば、ＣＲＴ（Cathode Ray Tube）や液晶表示装置などで構成され、各種情報をテキスト、あるいはイメージなどで表示する。
【００２１】
ＨＤＤ（hard disk drive）１８は、ハードディスクを駆動し、それらにＣＰＵ１１によって実行するプログラムや情報を記録または再生させる。ドライブ１９には、必要に応じて磁気ディスク２１、光ディスク２２、光磁気ディスク２３、あるいは半導体メモリ２４が装着され、データの授受を行う。
【００２２】
ネットワークインターフェース２０は、ネットワークや他の装置などと接続され、情報の授受を行う。
【００２３】
これらの入力部１４乃至ネットワークインターフェース２０は、入出力インターフェース１２および内部バス１３を介してＣＰＵ１１に接続されている。
【００２４】
ＨＤＤ18に保存されている動画像を、例えば、MPEG4によって符号化する場合、ＣＰＵ１１は、MPEG4の動き探索処理として、図２のように、入力された画像（カレント画像）を、１６×１６画素のマクロブロック（MB（Macro Block））に分割し、カレント画像に対して指定された探索範囲内（ここでは、Ｓ×Ｓ画素の範囲内）に、参照画像とするマクロブロックのマッチング位置を動かしながら、次に示す式（１）の演算を行って、カレントマクロブロックと、参照マクロブロックとの画素の差分の絶対値和ＡＤの値を求める。
【００２５】
【数１】
0003968774.tif 000002
0003968774.tif 000003
ただし、式（１）において、c（ｉ，ｊ）はカレントマクロブロックの画素（ｉ，ｊ）における画素値であり、r（ｉ，ｊ）は、参照マクロブロックの画素（ｉ，ｊ）における画素値であるものとする。
【００２６】
そして、ＣＰＵ１１は、探索範囲内で得られた値ＡＤが最小になるような相対位置を、動きベクトルとして求める。
【００２７】
従来の動き探索処理においては、全ての参照マクロブロックに対する差分の絶対値を計算して、最小の値ＭｉｎＡＤを求めていたが、本発明においては、式（１）の計算量を減らすために、次の式（２）の不等式が成立することを利用して、式（３）が成立する場合のみ、差分の絶対値和ＡＤを計算（すなわち、式（１）を計算）する。
【００２８】
【数２】
0003968774.tif 000004
0003968774.tif 000005
【数３】
0003968774.tif 000006
0003968774.tif 000007
【００２９】
ここで、ＭｉｎＡＤは、後述する動き探索処理中に更新される差分の絶対値和ＡＤの最小値である。
【００３０】
次に、図３のフローチャートを参照して、本発明を適応した動き探索処理について説明する。
【００３１】
ここでは、ＨＤＤ１８に予め記録されている動画像データ、もしくは、ネットワークインターフェース２０などを介して外部から入力され、一旦ＨＤＤ１８に供給して記録させた動画像データを、MPEG４を用いて圧縮処理する場合について説明する。
【００３２】
ステップＳ１において、ＣＰＵ１１は、ＨＤＤ１８に記録されている画像データを読み込み、カレント画像データから、カレントマクロブロックを抽出し、その画素値の和Σｃ（ｉ，ｊ）を計算する。
【００３３】
ステップＳ２において、ＣＰＵ１１は、カレント画像に対する初期位置の参照マクロブロックを抽出し、その画素値の和Σｒ（ｉ，ｊ）を計算する。
【００３４】
ステップＳ３において、図５を用いて後述するＭｉｎＡＤ初期値計算処理が実行される。
【００３５】
ステップＳ４において、ＣＰＵ１１は、現在の差分の絶対値和ＡＤの最小値ＭｉｎＡＤと、ステップＳ１において算出されるカレントマクロブロックの画素値の和Σｃ（ｉ，ｊ）、並びに、ステップＳ２もしくは後述するステップＳ９において算出される参照マクロブロックの画素値の和Σｒ（ｉ，ｊ）を用いて、上述した式（３）が成立するか否かを判断する。
【００３６】
ステップＳ４において、上述した式（３）が成立しないと判断された場合、処理は、ステップＳ８に進む。
【００３７】
ステップＳ４において、上述した式（３）が成立すると判断された場合、ステップＳ５において、ＣＰＵ１１は、上述した式（１）を用いて、カレントマクロブロックと、現在の参照マクロブロックの画素値の差分の絶対値和ＡＤを計算する。
【００３８】
ステップＳ６において、ＣＰＵ１１は、ステップＳ５において算出した画素値の差分の絶対値和ＡＤと、差分の絶対値和ＡＤの現在における最小値ＭｉｎＡＤを比較し、ＡＤ＜ＭｉｎＡＤが成立するか否かを判断する。
【００３９】
ステップＳ６において、ＡＤ＜ＭｉｎＡＤが成立しないと判断された場合、処理は、ステップＳ８に進む。
【００４０】
ステップＳ６において、ＡＤ＜ＭｉｎＡＤが成立すると判断された場合、ステップＳ７において、ＣＰＵ１１は、ステップＳ５において算出した画素値の差分の絶対値和ＡＤの値を、絶対値和ＡＤの現在における最小値ＭｉｎＡＤとする。
【００４１】
ステップＳ４において、上述した式（３）が成立しないと判断された場合、ステップＳ６において、ＡＤ＜ＭｉｎＡＤが成立しないと判断された場合、もしくは、ステップＳ７の処理の終了後、ステップＳ８において、ＣＰＵ１１は、探索範囲内の全ての位置の探索が終了したか否かを判断する。
【００４２】
ステップＳ８において、探索範囲内の全ての位置の探索が終了していないと判断された場合、ステップＳ９において、ＣＰＵ１１は、探索位置をずらして、新たな参照マクロブロックの画素値の和Σｒ（ｉ，ｊ）を計算し、処理は、ステップＳ４に戻り、それ以降の処理が繰り返される。
【００４３】
ここで、ステップＳ９における探索位置の変更は、例えば、図４に示されるように、カレントマクロブロックの位置をスタート点として、参照マクロブロックを、中心から外側に向かってらせん状に変更するようにする。実際の動画像では、それぞれのシーンにおいて、確率的に多くのマクロブロックが小さな動きベクトルを有している。従って、図4のように参照マクロブロックをらせん状にサーチすることにより、より小さな差分の絶対値和ＡＤの最小値ＭｉｎＡＤを早い探索段階で発見することができ、上述したステップＳ５乃至ステップＳ７の処理を省略することができる可能性が高くなる。更に、らせん状に探索位置を変更していくことにより、同値の差分の絶対値和ＡＤの最小値ＭｉｎＡＤが存在する場合に、より小さい値のベクトルを最終的な動きベクトルとして選択することが可能となる。
【００４４】
ステップＳ８において、探索範囲内の全ての位置の探索が終了したと判断された場合、ステップＳ１０において、図６を用いて後述するブロックタイプ判断および動きベクトル出力処理が実行され、処理が終了される。
【００４５】
以上説明した処理により、動き探索処理に必要な計算量を減少することができる。
【００４６】
また、ステップＳ９において実行される新たな参照マクロブロックの画素値の和Σｒ（ｉ，ｊ）の計算は、新たな参照マクロブロックの１６×１６画素全ての画素値の和を算出する必要はない。すなわち、前の参照マクロブロックからずれている画素のみの画素値を、それぞれ減算および加算するようにすればよい。
【００４７】
例えば、参照マクロブロックが１ライン（１６画素）分だけ水平、もしくは、垂直方向にシフトした場合、前の参照マクロブロックの画素値の和Σｒ（ｉ，ｊ）から、新たな参照マクロブロックに含まれない１６画素の画素値を減算し、新たな参照マクロブロックに含まれる１６画素の画素値を加算するようにすればよい。図２を用いて説明したように、らせん状に参照マクロブロックをサーチする場合、ステップＳ９の演算処理は、１６の画素値の減算処理と、１６の画素値の加算処理となる。
【００４８】
次に、図５のフローチャートを参照して、図３のステップＳ３において実行されるＭｉｎＡＤ初期値計算処理について説明する。
【００４９】
ステップＳ２１において、ＣＰＵ１１は、マクロブロック内の画素値の平均値と、それぞれの画素との差分の絶対値和ＭＡＤ、および動きベクトルが０のときの差分の絶対値和ＡＤ０を計算する。
【００５０】
ステップＳ２２において、ＣＰＵ１１は、マクロブロックがイントラマクロブロックであるか、インターマクロブロックであるかを判断するための閾値Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤの値を、ステップＳ２１において算出した値ＭＡＤを用いて計算する。
【００５１】
閾値Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤと、差分の絶対値和ＡＤの最小値ＭｉｎＡＤを比較して、最小値ＭｉｎＡＤが大きいか、等しい場合、そのマクロブロックはイントラマクロブロックである。イントラマクロブロックは、参照画像を持たない新たな画像のマクロブロックであり、参照画像から情報を得ることが出来ないため、動きベクトルの符号量を省いて、隣接ブロックを参照して、ＡＣ／ＤＣ予測を行い、DCTを行うことによって符号化を行う。これに対して、最小値ＭｉｎＡＤが閾値Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤより小さい場合、そのマクロブロックは、インターマクロブロックである。インターマクロブロックは、参照画像を基に、動きベクトルに基づいて動き補償を行い、DCTを行うことによって符号化することができる。
【００５２】
ステップＳ２３において、ＣＰＵ１１は、動きベクトルを０とするか否か、換言すれば、動き補償を行うか否かを判断するための閾値ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤの値を、ステップＳ２１において算出した、動きベクトルが０のときの差分の絶対値和ＡＤ０を用いて計算する。
【００５３】
閾値ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤは、実際の画像では動きがないような場面であっても、ノイズが動きベクトルとして検出されてしまうことを防ぐために設けられる閾値であり、閾値ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤと、差分の絶対値和ＡＤの最小値ＭｉｎＡＤとを比較して、最小値ＭｉｎＡＤが大きいか等しい場合、得られた動きベクトルを用いずに、動きベクトルを０として処理が実行される。
【００５４】
ステップＳ２４において、ＣＰＵ１１は、ステップＳ２２において計算された閾値Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤと、ステップＳ２３において計算された閾値ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤとを比較し、Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤ＜ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤが成立するか否かを判断する。
【００５５】
ステップＳ２４において、Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤ＜ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤが成立すると判断された場合、ＣＰＵ１１は、ステップＳ２５において、差分の絶対値和ＡＤの最小値ＭｉｎＡＤの初期値を、ステップＳ２２において計算されたＩｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤの値とし、ステップＳ２６において、ＭｉｎＡＤ０＿ｆｉａｇ＝１として、それぞれＲＡＭ１６に記憶し、処理は、図３のステップＳ４に戻る。
【００５６】
ステップＳ２４において、Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤ＜ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤが成立しないと判断された場合、ＣＰＵ１１は、ステップＳ２７において、差分の絶対値和ＡＤの最小値ＭｉｎＡＤの初期値を、ステップＳ２３において計算されたＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤの値とし、ステップＳ２８において、ＭｉｎＡＤ０＿ｆｉａｇ＝２として、それぞれＲＡＭ１６に記憶し、処理は、図３のステップＳ４に戻る。
【００５７】
ここで、ＡＤ０を基に算出される閾値ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤの値は、実際には、ＡＤ０より小さいか、同一の値となる。従って、閾値Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤと、閾値ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤとのうちの値の小さい方は、必ずＡＤ０より小さいか、同一の値となる。すなわち、図５を用いて説明した処理により、差分の絶対値和ＡＤの最小値ＭｉｎＡＤの値を小さな値に設定することが可能となり、図３を用いて説明した動き探索処理のうち、イントラマクロブロック、もしくは動き補償を行わないマクロブロックと判定される部分のマッチング処理（ステップＳ５乃至ステップＳ７の処理）を省略することができるので、計算処理量を削減することが可能となる。
【００５８】
次に、図６のフローチャートを参照して、図３のステップＳ１０において実行されるブロックタイプ判断および動きベクトル出力処理について説明する。
【００５９】
ステップＳ４１において、ＣＰＵ１１は、ＲＡＭ１６に記憶されているＭｉｎＡＤ０＿ｆｉａｇの値と、差分の絶対値和ＡＤの最小値ＭｉｎＡＤの値を参照し、ＭｉｎＡＤ０＿ｆｉａｇ＝１、すなわち、ＭｉｎＡＤの初期値は、Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤであり、かつ、探索範囲内の全ての探索処理が終了した後のＭｉｎＡＤの値がＩｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤと等しいか否かを判断する。
【００６０】
ステップＳ４１において、ＭｉｎＡＤ０＿ｆｉａｇ＝１かつＭｉｎＡＤ＝Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤであると判断された場合、ステップＳ４２において、ＣＰＵ１１は、処理中のマクロブロックは、他に参照画像を持たないイントラマクロブロックであるとして、処理を終了する。
【００６１】
ステップＳ４１において、ＭｉｎＡＤ０＿ｆｉａｇ＝１かつＭｉｎＡＤ＝Ｉｎｔｒａ＿Ｂｏｕｎｄａｒｙ＿ＡＤではないと判断された場合、ステップＳ４３において、ＣＰＵ１１は、ＲＡＭ１６に記憶されているＭｉｎＡＤ０＿ｆｉａｇの値と、差分の絶対値和ＡＤの最小値ＭｉｎＡＤの値を参照し、ＭｉｎＡＤ０＿ｆｉａｇ＝２、すなわち、ＭｉｎＡＤの初期値がＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤであり、かつ、探索範囲内の全ての探索処理が終了した後のＭｉｎＡＤの値がＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤと等しいか否かを判断する。
【００６２】
ステップＳ４３において、ＭｉｎＡＤ０＿ｆｉａｇ＝２かつＭｉｎＡＤ＝ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤであると判断された場合、ステップＳ４４において、ＣＰＵ１１は、処理中のマクロブロックは、動き補償無しマクロブロックであるとして、処理を終了する。
【００６３】
ステップＳ４３において、ＭｉｎＡＤ０＿ｆｉａｇ＝２かつＭｉｎＡＤ＝ＮｏＭＣ＿Ｂｏｕｎｄａｒｙ＿ＡＤではないと判断された場合、処理中のマクロブロックは、参照画像を用いて符号化処理を行うインターマクロブロックであり、かつ、動き補償ありのマクロブロックであるから、ステップＳ４５において、ＣＰＵ１１は、カレントマクロブロックから、差分の絶対値和ＡＤの最小値ＭｉｎＡＤをあたえた参照マクロブロックへの移動量を基に、動きベクトルMV（ｘ，ｙ）を求め、その値を出力して、処理を終了する。
【００６４】
以上説明した処理により求められたマクロブロックタイプ、もしくは動きベクトルは、マクロブロックの符号化に用いられる（続いて行われるマクロブロックの符号化処理に対して、これらの結果が出力される）。
【００６５】
マクロブロックが１６×１６画素で構成され、Ｓ×Ｓの探索範囲内において動きベクトルを探索する場合について、従来の処理により実行される計算量と本発明を適応した場合に実行される処理により実行される計算量とを比較する。
【００６６】
従来の計算方法によって、カレント画像のマクロブロックと、参照画像のマクロブロックとの差分の絶対値和ＡＤを求める場合、カレントマクロブロックと、参照マクロブロックにおいて、２５６個の画素毎に画素値の差を求め、それぞれの絶対値を取り、更に２５６の値の和を計算しなければならない。そして、動きベクトルを探索するためには、更に、この演算をＳ×Ｓの探索範囲内の全てにおいて実施する必要がある。従って、従来の方法による計算量Ｔ１は、次の式（４）で示される。
【００６７】
Ｔ１＝（２５６（減算）＋２５６（絶対値演算）＋２５６（加算））×Ｓ×Ｓ・・・（４）
【００６８】
これに対して、本発明を適応した計算方法によれば、差分の絶対値和ＡＤを算出する前に、まず、ステップＳ１において、カレント画像のマクロブロックの２５６個の画素値の和が算出され、ステップＳ２において、最初の参照画像のマクロブロックの２５６個の画素値の和が算出される。そして、探索範囲内の全てのマクロブロック（Ｓ×Ｓ個）において、ステップＳ４が実行される。すなわち、１回の減算、１回の絶対値計算および１回の比較計算がＳ×Ｓ回実行される。
【００６９】
そして、ステップＳ４の比較結果に基づいて、ステップＳ５の差分の絶対値和ＡＤの算出処理が実行される。この処理は、上述したように、カレントマクロブロックと、参照マクロブロックにおいて、２５６個の画素毎に画素値の差を求め、それぞれの絶対値を取り、更に２５６の値の和を計算する必要がある。ここで、ステップＳ４において、式（３）が成立したと判断され、ステップＳ５が実行される回数をａ（０＜ａ＜Ｓ×Ｓ）とする。
【００７０】
そして、ステップＳ８において、全ての探索範囲の処理が終了したと判断されるまで、すなわち、Ｓ×Ｓ回、ステップＳ９の処理が実行され、次の探索位置の参照マクロブロックのΣｒ（ｉ，ｊ）を求めるために、前の参照マクロブロックからずれた１６画素それぞれの減算処理および加算処理が行われる。
【００７１】
従って、本発明を適応した場合の計算量Ｔ２は、次の式（５）で示される。
【００７２】
0003968774.tif 000008
【００７３】
そして、上述した式（４）と式（５）を比較して、式（５）の演算量のほうが少なければ、本発明を利用した動き探索処理の演算量は従来における演算量よりも少ないといえる。本発明においては、図４を用いて説明しているように、参照マクロブロックをらせん状にサーチし、図５のフローチャートを用いて説明したように、ＭｉｎＡＤの初期値をできるだけ小さい値に設定するようにしているので、図３のステップＳ５の処理回数、すなわち、式（５）におけるａの値は、非常に小さくなる。従って、本発明を利用した動き探索処理の演算量は従来における演算量よりも少ないといえる。
【００７４】
本発明を適応した場合、圧縮処理を実行する画像の内容にもよるが、差分の絶対値和ＡＤの最小値ＭｉｎＡＤの初期値として小さな値があたえられ、更に、参照マクロブロックを、カレントマクロブロックに対してらせん状にサーチするようにしたので、最終的なＭｉｎＡＤが早い段階で得られる可能性が高くなるとともに、カレントマクロブロックと参照マクロブロックとのマッチング処理の実行回数が削減される。本発明は、探索範囲が広く設定されているような動き探索処理の演算回数を削減するのに、特に有効である。
【００７５】
上述した処理においては、MPEG４を用いて動画像データを圧縮する場合について説明したが、本発明は、MPEG４のみならず、MPEGによる画像圧縮処理全体に対して適応することが可能である。
【００７６】
また、本実施の形態においては、パーソナルコンピュータ１の処理として説明したが、本発明は、例えば、ＰＤＡ、携帯型電話機、画像記録再生装置など、画像処理を実行することができる全ての装置において適応することが可能である。
【００７７】
上述した一連の処理は、ソフトウェアにより実行することもできる。そのソフトウェアは、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【００７８】
この記録媒体は、図１に示すように、コンピュータとは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク２１（フレキシブルディスクを含む）、光ディスク２２（CD−ROM（Compact Disk-Read Only Memory），DVD（Digital Versatile Disk）を含む）、光磁気ディスク２３（ＭＤ(Mini-Disk)（商標）を含む）、もしくは半導体メモリ２４などよりなるパッケージメディアなどにより構成される。
【００７９】
また、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【００８０】
【発明の効果】
本発明によれば、MPEGを用いて動画像データを圧縮する場合の動き探索処理を行うことができ、その場合に、動き探索処理のための演算量を減少することができる。
【図面の簡単な説明】
【図１】パーソナルコンピュータ１の構成を示すブロック図である。
【図２】マクロブロック、探索範囲、および動きベクトルを説明する図である。
【図３】本発明を適応した動き探索処理を説明するフローチャートである。
【図４】動き探索処理において、らせん状に画像を探索することを説明する図である。
【図５】図３のステップＳ３におけるＭｉｎＡＤ初期値計算処理を説明するフローチャートである。
【図６】図３のステップＳ１０におけるブロックタイプ判断および動きベクトル出力処理を説明するフローチャートである。
【符号の説明】
１  パーソナルコンピュータ，  １１  ＣＰＵ，  １６  ＲＡＭ，  １８  ＨＤＤ，  ２０  ネットワークインターフェース
【図１】
0003968774.tif 000009
【図２】
0003968774.tif 000010
【図３】
0003968774.tif 000011
【図４】
0003968774.tif 000012
【図５】
0003968774.tif 000013
【図６】
0003968774.tif 000014