(57)【要約】【課題】ＳＡＤに比して簡易な演算により高精度にデータ間の類似度を算出することが可能なデータ処理装置、画像処理装置、データ処理方法、及びコンピュータプログラムを提供する。【解決手段】  画像処理装置は、プロセッサアレイ部１３０を備えている。プロセッサアレイ部１３０は、データバッファ１２１に格納された候補フレーム画像の画素データと、入力レジスタ１３１に格納されたマクロブロック画像の画素データとの排他的論理和を、排他的論理和演算部１３３によってビット毎に演算する。得られたビット毎の排他的論理和は連続するように互いに結合され、１つの数値データである排他的論理和データとして扱われる。各画素について得られた排他的論理和データが加算され、排他的論理和の総和が演算される。【選択図】図３
2014229263.tif 000002
【特許請求の範囲】
【請求項１】
所定長のビット列からなる複数の処理データをそれぞれ含む第１データと第２データとの類似度を評価するためのデータ処理装置であって、
前記第１データに含まれる処理データと、前記第２データに含まれる処理データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得する排他的論理和演算部と、
前記第１データと前記第２データとの類似度を示す指標を演算する類似度演算部と、を備え、
前記類似度演算部は、複数の処理データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似度を示す指標とする
データ処理装置。
【請求項２】
前記排他的論理和演算部は、前記排他的論理和データの上位所定ビットの値を演算する例外処理部を備え、
前記例外処理部は、前記第１データに含まれる処理データと前記第２データに含まれる処理データとの絶対差の上位所定ビットの値を演算し、
前記排他的論理和演算部は、前記例外処理部によって演算された前記絶対差の上位所定数ビットの値を、上位所定数ビットに含む前記排他的論理和データを取得する
請求項１に記載のデータ処理装置。
【請求項３】
前記例外処理部は、前記第１データの処理データの上位ビットと、前記第２データの処理データ上位ビットとに基づいて、前記絶対差の上位所定数ビットを演算する
請求項２に記載のデータ処理装置。
【請求項４】
前記例外処理部は、前記第１データの処理データの上位２ビットと、前記第２データの処理データの上位２ビットとに基づいて、前記絶対差の最上位ビットを演算する
請求項３に記載のデータ処理装置。
【請求項５】
前記排他的論理和演算部は、前記処理データの複数ビットのそれぞれに対応する複数のＥＸＯＲゲートを含み、前記複数のＥＸＯＲゲートによって前記複数ビットの排他的論理和演算を並列に実行する
請求項１〜４のいずれか１項に記載のデータ処理装置。
【請求項６】
前記排他的論理和演算部は、前記第１データに含まれる１つの処理データと、前記第２データに含まれる１つの処理データとの排他的論理和を演算する単位演算部を複数具備し、各単位演算部において、複数の処理データについての排他的論理和の演算を並列に実行する
請求項１〜５の何れか１項に記載のデータ処理装置。
【請求項７】
所定長のビット列からなる複数の画素データをそれぞれ含む第１画像データと第２画像データとの類似度を評価するための画像処理装置であって、
前記第１画像データに含まれる画素データと、前記第２画像データの画素データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得する排他的論理和演算部と、
前記第１画像データと前記第２画像データとの類似度を示す指標を演算する類似度演算部と、を備え、
前記類似度演算部は、複数の画素データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似を示す指標とする
画像処理装置。
【請求項８】
所定長のビット列からなる複数の処理データをそれぞれ含む第１データと第２データとの類似度を評価するデータ処理方法であって、
前記第１データに含まれる処理データと、前記第２データに含まれる処理データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得するステップと、
前記第１データと前記第２データとの類似度を示す指標を演算するステップと、
を含み、
前記第１データと前記第２データとの類似度を示す指標を演算するステップは、複数の処理データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似度を示す指標とすることを含む
データ処理方法。
【請求項９】
所定長のビット列からなる複数の処理データをそれぞれ含む第１データと第２データとの類似度を評価する処理をコンピュータに実行させるためのコンピュータプログラムであって、
前記処理は、
前記第１データに含まれる処理データと、前記第２データに含まれる処理データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得するステップと、
前記第１データと前記第２データとの類似度を示す指標を演算するステップと、
を含み、
前記第１データと前記第２データとの類似度を示す指標を演算するステップは、複数の処理データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似度を示す指標とすることを含む
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２つのデータの類似度を演算するためのデータ処理装置、画像処理装置、データ処理方法、及びコンピュータプログラムに関するものである。
【背景技術】
【０００２】
動画像の符号化（動画像圧縮）を行うために、ブロックマッチングによる動きベクトル検出が利用されている。ブロックマッチングとは、時間的に連続する２つの画像（フレーム）内のオブジェクトの対応関係から、オブジェクトの動きベクトルを検出する手法である。つまり、ブロックマッチングでは、２つのフレームのそれぞれから抽出した同一サイズのブロックの類似度を演算し、最も類似度の高いブロック間の相対的位置関係を動きベクトルとして検出する。
【０００３】
ブロックマッチングにおける類似度の指標として、絶対差総和(Sum of Absolute Difference, SAD)が広く利用されている。ＳＡＤとは、比較する２つのブロックに対して、全ての座標で輝度の絶対差（差分の絶対値）を計算し、それらを合計することで求められる値である。候補となる動きベクトルがｄ（ｄｘ，ｄｙ）のとき, ＳＡＤ値は式（１）で求められる。このとき、ｒ（ｘ，ｙ），ｃ（ｘ，ｙ）はそれぞれ参照ブロックと候補ブロックの座標（ｘ，ｙ）における輝度を表す。ＳＡＤ値は、比較する２つのブロックが類似しているほど、０に近い値となる。
【０００４】
【数１】
2014229263.tif 000003
【０００５】
かかるＳＡＤを計算するためには絶対差を算出する必要があることから多くの演算処理が必要となり、しかも１フレームにおける動きベクトル検出においては膨大な回数のＳＡＤ計算が必要となる。このため、ハードウェアにてＳＡＤを計算する場合には、回路構成が複雑化し、回路のサイズが大型化していた。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平８−２３７６６１号公報
【特許文献２】特開２０００−２７８６９１号公報
【特許文献３】特開２００３−３２４７３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明者らは、２つのデータのビット毎の排他的論理和を、桁の概念を有する数値データとしてみると、２つのデータの絶対差に近い値となるという性質を利用し、絶対差の演算よりも簡易な排他的論理和の演算によって、データ間の類似度を算出という着想を得た。
【０００８】
ここで、ブロックマッチングに際して、排他的論理和を利用することは、特許文献１〜３に開示されている。
ただし、特許文献１〜３に記載されているのは、排他的論理和演算をデータのビット毎に行い、異なるビットの数を数えて、これを評価値として用いてブロックマッチングを行うものにすぎない。しかし、異なるビットの数と絶対差の値の大小に相関関係は低く、特許文献１〜３に記載のものは、２つのデータのビット毎の排他的論理和が、２つのデータの絶対差に近い値となるという前述の性質を利用したものではない。
【０００９】
本発明は、排他的論理和の演算結果が、絶対差に近い値となるという性質を利用し、ＳＡＤに比して簡易な演算によってデータ間の類似度を算出することが可能なデータ処理装置、画像処理装置、データ処理方法、及びコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
（１）本発明は、所定長のビット列からなる複数の処理データをそれぞれ含む第１データと第２データとの類似度を評価するためのデータ処理装置であって、前記第１データに含まれる処理データと、前記第２データに含まれる処理データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得する排他的論理和演算部と、前記第１データと前記第２データとの類似度を示す指標を演算する類似度演算部と、を備え、前記類似度演算部は、複数の処理データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似度を示す指標とするデータ処理装置である。
【００１１】
上記本発明によれば、絶対差よりも簡易な演算で実現可能な排他的論理和を絶対差に代えて利用するため、ＳＡＤを用いた手法よりも簡易な演算でデータの類似度を示す指標を算出することが可能となる。また、排他的論理和が連なる排他的論理和データは、第１データの処理データと第２データの処理データとの絶対差の演算から桁上げ処理を除外した結果に等しく、多くの場合において絶対差に近い値となる。特に、桁上げが発生しない組合せでは、絶対差と同一の値となる。したがって、類似度を示す指標の演算の精度低下を抑えることができる。
【００１２】
（２）前記排他的論理和演算部は、前記排他的論理和データの上位所定ビットの値を演算する例外処理部を備え、前記例外処理部は、前記第１データに含まれる処理データと前記第２データに含まれる処理データとの絶対差の上位所定ビットの値を演算し、前記排他的論理和演算部は、前記例外処理部によって演算された前記絶対差の上位所定数ビットの値を、上位所定数ビットに含む前記排他的論理和データを取得するのが好ましい。
ビット毎の排他的論理和を連ねた排他的論理和データは、多くの場合絶対差に近い値を取るが、同一値となるとは限らない。少ないながらも一部の処理データの組合せでは、誤差が大きくなる。そこで、上記構成とすることにより、数値データの上位所定数ビットの値が絶対差の結果と同じになるので、数値データと絶対差との誤差を小さくすることが可能となる。
【００１３】
（３）  前記例外処理部は、前記第１データの処理データの上位ビットと、前記第２データの処理データ上位ビットとに基づいて、前記絶対差の上位所定数ビットを演算するのが好ましい。
この場合、例外処理部による処理に用いられるのが各処理データの一部（上位ビット）となるので、例外処理部による計算量を抑制することが可能となる。
【００１４】
（４）前記第１データの処理データの上位２ビットと、前記第２データの処理データの上位２ビットとに基づいて、前記絶対差の最上位ビットを演算するのが好ましい。
この場合、例外処理部による処理に用いられるのが各処理データの上位２ビットだけになるので、例外処理部による計算量をより一層抑制することが可能となる。また、最も桁の大きい最上位ビットを例外処理部により演算し、これを排他的論理和データの最上位ビットとするので、例外処理の演算を抑えつつも、高い誤差低減効果を得ることが可能となる。
【００１５】
（５）前記排他的論理和演算部は、前記処理データの複数ビットのそれぞれに対応する複数のＥＸＯＲゲートを含み、前記複数のＥＸＯＲゲートによって前記複数ビットの排他的論理和演算を並列に実行するのが好ましい。
この場合、各処理データの複数ビットのそれぞれについての排他的論理和演算を複数のＥＸＯＲゲートによって並列に実行するので、排他的論理和を高速に演算することが可能となる。
【００１６】
（６）前記排他的論理和演算部は、前記第１データに含まれる１つの処理データと、前記第２データに含まれる１つの処理データとの排他的論理和を演算する単位演算部を複数具備し、各単位演算部において、複数の処理データについての排他的論理和の演算を並列に実行するのが好ましい。
この場合、複数の処理データについての排他的論理和演算を、複数の単位演算部によって並列に実行するので、類似度を示す指標を高速に演算することが可能となる。
【００１７】
（７）他の観点からみた本発明は、所定長のビット列からなる複数の画素データをそれぞれ含む第１画像データと第２画像データとの類似度を評価するための画像処理装置であって、前記第１画像データに含まれる画素データと、前記第２画像データの画素データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得する排他的論理和演算部と、前記第１画像データと前記第２画像データとの類似度を示す指標を演算する類似度演算部と、を備え、前記類似度演算部は、複数の画素データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似を示す指標とする画像処理装置である。
【００１８】
（８）さらに他の観点からみた本発明は、所定長のビット列からなる複数の処理データをそれぞれ含む第１データと第２データとの類似度を評価するデータ処理方法であって、
前記第１データに含まれる処理データと、前記第２データに含まれる処理データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得するステップと、前記第１データと前記第２データとの類似度を示す指標を演算するステップと、を含み、前記第１データと前記第２データとの類似度を示す指標を演算するステップは、複数の処理データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似度を示す指標とすることを含むデータ処理方法である。
【００１９】
（９）さらに他の観点からみた本発明は、所定長のビット列からなる複数の処理データをそれぞれ含む第１データと第２データとの類似度を評価する処理をコンピュータに実行させるためのコンピュータプログラムであって、前記処理は、前記第１データに含まれる処理データと、前記第２データに含まれる処理データとの排他的論理和をビット毎に演算し、得られたビット毎の排他的論理和が連なる前記所定長のビット列として構成された排他的論理和データを取得するステップと、前記第１データと前記第２データとの類似度を示す指標を演算するステップと、を含み、前記第１データと前記第２データとの類似度を示す指標を演算するステップは、複数の処理データそれぞれについて取得された複数の排他的論理和データそれぞれを数値データとして扱うことで、複数の排他的論理和データの算術演算による総和を求め、前記総和を、前記類似度を示す指標とすることを含むコンピュータプログラムである。
【発明の効果】
【００２０】
本発明によれば、ＳＡＤより簡易な演算によって、データ間の類似度を算出することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】実施形態１に係る画像処理装置の構成を示すブロック図。
【図２】実施の形態１に係る画像処理装置におけるデータバッファ部とプロセッサアレイ部の詳細な構成を示す模式図。
【図３】プロセッサエレメントの構成を示す模式図。
【図４】絶対差を演算するための回路構成を示す模式図。
【図５】実施の形態１に係る排他的論理和演算部の回路構成を示す模式図。
【図６】実施の形態１に係る排他的論理和演算部による排他的論理和データと絶対差との誤差を示すグラフ。
【図７】実施の形態２に係る画像処理装置の排他的論理和演算部の構成の一部を示す模式図。
【図８】実施の形態２に係る排他的論理和演算部による排他的論理和データと絶対差との誤差を示すグラフ。
【図９】実施の形態３に係る画像処理装置の機能ブロック図。
【図１０】実施の形態３に係る画像処理装置による画像処理の流れを示すフローチャート。
【発明を実施するための形態】
【００２２】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。
【００２３】
（実施の形態１）
以下では、２つの画像データの類似度を示す指標を演算する画像処理装置の構成及びその動作について説明する。
【００２４】
本実施形態に係る画像処理装置１００は、ＥＸＯＲゲートを含むハードウェア（ＦＰＧＡ等）により構成されたプロセッサである。この画像処理装置１００は、時間的に連続する２つのフレームのそれぞれから抽出した同一サイズのブロックのブロックマッチング処理を行い、最も類似度の高いブロック間の相対的位置関係を動きベクトルとして検出するものである。
ブロックマッチング処理では、２つのブロックに含まれる各画素データの排他的論理和が演算され、画素データ毎に得られた排他的論理和の総和が、両画像データの類似度を示す指標として算出される。
【００２５】
図１は、本実施形態に係る画像処理装置の構成を示すブロック図である。図１に示すように、この画像処理装置１００は、入力部１１０と、データバッファ部１２０と、プロセッサアレイ部１３０と、総和部（類似度演算部）１４０と、最小値検出部１５０と、出力部１６０とを備えている。
【００２６】
入力部１１０は、バッファメモリ等から構成されており、画像処理装置１００に入力される画像データを一時的に保持することが可能である。入力部１１０には、ブロックマッチングに用いられる基準画像データであるマクロブロック画像と、前記マクロブロック画像と類似するブロックを探索する候補フレーム画像とが入力される。なお、本実施の形態においては、マクロブロック画像のサイズは１６［画素］×１６［画素］であり、候補フレーム画像のサイズは、マクロブロック画像よりも大きい２５６［画素］×２５６［画素］である。また、それぞれの画素データ（処理データ；ワードデータ）は、８ビット（複数ビット）のビット長を有する多値データである。
【００２７】
図２は、データバッファ部１２０とプロセッサアレイ部１３０の詳細な構成を示す模式図である。図２に示すように、データバッファ部１２０は、１６×２５６個のデータバッファ１２１，１２１，…を具備している。データバッファ１２１，１２１，…は、１６行２５６列のマトリックス状に配置されている。１行分のデータバッファ１２１，１２１，…には、候補フレーム画像の１行分（２５６画素）が記憶される。つまり、各データバッファ１２１のビット長は８ビットであり、１つのデータバッファ１２１には１画素分の画素データが記憶される。データバッファ部１２１全体としては、候補フレーム画像の１６行分（１６×２５６画素）の画素データを記憶可能である。データバッファ部１２１は、候補フレーム画像を画素データ単位でシフトするシフトレジスタとして機能する。
【００２８】
データバッファ１２１，１２１，…は、１クロックサイクル当たりに、記憶している画素データを右隣のデータバッファ１２１，１２１，…にシフトする。最も右端のデータバッファ１２１，１２１，…の画素データは、１行下の左端のデータバッファ１２１，１２１，…へシフトされる。
【００２９】
データバッファ部１２０のうち、右端の１６×１６の領域には、プロセッサアレイ部１３０が重ねて設けられている。プロセッサアレイ部１３０は、１６×１６の合計２５６個のプロセッサエレメント１３１，１３１，…を有している。つまり、各プロセッサエレメント１３１，１３１，…には、１つずつデータバッファ１２１，１２１，…が対応している。
【００３０】
プロセッサアレイ部１３０においては、ブロックマッチングにおける類似度の指標として、排他的論理和の総和（以下、「ＳＸＯＲ(Sum of Exclusive-OR)」という。）が演算される。ここで、「排他的論理和の総和」とは、排他的論理和演算の結果である論理値を数値とみなし、その数値についての総和（算術和としての総和）をとった値をいう。
候補となる動きベクトルがｄ（ｄｘ，ｄｙ）のとき, ＳＸＯＲ値は式（２）で求められる。このとき、ｒ（ｘ，ｙ），ｃ（ｘ，ｙ）はそれぞれ参照ブロックと候補ブロックの座標（ｘ，ｙ）における輝度を表す。
【数２】
2014229263.tif 000004
【００３１】
プロセッサエレメント１３１，１３１，…は、１つ１つがマクロブロックの１画素分の画素データを保持することが可能であり、１クロックサイクルごとにマクロブロックの画素データと候補フレームの画素データとの排他的論理和を出力する。上下に隣り合うプロセッサエレメント１３１，１３１，…は互いにデータバス１２５によって接続されており、排他的論理和の結果は順次真下のプロセッサエレメント１３１，１３１，…に伝送される。真上のプロセッサエレメント１３１からプロセッサエレメント１３１が排他的論理和の結果を受け取ると、当該プロセッサエレメント１３１が演算した排他的論理和と受け取った排他的論理和とが加算され、当該プロセッサエレメント１３１において中間結果として保持される。さらに中間結果は当該プロセッサエレメント１３１の真下のプロセッサエレメント１３１へと伝送され、この中間結果にそのプロセッサエレメント１３１において演算された排他的論理和の結果が加算され、新たな中間結果として保持される。最終的に１６列分の中間結果は、総和部１４０へと与えられる。
【００３２】
図３は、プロセッサエレメント１３１の構成を示す模式図である。上述したように、プロセッサエレメント１３１には、８ビットのビット長の入力レジスタであるデータバッファ１２１が対応して設けられている。また、プロセッサエレメント１３１には、８ビットのビット長の入力レジスタ１３２と、８個（複数；処理データのビット長に応じた数）のＥＸＯＲゲートが列状に配置された排他的論理和演算部１３３と、１２ビットの加算器（算術加算器）１３４と、１２ビットの出力レジスタ１３５とが設けられている。
【００３３】
入力レジスタ１３２には、マクロブロックの１画素分の画素データが保持される。排他的論理和演算部１３３の入力側には、入力レジスタ１３２とデータバッファ１２１とが接続されており、入力レジスタ１３２に保持されたマクロブロックの画素データＢ（Ｂ０〜Ｂ７）と、データバッファ１２１に保持された候補フレーム画像Ａ（Ａ０〜Ａ７）の画素データとが与えられ、対応するビット毎に排他的論理和Ｓ（Ｓ０〜Ｓ７）を演算するようになっている。
排他的論理和演算部１３３によって得られた８ビットの排他的論理和データ（８個の論理値）は、８ビットの数値データとして扱われる。
例えば、マクロブロックの画素データが｛１００１００１０｝であり、候補フレーム画像の画素データが｛１１０１０１１０｝である場合、排他的論理和データは｛０１０００１００｝となる。この場合の絶対差も｛０１０００１００｝である。したがって、この例では、論理値の集合である排他的論理和データと、数値である絶対差と、は同一の値（同一のビット列）となる。
ただし、排他的論理和データと絶対差とは常に一致するとは限らず、例えば、マクロブロックの画素データが｛１００１１０１０｝であり、候補フレーム画像の画素データが｛１１０１０１１０｝である場合、排他的論理和データは｛０１００１１００｝となる。この場合の絶対差は｛００１１１１００｝であり、排他的論理和データと絶対差とは異なる値となる。
【００３４】
かかる排他的論理和データは数値データであるとみなして、加算器（算術加算器）１３４の入力に与えられる。この加算器１３４の入力側は、直上（同列の１つ上の行）のプロセッサエレメント１３１の出力レジスタ１３５にも接続され、このプロセッサエレメント１３１から中間結果が与えられるようになっている。加算器１３４の出力側には、出力レジスタ１３５が接続されており、数値データとみなされた排他的論理和データと、中間結果とを加算した新たな中間結果が、出力レジスタ１３５に出力されるようになっている。出力レジスタ１３５は、直下（同列の１つ下の行）のプロセッサエレメント１３１の加算器１３４（最下行のプロセッサエレメント１３１の出力レジスタ１３５については、総和部１４０）に接続されており、中間結果を出力するようになっている。
【００３５】
図１に示すように、総和部１４０は、１６個の最下行のプロセッサエレメント１３１，１３１，…のそれぞれに接続されており、これらのプロセッサエレメント１３１，１３１，…から出力された中間結果を受け付ける。また、この中間結果を、数値データとして加算することで、ブロックの全画素についての排他的論理和の総和を演算するようになっている。
【００３６】
最小値検出部１５０は、常にＳＸＯＲの最小値を保持するようになっている。つまり、最小値検出部１５０は、比較器等から構成されており、総和部１４０から与えられたＳＸＯＲと、それまでのＳＸＯＲの最小値とを比較し、新たに与えられたＳＸＯＲが、それまでのＳＸＯＲの最小値よりも小さいか否かを判別する。新たに与えられたＳＸＯＲが、それまでのＳＸＯＲの最小値よりも小さい場合には、最小値検出部１５０がこれをＳＸＯＲの最小値として保持する。また、最小値検出部１５０は、最小値が更新されたときには、マクロブロックと候補フレーム画像の探索範囲の座標とから動きベクトルを算出し、これを記憶する。候補フレーム画像の全ての探索が終了したとき、最小値検出部１５０は、マクロブロックに対する動きベクトルを出力部１６０へ出力する。
【００３７】
出力部１６０は、レジスタ等からなり、最小値検出部１５０から与えられた動きベクトルのデータを保持する。かかる出力部１６０は、画像処理装置１００の外部に対して、この動きベクトルデータを出力するようになっている。
【００３８】
上記の如く構成したことにより、本実施の形態に係る画像処理装置１００にあっては、ＳＡＤを用いたブロックマッチングに比して、ブロックマッチングの処理を簡易なものとすることが可能となる。
ここで、図４は、絶対差を演算するための回路構成を示す模式図であり、図５は、排他的論理和演算部１３３の回路構成を示す模式図である。図４に示すように、絶対差の演算回路では、２つの入力Ａ，Ｂに対して、Ａ−Ｂ及びＢ−Ａの２つの減算を同時に行い、正の出力をマルチプレクサで選択することで、絶対差が演算される。
他方、図５に示すように、排他的論理和演算部１３３は、８個のＥＸＯＲゲート１３３ａ，１３３ａ，…によって構成されており、各ＥＸＯＲゲート１３３ａ，１３３ａ，…で同時に排他的論理和を演算する構成であるので、演算に要するステップ数が少なくて済む。
【００３９】
また、ビット毎に取得された複数の排他的論理和からなる排他的論理和データを、桁の概念を有する数値データとして扱うことにより、排他的論理和データを、数値データである絶対差と同様に扱うことができる。つまり、排他的論理和データは、絶対差の演算から桁上げ処理を除外した結果に等しく、高確率で絶対差に近い値となる。特に、桁上げが発生しない組合せでは、排他的論理和データが絶対差と同一となる。このため、類似度を示す指標であるＳＸＯＲは、類似度を高精度に反映した値となっている。
【００４０】
また、排他的論理和には符号が存在しないので、排他的論理和の演算においてＡとＢとを入れ換えても、同じ値となる。そのため、絶対差計算のように回路を並列化する必要はなく、回路規模を減少させることが可能となる。本実施の形態のように、計算のビット幅を８とすると、絶対差計算にはＮＡＮＤ素子換算で１８８ゲートを必要とするが、排他的論理和は３２ゲートと、回路規模は約６分の１になる。そのうえ、排他的論理和には桁上げが存在しないため、クリティカルパスが劇的に短くなる。このため、処理速度の向上も見込める。
【００４１】
排他的論理和の演算では、桁上げ処理が行われないため、入力が同一の場合においては、排他的論理和データが絶対差より小さくなることはない。つまり、排他的論理和データと絶対差との間に誤差が生ずる場合には、常に排他的論理和データの方が絶対差よりも大きくなる（排他的論理和データ≧絶対差）。
ここで、比較する２つの画像間の類似度が低い場合には、それぞれの画像に含まれる画素データが大きく異なることになり、２つの画素データの絶対差は大きい値となる。このように、２つの画素データの絶対差が大きい場合に、排他的論理和データが絶対差よりも小さくなってしまうと、ＳＸＯＲも小さくなり、実際よりも類似度が高いと誤った評価がなされてしまう。しかしながら、上述したように排他的論理和データの方が絶対差よりも必ず大きい値となることから、実際には類似度が低い２つの画素データの類似度を誤って類似度が高いと判断するようなことは起こらない。
【００４２】
（実施の形態２）
排他的論理和データは絶対差に近い値を取る場合が多いものの、誤差が生じる確率が比較的高く、その誤差の大きさは入力の組み合わせによって増減する。図６は、実施の形態１に係る排他的論理和演算部１３３による排他的論理和データと絶対差との誤差を示す図である。図において、横軸は入力Ａを示し、縦軸は入力Ｂを示している。また、図において、誤差が小さいほど淡く、誤差が大きいほど濃くなるように濃淡で誤差の大きさを示している。図において破線で囲んだ領域は、入力ＡとＢとの差が小さい領域である。この領域における誤差の存在は、ブロックマッチングの精度に強く影響する。このため、この領域では、排他的論理和データと絶対差との誤差が小さいことが望まれる。しかしながら、図６から分かるように、破線で囲んだ領域の中の一部において、大きな誤差（濃い部分）を生じている。例えば、入力ビット列が｛１０００００００｝と｛０１１１１１１１｝の場合には、絶対差が１であるのに対して、これらの入力から得られる排他的論理和データを数値（算術値）として扱った場合の値は２５５となり、その誤差は２５４と非常に大きくなる。
つまり、図６からも明らかなように、入力ビット列の上位２ビットがそれぞれ｛１０｝と｛０１｝となる場合、排他的論理和データと絶対差の誤差は最も大きくなる。
【００４３】
そこで、本実施の形態に係る画像処理装置では、排他的論理和の演算において例外処理を導入することで、入力ＡとＢとの差が本来的に小さい領域における、排他的論理和データと絶対差との誤差を低減する。また、本実施の形態では、ブロックマッチングの精度に強く影響を及ぼす排他的論理和演算部の上位ビット（特に最上位ビット）の演算に例外処理を適用することとする。
【００４４】
以下、排他的論理和演算部の入力をそれぞれＡｎ，Ｂｎ、出力をＳｎとして説明する。但し、ｎは０から７の整数であり、ｎが大きいほど上位ビットを指すこととする。
【００４５】
次の真理値表は、実施の形態１に係る排他的論理和演算部１３３の上位２ビットの入力値Ａ７，Ａ６及びＢ７，Ｂ６と、上位２ビットの出力値ＳＸＯＲとの関係を示している。また、下表において、ＳＡＤは、排他的論理和演算部１３３と同じ入力を絶対差演算回路に与えたときの上位２ビットの出力値を示している。
【表１】
2014229263.tif 000005
【００４６】
上記の真理値表からも、入力ビット列の上位２ビットがそれぞれ｛１０｝と｛０１｝となる場合、排他的論理和データと絶対差とに誤差が生じることがわかる。つまり、｛Ａ７，Ａ６｝，｛Ｂ７，Ｂ６｝＝｛１０｝，｛０１｝及び｛Ａ７，Ａ６｝，｛Ｂ７，Ｂ６｝＝｛０１｝，｛１０｝の場合（表において○印で示す箇所）では、絶対差ＳＡＤの最上位ビットＳ７は０であるが、排他的論理和データＳＸＯＲの最上位ビット７は１となっている。
【００４７】
上記の真理値表に基づくと、絶対差ＳＡＤの最上位ビットＳ７は、次の論理式（３）によって表される。
【数３】
2014229263.tif 000006
【００４８】
排他的論理和データＳＸＯＲの最上位ビットＳ７が１となる場合であっても、絶対差ＳＡＤの最上位ビットＳ７が０となるべきである場合、それにあわせて例外的に最上位ビットＳ７を０にすればよい。つまり、最上位ビットＳ７は単純にＡ７とＢ７の排他的論理和として求めるのではなく、上記の論理式（３）によって求めれば、絶対差ＳＡＤの最上位ビットＳ７と一致することになる。
【００４９】
ここで、論理式（３）は、簡略化された次の論理式（４）と等価である。
【数４】
2014229263.tif 000007
【００５０】
排他的論理和演算部には、入力同士の排他的論理和を計算するため、Ａ７，Ｂ７を入力とするＥＸＯＲゲートと、Ａ６，Ｂ６を入力とするＥＸＯＲゲートとが既に存在している。そこで、これらのＥＸＯＲゲートを利用して、例外処理の論理回路を構成するのが好ましい。そこで、ＥＸＯＲゲートを利用できるように、論理式（４）を変形すると、次の論理式（５）を導出することができる。
【００５１】
【数５】
2014229263.tif 000008
【００５２】
図７は、本実施の形態に係る画像処理装置の排他的論理和演算部の構成の一部を示す模式図である。本実施の形態に係る画像処理装置では、排他的論理和演算部２３３の上位ビットに、例外処理回路（例外処理部）２３６が設けられている。例外処理回路２３６は、２つのＯＲゲート、２つのＡＮＤゲート、及び１つのＮＡＮＤゲートの合計５つのゲートから構成されている。かかる例外処理回路２３６は、上記の論理式（６）の演算を実現するための回路である。
【００５３】
例外処理回路２３６は、入力Ａの上位２ビットと、入力Ｂの上位２ビットに基づいて、絶対差の最上位ビットの値を演算し、絶対差の最上位ビットの値が、排他的論理和データの最上位ビットの値となる。
図８は、本実施の形態に係る排他的論理和演算部２３３による排他的論理和データと絶対差との誤差を示すグラフである。図において、横軸は入力Ａを示し、縦軸は入力Ｂを示している。また、図において、誤差が小さいほど淡く、誤差が大きいほど濃くなるように濃淡で誤差の大きさを示している。図６と比較すると、入力Ａ，Ｂの上位２ビットが｛１０｝，｛０１｝における誤差が減少していることが分かる。
【００５４】
実施形態２では、例外処理回路２３６は、排他的論理和データの最上位ビットの値だけを演算するものであるが、排他的論理和データの複数の上位ビット（例えば、上位２ビット又は上位３ビット）の値を演算するものであってもよい。
また、例外処理回路２３６によって排他的論理和データのＸ個の上位ビットの値を求める場合、入力Ａ，Ｂの（Ｘ＋１）個以上の上位ビットを用いるのが好ましい。
なお、本実施の形態に係る画像処理装置のその他の構成及び動作は、実施の形態１に係る画像処理装置１００の構成及び動作と同様であるので、その説明を省略する。
【００５５】
（実施の形態３）
本実施の形態では、ソフトウェアによる情報処理によって、ＳＸＯＲを利用したブロックマッチングを行う画像処理装置について説明する。
【００５６】
まず、本実施の形態に係る画像処理装置の構成について説明する。図９は、本実施の形態に係る画像処理装置の機能ブロック図である。画像処理装置３００は、ＣＰＵ及び主記憶装置としてのメモリを備えたコンピュータによって構成されている。画像処理装置３００を構成するコンピュータには、当該コンピュータを画像処理装置３００として機能させるためのコンピュータプログラム（以下、「画像処理プログラム」という。）がインストールされている。以下の画像処理装置３００の機能は、当該画像処理プログラムがコンピュータによって実行されることによって発揮される。
【００５７】
画像処理装置３００は、入力部３０１、注目ブロック選択部３０２、排他的論理和演算部３０３、総和部３０４、最小値検出部３０５、及び出力部３０６としての機能を有している。また、画像処理装置３００にはハードディスク装置からなる補助記憶装置が内蔵されており、この補助記憶装置によって候補フレームデータベース３０７及びマクロブロックデータベース３０８が構成されている。
【００５８】
入力部３０１は、候補フレーム及びマクロブロックの入力を受け付けるように構成されている。かかる入力部３０１によって受け付けられた候補フレームは、候補フレームデータベース３０７に記憶され、入力部３０１によって受け付けられたマクロブロックは、マクロブロックデータベース３０８に記憶される。
【００５９】
注目ブロック選択部３０２は、候補フレームデータベース３０７に記憶されている候補フレームから、注目ブロックを選択するためのものである。かかる注目ブロック選択部３０２によって、２５６×２５６の候補フレーム画像から、処理対象の領域である１６×１６の注目ブロックが選択される。
【００６０】
排他的論理和演算部３０３は、注目ブロック選択部３０２によって選択された注目ブロックの画素と、及び基準画像であるマクロブロックの互いに対応する画素について、画素データの排他的論理和を演算するためのものである。この排他的論理和演算部３０３によって、注目ブロック及びマクロブロックの２５６画素全てについて、画素データの排他的論理和が演算される。
【００６１】
総和部３０４は、排他的論理和演算部３０３によって得られた各排他的論理和を加算し、ＳＸＯＲを演算するためのものである。
【００６２】
最小値検出部３０５は、総和部３０４によって得られたＳＸＯＲの最小値を保持し、その最小値が得られたときのマクロブロックと候補フレーム画像における注目ブロックの座標とから動きベクトルを算出し、これを記憶する。
【００６３】
出力部３０６は、最小値検出部３０５によって得られた動きベクトルを出力するためのものである。かかる出力部３０６は、例えばディスプレイに動きベクトルを表示したり、ハードディスクに動きベクトルを記憶したりする。
【００６４】
候補フレームデータベース３０７には、候補フレームの画像データが記憶される。また、マクロブロックデータベース３０８には、比較対象であるマクロブロックの画像データが記憶される。
【００６５】
次に、本実施の形態に係る画像処理装置３００の動作について説明する。図１０は、本実施の形態に係る画像処理装置による画像処理の流れを示すフローチャートである。
【００６６】
まず、入力部３０１に入力された候補フレーム及びマクロブロックのそれぞれが、候補フレームデータベース３０７及びマクロブロックデータベース３０８に格納される（ステップＳ１）。
【００６７】
次に、注目ブロック選択部３０２が、候補フレームデータベース３０７から候補ブロックを読み出し、この候補フレームから処理対象の領域である注目ブロックを選択する（ステップＳ２）。
【００６８】
排他的論理和演算部３０３が、マクロブロックデータベース３０８からマクロブロックを読み出し、選択された注目ブロックと、マクロブロックとにおける互いに対応する画素について、画素データの排他的論理和を演算する（ステップＳ３）。排他的論理和が演算されると、排他的論理和演算部３０３が、注目ブロックの全ての画素について排他的論理和が演算されたか否かを判定し（ステップＳ４）、排他的論理和が演算されていない画素が存在する場合には（ステップＳ４においてＮＯ）、ステップＳ３へと処理を戻し、排他的論理和が演算されていない画素について、画素データの排他的論理和を演算する（ステップＳ３）。これを繰り返すことにより、１６×１６の全ての画素について排他的論理和が演算される。
【００６９】
ステップＳ４において、注目ブロックの全画素について排他的論理和が演算された場合には（ステップＳ４においてＹＥＳ）、総和部３０４が、排他的論理和演算部３０３によって演算された２５６個の排他的論理和を加算し、ＳＸＯＲを演算する（ステップＳ５）。
【００７０】
次に最小値検出部３０５が、総和部３０４によって算出されたＳＸＯＲを、それまでに算出されたＳＸＯＲの最小値と比較する（ステップＳ６）。新たなＳＸＯＲがそれまでの最小値よりも小さい場合には、新たなＳＸＯＲが最小値とされ、ＳＸＯＲの最小値が更新される。また、このとき、最小値検出部３０５は、当該新たなＳＸＯＲが演算されたときの注目ブロックの座標と、マクロブロックの座標とから、動きベクトルを演算し、この動きベクトルを記憶する。新たなＳＸＯＲよりも最小値の方が小さい場合には、それまでの最小値が維持される。なお、第１回目に演算されたＳＸＯＲについては、これが最小値とされる。
【００７１】
次に、候補フレームの全領域について、注目ブロックが選択されたか否かが判定され（ステップＳ７）、候補フレームにおいて注目ブロックとして選択されていない領域が残っている場合には（ステップＳ７においてＮＯ）、処理がステップＳ２へと戻され、候補フレームにおける未選択の領域が、注目ブロックとして選択され（ステップＳ２）、ステップＳ３以降の処理が実行される。
【００７２】
ステップＳ７において、候補フレームの全ての領域について、注目ブロックが選択された場合には（ステップＳ７においてＹＥＳ）、出力部３０６が、ＳＸＯＲの最小値が得られたときの動きベクトルを出力し（ステップＳ８）、処理を終了する。
【００７３】
（評価実験１）
実施の形態１及び２において説明した構成の画像処理装置（動き検出プロセッサ）を、２．５ｍｍ角のＬＳＩに実装した。ハードウェア記述言語としてＶｅｒｉｌｏｇＨＤＬを、論理合成にＳｙｎｏｐｓｙｓ社製のＤｅｓｉｇｎ  Ｃｏｍｐｉｌｅｒを、自動配置配線に同社のＩＣ  Ｃｏｍｐｉｌｅｒを、設計規則にローム０．１８μｍ設計プロセスを使用した。また、比較対象として、同様の条件でＳＡＤによる動き検出プロセッサも作製した。
【００７４】
表２に、ＳＡＤによる動き検出プロセッサ（表２では「ＳＡＤ」と表記）、実施の形態１に係る動き検出プロセッサ（表２では「ＳＸＯＲ」と表記）、及び実施の形態２に係る動き検出プロセッサ（表２では「例外処理付きＳＸＯＲ」と表記）のそれぞれについて、動き検出プロセッサ全体の面積及び最大動作周波数を示す。動き検出プロセッサの面積は、実装したマクロ全ての合計を、動作周波数はプロセッサ全体のクリティカルパスを元に計算した。
【表２】
2014229263.tif 000009
【００７５】
また、表３に、ＳＡＤによる動き検出プロセッサ（表３では「ＳＡＤ」と表記）、実施の形態１に係る動き検出プロセッサ（表３では「ＳＸＯＲ」と表記）、及び実施の形態２に係る動き検出プロセッサ（表３では「例外処理付きＳＸＯＲ」と表記）のそれぞれについて、プロセッサアレイ部の面積及び最大動作周波数を示す。
【表３】
2014229263.tif 000010
【００７６】
表２及び表３から分かるように、プロセッサ全体の動作周波数はプロセッサアレイ部に依存しており、面積の差異も殆どがプロセッサアレイ部によるものである。結果として、ＳＸＯＲによる動き検出プロセッサは、ＳＡＤによる動き検出プロセッサと比較して、面積がプロセッサ全体で約１４％、プロセッサアレイ部で約４割削減されており、動作周波数が約１．２５倍向上している。また、例外処理付きＳＸＯＲによる動き検出プロセッサでは、ＳＸＯＲによる動き検出プロセッサと比較して、面積及び動作周波数の両方において若干劣っているものの、その差は１％前後であった。このように、例外処理付きＳＸＯＲによる動き検出プロセッサにおいても、ＳＸＯＲによる動き検出プロセッサと同様に良好な結果が得られた。
【００７７】
（評価実験２）
また、本発明者らは、実施の形態１乃至３に係る画像処理装置の性能を評価するために、ソフトウェアシミュレーションによる評価実験を行った。具体的には、ＳＸＯＲ、例外処理付きＳＸＯＲ、及びＳＡＤのそれぞれを利用した動き検出プログラムを実装し、それぞれのプログラムによって動画像の符号化を行った。なお、動画圧縮規格はＭＰＥＧ２(Moving Picture Experts Group phase 2)に準拠するものとし、符号化する動画にはVideo Qualiuty Experts Group (VQEG)が提供するサンプル動画(Football, Susie, Mobile)を使用した。表４に、実験環境を示し、表５に、実験結果を示す。
【表４】
2014229263.tif 000011
【表５】
2014229263.tif 000012
【００７８】
ノイズの測定には、Peak Signal to Noise Ratio (PSNR)を使用した。PSNRは、画像に含まれるノイズの比率であり、符号化前野画像と符号化後の画像を比較することで計測される。一般的に、高画質と呼ばれる画像のＰＳＮＲは３０ｄｂ以上であり、本実験により符号化した画像は全てこれを満たしていた。また、表５に示すように、例外処理を付加していないＳＸＯＲによる動き検出及び例外処理付きのＳＸＯＲによる動き検出の両方において、ＳＡＤによる動き検出との誤差は１．０ｄｂ以内に収まっており、十分に高い画質であると言える。また、例外処理付きＳＸＯＲによる動き検出では、全ての動画においてＳＸＯＲによる動き検出よりよい結果が得られた。
【００７９】
また、ＸＳＯＲを利用した動き検出では、符号化に要する計算時間が、ＳＡＤを利用した動き検出よりも１２％程度短縮できた。
【００８０】
（その他の実施の形態）
上述した実施形態１乃至３においては、動画の符号化を行う動き検出において、ＳＸＯＲ及び例外処理付きＳＸＯＲを利用する構成について述べたが、これに限定されるものではない。例えば、音声圧縮等において、ＳＸＯＲ又は例外処理付きＳＸＯＲを演算する構成とすることも可能である。
【符号の説明】
【００８１】
１００，３００  画像処理装置（データ処理装置）
１２０  データバッファ部
１２１  データバッファ
１３０  プロセッサアレイ部
１３１  プロセッサエレメント
１３２  入力レジスタ
１３３，２３３，３０３  排他的論理和演算部
１３３ａ  ＥＸＯＲゲート
１３４  加算器
１３５  出力レジスタ
１４０，３０４  総和部（類似度演算部）
１５０，３０５  最小値検出部
２３６  例外処理回路（例外処理部）
３０２  注目ブロック選択部
３０７  候補フレームデータベース
３０８  マクロブロックデータベース
【図１】
2014229263.tif 000013
【図２】
2014229263.tif 000014
【図３】
2014229263.tif 000015
【図４】
2014229263.tif 000016
【図５】
2014229263.tif 000017
【図７】
2014229263.tif 000018
【図９】
2014229263.tif 000019
【図１０】
2014229263.tif 000020
【図６】
2014229263.tif 000021
【図８】
2014229263.tif 000022