(57)【要約】【課題】少ない計算量で動き推定を行うことができる画像処理装置および画像処理方法を提供する。【解決手段】複数の画素により構成される第１の画像データを記憶する画像メモリ２と、入力された第２の画像データの内の画素の座標に基づいて、当該画素に対応する、画像メモリ２に記憶されている第１の画像データの内の画素の座標を生成する読み出し画素アドレスデコーダ５と、第２の画像の内の画素の座標、および当該第２の画像データの内の画素に対応する、第１の画像データの画素の座標に基づいて第１の画像データと第２の画像データとを比較し、比較の結果に基づいて評価値テーブルを生成する差分絶対値演算部６および評価値テーブル記憶部７と、評価値テーブルに基づいて動き推定を行う制御部９とを設ける。【選択図】　図１
2004080725.tif 000002
【特許請求の範囲】
【請求項１】
複数の画素により構成される画像データを処理する画像処理装置であって、
前記画像データに含まれる前記画素の座標に基づいて、当該画像データの前記各画素が対数周期構造になるように、前記画像データを記憶する記憶手段を有する
画像処理装置。
【請求項２】
前記記憶手段は、複数の画素を含む所定の領域を設定し、前記設定された領域の内の画素の順番が、偶数番目または奇数番目の画素を、順番をそのままに前半部に配置し、前記所定の領域の内の残りの画素を順番をそのままに後半部に配置し、前記後半部分または前半部分を新たに所定の領域として設定して、再帰的に前記画素が前記対数周期構造になるように記憶する
請求項１に記載の画像処理装置。
【請求項３】
複数の画素により構成される画像データを処理する画像処理装置であって、
第１の画像データを記憶する記憶手段と、
入力された前記第２の画像データの内の画素の座標に基づいて、当該画素に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する座標変換手段と、
前記第２の画像の内の画素の座標、および当該第２の画像データの内の画素に対応する、前記第１の画像データの画素の座標に基づいて、前記第１の画像データと前記第２の画像データとを比較し、前記比較の結果に基づいて評価値テーブルを生成する評価値テーブル生成手段と、
前記評価値テーブル生成手段により生成された評価値テーブルに基づいて動き推定を行う動き推定手段とを有する
画像処理装置。
【請求項４】
前記座標生成手段は、入力された前記第２の画像データの内の画素の座標に基づいて、当該画素の対数周期構造に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する
請求項３に記載の画像処理装置。
【請求項５】
前記座標生成手段は、前記入力された第２の画像データの内の座標に基づいて、当該画素の対数周期構造に対応する、少なくとも１画素分ずれた、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する
請求項３に記載の画像処理装置。
【請求項６】
前記記憶手段は、前記画像データの内の画素の座標に基づいて、前記画像データを複数の画像データに分割して記憶し、前記座標生成手段により生成された座標に応じて、前記複数に分割された画像データそれぞれの、当該座標に対応する画素の画素値を出力する
請求項３に記載の画像処理装置。
【請求項７】
前記記憶手段は、前記座標生成手段により生成された座標に基づいて、前記複数に分割された画像データそれぞれの、当該座標に対応する画素の画素値を、同時に出力可能になるように分割して、前記画像データを記憶する
請求項３に記載の画像処理装置。
【請求項８】
前記評価値テーブル生成手段は、前記第２の画像の内の画素、および前記座標変換手段により生成された前記第２の画像データの内の画素に対応する、前記第１の画像データの画素それぞれの画素値に基づいて、当該画素値それぞれの差分値を計算して、前記計算の結果に応じて、対数周期構造を有する評価値テーブルを生成し、
前記動き推定手段は、前記評価値テーブル生成手段により生成された評価値テーブルに含まれる前記画素値の差分値、および当該対数周期構造を有する評価値テーブルの所定の領域のアドレスに基づいて動き推定を行う
請求項３に記載の画像処理装置。
【請求項９】
前記第２の画像の内の画素、および前記座標変換手段により生成された前記第２の画像データの内の画素に対応する、前記第１の画像データの画素それぞれの画素値に基づいて、当該画素値それぞれの差分値を計算して、対数周期構造を有する差分画像データを生成する差分画像データ生成手段を有し、
前記動き推定手段は、前記差分画像データ生成手段により生成された前記差分画像データに含まれる差分値に基づいて、局所的な動き推定を行う
請求項３に記載の画像処理装置。
【請求項１０】
複数の画素の画素値により構成される画像データを処理する画像処理装置の画像処理方法であって、
記憶手段に、前記画像データに含まれる前記画素の座標に基づいて、当該画像データの前記各画素が対数周期構造になるように、前記画像データを記憶する
画像処理方法。
【請求項１１】
前記記憶手段に記憶させる場合には、複数の画素を含む所定の領域を設定し、前記設定された領域の内の画素の順番が、偶数番目または奇数番目の画素を、順番をそのままに前半部に配置し、前記所定の領域の内の残りの画素を順番をそのままに後半部に配置し、前記後半部分または前半部分を新たに所定の領域として設定して、再帰的に前記画素が前記対数周期構造になるように記憶する
請求項１０に記載の画像処理方法。
【請求項１２】
複数の画素の画素値により構成される画像データを処理する画像処理装置の画像処理方法であって、
記憶手段に、第１の画像データを記憶し、
入力された前記第２の画像データの内の画素の座標に基づいて、当該画素に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成し、
前記第２の画像の内の画素の座標、および当該第２の画像データの内の画素に対応する、前記第１の画像データの画素の座標に基づいて、前記第１の画像データと前記第２の画像データとを比較し、前記比較の結果に基づいて評価値テーブルを生成し、
前記生成された評価値テーブルに基づいて動き推定を行う
画像処理方法。
【請求項１３】
前記座標を生成する場合には、入力された前記第２の画像データの内の画素の座標に基づいて、当該画素の対数周期構造に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する
請求項１２に記載の画像処理方法。
【請求項１４】
前記座標を生成する場合には、前記入力された第２の画像データの内の画素の座標に基づいて、当該画素の対数周期構造に対応する、少なくとも１画素分ずれた、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する
請求項１２に記載の画像処理方法。
【請求項１５】
前記記憶手段に記憶させる場合には、前記画像データの内の画素の座標に基づいて、前記画像データを複数の画像データに分割して記憶し、
前記生成された座標に応じて、前記複数に分割された画像データそれぞれの、当該座標に対応する画素の画素値を出力する
請求項１２に記載の画像処理方法。
【請求項１６】
前記記憶手段に記憶させる場合には、前記生成された座標に、前記複数に分割された画像データそれぞれの、当該座標に対応する画素の画素値を、同時に出力可能になるように分割して、前記画像データを記憶する
請求項１５に記載の画像処理方法。
【請求項１７】
前記評価値テーブルを生成する場合には、前記第２の画像の内の画素、および前記座標変換手段により生成された前記第２の画像データの内の画素に対応する、前記第１の画像データの画素それぞれの画素値に基づいて、当該画素値それぞれの差分値を計算して、前記計算の結果に応じて、対数周期構造を有する評価値テーブルを生成し、
前記動き推定を行う場合には、前記生成された評価値テーブルに含まれる前記画素値の差分値、および当該対数周期構造を有する評価値テーブルの所定の領域のアドレスに基づいて動き推定を行う
請求項１２に記載の画像処理方法。
【請求項１８】
前記第２の画像の内の画素、および前記座標変換手段により生成された前記第２の画像データの内の画素に対応する、前記第１の画像データの画素それぞれの画素値に基づいて、当該画素値それぞれの差分値を計算して、対数周期構造を有する差分画像データを生成し、
前記動き推定を行う場合には、前記生成された前記差分画像データに含まれる差分値に基づいて、局所的な動き推定を行う
請求項１２に記載の画像処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、たとえば、画像データに基づいて動き推定等の画像処理を行う画像処理装置および画像処理方法に関するものである。
【０００２】
【従来の技術】
たとえば、複数のフレーム（画像）により構成される動画像を処理する画像処理装置が知られている。
たとえば、上述の従来の画像処理装置では、画像を所定のブロックに分割して、そのブロック単位で時間の異なるフレーム間でマッチングを行い、所定の時間の動き推定処理を行っていた。
【０００３】
【発明が解決しようとする課題】
しかし、従来のブロックマッチングをベースとした画像の動き推定処理では、所定の大きさのサーチ範囲を設定する必要があったので、ある動き量以上の動きを検出することは困難であった。
【０００４】
また、従来の動き推定処理では、サーチ範囲すべてについて、所定の画像領域を重ね合わせる必要があったので、計算量がＯ（ｎ）・Ｏ（ｓ）・Ｏ（ｋ）のオーダーになり、計算量が非常に多くなるという問題点があった。ここで、ｎは画像の総画素数、Ｓはサーチ範囲の面積、ｋはサーチカーネル規模である。
このため、少ない計算量で動き推定処理を行える画像処理装置が望まれている。
また、従来の動き推定処理では、全画面を対象とすると、たとえば部分的な動きを検出することができない等の問題点があった。
【０００５】
本発明は、かかる事情に鑑みてなされたものであり、その目的は、少ない計算量で動き推定を行うことができる画像処理装置および画像処理方法を提供することにある。
【０００６】
【課題を解決するための手段】
前記目的を達成するために、第１の発明の画像処理装置は、複数の画素により構成される画像データを処理する画像処理装置であって、前記画像データに含まれる前記画素の座標に基づいて、当該画像データの前記各画素が対数周期構造になるように、前記画像データを記憶する記憶手段を有する。
【０００７】
第１の発明の画像処理装置によれば、記憶手段では、複数の画素により構成される画像データに含まれる画素の座標に基づいて、当該画像データの各画素が対数周期構造になるように、画像データが記憶される。
【０００８】
好適には、前記記憶手段は、複数の画素を含む所定の領域を設定し、前記設定された領域の内の画素の順番が、偶数番目または奇数番目の画素を、順番をそのままに前半部に配置し、前記所定の領域の内の残りの画素を順番をそのままに後半部に配置し、前記後半部分または前半部分を新たに所定の領域として設定して、再帰的に前記画素が前記対数周期構造になるように記憶する。
【０００９】
前記目的を達成するために、第２の発明の画像処理装置は、複数の画素により構成される画像データを処理する画像処理装置であって、第１の画像データを記憶する記憶手段と、入力された前記第２の画像データの内の画素の座標に基づいて、当該画素に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する座標変換手段と、前記第２の画像の内の画素の座標、および当該第２の画像データの内の画素に対応する、前記第１の画像データの画素の座標に基づいて、前記第１の画像データと前記第２の画像データとを比較し、前記比較の結果に基づいて評価値テーブルを生成する評価値テーブル生成手段と、前記評価値テーブル生成手段により生成された評価値テーブルに基づいて動き推定を行う動き推定手段とを有する。
【００１０】
第２の発明の画像処理装置によれば、記憶手段では、複数の画素により構成される第１の画像データが記憶される。
座標変換手段では、入力された前記第２の画像データの内の画素の座標に基づいて、当該画素に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標が生成される。
評価値テーブル生成手段では、前記第２の画像の内の画素の座標、および当該第２の画像データの内の画素に対応する、前記第１の画像データの画素の座標に基づいて、前記第１の画像データと前記第２の画像データとを比較し、前記比較の結果に基づいて評価値テーブルが生成される。
動き推定手段では、前記評価値テーブル生成手段により生成された評価値テーブルに基づいて動き推定が行われる。
【００１１】
好適には、前記座標生成手段は、入力された前記第２の画像データの内の画素の座標に基づいて、当該画素の対数周期構造に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する。
【００１２】
また、好適には、前記座標生成手段は、前記入力された第２の画像データの内の座標に基づいて、当該画素の対数周期構造に対応する、少なくとも１画素分ずれた、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成する。
【００１３】
また、好適には、前記記憶手段は、前記画像データの内の画素の座標に基づいて、前記画像データを複数の画像データに分割して記憶し、前記座標生成手段により生成された座標に応じて、前記複数に分割された画像データそれぞれの、当該座標に対応する画素の画素値を出力する。
【００１４】
また、好適には、前記記憶手段は、前記座標生成手段により生成された座標に基づいて、前記複数に分割された画像データそれぞれの、当該座標に対応する画素の画素値を、同時に出力可能になるように分割して、前記画像データを記憶する。
【００１５】
また、好適には、前記評価値テーブル生成手段は、前記第２の画像の内の画素、および前記座標変換手段により生成された前記第２の画像データの内の画素に対応する、前記第１の画像データの画素それぞれの画素値に基づいて、当該画素値それぞれの差分値を計算して、前記計算の結果に応じて、対数周期構造を有する評価値テーブルを生成し、前記動き推定手段は、前記評価値テーブル生成手段により生成された評価値テーブルに含まれる前記画素値の差分値、および当該対数周期構造を有する評価値テーブルの所定の領域のアドレスに基づいて動き推定を行う。
【００１６】
また、好適には、前記第２の画像の内の画素、および前記座標変換手段により生成された前記第２の画像データの内の画素に対応する、前記第１の画像データの画素それぞれの画素値に基づいて、当該画素値それぞれの差分値を計算して、対数周期構造を有する差分画像データを生成する差分画像データ生成手段を有し、前記動き推定手段は、前記差分画像データ生成手段により生成された前記差分画像データに含まれる差分値に基づいて、局所的な動き推定を行う。
【００１７】
さらに、前記目的を達成するために、第３の発明の画像処理方法は、複数の画素の画素値により構成される画像データを処理する画像処理装置の画像処理方法であって、記憶手段に、前記画像データに含まれる前記画素の座標に基づいて、当該画像データの前記各画素が対数周期構造になるように、前記画像データを記憶する。
【００１８】
さらに、前記目的を達成するために、第４の発明の画像処理方法は、複数の画素の画素値により構成される画像データを処理する画像処理装置の画像処理方法であって、記憶手段に、第１の画像データを記憶し、入力された前記第２の画像データの内の画素の座標に基づいて、当該画素に対応する、前記記憶手段に記憶されている前記第１の画像データの内の画素の座標を生成し、前記第２の画像の内の画素の座標、および当該第２の画像データの内の画素に対応する、前記第１の画像データの画素の座標に基づいて、前記第１の画像データと前記第２の画像データとを比較し、前記比較の結果に基づいて評価値テーブルを生成し、前記生成された評価値テーブルに基づいて動き推定を行う。
【００１９】
【発明の実施の形態】
以下、本発明の好適な実施の形態を、図面に関連付けて説明する。
第１の実施の形態
本実施の形態に係る画像処理装置は、画像データを処理する場合に、画素単位で、対数周期構造を有するように並べ替えを行う。また、画像処理装置は、そのデータを利用して動き推定（動き推定処理）を行う。
【００２０】
図１は、本発明に係る画像処理装置の第１の実施の形態を示すブロック構成図である。
本実施の形態に係る画像処理装置１は、図１に示すように、画像メモリ２、入力画素アドレスデコーダ３、評価値テーブルアドレスデコーダ４、読み出し画素アドレスデコーダ５、差分絶対値和演算部６、評価値テーブル記憶部７、切替部８、および制御部９を有する。
【００２１】
画像メモリ２は、本発明に係る記憶手段に相当する。読み出し画素アドレスデコーダ５は、本発明に係る座標変換手段に相当する。差分絶対値和演算部６および評価値テーブル記憶部７は、本発明に係る評価値テーブル生成手段に相当する。制御部９は、本発明に係る動き推定手段に相当する。
【００２２】
画像メモリ２は、画像を記憶する。画像メモリ２は、たとえば、図１に示すように、複数の画像メモリ２−１，２−２を有する。
【００２３】
たとえば、画像メモリ２−１，２−２それぞれは、動画像を処理する際に、現フレームと、前フレームを交互に記憶する。この際、たとえば、後述するように、切替部８は、１フレーム毎に画像メモリ２−１と、画像メモリ２−２の役割を切替える。
ここで、現フレームは、たとえば処理対象の時刻ｔのフレームであり、前フレームは、たとえば時刻ｔ−１のフレームである。
【００２４】
具体的には、たとえば、切替部８は、１フレーム毎に、画像メモリ２−１，２−２に入力するデータを切替える。また、切替部８は、画像メモリ２−１，２−２から出力するデータを切替える。
【００２５】
画像メモリ２−１は、たとえば、入力された入力画素の画素値、および、入力画素アドレスデコーダ３から出力された入力画素のアドレスに応じて、所定のアドレス（座標とも言う）に、その画素値を記憶する。
【００２６】
画像メモリ２−２は、たとえば、１フレーム前の画像を記憶している。
また、上述したように、画像メモリ２−１および画像メモリ２−２それぞれは、１フレーム毎にその役割が切替わる。
【００２７】
画像メモリ２−２は、入力された読み出しアドレスに基づいて、所定のアドレスのデータを比較のための画素値（比較画素とも言う）として、差分絶対値和演算部６に出力する。
【００２８】
入力画素アドレスデコーダ３は、入力された画素のラスター入力アドレスに応じて、入力画素アドレスを生成し、画像メモリ２−１、評価値テーブルアドレスデコーダ４、および読み出し画素アドレスデコーダ５に出力する。
【００２９】
評価値テーブルアドレスデコーダ４は、入力画素アドレスデコーダ３から出力された、入力画素アドレスに応じて、評価値テーブル記憶部７に記憶している評価値テーブルのアドレスを決定する。
【００３０】
評価値テーブルアドレスデコーダ４は、具体的には、入力画素アドレスデコーダ３から出力された、入力画素アドレスに基づいて、評価値テーブルの、どのべき領域に相当するかを判別し、評価値テーブルのアドレスを決定する。
【００３１】
読み出し画素アドレスデコーダ５は、評価値テーブルアドレスデコーダ４から出力された、入力画素アドレスに基づいて、画像メモリ２−１に記憶されている画像データを、読み出すためのアドレスを生成し、画像メモリ２−２に出力する。
【００３２】
差分絶対値和演算部６は、入力画素の画素値と、画像メモリ２−２から出力された、比較の対象となる、１フレーム前の、入力画素に対応する画素の画素値に応じて評価値を生成し、生成した評価値を、評価値テーブル記憶部７に出力する。
【００３３】
また、差分絶対値和演算部６は、評価値テーブル記憶部７から出力された、所定のべき領域の評価値、入力画素の画素値、および、画像メモリ２−２から出力された比較の対象となる画素値に応じて、新たに評価値を生成する。
【００３４】
評価値テーブル記憶部７は、評価値テーブルを記憶する。
評価値テーブル記憶部７は、具体的には、評価値テーブルアドレスデコーダ４から出力された評価値テーブルアドレスに、差分絶対値和演算部６から出力された評価値を記憶する。
【００３５】
切替部８は、上述したように、１フレーム毎に画像メモリ２−１と、画像メモリ２−２の役割を切替える。具体的には、たとえば、切替部８は、画像メモリ２−１，２−２それぞれが、動画像を処理する際に、現フレームと、前フレームを交互に記憶するように、１フレーム毎に、画像メモリ２−１，２−２に入力するデータを切替える。また、切替部８は、画像メモリ２−１，２−２から出力するデータを切替える。
【００３６】
制御部９は、後述するように、評価値テーブル記憶部７に記憶している、評価値テーブルに基づいて、動画像の動き推定を行う。
【００３７】
以下、上述した構成に関して、詳細に説明する。
原理
まず、本発明に係る画像処理の原理に関して、図を参照しながら説明する。
図２（ａ）はラスター方式により画像を記憶する場合を説明するための模式図である。図２（ｂ）は対数構造を有するべきメモリを説明するための模式図である。
【００３８】
ラスター方式により画像を記憶する場合には、たとえば、図２（ａ）に示すように、画像をあたかも平面状そのままの状態で記憶するように、メモリの画素毎に画像に応じた画素値で記憶する。
【００３９】
一方、たとえば、図２（ｂ）に示すように画像を記憶するメモリをべきメモリと言う。べきメモリは、たとえば図２（ａ）に示した画像を画素単位に並び替えて、図２（ｂ）に示すように、対数周期的な構造を有するように記憶する。
【００４０】
たとえば図２（ｂ）に示したような対数周期的な構造を有する画像を、リスト内シャッフル処理により形成する。
図３は、図１に示した画像情報処理装置の動作、特に、リスト内シャッフルに関する動作を説明するための図である。画像処理装置１のリスト内シャッフルに関する動作を図３を参照しながら説明する。
【００４１】
図３（ａ）は、ラスター方式による１次元に配列された画素を模式的に示す図である。図３（ｂ）はリスト内シャッフル処理の第１段階を示す図、図３（ｃ）は第２段階を示す図、図３（ｄ）は第３段階を示す図である。
簡単のために、１次元に配列された画素をリスト内シャッフル処理を行う場合を、１次元に配列された画素に番号を付けて説明する。
【００４２】
リスト内シャッフルは、具体的には、数列の偶数番目または奇数番目の要素を、順序をそのままの状態で前半部に配置して、残りの数列の要素を、順序をそのままの状態で後半に配置し直す処理である。
【００４３】
たとえば、読み出しアドレスでコーダ５は、後述の数列（１）を、リスト内シャッフルを行い、数列（２）を生成する。
ここで、数列（１），（２）それぞれは、リスト内の順番を示す。
【００４４】
【数１】
｛１，２，３，４，５，６，…，２ｎ−３，２ｎ−２，２ｎ−１，２ｎ｝…（１）
｛１，３，５，…，２ｎ−３，２ｎ−１，２，４，６，…，２ｎ−２，２ｎ｝…（２）
【００４５】
対数周期的な構造を形成する際に、画像処理装置は、複数の画素を含む所定の領域を設定し、設定された領域の内の画素の順番が、偶数番目または奇数番目の画素を、順番をそのままに前半部に配置し、所定の領域の内の残りの画素を順番をそのままに後半部に配置し、後半部分または前半部分を新たに、所定の領域として設定して、再帰的に画素が対数周期構造になるように記憶する。
【００４６】
図４は、図１に示した画像処理装置の動作を説明するためのフローチャートである。画像処理装置の動作、特にリスト内シャッフルに関する動作を中心に図３，４を参照しながら詳細に説明する。
【００４７】
ステップＳＴ１において、画像処理装置１は、最初の処理対象のリストを設定する。
具体的には、図３（ａ）に示すように、すべての構成要素を、処理対象のリストＬ１１として設定する。
【００４８】
ステップＳＴ２において、画像処理装置１は、最初の処理対象のリストのリスト内シャッフル処理を行う。
【００４９】
たとえば、具体的には、図３（ｂ）に示すように、リストＬ１１内において、たとえば１次元に配列された画素の奇数番目の要素を、順序をそのままの状態で、リストＬ１１の前半に配置して、数列の偶数番目の要素を、順序をそのままの状態でリストＬ１１の後半に配置し直す。
【００５０】
ステップＳＴ３において、画像処理装置１は、リストＬ１１の後半部分を取り出し、その後半部分をリストＬ１２として設定する。
【００５１】
ステップＳＴ４において、リストの内の要素数が２以下か否かが判別される。２以下ではないと判別された場合には、ステップＳＴ２の処理に戻る。
一方、ステップＳＴ４において、リストの要素数が２以下であると判別された場合には、一連の処理を終了する。
【００５２】
たとえば、具体的には、図３（ｂ）に示すように、リストＬ１２の要素数が２以下ではないと判別し、図３（ｃ）に示すように、リストＬ１２内において、リスト内シャッフルを行う。
【００５３】
リストＬ１２の後半部分をリストＬ１３と設定する。そして、リストＬ１３内の要素数が２以下ではないと判別し、図３（ｄ）に示すように、リストＬ１３内において、リスト内シャッフルを行う。
【００５４】
リストＬ１３の後半部分をリストＬ１４と設定する。そして、リストＬ１４内の構成要素が２以下であると判別し、一連の処理を終了する。
【００５５】
次に、２次元に配列された画素を、リスト内シャッフル処理を行う場合を説明する。
図５は、２次元に配列された画素を、リスト内シャッフルを行う場合を説明するための図である。
【００５６】
図５（ａ）は垂直方向が長手方向である矩形領域を、水平方向にリスト内シャッフルを行う前の状態を示す図である。図５（ｂ）は垂直方向が長手方向である矩形領域を、水平方向にリスト内シャッフルを行った後の状態を示す図である。
【００５７】
図５（ｃ）は水平方向が長手方向である矩形領域を、垂直方向にリスト内シャッフルを行う前の状態を示す図である。図５（ｂ）は水平方向が長手方向である矩形領域を、垂直方向にリスト内シャッフルを行った後の状態を示す図である。
【００５８】
図６は、図１に示した画像処理装置の動作を説明するためのフローチャートである。画像処理装置１の動作を、図５，６を参照しながら説明する。
【００５９】
ステップＳＴ１１において、画像処理装置１は、最初の処理対象のリストを設定する。
具体的には、図５に示すように、水平方向の並べ替えの処理対象のリストを設定する。
【００６０】
ステップＳＴ１２において、設定されたリスト内シャッフル処理を行う。
ステップＳＴ１３において、リスト後ろ半分を取り出す。
【００６１】
ステップＳＴ１４において、リストの要素数が２以下か否かが判別される。２以下ではないと判別された場合には、ステップＳＴ１２の処理に戻る。
一方、ステップＳＴ１４において、リストの要素数が２以下であると判別された場合には、一連の処理を終了する。
【００６２】
具体的には、リスト内シャッフル処理を行う場合には、図５（ａ）に示すように、垂直方向が長手方向である矩形領域の画素の集合を処理の１単位として設定する。
【００６３】
そして、その設定された矩形領域を水平方向にリスト内シャッフルを行い、図５（ｂ）に示すようにな画像を生成する。
リスト内シャッフル処理は、上述した１次元の場合と同様である。
【００６４】
ステップＳＴ１５において、次に垂直方向の並べ替えのリストを定義する。
ステップＳＴ１６において、リスト内シャッフルを行う。
ステップＳＴ１７において、リスト後ろ半分の取り出しを行う。
【００６５】
ステップＳＴ１８において、リストの要素数が２以下か否かが判別される。２以下ではないと判別された場合には、ステップＳＴ１６の処理に戻る。
一方、ステップＳＴ１８において、リストの要素数が２以下であると判別された場合には、一連の処理を終了する。
【００６６】
具体的には、図５（ｃ）に示すように、水平方向が長手方向である矩形領域の画素の集合を処理の１単位として設定する。
そして、その矩形領域を垂直方向にリスト内シャッフルを行い、図５（ｄ）に示すような画像を生成する。
【００６７】
上述した形態では、画像を水平方向に並べ替えを行ってから、垂直方向に並べ替えを行ったが、この形態に限られるものではない。たとえば、逆に垂直方向に並べ替えを行ってから、垂直方向に並べ替えを行ってもよい。
【００６８】
べきメモリ
次に、べきメモリの構造を説明する。べきメモリは、対数周期的な構造を有する。べき構造は、例えば、前画像の読み出しアドレッシングによって、抽象的に実現する。
【００６９】
図７（ａ）はべきメモリの構造を説明するための図である。図７（ｂ）は図７（ａ）に示したべきメモリの構成を、ラスタスキャン構造に展開した図である。
【００７０】
べきメモリの構造を、たとえば２０×２０のサイズの画像を処理する場合を説明する。
【００７１】
新しいフォームの画素が入力された場合には、後述する動き推定処理の計算に必要な前フレームの画素は、その新しいフォームの画素の位置からライン方向に±１および垂直方向に±１の画素である。
【００７２】
具体的には、たとえば、新しいフレームの（４，４）画素が入力された場合には、計算に必要な前フレームの画素は、（２，２），（２，４），（２，６），（４，２），（４，４），（４，６），（６，２），（６，４），（６，６）の９点である。
【００７３】
他の画素に対しても同様である。
ここでの処理は、各べき領域の内部で完結させる。また、上述の処理では、べき領域を跨ぐ計算は行わない。
【００７４】
図１に示すようにラスタスキャンによって、順次入力される画素に対応する前フレーム画素の読み出しのためには、３ライン分の画素データを、任意のライン方向アドレスに対してアクセスする構造が必要である。
【００７５】
入力アドレスの生成
入力画素のアドレス（行ｏｒ列）から必要な３つのアドレスを発生させる。ここで、発生アドレスは、数式（３）に示す制限がある。
Ｈは画像横幅、Ｖは画像縦幅である。
【００７６】
【数２】
０＜発生アドレス＜画像サイズ（Ｈ　ｏｒ　Ｖ）…（３）
【００７７】
図８は、入力アドレスのビット判定による、アドレスの生成を説明するための図である。アドレスを発生させる動作を、図８を参照しながら説明する。
【００７８】
ステップＳＴ２１において、入力アドレスの１ビット目が”０”、具体的には、アドレスを２進数表示するとａｄｄｒｅｓｓ＝ＸＸＸＸＸ０、であるか否かが判別され、１ビット目が”０”であると判別された場合には、入力画素アドレス±２を生成する。
【００７９】
一方、ステップＳＴ２１において、１ビット目が”０”でないと判別された場合には、ステップＳＴ２２に進む。
【００８０】
ステップＳＴ２２において、入力アドレスの２ビット目が”０”、具体的には、ａｄｄｒｅｓｓ＝ＸＸＸＸ０１、であるか否かが判別され、２ビット目が”０”であると判別された場合には、入力画素アドレス±４を生成する。
一方、ステップＳＴ２２において、２ビット目が”０”でないと判別された場合には、ステップＳＴ２３に進む。
【００８１】
ステップＳＴ２３において、入力アドレスの３ビット目が”０”、具体的には、ａｄｄｒｅｓｓ＝ＸＸＸ０１１、であるか否かが判別され、３ビット目が”０”であると判別された場合には、入力画素アドレス±８を生成する。
一方、ステップＳＴ２３において、３ビット目が”０”でないと判別された場合には、ステップＳＴ２４に進む。
【００８２】
ステップＳＴ２４において、入力アドレスの４ビット目が”０”、具体的には、ａｄｄｒｅｓｓ＝ＸＸ０１１１、であるか否かが判別され、４ビット目が”０”であると判別された場合には、入力画素アドレス±１６を生成する。
一方、ステップＳＴ２４において、４ビット目が”０”でないと判別された場合には、ステップＳＴ２５に進む。
【００８３】
同様に、ステップＳＴｎにおいて、入力アドレスのｎビット目が”０”、具体的には、ａｄｄｒｅｓｓ＝…Ｘ０１１１…、であるか否かが判別され、ｎビット目が”０”であると判別された場合には、入力画素アドレス±２ｎを生成する。
【００８４】
図９は、アドレス生成の処理を説明するための図である。
画像は、図９に示すように、縦は画像振幅（Ｈ）、横は画像縦軸（Ｖ）である。たとえば、図９に示すように、べき領域番号（ｎ）およびアドレス番号（ｍｎ）を割り当てる。
【００８５】
【数３】
Ａｄｄｒｅｓｓ＝（１＋２ｍｎ）２ｎ−１…（４）
【００８６】
ここで、ｍｎ，ｎ＝０，１，２，…である。
【００８７】
上述したアドレスは、より具体的には、数式（４）に示すように導かれる。
【００８８】
画像の格納
図１０は、図１に示した画像メモリの一具体例を示す図である。
画像メモリ２は、読み出し画素アドレスデコーダ５により生成されたアドレス（座標）に基づいて、複数に分割された画像データそれぞれの、アドレス（座標）に対応する画素の画素値を、同時に出力可能になるように分割して、画像データを記憶する。
【００８９】
画像メモリ２は、たとえば図１０に示すように、複数のメモリブロック、たとえば、３つのブロックＡ、ブロックＢ、およびブロックＣ、ならびに、行アドレスデコーダ２１、列アドレスデコーダ２２を有する。
【００９０】
たとえば、ブロックＡ，Ｂ，Ｃそれぞれは、格子状にワード線ｗとビット線ｂを備え、その交点それぞれにメモリセルｍｃを有する。
また、ブロックＡ，Ｂ，Ｃそれぞれは、行セレクタ２１１、フリップフロップ／列セレクタ２２１、センスアンプ２２２を有する。
【００９１】
行セレクタ２１１は、行アドレスデコーダ２１からの信号に基づいて、所定のワード線ｗを活性化または不活性化する。
【００９２】
フリップフロップ／列セレクタ２２１は、列アドレスデコーダ２２からの信号に基づいて、所定のビット線ｂを活性化または不活性化する。
【００９３】
センスアンプ２２２は、活性化した所定のメモリセルｍｃに書き込みおよび読み出し処理を行う際に、所定の信号を増幅し出力する。
【００９４】
また、上述した行アドレスデコーダ２１は、処理を行うワード線ｗの行アドレスから、必要となる３行分のアドレスを生成する。
行アドレスデコーダ２１は、この３つの行アドレスを、それぞれブロックに存在するように生成する。
【００９５】
以下、３分割したメモリを設け、必要な３行分の行アドレスが、必ず別ブロックに存在することを説明する。
２乗構造（対数周期的な構造）を採用する場合、動き推定処理の際に、同時に読み出す必要のある３ラインは、センターのラインを中心に±２のｎ乗のラインである。
【００９６】
一方、３分割したメモリセルｍｃに格納されるラインは、３ｎ＋Ｃ（ｎ＝０，１，２，…；Ｃ＝０，１，２）というラインアドレスを持つことになる。
【００９７】
３ライン中の任意の２ライン、または３ライン全てが、同一の分割メモリに存在するためには、±２のｎ乗が３で割り切れる必要がある。
【００９８】
実際には、２のｎ乗は３で割り切れることは決してなく、必ず、±１または±２の剰余が生じ、上下のライン同士も決して同一のブロックには、存在しない。
【００９９】
この関係は、２のｎ乗および３ばかりでなく、２のｎ乗および５、３および４のｎ乗、３およびｎ乗と５、２のｎ乗および５等の、互いに素な数のべき乗との関係でも成立する。
【０１００】
列アドレスデコーダ２２が生成した３行分の行アドレスを３つのブロックＡ，Ｂ，Ｃに振り分け、行セレクタ２１１により選択されたワード線ｗを活性化させる。
【０１０１】
選択されたワード線ｗ上のデータは、一旦、１ライン分全てをフリップフロップ／列セレクタ２２１上に引き上げ、これを該当ライン上の入力画素の処理が終わるまで、保持する。
【０１０２】
列アドレスデコーダ２２は、３ブロック共通の３列分の列アドレスを発生させ、それを受けえた列アドレスセレクタが、必要なデータを選択し、出力する。
【０１０３】
該当ライン上の処理が続いている間に、メモリセルアレイ内部では、リフレッシュなど、データ保持に必要な動作を行う。
以上の操作を、処理するライン数分繰り返す。
【０１０４】
図１１（ａ）は、ラスター方式の画像メモリを説明するための図である。図１１（ｂ）は、図１に示した画像処理装置の動作、特に全画面動き推定を行う処理について説明するための図である。
【０１０５】
図１１（ａ）に示したラスター方式では、メモリにおける上下左右各方向への１アドレス分ずらしにより、それぞれの方向の１画素の動きを検出することができる。
【０１０６】
図１１（ｂ）に示した、本実施の形態に係る画像処理装置１では、メモリ領域５２は、上下左右各方向へ、１アドレス分ずらすことにより、それぞれの方向への２画素の動きを検出することができる。
【０１０７】
また、メモリ領域５３においては、上下左右方向への１アドレス分ずらすことにより、上下方向の２が、その動きが左右方向の１アドレス分ずらしによって、左右方向の２画素の動きが検出可能である。
メモリ領域５２，５３，５４などの領域を、べき領域と言う。
【０１０８】
図１２は、図１に示す画像処理装置の動作、特に全画面動きの推定を処理する動作を説明するための図である。
図１２（ａ）は全画面評価値テーブルを模式的に示す図、図１２（ｂ）は図１２（ａ）に示した全画面評価値テーブルの一部を拡大した図、図１２（ｃ）は、画像メモリの内の画像を模式的に示す図である。
【０１０９】
差分絶対値和演算部６は、画素の読み込みと同時に、差分絶対値和を積算し、評価値テーブルを生成し、評価値テーブル記憶部７に出力する。
制御部９は、評価値テーブル記憶部７に記憶された評価値テーブルに基づいて、全画面動きを推定する。具体的には、極値を与える評価値テーブル上のアドレスが動き情報に対応する。
全画面の評価値テーブルから、小さな差分絶対値和を与える評価値テーブル上のアドレスを抽出すると、全画面での動きを抽出する。
【０１１０】
図１３は、図１に示した画像処理装置の動作を説明するためのフローチャートである。画像処理装置の動作を図１３を参照しながら簡単に説明する。
ステップＳＴ１０１において、画像の内の画素の画素値が入力される。
ステップＳＴ１０２において、その画素に応じて、画像メモリに書き込まれる。
【０１１１】
ステップＳＴ１０３において、アドレスから、べき領域が決定される。
ステップＳＴ１０４において、評価値テーブルアドレスが決定される。
【０１１２】
ステップＳＴ１０５において、読み出しアドレスが設定される。
ステップＳＴ１０６において、読み出しアドレスに基づいて、前フレームから読み出される。
【０１１３】
ステップＳＴ１０７において、現フレームの入力画素との差分値演算が行われる。
ステップＳＴ１０８において、評価値テーブルに足し込まれる。
【０１１４】
ステップＳＴ１０９において、制御部９では、評価値テーブルが全て埋まっているか否かが判別される。全て埋まっていないと判別された場合には、ステップＳＴ１０４の処理に戻る。
一方、ステップＳＴ１０９の判別において、制御部９では、評価値テーブルが全て埋まっていると判別した場合には、ステップＳＴ１１０の処理に進む。
【０１１５】
ステップＳＴ１１０において、制御部９では、アドレスが１画面分終了しているか否かが判別される。終了していないと判別した場合には、アドレスが加算され（ＳＴ１１１）、ステップＳＴ１０２の処理に戻る。
【０１１６】
一方、ステップＳＴ１１０の判別において、制御部０では、アドレスが１画面分終了していると判別した場合には、評価値テーブルの最小値を探索する（ＳＴ１１２）。
ステップＳＴ１１３において、制御部９では、評価値テーブルの最小値に基づいて、全画面の動きが決定される。
【０１１７】
図１４は、図１に示した画像処理装置の動作、特に、全画面動き推定の処理に関する動作を説明するためのフローチャートである。画像処理装置１の動作を、図１４を参照しながら説明する。
【０１１８】
ステップＳＴ２０１において、向きベクトルリストの初期化を行う。
向きベクトルリストは、１アドレス分のずらしまでなら、｛（０，０），（０，１），（１，０），（０，−１），（−１，０），（１，１），（１，−１），（−１，１），（−１，１）｝などである。
【０１１９】
ステップＳＴ２０２において、「現在の最小誤差」と、「その出自」の初期化を行う。
具体的には、現在の最小誤差を、十分に大きい値に設定して、初期化を行う。
「その出自」は、その最小誤差が得られる向きベクトルαｍｉｎと、領域βｍｉｎのことである。
画像処理装置は、このリストの要素αについて処理を行う。
【０１２０】
ステップＳＴ２０３において、向きベクトルαに応じたずらし量で差分計算を行う。
ステップＳＴ２０４において、領域リストの初期化が行われる。
領域リストは、具体的には、図１１に示したメモリ領域５２，５３，５４のことである。
【０１２１】
このリストβについての処理を中心に説明する。
【０１２２】
ステップＳＴ２０５において、リストβの領域で誤差平均値の計算を行う。
具体的には、この領域についての誤差平均値、すなわち画素単位の差分絶対値の平均値等を計算する。
【０１２３】
ステップＳＴ２０６において、誤差平均値が「現在の最小誤差」より小なら、「現在の最小誤差」と「その出自」を更新する。
ステップＳＴ２０７において、領域リスト内において、処理対象の要素を、次の要素に設定する。その際、領域リスト内に処理されていない要素があるか否かが判別される。処理されていない要素がないと判別した場合には、ステップＳＴ２０５の処理に戻る。
一方、ステップＳＴ２０７の判別において、処理されていない要素があると判別した場合には、ステップＳＴ２０９の処理に進む。
【０１２４】
この上述したステップＳＴ２０６および２０７の処理により、「現在の最小誤差」と「最小誤差を与える領域β」と、「そのときの向きベクトルα」を計算する。
【０１２５】
ステップＳＴ２０９において、方向リスト内において、処理対象の要素を、次の要素に設定する。その際、方向リスト内に処理されていない要素があるか否かが判別され、処理されていない要素がないと判別された場合には、ステップＳＴ２０３の処理に戻る。
【０１２６】
一方、ステップＳＴ２０９の判別において、方向リスト内に処理されていない要素があると判別された場合には、ステップＳＴ２０９の処理に進む。
ステップＳＴ２１０において、「現在の最小誤差」と、「その出自」の初期化が行われる。
【０１２７】
図１５は、図１に示した画像処理装置の動き推定を説明するための図である。画像処理装置１の動作、特に全画面の動き推定の動作について、図１５を参照しながら説明する。
図１５（ａ）は、時刻ｔと時刻ｔ−１のフレームとをずらし量０で重ね、差分を計算した結果を示す画像、図１５（ｂ）は、ずらし量−１で重ね、差分を計算した結果を示す画像、図１５（ｃ）は、ずらし量−２で重ね、差分を計算した結果を示す画像、図１５（ｄ）は、ずらし量−３で重ね、差分を計算した結果を示す画像である。
【０１２８】
画像処理装置１は、全画面動き推定を行う。
簡単な説明のため、水平方向のみを並べ替えた、べき画像を利用したシミュレーションを行う。
ソースに、画面全体が左向きにパンする動画像を用いた場合を説明する。具体的には、この動画像は、左向きにフレーム６画素程度全体の動きを有する。
【０１２９】
図１５（ａ）に示すように第１の画像は、時刻ｔのフレームと時刻ｔ−１のフレームとを、ずらし量０で重ね、差分を計算した結果を示す画像である。
図１５（ａ）を参照すると、べき領域それぞれは、（白線で区切られた部分）も水平方向に相似的である。つまり、水平方向に伸縮すれば重なる。
ずらし量１とは、画像を１アドレス分ずらした量のことである。
【０１３０】
図１５（ｂ）に示すように、第２の画像は、ずらし量−１で時刻ｔと、時刻ｔ＋１のフレームを重ね、差分を計算した結果を示す図である。
図左から２番目および３番目のべき領域（それぞれ４画素動き、８画素動きに対応）で、差分が小さくなっている。
【０１３１】
図１５（ｃ）に示すように、第３の画像は、ずらし量−２で時刻ｔと、時刻ｔ＋１のフレームを重ね、差分を計算した結果を示す図である。
図１５（ｄ）に示すように、第４の画像は、ずらし量−３で時刻ｔと、時刻ｔ＋１のフレームを重ね、差分を計算した結果を示す図である。
【０１３２】
この第４の画像では、一番左のべき領域に対応しており、６画素動きに対応している。この部分で、はっきり差分が小さくなっている。
制御部は、この差分の差分値の小さい領域を、そのソースの全画面の動き量と推定する。
【０１３３】
図１６は、図１５に示した各画像の、べき領域それぞれの差分のパワーの平均を示す図である。画像処理装置１の全画面動き推定を図１６を参照しながら説明する。
【０１３４】
横軸は、そのべき領域に対する動き量を画素の単位で示した量である。
縦軸は、差分絶対値和を示す。
折れ線それぞれは、図１５に示した画像それぞれに対応する。
べきメモリ上で、何アドレス分ずらしたかによって、線を分けている。
【０１３５】
これらがほぼ重なっているので、各ずらし量で差分をとった画像間の整合性が確認できる。
また、制御部９は、図１６に示すように、差分絶対値和が最小値が、−２〜−４付近であることから、動き量を、−２〜−４であると推定する。
【０１３６】
以上、説明したように、複数の画素により構成される第１の画像データを記憶する画像メモリ２と、入力された第２の画像データの内の画素の座標に基づいて、当該画素に対応する、画像メモリ２に記憶されている第１の画像データの内の画素の座標を生成する読み出し画素アドレスデコーダ５と、第２の画像の内の画素の座標、および当該第２の画像データの内の画素に対応する、第１の画像データの画素の座標に基づいて第１の画像データと第２の画像データとを比較し、比較の結果に基づいて評価値テーブルを生成する差分絶対値演算部６および評価値テーブル記憶部７と、評価値テーブルに基づいて動き推定を行う制御部９とを設けたので、少ない計算量で、動き推定を行うことができる。
【０１３７】
また、一般的なブロックマッチングをベースとした一般的な画像の動き推定では、サーチ範囲を考える必要があったので、動き推定といっても、ある動き以上の動きは検出することが困難であったが、本実施の形態に係る画像処理装置１では、ある程度以上の動き量は検出することができる。
【０１３８】
一般的な画像処理装置の動き推定処理では、サーチ範囲すべてについて所定の画像領域の重ねあわせを行う必要があったので、計算量がＯ（ｎ）×Ｏ（ｓ）×Ｏ（ｋ）のオーダーであった。
本実施の形態に係る画像処理装置１では、計算量は、Ｏ（ｎ）となる。全画面を対象としたサーチを行う場合には、ｓがＯ（ｎ）のオーダーである。
このため、本実施の形態に係る画像処理装置は、全画面についての動き推定処理では、計算量がＯ（ｎ２）となるので、一般的な画像処理装置の動き推定処理の計算量と比べて、大幅に少ない計算量により実時間の動き推定を行うことができる。
【０１３９】
第２の実施の形態
図１７は、本発明に係る画像処理装置の第２の実施の形態を示すブロック構成図である。
本実施の形態に係る画像処理装置１ａは、図１７に示すように、画像メモリ２、入力画素アドレスデコーダ３、評価値テーブルアドレスデコーダ４、読み出し画素アドレスデコーダ５、差分絶対値和演算部６ａ、差分絶対値画像メモリ７０、切替部８、および制御部９ａを有する。
差分絶対値和演算部６ａは、および差分絶対値画像メモリ７０は、本発明に係る差分画像データ生成手段に相当する。
【０１４０】
画像処理装置１ａと、第１の実施の形態に係る画像処理装置１との相違点は、差分絶対値画像メモリ７０を有することである。
画像処理装置１ａは、時刻ｔと時刻ｔ＋１の画像の局所的な動き推定（動き推定処理）を行う。
相違点のみ説明する。
【０１４１】
差分絶対値和演算部６ａは、時刻ｔ＋１の画像と、時刻ｔの画像の所定の方向に１アドレス分ずらした画像の、画素値それぞれの差分値を計算し、差分絶対値画像メモリ７０に出力する。
【０１４２】
差分絶対値画像メモリ７０は、差分絶対値演算部６ａにより生成された、時刻ｔ＋１の画像と、時刻ｔの画像の所定の方向に１アドレス分ずらした画像の画素値それぞれの差分値に応じた画像を記憶する。
【０１４３】
制御部９ａは、差分絶対値画像メモリ７０に記憶されている、差分絶対値画像に基づいて、たとえば時刻ｔ＋１と、時刻ｔの画像の局所的な動き推定を行う。
【０１４４】
図１８は、図１７に示す画像処理装置の動作を説明するための図である。画像処理装置の動作、特に、局所動きを推定する動作を図１８を参照しながら説明する。具体的には、図１８は、局所動きの抽出結果を示す図である。一具体例として、ソースとして局所的な動きが含まれる動画像を用いた場合を説明する。
【０１４５】
図１８（ａ）に示した第１の画像は、ずらし量が−４、図１８（ｂ）に示した第２の画像は、ずらし量が−１、図１８（ｃ）に示した第３の画像は、ずらし量が０である。
【０１４６】
図１８（ａ）に示した第１の画像と、図１８に示した第２の画像とを見比べると、局所的な領域、たとえば、楕円で示した領域においてのみ差分値が小さくなる。
制御部９ａは、この差分値が小さい領域を、局所的な動きとして抽出する。
【０１４７】
以上、説明したように、画像処理装置１ａでは、時刻ｔ＋１の画像と、時刻ｔの画像の所定の方向に１アドレス分ずらした画像の、画素値それぞれの差分値を計算し、差分絶対値画像メモリ７０に出力する差分絶対値和演算部６ａと、差分絶対値演算部６ａにより生成された、時刻ｔ＋１の画像と、時刻ｔの画像の所定の方向に１アドレス分ずらした画像の画素値それぞれの差分値に応じた画像を記憶する差分絶対値画像メモリ７０と、差分絶対値画像メモリ７０に記憶されている、差分絶対値画像に基づいて、たとえば時刻ｔ＋１と、時刻ｔの画像の局所的な動き推定を行う制御部９ａとを設けたので、部分的な動きを検出することができる。
【０１４８】
画面シーケンスから、被写体の動き推定を行う場合に、検出できる動きの大きさに制限がなく、動きを推定することができる。
大域動きと部分的な動きを共に検出することができる。
一般的な画像処理装置の動き推定処理と比較して、本実施の形態に係る画像処理装置の動き推定処理では計算量が大幅に減少し、実時間に処理することが容易である。
また、たとえば、画像を伝送するとき、適当なべき領域から順に伝送することで、伝送容量の小さい回線でも、早い段階で画像の概要を提示することができる。
【０１４９】
なお、本発明は本実施の形態に限られるものではなく、任意好適な種々の改変が可能である。
たとえば、画像メモリ２は、ラスター方式により画像データを記憶してもよいし、対数周期構造を有するように画像データを記憶してもよい。
【０１５０】
【発明の効果】
本発明によれば、少ない計算量で、動き推定を行うことができる画像処理装置および画像処理方法を提供することができる。
【図面の簡単な説明】
【図１】本発明に係る画像処理装置の第１の実施の形態を示すブロック構成図である。
【図２】（ａ）は一般的なラスター方式により画像を記憶するメモリを説明するための模式図である。（ｂ）は図１に示した画像処理装置が画像を記憶する画像メモリを説明するための模式図である。
【図３】図１に示した画像情報処理装置の動作、特に、リスト内シャッフルに関する動作を説明するための図である。（ａ）は、ラスター方式による１次元に配列された画素を模式的に示す図である。（ｂ）はリスト内シャッフル処理の第１段階を示す図、（ｃ）は第２段階を示す図、（ｄ）は第３段階を示す図である。
【図４】図１に示した画像処理装置の動作を説明するためのフローチャートである。
【図５】２次元に配列された画素を、リスト内シャッフルを行う場合を説明するための図である。（ａ）は垂直方向が長手方向である矩形領域を、水平方向にリスト内シャッフルを行う前の状態を示す図である。（ｂ）は垂直方向が長手方向である矩形領域を、水平方向にリスト内シャッフルを行った後の状態を示す図である。（ｃ）は水平方向が長手方向である矩形領域を、垂直方向にリスト内シャッフルを行う前の状態を示す図である。（ｂ）は水平方向が長手方向である矩形領域を、垂直方向にリスト内シャッフルを行った後の状態を示す図である。
【図６】図１に示した画像処理装置の動作を説明するためのフローチャートである。
【図７】（ａ）はべきメモリの構造を説明するための図である。（ｂ）は（ａ）に示したべきメモリの構成を、ラスタスキャン構造に展開した図である。
【図８】入力アドレスのビット判定による、アドレスの生成を説明するための図である。
【図９】アドレス生成の処理を説明するための図である。
【図１０】図１に示した画像メモリの一具体例を示す図である。
【図１１】（ａ）は、ラスター方式の画像メモリを説明するための図である。（ｂ）は、図１に示した画像処理装置の動作、特に全画面動き推定を行う処理について説明するための図である。
【図１２】図１に示す画像処理装置の動作、特に全画面動きの推定を処理する動作を説明するための図である。（ａ）は全画面評価値テーブルを模式的に示す図、（ｂ）は（ａ）に示した全画面評価値テーブルの一部を拡大した図、（ｃ）は画像メモリの内の画像を模式的に示す図である。
【図１３】図１に示した画像処理装置の動作を説明するためのフローチャートである。
【図１４】図１に示した画像処理装置の動作、特に、全画面動き推定の処理に関する動作を説明するためのフローチャートである。
【図１５】図１に示した画像処理装置の動き推定を説明するための図である。（ａ）は時刻ｔのフレームと時刻ｔ−１のフレームとを、ずらし量０で重ね、差分を計算した結果を示す図である。（ｂ）はずらし量−１で時刻ｔと、時刻ｔ＋１のフレームを重ね、差分を計算した結果を示す図である。（ｃ）は、ずらし量−２で時刻ｔと、時刻ｔ＋１のフレームを重ね、差分を計算した結果を示す図である。（ｄ）は、ずらし量−３で時刻ｔと、時刻ｔ＋１のフレームを重ね、差分を計算した結果を示す図である。
【図１６】図１５に示した各画像の、べき領域それぞれの差分のパワーの平均を示す図である。
【図１７】本発明に係る画像処理装置の第２の実施の形態を示すブロック構成図である。
【図１８】図１７に示す画像処理装置の動作、特に、局所動きを推定する動作を説明するための図である。（ａ）はずらし量が−４、（ｂ）はずらし量が−１、（ｃ）はずらし量が０の画像を示す図である。
【符号の説明】
１…画像処理装置、２…画像メモリ、３…入力画素アドレスデコーダ、３…評価値テーブルアドレスデコーダ、４…評価値テーブルアドレスデコーダ、５…画素アドレスデコーダ、６…差分絶対値和演算部、７…評価値テーブル記憶部、８…切替部、９…制御部、７０…差分絶対値画像メモリ。
【図１】
2004080725.tif 000003
【図２】
2004080725.tif 000004
【図３】
2004080725.tif 000005
【図４】
2004080725.tif 000006
【図５】
2004080725.tif 000007
【図６】
2004080725.tif 000008
【図７】
2004080725.tif 000009
【図８】
2004080725.tif 000010
【図９】
2004080725.tif 000011
【図１０】
2004080725.tif 000012
【図１１】
2004080725.tif 000013
【図１２】
2004080725.tif 000014
【図１３】
2004080725.tif 000015
【図１４】
2004080725.tif 000016
【図１５】
2004080725.tif 000017
【図１６】
2004080725.tif 000018
【図１７】
2004080725.tif 000019
【図１８】
2004080725.tif 000020