(57)【要約】高エラーレート条件下の適応可能な画素推定に対する方法及び装置が記述されている。画素の推定を実行するために、複数のクラスが作成され、実行可能なクラスが決定され、そして最適フィルタが適用される。
2006512799.tif 000002
【特許請求の範囲】
【請求項１】
画素推定方法において、
動きクラス候補を決定するステップと、
空間クラス候補を決定するステップと、
全クラス候補を決定するステップと、
上記全クラス候補をマージするステップと、
フィルタ推定のための情報を抽出するステップと、
最適フィルタを形成するステップと、
上記最適フィルタを適用するステップと
を有する画素推定方法。
【請求項２】
上記動きクラス候補を決定するステップは、静止画像のゼロ動きクラスを決定するステップを有することを特徴とする請求項１記載の画素推定方法。
【請求項３】
上記空間クラス候補を決定するステップは、
上記推定された画素近傍の選択された画素から閾値を抽出し、与えられた既知の画素と上記閾値との関連性、又は与えられた未知の画素値に二値の何れを割り当てるかに基づいて二値を割り当てることを特徴とする請求項１記載の画素推定方法。
【請求項４】
上記全クラス候補を決定するステップは、上記動きクラス候補及び上記空間クラス候補を用いて抽出することを特徴とする請求項１記載の画素推定方法。
【請求項５】
上記全クラス候補をマージするステップは、上記全クラス候補からの行列をマージすることを特徴とする請求項１記載の画素推定方法。
【請求項６】
上記全クラス候補をマージするステップは、上記全クラス候補から学習データをマージすることを特徴とする請求項１記載の画素推定方法。
【請求項７】
上記フィルタ推定のための情報を抽出するステップは、上記フィルタ推定のために部分行列を抽出することを特徴とする請求項１記載の画素推定方法。
【請求項８】
上記フィルタ推定のための情報を抽出するステップは、タップ位置候補の広範なドメインを決定するステップと、上記タップ位置候補のサブセットを選択するステップとを有することを特徴とする請求項７記載の画素推定方法。
【請求項９】
上記タップ位置候補のサブセットを選択するステップは、与えられたＫタップ位置と、与えられたタップ位置に対する破損していないデータに対する利用可能な計算能力からなるグループから選択された判定基準に基づいて選択するステップを有することを特徴とする請求項８記載の画素推定方法。
【請求項１０】
上記最適フィルタを形成するステップは、最小の正方形の最適フィルタを形成することを特徴とする請求項１記載の画素推定方法。
【請求項１１】
上記最小の正方形の最適フィルタは、学習に基づくことを特徴とする請求項記載の請求項１０記載の画素推定方法。
【請求項１２】
請求項１記載の画素推定方法を実行する処理が格納された機械読取可能な記録媒体。
【請求項１３】
メモリに接続されたプロセッサからなり請求項１記載の一連の画素推定方法を実行する処理装置。
【請求項１４】
動きクラス候補を決定する手段と、
空間クラス候補を決定する手段と、
全クラス候補を決定する手段と、
上記全クラス候補をマージする手段と、
フィルタ推定のための情報を抽出する手段と、
最適フィルタを形成する手段と、
上記最適フィルタを適用する手段と
を備える画素推定装置。
【請求項１５】
請求項１４記載の画素推定装置を意味する情報が格納された機械読取可能な記録媒体。
【請求項１６】
入力及び出力を有し、上記入力は画素情報を受け取るように接続され、
入力と出力を有するメモリを有し、上記入力は受け取り、行列情報を格納するように接続され、
入力と出力を有する相互接続された多数のセルを有し、上記セルの入力は、上記行列情報と上記画素情報を受け取るように接続され、上記相互接続されたセルの出力は、上記出力に接続されている画素推定装置。
【請求項１７】
上記行列情報は、上記画素情報に由来することを特徴とする請求項１６記載の画素推定装置。
【請求項１８】
上記内部で接続された多数のセルはそれぞれ、局所演算装置に接続された局所メモリを有することを特徴とする請求項１６記載の画素推定装置。
【請求項１９】
請求項１６記載の画素推定装置を意味する情報が格納された機械読取可能な記録媒体。
【請求項２０】
リアルタイムに画素をエラー回復及びエラー改善する方法において、リアルタイムに複数の画素が供給され、補償され及び改善される各画素毎に対してカスタムフィルタをリアルタイムに構築する画素のエラー回復及び改善方法。
【請求項２１】
各画素をエラー回復及びエラー改善する上記カスタムフィルタは、最小の正方形フィルタであることを特徴とする請求項２１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理に関し、特に、本発明は、高エラーレート条件下における適応画素推定方法及び装置に関する。
【背景技術】
【０００２】
従来、符号化による量子化の影響に起因した画素エラーを回復するため、及び後処理を改善するための技術が提案されており、その技術として３段階の処理が用いられていた。第１段階では、基本的な補間方法を用いて画像フレーム全体に対して粗い隠蔽（以下、コンシールメントという）が施されていた。また、第２段階では、エラーのある全ての画素を再び対象として取り上げて、隣接するデータを用い、局所的な空間、動き及びエラー分類に基づいてフィルタを選択することによりフレームが改善されていた。また、各々の分類に対応する１つの推定フィルタが予め準備された。そして、第３段階では、量子化の影響を低減するために固定の平滑化フィルタを適用していた。
【０００３】
予め準備されたフィルタでは、考えられるエラーパターン（消失画素パターン）の数が大幅に制限される。画素の消失を補償するために、従来は、準最適の粗い回復を行っていた。また、画素のエラー回復と画素のエラー改善とがそれぞれ別の処理であるので、処理には長い時間が必要とされる。これらが現在の問題点である。
【発明の開示】
【０００４】
高エラーレート条件下における適応画素推定方法及び装置について説明する。
【０００５】
本発明の一実施の形態は、幾つかの点で従来技術の問題点を改善することができるカスタムアルゴリズム及びアーキテクチャである。第１に、本発明の一実施の形態では、画像内においてエラー回復及びエラー改善される各画素に対するカスタムフィルタは、考えられるエラーパターン（消失画素パターン）の数が大幅に制限される予め用意されたフィルタを用いた従来技術と比べて、実時間で生成される。画素の消失を補償するために、従来は、準最適の粗い回復を行っていたが、この技術は、本発明の一実施例における処理には含まれない。
【０００６】
本発明のほかの実施の形態において、第２の改善点は、画素のエラー回復と画素のエラー改善の両方を組み込んで単一のワンパス処理とすることである。（単一処理にすることにより）処理遅延を低減することができ、また、平滑化処理を適応化するとともに中間の有限精度計算結果を可能な限り排除することによって、結果が数値的に向上する。
【０００７】
数学的概観
【０００８】
推定フィルタを設計するための１つの技術は、予め決められた複数の画像に対する最小自乗最適フィルタを、学習を用いて決定することである。学習データは、観測行列Ａと所望とする応答のベクトルｂに集められる。以下、これらの量、使用、及びこれらの効果的な応用例に関する問題点について説明する。
【０００９】
図３に示す推定タップ３００について考えると、画素番号１から４０は、ｘと名付けられた中央画素を推定するために用いられる画素を表している。この推定タップ３００が画像データで満たされる度に、行列Ａ及びベクトルｂに１行付加できる。特に、４０の観測画素が図３に示すシーケンスで配列されて、値ｘがベクトルｂに１列を与える。学習の後には、ｍ×４０の行列Ａと、ｍ個のベクトルｂが得られる。ここで、ｍは、学習の回数である。最小自乗最適フィルタは、下記式（１）をｘに関して最小化することによって見つかる（解が１つでない場合には、最小ノルム解を選択する）。解ベクトルｘＬＳは、最適フィルタの係数を表す。
【００１０】
【数１】
2006512799.tif 000003
【００１１】
行列Ａとベクトルｂを集めて保存する代わりに、行列Ｒ＝ＡＴＡとベクトルｙ＝ＡＴｂとを集めて保存することも可能である。これは、ｘＬＳが下記式（２）で表される最小ノルム解を満足するとき成り立つ。
【００１２】
【数２】
2006512799.tif 000004
【００１３】
各学習画素は、通常、新たな行を行列Ａ及びベクトルｂに付加する。これは、Ｒ及びｙを下記式（３）、（４）のように更新することと等価である。
【００１４】
【数３】
2006512799.tif 000005
【００１５】
【数４】
2006512799.tif 000006
【００１６】
ここで、ａＴｋは、行列Ａの行ｋを示し、ｂｋは、ベクトルｂの行ｋを示し、Ｒ及びｙの下付文字は、更新回数を示す。Ｒ０及びｙ０は、全成分がゼロの場合を定義している。
【００１７】
毎回同じ倍率を用いるという条件下では、その倍率は、下記式（５）においてはキャンセルされるので、オーバフローを防ぐために、Ｒ及びｙにある倍率をかけたものを保存してもよい。
【００１８】
【数５】
2006512799.tif 000007
【００１９】
Ｒｍ及びｙｍが集められると、求めるべき学習タップのサブセットに対して最適なフィルタが定義される。各タップは、行列Ａの１つの列に対応する。タップが使用できないときには、行列Ａにおいて対応した列を削除することによって、より小規模な系を定義する。同様に、行列Ｒｍ及びｙｍに対応する行及び列を削除することができる。
【００２０】
また、行列Ｒｍ及びｙｍが異なる学習データのセットに対して集められ、この情報が１つの大きなセットにマージされる。上付文字の番号は、表記上の目的で、これら別々の学習クラスを示すために用いられる。例えば、Ｒｍ（１）は、学習セット１に対して集めた行列を示し、ｍ個の学習サンプルからなる。学習データは、それらの学習行列を単純に加え、また適切な重み（通常、学習サンプルの数又は総学習サンプルの割合）をかけることによって合成することができる。学習データの一具体例を下記式（６）、（７）に示す。
【００２１】
【数６】
2006512799.tif 000008
【００２２】
【数７】
2006512799.tif 000009
【００２３】
具体例を用いたアルゴリズムの説明
本発明の一実施の形態として示すアルゴリズムの技術として詳細に説明する。以下、データ及びフィルタタップに基づく具体例を用いて詳細に説明する。具体例において、説明を必要とするタップの全数を、本発明を不明瞭にすること避けるために比較的少ないものとする。
【００２４】
以下の前フレームのデータが、既に供給され、出力装置（復号器）によって処理されている場合について説明する。
【００２５】
前フレームのデータを下記表１に示す。
【００２６】
【表１】
2006512799.tif 000010
【００２７】
また、以下のデータは、解を表している。すなわち達成されるように試算された画素値を表している。現在フレームのデータ（元のデータであり、復号器は知らない）を下記表２に示す。
【００２８】
【表２】
2006512799.tif 000011
【００２９】
以下のデータは、消失画素を含んで伸張することで生じる、量子化されて破損した現在フレームのデータを表している。Ｎ／Ａは、何らかの伝送損失のために利用できなくなった画素値を示す。ケース１として、復号器は、上述した解で示された値により近い値になるようにセンタ画素の値を改善することを見込んでフィルタを適用する。量子化されて破損した現在フレームのデータ（ケース１において改善される）を表３に示す。
【００３０】
【表３】
2006512799.tif 000012
【００３１】
ケース２として、センタ画素が消失したとき、復号器が利用可能なデータのみを用いて消失画素を補間する。現在フレームのデータ、すなわち量子化されて破損したデータ（ケース２において補完される）を表４に示す。
【００３２】
【表４】
2006512799.tif 000013
【００３３】
更に、この具体例では、局所的な動きが、現在フレーム及び前フレームに基づいて決定され、関心の画素を中心とした表５に示す形状のタップを用いて測定されるとする。
【００３４】
【表５】
2006512799.tif 000014
【００３５】
次に、現在フレームのみに基づいて決定され、関心の画素を中心とした表６に示す形状のタップを用いて空間テクスチャを測定する。
【００３６】
【表６】
2006512799.tif 000015
【００３７】
実際の装置では、タップは、前フレームに基づいて決定されるが、この具体例では、行列を印刷に適した大きさにするために、タップ数を制限して記載している。
【００３８】
次に、現在フレームのみに基づいて決定され、関心の画素を中心とした表７に示す形状のタップを用いたフィルタを適用する。各ケースでは、利用可能な画素のみを使用する。
【００３９】
【表７】
2006512799.tif 000016
【００４０】
学習行列データは、行及び列で配列され、この行／列の番号は、下記表８に示すスキャン順序においてタップ位置と一致する。
【００４１】
【表８】
2006512799.tif 000017
【００４２】
１：動きクラス候補の決定
回復された画素がビデオシーケンスの一部であるとき、動きクラス又は動き補償を用いることによって性能を高めることができる。
【００４３】
具体例として、現在フレームと前フレームとの間で計算され、動きクラスＭＣ＝０、１、２、３を決定するために閾値が決められた平均絶対画素により、動きクラスを分類する。エラーを含む画素は、この処理によって削除される。例えば、ケース１では、現在フレームと前フレームとの間の平均絶対差分は、破損していない８つの画素を用いて２２と計算される。一般的な損失を除けば、平均差分が１３以上２５以下の画素は、動きクラス２に属すものとし、動きクラス（以下、ＭＣという）は、ＭＣ＝２がセットされる。同様に、ケース２では、現在フレームと前フレームとの間の平均絶対差分は、破損していない７つの画素を用いて２０と計算される。その結果は、差分画素は、動きクラス２に属する。
【００４４】
２：空間クラス候補の決定
クラスタップ内における破損した画素を最初のパスで推定し、推定値をクラス分類処理で用いて、最初の推定パスで残されたエラーをクラス分類におけるエラーとする幾つかの技術とは対照的に、本発明では、空間クラス候補のリストを生成する。空間クラスは、以下のように決定される。関心のある画素の周囲で＋型を形成する５つの画素の平均値を求める。例えば、ケース１であれば、下記表９に示す５つの画素を使用して平均を計算すると１１２．２５になる。
【００４５】
【表９】
2006512799.tif 000018
【００４６】
平均値より大である画素には１を割り当て、それ以外には０を割り当てる。これらの二進数を探索して、ビット（ｄｉｇｉｔ）を形成する。このケースでは、上記５画素の値と１１２．２５とを比較すると、表１０に示す結果になる。
【００４７】
【表１０】
2006512799.tif 000019
【００４８】
（左から右及び上から下に）二進数が探索された後、二進数はデジタルデータ０１０ｘ０を形成する。このデジタルデータにおいてｘは、不明の固有値（すなわちＮ／Ａ）を示す。固有の空間クラスを強制的に割り当てる代わりに、このエラーと一致する空間クラスの全候補のリストを作成する。
【００４９】
したがって、適正なクラスは、ｘが０か１かによって、０１０００（＝８）又は０１０１０（＝１０）の何れかである。
【００５０】
同様に、ケース２では、下記表１１に示す５つの画素を使用して平均を計算すると、１１３になり、下記表１１に示す、二進数０１ｘｘ０で形成される閾値を適用する。したがって、適応するクラスは、０１０００（＝８）、０１０１０（＝１０）、０１１００（＝１２）、０１１１０（＝１４）である。消失したビットが２つのあるので、これらのクラスには、４つの可能性がある。
【００５１】
【表１１】
2006512799.tif 000020
【００５２】
３：クラス候補の決定
クラスの候補の全てを決定するために、上述したケース１の結果とケース２の結果とを結合する。例えば、全てのクラスは、クラスＩＤ＝４×ＳＣ＋ＭＣによって決定される。
【００５３】
例えば、ケース１において、ＭＣが２で、ＳＣが８又は１０の何れか一方であるとき、クラスＩＤは、４＊８＋２＝３２、４＊１０＋２＝４２の何れか一方である。同様に、ケース２においてクラス候補ＩＤは、３４、４２、５０、５８の何れかである。
【００５４】
４：クラス候補から行列をマージする
ここでは、（６）及び式（７）を適用することによって、全クラス候補から情報をマージする方法について説明する。以下に示す学習行列がＲＯＭに予め格納されているとする。
【００５５】
一例として、４８０００サンプルで学習された下記式で表されるクラスＩＤ＝３４。
【００５６】
【数８】
2006512799.tif 000021
【００５７】
【数９】
2006512799.tif 000022
【００５８】
２４０００サンプルで学習された下記式で表されるクラスＩＤ＝４２。
【００５９】
【数１０】
2006512799.tif 000023
【００６０】
【数１１】
2006512799.tif 000024
【００６１】
３８４００サンプルで学習された下記式で表されるクラスＩＤ＝５０。
【００６２】
【数１２】
2006512799.tif 000025
【００６３】
【数１３】
2006512799.tif 000026
【００６４】
５８５６０サンプルで学習された下記式で表されるクラスＩＤ＝５８。
【００６５】
【数１４】
2006512799.tif 000027
【００６６】
【数１５】
2006512799.tif 000028
【００６７】
続く具体例として、不明ビットを用いてクラス分類を決めなかったときの学習結果について考える。このケースでは、クラスＩＤ３４及びクラスＩＤ４２は、１つのクラスとして一体化されて表される。
【００６８】
式（６）及び式（７）によれば、重み付けされた学習行列を付加して、結合されたデータを用いて最小自乗最適フィルタを開発することによって、単純に一体化されたクラスから学習行列を形成することができる。ケース１では、下記式（１６）及び（１７）を形成し、ケース２では、下記式（１８）及び（１９）を形成する。
【００６９】
【数１６】
2006512799.tif 000029
【００７０】
【数１７】
2006512799.tif 000030
【００７１】
【数１８】
2006512799.tif 000031
【００７２】
【数１９】
2006512799.tif 000032
【００７３】
５：フィルタ推定のための部分行列の抽出
ケース１において、行２、列３の画素は利用できない。これは配置番号６に対応するので、Ｒと行６のｙから行６及び列６を削除する。ケース２では、行２、列２及び３の画素が利用できない。これらは、配置番号５と６に対応するので、Ｒと行５及び行６のｙから行５及び列６を削除する。
【００７４】
６：学習に基づくＬＳ最適フィルタを形成する。
破損していないデータポイントのみに一致する減じられた学習行列を利用して、式（２）で最小ノルム解を検出することによって、最小自乗最適フィルタを形成する。ケース１では、下記表１２に示すフィルタを得るために８行８列の系を解き、ケース２では、下記表１３に示すフィルタを得るために７行７列の系を解く。
【００７５】
【表１２】
2006512799.tif 000033
【００７６】
【表１３】
2006512799.tif 000034
【００７７】
７：データを推定するためにフィルタを適用する。
消失画素の推定を形成するためにフィルタを適用して消失画素を推定し、次の破損された画素に対して処理を継続する。ケース１では、推定値１１２．２５が得られる。ケース２では、推定値１２８．６９が得られる。
【００７８】
なお、ケース１において、センタータップは、既存の値が最大臨界値であることを意味する非常に大きな値を有する。センタータップは、既存の値が大きく変化しないようにしている。
【００７９】
図４に、ビデオ信号処理のために可能なアルゴリズムのフローチャート４００を示す。ビデオ信号の場合、動き、空間及びフィルタタップは、３次元で決定される。例えば、図３に示すタップを現在フレーム及び前フレームに適用して３次元フィルタを形成することができる。
【００８０】
ブロック４０２（可能な動きクラスを決定する）の一例において、動きクラス候補の決定方法は、絶対画素差分（または、利用できる画素がなければ０）の平均の計算を含む。このケースでは、正確に動きクラス候補が常に１つはある。
【００８１】
ステップ４０２において、動きクラス候補を決定する。ステップ４０４において、可能な空間クラスを決定する。ステップ４０６において、ステップ４０２で決定された動きクラス候補及びステップ４０４で決定された空間クラス候補から可能なクラスを決定する。続いて、クラス候補（ステップ４０６において決定された）から供給された学習データをステップ４０８においてマージする。続いて、ステップ４１０において、フィルタを推定するための部分行列を抽出する。ステップ４１２でフィルタを形成し、ステップ４１４において適用する。
【００８２】
図５は、静止画処理に用いることが可能なアルゴリズムのフローチャート５００を示す。このケースでは、動きクラスを決定することなく、フィルタは２次元でのみ決定される。
【００８３】
ステップ５０２において、空間クラス候補を決定する。次に、クラス候補（ステップ５０２で決定された）から供給された学習データをステップ５０４においてマージする。ステップ５０６において、フィルタを推定するための部分行列を抽出する。
ステップ５０８においてフィルタを形成し、ステップ５１０において適用する。
【００８４】
限られたリソースによる実施
十分な計算能力があれば、通常、可能な限り多くのタップを用いればよい。このためには、一実施の形態として、タップ配置候補の広範なドメインを最初に決定し、その後で使用するセットを選択してもよい（例えば、図３に示すように）。
【００８５】
消失画素データを推定するためのＫタップ推定フィルタを使用するに十分な計算能力があるとする。このとき、利用可能な全データから最も重要なＫタップを選択する。このためには、図３に示した順序に基づくフィルタタップに対して、使用可能な破損のないデータをチェックする。Ｋタップが選択されると、Ｒ及びｙの行に対応する行と列とを抽出する（上述した図５に示すように、フィルタ推定のための部分行列を抽出する）。
【００８６】
パラレルメモリの実施
この方法による多大な計算と各画素のエラー回復の独立により、単純な装置と実現可能な方法を有効に用いることにより、大規模並列処理を実現することができる。例えば、一例として、スマートな格納領域を構築してもよい。この格納領域におけるセルの各々は、上述の方法によってクラスＩＤの候補を特定することができる。処理は、共有のＲＯＭに格納された参照Ｒデータ及び参照ｙデータを伝播することによって開始することができる。
【００８７】
各セルは、セルの関心画素と一致するデータを保存することができる。また、コレに独立して、各セルは、自身に対して最適フィルタの解を求めることができ、破損したデータを固定するためにそれを適用することができる。
【００８８】
そして、修正されたデータをシフトアウトし、破損された次の画像の一部分を入力するシフトインする。
【００８９】
以上のように、高エラーレート条件下の適応画素推定に対する方法及び装置について説明した。
【００９０】
図１は、説明してきた技術を適用可能なネットワーク環境１００を示したものである。図示したように、Ｓサーバ１０４‐１〜１０４‐Ｓ及びＣクライアント１０８‐１〜１０８‐Ｃの形態の幾つかのコンピュータシステムがネットワーク１０２を介して相互に接続されており、このネットワーク１０２は、例えば、家庭内ネットワークとすることもできる。また、ネットワーク１０２は、インターネット、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、衛星リンク、光ファイバネットワーク、ケーブルネットワーク、またはこれらの組合せ、及び／又はその他との組合せのうちから少なくとも１つ以上を含むこともできる。サーバは、例えば、ディスク記憶システムとしての役割のほか、記憶及び演算リソースとしての役割を果たすこともできる。同様に、クライアントがコンピューティング、記憶、及び表示能力を有することもできる。ここで説明した方法又は装置は、基本的には、ＬＡＮ、ＷＡＮ、システムバス等のように、局所的な通信又は遠隔通信に関わらず、あらゆるタイプの通信手段又は装置に適用することができる。
【００９１】
図２は、コンピュータシステム２００のブロック図を示し、コンピュータシステム２００は、図１に示したクライアント及びサーバの典型例を示す。ブロック図は、高レベルの概念表示であり、種々の方法、及び種々のアーキテクチャにより実装することができる。バスシステム２０２は、中央処理装置（ＣＰＵ）２０４、読出し専用メモリ（ＲＯＭ）２０６、ランダムアクセスメモリ（ＲＡＭ）２０８、ストレージ２１０、ディスプレイ２２０、オーディオ２２２、キーボード２２４、ポインタ２２６、その他の入出力（Ｉ／Ｏ）装置、及び通信装置２３０を相互に接続する。バスシステム２０２は、例えば、システムバスとして、Peripheral Component Interconnect（ＰＣＩ）、Advanced Graphics Port（ＡＧＰ）、Small Computer System Interface（ＳＣＳＩ）、Institute of Electrical and Electronics Engineers（ＩＥＥＥ）標準数１３９４（FireWire）、Universal Serial Bus（ＵＳＢ）等のうちの少なくとも１つとすることができる。ＣＰＵ２０４は、単一、複数又は分散処理コンピューティングリソースとすることができる。ストレージ２１０は、コンパクトディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ）、ハードディスク（ＨＤ）、光ディスク、テープ、フラッシュ、メモリスティック、ビデオレコーダ等とすることができる。ディスプレイ２２０は、例えば、ブラウン管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、プロジェクションシステム、テレビジョン（ＴＶ）等とすることができる。なお、コンピュータシステムの実装に応じて、コンピュータシステムは、ブロック図の中のコンポーネントの幾つか、全て、それ以上、又は再配置を含むことができる。例えば、薄型のクライアントは、例えば、一般的なキーボードをもたない無線携帯装置とすることもできる。したがって、図２のシステムについては、多くの変形例が可能である。
【００９２】
本発明を検討し、理解するという観点から、技術及び手法の記述のために、様々な用語が当業者により使用されていることを理解されたい。更に、明細書本文には、説明の目的で、本発明を十分に理解させるために数多くの固有の詳細が示されている。しかし、当業者にとって、これらの特定の詳細な例がなくても本発明を実施できることは明白である。幾つかの事例においては、本発明を不明瞭にすることを避けるために、詳細ではなく、ブロック図の形で、公知の構造及び装置が示されている。これらの実施態様については、当業者が本発明を実施可能な程度に詳細な記述が行われており、その他の実施態様も利用可能であること、また、本発明の範囲を逸脱することなく、論理的、機械的、電気的、及びその他の変更を行うことができることは言うまでもない。
【００９３】
明細書の幾つかの部分は、例えば、コンピュータメモリ内のデータビットに関する演算のアルゴリズム及び記号表示により提示してもよい。これらのアルゴリズム記述及び表示は、データ処理の当業者が自らの仕事の内容をその他の当業者に伝達するための手段である。アルゴリズムは、ここでは、また一般的にも、所望の結果をもたらす一貫性のある一連のアクトであると考えられている。これらのアクトは、物理的数量の物理的操作を求めるアクトである。通常は、これらの数量は、記憶、転送、結合、比較、及びその他の操作が可能な電気又は磁気信号の形をとる。主として、共用という理由から、これらの信号をビット、値、エレメント、記号、文字、用語、数字等と呼ぶのが時には便利であることが明らかになっている。
【００９４】
しかしながら、これらの用語及び類似の用語の全てが適切な物理的数量と関連付けられていなければならず、しかもそれらの数量に適用される単なる便利なラベルにすぎないことに留意されたい。検討から明らかなような特段の指摘がない限りは、記述全体を通じて、「処理」又は「演算」又は「計算」又は「決定」又は「表示」等のような用語を利用する検討が、コンピュータシステムのレジスタ又はメモリ内に物理的（電子的）数量として表示されたデータを操作し、コンピュータシステムのレジスタ又はメモリ、又はその他のかかる情報ストレージ、伝送、又は表示装置内に物理的数量として同様に表示されるその他のデータに変換するコンピュータシステム又は類似の電子演算装置のアクション及びプロセスに言及できることが高く評価される。
【００９５】
本発明は、この点で演算を行うための装置により実施することができる。この装置は、所要の目的のために特別に構成することもできるし、コンピュータ内に記憶されたコンピュータプログラムにより選択的に起動又は設定される汎用コンピュータであってもよい。このようなコンピュータプログラムは、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、コンパクトディスク読出し専用メモリ（ＣＤ‐ＲＯＭ）及び磁気光ディスクを含むあらゆるタイプのディスク、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、消去可能なプログラマブル読取専用メモリ（ＥＰＲＯＭ）、電気消去可能プログラマブル読取専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリ、磁気又は光カード等、又はコンピュータに対して局所的又はコンピュータに対して遠隔的に電子的命令を記憶するのに適したあらゆるタイプのメディアのようなコンピュータ読出し可能媒体に記憶することができるが、媒体はこれらの限定されるわけではない。
【００９６】
ここに提示したアルゴリズム及びディスプレイはいずれかの特定のコンピュータ又はその他の装置と本質的に関連性を有するわけではない。様々な汎用システムをここにおける教示に従ってプログラムとともに使用することもできるし、所要の方法を実施するために専用の装置を構成するのが便利であることが明らかになることもある。例えば、汎用プロセッサのプログラミングにより、又はハードウェアとソフトウェアの任意の組合せにより、本発明による方法のいずれも固定配線回路内で実施することができる。本発明は、携帯装置、マルチプロセッサシステム、マイクロプロセッサベース又はプログラマブル家電製品、デジタルシグナルプロセッサ（ＤＳＰ）、セットトップボックス、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ等を含めた、ここに記述した以外のコンピュータシステム構成により実施可能であることが、当業者には直ちに高く評価されよう。通信ネットワークを通じてリンクされている遠隔処理装置によりタスクが実行される分散コンピュータ環境においても、本発明は実施可能である。
【００９７】
本発明の方法は、コンピュータソフトウェアを使用して実施することもできる。もし承認された規格に適応するプログラミング言語により書かれている場合は、多種多様なハードウェアプラットホーム上での実行のため、及び多種多様なオペレーティングシステムとのインタフェースのために、方法を実施するように設計された命令のシーケンスをコンパイルすることができる。それに加えて、本発明はいずれかの特定のプログラミング言語との関連で記述されているわけではない。ここに記述したような本発明の教示を実施するために、多種多様なプログラミング言語を使用することができることが高く評価されよう。更に、ソフトウェアは様々な形態（例えば、プログラム、プロシージャ、アプリケーション、ドライバ、・・・）でアクションを起こしたり、結果をもたらしたりするものであると言われるのが技術的には普通である。かかる表現は、コンピュータによりソフトウェアの実行により、コンピュータのプロセッサがアクションを行ったり、結果を作り出したりするということの省略表現であるにすぎない。
【００９８】
通信、プロトコル、アプリケーション、実装、メカニズム等を記述するために、様々な用語及び技術が当業者により使用されていることを理解されたい。かかる技術の１つは、アルゴリズム又は数式による技術の実装の記述である。すなわち、技術は、例えば、コンピュータによるコードの実行として実装することもできるが、一方、その技術の表現は、公式、アルゴリズム又は数式として、より適切かつ簡潔に伝達及び通信することもできる。したがって、当業者は、Ａ＋Ｂ＝Ｃを表示するブロックを、ハードウェア及び／又はソフトウェアにおけるその実装が２つの入力（Ａ及びＢ）をとり、加算出力（Ｃ）を作ることになる加法関数をして認識することになろう。したがって、記述としての公式、アルゴリズム又は数式の使用は、少なくとも（本発明の技術を実施することができるとともに、実施態様として実装することもできるコンピュータシステムのような）ハードウェア及び／又はソフトウェアの中に物理的実施態様を有するものとして理解するものとする。
【００９９】
機械読出し可能媒体は、機械（例えば、コンピュータ）による読出しが可能な形で情報を記憶又は伝送するためのあらゆるメカニズムを含むと理解される。例えば、機械読出し可能媒体としては、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記録媒体、光記録媒体、フラッシュメモリ装置、電気、光、音響又はその他の形態の伝播信号（例えば、搬送波、赤外線信号、デジタル信号等）等がある。
【０１００】
「可能な」クラス（単数又は複数）、クラス「候補」（単数又は複数）という言葉は、交換可能に使用されている。例えば、可能なクラスの決定は、クラス候補を決定することによって実行されてもよい。このように、クラス「候補」は、可能なクラスと考えてよい。
【０１０１】
このように、高エラーレート条件下における適応画素推定方法及び装置について説明してきた。
【図面の簡単な説明】
【０１０２】
【図１】本発明の具体例として示す方法及び／又は装置におけるネットワーク環境を示す模式図である。
【図２】本発明の具体例として方法及び／装置においてコンピュータシステムの一実施の形態を示すブロック図である。
【図３】中央タップ近傍の画素を推定するときに各配置が重要であることを示すシーケンスにおいて番号付けされた学習タップ候補の一実施の形態を示す図である。
【図４】ビデオシステムにおいて破損した画素を回復するためのアルゴリズムを説明するフローチャートの一具体例である。
【図５】静止画像において破損した画素を回復するためのアルゴリズムを説明するフローチャートの一具体例である。
【図１】
2006512799.tif 000035
【図２】
2006512799.tif 000036
【図３】
2006512799.tif 000037
【図４】
2006512799.tif 000038
【図５】
2006512799.tif 000039
【手続補正書】
【提出日】平成17年9月14日(2005.9.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画素推定方法において、
動きクラス候補を決定するステップと、
空間クラス候補を決定するステップと、
全クラス候補を決定するステップと、
上記全クラス候補をマージするステップと、
フィルタ推定のための情報を抽出するステップと、
最適フィルタを形成するステップと、
上記最適フィルタを適用するステップと
を有する画素推定方法。
【請求項２】
上記動きクラス候補を決定するステップは、静止画像のゼロの動きクラスを決定するステップを有することを特徴とする請求項１記載の画素推定方法。
【請求項３】
上記空間クラス候補を決定するステップは、
上記推定された画素近傍の選択された画素から閾値を抽出し、与えられた既知の画素と上記閾値との関連性、又は与えられた未知の画素値に二値の何れを割り当てるかに基づいて二値を割り当てることを特徴とする請求項１記載の画素推定方法。
【請求項４】
上記全クラス候補を決定するステップは、上記動きクラス候補及び上記空間クラス候補を用いて抽出することを特徴とする請求項１記載の画素推定方法。
【請求項５】
上記全クラス候補をマージするステップは、上記全クラス候補からの行列をマージすることを特徴とする請求項１記載の画素推定方法。
【請求項６】
上記全クラス候補をマージするステップは、上記全クラス候補から学習データをマージすることを特徴とする請求項１記載の画素推定方法。
【請求項７】
上記フィルタ推定のための情報を抽出するステップは、上記フィルタ推定のために部分行列を抽出することを特徴とする請求項１記載の画素推定方法。
【請求項８】
上記フィルタ推定のための情報を抽出するステップは、タップ位置候補の広範なドメインを決定するステップと、上記タップ位置候補の部分集合を選択するステップとを有することを特徴とする請求項７記載の画素推定方法。
【請求項９】
上記タップ位置候補の部分集合を選択するステップは、与えられたＫタップ位置と、与えられたタップ位置に対する破損していないデータに対する利用可能な計算能力からなるグループから選択された判定基準に基づいて選択するステップを有することを特徴とする請求項８記載の画素推定方法。
【請求項１０】
上記最適フィルタを形成するステップは、最小の正方形の最適フィルタを形成することを特徴とする請求項１記載の画素推定方法。
【請求項１１】
上記最小の正方形の最適フィルタは、学習に基づくことを特徴とする請求項記載の請求項１０記載の画素推定方法。
【請求項１２】
請求項１記載の画素推定方法を実行する処理が格納された機械読取可能な記録媒体。
【請求項１３】
メモリに接続されたプロセッサからなり請求項１記載の一連の画素推定方法を実行する処理装置。
【請求項１４】
動きクラス候補を決定する手段と、
空間クラス候補を決定する手段と、
全クラス候補を決定する手段と、
上記全クラス候補をマージする手段と、
フィルタ推定のための情報を抽出する手段と、
最適フィルタを形成する手段と、
上記最適フィルタを適用する手段と
を備える画素推定装置。
【請求項１５】
請求項１４記載の画素推定装置を意味する情報が格納された機械読取可能な記録媒体。
【請求項１６】
入力及び出力を有し、上記入力は画素情報を受け取るように接続され、
入力と出力を有するメモリを有し、上記入力は受け取り、行列情報を格納するように接続され、
入力と出力を有する相互接続された多数のセルを有し、上記セルの入力は、上記行列情報と上記画素情報を受け取るように接続され、上記相互接続されたセルの出力は、上記出力に接続されている画素推定装置。
【請求項１７】
上記行列情報は、上記画素情報に由来することを特徴とする請求項１６記載の画素推定装置。
【請求項１８】
上記内部で接続された多数のセルはそれぞれ、局所演算装置に接続された局所メモリを有することを特徴とする請求項１６記載の画素推定装置。
【請求項１９】
請求項１６記載の画素推定装置を意味する情報が格納された機械読取可能な記録媒体。
【請求項２０】
リアルタイムに画素をエラー回復及びエラー改善する方法において、リアルタイムに複数の画素が供給され、補償され及び改善される各画素に対してカスタムフィルタをリアルタイムに構築する画素のエラー回復及び改善方法。
【請求項２１】
各画素をエラー回復及びエラー改善する上記カスタムフィルタは、最小の正方形フィルタであることを特徴とする請求項２１記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理に関し、特に、高エラーレート条件下における適応画素推定方法及び装置に関する。
【背景技術】
【０００２】
従来、符号化後の量子化の影響に起因した画素エラーを回復するための技術、及び後処理を改善するための技術が提案されており、その技術として、多くの場合、３段階の処理が用いられていた。第１段階では、基本的な補間方法を用いて画像フレーム全体に対して粗い隠蔽（以下、コンシールメントという）が施されていた。また、第２段階では、エラーのある全ての画素を再び対象として取り上げて、隣接するデータを用い、局所的な空間、動き及びエラー分類に基づいてフィルタを選択することによりフレームが改善されていた。また、各々の分類に対応する１つの推定フィルタが予め準備された。そして、第３段階では、量子化の影響を低減するために固定の平滑化フィルタを適用していた。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところが、予め準備されたフィルタでは、考えられるエラーパターン（消失画素パターン）の数が大幅に制限される。画素の消失を補償するために、従来は、準最適の粗い回復を行っていた。また、画素回復と画素改善とがそれぞれ別の処理であるので、処理時間が長くなってしまう。これらが現在の問題点である。
【課題を解決するための手段】
【０００４】
本発明に係る画素推定方法は、動きクラス候補を決定するステップと、空間クラス候補を決定するステップと、全クラス候補を決定するステップと、全クラス候補をマージするステップと、フィルタ推定のための情報を抽出するステップと、最適フィルタを形成するステップと、最適フィルタを適用するステップとを有することにより、上述した課題を解決する。
【発明を実施するための最良の形態】
【０００５】
高エラーレート条件下における適応画素推定方法及び装置について説明する。
【０００６】
本発明の一実施の形態は、幾つかの点で従来の問題点を改善することができるカスタムアルゴリズム及びアーキテクチャである。第１に、本発明の一実施の形態では、画像内においてエラー回復及びエラー改善される各画素に対するカスタムフィルタは、考えられるエラーパターン（消失画素パターン）の数が大幅に制限される予め用意されたフィルタを用いた従来の方法と比べて、実時間で生成される。画素の消失を補償するために、従来は、準最適の粗い回復を行っていたが、この技術は、本発明の一実施例における処理には含まれない。
【０００７】
本発明の他の実施形態において、第２の改善点は、画素のエラー回復と画素のエラー改善の両方を組み込んで単一のワンパス処理とすることである。（単一処理にすることにより）処理遅延を低減することができ、また、平滑化処理を適応化するとともに中間の有限精度計算結果を可能な限り排除することによって、結果が数値的に向上する。
【０００８】
数学的概観
推定フィルタを設計するための１つの技術は、予め決められた複数の画像に対する最小自乗最適フィルタを、学習を用いて決定することである。学習データは、観測行列Ａと所望の応答についてのベクトルｂに集められる。以下、これらの量、使用、及びこれらの効果的な応用例に関する問題点について説明する。
【０００９】
図３に示す推定タップ３００について考えると、画素番号１から４０は、ｘと名付けられた中央画素を推定するために用いられる画素を表している。この推定タップ３００が画像データで満たされる度に、行列Ａ及びベクトルｂに１つの行を付加することができる。特に、４０の観測画素は、図３に示す番号によって示される順番で配列され、値ｘは、ベクトルｂに対する１列に寄与している。学習の後には、ｍ行４０列の行列Ａと、ｍ個のベクトルｂが得られる。ここで、ｍは、学習の回数である。最小自乗最適フィルタは、下記式（１）をｘに関して最小化することによって見つかる（解が１つでない場合には、最小ノルム解を選択する）。解ベクトルｘＬＳは、最適フィルタの係数を表す。
【００１０】
【数１】
2006512799.tif 000040
【００１１】
行列Ａとベクトルｂとを集めて保存する代わりに、行列Ｒ＝ＡＴＡとベクトルｙ＝ＡＴｂとを集めて保存することも可能である。これは、ｘＬＳが下記式（２）で表される最小ノルム解を満足するとき成り立つ。
【００１２】
【数２】
2006512799.tif 000041
【００１３】
各学習画素は、通常、新たな行を行列Ａ及びベクトルｂに追加する。これは、Ｒ及びｙを下記式（３）、（４）のように更新することと等価である。
【００１４】
【数３】
2006512799.tif 000042
【００１５】
【数４】
2006512799.tif 000043
【００１６】
ここで、ａｋＴは、行列Ａの行ｋを示し、ｂｋは、ベクトルｂの行ｋを示し、Ｒ及びｙの下付文字は、更新回数を示す。Ｒ０及びｙ０は、全成分がゼロの場合を定義している。
【００１７】
毎回同じ倍率を用いるという条件下では、その倍率は、下記式（５）においてはキャンセルされるので、オーバフローを防ぐために、Ｒ及びｙにある倍率をかけたものを保存してもよい。
【００１８】
【数５】
2006512799.tif 000044
【００１９】
Ｒｍ及びｙｍが集められると、求めるべき学習タップの部分集合に対して最適なフィルタが定義される。各タップは、行列Ａの１つの列に対応する。タップが使用できないときには、行列Ａにおいて対応した列を削除することによって、より小規模な系を定義する。同様に、行列Ｒｍ及びｙｍに対応する行及び列を削除することもできる。
【００２０】
また、行列Ｒｍ及びｙｍが異なる学習データの集合に対して集められ、この情報が１つの大きな集合にマージされる。上付文字の番号は、表記上の目的で、これら別々の学習クラスを示すために用いられる。例えば、Ｒｍ（１）は、学習セット１に対して集めた行列を示し、ｍ個の学習サンプルからなる。学習データは、それらの学習行列を単純に加え、また適切な重み（通常、学習サンプルの数又は総学習サンプルの割合）をかけることによって結合することができる。学習データの一具体例を下記式（６）、（７）に示す。
【００２１】
【数６】
2006512799.tif 000045
【００２２】
【数７】
2006512799.tif 000046
【００２３】
具体例を用いたアルゴリズムの説明
本発明の一実施の形態として示すアルゴリズムの技術として詳細に説明する。以下、データ及びフィルタタップに基づく具体例を用いて詳細に説明する。本発明を不明瞭にすること避けるために、本具体例では、説明を必要とするタップの全数を比較的少なく扱うことにする。
【００２４】
以下の前フレームのデータが、既に供給され、出力装置（復号器）によって処理されている場合について説明する。
【００２５】
前フレームのデータを下記表１に示す。
【００２６】
【表１】
2006512799.tif 000047
【００２７】
また、下記表２のデータは、解、すなわち達成されようとしている画素値を表している。この現フレームのデータ（元のデータであり、復号器は知らない）を下記表２に示す。
【００２８】
【表２】
2006512799.tif 000048
【００２９】
以下のデータは、消失画素を含んで伸長することで生じ、量子化され破損した現フレームのデータを表している。Ｎ／Ａは、何らかの伝送損失のために利用できなくなった画素値を示す。ケース１として、復号器は、上述した解で示された値により近い値になるように中央画素の値を改善することを見込んでフィルタを適用する。量子化され破損した現フレームのデータ（ケース１：改善）を表３に示す。
【００３０】
【表３】
2006512799.tif 000049
【００３１】
ケース２として、中央画素が消失したとき、復号器が利用可能なデータのみを用いて消失画素を補間する。量子化されて破損し中央画素が消失した現フレームのデータ（ケース２：補完）を表４に示す。
【００３２】
【表４】
2006512799.tif 000050
【００３３】
更に、この具体例では、局所的な動きが、現フレーム及び前フレームに基づいて決定され、関心の画素を中心とした表５に示す形状のタップを用いて評価されるものとする。
【００３４】
【表５】
2006512799.tif 000051
【００３５】
次に、現フレームのみに基づいて決定され、関心の画素を中心とした表６に示す形状のタップを用いて空間テクスチャを評価する。
【００３６】
【表６】
2006512799.tif 000052
【００３７】
実際の装置では、タップは、前フレームに基づいて決定されるが、この具体例では、行列を印刷に適した大きさにするために、タップ数を制限して記載している。
【００３８】
次に、現フレームのみに基づいて決定され、関心の画素を中心とした表７に示す形状のタップを用いたフィルタを適用する。
【００３９】
【表７】
2006512799.tif 000053
【００４０】
学習行列データは、行及び列に配列され、この行／列の番号は、下記表８に示すスキャン順序においてタップ位置と一致する。
【００４１】
【表８】
2006512799.tif 000054
【００４２】
１：動きクラス候補の決定
回復された画素がビデオシーケンスの一部であるとき、動きクラス又は動き補償を用いることによって性能を高めることができる。
【００４３】
具体例として、現フレームと前フレームとの間で計算され、動きクラスＭＣ＝０、１、２、３を決定するために閾値が決められた平均絶対画素により、動きクラスを分類する。エラーを含む画素は、この処理によって削除される。例えば、ケース１では、現フレームと前フレームとの間の平均絶対差分は、破損していない８つの画素を用いて２２と計算される。一般的な損失を除けば、平均差分が１３以上２５以下の画素は、動きクラス２に属すものとし、動きクラス（以下、ＭＣという）は、ＭＣ＝２がセットされる。同様に、ケース２では、現フレームと前フレームとの間の平均絶対差分は、破損していない７つの画素を用いて２０と計算される。その結果は、差分画素は、動きクラス２に属する。
【００４４】
２：空間クラス候補の決定
クラスタップ内における破損した画素を最初のパスで推定し、推定値をクラス分類処理で用いて、最初の推定パスで残されたエラーをクラス分類におけるエラーとする幾つかの技術とは対照的に、本発明では、空間クラス候補のリストを生成する。空間クラスは、以下のように決定される。関心のある画素の周囲でプラス型（＋型）を形成する５つの画素の平均値を求める。例えば、ケース１であれば、下記表９に示す５つの画素を使用して平均を計算すると１１２．２５になる。
【００４５】
【表９】
2006512799.tif 000055
【００４６】
平均値より大である画素には１を割り当て、それ以外には０を割り当てる。これらの二進数を探索して、ビット（ｄｉｇｉｔ）を形成する。このケースでは、上記５画素の値と１１２．２５とを比較すると、表１０に示す結果になる。
【００４７】
【表１０】
2006512799.tif 000056
【００４８】
（左から右及び上から下に）二進数が探索された後、二進数はデジタルデータ０１０ｘ０を形成する。このデジタルデータにおいてｘは、不明の固有値（すなわちＮ／Ａ）を示す。固有の空間クラスを強制的に割り当てる代わりに、このエラーと一致する空間クラスの全候補のリストを作成する。
【００４９】
したがって、適正なクラスは、ｘが０か１かによって、０１０００（＝８）又は０１０１０（＝１０）の何れかである。
【００５０】
同様に、ケース２では、下記表１１に示す５つの画素を使用して平均を計算すると、１１３になり、下記表１１に示す、二進数０１ｘｘ０で形成される閾値を適用する。したがって、適応するクラスは、０１０００（＝８）、０１０１０（＝１０）、０１１００（＝１２）、０１１１０（＝１４）である。消失したビットが２つあるので、これらのクラスには、４つの可能性がある。
【００５１】
【表１１】
2006512799.tif 000057
【００５２】
３：クラス候補の決定
クラスの候補の全てを決定するために、上述したケース１の結果とケース２の結果とを結合する。例えば、全てのクラスは、クラスＩＤ＝４×ＳＣ＋ＭＣによって決定される。
【００５３】
例えば、ケース１において、ＭＣが２で、ＳＣが８又は１０の何れか一方であるとき、クラスＩＤは、４＊８＋２＝３２、４＊１０＋２＝４２の何れか一方である。同様に、ケース２においてクラス候補ＩＤは、３４、４２、５０、５８の何れかである。
【００５４】
４：クラス候補から行列をマージする
ここでは、（６）及び式（７）を適用することによって、全クラス候補から情報をマージする方法について説明する。以下に示す学習行列がＲＯＭに予め格納されているとする。
【００５５】
一例として、４８０００サンプルで学習された下記式で表されるクラスＩＤ＝３４。
【００５６】
【数８】
2006512799.tif 000058
【００５７】
【数９】
2006512799.tif 000059
【００５８】
２４０００サンプルで学習された下記式で表されるクラスＩＤ＝４２。
【００５９】
【数１０】
2006512799.tif 000060
【００６０】
【数１１】
2006512799.tif 000061
【００６１】
３８４００サンプルで学習された下記式で表されるクラスＩＤ＝５０。
【００６２】
【数１２】
2006512799.tif 000062
【００６３】
【数１３】
2006512799.tif 000063
【００６４】
５８５６０サンプルで学習された下記式で表されるクラスＩＤ＝５８。
【００６５】
【数１４】
2006512799.tif 000064
【００６６】
【数１５】
2006512799.tif 000065
【００６７】
続く具体例として、不明ビットを用いてクラス分類を決めなかったときの学習結果について考える。このケースでは、クラスＩＤ３４及びクラスＩＤ４２は、１つのクラスとして一体化されて表される。式（６）及び式（７）によれば、単純に重み付けされた学習行列を追加すること、及びこの結合されたデータを用いて最小自乗最適フィルタを実現することによって、この一体化されたクラスについての学習行列を形成することができる。ケース１では、下記式（１６）及び（１７）を形成し、ケース２では、下記式（１８）及び（１９）を形成する。
【００６８】
【数１６】
2006512799.tif 000066
【００６９】
【数１７】
2006512799.tif 000067
【００７０】
【数１８】
2006512799.tif 000068
【００７１】
【数１９】
2006512799.tif 000069
【００７２】
５：フィルタ推定のための部分行列の抽出
ケース１において、行２、列３の画素は利用できない。これは配置番号６に対応するので、Ｒと行６のｙから行６及び列６を削除する。ケース２では、行２、列２及び３の画素が利用できない。これらは、配置番号５と６に対応するので、Ｒと行５及び行６のｙから行５及び列６を削除する。
【００７３】
６：学習に基づくＬＳ最適フィルタを形成する。
【００７４】
破損していないデータポイントのみに一致する減じられた学習行列を利用して、式（２）で最小ノルム解を検出することによって、最小自乗最適フィルタを形成する。ケース１では、下記表１２に示すフィルタを得るために８行８列の系を解き、ケース２では、下記表１３に示すフィルタを得るために７行７列の系を解く。
【００７５】
【表１２】
2006512799.tif 000070
【００７６】
【表１３】
2006512799.tif 000071
【００７７】
７：データを推定するためにフィルタを適用する。
【００７８】
消失画素の推定値を形成するためにフィルタを適用して消失画素を推定し、次の破損された画素に対して処理を継続する。ケース１では、推定値１１２．２５が得られる。ケース２では、推定値１２８．６９が得られる。
【００７９】
なお、ケース１において、センタータップは、既存の値が最大臨界値であることを意味する非常に大きな値を有する。センタータップは、既存の値が大きく変化しないようにしている。
【００８０】
図４に、ビデオ信号処理のために可能なアルゴリズムのフローチャート４００を示す。ビデオ信号の場合、動き、空間及びフィルタタップは、３次元で決定される。例えば、図３に示すタップを現フレーム及び前フレームに適用して３次元フィルタを形成することができる。
【００８１】
ブロック４０２（可能な動きクラスを決定する）の一例において、動きクラス候補の決定方法は、絶対画素差分（または、利用できる画素がなければ０）の平均の計算を含む。このケースでは、正確に動きクラス候補が常に１つはある。
【００８２】
ステップ４０２において、動きクラス候補を決定する。ステップ４０４において、可能な空間クラスを決定する。ステップ４０６において、ステップ４０２で決定された動きクラス候補及びステップ４０４で決定された空間クラス候補から可能なクラスを決定する。続いて、クラス候補（ステップ４０６において決定された）から供給された学習データをステップ４０８においてマージする。続いて、ステップ４１０において、フィルタを推定するための部分行列を抽出する。ステップ４１２でフィルタを形成し、ステップ４１４において適用する。
【００８３】
図５は、静止画処理に用いることが可能なアルゴリズムのフローチャート５００を示す。このケースでは、動きクラスを決定することなく、フィルタは２次元でのみ決定される。
【００８４】
ステップ５０２において、空間クラス候補を決定する。次に、クラス候補（ステップ５０２で決定された）から供給された学習データをステップ５０４においてマージする。ステップ５０６において、フィルタを推定するための部分行列を抽出する。ステップ５０８においてフィルタを形成し、ステップ５１０において適用する。
【００８５】
限られたリソースによる実施
十分な計算能力があれば、通常、可能な限り多くのタップを用いればよい。このためには、一実施の形態として、タップ配置候補の広範なドメインを最初に決定し、その後で使用するセットを選択してもよい（例えば、図３に示すように）。
【００８６】
消失画素データを推定するためのＫタップ推定フィルタを使用するに十分な計算能力があるとする。このとき、利用可能な全データから最も重要なＫタップを選択する。このためには、図３に示した順序に基づくフィルタタップに対して、使用可能な破損のないデータをチェックする。Ｋタップが選択されると、Ｒ及びｙの行に対応する行と列とを抽出する（上述した図５に示すように、フィルタ推定のための部分行列を抽出する）。
【００８７】
パラレルメモリの実施
この方法による多大な計算と各画素のエラー回復を分離することにより、単純な装置と実現可能な方法を有効に用いて大規模並列処理を実現することができる。例えば、一例として、高性能の格納領域を構築してもよい。この高性能の格納領域において、セルの各々は、上述の方法によってクラスＩＤの候補を特定することができる。処理は、共有のＲＯＭに格納された参照Ｒデータ及び参照ｙデータを出力することによって開始することができる。各セルは、自身の関心のと一致しているデータを保存することができる。また、これに独立して、各セルは、自身に対して最適フィルタの解を求めることができ、破損したデータを固定するために最適フィルタを適用することができる。そして、修正されたデータを外部に移し、破損された次の画像の一部分を中に移す。
【００８８】
以上のように、高エラーレート条件下の適応画素推定に対する方法及び装置について説明した。
【００８９】
図１は、説明してきた技術を適用可能なネットワーク環境１００を示したものである。図１に示すように、Ｓサーバ１０４−１〜１０４−Ｓ及びＣクライアント１０８−１〜１０８−Ｃの形態の幾つかのコンピュータシステムがネットワーク１０２を介して相互に接続されており、このネットワーク１０２は、例えば、家庭内ネットワークとすることもできる。また、ネットワーク１０２は、インターネット、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、衛星リンク、光ファイバネットワーク、ケーブルネットワーク又はこれらの組合せ、及び／又はその他との組合せのうちから少なくとも１つ以上を含むこともできる。サーバは、例えば、ディスク記憶装置としての役割のほか、記憶及び演算リソースとしての役割を果たすこともできる。同様に、クライアントが演算、記憶、及び表示能力を有することもできる。ここで説明した方法又は装置は、基本的には、ＬＡＮ、ＷＡＮ、システムバス等のように、局所的な通信又は遠隔通信に関わらず、あらゆる種類の通信手段又は装置に適用することができる。
【００９０】
図２は、コンピュータシステム２００のブロック図を示し、コンピュータシステム２００は、図１に示したクライアント及びサーバの典型例を示す。図２に示すコンピュータシステム２００は、高レベルの概念を表示しており、種々の方法、及び種々のアーキテクチャにより実現することができる。バスシステム２０２は、中央処理装置（ＣＰＵ）２０４、読出し専用メモリ（ＲＯＭ）２０６、ランダムアクセスメモリ（ＲＡＭ）２０８、ストレージ２１０、ディスプレイ２２０、オーディオ２２２、キーボード２２４、ポインタ２２６、その他の入出力（Ｉ／Ｏ）装置、及び通信装置２３０を相互に接続する。バスシステム２０２は、例えば、システムバスとして、周辺機器構成相互接続（Peripheral Component Interconnect：ＰＣＩ）、アドバンスドグラフィックポート（Advanced Graphics Port：ＡＧＰ）、小型コンピュータ用周辺機器インタフェース（Small Computer System Interface：ＳＣＳＩ）、ＩＥＥＥ１３９４（（Institute of Electrical and Electronics Engineers：ＩＥＥＥ）標準化番号１３９４（いわゆる、ファイアウォール（FireWire））、ユニバーサルシリアルバス（Universal Serial Bus：ＵＳＢ）等のうちの少なくとも１つとすることができる。ＣＰＵ２０４は、単一、複数又は分散処理演算リソースとすることができる。ストレージ２１０は、コンパクトディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ）、ハードディスク（ＨＤ）、光ディスク、テープ、フラッシュ、メモリスティック、ビデオレコーダ等とすることができる。ディスプレイ２２０は、例えば、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、プロジェクタ装置、テレビジョン受像機（ＴＶ）等とすることができる。なお、コンピュータシステムは、実装に応じて、図２中の構成の幾つか、全て、それ以上、又は再配置したものを含むことができる。例えば、薄型のクライアントは、例えば、一般的なキーボードをもたない無線携帯装置とすることもできる。したがって、図２のシステムについては、多くの変形例が可能である。
【００９１】
本発明を検討し、理解するという観点から、技術及び手法の記述のために、様々な用語が当業者により使用されていることを理解されたい。更に、明細書本文には、説明の目的で、本発明を十分に理解させるために数多くの固有の詳細例が示されている。しかし、当業者にとって、これらの特定の詳細な例がなくても本発明を実施できることは明白である。幾つかの事例においては、本発明を不明瞭にすることを避けるために、詳細ではなく、ブロック図の形で、公知の構造及び装置が示されている。これらの実施態様については、当業者が本発明を実施可能な程度に詳細な記述が行われており、その他の実施態様も利用可能であること、また、本発明の範囲を逸脱することなく、論理的、機械的、電気的、及びその他の変更を行うことができることは言うまでもない。
【００９２】
明細書の幾つかの部分は、例えば、コンピュータメモリ内のデータビットに関する演算のアルゴリズム及び記号表示により提示することもできる。これらのアルゴリズム記述及び表示は、データ処理の当業者が自らの仕事の内容をその他の当業者に伝達するための手段である。アルゴリズムは、ここではまた一般的に、所望の結果をもたらす一貫性のある一連のアクトであると考えられている。これらのアクトは、物理的数量の物理的操作を求めるアクトである。通常は、これらの数量は、記憶、転送、結合、比較、及びその他の操作が可能な電気又は磁気信号の形をとる。主として、共用という理由から、これらの信号をビット、値、エレメント、記号、文字、用語、数字等と呼ぶのが便利な場合もあることが明らかになっている。
【００９３】
なお、これらの用語及び類似の用語の全ては、適切な物理的数量と関連付けられており、それら物理的数量に適用される単なる便利な指標にすぎない。特別の断りがない限りは、記述全体を通じて、「処理」又は「演算」又は「計算」又は「決定」又は「表示」等のような用語を用いてされる説明は、コンピュータシステムのレジスタ又はメモリ内に物理的（電子的）数量として表示されたデータを操作し、コンピュータシステムのレジスタ又はメモリ、或いはその他のかかる情報ストレージ、伝送、或いは表示装置内に物理的数量として同様に表示されるその他のデータに変換するコンピュータ装置又は類似の電子演算装置の動作及び処理に対して言及したものである。
【００９４】
本発明は、この点で演算を行うための装置により実施することができる。この装置は、所要の目的のために特別に構成することもできるし、コンピュータ内に記憶されたコンピュータプログラムにより選択的に起動又は設定される汎用コンピュータであってもよい。このようなコンピュータプログラムは、フロッピーディスク、ハードディスク、光ディスク、コンパクトディスク読出し専用メモリ（ＣＤ‐ＲＯＭ）及び磁気光ディスクを含むあらゆるタイプのディスク、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、消去可能なプログラマブル読取専用メモリ（ＥＰＲＯＭ）、電気消去可能プログラマブル読取専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリ、磁気又は光カード等、又はコンピュータに対して局所的又はコンピュータに対して遠隔的に電子的命令を記憶するのに適したあらゆるタイプのメディアのようなコンピュータ読出し可能媒体に記憶することができるが、媒体はこれらの限定されるわけではない。
【００９５】
ここに提示したアルゴリズム及びディスプレイは何れかの特定のコンピュータ又はその他の装置と本質的に関連性を有するわけではない。様々な汎用システムをここにおける教示に従ってプログラムとともに使用することもできるし、所要の方法を実施するために専用の装置を構成するのが便利であることが明らかになることもある。例えば、汎用プロセッサのプログラミングにより、又はハードウェアとソフトウェアの任意の組合せにより、本発明による方法の何れもハードワイアードサーキットリで実施することができる。本発明は、携帯装置、マルチプロセッサシステム、マイクロプロセッサベース又はプログラマブル家電製品、デジタルシグナルプロセッサ（ＤＳＰ）、セットトップボックス、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ等を含めた、ここに記述した以外のコンピュータシステム構成により実施可能であることが、当業者には直ちに高く評価されよう。通信ネットワークを通じてリンクされている遠隔処理装置によりタスクが実行される分散コンピュータ環境においても、本発明は実施可能である。
【００９６】
本発明の方法は、コンピュータソフトウェアを使用して実施することもできる。承認された規格に適応するプログラミング言語により書かれている場合、多種多様なハードウェアプラットホーム上で実行するため、及び多種多様なオペレーティングシステムとのインタフェースのために、方法を実施するように設計された命令のシーケンスをコンパイルすることができる。それに加えて、本発明は、何れかの特定のプログラミング言語との関連で記述されているわけではない。ここに記述したような本発明の教示を実施するために、多種多様なプログラミング言語を使用することができる。更に、当然のことながら、ソフトウェアは、様々な形態（例えば、プログラム、プロシージャ、アプリケーション、ドライバ、・・・）でアクションを起こしたり、結果をもたらす。かかる表現は、コンピュータにより、ソフトウェアを実行することにより、コンピュータのプロセッサがアクションを行ったり、結果を作り出したりする、ということの省略表現であるにすぎない。
【００９７】
通信、プロトコル、アプリケーション、実装、メカニズム等を記述するために、様々な用語及び技術が当業者により使用されていることを理解されたい。かかる技術の１つは、アルゴリズム又は数式による技術の実装の記述である。すなわち、技術は、例えば、コンピュータによるコードの実行として実装することもできるが、一方、その技術の表現は、公式、アルゴリズム又は数式として、より適切かつ簡潔に伝達及び通信することもできる。したがって、当業者は、Ａ＋Ｂ＝Ｃを表示するブロックを、ハードウェア及び／又はソフトウェアにおけるその実装が２つの入力（Ａ及びＢ）をとり、加算出力（Ｃ）を作ることになる加法関数をして認識することになろう。したがって、記述としての公式、アルゴリズム又は数式の使用は、少なくとも（本発明の技術を実施することができるとともに、実施態様として実装することもできるコンピュータシステムのような）ハードウェア及び／又はソフトウェアの中に物理的実施態様を有するものとして理解するものとする。
【００９８】
機械読出し可能媒体は、機械（例えば、コンピュータ）による読出しが可能な形で情報を記憶又は伝送するためのあらゆるメカニズムを含むと理解される。例えば、機械読出し可能媒体としては、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記録媒体、光記録媒体、フラッシュメモリ装置、電気、光、音響又はその他の形態の伝播信号（例えば、搬送波、赤外線信号、デジタル信号等）等がある。
【００９９】
「可能な」クラス（単数又は複数）、クラス「候補」（単数又は複数）という言葉は、交換可能に使用されている。例えば、可能なクラスの決定は、クラス候補を決定することによって実行されてもよい。このように、クラス「候補」は、可能なクラスと考えてよい。
【０１００】
このように、高エラーレート条件下における適応画素推定方法及び装置について説明してきた。
【図面の簡単な説明】
【０１０１】
【図１】本発明の具体例として示す方法及び／又は装置におけるネットワーク環境を示す模式図である。
【図２】本発明の具体例として方法及び／装置においてコンピュータシステムの一実施の形態を示すブロック図である。
【図３】中央タップ近傍の画素を推定するときに各配置が重要であることを示すシーケンスにおいて番号付けされた学習タップ候補の一実施の形態を示す図である。
【図４】ビデオシステムにおいて破損した画素を回復するためのアルゴリズムを説明するフローチャートの一具体例である。
【図５】静止画像において破損した画素を回復するためのアルゴリズムを説明するフローチャートの一具体例である。
【国際調査報告】
2006512799.tif 000072