(57)【要約】      （修正有）【課題】非線形接近音に基づく推定値を用いる特異点係数の帯域間及び帯域内予測。【解決手段】ベクトルｘ＝[x0 x1]Tで表わされるオリジナル信号の一部分x1を推定又は予測するアルゴリズムは初期推定値y0＝[x0 0]T、オリジナル信号ｘの未知の部分であるx1の初期推定値を形成して推定値ｙ[推定値y]を得る。変換行列をy0に適用すると共に初期しきい値T0を用いて係数をハード・スレショルディングすることによってノイズ除去行列D1を計算する。第２の信号推定値y1を形成するのにD1を用いて処理が行なわれる。次のしきい値Tnを得るのにしきい値をΔTだけ逐次的にデクリメントすることができる。その後ynに変換行列を適用すると共にTnを用いて次のノイズ除去Dn+1が計算され、信号推定値ｙ(n+1)を形成するためにDn+1を用いて処理が実行される。信号推定値を形成するためにしきい値が逐次的に小さくなるこのループが最終しきい値Tfに到達するまで実行される。【選択図】図４
2005235169.tif 000002
【特許請求の範囲】
【請求項１】
信号推定値yを形成するための方法であって、推定の対象となる信号xは使用可能なサンプルをなす第１要素と欠けているサンプルを表わす第２要素とを含み、信号推定値yは第１要素と第２要素に欠けているサンプルの推定値を表わす推定要素とを含み、この方法は、
（ａ）初期信号推定値y0の中の推定要素の初期推定値を全てゼロに設定するステップと、
（ｂ）変換成分に基づいてノイズ除去行列Dn+1を計算するステップと、
（ｃ）y(n+1)が推定要素の欠けているサンプルの推定値に関する新たな情報を保有すると共に第１要素の使用可能なサンプルに関して既知の情報を保持するように次の信号推定値y(n+1)を形成するために１回からＣ回の範囲で計算されたノイズ除去行列Dn+1をynに適用するステップとを有し、ここでＣは１から２０の範囲内の自然数であり、
ステップ（ｂ）及び（ｃ）は、n = 0,. . .,Nの条件が満たされている間所定の回数（N + 1）繰り返し実行され、ここでnは自然数である、方法。
【請求項２】
ステップ（ｂ）の各ノイズ除去行列Dn+1の計算は、変換成分をynに適用することと、しきい値Tnを用いてynの係数をしきい値設定すること、逆変換成分を適用することとからなる、請求項１に記載の方法。
【請求項３】
次のノイズ除去行列Dn+1を計算する際にnがインクリメントされるたびにTnはデクリメントされる、請求項２に記載の方法。
【請求項４】
nがインクリメントされるたびにTnは固定量ΔTだけデクリメントされる、請求項３に記載の方法。
【請求項５】
変換成分は変換行列又はオーバーコンプリート変換集合からなる、請求項１に記載の方法。
【請求項６】
変換成分は各ノイズ除去行列Dn+1の計算で使用可能な第１要素のサンプルに関する情報に基づいて適応的に変わる、請求項１に記載の方法。
【請求項７】
各ノイズ除去行列Dn+1はynに適用されるとynの有意な成分だけを選択するように計算される、請求項１に記載の方法。
【請求項８】
Ｃは１から１０の範囲内の自然数である、請求項１に記載の方法。
【請求項９】
信号推定値yを形成するための装置であって、推定の対象となる信号xは使用可能なサンプルをなす第１要素と欠けているサンプルを表わす第２要素とを含み、信号推定値yは第１要素と第２要素に欠けているサンプルの推定値を表わす推定要素とを含み、この装置は、
下記を行なうように構成された１個以上のコンポーネント又はモジュールを有し、
初期信号推定値y0の中の推定要素の初期推定値を全てゼロに設定し、
変換成分に基づいてノイズ除去行列Dn+1を計算し、
y(n+1)が推定要素の欠けているサンプルの推定値に関する新たな情報を保有すると共に第１要素の使用可能なサンプルに関して既知の情報を保持するように次の信号推定値y(n+1)を形成するために１回からＣ回の範囲で計算されたノイズ除去行列Dn+1をynに適用し、ここでＣは１から２０の範囲内の自然数であり、
計算及び適用の操作は、n = 0,. . .,Nの条件が満たされている間所定の回数（N + 1）繰り返し実行され、ここでnは自然数である、装置。
【請求項１０】
１個以上のコンポーネント又はモジュールは次のうちの１個以上、つまり、プロセッサ、特定用途向け集積回路、又はデジタル信号プロセッサからなる、請求項９に記載の装置。
【請求項１１】
装置はコンピュータシステムである、請求項９に記載の装置。
【請求項１２】
機械に信号推定値yを形成するための方法を実行するように指図するための命令プログラムを有するデバイス可読媒体であって、推定の対象となる信号xは使用可能なサンプルをなす第１要素と欠けているサンプルを表わす第２要素とを含み、信号推定値yは第１要素と第２要素に欠けているサンプルの推定値を表わす推定要素とを含み、このプログラムは、
（ａ）初期信号推定値y0の中の推定要素の初期推定値を全てゼロに設定するための命令と、
（ｂ）変換成分に基づいてノイズ除去行列Dn+1を計算するための命令と、
（ｃ）y(n+1)が推定要素の欠けているサンプルの推定値に関する新たな情報を保有すると共に第１要素の使用可能なサンプルに関して既知の情報を保持するように次の信号推定値y(n+1)を形成するために１回からＣ回の範囲で計算されたノイズ除去行列Dn+1をynに適用するための命令とを有し、ここでＣは１から２０の範囲内の自然数であり、
ステップ（ｂ）及び（ｃ）は、n = 0,. . .,Nの条件が満たされている間所定の回数（N + 1）繰り返し実行され、ここでnは自然数である、デバイス可読媒体。
【請求項１３】
各ノイズ除去行列Dn+1を計算するための命令（ｂ）は、変換成分をynに適用するための命令と、しきい値Tnを用いてynの係数をしきい値設定するための命令と、逆変換成分を適用するための命令とからなる、請求項１２に記載のデバイス可読媒体。
【請求項１４】
各ノイズ除去行列Dn+1を計算するための命令（ｂ）はさらに、次のノイズ除去行列Dn+1を計算する際にnがインクリメントされるたびにTnをデクリメントするための命令からなる、請求項１３に記載のデバイス可読媒体。
【請求項１５】
命令（ｂ）は、nがインクリメントされるたびにTnを固定量だけデクリメントするように指定する、請求項１４に記載のデバイス可読媒体。
【請求項１６】
変換成分は変換行列又はオーバーコンプリート変換集合からなる、請求項１２に記載のデバイス可読媒体。
【請求項１７】
変換成分は各ノイズ除去行列Dn+1の計算で使用可能な第１要素のサンプルに関する情報に基づいて適応的に変わる、請求項１２に記載のデバイス可読媒体。
【請求項１８】
各ノイズ除去行列Dn+1はynに適用されるとynの有意な成分だけを選択するように計算される、請求項１２に記載のデバイス可読媒体。
【請求項１９】
Ｃは１から１０の範囲内の自然数である、請求項１２に記載のデバイス可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル信号（例えば、デジタル画像）から欠けている（missing）データを予測するための技法に関するものである。デジタル信号から欠けているデータを推定し、ノイズ除去（de-noise）し、或いは歪みを緩和したり、もしくは信号密度を向上させるのに予測法を用いることができる。該技法を方法／アルゴリズムとして採用することができ、そうした方法／アルゴリズムはソフトウェアで、ハードウェアで、或いはそれらの組合せで実施することができるし、コンピュータやその他のプロセッサ制御型デバイス上で実現しても構わない。
【背景技術】
【０００２】
ウェーブレット画像圧縮やその他の画像にウェーブレットを適用する際の重要な問題の一つは、エッジに対するウェーブレット係数の圧縮性である。１次元の区分的に滑らかな信号については、ウェーブレット表現と、それゆえにウェーブレットに基づく圧縮アプリケーションが局所特異点（localized singularities）に対して免疫性を有することを証明できる。しかしながら、２次元の区分的に滑らかな信号については、エッジは疎でないウェーブレット係数集合を生むことになり、圧縮性能は曲線に沿って現れる局所特異点によって左右されることが今では広く認識されている。研究者はこの問題を２つの主要な軌跡を系統的に追うことによって解決しようとしてきた。第一に、エッジに対するウェーブレット係数のモデル化を改善することによって、高位の統計的従属性を利用することができ、圧縮コーデックがそうした係数に使うビット数を減らすことができる。第２に、新たな表現及び変換を設計することによって、２次元の問題を、エッジが点の特異点に変換され、はるかに削減されたビット数で符号化される１次元のケースに変換することが可能になる。
【０００３】
「第１軌跡」手法は自然分割された（naturally decimated）ウェーブレット係数に作用するが、モデルを設計する際にエイリアシングの問題と戦わなければならない。関連して、「第２軌跡」により設計される最良の表現の主要なプロパティの中には変換／回転不変オーバーコンプリート変換を介してしか利用できないものがある。しかしながら、オーバーコンプリート変換を用いると、圧縮のジレンマが生じる。つまり、入力信号をオーバーコンプリート展開で先ず表現（符号化する情報量が著しく増える）してから、速度歪みの点で今日の先端技術のコーデックに劣らない圧縮ビットストリームを何とかして得なければならない。
【０００４】
【特許文献１】米国特許第６,６４３,４０６号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、先に説明した先行技術による手法の欠点を克服することである。
【０００６】
本発明のもう一つの目的は、先に説明した先行技術による手法の欠陥によって劣化しない、デジタル信号から欠けているデータを予測及び推定するための技法を提供することである。
【課題を解決するための手段】
【０００７】
一つの態様によれば、発明は信号推定値yを形成するための方法を提供しており、これにおいて、推定の対象となる信号xは使用可能なサンプルを構成する第１要素と欠けているサンプルを記述する第２要素とを含み、信号推定値yは第１要素と第２要素の中の欠けているサンプルの推定値を記述する推定要素とを含んでいる。この方法は、初期の信号推定値y0の中の推定要素の初期推定値を全てゼロに設定するステップと、変換成分に基づいてノイズ除去行列Dn+1を計算するステップと、y(n+1)が推定要素の欠けているサンプルの推定値に関する新たな情報を保有すると共に第１要素の使用可能なサンプルに関する既知の情報を保持するように次の信号推定値y(n+1)を形成するために１回からC回の範囲で計算されたノイズ除去行列Dn+1をynに適用するステップとを有し、ここでCは１から２０の間の自然数で、ステップ（ｂ）及び（ｃ）は、n = 0,. . .,Nの条件が満たされている間所定の回数(N + 1)繰り返し実行され、ここでnは自然数である。Cは１から１０の間であるのが好ましい。
【０００８】
ステップ（ｂ）における各ノイズ除去行列Dn+1の計算は、変換成分をynに適用し、しきい値Tnを用いてynの係数をしきい値設定し、逆変換成分を適用することからなるのが好ましい。好適な実施例で、次のノイズ除去行列Dn+1を計算する際にnがインクリメントされるたびにTnは固定量ΔTだけデクリメントされるのが好ましい。
【０００９】
変換成分は変換行列又はオーバーコンプリート集合からなって構わない。さらに、変換成分は各ノイズ除去行列Dn+1の計算において使用可能な第１要素のサンプルに関する情報に基づいて適応的に変わって構わない。
【００１０】
各ノイズ除去行列Dn+1はynに適用されるとynの有意な成分だけを選択するように計算されるのが好ましい。
【００１１】
他の態様において、発明は、方法のステップに関して先に説明した処理操作を実行するための一個以上のコンポーネント又はモジュールを含んだ装置を必要とする。そうしたコンポーネント／モジュールはハードウェア、ソフトウェア、それらの組合せで実現できる。一つの実現例は、例えば、マイクロプロセッサと、そのマイクロプロセッサが本発明のアルゴリズムを実装しているソフトウェアの管理の下で処理操作を実行するメモリアーキテクチャとを含んだコンピュータシステムを用いて実現可能である。代わって、処理操作を一個以上の特定用途向け集積回路（ＡＳＩＣ）、デジタル信号処理回路機構など、或いはそれらの組合せで実行することもできる。その他の実現例については、上記の説明に照らせば当業者ならば明白であろう。
【００１２】
発明の更なる態様によれば、上記の方法又はそのステップはどれでもコンピュータやその他のプロセッサ制御型デバイスに保持された或いはコンピュータやその他のプロセッサ制御型デバイスで伝えられる命令プログラム（例えば、ソフトウェア）として実施可能である。代わって、命令プログラムをステップの一つ以上を実行するように設計されたハードウェアと一体化させてもいい。そうしたハードウェアとしては、例えば、一個以上のＡＳＩＣ、デジタル信号処理回路機構などがある。
【００１３】
添付の図面と共に以下に述べる説明並びに特許請求の範囲を読めば、発明をより深い理解できるようになるし、発明のその他の目的及び成果が明白になるし評価できるだろう。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施形態を図面に基づいて説明する。
【実施例１】
【００１５】
Ａ．概要
本発明は主として、変換不変オーバーコンプリート表現を用いてウェーブレットエッジ係数を予測するデータ予測及び推定技法に関するものである。すなわち、特異点に対してウェーブレット係数の高位な統計的従属性を判定するのにオーバーコンプリート表現をウェーブレット領域で用いる。レベルlのウェーブレット分解を最低周波数帯域から始めることによって、本発明の技法は区分的に滑らかな信号に対して欠けている高周波数係数を確実に推定するように設計されている。特異点を直接モデル化しようとする既存のテクノロジーと違って、本発明の技法は、疎なオーバーコンプリート分解を用いて、「非特異点」に対して効果のある単純且つロバストなモデルを形成する。すなわち、本発明の技法は、エッジを直接モデル化せずに、むしろ、領域を積極的に判定することによって境界／エッジを陰に（implicitly）得る。そうした場合、活用された変換不変分解は疎である。
【００１６】
問題の信号に対して疎な分解を提供するであろう局所線形変換（localized linear transforms）のオーバーコンプリート集合があるとして、つまり、変換は多数の小さな（small-magnitude）係数を生み出すものとして、信号に対してこれらの変数を適用し、変換ごとに無意味な係数集合をゼロにしきい値設定されたそれらの係数のインデックスとして適応的に判定するために、結果として生じた変換係数をハード・スレショルディングする（hard-threshold）。この集合は疎性制約条件（sparsity constraints）を確立するのに使用され、疎性制約条件はウェーブレット係数の高位従属性を推定するのに用いられる。オーバーコンプリートな局所変換は各々が「疎な領域」と特異点を含む領域とを有し、前者の場合には疎な係数集合を生み、後者の場合には疎性を生むことができない。本発明の技法は、総体的推定値を形成する際に各変換の疎な領域を適応的に判定及び優先する。興味深いのは、この疎な領域の積極的な判定は境界を形成するエッジを正確に判定できることである。非線形接近音（approximants）を使用する本発明の技法は、図１に表示されているパイプラインで（変換及びしきい値の集合があるとして）推定値を得る。観察した信号１０１から、無意味な係数集合１０２を得て、その次に疎性制約条件１０３が与えられ、そこから信号の非線形接近音１０４を得て、最終的に推定値１０５を生じる。
【００１７】
プロセスは、低周波数ウェーブレット係数だけ（２次元のレベルlのウェーブレット変換の最低周波数帯域だけ）を含んだ信号の観察から始まる。残りの係数は欠けているデータとして取り扱われる。本発明の技法は次に、「欠けている」高周波数係数を予測するために適用される。この大まかな予測は、例えば、符号化の対象となる次の係数の確率モデルを判定するために予測を実行し、ＤＰＣＭタイプの符号化を用いるウェーブレット圧縮コーデックの一部として、又は、復号化された情報がある場合後処理を行なうウェーブレット・デコーダの一部として、様々なアプリケーションに使用可能である。そのために、本発明のアルゴリズムは、全部設計し直さなくても今日の圧縮コーデックと簡単に組み合わせることができる。同様に、この発明はエッジに対して欠けている高周波数ウェーブレット係数の予測を可能にするから、欠けている解像度を予測して信号密度を高めるために用いることもできる。
【００１８】
区分的に滑らかな信号に関して、使用可能なデータがあるとすると共に（疎性制約条件により確立されているように）信号の一定の部分が滑らかであると確信するとして、本発明の技法は欠けているデータについて非常の優れた推定値を提供する。
【００１９】
発明についての更なる詳細を以下に説明する。
【００２０】
Ｂ．推定のフレームワークとアルゴリズム
2005235169.tif 000003
2005235169.tif 000004
【００２１】
2005235169.tif 000005
【００２２】
2005235169.tif 000006
2005235169.tif 000007
【００２３】
2005235169.tif 000008
2005235169.tif 000009
【００２４】
2005235169.tif 000010
【００２５】
Ｄ．インプリメンテーションとアプリケーション
図９に示すのは、本発明の処理を実行するのに使用可能な模式的システム１００である。図９に示すように、システムには計算資源を提供すると共にコンピュータを管理する中央処理機構（ＣＰＵ）がある。ＣＰＵ１０１はマイクロプロセッサなどで実現できるし、グラフィックスプロセッサを含むと共に／又は数学計算できるように浮動小数点プロセッサを含んでいて構わない。システム１００はさらにシステムメモリ１０２を含み、システムメモリ１０２はランダムアクセスメモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）といった形式で構わない。システムメモリはプログラムの実行時に本発明のアルゴリズムをインプリメントするプログラムを格納するのに使用できるし、入力データ、出力データ、及び／又は中間結果を格納するのにも使用できる。
【００２６】
システム１００は、適したコントローラを装備した様々な周辺コンポーネントを含んでいるか、又はそうしたコンポーネントと通信可能である。例えば、発明の通りにシステム１００で処理される画像を含んだドキュメントをデジタル化するのにスキャナ又はスキャナと同等の装置を用いることができる。処理の対象となる信号は何らかの適したやり方でシステム上で生成されても、システムにインポートされても構わない。例えば、オーディオやビデオなど、他のタイプのデジタル信号も任意の適したやり方でインポートされても構わない。システム１００は、データを操作しやすくするために、キーボード、マウス、及び／又はスタイラスなど、様々なオペレータ入力装置１０３を含んでいるのが好ましい。
【００２７】
オペレーティングシステム、ユーティリティ、及びアプリケーションの命令プログラムを記録するのに磁気テープやディスク又は光媒体といった記憶媒体を各々含んだ一つ以上の記憶装置を用いてもいい。そうした命令プログラムは本発明の様々な態様を実現するプログラムの実施例を含んでいるかもしれない。任意の既知のタイプのディスプレイ１０５を含んでいてもいい。
【００２８】
発明通りに信号を処理したら、適切な装置に出力して構わない。例えば、発明の通りに処理された画像を含んだドキュメントをプリンタに出力してもいい。
【００２９】
通信装置１０６によりシステム１００は、インターネット、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）など様々なネットワークのどれかで、或いは赤外線信号など任意の適した電磁搬送波信号により、遠隔装置に接続できるようになる。
【００３０】
例を挙げて説明したシステムにおいて、全ての主要なシステムコンポーネントはバス１０７に接続しており、バス１０７は一本以上の物理的バスを表わしているかもしれない。しかしながら、様々なシステムコンポーネントは互いに物理的に近接しているかもしれないし、近接していないかもしれない。例えば、入力データ及び／又は出力データは一ヶ所の物理的な場所から別の場所に遠隔伝送されるかもしれない。また、本発明の様々な態様を実現するプログラムはネットワークで遠隔場所（例えば、サーバ）からアクセスできるかもしれない。磁気テープやディスク又は光ディスク、ネットワーク信号、或いは赤外線信号などその他の電磁搬送波信号など多種多様な機械可読媒体のどれかによりそうしたデータ及び／又はプログラムを伝達しても構わない。
【００３１】
本発明はソフトウェアで実現するのが便利かもしれないが、ハードウェア実現又はハードウェア・ソフトウェアを組み合わせた実現も可能である。ハードウェア実現は、例えば、ＡＳＩＣ、デジタル信号処理回路機構などを用いて実施することができる。従って、「デバイス可読媒体」というクレーム表現は、ソフトウェア実装媒体だけでなく、必要な処理を実行するための命令がハードワイヤされたハードウェア及びハードウェア・ソフトウェアの組合せも含むものである。同様に、「命令プログラム」というクレーム表現はソフトウェアだけでなくハードウェアに実装された命令も含むものである。また、装置クレームの中で言及しているコンポーネントには任意のデバイス又は請求している操作を実行可能なデバイスの組合せも含まれる。そうしたデバイスには、命令ベースのプロセッサ（例えば、ＣＰＵ）、ＡＳＩＣ、デジタル処理回路機構、それらの組合せなどがある。これらのインプリメンテーションの変形例に照らせば、図面やそれにつけた説明は当業者がプログラムコード（つまり、ソフトウェア）を書いたり、必要な処理を実行するための回路（つまり、ハードウェア）を作るのに必要な機能的情報を提供していると考えるべきである。
【００３２】
上記の説明が実証しているように、本発明は疎な分解を可能にする変換を用いてデジタル信号から欠けているデータを予測及び推定するためのソフトウェアベースの又はハードウェアベースのアルゴリズム・技法を提供している。これらのアルゴリズムは、ビデオ、静止画像、オーディオ（音声、音楽など）の各信号など任意のデジタル信号に適用可能である。予測及び推定にはネットワーク伝送、ダメージを受けた画像の復元、スクラッチの除去などに起因するエラー修正が含まれる。本発明のアルゴリズムを用いてデジタル信号からノイズを除去すると共に／又は信号密度を高めることもできる。
【００３３】
発明をいくつかの具体的な実施例と共に説明してきたが、更なる変形例、修正例、変更例、応用例は上記の説明に照らせば当業者ならば明白だろう。従って、本書で説明した発明は、添付の特許請求の範囲及び精神から逸脱しない限りにおいて全てのそうした変形例、修正例、変更例、応用例を網羅するつもりである。
【図面の簡単な説明】
【００３４】
【図１】（変換及びしきい値の集合が与えられているとして）非線形接近音を用いる本発明の技法が推定値を生むに至る基本のパイプラインを図解しているフロー図。
【図２】「２サンプル」信号に対する非線形近似の疎なクラスを説明しており、非線形近似法のクラスが星型集合として描かれている。
【図３】「２サンプル」信号に対する疎な復元を説明している。
【図４】本発明の実施例による主アルゴリズムの基本的なプロセスの流れを説明しているフローチャート。
【図５】オリジナルグレースケールテスト画像を示したもので、左から右に、急須（1280 x 960）、グラフィックス（512 x 512）、気泡（512 x 512）、レナ（512 x 512）。
【図６】l = 1とした場合のテスト画像のピーク信号対雑音（PSNR）対しきい値曲線。
【図７】l = 2とした場合のテスト画像のピーク信号対雑音（PSNR）対しきい値曲線。
【図８】急須、気泡、レナからの処理された画像の一部。
【図９】本発明の技法を実施するのに使用可能な模式的システムを示すブロック図。
【符号の説明】
【００３５】
2005235169.tif 000011
【図１】
2005235169.tif 000012
【図２】
2005235169.tif 000013
【図３】
2005235169.tif 000014
【図４】
2005235169.tif 000015
【図６】
2005235169.tif 000016
【図７】
2005235169.tif 000017
【図９】
2005235169.tif 000018
【図５】
2005235169.tif 000019
【図８】
2005235169.tif 000020