(57)【要約】【課題】二次元直行変換の演算量を削減すること。【解決手段】画像処理装置は、第２の予測ブロック内で第１の予測ブロックに重複していない画素に関する第１の画素値行列（Ｂｃ＿ｌ）と第１の予測ブロック内で第２の予測ブロックに重複していない画素に関する第２の画素値行列（Ｂｐ＿ｌ）との差分を算出する。そして、算出された差分値行列を直交変換の対象行列とし、画像処理装置は、差分値行列に対して直交変換行列を用いて第１の直交変換と第２の直交変換とを施す。画像処理装置は、第１および第２の直交変換後の変換係数行列を、第１の予測ブロックに関する第１の変換係数行列を用いて補完することで第２のブロックに関する第２の変換係数行列を算出する。【選択図】図１−１
2011188007.tif 000002
【特許請求の範囲】
【請求項１】
画像内のＮ×Ｎ要素の第１のブロックが任意の探索方向にＭ（１≦Ｍ＜Ｎ／２）要素シフトしたＮ×Ｎ要素の第２のブロックの二次元直交変換を実行する画像処理装置であって、
前記第２のブロック内で前記第１のブロックに重複していない第１の特徴量行列と、前記第１のブロック内で前記第２のブロックに重複していない第２の特徴量行列との差分となる差分値行列を算出する差分値算出手段と、
前記差分値算出手段により算出されたＮ×Ｍ要素の差分値行列を、Ｎ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｍ要素の変換係数行列を算出する第１の直交変換手段と、
前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を、Ｍ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｎ要素の変換係数行列を算出する第２の直交変換手段と、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記第２の直交変換手段により変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する係数値算出手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
Ｍ＝１、かつ前記Ｎ×Ｎ要素の直交変換行列がアダマール変換行列、かつ前期Ｍ×Ｎ要素の変換行列が前記アダマール変換行列の一部を取り出した行列であり、
前記第２の直交変換手段は、
前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を前記探索方向にＮ個並べることにより、Ｎ×Ｎ要素の変換係数行列を生成する生成手段と、
前記生成手段により生成されたＮ×Ｎ要素の変換係数行列内の各要素の符号を、前記Ｍ×Ｎ要素の直交変換行列に基づいて変換する符号変換手段と、を備え、
前記係数値算出手段は、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記符号変換手段により符号が変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記画像と異なる画像内のＮ×Ｎ要素の第３のブロックに関する第３の変換係数行列と前記係数値算出手段により算出された第２の変換係数行列との差分となる係数差分値行列を算出する係数差分値算出手段と、
前記係数差分値算出手段により算出された係数差分値行列の絶対値を算出する絶対値演算手段と、
前記絶対値演算手段により算出された絶対値行列内の要素の総和を算出する総和演算手段と、
を備えることを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
画像内のＮ×Ｎ要素の第１のブロックが任意の探索方向にＭ（１≦Ｍ＜Ｎ／２）要素シフトしたＮ×Ｎ要素の第２のブロックの二次元直交変換を実行するコンピュータが、
前記第２のブロック内で前記第１のブロックに重複していない第１の特徴量行列と、前記第１のブロック内で前記第２のブロックに重複していない第２の特徴量行列との差分となる差分値行列を算出する差分値算出工程と、
前記差分値算出工程により算出されたＮ×Ｍ要素の差分値行列を、Ｎ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｍ要素の変換係数行列を算出する第１の直交変換工程と、
前記第１の直交変換工程により算出されたＮ×Ｍ要素の変換係数行列を、Ｍ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｎ要素の変換係数行列を算出する第２の直交変換工程と、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記第２の直交変換工程により変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する係数値算出工程と、
を実行することを特徴とする画像処理方法。
【請求項５】
画像内のＮ×Ｎ要素の第１のブロックが任意の探索方向にＭ（１≦Ｍ＜Ｎ／２）要素シフトしたＮ×Ｎ要素の第２のブロックの二次元直交変換を実行するコンピュータを、
前記第２のブロック内で前記第１のブロックに重複していない第１の特徴量行列と、前記第１のブロック内で前記第２のブロックに重複していない第２の特徴量行列との差分となる差分値行列を算出する差分値算出手段、
前記差分値算出手段により算出されたＮ×Ｍ要素の差分値行列を、Ｎ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｍ要素の変換係数行列を算出する第１の直交変換手段、
前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を、Ｍ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｎ要素の変換係数行列を算出する第２の直交変換手段、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記第２の直交変換手段により変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する係数値算出手段、
として機能させることを特徴とする画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像内のブロックに対して二次元直交変換処理をおこなう画像処理装置、画像処理方法、および画像処理プログラムに関する。
【背景技術】
【０００２】
従来より、Ｈ．２６４、ＭＰＥＧ−２等の予測画像を生成する手段としてフレーム間予測を用いる画像処理装置では、フレーム間予測で使用される動きベクトルを算出する処理を備えている（たとえば、下記特許文献１参照。）。動きベクトルとは、原画像内の対象となるブロックが参照画像内のどのブロックから動いたのかを示す動き位置情報である。
【０００３】
動きベクトルの算出処理では、原画像内の対象ブロックと、候補となる動きベクトルによって示された参照画像内の予測ブロックとの類似度を判定している。類似度判定のための評価指標として最も広く用いられているのがＳＡＤ（Ｓｕｍ  Ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ、絶対値差分和）である。ＳＡＤは、当該対象ブロックと予測ブロックの対応する各画素同士の差の絶対値を取り、差の絶対値を合計することで得られる。
【０００４】
しかしながら、動きベクトルの評価指標としては、ＳＡＤよりもＳＡＴＤ（Ｓｕｍ  Ｏｆ  Ａｂｓｏｌｕｔｅ  Ｔｒａｎｓｆｏｒｍｅｄ  Ｄｉｆｆｅｒｅｎｃｅ）（たとえば、下記特許文献２参照。）の方が正確である。ＳＡＴＤは、予測ブロックと対象ブロックの画素同士の差分を直交変換し、変換後の各係数の絶対値を合計することで得られる。
【０００５】
ＳＡＤを使っての評価は差分処理まで符号化処理を進めた結果の評価に相当するのに対して、ＳＡＴＤは直交変換処理まで符号化を進めた結果の評価である。よって、ＳＡＴＤでは、符号化結果であるストリームにより近いところまで符号化処理を進めているので、ＳＡＤと比較して正確に予測画像の評価をおこなうことができる。
【０００６】
また、直交変換では、演算量の少ないアダマール変換を用いることが多い。Ｈ．２６４のリファレンスエンコーダ内でもアダマール変換が用いられている。さらに、アダマール変換で用いるアダマール変換行列を変形することでアダマール変換での演算量を削減する処理が知られている（たとえば、下記特許文献３参照。）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−１８６５０４号公報
【特許文献２】特開平３−１８５９８６号公報
【特許文献３】特開２００４−２４１９５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ＳＡＴＤでは、ＳＡＤよりも多くの計算が必要であり、符号化処理全体の計算処理のうちのＳＡＤ／ＳＡＴＤが占める計算処理の割合が非常に大きいため、ＳＡＤとＳＡＴＤのうち、どちらを採用するかによって、符号化処理全体の演算量は、大きく異なっていた。
【０００９】
Ｈ．２６４リファレンスエンコーダでは、整数精度の探索ではＳＡＤによるベクトルの評価をおこない、小数精度の探索ではＳＡＴＤを用いるという手法を用いることにより、ＳＡＴＤを用いながらも演算量を削減していた。しかし、ＳＡＴＤの演算量が大きいという問題点があったため、実際の製品では評価精度が下がっても演算量の少ないＳＡＤを採用することが一般的であった。
【００１０】
本発明は、上述した従来技術による問題点を解消するため、直交変換の対象となる行列の要素数を減らすことで二次元直交変換の演算量を削減できる画像処理装置、画像処理方法、および画像処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の一観点によれば、画像内のＮ×Ｎ要素の第１のブロックが任意の探索方向にＭ（１≦Ｍ＜Ｎ／２）要素シフトしたＮ×Ｎ要素の第２のブロック内で前記第１のブロックに重複していない第１の特徴量行列と、前記第１のブロック内で前記第２のブロックに重複していない第２の特徴量行列との差分となる差分値行列を算出する差分値算出手段と、前記差分値算出手段により算出されたＮ×Ｍ要素の差分値行列をＮ×Ｎ要素の直交変換行列を用いて一次元直交変換してＮ×Ｍ要素の変換係数行列を算出する第１の直交変換手段と、前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を、Ｍ×Ｎ要素の直交変換行列を用いて一次元直交変換してＮ×Ｎ要素の変換係数行列を算出する第２の直交変換手段と、前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記第２の直交変換手段により変換されたＮ×Ｎ要素の変換係数行列とに基づいて前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する係数値算出手段と、を備える画像処理装置が提供される。
【発明の効果】
【００１２】
本画像処理装置、画像処理方法、および画像処理プログラムによれば、直交変換の対象となる行列の要素数を減らすことで二次元直交変換の演算量を削減することができるという効果を奏する。
【図面の簡単な説明】
【００１３】
【図１−１】本発明の１実施例を示す説明図（その１）である。
【図１−２】本発明の１実施例を示す説明図（その２）である。
【図２−１】現ベクトルのｘ成分が前ベクトルのｘ成分より１大きい場合を示す説明図である。
【図２−２】現ベクトルのｘ成分が前ベクトルのｘ成分より１小さい場合を示す説明図である。
【図２−３】現ベクトルのｙ成分が前ベクトルのｙ成分より１大きい場合を示す説明図である。
【図２−４】現ベクトルのｙ成分が前ベクトルのｙ成分より１小さい場合を示す説明図である。
【図３】実施の形態１にかかる画像処理装置の一例を示す説明図である。
【図４】スパイラルサーチによる動きベクトル探索例を示す説明図である。
【図５−１】実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その１）である。
【図５−２】実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その２）である。
【図５−３】実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その３）である。
【図５−４】実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その４）である。
【図６−１】入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その１）である。
【図６−２】入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その２）である。
【図６−３】入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その３）である。
【図６−４】入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その４）である。
【図７】マクロブロックの一例を示す説明図である。
【図８】実施の形態３にかかる画像処理装置の一例を示す説明図である。
【図９】ユニット０＿１〜ユニット０＿７の詳細な説明を示す説明図である。
【図１０】ユニット１＿１〜ユニット１＿４の詳細な説明を示す説明図である。
【図１１】ユニット２−３＿１〜ユニット２−３＿９の詳細な説明を示す説明図である。
【図１２】実施の形態にかかる画像処理装置のハードウェア構成を示すブロック図である。
【図１３】実施の形態４にかかる画像処理装置の機能的構成を示すブロック図である。
【図１４−１】係数値算出部１３０４の詳細な構成を示す説明図（その１）である。
【図１４−２】第１の直交変換部１３０２の詳細な構成を示す説明図である。
【図１４−３】係数値算出部１３０４の詳細な構成を示す説明図（その２）である。
【図１５】画像処理装置による画像処理手順の一例を示すフローチャートである。
【図１６】図１５で示した第１の二次元直交変換処理（ステップＳ１５０３）の詳細な説明を示すフローチャートである。
【図１７】図１５で示した第２の二次元直交変換処理（ステップＳ１５０４）の詳細な説明を示すフローチャートである。
【図１８】図１５で示した第２の二次元直交変換処理（ステップＳ１５０５）の詳細な説明を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下に添付図面を参照して、本発明にかかる画像処理装置、画像処理方法、および画像処理プログラムの好適な実施の形態を詳細に説明する。
【００１５】
図１−１，１−２は、本発明の１実施例を示す説明図である。まず、図１−１には、参照画像内で前ベクトルによって示される第１の予測ブロックと、第１の予測ブロックが探索方向に１シフトした現ベクトルによって示される第２の予測ブロックとが示されている。ここでは、Ｎ×Ｎ要素のブロックとは、Ｎ×Ｎ画素のブロックを示し、図１−１，１−２においては、４×４画素を１ブロックとして扱っている。画素に関する特徴量とは、画素値である。
【００１６】
まず、画像処理装置が、第２の予測ブロック内で第１の予測ブロックに重複していない第１の画素値行列（Ｂｃ＿ｌ）と、第１の予測ブロック内で第２の予測ブロックに重複していない第２の画素値行列（Ｂｐ＿ｌ）との差分となる差分値行列を算出する。
【００１７】
つぎに、画像処理装置が、４×４要素の直交変換行列を用いて４×１要素の差分値行列を一次元直交変換して４×１要素の変換係数行列を算出する。直交変換に関しては、既存の技術を用いればよく、直交変換行列は、直交変換によって決定される。
【００１８】
そして、画像処理装置が、４×１要素の変換係数行列を、１×４要素の直交変換行列を用いて一次元直交変換して、４×４要素の変換係数行列を算出する。
【００１９】
つぎに、図１−２に移って、画像処理装置が、第１の予測ブロックに関する４×４要素の第１の変換係数行列（Ｒｐ）と、算出された４×４要素の変換係数行列とに基づいて第２の予測ブロックに関する４×４の第２の変換係数行列を算出する。具体的には、たとえば、画像処理装置が、第１の変換係数行列と算出された４×４要素の変換係数行列とを加算し、行ベクトルを入れ替えるための入れ替え行列と乗算する。これにより、４×４の第２の変換係数行列が算出される。
【００２０】
第２の予測ブロックが第１の予測ブロックに対して横方向に１シフトしたブロックの場合、第１の特徴行列と第２の特徴行列とは、Ｎ行１列の行列である。そして、一次元直交変換では、Ｎ行Ｎ列の直交変換行列と１行Ｎ列の直交変換行列を用いておこなわれる。また、横方向にＭ（１≦Ｍ＜Ｎ／２）シフトした場合、第１の特徴行列と第２の特徴行列とは、Ｎ行Ｍ列の行列である。そして、一次元直交変換では、Ｎ行Ｎ列の直交変換行列とＭ行Ｎ列の直交変換行列を用いておこなわれる。
【００２１】
一方、第２の予測ブロックが第１の予測ブロックに対して縦方向に１シフトしたブロックの場合、第１の特徴行列と第２の特徴行列とは、１行Ｎ列の行列である。一次元直交変換では、Ｎ行Ｎ列の直交変換行列とＮ行１列の直交変換行列を用いておこなわれる。また、縦方向にＭ（１≦Ｍ＜Ｎ／２）シフトした場合、第１の特徴行列と第２の特徴行列とは、Ｍ行Ｎ列の行列である。そして、一次元直交変換では、Ｎ行Ｎ列の直交変換行列とＮ行Ｍ列の直交変換行列を用いておこなわれる。
【００２２】
本発明の詳細な説明については、実施の形態１から４を用いて説明する。まず、実施の形態１では、現ベクトルにより示されるＮ×Ｎ画素の第２の予測ブロックが、前ベクトルにより示されるＮ×Ｎ画素の第１の予測ブロックを用いて二次元直交変換される例を説明する。
【００２３】
つぎに、実施の形態２では、現ベクトルにより示されるＮ×Ｎ画素の第２の予測ブロックが、前ベクトルにより示されるＮ×Ｎ画素の第１の予測ブロックを用いて二次元アダマール変換される例を説明する。
【００２４】
そして、実施の形態３では、Ｎ＝４の場合において、現ベクトルにより示されるＮ×Ｎ画素の第２の予測ブロックに関するＳＡＴＤを算出する例を説明する。
【００２５】
最後に、実施の形態４では、実施の形態１で示した画像処理装置による処理がコンピュータによって処理される例を説明する。
【００２６】
（実施の形態１）
まず、図２−１〜図２−４を用いて前ベクトルが示す第１の予測ブロックと現ベクトルが示す第２の予測ブロックとについて説明する。
【００２７】
図２−１は、現ベクトルのｘ成分が前ベクトルのｘ成分より１大きい場合を示す説明図である。原画像内の対象ブロックから参照画像内の第１の予測ブロックへの矢印が、前ベクトルである。原画像内の対象ブロックから参照画像内の第２の予測ブロックへの矢印が、現ベクトルである。現ベクトルのｘ成分が前ベクトルのｘ成分より１大きい。したがって、第２の予測ブロックは、第１の予測ブロックから横方向に＋１シフトしたブロックである。
【００２８】
なお、本実施の形態１では、１ブロックが、４画素×４画素である。ベクトルのｘは、横方向の画素であり、ｙは縦方向の画素である。ベクトル（０、０）とは、原画像内の対象ブロックと同一位置にある参照画像内の予測ブロックを示すベクトルである。
【００２９】
そして、Ｂｃ＿ｌは、第２の予測ブロック内で第１の予測ブロックに重複していない画素の列ベクトルである。一方、Ｂｐ＿ｌは、第１の予測ブロック内で第２の予測ブロックに重複していない画素の列ベクトルである。
【００３０】
本実施の形態１では、第２の予測ブロックが二次元直交変換された第２の変換係数行列（Ｒｃ）を、第１の予測ブロックが二次元直交変換された第１の変換係数行列（Ｒｐ）を用いて算出する。現ベクトルのｘ成分が前ベクトルのｘ成分より１大きい場合は、下記式（１）を用いてＲｃを算出する。
【００３１】
Ｒｃ＝［Ｒｐ＋｛Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）｝・Ｔ２＿ｕ］・（ｉＴ２・Ｓｒ・Ｔ２）                                                                ・・・（１）
【００３２】
Ｔ１、Ｔ２、Ｔ２＿ｕ、Ｓｒについては、後述する。
【００３３】
図２−２は、現ベクトルのｘ成分が前ベクトルのｘ成分より１小さい場合を示す説明図である。原画像内の対象ブロックから参照画像内の第１の予測ブロックへの矢印が、前ベクトルである。原画像内の対象ブロックから参照画像内の第２の予測ブロックへの矢印が、現ベクトルである。現ベクトルのｘ成分が前ベクトルのｘ成分より１小さい。したがって、第２の予測ブロックは、第１の予測ブロックから横方向に−１シフトしたブロックである。なお、本実施の形態１では、１ブロックが、４画素×４画素である。
【００３４】
そして、Ｂｃ＿ｌは、第２の予測ブロック内で第１の予測ブロックに重複していない画素の列ベクトルである。一方、Ｂｐ＿ｌは、第１の予測ブロック内で第２の予測ブロックに重複していない画素の列ベクトルである。
【００３５】
第１の予測ブロックが二次元直交変換された第１の変換係数行列（Ｒｐ）を用いて第２の予測ブロックに関する第２の変換係数行列（Ｒｃ）が算出される。現ベクトルのｘ成分が前ベクトルのｘ成分より１小さい場合は、下記式（２）を用いてＲｃを算出する。
【００３６】
Ｒｃ＝［Ｒｐ＋｛Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）｝・Ｔ２＿ｄ］・（ｉＴ２・Ｓｌ・Ｔ２）                                                                ・・・（２）
【００３７】
Ｔ２＿ｄ、Ｓｌについては、後述する。
【００３８】
図２−３は、現ベクトルのｙ成分が前ベクトルのｙ成分より１大きい場合を示す説明図である。原画像内の対象ブロックから参照画像内の第１の予測ブロックへの矢印が、前ベクトルである。原画像内の対象ブロックから参照画像内の第２の予測ブロックへの矢印が、現ベクトルである。現ベクトルのｙ成分が前ベクトルのｙ成分より１大きい。したがって、第２の予測ブロックは、第１の予測ブロックから縦方向に＋１シフトしたブロックである。
【００３９】
そして、Ｂｃ＿ｒは、第２の予測ブロック内で第１の予測ブロックに重複していない画素の列ベクトルである。一方、Ｂｐ＿ｒは、第１の予測ブロック内で第２の予測ブロックに重複していない画素の列ベクトルである。
【００４０】
現ベクトルのｙ成分が前ベクトルのｙ成分より１大きい場合は下記式（３）によりＲｃが算出される。
【００４１】
Ｒｃ＝（Ｔ１・Ｓｄ・ｉＴ１）・［Ｒｐ＋Ｔ１＿ｌ・｛（Ｂｃ＿ｒ−Ｂｐ＿ｒ）・Ｔ２｝］                                                            ・・・（３）
【００４２】
Ｔ１＿ｌ、Ｓｄについては、後述する。
【００４３】
図２−４は、現ベクトルのｙ成分が前ベクトルのｙ成分より１小さい場合を示す説明図である。原画像内の対象ブロックから参照画像内の第１の予測ブロックへの矢印が、前ベクトルである。原画像内の対象ブロックから参照画像内の第２の予測ブロックへの矢印が、現ベクトルである。現ベクトルのｙ成分が前ベクトルのｙ成分より１小さい。したがって、第２の予測ブロックは、第１の予測ブロックから縦方向に−１シフトしたブロックである。
【００４４】
そして、Ｂｃ＿ｒは、第２の予測ブロック内で第１の予測ブロックに重複していない画素の列ベクトルである。一方、Ｂｐ＿ｒは、第１の予測ブロック内で第２の予測ブロックに重複していない画素の列ベクトルである。
【００４５】
現ベクトルのｙ成分が前ベクトルのｙ成分より１小さい場合は下記式（４）によりＲｃが算出される。
【００４６】
Ｒｃ＝（Ｔ１・Ｓｕ・ｉＴ１）・［Ｒｐ＋Ｔ１＿ｒ・｛（Ｂｃ＿ｒ−Ｂｐ＿ｒ）・Ｔ２｝］                                                                ・・・（４）
【００４７】
Ｔ１＿ｒ、Ｓｕについては、後述する。
【００４８】
以下に、上記式（１）〜（４）で示される各行列について示す。
・Ｔ１：一次元直交変換行列
・Ｔ２：一次元直交変換行列
・ｉＴ１：Ｔ１の逆行列
・ｉＴ２：Ｔ２の逆行列
・Ｓｒ：右からかけると、最右列を最左列に、残りの列を１つ右に移す行列
・Ｓｌ：右からかけると、最左列を最右列に、残りの列を１つ左に移す行列
・Ｓｄ：左からかけると、最下行を最上行に、残りの行を１つ下に移す行列
・Ｓｕ：左からかけると、最上行を最下行に、残りの行を１つ上に移す行列
・Ｂｃ＿ｌ：現ベクトルで示される予測ブロック内で前ベクトルで示される予測ブロックに重複していないＮ×１画素の画素値行列（第１の画素値行列）、列ベクトル
・Ｂｐ＿ｌ：前ベクトルで示される予測ブロック内で現ベクトルで示される予測ブロックに重複していないＮ×１画素の画素値行列（第２の画素値行列）、列ベクトル
・Ｂｃ＿ｒ：現ベクトルで示される予測ブロック内で前ベクトルで示される予測ブロックに重複していない１×Ｎ画素の画素値行列（第１の画素値行列）、行ベクトル
・Ｂｐ＿ｒ：前ベクトルで示される予測ブロック内で現ベクトルで示される予測ブロックに重複していない１×Ｎ画素の画素値行列（第２の画素値行列）、行ベクトル
・Ｔ２＿ｕ：Ｔ２の最上行を要素に持つ行ベクトル
・Ｔ２＿ｄ：Ｔ２の最下行を要素に持つ行ベクトル
・Ｔ１＿ｌ：Ｔ１の最左列を要素に持つ列ベクトル
・Ｔ１＿ｒ：Ｔ１の最右列を要素に持つ列ベクトル
・Ｒｐ：第１の予測ブロックに関する第１の変換係数行列
・Ｒｃ：第２の予測ブロックに関する第２の変換係数行列
【００４９】
上記式（１）の（ｉＴ２・Ｓｒ・Ｔ２）と、上記式（２）の（ｉＴ２・Ｓｌ・Ｔ２）と、上記式（３）の（Ｔ１・Ｓｄ・ｉＴ１）と、上記式（４）の（Ｔ１・Ｓｕ・ｉＴ１）とは、行列の入れ替えに関する入れ替え行列である。
【００５０】
ここで、上記式（１）の導出過程について説明する。また、Ｔ１、Ｐｃ、Ｔ２は、Ｎ行Ｎ列の行列であり、Ｔ１、Ｔ２は正則行列である。現ベクトルによって示される予測画像をＰｃ、前ベクトルによって示される予測画像をＰｐとする。下記式（５）では、Ｐｃを直交変換してＲｃを算出する例である。
【００５１】
Ｒｃ＝Ｔ１・Ｐｃ・Ｔ２                                            ・・・（５）
【００５２】
たとえば、下記式（６）とする。
【００５３】
Ｐｍ＝Ｐｃ・Ｓｒ                                                  ・・・（６）
【００５４】
よって、上記式（６）から下記式（７）を得ることができる。
【００５５】
Ｐｃ＝Ｐｍ・ｉＳｒ                                                ・・・（７）
【００５６】
そして、上記式（７）を上記式（５）に代入することで下記式（８）を得ることができる。
【００５７】
Ｒｃ＝Ｔ１・Ｐｍ・ｉＳｒ・Ｔ２                                    ・・・（８）
【００５８】
Ｐｐの左上の座標を（０，０）とした場合、第１の予測ブロック内の画素を（０，０）からの相対座標を用いてｐ（ｘ，ｙ）と表した場合、ＰｍとＰｐの成分は、それぞれ以下のようになる。
【００５９】
【数１】
2011188007.tif 000003
【００６０】
ＰｍとＰｐの関係を下記式（９）とする。
【００６１】
Ｐｍ＝Ｐｐ＋Ｚ                                                    ・・・（９）
【００６２】
Ｚは、第１列が（Ｂｃ＿ｌ−Ｂｐ＿ｌ）に等しく、残りの列はすべての成分が０の行列である。したがって、下記式（１０）を得ることができる。
【００６３】
Ｒｃ＝Ｔ１・（Ｐｐ＋Ｚ）・ｉＳｒ・Ｔ２
＝Ｔ１・（Ｐｐ＋Ｚ）・Ｉ・ｉＳｒ・Ｔ２
＝Ｔ１・（Ｐｐ＋Ｚ）・Ｔ２・ｉＴ２・ｉＳｒ・Ｔ２
＝（Ｔ１・（Ｐｐ＋Ｚ）・Ｔ２）・（ｉＴ２・ｉＳｒ・Ｔ２）
＝（Ｔ１・Ｐｐ・Ｔ２＋Ｔ１・Ｚ・Ｔ２）・（ｉＴ２・ｉＳｒ・Ｔ２）          
・・・（１０）
【００６４】
なお、ＩはＮ×Ｎ要素の単位行列である。Ｒｐは、Ｔ１・Ｐｐ・Ｔ２であるため、Ｒｃを下記式（１１）にすることができる。
【００６５】
Ｒｃ＝（Ｒｐ＋Ｔ１・Ｚ・Ｔ２）・（ｉＴ２・ｉＳｒ・Ｔ２）        ・・・（１１）
【００６６】
【数２】
2011188007.tif 000004
【００６７】
上記式（１）のＺ・Ｔ２は、上記式（１２）である。また、Ｔ２２、・・・、Ｔ２ｎはそれぞれＴ２の２行目、・・・、ｎ行目、０は、ｎ行ｎ―１列の零行列である。よって、下記式（１３）となり、上記式（１）が得られる。
【００６８】
Ｒｃ＝｛Ｒｐ＋Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）・Ｔ２＿ｕ｝・（ｉＴ２・ｉＳｒ・Ｔ２）                                                                ・・・（１３）
【００６９】
ここで、従来での演算量を説明する。従来では、上記式（５）のようにＮ×Ｎ要素の行列同士の演算を２回おこなう。Ｎ×Ｎ要素の行列同士の乗算では、従来の画像処理装置は、乗算結果の各要素を求めるのに乗算Ｎ回、加算をＮ−１回おこなう。したがって、Ｎ×Ｎ要素の行列同士の乗算回数は、乗算がＮ＾３回（「＾」は乗数を示し、Ｎ＾３はＮの３乗である。）、加算が（Ｎ−１）・Ｎ＾２回である。変換結果を算出するには、Ｎ×Ｎ要素の行列同士の乗算を２回おこなうので、一のブロックの直交変換では、乗算を２Ｎ＾３回、加算を（Ｎ−１）・２Ｎ＾２回実施する。なお、「＾２」は、２乗であることを示す。
【００７０】
つぎに、本発明での演算量を、上記式（１）を例に挙げて説明する。
・Ｂｃ＿ｌ−Ｂｐ＿ｌ：減算Ｎ回
・Ｔ１と（Ｂｃ＿ｌ−Ｂｐ＿ｌ）の乗算：「乗算Ｎ回、加算Ｎ−１回」をＮ回、すなわち乗算Ｎ＾２回、加算Ｎ（Ｎ−１）回
・（Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ））とＴ２＿ｕの乗算：乗算Ｎ＾２回
・Ｒｐと｛Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）・Ｔ２＿ｕ｝との加算：加算Ｎ＾２回
・［Ｒｐ＋｛Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）・Ｔ２＿ｕ｝］と（ｉＴ２・Ｓｒ・Ｔ２）の乗算：乗算Ｎ＾３回、加算を（Ｎ−１）・Ｎ＾２回
【００７１】
したがって、乗算が２Ｎ＾２回＋Ｎ＾３回、加減算がＮ回＋Ｎ・（Ｎ−１）回＋Ｎ＾２回＋（Ｎ−１）・Ｎ＾２回となり、従来と比較して高速化することができる。
【００７２】
上記式（１）の（ｉＴ２・Ｓｒ・Ｔ２）と、上記式（２）の（ｉＴ２・Ｓｌ・Ｔ２）と、上記式（３）の（Ｔ１・Ｓｄ・ｉＴ１）と、上記式（４）の（Ｔ１・Ｓｕ・ｉＴ１）とについては、直交変換行列（Ｔ１、Ｔ２）が決定された時点で決定される。したがって、実際には、Ｎ×Ｎ要素の行列である。
【００７３】
なお、図示では、４×４のブロックであるが、Ｎ×Ｎのブロック（Ｎ＞＝４）であればよく、上記式（１）〜（４）においての直交変換についても特に規定しない。
【００７４】
図３は、実施の形態１にかかる画像処理装置の一例を示す説明図である。画像処理装置３００は、差分値算出回路３０１と、第１の直交変換回路３０２と、第２の直交変換回路３０３と、係数値算出回路３０４を備えている。ここでは、上記式（１）を例に挙げて説明する。
【００７５】
差分値算出回路３０１は、上記式（１）の（Ｂｃ＿ｌ−Ｂｐ＿ｌ）の処理をおこない、具体的には、減算回路である。
【００７６】
つぎに、第１の直交変換回路３０２は、上記式（１）のＴ２と差分値行列との乗算処理をおこない、具体的には、たとえば、乗算回路と加算回路により構成される。
【００７７】
つぎに、第２の直交変換回路３０３は、上記式（１）のＴ２＿ｕとの乗算処理をおこない、具体的には、たとえば、乗算回路と加算回路により構成される。
【００７８】
そして、係数値算出回路３０４は、上記式（１）のＲｐとの加算および（ｉＴ２・Ｓｒ・Ｔ２）との乗算であり、具体的には、乗算回路と加算回路である。
【００７９】
図示していないが、探索方法については、従来から知られている動きベクトル探索（たとえば、全探索）の処理を用いればよく特に限定しない。なお、画像処理装置３００は、少なくとも探索開始点である１つの動きベクトル候補については、上記式（５）の処理を実行する。
【００８０】
また、上述の例では、第２の予測ブロックは、第１の予測ブロックが探索方向に１画素シフトしたブロックであるが、Ｍ（１≦Ｍ＜Ｎ／２）画素シフトした場合にも高速化をおこなうことができる。
【００８１】
まず、上記式（１）の（Ｂｃ＿ｌ−Ｂｐ＿ｌ）については、Ｂｃ＿ｌおよびＢｐ＿ｌがＮ行×Ｍ列である。そして、Ｔ２＿ｕは、Ｍ行Ｎ列である。また、（ｉＴ２・Ｓｒ・Ｔ２）については、たとえば、２画素シフトされた場合、（ｉＴ２・Ｓｒ・Ｓｒ・Ｔ２）とるが、Ｔ１、Ｔ２が決定された時点で（ｉＴ２・Ｓｒ・Ｓｒ・Ｔ２）の結果も決定しているのでＮ行Ｎ列である。したがって、演算量は、下記のようになります。
【００８２】
・Ｂｃ＿ｌ−Ｂｐ＿ｌ：減算Ｎ×Ｍ回
・Ｔ１と（Ｂｃ＿ｌ−Ｂｐ＿ｌ）の乗算：乗算Ｎ＾２回、加算Ｎ（Ｎ−１）回
・（Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ））とＴ２＿ｕの乗算：乗算Ｎ＾２回
・Ｒｐと｛Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）・Ｔ２＿ｕ｝との加算：加算Ｎ＾２回
・［Ｒｐ＋｛Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）・Ｔ２＿ｕ｝］と（ｉＴ２・Ｓｒ・Ｔ２）の乗算：乗算Ｎ＾３回、加算を（Ｎ−１）・Ｎ＾２回
【００８３】
乗算がＭ×Ｎ＾２回＋Ｍ×Ｎ＾２回＋Ｎ＾３回であり、加減算がＮ×Ｍ回＋Ｍ×Ｎ（Ｎ−１）＋（Ｍ−１）×Ｎ＾２回＋Ｎ＾２回＋（Ｎ−１）×Ｎ＾２回である。
【００８４】
よって、Ｎ＝８の場合、１画素〜３画素シフトした場合に高速化することができる。従来では、Ｎ＝８の場合、乗算が１０２４回で、加算が８９６回である。実施の形態１においては、Ｎ＝８で第２の予測ブロックが第１の予測ブロックから横方向に１画素シフトした場合、乗算が６４０回で、加算が５１２回である。第２の予測ブロックが第１の予測ブロックから横方向に２画素シフトした場合、乗算が７６８回で、加算が６４０回である。第２の予測ブロックが第１の予測ブロックから横方向に３画素シフトした場合、乗算が８９６回で、加算が７６８回である。
【００８５】
また、少なくとも１個のベクトルについては、必ず従来と同様の二次元直交変換を施さなければならない。従来と同様の二次元直交変換をおこなうベクトルの個数については、動きベクトル探索の探索方法によって異なる。
【００８６】
図４は、スパイラルサーチによる動きベクトル探索例を示す説明図である。たとえば、動きベクトル探索をスパイラルサーチでおこなう場合、ベクトルの指す参照画像の左上の画素は図のように変化する。各ベクトルは隣接するベクトルのｘ成分、またはｙ成分が１だけ違うようなベクトル列を形成する。よって、スパイラルサーチでは、従来と同様の二次元直交変換については、探索開始の中心点でのみ行えばよい。
【００８７】
（実施の形態２）
つぎに、実施の形態２では、Ｍ＝１、かつ実施の形態１で示した式（１）〜（４）のＴ１，Ｔ２がアダマール変換行列の場合に演算量を削減する例について説明する。アダマール変換行列は、各要素が「−１」、「１」の行列である。また、実施の形態２では、実施の形態１で示した構成と同一構成には同一符号を付し、当該構成の説明を省略する。
【００８８】
また、実施の形態１で示したようにＴ２＿ｕは、Ｔ２の最上行を要素に持つ行ベクトルであり、Ｔ２＿ｄは、Ｔ２の最下行を要素に持つ行ベクトルである。Ｔ２＿ｕおよびＴ２＿ｄの各要素は、「１」または「−１」である。
【００８９】
Ｔ２＿ｕやＴ２＿ｄは、設計時にＴ２が決定された時点で決定されるため、定数である。よって、上記式（１）、（２）の一次元直交変換後の差分（Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ））は、Ｎ×１の変換係数行列であるため、Ｎ×１の変換係数行列とＴ２＿ｕまたはＴ２＿ｄとの乗算は、単に列ベクトルの複製および符号変換のみで実現することができる。
【００９０】
実施の形態１で示したようにＴ１＿ｌは、Ｔ１の最左列を要素に持つ列ベクトルであり、Ｔ１＿ｒは、Ｔ１の最右列を要素に持つ列ベクトルである。Ｔ１＿ｌおよびＴ１＿ｒの各要素は、「１」または「−１」である。
【００９１】
Ｔ１＿ｌやＴ１＿ｒは、設計時にＴ１が決定された時点で決定されるため、定数である。よって、上記式（３）、（４）の一次元直交変換後の差分（（Ｂｃ＿ｒ−Ｂｐ＿ｒ）・Ｔ２）は、１×１の変換係数行列であるため、１×Ｎの変換係数行列とＴ１＿ｌやＴ１＿ｒとの乗算は、単に行ベクトルの複製および符号変換のみで実現することができる。
【００９２】
実施の形態２では、たとえば、Ｎ＝４とし、Ｔ１、Ｔ２を下記式（１４）とすると、Ｔ２＿ｄ、Ｔ２＿ｕ、Ｔ１＿ｌ、Ｔ１＿ｒは、それぞれ下記式（１５）〜（１８）である。
【００９３】
【数３】
2011188007.tif 000005
【００９４】
図５−１は、実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その１）である。まず、ｋ１＿０〜ｋ１＿３を要素とする列ベクトルが、上記式（１）の一次元直交変換後の差分（Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ））である。上記式（１６）のようにＴ２＿ｕの各要素は、すべて「１」であるため、ｋ１＿０〜ｋ１＿３を要素とする列ベクトルが３つ複製されて４×４要素の行列が生成される。
【００９５】
図５−２は、実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その２）である。まず、ｋ２＿０〜ｋ２＿３を要素とする列ベクトルが、上記式（２）の一次元直交変換後の差分（Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ））である。まず、ｋ２＿０〜ｋ２＿３を要素とする列ベクトルが３つ複製されて、４×４の行列が生成される。つぎに、上記式（１５）のようにＴ２＿ｄの要素は、１列目と３列目が「１」であり、２列目と４列目が「−１」であるため、２列目および４列目の各要素の符号が変換される。
【００９６】
図５−３は、実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その３）である。まず、ｋ３＿０〜ｋ３＿３を要素とする行ベクトルが、上記式（３）の一次元直交変換後の差分｛（Ｂｃ＿ｒ−Ｂｐ＿ｒ）・Ｔ２｝である。上記式（１７）のようにＴ１＿ｌの各要素は、すべて「１」であるため、ｋ３＿０〜ｋ３＿３を要素とする行ベクトルが３つ複製されて４×４の行列が生成される。
【００９７】
図５−４は、実施の形態２においての第２の直交変換回路３０３の具体的な処理例を示す説明図（その４）である。まず、ｋ４＿０〜ｋ４＿３を要素とする行ベクトルが、上記式（４）の一次元直交変換後の差分｛（Ｂｃ＿ｒ−Ｂｐ＿ｒ）・Ｔ２｝である。まず、ｋ４＿０〜ｋ４＿３を要素とする列ベクトルが３つ複製されて、４×４の行列が生成される。
【００９８】
つぎに、上記式（１８）のようにＴ１＿ｒの要素は、１行目と３行目が「１」であり、２行目と４行目が「−１」であるため、２行目および４行目の各要素の符号が変換される。
【００９９】
したがって、実施の形態２にかかる画像処理装置では、第２の直交変換回路３０３の具体的な処理を複製処理および符号変換処理とすることで、演算量を削減できる。
【０１００】
また、上述では、第２の直交変換後にＲｐと第２の直交変換処理後のＮ×Ｎ要素の変換係数行列とを加算している。ここで、上述のように符号の変換でなく、Ｒｐとの加算に代わって変換係数行列の要素が「−１」に対応する行または列に関しては、Ｒｐとの加算を減算に置き換えることができる。
【０１０１】
上記式（１）を例に挙げると、画像処理装置が、第２の直交変換回路３０３によりＮ×１要素の変換係数行列を（Ｎ−１）個複製してＮ×Ｎ要素の変換係数行列を生成する。
【０１０２】
つぎに、画像処理装置が、Ｔ２＿ｕは、すべて「１」であるため、係数値算出回路３０４によりＮ×Ｎ要素の変換係数行列と第１の変換係数行列とを加算する。そして、加算後のＮ×Ｎ要素の変換係数行列に行列の入れ替えに関する入れ替え行列（ｉＴ２・Ｓｒ・Ｔ２）を乗算して第２の変換係数行列（Ｒｃ）を算出する。
【０１０３】
上記式（２）を例に挙げると、画像処理装置３００が、第２の直交変換回路３０３によりＮ×１要素の変換係数行列を（Ｎ−１）個複製してＮ×Ｎ要素の変換係数行列を生成する。
【０１０４】
つぎに、画像処理装置３００が、Ｔ２＿ｄは、２列目と３列目が「−１」であるため、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の１列目とＮ×Ｎ要素の変換係数行列の１列目とを加算する。そして、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の２列目とＮ×Ｎ要素の変換係数行列の２列目とを減算し、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の３列目とＮ×Ｎ要素の変換係数行列の３列目とを減算する。さらに、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の４列目とＮ×Ｎ要素の変換係数行列の４列目とを加算する。そして、加減算後のＮ×Ｎ要素の変換係数行列に行列の入れ替えに関する入れ替え行列（ｉＴ２・Ｓｌ・Ｔ２）を乗算して第２の変換係数行列（Ｒｃ）を算出する。
【０１０５】
上記式（３）を例に挙げると、画像処理装置３００が、第２の直交変換回路３０３により１×Ｎ要素の変換係数行列を（Ｎ−１）個複製してＮ×Ｎ要素の変換係数行列を生成する。
【０１０６】
つぎに、画像処理装置３００が、Ｔ１＿ｌの要素は、すべて「１」であるため、係数値算出回路３０４によりＮ×Ｎ要素の変換係数行列と第１の変換係数行列とを加算する。そして、加算後のＮ×Ｎ要素の変換係数行列に行列の入れ替えに関する入れ替え行列（Ｔ１・Ｓｄ・ｉＴ１）を乗算して第２の変換係数行列（Ｒｃ）を算出する。
【０１０７】
上記式（２）を例に挙げると、画像処理装置３００が、第２の直交変換回路３０３によりＮ×１要素の変換係数行列を（Ｎ−１）個複製してＮ×Ｎ要素の変換係数行列を生成する。
【０１０８】
つぎに、画像処理装置３００が、Ｔ１＿ｒは、２行目と４行目が「−１」であるため、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の１行目とＮ×Ｎ要素の変換係数行列の１行目とを加算する。そして、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の２行目とＮ×Ｎ要素の変換係数行列の２行目とを減算し、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の３行目とＮ×Ｎ要素の変換係数行列の３行目とを加算する。さらに、係数値算出回路３０４によりＮ×Ｎ要素の第１の変換係数行列の４行目とＮ×Ｎ要素の変換係数行列の４行目とを減算する。そして、加減算後のＮ×Ｎ要素の変換係数行列に行列の入れ替えに関する入れ替え行列（Ｔ１・Ｓｕ・ｉＴ１）を乗算して第２の変換係数行列（Ｒｃ）を算出する。
【０１０９】
したがって、実施の形態２にかかる画像処理装置３００では、直交変換行列をアダマール行列とすることで、第１の直交変換回路３０２の処理を加算処理または減算処理のみで実現でき、演算量を削減できる。さらに、第２の直交変換回路３０３の具体的な処理を複製処理とし、係数値算出回路３０４での加算処理を第２の直交変換行列に基づいて加算処理または減算処理とすることで演算量を削減できる。
【０１１０】
（実施の形態３）
つぎに、実施の形態３では、Ｎ＝４の場合のみの場合においての高速化処理について説明する。実施の形態３では、原画像内の対象ブロックの直交変換から現ベクトルの直交変換結果を算出する処理を、現ベクトルの直交変換結果を算出せずに高速化する。
【０１１１】
まず、Ｓｒ、Ｓｄ、Ｓｕ、Ｓｌがそれぞれ下記式（１９）、（２０）である。さらに、Ｔ１とＴ２が設計時に決定されているため、上記式（１）の（ｉＴ２・Ｓｒ・Ｔ２）は、下記式（２１）であり、上記式（２）の（ｉＴ２・Ｓｌ・Ｔ２）は、下記式（２２）である。そして、上記式（３）の（Ｔ１・Ｓｄ・ｉＴ１）は、下記式（２３）であり、上記式（４）の（Ｔ１・Ｓｕ・ｉＴ１）は、下記式（２４）である。
【０１１２】
【数４】
2011188007.tif 000006
【０１１３】
上記式（１）〜（４）は、Ｒｃの算出に関する式であるが、ＳＡＴＤでは、原画内の対象ブロックの変換結果（Ｃ）からＲｃを引いて、各要素の絶対値を合計する。
【０１１４】
上記式（１）の（ｉＴ２・Ｓｒ・Ｔ２）は、上記式（２１）であるため、上記式（１）のように４×４要素の行列に対して（ｉＴ２・Ｓｒ・Ｔ２）を右からかけると下記式（２５）のようになる。
【０１１５】
【数５】
2011188007.tif 000007
【０１１６】
Ｔ１＿０〜Ｔ１＿１５を要素に持つ４×４要素の行列が、上記式（１）の［Ｒｐ＋｛Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ）｝・Ｔ２＿ｕ］の算出結果とする。したがって、（ｉＴ２・Ｓｒ・Ｔ２）の右からの乗算は、４×４要素の行列のうちの３列目と４列目を入れ替えて、入れ替え後の２列目と４列目の符号を反転することに相当する。
【０１１７】
図６−１は、入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その１）である。Ｈ１＿０からＨ１＿３が、１列目であり、Ｈ１＿４からＨ１＿７が２列目であり、Ｈ１＿８からＨ１＿１１が３列目であり、Ｈ１＿１２からＨ１＿１５が４列目である。
【０１１８】
まず、３列目と４列目が入れ替えられ、つぎに、２列目と４列目の符号が変換されている。これにより、４×４要素の行列と（ｉＴ２・Ｓｒ・Ｔ２）との乗算処理が、列の入れ替え処理および符号の反転処理のみとなり、高速化を図ることができる。
【０１１９】
そして、対象ブロックから反転処理後の４×４要素の行列が減算される。
【０１２０】
つぎに、上記式（２）の（ｉＴ２・Ｓｌ・Ｔ２）は、上記式（２２）であるため、上記式（２）のように４×４要素の行列に対して（ｉＴ２・Ｓｌ・Ｔ２）を右からかけると下記式（２６）のようになる。
【０１２１】
【数６】
2011188007.tif 000008
【０１２２】
したがって、（ｉＴ２・Ｓｌ・Ｔ２）の右からの乗算は、４×４要素の行列のうちの３列目と４列目を入れ替えて、入れ替え後の２列目と３列目の符号を反転することに相当する。
【０１２３】
図６−２は、入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その２）である。Ｈ２＿０からＨ２＿３が、１列目であり、Ｈ２＿４からＨ２＿７が２列目であり、Ｈ２＿８からＨ２＿１１が３列目であり、Ｈ２＿１２からＨ２＿１５が４列目である。まず、３列目と４列目が入れ替えられ、つぎに、２列目と３列目の符号が変換されている。これにより、４×４要素の行列と（ｉＴ２・Ｓｌ・Ｔ２）との乗算処理が、列の入れ替え処理および符号の反転処理のみとなり、高速化を図ることができる。
【０１２４】
つぎに、上記式（３）の（Ｔ１・Ｓｄ・ｉＴ１）は、上記式（２３）であるため、上記式（３）のように４×４要素の行列に対して（Ｔ１・Ｓｄ・ｉＴ１）を左からかけると下記式（２７）のようになる。
【０１２５】
【数７】
2011188007.tif 000009
【０１２６】
したがって、（Ｔ１・Ｓｄ・ｉＴ１）を左から４×４要素の行列に乗算するのは、４×４要素の行列のうちの３列目と４列目を入れ替えて、入れ替え後の２列目と３列目の符号を反転することに相当する。
【０１２７】
図６−３は、入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その３）である。Ｈ３＿０、Ｈ３＿４、Ｈ３＿８、Ｈ３＿１２が、１行目であり、Ｈ３＿１、Ｈ３＿５、Ｈ３＿９、Ｈ３＿１３が、２行目であり、Ｈ３＿２、Ｈ３＿６、Ｈ３＿１０、Ｈ３＿１４が、３行目であり、Ｈ３＿３、Ｈ３＿７、Ｈ３＿１１、Ｈ３＿１５が、４行目である。まず、３行目と４行目が入れ替えられ、つぎに、２行目と３行目の符号が変換されている。これにより、４×４要素の行列と（Ｔ１・Ｓｄ・ｉＴ１）との乗算処理が、列の入れ替え処理および符号の反転処理のみとなり、高速化を図ることができる。
【０１２８】
つぎに、上記式（４）の（Ｔ１・Ｓｕ・ｉＴ１）は、上記式（２４）であるため、上記式（４）のように４×４要素の行列に対して（Ｔ１・Ｓｕ・ｉＴ１）を左からかけると下記式（２８）のようになる。
【０１２９】
【数８】
2011188007.tif 000010
【０１３０】
したがって、（Ｔ１・Ｓｕ・ｉＴ１）を左から４×４要素の行列に乗算するのは、４×４要素の行列のうちの３行目と４行目を入れ替えて、入れ替え後の２行目と４行目の符号を反転することに相当する。
【０１３１】
図６−４は、入れ替え行列との乗算処理が入れ替え処理および符号変換処理に置き換えられた例を示す説明図（その４）である。Ｈ４＿０、Ｈ４＿４、Ｈ４＿８、Ｈ４＿１２が、１行目であり、Ｈ４＿１、Ｈ４＿５、Ｈ４＿９、Ｈ４＿１３が、２行目であり、Ｈ４＿２、Ｈ４＿６、Ｈ４＿１０、Ｈ４＿１４が、３行目であり、Ｈ４＿３、Ｈ４＿７、Ｈ４＿１１、Ｈ４＿１５が、４行目である。
【０１３２】
まず、３行目と４行目が入れ替えられ、つぎに、２行目と４行目の符号が変換されている。これにより、４×４要素の行列と（Ｔ１・Ｓｕ・ｉＴ１）との乗算処理が、列の入れ替え処理および符号の反転処理のみとなり、高速化を図ることができる。
【０１３３】
上述の係数値の算出に関する乗算処理では、入れ替え処理後に符号を変換している。動きベクトル検出処理では、実際には、第２の予測ブロックに関する第２の変換係数行列が算出された後、対象ブロックに関する第３の変換係数行列から第２の変換係数行列が減算される。係数値の算出に関する乗算処理では、入れ替え処理のみとし、第３の変換係数行列（Ｒｐ）から第２の変換係数行列を減算する際の処理の一部を加算に置き換えることで、第３の変換係数行列（Ｒｐ）と第２の変換係数行列との差分を算出できる。
【０１３４】
上記式（１）を例に挙げると、上述のようにＮ×Ｎ要素の変換係数行列の３列目と４列目が入れ替えられる。そして、第３の変換係数行列（Ｒｐ）の１列目から第２の変換係数行列の１列目を減算し、第３の変換係数行列（Ｒｐ）の２列目から第２の変換係数行列の２列目を加算する。さらに、第３の変換係数行列（Ｒｐ）の３列目から第２の変換係数行列の３列目を減算し、第３の変換係数行列（Ｒｐ）の４列目から第２の変換係数行列の４列目を加算する。
【０１３５】
上記式（２）を例に挙げると、上述のようにＮ×Ｎ要素の変換係数行列の３列目と４列目が入れ替えられる。そして、第３の変換係数行列（Ｒｐ）の１列目から第２の変換係数行列の１列目を減算し、第３の変換係数行列（Ｒｐ）の２列目から第２の変換係数行列の２列目を加算する。さらに、第３の変換係数行列（Ｒｐ）の３列目から第２の変換係数行列の３列目を加算し、第３の変換係数行列（Ｒｐ）の４列目から第２の変換係数行列の４列目を減算する。
【０１３６】
上記式（３）を例に挙げると、上述のようにＮ×Ｎ要素の変換係数行列の３行目と４行目が入れ替えられる。そして、第３の変換係数行列（Ｒｐ）の１行目から第２の変換係数行列の１行目を減算し、第３の変換係数行列（Ｒｐ）の２行目から第２の変換係数行列の２行目を加算する。さらに、第３の変換係数行列（Ｒｐ）の３行目から第２の変換係数行列の３行目を加算し、第３の変換係数行列（Ｒｐ）の４行目から第２の変換係数行列の４行目を減算する。
【０１３７】
なお、入れ替え後のＮ×Ｎ要素の変換係数行列と、第２の予測ブロックに関する第２の変換係数行列とは異なる。
【０１３８】
上記式（４）を例に挙げると、上述のようにＮ×Ｎ要素の変換係数行列の３行目と４行目が入れ替えられる。そして、第３の変換係数行列（Ｒｐ）の１行目から第２の変換係数行列の１行目を減算し、第３の変換係数行列（Ｒｐ）の２行目から第２の変換係数行列の２行目を加算する。さらに、第３の変換係数行列（Ｒｐ）の３行目から第２の変換係数行列の３行目を減算し、第３の変換係数行列（Ｒｐ）の４行目から第２の変換係数行列の４行目を加算する。これにより、演算量を削減することができる。
【０１３９】
また、入れ替え後のＮ×Ｎ要素の変換係数行列と、第２の予測ブロックに関する第２の変換係数行列とは異なる。よって、第２の変換係数行列（Ｒｃ）が算出されないため、現ベクトルを用いて次ベクトルのＳＡＴＤを求めるには、別の値を用いる。
【０１４０】
ここでは、上記式（２）のみを例に挙げて説明する。上記式（２２）は、下記式（２９）のようにＳとＬの２つの行列に分解できる。
【０１４１】
【数９】
2011188007.tif 000011
【０１４２】
（Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ））・Ｔ２＿ｄをＢとすると、下記式（３０）のようになる。
【０１４３】
Ｃ−Ｒｃ＝Ｃ−（Ｒｐ＋Ｂ）・Ｓ・Ｌ                              ・・・（３０）
【０１４４】
上記式（２９）において、Ｌは、Ｃとの減算の一部を加算へ置き換えることで実現できる。ここで、Ｃとの加減算および置き換え処理を◎を用いて表すと下記式（３１）のようになる。
【０１４５】
Ｃ−Ｒｃ＝Ｃ◎（Ｒｐ＋Ｂ）・Ｓ                                  ・・・（３１）
【０１４６】
また、現ベクトルの変換結果を用いて次ベクトルの変換結果を算出するには、Ｒｃの代わりにｉＬ（Ｌの逆行列）・Ｒｃを用いる。次ベクトルが現ベクトルの上下左右いずれかの方向に１画素移動したものであったとしても、Ｌ・（ｉＭ・Ｒｐ）＋Ｐｃ、またはＰｃ＋Ｍ・（ｉＭ・Ｒｐ）という演算が行われ、Ｍの左からの乗算は、Ｐｃの加算の一部を減算とすることに置き換えることができる。
【０１４７】
つぎに、実施の形態３をＨ．２６４エンコーダに適用した際の動きベクトル探索部の構成の一例を説明する。ここでは、動きベクトル探索部全体ではなく、原画像と参照画像をフレームメモリから取得した後ＳＡＴＤ算出をおこなう部分までの回路構成を説明する。
【０１４８】
図７は、マクロブロックの一例を示す説明図である。図７には、原画像内の現マクロブロックと参照画像内で対象マクロブロックと同一位置にある参照マクロブロックが示されている。現マクロブロックサイズおよび参照マクロブロックサイズは、４×４ブロックの集合であり、各ブロックサイズは、４×４画素である。
【０１４９】
実施の形態３では、動きベクトル探索はマクロブロックごとにおこなわれ、水平方向に並んだ５個のベクトルのＳＡＴＤを並列に算出する。ここで、水平方向に並んだ５個のベクトル０〜ベクトル４の一例について説明する。
【０１５０】
原画像内のマクロブロック内にはＢＫ１＿１〜ＢＫ１＿４がある。参照画像内のマクロブロック内にはＢＫ２＿１〜ＢＫ２＿４がある。ここでは、原画像内のＢＫ１＿１〜ＢＫ１＿４からベクトル０で指されているブロックをＢＫ２＿１〜ＢＫ２＿４とする。ＢＫ１＿１と同一位置にある参照画像内のブロックは、ＢＫ２＿１である。よって、ＢＫ２＿１を示す動きベクトルが、ＢＫ１＿１に関するベクトル０である。
【０１５１】
また、ＢＫ１＿２と同一位置にある参照画像内のブロックは、ＢＫ２＿２であり、ＢＫ２＿２を示す動きベクトルが、ＢＫ１＿２に関するベクトル０である。そして、ＢＫ１＿３と同一位置にある参照画像内のブロックは、ＢＫ２＿３であり、ＢＫ２＿３を示す動きベクトルが、ＢＫ１＿３に関するベクトル０である。ＢＫ１＿４と同一位置にある参照画像内のブロックは、ＢＫ２＿４であり、ＢＫ２＿４を示す動きベクトルが、ＢＫ１＿４に関するベクトル０である。
【０１５２】
そして、ＢＫ１＿１に関するベクトルを例に挙げると、ＢＫ２＿１を横方向に−１シフトしたブロックを示す動きベクトルが、ＢＫ１＿１に関するベクトル１である。さらに、横方向に−１シフトしたブロックを示す動きベクトルが、ＢＫ１＿１に関するベクトル２であり、以降、ＢＫ１＿１に関するベクトル３、４までが図示されている。上述のように本実施の形態３では、ベクトル０〜４までの５個のベクトルに関するＳＡＴＤを並列に算出する。
【０１５３】
ここで、５個のベクトルのうち最右のベクトルの変換結果をもとに最右のベクトルよりも左の４点の変換結果を求める構成とする。以降の数式の添え字は対象ベクトルの最右ベクトルとのｘ座標の差を表す。
【０１５４】
各ベクトルの原画像内のブロックの変換結果と参照画像内のブロックの変換結果の差分Ｄｘは以下のようになる。
【０１５５】
・Ｄ０＝Ｃ−Ｒ０
・Ｄ１＝Ｃ−Ｒ１＝Ｃ−（Ｒ０△Ｂ１）・Ｓ・Ｌ＝Ｃ◎（Ｒ０△Ｂ１）・Ｓ
・Ｄ２＝Ｃ−Ｒ２＝Ｃ−（Ｒ１△Ｂ２）・Ｓ・Ｌ＝Ｃ◎（Ｒ１△Ｂ２）・Ｓ
・Ｄ３＝Ｃ−Ｒ３＝Ｃ−（Ｒ２△Ｂ３）・Ｓ・Ｌ＝Ｃ◎（Ｒ２△Ｂ３）・Ｓ
・Ｄ４＝Ｃ−Ｒ４＝Ｃ−（Ｒ３△Ｂ４）・Ｓ・Ｌ＝Ｃ◎（Ｒ３△Ｂ４）・Ｓ
【０１５６】
ここで、Ｂｎは列ベクトル（Ｔ１・（Ｂｃ＿ｌ−Ｂｐ＿ｌ））を４つ並べた４×４行列、△と◎は同位置の行列成分に対して、第１列と第３列は加算、第２列と第４列は左辺成分から右辺成分を減ずる演算をおこなう演算子である。これらＤ０〜Ｄ４の絶対値和が各ベクトルにおけるＳＡＴＤとなる。
【０１５７】
また、Ｒ１＝（Ｒ０△Ｂ１）・Ｓ・Ｌにより、Ｐ１＝（Ｒ０△Ｂ１）・Ｓと置くと、Ｒ１△Ｂ２＝Ｐ１・Ｌ△Ｂ２＝Ｐ１▲Ｂ２となる。Ｍは右からかけると、第２列と第４列の符号を反転させる行列なので、▲は通常の行列加算演算子＋と等しい。Ｄ２〜Ｄ３をこの方法によって変形して、最終的に以下を得る。
【０１５８】
Ｄ０＝Ｃ−Ｒ０                                                  ・・・（３２）
【０１５９】
Ｄ１＝Ｃ−Ｒ１＝Ｃ◎（Ｒ０△Ｂ１）・Ｓ                          ・・・（３３）
【０１６０】
Ｄ２＝Ｃ−Ｒ２＝Ｃ◎（Ｐ１＋Ｂ２）・Ｓ                          ・・・（３４）
【０１６１】
Ｄ３＝Ｃ−Ｒ３＝Ｃ◎（Ｐ２＋Ｂ３）・Ｓ                          ・・・（３５）
【０１６２】
Ｄ４＝Ｃ−Ｒ４＝Ｃ◎（Ｐ３＋Ｂ４）・Ｓ                          ・・・（３６）
【０１６３】
図８は、実施の形態３にかかる画像処理装置の一例を示す説明図である。図８に示す画像処理装置８００は、セレクタと、二次元アダマール変換回路と、予測ブロック変換結果保持回路と、対象ブロック変換結果保持回路と、予測ブロック保持回路と、ユニット０〜ユニット４と、を備える構成である。つぎに、ユニット０〜ユニット４について説明する。
【０１６４】
ユニット０は、ユニット０＿１〜ユニット０＿４を備え、それぞれは同一構成である。ユニット０では、ベクトル０に対応するＳＡＴＤを算出する。
【０１６５】
ユニット１は、ユニット１＿１〜ユニット１＿４を備え、それぞれは同一構成である。ユニット１では、ベクトル１に対応するＳＡＴＤを算出する。
【０１６６】
ユニット２は、ユニット２−３＿１〜ユニット２−３＿４を備え、ユニット３は、ユニット２−３＿５〜ユニット２−３＿８を備え、ユニット２−３＿１〜ユニット２−３＿８は、同一構成である。ユニット２では、ベクトル２に対応するＳＡＴＤを算出し、ユニット３では、ベクトル３に対応するＳＡＴＤを算出する
【０１６７】
ユニット４は、ユニット２−３＿９と、ユニット０＿５〜ユニット０＿７を備え、ユニット２−３＿９は、ユニット２−３＿１と同一構成であり、ユニット０＿５〜ユニット０＿７は、ユニット０＿１と同一構成である。ユニット４は、ベクトル４に対応するＳＡＴＤを算出する。
【０１６８】
図９は、ユニット０＿１〜ユニット０＿７の詳細な説明を示す説明図である。ユニット０＿１〜ユニット０＿７では、それぞれ上記式（３２）を構成し、それぞれ減算回路を４つと、絶対値演算回路を４つと、総和演算回路を備えている。
【０１６９】
ユニット０＿１〜ユニット０＿７では、原画像内の対象ブロックの二次元直交変換結果と参照画像内のブロックの二次元直交変換結果との差分を算出し、それぞれの絶対値をとり、総和を算出してＳＡＴＤを出力する。
【０１７０】
図１０は、ユニット１＿１〜ユニット１＿４の詳細な説明を示す説明図である。ユニット１＿１〜ユニット１＿４では、それぞれ上記式（３３）を構成し、減算回路と、差分保持回路と、一次元アダマール変換回路と、△演算回路と、列入れ替え回路と、◎演算回路と、絶対値演算回路を４つと、総和演算回路を備えている。
【０１７１】
減算回路では、Ｂｃ＿ｌ−Ｂｐ＿ｌに対応する減算処理がおこなわれ、差分値を算出する。そして、減算結果を差分保持回路へ出力する。差分保持回路は、減算結果を保持し、また、あるブロックのための差分の受け取りと、つぎに一次元アダマール変換を施すための差分出力を同時におこなうため、ダブルバッファ構成である。
【０１７２】
一次元アダマール変換回路では、第１の直交変換処理をおこなう。よって、一次元アダマール変換回路では、Ｔ１に対応する加減算がおこなわれる。△演算回路では、上述のように１列目と３列目は加算、２列目と４列目は左辺成分から右辺成分を減ずる演算をおこなう。
【０１７３】
つぎに、列入れ替え回路では、列を入れ替える処理をおこない、◎演算回路では、上述のように１列目と３列目は加算、２列目と４列目は左辺成分から右辺成分を減ずる演算をおこなう。絶対値演算回路と総和演算回路については、公知であるため説明を省略する。
【０１７４】
図８に戻って、ユニット１内部ではユニット０から渡された予測ブロックの二次元直交変換結果（Ｒ０）に△Ｂ１に対応する演算がおこなわれる。Ｂ１は差分保持回路で保持されていた差分に一次元アダマール変換回路によって一次元アダマール変換をおこなうことによって得られる。Ｒ０△Ｂ１に対してＳに相当する列入れ替え処理がおこなわれ、Ｐ１が得られる。Ｐ１は原画変換結果とともに◎演算回路ではＰ１と原画変換結果よりＤ１を得、絶対値の総和がＳＡＴＤとして算出される。また、Ｐ１はユニット２へ送られる。このユニットで算出されるＳＡＴＤはベクトル０のひとつ左を差すベクトル１である。
【０１７５】
よって、ユニット１は前ベクトルの二次元直交変換結果としてＲ０を受け取り、ユニットｎからユニットｎ＋１へはＰｎが渡されている。
【０１７６】
図１１は、ユニット２−３＿１〜ユニット２−３＿９の詳細な説明を示す説明図である。ユニット２−３＿１〜ユニット２−３＿９では、それぞれ上記式（３４）〜（３６）を構成し、減算回路と、差分保持回路と、一次元アダマール変換回路と、＋演算回路と、列入れ替え回路と、◎演算回路と、絶対値演算回路を４つと、総和演算回路を備えている。
【０１７７】
ユニット２−３＿１〜ユニット２−３＿９は
１）△演算回路の代わりに＋演算回路（加算回路）である。
２）Ｒ０の代わりにＰ１が入力される。
３）差分保持回路への入力が１画素左にずれた位置での差分結果である。
【０１７８】
上記１）〜３）以外はユニット１＿１〜ユニット１＿４と同タイミングで同じ演算がおこなわれる。
【０１７９】
図８に戻って、まず、処理対象原画像内のマクロブロックと参照画像内のマクロブロックをフレームメモリから取得する。原画像内のマクロブロックについてはフレームメモリから取り込まれながらブロックごとに二次元アダマール変換処理が施され、対象ブロック変換結果保持回路に格納される。
【０１８０】
また、参照画像内のマクロブロックについてもフレームメモリから取り込まれながらベクトル０である４つのブロックが、ブロックごとに二次元アダマール変換処理が施され、予測ブロック変換結果保持回路に格納される。ここでは、Ｂ２＿１〜Ｂ２＿４に対してアダマール変換処理が施される。さらに、参照画像内のマクロブロックは変換されない状態でも予測ブロック保持回路に格納される。
【０１８１】
予測ブロック保持回路中の画像は以降のＳＡＴＤ算出処理中に使用されるが、たとえば、プリフェッチ機構のようなものを外部に持っていたり、フレームメモリとの帯域が十分に確保できる場合は予測ブロック保持回路を持たない構成も可能である。
【０１８２】
図８の画像処理装置８００では、全探索をベースとし垂直成分（ｙ成分）が等しい５個のベクトルを並列に処理し、さらに、４回繰り返し、２０個のベクトルに関するＳＡＴＤを算出している。従来では、加減算回数は３０４００回であるが、図８の画像処理装置８００では、加減算回数は２４２５６回である。なお、絶対値演算回数はいずれも５１２０回である。
【０１８３】
また、図８で示した原画像、参照画像をフレームメモリから取り込み時に変換する二次元アダマール変換回路は、各ユニット内で用いられる一次元アダマール変換回路と共有する構成も可能である。
【０１８４】
また、実施の形態３では、上記式（２）を例に挙げ、さらに、全探索をベースとして画像処理装置の構成を説明したが、これに限らず、上記式（１）〜（４）や他の探索方法を用いてもよい。
【０１８５】
（実施の形態４）
つぎに、実施の形態４について説明する。実施の形態４では、実施の形態１に示される画像処理装置の各機能がコンピュータによる処理で実現される例を示す。
【０１８６】
（画像処理装置のハードウェア構成）
図１２は、実施の形態にかかる画像処理装置のハードウェア構成を示すブロック図である。図１２において、画像処理装置は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１２０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１２０３と、磁気ディスクドライブ１２０４と、磁気ディスク１２０５と、光ディスクドライブ１２０６と、光ディスク１２０７と、ディスプレイ１２０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）１２０９と、キーボード１２１０と、マウス１２１１と、スキャナ１２１２と、プリンタ１２１３と、を備えている。また、各構成部はバス１２００によってそれぞれ接続されている。
【０１８７】
ここで、ＣＰＵ１２０１は、画像処理装置の全体の制御を司る。ＲＯＭ１２０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１２０３は、ＣＰＵ１２０１のワークエリアとして使用される。磁気ディスクドライブ１２０４は、ＣＰＵ１２０１の制御にしたがって磁気ディスク１２０５に対するデータのリード／ライトを制御する。磁気ディスク１２０５は、磁気ディスクドライブ１２０４の制御で書き込まれたデータを記憶する。
【０１８８】
光ディスクドライブ１２０６は、ＣＰＵ１２０１の制御にしたがって光ディスク１２０７に対するデータのリード／ライトを制御する。光ディスク１２０７は、光ディスクドライブ１２０６の制御で書き込まれたデータを記憶したり、光ディスク１２０７に記憶されたデータをコンピュータに読み取らせたりする。
【０１８９】
ディスプレイ１２０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１２０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【０１９０】
インターフェース（以下、「Ｉ／Ｆ」と略する。）１２０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク１２１４に接続され、このネットワーク１２１４を介して他の装置に接続される。そして、Ｉ／Ｆ１２０９は、ネットワーク１２１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１２０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【０１９１】
キーボード１２１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１２１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【０１９２】
スキャナ１２１２は、画像を光学的に読み取り、画像処理装置内に画像データを取り込む。なお、スキャナ１２１２は、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ１２１３は、画像データや文書データを印刷する。プリンタ１２１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【０１９３】
（画像処理装置の機能的構成）
図１３は、実施の形態４にかかる画像処理装置の機能的構成を示すブロック図である。画像処理装置１３００は、差分値算出部１３０１と、第１の直交変換部１３０２と、第２の直交変換部１３０３と、係数値算出部１３０４と、係数差分値算出部１３０５と、絶対値演算部１３０６と、総和演算部１３０７と、二次元直交変換部１３０８とを含む構成である。各機能（差分値算出部１３０１部〜二次元直交変換部１３０８）は、具体的には、たとえば、図１２に示したＲＯＭ１２０２、ＲＡＭ１２０３、磁気ディスク１２０５、光ディスク１２０７などの記憶装置に記憶されたプログラムをＣＰＵ１２０１に実行させることにより、または、Ｉ／Ｆ１２０９により、各機能を実現する。
【０１９４】
ここで、Ｎ×Ｎ画素を１ブロックとする。また、実施の形態４では、参照画像内で前ベクトルにより示される第１の予測ブロックを横方向に＋１シフトした場合の現ベクトルにより示される第２の予測ブロックの二次元直交変換処理に関して説明する。また、本実施の形態４では、動きベクトル候補に関する絶対値差分和（ＳＡＴＤ）を算出する処理のみを説明する。
【０１９５】
まず、二次元直交変換部１３０８は、参照画像内で前ブロックにより示される第１の予測ブロックをＮ×Ｎ要素の変換係数行列を用いて二次元直交変換する機能を有する。具体的には、たとえば、第１の予測ブロックに関する画素値行列に上述のＴ１を左からかけてＴ２を右からかけることで第１の予測ブロックに関する第１の変換係数行列を算出する。
【０１９６】
さらに、二次元直交変換部１３０８は、原画像内で対象となる第３のブロック（上述では対象ブロック）をＮ×Ｎ要素の変換係数行列を用いて二次元直交変換する機能を有する。具体的には、たとえば、対象ブロックに関する画素値行列に上述のＴ１を左からかけてＴ２を右からかけることで対象ブロックに関する第３の変換係数行列を算出する。
【０１９７】
そして、係数差分値算出部１３０５は、二次元直交変換部により算出された原画像内の対象ブロックに関する第３の変換係数行列から二次元直交変換部により算出された参照画像内の第１の予測ブロックに関する第１の変換係数行列との係数差分値を算出する。
【０１９８】
そして、絶対値演算部１３０６は、係数差分値の絶対値を算出する機能を有する。さらに、総和演算部１３０７は、演算済の係数差分値内の要素の総和を算出して第１の絶対値差分和（ＳＡＴＤ）を算出する。
【０１９９】
つぎに、差分値算出部１３０１は、第２の予測ブロック内で前記第１の予測ブロックに重複していない第１の画素値行列と、第１の予測ブロック内で第２の予測ブロックに重複していない第２の画素値行列との差分となる差分値行列を算出する機能を有する。具体的には、たとえば、ＣＰＵ１２０１が、Ｂｃ＿ｌからＢｐ＿ｌを引くことで差分値行列を算出する。
【０２００】
つぎに、第１の直交変換部１３０２は、差分値算出部１３０１により算出されたＮ×１要素の差分値行列をＮ×Ｎ要素の直交変換行列を用いて一次元直交変換してＮ×１要素の変換係数行列を算出する機能を有する。具体的には、たとてば、ＣＰＵ１２０１が、差分値行列に左からＮ×Ｎ要素の直交変換行列を乗算することで一次元直交変換する。
【０２０１】
第２の直交変換部１３０３は、第１の直交変換部１３０２により算出されたＮ×１要素の変換係数行列を、１×Ｎ要素の直交変換行列を用いて一次元直交変換してＮ×Ｎ要素の変換係数行列を算出する機能を有する。具体的には、たとえば、ＣＰＵ１２０１が、差分値行列に右から１×Ｎ要素の直交変換行列を乗算することで一次元直交変換する。
【０２０２】
係数値算出部１３０４は、第１の予測ブロックに関するＮ×Ｎ要素の第１の変換係数行列と、第１の直交変換部１３０２により変換されたＮ×Ｎ要素の変換係数行列とに基づいて第２の予測ブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する機能を有する。
【０２０３】
つぎに、係数差分値算出部１３０５は、二次元直交変換部により算出された原画像内の対象ブロックに関する第３の変換係数行列から係数値算出部１３０４により算出された参照画像内の第２の予測ブロックに関する第２の変換係数行列との係数差分値を算出する。
【０２０４】
そして、絶対値演算部１３０６は、係数差分値の絶対値を算出する機能を有する。さらに、総和演算部１３０７は、演算済の係数差分値内の要素の総和を算出して第２の絶対値差分和（ＳＡＴＤ）を算出する。
【０２０５】
つぎに、係数値算出部１３０４と、第１の直交変換部１３０２の詳細例と、係数差分値算出部１３０５の他の例を示す。
【０２０６】
（例１）
ここでは、Ｎ×Ｎ画素の第１の予測ブロックを、Ｍ（１＜＝Ｍ＜Ｎ）要素シフトしたＮ×Ｎ画素の第２の予測ブロックの２次元直交変換について説明する。第１の直交変換部１３０２と係数値算出部１３０４以外の機能部については、上述と同一であるため説明を省略する。
【０２０７】
上記式（１）を例に挙げると、第１の直交変換部１３０２は、Ｎ×Ｍ要素の変換係数行列にＭ×Ｎ要素の直交変換行列を掛けることで、Ｎ×Ｎ要素の変換係数行列を算出する。
【０２０８】
つぎに、図１４−１は、係数値算出部１３０４の詳細な構成を示す説明図（その１）である。係数値算出部１３０４は、加算部１４０１と入れ替え部１４０２によって構成されている。加算部１４０１は、第１の予測ブロックに関するＮ×Ｎ要素の第１の変換係数行列と、第１の直交変換部１３０２により変換されたＮ×Ｎ要素の変換係数行列とを加算する機能を有する。
【０２０９】
そして、入れ替え部１４０２は、第１の予測ブロックに関する加算後のＮ×Ｎ要素の変換係数行列に対してＮ×Ｎ要素の入れ替え行列を右から乗算することで第２の予測ブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する。
【０２１０】
（例２）
ここでは、直交変換行列（Ｔ１とＴ２）がアダマール変換行列の場合にＮ×Ｎ画素の第１の予測ブロックを、１要素シフトしたＮ×Ｎ画素の第２の予測ブロックの２次元直交変換について説明する。第１の直交変換部１３０２と係数値算出部１３０４以外の機能部については、上述と同一であるため説明を省略する。
【０２１１】
図１４−２は、第１の直交変換部１３０２の詳細な構成を示す説明図である。第１の直交変換部１３０２は、生成部１４０３と符号変換部１４０４によって構成されている。生成部１４０３は、第１の直交変換部１３０２により算出されたＮ×１要素の変換係数行列を、探索方向にＮ個並べることにより、Ｎ×Ｎ要素の変換係数行列を生成する。上記式（１）を例に挙げて詳細な処理を説明する。
【０２１２】
具体的には、たとえば、ＣＰＵ１２０１が、第１の直交変換部１３０２により算出されたＮ×１要素の変換係数行列をＮ−１個複製し、Ｎ×１要素の変換係数行列と複製したＮ−１個のＮ×１要素の変換係数行列を探索方向（ここでは、横方向）に並べる。
【０２１３】
つぎに、符号変換部１４０４は、生成部１４０３により生成されたＮ×Ｎ要素の変換係数行列の符号を、１×Ｎ要素の直交変換行列（上記式（１）ではＴ２＿ｕ）に基づいて変換する。具体的には、たとえば、ＣＰＵ１２０１が、Ｔ２＿ｕの各要素はすべて「１」であるためＮ×Ｎ要素の変換係数行列の符号を変換せずに出力する。Ｔ２＿ｄのように「−１」がある場合には、Ｎ×Ｎ要素の変換係数行列において対応する列ベクトルの符号を反転する。
【０２１４】
そして、係数値算出部１３０４は、第１の予測ブロックに関するＮ×Ｎ要素の第１の変換係数行列と、符号変換部１４０４により変換されたＮ×Ｎ要素の変換係数行列に基づいて、第２の予測ブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する。具体的には、例１の処理と同一である。
【０２１５】
（例３）
ここでは、例２と同一条件であるが、処理の異なる例を示す。第１の直交変換部１３０２と係数値算出部１３０４以外の機能部については、上述と同一であるため説明を省略する。
【０２１６】
第１の直交変換部１３０２は、生成部１４０３によって構成されている。生成部１４０３は、第１の直交変換部１３０２により算出されたＮ×１要素の変換係数行列を、探索方向にＮ個並べることにより、Ｎ×Ｎ要素の変換係数行列を生成する。生成部１４０３の処理については、例２と同一であるため説明を省略する。
【０２１７】
つぎに、図１４−３は、係数値算出部１３０４の詳細な構成を示す説明図（その２）である。係数値算出部１３０４は、加減算部１４０５と入れ替え部１４０６により構成されている。加減算部１４０５は、第１の予測ブロックに関するＮ×Ｎ要素の第１の変換係数行列と生成部１４０３により生成されたＮ×Ｎ要素の変換係数行列とを、当該Ｎ×Ｎ要素の変換係数行列に対応する１×Ｎ要素の直交変換行列内の要素が１の場合、加算し、−１の場合、減算する。
【０２１８】
そして、入れ替え部１４０６は、加減算部１４０５により加減算されたＮ×Ｎ要素の変換係数行列に対してＮ×Ｎ要素の入れ替え行列を乗算し、第２の予測ブロックに関する第２の変換係数行列を算出する。加減算部１４０５と入れ替え部１４０６については、実施の形態３で説明した処理と同一であるため詳細な説明を省略する。
【０２１９】
（例４）
ここでは、Ｎが４であり、直交変換行列（Ｔ１とＴ２）が、アダマール変換の場合について説明する。なお、例１で示した入れ替え部１４０２についてのみが異なるため、他の機能部については、説明を省略する。
【０２２０】
入れ替え部１４０２は、加算部１４０１により加算されたＮ×Ｎ要素の変換係数行列を、Ｎ×Ｎ要素の入れ替え行列に基づいて行または列の順序を入れ替え、入れ替え後のＮ×Ｎ要素の変換係数行列内の行または列ごとにＮ×Ｎ要素の入れ替え行列に基づいて符号を変換して、第２の予測ブロックに関する第２の変換係数行列を算出する。具体的には、図６−１〜図６−４で示した処理と同一であるため説明を省略する。
【０２２１】
（例５）
ここでは、例４と同一条件であるが、処理の異なる例を示す。例４で示した入れ替え部１４０２と係数差分値算出部１３０５以外の機能部については、上述と同一であるため説明を省略する。
【０２２２】
入れ替え部１４０２は、加算部１４０１により加算されたＮ×Ｎ要素の変換係数行列を、Ｎ×Ｎ要素の入れ替え行列に基づいて行または列の順序を入れ替える。具体的には、図６−１〜図６−４で示した処理のうち、行列の入れ替えに関する処理と同一であるため説明を省略する。
【０２２３】
係数差分値算出部１３０５は、原画像内の対象ブロックに関する第３の変換係数行列に入れ替え部１４０２により入れ替えられたＮ×Ｎ要素の変換係数行列を、当該Ｎ×Ｎ要素の変換係数行列に対応する入れ替え行列の値が１の場合には減算し、−１の場合には加算することで係数差分値量列を算出する。具体的な処理例については、実施の形態３で示した例と同一であるため説明を省略する。
【０２２４】
（画像処理装置による画像処理手順）
図１５は、画像処理装置による画像処理手順の一例を示すフローチャートである。ここでは、動きベクトルの探索方法がスパイラルサーチの場合を例に挙げて説明する。実施の形態１で説明したようにスパイラルサーチの場合、参照画像内で探索開始点での予測ブロックのみ従来の二次元直交変換を施せばよい。まず、画像処理装置が、次の動きベクトル候補を現ベクトルに決定し（ステップＳ１５０１）、最初のベクトルか否かを判断する（ステップＳ１５０２）。最初のベクトルか否かとは、探索開始点であるか否かを示している。
【０２２５】
つぎに、画像処理装置が、最初のベクトルであると判断した場合（ステップＳ１５０２：Ｙｅｓ）、第１の二次元直交変換処理を実施する（ステップＳ１５０３）。一方、画像処理装置が、最初のベクトルでないと判断した場合（ステップＳ１５０２：Ｎｏ）、第２の二次元直交変換処理を実施する（ステップＳ１５０４）。
【０２２６】
ステップＳ１５０３、またはステップＳ１５０４のつぎに、画像処理装置が、各差分の絶対値を算出し（ステップＳ１５０６）、絶対値の総和（ＳＡＴＤ）を算出し（ステップＳ１５０７）、格納する（ステップＳ１５０８）。
【０２２７】
そして、画像処理装置が、探索終了条件を満たしたか否かを判断し（ステップＳ１５０９）、満たしていないと判断した場合（ステップＳ１５０９：Ｎｏ）、ステップＳ１５０１に戻り、満たしたと判断した場合（ステップＳ１５０９：Ｙｅｓ）、一連の処理を終了する。
【０２２８】
つぎに、図１６は、図１５で示した第１の二次元直交変換処理（ステップＳ１５０３）の詳細な説明を示すフローチャートである。ここでは、二次元直交変換の変換行列については、アダマール変換行列であっても他の変換行列であっても処理は同一である。まず、画像処理装置が、原画像内の対象ブロックを二次元直交変換し（ステップＳ１６０１）、対象ブロックに関する変換係数行列を格納する（ステップＳ１６０２）。
【０２２９】
つぎに、画像処理装置が、参照画像内で現ベクトルにより示される予測ブロックを二次元直交変換し（ステップＳ１６０３）、予測ブロックに関する変換係数行列を格納する（ステップＳ１６０４）。そして、画像処理装置が、対象ブロックに関する変換係数行列と予測ブロックに関する変換係数行列との差を算出し（ステップＳ１６０５）、ステップＳ１５０６に移行する。
【０２３０】
つぎに、図１７は、図１５で示した第２の二次元直交変換処理（ステップＳ１５０４）の詳細な説明を示すフローチャートである。まず、画像処理装置が、第１の画素値行列と第２の画素値行列を取得し（ステップＳ１７０１）、第１の画素値行列と第２の画素値行列との差分を算出する（ステップＳ１７０２）。つぎに、画像処理装置が、Ｎ×Ｎの変換行列を用いて差分値行列を一次元直交変換し（ステップＳ１７０３）、１×Ｎの変換係数行列を用いて一次元直交変換後のＮ×１の変換係数行列を一次元直交変換する（ステップＳ１７０４）。
【０２３１】
そして、画像処理装置が、現ベクトルによって示される予測ブロックに関する直交変換係数行列を算出し（ステップＳ１７０５）、格納する（ステップＳ１７０６）。つぎに、画像処理装置が、対象ブロックに関する変換係数と予測ブロックに関する変換係数との差を算出し（ステップＳ１７０７）、ステップＳ１５０６に移行する。
【０２３２】
図１８は、図１５で示した第２の二次元直交変換処理（ステップＳ１５０５）の詳細な説明を示すフローチャートである。ここでは、Ｎ＝４、Ｍ＝１、かつ変換行列がアダマール行列の場合において、従来と比較して演算量が削減されていることを示す。まず、画像処理装置が、第１の画素値行列と第２の画素値行列を取得し（ステップＳ１８０１）、第１の画素値行列と第２の画素値行列との差分を算出する（ステップＳ１８０２）。つぎに、画像処理装置が、Ｎ×Ｎの変換行列を用いて差分値行列を一次元直交変換し（ステップＳ１８０３）、ベクトルを複製してＮ×Ｎの変換係数行列を生成する（ステップＳ１８０４）。
【０２３３】
そして、画像処理装置が、符号変換し（ステップＳ１８０５）、現ベクトルによって示される予測ブロックに関する直交変換係数行列を算出し（ステップＳ１８０６）、格納する（ステップＳ１８０７）。つぎに、画像処理装置が、対象ブロックに関する変換係数と予測ブロックに関する変換係数との差を算出し（ステップＳ１８０８）、ステップＳ１５０６に移行する。
【０２３４】
ここで、Ｎ＝４、Ｍ＝１、かつ変換行列がアダマール行列の場合において、従来と比較して演算量が削減されていることを示す。
【０２３５】
まず、従来について演算量を記載する。
・アダマール変換：減算１６回
・二次元アダマール変換：Ｔ１、Ｔ２のそれぞれで３２回の加減算。合計６４回の加減算
・絶対値演算：１６回
・加算：１５回
【０２３６】
一方、本発明では、以下のようになる。
・原画像内の対象ブロックおよび少なくとも参照画像内の探索点のブロックについての二次元アダマール変換：従来と同様の６４回の加減算
・参照画像内の他のブロック：第１の画素値と第２の画素値の減算４回、アダマール変換の加減算８回、前ベクトル変換結果との加減算１６回
・対象ブロックとの差分値算出処理：加減算１６回
・絶対値算出処理：絶対値演算１６回
・総和：加算１５回
【０２３７】
探索方法としてスパイラルサーチを例に挙げると、マクロブロックごとに２０個のベクトルについての評価を行った場合、加減算数は、従来のＳＡＴＤ算出では３０４００回であるが、本発明では１９２６４回となり、演算量が削減される。絶対値演算は、従来も本発明であっても５１２０回である。
【０２３８】
以上説明したように、画像処理装置、画像処理方法、および画像処理プログラムによれば、第１および第２の予測ブロックでの非重複領域の差分値を直交変換の対象行列として直交変換をおこない、第１の予測ブロックに関する変換係数行列を用いて補完する。これにより、対象行列および変換行列の要素数が減り、演算量を削減することができる。
【０２３９】
また、Ｍ＝１であり、直交変換行列がアダマール変換行列の場合、第２の直交変換処理の際に第１の直交変換処理で得られる変換係数行列を探索方向にＮ個並べて、直交変換係数行列に基づいて符号を変換することで演算量を削減することができる。
【０２４０】
また、差分値が直交変換された変換係数行列と第１の予測ブロックに関する変換係数行列とを加算し、加算後の変換係数行列に対して行列の入れ替えに関する入れ替え行列を乗算することで第２の予測ブロックに関する第２の変換係数行列を算出できる。これにより、差分値のみの直交変換によって要素数が減ることで、演算量を削減することができる。
【０２４１】
また、Ｍ＝１であり、直交変換行列がアダマール変換行列の場合、第２の直交変換処理の際に第１の直交変換処理で得られる変換係数行列を探索方向にＮ個並べる。そして、並べたＮ×Ｎの変換係数行列と第１の変換係数行列とを、直交変換係数行列に基づいて加算または減算することで演算量を削減することができる。
【０２４２】
また、Ｎが４であり、直交変換行列が、アダマール変換行列の場合、第１の変換係数行列との加算後の変換係数行列を、入れ替え行列に基づいて行または列の順序を入れ替え、入れ替え行列に基づいて符号を変換することで第２の変換係数行列を算出する。これにより、加算後の変換係数行列と入れ替え行列との加減算を行わずに第２の変換係数行列を算出できるため、演算量を減らすことができる。
【０２４３】
また、原画像内の対象ブロックに関する第３の変換係数行列の第２の予測ブロックに関する第２の変換係数行列との差分値を算出し、絶対値演算後に総和を算出することで、ＳＡＴＤを算出する。これにより、ＳＡＴＤ算出に関する演算量を削減できる。
【０２４４】
また、Ｎが４であり、直交変換行列が、アダマール変換行列の場合、第１の変換係数行列との加算後の変換係数行列を、入れ替え行列に基づいて行または列の順序を入れ替え、第３の変換係数行列の第２の予測ブロックに関する第２の変換係数行列との差分値を、
入れ替え行列に基づいて加算または減算することで、演算量を削減できる。
【０２４５】
なお、本実施の形態で説明した画像処理方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本画像処理プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本画像処理プログラムは、インターネット等のネットワークを介して配布してもよい。
【０２４６】
また、実施の形態４で説明した画像処理装置１３００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した画像処理装置１３００の機能（差分値算出部１３０１〜二次元直行変換部１３０８）をＨＤＬ記述によって機能定義し、機能定義されたＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、画像処理装置１３００を製造することができる。
【０２４７】
また、実施の形態４で説明した画像処理装置１３００の機能（差分値算出部１３０１〜二次元直行変換部１３０８）の一部のみを、ＡＳＩＣやＦＰＧＡなどのＰＬＤによって実現してもよい。
【０２４８】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０２４９】
（付記１）画像内のＮ×Ｎ要素の第１のブロックが任意の探索方向にＭ（１≦Ｍ＜Ｎ／２）要素シフトしたＮ×Ｎ要素の第２のブロックの二次元直交変換を実行する画像処理装置であって、
前記第２のブロック内で前記第１のブロックに重複していない第１の特徴量行列と、前記第１のブロック内で前記第２のブロックに重複していない第２の特徴量行列との差分となる差分値行列を算出する差分値算出手段と、
前記差分値算出手段により算出されたＮ×Ｍ要素の差分値行列を、Ｎ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｍ要素の変換係数行列を算出する第１の直交変換手段と、
前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を、Ｍ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｎ要素の変換係数行列を算出する第２の直交変換手段と、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記第２の直交変換手段により変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する係数値算出手段と、
を備えることを特徴とする画像処理装置。
【０２５０】
（付記２）Ｍ＝１、かつ前記Ｎ×Ｎ要素の直交変換行列がアダマール変換行列、かつ前期Ｍ×Ｎ要素の変換行列が前記アダマール変換行列の一部を取り出した行列であり、
前記第２の直交変換手段は、
前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を前記探索方向にＮ個並べることにより、Ｎ×Ｎ要素の変換係数行列を生成する生成手段と、
前記生成手段により生成されたＮ×Ｎ要素の変換係数行列内の各要素の符号を、前記Ｍ×Ｎ要素の直交変換行列に基づいて変換する符号変換手段と、を備え、
前記係数値算出手段は、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記符号変換手段により符号が変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出することを特徴とする付記１に記載の画像処理装置。
【０２５１】
（付記３）前記係数値算出手段は、
前記Ｎ×Ｎ要素の第１の変換係数行列と前記第２の直交変換手段により変換されたＮ×Ｎ要素の変換係数行列とを加算する加算手段と、
前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を、前記加算手段により加算されたＮ×Ｎ要素の変換係数行列とＮ×Ｎ要素の入れ替え行列との乗算により算出する入れ替え手段と、
を備えることを特徴とする付記１または２に記載の画像処理装置。
【０２５２】
（付記４）Ｍ＝１、かつ前記Ｎ×Ｎ要素の直交変換行列および前記Ｍ×Ｎ要素の直交変換行列が、アダマール変換行列であり、
前記第２の直交変換手段は、
前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を前記探索方向にＮ個並べることにより、Ｎ×Ｎ要素の変換係数行列を生成し、
前記係数値算出手段は、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と前記第２の直交変換手段により生成されたＮ×Ｎ要素の変換係数行列とを、当該Ｎ×Ｎ要素の変換係数行列に対応する前記Ｍ×Ｎ要素の直交変換行列内の要素が１の場合、加算し、−１の場合、減算する加減算手段と、
前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を、前記加減算手段により加減算されたＮ×Ｎ要素の変換係数行列に対してＮ×Ｎ要素の入れ替え行列との乗算により算出する入れ替え手段と、を備えることを特徴とする付記１に記載の画像処理装置。
【０２５３】
（付記５）Ｎ＝４、かつ前記Ｎ×Ｎ要素の直交変換行列および前記Ｍ×Ｎ要素の直交変換行列が、アダマール変換行列であり、
前記入れ替え手段は、
前記加算手段により加算されたＮ×Ｎ要素の変換係数行列の行または列の順序をＮ×Ｎ要素の入れ替え行列に基づく入れ替え、および入れ替え後のＮ×Ｎ要素の変換係数行列内の行または列ごとに要素の符号を前記入れ替え行列に基づく変換により前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出することを特徴とする付記３または４に記載の画像処理装置。
【０２５４】
（付記６）前記画像と異なる画像内のＮ×Ｎ要素の第３のブロックに関する第３の変換係数行列と前記係数値算出手段により算出された第２の変換係数行列との差分となる係数差分値行列を算出する係数差分値算出手段と、
前記係数差分値算出手段により算出された係数差分値行列の絶対値を算出する絶対値演算手段と、
前記絶対値演算手段により算出された絶対値行列内の要素の総和を算出する総和演算手段と、
を備えることを特徴とする付記１〜５のいずれか１つに記載の画像処理装置。
【０２５５】
（付記７）Ｎ＝４、かつ前記Ｎ×Ｎ要素の直交変換行列および前記Ｍ×Ｎ要素の直交変換行列が、アダマール変換行列であり、さらに、
前記画像と異なる画像内のＮ×Ｎ要素の第３のブロックに関する第３の変換係数行列に対して前記入れ替え手段により入れ替えられた４×４要素の変換係数行列を当該変換係数行列に対応する前記４×４要素の入れ替え行列の要素が１の場合の減算、当該要素が−１の場合の加算により係数差分値行列を算出する係数差分値算出手段と、
前記係数差分値算出手段により算出された係数差分値行列の絶対値を算出する絶対値演算手段と、
前記絶対値演算手段により算出された絶対値行列内の要素の総和を算出する総和演算手段と、を備え、
前記入れ替え手段は、
前記加算手段により加算されたＮ×Ｎ要素の変換係数行列を、前記Ｎ×Ｎ要素の入れ替え行列に基づいて行または列の順序を入れ替えることを特徴とする付記３または４に記載の画像処理装置。
【０２５６】
（付記８）画像内のＮ×Ｎ要素の第１のブロックが任意の探索方向にＭ（１≦Ｍ＜Ｎ／２）要素シフトしたＮ×Ｎ要素の第２のブロックの二次元直交変換を実行するコンピュータが、
前記第２のブロック内で前記第１のブロックに重複していない第１の特徴量行列と、前記第１のブロック内で前記第２のブロックに重複していない第２の特徴量行列との差分となる差分値行列を算出する差分値算出工程と、
前記差分値算出工程により算出されたＮ×Ｍ要素の差分値行列を、Ｎ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｍ要素の変換係数行列を算出する第１の直交変換工程と、
前記第１の直交変換工程により算出されたＮ×Ｍ要素の変換係数行列を、Ｍ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｎ要素の変換係数行列を算出する第２の直交変換工程と、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記第２の直交変換工程により変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する係数値算出工程と、
を実行することを特徴とする画像処理方法。
【０２５７】
（付記９）画像内のＮ×Ｎ要素の第１のブロックが任意の探索方向にＭ（１≦Ｍ＜Ｎ／２）要素シフトしたＮ×Ｎ要素の第２のブロックの二次元直交変換を実行するコンピュータを、
前記第２のブロック内で前記第１のブロックに重複していない第１の特徴量行列と、前記第１のブロック内で前記第２のブロックに重複していない第２の特徴量行列との差分となる差分値行列を算出する差分値算出手段、
前記差分値算出手段により算出されたＮ×Ｍ要素の差分値行列を、Ｎ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｍ要素の変換係数行列を算出する第１の直交変換手段、
前記第１の直交変換手段により算出されたＮ×Ｍ要素の変換係数行列を、Ｍ×Ｎ要素の直交変換行列を用いて一次元直交変換して、Ｎ×Ｎ要素の変換係数行列を算出する第２の直交変換手段、
前記第１のブロックに関するＮ×Ｎ要素の第１の変換係数行列と、前記第２の直交変換手段により変換されたＮ×Ｎ要素の変換係数行列とに基づいて、前記第２のブロックに関するＮ×Ｎ要素の第２の変換係数行列を算出する係数値算出手段、
として機能させることを特徴とする画像処理プログラム。
【符号の説明】
【０２５８】
３００  画像処理装置
３０１  差分値算出回路
３０２  第１の直交変換回路
３０３  第２の直交変換回路
３０４  係数値算出回路
８００  画像処理装置
１３００  画像処理装置
１３０１  差分値算出部
１３０２  第１の直交変換部
１３０３  第２の直交変換部
１３０４  係数値算出部
１３０５  係数差分値算出部
１３０６  絶対値演算部
１３０７  総和演算部
１３０８  二次元直交変換部
【図１−１】
2011188007.tif 000012
【図１−２】
2011188007.tif 000013
【図２−１】
2011188007.tif 000014
【図２−２】
2011188007.tif 000015
【図２−３】
2011188007.tif 000016
【図２−４】
2011188007.tif 000017
【図３】
2011188007.tif 000018
【図４】
2011188007.tif 000019
【図５−１】
2011188007.tif 000020
【図５−２】
2011188007.tif 000021
【図５−３】
2011188007.tif 000022
【図５−４】
2011188007.tif 000023
【図６−１】
2011188007.tif 000024
【図６−２】
2011188007.tif 000025
【図６−３】
2011188007.tif 000026
【図６−４】
2011188007.tif 000027
【図７】
2011188007.tif 000028
【図８】
2011188007.tif 000029
【図９】
2011188007.tif 000030
【図１０】
2011188007.tif 000031
【図１１】
2011188007.tif 000032
【図１２】
2011188007.tif 000033
【図１３】
2011188007.tif 000034
【図１４−１】
2011188007.tif 000035
【図１４−２】
2011188007.tif 000036
【図１４−３】
2011188007.tif 000037
【図１５】
2011188007.tif 000038
【図１６】
2011188007.tif 000039
【図１７】
2011188007.tif 000040
【図１８】
2011188007.tif 000041