(57)【要約】画像中のある特定のピクセル（１００）の近傍に位置するエッジの向きを推定する方法が開示される。該方法は、候補エッジ方向の集合を生成し、前記候補エッジ方向のそれぞれについて対応する試験ピクセル群（１０４、１０６）の対について前記対応する試験ピクセル群の対の２つの試験群（１０４、１０６）のピクセル値の間の差に基づいて一致誤差を計算することによって前記候補エッジ方向を評価し、前記候補エッジ方向の集合からそれぞれの一致誤差に基づいて前記候補エッジ方向の第１のものを選択し、前記候補エッジ方向の該第１のものを目標ピクセルブロック（１０２）に割り当てる、ことを有する。この方法の利点は、必要とされる計算が比較的少ないことである。これは前記推定エッジ方向が目標ピクセルブロック（１０２）に対して割り当てられることによって実現されている。
2006529039.tif 000002
【特許請求の範囲】
【請求項１】
画像中で、該画像のある特定のピクセルの近傍に位置するエッジの方向を推定する方法であって、
・前記特定ピクセルの近傍に位置する各試験ピクセル群のピクセルの値を比較し、
・前記特定ピクセルに、ピクセルの前記値の比較に基づく推定エッジ方向を割り当てることを有しており、
前記推定エッジ方向が前記特定ピクセルを含んでいる二次元目標ピクセルブロックに対して割り当てられることを特徴とする方法。
【請求項２】
請求項１記載の方法であって、当該画像中の追加的な二次元目標ピクセルブロックに該追加的な目標ピクセルブロックについての同様のエッジ方向推定に基づいて追加的なエッジ方向が割り当てられること、ならびに、最終的なエッジ方向が前記二次元目標ピクセルブロックのあるサブブロックについて、前記二次元目標ピクセルブロックに割り当てられている推定エッジ方向および前記追加的な目標ピクセルブロックのうちの第１のものに割り当てられている前記追加的なエッジ方向のうちの第１のものに基づいて計算されることを特徴とする方法。
【請求項３】
請求項１または２記載の方法であって、
・候補エッジ方向の集合を生成し、
・前記候補エッジ方向のそれぞれについて一致誤差を計算することによって前記候補エッジ方向を評価し、該一致誤差の第１のものは各試験ピクセル群のピクセル値の間の差に基づいており、
・前記候補エッジ方向の集合からそれぞれの一致誤差に基づいて前記候補エッジ方向の第１のものを選択し、前記候補エッジ方向の該第１のものを前記二次元目標ピクセルブロックに割り当てる、
ことを有することを特徴とする方法。
【請求項４】
請求項３記載の方法であって、前記候補エッジ方向の集合が、さらなるエッジ方向の集合から候補エッジ方向を選択することによって生成され、該さらなるエッジ方向の集合が以前のエッジ方向推定ののちに当該画像の前記さらなる目標ピクセルブロックに割り当てられたさらなるエッジ方向からなることを特徴とする方法。
【請求項５】
請求項４記載の方法であって、前記さらなるエッジ方向の集合からの前記候補エッジ方向の第２のものの選択が、
・前記候補エッジ方向の該第２のものと、
・前記候補エッジ方向の該第２のものが割り当てられた前記さらなる目標ピクセルブロックの第２のものの、当該特定ピクセルに対する位置、
とに基づいて行われることを特徴とする方法。
【請求項６】
請求項３記載の方法であって、前記候補エッジ方向の集合が、さらなるエッジ方向の集合から候補エッジ方向を選択することによって生成され、該さらなるエッジ方向の集合がある以前のエッジ方向推定ののちにある別の画像の別の目標ピクセルブロックに割り当てられたさらなるエッジ方向からなり、当該画像と前記別の画像とはともに一つのビデオ画像シーケンスに属するものであることを特徴とする方法。
【請求項７】
請求項３記載の方法であって、前記一致誤差が前記２つの試験ピクセル群のそれぞれのピクセルの間の差の絶対値の合計に基づいていることを特徴とする方法。
【請求項８】
前記試験ピクセル群がそれぞれ長方形のピクセルブロックであることを特徴とする、請求項１記載の方法。
【請求項９】
請求項３記載の方法であって、前記試験ピクセル群がそれぞれ台形のピクセルブロックであり、その実際の形は考察している候補エッジ方向に依存することを特徴とする方法。
【請求項１０】
請求項１または２記載の方法であって、
・当該特定ピクセルに関してある第１の方向に反対向きのオフセットをもつ２つの試験ピクセルブロックのピクセル値の間の差の第１の和を計算し、
・当該特定ピクセルに関してある第２の方向に反対向きのオフセットをもつ２つの試験ピクセルブロックのピクセル値の間の差の第２の和を計算し、
・前記差の第１の和と前記差の第２の和との商を計算することによってエッジ方向を決定する、
ことを有することを特徴とする方法。
【請求項１１】
画像中で、該画像のある特定のピクセルの近傍に位置するエッジの方向を推定するエッジ方向推定ユニットであって、
・前記特定ピクセルの近傍に位置する各試験ピクセル群のピクセルの値を比較する計算手段と、
・前記特定ピクセルに、ピクセルの前記値の比較に基づく推定エッジ方向を割り当てる割り当て手段とを有しており、
前記割り当て手段が前記推定エッジ方向を当該特定ピクセルを含んでいる二次元目標ピクセルブロックに対して割り当てるよう構成されていることを特徴とするユニット。
【請求項１２】
・入力画像のシーケンスに対応する信号を受信する受信手段と、
・前記入力画像のシーケンスに基づいて出力画像のシーケンスを計算する、請求項１１記載のエッジ方向推定ユニットによって制御される画像処理ユニット、
とを有することを特徴とする画像処理装置。
【請求項１３】
前記画像処理ユニットが請求項１１記載のエッジ方向推定ユニットによって制御される補間手段を有するインターレース除去ユニットであることを特徴とする、請求項１２記載の画像処理装置。
【請求項１４】
さらに前記出力画像を表示するための表示装置を有することを特徴とする、請求項１２記載の画像処理装置。
【請求項１５】
テレビであることを特徴とする、請求項１４記載の画像処理装置。
【請求項１６】
画像中で、該画像のある特定のピクセルの近傍に位置するエッジの方向を推定するための命令を有し、処理手段およびメモリを有するコンピュータ設備によって読み込まれるべきコンピュータプログラムであって、読み込まれたのち、前記処理手段に、
・前記特定ピクセルの近傍に位置する各試験ピクセル群のピクセルの値を比較し、
・前記特定ピクセルに、ピクセルの前記値の比較に基づく推定エッジ方向を割り当てる、
ことを実行する能力を与えるものであって、前記推定エッジ方向が当該特定ピクセルを含んでいる二次元目標ピクセルブロックに対して割り当てられることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中で、該画像のある特定のピクセルの近傍に位置するエッジの方向を推定する方法に関するものであり、該方法は、
・前記特定ピクセルの近傍に位置する各試験ピクセル群のピクセルの値を比較し、
・前記特定ピクセルに、ピクセルの前記値の比較に基づく推定エッジ方向を割り当てる、ことを有する。
【０００２】
本発明はさらに、画像中で、該画像のある特定のピクセルの近傍に位置するエッジの方向を推定するエッジ方向推定ユニットに関するものであり、該エッジ方向推定ユニットは、
・前記特定ピクセルの近傍に位置する各試験ピクセル群のピクセルの値を比較する計算手段と、
・前記特定ピクセルに、ピクセルの前記値の比較に基づく推定エッジ方向を割り当てる割り当て手段とを有する。
【０００３】
本発明はさらに、
・入力画像のシーケンスに対応する信号を受信する受信手段と、
・前記入力画像のシーケンスに基づいて出力画像のシーケンスを計算する、前記したエッジ方向推定ユニットによって制御される画像処理ユニットとを有する、画像処理装置にも関する。
【０００４】
本発明はさらに、画像中で、該画像のある特定のピクセルの近傍に位置するエッジの方向を推定するための命令を有し、処理手段およびメモリを有するコンピュータ設備によって読み込まれるべきコンピュータプログラムプロダクトにも関する。該コンピュータプログラムプロダクトは、読み込まれたのち、前記処理手段に、
・前記特定ピクセルの近傍に位置する各試験ピクセル群のピクセルの値を比較し、
・前記特定ピクセルに、ピクセルの前記値の比較に基づく推定エッジ方向を割り当てる、
ことを実行する能力を与えるものである。
【背景技術】
【０００５】
冒頭で述べたたぐいの画像処理装置の一つの実施形態は米国特許US5,019,903から知られている。この特許明細書は、デジタルビデオ信号の行の間を空間的に補間して補間された行を生成する装置を開示している。その装置は、当該信号の標本値の間を水平方向に補間して元来の標本値とそれらの間に位置する補間された標本値とからなるスーパーサンプリング信号を生成するよう構成されたスーパーサンプラーを有している。そのスーパーサンプリング信号の各標本値について、ブロック一致回路がそれぞれ、Ｎ×Ｍ標本値の２つのブロックの間の一致の度合いを決定する（Ｎは行数、Ｍは標本値の数）。前記２つのブロックは垂直方向には補間すべき行に関して反対向きにオフセットされており、水平方向には所定の標本値の位置に関して反対向きにオフセットされている。各ブロック一致回路はそれぞれの異なる水平オフセットについて一致誤差を生成する。この一致誤差に反応して、補間すべき行の各標本値について、選択手段が、前記異なるオフセットに対応する勾配ベクトルの組から前記ブロック間の最良一致を与えるオフセットに対応する勾配ベクトルを選択する。この勾配ベクトルがエッジの方向に対応すると想定されている。方向可変の空間補間手段が当該ビデオ信号を空間的に補間する。その補間方向は、それが生成する標本値ごとに、その生成される標本値に対応する所定の標本値の位置について選択された前記勾配ベクトルに従って制御される。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
前記の既知の画像処理装置の不都合な点は、当該ビデオ信号によって表現されている画像中のエッジの方向を決定するために比較的多数の計算が必要とされることである。各標本値について一致誤差を、評価すべき異なる勾配ベクトルに対応してあらゆるオフセットについて計算しなければならないのである。
【課題を解決するための手段】
【０００７】
必要とされる計算が比較的少数ですむような冒頭において述べたたぐいの方法を提供することが本発明の目的の一つである。
【０００８】
本発明のこの目的は、前記特定ピクセルを含んでいる二次元目標ピクセルブロックに推定エッジ方向が割り当てられることで達成される。個々のピクセルそれぞれについての試験ピクセルブロックの比較に基づいて画像中の個々のピクセルそれぞれについてエッジ方向を計算する代わりに、二次元目標ピクセルブロックに推定エッジ方向が割り当てられる。典型的な目標ブロックは８×８ピクセルからなり、計算負荷の６４倍もの低減につながる。既知の技術では、エッジ方向の計算および割り当ては個々のピクセルに対して行われていた。本出願人は、意外にも、ビデオ画像における構造の向き、すなわちエッジ方向に関係するデータによって制御される多くのビデオ処理アプリケーションについては、推定エッジ方向を二次元目標ピクセルブロックに割り当てることで満足のいく結果が得られることを発見した。これが意外というのは、画像の細部、すなわちエッジ方向の多くはピクセルの目標ブロックよりも小さいからである。
【０００９】
しかし、好ましくは、二次元目標ピクセルブロックへのエッジ方向の割り当てに続いてブロック侵食（block  erosion）として知られる後処理ステップが設けられる。ブロック侵食は、たとえば米国特許明細書US5,148,269において開示されている。そこで本発明に基づく方法の実施形態が特徴とするのは、当該画像中の追加的な二次元目標ピクセルブロックに該追加的な目標ピクセルブロックについての同様のエッジ方向推定に基づいて追加的なエッジ方向が割り当てられること、ならびに、最終的なエッジ方向が前記二次元目標ピクセルブロックのあるサブブロックについて、前記二次元目標ピクセルブロックに割り当てられている推定エッジ方向および前記追加的な目標ピクセルブロックのうちの第１のものに割り当てられている前記追加的なエッジ方向のうちの第１のものに基づいて計算されることである。好ましくは、前記追加的な目標ピクセルブロックの前記最初のものは、前記二次元目標ピクセルブロックの前記サブブロックに隣接する位置にある。本発明に基づくこの実施形態の利点は、追加的な計算は比較的少ないながら、エッジ方向が当該画像のより小さなサブブロックについて、あるいは個々のピクセルについてでさえ計算されるということである。その追加的な計算は主として少数の標本値の比較演算であり、たとえば単一の目標ブロックを形成する４つの各サブブロックについての４つのエッジ方向を決定するための４×２回の比較演算である。こうしたより小さいピクセルサブブロックについては、各試験ブロックのピクセルの比較的高価な比較は必要ないことを注意しておく。
【００１０】
本発明に基づく方法のある実施形態は、
・候補エッジ方向の集合を生成し、
・前記候補エッジ方向のそれぞれについて一致誤差を計算することによって前記候補エッジ方向を評価し、該一致誤差の第１のものは各試験ピクセル群のピクセル値の間の差に基づいており、
・前記候補エッジ方向の集合からそれぞれの一致誤差に基づいて前記候補エッジ方向の第１のものを選択し、前記候補エッジ方向の該第１のものを前記二次元目標ピクセルブロックに割り当てる、
ことを有する。
【００１１】
好ましくは、前記候補エッジ方向の集合は、さらなるエッジ方向の集合から候補エッジ方向を選択することによって生成され、該さらなるエッジ方向の集合は以前のエッジ方向推定ののちに当該画像の前記さらなる目標ピクセルブロックに割り当てられたさらなるエッジ方向からなる。本発明に基づくこの実施形態では、特定のピクセルの空間的な環境中において以前に推定されたエッジ方向が再利用され、現在の目標ピクセルブロックの近傍におけるさらなる目標ピクセルブロックに割り当てられる。画像中のエッジは複数の目標ブロックと重なる、すなわち複数の目標ブロックに広がると想定しているのである。もしある特定のエッジ方向が近くの目標ピクセルブロックに割り当てられていれば、この特定のエッジ方向が考察中の目標ピクセルブロックについてのよい候補エッジ方向になるというのである。よって、この実施形態の利点は、候補エッジ方向の集合が限定されており、その結果として計算の数が少なくなるという点である。もう一つの利点は、推定エッジ方向の一貫性が改善されるという点である。
【００１２】
好ましくは、前記さらなるエッジ方向の集合からの前記候補エッジ方向の第２のものの選択が、
・前記候補エッジ方向の該第２のものと、
・前記候補エッジ方向の該第２のものが割り当てられた前記さらなる目標ピクセルブロックの第２のものの当該特定ピクセルに対する位置、
とに基づいて行われる。これは、もし前記候補エッジ方向の第２のものが前記さらなる目標ピクセルブロックの第２のものの中心ピクセルから当該特定ピクセルへの線分と実質一致すれば、前記候補エッジ方向の該第２のものが選択されるということを意味する。逆もまた真である。もし前記候補エッジ方向の第３のものが前記候補エッジ方向の該第３のものが割り当てられたさらなる中心ピクセルから当該特定ピクセルへの線分に実質等しくなければ、前記候補エッジ方向の該第３のものは選択されない。換言すれば、候補エッジ方向の集合は主として現在の目標ピクセルブロックについて適切である確率が比較的高い候補エッジ方向からなっているのである。
【００１３】
あるいはまた、前記候補エッジ方向の集合は、さらなるエッジ方向の集合から候補エッジ方向を選択することによって生成され、該さらなるエッジ方向の集合はある以前のエッジ方向推定ののちにある別の画像の別の目標ピクセルブロックに割り当てられたさらなるエッジ方向からなる。ここで、当該画像と前記別の画像とはともに一つのビデオ画像シーケンスに属するものである。本発明に基づくこの実施形態では、現在の目標ピクセルブロックの時間的な環境中において推定されているエッジ方向が再利用され、時間的に近隣の目標ピクセルブロックに割り当てられる。ビデオ画像のシーケンスの一連の画像は互いに比較的よく一致すると想定しているのである。もしある特定のエッジ方向が以前の画像における対応する目標ピクセルブロックに割り当てられていれば、この特定のエッジ方向が考察中の目標ピクセルブロックについてのよい候補エッジ方向になるというのである。よって、この実施形態の利点は、候補エッジ方向の集合が限定されており、その結果として計算の数が少なくなるという点である。もう一つの利点は、推定エッジ方向の一貫性が改善されるという点である。
【００１４】
本発明に基づく、複数の候補エッジ方向を評価することに基づく方法のある実施形態では、前記一致誤差は前記２つの試験ピクセル群のそれぞれのピクセルの間の差の絶対値の合計に基づいている。この一致誤差は、画像の諸部分の間の一致を確立するための比較的良好な尺度であり、大がかりな計算は必要としない。任意的に、前記２つの試験ピクセル群は部分的に重なり合っていてもよい。そのほかにサブサンプリングを適用してもよい。
【００１５】
本発明に基づく方法のある実施形態では、前記試験ピクセル群はそれぞれ長方形のピクセルブロックである。典型的な試験ピクセルブロックは８×８または４×４ピクセルからなる。一般に、ブロックベースの画像処理はメモリアクセスと相性がよい。よって、メモリ帯域幅の使用が比較的少なくなる。
【００１６】
本発明に基づく、複数の候補エッジ方向を評価することに基づく方法のある実施形態では、前記試験ピクセル群はそれぞれ平行四辺形のピクセルブロックであり、その実際の形は考察している候補エッジ方向に依存する。
【００１７】
本発明に基づく方法のもう一つの実施形態は、
・当該特定ピクセルに関してある第１の方向に反対向きのオフセットをもつ２つの試験ピクセルブロックのピクセル値の間の差の第１の和を計算し、
・当該特定ピクセルに関してある第２の方向に反対向きのオフセットをもつ２つの試験ピクセルブロックのピクセル値の間の差の第２の和を計算し、
・前記差の第１の和と前記差の第２の和との商を計算することによってエッジ方向を決定する、ことを有する。
【００１８】
任意的に、前記差の第１および第２の和はそれぞれ差の重み付きの和である。好ましくは、前記第１および第２の方向は互いに直交する。たとえば、前記第１の方向は水平で前記第２の方向は垂直である。本発明に基づくこの実施形態の利点は、前記エッジ方向の計算が比較的堅牢になるということである。本発明に基づくこの実施形態のもう一つの利点は、複数の候補エッジ方向の評価を有する諸実施形態に比べて計算数が比較的少ないということである。任意的に、前記差の第１の和の計算に使われる前記２つの試験ブロックのうちの一方は、前記差の第２の和の計算にも使われる。
【００１９】
比較的少ない計算でエッジ方向を推定するよう構成された、冒頭において述べたたぐいのエッジ方向推定ユニットを提供することが本発明のさらなる目的である。
【００２０】
本発明のこの目的は、前記割り当て手段が当該特定ピクセルを含んでいるある二次元目標ピクセルブロックに前記推定エッジ方向を割り当てるよう構成される形で達成される。
【００２１】
比較的少ない計算でエッジ方向を推定するよう構成された、冒頭において述べたたぐいの画像処理装置を提供することが本発明のさらなる目的である。
【００２２】
本発明のこの目的は、前記割り当て手段が当該特定ピクセルを含んでいるある二次元目標ピクセルブロックに前記推定エッジ方向を割り当てるよう構成される形で達成される。
【００２３】
前記画像処理装置は、出力画像を表示するための表示装置など追加的な構成要素を有していてもよい。該画像処理ユニットは以下の種類の画像処理の一つまたは複数をサポートしていてもよい。
【００２４】
・インターレース除去：インターレースは奇数番目と偶数番目の画像走査線を交互に送信する映像放送で一般的な手続きである。インターレース除去は、完全な垂直解像度を復元する、すなわち各画像ごとに奇数番目と偶数番目の両方の走査線が得られるようにする。
【００２５】
・映像周波数変換：（インターレースされた）オリジナル入力画像の系列から（インターレースされた）出力画像のより大きな系列が計算される。出力のうち補間された画像は時間的にオリジナル入力画像２枚の間に位置する。
【００２６】
・空間的画像スケーリング：オリジナル入力画像の系列から、該入力画像よりも空間解像度の高い出力画像の系列が計算される。
【００２７】
・ノイズ削減：エッジ方向の情報は前記補間を制御するために重要である。これはまた、時間的処理にも関わり、空間−時間的ノイズ削減につながることもありうる。
【００２８】
・ビデオ圧縮、すなわちエンコードまたはデコード。たとえばＭＰＥＧ規格によるもの。
前記画像処理装置は、たとえばテレビ、セットトップボックス、ビデオデッキ、衛星チューナー、ＤＶＤ（Digital  Versatile  Disk［デジタル多目的ディスク］）プレーヤーもしくはレコーダーでありうる。
【００２９】
必要とされる計算が比較的少ない、冒頭において述べたたぐいのコンピュータプログラムプロダクトを提供することが本発明のさらなる目的である。
【００３０】
本発明のこの目的は、当該特定ピクセルを含んでいるある二次元目標ピクセルブロックに前記推定エッジ方向が割り当てられる形で達成される。
【００３１】
前記方法の修正およびその変形は、前記エッジ方向推定ユニット、前記画像処理装置および前記コンピュータプログラムプロダクトの修正およびその変形に対応するものでありうる。
【００３２】
本発明に基づく前記方法の、前記エッジ方向推定ユニットの、前記画像処理装置の、そして前記コンピュータプログラムプロダクトのこれらのことを含むさまざまな側面は、以下に付属の図面を参照しつつ記載される実装および実施形態によって明快に説明されることであろう。
【００３３】
図面を通じて、同じ参照符号は同様の部分を示すのに使われている。
【発明を実施するための最良の形態】
【００３４】
図１は、位置X〔本訳稿では便宜上下線でベクトルを表す〕のピクセルからなるある目標ブロックB(X)１０２中のある特定のピクセル１００の候補エッジ方向を評価するために使われる２つの試験ピクセルブロック１０４、１０６を示す概略図である。候補エッジ方向の評価は差分絶対値和（SAD:  Summed  Absolute  Difference）を一致基準とすることに基づいている。これに代わる、同じくらい好適な一致基準としてはたとえば、平均平方誤差（Mean  Square  Error）、規格化相互相関（Normalized  Cross  Correlation）、大差ピクセル数（Number  of  Significantly  Different  Pixels）などがある。ある特定の候補（candidate）エッジ方向tngtcについての一致誤差の計算は、たとえば式（１）で規定される。
【００３５】
SAD(tngtc,X,n)＝Σ｜F(x−tngtc,y＋1,n)−F(x＋tngtc,y−1,n)｜      （１）
〔和はx∈B(X)で行う〕
ここで、x＝(x,y)であり、F(x,n)は輝度信号、nは画像番号またはフィールド番号である。試験対象の候補エッジ方向は候補の集合（candidate  set）ＣＳから取ってきたもので、整数値のほかピクセル間値をとることもできる。結果として出力されるエッジ方向は、SADの値が最小になる候補エッジ方向である。その候補エッジ方向は、当該特定ピクセルを含んでいる目標ピクセルブロック１０２の諸ピクセルに割り当てられる。
【００３６】
前記候補の集合が式（２）
CS＝｛tngtc｜−8＜tngtc＜8｝      （２）
で規定され、たいていの応用ではピクセルの半分の精度で十分であるとすると、３０ほどの候補エッジ方向を評価する必要がある。しかし、本発明によれば、候補エッジ方向の数は予測または再帰を使って一桁減らすことができる。候補の集合を式（３）
CS(X,n)＝｛tngtc(n)｜tngt(X,n−1)−1,  tngt(X,n−1),  tngt(X,n−1)＋1｝      （３）
のように規定して良好な結果が実現された。ここで、tngt(X,n−1)は前回の画像n−1において位置Xに対して得られたエッジ方向の結果である。（簡単のため、整数点までの精度を前提としている。）実験によると、これは計算量の観点から魅力的であるばかりでなく、エッジ方向の一貫性向上にもつながる。任意的に、予測tngt(X,n−1)に対して該予測自身の次に（擬似ノイズの）アップデートが加えられる。
【００３７】
図２は、前記特定ピクセル１００の空間的環境において以前に推定されているエッジ方向２３０〜２５４に基づくいくつかの候補エッジ方向の選択を示す概略図である。これらの以前に推定された方向２３０〜２５４はそれぞれの目標ブロック２０２〜２２６に割り当てられたものである。特に時間的な予測が正しいエッジ方向に収束しない可能性のある動きの速いシーケンスについては、空間的な予測――たとえば同じ画像の他の部分にすでに割り当てられているエッジ方向――が有益であろう。ある好ましい実施形態では、有望な予測をその値と位置とに基づいて識別することができる。換言すれば、同じ画像の他の部分にすでに割り当てられているエッジ方向の集合から候補エッジ方向を選択することは、その候補エッジ方向の値とその候補エッジ方向が割り当てられている目標ブロックの中心ピクセルの当該特定ピクセル１００に対する位置とに基づく。たとえば、斜め隣の目標ピクセルブロック２１２に対して45°（tngtc＝1）のエッジ方向が割り当てられていたとすると、これは現在の目標ピクセルブロック２２８についての有望な予測となる。エッジが画像の大きな部分にわたって広がっていると想定しているのである。このことを明らかにするには、斜め隣の目標ピクセルブロック２１２に割り当てられているエッジ方向２４０が、当該特定ピクセル１００から前記斜め隣の目標ピクセルブロック２１２の中心ピクセル２６２への線分２６４と比較される。同様に、ブロック配列の位置(−2,1)にある目標ピクセルブロック２０６に割り当てられている値がtngtc＝−2だったとすると、これは現在の目標ピクセルブロック２２８についての有望な候補エッジ方向である。さらなる有望な候補は目標ピクセルブロック２１０、２１８、２２２に割り当てられているそれぞれエッジ方向２３８、２４６、２５０である。より正式な形では、
【００３８】
【数１】
2006529039.tif 000003
となる。式（４）の上側は二つ以上のｉの値について成り立つ可能性がある。その場合、好ましくはtngtcは絶対値が最小のiが割り当てられる。これを実現するのが次の擬似コードである。
【００３９】
【表１】
2006529039.tif 000004
候補の集合CSが時間的候補および空間的候補、すなわち同じ画像シーケンスの他の画像に対して推定されたエッジ方向および同じ画像の他の目標ブロックに対してのエッジ方向を含んでいることは明らかであろう。
【００４０】
任意的に、異なるエッジ方向候補に対してペナルティが加えられる。こうしたペナルティは時間的か空間的かといった候補の種類に依存してもよいが、候補の値そのものに依存してもよい。たとえば、水平軸に比べて比較的小さな角度の候補エッジ方向は比較的大きなペナルティでアップデートされるようにするなどである。
【００４１】
図３は、本発明の別の実施形態に基づいてエッジ方向を計算するのに使われる２対の試験ピクセルブロックを示す概略図である。このエッジ方向は、当該目標ピクセルブロックの諸ピクセルに直接割り当てることができる。あるいはまた、計算されたエッジ方向は、図５との関連で述べるように評価されるべき候補エッジ方向の集合を生成するための初期推定として適用される。試験ピクセルブロックの第１の対は、特定ピクセル１００を含んでいる、位置Xのピクセルからなる特定の目標ブロックB(X)３００に関して水平方向左にシフトさせた第１の試験ピクセルブロック３０２および、前記特定の目標ピクセルブロック３００に関して水平方向右にシフトさせた第２の試験ピクセルブロック３０４からなる。試験ピクセルブロックの第２の対は、前記特定の目標ピクセルブロック３００に関して垂直方向上にシフトさせた第３の試験ピクセルブロック３０６および、前記特定の目標ピクセルブロック３００に関して垂直方向下にシフトさせた第４の試験ピクセルブロック３０８からなる。適用されるシフトは典型的には１ピクセルである。エッジ方向の計算は、
・前記特定の目標ピクセルブロック３００に関して反対向きの水平オフセットをもつ２つの試験ピクセルブロック３０２、３０４のそれぞれのピクセル値の間の差の第１の和SH(B(X))を式（５）で規定されるように計算し、
・前記特定の目標ピクセルブロック３００に関して反対向きの垂直オフセットをもつ２つの試験ピクセルブロック３０６、３０８のそれぞれのピクセル値の間の差の第２の和SV(B(X))を式（６）で規定されるように計算し、
・前記第１の差の和と前記第２の差の和との商を計算することによってエッジ方向の初期推定値E(B(X))を式（７）で規定されるように決定する、ことを有する。
【００４２】
SH(B(X))＝Σ｛F(x−(1,0))−F(x＋(1,0))｝      （５）
〔和はx∈B(X)で行う〕
SV(B(X))＝Σ｛F(x−(0,1))−F(x＋(0,1))｝      （６）
〔和はx∈B(X)で行う〕
E(B(X))＝αSH(B(X))／SV(B(X))      （７）
ここで、αは前記特定の目標ピクセルブロックB(X)３００に関するシフトの量に依存する定数である。SV(B(X))＝0で分母が０となるためにE(B(X))が計算できなくなるのを避けるため、特別の用心が払われる。たとえば、商を計算する前にSV(B(X))に非常に小さな値が加えられる。あるいはまた、SV(B(X))は所定の閾値と比較される。SV(B(X))が該所定の閾値を超えた場合にのみ前記の商が計算され、そうでない場合にはE(B(X))にはデフォルト値が設定される。
【００４３】
前記初期推定値に基づいて、前記特定の目標ピクセルブロックB(X)３００についての候補の集合は
CS(X,n)＝｛tngtc(n)｜E(B(X))−T≦tngtc(n)≦E(B(X))+T｝      （８）
で定義される。ここで、Tは所定の閾値（threshold）である。
【００４４】
図４は、それぞれの候補エッジ方向の一致誤差を計算するのに使われる平行四辺形の試験ピクセルブロック４０２〜４１２の対を示す概略図である。試験ピクセルブロックの第１の対は特定のピクセル１００に関して垂直方向上にシフトさせた第１の試験ピクセルブロック４０２および、前記特定ピクセルに関して垂直方向下にシフトさせた第２の試験ピクセルブロック４０４からなる。第１試験ピクセルブロック４０２および第２試験ピクセルブロック４０４は、前記特定ピクセル１００に対する相対位置が垂直成分のみを含み、水平成分を含まないので、長方形である。試験ピクセルブロックの第２の対は特定のピクセル１００に関して垂直方向上にシフトさせ、水平方向左にシフトさせた第３の試験ピクセルブロック４０６および、前記特定ピクセル１００に関して垂直方向下にシフトさせ、水平方向右にシフトさせた第４の試験ピクセルブロック４０８からなる。第３試験ピクセルブロック４０６および第４試験ピクセルブロック４０８は、前記特定ピクセル１００に対する相対位置が垂直成分、水平成分の両方を含んでいるので、平行四辺形様になる。試験ピクセルブロックの第３の対は特定のピクセル１００に関して垂直方向上にシフトさせ、水平方向右にシフトさせた第５の試験ピクセルブロック４１０および、前記特定ピクセル１００に関して垂直方向下にシフトさせ、水平方向左にシフトさせた第６の試験ピクセルブロック４１２からなる。さまざまな試験ピクセルブロック４０２〜４１２の形は、対応するエッジ方向に関係している。たとえば、第１の試験ピクセルブロックの対を用いては、垂直方向のエッジ方向が評価される。
【００４５】
図５は、本発明に基づくエッジ方向推定ユニット５００の実施形態を示す概略図である。該ユニットは、
・候補エッジ方向の集合を生成する候補生成ユニット５０２と、
・候補エッジ方向のそれぞれについて対応するピクセル群の対についての一致誤差を計算することによって該候補エッジ方向を評価する評価ユニット５０４と、
・前記それぞれの一致誤差に基づいて前記候補エッジ方向の集合から前記候補エッジ方向の第１のものを選択し、前記候補エッジ方向の該第１のものを当該特定ピクセルに割り当てる選択ユニット５０６、
とを有する。評価ユニット５０４は前記一致誤差を、前記対応するピクセル群の対をなす２つの群のピクセル値の間の差に基づいて計算するよう構成されている。ここで、前記２つのピクセル群の前記特定ピクセルに関する位置は考察中の候補エッジ方向に依存する。前記ピクセル値は入力端子５１２によって与えられる。好ましくは、試験ピクセル群は試験ピクセルブロックである。これらの試験ピクセルブロックの形は長方形であることもあるし、図４との関連で述べたような平行四辺形であることもある。
【００４６】
前記候補生成ユニット５０２は候補エッジ方向の集合を以前の計算に基づいて生成するよう構成されている。好ましくは、当該エッジ方向推定ユニット５００は、前記選択ユニット５０６と前記候補生成ユニット５０２との間の任意的な接続を有しており、前記候補生成ユニット５０２に図１、図２との関連で述べたように選択されたエッジ方向に関連するデータを提供できるようになっている。任意的に、当該エッジ方向推定ユニット５００は、図３との関連で述べたように初期推定値を計算するよう構成された初期推定ユニット５１０を有している。
【００４７】
候補エッジ方向の評価はピクセル群について実行される。結果として、選択ユニット５０６によって割り当てられる一つのエッジ方向は、その群のすべてのピクセルに割り当てられる。個々のピクセルによって、あるいはピクセル部分群によって異なるエッジ方向の値を実現するためには、当該エッジ方向推定ユニット５００はブロック侵食ユニット５０８を有することができる。このブロック侵食ユニット５０８の作用は図７Ａ〜図７Ｃとの関連で説明される。
【００４８】
当該エッジ方向推定ユニット５００はその出力端子にエッジ方向の二次元配列を与える。
【００４９】
候補生成ユニット５０２、評価ユニット５０４、選択ユニット５０６、初期推定ユニット５１０およびブロック侵食ユニット５０８は一つのプロセッサを使って実装できる。通常、これらの機能はソフトウェアプログラムプロダクトの制御のもとに実行される。実行の間、通常は前記ソフトウェアプログラムプロダクトはＲＡＭのようなメモリに読み込まれており、そこから実行される。該プログラムはＲＯＭ、ハードディスクまたは磁気および／または光学記憶装置のような補助記憶装置から読み込まれてもよいし、インターネットのようなネットワークを通じて読み込まれてもよい。任意的に、カスタムチップ（application  specific  integrated  circuit）によって前記開示された機能を提供してもよい。
【００５０】
図６は本発明に基づく画像処理装置の実施形態を示す概略図である。該画像処理装置は、
・入力画像を表す信号を受信する受信手段６０２と、
・画像処理ユニット６０４と、
・該画像処理ユニットを制御する、図５との関連で述べたようなエッジ方向推定ユニット５００と、
・前記画像処理ユニット６０４の出力画像を表示する表示装置６０６、
とを有する。前記画像処理ユニット６０４は以下の機能の一つまたは複数を実行するよう構成されていてもよい：インターレース除去、映像周波数変換、空間的画像スケーリング、ノイズ削減、ビデオ圧縮。前記インターレース除去は好ましくはＴ・ドイレ（Doyle）およびＭ・ローイマンス（Looymans）によって論文「エッジ情報を使った順次走査変換（Progressive  scan  conversion  using  edge  information）」（Ｌ・キアリリオーネ（Chiariglione）（編）『ＨＤＴＶの信号処理（Signal  Processing  of  HDTV）ＩＩ』、エルセヴィエ・サイエンス・パブリッシャーズ、１９９０年、ｐｐ．７１１〜７２１）によって記載されているようなものである。
【００５１】
前記信号はアンテナまたはケーブルを通じて受信された放送信号でもよいが、ビデオデッキ（ＶＣＲ）またはデジタル多用途ディスク（ＤＶＤ）のような記憶装置からの信号でもよい。該信号は入力端子６１０で与えられる。当該画像処理装置６００は、たとえばテレビでありうる。あるいはまた、当該画像処理装置６００は任意的な表示装置を有しておらず、前記出力画像を表示装置６０６を有する装置に提供するのでもよい。その場合、当該画像処理装置６００はたとえばセットトップボックス、衛星チューナー、ビデオデッキ、ＤＶＤプレーヤーもしくはレコーダーなどでありうる。任意的に、当該画像処理装置６００は、ハードディスクまたは、光ディスクなどリムーバブルメディア上の記憶手段のような保存手段を有している。当該画像処理装置６００はまた映画スタジオまたは放送局によって利用されるシステムであってもよい。
【００５２】
図７Ａ、図７Ｂ、図７Ｃはブロック侵食、すなわち前記ブロック侵食ユニット５０８の作用を概略的に示している。図７Ａでは４つの目標ピクセルブロックＡ、Ｂ、Ｃ、Ｄが描かれている。これらの目標ピクセルブロックのそれぞれはたとえば８×８ピクセルからなる。これらの目標ピクセルブロックのそれぞれに選択ユニット５０６によってエッジ方向が割り当てられている。それはすなわち、たとえば目標ブロックＡの６４ピクセル全部にエッジ方向として同じ値V(A)が割り当てられており、目標ブロックＢの６４ピクセル全部にはエッジ方向として値V(B)が割り当てられているという意味である。
【００５３】
ブロック侵食は、ピクセルのサブブロックによって異なるエッジ方向の値を実現するために実行される。図７Ｂでは、目標ピクセルブロックＡが４つのサブブロックＡ１、Ａ２、Ａ３、Ａ４に分割されているところが描かれている。これらの（たとえば４×４の）ピクセルのサブブロックのそれぞれについて、エッジ方向の値は、親の目標ピクセルブロックＡのエッジ方向の値V(A)に基づいて、かつ親の目標ピクセルブロックＡの隣接目標ピクセルブロックのエッジ方向の値に基づいて計算される。たとえば、サブブロックＡ４のエッジ方向の値V(A4)は、親の目標ピクセルブロックＡのエッジ方向の値V(A)ならびに、親の目標ピクセルブロックＡの隣接目標ピクセルブロックＢおよびＣのエッジ方向の値V(B)およびV(C)に基づいて計算される。この計算は式（９）で表されるようなものでよい。
【００５４】
V(A4)＝median(V(A),V(B),V(C))      （９）
好ましくは、ブロック侵食は階層的に実行される。図７Ｃでは、図７ＢのピクセルのサブブロックＡ１が４つのサブブロックＡ１１、Ａ１２、Ａ１３、Ａ１４に分割されているところが描かれている。これらの（たとえば２×２の）ピクセルのサブブロックのそれぞれについて、エッジ方向の値は、親のピクセルサブブロックＡ１のエッジ方向の値V(A1)に基づいて、かつ親のピクセルサブブロックＡ１の隣接目標ピクセルブロックのエッジ方向の値に基づいて計算される。たとえば、サブブロックＡ１４のエッジ方向の値V(A14)は、親のピクセルサブブロックＡ１のエッジ方向の値V(A1)ならびに、親のピクセルサブブロックＡ１の隣接ピクセルサブブロックＡ２およびＡ３のエッジ方向の値V(A2)およびV(A3)に基づいて計算される。この計算は式（１０）で表されるようなものでよい。
【００５５】
V(A14)＝median(V(A1),V(A2),V(A3))      （１０）
さらなるサブブロックへの分割を適用することもできることは明らかであろう。
【００５６】
上記の実施形態は本発明を解説するものであって限定するものでないこと、そして当業者は付属の特許請求の範囲から離れることなく代替的な実施形態を考案することができるであろうことを注意しておく必要がある。請求項において、括弧内に参照符号があったとしてもそれを請求項を限定するものと解釈してはならない。「有する」の語は請求項に挙げられていない要素またはステップの存在を排除するものではない。要素の単数形の表現はそのような要素の複数の存在を排除するものではない。本発明は、いくつかの区別できる要素を有するハードウェアによっても、好適にプログラムされたコンピュータによっても実装できる。いくつかの手段を列挙する装置請求項において、そうした手段のいくつかは単一のハードウェア項目によって具現されることもできる。
【図面の簡単な説明】
【００５７】
【図１】本発明のある実施形態に基づき、ある特定のピクセルの候補エッジ方向を評価するために使われる２つの試験ピクセルブロックを示す概略図である。
【図２】当該特定ピクセルの空間的な環境中で以前に推定されたエッジ方向に基づいていくつかの候補エッジ方向の選択を示す概略図である。
【図３】本発明の別の実施形態に基づいてエッジ方向を計算するのに使われる２対の試験ピクセルブロックを示す概略図である。
【図４】それぞれの候補エッジ方向の一致誤差を計算するのに使われる平行四辺形の試験ピクセルブロックの対を示す概略図である。
【図５】本発明に基づくエッジ方向推定ユニットのある実施形態を示す概略図である。
【図６】本発明に基づく画像処理装置のある実施形態を示す概略図である。
【図７Ａ】ブロック侵食を示すための概略図である。
【図７Ｂ】ブロック侵食を示すための概略図である。
【図７Ｃ】ブロック侵食を示すための概略図である。
【図１】
2006529039.tif 000005
【図２】
2006529039.tif 000006
【図３】
2006529039.tif 000007
【図４】
2006529039.tif 000008
【図５】
2006529039.tif 000009
【図６】
2006529039.tif 000010
【図７Ａ】
2006529039.tif 000011
【図７Ｂ】
2006529039.tif 000012
【図７Ｃ】
2006529039.tif 000013
【国際調査報告】
2006529039.tif 000014
2006529039.tif 000015
2006529039.tif 000016