(57)【要約】【課題】本発明の実施形態は、雑音誘導プロセス（１０４）、デバイス、及び媒体により汚染された元の清浄信号（１０２）と等しい又は近似した清浄化信号（１１０）を、雑音汚染信号（１０６）から回復するための一般的に適用可能な雑音除去方法及びシステムを対象とする。【解決手段】第１パスにおいて、本発明の方法の実施形態及びシステムの実施形態は、多くの異なるタイプの近傍ルール（２０２、２０４、２０６；２０６及び２０８〜２１２）の内のインスタンスを受信し、受信した近傍ルールを使用して雑音含有信号から統計値（８２０）を収集する。第２パスでは、本発明の方法の実施形態及びシステムの実施形態は、多くの異なるタイプの雑音除去ルールの内のインスタンスを受信し、清浄化信号を生成するために、受信した雑音除去ルールを使用して、受信した雑音含有信号から雑音を除去する。【選択図】図８
2010534972.tif 000002
【特許請求の範囲】
【請求項１】
雑音汚染信号（１０６）を再構成して清浄化信号（１１０）を生成するための方法であって、
雑音汚染信号、雑音除去ルール、及び近傍ルール（２０２、２０４、２０６；２０６及び２０８〜２１２）を受信すること；
第１パスにおいて、
各雑音汚染信号成分（８０４）に近傍ルールを適用して雑音汚染信号成分に関する近傍（８０８）を発生すること及び等価な近傍（８１１、８１２，８１４）を有するその他の雑音汚染信号成分に基づいて雑音汚染信号成分に関する統計値（８２０）を収集すること；及び
第２パスにおいて、
第１パスにおいて前記記号に関して収集した統計値を使用して、各雑音汚染信号成分に雑音除去ルールを適用し、対応する清浄化信号成分を発生すること；
を備えることを特徴とする方法。
【請求項２】
雑音汚染信号（１０６）及び清浄化信号（１１０）は両方とも記号の順序付けられた配列であり；
各雑音汚染信号の記号は、濃度｜Ａ1｜＝ｋの記号のアルファベットＡ1（１１２）から選択され、各清浄化信号記号は、濃度｜Ａ2｜＝ｍの記号のアルファベットＡ2から選択され；
各雑音汚染信号成分及び清浄化信号成分は、１個以上の記号からなり；且つ
雑音汚染信号は、
通信媒体を通る送信、
信号格納デバイス内への格納、及び
信号処理システムによる処理
の１個以上によって汚染されることを特徴とする、請求項１に記載の方法。
【請求項３】
雑音汚染信号成分の近傍（８０６）は、雑音汚染信号から選択された１個以上の追加の雑音汚染信号成分を備え；且つ
雑音汚染信号から選択された前記１個以上の追加の雑音汚染信号成分を特定する近傍ルール（２０２、２０４、２０６）は、
近傍を定義する雑音汚染信号成分の位置に関連する近傍を定義する位置のリスト、及び
近傍を定義する雑音汚染信号成分の位置に関連する雑音汚染信号成分の位置を計算する計算方法
の１個以上を備えることを特徴とする、請求項１に記載の方法。
【請求項４】
近傍は、ｌ次近傍（５０２、５０７〜５１１）として特定され、ｌ次近傍の雑音汚染信号成分の位置は、
近傍ルールを適用して雑音汚染信号成分の位置（５０２、５０３）の集合を発生し、且つ
雑音汚染信号成分の位置の集合に、近傍ルールを連続的にｌ−１回適用して、雑音汚染信号成分の位置の集合に追加される追加的な雑音汚染信号成分の位置を発生すること、によって得られ；
第１及び第２の近傍が、関連する雑音汚染信号成分の位置（７０４、７０６、７０８、７１０、７１４、７１６、７１８、７２０）の同一の集合から構成され、且つ各関連する雑音汚染信号成分の位置に関して、同じ種類の雑音汚染信号成分が、第１及び第２の近傍を定義する位置に関して関連する雑音汚染信号成分の位置で発生する時、第１の近傍を定義する位置（７０２）の第１の近傍は、第２の近傍を定義する位置（７１２）の第２の近傍に等しく；
計数ベクトル（９０４）は、各雑音汚染信号成分（９０２）に関連し、計数ベクトルは、雑音汚染信号成分の全ての可能な種類に関する計数を含み；且つ
等価の近傍を有するその他の雑音汚染信号成分に基づいて、現在考察されている雑音汚染信号成分に関する統計値を収集することは、更に、現在考察されている雑音汚染信号成分の近傍と等価な近傍を有する各その他の雑音汚染信号成分に関し、その他の雑音汚染信号成分の種類に対応する計数ベクトルの計数をインクリメントすることからなる、ことを特徴とする請求項３に記載の方法。
【請求項５】
雑音除去システムを生じるプロセス又はデバイスに含まれる請求項１に記載の方法であって、当該プロセス又はデバイスは：
コンピュータシステム；
データ送信機；
データ受信機；
プリンタ；
スキャナ；及び
通信制御装置を含むことを特徴とする、方法。
【請求項６】
雑音汚染信号（１０６）を再構成して清浄化信号（１１０）を生成するシステムであって：
雑音除去ルールを受信し、
近傍ルール（２０２、２０４、２０６；２０６及び２０８〜２１２）を受信し、
第１パスにおいて、
各雑音汚染信号成分（８０４）に近傍ルールを適用して雑音汚染信号成分に関する近傍（８０８）を発生し、等価の近傍（８１１，８１２，８１４）を有するその他の雑音汚染信号成分に基づき雑音汚染信号成分に関する統計値を収集し、且つ
第２パスにおいて、
第１パスにおいて記号に関して収集された統計値を使用して、各雑音汚染信号成分に雑音除去ルールを適用し、対応する清浄化信号成分を発生することを備えるシステム。
【請求項７】
雑音汚染信号（１０６）及び清浄化信号（１１０）は両方とも記号の順序付けられた配列であり；
各雑音汚染信号の記号は、濃度｜Ａ1｜＝ｋの記号のアルファベットＡ1（１１２）から選択され、各清浄化信号の記号は、濃度｜Ａ2｜＝ｍの記号のアルファベットＡ2から選択され；
各雑音汚染信号成分及び清浄化信号成分は、１個以上の記号を備える、請求項６に記載のシステム。
【請求項８】
雑音汚染信号成分の近傍（８０６）は、雑音汚染信号から選択された１個以上の追加の雑音汚染信号成分からなり；且つ
雑音汚染信号から選択された前記１個以上の追加の雑音汚染信号成分を特定する近傍ルール（２０２、２０４、２０６）は、
近傍を定義する雑音汚染信号成分の位置に関連する近傍を定義する位置のリスト、及び
近傍を定義する雑音汚染信号成分の位置に関連する雑音汚染信号成分の位置を計算する計算方法
の１個以上を備える、請求項６に記載のシステム。
【請求項９】
近傍は、ｌ次近傍（５０２、５０７〜５１１）として特定され、ｌ次近傍の雑音汚染信号成分の位置は、
近傍ルールを適用して雑音汚染信号成分の位置（５０２、５０３）の集合を発生し、且つ
雑音汚染信号成分の位置の集合に、近傍ルールを連続的にｌ−１回適用して、雑音汚染信号成分の位置の集合に追加される追加的な雑音汚染信号成分の位置を発生すること、によって得られ；且つ
第１及び第２の近傍が、関連する雑音汚染信号成分の位置（７０４、７０６、７０８、７１０、７１４、７１６、７１８、７２０）の同一の集合から構成され、且つ各関連する雑音汚染信号成分の位置に関して、同じ種類の雑音汚染信号成分が、第１及び第２の近傍を定義する位置に関して関連する雑音汚染信号成分の位置で発生する時、第１の近傍を定義する位置（７０２）の第１の近傍は、第２の近傍を定義する位置（７１２）の第２の近傍に等しい請求項８に記載のシステム。
【請求項１０】
計数ベクトル（９０４）は、各雑音汚染信号成分（９０２）に関連し、計数ベクトルは、雑音汚染信号成分の全ての可能な種類に関する計数を含み；且つ
等価の近傍を有するその他の雑音汚染信号成分に基づいて、現在考察されている雑音汚染信号成分に関する統計値を収集することは、更に、現在考察されている雑音汚染信号成分の近傍と等価の近傍を有する各その他の雑音汚染信号成分に関し、その他の雑音汚染信号成分の種類に対応する計数ベクトルの計数をインクリメントすることからなる、請求項６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理及び信号処理に関し、特に、雑音によって汚染され信号から雑音を除去するための一般的に広く適用可能な方法及びシステムに関する。
【背景技術】
【０００２】
多くの異なるアプリケーション、コンピュータ環境、システム環境、及び問題領域において、雑音汚染信号（noise-corrupted signals）から雑音を除去するための、多くの様々な技術が現在適用されている。例えば、多くの通信システムでは、雑音を誘導するチャネルを介してのデジタル符号化信号の送信が、該信号の雑音汚染を招く可能性があり、その信号には、雑音を誘導するチャネルを介する送信に供された元のデジタル符号化信号をできる限り厳密に再生するために、雑音除去方法が適用される。雑音を誘導するチャネルには、電子通信媒体、多くの異なるタイプの計算プロセス、及び多種多様な異なるタイプのデータ記憶デバイス、データレンダリングデバイス、データ送信デバイス、データ収集デバイス、及びデータ処理デバイスが含まれる。一例として、電子メモリに格納されたデータは、宇宙放射線、静電気放電、及び電子メモリに入力される信号線上の電圧変動により汚染を被る。電子メモリから取り出されたデータは、結果として、格納のために電子メモリに初めに供されたデータと異なる可能性がある。他の例として、電子通信媒体を介して送信されたデータは、隣接する通信チャネルからの電子干渉によって、あるいは、通信媒体のリピータ及びその他のハードウェアコンポーネントにおける散発的故障によって、さらには、多くのその他のタイプの雑音導入事象によって汚染される可能性がある。その結果、送り先の受信機に受信された信号は、送信機を介して通信媒体へ最初に入力された信号と著しく異なる可能性がある。
【０００３】
しかしながら、雑音を誘導するチャネルには、情報を変形又は変化する非常に多くのその他のタイプの現象が含まれる可能性がある。例えば、ランダムプロセスによる遺伝子のヌクレオチド配列における変化は、祖先ＤＮＡ配列からなる信号に導入された雑音と見なされる可能性があり、また、蛋白質を符号化する遺伝子における変化から生じる蛋白質の立体構造における僅かな変化、又は遺伝子を含む染色体の関連調節領域における変化でさえ、蛋白質を符号化する遺伝子を含む染色体ヌクレオチド配列に導入された雑音から生じたとものと見なされる可能性がある。科学的且つ経済的観察から集められた多くのタイプのデータも、観察を記録することによって、観察法によって、及び観察された事象を符号化して格納することによって導入された雑音の結果として予期又は所望されるだろう記号の配列とは異なる記号の配列として符号化された情報として見なされる可能性がある。「雑音汚染（された）」ということばは、必ずしも、雑音が侵入する過程が不自然であるということを示唆したり、又は信号の劣化又は悪化を意味するものではなく、単に初期信号が何らかの理由で変化又は変形されたことを意味する。ランダムプロセスによるゲノム変異の場合には、この変化は、変化した遺伝子配列を有する有機体にはかなり好都合であるかもしれない。例えば、細菌宿主は、祖先配列に関して雑音と見なされる変異体を有し、それによって細菌宿主が抗菌化学処理、抗生物質、及びファージによる感染から生き延びる可能性がある。
【０００４】
異なるタイプの信号及び信号送信デバイス及び媒体が遭遇する多くの雑音の原因を認識し且つ対処するために多くの異なる技術が採用されている。例えば、エラー検出及びエラー訂正の両方用に信号に格納された冗長情報を使用して、ある種のデータ及び信号の汚染を検出し且つ汚染から回復するために、エラー訂正符号を採用することができる。加えて、多くの信号送信関連のプロトコル、データ格納初期化規則、及び他の信号符号化規則を、信号に導入された雑音の全体的影響を改善するように設計し、それによってあるエラーの影響が局所的に抑制され、ひいては信号全体の汚染に繋がらないようにしている。一例として、ビデオ信号のＭＰＥＧ符号化は、基準フレーム間に送信されるより複雑で一時的に符号化されたフレーム用の基準点として働く先行又は後続フレームへの依存が無い、基準フレームの頻繁な送信を使用する。従って、１個以上の一時的に符号化されたフレームにおけるエラーは、後続の全フレームに影響を与える可能性がなく、最大でも次に送信された基準フレームまでの後続フレームにしか影響を与えない。その他の技術は、元々送信又は格納された信号にできるだけ近似した信号を生成するために、受信又は回復された信号のどの部分が汚染したのかを推測するため、及び前記受信又は回復された信号に当てはまる汚染を推測するために、信号の目的地又は信号回復地点での、元々送信された信号のある特徴の知識に依存している。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
多くの雑音除去技術は、アルゴリズムが複雑であり、また、特定の問題領域、特にリアルタイムの問題領域に適用される場合にはコンピュータ的に扱い難い可能性がある。多くの雑音除去技術は、雑音除去方法及びシステムが適用される多くの種類の雑音除去関連の問題領域の比較的狭い部分にしか適用できない可能性があり、特定の雑音除去方法の適用可能性を決定する基準が複雑になる可能性がある。これらの理由から、情報科学者、コンピュータ科学者、及び多種多様な異なる情報送信媒体、プロセス、デバイス、及び情報処理ソフトウェア及びハードウェアの設計者、製造販売者、及びユーザは、単純で、計算効率が良く、一般的に適用可能な雑音除去方法の必要性を認識し続けている。
【課題を解決するための手段】
【０００６】
本発明の実施形態は、１個以上の雑音誘導プロセス、デバイス、又は媒体により汚染を被った、元の清浄信号（ｃｌｅａｎ ｓｉｇｎａｌ）と等しい又はそれに近い清浄化信号（ｃｌｅａｎｅｄ  ｓｉｇｎａｌ）を、雑音汚染信号（ｎｏｉｓｅ−ｃｏｒｒｕｐｔｅｄ  ｓｉｇｎａｌ）から回復させるための一般的に適用可能な雑音除去方法及びシステムに関する。第１パスにおいて、本発明の方法の実施形態及びシステムの実施形態は、多くの異なるタイプの近傍ルールの内のインスタンスを受信し、受信した近傍ルールを使用して雑音含有信号（ｎｏｉｓｙ  ｓｉｇｎａｌ）から統計値を収集する。第２パスでは、本発明の方法の実施形態及びシステムの実施形態は、多くの異なる種類の雑音除去ルールの内のインスタンスを受信し、受信した雑音除去ルールを使用して、清浄化信号を生成するために、受信した雑音含有信号から雑音を除去する。
【図面の簡単な説明】
【０００７】
【図１】本発明の方法の実施形態及びシステムの実施形態が対象とする、一つの一般的な問題領域、及び当該一般的な問題領域に関する表記法を示す。
【図２Ａ】記号配列Ｓの特定の記号Ｓｃに関して定義された多くの異なる近傍を示す。
【図２Ｂ】記号配列Ｓの特定の記号Ｓｃに関して定義された多くの異なる近傍を示す。
【図２Ｃ】記号配列Ｓの特定の記号Ｓｃに関して定義された多くの異なる近傍を示す。
【図３Ａ】線形記号配列内の記号のより高次の組織を示す。
【図３Ｂ】線形記号配列内の記号のより高次の組織を示す。
【図４Ａ】記号配列が１次元の線形配列として表わされる時の図３Ａ乃至図３Ｂに示す４個の近傍を示す。
【図４Ｂ】記号配列が１次元の線形配列として表わされる時の図３Ａ乃至図３Ｂに示す４個の近傍を示す。
【図４Ｃ】記号配列が１次元の線形配列として表わされる時の図３Ａ乃至図３Ｂに示す４個の近傍を示す。
【図４Ｄ】記号配列が１次元の線形配列として表わされる時の図３Ａ乃至図３Ｂに示す４個の近傍を示す。
【図５Ａ】１次近傍からの３次近傍の生成を示す。
【図５Ｂ】１次近傍からの３次近傍の生成を示す。
【図５Ｃ】１次近傍からの３次近傍の生成を示す。
【図６Ａ】１次近傍からの３次近傍の生成を示す。
【図６Ｂ】１次近傍からの３次近傍の生成を示す。
【図６Ｃ】１次近傍からの３次近傍の生成を示す。
【図７】近傍対を示す。
【図８】本発明のシステムの実施形態によって使用され、且つ本発明の方法の実施形態が対象とする一般的な雑音除去方法を示す。
【図９】本発明のシステムの実施形態によって使用され、且つ本発明の方法の実施形態が対象とする一般的な雑音除去方法を示す。
【発明を実施するための形態】
【０００８】
本発明の実施形態は、共通の計算方式を共有する比較的単純で、多くの場合に計算効率が良く、広範囲に適用可能な雑音除去方法及びシステムからなる大きな一群を対象とする。以下の第１小節では、一般的な問題領域、及びその問題領域に関連する表記法について図１を参照して論じる。次小節では、近傍の概念及び近傍構造について図２Ａ乃至図７を参照して論じる。第３小節では、近傍に基づく統計値収集について図８及び図９を参照して論じる。第４小節では、本発明の一方法実施形態のＣ＋＋のような疑似コード実施を提供する。最後に、第５小節では、特定の問題領域に対する本発明の様々な異なる応用について論じる。
【０００９】
（一般的な問題領域）
図１は、本発明の方法の実施形態及びシステムの実施形態が対象とする、一つの一般的な問題領域、及びその一般的な問題領域に関連する表記法を示す。非常に多数の異なる種類の特定の問題が、本小節で示す一般的な問題領域に含まれること、及び、ここで記述される問題領域を例外として含む更に多くの一般的な問題領域が存在することに留意すべきである。第１に、清浄信号１０２、原則的に、記号のベクトル又は１次元アレイＸであるが、ある種の雑音を導入するプロセス、媒体、又はデバイスにさらされる（１０４）。雑音導入によって、記号の第２のベクトルＺとして示す、雑音含有信号１０６を生じる。次に、雑音含有信号Ｚに、本願発明の範囲に含まれる多くの特定の雑音除去方法及びシステムの一つを適用し（１０８）、記号の第３ベクターＸ'として示す、雑音除去された（Ｄｅｎｏｉｓｅｄ）信号即ち清浄化（Ｃｌｅａｎｅｄ）信号１１０を生成する。各信号Ｘ、Ｚ、及びＸ'は、記号の順序付けられた配列からなり、各記号は、濃度｜Ａ｜＝ｋの周知の固定長アルファベットＡ１１２から選択される。従って：
Ａ＝［ａ1，ａ2，…，ａk］
Ｘ＝［ｘ1，ｘ2，…，ｘn］ここでｘi∈Ａ
Ｚ＝［ｚ1，ｚ2，…，ｚn］ここでｚi∈Ａ
Ｘ'＝［ｘ'1，ｘ'2，…，ｘ'n］ここでｘ'i∈Ａ
【００１０】
本発明の実施形態の多くにおいて、全３つの信号Ｘ，Ｚ，及びＸ'の長さは、全て一つの固定整数ｎに等しい。従って、本発明の実施形態の多くは、清浄信号の記号が雑音含有信号の記号へ変換され、その雑音含有信号のある記号が、雑音除去プロセスによって、雑音除去された信号の対応する記号へ変換される雑音除去問題を対象とする。記号変換プロセスが閉じられており、雑音を誘導する記号変換及び雑音を除去する記号変換の両方ともがアルファベットＡから選択される有効記号を生成する。加えて、本発明の多くの実施形態が適用される問題領域において、記号は、雑音誘導プロセス中及び雑音除去プロセス中のいずれにおいても、失われたり追加されたりすることもない。その他のある問題領域では、閉じた変換及び記号の無損失・無追加という制約の両方又はいずれかが緩和される可能性がある。更に多くの一般的な問題領域では、清浄信号、雑音含有信号、及び雑音が除去された信号Ｘ，Ｚ，及びＸ'は、１個のアルファベットよりもむしろ２個又は３個のアルファベットから選択された記号を含み、その２個又は３個のアルファベットは互いに完全に異なるのでも又は重複するのでもよく、互いに異なる濃度を有してもよい。従って、より一般的な場合では：
Ａ1＝［ａ11，ａ12，…，ａ1k］
Ａ2＝［ａ21，ａ22，…，ａ2l］
Ａ3＝［ａ31，ａ32，…，ａ3m］
｜Ａ1｜＝ｋ
｜Ａ2｜＝ｌ
｜Ａ3｜＝ｍ
Ｘ＝［ｘ1，ｘ2，…，ｘn］ここでｘi∈Ａ1
Ｚ＝［ｚ1，ｚ2，…，ｚn］ここでｚi∈Ａ2
Ｘ'＝［ｘ'1，ｘ'2，…，ｘ'n］ここでｘ'i∈Ａ3
【００１１】
（近傍及び近傍構造）
図２Ａ乃至図２Ｃは、記号配列Ｓの特定の記号Ｓｃに関して定義される多くの異なる近傍を示す。図２Ａは、記号Ｓｃ２０６に関して対称的な密集した近傍２０２及び２０４を示す。近傍は、近傍ルールによって特定の近傍定義位置に対する近傍位置として定義された記号配列内の１個以上の位置の集合である。近傍ルールは、記号配列における任意の指定の記号位置ｃに適用され、近傍定義記号位置に関して近傍位置Ｎ（ｃ）を発生する。図２Ｂは、記号Ｓｃ２０６に関して定義される非対称で疎な近傍２０８乃至２１２を示す。図２Ｃは、記号Ｓｃ２０６に関する更に他の近傍２１６乃至２１９を示す。
【００１２】
記号配列内の特定の記号位置に適用される近傍ルールは、近傍ルールが適用される記号に対して０，１，…，ｎＭａｘ個の記号位置の集合を発生することができ、ｎＭａｘは近傍ルールによって発生する近傍位置の最大数である。ある定義によれば、近傍ルールは常に固定数ｎＭａｘの近傍位置を発生することができ、一方で他の定義によれば、近傍定義位置ｃに対する近傍Ｎ（ｃ）において近傍ルールによって発生する位置の数は変化してもよい。近傍ルールは、決定論アルゴリズム又はパラメータ化方程式でよく、或いは、単に、記号配列内の近傍定義記号位置の指数又は位置に対する指数又は位置のリストでもよい。従って、例えば、図２Ａに示す近傍を発生するための近傍ルールは、選択的に以下のいずれのように表わしてもよい：
Ｎ(Sc)＝｛Ｓi：｜ｉ−ｃ｜≦３｝
Ｎ(Sc)＝｛ｃ−３，ｃ−２，ｃ−１，ｃ＋１，ｃ＋２，ｃ＋３｝
ｃｈａｒ  ＮＳｃ［６］；
ｆｏｒ（ｉｎｔ  ｉ＝０；ｉ＜３；ｉ＋＋）ＮＳｃ［ｉ］＝ｉ−３；
ｆｏｒ（ｉ＝３；ｉ＜６；ｉ＋＋）ＮＳｃ［ｉ］＝ｉ−２；
【００１３】
図２Ｂ及び図２Ｃに示す疎で非対称的な近傍は、無原則に見える可能性がある一方で、無原則に定義された近傍は、ある雑音除去の問題領域では有用であることが判明する可能性があり、しばしばそのような一見無原則に定義された近傍は、実のところ、高次の考察から生じる可能性がある。図３Ａ及び図３Ｂは、線形記号配列内の記号のより高次の構成を示す。図３Ａでは、線形記号配列が繰り返し折り畳まれて矩形領域を形成し、その矩形の上左側角に配列の第１の記号３０２、及び、その矩形の下右側角に配列の最後の記号３０４を有する。従って、線形記号配列は、或いは記号の２次元矩形アレイとして見なされる可能性がある。ゼロから始まる指数を仮定すると、１次元の線形記号配列Ｓ(i)から２次元の矩形記号行列Ｓ(j,k)への変換Ｓ(i)→Ｓ(j,k)は、以下によって与えられる：
ｊ＝ｉＭＯＤ  Ｍ；
ｋ＝ｉ／Ｍ；
ここでＭ＝Ｓ(j,k)の行の長さ。
記号の２次元行列における近傍定義位置３０３は、一例として、近傍定義位置３０３を囲む平行線模様の四角形領域３０５として図３Ａに示す２次元行列における８個の最も近接する記号からなる近傍に関連づけられる。
【００１４】
図３Ｂは、線形記号配列内の記号のより複雑でより高度の順序付けを示す。図３Ｂでは、線形記号配列は、より高いレベルでは、繰り返しループ構造と見なされる。３個の近傍定義位置３０６乃至３０８は、配列の濃く塗られた位置として図３Ｂで示され、それら３個の近傍定義位置周囲の近傍は、夫々、平行線模様の位置３１０乃至３１３，３１５乃至３２１，及び３２４乃至３２７として示される。
【００１５】
図４Ａ乃至図４Ｄは、記号配列が１次元の線形配列として示される時の図３Ａ及び図３Ｂに示す４個の近傍を示す。図４Ａは、例えば、近傍定義位置３０３周囲の近傍３０５を示す。図４Ｂ乃至図４Ｄは、図３Ｂにおける位置３０６乃至３０８周囲の近傍を示す。図４Ａ乃至図４Ｄに示す１次元の線形表現において観察される時、近傍は若干無原則的に見える可能性がある。
【００１６】
図３Ａに示す２次元の記号行列は、例えば、写真画像又はその他の記号の２次元の行列に関連する雑音除去の問題に生じる可能性がある。図３Ｂに示す繰り返しループ構造は、モノマー識別子の１次元の線形配列として示される可能性がある蛋白質、核酸、又はその他の高分子の３次元の２次構造に関連した雑音除去の問題に生じる可能性がある。特定の問題領域及び、生体高分子配列データにおいて２次、３次、及び４次構造に関連する近傍を含む異なるタイプのデータの記号による表現から自然に起こる線形の記号配列の多種多様な異なるタイプのより高度な構造及び順序付けが存在する。
【００１７】
図４Ａ乃至図４Ｄで提供される近傍の例が、高次の距離尺度から発生する一方、近傍ルールは、非距離関連の尺度に基づくことができる。例えば、近傍は、周期関数によって、時間順の記号配列における時間的関係によって、及び略無数の代替的考察によって定義される可能性がある。
【００１８】
図２Ａ乃至図２Ｃ及び図４Ａ乃至図４Ｄは、１次近傍を示す。より高次の近傍は、１次近傍から反復的又は再帰的に発生する可能性がある。図５Ａ乃至６Ｃは、１次近傍からの３次近傍の発生を示す。図５Ａは、近傍定義位置５０５に関する簡単な１次近傍Ｎ1５０２及び５０３を示す。図５Ａでは、近傍位置５０２及び５０３は、記号“１”５０６及び５０７によってマークされ、当該位置が、近傍定義位置５０５に関する１次近傍に対応することを意味する。図６Ａは、図５Ａに示す１次近傍５０２及び５０３を発生するために使用される近傍ルールを示す。
【００１９】
図５Ｂに示す２次近傍Ｎ2を発生するために、図５Ａにおける位置５０３及び５０２に対する図６Ｂ及び図６Ｃに示す近傍ルールは、夫々、図５Ａにおける近傍定義位置５０５に対する図６Ａに示す近傍ルールの適用によって発生された１次近傍位置に関する近傍位置を発生するために、位置５０３及び５０２に適用される。これらの新しい２次位置は、図５Ａにおける１次位置５０２及び５０３に追加され、図５Ｂに示す２次近傍５０２，５０７，及び５０８乃至５１１を発生する。近傍定義位置５０５と重複する新たに発生した２次位置は、２次近傍には含まれず、近傍内のそれらの位置は一意であり、低次の位置と重複するより高次の位置は、より高次の近傍内に追加的位置を発生しない。図５Ｃは、図５Ｂに示す２次位置５０８乃至５１１の全てに対して図６Ａに示す近傍ルールを適用することによって得られる３次近傍を示す。従って、配列の位置ｉのためのｌ次近傍Ｎl（ｉ）は、位置ｉの１次から（ｌ−１）次の近傍を連続的に発生することを経て発生される。
【００２０】
図７は、近傍対を示す。記号配列位置ｉに関するｌ次近傍構造は、位置ｉのｌ次近傍における全位置の、位置ｉに関する相対記号配列指数の集合からなる。図７において、位置ｊ７０２のｌ次近傍構造は、位置ｊ−２  ７０４，ｊ−３  ７０６，ｊ＋２  ７０８，及びｊ＋３  ７１０を含む。位置ｉ  ７１２は、図７に見ることができ、位置ｉのｌ次近傍は、ｉ−２  ７１４，ｉ−３  ７１６，ｉ＋２  ７１８，及びｉ＋３  ７２０を含むので、位置７０２と同じ近傍構造を有する。言い換えれば、もし、記号位置において、位置ｊと位置ｉとの間の距離が、ｉ−ｊ７２２として計算され、次に、もし位置ｉが、位置ｊのｌ次近傍における各位置ｋにつき、位置ｊと同じ近傍構造を有するならば、位置ｋ＋ｉ−ｊでのｌ次近傍位置ｉにおける対応する位置が存在する。更に、位置ｉのｌ次近傍における各位置ｐ毎に、位置ｐ−（ｉ−ｊ）での位置ｊのｌ次近傍における近傍位置が存在する。
【００２１】
図７にも示すように、記号配列の最初及び最後の部分へ特別な考慮を払わなくともいいように、モジュラー演算を使用して、線形記号配列を環状にすることができる。すると、図７に示す位置７２５は、記号配列Ｓが環状であるとみなされる時、位置７１２及び７０２と同じｌ次近傍構造を有し、位置７２６は、位置７２５の前の位置と見なされる。従って、位置７２８及び７３０は、位置７２５に関して、位置７１８及び７２０が位置７１２に関する相対的位置を有するのと、位置７０８及び７１０が位置７０２に関する相対的位置を有するのと同じ相対的位置を有する。同様に、位置７３４及び７３６は、位置７２５に関して、位置７１４及び７１６が位置７１２に関する相対的位置を有するのと、位置７０４及び７０６が位置７０２に関する相対的位置を有するのと同じ相対的位置を有する。より簡潔な表記法では：
｜Ｓ｜＝ｎの記号配列Ｓにおいて、
∀ｋ：ｋ∈Ｎ1（ｉ），（ｋ＋ｉ−ｊ）ＭＯＤｎ∈Ｎ1（ｊ）；及び
∀ｐ：ｐ∈Ｎ1（ｊ），（ｐ＋ｊ−ｉ）ＭＯＤｎ∈Ｎ1（ｉ）
の時、Ｎ1（ｉ）＝Ｎ1（ｊ）
【００２２】
（近傍に基づく統計値捕獲）
図８及び図９は、本発明の方法の実施形態が適用され、本発明のシステムの実施形態によって使用される一般的な雑音除去方法を示す。図８は、雑音含有信号から雑音を除去するための本発明の一般的な方法の第１パスを示す。第１パスでは、図８に示すように、雑音含有配列における各記号毎に統計値を収集する。図８は、雑音含有配列Ｚ８０２の第３の記号８０４の統計値の収集を示す。雑音含有配列Ｚにおける第３の記号は、記号“ａ3”である。図８に示す例におけるアルファベットは、４個の記号“ａ1”，“ａ2”，“ａ3”，及び“ａ4”からなる。図８に示す例では、表記“ｎl”によってマークされる各記号の近傍構造は同一であり、配列における記号に最も近い４個の記号からなり、２個の記号は近傍定義位置の指数よりも大きな指数を有し、２個の記号は近傍定義位置の指数よりも小さな指数を有する。図８において、第３の記号８０４の近傍８０６は、雑音含有記号配列Ｚの上方に第３の記号と共に示される。
【００２３】
統計値は、同じ近傍構造及びその近傍構造における同じ近傍コンフィギュレーション（構成）を有する雑音含有記号配列Ｚにおけるその他の記号から現在考察されている記号（現在の例では、記号８０４）に関して収集される。近傍構造は、上記で論じられたように、近傍ルールの適切な適用に従ってｌ次近傍として定義されることができる。図８では、雑音含有配列における各記号の上方に示される表記ｎi、ｉ∈｛０，１，…，９｝、は、その記号の近傍構造を示す。雑音含有記号配列Ｚの第３の記号８０４の近傍構造に関連する近傍構造記号ｎ1８０８は、図８において丸で囲んで示されている。図８において、近傍構造ｎ1を有する雑音含有記号配列Ｚの図示されている部分における他の全ての記号も丸の中に示されている。従って、雑音含有記号配列の記号８０９乃至８１５は全て、第３の記号８０４と同じ近傍構造ｎ1を共有している。これら７個の追加的な記号８０９乃至８１５は、第３の記号８０４の第１パス分析中の統計値収集の候補である。しかしながら、現在考察されている記号の統計値は、現在考察されている記号の近傍構造と同じ近傍構造を共有し、且つ、考察されている記号の近傍構造内の記号コンフィギュレーションと同じ近傍構造内の記号コンフィギュレーションを有する、雑音含有記号配列Ｚの記号から収集される。第３の現在考察されている記号８０４と同じ近傍構造を共有する雑音含有記号配列Ｚの７個の追加的記号の近傍の内容を検討すると、記号８１１，８１２，及び８１４のみが、第３の現在考察されている記号８０４と同じ近傍構造及びその近傍構造内の記号コンフィギュレーションの両方を有することが容易に決定される。
【００２４】
各記号Ｚｃは、ｋ＝｜Ａ｜であるｋに等しいサイズ｜Ｎ’  (c)｜の計数ベクトルＮ’(c)に関連する。図８では、第３の記号８０４に関連する計数ベクトル８２０は、図の上部、雑音含有記号配列Ｚ、及び、第３の現在考察されている記号８０４と同じ近傍構造を有する全記号の近傍コンフィギュレーションの両方の表示の上方に示されている。現在考察されている記号を含み、現在考察されている記号と同じ近傍構造及び同じ近傍構造のコンフィギュレーションを有する、各記号毎に、該記号の値に対応するＮ’(c)の要素がインクリメントされる。図８では、上記で論じられたように、現在考察されている記号８０４と同じ近傍構造及び近傍構造のコンフィギュレーションを共有する４個の記号８０４，８１１，８１２，及び８１４が存在する。従って、記号８０４，８１１，８１２，及び８１４の各値に関連する計数ベクトルＮ’(c)における計数がインクリメントされる。これらの記号値は、順に、“ａ3”，“ａ2”，“ａ1”，及び“ａ4”である。従って、元々ゼロに合わせた計数ベクトルＮ’(c)は、以下の通り、本発明の一般的な雑音除去方法の統計値解析フェーズ中に、雑音含有記号配列Ｚの表示された部分に対して以下のように更新される：
Ｎ’(c)［ａ3］＋＋；
Ｎ’(c)［ａ2］＋＋；
Ｎ’(c)［ａ1］＋＋；
Ｎ’(c)［ａ4］＋＋；
同一の構造及びコンフィギュレーションの近傍８０６，８２２，８２３，及び８２４内の中央記号として各記号値の一回の発生が存在するので、現在考察されている記号Ｚ3，Ｎ’(3)に関連する計数ベクトルは、各要素において計数値“１”を有する。一般に、実践的状況で、計数ベクトルは、一般的に、近傍の記号内容と、対応する近傍定義位置の記号間の相関関係を反映した異なる計数値の分布を含む結果となる。
【００２５】
近傍ルールは、雑音含有記号配列における各記号に適用される必要があることに留意すべきである。近傍ルールが、ｌが１よりも大きくかつ単一１次近傍ルールを超えるものが、１からｌまでのどの近傍次数のレベルでも適用可能である場合において、ｌ次近傍の計算を符号化する場合、雑音含有記号配列Ｚ内の任意の２個の所定の位置ｉ及びｊは、異なる近傍構造を有することができる。
【００２６】
雑音含有記号配列Ｚ内の各記号が、本発明の一実施形態を表わす一般的な方法の第１パスにおいて夫々考察された後、計数ベクトルは、各雑音含有記号と関連付けられている。図９は、本発明の一般的な雑音除去方法の第１パスの結果を示す。図９に示されるように、記号９０２等の、雑音含有記号配列Ｚ内の位置ｃの各雑音含有記号配列の記号は、雑音含有記号配列の記号９０２の真下の列ベクトルとして示される、計数ベクトル９０４等の計数ベクトルＮ’(c)に関連する。
【００２７】
本発明の別の実施形態では、計数ベクトルは、個々の記号よりもむしろ、又は個々の記号に加えて、記号のグループに関連し、従って、統計値は、個々の記号よりもむしろ、又は個々の記号に加えて、記号グループに関して収集されることができる。
【００２８】
本発明の実施形態を表わす一般的な雑音除去方法の第２パスでは、雑音除去ルールは、各雑音含有記号配列の記号、及び関連の計数ベクトルに適用され、雑音含有記号配列の記号に対応する雑音が除去された清浄化（ｃｌｅａｎｅｄ）記号値：Ｘ’ｃ＝Ｄ（Ｚc，Ｎ(c)）を発生する、ここで、Ｄは雑音除去ルールである。多くの異なるルールは、雑音含有記号配列の記号、及び関連の計数ベクトルに適用され、対応する雑音が除去された記号を発生する。上記で論じたように、雑音が除去された信号の記号が選択されるアルファベットは、雑音含有信号の記号が選択されるアルファベットと同じ又は異なる可能性がある。加えて、ある問題領域では、単一の雑音除去された信号の記号は、２個以上の雑音含有信号の記号から発生する可能性があり、多数の雑音除去された信号の記号は、単一の雑音含有信号の記号から発生する可能性がある。雑音含有記号配列の記号及び対応する計数ベクトルに加えて、雑音除去ルールは、雑音含有記号の配列Ｚについて及び最初の清浄配列Ｘについての追加的情報も使用する可能性がある。統計的にモデル化された雑音汚染が確率的にモデル化されたチャネルに導入される問題領域において、及び、様々な起こり得る雑音含有信号の近傍の各々において特定の清浄信号の記号の代わりに特定の雑音含有信号の記号の発生の同時確率分布を仮定し計算する問題領域において、雑音除去ルールは、同時確率分布に基づいて、清浄化信号の記号の期待値Ｘ’iを計算することができる：
Ｘ’i＝Ｅ（Ｘi，｜Ｚi，Ｎ’(i)）。
代わりに、雑音除去ルールは、単に、供給される信号及び関連の計数ベクトルに完全に基づく単純なアルゴリズム又は数式からなることができる。追加的情報を使用する雑音除去ルールの一例は、雑音誘発プロセス、媒体、又はデバイスに関連する記号汚染の確率、及び、雑音含有記号の配列に対応する雑音除去された記号配列において雑音含有記号配列の記号を代わりの記号と交換することによって生成される歪みを数値化する損失関数に依存する個々の汎用雑音除去機能のクラスの一例である。単純なアルゴリズム雑音除去ルールの一例は、境界確率  ０≧δ＜１／２を有する２進対称チャネル（「ＢＳＣ」：ｂｉｎａｒｙ  ｓｙｍｍｅｔｒｉｃ  ｃｈａｎｎｅｌ）の多数決雑音除去ルールである：
Ｄ（Ｚj，Ｎ’）＝｛Ｎ’(0)≧Ｎ’(1)の時０／そうでなければ１｝
【００２９】
本発明の他の実施形態では、雑音除去ルールは、個々の記号よりもむしろ、又は個々の記号に加えて、記号のグループに適用される可能性があり、従って、置き換え記号又は置き換え記号のグループが、個々の記号よりもむしろ、又は個々の記号に加えて、記号グループに関して発生する可能性がある。
【００３０】
（Ｃ＋＋風疑似コードによる実施形態）
次に、本発明の比較的単純なＣ＋＋風疑似コードの実施形態が提供される。この疑似コードは、本発明を定義する又は本発明の範囲を制限することは決して意図しておらず、単に本発明に従う一般的な雑音除去機能を実施するための一つのアプローチを示すことを意図している。
【００３１】
まず、定数の数及びタイプ宣言が提供される：
１  ｃｏｎｓｔ  ｉｎｔ  Ｋ  ＝  １０；
２  ｃｏｎｓｔ  ｉｎｔ  ｍａｘＮｅｉｇｈｂｏｒｈｏｏｄＳｚ  ＝  ５
３  ｃｏｎｓｔ  ｉｎｔ  ｍａｘＮ  ＝  １０００；
４  ｃｏｎｓｔ  ｉｎｔ  ｍａｘＯｒｄｅｒ  ＝  ７；
５  ｔｙｐｅｄｅｆ  ｉｎｔ  ＣＯＵＮＴ＿ＶＥＣＴＯＲ［Ｋ］；
６  ｔｙｐｅｄｅｆ  ｉｎｔ  （*ｄｅｎｏｉｓｉｎｇＲｕｌｅ）（ｉｎｔ*ｃ，ｉｎｔ  ｚ）；
定数Ｋは、アルファベットのサイズ及び計数ベクトルのサイズである。上記のライン２上に宣言されている定数ｍａｘＮｅｉｇｈｂｏｒｈｏｏｄＳｚは、雑音含有記号配列の一つの位置に関する任意の近傍構造内の位置の最大数である。上記のライン３上に宣言されている定数ｍａｘＮは、雑音含有記号配列の最大長である。上記のライン４上に宣言されている定数ｍａｘＯｒｄｅｒは、指定できる最大近傍次数である。上記のライン５上に宣言されているタイプＣＯＵＮＴ＿ＶＥＣＴＯＲは、雑音含有記号の配列における単一の記号に関する統計値の収集の計数ベクトルを表わす。上記のライン６上に宣言されているタイプ「ｄｅｎｏｉｓｉｎｇＲｕｌｅ」は、本発明の雑音除去方法に供給される雑音除去ルール関数の参照タイプである。
【００３２】
次に、単純な近傍クラスが提供される：
１  ｃｌａｓｓ  ｎｅｉｇｈｂｏｒｈｏｏｄ
２  ｛
３    ｐｒｉｖａｔｅ：
４                  ｉｎｔ  ｉｎｄｉｃｅｓ［ｍａｘＮｅｉｇｈｂｏｒｈｏｏｄＳｚ］；
５                  ｉｎｔ  ｓｉｚｅ；
６
７    ｐｕｂｌｉｃ：
８                ｉｎｔ＊ｗｒａｐ（ｉｎｔ*Ｓｔａｒｔ，ｉｎｔ*ｉ，ｉｎｔ  ｓｚ）；
９                ｖｏｉｄ  ｅｎｔｅｒ（ｉｎｔ  ｒｅｌＩｎｄｅｘ）；
１０                ｖｏｉｄ  ｃｌｅａｒ（）｛ｓｉｚｅ＝０；｝；
１１                ｉｎｔ  ｇｅｔＲｅｌＩｎｄｅｘ（ｉｎｔ  ｉ）
１２                              ｛ｉｆ（ｉ＜ｓｉｚｅ＆＆｜＞＝０）ｒｅｔｕｒｎ  ｉｎｄｉｃｅｓ［１］；ｅｌｓｅ  ｒｅｔｕｒｎ０；｝；
１３                ｉｎｔ  ｇｅｔＳｉｚｅ（）｛ｒｅｔｕｒｎ  ｓｉｚｅ；｝；
１４                ｂｏｏｌ  ｅｑｕａｌＮＣｏｎｆｉｇ（ｉｎｔ＊ｓｔａｒｔ，ｉｎｔ*ｌ，ｉｎｔ*ｊ，ｉｎｔ  ｓｚ）；
１５                ｂｏｏｌ  ｅｑｕａｌＮＳｔｒｕｃｔｕｒｅ（ｎｅｉｇｈｂｏｒｈｏｏｄ＊ｎ）；
１６                ｎｅｉｇｈｂｏｒｈｏｏｄ（）；
１７｝；
近傍を定義する相対指数は、ライン４上に宣言されているプライベートデータメンバーアレイ「ｉｎｄｉｃｅｓ」に格納される。ライン５上に宣言されているプライベートデータメンバー「ｓｉｚｅ」は、プライベートデータメンバーアレイ「ｉｎｄｉｃｅｓ」に格納されている近傍の定義内の相対指数の数を意味する。クラス「ｎｅｉｇｈｂｏｒｈｏｏｄ」は、コンストラクターに加えて、上記のライン８乃至１５上に宣言されている以下のパブリック関数メンバーを含む：（１）記号位置にモジュラー演算を実行して線形記号配列を環状にする関数ｗｒａｐ；（２）プライベートデータメンバー「ｉｎｄｉｃｅｓ」に相対指数を入力する関数ｅｎｔｅｒ；（３）クラス「ｎｅｉｇｈｂｏｒｈｏｏｄ」のインスタンスを再初期化する関数ｃｌｅａｒ；（４）指定された位置でのプライベートデータメンバー「ｉｎｄｉｃｅｓ」を戻す関数ｇｅｔＲｅｌＩｎｄｅｘ；（５）プライベートデータメンバー「ｉｎｄｉｃｅｓ」における相対指数の数を戻す関数ｇｅｔＳｉｚｅ；（６）第１記号の近傍が他の指定の記号の近傍と同じ記号コンフィギュレーションを有するか否かを断定する関数ｅｑｕａｌＮＣｏｎｆｉｇ；及び（７）クラス「ｎｅｉｇｈｂｏｒｈｏｏｄ」のインスタンスが、クラス「ｎｅｉｇｈｂｏｒｈｏｏｄ」の特定のインスタンスと同じ近傍構造を有するか否かを決定する関数ｅｑｕａｌＮＳｔｒｕｃｔｕｒｅ．
【００３３】
次に、近傍ルールに対するタイプ宣言が提供される：
１  ｔｙｐｅｄｅｆ  ｖｏｉｄ（*ｎｅｉｇｈｂｏｒｈｏｏｄＲｕｌｅ）（ｉｎｔ*ｓｔａｒｔ，ｉｎｔ*ｉ，ｉｎｔ  ｓｚ，
２                            ｎｅｉｇｈｂｏｒｈｏｏｄ*ｎ，ｉｎｔ  ｏｒｄｅｒ）；。
次に、雑音除去機能のクラスが提供される：
１  ｃｌａｓｓ  ｄｅｎｏｉｓｅｒ
２  ｛
３        ｐｒｉｖａｔｅ：
４                ＣＯＵＮＴ＿ＶＥＣＴＯＲ  ｃｏｕｎｔＶｓ［ｍａｘＮ］：
５                ｄｅｎｏｉｓｉｎｇＲｕｌｅ  ｄＲｕｌｅ；
６                ｎｅｉｇｈｂｏｒｈｏｏｄＲｕｌｅ  ｎＲｕｌｅ；
７                Ｉｎｔ  ｏｒｄｅｒ；
８
９        ｐｕｂｌｉｃ：
１０              ｖｏｉｄ  ｄｅｎｏｉｓｅ（ｉｎｔ*ｚ，ｉｎｔ  ｎ，ｉｎｔ*ｘＨａｔ）；
１１              ｄｅｎｏｉｓｅｒ（ｉｎｔ  ｏｒｄｅｒ，ｄｅｎｏｉｓｉｎｇＲｕｌｅ  ｄＲ，ｎｅｉｇｈｂｏｒｈｏｏｄＲｕｌｅ  ｎＲ）；
１２  ｝：
クラス「ｄｅｎｏｉｓｅｒ」は、ライン４上に宣言された雑音含有記号配列のｍａｘＮ記号までの計数ベクトル、ｃｏｕｎｔＶｓ、ライン５と６上に夫々宣言された雑音除去ルールと近傍ルール“ｄＲｕｌｅ”と“ｎＲｕｌｅ”に対する参照、及び本発明の実施の形態を表す雑音除去方法の第１のパス中の記号を演算するための近傍順序を含む整数順序を含む。コンストラクターに加えて、クラス「ｄｅｎｏｉｓｅｒ」は、供給された雑音含有記号配列から雑音を除去して、清浄化記号配列を生成する、上記のライン１１に宣言されている関数メンバー「ｄｅｎｏｉｓｅ」を含む。
【００３４】
クラス「ｎｅｉｇｈｂｏｒｈｏｏｄ」の関数メンバーの実施が次に提供される。まず、関数メンバー「ｗｒａｐ」を提示する：
１  Ｉｎｔ*ｎｅｉｇｈｂｏｒｈｏｏｄ：：ｗｒａｐ（ｉｎｔ*ｓｔａｒｔ，ｉｎｔ*ｉ，ｉｎｔ  ｓｚ）
２  ｛
３    ｉｆ（ｉ＜ｓｔａｒｔ）ｉ+＝ｓｚ；
４    ｅｌｓｅ  ｉｆ（ｉ＞＝ｓｔａｒｔ＋ｓｚ）ｉ−＝ｓｚ；
５    ｒｅｔｕｒｎ  ｉ；
６  ｝
関数メンバー「ｗｒａｐ」は、記号ｉへの供給された参照が、引数「ｓｔａｒｔ」によって参照される始発記号及びｓｔａｒｔ＋ｓｚ−１によって参照される最終記号を有する記号配列の範囲の外側か否かを決定する。もしｉが記号の有効位置の外側ならば、関数ｗｒａｐは、モジュラー演算を介してｉを調節し、記号配列内の位置を参照するようにし、原則的に記号配列を環状にする。
【００３５】
まず、関数メンバー「ｅｎｔｅｒ」が提供される：
１  ｖｏｉｄ  ｎｅｉｇｈｂｏｒｈｏｏｄ：：ｅｎｔｅｒ（ｉｎｔ  ｒｅｌＩｎｄｅｘ）
２  ｛
３    ｉｎｔ  ｐ；
４
５    ｉｆ（ｓｉｚｅ＝＝ｍａｘＮｅｉｇｈｂｏｒｈｏｏｄＳｚ）ｒｅｔｕｒｎ；
６    ｆｏｒ（ｐ＝０；  ｐ＜ｓｉｚｅ；ｐ＋＋）ｉｆ（ｉｎｄｉｃｅｓ［ｐ］＝＝ｒｅｌＩｎｄｅｘ）ｒｅｔｕｒｎ；
７    ｉｎｄｉｃｅｓ［ｓｉｚｅ++］＝ｒｅｌＩｎｄｅｘ；
８  ｝
関数メンバー「ｗｒａｐ」は、記号ｉへの供給された参照が、引数「ｓｔａｒｔ」によって参照される始発記号及びｓｔａｒｔ＋ｓｚ−１によって参照される最終記号を有する記号配列の範囲の外側か否かを決定する。もしｉが記号の有効位置の外側ならば、関数ｗｒａｐは、モジュラー演算を介してｉを調節し、記号配列内の位置を参照するようにし、原則的に記号配列を環状にする。
【００３６】
次は、関数メンバー「ｅｑｕａｌＮＳｔｒｕｃｔｕｒｅ」が提供される：
１  ｂｏｏｌ  ｎｅｉｇｈｂｏｒｈｏｏｄ：：ｅｑｕａｌＮＳｔｒｕｃｔｕｒｅ（ｎｅｉｇｈｂｏｒｈｏｏｄ*ｎ）
２  ｛
３      ｉｎｔ  ｐ，ｑ；
４      ｉｎｔ  ｎｘｔ；
５      ｂｏｏｌ  ｒｅｓ；
６
７      ｉｆ（ｎ−＞ｇｅｔＳｉｚｅ（）！＝ｓｉｚｅ）ｒｅｔｕｒｎ  ｆａｌｓｅ；
８      ｆｏｒ（ｐ＝０；ｐ＜ｓｉｚｅ；ｐ++）
９      ｛
１０          ｎｘｔ＝ｎ−＞ｇｅｔＲｅｌＩｎｄｅｘ（ｐ）；
１１          ｒｅｓ＝ｆａｌｓｅ；
１２          ｆｏｒ（ｑ＝０；ｑ＜ｓｉｚｅ；ｑ++）
１３          ｛
１４              ｉｆ（ｎｘｔ＝＝ｉｎｄｉｃｅｓ［ｑ］）
１５              ｛
１６                    ｒｅｓ＝ｔｒｕｅ；
１７                    ｂｒｅａｋ；
１８                ｝
１９      ｝
２０      ｉｆ（！ｒｅｓ）ｒｅｔｕｒｎ  ｆａｌｓｅ；
２１  ｝
２２  ｒｅｔｕｒｎ  ｔｒｕｅ；
２３｝
関数メンバー「ｅｑｕａｌＮＳｔｒｕｃｔｕｒｅ」は、近傍クラス“ｎ”のインスタンスへの供給された参照が、関数メンバー「ｅｑｕａｌＮＳｔｒｕｃｔｕｒｅ」を介して呼び出される近傍クラスのインスタンスと同じ構造を有するか否かを決定する。ライン７上では、もし相対指数の数がその２個のクラスで異なるならばＦＡＬＳＥが戻される。そうでなければ、ライン８乃至２１の入れ子のＦＯＲループにおいて、データメンバーアレイ「ｉｎｄｉｃｅｓ」の内容は、クラス「ｎｅｉｇｈｂｏｒｈｏｏｄ」の２個のインスタンスに関して比較される。その２個のアレイの内容が異なる時は値ＦＡＬＳＥが戻され、その２個のアレイの内容が同じ時はＴＲＵＥが戻される。２個のアレイにおける相対指数の順序付け重要ではない。
【００３７】
次に、関数メンバー「ｅｑｕａｌＮＣｏｎｆｉｇ」が提供される：
１  ｂｏｏｌ  ｎｅｉｇｈｂｏｒｈｏｏｄ：：ｅｑｕａｌＮＣｏｎｆｉｇ（ｉｎｔ*ｓｔａｒｔ，ｉｎｔ*ｉ，ｉｎｔ*ｊ，ｉｎｔ  ｓｚ）
２  ｛
３
４        ｉｎｔ  ｐ；
５        ｉｎｔ*ｎｘｔＩ：
６        ｉｎｔ*ｎｘｔＪ：
７        ｂｏｏｌ  ｒｅｓ＝ｔｒｕｅ：
８
９        ｆｏｒ（ｐ＝０；ｐ＜ｓｉｚｅ；ｐ++）
１０      ｛
１１            ｎｘｔＩ＝ｗｒａｐ（ｓｔａｒｔ，ｉｎｄｉｃｅｓ［ｐ］＋ｉ，ｓｚ）；
１２            ｎｘｔＪ＝ｗｒａｐ（ｓｔａｒｔ，ｉｎｄｉｃｅｓ［ｐ］＋ｊ，ｓｚ）；
１３            ｉｆ（*ｎｘｔＩ＝*ｎｘｔＪ）
１４            ｛
１５                  ｒｅｓ＝ｆａｌｓｅ；
１６                  ｂｒｅａｋ；
１７              ｝
１８      ｝
１９      ｒｅｔｕｒｎ  ｒｅｓ；
２０  ｝
関数メンバー「ｅｑｕａｌＮＣｏｎｆｉｇ」は、２個の近傍定義位置について、クラス「ｎｅｉｇｈｂｏｒｈｏｏｄ」のインスタンスによって表わされる近傍のコンフィギュレーションが、同一であるか否かを決定する。ライン９乃至１９のＦＯＲループにおいて、供給された記号参照ｉによって参照される記号の近傍における各記号は、供給された記号参照ｊによって参照される記号の近傍における対応する記号と比較される。２個の各近傍の全記号が等しい時、ＴＲＵＥが戻される。そうでなければ、ＦＡＬＳＥが戻される。
【００３８】
最後に、追加的な注釈なしにコンストラクターが提供される：
１  ｎｅｉｇｈｂｏｒｈｏｏｄ：：ｎｅｉｇｈｂｏｒｈｏｏｄ（）
２  ｛
３      ｓｉｚｅ＝０
４    ｝
【００３９】
次に、クラス「ｄｅｎｏｉｓｅｒ」の関数メンバーの実行が提供される：まず、関数メンバー「ｄｅｎｏｉｓｅ」が提供される：
１  ｖｏｉｄ  ｄｅｎｏｉｓｅｒ：：ｄｅｎｏｉｓｅ（ｉｎｔ*ｚ，ｉｎｔ  ｎ，ｉｎｔ*ｘＨａｔ）
２  ｛
３      ｉｎｔ  ｉ，ｊ：
４      ｉｎｔ  ｎｘｔ；
５      ｎｅｉｇｈｂｏｒｈｏｏｄ  ｎｉ，ｎｊ；
６
７      ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ++）
８      ｛
９            ｎＲｕｌｅ（ｚ，ｚ＋ｉ，ｎ，＆ｎｉ，ｏｒｄｅｒ）；
１０          ｆｏｒ（ｊ＝０；ｊ＜ｎ；ｊ++）
１１          ｛
１２          ｉｆ（ｊ，！＝１）
１３          ｛
１４                ｎＲｕｌｅ（ｚ，ｚ＋ｊ，ｎ，＆ｎｊ，ｏｒｄｅｒ）；
１５                ｉｆ（ｎｉ．ｅｑｕａｌＮＳｔｒｕｃｔｕｒｅ（＆ｎｊ）＆＆ｎｊ．ｅｑｕａｌＮＣｏｎｆｉｇ（ｚ，ｚ＋ｉ，ｚ＋ｊ，ｎ））
１６                （
１７                      ｎｘｔ＝*（ｚ＋ｊ）；
１８                      ｉｆ（ｎｘｔ＜０）ｎｘｔ＝０；
１９                      ｉｆ（ｎｘｔ＞＝Ｋ）ｎｘｔ＝Ｋ−１；
２０                      ｃｏｕｎｔＶｓ［ｉ］［ｎｘｔ］++；
２１                  ｝
２２            ｝
２３          ｝
２４        ｝
２５        ｆｏｒ（ｉ＝０；｜＜ｎ；｜++）
２６        ｛
２７              *（ｘＨａｔ＋ｉ）＝ｄＲｕｌｅ（＆（ｃｏｕｎｔＶｓ［１］［０］），*（ｚ＋ｉ））；
２８      ｝
２９  ｝
ライン２４の外側のＦＯＲループは、本発明の一実施形態を表わす一般的な雑音除去方法の第１パスを実施する。この外側ＦＯＲループでは、雑音含有記号配列の各記号を順々に考察する。ライン１２乃至２２の内側ＦＯＲループでは、外側のＦＯＲループに関して現在考察されている記号の近傍は、その他の全記号の近傍と比較され、現在考察されている記号の近傍は、内側のＦＯＲループに関して現在考察されている記号と同じコンフィギュレーション及び構成を有し、図８を参照して上記で論じられたように、現在考察されている記号の計数ベクトルが更新される。ライン２５乃至２８のＦＯＲループは、本発明の一実施形態を表わす一般的な雑音除去方法の第２パスを実施する。
【００４０】
最小限の注釈で、クラス「ｄｅｎｏｉｓｅｒ」のコンストラクターを提示する：
１  ｄｅｎｏｉｓｅｒ：：ｄｅｎｏｉｓｅｒ（ｉｎｔ  ｏｒｄ，ｄｅｎｏｉｓｉｎｇＲｕｌｅ  ｄＲ，ｎｅｉｇｈｂｏｒｈｏｏｄＲｕｌｅ  ｎＲ）
２｛
３      ｉｎｔ  ｉ，ｊ；
４
５      ｉｆ（ｏｒｄ＞＝１＆＆ｏｒｄ＜＝ｍａｘＯｒｄｅｒ）ｏｒｄｅｒ＝ｏｒｄ；
６      ｅｌｓｅ  ｏｒｄ＝１；
７      ｎＲｕｌｅ＝ｎＲ；
８      ｄＲｕｌｅ＝ｄＲ；
９      ｆｏｒ（ｉ＝０；ｉ＜ｍａｘＮ；ｉ++）
１０    ｛
１１            ｆｏｒ（ｊ＝０；ｊ＜Ｋ；ｊ＋＋）ｃｏｕｎｔＶｓ［ｉ］［ｊ］＝０；
１２    ｝
１３  ｝
【００４１】
最後に、単純な雑音除去方法、単純な近傍ルール、及び例示の主関数が提供される：
１  ｉｎｔ  ｄＲｕｌｅ（ｉｎｔ*ｃ，ｉｎｔ  ｚ）
２  ｛
３        ｉｎｔ  ｉ；
４        ｉｎｔ  Ｊ＝０；
５        ｉｎｔ  ｎ＝０；
６
７        ｆｏｒ（ｉ＝０；ｉ＜Ｋ；ｉ++）
８        ｛
９              ｉｆ（ｃ［ｉ］＞ｎ）
１０            ｛
１１                    ｎ＝ｃ［ｌ］；
１２                    ｊ＝ｌ；
１３            ｝
１４      ｝
１５      ｒｅｔｕｒｎ  ｊ；
１６  ｝
上記の雑音除去ルールは、交換記号として、雑音含有記号配列の記号の近傍における最高頻度で発生する記号を選択する。
１  ｖｏｉｄ  ｎＲｕｌｅ（ｉｎｔ*  ｓｔａｒｔ，ｉｎｔ*  Ｉ，ｉｎｔ  ｓｚ，ｎｅｉｇｈｂｏｒｈｏｏｄ*ｎ，ｉｎｔ  ｏｒｄｅｒ）
２  ｛
３      ｉｎｔｊ，ｋ，ｍ，ｓＺ；
４      ｉｎｔ*ｎｘｔ；
５      ｎｅｉｇｈｂｏｒｈｏｏｄ  ｔｍｐ；
６
７      ｎ−＞ｃｌｅａｒ（）；
８      ｉｆ（*ｉ％２）
９      ｛
１０          ｎ−＞ｅｎｔｅｒ（−１）；
１１          ｎ−＞ｅｎｔｅｒ（１）；
１２    ｝
１３    ｅｌｓｅ
１４    ｛
１５          ｎ−＞ｅｎｔｅｒ（−２）；
１６          ｎ−＞ｅｎｔｅｒ（−１）；
１７          ｎ−＞ｅｎｔｅｒ（１）；
１８          ｎ−＞ｅｎｔｅｒ（２）；
１９    ｝
２０    ｆｏｒ（ｊ＝１；ｊ＜ｏｒｄｅｒ；ｊ++）
２１    ｛
２２            ｓＺ＝ｎ−＞ｇｅｔＳｉｚｅ（）；
２３            ｆｏｒ（ｋ＝０；ｋ＜ｓＺ；ｋ++）
２４            ｛
２５                  ｎｘｔ＝ｎ−＞ｗｒａｐ（ｓｔａｒｔ，ｎ−＞ｇｅｔＲｅｌＩｎｄｅｘ（ｋ）＋ｉ，ｓｚ）；
２６                  ｎＲｕｌｅ（ｓｔａｒｔ，ｎｘｔ，ｓｚ，＆ｔｍｐ，１）；
２７                  ｆｏｒ（ｍ＝０；ｍ＜ｔｍｐ．ｇｅｔＳｉｚｅ（）；ｍ++）
２８                  ｛
２９                            ｎ−＞ｅｎｔｅｒ（ｔｍｐ．ｇｅｔＲｅｌＩｎｄｅｘ（ｍ））；
３０                    ｝
３１
３２          ｝
３３    ｝
３４  ｝
【００４２】
上記の近傍ルールは、記号位置（ｌｏｃａｔｉｏｎ）のパリティ次第で、２個の異なるタイプの近傍を選択及び発生する。
１  ｉｎｔ  ｍａｉｎ（ｉｎｔ  ａｒｇｃ，ｃｈａｒ*ａｒｇｖ［］）
２  ｛
３
４        ｉｎｔ  ｚ［３０］＝｛１，２，３，４，５，５，４，３，２，１，１，２，３，４，５，５，４，３，２，１，１，２，３，４，５，５，４，３，２，１｝；
５
６        ｉｎｔ  ｘ［３０］；
７
８        ｄｅｎｏｉｓｅｒ  ｄ（２，ｄＲｕｌｅ，ｎＲｕｌｅ）；
９        ｄ．ｄｅｎｏｉｓｅ（ｚ，３０，ｘ）；
１０      ｒｅｔｕｒｎ０；
１１  ｝
【００４３】
（特定の問題領域への適用）
本発明の方法の実施形態が対象とする一般的な雑音除去方法は、本発明の多種多様な異なる指定の雑音除去方法の実施形態のアルゴリズム的フレームワークを提供する。例えば、低密度パリティ検査（ＬＤＰＣ：Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号は、ＬＤＰＣ符号のタナーグラフ（Ｔａｎｎｅｒ  ｇｒａｐｈ）から得られる適切なＬＤＰＣベースの雑音除去ルール及び近傍ルールを使用して復号される。この例では、近傍は、同一のパリティ行列の行に対するタナーグラフのエッジによって関連付けられたパリティ行列の列に対応する記号位置からなる。
【００４４】
本発明の方法の実施形態は、雑音を誘導する媒体、プロセス、又はデバイスの雑音を誘導する特性に関する情報を採用する必要がなく、利用可能な時に、雑音除去ルールを介してそのような情報を採用することができる。本発明の方法の実施形態は、任意の濃度の記号配列のアルファベットのために使用することができる。本発明の方法の実施形態の計算の複雑性及び性能は、信念伝搬復号を含む、その他の現在利用可能な方法の計算の複雑性及び性能に匹敵又は超越する。最後に、適用可能な多種多様な異なるタイプの近傍ルールによって、本発明の方法の実施形態は、２次元画像、線形指定情報の３次元構造、及びより高次元の情報を含むより高度な構成を有する記号配列から雑音を除去するために使用される。
【００４５】
（結論）
本発明は、特定の実施形態に関して記述されたが、本発明をそれらの実施形態に限定することは意図していない。本発明の精神に基づく改良は、当業者に明白である。例えば、本発明の多くの異なる実施形態は、異なるプログラミング言語、制御構造、モジュール構成、データ構造を使用して、及びその他そのようなプログラミングパラメータを変化することによって実施することができる。本発明のシステムの実施形態は、１個以上のプロセッサ、メモリ、及び本発明の方法の実施形態を実施するソフトウェア又はファームウェアによって用いられる格納された近傍発生及び雑音除去ルールを含む、コンピュータシステム及びその他の電子デバイスを含む。上述のように、本発明の一般的な雑音除去方法、及び本発明の雑音除去方法を組み込む雑音除去システムは、雑音除去プロセスを実行するために、近傍発生ルーティン及び雑音除去ルールが供給される。近傍ルールは、上述のように、任意の次数であり、Ｎ個の記号を含む雑音含有記号配列内の近傍定義位置に関する１個からＮ−１個の記号を発生する。上述のように、多種多様な異なる雑音除去ルールは、異なる問題領域に適用され、供給された雑音含有記号配列の記号及び関連する計数ベクトルのみに頼るものもあれば、雑音含有記号配列に雑音を導入する雑音誘導プロセス、媒体、又はデバイスに関する追加的な情報、及び元の清浄記号配列に関する情報に頼るものもある。上述の方法は、大容量記憶装置制御装置、通信制御装置、プリンタ及びスキャナ、データ解析ソフトウェア及びシステム、及びその他多くのデバイス及びプロセスを含む、データ送信及びデータ処理に使用される多種多様な異なるデバイス及びプロセスに組み込むことができる。ある実施形態では、雑音含有記号配列の第１パスの横行（Ｔｒａｖｅｒｓｅ）の各反復中に近傍を再計算するよりもむしろ、各雑音含有記号配列の記号に関して、近傍ルールの適用によって、近傍を発生する方がより計算効率が良い。上述のように、本発明のある実施形態が、閉じた記号変換、及び雑音除去によって生成される清浄化信号が受信された雑音含有記号配列と同じ長さを有することを想定する、一方で、これらの制約は、本発明のある実施形態において若干緩和される可能性がある。加えて、統計値を収集する記号を特定するための近傍等価は、上述の実施形態において、２個の近傍に同一のコンフィギュレーション及び構造を有するよう要求するように、記述される一方で、本発明のある実施形態において、等価基準も緩和され、記号の大きな集合が、雑音含有記号配列において任意の与えられている現在考察されている記号に関して統計値収集するために使用可能になる。
【００４６】
先行の記述は、本発明が完全に理解されるように、説明目的で、独特の用語を使用した。しかしながら、その具体的な詳細は、本発明を実践するために必要ではないことは当業者に明らかである。本発明の具体的な実施形態の先行する記述は、例示及び説明のために与えられている。それらの記述は、完全なものであること、又は、開示された正確な形式に本発明を制限することは意図していない。上記の教示を考慮した上で、多くの改良及び変形が可能である。実施形態は、本発明の原則及びその実際の適用を最良に説明し、それによって当業者が、意図する具体的な使用に適するように様々な改良によって本発明及び様々な実施形態を最良に利用できるように、示され記述されている。本発明の範囲は、以下の特許請求の範囲及びそれらの等価物によって定義されることが意図されている。
【図１】
2010534972.tif 000003
【図２Ａ】
2010534972.tif 000004
【図２Ｂ】
2010534972.tif 000005
【図２Ｃ】
2010534972.tif 000006
【図３Ａ】
2010534972.tif 000007
【図３Ｂ】
2010534972.tif 000008
【図４Ａ】
2010534972.tif 000009
【図４Ｂ】
2010534972.tif 000010
【図４Ｃ】
2010534972.tif 000011
【図４Ｄ】
2010534972.tif 000012
【図５Ａ】
2010534972.tif 000013
【図５Ｂ】
2010534972.tif 000014
【図５Ｃ】
2010534972.tif 000015
【図６Ａ】
2010534972.tif 000016
【図６Ｂ】
2010534972.tif 000017
【図６Ｃ】
2010534972.tif 000018
【図７】
2010534972.tif 000019
【図８】
2010534972.tif 000020
【図９】
2010534972.tif 000021
【国際調査報告】
2010534972.tif 000022
2010534972.tif 000023