(57)【特許請求の範囲】
【請求項１】
第１の画像上の所定の大きさの矩形領域を探索対象矩形領域とし、第２の画像上に、その探索対象矩形領域と同じ大きさの複数の評価矩形領域を順次設定し、上記探索対象矩形領域に対して最も類似度が高い、上記第２の画像上での評価矩形領域を探索する画像照合装置において、
上記探索対象矩形領域及び現在探索対象となっている上記評価矩形領域を複数に分割した、しかも、指定された単位要素の類似度を得る単位要素類似度算出手段と、
単位要素毎の類似度を合成して、現在探索対象となっている上記評価矩形領域の類似度を得る、単位要素類似度合成手段と、
複数の評価矩形領域について同一値となる単位要素の類似度の情報を格納している共通単位要素類似度格納手段と、
現在探索対象となっている上記評価矩形領域の単位要素を認識し、上記共通単位要素類似度格納手段に単位要素の類似度が格納されているものであれば、その単位要素の類似度を上記単位要素類似度合成手段に出力させ、上記共通単位要素類似度格納手段に単位要素の類似度が格納されていないものであれば、その単位要素の類似度を、上記単位要素類似度算出手段によって算出させて上記単位要素類似度合成手段に出力させる単位要素別処理切換手段と
を有することを特徴とする画像照合装置。
【請求項２】
上記共通単位要素類似度格納手段は、同一値となる単位要素の類似度を有する複数の評価矩形領域が対象となる前に、格納情報が設定されるものであることを特徴とする請求項１に記載の画像照合装置。
【請求項３】
上記共通単位要素類似度格納手段は、同一値となる単位要素の類似度を有する複数の評価矩形領域のいずれかが処理対象となっているときに、上記単位要素類似度算出手段が算出した単位要素の類似度を、他の評価矩形領域の類似度算出で利用できるように格納するものであることを特徴とする請求項１に記載の画像照合装置。
【請求項４】
上記共通単位要素類似度格納手段は、複数の単位要素の類似度を合算値で格納するものであることを特徴とする請求項３に記載の画像照合装置。
【請求項５】
上記単位要素が、上記矩形領域の水平ライン又は垂直ラインであることを特徴とする請求項１〜４のいずれかに記載の画像照合装置。
【請求項６】
上記第２の画像が、上記第１の画像と同じ大きさの原画像を、その周囲画素値を利用して拡張した拡張画像であることを特徴とする請求項１〜５のいずれかに記載の画像照合装置。
【請求項７】
上記第２の画像が、上記第１の画像と同じ大きさの原画像を、その周囲画素値を利用して拡張した拡張画像であって、画像読出部から読み出すものであり、
上記画像読出部が、
上記第２の画像を構成する画素値の集合でなる画像情報を記憶する画像記憶手段と、
入力された座標値におけるｘ座標又はｙ座標値の少なくとも１方を、上記画像記憶手段のアクセス用の座標値に置換するための座標変換情報を記憶する座標変換情報記憶手段と、
上記入力された座標におけるｘ座標値又はｙ座標値を、上記座標変換情報記憶手段をアクセスして上記画像記憶手段のアクセス用の座標値に置換する座標置換手段と、
この座標置換手段から出力されたｘ座標値又はｙ座標値、及び又は、入力された置換されていないｙ座標値またはｘ座標値に基づいて、上記画像記憶手段をアクセスして画素値を取り出す画像読出手段とでなる
ことを特徴とする請求項１〜６のいずれかに記載の画像照合装置。
【請求項８】
上記画像記憶手段は、原画像をｘ方向（又はｙ方向）に拡張した画像の情報を記憶したものであり、上記座標変換情報記憶手段は、入力された座標値におけるｙ座標値（又はｘ座標値）を置換するための座標変換情報を記憶しているものであり、上記画像読出手段は、置換されたｙ座標値（又はｘ座標値）と、入力されたｘ座標（又はｙ座標）に基づいて、上記画像記憶手段をアクセスして画素値を取り出すものであることを特徴とする請求項７に記載の画像照合装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像照合装置に関し、例えば、動画像符号化などに利用される動きベクトル探索装置に適用し得るものである。
【０００２】
【従来の技術】
動画像のディジタル圧縮符号化においては、動画像の時間的冗長性を減少させる目的で、動き補償フレーム間予測がしばしば用いられる。
【０００３】
この動き予測には動きベクトル探索処理が不可欠であるが、その処理は、圧縮しようとする画像を１６×１６画素等の大きさの矩形領域（部分画像）に分割し、それぞれの矩形領域に対して類似度の高い矩形領域を予測参照画像中から見つけ出すことが主な処理である。類似度の評価には、矩形領域同士の画素値の差の絶対値和、若しくは、矩形領域同士の画素値の差の２乗和が良く使われている。
【０００４】
一方、符号化技術の研究で、予測参照画像中の画像端の画素値を使って画像の範囲を拡張することにより、画像の境界にまたがった物体の動きに対しても正確な予測が可能（Ｕｎｒｒｅｓｔｒｉｃｔｅｄ  Ｍｏｔｉｏｎ  ｖｅｃｔｏｒ  ｍｏｄｅ：非制限動きベクトルモード）となり、符号化効率の向上をもたらすことが分かっている。これは、例えば、ＩＴＵ−Ｔ勧告Ｈ．２６３  Ａｎｎｅｘ  Ｄなどで周知技術である。
【０００５】
このような画像範囲拡張技術を利用した動きベクトルの従来の探索方法を、ＩＴＵ−Ｔ勧告Ｈ．２６３  Ａｎｎｅｘ  Ｄに規定されているものを例として説明する。
【０００６】
ＱＣＩＦサイズ（１７６×１４４画素）の非制限動きベクトルモードの画像（周辺が拡張された参照画像）の画素値（例えば輝度値）Ｒｕｍｖ（ｘ，ｙ）は、周辺が拡張される前の参照画像の画素値をＲ（ｘ’，ｙ’）で表すと、以下の（１）式のように定義される。なお、ｘ，ｙ，ｘ’，ｙ’は画素領域での空間座標であり、拡張される前の参照画像におけるｘ’及びｙ’はそれぞれ、０〜１７５、０〜１４４の範囲内の値をとるものである。
【０００７】
0003865541.tif 000002
このような（１）式によって拡張された参照画像を、言い換えると、（１）式による拡張方法を、図２を使用して説明する。
【０００８】
図２（ａ）及び（ｂ）において、白領域は拡張前からある画素を有する領域であり、左上ハッチが付与された（以下、記載の簡潔化のため「灰色」と呼ぶ）領域が拡張された領域である。図２（ａ）は拡張された画素も含めた全体を表現している。図２（ａ）の破線で囲まれた領域を拡大して示したものが、図２（ｂ）である。図２（ｂ）において、その上側及び左側に、ｘ座標軸及びｙ座標軸を示してある。この図２（ｂ）においては、ｘ座標が−３以上４以下で、ｙ座標が−３以上３以下である領域を示している。また、各枡目は画素を表しており、枡目に書かれている値はそれぞれの画素値である。
【０００９】
例えば、拡張された領域にある座標（３、−１）の画素値の値は、（１）式に従って、Ｒｕｍｖ（３，−１）を求めれば良く、これはＲ（３，０）と等しく、すなわち、拡張前後の参照画像かを問わず、ｘ座標が３でｙ座標が０の画素の画素値と同じ値となる。さらに例えば、拡張領域に属する座標（−２，３）の画素値は、拡張前後の参照画像かを問わず、座標（０，３）の画素値と同じ値となる。図２（ｂ）の灰色領域（拡張領域）の周辺画素の画素値は、以上のように、拡張領域を規定するマイナス座標値（ｘ座標若しくはｙ座標のどちらか１個がマイナス座標値をとることもあり、ｘ座標及びｙ座標の両方ともがマイナス座標値をとることもある）を０に置き換えた位置の座標値を適用している。
【００１０】
次に、このようにして拡張された領域を持った予測参照画像を用いた動きベクトルの探索について説明する。
【００１１】
図３は、物体が動いていく様子を表した画像を模式的に示したものである。説明を簡単にするため、図３（ａ）に示す予測参照画像の方が時間的に前に位置しているとする。なお、動き補償フレーム間予測を考慮し、動きベクトルの検出対象画像を、図３では圧縮対象画像と表現している。灰色矩形で表しているある物体ＭＭは、図３（ａ）に示す参照画像では上部に位置し、その物体ＭＭの移動により、図３（ｂ）で示す圧縮対象画像ではその物体ＭＭは右下の位置に移動している。図３（ａ）では、その物体ＭＭの一部が参照画像の外にはみ出している状態（画像要素となっていない状態）を示している。
【００１２】
ここで、図３（ｂ）に示す圧縮対象画像の灰色領域（物体ＭＭ）と類似度が高い部分が、図３（ａ）に示す予測参照画像のどこにあるかを探索することを考える。
【００１３】
予測参照画像が図４（ａ）に示すような周辺領域（拡張領域）が存在しない場合（非制限動きベクトルモードではない場合）には、図４（ｂ）に示す灰色領域ＭＭと最も類似度が高い領域は、例えば、図４（ａ）における破線で囲まれた領域ＡＲ１となる。
【００１４】
これに対して、予測参照画像が図５（ａ）に示すような周辺領域（拡張領域）が存在する場合（非制限動きベクトルモードの場合）であると、図５（ｂ）に示す灰色領域ＭＭと最も類似度が高い領域は、図５（ａ）における破線で囲まれた領域ＡＲ２となる。
【００１５】
この領域ＡＲ２は、図５（ｂ）に示す灰色領域ＭＭの全範囲と同じ大きさの領域であるが、周辺領域（拡張領域）が存在しない予測参照画像について得られた領域ＡＲ１は、図４（ｂ）に示す灰色領域ＭＭの一部しか重複しておらず、この領域ＡＲ１は、灰色領域ＭＭ以外の領域にも対応した部分を有する。
【００１６】
このことからは、動き補償フレーム間予測方式に従って、画像圧縮する場合には、周辺に拡張した領域を有する参照画像を適用した方が、圧縮効率が高くなるということが分かる。すなわち、図４及び図５の比較から、灰色領域ＭＭに対する照合結果は、周辺に拡張した領域を有する参照画像を適用した方（非制限動きベクトルモードの方）が良く、動き補償フレーム間予測のために、参照画像の画素値との差分を得た場合に、差分値は小さな値となり、符号化データ量が少なくなる。
【００１７】
ところで、誤り耐性の向上のため、１枚の画像を複数の部分に分割し、分割された部分に閉じた範囲の情報で復号できるような方法が開発されている（例えばＨ．２６３  Ａｎｎｅｘ  Ｒにて周知されている）。この方法でも、画像端の画素値を用いて周囲を拡張した予測参照画像を利用して、画像境界にまたがる物体の移動を効率的に符号化することが可能である。
【００１８】
【発明が解決しようとする課題】
しかしながら、上述した周辺画像を拡張した予測参照画像を使って、動きベクトルを探索する場合など、実際に存在しない画素も検索対象に入るため拡張していない場合に比べ処理量が増大し、又は、処理に必要な画素値を記憶する記憶装置の記憶容量が多大になってしまう。
【００１９】
例えば、図６に示すように、ＱＣＩＦサイズ（１７６×１４４画素）の画像を、１７６×１６画素からなる９個のブロックに分割し、各ブロックの周辺画像の拡張を上下左右共に１６画素ずつにし、拡張された分割ブロックを探索対象画像とすることもある。そして、圧縮対象画像での１６×１６画素の矩形領域の単位（マクロブロックと呼ぶ）で動きベクトルを探索するとし、予測参照画像（拡張分割ブロック）での、その矩形領域の位置を中心とした、その矩形領域の上下左右の１６画素ずつを含めた範囲（４８×４８画素）を、動きベクトルの探索範囲をする方法もある。また、マクロブロックと予測参照画像内の特定の領域（拡張分割ブロック）の類似度を差の絶対値和で求めるとする。
【００２０】
まず、拡張範囲での画素値を、類似度計算毎に求める場合を説明する。ある予測参照画像内の矩形領域とマクロブロックの類似を見るためには、まず、参照予測画像の画素値を（１）式に従って確定しなければならない。この確定には、（１）式から明らかなように、拡張領域に属するか否かを判定する必要があり、そのため、１画素の画素値を確定するためには条件判定を４回実行する必要がある。マクロブロック内の画素数は、２５６画素であるので、１画素当たり４回の条件判定を、２５６画素について実行しなければならない。
【００２１】
このような条件判定を、近年のパイプライン処理を行なうことで高速化しているマイクロコンピュータによる処理で行うことは適切ではない。すなわち、パイプライン処理は、分岐が少ない処理には適しているが、分岐が多い処理の場合には、準備している次の処理が無駄になることも多く、上述したような条件判定が多い処理では、パイプライン処理が乱れ、高速に処理ができなくなる。
【００２２】
また、マクロブロックと照合される予測参照画像での１６×１６画素の計２５６画素の画素値の確定が終了すると、次に、類似度を計算する。これは、対応画素間の差の絶対値を求め、それらの総和を計算する演算である。この演算には、画素間の差の絶対値を求める演算が２５６回だけ、和を求めるための加算処理が２５５回だけ必要である。マクロブロックと、予測参照画像上でのある１６×１６画素の領域との類似度計算にも非常に多くの演算が必要であり、この演算が必要としても、画素値確定処理をも考慮に入れると、予測参照画像上でのある１６×１６画素の領域に対する類似度演算にも非常に多くの処理が必要となっている。
【００２３】
そのため、上述した条件判定を可能な限り削除することが必要である。この方法として、予め、周辺領域を拡張した参照画像の全体を求めて記憶装置に記憶させ、マクロブロック毎の処理では、（１）式の判定を行う代わりに、記憶装置から、画素値を読み出す方法が容易に考えられる。
【００２４】
しかしながら、この方法では、拡張領域の画素値も記憶する必要があり、記憶容量が多く必要となる。特に、上述した図６のような拡張分割ブロックを参照画像とする場合ではかかる課題は大きい。
【００２５】
拡張領域の画素値を記憶しない場合には、画素値を記憶する画素数は２５３４４＝１７６×１４４である。画像をブロックに分割しないで、周辺画像を拡張した場合の全画素数は３６６０８＝（１６＋１７６＋１６）×（１６＋１４４＋１６）である。画像をブロックに分割した場合の全画素数は、８９８５６＝（１６＋１７６＋１６）×（１６＋１６＋１６）×９である。
【００２６】
拡張分割ブロックを参照画像とする場合の必要な記憶容量は、拡張領域の画素値を予め求めない方法の場合に比較すれば、約３．５５倍だけ必要であり、画像をブロックに分割しないで周辺領域の画素値を予め求めておく場合に比較すると、約２．４５倍だけ必要である。
【００２７】
また、分割ブロックにおいて、領域を拡張しない場合は、それぞれのマクロブロックが探索する範囲は、最大でもマクロブロックを左右±１６画素の範囲内で探索すれば良い。ところが、参照画像を拡張した場合には、上下±１６画素の範囲も探索する必要があるので、探索処理量は３２倍となる。
【００２８】
以上のように、参照画像の領域を拡張して探索するようにした場合には、処理量、若しくは、必要な記憶容量が増大するという課題がある。処理量の増大は、ソフトウェア処理を中心とするものであれば、処理時間の長期化になり、ハードウェアによる処理を中心とするものであれば、規模の増大や複雑化になる。
【００２９】
上述した課題は、動きベクトル探索装置について生じているだけでなく、動領域切出装置や動領域／静止画領域弁別装置などの参照画像との照合処理を含む画像処理装置にも生じている。
【００３０】
そのため、照合のための処理量を従来より削減できる画像照合装置が求められている。
【００３１】
【課題を解決するための手段】
かかる課題を解決するため、本発明は、第１の画像上の所定の大きさの矩形領域を探索対象矩形領域とし、第２の画像上に、その探索対象矩形領域と同じ大きさの複数の評価矩形領域を順次設定し、探索対象矩形領域に対して最も類似度が高い、上記第２の画像上での評価矩形領域を探索する画像照合装置において、（１）探索対象矩形領域及び現在探索対象となっている評価矩形領域を複数に分割した、しかも、指定された単位要素の類似度を得る単位要素類似度算出手段と、（２）単位要素毎の類似度を合成して、現在探索対象となっている評価矩形領域の類似度を得る、単位要素類似度合成手段と、（３）複数の評価矩形領域について同一値となる単位要素の類似度の情報を格納している共通単位要素類似度格納手段と、（４）現在探索対象となっている評価矩形領域の単位要素を認識し、共通単位要素類似度格納手段に単位要素の類似度が格納されているものであれば、その単位要素の類似度を単位要素類似度合成手段に出力させ、共通単位要素類似度格納手段に単位要素の類似度が格納されていないものであれば、その単位要素の類似度を、単位要素類似度算出手段によって算出させて単位要素類似度合成手段に出力させる単位要素別処理切換手段とを有することを特徴とする。
【００３３】
【発明の実施の形態】
（Ａ）第１の実施形態
以下、本発明による画像照合装置の第１の実施形態を図面を参照しながら詳述する。
【００３４】
なお、以下では、これら第１の実施形態の画像読出装置及び画像照合装置が、動きベクトル探索装置に適用されているとして説明を行う。
【００３５】
第１の実施形態の画像読出装置は、予測参照画像中の指定された座標の画素値を出力するものであるが、拡張した周辺画像領域の画素値として、ｘ方向にだけ拡張した領域の画素値を記憶しているものであり、ｙ方向の拡張領域の画素値としては記憶している原画像領域（拡張領域以外の領域を原画像領域と呼ぶ）のいずれかの画素値を出力するものである。第１の実施形態の画像照合装置は、このような第１の実施形態の画像読出装置を適宜アクセスして照合処理を行うものである。
【００３６】
（Ａ−１）第１の実施形態の構成
図１は、この第１の実施形態の画像読出装置１００の構成を示すブロック図である。
【００３７】
第１の実施形態の画像読出装置１００には、図示しない画像照合装置本体から、画素値を必要とする座標が入力され、その入力された座標に係る画素値が、画像読出装置１００から、図示しない画像照合装置本体に与えられる。ここで、入力座標は、当然に、ｘ座標とｙ座標との組になっている。また、入力される座標として、ｘ方向及びｙ方向への拡張領域の座標を指示する座標もあり得る。なお、画像読出装置１００と、図示しない画像照合装置本体とで画像照合装置が構成されている。
【００３８】
図１において、第１の実施形態の画像読出装置１００は、ｙ座標置換部１０１、ライン番号格納部１０２、予測参照画像格納部１０３及び画素値読出部１０４を有する。
【００３９】
予測参照画像格納部１０３は、動き補償フレーム間予測方式に従って符号化する際に適用される予測参照画像を記憶するものである。この予測参照画像格納部１０３における予測参照画像（画素値）の格納にも、この第１の実施形態の特徴がある。
【００４０】
図７は、予測参照画像格納部１０３に格納されている予測参照画像を示すものである。図７（ａ）は、予測参照画像格納部１０３に格納されている予測参照画像を模式的に表したものであり、白色領域は元々の１フレーム分の画像（画素値）を格納している原画像領域であり、灰色領域が拡張領域である。この図７（ａ）に示すように、予測参照画像格納部１０３に格納されている拡張領域の画素値は、ｘ方向の拡張領域についてのものだけである。ｘ方向の拡張領域についての画素値は、上述した（１）式に従って予め求められ、予測参照画像格納部１０３に格納されている。図７（ｂ）は、図７（ａ）の破線で囲まれた領域を拡大したものである。それぞれの枡目が画素を表している。図７（ｂ）の上部には、ｘ座標軸を、左部にはｙ座標軸を記載している。
【００４１】
予測参照画像格納部１０３には、拡張領域のうち、ｘ方向の拡張領域についての画素値しか格納されていないが、上述したように、当該画像読出装置１００へ入力される座標としては、ｘ方向及び又はｙ方向への拡張領域の座標を指示する座標もあり得る。このような画素値が格納されている拡張領域の範囲と、入力座標が取り得る拡張範囲との相違を補完するために、ｙ座標置換部１０１及びライン番号格納部１０２が設けられている。
【００４２】
ｙ座標置換部１０１は、入力されたｙ座標を、ライン番号格納部１０２の格納情報を用いて、画素値読出部１０４へ与えるｙ座標に置換するものである。
【００４３】
この第１の実施形態の場合、ライン番号格納部１０２は、図８に示すテーブル構成でなっている。図８は、上部側の拡張領域に係る部分を取り出して示している。また、図８は、ｙ方向の上方への拡張領域が４画素の例の場合である。図示は、省略しているが、ｙ方向の下方への拡張領域も４画素である。
【００４４】
図８において、矩形の連結したものはデータの配列を表しており、それぞれの配列の中に、出力するライン番号（ｙ座標）が格納されている。それぞれの要素は、図８の左側に示してあるｙ座標軸（このｙ座標軸はｙ方向に画素を拡張した場合のｙ座標である）をインデックス（アドレス）とし、実際に画素値が格納されている予測参照画像格納部１０３でのライン番号（ｙ座標）を格納している。この図８から、例えば、ｙ方向に拡張された画素のｙ座標＝−４に対応するライン番号（出力ｙ座標）は０であり、ｙ座標＝３に対応するライン番号（出力ｙ座標）は３であることが分かる。
【００４５】
なお、予測参照画像の元々のサイズが、例えば、ＱＣＩＦサイズ（１７６×１４４画素）である場合において、ライン番号格納部１０２におけるｙ方向の下方への拡張領域については、図示は省略するが、入力ｙ座標が１４４〜１４７のいずれかであれば、１４３のライン番号（出力ｙ座標）を出力するように、ライン番号格納部１０２は構成されている。
【００４６】
入力されたｙ座標が原画像領域のｙ座標範囲の値である場合には、ライン番号格納部１０２からは、そのｙ座標値と同じライン番号（ｙ座標値）が出力される。そのため、ライン番号格納部１０２に、入力されたｙ座標が原画像領域のｙ座標範囲の値である場合用の情報を格納しておかないことも考えられるが、この場合には、ｙ座標置換部１０１で、判定処理も行うことになり、処理が煩雑となるので、図８に示す構成とすることが好ましい。
【００４７】
画素値読出部１０４は、入力されたｘ座標と、ｙ座標置換部１０１からのライン番号（ｙ座標）とをもとに、予測参照画像格納部１０３から画素値を読み出して、図示しない画像照合装置本体に出力するものである。
【００４８】
（Ａ−２）第１の実施形態の動作
図示しない画像照合装置本体は、圧縮対象画像と予測参照画像との照合に必要な座標の画素値を取り出すため、画像読出装置１００に対して、ｘ座標及びｙ座標を入力する。
【００４９】
このとき、画像読出装置１００のｙ座標置換部１０１は、ライン番号格納部１０２から、入力されたｙ座標の値に対応したライン番号（ｙ座標）を読み出す（図８参照）。読み出されたｙ座標は、入力されたｘ座標と共に、画素値読出部１０４に与えられる。画素値読出部１０４は、そのｘ座標及びライン番号（ｙ座標）の画素値を、予測参照画像格納部１０３から画素値を取り出し、画像照合装置本体に出力する。
【００５０】
図９に、入力されたｙ座標と、画素値が出力される予測参照画像格納部１０３での座標との関係をこの様子を示す。図９（ａ）は、ライン番号格納部１０２のデータ構成図（図８を再掲載）であり、図９（ｂ）は、図７（ｂ）と同様に、予測参照画像格納部１０３に格納されている予測参照画像の一部を表している。入力されたｙ座標の値は、図９（ａ）に従って、ライン番号（ｙ座標）に変換される。例えば、入力されたｙ座標が−４であるならばライン番号０に変換され、入力されたｙ座標が０であるならばライン番号０に変換され、入力されたｙ座標が８であるならばライン番号８に変換される。このようなライン番号と、入力されたｘ座標の値とから、図９（ｂ）に示す格納されている予測参照画像での画素値の座標が特定でき、その画素値が読み出される。
【００５１】
（Ａ−３）第１の実施形態の効果
上述した第１の実施形態の画像読出装置及び画像照合装置によれば、以下の効果を奏することができる。
【００５２】
格納領域の画素値については、予めｘ方向への画素値のみを求めて格納しておくようにしたので、従来技術に比較し、拡張された周辺領域用の画素値を格納する記憶容量を減少させることができる。ライン番号格納部１０２が必要となっているが、拡張画像でのライン数分だけのデータで良いので、記憶容量の減少を妨げるものにはなっていない。
【００５３】
また、ｙ方向の拡張領域の画素値は予め格納をしていないが、入力されたｙ座標をライン番号（ｙ座標）に変換するライン番号格納部１０２を利用しているため、入力された座標が拡張領域に属するか否かを判定することを不要にできる。そのため、パイプライン処理を行なうマイクロプロセッサを利用したとしても、パイプライン処理に、条件分岐による乱れが生じなくなり、高速に処理を行うことができるようになる。
【００５４】
（Ａ−４）第１の実施形態を変形した実施形態
なお、第１の実施形態は、画素値を格納しておく拡張領域の方向をｘ方向とし、座標値の変換を行う方向をｙ方向としたものを示したが、画素値を格納しておく拡張領域の方向をｙ方向とし、座標値の変換を行う方向をｘ方向としたものであっても良い。
【００５５】
また、原画像領域に属する画素値だけを予測参照画像格納部に格納させておき、入力されたｘ座標及びｙ座標の双方をそれぞれ、ｘ座標置換部及びｙ座標置換部で置換してから、画素値読出部に与えて、予測参照画像格納部から画素値を読み出すようにしても良い。
【００５６】
この場合には、第１の実施形態以上に必要とする記憶容量を削減することが可能となる。
【００５７】
（Ｂ）第２の実施形態
以下、本発明による画像照合装置の第２の実施形態を図面を参照しながら詳述する。なお、以下では、第２の実施形態の画像照合装置が、動きベクトル探索装置に適用されているとして説明を行う。
【００５８】
第２の実施形態の画像照合装置は、圧縮対象画像と予測参照画像との所定大きさの矩形領域による類似度判定での演算回数を減少させることを目的としてなされたものである。第２の実施形態の画像照合装置は、拡張領域を有する予測参照画像においては、その拡張領域での画素値は、ｙ方向又はｘ方向を固定して見ると、他方の方向が変化しても同一であるという性質を利用してなされたものである。
【００５９】
図１０は、類似度の比較対象の画素範囲を示している。説明を簡単にするために、探索単位が４×４画素の矩形領域とする。類似度の評価は、圧縮対象画像の指定された矩形領域（以下、探索対象矩形領域と呼ぶ）と、予測参照画像中の類似度を評価する矩形領域（以下、評価矩形領域と呼ぶ）を取り出して行う。評価矩形領域は、探索対象矩形領域と、最も類似している部分が見つかるまで切り換えられる。又は、複数の評価矩形領域との類似度を得た後、最も類似度が高い評価矩形領域が決定する。
【００６０】
図１０（ａ）は、圧縮対象画像の一部を表しており、太い実線で囲んだ４×４画素の領域が類似度を求める探索対象対象領域である。探索対象矩形領域中の網模様（右上ハッチと左上ハッチの重畳模様）の部分（左上画素）を探索対象矩形領域内用の座標の原点にとり、図中の矢印の方向に座標軸Ｍｘ、Ｍｙをとる（なお、探索対象矩形領域内用の座標の原点を、圧縮対象画像での座標系では（Ｘ，Ｙ）で表す）。図１０（ｂ）は予測参照画像であり、この画像の中から、探索対象矩形領域と最も類似度が高い評価矩形領域が見つけ出される。探索対象矩形領域から、その探索対象矩形領域と最も類似度が高い評価矩形領域へのｘｙ平面上でのずれ、又は、その逆方向のずれが検出された動きベクトルとなる。
【００６１】
（Ｂ−１）第２の実施形態の構成
図１１は、第２の実施形態の画像照合装置２００の要部構成を示すブロック図である。なお、図１１では、圧縮対象画像の格納部や、予測参照画像の格納部や、これら格納部に対するアクセス構成は省略しており、図１１は、類似度の探索面から、画像照合装置２００の構成を示している。また、図１１では、最大の類似度を与える評価矩形領域の決定構成も省略している。
【００６２】
第２の実施形態の画像照合装置２００の図１１に示す構成部分には、圧縮対象画像中の探索対象矩形領域を代表する（Ｘ，Ｙ）と、予測参照画像中のある評価矩形領域を代表する座標（Ｘ０，Ｙ０）とが入力され、探索対象矩形領域に対するその評価矩形領域の類似度が評価値として出力される。
【００６３】
ここで、この第２の実施形態の画像照合装置２００においては、予測参照画像中の評価矩形領域の移動の仕方も定まっている。このことを、図１２を参照しながら説明する。
【００６４】
ｘ方向が同じ複数の評価矩形領域については、図１２（ａ）、…、（ｂ）、…、（ｃ）…の順（又はこの逆の順）に、ｙ座標が小さい（又は大きい）評価矩形領域を先に評価する。そして、同一のｘ座標を有する評価矩形領域の全てに対し、評価し終えた（類似度計算をし終えた）後で、ｘ座標を変化させ、上述したｙ方向の移動を行う。ｙ方向に全て探索を終えてからｘ方向に移動することが要件であり、探索（類似度評価）の重複がなければ、ｘ方向にはどのように移動しても良い。
【００６５】
図１１に示す構成は、このような評価矩形領域の変化順序をも考慮してなされたものである。
【００６６】
図１１において、第２の実施形態の画像照合装置２００は、評価ライン指示部２０１、ライン評価値格納部２０２、既評価判定部２０３、１ライン評価値読出部２０４、１ライン類似度評価部２０５、１矩形領域評価値格納部２０６及び評価値加算部２０７を有する。
【００６７】
ライン評価値格納部２０２は、後述するようなライン（この第２の実施形態の説明においてラインとは水平ラインを呼んでいる）毎の評価結果（類似度計算値）を格納しているものである。このライン評価値格納部２０２へのライン毎の評価結果の格納は、評価矩形領域の移動によって、ｘ座標が切り換えられたときに実行される。
【００６８】
ライン評価値格納部２０２に格納しておくライン毎の評価結果は、ｘ座標が同じで、ｙ座標が異なる複数の評価矩形領域で共通に利用できるものである。
【００６９】
図２（ｂ）を用いて説明したように、ｙ方向の拡張領域（ここでは上部側について言及する）の画素値は、ｘ座標が同じである、元々の参照画像の最も上のラインの画素値と同じ値になっている。そのため、圧縮対象画像中の探索対象矩形領域が固定されているならば、ｘ座標が同じで、ｙ座標が異なる複数の評価矩形領域では、ライン毎の評価結果単位では同じ値が生じる。例えば、図１２（ａ）に示す評価矩形領域の最も上のラインに対するライン毎の評価結果と、図１２（ｂ）に示す評価矩形領域の最も上のラインに対するライン毎の評価結果とは同じになる。ライン評価値格納部２０２には、ｘ座標が同じで、ｙ座標が異なる複数の評価矩形領域で共通に利用できる、このようなライン毎の評価結果が格納される。
【００７０】
ライン評価値格納部２０２の構造を図１３を用いて説明する。図１３（ａ）及び図１３（ｂ）はそれぞれ、圧縮対象画像の探索対象矩形領域と予測参照画像中の評価矩形領域である。それぞれの図の枡目は画素を表しており、その中のＡ００，Ｂ００等の記号は画素値を現している。図１３（ｃ）は評価値格納部２０２である。図１３（ｃ）に示すライン評価値格納部２０２は、配列となっており、それぞれの要素として、図１３（ａ）に示す探索対象矩形領域と図１３（ｂ）に示す評価矩形領域とから求めたライン毎の評価値が格納されている。図１３では、ライン毎の評価値が、差の絶対値和である場合を示している。ライン評価値格納部２０２の各要素にはインデックスが張られており、インデックスの値を指定することで、対応する配列要素の中身を取り出すことができる。
【００７１】
ここで、図１３（ｂ）に示す評価矩形領域は、拡張領域内に全てが入る領域とすることで、ｘ座標が同じで、ｙ座標が異なる複数の評価矩形領域で共通に利用できるライン毎の評価結果を、ライン評価値格納部２０２に格納できる。
【００７２】
ｘ座標が同じで、ｙ座標が異なる複数の評価矩形領域で共通に利用できるライン毎の評価結果をライン評価値格納部２０２に格納した後に、原時点で対象となる評価矩形領域の代表座標と、探索対象矩形領域の代表座標とが、図１１に示す構成に入力され始める。
【００７３】
評価ライン指示部２０１は、予測参照画像の評価矩形領域の代表座標（Ｘ０，Ｙ０）を受け取り、その評価矩形領域内をライン毎に評価できるように、順に評価すべきラインを規定する情報を出力するものである。
【００７４】
既評価判定部２０３は、評価ライン指示部２０１から与えられたライン情報が指示するラインが既に評価されているか否か、言い換えると、そのラインについての評価値が、ライン評価値格納部２０２に格納されているか否かを判定するものである。既評価判定部２０３は、そのラインが既に評価されている場合には、スイッチ２０３Ｓを介して、評価ライン指示部２０１からのライン情報を１ライン評価値読出部２０４に与え、そのラインが評価されていない場合には、スイッチ２０３Ｓを介して、評価ライン指示部２０１からのライン情報を１ライン類似度評価部２０５に与える。
【００７５】
１ライン評価値読出部２０４は、ライン評価値格納部２０２に格納されている評価値を既評価判定部２０３の判定結果に従って読出し、ライン評価値加算部２０７に与えるものである。
【００７６】
１ライン類似度評価部２０５は、評価ライン指示部２０１からのライン情報に従って、そのラインについての評価値（差の絶対値和）を計算してライン評価値加算部２０７に与えるものである。
【００７７】
１矩形領域評価値格納部２０６は、評価矩形領域内の評価値計算の途中結果を格納するものである。また、１矩形領域評価値格納部２０６は、現在対象となっている評価矩形領域の最終評価値（類似度）が得られた際には、その評価値を出力するものである。
【００７８】
ライン評価値加算部２０７は、１ライン評価値読出部２０４又は１ライン類似度評価部２０５から与えられた１ライン分の評価値と、１矩形領域評価値格納部２０６にある評価値の途中結果から、矩形領域内の評価値の計算の途中結果を更新するものである。
【００７９】
（Ｂ−２）第２の実施形態の動作
図１０（ａ）に示す圧縮対象画像の太線で囲まれた探索対象矩形領域に対して、予測参照画像中の複数の評価矩形領域の類似度を順に求める。ここでは、圧縮対象画像中の探索対象矩形領域の位置を固定して説明する。この固定した探索対象矩形領域に対して、上述したように、予測参照画像中の評価矩形領域を移動させて類似度を求める。
【００８０】
予測参照画像の探索をあるｘ座標に対して初めて行うとき、上述したように、ライン評価値格納部２０２に、ライン毎の評価値を設定する。
【００８１】
評価ライン指示部２０１は、類似度の計算対象の評価矩形領域の代表座標（Ｘ０，Ｙ０）を受け取る（図１０参照）。次に、評価ライン指示部２０１は、指定された評価矩形領域を（Ｘ０，Ｙ０）、（Ｘ０，Ｙ０＋１）、（Ｘ０，Ｙ０＋２）、（Ｘ０，Ｙ０＋３）から始まる水平方向４画素のライン単位に分割し、それぞれの座標を適当な順に既評価判定部２０３に与える。
【００８２】
既評価判定部２０３においては、与えられた座標から始まる水平方向４画素のラインと、それに対応する圧縮対象画像中のラインとの間の類似度を評価した結果が、ライン評価値格納部２０２に格納されているか否かを判定する。
【００８３】
ここで、ｙ座標がｙ≦０を満たす場合には、既に評価されていると判定する。既に類似度が評価されていた場合は、次のようになる。まず、この評価矩形領域内での相対座標のｙ座標値を、評価ライン指示部２０１から１ライン評価値読出部２０４に送り、１ライン評価値読出部２０４を通じて、ライン評価値格納部２０２から１ラインの評価値を読み出す。ライン評価値格納部２０２の構成は図１３（ｃ）に示すようになっているため、ライン評価値を読み出すためにはインデックスが必要であるが、例えば、このインデックスは評価ライン指示部２０１から送られた、この評価矩形領域内での相対座標のｙ座標値を適用できる。
【００８４】
一方、既評価判定部２０３で、まだ評価がされていないと判定された場合には、評価ライン指示部２０１から１ライン類似度評価部２０５に評価対象のラインの開始座標が与えられる。１ライン類似度評価部２０５は、評価対象ラインと圧縮対象画像中の探索対象矩形領域の対応するラインの類似度を評価する。類似度の評価は、画素毎の演算結果からライン単位の評価値を求める方法を適用でき、ライン毎の評価値から矩形領域の評価値を求められるものならば、どのようなものでも良い。例えば画素毎の差の絶対値和や差の２乗和を適用することができる。なお、ライン評価値格納部２０２の格納評価値と、同じ算出方法であることは当然である。
【００８５】
１ライン類似度評価部２０５で求められた評価矩形領域内のある１ライン分の評価値又は１ライン評価値読出部２０４によって読み出された１ライン分の評価値は、ライン評価値加算部２０７によって、１評価領域類似度格納部２０６に格納されている評価矩形領域内で既に評価された部分の類似度と加算され、加算結果が、１評価領域類似度格納部２０６に再格納される。
【００８６】
評価ライン指示部２０１が出力したライン情報（Ｘ０，Ｙ０）、（Ｘ０，Ｙ０＋１）、（Ｘ０，Ｙ０＋２）、（Ｘ０，Ｙ０＋３）に対応する処理結果が全て１矩形領域評価値格納部２０６に反映された時点で、探索対象矩形領域とその時点での評価類似度とな間の評価は終了し、１矩形領域分の評価値が出力される。
【００８７】
（Ｂ−３）第２の実施形態の効果
以上のように、第２の実施形態の画像照合装置２００によれば、拡張領域の画素値の性格を利用し、複数の評価矩形領域に共通するライン毎の評価値の算出は１回で済むようにしたので、全ての評価矩形領域の評価値（類似度）の算出のための処理量を従来より大幅に削減することができる。
【００８８】
以下では、このことを具体例で説明する。
【００８９】
類似度の評価が予測参照画像の境界（ｙ＝一定）を含んでいる場合を考える。図１０（ｂ）及び図１２（ａ）、（ｂ）、（ｃ）の斜線の部分が境界である。その境界上のある座標（ｘ，ｙ）と周辺画像（図１０（ｂ）及び図１２ではｙ＜０の部分）の座標（ｘ，ｙ＋ｎ）（但し、ｎ＜０）では画素値が同じである。
【００９０】
従って、図１２（ａ）に示す表か矩形領域内の座標（３，−３）からｘ方向に４画素で構成されそラインと、図１０（ａ）の（Ｍｘ，Ｍｙ）＝（０，０）からＭｘ方向に４画素で構成される画素の間の類似度の評価値は、図１２（ｂ）のように評価矩形領域を移動させた場合の（３，−１）からｘ方向に４画素から構成される評価矩形領域と図１０（ａ）の（Ｍｘ，Ｍｙ）＝（０，０）からＭｘ方向に４画素で構成される画素の間の類似度の評価値とは等しくなる。
【００９１】
一度、図１２（ａ）のようなｙ≦０の領域でライン毎の評価値を求め、その結果をライン評価値格納部２０２に格納しておくと、１予測参照画像内で矩形領域を移動させた場合、既に評価を行なった部分については、再度評価を行なう必要がなくなり、計算量が減少する。
【００９２】
例えば、類似度の評価に差の絶対値和を用いており、矩形領域が１６×１６画素の大きさだったとすると、矩形領域内の１ラインを評価する場合、１６回の減算と絶対値計算１５回の加算が必要であるが、再度評価を行なう必要がなくなるとこれらの演算が必要でなくなる。
【００９３】
（Ｂ−４）第２の実施形態を変形した実施形態
なお、第２の実施形態は、評価矩形領域をｘ方向を固定してｙ方向に移動させるスキャンニング方法を採用し、水平ライン毎の評価値を、ｘ座標が切り替わった際に予め算出して格納しておき、ｘ座標が同じ評価矩形領域の評価では、その格納されている水平ライン毎の評価値を利用して、評価値の算出時の処理量を削減するものを示したが、ｘ方向及びｙ方向を入れ換えても良い。
【００９４】
すなわち、評価矩形領域をｙ方向を固定してｘ方向に移動させるスキャンニング方法を採用し、垂直ライン毎の評価値を、ｙ座標が切り替わった際に予め算出して格納しておき、ｙ座標が同じ評価矩形領域の評価では、その格納されている垂直ライン毎の評価値を利用して、評価値の算出時の処理量を削減するようにしても良い。
【００９５】
また、ライン単位ではなく、拡張領域や原画像領域の境界を考慮し、画素単位の評価値を予め算出して格納しておき、拡張領域や原画像領域の境界を含む評価矩形領域の評価では、その格納されている垂直ライン毎の評価値を利用して、評価値の算出時の処理量を削減するようにしても良い。
【００９６】
第２の実施形態の説明では、記憶部からの圧縮対象画像や予測参照画像の画素値の取り出しには、言及しなかったが、第１の実施形態の方法を適用できることは勿論である。
【００９７】
（Ｃ）第３の実施形態
以下、本発明による画像照合装置の第３の実施形態を図面を参照しながら詳述する。なお、以下では、第３の実施形態の画像照合装置が、動きベクトル探索装置に適用されているとして説明を行う。
【００９８】
第３の実施形態の画像照合装置も、圧縮対象画像と予測参照画像との所定大きさの矩形領域による類似度判定での演算回数を減少させることを目的としてなされたものである。第３の実施形態の画像照合装置も、拡張領域を有する予測参照画像においては、その拡張領域での画素値は、ｙ方向又はｘ方向を固定して見ると、他方の方向が変化しても同一であるという性質を利用してなされたものである。
【００９９】
第３の実施形態の画像照合装置が、第２の実施形態の画像照合装置と最も異なる点は、複数の評価矩形領域に共通するライン毎の評価値も、ある評価矩形領域の評価値（類似度）の算出時に求めて、それを格納し、他の評価矩形領域の評価値（類似度）の算出時に利用できるようにした点である。
【０１００】
このような相違点との関係から、第３の実施形態の画像照合装置においては、予測参照画像中の評価矩形領域の変化順序（移動順序）を、例えば、図１４に示すように決めている。
【０１０１】
図１４に示す、太い直線で囲まれた矩形領域を類似度の評価矩形領域とする。この予測参照画像中の評価矩形領域は、圧縮対象画像中の探索対象矩形領域と類似度が高い領域を求めるため、図１４（ａ）、（ｂ）、…、（ｃ）、（ｄ）、…のように、原画像領域から拡張領域へ向けてｙ方向に平行移動する。図１４は、上部拡張領域側について示しているが、下部拡張領域側についても、原画像領域から拡張領域へ向けてｙ方向に平行移動する。
【０１０２】
なお、説明を簡単にするため、矩形領域の大きさを４×４画素とするが、特に大きさが変わっても動作が変わるものではない。
【０１０３】
（Ｃ−２）第３の実施形態の構成
図１５は、第３の実施形態の画像照合装置３００の要部構成を示すブロック図である。なお、図１５では、圧縮対象画像の格納部や、予測参照画像の格納部や、これら格納部に対するアクセス構成は省略しており、図１５は、類似度の探索面から、画像照合装置３００の構成を示している。また、図１５では、最大の類似度を与える評価矩形領域の決定構成も省略している。
【０１０４】
第３の実施形態の画像照合装置３００の図１５に示す構成部分には、圧縮対象画像中の探索対象矩形領域を代表する（Ｘ，Ｙ）（図１５では入力先を省略している）と、予測参照画像中のある評価矩形領域を代表する座標（Ｘ０，Ｙ０）とが入力され、探索対象矩形領域に対するその評価矩形領域の類似度が評価値として出力される。
【０１０５】
図１５において、第３の実施形態の画像照合装置３００は、評価ライン指示部３０１、境界判定部３０２、拡張領域評価値格納部３０３、拡張領域評価値読出部３０４、１ライン類似度評価部３０５、ライン評価値加算部３０６、１ライン類似度評価部３０７、１矩形領域類似度格納部３０８、ライン評価値加算部３０９及びライン評価値一時格納部３１０を有する。
【０１０６】
評価ライン指示部３０１は、評価矩形領域の代表座標（Ｘ０，Ｙ０）を受け取り、評価矩形領域内をライン（この第３の実施形態の説明においてもラインとは水平ラインを呼んでいる）毎に評価するように、順に評価すべきラインの開始座標を出力するものである。
【０１０７】
境界判定部３０２は、評価ライン指示部３０１から与えられた開始座標から、そのｙ座標（ライン）が、本来の予測参照画像（原画像領域）の上下の境界（最も上のライン又は最も下のライン）上にあるか、拡張領域にあるか、それとももともとの画像（原画像領域；上下の境界を除く）内にあるかを判定する部分である。
【０１０８】
図１４において、ｙ＝０の境界（上側の境界）を例にとると、境界判定部３０２は、評価ライン指示部３０１から与えられたｙ座標（ライン）がｙ＝０であるか（境界か；図１４でのハッチを付与したライン）、ｙ＜０であるか（拡張領域にあるか；図１４での灰色領域のライン）、ｙ＞０であるか（原画像領域にあるか；図１４での白色領域のライン）を判定する。
【０１０９】
そして、境界判定部３０２は、判定結果に応じて、スイッチ３０２Ｓを操作し、評価ライン指示部３０１から出力されたラインの開始座標を、拡張領域評価値読出部３０４、１ライン類似度評価部３０５又は１ライン類似度評価部３０７に入力させる。例えば、境界判定部３０２は、上側の境界近傍については、評価ライン指示部３０１から与えられたｙ座標（ライン）がｙ＝０であるときには、評価ライン指示部３０１から出力されたラインの開始座標を１ライン類似度評価部３０５に入力させ、評価ライン指示部３０１から与えられたｙ座標（ライン）がｙ＜０であるときには、評価ライン指示部３０１から出力されたラインの開始座標を拡張領域評価値読出部３０４に入力させ、評価ライン指示部３０１から与えられたｙ座標（ライン）がｙ＞０であるときには、評価ライン指示部３０１から出力されたラインの開始座標を１ライン類似度評価部３０７に入力させる。
【０１１０】
拡張領域評価値格納部３０３は、当該装置３００が評価途中に利用する記憶部である。この拡張領域評価値格納部３０３には、予測参照画像中の評価矩形領域の全て又は一部が拡張領域に位置しているときに、読み出される評価値が、ライン評価値加算器３０６によって格納される。
【０１１１】
拡張領域評価値読出部３０４は、境界判定部３０２による対象ラインの所属領域の判定によって、そのラインが拡張領域のラインであると判定されたときに、拡張領域評価値格納部３０３に格納されている拡張領域についての評価値を読み出し、ライン評価値加算部３０９に与えるものである。
【０１１２】
１ライン類似度評価部３０５は、境界判定部３０２による対象ラインの所属領域の判定によって、そのラインが境界ラインであると判定されたときに、そのラインについての類似度を評価し、その評価値を、ライン評価値加算部３０９及びライン評価値一時格納部３１０に与えるものである。
【０１１３】
ライン評価値一時格納部３１０は、１ライン類似度評価部３０５による評価値をバッファリングするものである。
【０１１４】
ライン評価値加算部３０６は、拡張領域評価値格納部３０３に格納されている値と、１ライン類似度評価部３０５がライン評価値一時格納部３１０に格納した評価値とを加算して拡張領域評価値格納部３０３に書き戻すものである。なお、このライン評価値加算部３０６の動作タイミングについては、後述する動作の説明で明らかにする。
【０１１５】
１ライン類似度評価部３０７は、境界判定部３０２による対象ラインの所属領域の判定によって、そのラインが原画像領域内（境界は除く）のラインであると判定されたときに、そのラインについての類似度を評価し、その評価値を、ライン評価値加算部３０９に与えるものである。
【０１１６】
１矩形領域類似度格納部３０８は、最終的には、現在対象となっている評価矩形領域全体の類似度を格納するものであり、処理の途中においては、途中での類似度（評価値）も格納する。
【０１１７】
ライン評価値加算部３０９は、１矩形領域類似度格納部３０８に格納されている値と、拡張領域評価値読出部３０４、１ライン類似度評価部３０５又は１ライン類似度評価部３０７から与えられたライン評価値とを加算して１矩形領域類似度格納部３０８に書き戻すものである。
【０１１８】
なお、１ライン類似度評価部３０５及び１ライン類似度評価部３０７には圧縮対象画像での探索対象矩形領域の情報も入力されているが、図１５では図示を省略している。
【０１１９】
（Ｃ−２）第３の実施形態の動作
この第３の実施形態の動作説明では、説明を簡単にするため、探索対象矩形領域及び評価矩形領域の大きさを４×４画素とする。また、予測参照画像の境界ｙ＝０付近での探索の場合を例に説明する。さらに、評価矩形領域を規定する座標情報としては、図１４の網模様の位置の座標を代表として使用する。
【０１２０】
評価対象とする予測参照画像内の矩形領域を指定するために、その評価矩形領域を代表する点の座標が入力される。この入力は、予測参照画像内の評価矩形領域の探索範囲内が探索し終るまで、各評価矩形領域毎に順に入力される。この入力の順番（評価矩形領域の変換順）は、ｘ座標を固定した状態で、ｙ≦０のラインを含んだ複数の評価矩形領域の評価を行なう際には、それら複数の評価矩形領域がｙ座標が負の方に変化するように変化させる。上述した図１４は、その入力座標の変化の様子を示しているものでもある。図１４では、ｙ≦０を含んだ領域を探索する場合であり、１画素分だけ評価矩形領域をｙ座標が負の方向に移動させるため、評価矩形領域は、（ａ）、（ｂ）、…、（ｃ）、（ｄ）…のように動いて行く。詳細な移動の様子は次のようになる。
【０１２１】
まず、図１４（ａ）のように、ｙ＞０のラインだけでなる評価矩形領域から始まるとする。評価矩形領域の類似度の評価が終る度に、ｙ座標が負の方向に、評価矩形領域を１画素分だけ平行移動させる。図１４（ａ）の状態から、評価矩形領域を１画素分だけ移動させると、図１４（ｂ）に示すように、ｙ＝０のラインを評価矩形領域内の最もｙ座標の小さい場所に含んだ状態になる。さらに、ｙ座標が負の方向に評価矩形領域の平行移動を３回だけ繰り返すと、図１４（ｄ）に示すように、ｙ＝０のラインを評価矩形領域内の最もｙ座標の大きい場所に含んだ状態となる。これ以上、ｙ座標の負の方向に平行移動しても予測参照画像内の評価矩形領域における画素値の値が変化しないため、このｘ座標でのｙ方向の探索はここで打ち切る。新たにｘ座標の値を適当なものに変更し、上述したような評価矩形領域の移動を行なう。
【０１２２】
次に、ある１個の評価矩形領域に対する動作を説明する。
【０１２３】
評価ライン指示部３０１は、評価矩形領域の代表座標入力によって指定された４×４画素の評価矩形領域を、ｘ方向に連続する４個の画素からなる４本のラインに分割する。そして、各ラインのｘ座標が最も小さな位置の座標を順に境界判定部３０２に与える。この順番は、ｙ＝０付近を評価している場合、ｙ座標の大きいラインからである。なお、ＱＣＩＦサイズの場合において、ｙ＝１４３付近を評価している場合、ｙ座標の小さいラインからである。
【０１２４】
境界判定部３０２は、入力されたラインの座標（ｙ座標）から、指定されたラインがｙ＞０の領域にあるか、ｙ＝０の領域（境界上）にあるか、ｙ＜０の領域（拡張領域）にあるかを判定する。
【０１２５】
以下では、境界判定部３０２が、（１）指定されたラインがｙ＞０の領域にある、（２）ｙ＝０の領域にある、（３）ｙ＜０の領域にある、と判定した３通りの場合の動作を順に説明する。
【０１２６】
（１）指定されたラインがｙ＞０の領域にある場合
ｙ＞０にあると判定した場合には、境界判定部３０２と連動しているスイッチ３０２Ｓによって評価ライン指示部３０１からの出力を１ライン類似度評価部３０７に送る。
【０１２７】
１ライン類似度評価部３０７では、評価ライン指示部３０１から入力された座標から始まるライン（４画素）と圧縮対象画像内の探索対象矩形領域の対応するラインとの類似度を評価する。ここで、ラインの類似度は、画素値毎の差の絶対値和や画素値毎の差の２乗和を適用できる。１ライン類似度評価部３０７は、この結果（ライン評価値）をライン評価値加算部３０９に送る。
【０１２８】
なお、ライン評価値加算部３０９による処理は、境界判定部３０２の判定結果に関係なく、各ラインについて共通である。
【０１２９】
１矩形領域類似度格納部３０８には、予測符号化画像内のこの矩形領域中の、既に評価を終えたラインの評価値の合計が入っている。ライン評価値加算部３０９は、１矩形領域類似度格納部３０８に格納されている値と、１ライン類似度評価部３０７から送られてくる１ライン分の評価値を加算して１矩形領域類似度格納部３０８に再格納する。
【０１３０】
１矩形領域類似度格納部３０８は矩形領域内の全てのラインの評価値が合計されたときに、評価値を出力端より出力する。１矩形領域類似度格納部３０８から評価値が出力されると、評価ライン指示部３０１には新たな評価矩形領域が指定される。
【０１３１】
（２）指定されたラインがｙ＝０の領域にある場合
境界判定部３０２によって指定されたラインがｙ＝０の領域にあると判定した場合には、境界判定部３０２と連動しているスイッチ３０２Ｓによって、評価ライン指示部３０１からの出力が１ライン類似度評価部３０５に与えられる。
【０１３２】
１ライン類似度評価部３０５では、評価ライン指示部３０１から入力された座標から始まるライン（４画素）と圧縮対象画像内の探索対象矩形領域の対応するラインとの類似度を評価する。この評価値は、ライン評価値一時格納部３１０に与えられると共に、ライン評価値加算部３０９にも与えられる。
【０１３３】
ライン評価値一時格納部３１０は、評価矩形領域座標入力から新たな評価矩形領域が入力されたとき（つまり予測参照画像中の評価矩形領域がｙ方向に平行移動したとき）に、格納されている評価値をライン評価値加算部３０６に与える。すなわち、ライン評価値一時格納部３１０及びライン評価値加算部３０６は、今回の評価対象の評価矩形領域の類似度評価のために設けられているものではなく、むしろ、今後移動された評価矩形領域に対する類似度評価のために設けられている。
【０１３４】
ライン評価値加算部３０６は、ライン評価値一時格納部３１０からのライン評価値と、拡張領域評価値格納部３０３に格納されているそれまでに計算された各ラインの評価値の合計とを加算し、その結果を拡張領域評価値格納部３０３に書き戻す。
【０１３５】
１ライン類似度評価部３０５からライン評価値が与えられたライン評価値加算部３０９の処理は、上述した（１）の場合と同様である。
【０１３６】
（３）指定されたラインがｙ＜０の領域にある場合
境界判定部３０２によって、指定されたラインがｙ＜０の領域にあると判定された場合には、境界判定部３０２と連動しているスイッチ３０２Ｓによって、評価ライン指示部３０１からの出力が拡張領域評価値読出部３０４に与えられ、拡張領域評価値読出部３０４によって拡張領域評価値格納部３０３に格納されている評価値が読み出され、ライン評価値加算部３０９に与えられる。この読出時には、拡張領域評価値格納部３０３には、ｙ＜０の領域に属する全てのラインの評価値の合計が既に格納されている。
【０１３７】
なお、現在の評価矩形領域についての指定ラインの切換により、指定ラインがｙ＜０のラインに初めてなったときに、上述したように、拡張領域評価値読出部３０４は拡張領域評価値格納部３０３の評価値を読み出すが、この読出しによる評価値をライン評価値加算部３０９が加算処理することにより、現在対象となっている評価矩形領域に対する評価は終了する。すなわち、評価ライン指示部３０１から出力されていないｙ＜０のラインがあっても、拡張領域評価値格納部３０３に格納されている評価値には、そのラインの評価値も含まれているので終了する。
【０１３８】
拡張領域評価値読出部３０４から評価値が与えられたライン評価値加算部３０９の処理は、上述した（１）の場合と同様である。
【０１３９】
以上、対象ラインのｙ座標での位置毎によって処理が異なることを説明したが、以下では、このようなライン毎の処理手順が、予測参照画像中の評価矩形領域の位置によって、どのように現れるかを説明する。
【０１４０】
図１４（ａ）は、予測参照画像の評価矩形領域全てが、ｙ＞０の原画像領域に含まれている場合を示している。なお、各評価矩形領域について、評価を始める前には、１矩形領域類似度格納部３０８の値は０に初期化されている。
【０１４１】
評価ライン指示部３０１はまず、ｙ＝４の位置のラインを送り出す。境界判定部３０２に連動しているスイッチ３０２Ｓによって、この情報は１ライン類似度評価部３０７に与えられ、このｙ＝４のラインの評価値が得られる。そして、ライン評価値加算部３０９によって１矩形領域類似度格納部３０８に格納される。
【０１４２】
次に、評価ライン指示部３０１はｙ＝３の位置のラインを送り出し、１ライン類似度評価部３０７及びライン評価値加算部３０９で同様に処理され、この時点では、ｙ＝４及びｙ＝３のライン評価値の合計値が１矩形領域類似度格納部３０８に格納される。
【０１４３】
ｙ＝２、ｙ＝１のラインについても同様に処理される。ｙ＝１のラインの処理が終了したときには、ｙ＝４、ｙ＝３、ｙ＝２及びｙ＝１のライン評価値の合計値、すなわち、現在の評価矩形領域に対する評価値（類似度）が１矩形領域類似度格納部３０８に格納され、この評価矩形領域に対する評価が完了する。
【０１４４】
図１６に、予測参照画像での評価矩形領域が全てｙ＞０の領域に含まれている場合（図１４（ａ）の位置）での類似度の評価の様子を模式的に示す。この図１６は、ｙ＝１のラインを、予測参照画像での評価矩形領域と圧縮対象画像の探索対象矩形領域とから切出し、１ライン分の類似度の評価値を求める様子を示している。
【０１４５】
次に、予測参照画像中の評価矩形領域が、ｙ＝０のラインは含んでいるが、ｙ＜０のラインは含んでいない場合の動作を、図１４（ｂ）をも参照しながら説明する。
【０１４６】
図１４（ｂ）に示す評価矩形領域を処理する場合、評価ライン指示部３０１はまず、ｙ＝３の位置のラインを送り出し、次に、ｙ＝２の位置のラインを送り出し、さらに、ｙ＝１の位置のラインを送り出す。
【０１４７】
これらラインは、全てｙ＞０のラインであるので、上述したように、１ライン類似度評価部３０７及びライン評価値加算部３０９が機能し、各ライン毎の評価値の算出及び累積処理が実行され、ｙ＝１の位置のラインに対する処理が終了した時点では、ｙ＝３、ｙ＝２及びｙ＝１のライン評価値の合計値が１矩形領域類似度格納部３０８に格納される。
【０１４８】
次に、ｙ＝０のラインを評価ライン指示部３０１が送り出すと、境界判定部３０２によって、そのライン情報は１ライン類似度評価部３０５に与えられ、１ライン類似度評価部３０５によってｙ＝０のラインの評価値が得られ、このラインの評価値は、ライン評価値一時格納部３１０及びライン評価値加算部３０９に与えられる。
【０１４９】
ライン評価値加算部３０９では、１矩形領域類似度格納部３０８に格納されている評価値（ｙ＝３〜ｙ＝１のライン評価値の合計値）と、与えられたｙ＝０のラインの評価値とを加算し、１矩形領域類似度格納部３０８に再格納する。この時点で、予測参照画像中の今回の評価矩形領域の類似度の評価が完了するので、１矩形領域類似度格納部３０８に格納された値を出力する。
【０１５０】
ｙ＝０のラインの評価値が与えられたライン評価値一時格納部３１０は、この評価値を格納する。ライン評価値加算部３０６は、ｙ方向に１画素だけずらした次の評価矩形領域の処理の開始前に、そのとき拡張領域評価値格納部３０３に格納されている値（今回の時点では初期値０）と、ライン評価値一時格納部３１０に格納されている評価値（ｙ＝０のラインの評価値）とを加算して拡張領域評価値格納部３０３に書き戻す。
【０１５１】
ここで、図１４（ｂ）に示す評価矩形領域のｙ＝０のラインの評価値は、図１４（ｃ）に示す評価矩形領域のｙ＝−２のラインの評価値や、図１４（ｄ）に示す評価矩形領域のｙ＝−３のラインの評価値と同一である。
【０１５２】
以上のような動作を図１７に模式的に示している。図１７の太い矢印は、予測参照画像の評価矩形領域内のｙ＝０のラインの処理である。それぞれのラインの値から画素値を取り出し、ライン評価値を求めている。
【０１５３】
なお、この後、予測参照画像中の矩形領域の位置をｙ座標の負の方向に１画素分だけ平行移動し、新たな評価矩形領域（図１４（ｂ）と図１４（ｃ）との中間位置の評価矩形領域）に対する評価を開始するが、この評価矩形領域に対するｙ＝−１のラインの処理時には、拡張領域評価値格納部３０３のデータ（初期値は０）が利用される（以下の説明参照）。
【０１５４】
次に、ｙ＜０のラインを含む評価矩形領域に対する評価動作を、図１４（ｃ）及び図１８を参照しながら詳述する。
【０１５５】
図１４（ｃ）に示す表か矩形領域を処理する場合には、評価ライン指示部３０１はまず、ｙ＝１の位置のラインを送り出す。境界判定部３０２に連動しているスイッチ３０２Ｓによって、このライン情報は１ライン類似度評価部３０７に与えられ、かくして、ｙ＝１のラインの評価値が得られ、ライン評価値加算部３０９によって、ｙ＝１のライン評価値が１矩形領域類似度格納部３０８に格納される。この際の処理は、図１８の細い矢印の流れに対応している。
【０１５６】
次に、評価ライン指示部３０１はｙ＝０の位置のラインを送り出す。図１８の太い矢印の流れがこの処理に対応している。
【０１５７】
ｙ＝０の位置のライン情報は、境界判定部３０２の判定によって、１ライン類似度評価部３０５に与えられ、１ライン類似度評価部３０５によって、このラインについての評価値が得られ、その評価値は、ライン評価値一時格納部３１０及びライン評価値加算部３０９に与えられる。
【０１５８】
ライン評価値加算部３０９では、１矩形領域類似度格納部３０８に格納されている評価値（ｙ＝１のラインの評価値）と、与えられたｙ＝０のラインの評価値とを加算し、１矩形領域類似度格納部３０８に再格納する。
【０１５９】
次に、ｙ＜０である拡張領域のｙ＝−１のラインが評価ライン指示部３０１から出力されると、そのライン情報は、境界判定部３０２によるスイッチ３０２Ｓの操作によって、拡張領域評価値読出部３０４に与えられる。
【０１６０】
拡張領域評価値読出部３０４は、与えられたラインの位置とは関係なく、ライン情報が与えられたことに基づいて、拡張領域評価値格納部３０３から評価値を読み出し、ライン評価値加算部３０９に与える。
【０１６１】
このとき、拡張領域評価値格納部３０３に格納されている評価値は、今回の評価矩形領域におけるｙ＝−１及びｙ＝−２のラインの評価値の合計値になっている。
【０１６２】
ライン評価値加算部３０９は、拡張領域評価値格納部３０３から評価値（ｙ＝−１及びｙ＝−２のラインの評価値の合計値）が与えられると、その評価値と、１矩形領域類似度格納部３０８に格納されている既に計算途中の類似度の評価値（ｙ＝１及びｙ＝０のラインの評価値の合計値）とを加算し、１矩形領域類似度格納部３０８に再格納する。
【０１６３】
境界判定部３０２が拡張領域評価値読出部３０４の方にスイッチ３０２Ｓを切りかえると、今回の評価矩形領域の処理は完了したことになり、１矩形領域類似度格納部３０８に格納されている評価値が出力される。すなわち、評価ライン指示部３０１は、今回の評価矩形領域についてのｙ＝−２のライン情報を出力することはない。
【０１６４】
一方、上述したように、ｙ＝０のラインの評価値が与えられたライン評価値一時格納部３１０は、この評価値を格納する。ライン評価値加算部３０６は、ｙ方向に１画素だけずらした次の評価矩形領域の処理の開始前に、そのとき拡張領域評価値格納部３０３に格納されている値（今回の評価矩形領域に対する表現を使えば、ｙ＝−１及びｙ＝−２のラインの評価値の合計値）と、ライン評価値一時格納部３１０に格納されている評価値（今回の評価矩形領域に対するｙ＝０のラインの評価値）とを加算して拡張領域評価値格納部３０３に書き戻す。
【０１６５】
この書き戻された評価値は、ｙ方向に１画素分だけずらした次の評価矩形領域（図１４（ｄ））から見れば、ｙ＝−１〜ｙ＝−３のラインの評価値の合計値となっている。
【０１６６】
（Ｃ−３）第３の実施形態の効果
以上のように、第３の実施形態の画像照合装置３００によれば、拡張領域の画素値の性格を利用し、複数の評価矩形領域に共通するライン毎の評価値の算出は１回で済むようにしたので、全ての評価矩形領域の評価値（類似度）の算出のための処理量を従来より大幅に削減することができる。
【０１６７】
また、第２の実施形態に比較しても処理量又は処理時間を削減することができる。すなわち、第２の実施形態の場合、各評価矩形領域に対し、４個のラインの評価値を常に加算しなければならなかったが、この第３の実施形態によれば、拡張領域を含む評価矩形領域については、それまでの拡張領域に属する全てのラインの評価値が求まっているため、それを総合評価値の算出に利用でき、処理量を削減できる。
【０１６８】
（Ｃ−４）第３の実施形態を変形した実施形態
なお、第３の実施形態は、評価矩形領域をｘ方向を固定してｙ方向に移動させるスキャンニング方法を採用し、拡張領域における水平ライン毎の評価値の共通性を利用したものであったが、ｘ方向及びｙ方向を入れ換えても良い。すなわち、評価矩形領域をｙ方向を固定してｘ方向に移動させるスキャンニング方法を採用し、拡張領域における垂直ライン毎の評価値の共通性を利用するようにしても良い。
【０１６９】
また、ライン単位ではなく、拡張領域や原画像領域の境界を考慮し、拡張領域及び境界での画素単位の評価値の共通性を利用して、評価値の算出時の処理量を削減するようにしても良い。
【０１７０】
第３の実施形態の説明では、記憶部からの圧縮対象画像や予測参照画像の画素値の取り出しには、言及しなかったが、第１の実施形態の方法を適用できることは勿論である。
【０１７１】
（Ｄ）他の実施形態
上記各実施形態では、動きベクトルの検出を意図してなされたものであるが、複数の画像間で同一画像部分の探索を必要とする処理を含む装置であれば、本発明を適用することができる。例えば、動画像領域を静止画領域から弁別して切り出す装置でも、画像間の比較（照合）を行うものがあり、この場合にも本発明を適用することができる。
【０１７２】
【発明の効果】
本発明の画像照合装置によれば、照合のための処理量を従来より削減することができる。
【図面の簡単な説明】
【図１】第１の実施形態に係る画像読出装置の構成を示すブロック図である。
【図２】参照画像の拡張方法の説明図である。
【図３】従来の動きベクトルの探索方法の説明図である。
【図４】従来の課題の説明図（１）である。
【図５】従来の課題の説明図（２）である。
【図６】従来の課題の説明図（２）である。
【図７】第１の実施形態の予測参照画像格納部の構成を示す説明図である。
【図８】第１の実施形態のライン番号格納部の構成を示す説明図である。
【図９】第１の実施形態の動作の説明に供する図面である。
【図１０】第２の実施形態の照合対象の説明図である。
【図１１】第２の実施形態に係る画像照合装置の構成を示すブロック図である。
【図１２】第２の実施形態の評価矩形領域の移動方法の説明図である。
【図１３】第２の実施形態のライン毎の評価値算出方法の説明図である。
【図１４】第３の実施形態の評価矩形領域の移動方法の説明図である。
【図１５】第３の実施形態に係る画像照合装置の構成を示すブロック図である。
【図１６】第３の実施形態のライン毎の評価値算出方法の説明図である。
【図１７】第３の実施形態のライン評価値一時格納部に格納する情報の説明図（１）である。
【図１８】第３の実施形態のライン評価値一時格納部に格納する情報の説明図（２）である。
【符号の説明】
１００…画像読出装置、１０１…ｙ座標置換部、１０２…ライン番号格納部、１０３…予測参照画像格納部、１０４…画素値読出部、２００…画像照合装置、２０１…評価ライン指示部、２０２…ライン評価値格納部、２０３…既評価判定部、２０４…１ライン評価値読出部、２０５…１ライン類似度評価部、２０６…１矩形領域評価値格納部、２０７…評価値加算部、３００…画像照合装置、３０１…評価ライン指示部、３０２…境界判定部、３０３…拡張領域評価値格納部、３０４…拡張領域評価値読出部、３０５…１ライン類似度評価部、３０６…ライン評価値加算部、３０７…１ライン類似度評価部、３０８…１矩形領域類似度格納部、３０９…ライン評価値加算部、３１０…ライン評価値一時格納部。
【図１】
0003865541.tif 000003
【図２】
0003865541.tif 000004
【図３】
0003865541.tif 000005
【図４】
0003865541.tif 000006
【図５】
0003865541.tif 000007
【図６】
0003865541.tif 000008
【図７】
0003865541.tif 000009
【図８】
0003865541.tif 000010
【図９】
0003865541.tif 000011
【図１０】
0003865541.tif 000012
【図１１】
0003865541.tif 000013
【図１２】
0003865541.tif 000014
【図１３】
0003865541.tif 000015
【図１４】
0003865541.tif 000016
【図１５】
0003865541.tif 000017
【図１６】
0003865541.tif 000018
【図１７】
0003865541.tif 000019
【図１８】
0003865541.tif 000020